구조화된 서포트 벡터 머신

구조화된 Support-Vector 머신은 Support-Vector Machine(SVM) 분류기를 일반화하는 기계 학습 알고리즘입니다.SVM 분류기는 바이너리 분류, 멀티 클래스 분류 및 회귀를 지원하는 반면, 구조화된 SVM은 일반적인 구조화된 출력 라벨에 대한 분류기의 훈련을 허용합니다.

예를 들어 샘플인스턴스는 자연어 문장이며 출력라벨은 주석이 달린 해석 트리입니다.분류기 훈련은 올바른 샘플과 출력 라벨 쌍의 쌍으로 구성됩니다.훈련 후 구조화된 SVM 모델을 통해 새로운 샘플인스턴스에 대응하는 출력 라벨을 예측할 수 있습니다.즉, 자연어 문장이 주어지면 분류자는 가장 가능성이 높은 해석 트리를 생성할 수 있습니다.

트레이닝

${\$ \ $displaystyle \ell$ $({\boldsymbol {x}}_{n},y_{n})\in {\mathcal {X}}\times {\mathcal {Y}}$ $（$ $({\boldsymbol {x}}_{n},y_{n})\in {\mathcal {X}}\times {\mathcal {Y}}$ , $({\boldsymbol {x}}_{n},y_{n})\in {\mathcal {X}}\times {\mathcal {Y}}$ ) $({\boldsymbol {x}}_{n},y_{n})\in {\mathcal {X}}\times {\mathcal {Y}}$ $({\boldsymbol {x}}_{n},y_{n})\in {\mathcal {X}}\times {\mathcal {Y}}$ × $({\boldsymbol {x}}_{n},y_{n})\in {\mathcal {X}}\times {\mathcal {Y}}$ Y ( \ $bold symbol$ { x $} _$ { $n$ } , y $_$ { $n$ } ) \ $in$ \ $mathcal$ { Y } \ times \ $mathcal$ { $Y$ ) 、 ${\mathcal {X}}$ $= 1$ , $...$ , \ $display style$ $splaystyle$ {\ $mathcal {Y$ 구조화된 SVM은 다음과 같은 정규화된 위험 함수를 최소화합니다.

{\boldsymbol {w} {\min}} \coldsymbol {w} + C \sum _ {n=1}^{\ell } {\underset {y} {\max }}\left(0,\Delta(y_n}) {\comboldsy

함수는 아핀 함수 집합의 최대값이 볼록하므로 w $\$ 에서 ${\boldsymbol {w}}$ 볼록합니다.함수 $\Delta :{\mathcal {Y}}\times {\mathcal {Y}}\to \mathbb {R} _{+}$ : $\Delta :{\mathcal {Y}}\times {\mathcal {Y}}\to \mathbb {R} _{+}$ Y × $\Delta :{\mathcal {Y}}\times {\mathcal {Y}}\to \mathbb {R} _{+}$ $\Delta :{\mathcal {Y}}\times {\mathcal {Y}}\to \mathbb {R} _{+}$ + {\ $displaystyle \Delta$ : {\ $mathcal {Y}}\times$ {\ $mathcal {Y}}\times \mathbb$ { $R}$ _ ${+}}$ 는 $\Delta :{\mathcal {Y}}\times {\mathcal {Y}}\to {\mathbb {R}}_{+}$ 라벨 공간의 거리를 측정하고 $y, z$ 를 만족하는 임의의 함수(필수는 아님)입니다. $표시,$ \tay $le \Delta (y,y$ )= $0\;\forall$ y $,z\in$ { $mathcal {Y$ 함수 $\Psi :{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}$ : $\Psi :{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}$ X × $\Psi :{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}$ $\Psi :{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}$ $\Psi :{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}$ $\Psi :{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}$ \ $displaystyle$ \ $Psi$ : {\ $mathcal {X}}\times$ \ $mathcal {Y}\to$ \ $mathbb {R}$ 는 벡터 추출의 일부 기능입니다.이 기능의 설계는 응용 프로그램에 따라 크게 달라집니다.

위의 정규화된 리스크 함수는 미분할 수 없기 때문에 종종 각 샘플에 하나의 슬랙 변수 $\xi _{n}$ n $\xi _{n}$ \ $displaystyle \xi$ _ { $n}$ 을 $\xi _{n}$ 도입하여 2차 프로그램의 관점에서 재구성된다.표준 구조화된 SVM 기본 공식은 다음과 같습니다.

{\displaystyle {\boldsymbol {w}, {\boldsymbol {xi }}, {\min}}, {\boldsymbol {w}, {n=1}^{\ell}\xi _{n}\textrm {st}.}&\boldsymbol {w},\Psi({\boldsymbol {x}_{n},y_{n})\rangle -\psi({\boldsymbol {x}_{n},y})\rangle +\xi _{n}\Deltay(n},

추론

테스트 시 샘플 ${\boldsymbol {x}}\in {\mathcal {X}}$ X $(\$ in $(\mathcal$ {X $})$ 만 ${\boldsymbol {x}}\in {\mathcal {X}}$ 알려져 있으며, 예측 $f:{\mathcal {X}}\to {\mathcal {Y}}$ f: $f:{\mathcal {X}}\to {\mathcal {Y}}$ $f:{\mathcal {X}}\to {\mathcal {Y}}$ (\ $displaystyle$ f $:{\mathcal {X}}\to(\mathcal$ ${$ Y $}})$ 는 $f:{\mathcal {X}}\to {\mathcal {Y}}$ $레이블$ Y(\displaystyle ${Cal$ 에서 예측된 레이블에 매핑됩니다. ${\boldsymbol {w}}$ 을 통해 얻은 \style\ $boldsymbol$ {w $}$ 의 ${\boldsymbol {w}}$ ${\boldsymbol {w}}$ 예측 기능은 다음과 같습니다.

fboldsymbol {x}= 언더셋 {y\in\mathcal {Y}}{\textrm {symbol {w}},\Psi({\boldsymbol {x},y})\rangle

따라서 레이블 공간의 최대화기가 예측 레이블입니다.이 극대기에 대한 해결은 소위 추론 문제이며 확률론적 모델에서 최대 a-후열(MAP) 예측을 하는 것과 유사하다. $\Psi$ \ $displaystyle$ \ $Psi$ $\Psi$ 함수의 구조에 따라서는 맥시마이저를 풀기가 어려울 수 있습니다.

분리

위의 2차 프로그램은 매우 크고 아마도 무한대의 선형 부등식 제약 조건을 포함한다.일반적으로 불평등의 수는 너무 커서 명시적으로 최적화될 수 없다.대신, 제한의 유한하고 작은 부분 집합만 사용되는 지연된 제약 조건 생성을 사용함으로써 문제가 해결됩니다.제약 조건의 하위 집합에 대해 최적화하면 실현 가능한 집합이 확대되고 목표에 하한을 제공하는 솔루션이 생성됩니다. $displaystyle의$ 이 ${\boldsymbol {w}}$ $완전$ 한 집합 부등식의 제약을 위반하는지 여부를 테스트하기 위해서는 분리 문제를 해결해야 한다.부등식이 샘플별로 $({\boldsymbol {x}}_{n},y_{n})$ 되므로( x $({\boldsymbol {x}}_{n},y_{n})$ , $({\boldsymbol {x}}_{n},y_{n})$ n $({\boldsymbol {x}}_{n},y_{n})$ {\ $boldsymbol {x}_{n}, y_{n})$ 다음과 $({\boldsymbol {x}}_{n},y_{n})$ 같은 문제를 해결해야 합니다.

\displaystyle y_{n}^{*}= 언더셋 {y\in\mathcal {Y}}{\textrm {argmax}}\left(\Delta(y_{n},y)+\Psi(\boldsymbol {x}_{n},\langle - w})

최대화할 우측 목표는 상수 $-\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle -\xi _{n}$ - $-\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle -\xi _{n}$ w $-\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle -\xi _{n}$ ( $-\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle -\xi _{n}$ , $-\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle -\xi _{n}$ ) $-\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle -\xi _{n}$ - $-\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle -\xi _{n}$ n \ $displaystyle -$ \ $langle {$ w } , \ $Psi$ ( \ $bold symbol$ { $x } _$ { $n$ } , $y _ n$ } ) 및 $-\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y_{n})\rangle -\xi _{n}$ $\Delta (y_{n},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y)\rangle$ 된 $\Delta (y_{n},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{n},y)\rangle$ 변수 이상에 의존하는 항으로 구성됩니다. $ystyle \Delta(y_{n},y)+\langle {boldsymbol {w},\Psi({\boldsymbol {x}_{n},y}\rangle$ 달성된 우측 목표가 0보다 작거나 같을 경우 이 샘플의 제약조건을 위반하지 않습니다.이 값이 0보다 클 경우 이 샘플과 관련하여 가장 위반이 심한 제약 조건을 식별한 것입니다.이 제약으로 인해 문제가 확대되어 해결되었습니다.그 과정은 위반된 불평등이 식별되지 않을 때까지 계속된다.

위의 문제에서 상수가 떨어지면 다음과 같은 문제가 해결됩니다.

\displaystyle y_{n}^{*}={\textrm {argmax}}}\left(\Delta(y_{n},y)+\Psi(\boldsymbol {x}_{ny},\rangle \right})

이 문제는 추론 문제와 매우 유사해 보입니다.유일한 차이점은 용어 $\Delta (y_{n},y)$ ( $\Delta (y_{n},y)$ n , $\Delta (y_{n},y)$ $){$ $displaystyle \Delta$ ( y $_$ {n $, y$ $\Delta (y_{n},y)$ 가 추가된 것입니다.대부분의 경우 라벨 공간에서 자연스럽게 분해되도록 선택됩니다.이 경우 $(\displaystyle \Delta$ })의 $\Delta$ 영향을 추론문제로 인코딩할 수 있으며, 가장 위반되는 제약조건에 대한 해결은 추론문제의 해결과 동등하다.

레퍼런스

Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann and Yasemin Altun(2005), 구조화 및 상호의존적 출력 변수에 대한 Large Margin Methods for Structured and Interdependent Output Variables, JMLR, Vol. 6, 1453-1484페이지.
Thomas Finley and Thorsten Joachims (2008), Training Structural SVMs when Exact Inference is Intractable, ICML 2008.
Sunita Sarawagi와 Rahul Gupta(2008), 구조화된 출력 공간을 위한 정확한 최대 마진 트레이닝, ICML 2008.
Gökhan BakIr, Ben Taskar, Thomas Hofmann, Bernhard Schölkopf, Alex Smola 및 SVN Vishwanathan(2007), Predicting Structured Data, MIT Press.
Vojtchch Franc와 Bogdan Savchynsky의 Max-Sum 분류기 차별적 학습, 9 (1월) : 67 - 104, 2008, Microtome Publishing
Kevin Murphy [ 1 ]머신러닝, MIT 프레스

Search

구조화된 서포트 벡터 머신

네임스페이스

더

목차

트레이닝

추론

분리

레퍼런스