Talk:Forward–backward algorithm: Difference between revisions

Revision as of 17:18, 21 July 2010

Latest revision as of 08:13, 19 May 2024

(22 intermediate revisions by 15 users not shown)

Line 1:

{{WikiProject Robotics|nested=nobanner shell|class=startStart|importance=mid}}

{{WikiProject Computing|class=StartRobotics|importance=mid}}

{{WikiProject Computing|importance=}}

}}

---

==Untitled==

The O_1 matrix listed in the Forward Algorithm section is inconsistent with the one presented in the Example section, even though both the transition matrix (T) and the emission matrix (B) are the same between the two sections. I believe the O_1 matrix listed in the example section is correct. This would be much more clear if there were more hidden states than emissions or vice versa, since the matrix dimensions would be indicative of whether states are being conditioned on emissions or if emissions are being conditioned on states. No edits made.

--- <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/129.67.44.219|129.67.44.219]] ([[User talk:129.67.44.219|talk]]) 16:44, 26 March 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

The description is very hard to follow. It is incomplete, being based upon and making reference to a book that is not available online. The one-dimensional vectors are written wrongly in the matrix formulas (horizontal instead of vertical). IMO, this article needs a fundamental re-writing, it is extremely frustrating to read as it is.

Line 92 ⟶ 99:

== Merge with Forward Algorithm ==

{{discussion top|result='''No merge of [[forward algorithm]]'''. --[[User:Karl.brown|KarlB]] ([[User talk:Karl.brown|talk]]) 22:17, 7 July 2012 (UTC) }}

I am against the proposed merge of [[forward algorithm]] into this article, because the forward algorithm is an important algorithm in its own right; it is probably more frequently employed than the forward-backward algorithm. Since the forward algorithm is used as a subprocedure of the forward-backward algorithm (it is precisely step 1 in the description), I would propose the following: We make the description of the algorithm a template, which we then simply include in both articles. [[Special:Contributions/131.159.0.7|131.159.0.7]] ([[User talk:131.159.0.7|talk]]) 17:18, 21 July 2010 (UTC)

I am also against the proposed merge, for the same reasons. In addition, it's nice to see a short-n-sweet description of the Forward algorithm by itself. If the Forward-Backward article were appended, then you glance at how long the scroll bar is, and flip through the long article and feel daunted by the complexity. A user. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/15.203.233.76|15.203.233.76]] ([[User talk:15.203.233.76|talk]]) 17:51, 19 November 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

:Removed the merge proposal since it's been around for a year, nobody defended it and I'm the third reader to disagree here. The forward algorithm is useful in its own right and deserves its own article. [[User:Qwertyus|Qwertyus]] ([[User talk:Qwertyus|talk]]) 09:46, 2 August 2011 (UTC)

::Someone took a bold step and replaced "Forward algorithm" with a redirect (edit was 30. september 2011 kl. 19:34‎ [[User:Max Libbrecht]]). I assume good faith, but having seen the discussion here, and no discussion anywhere else that supports the effective deletion, I'm going to revert the [[Forward algorithm]] page to being a separate item. I might also put a "not to be confused with..." --[[User:Mcld|mcld]] ([[User talk:Mcld|talk]]) 10:58, 2 May 2012 (UTC)

{{discussion bottom}}

== Page Cleanup ==

Line 115 ⟶ 129:

Semi-agreed semi-disagreed. I am taking a class on HMM and this matrix treatment of the algorithms was sorely needed. However the switch from right multiplication in the description of the forward algorithm to left in the example is a serious mistake, especially since the transposes that are necessary are invisible in the example since the matricies are symmetrical. What this page needs is an introductory section without the matrix notation and a cleanup of the matrix examples/explanation, but please don't jettison a useful resource. --[[User:Wjeck|Wjeck]] ([[User talk:Wjeck|talk]]) 13:54, 25 November 2009 (UTC)

I agree. The problem for me is one of clarity, not accessibility or computational efficiency. Matrix notation is meant to make some concepts clearer, and this is not really one of them. It should be fine to keep the matrix notation in another section, but the first description should be in more straightforward terms. But I tried looking for such an explanation on the web, and couldn't find it, so maybe the first step would be to link to one from this article. I didn't find Russell and Norvig's presentation very clear. [[User:A5|A5]] ([[User talk:A5|talk]]) 23:07, 4 August 2010 (UTC)

:Strongly agree. I work with matrix maths a lot, but it's obvious to me that the explanation given in this page is quite hard to understand. It seems to be oriented towards computational efficiency rather than clear exposition. The bit with the emission probabilities placed into a diagonal matrix in particular, really rams the point home that the layout is not so we can understand it! --[[User:Mcld|mcld]] ([[User talk:Mcld|talk]]) 11:05, 2 May 2012 (UTC)

I agree. There's an additional problem; the evidence states 00100 are a [[palindrome]], which is extremely confusing for an algorithm that is supposed to have separate forward & backward steps. Furthermore, the transition matrix is symmetric, which also makes the backwards step more unclear. Should you transpose it? [[User:Chrism2671|Chrism2671]] ([[User talk:Chrism2671|talk]]) 12:45, 6 April 2022 (UTC)

== Merge with BCJR algorithm ==

{{discussion top}}

It has been proposed since 2009 to merge [[BCJR algorithm]] into this article. Any thoughts? --[[User:Karl.brown|KarlB]] ([[User talk:Karl.brown|talk]]) 22:18, 7 July 2012 (UTC)

:The merge tag was only added and no discussion was initiated. I am therefore closing the merge request as improper and removing the tags. [[User:Wiki.Tango.Foxtrot|WTF?]] ([[User talk:Wiki.Tango.Foxtrot|talk]]) 18:18, 11 October 2012 (UTC)

{{Discussion bottom}}

== [[ECC]] & BCJR ==

Unfortunate that there's no discussion, since the explanation of [[BCJR]] & viterbi, when applied in the digital ___domain, is considerably easier to understand than the HMM version given here. Unfortunately, the BCJR article is currently a stub with no content in it :-( Anyway, just to make this article easier to understand, I think its important to expand on these other, easier-to-explain, easier-to-comprehend algorithms. [[User:Linas]] ([[User talk:99.153.64.179|talk]]) 00:46, 9 November 2013 (UTC)

== Consistent notation across HMM articles ==

The notation used on this page is inconsistent with the notation used on the [[Hidden_Markov_model|HMM]], [[Forward_algorithm|forward algorithm]], and [[Viterbi_algorithm|Viterbi algorithm]] pages. Namely, in the latter cases, <math>x</math> represent the hidden states and <math>y</math> the observations, whereas here <math>o</math> represent the hidden states with <math>x</math> being the observations. I know that generally there is no standard notational convention across the many HMM papers, but for this set of articles, it would be much less confusing to stick with a consistent notation. Thoughts? <small><span class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:OhGodItsSoAmazing|OhGodItsSoAmazing]] ([[User talk:OhGodItsSoAmazing|talk]] • [[Special:Contributions/OhGodItsSoAmazing|contribs]]) 19:32, 7 December 2013 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

== Request for efficient higher order extension ==

I've been looking for a reference that describes the efficient extension when using an order greater than one. I know the basic trick is to take (Q x Q) --> Q', then use this space which maps from [q_k at t-1 and q_l at t] to [q_j at t and q_i at t+1]. Clearly q_l=q_j. This causes many zeros in the transition probability matrix.

Without modifying the algorithm, time is wasted on these zeros. A second order HMM implemented naively has a run time of O(N^4 T). But if we squeeze the zeros out in the algorithm, then this reduces to O(N^3 T). A third order HMM implemented naively runs in O(N^6 T), but squeezing the zeros out to avoid the algorithm running over them would run in O(N^4 T). I've done some work myself, but without references it would count as original research.

I'll provide one possible extension in the forward pass below (using the forward algorithm listed here in non-matrix form http://www.cs.sjsu.edu/~stamp/RUA/HMM.pdf):

f0:1(i) = pi(i)*b_i(O_1)

f0:2(j,i) = pi(j,i)*b_{j,i}(O_2), using pi(j,i) as the joint prior probability of state q_j followed by state q_i. Alternatively

f0:2(j,i) = f0:1(j) * T{j}{i} * b_{j,i}(O_2), but here T{j,i} is an element of the first-order transition matrix

f0:t(j,i) = sum_{l,k}^{N} f0:{t-1}(k,l) * T_{k,l}{j,i} * B{j,i}(O_t}, but q_l=q_j. Squeezing the zeros out give:

f0:t(j,i) = sum_{k}^{N} f0:{t-1}(k,j) * T_{k,j}{j,i} * B{j,i}(O_t}, for i and j in 1, 2, ..., N

Mouse7mouse9 20:20, 28 January 2014 (UTC) <small><span class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Mouse7mouse9|Mouse7mouse9]] ([[User talk:Mouse7mouse9|talk]] • [[Special:Contributions/Mouse7mouse9|contribs]]) </span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

== Forward Probabilities ==

There is already a page on Forward Algorithm. It would be better to reference that instead of repeating. The section on backward probabilities starts:

A similar procedure can be constructed to find backward probabilities.

referring the section on forward probabilities, forcing the reader who's already read the article on the Forward Algorithm to go review above section to ensure they understand the reference ...