選別（アルゴリズム）

ウィノウアルゴリズム^{[1]は、ラベル付けされた例から}線形分類器を学習する機械学習の手法です。パーセプトロンアルゴリズムと非常によく似ています。ただし、パーセプトロンアルゴリズムは加法的重み更新方式を使用するのに対し、ウィノウは乗法方式を使用するため、多くの次元が無関係な場合にパフォーマンスが大幅に向上します (そのため、ウィノウという名前が付けられています)。これは、高次元データにうまく適応する単純なアルゴリズムです。トレーニング中、ウィノウには一連の正例と負例が示されます。これらから、新しい例を正または負としてラベル付けするために使用できる決定超平面を学習します。このアルゴリズムは、学習フェーズと分類フェーズが明確に分離されていないオンライン学習設定でも使用できます。

基本アルゴリズム Winnow1 は次のとおりです。インスタンス空間は、つまり、各インスタンスはブール値の特徴のセットとして記述されます。アルゴリズムはの非負の重みを維持します。重みは最初は 1 に設定され、特徴ごとに 1 つの重みがあります。学習器に例 が与えられると、線形分類器の一般的な予測ルールが適用されます。 ${\displaystyle X=\{0,1\}^{n}}$ ${\displaystyle w_{i}}$${\displaystyle i\in \{1,\ldots ,n\}}$${\displaystyle (x_{1},\ldots,x_{n})}$

• ならば 、1を予測する${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}>\Theta }$
• それ以外の場合は0を予測する

ここで、しきい値と呼ばれる実数があります。重みとともに、しきい値はインスタンス空間内の分割超平面を定義します。適切な境界は、次の場合に得られます(以下を参照)。 ${\displaystyle \Theta}$${\displaystyle \Theta =n/2}$

提示される各例に対して、学習者は次の更新ルールを適用します。

• 例が正しく分類されている場合は何も行いません。
• 例が誤って予測され、正しい結果が 0 だった場合、各特徴に対して、対応する重みが 0 に設定されます (降格ステップ)。 ${\displaystyle x_{i}=1}$${\displaystyle w_{i}}$

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

• 例が誤って予測され、正しい結果が 1 だった場合、各特徴に対して、対応する重みにαを掛けます(昇格ステップ)。 ${\displaystyle x_{i}=1}$${\displaystyle w_{i}}$

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

αの典型的な値は2 です。

この基本的なアプローチには多くのバリエーションがあります。Winnow2 ^{[1] は、}降格ステップで重みが0 に設定されるのではなく αで除算されることを除いて同様です。Balanced Winnow は2 セットの重み、つまり 2 つの超平面を維持します。これは、マルチラベル分類に一般化できます。

特定の状況では、Winnow が学習する際に発生する間違いの数には、提示されるインスタンスの数とは無関係な上限があることが示されます。Winnow1 アルゴリズムが、によって与えられる -リテラル単調論理和であるターゲット関数に対してと を使用する場合、インスタンスの任意のシーケンスに対して、間違いの合計数は によって制限されます 。^[2]${\displaystyle \alpha >1}$${\displaystyle \Theta \geq 1/\alpha }$${\displaystyle k}$${\displaystyle f(x_{1},\ldots ,x_{n})=x_{i_{1}}\cup \cdots \cup x_{i_{k}}}$${\displaystyle \alpha k(\log _{\alpha }\Theta +1)+{\frac {n}{\Theta }}}$