807 Views
May 09, 24
スライド概要
AI・機械学習を勉強したい学生たちが集まる、京都大学の自主ゼミサークルです。私たちのサークルに興味のある方はX(Twitter)をご覧ください!
2024前期輪読会#2 グラフニューラルネットワーク 2-1,2 京都大学工学部 木村優汰 0
グラフニューラルネットワーク 目次 1. ニューラルネットワーク 2. グラフ理論 1
2.1 ニューラルネットワーク 2
2.1.1 機械学習モデルの訓練と推論 機械学習モデル:fθで表す。(θがパラメータ) (ニューラルネットワークは機械学習モデルの種類) 推論(inference):入力xに対して出力fθ(x)を求める操作 訓練(training):適切なパラメータθを探す操作(=損失関数を小さくする操作) 訓練→推論 損失関数の最小化=精度の良いモデルの作成 損失関数を最小化するアルゴリズム:最適化アルゴリズム (SGD,Adam,etc) 3
2.1.2 多層パーセプトロン x1 y1 :活性化関数σ、x:入力 x2 z1 ・入出力ともにベクトル ・以下の式で定義 f(x) = σ(Wσ(Wσ(…Wσ(W(x)…)) W:重みを要素とする行列 ・繰り返し単位:層 ・線形変換と非線形変換を交互に行うモデル 4
2.1.3 畳み込みニューラルネットワーク 入力データ フィルタ 出力データ (3次元の畳み込み演算) 畳み込み層:以下の式で定義 (xは三階のテンソルとする) = (h:画像の高さ,w:幅,c:チャンネル数) W:フィルタ(カーネル) 5
2.1.3 畳み込みニューラルネットワーク 畳み込みニューラルネットワークの構造 入力 データ 入力 層 畳み込 み層 ブーリン グ層 全結合 入力層:特徴マップの作製 ブーリング層:特徴マップのサイズを小さくする 6
2.1.4 誤差逆伝播法と一気通貫学習 誤差逆伝播法:誤差の勾配を計算するアルゴリズム (勾配:パラメータの最適化に用いた) 利点:数値微分よりも効率的、精度が高い 計算コスト(一度の計算で求まる)、実装の容易性 一気通貫学習:中間ステップを挟まずに入力から望ましい出力を 一気に得る機械学習の手法 利点:ステップごとの個別の最適化よりも効率的 中間表現の必要性がないのでモデルがシンプルに表せる 7
2.2 グラフ理論 8
2.2.1 グラフの定義 V = {1,2,3,4,5} 2 E = {{1,2},{1,3},{2,3},{2,4},{2,5} 3 G = (V,E) 5 グラフとは? → 頂点(ノード)と辺(エッジ)で構成される データ構造のこと 1 4 グラフGは頂点集合Vと辺集合Eで定義 *辺{u,v}のうちu=vの場合の辺を自己ループという 9
2.2.2,3 近傍、次数 頂点vの近傍(neighborhood):vと辺を共有する頂点、N(v)で書く vとuが近傍=uはvに隣接している 例えば、N(2) = {1,3,4,5} 頂点vの次数(degree):vに隣接する頂点の数,deg(v)で書く 例えば、deg(2)=4 次数行列:各頂点vについてdeg(v)を対角成分に並べた対角行列 Diag(deg(1),…,Deg(n)) 10
2.2.4 部分グラフ 部分グラフ:グラフの一部を取り出したグラフ G=(V,E)について、V’ V,E’ E,G’=(V’,E’)なるG’:部分グラフ 誘導部分グラフ:EのうちV’に属する頂点間の辺をすべて含む 部分グラフ 4 1 G 1 1 2 2 3 3 2 3 5 11
2.2.5 ウォークとパス ウォーク:辺をたどって作成した頂点の列 ex){1,3,1,2,4,2,5},{2,4,2,5,2,1,3} パス:頂点の重複がないウォークのこと ex){1,3,2,5} 12
2.2.6 連結性 連結グラフ:パスによってすべての頂点間を行き来できるグラフ 非連結グラフ:連結でないグラフ 連結成分:極大な連結部分グラフ 13
2.2.7 隣接行列と接続行列 隣接行列:各頂点間が辺で結ばれている時1それ以外の時0の行列 頂点同士の接続関係を表す 最短経路問題 接続行列:頂点iと辺jが接続している時1それ以外の時0の行列 頂点と辺の接続関係を表す グラフの辺の数 これらはグラフの行列による表現方法 14
2.2.8 重み付きグラフ 各辺が実数値を持つようなグラフ G = (V,E,w) w:辺に重みを与える関数 で定義 重み付き隣接行列(1の代わりに重みを要素とする行列)で表現 類似度行列との同一視 次数:近傍の重みの和 15
2.2.9 有向グラフ 有向グラフ:辺に向きをつけたグラフ (向きなし→無向グラフ) 無向グラフを一般化したグラフ Ex)Webページのリンク構造、交通ネットワーク 本書では基本無向グラフで考える 16
2.2.10 同類選好的グラフと異類選好的グラフ 同類選好:似た者同士が辺でつながる可能性が高い 異類選好:異なる者同士が辺でつながる可能性が高い 同類選好→ソーシャルネットワーク (コミュニティの形成) 異類選好→映画関係者同士のつながり 17
18
19