論文の概要: Provably Extracting the Features from a General Superposition
- arxiv url: http://arxiv.org/abs/2512.15987v1
- Date: Wed, 17 Dec 2025 21:42:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-19 18:10:31.833622
- Title: Provably Extracting the Features from a General Superposition
- Title（参考訳）: 一般仮定から特徴を抽出する可能性
- Authors: Allen Liu,
- Abstract要約: ブラックボックス・クエリー・アクセスによる重ね合わせにおける学習機能の設定について検討する。
我々の主な成果は、応答が非退化している全ての特徴方向を識別する効率的なクエリアルゴリズムである。
- 参考スコア（独自算出の注目度）: 6.431258907649152
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: It is widely believed that complex machine learning models generally encode features through linear representations, but these features exist in superposition, making them challenging to recover. We study the following fundamental setting for learning features in superposition from black-box query access: we are given query access to a function \[ f(x)=\sum_{i=1}^n a_i\,σ_i(v_i^\top x), \] where each unit vector $v_i$ encodes a feature direction and $σ_i:\mathbb{R} \rightarrow \mathbb{R}$ is an arbitrary response function and our goal is to recover the $v_i$ and the function $f$. In learning-theoretic terms, superposition refers to the overcomplete regime, when the number of features is larger than the underlying dimension (i.e. $n > d$), which has proven especially challenging for typical algorithmic approaches. Our main result is an efficient query algorithm that, from noisy oracle access to $f$, identifies all feature directions whose responses are non-degenerate and reconstructs the function $f$. Crucially, our algorithm works in a significantly more general setting than all related prior results -- we allow for essentially arbitrary superpositions, only requiring that $v_i, v_j$ are not nearly identical for $i \neq j$, and general response functions $σ_i$. At a high level, our algorithm introduces an approach for searching in Fourier space by iteratively refining the search space to locate the hidden directions $v_i$.
- Abstract（参考訳）: 複雑な機械学習モデルは一般に線形表現を通じて特徴を符号化すると考えられているが、これらの特徴は重ね合わせに存在するため、回復は困難である。
関数 \[f(x)=\sum_{i=1}^n a_i\,σ_i(v_i^\top x), \] ここで各単位ベクトル $v_i$ は特徴方向を符号化し、$σ_i:\mathbb{R} \rightarrow \mathbb{R}$ は任意の応答関数であり、我々のゴールは $v_i$ と関数 $f$ を回復することである。
学習理論の用語において、重ね合わせ(英: superposition)とは、典型的なアルゴリズム的アプローチにおいて特に困難であることが証明された、特徴の数が基礎的な次元(例えば$n > d$)よりも大きい場合のオーバーコンプリート状態を指す。
我々の主な結果は効率の良いクエリアルゴリズムで、ノイズの多いオラクルアクセスから$f$まで、応答が非退化しているすべての特徴方向を特定し、関数$f$を再構築します。
重要なことに、我々のアルゴリズムはすべての前の結果よりもはるかに一般的な設定で機能する -- 基本的に任意の重ね合わせを許すが、$v_i, v_j$は$i \neq j$とほとんど同じではなく、一般応答関数$σ_i$である。
高いレベルでは,探索空間を反復的に修正し,隠れた方向を$v_i$で見つけることによって,フーリエ空間の探索手法を導入する。
関連論文リスト
- Learning Partitions with Optimal Query and Round Complexities [16.815943270621638]
未知の$n$要素を少なくとも$k$集合に分割することの基本的な問題を考える。
非適応アルゴリズムには$Theta(n2)$クエリが必要ですが、適応アルゴリズムには$Theta(nk)$クエリが必要です。
我々のアルゴリズムは、最適な$O(nk)$クエリ複雑性を達成するために、$O(log log n)$ラウンドしか必要としない。
論文 参考訳（メタデータ） (2025-05-08T07:27:29Z) - Efficient Algorithm for Sparse Fourier Transform of Generalized $q$-ary Functions [0.3004066195320147]
GFastはFourier変換を$f$、サンプル複雑性は$O(Sn)$で計算する符号化理論アルゴリズムである。
GFastは、実世界の心臓疾患の診断とタンパク質の適合性モデルの説明を、最大13時間分のサンプルで行える。
論文 参考訳（メタデータ） (2025-01-21T18:45:09Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - On the instance optimality of detecting collisions and subgraphs [7.055459105099637]
グラフや関数における部分構造検出問題のラベルなしインスタンス最適性について検討する。
アルゴリズムが任意の入力に対して満足する$A$を許容すれば、問題は$g(n)$-instanceOptimationである。
この結果から,グラフや関数のサブ構造検出問題において,ラベルなしのインスタンス最適性を三分したことが示唆された。
論文 参考訳（メタデータ） (2023-12-15T20:50:03Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文 参考訳（メタデータ） (2020-02-23T22:51:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。