HHMM and HMM

An HMM is a stochastic finite automaton, where each state generates an observation. The observation can be a discrete symbol or a feature vector. The parameters of the model are the initial state distribution, the transition model, and the observation model. An HMM can be represented by a state transition diagram or by a Bayesian network.

Any HHMM can be converted to HMM. The resulting state-space may be smaller, because it does not contain abstract states. This occurs if there are not many shared sub-structures. The state-space may be larger if there are shared sub-structures because they must be duplicated.  Whether the state-space will be lager or smaller, depends on the ratio between the number of hidden states \(n_h^S\) in  HHMM and the number of hidden states \(n^S\) in HMM.

In general, a dynamic Bayesian network (DBN) can be converted to an HMM if all the hidden nodes are discrete. In this case, using the HMM inference engine can be faster than the using the junction tree inference engine for small models because the constant factors of the algorithm are lower, but can be exponentially slower for models with many variables (e.g.,  > 6 binary hidden nodes).

HMM parameter learning: EM algorithm
n sequences with length m
\begin{align}
t^t(s'|s) = \frac{\sum_{i = 1}^n\sum_{j=1}^m p(S_j = s, S_{j+1} = s'|x_{i, 1}\ldots x_{i, m};\underline{\theta})}{\sum_{i = 1}^n\sum_{j=1}^m \sum_{s'} p(S_j = s, S_{j+1} = s'|x_{i, 1}\ldots x_{i, m};\underline{\theta})}
\end{align}
$$\sum_{s'} t(s'|s) = 1$$

Trianglulate a graph

Triangulation ensures a graph G is triangulated (chordal), i.e., every cycle of length > 3 has a chord. During the process, we can also find maximal cliques in the triangulated graph.

Pseudo code:

// G is moralized.
triangulate(G, order):
1. eliminated = {}
2. cliques = {}
3. for i = 1 : n
       u = order(i)
       nodes = neighbors of u which are not eliminated yet \(\cup\) u
       make every node in nodes all connected to each other
       add u to eliminated
       check whether nodes is a subset of any clique already found, if not, add nodes to cliques.
     
     

Machine learning

Perceptron

Repeat until convergence:

For t = 1 ... n

1. \(y'\) = sign(\(\underline{x}_t\cdot\underline{\theta}\))
2. If \(y'\ne y_t\) Then \(\underline{\theta} = \underline{\theta} + y_t\underline{x}_t\), Else leave \(\underline{\theta}\) unchanged.

Kernel form of the perceptron

• Definition: for any \(\underline{x}\), define \(g(x) = \sum_{j=1}^n\alpha_jy_jK(\underline{x}_j,\underline{x})\) where \(K(\underline{x}_j,\underline{x}) = \phi(\underline{x}_j)\cdot\phi(\underline{x})\)
• Repeat until convergence:
• For t = 1 ... n
1. y' = sign(g(\(\underline{x}_t\))
2. If \(y'\ne y_t\) Then \(\alpha_t = \alpha_t + 1\)

Algorithms for inference

Definitions

Chordal graph: a graph is chordal if any cycle of the graph of size >= 4 has a chord.

Formulas

Parameter estimation for HMM with Gaussian distribution for emission probabilities:

$$\underline{\mu}_s^t = \frac{\sum_{i=1}^n\sum_{j=1}^mp(S_j = s|\underline{x}_{i,1}\dots\underline{x}_{i,m};\theta)\underline{x}_{i,j}}{\sum_{i=1}^n\sum_{j=1}^mp(S_j = s|\underline{x}_{i,1}\dots\underline{x}_{i,m};\theta)}$$

General form of EM algorithm

The basic idea is that we want to maximize the likelihood of the "complete" data. Because we don't know the "complete" data, we need to take the expectation of the "complete" data with respect to the probability distribution of the hidden variables.

Let \(\mathbf{Z}\) denote all the hidden variables for all the examples, and let \(\boldsymbol{\theta}\) be all the parameters for the probability model. \begin{aligned}\boldsymbol{\theta}^{(i+1)} &= \underset{\boldsymbol{\theta}}{\arg\max}\sum_{\boldsymbol{z}}P(\boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{x}, \boldsymbol{\theta}^{(i)})L(\boldsymbol{x}, \boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{\theta}) \\ &=\underset{\boldsymbol{\theta}}{\arg\max}E_{P(\boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{x}, \boldsymbol{\theta}^{(i)})}L(\boldsymbol{x}, \boldsymbol{Z}= \boldsymbol{z}|\boldsymbol{\theta}) \end{aligned}
The E-step is the computation of the summation, which is the expectation of the log likelihood of the "completed" data with respect to the distribution \(P(\boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{x}, \boldsymbol{\theta}^{(i)})\).

Bayesian network

The posterior probability is the probability of the parameters given the evidence : \(P(\theta|X)\).
Likelihood is the probability of the evidence given the parameters: \(P(X|\theta)\).

A maximum a posteriori probability (MAP) estimate is a mode of the posterior distribution. It can be used to obtain a point estimate of an unobserved quantity on the basis of empirical data. It is closely related to maximum likelihood (ML), but employs an augmented optimization objective which incorporates a prior distribution over the quantity one wants to estimate. MAP estimation can therefore be seen as a regularization of ML estimation.

Maximum likelihood estimate of \(\theta\) is $$\hat\theta_{ML}(x) = \underset{\theta}{\arg\max}f(x|\theta)$$
If \(g(\theta)\) is a prior distribution over \(\theta\), $$\hat{\theta}_{MAP} = \underset{\theta}{\arg\max}f(x|\theta)g(\theta)$$

Conjugate prior

In Bayesian probability theory, if the posterior distributions \(p(\theta|x)\) are in the same family as the prior probability distribution \(p(\theta)\), the prior and posterior are then called conjugate distribution, and the prior is called a conjugate prior for the likelihood. For example, the Gaussian family is conjugate to itself with respect to a Gaussian likelihood function: if the likelihood function is Gaussian, choosing a Gaussian prior over the mean will ensure that the posterior distribution is also Gaussian.

The posterior distribution of a parameter \(\theta\) given some data x is $$p(\theta|x) = \frac{p(x|\theta)p(\theta)}{\int{p(x|\theta)p(\theta)d\theta}}$$ A conjugate prior is an algebraic convenience, giving a closed-form expression for the posterior.

Dirichlet distribution is the conjugate prior of the categorical distribution and multinomial distribution. The Dirichlet distribution with parameters \(\alpha_1, \dots, \alpha_K > 0\) has a probability density function given by $$f(x_1, \dots, x_{K-1};\alpha_1, \dots, \alpha_K) \propto \prod_{i = 1}^Kx_i^{\alpha_i-1}$$ for \(x_i > 0\) and \(\sum x_i = 1\). This makes it suitable to be a prior distribution for a model parameter \(\boldsymbol{\theta}\) for a multinomial distribution where \(\boldsymbol{\theta}_i = x_i\).

Decision Tree

Decision trees are classifiers for instances represented as feature vectors. Nodes are tests for feature values. There is one branch for each value of the feature. Leaves specify the category.

The central choice in the algorithm to build a decision tree is selecting which attribute to test at each node in the tree. We would like to select the attribute that is most useful for classifying examples. A good quantitative measure of the worth of an attribute is information gain, which measures how well a given attribute separates the training examples according to their target classification.

Information gain is related to entropy, that characterizes the (im)purity of an arbitrary collection of examples. Given a collection S, containing positive and negative examples of some target concept, the entropy of S relative to this boolean classification is

$$Entropy(S)\equiv -p_\oplus \log_2 p_\oplus-p_\ominus\log_2 p_\ominus$$

where \(p_\oplus\) is the proportion of positive examples in S and \(p_\ominus\) is the proportion of negative examples in S.

Information gain  is simply the expected reduction in entropy by partitioning the examples according to this attribute. Gain(S, A) of an attribute A, relative to a collection of examples S, is define as

$$Gain(S, A) \equiv Entropy(S) - \sum_{v\in Values(A)}\frac{|S_v|}{|S|}Entropy(S_v)$$

On generative and discriminative models

In a supervised learning problem, we want to find the function f: X -> Y, or P(Y|X). Discriminative models directly estimate P(Y|X). It is given the name because given X, we can directly discriminate (or determine) the value of the target Y. Generative models, on the other hand, estimate the joint probability P(Y, X) by finding P(X|Y) and P(Y). It is called generative because given the parameters P(X|Y) and P(Y), we can generate observable samples from the model.

Discriminative models include: logistic regression, conditional random fields, support vector machine
Generative models include: HMM, naive Bayes, Gaussian mixture models.

For solving a classification problem, a discriminative classifier is almost always preferred because discriminative models do not need to model the distribution of the observed variables, and they can generally express more complex relationships between the observed and target variables. However, Ng et al. also demonstrated in their experiments that generative methods may also converge more quickly to its (higher) asymptotic error as number of training examples increases. The generative model may also approach its asymptotic error with a number of training examples that is only logarithmic, rather than linear, in the number of parameters. This means that with smaller number of training examples, generative models may do better.