<div class="gmail_quote">On Tue, Jul 13, 2010 at 2:16 PM, Glen Jarvis <span dir="ltr"><<a href="mailto:glen@glenjarvis.com">glen@glenjarvis.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
I was invited to this list for questions I have about Hidden Markov Models. Please forgive the extra chatter.<br clear="all"><br></blockquote><div><br></div><div>This is exactly what this list is for!</div><div><br></div>
<div>"A HMM can be considered as the simplest dynamic Bayesian network."</div><div><br></div><div>Eek! That's an awful place to start from, unless you already know Bayesian networks (if you do, I have a very dense 600 page book I'd love to get an explanation of). It's like saying a NOT gate is the simplest quantum tunneling gate, or something similarly startlingly "This is the simplest example of a [insert family of obscure and generally brain-fucking objects here]." Bayes nets are nasty awful things to implement, and HMMs are incredibly much simpler.</div>
<div><br></div><div>Stick to the "Concrete Example" on wikipedia. I did a presentation on it in the last ML incarnation; it might have been one of the things we programmed our way through. Here's that presentation as a correspondence course:</div>
<div><br></div><div>There are two big conceptual hurdles to understanding HMMs: </div><div><br></div><div>1) the hidden part (which is always poorly explained, because it's impossible to explain in a straightforward and concise way, and academics choose concise), and</div>
<div><br></div><div>2) the dynamic programming way (which is typically poorly explained, because it's difficult to explain in a straightforward and concise way, and academics choose concise)</div><div><br></div><div>Load up the "Concrete Example" section of wikipedia's HMM page. Do not click any other links, especially not the Markov Model page, as it's obtuse and useless to a beginner. Start with writing something that generates random observations from the underlying model, to get a feel for what an HMM is modeling. It's not intuitive at first, and then it suddenly clicks and you get it. You will then forget, and repeat the moment of enlightenment several times as you see different confusing aspects of the model (unless you've been thinking probabilistically for a long time).</div>
<div><br></div><div>Once you get the idea of how the HMM is "hiding" its state, and have an intuitive feeling for how the combined probabilities work on the generation side, you can step back to conditional probabilities bit. At that point, you want to make a big hidden*observed matrix on a piece of paper, draw a toy model on another piece of paper. Make the probabilities friendly. From there, start at the very beginning of the piece of paper, and do what your software did above. Do this for 4 or 5 columns, which is a lot of time spent copying numbers and feeling how the cells interconnect. As you fill in each cell, draw arrows between cells if you need to, and say out loud what's happening. Do this in the privacy of your own home. But, really, do talk yourself through it, it's very helpful.</div>
<div><br></div><div>You can implement this process (it's very computationally expensive, but that doesn't matter for our toy problems), and have one thing that implements the use of HMMs to explain a sequence of observations. It's only useful for pedagogy, so, write it, commit it to your dvcs of choice, and forget about it.</div>
<div><br></div><div>Go read up on Levenshtein distance. <a href="http://en.wikipedia.org/wiki/Levenshtein_distance">http://en.wikipedia.org/wiki/Levenshtein_distance</a> -- this is dynamic programming. It's the class of things Viterbi fits into. Once you have implemented this and it works, make sure you understand how dynamic programming worked there.</div>
<div><br></div><div>Next, go to the wikipedia page for the viterbi algorithm. It's a dynamic algorithm that has a bunch of cells, much like levenshtein, but, this time, you're keeping track of each transition (so you have the whole string). In Levenshtein, this is equivalent to remembering the sequence of commands you used to edit the string. In the cells, instead of an edit distance, you have the probability that you went into that state. Unlike Levenshein, this path isn't necessarily a connected sequence of cells (you can transition out to any of the next states at each point; I'm pretty sure this actually a higher-dimensional walk and they are therefore adjacent in the next dimension, but haven't bothered to think about it). Anyway, you've got cells that get highlighted one per column, as in viterbi, which show the most probable explanation of how you got to that observation.</div>
<div><br></div><div>From here, you're ready for Baum-Welch, but that's not as amenable to a correspondence course without a bit more math.</div><div><br></div><div><br></div><div>FWIW, in my toy models, I like 3 hidden states and 3 emitted states, with the hidden states having even chances of transitioning to each other (1/3 all round), and having each hidden state correspond to an observed state at .8, with .1 to the other observed states.</div>
<div> </div><div>Happy hacking,</div><div>--</div><div>/jbm</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div>I work at a Phylogenomics lab and we do HMM stuff all the time -- with either the SAM software tool (<a href="http://compbio.soe.ucsc.edu/sam.html" target="_blank">http://compbio.soe.ucsc.edu/sam.html</a>), or the newer tool HMMR (<a href="http://hmmer.janelia.org/" target="_blank">http://hmmer.janelia.org/</a>). Conceptually I have 'enough' knowledge -- like a user to a pc has enough to be able to point and click to read their email.</div>
<div><br></div><div>But, the fundamental "could I write my own toy example" always escapes me.</div><div><br></div><div>Here's what I know (from the ground up):</div><div><br></div><div>Conditional Probability:</div>
<div> Although I never reviewed this Wiki page, it's probably a fairly good introduction:</div><div> <a href="http://en.wikipedia.org/wiki/Conditional_probability" target="_blank">http://en.wikipedia.org/wiki/Conditional_probability</a></div>
<div><br></div><div> </div><div>Baye's Theorem:</div><div> This wiki page doesn't explain it in a clear way like I would to someone just starting off. I'd start with a conditional tree (classic text book examples are - base decision (root of the tree) is "if the owner purchased a warranty or not (either yes (left branch) or no (right branch). And, then a second condition -- let's say the radio breaks (another fork of the left tree), for example. Then, we can say things like "what's the probability that, given the condition that someone purchased a warranty, what's the probability that they have a broken radio)... Obviously this would be much clear with a nice whiteboard and a decision tree. Baye's theorem has always twisted a mind or two in probability class - but it's actually not that hard once you get your mind around it (although I need a refresher).</div>
<div><br></div><div> <a href="http://en.wikipedia.org/wiki/Bayes'_theorem" target="_blank">http://en.wikipedia.org/wiki/Bayes'_theorem</a></div><div><br></div><div><br></div><div>The Simplest Baysean Network </div>
<div> I'm obviously working myself up to the Wiki page for an HMM (<a href="http://en.wikipedia.org/wiki/Hidden_Markov_model" target="_blank">http://en.wikipedia.org/wiki/Hidden_Markov_model</a>). This explains that an HMM is "A HMM can be considered as the simplest dynamic Bayesian network." [1]). </div>
<div><br></div><div> But, the simples dynamic Bayesian network Wiki page (<a href="http://en.wikipedia.org/wiki/Dynamic_Bayesian_network" target="_blank">http://en.wikipedia.org/wiki/Dynamic_Bayesian_network</a>) used to talk about grass, water and sprinklers (as an example). Although I didn't get it 100%, I always felt comfortable there was a real-world example.</div>
<div><br></div><div> With all of that said, I still couldn't "do it." How was this different than a Baysean decision tree? If I had a simple exercise that I could work through, with an 'answer to compare to', it would help. </div>
<div><br></div><div><br></div><div>Best of all, I'd like to write a very small toy program. I'm most comfortable with Protein Multiple Sequence Alignments (MSA), so if I could make a very basic hmm from a small MSA, it'd really help..</div>
<div><br></div><div> Can anyone explain to me, like they were speaking to a 6-year old, how a simple baysean network (HMM) can be created. If you want an example, imagine the following:</div><div><br></div><div><br></div>
<div><br></div><div><br></div><div>* There are 20 letters of an alphabet (all letters except JOBZUX (interesting way to remember it :))</div><div>* An example of a set of sequences that have been aligned follows:</div><div>
<br></div><div><span style="font-family:'courier new', monospace">DLITPLHTYMITGN-VCVHVIKKIIELGGDMDMKCV</span></div><div><div><font face="'courier new', monospace">NLITPLHSYLRRDELISASVLKKVIELGADRNLRCC</font></div>
<div><font face="'courier new', monospace">HLITPLHSYLRRDESISASVLKKVIELGADRNLRCC</font></div><div><font face="'courier new', monospace">HLITPLHSYLRRDESISASVLKKVIELGADRNLRCC</font></div>
<div><font face="'courier new', monospace">HLITPLHSYLRRDESISASVLKKVIELGADRNLRCC</font></div><div><font face="'courier new', monospace">DLITPLHTYMITGN-VCVHVIKKIIELGGDMDMKCV</font></div>
<div><font face="'courier new', monospace">NLITPLHTYMITGN-VCVHVIKKIIELGGDMDMKCI</font></div><div><font face="'courier new', monospace">NLITPLHTYMITGN-VCVDVIKKIIELGGDMDMKCV</font></div>
<div><font face="'courier new', monospace">DLITPLHTYTITGN-VCAYVIKKIIELGGDMDMKCV</font></div><div><font face="'courier new', monospace">DLITPLHTYMITGN-VCVHVIKKIIELG--------</font></div>
</div><div><br></div><div>So, in this example, the first column is more variable than the second or the fourteenth. </div><div><br></div><div>I should be able to score an HMM and see if it matches another sequence (notice lower case letters mean an HMM insert state):</div>
<div><br></div><div><div><font face="'courier new', monospace">masltehaivnvrkliystcledfdnristnarinnydpddgycsdgdiysynhtvrykhikvfkkkyyg</font></div><div><font face="'courier new', monospace">idnrqrqqytdsktalidiigsmilmlkadrknkslvdqykkfvkyiikdnksktanhvfdipnngdmdi</font></div>
<div><font face="'courier new', monospace">lytyfnsprtrcikldlikymvdvgivnlnyvckktgygilhaylgnmnvdidilewlcnngvdvnlqns</font></div><div><font face="'courier new', monospace">......................................................................</font></div>
<div><font face="'courier new', monospace">...............NLITPLHTYMITGN.VCVDVIKKIIELGGDMDMKCVngmspimtymtnidnvnpe</font></div><div><font face="'courier new', monospace">itnayiesldgdkvknipmilhsyitlarnidisvvysflqpgvklhykdsagrtclhqyilrhnistni</font></div>
<div><font face="'courier new', monospace">ikllheygndvnepdnigntvlhtylsmlsvvhildpetdndirldviqcllslgaditavnclgytplt</font></div><div><font face="'courier new', monospace">syictaqnymyydiidclisdkvlnmvkhrilqdllirvddtpciihhiiakyniptdlytdeyepydst</font></div>
<div><font face="'courier new', monospace">dihdvyhcaiierynnavcetsgmtplhvsiishtnanivmdsfvyllsiqaniniptkngvdplmltme</font></div><div><font face="'courier new', monospace">nnmlsghqwylvknildkrpnvdivisfldkcyaagkfpslllseddiikptlrlalmlagldycnkcie</font></div>
<div><font face="'courier new', monospace">ymerdiaildnshamflafdklvsirdnidkltklhinsrsnisiydilvskcykediithrenhnlvac</font></div><div><font face="'courier new', monospace">chgndplydiinkyitdarsmyyiandisryimdmypvmripvpllfsciigifrltyfkkiiidrhhds</font></div>
<div><font face="'courier new', monospace">finarltdea</font></div></div><div><br></div><div><br></div><div>I know we can use a substitution matrix (i.e., blosum62; <a href="http://www.uky.edu/Classes/BIO/520/BIO520WWW/blosum62.htm" target="_blank">http://www.uky.edu/Classes/BIO/520/BIO520WWW/blosum62.htm</a>) to say how likely it is for one of the letters to change to another letter, but how do I incorporate that likelihood given that likelihood of the previous letter (the likelihood that the second column is an L, given the first column is a D (obviously pretty high in the above example). </div>
<div><br></div><div>Here's a snippet of what was generated for this example:</div><div><br></div><div><div><font face="'courier new', monospace">HMM A C D E F G H I K L M N P Q R S T V W Y</font></div>
<div><font face="'courier new', monospace"> m->m m->i m->d i->m i->i d->m d->d</font></div><div><font face="'courier new', monospace"> COMPO 2.95757 3.22921 2.84828 2.93689 4.02506 2.84493 3.33255 2.33133 2.65067 2.12155 3.45566 3.32303 3.36052 3.85947 3.13260 2.99602 2.82345 2.43542 5.63061 3.48580</font></div>
<div><font face="'courier new', monospace"> 2.68618 4.42225 2.77519 2.73123 3.46354 2.40513 3.72494 3.29354 2.67741 2.69355 4.24690 2.90347 2.73739 3.18146 2.89801 2.37887 2.77519 2.98518 4.58477 3.61503</font></div>
<div><font face="'courier new', monospace"> 0.01686 4.48732 5.20967 0.61958 0.77255 0.00000 *</font></div><div><font face="'courier new', monospace"> 1 3.06925 5.62515 1.55218 2.36308 4.87352 3.48242 2.02657 4.44300 2.84967 3.92317 4.73346 1.82577 4.04654 3.07283 3.40453 2.97597 3.33762 4.00967 6.04161 4.55323 1 x -</font></div>
<div><font face="'courier new', monospace"> 2.68618 4.42225 2.77519 2.73123 3.46354 2.40513 3.72494 3.29354 2.67741 2.69355 4.24690 2.90347 2.73739 3.18146 2.89801 2.37887 2.77519 2.98518 4.58477 3.61503</font></div>
<div><font face="'courier new', monospace"> 0.01686 4.48732 5.20967 0.61958 0.77255 0.48576 0.95510</font></div></div><div><br></div><div><br></div><div>Err.. at this point I'm so confused on what the actual product of an HMM actually is, I forget all I did know... </div>
<div><br></div><div>Has anyone worked with HMMs in a different context? Are there toy examples we could write? Do you have any input on this?</div><div><br></div><div><br></div><div><br></div><div>Cheers,</div><div><br>
</div>
<div><br></div><div>Glen</div><div>[1] <a href="http://en.wikipedia.org/wiki/Hidden_Markov_model" target="_blank">http://en.wikipedia.org/wiki/Hidden_Markov_model</a></div><div>-- <br>Whatever you can do or imagine, begin it;<br>
boldness has beauty, magic, and power in it.<br>
<br>-- Goethe <br>
</div>
<br>_______________________________________________<br>
ml mailing list<br>
<a href="mailto:ml@lists.noisebridge.net">ml@lists.noisebridge.net</a><br>
<a href="https://www.noisebridge.net/mailman/listinfo/ml" target="_blank">https://www.noisebridge.net/mailman/listinfo/ml</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br>Josh Myer 650.248.3796<br> <a href="mailto:josh@joshisanerd.com">josh@joshisanerd.com</a><br>