Все производные сети
Разработчик библиотеки для нейросетей проверяет свой автоматический дифференциатор и просит эталон: для маленькой сети и пачки примеров посчитать функцию потерь и её производные по всем весам.
Сеть — это L слоёв с размерами n0, …, nL. Слой l по входу a (вектор из nl−1 чисел) считает zi = Σk wikak + wi,n (последний вес строки — сдвиг). После всех слоёв, кроме последнего, берётся tanh. Последний слой даёт z, и потери примера с ответом t — ln Σj ezj − zt (софтмакс и перекрёстная энтропия). Потери пачки — сумма по примерам.
Вход
В первой строке — L (1 ≤ L ≤ 4), во второй — n0, …, nL (1 ≤ n ≤ 128, nL ≥ 2). Дальше веса: для каждого слоя по порядку — nl строк по nl−1 + 1 чисел. Потом B (1 ≤ B ≤ 50) и B строк: n0 чисел входа и ответ t (0 ≤ t < nL).
Выход
В первой строке — потери пачки. Дальше производные потерь по весам в том же порядке и той же раскладке, что веса во входе. Каждое число засчитывается с ошибкой до 10−6 (для чисел больше единицы — до 10−6 от числа).
Примеры
Пример 1
1 2 2 1.0000 0.0000 0.0000 0.0000 1.0000 0.0000 1 1.000 0.000 0
0.3132616875 -0.2689414214 0 -0.2689414214 0.2689414214 0 0.2689414214
Пример 2
2 2 2 2 0.5000 -0.5000 0.0000 0.2500 0.2500 0.1000 1.0000 -1.0000 0.0000 -1.0000 1.0000 0.0000 2 1.000 2.000 1 0.000 -1.000 0
0.35319829 0.1424988312 0.6429633609 -0.2154668674 -0.09465939317 -0.6343970116 0.3504188321 -0.1470366282 0.09649231629 -0.1369874045 0.1470366282 -0.09649231629 0.1369874045
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Можно сдвинуть каждый вес на маленькое ε и пересчитать потери — но весов в большом тесте 13 098, и на каждый нужно два прохода по всей пачке.
2Подсказка 2
Если знать производную потерь по выходам слоя z, то производная по весу wik — это она, умноженная на вход ak. А производная по входам слоя — сумма по выходам. Начните с конца.
3Идея
Обратное распространение. На последнем слое производная потерь по z — вероятности софтмакса минус единица на месте ответа. Дальше для каждого слоя от последнего к первому: прибавить к производным весов δi·ak, передать назад δ′k = Σi δiwik и умножить на производную tanh, 1 − ak².
4Разбор
Для каждого примера проход вперёд запоминает входы всех слоёв (с единицей для сдвига), обратный проход по формулам выше накапливает производные в массиве той же формы, что веса. Софтмакс считают со сдвигом на наибольшее z: ln Σ ez = max + ln Σ ez − max, иначе при больших весах (девятый тест, где z доходит до тысячи, а ez в числах с плавающей точкой кончается после 709) экспонента переполняется.
4+Решение
5Сложность
O(B·W), где W — число весов: проход вперёд и назад — по одному умножению на вес. Разностные производные — O(B·W²).
6Типичные ошибки
- Разностные производные. Это
wrong.py: точность у них хорошая, но на тринадцати тысячах весов — двадцать шесть тысяч проходов по пачке. - Производная tanh по выходу. Это 1 − tanh², то есть 1 − a², где a — уже посчитанный выход нейрона, а не вход z.
- Сдвиг. Его вход — постоянная единица, поэтому производная по сдвигу — просто δ, а назад он ничего не передаёт.
- Переполнение. exp(z) без вычитания максимума даёт бесконечность при z в несколько сотен.