fastText
Jak działa
1) Każde słowo w jest rozszerzane do reprezentacji subword: dodawane są znaczniki granic (np. <where> → <wh, whe, her, ere, re>), a następnie wyznaczany jest worek n-gramów znakowych G_w o długościach od minn do maxn (typowo 3–6) plus samo słowo. 2) Każdemu n-gramowi g przypisywany jest wektor z_g; wektor słowa to v_w = Σ_{g∈G_w} z_g. 3) Trening jak w word2vec — skip-gram lub CBOW z negative sampling — ale gradient propagowany jest na wszystkie n-gramy współtworzące słowo. 4) Aby ograniczyć liczbę parametrów, n-gramy mapowane są do stałej liczby kubełków za pomocą hashing trick (Fowler-Noll-Vo, typowo 2M kubełków). 5) Dla słów OOV w czasie inferencji wektor obliczany jest z n-gramów słowa, nawet jeśli słowo nie wystąpiło w korpusie. 6) W trybie klasyfikacji tekstu (osobny model) zdania reprezentowane są jako średnia wektorów słów+n-gramów, a klasyfikator liniowy z hierarchicznym softmaxem oblicza prawdopodobieństwa klas — co umożliwia trening na milionach przykładów w minuty.
Rozwiązany problem
Word2vec i GloVe uczą jednego wektora na słowo z zamkniętego słownika — słowa spoza słownika (OOV: rzadkie terminy, błędy ortograficzne, neologizmy, formy fleksyjne w językach takich jak polski, fiński czy turecki) nie mają reprezentacji. Dodatkowo te modele ignorują wewnętrzną strukturę morfologiczną słów: „running” i „runner” są dla nich niezależnymi tokenami. fastText rozwiązuje oba problemy poprzez kompozycję wektorów subword.
Komponenty
Zbiór n-gramów znakowych słowa o długościach minn..maxn, plus znaczniki granic < i >. Dla minn=3, maxn=6 słowo „where” generuje: <wh, whe, her, ere, re>, <whe, where, …, <where>.
Oficjalna
Trenowalne wektory dla każdego n-gramu (po hashingu do kubełka). Wektor słowa to suma v_w = Σ z_g po wszystkich g w G_w.
Liczba unikalnych n-gramów rośnie kombinatorycznie z rozmiarem korpusu. fastText hashuje każdy n-gram funkcją Fowler-Noll-Vo modulo bucket (typowo 2M), współdzieląc wektory między kolidujące n-gramy.
Oficjalna
Funkcja straty dziedziczona z word2vec — przewidywanie słów kontekstu (skip-gram) lub słowa centralnego z kontekstu (CBOW) z negative sampling jako estymatorem softmaxu.
Oficjalna
W trybie klasyfikacji tekstu warstwa wyjściowa to drzewo Huffmana nad klasami, redukujące koszt softmax z O(K) do O(log K), gdzie K to liczba klas. Krytyczne przy K rzędu setek tysięcy.
Oficjalna
Implementacja
Hashing trick mapuje n-gramy do skończonej liczby kubełków (domyślnie 2M). Przy bardzo dużym słowniku różne n-gramy współdzielą wektory, co może obniżać jakość embeddingów dla rzadkich subwordów.
Domyślne 3–6 znaków jest dobre dla angielskiego. Dla języków o długich morfemach (niemiecki, fiński) sensowniejsze są dłuższe n-gramy; dla języków logograficznych (chiński, japoński) podejście znakowe wymaga zupełnie innych ustawień lub segmentacji.
Tak jak word2vec i GloVe, fastText daje jeden wektor na słowo. Polysemia nie jest rozróżniana.
Pretrenowane wektory FAIR zajmują kilka GB na język. Quantization (`fasttext quantize`) może je skompresować do MB-rzędu, ale z utratą jakości.
Ewolucja
Mikolov et al. publikują skip-gram i CBOW. fastText przejmuje te cele uczenia, ale stosuje je do n-gramów znakowych zamiast całych słów.
arXiv:1607.04606 (lipiec 2016) — Bojanowski, Grave, Joulin, Mikolov wprowadzają model subword. Równolegle ukazuje się arXiv:1607.01759 — klasyfikator tekstowy fastText.
Wersja embeddingowa ukazuje się w TACL 2017, klasyfikator w EACL 2017 („Bag of Tricks for Efficient Text Classification”).
FAIR udostępnia pretrenowane wektory 300-wymiarowe na Common Crawl + Wikipedia dla 157 języków — do dziś standard baseline dla wielu języków o niskich zasobach.
ELMo i BERT wprowadzają kontekstowe reprezentacje słów; fastText pozostaje silnym baseline'em w warunkach niskich zasobów obliczeniowych i dla języków o ubogiej infrastrukturze.
Hiperparametry (konfigurowalne osie)
Najkrótszy n-gram znakowy uwzględniany w worku G_w. Domyślnie 3.
Najdłuższy n-gram znakowy. Domyślnie 6. Ustawienie maxn=0 wyłącza subword units i sprowadza fastText do word2vec.
Wymiarowość wektorów słów i n-gramów.
Rozmiar tablicy kubełków dla n-gramów. Większy = mniej kolizji, więcej pamięci. Domyślnie 2 000 000.
Liczba słów po lewej i prawej brana pod uwagę przy budowie kontekstu (skip-gram/CBOW). Domyślnie 5.
Liczba przejść po korpusie. Domyślnie 5.
Krok SGD. Domyślnie 0.05 dla skip-gram/CBOW, 0.1 dla supervised.
Liczba próbek negatywnych w negative sampling. Domyślnie 5.
Złożoność obliczeniowa
Złożoność czasowa: O(T · |G_w| · k · d). Złożoność przestrzenna: O((|V| + bucket) · d).
Wąskie gardło obliczeniowe
Każda aktualizacja gradientu propaguje sygnał na wszystkie n-gramy słowa (typowo 10–20). To czyni fastText wolniejszym od word2vec na tym samym korpusie, ale nadal o rząd wielkości szybszym niż modele neuronowe.
Paradygmat wykonania
Statyczne embeddingi (jeden wektor na słowo, niezależny od kontekstu zdania), kompozycyjne na poziomie subword. Brak mechanizmu uwagi ani rekurencji.
Równoległość
Trening wielowątkowy w stylu Hogwild! — asynchroniczne aktualizacje SGD bez locków na współdzielonych parametrach. Skaluje się dobrze do kilkudziesięciu rdzeni CPU.
Wymagania sprzętowe
Implementacja referencyjna w C++ jest CPU-only, wielowątkowa (Hogwild!), zoptymalizowana pod nowoczesne CPU. fastText osiąga przepustowość setek tysięcy słów/sekundę na rdzeń.
Inferencja (lookup wektora) jest trywialna i działa wszędzie. Istnieją porty na GPU w PyTorch/TensorFlow, ale rzadko są szybsze niż referencyjny C++.