Przyspieszenie osiąga się przez pierwsze przepisanie , gdzie oznacza iloczyn elementarny ( Hadamarda ). Każdy z i można obliczyć w czasie odpowiednio i w tym iloczyn Hadamarda daje całkowity czas . W większości przypadków ta metoda jest znacznie szybsza niż pełne wymagające czasu.
, takich jak są jeszcze bardziej
Historia
Termin szkic tensorowy powstał w 2013 roku, opisując technikę Rasmusa Pagha z tego samego roku. Pierwotnie rozumiano, że używa się szybkiej transformaty Fouriera do szybkiego splotu szkiców zliczania . Późniejsze prace badawcze uogólniły to do znacznie większej klasy redukcji wymiarowości poprzez losowe osadzenie Tensor.
Losowe osadzenie tensorowe zostało wprowadzone w 2010 roku w artykule na temat prywatności różnicowej i zostało po raz pierwszy przeanalizowane przez Rudelsona i in. w 2012 r. w kontekście rzadkiego ożywienia.
Avron i in. jako pierwsi zbadali właściwości osadzania podprzestrzeni szkiców tensorowych, ze szczególnym uwzględnieniem zastosowań w jądrach wielomianowych . W tym kontekście szkic jest wymagany nie tylko do zachowania normy każdego pojedynczego wektora z pewnym prawdopodobieństwem, ale także do zachowania normy wszystkich wektorów w każdej indywidualnej podprzestrzeni liniowej . Jest to znacznie silniejsza właściwość i wymaga większych rozmiarów szkiców, ale pozwala na bardzo szerokie zastosowanie metod jądra, jak opisano w książce Davida Woodruffa.
gdzie elementarnym ( Hadamarda . Ponieważ operację tę można obliczyć w czasie liniowym, pomnożyć na wektorach o strukturze tensorowej znacznie szybciej niż
Konstrukcja z szybką transformatą Fouriera
Szkic tensorowy Phama i Pagha oblicza do , gdzie do niezależnymi szkicu zliczania , splotem wektorowym . Pokazują, że w zdumiewający sposób jest to równe - szkic zliczania iloczynu tensorowego!
Ponieważ jest macierzą ortonormalną , nie ma to wpływu na normę do i można je zignorować. Pozostaje to, że do .
Z drugiej strony,
.
Zastosowanie do macierzy ogólnych
Problem z oryginalnym algorytmem szkicu tensorowego polegał na tym, że wykorzystywał on macierze szkicu zliczania , które nie zawsze są bardzo dobrymi redukcjami wymiarów.
W 2020 roku wykazano, że do stworzenia szkicu tensorowego wystarczą dowolne macierze z wystarczająco losowymi niezależnymi wierszami. Pozwala to na stosowanie macierzy o silniejszych gwarancjach, takich jak rzeczywiste macierze Gaussa Johnsona Lindenstraussa .
W szczególności otrzymujemy następujące twierdzenie
Rozważ macierz z wierszami , mi } . Niech będą niezależne, składające się z i .
wtedy _ dla dowolnego wektora , jeśli
.
W szczególności, jeśli wpisy są otrzymujemy , który pasuje do normalnego Twierdzenie Johnsona _ _
Artykuł pokazuje również, że zależność od jest konieczne w przypadku konstrukcji wykorzystujących projekcje losowe tensorowe z wpisami Gaussa .
Wariacje
Konstrukcja rekurencyjna
Ze względu na wykładniczą zależność od szkicach tensorowych opartych na iloczynie dzielącym twarz , w 2020 roku opracowano inne podejście, które stosuje się do
Możemy osiągnąć ,
.
W tej metodzie stosujemy tylko ogólną metodę szkicowania tensorów, aby uporządkować 2 tensory, co pozwala uniknąć zależności wykładniczej w liczbie rzędów.
to macierz Hadamarda , która umożliwia mnożenie macierzy i wektorów w czasie
to macierz próbkowania, która składa , z wyjątkiem pojedynczej 1 w każdym rzędzie.
taką, która ma iloczyn tensorowy wartości na być w pełni niezależną, możliwe jest obliczenie szybko.
Na przykład niech będą dwoma niezależnymi niech macierzą ukośną . Możemy następnie podzielić w następujący sposób:
Innymi słowy, , dzieli się na dwie transformacje Fasta Johnsona-Lindenstraussa, a całkowita redukcja wymaga czasu zamiast jak w przypadku podejścia bezpośredniego.
To samo podejście można rozszerzyć na obliczanie produktów wyższego stopnia, takich jak
Ahle i in. pokazuje, że jeśli ma wierszy, a następnie ∈ z prawdopodobieństwem , jednocześnie umożliwiając szybkie mnożenie z tensorami stopnia
Jin i wsp. w tym samym roku wykazali podobny wynik dla bardziej ogólnej klasy macierzy zwanej RIP , która obejmuje podpróbkowane macierze Hadamarda. Pokazali, że te macierze umożliwiają podział na tensory, pod warunkiem, że liczba wierszy wynosi . w przypadku jest to zgodne z poprzednim wynikiem.
Te szybkie konstrukcje można ponownie połączyć z podejściem rekurencji wspomnianym powyżej, dając najszybszy ogólny szkic tensorowy.
Szkicowanie uwzględniające dane
Możliwe jest również wykonanie tak zwanego szkicowania tensorowego „świadomego danych”. Zamiast mnożenia losowej macierzy na danych, punkty danych są próbkowane niezależnie z pewnym prawdopodobieństwem zależnym od normy punktu.
Aplikacje
Jawne jądra wielomianowe
Metody jądra są popularne w uczeniu maszynowym , ponieważ dają zaprojektowanemu algorytmowi swobodę projektowania „przestrzeni cech”, w której można mierzyć podobieństwo ich punktów danych. Prosty klasyfikator binarny oparty na jądrze jest oparty na następujących obliczeniach:
Używana w ten sposób metoda jądra nazywana jest „niejawną”. Czasami szybciej jest wykonać „jawną” metodę jądra, w której para funkcji są znalezione takie, że . Pozwala to na wyrażenie powyższego obliczenia jako
gdzie wartość można obliczyć z góry.
Problem z tą metodą polega na tym, że przestrzeń cech może być bardzo duża. To znaczy . Na przykład dla jądra wielomianu otrzymujemy i jest iloczynem tensorowym i gdzie . Jeśli , może znacznie większy niż liczba punktów danych ( więc metoda jawna jest
Ideą szkicu tensorowego jest to, że możemy obliczyć przybliżone funkcje może być nawet mniejszy niż i który nadal ma tę właściwość .
W 2020 roku wykazano, że ta metoda działa nawet w przypadku wielomianów wysokiego stopnia i jąder radialnych funkcji bazowych.
Skompresowane mnożenie macierzy
mamy dwa duże zbiory danych, znaleźć z największymi iloczynami wewnętrznymi . Moglibyśmy obliczyć po prostu spójrz na . zajęłoby to co najmniej prawdopodobnie bliższe standardowych technik mnożenia
Ideą skompresowanego mnożenia macierzy jest ogólna tożsamość
gdzie jest iloczynem tensorowym \ Ponieważ możemy skutecznie obliczyć ( ) przybliżenie do , zsumować, aby uzyskać przybliżenie dla
Kompaktowe łączenie wieloliniowe
Szkice tensorowe można wykorzystać do zmniejszenia liczby potrzebnych zmiennych podczas implementacji łączenia dwuliniowego w sieci neuronowej .
Łączenie dwuliniowe to technika pobierania dwóch wektorów wejściowych tensorowego neuronowej.
Autorzy rozważali użycie szkicu tensorowego w celu zmniejszenia liczby potrzebnych zmiennych.
W 2017 r. inny artykuł zajmuje się FFT cech wejściowych, zanim zostaną one połączone za pomocą iloczynu elementarnego. To znowu odpowiada oryginalnemu szkicowi tensora.