論文の概要: Solving Normalized Cut Problem with Constrained Action Space
- arxiv url: http://arxiv.org/abs/2505.13986v1
- Date: Tue, 20 May 2025 06:33:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-21 14:49:52.784161
- Title: Solving Normalized Cut Problem with Constrained Action Space
- Title（参考訳）: 拘束作用空間を用いた正規化切断問題の解法
- Authors: Qize Jiang, Linsey Pang, Alice Gatti, Mahima Aggarwa, Giovanna Vantin, Xiaosong Ma, Weiwei Sun, Sanjay Chawla,
- Abstract要約: 本稿では、制約されたアクション空間を用いて、正規化されたカット問題を事前定義されたテンプレートインスタンスへ誘導する最初のRLソリューションを提案する。
輸送ネットワークを例として、ウェッジとリングのグラフ分割を形作るWedge and Ring Transformerを作成します。
- 参考スコア（独自算出の注目度）: 13.415654235179693
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Reinforcement Learning (RL) has emerged as an important paradigm to solve combinatorial optimization problems primarily due to its ability to learn heuristics that can generalize across problem instances. However, integrating external knowledge that will steer combinatorial optimization problem solutions towards domain appropriate outcomes remains an extremely challenging task. In this paper, we propose the first RL solution that uses constrained action spaces to guide the normalized cut problem towards pre-defined template instances. Using transportation networks as an example domain, we create a Wedge and Ring Transformer that results in graph partitions that are shaped in form of Wedges and Rings and which are likely to be closer to natural optimal partitions. However, our approach is general as it is based on principles that can be generalized to other domains.
- Abstract（参考訳）: 強化学習(Reinforcement Learning, RL)は、主に問題インスタンス全体にわたって一般化可能なヒューリスティックを学習する能力のために、組合せ最適化問題を解決する重要なパラダイムとして登場した。
しかし、組合せ最適化問題の解をドメインの適切な結果に導いてくれる外部知識の統合は、依然として極めて難しい課題である。
本稿では、制約されたアクション空間を用いて、正規化されたカット問題を事前定義されたテンプレートインスタンスへ誘導する最初のRLソリューションを提案する。
輸送ネットワークを例として用いた Wedge and Ring Transformer は,Wedges や Rings の形をしたグラフ分割を生み出す。
しかし、我々のアプローチは、他のドメインに一般化できる原則に基づいているため、一般的である。
関連論文リスト
- Towards graph neural networks for provably solving convex optimization problems [5.966097889241178]
提案するMPNNフレームワークは,検証可能な実現可能性保証を用いて凸最適化問題を解決する。
実験の結果,提案手法は既存の神経ベースラインよりも解の質や実現可能性に優れていた。
論文 参考訳（メタデータ） (2025-02-04T16:11:41Z) - Evolving Generalizable Parallel Algorithm Portfolios via Domain-Agnostic Instance Generation [27.138566940625385]
一般化は、データからトレーニングする際の中核的な目的である。
並列アルゴリズムポートフォリオ(PAP)とインスタンス人口を同時に進化させることによって、共進化的アプローチはこの課題に対処する。
本研究は,パラメタライズドサーチ(DACE)のドメインに依存しない共進化という,汎用的で既成のPAP構築手法を提案する。
論文 参考訳（メタデータ） (2025-01-06T10:29:48Z) - Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳（メタデータ） (2024-03-06T04:43:22Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳（メタデータ） (2023-01-28T01:50:42Z) - Path Regularization: A Convexity and Sparsity Inducing Regularization
for Parallel ReLU Networks [75.33431791218302]
本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。
我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
論文 参考訳（メタデータ） (2021-10-18T18:00:36Z) - Offline Model-Based Optimization via Normalized Maximum Likelihood
Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。
この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。
我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文 参考訳（メタデータ） (2021-02-16T06:04:27Z) - Reversible Action Design for Combinatorial Optimization with
Reinforcement Learning [35.50454156611722]
強化学習(rl)は、これらの問題に取り組むための新しいフレームワークとして最近登場した。
最先端の実証性能を示すだけでなく、様々な種類のCOPに一般化する汎用RLフレームワークを提案します。
論文 参考訳（メタデータ） (2021-02-14T18:05:42Z) - Efficient Consensus Model based on Proximal Gradient Method applied to
Convolutional Sparse Problems [2.335152769484957]
我々は、勾配近似(PG)アプローチに基づく効率的なコンセンサスアルゴリズムの理論解析を導出し、詳述する。
提案アルゴリズムは、異常検出タスクに対する別の特別な畳み込み問題にも適用できる。
論文 参考訳（メタデータ） (2020-11-19T20:52:48Z) - Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
本稿では,RL(Deep Reinforcement Learning)を用いた制約付き最適化問題に対処する枠組みを提案する。
我々は、その定式化における制約に対処するために、Neural Combinatorial Optimization(NCO)理論を拡張した。
その文脈では、ソリューションは環境との相互作用に基づいて反復的に構築されます。
論文 参考訳（メタデータ） (2020-06-22T03:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。