読者です 読者をやめる 読者になる 読者になる

IIR15章まとめ

15章では、サポートベクターマシンとドキュメントにおける機械学習について説まとめている。

サポートベクターマシン(Support Vector Machines)

サポートベクターマシン(SVM)は、データを2クラスに分類する高性能な線形識別アルゴリズムである。

まず、訓練データを2クラスに線形分類する。

データ点に接するまでの境界の幅をマージンと呼び、これが最大となるように、識別線を決定する。これをマージン最大化という。

また、境界上の点をサポートベクターと呼ぶ。

なぜマージン最大化?

  • 安全である。
  • 境界の位置に微小な誤りがあったとしても、誤識別される可能性が低い。

具体的には、以下の識別関数により-1か1を出力する。

SVMの拡張

以下、訓練データが線形分離不可能な場合の手法を考える。

ソフトマージン分類法

ソフトマージン分類法は、データセットが線形分離できない場合に、多少の誤りを許す分類法。

多クラスSVM

2クラス分類を行うSVMを用いて、多クラス分類を行うSVMを作成する。

以下の2つの手法がある。|C|をクラス数とする。

  • One-Versus-Rest分類法

1つのクラスと残りすべてのクラスのデータをSVMで分離する。
C個のSVMが必要になる。

  • One-Versus-One分類法

2クラスの組合せを作り、それぞれをSVMで分離する。
C(C-1)/2個のSVMが必要になる。

カーネルトリック

例えば、以下のようなデータセットは線形分離できない。

しかし、これを以下のように2次元空間に写像すると、線形分離できてしまう。

このように、訓練データを高次元空間に写像し、その写像された空間上で線形分離を行うことを、カーネルトリックという。

これにより、SVMの性能を飛躍的に向上させることが可能になったといえる。

テキストドキュメント分類法

テキストドキュメントの分類法を考える。

まず、よい性能を発揮するには、各クラスにおいて数百〜数千の訓練データが必要である。

以下では、訓練データの量で場合分けして分類法を説明する。

訓練データがない場合

以下のような手書きのルールを用いる。

IF (wheat OR grain) AND NOT (whole OR bread) THEN
c = grain

実際はこれよりもっと大きいルールセットとなる。

注意深くルールを作ればかなり正確に分類できるが、そのようなものは基本的にルールセットが膨大であり、作成に時間がかかる上、メンテナンスも大変である。

訓練データが少しだけある場合

より多くのラベルが付いたデータをできるだけ速く得る方法を考える。

例えば、これまで人間がメールを目的により分類していたものを参考にする、など。

訓練データが十分にある場合

これまで説明した分類法がどれでも使える。

訓練データが大量にある場合

どの分類法を使っても、性能にはほとんど差が出ない。

トレーニングや実行時間の効率のスケーラビリティを基に分類法を決めるとよい。

重み学習

訓練データを用いてタームの重みを学習し、それをクエリとドキュメントとの適合性判断に用いる。これをランキング学習という。

以下、重み学習のスコアリング手法を説明する。

ゾーンスコアリング

各ゾーンで重みを分け、クエリのタームがそのゾーンに出現していたら、その重みをスコアに加える。

例として、以下のものを考える。

著者(0.2), タイトル(0.3), 本文(0.5)

重みの和は1になるようにしておく。

クエリのタームがタイトルと本文に出現していたとすると、スコアは以下のように求められる。

0.3 + 0.5 = 0.8

  • メリット

シンプルである

  • デメリット

コストがかかる

実数値でのスコアリング

簡単な例として2次元で考える。2つの要素は以下のように定める。

  • クエリとドキュメントのコサイン類似度
  • ドキュメントにおけるクエリの近接度

すると、以下のような結果が得られたとする。

下式のa, b, cを訓練データで重み学習する。

Score(d, q) = Score(α, ω) = aα + bω + c

そしてある閾値θを定め、Score(d, q) > θ なら適合、そうでなければ不適合とする。

コサイン類似度、クエリの近接度以外の要素の例としては、PageRank、ドキュメントの新しさや長さなどが挙げられる。

このような機械学習は、適合度を実数値で表現する順序回帰問題である。

ランキングにおいて重要なのは、あるドキュメントが一般的に適合しているかという情報ではなく、他のドキュメントと比較して相対的にどちらがよりよいかという情報である。

よって、情報検索におけるランキングにおいて、順序回帰が問題となるのである。

現在では、機械学習は、線形問題にはかなり強いが、非線形問題にはあまり強くないと言われている。