Solved-Homework -Assignment 7 -Solution

Description

Question 1: N-gram Language Modeling [60 points]

In this question you will implement a chatbot by generating random sentences from your HW1 corpus using n-gram language models with Laplace smoothing.

We have created a vocabulary le vocabulary.txt for you to interpret the data, though you do not need it for programming. The vocabulary is created by tokenizing the corpus, converting everything to lower case, and keeping word types that appears three times or more. There are 4699 lines in the vocabulary.txt le.

Download the le corpus.txt from the homework website. This le has one word token per line, and we have already converted the word to its index (line number) in vocabulary.txt. Thus you will see word indices from 1 to 4699. In addition, we have a special word type OOV (out of vocabulary) which has index 0. All word tokens that are not in the vocabulary map to OOV. For example, the rst OOV in the corpus appears as

392	are
1512	entirely

• undermined

12.

The words on the right are provided from the original essays for readability, they are not in the corpus. The word \undermined” is not in the vocabulary, therefore it is mapped to OOV and have an index 0. OOV represents a set of out-of-vocabulary words such as \undermined, extra-developed, metro, customizable, optimizable” etc. But for this homework you can treat OOV as a single special word type. Therefore, the vocabulary has v = 4700 word types. The corpus has 228548 tokens.

Note:

Please make sure the outputs are formatted exactly as described in this document. A sample test script is provided which compares your outputs with the expected outputs. Please make sure that all the test cases pass before submitting. No points will be awarded if the output doesn’t match exactly, even if the algorithm is correctly implemented.

Write a program Chatbot.java with the following command line format, where the commandline input has variable length¹ and the numbers are integers:

$java Chatbot FLAG number1 [number2 number3 number4]

(Part a, 5 points) Denote the vocabulary by the v word types w₀; w₁; : : : ; w_{v 1} in the order of their index (so w₀ has index 0 and represents OOV, and so on). For this homework it is important that you keep this order so that we can automatically grade your code.

You will rst create a unigram language model with add-one Laplace smoothing. This is a probability

distribution over the vocabulary, for word type w 2 f0; : : : ; v		1g the estimated probability is
pi p(w = i) =	c(w = i) + 1
			;
	n + jV j

where c(w = i) is the count of word type i in the corpus (i.e. how many times w_i appeared). Note you need to estimate and store p_i for all v word types, including OOV: p(w = OOV ) is the fraction of 0’s in the corpus. Your p(w) should sum to 1 over the vocabulary, including OOV.

CS 540

$java Chatbot 200 32 1000

0

0.0000000

0.0320174

$java Chatbot 200 321 10000

1

0.0320174

0.0321761

$java Chatbot 200 5000 10000

2364

0.4999528

0.5144953

$java Chatbot 200 99997 100000

4699

0.9999614

1.0000000

(Part c, 10 points) Now you will create a bigram language model of the form p(w j h), where both w and h (the history) are word types in the vocabulary. Fixing h, p(w j h) is a multinomial distribution over word types w = 0; : : : ; v 1, and is estimated as follows:

p(w j h) =	c(h; w) + 1		;
	(Puv=01 c(h; u)) + jV j

where c(h; w) is the count of the bigram (adjacent word pair) h; w in the corpus. These counts are obtained by letting the history start at the rst word position in the corpus, then gradually moving the history one position later, until nally the (history, word) pair \use up” the corpus. For bigrams, that means history stops at the 2nd to last word position in the corpus. For example, if the corpus is \cake cake cake you want cake cake” then c(cake; you) = 1, c(cake; cake) = 3, c(cake; want) = 0. Note it is perfectly ne to estimate p(w = i j h = i) for the same word type i. It is also perfectly ne if either w or h or both are OOV.

The above discussion is for a xed h, where p(w j h) is a multinomial distribution. You will need to do so for all possible h = 0; : : : ; v 1, so that you will end up with v multinomial distributions. This is where the sparse storage becomes important.

When FLAG=300, number1 speci es the history word type index h, and number2 speci es the word

type index w. You should print out three numbers on three lines: c(h; w),	P	v 1 c(h; u), and p(w	j	h).
For example,		u=0

$java Chatbot 300 414 2297

1054

1082

0.1824628

CS 540

$java Chatbot 300 0 0

406

7467

0.0334511

$java Chatbot 300 0 1

0

7467

0.0000822

$java Chatbot 300 2110 4240

115

917

0.0206516

$java Chatbot 300 4247 0

41

1435

0.0068460

(Part d, 10 points) Now you will use the same function in Part b to sample from a bigram given h. That is, instead of using the unigram probability p(w), we x some h and you will generate a random word type from p(w j h). The method is the same, you just need to do more bookkeeping and record the segments separately for each history h. Speci cally, for history h the segments are:

0			[lh0 = 0; rh0 = p(w = 0 j h)]
	lhi =	i 1	p(w = j j h); rhi =	i	p(w = j j h)	3	; i = 1; : : : ; v 1:
@		Xj		X		5
		=0		j=0

Again, you should use sparse storage.

When FLAG=400, we provide number1 and number2 (we guarantee that number2 number1), num-ber3 is the word type for history h, and you should let r = number1=number2 to pick the corresponding word type w from p(w j h). Your code should output three numbers on three lines: the word type index i that this r selects, l_hi the left end of w_i’s interval conditioned on h, and r_hi the right end of w_i’s interval conditioned on h.

$java Chatbot 400 0 100 414

0

0.0000000

0.0003459

$java Chatbot 400 1 100 414

54

CS 540

0.0096852

0.0100311

$java Chatbot 400 98 100 414

4584

0.9799377

0.9801107

$java Chatbot 400 81 100 4697

3807

0.8099894

0.8102019

$java Chatbot 400 15 100 4442

710

0.1499684

0.1501793

(Part e, 10 points) Finally you create a trigram language model of the form p(w j h₁; h₂), where now the history is the pair of word types h₁; h₂ in that order. Fixing h₁; h₂, p(w j h₁; h₂) is a multinomial distribution over word types w = 0; : : : ; v 1, and is estimated as follows:

c(h₁; h₂; w) + 1

^{p(w j h1; h2) =} ₍Pv_u=01 _{c(h1; h2; u)) + jV j}^;

where c(h₁; h₂; w) is the count of the trigram (adjacent word triple) h₁; h₂; w in the corpus. For the cake corpus c(cake; cake; you) = 1, c(cake; cake; cake) = 1, c(cake; cake; want) = 0, c(cake; you; want) = 1 and for u 6= want we have c(cake; you; u) = 0, c(want; cake; cake) = 1 and for u 6= cake we have c(want; cake; u) = 0.

When FLAG=500, number1 speci es the history word type index h₁, number2 is h₂, and number3 is

w. You should print out three numbers on three lines: c(h

; h

; w),

v 1 c(h

; h

; u), and p(w

j

h

; h

).

For example,

1

2

Pu=0

1

2

1

2

$java Chatbot 500 23 12 123

0

0

0.0002128

$java Chatbot 500 5 660 3425

10

402

0.0021560

CS 540

1

3

0.0004253

$java Chatbot 500 414 2297 2364

99

1054

0.0173792

$java Chatbot 500 0 0 0

35

406

0.0070505

(Part f, 10 points) Now you will sample from the trigram model p(w j h₁; h₂). When FLAG=600, we provide number1 and number2 (we guarantee that number2 number1), number3 is h₁ and number4 is h₂, and you should let r = number1=number2 to pick the corresponding word type w from p(w j h₁; h₂). When this conditional probability is de ned, your code should output three numbers on three lines: the word type index i that this r selects, l_h1;h2;i the left end of w_i’s interval conditioned on h₁; h₂, and r_h1;h2;i the right end of w_i’s interval conditioned on the history. Otherwise, your code should output a single line with text unde ned.

$java Chatbot 600 2 5 660 3425

1881

0.3999151

0.4001274

$java Chatbot 600 2 5 3001 104

1880

0.3998304

0.4000424

java Chatbot 600 50 100 496 4517

2340

0.4997911

0.5000000

$java Chatbot 600 33 100 2591 2473

1530

0.3298473

0.3300565

$java Chatbot 600 0 100 2297 414

0

0.0000000

CS 540

0.0002128

$java Chatbot 600 0 100 496 4517

0

0.0000000

0.0002089

(Part g, 10 points) Now the fun begins! You will generate random sentences using your n-gram language models. But for building a chatbot, we will specify a sentence pre x s₁; s₂; : : : ; s_t which are t initial words (represented by word type indices) in the sentence. Your code will complete this sentence as follows:

1. set seed for randomizer

2. Repeat:

1. 1. h₁ = s_{t 1}; h₂ = s_t

   2. generate a random word s_t+1 from p~(w j h₁; h₂)

1. 3. t = t + 1 // shifts the trigram history by one position in the next iteration.

3. Until the generated word is a period, or a question mark, or an exclamation mark.

Note in step 1(b) a complication arises from the sentence pre x, and we introduced a placeholder p~:

{ The sentence pre x is empty. In this case, simply let p~(w j h₁; h₂) be the unigram model p(w) which does not require any history.

{ The sentence pre x has only one word s₁. In this case, let p~(w j h₁; h₂) = p(w j h = s₁) the bigram model.

{ The sentence pre x h₁ = s_{t 1}; h₂ = s_t as history is unde ned for a trigram model. If so, let p~(w j h₁; h₂) = p(w j h₂) the bigram model.

{ Otherwise, let p~(w j h₁; h₂) = p(w j h₁; h₂) the trigram model.

When FLAG=700, number1=seed, which is the seed of the random number generator; number2=t (which only needs to be 0, 1, or 2), and the next t numbers on the commandline specify the sentence pre x s₁; s₂; : : : ; s_t. We will guarantee that s_i is not period, or a question mark, or an exclamation mark.

If seed = 1, you actually do not set the seed (this allows you to generate di erent random sentences).

Otherwise you should set the seed to seed. To set the seed in Java, use the following code:

Random rng = new Random();

if (seed != -1) rng.setSeed(seed);

In step 1(b) each time you should generate a new random number r 2 [0; 1] in order to generate the random word. This should be done with

CS 540
rng.nextDouble();
You should try your code multiple times with the same sentence pre x: when seed =	1 your code

should complete the sentence in di erent ways; otherwise it should be the same completion.

Your code will output the completed sentence (starting at s_t+1), one word index per line.

Because of Laplace smoothing, the generated sentences can be too long. This is because Laplace smoothing assigns a default prior probability to all the terms even if they never appear. Hence, only partial sample outputs are shown below. For the complete outputs, please refer to the provided sample test case les.

$java Chatbot 700 0 0

3693

1118

2995

2587

2808

1566

1810

4628

4132

4423

…

$java Chatbot 700 1 1 523

3433

1927

976

1563

4548

28

4529

4417

4451

4404

…

$java Chatbot 700 31 2 2110 311

3434

1846

3693

3003

3508

4553

2315

985

CS 540

2533

4521

…

(Part h, no points) For this part you do not need to develop your code any further, but you will test out the Chatbot that you have developed by actually \talking” to it.

Please download ChatbotDriver.java and place this le together with your Chatbot.java in the same directory. This driver class basically takes the user input, apply some rules to generate a pre x based on the input (or just use the input itself as the pre x), and call \java Chatbot 700 -1 prefix” to generate a response and visualize it as actual words (\OOV” will be displayed for OOV indices). You can compile both les and try chatting with your Chatbot. Also make sure you have the txt les in the directory as well.

Note: because of randomness, your results will di er.

$javac Chatbot.java ChatbotDriver.java

$java ChatbotDriver

You: What’s your opinion on self-driving cars?

Chatbot: self-driving cars similar apply desired rarely describing unique behavior proposal contributing inventions failing tolerance self-driven battle conjunction center aspect space difficulties person population user promising 12 billion … You: healthcare system

Chatbot: healthcare system suggests unfair takes underlying validation corporation

investment capital falling or database professionals protocol relationships broadly

animal selection .

You: tell me a joke

Chatbot: attempts analyzed conversation amount complete accent data gone integrate

require distance parts switch else doubts enacted ct at believes happening apparent

arrive forever subjects racial x-ray screens norm 2 alter eliminating ai exercise

surgical perception consent autonomy …

You: say anything

Chatbot: simplified household refers regulatory processing differently executive knows carpooling face choosing unlikely sold published peer state-of-the-art cultures healthcare start tested hired devastating boston transition questionable staple fails collisions portability compromised true prejudices kate crisis highways … You: what is your idea of an ideal world?

Chatbot: my idea of an ideal world choosing individualized home/service mentions infinite knowledge 1999 things flint year disruptions switching professional mistake uneven compatibility direction cited developing argues eliminating brains virtually vehicles businesses accountability attract promise involves can shut buttons …

Have fun and try to make it more intelligent by modifying ChatbotDriver.java! (e.g. adding more rules to the generateCommand method.)