線形分類器

提供: miniwiki
移動先:案内検索

線形分類器: Linear classifier)は、特徴の線形結合の値に基づいて分類を行う確率的分類器である。機械学習において、分類は項目群を特徴値に基づいてグループに分類することを目的とする。

定義

分類器への入力特徴ベクトルが実数ベクトル [math]\vec x[/math] であるとき、出力のスコアは次のようになる。

[math]y = f(\vec{w}\cdot\vec{x}) = f\left(\sum_j w_j x_j\right)[/math]

ここで、[math]\vec w[/math] は重み付けの実数ベクトル、f は2つのベクトルのドット積を必要な出力に変換する関数である。重み付けベクトル [math]\vec w[/math] はラベル付き訓練例で学習することで変化していく。f はあるしきい値以上の値を第一クラスに分類し、それ以外を第二クラスに分類するといった単純な関数であることが多い(二項分類)。より複雑な f としては、ある項目があるクラスに属する確率を与えるものなどがある。

二項分類問題は、高次元の入力空間を超平面で分割する操作として視覚化できる。その超平面の一方の側にある点は分類において "yes" とされた点であり、もう一方の側にある点は "no" とされた点である。

線形分類器は、特に [math]\vec x[/math] が疎であるとき最も高速な分類器であるため、分類の速度が重要な場合に使われることが多い。ただし、決定木の方が速い場合もある。また、線形分類器は [math]\vec x[/math] の次元が大きいときにうまく機能する。例えば、文書分類において [math]\vec x[/math] の各要素は文書における個々の単語の出現回数などになる。そのような場合、線形分類器は正則化されているべきである。

生成的モデルと識別的モデル

線形分類器 [math]\vec w[/math] のパラメータを決定する手法は大まかに2つに分類される[1][2]。1つは条件付き確率 [math]P(\vec x|{\rm class})[/math] をモデル化したものである。そのようなアルゴリズムとして以下のものがある。

2つめは識別モデルと呼ばれるもので、訓練例の出力の品質を最大化しようとするものである。訓練コスト関数に項を追加することで、最終モデルの正則化が容易に実現できる。線形分類器の識別訓練の例として、以下のものがある。

  • ロジスティック回帰 - 観測された訓練例が分類器の出力に依存した二項分布モデルで生成されたものと見なし、[math]\vec w[/math] を最尤推定する。
  • パーセプトロン - 訓練例の学習時に発生した全ての誤りを正そうとするアルゴリズム
  • 線形サポートベクターマシン - 判断超平面と訓練例との間の余白を最大化するアルゴリズム

なお英語でいうと、線形判別分析(Linear Discriminant Analysis)と識別モデル(Discriminative Model)は関連がありそうだが、上のように分類されている。LDAは主成分分析(Principal Component Analysis、PCA)との対比で意味を持つ名前である。LDAは教師あり学習アルゴリズムであり、PCAは教師なし学習アルゴリズムである。[3]

識別訓練は条件付き確率分布をモデル化する方式よりも正確であることが多い。しかし、欠落データの扱いは条件付き確率分布モデルの方が容易なことが多い。

上述の線形分類器のアルゴリズムはいずれも、カーネルトリックを使って、異なる入力空間 [math]\varphi(\vec x)[/math] 上の非線形アルゴリズムに変換できる。

関連項目

脚注

  1. T. Mitchell, Generative and Discriminative Classifiers: Naive Bayes and Logistic Regression. Draft Version, 2005 download(PDF)
  2. A. Y. Ng and M. I. Jordan. On Discriminative vs. Generative Classifiers: A comparison of logistic regression and Naive Bayes. in NIPS 14, 2002. download(PS)
  3. R.O. Duda, P.E. Hart, D.G. Stork, "Pattern Classification", Wiley, (2001). ISBN 0-471-05669-3

参考文献

  1. Y. Yang, X. Liu, "A re-examination of text categorization", Proc. ACM SIGIR Conference, pp. 42-49, (1999). paper @ citeseer
  2. R. Herbrich, "Learning Kernel Classifiers: Theory and Algorithms," MIT Press, (2001). ISBN 0-262-08306-X