A Sober Look at Spectral Learning
Han Zhao and Pascal Poupart{han.zhao, ppoupart}@uwaterloo.ca
David R. Cheriton School of Computer Science, University of Waterloo• SL suffers from negative probabilities.
• EM rarely gets stuck in local optima.
• EM often outperforms SL.

Our contribution: empirical evaluation• The choice of rank hyperparameter and theamount of training data greatly influences SL.
• Likelihood function becomes unimodal withincreased size of training data.

Background

First three order moments:• P1, where P1[i] = Pr(x1 = i).

SmallSyn LargeSyn# hidden states
450# observations
8100
test set size 4096
10,000length of test sequence450
Each column vector of transition matrix T and observation matrix O is drawn from a uniform Dirichlet distribution. The stationary distribution of T is
used as the initial distribution of the corresponding
HMM to generate synthetic observation sequences.

P3,x,1[ij] = Pr(x3 = i, x2 = x, x1 = j).
Compute the following operators:• b1 = U

TP1• bT∞ = P1T (U T P2,1)+• Bx = U T P3,x,1(U T P2,1)+, ∀x ∈ [n]where U is the thin left singular matrix of P2,1 suchthat U T O is invertible.
T
Joint probability: Pr(x1:t) = b∞Bxt · · · Bx1b1.
LearnHMM is shown by [1] to be consistent in joint
probability and admits finite sample bounds.

L1 =









































5
10 observations
20 observations
30 observations
40 observations
50 observations
60 observations70 observations
80 observations
90 observations
100 observations

4.5
4
3.5
3
2.5
2
1.5
1
0.5
00

x1:t∈T

SmallSyn| Pr(x1:t) − P̃r(x1:t)|

1.06

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.5

2

2.5

3

3.5

0.9

4010

20

30

40

0.65
0.6
0.55

Proportion of Negative Probabilities

Normalized L1 error

Normalized L1 error

11.5

22.533.50.030.02
0.50123Training Size(d)454x 100.01

0123

Training Size(e)456x 101001502004[1] D. Hsu, S. M. Kakade, and T. Zhang, “A spectral
algorithm for learning Hidden Markov Models,” Journalof Computer and System Sciences, vol. 78,
pp. 1460–1480, Sept. 2012.

LargeSyn

0.04

50

References

0.05

0.5

0.7

0.45

0.1

LargeSyn, m = 50

0.05

00.15

SmallSyn, m = 40.75−80

Training Size

0.2(c)

0.06−60−1400.25(b)0.8−40Training Size = 1000000

0.3(a)

LearnHMM
EM−20−120

Training Size = 500000

050

Training Size = 100000

Rank Hyperparameter

0.07

EM log−likelihood
True log−likelihood

Training Size = 50000

0.35

Rank Hyperparameter

0.85

1

Training Size = 10000

Rank Hyperparameter

LearnHMM
EM

0.8−1000.4

1.08

Normalized L1 error

Normalized L1 error

0.6(2)

SmallSyn

1.1

0.65

0.6

θ

(1)

LargeSyn

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

0.4

Log−likelihood Comparison

1/tX0.200.9

Observable operators:
Ax , T diag(Ox,1, . . . , Ox,m), ∀x ∈ [n].
Equivalent parametrization: H = hπ, Axi, ∀x ∈ [n].
Joint probability: Pr(x1:t) = 1T Axt · · · Ax1π.

HMM with 2 hidden states, 2 observations and 4parameters, EM v.s. true model parameter:

For LearnHMM, we also report the proportion of negative probabilities in test dataset.
|{P̃r(x1:t) < 0 | x1:t ∈ T }|NEG_PROP =|T |1Figure 1: Graphical model of HMM.

For LearnHMM and EM, we report the normalized L1 error of test sequence:,

Tij = Pr(st+1 = i|st = j).
• Observation matrix O ∈ Rn×m,
Oij = Pr(ot = i|st = j).
m• Initial distribution π ∈ R , πi = Pr(s1 = i).

Table 1: Synthetic datasets• P3,x,1, ∀x ∈ [n], where

0.7• Transition matrix T ∈ R

The likelihood function of a single-parameter HMM
with increased number of observations: H = hT =
θ 1−θ0.7 0.3,O =, π = (0.5, 0.5)i1−θ θ0.3 0.7• P2,1, where P2,1[ij] = Pr(x2 = i, x1 = j).

A Hidden Markov Model H = hT, O, πi:m×m

Two synthetic experiments to compare LearnHMM
and EM:(normalized) likelihood

Practice:

Local optima of EM

Log−likelihood

We do an empirical evaluation of spectral learning(SL) and expectation maximization (EM) for Hidden Markov Models (HMM) that reveals a gap between theory and practice:
Theory:• SL is consistent and admits finite sample bounds.
• EM subject to local optima problem due tonon-concave likelihoods.

Experiment

Spectral Learning (LearnHMM)

Proportion of Negative Probabilities

Introduction

0.45
0.4
0.35
0.3
0.25
0.20.15
Training Size = 10000

0.1

Training Size = 50000
Training Size = 100000

0.05

Training Size = 500000
Training Size = 1000000

00102030

Rank Hyperparameter(f)4050