論文の概要: Graph Pruning for Enumeration of Minimal Unsatisfiable Subsets

• arxiv url: http://arxiv.org/abs/2402.15524v1
• Date: Mon, 19 Feb 2024 20:03:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-03 19:17:38.180161
• Title: Graph Pruning for Enumeration of Minimal Unsatisfiable Subsets
• Title（参考訳）: 最小不満足なサブセット列挙のためのグラフプルーニング
• Authors: Panagiotis Lymperopoulos and Liping Liu
• Abstract要約: バイナリ制約の最小不満足な部分集合(MUS)を見つけることは、過剰制約されたシステムの不適合性解析において一般的な問題である。 MUS列挙を高速化するために,学習モデルを用いて公式をプルーする手法を提案する。
• 参考スコア（独自算出の注目度）: 4.59143974279554
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding Minimal Unsatisfiable Subsets (MUSes) of binary constraints is a common problem in infeasibility analysis of over-constrained systems. However, because of the exponential search space of the problem, enumerating MUSes is extremely time-consuming in real applications. In this work, we propose to prune formulas using a learned model to speed up MUS enumeration. We represent formulas as graphs and then develop a graph-based learning model to predict which part of the formula should be pruned. Importantly, our algorithm does not require data labeling by only checking the satisfiability of pruned formulas. It does not even require training data from the target application because it extrapolates to data with different distributions. In our experiments we combine our algorithm with existing MUS enumerators and validate its effectiveness in multiple benchmarks including a set of real-world problems outside our training distribution. The experiment results show that our method significantly accelerates MUS enumeration on average on these benchmark problems.
• Abstract（参考訳）: 双対制約の最小不満足な部分集合(MUS)を見つけることは、過制約系の不実現性解析において一般的な問題である。 しかし、問題の指数関数的探索空間のため、museの列挙は実際のアプリケーションでは極めて時間がかかる。 本研究では,mus列挙を高速化するために学習モデルを用いたprune式を提案する。 式をグラフとして表現し、グラフベースの学習モデルを開発し、公式のどの部分を刈り取るべきかを予測する。 重要なことに、このアルゴリズムは、刈り取った公式の満足度だけをチェックすることで、データラベリングを必要としない。 異なる分散を持つデータに外挿するため、ターゲットアプリケーションからのトレーニングデータさえ必要としない。 実験では,本アルゴリズムを既存のMUS列挙子と組み合わせ,トレーニング分布外の実世界の問題を含む複数のベンチマークで有効性を検証する。 実験の結果,本手法はベンチマーク問題において平均でmuse列挙を著しく高速化することが示された。

関連論文リスト

• On the Performance of Empirical Risk Minimization with Smoothed Data [59.3428024282545]
  経験的リスク最小化(Empirical Risk Minimization、ERM)は、クラスがiidデータで学習可能であれば、サブ線形誤差を達成できる。 We show that ERM can able to achieve sublinear error when a class are learnable with iid data。
  論文  参考訳（メタデータ） (2024-02-22T21:55:41Z)
• Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
  ケルネル学習とBayesian Spike-and-Slab pres (KBASS)に基づく新しい方程式探索法を提案する。 カーネルレグレッションを用いてターゲット関数を推定する。これはフレキシブルで表現力があり、データ空間やノイズに対してより堅牢である。 我々は,効率的な後部推論と関数推定のための予測伝搬予測最大化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-10-09T03:55:09Z)
• Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
  グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。 いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
  論文  参考訳（メタデータ） (2023-02-13T15:13:22Z)
• Minimax rate of consistency for linear models with missing values [0.0]
  多くの実世界のデータセットでは、複数のソースが集約され、本質的に欠落した情報(センサーの故障、調査における未回答の疑問...)が欠落する。 本稿では,広範に研究された線形モデルに焦点をあてるが,不足する値が存在する場合には,非常に難しい課題であることが判明した。 最終的には、多くの学習タスクを解決し、入力機能の数を指数関数的にすることで、現在の現実世界のデータセットでは予測が不可能になる。
  論文  参考訳（メタデータ） (2022-02-03T08:45:34Z)
• Gaussian Graphical Model Selection for Huge Data via Minipatch Learning [1.2891210250935146]
  グラフィカルモデル選択の問題を解決するために,MPGraph (Minipatch Graph) 推定器を提案する。 MPGraphは、観測とノードの両方の小さなランダムなサブセットに適合する閾値グラフ推定器の一般化である。 本アルゴリズムは有限サンプルグラフ選択の整合性を実現する。
  論文  参考訳（メタデータ） (2021-10-22T21:06:48Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  グラフ構造化データに対する半教師付き学習(SSL)は、多くのネットワークサイエンスアプリケーションに現れる。 グラフ上の学習を効率的に管理するために,近年,グラフニューラルネットワーク(GNN)の変種が開発されている。 実際に成功したにも拘わらず、既存の手法のほとんどは、不確実な結節属性を持つグラフを扱うことができない。 ノイズ測定によって得られたデータに関連する分布の不確実性によっても問題が発生する。 分散ロバストな学習フレームワークを開発し,摂動に対する定量的ロバスト性を示すモデルを訓練する。
  論文  参考訳（メタデータ） (2021-10-20T14:23:54Z)
• Imputation-Free Learning from Incomplete Observations [73.15386629370111]
  本稿では,不備な値を含む入力からの推論をインプットなしでトレーニングするIGSGD法の重要性について紹介する。 バックプロパゲーションによるモデルのトレーニングに使用する勾配の調整には強化学習(RL)を用いる。 我々の計算自由予測は、最先端の計算手法を用いて従来の2段階の計算自由予測よりも優れている。
  論文  参考訳（メタデータ） (2021-07-05T12:44:39Z)
• Evaluating State-of-the-Art Classification Models Against Bayes Optimality [106.50867011164584]
  正規化フローを用いて学習した生成モデルのベイズ誤差を正確に計算できることを示す。 われわれの手法を用いて、最先端の分類モデルについて徹底的な調査を行う。
  論文  参考訳（メタデータ） (2021-06-07T06:21:20Z)
• Continuous Optimization Benchmarks by Simulation [0.0]
  最適化アルゴリズムのテスト、比較、チューニング、理解にはベンチマーク実験が必要である。 以前の評価から得られたデータは、ベンチマークに使用される代理モデルのトレーニングに使用することができる。 本研究では,スペクトルシミュレーションにより連続最適化問題のシミュレーションが可能であることを示す。
  論文  参考訳（メタデータ） (2020-08-14T08:50:57Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。 テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。 以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-22T21:12:31Z)

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

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