Spectral learning of latent-variable PCFGs: algorithms and sample complexity

Shay B. Cohen, Karl Stratos, Michael Collins, Dean P. Foster, Lyle H. Ungar

Abstract

We introduce a spectral learning algorithm for latent-variable PCFGs (Matsuzaki et al., 2005; Petrov et al., 2006). Under a separability (singular value) condition, we prove that the method provides statistically consistent parameter estimates. Our result rests on three theorems: the first gives a tensor form of the inside-outside algorithm for PCFGs; the second shows that the required tensors can be estimated directly from training examples where hidden-variable values are missing; the third gives a PAC-style convergence bound for the estimation method.
BibTeX
@article{cohen2014spectral,
  author = {Shay B. Cohen and Karl Stratos and Michael Collins and Dean P. Foster and Lyle H. Ungar},
  title = {{Spectral learning of latent-variable PCFGs: algorithms and sample complexity}},
  journal = {J. Mach. Learn. Res.},
  year = {2014},
}

Loading related content...

Figure