브라운부스트

BrownBoost는 노이즈가 많은 데이터셋에 강력할 수 있는 부스팅 알고리즘이다.BrownBoost는 다수 알고리즘에 의한 부스트의 적응형 버전이다.모든 부스팅 알고리즘이 사실인 것처럼 BrownBoost는 다른 기계 학습 방법과 함께 사용된다.브라운부스트는 2001년 요아프 프라운드에 의해 소개되었다.^[1]

동기

AdaBoost는 다양한 데이터셋에서 좋은 성능을 발휘하지만, 시끄러운 데이터셋에서 AdaBoost가 좋은 성능을 발휘하지 못한다는 것을 알 수 있다.^[2]이는 에이다부스트가 반복적으로 잘못 분류되는 사례에 초점을 맞춘 결과다.이와는 대조적으로 브라운부스트는 반복적으로 잘못 분류되는 사례에 대해 효과적으로 "올려" 있다.브라운부스트의 핵심 가정은 시끄러운 예들이 약한 가설에 의해 반복적으로 잘못 표기되고 잡음이 없는 예들은 "포기되지 않을 만큼" 자주 정확하게 라벨을 붙일 것이라는 것이다.따라서 시끄러운 예만 "포기"되는 반면, 잡음이 없는 예들은 최종 분류기에 기여할 것이다.반대로 최종 분류자가 잡음이 없는 예에서 배운다면 최종 분류자의 일반화 오류는 시끄러운 예와 잡음이 없는 예에서 배웠을 때보다 훨씬 나을 수 있다.

알고리즘 사용자는 훈련 세트에서 허용할 오류 양을 설정할 수 있다.따라서 훈련 세트가 소음이 심할 경우(모든 예시 중 10%가 잘못 라벨 부착된 것으로 가정할 경우), 부스터는 10%의 오류율을 수용하도록 지시할 수 있다.시끄러운 예들은 무시될 수 있기 때문에, 진정한 예들만이 학습 과정에 기여할 것이다.

알고리즘 설명

BrownBoost는 비컨벡스 잠재적 손실 함수를 사용하기 때문에 에이다부스트 프레임워크에는 맞지 않는다.비 컨벡스 최적화는 소음이 많은 데이터 세트를 과도하게 장착하지 않도록 하는 방법을 제공한다.그러나 브라운부스트는 볼록 손실 함수(예: AdaBoost 및 LogitBoost)를 분석적으로 최소화하는 알고리즘을 증강하는 것과 대조적으로, 표준 수치 방법을 사용하여 2개의 방정식과 2개의 미지의 시스템을 해결한다.

BrownBoost(알고리즘에서 $c$ $c$ ${\displaystyle$ c $})$ 의 유일한 파라미터는 알고리즘이 실행되는 "시간"이다.BrownBoost 이론은 각 가설은 가변 시간(알고리즘에서 $t$ ${\displaystyle$ t $})$ 이 소요된다고 기술하고 있는데, 이는 가설 $\alpha$ $\alpha }$ 에 주어진 무게와 직접 관련이 있다 $\alpha$ BrownBoost의 시간 매개변수는 AdaBoost의 반복 $T$ T ${\displaystytytytytyte$ T $}$ 과 유사하다.

$c$ $c$ 의 값이 클수록 BrownBoost는 데이터를 소음이 덜한 것처럼 취급하여 더 적은 예시를 포기하게 된다는 것을 의미한다 $c$ .반대로 $c$ $c$ 의 값이 작다는 것은 BrownBoost가 데이터를 더 시끄러운 것으로 취급하고 더 많은 예를 포기하는 것을 의미한다 $c$ .

알고리즘의 각 반복 동안, 가설은 무작위 추측에 비해 어느 정도 유리하게 선택된다.반복하는 $t$ 동안 이 가설의 무게 $\alpha$ {\ $displaystyle$ \ $alpha }$ 과 $\alpha$ "통과된 시간의 양" $t$ {\ $displaystyt t}$ 은 두 개의 알 수 없는 것( $\alpha$ α ${\$ 의 가중치)으로 구성된 두 개의 비선형 방정식(1.rt 예제 가중치 및 2. 전위 상수)의 시스템에서 동시에 해결된다. $displaystyle \property }$ 및 $\alpha$ $t$ $t$ 시간이 경과함이는 이분법(JBoost 소프트웨어 패키지에서 구현한 것)이나 뉴턴의 방법(Freund가 원본에서 설명한 것)으로 해결할 수 있다.이러한 방정식이 해결되면 알고리즘에서 $r_{i}(x_{j})$ 각 예시( $r_{i}(x_{j})$ i $r_{i}(x_{j})$ ( $r_{i}(x_{j})$ j $r_{i}(x_{j})$ ) ${\displaystyle r_{i}(x_{j})$ 의 여백과 남은 $시간$ s ${\displaysty s}$ 이(가) 적절히 업데이트된다 $s$ .이 과정은 시간이 남지 않을 때까지 반복된다.

The initial potential is defined to be ${\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}({\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})$ . Since a constraint of each iteration is that the potential be held constant, the final potential is ${\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}(r_{i}(x_{j})/{\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})$ ${\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}(r_{i}(x_{j})/{\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})$ .따라서 최종 오차는 $1-{\mbox{erf}}({\sqrt {c}})$ - $1-{\mbox{erf}}({\sqrt {c}})$ ( $){\displaystyle 1-{\mbox{erf}}{\sqrt{c}}}$ 에 가까울 가능성이 있지만, 최종 잠재적 기능은 0-1 손실 오류 함수가 아니다 $1-{\mbox{erf}}({\sqrt {c}})$ 최종 오차가 정확히 1 $1-{\mbox{erf}}({\sqrt {c}})$ - $1-{\mbox{erf}}({\sqrt {c}})$ ( $){\displaystyle 1-{\mbox{erf}}({\sqrt{c}})$ 이 되려면, 손실 함수의 분산이 부스팅 반복이 끝날 때 0-1 손실 함수를 형성하는 데 선형적으로 감소해야 한다 $1-{\mbox{erf}}({\sqrt {c}})$ 이것은 문헌에서는 아직 논의되지 않았으며 아래 알고리즘의 정의에서도 논의되지 않는다.

최종 분류자는 약한 가설의 선형 결합이며 다른 대부분의 부스팅 알고리즘과 동일한 방식으로 평가된다.

BrownBoost 학습 알고리즘 정의

입력:

$m$ training examples $(x_{1},y_{1}),\ldots ,(x_{m},y_{m})$ where $x_{j}\in X,\,y_{j}\in Y=\{-1,+1\}$
$매개$ 변수 c $c$

초기화:

$s=c$ = $s=c$ $s=c$ . ( $s$ $s$ 의 값은 게임에 $s$ 남은 시간)
$r_{i}(x_{j})=0$ $r_{i}(x_{j})=0$ ( $r_{i}(x_{j})=0$ j $r_{i}(x_{j})=0$ ) $r_{i}(x_{j})=0$ = $r_{i}(x_{j})=0$ $r_{i}(x_{j})=0$ $r_{i}(x_{j})=0$ $\forall j$ $\forall j$ $\forall j$ . $r_{i}(x_{j})$ $r_{i}(x_{j})$ ( $r_{i}(x_{j})$ $r_{i}(x_{j})$ ) ${\displaystyle r_{i}(x_{j})$ 의 값은 $r_{i}(x_{j})$ $반복$ i{\ $displaystyle i}$ 의 $i$ 여백(예: $x_{j}$ $x_{j}$ {\ $displaystyle x_{j$

$s>0$ > $s>0$ $s>0$ 일 $s>0$ 때:

각 예제의 가중치 설정: $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ ( $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ ) $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ = $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ - $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ ( r $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ ( $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ ) $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ + $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ ) $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ ${\$ $}}{$ $r_{i}(x_{j})$ $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ c2}}: $r_{i}(x_{j})$ 서 r i $r_{i}(x_{j})$ j $){\displaystyle r_{i}(x_{j}})$ 는 $r_{i}(x_{j})$ 예 $x_{j}$ j ${\$ 의 여백이다.
분류자 $h_{i}:X\to \{-1,+1\}$ $h_{i}:X\to \{-1,+1\}$ : $h_{i}:X\to \{-1,+1\}$ → $h_{i}:X\to \{-1,+1\}$ { $h_{i}:X\to \{-1,+1\}$ - $h_{i}:X\to \{-1,+1\}$ , $h_{i}:X\to \{-1,+1\}$ + $h_{i}:X\to \{-1,+1\}$ $h_{i}:X\to \{-1,+1\}$ $h_{i$ 를 찾으십시오. $X$ \{- $1,+1\}:$ $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$ W $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$ ( $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$ j $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$ ) $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$ $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$ ( $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$ $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$ ) $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$ $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$ > $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$ ${\displaystyle \sum _{j}W_{i}(x_{j})h_{i}(x_{j}y$ }y)_ ${j}$ y} $0}$
다음 방정식을 충족하는 $\alpha ,t$ $\alpha ,t$ , $\alpha ,t$ t {\ $displaystyle \alpha$ , $t}$ 을(를) 찾으십시오.
${\displaystyle \sum _{j}h_{i}(x_{j})y_{j}e^{-{\frac {(r_{i}(x_{j})+\alpha h_{i}(x_{j})y_{j}+s-t)$ $^{2}}:{c}}=0}$ .
( $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ :^[3] E W $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ + 1 $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ [ $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ ( $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ j $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ ) y $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ = $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ $E_{W_{i+1}[h_{i}(x_{j}y_{j}})=0$ 조건과 $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ 유사하다.In this setting, we are numerically finding the $W_{i+1}=\exp \left({\frac {\cdots }{\cdots }}\right)$ such that $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ .)
이 업데이트는 제약조건의 적용을 받는다.
$\sum \left(\Phi \left(r_{i}(x_{j})+\alpha h(x_{j})y_{j}+s-t\right)-\Phi \left(r_{i}(x_{j})+s\right)\right)=0$ ,
여기서 φ $\Phi (z)=1-{\mbox{erf}}(z/{\sqrt {c}})$ ) $\Phi (z)=1-{\mbox{erf}}(z/{\sqrt {c}})$ = $\Phi (z)=1-{\mbox{erf}}(z/{\sqrt {c}})$ - $\Phi (z)=1-{\mbox{erf}}(z/{\sqrt {c}})$ / c $\Phi (z)=1-{\mbox{erf}}(z/{\sqrt {c}})$ ) $\Phi(z)=1-{\mbox{erf}}(z/{\sqrt{c})$ 은 여백 $r_{i}(x_{j})$ $r_{i}(x_{j})$ j $r_{i}(x_{j})$ ) ${\displaysty r_{i}(x_{j})$ 가 있는 지점에 대한 잠재적 손실이다 $\Phi (z)=1-{\mbox{erf}}(z/{\sqrt {c}})$ .
각 예제의 여백 $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ : $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ i $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ + 1 ( $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ ) $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ = $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ i $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ ( x $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ ) $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ + $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ ( $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ ) $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$ ${\$ h $(x_{j}$ y}y}y $)_{$ j}}}}}}}}}}}}
남은 시간 업데이트: $s=s-t$ = $s=s-t$ - $s=s-t$ $s=s-t$

출력: $H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)$ x $H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)$ ) $H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)$ = $H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)$ ∑ i $H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)$ $H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)$ i ( $H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)$ x $H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)$ ) ) ${\$

경험적 결과

소음이 많은 데이터세트가 있는 예비 실험 결과에서 브라운부스트는 에이다부스트의 일반화 오류를 능가했지만, 로짓부스트는 브라운부스트만큼 좋은 성적을 거두었다.^[4]BrownBoost의 구현은 오픈 소스 소프트웨어 JBoost에서 찾을 수 있다.

참고 항목

참조

^ 요아프 프룬드.다수 알고리즘에 의한 부스트의 적응형 버전.머신러닝, 43(3):293--318, 2001년 6월.
^ 디테리히, T. G. (2000년)결정 나무의 앙상블을 구성하는 세 가지 방법, 즉 배깅, 부스팅, 무작위화 방법의 실험적 비교.기계 학습, 40(2) 139-158.
^ 로버트 샤피어와 요람 싱어.신뢰도 등급 예측을 사용하여 향상된 성능.기계 학습 저널, Vol 37(3), 페이지 297-336. 1999.
^ 로스 맥도날드, 데이비드 J. 핸드, 이드리스 A.에클리.인공등급 노이즈를 이용한 실제 데이터 집합에서의 3가지 부스팅 알고리즘의 실증적 비교다중 분류기 시스템, 컴퓨터 과학의 직렬 강의 노트 35-44, 2003페이지.

외부 링크

JBoost

[Freund01-1] 요아프 프룬드.다수 알고리즘에 의한 부스트의 적응형 버전.머신러닝, 43(3):293--318, 2001년 6월.

[Dietterich00-2] 디테리히, T. G. (2000년)결정 나무의 앙상블을 구성하는 세 가지 방법, 즉 배깅, 부스팅, 무작위화 방법의 실험적 비교.기계 학습, 40(2) 139-158.

[Schapire99-3] 로버트 샤피어와 요람 싱어.신뢰도 등급 예측을 사용하여 향상된 성능.기계 학습 저널, Vol 37(3), 페이지 297-336. 1999.

[McDonald03-4] 로스 맥도날드, 데이비드 J. 핸드, 이드리스 A.에클리.인공등급 노이즈를 이용한 실제 데이터 집합에서의 3가지 부스팅 알고리즘의 실증적 비교다중 분류기 시스템, 컴퓨터 과학의 직렬 강의 노트 35-44, 2003페이지.

[1]

[2]

[3]

[4]

Search