論文の概要: Lookback for Learning to Branch

• arxiv url: http://arxiv.org/abs/2206.14987v1
• Date: Thu, 30 Jun 2022 02:33:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-01 14:08:00.473104
• Title: Lookback for Learning to Branch
• Title（参考訳）: 分岐への学習のためのルックバック
• Authors: Prateek Gupta, Elias B. Khalil, Didier Chet\'elat, Maxime Gasse, Yoshua Bengio, Andrea Lodi, M. Pawan Kumar
• Abstract要約: Bipartite Graph Neural Networks (GNN) は、ディープラーニングに基づくMixed-Integer Linear Program (MILP) の重要コンポーネントであることが示されている。 近年の研究では、分岐とバウンド(B&B)の解法における分岐(可変選択)を置き換える上で、そのようなGNNの有効性が実証されている。
• 参考スコア（独自算出の注目度）: 77.32867454769936
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The expressive and computationally inexpensive bipartite Graph Neural Networks (GNN) have been shown to be an important component of deep learning based Mixed-Integer Linear Program (MILP) solvers. Recent works have demonstrated the effectiveness of such GNNs in replacing the branching (variable selection) heuristic in branch-and-bound (B&B) solvers. These GNNs are trained, offline and on a collection of MILPs, to imitate a very good but computationally expensive branching heuristic, strong branching. Given that B&B results in a tree of sub-MILPs, we ask (a) whether there are strong dependencies exhibited by the target heuristic among the neighboring nodes of the B&B tree, and (b) if so, whether we can incorporate them in our training procedure. Specifically, we find that with the strong branching heuristic, a child node's best choice was often the parent's second-best choice. We call this the "lookback" phenomenon. Surprisingly, the typical branching GNN of Gasse et al. (2019) often misses this simple "answer". To imitate the target behavior more closely by incorporating the lookback phenomenon in GNNs, we propose two methods: (a) target smoothing for the standard cross-entropy loss function, and (b) adding a Parent-as-Target (PAT) Lookback regularizer term. Finally, we propose a model selection framework to incorporate harder-to-formulate objectives such as solving time in the final models. Through extensive experimentation on standard benchmark instances, we show that our proposal results in up to 22% decrease in the size of the B&B tree and up to 15% improvement in the solving times.
• Abstract（参考訳）: 表現的かつ計算的に安価な二部グラフニューラルネットワーク(GNN)は、深層学習に基づくMILP(Mixed-Integer Linear Program)の重要コンポーネントであることが示されている。 近年の研究では、分岐とバウンド(B&B)の解法における分岐(可変選択)ヒューリスティックを代替するGNNの有効性が示されている。 これらのGNNは訓練され、オフラインで、MILPのコレクション上で、非常に良いが計算に高価な分岐ヒューリスティックな強い分岐を模倣する。 B&BがサブMILPのツリーをもたらすことを考えれば、私たちは尋ねる。 (a)b&b木の隣接ノード間に目標ヒューリスティックによって示される強い依存関係があるか否か、及び (b)そうであれば、訓練手順に組み込むことができるかどうか。 特に、強い分岐ヒューリスティックでは、子ノードの最良の選択はしばしば親の2番目の選択であることが分かりました。 これを「見返り」現象と呼ぶ。 驚いたことに、Gasse et al. (2019) の典型的な分岐 GNN はこの単純な「答え」を見逃すことが多い。 GNNに見返り現象を組み込むことにより、目標行動をより密接に模倣する2つの方法を提案する。 (a)標準クロスエントロピー損失関数の目標平滑化及び b) Parent-as-Target (PAT) Lookback regularizer 項を追加する。 最後に,最終モデルにおける時間解決などの難解な目標を取り入れたモデル選択フレームワークを提案する。 標準ベンチマークのインスタンスを広範囲に実験した結果,提案手法ではb&bツリーのサイズが最大22%減少し,解決時間も最大15%向上した。

関連論文リスト

• Bregman Graph Neural Network [27.64062763929748]
  ノード分類タスクでは、GNNによって誘導される滑らか化効果は、連結ノードの表現と過剰な均質化ラベルを同化する傾向がある。 本稿では,Bregman 距離の概念に触発された GNN のための新しい二段階最適化フレームワークを提案する。
  論文  参考訳（メタデータ） (2023-09-12T23:54:24Z)
• Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
  まず,確率論的手法を用いて設計した新しいグラフニューラルネットワーク(GNN)モデルを提案する。 我々のアプローチは、AIで使用される古典的なバックトラッキングアルゴリズムの強化にGNNを適用する新しい方法を導入する。
  論文  参考訳（メタデータ） (2022-11-26T00:01:01Z)
• Learning to Compare Nodes in Branch and Bound with Graph Neural Networks [5.08128537391027]
  整数プログラミングにおける分岐とバウンドのアプローチは、次の探索のために空間の一部を順序付けする必要がある。 本稿では,この問題に対処する新たなシアムグラフニューラルネットワークモデルを提案し,ノードを属性付き二部グラフとして表現する。 本手法は,ノードがランクに応じて探索される平易なフレームワークのインスタンスを解くことで評価する。
  論文  参考訳（メタデータ） (2022-10-30T19:38:23Z)
• Recurrent Bilinear Optimization for Binary Neural Networks [58.972212365275595]
  BNNは、実数値重みとスケールファクターの内在的双線型関係を無視している。 私たちの仕事は、双線形の観点からBNNを最適化する最初の試みです。 我々は、様々なモデルやデータセット上で最先端のBNNに対して印象的な性能を示す頑健なRBONNを得る。
  論文  参考訳（メタデータ） (2022-09-04T06:45:33Z)
• Universal Deep GNNs: Rethinking Residual Connection in GNNs from a Path Decomposition Perspective for Preventing the Over-smoothing [50.242926616772515]
  近年の研究では、残りの結合を持つGNNが変性をわずかに遅らせていることが示されている。 本稿では,新しい経路分解の観点からの残差接続を有するGNNの前方・後方挙動について検討する。 コールドスタート適応残差接続(DRIVE)とフィードフォワードモジュールを備えたUniversal Deep GNNsフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-05-30T14:19:45Z)
• Rethinking Nearest Neighbors for Visual Classification [56.00783095670361]
  k-NNは、トレーニングセット内のテストイメージとトップk隣人間の距離を集約する遅延学習手法である。 我々は,教師付き手法と自己監督型手法のいずれでも,事前学習した視覚表現を持つk-NNを2つのステップで採用する。 本研究は,幅広い分類タスクに関する広範な実験により,k-NN統合の汎用性と柔軟性を明らかにした。
  論文  参考訳（メタデータ） (2021-12-15T20:15:01Z)
• Neural Network Branch-and-Bound for Neural Network Verification [26.609606492971967]
  本稿では,効率的な分岐戦略を設計するための新しい機械学習フレームワークを提案する。 グラフ入力として検証したいネットワークを直接扱う2つのグラフニューラルネットワーク(GNN)を学習する。 我々のGNNモデルは、より大きな未確認ネットワーク上での厳しい特性に対してよく一般化されていることを示す。
  論文  参考訳（メタデータ） (2021-07-27T14:42:57Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• S2-BNN: Bridging the Gap Between Self-Supervised Real and 1-bit Neural Networks via Guided Distribution Calibration [74.5509794733707]
  本研究では, 実数値から, 最終予測分布上のバイナリネットワークへの誘導型学習パラダイムを提案する。 提案手法は,bnn上で5.515%の絶対利得で,単純なコントラスト学習ベースラインを向上できる。 提案手法は、単純なコントラスト学習ベースラインよりも大幅に改善され、多くの主流教師付きBNN手法に匹敵する。
  論文  参考訳（メタデータ） (2021-02-17T18:59:28Z)
• Rethinking pooling in graph neural networks [12.168949038217889]
  畳み込み層とその後のプール層との相互作用について検討する。 一般的な信念とは対照的に、局所プールは、関連する、広く使用されているベンチマーク上でのGNNの成功には寄与しない。
  論文  参考訳（メタデータ） (2020-10-22T03:48:56Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。