論文の概要: CountSketches, Feature Hashing and the Median of Three
- arxiv url: http://arxiv.org/abs/2102.02193v1
- Date: Wed, 3 Feb 2021 18:45:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-04 17:36:59.556696
- Title: CountSketches, Feature Hashing and the Median of Three
- Title（参考訳）: CountSketches, feature Hashing, and the Median of Three
- Authors: Kasper Green Larsen, Rasmus Pagh, Jakub T\v{e}tek
- Abstract要約: 古典的なCountSketch法は、(高次元)ユークリッドベクトル $v$ を次元 $(2t-1) s$ に変換するスパースでランダムな射影である。
我々の主な貢献は、Count-Sketchの新しい分析であり、$t > 1$ のとき、$O(min|v|2/s2,|v|2/s2)$ への分散の改善を示す。
この結果は、基本的にCountSketchと同一であるが中央値を使用しないFeature Hashing法が可能であることを示唆している。
- 参考スコア（独自算出の注目度）: 18.85876632959721
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we revisit the classic CountSketch method, which is a sparse,
random projection that transforms a (high-dimensional) Euclidean vector $v$ to
a vector of dimension $(2t-1) s$, where $t, s > 0$ are integer parameters. It
is known that even for $t=1$, a CountSketch allows estimating coordinates of
$v$ with variance bounded by $\|v\|_2^2/s$. For $t > 1$, the estimator takes
the median of $2t-1$ independent estimates, and the probability that the
estimate is off by more than $2 \|v\|_2/\sqrt{s}$ is exponentially small in
$t$. This suggests choosing $t$ to be logarithmic in a desired inverse failure
probability. However, implementations of CountSketch often use a small,
constant $t$. Previous work only predicts a constant factor improvement in this
setting.
Our main contribution is a new analysis of Count-Sketch, showing an
improvement in variance to $O(\min\{\|v\|_1^2/s^2,\|v\|_2^2/s\})$ when $t > 1$.
That is, the variance decreases proportionally to $s^{-2}$, asymptotically for
large enough $s$. We also study the variance in the setting where an inner
product is to be estimated from two CountSketches. This finding suggests that
the Feature Hashing method, which is essentially identical to CountSketch but
does not make use of the median estimator, can be made more reliable at a small
cost in settings where using a median estimator is possible.
We confirm our theoretical findings in experiments and thereby help justify
why a small constant number of estimates often suffice in practice. Our
improved variance bounds are based on new general theorems about the variance
and higher moments of the median of i.i.d. random variables that may be of
independent interest.
- Abstract（参考訳）: 本稿では、(高次元)ユークリッドベクトル $v$ を、$t, s > 0$ が整数パラメータである次元 $(2t-1) s$ のベクトルに変換する、スパースでランダムなプロジェクションである古典的なCountSketchメソッドを再検討する。
たとえ$t=1$であっても、CountSketchは$v$の座標を$\|v\|_2^2/s$で有界で推定できる。
t > 1$の場合、見積もりは$t-1$の独立した見積もりの中央値を取り、見積もりが$t$で2 \|v\|_2/\sqrt{s}$以上オフになる確率は指数的に小さい。
これは、所望の逆失敗確率において対数として$t$を選択することを示唆する。
しかし、CountSketchの実装は小さな定数$t$を使うことが多い。
前の作業は、この設定で一定の要因の改善を予測します。
私たちの主な貢献は、$O(\min\{\|v\|_1^2/s^2,\|v\|_2^2/s\})$に対する分散性の改善を示すCount-Sketchの新しい分析である。
すなわち、分散は比例的に$s^{-2}$に減少し、漸近的に$s$となる。
また、2つのCountSketchesから内積を推定する設定におけるばらつきについても検討する。
この発見は、本質的にcountsketchと同一であるが、中央値推定器を使用しない特徴ハッシュ法は、中央値推定器の使用が可能な設定において、少ないコストでより信頼性を高めることができることを示唆している。
私たちは、実験における理論的発見を確認し、なぜ少数の見積もりが実際に十分であるのかを正当化します。
改良された分散境界は、i.d.の中央値の分散と高次モーメントに関する新しい一般定理に基づいている。
独立した関心を持つ可能性のあるランダム変数。
関連論文リスト
- Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances [15.990720051907864]
Subset-of-Signalsモデルはヘテロスケダティック平均推定のベンチマークとして機能する。
我々のアルゴリズムは、このオープンな問題を対数的要因に分解する。
たとえ$d=2$であっても、我々の手法は各サンプルのばらつきを知るのに匹敵するレートを可能にします。
論文 参考訳（メタデータ） (2023-12-05T01:13:10Z) - Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。
また、Acharyaなどのアルゴリズムの改良版も提供します。
論文 参考訳（メタデータ） (2023-06-20T06:13:56Z) - List-Decodable Sparse Mean Estimation [7.594050968868919]
最近の研究関心の高まりは、$alpha in (0, frac12]$というリストデコザブルな設定に焦点が当てられ、目標平均を少なくとも1つ近似した有限個の見積もりを出力することが目的である。
本稿では,基礎となるターゲットが平均分布$k$,最初のコントリビューションが最初のサンプル$Obig(mathrmpoly(k, log dbig)$,すなわち次元の多元対数であると考えている。
論文 参考訳（メタデータ） (2022-05-28T05:13:45Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - Weighted-average quantile regression [1.0742675209112622]
重み付き平均量子化回帰フレームワークである$int_Y|X(u)psi(u)du = X'beta$を導入する。
我々はパラメータのベクトルを$beta$で推定し、$T$は利用可能なサンプルのサイズである。
論文 参考訳（メタデータ） (2022-03-06T19:06:53Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$ [5.457150493905064]
ガウス下収束を考慮した新しい推定器を提案する。
我々の推定器はその分散に関する事前の知識を必要としない。
我々の推定器の構成と分析は、他の問題に一般化可能なフレームワークを提供する。
論文 参考訳（メタデータ） (2020-11-17T02:47:24Z) - Multivariate mean estimation with direction-dependent accuracy [8.147652597876862]
独立な同一分布観測に基づくランダムベクトルの平均を推定する問題を考察する。
確率ベクトルの1次元辺の分散があまり小さくない全ての方向において、ほぼ最適誤差を持つ推定器を証明した。
論文 参考訳（メタデータ） (2020-10-22T17:52:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。