승수 가중치 갱신 방법

곱셈 가중치 갱신 방법은 의사결정과 예측에 가장 일반적으로 사용되는 알고리즘 기술이며, 게임 이론과 알고리즘 설계에도 널리 사용됩니다.가장 간단한 사용 사례는 전문가의 조언에 의한 예측 문제이며, 의사결정자는 그에 따를 전문가를 반복적으로 결정해야 합니다.이 방법은 전문가에게 초기 가중치를 할당하고(일반적으로 동일한 초기 가중치), 전문가가 얼마나 잘 수행했는지에 대한 피드백에 따라 이러한 가중치를 곱셈 및 반복적으로 업데이트한다. 즉, 성과가 저조할 경우 줄이고 그렇지 않을 ^[1]경우 가중치를 증가시킨다.이는 기계학습(AdaBoost, Winnow, Hedge), 최적화(리니어 프로그램 해결), 이론 컴퓨터 과학(LP 및 SDP에 대한 빠른 알고리즘 고안), 게임 이론 등 매우 다양한 분야에서 반복적으로 발견되었다.

이름.

"승수 가중치"는 승수 가중치 갱신 ^[2]방법에서 도출된 알고리즘에 사용되는 반복 규칙을 의미한다.검색 또는 재검출된 필드마다 다른 이름으로 제공됩니다.

이력 및 배경

이 기술의 가장 초기의 알려진 버전은 1950년대 초 게임 이론에서 제안된 "가상 플레이"라는 알고리즘이었다.그리고리아디스와 카치얀은^[3] 곱셈 가중치 알고리즘을 사용하여 2인용 제로섬 게임을 효율적으로 해결하기 위해 무작위화된 변형 "가상 플레이"를 적용했다.이 경우, 플레이어는 더 나은 결과를 얻은 행동에 더 높은 비중을 두고 이러한 가중치에 의존하여 전략을 선택한다.기계학습에서, Littlstone은 그의 유명한 winnow 알고리즘에서 승수 가중치 업데이트 규칙의 가장 초기 형태를 적용했는데, 이것은 Minsky와 Papert의 초기 퍼셉트론 학습 알고리즘과 유사하다.나중에 그는 winnow 알고리즘을 가중치 과반수 알고리즘으로 일반화했다.Freund와 Schapire는 그의 절차를 따라 winnow 알고리즘을 헤지 알고리즘의 형태로 일반화했다.

곱셈 가중치 알고리즘은 케네스 클락슨의 선형 프로그래밍(LP) 알고리즘과 같은 계산 기하학에도 선형 ^[4]^[5]시간에 변수 수가 한정되어 널리 적용된다.나중에 Bronnimann과 Goodrich는 VC ^[6]치수가 작은 하이퍼그래프의 세트커버를 찾기 위해 유사한 방법을 사용했다.

운영 연구와 온라인 통계 의사결정 문제 분야에서는 가중 다수 알고리즘과 그 보다 복잡한 버전이 독립적으로 발견되었다.

컴퓨터 과학 분야에서, 일부 연구자들은 이전에 다른 맥락에서 사용되는 곱셈 업데이트 알고리즘 사이의 밀접한 관계를 관찰했습니다.Young은 빠른 LP 알고리즘과 무작위 반올림 알고리즘의 탈난도화를 위한 Raghavan의 비관적 추정기 방법 사이의 유사점을 발견했다; Klivans와 Servedio는 학습 이론에서 Yao의 XOR Lemma의 증명에 연결된 부스팅 알고리즘; Garg와 Khandekar는 다음을 포함하는 볼록 최적화 문제를 위한 공통 프레임워크를 정의했다.a는 Garg-Konemann 및 Flotkin-Shmoys-Tardos를 하위 ^[1]케이스로 포함합니다.

헤지 알고리즘은 거울 강하의 특수한 경우입니다.

일반적인 셋업

관련 보상을 얻으려면 n명의 전문가의 의견을 바탕으로 2진수 결정을 내려야 합니다.1차에서는 모든 전문가들의 의견이 같은 비중을 갖는다.의사결정자는 전문가 대다수의 예측을 바탕으로 첫 번째 결정을 내릴 것이다.그 후, 의사결정자는 연속적으로 각 전문가의 예측의 정확성에 따라 의견의 가중치를 반복적으로 갱신한다.실생활의 예로는 내일 비가 올지, 주식시장이 오를지 내려갈지 예측하는 것이 있다.

알고리즘 분석

절반^[2] 알고리즘

적과 N 전문가의 조언을 받은 애그리게이터 간에 순차적으로 진행되는 게임을 고려할 때 애그리게이터가 가능한 한 실수를 적게 하는 것이 목표입니다.N 전문가 중 항상 올바른 예측을 하는 전문가가 있다고 가정합니다.하프빙 알고리즘에서는 일관된 전문가만 유지됩니다.실수를 한 전문가는 해고될 것이다.모든 결정에 대해 애그리게이터는 나머지 전문가 중 과반수 찬성으로 결정한다.따라서 애그리게이터가 실수를 할 때마다 나머지 전문가의 절반 이상이 해고됩니다.애그리게이터는 $최대 2$ 로그 $($ N)의 오류를 ^[2]범합니다.

가중 다수 알고리즘^[1]^[7]

실수 전문가를 해고하는 하프링 알고리즘과 달리 가중 다수결 알고리즘은 조언을 깎아내린다.같은 "전문가 조언" 설정이 주어진 경우 n개의 결정이 있으며 각 루프에 대해 1개의 결정을 선택해야 한다고 가정합니다.각 루프에서 모든 결정은 비용을 수반합니다.모든 비용은 선택 후 공개됩니다.전문가가 맞으면 비용은 0이고 그렇지 않으면 1입니다.이 알고리즘의 목표는 최고 전문가와 거의 같은 수준으로 누적 손실을 제한하는 것입니다.대부분의 전문가가 매번 지속적으로 틀릴 수 있기 때문에 매번 다수결로 선택하는 첫 번째 알고리즘은 작동하지 않습니다.가중치 과반수 알고리즘은 비용을 1 또는 ^[1]0으로 고정하는 대신 전문가의 가중치를 유지함으로써 위의 사소한 알고리즘을 수정합니다.이렇게 하면 절반 알고리즘에 비해 오류가 줄어듭니다.

초기화: $\eta \leq 1/2$ / 2 $\eta \leq 1/2$ ( \  $displaystyle \eta$  \ $leq$  1 $/$ 2 $\eta \leq 1/2$ 를 수정합니다.각 익스퍼트에 대해  ${w_{i}}^{1}$ 와 1 ${w_{i}}^{1}$ ( \  $displaystyle { w$ _ {  $i$ } }^{1} $1$  1을 관련짓습니다. $t$ {\ $displaystyle$  t $}$  ${\mathit {1}}$ = $t$  ${\mathit {1}}$  {{ $displaystyle {1}},$   $2$  ${\mathit {2}}$ {\ $displaystyle {2}},$   $...,$  T {\ $displaystyle$   $T$  $}$  1.  $\mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}$  예측의 가중치  $\mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}$ 에 의해 주어진 예측을 1  $\mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}$   $\mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}$   $\mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}$   $\mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}$   ${\$ ^{ $t},$  $,\mathbb {w_{n}}^{t$  즉, 전문가의 조언 총 가중치가 높은 예측에 따라 0 또는 1을 선택합니다(임의적으로 연결 해제).2.잘못 예측한 모든 전문가에 대해  $w_{i}^{t+1}$  라운드의 체중을 ( $w_{i}^{t+1}$   $w_{i}^t+1$ }의 $곱하여$   $w$  i  $(1-\eta )w_{i}^{t}$ + $w_{i}^{t+1}$ 1 ( 1 -  $}}$  )  $(1-\eta )w_{i}^{t}$  t style ( 1 - \ $eta$ ) w $_$  {  $i$ }^ $t$ } ( $(1-\eta )w_{i}^{t}$  규칙)

$\eta =0$ $\eta =0$ 0 { $displaystyle \eta$ = $0$ 이면 전문가의 조언의 가중치는 그대로 유지됩니다. ${\(\displaystyle \eta)$ 가 $\eta$ 증가하면 전문가의 조언의 무게도 줄어듭니다.일부 연구자는 가중치 과반수 $\eta =1/2$ 에서 = $\eta =1/2$ / $\eta =1/2$ $(\displaystyle$ \ $eta$ = 1 $/2$ )을 $\eta =1/2$ 고정합니다.

$m_{i}^{T}$ $(\displaystyle$ T $)$ 스텝 $T$ 후 $m$ $(\$ $T}}$ 은 $m_{i}^{T}$ expert $M^{T}$ 와 $M^{T}$ 의 $M^{T}$ 실수 횟수({ $displaystyle$ M $^{T})$ 입니다 $M^T$ .다음으로 모든 $display$ i에 대해 다음과 같이 설정합니다.

 ${\$  $T}+{\frac {2\ln(n)}{\eta$

특히, 이것은 최고의 전문가인 i에게 적용된다.최고의 전문가는 $m_{i}^{T}$ 의 $m_{i}^{T}$ T $($ 스타일 $m_{$ })^{ $T$ 알고리즘 전체에 의한 오류 수에 대한 최적의 제한을 제공합니다.

랜덤화 가중치 다수^[2]^[8] 알고리즘

N명의 전문가와 같은 설정이 되어 있습니다.가중치를 셀 때 양수와 음수를 예측하는 전문가의 비율이 둘 다 50%에 가까운 특수한 상황을 고려합니다.그러면 동점일 수도 있어요.가중치 과반수 알고리즘의 가중치 갱신 규칙에 따라 알고리즘에 의한 예측이 랜덤화됩니다.알고리즘은 전문가가 양수 또는 음수를 예측할 확률을 계산한 다음 계산된 ^{[further explanation needed]}분수에 따라 무작위로 결정합니다.

예측하다

f(x)=syslog{case}1&{\text{probility}}{\frac {q_{1}}{W}}\0&{\text{그렇지 않으면}\end{case}}}

어디에

 $W=\sum _{i}{w_{i}}=q_{0}+q_{1}$   $=$   $W=\sum _{i}{w_{i}}=q_{0}+q_{1}$   $W=\sum _{i}{w_{i}}=q_{0}+q_{1}$   $=$   $W=\sum _{i}{w_{i}}=q_{0}+q_{1}$  + $W=\sum _{i}{w_{i}}=q_{0}+q_{1}$  1  $({$  W=\ $sum$  _ ${i}{w_{i$ }}= $q_{0}+q_{1$

랜덤화된 가중치 과반수 알고리즘에 의한 실수의 수는 다음과 같이 한정됩니다.

  $\displaystyle E\left [\#{\text{학습자의 실수}\right]\leq \alpha _{\beta }\left(\#{\text{최고의 전문가의 실수})+c_{\beta }\ln(N)}$

$c_{\beta }={\frac {1}{1-\beta }}$ 서 $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ ln $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ ( $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ β ) $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ - $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ {\ $displaystyle \alpha$ _ ${\display$ } = $phrac {$ 1} {\display $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ } } $\alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}$ $c_{\beta }={\frac {1}{1-\beta }}$ $c_{\beta }={\frac {1}{1-\beta }}$ - $c_{\beta }={\frac {1}{1-\beta }}$ - $c_{\beta }={\frac {1}{1-\beta }}$ {\ $displaystyle c_$ {\display $c_{\beta }={\frac {1}{1-\beta }}$ } } $= phrac$ { $1$ - { $1$ - {\ $d$ $}$ }

학습 알고리즘만이 랜덤화 되는 것에 주의해 주세요.기본적인 가정은 예시와 전문가들의 예측이 무작위가 아니라는 것이다.유일한 무작위성은 학습자가 자신의 예측을 하는 무작위성이다.이 랜덤화 알고리즘에서는 $\alpha _{\beta }\rightarrow 1$ $\beta \rightarrow 1$ $\beta \rightarrow 1$ $(\displaystyle$ \ $alpha$ _{\ $rightarrow$ $\beta \rightarrow 1$ 이 β → 1 $(\displaystyle$ \ $alpha$ \ $rightarrow$ 1)이면 $\alpha _{\beta }\rightarrow 1$ β $\alpha _{\beta }\rightarrow 1$ → 1(\displaystyle \displaystyle \ $rightarrow$ 1)이 됩니다. 이 랜덤화 알고리즘은 가중치화 알고리즘에 비해 실수 ^[9]횟수를 절반으로 줄였습니다.그러나 일부 연구에서는 가중 다수 알고리즘에서 = $\eta =1/2$ / $(\displaystyle \eta = 1/$ 2)를 $\eta =1/2$ 정의하고 랜덤 가중 다수 ^[2]알고리즘에서 0 $0\leq \eta \leq 1$ = $(\displaystyle$ 0 $\leq \leq$ 1)을 $0\leq \eta \leq 1$ $0\leq \eta \leq 1$ 한다는 점에 유의해야 한다.

적용들

곱셈 가중치 방법은 일반적으로 제한된 최적화 문제를 해결하기 위해 사용됩니다.각 전문가가 문제의 제약이 되고 사건은 관심 영역의 포인트를 나타냅니다.전문가의 처벌은 ^[1]사건에 의해 표현되는 점에서 대응하는 제약이 얼마나 잘 충족되는지에 대응한다.

제로섬 게임 대략 해결(Oracle 알고리즘):^[1]^[9]

전문가에 대한 $배포$ P $(\style P)$ 를 $P$ 받았다고 가정해 봅시다. $(\$ $displaystyle$ A $)$ = $A$ n개의 $n$ $행$ 이 $있는$ 유한한 2인용 제로섬 게임의 지불 매트릭스.

행 $p_{r}$ $p_{r}$ ${\$ $displaystyle$ $p_{r}$ 가 $p_{r}$ 플랜 $i$ {\ $displaystyle$ $p_{c}$ 를 $p_{c}$ 사용하고 컬럼 $p_{c}$ p $p_{c}$ {\ $displaystyle$ p_{ $c}$ 가 $플랜$ j $A_{ij}$ {\displaystyle p_{c $j$ 를 사용하는 경우, 플레이어 $p_{c}$ $displaystyle p_$ ${c$ }는 $})\$ $displaystyleft(i$ )가 $됩니다.$ $j$ A $A\left(i,j\right)\in \left[0,1\right]$ ( $A\left(i,j\right)\in \left[0,1\right]$ , $A\left(i,j\right)\in \left[0,1\right]$ $A\left(i,j\right)\in \left[0,1\right]$ [ $A\left(i,j\right)\in \left[0,1\right]$ , $]\$ $displaystyle$ A \ $left$ ( $i$ , $j$ \ $right$ )\ $in \ left$ [ $0$ , $1$ \ $right$ 라고 $A\left(i,j\right)\in \left[0,1\right]$ 합니다.

$p_{r}$ $(\$ ${$ $r$ })이 $p_{r}$ 행 $위$ 의 분포 P(\ $displaystyle$ p_ ${$ c $P$ })에서 $액션$ i(\ $displaystyle$ i $)$ 를 $i$ 선택한 경우 $,$ $p_{c}$ p c(\ $displaystyle$ $p_$ {c $p_{c}$ })가 $액션$ j $($ $A\left(P,j\right)=E_{i\in P}\left[A\left(i,j\right)\right]$ $,$ $A\left(P,j\right)=E_{i\in P}\left[A\left(i,j\right)\right]$ j)를 $j$ 선택한 경우의 $A\left(P,j\right)=E_{i\in P}\left[A\left(i,j\right)\right]$ $A\left(P,j\right)=E_{i\in P}\left[A\left(i,j\right)\right]$ 는 A $A\left(P,j\right)=E_{i\in P}\left[A\left(i,j\right)\right]$ j) $A\left(P,j\right)=E_{i\in P}\left[A\left(i,j\right)\right]$ $A\left(P,j\right)=E_{i\in P}\left[A\left(i,j\right)\right]$ j, j $)$ 입니다. $A\left(P,j\right)=$ $E_{i\in P}\left[$ $A\left(i,j\right)\right$

$A\left(P,j\right)$ ( $A\left(P,j\right)$ , $A\left(i,P\right)=E_{j\in P}\left[A\left(i,j\right)\right]$ j ) $A\left(P,j\right)$ { $displaystyle$ A $\ left$ ( $P$ , $j$ \ $right )$ }를 최대화하려면 , $A\left(i,P\right)=E_{j\in P}\left[A\left(i,j\right)\right]$ $p_{c}$ { $displaystyle$ $p_{c$ $j$ 를 $j$ 합니다 $p_{c}$ $p_{l}$ $.$ $A\left(i,P\right)=E_{j\in P}\left[A\left(i,j\right)\right]$ 로 플레이어 $p_{l}$ $p_{l}$ { $p_{l}$ $A\left(i,P\right)=E_{j\in P}\left[A\left(i,j\right)\right]$ $A\left(i,P\right)=E_{j\in P}\left[A\left(i,j\right)\right]$ J $A\left(i,P\right)=E_{j\in P}\left[A\left(i,j\right)\right]$ P [ $display I$ $E_{j\in P}\left[$ $A(i,j\$ right $A\left(i,P\right)=E_{j\in P}\left[A\left(i,j\right)\right]$ $플랜$ i를 선택하면 이 $대가$ 를 $최소화$ 할 $i$ 수 있습니다.John Von Neumann의 Min-Max 정리에 의해 우리는 다음을 얻는다.

                                           $\displaystyle \min _{P}\max _{j}A\left(P,j\right)=\max _{Q}\min _{i}A\left(i, Q\right)}$

여기서 P와 i는 행의 분포에 따라 변화하고 Q와 j는 열에 따라 변화합니다.

그리고 $(\$ ^{*})은 $\lambda ^{*}$ 상기 수량의 공통값으로 "게임의 가치"라고도 합니다. $\delta >0$ (\ $displaystyle \delta$ > $0)$ 을 $\delta >0$ 에러 파라미터로 합니다. $\delta$ 오차로 둘러싸인 제로섬 게임을 해결하려면 ${\$ { $displaystyle$ \ $delta$

                                                  $\displaystyle \da ^{*}-\display \leq \min _{i}A\left(i,q\right)}$                                                    $\displaystyle \max _{j}A\left(p,j\right)\leq \lambda ^{*}+\delta }$

따라서 ORACLE에 대한 O( $log 2 (n)/$ $(\$ ^{ $2$ 콜을 사용하여 제로섬 게임을 using의 가산계수까지 해결하는 알고리즘이 있으며 콜당^[9] 처리 시간은 O(n)입니다.

Bailey와 Piliouras는 곱셈 가중치 업데이트의 시간 평균 행동이 제로섬 게임에서 내쉬 평형으로 수렴되지만 일상(마지막 반복) 행동은 그것으로부터 ^[10]멀어진다는 것을 보여주었다.

기계 학습

기계 학습에서 Littlstone과 Warmuth는 winnow 알고리즘을 가중 다수 ^[11]알고리즘으로 일반화했다.나중에, 프룬트와 샤파이어는 헤지 ^[12]알고리즘의 형태로 그것을 일반화했다.또한 Yoav Freund와 Robert Schapire에 의해 공식화된 AdaBoost 알고리즘은 Multiplative Weight Update ^[1]Method를 사용하였습니다.

윈노우 알고리즘

알고리즘에 대한 현재 지식을 바탕으로, 곱셈 가중치 업데이트 방법은 Littlstone의 winnow ^[1]알고리즘에서 처음 사용되었다.선형 프로그램을 해결하기 위해 기계 학습에 사용됩니다.

$m$ 이 붙은 m ${displaystyle$ m $}$ 의 $m$ 예 $\left(a_{1},l_{1}\right),{\text{…}},\left(a_{m},l_{m}\right)$ $\left(a_{1},l_{1}\right),{\text{…}},\left(a_{m},l_{m}\right)$ $\left(a_{1},l_{1}\right),{\text{…}},\left(a_{m},l_{m}\right)$ , $\left(a_{1},l_{1}\right),{\text{…}},\left(a_{m},l_{m}\right)$ 1 $\left(a_{1},l_{1}\right),{\text{…}},\left(a_{m},l_{m}\right)$ $\left(a_{1},l_{1}\right),{\text{…}},\left(a_{m},l_{m}\right)$ ( m $\left(a_{1},l_{1}\right),{\text{…}},\left(a_{m},l_{m}\right)$ , $\left(a_{1},l_{1}\right),{\text{…}},\left(a_{m},l_{m}\right)$ $){$ ( $a$ _ {1} , l $_$ { $1}$ \ $right$ , { \ $text$ { ... $}}},\left(a_$ right)}. $a_{j}\in \mathbb {R} ^{n}$ 서 \ $mathbb$ {R $}$ ^{n}의 j $a_{j}\in \mathbb {R} ^{n}$ R $n$ \ display $style a_{j}\$ in \ mathbbb {R} ^{n $a_{j}\in \mathbb {R} ^{n}$ }은 $특징$ 벡터이며, $l_{j}\in \left\{-1,1\right\}\quad$ j $l_{j}\in \left\{-1,1\right\}\quad$ { $l_{j}\in \left\{-1,1\right\}\quad$ - $l_{j}\in \left\{-1,1\right\}\quad$ , 1 $l_{j}\in \left\{-1,1\right\}\quad$ }\ display $styleft l_{j}\$ right $}$ 는 라벨입니다 $l_{j}\in \left\{-1,1\right\}\quad$ .

목적은 음이 아닌 가중치를 찾아 모든 예에서 특징의 가중치 조합의 부호가 해당 레이블과 일치하도록 하는 것이다.즉, $모든$ j(\ $displaystyle$ j $j$ 에 $l_{j}a_{j}x\geq 0$ l j $l_{j}a_{j}x\geq 0$ $l_{j}a_{j}x\geq 0$ x $l_{j}a_{j}x\geq 0$ 0 {\ $displaystyle l_{j}a_{j}x\geq$ 0 $}$ 이 $l_{j}a_{j}x\geq 0$ $l_{j}a_{j}x\geq 0$ 합니다.일반성을 잃지 않고 총 중량이 1이라고 가정하여 분포를 형성합니다.따라서 알림 편의를 위해 j $(\$ 를 $a_{j}$ l $l_{j}a_{j}$ $(\$ 로 $a_{j}$ 하면 다음 LP에 대한 해결 방법을 찾을 수 있습니다.

 $\forall j=1,2,{\text{…}},m:a_{j}x\geq 0$  $}}},$ m $:a_{j}x$  $1*x=1$ \ $geq$ 0}, 1 $1*x=1$ ∗ $=$   $1$  {  $displaystyle 1$ * x $=$ 1 、  $\forall i:x_{i}\geq 0$   $ii$  : x $\forall i:x_{i}\geq 0$ ≥  $\forall i:x_{i}\geq 0$  { $displaystyle$  \  $forall i$  : $\forall i:x_{i}\geq 0$  _ { $i$  } \  $geq$ 0 $\forall i:x_{i}\geq 0$ } 。

이것은 LP의 일반적인 형태입니다.

헤지 알고리즘

헤지 알고리즘은 가중 다수 알고리즘과 유사합니다.그러나 지수 업데이트 규칙은 다릅니다.^[2]일반적으로 자원의 다른 부분을 N개의 다른 옵션에 할당해야 하는 바이너리 할당 문제를 해결하기 위해 사용됩니다.모든 옵션에서의 손실은 모든 반복의 마지막에 사용할 수 있습니다.목표는 특정 배분에 대해 입은 총 손실을 줄이는 것이다.다음 반복에 대한 할당은 곱셈 ^[13]업데이트를 사용하여 현재 반복에서 입은 총 손실에 기초하여 수정된다.

분석.

학습속도 $\eta >0$ { $display$ style \ $eta$ > $0$ for $\eta >0$ 、 t $t\in [T]$ [ $]$ { $displaystyle$ t \ $in$ [ T $t\in [T]$ $p^{t}$ $、$ $p^{t}$ t \ $displaystyle p^$ { t $p^{t}$ } picked picked picked picked picked picked picked picked picked 。그리고 $모든$ 전문가들을 위해 i $.\displaystyle$ i $i$

                                 $\displaystyle \sum _{t\leq T}p^{t}\leq \sum _{t\leq T}m_{i}^{t}+{\frac {ln(N)}{\eta }+\eta T}$

초기화: $\eta >0$ > $\eta >0$ ( $displaystyle \eta > 0$ )를 수정합니다.각 익스퍼트에 대해 $w_{i}^{1}$ ({ $display w_{i}^1})$ $w_{i}^{1}$ for 1 (t=1,2,...T의 경우):

1.  $p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}$   $p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}$  t  $p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}$   $p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}$  t $p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}$  t {  $displaystyle p$ _ {  $i$ }^{ t } = $specfrac$ { w $_$  {  $i$ }^  $t}$  { \ $Phi$  t $}}$  (여기서 $p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}$   $\Phi t=\sum _{i}w_{i}^{t}$  t  $\Phi t=\sum _{i}w_{i}^{t}$   $w$  i  $\Phi t=\sum _{i}w_{i}^{t}$   $\Phi t=\sum _{i}w_{i}^{t}$  i t $\Phi t=\sum _{i}w_{i}^{t}$ \  $Phi$  t = \  $sum _$ { i } $w$  _ { i } $\Phi t=\sum _{i}w_{i}^{t}$ ） $\Phi t=\sum _{i}w_{i}^{t}$ 。 2.  $w_{i}^{t+1}=w_{i}^{t}\exp(-\eta m_{i}^{t}$   $m^{t}$   $m^{t}$  { \ $m^{t}$  m  $^$ {  $t$ } 、 3.  $w_{i}^{t+1}=w_{i}^{t}\exp(-\eta m_{i}^{t}$  t +  $w_{i}^{t+1}=w_{i}^{t}\exp(-\eta m_{i}^{t}$   $w_{i}^{t+1}=w_{i}^{t}\exp(-\eta m_{i}^{t}$   $w_{i}^{t+1}=w_{i}^{t}\exp(-\eta m_{i}^{t}$  t  $exp$  -  $i$  m i t _ 1 + t _ t _  $t }$  ） ） 。

AdaBoost 알고리즘

이 알고리즘은^[12] 트레이닝의 예에 대해 일련의 $w^{t}$ 를 $w^{t}$ 합니다.\ $display style$ w^ { $t$ } 。t $\displaystyle$ t $t$ displaystyle p $^{t}$ 를 $p^{t}$ $t$ 할 때마다 이러한 가중치를 정규화하여 $p^{t}$ p $\$ p^{t}를 계산합니다. $이$ 분포는 약한 학습자 $WeakLearn$ 에게 전달되며, 이는 분포에 $대해$ (바람직하게 $)$ 작은 $h_{t}$ 오류가 있다는 $h_{t}$ 을 $h_{t}$ 합니다 $.$ Using the new hypothesis $h_{t}$ , AdaBoost generates the next weight vector $w^{t+1}$ .프로세스가 반복됩니다.이러한 반복 후 최종 $h_{f}$ $h_{f}$ f ${\$ 는 $h_f$ 출력입니다. $h_{f}$ $h_{f}$ f $(\$ 는 $h_f$ 가중 다수표를 사용하여 ^[12]T 약 가설의 결과를 결합한다.

 $x_{1}$ : 라벨이 붙은N $({displaystyle$   $x_{1$   $({$  ...( $y_{1}$  $({$   $({$ 의 $D$   $시퀀스$ N $({displaystyle$ D $})$ 의 $N$  약한 학습 예ithm "WeakLearn"  $반복$  횟수를 지정하는 $T$   $정수$ T {\ $displaystyle$  T $}$  무게 벡터를  $w_{i}^{1}=D(i)$ 합니다.  $w_{i}^{1}=D(i)$  1  $=$  $D$  (  $w_{i}^{1}=D(i)$ ) {  $displaystyle$  w  $_$ { i }^{ $i$  $i=1$  D ( $w_{i}^{1}=D(i)$ i $w_{i}^{1}=D(i)$  ) $i=1$  1 {  $displaystyle$  n $N$ } $t=1$   $t=1$  .  $displaystyle$  N $= 1$  .  $displaystyle$  ... , $t=1$  $1$  . displaystyle ... $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$  t  $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$   $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$   $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$   $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$  i  $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$   $1$   $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$   $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$   $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$  { { $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$ \  $display style$  p^ { t }  $h_{t}:X\rightarrow$   $sum frac$ { $w$ ^ { t } { \ sum _ { i $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$ = $1$ } { N } $w$ _ {  $i$ }^{  $t$ } $p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}$ } } 。 WeakLearn을 호출하여 p $p^{t}$ t  $p^{t}$  t t  $p^{t}$  t t {\  $display$   $h_{t}:X\rightarrow$  p → p^{  $t$  $h_{t}:X\rightarrow$  } }  $}$   $h_{t}:X\rightarrow$ 을  $h_{t}:X\rightarrow$ . $X\right$  화살표 $}$  [0,1] $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$ . h  $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$ :  $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$  t  $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$   $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$  i  $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$   $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$  N  $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$ t \  $displaystyle$  h $_$  {  $t$  $h_{t}(x_{i})$ } = \  $sum _$ { $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$ i $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$ = $1$  $\beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}$ }^{  $N$ }  $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$  $h_{t}(x_{i})$  $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$ _ {  $i$ }^{ $h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}$  $t$  } $h_{t}(x_{i})$  t ( $x$ i ) $h_{t}(x_{i})$   $\beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}$  h $_$   $\beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}$   $\beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}$  t  $\beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}$  1 .  $\beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}$  t .5. 새로운 무게 벡터를  $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$ t +  $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$   $=$   $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$   $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$   $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$   $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$ 1 -  $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$ t (  $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$ i $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$ ) -  $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$ {  $displaystyle w$ _ {  $i$ }^{ $t$ }\ $display$  _ {  $i$ }^{ t }\display _ { i }^{ 1 - h _ t $w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}$ （ x $_$  {  $i$ } ）- $y$ _ { $i }$ }} 。가설을 출력합니다.

       $f(x)=cases}1&{\text{if}}\sum _{t=1}^{T}\log(1/\beta _{t})h_{t}(x)\geq {frac {1}{2}}\sum _{t=1}^{T}\log(1/\beta _{t}){\frac {q_{1}}{W}}\0&{\text{othery}}\end{cases}$

대략적인 선형^[14] 프로그램 해결

문제

m $m\times n$ × $m\times n$ (\ $displaystyle$ m $\times$ n $)$ $A$ (\ $displaystyle$ A $)$ 및 $b\in \mathbb {R} ^{n}$ (\ $displaystyle b\in\mathbb$ {R $}^{n$ 에 $Ax\geq b$ $Ax\geq b$ b $(\displaystyle$ Ax $\geq$ b $Ax\geq b$ 와 $b\in \mathbb {R} ^{n}$ x(\ $displaystyle$ x $)$ 가 $x$ 있습니까?

 $b$  $Ax\geq$  b $}$  (1)

추정

제로 섬 문제를 해결하는 데, 오류 매개 변수 ϵ하고, 0{\displaystyle \epsilon>0}의 조언를 물어보기 알고리즘을 이용해서, 출력 것 둘 중 어느 것도 된 포인트={\displaystyle)}그런 Ax≥ b− ϵ{Ax\geq b-\epsilon\displaystyle}또는 증거는 x{\displaystyle)}지 않는다 존재하는 서비스, 즉은 없는 해결책 thi.s라인불평등의 ar 체계.

솔루션

$p\in \Delta _{n}$ p $p\in \Delta _{n}$ $p\in \Delta _{n}$ \ $displaystyle$ p \ $in$ \ $Delta$ _ { $n$ } 를 지정하면 다음과 같은 완화 문제가 해결됩니다.

 $?$  $Ax\geq$  p $^{\textsf {T}}\!b}$  (2)

(1)을 만족하는 x가 존재하는 경우 x는 $p\in \Delta _{n}$ $p\in \Delta _{n}$ $\$ p $\in\Delta_{n$ 에 대해 (2)를 만족합니다.이 진술의 대조적인 내용 또한 사실이다.Oracle이 p ${\displaystyle$ p $p$ 에 대해 실행 가능한 솔루션을 반환하는 $경우$ 솔루션 x{\ $displaystyle$ x $\max _{i}|{(Ax)}_{i}-b_{i}|\leq 1$ 가 $x$ bound $\max _{i}|{(Ax)}_{i}-b_{i}|\leq 1$ $\max _{i}|{(Ax)}_{i}-b_{i}|\leq 1$ i ( $\max _{i}|{(Ax)}_{i}-b_{i}|\leq 1$ ) $\max _{i}|{(Ax)}_{i}-b_{i}|\leq 1$ $\max _{i}|{(Ax)}_{i}-b_{i}|\leq 1$ $\max _{i}|{(Ax)}_{i}-b_{i}|\leq 1$ $\max _{i}|{(Ax)}_{i}-b_{i}|\leq 1$ 1 { $displaystyle$ \ $max _$ { $i }$ _ { i } $_$ b $_$ { i } \ $leq$ 1 $\max _{i}|{(Ax)}_{i}-b_{i}|\leq 1$ 1 bounded bounded bounded bounded bounded bounded {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\e system (2) ( $최대$ 2 ${\$ \ $displaystyle$ 2 \ $epsilon$ $2\epsilon$ 。알고리즘은 ${\frac {\ln(m)}{\epsilon ^{2}}}$ 2 ${\frac {\ln(m)}{\epsilon ^{2}}}$ ( ${\frac {\ln(m)}{\epsilon ^{2}}}$ m )의 \ $displaystyle { ln$ ( m $){$ \ $epsilon$ ^ { ${\frac {\ln(m)}{\epsilon ^{2}}}$ }}}을 ${\frac {\ln(m)}{\epsilon ^{2}}}$ (를) 호출하여 문제를 해결합니다.반대론도 역시 사실이다.이 경우 곱셈 업데이트가 알고리즘에 적용됩니다.

기타 응용 프로그램

진화 게임 이론

곱셈 가중치 업데이트는 진화 게임 이론에서 일반적으로 사용되는 모델인 복제자 방정식(복제자 역학)의 이산 시간 변형이다.폭주 ^[15]게임에 적용하면 내쉬 평형으로 수렴됩니다.

운영 조사 및 온라인 통계 의사결정^[1]

운영 연구 및 온라인 통계 의사 결정 문제 분야에서는 가중 다수 알고리즘과 더 복잡한 버전이 독립적으로 발견되었습니다.

계산기하학

곱셈 가중치 알고리즘은 클락슨의 선형 프로그래밍(LP) 알고리즘과 같은 계산 ^[1]기하학에도 선형 ^[4]^[5]시간에 변수 수가 한정되어 광범위하게 적용된다.나중에 Bronnimann과 Goodrich는 VC ^[6]치수가 작은 하이퍼그래프에 대해 Set Covers를 찾기 위해 유사한 방법을 사용했다.

경사 강하법^[1]

행렬 곱셈 가중치^[1] 업데이트

LP^[1] 포장/커버용 Plotkin, Shmoys, Tardos 프레임워크

멀티커뮤니티 플로우^[1] 문제에 대한 근사치

O(logn) - 많은 NP-hard^[1] 문제에 대한 근사치

이론 학습 및 활성화^[1]

하드코어 세트와 XOR 보조어^[1]

한난 알고리즘과 곱셈^[1] 가중치

온라인 볼록 최적화^[1]

레퍼런스

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q ^r ^s Arora, Sanjeev; Hazan, Elad; Kale, Satyen (2012). "The Multiplicative Weights Update Method: A Meta-Algorithm and Applications". Theory of Computing. 8: 121–164. doi:10.4086/toc.2012.v008a006.
^ ^a ^b ^c ^d ^e ^f ^g "The Multiplicative Weights Algorithm*" (PDF). Retrieved 9 November 2016.
^ Grigoriadis, Michael D.; Khachiyan, Leonid G. (1995). "A sublinear-time randomized approximation algorithm for matrix games". Operations Research Letters. 18 (2): 53–58. doi:10.1016/0167-6377(95)00032-0.
^ ^a ^b 케네스 L. 클락슨크기가 작을 때 선형 프로그래밍을 위한 라스베이거스 알고리즘. Proc. 29th FOCS, 페이지 452–456.IEEE Comp.SOC. 프레스, 1988년[doi:10.1109/SFCS.1988.21961]123, 152
^ ^a ^b 케네스 L. 클락슨크기가 작을 때 선형 및 정수 프로그래밍을 위한 라스베이거스 알고리즘, ACM 저널, 42:488–499, 1995.[doi:10.1145/201019.201036]123, 152
^ ^a ^b H. 브로니만과 M.T. 굿리치유한 VC 차원에서의 거의 최적의 세트 커버, 이산 컴퓨터. 검, 14:463~479, 1995.10일 앤의 예비판.공감, 공감.검(SCG'94)[doi:10.1007/BF02570718] 123, 152
^ "Lecture 8: Decision-making under total uncertainty: the multiplicative weight algorithm" (PDF). 2013.
^ "COS 511: Foundations of Machine Learning" (PDF). 20 March 2006.
^ ^a ^b ^c "An Algorithmist's Toolkit". 8 December 2009. Retrieved 9 November 2016.
^ 베일리, 제임스 P, 게오르기오스 필리우라스입니다제로섬 게임에서는 가중치 승수가 갱신된다.2018년 ACM 경제연산에 관한 회의의 진행.ACM, 2018년
^ Foster, Dean P.; Vohra, Rakesh (1999). "Regret in the on-line decision problem" (PDF). Games and Economic Behavior. 29 (1–2): 7–35. doi:10.1006/game.1999.0740.
^ ^a ^b ^c 요아브, 프룬드로버트, E. Schapire(1996년).TA 의사결정 - 온라인 학습의 이론적인 일반화 및 Application to Boosting*, 55페이지. 컴퓨터 및 시스템 과학 저널.
^ "Online Learning from Experts: Weighed Majority and Hedge" (PDF). Retrieved 7 December 2016.
^ "Fundamentals of Convex Optimization" (PDF). Retrieved 9 November 2016.
^ 클라인버그, 로버트, 게오르기오스 필리우라스, 에바 타도스."승수 업데이트는 정체 게임에서의 일반적인 무후회 학습보다 성능이 뛰어납니다."제41회 ACM 연례 컴퓨터 이론 심포지엄의 진행.ACM, 2009.

외부 링크

생명의 게임 이론 Erick Chastain, Adi Livnat, Christos Papadimitriou 및 Umesh Vazirani의 논문에서 진화생물학의 방법 사용을 설명하는 Quanta 매거진 기사

[ref1-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q ^r ^s Arora, Sanjeev; Hazan, Elad; Kale, Satyen (2012). "The Multiplicative Weights Update Method: A Meta-Algorithm and Applications". Theory of Computing. 8: 121–164. doi:10.4086/toc.2012.v008a006.

[ref2-2] ^ ^a ^b ^c ^d ^e ^f ^g "The Multiplicative Weights Algorithm*" (PDF). Retrieved 9 November 2016.

[3] Grigoriadis, Michael D.; Khachiyan, Leonid G. (1995). "A sublinear-time randomized approximation algorithm for matrix games". Operations Research Letters. 18 (2): 53–58. doi:10.1016/0167-6377(95)00032-0.

[Kenneth_L._Clarkson_pp._452-4] 케네스 L. 클락슨크기가 작을 때 선형 프로그래밍을 위한 라스베이거스 알고리즘. Proc. 29th FOCS, 페이지 452–456.IEEE Comp.SOC. 프레스, 1988년[doi:10.1109/SFCS.1988.21961]123, 152

[Kenneth_L._Clarkson_1995-5] 케네스 L. 클락슨크기가 작을 때 선형 및 정수 프로그래밍을 위한 라스베이거스 알고리즘, ACM 저널, 42:488–499, 1995.[doi:10.1145/201019.201036]123, 152

[M.T._GOODRICH._1995-6] H. 브로니만과 M.T. 굿리치유한 VC 차원에서의 거의 최적의 세트 커버, 이산 컴퓨터. 검, 14:463~479, 1995.10일 앤의 예비판.공감, 공감.검(SCG'94)[doi:10.1007/BF02570718] 123, 152

[ref5-7] "Lecture 8: Decision-making under total uncertainty: the multiplicative weight algorithm" (PDF). 2013.

[ref6-8] "COS 511: Foundations of Machine Learning" (PDF). 20 March 2006.

[ref7-9] "An Algorithmist's Toolkit". 8 December 2009. Retrieved 9 November 2016.

[Bailey_and_Piliouras_EC18-10] 베일리, 제임스 P, 게오르기오스 필리우라스입니다제로섬 게임에서는 가중치 승수가 갱신된다.2018년 ACM 경제연산에 관한 회의의 진행.ACM, 2018년

[11] Foster, Dean P.; Vohra, Rakesh (1999). "Regret in the on-line decision problem" (PDF). Games and Economic Behavior. 29 (1–2): 7–35. doi:10.1006/game.1999.0740.

[ref8-12] 요아브, 프룬드로버트, E. Schapire(1996년).TA 의사결정 - 온라인 학습의 이론적인 일반화 및 Application to Boosting*, 55페이지. 컴퓨터 및 시스템 과학 저널.

[ref16-13] "Online Learning from Experts: Weighed Majority and Hedge" (PDF). Retrieved 7 December 2016.

[ref11-14] "Fundamentals of Convex Optimization" (PDF). Retrieved 9 November 2016.

[Kleinberg,_Piliouras,_Tardos_09-15] 클라인버그, 로버트, 게오르기오스 필리우라스, 에바 타도스."승수 업데이트는 정체 게임에서의 일반적인 무후회 학습보다 성능이 뛰어납니다."제41회 ACM 연례 컴퓨터 이론 심포지엄의 진행.ACM, 2009.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Search

승수 가중치 갱신 방법

네임스페이스

더

목차

이름.

이력 및 배경

일반적인 셋업

알고리즘 분석

절반^[2] 알고리즘

가중 다수 알고리즘^[1]^[7]

랜덤화 가중치 다수^[2]^[8] 알고리즘

적용들

제로섬 게임 대략 해결(Oracle 알고리즘):^[1]^[9]

기계 학습

윈노우 알고리즘

헤지 알고리즘

분석.

AdaBoost 알고리즘

대략적인 선형^[14] 프로그램 해결

문제

추정

솔루션

기타 응용 프로그램

진화 게임 이론

운영 조사 및 온라인 통계 의사결정^[1]

계산기하학

경사 강하법^[1]

행렬 곱셈 가중치^[1] 업데이트

LP^[1] 포장/커버용 Plotkin, Shmoys, Tardos 프레임워크

멀티커뮤니티 플로우^[1] 문제에 대한 근사치

O(logn) - 많은 NP-hard^[1] 문제에 대한 근사치

이론 학습 및 활성화^[1]

하드코어 세트와 XOR 보조어^[1]

한난 알고리즘과 곱셈^[1] 가중치

온라인 볼록 최적화^[1]

레퍼런스

외부 링크

Search

승수 가중치 갱신 방법

이름.

이력 및 배경

일반적인 셋업

알고리즘 분석

절반[2] 알고리즘

가중 다수 알고리즘[1][7]

랜덤화 가중치 다수[2][8] 알고리즘

적용들

제로섬 게임 대략 해결(Oracle 알고리즘):[1][9]

기계 학습

윈노우 알고리즘

헤지 알고리즘

분석.

AdaBoost 알고리즘

대략적인 선형[14] 프로그램 해결

문제

추정

솔루션

기타 응용 프로그램

진화 게임 이론

운영 조사 및 온라인 통계 의사결정[1]

계산기하학

경사 강하법[1]

행렬 곱셈 가중치[1] 업데이트

LP[1] 포장/커버용 Plotkin, Shmoys, Tardos 프레임워크

멀티커뮤니티 플로우[1] 문제에 대한 근사치

O(logn) - 많은 NP-hard[1] 문제에 대한 근사치

이론 학습 및 활성화[1]

하드코어 세트와 XOR 보조어[1]

한난 알고리즘과 곱셈[1] 가중치

온라인 볼록 최적화[1]

레퍼런스

외부 링크

절반^[2] 알고리즘

가중 다수 알고리즘^[1]^[7]

랜덤화 가중치 다수^[2]^[8] 알고리즘

제로섬 게임 대략 해결(Oracle 알고리즘):^[1]^[9]

대략적인 선형^[14] 프로그램 해결

운영 조사 및 온라인 통계 의사결정^[1]

경사 강하법^[1]

행렬 곱셈 가중치^[1] 업데이트

LP^[1] 포장/커버용 Plotkin, Shmoys, Tardos 프레임워크

멀티커뮤니티 플로우^[1] 문제에 대한 근사치

O(logn) - 많은 NP-hard^[1] 문제에 대한 근사치

이론 학습 및 활성화^[1]

하드코어 세트와 XOR 보조어^[1]

한난 알고리즘과 곱셈^[1] 가중치

온라인 볼록 최적화^[1]