ML: Embedding слів
Вступ
Перелічимо у словнику $\mathcal{V}$ (vocabulary) розміром V_DIM = V
усі значення деякої якісної ознаки.
Наприклад, для 7 кольорів
{red, green, blue, yellow, cyan, magenta, gray} у словнику буде V = 7 слів.
Щоб нейронна мережа могла працювати з такою ознакою, її необхідно векторизувати.
Це означає, що значенням ознаки ставляться у відповідність унікальні вектори
з E_DIM = E компонентами.
Тим самим якісна ознака ніби занурюється (embedding) у речовинний векторний простір.
Кожне значення ознаки - це точка E-вимірного простору.
Координати точки-ознаки (як речовинні числа) можна відправляти на вхід нейронної мережі або будь-якої іншої моделі машинного навчання.
При невеликій кількості значень ознаки підходить one-hot кодування. У цьому способі розмірності векторів і число слів у словнику збігаються (E = V), а вектор i-го слова складається з нулів, крім i-ї позиції, у якій стоїть одиниця. One-hot кодування можна інтерпретувати як V-вимірний простір, кожна вісь якого означає наявність (1) або відсутність (0) даного значення. При цьому вектори всіх слів словника попарно ортогональні:
Vocabulary One-hot Embedding ------------------------------------------------------ 1. red [1, 0, 0, 0, 0, 0, 0] [1.0, 0.0, 0.0] 2. green [0, 1, 0, 0, 0, 0, 0] [0.0, 1.0, 0.0] 3. blue [0, 0, 1, 0, 0, 0, 0] [0.0, 0.0, 1.0] 4. yellow [0, 0, 0, 1, 0, 0, 0] [1.0, 1.0, 0.0] 5. cyan [0, 0, 0, 0, 1, 0, 0] [1.0, 0.0, 1.0] 6. magenta [0, 0, 0, 0, 0, 1, 0] [0.0, 1.0, 1.0] 7. gray [0, 0, 0, 0, 0, 0, 1] [0.2, 0.2, 0.2]
One-hot кодування іноді використовують і для слів природної мови, що має дуже великий словник.
Будь-який документ можна охарактеризувати сумою (або логічним OR) one-hot векторів
його слів. Такий вектор документа називається мішком слів (bag of words, BoW),
бо він відображає лише кількість або факт наявності (при OR) слів у документі, але не їхній порядок.
Подібну просту векторизацію документів можна використовувати, наприклад, для їхньої класифікації або пошуку.
У one-hot кодування є два недоліки: 1) при великому словнику векторне представлення ознак стає дуже громіздким, а число параметрів моделі збільшується; 2) one-hot вектори не відображають близькості різних слів словника (якщо вона існує).
Для усунення цих недоліків використовують вектори відносно невеликої розмірності з речовинними компонентами. Більшість їхніх компонент відмінні від нуля, тому це розподілене ("розмазане") представлення (distributes representation). Такий підхід називається Embedding або Word2Vec. Значення компонент векторів зазвичай визначають у процесі навчання. Передбачається, що вектори в E-вимірному просторі будуть об’єднуватися в кластери за семантичною (смисловою) близькістю слів, що спрощує навчання інших шарів моделі. Втім, вони можуть бути і задані (вище - це {R,G,B}-компоненти кольору).
Для експериментів з векторизацією слів природної мови знадобиться деякий корпус текстів. Будемо використовувати короткі історії ROC Stories, детальний опис яких можна знайти у документі NLP_ROCStories.html. Наведені приклади на бібліотеці PyTorch знаходяться в ноутбуці NN_Embedding_Learn.ipynb, для якого необхідні тексти з файлу 100KStories.csv. Трохи почищені історії можна скачати у нас на сайті
Вектори контексту
З кожним словом $w_i$ словника $\mathcal{V}$ ми хочемо пов’язати вектор $\mathbf{u}_i=\{u_{i0},...,u_{i,\text{E}-1}\}$ так, щоб семантично близькі слова мали схожі вектори. У результаті цього, наприклад, слова dog, cat, rabbit у векторному просторі повинні опинитися поруч (утворити кластер) і при цьому бути на відстані від кластера слів car, bus, train.
Семантична близькість двох слів призводить до того, що в текстах вони зустрічаються в однаковому контексті, тобто в середньому їх оточують одні й ті самі слова. Візьмемо спочатку вектори розмірністю E_DIM, яка дорівнює числу слів V_DIM у словнику (E=V). Нехай у вектора i-го слова j-та компонента пропорційна частоті $u_{ij} = P(w_i,w_j)$ спільної появи слів $w_i$ і $w_j$ в одному реченні. Близькі за змістом слова можуть і не зустрічатися в одному реченні, але вони мають аналогічний контекст і схожі вектори. Нижче червоним кольором умовно позначені високі значення $P(w_i,w_j)$. Видно, що вектори cat і dog схожі і відрізняються від векторів car і bus:
Частоти спільної появи слів у природній мові "зашумлюються" частими словами типу артикля 'the' (закон Ципфа). Щоб зменшити цей ефект, замість частоти будемо використовувати метрику pPMI (positive pointwise mutual information): $$ \mathrm{pPMI} = \max(0,\,\mathrm{PMI}),~~~~~~~~~~~~\mathrm{PMI} = \log \frac{P(w_1, w_2)}{P(w_1)P(w_2)} ~\equiv~ \log \frac{P(w_1\,|\,w_2)}{P(w_1)}. $$ Якщо слова $w_1$ і $w_2$ "незалежні", то умовна ймовірність $P(w_1\,|\,w_2)=P(w_1)$, а для спільної ймовірності $P(w_1, w_2) \,=\, P(w_1)P(w_2)$. У цьому випадку $\mathrm{PMI}=0$. Функція $\max$ у визначенні pPMI обрізає нульові значення спільних ймовірностей і можливі від’ємні значення логарифма, якщо $P(w_1\,|\,w_2) < P(w_1)$.
Наведемо один з варіантів обчислення спільної ймовірності появи двох слів у реченні за допомогою бібліотеки numpy. Завантаження списку документів docs (ROC історій) і складання словника wordID описані в документі ROC Stories.
import numpy as np
p12 = np.zeros((V_DIM, V_DIM)) # спільні ймовірності
p1 = np.zeros((V_DIM,)) # частоти слів
for d in docs: # по документах
for s in d: # по реченнях документа
ws = set(s.split()) # "словник" слів речення
for w1 in ws:
if w1 in wordID: # слово є в загальному словнику
p1[ wordID[w1]["id"] ] += 1
for w2 in ws:
if w2 in wordID:
p12[ wordID[w1]["id"], wordID[w2]["id"] ] += 1
p12 /= p12.sum() # нормуємо на одиницю
p1 /= p1.sum()
Тепер можна обчислити вектори слів за формулою pPMI:
vecs = p12 / ( p1.reshape((V_DIM,1)) @ p1.reshape((1, V_DIM)) ) vecs[vecs <= 0] = 1 # нулі або мінус під логарифмом vecs = np.log(vecs) vecs[vecs <= 0] = 0 # max у pPMIЧас отримання компонент векторів для корпусу 100k ROCStories на Python займає близько хвилини (при обчисленнях на CPU Intel i7-7500U 2.7GHz, 16Gb). Наведемо приклади кількох компонент чотирьох векторів (опускаючи нулі):
paws vet wheel driver motion white very we can
bark collar claw gas stops red the after not to
------------------------------------------------------------------------------------------------
cat 1.1 4.0 2.6 2.9 2.5 1.6 0.4 0.3 0.1
dog 3.7 2.9 3.3 3.0 0.2 1.1 0.4 0.1 0.1
car 1.5 2.2 2.0 1.5 1.3 0.3 0.1 0.1
bus 3.8 2.7 2.6 0.8 0.5 0.4 0.3
say 2.7 0.5 0.5 0.4 1.1 1.3 0.8
ask 1.7 2.1 0.2 1.1 1.1
get 0.9 0.8 1.0 0.9 1.2 0.3 0.7 0.7 1.0
Звернімо увагу на малі значення pPMI з високочастотними словами в останніх колонках таблиці. Очевидно, що ці слова не мають прямого смислового зв’язку зі словами cat, dog, cat, bus.
Зниження розмірності
Хоча компоненти векторів слів тепер відображають подібність слів, їхня розмірність так само велика, як і при one-hot кодуванні. Для зниження розмірності ембедингу скористаємося методом головних компонент (PCA: principal component analysis):
from sklearn.decomposition import PCA pca = PCA() res = pca.fit_transform(vecs)Обчислення головних компонент для матриці (10000, 10000) займає близько 7 хвилин. Перші 50 власних значень коваріаційної матриці (pca.singular_values_) швидко зменшуються, а потім зменшення до нуля (при i=V) стає практично лінійним:
Обмежимося далі розмірністю векторного простору E_DIM = E = 100:
vecs = res[:, : E_DIM] # перші 100 колонок vecs = (vec-vec.mean(axis=0))/(res.std(axis=0) * np.sqrt(E_DIM) )# вирівнюємо розкидФінальна нормалізація компонент (віднімання середнього і ділення на розкид) переносить "центр хмари точок" на початок координат, що покращує роботу косинусної міри відстані (див. нижче). Ділення на корінь від розмірності ембедингу E_DIM масштабує довжини векторів у середньому до одиничного значення.
Міри близькості
Міри близькості двох векторів $\mathbf{u}$, $\mathbf{v}$ у багатовимірному просторі можна вибрати різним чином: $$ \begin{array}{llclcl} \text{евклідова відстань:} & \text{dist}_1(\mathbf{u},\mathbf{v}) &=& \sqrt{(\mathbf{u}-\mathbf{v})^2}\\[2mm] \text{косинусна відстань:} & \text{dist}_2(\mathbf{u},\mathbf{v}) &=& 1-\cos(\mathbf{u},\mathbf{v})&=& 1-\displaystyle \frac{\mathbf{u}\mathbf{v}}{|\mathbf{u}|\cdot|\mathbf{v}|} \end{array} $$ Після скорочення розмірності частіше використовують косинусну відстань. За допомогою косинусної відстані знайдемо найближчих сусідів до деяких слів (див. модуль my_embedding.py):
- cat: kitten (0.17), dog (0.18), puppy (0.25), kittens (0.32), stray (0.33), pet (0.33), poodle (0.34), pup (0.36), chihuahua (0.36), shelter (0.37), meowed (0.37), cats (0.38), kitty (0.39)
- car: truck (0.23), vehicle (0.28), driving (0.30), cars (0.30), driver (0.32), road (0.33), intersection (0.33), interstate (0.33), tire (0.34), brakes (0.34), semi (0.34), towed (0.34), sped (0.35), highway (0.36), rear-ended (0.38), ford (0.39), van (0.39), swerved (0.39), wrecked (0.40), oncoming (0.40), drivers (0.41), parked (0.41)
- apple: orchard (0.30), peach (0.31), apples (0.32), blueberry (0.34), pie (0.34), fruit (0.37), cherry (0.37), banana (0.42), oranges (0.43), bakes (0.46), peaches (0.46), bake (0.48), dessert (0.48), ripe (0.48), fresh (0.49), smoothie (0.49), picking (0.49), grapes (0.49), pumpkin (0.49), pies (0.49), muffins (0.51), bananas (0.51), lemon (0.52), cherries (0.53)
- gin: vodka (0.27), martini (0.32), drink (0.32), drank (0.34), drinking (0.38), drinks (0.40), wine (0.40), iced (0.41), sipping (0.41), champagne (0.43), beer (0.43), bartender (0.45), whiskey (0.46), beers (0.47), alcoholic (0.48), espresso (0.49), decaf (0.49), sipped (0.49), soda (0.50), beverage (0.50), tea (0.50), sip (0.50), glass (0.51), coffee (0.51)
- monday: tuesday (0.39), saturday (0.47), early (0.48), wednesday (0.48), friday (0.50), overslept (0.50), thursday (0.51), morning (0.52), late (0.52), noon (0.54), sunday (0.55), meeting (0.55), today (0.55), pm (0.57), scheduled (0.57), :30 (0.58), appointment (0.59), 11 (0.60), lecture (0.61), postponed (0.62), woke (0.62), 8 (0.62), arrive (0.62), april (0.63)
- red: blue (0.23), yellow (0.29), bright (0.31), stripes (0.34), white (0.37), pale (0.38), purple (0.42), brown (0.42), pink (0.43), flashing (0.43), green (0.43), colored (0.44), resulting (0.47), black (0.47), puffy (0.48), orange (0.50), dyed (0.51), streaks (0.51), color (0.52), dye (0.53), eyes (0.53), stains (0.54), ink (0.54), stained (0.55)
- small: large (0.39), a (0.46), big (0.46), suburban (0.52), huge (0.54), tiny (0.55), near (0.58), breeder (0.59), stone (0.59), sized (0.60), cardboard (0.61), own (0.61), inheritance (0.62), corgi (0.64), larger (0.64), little (0.64), lived (0.65), isolated (0.66)
- say: [seem (0.43), tell (0.43), know (0.46), anything (0.46), understand (0.48), what (0.48), happen (0.49), exist (0.49), matter (0.50), psychic (0.50), saying (0.50), don't (0.51), anybody (0.51), hello (0.51), why (0.52)', won't (0.52), god (0.52), cruel (0.54), hi (0.54), respond (0.54), says (0.55), ? (0.55), sorry (0.56), yes (0.56)
Для порівняння косинусна і евклідова відстань між цими словами:
dist_cos dist_len
cat car apple gin monday red small say cat car apple gin monday red small say
cat 0.94 1.01 0.90 1.07 1.02 0.84 1.01 2.62 2.62 1.98 2.27 3.06 2.46 2.32
car 0.94 0.97 1.07 1.06 0.87 1.02 1.02 2.62 2.57 2.10 2.26 2.83 2.73 2.33
apple 1.01 0.97 0.99 0.94 0.84 0.94 1.03 2.62 2.57 1.90 2.02 2.70 2.51 2.22
gin 0.90 1.07 0.99 1.16 0.90 1.01 1.09 1.98 2.10 1.90 1.40 2.38 2.03 1.53
monday 1.07 1.06 0.94 1.16 0.89 1.09 1.15 2.27 2.26 2.02 1.40 2.48 2.27 1.81
red 1.02 0.87 0.84 0.90 0.89 0.98 1.05 3.06 2.83 2.70 2.38 2.48 2.98 2.73
small 0.84 1.02 0.94 1.01 1.09 0.98 1.04 2.46 2.73 2.51 2.03 2.27 2.98 2.33
say 1.01 1.02 1.03 1.09 1.15 1.05 1.04 2.32 2.33 2.22 1.53 1.81 2.73 2.33
Звернімо увагу, що косинусна відстань між словами з "різних кластерів" порядку одиниці,
що говорить про перпендикулярність цих векторів.
Порівняно з підходами, заснованими на нейронних мережах, векторизація за допомогою PCA є досить швидким методом і при відносно невеликих словниках може слугувати дуже непоганим першим наближенням.
Властивості векторного простору
Побудуємо гістограми розподілу довжин векторів окремо для частих слів (перші 1000), рідкісних слів і всіх разом. Часті слова мають довші вектори, що типово для всіх методів ембедингу:
Семантичні напрямки
Обчислимо вектор різниці між векторами двох слів $\mathbf{u}_1-\mathbf{u}_2$. Наведемо його довжину len і матрицю косинусних відстаней між такими векторами (якщо вони менші за 1, то кут між векторами менший за 90°):
sex pm len 1 2 3 4 5 6 7
1. [he she ] 23352 - 19702| 0.63| 0.56 0.60 0.44 0.68 0.71 0.84
2. [man woman ] 1020 - 311| 1.35| 0.56 0.57 0.74 0.84 0.91 0.75
3. [boy girl ] 378 - 551| 1.18| 0.60 0.57 0.78 0.85 0.77 0.76
4. [father mother ] 319 - 744| 1.43| 0.44 0.74 0.78 0.64 1.06 1.13
5. [uncle aunt ] 68 - 76| 1.34| 0.68 0.84 0.85 0.64 0.95 1.10
6. [nephew niece ] 38 - 65| 1.18| 0.71 0.91 0.77 1.06 0.95 0.87
7. [king queen ] 29 - 17| 1.00| 0.84 0.75 0.76 1.13 1.10 0.87
Помітно гірше вісь віку:
age pm len 1 2 3 4 5
1. [old young ] 778 - 175| 2.23| 0.99 0.93 1.05 1.09
2. [man boy ] 1020 - 378| 1.81| 0.99 0.32 0.94 0.92
3. [woman girl ] 311 - 551| 1.58| 0.93 0.32 0.97 0.94
4. [grandpa dad ] 56 - 568| 1.54| 1.05 0.94 0.97 0.66
5. [grandmother mother ] 120 - 744| 1.45| 1.09 0.92 0.94 0.66
Трохи математики $^*$
Нагадаємо, що метод PCA в $n$-вимірному просторі шукає
"найближчу" до навчальних точок $m$-вимірну площину,
для якої середньоквадратичне відхилення відстаней множини точок мінімальне.
Координати $N$ точок у $n$-вимірному просторі визначаються матрицею $\mathbf{X}$ форми $(N,n)$.
Нехай з координат відняті їхні середні значення по всіх точках.
Тоді коваріаційна матриця дорівнює $\mathbf{C} = \mathbf{X}^\top\mathbf{X}/(N-1)$.
Розв’язок PCA-задачі зводиться до знаходження відсортованих у порядку спадання $\lambda_1 \ge ... \ge \lambda_n$ власних значень $\lambda_\alpha$ коваріаційної матриці: $\mathbf{C}\,\mathbf{v}^{(\alpha)}=\lambda_\alpha\,\mathbf{v}^{(\alpha)}.$ Нехай $\mathbf{L}=\text{diag}(\lambda_1,...\lambda_n)$ - діагональна матриця. Тоді $\mathbf{C}=\mathbf{V}\mathbf{L}\mathbf{V}^\top$, де в кожній колонці матриці $\mathbf{V}_{i\alpha}=v^{(\alpha)}_i$ знаходяться компоненти власних векторів $\mathbf{v}^{(\alpha)}.$ Перші $m$ колонок матриці $\mathbf{X}\mathbf{V}$ форми $(N,n)$ будуть координатами проекцій точок $\mathbf{X}$ на $m$-вимірну площину.
При знаходженні $\mathbf{C}$ перемноження великих матриць $\mathbf{X}$ форми $(N,n)$ призводить до втрати точності. Тому іноді ефективніше використовувати SVD-розклад (singular value decomposition):
де $\mathbf{S}$ - діагональна матриця $(N,n)$ з сингулярними числами $s_i$ на діагоналі, а $\mathbf{U}, \mathbf{V}$ - ортогональні матриці (колонки $\mathbf{U}$ - власні вектори матриці $\mathbf{X}\mathbf{X}^\top$, а колонки $\mathbf{V}$ - власні вектори $\mathbf{X}^\top\mathbf{X}$). Зрозуміло, що
$$ \mathbf{C} = \frac{\mathbf{X}\mathbf{X}^\top}{N-1} = \frac{\mathbf{V}\mathbf{S}\mathbf{U}^\top\,\mathbf{U}\mathbf{S}\mathbf{V}^\top} {N-1} =\mathbf{V}\frac{\mathbf{S}^2}{N-1}\mathbf{V}^\top. $$Таким чином, власні значення коваріаційної матриці дорівнюють $\lambda_i=s^2_i/(N-1)$, а головні компоненти даються добутком $\mathbf{X}\mathbf{V}=\mathbf{U}\mathbf{S}\mathbf{V}^\top\mathbf{V}=\mathbf{U}\,\mathbf{S}$. На numpy PCA за допомогою SVD робиться таким чином:
U, S, V = np.linalg.svd(X - X.mean(axis=0)) vecs = U[:, : m] @ np.diag(S[ : m])
Global Vectors (GloVe)
При дуже великих словниках зниження розмірності методом PCA або SVD може бути утрудненим. У цьому випадку зазвичай використовують нейронні мережі, які одразу працюють з векторними просторами невеликих вимірів (див. наступний документ). У роботі Pennington J. et.al. (2014) було запропоновано проміжний підхід, названий "Global Vectors for Word Representation" або скорочено GloVe.
У цьому підході спочатку обчислюються логарифми ймовірностей $P_{ij}$ спільної зустрічальності слів $w_i$ і $w_j$ у тексті всередині ковзного вікна з 10 слів. Підбираними параметрами моделі є компоненти E-вимірних векторів $\mathbf{u}_i$ слів і параметри зміщення $b_i$. У процесі навчання (підбору $\mathbf{u}_i$ і $b_i$) мінімізується такий функціонал помилки:
$$ \text{Loss} = \sum_{ij} f(N_{ij})\,\bigr(\mathbf{u}_i\mathbf{u}'_j + b_i + b'_j - \log P_{ij}\bigr)^2 = \min_{\mathbf{u}_i,\mathbf{u}'_j\,b_i,b'_j} $$ Ваги $f(N_{ij})$ пропорційні числу появи $N_{ij}$ пари у вікні. Ці ваги обрізаються для надто високочастотних слів. Автори вибрали таку функцію, у якій $x_\text{max}=100$ незалежно (?) від довжини тексту.
$$
f(x) =
\left\{
\begin{array}{ll}
(x/x_{\text{max}})^{3/4} & \text{if}~ x < x_{\text{max}}\\
1 & \text{otherwise}
\end{array}
\right.
$$
У скалярному добутку $\mathbf{u}_i\mathbf{u}'_j$ використовувалися різні вектори $\mathbf{u}$ і $\mathbf{u}'$, а фінальний ембединг дорівнював $\mathbf{u}+\mathbf{u}'$. З точки зору авторів, це допомагало перенавчанню (хоча $P_{ij}=P_{ji}$, але початкові випадкові значення компонент $\mathbf{u}$ і $\mathbf{u}'$ були різними). Параметри "зміщень" $b_i$, $b'_j$ можна інтерпретувати як навчані ймовірності в знаменнику PMI, тобто мінімізуючи помилку ми прагнемо отримати щось типу $\mathbf{u}_i\mathbf{u}'_j = \log P_{ij}/P_i P_j$.
Векторизацію було проведено на великих корпусах текстів:
We trained our model on five corpora of varying sizes: a 2010 Wikipedia dump with 1 billion tokens; a 2014 Wikipedia dump with 1.6 billion tokens; Gigaword 5 which has 4.3 billion tokens; the combination Gigaword5 + Wikipedia2014, which has 6 billion tokens; and on 42 billion tokens of web data, from Common Crawl
У відкритому доступі знаходяться набори векторів з розмірністю від 50 до 300 і словником 400k. Перед побудовою словника автори "tokenize and lowercase each corpus with the Stanford tokenizer". Доброю ідеєю при використанні GloVe буде також використання Stanford tokenizer, бо він робить "непробільне" розбиття: can't → [ca, n't]; she's → [she, 's] і т.п.Аналіз векторного простору GloVe можна знайти в цьому документі.
Проблеми ембедингу
Технологія ембедингу - одне з найчудовіших винаходів останнього десятиліття. Однак з нею пов’язаний також ряд проблем.
✑ Для отримання надійних контекстних векторів рідкісних слів потрібен дуже великий корпус текстів. Однак у великому корпусі може відбуватися перекіс у семантичних значеннях слів порівняно з їхніми характерними повсякденними значеннями. Наприклад, при векторизації GloVe для слова apple отримуємо таких найближчих сусідів: microsoft(.26), ibm (.32), intel(.32), software(.32), dell (.33). У той самий час суттєво менший корпус ROC Stories видає більш "повсякденних сусідів" для apple.
✑ Простий ембединг не враховує семантичної і синтаксичної неоднозначності. Зазвичай передбачається, що семантична неоднозначність знімається після проходження вихідних векторів слів через кілька шарів нейронної мережі, у яких аналізується контекст усього речення (архітектури RNN або Attention). Наприклад, загальний контекст речень "Remove first row of the table." і "Put an apple on the table" дозволяє в кожному випадку уточнити семантичне значення слова table.
✑ Оскільки слова у векторному просторі є точками, а не протяжними областями, ембединг не відображає ієрархічної природи смислів: предмет - інструмент - молоток.
