人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

JOI 2018/2019 春合宿 講義3「グラフ機械学習」

(個人用のメモにつき解読不能です)

機械学習の基本

たくさんのデータが与えられ,データから規則を見つけ,その規則を使って新しいデータについて予想する

2番目を自動的に行うのが機械学習

 

分類問題の例:迷惑メール分類

迷惑メールとそうでないメールの例が事前にたくさん与えられる

ナイーブベースというものでけっこう精度がよい

 

分類問題の例:絵画分類

新造形主義の現代芸術か,印象派の風景画かを分別

IOI 2013 Art Class の一部

 

分類問題の例:化合物分類

化合物が頂点と辺にラベルの付いたグラフで与えられ,有毒か無毒か分類

ただし,両者のグラフの例が事前にたくさん与えられる

 

簡単な問題:アヤメの品種の分類

アヤメのがくの長さと花弁の長さが与えられ,Setosa か Virginica か分類

 

2つの値でプロットしてみる

花弁の長さで分類すればよさそう

 

目で判断するのではなく,どういう線をひくかを自動的に見つけるのが機械学習

 

直線を引くことを考える(線形モデル)

二次元の直線 ax + by + c = 0

がくの長さを x,花弁の長さを y として Setosa なら ax + by + c > 0,Virginica なら < 0 になるような a, b, c がほしい

 

単純な乱択解法

もっと効率よくしたい

 

失敗したら繰り返すを繰り返して,良い解に到達していく

失敗するのは t(ax + by + c) <= 0(t は 1, -1 のどちらか)ということ

 

α: 小さい正の定数(適当)

a' = a + αtx, b' … と更新する

修正すると t(a'x + b'y + c') > t(ax + by + c)

このアルゴリズムをパーセンプロトンという

 

パーセンプロトンの嬉しいところ

データが直線で完全に分離できるなら,有限回のループで必ず直線が得られる

 

絵画分類

256 x 256 の大きさとする

画像は 256 * 256 * 3 個の値で表現できる

196608 次元で同じことをやる…?

 

全部の値自体に大した意味はない,ある座標の色によって分類する推論はできない

データをもっと少ない特徴量で表現できればパーセンプロトンが使える

印象派は暗く,新造形主義は原色を多用してそう

 

データを特徴量に変換する関数φ

Φ1:RGB の合計,φ2:周りとの差 とおいて,値をプロット

 

特徴量抽出は非線形の関係を抽出できる

データの分離可能性を上げる効果もある

φ(x, y) = (x ^ 2, y ^ 2) という変換をすると直線で分類できたり

 

この直線をφ^-1 で元の空間に戻すと円で分類することにも対応

 

もっと強力なモデルも

多層パーセプトロン,サポートベクトルマシン,Convolutional Neural Networks

 

機械学習では何万次元にもなるベクトルをつかう

N 個の実数を並べたものを n 次元ベクトルとよぶ

高次元ベクトルについては std::vector みたいなもの

 

ベクトルの足し算,定数倍,内積,長さ,余弦定理

重要な事実:ベクトルが似ている(似た方向を向いている)とき内積が大きくなり,似ていない(違う方向を向いている)とき小さくなる

 

がくの長さ x,花弁の長さ y のアヤメを z = (x,y,1)  という三次元ベクトルであらわすと,

(z, w) > 0, (z, w) < 0 で分類できる(w = (a, b, c))

加算なども同様にベクトルで出来る

 

カーネルトリックとは特徴量そのものを設計しなくても,データが似ているかどうかの基準を設計すればモデルを訓練できるようになる

 

データ:x_1, x_2, …

対応するラベル t_1, t_2, …(1 か -1 をとる)

初期重みは全てゼロとする w_initial = (0, 0, 0, …)

重みは w = α*(失敗回数)* t *φ

 

t * (φ(x_i), w) <= 0 が失敗しているかの基準

更新は f_i をインクリメントする

もはや生のデータ x や特徴量φ(x_i) は使ってない

使ってるのは特徴量の内積(どれだけ似てるか)のみ

特徴量の内積カーネルという

 

失敗:(カーネルと足し合わせたもの)<=0

更新:f_i をインクリメント

特徴量の内積しか使わないのであれば,特徴量を設計するかわりに,最初からデータがどれほど似てるかを直接設計すればいい

カーネルトリックによって強力な特徴量が簡単に設計できる

 

カーネル(=データ類似度)さえかければモデルを学習できる

カーネルはどんな形式のデータに対しても設計しやすいことが多い

「二つの文字列が似てるか」などの方が簡単なことが多い

 

Identity Kernel:同じなら1,違うなら0をとる

K(x, y) = 1 (x = y のとき), 0 (otherwise)

どんなデータでも使える

別のカーネルと作るための構成要素になることがある

 

ガウスカーネル:ベクトル同士のカーネル

K(x, y) = exp(-β * |x - y|^2)(βは適当な定数,x, y はベクトル)

距離が大きくなるほど小さくなる

正規分布っぽい雰囲気がある

対応する特徴量φは無限次元

真面目に特徴量を計算してられない

 

ストリングカーネル:文字列に対するカーネル

自然言語(迷惑メール分類など)や DNA 配列など様々な応用

  1. 2つ文字列があたえられるので,類似度を計算してください

 

Spectrum Kernel

文字列 s, t の長さが p の部分文字列のうち,共通するものの個数

たくさん同じ部分文字列を持つほど文字列は似ていると考える

 

Gap-weighted String Kernel

部分文字列だけでなく部分列まで考える(意味は同じだが文字列が離れる場合がある)

ただし,文字列が離れれば離れるほど,意味のつながりは薄くなる

 

なので Gap に weight をつける

部分列が s で ls, t で lt 離れているとき c ^ (ls + lt)(c は 0.9 とか)だけカウントする

 

DP で計算できる

文字列が I ではじまり j で終わるとする

L = j - I + 1

S の末尾に文字xを追加したとき,増分は t の x の各出現 z を最後とする長さ p の部分列

 

グラフカーネル

  1. 2つグラフが与えられるので類似度を計算して下さい

 

頂点と辺にラベルの付いたグラフを考える

か動物分類などの応用を念頭に置いておくと分かりやすい

頂点には C, O, H などのラベル

辺には1重結合,2重結合などのラベル

 

Graphlet Kernel

グラフ G, H の大きさ p の連結部分グラフのうち,共通するものの個数

普通 p = 3, 4, 5 ぐらい

 

Random Walk Kernel

ぐらふ G, H のランダムウォークのラベルが一致する確率

スタート位置,遷移確率は等確率など

一定確率で止まる

一致確率ではなく,カーネルの期待値でもいい(一致のところで Identity Kernel を使える)

 

ランダムウォークは無限通りあるので愚直に計算は出来ない

とりあえず,長さ p のランダムウォークのみ考える

dp[p][u][v] : 長さが p のランダムウォークで,G では u にいて,H では v にいて,ラベルが一致している確率

連立方程式を解くときもある

 

MUTAG データセット:30 頂点くらいからなる化合物のデータセットで,化合物か変異原であるかを当てる

Random Walk Kernel + SVM を使うと 85 % あたる

 

クラスタリング

最初与えられるデータについても答えが分かっていないときもある

こういうときどういう風にクラスが分かれるのか知りたい

 

カーネルを元にグラフ G をつくる

G の最小カットを求める

異なるクラスタ間にはカーネルの値が大きい要素があまりない → 似ていない

普通は実数に緩和して解く

 

ニューラルネットワーク

微分を導入する

変数 f が変数 x によって決まっているとき,x をちょっと増加させたときの f の増え方を表すのが微分

f に対する x の影響力ともいえる

微分の正負で x をちょっと増加させたときの増加・減少を知れる

 

非連続な関数やギザギザの関数などは微分できない

 

微分の連鎖律(チェインルール):f が g によってきまっていて g が x によってきまっているとき,f は x に決まっているので,x による f の成分が計算できるはず

影響力は(g の f に対する影響力)*(x の f にたいする影響力)

 

購買法によるモデルの訓練

パラメータ w_1, w_2, … で表現できるモデルがある

モデルの良さを表す値(データに対してどれぐらい良い結果を返すかなど)L を設計する

(K / w_i) の微分を計算できれば,w_i += α(L / w)' とすれば,L はα((L / w)')^2 >= 0 ぐらいよくなる(αは正の定数)

(L / w_i)を求めて更新を繰り返すとモデルがよくなる

 

ただ,この微分を求めるのは大変 or 不可能

ニューラルネットワークでこの微分が DP で求まる

 

ニューラルネットワークパーセプトロンなどの線形モデルを多層にしたもの

線形変換と非線形変換を繰り返す(非線形変換は sigmoid 関数などを使う)

計算自体にあまり意味はない

謎の変形を繰り返し,謎の予測値を出す関数

層構造になっているので,出力側から順番に微分を計算できる (backpropagation)

 

持ってるデータ (x, t) について,ニューラルネットワークの出力 y が t に近くなるようにしたい

例:L=1/2 * Σ(i=1~N) (t_i - y_i)^2 を最小化する

勾配法で最小化するために (L / 重み)' を求めていく

 

(L / y)' は簡単,y を t に近づけると良くなって,遠ざけると悪くなる

 

バックプロぱげーしょん

層の右側(y 側)から DP をすすめていく

一つ右の層への影響しか考えなくていい

 

ニューラルネットワークの嬉しいところ

非線形関数なので,直線以外で分類できる

Universal Approximation Theorem: ニューラルネットワークは任意の関数を,緩い仮定の下,中間層を増やすことで任意の精度で近似できる

複雑な関数をモデル化できるので,データがたくさんあれば,特徴量抽出をせずに生のデータを入れてもうまくいくことがある

 

ディープラーニングライブラリの自動微分

Chainer:ニューラルネットワークに関するいろんなことをやってくれる

ディープラーニング用のライブラリがたくさんある (TensorFlow, Chainer, PyTorch,…)

微分を自動で計算してくれる

 

問題に合わせてニューラルネットワークのパラメータ数や非線形関数を設計したりする

特徴量抽出やカーネルをする必要がなくなりやることは少なくなっている

 

グラフニューラルネットワーク (GNN)

文字列やグラフなどは固定長配列であらわせないデータ

特徴量抽出は大変,カーネルの議論はニューラルネットワークでは使えない

グラフ用のニューラルネットワークがいくつか考案されている:GraphSAGE

文字列は RNN, LSTM などを使ってできる

 

グラフニューラルネットワークはまだまだ発展途上

最初に考案されたのは 2016 年,GraphSAGE は 2017 年

 

ノード分類を考える

Twitterのフォロー・フォロワー関係の向こうぐらふ

頂点はユーザー,辺はFF関係

各ユーザーについて性別・年齢などの特徴量が与えられる

一部のユーザーについて,アンケートにより猫好きか犬好きかが分かっている

他のユーザーについて,猫好きか犬好きか

 

案1:グラフは捨てて特徴から分類するニューラルネットワークを使う

→ グラフの情報を捨てるのはもったいない

ほしい性質1:グラフをいい感じに使いたい

 

案2:グラフは隣接行列で表現できるので,これをニューラルネットワークに入れる

→ ノードに順番をつけなきゃいけない,表現の仕方が O(n!)

適当に番号づけすると予測結果が異なってくるかも

ほしい性質2:どんな番号付けでも同じ予測結果を返してほしい

 

ほしい性質3:勾配法で最適化したいので,微分可能であってほしい

現状ではこれを雑に解決する

これら3つのほしい性質が満たされてればOK

 

GraphSAGE-GCN の定義

「隣接ノードの特徴量を線形変換して平均する」と非線形変換を繰り返す

これを勾配法で最適化

ニューラルネットワークに似ている