論文の概要: Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems

• arxiv url: http://arxiv.org/abs/2102.03002v1
• Date: Fri, 5 Feb 2021 05:23:26 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-08 14:42:53.409195
• Title: Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems
• Title（参考訳）: Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems
• Authors: Yiwei Bai, Wenting Zhao, Carla P. Gomes
• Abstract要約: ZTopは、シンプルなが効果的なモデル選択と、問題を解決するための学習のためのアンサンブル機構である。 ZToppingは、ZTopアンサンブル戦略と与えられたディープラーニングアプローチを用いて、現在最先端のディープラーニングアプローチの性能を大幅に向上させる方法を示している。
• 参考スコア（独自算出の注目度）: 21.411742165753456
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: There has been an increasing interest in harnessing deep learning to tackle combinatorial optimization (CO) problems in recent years. Typical CO deep learning approaches leverage the problem structure in the model architecture. Nevertheless, the model selection is still mainly based on the conventional machine learning setting. Due to the discrete nature of CO problems, a single model is unlikely to learn the problem entirely. We introduce ZTop, which stands for Zero Training Overhead Portfolio, a simple yet effective model selection and ensemble mechanism for learning to solve combinatorial problems. ZTop is inspired by algorithm portfolios, a popular CO ensembling strategy, particularly restart portfolios, which periodically restart a randomized CO algorithm, de facto exploring the search space with different heuristics. We have observed that well-trained models acquired in the same training trajectory, with similar top validation performance, perform well on very different validation instances. Following this observation, ZTop ensembles a set of well-trained models, each providing a unique heuristic with zero training overhead, and applies them, sequentially or in parallel, to solve the test instances. We show how ZTopping, i.e., using a ZTop ensemble strategy with a given deep learning approach, can significantly improve the performance of the current state-of-the-art deep learning approaches on three prototypical CO domains, the hardest unique-solution Sudoku instances, challenging routing problems, and the graph maximum cut problem, as well as on multi-label classification, a machine learning task with a large combinatorial label space.
• Abstract（参考訳）: 近年,組合せ最適化(CO)問題に取り組むためにディープラーニングを活用することへの関心が高まっている。 典型的なcoディープラーニングアプローチは、モデルアーキテクチャの問題構造を活用する。 それでも、モデル選択は主に従来の機械学習設定に基づいている。 CO問題の離散的な性質のために、単一のモデルが問題を完全に学ぶ可能性は低い。 ZTopはZero Training Overhead Portfolioの略で、組み合わせ問題を解決するためのシンプルで効果的なモデル選択とアンサンブルメカニズムです。 ZTopは、一般的なCOアンサンブル戦略であるアルゴリズムポートフォリオ、特にランダム化されたCOアルゴリズムを定期的に再開するポートフォリオの再開に触発され、事実上、異なるヒューリスティックな検索空間を探索します。 我々は、同じトレーニング軌道で取得した訓練されたモデルが、同様の検証性能を持つ場合、非常に異なる検証インスタンスでうまく機能することを観察した。 この観察に続いて、ztopは訓練されたモデルのセットをアンサンブルし、それぞれがトレーニングオーバーヘッドゼロのユニークなヒューリスティックを提供し、それらを逐次または並行に適用してテストインスタンスを解決する。 ZToppingは、ZTopのアンサンブル戦略と与えられたディープラーニングアプローチを用いて、現在の3つの原型COドメイン、最も困難なユニークソリューションのSudokuインスタンス、挑戦的なルーティング問題、グラフ最大カット問題、およびマルチラベル分類、大規模な組み合わせラベル空間を備えた機械学習タスクのパフォーマンスを大幅に向上させる方法を示す。

関連論文リスト

• EnsIR: An Ensemble Algorithm for Image Restoration via Gaussian Mixture Models [70.60381055741391]
  画像復元の課題は、説明された問題に関連し、単一のモデル予測と地道のずれをもたらす。 アンサンブル学習は、複数のベースモデルの予測を組み合わせることで、これらの偏差に対処することを目的としている。 我々は予測候補のアンサンブル重みを推定するために予測(EM)に基づくアルゴリズムを用いる。 我々のアルゴリズムは、モデルに依存しない訓練不要であり、様々なトレーニング済み画像復元モデルのシームレスな統合と強化を可能にする。
  論文  参考訳（メタデータ） (2024-10-30T12:16:35Z)
• GOAL: A Generalist Combinatorial Optimization Agent Learning [0.05461938536945722]
  GOALは複数のハード最適化問題(COP)を効率的に解くことができるモデルである ゴールは1つのバックボーンと、入力および出力処理用の軽量な問題固有のアダプタで構成されている。 GOALは,幅広いCOPを解く最初のマルチタスクモデルでありながら,特定のベースラインよりもわずかに劣っている。
  論文  参考訳（メタデータ） (2024-06-21T11:55:20Z)
• Oracle Inequalities for Model Selection in Offline Reinforcement Learning [105.74139523696284]
  本稿では,値関数近似を用いたオフラインRLにおけるモデル選択の問題について検討する。 対数係数まで最小値の速度-最適不等式を実現するオフラインRLの最初のモデル選択アルゴリズムを提案する。 そこで本研究では,優れたモデルクラスを確実に選択できることを示す数値シミュレーションを行った。
  論文  参考訳（メタデータ） (2022-11-03T17:32:34Z)
• 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)
• A Unified Analysis of Dynamic Interactive Learning [5.474944738795308]
  Emamjomeh-Zadeh氏らによる以前の研究は、非静的なユーザの好みをモデル化する手段として、インタラクティブな学習のダイナミクスを導入しました。 私たちは、[Emamjomeh-Zadeh et al., 2020]で分析されたモデルの両方をキャプチャするフレームワークを提供します。 また,学習者が各ラウンドのフィードバックに従う,効率的なアルゴリズムについても検討する。
  論文  参考訳（メタデータ） (2022-04-14T16:03:37Z)
• On the Difficulty of Generalizing Reinforcement Learning Framework for Combinatorial Optimization [6.935838847004389]
  現実の応用とグラフ上の組合せ最適化問題(COP)は、コンピュータサイエンスにおける標準的な課題である。 このアプローチの基本原理は、ノードのローカル情報とグラフ構造化データの両方を符号化するグラフニューラルネットワーク(GNN)をデプロイすることである。 我々は,クラウド上のセキュリティ対応電話機のクローン割り当てを古典的二次代入問題 (QAP) として,深層RLモデルが他の難題の解法に一般的に適用可能であるか否かを調査する。
  論文  参考訳（メタデータ） (2021-08-08T19:12:04Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems [4.692304496312442]
  本稿では,カバーセールスマン問題 (CSP) を大まかに解くための新しい深層学習手法を提案する。 このアプローチでは、CSPの都市位置を入力として、ディープニューラルネットワークモデルがソリューションを直接出力するように設計されている。 指導なしに深層強化学習を用いて訓練される。
  論文  参考訳（メタデータ） (2021-02-11T07:25:04Z)
• SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning [102.78958681141577]
  SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。 SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
  論文  参考訳（メタデータ） (2020-07-09T17:08:44Z)
• Stepwise Model Selection for Sequence Prediction via Deep Kernel Learning [100.83444258562263]
  本稿では,モデル選択の課題を解決するために,新しいベイズ最適化(BO)アルゴリズムを提案する。 結果として得られる複数のブラックボックス関数の最適化問題を協調的かつ効率的に解くために,ブラックボックス関数間の潜在的な相関を利用する。 我々は、シーケンス予測のための段階的モデル選択(SMS)の問題を初めて定式化し、この目的のために効率的な共同学習アルゴリズムを設計し、実証する。
  論文  参考訳（メタデータ） (2020-01-12T09:42:19Z)
• Learning fine-grained search space pruning and heuristics for combinatorial optimization [5.72274610208488]
  本稿では,機械学習技術を利用して正確な最適化アルゴリズムをスケールアップするフレームワークを提案する。 我々のフレームワークは、問題インスタンスのサイズを減らすために、要素を刈り取るという比較的単純なタスクを学習します。 我々のフレームワークは入力グラフのかなりの部分を取り除き、なおも最大傾きのほとんどを検出可能であることを示す。
  論文  参考訳（メタデータ） (2020-01-05T13:10:39Z)

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

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