[2019/05/29] Machine Learning 輪講

[agatan]

Why

Machine Learning 輪講は最新の技術や論文を追うことで、エンジニアが「技術で解決できること」のレベルをあげていくことを目的にした会です。

prev. #2

What

話したいことがある人はここにコメントしましょう！ 面白いものを見つけた時点でとりあえず話すという宣言だけでもしましょう！

[agatan]

Structured Domain Randomization: Bridging the Reality Gap by Context-Aware Synthetic Data

• https://arxiv.org/abs/1810.10093

Synthetic Data で良い Object Detector を学習するために頑張る話。

• Global Parameter → Context Parameter → Object Placement の順番でパラメータを決定していく。
  • ひたすらルールベースでパラメータを定義していく（N 個の vehicles, M 本の道, X 番目のテクスチャ, ...)
• Unreal Engine 4 でレンダリング
• KITTI データセットで評価
  • 別ドメインのリアルデータセットで学習するよりも SDR の方が良い結果が得られた

[agatan]

• https://arxiv.org/abs/1810.05997
• ICLR 2019

semi-supervised node classification のために PageRank と GNN を組み合わせようという話。 （グラフ中の一部ノードにのみラベルが与えられているとき、全ノードを正しく classification したい。というタスク）

概要

• なるべくたくさんの近隣ノードを考慮できると嬉しいはず。（特にラベルがものすごく sparse な場合）
• GCN の層を単純に増やすだけではうまくいかない
  • 層を増やすと PageRank に近い分布で propagate されることになる
  • PageRank は Graph 全体に対して定まる property なので、ノード単位の classification に活用しても良くならない
• Personalized PageRank を用いることで、うまく近隣ノードから propagate してくることができた (PPNP)
• Personalized PageRank は O(n^2) なので計算量がつらい。Topic-Sensitive PageRank で近似することで精度を保ちつつ計算量を抑えることができた （APPNP）

GCN の問題点

Graph Convolutional Network (GCN) は以下のような式で定義される（2 層の場合）。

ここで、 A は normalize された隣接行列, X は feature matrix, W はパラメータ。 直感的には、一層ごとに自身の feature と隣接ノードの feature の平均を取るようなイメージ。

問題は

• 2 層の場合、2 hop 先までしか考慮できない
  • 2 hop 以内にラベルがついたノードがないとうまく学習に寄与できない
• 平均をとっていくため、層を多数重ねた場合に「より近いノードに集中する」ことができなくなる
• 「遠くのノードを考慮する = 層を増やす = パラメータが増える」
  • 「どこまで見るか」と「ネットワークの層 / サイズ」は直行する概念のはず。分離したい。

Personalized PageRank の活用

GCN の層を増やしていくと、propagate の分布は PageRank に似た分布に近づいていく。 PageRank は

を無限 step 計算したときの \pi で、

• 確率 1 - α で今いるノードからランダムなエッジをたどる
• 確率 α で全ノードからランダムに選んでテレポート

を無限 step 繰り返したときの分布と一致する。 (GCN との違いは self loop の扱いと normalize の有無だけ。)

が、PageRank は Graph 全体に対するプロパティであり、各ノードに focus したものではない。 そこで Personalized PageRank を使うというアイディアが出てくる。

x は root node, i_x は teleport vector (personalize vector) でここでは [0, 0, ..., 1, 0, ...] のように「自分自身が 1, それ以外は 0」であるような要素 n のベクトル。 Personalized PageRank は「確率 1 - α でランダムウォーク、確率 α で自分自身に戻る」を無限に繰り返したときの分布。 全ノードから見た Personalized PageRank を計算する必要があるので大変。

Personalized propagation of neural predictions (PPNP)

ノードを別個で predict する Network に通した後、周辺にその結果を propagate する PPNP を提案している。

Approximate personalized propagation of neural predictions (APPNP)

PPNP は Personalized PageRank を使っているが、全ノードごとに Personalized PageRank を作ると NxN の Dense Matrix を作る必要があるし時間計算量も N^2 でかかってくる。

そこで、topic-sensitive PageRank を活用することで近似しつつ計算量を落とす。 topic-sensitive PageRank は、topic ごとに teleport vector が定義されるような PageRank。 今回の場合は、クラス = Topic とみなして topic-sensitive PageRank を計算する。

K step の power iteration で近似する。（収束したかどうかは見ない。常に固定回数）

評価

State of the Art の精度を出している。 PubMed などはグラフが大きいので PPNP は計算できない。が、APPNP は計算可能で性能もよかった。

学習時間はシンプルな GCN よりは遅いが、GAT などよりは速い。

APPNP の power iteration 数と精度の分析。 最適な K は、max(ラベルのあるノードとの shortest path distance for node in all nodes) と大体同じになっているらしい。

「propagate をどのタイミングで活用するか」についての分析。 propagate しない、training 時のみ、inference 時のみ、両方、の 4 pattern ある。

• Inference 時のみでも大きな gain がある
  • なので、学習時は propagate せずサクッと学習するとか、学習済みモデルを持ってきて propagate するとかも可能。
• Train 時のみでも大きな gain がある
  • inductive な問題設定に対しても意味がある（学習時には存在しなかったノードや、だれともつながっていないノードに対しても効果がある）