論文の概要: Learning to Understand: Identifying Interactions via the Mobius
Transform
- arxiv url: http://arxiv.org/abs/2402.02631v1
- Date: Sun, 4 Feb 2024 22:47:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-06 18:22:36.131199
- Title: Learning to Understand: Identifying Interactions via the Mobius
Transform
- Title(参考訳): 理解への学習:Mobius変換によるインタラクションの特定
- Authors: Justin S. Kang, Yigit E. Erginbas, Landon Butler, Ramtin Pedarsani,
Kannan Ramchandran
- Abstract要約: 機械学習における最も基本的な問題の1つは、我々が学習した関数の解釈可能な表現を見つけることである。
Mobius変換は、その係数が入力変数の集合上のユニークな重要なスコアに対応するため、このために有用なツールである。
この研究は、非ゼロモダス係数の分数(したがって入力間の相互作用)が小さい(典型的)レジームに焦点をあてる。
- 参考スコア(独自算出の注目度): 19.939343881656594
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One of the most fundamental problems in machine learning is finding
interpretable representations of the functions we learn. The Mobius transform
is a useful tool for this because its coefficients correspond to unique
importance scores on sets of input variables. The Mobius Transform is strongly
related (and in some cases equivalent) to the concept of Shapley value, which
is a widely used game-theoretic notion of importance. This work focuses on the
(typical) regime where the fraction of non-zero Mobius coefficients (and thus
interactions between inputs) is small compared to the set of all $2^n$ possible
interactions between $n$ inputs. When there are $K = O(2^{n \delta})$ with
$\delta \leq \frac{1}{3}$ non-zero coefficients chosen uniformly at random, our
algorithm exactly recovers the Mobius transform in $O(Kn)$ samples and
$O(Kn^2)$ time with vanishing error as $K \rightarrow \infty$, the first
non-adaptive algorithm to do so. We also uncover a surprising connection
between group testing and the Mobius transform. In the case where all
interactions are between at most $t = \Theta(n^{\alpha})$ inputs, for $\alpha <
0.409$, we are able to leverage results from group testing to provide the first
algorithm that computes the Mobius transform in $O(Kt\log n)$ sample complexity
and $O(K\mathrm{poly}(n))$ time with vanishing error as $K \rightarrow \infty$.
Finally, we present a robust version of this algorithm that achieves the same
sample and time complexity under some assumptions, but with a factor depending
on noise variance. Our work is deeply interdisciplinary, drawing from tools
spanning across signal processing, algebra, information theory, learning theory
and group testing to address this important problem at the forefront of machine
learning.
- Abstract(参考訳): 機械学習における最も根本的な問題の1つは、我々が学習する関数の解釈可能な表現を見つけることである。
Mobius変換は、その係数が入力変数の集合上のユニークな重要なスコアに対応するため、このために有用なツールである。
Mobius Transform は、ゲーム理論における重要概念であるShapley value の概念と強く関連している(場合によっては同等である)。
この研究は、非零モビウス係数の分数(したがって入力間の相互作用)が、$n$入力間の2^n$ 可能なすべての相互作用の集合に比べて小さい(典型的な)レジームに焦点を当てている。
k = o(2^{n \delta})$ with $\delta \leq \frac{1}{3}$ non-zero 係数がランダムに選択されたとき、このアルゴリズムは、o(kn)$ のサンプルでモビウス変換を正確に回復し、o(kn^2)$ のエラーが消えると、k \rightarrow \infty$ となる。
また、グループテストとMobius変換の驚くべき関係も明らかにしました。
すべての相互作用が少なくとも$t = \Theta(n^{\alpha})$入力の間にある場合、$\alpha < 0.409$に対して、グループテストの結果を活用して、$O(Kt\log n)$サンプル複雑性と$O(K\mathrm{poly}(n))$エラーを消滅した時間を$K \rightarrow \infty$で計算する最初のアルゴリズムを提供する。
最後に、このアルゴリズムの頑健なバージョンを示し、いくつかの仮定の下で同じサンプルと時間複雑性を達成するが、ノイズ分散に依存する要因を持つ。
私たちの研究は、信号処理、代数、情報理論、学習理論、グループテストにまたがるツールから、機械学習の最前線でこの重要な問題に対処するために、深く学際的です。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳(メタデータ) (2023-08-18T17:52:12Z) - 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) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳(メタデータ) (2022-03-28T23:53:48Z) - Learning the optimal regularizer for inverse problems [1.763934678295407]
線形逆問題 $y=Ax+epsilon$ を考えると、$Acolon Xto Y$ は分離可能なヒルベルト空間 $X$ と $Y$ の間の既知の線型作用素である。
この設定は、デノイング、デブロアリング、X線トモグラフィーなど、画像のいくつかの逆問題を含んでいる。
古典的な正規化の枠組みの中では、正規化関数が優先順位を与えられず、データから学習される場合に焦点を当てる。
論文 参考訳(メタデータ) (2021-06-11T17:14:27Z) - $k$-Forrelation Optimally Separates Quantum and Classical Query
Complexity [3.4984289152418753]
我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。
我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
論文 参考訳(メタデータ) (2020-08-16T21:26:46Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳(メタデータ) (2020-06-11T00:55:35Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。