Structured Prediction - Svivek

Structured PredictionFinal wordsCS 6355: Structured Prediction1

A look back What is a structure? The machine learning of interdependent variables2

Recall: A working definition of a structureA structure is a concept that can be applied to any complex thing, whether itbe a bicycle, a commercial company, or a carbon molecule. By complex, wemean: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 awholeFrom the book Analysing Sentences: An Introduction to English Syntax by Noel Burton-Roberts, 1986.3

An example task: Semantic ParsingFind the largest state in the USSELECT expression FROM table WHERE conditionMAX (numeric list)ORDERBY predicateDELETE FROM table WHERE conditionUS CITIES US STATESnamenamepopulation populationsizestatecapitalSELECT expression FROM tableExpression 1 Expression 24

A plausible strategy to build the queryFind the largest state in the USSELECT expression FROM table WHERE conditionMAX numeric listORDERBY predicateDELETE FROM table WHERE conditionSELECT expression FROM tableExpression 1 Expression 2US CITIESUS 5

A plausible strategy to build the queryFind the largest state in the USSELECT expression FROM table WHERE conditionSELECT expression FROM table WHERE conditionMAX numeric listORDERBY predicateDELETE FROM table WHERE conditionSELECT expression FROM tableExpression 1 Expression 2US CITIESUS 6

A plausible strategy to build the queryFind the largest state in the USSELECT expression FROM table WHERE conditionUS STATESSELECT expression FROM table WHERE conditionMAX numeric listORDERBY predicateDELETE FROM table WHERE conditionSELECT expression FROM tableExpression 1 Expression 2US CITIESUS 7

A plausible strategy to build the queryFind the largest state in the USSELECT expression FROM table WHERE conditionnameUS STATESSELECT expression FROM table WHERE conditionMAX numeric listORDERBY predicateDELETE FROM table WHERE conditionSELECT expression FROM tableExpression 1 Expression 2US CITIESUS 8

A plausible strategy to build the queryFind the largest state in the USSELECT expression FROM table WHERE conditionnameUS STATESExpression 1 Expression 2SELECT expression FROM tableSELECT expression FROM table WHERE conditionMAX numeric listORDERBY predicateDELETE FROM table WHERE conditionSELECT expression FROM tableExpression 1 Expression 2US CITIESUS 9

A plausible strategy to build the queryFind the largest state in the USSELECT expression FROM table WHERE conditionnameUS STATESExpression 1 Expression 2SELECT expression FROM tableMAX numeric listSELECT expression FROM table WHERE conditionMAX numeric listORDERBY predicateDELETE FROM table WHERE conditionSELECT expression FROM tableExpression 1 Expression 2US CITIESUS 10

A plausible strategy to build the queryFind the largest state in the USSELECT expression FROM table WHERE conditionnameUS STATESExpression 1 Expression 2SELECT expression FROM tableMAX numeric listUS STATESSELECT expression FROM table WHERE conditionMAX numeric listORDERBY predicateDELETE FROM table WHERE conditionSELECT expression FROM tableExpression 1 Expression 2US CITIESUS 11

A plausible strategy to build the queryFind the largest state in the USSELECT expression FROM table WHERE conditionnameUS STATESExpression 1 Expression 2SELECT expression FROM tablesizeOr perhaps population?MAX numeric listsizeSELECT expression FROM table WHERE conditionMAX numeric listORDERBY predicateDELETE FROM table WHERE conditionSELECT expression FROM tableExpression 1 Expression 2US STATESUS CITIESUS 12

A plausible strategy to build the queryFind the largest state in the US At each step many, many decisions to makeSELECT expression FROM table WHERE condition Somenamedecisions aresimply not allowedUS STATESExpression 1 Expression 2- A query has to be well formed!sizeSELECT expression FROM table Even so, many possible options- Why doesto SELECT? MAX numeric listOr“Find”perhapsmappopulation?- Largest by size/population/population of capital?sizeSELECT expression FROM table WHERE conditionMAX numeric listORDERBY predicateDELETE FROM table WHERE conditionSELECT expression FROM tableExpression 1 Expression 2US STATESUS CITIESUS 13

Standard classification tools can’t predictstructuresX: “Find the largest state in the US.”Y: SELECT nameFROM us statesWHERE size (SELECT MAX(size) FROM us states)Classification is about making one decision–Spam or not spam, or predict one label, etcWe need to make multiple decisions– Each part needs a label Should “US” be mapped to us states or us cities?Should “Find” be mapped to SELECT or DELETE?– The decisions interact with each other If the outer FROM clause talks about the table us states, then the inner FROM clause should not talkabout 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?14

How did we get here?Binary classification Learning algorithms Prediction is easy – Threshold Features (?)Multiclass classification Different strategies One-vs-all, all-vs-all Global learning algorithms One feature vector per outcome Each outcome scored Prediction highest scoring outcomeStructured classification Global models or local models Each outcome scored Prediction highest scoring outcome Inference is no longer easy! Makes all the difference15

Structured output is A graph, possibly labeled and/or directedRepresentation– Possibly from a restricted family, such as chains, trees, etc.– A discrete representation of input– Eg. A table, the SRL frame output, a sequence of labels etc A collection of inter-dependent decisionsProcedural– Eg: The sequence of decisions used to construct the output The result of a combinatorial optimization problemFormally– argmaxy 2 all outputsscore(x, y)16

Challenges with structured output Two challenges1. We cannot train a separate weight vector for each possibleinference outcome For multiclass, we could train one weight vector for each label1. We cannot enumerate all possible structures for inference Inference for binary/multiclass is easy Solution– Decompose the output into parts that are labeled– Define how the parts interact with each other how labels are scored for each part an inference algorithm to assign labels to all the parts17

Multiclass as a structured output A structure is Multiclass– A graph (in general,hypergraph), possibly labeledand/or directed– A graph with one node andno edges– A collection of interdependent decisions– Can be composed via multipledecisions– The output of a combinatorialoptimization problem– Winner-take-allargmaxi wTÁ(x, i)argmaxy 2 all outputsscore(x, y) Node label is the output18

Multiclass is a structure: Implications1. A lot of the ideas from multiclass may be generalized tostructures– Not always trivial, but useful to keep in mind2. Broad statements about structured learning must applyto multiclass classification–Useful for sanity check, also for understanding3. Binary classification is the most “trivial” form ofstructured classification–Multiclass with two classes19

Structured PredictionThe machine learning of interdependent variables20

Computational issuesData annotationdifficultyHow to train themodel?Model definitionWhat are the parts of the output?What are the inter-dependencies?Backgroundknowledge aboutdomainHow to do inference?Semisupervised/indirectlysupervised?21

Computational issuesData annotationdifficultyHow to train themodel?Model definitionWhat are the parts of the output?What are the inter-dependencies?Backgroundknowledge aboutdomainHow to do inference?Semisupervised/indirectlysupervised?22

What does it mean to define the model?Say we want to predict four output variables from some inputxy1y2y3y423

What does it mean to define the model?Say we want to predict four output variables from some inputRecall: Each factor is alocal expert about allthe random variablesconnected to itxy1y2y3y4i.e. A factor can assigna score to assignmentsof variables connectedto itOption 1: Score each decision separatelyPro: Prediction is easy, each y independentCon: No consideration of interactions24

What does it mean to define the model?Say we want to predict four output variables from some inputRecall: Each factor is alocal expert about allthe random variablesconnected to itxy1y2y4y3i.e. A factor can assigna score to assignmentsof variables connectedto itOption 2: Add pairwise factorsPro: Accounts for pairwise dependenciesCons: Makes prediction harder,ignores third and higher orderdependencies25

What does it mean to define the model?Say we want to predict four output variables from some inputRecall: Each factor is alocal expert about allthe random variablesconnected to itxy1y2y4y3i.e. A factor can assigna score to assignmentsof variables connectedto itOption 3: Use only order 3 factorsPro: Accounts for order 3 dependenciesCons: Prediction even harder.Inference should consider alltriples of labels now26

What does it mean to define the model?Say we want to predict four output variables from some inputRecall: Each factor is alocal expert about allthe random variablesconnected to itxy1y2y4y3i.e. A factor can assigna score to assignmentsof variables connectedto itOption 4: Use order 4 factorsPro: Accounts for order 4 dependenciesCons: Basically no decompositionover the labels!27

What does it mean to define the model?Say we want to predict four output variables from some inputRecall: Each factor is alocal expert about allthe random variablesconnected to itxy1y2y3y4i.e. A factor can assigna score to assignmentsof variables connectedto itHow do we decide what to do?28

Some aspects to consider Availability of supervision– Supervised algorithms are well studied; supervision is hard (orexpensive) to obtain Complexity of model– More complex models encode complex dependencies betweenparts; complex models make learning and inference harder Features– Most of the time we will assume that we have a good featureset to model our problem. But do we? Domain knowledge– Incorporating background knowledge into learning andinference in a mathematically sound way29

Computational issuesData annotationdifficultyHow to train themodel?Model definitionWhat are the parts of the output?What are the inter-dependencies?Backgroundknowledge aboutdomainHow to do inference?Semisupervised/indirectlysupervised?30

Training structured models Inference in training makes all the difference from multiclass/binaryclassification Empirical risk minimization principle– Minimize loss over the training data– Regularize the parameters to prevent overfitting We have seen different training strategies falling under this umbrella– Conditional Random Fields– Structural Support Vector Machines– Structured Perceptron (doesn’t have regularization) Different algorithms exist– We saw stochastic gradient descent in some detail31

Training considerations Train globally vs train locallyGlobal: Train according to your final modelxy1y2y3y4Pro: Learning uses all the available informationCon: Computationally expensive32

Training considerations Train globally vs train locallyLocal: Decompose your model into smaller ones and train each one separatelyFull model still used at prediction timey2y1xy4y3y2y1y2y3y4y1y3y1y3y2y4y4Pro: Easier to trainCon: May not capture global dependencies33

Training considerations Local vs global– Local learning Learn parameters for individual components independently Learning algorithm not aware of the full structure– Global learning Learn parameters for the full structure Learning algorithm “knows” about the full structureHow do we choose?– Depends on inference complexity– Jury still out on which one is better– Depends on size of available data too34