部分空間法の原理【はじパタ9章後半の解説】

えびかずき

こんにちは、えびかずきです。

今回は部分空間法の原理について説明していきます。

部分空間法とは

部分空間法とは、データの全体のベクトル空間を識別クラスごとの部分空間に分けて、その部分空間への射影の大きさを比較することでクラス分類をする手法です。

例えば、話を単純化してデータ全体が３次元のベクトル空間だとしましょう。

訓練データが下のように2クラスある場合に、赤のテストデータをどちらかにクラス分けしたいとします。

さてこの場合に部分空間法を使うならば、どのようにするでしょうか？

下の図を見てもらえるとわかりやすいと思います。

訓練データ1と2は、それぞれクラス1と2に属しているとして、この条件下でそれぞれの訓練データを使って各クラスの部分空間を作ります。

この部分空間を作るという作業が、機械学習でいう訓練の工程にあたります。

そしてこの状態でテストデータが与えらた時にどうするかというと、各クラスの部分空間への射影をとって、一番大きいクラスへ分類します。

部分空間への射影をとって、それが大きければ大きいほどそのクラスに似ているはずという考え方ですね。

ここで「部分空間」という耳なれないワードが出てきました。

部分空間というのは線形代数に慣れていないと聞き馴染みのない言葉だと思いますが、厳密さを犠牲にしてあえて簡単に言えば、全体の空間の次元以下の部分的な空間のことを言います。

さらに補足すると、部分空間は必ず原点を通ります。

部分空間というと誤解しがちなのですが、決して下のように全体と同じ次元だけど座標の範囲指定が違うだけという理解は間違いですので、お気をつけください。

くどいようですが、部分空間というのは、図1のように原点を通って無限に広がった空間であるということに注意が必要です。

言葉では空間といっていますが、部分空間は図1のように平面でも構いかませんし、極端なことを言えば１次元の直線でも構いません。

あくまでも全体の次元以下の空間を部分空間と言うわけです。

部分空間法の特徴

部分空間法のメリットは、訓練・テスト（推定）ともに計算コストが小さく極めて簡便な分類手法であるということです。

訓練工程では、後で述べる固有値問題を解くだけ。

テスト工程では、各部分空間への射影を取るだけですからね。

さらに言うと、考えているベクトル空間が非常に大きい場合でも、個々のクラスの部分空間を考えれば良いだけなので、計算量は大きくなりにくいという点でも計算コストが小さいと言えます。

一方でデメリットとしては、部分空間に近ければ同じクラスと認識してしまうので、空間的に距離が遠くても関係がないということです。

したがって個々のデータの数値的な大きさが、クラス分類に大きく影響を及ぼすような場合は部分空間法には不向きです。

逆に言えば、個々のデータ数値的な大きさはあまり気にしないというケースで力を発揮する分類手法です。

さてそれはどんなケースでしょうか。

どんなケースで使うか？

たとえば、下のような数字の認識をしたいと言うようなケースで部分空間法は有効です。

これはMNISTデータベースの手書き文字訓練データです。

このデータの構造は28×28ピクセルのグレースケール画像です。

すなわち、それぞれの画像データは784次元のベクトル空間に属するということです。

784次元の空間というのはよほどの天才でない限りに感覚的に理解することは不可能ですが、理論的には上で説明した３次元空間を拡張していった先の空間です。

つまり空間に軸をどんどん追加していって、最終的に784本の軸をとった状態がこの場合に考えるべき全体の空間です。

どうしてこのようなケースで部分空間法が有効かというと、各次元（ここでいう各ピクセル）の数値的な大きさがあまり気にならないクラス分けだからです。

具体的に言えば、他のピクセルとの相対的な量関係が同じなら、同じ数字だと認識できるからです。

例えは、数字の色が薄くなったとしても「3」は「3」だし「6」は「6」ですよね。

部分空間法の原理

ここでは上のような手書き数字の認識を例に、原理を説明していこうと思います。

また、ここで紹介する方法は、はじパタで紹介されているのと同じ、訓練データの相関行列を使用するCLAFIC法について説明していきます。

訓練工程

訓練工程では、データのクラスごとに部分空間をつくる必要があります。

部分空間を作る方法は、主成分分析で主成分を導くやり方に似ています。
（主成分分析の原理は過去記事をください。）

具体的に言うと、CLAFIC法では訓練データの射影の長さの二乗の期待値（和という表現でも良い）が最も大きくなるような基底ベクトルを部分空間の軸に選びます。

これは主成分分析でいう主成分ベクトルと似たような性質を持ったベクトルで、それにみ合った方程式をたてて固有値問題を解くことで得られます。このとき主成分分析と同様に直交する全てのベクトルが同時に得られます。

そうやって得られた規定ベクトルの線型結合によって張られる空間が部分集合になるというわけです。

データ\(\textbf {x}_1\)が、数字の1を表す訓練画像の一つだとすれば、

\(\textbf {x}_{(1)}=\begin{pmatrix} x_1\\x_2\\…\\x_{784}\\\end{pmatrix}\)

(1)はクラス1を表す

と表すことができる。

ここで、部分空間を張る”とある”単位ベクトル（長さが1のベクトル）\(\textbf {u}_{(1)j} (j=1,2,3,…,d)\)の組を考える。（これが後に固有値問題の解として部分集合の次元の個数(d)だけ得られ基底ベクトルとなる）

この時、訓練データ\(\textbf {x}_{(1)}\)を部分空間へ正射影した長さ（各単位ベクトルへ射影した時の長さの和）の期待値は、

\(\displaystyle E\left[\sum_{j=1}^d(\textbf {x}_{(1)}^T\textbf {u}_{(1)j)})^2\right]\)

dはクラス1の訓練データを集めた時の次元を表し、d ≦Nである

となります。

ここで確認として期待値とは、N個の訓練画像すべてのデータについて足し合わせてNで割ったものを意味します。

この期待値が、\(\textbf {u}_{(1)j}\)の長さが1であるという制約条件の下で最大になるような方程式を立てれば良い。

つまりこれは主成分分析の時と同じようにラグランジュの未定乗数法で解くことができて、次のラグランジュ関数を微分して0となるようにすれば良い。

\(L_{1}(\textbf {u}_{(1)j})=\displaystyle \sum_{j=1}^d E\left[(\textbf {x}_{(1)}^T\textbf {u}_{(1)j})^2\right] -\sum_{j=1}^d λ_{(1)j}(\textbf {u}_{(1)j}^T\textbf {u}_{(1)j}-1)\)

これを変形すると、

\(=\displaystyle \sum_{j=1}^d\textbf {u}_{(1)j}^T E\left[(\textbf {x}_{(1)}\textbf {x}_{(1)}^T)\right] -\sum_{j=1}^d λ_{(1)j}(\textbf {u}_{(1)j}^T\textbf {u}_{(1)j}-1)\)

となって、\(E\left[(\textbf {x}_{(1)}\textbf {x}_{(1)}^T)\right]\)はクラス1の相関行列を意味しているので、これを\(Q_{(1)}\)とおいて整理し直すと、

\(=\displaystyle \sum_{j=1}^d\textbf {u}_{(1)j}^T Q -\sum_{j=1}^d λ_{(1)j}(\textbf {u}_{(1)j}^T\textbf {u}_{(1)j}-1)\)

となる。

そしてこれを\(\textbf {u}_{(1)j}\)で微分して0とおくと、

\(\dfrac{\partial L_{(1)}(\textbf {u}_{(1)j})}{\partial \textbf {u}_{(1)j}}=2Q_{(1)}\textbf {u}_{(1)j}-2λ_{(1)j}\textbf {u}_{(1)j}=0\)

\(Q_{(1)}\textbf {u}_{(1)j}=λ_{(1)j}\textbf {u}_{(1)j}\)

となる。

したがって、この固有値問題をと解いて得られる、ベクトルと固有値がそれぞれ、部分空間の基底ベクトルと各基底へ射影した長さの2乗の期待値になる。

精度を高める工夫(忠実度κ):

基本的な原理は上に示した通りですが、このまま使うのは実用的ではありません。

なぜなら、各クラスの部分空間の次元に大小がある場合、次元が大きいほど射影も大きくなる傾向があり、クラス間での不平等が生じるという問題があるためです。

これに対する対応策として、基底ベクトルと各基底へ射影した長さの2乗の期待値、つまり固有値λを大きい順に並べた時の累積値に制限をつけて部分空間が大きくなり過ぎないように制限するという方法があります。

この制限の値をはじパタでは忠実度κと呼んでいますが、こうすれば各クラスに属する学習データの部分空間への射影長の期待値は一定に揃うので、クラス間の評価の平等性が担保できます。

忠実度κの値は、分類精度を確認しながら交差確認法などで経験的に決めることになりまます。

テスト（推論）

さて最後にテストデータをどのように分類するかですが、

これは極めて簡単で、テストデータとクラスごとの部分空間との射影をとって、射影長の大きい部分空間のクラスに分類すればOKです。

最後に

最後に断っておきたいのですが、この部分空間法はあくまでパターン認識を効率的に行うための一つの要素技術であって、これ単体で使うという場面はほとんどないと思います。

部分空間法は計算量が少なく高速で処理できることが強みではありますが、デバイスの処理性能が高まっている昨今においては、わざわざ精度を犠牲にして部分空間法単体まで高速化しなければならないというケースは滅多にないはずです。

画像認識ならば、近年はニューラルネットのCNNをベースにした技術が発展して来ていますので、実際にはそちらを選択するケースの方が多いでしょう。

まとめ

今回は部分空間法の原理について説明しました。

はじパタでは原理が線形代数で抽象的に説明されていますが、初見では中々その中身が理解しにくいと思います。

理解の第一歩は、今回の記事のように具体的な例で考えてみることです。

頭を悩ませながらこの記事に辿り着いた方々の理解の助けに少しでもなれば嬉しいです。

参考