BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Learning hierarchical structure: strong learning of PCFGs - Alexan
 der Clark\, King's College London
DTSTART:20180601T110000Z
DTEND:20180601T120000Z
UID:TALK104590@talks.cam.ac.uk
CONTACT:Andrew Caines
DESCRIPTION:A central problem in language acquisition and NLP is the acqui
 sition of hierarchically structured syntactic representations. The simples
 t model of this is strong learning of context-free grammars from strings: 
 where the learner is required to recover isomorphic labeled parse trees wh
 ile observing only unstructured strings of symbols. Recently developed alg
 orithms for learning context-free grammars from strings typically use a ra
 ther unrealistic learning model which only guarantees asymptotic weak conv
 ergence using membership queries (the ability to test whether a given stri
 ng is in the language or not). However the classes of languages that can b
 e learned are quite large. Probabilistic variants of these algorithms have
  also been developed with PAC style guarantees for some smaller classes.\n
 \nHere we convert the simplest of these algorithms -- a primal learning al
 gorithm called a 1-finite kernel learner -- into a practical probabilistic
  learning algorithm that can learn the structure of probabilistic context-
 free grammars from strings. This involves converting a logical notion of t
 he validity of a production in the grammar to its probabilistic equivalent
 . We combine this approach with some standard machine learning techniques:
  non-negative matrix factorisation\, and the Inside-Outside algorithm.\n\n
 We experiment using synthetic data restricting ourselves to CFGs that sati
 sfy three reasonable conditions: being in Chomsky normal form\; having man
 y more terminals (words) than nonterminals (syntactic categories) and not 
 being excessively ambiguous. We observe that on nearly all grammars that s
 atisfy these conditions the learner approaches the theoretically optimal p
 erformance using standard parsing metrics. This work suggests that syntact
 ic structure can be learned just from strings and more generally that the 
 unrealistic learning models used in recent theoretical work can be convert
 ed quite easily into practical algorithms.
LOCATION:FW26\, Computer Laboratory
END:VEVENT
END:VCALENDAR