Рекуррентная сеть: состояние во времени

Рекуррентная сеть читает последовательность по одному элементу и переносит вперёд скрытое состояние. Одни и те же веса работают на каждом шаге, поэтому модель принимает строки любой длины. Но память не даётся бесплатно: её надо протащить сквозь многократное перемножение, и ровно там она теряется — сначала в градиенте, потом в самом состоянии.

Датчик, который не помнит вчерашнего дня

Счётчик у входа в парк сообщает, сколько велосипедов взяли за прошлый час. Много это или мало? Ответа нет, пока мы не знаем, что было час назад, вчера в это же время и какой сегодня день недели. Одно число без истории почти не несёт информации.

Реальные данные это подтверждают буквально. Возьмём почасовой ряд проката велосипедов за два года. Корреляция числа поездок с тем же числом час назад равна $0{,}84$; через двенадцать часов она уходит в минус, $-0{,}16$ (утро против ночи); ровно через сутки снова взлетает до $0{,}79$, а через неделю держится на $0{,}76$. История не просто полезна — она устроена ритмично, и модель обязана уметь её читать.

Первое, что приходит в голову, — подать модели окно последних $k$ измерений:

$$\widehat y_t=w_0+\sum_{j=1}^{k}w_jx_{t-j}.$$

Это обычная линейная регрессия по лагам, и она работает. Но у неё два врождённых недостатка. Во-первых, длина памяти зашита в архитектуру: чтобы заглянуть на неделю назад, нужно $k=168$ входов и $169$ параметров. Во-вторых, для каждой позиции окна заводится собственный вес, хотя правило «свежее значение важнее» одно и то же на всех позициях. Параметры дублируют друг друга.

Одна ячейка и общие веса

Простейшая рекуррентная сеть (Elman RNN) обходится одним и тем же правилом обновления на каждом шаге:

$$h_t=\tanh\!\left(W_xx_t+W_hh_{t-1}+b\right), \qquad \widehat y_t=W_y^{\top}h_t+c, \qquad h_0=0 .$$

Вектор $h_t$ — сжатое резюме всего префикса $x_1,\ldots,x_t$. Матрицы $W_x,W_h$ и векторы $b,W_y$ одинаковы для всех $t$: это weight sharing, тот же приём, что делает свёртку экономной в уроке 28, только сдвиг здесь не по пространству, а по времени.

Следствие важное: число параметров не зависит от длины последовательности. Наша учебная сеть с шириной $d_h=16$ имеет

$$\underbrace{16\cdot 1}_{W_x}+\underbrace{16\cdot 16}_{W_h} +\underbrace{16}_{b}+\underbrace{16}_{W_y}+\underbrace{1}_{c}=305$$

параметров — и столько же осталось бы при длине истории в год. Линейная модель по $48$ лагам обходится $49$ параметрами, зато по $720$ лагам ей уже нужен $721$ параметр, и дальше цена растёт линейно.

На практике шаг считают сразу для целого батча из $B$ последовательностей: если $H_{t-1}$ — матрица $B\times d_h$, а $X_t$ — матрица $B\times d_x$, то

$$H_t=\tanh\!\left(X_tW_x^{\top}+H_{t-1}W_h^{\top}+\mathbf 1b^{\top}\right).$$

Время идёт последовательно (шаг $t$ нельзя посчитать раньше шага $t-1$), а вот объекты внутри батча считаются параллельно. Именно это ограничение и делает рекуррентные сети медленнее свёрточных при обучении на длинных строках.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Скалярная память: рентген рекуррентности

Чтобы увидеть механику, разденем сеть до одного числа и уберём нелинейность:

$$h_t=wx_t+uh_{t-1},\qquad h_0=0 .$$

Развернём рекурсию до конца:

$$h_t=w\left(x_t+ux_{t-1}+u^2x_{t-2}+\cdots+u^{t-1}x_1\right) =w\sum_{j=0}^{t-1}u^{\,j}x_{t-j}.$$

Вот и вся память: это взвешенная сумма всего прошлого с геометрическими весами. Подадим единичный импульс $x_1=1$ и нули дальше — получим $h_t=wu^{\,t-1}$. Найдём время полузабывания $t_{1/2}$ из условия $|u|^{\,t-1}=\tfrac12$:

$$t_{1/2}=1+\frac{\ln\tfrac12}{\ln|u|}.$$

При $u=0{,}5$ это $2{,}0$ шага, при $u=0{,}8$ — $4{,}11$ шага, при $u=0{,}95$ — $14{,}51$ шага. Знаменатель $\ln|u|\approx-(1-|u|)$ вблизи единицы, поэтому характерная глубина памяти растёт как

$$\tau\approx\frac{1}{1-|u|},$$

то есть неограниченно при $|u|\to1$. Полезно посчитать и реакцию на ступеньку $x_t\equiv1$: сумма геометрической прогрессии даёт

$$h_t=w\,\frac{1-u^{\,t}}{1-u}\ \xrightarrow[t\to\infty]{}\ \frac{w}{1-u},$$

так что при $u=0{,}95$ установившийся уровень в двадцать раз больше входа. Одна и та же величина $1/(1-u)$ служит и глубиной памяти, и коэффициентом усиления постоянной составляющей — забыть об этом легко, а масштаб состояния уедет. Обратная сторона: при $|u|>1$ старые входы не гаснут, а растут, и состояние уходит в бесконечность; при $u=1$ память вечна, но любая постоянная составляющая накапливается без границы — сумматор переполняется.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Насыщение: tanh держит состояние, но гасит производную

В настоящей ячейке стоит $\tanh$, и он делает две вещи сразу. Хорошая: держит $h_t$ в коридоре $(-1;1)$, так что взрыва состояния не будет даже при $\|W_h\|>1$. Плохая: производная

$$\frac{d}{dz}\tanh z=1-\tanh^2z$$

в области насыщения почти нулевая. При $z=2$ она равна уже $0{,}071$, то есть сигнал, проходящий назад через такую координату, ослабляется в четырнадцать раз за один шаг. Мы это видели в уроке 17, где затухание активаций рассматривалось по глубине; в рекуррентной сети глубина — это время, и множителей столько, сколько шагов.

Обучение через развёртку

Функция потерь складывается по шагам (или берётся только на последнем, если ответ нужен один):

$$\mathcal L=\sum_{t=1}^{T}\ell(\widehat y_t,y_t).$$

Backpropagation through time — это обычное обратное распространение по развёрнутому графу. Никакой новой математики: цепное правило по графу, у которого веса повторяются, поэтому градиенты по одной и той же матрице со всех шагов складываются:

$$\frac{\partial\mathcal L}{\partial W_h} =\sum_{t=1}^{T}\frac{\partial\mathcal L}{\partial h_t}\, \frac{\partial h_t}{\partial W_h}\bigg|_{h_{t-1}\ \text{фиксировано}} .$$

Ключевой множитель — якобиан переноса состояния через один шаг:

$$\frac{\partial h_{k}}{\partial h_{k-1}} =\operatorname{diag}\!\left(1-h_k^{2}\right)W_h,$$

а через много шагов — произведение:

$$\frac{\partial h_T}{\partial h_t} =\prod_{k=t+1}^{T}\operatorname{diag}\!\left(1-h_k^{2}\right)W_h .$$

Скалярный пример выше был не игрушкой: это ровно тот же продукт, в котором $u$ заменили матрицей. Сам обратный ход удобно записать рекурсией по состоянию: если $\delta_t=\partial\mathcal L/\partial h_t$, то

$$\delta_t=\underbrace{\frac{\partial\ell_t}{\partial h_t}}_{\text{местный вклад}} +\;W_h^{\top}\operatorname{diag}\!\left(1-h_{t+1}^{2}\right)\delta_{t+1}, \qquad \delta_T=\frac{\partial\ell_T}{\partial h_T}.$$

Каждый шаг назад — одно и то же линейное преобразование, применённое к $\delta$. Ровно как прямой ход накапливал память, обратный накапливает ответственность, и оба страдают от одного и того же перемножения.

Произведение якобианов: где кончается обучение

Норма произведения ведёт себя как степень: если каждый множитель в среднем сжимает в $\rho$ раз, то

$$\left\|\frac{\partial h_T}{\partial h_t}\right\| \;\sim\;\rho^{\,T-t}, \qquad \log_{10}\left\|\frac{\partial h_T}{\partial h_t}\right\| \approx (T-t)\log_{10}\rho .$$

Логарифм падает линейно по лагу — это прямая на графике, а не медленное угасание. Строгая верхняя оценка получается из субмультипликативности нормы: поскольку $\|\operatorname{diag}(1-h_k^2)\|\le1$ всегда,

$$\left\|\frac{\partial h_T}{\partial h_t}\right\| \le\prod_{k=t+1}^{T}\left\|\operatorname{diag}(1-h_k^2)\right\|\cdot\|W_h\| \le\|W_h\|^{\,T-t}.$$

Значит, при $\|W_h\|<1$ забывание гарантировано: никакая удача с данными не спасёт. Симметричного утверждения для $\|W_h\|>1$ нет — там взрыв возможен, но не обязателен, и его гасит насыщение.

Численный опыт с матрицей $32\times32$ и настоящими множителями $\operatorname{diag}(1-h_k^2)$ даёт на лаге $50$: при спектральном радиусе $W_h$, равном $0{,}8$, логарифм нормы равен $-4{,}4$; при $1{,}0$ — $-0{,}3$; при $1{,}15$ — $+0{,}4$. К лагу $77$ первая кривая проваливается ниже $10^{-7}$, а к лагу $120$ — до $10^{-11{,}2}$: обучающий сигнал из далёкого будущего тонет в шуме мини-батча раньше, чем доходит до цели.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Обрезка градиента лечит взрыв, но не забывание

Против взрыва есть простое и честное средство — обрезка нормы:

$$g\leftarrow g\cdot\min\!\left(1,\frac{c}{\|g\|}\right).$$

Иначе говоря, шаг оптимизатора меняется только тогда, когда норма превысила порог:

$$\|g\|\le c\ \Rightarrow\ g\leftarrow g, \qquad \|g\|>c\ \Rightarrow\ g\leftarrow c\,\frac{g}{\|g\|}.$$

Направление сохраняется, длина ограничивается порогом $c$. Это не регуляризация и не изменение задачи: это защита оптимизатора от единичного шага, который выбросит веса в бессмысленную область. В нашем обучении с $c=5$ такой предохранитель срабатывал редко, но именно он гарантирует, что случайный выброс нормы (в модельном примере на полях — с $46$ до $5$, то есть в $9{,}2$ раза) не уничтожит десятки эпох работы.

Важно понимать асимметрию: обрезка спасает от слишком большого шага и ничем не помогает против слишком малого. Исчезнувший градиент нельзя «разжать» — там уже нет информации, только машинный нуль.

Лаборатория импульса

Начните с импульса и линейного режима. Двигайте $u$ и следите за красной чертой «половина импульса»: при $u=0{,}5$ она стоит на втором шаге, при $u=0{,}8$ — на четвёртом, при $u=0{,}95$ уезжает за четырнадцатый. Нижняя панель показывает то же самое число в другой роли — как множитель градиента. Обе кривые падают одинаково, потому что это одна и та же степень $u$.

Теперь включите $\tanh$ и поднимите амплитуду до пяти. Состояние прижимается к единице и держится дольше — казалось бы, память улучшилась. Но нижняя панель проваливается: производная $1-h^2$ у насыщенной координаты почти нулевая. Ровно эта пара наблюдений и объясняет, почему обычная RNN уверенно ловит недавнее и почти неспособна обучиться дальним связям, ради которых в уроке 74 появится LSTM с отдельным путём памяти.

Наконец, переключите вход на «суточный ритм» и подберите $u$ так, чтобы состояние повторяло период входа. Заметьте, что при $u$ около единицы ячейка работает как интегратор и сдвигает фазу: память — это ещё и задержка.

Реальные данные: прокат велосипедов по часам

Проверим всё на настоящем ряде. Берём почасовые поездки, обучаемся на $2011$ годе, проверяем на $2012$-м — разделение по времени, а не случайное, иначе модель подсмотрит будущее (урок 32). Вход — $48$ прошлых часов, цель — следующий час. После выбрасывания окон с пропущенными часами осталось $6595$ обучающих и $8066$ тестовых окон. Нормировка считается только по обучающей части:

$$\tilde x=\frac{x-\mu_{\text{train}}}{\sigma_{\text{train}}}, \qquad \mu_{\text{train}}=162{,}4,\quad \sigma_{\text{train}}=140{,}4\ \text{поездки},$$

и те же два числа применяются к тесту. Посчитать среднее по всем данным — классическая утечка: тест повлияет на обучение через масштаб.

Сравниваем четыре модели по средней абсолютной ошибке в поездках:

$$\mathrm{MAE}=\frac1n\sum_{i=1}^{n}\left|\widehat y_i-y_i\right| .$$

Константа «обучающее среднее» даёт $168{,}6$; persistence $\widehat y_t=y_{t-1}$ — $81{,}3$; «тот же час вчера» $\widehat y_t=y_{t-24}$ — $77{,}8$; наша RNN шириной $16$ — $56{,}6$. Выигрыш над persistence составляет $30{,}3\%$, и достигнут он тремястами пятью параметрами.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Усечённое BPTT: сколько шагов пропускать назад

Хранить весь граф для длинной последовательности дорого. Truncated BPTT обрабатывает отрезки длины $L$: состояние переносится вперёд полностью, а градиент обрывается на границе. Модель может использовать далёкую информацию, но не может научиться использовать её напрямую.

Мы обучили одну и ту же сеть при $L\in\{1,2,4,8,16,24,48\}$. Ошибка на тесте:

$$\begin{aligned} L=1&\colon\ 60{,}9, & L=2&\colon\ 61{,}0, & L=4&\colon\ 61{,}2, & L=8&\colon\ 55{,}8,\\ L=16&\colon\ 55{,}5, & L=24&\colon\ 56{,}6, & L=48&\colon\ 56{,}9 . & \end{aligned}$$

Кривая не монотонна, и это честный результат. До $L=8$ градиент слишком близорук и сеть недоучивается. Дальше выигрыш исчерпывается: лучший результат даёт $L=16$, а не максимальное $L=48$. Длинная развёртка добавляет шум и трудность оптимизации, не добавляя полезного сигнала — на этих данных полезная история короче суток.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Что сеть на самом деле читает

Обученная модель — чёрный ящик, но её можно допросить вмешательством. Для каждого лага $\ell$ заменим вход $x_{t-\ell}$ обучающим средним, оставив остальные на месте, и измерим прирост ошибки:

$$I(\ell)=\mathrm{MAE}_{\text{occl}(\ell)}-\mathrm{MAE}_{\text{base}} .$$

Результат отрезвляет. Лаг $1$ даёт $+147{,}0$ поездки — в два с половиной раза больше базовой ошибки $56{,}6$. Лаг $12$ — уже $+3{,}21$, лаг $24$ — $+0{,}46$, лаг $48$ — $0{,}00$. Первые двенадцать часов несут $93{,}9\%$ всего эффекта вмешательства, а всё, что дальше суток, — $0{,}4\%$.

Удобно свести профиль к одному числу — центру тяжести использованной истории:

$$\bar\ell=\frac{\sum_{\ell}\ell\,I(\ell)_+}{\sum_{\ell}I(\ell)_+},$$

где $(\cdot)_+$ означает срезку отрицательных значений. Здесь сумма $\sum_\ell I(\ell)_+$ равна $221{,}7$, из них $147{,}0$ приходится на первый лаг, и центр тяжести оказывается на $\bar\ell=3{,}1$ часа. Модель, которой выдали двое суток истории, в среднем опирается на три последних часа.

То есть наша RNN, формально имеющая доступ к сорока восьми часам, реально живёт в окне около половины суток. Это не провал эксперимента, а измерение объекта: короткая память и есть характерное свойство простой рекуррентной ячейки, и оно согласуется с кривой усечения, где минимум был на $L=16$.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Автомат Цетлина: та же плата за долгую память

Идея «поведение определяется небольшим внутренним состоянием» появилась в советской науке раньше нейросетевого бума. В начале $1960$-х Михаил Львович Цетлин (1924–1966) изучал конечные автоматы, действующие в случайной среде: автомат $L_{2N,2}$ имеет два действия и счётчик уверенности глубины $N$. Успех сдвигает счётчик глубже в текущую сторону, неудача — к границе, и на границе автомат меняет действие. Никакого градиента, никакого обучения весов — только состояние.

Мы воспроизвели опыт Цетлина численно: среда наказывает первое действие с вероятностью $0{,}4$, второе — с вероятностью $0{,}6$, автомат работает $40\,000$ шагов. Доля выбора лучшего действия:

$$N=1\colon\ 0{,}599,\qquad N=4\colon\ 0{,}826,\qquad N=16\colon\ 0{,}999 .$$

Чем глубже память, тем целесообразнее поведение, и в пределе $N\to\infty$ автомат становится оптимальным. Условие целесообразности Цетлин формулировал как сравнение со случайным выбором: автомат целесообразен, если

$$\lim_{T\to\infty}\frac1T\sum_{t=1}^{T}\mathbb E\,[\text{штраф}_t] \;<\;\frac{c_1+c_2}{2},$$

то есть если он в среднем получает меньше штрафов, чем монетка. Наши числа удовлетворяют этому условию уже при $N=1$: доля лучшего действия $0{,}599$ больше $0{,}5$. Но у медали есть обратная сторона. Мы поменяли среду местами и посчитали, сколько шагов автомату нужно, чтобы сменить действие: при $N=1$ хватило одного шага, при $N=16$ понадобилось $108$.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Это в точности наш компромисс. Глубина памяти $N$ у Цетлина играет роль множителя $u$: увеличение обоих делает систему устойчивее к шуму и инертнее к переменам. Разница лишь в том, что $N$ задаётся конструктором, а $u$ модель подбирает сама градиентным спуском — и потому наталкивается на произведение якобианов, о котором Цетлину думать не приходилось.

Какая задача действительно требует памяти

Чтобы измерять дальнюю память честно, нужны задачи, где короткое окно бесполезно по построению. Классических две.

Adding problem: последовательность из случайных чисел, два из них помечены маркером, надо выдать их сумму. Правильный ответ невозможно угадать по локальному окну, а цель известна точно.

Delayed copy: показать символ, потом $D$ шагов пустоты, потом потребовать его воспроизвести. Увеличивая $D$, получаем кривую дальности памяти, и она — свойство архитектуры, а не набора данных.

Такие синтетические задачи не заменяют реальные ряды, зато изолируют механизм. На реальных данных всё смешано: сезонность, погода, тренд, — и по итоговой метрике невозможно понять, память подвела или признаков не хватило.

RNN, свёртка и внимание

Одномерная свёртка обрабатывает локальные окна параллельно, её рецептивное поле растёт с глубиной и dilation (урок 28). RNN работает строго последовательно, зато онлайн: пришло измерение — обновили одно состояние, хранить историю не нужно. Механизм внимания даёт прямой доступ ко всем прошлым позициям, но требует их хранить и обычно стоит квадратично по длине.

Выбор диктуется задачей, а не модой. Для потокового датчика с жёстким лимитом памяти рекуррентность остаётся разумной: постоянные $305$ параметров и постоянные $16$ чисел состояния независимо от того, работает прибор час или год. Для длинного текста, где нужно связать слова через тысячу позиций, фиксированное состояние становится узким горлом, а произведение якобианов — непреодолимой стеной.

Память измеряется задачей, а не архитектурой

Рекуррентная сеть — это одно правило обновления, применённое многократно. Развёртка одновременно объясняет её экономию (параметров ровно $305$ при любой длине) и её главную болезнь: обучающий сигнал проходит через произведение якобианов и гибнет экспоненциально по лагу.

Дальше идут два вывода, которые стоит унести с урока. Первый: наличие информации в состоянии и обучаемость связи — разные вещи; насыщенный $\tanh$ разводит их окончательно. Второй: заявленную память надо измерять, а не предполагать. Наша сеть имела доступ к $48$ часам, обучалась на $16$ шагах лучше, чем на $48$, и в профиле вмешательства показала, что $93{,}9\%$ её работы приходится на первые двенадцать лагов. Это и есть честный ответ на вопрос «какая у модели память».

В уроке 74 появится ячейка с отдельным аддитивным путём для состояния — там произведение якобианов заменится суммой, и дальность обучения вырастет на порядок. А в уроке 76 от идеи фиксированного канала откажутся вовсе.

Задачи