Rethinking the Value of Network Pruning
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, Trevor Darrell
Статья: https://arxiv.org/abs/1810.05270
Код (unofficial): https://github.com/Eric-mingjie/rethinking-network-pruning

Про переосмысление ценностей и снова про прунинг.

Классический прунинг реализует пайплайн вида “обучение модели” → “прунинг” → “файнтюнинг”

Данная работа ниспровергает некоторые широко распространённые верования относительно этого процесса:

1) Важно начинать с обучения большой over-parameterized сети, из которой мы затем можем удалить часть избыточных параметров, не влияя существенно на точность. И это, считается, лучше, чем обучать маленькую модель с нуля.

2) И веса, и архитектура полученной урезанной модели важны для получения итогового качественного результата. Поэтому выбирается файнтюнинг получившейся модели, а не обучение полученной архитектуры с нуля.

Авторы показывают, что для методов structured pruning (прунинг на уровне каналов свёртки или выше) оба верования не обязательно верны.

То есть,

1) Обучение с нуля маленькой целевой модели (где убрано x% каналов в каждом слое) со случайной инициализации способно дать то же или более высокое качество. То есть не обязательно начинать с [долгого] обучения большой модели, можно сразу начать с маленькой.

2) Обучение урезанной после прунинга модели с нуля также даёт аналогичное или более высокое качество по сравнению с файн-тюнингом. То есть полученная архитектура может быть важнее, чем собственно сами веса.

Для методов unstructured pruning (где прунятся индивидуальные веса) также удаётся при обучении с нуля получить сравнимые с прунингом + файн-тюнингом результаты на маленьких датасетах, но не получается на больших типа ImageNet.

Почему раньше все считали иначе? Возможно, просто менее тщательно подбирали гиперпараметры (увы, обычная история в DL, к тому же требующая больших вычислительных ресурсов на эксперименты с переборами), схемы аугментации данных или был нечестный вычислительный бюджет для бейзлайнов.

Пора всё переосмыслить. Возможно, ценность прунинга порой состоит в нахождении правильной целевой архитектуры нежели конкретных “важных” весов. Таким образом прунинг может работать как неявный architecture search.

Авторы озаботились тщательным сравнением с разными методами. Среди прочего, важно сравнивать в рамках одинаковых вычислительных бюджетов. Соответственно есть два режима обучения маленьких сетей с нуля -- Scratch-E (то же число эпох) и Scratch-B (тот же вычислительный бюджет в терминах FLOPs).

Дальше сравнивают с кучей методов:

1) Predefined Structured Pruning (pruning ratio предопределён заранее): L1-norm absed filter pruning, ThiNet, Regression based feature reconstruction. Scratch-B почти тотально лучше всего остального.

2) Automatic Structured Pruning (pruning ratio определяется алгоритмом для каждого слоя самостоятельно): Network slimming, Sparse structure selection. Scratch-B снова рулит.

3) Unstructured Magnitude-based Pruning. Scratch-B сравним с файн-тюнингом (но при высоких pruning ratio файнтюнинг порой выигрывает) и проигрывает только на ImageNet.

Один из главных выводов, что для structured pruning полученные после прунинга веса не лучше случайных, и видимо вся польза в полученной архитектуре.

Сравнения с равномерным прунингом показывают существенную разницу, так что архитектура важна. Но есть и кейсы, где особой разницы нет, это больше свойственно архитектурам типа ResNet или DenseNet, видимо в этих сетях избыточность более сбалансирована, чем, скажем, в VGG.

На эксплуатации этого знания (в каких слоях какая часть каналов отпрунена и т.п., паттерны разреженности в фильтрах) можно построить guided pruning. Оно работает.

Говоря про прунинг нельзя не коснуться Lottery Ticket Hypothesys (LTH), которая работала в режиме unstructured pruning и где начальная инициализация подсети была важна. Текущая работа показывает, что результирующую сеть можно обучать с новой случайной инициализации и всё ок (но текущая работа в основном про structured pruning, хотя есть и unstructured).

Выглядит как противоречие.

Авторы показывают, что вся разница от learning rate. В LTH он был слишком низкий. Для structured pruning и при низком, и при высоком LR выигрышный билет не превосходит случайную инициализацию. В unstructured pruning оригинальная инициализация даёт преимущество только при низком LR (а с таким низким LR итогое качество и так хуже, чем с высоким, который обычно и используется).

Авторы оригинальной работы про LTH, кстати, пишут, что не сумели найти выигрышные билеты на высоком LR (“At the higher learning rate, iterative pruning does not find winning tickets, and performance is no better than when the pruned networks are randomly reinitialized.”). Так что сходится.

Пример результата

Guided sparsification

Lottery ticket suboptimality — всё дело в волшебных пузырьках!

Weight Agnostic Neural Networks
Adam Gaier, David Ha
Статья: https://arxiv.org/abs/1906.04358
Интерактивная статья: https://weightagnostic.github.io/
Код: https://github.com/weightagnostic/weightagnostic.github.io

Очень интересная работа снова про важность архитектур сетей (а не весов). У Дэвида Ха, кстати, крутые работы, рекомендую следить.

Главный вопрос статьи: до какой степени сама архитектура сети, без обучения каких-либо весов, может кодировать решения определённых задач? Архитектура с правильным inductive bias может быть способна это делать.

В этом есть большой биологический смысл. Многие животные уже рождаются со способностью решать какие-то задачи (убегать от хищника, например), не тратя время на обучение.

Идея в том, что давайте вообще не будем обучать веса, заменим обучение на сэмплирование, а до кучи, чтобы избежать проблем больших размерностей, заэнфорсим weight sharing для _ВСЕХ_ весов и будем сэмплить только одно число — сделаем все веса одинаковыми. Да ещё и будем выбирать решения, работающие в диапазоне весов, а не только с одним конкретным. Поэтому Weight Agnostic Neural Networks (WANN).

Для поиска таких сетей запускается эволюционный алгоритм, похожий на широко известный NEAT (там, правда, и веса оптимизировались):
1) Создаём популяцию минимальных простых разреженных сеток (без скрытых узлов);
2) Каждая сеть оценивается для разных значений параметра веса ([-2, -1, -0.5, +0.5, +1, +2]), итог усредняется;
3) Сети ранжируются по качеству _И_ сложности (многокритериальная оптимизация);
4) Отбираем лучших, мутируем и создаём новую популяцию.
5) goto 2

Мутации бывают такие: добавить узел, добавить соединение, изменить активацию (взята достаточно богатая библиотека активаций, там много нетипового, например, синусоида или инвертирование).

Из двух сетей с одинаковым качеством выбирается более простая. Используются три критерия: среднее качество по всем значениям веса, максимальное качество для лучшего веса, число соединений в сети. Чтобы помочь сложным структурным изменениям, которые могут потребовать нескольких улучшений, ранжирование по сложности сделано вероятностным: в 80% случаев сети ранжируются по среднему качеству и сложности, а в 20% случаев по среднему качеству и максимальному качеству.

Эксперимент запускается на трёх задачах непрерывного управления: CartPoleSwingUp, BipedalWalker-v2 и CarRacing-v0. Проверяются варианты: все рандомные веса, рандомный общий вес, настраиваемый общий вес, настраиваемые веса.

WANN со случайным общим весом вполне работают. Если этот вес потом потюнить, то работают ещё лучше. Итоговое качество ниже, чем у полностью обучаемых сетей, но весьма достойно.

Дополнительный плюс получающихся сетей в том, что они выходят достаточно маленькими, чтобы быть интерпретируемыми.

Также авторы проверяют метод на задаче классификации (MNIST), получается вполне разумное качество, сравнимое с однослойной сеткой с тысячами весов, обучаемой градиентным спуском.

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

Важная и интересная работа, напоминающая, что текущий мейнстримовый подход к AI не факт, что самый правильный:

“The first lesson from neuroscience is that much of animal behavior is innate, and does not arise from learning. Animal brains are not the blank slates, equipped with a general purpose learning algorithm ready to learn anything, as envisioned by some AI researchers; there is strong selection pressure for animals to restrict their learning to just what is needed for their survival.”

(“A Critique of Pure Learning: What Artificial Neural Networks can Learn from Animal Brains”, https://www.biorxiv.org/content/10.1101/582643v1)

Авторы расшарили свой код и призывают к дальнейшему экспериментированию. Также весьма зачётный список ссылок в работе.

Прикольный момент из серии как делается наука: авторы собирались исследовать сети, где для каждого соединения свой случайный вес, но не добились особого результата. Пытаясь заставить это работать, у них таки получилось, но потом выяснилось, что в коде баг и все соединения получили одинаковый вес. В попытке понять этот результат авторы и развили тему.

Operators for searching the space of network topologies

Performance of Randomly Sampled and Trained Weights for Continuous Control Tasks

CartpoleSwingUp champion network

A minimal architecture discovered in earlier generations that is still capable of controlling the Bipedal Walker to walk forward, despite not achieving an excellent score.

В нескольких последующих постах выложу обзор статей о современных  неавторегрессионных моделях генерации текста -- т.е. моделей, предлагающих генерировать текст не по одному токену слева направо, а как-то иначе, более хитрым образом. Подробно опишу пять статей на этот счёт, ещё пару упомяну. Изложение будет в хронологической последовательности, и сложность моделей будет постепенно нарастать.

The Importance of Generation Order in Language Modeling
Nicolas Ford, Daniel Duckworth, Mohammad Norouzi, George E. Dahl
Google Brain, 2018

#nlp #nlg #nonautoregressive #transformer

Статья: https://arxiv.org/abs/1808.07910

Основная часть NLG моделей авторегрессионна, т.е. они пишут текст слева направо, по одному токену за итерацию. Как можно отойти от такой схемы? Авторы придумали использовать двухпроходный алгоритм — общий словарь можно разделить на две части, а затем обучить две независимые трансформерные модели: первая генерирует текст только из токенов первой части словаря + специального placeholder-токена, затем вторая модель получает этот текст с плейсхолдерами на вход и заполняет пропуски словами из второго словаря. Работа описывает различные стратегии разбиения словаря на две части и сравнения их эффективности.

Какие стратегии рассматривались?
 * Common First (частотные в первом проходе) / Rare First (редкие в первом проходе) -- разбиение словаря токенов по частоте в корпусе, отсечка выбиралась так, чтобы матожидание числа "частых" и "редких" в предложении было примерно одинаковым.
 * Function First (сначала функциональные) and Content First (сначала содержательные) -- разбивали по роли слова, в функциональные попали также предлоги, союзы, модальные глаголы, вопросительные слова и прочее. Омонимию по роли разрешали просто выбирая наиболее частотную роль слова в корпусе (согласно Parsey McParseface).
 * Odd First -- контрольный вариант, где в первую половину словаря попали токены с нечётными индексами (по эффекту это должно быть экививалентно равномерно случайному разбиению)

Эксперименты гоняли на датасете LM1B, lowercase, со общим словарём в 64К токенов, только целые слова, без subword tokens. В качестве бейзлайна использовали просто Transformer без энкодера, т.е. простую LM. В качестве “enhanced baseline” его же, но по числу параметров подогнанного до размера анализируемых архитектур. Сравнивали модели по perplexity.

Человеческая интуиция подсказывает, что разумнее сначала передать главную мысль, записать ключевые смысловые слова, а затем уже вокруг них выстраивать предложение (многие люди так делают конспекты и быстрые записки в блокнотах). Здесь, однако, вышло, что наиболее эффективно писать сначала все служебные слова, т.е. фиксировать структуру предложения, а потом уже заполнять её смыслом. Хуже всех при этом отработал Odd First, он оказался заметно слабее всех остальных, это, в целом, показывает, что сама генерация в два прохода — задача существенно более сложная, чем обычная генерация. Вероятно, поэтому ни один из двухпроходных вариантов не смог обойти “enhanced baseline” (хотя Function First почти сравнялся с ним). Другая возможная причина — из требований равенства параметров в моделях каждая из трансформер-сетей в двухпроходной архитектуре заметно меньше чем трансформер в “enhanced baseline”, и качество может падать из-за недостаточного размера.

Обсуждая причины победы Function First над остальными вариантами авторы формулируют две мысли:
* для написания корректного правдоподобного предложения проще сначала задать его синтаксическую структуру, а потом уже заполнять её смыслом
* выгоднее до последнего избегать генерации редких токенов, потому что последующая за ними генерация будет обусловлена маловероятным контекстом (поэтому, кстати, на втором месте после Function First стоит Common First)

Я бы добавил третью мысль — у второй сетки нет возможности вставлять столько слов, сколько ей надо, каждый плейсхолдер она может заполнять только одним словом. Поэтому сценарий "накидать ключевые смыслом слова, а потом выписать вокруг них структуру" тут просто не реализуем в чистом виде.

Sequence Modeling with Unconstrained Generation Order
Dmitrii Emelianenko, Elena Voita, Pavel Serdyukov
Yandex, 2019

Статья: https://arxiv.org/abs/1911.00176
Код: https://github.com/TIXFeniks/neurips2019_intrus

#nlp #nlg #nonautoregressive #transformer #nips

Авторы решают задачу обучения модели, которая генерирует последовательность по одному токену, но в произвольном порядке. На каждом шагу сеть предсказывает позицию и токен для неё. Такая задача затруднена тем, что для последовательности из N токенов существует N! различных путей последовательных вставок из пустой строки до таргета. Вместо того, чтобы учить модель, награждая за все правильные последовательности и штрафуя за неправильные (что просто нереально), делается следующий трюк — давайте скажем, что для каждой строки есть некоторый оптимальный путь, тогда задача модели — сопоставить ему наибольшую вероятность. Это позволяет перейти к оптимизации lower bound оценки на исходный страшный log-likelihood. Затем делается замена оценки оптимального пути на матожидание по сэмплу путей из текущей модели с весами соответствующими вероятности пути, что даёт следующую lower bound оценку, которую уже не так сложно оптимизировать.

Архитектура предлагаемой модели INTRUS -- encoder/decoder трансформер со следующими модификациями:
 - отключаем маскирование "будущих" токенов в декодере, т.к. у нас больше нет явной последовательности, декодер надо полностью пересчитывать после каждой вставки.
 - последний слой предсказывает матрицу вероятностей размера (число слотов Х число токенов), для этого делается отдельная проекция в вероятности слотов и отдельная проекция в условные вероятности p(токен|слот), а затем из них собирается итоговая вероятность.

Тестировали на нескольких задачах (NMT, Image-To-Latex, Image captioning). На всех тестах мерили BLEU, для MSCOCO дополнительно CIDEr. Почти везде обогнали бейзлайны, но при этом увеличение времени работы относительно бейзлайна надлинейно растёт от длины строки.

Изучение последовательностей сэмплинга, предлагаемых, обученной моделью показало, что часто модель выбирает сэмплирование слева направо или справа налево, но иногда отходит от этой последовательности при обработке связанных групп токенов (приводят пример со связью открывающих и закрывающих кавычек или скобок). Другая стратегия — генерация из середины в стороны. Авторы отмечают, что чаще модель старается сначала сэмплить высокочастотные токены (например, пунктуацию и союзы), что совпадает с результатами из предыдущей описанной статьи. Для анализа этого эффекта приводятся распределения частот сэмплинга разных частей речи от номера шага для такой модели и для обычного сэмплинга слева направо.

Здесь же, дополнительно, упомяну статью Insertion-based Decoding with automatically Inferred Generation Order от Facebook AI, 2019. Она очень похожа по логике на INTRUS, решает ту же задачу генерации по одному токену в произвольном порядке. Из основных отличий я отметил два -- они используют другую ELBo оценку, и они используют относительное а не абсолютное позиционное кодирование. Детали читайте в [arxiv:1902.01370].