Parabola JournalMachine Learning

ガウス過程に関して

この記事は Machine Learning Advent Calendar 2015 – Qiita に併せて書かれたものです.以下の文章は元々自分の研究でガウス過程を使うためにまとめておこうと思い書いているもので,このアドベントカレンダー後にも適宜修正する予定です.

過程とは元々時間tに関連した関数  f(t) に関して議論をするための言葉らしいですが,確率過程とは(インターネット上の情報源をまとめると)確率変数の集合 \{X(t) \mid t \in\mathcal{T}\} に関して議論するための手法群のようです.適当にi.i.d.なものを取ってきてもいいですが,確率変数同士に何らかの構造があるとき,より価値のあるものになるのでしょう(例; マルコフ連鎖;  X(t)  X(t-1) のみに依存し, \mathcal{T} は時間のインデクスである).

一般的な教師あり機械学習 (supervised machine learning) の 回帰問題 (regression problem) では訓練データの集合 \mathcal{D} = \{x^{(i)}, y^{(i)} \}_{i=1}^n が与えられた時に,モデル  f(\cdot) が持つパラメータを学習し,未知の入力  x^{(n+1)} に対して値  f(x) を計算し,その性能を議論します. PRML§3/§6で扱っている線形回帰モデルでは,シンプルな形であれば  y = w^{\mathrm{T}} x や基底関数を用いて  y = w^{\mathrm{T}} \phi (x) の形をモデルとして,パラメータ  w を求めます.以降では  \phi(x) = (\phi_1(x), \phi_2(x), \cdots, \phi_H(x)) とします.

ガウス過程は訓練データ  y^{(1)}, y^{(2)}, \cdots, y^{(n)} に関して構造として,ガウス分布を与えます.前提として事前知識として  p(\mathbf{w}) = \mathcal{N}(w \mid 0, \alpha^{-1} I) を重みの事前分布に与えると, 基底関数 (とその個数H) がfixされているため,上の  \mathbf{y}^\mathrm{T} = (y^{(1)}, y^{(2)}, \cdots, y^{(n)}) に関する議論はそのままパラメータの事前分布から特徴付けされます.平均は0になり(事前分布より),共分散行列は  \mathrm{cov}[\mathbf{y}] = \alpha^{-1} \mathbf{\Phi} \mathbf{\Phi}^\mathrm{T} . これが どんな入力と出力 (→ これ \mathcal{D} = \{x^{(i)}, y^{(i)} \}_{i=1}^n ) に対しても成り立つとき,  \mathbf{y} はガウス過程に従うと呼ぶ(定義).ガウス過程をベイズ的な回帰モデルの特徴付けとして説明する以外の説明方法としてはGPML(Gaussian Process for Machine Learning)にいろいろと書かれています (Weight-space view と Function-space view,あまり意味がわからなかった).

GPy

使うぞい.

import numpy as np
import matplotlib.pyplot as plt
import GPy

X = np.linspace(0.05,0.95,10)[:,None]
Y = -np.cos(np.pi*X) + np.sin(4*np.pi*X) + np.random.normal(loc=0.0, scale=0.1, size=(10,1)) 
plt.figure()
plt.plot(X,Y,'kx',mew=1.5)


figure_0

k = GPy.kern.RBF(input_dim=1, variance=1., lengthscale=0.2)
model = GPy.models.GPRegression(X, Y, k)
model.plot()


figure_00

model.optimize()
model.plot()


figure_1

ガウス過程回帰

予測分布の真面目な導出は機械学習プロフェッショナルシリーズ「異常検知と変化検知」の§8.3と§8.4にあります.

“ガウス過程回帰の完全な導出と、実験計画法への応用。 ガウス過程回帰は工学のいろんなところに顔を出しますが、 ミステリアスな方法だと思われているようなので、完備された解説を書きました。”


異常検知と変化検知 (機械学習プロフェッショナルシリーズ)
井手 剛 杉山 将
講談社
売り上げランキング: 11,821


カーネル

ガウス過程回帰(GPR)がカーネルに関する章PRML§6に出てくる理由は,ガウス過程における  \mathbf{y}^\mathrm{T} = (y^{(1)}, y^{(2)}, \cdots, y^{(n)}) に関する同時分布が平均0であり共分散行列 \alpha^{-1} \mathbf{\Phi} \mathbf{\Phi}^\mathrm{T} = K, K_{i,j} = k(x_i, x_j) = \alpha^{-1} \phi(x_i)^{\mathrm{T}} \phi(x_j) で特徴付けられるからでしょうが,(無限次元とか言い出すのもこのあたりから),
あまりカーネル法との話は説明されていないと感じました (最初にPRMLを読んだ時も,今回読んでたときも).

こういった部分に関しては「カーネル多変量解析」という本の§2.カーネル多変量解析の仕組み > §2.3.確率モデルからの導入 (b) 正規過程からカーネルへ)という部分と,§7.汎化と正則化の理論; 7.2.正則化とカーネル法 (c) 正規過程(正則化と確率モデル)という部分にガウス過程の話があります.ここでは上で話していた「同時分布が平均0,行列Kを共分散行列としたガウス分布」といった話とは別として,関数自体に注目した場合の話もあります.自分の場合は両方読んでなんとなくイメージがつかめた気分になりました.



リンク


– PRMLの§3(線形回帰),§6.1&6.4(カーネル法,ガウス過程)あたりが参考になります
@naoya_t さんのグラフ再現: http://naoyat.hatenablog.jp/entry/2012/11/13/220933
– GPMM; Gaussian Processes for Machine Learning: Book webpage
– 統数研の持橋先生の資料1: http://www.ism.ac.jp/~daichi/paper/svm2009advgp.pdf
– 統数研の持橋先生の資料2: http://www.ism.ac.jp/~daichi/lectures/H26-GaussianProcess/gp-lecture2-daichi.pdf
– 集中講義 Gaussian Process Summer/Winter School; Gaussian Process Summer Schools
– 集中講義 Gaussian Process Winter School 2015のipython notebook; Jupyter Notebook Viewer

他のブログ記事
ガウス過程シリーズ 1 概要

Parabola JournalMachine Learning

Scikit-learnを使って主成分分析などを中心に遊んだ

Machine Learning Advent Calendar 2014の企画で書いているブログ記事です.最近私生活で使ってたことや,そのときに躓いたことをまとめました.

主成分分析

名前は聞いたことる方が多いと思いますが,できるだけデータの情報を損失することなく新しい軸を作るための手法です.高次元ベクトルデータなどは現実に可視化することは不可能ですが,2次元や3次元ぐらいまでに落としてあげると可視化することが出来ますし,タスクに依っては低次元部分だけのデータで十分なこともあります.
outputよくある例ではこのような二次元データからoutput2このように第一主成分(青破線)と第二主成分(黒破線)を求めます.そうするとデータ間のユークリッド距離は,青線上で測った場合でも概ね元のデータの特徴を保持している,ということが言えます.PCAはscikit-learnに実装されているものを利用するか,自分で固有値分解をすると計算可能です.
x = np.linspace(-3, 3, n)
y = 2.5 * x + np.random.randn(n)

data = np.c_[x, y]
dim  = 1
pca  = sklearn.decomposition.PCA(dim)
result = pca.fit_transform(data)
print data.shape      # (n, 2)
print result.shape    # (n, 1)

完全に余談ですが固有ベクトル計算は縦に出てきます.
cov_data = np.cov(data)
[values, vectors] = scipy.linalg.eigh(cov_data)
sorted_ix = np.argsort(values)[::-1] # 昇順から降順へ(PCAの場合,大きい固有値に対応する固有ベクトルを使う)
values_sorted  = evs[sorted_ix]
vectors_sorted = evc[:,sorted_ix] # ←ココ!!

一週間このミスでハマりました.それはともかく,意外と大事です.データ全部ぶち込んで自動で上手く行けばいいですが,現実にはなかなかそうは上手くいきません.データをじっくり眺めるために敢えて基本的な手法に通してみるのも大事だと思います.

MDS

主成分分析と似たような形でデータを低次元空間で可視化できる手法は他にもたくさんあり,お手軽なものは多次元尺度構成法 – Wikipediaというものがあります(英語版の方が詳しい; Multidimensional scaling – Wikipedia, the free encyclopedia).MDSでは

  • 似ているデータ→近くに置く
  • 似ていないデータ→遠く置く
という凄い単純な原則に則った可視化を行ってくれます.関係パッケージはsklearn.manifoldにあります.同時にsklearn.metrics当たりを使うといい感じに使うことができます.もし距離を計算してある場合には,metrics関係のパッケージは使わなくて良いです.

# 距離行列が計算済み(http://www1.doshisha.ac.jp/~mjin/R/27/27.html)
lbls = ["Hyogo", "Wakayama", "Osaka", "Nara", "Shiga", "Kyoto"]
data = np.matrix([[0, 134,85, 116, 118, 60],
                  [134, 0, 68, 66, 145, 141],
                  [85, 68, 0, 32, 83, 75],
                  [116, 66, 32, 0, 79, 95],
                  [118, 145, 83, 79, 0, 63],
                  [60,141, 75, 95, 63, 0]])
mds = skm.MDS(n_components = 2, \
              dissimilarity='precomputed')
y = mds.fit_transform(data)

こんな図が生成されます.

mds

上のMDSが入っているmanifoldパッケージには他にも面白い手法がたくさん実装されていて,例えば非線形な次元圧縮手法で恐らく一番有名なIsomapが実装されています.いろいろ調べていましたが,結局全部scikit-learnのスタイルで実装されているので,使い方はMDSとだいたい同じです(パラメータを設定,fit, predict/transformをする.終わり).下で使います.

まとめ.scikit-learn内のメソッドはだいたい
  • fit()
  • fit_predict()
  • fit_transform()
といった関数を持っています.ですので何か試したい手法が会った場合,そのクラスコンストラクタに渡す必要があるパラメータをよく読み,fit/fit_predict/fit_transformなどを実行するとだいたい望んだ結果を得る事ができます.またndarrayを操作するとき,スライスや既に実装されているviewの取得方法を上手く使うことで,ムダな計算を省くことができるようです.

オマケ

せっかくなので小ネタとして使ってみます.データとしては今季最高のアニメとごく一部のクラスタで名高い,TVアニメ「結城友奈は勇者である」公式サイトのスペシャルからアイコンダウンロード(ここです→アイコンダウンロード | TVアニメ「結城友奈は勇者である」公式サイト)へ行って取ってきます.全部jpgファイルなので,前処理でpngに変換してあります.

wget ICON_URL_BASE{001..124}.jpg
for v in `ls`; do;
    convert $v ${v%.*}.png;
done;

numpy/scipyから画像を読み込む方法などについてはドキュメントがある(6. 画像の取扱い — 2012.ProgramingLanguage 0.1 documentation),それを利用してみようと思います.

yuyuyu1


PythonMachine Learning

円の方程式/人工データ作成/スペクトラムクラスタリング

よくある例題データみたいなのを使ってscikit-learn(sklearn)を使ってスペクトラムクラスタリングを(英語版Wikipedia)を試そうと思っていろいろやっていたのをメモしておく.

円の方程式

凄い当たり前だけど,半径rの円上の点を生成するには三角関数(cos/sin)を使えばいい.媒介変数とし角度θ(0≦θ≦2π)として,θの基準となる軸からθだけ回転した点の(x,y)座標は (r \cos(\theta), r \sin(\theta))

人工データの作成

適当に小さい円(r=1.5)と大きい円(r=3.0)に関して人工データを作成する.どうやって二次元ベクトルを作るかよく分からなかったのでnumpy.r_[X,Y]というベクトルをくっつけてくれるっぽい感じのメソッドをそのまま使った.媒介変数θは0から2πの間を適当に分割して作った.こういう昨日はMatlabと一緒でnumpy.linspaceがやってくれる.2つ作った店の集合(small/large)を縦にくっつけるのにnumpy.r_とは反対でnumpy.c_を使った.ついでに(標準)正規分布の乱数を適当に付けた(numpy.random.randn)
import numpy as np
import scipy as sp
import matplotlib.pyplot as plt
np.random.seed(0)

N = 500
theta = np.linspace(0, 2 * np.pi, N / 2)
r1, r2 = 1.5, 3.0
small = np.c_[r1 * np.cos(theta), r1 * np.sin(theta)]
large = np.c_[r2 * np.cos(theta), r2 * np.sin(theta)]
dataX = np.r_[small, large] + np.random.randn(N, 2) * 0.25

# plot
plt.figure()
plt.plot(dataX[:,0], dataX[:,1], 'bo')
plt.savefig("sample.png")

プロットするとよくある図みたいにこうなる.
sample

スペクトラムクラスタリング

スペクトラムクラスタリングに関してはリンク先が解説してくれている(スペクトラルクラスタリングの話 – おいしいお米の話).numpy/scipyだけではなく,ここからはscikit-learnを使う.スペクトラムクラスタリングに相当する機能はsklearn.clusterに納められているクラスタリング関係のパッケージ群の中に

  • SpectralClustering (クラス)
  • spectral_clustering (関数)
の2つが何故か用意されていて,関数で直接計算する場合とクラスにいろいろとパラメータを設定してfit→predictするという,いつものsklearn方式が使える,と思いきやfit_predictという関数に統合されているという謎な感じになっている.スペクトラムクラスタリングに必要な行列W(affinity matrix)をどう計算するかという問題があるけど,データをnumpy.ndarrayの形(例えば人工データのdataX)で入れると,クラスSpectralClustering自体が計算してくれる.パラメータを設定すると,事前に自分が計算した行列を使うことも可能.以下のように使う.

# spectral clustering by scikit-learn
from sklearn.cluster import SpectralClustering, spectral_clustering
sc = SpectralClustering(n_clusters = 2, eigen_solver='arpack', affinity = 'rbf', gamma = 10.0)
assigned_labels = sc.fit_predict(dataX)

assigned_labels(SpectralClustering#fit_predictの返り値)にはfitしたデータ(dataX)の各データ点がどのクラスタ番号に割り振られたか,というラベル情報が返ってくるので,それとnumpy.whereを使ってデータを分けることが可能.

plt.figure()
c1 = dataX[np.where(assigned_labels == 1)]
c0 = dataX[np.where(assigned_labels == 0)]
plt.plot(c1[:,0], c1[:,1], 'bo')
plt.plot(c0[:,0], c0[:,1], 'rx')
plt.savefig("clustered.png")

プロットするとよくある感じの結果が得られた.

clustered

Parabola JournalプログラミングMachine Learning

Subgroup DiscoveryとPython Orangeで遊んでいた

 
Machine Learning Advent Calendar 2013の一環で書いてます.動かしてみるつもりだったんですが,諸般の事情で動かなかったものもあったりして・・・.機械学習関係で比較的メジャーなタスクは分類と回帰だと思うのですが,RのEcdatパッケージに含まれているHousing data(data(Housing)で使う)を線形回帰してみます.

入力
output

出力(回帰直線を重ねたもの)
output_line

わーい嬉しい.まぁ細かいところを見てみたらこのデータに線形回帰を突っ込むのがそもそもどうなのか,という問題はありますが,別に2次の項を入れた曲線で近似したところでどうこうなる問題でもないでしょう.そこで,結局横軸(x: lotsize)と縦軸(y: price)がダメなんでしょ?という話を考えたい.いえ,別に積極的に考えたくはないのですが.あと問題にもよりますが.

なんとなく線形回帰ダメっぽいという話からすると,このグラフ(軸のとり方)がそもそもあかんのや,という話を考えるしかないでしょう.別にどこかの特徴空間に写像してもらって,うまく回帰するならそれはそれでもちろんいいですけどね,そのあたりはよく分かりません.Housingデータはもともと,price, lotsize, bedrooms, bathrms, stories(謎), driveway, … と他にも属性ありますので,そのあたりもコミコミで計算したらもっといい感じの回帰式にはなると思います(何がいい回帰式なのか,はとりあえず考えない).

  1. とりあえずデータがあります(離散値,整数値,カテゴリ値,二値,etc.で構成される)
  2. なんか処理したい(←今ココ
という状況を思い浮かべていただきたいと思います.こういう状況になるとさすがにパッケージにぶち込んで\(^o^)/というわけにはいかないので,データの整形・特徴抽出・正規化などなどをやる必要があるかもしれません.結局データ事態が言うほどキレイでない,というのが問題なんですね.データの生成がそもそもi.i.d.でないとか,いろんなデータの種類が混じっているとか,要因はいろいろでしょうが,なかなか難しい.

全部ごちゃまぜのデータを扱うのももちろんそれはそれで良いのですが,出来ればなんかキレイなデータにしてから処理した方が,扱いやすくなります.例えば先にクラスタリング(何でもいいので,レコード間の距離か類似度を決めて,例えば階層クラスタリングにぶち込んでグループ分け,みたいなことする)などの手法をかけたデータの前処理を職人芸でやって,さらに機械学習の諸手法で大域モデルを学習すれば,そのグループの中での精度は高くなるでしょう,仮にただの線形回帰だとしても.

ここでようやく表題なのですが,Subgroup Discovery(日本語訳不明)というのはデータマイニングの諸手法の一つで,簡単に言えば,与えられたデータの中で特徴的な部分集合を発見してあげる手法の総称です.(教師あり学習+教師なし学習)/2みたいなポジションです.なんでかというと,目的変数(target; 決定木とかでも決めているあれ,いわゆる目標変数)を決めた上で,マイニングとルール生成と評価を繰り返していくからでしょうね.もちろんこういう手法だけでなく,RやPythonの可視化(Numpy/Scipy->Matplotlib), Wekaほげほげを利用して可視化しながらデータをよーく眺めるというのが,まず最初にやる作業となるとは思いますが,前処理にデータマイニング処理使ってもいいじゃないか.そこで今回はPythonのOrangeという環境でそれをやろうとしました,という話です.データマイナーを名乗るための道のりは長く険しいですね.

パッケージとしてはよく分かりませんが,Python Orange用(http://kt.ijs.si/petra_kralj/SubgroupDiscovery/),Rapid Miner用(http://kt.ijs.si/petra_kralj/SubgroupDiscovery/rm.html),R用(詳細未確認)(http://www.subgroup.cc/)をとりあえず見つけました.

特徴的な部分集合とはどういうことか

線形回帰の例を続けます.全体の回帰式Y_{\mathrm{Price},i} = A + B X_{\mathrm{lotsize}, i} + \varepsilon_iが得られているとします.次にやることは,ある部分集合D (つまり,subgroup)を検索します.この部分集合Dにおいて回帰式を学習すると,例えば別の回帰式Y_{D,\mathrm{Price},i} = A_D + B_D X_{\mathrm{lotsize}, i} + \varepsilon_iが得られるとします.もし,2つの例えば回帰直線の傾きが統計的に有意に異なるなら(つまり帰無仮説H_0\: B_D = B)をチェックする.もし有意に異なるなら,今見ている部分集合Dを,何らかの特徴によって全体と異なる部分だ,と見なす(´・ω・`)

部分集合の作り方: 簡単なイメージ

例えば離散値属性がある場合(性別: 男/女,年齢層:10代/20代/30代/…),これをそのまま条件としたサブグループというのを作ることができる.
  • サブグループ1: 男性
  • サブグループ2: 10代男性
  • サブグループ3: 10代男性既婚
ある条件が有意に異なるサブグループを発見した場合,さらに条件を加えて条件1∧条件2,条件1∧条件2∧条件3,…と頑張って条件を難しくしていく.この探索空間はデータベースの次元(属性数,か)が上がると当然のように手に負えなくなるので,近似的な探索(例えばグループを表現するルールの精度やカバー率を定義して,その値が大きいものから決められた個数だけ発展的に検索するなど.要するにビーム探索)をすることも.というか,基本的に全列挙は諦めていると思う.

上のHousingデータの属性pref_area(Yes/No二値)を例えば対象とすると,Yes(好ましい)とNo(好ましくない)という+/-がデータ中の各レコードに付いていると考えることができる.次にやるのは上で考えた空間の探索で,簡単な規則から難しい規則を生成して,空間を走査していく.

ある条件(ルール)が得られた時,ルールで表現されるレコードのうち,pref_areaが,例えばYesが75%以上であれば,そのルールを特徴的な部分を表現していると見なす.アイテム集合発見における出現割合(# of occurrences / The entire size of DB)みたいなもの.もちろんそういう評価の仕方だけでなく,いろんな評価があってもいいのだけど,空間内のルールと評価関数においてdownward-closure propertyが成立していた方が,探索は簡単になる.

必要なもの

真面目に考えると,Subgroup Discoveryを適用するには次のことを決める必要がある.
  • 何を対象として集合を分けるのか
  • 決定木作るときの対象属性と同じ.Subgroup Discoveryは基本的に1つの対象変数のみを扱う.2つ以上を同時に扱うような拡張は,一部でExceptional Model Miningと呼ばれる.
  • そのようにしてサブグループを表現するのか
  • 命題論理式,述語論理式,数値区間,その他いろいろを使う.定式化的には探索空間を効率的に検索するための精密化演算子が上手く定義出来,下で述べる基準について単調性が保証される方が望ましい.
  • サブグループ選択のための基準
  • ルールを評価するために使う.カバー率や頻度,エントロピーなど.
  • 探索をどのように効率化するか
  • いくら枝刈りを頑張っても全列挙はだいたいしんどいので近似探索手法も同時に使う.

Orangeで動かしてみる

Subgroup Discovery用のWidgetをインストールしたOrangeにデータをぶち込む
Orange_1

見たい場合はData Tableに通す
Orange_2

インストールしたSubgroup Discovery Widget群を使って
Orange_3

Subgroup Discoveryを動かすと
Orange_4

楽しい✌(‘ω’✌ )三✌(‘ω’)✌三( ✌’ω’)✌ここでは相関規則系のSubgroup Discovery手法を利用しているので,出てきているサブグループの記述もそういう形です.(条件→嬉しい✌(‘ω’✌ )三✌(‘ω’)✌三( ✌’ω’)✌)とりあえず家賃400(単位はポンド・・・か?)あたりでいいらしいです.
Orange_5

データマイナーへの道のりは長く険しいですねぇ(二度目).機械学習手法を用いるとき,自分のデータがどういうデータなのかに注意をはらって,楽しい学習ライフを送りましょうということで,ひとつ.

参考文献
  • F. Herrera et al. An overview on subgroup discovery: foundations and applications

参考リンク



Parabola JournalMachine Learning

グラフカーネルのメモ

 
Weisfeiler-Lehmanグラフカーネルについてのメモである.特に冒頭のグラフカーネルを俯瞰したイントロあたりを読んで面白かったので力尽きるまで読んだ.あと書いている人はカーネル法の研究者でもなければ,グラフに関した機械学習の研究者でもありませんので,気軽に読んでくださいね(これはいわゆる,マクドナルドで女子高生がXXメソッド).

  • N. Shervashidze et al., Weisfeiler-Lehman Graph Kernels, JMLR, vol. 12, pp. 2539-2561, 2011.

お約束: Preliminary

  • ラベル付きグラフG=(V, E, l),ラベルは自然数とする.
  • N(v)でvの近傍を表す.
  • Walk: edgeの列で,Path: 異なる節点を通るようなWalk(たぶん)
  • 部分木: サイクルを含まない部分グラフ
  • 部分木パターン: 同じ節点を含んでもいいように部分木の概念を拡張したもの(tree-walk)
  • 部分木パターンとは,ある節点からはじめて,その近傍を子に持つように作成した木のこと.しかし,開始地点になったノードも,再び木の下の方に出現する.
  • グラフ同型はラベルを込み込みにした定義とする


主なグラフカーネルの種類へのリンク: Link to Famous Classes of Graph Kernels

注意: 著者の一部変音記号?(アルファベットの上に付くあれ)を省略しました.

Walk Based Graph Kernels
  • H. Kashima, K. Tsuda, A. Inokuchi, Marginalized Kernels Between Labeled Graphs, In Proc. of ICML 2003.
  • T. Gärtner, P. A. Flach, S. Wrobel, On Graph Kernels: Hardness Results and Efficient Alternatives, In Proc. of COLT, 2003.
Path Based Graph Kernels
  • K. M. Borgwardt, H. P. Kriegel, Shortest Path Kernels on Graphs, In Proc. of ICDM 2005.
Limited-size Subgraph Based Graph Kernels
  • T. Horvath, T. Gärtner, S. Wrobel, Cyclic Pattern Kernels for Predictive Graph Mining, In Proc. of KDD 2004.
  • N. Shervashidze, S. V. N. Vishwanathan, T. Petri, K. Mehlhorn, K. M. Borgwardt., Efficient Graphlet Kernels for Large Graph Comparison, In Proc. of AIS, 2009. (GraphletsとはLimited-sizeなサブグラフのこと)
Subtree Patterns Based Graph Kernels
  • J. Ramon, T. Gärtner, Expressivity Versus Efficiency of Graph Kernels, Technical Report of Mining Graphs, Trees, and Sequences, 2003.
  • P. Mahe, J. P. Vert, Graph Kernels Based on Tree Patterns for Molecules, Machine Learning, 2009.

これらのグラフカーネル群の計算コストはいろいろ.

Weisfeiler-Lehman Test of Isomorpshimとは

Weisfeiler-Lehman Kernelの前に,元々Weisfeiler-Lehman Testというものがある.これはNP問題(合ってる?)であるグラフの同型性(同じ構造をしていること)を判定するために大昔の60年代にWeisfeilerとLehmanによって提案された手法である.基本的には,与えられた2つのグラフGとHが同型かどうかを判定するために,それぞれのラベルをひたすら計算し直すような反復を行なって,生成されたラベルの集合が同じものなら同型,そうでなければ同型ではないと返す.この手法は1次元のWeisfeiler-Lahman Testと呼ばれていて,もし同型であればだいたいの場合において正しく動作する,らしい.

基本的な4操作

1. ラベル集合の決定
GとHのすべてのノードvについて,自分自身のラベルl(v)と,その近傍のラベルL(v)={l(u)
u∈N(v)}を集めたもの(多重集合と見なす)を,そのノードのラベルとする.

2. ラベル集合の整列
GとHのすべてのノードvに付けられたラベルの多重集合をソートし,辞書順に小さい順番で並べる.

3. ラベルの圧縮
GとHにおいて今まで出てきていないラベル(まだ使われていない自然数)を付与することで,多重集合に新たな自然数を対応させる.

4. ラベルの付け替え
GとHのすべてのノードvについて,新しく圧縮して作ったラベルを付与する.

この動作を,初期に出現するラベル数|Σ|の半分(n=|Σ|/2)ほど繰り返しても,両方のグラフに新しく作られるラベルの集合が一致していれば,Weisfeiler-Lehman Test of Isomorphismは2つのグラフが(おそらく)同型である,と返し,そうでなければ2つのグラフは同型ではない,と返す.
(非常に簡単な例ながら,下に両方の例を作りました.)

動作例(同型である,と返す)


Wltest 01
2回(=|Σ|/2=4/2)繰り返しても,ラベルの集合は同じなので同型と出力する.

動作例(同型ではない,と返す)


Wltest 02
1回目の手順で,ラベル集合が異なるようになるため,同型ではないと返す.

Weisfeiler-Lehamn Graph Kernelとは

上のWL-Testでやっているラベルの付け替えを与えられたグラフに何度も適用すると,グラフの系列が出来る.もし同型(同じ構造)であれば,同じラベル集合を持つような系列になり,そうでなければラベルの系列も変化していく.このラベルの系列を利用して,WL-Kernelを定義する.

上の一連の操作(手順1~4)をi回繰り返したものをGiと書く.あるグラフGのh-Weisfeiler-Lehman系列を{G0,G1,…,Gh}とする.なお上の2つの例は節点の中にラベルを直接描いているため,この系列の正体は{(V,E,l0), (V,E,l1), …, (V,E,lh)}である.さて,ある既存のグラフカーネルをkとしたとき,Weisfeiler-Lehnman Graph Kernelとは,h-WL系列の各グラフ同士にカーネルを適用したものの和と定義する.

  • k_{WL}^{h,k}(G, H) = k(G0, H0) + k(G1, H1) + … + k(Gh, Hh)
  • よく分からない再生核ヒルベルト空間のお陰で,カーネルの和はカーネルなので,これはカーネル(?論文にはちゃんと定理として解説あります.)
  • 上にリストアップした既存のクラスのグラフカーネルを持ってきて,Weisfeiler-Lehaman Test of Isomorphismと融合したものが,Weisfeiler-Lehaman Grpah Kernelとなる.


おしまい.(論文にはWL-Graph Kernelの具体例が3つ+実験がある).

ところでWeisfeiler-Lehman Kernelというよりも,Weisfeiler-Lehman Test of Isomorphismの解説になってしまってどうしたものか….


あとがきと免責

何か間違っているところ等問題があれば@taki__taki__まで通知してください(修正します).あと勘違いなどしている可能性が高い部分もあるかもしれませんが,責任は負えません,ごめんなさい.

メモ

そのうち続き書く