論文の概要: Recovery of sparse linear classifiers from mixture of responses
- arxiv url: http://arxiv.org/abs/2010.12087v3
- Date: Thu, 24 Dec 2020 21:06:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 06:13:52.555489
- Title: Recovery of sparse linear classifiers from mixture of responses
- Title（参考訳）: 反応の混合によるスパース線形分類器の復元
- Authors: Venkata Gandikota, Arya Mazumdar, Soumyabrata Pal
- Abstract要約: 双対応答列から超平面の集合を学習する方法を示す。
各応答はベクトルとのクエリの結果であり、クエリベクトルが属するコレクションからランダムに選択された超平面の側面を示す。
- 参考スコア（独自算出の注目度）: 42.228977798395846
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the problem of learning a mixture of linear classifiers, the aim is to
learn a collection of hyperplanes from a sequence of binary responses. Each
response is a result of querying with a vector and indicates the side of a
randomly chosen hyperplane from the collection the query vector belongs to.
This model provides a rich representation of heterogeneous data with
categorical labels and has only been studied in some special settings. We look
at a hitherto unstudied problem of query complexity upper bound of recovering
all the hyperplanes, especially for the case when the hyperplanes are sparse.
This setting is a natural generalization of the extreme quantization problem
known as 1-bit compressed sensing. Suppose we have a set of $\ell$ unknown
$k$-sparse vectors. We can query the set with another vector $\boldsymbol{a}$,
to obtain the sign of the inner product of $\boldsymbol{a}$ and a randomly
chosen vector from the $\ell$-set. How many queries are sufficient to identify
all the $\ell$ unknown vectors? This question is significantly more challenging
than both the basic 1-bit compressed sensing problem (i.e., $\ell=1$ case) and
the analogous regression problem (where the value instead of the sign is
provided). We provide rigorous query complexity results (with efficient
algorithms) for this problem.
- Abstract（参考訳）: 線形分類器の混合を学習する問題において、目的は二項応答の列から超平面の集合を学習することである。
各応答はベクトルによるクエリの結果であり、クエリベクトルが属するコレクションからランダムに選択されたハイパープレーンの側面を示す。
このモデルはカテゴリラベルを持つ異種データの豊富な表現を提供し、いくつかの特別な設定でしか研究されていない。
我々は、すべての超平面を回復する上限、特に超平面が疎い場合のクエリ複雑性という、ひっそりと未熟な問題に目を向ける。
この設定は1ビット圧縮センシングとして知られる極端量子化問題の自然な一般化である。
a set of $\ell$ unknown $k$-sparse vectors とする。
集合を別のベクトル $\boldsymbol{a}$ でクエリし、$\boldsymbol{a}$ の内部積の符号と$\ell$-set からランダムに選択されたベクトルを求めることができる。
すべての$\ell$ 未知ベクトルを識別できるクエリはいくつあるか?
この問題は、基本的な1ビット圧縮されたセンシング問題(例えば$\ell=1$ case)と類似の回帰問題(符号の代わりに値が与えられる)よりもはるかに難しい。
この問題に対する厳密なクエリ複雑性の結果(効率的なアルゴリズム)を提供する。
関連論文リスト
- 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) - Matching Map Recovery with an Unknown Number of Outliers [0.0]
我々は,2組の$d$次元雑音特徴ベクトル間のマッチング写像を求める問題を考察する。
高次元環境では、信号対雑音比が5(dlog(4nm/alpha))1/4$より大きい場合、真のマッチングマップは確率1-alpha$で復元可能であることを示す。
論文 参考訳（メタデータ） (2022-10-24T15:59:10Z) - Improved analysis of randomized SVD for top-eigenvector approximation [16.905540623795467]
そこで本研究では,無作為なSVDアルゴリズムであるcitethalko2011finding を新たに解析し,興味のある場合の厳密な境界を導出する。
特に、これは任意の反復数を持つランダム化SVDに対して$R(hatmathbfu)$の非自明な境界を与える最初の作品である。
論文 参考訳（メタデータ） (2022-02-16T11:12:07Z) - On the query complexity of connectivity with global queries [0.2538209532048867]
グラフがグローバルクエリと結びついているかどうかを判断する際のクエリの複雑さについて検討する。
ゼロエラーランダム化アルゴリズムは接続性を解決するために,$Omega(n)$リニアクエリを生成する必要がある。
論文 参考訳（メタデータ） (2021-09-05T16:22:55Z) - Support Recovery of Sparse Signals from a Mixture of Linear Measurements [48.556633593447465]
簡単な測定からスパースベクトルの支持を回復することは、広く研究されている問題である。
この問題の一般化を考える:線形回帰の混合と線形分類器の混合である。
我々は$k, log n$ および quasi-polynomial を $ell$ で多くの測定値を用いて、混合中の未知ベクトルの全てのサポートを回復するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-10T17:48:13Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z) - Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and
Graph Problems [58.83118651518438]
ベクトル行列ベクトルクエリを用いて行列について学習する一般的な問題を考える。
これらのクエリは、固定フィールド上の$boldsymbolumathrmTboldsymbolMboldsymbolv$の値を提供する。
我々は、線形代数、統計、グラフにまたがる様々な問題に対して、新しい上界と下界を提供する。
論文 参考訳（メタデータ） (2020-06-24T19:33:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。