論文の概要: Annealed Training for Combinatorial Optimization on Graphs

• arxiv url: http://arxiv.org/abs/2207.11542v1
• Date: Sat, 23 Jul 2022 15:48:14 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-26 15:12:45.083530
• Title: Annealed Training for Combinatorial Optimization on Graphs
• Title（参考訳）: グラフの組合せ最適化のためのアニールトレーニング
• Authors: Haoran Sun, Etash K. Guha, Hanjun Dai
• Abstract要約: 我々は,CO問題に対する簡易かつ効果的な熱処理トレーニングフレームワークを提案する。 4種類のCO問題において、本手法は、合成グラフと実世界のグラフの双方において、他の教師なしニューラルネットワークよりも性能が大幅に向上する。
• 参考スコア（独自算出の注目度）: 27.34972565928359
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The hardness of combinatorial optimization (CO) problems hinders collecting solutions for supervised learning. However, learning neural networks for CO problems is notoriously difficult in lack of the labeled data as the training is easily trapped at local optima. In this work, we propose a simple but effective annealed training framework for CO problems. In particular, we transform CO problems into unbiased energy-based models (EBMs). We carefully selected the penalties terms so as to make the EBMs as smooth as possible. Then we train graph neural networks to approximate the EBMs. To prevent the training from being stuck at local optima near the initialization, we introduce an annealed loss function. An experimental evaluation demonstrates that our annealed training framework obtains substantial improvements. In four types of CO problems, our method achieves performance substantially better than other unsupervised neural methods on both synthetic and real-world graphs.
• Abstract（参考訳）: 組合せ最適化(CO)問題の難しさは、教師あり学習のためのソリューション収集を妨げる。 しかしながら、CO問題に対するニューラルネットワークの学習は、トレーニングがローカルオプティマで簡単に阻止されるため、ラベル付きデータの欠如によって悪名高い。 本研究では,CO問題に対する簡易かつ効果的な熱処理訓練フレームワークを提案する。 特に、CO問題を非バイアスエネルギーベースモデル(EBM)に変換する。 EBMをできる限りスムーズにするため、われわれは罰則を慎重に選択した。 次に、ESMを近似するためにグラフニューラルネットワークを訓練する。 初期化付近の局所的最適位置でトレーニングが止まるのを防ぐために,アニール損失関数を導入する。 実験評価の結果,アニールトレーニングの枠組みが大幅に改善されていることが示された。 4種類のco問題において,本手法は合成グラフと実世界グラフの両方において,他の教師なしニューラル手法よりも大幅に性能が向上する。

関連論文リスト

• Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
  組合せ最適化(英: Combinatorial Optimization、CO)は、計算機科学、応用数学などにおける基本的な問題である。 本稿では, 正線形制約下でのCO問題の解法として, 非自己回帰ニューラルネットワーク群を設計する。 本研究では,施設位置,最大被覆率,旅行セールスマン問題を含む代表的CO問題の解決において,この枠組みの有効性を検証する。
  論文  参考訳（メタデータ） (2024-09-06T14:58:31Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
  ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。 私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。 以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
  論文  参考訳（メタデータ） (2023-05-18T13:59:02Z)
• Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning [14.86600327306136]
  最適化のための教師なし学習(CO)の一般的なフレームワークは、出力がCOの目的を直接最適化することで問題解決をもたらすニューラルネットワーク(NN)を訓練することである。 本研究では,COにおける教師なし学習の新たな目的について提案する。この学習の目的は,直接的な解決策を与えるのではなく,将来の問題インスタンスの優れた初期化を探すことである。 微調整前のモデルが与える初期解だけでも, 様々な評価条件下では, ベースラインを著しく上回る結果が得られます。
  論文  参考訳（メタデータ） (2023-01-08T22:14:59Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels [141.29156234353133]
  最先端の凸学習手法は、クライアントが異なるデータ分布を持つ場合、集中型よりもはるかにパフォーマンスが劣る。 我々は、この格差は、非NISTityが提示した課題に大きく起因していることを示す。 本稿では,Train-Convexify Neural Network (TCT) 手法を提案する。
  論文  参考訳（メタデータ） (2022-07-13T16:58:22Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Step-Ahead Error Feedback for Distributed Training with Compressed Gradient [99.42912552638168]
  集中型分散トレーニングにおける局所的エラーフィードバックによって,新たな"段階的ミスマッチ"問題が発生することを示す。 本稿では, 厳密な理論的解析を施した2つの新しい手法, 1) 一歩前進, 2) 誤差平均化を提案する。
  論文  参考訳（メタデータ） (2020-08-13T11:21:07Z)
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs [35.14404918074861]
  本研究では,グラフ上での組合せ最適化問題に対する教師なし学習フレームワークを提案する。 エルドスの確率論的手法に触発され、ニューラルネットワークを用いて集合上の確率分布をパラメータ化する。 ネットワークが適切に選択された損失に最適化された場合、学習された分布は、制御された確率、低コストな積分解を含むことを示す。
  論文  参考訳（メタデータ） (2020-06-18T16:13:36Z)

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

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