13
$\begingroup$

I have used Hidden Markov Model algorithm for automated speech recognition in a signal processing class. Now going through Machine learning literature i see that algorithms are classified as "Classification" , "Clustering" or "Regression". Which bucket does HMM fall into? I did not come across hidden markov models listed in the literature.

$\endgroup$
0

2 Answers 2

14
$\begingroup$

I would be tempted to reply "none", or "both classification and clustering".

Why "none"? Because HMMs are not in the same bag as support vector machines or k-means.

Support vector machines or k-means are specifically designed to solve a problem (classification in the first case, clustering in the second), and are indeed just an optimization procedure to maximize an "expected goodness of classification" or "goodness of clustering" criterion. The beauty lies in the choice of the criterion and optimization procedure. HMM are not an algorithm per se. They are a specific kind of probability distribution over sequences of vectors - for which we know good parameter estimation and marginal distribution computation algorithms. But asking whether they are in the "clustering" or "classification" family is as ridiculous as asking whether the Gaussian distribution is supervised or unsupervised learning.

Why "both classification and clustering"? Because of the following: Being probability distributions, HMM can be used for classification in a bayesian framework; and being model with hidden states, some latent clustering of the training data can be recovered from their parameters. More precisely:

HMM can be used for classification. This is a straightforward application of the bayesian classification framework, with the HMM being used as the probabilistic model describing your data. For example, you have a large database of utterances of digits ("one", "two", etc) and want to build a system capable of classifying an unknown utterance. For each class in your training data ("one", "two", you estimate the parameters of a HMM model describing the training sequences in this class - and you end up with 10 models. Then, to perform recognition, you compute the 10 likelihood scores (which indicate how likely the sequence you want to recognize has been generated by the model), and the model with the highest score gives you the digit. In the Rabiner tutorial on HMMs, the training stage is "Problem 3", the classification stage is "Problem 2".

HMM can be used in an unsupervised fashion too, to achieve something akin to clustering. Given a sequence, you can train a $k$-state HMM on it, and at the end of the training process, run the Viterbi algorithm on your sequence to get the most likely state associated with each input vector (or just pull this from the $\gamma$ during the training process). This gives you a clustering of your input sequence into $k$ classes, but unlike what you would have obtained by running your data through k-means, your clustering is homogeneous on the time axis. For example, you can extract the color histograms of each frame of a video sequence, run this process on this sequence, and you'll end up with a break-down of the video into homogeneous temporal segments corresponding to scenes (the unpractical bit is that you have to set up the number of scenes $k$ in advance). This technique is commonly used in automatic, unsupervised, structure analysis of video or music.

$\endgroup$
1
$\begingroup$

First, let's look at the three options:

  • Classification : Identifying which class of a set of pre-defined classes the data belongs to.
  • Clustering : Learning the set of classes the data belongs to.
  • Regression : Finding a relationship between on variable and one or more others.

The description of the HMM on Wikipedia has the following table:

enter image description here

so the number of states (classes) is fixed.

That means that the algorithm does not try to figure out the number of classes (states) are --- so it's not open-ended clustering (where the number of states is unknown).

However, as @nikie points out, the HMM will do clustering.

There is not really an independent variable (as exists in the regression context) --- so it's not regression.

So my answer is that the HMM is a classification and a clustering algorithm, I do not believe it is a regression.

$\endgroup$
2
  • 2
    $\begingroup$ How do you get from "the number of classes if fixed" to "so the algorithm does not try to figure out that the classes are"? The number of classes for k-means clustering is fixed, too, but it's clearly a clustering algorithm. $\endgroup$ Sep 12, 2012 at 7:10
  • $\begingroup$ I suppose I'm used to the open-ended clustering rather than fixed. Will update answer. Thanks! $\endgroup$
    – Peter K.
    Sep 12, 2012 at 17:20

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.