SVM を用いた
多クラスパターン識別手法
に関する研究
02TA601C
宮下亨裕
1.はじめに
SVM(Support Vector Machine)とは、近年注目を集めているパーセプトロン
型のパターン認識手法の名前である。この手法は、理論的基礎を持ち、実験的
に非常に優れた成績を挙げている。学習は、二次計画問題を解くことによって
行うことができ、実現しやすい。SVM が注目を集めているのは、この 3 点を
兼ね備えているからである。
だが、SVM は 2 クラス識別器であるため、そのまま、多クラス識別に適用す
ることは出来ない。2 クラス識別器を多クラス識別に適用する代表的な方法と
して、1vr(one versus the rest)がある。一つのクラスと他の残りのクラス間で
識別器を学習して用いるものである。これを SVM に適用した場合、学習に全
てのデータを用いた N 個の SVM を構築する必要があり、識別時間が遅くな
る。
本研究では、多クラス識別器の識別所要時間と識別率に注目し、研究を進めて
いくが、まず、ある l に対して、各クラスを l の長さを持った＋1 と−1 のコー
ドで表して行列を作り、その行列上にマッピングされる 2 クラス識別問題を
解くことを基本とする ECC について、そのコード中の符号に 0 を許し、コー
ドの長さ l を変える事によって、識別所要時間の短縮を狙う。（コード中の 0
は、そこにマッピングされる 2 クラス識別問題を扱わないことを意味する。）
次に、階層型クラスタリングを用い、クラスをクラスタに分割し、そこに２
クラス識別を適用し、識別所要時間の短縮を狙う。
2
2.SVM について
(1) 学習法
線形 SVM では、テストサンプル x = ( x1, ..., x d ) T の識別関数は次のようになる。
d
f ( x) = ∑ w j x j + b
j =1
この識別器の f ( x) = 0 を満たす点の集合(識別面)は、d−1 次元の超平面とな
る。訓練サンプルを識別する超平面は、無数に存在するが、パターン認識の
目的は、訓練サンプルを識別することではなく、未知のテストサンプルを正
しく識別することである。そこで、SVM は２つのクラスの真ん中を通る識
別面を最も優れているとする。そのために、超平面と訓練サンプルとの最小
距離を評価関数として用い、これを最大にするように超平面を決定する。よ
って、識別面は、各クラスの訓練サンプルの凸包を結ぶ最短の線分の中点を
通り直行する超平面となる。
w
訓練サンプルを、 x1 , x 2 ,..., xl で、それぞれのクラスラベルを、 y1 , y 2 ,..., y l と
表し、訓練サンプルがクラス 1 に属していれば、 y = 1 、クラス２に属して
いれば、 y = −1 とする。パラメータに冗長性があるので、次のような制約を
3
加える。
min | wT xi + b |= 1
i =1,...,l
この時、訓練サンプルと超平面の最小距離は、
1
|| w ||
になる。よって、次のようになる。
目的関数：
|| w || 2 →最小化
制約条件：
y i ( wT xi + b) ≥ 1(i = 1,..., l )
ラグランジュ乗数 α i (≥ 0) を導入すると、
L( w, b, α ) =
l
1
T
|| w || 2 −∑ α i ( y i (( xi w + b) − 1))
2
i =1
最適化問題を解くと、
l
∑α y
i =1
i
i
=0
l
w = ∑ α i y i xi
i =1
これを、目的関数と制約条件に代入すると、
目的関数：
l
1 l
α
−
∑
∑α iα j yi y j xi x j →最大化
i
2 i , j =1
i =1
制約条件：
l
α i ≥ 0(i = 1,..., l ), ∑ α i y i = 0
i =1
この２次計画問題を解き、 α i ≠ 0 を満たすものがサポートベクター(SV)に
対応する。
(2) ソフトマージン
ここまでは、訓練サンプルが超平面によって完全に識別できると仮定して
るが、一般には、そうでない場合も考えられる。その場合、 w, b が存在しな
4
いため、最適化を行うことが出来ない。そのような場合に対処するために、
考案されたのが、ソフトマージンである。
最適化を行うには、制約条件を緩める必要があるので、スラック変数
ξ ≥ 0, i = 1,...l
を導入し、制約条件を次にように変更する。
y i ( wT x i + b) ≥ 1 − ξ i
最適化においては、次の目的関数を最小化する。
l
1
|| w || 2 +C ∑ ξ i
2
i =1
C の設定は、実験的に行うことになる。
ラグランジュ乗数αに関する問題も次のように変更される。
目的関数：
l
1 l
T
α
−
α iα j y i y j xi x j →最大化
∑
∑
i
2 i , j =1
i =1
制約条件：
l
0 ≤ α i ≤ C ; (i = 1,..., l ), ∑ α i y i = 0
i =1
ラグランジュ乗数に関する問題は、比較的シンプルな形になる。
(3) 非線形識別器への拡張
線形識別器は、2 クラスが線形分離可能な場合には、良い認識率を達成でき
るが、一般にはそうではないことが多い。そこで、前処理として、非線形な
写像を用いて、より高次元の空間に写像を行い、線形分離性を高めることが
考えられる。
Φ : ℜd → ℜq
このような写像を行い、写像先の空間 ℜ q で線形識別を行えば、実質的に、
元の空間で非線形識別を行っているのと同じことになる。
ただし、この写像は、元の空間におけるサンプル同士の距離関係を、ある程
度保存する必要がある。そこで、元の空間で定義されるカーネル関数 K ( x, x ′)
を用意して、Φは次の条件を満たすと仮定する。
K ( x, x ′) = Φ ( x) T Φ( x ′)
つまり、カーネル関数の値が、写像先で内積として反映されるとすつ。ここ
で、K を 2 点間の近さを表す関数と設定すれば、内積という形で、近さが保
5
存されることになる。
このようなΦが存在すると仮定し、 ℜ d において SVM を適用しよう。する
と、識別関数は、
f (Φ ( x)) = wT Φ ( x) + b
となる。よって、
n
f (Φ( x)) = ∑ α i y i Φ( x) T Φ ( xi ) + b
i =1
n
= ∑ α i y i K ( x, x i ) + b
i =1
学習の問題も、
目的関数：
l
∑α i −
i =1
1 l
∑α iα j yi y j K ( xi , x j ) → 最大化
2 i , j =1
制約条件：
l
0 ≤ α i ≤ C (i = 1,..., l ), ∑ α i y i = 0
i =1
と書ける。
注目すべきなのは、識別関数も、学習の最適化問題も、Φを用いず、K によ
ってのみ記述できるという点である。したがって、 ℜ q における識別が、実
際にΦを求めることなく実現できるのである。このようにして、Φの求解を
避ける方法は、カーネルトリックと呼ばれる。
カーネルトリックが有効なのは、実際にΦが存在するようなカーネルが与え
られた場合に限る。カーれるが正定値関数のときには、Φが存在することが
知られている。その例としては、多項式カーネル
K ( x, x ′) = ( x T x ′ + 1) p
やガウシアンカーネル
|| x − x ′ || 2
)
σ2
などがある。このようなカーネルに対応するΦは、特徴空間を非常に高次元
の空間に写像する。例えば、ガウシアンカーネルを用いると、写像された 2
点の内積は必ず正で 0 で正にならない。したがって、元の空間に存在する無
限個の点を写像すると、写像先の 2 点は直交しないから、無限次元の空間を
張ることになる。
K ( x, x ′) = exp(−
(4)SVM の理論
6
まず、p(x,y)という確率分布があり、訓練サンプルも、テストサンプルも
、この同じ確率分布に従って独立にサンプリングされたと仮定する。また、
損失関数 q を誤りが起こったときのみ 1 になるように定義する。
0, yf ( x) ≥ 0
q ( x, y ) =
1, yf ( x) < 0
すると、テストサンプルが無限個ある時、誤識別率は、
R( f ) = ∫∫ q( x, y ) p( x, y )dxdy
と表せる。一方、訓練サンプルに対する誤識別率は、同様に、
Remp ( f ) =
1 l
∑ q ( xi , yi )
l i =1
と表せる。一般に、 R( f ) を期待リスク、 Remp ( f ) を経験リスクを呼ぶ。学習
問題は、ある関数の集合 F が与えられたとき、その中から、最も期待リスク
を最小化する f を見付ける問題として定式化される。しかし、経験リスクし
か知ることが出来ないので、代わりに経験リスクを最初化するしかない。こ
の方法は、経験リスク最小化(ERM)と呼ばれる。
ERM を用いる時、学習結果は、関数の集合 F をっどのように設定するかで
異なってくる。学習結果の期待リスクをできるだけ小さくするための F の設
定法の手がかりとなるのが、関数の集合 F におけるリスクの差の上限、数式
で表せば、
sup | R( f ) − Remp ( f ) |
f ∈F
である。
ここで、 f と q は 1 対１に対応するので、集合 F には損失関数の集合 L が対
応する。ここで、 L の VC 次元を h とすると、次の不等式は、1 − η 以上の確
率で成立する。
sup | R( f ) − Remp ( f ) |≤
f ∈F
ここで、
7
Remp ( f )
ε (l )
1+ 1+
2
ε (l )
ε (l ) = 4
h(ln(2l h) + 1) − ln(η 4)
l
VC 次元とは、集合 L の大きさを示す量の一つである。よって、 L の VC 次
元を小さい値に抑えれば、それによってリスクの差を小さくすることが出来
る。
これを用いて、実際に期待リスクの最小化を行う方法に、構造的リスク最小
化(SRM)がある。これは、入れ子構造を持つ複数の関数集合を考えて、
F1 ⊂ F2 ⊂ ... ⊂ Fk
とし、このうちどれを選んで ERM を行えば、最も期待リスクを小さくでき
るか考える。
期待リスクは、経験リスクとリスクの差の和であるから、これを最小にする
には、中くらいの大きさのものを選べばよいことが分かる。
SVM は、構造的リスク最小化に基づいた学習法として解釈できる。SVM で
用いている関数集合は、線形関数の集合であり、
Fr = { f | f ( x) = wT x + b, || w ||≤ r}
と定義される。SVM では、訓練サンプルが完全に識別できるという制約の
元で、|| w || を最小化する関数を選んでいる。これは、経験リスクを 0 にする
関数の中で、最も小さい Fr に含まれているものを選ぶことに対応する。つま
り、経験リスクを 0 にする関数の中でも、小さい集合に含まれているものを
選ぶことにより、リスクの差の上限を低く抑え、結果的に期待リスクを小さ
くしようとしている。
8
3.1vr と ECC について
一つのクラスと他の残りのクラス間で識別器を学習して用いるものである。こ
れを SVM に適用した場合、学習に全てのデータを用いた N 個の SVM を構築
する必要がある。５クラスの問題を識別する場合、正の訓練サンプルに用いる
クラスを＋１、負の訓練サンプルに用いるクラスを−1 とすると、次のように
表現できる。
1
2
3
4
5
#1
1
-1
-1
-1
-1
#2
-1
1
-1
-1
-1
#3
-1
-1
1
-1
-1
#4
-1
-1
-1
1
-1
#5
-1
-1
-1
-1
1
ここで、列の数は SVM の数を表す。1vr では、全てのデータを学習に用いる
ことが明確にわかる。通常、1vr では、テストサンプルについて、#1∼#5 に
相当する SVM が出力する値が最大になる SVM に相当するクラスを、そのテ
ストサンプルのクラスとするが、各行を各クラスのコードと見なし、#1∼#5
にテストサンプルが入力された時の出力値との内積などの距離の近いコード
のクラスをそのテストサンプルのクラスとする方法も考えられる。
例えば、あるテストサンプルについての#1∼#5 の SVM による出力値が
0.2 1.2 -1.4 -2.0 -0.8
であったとすると、それぞれのクラスのコードとの内積は、
3.2 5.2 0.0 -0.8 1.2
であり、クラス 2 がこのテストサンプルのクラスであると決定できる。
これを一般化すると、
・ 各クラスに同じ長さのコードを割り当てる
・ このコード長が SVM の個数になる
・ 各 SVM の学習に用いるデータは各コードの各ビットの値が+1 か−1 かに
よって与える。
9
・ 得られた SVM に未知入力を与えると、コード長分の出力値が得られ、こ
の数値列と各コードとの内積などの距離を求め、もっとも近いコードに相
当するクラスをこの入力のクラスとする。
という多クラス識別法があると考えることができる。
これが、ECC の基本的な考えである。ECC では、コードの各ビットの値を
±1 以外に拡張することが可能である。もっとも簡単な拡張は０とすること
であり、０は学習データとして、そのクラスを用いないということを意味す
る。
このことから、各クラスに割り当てるコードを上手く選べば、学習に用いる
データを少なくし、その結果、識別に必要なサポートベクター(SV)数を少な
くできる可能性がある。
10
4.実験 1(1vr と ECC の比較)
(1) 評価のポイント
1vr と ECC の比較の際の観点として、識別率とサポートベクター(SV)数
に注目した。識別率は、識別器の評価をする上で、当然、注目すべき値で
ある。ところで、2 章の議論から、サポートベクター数が SVM の識別器(識
別面)の複雑さの指標となることがわかる。識別器が複雑であるというこ
とは、入力パターンの識別所要時間の増加につながるので、サポートベク
ター数が識別所要時間の目安になるということが言える。したがって、サ
ポートベクター数に注目する。ただし、ECC のコードの長さが 1vr のデ
ータ数と違う時、学習される SVM の数が違うので、サポートベクターの
総数が厳密に識別所要時間に対応していえるとは言えないが、サポートベ
クター以外のデータは結果に影響を及ぼさないので、十分に目安としての
機能を果たしうる。
(2) 学習データのサンプリング
学習データの符号の正負(+1 と−1)の分布について、偏ってどちらかが多
い時、そのデータで学習された識別器の識別率が正確に識別器の性能を反
映しているとは言えない場合があるので、少数クラスを繰り返しサンプリ
ングし、符号の正負の分布の偏りをなくした。
11
(3) 実験の詳細
① 使用データ
12 クラスの手書きひらがなパターンから、方向性特徴抽出と呼ばれる方
法で抽出した 256 次元ベクトルを用いた。
② ECC のコードの決定
コード長と符号の発生確率を変化させたランダムコードを与えた。
実験したコード長、発生確率
コード長
発生確率(+1)
発生確率(-1)
1
18
0.2
0.2
2
24
0.15
0.15
3
24
0.2
0.2
③ 使った SVM
ガウシアンカーネルを用い、c は 1000、g は 0.00001 で学習、出力を行
った。
④ 識別法
各 SVM の出力を+1 と−1 に符号化し、その数値列と各クラスのコード
の内積も求め、もっとも距離が近いコードのクラスを入力サンプルのク
ラスとした。
12
(4) 結果
① 1vr
SV 数
識別率
1950
正解が 1 番目に入った確率
(学習データ/テストデータ)
0.99
0.95
正解が 2 番目以内に入った確率 1.00
(学習データ/テストデータ)
0.96
正解が 3 番目以内に入った確率 1.00
(学習データ/テストデータ)
0.96
13
② ECC
(a) 符号発生確率 +1：0.2
コード長：18
-1：0.2
SV 数
識別率
1912
正解が 1 番目に入った確率
(学習データ/テストデータ)
0.79
正解が 2 番目以内に入った確率
(学習データ/テストデータ)
0.99
正解が 3 番目以内に入った確率
(学習データ/テストデータ)
1.00
(b) 符号発生確率 +1：0.15
コード長：24
0.99
2638
正解が 1 番目に入った確率
(学習データ/テストデータ)
0.78
正解が 2 番目以内に入った確率
(学習データ/テストデータ)
0.94
正解が 3 番目以内に入った確率
(学習データ/テストデータ)
1.00
(c) 符号発生確率 +1：0.2
コード長：24
0.76
0.93
0.99
-1：0.2
SV 数
識別率
0.99
-1：0.15
SV 数
識別率
0.77
3618
正解が 1 番目に入った確率
(学習データ/テストデータ)
1.00
正解が 2 番目以内に入った確率
(学習データ/テストデータ)
1.00
正解が 3 番目以内に入った確率
1.00
14
0.97
0.99
(学習データ/テストデータ)
1.00
(5) 結果の考察
ランダムコードを与えた ECC では、1vr に比べて、SV 数があまり変わら
ない場合は、累積正解率こそ遜色ないものの、1 位正解率では著しく劣り、
1 位正解率で勝る場合は、SV 数が大幅に増える。識別率ど識別所要時間
で、向上がみられたとは言い難い。ただし、コード中の 0 が多いので、SVM
を構築する際に用いるデータ数が少なく、高速な学習が可能である。
15
5.階層的クラスタリング
N 個の標本を C 個のクラスタに分ける連続した分割処理を考え、まず、最
初の分割処理として N 個の標本を N 個のクラスタに分割する。次に N−１
個のクラスタへの分割、その次は N−２個のクラスタへの分割という具合に
N 回分割処理を行えば、最終的には全ての標本は、１つのクラスタに含まれ
る。任意の標本 x と x’があるとすると、２つの標本 x と x’はあるレベルで同
じクラスタに属する。あるレベル K で、２つの標本が同一のクラスタに属
する時、これより上位のレベル全てで、２つの標本が同一クラスタに属する
場合、このようなクラスタリングを階層的クラスタリングと言う。
階層的クラスタリングは、アプローチ手法の違いから、凝集的アプローチと
分割的アプローチの２つの手法に分けられる。凝集的手法では、N 個の１要
素クラスタから開始し、連続的にクラスタを融合していく。分割的手法では、
全ての標本を含む１つのクラスタから開始して、連続的にクラスタを分割す
る。あるレベルから次のレベルへと移るために必要な計算は、通常、凝集的
手法がより簡単である。
(凝集的階層化クラスタリングのアルゴリズム)
1 begin
2
initialize
do
c, c ′ ← n, Di ← {xi }, i = 1,..., n
c ← c −1
3
もっとも近いクラスタを探す。 Di , D j とする。
4
Di , D j を融合
5
6
until c = c ′
return c 個のクラスタ
7 end
16
6.実験 2(階層的クラスタリングを応用した識別手法)
(1) 実験の前に
用いるデータが属するクラスがいくつかのクラスタにはっきり分割でき
るなら、まず、クラスタに分割し、そのクラスタ分割に基づいて、多ク
ラス問題を解くことが考えられる。
(2) 階層的クラスリングの適用
各クラスに属するベクトルデータから平均ベクトルを求め、これによって
クラス間の距離を決定することとし、これに凝集的階層化クラスタリング
を適用する。具体的には、
① 各平均ベクトルを要素とする集合に適用する。
② 要素間の距離が最も小さい組み合わせを探し、
これらを融合し、
融合してえられた要素の平均ベクトルは、
融合される要素の平均とする。
③ 要素数が 1 になるまで、これを繰り返す
これによって、木構造による表現が得られる。
(3) 木構造の利用
５つのクラスに階層的クラスタリングを適用して、次の木構造による表現
が得られたとする。
#1
#2
#3
#4
1
2
3
17
4
5
#1、#2、#3、#4 の枝分かれの部分に識別器を配置し、出力値が正の時に、
左に進むとすると、以下のような符号化が出来る。
1
2
3
4
5
#1
1
1
1
1
-1
#2
1
1
1
-1
0
#3
1
1
-1
0
0
#4
1
-1
0
0
0
未知入力に対し、全ての識別器が出力するわけではないので、厳密な ECC
とは違うが、0 が含まれるため、学習データが少なく、SV 数が抑えられ
る可能性がある。
木構造の根元に近い部分では、学習データが多いが、識別すべきクラス間
の距離が十分に大きく、識別しやすい問題であることが期待できる。また、
葉に近い部分では、識別すべきクラスの距離が近く、識別困難な問題にな
ること予想されるが、学習データが少なく、SV 数が抑えられる可能性が
ある。
18
(4) 実験の詳細
① 使用データ
12 クラスの手書きひらがなパターンから、方向性特徴抽出と呼ばれる方
法で抽出した 256 次元ベクトルを用いた。
② 階層的クラスタリング
使用データに凝集的階層化クラスタリングを適用して、木構造の表現を
得た。
③ 木構造表現の利用
木構造の枝分かれの部分に SVM を配置し、その出力値の正負によって
進む部分木を決定する決定木として利用した。
④ 使った SVM
ガウシアンカーネルを用い、c は 1000、g は 0.00001 で学習、出力を行
った。
19
(5) 結果
① 階層的クラスタリングを適用して得られた木構造表現
使用したデータが構成する 12 のクラスは、凝集的階層化クラスタリ
ングによって、次のような木構造で表現されるクラスタに分割された。
3
2
0
4
1
9
7
8
5
6
10
11
② 識別結果
SV 数
1164
識別率
(学習データ/テストデータ)
1.00
0.98
(6) 結果の考察
結果の SV 数は、全ての SVM の SV 数である。この実験で用いた方式の
場合、未知入力があった時、必ずしも全ての SVM に入力されるわけでは
ないので、結果の SV 数の少なさ以上に、識別所要時間が 1vr に対して、
向上していると考えられる。
識別率は、1vr とほぼ同等であると言える。
20
ただし、順位確率が出ず、多重仮説が必要な場合には、適していない。
7.まとめ
ECC は、1vr に対して、同等の識別所要時間を実現すると、1 位正解率で大き
く劣るが、累積正解率が高く、学習データが少ないため、高速な学習が可能で
ある。多重仮説が必要な場合に可能性がありうる。
階層的クラスタリングを応用した多クラス識別法は、学習データも少なく、
SV 数も少ない。高速な学習と識別が可能であると考えられる。ただし、順位
確率が出ないので、多重仮説が必要な場合には適していない。そこに関連して、
木構造を符号化して、行列として表現したものを、ECC のコードとして見な
して識別を行う多クラス識別法も検討してみるべき課題である。
21
(参考文献)
「サポートベクターマシンとは何か」 津田宏治
電子情報通信学会誌 Vol.83 No.6 pp.460-466
「パターン識別」Richard O. Duda
Peter E. Hart
David G. Stork
監訳
尾上守夫
新技術コミュニケーションズ
22
2000 年 6 月
23
© Copyright 2024 ExpyDoc
