Structured SVM - Separation

Separation

The above quadratic program involves a very large, possibly infinite number of linear inequality constraints. In general, the number of inequalities is too large to be optimized over explicitly. Instead the problem is solved by using delayed constraint generation where only a finite and small subset of the constraints is used. Optimizing over a subset of the constraints enlarges the feasible set and will yield a solution which provides a lower bound on the objective. To test whether the solution violates constraints of the complete set inequalities, a separation problem needs to be solved. As the inequalities decompose over the samples, for each sample the following problem needs to be solved.

y_n^* = \underset{y \in \mathcal{Y}}{\textrm{argmax}} \left( \Delta(y_n,y) + \boldsymbol{w}'\Psi(\boldsymbol{x}_n,y) - \boldsymbol{w}'\Psi(\boldsymbol{x}_n,y_n) - \xi_n\right)

The right hand side objective to be maximized is composed of the constant and a term dependent on the variables optimized over, namely . If the achieved right hand side objective is smaller or equal to zero, no violated constraint for this sample exist. If it is strictly larger than zero, the most violated constraint with respect to this sample has been identified. The problem is enlarged by this constraint and resolved. The process continues until no violated inequalities can be identified.

If the constants are dropped from the above problem, we obtain the following problem to be solved.

This problem looks very similar to the inference problem. The only difference is the addition of the term . Most often, it is chosen such that it has a natural decomposition in label space. In that case, the influence of can be encoded into the inference problem and solving for the most violating constraint is equivalent to solving the inference problem.

Read more about this topic:  Structured SVM

Famous quotes containing the word separation:

    “Like sleep disturbances, some worries at separation can be expected in the second year. If you accept this, then you will avoid reacting to this anxiety as if it’s your fault. A mother who feels guilty will appear anxious to the child, as if to affirm the child’s anxiety. By contrast, a parent who understands that separation anxiety is normal is more likely to react in a way that soothes and reassures the child.”
    —Cathy Rindner Tempelsman (20th century)

    “... the separation of church and state means separation—absolute and eternal—or it means nothing.”
    —Agnes E. Meyer (1887–1970)

    “The scholar was not raised by the sacred thoughts amongst which he dwelt, but used them to selfish ends. He was a profane person, and became a showman, turning his gifts to marketable use, and not to his own sustenance and growth. It was found that the intellect could be independently developed, that is, in separation from the man, as any single organ can be invigorated, and the result was monstrous.”
    —Ralph Waldo Emerson (1803–1882)