Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
論文読み会 AAAI2022 | MIP-GNN: A Data-Driven Framewo...
Search
cocomoff
January 04, 2023
Research
0
230
論文読み会 AAAI2022 | MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers
論文読み会の資料です.
(A slide for the paper-reading activity at my company, written in Japanese.)
cocomoff
January 04, 2023
Tweet
Share
More Decks by cocomoff
See All by cocomoff
論文読み会 NeurIPS2024 | UrbanKGent: A Unified Large Language Model Agent Framework for Urban Knowledge Graph Construction
cocomoff
1
61
論文読み会 AMAI | Personalized choice prediction with less user information
cocomoff
0
46
論文読み会 KDD2024 | Relevance meets Diversity: A User-Centric Framework for Knowledge Exploration through Recommendations
cocomoff
0
230
論文読み会 KDD2022 | Multi-Behavior Hypergraph-Enhanced Transformer for Sequential Recommendation
cocomoff
0
130
論文読み会 AISTATS2024 | Deep Learning-Based Alternative Route Computation
cocomoff
0
41
論文読み会 AAAI2021 | Knowledge-Enhanced Top-K Recommendation in Poincaré Ball
cocomoff
0
78
論文読み会 WWW2022 | Learning Probabilistic Box Embeddings for Effective and Efficient Ranking
cocomoff
0
290
ClimaX: A foundation model for weather and climate
cocomoff
0
580
論文読み会 EMNLP2021 | Decision-Focused Summarization
cocomoff
0
210
Other Decks in Research
See All in Research
When Submarine Cables Go Dark: Examining the Web Services Resilience Amid Global Internet Disruptions
irvin
0
260
在庫管理のための機械学習と最適化の融合
mickey_kubo
3
1.1k
Delta Airlines® Customer Care in the U.S.: How to Reach Them Now
bookingcomcustomersupportusa
PRO
0
100
SSII2025 [SS2] 横浜DeNAベイスターズの躍進を支えたAIプロダクト
ssii
PRO
7
3.7k
ストレス計測方法の確立に向けたマルチモーダルデータの活用
yurikomium
0
870
能動適応的実験計画
masakat0
2
670
引力・斥力を制御可能なランダム部分集合の確率分布
wasyro
0
210
診断前の病歴テキストを対象としたLLMによるエンティティリンキング精度検証
hagino3000
1
110
問いを起点に、社会と共鳴する知を育む場へ
matsumoto_r
PRO
0
480
集合間Bregmanダイバージェンスと置換不変NNによるその学習
wasyro
0
120
なめらかなシステムと運用維持の終わらぬ未来 / dicomo2025_coherently_fittable_system
monochromegane
0
1.3k
Hiding What from Whom? A Critical Review of the History of Programming languages for Music
tomoyanonymous
0
100
Featured
See All Featured
The Art of Programming - Codeland 2020
erikaheidi
54
13k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
60k
RailsConf 2023
tenderlove
30
1.2k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
26k
GraphQLとの向き合い方2022年版
quramy
49
14k
Building Applications with DynamoDB
mza
95
6.5k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
138
34k
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.4k
Statistics for Hackers
jakevdp
799
220k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
21
1.4k
Why You Should Never Use an ORM
jnunemaker
PRO
58
9.5k
The World Runs on Bad Software
bkeepers
PRO
70
11k
Transcript
MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers 著者: Elias
B. Khalil, Christopher Morris, Andrea Lodi (Univ. of Toronto, McGill University, Cornell Tech) 学会: AAAI2022 @cocomoff 1/20
概要 やりたいこと 組合せ最適化ソルバーをデータ駆動型でサポートする 分枝限定法で どのノードを次に選択するか (node selection) どの変数を分枝するか (branching variable
selection) やったことの概要 0-1整数計画問題(Binary Linear Programming; BLP) を考える 表現力の高い問題クラス 具体的にはGISP (Generalized Independent Set Prolbem) / FCMNF (Fixed-Charge Multi-Commodity Flow problem) で実験 ソルバーを使ってそこそこの解を計算し、学習に使う 最適化問題の変数バイアス(Variable bias、後で説明)をGNNで推定 変数バイアスの予測値を使ってスコアリング手法を提案 ついでに解のwarm-startとかもできる 2/20
結果 GISPのベンチマークデータについて、MIP-GNNでサポートする分枝限定法とデフォ ルトの分枝限定法でどのようなパフォーマンス差が観測されたか Primal integral: 最適解と比べてある段階で見つかった解がどれぐらいのも のか、を解が見つかった時間で積分した評価値(?)、小さいと最適に近い Gap: ギャップ、小さいと最適に近い 3/20
目次 イントロ・結果 準備 分枝限定法 変数バイアス (Variable Bias) LP、BLP (0-1 ILP)
学習問題の設定 手法 (MIP-GNN) 実験 4/20
補足: 分枝限定法 Qiita: 「図で見る分枝限定法」より図を引用 ナップサック問題(あるアイテムについて、0 (入れない)・1 (入れる) を決める) node selection:
次にどの部分木を調べるか決める branching variable selection: まだ展開して決定していない二値変数のう ち、どれを次に展開するかを決める 5/20
補足: 変数バイアス CNF-SAT に対して定義された概念 [1] 例題: 3つの節、 変数の式 SATインスタンス 変数割当
が を充足する が真 補足: 変数バイアス(Bias) 充足可能な について、変数 の(推定された)バイアス分布 とは、 の充足可 能な割当について変数 が真 (または偽) で現れる割合を表す positive/negative bias ( ) 全ての変数についてのバイアスをベクトルに格納したものを Survey/Profile と呼ぶ 余談: 名前が一般的過ぎてググっても情報が出てこない… 要するに「どれぐらい真 (または偽)を取り得るか」の情報 [1] E.I. Hsu et al., Probabilistically Estimating Backbones and Variable Bias: Experimental Overview, Proceedings of CP2008, pp.613-617, 2008 / 同著者のAAAI2008 Workshopの論文もある。 6/20
補足: LP、BLP (0-1 ILP) 線形計画問題 (LP) は 3つ組 で定義される ぐらいの範囲を考える
feasible set LPの目的: Simplex法や内点法で解ける 整数線形計画問題 (ILP) は 3つ組 で定義される ただし feasible set に制限する場合、BLP (0-1 ILP) と呼ぶ あるBLPのインスタンス から整数性を落とした問題 を緩和問題と呼ぶ 分枝限定法 分枝操作と限定操作を用いた一般解法で全てのソルバーで使われている 分枝操作: 変数の場合分け 限定操作: 見積もった最適値による枝刈り 内部で切除平面法と合わせた場合に分枝切除法と呼ばれることも 7/20
目次 イントロ・結果 補足 分枝限定法 変数バイアス (Variable Bias) LP、BLP (0-1 ILP)
学習問題の設定 手法 (MIP-GNN) 実験 8/20
学習問題の設定 | BLPの場合の変数バイアス 実世界の何らかの分布から作られたインスタンスの集合 を考える あるインスタンス について、near-optimal solutions の集合 (tolerance
) を定義する 変数バイアスベクトル を以下で定義する -near optimal solutionの中で、各決定変数が だった割合のベクトル CNF-SATの変数バイアスのベクトル (Survey/Profile) と同じ 凄い強そうな情報だが、計算がヤバそう これを教師あり学習で近似する (MIP-GNN) のが提案アプローチ 9/20
学習問題の設定 | 教師あり学習 普通の教師あり学習を考える。記号: : インスタンス集合 の上の分布 : 有限の学習集合インスタンスの集合 (分布
でサンプル) 予測モデル はインスタンス の決定変数の集合 パラメータ ロス関数 教師あり学習 直感的には が面倒そうだけど、GNNに任せたらいけそう ポイント: 変数と制約に注目して、二部グラフを作った上でGNNを動かす 10/20
目次 イントロ・結果 補足 分枝限定法 変数バイアス (Variable Bias) LP、BLP (0-1 ILP)
学習問題の設定 手法 (MIP-GNN) 実験 11/20
MIP-GNN: 概要 変数と制約に注目した、二部グラフ上のGNNによるスコア計算 決定変数と制約に対応した特徴ベクトルを作る 制約に使われている決定変数と結んで二部グラフを作る いい感じにGNN (周辺の特徴のaggregation、特徴ベクトルのmerge) する 12/20
MIP-GNN: アーキテクチャ 二部グラフ (制約cと変数vのパート) v cの伝搬(左)、c v の伝搬(右) これを交互に繰り返す (iterate)
特徴ベクトル ( 層目): 目的関数の (紛らわしい) の情報もここに入れる v → c はベクトルの連結、普通のGNN c → v 各変数 に対して を求め、ベクトル を得る 制約 の違反量をsoftmaxで測定する: 誤差ベクトルは次段のvariable embedding更新に使う 13/20
MIP-GNN: 学習と評価 学習 -near optimal solutionを既存のソルバーで探して学習する 正確な値 を予測しなくても、 に近いかどうか?が知れたら十分に嬉しい しきい値
で加工した二値分類問題として学習させる もし であれば を、そうでなければ を当てる MIP-GNNで最後にMLPを通して推定したスコアは、以降の活用フェーズ(右側)では で表す 評価 | 確信スコア MLPを通して出力されたベクトル に対して、変数 の確信度を定義: は の近い方に丸める操作 どれぐらい予測が整数に近いかを表す 14/20
MIP-GNN: 分枝限定法への活用 数値の確信度を使って、分枝限定法のノード選択スコアを定義する BnBで既に確定している変数と予測値が一致していればその確信度を、そうで なければ乖離している具合を使ってスコアに入れる もう少し真面目な定義は論文へ 15/20
MIP-GNN: 解のwarm-start スコアを見て、直接近似解を求められそう: しきい値 を用いて 適当に丸めているだけなのでfeasibleではない解になる、CPLEXには壊れた解を feasibleに直す機能(repair)があるので、それに突っ込めばOK よく知りません… (これはただのメモ) node-selection、branching
variable selection、warm-startの3要素 branching variable selectionはサポートしてない(説明なし?)? ついでに、ソルバーを使って -near optimal solutionの準備は必要なので、 それはそれで大変な気がする(60分と書いてあった、詳細は知らない) 16/20
目次 イントロ・結果 補足 分枝限定法 変数バイアス (Variable Bias) LP、BLP (0-1 ILP)
学習問題の設定 手法 (MIP-GNN) 実験 17/20
実験結果 | GISPの性能 (再掲) そこそこ良い (node-selectionのサポートあり vs なし) 18/20
実験結果 | パラメータとGNNアーキテクチャ 途中で出てきたしきい値 の影響 GNNの具体的なアーキテクチャ: GIN、GraphSage、EC (EdgeConvolution) 大きく差はない 19/20
実験結果 | 転移学習 問題集合間の転移: 効果的だったり、そうでもなかったりした GISPとFCMNFがあると書いてあったけど、FCMNFは載ってなかった(どこかの Appendixにあるらしい) 20/20