パラメータの変動に伴うガウス型カーネル行列の固有値の挙動
理学専攻

情報科学コース

1840667 根本優花

はじめに

1

カーネル法は非線形データ解析の手法の一つである．
近年はサポートベクトルマシンの発明によって一躍注目されるようになった．カーネル法を扱う際には，カーネル関数と呼ばれる非線形の関数を用いる．カーネル法の最も重要な特徴は，カーネル関数に線形手法を用いて非線形問題を解くという点である．この方法は複雑な最適化問題を避け，大規模なデータ解析をすることを可能にしている一方で，従来のパターン認識とは逆転の発想を用いてデータを一旦高い次元の空間に移してから処理を行うというカーネルトリックを用いる．
本研究では，カーネルアルゴリズムの多くが固有値問題に帰着していることを踏まえ，カーネル関数によって生成されるカーネル行列とその固有値に関する実験をもとに，クラスタリングにおけるクラスタ数の推定ならびにカーネルパラメータの推定，データ次元の削減に関する提案を行う．

2カーネル法とカーネル行列

2.1

カーネル関数

2.2

Wishart 行列と Marchenko-Pastur 則

3.1

Wishart 行列とする．この N × N のランダム行列 WN を Wishart行列という．

3.2で与えられる．ただし，λ± (λ) = (1 ±3.3√λ)2 である．

Catalan 数

Marchenko-Pastur 分布において，λ = 1 のとき，つまり Wishart 行列が正方行列の積のとき，そのモーメント列は Catalan 数 Cn で与えられる．ここで Cn は，( )12n(2n)!
Cn ==n+1 n(n + 1)!n! (n ≥ 0)

m=1

ガウスカーネル= 1, 1, 2, 5, 14, 42, 132, 429 · · ·となる自然数列である．

k(x, x′ ) = exp(−β||x − x′ ||2 )この式は正規分布の確率密度関数と同じ形をしている．
このカーネルをガウスカーネルという．一般にカーネル行列は正定値性をもつ．

4

クラスタ数と優固有値の関係性について

4.1

実験概要

正規乱数を使ってクラスタを生成し，これに対しパラメータ β を動かしながらガウス型カーネル行列の固有値を求める．このとき，クラスタ数や配置を様々に用意し，パラメータ β の値に伴う優固有値の挙動を考察する．

カーネル行列カーネル関数を要素にもつカーネル行列k(x1 , x1 ) k(x2 , x1 ) · · · k(xn , x1 ) k(x1 , x2 ) k(x2 , x2 ) · · · k(xn , x2 ) 


K=
..
..
..
..
.

.
.
.

k(x1 , xn ) k(x2 , xn ) · · ·Marchenko-Pastur 則Wishart 行 列 の 固 有 値 漸 近 分 布 を 与 え る ，Marchenko-Pastur 分布がある．N × M の Ginibre 行列の漸近的縦横比を λ とおくとき，その固有値漸近分
布は√−(x − λ− )(x − λ+ )1[λ− ,λ+ ] (x)dxdπλ (x) =2πλx+ max{0, 1 − λ}δ0 (x)以下の式によって表される関数をガウスカーネルという．ただし，|| · || はベクトルノルムを表し，β > 0はあらかじめ適当に定められるパラメータである．

2.3

3

G を N × M の独立に平均 0 分散 1 の標準ガウス分
布に従う変数を要素に持つランダム行列，その共分散行列を，
1
WN = GN,M TGN,MN

一般に，ϕ1 , · · · , ϕd という非線形関数で特徴抽出
さ れ た ベ ク ト ル を 特 徴 ベ ク ト ル と い い ，Φ(x) =(ϕ1 (x), · · · , ϕd (x))T と書くことにする．X の二つの要素 x, x′ に対し，カーネル関数 k(x, x′ ) は x, x′ それぞれの特徴ベクトルどうしの内積d∑k(x, x′ ) = Φ(x)T Φ(x′ ) =ϕm (x)ϕm (x′ )として定義される．

(指導教員：吉田裕亮)

4.2

実験結果

図１−２，図２−２，図３−２の固有値分布の全てのグラフに関して、横軸はパラメータ β の値，縦軸は固有値の値を示す．

k(xn , xn )4を考えたとき，その二次形式が常に非負，すなわちn ∑n∑αi αj Kij ≥ 02-3-2-1

1234

i=1 j=1-2が任意の n 次元ベクトル α = (α1 , · · · , αn )T について成り立つとき，カーネル関数 k(x, x′ ) は正定値性をもつ．

-4

図１−１：クラスタ数２の正規分布

13005ガウスカーネルの最適なパラメータ β250

先の実験結果で得られたガウス型カーネル行列の固有値とパラメータ β のグラフにより，カーネル関数を扱う際に重要となるパラメータ β の決定方法の提案を行う．

200150100503005101520250

図１−２：図１−１の固有値分布
20081506100

45025-8-6-4-224101520

図４：クラスタ数２の正規分布の固有値分布

6-2

図４は先述したクラスタ数が 2 つの正規分布のパラメータ β の変動に伴う固有値のグラフである．図４中の矢線で示された第２固有値を観察する．すなわち第２固有値が極大点を与える β を最適な β として与える．

図２−１：クラスタ数３の正規分布
250

200

6

データの次元の縮約の提案

150

先に紹介した方法で最適なβを決定したのち，ガウス型カーネル行列の固有値を求め，その優固有値を上からひとつずつ取り除き、そのモーメント列を求める．
モーメント列が Catalan 数にできるだけ近くなるまで優固有値を取り除く．取り除かれた優固有値の数が有効なデータの次元になる．それ以降の固有値はランダムな正方行列の積の Wishart 行列の固有値，すなわちλ = 1 の Marchenko-Pastur 則に対応すると考えられるので，取り除いた部分が本質的な主要部になる．この方法を用いれば，データの次元を大幅に縮約し，計算量を大幅に削減することも可能となる．

10050246810

図２−２：図２−１の固有値分布642-6-4-2246-2-47-6

図３−１：２つの正規分布がクロスした１つのクラスタ

本研究では、カーネル行列とその固有値の挙動を観察することにより得られた３つのトピックスについて述べた．これらの実験結果や提案をカーネル法を扱う際に適用することで，より分析の高精度化と効率化が期待できる．それぞれの提案について補足を述べると，クラスタ数と優固有値の個数の関係性については，クラスタ数が目視で明らかに決定できない正規分布の場
合，優固有値が明らかに同じ個数になったとは断定できなかった．また，ガウスカーネルの最適なパラメー
タ β の決定方法に関しては，クラスタ数が１つの場合には適用できないため，別の方法でパラメータを推定する必要があるといえる．またこれらの実験については，自ら推定しやすい正規分布を作成したので実データに適用するまでに至っていない．しかし，いずれも理論的に推測したものを実験で示すことに成功しているので，今後実験を続けることで更なる発展も期待できるといえる．

40030020010051015

考察と今後の展望20

図３−２：図３−１の固有値分布
図３−１に関しては，２つの正規分布が交差したクラスタである．実験前は分散が２方向に伸びているた
め，優固有値の個数は２つになるのではないかとの予測を立てていたが，図３−２の結果を見ると実際には優固有値の個数は明らかに１つになった．それぞれの固有値分布のグラフを見ると，上から数本のグラフが明確に分かれていることがわかる．そしてその本数は，クラスタ数に対応していることがわかる．これらの結果により，クラスタ数が複数個ある場合について、優固有値とクラスタ数は一致するということが充分にいえる．

参考文献[1] 赤穂昭太郎「カーネル多変量解析」岩波書店,2008[2] A.M. Tulino and S. Verdu「Random Matrix
Theory and Wireless Communications」Now
Pub,2004

2