Structured Prediction
Introduction
What is structured prediction?
CS 6355: Structured Prediction
Our goal today
To define a Structure and Structured Prediction
2
What are structures?
3
What are some examples of structured
data?
• Database tables and spreadsheets
• HTML documents
• JSON objects
• Wikipedia info-boxes
• Computer programs
… we will see more examples
4
What are some examples of unstructured
data?
• Images
• Videos
• Text documents
• PDF files
• Books What makes these unstructured?
• … How are they different from the previous list?
5
Structured representations are useful
because ….
• We know how to process them
– Algorithms for managing symbolic data
– Computational complexity well understood
• They abstract away unnecessary complexities
– Why deal with text, images, etc when you can process a
database with the same information?
6
Example: Reading comprehension is hard!
Water is split, providing a source of electrons and
protons (hydrogen ions, H+) and giving off O2 as a by-
product. Light absorbed by chlorophyll drives a transfer
of the electrons and hydrogen ions from water to an
acceptor called NADP+.
What can the splitting of water lead to?
A: Light absorption
B: Transfer of ions
Reading comprehension is hard!
Water is split, providing a source of electrons and
protons (hydrogen ions, H+) and giving off O2 as a by-
product. Light absorbed by chlorophyll drives a transfer
of the electrons and hydrogen ions from water to an
acceptor called NADP+.
What can the splitting of water lead to?
A: Light absorption
B: Transfer of ions
Reading comprehension is hard!
Water is split, providing a source of electrons and
protons (hydrogen ions, H+) and giving off O2 as a by-
product. Light absorbed by chlorophyll drives a transfer
of the electrons and hydrogen ions from water to an
acceptor called NADP+.
What can the splitting of water lead to?
A: Light absorption
B: Transfer of ions
Reading comprehension is hard!
Enable
Water is split, providing a source of electrons and
protons (hydrogen ions, H+) and giving off O2 as a by-
product. Light absorbed by chlorophyll drives a transfer
of the electrons and hydrogen ions from water to an
acceptor called NADP+.
What can the splitting of water lead to?
A: Light absorption
B: Transfer of ions
Reading comprehension is hard!
Enable
Water is split, providing a source of electrons and
protons (hydrogen ions, H+) and giving off O2 as a by-
product. Light absorbed by chlorophyll drives a transfer
of the electrons and hydrogen ions from water to an
acceptor called NADP+. Cause
What can the splitting of water lead to?
A: Light absorption
B: Transfer of ions
Reading comprehension is hard!
Enable
Water is split, providing a source of electrons and
protons (hydrogen ions, H+) and giving off O2 as a by-
product. Light absorbed by chlorophyll drives a transfer
of the electrons and hydrogen ions from water to an
acceptor called NADP+. Cause
What can the splitting of water lead to?
A: Light
If we hadabsorption
a representation like this, we might be
B: Transfer ofanswer
able to ions complex questions
Machine learning to the rescue
• Techniques from statistical learning can help build
these representations
• In fact, machine learning is necessary to scale up and
generalize this process
13
A detour about classification
14
Classification
We know how to train classifiers
– Given an email, spam or not spam?
– Is a review positive or negative?
– Automatically be place emails into a folder into?
– “Predict if a car purchased at an auction is a lemon”
15
Standard classification setting
• Notation
– X: A feature representation of input
– Y: One of a set of labels (spam, not-spam)
• The goal: To learn a function X ! Y that maps
examples into a category
• The standard recipe
1. Collect labeled examples {(x1,y1), (x2, y2), !}
2. Train a function f: X ! Y that
a. Is consistent with the observed examples, and
b. Can hopefully be correct on new, previously unseen examples
16
Classification is generally well understood
• Theoretically: generalization bounds
– We know how many examples one needs to see to guarantee good behavior
on unseen examples
• Algorithmically: good learning algorithms for linear representations
– Efficient and can deal with high dimensionality (millions of features)
• Some open questions
– What is a good feature representation?
– Learning protocols: how to minimize supervision, efficient semi-supervised
learning, active learning
Is this sufficient for solving problems like the reading
comprehension one?
17
Classification is generally well understood
• Theoretically: generalization bounds
– We know how many examples one needs to see to guarantee good behavior
on unseen examples
• Algorithmically: good learning algorithms for linear representations
– Efficient and can deal with high dimensionality (millions of features)
• Some open questions
– What is a good feature representation?
– Learning protocols: how to minimize supervision, efficient semi-supervised
learning, active learning
Is this sufficient for solving problems like the reading
comprehension one? No!
18
Back to “What are structures?”
19
Semantic Role Labeling
Input: John saw the dog chasing the ball.
Output:
Predicate see Predicate Chase
Viewer John Chaser The dog
Thing viewed The dog chasing the ball Thing chased the ball
Or equivalently, predicate-argument representations
See(Viewer: John, Chase(Chaser: the dog,
Viewed: the dog chasing the ball) Chased: the ball)
20
Semantic Parsing
X: “A python function that takes a name and prints the
string Hello followed by the name and exits.”
Y:
X: “Find the largest state in the US.”
SELECT name
Y: FROM us_states
WHERE size = (SELECT MAX(size) FROM us_states)
In all these cases, the output Y is a structure
21
What is a structure? One definition
By … linguistic structure, we refer to symbolic
representations of language posited by some theory of
language.
From the book Linguistic Structure Prediction, by Noah Smith, 2011.
22
What is in this picture?
23
Photo by Andrew Dressel - Own work. Licensed under Creative Commons Attribution-Share Alike 3.0
Object detection
Right facing bicycle
24
Photo by Andrew Dressel - Own work. Licensed under Creative Commons Attribution-Share Alike 3.0
Object detection
Right facing bicycle
saddle/seat handle bar
right wheel
left wheel
25
Photo by Andrew Dressel - Own work. Licensed under Creative Commons Attribution-Share Alike 3.0
The output: A schematic showing the parts
and their relative layout
Right facing bicycle
saddle/seat handle bar
right wheel
left wheel
Once again, a structure
26
Produced with a Trial Version of PDF Annotator - [Link]
A working definition of a structure
From the book Analysing Sentences: An Introduction to English Syntax by Noel Burton-Roberts, 1986.
A structure is a concept that can be applied to any complex thing, whether it
be a bicycle, a commercial company, or a carbon molecule. By complex, we
mean:
1. It is divisible into parts,
2. There are different kinds of parts,
3. The parts are arranged in a specifiable way, and,
4. Each part has a specifiable function in the structure of the thing as a
whole
27
What is structured prediction?
28
Simple classifiers are not designed to predict
structures X: “Find the largest state in the US.”
Y: SELECT name
FROM us_states
WHERE size = (SELECT MAX(size) FROM us_states)
Classification is about making one decision
– Spam or not spam, or label a picture
We need to make multiple decisions
– Each part needs a label
• Should “US” be mapped to us_states or utah_counties?
• Should “Find” be mapped to SELECT or FROM or WHERE?
– The decisions interact with each other
• If the outer FROM clause talks about the table us_states, then the inner FROM
clause should not talk about utah_counties
– How to compose the fragments together to create the whole structure?
• Should the output consist of a WHERE clause? What should go in it?
29
Structured prediction
Machine learning of interdependent variables
• Unlike simple classification problems, many problems
have
– Multiple interdependent output variables
– Both local and global decisions to be made
• Mutual dependencies necessitate a joint assignment to
all the output variables
– Joint inference or Global inference or simply Inference
• These problems are called structured output problems
30
Computational issues
Model definition
What are the parts of the output?
Data annotation What are the inter-dependencies?
difficulty
Background
How to train the
knowledge about How to do inference?
model?
domain
Semi-
supervised/indirectly
supervised?
31
Another look at the important issues
• Availability of supervision
– Supervised algorithms are well studied; supervision is hard (or
expensive) to obtain
• Complexity of model
– More complex models encode complex dependencies between
parts; complex models make learning and inference harder
• Features
– Most of the time we will assume that we have a good feature
set to model our problem. But do we?
• Domain knowledge
– Incorporating background knowledge into learning and
inference in a mathematically sound way
32