技術的サマリー：ニューロンに対する保証付き最適な構成的説明

問題定義

構成的説明は、ニューロンの受容野活性化と特定の概念（物体、テクスチャなど）との空間的整合性を、論理規則を用いて記述することを目的とする。核心的な目標は、概念の集合 $L_1$ から構成される論理式 $L$ を見つけ出し、ニューロンの活性化マップと概念アノテーションとの間の交差率（Intersection over Union: IoU）を最大化することである。

しかし、すべての可能な概念の組み合わせの探索空間は、組み合わせ的に爆発する。先行研究（例：Mu and Andreas, 2020）は、構造的な仮定を通じて探索空間を制限し、ビームサーチを採用することでこの問題に対処してきた。ビームサーチは計算効率的であるが、最適性の理論的保証は提供しない。したがって、生成された説明が真に最良の整合性なのか、それとも単なる局所最適解に過ぎないのか、またそれらが真の解（グラウンドトゥルース）からどの程度乖離しているのかは依然として不明瞭である。この不確実性は、現在の解釈可能性手法の信頼性を制限し、近似誤差を低減するアルゴリズムの開発を妨げている。

手法

著者らは、計算上の実現可能性を犠牲にすることなく、標準的な仮定によって定義された全状態空間にわたる保証付き最適な構成的説明を計算するフレームワークを提案する。この手法は、以下の 3 つの主要な構成要素からなる。

1. IoU 指標の分解（dIoU）

本論文は、整合性の質を支配する基本的な量へと IoU スコアを分解する手法を導入する。これは以下の 3 つの仮定に依存する。

• 仮定 1: 説明内の概念は互いに異なる。
• 仮定 2: 概念は逐次的に組み合わせられる。
• 仮定 3: 論理演算子は00-保存的である（すなわち、2 つの 0 から 1 を生成することはできない）。これには、標準的なビットごとの演算子：OR（$\lor$）、AND（$\land$）、AND NOT（$\land \neg$）が含まれる。

IoU は、ニューロン活性化行列 $N$ と概念行列 $M$ から導出される 4 つの主要な集合を用いて再定式化される。

• ユニーク/交差（$I_U, I_C$）: ニューロンがユニークな概念アノテーション、または共通の概念アノテーションに対して発火する場所。
• ユニーク/追加（$E_U, E_C$）: 概念がアノテーションされているがニューロンは発火しない場所。

この分解（dIoU）により、論理演算子が IoU スコアの分子（交差）と分母（和集合）に与える影響を微細に分析することが可能になる。

2. ヒューリスティック推定

探索を誘導するために、著者らは任意の部分ラベル $L$ と、$L$ を最大長さ $n$ まで拡張する任意の潜在的な経路に対する、最大および最小の可能な IoU を推定するヒューリスティックを設計する。

• ラベル量: ヒューリスティックは、Disjoint Matrix（非重複行列）を用いて重複を確認し、ラベル $L$ に概念 $k$ を追加することの影響を推定する。演算子が非重複か重複しているかに基づき、交差と追加（Extras）の範囲を導出する。
• 経路量: ラベルをさらに拡張する可能性を推定するために、本手法はTopおよびBottベクトルを利用する。これらのベクトルは、データセット全体における各量の $t$ 番目に高い値と低い値の累積和を格納しており、アルゴリズムが残り概念を追加することで達成可能な最良および最悪のケースの改善を見積もることを可能にする。
• 集約計算対サンプル計算: 精度と効率のバランスを取るため、ヒューリスティックは初期の枝刈りおよびフロンティア管理には集約計算（データセット全体での合計）を使用し、有望なノードの推定値を精緻化するにはサンプルベースの計算（画像ごと）を予約する。

3. 最適探索アルゴリズム

著者らは、最適性を保証するベストファースト探索アルゴリズム（アルゴリズム 1）を提案する。

1. 初期化: すべての原子概念に対して正確な量を計算し、ヒューリスティックを用いて経路を推定する。
2. フロンティア管理: 推定された最大 IoU（$dIoU_{max}$）でソートされたノードの優先度付きキューを維持する。
3. 枝刈り: これまでに発見された最小推定値のグローバル最大値（$MinIoU$）を下回る$dIoU_{max}$ を持つノードを削除することで、フロンティアを動的に枝刈りする。
4. 展開と精緻化:
   • 最も高い推定値を持つノードをポップする。
   • 推定値が集約型の場合、サンプルベースの推定値に精緻化する。
   • 冗長性を削減するために論理的等価規則を適用する。
   • ノードが最終ラベルの場合、正確な IoU を計算する。それが新たな最良の場合、グローバル最良を更新し、部分ラベルを共有する他のノードの推定値を更新するために正確な量を逆伝播させる。
   • ノードが最終でない場合、すべての可能な概念と演算子を連結して展開し、範囲を再推定してフロンティアに挿入する。

このアルゴリズムは、許容可能（最大可能な IoU を過小評価しない）であり、かつ完全であることが証明されており、大域的最適解を見つけることを保証する。

主要な貢献

1. 形式的保証: 標準的な仮定によって spans される全状態空間における構成的説明の最適性に対する理論的保証を提供する、初のフレームワークである。
2. 分解（dIoU）: 整合性を支配する基本的な量を特定し、論理演算子の影響を正確に特徴づけることを可能にする、IoU 指標の新たな分解。
3. 最適アルゴリズム: 網羅的なビームサーチと同等の時間で最適説明を計算する探索アルゴリズムであり、全状態空間の探索を実現可能にする。
4. ヒューリスティック誘導型ビームサーチ: 提案された分解とヒューリスティックによって誘導されるビームサーチのバリアントであり、より高い柔軟性を提供しつつ、以前のランタイム性能と同等かそれ以上を達成する。

結果

著者らは、Places365 で訓練された ResNet18、AlexNet、DenseNet161 モデルに対して、複雑さが異なる 3 つのデータセット（Cityscapes、Ade20K、Broden）を用いて手法を評価した。

• 実現可能性: 最適アルゴリズムは、すべての複雑さレベルにおいて、実行可能なランタイム内で最適解を正常に見つける。ビームサーチよりも広い状態空間を探索するが、そのランタイムはバニラビームサーチと同等のままである（例：高複雑度で約 5768 秒/単位、対バニラビームサーチで約 5929 秒）。一方、単純な幅優先探索では数億時間が必要となる。
• ビームサーチの非最適性: 分析により、重なり合う概念が関与する場合、以前にビームサーチで得られた説明の**10–40%**が非最適であることが明らかになった。
  • カテゴリ 1（最も一般的）: 説明は概念と IoU の両方で異なる。ビームサーチは、特殊なユニットを記述する複雑な AND/AND NOT の組み合わせを含む説明を見つけることがよく失敗する。
  • カテゴリ 2: 説明は概念を共有するが、論理構造が異なり、異なる IoU スコアにつながる（例：((A OR B) AND C) 対 ((A AND C) OR B)）。
  • カテゴリ 3: 説明は同じ IoU を共有するが、構造が異なる。ビームサーチは、決して共起しない非重複概念に依存する「未検証」の説明を生成する可能性があるが、最適アルゴリズムは正しい整合性を特定する。
• ヒューリスティックの性能: 提案されたヒューリスティックによって誘導されるビームサーチのバリアントは、訪問した状態数においてベースライン（MMESH、バニラビーム）を上回り、説明の長さやビームサイズに対してより効果的にスケーリングする。また、ヒューリスティック計算のために空間テンソルを格納する必要がないため、メモリ要件が低い。

意義と主張

本論文は、グラウンドトゥルースの最適解を特定することが以下の点で重要であると主張する。

1. 信頼性: 非最適な近似によって引き起こされるニューロンの挙動に関する誤解を招く見方を防ぐ。
2. データセットの特性評価: ビームサーチが最適解に収束する場合、未研究のデータセットの性質を明らかにする。
3. アルゴリズム開発: 近似誤差を低減する新しいアルゴリズムの開発を導くためのベンチマークを提供する。

著者らは、この手法が空間情報に依存しない（MMESH とは異なり）、と強調しており、そのヒューリスティックはコンピュータビジョン以外の分野にも適用可能である可能性がある。彼らは、この研究を、最適な単一概念を見つける Network Dissection と、以前は複雑さのために最適性を犠牲にしていた構成的説明との間のギャップを埋める理論的基盤として位置づけている。論文は、最適アルゴリズムは重要な一歩であるが、今後の研究では、00-保存的でない演算子やトランスフォーマーのような他のアーキテクチャに対してこれらの保証を拡張する必要があると結論づけている。