To, co dla użytkownika komputera pozostaje niewidoczne, dla matematyków jest polem bardzo intensywnych badań. Dr hab. Joachim Jelisiejew z Wydziału Matematyki, Informatyki i Mechaniki UW wraz ze współpracownikami bada strukturę tensorów i szuka sposobów na rozpoznawanie tych, które można przybliżyć za pomocą możliwie małej liczby prostych elementów.
Zanim przejedziemy do tensorów, zacznijmy jednak od macierzy. Najprościej wyobrazić ją sobie jako planszę sudoku: prostokątną tabelę z liczbami ułożonymi w wiersze i kolumny. Oczywiście w macierzy nie obowiązują reguły sudoku, a same liczby mogą oznaczać bardzo różne rzeczy.
Tensor jest jej bardziej rozbudowanym krewnym. Pozwala uporządkować liczby nie tylko w wierszach i kolumnach, ale także w kolejnych „kierunkach”. Można więc wyobrazić go sobie jak stos wielu takich tabel ustawionych jedna za drugą albo kostkę wypełnioną liczbami.
Takie uporządkowanie pozwala zapisywać coraz bardziej złożone informacje. Tensor może na przykład opisywać kolorowy obraz: liczby określają położenie każdego piksela oraz to, ile ma w sobie czerwieni, zieleni i niebieskiego. Jeśli dodamy jeszcze jeden wymiar, możemy zapisać kolejne obrazy, a więc na przykład następujące po sobie klatki filmu.
I tu wracamy do modeli językowych. Komputer nie widzi przecież słów tak jak człowiek. Tekst zostaje podzielony na mniejsze fragmenty, nazywane tokenami, a te są przedstawiane za pomocą liczb.
Podczas treningu model nie „wkuwa na pamięć” ogromnych ilości tekstu. Zamiast tego uczy się występujących w nim zależności, dostrajając miliardy liczb, czyli swoich parametrów.
Kiedy później np. ChatGPT tworzy odpowiedź, na podstawie tych liczb oblicza, jakie tokeny mogą pojawić się jako następne. Żeby to zrobić, raz za razem wykonuje ogromną liczbę działań matematycznych. Jednymi z najważniejszych i najczęściej wykonywanych są operacje na macierzach.
Samo mnożenie macierzy nie brzmi szczególnie groźnie. To algorytm, którego podstaw można nauczyć nawet uczniów w szkole. Problem zaczyna się wtedy, gdy macierze mają nie kilka czy kilkanaście, lecz ogromną liczbę elementów, a podobne działania trzeba powtarzać raz za razem.
W klasycznym sposobie mnożenia dwóch kwadratowych macierzy, czyli dwóch takich „plansz sudoku”, które mają tyle samo wierszy co kolumn, właśnie n, liczba potrzebnych operacji rośnie mniej więcej jak n3.
Oznacza to, że jeśli długość boku takiej macierzy zwiększymy 10 razy, liczba potrzebnych działań wzrośnie mniej więcej 1000 razy. Przy niewielkich macierzach nie robi to wielkiego wrażenia. Przy naprawdę dużych zaczyna robić kolosalną różnicę.
Małe poprawki, kolosalne znaczenie
Taki rząd wielkości daje zwykły, klasyczny algorytm, czyli po prostu ustalony sposób wykonywania kolejnych działań potrzebnych do pomnożenia macierzy.
Matematycy od dawna próbują więc odpowiedzieć na pytanie: czy da się choć trochę zmniejszyć wykładnik 3, a tym samym ograniczyć liczbę potrzebnych obliczeń?
Pierwszy przełom nastąpił w 1969 roku, gdy Volker Strassen pokazał, że macierze można mnożyć ciut szybciej niż klasyczną metodą.
Późniejsze prace wykorzystywały coraz bardziej zaawansowane narzędzia z algebry i geometrii, w tym badanie własności tensorów. Każdy kolejny wynik pozwalał jeszcze trochę zmniejszyć liczbę operacji potrzebnych przy bardzo dużych macierzach, choć z czasem postępy stawały się coraz mniejsze.
W klasycznym algorytmie liczba operacji rośnie jak n3. Najlepsze znane metody pozwoliły zmniejszyć ten wykładnik do około n2,37.
Niewiele? Tylko pozornie. Jeśli dla zobrazowania różnicy spojrzymy wyłącznie na same wykładniki, przy macierzy 1000×1000 oznacza to około 76 razy mniej operacji, a przy macierzy milion na milion – prawie sześć tysięcy razy mniej!
W praktyce rzeczywista szybkość algorytmu zależy również od wielu innych czynników, ale te liczby dobrze pokazują, dlaczego matematycy walczą nawet o niewielkie zmniejszenie wykładnika.
Tylko jeden wymiar więcej, ale dużo, dużo trudniej
Przejście od macierzy do tensorów wygląda niewinnie, ale matematycznie bardzo komplikuje sprawę. W przypadku macierzy stosunkowo łatwo można obliczyć jej rangę, czyli w dużym uproszczeniu sprawdzić, jak bardzo jest ona złożona. Z tensorami jest znacznie gorzej.
Najłatwiej wyobrazić sobie tensor jako konstrukcję zbudowaną z prostszych matematycznych „klocków”. Jego ranga mówi, ile takich najprostszych klocków potrzeba co najmniej, żeby złożyć dany tensor dokładnie. Im niższa ranga, tym prostsza jest pod tym względem jego struktura. Dla dużych tensorów ustalenie tej liczby może być jednak niezwykle trudne.
Dr hab. Joachim Jelisiejew wraz ze współpracownikami badał jeszcze pokrewne pojęcie – rangę brzegową (border rank).
Tutaj nie pytamy już, z ilu prostych elementów trzeba zbudować tensor idealnie, lecz z ilu wystarczy go przybliżyć tak dokładnie, jak tylko chcemy.
Najprościej wyobrazić to sobie na przykładzie liczby 1. Możemy zbliżać się do niej przez 0,9, potem 0,99, 0,999 i tak dalej.
Nigdy nie musimy trafić w nią dokładnie, ale różnica może być dowolnie mała. Z tensorami działa to podobnie: nawet jeśli nie da się zbudować danego tensora dokładnie z określonej liczby prostych „klocków”, można czasem tworzyć z nich kolejne wersje coraz bardziej podobne do oryginału.
– Tensory z rangą brzegową 1 i 2 są dość trywialne. Te z rangą brzegową 3 są znane, ja zajmowałem się przypadkami 4 i 5. Warto podkreślić, że zrobienie kolejnego „oczka” jest wykładniczo trudniejsze. To nam się udało, bo przedstawiliśmy problem w terminach algebry przemiennej – tłumaczy dr hab. Joachim Jelisiejew.
Mówiąc prościej: każdy kolejny poziom oznacza ogromny wzrost liczby możliwych przypadków do zbadania. To, co dało się już opisać dla prostszych tensorów, przy randze 4, a szczególnie 5, stawało się znacznie trudniejszym problemem. Kluczem okazało się więc spojrzenie na niego z innej strony i wykorzystanie narzędzi algebry przemiennej.
Dwa spojrzenia, głębsze zrozumienie
Algebra przemienna i geometria algebraiczna to dwa różne, ale dobrze uzupełniające się sposoby patrzenia na ten sam problem. Pierwsza skupia się przede wszystkim na równaniach i zależnościach między nimi. Można powiedzieć, że zamiast oglądać figurę, matematyk bada przepis, który ją opisuje.
Geometria algebraiczna robi krok w drugą stronę: równania zamienia w geometryczne obiekty i pozwala badać ich kształt oraz wzajemne położenie.
Najprostszy przykład znamy jeszcze ze szkoły. Równanie x² + y² = 1 można potraktować po prostu jako zapis algebraiczny. Ale można też narysować wszystkie punkty, które je spełniają. Wtedy dostajemy okrąg. To właśnie podstawowa idea geometrii algebraicznej: ten sam problem można oglądać jednocześnie jako układ równań i jako obiekt geometryczny.
Podobny zabieg można zastosować do tensorów. Naukowiec z UW badał szczególne zbiory tensorów, przedstawiając je za pomocą obiektów geometrycznych.
Jednym z nich są tzw. rozmaitości siecznych. W dużym uproszczeniu r-ta rozmaitość siecznych opisuje tensory, których ranga brzegowa jest nie większa niż r.
Można tu wrócić do wcześniejszego przykładu z liczbą 1. Tak jak liczby 0,9, 0,99 czy 0,999 mogą zbliżać się do 1 coraz dokładniej, tak pewne tensory mogą być coraz lepiej przybliżane przez tensory o prostszej strukturze.
Geometria algebraiczna pozwala badać cały zbiór takich możliwych przybliżeń naraz, zamiast analizować każdy tensor osobno.
To ma znaczenie również dla teorii szybkiego mnożenia macierzy. Jeśli mnożenie macierzy opiszemy za pomocą tensora, możemy pytać, jak mało prostych tensorów wystarczy, by go coraz dokładniej przybliżać. Im lepiej rozumiemy strukturę takich obiektów, tym więcej wiemy o matematycznych możliwościach upraszczania obliczeń.
Na czym więc polegało nowe spojrzenie?
– Opiera się ono na nowym niezmienniku: algebrze centroidu. Najistotniejsze jest jednak nie tyle samo pojęcie, a nowe spojrzenie na całą teorię tensorów, które pozwala systematycznie stosować do niej narzędzia algebry przemiennej i geometrii algebraicznej. Obie te teorie są znacznie bardziej rozbudowane niż algebra liniowa i w konsekwencji stosowanie ich prowadzi do ogólniejszych, głębszych wyników, które dodatkowo można o wiele szybciej i bardziej elegancko udowodnić. Zaskakujące dla mnie samego było to, że tak podstawowa struktura nie była znaleziona i zastosowana wcześniej – tłumaczy dr hab. Joachim Jelisiejew.
Mówiąc prościej: zamiast patrzeć na tensor tylko jak na wielowymiarową tablicę liczb i mozolnie analizować opisujące go równania, badacze próbują zobaczyć także odpowiadający im obiekt geometryczny.
Trochę jak ze wspomnianym równaniem x² + y² = 1: można je liczyć i przekształcać, ale można też od razu zobaczyć, że to okrąg.
Nagroda matematyczna… a może literacka?
Dr hab. Joachim Jelisiejew został niedawno uhonorowany Nagrodą Naukową Wydziału III Polskiej Akademii Nauk im. Wacława. Jak czytamy w uzasadnieniu, nagrodę przyznano za cykl prac z geometrii algebraicznej oraz jej zastosowań w teorii motywów, teorii tensorów oraz działań grup. Wśród głównych wyników można wyróżnić: znalezienie teorii motywicznych, przykłady patologii oraz ekscesów przestrzeni moduli, a także wyniki typu „nie ma smoków” dla brzegu rozmaitości…
Brzmi jak fragment futurystycznej powieści Stanisława Lema, ale za tymi poetycko brzmiącymi określeniami kryje się ścisła matematyka. Co dokładnie oznaczają te kolejne zakamarki matematycznego świata, to już jednak temat na osobną opowieść. Najlepiej przy drugiej mocnej kawie.
