🤖 machine learning

CQD-SHAP: Explainable Complex Query Answering via Shapley Values

本論文は、不完全な知識グラフに対する複雑なクエリ回答において、各クエリ部分の回答ランキングへの寄与度を定量化することで、既存のブラックボックス型およびニューロシンボリックモデルの解釈性の限界に対処する、協力ゲーム理論のシャプレー値を利用した新しいフレームワークであるCQD-SHAPを提案する。

原著者： Parsa Abbasi, Stefan Heindorf

公開日 2026-06-23

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Parsa Abbasi, Stefan Heindorf

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

全体像：「ブラックボックス」の探偵

想像してみてください。そこには、本と本が紐でつながれた、巨大で散らかった図書館（知識グラフ）があります。時として、その図書館からはページが抜け落ちていたり、本そのものが丸ごとなくなっていたりすることもあります（これは不完全性と呼ばれます）。

「ハリー・ポッターの著者は誰？」といった単純な質問をすれば、コンピュータは通常、その紐を辿るだけで答えを見つけることができます。しかし、もし次のような複雑な質問をされたらどうでしょう？ 「糖尿病を治療し、かつ腎毒性を引き起こす薬はどれか？」

この質問に答えるために、コンピュータは2つのことを行う必要があります。

紐を辿る（記号的アプローチ）：既存の図書館の中に、確実に「糖尿病を治療する薬」であり、かつ「腎毒性を引き起こす薬」であると記されているものを探します。
欠けている繋がりを推測する（ニューラルアプローチ）：図書館が不完全であるため、コンピュータは「賢い推測器」（ニューラルネットワーク）を使用して、本来あるべきなのにまだ書き込まれていない繋がりを推論します。

問題は、この「賢い推測器」がブラックボックスであることです。それは答えのリスト（例：「インスリン」）を提示してくれますが、なぜその答えを選んだのかを教えてくれません。図書館に明記されていたからインスリンを選んだのでしょうか？それとも、図書館にはその事実が書かれていないものの、コンピュータが「インスリンは腎毒性と関連がある」と判断して推測したからでしょうか？

CQD-SHAPは、このブラックボックスを開け、質問の各要素が最終的な答えにどれだけ貢献したかを正確に説明するために設計された新しいツールです。

コアとなるアイデア：「チームスコア」の比喩

著者らは、ゲーム理論の概念であるシャプレー値（Shapley Values）を使用しています。これは、グループプロジェクトにおいて、チームの生徒たち（質問のアトム／原子）が協力して、成績（答えのランキング）を目指す様子をイメージすると分かりやすいでしょう。

例として挙げた質問（「糖尿病のための薬かつ腎毒性のための薬」）には、2人の「生徒」（アトム）がいます。

生徒A：「糖尿病のための薬」
生徒B：「腎毒性のための薬」

最終的な成績（「インスリン」の順位）は、両方の生徒がいかにうまくパフォーマンスを上げたかに依存します。しかし、生徒Aと生徒B、それぞれにどれだけの功績があるのでしょうか？

CQD-SHAPは、公平な審判として機能します。それは何千回ものミニ実験を行い、スコアを算出します。

シナリオ1：生徒Aが「図書館の歩行（記号的）」を行い、生徒Bが「賢い推測器（ニューラル）」を使う。
シナリオ2：生徒Aが「賢い推測器」を使い、生徒Bが「図書館の歩行」を行う。
シナリオ3：両者が「図書館の歩行」を行う。
シナリオ4：両者が「賢い推測器」を使う。

これらのシナリオを比較することで、CQD-SHAPは「賢い推測器」が各生徒の最終成績をどれだけ向上させたかを正確に計算します。

「アハー！」の瞬間：なぜこれが重要なのか

この論文は、この手法が驚くべき事実を明らかにすると主張しています。時として、「賢い推測器」が主導権を握っていることもあれば、逆に結果を台無しにしていることもあるのです。

「うるさい隣人」の比喩：
特定の家（答え）を探しているとしましょう。

**「図書館の歩行」**は、公式の住所録を読むようなものです。正確ですが、古い本であればその家が載っていないこともあります。
**「賢い推測器」**は、近所の知り合いに聞くようなものです。彼らは、たとえ住所録に載っていなくても、その家が存在することを知っているかもしれません。

CQD-SHAPは次のように教えてくれるかもしれません。

「『インスリン』という答えに対して、『腎毒性』の部分は、賢い推測器が繋がりを推測したことで、大幅なブースト（+450ポイント）を得ました。しかし、『糖尿病』の部分は、賢い推測器が混乱して間違った隣人を提案してしまったため、わずかなペナルティ（-10ポイント）を受けています。」

CQD-SHAHがなければ、あなたは単に「インスリン」がリストのトップにあるのを見て、コンピュータが100%確信していると思い込んでしまうでしょう。しかし、CQD-SHAPがあれば、こう気づけます。*「待てよ、コンピュータは腎毒性の部分についてはほとんど推測に基づいている。この事実は再確認すべきだ」*と。

検証方法（「ストレス・テスト」）

著者らは、FreebaseやNELLなどの実世界のデータセットを用い、様々な種類の複雑な質問（「AND」を含むものや「OR」を含むものなど）でテストを行いました。

彼らは、どの部分が重要かを推測する他の手法（例えば、最初の部分を選ぶ、最後の部分を選ぶ、あるいはスコアが最も低い部分を選ぶといった方法）と、自分たちの手法を比較しました。

結果：

必要条件の説明（Necessary Explanations）：最も重要な部分から「賢い推測器」を取り除いたとき、答えの順位が大幅に下がれば、その部分は不可欠です。CQD-SHAPは、他の手法よりもこれらの決定的な部分を特定することに長けていました。
十分条件の説明（Sufficient Explanations）：最も重要な部分にのみ「賢い推測器」を使用した場合、答えの順位が大幅に上がれば、その部分は十分な根拠となります。ここでも、CQD-SHAPが勝利しました。

簡単に言えば、CQD-SHAPは、なぜある答えが高い順位になったのか（あるいは低くなったのか）を説明するために、質問の「正しい」部分を指摘できる唯一の手法なのです。

主な要点

答えだけでなく「なぜ」が重要：これは、複雑なクエリがなぜ特定の回答を返したのかを、論理的なステップごとに分解して説明します。
「推測力」を測定する：ニューラルネットワークによる「欠けている事実を推測する能力」が、最終的なランキングにどれほど貢献したか（あるいは悪影響を与えたか）を具体的に数値化します。
数学的に公平である：シャプレー値という厳密な数学的公式を用いることで、「貢献度」が各質問要素に対して公平に分配されることを保証します。
エラーを検知する：高い順位の回答が、実は弱くノイズの多い推測に基づいていることを明らかにできるため、ユーザーがシステムを盲信しすぎるのを防ぐことができます。

これが「ではない」こと（論文の記述に基づく）

これは病気を治したり、患者を診断したりすることを主張しているわけではありません。「薬」の例は、システムの仕組みを示すためのメタファーに過ぎません。
これは医師や弁護士に取って代わるものだとは言っていません。これは、AIモデルがどのように考えているかを理解するためのツールです。
これは、あらゆるAIの「ブラックボックス問題」を解決すると主張しているのではなく、この特定のタイプの複雑な質問回答システムに関するものです。

要約すると、CQD-SHAPは、AI探偵のための「スコアカード」として機能する透明化ツールです。どの手がかり（クエリの各部分）が「事実」であり、どれが「賢い推測」であったのかを明確に示すことで、ユーザーが何を信頼すべきかを判断できるようにします。

技術要約: CQD-SHAP

問題提起

知識グラフ（KG）における複雑なクエリ回答（CQA）は、単純なリンク予測を超え、マルチホップ推論や論理演算子（連言、選言）を必要とするクエリを扱う。CQD（Complex Query Decomposition）のようなニューロシンボリックな手法は、実世界のKGの不完全性を対処するために欠損リンクを推論する形で登場したが、これらは主にブラックボックスモデルとして機能している。既存の説明可能性手法は、単一ホップの予測に対する重要なトリプルやパスの特定に焦力しており、複雑なクエリに直接適用することはできない。さらに、現在のニューロシンボリックCQA手法には、特定の回答のランキングに対する異なるクエリ構成要素（アトム）の具体的な寄与度に関する透明性が欠けている。この不透明性は、ユーザーの信頼、デバッグ、およびドメインエキスパートによるKGのギャップ特定やクエリの洗練を妨げる要因となっている。

手法: CQD-SHAP

本論文は、協力ゲーム理論のシャープレイ値（Shapley values）を用いて、各クエリアトムが特定の回答エンティティのランキングに与える寄与を定量化することにより、ニューロシンボリックCQAモデル（具体的にはCQD）の結果を説明するフレームワークであるCQD-SHAPを提案する。

コアとなる定義

プレイヤー: 複雑なクエリ $Q$ の構成要素であるアトムは、協力ゲームにおけるプレイヤーとして扱われる。
提携（Coalitions）: 集合 $S$ に含まれるアトムはニューラル・アプローチ（リンク予測器による欠損リンクの推論）を用いて実行される一方、残りのアトムはシンボリック・アプローチ（KG内の観測された事実への厳密な依存）を用いて実行される。
価値関数: ターゲットエンティティ $e_i$ $e_{i}$ に対する提携 $S$ $S$ の価値は、** $\Delta$ $Δ$ Rank 量化関心（QoI）**によって定義される。これは、クエリ全体を純粋にシンボリックに実行した場合と比較して、アトム $S$ $S$ をニューラルに実行した際に $e_i$ $e_{i}$ のランキング順位がどの程度改善するかを測定するものである。
- 定式化： $val_{e_i}(Q_S) = r_i(Q_{\emptyset}) - r_i(Q_S)$ 。ここで、 $r_i$ はフィルタリングされた設定におけるエンティティ $e_i$ のランクである。
シャープレイ値の計算: 特定のアトム $a$ の寄与は、他の全アトムからなるあらゆる可能な提携における、そのアトムの平均的な限界寄与として計算される。これは、効率性（すべての寄与の総和が、フルニューラル実行によって得られた総ランク改善量に等しいこと）を含む、シャープレイの公理を満たしている。

実行の詳細

ニューラル実行: リンク予測器（例：CQD由来）を使用してエンティティにスコアを割り当て、不完全なグラフ上での推論を可能にする。
シンボリック実行: 観測された（不完全な）KG上でグラフ探索を行い、存在する事実には定数スコアを、存在しない事実には低いスコアを割り当てる。
厳密な計算: 複雑なクエリのアトム数は通常少ない（ $\le 4$ ）ため、本論文では近似を用いず、厳密なシャープレイ値を計算する。

主な貢献

CQAにおける初のシャープレイ値に基づく説明: 著者らの知る限り、シャープレイ値を用いてニューロシンボリックCQAモデルを説明する初めてのアプローチである。
アトムレベルの説明の形式的定義: リンク予測で使用されるトリプルレベルやパスレベルの説明とは区別される、クエリアトムレベルでの形式的な説明フレームワークを定義した。
新しい指標 (CQD-SHAP): 特定のアトムのニューラル実行が、シンボリック実行と比較して、ターゲットの回答のランキングにどの程度寄与するかを定量化する方法を導入した。
評価基準の再定義: リンク予測における**必要性（Necessary）および十分性（Sufficient）**の概念をCQAドメインへと拡張した：
- 必要性: 最も重要なアトムをシンボリック実行に置き換えると、回答のランキングが大幅に低下する（ $\Delta$ MRRで測定）。
- 十分性: 最も重要なアトムのみをニューラルに実行し（他はシンボリック）、フルシンボリックのベースラインと比較してランキングを大幅に向上させる。

実験結果

著者らは、FB15k-237、NELL995、およびそれらのより困難なバリアント（+H）を用い、様々なクエリタイプ（射影、交差、和集合）に対してCQD-SHAPを評価した。

性能: CQD-SHAPは、必要性および十分性の両方の評価シナリオにおいて、すべてのベースライン（First, Last, Random, Score-based selection）を一貫して上回った。
- 必要性のシナリオでは、CQD-SHAPは（NELL995の2uクエリにおいて）MRRを最大**45.70%**減少させ、最良のベースラインよりも大幅に減少させた。
- 十分性のシナリオでは、（NELL995+Hの2uクエリにおいて）MRRを最大**58.90%**増加させた。
クエリ構造への感度: この手法は、射影クエリよりも交差クエリ（例：3i, 4i）において高い有効性を示した。著者らは、これをt-normを用いた交差の構造的性質（一つの決定的な分岐が強力なフィルタとして機能する一方で、射影クエリには代替経路が存在することが多いこと）に起因すると考えている。
効率性: シャープレイ値のNP困難な性質にもかかわらず、アトム数が少ないため、低レイテンシ（データセットに応じてクエリ・回答ペアあたり平均約30〜140ミリ秒）での厳密な計算が可能であった。
洞察: 分析により、最も重要なアトムが必ずしも「欠損リンク」であるとは限らないことが明らかになった。場合によっては、KG内に存在する事実に対応するアトムが、埋め込みの近接性や他の部分のニューラル実行によって導入されたノイズにより、ランキングの主要な推進力となることがある。

重要性と主張

本論文は、CQD-SHAPがニューロシンボリックなクエリ回答を解釈するための、数学的に厳密かつ効果的な方法を提供すると主張している。シャープレイの公理を満たすことで、クエリ構成要素への公平な帰属を保証している。著者らは、このアプローチが以下の点に寄与すると述べている：

どのクエリ部分が推論された知識に大きく依存しているかを明らかにすることで、ドメインエキスパートがKGのギャップを特定するのを助ける。
どのアトムが最終的なランキングに最も影響を与えるかを示すことで、クエリのデバッグを支援する。
ニューラル予測器が、不完全なデータをどのように活用しているかについて、シンボリックな検索と比較した透明性のある視点を提供する。

著者らは、これが複雑なクエリ回答の結果を説明するためにシャープレイ値を適用した最初の研究であることを明示しており、既存のリンク予測の説明手法の限界を超えたものであるとしている。また、現在の研究はローカルな説明（単一の回答）に焦点を当てているが、将来的にはグローバルな説明や、これらの値を人間が理解しやすい形にするための自然言語生成への展開を含んでいると述べている。