Winnow(알고리즘)

윈나우 알고리즘은^[1] 라벨이 부착된 예에서 선형 분류기를 학습하기 위한 기계학습의 기법이다.그것은 지각 알고리즘과 매우 유사하다.단, 퍼셉트론 알고리즘은 부가적인 무게-업데이트 방식을 사용하는 반면, 위노우(Winnow)는 여러 차원이 무관할 때(이름 winnow) 훨씬 더 좋은 성능을 발휘할 수 있는 승법 방식을 사용한다.고차원 데이터에 맞게 잘 스케일링되는 간단한 알고리즘이다.훈련 중에 위나우는 일련의 긍정적인 예와 부정적인 예들을 보여준다.이것들로부터 그것은 새로운 예들을 긍정적이거나 부정적이거나 라벨을 붙이는 데 사용될 수 있는 의사결정 하이퍼플레인지를 배운다.학습과 분류 단계가 명확히 구분되지 않는 온라인 학습 환경에서도 알고리즘을 사용할 수 있다.

알고리즘.

기본 알고리즘인 Winnow1은 다음과 같다.인스턴스 공간은 $X{\displaystyle }$=${\displaystyle }${ 0${\displaystyle ,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\$ 즉 각 인스턴스는 부울 값 기능 집합으로 설명된다.알고리즘은 초기에 각 형상에 대해 ${\displaystyle 1}$의 무게로 설정된 $i$${\displaystyle \in \{1}$,${\displaystyle }$…${\displaystyle }$, n ${\displaystyle \}}$ ${\displaystyle i\in \{1,\ldots ,n\}$에 대해 i$${\$displaystyle w_{i}}$의 음이 아닌 가중치를 유지한다.학습자에게 예$({\displaystyle {x\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, x ${\displaystyle n_{}}$) ${\displaystyle (x_{1},\ldots ,x_{n}})$가 주어지면, 다음과 같은 선형 분류자에 대한 일반적인 예측 규칙을 적용한다$.$

• = i > ${\displaystyle \sum _{i=1}^{n_${n$}w_{i}x_{i}}>$인 경우$\Teta },$그런 다음 1을 예측하십시오.
• 그렇지 않으면 0을 예측하십시오.

여기서 $\theta {\displaystyle \mathrm{}}$ ${\displaystyle \Teta }$은(는) 임계값이라고 하는 실제 수입니다.임계값은 가중치와 함께 인스턴스 공간에서 분할 하이퍼 평면을 정의한다.$\theta {\displaystyle \mathrm{}}$= ${\displaystyle n}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \Teta =n/2}$일 경우 양호한 한도를 구한다($$아래 참조).

학습자가 제시된 각 예에 대해 다음과 같은 업데이트 규칙을 적용한다.

• 예를 올바르게 분류하면 아무 것도 하지 마십시오.
• 예를 잘못 예측하고 올바른 결과가 0인 경우, 각 $형상{\displaystyle {}_{}}$ x${\displaystyle {}_{}{i}_{}}$ = ${\displaystyle 1}${\$displaystyle x_{i}=$1}에 대해 해당 ${\displaystyle {가중치}_{}}$ w${\$가 0(데모션$$ 단계)으로 설정된다$.$

  ${\displaystyle \forall x_{i}=1,w_{i}=0}$

• 예를 잘못 예측하고 올바른 결과가 1인 경우, 각 형상 ${\displaystyle x_{}}$ i${\displaystyle {}_{}}$= ${\displaystyle 1}$ ${\displaystyle x_{i}=1}$에 대해 ${\displaystyle {해당}_{}}$하는 w${\$에 α(추진 단계)를$$ 곱한 값$.$

  ${\displaystyle \forall x_{i}=1,w_{i}=\display w_{i}}$

α의 대표적인 값은 2이다.

이 기본적인 접근법에는 많은 변화가 있다.Winnow2는^[1] 강등 단계에서 가중치를 0으로 설정하지 않고 α로 나눈다는 점을 제외하면 유사하다. Balance Winnow는 두 세트의 가중치를 유지하며, 따라서 두 개의 하이퍼플레인을 유지한다.그런 다음 다중 라벨 분류에 대해 일반화할 수 있다.

실수 한계

어떤 상황에서는 위노우가 학습하면서 저지르는 실수 횟수가 제시된 인스턴스 수와 무관한 상한선을 가지고 있음을 보여줄 수 있다.만약 Winnow1는 뼈대는 표적 기능에α 1{\displaystyle \alpha 1}과Θ ≥ 1/α{\displaystyle \Theta 1/\alpha \geq}을 사용하는 k{k\displaystyle}-literalmonotone 분야와의 괴리 f(x1,…,)n)에 의해=지정된)나는 1∪ ⋯ ∪)나는 k{\displaystyle f(x_{1},\ldots{n,x_})=x_{i_{1.}}\c$\cdots \cdots$ \cup x_${i_{k}}$을$($를) 선택한 다음, 일련의 경우에서 총 실수 횟수는 $\alpha k{\displaystyle (\mathrm{로그}}$ ${\displaystyle {\alpha }_{}\mathrm{\alpha }}$ ⁡${\displaystyle }$+ + ${\displaystyle 1}$)${\displaystyle }$+ n ${\displaystyle \frac{\mathrm{n}}{}}$ $\$ style $\alpha$ k$(\log _{\alpha }}\ta +1)+{\frac {$n}{n}{n$}{$n}{n}로 제한된다.$세타$ $\}\}.$^[2]

참조