カウントスケッチ

Method of a dimension reduction

カウントスケッチは次元削減の一種で、統計、機械学習、アルゴリズムにおいて特に有効です。^{[1] [2]}これは、ストリームの頻度モーメントを近似するためのAlon、Matias、SzegedyによるAMSスケッチを高速化する目的で、Moses Charikar、Kevin Chen、Martin Farach-Colton [3] によって発明されました^（これらの計算では、ストリームの個別要素の発生回数を数える必要があります）。

このスケッチは、ジョン・ムーディによる特徴ハッシュアルゴリズム^[5]とほぼ同一^[要出典]ですが、依存性の低いハッシュ関数を使用する点で異なり、より実用的です。高い成功確率を維持するために、複数のカウントスケッチを集計する際には、平均値ではなく中央値トリックが用いられます。

これらの特性により、明示的カーネル法やニューラルネットワークにおける双線形プーリングが可能になり、多くの数値線形代数アルゴリズムの基礎となっています。^[6]

直感的な説明

このデータ構造の発明者は、その動作について次のように繰り返し説明しています。^[3]

• 最も単純なレベルでは、ストリーム要素qを {+1, -1} にマッピングする単一のハッシュ関数 sの出力が、単一のアップダウンカウンタCに入力されます。データを1回処理するだけで、ストリーム要素qの頻度は、非常に不正確ではありますが、期待値 sで近似できます。 ${\displaystyle n(q)}$ ${\displaystyle {\mathbf {E}}[C\cdot s(q)]}$
• 前回の推定値の分散を改善する簡単な方法は、それぞれ独自のカウンタに接続された異なるハッシュ関数の配列を使用することです。各要素qについて は依然として成立するため、 i の範囲全体で平均化することで近似値がより厳密になります。 ${\displaystyle s_{i}}$ ${\displaystyle C_{i}}$ ${\displaystyle {\mathbf {E}}[C_{i}\cdot s_{i}(q)]=n(q)}$
• 前述の構成にはまだ大きな欠陥があります。頻度は低いものの依然として重要な出力要素a が頻度の高い要素とハッシュ衝突を起こした場合、推定値に大きな影響が出る可能性があります。これを避けるには、任意の 2 つの異なる要素間の衝突カウンタの更新頻度を減らす必要があります。これは、前述の構成の各 をm個のカウンタの配列に置き換え（カウンタ セットを 2 次元行列 にします）、増分/減分する特定のカウンタのインデックスjは、要素qを範囲 {1.. m } にマップする別のハッシュ関数のセットによって選択されます。 なので、 iのすべての値の平均化は機能します。 ${\displaystyle n(a)}$ ${\displaystyle C_{i}}$ ${\displaystyle C_{i,j}}$ ${\displaystyle h_{i}}$ ${\displaystyle {\mathbf {E}}[C_{i,h_{i}(q)}\cdot s_{i}(q)]=n(q)}$

数学的な定義

1. 定数と（後ほど定義）に対して、ととなるランダムハッシュ関数と をそれぞれ独立に選択します。とが選択されるハッシュ族は、互いに独立である必要があります。 ${\displaystyle w}$ ${\displaystyle t}$ ${\displaystyle d=2t+1}$ ${\displaystyle h_{1},\dots ,h_{d}}$ ${\displaystyle s_{1},\dots ,s_{d}}$ ${\displaystyle h_{i}:[n]\to [w]}$ ${\displaystyle s_{i}:[n]\to \{\pm 1\}}$ ${\displaystyle h_{i}}$ ${\displaystyle s_{i}}$

2.ストリーム内の各項目について、 番目のハッシュの 番目のバケットに追加します。 ${\displaystyle q_{i}}$ ${\displaystyle s_{j}(q_{i})}$ ${\displaystyle h_{j}(q_{i})}$ ${\displaystyle j}$

このプロセスの最後には、 ${\displaystyle wd}$ ${\displaystyle (C_{ij})}$

${\displaystyle C_{i,j}=\sum _{h_{i}(k)=j}s_{i}(k).}$

sの数を推定するには、次の値を計算します。 ${\displaystyle q}$

${\displaystyle r_{q}={\text{median}}_{i=1}^{d}\,s_{i}(q)\cdot C_{i,h_{i}(q)}.}$

値は、ストリームに出現した回数の偏りのない推定値です。 ${\displaystyle s_{i}(q)\cdot C_{i,h_{i}(q)}}$ ${\displaystyle q}$

推定値の分散は であり、は川の長さ、は である。^[7] ${\displaystyle r_{q}}$ ${\displaystyle O(\mathrm {min} \{m_{1}^{2}/w^{2},m_{2}^{2}/w\})}$ ${\displaystyle m_{1}}$ ${\displaystyle m_{2}^{2}}$ ${\displaystyle \sum _{q}(\sum _{i}[q_{i}=q])^{2}}$

さらに、は確率 で真の値から以上にずれることは決してないことが保証されています。 ${\displaystyle r_{q}}$ ${\displaystyle 2m_{2}/{\sqrt {w}}}$ ${\displaystyle 1-e^{-O(t)}}$

ベクトル定式化

あるいは、Count-Sketchは非線形再構成関数を用いた線形写像とみなすこともできる。 を、次のように定義される行列の集合とする。 ${\displaystyle M^{(i\in [d])}\in \{-1,0,1\}^{w\times n}}$ ${\displaystyle d=2t+1}$

${\displaystyle M_{h_{i}(j),j}^{(i)}=s_{i}(j)}$

については 、それ以外は 0 です。 ${\displaystyle j\in [w]}$

次に、によってベクトルが描かれます。再構築するには、 を取ります。これにより、とをとった場合とで、上記と同じことが保証されます。 ${\displaystyle v\in \mathbb {R} ^{n}}$ ${\displaystyle C^{(i)}=M^{(i)}v\in \mathbb {R} ^{w}}$ ${\displaystyle v}$ ${\displaystyle v_{j}^{*}={\text{median}}_{i}C_{j}^{(i)}s_{i}(j)}$ ${\displaystyle m_{1}=\|v\|_{1}}$ ${\displaystyle m_{2}=\|v\|_{2}}$

テンソルスケッチとの関係

2 つのベクトルの外積のカウント スケッチ投影は、2 つのコンポーネント カウント スケッチの 畳み込みと同等です。

カウントスケッチはベクトル畳み込みを計算する

${\displaystyle C^{(1)}x\ast C^{(2)}x^{T}}$ここで、およびは独立したカウントスケッチ行列です。 ${\displaystyle C^{(1)}}$ ${\displaystyle C^{(2)}}$

PhamとPagh ^[8] は、これがベクトルの外積のカウントスケッチに等しいことを示しています。ここで、はクロネッカー積を表します。 ${\displaystyle C(x\otimes x^{T})}$ ${\displaystyle C}$ ${\displaystyle \otimes }$

高速フーリエ変換は、カウントスケッチの高速畳み込みに使用できます。面分割積^{[9] [10] [11]}を用いることで、このような構造は通常の行列よりもはるかに高速に計算できます。

参照

• Count-min スケッチは、メモリ要件がより小さい（トレードオフとしてエラー保証がより弱い）アルゴリズムのバージョンです。
• テンソルスケッチ

参考文献

1. Faisal M. Algashaam、Kien Nguyen、Mohamed Alkanhal、Vinod Chandran、Wageeh Boles。「マルチモーダルコンパクトマルチリニアプーリングを用いたマルチスペクトル眼周分類」[1]。IEEE Access、Vol.5、2017年。
2. Ahle, Thomas; Knudsen, Jakob (2019年9月3日). 「Almost Optimal Tensor Sketch」. ResearchGate . 2020年7月11日閲覧。
3. チャリカ、チェン、ファラック＝コルトン、2004。
4. Alon, Noga, Yossi Matias, Mario Szegedy. 「周波数モーメントの近似における空間計算量」Journal of Computer and system sciences 58.1 (1999): 137-147.
5. ムーディー、ジョン。「多重解像度階層における高速学習」神経情報処理システムの進歩。1989年。
6. Woodruff, David P.「数値線形代数のためのツールとしてのスケッチ」理論計算機科学10.1-2（2014）：1–157。
7. Larsen、Kasper Green、Rasmus Pagh、Jakub Tětek。「CountSketches、Feature Hashing、そして3の中央値」。国際機械学習会議。PMLR、2021年。
8. Ninh, Pham; Pagh, Rasmus (2013).明示的な特徴マップを用いた高速かつスケーラブルな多項式カーネル．SIGKDD国際会議「知識発見とデータマイニング」．Association for Computing Machinery. doi :10.1145/2487575.2487591.
9. Slyusar, VI (1998). 「レーダーアプリケーションにおけるマトリックスの最終製品」(PDF) .無線エレクトロニクスと通信システム. 41 (3): 50– 53.
10. Slyusar, VI (1997-05-20). 「面分割行列積に基づくデジタルアンテナアレイの解析モデル」(PDF) . Proc. ICATT-97, キエフ: 108–109 .
11. Slyusar, VI (1998年3月13日). 「行列の面積の族とその特性」(PDF) .サイバネティクスとシステム分析 C/C of Kibernetika I Sistemnyi Analiz.- 1999. 35 ( 3): 379– 384. doi :10.1007/BF02733426. S2CID  119661450.

さらに読む

• チャリカー, モーゼス; チェン, ケビン; ファラッハ＝コルトン, マーティン (2004). 「データストリームにおける頻出アイテムの検出」(PDF) .理論計算機科学. 312 (1). Elsevier BV: 3– 15. doi :10.1016/s0304-3975(03)00400-6. ISSN  0304-3975.
• ファイサル・M・アルガシャム、キエン・グエン、モハメド・アルカンハル、ヴィノド・チャンドラン、ワギー・ボレス。「マルチモーダル・コンパクト・マルチリニア・プーリングによるマルチスペクトル眼周分類」[1]。IEEE Access、第5巻、2017年。
• Ahle, Thomas; Knudsen, Jakob (2019-09-03). 「ほぼ最適なテンソルスケッチ」. ResearchGate . 2020年7月11日閲覧。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Count_sketch&oldid=1273872249"