5
$\begingroup$

I was doing some NLP related stuff which involves training a hidden Markov model, and use the model to segment sentences. For every sentence, I translate the tokens into feature vectors. The features are manually picked by me, and I can only think of 20 features temporarily. All of the features are binary. So an example feature vector in my case would be like:

[0, 0, 1, 1, 0…]

When training the HMM (supervised learning with maximum likelihood estimation), I convert the binary feature vector to integer, and use the integers as the observations in HMM. My question is what if I have more dimension of features, say 100 features, then it might not be possible or efficient to map feature vectors to integers when training the HMM. What if the features are not binary. What are some common solutions/best practice to these problems?

P.S. I did some research and find that one solution is to use K-Means to find clusters of feature vectors and consider each cluster as a single observation in HMM (also known as vector quantization). But I don't think it is the best solution.

|cite|improve this question
$\endgroup$
4
$\begingroup$

A Hidden Markov Model is defined by two different probability distributions, namely

$$ \begin{align*} p(s_t \mid s_{t-1}),&\;\;\;\text{the transition probabilities, and}\\ p(x_t \mid s_t),&\;\;\;\text{the emission probabilities.} \end{align*} $$ In typical presentations of HMMs the emission probabilities are taken to be categorical as this is the natural choice if each observation in the sequence is a word.

You can easily modify the emission distribution to deal with other types of observations. For example, if your observation $x_t$ is a continuous vector then it may make sense to assume $p(x_t|s_t)$ is a multivariate normal distribution with state dependent mean vector and covariance matrix, i.e.,

$$ x_t \mid s_t \sim N(\mu_{s_t}, \Sigma_{s_t}). $$

On the other hand if $x_t$ is a binary vector you may want to make a conditional independence assumption (as you would for Naive Bayes') and assume

$$ p(x_t\mid s_t) = \prod_{i=1}^n p(x_{ti}\mid s_t) = \prod_{i=1}^n \left(\theta_{s_ti}\mathbb{I}\left\{x_{ti} = 1\right\} + (1-\theta_{s_ti})\mathbb{I}\left\{x_{ti} = 0\right\}\right). $$

These are just some common distributions you'll see people work with. You can really use anything you want, provided you can compute the values you need and learn the parameters.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Hi alto, thank you for the answer. I didn't choose word to be the observation is because the words in my problem case tend to be a very big set, and the meaning of word is not that important to me, the pattern(like if they are capitalized, if they are english word) are more important. So I used a series of features to represent each word. But I don't really understand the conditional independence assumption there. So xti means the ith column in my feature vector? Why do I have to calculate the product of p(each column | st)? I thought I can treat the feature vector as a whole $\endgroup$ – xiaoyao Aug 6 '13 at 2:46
  • 1
    $\begingroup$ @xiaoyao, yes I assumed $t$ indexed time and $i$ indexed the features in your feature vector. If your feature vector consists of $n$ binary random variables, then in general you will need $2^n-1$ parameters to represent the conditional joint distribution $p(x_t\mid s_t)$. This is exactly the same as what you're already doing when converting the binary vector into an integer, and as you noticed, will get unwieldy very quickly. One way to deal with this problem is to assume the features are conditionally independent given the state, in which case one would only need $n$ parameters. $\endgroup$ – alto Aug 6 '13 at 11:20
  • $\begingroup$ @xiaoyao , when you say you convert the vector to an integer and use that as an observation, would for instance these two vectors contribute to the same observation? [0,0,0,1,1,1] and [1,0,0,1,0,1] (just trying to understand your method of implementation of HMM using feature vector in this way) I was working on something and I thought of creating a model of each feature since some of them do happen to be sequentially correlated. But that would become tedious and this seems interesting. @alto if you could answer this too I would appreciate that $\endgroup$ – Aalok Sep 3 '16 at 17:10
1
$\begingroup$

If you think the observations interact with the observations, there is a very elegant HMM with Features model proposed by Berkeley that might be useful for you.

ee Paper and Slides

Me and my collaborator recently implemented this algorithm. Although currently it is mostly written for educational applications, it is general enough to get you started.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

You should check out the TrueSkill model proposed by Ralf Herbrich and Thore Graepel at Microsoft Research. (Some related papers are listed at the end of that page, where some implementation details are given.) Simply put, TrueSkill does very large scale learning with graphical models. It is able to handle very large data sets with millions of features, both nominal and numerical features.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

See this answer: How to handle high dimensional feature vector in probability graph model?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This is the same as in your other answer on this same question, right? Is there a reason you answered again rather than editing your old one with the new link? $\endgroup$ – Dougal Apr 30 '15 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.