LPBoost

LPBoost(Linear Programming Boost)는 부스팅 계열의 분류자로부터 감독을 받는 분류자 입니다.LPBoost는 서로 다른 등급의 훈련 샘플 간의 마진을 최대화하므로 또한 마진 최대화 감독 분류 알고리즘의 등급에 속한다.분류함수를 고려한다.

${\displaystyle f:{\mathcal {X}\to \{-1,1\}}$

공간 $X{\displaystyle \mathcal{}}$ ${\${\$mathcal{X}$의 표본을 각각 1과 -1로 표시된 두 가지 클래스 중 하나로$$ 분류한다.LPBoost는 이러한 분류 함수를 학습하기 위한 알고리즘으로, 알려진 클래스 라벨이 있는 일련의 훈련 예시를 제공한다.LPBoost는 머신러닝 기법이며, 특히 구조화된 도메인에서 공동 분류와 특징 선택의 적용에 적합하다.

LPBoost 개요

모든 부스팅 분류기에서와 마찬가지로 최종 분류 함수는 형식이다.

${\displaystyle f({\boldsymbol {x})=\sum _{j=1}^{J}\알파 _{j}h_{j}({\boldsymbol {x}),}$

여기서 $\alpha {\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$는 약한 분류자 $h{\displaystyle {}_{}}$: ${\displaystyle X}$→${\displaystyle }${${\displaystyle }$- ${\displaystyle 1}$, ${\displaystyle 1\}}$ ${\displaystyle h_{j}$에 대한 음이 아닌 가중치임$$.${\mathcal{X}\to \{-1$ 각각의 약한 분류자 $h{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$ 개별적인 약한 분류자 h j는 무작위보다 약간 나을 수도$$ 있지만, 결과적으로 많은 약한 분류자의 선형 결합은 매우 좋은 성과를 낼 수 있다.

LPBoost는 빈약한 분류자 집합에서 $시작$하여 f ${\displaystyle f}$을(를) 구성한다.반복적으로, 약한 분류자로 간주되는 분류자 집합에 추가할 약한 분류자 하나를 선택하고, 추가하며, 현재 약한 분류자 집합에 대한$$ 모든 가중치 $\alpha {\displaystyle \mathit{}}$ ${\$}}}을 조정한다.추가할 약한 분류자가 남아 있지 않을 때까지 이런 일이 반복된다.

모든 분류자 가중치가 각 반복에서 조정되는 속성을 완전 보정 속성이라고 한다.AdaBoost와 같은 초기 부양 방법은 이 속성을 가지고 있지 않고 더 느리게 수렴한다.

선형 프로그램

보다 일반적으로 $H{\displaystyle \mathcal{}}$= ${\displaystyle \{h}$ (${\displaystyle \cdot }$; ${\displaystyle \Omega }$ )${\displaystyle \Omega }$ ${\displaystyle \mathrm{\Omega }}$ ${\displaystyle \}}$ ${\displaystyle {\mathcal{H}=\h(\cdot ;\omega$) $\omega \}}}}$은(는) 아마도 무한히 약한 분류자 집합이며$$, 가설이라고도 한다.LPBoost가 해결하는 문제를 적는 한 가지 방법은 변수가 무한히 많은 선형 프로그램이다.

$음$이 아닌 체중 벡터 α {\$displaystyle {\boldsymbol {\xi$에 걸쳐 최적화하는 LPBoost의 원시 선형 프로그램, 이완 변수의 비음극$$ 벡터 $\xi {\displaystyle \mathit{}}$ ${\displaystyle$ {\$boldsymbol{\$$xi$ $}}},$ ${\displaysty}$은 다음과$$ 같다.

${\displaystyle {\begin{array}{cl}{{\\underset {{\boldsymbol {\\alpha }},{\boldsymbol{\xi},\rho }{\min }&-\rho +D\sum _{n=1^{n}\n}\textrum.}}&\sum _{\omega \in \Omega }y_{n}\alpha _{\omega }h({\boldsymbol {x}}_{n};\omega )+\xi _{n}\geq \rho ,\qquad n=1,\dots ,\ell ,\\&\sum _{\omega \in \Omega }\alpha _{\omega }=1,\\&\xi _{n}\geq 0,\qquad n=1,\dots ,\ell ,\\&\alpha _{\omega }\geq 0,\qquad \omega \in \Omega ,\\&\rho \in {\mathbb {R} }.\end{array}}}$

느슨한 변수${\displaystyle }\xi {\displaystyle \mathit{}}$ ${\displaystyle 0}$ ${\displaystyle {\boldsymbol {\xi }\geq$ 0$}$의 영향을 주의하십시오$.$ 이들의 단일 표준은 항상 일정한 요인 $D{\displaystyle }$ ${\displaystyle D$에 의해 객관적 함수에서 불이익을 받으며, 충분히 작을 경우 항상 초기 실행 가능한 선형 프로그램으로 이어진다.

Here we adopted the notation of a parameter space ${\displaystyle \Omega }$, such that for a choice ${\displaystyle \omega \in \Omega }$ the weak classifier ${\displaystyle h(\cdot ;\omega ):{\mathcal {X}}\to \{-1,1\}}$ is uniquely defined.

위의 선형 프로그램이 초기 출판물에 부스팅 방법에 대해 처음 기록되었을 때, 그것은 많은 변수 $\alpha {\displaystyle \mathit{}}$ ${\$ 때문에 난치불능으로 무시되었다$.$ 나중에야 그러한 선형 프로그램은 실제로 g열의 고전적인 기법을 사용하여 효율적으로 해결될 수 있다는 것이 밝혀졌다.내조

LPBoost용 컬럼 생성

선형 프로그램에서 열은 원시 변수에 해당한다.컬럼 생성은 대규모 선형 프로그램을 해결하는 기법이다.일반적으로 제한된 문제에서 작동하며 변수의 부분 집합만 처리한다.원시 변수를 반복적으로 그리고 필요에 따라 생성함으로써 결국 모든 변수에 대한 원래 제한되지 않은 문제가 복구된다.문제를 발생시킬 열을 교묘하게 선택함으로써, 획득한 솔루션이 원래의 전체 문제에 최적이 되도록 보장하면서도, 작은 부분의 열만 생성하면 되는 문제를 해결할 수 있다.

LPBoost 이중 문제

원시 선형 프로그램의 열은 이중 선형 프로그램의 행에 해당한다.LPBoost의 동등한 이중 선형 프로그램은 다음과 같은 선형 프로그램이다.

${\displaystyle {\cHB{array}{cl}{\cl}{\\boardsymbol{\board}},\board }{\max}&#{\textrm {lo.t}}}&\sum _{n=1}^{\ell }y_{n}h({\boldsymbol {x}}_{n};\omega )\lambda _{n}+\gamma \leq 0,\qquad \omega \in \Omega ,\\&0\leq \lambda _{n}\leq D,\qquad n=1,\dots ,\ell ,\\&\sum _{n=1}^{\ell }\lambda _{n}=1,\\&\gamma \in \mathbb {R} .\end{array}}}$

선형 프로그램의 경우 원시 문제와 이중 문제의 최적 값은 동일하다.위의 원시 문제와 이중 문제에 대해 최적 값은 음의 '연성 여유'와 동일하다.소프트 마진은 마이너스 훈련 사례에서 양수를 분리하는 마진 크기에서 마진 위반 표본에 대한 벌칙을 전달하는 양의 느슨한 변수를 뺀 값이다.따라서 모든 표본이 분류 함수에 의해 선형적으로 분리되는 것은 아니지만 연한 여백은 양수일 수 있다.후자는 '하드 마진' 또는 '실현 마진'이라고 불린다.

수렴기준

이중 문제에서 충족되는 제약 조건의 일부를 고려하십시오.유한 부분 집합에 대해 우리는 선형 프로그램을 해결할 수 있고 따라서 모든 제약조건을 충족시킬 수 있다.만약 우리가 이중 문제에 추가하지 않은 모든 제약조건들 중에서 어떤 제약조건도 위반되지 않는다는 것을 증명할 수 있다면, 우리의 제한적인 문제를 해결하는 것이 원래의 문제를 해결하는 것과 같다는 것을 증명했을 것이다.좀 더 공식적으로 ${\$을(를) 모든 제한된 인스턴스에 대한 최적의 목표 함수 값이 되도록$$ 한다.그런 다음, 원래의 문제 공간에서 '가장 위반된 제약조건'에 대한 검색 문제를 공식화할 수 있다. 즉, $\Omega {\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ ∈ ${\displaystyle \mathrm{\Omega }}$ ${\displaystyle \omega ^{*}\$in $\Oomega }$에서 \Oomega }을(를) 찾을$$ 수 있다.

${\displaystyle \omega ^*}={\underset {\in}{\textrm {argmax}}\sum _{n=1}^{n=1}{n1}y_{n}h({\boldsymbol{x}_{n};\omega )\lambda _{n}.}$

즉, 이중 구속조건의 좌측을 최대화하는$$ 단일 결정 그루터기 $h{\displaystyle (}$ ${\displaystyle \cdot ;}$$$${\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$) ${\displaystyle h(\cdot;\omega ^{*}})$에 대한$$ 공간 $H{\displaystyle \mathcal{}}$ ${\$ h(\cdot;\$mathcal {H}}})$를 검색한다.어떤 선택으로든 의사결정의 그루밍에 의해 제약조건을 위반할 수 없는 경우, 해당 제약조건 중 어느 것도 본래의 문제에서 활동할 수 없으며 제한적인 문제는 동등하다.

벌칙 $상수{\displaystyle }$ D ${\디스플레이 스타일$ D$}$

벌칙 상수 $D{\displaystyle }$ ${\displaystyle D}$의 양의 값은 모델 선택 기법을 사용하여 찾아야 한다$$.그러나 $D{\displaystyle }$= 1 ${\displaystyle \frac{\ell }{}}$ ${\displaystyle \frac{\nu }{}}$ ${\$$displaystyle$ D$={\frac {1}{\\ell \nu }}$을$($를$)$ 선택하면 여기서 $\ell {\displaystyle }$ ${\displaystyle$ $\$$ell }$은(는) 교육 샘플의 < < ><\$displaystystyle$ 0$<\nu$ >은 다음과 같은 속성이$$ 있다$.$

• ${\displaystyle \nu }$ ${\displaystyle \nu}$은(는) 교육 오류의 일부에 대한 상한으로$$, $즉{\displaystyle }$ k ${\displaystyle k}$이(가) 잘못된 분류된 교육 샘플 수를 나타내는 경우 $k{\displaystyle \frac{}{}}$ ${\displaystyle \frac{\ell }{}}$ ${\displaystyle \le }$ ≤ ≤ ${\frac {k}{\ell}}\leq \nu$
• ${\displaystyle \nu }$ ${\displaystyle \nu}$은(는) 훈련 샘플의 외부 또는 여백에 있는 분수에 대한 하한이다$$.

알고리즘.

• 입력:
  • $교육{\displaystyle }$ 세트 X =${\displaystyle }${${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathit{}}_{}}$, ${\displaystyle \dots ,}$ x${\displaystyle {}_{}}$}${\displaystyle X=\{\\boldsymbol${x$}_{1},\dots$, ${\boldsymbol${x$}_{\ell}\}\,$ $x{\displaystyle {\mathit{}}_{}}$∈${\displaystyle {}_{}X\mathcal{}}$ ${\$
  • 교육 라벨 $Y{\displaystyle }$=${\displaystyle }${ Y ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}\dots ,}$ y ${\displaystyle {\ell }_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle$ Y$=\{y_{1},\dots, y_{\ell }\},$${\displaystyle {yi}_{}}$ ${\displaystyle {}_{}}${${\displaystyle }$- ${\displaystyle 1}$, ${\displaystyle 1\}}$ ${\displaysty y_{i}\in \-1,1\}$
  • 수렴 임계값${\displaystyle }\theta {\displaystyle }$ ${\displaystyle 0}$ ${\displaystyle \theta \geq 0}$
• 출력:
  • 분류함수 $f{\displaystyle }$: ${\displaystyle X}$→${\displaystyle }${${\displaystyle }$- ${\displaystyle 1}$,${\displaystyle 1}$} ${\displaystyle f:{\mathcal{X}\to$\{-$1,1\}}$

1. 초기화
   1. 무게, 균일한 $\lambda {\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle 1\frac{\ell }{},}$ n = ${\displaystyle 1}$ ${\displaystyle \dots ,\ell }$ ${\displaystyle \lambda _{n}\frac {1}{\ell },\quad n=1,\dots ,\ell }$
   2. ${\displaystyle \mathrm{Edge}}$ $\gamma {\displaystyle }$ ${\displaystyle \leftarrow }$0 {\$displaystyle \gamma \leftarrow 0}$
   3. 가설 카운트 $J{\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle 1}$ ${\displaystyle J\왼쪽$ 화살표 $1}$
2. 반복하다
   1. ${\displaystyle {\hat{h}\왼쪽 화살표 {\underset \\\data }{\textrm {argmax}}\sum _{n=1}^{n1}\el }h({\boldsymbol{x}_{n};\lambda _{n}}).$
   2. 만약 $\sum {\displaystyle \underset{n}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{1}}}$ ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle {}_{}\stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ (${\displaystyle }$x ${\displaystyle {}_{}}$) ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ +${\displaystyle {}_{}\gamma }$ {${\displaystyle \theta }$ { { {$$\$displaystyle \sum _{n=1}^{n_}{n}{n$}}}{\hat${\hda{\\\n}}}}{\n$$}+\leq.$
      1. 부숴뜨리다
   3. ${\displaystyle h_{J}\왼쪽 화살표 {\hat {h}}$
   4. $[\displaystyle J\왼쪽 화살표 J+1}$
   5. ${\displaystyle }$(${\displaystyle \lambda \mathit{}}$ ,${\displaystyle \gamma }$)$$←{\$displaystyle ({\boldsymbol${\$lambda$}},\$gamma )\leftarrow }$ LPBoost 듀얼 용액$$
   6. ${\displaystyle \mathit{\alpha }}$ ${\displaystyle \leftarrow }$ ${\displaystyle {\boldsymbol {\alpha }}\leftarrow }$LPBoost 이중 문제 해결의 라그랑어$$ 승수
3. ${\displaystyle f({\boldsymbol{x}):={\textrm{sign}}\좌(\sum _{j=1}^{J}\알파 _{j}h_{j}({\boldsymbol{x}}})\오른쪽)}}$

수렴 임계값을 $\theta {\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle \theta =0}($으)로 설정하면 위의$$ 선형 프로그램의 글로벌 최적 솔루션으로 얻을 수 있다는 점에 유의하십시오.실제로 $\theta {\displaystyle }$ ${\displaystyle \theta}$은(는) 좋은 솔루션을 빨리 얻기 위해 작은 양의 값으로 설정된다$$.

실현마진

교육 샘플을 분리하는 실제 여유는 실현된 여유라고 하며 다음과 같이 정의된다.

${\displaystyle \rho({\positionsymbol {\properties }}):=\min _{n=1,\dots,\ell }y_{n}\sum _{\na_{\na_{\na}\in \Oomega }\Oomega }\Oomega }\na _{\boldsymbol{x}_{n};\omega }.}$

실현된 마진은 대개 첫 번째 반복에서 음수가 될 수 있다.일반적으로 그렇듯이, 단일 표본을 추출할 수 있는 가설 공간의 경우, 실현된 마진은 결국 어떤 양의 값으로 수렴될 것이다.

수렴보증

위의 알고리즘이 수렴하는 것으로 입증되지만, 에이다부스트나 토탈부스트와 같은 다른 부스팅 공식과는 대조적으로, LPBoost에는 알려진 수렴 한계가 없다.그러나 실제로 LPBoost는 다른 제형보다 빠르게, 종종 더 빠르게 수렴하는 것으로 알려져 있다.

기본 학습자

LPBoost는 앙상블 학습 방법이기 때문에 기본 학습자의 선택을 좌우하지 않는 가설 $H{\displaystyle \mathcal{}}$ ${\$ 데미리즈 외 연구진은 가벼운 가정 하에서 어떤 기본 학습자도 사용할 수 있다는 것을 보여주었다.기초 학습자가 특히 단순하면 흔히 의사결정 그루터기라고 한다.

문학에서 부스팅과 함께 일반적으로 사용되는 기본 학습자의 수는 많다.예를 들어, $X{\displaystyle \mathcal{}}$⊆ ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle n^{}}$ ${\${\$mathb {R}^{n$ 기본 학습자는 선형 소프트 마진 지원 벡터 시스템이 될 수 있다.아니면 훨씬 더 간단한 형태의 그루터기.

${\displaystyle h({\boldsymbol {x}};\omega \in \{1,-1\},p\in \{1,\dots ,n\},t\in {\mathbb {R} }):=\left\{{\begin{array}{cl}\omega &{\textrm {if~}}{\boldsymbol {x}}_{p}\leq t\\-\omega &{\textrm {otherwise}}\end{array}}\right..}$

위의 결정 스텀프는 입력 공간의 단일$$ $치수{\displaystyle }$ p ${\displaystyle p}$만 보고 일정한 임계값 $t{\displaystyle }$ ${\displaystyle t}$을 사용하여 샘플의 각 열을 단순히 임계값으로 지정한다$.$그런 다음 $양수{\displaystyle }$ 또는$$ 음수 클래스에 대해 Ω${\displaystyle$ \omega $}$에 따라 어느 방향으로든 결정할 수 있다$.$

교육용 샘플에 대한 가중치가 주어지면, 위의 양식의 최적 의사결정 그루터기를 구성하는 것은 게인 기능을 최적화하기 위해$$ 모든 샘플 열을 따라 검색하고 $p{\displaystyle }$ ${\displaystyle p$ $t{\displaystyle }$ ${\displaysty t}$ 및$$ $\Omega {\displaystyle }$ ${\displaystyle \omega$}을(를) 결정하는 것이다.

참조

• Column Generation을 통한 선형 프로그래밍 부스팅, A.데미리즈와 K.P.베넷과 J.샤위-테일러2002년 클루워 머신러닝 46페이지 225-254페이지에 출판되었다.