Winnow の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Winnow へ行く。

* Winnow [#yf8c539d]

//ここには %項目の説明を書いてください．よろしければ署名しておいてください．

目的変数が2値，\(n\)個の特徴量も全て2値の場合の逐次学習アルゴリズム．

線形関数 \(f=w_1x_1+\cdots+w_nx_n\) について，\(f\gt\theta\) なら 1 に，でなければ 0 に分類する．また，係数\(\alpha\gt 1\) を定める．
- 新たな事例，すなわち，長さ\(n\)の2値ベクトルと2値の目的変数の対が与えられたとき
-- 正しく分類されたなら，重みはそのまま
-- 誤分類された場合は
--- 事例のクラスが1のとき，特徴ベクトルの要素 \(x_i\) が 1 のものは，その重み \(w_i\)を \(\alpha\)倍する．
--- 事例のクラスが0のとき，特徴ベクトルの要素 \(x_i\) が 1 のものは，その重み \(w_i\)を \(\alpha\)で割る．

単純なアルゴリズムだが，PAC学習の観点から理論的な誤り率の限界，\(\alpha\) に関する収束条件，学習可能な問題のクラスなどが示されていて，この種のアルゴリズムのパイオニアとなった．

> -- しましま

** 関連項目 [#j17b7ac7]

//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．
-[[クラス分類]]
-[[逐次学習]]
-[[データストリーム]]
-[[PAC学習]]
#br
-[[検索:Winnow]]

** リンク集 [#zd7c4952]

//関連するWWW資源があればリンクしてください．

** 関連文献 [#gde910fd]

//この%項目%に関連する書籍や論文を紹介してください．

-基本文献~
N.Littlestone "Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm" Machine Learning, vol.2, pp.285-318 (1988)~
[[GoogleScholarAll:Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm]]
-[[Book/Data Mining - Practical Machine Learning Tools and Techniques]] 4.6節 Linear classification Winnow
-[[Book/Pattern Classification]] 5.5.3節