Main Content

이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

서포트 벡터 머신 회귀 이해하기

SVM 회귀의 수학적 정식화

개요

서포트 벡터 머신(SVM) 분석은 분류 및 회귀에 많이 사용되는 머신러닝 도구이며, 블라디미르 배프니크(Vladimir Vapnik)와 그의 동료에 의해 1992년에 최초로 정립되었습니다[5]. SVM 회귀는 커널 함수를 기반으로 하므로 비모수적 기법으로 간주됩니다.

Statistics and Machine Learning Toolbox™는 선형 엡실론 무시 SVM(ε-SVM) 회귀를 구현하며, 이는 L1 손실이라고도 합니다. ε-SVM 회귀에서 훈련 데이터 세트는 예측 변수와 관측된 응답 변수 값을 포함합니다. 각 훈련 점 x에 대해 ε보다 크지 않은 값만큼 yn에서 벗어나며, 이와 동시에 최대로 평탄한 함수 f(x)를 구하는 것이 목적입니다.

선형 SVM 회귀: 원문제(Primal) 식

훈련 데이터 세트를 가정하겠습니다. 여기서 xn은 관측된 응답 변수 값 yn을 갖는 N개의 관측값으로 구성된 다변량 집합입니다.

다음 선형 함수를 구하고

f(x)=xβ+b,

이 함수가 최대한 평탄하도록, 최소 노름 값(β′β)을 갖는 f(x)를 구합니다. 이는 다음을 최소화하는 볼록 최적화 문제로 정식화됩니다.

J(β)=12ββ

여기에는 모든 잔차가 ε보다 작은 값을 갖는다는 조건이 적용되며, 이를 수식 형태로 나타내면 다음과 같습니다.

n:|yn(xnβ+b)|ε.

모든 점에 대해 이러한 제약 조건을 충족하는 함수 f(x)가 존재하지 않을 수 있습니다. 존재하지 않을 경우 실현불가능 제약 조건을 처리하려면 각 점에 대해 여유 변수 ξnξ*n을 추가하십시오. 여유 변수가 필수 조건을 여전히 충족하면서 ξn 값 및 ξ*n 값까지 회귀 오차를 허용하므로 이 방식은 SVM 분류의 “소프트 마진” 개념과 유사합니다.

여유 변수를 포함시키면 목적 함수가 생성되며, 이를 원문제 식이라고도 합니다[5].

J(β)=12ββ+Cn=1N(ξn+ξn*),

여기에는 다음 조건이 적용됩니다.

n:yn(xnβ+b)ε+ξnn:(xnβ+b)ynε+ξn*n:ξn*0n:ξn0.

상수 C는 상자 제약 조건으로, 엡실론 마진(ε) 외부에 있는 관측값에 부과되는 벌점을 제어하고 과적합을 방지(정규화)하는 데 도움이 되는 양수 값입니다. 이 값에 따라 f(x)의 평탄한 정도와 편차가 ε보다 얼마나 더 커도 될지 간의 상호 절충 관계가 결정됩니다.

선형 ε-무시 손실 함수는 관측값으로부터 ε 거리 내에 있는 오차를 0과 같다고 간주하여 무시합니다. 손실은 관측값 y와 ε 경계 간의 거리를 기준으로 측정됩니다. 이는 공식적으로 다음으로 설명됩니다.

Lε={0if |yf(x)|ε|yf(x)|εotherwise

선형 SVM 회귀: 쌍대 문제(Dual) 식

앞에서 설명한 최적화 문제는 라그랑주 쌍대 문제 정식화로 푸는 것이 계산량 측면에서 더 간단합니다. 쌍대 문제의 해는 원문제(최소화)의 해에 대한 하한을 제공합니다. 원문제와 쌍대 문제의 최적 값은 같을 필요가 없으며, 그 차이를 “쌍대 격차”이라고 합니다. 그러나 볼록 문제이고 제약 조건의 검증 조건(CQC, constraint qualification condition)을 충족하는 경우 원문제의 최적해 값은 쌍대 문제의 해에서 얻어집니다.

쌍대 문제 식을 얻으려면 각 관측값 xn에 대해 음이 아닌 승수 αnα*n을 추가하여 원문제 함수에서 라그랑주 함수를 생성하십시오. 그러면 다음을 최소화하는 쌍대 문제 식이 생성됩니다.

L(α)=12i=1Nj=1N(αiαi*)(αjαj*)xixj+εi=1N(αi+αi*)+i=1Nyi(αi*αi)

이때 제약 조건은 다음과 같습니다.

n=1N(αnαn*)=0n:0αnCn:0αn*C.

β 파라미터는 다음 방정식을 사용하여 훈련 관측값의 일차 결합으로 완전히 설명될 수 있습니다.

β=n=1N(αnαn*)xn.

새 값을 예측하는 데 사용되는 함수는 서포트 벡터에만 종속됩니다.

f(x)=n=1N(αnαn*)(xnx)+b.(1)

카루쉬-쿤-터커(KKT) 상보성 조건은 최적해를 구하는 데 필요한 최적화 제약 조건입니다. 선형 SVM 회귀의 경우 이 조건은 다음과 같습니다.

n:αn(ε+ξnyn+xnβ+b)=0n:αn*(ε+ξn*+ynxnβb)=0n:ξn(Cαn)=0n:ξn*(Cαn*)=0.

이 조건은 엡실론 튜브 안쪽(즉, 경계 불포함)에 있는 모든 관측값이 라그랑주 승수 αn = 0αn* = 0을 가진다는 것을 나타냅니다. αn 또는 αn*이 0이 아닌 경우 대응되는 관측값을 서포트 벡터라고 합니다.

훈련된 SVM 모델의 속성 Alpha는 서포트 벡터의 두 라그랑주 승수 사이의 차이, 즉 αn – αn*을 저장합니다. 속성 SupportVectorsBias는 각각 xn과 b를 저장합니다.

비선형 SVM 회귀: 원문제(Primal) 식

일부 회귀 문제는 선형 모델을 사용하여 적절히 기술할 수 없습니다. 이 경우, 라그랑주 쌍대 문제 정식화를 사용하면 이전에 설명한 기법이 비선형 함수로 확장될 수 있습니다.

내적 x1′x2를 비선형 커널 함수 G(x1,x2) = <φ(x1),φ(x2)>로 바꿔서 비선형 SVM 회귀 모델을 구합니다. 여기서 φ(x)는 x를 고차원 공간으로 매핑하는 변환입니다. Statistics and Machine Learning Toolbox는 다음과 같은 내장 준정부호 커널 함수를 제공합니다.

커널 이름커널 함수
선형(내적)G(xj,xk)=xjxk
가우스G(xj,xk)=exp(xjxk2)
다항식G(xj,xk)=(1+xjxk)q, 여기서 q는 집합 {2,3,...}에 속합니다.

그람 행렬은 요소 gi,j = G(xi,xj)를 포함하는 nxn 행렬입니다. 각 요소 gi,j는 φ로 변환될 때 예측 변수의 내적과 같습니다. 그러나, 커널 함수를 사용하여 그람 행렬을 직접 생성할 수 있으므로 φ를 몰라도 상관없습니다. 이 방법을 사용하여 비선형 SVM은 변환된 예측 변수 공간에서 최적 함수 f(x)를 구합니다.

비선형 SVM 회귀: 쌍대 문제(Dual) 식

비선형 SVM 회귀에 대한 쌍대 문제 식은 예측 변수의 내적(xi′xj)을 그람 행렬(gi,j)의 대응하는 요소로 바꿉니다.

비선형 SVM 회귀는 다음을 최소화하는 계수를 구합니다.

L(α)=12i=1Nj=1N(αiαi*)(αjαj*)G(xi,xj)+εi=1N(αi+αi*)i=1Nyi(αiαi*)

여기에는 다음 조건이 적용됩니다.

n=1N(αnαn*)=0n:0αnCn:0αn*C.

새 값을 예측하는 데 사용되는 함수는 다음과 같습니다.

f(x)=n=1N(αnαn*)G(xn,x)+b.(2)

KKT 상보성 조건은 다음과 같습니다.

n:αn(ε+ξnyn+f(xn))=0n:αn*(ε+ξn*+ynf(xn))=0n:ξn(Cαn)=0n:ξn*(Cαn*)=0.

SVM 회귀 최적화 문제 풀기

솔버 알고리즘

최소화 문제는 표준 2차 계획법 형식으로 표현할 수 있으며 일반적인 2차 계획법을 사용하여 풀 수 있습니다. 그러나, 특히 그람 행렬이 메모리에 저장하기에 너무 클 수 있으므로 2차 계획법 알고리즘을 사용하는 경우 많은 계산이 필요할 수 있습니다. 분해 방법을 대신 사용하면 계산 속도를 높이고 메모리 부족 문제를 방지할 수 있습니다.

분해 방법(청크 설정 및 워킹 세트 방법이라고도 함)은 모든 관측값을 두 개의 서로소 집합인 워킹 세트와 나머지 세트로 구분합니다. 분해 방법은 각 반복마다 워킹 세트에 있는 요소만 수정합니다. 따라서, 각 반복마다 그람 행렬의 일부 열만 필요하므로 각 반복에 필요한 저장 공간이 줄어듭니다.

순차적 최소규모 최적화(SMO)는 SVM 문제를 푸는 데 가장 많이 사용되는 방법입니다[4]. SMO는 일련의 2점 최적화를 수행합니다. 각 반복마다, 2차 정보를 사용하는 선택 규칙에 따라 두 점으로 구성된 워킹 세트가 선택됩니다. 그런 다음, 이 워킹 세트에 대한 라그랑주 승수는 [2][1]에서 설명한 접근 방식을 사용하여 해석적으로 풉니다.

SVM 회귀에서 활성 세트의 기울기 벡터 L은 각 반복 후에 업데이트됩니다. 기울기 벡터에 대해 분해된 방정식은 다음과 같습니다.

(L)n={i=1N(αiαi*)G(xi,xn)+εyn,nNi=1N(αiαi*)G(xi,xn)+ε+yn,n>N.

반복 단일 데이터 알고리즘(ISDA)은 각 반복마다 하나의 라그랑주 승수를 업데이트합니다[3]. ISDA는 대개 작은 양의 상수 a를 커널 함수에 추가하는 방식으로 편향 항 b 없이 수행됩니다. 쌍대 문제 방정식에서 b를 생략하면 다음과 같이

n=1N(αiα*)=0

합계 제약 조건이 제거됩니다. 그러면 각 반복마다 라그랑주 승수를 업데이트할 수 있으며, 따라서 이상값을 제거하기가 SMO보다 더 쉽습니다. ISDA는 모든 αnαn* 값 중에서 가장 나쁜 KKT 이탈값을 업데이트할 워킹 세트로 선택합니다.

수렴 조건

이러한 솔버 알고리즘 각각은 지정된 공분산 조건이 충족할 때까지 반복적으로 계산을 수행합니다. 공분산 조건에 대한 여러 가지 옵션이 있습니다.

  • 실현가능성 격차 — 실행가능성 격차는 다음과 같이 표현됩니다.

    Δ=J(β)+L(α)J(β)+1,

    여기서 J(β)는 원문제 목적 함수이고 L(α)는 쌍대 문제 목적 함수입니다. 각 반복을 마칠 때마다 실현가능성 격차가 계산됩니다. 실현가능성 격차가 GapTolerance로 지정된 값보다 작을 경우 알고리즘이 공분산 조건을 충족하는 것이므로 소프트웨어가 해를 반환합니다.

  • 기울기 차이 — 각 반복을 마칠 때마다 기울기 벡터 L이 계산됩니다. 현재 반복과 이전 반복의 기울기 벡터 값의 차이가 DeltaGradientTolerance로 지정된 값보다 작을 경우 알고리즘이 공분산 조건을 충족하는 것이므로 소프트웨어가 해를 반환합니다.

  • 최대 KKT 위반 — 각 반복을 마칠 때마다 모든 αnαn* 값에 대한 KKT 위반이 계산됩니다. 최대 위반이 KKTTolerance로 지정된 값보다 작을 경우 알고리즘이 공분산 조건을 충족하는 것이므로 소프트웨어가 해를 반환합니다.

참고 문헌

[1] Fan, R.E. , P.H. Chen, and C.J. Lin. A Study on SMO-Type Decomposition Methods for Support Vector Machines. IEEE Transactions on Neural Networks, 17:893–908, 2006.

[2] Fan, R.E. , P.H. Chen, and C.J. Lin. Working Set Selection Using Second Order Information for Training Support Vector Machines. The Journal of machine Learning Research, 6:1871–1918, 2005.

[3] Huang, T.M., V. Kecman, and I. Kopriva. Kernel Based Algorithms for Mining Huge Data Sets: Supervised, Semi-Supervised, and Unsupervised Learning. Springer, New York, 2006.

[4] Platt, J. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Technical Report MSR-TR-98–14, 1999.

[5] Vapnik, V. The Nature of Statistical Learning Theory. Springer, New York, 1995.

참고 항목

| | |

관련 항목