論文の概要: Neural Learning of One-of-Many Solutions for Combinatorial Problems in
Structured Output Spaces
- arxiv url: http://arxiv.org/abs/2008.11990v2
- Date: Sun, 4 Apr 2021 15:36:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-24 07:18:53.103557
- Title: Neural Learning of One-of-Many Solutions for Combinatorial Problems in
Structured Output Spaces
- Title（参考訳）: 構造化出力空間における組合せ問題に対する一対一解のニューラルラーニング
- Authors: Yatin Nandwani, Deepanshu Jindal, Mausam and Parag Singla
- Abstract要約: 複数のソリューションの存在に消極的であることは、トレーニング能力を著しく損なう可能性がある、と私たちは主張する。
本稿では、既存の予測ネットワークをRL問題に適用し、解乗法を扱う汎用学習フレームワークを提案する。
- 参考スコア（独自算出の注目度）: 20.101005623256626
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent research has proposed neural architectures for solving combinatorial
problems in structured output spaces. In many such problems, there may exist
multiple solutions for a given input, e.g. a partially filled Sudoku puzzle may
have many completions satisfying all constraints. Further, we are often
interested in finding any one of the possible solutions, without any preference
between them. Existing approaches completely ignore this solution multiplicity.
In this paper, we argue that being oblivious to the presence of multiple
solutions can severely hamper their training ability. Our contribution is two
fold. First, we formally define the task of learning one-of-many solutions for
combinatorial problems in structured output spaces, which is applicable for
solving several problems of interest such as N-Queens, and Sudoku. Second, we
present a generic learning framework that adapts an existing prediction network
for a combinatorial problem to handle solution multiplicity. Our framework uses
a selection module, whose goal is to dynamically determine, for every input,
the solution that is most effective for training the network parameters in any
given learning iteration. We propose an RL based approach to jointly train the
selection module with the prediction network. Experiments on three different
domains, and using two different prediction networks, demonstrate that our
framework significantly improves the accuracy in our setting, obtaining up to
21 pt gain over the baselines.
- Abstract（参考訳）: 近年、構造化出力空間における組合せ問題を解くためのニューラルネットワークが提案されている。
そのような問題の多くは、ある入力に対して複数の解が存在する可能性があり、例えば、部分満たした数足パズルは、すべての制約を満たす多くの完了を持つ。
さらに、私たちはしばしば、それらの間の好みなしに、可能なソリューションのどれかを見つけることに興味があります。
既存のアプローチはこの解の多重性を完全に無視する。
本稿では,複数の解が存在することに服従すれば,その訓練能力が著しく損なわれると論じる。
我々の貢献は2つある。
まず,N-Queens や Sudoku といった関心事の解決に有効である構造化出力空間における組合せ問題に対する一対一の解を求めるタスクを正式に定義する。
次に,既存の予測ネットワークを組合せ問題に適用し,解の多重性を扱う汎用学習フレームワークを提案する。
我々のフレームワークは選択モジュールを使用し、任意の学習イテレーションにおいて、ネットワークパラメータのトレーニングに最も効果的である解を動的に決定することを目的としています。
予測ネットワークを用いて選択モジュールを協調訓練するためのRLに基づく手法を提案する。
3つの異なる領域の実験と2つの異なる予測ネットワークを用いて、我々のフレームワークが我々の設定の精度を大幅に向上し、ベースラインよりも最大21ptのゲインを得ることを示した。
関連論文リスト
- Towards a Generic Representation of Combinatorial Problems for
Learning-Based Approaches [2.2526069385327316]
近年,問題解決に学習ベースのアプローチを使うことへの関心が高まっている。
この課題は、対象とする問題を学習アルゴリズムと互換性のある構造に符号化することにある。
既存の多くの研究は、しばしばグラフの形で、テキストトグラフニューラルネットワークの利点を活用するために問題固有の表現を提案している。
本稿では,学習に基づくアプローチにおける問題を完全に包括的に表現することを提唱する。
論文 参考訳（メタデータ） (2024-03-09T22:28:46Z) - PMGDA: A Preference-based Multiple Gradient Descent Algorithm [12.600588000788214]
マルチタスク学習のような、多くの多目的機械学習アプリケーションにおいて、意思決定者の所定の好みに合ったソリューションを見つけることが望ましい。
本稿では,意思決定者の好みに合ったソリューションを見つけるための,新しい予測と修正のためのフレームワークを提案する。
論文 参考訳（メタデータ） (2024-02-14T11:27:31Z) - OFA$^2$: A Multi-Objective Perspective for the Once-for-All Neural
Architecture Search [79.36688444492405]
once-for-All(OFA)は、異なるリソース制約を持つデバイスのための効率的なアーキテクチャを探索する問題に対処するために設計された、ニューラルネットワーク検索(NAS)フレームワークである。
我々は,探索段階を多目的最適化問題として明示的に考えることにより,効率の追求を一歩進めることを目指している。
論文 参考訳（メタデータ） (2023-03-23T21:30:29Z) - Learning To Dive In Branch And Bound [95.13209326119153]
グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。
我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
論文 参考訳（メタデータ） (2023-01-24T12:01:45Z) - AMS-Net: Adaptive Multiscale Sparse Neural Network with Interpretable
Basis Expansion for Multiphase Flow Problems [8.991619150027267]
本研究では、物理過程の学習に応用可能な適応スパース学習アルゴリズムを提案し、大きなスナップショット空間を与えられた解のスパース表現を得る。
基本関数の情報は損失関数に組み込まれており、複数の時間ステップにおけるダウンスケール縮小次数解と参照解との差を最小限に抑える。
複雑なアプリケーションにおける提案手法の有効性と解釈性を示すため, 2相多相流問題に対してより数値的な実験を行った。
論文 参考訳（メタデータ） (2022-07-24T13:12:43Z) - Improved Training of Physics-Informed Neural Networks with Model
Ensembles [81.38804205212425]
我々は、PINNを正しい解に収束させるため、解区間を徐々に拡大することを提案する。
すべてのアンサンブルのメンバーは、観測されたデータの近くで同じ解に収束する。
提案手法は, 得られた解の精度を向上させることができることを示す。
論文 参考訳（メタデータ） (2022-04-11T14:05:34Z) - What's Wrong with Deep Learning in Tree Search for Combinatorial
Optimization [8.879790406465556]
本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。
また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。
木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
論文 参考訳（メタデータ） (2022-01-25T17:37:34Z) - Discovering Diverse Solutions in Deep Reinforcement Learning [84.45686627019408]
強化学習アルゴリズムは通常、特定のタスクの単一のソリューションを学ぶことに限定される。
連続的あるいは離散的な低次元潜在変数に条件付きポリシーを訓練することにより、無限に多くの解を学習できるRL法を提案する。
論文 参考訳（メタデータ） (2021-03-12T04:54:31Z) - Learning by Fixing: Solving Math Word Problems with Weak Supervision [70.62896781438694]
数学用語問題(mwps)の従来のニューラルネットワークソルバは、完全な監視によって学習され、多様なソリューションを生み出すことができない。
MWPを学習するためのテキスト弱教師付きパラダイムを提案する。
この手法は最終回答のアノテーションのみを必要とし、単一の問題に対して様々な解決策を生成できる。
論文 参考訳（メタデータ） (2020-12-19T03:10:21Z) - Pareto Multi-Task Learning [53.90732663046125]
マルチタスク学習は複数の相関タスクを同時に解くための強力な方法である。
異なるタスクが互いに衝突する可能性があるため、すべてのタスクを最適化するひとつのソリューションを見つけることは、しばしば不可能である。
近年,マルチタスク学習を多目的最適化として活用することにより,タスク間のトレードオフが良好である1つのパレート最適解を求める方法が提案されている。
論文 参考訳（メタデータ） (2019-12-30T08:58:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。