線形分類器

機械学習では、線形分類器が各オブジェクトの特徴の線形結合に基づいて分類の決定を行います。このような分類器は、文書分類などの実用的な問題や、より一般的には多くの変数（特徴）を持つ問題に適しており、非線形分類器に匹敵する精度レベルに達しながら、トレーニングと使用にかかる時間が短くなります。^[1]

意味

分類器への入力特徴ベクトルが実数ベクトルの場合、出力スコアは ${\vec {x}}$

y=f({\vec {w}}\cdot {\vec {x}})=f\left(\sum _{j}w_{j}x_{j}\right),

ここで、は重みの実数ベクトルであり、f は2 つのベクトルのドット積を目的の出力に変換する関数です。（言い換えると、はRへの1 形式または線形関数マッピングです。）重みベクトルは、ラベル付けされたトレーニングサンプルのセットから学習されます。fは多くの場合、しきい値関数であり、特定のしきい値を超えるのすべての値を最初のクラスに、その他のすべての値を 2 番目のクラスにマッピングします。例: ${\vec {w}}$ ${\vec {w}}$ ${\vec {x}}$ ${\vec {w}}$ ${\vec {w}}\cdot {\vec {x}}$

f(\mathbf {x} )={\begin{cases}1&{\text{if }}\ \mathbf {w} ^{T}\cdot \mathbf {x} >\theta ,\\0& {\text{その他}}\end{ケース}}

上付き文字の T は転置を示し、スカラーしきい値です。より複雑なf は、アイテムが特定のクラスに属する確率を示す場合があります。 $\theta$

2 クラス分類問題の場合、線形分類器の動作を、高次元の入力空間を超平面で分割するものとして視覚化できます。超平面の片側にあるすべてのポイントは「はい」に分類され、他のポイントは「いいえ」に分類されます。

線形分類器は、分類の速度が問題となる状況でよく使用されます。これは、特にがスパースな場合に、最も高速な分類器となることが多いためです。また、線形分類器は、の次元数が大きい場合に非常にうまく機能します。たとえば、文書分類では、の各要素は通常、文書内の単語の出現回数です (文書-用語行列を参照)。このような場合、分類器は適切に正規化されている必要があります。 ${\vec {x}}$ ${\vec {x}}$ ${\vec {x}}$

生成モデルと識別モデル

線形分類器のパラメータを決定する方法には、大きく分けて2つの種類があります。生成モデルと識別モデルです。 ^[2]^[3]前者の方法は結合確率分布をモデル化し、後者の方法は条件付き密度関数をモデル化します。このようなアルゴリズムの例には次のものがあります。 ${\vec {w}}$ $P({\rm {class}}|{\vec {x}})$

線形判別分析（LDA） -ガウス条件付き密度モデルを想定
多項式または多変量ベルヌーイイベントモデルを使用した単純ベイズ分類器。

2 番目の方法セットには、トレーニングセットの出力の品質を最大化しようとする識別モデルが含まれます。トレーニングコスト関数の追加項により、最終モデルの正規化を簡単に実行できます。線形分類器の識別トレーニングの例には、次のものがあります。

ロジスティック回帰—観測されたトレーニングセットが分類器の出力に依存する二項モデルによって生成されたと仮定した最大尤度推定。 ${\vec {w}}$
パーセプトロン— トレーニングセットで発生したすべてのエラーを修正しようとするアルゴリズム
フィッシャーの線形判別分析 - 他の仮定を置かずにクラス間散布とクラス内散布の比率を最大化するアルゴリズム（「LDA」とは異なる）。本質的には、バイナリ分類の次元削減手法です。^[4]
サポートベクターマシン—決定超平面とトレーニングセット内の例の間のマージンを最大化するアルゴリズム。

注: その名前にもかかわらず、LDA はこの分類法の識別モデルのクラスには属しません。しかし、LDA を他の主要な線形次元削減アルゴリズムである主成分分析(PCA) と比較すると、その名前は意味をなします。LDA はデータのラベルを利用する教師あり学習アルゴリズムですが、PCA はラベルを無視する教師なし学習アルゴリズムです。要約すると、その名前は歴史的な遺物です。^[5]

判別トレーニングは、条件付き密度関数をモデル化するよりも高い精度が得られることが多い^{[引用が必要]}。ただし、欠損データの処理は条件付き密度モデルの方が簡単な場合が多い^{[引用が必要]}。

上記のすべての線形分類アルゴリズムは、カーネルトリックを使用して、異なる入力空間で動作する非線形アルゴリズムに変換できます。 $\varphi ({\vec {x}})$

識別訓練

線形分類器の識別訓練は、通常、望ましい出力を持つ訓練セットと分類器の出力と望ましい出力の差を測定する損失関数を与えられた最適化アルゴリズムによって、教師あり方式で進められる。したがって、学習アルゴリズムは、次の形式の最適化問題を解く^[1]

{\underset {\mathbf {w} }{\arg \min }}\;R(\mathbf {w} )+C\sum _{i=1}^{N}L(y_{i} ,\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i})

どこ

$wは$ 分類器パラメータのベクトルであり、
$L (y i, w T x i)は、分類器の予測と$ $i$ 番目のトレーニング例の $実際の出力y i$ との間の差異を測定する損失関数です
$R (w) は$ 、パラメータが大きくなりすぎること（過剰適合を引き起こすこと）を防ぐ正規化関数であり、
$C は$ 、正規化と損失関数のバランスを制御するスカラー定数 (学習アルゴリズムのユーザーによって設定) です。

一般的な損失関数には、ヒンジ損失（線形SVMの場合）とログ損失（線形ロジスティック回帰の場合）があります。正則化関数 $R$ が凸の場合、上記は凸問題です。^{[1]このような問題を解決するためのアルゴリズムは多数存在します。線形分類の一般的なものには、（}確率的）勾配降下法、L-BFGS、座標降下法、ニュートン法などがあります。

参照

注記

^ abc Guo-Xun Yuan; Chia-Hua Ho; Chih-Jen Lin (2012). 「大規模線形分類の最近の進歩」(PDF)。Proc . IEEE。100 (9). 2017-06-10にオリジナルからアーカイブ(PDF) 。
^ T. ミッチェル、生成的分類器と識別的分類器: ナイーブベイズとロジスティック回帰。ドラフト版、2005 年
^ AY Ng および MI Jordan。識別的分類器と生成的分類器について: ロジスティック回帰と Naive Bayes の比較。NIPS 14、2002 年。
^ RO Duda、PE Hart、DG Stork、「パターン分類」、Wiley、 ( 2001)。ISBN 0-471-05669-3
^ Duda, Richard O.; Hart, Peter E.; Stork, David G. (2001).パターン分類。Wiley-Interscience 刊行物 (第 2 版)。ニューヨーク、チチェスター、ワインハイム、ブリスベン、シンガポール、トロント: John Wiley & Sons, Inc. p. 117。ISBN 978-0-471-05669-0。

さらに読む

Y. Yang、X. Liu、「テキスト分類の再検討」、Proc. ACM SIGIR Conference、pp. 42–49、(1999)。論文 @ citeseer
R. Herbrich、「Learning Kernel Classifiers: Theory and Algorithms」、MIT Press、(2001)。ISBN 0-262-08306 -X

[ieee-1] Guo-Xun Yuan; Chia-Hua Ho; Chih-Jen Lin (2012). 「大規模線形分類の最近の進歩」(PDF)。Proc . IEEE。100 (9). 2017-06-10にオリジナルからアーカイブ(PDF) 。

[2] T. ミッチェル、生成的分類器と識別的分類器: ナイーブベイズとロジスティック回帰。ドラフト版、2005 年

[3] AY Ng および MI Jordan。識別的分類器と生成的分類器について: ロジスティック回帰と Naive Bayes の比較。NIPS 14、2002 年。

[4] ^ RO Duda、PE Hart、DG Stork、「パターン分類」、Wiley、 ( 2001)。ISBN 0-471-05669-3

[5] Duda, Richard O.; Hart, Peter E.; Stork, David G. (2001).パターン分類。Wiley-Interscience 刊行物 (第 2 版)。ニューヨーク、チチェスター、ワインハイム、ブリスベン、シンガポール、トロント: John Wiley & Sons, Inc. p. 117。ISBN 978-0-471-05669-0。