Spectracular Learning Algorithms For Natural Language Processing

HMMs: the forward algorithmH1H2H3H4thedogsawhimp(the dog saw him) Xp(the dog saw him, h1 h2 h3 h4 )h1 ,h2 ,h3 ,h4The forward algorithm:fh0 π(h)Spectral Learning for NLP41

HMMs: the forward algorithmH1H2H3H4thedogsawhimp(the dog saw him) Xp(the dog saw him, h1 h2 h3 h4 )h1 ,h2 ,h3 ,h4The forward algorithm:fh0 π(h)fh1 Xt(h h0 )o(the h0 )fh00h0Spectral Learning for NLP41

HMMs: the forward algorithmH1H2H3H4thedogsawhimp(the dog saw him) Xp(the dog saw him, h1 h2 h3 h4 )h1 ,h2 ,h3 ,h4The forward algorithm:fh0 π(h)fh1 Xt(h h0 )o(the h0 )fh00h0fh2 Xt(h h0 )o(dog h0 )fh10h0Spectral Learning for NLP41

HMMs: the forward algorithmH1H2H3H4thedogsawhimp(the dog saw him) Xp(the dog saw him, h1 h2 h3 h4 )h1 ,h2 ,h3 ,h4The forward algorithm:fh0 π(h)fh1 Xt(h h0 )o(the h0 )fh00h0fh2 Xh0Spectral Learning for NLPt(h h0 )o(dog h0 )fh10fh3 Xt(h h0 )o(saw h0 )fh20h041

HMMs: the forward algorithmH1H2H3H4thedogsawhimp(the dog saw him) Xp(the dog saw him, h1 h2 h3 h4 )h1 ,h2 ,h3 ,h4The forward algorithm:fh0 π(h)fh1 Xt(h h0 )o(the h0 )fh00h0fh2 Xt(h h0 )o(dog h0 )fh10fh3 t(h h0 )o(saw h0 )fh20h0h0fh4 XXt(h h0 )o(him h0 )fh30h0Spectral Learning for NLP41

HMMs: the forward algorithmH1H2H3H4thedogsawhimp(the dog saw him) Xp(the dog saw him, h1 h2 h3 h4 )h1 ,h2 ,h3 ,h4The forward algorithm:fh0 π(h)fh1 Xt(h h0 )o(the h0 )fh00h0fh2 Xt(h h0 )o(dog h0 )fh10fh3 Xh0Spectral Learning for NLPt(h h0 )o(saw h0 )fh20h0h0fh4 Xt(h h0 )o(him h0 )fh30p(. . .) Xfh4h41

HMMs: the forward algorithm in matrix formSpectral Learning for NLPH1H2H3H4thedogsawhim42

HMMs: the forward algorithm in matrix formSpectral Learning for NLPH1H2H3H4thedogsawhim42

HMMs: the forward algorithm in matrix formIH1H2H3H4thedogsawhimFor each word x, define the matrix Ax Rm m as[Ax ]h0 ,h t(h0 h)o(x h)Spectral Learning for NLP42

HMMs: the forward algorithm in matrix formIH1H2H3H4thedogsawhimFor each word x, define the matrix Ax Rm m as[Ax ]h0 ,h t(h0 h)o(x h) e.g., [Athe ]h0 ,h t(h0 h)o(the h)Spectral Learning for NLP42

HMMs: the forward algorithm in matrix formIH1H2H3H4thedogsawhimFor each word x, define the matrix Ax Rm m as[Ax ]h0 ,h t(h0 h)o(x h) e.g., [Athe ]h0 ,h t(h0 h)o(the h)IDefine π as vector with elements πh , 1 as vector of all onesSpectral Learning for NLP42

HMMs: the forward algorithm in matrix formIH1H2H3H4thedogsawhimFor each word x, define the matrix Ax Rm m as[Ax ]h0 ,h t(h0 h)o(x h) e.g., [Athe ]h0 ,h t(h0 h)o(the h)IIDefine π as vector with elements πh , 1 as vector of all onesThenp(the dog saw him) 1 Ahim Asaw Adog Athe πForward algorithm through matrix multiplication!Spectral Learning for NLP42

The Spectral Algorithm: definitionsH1H2H3H4thedogsawhimDefine the following matrix P2,1 Rn n :[P2,1 ]i,j P(X2 i, X1 j)Easy to derive an estimate:[P̂2,1 ]i,j Spectral Learning for NLPCount(X2 i, X1 j)N43

The Spectral Algorithm: definitionsH1H2H3H4thedogsawhimFor each word x, define the following matrix P3,x,1 Rn n :[P3,x,1 ]i,j P(X3 i, X2 x, X1 j)Easy to derive an estimate, e.g.,:[P̂3,dog,1 ]i,j Spectral Learning for NLPCount(X3 i, X2 dog, X1 j)N44

Main Result Underlying the Spectral AlgorithmIDefine the following matrix P2,1 Rn n :[P2,1 ]i,j P(X2 i, X1 j)IFor each word x, define the following matrix P3,x,1 Rn n :[P3,x,1 ]i,j P(X3 i, X2 x, X1 j)Spectral Learning for NLP45

Main Result Underlying the Spectral AlgorithmIDefine the following matrix P2,1 Rn n :[P2,1 ]i,j P(X2 i, X1 j)IFor each word x, define the following matrix P3,x,1 Rn n :[P3,x,1 ]i,j P(X3 i, X2 x, X1 j)ISVD(P2,1 ) U Rn m , Σ Rm m , V Rn mSpectral Learning for NLP45

Main Result Underlying the Spectral AlgorithmIDefine the following matrix P2,1 Rn n :[P2,1 ]i,j P(X2 i, X1 j)IFor each word x, define the following matrix P3,x,1 Rn n :[P3,x,1 ]i,j P(X3 i, X2 x, X1 j)ISVD(P2,1 ) U Rn m , Σ Rm m , V Rn mIDefinition:Bx U P3,x,1 V {z}Σ 1 {z}m mSpectral Learning for NLPm m45

Main Result Underlying the Spectral AlgorithmIDefine the following matrix P2,1 Rn n :[P2,1 ]i,j P(X2 i, X1 j)IFor each word x, define the following matrix P3,x,1 Rn n :[P3,x,1 ]i,j P(X3 i, X2 x, X1 j)ISVD(P2,1 ) U Rn m , Σ Rm m , V Rn mIDefinition:Bx U P3,x,1 V {z}Σ 1 {z}m mIm mTheorem: if P2,1 is of rank m, thenBx GAx G 1where G Rm m is invertibleSpectral Learning for NLP45

Why does this matter?ITheorem: if P2,1 is of rank m, thenBx GAx G 1where G Rm m is invertibleIRecall p(the dog saw him) 1 Ahim Asaw Adog Athe π.Forward algorithm through matrix multiplication!Spectral Learning for NLP46

Why does this matter?ITheorem: if P2,1 is of rank m, thenBx GAx G 1where G Rm m is invertibleIRecall p(the dog saw him) 1 Ahim Asaw Adog Athe π.Forward algorithm through matrix multiplication!INow note thatBhim Bsaw Bdog BtheSpectral Learning for NLP46

Why does this matter?ITheorem: if P2,1 is of rank m, thenBx GAx G 1where G Rm m is invertibleIRecall p(the dog saw him) 1 Ahim Asaw Adog Athe π.Forward algorithm through matrix multiplication!INow note that Spectral Learning for NLPBhim Bsaw Bdog BtheGAhim G 1 GAsaw G 1 GAdog G 1 GAthe G 146

Why does this matter?ITheorem: if P2,1 is of rank m, thenBx GAx G 1where G Rm m is invertibleIRecall p(the dog saw him) 1 Ahim Asaw Adog Athe π.Forward algorithm through matrix multiplication!INow note that Bhim Bsaw Bdog BtheGAhim G 1 GAsaw G 1 GAdog G 1 GAthe G 1 GAhim Asaw Adog Athe G 1The G’s cancel!Spectral Learning for NLP46

Why does this matter?ITheorem: if P2,1 is of rank m, thenBx GAx G 1where G Rm m is invertibleIRecall p(the dog saw him) 1 Ahim Asaw Adog Athe π.Forward algorithm through matrix multiplication!INow note that Bhim Bsaw Bdog BtheGAhim G 1 GAsaw G 1 GAdog G 1 GAthe G 1 GAhim Asaw Adog Athe G 1The G’s cancel!IFollows that if we have b 1 G 1 and b0 Gπ thenSpectral Learning for NLP46

Why does this matter?ITheorem: if P2,1 is of rank m, thenBx GAx G 1where G Rm m is invertibleIRecall p(the dog saw him) 1 Ahim Asaw Adog Athe π.Forward algorithm through matrix multiplication!INow note that Bhim Bsaw Bdog BtheGAhim G 1 GAsaw G 1 GAdog G 1 GAthe G 1 GAhim Asaw Adog Athe G 1The G’s cancel!IFollows that if we have b 1 G 1 and b0 Gπ thenb Bhim Bsaw Bdog Bthe b0Spectral Learning for NLP46

Why does this matter?ITheorem: if P2,1 is of rank m, thenBx GAx G 1where G Rm m is invertibleIRecall p(the dog saw him) 1 Ahim Asaw Adog Athe π.Forward algorithm through matrix multiplication!INow note that Bhim Bsaw Bdog BtheGAhim G 1 GAsaw G 1 GAdog G 1 GAthe G 1 GAhim Asaw Adog Athe G 1The G’s cancel!IFollows that if we have b 1 G 1 and b0 Gπ thenb Bhim Bsaw Bdog Bthe b0Spectral Learning for NLP 1 Ahim Asaw Adog Athe π46

The Spectral Learning Algorithm1. Derive estimates[P̂2,1 ]i,j Count(X2 i, X1 j)NFor all words x,[P̂3,x,1 ]i,j Spectral Learning for NLPCount(X3 i, X2 x, X1 j)N47

The Spectral Learning Algorithm1. Derive estimates[P̂2,1 ]i,j Count(X2 i, X1 j)NFor all words x,[P̂3,x,1 ]i,j Count(X3 i, X2 x, X1 j)N2. SVD(P̂2,1 ) U Rn m , Σ Rm m , V Rn mSpectral Learning for NLP47

The Spectral Learning Algorithm1. Derive estimates[P̂2,1 ]i,j Count(X2 i, X1 j)NFor all words x,[P̂3,x,1 ]i,j Count(X3 i, X2 x, X1 j)N2. SVD(P̂2,1 ) U Rn m , Σ Rm m , V Rn m3. For all words x, define Bx U P̂3,x,1 V {z}Σ 1 . {z}m mm m(similar definitions for b0 , b , details omitted)Spectral Learning for NLP47

The Spectral Learning Algorithm1. Derive estimates[P̂2,1 ]i,j Count(X2 i, X1 j)NFor all words x,[P̂3,x,1 ]i,j Count(X3 i, X2 x, X1 j)N2. SVD(P̂2,1 ) U Rn m , Σ Rm m , V Rn m3. For all words x, define Bx U P̂3,x,1 V {z}Σ 1 . {z}m mm m(similar definitions for b0 , b , details omitted)4. For a new sentence x1 . . . xn , can calculate its probability, e.g.,p̂(the dog saw him) b Bhim Bsaw Bdog Bthe b0Spectral Learning for NLP47

GuaranteesIThroughout the algorithm we’ve used estimates P̂2,1 andP̂3,x,1 in place of P2,1 and P3,x,1IIf P̂2,1 P2,1 and P̂3,x,1 P3,x,1 then the method is exact.But we will always have estimation errorsIA PAC-Style Theorem: Fix some length T . To haveX p(x1 . . . xT ) p̂(x1 . . . xT ) x1 .xT {z}L1 distance between p and p̂with probability at least 1 δ, then number of samplesrequired is polynomial inn, m, 1/ , 1/δ, 1/σ, Twhere σ is m’th largest singular value of P2,1Spectral Learning for NLP48

Intuition behind the TheoremIDefine  A 2 sX(Âj,k Aj,k )2j,kIWith N samples, with probability at least 1 δ P̂2,1 P2,1 2 P̂3,x,1 P3,x,1 2 wherer I11log Nδr1NThen need to carefully bound how the error propagatesthrough the SVD step, the various matrix multiplications, etcetc. The “rate” at which propagates depends on T , m, n,1/σSpectral Learning for NLP49

SummaryIThe problem solved by EM: estimate HMM parameters π(h),t(h0 h), o(x h) from observation sequences x1 . . . xnIThe spectral algorithm:IIIICalculate estimates P̂2,1 (bigram counts) and P̂3,x,1 (trigramcounts)Run an SVD on P̂2,1Calculate parameter estimates using simple matrix operationsGuarantee: we recover the parameters up to linear transformsthat cancelSpectral Learning for NLP50

Outline Singular value decomposition Canonical correlation analysis Spectral learning of hidden Markov models Algorithm for latent-variable PCFGsSpectral Learning for NLP51

Problems with spectral HMM learning algorithmParameters are masked by an unknown linear transformationINegative marginals (due to sampling error)IParameters cannot be easily interpretedICannot improve parameters using, for example, EMHsu et al. suggest a way to extract probabilities, but the method isunstableSpectral Learning for NLP52

This part of the talkLike the spectral algorithm, has theoretical guaranteesEstimates are actual probabilitiesMore efficient than EMCan be used to initialize EM, which converges in an iteration or twoSpectral Learning for NLP53

L-PCFGs(Matsuzaki et al., 2005; Petrov et al., 2006)S1 ctral Learning for NLP54

The probability of a treep(tree, 1 3 1 2 2 4 1)S1 π(S1 ) t(S1 NP3 VP2 S1 ) VP2NP3D1N2V4P1t(NP3 D1 N2 NP3 ) t(VP2 V4 P1 VP2 ) q(D1 the D1 ) q(N2 dog N2 ) thedogsawhimq(V4 saw V4 ) q(P1 him P1 )p(tree) Xp(tree, h1 h2 h3 h4 h5 h6 h7 )h1 .h7Spectral Learning for NLP55

Inside and Outside TreesAt node VP:Outside tree o SSNPVPNPDtheNdogVsawPVPDNthedogInside tree t himVPVPsawhimConditionally independent given the label and the hidden statep(o, t VP, h) p(o VP, h) p(t VP, h)Spectral Learning for NLP56

Designing Feature FunctionsDesign functions ψ and φ:φ maps any inside tree to a binary vector of length dψ maps any outside tree to a binary vector of length d0SVPVPNPDNthedogOutside tree o ψ(o) [0, 1, 0, 0, . . . , 0, 0] VPsawhimInside tree t 0Rdφ(t) [1, 0, 0, 0, . . . , 0, 0] Rdψ and φ as multinomials p(f ) for f [d] and p(g) for g [d0 ].Spectral Learning for NLP57

Latent State DistributionsThink of f and g as representing a whole inside/outside treeSay we had a way of getting:Ip(f h, VP) for each h and f inside featureIp(g h, VP) for each h and g outside featureThen we could run EM on a convex problem to find parameters.How?Spectral Learning for NLP58

Binary rule estimationTake M samples of nodes with rule VP V NP.At sample iIg (i) outside feature at VPIf2 inside feature at VIf3 inside feature at NP(i)(i)t̂(h1 , h2 , h3 VP V NP) maxt̂MXi 1logXt̂(h1 , h2 , h3 VP V NP) h1 ,h2 ,h3 (i)(i)p(g h1 , VP)p(f2 h2 , V)p(f3 h3 , NP)(i)Spectral Learning for NLP59

Binary Rule Estimation Use Bayes rule to convertt̂(h1 , h2 , h3 VP V NP)tot̂(VP V NP, h2 , h3 VP, h1 ). The log-likelihood function is convex, and therefore EMconverges to global maximum Estimation of π and q is similar in flavorMain question: how do we get the latent state distributionsp(h f, VP) and p(h g, VP)?Spectral Learning for NLP60

Vector Representation of Inside and Outside TreesDesign functions Z and Y :Y maps any inside feature value f [d0 ] to a vector of length m.Z maps any outside feature value g [d] to a vector of length m.Convention: m is the number of hidden states under the L-PCFG.SNPVPVPDNthedogOutside tree o Z(g) [1, 0.4, 5.3, . . . , 72] VPsawhimInside tree t RmY (f ) [ 3, 17, 2, . . . , 3.5] RmZ and Y reduce the dimensionality of φ and ψ using CCASpectral Learning for NLP61

Identifying Latent State Distributions For each f [d], define:P0v(f ) dg 1 p(g f, VP)Z(g) E[Z(g) f, VP] v(f ) Rm is “the expected value of an outside tree(representation) given an inside tree (feature)”Spectral Learning for NLP62

Identifying Latent State Distributions For each f [d], define:P0v(f ) dg 1 p(g f, VP)Z(g) E[Z(g) f, VP] v(f ) Rm is “the expected value of an outside tree(representation) given an inside tree (feature)” By conditional independence:v(f ) mXp(h f, VP)w(h)h 1Rmwhere w(h) andPd0w(h) g 1 p(g h, VP)Z(g) E[Z(g) h, VP]. w(h) is “the expected value of an outside tree(representation) given a latent state”Spectral Learning for NLP62

Pivot Assumption PReminder: v(f ) mh 1 p(h f, VP)w(h) If we know w(h), we can find latent state distributions:I Given an inside tree (feature f ) and a node such as VP,compute v(f )I SolvemXarg min v(f ) p(h f, VP)w(h) 2p(h f,VP)h 1Assumption: For each latent state there is f [d] a “pivotfeature value” s.t.p(h f, VP) 1.Result of this: v(f ) w(h) for any pivot feature fSpectral Learning for NLP63

Identifying Latent State Distributions m pivot features {f1 , . . . , fm } such that v(fh ) w(h)Then, for all f [d]v(f ) mXp(h f, VP)v(fh )h 1 Therefore, we can identify p(h f, VP) for all f by solving:argSpectral Learning for NLPminp(h f,VP) v(f ) mXp(h f, VP)v(fh ) 2h 164

Identifying Pivot Features v(f ) are observable quantities, can be calculated from data Arora et al. (2012) showed how to find the pivot features Basic idea: find the corners of the convex hull spanned by the dfeaturesSpectral Learning for NLP65

Identifying Latent State DistributionsAlgorithm: Identify m pivot features f1 , . . . , fm by findingvertices of ConvexHull(v1 , . . . , vd ) (Arora et al., 2012) Solve for each f [d]:argmXmin v(f ) p(h f, VP)v(fh ) 2p(h f,VP)h 1Output:ILatent state distributions p(h f, VP) for any f [d]Can analogously get:ILatent state distributions p(h g, VP) for any g [d0 ] We managed to extract latent state probabilities from observeddata only!Spectral Learning for NLP66

Experiments - Language Modeling Saul and Pereira (1997):p(w2 w1 ) Xp(w2 h)p(h w1 ).hhw1w2This model is a specific case of L-PCFG Experimented with bi-gram modeling for two corpora: Browncorpus and Gigaword corpusSpectral Learning for NLP67

Results: perplexitymbigram Kneser-Neytrigram Kneser-NeyEMiterationspivotSpectral Learning for NLPBrown128 256408386388 36598426 597test415394364560NYT128 256271150284 2653532782 886test27915826771568

Results: perplexitymbigram Kneser-Neytrigram Kneser-NeyEMiterationspivotpivot EMiterationsBrown128 256408386388 36598426 597310 32711test415394364560357NYT128 256271150284 2653532782 886279 2921912test279158267715281 Initialize EM with pivot algorithm output EM converges in much fewer iterations Still consistent - called “two-step estimation” (Lehmann andCasella, 1998)Spectral Learning for NLP69

Results with EM (section 22 of Penn treebank)Performance with expectation-maximization (m 32): 88.56%Vanilla binarized PCFG maximum likelihood estimationperformance: 68.62%Performance with spectral algorithm (Cohen et al., 2013): 88.82%Spectral Learning for NLP70

Inside features usedConsider the VP node in the following tree:SNPVPDNVthecatsawNPDNthedogThe inside features consist of:IThe pairs (VP, V) and (VP, NP)IThe rule VP V NPIThe tree fragment (VP (V saw) NP)IThe tree fragment (VP V (NP D N))IThe pair of head part-of-speech tag with VP: (VP, V)Spectral Learning for NLP71

Outside features usedConsider the D node inthe following tree:SNPVPDNVthecatsawNPDNthedogThe outside features consist of:IThe fragmentsNPD ,NandVPVNPD SNPNVPVNPD IThe pair (D, NP) and triplet (D, NP, VP)IThe pair of head part-of-speech tag with D: (D, N)Spectral Learning for NLPN72

ResultsmEMiterationsSpectral(Cohen et al., 2013)PivotPivot EMiterations886.6940sec. 22162488.32 88.3530303288.5620sec. 6.8788.64286.4088.55285.8387.7688.03Again, EM converges in very few iterationsSpectral Learning for NLP73

ConclusionFormal guarantees:IStatistical consistencyINo problem of local maximaAdvantages over traditional spectral methods:INo negative probabilitiesIMore intuitive to understandSpectral Learning for NLP74

Things we did not talk aboutTheses algorithms can be kernelized (e.g. Song et al., 2010)Many other algorithms similar in flavor (see reading list)IRely on some decomposition of observable quantities to get ahandle

Latent-variable Models Latent-variable models are used in many areas of NLP, speech, etc.: I Hidden Markov Models I Latent-variable PCFGs I Naive Bayes for clustering I Lexical representations: Brown clustering, Saul and Pereira, etc. I Alignments in statistical machine translation I Topic modeling I etc. etc. The Expectation-maximization (EM) algorithm is generally used