高卒でもわかる機械学習 (1) 識別関数の前知識

教師あり学習

大量のメールがあって、それぞれ人間の目でSPAMかどうかが判定済みであるとします。
それらのメールの何となくSPAMっぽい2単語「主人」「オオアリクイ」に注目し、各メールにそれらの単語が何回出てくるかを数えてグラフにプロットしたら下記のようになったとします。
(「主人」出現回数をx_1、「オオアリクイ」出現回数をx_2とおきます。)

SPAMグラフ

何だか、グラフ中に直線を引けばSPAMとそうでないメールを分けられそうだと思いませんか。
そしてその直線を基準にすれば、未判定のメールがSPAMなのかどうかも判断できそうな気がしませんか。
これが識別関数による教師あり学習の基本です。

教師あり学習では、教師データと呼ばれるデータをたくさん読み込ませて機械に学習させます。
教師データというのは「パラメータと正解ラベルの組」です。今回の例でいくとパラメータとは「主人」「オオアリクイ」という単語の数、正解ラベルとはSPAMかどうかのフラグ(事前に判明しているもの)を指します。
「この単語が○個、こっちの単語が△個あったらSPAMだよ」ということを教えてくれる教師というわけです。

識別関数

SPAMとそうでないメールを分ける直線の式を、3つの定数 w_0, w_1, w_2 を使って
w_0 + w_1 x_1 + w_2 x_2 = 0
とおきます。
移項して、中学で学ぶような「傾きと切片」の式に直すと
x_2 = - \frac{w_1}{w_2} x_1 - \frac{w_0}{w_2}
となりますね。
w_0, w_1, w_2 が何の値なのかはさておき、それら3つが決まれば直線の傾きや位置が決まるのがわかると思います。
この適切な w_0, w_1, w_2 を機械によって求める作業がここでの「学習」です。
(実際に求める方法は次回解説します。)

SPAMグラフで線の模索

この直線で分割された片方のエリアでは
w_0 + w_1 x_1 + w_2 x_2 > 0
となり、もう一方のエリアでは
w_0 + w_1 x_1 + w_2 x_2 < 0
となります。
これは x_1 または x_2 について不等式を解いてみるとわかると思います。

SPAMグラフと関数

w_0, w_1, w_2 の値を調整し(つまりグラフの直線を動かし)、教師データ中の全てのSPAMが w_0 + w_1 x_1 + w_2 x_2 > 0 のエリアに、全ての非SPAMが w_0 + w_1 x_1 + w_2 x_2 < 0 のエリアに入るようになれば学習完了です。
その後、 w_0 + w_1 x_1 + w_2 x_2x_1x_2 に、新しい(SPAMかどうかが不明な)メールに含まれる「主人」「オオアリクイ」の単語数を代入すると、その結果が0より大きいか小さいか(グラフで言えば、直線をはさんだどちらのエリアにプロットされるか)でSPAM識別ができるということになります。

SPAM判定

この w_0 + w_1 x_1 + w_2 x_2 がここでの識別関数です。

ベクトルで表現する

ここでベクトルの概念を導入します。1

一般に、ベクトル \bm{a} = \left(     \begin{array}{c}       a_1 \\       a_2 \\       \vdots \\       a_n     \end{array}   \right) とベクトル \bm{b} = \left(     \begin{array}{c}       b_1 \\       b_2 \\       \vdots \\       b_n     \end{array}   \right) の内積は、下記のように定義されます。

    \[\bm{a} \cdot \bm{b} = a_1 b_1 + a_2 b_2 + \cdots + a_n b_n\]

なので、 \bm{w} = \left(     \begin{array}{c}       w_0 \\       w_1 \\       w_2     \end{array}   \right) , \bm{x} = \left(     \begin{array}{c}       1 \\       x_1 \\       x_2     \end{array}   \right) とおくと、w_0 + w_1 x_1 + w_2 x_2  = 0 は、

    \[\bm{w} \cdot \bm{x} = 0\]

というとてもシンプルな形で表現することができます。2

以降、内積の記号を省略してこれを

    \[\bm{w} \bm{x} = 0\]

と記述することにします。

n次元の場合を考える

ここまでは、メール中の2単語に注目した場合を考えました。
2次元なのでグラフは平面上に描くことができ、それを分割するのは直線でした。
しかし実際にはたった2単語でSPAMかどうかを判定するのは難しいです。

3単語の場合はどうでしょう?
グラフで表すと、3次元なので立体空間になります。
立体空間を2つに分けるのは、線ではなく面になりますね。
この面が平面である場合、式はこのように表現できます。
w_0 + w_1 x_1 + w_2 x_2 + w_3 x_3 = 0
w_3x_3 が増えましたが、これもベクトルで下記のように表現できます。3
\bm{w} \bm{x} = 0 \mbox{ where } \bm{w} = \left(     \begin{array}{c}       w_0 \\       w_1 \\       w_2 \\       w_3     \end{array}   \right) , \bm{x} = \left(     \begin{array}{c}       1 \\       x_1 \\       x_2 \\       x_3     \end{array}   \right)

では4単語の場合はどうでしょう?
4次元になるとグラフで表現するのが非常に難しくなります。
しかし実はあまり難しく考えなくていいのです。
3次元までと同じように、w_4x_4 を増やした下記の式で分割することを考えます。
w_0 + w_1 x_1 + w_2 x_2 + w_3 x_3 + w_4 x_4 = 0
これもベクトルの次元数が変わるだけで、やはり下記のように表現できます。
\bm{w} \bm{x} = 0 \mbox{ where } \bm{w} = \left(     \begin{array}{c}       w_0 \\       w_1 \\       w_2 \\       w_3 \\       w_4     \end{array}   \right) , \bm{x} = \left(     \begin{array}{c}       1 \\       x_1 \\       x_2 \\       x_3 \\       x_4     \end{array}   \right)

3次元空間に生きる我々は、4次元以上のグラフをイメージすることができません。
しかしそれでいいのです。
2次元や3次元と同じように、上記のような数式で表すことさえできれば、計算はできます。
要は、数式に値を代入した結果が0より大きいか小さいかがわかればいいのです。
これは5次元でも1000000次元でも同じです。

線形分離可能とは

このように、n次元空間上にある点の集合を
\bm{w} \bm{x} = 0 \mbox{ where } \bm{w} = \left(     \begin{array}{c}       w_0 \\       w_1 \\       w_2 \\       \vdots \\       w_n     \end{array}   \right) , \bm{x} = \left(     \begin{array}{c}       1 \\       x_1 \\       x_2 \\       \vdots \\       x_n     \end{array}   \right)
で分割できることを、線形分離可能と言います。

再三になりますが、2次元空間を分割するのは直線です。3次元空間だと平面。
4次元以上だと空間そのものがイメージできないのですが、その空間も同じように \bm{w} \bm{x} = 0 で表される「何か」で分割できると考えることができます。
2次元空間における直線、3次元空間における平面、4次元以上の空間のその「何か」をまとめて、超平面と呼びます。
線形分離可能とは、n次元空間上の点の集合を超平面で分割できること、ということができます。
2次元の場合と同じく、分割された片方のエリアは \bm{w} \bm{x} > 0 となり、もう一方は \bm{w} \bm{x} < 0 となります。

線形分離不可能な問題もあります。
例えば2次元の場合、グラフにプロットした結果、境界線が曲がっていたり、点が混ざっていたりすると直線で分割できませんね。

線形分離不可能な例

この問題を解決する手法の1つは次の次くらいの回で説明します。
まずは、線形分離可能な問題から考えましょう。

思いのほか長くなった

次回は、実際に w_0, w_1, \dots の値を求めていく方法を書きます。
キーワードは単純パーセプトロンと勾配降下法です。


  1. ベクトルを \vec{a} のような矢印をつけた記号で表す方法がありますが、この記事では太字で \bm{a} のように表現します。以降もその手法を踏襲しますが、時々太字にするのを忘れるかも知れません…その場合はご容赦ください。 
  2. \bm{w} \bm{x} + b としている資料も多いです。その表現は \bm{w} = \left( \begin{array}{c}   w_1 \\   w_2 \end{array} \right), \bm{x} = \left( \begin{array}{c}   x_1 \\   x_2 \end{array} \right) とし、 w_0 の代わりに b を使っているだけで、意味するところは同じです。そちらの方がわかりやすい人もいるかも知れませんね。
    \bm{w} \bm{x} + b = \bm{w} \bm{x} + w_0 = \left( \begin{array}{c}   w_1 \\   w_2 \end{array} \right) \cdot \left( \begin{array}{c}   x_1 \\   x_2 \end{array} \right) + w_0 = w_0 + w_1 x_1 + w_2 x_2
    また、 \bm{w} \bm{x} の部分を \bm{w}^\mathrm{T} \bm{x} のように記載している資料もあります。これは、 \bm{w} および \bm{x} を単に値の集まりとしてのベクトルではなく列ベクトルとして扱っている(つまり行列の積として記述している)だけで、やはり意味するところは同じです。\bm{w} の右上に \mathrm{T} がありますが、これは「\bm{w}\mathrm{T}乗」ではなく、「\bm{w}の転置行列」を表します。
    \bm{w}^\mathrm{T} \bm{x} =  \left( \begin{array}{c}   w_1 \\   w_2 \end{array} \right)^\mathrm{T} \left( \begin{array}{c}   x_1 \\   x_2 \end{array} \right) = (w_1, w_2) \left( \begin{array}{c}   x_1 \\   x_2 \end{array} \right) = w_1 x_1 + w_2 x_2 
  3. \mbox{ where }」は「ただし」とでも読み替えてください。 
Pocket

Comments

comments