HMM Tagging problem

HMM Tagging Problem

Complexity issues have risen their ugly heads again and with the IPO date on your new comp ling startup fast approaching, you have discovered that if your hot new system is going to parse sentences as long as 4 words, you had better limit yourself to a 3-word vocabulary.

Consider the following HMM tagger for tagging texts constructed with a 3 word vocabulary.

station
ground
control

and a tagset of 2 tags:

V [Verb]
N [Noun]

Here is a partial state table for the HMM:

States	Start V = Verb N = Noun
State	Observation	Transition	Transition Probability
Start	ground	Start => N	Pr(N \| Start) *	Pr(ground \| N)
			.5 *	.4
			.20
		Start => V	Pr(V \| Start) *	Pr(ground \| V)
			.5 *	.3
			.15
	control	Start => N	to be filled in
	control	Start => V	to be filled in
	station	Start => N	to be filled in
	station	Start => V	to be filled in
V	ground	V => N	Pr(N \| V) *	Pr(ground \| N)
			.9 *	.4
			.36
		V => V	Pr(V \| V) *	Pr(ground \| V)
			.1 *	.3
			.03
	control	V => N	to be filled in
	control	V => V	to be filled in
	station	V => N	to be filled in
	station	V => V	to be filled in
N	ground	N => N	Pr(N \| N) *	Pr(ground \| N)
			.5 *	.4
			.02
		N => V	Pr(V \| N) *	Pr(ground \| V)
			.5 *	.3
			.15
	control	V => N	to be filled in
	control	V => V	to be filled in
	station	V => N	to be filled in
	station	V => V	to be filled in

The table is incomplete. The states and are all present, and all the transitions with non-zero probabilities are present, but the transition probabilities for control and station have been left out.

Our tagger assumes all input will start with a start symbol [s]. It also assumes the Start state is incompatible with any input except [s].

You can use this tagger to assign the most likely tag sequence to any sequence of words taken from our small vocabulary. Consider the following input to our tagger:

ground ground There are 4 different state sequences that will accept this input:

Start V V
Start V N
Start N N
Start N V

These correspond to 4 different assignments of part-of-speech tags to the two input words (ground ground) Here is each word aligned above its transition and transition probability.

	ground		ground
start		V		N
	(1.0 * .5)		(.3 * .9)		(.4 * .5)

So this corresponds to the path in which the first occurrence of ground is labeled a verb, and the second a noun. Let's review where these transition probabilities come from.

The probability model being used is the following.

_1,n

_1,n+1

_i=1

_{i + 1}

That is, the joint probability of a word sequence n words long and a tag sequence n + 1 tags long is equal to the product of the probabilities of each word given its tag times the probability of each following tag given the word tag. For each w_i,

P(w_i | t _i) * P(t_{i + 1} | t _i)

For our example, according to this probability model we calculate the joint probability to be:

(.3 * .5) * (.4 * .9) = .054
Pr(ground|V) * Pr(V | Start) * Pr(ground|N) * Pr(N|V)

This is the product of the transition probabilities for this path through the HMM. To find the most likely assignment of tags we need to find the most probable path through the HMM. This is what the Viterbi algorithm is for.

Problem 3 Proper

Part A

The above HMM was given with only a partial probability model. Here is the entire probability model:

w	Pr(w \| N )	Pr(w \| V )
ground	.4	.3
control	.3	.3
station	.3	.4

Pr(X \| N)	Pr(X \| V)	Pr(X \| Start)
Pr(V \| N) .5	Pr(V \| V) .1	Pr(V \| Start) .5
Pr(N \| N) .5	Pr(N \| V) .9	Pr(N \| Start) .5

The first part of the problem is to use this probability model to complete the transition table for the above HMM tagger by filling in the transition probabilities for control and station.

Part B

The second part of the tagging problem is to tag the following input:

ground control station This can be done by computing the products of the transition probabilities (called the path probabilities) for all 16 paths through the HMM and choosing the most probable path.

But the assigned problem is to choose the most probable path by using the Viterbi algorithm.

To help you get started, here is the partial Viterbi matrix for our HMM and the given input:

V		.5
N		.5
Start	1.0
		ground	control	station
	t=0	t=1	t=2	t=3

Note that the Viterbi values for t=0 and t=1 have already been filled in. Continue the matrix and fill in the values for t=2, and t=3. Show your calculations. Use the Viterbi homework assignment and Viterbi lecture as your model of what to show.

Part C

Using the results of your Viterbi calculation, give the most probable state sequence through the HMM.

Pr(X \| N)	Pr(X \| V)	Pr(X \| Start)
Pr(V \| N) .5	Pr(V \| V) .1	Pr(V \| Start) .5
Pr(N \| N) .5	Pr(N \| V) .9	Pr(N \| Start) .5