ランダム投影
Technique to reduce dimensionality of points in Euclidean space

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

次元削減

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

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

方法

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

ランダム射影では、元の次元データが、左辺にランダム行列を乗じることで、次元部分空間に射影されます。行列表記法を用いると、元のN個のd次元観測値集合がd次元の場合、k次元部分空間へのデータの射影はk次元部分空間となります。ランダム射影は計算的に単純です。ランダム行列「R」を作成し、データ行列Xをk次元の次元に射影します。データ行列Xが疎行列で、列ごとに約c個の非ゼロ要素がある場合、この演算の複雑さはk次元です。[3] d {\displaystyle d} k {\displaystyle k} R ∈ R k × d {\displaystyle R\in \mathbb {R} ^{k\times d}} X d × N {\displaystyle X_{d\times N}} X k × N R P = R k × d X d × N {\displaystyle X_{k\times N}^{RP}=R_{k\times d}X_{d\times N}} d × N {\displaystyle d\times N} O ( d k N ) {\displaystyle O(dkN)} O ( c k N ) {\displaystyle O(ckN)}

直交ランダム投影

単位ベクトルはランダム部分空間に直交射影することができる。 を元の単位ベクトルとし、をその射影とする。ノルム二乗分布は、単位球面上に一様にサンプリングされたランダム点をその最初の座標に射影した場合と同じ分布に従う。これは、多変量ガウス分布 からランダム点をサンプリングし、それを正規化するのと等価である。 u {\displaystyle u} v {\displaystyle v} ‖ v ‖ 2 2 {\displaystyle \|v\|_{2}^{2}} k {\displaystyle k} x ∼ N ( 0 , I d × d ) {\displaystyle x\sim {\mathcal {N}}(0,I_{d\times d})}

したがって、は と同じ分布を持ちます。ベータ分布のカイ 2 乗構成により、 は分布 を持ち、平均 となります。 ‖ v ‖ 2 2 {\displaystyle \|v\|_{2}^{2}} ∑ i = 1 k x i 2 ∑ i = 1 k x i 2 + ∑ i = k + 1 d x i 2 {\displaystyle {\frac {\sum _{i=1}^{k}x_{i}^{2}}{\sum _{i=1}^{k}x_{i}^{2}+\sum _{i=k+1}^{d}x_{i}^{2}}}} Beta ⁡ ( k / 2 , ( d − k ) / 2 ) {\displaystyle \operatorname {Beta} (k/2,(d-k)/2)} k / d {\displaystyle k/d}

任意の濃度不等式 が成り立つ。[4] : 50  P r [ | ‖ v ‖ 2 − k d | ≥ ϵ k d ] ≤ 3 exp ⁡ ( − k ϵ 2 / 64 ) {\displaystyle Pr\left[\left|\|v\|_{2}-{\frac {k}{d}}\right|\geq \epsilon {\sqrt {\frac {k}{d}}}\right]\leq 3\exp \left(-k\epsilon ^{2}/64\right)} ϵ ∈ ( 0 , 1 ) {\displaystyle \epsilon \in (0,1)}

ガウスランダム投影

ランダム行列Rは、ガウス分布を用いて生成できます。最初の行は、から一様に選択されたランダムな単位ベクトルです。2行目は、最初の行に直交する空間からのランダムな単位ベクトル、3行目は最初の2行に直交する空間からのランダムな単位ベクトル、というように続きます。このようにRを選択することで、以下の特性が満たされます。 S d − 1 {\displaystyle S^{d-1}}

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

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

アクリオプタス[5]は、ランダム行列はより効率的にサンプリングできることを示した。完全な行列は、IIDに従ってサンプリングすることができる。

R i , j = 3 / k × { + 1 with probability  1 6 0 with probability  2 3 − 1 with probability  1 6 {\displaystyle R_{i,j}={\sqrt {3/k}}\times {\begin{cases}+1&{\text{with probability }}{\frac {1}{6}}\\0&{\text{with probability }}{\frac {2}{3}}\\-1&{\text{with probability }}{\frac {1}{6}}\end{cases}}}

あるいは、完全な行列をIIDに従ってサンプリングすることもできます。どちらも整数演算で計算できるため、データベースアプリケーションに効率的です。より関連した研究は[6]で行われています。 R i , j = 1 / k × { + 1 with probability  1 2 − 1 with probability  1 2 {\displaystyle R_{i,j}={\sqrt {1/k}}\times {\begin{cases}+1&{\text{with probability }}{\frac {1}{2}}\\-1&{\text{with probability }}{\frac {1}{2}}\end{cases}}}

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

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

ランダム射影は、量子化（離散化）によってさらに凝縮することができ、1ビット（符号ランダム射影）または複数ビットで実現できます。これは、SimHash [8]、RPツリー[9]、その他のメモリ効率の高い推定・学習手法の構成要素です。[10] [11]

大きな準直交基地

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

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

実装

参照

参考文献

  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 978-0-8218-5030-5. MR  0737400. S2CID  117819162.。
  3. ^ Bingham, Ella; Mannila, Heikki (2014年5月6日). 「次元削減におけるランダム投影：画像およびテキストデータへの応用」(PDF) .
  4. ^ Mahoney, Michael W. (2016-08-16)、ランダム化線形代数の講義ノート、arXiv : 1608.04481
  5. ^ Achlioptas, Dimitris (2001). 「データベースフレンドリーなランダムプロジェクション」.第20回ACM SIGMOD-SIGACT-SIGARTシンポジウム「データベースシステムの原理 - PODS '01」の議事録. pp.  274– 281. CiteSeerX 10.1.1.28.6652 . doi :10.1145/375551.375608. ISBN  978-1-58113-361-5. S2CID  2640788。
  6. ^ Li, Ping; Hastie, Trevor; Church, Kenneth (2006). 「非常にスパースなランダム投影」.第12回ACM SIGKDD国際会議「知識発見とデータマイニング」の議事録. pp.  287– 296. doi :10.1145/1150402.1150436. ISBN 1-59593-339-5. S2CID  7995734。
  7. ^ Kane, Daniel M.; Nelson, Jelani (2014). 「スパーサー・ジョンソン・リンデンシュトラウス変換」. Journal of the ACM . 61 (1): 1– 23. arXiv : 1012.1577 . doi :10.1145/2559902. MR  3167920. S2CID  7821848.
  8. ^ Charikar, Moses (2002). 「丸めアルゴリズムによる類似度推定手法」.第34回ACMコンピューティング理論シンポジウム議事録. 第1巻. pp.  380– 388. doi :10.1145/509907.509965. ISBN 1-58113-495-9. S2CID  4229473。
  9. ^ Freund, Yoav; Dasgupta, Sanjoy; Kabra, Mayank; Verma, Nakul (2007). 「ランダム射影を用いた多様体構造の学習」.第20回国際神経情報処理システム会議. 1 (1): 473– 480.
  10. ^ Boufounos, Petros; Baraniuk, Richard (2008). 「1ビット圧縮センシング」. 2008年 第42回情報科学・システム年次会議. 第1巻. pp.  16– 21. doi :10.1109/CISS.2008.4558487. ISBN 978-1-4244-2246-3. S2CID  206563812。
  11. ^ Li, Xiaoyun; Li, Ping (2019). 「量子化圧縮学習の一般化誤差解析」.第33回国際神経情報処理システム会議. 1 : 15150–15160 .
  12. ^ カイネン、ポール・C. ;クルコヴァ、ヴェラ(1993)、「ユークリッド空間の準直交次元」、応用数学レター、6 (3): 7– 10、doi : 10.1016/0893-9659(93)90023-G、MR  1347278
  13. ^ Hecht-Nielsen, R. (1994). 「コンテキストベクトル：生データから自己組織化された汎用近似意味表現」. Zurada, Jacek M.; Marks, Robert Jackson; Robinson, Charles J. (編). 『計算知能：生命の模倣』 IEEE. pp.  43– 56. ISBN 978-0-7803-1104-6。
  14. ^ Gorban, Alexander N. ; Tyukin, Ivan Y.; Prokhorov, Danil V.; Sofeikov, Konstantin I. (2016). 「ランダム基数による近似：賛成と反対」. Information Sciences . 364– 365: 129– 145. arXiv : 1506.04631 . doi :10.1016/j.ins.2015.09.021. S2CID  2239376.
  15. ^ Ravindran, Siddharth (2020). 「k近傍法（k-NN）を用いたビッグデータ分類における次元削減のためのデータ非依存型再利用可能射影（DIRP）手法」. National Academy Science Letters . 43 : 13–21 . doi :10.1007/s40009-018-0771-6. S2CID  91946077.
  16. ^ 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 .
  • ラムダス、アディティア. ランダム投影へのランダム入門（レポート）. CiteSeerX  10.1.1.377.2593 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Random_projection&oldid=1315046883"