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

• arxiv url: http://arxiv.org/abs/2410.08025v2
• Date: Fri, 11 Oct 2024 08:02:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-31 05:55:13.957669
• 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 that capture 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 (part of, e.g., transformers). Our findings reveal a challenging complexity landscape. Many queries are intractable (NP-hard, $\Sigma^p_2$-hard), remain fixed-parameter intractable (W[1]-hard) when constraining model/circuit features (e.g., depth), and are inapproximable under additive, multiplicative, and probabilistic approximation schemes. To navigate this landscape, we prove there exist transformations to tackle some of these hard problems (NP- vs. $\Sigma^p_2$-complete) with better-understood heuristics, and prove the tractability (PTIME) or fixed-parameter tractability (FPT) 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 among existing and future architectures.
• Abstract（参考訳）: ニューラルネットワークの機械学習、認知/脳科学、社会のヒンジへの応用が、回路発見による内的解釈の可能性について提案されている。 これは、実行可能なアルゴリズムオプションを経験的および理論的に探索することを要求する。 ヒューリスティックスの設計とテストの進歩にもかかわらず、そのスケーラビリティと忠実さには懸念がある。 これを解決するために,古典的・パラメータ化された計算複雑性理論を用いて回路探索について検討する:(1)説明,説明,予測,制御の余裕の観点から,回路探索クエリを推論するための概念的足場を記述する;(2)機械的説明を捉えるための包括的なクエリセットを形式化し,その分析のための形式的フレームワークを提案する;(3)多層パーセプトロン(例えば,トランスフォーマー)に対する実用的関心の複雑さの解決に使用する。 私たちの発見は、難しい複雑さの風景を明らかにします。 多くのクエリは引き込み可能(NP-hard, $\Sigma^p_2$-hard)であり、モデル/回路の特徴(例えば深さ)を制約する場合は固定パラメータ引き込み可能(W[1]-hard)であり、加法的、乗法的、確率的近似スキームでは不適応である。 この状況をナビゲートするために、よりよく理解されたヒューリスティックスを用いてこれらの難解な問題(NP-対$\Sigma^p_2$-complete)に取り組むための変換が存在することを証明し、有用な空き容量を保持するより控えめなクエリのトラクタビリティ(PTIME)または固定パラメータトラクタビリティ(FPT)を証明する。 このフレームワークは、解釈可能性クエリの範囲と限界を理解し、実行可能な選択肢を探究し、リソース要求を既存のアーキテクチャと将来のアーキテクチャと比較することを可能にする。

関連論文リスト

• Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
  完全拡張である引数の集合の確率を計算する複雑なタスクのアルゴリズムを開発する。 実験的評価は我々のアプローチの可能性を示唆している。
  論文  参考訳（メタデータ） (2024-07-06T12:08:38Z)
• 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)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。 我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。 一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
  論文  参考訳（メタデータ） (2020-06-07T14:47:07Z)

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

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