Difference between revisions of "Daume and Marcu 2005 Learning as Search Optimization: Approximate Large Margin Methods for Structured Prediction"

From Cohen Courses
Jump to navigationJump to search
Line 7: Line 7:
 
The authors present the Learning as Search Optimization (LaSO) framework.  The algorithm is basically SEARN but analyzed differently (and also ~24 pages shorter).
 
The authors present the Learning as Search Optimization (LaSO) framework.  The algorithm is basically SEARN but analyzed differently (and also ~24 pages shorter).
  
Like SEARN, LaSO attempts to combine the learning of the model with the search that occurs during decoding.   
+
Like SEARN, LaSO attempts to combine the learning of the model with the search that occurs during decoding.  Instead of learning the model, and then doing a search during decoding to find the best output <math>hat{y}</math>
 +
 
 +
<math>hat{y}=text{arg}\max_{y \in \mathcal{Y}} f(x,y;w)</math>
  
 
=== Method ===
 
=== Method ===
 +
 +
The generic search (decoding) algorithm is shown below:
 +
 +
[[File:LaSO Generic Search.png]]
 +
 +
The ''enqueue'' function puts the nodes onto the queue in some order.  Depending on the order that the ''enqueue'' function puts nodes on the queue, you can get depth-first, breadth-first, beam, heuristic, A*, etc search algorithms from standard AI textbooks.  The thing that is different about LaSO is the function ''enqueue''.
 +
 +
LaSO works by learning the ''enqueue'' function from the training examples.
  
 
[[File:LaSO Algorithm.png]]
 
[[File:LaSO Algorithm.png]]

Revision as of 03:04, 1 October 2011

Citation and Online Link

Learning as Search Optimization: Approximate Large Margin Methods for Structured Prediction An alternative formal analysis of Searn.

Summary

The authors present the Learning as Search Optimization (LaSO) framework. The algorithm is basically SEARN but analyzed differently (and also ~24 pages shorter).

Like SEARN, LaSO attempts to combine the learning of the model with the search that occurs during decoding. Instead of learning the model, and then doing a search during decoding to find the best output

Method

The generic search (decoding) algorithm is shown below:

LaSO Generic Search.png

The enqueue function puts the nodes onto the queue in some order. Depending on the order that the enqueue function puts nodes on the queue, you can get depth-first, breadth-first, beam, heuristic, A*, etc search algorithms from standard AI textbooks. The thing that is different about LaSO is the function enqueue.

LaSO works by learning the enqueue function from the training examples.

LaSO Algorithm.png

Experimental Result

Related Papers

In progress by User:Jmflanig