JOI 2018/2019 春合宿 講義３「グラフ機械学習」
（個人用のメモにつき解読不能です）
機械学習の基本
たくさんのデータが与えられ，データから規則を見つけ，その規則を使って新しいデータについて予想する
２番目を自動的に行うのが機械学習
分類問題の例：迷惑メール分類
迷惑メールとそうでないメールの例が事前にたくさん与えられる
ナイーブベースというものでけっこう精度がよい
分類問題の例：絵画分類
新造形主義の現代芸術か，印象派の風景画かを分別
IOI 2013 Art Class の一部
分類問題の例：化合物分類
化合物が頂点と辺にラベルの付いたグラフで与えられ，有毒か無毒か分類
ただし，両者のグラフの例が事前にたくさん与えられる
簡単な問題：アヤメの品種の分類
アヤメのがくの長さと花弁の長さが与えられ，Setosa か Virginica か分類
２つの値でプロットしてみる
花弁の長さで分類すればよさそう
目で判断するのではなく，どういう線をひくかを自動的に見つけるのが機械学習
直線を引くことを考える（線形モデル）
二次元の直線 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：同じなら１，違うなら０をとる
K(x, y) = 1 (x = y のとき), 0 (otherwise)
どんなデータでも使える
別のカーネルと作るための構成要素になることがある
K(x, y) = exp(-β * |x - y|^2)（βは適当な定数，x, y はベクトル）
距離が大きくなるほど小さくなる
正規分布っぽい雰囲気がある
対応する特徴量φは無限次元
真面目に特徴量を計算してられない
自然言語（迷惑メール分類など）や DNA 配列など様々な応用
- ２つ文字列があたえられるので，類似度を計算してください
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 の末尾に文字ｘを追加したとき，増分は t の x の各出現 z を最後とする長さ p の部分列
グラフカーネル
- ２つグラフが与えられるので類似度を計算して下さい
頂点と辺にラベルの付いたグラフを考える
か動物分類などの応用を念頭に置いておくと分かりやすい
頂点には C, O, H などのラベル
辺には１重結合，２重結合などのラベル
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関係
各ユーザーについて性別・年齢などの特徴量が与えられる
一部のユーザーについて，アンケートにより猫好きか犬好きかが分かっている
他のユーザーについて，猫好きか犬好きか
案１：グラフは捨てて特徴から分類するニューラルネットワークを使う
→ グラフの情報を捨てるのはもったいない
ほしい性質１：グラフをいい感じに使いたい
案２：グラフは隣接行列で表現できるので，これをニューラルネットワークに入れる
→ ノードに順番をつけなきゃいけない，表現の仕方が O(n!)
適当に番号づけすると予測結果が異なってくるかも
ほしい性質２：どんな番号付けでも同じ予測結果を返してほしい
ほしい性質３：勾配法で最適化したいので，微分可能であってほしい
現状ではこれを雑に解決する
これら３つのほしい性質が満たされてればOK
GraphSAGE-GCN の定義
「隣接ノードの特徴量を線形変換して平均する」と非線形変換を繰り返す
これを勾配法で最適化
ニューラルネットワークに似ている
