ML: Обчислювальний граф
Вступ
Машинне навчання зазвичай зводиться до мінімізації скалярної функції,
яка залежить від безлічі змінних.
Найпростішим прикладом є лінійна модель
$\mathbf{y} = \mathbf{x}\cdot\mathbf{w} + \mathbf{b}$
з параметрами $\mathbf{w}$ (матриця) і $\mathbf{b}$ (вектор).
За набором навчальних прикладів $\{\hat{\mathbf{x}},\hat{\mathbf{y}}\}$
обчислюється похибка навчання $L$. Для mse-похибки (mean squared error)
вона дорівнює середньому значенню квадрата різниці навчальних значень $\hat{\mathbf{y}}$
і виходів моделі $\mathbf{y}$:
Похибка моделі залежить від її параметрів $L=L(\mathbf{w},\mathbf{b})$. Навчання моделі означає пошук значень параметрів, за яких похибка досягає свого мінімуму: $\mathbf{w},\,\mathbf{b} = \text{argmin}\,L(\mathbf{w},\,\mathbf{b})$. Якщо параметрів дуже багато, найбільш ефективний градієнтний метод та різні його модифікації. Для складної моделі аналітично обчислити градієнт (похідні за параметрами) непросто. Зручніше подати модель у вигляді обчислювального графа (computational graph). Граф має топологію дерева, коренем якого є шукана величина (похибка $L$), а вузли виконують елементарні обчислення. Якщо похідні в кожному вузлі відомі, то можна знайти й градієнт похибки за параметрами моделі, які знаходяться в листках дерева. Подібний підхід лежить в основі всіх сучасних фреймворків машинного навчання.
Загальна постановка задачі
Нехай модель задана функцією $\mathbf{y}=f(\mathbf{x},\,\mathbf{p})$,
де $\mathbf{x}$ - вектор ознак об'єкта,
а $\mathbf{p}$ - вектор параметрів.
Крім цього, є $N$ навчальних прикладів
$\{\hat{\mathbf{x}},\,\hat{\mathbf{y}}\}=(\hat{\mathbf{x}}^{(1)},\,\hat{\mathbf{y}}^{(1)}),\,...,\,(\hat{\mathbf{x}}^{(N)},\,\hat{\mathbf{y}}^{(N)})$,
які позначаються дашком.
Параметри $\mathbf{p}$ моделі підбираються так, щоб мінімізувати середню похибку $L$ на один приклад:
$$
L ~=~ L(\mathbf{p})~=~ \frac{1}{N}\sum^N_{i=1} L(\hat{\mathbf{y}}^{(i)},\,\mathbf{y}^{(i)}),~~~~~~~~~~~
\mathbf{y}^{(i)} = f(\hat{\mathbf{x}}^{(i)},\mathbf{p}).
$$
Щоб знайти мінімум $L$, необхідно зсувати вектор параметрів у напрямку, протилежному до градієнта (частинних похідних)
$L$ за $\mathbf{p}$. Величина зсуву визначається скалярним гіперпараметром $\lambda$ (швидкість навчання):
Обчислення проводяться у два етапи. Спочатку при прямому проході (зліва направо)
обчислюється похибка $L$ за заданих $\hat{\mathbf{x}}$, $\hat{\mathbf{y}}$ і $\mathbf{p}$.
При цьому певних значень набувають усі вузли обчислювального графа.
Потім запускається процедура зворотного проходу.
Початковий градієнт $g$ у скалярному вузлі похибки $L$ є скаляром.
Проходячи через вузли графа від похибки справа наліво, він перетворюється на вектор $\mathbf{g}$ (у загальному випадку на тензор).
Зміни $\mathbf{g}$ у кожному вузлі відбуваються таким чином, що,
коли він "добирається" до параметрів $\mathbf{p}$,
то виявляється рівним частинним похідним: $\mathbf{g}^{(\mathbf{p})}=\partial L/\partial\mathbf{p}$.
Прямий і зворотний проходи
Розглянемо як простий приклад функцію $z=f(x,y)=x\cdot x + \sin(2 y)$ двох скалярних змінних $x$ і $y$. Нехай $x=4$ і $y=3.14159$. Ці числа присвоюються листовим вузлам $x,y$ і потім поширюються по обчислювальному графу зліва направо. Так, у вузол множення входять дві стрілки кожного аргументу операції. У першому такому вузлі вони "несуть" однакові значення $4$, які, перемножуючись, дають на виході вузла число $16$ (зелений колір). У результаті кожен вузол, включно з фінальним ($z=16$), набуває певного значення:
$$ z = x\cdot x + \sin(2\cdot y) $$
Після прямого проходу по графу, запускається зворотне (backward) поширення обчислення похідних. Нижче на малюнку з кореневого вузла $z$ виходить число $g_z$ (його вважають рівним $1$). Воно рухається по графу до листових вузлів $x,y$. Проходячи через кожен вузол, ця величина певним чином змінюється:
$$ \begin{array}{lcl} g_x = \frac{\displaystyle\partial z}{\displaystyle\partial x} &=& 2\cdot x,\\[4mm] g_y = \frac{\displaystyle\partial z}{\displaystyle\partial y} &=& 2\,\cos(2\cdot y) \end{array} $$
Необхідно так визначити правила цих змін, щоб величини $g_x, g_y$, що входять у листові вузли $x,y$, виявилися частинними похідними $z$ за $x,y$.
Спойлер
У цьому документі зустрічається багато громіздких формул. Щоб не загубитися в них,
перелічимо спершу основні правила зворотного поширення:
- Градієнт $g^A$, що входить у будь-який вузол $A$, має сенс похідної цільової величини (кореня дерева) за значенням у цьому вузлі: $g^A = \partial L/\partial A$.
- Тензорна розмірність градієнта, що входить у вузол,
збігається з розмірністю
тензора, який отримує цей вузол на своєму виході.
- Через вузли змінних градієнт проходить без змін, а у вузли констант "не заходить".
- Початковий градієнт, що входить і виходить з кореня дерева $L$
дорівнює одиниці,
оскільки за визначенням це: $g=\partial L/\partial L =1$. - Пройшовши через вузол, градієнт розщеплюється по всіх ребрах, що входять у вузол, і множиться на похідні між вузлами, які з'єднує ребро (нижче лівий малюнок).
- Якщо у вузол входить кілька градієнтів, то вони додаються (нижче правий малюнок), що є наслідком правила обчислення похідної складеної функції (формула під малюнком).
$$
g^B ~=~ \frac{\partial L}{\partial B} ~=~ \frac{\partial L}{\partial A}\,\frac{\partial A}{\partial B} ~=~ g^A\,\frac{\partial A}{\partial B},
$$
$$
g^C ~=~ \frac{\partial L}{\partial C} ~=~
\frac{\partial L}{\partial A}\,\frac{\partial A}{\partial C}
+
\frac{\partial L}{\partial B}\,\frac{\partial B}{\partial C}
~=~ g^A\,\frac{\partial A}{\partial C} + g^B\,\frac{\partial A}{\partial B}.
$$
Похідні для скалярів
Розглянемо спочатку скалярні функції однієї $f(x)$ і двох $f(x,y)$ змінних. У вузли, які їх обчислюють, входить одне і два ребра відповідно (аргументи функції). Нехай при зворотному поширенні у вузол функції справа наліво потрапляє деяке число $g$. Вимагатимемо, щоб на виході воно змінювалося таким чином:
(def1)
Проходячи через вузол, який обчислює $f(x)$, величина $g$ множиться на похідну функції $f'(x)$.
Аналітичний вираз для $f'(x)$ відомий, оскільки припускається, що функція вузла обчислювального графа
досить проста.
Числові значення $f(x)$ і $f'(x)$ залежать від значення аргументу $x$,
відомого в результаті прямого проходу по графу (зліва направо).
Аналогічна ситуація для функції двох змінних.
Якщо граф складається тільки з цих вузлів, то при початковому градієнті $g=1$ ми отримаємо правильні вирази для похідних, що входять у листові вузли $x,y$.
Застосуємо ці визначення до функції синуса та операцій додавання і множення:
Таким чином, операція додавання не змінює градієнт $g$, що проходить через неї, а розщеплює його на дві однакові величини. Проходячи через вузол множення, градієнт змінюється, множачись на "інший" аргумент.
Тепер неважко записати поширення похідних для функції $z=x*x+\sin(2*y)$:
де враховано, що $\cos(2\pi)=1$. Таким чином, у вузол $y$ входить двійка ($\partial z/\partial y = 2$), а у вузол $x$ входить двічі четвірка, тобто $\partial z/\partial x = 8$.
Наведемо приклад обчислення цих градієнтів на PyTorch:
from torch import tensor, sin x, y = tensor(4., requires_grad=True), tensor(3.14159265, requires_grad=True) z = x*x + sin(2*y) # граф з коренем: tensor(16., grad_fn=<AddBackward0>) z.backward() # запускаємо обчислення градієнтів (зворотний прохід) print(x.grad, y.grad) # tensor(8.) tensor(2.)У цьому коді на Python вводяться два тензори $x,y$ нульової розмірності (скаляри). Властивість requires_grad означає, що ці тензори будуть листками дерева обчислення. У результаті запису виразу для $z$ (корінь), це дерево безпосередньо будується і одночасно з цим запускається прямий прохід (обчислюється значення $z$). Виклик методу backward ініціює зворотний прохід, у результаті якого у $x,y$ з'являється властивість grad, у якій знаходяться значення похідних $\partial z/\partial x$ і $\partial z/\partial y$.
Граф для складених функцій
Розглянемо як приклад зворотне поширення для складених функцій. Нижче зліва $z$ дорівнює функції $A$, яка залежить від функції $B(x)$. Похідна $z$ за $x$ береться як похідна складеної функції (формула під малюнком). До цього ж результату ми прийдемо, аналізуючи зворотне поширення похідної по графу. З вузла $z$ виходить одиниця. Заходячи у вузол $B$, вона перетворюється на $\partial A/\partial B$. Після проходження вузла $B$ ця похідна множиться на $\partial B/\partial x$:
$$
g^x ~=~ \frac{\partial z}{\partial x} ~=~ \frac{\partial A}{\partial x} ~=~ \frac{\partial A}{\partial B}\,\frac{\partial B}{\partial x},
$$
$$
g^x ~=~ \frac{\partial z}{\partial x} ~=~ \frac{\partial A}{\partial x} ~=~
\frac{\partial A}{\partial B}\,\frac{\partial B}{\partial x} ~+~
\frac{\partial A}{\partial C}\,\frac{\partial C}{\partial x}.
$$
Аналогічно аналізується другий приклад. У ньому потік градієнта розщеплюється на вузлі $A$, а потім сходиться на листку дерева $x$. Ці дві похідні необхідно просумувати, що відповідає знаку плюс у формулі частинної похідної (під малюнком).
Градієнти для тензорів
У задачах машинного навчання коренем графа (дерева) зазвичай є скалярна величина (наприклад, похибка моделі), тоді як листові вузли графа (параметри моделі) - це тензори. Частинні похідні кореня за компонентами тензора власне й називаються градієнтами.
Нехай зі скалярної функції похибки $L$ на вхід моделі надходить градієнт.
Він поширюється по графу і
входить у вигляді тензора $g^{(\mathbf{Z})}_{ij...}$ справа в деякий вузол $\mathbf{Z}$.
У цьому вузлі відбувається обчислення, яке змінює тензор на $g^{(\mathbf{X})}_{\alpha\beta...}$,
і він входить у вузол $\mathbf{X}$.
Залежно від характеру обчислень у $Z$, число індексів і їхні розмірності тензора можуть змінитися. При цьому розмірність і форма градієнта, що входить у вузол, завжди мають збігатися з розмірністю і формою даних, які зберігаються в цьому вузлі. Оскільки $L$ залежить від тензора $\mathbf{Z}$, який залежить від тензора $\mathbf{X}$, то похідна складеної функції обчислюється таким чином:
(def2)
Якщо коренем обчислювального графа виступає скалярна величина, то градієнт, що виходить із неї, як і раніше, вважають рівним 1, оскільки $\partial L/ \partial L = 1$.
☯ Наведене визначення можна узагальнити на випадок, коли в корені графа знаходиться тензор, а не скаляр. Залежно від цілей, градієнт у ньому ініціалізують тим чи іншим тензором (тієї ж розмірності!). Наприклад, якщо цей тензор складається з одиниць: $g^{(\mathbf{L})}_{ij...}=g^{(\mathbf{Z})}_{ij...}=1$, то відбуватиметься підсумовування всіх компонент кореневого тензора, що перетворить його на скаляр:
$$ g^{(\mathbf{X})}_{\alpha\beta...} ~=~ \sum_{i,j,...} \frac{\partial Z_{ij...}}{\partial X_{\alpha\beta...}} ~=~ \frac{\partial Z}{\partial X_{\alpha\beta...}},~~~~~~~~~~~~~~~Z~=~\sum_{i,j,...} \,Z_{ij...} $$Щоб отримати частинну похідну безпосередньо від компонент $Z_{ij...}$, необхідно взяти $g^{(\mathbf{Z})}_{ij...}$, що складається з нулів, крім єдиного елемента з індексами $i,j,...$, рівного одиниці (проєкційний тензор). Втім, для машинного навчання ці випадки не важливі.
Додавання і множення тензорів
З'ясуємо, як градієнт змінюється при проходженні через різні обчислювальні вузли. Попередньо варто переглянути нагадування щодо роботи із символом Кронекера $\delta_{ij}$ у цьому документі.
✒ Найпростіший вузол додає два тензори з однаковим числом індексів. Скориставшись визначенням (def2), маємо:
$$ Z_{ij...} = X_{ij...} + Y_{ij...}, ~~~~~~~~~~~~~ g^{(\mathbf{X})}_{\alpha\beta...} ~=~ \sum_{ij...} g^{(\mathbf{Z})}_{ij...}\,\frac{\partial Z_{ij...}}{\partial X_{\alpha\beta...}} ~=~ \sum_{ij...} g^{(\mathbf{Z})}_{ij...}\,\delta_{i\alpha}\,\delta_{j\beta}... ~=~ g^{(\mathbf{Z})}_{\alpha\beta...} $$
Таким чином, підсумовування не змінює градієнта,
розщеплюючи його на два однакових тензори, які потрапляють у вузли кожного аргументу операції.
При відніманні $Z_{ij...} = X_{ij...} - Y_{ij...}$
градієнт, що входить у вузол Y, змінить свій знак,
а градієнт у вузол X потрапить без зміни.
✒ Якщо $\mathbf{M}$ - матриця форми (n,m), а $\mathbf{v}$ - вектор із m компонентами, то при їх додаванні відбувається розширення (broadcasting) вектора $\mathbf{v}$: (n,m)+(m,) = (n,m)+(1,m) = (n,m). У цьому випадку градієнт $\mathbf{g}^{(\mathbf{v})}$, що входить у вузол векторного аргументу $\mathbf{v}$, також є вектором:
$$ Z_{ij} = M_{ij} + v_j, ~~~~~~~~~~~~~~~~~ g^{(\mathbf{v})}_{\alpha} = \sum_{i,j} g^{(\mathbf{Z})}_{ij}~\frac{\partial Z_{ij}}{\partial v_{\alpha}} ~=~ \sum_{i,j} g^{(\mathbf{Z})}_{ij}~\delta_{j\alpha} ~=~ \sum_i \,g^{(\mathbf{Z})}_{i\alpha}. $$У матричний аргумент $M_{ij}$ вузла додавання градієнт $g^{(\mathbf{Z})}_{ij}$, як і раніше, потрапляє без зміни. У загальному випадку підсумовування виконується за всіма індексами, які зазнали процедури розширення.
✒ Вузол множення тензорів (без згортки) розглянемо на прикладі двох матриць:
$$ Z_{ij} = M_{ij}\,N_{ij},~~~~~~~~~~~~~~~ g^{(\mathbf{M})}_{\alpha\beta} = \displaystyle\sum_{ i,j} g^{(\mathbf{Z})}_{ij}~\frac{\partial Z_{ij}}{\partial M_{\alpha\beta}} = \displaystyle\sum_{i,j} g^{(\mathbf{Z})}_{ij}~\delta_{i\alpha}\delta_{i\beta}\, N_{ij} = \displaystyle g^{(\mathbf{Z})}_{\alpha \beta}\, N^{\phantom{(\mathbf{Z})}}_{\alpha\beta} $$і аналогічно для $g^{(\mathbf{N})}_{\alpha\beta}$ Таким чином, зміна градієнта повністю аналогічна зміні похідних скалярних величин при проходженні вузла їхнього добутку.
Згортка тензорів
✒ Розглянемо згортку двох векторів у вузлі dot. Її результатом буде скаляр, тому і в вузол входить скаляр $g^{(z)}$:
$$ z = \sum_i u_i\,v_i,~~~~~~~~~~~~~~ g^{(\mathbf{u})}_\alpha = g^{(z)}\, \displaystyle\frac{\partial z}{\partial u_{\alpha}} = g^{(z)}\,v_{\alpha}, $$і аналогічно для $g^{(\mathbf{v})}_{\alpha} $ Таким чином, при зворотному поширенні у вузол dot потрапляє скаляр $g^{(z)}$, а при виході з нього він перетворюється на два вектори: $\mathbf{g}^{(\mathbf{u})} = \mathbf{g}^{(z)} \, \mathbf{v}$ і $\mathbf{g}^{(\mathbf{v})} = \mathbf{g}^{(z)} \, \mathbf{u}$.
✒ Згортка матриці $M_{ij}$ і вектора $v_j$, у фреймворку PyTorch,
позначається як mv.
Результатом операції буде вектор, тому
і градієнт, що входить у вузол, буде вектором $g^{(\mathbf{z})}_{i}$:
Друга формула - це просто згортка вектора і матриці: $\mathbf{g}^{(\mathbf{v})} = \mathbf{g}^{(\mathbf{z})}\,\mathbf{M}$.
✒ Обчислення для згортки двох матриць (результат знову матриця) проводиться аналогічним чином:
$$ Z_{ij} = \sum_{k} M_{ik}\,N_{kj},~~~~~~~~~~~~~~~ \left\{ \begin{array}{lclclcl} g^{(\mathbf{M})}_{\alpha\beta} &=& \displaystyle\sum_{ i,j} g^{(\mathbf{Z})}_{ij}~\frac{\partial Z_{ij}}{\partial M_{\alpha\beta}} &=& \displaystyle\sum_{i,j,k} g^{(\mathbf{Z})}_{ij}~\delta_{i\alpha}\delta_{k\beta}\, N_{kj} &=& \displaystyle\sum_{j} \displaystyle g^{(\mathbf{Z})}_{\alpha j}\, N^{\phantom{(\mathbf{Z})}}_{\beta j}, \\[3mm] g^{(\mathbf{N})}_{\alpha\beta} &=& \displaystyle\sum_{i,j} g^{(\mathbf{Z})}_{ij}~\frac{\partial Z_{ij}}{\partial N_{\alpha\beta}} &=& \displaystyle \sum_{i,j,k} g^{(\mathbf{Z})}_{ij}~M_{ik}\,\delta_{k\alpha}\delta_{j\beta} &=& \displaystyle \sum_{i} M^{\phantom{(\mathbf{Z})}}_{i\alpha}\,g^{(\mathbf{Z})}_{i\beta}. \end{array} \right. $$ Переставляючи індекси в матриці за допомогою операції транспонування $M^\top_{\alpha\beta}=M_{\beta\alpha}$, ці формули можна записати в безіндексній формі: $~~\mathbf{g}^{(\mathbf{M})}= \mathbf{g}^{(\mathbf{Z})}\,\mathbf{N}^\top~~$ і $~~\mathbf{g}^{(\mathbf{N})}= \mathbf{M}^\top\,\mathbf{g}^{(\mathbf{Z})}$.
Подамо отримані вище формули в графічному вигляді, опускаючи індекси у матриць і векторів:
Приклад обчислення градієнта від скалярного добутку двох векторів $z=\mathbf{u}\cdot \mathbf{v}$, для якого $\partial z/\partial \mathbf{u} = \mathbf{v}$:
u, v = tensor([1.,2.], requires_grad=True), tensor([3.,4.], requires_grad=True) z = u.dot(v) # tensor(11., grad_fn=<DotBackward>) z.backward() # запускаємо обчислення градієнтів print(u.grad) # tensor([3., 4.]) print(v.grad) # tensor([1., 2.])
Функції від тензорів
Розглянемо тепер функції від тензора. Якщо це "звичайна" функція, яка застосовується незалежно до кожного елемента тензора, то все як і в скалярному випадку:
$$ Z_{ij...} = f(X_{ij...}),~~~~~~~~~~ g^{(\mathbf{X})}_{\alpha\beta...} ~=~ \sum_{i,j,...} g^{(\mathbf{Z})}_{ij...}~\frac{\partial f(X_{ij...})}{\partial X_{\alpha\beta...}} ~=~\sum_{i,j,...} g^{(\mathbf{Z})}_{ij...}~f'(X_{ij...})~\delta_{i\alpha}\delta_{j\beta}... ~=~ g^{(\mathbf{Z})}_{\alpha\beta...}~f'(X_{\alpha\beta...}). $$ Найпопулярніші в нейронних мережах функції мають такі похідні: $$ \left\{ \begin{array}{rcl} y=\sigma(x)&=&\displaystyle\frac{1}{1+e^{-x}},\\[3mm] \sigma'(x)&=& y\,(1-y) \end{array} \right. ~~~~~~~~~~~~~ \left\{ \begin{array}{rcl} y=\tanh(x) &=& \displaystyle\frac{e^{x}-e^{-x}}{e^{x}+e^{-x}}\\[3mm] \tanh'(x) &=& 1-y^2 \end{array} \right. ~~~~~~~~~~~~~ \left\{ \begin{array}{rcl} y=\text{relu}(x) &=& \text{max}(0,\,x)\\[3mm] \text{relu}'(x) &=& \mathrm{0~if~x~<~0~else~1} \end{array} \right. $$Трохи складніше з функціями, які змінюють розмірність тензора. Розглянемо, наприклад, підсумовування тензора за першим індексом: X.sum(axis=0):
$$ Z_{jk...} = \sum_i X_{ijk...},~~~~~~~~~~ g^{(\mathbf{X})}_{\alpha\beta\gamma...} ~=~ \sum_{j,k,...} g^{(\mathbf{Z})}_{jk...}~\frac{\partial Z_{jk...}}{\partial X_{\alpha\beta\gamma...}} ~=~ \sum_{i,j,k,...} g^{(\mathbf{Z})}_{jk...}~\delta_{i\alpha}\delta_{j\beta}\delta_{k\gamma}\,... ~=~ g^{(\mathbf{Z})}_{\beta\gamma...} $$Таким чином, для кожного значення індексу $\alpha$ в $g^{(\mathbf{X})}_{\alpha\beta\gamma...} $ відбувається дублювання градієнта $g^{(\mathbf{Z})}_{\beta\gamma...}$, що входить у функцію. Коли підсумовуються всі компоненти тензора $\mathbf{X}$, градієнт (тієї ж розмірності), що входить у нього з вузла підсумовування, складатиметься з одиниць, помножених на скалярну величину $g^{(Z)}$, що входить у вузол.
x = 5*torch.eye(2,3) # [ [5., 0., 0.],
x.requires_grad=True # [0., 5., 0.] ]
z = x.sum()
z.backward() # запускаємо обчислення градієнтів
print(x.grad) # [ [1., 1., 1.],
# [1., 1., 1.] ]
Софтмакс і похибка за крос-ентропією
У задачах класифікації часто використовують похибку крос-ентропії (CE, CrossEntropyLoss) перед якою стоїть функція softmax. Ці два обчислювальні вузли є стартовими при зворотному поширенні градієнта.
Функція softmax: $\mathbf{y}=\text{sm}(\mathbf{x})$ нормує вектор $\mathbf{x}$, так, щоб сума компонент вектора $\mathbf{y}$ на виході функції дорівнювала одиниці (зазвичай $y_i$ інтерпретуються як ймовірності класів).
$$ y_i = \frac{e^{x_i}}{\sum_k e^{x_k}},~~~~~~~~~~~~~~~~~~~~~~y_i > 0,~~~~~~\sum_k y_k = 1, ~~~~~~~~~~~~~~~ \frac{\partial y_i}{\partial x_\alpha} = y_i\,\delta_{i\alpha}\ - y_i\, y_\alpha. $$ Зазначимо, що софтмакс $\mathbf{y}=\text{sm}(\mathbf{x})$ - неоднозначна функція. Якщо до кожної компоненти вектора $\mathbf{x}$ додати одне й те саме число, то результат функції не зміниться: $\text{sm}(\mathbf{x}+a) = \text{sm}(\mathbf{x})$. Градієнт $\mathbf{g}^{(\mathbf{y})}$, проходячи через софтмакс, перетворюється на градієнт $\mathbf{g}^{(\mathbf{x})}$: $$ g^{(\mathbf{x})}_\alpha ~=~ \sum_{i}\,g^{(\mathbf{y})}_i\,\frac{\partial y_i}{\partial x_\alpha} ~=~ \Bigr(g^{(\mathbf{y})}_\alpha - \sum_i g^{(\mathbf{y})}_i y_{i}\Bigr)\,y_\alpha. $$Таким чином, від градієнта $g^{(\mathbf{y})}_\alpha$, що входить у функцію $\mathbf{y} = \text{sm}(\mathbf{x})$, віднімається його "середнє" за всіма компонентами з вагами $y_i$ ("ймовірності"), і результат знову множиться на "ймовірності": $\mathbf{g}^{(\mathbf{y})}\odot \mathbf{y} - (\mathbf{g}^{(\mathbf{y})}\mathbf{y})\,\mathbf{y}$.
Похибка CE отримує на вхід "ймовірності" класів $y_i$, обчислені моделлю,
і номер істинного класу $c$.
Як похибка виступає логарифм із протилежним знаком від ймовірності правильного класу.
Мінімізація CE-похибки - це задача максимізації значення "ймовірності"
$y_c$ правильного класу (оскільки завдяки софтмаксу всі $y_i > 0$ і їхня сума дорівнює одиниці, максимізація
$y_c$ мінімізує ймовірності решти класів):
$$
L=\text{CE}(\mathbf{y}, c) = -\log y_c,~~~~~~~~~~~~~~~~g^{(\mathbf{y})}_i=\frac{\partial L}{\partial y_i} = -\frac{\delta_{i c}}{y_c}
=\{0,...,0,\frac{-1}{y_c},0,...,0\}.
$$
Градієнт $g^{(\mathbf{y})}_i$, що виходить із функції похибки, - це вектор із нульовими компонентами, крім $c$-тої компоненти істинного класу. Далі, проходячи через софтмакс, він перетворюється на: $$ g^{(\mathbf{x})}_\alpha ~=~ y_\alpha - \delta_{\alpha c} ~=~ \left\{ \begin{array}{ll} y_i & i \neq c, \\ y_c - 1 & i = c. \end{array} \right. $$ Якби $x_\alpha$ були параметрами моделі, то градієнтний метод зі швидкістю навчання $\lambda$ підправляв би їх таким чином: $$ x_\alpha \mapsto x_\alpha - \lambda\,g^{(\mathbf{x})}_\alpha = \left\{ \begin{array}{ll} x_\alpha - \lambda\, y_\alpha & \alpha\neq c \text{ - зменшуємо для невірних класів} \\[2mm] x_c + \lambda\, (1-y_c) & \alpha = c \text{ - збільшуємо для правильного класу} \end{array} \right. $$ Якщо "правильна ймовірність" $y_c$ близька до одиниці (а решта $y_i$, відповідно, до нуля), параметри $x_i$ перестають змінюватися. На практиці, звісно, вектор $\mathbf{x}$ є не параметром, а виходом моделі. Тому при зворотному поширенні градієнт $g^{(\mathbf{x})}_i$ продовжує рухатися по вузлах до початку графа (до його параметрів).
Міні-PyTorch
Намітимо ідею побудови графа обчислень (деталі можна знайти у файлі: ML_Comp_Graph.ipynb).
Створимо клас тензора, який зберігатиме елементи в масиві numpy.
Синтаксис методів зробимо близьким до синтаксису фреймворка PyTorch,
з оглядом якого можна ознайомитися за цим документом.
У класу Tensor визначимо конструктор і метод tensor, який перетворює аргумент на екземпляр класу Tensor, якщо він ним ще не є:
import numpy as np
class Tensor:
def __init__(self, val, args=None, fn=None):
self.data = np.array(val) # збережені дані
self.grad = None # градієнт, що входить у вузол
self.fn = fn # операція, яку обчислює вузол
self.args = args # список аргументів операції
def tensor(self, t): # для констант у виразах
return t if isinstance(t, Tensor) else Tensor(t)
Основні операції з тензорами здійснюються за допомогою бібліотеки numpy. Крім повернення значення операції, запам'ятовують ім'я функції та посилання на її аргументи. Виклик t = self.tensor(t) робиться, щоб аргументом операції міг бути не тільки Tensor, а й константа у вигляді числа або масиву numpy:
class Tensor: # продовження
def add(self, t): # додавання
t = self.tensor(t)
return Tensor(self.data + t.data, [self, t], "add")
def sub(self, t): # віднімання
t = self.tensor(t)
return Tensor(self.data - t.data, [self, t], "sub")
def mul(self, t): # множення без згортки
t = self.tensor(t)
return Tensor(self.data * t.data, [self, t], "mul")
def dot(self, v): # скалярний добуток векторів
v = self.tensor(v)
return Tensor(np.dot(self.data, v.data), [self, v], "dot")
def mv(self, v): # згортка матриці і вектора
v = self.tensor(v)
return Tensor(np.dot(self.data, v.data), [self, v], "mv")
def mm(self, n): # згортка матриць
n = self.tensor(n)
return Tensor(np.dot(self.data, n.data), [self, n], "mm")
Ключовий метод backward обчислення градієнтів при зворотному поширенні по графу має вигляд:
class Tensor: # продовження
def backward(self, grad = 1):
if self.grad is None:
self.grad = grad
else: # накопичуємо вхідні градієнти
self.grad += grad
if self.fn == "add": # додавання
self.args[0].backward( grad)
self.args[1].backward( grad)
elif self.fn == "sub": # віднімання
self.args[0].backward( grad)
self.args[1].backward(-grad)
elif self.fn in ["dot", "mul"]: # згортка векторів або множення тензорів
self.args[0].backward( grad * self.args[1].data)
self.args[1].backward( self.args[0].data * grad)
elif self.fn == "mv": # згортка матриці і вектора
self.args[0].backward( np.outer(grad, self.args[1].data))
self.args[1].backward( np.dot(grad, self.args[0].data))
elif self.fn == "mm": # згортка двох матриць
self.args[0].backward( np.dot(grad, self.args[1].data.T))
self.args[1].backward( np.dot(self.args[0].data.T, grad))
Розглянемо приклад використання класу Tensor.
v = Tensor([1,2]) # створюємо вектор
m = Tensor(np.eye(2)) # створюємо одиничну матрицю
n = Tensor(np.ones((2,2))) # створюємо матрицю з одиниць
z = m.mm(n).mv(v).dot(v) # будуємо обчислювальний граф
z.backward() # обчислюємо градієнти
print(z) # 9.0
print(v.grad) # [6. 6.]
print(m.grad) # [[3. 3.]
# [6. 6.]]
print(n.grad) # [[1. 2.]
# [2. 4.]]
