1、A Review of Hidden Markov Models for Context-Based Classification ICML01 Workshop on Temporal and Spatial Learning Williams College June 28th 2001,Padhraic Smyth Information and Computer Science University of California, Irvinewww.datalab.uci.edu,Outline,Context in classificationBrief review of hidd
2、en Markov models Hidden Markov models for classificationSimulation results: how useful is context? (with Dasha Chudova, UCI),Historical Note,“Classification in Context” was well-studied in pattern recognition in the 60s and 70s e.g, recursive Markov-based algorithms were proposed, before hidden Mark
3、ov algorithms and models were fully understoodApplications in OCR for word-level recognition remote-sensing pixel classification,Papers of Note,Raviv, J., “Decision-making in Markov chains applied to the problem of pattern recognition”, IEEE Info Theory, 3(4), 1967Hanson, Riseman, and Fisher, “Conte
4、xt in word recognition,” Pattern Recognition, 1976Toussaint, G., “The use of context in pattern recognition,” Pattern Recognition, 10, 1978Mohn, Hjort, and Storvik, “A simulation study of some contextual classification methods for remotely sensed data,” IEEE Trans Geo. Rem. Sens., 25(6), 1987.,Conte
5、xt-Based Classification Problems,Medical Diagnosis classification of a patients state over timeFraud Detection detection of stolen credit cardElectronic Nose detection of landminesRemote Sensing classification of pixels into ground cover,Modeling Context,Common Theme = Context class labels (and feat
6、ures) are “persistent” in time/space,Modeling Context,Common Theme = Context class labels (and features) are “persistent” in time/space,X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,Features (observed),Class (hidden),Time,Feature Windows,Predict Ct using a window, e.g., f(Xt, Xt-1, Xt-2) e.g., NETtalk app
7、lication,X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,Features (observed),Class (hidden),Time,Alternative: Probabilistic Modeling,E.g., assume p(Ct | history) = p(Ct | Ct-1) first order Markov assumption on the classes,X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,Features (observed),Class (hidden),Time,Brief
8、review of hidden Markov models (HMMs),Graphical Models,Basic Idea: p(U) an annotated graphLet U be a set of random variables of interest1-1 mapping from U to nodes in a graphgraph encodes “independence structure” of modelnumerical specifications of p(U) are stored locally at the nodes,Acyclic Direct
9、ed Graphical Models (aka belief/Bayesian networks),In general,p(X1, X2,XN) = p(Xi | parents(Xi ) ),p(A,B,C) = p(C|A,B)p(A)p(B),Undirected Graphical Models (UGs),Undirected edges reflect correlational dependencies e.g., particles in physical systems, pixels in an image Also known as Markov random fie
10、lds, Boltzmann machines, etc,Examples of 3-way Graphical Models,Markov chain p(A,B,C) = p(C|B) p(B|A) p(A),Examples of 3-way Graphical Models,Markov chain p(A,B,C) = p(C|B) p(B|A) p(A),Independent Causes: p(A,B,C) = p(C|A,B)p(A)p(B),Hidden Markov Graphical Model,Assumption 1: p(Ct | history) = p(Ct
11、| Ct-1) first order Markov assumption on the classesAssumption 2: p(Xt | history, Ct ) = p(Xt | Ct ) Xt only depends on current class Ct,Hidden Markov Graphical Model,X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,Features (observed),Class (hidden),Time,Notes:- all temporal dependence is modeled throughthe
12、 class variable C- this is the simplest possible model- Avoids modeling p(X|other Xs),Generalizations of HMMs,R1,C1,R2,C2,R3,C3,RT,CT,- - - - - - - -,Spatial Rainfall (observed),State (hidden),Hidden state model relating atmospheric measurements to local rainfall“Weather state” couples multiple vari
13、ables in time and space(Hughes and Guttorp, 1996)Graphical models = language for spatio-temporal modeling,A1,A2,A3,AT,Atmospheric (observed),Exact Probability Propagation (PP) Algorithms,Basic PP Algorithm Pearl, 1988; Lauritzen and Spiegelhalter, 1988 Assume the graph has no loops Declare 1 node (a
14、ny node) to be a root Schedule two phases of message-passing nodes pass messages up to the root messages are distributed back to the leaves(if loops, convert loopy graph to an equivalent tree),Properties of the PP Algorithm,Exact p(node|all data) is recoverable at each node i.e., we get exact poster
15、ior from local message-passing modification: MPE = most likely instantiation of all nodes jointly Efficient Complexity: exponential in size of largest clique Brute force: exponential in all variables,Hidden Markov Graphical Model,X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,Features (observed),Class (hid
16、den),Time,PP Algorithm for a HMM,X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,Features (observed),Class (hidden),Let CT be the root,PP Algorithm for a HMM,X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,Features (observed),Class (hidden),Let CT be the rootAbsorb evidence from Xs (which are fixed),PP Algorithm fo
17、r a HMM,X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,Features (observed),Class (hidden),Let CT be the rootAbsorb evidence from Xs (which are fixed)Forward pass: pass evidence forward from C1,PP Algorithm for a HMM,X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,Features (observed),Class (hidden),Let CT be the ro
18、otAbsorb evidence from Xs (which are fixed)Forward pass: pass evidence forward from C1Backward pass: pass evidence backward from CT(This is the celebrated “forward-backward” algorithm for HMMs),Comments on F-B Algorithm,Complexity = O(T m2)Has been reinvented several times e.g., BCJR algorithm for e
19、rror-correcting codesReal-time recursive version run algorithm forward to current time t can propagate backwards to “revise” history,HMMs and Classification,Forward-Backward Algorithm,Classification Algorithm produces p(Ct|all other data) at each node to minimize 0-1 losschoose most likely class at
20、each tMost likely class sequence? Not the same as the sequence of most likely classes can be found instead with Viterbi/dynamic programming replace sums in F-B with “max”,Supervised HMM learning,Use your favorite classifier to learn p(C|X) i.e., ignore temporal aspect of problem (temporarily)Now, es
21、timate p(Ct | Ct-1) from labeled training dataWe have a fully operational HMMno need to use EM for learning if class labels are provided (i.e., do “supervised HMM learning”),Fault Diagnosis Application (Smyth, Pattern Recognition, 1994),Features,Fault Classes,X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,
22、Fault Detection in 34m Antenna Systems:Classes: normal, short-circuit, tacho problem, Features: AR coefficients measured every 2 secondsClasses are persistent over time,Approach and Results,Classifiers Gaussian model and neural network trained on labeled “instantaneous window” data Markov component
23、transition probabilities estimated from MTBF dataResults discriminative neural net much better than Gaussian Markov component reduced the error rate (all false alarms) of 2% to 0%.,Classification with and without the Markov context,We will compare what happens when(a) we just make decisions based on
24、 p(Ct | Xt )(“ignore context”)(b) we use the full Markov context(i.e., use forward-backward to“integrate” temporal information),X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,Simulation Experiments,Systematic Simulations,Simulation Setup1. Two Gaussian classes, at mean 0 and mean 1= vary “separation” = sig
25、ma of the Gaussians2. Markov dependenceA = p 1-p ; 1-p pVary p (self-transition) = “strength of context”Look at Bayes error with and without context,X1,C1,X2,C2,X3,C3,XT,CT,- - - - - - - -,In summary.,Context reduces error greater Markov dependence = greater reductionReduction is dramatic for p0.9 e
26、.g., even with minimal Gaussian separation, Bayes error can be reduced to zero!,Approximate Methods,Forward-Only: necessary in many applications“Two nearest-neighbors” only use information from C(t-1) and C(t+1)How suboptimal are these methods?,In summary (for approximations).,Forward only: “tracks”
27、 forward-backward reductions generally gets much more than 50% of gap between F-B and context-free Bayes error2-neighbors typically worse than forward only much worse for small separation much worse for very high transition probs does not converge to zero Bayes error,Extensions to “Simple” HMMs,Semi
28、 Markov modelsduration in each state need not be geometricSegmental Markov Modelsoutputs within each state have a non-constant mean, regression functionDynamic Belief NetworksAllow arbitrary dependencies among classes and featuresStochastic Grammars, Spatial Landmark models, etcSee Afternoon Talks a
29、t this workshop for other approaches,Conclusions,Context is increasingly important in many classification applicationsGraphical models HMMs are a simple and practical approach graphical models provide a general-purpose language for contextTheory/Simulation Effect of context on error rate can be dramatic,Sketch of the PP algorithm in action,Sketch of the PP algorithm in action,Sketch of the PP algorithm in action,1,Sketch of the PP algorithm in action,1,2,Sketch of the PP algorithm in action,1,2,3,Sketch of the PP algorithm in action,1,2,3,4,
