NLP/CV最先端勉強会」が開催されました。様々な分野の最先端の研究成果をサーベイする本勉強会。今回は、グラフと対話応答のサーベイチーム報告会と、CVPR2019速報を行いました。Applications」に登壇したのは、内橋堅志氏。Completion、CV、NLPなど、応用タスクをサーベイしました。だいたい120本くらい読んで、30本の重要論文と70本の関連論文にまとめたのですが、今回は発表用の縮小版です。自己紹介させてください。僕は内橋堅志と申しまして、xpaper.challengeの運営をしています。フリーランスの機械学習エンジニアとリサーチャーで、いろいろなお仕事やらせてもらっています。Twitterは「uchi_k」という名前でやってるので、よかったら見てみてください。Scholarに突っ込んで、論文見ていって。論文のリストを作って、重要そうな論文を探していきます。重要論文の選定なんですが、2018年より以前だと、引用数でだいたい評価が定まってるんですよね。それを使って評価しました。2019年だとまだまだ引用数がついていないので、がんばって内容で評価する。あとは有名研究者が書いていたらちょっと優先して読む、みたいな感じで消化していってます。あとは有識者に「この論文どうですか」「最近なんかいいのありましたか」みたいなことを聞いてます。今はだいたい120~130本ぐらい読んでいる感じなんですが、カンファレンスの割合としてはNeurIPSが多いですね。あとはICLRが多いです。ICML、AAAIと続いていくのですが、やはり理論系のトップ会議に集中します。だいたいここまで挙げた会議で半分くらいかな、という感じです。これからグラフの論文で、例えばグラフニューラルネットワークスが多いんですがそういったものを書くとしたら、このあたりを狙って出すのかな、という感じです。あとは情報検索系の会議です。KDDやWWW、WISDOM、SIGIRもけっこうあります。Embeddingとか、リコメンデーション系のタスクは、こっちのほうが多いかなと。あとはarxivですね、2019年の論文はだいたいarxivでした。論文は最も貢献が大きいと思った分野に割り振りながら説明します。今回は前提とする知識が正直結構あります。一番はニューラルネットワークの基礎知識ですね。MLPだとかconvolution、pooling、CNN、RNN、LSTM、その他といったところです。あとはグラフの基礎用語です。だいたいは大丈夫だと思いますが、グラフラプラシアンとかはちょっとむずかしいというかアレなんですが、その辺を前提にしています。断りがなければループや多重エッジがないグラフを扱ってます。数式は追わないで、論文内で重要な数式があれば紹介しますし、図を見た方が早い場合はそれでやっちゃう、という感じでやらせてください。今日は30分で説明するのですが、結構な量を紹介したいと思うので、細かいところは紹介できません。一応、重要論文30本、関連論文70本にまとめようということでやっています。今見ていただいている資料では40ぐらいに減らしています。それでも終わるかわかりませんが、発表では基本、基礎的な内容に絞ってやっていきたいと思います。範囲が広いので説明不十分なところがあるかと思いますが、後日アップする資料で補完してもらえたらなと思います。Modelまずはグラフニューラルネットワークです。Model』という論文があって、これは2009年に出た論文です。グラフニューラルネットワークの一番最初みたいな感じですね。一応2005年ぐらいに出た論文もあるんですが、おそらくこちらのほうが引用されているし、ちゃんとした定式化されているという印象です。本当にシンプルで、ノードがメッセージを伝播していく仕組みでGNNを導出する、という感じですね。これを見てもらうと図がありますが、隣接ノードを見ています。自分のノードが持っているラベルと、隣接してるエッジ。エッジというのはこのノードを結ぶ線のことです。エッジのラベルと隣接しているノードの状態、あとは隣接ノードのラベルの4つを伝播していく、という仕組みです。最近傍ノードの情報も再帰的にaggregateし、1回1回集めていきます。1-hopなんですよね。隣のノードの情報しか取れないので。5回やると、毎回集めてるのは最近傍ですが、その最近傍のノードはさらにその最近傍のノードの情報を取ってくるので、k回やるとk-hopの情報が取れます。一応、あらかじめ決められたタイムステップで学習が終わるモデルです。問題点があって、まずこのやり方は、1回1回繰り返す毎にめちゃめちゃ薄まっていきます。遠くのノードの情報は取りにくいです。最初にできたやつなんでこんなものですね。グラフ構造もそのままニューラルネットに落とし込めるようになりました、というのが一番の貢献なのかなと思います。Graphs続いてそこから一気に5年経ちます。Connected」がありますね。この論文では2つの提案をしてるのですが、この論文でやっているのは、グラフにおける局所性と解像度を定義して、グラフに拡張する方法をSpatial、空間的な方法と、Spectral、周波数空間でやるという2種類を提案しました。LeCun先生が書いています。LeCun先生はCNNを作った人ということで、今回紹介してみました。2つあると言ったんですが、まずはSpatialなほうで説明していきます。「局所性と解像度を定義し」と言ったので、まずは隣接行列を使って局所性を定義します。これがすごく簡単で、正確に言うと重み付き隣接行列ですね。隣接行列って、ノードの数が例えばn個だとn×nの行列で、つながってるところに1が入ってる、みたいな感じです。重み付きだと、そのつながりにちょっと重みがかかっています。この重み付き隣接行列に対して、デルタでしきい値を適当に設定して、それより値が大きいところがつながってるとして、強くつながってるところだけを取ってくる、という操作で局所性を表現しています。1個が、マルチスケールクラスタリングです。これが解像度を表現しようとしているのですが、クラスタに含まれている全ノードの特徴量を入力にして、代表値として1つの特徴量を出力するというものです。入力ノードの集合がまずあったとして、それがクラスタリングされて、4つの点が凝縮されて代表点が取れています。これが、例えば6個のクラスタに順番に分けていくと。やっていくと、CNNで言う解像度みたいに見えます。いうことをやってますと。ここで軽く触れておきたいのが、CNNの特徴はこの局所性と解像度という、入力のサイズによらないフィルターですよね。poolingやサブサンプリングするというのもありますが。あとは重み共有があります。重み共有に関して、おそらくグラフで重み共有するのは難しいと思います。その理由はいろいろありますが、グラフって構造が場所によって全く違うので、共有した重みを定義しづらいんですね。完全にCNNに持ってくるのはハナから諦めている、とイメージしてもらえるといいかなと思います。時間がないのでポンポンいきます。k,i,j」という添字がありますが、これは隣接関係があるところだけを残すフィルターです。このフィルターってノード数がnとしたら、n×nなんですよ。n×nのフィルターなんですが、一応めっちゃスパースです。今回は局所性を定義しているので、それに従ってめっちゃスパースではあるんですが、n×nなんですよね。大きいフィルタをボーンとかけている、というのが下の式です。次に、Spectralな手法について説明します。先ほどのやつはわかりやすかったと思いますが、これは簡単に言うと、フーリエ変換したところで要素積をとって逆フーリエ変換しましょう、という話です。「グラフでフーリエ変換って何なの?」となるので、できるだけがんばって説明します。フーリエ変換というのは、波形を周波数成分に分解する。周波数成分がいっぱいでてきて、それに対して係数が付いていて、その足し合わせになりますよ、というものだと思います。これを踏まえて、グラフフーリエ変換とは何かということです。グラフ上で定義された信号があります。これはノードの特徴量と思ってください。それに対して信号の急峻さを定義して、その急峻さごとに成分分解するんですけど......。これは説明をパッとするの難しいのですが、今は納得してください。急峻さごとに成分分解するのがグラフフーリエ変換です。これはどうやってやるかというと、グラフラプラシアンの固有値計算をしたら、急峻さ成分への分解が可能です。これも納得してもらうしかないんですけど。domainで要素積になりますよ、という定理があります。要素積でconvolutionできるじゃん、ということなんですね。したら、要素積に対して逆フーリエ変換を取ると、Spectralな空間でconvolutionをして返ってきます。フーリエ基底に対応したグラフラプラシアンの固有ベクトルがあって、その結合係数を変化させて、グラフ上の特徴量変換をやって元の空間に返ってくればいい、というのがこの式ですね。固有値計算ってめっちゃ計算量がヤバいんです。固有ベクトルの積も計算コストがデカい。やりたくないんですが、こういう大きい計算が最初に定義された論文ですね。Filteringその固有値計算とか、そこを回避したいってモチベがあるので、そこに取り組んだのがその2年後に出たこちらの論文です。これは一言で言うと、チェビシェフ多項式近似で固有値分解を回避しよう。計算量を下げて、実用的な範囲で計算量をとどめましょう、みたいなことです。一言で言うと「チェビシェフ多項式近似しました」って感じですね。それで、多項式近似したほうが精度上がったというのがおもしろいところだと思っています。結局「なんで近似したほうが精度上がるの?」という話なんですが、これは「そもそもちょっと過学習してたんじゃない?」みたいな疑惑がありました。この次の論文でも、この「多項式近似したら精度上がった」という部分とちょっと関係してきます。あとはチェビシェフ多項式の次数、今回はkなんですが、これって固有値をk個取るのに対応しているので、フィルターサイズと対応してます。これ、後で使うのでちょっと覚えておいてください。Networksこの次を見ると、今まで紹介した論文一旦忘れてもいいぐらい、これ大事なのかなと思います。Networksのデファクトみたいな感じです。書いてる人も業界のメインみたいな人です。引用もめちゃめちゃされている論文です。一言で言うと、隣接ノードの畳み込みオンリーでSpectralGCNの近似ができます。隣接ノードの畳み込みの話をSpatialのところでやって、SpectralGCNの近似になるという話なので、簡単に言うと、SpatialなやつとSpectralなやつが、今ここで融合したと思ってください。先ほどチェビシェフ多項式近似をやりましたが、k=1の場合、最近傍のみ参照するということです。そのk=1の場合でやります。確かに、モデルの表現能力はめっちゃ下がります。k=1だと線形になるんですが、そこはDNNの深さでがんばりましょう。trickがいくつか導入されています。これはちょっと紹介できませんが、見てみてください。Networksが定義されたかな、というところですね。entropyで学習します、という論文です。今までのSpatialなやつとSpectralなやつとが合流した感じで、注目されていました。あとはこれもチェビシェフ多項式近似でk=1にしていますが、今まで過学習をたくさんしていたのか、過学習の抑制効果で近似したほうが精度が良くなっているんだと思います。あとは多項式近似にしたほうが精度も上がります。これはチェビシェフでも言いましたが、僕は過学習の抑制ができたからだと思っています。Networks』です。Networksは、x(t+1)をx(t)の状態から更新していくもので、あれは実質RNNなんですが、その状態更新をLSTMやGRUでやりましょう、ということですね。一応、勾配計算のアルゴリズムが変わったのと、シーケンシャルな出力を学習できるようになったので、応用幅はすごく増えたと思っています。この論文の中ではけっこういろんなタスクをやっていますが、コードの信頼性評価というタスクがあり、これがおもしろいなと思ったので、興味あったら見てみてください。前の論文は2009年で、これは2016年ということで、よりスマートな時代に沿った定式ではないかと思います。Networks?』という論文は、めちゃくちゃおもしろいです。これがICLRの2019のオーラルだったと思いますが、この論文が今後すごく大事になると思っています。test」はあまり聞き慣れないと思いますが、これは簡単に言うとグラフが2個あって、それが同じグラフであるかをチェックする方法です。testをかけると同じかどうかわかるというものです。結局グラフの表現能力は、グラフが同じ形かどうかをチェックできるかどうかで見ればいいよね、みたいな。testと同等の性能がそもそも得られているかを調べて、必要な制約は何か、というのをやっています。基本はAGGREGATEしてCOMBINEしてるよね、みたいな、この2つに分けています。TaskだったらAGGREGATEしてからCOMBINEしています。「結局、今まではAGGREGATEとCOMBINEに何を選ぶかでしたよね」ということを言っています。GCNに関しては「ぽく」書けばこうですね、みたいなことをこの論文では言っています。書けるのはわかりました。それぞれの表現能力の高さを分析したいんですけど、理想的には異なるグラフを完全に識別できるかどうかで、グラフの表現能力の高さがわかります。完全に識別できるとしたら、同型性識別問題はNPなんですけど、それを解決したことになってしまいます。この論文の中でいろいろ説明されてるんですが、今回は割愛します。kernelと等価です。testって、特徴ベクトルとして出てくるのって離散値なんですよ。subtree間の類似性とかそういうものは見れないんですが、GNNsではできます。testに類似しているというのがあるんですが、それを学習ベースで連続空間に拡張しています。結局表現能力の高さではなく、embeddingやグラフ構造間のdependencyができるようになってるところがいいよね、というように結論付けてます。testと一緒ぐらいです。Network」です。これがミニマムですよ、ということで、シンプルなものを提案しています。シンプルなんですが、もうこれでいいんですよ。これで「理論上、同程度の性能が出ます」と言ってるところが、クールなところかなと思います。Part2スピーカーの話が良かったらいいねしよう!nlpaper.challengenlpaper.challengeに関する記事をまとめています。コミュニティをフォローすることで、nlpaper.challengeに関する新着記事が公開された際に、通知を受け取ることができます。