>100 Views
July 12, 24
スライド概要
AI・機械学習を勉強したい学生たちが集まる、京都大学の自主ゼミサークルです。私たちのサークルに興味のある方はX(Twitter)をご覧ください!
節:動的計画法との整合性
GNN8.7
動的計画法は,シンプルな部分問題に分割し,その解を再利用して全体の解を求める
フィボナッチ数列を例に
普通に再帰で書く場合
def fibonacci(n):
if n <= 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
動的計画法の場合
def fibonacci(n):
fib = [1, 1]
for i in range(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
return fib[n]
メッセージ伝達型GNNは,動的計画法である
集約 (h(l)
(l)
= fθ,l+1
h(l+1)
v
v , {{hv ∣ u ∈ N (v)}})
前の層の中間表現を利用して,次の層の中間表現を計算している
ラベル伝播法(ランダムウォーク近似)も,動的計画法である
ラベル伝播法
一部の頂点に教師ラベルが付いており,ラベルが付いていない残りの頂点のラベルを予測したい
ラベル伝播法はランダムウォークで解釈可能
解fv は,頂点vからランダムウォークを始めて,初めて訪れた教師ラベル付き頂点のラベルが1である確率qv と一致する.
動的計画法で定式化
(l)
qv :=(頂点vからl 歩以内でラベル付き頂点を訪れる確率,初めて訪れたラベル付き頂点が正例である確率)と定義する
初期値は
(1, yv ) if v ∈ VL
q(0)
v ={
(0, 0.5) if v ∈ VU
漸化式は(v ∈ VU のとき)
(l+1)
qv,1
= ∑
u∈N (v)
(l+1)
qv,2
=
Wvu (l)
q
deg(v) u,1
1
Wvu (l) (l)
∑
qu,1 qu,2
(l+1)
deg(v)
qv,1 u∈N (v)
節:動的計画法との整合性
GNN8.7
1
法も,動的計画法である 単一始点最短経路問題 ある始点s ∈ V から任意の頂点v ∈ V までの最短経路長dv を求めたい Bellman-Ford法とは Bellman–Ford https://qiita.com/wakimiko/items/69b86627bea0e8fe29d5 漸化式で書くと 0 if v = s d(0) v ={ ∞ if v =s (l) d(l+1) = min (d(l) v v , min (du + Wvu )) u∈N (v) アルゴリズム整列性があると,GNNの学習効率が良い 機械学習モデルf とアルゴリズムgが次のような合成で表せて,各部分モデルfi が部分アルゴリズムgi を効率的に学習できるとき,ア ルゴリズム整列性があるという. f = fL ∘ fL−1 ∘ ⋯ ∘ f1 g = gL ∘ gL−1 ∘ ⋯ ∘ g1 つのモデルで複雑な手続きをEnd-to-Endで表現するのは難しい シンプルな部分アルゴリズムならモデル表現は比較的容易 ➡︎ 学習しやすい まずは単純なGNNを使用してみよう 「近傍の頂点を重視する」というシンプルな規則が制度向上に寄与することが多い やたら表現力の高いモデルを使っても,以下のような問題が生じる 過学習しやすい 計算量,メモリ消費量が大きい → 実装・保守のコスト高い 単純なモデルから始めよう SGC:単純グラフ畳み込み(3.2.4節[P.79~]) GAT:グラフ注意ネットワーク(3.2.2節[P.76~]) GIN:グラフ同型ネットワーク(3.2.3節[P.263~]) ただし,表現能力が重要となる場面もある グラフ頂点数が少なく,多くの対称性を持つグラフ ex)化合物グラフ より大きな表現力が必要 「近傍の頂点を重視する」規則があまり効かない 対処法 :表現力の高いモデルを使う 対処法 :乱択特徴量 学習データが非常に多い場合 近年の大規模学習の成功例のように,GNNでもうまく行くかも? 1 1 2 節:動的計画法との整合性 GNN8.7 2