Theoretical Guarantees
for Learning Weighted Automata
Borja BalleICGI Keynote — October 2016

Thanks To My Collaborators!

Mehryar
Mohri

Ariadna
Quattoni

XavierCarreras

PrakashPanangaden

Doina
PrecupOutline

1. The Complexity of PAC Learning Regular Languages

2. Empirical Risk Minimization for Regular Languages

3. Statistical Learning of Weighted Automata via Hankel Matrices

Outline

1. The Complexity of PAC Learning Regular Languages

2. Empirical Risk Minimization for Regular Languages

3. Statistical Learning of Weighted Automata via Hankel Matrices

Regular Inference (Informal Description)§ Unknown regular language L Ď Σ‹§With indicator function f : Σ‹ Ñ t0, 1u§ Given examples px1 , fpx1 qq, px2 , fpx2 qq, . . .
§§Finite or infinite(positive and negative) OR (only positive)§ Find a representation for L (eg. a DFA)§§

Using a reasonable amount of computation
After seeing a reasonable amount of examples

PAC Learning Regular Languages§ Concept class C of functions Σ‹ Ñ t0, 1u§

Eg. C “ DFAn all regular languages recognized by DFA with n states§ Hypothesis class H of representations for functions Σ‹ Ñ t0, 1u§§

Proper learning H “ C
Improper learning H ‰ CDefinition: PAC LearnerAn algorithm A such that for any f P C and any prob. dist. D on Σ‹ , andany accuracy ε and confidence δ, satisfies: given a large enough sample ofexamples S “ ppxi , fpxi qqq i.i.d. from D, the output hypothesis f̂ “ ApSq P
H satisfies Px„D rfpxq ‰ f̂pxqs ď ε with probability at least 1 ´ δ.
§ Large enough typically means polynomial of 1{ε, 1{δ, size of f
§ For any prob. dist. D on Σ‹ is called distribution-free learning

Note: see [De la Higuera, 2010] for other important formal learning models

Sample Complexity of PAC Learning DFA
Sample Complexity
The distribution-free sample complexity of PAC learning C “ DFAn ispolynomial in n and |Σ|Follows from:§ Any concept class C can be proper PAC-learned with:¯´§

VCpCq logp1{εq`logp1{δqε|S| “ O´§

|S| “ O´§

|S| “ O

VCpCq logp1{δqε[Vapnik, 1982]¯

VCpCq`logp1{δqε[Haussler et al., 1994]¯[Hanneke, 2016]§ VCpDFAn q “ Op|Σ|n log nq [Ishigami and Tani, 1993]

Generic Learning Algorithm:§ Upper bounds in [Vapnik, 1982, Hanneke, 2016] apply to consistentlearning algorithms§ A is consistent if for any sample S “ ppxi , fpxi qqq the hypothesisf̂ “ ApSq satisfies f̂pxi q “ fpxi q for all iComputational Complexity of PAC Learning DFA§ Proper PAC learning of DFA is equivalent to finding smallest

consistent DFA with S [Board and Pitt, 1992]§ Finding the smallest consistent DFA is NP-hard[Angluin, 1978, Gold, 1978]§ Approximating the smallest consistent DFA is NP-hard[Pitt and Warmuth, 1993, Chalermsook et al., 2014]§ Improper learning DFA is as hard as breaking RSA[Kearns and Valiant, 1994]§ Improper learning DFA is as hard as refuting random CSP[Daniely et al., 2014]

Is Worst-case Hardness Too Pessimistic?
Positive Results:§ Given characteristic sample, state-merging can find smallest

consistent DFA [Oncina and Garcı́a, 1992]§ PAC learning is possible under nice distributions adapted to target

language [Parekh and Honavar, 2001, Clark and Thollard, 2004]§ Random DFA under uniform distributions seem easy to learn[Lang, 1992, Angluin and Chen, 2015]§ And also lots of successful heuristics in practice: EDSM, SAT solvers,

etc.
Take Away:§ By giving up on distribution-free and focusing on nice distributions

efficient PAC learning is possible§ Almost all of these algorithms still focus on sample consistency§ Do we expect them to work well for practical applications?
§§

Probably yes for software engineering
Probably not for NLP, robotics, bioinformatics, ...

Outline

1. The Complexity of PAC Learning Regular Languages

2. Empirical Risk Minimization for Regular Languages

3. Statistical Learning of Weighted Automata via Hankel Matrices

Regular Inference as an Optimization Problem
Thought Experiment
Given input sample S “ ppxi , yi qq for i “ 1...100, would you rather:
1. classify all 100 examples correctly with 50 states, or
2. classify 95 examples correctly with 5 states?
Optimization Problems
1. Minimal consistent DFA
min |A|

APDFA

s.t. Apxi q “ yi @i P rms

2. Empirical risk minimization in DFAnm

1 ÿ
1rApxi q ‰ yi s
APDFA mi“1mins.t. |A| ď nStatistical Learning for Classification
Statistical Learning Setup§ D probability distribution over Σ‹ ˆ t`1, ´1u§ H hypothesis class of functions Σ‹ Ñ t`1, ´1u§ `01 the 0-1 loss function for y, ŷ P t`1, ´1u`01 pŷ, yq “

1 ´ signpŷyq“ 1rŷ “ ys2

Statistical Learning Goal
§ Find the minimizer of the average loss:f˚ “ argmin Epx,yq„D r`01 pfpxq, yqs “ argmin LD pf; `01 q
fPH

fPH

§ From a sample S “ ppxi , yi qq with m i.i.d. examples from Dm1 ÿEpx,yq„D r`01 pfpxq, yqs «`01 pfpxi q, yi qm i“1ERM and VC Theory
Empirical Risk Minimization (ERM)§ Given the sample S “ ppxi , yi qq return the hypothesism1 ÿf̂ “ argmin`01 pfpxi q, yi , q “ argmin L̂S pf; `01 q
m
fPH
fPH
i“1
Statistical Justification§ Generalization bound based on VC theory: with prob. at least 1 ´ δover S (e.g. see [Mohri et al., 2012])
˜c¸
VCpHq log m ` logp1{δq
LD pf; `01 q ď L̂S pf; `01 q`O@f P Hm§ In the case H “ DFAn :˜c
LD pA; `01 q ď L̂S pA; `01 q`O¸|Σ|n log n log m ` logp1{δqm@|A| ď nSources of Hardness in ERM for DFA

m

1 ÿ
min
`01 pApxi q, yi q
APDFA mi“1s.t. |A| ď n§ Non-convex loss: `01 pApxq, yq is not convex in Apxq because of sign
§ Combinatorial search space: search over DFA is search over labelled

directed graph with constraints§ Non-convex constraint: introducing |A| into the optimization is hard

Common Wisdom: Optimization tools that work better in practice deal
with differentiable and/or convex problems

Roadmap to a Tractable Surrogate§ Replace by `01 by a convex upped bound§ Make search space continuous: from DFA to WFA§ Identify convex constraints on WFA that can prevent overfitting

Writing DFA with Matrices and Vectors
a

b
a

q1

1

q2

0

0

1

b

A “ xα, β, tAσ uy
„
α“

1
0



„
β“

1
0



„
Aa “

1 0
1 0



Apaabq “ αJ Aa Aa Ab β “ 1

„
Ab “

0 1
0 1



Weighted Finite Automata (WFA)a, 1.2b, 2a, 3.2
b, 5
a, ´2
b, 0

q1

´1

q2

0.5

1.2

0

a, ´1
b, ´2

A “ xα, β, tAσ uy
„
α“

´1
0.5



„
β“

1.2
0

A : Σ‹ Ñ R



„
Aa “

1.2 ´1´2 3.2

„Ab “Apx1 ¨ ¨ ¨ xT q “ αJ Ax1 ¨ ¨ ¨ AxT β

2 ´2
0 5



ERM for WFA is Differentiablem

1 ÿ`pApxi q, yi q
APWFA mi“1mins.t. |A| “ nwith loss `pŷ, yq differentiable on first coordinate
Gradient Computation§ WFA A “ xα, β, tAσ uy, x P Σ‹ , y P R, can compute ∇A `pApxq, yq§ Example with x “ abca and weights in Aa :˘`
B`
pApxq, yq ¨ ∇Aa αJ Aa Ab Ac Aa β
Bŷ
´
¯
B`
J
J J
J J J
“
pApxq, yq ¨ αβJ AJ
a Ac Ab ` Ac Ab Aa αβ
Bŷ

∇Aa `pApxq, yq “§ Can use gradient descent to “solve” ERM for WFA
§ The optimization is highly non-convex, but its commonly done in RNN§ Since WFAn is infinite, what is a proper way to prevent overfitting?

Statistical Learning and Rademacher Complexity§ The risk of overfitting can be controlled with generalization bounds ofthe form: for any D, with prob. 1 ´ δ over S „ Dm

LD pf; `q ď L̂S pf; `q ` CpS, H, `q@f P H§ Rademacher complexity provides bounds for any H “ tf : Σ‹ Ñ Ru«
Rm pHq “ ES„Dm Eσ

ff
m
1 ÿ
i
sup
σi fpx q
where σi „ unifpt`1, ´1uq
fPH m i“1§ For a bounded Lipschitz loss ` with probability 1 ´ δ over S „ Dm(e.g. see [Mohri et al., 2012])
˜
LD pf; `q ď L̂S pf; `q ` O Rm pHq `c¸
logp1{δqm@f P HRademacher Complexity of WFA§ Given a pair of Hölder conjugate integers p, q (1{p ` 1{q “ 1), definea norm on WFA given by"*}A}p,q “ max }α}p , }β}q , max }Aa }qaPΣ

§ Let An Ă WFAn be the class of WFA with n states given by

An “ tA P WFAn | }A}p,q ď 1u
Theorem [Balle and Mohri, 2015b]
The Rademacher complexity of An is bounded by¸˜cLmn2 |Σ| logpmq
Rm pAn q “ O`,mmwhere Lm “ ES rmaxi |xi |s.

Learning WFA with Gradient Descent§ Solve the following ERM problem with (stochastic) projected gradientdescent:m

1 ÿ`pApxi q, yi q
APWFAn mi“1mins.t. }A}p,q ď R§ Control overfitting by tuning R (e.g. via cross-validation)§ Can equally solve classification (yi P t`1, ´1u) and regression(yi P R) with differentiable loss functions§ Risk of underfitting: unlikely that we will find the global optimum,

might get stuck in local optimum

Outline

1. The Complexity of PAC Learning Regular Languages

2. Empirical Risk Minimization for Regular Languages

3. Statistical Learning of Weighted Automata via Hankel Matrices

Hankel Matrices and Fliess’ Theorem‹‹

Given f : Σ‹ Ñ R define its Hankel matrix Hf P RΣ ˆΣ as


a

b

»
fpq fpaq
fpbq——
a — fpaq fpaaq fpabq——
b — fpbq fpbaq fpbbq
.. —
. —
—
—
p – ¨¨¨
¨¨¨
¨¨¨
..
.


¨¨¨

s

..
.
..
.
..
.
fppsq

¨¨¨

fi
ffi
ffi
ffi
ffi
ffi
ffi
ffi
ffi
ffi
ffi
fl

Theorem [Fliess, 1974]
The rank of Hf is finite if and only if f is computed by a WFA, in whichcase rankpHf q equals the number of states of a minimal WFA computing f

From Hankel to WFA
App1 ¨ ¨ ¨ pT s1 ¨ ¨ ¨ sT 1 q “ αJ Ap1 ¨ ¨ ¨ ApT As1 ¨ ¨ ¨ AsT 1 β
s

»
—
—
—
– ¨

p

¨

¨
¨
¨
fppsq
¨

fi

¨

»
¨
ffi — ¨ffi —ffi “ — ¨
¨ fl – ‚
¨

¨
¨
¨
‚
¨

¨
¨
¨
‚
¨

fi
»
¨
ffi
ffi –
¨
ffi
fl
¨

¨
¨
¨

‚
‚
‚

¨
¨
¨

fi
¨
¨ fl
¨

App1 ¨ ¨ ¨ pT as1 ¨ ¨ ¨ sT 1 q “ αJ Ap1 ¨ ¨ ¨ ApT Aa As1 ¨ ¨ ¨ AsT 1 β
s

»

p

—
—
—
– ¨

¨

¨
¨
¨
fppasq
¨

fi

¨

»
¨
ffi — ¨ffi —ffi “ — ¨
¨ fl – ‚
¨

¨
¨
¨
‚
¨

fi
¨
»
¨ ffi
‚
ffi
¨ ffi – ‚
fl
‚
‚
¨

‚
‚
‚

fi »
‚
¨
‚ fl – ¨
‚
¨

¨
¨
¨

‚
‚
‚

¨
¨
¨

fi
¨
¨ fl
¨

§ Algebraically: H “ PS and Ha “ PAa S, so we can learn by
Aa “ P` Ha S`§ This is the underlying principle behind query learning and spectral

learning for WFA [Balle and Mohri, 2015a]§ For more information, see our EMNLP’14 tutorial with A. Quattoni
and X. Carreras [Balle et al., 2014]

Learning with Hankel Matrices [Balle and Mohri, 2012]
Step 1: Learn a finite Hankel matrix over P ˆ S directly from data bysolving the convex ERMm1 ÿ`pHpxi q, yi q
m
PˆS
HPR
i“1

Ĥ “ argmin

s.t. H P Hankel

Step 2: Extract sub-blocks Ĥ , Ĥa from the Hankel matrix Ĥ
P Ď P Y pP ¨ ΣqĤ pp, sq “ Ĥpp, sq

p P P , s P S

Ĥa pp, sq “ Ĥppa, sq

p P P , s P S

Step 3: Learn a WFA from the Hankel matrix using SVD
Ĥ “ UDVJ
Âa “ UJ Ĥa VD´1

Controlling Overfitting with Hankel Matrices§ To prevent overfitting, control number of states of resulting WFA bym

1 ÿ`pHpxi q, yi q
m
PˆS
HPR
i“1

Ĥ “ argmin

s.t. H P Hankel, rankpHq ď n§ Since this is not convex, a usual surrogate is to use Schatten normsm1 ÿ`pHpxi q, yi q
m
PˆS
HPR
i“1

Ĥ “ argmin

s.t. H P Hankel, }H}S,p ď R

where }H}S,p “ }ps1 , . . . , sn q}p and s1 ě ¨ ¨ ¨ sn ą 0 are the singularvalues of H
§ These norms can be computed in polynomial time even for infinite

Hankel matrices [Balle et al., 2015]

Rademacher Complexity of Hankel Matrices
Given R ą 0 and p ě 1 define the class of infinite Hankel matrices
ˇ
)
!
‹
‹ ˇ
Hp “ H P RΣ ˆΣ ˇ H P Hankel, }H}S,p ď R
Theorem [Balle and Mohri, 2015b]
The Rademacher complexity of H2 is bounded by˙ˆR.
Rm pH2 q “ O ?
m
The Rademacher complexity of H1 is bounded by?
ˆ˙
R logpmq Wm
Rm pH1 q “ O
,
m
“
(‰
ř
ř
where Wm “ ES minsplitpSq max maxp i 1rpi “ ps, maxs i 1rsi “ ss .
Note: splitpSq contains all possible prefix-suffix splits xi “ pi si of all strings in S

Constrained vs. Regularized Optimization§ Constrained ERM with parameter R ą 0m

1 ÿ`pHpxi q, yi q
HPRPˆS mi“1mins.t. H P Hankel, }H}S,p ď R§ Regularized ERM with parameter λ ą 0m

1 ÿ`pHpxi q, yi q ` λ}H}S,p
HPRPˆS mi“1mins.t. H P Hankel§ Regularized versions can be easier to solve and λ easier to tune
§ For example, for H2 bounds informally say that for any H

ˆLD pH; `q ď L̂S pH; `q ` O}H}S,2?
m˙?
so choosing λ “ Op1{ mq would imply ERM minimizes a direct
upper bound on LD

Applications of Learning with Hankel Matrices§ Max-margin taggers [Quattoni et al., 2014]

Hamming Accuracy (test)

90
88
86
84
No Regularization
Avg. Perceptron
CRF
Spectral IO HMM
L2 Max Margin
Spectral Max Margin

82
80
78
500

1K

2K

5K

Training Samples§ Unsupervised transducers [Bailly et al., 2013b]§ Unsupervised WCFG [Bailly et al., 2013a]

10K

15K

Conclusion / Open Problems / Future Work§ It is possible to solve regular inference with machine learning,

focusing on the realistic statistical learning scenario, and still obtainmeaningful theoretical guarantees§ In practice works very well, but convex algorithms are not always

scalable: we need good implementations§ How to choose P and S from data in practice?
§ PAC learning of WFA for regression is still open
§ Theoretical link between finite and infinite Hankel matrices is stillweakReferences I
Angluin, D. (1978).
On the complexity of minimum inference of regular sets.
Information and Control, 39(3):337–350.
Angluin, D. and Chen, D. (2015).
Learning a random dfa from uniform strings and state information.
In International Conference on Algorithmic Learning Theory, pages 119–133.
Springer.
Bailly, R., Carreras, X., Luque, F., and Quattoni, A. (2013a).
Unsupervised spectral learning of WCFG as low-rank matrix completion.
In EMNLP.
Bailly, R., Carreras, X., and Quattoni, A. (2013b).
Unsupervised spectral learning of finite state transducers.
In NIPS.
Balle, B. and Mohri, M. (2012).
Spectral learning of general weighted automata via constrained matrix completion.
In NIPS.

References II
Balle, B. and Mohri, M. (2015a).
Learning weighted automata.
In Algebraic Informatics, pages 1–21. Springer.
Balle, B. and Mohri, M. (2015b).
On the rademacher complexity of weighted automata.
In Algorithmic Learning Theory, pages 179–193. Springer.
Balle, B., Panangaden, P., and Precup, D. (2015).
A canonical form for weighted automata and applications to approximate
minimization.
In LICS.
Balle, B., Quattoni, A., and Carreras, X. (2014).
Spectral Learning Techniques for Weighted Automata, Transducers, andGrammars.
http://www.lancaster.ac.uk/~deballep/emnlp14-tutorial/.

References III
Board, R. and Pitt, L. (1992).
On the necessity of occam algorithms.
Theoretical Computer Science, 100(1):157–184.
Chalermsook, P., Laekhanukit, B., and Nanongkai, D. (2014).
Pre-reduction graph products: Hardnesses of properly learning dfas andapproximating edp on dags.
In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposiumon, pages 444–453. IEEE.
Clark, A. and Thollard, F. (2004).
Partially distribution-free learning of regular languages from positive samples.
In Proceedings of the 20th international conference on Computational Linguistics,
page 85. Association for Computational Linguistics.
Daniely, A., Linial, N., and Shalev-Shwartz, S. (2014).
From average case complexity to improper learning complexity.
In Proceedings of the 46th Annual ACM Symposium on Theory of Computing,pages 441–448. ACM.

References IV
De la Higuera, C. (2010).
Grammatical inference: learning automata and grammars.
Cambridge University Press.
Fliess, M. (1974).
Matrices de Hankel.
Journal de Mathématiques Pures et Appliquées.
Gold, E. M. (1978).
Complexity of automaton identification from given data.
Information and control, 37(3):302–320.
Hanneke, S. (2016).
The optimal sample complexity of pac learning.
Journal of Machine Learning Research, 17(38):1–15.
Haussler, D., Littlestone, N., and Warmuth, M. K. (1994).
Predicting t0, 1u-functions on randomly drawn points.
Information and Computation, 115(2):248–292.

References V
Ishigami, Y. and Tani, S. (1993).
The vc-dimensions of finite automata with n states.
In Algorithmic Learning Theory, pages 328–341. Springer.
Kearns, M. and Valiant, L. (1994).
Cryptographic limitations on learning boolean formulae and finite automata.
Journal of the ACM (JACM), 41(1):67–95.
Lang, K. J. (1992).
Random dfa’s can be approximately learned from sparse uniform examples.
In Proceedings of the fifth annual workshop on Computational learning theory,
pages 45–52. ACM.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2012).
Foundations of machine learning.
MIT press.
Oncina, J. and Garcı́a, P. (1992).
Identifying regular languages in polynomial time.
Advances in Structural and Syntactic Pattern Recognition, 5(99-108):15–20.

References VI
Parekh, R. and Honavar, V. (2001).
Learning dfa from simple examples.
Machine Learning, 44(1-2):9–35.
Pitt, L. and Warmuth, M. K. (1993).
The minimum consistent dfa problem cannot be approximated within any
polynomial.
Journal of the ACM (JACM), 40(1):95–142.
Quattoni, A., Balle, B., Carreras, X., and Globerson, A. (2014).
Spectral regularization for max-margin sequence tagging.
In ICML.
Vapnik, V. (1982).
Estimation of dependencies based on empirical data.

Theoretical Guarantees
for Learning Weighted Automata
Borja BalleICGI Keynote — October 2016