# Hidden Markov Model in Tagging Problem

I try to understand the details regarding using Hidden Markov Model in Tagging Problem.

The best concise description that I found is the Course notes by Michal Collins.

The goal is to find a function $f(x)=arg max_{y \in Y} p(y|x)$, where $y$ is the tag set for sentence $x$.

Question 1. It's suggested to use a generative model and to estimate joint probability $p(x,y)$ from the trainig examples, however what the the reason to use generative model and increase the number of computation why not directly to estimate $p(y|x)$, I think it's possible to estimate the conditional probability straightforward from the training data.

Addendum. Do you know the reason why at all we should try to use a generative model in this case (POS tagging). As I understand if we can estimate $p(x,y)$ that exactly with the same success we can estimate $p(y|x)$ and directly find the answer to the question, what is the best tagging - $\hat{y}$ without weak assumption of generative model. There is the reason to use generative model, and I don't see it yet. Can you explain me what the reason?

Question 2. Assume we decided to use a generative model and made estimation to $p(x,y)$ why we decide to decompose it as follows $p(x,y)=p(y)p(x|y)$ and not $p(x,y)=p(x)p(y|x)$?

Addendum. I do understand that it's very logical to use the decomposition $p(y)p(x|y)$ just because by doing it we approach $p(y|x)$, so mathematically it seems very reasonable, however according to the task I don't see what the problem to decompose it like $p(x,y)=p(x)p(y|x)$, there should be sore reason why we can not decompose it so and I don't understand why.

• Could you edit your question to use complete sentences, and avoid run-on sentences? I suggest you proofread the question, then click "edit" to revise it accordingly. – D.W. Nov 6 '13 at 21:33

1. You can directly estimate $p(y|x)$, this is what you're doing when using a Conditional Random Fields (CRF) for tagging. As someone else said, this is called a discriminative model. A major advantage of discriminative models for tagging is they allow one to easily incorporate arbitrary features (starts with a capital letter, contains a number, contains punctuation, etc). This isn't easy with generative models since doing so would usually violate the the independence assumptions required to make $p(x|y)$ tractable. Ultimately which one is better will depend on your particular problem.

2. If you're doing classification, and you can build a good model of $p(y|x)$, then what would you be messing with the joint for? When using a generative model for classification the idea is to "sneak up" on the distribution of interest, namely $p(y|x)$, because it is hard to model explicitly. One way to do this is by observing that $p(y|x) \varpropto p(y,x) = p(y)p(x|y)$.

• thank you for your answer, as with MEMM model where it's possible to add arbitrary features, I wounder if there is possible at all to add some features except (previous tag for current tag, and current tag for word), the problem is in HMM I cannot think about features at all, for me it's just HMM assumption and Bayes. Can you show how to incorporate features to it? – user16168 Feb 1 '14 at 17:16
• Ironically I recently read a really neat paper covering this exact subject, Painless Unsupervised Learning with Features. Although they focus on unsupervised learning, the techniques they use are would be applicable to supervised generative models as well. – alto Feb 1 '14 at 17:45

You can try to directly fit the function $\Pr[y | x]$. This is called a discriminative classification. This is typically solved via some regression mechanism such as ordinary least squares, or lasso, or ridge depending on certain assumptions of the model.
The reason we want to factor $\Pr[x, y] = \Pr[x | y] \Pr[y]$ is because we are interested in the class conditional density $\Pr[x | y]$. That is, what is the probability of observing data $x$ given the label $y$?