Szkic tensora

W statystyce , uczeniu maszynowym i algorytmach szkic tensorowy jest rodzajem redukcji wymiarowości , która jest szczególnie wydajna w przypadku zastosowania do wektorów o strukturze tensorowej . Taki szkic może być użyty do przyspieszenia jawnych metod jądra , łączenia dwuliniowego w sieciach neuronowych i jest kamieniem węgielnym w wielu algorytmach numerycznej algebry liniowej.

Definicja matematyczna

Z matematycznego punktu widzenia macierz redukcji wymiarów lub macierz szkicowania jest macierzą, gdzie , takie jak że dla dowolnego wektora

z dużym prawdopodobieństwem. Innymi słowy, wektorów z małym błędem.

dodatkową właściwość, że jeśli R takie, że , transformacja można obliczyć wydajniej. Tutaj oznacza produkt Kroneckera , a nie produkt zewnętrzny , chociaż oba są powiązane spłaszczeniem .

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.

Losowe projekcje tensorowe

Produkt podziału twarzy jest zdefiniowany jako iloczyn tensorowy rzędów (został zaproponowany przez V. Slyusara w 1996 r. Do zastosowań w radarach i antenach cyfrowych ). Bardziej bezpośrednio, niech i i będą dwiema macierzami. Następnie iloczyn rozszczepiający twarz do Powodem, dla którego ten produkt jest użyteczny, jest następująca tożsamość:

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!

Okazuje się, że zależność tę można postrzegać w kategoriach iloczynu dzielącego twarz jako

, gdzie jest transformacji .

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.

Można udowodnić, że o czynnik .

Szybkie konstrukcje

Szybka transformata Johnsona-Lindenstraussa jest macierzą redukcji wymiarowości

macierz obliczenie iloczynu wektora zajmuje . Transformacja Fast Johnson Lindenstrauss (FJLT) została wprowadzona przez Ailona i Chazelle w 2006 roku.

Wersja tej metody przyjmuje gdzie

  1. macierzą ukośną każdy jest _

Mnożenie obliczyć _

  1. to macierz Hadamarda , która umożliwia mnożenie macierzy i wektorów w czasie
  2. 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:

gdzie to punkty danych, to etykieta albo -1, klasy . Funkcja . Typowymi przykładami są radialne jądro funkcji bazowej , i jądra wielomianowe, takie jak .

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.

Dalsza lektura