Calculating Emission Probability values for Hidden Markov Model (HMM)

Question

I'm new to HMM and still learning. I'm currently using HMM to tag part-of-speech. To implement the viterbi algorithm I need transition probabilities ($ a_{i,j} \newcommand{\Count}{\text{Count}}$) and emission probabilities ($ b_i(o) $).

I'm generating values for these probabilities using supervised learning method where I give a sentence and its tagging. I calculate emission probabilities as:

$$ b_i(o) = \frac{\Count(i \to o)}{\Count(i)} $$

where $\Count(i)$ is the number of times tag $i$ occurs in the training set and $\Count(i \to o)$ is the number of times where the observed word $o$ maps to the tag $i$.

But when using this trained $b_i(o)$ for tagging, there might be observed variables in the given sentence that never appeared when finding the value for $b_i$. In such a case how do you estimate a value for $b_i$ for that instance?

Answer 1

For these kind of questions, it is possible to use Laplace Smoothing. In general Laplace Smoothing can be written as: $$ \text{If } y \in \begin{Bmatrix} 1,2,...,k\end{Bmatrix} \text{then,}\\ P(y=j)=\frac{\sum_{i=1}^{m} L\begin{Bmatrix} y^{i}=j \end{Bmatrix} + 1}{m+k} $$

Here $L$ is the likelihood.

So in this case the emission probability values ( $b_i(o)$ ) can be re-written as: $$ b_i(o) = \frac{\Count(i \to o) + 1}{\Count(i) + n} $$

where $n$ is the number of tags available after the system is trained.

Answer 2

This is relatively old question, but I'll add my 5 cents for the people who (like myself) came across it searching for something related.

An alternative approach for dealing with zero emission probabilities is to "close the vocabulary". An idea is to define "rare" words in training set - those that appear less than predefined number of times and substitute them with "word classes" before the model is trained. When applying a model to a new sequence of words, all words that were not seen in a training set are converted to "word classes" as well (effectively considering them as "rare"). It guarantees that for a model there will be no unseen words.

The rules for producing "word classes" from words have to be selected manually (which is a downside). For instance, in a (probably) first article when this approach was utilized (Bikel, D.M., Schwartz, R. & Weischedel, R.M. Machine Learning (1999) 34: 211.; https://link.springer.com/article/10.1023/A:1007558221122; http://curtis.ml.cmu.edu/w/courses/index.php/Bikel_et_al_MLJ_1999) an examples of classes are:

Word Feature           | Example Text           | Intuition
-----------------------|------------------------|-----------------------------------------
twoDigitNum            | 90                     | Two-digit year
fourDigitNum           | 1990                   | Four digit year
containsDigitAndAlpha  | A8956-67               | Product code
containsDigitAndDash   | 09-96                  | Date
containsDigitAndSlash  | 11/9/89                | Date
containsDigitAndComma  | 23,000.00              | Monetary amount
containsDigitAndPeriod | 1.00 Monetary          | amount, percentage
otherNum               | 456789                 | Other number
allCaps                | BBN                    | Organization
capPeriod              | M.                     | Person name initial
firstWord              | first word of sentence | No useful capitalization information
initCap                | Sally                  | Capitalized word
lowerCase              | can                    | Uncapitalized word
other                  | ,                      | Punctuation marks, all other words

An example of pre-processed tagged sentence from a training set (from lectures of Michael Collins):

"Profits/NA soared/NA at/NA Boeing/SC Co./CC ,/NA easily/NA topping/NA forecasts/NA on/NA Wall/SL Street/CL ,/NA as/NA their/NA CEO/NA Alan/SP Mulally/CP announced/NA first/NA quarter/NA results/NA ./NA"

is transformed (with some hypothetical set of tags and "rare words") into (substituted words as shown in bold)

"firstword/NA soared/NA at/NA initCap/SC Co./CC ,/NA easily/NA lowercase/NA forecasts/NA on/NA initCap/SL Street/CL ,/NA as/NA their/NA CEO/NA Alan/SP initCap/CP announced/NA first/NA quarter/NA results/NA ./NA"

It is still possible that in training set not all pairs of "tag -> word/word class" are seen, which makes it impossible for a certain word or word class being tagged with those tags. But that doesn't prevent of those words to be tagged with other tags - unlike when there is a word that was not seen in a training set.