[ на главную ]

Классификатор на основе машины опорных векторов.
SVM/SMO

Евгений Борисов

Среда, 26 Июня 2013 г.


В этой статье мы поговорим о модели, которая носит название машина опорных векторов (support vector machines, SVM) [ 1 ] , этот метод также называют - классификатор с максимальным зазором. Рассмотрим сам классификатор и метод его обучения – sequential minimal optimization (SMO).


1 Ведение

SVM-классификатор реализует бинарную классификацию, т.е. разделяет множество входных векторов на две части: положительный-отрицательный, свои-чужие, да-нет и т.п.

Прежде чем классификатор начнёт работать его необходимо обучить на множестве специально подобранных учебных примеров, которое состоит из двух частей - положительные (условно) примеры и отрицательные примеры. В данном случае применяется подход "обучение с учителем т.е. каждый учебный пример представляет собой пару <учебный вход, правильный ответ> . Применяется алгоритм обучения (о нём мы поговорим ниже), который изменяет параметры SVM, подстраиваясь под учебный набор.

Неформально работу алгоритма обучения SVM можно писать следующим образом. Алгоритм обучения находит среди элементов учебного множества точки, лежащие на границе двух подмножеств (положительного и отрицательного) и строит между этими точками разделяющую поверхность. В терминах SVM такие точки называются опорными векторами.


Рис. 1: описание работы SVM


SVM, помимо всего прочего, обладает интересной особенностью, эта система модульная, она содержит в себе т.н. функцию ядра, заменяя которую можно менять характеристики классификатора.


2 Модель

Классификатор описывается следующими соотношениями

где w 0 – порог (свободный член); λ i – коэффициент; x i ,y i – пара из учебного набора, (векторы x i , для которых λ i > 0 называются опорными); K ( x i ,x ) – функция ядра

Машина опорных векторов отображает входной вектор в пространство более высокой размерности и находит разделяющую гиперплоскость с максимальным зазором между точками разных классов. Отображение это осуществляется с помощью функции ядра.

Изначально SVM это линейный классификатор, т.е. он может решать только линейно разделимые задачи. Однако, применяя нелинейное ядро, можно отобразить исходные данные в пространство большей размерности, где уже может существовать оптимальная разделяющая гиперплоскость.


Рис. 2: начальный набор данных - линейно неразделимая задача
Рис. 3: результат работы - линейно разделимая задача


Функция ядра должна удовлетворять специальным условиям [ 2 ] , примеры таких функций приведены ниже.

Обучение SVM сводится к нахождению коэффициентов λ (множителей Лангранжа) и w 0 . Найти их можно решив следующую задачу квадратичной оптимизации.

        ∑l      1 ∑l  ∑l L (λ ) =    λi − 2-       λiλjyiyjK (xi,xj) → maxλ i=1        i=1 j=1
при ограничениях
( |  ∑l {     λiyi = 0 |  i=1 ( 0 ≤ λ  ≤ C  ; C = const i

Для решения этой задачи можно применять разные методы, ниже мы рассмотрим алгоритм sequential minimal optimization (SMO) [ 3 ] .


3 SMO – sequential minimal optimization

Есть три составляющих SMO:

  1. эвристический выбор двух множителей λ j , λ i для оптимизации,
  2. аналитический метод решения для двух множителей λ j , λ i ,
  3. и метод вычисления w 0

3.1 общая схема алгоритма SMO

  1. инициировать λ значениями, удовлетворяющими ограничениям
  2. по определённым правилам,
    выбрать первый коэффициент λ j для оптимизации
  3. в зависимости от λ j ,
    выбрать второй коэффициент λ i для оптимизации
  4. оптимизировать пару λ i , λ j
    вычислить новое значение порога w 0
  5. если параметры системы изменились
    то переход на п. 2
    иначе переход на следующий пункт
  6. конец работы

3.2 основная часть

  1. инициировать λ значениями, удовлетворяющими ограничениям
    ( например k : λ k := 0 , w 0 := 0 , C := 10 )
  2. построить очередь из примеров учебной выборки
  3. выбрать первый в очереди пример,

    выполнить процедуру обработки учебного примера (разд. 3.3 ),

    сдвинуть очередь

  4. если есть не обработанные примеры из очереди
    то переход на п. 3
    иначе переход на следующий пункт
  5. если процедура обработки примера изменила параметры
    то переход на на следующий пункт
    иначе переход на п. 10
  6. построить очередь из примеров учебной выборки,
    для которых выполняется 0 < λ k < C
  7. выбрать первый в очереди пример,

    выполнить процедуру обработки учебного примера (разд. 3.3 ),

    сдвинуть очередь

  8. если есть не обработанные примеры из очереди
    то переход на п. 7
    иначе переход на следующий пункт
  9. если процедура обработки примера изменила параметры
    то переход на п. 6
    иначе переход на п. 2
  10. конец работы

3.3 алгоритм обработки учебного примера j

  1. вычислить ошибку E j на учебном примере j

          { E ′; 0 < λj < C Ej :=            j u(xj) − yj ; (λj ≤ 0) ∨ (λj ≥ C )
    где E – error cache

  2. проверка на нарушение λ j условий KKT :

     τ :=  0.001 rj :=  Ejyj

    если ((rj < − τ) ∧ (λj < C )) ((rj > τ) ∧ (λj > 0))
    то переход на следующий пункт
    иначе переход на п. 5

  3. выполнить процедуру поиска второго элемента пары λ i (разд. 3.4 )
  4. если параметры изменились
    то переход на п. 6
    иначе переход на следующий пункт
  5. нет изменений, конец работы
  6. параметры изменены, конец работы

3.4 алгоритм поиска второго элемента пары λ i для оптимизации

  1. построить очередь из λ ,
    для которых выполняется 0 < λ k < C
  2. если очередь пустая (не содержит элементов)
    то переход на п. 8
    иначе переход на следующий пункт
  3. среди элементов очереди найти λ i , для которой max i | E j E i |
  4. выполнить процедуру оптимизации для λ j i (разд. 3.5 )

    если параметры изменились
    то переход на п. 13
    иначе переход на следующий пункт

  5. перемешать элементы очереди случайным образом
  6. выбрать первый в очереди λ i ,

    выполнить процедуру оптимизации для λ j i (разд. 3.5 )

    сдвинуть очередь

    если параметры изменились
    то переход на п. 13
    иначе переход на следующий пункт

  7. если есть не обработанные примеры из очереди
    то переход на п. 6
    иначе переход на следующий пункт
  8. построить очередь из λ ,
    перемешать элементы очереди случайным образом
  9. выбрать первый в очереди λ i ,

    выполнить процедуру оптимизации для λ j i (разд. 3.5 )

    сдвинуть очередь

  10. если параметры изменились
    то переход на п. 13
    иначе переход на следующий пункт
  11. если есть не обработанные примеры из очереди
    то переход на п. 9
    иначе переход на следующий пункт
  12. нет изменений, конец работы
  13. параметры изменены, конец работы

3.5 алгоритм оптимизации пары λ j , λ i

  1. если i = j
    то переход на п. 12
    иначе переход на следующий пункт
  2. вычислить значение L и H

    если y i = y j
    то

    γ :=  λi + λj

    ⌊{ L := γ − C ||  H  := C        ; γ > C |{ |⌈   L := 0 ; γ ≤ C H  := γ

    иначе

    γ :=  λ − λ i    j

      { ⌊   L := 0 |                 ; γ > 0 |   H := C  − γ || { ⌈   L := − γ      ; γ ≤ 0 H := C

  3. если L = H
    то переход на п. 12
    иначе переход на следующий пункт
  4. вычислить значение ошибок и параметра η :

          {          ′ E j ; 0 < λj < C Ej :=   u(x ) − y ; (λ ≤  0) ∨ (λ ≥ C ) {    j     j    j          j E ′i ; 0 < λi < C Ei := u(xi) − yi ; (λi ≤ 0) ∨ (λi ≥ C)
    где E – error cache

    η :=  2Kij − Kii − Kjj
    где K ij = K ( x i ,x j ) – функция ядра

  5. вычислить новое значение λ j :

    если η < 0
    то

     ′                    1 λj :=  λj − yj(Ei − Ej )η-

          ( | H  ; λ′j ≥ H ′′   {   ′        ′ λ j := | λ j ; L < λ j < H (  L ; λ′ ≤ L j

    иначе

     𝜀 := 0.001 c1 := η∕2 c2 := yj(Ei − Ej) − ηλj L ′ := c1L2 + c2L ′       2 H  := c1H  +  c2H

          (       ′    ′ |{ L  ; L > H  +  𝜀 λ′′j :=    λj ; H ′ − 𝜀 ≤ L′ ≤ H ′ + 𝜀 |(       ′    ′ H  ; L < H  −  𝜀

  6. если | λ j ′′ λ j | < 𝜀 ( λ j ′′ + λ j + 𝜀 )
    то переход на п. 12
    иначе переход на следующий пункт
  7. вычислить новое значение λ i
     s := yi ⋅ yj λ′i := λi + s ⋅ (λ′′j − λj)
    если λ i < 0
    то
    λ ′′:= s ⋅ λ′ j′′       i λ i := 0
    иначе если λ i > C
    λ′j′:= s ⋅ (λ′i − C ) ′′ λi := C
    иначе
     ′′     ′ λi :=  λi
  8. вычислить новое значение порога w 0

                        ′′               ′′ b1 :=  w0 + Ei + yi(λi − λi)Kii + yj(λj − λj)Kij b2 :=  w0 + Ej + yi(λ′i′− λi)Kij + yj(λ′′j − λj)Kjj b3 :=  (b1 + b2)∕2

          ( | b1 ; 0 < λ′i′< C ′′   {            ′′ w 0 := | b2 ; (0 < λj < C ) ∧ ((λi ≤ 0) ∨ (λi ≥ C )) ( b3 ; ((λi ≤ 0 ) ∨ (λi ≥ C )) ∧ ((λj ≤ 0) ∨ (λj ≥ C ))

    Δw0  :=  w′0′− w0

  9. выполнить процедуру обновления error cache (разд. 3.6 )
  10. обновить значения параметров

  11. параметры изменены, конец работы
  12. нет изменений, конец работы

3.6 алгоритм обновления error cache

  1. tj :=  yj(λ′′−  λj) j′′ ti := yi(λ i − λi)
  2. построить очередь из примеров учебной выборки,
    для которых 0 < λ k < C
  3. выбрать первый в очереди пример (с индексом k в списке примеров)

    Ek′:= E ′k + tjKjk + tiKik − Δw0

    сдвинуть очередь

  4. если есть не обработанные примеры из очереди
    то переход на п. 3
    иначе переход на следующий пункт
  5. E i := 0 ; E j := 0
  6. конец работы

4 Реализация

В этом разделе представлена реализация, описанных выше моделей SVM и метода обучения SMO.


Пример работы SVM с линейно разделимым набором данных, используется линейное ядро.
Рис. 4: учебные наборы и опорные векторы, найденные SMO

Рис. 5: тестовый набор данных
Рис. 6: результат работы SVM


Пример работы SVM с линейно неразделимым набором данных, в качестве функции ядра используется Gaussian kernel.
Рис. 7: учебные наборы и опорные векторы, найденные SMO

Рис. 8: тестовый набор данных
Рис. 9: результат работы SVM


Реализация в системе Octave [ здесь ].



Список литературы

[1] Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979

[2] Воронцов К.В. Метод опорных векторов

[3] John C. Platt  Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines // Microsoft Research, Technical Report MSR-TR-98-14, April 21, 1998

[4] GNU Octave – http://www.gnu.org/software/octave/

При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.