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

テキストマイニングのための機械学習超入門 二夜目 パーセプトロン

テキストマイニング 機械学習 自然言語処理

 一夜目はパターン認識と機械学習の概要を学びました。今夜は、識別部で用いられる機械学習の基本的な線形識別器である「パーセプトロン」を具体的に学びたいと思います。「線形識別器?パーセプトロン?何それ?」字面は厳しいですが、手を動かしてみると意外と簡単に理解できます。今夜からは数式をバリバリ使っていきますし、手を動かしていただきます。「必ず」手元にペンと紙を用意してください。そうは言ってもパーセプトロンが一体何なのか、機械学習の中でどのような位置づけなのかがわからないと混乱するかもしれません。パーセプトロンの説明へ入る前に、機械学習の3つのアプローチをご紹介します。


機械学習の3つのアプローチ - 識別関数、識別モデル、生成モデル
 機械学習は大きく分けて識別関数、識別モデル、生成モデルという3つのアプローチがあります。

  • 識別関数 := 入力データを見て、特定のクラスに属するよう識別(代表的な手法:パーセプトロンニューラルネットワークサポートベクターマシン
  • 識別モデル := 入力データからクラス事後確率をモデル化して識別(代表的な手法:CRF)
  • 生成モデル := 入力データがどのような分布で生成されたものかをモデル化して識別(代表的な手法:ナイーブベイズ)

 前夜学んだ最近傍決定則はデータから直接属するクラスを見つけたので、識別関数です。識別モデルと生成モデルが分かりにくいですね。ここでは識別関数と生成モデルの違いを、昨夜の例を用いて説明します。特徴空間がX=(サッカー、野球、政治、選挙)であり、Aさんが100単語発したある時の特徴ベクトルがX_A(50, 30, 15, 5)だとします。この場合、識別関数では、単に「サッカーという単語が出現した回数は50回である」とだけ考えます。対して、生成モデルでは「Aさんは特徴空間Xにおいて、サッカーという単語が出現したのは100回中50回なので、サッカーの出現確率は0.5だ」というように確率分布まで考えます。前者は、Aさんがさらに100単語発したときサッカーが何回出現するかを全く考慮していません。後者は、Aさんがさらに100単語発するなら、サッカーは50回程度出現するだろう」と考えます。「生成モデル」という名が表すように、「どのような確率分布でデータが生成されたのか?」というモデルを立てて識別するため、単に実際観測されたデータだけではなく、データが観測された背景まで考慮するので、データに欠損がある場合など、識別に有利に働く場合があります。ただし、非常に理論が複雑だったり、データに対し確率論の適用が必要になったりと、良いこと尽くめではありません。また、生成モデルが識別関数より一般的に精度が高いというわけでもありません。現実問題として、実務で用いられる機械学習の大半が識別関数です*1
 最近は異なるアプローチを混ぜて識別する先進的な手法を取ることもよくありますし、そこまで厳密に区別する必要はありません。ただ、アプローチが違うということは、識別の基となっている考え方そのものが違うということだけは念頭に置いてください*2


●線形識別器
 識別するとはどういうことでしょうか。以下、簡単のため、2クラスの識別問題について考えていきます。昨夜の最近傍決定則では、入力データは最も近いプロトタイプのクラスに属するとして識別を行いました。図で考えてみましょう。図1をご覧ください。


図1

青クラスを代表する青プロトタイプと赤クラスを代表する赤プロトタイプ、両プロトタイプから等距離に引かれた緑の直線を描きました。この緑の直線は各プロトタイプから等距離にあるため、この線より青プロトタイプに近ければ青クラス、赤プロトタイプに近ければ赤クラスだと考えること出来ます。
 このように、入力データを各クラスに識別するような直線を超平面(あるいは決定境界や識別面)といいます*3。つまり、識別する=超平面を求めることです。そして、超平面を求めるとは、正しいプロトタイプを適切に設定するということでもあります。なぜなら、ここでいう超平面とは各プロトタイプから等距離に位置するものだからです*4。また、このように超平面で完全にクラスを分離出来る場合を「線形分離可能である」といいます。図2のように直線で分離出来ないような場合を非線形分離といいます。


図2

 線形の超平面を求めるアルゴリズムの総称を線形識別器(あるいは分類器)といいます。どのようにして線形識別器は超平面を求めるのでしょうか?次からは線形識別器の一つであるパーセプトロンの中身を学びましょう。


パーセプトロンの概要
 パーセプトロンは識別関数に属する線形識別器の一種です。基本的な概念はとても簡単で、ニューラルネットワークサポートベクターマシン(以下SVM)など数ある識別関数の基礎中の基礎でもあり、非常に重要です。基礎と初歩は全く異なります。パーセプトロンが必ずしも他の手法より精度が低いというわけではありません。様々な拡張性に富み、最近必須と言っても良いオンライン学習として活用することが出来ます*5
 まずはパーセプトロンのイメージ大雑把に掴んでみましょう。図3をご覧ください(図2では青丸が青プロトタイプでしたが、今度は青丸=青学習データだと考えてください。赤丸も同様)。


図3

各クラスを分離するような超平面(緑の点線)を適当に作ります。適当なので、図にあるように誤識別してしまいます。誤識別してしまった場合は、正しく識別できるように超平面を正しい方向に少しずつ修正します(図3の黒矢印の方向に)。それを何度も繰り返して、最終的に全データを正しく識別出来る黄点線のような超平面を求めます。これがパーセプトロンの処理の流れです。誤識別したとき、正しい方向に修正することを「学習する」といいます。
 パーセプトロンの処理は、まとめると1.最初の超平面は適当に決める、2.識別関数が誤識別したときに学習する、3.2を何度も繰り返す、の3点です。特に2の学習部分が肝心です。


●識別関数
 先ほど「誤識別したときに学習を行う」と説明しました。なので、学習する前に識別をしなければなりません。識別とは、対象の学習データに対して、最も近いプロトタイプがどれかを判定することです。ではどうやって識別すれば良いのでしょうか。識別を実現する関数、その名も識別関数を作りましょう。
 学習データxからプロトタイプpまでの距離を||x-p||と表現します。二次元(横軸位置、縦軸位置)で考えてみましょう。数学的に、二点間の距離とは、二点の座標成分の差の絶対値を意味します。xが(3, 4)、pが(6,2)だった場合、||x-p||は(3-6, 4- 2) = ||(-3, 2)|| = ||(3, 2)||*6となります。これで学習データxとプロトタイプpの距離を表現することが出来ました。
 ですが、プロトタイプは一つではなく、クラスの数だけあります。学習データと複数のプロトタイプの距離を表現するにはどうすればよいでしょうか。二値分類(データを二つのクラスに分類)する場合は二つのプロトタイプ、百のクラスに分類する場合は百のプロトタイプが存在します。そこでプロトタイプをp_i i = 1, 2, ... , nと表現します。p_iはn個あるプロトタイプのうち、i番目のプロトタイプを指します。そしてi番目のiは1からn個まで存在します。プロトタイプが2つならp_1, p_2と表現できます。これを利用し、学習データxと各プロトタイプp_iを||x - p_i||と表現することが出来ます。
 これで学習データと各プロトタイプとの距離を表現することが出来ました…が、やりたかったことは、最も近いプロトタイプがどれかを判定することでしたね。そこで最も近いプロトタイプを arg_i min ||x - p_i||のように表現します。minはminimum(最小)の略で、minの右の項の中で最小のものを選択するという意味です。ここでは最小の距離を取得します。しかし本当に欲しかったのは、最小の距離ではなく、最小の距離のプロトタイプです。argはargument(引数)の略で、指定した引数の値を返すという意味です。ここでは引数にiを指定しているため、argの右項の条件を満たすiを取得します。つまり、「学習データとn個あるプロトタイプとの距離を一つ一つ調べて、その中でも最小の距離になるようなi番目のプロトタイプを取得する」という意味になります。たった一行の数式に沢山の意味が詰まってますね。
 対象の学習データに対して、最も近いプロトタイプがどれかを表現することが出来、ようやく識別関数を作る準備が整いました。識別関数を作るのにも色々な種類がありますが、ここでは一番シンプルな最小二乗法を用います*7。最小二乗法は、その名のとおり、距離を二乗して、その中でも学習データとの距離が最小になるプロトタイプを選択します。距離を||x - p||と表現したので、その二乗は||x - p||^2です。これを展開すると||x||^2 - 2p_ix + ||p_i||^2となります*8。この距離の式を最小にするようなプロトタイプを求めることが、識別関数のそもそもの目的でした。ということはこの式に全プロトタイプを当てはめて、距離が最小になるものを選択するわけですが、どのプロトタイプに対しても、||x||^2の部分は全く変更がありません。対象とする学習データxは固定で、プロトタイプだけ入れ替えているからです。つまり、 arg_i min ||x||^2 - 2p_ix + ||p_i||^2 arg_i min - 2p_ix + ||p_i||^2で選出されるプロトタイプは同じ結果になります。同じ結果になるなら、簡単のため、  arg_i min - 2p_ix + ||p_i||^2を利用しましょう。無駄な計算を省略することで、実際解析する際の高速化が望めます。さらにいうと、  - 2p_ix + ||p_i||^2という式の全ての項を定数倍しても結果は変わりません。後々計算しやすいよう、全体に\frac{1}{2}を掛けて -p_ix + \frac{1}{2} ||p_i||^2としておきます*9。そしてさらに計算の都合上、全体に-1を掛けて、符号を逆転させます。そうすることによって、最小化問題を最大化問題に変更することが出来ます*10(このへんの操作は、計算の都合上の話であり、パーセプトロンのロジックの本質的なことではありませんが、こうやると後々実際計算するとき非常に楽になるので、ちょっと頑張って読んでください)。これを識別関数  g(x) := p_ix - \frac{1}{2} ||p_i||^2であると定義します。そしてこの識別関数の値を最大にするプロトタイプが、学習データに最も近いプロトタイプです。
 随分時間がかかりましたが、ようやく識別関数を作ることが出来ました。いよいよ学習部分に入ります。
 

パーセプトロンの学習規則
 学習するとは、識別関数が誤識別した際、超平面を正しく修正することです。超平面の修正方法は二つあります。一つ目は図3のように超平面を回転させること、二つ目は図4のように超平面を移動させることです。


図4

適当に回転・移動させるだけではなく、正しい回転量・移動量を求める必要もあります。これを実現するにはどうすればいいでしょうか。
 超平面は各プロトタイプから等距離に位置すると説明しました。ということは、超平面の位置や向きはプロトタイプに依存しており、プロトタイプを上手く調整すると、正しい超平面を得られそうです。また、学習は誤識別したときに行います。誤識別するということは、識別関数が対象としている学習データとこれまでのプロトタイプからでは、最も近いプロトタイプがどれかを誤って判定してしまうということです。以上のことから、誤識別した学習データを利用してプロトタイプを移動させれば良さそうですね。直感的にも、図3や図4のように、誤識別した学習データを正しいクラスに識別できるよう超平面を引き直せばよいわけですから、学習には今の超平面(を形成するプロトタイプ)と誤識別した学習データを何らかの形で組みあわせる必要があるとわかります。
 誤識別した学習データに応じてどの程度現在の超平面を回転・移動させるかを求めるため、「重み」という概念を利用します。誤識別した学習データに重みを掛け、その値の分だけ超平面を回転・移動させます。重みベクトルwをプロトタイプpを用いて、識別関数  g(x) := p_ix - \frac{1}{2} ||p_i||^2から次のように表現します。

w_{ij} = p_{ij}
w_{i0} = - \frac{1}{2}||p||^2

p_{ij}のiとはプロトタイプが何番目かというインデックス、jはそのプロトタイプの要素j番目のインデックスです。二次元の場合、プロトタイプは縦軸と横軸の位置情報を持つため、p = (横軸の位置、縦軸の位置)と二つの変数を持っています。この時、例えばp_{32}は、3番目のプロトタイプの2番目の要素(縦軸の位置情報)であるという意味です。つまり、重みwはプロトタイプとバイアスw_{i0}という情報をひっくるめた概念です。
 さて、超平面における重みと何やら突然出てきた感のあるバイアス項の意味を二次元平面上で考えてみましょう。二次元では、超平面とは平面を横切る直線になります。例えばy = αx + β (α > 0)という式は、右上がりの直線が平面を二分割します。この式のαが重み、 βという切片に当たるのがバイアスです。ここでαを1、βを0として直線を描くと、原点を通り、45度で平面を二分割する直線が描けますね。αを2にしてみると、傾きが急になり、半時計回りに直線が回転しますね。αを変更すると直線が回転する、そして「α=重み」かつ「直線=超平面」なので、「重みを変更する=超平面を回転させる」という意味になります。また、βを0から1にすると、直線が上に移動しますね。ここで、「β=バイアス」なので、「バイアスを変更する=超平面を移動させる」という意味になります。これで重みとバイアス項が超平面に対してどのような働きをするのかがわかりました。
 超平面を正しく引くには、重みとバイアスを変更する必要があることがわかりました。ではどのように変更させればよいでしょうか。学習の具体的な更新式は次のようになります。

w' = w + ρ * x * L

ここでρは学習係数といい、重みに対して一回の学習がどの程度影響をするかを表します。あまりに小さすぎると収束まで時間がかかりますし、あまりに大きすぎるとぴったりの重みに収束しないケースが出てきます。ρの値の決め方は色々あり、また、ρを可変にして、学習回数が増加する度ρを小さくするアルゴリズムなどもあります。実用上、このρの値によって収束速度がかなりかわってくるため、徐々にρを小さくするアルゴリズムを採用するのが良いでしょう。Lは分類するクラスのラベルです。二値分類の場合、クラスのラベルを+1, -1として分類することが多く、こうすると計算上便利です。図3のように青赤クラス分類をする場合、青クラスを-1、赤クラスを+1とラベリングしておけば、青クラスの学習データを赤クラスだと誤識別したとき、超平面を半時計回りに回転させるように更新式に応じて重みを修正します。
 更新式、とてもシンプルですね。つまり、更新とは、元の重みに対し、学習係数と誤識別した対象の学習データ掛け合わせたものを引くというだけです。そうして新しく得た重みで再度識別関数の用い、識別を行います。これを全学習データ分繰り返し、誤識別が一つもなくなったら学習終了です。
 ここで、「全学習データに対して誤識別が一つもなければ学習終了?ということは誤識別してしまうような、線形分離不可能な場合はいつまでも収束しないの?」という疑問が生まれます。実際その通りで、収束しません。ではどうするか?あるデータに対して誤識別する上限回数は決まっているという、パーセプトロン収束定理というものがあります。この定理に基づき、上限回数を超えて収束しない場合はそこで学習を打ち切るなどします。ただ、実務上、「単に収束までの時間が掛かりすぎているのか、収束しないのか」の判断を分析前に知ることはまず不可能なため、事前に何回試行すればそこで打ち切りとするのが殆どです。
 これでパーセプトロンの説明は終わりです。では、実践に入りましょう。


●人力パーセプトロン
 実際手を動かして、パーセプトロンの挙動を確認しましょう。さーて、ここからが凄く面白いところなので、必ずペンと紙を用意して読んでください。
 例題:学習データがx = (5, 1, 4, 2)の4つで、C1 = (5, 4)、c2 = (2, 1)というクラスに属するときの超平面を求めよ。
要するに、一次元のデータ1, 2, 4, 5があり、1, 2と4, 5を分割するような超平面を求めればいいわけですね。直感的に、超平面は3を通りそうですね。
まず、各データのバイアス項を1と適当に決め*11ます。すると先程の学習データは次のように表現出来ます。
x1 = (1, 5)
x2 = (1, 2)
x3 = (1, 4)
x4 = (1, 1)
次に重みの初期値を適当に決めます。ここではw0 = 0, w1 = 0とします。また、識別関数に学習データを放り込んだ結果が≧0ならC1に、<0ならC2に識別するとします。本当なら、どの学習データを識別関数に放り込んで学習するかはランダムに決めるのですが、手作業でランダム選択は難しいので、便宜上1〜4まで順番に処理していきたいと思います。え、そんなことで良いのかって?それはやってみれば解ります:D。学習係数は1とこれも適当に決めておきます。え、これもそんな適当に決めていいのかって?それもやってみると解ります、楽しみにして下さい:D。二値分類なので、C1の方のラベルを+1、C2を-1にしておきましょう(逆でも良い)。
さぁ、下準備は終わりました。では実際学習していきましょう。まずx1を識別関数g(x)に掛けてみます。x1 = (1, 5)でw = (w0, w1) = (0, 0)なので、g(x) = 1 * 0 + 5 * 0 = 0となり、正しくC1に識別されました。ではC2に取りかかりましょう。x2 = (1, 2)、w = (0, 0)なので、g(x) = (1 * 0 + 2 * 0) = 0となり、x2はC2の筈なのにC1に識別されてしまいました。誤識別が発生したので学習します。学習データx2と現在の重みwを更新式"w' = w + ρ * x * L"に放り込むと、
w0' = 0 + 1 * 1 * -1 = -1
w1' = 0 + 1 * 2 * -1 = -2
となり、新しい重みがw' = (-1, -2)になりました。この新しい重みで次の学習データを識別します。x3 = (1, 4)、w =(-1, -2)なので、g(x) =1 * -1 + 4 * -2 = -9となり、x3はC1の筈なのにC2であると誤識別されました。再度学習しましょう。
w0' = -1 + 1 * 1 * 1 = 0
w1' = -2 + 1 * 4 * 1 = 2
で。新しい重みはw' = (0, 2)となりました。続けましょう。x4 = (1, 1)、w = (0, 2)→g(x) = 1 * 0 + 1 * 2 = 2なので誤識別。
w0' = 0 + 1 * 1 * -1 = -1
w1' = 2 + 1 * 1 * -1 = 1
また最初の学習データに戻って同じ事を誤識別が発生しないようになるまで繰り返します。x1 =(1, 5)、w = (-1, 1)→g(x) = 1 * -1 + 5 * 1 = 4。正しく識別されました。x2 = (1, 2)、w = (-1, 1)なので、g(x) = (1 * -1 + 2 * 1) = 1なので再度学習。
w0' = -1 + 1 * 1 * -1 = -2
w1' = 1 + 1 * 1 * -1 = 0
x3 = (1, 4)、w =(-2, 0)なので、g(x) =1 * -2 + 4 * 0 = -2なので再度学習。
w0' = -2 + 1 * 1 * 1 = -1
w1' = 0 + 1 * 4 * 1 = 4
x4 = (1, 1)、w = (-1, 4)→g(x) = 1 * -1 + 1 * 4 = 3なので再度学習。
w0' = -1 + 1 * 1 * -1 = -2
w1' = 4 + 1 * 1 * -1 = 3



どうしよう、大変辛くなってきた… :(




気を取り直して頑張りましょう :)
またまた最初の学習データに戻って同じ事を誤識別が発生しないようになるまで繰り返します。x1 =(1, 5)、w = (-2, 3)→g(x) = 1 * -2 + 5 * 3 = 13。正しく識別されました。x2 = (1, 2)、w = (-2, 3)なので、g(x) = (1 * -2 + 2 * 3) = 4なので再度学習。
w0' = -2 + 1 * 1 * -1 = -3
w1' = 3 + 1 * 2 * -1 = 1
x3 = (1, 4)、w =(-3, 1)なので、g(x) =1 * -3 + 4 * 1 = 1なので正しく識別されました。
x4 = (1, 1)、w = (-3, 1)→g(x) = 1 * -3 + 1 * 1 = -2なので正しく識別されました。


またまたまた最初の学習データに戻って同じ事を誤識別が発生しないようになるまで繰り返します。x1 =(1, 5)、w = (-3, 1)→g(x) = 1 * -3 + 5 * 1 = 2。正しく識別されました。x2 = (1, 2)、w = (-3, 1)なので、g(x) = (1 * -3 + 2 * 1) = -1なので正しく識別されました。
おや、x3, x4は先程この重みで正しく識別されると言う事を確認しましたね。ということで、全データに対して重みw =(-3, 1)は正しい識別を提供するようです。実際紙に描いて確認してみましょう。二次元座標を描いてみて下さい。一次元の学習データが1, 2, 4, 5なので、横軸の数直線に1, 2, 4, 5と描きます。それに超平面(二次元なのでここでは直線)y = x - 3を引きましょう。すると綺麗にデータを二分割する直線になりましたね。やった!成功です!
あー、長かった…。
これで要領は掴めたと思います。次に、学習データの並びを変更してみたり(今は各クラスのデータが交互に出現しましたが、クラス毎に偏って出現するなど)、学習係数を学習データに対して大きく、あるいは小さく設定してみたりしましょう。是非手計算してみて下さい。

 わかったことをまとめましょう。

  1. 学習係数ρが大きすぎると収束しない。かといってρが小さ過ぎると収束まで時間がかかる
  2. 逐次学習であるため、全く同じデータでも、入力順が異なると、異なる超平面を形成する(だから学習データをランダムに選択する必要が有るわけですね)。超平面は一つではない。先程の例だとy = x - 3になったが、例えばy = 1.5x - 2.5でもきちんと分割できる。線を描き込んで確かめて下さい
  3. 1次元でデータ数4個という非常の小規模な学習でも、収束までそれなりの試行回数が必要。実際の分析では高次元大量データを扱うことになるので、反復数はとんでもないことになる。そのため、一回一回の計算をほんの少しでも高速化出来れば、全体的にかなり改善される

 お疲れ様でした。パーセプトロン、理屈は割と簡単でしたね。しかし、実際手を動かして処理を追うことにより、識別器の動きが肌で理解できたのではないかと思います。パーセプトロンは実装も簡単ですので、是非チャレンジしてみてください。


▲追記
パーセプトロンの説明記事を書きます」と言ったらさくさくテキストマイニング勉強会のアイドルtorotoki君がPython実装してくれました。是非御覧下さい。
Pythonパーセプトロンを実装した」 http://eaqule.com/blog/python/perseptron-with-python/

*1:素晴らしい記事なので、是非ご一読頂きたい "機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜" http://d.hatena.ne.jp/echizen_tm/20110114/1295030258

*2:もっと詳しく知りたい方は、パターン認識と機械学習(上)1.5.4に書いてありますのでご参照下さい

*3:超平面と言いつつ、この図では二次元に引かれた直線なので「なんで超『平面』なの?」と疑問に思われるかもしれませんが、一般に特徴空間は高次元であるため、直線の場合も平面の場合も総称して超平面といいます

*4:本当はちょっと違いますが簡単のために…。学習データと超平面との距離をマージンといいます。パーセプトロンにはマージンを最大化するように学習するマージン最大化学習や、パッシブアグレッシブパーセプトロンではある程度の誤識別を許容するソフトマージンという手法などもあり、また、この例で言うと、青クラスのマージンと赤クラスのマージンを非対称に設定する場合もあります。例えば、健康診断で癌の識別をする際、百歩譲って癌でもないのに癌だと診断されても再診断を受けるだけで話は済みますが、癌なのに癌でないと診断されてしまうと取り返しのつかないことになってしまいます。なのでがんではないと判定するマージンを大きく取る、つまり癌ではないと誤識別しにくいようにマージンを設定するということもあります

*5:ぶっちゃけた話をすると、大抵の分類問題はパーセプトロンで何とかなりますし、パーセプトロンわからないと他の識別関数もほぼ全部理解できないと思います。それくらい滅茶苦茶重要です

*6:絶対値とは、数の大きさだけを考えて、符号は考えないことです。例えば|-3| = |3|となります。xの絶対値を表現する記号は|x|、xの距離を表現する記号は||x||となります。混同しないよう注意してください

*7:参照 http://ibisforest.org/index.php?%E6%9C%80%E5%B0%8F2%E4%B9%97%E6%B3%95 ちなみに、最小二乗法はシンプルかつ理論上正規分布最尤推定になっているなどのメリット(?)もありますが、実際使うと、外れ値に弱かったり、データ数の多いクラスに超平面が吸い寄せられるなど癖があってあまりお薦めできません。もうちょっと詳しく知りたい方は、わかりやすいパターン認識9章、あるいはパターン認識と機械学習4.1.3などをご参照下さい

*8:すみません、誤魔化しています。pもxもベクトルなので、本当なら[tex:2p_i]の右肩に転置を意味するtが乗ります。ただ、それを言い出すと簡単な線形代数の知識が必要になるので、また後日ということで…

*9:xで微分するとき、分数が消えて式がスマートになりますね:D

*10:[-xを最小化する = +xを最大化する]です。xに具体的な数値を当てはめて考えてみましょう

*11:0.1でも3でも構いません。よく1が使われます。極端な値でなければ、バイアス項も適宜学習されていくで問題有りません