Structured Prediction Cascades

This method as proposed by Weiss et al, AISTATS 2010

This page is reserved for a write up by Dan Howarth

Citation

Structured Prediction Cascades. David Weiss and Ben Taskar. International Conference on Artificial Intelligence and Statistics (AISTATS), May 2010.

Online version

[1]

Summary

In many structured prediction models an increase in model complexity comes at a high computational cost. For example, the complexity of a HMM grows exponentially with the order of the model. This work introduces a method for learning increasingly complex models while continually pruning the possible output space. This is done by "weeding" out the incorrect output states early on.

Previous methods to solve the problem of model complexity were commonly approximate search methods or heuristic pruning techniques. Structured prediction cascades are different however because they explicitly learn the error/computation trade off for each increase in model complexity.

In this work structured prediction cascades are applied to handwriting recognition and POS tagging.

Brief description of the method

The linear hypothesis class considered is of the form: $h_{\theta }(x)=\arg \max _{y\in {\mathcal {Y}}}\sum _{c\in {\mathcal {C}}}\theta ^{\mathrm {T} }f_{c}(x,y_{c})$ where ${\mathcal {C}}$ is the set of cliques.

At each level of the cascade the method is given the set of possible clique assignments as input, and each level then filters this set and passes the filtered set as input to the next level.

${\mathcal {Y}}_{c}$ is the set of possible output assignments to clique $c$

Let the following be defined for the $i$'th model:

${\mathcal {C}}^{i}$, the set of maximal cliques

${\mathcal {V}}_{c}^{i}\subseteq {\mathcal {Y}}_{c}$, the set of valid output assignments for clique $c$

Before pruning, ${\mathcal {V}}_{c}^{i}=\{y_{c}\in {\mathcal {Y}}_{c}|\forall c'\in {\mathcal {C}}^{i-1},c'\subseteq c,y_{c^{i}}\in {\mathcal {V}}_{c^{i}}^{i-1}\}$, or the set of assignments to the cliques in level $i$ that each contain as a subset a valid assignment in the $i-1$'th level

Any $y_{c}\in {\mathcal {V}}_{c}^{i}$ is then pruned if their max-marginal score is less than a threshold.

The threshold is the function $t(x,\alpha )=\alpha \theta ^{*}(x)+(1-\alpha ){\frac {1}{|V|}}\sum _{c\in {\mathcal {C}},y_{c}\in {\mathcal {V}}_{c}}\theta ^{*}(x,y_{c})$ where

$\alpha$ determines the number of max marginals eliminated

$\theta (x,y)=\theta ^{\mathrm {T} }f(x,y)$

$\theta ^{*}(x,y_{c})=\max _{y'\in {\mathcal {Y}}}\{\theta (x,y'):y'_{c}=y_{c}\}$, the score of best possible output that contains the assignments $y_{c}$

$\theta ^{*}(x)=max_{y}\theta (x,y)$

Learning

At each level of the cascade the best $\theta$ and $\alpha$ must be inferred.

At each level two competing objectives exist: accuracy and efficiency. This trade off is quantified by by the filtering loss ${\mathcal {L}}_{f}$ and efficiency loss ${\mathcal {L}}_{e}$:

${\mathcal {L}}_{f}=1[\theta (x,y)\leq t(x,\alpha )]$

${\mathcal {L}}_{e}={\frac {1}{|{\mathcal {V}}|}}\sum _{c\in {\mathcal {C}},y_{c}\in {\mathcal {V}}_{c}}1[\theta ^{*}(x,y_{c})\leq t(x,\alpha )]$

The cascade learning objective is then expressed by:

$\min _{\theta ,\alpha }\mathbb {E} [{\mathcal {L}}_{e}(Y,\theta (X))]{\text{ s.t. }}\mathbb {E} [{\mathcal {L}}_{f}(Y,\theta (X))]\leq \epsilon$

where $\epsilon$ is a parameter that bounds the expected error rate

Given $\alpha$ we choose \theta to optimize the convex problem:

$\inf _{\theta }{\frac {\lambda }{2}}||\theta ||^{2}+{\frac {1}{n}}\sum _{i}H(\theta ;(x^{i},y^{i}))$

where $H$ is the upper bound of ${\mathcal {L}}_{f}$ and convex:

$H(\theta ;(x^{i},y^{i}))=max\{0,l+t(x^{i},\alpha )-\theta ^{\mathrm {T} }f(x^{i},y^{i})\}$

$H$ is a hinge loss function that is positive if the true score is above the threshold by $l$. $\theta$ is solved for by using stochastic sub-gradient descent.

Experimental Result

In this work structured prediction cascades were applied to handwriting recognition and POS tagging.

The results for handwriting recognition were not compared to any other results, but rather showed the dramatic increase in accuracy as the order of the model increased. The model they used was a Markov model, and the paper explains that the search space of a 4-gram model was reduced by a magnitude of 5, while only producing a 3.41% filtering error.

Model Order:	1	2	3	4
Accuracy, Char (%)	77.44	85.69	87.95	92.25
Accuracy, Word (%)	26.65	49.44	73.83	84.46
Filter Loss (%)	0.56	0.99	3.41	-
Avg. Num n-grams	26.0	123.8	88.6	5.4

POS tagging was applied to the WSJ portion of the Penn TreeBank (Marcus et al., 1993). The following table shows the comparative results of the standard structured perceptron (SP), structured cascades using a markov model (SC), and a conditional random field (CRF), and a heuristic baseline in which only POS tags associated with a given word in the training set were searched during inference (Tags). Accuracy for the different methods was pretty much the same, but structured cascades was able to perform more efficiently at test time.

Model:	SP	SC	CRF	Tags
Accuracy (%)	96.83	96.82	96.84	-
Filter Loss (%)	0	0.121	0.024	0.118
Test Time (ms)	173.28	1.56	4.16	10.6
Avg. Num States	1935.7	3.93	11.845	95.39