순차 최소 최적화

순차 최소 최적화

클래스	지원 벡터 머신 교육을 위한 최적화 알고리즘
최악의 경우 공연	O(n)

순차적 최소 최적화(SMO)는 SVM(Support-Vector Machine) 훈련 중에 발생하는 2차 프로그래밍(QP) 문제를 해결하기 위한 알고리즘이다.그것은 1998년 마이크로소프트 리서치에서 존 플랫에 의해 발명되었다.^[1]SMO는 교육 지원 벡터 기계에 널리 사용되며 인기 있는 LIBSVM 툴에 의해 구현된다.^[2][3]1998년 SMO 알고리즘의 출시는 SVM 교육에 대해 이전에 사용 가능했던 방법이 훨씬 더 복잡하고 값비싼 제3자 QP 해결사가 필요했기 때문에 SVM 커뮤니티에 많은 흥분을 불러일으켰다.^[4]

최적화 문제

데이터 집합(x₁, y₁), ..., (x_n, y_n)의 이진 분류 문제를 고려하십시오. 여기서 x는_i 입력 벡터이고 y_i ∈{-1, +1}는 이에 해당하는 이진 레이블이다.소프트 마진 지지 벡터 머신은 2차 프로그래밍 문제를 해결하여 훈련하는데, 다음과 같이 이중 형태로 표현된다.

${\displaystyle \max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha _{i}\alpha _{j},}$

대상:

${\displaystyle 0\leq \alpha _{i}\leq C,\quad {\mbox{ for }}i=1,2,\ldots,n,}$

${\displaystyle \sum _{i=1}^{n}y_{i}\reason _{i}=0}$

여기서 C는 SVM 하이퍼 파라미터, K(x_i, x)는_j 사용자가 제공하는 커널 함수, $\alpha {\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 변수는$$ 라그랑주 승수다.

알고리즘.

SMO는 위에서 설명한 최적화 문제를 해결하기 위한 반복 알고리즘이다.SMO는 이 문제를 가능한 가장 작은 하위 문제들로 세분화하여 분석적으로 해결한다.라그랑주 승수 ${\displaystyle {\alpha i}_{}}$ ${\$를 포함하는 선형 평등 제약 때문에 가능한 가장 작은 문제는 그러한 승수 두 개를 포함한다$.$그런 다음 두 $개$의 $α$ 1 {\$displaystyle \alpha$$\_${${\displaystyle {1\mathrm{}}_{}}$} 및$α$ 2 {\$displaystyle \alpha _{$2}}개의 경우 제약조건은 다음과 같이 감소한다$.$

${\displaystyle 0\leq \alpha _{1},\alpha _{2}\leq C,}$

${\displaystyle y_{1}\properties _{1}+y_{2}\properties _{2}=k,}$

그리고 이러한 감소된 문제는 분석적으로 해결될 수 있다: 최소 1차원 2차원의 함수를 찾아야 한다.${\displaystyle k}$ $[\displaystyle k}$은(는) 각 반복에 고정된 평등 제약 조건의 나머지 항에 대한 합계의 음수다.

알고리즘은 다음과 같이 진행된다.

1. 최적화 문제에 대한 KKT(Karush-Kuhn-Tucker) 조건을 위반하는$$ 라그랑주 승수 $\alpha {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}를 찾으십시오.
2. 두 번째 승수 ${\displaystyle {\alpha \mathrm{}}_{}}$ 2 ${\$}를 선택하고$$ 쌍$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{\alpha \mathrm{}}_{}}$ 2$){\displaystyle (\alpha _{1},\alpha _{2})$을 최적화하십시오$.$
3. 수렴될 때까지 1단계와 2단계를 반복하십시오.

모든 라그랑주 승수가 (사용자 정의 공차 내에서) KKT 조건을 만족하면 문제가 해결되었다.이 알고리즘은 수렴이 보장되지만, 융합 속도를 가속화하기 위해 경험적 접근법을 사용하여 승수 쌍을 선택한다.$\alpha {\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 및$$ ${\displaystyle {\alpha }_{}}$ j ${\$에 대해 n${\displaystyle }$($n{\displaystyle }$- ${\displaystyle 1}$)${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle n(n-1)/$2}이$($가$$) 가능한 선택 사항이 있으므로 이는 대용량 데이터 세트에 매우 중요하다$.$

관련 작업

대규모 SVM 학습 문제를 일련의 소규모 최적화 작업으로 분할하는 첫 번째 접근법은 Bernhard Boser, Isabel Guyon, Vladimir Vapnik에 의해 제안되었다.^[5]그것은 "청킹 알고리즘"으로 알려져 있다.알고리즘은 데이터의 무작위 부분 집합으로 시작하여 이 문제를 해결하고 반복적으로 최적성 조건을 위반하는 예를 추가한다.이 알고리즘의 한 가지 단점은 QP-problems 스케일링을 SV 개수로 해결할 필요가 있다는 점이다.실제 희박한 데이터 세트에서 SMO는 청킹 알고리즘보다 1000배 이상 빠를 수 있다.^[1]

1997년 E. 오수나, R. 프룬드, F. 지로시는 SVM에 대한 완전히 새로운 QP 알고리즘 세트를 제안하는 정리를 증명했다.^[6] 이 정리 덕분에 큰 QP 문제는 일련의 더 작은 QP 하위 문제로 분해될 수 있다.KKT(Karush-Kuhn-Tucker) 조건의 위반자를 항상 하나 이상 추가하는 일련의 QP 하위 문제가 수렴될 것으로 보장된다.청킹 알고리즘은 정리의 조건에 따르며, 따라서 수렴할 것이다.^[1]SMO 알고리즘은 Osuna 알고리즘의 특별한 사례로 볼 수 있는데, 최적화의 크기가 2이고 모든 단계에서 두 라그랑주 승수가 좋은 휴리스틱스를 통해 선택된 새로운 승수로 대체된다.^[1]

SMO 알고리즘은 Bregman 메서드 또는 행-액션 메서드라고 불리는 최적화 알고리즘 계열과 밀접하게 관련되어 있다.이 방법들은 선형 제약조건으로 볼록 프로그래밍 문제를 해결한다.그것들은 각각의 단계가 각각의 제약조건에 현재의 원초점을 투영하는 반복적인 방법이다.^[1]

참고 항목

• 커널 퍼셉트론

참조