#### 論文の概要: 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
• 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.の中央値の分散と高次モーメントに関する新しい一般定理に基づいている。 独立した関心を持つ可能性のあるランダム変数。