Schița tensorului

Schița tensorală este o tehnică de reducere a dimensionalității utilizată în statistici, învățare automată și algoritmi de date mari [1] [2] . Este eficient în special pentru vectorii care au o structură tensorală. O astfel de schiță poate fi folosită pentru a accelera combinarea biliniară în rețelele neuronale și este o piatră de temelie în mulți algoritmi numerici de algebră liniară [3] .

Istorie

Termenul de schiță tensorală (schiță) a fost inventat în 2013 [4] și descris ca metodă de către Rasmus Peg [5] în același an .

La început, metoda corespunzătoare s-a bazat pe utilizarea transformării rapide Fourier pentru a implementa convoluția rapidă într-un mod similar cu o schiță de referință . Ca rezultat al cercetărilor ulterioare, a fost generalizat la o clasă mult mai mare de metode de reducere a dimensionalității folosind proiecții ale tensorilor aleatorii.

Proiecții tensorale

Una dintre variantele schiței tensorului se bazează pe utilizarea produsului final al matricelor propus de Slyusar V. I. [ 6] în 1996 ( face-splitting product ) [7] [8] [9] [10] [11] .

Produsul final a două matrice cu același număr de rânduri și are forma [7] [8] [9] [12] : $\mathbf {C} \in \mathbb {R} ^{3\times 3}$ $\mathbf {D} \in \mathbb {R} ^{3\times 3}$ $\mathbf {C} \bullet \mathbf {D} =\left[{\begin{array}{c }\mathbf {C} _{1}\otimes \mathbf {D} _{1}\\ \hline \mathbf {C} _{2}\otimes \mathbf {D} _{2}\\\hline \mathbf {C} _{3}\otimes \mathbf {D} _{3}\\\end {matrice}}\right]=\left[{\begin{array}{ccccccccc }\mathbf {C} _{1,1}\mathbf {D} _{1,1}&\mathbf {C} _{ 1,1}\mathbf {D} _{1,2}&\mathbf {C} _{1,1}\mathbf {D} _{1,3}&\mathbf {C} _{1,2} \mathbf {D} _{1,1}&\mathbf {C} _{1,2}\mathbf {D} _{1,2}&\mathbf {C} _{1,2}\mathbf {D } _{1,3}&\mathbf {C} _{1,3}\mathbf {D} _{1,1}&\mathbf {C} _{1,3}\mathbf {D} _{1 ,2}&\mathbf {C} _{1,3}\mathbf {D} _{1,3}\\\hline \mathbf {C} _{2,1}\mathbf {D} _{2, 1}&\mathbf {C} _{2,1}\mathbf {D} _{2,2}&\mathbf {C} _{2,1}\mathbf {D} _{2,3}&\ mathbf {C} _{2,2}\mathbf {D} _{2,1}&\mathbf {C} _{2,2}\mathbf {D} _{2,2}&\mathbf {C} _{2,2}\mathbf {D} _{2,3}&\mathbf {C} _{2,3}\mathbf {D} _{2,1}&\mathbf {C} _{2, 3}\mathbf {D} _{2,2}&\mathbf {C} _{2,3}\mathbf {D} _{2,3}\\\hline \mathbf {C} _{3,1 }\mathbf {D} _{3,1}&\mathbf {C} _{3,1 }\mathbf {D} _{3,2}&\mathbf {C} _{3,1}\mathbf {D} _{3,3}&\mathbf {C} _{3,2}\mathbf { D} _{3,1}&\mathbf {C} _{3,2}\mathbf {D} _{3,2}&\mathbf {C} _{3,2}\mathbf {D} _{ 3,3}&\mathbf {C} _{3,3}\mathbf {D} _{3,1}&\mathbf {C} _{3,3}\mathbf {D} _{3,2} &\mathbf {C} _{3,3}\mathbf {D} _{3,3}\end{array}}\right].$

Oportunitatea utilizării acestei lucrări constă în proprietatea sa:

(\mathbf {C} \bullet \mathbf {D} )(x\otimes y)=\mathbf {C} x\circ \mathbf {D} y=\left[{\begin{array}{c }(\mathbf {C} x)_{1}(\mathbf {D} y)_{1}\\(\mathbf {C} x)_{2}(\mathbf {D} y)_{2 }\\\vdots \end{array}}\right],

unde este produsul Hadamard în funcție de elemente . $\circ$

Pe această bază, o schiță tensorală arbitrară a formei poate fi reprezentată ca , unde matricele și au o dimensiune mai mică și . Deoarece operațiile și pot fi efectuate în timp liniar și , în consecință, trecerea la reprezentare face posibilă efectuarea înmulțirii prin vectori cu o structură tensorală mult mai rapidă decât se formează expresia originală , și anume, în timp . $\mathbf {M} (y\otimes z)$ $\mathbf {M'} y\circ \mathbf {M''} z$ $\mathbf {M'}$ $\mathbf {M''}$ $\mathbf {M'} \bullet \mathbf {M''} =\mathbf {M}$ $\mathbf {M'} y$ $\mathbf {M''} z$ $kd_{1)$ $kd_{2)$ $\mathbf {M'} \bullet \mathbf {M''}$ $\mathbf {M} (y\otimes z)$ $kd=kd_{1}d_{2}$

Pentru tensorii de ordin superior, cum ar fi , economiile vor fi și mai semnificative. $x=y\otimes z\otimes t$

O astfel de transformare satisface lema privind micile distorsiuni ale datelor de intrare cu dimensiuni mari.

Vezi și

Note

↑ Descompunerea Tucker de rang scăzut a tensoarelor mari folosind: Tensor Sketch . amath.colorado.edu . Boulder, Colorado: Universitatea din Colorado Boulder . Preluat la 30 iulie 2020. Arhivat din original la 14 februarie 2019. (nedefinit)
↑ Ahle, Thomas; Knudsen, Jakob Schiță tensorului aproape optimă . Researchgate (3 septembrie 2019). Preluat la 11 iulie 2020. Arhivat din original la 14 iulie 2020. (nedefinit)
↑ Woodruff, David P. „Sketching as a Tool for Numerical Linear Algebra”. Informatică teoretică 10.1-2 (2014): 1-157.
↑ Ninh, Pham; Rasmus, Pagh (2013). Nuclee polinomiale rapide și scalabile prin hărți de caracteristici explicite . Conferința internațională SIGKDD privind descoperirea cunoștințelor și extragerea datelor. Asociația pentru Mașini de Calcul. DOI : 10.1145/2487575.2487591 .
↑ Rasmus, Pagh (2013). Înmulțirea matriceală comprimată. ACM Transactions on Computation Theory, august 2013 Articolul Nr.: 9 . Asociația pentru Mașini de Calcul. DOI : 10.1145/2493252.2493254 .
↑ Anna Esteve, Eva Boj & Josep Fortiana (2009): Interaction Terms in Distance-Based Regression, Communications in Statistics - Theory and Methods, 38:19, P. 3501 [1] Arhivat 26 aprilie 2021 la Wayback Machine
↑ 1 2 Slyusar, VI (27 decembrie 1996). „Produse finale în matrice în aplicații radar” (PDF) . Radioelectronică și sisteme de comunicații.– 1998, voi. 41; Numărul 3 : 50-53. Arhivat (PDF) din original pe 27.07.2020 . Accesat 2020-07-30 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ 1 2 Slyusar, VI Model analitic al matricei de antene digitale pe baza produselor matricei de divizare a feței // Proc . ICATT-97, Kiev: jurnal. - 1997. - 20 mai. - P. 108-109 . Arhivat din original pe 25 ianuarie 2020.
↑ 1 2 Slyusar, VI A Family of Face Products of Matrices and its Properties // Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz : journal. - 1999. - Vol. 35 , nr. 3 . - P. 379-384 . - doi : 10.1007/BF02733426 . Arhivat din original pe 25 ianuarie 2020.
↑ Slyusar, VI Produse faciale generalizate ale matricelor în modele de rețele de antene digitale cu canale neidentice // Radioelectronics and Communications Systems : journal . - 2003. - Vol. 46 , nr. 10 . - P. 9-17 . Arhivat din original pe 20 septembrie 2020.
↑ Minochkin A.I., Rudakov V.I., Slyusar V.I. Fundamentele cercetării militaro-tehnice. Teorie și aplicații. Volum. 2. Sinteza mijloacelor de suport informaţional pentru armament şi tehnică militară // Ed. A.P. Kovtunenko. - Kiev: „Granmna”. - 2012. C. 7 - 98; 354 - 521 (2012). Preluat la 30 iulie 2020. Arhivat din original la 25 ianuarie 2020. (nedefinit)
↑ Slyusar, VI (15.09.1997). „Noi operațiuni de produs matrice pentru aplicații de radare” (PDF) . Proc. Probleme directe și inverse ale teoriei undelor electromagnetice și acustice (DIPED-97), Lviv. : 73-74. Arhivat (PDF) din original pe 25.01.2020 . Accesat 2020-07-31 . Parametrul depreciat folosit |deadlink=( ajutor )

Inteligenţă artificială
Poveste	Istoria inteligenței artificiale Iarna inteligenței artificiale Seminarul Dartmouth
Filozofie	Testul Turing Cameră chinezească Inteligență artificială puternică și slabă Inteligență artificială prietenoasă Etica inteligenței artificiale Problema de control
Directii	Abordarea agentului Control adaptiv Ingineria cunoașterii Model de sistem viabil Învățare automată Retea neurala logica fuzzy procesarea limbajului natural Recunoasterea formelor Inteligența roiului AI simbolic Algoritmi evolutivi Sistem expert
Aplicație	Control vocal Problema de clasificare Clasificarea documentelor Gruparea documentelor analiza grupului Căutare locală Traducere automată Recunoaștere optică a caracterelor Recunoaștere a vorbirii Scris de mana recunoscut Joc AI
Cercetători	Charles Babbage Vladimir Vapnik Joseph Weizenbaum Norbert Wiener Viktor Glushkov Vladimir Gorodețki Jan LeCun Alexei Lyapunov John McCarthy Marvin Minsky Allen Newell Seymour Papert Judah Pearl Germogen Pospelov Dmitri Pospelov Frank Rosenblatt Herbert Alexander Simon Alan Turing Patrick Winston Victor Finn Serghei Fomin Demis Hassabis Geoffrey Hinton Noam Chomsky Claude Shannon Andrew Eun Eliezer Iudkovski

Învățare automată și extragerea datelor
Sarcini	Problema de clasificare Învățați fără profesor Învățare asistată de profesor Analiza regresiei AutoML Regulile de asociere Extragerea caracteristicilor Antrenamentul trăsăturilor Antrenament de clasare Derivarea gramaticală Învățare online
Învățarea cu un profesor	metoda k-cel mai apropiat vecin Clasificator naiv Bayes arborele de decizie Suport mașină vectorială Regresie liniara Regresie logistică perceptron Ansambluri de modele Bagare stimularea pădure la întâmplare Metoda vectorială relevantă
analiza grupului	metoda k-means Metoda de grupare fuzzy Gruparea ierarhică algoritmul EM MESTEACĂN VINDECA DBSCAN OPTICA Schimbarea medie
Reducerea dimensionalității	Analiza factorilor Metoda componentei principale CCA ICA LDA Expansiunea nenegativă a matricei t-SNE
Prognoza structurală	Modelul probabilistic grafic Rețeaua bayesiană Modelul Markov ascuns CRF
Detectarea anomaliilor	metoda k-cel mai apropiat vecin Nivelul de emisie local
Modele grafice probabilistice	Rețeaua bayesiană Rețeaua Markov Modelul Markov ascuns
Rețele neuronale	Mașină Boltzmann limitată hartă de auto-organizare Funcția de activare Sigmoid softmax Funcția de bază radială Metoda de propagare înapoi Invatare profunda Perceptron multistrat Rețea neuronală recurentă memorie pe termen lung și scurt Bloc recurent controlat Rețeaua neuronală convoluțională U-Net Autoencoder
Consolidarea învățării	procesul Markov Ecuația Bellman Algoritmul lacom Q-learning SARSA Diferența temporală (TD)
Teorie	Teoria Vapnik-Chervonenkis Dilema părtinire-dispersie Teoria învățării computaționale Minimizarea riscului empiric Occam învață Învățarea PAC Teoria învăţării statistice
Reviste și conferințe	NeurIPS ICML ML JMLR ArXiv:cs.LG