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

Recent Post

Codecademy Code Foundations

Search This Blog

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.

No comments:

Post a Comment

Popular Articles