SVM: Solution to the Dual Problem in Machine Learning

The SMO algorithm

The SMO algorithm can efficiently solve the dual problem. First we discuss Coordinate Ascent.
Coordinate Ascent

• Consider solving the unconstrained optimization problem:

                    max W (⍺1,⍺2,....,⍺n)

Loop until convergence: {
            for i = 1 to n {
                     ⍺i = arg max W (⍺1......,⍺i,....,⍺n)
             }
} 

Coordinate ascent

• Ellipses are the contours of the function.
• At each step, the path is parallel to one of the axes.

Sequential minimal optimization

• Constrained optimization :

• Question : Can we do coordinate along one direction at a time (i.e., hold all ⍺[-i] fixed, and update ⍺i?)

The SMO algorithm

• Choose a set of ⍺1's satisfying the constraints.
• ⍺1 is exactly determined by the other ⍺'s.
• We have to update at least two of them simultaneously to keep satisfying the constraints.

Repeat till convergence {

1. Select some pair ⍺i and ⍺j to update next (using a heuristic that tries to pick the two that will allow us to make the biggest progress towards the global maximum).
2. Re-optimize W(⍺) with respect to ⍺i and ⍺j , while holding all the other ⍺k's (k≠ i;j) fixed.

}
The update to ⍺i and ⍺j can be computed very efficiently.