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

SVM 회귀의 수학적 정식화

개요

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

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

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

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

다음 선형 함수를 구하고

$f (x) = x' β + b,$

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

$J (β) = \frac{1}{2} β' β$

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

$\forall n : | y_{n} - (x_{n}' β + b) | \leq ε 。$

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

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

$J (β) = \frac{1}{2} β' β + C \sum_{n = 1}^{N} (ξ_{n} + ξ_{n}^{*}),$

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

$\begin{array}{l} \forall n : y_{n} - (x_{n}' β + b) \leq ε + ξ_{n} \\ \forall n : (x_{n}' β + b) - y_{n} \leq ε + ξ_{n}^{*} \\ \forall n : ξ_{n}^{*} \geq 0 \\ \forall n : ξ_{n} \geq 0 。 \end{array}$

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

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

$L_{ε} = {\begin{array}{l} 0 & if | y - f (x) | \leq ε \\ | y - f (x) | - ε & otherwise \end{array}$

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

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

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

$L (α) = \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} (α_{i} - α_{i}^{*}) (α_{j} - α_{j}^{*}) x_{i}' x_{j} + ε \sum_{i = 1}^{N} (α_{i} + α_{i}^{*}) + \sum_{i = 1}^{N} y_{i} (α_{i}^{*} - α_{i})$

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

$\begin{array}{l} \sum_{n = 1}^{N} (α_{n} - α_{n}^{*}) = 0 \\ \forall n : 0 \leq α_{n} \leq C \\ \forall n : 0 \leq α_{n}^{*} \leq C 。 \end{array}$

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

$β = \sum_{n = 1}^{N} (α_{n} - α_{n}^{*}) x_{n} 。$

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

f (x) = \sum_{n = 1}^{N} (α_{n} - α_{n}^{*}) (x_{n}' x) + b 。

(1)

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

$\begin{array}{l} \forall n : α_{n} (ε + ξ_{n} - y_{n} + x_{n}' β + b) = 0 \\ \forall n : α_{n}^{*} (ε + ξ_{n}^{*} + y_{n} - x_{n}' β - b) = 0 \\ \forall n : ξ_{n} (C - α_{n}) = 0 \\ \forall n : ξ_{n}^{*} (C - α_{n}^{*}) = 0 。 \end{array}$

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

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

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

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

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

커널 이름	커널 함수
선형(내적)	$G (x_{j}, x_{k}) = x_{j}' x_{k}$
가우스	$G (x_{j}, x_{k}) = \exp (- {为 x_{j} - x_{k} 为}^{2})$
다항식	$G (x_{j}, x_{k}) = {(1 + x_{j}' x_{k})}^{q}$ , 여기서 q는 집합 {2,3,...}에 속합니다.

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

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

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

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

$L (α) = \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} (α_{i} - α_{i}^{*}) (α_{j} - α_{j}^{*}) G (x_{i}, x_{j}) + ε \sum_{i = 1}^{N} (α_{i} + α_{i}^{*}) - \sum_{i = 1}^{N} y_{i} (α_{i} - α_{i}^{*})$

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

$\begin{array}{l} \sum_{n = 1}^{N} (α_{n} - α_{n}^{*}) = 0 \\ \forall n : 0 \leq α_{n} \leq C \\ \forall n : 0 \leq α_{n}^{*} \leq C 。 \end{array}$

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

f (x) = \sum_{n = 1}^{N} (α_{n} - α_{n}^{*}) G (x_{n}, x) + b 。

(2)

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

$\begin{array}{l} \forall n : α_{n} (ε + ξ_{n} - y_{n} + f (x_{n})) = 0 \\ \forall n : α_{n}^{*} (ε + ξ_{n}^{*} + y_{n} - f (x_{n})) = 0 \\ \forall n : ξ_{n} (C - α_{n}) = 0 \\ \forall n : ξ_{n}^{*} (C - α_{n}^{*}) = 0 。 \end{array}$

SVM 회귀 최적화 문제 풀기

솔버 알고리즘

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

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

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

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

${(\nabla L)}_{n} = {\begin{matrix} \sum_{i = 1}^{N} (α_{i} - α_{i}^{*}) G (x_{i}, x_{n}) + ε - y_{n}, n \leq N \\ - \sum_{i = 1}^{N} (α_{i} - α_{i}^{*}) G (x_{i}, x_{n}) + ε + y_{n}, n > N \end{matrix} 。$

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

$\sum_{n = 1}^{N} (α_{i} - α^{*}) = 0$

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

수렴 조건

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

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

$Δ = \frac{J (β) + L (α)}{J (β) + 1},$

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