A Sober Look at Spectral Learning

Han Zhao
HAN . ZHAO @ UWATERLOO . CA
Pascal Poupart
PPOUPART @ UWATERLOO . CA
Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, CanadaAbstract
Spectral learning recently generated lots of excitement in machine learning, largely because
it is the first known method to produce consistent estimates (under suitable conditions) for several latent variable models. In contrast, maximum likelihood estimates may get trapped inlocal optima due to the non-convex nature ofthe likelihood function of latent variable models. In this paper, we do an empirical evaluationof spectral learning (SL) and expectation maximization (EM), which reveals an important gap
between the theory and the practice. First, SL often leads to negative probabilities. Second, EM
often yields better estimates than spectral learning and it does not seem to get stuck in local
optima. We discuss how the rank of the model
parameters and the amount of training data canyield negative probabilities. We also question thecommon belief that maximum likelihood estimators are necessarily inconsistent.

1. Introduction
Spectral Learning is a general approach that uses spectral decompositions (e.g., singular value decomposition andtensor decomposition) for parameter estimation based on
the method of moments (Hsu et al., 2012; Parikh & Xing,2011; Anandkumar et al., 2012a;c;b). Spectral learning
has generated a lot of excitement in recent years due toits performance guarantees in latent variable models. The
presence of discrete latent variables generally leads to a
non-concave log-likelihood function, which is problematic for maximum likelihood estimators. Spectral learning is the first known method to be consistent (under suitable conditions) for several latent variable models including mixtures of Gaussians (MoGs), hidden Markov models (HMMs) and latent Dirichlet allocation (LDA). Furthermore, finite sample bounds guarantee that the approach willfind nearly optimal parameters or make nearly optimal pre-dictions with high probability given a sufficient amount oftraining data (Hsu et al., 2012).
We report some experiments that suggest an important gap
between the theory and the practice. Despite its theoretical guarantees, spectral learning often generates negativeprobabilities. This is an important issue that has received
little attention so far. We show some empirical results thatsuggest that a poor choice of the rank of the model parameters and insufficient training data increase the likelihoodof negative probabilities. We also investigate how wellspectral learning performs in comparison to common approaches such as EM that do not enjoy the same theoretical guarantees. Interestingly, even though EM is subject
to local optima and spectral learning is not, EM often outperforms spectral learning. Contrary to the common belief,
we suggest that EM may be consistent in several settings.
We discuss two situations under the assumption that theobservation space is finite. When the true parameters are
identifiable, increasing the amount of data often leads toa unimodal (though still non-concave) likelihood function,
which explains why maximum likelihood estimators do not
suffer from local optima. When the true parameters areunidentifiable (i.e., several equivalent solutions), the likelihood function remains multimodal, but if all the peaks ofthe likelihood function are at equivalent solutions, maximum likelihood estimators do not suffer from local optima.
We also discuss two advantages of maximum likelihood estimators over spectral learning: a) maximum likelihood isa better objective to optimize than moment consistency andb) the data efficiency of maximum likelihood tends to behigher since it uses all empirical moments of the data (notjust a few low order moments).

2. Spectral Learning for HMMs
Consider an HMM described as follows. Let x1 , x2 , x3 , . . .
denote a sequence of discrete observations where xt ∈[n] = {1, . . . , n} is the observation at time step t, andh1 , h2 , h3 , . . . denotes a sequence of hidden states whereht ∈ [m] = {1, . . . , m} is the hidden state at timestep t. The parameters of an HMM are (π, T, O) whereπ ∈ Rm is the initial state distribution, T ∈ Rm×m is

A Sober Look at Spectral Learning

the transition matrix and O ∈ Rn×m is the observation
matrix. More specifically, we have Pr(h1 = i) = πi ,Pr(ht+1 = i|ht = j) = Tij and Pr(xt = i|ht = j) =Oij . Based on (π, T, O), we define an observable operator
Ax = T diag(Ox,1 , . . . , Ox,m ) ∈ Rm×m for each observation x ∈ [n]. The joint probability of an observation
sequence of length t can be computed based on these operators as follows:
Pr(x1 , . . . , xt ) = 1Tm Axt . . . Ax1 π(1)observation sequences of length 4. The large HMM has 50
hidden states, 100 observations and a test set of 10,000 observation sequences of length 50. Fig. 1a and Fig. 1d show
the normalized L1 error when estimating the probability ofthe test sequences as we vary the amount of training data
and the rank hyperparameter m. The normalized L1 error
is defined as follows:
Xc 1 , . . . , xt )| 1t
L1 =| Pr(x1 , . . . , xt ) − Pr(x(x1 ,...,xt )∈T

Hsu et al. (2012) proposed a spectral algorithm called
LearnHMM to estimate a transformed set of operators
based on some low order empirical moments of the data.
The following moment matrices are estimated from thedata:

where T is the set of test sequences. We also report theproportion of negative probabilities

P1 ∈ Rn ,[P1 ]i = Pr(x1 = i)P2,1 ∈ Rn×n ,[P2,1 ]ij = Pr(x2 = i, x1 = j)
P3,x,1 ∈ Rn×n , [P3,x,1 ]ij = Pr(x3 = i, x2 = x, x1 = j)computed by LearnHMM in Fig. 1b and Fig. 1e. Negative probabilities are an important problem as they occur
frequently. Increasing the amount of data and choosing amore accurate rank parameter tends to decrease the L1 error and the proportion of negative probabilities.

LearnHMM requires a matrix U ∈ Rn×m such that U T Ois invertible. It is often chosen to be the first m left singular vectors that preserve the range of O. The following
operators are then computed:b1= U T P1bT∞

= P1T (U T P2,1 )+Bx

= U T P3,x,1 (U T P2,1 )+ ∀x ∈ [n](2)If T and O are of rank m and π is element-wise positive, it
can be shown thatPr(x1 , . . . , xt ) = bT∞ Bxt . . . Bx1 b1
The classic parameters (π, O, T ) can also be recoveredfrom the operators (Hsu et al., 2012).
In practice, since we do not know the exact moments, weobtain approximate moment matrices Pb1 , Pb2,1 , Pb3,x,1 frombx . Hsu et al.
the data and approximate operators bb1 , bbT∞ , B(2012) proved that joint probability estimates are consistentin the sense thatXc 1 , . . . , xt )| = 0 (3)lim| Pr(x1 , . . . , xt ) − Pr(xN →∞x1 ,...,xt

where N is the sample size. They also showed that ∀ > 0,
the sample size needed to get an -bound on the estimate ispolynomial in t and m. Several extensions and variants ofthis approach have been proposed for many latent variable
models (Parikh et al., 2012; Parikh & Xing, 2011; Anandkumar et al., 2012a;c).

3. Negative Probabilities
We implemented LearnHMM and tested it on small andlarge synthetic discrete HMMs. The small HMM has 4 hidden states, 8 observations and the test set consists of 4096

NEG PROP =c 1 , . . . , xt ) < 0 | (x1 , . . . , xt ) ∈ T }||{Pr(x|T |Negative probabilities do not invalidate the theoreticalguarantees of spectral learning. They simply reflect thefact that the theoretical guarantees are expressed in termsof bounds on additive error (see Theorem 6 in Hsu et al.
(2012)). When the true probability is close to 0 and thebound is loose, it may guarantee that the estimated probability is in some interval that is partly negative. The problem of negative probabilities is well-known in the literature on observable operator models and was acknowledged
by Boots et al. (2011) who rounded up all negative outputs
to a number slightly above zero followed by normalization.
In some spectral learning algorithms such as Excess Correlation Analysis for latent Dirichlet allocation (Anandkumar et al., 2012a), the parameters are estimated up to asign. This means that an exact estimate of a distribution
will normally be all positive or all negative and the sign
can be flipped in the case of an entirely negative distribution. However, since the parameters are estimated approximately, the sign of the probabilities will often be mixed.
It is not clear anymore whether the sign should be flipped.
A simple heuristic consists of adding the probabilities ofall outcomes and if the sum is negative, then flip the signof all probabilities. After that, the negative probabilities
can be rounded up to a number slightly higher than 0 followed by normalization. Here, there is a risk that the signof the probabilities will be flipped when it should not. If
most of the mass is negative due to the approximate natureof spectral learning, then the sign should not be flipped.
Those heuristics will ensure that the final probabilities arepositive, but they may increase the additive error. Spectrallearning (with those heuristics) remains consistent in thelimit, but the finite sample bounds need to be revised (thisis an open problem).

A Sober Look at Spectral Learning
SmallSyn

SmallSyn

0.5
0.45
0.4
0.35

1

1.5

2

2.5

33.5

Training Size = 1000000

0.3
0.25
0.2
0.15
0.1
0.05

0.8
0.75
0.7
0.65
0.6
0.55
0.5

11.5

Rank Hyperparameter

22.5

3

3.5

0.45

401Rank Hyperparameter(a)(b)

LargeSyn

LargeSyn

1.1234Training Size

54x 10(c)LargeSyn, m = 50

Proportion of Negative Probabilities

0.5

1.08
1.06

Normalized L1 error

LearnHMM
EM

0.85

Training Size = 100000
Training Size = 500000

04

Training Size = 50000

0.35

1.04
1.02
10.98
0.96

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

0.94
0.92
0102030

4050

Rank Hyperparameter

LearnHMM
EM0.070.45
0.4

Normalized L1 errorNormalized L1 error

0.6
0.55

0.9
Training Size = 10000

Normalized L1 error

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

0.65

0.9

SmallSyn, m = 4

0.4

Proportion of Negative Probabilities

0.7

0.35
0.3
0.25
0.2
0.15
Training Size = 10000

0.1

0.06

0.05

0.04

0.03

Training Size = 50000

0.02

Training Size = 100000

0.05

Training Size = 500000
Training Size = 1000000

00102030

Rank Hyperparameter(d)(e)4050

0.010123

Training Size

456x 10(f)Figure 1. Results for LearnHMM on two data sets (Fig.1a,1b,1d,1e) and comparing LearnHMM with EM (Fig.1c,1f).

Can we modify spectral learning to ensure that all probabilities are non-negative? The root of the problem is thatspectral learning implicitly solves a system of non-linear
equations without restricting the space to non-negative solutions. Could we simply add additional constraints to ensure non-negativity? We conjecture that it will be NP-hard.
Consider the problem of matrix factorization (i.e., find matrices A and B such that C=AB). If the entries of A and B
may be any real number, then a solution can be found inpolynomial time by singular value decomposition. However, if we want A and B to be non-negative then thisbecomes a problem of non-negative matrix factorization,
which is NP-hard (Vavasis, 2009). Similarly, spectral learning finds operators (from which transition and observation
matrices can be recovered) by singular value decomposition in polynomial time. If we add non-negativity constraints for the resulting transition and observation matrices, we conjecture that the problem will become NP-hard.

4. Empirical Comparison with EM
We compared empirically spectral learning to expectation
maximization (EM) on synthetic HMMs. The theory suggests that spectral learning should perform better since it
is consistent while EM is subject to local optima, but theresults are mixed. On the small synthetic HMM (Fig. 1c),with the true rank and sufficient data, spectral learning outperforms EM, but on the large synthetic HMM (Fig. 1f),
EM outperforms spectral learning. The amount of training

data was the same for both problems. We suspect that theamount of training data was insufficient for spectral learning to estimate reasonable operators for the larger model.
Furthermore, since spectral learning inverts a matrix to recover a similarity transform of the observable operators, it
is unstable and sensitive to noise. We also noticed a large
amount of negative probabilities. In general, spectral learning is very sensitive to the amount of data and the rank parameter as discussed in the previous section.
We also note that spectral learning does not optimize any
desirable objective. Since it implicitly solves a non-linear
system of equations induced by moment matching, if themoments matrices are too approximate, the resulting operators may be far from those that produced the data. If
the system of equations is highly sensitive to perturbations,then spectral learning may yield terrible results. In contrast,
EM directly maximizes the likelihood of the data. So evenwhen there is little data it will find parameters that are likely
to generate the data. The main issue with small datasets for
EM is overfitting. We did not use regularization to mitigate
overfitting in this experiment.
Another difference between spectral learning and EM is theinformation from the data that is used in training. Spectral
learning does not use the raw training data. It uses only
the first few empirical moments, which can be viewed as
insufficient statistics. In contrast, EM trains with the raw
data and therefore implicitly takes into account all the empirical moments including the higher order moments thatspectral learning ignores.

A Sober Look at Spectral Learning

5. Local Optima& Berger, 1990). Hence the likelihood function converges
to a Dirac distribution too and we conjecture that EM isconsistent in this setting.

10 observations
20 observations
30 observations
40 observations
50 observations
60 observations
70 observations
80 observations
90 observations
100 observations(normalized) likelihood

4
3.5
3
2.5
2
1.5
1
0.5
0

0

0.2

0.4

0.6

0.8

1

θ

Figure 2. Unnormalized likelihood curves Pr(θ|data).

We were surprised by the fact that EM performed as wellas it did since it may get stuck in arbitrarily bad local
optima. While EM produced different results for different random restarts as shown by the error bars in Fig. 1cand 1f, the results were generally quite good and consistent. The variation for different random results can beexplained by (minor) local optima or different amountsof overfitting. To investigate this further we constructeda single-parameter HMM for which we can visualize thelikelihood function. This HMM has 2 states and 2 observations. We assume that the observation distribution
is known and fixed (Pr(xi |hi ) = 0.7 ∀i) while the transition distribution is symmetric with a single parameterθ = Pr(hi+1 = n|hi = n) ∀n, i indicating the probability
that the current state remains unchanged. The likelihood
function can be computed analytically for discrete latentvariable models since it consists of an unnormalized mixture of Dirichlets. However, this mixture has one Dirichlet component per joint assignment of the latent variables.
For a sequence of t time steps, this would yield an exponentially large mixture in t. However, when there is only
one parameter θ, several mixture components can be collapsed together and the number of different components
in the mixture grows quadratically in t. Figure 2 shows
the analytical likelihood function for data sequences of increasing length. Each curve is a mixture of Dirichlets corresponding to the likelihood function for observation sequences of different length. Since the likelihood functionsare (unnormalized) mixtures of Dirichlets, we expect to see
multimodal curves, but most of the curves in Fig. 2 are unimodal. This means that maximum likelihood estimatorssuch as EM will perform very well. The fact that mixturesof Dirichlets tend to form unimodal curves as we increase
the amount of data can be explained by the consistency ofBayesian learning (Casella & Berger, 1990). When we startwith a uniform prior, the posterior in Bayesian learning is
the likelihood function. Since Bayesian learning is consistent for discrete observation models, the posterior converges to a Dirac distribution in the limit as long as the true
parameters are identifiable (i.e., unique solution) (Casella

To test our conjecture that EM is consistent we did anotherexperiment with an HMM of 2 states, 2 observations and 4parameters. Fig. 3 shows the likelihood of the training data
for the solutions found by EM in comparison to the true parameters. Our conjecture would not hold if EM found solutions with lower likelihood than for the true parameters
because this would mean that it got stuck in a local optimum. However as the the amount of training data increases
EM consistently finds solutions with higher likelihood thanfor the true parameters and the variance of the likelihood
vanishes. This suggests that EM found solutions that are
all equivalent (i.e. no local optimum that is worse than theother optima). The fact that the likelihood is higher thanfor the true parameters simply indicates overfitting. Whilewe suspect that EM is consistent in some settings undersuitable conditions (that remain to be proven formally), wenote that EM is inconsistent for some continuous observation models such as HMMs with continuous observations
and mixture of Gaussians (MoGs). For MoGs, it is will
known that EM may converge to a mixture of a Dirac distribution centered at one data point with a widespread Gaussian that fits the rest of the data (Bishop, 2006). This singular solution has infinite data likelihood, but it does notcorrespond to the true parameters, confirming the inconsistency of EM.
Log−likelihood Comparison
0EM log−likelihood
True log−likelihood−20

Log−likelihood

54.5−40−60−80−100−120−140050100

150200Training Size

Figure 3. Log likelihood comparison.

6. Conclusion
Spectral learning is an exciting and promising line of research. In this work we showed that there is an important
gap between the theory and the practice. We highlighted
several open problems regarding negative probabilities andconjectured that EM may be consistent in some settings.

A Sober Look at Spectral Learning

References
Anandkumar, Anima, Foster, Dean P, and Hsu, Daniel. A
Spectral Algorithm for Latent Dirichlet Allocation. InNIPS, pp. 926—-934, 2012a.
Anandkumar, Anima, Ge, Rong, Hsu, Daniel, Kakade,Sham M, and Telgarsky, Matus. Tensor Decompositions
for Learning Latent Variable Models. In arXiv preprint
arXiv:1210.7559, pp. 1–55, 2012b.
Anandkumar, Animashree, Hsu, Daniel, and Kakade,Sham M. A Method of Moments for Mixture Models and Hidden Markov Models.
arXiv preprint
arXiv:1203.0683, 2012c.
Bishop, Christopher M. Pattern recognition and machinelearning, volume 1. springer New York, 2006.
Boots, Byron, Siddiqi, Sajid M, and Gordon, Geoffrey J.
Closing the learning-planning loop with predictive state
representations. The International Journal of Robotics
Research, 30(7):954–966, 2011.
Casella, George and Berger, Roger L. Statistical inference,
volume 70. Duxbury Press Belmont, CA, 1990.
Hsu, Daniel, Kakade, Sham M., and Zhang, Tong. A
spectral algorithm for learning Hidden Markov Models.
Journal of Computer and System Sciences, 78(5):1460–1480, September 2012.
Parikh, Ankur and Xing, Eric P. A Spectral Algorithm for
Latent Tree Graphical Models. In Proceedings of the28th International Conference on Machine Learning, pp.
1065–1072, 2011.
Parikh, Ankur, Teodoru, Gabi, Tech, Georgia, Ishteva,Mariya, and Xing, Eric P. A Spectral Algorithm for
Latent Junction Trees. arXiv preprint arXiv:1210.4884,
2012.
Vavasis, Stephen A. On the complexity of nonnegative matrix factorization. SIAM Journal on Optimization, 20(3):1364–1377, 2009.