Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
Для отслеживания состояния из конечного набора на последовательностях любой длины модели нужно одновременно гасить вычислительную ошибку и сохранять расстояние между разными состояниями; аффинное обновление не умеет делать это в конечной точности. Хотя работа не прошла рецензирование и числа получили сами авторы, предложенная NFSM показала безошибочную точность на всех проверенных длинах, а аффинные аналоги ломались на каждой задаче, где ответ нельзя восстановить по короткому хвосту входа. Для систем с долгой памятью это архитектурное ограничение, а не только вопрос обучения.
Линейные RNN, SSM и линейное внимание используют аффинное обновление: умножают скрытое состояние на матрицу и добавляют смещение. Такие операции можно объединять через параллельный проход (parallel scan), сокращая последовательную глубину вычислений с O(L) до O(log L), где L — длина входа. Но округление на каждом шаге и сам параллельный проход вносят ошибку.
Авторы свели надёжное отслеживание к трём условиям: состояния должны однозначно читаться, каждый шаг должен возвращать представление в ограниченную устойчивую область и одновременно выполнять правильный переход. Для этого карта обновления должна локально сжимать отклонения, но глобально не сближать разные состояния. У аффинного преобразования один темп изменения на всём пространстве: сжатие подавляет ошибку, но стирает старую информацию, а отсутствие сжатия позволяет ошибке накапливаться.
Из этого следует теоретическая граница: при любой конечной точности аффинная рекуррентная модель может надёжно реализовать только автоматы, чьё состояние определяется хвостом входа ограниченной длины. NFSM обходит предел нелинейным обновлением, совместимым с параллельным проходом. После обучения из модели можно извлечь таблицу переходов и проверить её целиком, а не судить о долгой памяти по тестам на нескольких длинах.
Проверка охватила синтетические задачи на абелевых и неабелевых группах, необратимых моноидах и текстовый набор Tracking Shuffled Objects. Один слой NFSM выучил точные таблицы переходов во всех алгебраических задачах, а два слоя сохранили безошибочную точность на всех проверенных длинах текстовых задач; большинство аффинных аналогов ошиблись уже в пределах нескольких сотен шагов. Результат относится к конечному набору состояний: задачи вроде неограниченного счёта работа оставляет открытыми.
Источники
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
