Machine Translation and Sequence-to-sequence Models

Machine Translation andSequence-to-sequence
Modelshttp://phontron.com/class/mtandseq2seq2017/
Graham Neubig
Carnegie Mellon University
CS 11-731

1

Machine Translation and Sequence-to-sequence Models

What is Machine Translation?
kare wa ringo wo tabeta .

He ate an apple .
2

Machine Translation and Sequence-to-sequence Models

What areSequence-to-sequence Models?
Sequence-to-sequence Models
Machine translation:

kare wa ringo wo tabeta → he ate an apple

Tagging:

he ate an apple → PRN VBD DET PP
Dialog:he ate an apple → good, he needs to slim down
Speech Recognition:→ he ate an apple

And just about anything...:

1010000111101 → 00011010001101

3

Machine Translation and Sequence-to-sequence Models

Why MT as a Representative?

Useful!

Global MT Market
Expected To Reach $983.3
Million by 2022

Source: The Register

Imperfect...

Source: Grand View Research

4Machine Translation and Sequence-to-sequence Models

MT and Machine Learning
Big Data! Billions of words for major languages… but little for others

Well-defined, Difficult Problem!
Use for algorithms, math, etc.

Algorithms Widely Applicable!
5

Machine Translation and Sequence-to-sequence Models

MT and Linguistics트레이나 베이커는 좋은 사람이니까요Baker yinikkayo tray or a good man
Trina Baker is a good person
Morphology! 이니까요 is a variant of 이다 (to be)
Syntax! should keep subject together
Semantics! “Trina” is probably not a man...
… and so much more!

6

Machine Translation and Sequence-to-sequence Models

Class Organization

7

Machine Translation and Sequence-to-sequence Models

Class Format●

Before class:
Read the assigned material● Ask questions via web (piazza/email)●●In class:Take a small quiz about material● Discussion/questions● Pseudo-code walk
● Programming (TAs/Instructor will supervise)●8

Machine Translation and Sequence-to-sequence Models

Assignments●●●

Assignment 1: Create a neuralsequence-to-sequence modeling system.
Turn in code to run it, and a short 1-2
page report.
Assignment 2: Create a symbolic
sequence-to-sequence modeling system.
Similarly turn in code/report.
Final project: Come up with aninteresting new idea and test it.
9Machine Translation and Sequence-to-sequence Models

Assignment Instructions●●

Bring your computer to every class and make a Github
account.
We recommend you implement in the following
libraries:
DyNet: for neural networks (C++ or Python)● OpenFST: for transducers, if you use them (C++)● pyfst: for transducers in Python●●

It is OK to work in small groups up to 3, particularly forthe final project. If you do so, please use a shared git
repository and commit the code that you write, and inreports note who did what part of the project.
10

Machine Translation and Sequence-to-sequence ModelsClass Grading●Short quizzes: 20%●Assignment 1: 20%●Assignment 2: 20%●Final Project: 40%

11

Machine Translation and Sequence-to-sequence Models

Class Plan
1. Introduction (Today): 1 class
2. Language Models: 4 classes
3. Neural MT: 2 classes
3. Evaluation/Data: 2 classes#1 Due4. Symbolic MT: 4 classes
5. Algorithms: 2 classes#2 Due7. Advanced Topics: 11 classes
8. Final Project Discussion: 2 classes
ProjectDue

12

Machine Translation and Sequence-to-sequence Models

Guest Lectures
Bob Frederking:Knowledge-based Translation● LP Morency:Something Multi-modal●(Date TBD)

13

Machine Translation and Sequence-to-sequence Models

Statistical Machine Translation

14

Machine Translation and Sequence-to-sequence Models

Statistical Machine Translation
F = kare wa ringo wo tabeta .
E=He ate an apple .

Probability model: P(E|F;Θ)Parameters
15

Machine Translation and Sequence-to-sequence Models

Problems in SMT●

Modeling: How do we define P(E|F;Θ)?

●Learning: How do we learn Θ?

●Search: Given F, how do we find thehighest scoring translation?
E' = argmaxE P(E|F;Θ)●Evaluation: Given E' and a humanreference E, how do we determine how
good E' is?

16Machine Translation and Sequence-to-sequence Models

Part 1: Neural Models

17

Machine Translation and Sequence-to-sequence Models

Language Models 1: n-gram
Language Models
E1 = he ate an apple

Given multiple candidates,
E2 = he ate an apples
which is most likely as
E3 = he insulted an apple
an English sentence?
E4 = preliminary orange orange●

Definition of language modeling●Count-based n-gram language models●

Evaluating language models●

Implement: n-gram language model

18

Machine Translation and Sequence-to-sequence ModelsLanguage Models 2: Log-linear
Language Models
athetalkgifthat…

3.02.5b = -0.2
0.1
1.2…

w1,a =-6.0
-5.1
0.2
0.1
0.6…

w2,giving =-0.2-0.3
1.0
2.0-1.2…

●

Log-linear language models●

Stochastic gradient descent●Features for language modeling●-3.2-2.9
s = 1.0
2.2
0.6…

Implement: Log-linear language model

19

Machine Translation and Sequence-to-sequence Models

Language Models 3: NeuralNetworks and Feed-forward LMs






thisisapen
●Neural networks and back-propagation●

Feed-forward neural language models●

Mini-batch training●

Implement: Feed-forward LM

20

Machine Translation and Sequence-to-sequence Models

Language Models 4:
Recurrent LMs






thisisapen
●

Recurrent neural networks●

Vanishing Gradient and LSTMs/GRUs●

Regularization and dropout●

Implement: Recurrent neural network LM

21

Machine Translation and Sequence-to-sequence Models

Neural MT 1:
Encoder-decoder Models
thisisapen 
 kore wa pen desu

kore wa pen desu 

● Encoder-decoder Models●

Searching for hypotheses●

Mini-batched training●

Implement: Encoder-decoder model

22

Machine Translation and Sequence-to-sequence Models

Neural MT 2:Attentional Models

okonaikouenwomasu
a1 a2 a3 a4
hi-1
hiri-1

g1,...,g4

P(ei|F,e1,...,ei-1●

Attention in its various varieties●

Unknown word replacement●

Attention improvements, coverage models●

Implement: Attentional model

23

Machine Translation and Sequence-to-sequence Models

Data and Evaluation24

Machine Translation and Sequence-to-sequence Models

Creating Data●Preprocessing●Document harvesting and crowdsourcing●

Other tasks: dialog, captioning●

Implement: Find/preprocess data25

Machine Translation and Sequence-to-sequence Models

Evaluation
taro ga hanako wo otozureta
Taro visited Hanako the Taro visited the Hanako Hanako visited Taro

Adequate? ○Fluent?
○Better?
B, C○
☓C

☓○

●

Human evaluation●

Automatic evaluation●

Significance tests and meta-evaluation●

Implement: BLEU and measure correlation

26

Machine Translation and Sequence-to-sequence Models

Symbolic Translation
Models27

Machine Translation and Sequence-to-sequence ModelsSymbolic Methods 1:
IBM Models
太郎 が 花子 を 訪問 した 。

太郎 が 花子 を 訪問 した 。

taro visited hanako .

taro visited hanako .

●The IBM/HMM models●The EM algorithm●

Finding word alignments●

Implement: Word alignment28

Machine Translation and Sequence-to-sequence Models

Symbolic Methods 2:
Monotonic Symbolic Models
he ate an apple↓PRN VBD DET PP●

Models for sequence transduction●

The Viterbi algorithm●

Weighted finite-state transducers●

Implement: A part-of-speech tagger

29

Machine Translation and Sequence-to-sequence Models

Symbolic Methods 3:
Phrase-based MT
F = watashi wa CMU de kouen wo okonaimasu .
watashi waIwatashi waI

CMU deat CMU

kouena talkwo okonaimasu
will give

wo okonaimasu
will givekouena talk

CMU deat CMU.
.
.
.

E = I will give a talk at CMU .
●Phrase extraction and scoring●Reordering models●

Phrase-based decoding●Implement: Phrase extraction or decoding30

Machine Translation and Sequence-to-sequence Models

Symbolic Methods 4:
Tree-based MTx2 at x1

VP0-5
VP2-5

PP0-1
N0P1N2CMU

x2 x1

PP2-3

VP4

P3

V4

de kouen wo okonaimasu

givea talkCMU●Graphs and hyper-graphs●

Synchronous context free grammars●Tree substitution grammars●

give a talkat CMU

Implement: Search over hyper-graphs

31

Machine Translation and Sequence-to-sequence Models

Algorithms

32

Machine Translation and Sequence-to-sequence Models

Algorithms 1: Search●○○
1, yes○○○0, 


X
○●○
2, is
○○●
3, orX
●○●
3, or

●●○
2, is

●●●
3, or

●●●
2, true

X

○●●
2, is

●

Beam search and cube pruning●Hypothesis recombination●Future costs, A* search●


Implement: Beam search

33

Machine Translation and Sequence-to-sequence Models

Algorithms 2:
Parameter Optimization
Highest ○○ Taro visited Hanako☓ the Taro visited the Hanako☓ Hanako visited TaroLMTMRM
0.2*-4 0.3*-3 0.5*-1
0.2*-5 0.3*-4 0.5*-1
0.2*-2 0.3*-3 0.5*-2●

Loss functions●

Deciding the hypothesis space●Optimization criteria●-2.2-2.7-2.3

Implement: Optimization of NMT or PBMT

34

Machine Translation and Sequence-to-sequence Models

Advanced Topics

35

Machine Translation and Sequence-to-sequence Models

Other Sequence-to-sequenceTasks
he ate an apple → PRN VBD DET PP
he ate an apple → good, he needs to slim down
→ he ate an apple●Case studies about task-specific models

Consistency constraints in tagging● Diversity objectives in dialog● Dynamic programming in speech● Implement: Try models on other tasks●36Machine Translation and Sequence-to-sequence Models

Ensembling/SystemCombination
Model 1+Model 2●Ensembles and distillation●Post-hoc hypothesis combination●Reranking●

Implement: Ensembled decoding37

Machine Translation and Sequence-to-sequence Models

Hybrid Neural-symbolicModels

watashi waI

CMU deat CMU●

Symbolic models with neural components●

Neural models with symbolic components●

Implement: Implement lexicons in NMT orneural feature functions

38

Machine Translation and Sequence-to-sequence Models

Multi-lingual and Multi-task
Learning
hello

こんにちはhola●

Learning for multiple tasks●

Learning for multiple languages●

Implement: Implement a multi-lingual neuralsystem
39Machine Translation and Sequence-to-sequence Models

Subword Models
reconstructed
re+ construct+ ed●Character models●

Subword models●

Morphology models●

Implement: Implement subword splitting

40

Machine Translation and Sequence-to-sequence Models

Document Level Models●

Document level modeling●Document level evaluation●

Stream decoding●

Implement: Document level measures

41

Machine Translation and Sequence-to-sequence Models

For Next Class42

Machine Translation and Sequence-to-sequence Models

Homework●●

Read n-gram language modeling materials
Get software working on your machine (doing all atonce may be more efficient?)
By Thursday 1/19: Python● By Tuesday 1/24: Numpy● By Thursday 1/26: DyNet●43