"機械学習","信号解析","ディープラーニング"の勉強

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

"機械学習","信号解析","ディープラーニング"の勉強

"機械学習","信号解析","ディープラーニング"について、それぞれ勉強しながらブログにまとめていきます。テーマは気分によってバラバラかもしれません。

フィッシャーの線形判別

人工知能 人工知能-機械学習

フィッシャーの線形判別は、データを分類する際に統計学の分野で古くから使われている手法です。「判別」という言葉が付いていますが、事実上これはデータを分類するための都合の良い線形変換を見つける手法だと言えます。フィッシャーの線形判別は主成分分析などと同じように、古くから使われている有用な手法というだけでなく、線形代数や統計の基礎的な復習にもなるので絶好のテーマです。是非マスターしてしまいましょう。

 

 

 直感的な例

f:id:s0sem0y:20160807041535p:plain

この画像ではデータは二次元で、赤と青の2クラスがあるという状況です(参照BRML, PRMLではないです)。このデータを一次元の直線上に射影した場合に、直線上のどの位置にデータ点が来るのかが示されています。さて、(a)と(b)どちらが識別に有利な一次元データを獲得していると言えるでしょうか?、直感的には(a)だと感じるはずです。一次元のデータ上で赤と青が上手く分かれているように見えますね。

さてこのような直線は如何にして獲得されるのでしょうか。このような都合の良い射影先の直線(あるいは平面、あるいはそれより高次元の部分空間)を見つける1つの指針がフィッシャーの線形判別だというわけです。

問題設定

問題設定として、2クラスのD次元データを対象にしましょう。

D次元のデータを適当な線形変換によって一次元(直線上)に圧縮してしまい、その直線上でデータがどちらのクラスかを判別しやすくしたいという問題設定です。

数式で表すと、

 

y=w^Tx

 

で、yは圧縮された一次元データ、xはD次元ベクトル、wが線形変換に相当します(この場合は一次元のデータを取り出したいため、wはD次元ベクトルです。もしも二次元データを取り出したければ、W=[w_1,w_2]のように行列を準備すればいいでしょう)。yの値を見てデータが上手く分類できるようにwを決定したいということです。

線形変換w決定への戦略1

先ほどの画像をもう一度見てみましょう。

この画像が上手く判別できていると言える原因を探ってみます。

f:id:s0sem0y:20160807041535p:plain

 

まず青と赤の点が、射影された先で分かれていてほしいというのは当たり前の要求です。wにこれを要請する方法は以下のとおりです。

まず、データ点の青の点をC_1(クラス1)、赤の点をC_2(クラス2)だとしましょう。クラス1のデータ点の平均的な位置m_1と、クラス2の平均的な位置m_2は以下の式となりますね。(N_kはクラスC_kのデータ点の数とします)

 

m_1=\frac{1}{N_1}\sum_{n∈C_1}x_n

 

m_2=\frac{1}{N_2}\sum_{n∈C_2}x_n

 

このm_1,m_2がそれぞれのクラスの代表点だと考えて、これらが変換wを受けた後になるべく離れているということを要請すればいいのです。すなわち

 

w^Tm_1-w^Tm_2=w^T(m_1-m_2)

 

が最大になるようにwを決定するということです。ただし、これを最大にするためにwベクトル自体をやけに大きくしても意味がありません(なぜなら今、分離に有利な直線の傾きを決めようとしているからです。wの方向にのみ興味があるのです)。ですから、|w|^2=1という制約を入れておく必要があります。

 

しかし実はこの要求だけでは分離は上手くいきません。もう一度画像を見てみましょう。

f:id:s0sem0y:20160807041535p:plain

 

例え青の点が赤の方に混ざりこんでいようが、一方で赤の点からかなり離れている青の点がたくさんあれば、結局平均的には離れていると見なせてしまうからです。結局射影先での青の点の平均的な位置と、赤の点の平均的な位置を離すだけでは、個々の点の混ざり具合を完全に抑えることはできないのです。これではまだ上手いwを見つけたとは言えません。

 

線形変換w決定への戦略2

もう少しwに対して、それぞれのクラスに関する制約を入れておいた方が良いでしょう。先ほど残された課題は、平均的な位置としては離れていても、個々の点が混ざり合っているということでした。すなわち言い方を変えると、青の点のばらつきが大きい、赤の点のばらつきが大きい、そのために(平均的には離れていても)混ざり合ってしまうことがあるということです。

ですから、次にwに課する要請は、同じクラスのデータ点は、射影された先で近くにいてほしいというものです。つまり同じクラスのデータ点の分散を小さくしておきたいということです。

クラスC_1のデータ点の射影先での分散s^{2}_{1}

 
s^{2}_{1}=\sum_{n∈C_1}(w^Tx_n-w^Tm_1)^2

 

同様にクラスC_2に関しては

 

s^{2}_{2}=\sum_{n∈C_2}(w^Tx_n-w^Tm_2)^2

 

 と表されます。

分散は平均からの距離の二乗の和です。これが小さいほどバラつきが少ないと言えますね。

つまり、それぞれのクラス毎の分散が小さければデータは射影先でクラス毎に纏まっているということです。

 

s^2=s^2_1+s^2_2

 

をなるべく小さくすれば良いわけで、これを総クラス内分散と言います。

 

フィッシャーの線形判別の定式化

以上から、上手いwを見つける戦略として

 

1.射影先でのクラス毎の平均を計算し、なるべく離れるようにする。

2.射影先でのクラス毎の分散を計算し、なるべく小さくなるようにする。

 

というものが与えられました。式としては、

 

m_1=\frac{1}{N_1}\sum_{n∈C_1}x_n

 

m_2=\frac{1}{N_2}\sum_{n∈C_2}x_n

 

w^Tm_1-w^Tm_2=w^T(m_1-m_2)  を最大化。

 

s^{2}_{1}=\sum_{n∈C_1}(w^Tx_n-w^Tm_1)^2

  

s^{2}_{2}=\sum_{n∈C_2}(w^Tx_n-w^Tm_2)^2

 

s^2=s^2_1+s^2_2  を最小化。

 

の2つの要請がありました。 この2つを両方考慮した評価関数を考えましょう。指針としては、平均に関することを分子に、分散に関することを分母に持ってくることで、平均に関しての最大化と分散に関しての最小化を、評価関数J(w)=\frac{平均に関すること}{分散に関すること}の最大化という1つの問題に置き換えられます。

1.平均に関して

まずは分子に関する式を二次形式で表現しておくことで、分散と対等に扱うことができます。

 

w^Tm_1-w^Tm_2=w^T(m_1-m_2)

 

を二次形式(ベクトルや行列に関する二乗のようなもの)で表現すると

 

w^T(m_1-m_2)(m_1-m_2)^Tw

 

となります。これは、それぞれのクラスの平均的な位置の二乗になっているために、クラス間分散と表現されます。特にS_B≡(m_1-m_2)(m_1-m_2)^Tはクラス間共分散行列と定義されます。クラス間共分散行列を使って表現すると

 

w^TS_Bw

 

を最大化するというのが平均に関する要請になります。

 

2.分散に関して

次に分散に関する式ですが、これは元々分散の概念であるため元々二次形式で表現されます。それぞれ

s^{2}_{1}=\sum_{n∈C_1}(w^Tx_n-w^Tm_1)^2

s^{2}_{2}=\sum_{n∈C_2}(w^Tx_n-w^Tm_2)^2でした。

s^2=s^2_1+s^2_2wを外に出して

 

s^2=s^2_1+s^2_2=w^T(\sum_{n∈C_1}(x_n-m_1)^2+\sum_{n∈C_2}(x_n-m_2)^2)w

 

と表せます。ここでS_w≡\sum_{n∈C_1}(x_n-m_1)^2+\sum_{n∈C_2}(x_n-m_2)^2を総クラス内共分散行列と定義して

 

w^TS_ww

 

を最小化するのが分散に関する要請になります。

 

フィッシャーの線形判別の評価関数

以上をまとめて評価関数J(w)

 

J(w)=\frac{w^TS_Bw}{w^TS_ww}

 

と表現することができます。

これの具体的な解き方は、単にwで微分するだけのことなので調べればすぐに出てくるでしょう。大事なのはフィッシャーの線形判別がどのように考えて構成されたかです。

これが分かると以下のような評価関数の変更の意図も分かるかと思います。

 

J(w)=\frac{w^TS_Bw}{w^TS'_ww}

 

S'_w=π_1\sum_{n∈C_1}(x_n-m_1)^2+π_2\sum_{n∈C_2}(x_n-m_2)^2

 

とする方法です。これは射影先でのクラス毎の散らばり具合について、どちらのクラスにより散らばってほしくないかを表現する係数πになっています。

 

解を求める

wを実際に求める方法を書いておきます。

評価関数J(w)wで微分して0となればいいので、条件は

 

\frac{\partial}{\partial w} \frac{w^TS_Bw}{w^TS_ww}=\frac{2}{(w^TS_ww)^2}[(w^TS_ww)S_Bw-(w^TS_Bw)S_ww]

 

が0となればよく、結局、満たしておく条件は

 

(w^TS_Bw)S_ww=(w^TS_ww)S_Bw

 

となります。最初に述べた通り、今興味があるのはwの方向だけで、大きさは興味がありません。二次形式はスカラーとなっており、大きさにしか寄与せず、wの方向を決めるのはベクトルだけですから(w^TS_Bw)(w^TS_ww)は無視しても構いません。

すなわち等式を以下のように評価してwの方向のみを考えればいいのです。

 

S_ww∝S_Bw

 

両辺に{S_w}^{-1}を左から掛けて、更にS_Bw(m_1-m_2)に比例することを用いて最終的には以下の式になります。

 

w∝{S_w}^{-1}S_Bw∝{S_w}^{-1}(m_1-m_2)

 

wの具体的な大きさを求めることも当然できますが、方向だけに興味があり|w|^2=1の制約で問題を解きたいため、上記を満たすwを決めてから単位ベクトルにしてしまえばいいでしょう。

結局は手元にあるD次元データのクラス毎の平均を求めm_1-m_2を求め、総クラス内共分散S_wを計算して、その逆行列を求めればwは決まるということです。

 

最後に

今回はフィッシャーの線形判別を考えだす過程と共に解説しました。

これは実際には特徴抽出の手法であって、直接識別はできません。一次元に圧縮した場合には、そのスカラー値yに適当な閾値を設けてクラス分類したり、あるいはそれぞれのデータをガウス分布で表現して(せっかく平均と分散考えたわけですし)データ点の尤度を計算する方法も考えられるでしょう。

この手法の有用性は、実は最初の画像

f:id:s0sem0y:20160807041535p:plain

で示されており、(a)はフィッシャーの線形判別で(b)は主成分分析になっています。

主成分分析はデータのラベルを一切用いない教師なし学習ですから、不利と言えば不利なのですが、分類が目的の際にはフィッシャーの線形判別が威力を発揮するのを理解してもらえたでしょうか。

 

今回はこの辺で。