2024.12.19
システムの穴を運用でカバーしようとしてミス多発… バグが大量発生、決算が合わない状態から業務効率化を実現するまで
リンクをコピー
記事をブックマーク
Graph Representationに移ります。
この「Deepwalk」というものがあって、Embeddingの話、グラフのノードの分散表現を得たいという話をしたいと思います。このDeepwalkは、けっこう有名かなと思います。
グラフ上でランダムウォークします。すると、系列が得られると思いますが、その得られた系列、Skip-gramってわかりますかね? n-gramはわかると思いますが、Skip-gramは「I have a pen」みたいなものがあったとして、ちゃんと学習されたSkip-gramがあったら、「I」がきたときに隣接する単語「a」は違うよね、「have」ですよね、みたいな。そうやって、関係性の近いワードの確率が出ます。それがSkip-gramです。
その得られた系列をSkip-gramに入力してノードの分散表現を得ます、ということをDeepwalkはやっています。
この図はグラフがあって、そのグラフが分散表記になったというやつなんですけど。なんかイケてる感じしませんか? グラフの近さを表現できてる感があると思います。
続いて「LINE」という手法があって、直接リンクを持っていないノードでも近しい特徴を持っているのであればそれは似ているノードだから、それも考慮してEmbeddingしましょう、みたいな感じです。
これは図を見てもらうのが一番早いですね。図を見てもらうとノード5と6があると思いますが、まずノード5と6はつながっていません、ですが、ノード5と6がつながっているノードはだいたい一緒です。なので、「second-order proximity」と言っているのですが、「グローバルに見ると5と6は似てますよね」みたいなことを言っています。だからそれを考慮してEmbeddingしましょう、というやつです。一応エッジサンプリングを工夫したりとかもありますが、こういう手法があります。
次に「node2vec」というやつが出て、これはだいたい1年刻みでやっています。
なのでこのnode2vecは、DeepWalkで系列取得するのがランダムウォークだったんですが、ランダムウォークではなくもうちょっとグラフらしくノード探索しましょう、というのを提案してますね。
「グラフらしく」とは何かというと、幅優先と深さ優先のバランス取りましょう、という話です。今までやっていたのは、幅優先、近隣の関係見ましょうという感じで、同じノードばかり見てしまうんですよね。ですが、深さ優先するとより遠くのノードから近傍を構成できます。
ただし、遠くに行くので分散がデカくなるという問題はありますが、その間のバランスを取ってサンプリング戦略決めましょう、ということで、サンプリング戦略を持っているDeepwalkです。
あとは、GraphGANというものがあります。
これは何かと言うと、シンプルに言うと生成されたノードをグラフに混ぜ込んでいく生成モデルと、それに対してグラフ全体の妥当性を判断する識別モデルがあったら、グラフでGANできるやん、ということをやってます。
だからこれは生成されたノードをグラフに混ぜ込むということがわかっていれば、パッと理解できるかなと思います。一応policy gradientを取るんですが、これがけっこう曲者です。loss計算が曲者で、そこでけっこうがんばってるイメージですね。そこをがんばって、Graph Softmaxを導入していて、これが地味に貢献していて、計算効率がすごい上がりますよ、という。異なる文脈で発展してきたグラフ生成モデルという識別モデルがここで融合します。
次はずっと話したかったWL testです。
これは「グラフの同型性の判断をやるやつですよ」と言ったんですが、これは1回やってみるといいなって思っています。1回、何か小さなグラフでWL testやってみると、一発でわかります。
一発でわかるんですが、一応説明します。全部のノードについて、自分と近傍ノードのラベルを集めてきます。そして集めたラベルをソートして、そのラベル集合にまったく新しいラベルを振ります。これを繰り返すと毎回新しいラベルが作られていくのですが、その新しく作られるラベル集合がどこかで一致しだしたら同型。一致してなかったら非同型ですよ、というやつです。これはやればわかります。同型性判定ではおそらく一番引用されてるんじゃないかと思います。
このWL subtree kernelというものは、subtree kernelを使うと特徴量化もできるのですが、これは同じ人が論文を書いています。同じ人が書いているので、だいたい書き方も一緒です。よかったら読んでください。
続いて、Applicationsを見ます。
これはグラフの低次元埋め込みを学習して、グラフでの論理演算を帰化操作に変換するということをしていて、まず何かグラフあるとします。それを埋め込みます。グラフでやりたかった操作があったとして、そのグラフでやりたかった操作は埋め込み空間では、幾何操作ですよね。
グラフでやりたかった論理演算は、埋め込み空間で何か対応する幾何操作があります。その幾何操作でやると、線形時間で探索できていいですよ、みたいなことをいっています。
1個1個説明します。まず、Knowledge Graphを対象にしてるんですが、現実世界にあるKnowledge Graphって、絶対に何か欠けてると思っていいと思います。それはなぜかというと、僕らはすべての知識を持っているわけではなく、ちょっとずつKnowledge Graphに新しい知識を足しながら、その中で推論をやっていきます。なので、常に不完全なグラフの上で僕らは推論してると思うんです。
その不完全なグラフがあって、今はわからないですが、新しいノードが実はつながってて、本当は今回のクエリの答えはそれなんだって場合、あり得るじゃないですか。
そのときに、ちゃんと今はないノードを指してほしい、というのがモチベーションとしてあります。まずグラフ上でのクエリ自体をグラフにして、その始点を今回はconjunctive queryなので論理積の演算なんですが、そのスタートのところを低次元で埋め込む。そして、グラフ上では論理積の操作なんですが、このグラフ上での論理積の操作は埋め込み空間ではprojectionになってると。このprojectionはベクトルのintersectionでできる、というのが今回の論文でわかりました。
そして、projectionしたら、今は存在しないノードかもしれませんが、そのprojectionによって、この新しいノードが求めるものですよ、ということがわかる。シンプルに言うとそういう感じです。
今までもこういうことはありましたが、これを幾何操作でやっているところが偉くて。なぜかというと、まず考えてほしいのですが、Knowledge Graphがあって「不完全なKnowledge Graphですよ」と言われたときに、全てのノードを取ってきて、そのノードが新しいノードとつながっている可能性を全部考慮しなければいけません。結局、ノードの数だけ尤度計算が発生するんですよね。ノード全部に対して、新しいノードとのつながりがあり得るから。
なんですが、これをProjectionにすると考えなくていいんですよね。ただ移動するだけなので、わかりますかね(笑)……考えなくていいんですよね、すべての点に対する尤度計算しなくていいので。だから線形時間と言っていて、この論文はそういうちょっとおもしろいことを提案しています。
この論文は他にも言うことはありますが、グラフを経由したEmbeddingをやることで、論理演算可能な性質がEmbedding先の空間に残るというのがおもしろいです。
最後に、見て一発でわかる系のやつで終わります。物理法則を物体とその関係性に分解することで推測できるようにしました、という物理シミュレーションですね。
シンプルに物体と物体間の関係をグラフにして、その効果量の計算モデルと、あとは外力ですね。その相互作用を考慮した状態推定を行うモデルを2個作ってやっています。という感じなんですけど。なんかキレイにできてるな、って思ったので紹介しました。
汎用性が高くて一般的な物理法則に適用できるんですが、まだまだトイプログラムぐらいしかできないくらい、計算量がめちゃくちゃ大きいんですね。
とりあえずこれで論文は終わりです。あとは今回読んでいて「おもしろい論文書くな」と思った研究者を紹介します。
とくに僕が好きなのは、このMax Wellingさんですね。この人はVariational AutoEncoderの人なので、知ってる人も多いと思います。あとはThomasさんはたぶんこの研究室の博士だと思いますが、GCNでけっこう実績を残している人です。僕が一番好きなのは、このWilliam Hamilton先生です。すごく独特の切り口で、毎回グラフのいろいろな問題を扱ってらっしゃいます。
こんな感じで、今回は時間なくてアレだったんですけど……グラフ論文のサーベイを研究したい人、あるいはおもしろいデータセットを作りたい、あるいは共同研究考えてみたい。そんな人がいたらまずは連絡をください。NLPとCVとなっていますが、そういうところも今後やりたいと思っています。
はい、以上です。ありがとうございました。
(会場拍手)
関連タグ:
2024.12.20
日本の約10倍がん患者が殺到し、病院はキャパオーバー ジャパンハートが描く医療の未来と、カンボジアに新病院を作る理由
2024.12.19
12万通りの「資格の組み合わせ」の中で厳選された60の項目 532の資格を持つ林雄次氏の新刊『資格のかけ算』の見所
2024.12.16
32歳で成績最下位から1年でトップ営業になれた理由 売るテクニックよりも大事な「あり方」
2023.03.21
民間宇宙開発で高まる「飛行機とロケットの衝突」の危機...どうやって回避する?
PR | 2024.12.20
モンスター化したExcelが、ある日突然崩壊 昭和のガス工事会社を生まれ変わらせた、起死回生のノーコード活用術
2024.12.12
会議で発言しやすくなる「心理的安全性」を高めるには ファシリテーションがうまい人の3つの条件
2024.12.18
「社長以外みんな儲かる給与設計」にした理由 経営者たちが語る、優秀な人材集め・会社を発展させるためのヒント
2024.12.17
面接で「後輩を指導できなさそう」と思われる人の伝え方 歳を重ねるほど重視される経験の「ノウハウ化」
2024.12.13
ファシリテーターは「しゃべらないほうがいい」理由 入山章栄氏が語る、心理的安全性の高い場を作るポイント
2024.12.10
メールのラリー回数でわかる「評価されない人」の特徴 職場での評価を下げる行動5選
Climbers Startup JAPAN EXPO 2024 - 秋 -
2024.11.20 - 2024.11.21
『主体的なキャリア形成』を考える~資格のかけ算について〜
2024.12.07 - 2024.12.07
Startup CTO of the year 2024
2024.11.19 - 2024.11.19
社員の力を引き出す経営戦略〜ひとり一人が自ら成長する組織づくり〜
2024.11.20 - 2024.11.20
「確率思考」で未来を見通す 事業を成功に導く意思決定 ~エビデンス・ベースド・マーケティング思考の調査分析で事業に有効な予測手法とは~
2024.11.05 - 2024.11.05