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

Internet Message Format | 1993-01-28 | 4.2 KB

Path: sparky!uunet!charon.amdahl.com!pacbell.com!decwrl!concert!gatech!udel!bogus.sura.net!howland.reston.ans.net!spool.mu.edu!caen!batcomputer!munnari.oz.au!manuel.anu.edu.au!andosl!tridge
From: [e-mail] (Andrew Tridgell)
Newsgroups: comp.speech
Subject: Re: Null Transitions in HMMs
Date: 26 Jan 1993 23:01:56 GMT
Organization: CSLab, Autralian National Uni.
Lines: 83
Distribution: world
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <[e-mail]>
NNTP-Posting-Host: 150.203.15.21

In article <[e-mail]>, [e-mail] (Christopher Marshall) writes:
> 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:

I normally assmume that for any i and j the sum of B(i,j,k) over all k
is 1. This doesn't really matter if A(i,j) is 0 but actually gives
rise to a problem later in your argument.
>
> case 1 if i!=S1:
>    A'(i,j)= A(i,j)
>    B'(i,j,k)= B(i,j,k)
>

I assume you meant: case 1 if i!=S1 and j!=S2 otherwise you neglect
the case A(i,S2), which will change if A(i,S1) is non zero.


> 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)

I think you are making A and B dependant in this equation. B is the
probability of an output symbol given that a transition from i to j
does occur. Otherwise the standard update rules would violate the B
summing to 1 rule (see above). Say the probability A(i,j) was changed
by the update rule. This should have no effect on the distribution of
symbols given that the transition does occur.

also - you assign probabilities to null transitions. This is fine but
I think it is unnecessary

> 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.

Why exclude the possability of null transitions touching head to tail?
Or even of loops of null transitions? As long as you get away from the
time step notion and go to one that is output stepped these do not
pose any problem.

I have always viewed null transitions as convenience connections. They
are a shorthand way of connecting lots of states. They don't really
change the mathematics. If you make them make real changes then you'll
have to go through the rigmarole of re-proving the HMM results with
them in place.

In my equations I have not worried about normalising. This is because
adding a connection always stuffs up the normalisation. If you want to
re-normalise then this is easy. You know that the sum of the
probabilities of leaving a node must be 1 so divide by the sum.  This
means we get:

A''(i,j) = A'(i,j) / {sum over j of A'(i,j)}

similarly:

B''(i,j,k) = B'(i,j,k) / {sum over k of B'(i,j,k)}

Note that I allow B(i,j,k) to be non-zero even if A(i,j) is zero. I
don't store these in practice, of course, but they are there in
theory. In practice the equations look nothing like the ones above. On
a real computer you need to use a log representation and in my case I
use a log integer representation. Does anyone else use a log integer
form?

Andrew

--
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Andrew Tridgell                 CSLab, Research School of Physical Sciences
[e-mail]      Australian National University (x3064)
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-