mits58のメモ

メモ　参考にしないでください

A Simple Proof of the Universality of Invariant/Equivariant Graph Neural Networks

読んでいる（ちゃんと理解していない）

arxiv.org

Invariant や Equivariant とは？

まず、グラフ上の問題をグラフデータの組 (G_i, y_i) から、下記の仮説を探す問題と定義する。（機械学習的にこれは自然やんな）

h:\mathcal{G} \rightarrow \mathcal{Y}\ \mathrm{s.t.}\ h(G_i) \sim y_i

この時、\mathcal{Y} に当たる集合は色々考えられるが、 \mathbb{R} や、 \mathbb{R}^{(V(G))_k} を取り上げる。それぞれグラフ、ノードに対する問題に対応している。（毒性あるなら1とか、あるノード同士が同じコミュニティなら1とかそんなかんじ）

同型なグラフに対して違う形の入力（頂点順序を入れ替えて、同じように辺を張ったグラフとか）が与えられた時、違う値を返して来ると辛い気持ちになります。ということで、それぞれ対応する仮説 h に対し、「同型なグラフに対しては同じ値を返す性質」を定義します。それが、Invariant や Equivariant ってことらしい。

じゃあこの論文は何したの？

Tensorized Graph Neural Networks というモデル（表記ゆれしてるけどこっちが正しい？ちゃんと調べないとなぁ）が、先程の invariant や equivariant を持つ関数に対し universality を持つことを示しています。

気持ち？

Stone-Weierstrassの定理を用いて証明しているらしい。これはざっくり言ってしまうと、ある空間上に定められた連続関数が任意精度で一様に近似できるってことらしい。

で、対応する隣接行列のようなものが張る空間を考えて、それ上で編集距離を導入して、Stone-Weierstrassの定理を満たすことを示してるらしい。

 

雑感

  • Tensorized Graph Neural Networksについて調べないとなぁ
  • https://arxiv.org/abs/1905.04943 今年のNeurIPSやんワロタ（気になる論文リストにはぶちこんでた）
  • この論文を読んだモチベとして、「どんな h が学習できるの？」と思ったんだけど、同型なグラフに対して同じ値を返すならセーフだった
  • あと、グラフサイズ無限大に飛ばした時に無限大になる値なら学習できるみたいな話も聞いたけどそれなんだろ……ちゃんと証明読むとわかる？　いや、うーん……今やってはいけない（真顔）

深層学習の数理

明日から出張＆来週（？）〆切の原稿があるのに放置して下記を読んでいました……

www.slideshare.net

深層学習について最近色々な本を漁ってますがふんわりとした理解しかできていなくつらい。 あとスパース学習（Lasso）あんまりわからんので後で調べる

深層学習の理論的課題とは

表現能力

  • ニューラルネットは、ReLUとかSigmoidだったら万能性を有する（つまり、どんな関数でも近似できる）
  • Cybenkoの理論によると、関数がSigmoid的（つまり負の方向に行くと0、正の方向だと1みたいな関数）だと、任意の連続関数を近似できる
    • なんでかっていうと、Sigmoid関数はパラメタをうまく調節すると任意のStep関数を近似できる
    • 任意のStep関数を近似できると、うまくそれらの和や差を取ることで、cos、sinが近似できる
    • cos sin が近似できるとフーリエ変換ができる
    • という流れ（大雑把だけど）
  • Ridgelet変換のくだりはマジでわからんかった……任意の連続関数が、許容条件を満たす活性化関数の下でいい感じに書けることと、そのいい感じに書いた関数が3層NNで近似可能ということを言ってるのかなぁと（それこそ鈴木先生が書かれていた「Ridgelet変換で双対空間へ行き戻ってくる」という表現が正しそう）
  • Gaussian Kernelの万能性も気になる……（授業で適当に使ってみたけどなんでなんや）

まあここまでで3層NNで任意の連続関数が近似できるのわかった、けどなんで層が多いほうがいいん？ -> 深さに対して指数的に表現力が上昇するため

  • NNの表現力を、平面をどれだけの領域に分割できるかと捉える
  • すると、深さに対しては指数的に分割領域が増えて、隠れユニットに対しては多項式的に増える
  • Arora et al. 2018は読みたいなぁ（でも余裕なし）
  • カーネル法と深層学習は似ていて、カーネル法は1層目の学習は行わないけど、深層学習では1層目の学習も行う
  • つまり、深層学習は各層で逐次的にカーネル関数を学習しているといえる（らしい）
  • つよそう（こなみ）　ただ、論理をintuitiveにでも理解したい（あんまりわからんかった）

汎化能力

  • パラメタ数 >> サンプル数となるのはつらい（なんでかっていうとサンプルにぴったり合うモデルができてしまうので）
  • だけど、NNは訓練誤差が0になってからもテスト誤差が減少し続けるらしい
  • ふつう、モデルが複雑になると途中でoverfittingが起きてしまう
  • けど、ある一定のしきい値を超えると逆にvarianceが減っていく（らしい）（設定にもよるらしい）
  • 陰的正則化も聞いているかもしれないという話（活性化関数入ってるとあんまりわかってないらしい）

というか後半全然わからんかった……まじの関数解析が始まっていた

最適化能力

  • NNの目的関数は非凸なので、大域的最適解ではなく局所最適解や鞍点に陥る可能性がある
  • ただし、線形NNの場合、局所最適解は全て大域的最適解となる
    • 横幅を広くとれば大域的最適解が求められる（らしい）

というかこれもわかっていなくてダメでした

雑感

  • 結構数理的解析が行われているのかと思いきや、あまりわかってない部分も多々あるようで
  • 解析学と密接に関係していてちゃんと勉強しないとなぁという気持ちに（つらい）
  • 感覚で捉えたけど、また勉強し直したら読みたいスライドではある

Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

読んだ。

arxiv.org

NeurIPS 2018に通ってる。Intel LabとHKUSTの人だった（見たことない）（サーベイ力無し）

 

以下雑まとめ

  • 例にもれず組合せ最適化×GNNのお話
  • 着目してる問題は、Maximum Independent SetとMinimum Vertex CoverとMaximal CliqueとSAT
  • MIS以外の問題は、全部MISに落とし込めるのでMISだけを考える
  • GNNを使う理由としては、頂点が解に含まれる確率を予測して、探索木を展開していく際にうまく使いたいというモチベがあるから
  • まあこれはよしなにGNNを構成すれば可能（今回はGCN使ってる）
  • でも、4頂点のサイクルグラフ（あってる？）を考えると、２パターンのMIS解ある、こんな感じで１つのグラフにいろいろな解があるし、各頂点が常に全ての解に含まれるかといったらそうではない
  • 多様性を考慮しないとアカン、つらい……　ならM個の解それぞれに各頂点が含まれる確率を生成するようにすればよくね？　これは、いい感じにLoss関数とかを書き換えると可能になる
  • で、他のLocal SearchとかGraph Reductionテクを使った上で、この頂点が解に含まれるかベクトルをM個生成、これを使って確率が高い方からGreedyに使って行き、M個の解を生成
  • その中でいいのを取るというかんじ
  • 生成速度も早くて、生成される解の品質もSoTAなMIS Solverと変わらなくてよかった（完）

以下雑感

  • これめちゃくちゃ頭いい、プロか？（プロだが）
  • というかGCNの部分を他のモデルに変えるだけでも十分性能上がりそう〜〜〜
  • でもなんでMISに落とし込んでるんだろう？　単純にMVCでもMCでもいけるじゃん？（Graph ReductionとかLocal Searchとか使いたいから？）（それは似たようなものがあるじゃん？）
  • MISは実質Polyタイム（よしなにBranch Ruleを定めると実測値めちゃはやらしい）とか言われてるくらいだし、他の分野で競うのが良さそうなのになぁ……
  • Message Passingでうまく抽出できる構造って、密な部分構造（クリークっぽいの）だと思うんだけどどうなんだろ？
  • だからMaximal Cliqueはいい感じの結果でそうなんだけど、筆者は検証してない？なんで？（悪いから？）
  • あと、学習にかかったのが16時間くらいで思ったより短かった（そんなもん？）

 

近いうち木幅のまともな記事を書きます（）

Approximation Ratios of Graph Neural Networks for Combinatorial Problems

arXiv

読んだ。以下メモ

結局何したん？

  • GNN って Distributed Local Algorithm と関連してるよね
  • なので、Distributed Local Algorithm の理論使って GNN がどれくらいの近似解を算出できるかを解析したよ
  • んで、理論的に一番な GNN である CPNGNN を提案したよ

 

  • Distributed Local Algorithm は GNN の Aggregation っぽいことを行ってグラフ上の組合せ最適化を解くアルゴリズム
  • なので、Distributed Local Algorithm と GNN で解ける問題クラスが同じだよってことを示して解析してる
  • 今回 Input Graph の最大次数を Δ で固定する仮定を置いて解析してる（よくある仮定らしい）

じゃあ、今回の GNN の売りポイントって何っていうと

  • Message Passing において、ノードごとに渡すメッセージを変えている
  • Aggregate した後の各要素を Concatenate する（普通 sum とか max とか ave とっちゃう）

ってところ。でも2つ目は最大次数の仮定がないとできないよね……

ノードごとに渡すメッセージを変える部分は Port numbering と呼ばれるテクニックを用いているらしい。

で、finding single leaf problem って問題に対して適用してみたら GCN とかじゃ溶けなかったけど CPNGNN だとできたよ。

 

コメント

  • 実際に学習してみたらどうなったんだろう…… Empirical な解析がなかった
  • 結構最大次数を Bound する仮定が効いてそう……とは思いました

 

Preferred Networks さんにインターンシップに行きました

Preferred Networks さんにインターンシップに行きました。

何をしたかは下記へどうぞ。

 

簡単に言うと、グラフの計算が難しい統計量である「木幅」を、グラフニューラルネットワークで予測してみようというタスクに取り組みました。

自分がﾃﾞｨｰﾌﾟﾗｰﾆﾝｸﾞﾅﾆﾓﾜｶﾗﾅｲ……のと、夏休み中という短い期間だったので、大した成果はないです……（つらい）

 

ということでリサーチブログでは書かなかった諸々を書き連ねます。

選考について

  • 今思い返しても受かった理由が、「メンターさんの興味とかぶった」以外にわからない……（本当に拾っていただきありがとうございます……）
  • 面接でも上手く喋れず、コーディング課題もそこまでできたというわけじゃないですが、インターンでやりたいことは結構明確に書いた記憶があります。
  • なので、来年以降受ける皆さんは、テーマはメンターと相談して決める……というより、自分からメンターを引き寄せる（！？）つもりで行くといいと思います

労働環境とか待遇とか

  • 大手町は昼飯が高いです。「食堂のかけそば（230 yen）」みたいなのは存在しないと思ってください……　僕自身3000円弱のランチを一度食べてしまいました（極厚ローストビーフでした……美味しかった）
  • 英語ができないとちょっとつらい思いをします（僕はしました）なので、受かってからで良いので英語になれておくといいと思います。
  • あと計算資源が潤沢でした……羨ましい……

今回の研究について

  • 自分としては、Chainer を使って疎行列演算を用いたグラフ畳み込みを実装できたのは良かったです。Chainer-Chemistry の実装は密行列形式で隣接行列を持っているため、実グラフデータに対して不適だよなぁと思っていました。
  • ただ、Max 演算でクソデカ行列くんを生成してしまうので、そこはつらいなぁ…… （Scatter 演算の実装はよ）
  • 後、手法1として提案した、「分類モデルによる誘導部分構造における部分問題に対する解の分類結果を用いた枝刈り」は汎用性が高いと思っています。

 

ということで、2ヶ月弱ほどありがとうございました！

 

 

 

「埋蔵分子」発掘プロジェクト―化学反応経路マップのインタラクティブ可視化に向けて

evernote に埋もれている論文メモをはてなブログへ移行しています。

   

2.分子構造と化学反応経路の探索

2.1トポロジカルな分子構造の数え上げ

  • トポロジカル法:原子と結合のトポロジカルな関係に基づき数学的に列挙する方法。A. Kerber, R. Laneらによるもの→速い、原子価を満たすもののみ、分子構造が平面

2.2量子化学に基づく分子・反応経路探索

  • PES上の極小点と鞍点を結ぶ反応経路を探索
    • 分子構造とその合成方法を得る数え上げ法:ポテンシャル法
    • Scaled Hypersphere Searchという手法により自動的に探索が可能になった
  • Global Reaction Route Mapに実装されている
  • ポテンシャル曲面を超球面探索法により網羅的に探索するらしい
  • トポロジカル法と比べて色々な構造が列挙できるよ

2.3「埋蔵分子」発掘プロジェクト

  • GRRMをつかって反応経路の網羅的探索とリポジトリ化を行う
    • 化学情報資源を整備するプロジェクト
  • 効率良い検索しすてむがほしい

3化学者による化学反応経路マップの解析

3.1GRRMからの出力:化学反応経路マップ

  • GRRMから、幾何学情報と物理化学的パラメータが得られる
    • 幾何学情報→分子構造(原子の種類と三次元座標値)     - 物理化学的パラメータ→ポテンシャルエネルギーなど
  • EQ:PES上の極小点　安定な分子構造のこと
  • TS:2つのEQを結ぶ化学反応経路上の最もポテンシャルエネルギーの高い地点　遷移状態
  • DC:1つの分子構造が分解し、2つ以上の分子構造へと変化するときの分離した状態のこと　解離チャネル
  • GRRMは複数のEQ、TS、DCをノードとしてもつ
  • 1つの組成式から得られるネットワーク全体を化学反応経路マップという  

    3.2化学反応解析の基本要件

    注目する属性
    • 分子構造 EQ、TS、DCの構造情報は基本的な属性、平面構造から立体構造まである、化学反応経路を経る過程で分子構造がどのように変化していくかを示す動画も重要らしい
    • EQのポテンシャルエネルギー 分子の内部エネルギー、その化合物がどの程度安定に存在しうるかを示す指標＝値が低いほど現実に多く存在しうる可能性高い。逆にこれが高い化合物は高い反応性を持つ＝反応設計のキー反応物となるポテンシャルをもつ。必須の基本的な物理化学的数値データ
    • TSのポテンシャルエネルギー あるEQが別のEQに変化するためにはエネルギーの壁を超える必要あり＝活性化エネルギー 活性化エネルギー＝TSのポテンシャルエネルギーと反応物のポテンシャルエネルギーの差分で表される 1つのEQ構造が複数のEQ構造へ変化する複数の経路が存在するとき→最も低い活性化エネルギーを経る反応が最も起こりやすい
    • 化学反応ステップ数 EQを結ぶ複数の反応経路の解析をするとき→いくつのEQ構造を経ているかの情報＝反応ステップ数も大事な情報→よりステップ数の少ない反応経路の方が効率的な合成となる  
  • 反応物を指定した検索 興味のある反応物から出発した検索と各ノードの詳細情報の解析を行う 出発点となる反応物を決める基準
  • 分子構造、ポテンシャルエネルギー値 出発点が反応物→反応予測、生成物→化学合成設計  
  • 反応物と生成物を指定した検索 2つのノードを指定→その間を結ぶ全ての化学反応経路の探索と各ノードの詳細情報の解析を行う →全てのパスのうち、より低い遷移状態を経るものが実際に起こりやすい＋反応ステップ数が少ないものが有望な化学反応経路  

    4化学反応経路の可視化

  • ボール＆スティック表示と呼ばれる分子モデル図がある→重要な可視化
  • 最もポテンシャル      

    コメント

    ・埋蔵分子の合成方法を得るためにも反応経路ネットワーク解析したいって気持ちになりますね ・GRRMってすごいんや(べた褒めされてるし) ・DCっていう構造もあるのね(あんまりよくわかってないけど) ・3-2あたりはためになった ・結局活性化エネルギーとステップ数が解析の上で重要そう    

Revisiting Graph Neural Networks: All We Have is Low-Pass Filters

arXiv

ちょっと気になりばーっと読んだ。

これはなに？

Graph Convolution って、実はグラフ信号処理における Low-Pass Filter と同じやんけ！なので、単純にグラフ信号に対して Low-Pass Filter かけたやつを MLP で学習させたら GCN と同じくらいになって、人工データだと勝ったよん。

  • まず、既存のデータセットの特徴ベクトルは、低周波の真の特徴ベクトルにノイズを加えたものになっているんじゃないかって仮説を検証している
  • 実際、グラフフーリエ変換とかで確かめてみたら、だいたい下位20%の周波数の特徴要素で十分な精度が出てるし、それより多くすると精度が下がっちゃった
  • で、次に Graph Convolution でよくやる Adjacency Matrix を掛けるって演算は Low Pass Filtering と同じだよってことを、グラフ信号処理におけるグラフフィルタを使って示してる
  • そして、単純に Filter かけたやつと GCN や SGC に対し精度の保証を与えて実験して確認してる

コメント

  • Adjacency Matrix を掛けるってのは Sum Pooling とか Average Pooling と同じなんだけど、Max Pooling ではないんだよね……そこってどうなるんやろ
  • 後これ多層 GNN への拡張してないのでそことか考えてみるとまた違う？ でもこれも、Low-Pass Filter の重ねがけみたいな感じになるんやろか……うーん
  • 逆に Graph Convolution は任意の Low-Pass Filter を近似できるってことになるんかな？