# New Technology

Trending Technology Machine Learning, Artificial Intelligent, Block Chain, IoT, DevOps, Data Science

## Search This Blog

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.