論文の概要: Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning
- arxiv url: http://arxiv.org/abs/2604.23377v1
- Date: Sat, 25 Apr 2026 16:51:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-28 17:12:07.304564
- Title: Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning
- Title（参考訳）: ニューロシンボリックラーニングにおける推論ショートカットの制約に基づく解析
- Authors: Akihiro Takemura, Katsumi Inoue, Masaaki Nishino,
- Abstract要約: 我々は制約満足度問題として推論ショートカットを定式化する。
本研究では,与えられた制約セットが意図した概念マッピングを一意に決定するかどうかを検証するASPベースのアルゴリズムを開発する。
また, ショートカットフリー性を決定することはcoNP完全であり, ショートカットのカウントは#P完全であり, 最小の修復はNP完全である。
- 参考スコア（独自算出の注目度）: 10.5155061359458
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Neurosymbolic systems can satisfy logical constraints during learning without achieving the intended concept-label correspondence; this is a problem known as reasoning shortcuts. We formalize reasoning shortcuts as a constraint satisfaction problem and investigate under which conditions concept mappings are uniquely determined by the constraints. We prove that a discrimination property (requiring that no valid concept mapping can be transformed into another valid mapping by swapping two concept values) is necessary for shortcut-freeness under bijective mappings, but demonstrate via a counterexample that it is insufficient even when the constraint graph is connected. We develop an ASP-based algorithm that verifies whether a given constraint set uniquely determines the intended concept mapping, with proven soundness and completeness. When shortcuts are detected, a greedy repair algorithm eliminates them by augmenting the constraint set, converging in at most $k$ iterations, where $k$ is the number of alternative valid mappings. We further provide a complexity classification: deciding shortcut-freeness is coNP-complete, counting shortcuts is #P-complete, and finding minimal repairs is NP-hard. We also establish sample complexity bounds showing that logarithmically many label queries suffice for disambiguation in favorable cases, while querying all ambiguous positions suffices in the worst case. Experiments across eight benchmark domains validate our approach.
- Abstract（参考訳）: ニューロシンボリックシステムは、意図された概念とラベルの対応を達成せずに、学習中に論理的制約を満たすことができる。
本稿では,制約満足度問題として推論ショートカットを定式化し,制約によって概念マッピングが一意に決定される条件について検討する。
本研究では,2つの概念値の交換によって有効概念写像が別の有効な写像に変換できないような)識別特性が,単射写像の下でのショートカット自由度に必要であることを示すが,制約グラフが接続されても不十分であることを示す反例を用いて実証する。
本研究では,与えられた制約セットが意図した概念マッピングを一意に決定するか否かを,音質と完全性で検証するASPベースのアルゴリズムを開発する。
ショートカットが検出されると、greedyの修復アルゴリズムは制約セットを増大させ、少なくとも$k$の反復で収束させることでそれらを排除し、$k$は代替の有効なマッピングの数である。
ショートカットフリー性を決定することはcoNP完全であり、ショートカットをカウントすることは#P完全であり、最小限の修理を見つけることはNP完全である。
また,複数のラベルクエリを対数的に有意なケースでは曖昧さが十分であり,最悪の場合では不明瞭な位置を問合せすることが十分であることを示す。
8つのベンチマークドメインにわたる実験は、我々のアプローチを検証する。
関連論文リスト
- Which bird does not have wings: Negative-constrained KGQA with Schema-guided Semantic Matching and Self-directed Refinement [5.784146913646395]
我々は、NEGative-Constrained (NEST) KGQAという新しいタスクを導入し、各質問は少なくとも1つの負の制約を含む。
また,既存の論理形式は否定を明瞭に表現するのにはあまり適していないため,Python形式の論理形式であるPyLFを設計する。
本稿では,複数制約の質問に特化し,セマンティック・エグゼクタビリティを確保するCUCKOOという新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2026-04-16T08:02:55Z) - OrLog: Resolving Complex Queries with LLMs and Probabilistic Reasoning [51.58235452818926]
そこで我々は,論理的推論から述語レベルの妥当性推定を分離するニューロシンボリック検索フレームワークOrLogを紹介する。
大規模言語モデル (LLM) は1つの復号のない前方通過において原子述語に対する可視性スコアを提供し、確率論的推論エンジンはクエリ満足度の後方確率を導出する。
論文 参考訳（メタデータ） (2026-01-30T15:31:58Z) - CoT-Seg: Rethinking Segmentation with Chain-of-Thought Reasoning and Self-Correction [50.67483317563736]
本稿では,段階的に考察し,必要な情報を検索し,結果を生成し,自己評価を行い,結果を洗練するシステムを提案する。
CoT-Segは、思考の連鎖推論と自己補正を組み合わせることで、推論セグメンテーションを再考する、トレーニング不要のフレームワークである。
論文 参考訳（メタデータ） (2026-01-24T11:41:54Z) - Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
CoT(Chain-of-Thought)は、問題を逐次ステップに分解することで、大きな言語モデル(LLM)の推論を促進する。
思考のシジー(Syzygy of Thoughts, SoT)は,CoTを補助的,相互関連的な推論経路を導入して拡張する新しいフレームワークである。
SoTはより深い論理的依存関係をキャプチャし、より堅牢で構造化された問題解決を可能にする。
論文 参考訳（メタデータ） (2025-04-13T13:35:41Z) - Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure [50.46052024418364]
我々は,既知報酬構造を持つバンドイット問題における欲求(探索のみ)アルゴリズムについて検討する。
我々の特徴は、任意のフィードバックで文脈的な帯域幅と対話的な意思決定にまで及ぶ。
論文 参考訳（メタデータ） (2025-03-06T01:51:11Z) - Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity,
and Robust Algorithms [31.478874616470048]
本稿では,ReLUアクティベーション機能を持つニューラルネットワークの実証的損失に対する定常性試験の計算問題について検討する。
片方向線形関数に対するある一階近似定常性の概念の検証はコ-NPハードであることが示される。
本稿では,Clarke と Fr'echet の差分で近似近距離定常性をテストするアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-23T17:26:51Z) - Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。
我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
論文 参考訳（メタデータ） (2021-05-13T18:24:30Z) - An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
過制約問題における最小限の障害制約を識別する分割・分散型診断アルゴリズム(FastDiag)を提案する。
ヒットセットの競合指向計算とfastdiagを比較し,詳細な性能解析を行う。
論文 参考訳（メタデータ） (2021-02-17T19:55:42Z) - A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。
我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。
一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
論文 参考訳（メタデータ） (2020-06-07T14:47:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。