論文の概要: Pretrained Cost Model for Distributed Constraint Optimization Problems
- arxiv url: http://arxiv.org/abs/2112.04187v1
- Date: Wed, 8 Dec 2021 09:24:10 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-09 22:37:03.180184
- Title: Pretrained Cost Model for Distributed Constraint Optimization Problems
- Title（参考訳）: 分散制約最適化問題に対する事前学習コストモデル
- Authors: Yanchen Deng, Shufeng Kong, Bo An
- Abstract要約: 分散制約最適化問題(DCOP)は、最適化問題の重要なサブクラスである。
本稿では,DCOPのための新しい非巡回グラフスキーマ表現を提案し,グラフ表現を組み込むためにグラフ注意ネットワーク(GAT)を利用する。
我々のモデルであるGAT-PCMは、幅広いDCOPアルゴリズムを向上するために、オフラインで最適なラベル付きデータで事前訓練される。
- 参考スコア（独自算出の注目度）: 37.79733538931925
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Distributed Constraint Optimization Problems (DCOPs) are an important
subclass of combinatorial optimization problems, where information and controls
are distributed among multiple autonomous agents. Previously, Machine Learning
(ML) has been largely applied to solve combinatorial optimization problems by
learning effective heuristics. However, existing ML-based heuristic methods are
often not generalizable to different search algorithms. Most importantly, these
methods usually require full knowledge about the problems to be solved, which
are not suitable for distributed settings where centralization is not realistic
due to geographical limitations or privacy concerns. To address the generality
issue, we propose a novel directed acyclic graph representation schema for
DCOPs and leverage the Graph Attention Networks (GATs) to embed graph
representations. Our model, GAT-PCM, is then pretrained with optimally labelled
data in an offline manner, so as to construct effective heuristics to boost a
broad range of DCOP algorithms where evaluating the quality of a partial
assignment is critical, such as local search or backtracking search.
Furthermore, to enable decentralized model inference, we propose a distributed
embedding schema of GAT-PCM where each agent exchanges only embedded vectors,
and show its soundness and complexity. Finally, we demonstrate the
effectiveness of our model by combining it with a local search or a
backtracking search algorithm. Extensive empirical evaluations indicate that
the GAT-PCM-boosted algorithms significantly outperform the state-of-the-art
methods in various benchmarks. The pretrained model is available at
https://github.com/dyc941126/GAT-PCM.
- Abstract（参考訳）: 分散制約最適化問題(DCOP)は、複数の自律エージェント間で情報と制御が分散される組合せ最適化問題の重要なサブクラスである。
これまで、機械学習(ml)は効果的なヒューリスティックスを学習することで組合せ最適化問題を解決するために広く用いられてきた。
しかし、既存のMLベースのヒューリスティック手法は、しばしば異なる探索アルゴリズムに対して一般化できない。
最も重要なことは、これらの手法は通常解決すべき問題に関する完全な知識を必要とし、地理的制限やプライバシー上の懸念のために集中化が現実的でない分散環境には適さないことである。
一般性問題に対処するため、DCOPのための新規な非巡回グラフ表現スキーマを提案し、グラフ表現を埋め込むためにグラフ注意ネットワーク(GAT)を利用する。
我々のモデルであるGAT-PCMは、オフラインで最適なラベル付きデータを事前学習し、効率的なヒューリスティックを構築し、局所探索やバックトラック探索などの部分割り当ての品質評価が重要なDCOPアルゴリズムを広範囲に拡張する。
さらに、分散モデル推論を実現するために、各エージェントが埋め込みベクトルのみを交換し、その可聴性と複雑さを示すGAT-PCMの分散埋め込みスキーマを提案する。
最後に,ローカル検索やバックトラッキング検索アルゴリズムと組み合わせることで,モデルの有効性を実証する。
GAT-PCM-boostedアルゴリズムは様々なベンチマークで最先端の手法よりも優れていた。
事前訓練されたモデルはhttps://github.com/dyc941126/GAT-PCMで入手できる。
関連論文リスト
- Joint Graph Learning and Model Fitting in Laplacian Regularized
Stratified Models [5.933030735757292]
ラプラシア正規化成層モデル(Laplacian regularized Stratified Model、LRSM)は、サブプロブレムの明示的または暗黙的なネットワーク構造を利用するモデルである。
本稿では,LRSMにおけるグラフ重みの重要性と感度を示し,その感度が任意に大きいことを示す。
本稿では,1つの最適化問題を解くことで,モデルパラメータを適合させながらグラフを共同学習する汎用的手法を提案する。
論文 参考訳（メタデータ） (2023-05-04T06:06:29Z) - Regularization and Optimization in Model-Based Clustering [4.096453902709292]
k-平均アルゴリズムの変種は、本質的に同じ球面ガウスの混合と、そのような分布から大きく逸脱するデータに適合する。
一般のGMMに対してより効率的な最適化アルゴリズムを開発し、これらのアルゴリズムと正規化戦略を組み合わせ、過度な適合を避ける。
これらの結果から, GMM と k-means 法の間の現状に新たな光を当て, 一般 GMM をデータ探索に利用することが示唆された。
論文 参考訳（メタデータ） (2023-02-05T18:22:29Z) - End-to-End Pareto Set Prediction with Graph Neural Networks for
Multi-objective Facility Location [10.130342722193204]
施設配置問題(FLP)は、サプライチェーンやロジスティクスで広く見られるNPハード最適化問題の典型的なクラスである。
本稿では,システム全体のコストを同時に最小化し,システム信頼性を最大化する多目的施設配置問題(MO-FLP)について考察する。
ノードとエッジの暗黙グラフ表現を学習するために、2つのグラフニューラルネットワークを構築した。
論文 参考訳（メタデータ） (2022-10-27T07:15:55Z) - Exploiting Temporal Structures of Cyclostationary Signals for
Data-Driven Single-Channel Source Separation [98.95383921866096]
単一チャネルソース分離(SCSS)の問題点について検討する。
我々は、様々なアプリケーション領域に特に適するサイクロ定常信号に焦点を当てる。
本稿では,最小MSE推定器と競合するU-Netアーキテクチャを用いたディープラーニング手法を提案する。
論文 参考訳（メタデータ） (2022-08-22T14:04:56Z) - Late Fusion Multi-view Clustering via Global and Local Alignment
Maximization [61.89218392703043]
マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。
既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。
これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
論文 参考訳（メタデータ） (2022-08-02T01:49:31Z) - A Differentiable Approach to Combinatorial Optimization using Dataless
Neural Networks [20.170140039052455]
我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。
特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
論文 参考訳（メタデータ） (2022-03-15T19:21:31Z) - Multi-Task Learning on Networks [0.0]
マルチタスク学習コンテキストで発生する多目的最適化問題は、特定の特徴を持ち、アドホックな方法を必要とする。
この論文では、入力空間の解は、関数評価に含まれる知識をカプセル化した確率分布として表現される。
確率分布のこの空間では、ワッサーシュタイン距離によって与えられる計量が与えられ、モデルが目的関数に直接依存しないような新しいアルゴリズムMOEA/WSTを設計することができる。
論文 参考訳（メタデータ） (2021-12-07T09:13:10Z) - Conservative Objective Models for Effective Offline Model-Based
Optimization [78.19085445065845]
計算設計の問題は、合成生物学からコンピュータアーキテクチャまで、様々な場面で発生している。
本研究では,分布外入力に対する接地的目標の実際の値を低くする目的関数のモデルを学習する手法を提案する。
COMは、様々なMBO問題に対して、既存のメソッドの実装と性能の面では単純である。
論文 参考訳（メタデータ） (2021-07-14T17:55:28Z) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。
我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。
コア最適化問題の実用的なパラメトリゼーションを提供する。
論文 参考訳（メタデータ） (2021-07-08T18:01:02Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
半教師付き学習における簡単なメタ学習アルゴリズムを提案する。
その結果,提案アルゴリズムは最先端の手法に対して良好に動作することがわかった。
論文 参考訳（メタデータ） (2020-07-08T08:48:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。