4 votes
Accepted

Hidden Markov Model initial probability reestimate: Why $\pi^*_i = \gamma_i(1)$ instead of $\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$

It is defined to be a probability. A probability is by definition already normalized. In particular, we are guaranteed that $$\sum_{j=1}^N \gamma_j(1) = 1,$$ as there are only $N$ possibilities ...
D.W.'s user avatar
  • 158k
3 votes
Accepted

What is difference between Hidden Markov Model and Non-deterministic Finite-State Machine?

Deterministic Finite State Machines have at most one trace for a given input. Nondeterministic Finite State Machines may have many traces for a given input. A Hidden Markov Model in some sense fits &...
C8H10N4O2's user avatar
  • 746
3 votes
Accepted

Shortest path given correct order of colours?

Use a product construction, to construct a new graph whose vertices are given $(x,y,z,k)$, where $k$ counts the index into the sequence of colors (i.e., we are currently at $k$th vertex in that ...
D.W.'s user avatar
  • 158k
2 votes

Examples of difference between Hidden Markov Model and Bayesian Network?

A Hidden Markov Model can be expressed as an instance of a Bayesian network of a particular form. Consequently, a HMM can be viewed as an special case or kind of Bayesian network. Bayesian networks ...
D.W.'s user avatar
  • 158k
2 votes
Accepted

counteracting numerical instability in HMM training

Avoiding zero probabilities You probably want to be using additive smoothing when estimating probabilities from count data. With a dictionary of 80,000 words, most of those words will be very rare: ...
D.W.'s user avatar
  • 158k
2 votes
Accepted

Compare Hidden Markov Model's sample with ground truth data

Compute the likelihood of the observed data, for each model. Then higher the likelihood, the better the fit. The likelihood is just the probability that the model assigns to the observed data, which ...
D.W.'s user avatar
  • 158k
2 votes

Training a HMM with Baum-Welch gives different results across runs

It is impossible to locate the issue for sure without inspecting the implementation and results in more detail than is ontopic here. For instance, numeric algorithms always have potential issues ...
Raphael's user avatar
  • 72.3k
1 vote

Find a transducer that maps a given deterministic process to another

Your processes are just deterministic finite-state transducers. Question 1: It sounds like you are asking, given two deterministc finite-state transducers $S,P$, can we find a deterministic finite-...
D.W.'s user avatar
  • 158k
1 vote
Accepted

Viterbi Algorithm: initial state with ONE probability

Wikipedia is wrong. That's not what $T_1$ stores. Rather, $T_1$ stores the likelihood of a path... namely, the likelihood of the path that has the highest likelihood. What's the likelihood of a ...
D.W.'s user avatar
  • 158k
1 vote

HMM tagger - Baum Welch training

Actually, there are only $459^3$ transitions, not $459^4$ transitions. That helps a lot. This is because a state is a pair $(t,u)$ where $t,u$ are tags, and a transition has the form $(t,u)\to (u,v)$...
D.W.'s user avatar
  • 158k
1 vote

Convergence of Markov model

This isn't a hidden Markov model; this is an ordinary Markov model. Take a look at Wikipedia's article on Markov chains and specifically the notion of a steady-state distribution (or stationary ...
D.W.'s user avatar
  • 158k

Only top scored, non community-wiki answers of a minimum length are eligible