View source for Daume and Marcu 2005 Learning as Search Optimization: Approximate Large Margin Methods for Structured Prediction

From Cohen Courses

← Daume and Marcu 2005 Learning as Search Optimization: Approximate Large Margin Methods for Structured Prediction

You do not have permission to edit this page, for the following reason:

---

You can view and copy the source of this page.

=== Citation and Link === [http://hal3.name/docs/daume05laso.pdf Learning as Search Optimization: Approximate Large Margin Methods for Structured Prediction] === Summary === The authors present the Learning as Search Optimization (LaSO) framework. The algorithm is basically SEARN but analyzed differently (and also ~24 pages shorter). 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, LaSO attempts to directly learn to search. === 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. In LaSO ''enqueue'' ranks nodes according to a function ''g'' which is a linear in the set of features. The features can depend on the input ''x'' and the path to the current current node ''n'': <math>g=\mathbf{\omega}^\top \mathbf{\Phi}(x,n)</math> LaSO learns the feature weights from the training examples. The learning algorithm is shown below: [[File:LaSO Algorithm.png]] Nodes for which there exists a path to the optimal goal are called "y-good" nodes. The ''siblings'' function denotes the set of nodes at the same depth as current node that can reach the goal (i.e. are y-good). The algorithm may have to backtrack to find them if they are not currently in the queue. If the search makes a mistake, the weights are updated with the function ''update''. The two functions they propose in the paper are the perceptron update and a variant of the approximate large margin update (ALMA). * '''Perceptron update rule:''' <math>\mathbf{\omega} \leftarrow \mathbf{\omega} + \Delta</math> [[File:LaSO Perceptron Update.png]] * '''ALMA update rule:''' <math>\mathbf{\omega} \leftarrow \mathbf{\omega} + \wp(\mathbf{\omega} + Ck^{-1/2} \wp(\Delta))</math> where <math>\wp(\mathbf{u}) = \mathbf{u} / \max \{1,\lVert \mathbf{u} \rVert_{2} \}</math> and k starts at 1 and is incremented at each update. === Experimental Result === === Related Papers === In progress by [[User:Jmflanig]]

Return to Daume and Marcu 2005 Learning as Search Optimization: Approximate Large Margin Methods for Structured Prediction.