NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/comp/speech/490

Text File | 1993-01-24 | 3.4 KB | 83 lines

Newsgroups: comp.speech
Path: sparky!uunet!seas.gwu.edu!marshall
From: [e-mail] (Christopher Marshall)
Subject: Re: Null Transitions in HMMs
Message-ID: <[e-mail]>
Sender: [e-mail]
Organization: George Washington University
References: <[e-mail]> <[e-mail]>
Date: Sun, 24 Jan 1993 23:22:04 GMT
Lines: 71

>The solution to this is to NOT change the equations at all - but to
>change A(i,j) and B(i,j,k).
>
>A(i,j) is defined by you as the probability of moving from state i to
>state j in 1 time step. If we instead define it as the probability of
>moving from state i to state j while producing exactly one output then
>the problem is solved. If there are no null transitions then these
>definitions are equivalent.
>
>B(i,j,k) is similarly defined normally as the probability of producing
>symbol k given that a transition is made in one time step from state i
>to state j. The new definition will be the probability of producing
>symbol k given that exactly one output is produced in a move from
>state i to state j.

This is a very good explanation.  I like it.  You are describing a
way to convert an HMM with null transitions into one without
null transitions.  It basically results in adding normal
transitions to the HMM for every null transition you remove.

From earlier discussions I have had though, I get the feeling that
there is another approach which requires fewer computations
than this one.  I have never been able to figure it out though.

>An example will make this clearer (I hope). Say you already have the
>A(i,j) and B(i,j,k) for no null transitions. Then say we add a null
>transition from state s1 to state s2 and wish to find A'(i,j) and
>B'(i,j,k) including this transition. We can write:
>
>A'(i,s2) = A(i,s2) + A(i,s1)
>B'(i,s2,k) = B(i,s2,k) + B(i,s1,k)
>

I applied your logic to this example and came up with a different set
of equations, although similar in spirit.

Assume we have an HMM with A(i,j) and B(i,j,k), which contains a null
transition from S1 to S2.  Let B(S1,S2,k)= 0 for all k.  We compute A'(i,j)
and B'(i,j,k) for the corresponding HMM without null transitions as follows:

case 1 if i!=S1:
   A'(i,j)= A(i,j)
   B'(i,j,k)= B(i,j,k)

case 2 if i=S1 and j!=S2:
   This is the tricky case.  When considering transitions from S1 to non-S2
   states, you have to consider the possibility that the HMM will go from
   S1 to S2 to j, emmiting a symbol on the s2 to j transition AND the
   possibility that the HMM will go directly from S1 to j.
   A'(S1,j)= A(S1,j) + A(S1,S2)*A(S2,j)
   B'(S1,j,k)= A(S1,j)*B(S1,j,k) + A(S1,S2)*A(S2,j)*B(S2,j,k)
               -----------------------------------------------
               A(S1,j) + A(S1,S2)*A(S2,j)

case 3 if i=S1 and j=S2:
   For the HMM to go from S1 to S2 and output a symbol, it must go
   S1 to S2 to S2 and output a symbol on the S2->S2 transition.  Hence,
   A'(S1,S2)= A(S1,S2)*A(S2,S2)
   B'(S1,S2,k)= B(S2,S2,k)

Now, what about an HMM with more than one null transition?  As long
as no two null transitions touch head to tail (so that you could make two
or more transitions in a row and not output a symbol), then this procedure
can be applied once for each null transition and it will work correctly.

From what I have read/heard though, it is possible to handle an HMM with
null transitions as long as there are no closed loops of null transitions
present.

Chris Marshall
[e-mail]