論文の概要: What's Wrong with Deep Learning in Tree Search for Combinatorial
Optimization
- arxiv url: http://arxiv.org/abs/2201.10494v1
- Date: Tue, 25 Jan 2022 17:37:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-26 15:00:18.214602
- Title: What's Wrong with Deep Learning in Tree Search for Combinatorial
Optimization
- Title(参考訳): 組合せ最適化のための木探索におけるディープラーニングの誤り
- Authors: Maximilian B\"other, Otto Ki{\ss}ig, Martin Taraz, Sarel Cohen, Karen
Seidel, Tobias Friedrich
- Abstract要約: 本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。
また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。
木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
- 参考スコア(独自算出の注目度): 8.879790406465556
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Combinatorial optimization lies at the core of many real-world problems.
Especially since the rise of graph neural networks (GNNs), the deep learning
community has been developing solvers that derive solutions to NP-hard problems
by learning the problem-specific solution structure. However, reproducing the
results of these publications proves to be difficult. We make three
contributions. First, we present an open-source benchmark suite for the NP-hard
Maximum Independent Set problem, in both its weighted and unweighted variants.
The suite offers a unified interface to various state-of-the-art traditional
and machine learning-based solvers. Second, using our benchmark suite, we
conduct an in-depth analysis of the popular guided tree search algorithm by Li
et al. [NeurIPS 2018], testing various configurations on small and large
synthetic and real-world graphs. By re-implementing their algorithm with a
focus on code quality and extensibility, we show that the graph convolution
network used in the tree search does not learn a meaningful representation of
the solution structure, and can in fact be replaced by random values. Instead,
the tree search relies on algorithmic techniques like graph kernelization to
find good solutions. Thus, the results from the original publication are not
reproducible. Third, we extend the analysis to compare the tree search
implementations to other solvers, showing that the classical algorithmic
solvers often are faster, while providing solutions of similar quality.
Additionally, we analyze a recent solver based on reinforcement learning and
observe that for this solver, the GNN is responsible for the competitive
solution quality.
- Abstract(参考訳): 組合せ最適化は多くの現実世界の問題の核心にある。
特にグラフニューラルネットワーク(gnns)の台頭以来、ディープラーニングコミュニティは、問題固有のソリューション構造を学習することでnp問題に対するソリューションを導出するソルバを開発してきた。
しかし、これらの出版物の結果の再現は困難であることが証明されている。
我々は3つの貢献をした。
まず、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。
このスイートは、さまざまな最先端の伝統的および機械学習ベースのソルバに統一されたインターフェースを提供する。
第2に、我々のベンチマークスイートを用いて、Liらによる人気のガイド木探索アルゴリズムを詳細に分析する。
[neurips 2018]、小規模、大規模、実世界のグラフで様々な構成をテストする。
コード品質と拡張性に着目してアルゴリズムを再実装することにより,木探索で使用されるグラフ畳み込みネットワークは,解構造の有意義な表現を学習せず,実際にランダムな値に置き換えることができることを示す。
その代わりに、木探索はグラフのカーネル化のようなアルゴリズム技術を使って良い解を見つける。
したがって、元の出版物からの結果は再現できない。
第3に,木探索の実装を他の解法と比較するために解析を拡張し,古典的アルゴリズム解法の方が高速であることが示され,同様の品質の解法を提供する。
さらに、強化学習に基づく最近の解法を解析し、この解法について、GNNが競合ソリューションの品質に責任があることを観察する。
関連論文リスト
- Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems [0.0]
Graph Neural Networks (GNNs)は、コンビネーション最適化(CO)問題の解決における研究者の約束を示す。
本研究では,最大独立集合(MIS)問題の解法におけるGNNの有効性について検討した。
論文 参考訳(メタデータ) (2024-11-06T09:12:31Z) - A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization [12.016449555335976]
我々はNP-hard Maximum Cut問題に特化しているオープンソースのベンチマークスイートMaxCut-Benchを提案する。
我々は、このベンチマークを用いて、いくつかの一般的な学習ベースのアプローチの結果を体系的に相関づけたり、再現したりしようとする。
以上の結果から, 学習者の数人は, ナイーブな欲求アルゴリズムを上回り得ず, タブサーチを一貫して上回っているのはそのうちの1人だけであることが示唆された。
論文 参考訳(メタデータ) (2024-06-14T19:44:23Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳(メタデータ) (2024-06-05T22:52:27Z) - Learning To Dive In Branch And Bound [95.13209326119153]
グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。
我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
論文 参考訳(メタデータ) (2023-01-24T12:01:45Z) - Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
まず,確率論的手法を用いて設計した新しいグラフニューラルネットワーク(GNN)モデルを提案する。
我々のアプローチは、AIで使用される古典的なバックトラッキングアルゴリズムの強化にGNNを適用する新しい方法を導入する。
論文 参考訳(メタデータ) (2022-11-26T00:01:01Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳(メタデータ) (2022-11-01T18:33:20Z) - Learning to Prune Instances of Steiner Tree Problem in Graphs [0.47138177023764655]
ノードの集合が与えられるグラフ上のスタイナー木問題を考える。
目的は、追加ノードを含むすべてのノードを含むツリーのサブグラフを見つけることである。
論文 参考訳(メタデータ) (2022-08-25T10:31:00Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z) - Physarum Powered Differentiable Linear Programming Layers and
Applications [48.77235931652611]
一般線形プログラミング問題に対する効率的かつ微分可能な解法を提案する。
本稿では,ビデオセグメンテーションタスクとメタラーニングにおける問題解決手法について述べる。
論文 参考訳(メタデータ) (2020-04-30T01:50:37Z) - GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。
このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。
我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
論文 参考訳(メタデータ) (2020-02-08T10:03:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。