カーネル PCA を用いたパターン認識
和田萌

1(指導教員：吉田裕亮)

はじめに表現を φ(x(i) ) とすると, i 番目と j 番目のデータの間のカーネル関数がパターン認識とは, いくつかの概念に分類出来る観測データが存在するとき, 観測されたパターンをそれらの概念のうちのひとつに対応させることである.
近年の社会の情報化は, 文字を介してコンピューターへ直接アクセスする用例や, データベースを構築する為に, 膨大な量の文字データを OCR で読み取る必要性を生み出した. 更に, ワークステーションやパソコンの普及は既に存在する文書を読み取り, 再利用を測る為のフレキシブルな入力を求めており, 手書きパターン認識技術は不可欠な技術となっている.
そこで, 本研究ではこのパターン認識をカーネルPCA を用いて, 機械学習により判別器の構成を行った.

2

K(x(i) , x(j) ) =< φ(x(i) ), φ(x(j) ) >のように定義されている必要がある.

4

PCA は線形の関係 (相関関係) を基礎とした分析であった. それをカーネル法を用いて非線形に拡張した手法がカーネル PCA である. この分析では, 非線形空間への写像を行い, その空間での PCA をカーネル法により行う分析である. カーネル法を用いることで, 実際に非線形な写像を計算することなく非線形な空間でのPCA が行うことができる. 以下にその定化式を示す.
今, 共分散行列

PCA(主成分分析)

PCA(principal component analysis) とは, 多次元データの情報をその総合力の特性を保ちながら, より低い次元に縮約させる方法.
X を p × n のデータ行列とし, X の縦成分 (変数)ごとに標準化し, その行列を X0 とする. この標準化されたデータの相関行列 R を求める.
R=

S=1"
xj xτjn jは非線形な空間への写像 φ とすると,

C=1(X0 )t X0
p1"φ(xj )φ(xj )τ
n jとなる. この時の固有値問題は, 同様に行列 R の固有方程式を解き, n 個の固有値と, 各々の固有値に対応する固有ベクトルからなる行列 V を求める. 固有値は元データの情報保持率を表すことになる. 標準化されたデータ行列 X0 を,

Ca = λaとなる. ここで

zj = φ(xj )τ aである. よって,

X0 V = X ∗と変換する. X ∗ の第 1 列目は第 1 主成分, X ∗ の第 2列目は第 2 主成分と呼ばれる.

3

カーネル PCA

Ca =

1"
1 "
φ(xj )φ(xj )τ
zk φ(xk )
n jnλ
k1 "
= 2zk φ(xj )K(xj , xk )n λカーネル法

j,k

カーネル法とは, (データ集合を X とする時) 2 つのデータの間にある種の類似度を表すカーネル関数, K: X × X → R を通じてデータにアクセスするような学習モデルである.
具体的には, n 個のデータ x(1) , x(2) , ..., x(n) ∈ Xが与えられたときに, モデル f (ξ) が,! n%#$"(i)(i)f (ξ) = g
α K ξ, xλa =となる. ここで

1"zj φ(xj )n jK(xj , xk ) = φ(xj )τ φ(xk )はカーネル関数である. カーネルには Linear, Polynomial, Gaussian, Sigmoid 等が代表的である. よって,i=−1のような形, つまり, カーネル関数の線形結合の関数として表現されるようなモデルを扱うのがカーネル法である. なお, g はある関数, また {α(i) }ni=1 はモデルパラメータである.
カーネル関数はどのような関数でも良いという訳ではなく, 内積として書くことが出来る必要がある. つまり, データ x(i) の d 次元の特徴空間中でのベクトルとなる.

51"
zk K(xj , xk ) = λzjn j

提案手法

本研究ではカーネル PCA を用いて, 手書き文字 (数字) の判別を以下のように行うことを提案する.

21

1.

カーネル選択ではガウスカーネルを使用する.

0, 2, 3, 5, 6 のときと比較すると, どちらも低い数値であるが, 高い正答率を得られた.
ここで, 誤判別された画像データが以下のようなものであった.

K(x, y) = exp(−||x − y||2 /σ 2 )(σ > 0)
2.

それぞれのデータ間距離を計算する.

1(x&1 + x&2 + · · · + x&n )||2nnnn
2"
1 ""= ||&y ||2 −(&y , x&i ) + 2(x&i , x&j )n i=1
n i=1 j=1||&y −

図 1: (誤判別例) 1

この値が一番小さくなる数字グループに属すると判断する.

6

数値実験

6.1

手書き数字データ

ここでは, 公開されているアメリカ合衆国郵便公社が業務で得た実際の手書き数字データを使用する. 数
字 10 種類の手書きデータを各 100 個用意する. 画像
は 16 × 16 画素の 256 次元を使用する. 各画素値は 256階調の離散値である.

図 2: (誤判別例) 7

3. ノイズを除いた 1, 4, 7, 8, 9 の判別
そこで, 上のような人の目でみても明らかに判別が難しい数字データを学習データから除き, 改めて 50 個用意し, 判別を行った. すると, 下の表のようにすべての数字に対し, ほぼ 100%の高い正答率を得ることができた.

1. 0〜9 の判別
0〜9 を一度に判別を試みたが, 数字が多すぎるため判別は不可能であった.
そこで, 似ているもの同士を同じグループとしてまとめ 2 群にわけたあと, それぞれのグループ内で各数字を判別する階層的方法をとった.
0, 2, 3, 5, 6 と 1, 4, 7, 8, 9 の 2 群に分けたときが,最も判別正答率が高いためこれを使用する.
この段階における判別の正答率は, 学習データでは96%, また学習データとは違うデータを使って汎化性能を調べた場合は 92%であった.

n02356

2. 0, 2, 3, 5, 6 の判別
0, 2, 3, 5, 6 のデータを各 50 個ずつ用意し, 250 個のデータに対して改めてパラメータを選択し, 判別機にかける. 以下の表からわかるように, どの判別においても, 100%に近い高い正答率を得ることができた.
次に, 学習データとは異なるデータをテストデータとして 50 個用意し, 判別を行い汎化性能を調べた. 平均正答率は 96.4%と, 学習データ判別の正答率と比較すると低い数値ではあるが, かなり高い正答率を得られた.
n0235
6

学習データ正答率

汎化性能正答率

100%
100%
98%
100%
100%

100%
100%
92%
96%
94%

7

学習データ正答率

汎化性能正答率

92%
94%
94%
92%
90%

80%
86%
90%
76%
88%

改良後正答率

92%
94%
94%
92%
90%

100%
96%
100%
98%
94%

まとめと今後の課題

昨年の研究では, 256 次元のデータに対して PCA により次元を下げた後, 2 群の判別 (例:3 であるか, そうでないか) を行った. その拡張として, 本研究ではカー
ネル PCA を用いて, 次元を落とす手間を省き, 256 次元のデータをそのまま 2 段階で 10 通りの文字の識別を行った. この手法はかなり単純な計算法で判別を行うことができるため, 有効であると思われる. さらに,学習に用いるデータ数を増やすことで, 判別における正答率を高めたい. また, 数字判別より複雑なアルファ
ベットやカタカナなどにおいてもこの手法が有効であるか確認したい.

参考文献[1] B.Schlkoph and A.J.Smola, Learning With Kernel, MIT Press, 2002.

3. 1, 4, 7, 8, 9 の判別
同じ方法で 1, 4, 7, 8, 9 の学習データの判別正答率,汎化性能を調べた結果は以下の表のようになった.
n02356

改良前正答率[2] 石村貞夫, すぐわかる多変量解析, 東京図書 (1992)

22