순차적 최소 최적화

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 최적화 문제
3. 알고리즘
4. 관련 연구
참조

1. 개요

순차적 최소 최적화(SMO)는 이진 분류 문제의 소프트 마진 서포트 벡터 머신(SVM)을 학습하기 위한 반복적인 알고리즘이다. SMO는 라그랑주 승수를 포함하는 선형 등식 제약 조건 때문에, 두 개의 승수를 포함하는 가장 작은 하위 문제를 분석적으로 해결한다. 이 알고리즘은 카루쉬-쿤-터커(KKT) 조건을 위반하는 라그랑주 승수를 찾고, 두 번째 승수를 선택하여 최적화하는 과정을 반복하며, 모든 라그랑주 승수가 KKT 조건을 만족하면 종료된다. SMO는 베른하르트 보저, 이자벨 기용, 블라디미르 바프니크의 청킹 알고리즘과 오수나, 프로인트, 지로시의 정리와 관련이 있으며, 브레그만 방법과 같은 최적화 알고리즘군과도 연관된다.

더 읽어볼만한 페이지

서포트 벡터 머신 - 힌지 손실
힌지 손실은 주로 서포트 벡터 머신에서 사용되는 볼록 함수 형태의 손실 함수이며, 이진 분류, 다중 클래스 분류, 구조적 예측으로 확장될 수 있고, 미분 불가능한 지점을 가져 평활화된 버전이 사용되기도 한다.
최적화 알고리즘 및 방법 - 신뢰 영역
신뢰 영역 방법은 비선형 최적화에서 함수의 모델을 신뢰할 수 있는 영역 내에서만 사용하여 최적화를 수행하는 방법으로, 다양한 분야에서 전역 최적해를 찾기 위한 도구로 활용된다.
최적화 알고리즘 및 방법 - 확률적 계획법
확률적 계획법은 불확실한 상황에서 최적의 의사 결정을 내리기 위한 수학적 방법론으로, 다양한 확률적 프로그래밍 기법을 포함하며, 생물학, 경제, 금융 공학 등 여러 분야에 응용된다.
토막글 틀에 과도한 변수를 사용한 문서 - 전향
전향은 종교적 개종이나 노선 변경을 의미하며, 근대 이후 정치적 이념 변화를 지칭하는 용어로 확장되어 개인의 신념 변화, 정치적 압력 등 다양한 요인으로 발생하며, 사회주의·공산주의로부터의 전향, 전향 문학, 냉전 시대 이후의 전향 현상 등을 폭넓게 논의한다.
토막글 틀에 과도한 변수를 사용한 문서 - 포토마스크
포토마스크는 반도체, 디스플레이, 인쇄 회로 기판 제조 시 웨이퍼에 회로 패턴을 전사하는 마스크로, 기술 발전을 거듭하며 융용 실리카 기판과 금속 흡수막을 사용하고 위상 천이 마스크, EUV 마스크 등의 고급 기술이 개발되어 반도체 미세화에 기여하고 있지만, 높은 제작 비용과 기술적 어려움은 해결해야 할 과제이다.

순차적 최소 최적화
개요
종류	최적화 알고리즘
사용 분야	서포트 벡터 머신 훈련
세부 사항
시간 복잡도	O(n³)
공간 복잡도	해당 사항 없음

2. 최적화 문제

이진 분류 문제에서 데이터 세트 (''x''₁, ''y''₁), ..., (''x''_''n'', ''y''_''n'')를 고려한다. 여기서 ''x''_''i''는 입력 벡터이고, ''y''_''i'' ∈ {-1, +1}는 해당 이진 레이블이다. 소프트 마진 서포트 벡터 머신(SVM)은 다음의 쌍대 문제로 표현되는 이차 계획법 문제를 풀어 학습된다.

: $\max_{\alpha} \sum_{i=1}^n \alpha_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j K(x_i, x_j) \alpha_i \alpha_j,$

:조건:

: $0 \leq \alpha_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,$

: $\sum_{i=1}^n y_i \alpha_i = 0$

여기서 ''C''는 SVM의 하이퍼파라미터이고 ''K''(''x''_''i'', ''x''_''j'')는 커널 함수이며, 둘 다 사용자가 제공한다. 변수 $\alpha_i$ 는 라그랑주 승수이다.

3. 알고리즘

순차적 최소 최적화(SMO)는 최적화 문제를 풀기 위한 반복적인 알고리즘이다. SMO는 이 문제를 일련의 가능한 가장 작은 하위 문제로 나누고, 이를 분석적으로 해결한다. 라그랑주 승수 $\alpha_i$ 를 포함하는 선형 등식 제약 조건 때문에, 가능한 가장 작은 문제는 두 개의 승수를 포함한다. 그러면 두 개의 승수 $\alpha_1$ 과 $\alpha_2$ 에 대해 제약 조건은 다음과 같이 축소된다.

: $0 \leq \alpha_1, \alpha_2 \leq C,$

: $y_1 \alpha_1 + y_2 \alpha_2 = k,$

이 축소된 문제는 분석적으로 해결할 수 있다. 즉, 1차원 이차 함수의 최솟값을 찾아야 한다. $k$ 는 각 반복에서 고정되는 등식 제약 조건의 나머지 항들의 합의 음수이다.

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

# 최적화 문제에 대한 카루쉬-쿤-터커(KKT) 조건을 위반하는 라그랑주 승수 $\alpha_1$ 을 찾는다.

# 두 번째 승수 $\alpha_2$ 를 선택하고 쌍 $(\alpha_1,\alpha_2)$ 를 최적화한다.

# 수렴할 때까지 1단계와 2단계를 반복한다.

모든 라그랑주 승수가 KKT 조건을 (사용자가 정의한 허용 오차 내에서) 만족하면 문제가 해결된 것이다. 이 알고리즘은 수렴이 보장되지만, 수렴 속도를 가속화하기 위해 승수 쌍을 선택하는 데 휴리스틱이 사용된다. 이는 $n(n-1)/2$ 개의 $\alpha_i$ 와 $\alpha_j$ 선택이 가능하므로 대규모 데이터 세트의 경우 중요하다.

4. 관련 연구

베른하르트 보저, 이자벨 기용, 블라디미르 바프니크는 대규모 SVM 학습 문제를 일련의 더 작은 최적화 작업으로 분할하는 "청킹 알고리즘"을 제안했다.^[5] 이 알고리즘은 데이터의 임의 하위 집합으로 시작하여 최적성 조건을 위반하는 예제를 반복적으로 추가하는 방식으로 작동한다. 그러나 이 알고리즘은 SV의 수에 따라 크기가 조정되는 QP 문제를 해결해야 하는 단점이 있다. 실제 희소 데이터 세트에서 SMO는 청킹 알고리즘보다 1000배 이상 빠를 수 있다.^[1]

1997년, E. 오수나, R. 프로인트, F. 지로시는 SVM에 대한 새로운 QP 알고리즘 세트를 제시하는 정리를 증명했다.^[6] 이 정리에 따라 대규모 QP 문제는 일련의 더 작은 QP 하위 문제로 분해될 수 있으며, Karush–Kuhn–Tucker (KKT) 조건을 위반하는 사례를 항상 하나 이상 추가하는 QP 하위 문제는 수렴이 보장된다. 청킹 알고리즘은 이 정리의 조건을 준수하므로 수렴된다.^[1] SMO 알고리즘은 최적화 크기가 2이고 모든 단계에서 두 개의 라그랑주 승수가 좋은 휴리스틱을 통해 선택된 새로운 승수로 대체되는 오수나 알고리즘의 특수한 경우로 간주될 수 있다.^[1]

SMO 알고리즘은 브레그만 방법 또는 행렬 작용 방법이라고 불리는 최적화 알고리즘군과 밀접하게 관련되어 있다. 이 방법들은 선형 제약 조건이 있는 볼록 프로그래밍 문제를 해결하며, 각 단계에서 현재의 주점(primal point)을 각 제약 조건에 투영하는 반복적인 방법들이다.^[1]

참조

_[1] 웹사이트 Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines https://www.microsof[...]
_[2] 논문 LIBSVM: A library for support vector machines
_[3] 웹사이트 Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems http://jmlr.csail.mi[...] 2006
_[4] 학위논문 Everything Old is New Again: a Fresh Look at Historical Approaches in Machine Learning Massachusetts Institute of Technology
_[5] 서적 Proceedings of the fifth annual workshop on Computational learning theory - COLT '92
_[6] 서적 Neural Networks for Signal Processing [1997] VII. Proceedings of the 1997 IEEE Workshop
_[7] Citation Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines
_[8] 논문 LIBSVM: A library for support vector machines
_[9] 문서 Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems http://jmlr.csail.mi[...] Luca Zanni 2006
_[10] 간행물 Everything Old is New Again: a Fresh Look at Historical Approaches in Machine Learning https://hdl.handle.n[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com