これらのキーワードがハイライトされています:データストリーム
Winnow†
目的変数が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\) に関する収束条件,学習可能な問題のクラスなどが示されていて,この種のアルゴリズムのパイオニアとなった.
-- しましま
関連項目†
リンク集†
関連文献†