Abstract
複雑な機械学習モデルは概して線形表現によって特徴を符号化する、ということが広く信じられている。これは、解釈可能性に関する膨大な研究の基礎となる仮説である。しかし、解釈可能な特徴を抽出するうえでの重要な課題は、それらの特徴が重ね合わせ（superposition）の中に存在する点である。本研究では、学習理論的な観点から、重ね合わせの中にある特徴を抽出するという問題を扱う。まず、次の基本的な設定から出発する。すなわち、関数
\[ f(x)=\sum_{i=1}^n \sigma_i(v_i^\top x), \]
に対してクエリ（問い合わせ）アクセスが与えられているものとする。ここで、各単位ベクトル v_i は特徴方向を符号化しており、
\sigma_i:\R\to\R は任意の応答関数であり、目標は v_i と関数 f を復元することである。
学習理論の観点では、重ね合わせとは
\emph{過完全（overcomplete）な領域} を指し、特徴数が基底となる次元よりも大きい（すなわち n > d）という状況である。この条件は、典型的なアルゴリズム的アプローチにとってとりわけ困難であることが分かっている。我々の主結果は、f へのノイズを含むオラクルアクセスから、応答が縮退しないすべての特徴方向を効率よく同定し、関数 f を再構成するクエリアルゴリズムである。重要な点として、このアルゴリズムは、関連する先行研究のすべてよりもかなり一般的な設定で動作する。我々は本質的に任意の重ね合わせを許し、さらに i
eq j に対して v_i, v_j がほぼ同一でないことのみを要求し、また一般の応答関数
\sigma_i を許容する。大づかみに言えば、我々のアルゴリズムは、探索空間を反復的に絞り込むことで隠された方向 v_i を見つけるための方法を、フーリエ空間での探索として導入する。
