A Sober Look at Spectral Learning
Han Zhao and Pascal Poupart

June 17, 2014

1 / 69

Spectral Learning
What is spectral learning?
I New methods in machine learning to tackle mixture models

and graphical models with latent variables.

2 / 69

Spectral Learning
What is spectral learning?
I New methods in machine learning to tackle mixture models

and graphical models with latent variables.
I Dates back to Karl Pearson’s method of moments approach tosolve mixture of Gaussians.

3 / 69

Spectral Learning
What is spectral learning?
I New methods in machine learning to tackle mixture models

and graphical models with latent variables.
I Dates back to Karl Pearson’s method of moments approach tosolve mixture of Gaussians.
I An alternative to the principle of maximum likelihood

estimation and Bayesian inference.

4 / 69

Spectral Learning
What is spectral learning?
I New methods in machine learning to tackle mixture models

and graphical models with latent variables.
I Dates back to Karl Pearson’s method of moments approach tosolve mixture of Gaussians.
I An alternative to the principle of maximum likelihood

estimation and Bayesian inference.
I Been widely applied to various models, including Hidden

Markov Models [1, 2], mixture of Gaussians [3], Topic
Models [4, 5, 6] and latent junction trees [7, 8], etc.

5 / 69

Spectral Learning
What is spectral learning?
I New methods in machine learning to tackle mixture models

and graphical models with latent variables.
I Dates back to Karl Pearson’s method of moments approach tosolve mixture of Gaussians.
I An alternative to the principle of maximum likelihood

estimation and Bayesian inference.
I Been widely applied to various models, including Hidden

Markov Models [1, 2], mixture of Gaussians [3], Topic
Models [4, 5, 6] and latent junction trees [7, 8], etc.
Today I will focus on spectral algorithm for Hidden Markov Models.

6 / 69HMM

Hidden Markov ModelI A discrete time stochastic process.
I Satisfies Markovian property.
I The state of the system at each time step is hidden, only theobservation of the system is visible.

7 / 69HMM

HMM can be defined as a triple hT , O, πi:
I Transition matrix T ∈ Rm×m , Tij = Pr(st+1 = i | st = j).
I Observation matrix O ∈ Rn×m , Oij = Pr(ot = i | st = j).
I Initial distribution π ∈ Rm , πi = Pr(s1 = i).

8 / 69HMM
Given an HMM H = hT , O, πi, we are interested in two inference
problems:

9 / 69HMM
Given an HMM H = hT , O, πi, we are interested in two inference
problems:
1. Marginal Inference (Estimation problem). Computing themarginal probability
X
X
Pr(o1:t ) =Pr (o1:t , s1:t ) =Pr(s1:t ) Pr(o1:t |s1:t )
s1:t

s1:t

10 / 69

HMM
Given an HMM H = hT , O, πi, we are interested in two inference
problems:
1. Marginal Inference (Estimation problem). Computing themarginal probability
X
X
Pr(o1:t ) =Pr (o1:t , s1:t ) =Pr(s1:t ) Pr(o1:t |s1:t )
s1:t

s1:t

2. MAP Inference (Decoding problem). Computing the sequence∗ maximizing the posterior probabilitys1:t∗= arg max Pr(s1:t |o1:t )
s1:t
s1:t

11 / 69

HMM
Given an HMM H = hT , O, πi, we are interested in two inference
problems:
1. Marginal Inference (Estimation problem). Computing themarginal probability
X
X
Pr(o1:t ) =Pr (o1:t , s1:t ) =Pr(s1:t ) Pr(o1:t |s1:t )
s1:t

s1:t

Dynamic Programming !
2. MAP Inference (Decoding problem). Computing the sequence∗ maximizing the posterior probabilitys1:t∗= arg max Pr(s1:t |o1:t )
s1:t
s1:t

12 / 69

HMM
Given an HMM H = hT , O, πi, we are interested in two inference
problems:
1. Marginal Inference (Estimation problem). Computing themarginal probability
X
X
Pr(o1:t ) =Pr (o1:t , s1:t ) =Pr(s1:t ) Pr(o1:t |s1:t )
s1:t

s1:t

Dynamic Programming !
2. MAP Inference (Decoding problem). Computing the sequence∗ maximizing the posterior probabilitys1:t∗= arg max Pr(s1:t |o1:t )
s1:t
s1:t

Viterbi Algorithm !

13 / 69

HMM
Given an HMM H = hT , O, πi, we are interested in two inference
problems:
1. Marginal Inference (Estimation problem). Computing themarginal probability
X
X
Pr(o1:t ) =Pr (o1:t , s1:t ) =Pr(s1:t ) Pr(o1:t |s1:t )
s1:t

s1:t

Dynamic Programming !
2. MAP Inference (Decoding problem). Computing the sequence∗ maximizing the posterior probabilitys1:t∗= arg max Pr(s1:t |o1:t )
s1:t
s1:t

Viterbi Algorithm !
What about the learning problem?
14 / 69

HMM Reparametrization
Let H = hT , O, πi be an HMM, define the following observable
operators:
Ax , T diag(Ox,1 , . . . , Ox,m ),∀x ∈ [n]H = hπ, Ax i, ∀x ∈ [n] is an equivalent parameterization of HMM.

15 / 69

HMM Reparametrization
Let H = hT , O, πi be an HMM, define the following observable
operators:
Ax , T diag(Ox,1 , . . . , Ox,m ),∀x ∈ [n]H = hπ, Ax i, ∀x ∈ [n] is an equivalent parameterization of HMM.

16 / 69

HMM Reparametrization
Let H = hT , O, πi be an HMM, define the following observable
operators:
Ax , T diag(Ox,1 , . . . , Ox,m ),∀x ∈ [n]H = hπ, Ax i, ∀x ∈ [n] is an equivalent parameterization of HMM.

Ax [i, j] = Pr(st+1 = i|st = j) × Pr(ot = x|st = j) = Pr(st+1 =i, ot = x|st = j).
17 / 69

HMM Reparametrization
We can express the marginal probability in terms of observable
operators:
X
Pr(o1:t , s1:t+1 )Pr(o1:t ) =s1:t+118 / 69

HMM Reparametrization
We can express the marginal probability in terms of observable
operators:
X
Pr(o1:t , s1:t+1 )Pr(o1:t ) =s1:t+1=X[Pr(st+1 |st ) Pr(ot |st )] · · · [Pr(s2 |s1 ) Pr(o1 |s1 )] Pr(s1 )

s1:t+119 / 69

HMM Reparametrization
We can express the marginal probability in terms of observable
operators:
X
Pr(o1:t , s1:t+1 )Pr(o1:t ) =s1:t+1=X[Pr(st+1 |st ) Pr(ot |st )] · · · [Pr(s2 |s1 ) Pr(o1 |s1 )] Pr(s1 )

s1:t+1=X

Aot [st+1 , st ] · · · Ao1 [s2 , s1 ]πs1s1:t+120 / 69

HMM Reparametrization
We can express the marginal probability in terms of observable
operators:
X
Pr(o1:t , s1:t+1 )Pr(o1:t ) =s1:t+1=X[Pr(st+1 |st ) Pr(ot |st )] · · · [Pr(s2 |s1 ) Pr(o1 |s1 )] Pr(s1 )

s1:t+1=X

Aot [st+1 , st ] · · · Ao1 [s2 , s1 ]πs1s1:t+1= 1T Aot · · · Ao1 π

21 / 69

HMM Reparametrization
We can express the marginal probability in terms of observable
operators:
X
Pr(o1:t , s1:t+1 )Pr(o1:t ) =s1:t+1=X[Pr(st+1 |st ) Pr(ot |st )] · · · [Pr(s2 |s1 ) Pr(o1 |s1 )] Pr(s1 )

s1:t+1=X

Aot [st+1 , st ] · · · Ao1 [s2 , s1 ]πs1s1:t+1= 1T Aot · · · Ao1 π
Goal of Learning: Estimate the observable operators from sequenceof observations.

22 / 69

Spectral Learning for HMM [1]Assumption 1: π > 0 element-wise, and T and O are full rank
(rank(T ) = rank(O) = m). Define the first three order momentsof the observations:
P1 [i] = Pr(x1 ) = i
P2,1 [i, j] = Pr(x2 = i, x1 = j)
P3,x,1 [i, j] = Pr(x3 = i, x2 = x, x1 = j), ∀x ∈ [n]23 / 69

Spectral Learning for HMM [1]Assumption 1: π > 0 element-wise, and T and O are full rank
(rank(T ) = rank(O) = m). Define the first three order momentsof the observations:
P1 [i] = Pr(x1 ) = i
P2,1 [i, j] = Pr(x2 = i, x1 = j)
P3,x,1 [i, j] = Pr(x3 = i, x2 = x, x1 = j), ∀x ∈ [n]Let U ∈ Rn×m be the left singular matrix of P2,1 , define thefollowing observable operators:
b 1 = U T P1
Tb∞ = (P2,1U)+ P1

Bx = (U T P3,x,1 )(U T P2,1 )+ ,∀x ∈ [n]where M + denotes the Moore-Penrose pseudoinverse of matrix M.
24 / 69

Spectral Learning for HMM [1]Theorem (Observable HMM Representation [1])Assume the HMM obeys assumption 1, then
1. b1 = (U T O)π
T = 1T (U T O)−1
2. b∞

3. Bx = (U T O)Ax (U T O)−1∀x ∈ [n]T B ···B b
4. Pr(o1:t ) = b∞xt
x1 1

25 / 69

Spectral Learning for HMM [1]Theorem (Observable HMM Representation [1])Assume the HMM obeys assumption 1, then
1. b1 = (U T O)π
T = 1T (U T O)−1
2. b∞

3. Bx = (U T O)Ax (U T O)−1∀x ∈ [n]T B ···B b
4. Pr(o1:t ) = b∞xt
x1 1

b1 , b∞ and Bx only depend on first three order moments ofobservations, free of hidden states !

26 / 69

Spectral Learning for HMM [1]Main result of Spectral Learning algorithm for HMM:

Theorem (Sample Complexity)
There exists a constant C > 0 such that the following holds. Pickany 0 < , η < 1 and t ≥ 1. Assume the HMM obeys assumption
1, andm · log(1/)m · n0 () · log(1/)t2+N≥C· 2 ·σm (O)2 σm (P2,1 )4
σm (O)2 σm (P2,1 )2With probability at least 1 − η, the model returned by the spectral
learning algorithm for HMM satisfies
Xb 1:t )| ≤ | Pr(x1:t ) − Pr(xx1 ,...,xt

where n0 () = O(1/(1−s) ), s > 1 a constant.
27 / 69

Compared with EM

Expectation-Maximization [9]:I Local search heuristic algorithm based on the principle ofMaximum Likelihood Estimation

For a given t ≥ 1, and 0 < , η < 1, spectral learning algorithm:

28 / 69

Compared with EM

Expectation-Maximization [9]:I Local search heuristic algorithm based on the principle ofMaximum Likelihood Estimation
I Local optima problem.

For a given t ≥ 1, and 0 < , η < 1, spectral learning algorithm:

29 / 69

Compared with EM

Expectation-Maximization [9]:I Local search heuristic algorithm based on the principle ofMaximum Likelihood Estimation
I Local optima problem.
I No consistency guarantees.

For a given t ≥ 1, and 0 < , η < 1, spectral learning algorithm:

30 / 69

Compared with EM

Expectation-Maximization [9]:I Local search heuristic algorithm based on the principle ofMaximum Likelihood Estimation
I Local optima problem.
I No consistency guarantees.

For a given t ≥ 1, and 0 < , η < 1, spectral learning algorithm:
I A finite sample complexity to be consistent in terms of L1

error on marginal probability.

31 / 69

Compared with EM

Expectation-Maximization [9]:I Local search heuristic algorithm based on the principle ofMaximum Likelihood Estimation
I Local optima problem.
I No consistency guarantees.

For a given t ≥ 1, and 0 < , η < 1, spectral learning algorithm:
I A finite sample complexity to be consistent in terms of L1

error on marginal probability.
I No local optima since it only solves an SVD without any local

search.

32 / 69EM v.s. Spectral algorithm
Two synthetic experiments:# states# observations
test set size
length of test sequence

SmallSyn
4
8
4096
4

LargeSyn
50
100
10,00050

Measure: normalized L1 prediction error on test data set
X
b 1:t )| 1t
L1 =| Pr(x1:t ) − Pr(xx1:t ∈T

where T is the test set.

33 / 69EM v.s. Spectral algorithm
SmallSyn

LargeSyn
1.1

0.7
Training Size = 10000
Training Size = 50000
Training Size = 100000
Training Size = 500000
Training Size = 1000000

0.6

1.06

Normalized L1 error

Normalized L1 error

0.65

1.08

0.55
0.5
0.45
0.4

1.04
1.02
1
0.98
0.96

Training Size = 10000
Training Size = 50000
Training Size = 100000
Training Size = 500000
Training Size = 1000000

0.94
0.35

0.92
1

1.5

2

2.5

3

3.5

0.9

4

0

10

20

30

Rank Hyperparameter

Rank Hyperparameter

SmallSyn, m = 4

LargeSyn, m = 50

40

50

0.9
LearnHMM
EM

LearnHMM
EM

0.07

0.8

Normalized L1 error

Normalized L1 error

0.85

0.75
0.7
0.65
0.6
0.55

0.06

0.05

0.04

0.03

0.02
0.5
0.45

0

1

2

3

Training Size

4

5
4

x 10

0.01

0

1

2

3

Training Size

4

5
6

x 10

34 / 69EM v.s. Spectral algorithm
Negative probability problem with spectral learning algorithm:
I Size of training data.

35 / 69EM v.s. Spectral algorithm
Negative probability problem with spectral learning algorithm:
I Size of training data.
I Estimation of rank hyperparameter.

36 / 69EM v.s. Spectral algorithm
Negative probability problem with spectral learning algorithm:
I Size of training data.
I Estimation of rank hyperparameter.
I Length of test sequence.

37 / 69EM v.s. Spectral algorithm
Negative probability problem with spectral learning algorithm:
I Size of training data.
I Estimation of rank hyperparameter.
I Length of test sequence.
Proportion of negative probabilities:
b 1:t ) < 0 | x1:t ∈ T }||{Pr(x|T |NEG PROP =SmallSyn

LargeSyn
0.5

Proportion of Negative Probabilities

Proportion of Negative Probabilities

0.4
Training Size = 10000
Training Size = 50000

0.35

Training Size = 100000
Training Size = 500000
Training Size = 1000000

0.3
0.25
0.2
0.15
0.1
0.05
0

1

1.5

2

2.5

3

Rank Hyperparameter

3.5

4

0.45
0.4
0.35
0.3
0.25
0.2
0.15
Training Size = 10000

0.1

Training Size = 50000
Training Size = 100000

0.05

Training Size = 500000
Training Size = 1000000

0

0

10

20

30

40

50

Rank Hyperparameter

38 / 69

Compared with EM
Why EM succeeds in practice?
If the log-likelihood function of model parameter tends toconcave/quasi-concave when the sample size goes to infinity ?

39 / 69

Compared with EM
Why EM succeeds in practice?
If the log-likelihood function of model parameter tends toconcave/quasi-concave when the sample size goes to infinity ?
1. Local search algorithms, for example, EM algorithm in ourcase, will converge to global optima, hence obtain the
maximum likelihood estimator [10].

40 / 69

Compared with EM
Why EM succeeds in practice?
If the log-likelihood function of model parameter tends toconcave/quasi-concave when the sample size goes to infinity ?
1. Local search algorithms, for example, EM algorithm in ourcase, will converge to global optima, hence obtain the
maximum likelihood estimator [10].
2. Consistency. Sequence of MLE converges in probability to thetrue model parameter (suppose the model is identifiable byparameter) [11].

41 / 69

Compared with EM
Why EM succeeds in practice?
If the log-likelihood function of model parameter tends toconcave/quasi-concave when the sample size goes to infinity ?
1. Local search algorithms, for example, EM algorithm in ourcase, will converge to global optima, hence obtain the
maximum likelihood estimator [10].
2. Consistency. Sequence of MLE converges in probability to thetrue model parameter (suppose the model is identifiable byparameter) [11].
3. Asymptotic normality. The distribution of MLE tends to be a
Gaussian distribution with mean the true parameter andcovariance matrix equal to the inverse the Fisher information
matrix, i.e., more and more concentrated [11].

42 / 69

Compared with EM
Why EM succeeds in practice?
If the log-likelihood function of model parameter tends toconcave/quasi-concave when the sample size goes to infinity ?
1. Local search algorithms, for example, EM algorithm in ourcase, will converge to global optima, hence obtain the
maximum likelihood estimator [10].
2. Consistency. Sequence of MLE converges in probability to thetrue model parameter (suppose the model is identifiable byparameter) [11].
3. Asymptotic normality. The distribution of MLE tends to be a
Gaussian distribution with mean the true parameter andcovariance matrix equal to the inverse the Fisher information
matrix, i.e., more and more concentrated [11].
4. Most statistical efficient consistent estimator of model
parameter [11].
43 / 69

Synthetic Experiment

Is our conjecture true in HMM? An HMM with one single
parameter for visualization:




θ
1−θ
0.7 0.3
H = hT =,O =, π = (0.5, 0.5)i1−θθ
0.3 0.7
Beta distribution with uniform distribution as prior.
Exact Bayesian updating with more and more observations.

44 / 69

Synthetic Experiment
1.3
10 observations
1.2(normalized) likelihood

1.1

1

0.9

0.8

0.7

0.6

0.5

0.4

0

0.1

0.2

0.3

0.4

0.5

θ

0.6

0.7

0.8

0.9

1
45 / 69

Synthetic Experiment2
10 observations
20 observations
1.8(normalized) likelihood

1.6

1.4

1.2

1

0.8

0.6

0.4

0

0.1

0.2

0.3

0.4

0.5

θ

0.6

0.7

0.8

0.9

1
46 / 69

Synthetic Experiment2
10 observations
20 observations
30 observations

1.8(normalized) likelihood

1.6

1.4

1.2

1

0.8

0.6

0.4

0.2

0

0

0.1

0.2

0.3

0.4

0.5

θ

0.6

0.7

0.8

0.9

1
47 / 69

Synthetic Experiment2
10 observations
20 observations
30 observations
40 observations

1.8(normalized) likelihood

1.6

1.4

1.2

1

0.8

0.6

0.4

0.2

0

0

0.1

0.2

0.3

0.4

0.5

θ

0.6

0.7

0.8

0.9

1
48 / 69

Synthetic Experiment3
10 observations
20 observations
30 observations
40 observations
50 observations(normalized) likelihood

2.5

2

1.5

1

0.5

0

0

0.1

0.2

0.3

0.4

0.5

θ

0.6

0.7

0.8

0.9

1
49 / 69

Synthetic Experiment3
10 observations
20 observations
30 observations
40 observations
50 observations
60 observations(normalized) likelihood

2.5

2

1.5

1

0.5

0

0

0.1

0.2

0.3

0.4

0.5

θ

0.6

0.7

0.8

0.9

1
50 / 69

Synthetic Experiment3
10 observations
20 observations
30 observations
40 observations
50 observations
60 observations
70 observations(normalized) likelihood

2.5

2

1.5

1

0.5

0

0

0.1

0.2

0.3

0.4

0.5

θ

0.6

0.7

0.8

0.9

1
51 / 69

Synthetic Experiment
4.5
10 observations
20 observations
30 observations
40 observations
50 observations
60 observations
70 observations
80 observations

4(normalized) likelihood

3.5

3

2.5

2

1.5

1

0.5

0

0

0.1

0.2

0.3

0.4

0.5

θ

0.6

0.7

0.8

0.9

1
52 / 69

Synthetic Experiment
5
10 observations
20 observations
30 observations
40 observations
50 observations
60 observations
70 observations
80 observations
90 observations

4.5(normalized) likelihood

4

3.5

3

2.5

2

1.5

1

0.5

0

0

0.1

0.2

0.3

0.4

0.5

θ

0.6

0.7

0.8

0.9

1
53 / 69

Synthetic Experiment
5
10 observations
20 observations
30 observations
40 observations
50 observations
60 observations
70 observations
80 observations
90 observations
100 observations

4.5(normalized) likelihood

4

3.5

3

2.5

2

1.5

1

0.5

0

0

0.1

0.2

0.3

0.4

0.5

θ

0.6

0.7

0.8

0.9

1
54 / 69

Synthetic Experiment
Another small synthetic experiment: HMM with 2 states, 2
observations and 4 free parameters.

55 / 69

Synthetic Experiment
Another small synthetic experiment: HMM with 2 states, 2
observations and 4 free parameters.
Log−likelihood Comparison0
EM log−likelihood
True log−likelihood

Log−likelihood

−20

−40

−60

−80

−100

−120

−140

0

50

100

150

200

Training Size
56 / 69

Conclusions

Spectral learning for HMM
Pros:
1. Additive L1 error bound with finite sample complexity.
Cons:

57 / 69

Conclusions

Spectral learning for HMM
Pros:
1. Additive L1 error bound with finite sample complexity.
2. No local optima.
Cons:58 / 69

Conclusions

Spectral learning for HMM
Pros:
1. Additive L1 error bound with finite sample complexity.
2. No local optima.
Cons:
1. Negative probability.

59 / 69

Conclusions

Spectral learning for HMM
Pros:
1. Additive L1 error bound with finite sample complexity.
2. No local optima.
Cons:
1. Negative probability.
2. Not most statistically efficient.

60 / 69

Conclusions

Spectral learning for HMM
Pros:
1. Additive L1 error bound with finite sample complexity.
2. No local optima.
Cons:
1. Negative probability.
2. Not most statistically efficient.
3. Slow to converge.

61 / 69

Conclusions

EM for HMM
Pros:
1. Fast to converge.

Cons:62 / 69

Conclusions

EM for HMM
Pros:
1. Fast to converge.
2. Statistically efficient.
Cons:63 / 69

Conclusions

EM for HMM
Pros:
1. Fast to converge.
2. Statistically efficient.
3. Optimization based approach.
Cons:

64 / 69

Conclusions

EM for HMM
Pros:
1. Fast to converge.
2. Statistically efficient.
3. Optimization based approach.
Cons:
1. Local search heuristics, no provable guarantee for global
optima.

65 / 69

Conclusions

EM for HMM
Pros:
1. Fast to converge.
2. Statistically efficient.
3. Optimization based approach.
Cons:
1. Local search heuristics, no provable guarantee for global
optima.
2. Stuck in local optima for non-convex optimization.

66 / 69

Reference I
D. Hsu, S. M. Kakade, and T. Zhang, “A spectral algorithm
for learning Hidden Markov Models,” Journal of Computer and
System Sciences, vol. 78, pp. 1460–1480, Sept. 2012.
A. Anandkumar, D. Hsu, and S. M. Kakade, “A Method ofMoments for Mixture Models and Hidden Markov Models,”arXiv preprint arXiv:1203.0683, 2012.
D. Hsu and S. M. Kakade, “Learning mixtures of sphericalgaussians: moment methods and spectral decompositions,” inProceedings of the 4th conference on Innovations in
Theoretical Computer Science, pp. 11–20, ACM, 2013.
A. Anandkumar, D. P. Foster, and D. Hsu, “A Spectral
Algorithm for Latent Dirichlet Allocation,” in NIPS,
pp. 926—-934, 2012.
67 / 69

Reference II
A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and
M. Telgarsky, “Tensor Decompositions for Learning Latent
Variable Models,” in arXiv preprint arXiv:1210.7559, pp. 1–55,
2012.
S. Arora, R. Ge, Y. Halpern, D. Mimno, A. Moitra, D. Sontag,
Y. Wu, and M. Zhu, “A practical algorithm for topic modelingwith provable guarantees,” arXiv preprint arXiv:1212.4777,
2012.
A. Parikh, G. Teodoru, G. Tech, M. Ishteva, and E. P. Xing,“A Spectral Algorithm for Latent Junction Trees,” arXiv
preprint arXiv:1210.4884, 2012.
A. Parikh and E. P. Xing, “A Spectral Algorithm for Latent
Tree Graphical Models,” in Proceedings of the 28th
International Conference on Machine Learning, pp. 1065–1072,
2011.
68 / 69

Reference III

L. Rabiner, “A tutorial on hidden markov models and selected
applications in speech recognition,” Proceedings of the IEEE,
vol. 77, no. 2, pp. 257–286, 1989.
S. P. Boyd and L. Vandenberghe, Convex optimization.
Cambridge university press, 2004.
G. Casella and R. L. Berger, Statistical inference, vol. 70.
Duxbury Press Belmont, CA, 1990.

69 / 69