論文の概要: Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation

• arxiv url: http://arxiv.org/abs/2207.05984v2
• Date: Thu, 14 Jul 2022 03:51:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-15 12:11:16.145380
• Title: Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation
• Title（参考訳）: 主観的緩和による組合せ最適化のための教師なし学習
• Authors: Haoyu Wang, Nan Wu, Hang Yang, Cong Hao, Pan Li
• Abstract要約: 本研究は,最適化(CO)問題に対する教師なし学習フレームワークを提案する。 我々の重要な貢献は、緩和された目的がエントリーワイドな凹凸を満たすならば、低い最適化損失は最終積分解の品質を保証するという観察である。 特に、この観察は、対象が明示的に与えられていないアプリケーションにおいて、事前にモデル化される必要がある場合に、対象モデルの設計を導くことができる。
• 参考スコア（独自算出の注目度）: 19.582494782591386
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Using machine learning to solve combinatorial optimization (CO) problems is challenging, especially when the data is unlabeled. This work proposes an unsupervised learning framework for CO problems. Our framework follows a standard relaxation-plus-rounding approach and adopts neural networks to parameterize the relaxed solutions so that simple back-propagation can train the model end-to-end. Our key contribution is the observation that if the relaxed objective satisfies entry-wise concavity, a low optimization loss guarantees the quality of the final integral solutions. This observation significantly broadens the applicability of the previous framework inspired by Erdos' probabilistic method. In particular, this observation can guide the design of objective models in applications where the objectives are not given explicitly while requiring being modeled in prior. We evaluate our framework by solving a synthetic graph optimization problem, and two real-world applications including resource allocation in circuit design and approximate computing. Our framework largely outperforms the baselines based on na\"{i}ve relaxation, reinforcement learning, and Gumbel-softmax tricks.
• Abstract（参考訳）: 組合せ最適化(co)問題を解決するために機械学習を使うことは、特にデータがラベルされていない場合、難しい。 本研究は,CO問題に対する教師なし学習フレームワークを提案する。 私たちのフレームワークは、標準的な緩和プラスラウンドアプローチに従っており、緩和されたソリューションをパラメータ化するためにニューラルネットワークを採用しています。 我々の重要な貢献は、緩和された目的がエントリーワイドな凹凸を満たすならば、低い最適化損失は最終積分解の品質を保証するという観察である。 この観察は、erdosの確率的手法に触発された以前のフレームワークの適用可能性を大きく広げる。 特に、この観察は、事前にモデル化する必要がある間、目的が明示的に与えられていないアプリケーションにおける客観的モデルの設計を導くことができる。 我々は,回路設計における資源配分と近似計算を含む2つの実世界の応用を,合成グラフ最適化問題の解法により評価する。 我々のフレームワークは,na\"{i}ve緩和,強化学習,Gumbel-softmaxトリックに基づくベースラインよりも優れています。

関連論文リスト

• An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
  本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。 重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。 フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
  論文  参考訳（メタデータ） (2024-08-16T02:07:34Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes [52.818579746354665]
  本稿では,ニューラルネットワークを一般化し,トランスフォーマーアーキテクチャを用いて獲得関数を学習する,エンド・ツー・エンドの差別化可能な最初のメタBOフレームワークを提案する。 我々は、この強化学習(RL)によるエンドツーエンドのフレームワークを、ラベル付き取得データの欠如に対処できるようにします。
  論文  参考訳（メタデータ） (2023-05-25T10:58:46Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning [14.86600327306136]
  最適化のための教師なし学習(CO)の一般的なフレームワークは、出力がCOの目的を直接最適化することで問題解決をもたらすニューラルネットワーク(NN)を訓練することである。 本研究では,COにおける教師なし学習の新たな目的について提案する。この学習の目的は,直接的な解決策を与えるのではなく,将来の問題インスタンスの優れた初期化を探すことである。 微調整前のモデルが与える初期解だけでも, 様々な評価条件下では, ベースラインを著しく上回る結果が得られます。
  論文  参考訳（メタデータ） (2023-01-08T22:14:59Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。 特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
  論文  参考訳（メタデータ） (2022-03-15T19:21:31Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。 このアプローチは多くの実装と最適化の課題をもたらします。 提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
  論文  参考訳（メタデータ） (2021-03-18T14:26:26Z)
• Automatically Learning Compact Quality-aware Surrogates for Optimization Problems [55.94450542785096]
  未知パラメータで最適化問題を解くには、未知パラメータの値を予測し、これらの値を用いて問題を解くための予測モデルを学ぶ必要がある。 最近の研究によると、複雑なトレーニングモデルパイプラインのレイヤーとして最適化の問題を含めると、観測されていない意思決定の繰り返しを予測することになる。 我々は,大規模最適化問題の低次元サロゲートモデルを学習することにより,解の質を向上させることができることを示す。
  論文  参考訳（メタデータ） (2020-06-18T19:11:54Z)
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs [35.14404918074861]
  本研究では,グラフ上での組合せ最適化問題に対する教師なし学習フレームワークを提案する。 エルドスの確率論的手法に触発され、ニューラルネットワークを用いて集合上の確率分布をパラメータ化する。 ネットワークが適切に選択された損失に最適化された場合、学習された分布は、制御された確率、低コストな積分解を含むことを示す。
  論文  参考訳（メタデータ） (2020-06-18T16:13:36Z)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  無線ネットワークにおけるリソース割り当てとトランシーバーは、通常最適化問題の解決によって設計される。 本稿では,変数最適化と関数最適化の両問題を解くための教師なし・教師なし学習フレームワークを紹介する。
  論文  参考訳（メタデータ） (2020-01-03T11:01:52Z)

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

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