Final Test

Question 1

Fundamental HMM Assumptions (3)

Answer 1

• Observation independence assumption
• First-order Markov assumption
• Transitions are time-independent

Question 2

Observation independence assumption

Answer 2

Likelihood of the t’th feature vector depends only on the current state, and is therefore otherwise unaffected by previous states and feature vectors.

Question 3

First-order Markov Assumption

Answer 3

Apart from the immediately preceding state, no other previously observed states or features affect the probability of occurrence of the next state.

Question 4

Time-independent transition

Answer 4

We assume the transition probability between two states to be constant irrespective of the time when the transition actually takes place.

Question 5

3 Steps of Viterbi Re-estimation

Answer 5

• Initialisation
• EM Re-estimation
• Termination

Question 6

Viterbi Re-estimation: Initialization: 2 Steps

Answer 6

a) For every training observation sequence, assign in a sensible manner, a corresponding state sequence and extend it by adding the initial and termination state.
b) From this initial state sequence, generate an initial model.

Question 7

Viterbi Re-estimation: EM Re-estimation: 2 Steps

Answer 7

Expectation Step: For the current model estimate, apply the viterbi algorithm on every training sequence to calculate its log-likelihood given S*, the expected state sequence for this observation sequence. Accumulate the “score” to be used later to test for convergence.

Maximization step: Use all the S*’s obtained in the E-step to update the parameters of the HMM.

Question 8

Viterbi Re-estimation: Termination

Answer 8

Compare the total score obtained in the E-step to that from the previous E-step. If it within an acceptable tolerance, terminate, otherwise continue with re-estimation, (step 2).

Question 9

Goal of dimensionality reduction

Answer 9

To project the data onto a lower dimensional space, while retaining some of the essential characteristics of the data.

Question 10

PCA approach to dimensionality reduction

Answer 10

PCA finds lower dimensional subspaces that describe the essential properties of the data, by finding the directions of maximum variation in the data.

Question 11

LDA approach to dimensionality reduction

Answer 11

LDA reduces the dimension of the data values in such a way that maximum class separation is obtained in the lower dimensional space.

Question 12

Dynamic programming algorithm

Answer 12

An algorithm that uses a table to store intermediate values as it builds up the probability of the observation sequence.

Question 13

What does the forward algorithm do?

Answer 13

Computes the observation probability by summing over the probabilities of all possible hidden state paths that could generate the observation sequence, but it does so efficiently by implicitly folding each of these paths into a single forward trellis.

Question 14

HMMs: Decoding task

Answer 14

Given as input an HMM, and a sequence of observations, find the most probable sequence of states.

Question 15

HMMs: Learning task

Answer 15

Given an observation sequence O and the set of possible states in the HMM, learn the HMM parameters.

Question 16

Viterbi algorithm use

Answer 16

To find the optimal sequence of hidden states.
Given an observation sequence and an HMM, the algorithm returns the state path through the HMM that assigns maximum likelihood to the observation sequence.

Question 17

Forward-backward algorithm use

Answer 17

To train the parameters of an HMM, being the transition probability matrix and the observation likelihood matrix.

Question 18

Sequence Model (or Classifier)

Answer 18

A model whose job is to assign a label or class to each unit in a sequence,

thus mapping a sequence of observations to a sequence of labels.

Question 19

HMM

Answer 19

A probabilistic sequence model: given a sequence of units, they compute a probability distribution over possible sequences of labels and choose the best label sequence.

Question 20

Markov chain

Answer 20

A special case of a weighted automaton in which weights are probabilities and in which the input sequence uniquely determines which states the automaton will go through.

Question 21

3 fundamental problems that characterize hidden Markov models

Answer 21

• Likelihood: What’s the likelihood of an observation sequence given an HMM.
• Decoding: Given an observation sequence and an HMM, what’s the best hidden state sequence.
• Learning: Given an observation sequence and the set of states in the HMM, learn the HMM parameters.

Question 22

Algorithms solving the 3 problems of HMMs

Answer 22

• Likelihood computation: The Forward Algorithm
• Decoding: The Viterbi Algorithm
• HMM Training: The Forward-Backward algorithm

Question 23

Backward probability

Answer 23

The probability of seeing the observations from time t+1 to end, given that we are in state i at time t.

Question 24

Contrast discriminative and generative models (TEXTBOOK)

Answer 24

In the case of generative models, a model is trained for each class, totally ignoring the properties of the properties of the other classes.
Discriminative models use all the training data simultaneously to generate the model. It can be used to good effect to try and maximise the differences between classes.

Question 25

Generative Approach (TEXTBOOK)

Answer 25

A model is developed for every class from the observations known to belong to that class.

Once this model is known, it is in principle possible to generate observations for each class.

Question 26

Discriminative Approach (TEXTBOOK)

Answer 26

Directly estimates the posterior from the data. This has the advantage that the data is used to best effect in order to discriminate between the classes.

Thus training data is used more effectively in distinguishing between classes.