論文の概要: An Integer Linear Programming Framework for Mining Constraints from Data
- arxiv url: http://arxiv.org/abs/2006.10836v2
- Date: Fri, 11 Jun 2021 04:34:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-19 09:51:53.324342
- Title: An Integer Linear Programming Framework for Mining Constraints from Data
- Title（参考訳）: データから制約をマイニングするための整数線形プログラミングフレームワーク
- Authors: Tao Meng and Kai-Wei Chang
- Abstract要約: データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
- 参考スコア（独自算出の注目度）: 81.60135973848125
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Structured output prediction problems (e.g., sequential tagging, hierarchical
multi-class classification) often involve constraints over the output label
space. These constraints interact with the learned models to filter infeasible
solutions and facilitate in building an accountable system. However, although
constraints are useful, they are often based on hand-crafted rules. This raises
a question -- \emph{can we mine constraints and rules from data based on a
learning algorithm?}
In this paper, we present a general framework for mining constraints from
data. In particular, we consider the inference in structured output prediction
as an integer linear programming (ILP) problem. Then, given the coefficients of
the objective function and the corresponding solution, we mine the underlying
constraints by estimating the outer and inner polytopes of the feasible set. We
verify the proposed constraint mining algorithm in various synthetic and
real-world applications and demonstrate that the proposed approach successfully
identifies the feasible set at scale.
In particular, we show that our approach can learn to solve 9x9 Sudoku
puzzles and minimal spanning tree problems from examples without providing the
underlying rules. Our algorithm can also integrate with a neural network model
to learn the hierarchical label structure of a multi-label classification task.
Besides, we provide a theoretical analysis about the tightness of the polytopes
and the reliability of the mined constraints.
- Abstract（参考訳）: 構造化された出力予測問題(例えば、シーケンシャルタグ付け、階層的多クラス分類)は、しばしば出力ラベル空間上の制約を伴う。
これらの制約は学習したモデルと相互作用し、実現不可能なソリューションをフィルタリングし、説明可能なシステムの構築を容易にする。
しかし、制約は有用であるが、しばしば手作りの規則に基づいている。
学習アルゴリズムに基づいたデータから制約やルールをマイニングできますか?
本稿では,データから制約をマイニングするための一般的な枠組みを提案する。
特に、構造化出力予測における推論を整数線形計画問題(ilp)として考える。
次に,対象関数の係数と対応する解を仮定し,実現可能な集合の外側および内側のポリトープを推定することにより,基礎となる制約を掘り出す。
提案手法は,様々な合成・実世界の応用において制約マイニングアルゴリズムを検証し,提案手法が大規模に実現可能であることを示す。
特に,本手法では,9×9のスドクパズルの解法を学習し,木問題を例から最小限に分散させる。
また,ニューラルネットワークモデルと統合することで,マルチラベル分類タスクの階層的ラベル構造を学習する。
さらに,ポリトープの密着性と,採掘された制約の信頼性に関する理論的解析を行った。
関連論文リスト
- Learning Model Agnostic Explanations via Constraint Programming [8.257194221102225]
解釈可能な機械学習は、不透明な分類器による予測を人間に理解可能な言葉で説明するという、繰り返し発生する課題に直面している。
本稿では,このタスクを制約最適化問題(Constraint Optimization Problem)として,入力データインスタンスの最小誤差と境界サイズの説明と,ブラックボックスが生成したサンプルの集合を求める。
提案手法は,様々なデータセット上で実証的に評価し,最先端のアンカー法よりも統計的に優れていることを示す。
論文 参考訳（メタデータ） (2024-11-13T09:55:59Z) - Semantic Objective Functions: A distribution-aware method for adding logical constraints in deep learning [4.854297874710511]
制約付き学習と知識蒸留技術は有望な結果を示した。
本稿では,機械学習モデルに知識を付加した論理的制約を組み込むロスベース手法を提案する。
本手法は,論理的制約のある分類タスクを含む,様々な学習課題において評価する。
論文 参考訳（メタデータ） (2024-05-03T19:21:47Z) - Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
Deep Unrolling(ディープ・アンローリング)は、トレーニング可能なニューラルネットワークの層に切り捨てられた反復アルゴリズムをアンロールする、新たな学習最適化手法である。
アンロールネットワークの収束保証と一般化性は、いまだにオープンな理論上の問題であることを示す。
提案した制約の下で訓練されたアンロールアーキテクチャを2つの異なるアプリケーションで数値的に評価する。
論文 参考訳（メタデータ） (2023-12-25T18:51:23Z) - A New Computationally Simple Approach for Implementing Neural Networks
with Output Hard Constraints [5.482532589225552]
ニューラルネットワークの出力値に厳密な凸制約を課す新しい手法を提案する。
マッピングは、出力の制約のある追加のニューラルネットワーク層によって実装される。
提案手法は,出力ベクトルだけでなく,入力による共同制約にも制約が課される場合に,単純に拡張される。
論文 参考訳（メタデータ） (2023-07-19T21:06:43Z) - Neural Fields with Hard Constraints of Arbitrary Differential Order [61.49418682745144]
我々は、ニューラルネットワークに厳しい制約を課すための一連のアプローチを開発する。
制約は、ニューラルネットワークとそのデリバティブに適用される線形作用素として指定することができる。
私たちのアプローチは、広範囲の現実世界のアプリケーションで実証されています。
論文 参考訳（メタデータ） (2023-06-15T08:33:52Z) - Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。
特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。
以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
論文 参考訳（メタデータ） (2022-02-08T16:39:57Z) - Constrained Machine Learning: The Bagel Framework [5.945320097465419]
制約付き機械学習問題は、学習したモデルが正確で、制約を尊重しなければならない問題である。
本研究の目的は,制約付き機械学習問題のモデリング能力を最適化から組み込むことで拡張することである。
機械学習には特定の要件があるため、仮説の空間を分割する拡張テーブル制約も提案する。
論文 参考訳（メタデータ） (2021-12-02T10:10:20Z) - Adaptive Discretization in Online Reinforcement Learning [9.560980936110234]
離散化に基づくアルゴリズムを設計する際の2つの大きな疑問は、離散化をどのように生成し、いつそれを洗練するかである。
オンライン強化学習のための木に基づく階層分割手法の統一的理論的解析を行う。
我々のアルゴリズムは操作制約に容易に適応し、我々の理論は3つの面のそれぞれに明示的な境界を与える。
論文 参考訳（メタデータ） (2021-10-29T15:06:15Z) - CoreDiag: Eliminating Redundancy in Constraint Sets [68.8204255655161]
最小コア(最小非冗長制約集合)の決定に利用できる新しいアルゴリズムを提案する。
このアルゴリズムは、冗長性の度合いが高い分散知識工学シナリオにおいて特に有用である。
本手法の適用可能性を示すために, 商業的構成知識ベースを用いた実証的研究を実施した。
論文 参考訳（メタデータ） (2021-02-24T09:16:10Z) - Local Propagation in Constraint-based Neural Network [77.37829055999238]
ニューラルネットワークアーキテクチャの制約に基づく表現について検討する。
本稿では,いわゆるアーキテクチャ制約を満たすのに適した簡単な最適化手法について検討する。
論文 参考訳（メタデータ） (2020-02-18T16:47:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。