ランダム投影

数学と統計学において、ランダム射影はユークリッド空間にある点の集合の次元を削減するために使用される手法である。理論的結果によれば、ランダム射影は距離をよく保存するが、経験的結果はまばらである。^{[1]それらは}ランダムインデックスという名前で多くの自然言語タスクに適用されてきている。

次元削減

次元削減とは、その名前が示すように、統計学や機械学習のさまざまな数学的手法を使用してランダム変数の数を削減することです。次元削減は、大規模なデータセットの管理と操作の問題を軽減するためによく使用されます。次元削減手法では、通常、多様体の固有の次元を決定し、その主方向を抽出する際に線形変換が使用されます。この目的のために、主成分分析、線形判別分析、正準相関分析、離散コサイン変換、ランダム投影など、さまざまな関連手法があります。

ランダム投影は、制御された量のエラーと引き換えに処理時間の短縮とモデルサイズの縮小を実現し、データの次元を削減するシンプルで計算効率の高い方法です。ランダム投影行列の次元と分布は、データセットの任意の 2 つのサンプル間のペアワイズ距離をほぼ維持するように制御されます。

方法

ランダム射影の核となる考え方はジョンソン・リンデンシュトラウスの補題^[2]で与えられており、ベクトル空間内の点が十分に高次元である場合、点間のペアワイズ距離を高い確率で近似的に保存する方法で、それらの点を適切な低次元空間に射影できると述べています。

ランダム射影では、元の d 次元データは、列の長さが単位であるランダム次元行列 R を使用して、k 次元 (k << d) のサブスペースに射影されます。^[^{出典が必要}^]行列表記法の使用: が元のN 個の d 次元観測値のセットである場合、はデータのより低い k 次元サブスペースへの射影です。ランダム射影は計算上は単純です。ランダム行列 "R" を作成し、データ行列 X をのオーダーの K 次元に射影します。データ行列 X がスパースで、列ごとに約 c 個の非ゼロ要素がある場合、この操作の複雑さはのオーダーです。^[3] $k\times d$ $X_{d\times N}$ $X_{k\times N}^{RP}=R_{k\times d}X_{d\times N}$ $d\times N$ $O(dkN)$ $O(ckN)$

ガウスランダム投影

ランダム行列 R は、ガウス分布を使用して生成できます。最初の行は、から一様に選択されたランダムな単位ベクトルです。2 行目は、最初の行に直交する空間からのランダムな単位ベクトル、3 行目は最初の 2 行に直交する空間からのランダムな単位ベクトル、というように続きます。この方法で R を選択すると、次のプロパティが満たされます。 $S^{d-1}$

球面対称性: 任意の直交行列に対して、RA と R は同じ分布を持ちます。 $A\in O(d)$
直交性: R の行は互いに直交します。
正規性: R の行は単位長さのベクトルです。

より計算効率の高いランダム投影

アクリオプタス^[4]は、ガウス分布は次のようなより単純な分布に置き換えられることを示した。

R_{i,j}={\sqrt {3}}\times {\begin{cases}+1&{\text{確率で}}{\frac {1}{6}}\\0&{\text{確率で}}{\frac {2}{3}}\\-1&{\text{確率で}}{\frac {1}{6}}\end{cases}}

これは、計算を整数演算で実行できるため、データベースアプリケーションに効率的です。さらに関連する研究は^{[5]で行われています。}

その後、スパースJL変換の研究で、分布をさらにスパースにして、列ごとに非ゼロの要素を非常に少なくしながら、整数演算を使用する方法が示されました。^[6]これは、スパース埋め込み行列によってデータをより低い次元にさらに高速に投影できるため、有利です。

量子化によるランダム投影

ランダム投影は、1ビット（符号ランダム投影）またはマルチビットの量子化（離散化）によってさらに凝縮することができます。これは、SimHash、^[7] RPツリー、^[8]およびその他のメモリ効率の高い推定および学習方法の構成要素です。^[9]^[10]

大型の準直交基地

ジョンソン・リンデンシュトラウスの補題は、高次元空間内のベクトルの大きな集合は、距離を近似的に保存しながら、はるかに低い（それでも高い）次元nの空間に線形に写像できることを述べています。この効果の説明の 1 つは、 n次元ユークリッド空間の準直交次元が指数的に高いことです。^[11]n次元ユークリッド空間には、（内積の値が小さい）ほぼ直交するベクトルの集合が指数的に大きい（次元n ）ことが存在します。この観察は、高次元データのインデックス作成に役立ちます。 ^[12]

大規模なランダム集合の準直交性は、機械学習におけるランダム近似法にとって重要である。高次元では、球面上の等分布（および他の多くの分布）からランダムに独立に選択された指数関数的に大きな数のベクトルは、確率が1に近い状態でほぼ直交する。^[13] これは、ランダムに独立に選択されたベクトルの線形結合によってこのような高次元空間の要素を表すには、線形結合で制限された係数を使用する場合、指数関数的に大きな長さのサンプルを生成する必要があることが多いことを意味している。一方、任意の大きな値を持つ係数が許容される場合、近似に十分なランダムに生成された要素の数は、データ空間の次元よりもさらに少なくなる。

実装

RandPro - ランダム投影のためのRパッケージ^[14]^[15]
sklearn.random_projection - scikit-learn Python ライブラリからのランダム投影用のモジュール
Wekaの実装 [1]

参照

参考文献

^ Ella, Bingham; Heikki, Mannila (2001). 「次元削減におけるランダム投影: 画像およびテキストデータへの応用」KDD - 2001: 第 7 回 ACM SIGKDD 国際知識発見およびデータマイニング会議の議事録。ニューヨーク: Association for Computing Machinery。pp. 245–250。CiteSeerX 10.1.1.24.5135。doi :10.1145/502512.502546。
^ ジョンソン、ウィリアム B. ;リンデンシュトラウス、ジョラム(1984)。「ヒルベルト空間へのリプシッツ写像の拡張」。現代解析と確率の会議 (コネチカット州ニューヘブン、1982) 。現代数学。第 26 巻。プロビデンス、ロードアイランド州: アメリカ数学協会。pp. 189–206。doi :10.1090/conm/026/ 737400。ISBN 9780821850305. MR 0737400. S2CID 117819162.。
^ Bingham, Ella; Mannila, Heikki (2014 年 5 月 6 日)。「次元削減におけるランダム投影: 画像およびテキストデータへの応用」(PDF)。
^ Achlioptas, Dimitris (2001). 「データベースに適したランダム投影」。第 20 回ACM SIGMOD-SIGACT-SIGART シンポジウム「データベースシステムの原理 - PODS '01」の議事録。274 ～ 281 ページ。CiteSeerX 10.1.1.28.6652。doi : 10.1145 / 375551.375608。ISBN 978-1581133615. S2CID 2640788。
^ Li, Ping; Hastie, Trevor; Church, Kenneth (2006). 「非常にスパースなランダム投影」。知識発見とデータマイニングに関する第 12 回 ACM SIGKDD 国際会議の議事録。pp . 287–296。doi :10.1145 / 1150402.1150436。ISBN 1595933395. S2CID 7995734。
^ Kane, Daniel M.; Nelson, Jelani (2014). 「Sparser Johnson-Lindenstrauss Transforms」. Journal of the ACM . 61 (1): 1–23. arXiv : 1012.1577 . doi :10.1145/2559902. MR 3167920. S2CID 7821848.
^ Charikar, Moses (2002)。「丸めアルゴリズムによる類似性推定手法」。第34 回 ACM コンピューティング理論シンポジウムの議事録。第 1 巻。380 ～ 388 ページ。doi :10.1145/ 509907.509965。ISBN 1581134959. S2CID 4229473。
^ Freund, Yoav; Dasgupta, Sanjoy; Kabra, Mayank; Verma, Nakul (2007). 「ランダム投影を用いた多様体構造の学習」.第20回国際神経情報処理システム会議. 1 (1): 473–480.
^ Boufounos, Petros; Baraniuk, Richard (2008). 「1 ビット圧縮センシング」.第 42 回情報科学およびシステム年次会議. 1 (1): 16–21. doi :10.1109/CISS.2008.4558487. S2CID 206563812.
^ Li, Xiaoyun; Li, Ping (2019). 「量子化圧縮学習の一般化誤差分析」.第33回国際神経情報処理システム会議. 1 : 15150–15160.
^ カイネン、ポール C. ;クルコヴァ、ベラ(1993)、「ユークリッド空間の準直交次元」、応用数学レター、6 (3): 7–10、doi : 10.1016/0893-9659(93)90023-G、MR 1347278
^ Hecht-Nielsen, R. (1994). 「コンテキストベクトル: 生データから自己組織化された汎用近似意味表現」。Zurada, Jacek M.、Marks, Robert Jackson、Robinson, Charles J. (編)。計算知能: 生命の模倣。IEEE。pp. 43–56。ISBN 978-0-7803-1104-6。
^ Gorban, Alexander N. ; Tyukin, Ivan Y.; Prokhorov, Danil V.; Sofeikov, Konstantin I. (2016). 「ランダム基数による近似: 賛否両論」.情報科学. 364–365: 129–145. arXiv : 1506.04631 . doi :10.1016/j.ins.2015.09.021. S2CID 2239376.
^ Ravindran, Siddharth (2020). 「k近傍法（k-NN）を用いたビッグデータ分類における次元削減のためのデータ非依存再利用可能投影（DIRP）手法」。全米科学アカデミー科学レター。43 :13–21。doi : 10.1007 /s40009-018-0771-6。S2CID 91946077。
^ Siddharth, R.; Aghila, G. (2020年7月). 「RandPro - Rでの高次元多変量データ分析のためのランダム投影ベースの特徴抽出の実用的な実装」. SoftwareX . 12 : 100629. Bibcode :2020SoftX..1200629S. doi : 10.1016/j.softx.2020.100629 .

さらに読む

Fodor, Imola K (2002). 次元削減技術の調査 (レポート). CiteSeerX 10.1.1.8.5098 .
Menon, Aditya Krishna (2007).ランダム投影と次元削減への応用(論文). CiteSeerX 10.1.1.164.640 .
Ramdas, Aditya. ランダム投影へのランダム入門 (レポート) 。CiteSeerX 10.1.1.377.2593。

[1] Ella, Bingham; Heikki, Mannila (2001). 「次元削減におけるランダム投影: 画像およびテキストデータへの応用」KDD - 2001: 第 7 回 ACM SIGKDD 国際知識発見およびデータマイニング会議の議事録。ニューヨーク: Association for Computing Machinery。pp. 245–250。CiteSeerX 10.1.1.24.5135。doi :10.1145/502512.502546。

[2] ジョンソン、ウィリアム B. ;リンデンシュトラウス、ジョラム(1984)。「ヒルベルト空間へのリプシッツ写像の拡張」。現代解析と確率の会議 (コネチカット州ニューヘブン、1982) 。現代数学。第 26 巻。プロビデンス、ロードアイランド州: アメリカ数学協会。pp. 189–206。doi :10.1090/conm/026/ 737400。ISBN 9780821850305. MR 0737400. S2CID 117819162.。

[3] Bingham, Ella; Mannila, Heikki (2014 年 5 月 6 日)。「次元削減におけるランダム投影: 画像およびテキストデータへの応用」(PDF)。

[4] Achlioptas, Dimitris (2001). 「データベースに適したランダム投影」。第 20 回ACM SIGMOD-SIGACT-SIGART シンポジウム「データベースシステムの原理 - PODS '01」の議事録。274 ～ 281 ページ。CiteSeerX 10.1.1.28.6652。doi : 10.1145 / 375551.375608。ISBN 978-1581133615. S2CID 2640788。

[5] Li, Ping; Hastie, Trevor; Church, Kenneth (2006). 「非常にスパースなランダム投影」。知識発見とデータマイニングに関する第 12 回 ACM SIGKDD 国際会議の議事録。pp . 287–296。doi :10.1145 / 1150402.1150436。ISBN 1595933395. S2CID 7995734。

[6] Kane, Daniel M.; Nelson, Jelani (2014). 「Sparser Johnson-Lindenstrauss Transforms」. Journal of the ACM . 61 (1): 1–23. arXiv : 1012.1577 . doi :10.1145/2559902. MR 3167920. S2CID 7821848.

[7] Charikar, Moses (2002)。「丸めアルゴリズムによる類似性推定手法」。第34 回 ACM コンピューティング理論シンポジウムの議事録。第 1 巻。380 ～ 388 ページ。doi :10.1145/ 509907.509965。ISBN 1581134959. S2CID 4229473。

[8] Freund, Yoav; Dasgupta, Sanjoy; Kabra, Mayank; Verma, Nakul (2007). 「ランダム投影を用いた多様体構造の学習」.第20回国際神経情報処理システム会議. 1 (1): 473–480.

[9] Boufounos, Petros; Baraniuk, Richard (2008). 「1 ビット圧縮センシング」.第 42 回情報科学およびシステム年次会議. 1 (1): 16–21. doi :10.1109/CISS.2008.4558487. S2CID 206563812.

[10] Li, Xiaoyun; Li, Ping (2019). 「量子化圧縮学習の一般化誤差分析」.第33回国際神経情報処理システム会議. 1 : 15150–15160.

[11] カイネン、ポール C. ;クルコヴァ、ベラ(1993)、「ユークリッド空間の準直交次元」、応用数学レター、6 (3): 7–10、doi : 10.1016/0893-9659(93)90023-G、MR 1347278

[12] Hecht-Nielsen, R. (1994). 「コンテキストベクトル: 生データから自己組織化された汎用近似意味表現」。Zurada, Jacek M.、Marks, Robert Jackson、Robinson, Charles J. (編)。計算知能: 生命の模倣。IEEE。pp. 43–56。ISBN 978-0-7803-1104-6。

[GorbanTyukin2016-13] Gorban, Alexander N. ; Tyukin, Ivan Y.; Prokhorov, Danil V.; Sofeikov, Konstantin I. (2016). 「ランダム基数による近似: 賛否両論」.情報科学. 364–365: 129–145. arXiv : 1506.04631 . doi :10.1016/j.ins.2015.09.021. S2CID 2239376.

[14] Ravindran, Siddharth (2020). 「k近傍法（k-NN）を用いたビッグデータ分類における次元削減のためのデータ非依存再利用可能投影（DIRP）手法」。全米科学アカデミー科学レター。43 :13–21。doi : 10.1007 /s40009-018-0771-6。S2CID 91946077。

[15] Siddharth, R.; Aghila, G. (2020年7月). 「RandPro - Rでの高次元多変量データ分析のためのランダム投影ベースの特徴抽出の実用的な実装」. SoftwareX . 12 : 100629. Bibcode :2020SoftX..1200629S. doi : 10.1016/j.softx.2020.100629 .