The SMO algorithm

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

Coordinate Ascent

Loop until convergence: {

for i = 1 to n {

⍺i = arg max W (⍺1......,⍺i,....,⍺n)

}

}

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

Coordinate Ascent

- Consider solving the unconstrained optimization problem:

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.

- 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).
- 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.

## No comments:

## Post a Comment