Default Deck - GitHub Pages

Default Deck - GitHub Pages

Neural Graphical Models over Strings for Principal Parts Morphological Paradigm Completion Ryan Cotterell, John Sylak-Glassman, and Christo Kirov Co-Authors Ryan Cotterell John SylakGlassman

Problem Overview Morphological Paradigm Completion Morphological Paradigms breche brach brichst

brachst brechen brachen gebracht Morphological Paradigms

Paradigm Completion ? brach ? brachst

brechen ? ? Question: can we generate morphologically related words? Why this matters!

Inflection generation useful for: Dictionary/Corpus Expansion Parsing (e.g., Tsarfaty et al. 2013; references therein) Machine Translation (e.g., Tckstrm 2009) etc. Our Approach Most of the community effort has focused on modeling pairs of variables with supervision

E.g., brachen -> brechen E.g., brachen -> gebracht like neural MT We focus on joint decoding of ALL uknown paradigm slots given ALL known slots Natural way to capture correlations in output structure Our Approach

Joint probability distributions over a tuple of strings String-valued latent variables in generative models (e.g., Dreyer & Eisner, Cotterell & Eisner, Andrews et al.) Inference: What unobserved strings could have generated gebracht? Research Questions: How do we parametrize the distributions? How can we perform efficient inference?

Can we learn predictive parameters in practice? The Formalism Graphical Models over Strings Review: Factor Graph Notation A

B D C E Example Factor Graph 12

Example Factor Graph 13 Inference through Message Passing Inference: Belief Propagation 15

Inference: Belief Propagation 16 Paradigm Graphs Morphological Paradigm: Spanish Verbs to put

poner puso pongo pusimos pondra pusieron

pongamos Morphological Paradigm: Spanish Verbs to put poner puso

pongo 2 factors! N s~ a h h p a r

dg e t c e n n lly co u F

pusimos pondra pusieron pongamos Too Many Parameters! Paradigms can be viewed as Tree Structured (e.g., Narasimhan et al. 2015)

to put poner puso pongo pusimos pusieron

pondra pongamos Morphological Paradigm Tree: Spanish Verbs Generative Model of a Tuple of Strings

poner puso pongo pusimos pusieron pondra

pongamos Conditional Distributions play the Role of Factors! Recurrent Neural Factors Morphological Paradigm Tree: Spanish Verbs Generative Model

of a Tuple of Strings poner puso pongo pusimos pusieron

pondra pongamos Each conditional is a seq2seq model (Aharoni et al. 2016)! Which Tree?

Which Tree? Baseline Tree (lemma-rooted) Which Tree? Gold Tree Latin verb to love amo, amare, amavi, amatus

Principal Parts intuition Based on Linguistic Scholarship Used in Pedagogy arts P l a p

i c Prin kel & n i F ( s i

s Analy 07 ) 0 2 p m Stu Which Tree?

Heuristic Tree (Linguistically-Inspired) Keep only the most deterministic edges! (e.g., Ackerman & Malouf 2013) Edge Weight = # edit paths (Chrupala 2008) Find minimal directed spanning tree (Edmonds 1967)

How do we do Inference? Neural factors give flexibility, but lose tractable closed-form inference Approximate MAP via Simulated Annealing Modified Metropolis-Hastings MCMC Pseudocode Overview

Repeat Until Convergence Select latent variable at uniform Sample a new string value for the variable Select neighboring edge at uniform Sample string from Neural Net for that edge Accept with probability Reduce to approximate MAP estimate (simulated annealing)

Experiments Compared Baseline/Gold/Heuristic paradigm graphs Recover 2/3 of forms in test paradigms given the lemma and remaining 1/3 of forms All paradigm data from Wiktionary ( Results Extensions

Framework applies to any inference problem over mutually related sets of strings. Possible application: Cognate Reconstruction discover transliteration relations across different languages in a family to augment dictionaries, e.g. use high-coverage dictionaries of high-resource language to infer entries for related low-resource language. tree-shaped graphs relevant for historical reconstruction (e.g., Bouchard-Cote 2007)

Thank You! DAAD Long-Term Research Grant, NDSEG Fellowship, and DARPA LORELEI [email protected] [email protected] [email protected]

References Tckstrm, Oscar. 2009. The Impact of Morphological Errors in Phrase-based Statistical Machine Translation from German and English into Swedish. In Proceedings of 4th Language & Technology Conference, 546-550. Poznan, Poland. Tsarfaty, Reut; Djam Seddah; Sandra Kbler; and Joakim Nivre. 2013. Parsing Morphologically Rich Languages: Introduction to the Special Issue. Computational Linguistics 39(1): 15-22. Finkel, Raphael; and Gregory Stump. 2007. Principal parts and morphological typology. Morphology 17:39-75.

plus additional references listed in the proceedings paper

Recently Viewed Presentations

  • Yale FBO Communications

    Yale FBO Communications

    FlowVisor. Allocate a fixed portion of tasks and resources. There are significant previous studies on the debugging and. evaluation of distributed systems. (Click) Compared with them, ShadowStream is the first system based on the. key observation that both the Repair...
  • Pipelining -

    Pipelining -

    Pipelining defined. Multiple instructions are overlapped in execution. Divide the work of the cpu as equally as possible. MIPS lends itself to pipelining because the only operations that affect memory are load and store and the instruction size is the...
  • U3 Unit Conversions - Amazon S3

    U3 Unit Conversions - Amazon S3

    Since the gallons unit is in the denominator of the given quantity and we want gallons to cancel, we will place gallons in the numerator of the conversion factor. [click] Gallons will cancel and leave liters in the denominator, which...
  • Diabetes Mellitus - Job Corps

    Diabetes Mellitus - Job Corps

    1550 BC: The oldest description of diabetes was noted to be a polyuric condition in ancient Egypt. In the 5th/6th century BC: The descriptions of diabetes recognized the distinction between two forms of diabetes, one in older, fatter people (type...
  • Understanding Population Pyramids - CVUSD Home

    Understanding Population Pyramids - CVUSD Home

    Calibri Arial Lucida Grande Times Didot Office Theme Microsoft Excel Worksheet Understanding Population Pyramids Population Pyramids Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Analysis of Italy's Population Pyramid Slide 9 Slide 10 Slide 11 Slide 12 Slide...
  • ODE workshop: During a chemical reaction, the concentration

    ODE workshop: During a chemical reaction, the concentration

    ODE workshop: 1) During a chemical reaction, the concentration C satisfies Solve this using both the Euler and the Runge-Kutta method using the
  • Neural Network Theory - UTK

    Neural Network Theory - UTK

    Random order - a neuron i is randomly chosen and its ????, ??and ?? are updated. For n neurons, a cycle is the n-fold execution of this step. Not always useful. Random permutation - each neuron is chosen exactly once,...
  • Drive-by-wire and BMW problems - University of Birmingham

    Drive-by-wire and BMW problems - University of Birmingham

    Using a document's grammar to hide information "The auto drives fast on a slippery road over the hill" changed to "Over the slope the car travels quickly on an ice-covered street". Encoding text with a different meaning By using a...