論文の概要: The Computational Complexity of Circuit Discovery for Inner Interpretability

• arxiv url: http://arxiv.org/abs/2410.08025v3
• Date: Tue, 01 Apr 2025 14:16:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-02 20:27:04.299476
• Title: The Computational Complexity of Circuit Discovery for Inner Interpretability
• Title（参考訳）: 内部解釈可能性のための回路探索の計算複雑性
• Authors: Federico Adolfi, Martina G. Vilas, Todd Wareham,
• Abstract要約: 我々は古典的およびパラメータ化された計算複雑性理論を用いて回路発見を研究する。 私たちの発見は、難しい複雑さの風景を明らかにします。 このフレームワークは、解釈可能性クエリの範囲と限界を理解するのに役立ちます。
• 参考スコア（独自算出の注目度）: 0.30723404270319693
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Many proposed applications of neural networks in machine learning, cognitive/brain science, and society hinge on the feasibility of inner interpretability via circuit discovery. This calls for empirical and theoretical explorations of viable algorithmic options. Despite advances in the design and testing of heuristics, there are concerns about their scalability and faithfulness at a time when we lack understanding of the complexity properties of the problems they are deployed to solve. To address this, we study circuit discovery with classical and parameterized computational complexity theory: (1) we describe a conceptual scaffolding to reason about circuit finding queries in terms of affordances for description, explanation, prediction and control; (2) we formalize a comprehensive set of queries for mechanistic explanation, and propose a formal framework for their analysis; (3) we use it to settle the complexity of many query variants and relaxations of practical interest on multi-layer perceptrons. Our findings reveal a challenging complexity landscape. Many queries are intractable, remain fixed-parameter intractable relative to model/circuit features, and inapproximable under additive, multiplicative, and probabilistic approximation schemes. To navigate this landscape, we prove there exist transformations to tackle some of these hard problems with better-understood heuristics, and prove the tractability or fixed-parameter tractability of more modest queries which retain useful affordances. This framework allows us to understand the scope and limits of interpretability queries, explore viable options, and compare their resource demands on existing and future architectures.
• Abstract（参考訳）: ニューラルネットワークの機械学習、認知/脳科学、社会のヒンジへの応用が、回路発見による内的解釈の可能性について提案されている。 これは、実行可能なアルゴリズムオプションを経験的および理論的に探索することを要求する。 ヒューリスティックスの設計とテストの進歩にもかかわらず、そのスケーラビリティと忠実さには懸念がある。 これを解決するために,古典的・パラメータ化された計算複雑性理論を用いて回路探索について検討する:(1)説明,説明,予測,制御の余裕の観点から,回路探索クエリを推論するための概念的足場を記述する;(2)機械的説明のための包括的なクエリセットを定式化し,その分析のための形式的フレームワークを提案する;(3)多数のクエリ変異の複雑性を解決し,多層パーセプトロンに対する実践的関心の緩和を図る。 私たちの発見は、難しい複雑さの風景を明らかにします。 多くのクエリは抽出可能であり、モデル/回路の特徴に対して固定パラメータが抽出可能であり、加法的、乗法的、確率的近似スキームの下では不適応である。 この状況をナビゲートするために、よりよく理解されたヒューリスティックスを用いてこれらの難解な問題に対処する変換が存在することを証明し、有用なアベイランスを保持するより控えめなクエリのトラクタビリティや固定パラメータのトラクタビリティを証明する。 このフレームワークは、解釈可能性クエリの範囲と限界を理解し、実行可能な選択肢を探究し、既存のアーキテクチャと将来のアーキテクチャにおけるリソース要求を比較します。

関連論文リスト

• Why Reasoning Matters? A Survey of Advancements in Multimodal Reasoning (v1) [66.51642638034822]
  推論は人間の知性の中心であり、多様なタスクにまたがる構造化された問題解決を可能にする。 大規模言語モデル(LLM)の最近の進歩は、算術、常識、記号領域における推論能力を大幅に向上させてきた。 本稿では,テキストおよびマルチモーダルLLMにおける推論手法の簡潔かつ洞察に富んだ概要について述べる。
  論文  参考訳（メタデータ） (2025-04-04T04:04:56Z)
• Complexity Control Facilitates Reasoning-Based Compositional Generalization in Transformers [10.206921909332006]
  本研究では,コンポジションタスクにおけるトランスフォーマーの振舞いのメカニズムについて検討する。 複雑性制御戦略は,分布外(推論に基づく解)を一般化するプリミティブレベルのルールを学習するか,あるいは記憶されたマッピング(メモリベースの解)にのみ依存するかに影響を及ぼす。
  論文  参考訳（メタデータ） (2025-01-15T02:54:52Z)
• A Compositional Atlas for Algebraic Circuits [35.95450187283255]
  クエリの大規模なクラスは、半環上の基本演算子(アグリゲーション、製品、および要素ワイドマッピング)の組み合わせに対応することを示す。 分析を応用して、このような多くの合成クエリに対して、新しいトラクタビリティ条件を導出する。
  論文  参考訳（メタデータ） (2024-12-07T00:51:46Z)
• Make LLMs better zero-shot reasoners: Structure-orientated autonomous reasoning [52.83539473110143]
  本稿では,Large Language Models (LLM) の質問をよりよく理解するための構造指向分析手法を提案する。 複雑な質問応答タスクの信頼性をさらに向上するために,多エージェント推論システム,構造指向自律推論エージェント(SARA)を提案する。 大規模な実験により,提案システムの有効性が検証された。
  論文  参考訳（メタデータ） (2024-10-18T05:30:33Z)
• Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
  完全拡張である引数の集合の確率を計算する複雑なタスクのアルゴリズムを開発する。 実験的評価は我々のアプローチの可能性を示唆している。
  論文  参考訳（メタデータ） (2024-07-06T12:08:38Z)
• Prompt-fused framework for Inductive Logical Query Answering [31.736934787328156]
  本稿では,Pro-QEという問合せ対応のプロンプトフューズフレームワークを提案する。 論理的クエリにおける未知のエンティティの問題に,我々のモデルがうまく対処できることが示される。
  論文  参考訳（メタデータ） (2024-03-19T11:30:30Z)
• Hierarchical Invariance for Robust and Interpretable Vision Tasks at Larger Scales [54.78115855552886]
  本稿では、畳み込みニューラルネットワーク(CNN)のような階層型アーキテクチャを用いて、オーバーコンプリート不変量を構築する方法を示す。 オーバーコンプリート性により、そのタスクはニューラルアーキテクチャサーチ(NAS)のような方法で適応的に形成される。 大規模で頑健で解釈可能な視覚タスクの場合、階層的不変表現は伝統的なCNNや不変量に対する効果的な代替物とみなすことができる。
  論文  参考訳（メタデータ） (2024-02-23T16:50:07Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。 具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。 コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
  論文  参考訳（メタデータ） (2023-08-29T17:22:39Z)
• Explainable Equivariant Neural Networks for Particle Physics: PELICAN [51.02649432050852]
  PELICANは、新しい置換同変であり、ローレンツ不変アグリゲーターネットワークである。 本稿では,タグ付け(分類)とローレンツ発泡トップクォークの再構成(回帰)の両文脈におけるPELICANアルゴリズムアーキテクチャについて述べる。 PELICANの適用範囲を、クォーク開始時とグルーオン開始時とを識別するタスクに拡張し、5種類のジェットを対象とするマルチクラス同定を行う。
  論文  参考訳（メタデータ） (2023-07-31T09:08:40Z)
• Learnability with PAC Semantics for Multi-agent Beliefs [38.88111785113001]
  推論と帰納の緊張は、おそらく哲学、認知、人工知能といった分野において最も根本的な問題である。 Valiant氏は、学習の課題は推論と統合されるべきである、と認識した。 古典的な包含よりも弱いが、クエリに応答する強力なモデル理論のフレームワークを可能にする。
  論文  参考訳（メタデータ） (2023-06-08T18:22:46Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。 これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。 提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
  論文  参考訳（メタデータ） (2023-04-14T11:35:35Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  本稿では,ニューラルネットワーク演算子から知識グラフの埋め込みを分解する,複雑な問合せ応答のためのフレームワークを提案する。 クエリグラフの上に、局所的な原子式上のワンホップ推論とグローバル論理的推論を結びつける論理メッセージパッシングニューラルネットワーク(LMPNN)を提案する。 我々のアプローチは、最先端のニューラルCQAモデルをもたらす。
  論文  参考訳（メタデータ） (2023-01-21T02:34:06Z)
• Successive Prompting for Decomposing Complex Questions [50.00659445976735]
  最近の研究は、大規模言語モデル(LM)の機能を活用して、数ショットで複雑な質問応答を行う。 そこでは、複雑なタスクを単純なタスクに繰り返し分解し、それを解決し、最終解を得るまでプロセスを繰り返します。 我々の最良のモデル(逐次プロンプト付き)は、DROPデータセットの数ショットバージョンにおいて、5%の絶対F1の改善を実現します。
  論文  参考訳（メタデータ） (2022-12-08T06:03:38Z)
• Computational Complexity of Segmentation [0.0]
  認知システムの能力の仕様は、しばしば、探索空間とサブ計算の複雑さに関する未検討の直観的な仮定によって形成される。 直感に反する可能性のある硬さと探索空間サイズに関する2つの結果集合を証明した。
  論文  参考訳（メタデータ） (2022-01-31T10:33:03Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• CausalCity: Complex Simulations with Agency for Causal Discovery and Reasoning [68.74447489372037]
  本稿では,因果探索と反事実推論のためのアルゴリズムの開発を目的とした,高忠実度シミュレーション環境を提案する。 私たちの作業の中核となるコンポーネントは、複雑なシナリオを定義して作成することが簡単になるような、テキストの緊急性を導入することです。 我々は3つの最先端の手法による実験を行い、ベースラインを作成し、この環境の可利用性を強調する。
  論文  参考訳（メタデータ） (2021-06-25T00:21:41Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。 我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。 一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
  論文  参考訳（メタデータ） (2020-06-07T14:47:07Z)

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

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