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\) に関する収束条件,学習可能な問題のクラスなどが示されていて,この種のアルゴリズムのパイオニアとなった.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:11:28 (2487d)