Winnow - 機械学習の「朱鷺の杜Wiki」

[ トップ ] [ 編集 | 凍結 | 差分 | 履歴 | 添付 | リロード ] [ 新規 | 一覧 | 検索 | 最終更新 | ヘルプ | ログイン ]

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

-- しましま

関連項目†

リンク集†

関連文献†

基本文献
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節

朱鷺の杜Wiki

参加しよう

Wiki超入門
練習用ページ
数式の表示
こびとさん
編集用ID: ibis
パスワード: 「VC次元」のVのフルスペルで最初だけ大文字

最新の30件
2024-12-21
- しましま/IBISML055
2024-11-07
- しましま/IBIS2024
2024-11-04
- IBIS
2024-05-31
- 人工知能学会全国大会
- しましま/人工知能学会全国大会2024
2024-04-13
- python
2024-04-09
- K-NEL
- K-NEL/errata
2023-11-22
- PRML/errata2
2023-11-21
- PRML/errata1
2023-11-01
- しましま/IBIS2023
2023-06-11
- しましま/人工知能学会全国大会2023
2023-03-28
- Book
2022-11-27
- 朱鷺の社
2022-11-24
- しましま/IBIS2022
2022-07-08
- AutoTicketLinkName
2022-06-17
- しましま/人工知能学会全国大会2022
2021-11-13
- しましま/IBIS2021
2021-10-29
- 回帰分析
2021-06-11
- しましま/人工知能学会全国大会2021
2021-03-07
- MenuBar
2021-02-15
- python/numpy
2020-12-22
- 特異値分解
2020-12-18
- complement naive Bayes
2020-11-27
- しましま/IBIS2020
2020-10-17
- Paper/bias-on-the-web
2020-07-16
- F値
2020-06-30
- DataSet
2020-06-24
- バイアス-バリアンス
2020-06-10
- Paper

カウンタ

累計: 8413
今日: 1
昨日: 3

Last-modified: 2010-02-11 (木) 16:11:28