論文の概要: Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation

• arxiv url: http://arxiv.org/abs/2202.03888v1
• Date: Tue, 8 Feb 2022 14:22:38 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-09 19:46:15.797225
• Title: Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation
• Title（参考訳）: 組合せ最適化のための文脈例からMAX-SATを学ぶ
• Authors: Mohit Kumar, Samuel Kolb, Stefano Teso, Luc De Raedt
• Abstract要約: 本稿では,文脈的事例から最適化問題を学習するための新しい設定を提案する。 これらの例は、特定の文脈において、ソリューションが十分であるかどうかを示している。 我々は,これらの特徴を持つシンプルかつパワフルな設定として,Agnostic-SATフォーマリズムを用いたフレームワークを開発した。
• 参考スコア（独自算出の注目度）: 28.922102456989464
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Combinatorial optimisation problems are ubiquitous in artificial intelligence. Designing the underlying models, however, requires substantial expertise, which is a limiting factor in practice. The models typically consist of hard and soft constraints, or combine hard constraints with an objective function. We introduce a novel setting for learning combinatorial optimisation problems from contextual examples. These positive and negative examples show - in a particular context - whether the solutions are good enough or not. We develop our framework using the MAX-SAT formalism as it is simple yet powerful setting having these features. We study the learnability of MAX-SAT models. Our theoretical results show that high-quality MAX-SAT models can be learned from contextual examples in the realisable and agnostic settings, as long as the data satisfies an intuitive "representativeness" condition. We also contribute two implementations based on our theoretical results: one leverages ideas from syntax-guided synthesis while the other makes use of stochastic local search techniques. The two implementations are evaluated by recovering synthetic and benchmark models from contextual examples. The experimental results support our theoretical analysis, showing that MAX-SAT models can be learned from contextual examples. Among the two implementations, the stochastic local search learner scales much better than the syntax-guided implementation while providing comparable or better models.
• Abstract（参考訳）: 組合せ最適化問題は人工知能においてユビキタスである。 しかし、基礎となるモデルを設計するにはかなりの専門知識が必要です。 モデルは通常、ハードな制約とソフトな制約、あるいはハードな制約と客観的な機能を組み合わせたものです。 本稿では,文脈の例から組合せ最適化問題を学習するための新しい設定を提案する。 これらの正の例と負の例は、ソリューションが十分であるかどうかという特定の文脈を示す。 MAX-SAT形式は,これらの特徴を持つシンプルで強力な設定であるため,我々のフレームワークを開発した。 MAX-SATモデルの学習性について検討する。 我々の理論的結果は、データが直感的な「表現性」条件を満たす限り、現実的かつ不可知的な設定における文脈例から、高品質のMAX-SATモデルを学習できることを示唆している。 また,2つの実装を理論的結果に基づいて提案する。一方は構文誘導合成のアイデアを利用し,他方は確率的局所探索技術を利用する。 2つの実装は、文脈例から合成モデルとベンチマークモデルを復元することで評価される。 実験結果は,max-satモデルが文脈サンプルから学習できることを示す理論解析を支持する。 2つの実装のうち、確率的局所探索学習者は、同等またはより良いモデルを提供しながら、構文誘導実装よりもはるかにスケールする。

関連論文リスト

• Promises and Pitfalls of Generative Masked Language Modeling: Theoretical Framework and Practical Guidelines [74.42485647685272]
  GMLM(Generative Masked Language Models)に焦点を当てる。 我々は,マルコフ連鎖の入力として使用されるマスキングにより,データ分布の条件付き確率に適合するモデルを訓練し,モデルからサンプルを抽出する。 我々は,T5モデルを並列デコーディングに適応させ,最小品質の犠牲を伴って機械翻訳における2～3倍の高速化を実現した。
  論文  参考訳（メタデータ） (2024-07-22T18:00:00Z)
• DeTriever: Decoder-representation-based Retriever for Improving NL2SQL In-Context Learning [19.93800175353809]
  DeTrieverは、隠れた状態の重み付けを学習する新しいデモ検索フレームワークである。 提案手法は1ショットNL2タスクにおける最先端のベースラインを大幅に上回る。
  論文  参考訳（メタデータ） (2024-06-12T06:33:54Z)
• RetICL: Sequential Retrieval of In-Context Examples with Reinforcement Learning [53.52699766206808]
  In-Context Learning (RetICL) のための検索式を提案する。 RetICLは数学用語の問題解決と科学的質問応答のタスクに基づいて評価し,一貫した性能や一致,学習可能なベースラインを示す。
  論文  参考訳（メタデータ） (2023-05-23T20:15:56Z)
• W2SAT: Learning to generate SAT instances from Weighted Literal Incidence Graphs [11.139131079925113]
  W2SATは、現実世界/産業インスタンスから固有の構造と特性を学ぶことによってSAT式を生成するフレームワークである。 Weighted Literal Incidence Graph (WLIG)と呼ばれる新しいSAT表現を導入する。 WLIGからSAT問題への復号化は、新しい丘登り最適化法で重なり合う斜角を見つけることをモデル化する。
  論文  参考訳（メタデータ） (2023-02-01T06:30:41Z)
• Mutual Exclusivity Training and Primitive Augmentation to Induce Compositionality [84.94877848357896]
  最近のデータセットは、標準的なシーケンス・ツー・シーケンスモデルにおける体系的な一般化能力の欠如を露呈している。 本稿では,セq2seqモデルの振る舞いを分析し,相互排他バイアスの欠如と全例を記憶する傾向の2つの要因を同定する。 広範に使用されている2つの構成性データセット上で、標準的なシーケンス・ツー・シーケンスモデルを用いて、経験的改善を示す。
  論文  参考訳（メタデータ） (2022-11-28T17:36:41Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  カラムワイズモデルを適応的かつ自動的に構成するための一般化反復計算フレームワークを提案する。 既製の学習者,シミュレータ,インターフェースを備えた具体的な実装を提供する。
  論文  参考訳（メタデータ） (2022-06-15T19:10:35Z)
• Optimizing Binary Decision Diagrams with MaxSAT for classification [3.2894524838755608]
  説明可能な人工知能への関心の高まりは、解釈可能な機械学習(ML)モデルの必要性を動機付けている。 近年、従来の手法の弱点を克服するために、そのようなモデルを計算するためのいくつかの正確な方法が提案されている。 本稿ではまず,最適なバイナリ決定図(BDD)を学習するためのSATモデルを提案する。 次に、符号化をMaxSATモデルに上げ、限られた深さで最適なBDDを学習します。 最後に、MaxSATモデルを介して見つけたBDDの互換性のあるサブツリーをマージする手法を導入することにより、フラグメンテーションの問題に取り組む。
  論文  参考訳（メタデータ） (2022-03-21T23:17:37Z)
• A Lagrangian Duality Approach to Active Learning [119.36233726867992]
  トレーニングデータのサブセットのみをラベル付けするバッチアクティブな学習問題を考察する。 制約付き最適化を用いて学習問題を定式化し、各制約はラベル付きサンプルにモデルの性能を拘束する。 数値実験により,提案手法は最先端の能動学習法と同等かそれ以上に機能することを示した。
  論文  参考訳（メタデータ） (2022-02-08T19:18:49Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Preference Modeling with Context-Dependent Salient Features [12.403492796441434]
  本稿では,各項目の特徴について,ノイズの多いペアワイド比較から,項目集合のランキングを推定する問題を考察する。 私たちのキーとなる観察は、他の項目から分離して比較した2つの項目は、機能の健全なサブセットのみに基づいて比較できるということです。
  論文  参考訳（メタデータ） (2020-02-22T04:05:16Z)

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

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