랜덤 투영법

수학과 통계에서 랜덤 투영은 유클리드 공간에 있는 점 집합의 치수성을 줄이기 위해 사용되는 기법이다.무작위 투영 방법은 다른 방법과^{[citation needed]} 비교할 때 검정력, 단순성 및 낮은 오류율로 알려져 있다.실험 결과에 따르면 랜덤 투영은 거리를 잘 보존하지만 경험적 결과는 희박하다.^[1]그것들은 무작위 인덱싱이라는 이름으로 많은 자연어 작업에 적용되어 왔다.

차원성 감소

차원성 감소는 이름에서 알 수 있듯이 통계학이나 기계학습의 다양한 수학적 방법을 사용하여 무작위 변수의 수를 줄이고 있다.차원성 감소는 대형 데이터 세트를 관리하고 조작하는 문제를 줄이기 위해 자주 사용된다.치수성 감소 기법은 일반적으로 다지관의 내적인 치수성을 결정할 때 선형 변환을 사용하고 다지관의 주요 방향을 추출한다.이를 위해 주성분 분석, 선형 판별 분석, 표준 상관 분석, 이산 코사인 변환, 랜덤 투영 등 다양한 관련 기법이 있다.

무작위 투영은 더 빠른 처리 시간과 더 작은 모델 크기를 위해 통제된 양의 오차를 거래함으로써 데이터의 차원성을 감소시키는 간단하고 계산적으로 효율적인 방법이다.랜덤 투영 매트릭스의 치수와 분포는 데이터 집합의 두 표본 사이의 쌍방향 거리를 근사적으로 보존하도록 제어된다.

방법

무작위 투영 뒤의 핵심 개념은 벡터 공간의 점들이 충분히 높은 차원이라면, 점 사이의 거리를 ^[2]근사적으로 보존하는 방법으로 적절한 저차원 공간에 투영될 수 있다고 기술한 존슨-린덴스트라우스 보조정리기에 제시되어 있다.

무작위 투영에서 원래 $k\times d$ 데이터는 랜덤 $k\times d$ $k\times d$ d $k\times d$ $k\times d$ - 치수 행렬 R을 사용하여 k-차원(k< d)^{[citation needed]} 하위 공간에 투영된다.행렬 표기법 사용:If $X_{d\times N}$ is the original set of N d-dimensional observations, then $X_{k\times N}^{RP}=R_{k\times d}X_{d\times N}$ is the projection of the data onto a lower k-dimensional subspace.무작위 투영은 계산적으로 간단하다: 랜덤 행렬 "R"을 형성하고 $d\times N$ × $d\times N$ (\ $displaystyle$ d $\times$ N $)$ 의 $d\times N$ K 치수에 $O(dkN)$ N ( $O(dkN)$ $O(dkN)$ ) $O(dkN)$ {\displaystyle O( $dkN)$ X를 투영한다 $O(dkN)$ 데이터 행렬 X가 열당 약 c nonzero로 희박하다면, 이 작업의 복잡성은 순서 O ( $O(ckN)$ 이다. $O(ckN)$ $O(ckN)$ ^[3].

가우스 랜덤 투영법

랜덤 행렬 R은 가우스 분포를 사용하여 생성할 수 있다.첫 번째 행은 $S^{d-1}$ $S^{d-1}$ - 1 ${\$ 에서 균일하게 선택한 임의 단위 벡터다 $S^{d-1}$ 두 번째 행은 첫 번째 행과 직교하는 공간으로부터 무작위 단위 벡터, 세 번째 행은 직교하는 공간으로부터 처음 두 행까지의 임의 단위 벡터 등이다.이러한 방법으로 R을 선택하면 다음과 같은 특성이 충족된다.

구면 대칭:직교 행렬 $A\in O(d)$ $A\in O(d)$ $A\in O(d)$ ( $A\in O(d)$ ) ${\displaystyle A\in O(d$ 에 대해 RA와 R은 동일한 분포를 가진다.
직교 분포:R의 행은 서로 직교한다.
정규성:R의 행은 단위 길이 벡터다.

더 계산적으로 효율적인 무작위 투영

Achlioptas는^[4] 가우스 분포가 다음과 같은 훨씬 단순한 분포로 대체될 수 있다는 것을 보여주었다.

R_{i,j}={\sqrt {3}}\times {\begin{cases}+1&{\text{with probability }}{\frac {1}{6}}\\0&{\text{with probability }}{\frac {4}{6}}\\-1&{\text{with probability }}{\frac {1}{6}}\end{cases}}

이것은 계산이 정수 산수를 사용하여 수행될 수 있기 때문에 데이터베이스 애플리케이션에 효율적이다.더 많은 관련 연구가 다음에서 수행된다.^[5]

이후 스파스 JL 변환 작업에서 열당 0이 거의 없는 분포를 고르게 하면서 정수 산수를 사용하는 방법을 보여주었다.^[6]이것은 스파스 내장 매트릭스가 데이터를 더 낮은 차원으로 더 빨리 투영할 수 있다는 것을 의미하기 때문에 유리하다.

정량화를 사용한 랜덤 투영

랜덤 투영은 1비트(사인 랜덤 투영) 또는 다중 비트로 정량화(분산)를 통해 추가로 응축될 수 있다.심해시,^[7] MACXUT,^[8] 그리고 다른 기억 효율적 추정과 학습 방법의 구성 요소다.^[9]^[10]

큰 콰시오르토건 베이스

존슨-린덴스트라우스 보조정리기는 고차원 공간에 있는 큰 벡터 집합은 거리의 대략적인 보존으로 훨씬 더 낮은(그러나 여전히 높은) 차원 n의 공간에 선형적으로 매핑될 수 있다고 기술하고 있다.이러한 효과에 대한 설명 중 하나는 n차원 유클리드 공간의 기하급수적으로 높은 퀘이시오곤 차원이다.^[11]n-차원 유클리드 공간에는 거의 직교 벡터(내부 제품 값이 작은) 세트가 기하급수적으로 많다.이 관찰은 고차원 데이터의 색인화에 유용하다.^[12]

대형 랜덤 집합의 퀘이셔토곤성은 머신러닝에서 랜덤 근사 방법에 중요하다.높은 치수에서, 기하급수적으로 많은 수의 무작위 및 독립적으로 선택된 벡터는 구체의 등분포로부터 (그리고 많은 다른 분포로부터) 거의 직교하며, 1에 가까운 확률이다.^[13]이것은 임의로 그리고 독립적으로 선택된 벡터의 선형 결합에 의해 그러한 고차원 공간의 요소를 나타내기 위해, 우리가 선형 결합에 경계 계수를 사용할 경우 기하급수적으로 큰 길이의 표본을 생성해야 할 경우가 종종 있다는 것을 암시한다.반면 임의로 큰 값을 갖는 계수가 허용될 경우, 근사치에 충분한 임의로 생성된 원소의 수는 데이터 공간의 치수보다 훨씬 적다.

구현

RandPro - 랜덤 투영을 위한 R 패키지
sklearn.random_projection - 임의 투영을 위한 Python 모듈
Weka 구현 [1]

참고 항목

참조

^ Ella, Bingham; Heikki, Mannila (2001). "Random projection in dimensionality reduction: Applications to image and text data". KDD-2001: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: Association for Computing Machinery. pp. 245–250. CiteSeerX 10.1.1.24.5135. doi:10.1145/502512.502546.
^ Johnson, William B.; Lindenstrauss, Joram (1984). "Extensions of Lipschitz mappings into a Hilbert space". Conference in Modern Analysis and Probability (New Haven, Conn., 1982). Contemporary Mathematics. Vol. 26. Providence, RI: American Mathematical Society. pp. 189–206. doi:10.1090/conm/026/737400. ISBN 9780821850305. MR 0737400..
^ Bingham, Ella; Mannila, Heikki (2001). "Random projection in dimensionality reduction: Applications to image and text data". KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 245–250. doi:10.1145/502512.502546.
^ Achlioptas, Dimitris (2001). "Database-friendly random projections". Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems - PODS '01. pp. 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). "Very sparse random projections". 12th ACM SIGKDD international conference on Knowledge discovery and data mining (1): 287–296. doi:10.1145/1150402.1150436.
^ 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). "Similarity estimation techniques from rounding algorithms". 34-th annual ACM symposium on Theory of computing. 1 (1): 380–388. doi:10.1145/509907.509965.
^ Freund, Yoav; Dasgupta, Sanjoy; Kabra, Mayank; Verma, Nakul (2007). "Learning the structure of manifolds using random projections". 20th International Conference on Neural Information Processing Systems. 1 (1): 473–480.
^ Boufounos, Petros; Baraniuk, Richard (2008). "1-bit Compressive Sensing". 42nd Annual Conference on Information Sciences and Systems. 1 (1): 16–21.
^ Li, Xiaoyun; Li, Ping (2019). "Generalization error analysis of quantized compressive learning". 33rd International Conference on Neural Information Processing Systems. 1: 15150–15160.
^ Kainen, Paul C.; Kůrková, Věra (1993), "Quasiorthogonal dimension of Euclidean spaces", Applied Mathematics Letters, 6 (3): 7–10, doi:10.1016/0893-9659(93)90023-G, MR 1347278
^ Hecht-Nielsen, R. (1994). "Context vectors: General-purpose approximate meaning representations self-organized from raw data". In Zurada, Jacek M.; Marks, Robert Jackson; Robinson, Charles J. (eds.). Computational Intelligence: Imitating Life. IEEE. pp. 43–56. ISBN 978-0-7803-1104-6.
^ Gorban, Alexander N.; Tyukin, Ivan Y.; Prokhorov, Danil V.; Sofeikov, Konstantin I. (2016). "Approximation with Random Bases: Pro et Contra". Information Sciences. 364–365: 129–145. arXiv:1506.04631. doi:10.1016/j.ins.2015.09.021. S2CID 2239376.
^ Ravindran, Siddharth (2020). "A Data-Independent Reusable Projection (DIRP) Technique for Dimension Reduction in Big Data Classification Using k-Nearest Neighbor (k-NN)". National Academy Science Letters. 43: 13–21. doi:10.1007/s40009-018-0771-6. S2CID 91946077.
^ Siddharth, R.; Aghila, G. (July 2020). "RandPro- A practical implementation of random projection-based feature extraction for high dimensional multivariate data analysis in R". SoftwareX. 12: 100629. Bibcode:2020SoftX..1200629S. doi:10.1016/j.softx.2020.100629.

추가 읽기

Fodor, Imola K (2002). A survey of dimension reduction techniques (Report). CiteSeerX 10.1.1.8.5098.
Menon, Aditya Krishna (2007). Random projections and applications to dimensionality reduction (Thesis). CiteSeerX 10.1.1.164.640.
Ramdas, Aditya. A Random Introduction To Random Projections (Report). CiteSeerX 10.1.1.377.2593.

[1] Ella, Bingham; Heikki, Mannila (2001). "Random projection in dimensionality reduction: Applications to image and text data". KDD-2001: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: Association for Computing Machinery. pp. 245–250. CiteSeerX 10.1.1.24.5135. doi:10.1145/502512.502546.

[2] Johnson, William B.; Lindenstrauss, Joram (1984). "Extensions of Lipschitz mappings into a Hilbert space". Conference in Modern Analysis and Probability (New Haven, Conn., 1982). Contemporary Mathematics. Vol. 26. Providence, RI: American Mathematical Society. pp. 189–206. doi:10.1090/conm/026/737400. ISBN 9780821850305. MR 0737400..

[3] Bingham, Ella; Mannila, Heikki (2001). "Random projection in dimensionality reduction: Applications to image and text data". KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 245–250. doi:10.1145/502512.502546.

[4] Achlioptas, Dimitris (2001). "Database-friendly random projections". Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems - PODS '01. pp. 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). "Very sparse random projections". 12th ACM SIGKDD international conference on Knowledge discovery and data mining (1): 287–296. doi:10.1145/1150402.1150436.

[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). "Similarity estimation techniques from rounding algorithms". 34-th annual ACM symposium on Theory of computing. 1 (1): 380–388. doi:10.1145/509907.509965.

[8] Freund, Yoav; Dasgupta, Sanjoy; Kabra, Mayank; Verma, Nakul (2007). "Learning the structure of manifolds using random projections". 20th International Conference on Neural Information Processing Systems. 1 (1): 473–480.

[9] Boufounos, Petros; Baraniuk, Richard (2008). "1-bit Compressive Sensing". 42nd Annual Conference on Information Sciences and Systems. 1 (1): 16–21.

[10] Li, Xiaoyun; Li, Ping (2019). "Generalization error analysis of quantized compressive learning". 33rd International Conference on Neural Information Processing Systems. 1: 15150–15160.

[11] Kainen, Paul C.; Kůrková, Věra (1993), "Quasiorthogonal dimension of Euclidean spaces", Applied Mathematics Letters, 6 (3): 7–10, doi:10.1016/0893-9659(93)90023-G, MR 1347278

[12] Hecht-Nielsen, R. (1994). "Context vectors: General-purpose approximate meaning representations self-organized from raw data". In Zurada, Jacek M.; Marks, Robert Jackson; Robinson, Charles J. (eds.). Computational Intelligence: Imitating Life. 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). "Approximation with Random Bases: Pro et Contra". Information Sciences. 364–365: 129–145. arXiv:1506.04631. doi:10.1016/j.ins.2015.09.021. S2CID 2239376.

[14] Ravindran, Siddharth (2020). "A Data-Independent Reusable Projection (DIRP) Technique for Dimension Reduction in Big Data Classification Using k-Nearest Neighbor (k-NN)". National Academy Science Letters. 43: 13–21. doi:10.1007/s40009-018-0771-6. S2CID 91946077.

[15] Siddharth, R.; Aghila, G. (July 2020). "RandPro- A practical implementation of random projection-based feature extraction for high dimensional multivariate data analysis in R". SoftwareX. 12: 100629. Bibcode:2020SoftX..1200629S. doi:10.1016/j.softx.2020.100629.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Search