A Provably Correct Learning Algorithm for Latent-Variable PCFGs

Shay Cohen; Michael Collins

A Provably Correct Learning Algorithm for Latent-Variable PCFGs

Shay Cohen, Michael Collins

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We introduce a provably correct learning algorithm for latent-variable PCFGs. The algorithm relies on two steps: first, the use of a matrix-decomposition algorithm applied to a co-occurrence matrix estimated from the parse trees in a training sample; second, the use of EM applied to a convex objective derived from the training samples in combination with the output from the matrix decomposition. Experiments on parsing and a language modeling problem show that the algorithm is efficient and effective in practice.

Original language	English
Title of host publication	Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics
Publisher	Association for Computational Linguistics
Pages	1052-1061
Number of pages	10
Publication status	Published - 2014

Access to Document

Cohen and Collins 2014 A provably correct learningAccepted author manuscript, 313 KB

http://aclweb.org/anthology/P14-1099

Cite this

@inproceedings{33689bce01c54ca2b9c60329de8baee3,

title = "A Provably Correct Learning Algorithm for Latent-Variable PCFGs",

abstract = "We introduce a provably correct learning algorithm for latent-variable PCFGs. The algorithm relies on two steps: first, the use of a matrix-decomposition algorithm applied to a co-occurrence matrix estimated from the parse trees in a training sample; second, the use of EM applied to a convex objective derived from the training samples in combination with the output from the matrix decomposition. Experiments on parsing and a language modeling problem show that the algorithm is efficient and effective in practice.",

author = "Shay Cohen and Michael Collins",

year = "2014",

language = "English",

pages = "1052--1061",

booktitle = "Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics",

publisher = "Association for Computational Linguistics",

}

TY - GEN

T1 - A Provably Correct Learning Algorithm for Latent-Variable PCFGs

AU - Cohen, Shay

AU - Collins, Michael

PY - 2014

Y1 - 2014

N2 - We introduce a provably correct learning algorithm for latent-variable PCFGs. The algorithm relies on two steps: first, the use of a matrix-decomposition algorithm applied to a co-occurrence matrix estimated from the parse trees in a training sample; second, the use of EM applied to a convex objective derived from the training samples in combination with the output from the matrix decomposition. Experiments on parsing and a language modeling problem show that the algorithm is efficient and effective in practice.

AB - We introduce a provably correct learning algorithm for latent-variable PCFGs. The algorithm relies on two steps: first, the use of a matrix-decomposition algorithm applied to a co-occurrence matrix estimated from the parse trees in a training sample; second, the use of EM applied to a convex objective derived from the training samples in combination with the output from the matrix decomposition. Experiments on parsing and a language modeling problem show that the algorithm is efficient and effective in practice.

M3 - Conference contribution

SP - 1052

EP - 1061

BT - Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics

PB - Association for Computational Linguistics

ER -

A Provably Correct Learning Algorithm for Latent-Variable PCFGs

Abstract

Access to Document

Fingerprint

Cite this