notes/machine_learning/neural_networks.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети"
]
},
"source": [
"## Декомпозиция построения и обучения нейронной сети\n",
"\n",
"В построении и обучении нейронных сетей можно выделить три ключевых составляющих:\n",
"\n",
"1. Модель (граф вычислений), то есть то, что отображает входы в выходы;\n",
"2. Функция потерь, то есть то, что оптимизируется при обучении;\n",
"3. Оптимизационная процедура, то есть способ по данным настроить обучаемые параметры.\n",
"\n",
"#### Модель\n",
"\n",
"* Какие базовые и составные операции используются?\n",
" - классические нейроны, т.е. то, что вычисляет $f(Wx + b)$, где [функция активации](__home_url__/notes/Функции активации для нейронных сетей) $f$ — это:\n",
" - тождественное преобразование (подходит для выходного слоя в задаче регрессии),\n",
" - нелинейная функция, на положительной полуоси близкая к тождественному преобразованию (это основной источник нелинейности для скрытых слоёв):\n",
" - ReLU,\n",
" - Leaky ReLU,\n",
" - Parametric ReLU,\n",
" - MaxOut,\n",
" - Exponential Linear Unit,\n",
" - Gaussian Error Linear Unit,\n",
" - софтмакс (подходит для выходного слоя в задаче классификации),\n",
" - сигмоида (подходит для выходного слоя в задаче классификации, где один объект может принадлежать ко многим классам; в скрытых слоях без нужды лучше не использовать),\n",
" - гиперболический тангенс (видоизменённая версия сигмоиды),\n",
" - etc;\n",
" - [нормализация](__home_url__/notes/Нормализация в нейронных сетях):\n",
" - пакетная,\n",
" - послойная,\n",
" - etc;\n",
" - [субдискретизация](__home_url__/notes/Субдискретизация),\n",
" - [LSTM-юниты](__home_url__/notes/Внутреннее устройство LSTM-юнита),\n",
" - блоки с [вниманием](__home_url__/notes/Архитектура seq2seq и механизим внимания) или [трансформерные](__home_url__/notes/Трансформер) блоки,\n",
" - etc.\n",
"* Как из операций формируются слои?\n",
" - Какие количественные характеристики?\n",
" - Сколько слоёв?\n",
" - Какой ширины каждый из слоёв?\n",
" - Какие связи между слоями?\n",
" - полные,\n",
" - локальные (то есть каждый нейрон связан лишь с некоторой областью предыдущего слоя),\n",
" - свёрточные (частный случай локальных, где к тому же веса в фильтре одинаковые для всего слоя):\n",
" - с классической свёрткой,\n",
" - с транспонированной свёрткой,\n",
" - с раздвинутой (dilated) свёрткой,\n",
" - мозаично-свёрточные (веса в фильтре одинаковые через каждые $k$ позиций),\n",
" - рекуррентные (слой соединён с самим собой),\n",
" - остаточные (как в ResNet, в обход одного или нескольких следующих слоёв c последующим суммированием),\n",
" - плотные (как в DenseNet, в обход одного или нескольких следующих слоёв c последующей конкатенацией),\n",
" - etc;\n",
" - Какие веса являются общими/связанными (shared weights)?\n",
"\n",
"#### Функция потерь\n",
"\n",
"* Для регрессии:\n",
" - MSE, среднеквадратичная ошибка (ведёт к оптимизации правдоподобия обучающей выборки при гауссовском шуме в целевой переменной),\n",
" - MAE, средний модуль ошибки (ведёт к оптимизации правдоподобия обучающей выборки при лапласовском шуме в целевой переменной),\n",
" - etc.\n",
"* Для классификации:\n",
" - [логарифмическая функция потерь](__home_url__/notes/Логарифмическая функция потерь и энтропия Шеннона) (ведёт к оптимизации правдоподобия обучающей выборки при отсутствии шумов в метках объектов обучающей выборки),\n",
" - дифференцируемая [аппроксимация](__home_url__/notes/Аппроксимация функции потерь) точности по обоим классам,\n",
" - etc.\n",
"* Для других задач:\n",
" - GAN loss,\n",
" - style transfer loss,\n",
" - функции потерь для ранжирования:\n",
" - [попарные](__home_url__/notes/RankNet, LambdaRank и YetiRank) (например, RankNet), включая заданные только через градиенты (LambdaRank и YetiRank),\n",
" - [посписочные](__home_url__/notes/Посписочные функции потерь),\n",
" - etc.\n",
"\n",
"#### Оптимизационная процедура\n",
"\n",
"* Какой метод оптимизации выбрать?\n",
" - градиентный спуск с таким приёмом, как [обратное распространение](__home_url__/notes/Обратное распространение (backpropagation)) (эта вычислительная техника сильно ускоряет подсчёт градиентов):\n",
" - первого порядка,\n",
" - второго порядка (метод Ньютона, (L-)BFGS);\n",
" - генетические или популяционные алгоритмы (не мэйнстрим в обучении нейронных сетей; иногда применяются в обучении с подкреплением в [методе кросс-энтропии](https://github.com/udacity/deep-reinforcement-learning/blob/master/cross-entropy/CEM.ipynb) и в [эволюционных стратегиях](https://arxiv.org/pdf/1703.03864.pdf)),\n",
" - [вариационный вывод](__home_url__/notes/Вариационный байесовский вывод и mean-field approximation) (как правило, это вычислительно затратно, но зато поддерживается обучение дискретных мест, через которые не проходит градиент).\n",
"* Какие техники [регуляризации](__home_url__/tags/регуляризация) использовать?\n",
" - [$L_p$-регуляризацию](__home_url__/notes/Регуляризация штрафом, накладываемым на норму обучаемых параметров) ($L_1$-регуляризация приводит к отбору весов, а $L_2$-регуляризация приводит к затуханию весов),\n",
" - [раннюю остановку](__home_url__/notes/Ранняя остановка),\n",
" - [дропаут](__home_url__/notes/Дропаут),\n",
" - обогащение (augmentation) данных: в частности, подмешивание шума,\n",
" - сглаживание целевой переменной (label smoothing),\n",
" - [многозадачное обучение](__home_url__/notes/Многозадачное обучение (multi-task learning)).\n",
" \n",
"На частном случае градиентного спуска первого порядка остановимся подробнее, потому что это самый популярный вариант.\n",
"\n",
"- Как [инициализировать веса](__home_url__/notes/Инициализация весов в нейронных сетях) каждого из слоёв перед началом обучения?\n",
"- Когда обновлять веса?\n",
" - после подсчёта коррекций на всех объектах обучающей выборки (классический градиентный спуск),\n",
" - после подсчёта коррекций на всём пакете из случайно выбранных объектов обучающей выборки (пакетный градиентный спуск),\n",
" - после подсчёта коррекций на каждом отдельно взятом объекте (стохастический градиентный спуск).\n",
"- Какой темп обучения (learning rate) выбрать?\n",
" - постоянный (нет гарантий сходимости для пакетного и стохастического градиентного спуска),\n",
" - с расписанием, то есть в виде заранее заданной невозрастающей функции от числа шагов,\n",
" - [адаптивный](__home_url__/notes/Методы подбора темпа обучения в нейронных сетях) (как от итерации к итерации, так и покоординатно):\n",
" - AdaGrad (может приводить к излишне раннему затуханию темпа обучения),\n",
" - RMSProp,\n",
" - Adam.\n",
"- Какую инерцию (momentum) обновлений весов выбрать?\n",
" - никакую,\n",
" - обычную (помогает оптимизации внутри «каньонов»),\n",
" - инерцию Нестерова (отличается от обычной только весами, в которых считается градиент)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети"
]
},
"source": [
"## Обратное распространение (backpropagation)\n",
"\n",
"Обратное распространение — приём, позволяющий эффективно вычислять частные производные функции по её параметрам.\n",
"\n",
"В контексте нейронных сетей обратное распространение пригождается при выполнении шага градиентного спуска. Наглядности ради рассмотрим стохастический градиентный спуск, где веса обновляются на каждом объекте отдельно, но для классического и пакетного градиентного спуска просто добавится ещё одно измерение, индексирующее объекты пакета (mini-batch'а), из-за чего матрицы станут тензорами, но сути это не поменяет. Итак, пусть имеются:\n",
"* объект с вектором признаков $x \\in \\mathbb{R}^n$,\n",
"* целевая переменная на этом объекте $y$, являющаяся вещественным числом (в задаче регрессии) или вектором (например, one-hot вектором метки класса в задаче многоклассовой классификации),\n",
"* предсказание нейронной сети $\\hat{y}$, могущее быть числом или вектором в зависимости от $y$,\n",
"* функция потерь $L$, по $y$ и $\\hat{y}$ возвращающая вещественное число.\n",
"\n",
"Тогда $i$-я компонента вектора обновления весов нейронной сети $w$ на этом объекте при шаге стохастического градиентного спуска с точностью до знака и умножения на темп обучения $\\eta$ имеет вид:\n",
"$$\\frac{\\partial L(y, \\hat{y})}{\\partial w_i} = \\nabla_{w_i}\\hat{y} \\: \\nabla_\\hat{y}L(y, \\hat{y}),$$\n",
"где общности ради можно считать, что оператор $\\nabla$ возвращает матрицу Якоби (матрицу, составленную из частных производных) размерности $k \\times l$, где $k$ — размерность того, по чему дифференцируется, а $l$ — размерность того, что дифференцируется. При таком определении градиент (вектор частных производных) является частным случаем матрицы Якоби, и, на самом деле, в выписанной формуле фигурируют лишь скаляры и векторы: множитель $\\nabla_{w_i}\\hat{y}$ имеет размерность $1 \\times m$, а множитель $\\nabla_\\hat{y}L(y, \\hat{y})$ имеет размерность $m \\times 1$, где $m$ — 1, если $y$ и $\\hat{y}$ скаляры, или длина $y$ или $\\hat{y}$, если это векторы. Так или иначе, множитель $\\nabla_\\hat{y}L(y, \\hat{y})$ посчитать легко из явного вида функции $L$. Встаёт вопрос, как посчитать $\\nabla_{w_i}\\hat{y}$, и вот тут-то и пригождается обратное распространение.\n",
"\n",
"На самом деле, вычислить $\\nabla_{w_i}\\hat{y}$ можно просто в лоб. Для этого достаточно вспомнить, что нейронная сеть является композицией дифференцируемых функций, а потом пройтись по всем путям от нейрона, к которому относится рассматриваемый вес $w_i$ (или от каждого из таких нейронов, если вес $w_i$ общий между несколькими нейронами), до любого выхода нейронной сети, применяя при этом формулу дифференцирования композиции:\n",
"$$\\nabla_x (f \\circ g) = \\nabla_x g \\nabla_g f.$$\n",
"Кстати, в скалярном виде эта формула известна ещё из школьной программы как:\n",
"$$(f \\circ g)^{\\prime}(x) = f^{\\prime}(g(x))g^{\\prime}(x).$$\n",
"Результаты, полученные для каждого из путей, надо просуммировать, чтобы получить финальный результат.\n",
"\n",
"Так можно вычислить обновление какой-то одной компоненты вектора весов. Но если сделать это для всех значений $i$, то окажется, что значительное количество частных производных будет многократно посчитано заново. Например, для многослойного перцептрона частная производная значения активации какого-либо нейрона по значению активации нейрона предыдущего слоя будет посчитана столько раз, сколько существует путей из какого-либо входного или скрытого нейрона в какой-либо выходной нейрон, проходящих через связь между двумя рассматриваемыми нейронами.\n",
"\n",
"Обратное распространение сводится к тому, что процесс вычисления частных производных становится организован таким образом, что все частные производные берутся лишь по одному разу. Для этого происходит движение по нейронной сети в обратную сторону (от выходов ко входам), и считаются частные производные выходов по значению активации текущего нейрона. В этом простом способе избежать повторов и заключается вся суть обратного распространения, а вектор градиента $L$ по $w$, который оно находит, является тем же самым вектором градиента $L$ по $w$, который был бы найден любым другим способом вычислить его (например, неэффективным способом прямого прохода, описывавшимся выше).\n",
"\n",
"Справедливости ради стоит отметить, что при вычислении частных производных есть дилемма между количеством вычислений и расходом памяти, а обратное распространение (по крайней мере, в вышеописанном виде) занимает крайнюю позицию, когда оптимизируется количество вычислений ценой максимальных требований к памяти. С точки зрения памяти, наоборот, способ считать всё в лоб наиболее эффективен, потому что ему достаточно константного объёма памяти.\n",
"\n",
"Наконец, важно подчеркнуть, что применимость обратного распространения не ограничивается нейронными сетями. Более общим понятием является граф дифференцируемых вычислений, то есть направленный граф, воспроизводящий некоторую дифференцируемую функцию, получающую на вход вещественный вектор и возвращающую вещественный вектор (возможно, другой длины). Вершины графа вычислений бывают трёх типов:\n",
"* входы — в них не ведут никакие рёбра, и в каждом из них задаётся соответствующая компонента входного вектора;\n",
"* операции — в них должно вести хотя бы одно ребро и из них должно выходить хотя бы одно ребро; каждой такой вершине сопоставлена дифференцируемая функция, принимающая на вход то, что отдают вершины, откуда ведут рёбра, и возвращающая вещественное число (теоретически это никак не ограничивает общность, потому что для векторнозначных функций можно сделать несколько операций, каждая из которых вычисляет соответствующую компоненту, однако на практике вычислять все компоненты вектора вместе может быть эффективнее);\n",
"* выходы — в каждый из них ведёт ровно одно ребро, и результат операции, откуда ведёт ребро, становится соответствующей компонентой выходного вектора.\n",
"\n",
"Имея такой граф вычислений, методом обратного распространения можно, двигаясь от конца исходного графа к началу, построить новый граф вычислений, который бы выдавал частные производные выходов по входам (всем или только интерессующим). Частный случай нейронных сетей получается из общего понятия графа дифференцируемых вычислений так: входами являются обучаемые параметры нейронной сети и признаки объектов пакета, а выходом является значение функции потерь на этом пакете. Если говорить только об обучении, то, конечно, частные производные по признакам объектов можно не вычислять, но они пригождаются для создания шума, сбивающего с толку (adversarial noise)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети"
]
},
"source": [
"## Функции активации для нейронных сетей\n",
"\n",
"#### Тождественная функция\n",
"\n",
"Если слой что-либо вычисляет в терминах весов и свободных членов (скажем, преобразует выход предыдущего слоя $x$ по формуле $Wx + b$), то можно просто это же и вернуть. По факту в таком случае активацией будет тождественная функция, хотя иногда эту активацию не совсем корректно называют линейной, имея в виду, что в целом весь слой с ней осуществляет линейное (точнее, аффинное) преобразование.\n",
"\n",
"Тождественная активация хороша тем, что она не вносит в градиент множитель, равный её производной, ведь он равен 1. Это снижает шансы на возникновение проблем с затухающим или вздувающимся градиентом, но тем не менее подобные проблемы возможны (например, из-за неправильной инициализации весов).\n",
"\n",
"В выходном слое использовать тождественную активацию можно, если стоит задача регрессии. Для задачи классификации тождественная активация не даёт никаких гарантий того, что на выходе получится вектор вероятностей, что делает невозможным её применение. Точнее, можно что-то придумать (например, для бинарной классификации суммировать все компоненты выходного вектора и говорить, что класс положительный, если сумма больше 0, и нулевой иначе), но непонятно, зачем. \n",
"\n",
"В скрытых слоях использовать тождественную активацию можно, если понимать, что это даст. Например, если в многослойном перцептроне везде использовать тождественную активацию, то, каким бы глубоким этот перцептрон ни был, та же выразительная сила будет доступна перцептрону без скрытых слоёв, ведь не будет никакой нелинейности. Однако вот пример, когда в тождественной активации скрытого слоя есть смысл. Пусть слой получает вектор $x_1$ длины $k$, преобразует его по формуле $W_1 x_1 + b_1$ в вектор длины $l$ и имеет тождественную активацию, а затем идёт слой, преобразующий свой вход $x_2$ длины $l$ по формуле $W_2 x_2 + b_2$ в вектор длины $m$ и применяющий произвольную активацию $\\zeta$. Результат после двух этих слоёв равен $\\zeta(W_2(W_1 x_1 + b_1) + b_2) = \\zeta(W_2 W_1 x_1 + (W_2 b_1 + b_2)) = \\zeta(W_3 x_1 + b_3)$. Не любая матрица $W_3$ размера $m \\times k$ представима в виде произведения матриц размера $m \\times l$ и $l \\times k$, и при $l < k, m$ такое ограничение можно рассматривать как дополнительную регуляризацию.\n",
"\n",
"#### Софтмакс\n",
"\n",
"Строго говоря, функцию активации софтмакс следовало бы назвать софтаргмакс, потому что она является гладким приближением операции $\\arg \\max$. По входному вектору $x$ длины $k$ эта функция возвращает вектор той же длины, $i$-я компонента которого равна:\n",
"$$\\mathrm{softmax}(x)_i = \\frac{e^{x_i}}{\\sum_{j=1}^k e^{x_j}}.$$\n",
"По сравнению с исходным вектором $x$ вектор $\\mathrm{softmax}(x)$ можно интерпретировать как вектор вероятностей, ведь все его компоненты лежат на интервале $(0; 1)$ и дают в сумме 1. Благодаря этому свойству софтмакс часто используется как активация выходного слоя нейронной сети в задачах классификации.\n",
"\n",
"Если из каждой компоненты вектора $x$ вычесть константу $c$, значение софтмакса не изменится. Поэтому вычислять софтмакс можно разными способами:\n",
"* по исходному вектору $x$,\n",
"* по вектору $x - \\max_i x_i$,\n",
"* по вектору $x - x_k$.\n",
"\n",
"Второй из этих вариантов обладает наибольшей вычислительной устойчивостью. Третий вариант примечателен только тем, что при $k = 2$ он даёт сигмоидную функцию активации:\n",
"$$\\sigma(z) = \\frac{1}{1 + e^{-z}},$$\n",
"где $z = x_1$. Тогда $\\sigma(z)$ интерпретируется как предсказанная вероятность положительного класса, а $1 - \\sigma(z)$ — как предсказанная вероятность нулевого класса.\n",
"\n",
"Если софтмакс используется в качестве активации выходного слоя, то при обучении желательно использовать [логарифмическую функцию потерь](__home_url__/notes/Логарифмическая функция потерь и энтропия Шеннона). К примеру, если для задачи классфикации зачем-то взять в качестве функции потерь MSE между one-hot encoded вектором истинного класса объекта и вектором предсказанных вероятностей, то в случаях, когда нейронная сеть очень уверенно предсказывает неверный класс, градиент этой ошибки не пройдёт через софтмакс, потому что в подобных регионах софтмакс насыщается и имеет почти нулевые частные производные. А вот для логарифмической функции потерь из-за взаимоуничтожения экспоненты из определения софтмакса и логарифма из определения логарифмической функции потерь градиент будет затухать, только если нейронная сеть уверенно предсказывает верный класс (но тогда и ошибки никакой нет).\n",
"\n",
"Использовать софтмакс в качестве активации в скрытых слоях не рекомендуется, если на то нет весомых причин. Во-первых, из-за насыщения эта активация будет приводить к неинформативным градиентам. Во-вторых, при прямом проходе по сети после софтмакса, как правило, лишь единицы нейронов будут иметь значения, заметно отличающиеся от 0, ведь софтмакс имитирует поведение операции $\\arg \\max$. \n",
"\n",
"#### Сигмоида и гиперболический тангенс\n",
"\n",
"Выше уже возникала сигмоидная функция:\n",
"$$\\sigma(x) = \\frac{1}{1 + e^{-x}}.$$\n",
"Теперь предлагается применять её не к первой компоненте вектора длины 2, где вторая компонента нулевая, а поэлементно к каждой компоненте вектора произвольной длины.\n",
"\n",
"Точно так же поэлементно можно применять гиперболический тангенс:\n",
"$$\\tanh(x) = \\frac{e^x - e^{-x}}{e^x + e^{-x}} = 2\\sigma(2x) - 1.$$\n",
"Из последнего равенства видно, что, на самом деле, гиперболический тангенс довольно похож на сигмоиду.\n",
"\n",
"Ни одна из этих двух активаций не может использоваться в выходном слое для задачи регрессии, потому что их область значений — $(0; 1)$. Для классификации же проблема в том, что поэлементное применение не предоставляет никаких гарантий того, что в сумме все компоненты вектора дадут 1. Однако, поскольку каждая компонента лежит между 0 и 1, эти функции активации можно использовать в выходном слое для тех задач классификации, где объект может принадлежать сразу к нескольким классам. В таком случае $i$-я компонента выходного вектора считается предсказанной вероятностью принадлежности к $i$-му классу и ничего не говорит про принадлежность к остальным классам.\n",
"\n",
"Исторически сигмоида и гиперболический тангенс широко использовалась в качестве нелинейности в скрытых слоях неглубоких сетей, потому что, во-первых, эти функции активации гладкие, а, во-вторых, их производные аналитически выражаются через их значения, что упрощает вычисления:\n",
"$$\\sigma^\\prime(x) = \\sigma(x)(1 - \\sigma(x)),$$\n",
"$$\\tanh^\\prime(x) = 1 - \\tanh^2(x).$$\n",
"Однако из этих же формул видна серьёзная проблема для глубокого обучения: выписанные производные всегда меньше 1 по модулю, а это означает, что в достаточно глубокой сети, где во всех скрытых слоях используются сигмоиды или гиперболические тангенсы, затухание градиента гарантировано. К этому можно добавить, что обе функции насыщаются при значениях своего аргумента, хоть сколько-нибудь больших по модулю, что тоже вносит вклад в затухание градиента.\n",
"\n",
"В то же время эти активации могут фигурировать в скрытых слоях внутри сложносоставных юнитов, если там они выполняют специальную роль. Например, в [LSTM](__home_url__/notes/Внутреннее устройство LSTM-юнита) сигмоида используется в вентилях, потому что значения вентилей показывают, какую долю сигнала пропустить, и потому они должны быть от 0 до 1.\n",
"\n",
"#### ReLU, LReLU, PReLU, MaxOut\n",
"\n",
"Разбор предыдущих функций активации наводит на мысль, что для скрытых слоёв хорошо бы иметь что-то, что очень похоже на тождественную функцию активации (ведь она создаёт меньше всего проблем с градиентом), но при этом вносит нелинейность. Одной из таких активаций является так называемый Rectified Linear Unit:\n",
"$$\\mathrm{ReLU}(x) = \\max(0, x).$$\n",
"Применяется эта функция активации поэлементно.\n",
"\n",
"Для ReLu важна правильная инициализация весов. Как и в случае с тождественной активацией, при чрезмерно больших начальных значениях возможно вздутие градиента. А ещё нейрон с ReLU-активацией может выбыть, если на всех объектах до активации в нём будут получаться отрицательные значения (например, если при положительных входных признаках в первом скрытом слое все веса и свободный член оказались отрицательными). Такой выбывший нейрон не будет вносить никакого вклада в предсказание, а градиент до его весов доходить не будет, потому что у локально константной функции нулевая производная.\n",
"\n",
"Для решения проблемы выбытия нейронов придумали Leaky ReLU:\n",
"$$\\mathrm{LReLU}(x) = \\max(\\alpha x, x),$$\n",
"где $\\alpha$ — константа и, как правило, $0 < \\alpha < 0.1$. Если же $\\alpha$ положить не константой, а обучаемым параметром, то получится Parametric ReLU.\n",
"\n",
"Ещё большее обобщение получается, если полагать активацию кусочно-линейной функцией, в которой все углы наклона и точки излома определяются обучаемыми параметрами. Один из вариантов, как это сделать, называется MaxOut. В нём вместо классического слоя с весами $W$ и свободным членом $b$ используется слой из составных юнитов, у которого есть $n$ весов $W_i$ и свободных членов $b_i$, а активация каждого юнита выглядит так:\n",
"$$\\mathrm{MaxOut}(x) = \\max_{i \\in \\{1, \\dots, n\\}}(W_i x + b_i).$$\n",
"В теории для любой выпуклой функции активации при $n \\to +\\infty$ через MaxOut можно получить её кусочно-линейное приближение.\n",
"\n",
"#### ELU и GELU\n",
"\n",
"В предыдущем разделе все функции активации были кусочно-линейными. Но можно рассмотреть и аналоги ReLU, не являющиеся кусочно линейными.\n",
"\n",
"Один из них: Exponential Linear Unit, ELU. Если $x \\ge 0$, то:\n",
"$$\\mathrm{ELU}(x) = x.$$\n",
"Если же $x < 0$, то:\n",
"$$\\mathrm{ELU}(x) = \\alpha (e^x - 1),$$\n",
"где $\\alpha$ — константа.\n",
"\n",
"Другой вариант: Gaussian Error Linear Unit, [GELU](https://arxiv.org/pdf/1606.08415.pdf):\n",
"$$\\mathrm{GELU}(x) = \\Phi(x)x,$$\n",
"где $\\Phi$ — кумулятивная функция стандартного нормального распределения."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"регуляризация",
"нейронные_сети"
]
},
"source": [
"## Дропаут\n",
"\n",
"#### Введение\n",
"\n",
"Дропаут — метод регуляризации, применяемый к нейронным сетям. Выходной слой не затрагивается дропаутом, а для $i$-го слоя, не являющегося выходным, у дропаута есть гиперпараметр $r_i$, являющийся вероятностью, с которой произвольный юнит этого слоя будет сохранён при обучении на одном пакете. \n",
"\n",
"#### Обучение\n",
"\n",
"Граф вычислений выходов нейронной сети по её входам модифицируется так, что в $i$-м слое (не являющемся выходным) вместо $j$-го юнита ставится блок из трёх юнитов:\n",
"* юнита, который имеет все те же входы, что и исходный, и выполняет ту же операцию, что и исходный;\n",
"* юнита, хранящего в себе константу $\\mu_{ij}$;\n",
"* юнита, вычисляющего произведение двух предыдущих юнитов, дополнительно умноженное на $\\frac{1}{r_i}$, и являющегося входом для всех тех юнитов, для которых входом был исходный юнит.\n",
"\n",
"Для каждого пакета все $\\mu_{ij}$ независимо сэмплируются из распределения Бернулли с вероятностью успеха $r_i$, после чего полагаются константами. Иными словами, можно считать, что те юниты, для которых $\\mu_{ij} = 0$, удаляются. По получившемуся графу делается шаг пакетного градиентного спуска.\n",
"\n",
"#### Применение\n",
"\n",
"Применяется исходная нейронная сеть со всеми своими юнитами и без умножения того, что отдаёт $i$-й слой, на $\\frac{1}{r_i}$.\n",
"\n",
"#### Интерпретация\n",
"\n",
"На дропаут можно смотреть как на способ, побуждающий юниты скрытых слоёв выучивать представления данных, которые были бы полезны не только в контексте всех юнитов этого слоя, но и сами по себе. Нейронная сеть становится избыточной и устойчивой к потере части своих юнитов.\n",
"\n",
"Другой взгляд на дропаут сводится к тому, что это метод, вместо одной нейронной сети обучающий ансамбль нейронных сетей, у которых все веса общие, но состав юнитов разный. Если у исходной нейронной сети во всех слоях кроме выходного $m$ юнитов, то в ансамбле будет $2^m$ различных нейронных сетей.\n",
"\n",
"На самом деле, у умножения того, что $i$-й слой отдаёт $(i+1)$-му, на $\\frac{1}{r_i}$ нет строгого обоснования (за исключением простых частных случаев), а есть лишь эвристическое пояснение, что так не меняется ожидаемая сумма по всем связям между этими слоями. Поэтому есть и альтернативная версия дропаута, отталкивающаяся от его интерпретации как ансамбля. Умножение на $\\frac{1}{r_i}$ не делается при обучении, а вместо этого на этапе применения сэмплируются $k$ различных реализаций $\\mu_{ij}$, после чего усредняются предсказания $k$ получившихся прореженных нейронных сетей. "
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети"
]
},
"source": [
"## Нормализация в нейронных сетях\n",
"\n",
"#### Введение\n",
"\n",
"Нейронные сети с нормализацией имеют то преимущество перед нейронными сетями без неё, что обучаются быстрее, а ещё их обучению сопутствует некоторая дополнительная регуляризация, благодаря которой порой не нужен [дропаут](__home_url__/notes/Дропаут).\n",
"\n",
"Идея, стоящая за нормализацией, восходит к тому, что в машинном обучении бывает полезно центрировать данные и делать их дисперсию единичной. Однако в случае глубоких нейронных сетей классическое масштабирование (то есть вычитание из признаков их средних и деление на их среднеквадратичное отклонение) оказывается недостаточным, если его просто провести в рамках предобработки данных. Эффект от разовой предобработки может и не дойти до слоёв, расположенных далеко от входных. Значит, есть смысл делать масштабирование в каждом слое отдельно. Иными словами, есть смысл нормировать то, что какой-либо промежуточный слой подаёт на вход следующему слою. И помимо того, что это может быть полезно из общих соображений, в контексте нейронных сетей есть и ещё один довод за это: у функций активации, таких как сигмоида или гиперболический тангенс, градиенты заметно отличаются от нуля лишь в окрестности нуля, а поэтому подача на вход активации больших по модулю значений приведёт к затуханию распространения информации при обучении.\n",
"\n",
"Обычное нормирование в каждом слое является вычислительно неэффективным. Действительно, чтобы его сделать, при зафиксированных текущих весах надо прогнать через нейронную сеть всё обучающее множество, но обычно значения весов обновляют после каждого пакета (mini-batch). Поэтому были придуманы различные варианты процедур нормализации, специально предназначенные для нейронных сетей. Исторически первым вариантом такой нормализации была [пакетная нормализация](https://arxiv.org/pdf/1502.03167.pdf) (batch normalization), а впоследствии она была доработана до [пакетной ренормализации](https://arxiv.org/pdf/1702.03275.pdf), и, на самом деле, далее именно эта модифицированная версия далее будет называться пакетной нормализацией.\n",
"\n",
"#### Переменные, вносимые пакетной нормализацией\n",
"\n",
"Со слоем пакетной (ре)нормализации ассоциированы следующие сущности:\n",
"* Два вектора, обучаемых пакетным градиентных спуском:\n",
" - $\\gamma$, вектор перемасштабирования, инициализируется вектором из одних единиц той же длины, что и размер предыдущего слоя,\n",
" - $\\beta$, вектор сдвига, инициализируется вектором из одних нулей той же длины, что и размер предыдущего слоя;\n",
"* Два вектора, существующих только во время обучения:\n",
" - $\\mu_\\mathrm{batch}$, вектор средних по текущему пакету значений, подаваемых на вход слою пакетной нормализации,\n",
" - $\\sigma_\\mathrm{batch}$, вектор среднеквадратичных отклонений значений, подаваемых на вход слою пакетной нормализации, подсчитанный по текущему пакету;\n",
"* Два вектора, арифметическими операциями обновляемые на каждом пакете во время обучения и остающиеся константами во время применения, нужны они только на стадии применения:\n",
" - $\\mu_\\mathrm{cum}$, вектор экспоненциального среднего от векторов средних по пакетам значений, подаваемых на вход слою,\n",
" - $\\sigma_\\mathrm{cum}$, вектор экспоненциального среднего от векторов внутрипакетных среднеквадратичных отклонений значений, подаваемых на вход слою.\n",
" \n",
"К числу гиперпараметров пакетная нормализация добавляет только коэффициент сглаживания $\\alpha$ для подсчёта экспоненциальных средних (или несколько таких коэффициентов для разных слоёв и отдельно для средних и среднеквадратичных отклонений).\n",
"\n",
"#### Обучение и применения для слоя пакетной нормализации\n",
"\n",
"Рассмотрим слой пакетной нормализации, которому в пакете подаются векторы-строки $u_i$, где $i$ принимает значения от 1 до размера пакета, а все $u_i$ имеют длину, равную размеру предыдущего слоя. Тогда обучение разбивается на такие шаги:\n",
"* Вычислить $\\mu_\\mathrm{batch}$ как среднее $u_i$ и вычислить $\\sigma_\\mathrm{batch}$ как среднеквадратичное отклонение $u_i$;\n",
"* Обновить значения $\\mu_\\mathrm{cum}$ и $\\sigma_\\mathrm{cum}$ по правилу простого экспоненциального сглаживания:\n",
"$$\\mu_\\mathrm{cum} := \\alpha\\mu_\\mathrm{cum} + (1-\\alpha)\\mu_\\mathrm{batch},$$\n",
"$$\\sigma_\\mathrm{cum} := \\alpha\\sigma_\\mathrm{cum} + (1-\\alpha)\\sigma_\\mathrm{batch};$$\n",
"* Вычислить нормализованные значения $v_i = (u_i - \\mu_\\mathrm{batch}) \\: / \\: (\\sigma_\\mathrm{batch} + \\varepsilon)$, где $\\varepsilon$ — некоторая малая константа, позволяющая избежать проблем с делением на ноль;\n",
"* Как вход для следующего слоя на соответствующем ($i$-м) объекте батча передать вектор $\\gamma \\circ v_i + \\beta$, где $\\circ$ обозначает поэлементное умножение;\n",
"* При обновлении параметров нейронной сети методом обратного распространения ошибок также считать градиенты по $\\gamma$ и $\\beta$, чтобы градиентный спуск сам мог решить, какими примерно должны быть средние и дисперсии, ведь это влияет, например, на то, какие участки нелинейности функции активации задействованы.\n",
"\n",
"На стадии применения для нормализации всегда используются $\\mu_\\mathrm{cum}$ и $\\sigma_\\mathrm{cum}$, а $\\gamma$ и $\\beta$ полагаются выученными константными векторами.\n",
"\n",
"На то, почему на стадии применения используются экспоненциальные средние от среднего и среднеквадратичного отклонения, можно посмотреть с такой точки зрения. Есть две крайности. С одной стороны, простое среднее по всем пакетам от внутрипакетных средних лучше оценивает среднее на данных для применения, чем одно лишь последнее значение $\\mu_\\mathrm{batch}$, и аналогично среднее по всем пакетам от внутрипакетных среднеквадратичных отклонений лучше оценивает среднеквадратичное отклонение на данных для применения, чем одно лишь последнее значение $\\sigma_\\mathrm{batch}$. С другой стороны, под конец обучения (т.е. на последнем пакете) слой пакетной нормализации использовал текущие значения $\\mu_\\mathrm{batch}$ и $\\sigma_\\mathrm{batch}$ и в подбор финальных значений $\\gamma$ и $\\beta$ они внесли наиболее свежий вклад. Как компромисс между этими двумя крайностями (средним по всем пакетам и только последним значением) и выбрано экспоненциальное среднее.\n",
"\n",
"#### Открытые вопросы\n",
"\n",
"Связанные с пакетной нормализацией вопросы, на которые пока нет однозначных ответов, таковы:\n",
"* почему же всё-таки улучшается результат;\n",
"* стоит ли делать пакетную нормализацию сразу же перед функцией активации или же сразу же после неё (разные специалисты делают и так, и так).\n",
"\n",
"Остановимся на первом вопросе. Попытаться объяснить, почему пакетная нормализация улучшает результаты, можно вот как. Когда в процессе обучения меняется распределение выходов некоторого слоя, следующий за ним слой оказывается обученным на предшествовавших этому входах, то есть на входах, имевших другое распределение, — это то, что называют внутренним сдвигом переменных (internal covariance shift), и это то, что якобы устраняется при помощи нормализации. Такое объяснение приводилось в оригинальной статье, но позже [было показано](https://arxiv.org/pdf/1805.11604.pdf), что это, в лучшем случае, вводная иллюстрация, но никак не настоящее объяснение. Новая гипотеза сводится к тому, что пакетная нормализация делает зависимость функции потерь от настраиваемых параметров более гладкой. Также считается, что пакетная нормализация добавляет шум, содержащийся в статистиках, посчитанных на текущем пакете, и это является формой регуляризации.\n",
"\n",
"Помимо теоретических неясностей у пакетной нормализации есть и практические недостатки:\n",
"* нейронные сети с пакетной нормализацией могут обучаться только пакетным градиентным спуском;\n",
"* при малом размере пакета качество может быть не на высоте, ведь средние и среднеквадратичные отклонения считаются по малому числу объектов;\n",
"* применение в рекуррентных нейронных сетях затруднено тем, что у одного и того же слоя в разные моменты времени свои статистики.\n",
"\n",
"В связи с этим появились многочисленные [альтернативы](https://web.archive.org/web/20201023123942/https://mlexplained.com/2018/11/30/an-overview-of-normalization-methods-in-deep-learning/).\n",
"\n",
"#### Нормализация весов\n",
"\n",
"Простая, но рабочая альтернатива пакетной нормализации называется [нормализацией весов](https://arxiv.org/pdf/1602.07868.pdf) (weight normalization). Она предлагает представить каждый вектор весов $w$ в виде $w = g \\frac{v}{\\Vert v \\Vert}$, где $g$ — скаляр, а $v$ — вектор той же длины, что и $w$. Очевидно, любой ненулевой вектор можно представить в таком виде. При выполнении градиентного спуска все частные производные теперь будет считаться не относительно $w$, а относительно $g$ и $v$. Таким образом, нормализация весов сводится к перепараметризации нейронной сети, когда вместо одних обучаемых параметров используются другие, но, по сути, сеть остаётся той же самой. Утверждается, что сходимость обучения при этом улучшается.\n",
"\n",
"Нормализация весов в первую очередь оказывает эффект на дисперсию выходных значений. Чтобы лучше управлять ещё и средним, нормализацию весов можно совместить с урезанной версией пакетной нормализации, затрагивающей только среднее, но не трограющей среднеквадратичные отклонения (т.е. в ней есть $\\beta$, $\\mu_\\mathrm{batch}$ и $\\mu_\\mathrm{cum}$, но отсутствуют $\\gamma$, $\\sigma_\\mathrm{batch}$ и $\\sigma_\\mathrm{cum}$). \n",
"\n",
"#### Послойная нормализация\n",
"\n",
"Ещё одной простой и в то же время эффективной и совместимой с рекуррентными сетями альтернативой является [послойная нормализация](https://arxiv.org/pdf/1607.06450.pdf) (layer normalization). Её идея заключается в том, что вычисление среднего и среднеквадратичного отклонения делаются для каждого объекта по отдельности. Раз так, то больше нельзя вычислять эти статистики ни на всей выборке (как в не связанной с нейронными сетями классической нормализации), ни даже на одном пакете. Множеством, по которому вычисляются эти статистики, становится множество всех нейронов слоя, и именно поэтому эта нормализация называется послойной.\n",
"\n",
"Объяснение, почему это может работать, дано в оригинальной статье. Отдельно стоит обратить внимание на то, что послойная нормализация в отличие от пакетной нормализации и нормализации весов не сводится к перепараметризации и потому она может изменить выразительную силу нейронной сети.\n",
"\n",
"От послойной нормализации происходят применяемые в задачах, связанных с изображениями, так называемые [«нормализация инстанса»](https://arxiv.org/pdf/1607.08022.pdf) и [«групповая нормализация»](https://arxiv.org/pdf/1803.08494.pdf). В первой из них усреднение делается не по слою, а по слою и каналу изображения, а во второй — по слою и группе каналов изображения."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"изображения",
"естественные_языки"
]
},
"source": [
"## Субдискретизация\n",
"\n",
"В свёрточных нейронных сетях часто используют слой, в котором фильтр (filter, kernel) проходит по входу с некоторым шагом (stride) и каждый раз от всего, что попадает в него, берёт значение некоторой агрегирующей функции, становящееся значением в соответствующем выходном юните. В англоязычной литературе этот слой называют \"pooling\", а в русскоязычной литературе принято название «субдискретизация», хотя оно не совсем точное. В цифровой обработке сигналов субдискретизацией (subsampling, downsampling) называют снижение частоты дискретизации (sample rate, frame rate), но с такой точки зрения субдискретизацией является и свёртка (convolution) с шагом, большим 1. Более того, если в слое так называемой субдискретизации шаг равен 1 и используется режим работы с граничными значениями, за которым благодаря MATLAB'у укоренилось название \"same\", то ни частота дискретизации, ни даже размерность не изменятся.\n",
"\n",
"В качестве агрегирующей функции можно взять максимум — тогда речь пойдёт о субдискретизации максимумом (max pooling). Её часто используют для задач, связанных с изображениями, потому что она придаёт следующие свойства:\n",
"* устойчивость к сдвигам изображения на небольшое количество пикселей;\n",
"* возможность реализовать следующую логику: присутствие детектируемого объекта на объединении участков зависит от того, присутствует ли объект хотя бы на одном из этих участков, а не от доли участков, на которых он присутствует.\n",
"\n",
"В то же время, не всегда субдискретизация максимумом уместна. Если стоит задача обвести на изображении интересующую часть (а не просто ответить, есть ли интересующий объект или нет), несколько слоёв субдискретизации максимумом могут соединить слишком много пикселей в область, внутри которой предсказания будут одинаковыми.\n",
"\n",
"Для анализа же текстов порой используют так называемый максимум во времени (max over time pooling). Агрегирующей функцией по-прежнему является максимум, но фильтр одномерный и в длину имеет размер всего объекта (текста или предложения).\n",
"\n",
"Предыдущий абзац показывает, что размер фильтра может быть переменным. При работе с изображениями это можно использовать, чтобы заложить поддержку картинок разного размера: достаточно сделать фильтр выраженным в относительных значениях. Например, всё изображение разбивается на $l \\times m$ меньших изображений, к каждому из которых применяется агрегирующая функция, и, каким бы ни был размер исходного изображения, после субдискретизации размер будет $l \\times m$.\n",
"\n",
"Также субдискретизация может увеличивать количество измерений в слое. Происходит это, если агрегирующая функция возвращает не одно значение, а несколько. Например, K-max pooling предполагает взятие K наибольших значений."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"методы_оптимизации"
]
},
"source": [
"## Методы подбора темпа обучения в нейронных сетях\n",
"\n",
"#### Введение\n",
"\n",
"В классическом варианте градиентного спуска темп обучения не является гибким сразу с двух точек зрения:\n",
"* он один и тот же для всех настраиваемых параметров;\n",
"* он меняется от шага к шагу по заранее заданному расписанию (или вообще не меняется).\n",
"\n",
"Исторически одним из первых методов, где появилась адаптивность в двух вышеперечисленных аспектах, был AdaGrad, но у него был важный недостаток: темп обучения монотонно не возрастал и мог преждевременно стать слишком маленьким. Метод, отличающийся от AdaGrad только исправлением этой особенности, получил название RMSProp. А метод, в полном виде называющийся Adaptive Moment Estimation и обычно сокращённо называемый Adam, считается дальнейшим развитием адаптивного управления темпом обучения.\n",
"\n",
"#### RMSProp (и AdaGrad)\n",
"\n",
"Метод RMSProp имеет три гиперпараметра:\n",
"* $\\eta$ — положительное вещественное число, задающее относительную скорость обучения (все подбираемые темпы обучения содержат его как множитель);\n",
"* $\\beta$ — число от 0 до 1, отвечающее за сглаживание/угасание накопленного второго момента градиентов;\n",
"* $\\varepsilon$ — малое положительное число, введённое ради численной стабильности.\n",
"\n",
"Перед каждым шагом обновления обучаемых параметров сначала обновляется внутренний параметр метода RMSProp $v_t$, интерпретируемый как накопленная сумма градиентов, поэлементно возведённых в квадрат. Начальное значение этого параметра $v_0$ равно вектору из одних нулей той же длины, что и вектор $\\theta$ обучаемых параметров. На $t$-м шаге обучения обновление $v_t$ делается по формуле:\n",
"$$v_t = \\beta v_{t-1} + (1 - \\beta) g^2_t,$$\n",
"где $g_t$ — градиент функции потерь по параметрам $\\theta$, получившийся на $t$-м шаге до обновления этих параметров (т.е. при $\\theta = \\theta_{t-1}$), а в квадрат он возводится поэлементно. Экспоненциальное сглаживание в этой формуле позволяет $v_t$ не только расти, но и падать. Если бы гиперпараметра $\\beta$ не было бы, а формула обновления имела бы вид:\n",
"$$v_t = v_{t-1} + g^2_t,$$\n",
"то получился бы метод AdaGrad.\n",
"\n",
"После обновления $v_t$ проводится обновление обучаемых параметров:\n",
"$$\\theta_{t} = \\theta_{t-1} - \\frac{\\eta}{\\sqrt{v_t} + \\varepsilon} \\circ g_t,$$\n",
"где $\\circ$ — адамарово произведение (поэлементное умножение), корень из $v_t$ извлекается поэлементно, а операции со скалярами $\\eta$ и $\\varepsilon$ тоже применяются к компонентам вектора поэлементно.\n",
"\n",
"По сравнению с градиентным спуском с фиксированным темпом обучения $\\eta$, где обновления устроены как\n",
"$$\\theta_{t} = \\theta_{t-1} -\\eta g_t,$$\n",
"RMSProp больше внимания уделяет тем параметрам, частные производные функции потерь по которым получаются небольшими.\n",
"\n",
"#### Adam\n",
"\n",
"Метод Adam имеет четыре гиперпараметра:\n",
"* $\\eta$ — положительное вещественное число, задающее относительную скорость обучения (все адаптивно подобранные темпы обучения содержат его как множитель);\n",
"* $\\beta_1$ — число от 0 до 1, отвечающее за сглаживание/угасание накопленного среднего градиентов;\n",
"* $\\beta_2$ — число от 0 до 1, отвечающее за сглаживание/угасание накопленного второго момента градиентов;\n",
"* $\\varepsilon$— малое положительное число, введённое ради численной стабильности.\n",
"\n",
"Как можно было догадаться по списку гиперпараметров, в отличие от RMSProp у метода Adam есть два внутренних параметра, а не один. Они обозначаются как $m_t$ и $v_t$ и имеют начальные значения $m_0$ и $v_0$, равные вектору из одних нулей той же длины, что и вектор $\\theta$. Перед обновлением весов на $t$-м шаге они обновляются по формулам:\n",
"$$m_t = \\beta_1 m_{t-1} + (1 - \\beta_1) g_t,$$\n",
"$$v_t = \\beta_2 v_{t-1} + (1 - \\beta_2) g^2_t,$$\n",
"где, как и ранее, $g_t$ — градиент функции потерь по параметрам $\\theta$, получившийся на $t$-м шаге при $\\theta = \\theta_{t-1}$, а в квадрат он возводится поэлементно. Что касается формулы для $m_t$, экспоненциальное сглаживание в ней можно сравнить с инерцией, но только это уже инерция градиентов, а не инерция обновлений весов, часто используемая при обучении нейронных сетей. Что же касается формулы для $v_t$, в ней экспоненциальное сглаживание нужно в первую очередь ради того, чтобы накопленная сумма квадратов градиентов со временем могла и падать, а не только расти. Устойчивость траектории для $v_t$ не играет первостепенной роли.\n",
"\n",
"Можно заметить, что значения $m_t$ и $v_t$ при малых $t$ будут смещены в сторону нуля. Чтобы исправить это, вводят следующие скорректированные величины:\n",
"$$\\hat{m_t} = \\frac{m_t}{1 - \\beta_1^t},$$\n",
"$$\\hat{v_t} = \\frac{v_t}{1 - \\beta_2^t}.$$\n",
"\n",
"Формула обновления весов методом Adam принимает вид:\n",
"$$\\theta_{t} = \\theta_{t-1} - \\frac{\\eta}{\\sqrt{\\hat{v_t}} + \\varepsilon}\\hat{m_t}.$$\n",
"Таким образом, Adam отличается от RMSProp двумя доработками: введением инерции градиентов и коррекцией накопленных моментов для начальных шагов.\n",
"\n",
"#### Сравнение с классическим и стохастическим градиентным спуском\n",
"\n",
"Как правило, адаптивность лучше её отсутствия. Однако в статье [Wilson et al., 2017](https://arxiv.org/abs/1705.08292) показывается, что иногда нейронные сети, обученные адаптивными методами, проигрывают нейронным сетям, обученным классическим градиентным спуском или стохастическим градиентным спуском.\n",
"\n",
"Причины этого можно увидеть в том, что задача машинного обучения не сводится к задаче оптимизации, ведь значение функции потерь на обучающей выборке менее важно, чем на тестовой. Интуитивно говоря, области пространства аргументов, где значения оптимизируемой функции близки к экстремуму, бывают «узкими» (вытянутыми вдоль небольшого числа направлений) и «широкими» (имеющими примерно равные габариты по всем направлениям). Считается, что адаптивные методы чаще приводят в экстремумы с «узкими» областями, а у решений из них обобщающая способность ниже.\n",
"\n",
"Другой взгляд на этот неожиданный результат заключается в том, что методы наподобие AdaGrad, RMSProp или Adam предназначены для ускорения обучения, а не для улучшения качества обученной нейронной сети. Грубо говоря, они позволяют начать с высокого темпа обучения, чтобы побыстрее пройти начальную стадию.\n",
"\n",
"Так или иначе, если данных мало, то стоит попробовать не только Adam, но и обычный градиентный спуск."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети"
]
},
"source": [
"## Инициализация весов в нейронных сетях\n",
"\n",
"#### Введение\n",
"\n",
"Есть две основных проблемы, к которым может привести неправильная инициализация весов:\n",
"* сокращение уникального количества юнитов из-за эффекта симметрии,\n",
"* нестабильные градиенты (вплоть до значений NaN).\n",
"\n",
"Наиболее выраженно первая проблема проявляется, если все веса инициализировать одной и той же константой. Тогда любые два юнита одного и того же слоя будут обучаться на одних и тех же градиентах, то есть всегда будут иметь одни и те же значения, и, таким образом, можно будет считать, что в каждом слое есть ровно один юнит. Точнее, чтобы это произошло, также необходимо, чтобы асимметрия между юнитами не вносилась в процессе обучения (например, из-за [дропаута](__home_url__/notes/Дропаут)) и не была изначально заложена в архитектуре (например, из-за отсутствия части связей между слоями). Но даже если симметрия где-то нарушается, всё равно хорошо бы, чтобы при инициализации весов симметрии не было и, тем самым, выше бы были шансы на то, что благодаря разнообразию среди юнитов нейронная сеть в полной мере раскроет свою выразительную силу. \n",
"\n",
"Вторая проблема проявляется, если начальные значения весов оказываются слишком большими по модулю.\n",
"\n",
"Чтобы избежать обоих проблем, существует следующее эвристическое правило: перед началом обучения все веса должны быть разными и малыми по модулю. Отсюда проистекает один из простых способов инициализации весов: породить каждый из них независимо из гауссовского распределения с нулевым средним и дисперсией 0,01 (или ещё меньше, если всё равно вторая проблема останется). От этого базового решения можно пойти по двум направлениям, каждое из которых сконцентрировано на ещё более надёжном предотвращении одной из двух основных проблем. \n",
"\n",
"#### Ортогональная инициализация\n",
"\n",
"Рассмотрим слой, который получает на вход значения $m$ юнитов предыдущего слоя в виде вектора-столбца $x$ размера $m \\times 1$ и возвращает $f(Wx + b)$, где $W$ — матрица весов размера $k \\times m$, $k$ — количество юнитов в этом слое, $b$ — вектор-столбец свободных членов размера $k \\times 1$, а $f$ — поэлементная функция активации.\n",
"\n",
"Для начала, как и в базовом решении, сгенирируем матрицу $V$ размера $k \\times m$, независимо просэмплировав её элементы из гауссовского распределения с нулевым средним и дисперсией 0,01. Асимметрию между юнитами будем понимать как асимметрию между строками матрицы $W$, а две строки будем считать максимально непохожими друг на друга, если они ортогональны. Попарная ортогональность всех $k$ строк друг другу возможна, только если $k \\le m$. Предположим, что это так. Для квадратных матриц известна процедура Грама-Шмидта, приводящая к QR-разложению. Для неквадратных матриц есть её [обобщение](https://en.wikipedia.org/wiki/QR_decomposition#Rectangular_matrix), благодаря которому матрицу $V$ можно представить в виде:\n",
"$$V = RQ,$$\n",
"где $R$ — нижнетреугольная матрица размера $k \\times k$, а $Q$ — матрица размера $k \\times m$ с ортогональными строками. Если что, матрицы $R$ и $Q$ стоят в таком порядке (а не $Q$ и $R$) и матрица $R$ нижнетреугольная, а не верхнетреугольная, потому что для случая $k \\le m$ нужно транспонирование QR-разложения. Так вот, в качестве начального значения матрицы $W$ и берётся матрица $Q$.\n",
"\n",
"Если же $k > m$, матрицу $W$ можно инициализировать матрицей с ортогональными столбцами из QR-разложения. Хотя это и не то, что нужно с теоретической точки зрения, так сделано, например, в [tensorflow](https://www.tensorflow.org/api_docs/python/tf/keras/initializers/Orthogonal). \n",
"\n",
"#### Стремление к единичной дисперсии\n",
"\n",
"Поскольку то, что подаётся во входной слой, можно отмасштабировать, без ограничения общности можно предположить, что у каждого входа нейронной сети единичная дисперсия. Хочется, чтобы и для последующих слоёв это свойство сохранялось. Исходя из этих соображений были придуманы различные варианты инициализации весов, приближающие к желаемому свойству слои с различными функциями активации.\n",
"\n",
"Как и в базовом решении, веса можно порождать из нормального распределения с нулевым средним, но дисперсия теперь будет равна:\n",
"* $1 / m$ - тут логика такая: раз юнит имеет $m$ входов, то поделим на $m$; считается, что это работает для $\\tanh$;\n",
"* $2 / (k + m)$ — Glorot Normal Initialization; её логика: при прямом проходе входов $m$, но при обратном проходе входов $k$, значит делить надо на их среднее арифметрическое; считается, что работает с $\\sigma$ и $\\tanh$;\n",
"* $2 / ((1 + \\alpha^2)m)$, где $\\alpha$ — угол наклона отрицательной части для LReLU и PReLU и 0 для ReLU — He Normal Initialization; предназначена для ReLU-подобных функций активации.\n",
"\n",
"Также веса можно сэмплировать из равномерного распределения на отрезке $[-a, a]$, где $a$ равно:\n",
"* $\\sqrt{3 / m}$ — LeCun Uniform Initialization,\n",
"* $\\sqrt{6 / (k + m)}$ — Glorot Uniform Initialization.\n",
"\n",
"Наконец, одно время для получения адекватных начальных значений весов использовалось жадное послойное предобучение с дополнением до автокодировщика.\n",
"\n",
"#### Инициализация свободных членов\n",
"\n",
"При условии, что веса $W$ инициализированы приемлемым образом, свободные члены $b$ можно инициализировать константами (даже нулями) или небольшими случайными числами. Особой роли этот выбор играть не будет, хотя при желании можно найти исключения. Например, для ReLU всё-таки лучше, чтобы свободный член был чуть больше 0, чтобы снизить шансы на то, что нейрон придёт в нерабочее состояние."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"последовательности"
]
},
"source": [
"## Внутреннее устройство LSTM-юнита\n",
"\n",
"#### Что означает LSTM?\n",
"\n",
"Аббревиатура LSTM расшифровывается как Long Short-Term Memory (краткосрочная память произвольной длины). Она входит в название специального составного «нейрона»/юнита, то есть «нейрона», имеющего внутреннюю структуру. По-русски его ещё называют LSTM-модулем, а по-английски он называется LSTM cell, LSTM unit или LSTM neuron. Этот юнит предназначен для задач, где объекты образуют последовательность, причём влияние некоторого объекта может распространяться на целевые переменные объектов, стоящих впереди него на произвольном расстоянии.\n",
"\n",
"#### Содержимое LSTM-юнита\n",
"\n",
"Для каждого индекса $t$, которым нумеруются позиции последовательности, с LSTM-юнитом ассоциированы следующие сущности:\n",
"* входы и выходы:\n",
" - вектор входов $x_t$, берущийся из последовательности и имеющий длину $d$,\n",
" - вектор возвращаемых юнитом выходов $y_t$, имеющий длину $h$;\n",
"* внутреннее состояние:\n",
" - вектор \"памяти\" $c_t$ той же длины $h$, что и вектор выходов;\n",
"* три вектора, называемых вентилями и имеющих ту же длину $h$, что и выход:\n",
" - входной вентиль (input gate), $i_t$,\n",
" - вентиль забвения (forget gate), $f_t$,\n",
" - выходной вентиль (output gate), $o_t$;\n",
"* восемь матриц весов и четыре векторных свободных члена:\n",
" - $W_i$, $W_f$, $W_o$, $W_c$, их размер $h \\times d$,\n",
" - $U_i$, $U_f$, $U_o$, $U_c$, их размер $h \\times h$,\n",
" - $b_i$, $b_f$, $b_o$, $b_c$, их длина $h$.\n",
" \n",
"Когда нейронная сеть уже обучена, последние двенадцать сущностей не меняются от шага к шагу, и именно поэтому индекс $t$ у них отсутствует.\n",
"\n",
"#### Динамика при движении по последовательности\n",
"\n",
"Начальные условия в позиции $t = 0$, предшествующей началу последовательности, задаются так:\n",
"* $c_0 = 0$, $y_0 = 0$,\n",
"* веса матриц и свободных членов как-то инициализированы, если происходит обучение, или уже обучены и зафиксированы, если речь идёт о применении,\n",
"* чему равны вентили, неважно.\n",
"\n",
"При заданной последовательности $x_t$ для любой позиции $t \\ge 1$ можно рекуррентно определить значения всех сущностей, ассоциированных с LSTM-юнитом, по формулам:\n",
"$$i_t = \\sigma(W_i x_t + U_i y_{t-1} + b_i),$$\n",
"$$f_t = \\sigma(W_f x_t + U_f y_{t-1} + b_f),$$\n",
"$$o_t = \\sigma(W_o x_t + U_o y_{t-1} + b_o),$$\n",
"$$c_t = f_t \\circ c_{t-1} + i_t \\circ \\tanh (W_c x_t + U_c y_{t-1} + b_c),$$\n",
"$$y_t = o_t \\circ \\tanh (c_t),$$\n",
"где $\\sigma$ — [сигмоидная функция активации](__home_url__/notes/Функции активации для нейронных сетей), $\\tanh$ — гиперболический тангенс, а $\\circ$ — операция взятия адамарова произведения (поэлементное умножение).\n",
"\n",
"На самом деле, выше выписан классический вариант. Вместо сигмоиды и гиперболического тангенса можно использовать и иные функции активации. Например, если целевая переменная вещественная и выходит за пределы интервала $(0; 1)$, то менять функции активации непременно надо.\n",
"\n",
"#### Интерпретация\n",
"\n",
"Почему данная конструкция, после обучения являющаяся некоторой динамической системой в дискретном времени, осмысленна?\n",
"\n",
"Можно считать, что LSTM-юнит в зависимости от значений вентилей способен демонстрировать различные режимы поведения (ниже 0 и 1 обозначают векторы из одних 0 или 1 соответственно):\n",
"* при $f_t = 0$, $i_t = o_t = 1$ получается обычный рекуррентный нейрон (нейрон Элмана);\n",
"* при $o_t = 0$, $i_t = f_t = 1$ происходит накопление входной информации (например, нейрон может работать счётчиком), а на выход информация не отдаётся;\n",
"* при $i_t = o_t = 0$, $f_t = 1$ происходит хранение того, что в памяти, без изменений;\n",
"* при $i_t = 0$, $f_t = o_t = 1$ происходит извлечение наружу информации, накопившейся в памяти;\n",
"* при $i_t = f_t = 0$ происходит сбрасывание памяти.\n",
"\n",
"Таким образом, LSTM-юнит обладает способностями к гибкому управлению памятью и способен проводить над ней все операции, кажущиеся необходимыми. Если данных много, то нейронная сеть с такими нейронами сможет выучить устойчивые закономерности даже в случае отсутствия ограничения максимальной дальности влияния входов на выходы.\n",
"\n",
"#### Обучение\n",
"\n",
"Обучение LSTM-юнита производится методом, по-английски называемым Truncated Back-Propagation Through Time, где первое слово обозначает, что в вычислениях следующие частные производные полагаются равными нулю:\n",
"$$\\frac{\\partial i_t}{\\partial y_{t-1}} = \\frac{\\partial f_t}{\\partial y_{t-1}} = \\frac{\\partial o_t}{\\partial y_{t-1}} = \\frac{\\partial c_t}{\\partial y_{t-1}} = 0.$$\n",
"\n",
"#### Модификации\n",
"\n",
"Помимо классического LSTM-юнита, описанного выше, существует версия, называемая LSTM с глазками (peepholes). Её отличие в том, что вентили могут обращаться к памяти нейрона (подглядывать в неё через глазки). Вводятся ещё три матрицы размера $h \\times h$, обозначаемые как $V_i$, $V_f$ и $V_o$. В рекуррентных соотношениях, задающих динамику при движении по последовательности, последние два равенства остаются неизменными, а первые три принимают вид:\n",
"$$i_t = \\sigma(W_i x_t + U_i y_{t-1} + V_i c_{t-1} + b_i),$$\n",
"$$f_t = \\sigma(W_f x_t + U_f y_{t-1} + V_f c_{t-1} + b_f),$$\n",
"$$o_t = \\sigma(W_o x_t + U_o y_{t-1} + V_o c_{t} + b_o).$$\n",
"В последнем из соотношений используется $c_t$, а не $c_{t-1}$, потому что на момент обновления значения выходного вентиля значение памяти на текущем шаге уже известно.\n",
"\n",
"Есть и версия LSTM с глазками, где матриц $U_i$, $U_f$, $U_o$ и $U_c$ нет (т.е. можно считать, что они тождественно нулевые)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети"
]
},
"source": [
"## Многозадачное обучение (multi-task learning)\n",
"\n",
"Допустим, есть вспомогательная задача, для которой имеется много размеченных данных, и есть основная задача, для которой размеченных данных существенно меньше. Также допустим, что эти две задачи работают с одними и теми же объектами, но предсказывают на них разные целевые переменные. Например, во вспомогательной задаче нужно определить пол человека с портретного фото, а в основной задаче требуется определить цвет волос.\n",
"\n",
"В описанной ситуации можно поступить следующим образом. Построим нейронную сеть для решения вспомогательной задачи и обучим её. Затем уберём сколько-то последних слоёв получившейся сети, и вместо них поставим новые, такие что размерность выходного слоя уже соответствует основной задаче.\n",
"\n",
"Далее есть два варианта:\n",
"\n",
"1. Зафиксировать веса оставленных слоёв нейронной сети, обученной под вспомогательную задачу, и просто прогонять объекты через оставленные слои как через статичный предобработчик;\n",
"\n",
"2. Веса оставшихся от вспомогательной задачи слоёв обучать наравне с весами новых слоёв, то есть считать, что они просто были инициализированы по-другому, но больше отличий между ними и весами новых слоёв нет.\n",
"\n",
"Какой из вариантов выбрать, зависит от числа данных в основной задаче. Если острого недостатка в них нет, то второй способ, как правило, даёт более высокий результат. Первый способ, однако, быстрее, и также он менее требователен к количеству данных (а если размеченных данных совсем мало, то можно даже использовать результат прогона через оставленные обученные слои в качестве признаков для более простого метода: например, метода ближайших соседей).\n",
"\n",
"Новая нейронная сеть обучится лучше, чем если бы сеть с такой же архитектурой обучалась на данных для основной задачи с нуля. Дело в том, что при описанном подходе нейронная сеть будет опираться на скрытое представление, выученное по большому количеству размеченных данных оставленными слоями старой нейронной сети. Также подстройка весов под разные задачи способствует увеличению обобщающей способности. Подробности о том, почему многозадачное обучение работает, есть в разделе 3 статьи [Ruder, 2017](https://arxiv.org/pdf/1706.05098.pdf).\n",
"\n",
"Ещё один подход к многозадачному обучению таков: обучать нейронную сеть параллельно то под вспомогательную задачу, то под основную, при каждом переключении задачи оставляя сколько-то первых слоёв, но заменяя последние слои на то, что было ранее в задаче, к которой происходит переход."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети"
]
},
"source": [
"## Автокодировщики с большей размерностью скрытого слоя\n",
"\n",
"Рассмотрим автокодировщик (autoencoder) со входным слоем размерности $l$, одним скрытым слоем размерности $h$ и выходным слоем, размерность которого по определению должна быть равна размерности входного слоя, то есть $l$. Вопрос: могут ли для чего-то пригодиться автокодировщики, где $h > l$?\n",
"\n",
"Без дополнительных модификаций такие автокодировщики не смогут обучаться чему-то нетривиальному, потому что всегда есть вырожденное решение: использовать лишь $l$ нейронов из $h$, чтобы просто передать вход в неизменном виде.\n",
"\n",
"Есть следующие способы заставить скрытый слой выучивать нетривиальное представление:\n",
"* К ошибке восстановления, на входном векторе $x$ равной $\\Vert x - \\mathrm{autoencoder}(x)\\Vert_2$, добавить регуляризатор, подталкивающий к разреженности скрытого слоя: например, $L_1$-норму $h$-мерного вектора, получающегося из $x$ в скрытом слое;\n",
"* Ко входу подмешивать шум, но при вычислении ошибки восстановления требовать близости к незашумлённому входу, то есть минимизировать математическое ожидание функции, на входном векторе $x$ равной $\\Vert x - \\mathrm{autoencoder}(x + \\varepsilon)\\Vert_2$, где $\\varepsilon$ — шум.\n",
"* Каждую из компонент вектора входов с некоторой вероятностью $p$ обнулять, но при вычислении ошибки восстановления сверяться с вектором входов, где все компоненты имеют исходный вид — так автокодировщик будет побуждён выучивать взаимосвязи между признаками, позволяющие по части признаков восстановить остальные признаки. \n",
"\n",
"Полученный автокодировщик можно использовать в следующих целях:\n",
"* То, что получается в скрытом слое, можно брать в качестве признакового описания объекта; такие признаки могут содержать в себе более сложные взаимодействия, чем признаки, даваемые автокодировщиком с низким $h$; пригождается это в частичном обучении (semi-supervised learning), ведь объекты без меток тоже влияют на выучиваемый способ порождать признаки;\n",
"* До появлении [пакетной нормализации](__home_url__/notes/Нормализация в нейронных сетях) и остаточного обучения была популярна \"жадная\" (послойная от входов к выходам) инициализация весов глубокой однонаправленной нейронной сети, при которой инициализируемый на данный момент слой дополнялся до автокодировщика и обучался задаче автокодировщика, где кодировалось то, что подавал на вход предыдущий слой, — стало быть, если в каком-то месте ширина нейронной сети возрастала, то требовалось обучать автокодировщик, у которого $h > l$."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"естественные_языки",
"векторные_вложения"
]
},
"source": [
"## На пути к word2vec\n",
"\n",
"Помимо word2vec есть некоторые более простые способы отобразить слово в непрерывный вектор.\n",
"\n",
"#### Вложение на базе разбивки по коллекциям слов\n",
"\n",
"* Построим матрицу, где строкам соответствуют слова, столбцам — некоторые коллекции слов (например, документы или предложения), а на пересечении строки и столбца может стоять:\n",
" - бинарный индикатор вхождения слова в коллекцию;\n",
" - количество вхождений слова в коллекцию;\n",
" - TF-IDF;\n",
" - BM-25.\n",
"* Применим к получившейся матрице какую-либо процедуру снижения размерности, такую как:\n",
" - метод главных компонент, PCA;\n",
" - многомерное шкалирование, MDS;\n",
" - вложение на базе случайного соседства, t-SNE.\n",
"* Примем за векторное представление некоторого слова соответствующую этому слову строку матрицы со сниженной размерностью. Интерпретировать подобную строку можно как вектор с весами [скрытых тем](__home_url__/tags/тематическое_моделирование).\n",
"\n",
"#### Вложение через переходные вероятности\n",
"\n",
"* Пронумеруем все слова.\n",
"* Возьмём матрицу размера $\\vert V \\vert \\times \\vert V \\vert$, где $\\vert V \\vert$ — количество слов, на пересечении $i$-й строки и $j$-го столбца которой стоит вероятность того, что сразу же после $i$-го слова в тексте встретится $j$-е слово. Казалось бы, вложением $i$-го слова можно считать $i$-ю строку такой матрицы или $i$-й столбец такой матрицы, однако у столь простого подхода есть два недостатка:\n",
" - большое количество оцениваемых по данным параметров, а именно $\\vert V \\vert^2$ элементов матрицы переходных вероятностей;\n",
" - размерность вектора вложения такая же, как у вектора, получаемого через one-hot encoding;\n",
" - подобное представление не очень информативно, хотя и более информативно, чем представление, получаемое через one-hot encoding.\n",
"* Попробуем получить более разумное вложение за счёт большей компактности представления. Предположим, что для некоторого фиксированного $d < \\vert V \\vert$ откуда-то даны две матрицы $W_1$ и $W_2$ размеров $d \\times \\vert V \\vert$ и $\\vert V \\vert \\times d$ соответственно, такие что матрицу переходных вероятностей удалось приблизить матрицей $W_2 W_1$. Последнее предположение формализуется и уточняется так: $\\forall i, i \\in \\{1, ..., \\vert V \\vert\\}$, после применения операции softmax к $\\vert V \\vert \\times 1$ вектору-столбцу $W_2 W_1 x_i$, где $x_i$ — вектор-столбец размера $\\vert V \\vert \\times 1$, такой что его $i$-я компонента равна 1, а остальные равны 0 (т.е. $x_i$ — one-hot представление $i$-го слова), получается вектор, близкий к вектору переходных вероятностей из $i$-го слова. В таком случае вложением слова в векторное пространство можно считать что угодно из этого списка:\n",
" - $i$-й столбец матрицы $W_1$;\n",
" - $i$-ю строку матрицы $W_2$;\n",
" - сумму или полусумму $i$-го столбца матрицы $W_1$ и транспонированной $i$-й строки матрицы $W_2$ (обычно так делают для GloVe, а не для word2vec);\n",
" - конкатенацию $i$-го столбца матрицы $W_1$ и транспонированной $i$-й строки матрицы $W_2$.\n",
"\n",
"Описанный в предыдущем пункте подход имеет следующие преимущества:\n",
"* всего $2 d \\vert V \\vert$ обучаемых параметров;\n",
"* размерность вектора вложения можно сделать маленькой;\n",
"* получаются более информативные векторные представления, поскольку теперь матрица переходных вероятностей размера $\\vert V \\vert \\times \\vert V \\vert$ не может быть произвольной, а должна быть сводимой к виду $W_2 W_1$ с точностью до применения операции softmax к каждому столбцу указанного произведения двух матриц.\n",
"\n",
"#### Связь word2vec с вложением через переходные вероятности\n",
"\n",
"Нейронная сеть word2vec является способом найти описанные в предыдущем разделе матрицы $W_1$ и $W_2$, и в этом способе ради ускорения обучения возникают дополнительные трюки наподобие отрицательного сэмплирования. Главное отличие в постановке задачи машинного обучения заключается в том, что в word2vec выходное слово уже не обязано идти сразу же после входного слова, а должно лишь попасть в контекст определённой ширины. \n",
"\n",
"Обозначим размер контекстного окна за $C$ (если считать, что берётся равное число слов до текущего и после него, то $C$ будет чётным). Тогда:\n",
"* в word2vec-CBoW (continuous bag of words) текущее слово предсказывается по словам, его окружающим:\n",
" - входной слой имеет размер $C \\vert V \\vert$ (для текущих слов, близких к началу или концу текста, для недостающих слов контекста на вход подаются нулевые векторы),\n",
" - в скрытом слое суммируются или усредняются $C$ произведений одной и той же матрицы $W_1$ со входными one-hot векторами, каждый из которых имеет длину $\\vert V \\vert$,\n",
" - выходной слой имеет размер $\\vert V \\vert$, а получается выход умножением слева вектора скрытого слоя на $W_2$ и применением софтмакса к произведению;\n",
"* в word2vec-SkipGram по текущему слову предсказывается, какие слова его окружают:\n",
" - входной слой имеет размер $\\vert V \\vert$,\n",
" - скрытый слой получается из входа умножением на матрицу $W_1$,\n",
" - выход имеет длину $C \\vert V \\vert$, и для этих $C$ блоков, представляющих вероятности попадания слова в какую-либо из позиций контекста входного слова, происходит умножение одной и той же матрицы $W_2$ на вектор скрытого слоя с последующим применением софтмакса (то, что во всех $C$ копиях будет одно и то же вероятностное распределение, нестрашно, ведь задача не в том, чтобы предсказать контекст, а в том, чтобы обучить вложение).\n",
"\n",
"Поскольку в SkipGram функция потерь (а именно [log loss](__home_url__/notes/Логарифмическая функция потерь и энтропия Шеннона)) вычисляется независимо для каждого из $C$ блоков, можно считать, что обучающих примеров в $C$ раз больше, чем было исходно, а вход и выход имеют длину $\\vert V \\vert$. В рамках такого [подхода к word2vec](http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/) размеры слоёв не зависят от размера контекстного окна.\n",
"\n",
"Так или иначе, есть сходство между word2vec и представлением матрицы в виде произведения двух матриц меньшего ранга. Однако по сравнению с матричными разложениями у word2vec есть два преимущества:\n",
"* разработаны приёмы, дающие существенное ускорение на этапе обучения, благодаря чему становится возможным обучение на больших объёмах реальных данных;\n",
"* поддерживается потоковое обучение, то есть уже обученную модель можно дообучить без обучения с нуля."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"естественные_языки",
"векторные_вложения"
]
},
"source": [
"## Вероятностная интерпретация word2vec\n",
"\n",
"#### Вероятностная модель\n",
"\n",
"Пусть есть выборка пар ($x_i$, $y_{i,c}$), где $i \\in \\{1, ..., L\\}$, $L$ — размер выборки, $c \\in \\{1, ..., C\\}$, $C$ — как-то заданное количество слов в контексте, $x_i$ — one-hot encoded вектор какого-то слова, а $y_{i,c}$ — one-hot encoded вектор слова, встретившегося в контексте слова $x_i$ на позиции $c$.\n",
"\n",
"Допустим, эта выборка порождена из распределения, такого что условные вероятности выхода при условии входа имеют вид $$\\mathbb{P}(y_{i,c} \\vert x_i) = \\frac{\\exp(I(x_i)^TO(y_{i,c}))}{\\sum_{v \\in V}\\exp(I(x_i)^TO(v))},$$\n",
"где $V$ — множество всех слов, а $I$ и $O$ — некоторые отображения из $\\vert V \\vert$-мерного в $d$-мерное пространство. Сделаем два наблюдения, касающихся выписанной формулы. Во-первых, в правой части применяется операция softmax. Во-вторых, поскольку все векторы $x_i$ и $y_{i,c}$ таковы, что в них на одной позиции стоит 1, а на всех остальных стоят 0, без ограничения общности можно считать, что $I$ и $O$ задаются умножением на матрицы размера $d \\times \\vert V \\vert$.\n",
"\n",
"Попытаемся найти эти матрицы, решив задачу максимизации правдоподобия имеющейся выборки:\n",
"$$\\prod_{i = 1}^L\\prod_{c = 1}^C \\mathbb{P}(y_{i,c} \\vert x_i) \\rightarrow \\max_{I, O}.$$\n",
"\n",
"Оказывается, word2vec именно эту задачу и решает. Убедимся в этом.\n",
"\n",
"Рассмотрим word2vec-SkipGram в чистом виде без каких-либо оптимизаций (не важно, что такая нейронная сеть будет крайне долго обучаться — главное, что на её примере видна общая идея). Эта word2vec-SkipGram принимает на вход one-hot encoded вектор слова, умножает его слева на $d \\times \\vert V \\vert$ матрицу $W_1$ (по сути, это операция взятия соответствующего слову столбца матрицы $W_1$) и делает результат вектором значений скрытого слоя, а этот вектор значений скрытого слоя умножает слева на $\\vert V \\vert \\times d$ матрицу $W_2$, чтобы получить вектор размера $\\vert V \\vert \\times 1$, после применения операции softmax к которому получаются вероятности попадания слов в контекст входного слова. Раз так, то отображением $I$, выучиваемым word2vec, является умножение слева на матрицу $W_1$, а отображением $O$ — умножение слева на матрицу $W_2^T$. Действительно, при таких $I$ и $O$ имеем:\n",
"$$I(x_i)^TO(y_{i,c}) = (W_1 x_i)^T W_2^T y_{i,c} = (W_2 W_1 x_i)^T y_{i,c},$$\n",
"то есть входной вектор $x_i$ преобразуется, как и ожидалось. Чтобы максимизировалось правдоподобие имеющейся выборки, обучать такую word2vec надо под задачу $\\vert V \\vert$-классовой классификации с логарифмической функцией потерь, где по $x_i$ требуется предсказать $y_{i,c}$.\n",
"\n",
"#### Две матрицы вместо одной\n",
"\n",
"Тут нелишне сделать небольшое отступление. Зададимся вопросом: почему для слова с идентификатором $j$ выучивается целых два вложения, а именно $j$-й столбец матрицы $W_1$ и $j$-я строка матрицы $W_2$? Иными словами, почему по аналогии с некоторыми автокодировщиками нельзя положить соответствующие пары весов по определению равными друг другу, чтобы при обучении они учитывались как один оптимизируемый параметр? Дело в том, что тогда word2vec получит неустранимый дефект: согласно её предсказаниям, довольно часто наиболее вероятным словом в контексте некого слова будет оно же само. И впрямь, скалярное произведение $I(x_i)^TO(x_i)$ при $I \\equiv O$ получает фору за счёт того, что его множители коллинеарны.\n",
"\n",
"Раз уж ищутся одновременно два вложения, уместно прокомментировать отличия в их интерпретации: $j$-й столбец матрицы $W_1$ задаёт значение скрытого слоя при подаче на вход $j$-го слова, а $j$-я строка матрицы $W_2$ показывает, какой вклад вносит каждая из компонент скрытого слоя в предшествующую софтмаксу неотнормированную вероятность $j$-го слова на выходе. В принципе, пользоваться можно любым из этих вложений, но чаще под вложением, получаемым при помощи word2vec, имеют в виду $j$-й столбец матрицы $W_1$.\n",
"\n",
"#### Оптимизации\n",
"\n",
"Вернёмся к основной теме заметки. Обнаруживается, что описанная выше архитектура word2vec обучается чрезвычайно медленно, так как:\n",
"* для вложения $\\vert V \\vert$ слов в $d$-мерное пространство требуется на каждом шаге обновлять $2 \\vert V \\vert d$ весов;\n",
"* на каждом объекте вычисляется softmax от вектора длины $\\vert V \\vert$.\n",
"\n",
"Для ускорения обучения, конечно, можно выкинуть сколько-то обучающих примеров с вероятностью, пропорциональной частоте входного слова, потому что и оставшегося хватит для выучивания векторных представлений слов. Но есть и два взаимоисключающих способа принципиально ускорить обучение word2vec:\n",
"* отрицательное сэмплирование (Noise Contrastive Estimation, NCE),\n",
"* иерархический софтмакс.\n",
"\n",
"#### Отрицательное сэмплирование\n",
"\n",
"Реализовать отрицательное сэмплирование можно двумя способами:\n",
"* По-прежнему рассматривается задача $\\vert V \\vert$-классовой классификации, но при обучении считаются константами все веса от входов к скрытому слою кроме весов, исходящих от текущего входного слова, и все веса от скрытого слоя к выходному слою кроме весов, ведущих к текущему выходному слову, и весов, ведущих к скольки-то другим словам. Эти другие слова сэмплируются из эмпирического распределения слов, возведённого в степень 0,75, чтобы редкие слова выбирались чаще. Число 0,75, согласно [первоисточнику](https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf), было подобрано эмпирически, причём [не исключено](https://arxiv.org/pdf/1804.04212.pdf), что для других корпусов этот гиперпараметр нужно подбирать заново. Сокращение числа обновляемых весов само по себе ускоряет обучение, но для большего эффекта операция softmax применяется только для ограничения выходного вектора на истинное $y_{i,c}$ и отрицательно просэмплированные к нему слова. \n",
"* Нейронная сеть заменяется на «двубашенную», а применяется к парам слов. Задача такой нейронной сети — по паре слов предсказать, встретились ли они в одном контекстном окне или нет. В обучающей выборке для каждого примера положительного класса, взятого из реальных текстов, при том же первом слове пары сэмплируется несколько вторых слов для создания отрицательных примеров. Первая «башня» получает one-hot encoded вектор первого слова и умножает его на $W_1$. Вторая «башня» получает one-hot encoded вектор второго слова и умножает его на $W_2^T.$ Выходы «башен» подаются на вход в скалярное произведение. А вот дальше возможны варианты:\n",
" - рассматривается задача бинарной классификации, и тогда от скалярного произведения можно взять сигмоиду и интерпретировать её выход как предсказанную вероятность положительного класса (этот вариант проще, но даёт не совсем то, что способ с замораживанием весов, ведь в нём вообще нет софтмакса);\n",
" - рассматривается задача посписочного [ранжирования](__home_url__/tags/ранжирование), где список образуют положительный пример и все просэмплированные к нему отрицательные примеры, а от получившихся для списка скалярных произведений берётся софтмакс, то есть функцией потерь становится InfoNCE, используемая и в [DSSM](__home_url__/notes/DSSM (Deep Semantic Similarity Model)), с которой у этого варианта есть сходства. \n",
" \n",
"#### Иерархический софтмакс\n",
"\n",
"Здесь идея сводится к тому, чтобы изменить вероятностную модель на близкую к ней, но требующую меньшего количества вычислений. Если для того, чтобы применением софтмакса получить из выходного слоя вероятностное распределение на словах, требовалось просуммировать $\\vert V \\vert$ слагаемых в знаменателе, то для иерархического софтмакса вычисление вероятностного распределения на словах требует лишь порядка $\\log \\vert V \\vert$ операций.\n",
"\n",
"Для этого отображение $O$ берётся таким, что областью его определения являются не one-hot encoded векторы слов, а one-hot encoded векторы узлов бинарного дерева, листьями которого являются слова. В принципе, формировать это дерево можно по-разному: например, как-то по-умному разбить слова на вложенные друг в друга темы. Однако в оригинальной статье решили поступить проще: взять структуру данных, называющуюся дерево Хаффмана. У него есть свойство, что чем чаще встречается слово, тем короче будет путь от корня до листа с этим словом. Благодаря данному свойству обучение ускоряется, и это единственная причина, по которой было выбрано дерево Хаффмана.\n",
"\n",
"После перехода к узлам бинарного дерева в вероятностную модель вносятся соответствующие правки:\n",
"$$\\mathbb{P}(y_{i,c} \\vert x_i) = \\prod_{l \\in \\mathrm{Path}(y_{i,c})} \\sigma\\!\\left(\\mathrm{Child}(l, y_{i,c}) I(x_i)^TO(l)\\right),$$\n",
"где $\\mathrm{Path}(y_{i,c})$ — путь от корня дерева (включительно) до листа, соответствующего слову $y_{i,c}$ (не включая его), $\\sigma$ — сигмоидная функция, а $\\mathrm{Child}(l, y_{i,c})$ равна 1, если в узле $l$ путь до вершины $y_{i,c}$ поворачивает направо, и -1 иначе.\n",
"\n",
"У выписанной вероятностной модели есть следующие свойства:\n",
"* Поскольку $\\sigma(t) + \\sigma(-t) = 1$, а в каждом нелистовом узле аргументы сигмоиды для поворотов налево и направо отличаются только знаком, сумма по всем листьям даст 1, как это и положено вероятностям.\n",
"* Для любого $x_i$ и любого вероятностного распределения на словах $\\tau$ найдутся $I$ и $O$, при которых оно получится. Доказать это можно рекурсивно, начав с корня поиском в глубину или ширину и для каждого узла $l$ подбирая $O(l)$ так, чтобы налево от этого узла шёл вес, равный сумме вероятностей, назначенных $\\tau$ словам, которые идут после левого поворота из узла $l$. Впрочем, это свойство ничего не даёт на практике, ведь $O$ должно быть одним и тем же для всех $x_i$, то есть подбирать его под каждый $x_i$ отдельно не выйдет.\n",
"\n",
"По сравнению с Noise Contrastive Estimation появляется то отличие, что теперь вложением слова является лишь $i$-й столбец матрицы $W_1$, потому что матрица $W_2$ применяется только к нелистовым узлам бинарного дерева, а им не соответствуют никакие слова."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"естественные_языки",
"векторные_вложения",
"нейронные_сети"
]
},
"source": [
"## Вложение по подсловам fastText\n",
"\n",
"Алгоритм fastText — способ отображать слова в векторные вложения, базирующийся на word2vec-SkipGram.\n",
"\n",
"Основным отличием от word2vec является то, что теперь обучение происходит не на словах, а на $n$-граммах из символов. Среди гиперпараметров fastText есть два, определяющие, какие именно $n$-граммы рассматриваются: их минимальная длина $n_{\\min}$ и их максимальная длина $n_{\\max}$. В [оригинальной статье](https://arxiv.org/pdf/1607.04606.pdf) знаки препинания (в том числе пробелы) игнорируются, но зато в начало каждого слова добавляется специальный символ \"<\", а в конец каждого слова добавляется специальный символ \">\". Также независимо от длины слово само оно, заключённое в угловые скобки, тоже считается рассматриваемой $n$-граммой.\n",
"\n",
"При помощи word2vec-SkipGram, обученной по $n$-грамме предсказывать $n$-граммы, встречающиеся в её контексте, каждая $n$-грамма отображается в непрерывный вектор. Вложение же слова определяется как сумма векторных вложений $n$-грамм, целиком входящих в это слово.\n",
"\n",
"По сравнению с word2vec у fastText есть следующие преимущества:\n",
"* слова, не встречавшиеся на этапе обучения, всё равно могут быть отображены в векторы;\n",
"* однокоренные слова и разные формы одного и того же слова будут отображаться в схожие векторы, даже если обучающих данных недостаточно, чтобы word2vec могла это вывести.\n",
"\n",
"Что касается недостатков fastText, то к ним можно отнести скорость обучения. Дело в том, что при хоть сколько-нибудь большом $n_{\\max}$ количество $n$-грамм будет существенно превышать количество слов в языке. Как следствие, и количество обучаемых параметров будет больше, чем у word2vec."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"естественные_языки",
"векторные_вложения"
]
},
"source": [
"## DSSM (Deep Semantic Similarity Model)\n",
"\n",
"\n",
"#### Введение\n",
"\n",
"Как и word2vec, DSSM примечательна тем, что строит векторные вложения слов в качестве побочного продукта решения некоторой задачи. С этой точки зрения основным отличием DSSM от word2vec можно назвать то, что она обучается с учителем, а не в рамках концепции predictive learning (обучение через предсказание контекста). Объектами в постановке задачи для DSSM являются пары из поискового запроса и документа, где что запрос, что документ являются каким-либо текстом. Целевая переменная содержит информацию о том, релевантен ли документ запросу. В [оригинальной статье](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/cikm2013_DSSM_fullversion.pdf) предполагалось, что целевая переменная бинарная, причём к каждому запросу брался один документ, считавшийся релевантным (например, кликнутым в выдаче по этому запросу), и также бралось сколько-то документов для отрицательных примеров (например, показанных по запросу, но не кликнутых).\n",
"\n",
"#### Формат входных данных\n",
"\n",
"Из соображений минимизации количества весов нейронной сети в качестве представления текстов (неважно, запрос это или документ) выбран мешок триграмм (переход к нему авторы статьи о DSSM назвали word hashing). Если число слов в языке измеряется сотнями тысяч, то триграмм из 30 символов меньше 30 тысяч, так что размерность входа, действительно, сокращается на порядок.\n",
"\n",
"#### Архитектура нейронной сети\n",
"\n",
"Архитектура у DSSM следующая:\n",
"- Есть несколько полносвязных слоёв, размер входа первого из которых равен количеству триграмм, а размер выхода последнего из которых равен размерности искомого векторного вложения.\n",
"- Поскольку объектами являются пары из запроса и документа, есть две копии вышеописанных полносвязных слоёв, через одну из которых прогоняется запрос, а через другую — документ. В оригинальной статье веса в этих копиях были общими (т.е. одними и теми же).\n",
"- Если обозначить за $q$ запрос, за $d$ документ, за $y_q$ получившееся вложение запроса, а за $y_d$ получившееся вложение документа, то далее эти вложения как входы подаются юниту, возвращающему вещественное число, равное косинусу угла между ними: $\\frac{y^T_q y_d}{\\|y_q\\| \\|y_d\\|}$. Обозначим его за $R(q, d)$ и будем считать, что оно оценивает степень соответствия документа запросу.\n",
"\n",
"В том, что у DSSM есть две копии слоёв (иногда их называют «башнями»), можно усмотреть параллель с word2vec, у которой две матрицы $W_1$ и $W_2$ (особенно в той реализации, где у word2vec два входа размерности $\\vert V \\vert$ каждый). Но в отличие от word2vec в DSSM веса в копиях одинаковые, потому что нет такой проблемы, что по запросу среди документов может оказаться этот же самый запрос.\n",
"\n",
"#### Обучение\n",
"\n",
"Функция потерь для DSSM вычисляется не для одного объекта, а, как и в задачах [ранжирования](__home_url__/tags/ранжирование), для группы объектов. В данном случае группу образуют положительный пример и подобранные к нему отрицательные примеры. Если обозначить за $(q, d^+)$ положительный пример, а за $D$ — множество из $d^+$ и документов из соответствующих отрицательных примеров, то на группе с примером $(q, d^+)$ значение функции потерь равно:\n",
"$$-\\log P(d^+ \\, \\vert \\, q) = -\\log \\frac{e^{\\gamma R(q, d^+)}}{\\sum_{d \\in D} e^{\\gamma R(q, d)}},$$\n",
"то есть $P(d^+ \\, \\vert \\, q)$ — предсказанная вероятность того, что для запроса $q$ документом из положительного примера является $d^+$ — полагается равной результату применения операции softmax с температурой $\\gamma$ (это гиперпараметр) к предсказанным мерам релевантности $R(q, d)$.\n",
"\n",
"Выписанная функция потерь является логарифмической функцией потерь для задачи $D$-классовой классификации, в которой вся группа считается одним объектом и из всех документов группы нужно найти один положительный, индекс которого определяет метку класса. Правда, понятие метки здесь довольно условно, ведь для любой группы можно получить любую метку, просто изменив порядок документов в ней. Однако это нисколько не страшно, ведь DSSM не предсказывает метку напрямую, а ранжирует документы. В частности, даже если у всех групп обучающей выборки будет одна и та же метка, это не выльется в переобучение, а DSSM будет способна предсказывать любые метки.\n",
"\n",
"Как известно, логарифмическая функция потерь ведёт к максимизации правдоподобия обучающей выборки. Такая интерпретация удобна, если отрицательные примеры являются настоящими отрицательными примерами (например, показанными по запросу, но не кликнутыми документами). Но на функцию потерь, используемую в DSSM, можно посмотреть и под другим углом. Эта же самая функция потерь носит название [InfoNCE](https://arxiv.org/pdf/1807.03748.pdf), где NCE расшифровывается как Noise Contrastive Estimation, а префикс Info указывает на взаимную информацию и добавлен, потому что название без него уже было занято другой функцией потерь. Предположим, что теперь ко всем запросам отрицательные примеры просэмплированы из одного и того же распределения $p_\\mathrm{proposal}$, а положительные примеры приходят из условного распределения $p_\\mathrm{true}(d \\vert q)$. Обсуждаемая функция потерь будет минимизирована при следующих значениях:\n",
"$$e^{\\gamma R(q, d)} = p_\\mathrm{true}(d \\vert q) \\prod_{d^\\prime \\in D, d^\\prime \\ne d} p_\\mathrm{proposal}(d^\\prime).$$\n",
"В функции потерь в дроби из софтмакса и числитель, и знаменатель разделим на $\\prod_{d^\\prime \\in D} p_\\mathrm{proposal}(d^\\prime)$ и получим:\n",
"$$e^{\\gamma R(q, d)} \\propto \\frac{p_\\mathrm{true}(d \\vert q)}{p_\\mathrm{proposal}(d)}.$$\n",
"Хотя это свойство должно быть только у идеальных $R(q, d)$, оно интересно тем, что показывает, что DSSM учится выбирать тот документ, у которого выше всего отношение вероятности того, что он пришёл из настоящего распределения, к вероятности того, что он пришёл из того распределения, откуда сэмплируют отрицательные примеры.\n",
"\n",
"Если в качестве $p_\\mathrm{proposal}$ взять распределение документов, являющихся положительными примерами в обучающих данных, то отрицательные примеры можно не сэмплировать заранее. Достаточно обучаться только на положительных парах из запроса и документа, к каждой паре считая отрицательными примерами все пары, где к тому же запросу берётся документ из другой пары, попавшей в тот же пакет (по-английски этот приём называют in-batch negatives). Тем самым DSSM научится рекомендовать документы, у которых выше всего отношение вероятности того, что он релевантен для текущего запроса, к безусловной вероятности того, что он релевантен."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"байесовские_методы",
"нейронные_сети",
"графические_модели",
"генеративные_модели"
]
},
"source": [
"## Вариационный автокодировщик\n",
"\n",
"#### Введение\n",
"\n",
"Говоря верхнеуровнево, вариационный автокодировщик является примером нейробайесовского метода, а именно метода, где нейронные сети в качестве инструмента встраиваются в байесовский вывод, чтобы оптимизация, нужная для байесовского вывода, проводилась над нейронными сетями теми средствами, которые разработаны для них.\n",
"\n",
"Основные отличия вариационного автокодировщика от классического автокодировщика таковы:\n",
"* И кодировщик, и декодировщик на своих выходных слоях выдают параметры вероятностных распределений;\n",
"* Между кодировщиком и декодировщиком сущестует специальная прослойка, нужная для перепараметризации;\n",
"* Обучение проводится с функцией потерь, восходящей к вариационному байесовскому выводу.\n",
"\n",
"#### Вероятностная модель\n",
"\n",
"Вариационный автокодировщик связан с вероятностной графической моделью, описываемой следующими предположениями:\n",
"* Имеются объекты, каждый из которых обладает $n$ наблюдаемыми признаками, и дана обучающая выборка в виде матрицы $X$ размера $l \\times n$, где $l$ — количество объектов;\n",
"* Имеется скрытое пространство размерности $h$ (причём с точки зрения предметной области считается, что в этом пространстве в лучшей степени проявляются какие-то важные характеристики объектов), и существует (но не дана) матрица $T$ скрытых признаков, имеющая размеры $l \\times h$;\n",
"* Имеется вектор $\\theta$, интерпретируемый как вектор неизвестных параметров вероятностной модели; забегая вперёд, отметим, что это будет вектор весов декодирующей нейронной сети;\n",
"* Все объекты являются независимыми друг от друга, причём как в смысле своих наблюдаемых признаков $X_{i\\cdot}$, так и в смысле своих скрытых признаков $T_{i\\cdot}$, благодаря чему вместо совместной условной плотности для всей выборки $p(X, T \\, \\vert \\, \\theta)$ можно рассматривать совместную условную плотность для произвольного $i$-го объекта $p(X_{i\\cdot}, T_{i\\cdot} \\, \\vert \\, \\theta) = p(x_i, t_i \\, \\vert \\, \\theta)$, где в правой части просто ввели более удобные обозначения $x_i = X_{i\\cdot}$ и $t_i = T_{i\\cdot}$;\n",
"* Скрытые признаки объекта влияют (с точки зрения графических моделей) на его наблюдаемые признаки, но не наоборот, то есть сначала порождается $t_i \\sim p(t_i)$ (тут априорное распределение $t_i$ не зависит от $\\theta$), а затем порождается $x_i \\sim p(x_i \\, \\vert \\, t_i, \\theta)$.\n",
"\n",
"Обозначим кортеж из строк матрицы $T$ и элементов вектора $\\theta$ за $Z$ и благодаря перечисленным предположениям перепишем вероятностную модель так:\n",
"$$p(X, Z) = p(\\theta) p(X, T \\, \\vert \\, \\theta) = p(\\theta) \\prod_{i=1}^l p(x_i \\, \\vert \\, t_i, \\theta) p(t_i).$$\n",
"Определение задачи статистического вывода требует явного аналитического вида для $p(X, Z)$ и, чтобы его получить, опишем каждый из сомножителей правой части:\n",
"* Предполагается, что параметры вероятностной модели (а именно веса нейронной сети) имеют атомарное распределение, $p(\\theta) = \\delta(\\theta - \\theta_0)$, где $\\delta$ — дельта-функция Дирака; введение такого ограничивающего предположения вызвано тем, что с точки зрения нейронных сетей обучаются только сами веса, но не их распределение, а с точки зрения вариационного байесовского вывода тем, что вовлечение нейронных сетей оставляет лишь более слабый аналог сопряжённости;\n",
"* Распределение $p(x_i \\, \\vert \\, t_i, \\theta)$ является распределением из заданного параметрического семейства, предсказываемым некоторой нейронной сетью, обладающей следующими свойствами:\n",
" - на вход подаётся $t_i$,\n",
" - все веса извлекаются из $\\theta$,\n",
" - на выходе получаются параметры распределения $p(x_i \\, \\vert \\, t_i, \\theta)$ (например, если считать, что речь идёт о картинках размера $d \\times d$ пикселей, каждый из которых чёрный или белый, то можно положить, что распределение $p(x_i \\, \\vert \\, t_i, \\theta)$ параметризовано $d^2$ вероятностями того, что соответствующий пиксель является чёрным),\n",
" - прочие детали архитектуры могут быть произвольными (например, размерность выходного слоя в общем случае не обязана быть равна $n$, если распределение $n$-мерных строк $x_i$ матрицы $X$ параметризовано не $n$ параметрами);\n",
"* Для вариационных автокодировщиков распределение $p(t_i)$ принято полагать стандартным нормальным распределением. Делается это, чтобы вариационный автокодировщик выучивал нетривиальные компактные представления, а не сопоставлял бы одному и тому же скрытому классу точки из совершенно разных регионов скрытого простанства, а потом запоминал бы, какому классу какие регионы приписывал.\n",
"\n",
"В рамках так описанной вероятностной модели $p(X, Z)$ можно поставить задачу статистического вывода, то есть задачу оценивания $p(Z \\, \\vert \\, X) = p(T, \\theta \\, \\vert \\, X)$. Из-за вовлечения вариационного вывода оценка будет найдена в виде $\\delta(\\theta - \\theta_0 \\, \\vert \\, X)p(T \\, \\vert \\, X)$.\n",
"\n",
"#### Использование нейронных сетей\n",
"\n",
"Когда специфицировалась вероятностная модель, уже была построена одна нейронная сеть, а именно сеть, возвращающая параметры, задающие распределение $p(x_i \\, \\vert \\, t_i, \\theta)$. Эту нейронную сеть называют декодировщиком (decoder), потому что она отображает вектор, лежащий в скрытом пространстве, в вероятностное распределение, откуда можно сэмплировать наблюдаемые признаковые описания объектов. Также её называют порождающей нейронной сетью (generative network), поскольку она позволяет порождать признаковые описания объектов.\n",
"\n",
"Вторая нейронная сеть возникает из-за поиска приближения апостериорного распределения $p(T \\, \\vert \\, X)$ в специальном классе распределений $Q$. Это класс $h$-мерных гауссовских распределений с диагональной ковариационной матрицей. Любое такое распределение $q \\in Q$ параметризуется при помощи $2h$ скаляров, а именно $h$ компонент вектора среднего $\\mu$ и $h$ диагональных элементов ковариационной матрицы $S$. Однако в вариационном автокодировщике вместо параметризации этими параметрами используется параметризация весами $\\phi$ нейронной сети, архитектура которой может быть произвольной с точностью до двух ограничений: вход нейронной сети имеет размер $n$, а её выход имеет размер $2h$, причём выход именно как среднее и диагональ ковариационной матрицы и интерпретируется. Такая нейронная сеть называется кодировщиком (encoder), потому что она отображает вектор наблюдаемых признаков объекта в вероятностное распределение вектора из скрытого пространства. Также эту нейронную сеть называют нейронной сетью вывода (inference network), потому что по её выдаче строится аппроксимация распределения $p(Z \\, \\vert \\, X)$. Далее через $q_\\phi(t_i \\, \\vert x_i)$ будем обозначать распределение $h$-мерного вектора $t_i$, являющееся гауссовским распределением со средним и диагональной ковариационной матрицей, получающимися, если кодировщику с весами $\\phi$ подать на вход $n$-мерный вектор $x_i$. \n",
"\n",
"Две описанных нейронных сети собираются в одну, являющуюся автокодировщиком, при помощи добавления между ними соединительной прослойки, осуществляющей приём перепараметризации (reparameterization trick). Данный приём позволяет так соединить кодировщик с декодировщиком, чтобы можно было вычислять производные выхода всего автокодировщика по параметрам кодировщика. По умолчанию взятие таких производных затруднено тем, что для получения входа кодировщика нужно просэплировать вектор из распределения, получаемого на базе выхода кодировщика, но в сэмпле, строго говоря, нет явной зависимости от весов кодировщика, потому что просэмплированный вектор является константой. Итак, опишем соединительную прослойку. Пусть она будет юнитом, который получает на вход весь выход кодировщика (из которого однозначно получаются вектор средних $\\mu$ и ковариационная матрица $S$) и дополнительно некоторый случайный вектор $\\nu$, просэмплированный из $h$-мерного стандартного нормального распределения. Юнит-прослойка не обучается и всегда выполняет одно и то же преобразование: возвращает $h$ компонент вектора $S\\nu + \\mu$, то есть вектора, который распределён уже по нормальному распределению со средним $\\mu$ и ковариационной матрицей $S$. Обозначим этот вектор за $V(q_\\phi(t_i \\, \\vert x_i), \\nu)$. Его компоненты подаются как входы декодировщику. Так и устроен автокодировщик, собираемый из кодировщика и декодировщика.\n",
"\n",
"Назван же получившийся автокодировщик вариационным, потому что при его обучении в функции потерь участвует вариационная регуляризация. Выглядит сама функция потерь так:\n",
"$$-\\mathrm{ELBO}(\\phi, \\theta) = \\sum_{i=1}^l \\left(-\\mathbb{E}_{\\nu \\sim \\mathcal{N}_{0, I_{h}}}[\\log p(x_i \\, \\vert \\, V(q_\\phi(t_i \\, \\vert x_i), \\nu), \\theta)] + D_{KL}(q_\\phi(t_i \\, \\vert x_i) \\Vert p(t_i)) \\right),$$\n",
"где $I_h$ — единичная матрица размера $h \\times h$. На дивергенцию Кульбака-Лейблера $D_{KL}(q_\\phi(t_i \\, \\vert x_i) \\Vert p(t_i))$ можно смотреть как на регуляризатор, а на $\\mathbb{E}_{\\nu \\sim \\mathcal{N}_{0, I_{h}}}[\\log p(x_i \\, \\vert \\, V(q_\\phi(t_i \\, \\vert x_i), \\nu), \\theta)]$ можно смотреть как на ожидаемую ошибку восстановления $x_i$ после прогона его же самого через автокодировщик, куда в юнит-прослойку подали случайный вектор $\\nu$. Точнее же, это ожидаемый логарифм правдоподобия известного $x_i$ относительно распределения, возвращаемого нейронной сетью, параметры которой равны $\\theta$, при подаче ей на вход вектора $V(q_\\phi(t_i \\, \\vert x_i), \\nu)$.\n",
"\n",
"Обучение с указанной функцией потерь возможно теми же методами, какими обычно обучаются нейронные сети, то есть, например, стохастическим градиентным спуском с какими-нибудь дополнительными приёмами по управлению темпом обучения. Результаты же получаются интересными, потому что функция потерь взята не с потолка, а является умноженной на минус один нижней вариационной оценкой (evidence lower bound, ELBO) для $\\log p(X)$. Иными словами, за этой функцией потерь стоит теория байесовского вывода в приведённой в предыдущем разделе графической модели.\n",
"\n",
"Кстати, на стохастический градиентный спуск можно посмотреть как на то, что приводит к стохастическому EM-алгоритму, являющемуся существенно более быстрым, чем детерминированный EM-алгоритм, если $l \\gg n$.\n",
"\n",
"#### Применение\n",
"\n",
"Вариационный автокодировщик можно использовать в качестве порождающей модели. Подача на вход декодировщику вектора, просэмплиованного из априорного распределения $p(t)$, то есть из $h$-мерного стандартного нормального распределения, приведёт к появлению на выходе декодировщика априорного предсказательного распределения (prior predictive distribution), откуда можно сэмплировать объекты, похожие на объекты из генеральной совокупности, породившей $X$. Подача же на вход декодировщику вектора, просэмплированного из распределения $q_\\phi(t_i \\, \\vert x_i)$, где $x_i$ как-то взят, приведёт к появлению на выходе декодировщика апостериорного предсказательного распределения (posterior predictive distribution), откуда можно сэмплировать объекты, похожие на $x_i$."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"генеративные_модели",
"изображения"
]
},
"source": [
"## Особенности архитектуры DCGAN\n",
"\n",
"Аббревиатура DCGAN расшифровывается как Deep Convolutional GAN (Generative Adversarial Network). Однако все или почти все GAN'ы, работающие с изображениями, являются глубокими и свёрточными, так что название, данное авторами, слишком размыто. Более мелкие детали отличают архитектуру DCGAN от прочих архитектур, таких как LAPGAN. Эти детали таковы:\n",
"* отсутствует [субдискретизация](__home_url__/notes/Субдискретизация) (pooling); вместо этого в дискриминаторе используются свёрточные слои с шагом (stride), равным 2 или более, а в генераторе используются свёрточные слои с дробным шагом, меньшим 1 (fractionally-strided convolution layers), также известные как транспонированные свёрточные слои (transposed convolution layers, ещё их ошибочно называют deconvolution layers, хотя они не осуществляют обратное преобразование к свёртке); никаких слоёв, кроме вышеописанных свёрточных, в DCGAN нет;\n",
"* везде в генераторе используется функция активации ReLU кроме выходного слоя, где используется гиперболический тангенс; в дискриминаторе же везде используется Leaky ReLU.\n",
"\n",
"Дополнительно можно отметить, что для обучения DCGAN применяются набравшие популярность техники, такие как:\n",
"* [пакетная нормализация](__home_url__/notes/Нормализация в нейронных сетях) (batch normalization);\n",
"* [оптимизатор Adam](__home_url__/notes/Методы подбора темпа обучения в нейронных сетях)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"последовательности"
]
},
"source": [
"## Архитектура seq2seq и механизм внимания\n",
"\n",
"#### Введение\n",
"\n",
"В задачах глубокого обучения, где объекты являются последовательностями, существуют различные варианты того, когда и как принимаются входы и отдаются выходы. В частности, возможны такие варианты:\n",
"* принимается вся входная последовательность целиком, а отдаётся одна метка, а не последовательность (пример: задача анализа тональности предложений, то есть определения того, является ли произвольное предложение положительным, отрицательным или нейтральным с точки зрения эмоционального фона);\n",
"* входная последовательность принимается элемент за элементом, и до того, как будет принят следующий входной элемент, должен быть отдан текущий элемент выходной последовательности (пример: задача онлайнового/потокового разбора предложения по частям речи);\n",
"* принимается вся входная последовательность целиком, а затем порождается выходная последовательность, причём ограничение, что длина выходной последовательности обязана быть равной длине входной последовательности, может налагаться, а может и не налагаться.\n",
"\n",
"Архитектура seq2seq применима именно к последней из этих ситуаций, где ограничения на длину выхода нет. Классическим примером задачи, подпадающей под такое описание, является машинный перевод: во-первых, чтобы перевести предложение, желательно сначала дочитать его до конца и лишь потом начинать писать предложение на другом языке, и, во-вторых, в оригинале и в переводе количество слов может не совпадать. Несовпадение длин входной и выходной последовательностей и является одной из основных причин, по которым нужны особые архитектуры вместо просто рекуррентных нейронных сетей.\n",
"\n",
"Стоит отметить, что помимо seq2seq для генерации новой последовательности по целиком известной входной последовательности могут применяться и другие архитектуры: например, [трансформеры](__home_url__/notes/Трансформер).\n",
"\n",
"#### Вероятностная интерпретация\n",
"\n",
"Вероятностная модель, стоящая за seq2seq, имеет следующий вид. Пусть $\\{x_i\\}_{i=1}^l$ — входная последовательность, $\\{y_i\\}_{i=1}^m$ — выходная последовательность, а $\\mathbb{P}\\!\\left(\\{y_i\\}_{i=1}^m \\, \\left| \\, \\{x_i\\}_{i=1}^l \\right.\\right)$ — неизвестное условное вероятностное распределение на выходных последовательностях при условии заданной входной последовательности. Общая задача сводится к отображению $\\{x_i\\}_{i=1}^l$ в $\\arg \\max_{\\{y_i\\}_{i=1}^m} \\mathbb{P}\\!\\left(\\{y_i\\}_{i=1}^m \\, \\left| \\, \\{x_i\\}_{i=1}^l \\right.\\right)$. В рамках архитектуры seq2seq вводится дополнительное предположение, что\n",
"$$\\mathbb{P}\\!\\left(\\{y_i\\}_{i=1}^m \\, \\left| \\, \\{x_i\\}_{i=1}^l \\right.\\right) \\approx \\mathbb{P}\\!\\left(\\left.\\{y_i\\}_{i=1}^m \\, \\right| \\, v \\right) \\cdot \\, \\mathbb{P}\\!\\left(v \\, \\left| \\, \\{x_i\\}_{i=1}^l \\right.\\right),$$\n",
"где $v$ — вектор фиксированного размера. Неизменность его размера важна, чтобы количество весов в нейронной сети было постоянным и заранее известным.\n",
"\n",
"В терминологии нейронных сетей сделанное предположение позволяет ввести архитектуру seq2seq, составляющими которой являются:\n",
"* кодировщик, который:\n",
" - на стадии обучения оценивает распределение $\\mathbb{P}\\!\\left(v \\, \\left| \\, \\{x_i\\}_{i=1}^l \\right.\\right)$,\n",
" - и на стадии обучения, и на стадии применения для каждой входной последовательности $\\{x_i\\}_{i=1}^l$ произвольной длины $l$ оценивает $\\hat{v} = \\arg \\max_v \\hat{\\mathbb{P}}\\!\\left(v \\, \\left| \\, \\{x_i\\}_{i=1}^l \\right.\\right)$;\n",
"* декодировщик, который:\n",
" - на стадии обучения оценивает распределение $\\mathbb{P}\\!\\left(\\left.\\{y_i\\}_{i=1}^m \\, \\right| \\, v \\right)$,\n",
" - и на стадии обучения, и на стадии применения по переданному кодировщиком значению вектора $v$ \"жадным\" образом, [лучевым поиском](__home_url__/notes/Лучевой поиск для порождения последовательностей) или ещё как-либо порождает выходную последовательность из выучиваемого или выученного распределения $\\mathbb{P}\\!\\left(\\left.\\{y_i\\}_{i=1}^m \\, \\right| \\, v \\right) \\approx \\prod_{i=0}^{m-1} \\mathbb{P}\\!\\left(y_{i+1} \\, \\left| \\, \\{y_j\\}_{j=1}^i, v \\right.\\right)$, где равенство выписано в предположении присутствия марковского свойства.\n",
" \n",
"Вектор $v$, возвращаемый кодировщиком и использующийся как начальное скрытое состояние декодировщика, можно интерпретировать как векторное представление последовательности, на которой он был получен. Например, в случае с машинным переводом кодировщик является чем-то вроде sentence2vec, а на $v$ можно смотреть как на машиночитаемый \"смысл\" переводимого предложения.\n",
" \n",
"#### Детали реализации\n",
"\n",
"Первый вопрос, возникающий в связи с деталями реализации seq2seq, звучит так: как можно обеспечить работу с переменными значениями длин $l$ и $m$? Ответ на него таков. Предполагается, что одним из элементов последовательностей может быть специальный символ \"EOS\", интерпретируемый как конец последовательности, после появления которого работа с последовательностью прекращается. Кстати, при обучении пакетным градиентным спуском можно разбивать данные на пакеты так, чтобы в одном пакете все входные последовательности имели одинаковую длину (такой приём по-английски называется bucketing) — советуют так делать не потому, что пакеты должны быть представлены прямоугольными матрицами (для этого концы более коротких последовательностей можно просто дозаполнить нулями), а потому, что считается, будто от этого увеличивается качество моделей.\n",
"\n",
"Второй важный вопрос — откуда брать $v$. Ответ на него зависит от того, какой кодировщик используется. В порядке от простого к сложному можно назвать следующие варианты:\n",
"* обычная [LSTM-сеть](__home_url__/notes/Внутреннее устройство LSTM-юнита),\n",
"* двусторонняя (bidirectional) LSTM-сеть,\n",
"* обычная или двусторонняя LSTM-сеть с механизмом внимания (о нём ниже).\n",
"\n",
"Чтобы понять, что даёт каждое из этих усложнений, начнём с самого простого варианта. В случае обычной LSTM-сети через неё прогоняется вся входная последовательность, а затем финальное скрытое состояние и становится отдаваемым значением вектора $v$. Проблема тут в том, что обычно первый элемент выходной последовательности должен во многом зависеть от первого элемента входной последовательности, но если входная последовательность достаточно длинная, то в скрытом состоянии может не остаться информации о первом элементе. Поскольку же все последующие порождаемые элементы зависят от первого, порождение плохого первого элемента может привести к плохому конечному результату. В статье [Sutskever et al., 2014](https://papers.nips.cc/paper/5346-sequence-to-sequence-learning-with-neural-networks.pdf), являющейся одной из первых статей о seq2seq, для задачи машинного перевода использовались односторонние сети, но был предложен приём, улучшающий качество старта декодировщика. Входная последовательность проходилась в обратном порядке: от конца к началу. С другой стороны, из-за этого приёма увеличивается расстояние между последним элементом входной последовательности и последним элементом выходной последовательности.\n",
"\n",
"Двусторонние сети как раз сочетают сильные стороны прохода что в прямом порядке, что в обратном. В случае seq2seq использование двусторонних сетей возможно, ведь вся входная последовательность доступна сразу же. Вектором $v$ становится конкатенация последних скрытых состояний при проходе в обе стороны.\n",
"\n",
"Описанный приём позволяет сократить потерю информации при генерации начала выходной последвательности и её конца, однако есть ведь ещё и середина. Сконкатенировать все промежуточные скрытые состояния кодировщика и назвать это вектором $v$ нельзя, ведь тогда длина $v$ будет зависеть от длины входной последовательности. Теоретически можно бы было взять все скрытие состояния кодировщика и усреднить их. Но есть идея получше: усреднить их с весами, зависящими от какого-либо контекста: например, самих же скрытых состояний кодировщика и текущего скрытого состояния декодировщика. Усреднение с такими весами и называют вниманием, интерпретируя различия в весах как то, что на одних скрытых состояниях нейронная сеть концентриуется больше, а на других меньше.\n",
"\n",
"До того, как переходить к вниманию, обсудим ещё детали реализации декодировщика. Если в его качестве брать рекуррентную нейронную сеть, то только одностороннюю, потому что выходная последовательность порождается строго от начала к концу. Информация об уже порождённых элементах в таком случае будет учитывается далее через передающееся скрытое состояние декодировщика.\n",
"\n",
"Также необходимо подчеркнуть, что при обучении декодировщика те элементы выходной последовательности, которые он порождает, на следующих шагах всегда заменяются на элементы выходной последовательности обучающего примера и используется скрытое состояние, рассчитанное по ним. Делается так, потому что иначе обучение генерировать неначальные элементы стояло бы на месте. Однако из-за этого, если декодировщик ошибётся на этапе применения и породит странный элемент, с очень высокой вероятностью остаток последовательности будет порождён некачественно. Для борьбы с этой проблемой используют приёмы наподобие word dropout.\n",
"\n",
"#### Механизм внимания\n",
"\n",
"Механизм внимания вносит следующее изменение в декодировщик: теперь что возвращаемое им выходное значение $y_i$, что его собственное скрытое состояние $d_i$ зависят ещё и от некоторого вектора контекста $c_i$, а не только от предыдущего выходного значения $y_{i-1}$ и предыдущего скрытого состояния $d_{i-1}$, как было в классической seq2seq.\n",
"\n",
"Один из вариантов определения вектора контекста $c_i$ таков:\n",
"$$c_i = \\sum_{j=1}^l \\alpha_{ij}h_j,$$\n",
"где $h_j$ — вектор скрытого состояния кодировщика после пропуска через него $j$-го элемента входной последовательности (если кодировщик является двусторонней сетью, то под $h_j$ понимается конкатенация скрытых состояний кодировщика, возникавших при проходе через $j$-й элемент вперёд и назад), а $\\alpha_{ij}$ — вес, назначаемый вниманием $j$-му скрытому состоянию кодировщика на $i$-м шаге декодировщика:\n",
"$$\\alpha_{ij} = \\frac{\\exp(f(d_{i-1}, h_j))}{\\sum_{k=1}^l \\exp(f(d_{i-1}, h_k))},$$\n",
"где $f$ — некоторая функция, определяющая важность $h_j$ при условии $d_{i-1}$. Иными словами, вектор $\\alpha_{i\\cdot}$ получается применением софтмакса к вектору, составленному из результатов применения $f$ к парам, первым элементом которых является $d_{i-1}$, а второй элемент пробегает множество $\\{h_k\\}_{k=1}^l$.\n",
"\n",
"В качестве функции $f$ можно взять:\n",
"* перцептрон со входом размерности $p + q$, где $p$ — размерность скрытого состояния кодировщика, а $q$ — размерность скрытого состояния декодировщика, и выходом размерности 1; этот перцептрон обучается совместно с декодировщиком как его часть;\n",
"* косинус угла между $d_{i-1}$ и $h_j$ или их скалярное произведение (эти варианты, очевидно, требуют, чтобы размерности скрытых состояний в кодировщике и декодировщике были одинаковы)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"последовательности",
"трансформеры",
"генеративные_модели"
]
},
"source": [
"## Трансформер\n",
"\n",
"#### Введение\n",
"\n",
"К недостаткам рекуррентных нейронных сетей можно отнести расход вычислительных ресурсов на обновление скрытого состояния и сложности с распараллеливанием. При этом, когда речь шла о внесении механизма внимания в [архитектуру seq2seq](__home_url__/notes/Архитектура seq2seq и механизм внимания), можно было задаться вопросом, а точно ли рекуррентные сети справляются со своей основной задачей (т.е. с учётом структуры последовательности в данных), если всё равно кодировщику приходится отдавать последовательность: пусть и последовательность скрытых состояний, а не последовательность векторных вложений исходных элементов. Статья [Vaswani et al., 2017](https://arxiv.org/pdf/1706.03762.pdf) показывает, что если ввести ряд дополнительных механизмов, то можно обойтись одним вниманием без рекуррентных сетей.\n",
"\n",
"Эти дополнительные механизмы называются так:\n",
"* отображение позиции в вектор (positional encoding),\n",
"* внутреннее внимание на базе отмасштабированного скалярного произведения (scaled dot-product self-attention),\n",
"* множественное внимание (multi-head attention).\n",
"\n",
"Также в трансформере используются такие общие для нейронных сетей техники, как:\n",
"* [послойная нормализация](__home_url__/notes/Нормализация в нейронных сетях) (layer normalization),\n",
"* обходные связи (residual connections).\n",
"\n",
"То, как всё это соединяется в трансформер, будет описано позже, а сначала будут подробно разобраны отдельные составляющие.\n",
"\n",
"#### Отображение позиции в вектор\n",
"\n",
"При отказе от рекуррентных сетей важно не потерять информацию о порядке элементов последовательности друг относительно друга. В трансформере эта информация учитывается за счёт того, что к исходному вложению каждого элемента прибавляется вектор, однозначно задаваемый позицией этого элемента. Вообще говоря, такие добавочные вложения, кодирующие позицию, можно обучать, но тогда трансформер нельзя будет применить к последовательности, длина которой больше, чем количество позиций, для которых при обучении были найдены вложения. Вместо этого оригинальная статья предлагает использовать векторы, задаваемые аналитическими формулами.\n",
"\n",
"Обозначим за $d$ размерность входного векторного вложения, а за $e^{(i)}$ — вектор, соответствующий $i$-й позиции. Отметим, что размерность $e^{(i)}$ тоже должна быть равна $d$, чтобы его можно было сложить с векторным вложением $i$-го элемента входной последовательности. Так вот, компоненты вектора $e^{(i)}$, стоящие на чётных и нечётных местах, находятся по формулам:\n",
"$$e_{2j}^{(i)} = \\sin(\\frac{i}{10000^{2j \\, / \\, d}}),$$\n",
"$$e_{2j+1}^{(i)} = \\cos(\\frac{i}{10000^{2j \\, / \\, d}}).$$\n",
"Выбор данных функций авторы поясняют так. Из школьного курса алгебры известно, что $\\sin(\\alpha + \\beta) = \\sin(\\alpha)\\cos(\\beta) + \\cos(\\alpha)\\sin(\\beta)$ и $\\cos(\\alpha + \\beta) = \\cos(\\alpha)\\cos(\\beta) - \\sin(\\alpha)\\sin(\\beta)$. Из этих формул вытекает, что для любого сдвига в позиции $k = \\mathrm{const}$:\n",
"$$e_{2j}^{(i+k)} = \\mathrm{const}_1 e_{2j}^{(i)} + \\mathrm{const}_2 e_{2j+1}^{(i)},$$\n",
"$$e_{2j+1}^{(i+k)} = \\mathrm{const}_1 e_{2j+1}^{(i)} - \\mathrm{const}_2 e_{2j}^{(i)}.$$\n",
"Если закрыть глаза на некоторые нестыковки, эти формулы выглядят так, как если бы вложение позиции, сдвинутой на константу $k$, являлось линейной комбинацией вложения исходной позиции и его же, но со сдвигом на одну его компоненту. Благодаря этому механизм внимания якобы лучше усваивает относительные позиции.\n",
"\n",
"#### Внутреннее внимание на базе отмасштабированного скалярного произведения\n",
"\n",
"Блок графа вычислений, реализующий внутреннее внимание на базе отмасштабированного скалярного произведения, преобразует переменное количество $l$ векторных вложений размерности $d$ в другие $l$ векторных вложений той же размерности $d$. Говоря концептуально, в этом блоке через механизм внимания каждое вложение обновляется с учётом информации, содержащейся в других вложениях. Тут можно снова увидеть связь с дистрибутивной гипотезой в лингвистике, вдохновившей word2vec.\n",
"\n",
"У блока внутреннего внимания есть следующие обучаемые параметры:\n",
"* $W_q$ — матрица размера $d \\times d$, умножение справа на которую превращает входное вложение размерности $1 \\times d$ в его \"запросную\" версию;\n",
"* $W_k$ — матрица размера $d \\times d$, умножение справа на которую превращает входное вложение размерности $1 \\times d$ в его версию-\"ключ\";\n",
"* $W_v$ — матрица размера $d \\times d$, умножение справа на которую превращает входное вложение размерности $1 \\times d$ в его версию-\"значение\".\n",
"\n",
"В рассматриваемом блоке каждое выходное вложение $x_i^{\\prime}$ можно вычислять по входным вложениям $\\{x_j\\}_{j=1}^l$ параллельно с остальными выходными вложениями. Делается это так:\n",
"$$x_i^{\\prime} = \\sum_j \\omega_j (x_j W_v),$$\n",
"$$\\omega = \\mathrm{softmax}_j\\left(\\frac{(x_i W_q) (x_j W_k)^T}{\\sqrt{d}}\\right),$$\n",
"где суммирование и взятие софтмакса проводится по всем $j$ от 1 до $l$, если речь идёт о кодировщике, или по всем $j < i$, если речь идёт о декодировщике (ведь он, как и в seq2seq, порождает выход последовательно), а $\\omega$ — вектор, длина которого равна количеству значений $j$, по которым проводится суммирование. Значение $\\omega_j$ этого вектора интерпретируется как скалярный вес, соответствующий вкладу $x_j$, и он тем больше, чем больше скалярное произведение между \"запросной\" версией входного вложения $x_i$ и версией-\"ключом\" входного вложения $x_j$.\n",
"\n",
"В оригинальной статье температура в софтмаксе не использовалась, а проблема того, что если одно значение сильно больше остальных, то градиент окажется затухающим, решалась через нормировку на $\\sqrt{d}$. К выбору именно такого значения можно найти следующую иллюстрацию. Возьмём две матрицы размера $d \\times d$, каждый элемент которых является независимой случайной величиной с нулевым средним и единичной дисперсией. Тогда среднеквадратичное отклонение элемента произведения этих матриц будет в $\\sqrt{d}$ раз выше.\n",
"\n",
"#### Множественное внимание\n",
"\n",
"Блок, описанный в предыдущем разделе, можно сделать более гибким, не увеличив при этом количество обучаемых параметров.\n",
"\n",
"Положим, что $d = ab$, где $a$ и $b$ — целые числа. Тогда вместо одного блока внутреннего внимания можно сделать $a$ параллельных и независимых блоков внутреннего внимания, но только таких, что у них матрицы $W_q$, $W_k$ и $W_v$ будет иметь размерность не $d \\times d$, а $d \\times b$. На самом деле, если $d$ не делится нацело на интересующее $a$, т.е. $d = ab + r$, то просто у $r$ блоков эти матрицы будут иметь размерность $d \\times (b+1)$, а у оставшихся — $d \\times b$. Выходное вложение для блока множественного внимания получается конкатенацией выходных вложений составляющих его $a$ блоков.\n",
"\n",
"По сравнению с обычным внутренним вниманием во множественном разные сегменты списка индексов от 1 до $d$ (т.е. сегменты вида $[1, b]$, $[b+1, 2b]$, $\\dots$) могут получать собственные веса, а не единые для всех усреднённые веса.\n",
"\n",
"Впрочем, необязательно требовать, чтобы количество обучаемых параметров не увеличивалось. Если взять $a$ блоков внутреннего внимания с матрицами размера $d \\times f$, то просто конкатенацию их выходов надо будет умножить справа на дополнительную обучаемую матрицу $W_o$ размера $af \\times d$, чтобы финальное вложение имело всё ту же размерность $d$. Ограничение на то, что все трансформерные блоки имеют входы и выходы одной и той же размерности $d$, нужно, чтобы произвольное количество трансформерных блоков можно было соединять последовательно без необходимости для каждого придумывать, какие размерности использовать внутри (например, в полносвязном участке).\n",
"\n",
"#### Общая архитектура\n",
"\n",
"При чтении этого раздела полезно держать перед глазами схему из оригинальной статьи.\n",
"\n",
"Трансформер решает задачу отображения входной последовательности в выходную последовательность. Элементы входной последовательности представляются как one hot векторы, которые умножаются на одну и ту же обучаемую матрицу, дающую первичные вложения размерности $d$ (такая операция называется получением вложения по индексу, embedding lookup). К этим вложениям прибавляются вложения позиций, чтобы учесть структуру последовательности, а не просто иметь мешок элементов.\n",
"\n",
"Дальше получившиеся вложения подаются в цепочку трансформерных блоков кодировщика, каждый из которых можно разделить на две части:\n",
"* Первая часть применяет множественное внимание, а результаты складывает с тем, что пришло ей на вход (обходная связь, residual connection), и к сумме применяет послойную нормализацию, результат которой отправляет во вторую часть.\n",
"* Вторая часть применяется независимо для каждого из элементов (получается, это место можно распараллелить). Вход, соответствующий некоторому элементу, прогоняется через многослойный перцептрон с одним скрытым слоем размерности $4d$ (константа 4 хорошо себя показала эмпирически) и выходным слоем размерности $d$, выход которого снова складывается со входом перцептрона через обходную связь и подвергается послойной нормализации.\n",
"\n",
"После нескольких (в оригинальной статье шести) таких трансформерных блоков кодировщика из $l$ векторов размерности $d$ получаются другие $l$ векторов размерности $d$.\n",
"\n",
"Выходная последовательность генерируется декодировщиком поочерёдно элемент за элементом. На $i$-й итерации, когда уже сгенерированы $i-1$ элементов, их первичные (т.е. полученные из матрицы по индексу) вложения складываются с позиционными вложениями и подаются в цепочку трансформерных блоков декодировщика.\n",
"\n",
"Каждый трансформерный блок декодировщика можно разбить на три части:\n",
"* Первая часть во всём идентична первой части из блока кодировщика кроме того, что её множественное внимание можно назвать вниманием с маскировкой (masked multi-head self-attention), чтобы подчеркнуть, что прячутся входы тех элементов, которые ещё не были сгенерированы. Как минимум один элемент всегда сгенерирован, потому что им является служебный токен \\<START\\>.\n",
"* Вторая часть тоже устроена как первая часть из блока кодировщика, но на вход ей подаются как выходы первой части декодировщика, так и финальные выходы кодировщика (и это единственное место в декодировщике, где учитывается исходная входная последовательность длины $l$). Матрица $W_q$ из слоя внимания этой части применяется к вложениям сгенерированных элементов, а вот матрицы $W_k$ и $W_v$ применяются к финальным выходам кодировщика. Так сделано, потому что в финальных выходах кодировщика отражён весь контекст, тогда как в уже сгенерированных элементах выходной последовательности — не весь (особенно поначалу). \n",
"* Третья часть устроена аналогично второй части из блока кодировщика.\n",
"\n",
"После цепочки трансформерных блоков в декодировщике идёт линейный слой, подсчитывающий взвешенную (с обучаемыми весами) сумму всех выходов последнего блока и повышающий размерность до размера словаря элементов. К результату применяется софтмакс, и это интерпретируется как условное вероятностное распределение следующего элемента при условии входной последовательности и того, что было сгенерировано ранее. Следующий элемент сэмплируется из этого распределения, и начинается новая итерация. Цикл продолжается, пока не будет сгенерирован специальный токен конца последовательности \\<EOS\\>.\n",
"\n",
"#### Обучение\n",
"\n",
"Трансформер решает задачу вида seq2seq, поэтому для его обучения нужна выборка, где каждой входной последовательности сопоставлена выходная. Из одной такой пары последовательностей генерируется столько обучающих примеров, сколько элементов есть в выходной последовательности (без учёта служебных токенов): $i$-й пример включает в себя всю входную последовательность и $i - 1$ первых элементов выходной. Входная последовательность пропускается через кодировщик, а выход декодировщика интерпретируется как предсказанные вероятности классов. Истинным классом считается класс, соответствующий $i$-му элементу выходной последовательности, т.е. трансформер учиться угадывать следующий элемент выходной последовательности, но только на истинных начальных подпоследовательностях, а не на том, что он мог бы нагенерировать. Для обучения используется логарифмическая функция потерь. \n",
"\n",
"#### Более поздние доработки\n",
"\n",
"С момента появления первоначальной версии были предложены следующие изменения: \n",
"* в статье [Xiong et al., 2020](https://arxiv.org/pdf/2002.04745.pdf) послойная нормализация применяется до множественного внимания и до полносвязного слоя; такое решение уже стало мэйнстримом;\n",
"* позиционные вложения можно делать в явном виде ориентированными на относительные позиции вместо абсолютных;\n",
"* вместо софтмакса от вектора, длина которого равна размеру словаря элементов, можно использовать вычислительно более эффективные операции, такие как иерархический софтмакс;\n",
"* вместо того, чтобы иметь и кодировщик, и декодировщик, для получения векторных представлений достаточно только кодировщика (как в [BERT'е](__home_url__/notes/BERT (Bidirectional Encoder Representations from Transformers))), а для генерации текстов достаточно только декодировщика (как в [GPT](__home_url__/notes/GPT (Generative Pre-trained Transformer)))."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"естественные_языки",
"векторные_вложения",
"трансформеры"
]
},
"source": [
"## BERT (Bidirectional Encoder Representations from Transformers)\n",
"\n",
"#### Общая идея\n",
"\n",
"Пусть стоит задача получить векторные вложения предложений (на самом деле, в этой заметке под словом «предложение» может иметься в виду любой цельный отрывок текста). Наивный подход такой: взять в их качестве как-либо проагрегированные вложения [токенов](__home_url__/notes/Разбиение текстов на токены), образующих это предложение. Однако у него есть очевидные недостатки: не учитывается ни порядок слов, ни связи между ними, ни возможная омонимия, которую можно бы было снять из контекста.\n",
"\n",
"В статье [Devlin et al., 2018](https://arxiv.org/pdf/1810.04805.pdf) вместо этого предлагается использовать выход кодировщика из [трансформера](__home_url__/notes/Трансформер). При этом в зависимости от целей под выходом кодировщика можно понимать следующее:\n",
"* отдельные вложения для каждого из токенов, учитывающие весь контекст предложения,\n",
"* агрегацию (сумму или среднее) вложений каждого из токенов,\n",
"* как будет объяснено ниже, для BERT'а в начало предложений добавляется служебный токен \\<CLS\\>, и иногда достаточно только его вложения. \n",
"\n",
"Также к обученному единожды BERT'у дальше можно добавлять различные «головы» (например, из полносвязных слоёв, получающих на вход вложение, даваемое BERT'ом), чтобы вместе с ними дообучать его под какие-либо частные прикладные задачи. В оригинальной статье первичное обучение называют pre-training, а обучение под конечные задачи — fine-tuning.\n",
"\n",
"Базовое обучение BERT'а могло бы, конечно, проводиться как обучение полного трансформера, из которого потом оставляют только кодировщик. Однако в общем случае в наличии имеется лишь корпус неразмеченных текстов и нет сопоставленных пар последовательностей. Именно поэтому предлагается обучать лишь кодировщик, а декодировщик вообще не рассматривать. В таком случае требуется придумать одну или несколько задач, для которых достаточно корпуса неразмеченных текстов, и обучить BERT на них. В оригинальной статье предлагаются две следующих задачи:\n",
"* восстановление скрытых токенов (Masked Language Model, MLM),\n",
"* бинарная классификация пар предложений, встретились ли они рядом (Next Sentence Prediction, NSP).\n",
"\n",
"#### Задача восстановления скрытых токенов\n",
"\n",
"В каждом предложении каждый из токенов скрывается с вероятностью $p_\\mathrm{mask}$ (в оригинальной статье она равна 15%). Такой подход позволяет BERT'у, действительно, быть двунаправленным, а не предсказывать только слева направо. На место скрытых токенов можно поставить служебный токен \\<MASK\\>, однако, так как в реальных данных этот токен не встречается, а поэтому обучаться только на текстах с ним не совсем правильно, процедура скрытия токенов устроена сложнее. Из токенов, отобранных для скрытия:\n",
"* 80% всё-таки заменяются на токен \\<MASK\\>;\n",
"* 10% заменяются на любой другой случайный токен (этот вариант, как и следующий, смягчает проблему наличия токена \\<MASK\\>);\n",
"* 10% остаются неизменными, но при этом участвуют в подсчёте функции потерь наравне с остальными скрытыми (этот вариант не даёт переобучиться на то, что скрытый токен всегда не такой как то, что стоит на его месте).\n",
"\n",
"На этапе обучения объект, прошедший через вышеописанную процедуру скрытия части токенов, прогоняется через кодировщик и для каждой позиции, на которой токен подвергался скрытию, выходные вложения кодировщика подаются в один и тот же перцептрон с функцией активации софтмакс в конце, возвращающий вероятности того, какой токен на самом деле должен быть на этом месте. По этим вероятностям считается логарифмическая функция потерь.\n",
"\n",
"#### Классификация пар предложений\n",
"\n",
"Задача из предыдущего раздела является обучением двунаправленной языковой модели. Но в общем случае хочется также уметь работать на уровне предложений, а не только на уровне слов. Для этого и добавлена задача классификации пар предложений.\n",
"\n",
"Положительными примерами в ней являются пары предложений, где второе из них встретилось в тексте после первого, а отрицательными — такие, где второе предложение просэмплировано. Каждый объект подвергается дополнительным модификациям:\n",
"* перед началом первого предложения ставится служебный токен \\<CLS\\>, вложение которого и будет наиболее важным, так как остальные вложения будут нужны лишь для того, чтобы модифицировать его через механизм внимания в трансформерных блоках;\n",
"* между предложениями вставляется служебный токен \\<SEP\\>;\n",
"* помимо имеющихся в классическом трансформере вложений, получаемых по индексу (embedding lookup), и позиционных вложений каждый токен получает третье вложение; оно обучаемое и имеет всего два значения: одно для токенов от \\<CLS\\> до \\<SEP\\> включительно и одно для токенов второго предложения.\n",
"\n",
"Вложение токена \\<CLS\\> прогоняется через перцептрон, возвращающий скалярную вероятность того, могли ли эти предложения идти последовательно. По ней считается логарифмическая функция потерь.\n",
"\n",
"#### Предварительное обучение\n",
"\n",
"BERT обучается одновременно решать обе вышеперечисленных задачи. Таким образом, объектами для базового обучения являются пары предложений, разделённых токеном \\<SEP\\> и с токеном \\<CLS\\> перед началом первого из них, где в обоих предложениях какие-либо их токены могут быть скрыты. Итоговой функцией потерь является (взвешенная) сумма отдельных функций потерь.\n",
"\n",
"#### Донастройка под частные задачи\n",
"\n",
"В случае, если частная задача не предполагает наличие пар предложений, а работает с отдельными предложениями, токен \\<SEP\\> всё равно ставится, но после него ничего не идёт (или идёт токен конца \\<EOS\\>, если он есть). Если же в частной задаче тоже есть пары (например, вопрос-ответ или предложение и его перефразировка), то всё остаётся, как было при базовом обучении.\n",
"\n",
"Если частная задача является задачей классификации, «голову» можно пристроить к вложению токена \\<CLS\\>, потому что на нём уже обучался классификатор. Если же нужны вложения отдельных токенов, «голова» пристраивается ко всем выходам или их агрегации. "
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"естественные_языки",
"трансформеры",
"генеративные_модели"
]
},
"source": [
"## GPT (Generative Pre-trained Transformer)\n",
"\n",
"GPT базируется на идее, что из [трансформера](__home_url__/notes/Трансформер) можно оставить только декодировщик. Эта идея была предложена в статье [Liu et al., 2018](https://arxiv.org/pdf/1801.10198.pdf). Авторы данной статьи отмечают, что для машинного перевода иметь и кодировщик, и декодировщик, может быть, и оправданно, но для задач, где входы и выходы должны быть на одном языке, это избыточно.\n",
"\n",
"Разумеется, нельзя просто удалить кодировщик из классического трансформера, потому что непонятно, что тогда будет получать на вход та часть трансформерного блока декодировщика, которая связана с кодировщиком. Поэтому заодно удаляется и вся эта часть, то есть трансформерный блок декодировщика теперь отличается от трансформерного блока кодировщика только тем, что в нём внимание с маскировкой, скрывающее входы несгенерированных токенов.\n",
"\n",
"В задачах класса seq2seq для использования только декодировщика без кодировщика вводится служебный токен \\<SEP\\>, разграничивающий входную последовательность от того, что сгенерировано в качестве выходной последовательности. Обучение делается аналогично обучению классического трансформера.\n",
"\n",
"Статья, посвящённая первой версии GPT ([Radford et al., 2018](https://s3-us-west-2.amazonaws.com/openai-assets/research-covers/language-unsupervised/language_understanding_paper.pdf)), примечательна не разработкой новой архитектуры, а тем, что в ней было предложено разделить базовое обучение на корпусе неразмеченных текстов и донастройку под конкретные частные задачи. Если частные задачи требуют структурированный вход (например, как в задаче выбора из заранее данных вариантов ответа, когда есть текст-вопрос и несколько текстов-ответов), было предложено подавать весь вход как один текст, но с дополнительными токенами-разделителями между частями.\n",
"\n",
"Впрочем, по мере увеличения количества обучаемых параметров стало обнаруживаться, что даже просто языковой модели достаточно для решения широкого круга задач. Также у GPT появилась способность к «обучению» на выборках из единиц примеров (few shot learning). Делается это так: входной текст содержит так называемую подводку (prompt), то есть примеры, что во что отображать, а также пример, ответ для которого хочется получить. Например, текст «Париж -> Франция, Мадрид -> Испания, Рим -> Италия, Афины ->» языковая модель должна будет продолжить словом «Греция», хотя в явном виде её никто не обучал угадывать страну по городу."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"графы"
]
},
"source": [
"## Свёрточные слои в графовых нейронных сетях\n",
"\n",
"#### Введение\n",
"\n",
"В этой заметке разбираются слои, которые обновляют векторные вложения объектов, являющихся вершинами графа, с учётом векторных вложений соседних вершин. Обычно под соседними понимаются вершины, соединённые с текущей вершиной ребром. Такая трактовка не ограничивает общность, потому что если хочется брать вершины, соединённые не более чем $k$ рёбрами, то можно переопределить исходный граф.\n",
"\n",
"Рассматриваемым слоям обязательно требуется следующая информация:\n",
"* $X$ — матрица размера $l \\times n$, где $l$ — количество вершин в графе, а $n$ — размерность входного представления вершины; эта матрица может хранить вложения вершин или их признаковые описания (если слой принимает граф, не пропускавшийся через другие слои);\n",
"* $A$ — матрица смежности графа, её размер — $l \\times l$; в общем случае она может быть несимметричной и может состоять не только из нулей и единиц, поэтому далее считается, что элемент $A_{ij}$ является весом ребра, исходящего из $i$-й вершины и ведущего в $j$-ю вершину; с технической точки зрения матрица $A$ может храниться в разреженном формате или как список смежности.\n",
"\n",
"#### Свёрточный слой для графов, GCN\n",
"\n",
"Этот слой предложен в статье [Kipf, Welling, 2017](https://arxiv.org/pdf/1609.02907.pdf).\n",
"\n",
"Обозначим за $D^\\mathrm{out}$ диагональную матрицу размера $l \\times l$ исходящих степеней вершин графа. Её элемент, стоящий на главной диагонали, есть $D^\\mathrm{out}_{ii} = \\sum_k A_{ik}$. Аналогично введём диагональную матрицу входящих степеней вершин графа $D^\\mathrm{in}$, ненулевые элементы которой являются $D^\\mathrm{in}_{ii} = \\sum_k A_{ki}$.\n",
"\n",
"Также введём обозначения $\\tilde{A} = A + I_l$, $\\tilde{D}^\\mathrm{out} = D^\\mathrm{out} + I_l$, $\\tilde{D}^\\mathrm{in} = D^\\mathrm{in} + I_l$, где $I_l$ — единичная матрица размера $l \\times l$. По смыслу $\\tilde{A}$, $\\tilde{D}^\\mathrm{out}$ и $\\tilde{D}^\\mathrm{in}$ соответствуют графу, получающемуся из исходного добавлением петель, то есть рёбер, входящих в ту же вершину, из которой они исходят. Если масштаб значений матрицы $A$ далёк от $[0, 1]$, то, возможно, для $\\tilde{A}$, $\\tilde{D}^\\mathrm{out}$ и $\\tilde{D}^\\mathrm{in}$ стоит добавлять не $I_l$, а $cI_l$, где $c$ — константа, подобранная под масштаб значений $A$.\n",
"\n",
"У графового свёрточного слоя есть следующие обучаемые параметры:\n",
"* матрица весов $W$ размера $n \\times m$, где $m$ — размерность выходных вложений вершин;\n",
"* опциональный вектор сдвига $b$ размера $1 \\times m$.\n",
"\n",
"Входная матрица $X$ преобразуется графовым свёрточным слоем по формуле:\n",
"$$\\mathrm{GCN}(X) = \\sigma\\left(\\left(\\tilde{D}^\\mathrm{out}\\right)^{-\\frac{1}{2}} \\tilde{A} \\left(\\tilde{D}^\\mathrm{in}\\right)^{-\\frac{1}{2}} X W + b\\right),$$\n",
"где $\\sigma$ — любая нелинейная функция активации (например, сигмоида или ReLU). На эту формулу можно посмотреть с двух точек зрения: с прямой и с теоретической.\n",
"\n",
"Буквальная интерпретация формулы такова. Краткости ради положим $\\overline{A} = \\left(\\tilde{D}^\\mathrm{out}\\right)^{-\\frac{1}{2}} \\tilde{A} \\left(\\tilde{D}^\\mathrm{in}\\right)^{-\\frac{1}{2}}$. Тогда:\n",
"$$\\overline{A}_{ij} = \\frac{\\tilde{A}_{ij}}{\\sqrt{\\tilde{D}^\\mathrm{out}_{ii} \\tilde{D}^\\mathrm{in}_{jj}}} = \\frac{\\tilde{A}_{ij}}{\\sqrt{\\sum_k \\tilde{A}_{ik} \\sum_k \\tilde{A}_{kj}}}.$$\n",
"Это означает, что матрица $\\overline{A}$ хранит веса ребёр, скорректированные на их «важность», где ребро тем важнее, чем меньше рёбер исходит из той же вершины и чем меньше рёбер входит в ту же вершину.\n",
"\n",
"Тем самым получается следующее:\n",
"* умножение $X$ слева на $\\overline{A}$ заменяет $i$-ю строку $X$ на взвешенную сумму строк $X$ с весами, заданными строкой $\\overline{A}_{i\\cdot}$, то есть вклад $j$-й строки пропорционален скорректированному весу ребра из $i$ в $j$,\n",
"* умножение на $W$ справа линейно преобразует получившуюся матрицу $\\overline{A}X$,\n",
"* опционально можно добавить вектор сдвига, а потом результат пропускается через нелинейную функцию активации.\n",
"\n",
"Благодаря предложенной выше интерпретации на свёрточный слой можно просто смотреть как на некоторую естественную конструкцию. Однако в оригинальной статье есть и более абстрактное обоснование, почему он имеет такой вид. Авторы показывают, что формула для GCN является аппроксимацией для [свёртки на графе](https://francescocasalegno.github.io/blog/post_gccn.html). \n",
"\n",
"Чтобы определить свёртку на графе, нелишне вспомнить, что такое классическая свёртка. В математическом анализе свёрткой двух функций вещественного аргумента $f$ и $g$ называется\n",
"$$(f \\ast g)(x) = \\int_{-\\infty}^{+\\infty}f(y)g(x - y) \\, dy.$$\n",
"У свёртки есть следующее свойство:\n",
"$$\\mathcal{F}(f \\ast g) = \\mathcal{F}(f) \\mathcal{F}(g),$$\n",
"где $\\mathcal{F}$ — преобразование Фурье. Это свойство интересно тем, что бывает и [преобразование Фурье для графов](https://en.wikipedia.org/wiki/Graph_Fourier_transform). Оно использует в качестве базиса не синусоиды, как обычное преобразование Фурье, а собственные векторы матрицы Лапласа графа $L = D - A$. Через него и вводится свёртка на графе, приближаемая слоем GCN.\n",
"\n",
"Если же от абстрактной математики вернуться к машинному обучению, можно увидеть параллели со свёрточными сетями для изображений. У них тоже есть параметры $W$ и $b$, но только вместо соседних вершин берётся всё, что попадает в фильтр (также называемый kernel).\n",
"\n",
"#### GraphSAGE\n",
"\n",
"К недостаткам GCN можно отнести трансдуктивность, то есть то, что этот слой может делать предсказания только для вершин, которые встречались при обучении. Чтобы обойти это ограничение, был предложен слой GraphSAGE ([Hamilton et al., 2017](https://arxiv.org/pdf/1706.02216.pdf)). Избавиться от трансдуктивности позволяет следующая идея: обучаются не вложения вершин, а функции, по вложениям окрестности какой-либо вершины возвращающие вложение этой окрестности.\n",
"\n",
"В общем виде слой GraphSAGE преобразует входные вложения по формуле:\n",
"$$\\mathrm{GraphSAGE}(X) = \\sigma\\left ([X \\Vert \\mathrm{agg}(X)]W + b \\right),$$\n",
"где оператор $\\Vert$ обозначает горизонтальную конкатенацию, матрица обучаемых весов $W$ теперь имеет размерность $2n \\times m$, а $\\mathrm{agg}(X)$ обозначает функцию, по матрице размера $l \\times n$ возвращающую матрицу размера $l \\times n$, $i$-я строка которой является проагрегированным по всем вершинам из окрестности $i$-й вершины вложением.\n",
"\n",
"В качестве функции $\\mathrm{agg}(X)$ можно брать:\n",
"* сумму или среднее, и тогда такая функция не будет обучаемой;\n",
"* поэлементный максимум по всем векторным вложениям вершин из окрестности, преобразованных многослойным перцептроном; все обучаемые параметры такого перцептрона становятся также обучаемыми параметрами слоя GraphSAGE.\n",
"* последнее скрытое состояние [LSTM](__home_url__/notes/Внутреннее устройство LSTM-юнита), через которую прогнали последовательность из всех вершин окрестности, как-либо упорядоченных; все обучаемые параметры такой LSTM становятся также обучаемыми параметрами слоя GraphSAGE; недостаток этого варианта в том, что результат зависит от упорядочивания вершин из окрестности;\n",
"* векторное представление \\<CLS\\>-токена [BERT](__home_url__/notes/BERT (Bidirectional Encoder Representations from Transformers))ообразной модели, которая обработала все соседние вершины; опять же, обучаемые параметры этой модели становятся также обучаемыми параметрами слоя; по сравнению с предыдущим вариантом исчезла проблема упорядочивания вершин.\n",
"\n",
"Тем самым получается, что отличие от GCN не такое уж и большое: просто за учёт связей в графе отвечает не умножение на $\\overline{A}$, а конкатенация с проагрегированным вложением окрестности. А веса рёбер можно учитывать, домножая на них векторы, подаваемые на вход в перцептрон, LSTM или BERT.\n",
"\n",
"Отдельно стоит отметить, что при комбинировании в одной нейронной сети нескольких слоёв GraphSAGE в качестве левого операнда оператора конкатенации можно брать как выход предыдущего слоя, так и исходную матрицу $X$. Этот последний вариант будет аналогичен обходной связи (residual connection)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"нейронные_сети",
"пререквизиты_из_математики"
]
},
"source": [
"## Сэмплирование из категориального распределения через распределение Гумбеля\n",
"\n",
"#### Описание проблемы\n",
"\n",
"Представим такую ситуацию. Пусть имеются $l$ токенов, среди которых есть токен \\<STOP\\>. Изначально последовательность состоит только из токена \\<START\\>, который не входит в упомянутые $l$ токенов. На каждом шаге нейронная сеть получает на вход некую информацию о текущей последовательноси (неважно, какую) и возвращает вектор длины $l$, который после нормировки интерпретируется как вектор вероятностей категориального распределения над токенами. Из этого категориального распределения сэмплируется следующий элемент последовательности, и так продолжается до тех пор, пока не будет сгенерирован токен \\<STOP\\>. По получившейся последовательности (в виде one-hot encoded векторов) дифференцируемым образом вычисляется функция потерь. Опять же, неважно, как (например, если это GAN, то может быть дискриминатор с агрегирующей [LSTM](__home_url__/notes/Внутреннее устройство LSTM-юнита)) или с [транформерными](__home_url__/notes/Трансформер) блоками). Проблема в том, что операция сэмплирования не позволит стандартным способом подсчитать градиент функции потерь по весам какого-либо юнита, стоящего до сэмплирования.\n",
"\n",
"Для большей ясности сравним описанный пример с языковой моделью, по предыдущим словам предсказывающей следующее слово. Такая модель обучается решать задачу классификации, где для логарифмической функции потерь не нужно никакое сэмплирование. В разбираемом же примере функция потерь вычисляется по самой последовательности, а не по вероятностям её отдельных элементов. Более того, без сэмплирования и получить эту последовательность не вышло бы, ведь её элементы зависят от конкретных значений предыдущих элементов, а не их вероятностей.\n",
"\n",
"Проблема вычисления градиентов при наличии сэмплирования из категориального распределения является достаточно общей. Она может возникать не только в генеративных моделях, но и в обучении с подкреплением, если выбор действия дискретен. Для её решения используют приём с распределением Гумбеля. Далее он будет детально разобран.\n",
"\n",
"#### Вероятностные распределения\n",
"\n",
"Стандартным распределением Гумбеля $G(0, 1)$ (далее просто $G$) называется распределение с кумулятивной функцией\n",
"$$F_G(x) = e^{-e^{-x}}$$\n",
"или, что эквивалентно, с функцией плотности\n",
"$$f_G(x) = e^{-(x + e^{-x})}.$$\n",
"\n",
"Сэмплировать величины $x$ из стандартного распределения Гумбеля можно методом обратного преобразования:\n",
"* просэмплировать из распределения, равномерного на отрезке $[0; 1]$, величину $y = F_G(x) = e^{-e^{-x}}$;\n",
"* вычислить $x$ по формуле $x = F_G^{-1}(y) = -\\log(-\\log(y))$.\n",
"\n",
"Также далее пригодится экспоненциальное распределение. У экспоненциального распределения с интенсивностью $\\lambda$ кумулятивная функция равна 0 при отрицательных $x$, а при $x \\ge 0$\n",
"$$F_E(x; \\lambda) = 1 - e^{-\\lambda x},$$\n",
"в то время как функция плотности равна 0 при отрицательных $x$, а на неотрицательной полуоси имеет вид\n",
"$$f_E(x; \\lambda) = \\lambda e^{-\\lambda x}.$$\n",
"\n",
"Связь между этими распределениями такова. Если $x \\sim F_E(x; \\lambda)$, то $y = -\\log(\\lambda x) \\sim F_G(y)$. Это вытекает из формулы замены переменных. Согласно этой формуле, плотность $y$ равна:\n",
"$$f_E(x; \\lambda) \\left\\lvert \\frac{dx}{dy} \\right\\rvert\n",
"= \\lambda e^{-\\lambda x} \\left\\lvert \\frac{d \\frac{1}{\\lambda} e^{-y}}{dy} \\right\\rvert\n",
"= \\lambda e^{-e^{-y}} \\left\\lvert -\\frac{1}{\\lambda} e^{-y} \\right\\rvert\n",
"= f_G(y).$$\n",
"\n",
"#### Альтернативный способ сэмплирования из категориального распределения\n",
"\n",
"Пусть есть вектор $\\pi$ длины $l$, задающий вероятности каждого из $l$ исходов. Категориальное распределение, заданное им, обозначим как $C(\\pi)$.\n",
"\n",
"Ни с того, ни с сего рассмотрим $l$ экспоненциальных распределений, у $i$-го из которых интенсивность равна $\\pi_i$. Предположим, что случайная величина $j$ порождается так:\n",
"* из каждого из этих распределений сэмплируется по числу $x_i$;\n",
"* $j = \\arg \\min_i x_i$.\n",
"\n",
"Утверждается, что такой способ сэмплирования $j$ совпадает с сэмплированием из $C(\\pi)$. Действительно, вероятность получить некое конкретное значение $j$ при данной процедуре равна:\n",
"$$\\mathbb{P}[j] = \\int_0^{+\\infty} \\mathbb{P}[x_j = x] \\mathbb{P}[\\forall i \\ne j \\; x_i > x] dx\n",
"= \\int_0^{+\\infty} f_E(x; \\pi_j) \\left(\\prod_{i \\ne j} (1 - F_E(x; \\pi_i))\\right) dx\n",
"= \\int_0^{+\\infty} \\pi_j e^{-\\pi_j x} \\left(\\prod_{i \\ne j} e^{-\\pi_i x}\\right) dx\n",
"= \\pi_j \\int_0^{+\\infty} e^{-\\sum_i \\pi_i x} dx = \\pi_j.$$\n",
"\n",
"Продолжим представлять сэмплирование из $C(\\pi)$ в альтернативных формах. Вместо того, чтобы сэмплировать $x_i$ из экспоненциальных распределений с интенсивностями $\\pi_i$, просэмплируем $y_i = -\\log(\\pi_i x_i)$ из стандартного распределения Гумбеля, а потом рассмотрим $-\\log(x_i) = y_i + \\log(\\pi_i)$. Тогда, поскольку $-\\log(x)$ является убывающей функцией:\n",
"$$j = \\arg \\min_i x_i = \\arg \\max_i \\left(y_i + \\log(\\pi_i)\\right).$$\n",
"\n",
"Повторим это ещё раз в виде альтернативной процедуры сэмплирования $j$ из $C(\\pi)$:\n",
"* для всех $i$ от 1 до $l$ независимым образом из стандартного распределения Гумбеля сэмплируются $y_i$;\n",
"* $j = \\arg \\max_i \\left(y_i + \\log(\\pi_i)\\right)$.\n",
"\n",
"При полученной процедуре сэмплирование из категориального распределения, зависящее как от вектора $\\pi$, так и от исхода случайности, оказывается перепараметризованным. Эта перепараметризация даёт то, что вектор $\\pi$ теперь отделён от случайности, которая вся сосредоточена в векторе $y$.\n",
"\n",
"#### Решение проблемы вычисления градиентов\n",
"\n",
"Несмотря на преимущества сэмплирования через распределение Гумбеля, его одного не хватит для вычисления градиентов, потому что в нём фигурирует операция $\\arg \\max$, у которой нет информативного градиента по $\\pi$. Вместо неё можно использовать её дифференцируемый аналог: операцию $\\mathrm{softmax}$..\n",
"\n",
"Введём следующие обозначения:\n",
"* $J_{\\textrm{one-hot}}$ — вектор длины $l$, такой что в нём везде нули кроме $j$-й позиции, где $j = \\arg \\max_i \\left(y_i + \\log(\\pi_i)\\right)$;\n",
"* $J_{\\textrm{continuous}}$ — вектор длины $l$, получающийся применением операции софтмакс с температурой $\\tau$ к вектору, $i$-я компонента которого равна $y_i + \\log(\\pi_i)$. Как известно, чем ближе $\\tau$ к 0, тем ближе $J_{\\textrm{continuous}}$ к $J_{\\textrm{one-hot}}$, но тем выше риски получить исчезающий градиент.\n",
"\n",
"Граф вычислений, в котором фигурирует сэмплирование из категориального распределения с предсказанными вероятностями $\\pi$, модифицируем, вместо операции сэмплирования поставив следующие операции:\n",
"* вычисление $J_{\\textrm{continuous}}$ по $\\pi$ и $y$ (температура $\\tau$ может быть константным гиперпараметром, а может возвращаться каким-либо подграфом исходного графа);\n",
"* one-hot кодирование, превращающее $J_{\\textrm{continuous}}$ в $J_{\\textrm{one-hot}}$.\n",
"\n",
"Касательно прямого прохода это означает, что операция сэмплирования реализована через распределение Гумбеля, а функция потерь рассчитывается по $J_{\\textrm{one-hot}}$.\n",
"\n",
"А вот при обратном проходе, казалось бы, лучше не стало. Несмотря на весь проделанный путь мы снова упираемся в наличие операции, у которой нет информативного градиента. И вот тут уже приходится прибегнуть к нестрогости: искусственным образом объявляется, что у one-hot кодирования такой же градиент, как у тождественной операции, то есть при обратном проходе её можно просто-напросто пропустить. Это допущение называется «дуболомным» обратным распространением (straight-through backpropagation). Хотя идея может звучать сомнительно, она описывалась классиками глубокого обучения: например, в статье [Bengio, 2013](https://arxiv.org/pdf/1308.3432.pdf). Итого получаем, что при обратном распространении:\n",
"* от функции потерь до операции сэмплирования вычисляется $\\frac{\\partial \\textrm{Loss}}{\\partial J_{\\textrm{one-hot}}}$ (и в этом нет нестрогости),\n",
"* для весов $\\theta$, стоявших до сэмплирования при прямом проходе, вместо $\\frac{\\partial J_{\\textrm{one-hot}}}{\\partial \\theta}$ используется $\\frac{\\partial J_{\\textrm{continuous}}}{\\partial \\theta}$.\n",
"\n",
"Альтернативы такому подходу тоже не отличаются строгостью. Если функцию потерь можно вычислить по $J_{\\textrm{continuous}}$ (например, потому что она является дискриминатором GAN'а), то можно, конечно, полностью отказаться от $J_{\\textrm{one-hot}}$, но ведь на этапе применения всё равно будет сэмплирование, то есть получится расхождение между обучением и применением."
]
}
],
"metadata": {
"celltoolbar": "Tags",
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.12"
}
},
"nbformat": 4,
"nbformat_minor": 2
}