論文の概要: SAT-Based Bounded Fitting for the Description Logic ALC

• arxiv url: http://arxiv.org/abs/2507.21752v1
• Date: Tue, 29 Jul 2025 12:32:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-30 17:08:56.255008
• Title: SAT-Based Bounded Fitting for the Description Logic ALC
• Title（参考訳）: 記述論理ALCのためのSATベース境界フィッティング
• Authors: Maurice Funk, Jean Christoph Jung, Tom Voellmer,
• Abstract要約: 記述論理ALCとその構文的断片に対する有界適合性について検討する。 検討されたすべてのフラグメントに対して,基礎となるサイズ制限フィッティング問題はNP完全であることを示す。 本稿では,SATソルバに基づくALCとそのフラグメントにおける有界フィッティングの実装について述べる。
• 参考スコア（独自算出の注目度）: 7.193373053157516
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bounded fitting is a general paradigm for learning logical formulas from positive and negative data examples, that has received considerable interest recently. We investigate bounded fitting for the description logic ALC and its syntactic fragments. We show that the underlying size-restricted fitting problem is NP-complete for all studied fragments, even in the special case of a single positive and a single negative example. By design, bounded fitting comes with probabilistic guarantees in Valiant's PAC learning framework. In contrast, we show that other classes of algorithms for learning ALC concepts do not provide such guarantees. Finally, we present an implementation of bounded fitting in ALC and its fragments based on a SAT solver. We discuss optimizations and compare our implementation to other concept learning tools.
• Abstract（参考訳）: 境界フィッティングは、正および負のデータ例から論理式を学ぶための一般的なパラダイムであり、最近かなりの関心を集めている。 記述論理ALCとその構文的断片に対する有界適合性について検討する。 一つの正と負の特殊な例であっても, 基礎となるサイズ制限フィッティング問題はすべての研究断片に対してNP完全であることを示す。 設計上、有界なフィッティングには、ValiantのPAC学習フレームワークの確率論的保証が伴う。 対照的に、ALC概念を学習するための他のアルゴリズムのクラスは、そのような保証を提供していない。 最後に、SATソルバに基づくALCとそのフラグメントにおける有界フィッティングの実装について述べる。 最適化について議論し、その実装を他の概念学習ツールと比較する。

関連論文リスト

• Nearly Optimal Sample Complexity for Learning with Label Proportions [54.67830198790247]
  トレーニングセットの例をバッグにグループ化する部分情報設定であるLLP(Learning from Label Proportions)について検討する。 部分的な可観測性にもかかわらず、ゴールは個々の例のレベルで小さな後悔を達成することである。 我々は, LLPの2乗損失下でのサンプル複雑性について, 標本複雑性が本質的に最適であることを示す。
  論文  参考訳（メタデータ） (2025-05-08T15:45:23Z)
• Minimum Description Length and Generalization Guarantees for Representation Learning [16.2444595840653]
  本稿では,表現学習アルゴリズムの一般化誤差の上限を導出するフレームワークを提案する。 エンコーダの入力と表現の間の相互情報ではなく、我々の新しい境界は「マルチレター」相対エントロピーを含む。 著者たちの最もよく知る限り、確立された一般化境界は、情報ボトルネック型エンコーダと表現学習のための第一種である。
  論文  参考訳（メタデータ） (2024-02-05T18:12:28Z)
• Nonparametric active learning for cost-sensitive classification [2.1756081703276]
  コスト依存型分類のための一般的な非パラメトリック能動学習アルゴリズムを設計する。 我々は、一致した(対数係数まで)下界を提供することにより、得られた上界のほぼ最適性を証明した。
  論文  参考訳（メタデータ） (2023-09-30T22:19:21Z)
• SAT-Based PAC Learning of Description Logic Concepts [18.851061569487616]
  本稿では,記述の存在下で論理概念を学習するためのスキームとして有界フィッティングを提案する。 本稿では,SATソルバをベースとした記述論理 $mathcalELHr$ のバウンドフィッティングを実装したシステム SPELL を提案し,その性能を最先端の学習者と比較する。
  論文  参考訳（メタデータ） (2023-05-15T10:20:31Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• On Guaranteed Optimal Robust Explanations for NLP Models [16.358394218953833]
  我々は,マシーン学習のための推論に基づく説明を構築し,ニューラルネットワークモデルのための局所的説明を計算する方法を開発した。 我々は,それぞれ暗黙の打撃集合と最大普遍部分集合に基づく2つの解アルゴリズムを提案する。 SST、Twitter、IMDBデータセットから、広く使用されている3つの感情分析タスクと最大100ワードのテキストに基づいてフレームワークを評価します。
  論文  参考訳（メタデータ） (2021-05-08T08:44:48Z)
• Reducing Confusion in Active Learning for Part-Of-Speech Tagging [100.08742107682264]
  アクティブラーニング(AL)は、データ選択アルゴリズムを使用して、アノテーションコストを最小限に抑えるために有用なトレーニングサンプルを選択する。 本研究では、特定の出力タグのペア間の混乱を最大に低減するインスタンスの選択問題について検討する。 提案するAL戦略は,他のAL戦略よりも有意差で優れている。
  論文  参考訳（メタデータ） (2020-11-02T06:24:58Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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