Modeling and Predicting Sequences: HMM and (may be) CRFAmr Ahmed10701Feb 25Big Picture• Predicting a Single Label– Input (x): A set of features:- Bag of words in a document- Output (y): Class label- Topic of the document- Predicting Sequence of Labels– Input (x): A set of features (with order/structure among them)• Sequence of words in a sentence– Output (y)• Part of speech (POS) tag of each wordNotation Note:I use normal face letters for scalar as in y and bold face letters for vectors like x and yPredicting Sequences• Example: POSyx Students found the HW easy• Example NP chunkingy:X: Rockwell International Corp signed an agreement with Boeing Co.B I E O B O B EENN VBD DD NN JJBack To big Picture• Generative: – Models P(x,y)– Predict using Bayes rule argmax P(y|x)– Naïve Bayes• Discriminative:– Model P(y|x)– Predict using argmax P(y|x)– Logistic RegressionSingle OutputBack To big Picture• Generative: – Models P(x,y)– Predict using Bayes rule argmaxyP(y|x)– HMM• Discriminative:– Model P(y|x)– Predict using argmaxyP(y|x)– CRFSequence of OutputHMM• Defines a generative model over P(x,y)• Each x has M options and each y has K options• You need a big table of size M|X|K|Y|• We need to add some conditional independence assumption to make things manageable– We have done that in Naïve Bayesyxy1y2y3yTx1x2x3xTxHMM • What we need to define#par. shorthand– Initial state: P(y1) K-1 pi=P(y1=i) – Transitoin: P(yt|yt-1) K*(K-1) aij=P(yt+1=j|yt=i) – Emission: P(xt|yt) K*(M-1) bik=P(xt=k|yt=i) • Factorization:y1y2y3yTx1x2x3xTP(x1; : : : ; xT; y1; : : : ; yT) = P(y1)p(x1jy1)p(y2jy1) : : : P(y2jy1)P(xTjyT)P(x1; : : : ; xT; y1; : : : ; yT) = P(y1)QtP(ytjyt¡1)P(xtjyt)Tasks• Inference– Find P(y|x)• MPA: P(yt|x)• Veterbi: P(y|X)– Learning• Learning model parameters using MLE–pi, aij, bik– Fully Observed: » count and normalize– Unsupervised: » EMInference: MPA• Find argmaxiP(yt=i|x)• We need to compute P(yt=i|x) firstp(yt= ijx1; : : : ; xT) =p(yt= i; x1; : : : ; xT)p(x1; : : : ; xT)=p(yt= i; x1; : : : ; xt)p(xt+1; : : : ; xTjyt= i; x1; : : : ; xt)p(x1; : : : ; xT)=p(yt= i; x1; : : : ; xt)p(xt+1; : : : ; xTjyt= i)p(x1; : : : ; xT)=®it¯itp(x1; : : : ; xT)(1)y1y2y3yTx1x2x3xTMPA• We need to do that for any t– .– Define a recursive program®1; ®2; : : : ; ®TAAxtx1yty1... Axt-1yt-1... ... ... ®it= p(yt= i; x1; : : : ; xt)®jt¡1= p(yt¡1= j; x1; : : : ; xt¡1)====1),,,,...,(),,,...,(11111tytttttttktkyyxxxPkyxxxP),,...,,|(),...,,|(),,...,(1111111111===tttttttyttyxxkyxPxxykyPyxxPt)|()|(),,...,(11111kyxPykyPyxxPttttyttt===)|(),,...,()|(1111iykyPiyxxPkyxPttitttt=====kiiitttakyxP,1)|(==Divide variable into three sets:{X1,..,xt-1,yt-1} (to be able to seet-1),{yt},{xt}, then apply chain ruleSumming over yt-1is just summing Over yt-1=1…KA trick that we will use often: add a variable and marginalize over to be able to apply recursionForward Algorithmy1y2yTx1x2xT111kT1Tk212k1,122)1|(iiiayxP==kiiiakyxP,122)|(==11111)1|(p== yxPkkkyxPp)|(111==Inference: MPA• Find argmaxiP(yt=i|x)• We need to compute P(yt=i|x) firsty1y2y3yTx1x2x3xTp(yt= ijx1; : : : ; xT) =p(yt= i; x1; : : : ; xT)p(x1; : : : ; xT)=p(yt= i; x1; : : : ; xt)p(xt+1; : : : ; xTjyt= i; x1; : : : ; xt)p(x1; : : : ; xT)=p(yt= i; x1; : : : ; xt)p(xt+1; : : : ; xTjyt= i)p(x1; : : : ; xT)=®it¯itp(x1; : : : ; xT)(1)Backward Algorithm• We need to do that for any t– .– Define a recursive program¯1; ¯2; : : : ; ¯TA Axt+1xTyt+1yT... ¯it= p(xt+1; : : : ; xTjyt= i)¯jt+1= p(xt+2; : : : ; xTjyt+1= j)Axtyt... ... ... )|,...,(1kyxxPtTtkt====1)|,,...,(11tyttTtkyyxxP),,|,...,(),|()|(112111kyiyxxxPkyiyxpkyiyPtttTttttitt=======itttiikiyxpa111,)|(==)|,...,()|()|(12111iyxxPiyxpkyiyPtTtttitt=====Divide variable into three sets: {yt+1},{xt+1},{Xt+2,..,xT} (to be able to see t+1) then apply chain ruleadd and marginalize trickBackward Algorithmy1y2yTx1x2xT111kT1 = 1Tk= 1T11T1kiTTTiiiyxpa)|(,1=iTTTiikiyxpa)|(,=Inference: MPA• Find argmaxiP(yt=i|x)• We need to compute P(yt=i|x) firsty1y2y3yTx1x2x3xTp(yt= ijx1; : : : ; xT) =p(yt= i; x1; : : : ; xT)p(x1; : : : ; xT)=p(yt= i; x1; : : : ; xt)p(xt+1; : : : ; xTjyt= i; x1; : : : ; xt)p(x1; : : : ; xT)=p(yt= i; x1; : : : ; xt)p(xt+1; : : : ; xTjyt= i)p(x1; : : : ; xT)=®it¯itp(x1; : : : ; xT)(1)EvaluationP (x1; : : : ; xT) =XyTP (x1; : : : ; xT; yT)=kXi=1P (x1; : : : ; xT; yT= i)=kXi=1®iTp(yt= ijx1; : : : ; xT) =®it¯itp(x1; : : : ; xT)Now we have everything to compute:Practical Consideration• , are product of many terms• Likely to run (and you will) into underflow for any sequence > 10• Can we use logs?• In general we didn’t get log() on the right hand side, but you can use a technique called (log add) that I didn’t discuss in the recitation.• Solution: rescaling --- normalize after each step! ) ) )kiiitkttktkiiitkttktayxPayxP,1,1log)1|(loglog)1|(====Scaling• Normalize after each step!• ctis a normalization constant• Keep track of ctfor all t =====jjiiittttjjiiitttkiiitttktajyxPcajyxPakyxP,1,1,1)|()|()|(ˆScaling: Interpretation• How to interpret ctand the normalized • Claim: remember• Proof by induction: assume it is true for t-1==tiiktktc11ˆ ==jjiiittttajyxPc,1)|(ktttttkiiitttttttkiiittttttjjiiitttkiiitttktccakyxPccackyxPajyxPakyxP ===========1'',111'',111'',1,11)|(1 1)|( )|()|(ˆBy definition of ctSubs. t-1from hypothesisScaling: Computation• Can we still calculate P(x1,..,xT)• Yes!• But you really need to do it in log space:=========TtTtKiiTKiTttiTKiiTxxPcc111111),...,(111ˆ ) )==TttTcxxP11log,...,logScaling: Backward • You can use the same trick with • Now how to compute MPA• Then finally normalize• Note that the constant in the “hat” version of both and is only function of t (same for all k)ktktktktttPkyPkyP=== )(),()|(xxxTasks• Inference– Find P(y|x)• MPA:
View Full Document
Unlocking...