What's Hidden in a Randomly Weighted Neural Network?
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, Mohammad Rastegari
Статья: https://arxiv.org/abs/1911.13299
Из серии “про суть вещей”.
Случайно инициализированные сетки содержат подсети, которые демонстрируют хорошее качество вообще без обучения. Например, в рандомно инициализированном Wide ResNet-50 содержится подсетка со случайными весами, которая _без обучения_ достигает качества _обученного_ на ImageNet ResNet-34. Предлагается алгоритм для эффективного нахождения таких подсеток.
В каком-то смысле продолжение истории про Lottery Ticket Hypothesys (https://arxiv.org/abs/1803.03635). Если кто не помнит, то это история про то, что большие сети содержат разреженные подсети, которые можно эффективно натренировать до такого же качества, что и большие родительские сети, если установить им ту самую “правильную инициализацию”, которая была у них внутри большой модели.
Затем была работа (https://arxiv.org/abs/1905.01067), показавшая, что существуют т.н. Supermasks — маски, наложенные на _необученную_ случайно инициализированную сеть, дающие результирующую сеть с качеством намного выше, чем случайное угадывание (86% on MNIST, 41% on CIFAR-10). Маска здесь в смысле бинарной маски, зануляющей часть весов.
Теперь авторы текущей работы выдвигают свою ещё более сильную гипотезу и подтверждают её фактами.
В терминах красивых фраз они “validate the unreasonable effectiveness of randomly weighted neural networks for image recognition“.
Для нахождения таких подсетей авторы предложили алгоритм edge-popup, суть которого в том, что для каждого веса в сети мы учим дополнительное число (popup score), по которому мы дальше оставляем топ-k% весов. В данной процедуре сами веса сети не обучаются и остаются случайными, как в начале процесса, обучаются градиентным спуском только popup scores, по которым дальше генерится подсеть.
Также авторы показывают, что распределение, из которого сэмплят веса, очень важно, и качество найденных алгоритмом сетей существенно проседает при “неправильной” инициализации.
В общем на подходе алгоритмы совсем нового типа: которые не обучают неделями большие сети бэкпропом, а генерят огромные случайные сети и начинают их по-умному урезать.
(to be continued…)
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, Mohammad Rastegari
Статья: https://arxiv.org/abs/1911.13299
Из серии “про суть вещей”.
Случайно инициализированные сетки содержат подсети, которые демонстрируют хорошее качество вообще без обучения. Например, в рандомно инициализированном Wide ResNet-50 содержится подсетка со случайными весами, которая _без обучения_ достигает качества _обученного_ на ImageNet ResNet-34. Предлагается алгоритм для эффективного нахождения таких подсеток.
В каком-то смысле продолжение истории про Lottery Ticket Hypothesys (https://arxiv.org/abs/1803.03635). Если кто не помнит, то это история про то, что большие сети содержат разреженные подсети, которые можно эффективно натренировать до такого же качества, что и большие родительские сети, если установить им ту самую “правильную инициализацию”, которая была у них внутри большой модели.
Затем была работа (https://arxiv.org/abs/1905.01067), показавшая, что существуют т.н. Supermasks — маски, наложенные на _необученную_ случайно инициализированную сеть, дающие результирующую сеть с качеством намного выше, чем случайное угадывание (86% on MNIST, 41% on CIFAR-10). Маска здесь в смысле бинарной маски, зануляющей часть весов.
Теперь авторы текущей работы выдвигают свою ещё более сильную гипотезу и подтверждают её фактами.
В терминах красивых фраз они “validate the unreasonable effectiveness of randomly weighted neural networks for image recognition“.
Для нахождения таких подсетей авторы предложили алгоритм edge-popup, суть которого в том, что для каждого веса в сети мы учим дополнительное число (popup score), по которому мы дальше оставляем топ-k% весов. В данной процедуре сами веса сети не обучаются и остаются случайными, как в начале процесса, обучаются градиентным спуском только popup scores, по которым дальше генерится подсеть.
Также авторы показывают, что распределение, из которого сэмплят веса, очень важно, и качество найденных алгоритмом сетей существенно проседает при “неправильной” инициализации.
В общем на подходе алгоритмы совсем нового типа: которые не обучают неделями большие сети бэкпропом, а генерят огромные случайные сети и начинают их по-умному урезать.
(to be continued…)
Proving the Lottery Ticket Hypothesis: Pruning is All You Need
Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, Ohad Shamir
Статья: https://arxiv.org/abs/2002.00585
И вот продолжение предыдущей работы, более сильный вариант гипотезы лотерейного билета получил математическое доказательство.
Для любого ограниченного распределения и любой целевой сети с ограниченными весами, достаточно over-parameterized сетка со случайными весами содержит подсеть с примерно такой же точностью, что и целевая сеть. БЕЗ ВСЯКОГО ОБУЧЕНИЯ.
(Disclaimer: вывод доказательства пока не проверял)
Авторы разделяют два типа подсетей: подсети с удалёнными весами (weight-subnetworks) и подсети с целиком удалёнными нейронами (neuron-subnetworks). Показано, что прунинг весов может достигать строго лучших результатов, чем прунинг нейронов.
Главный результат: в работе показано, что ReLU-сеть произвольной глубины L может быть аппроксимирована нахождением weight-subnetwork в случайной сети глубины 2L и достаточной ширины.
Есть также чуть более сильный результат для случая, когда целевая сеть имеет глубину 2. Тогда достаточно отпрунить сеть глубины 3 (а не 4).
Ещё один результат касается прунинга нейронов: сеть глубины 2 (с одним скрытым слоем) содержит neuron-subnetwork сравнимую с лучшим классификатором с рандомными фичами (то есть классификатор, у которого тренируется только второй слой сети). Эта эквивалентность высвечивает также проблему для прунинга нейронов — поскольку модели на случайных фичах ограничены (https://arxiv.org/abs/1904.00687), ограничен и такой прунинг, а прунинг весов более могуч.
Главный итог: по сути прунинг случайно инициализированной сети столь же мощен как и оптимизация её весов. То есть “all you need is a good pruning mechanism”.
При всех этих крутых результатах прунинг весов вычислительно труден и не существует эффективного алгоритма, гарантирующего получение оптимальной weight-subnetwork для любого входного распределения. Правда, как и с обучением весов, на практике могут хорошо работать различные эвристики.
Кроме того, про градиентные алгоритмы, основу всего современного обучения нейросетей, известно наличие проблемных мест (кстати, в частности, это подтверждает способность self-distillation получать лучшие результаты, чем обученная градиентными методами родительская сеть на тех же данных). Возможно, алгоритмы на основе прунинга сумеют избежать этих проблем. Who knows.
Что дальше? Найти хорошую практическую эвристику и изменить мир. А также обобщить результаты на другие архитектуры типа свёрточных или резнетов.
Ну если в доказательствах нет ошибок.
Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, Ohad Shamir
Статья: https://arxiv.org/abs/2002.00585
И вот продолжение предыдущей работы, более сильный вариант гипотезы лотерейного билета получил математическое доказательство.
Для любого ограниченного распределения и любой целевой сети с ограниченными весами, достаточно over-parameterized сетка со случайными весами содержит подсеть с примерно такой же точностью, что и целевая сеть. БЕЗ ВСЯКОГО ОБУЧЕНИЯ.
(Disclaimer: вывод доказательства пока не проверял)
Авторы разделяют два типа подсетей: подсети с удалёнными весами (weight-subnetworks) и подсети с целиком удалёнными нейронами (neuron-subnetworks). Показано, что прунинг весов может достигать строго лучших результатов, чем прунинг нейронов.
Главный результат: в работе показано, что ReLU-сеть произвольной глубины L может быть аппроксимирована нахождением weight-subnetwork в случайной сети глубины 2L и достаточной ширины.
Есть также чуть более сильный результат для случая, когда целевая сеть имеет глубину 2. Тогда достаточно отпрунить сеть глубины 3 (а не 4).
Ещё один результат касается прунинга нейронов: сеть глубины 2 (с одним скрытым слоем) содержит neuron-subnetwork сравнимую с лучшим классификатором с рандомными фичами (то есть классификатор, у которого тренируется только второй слой сети). Эта эквивалентность высвечивает также проблему для прунинга нейронов — поскольку модели на случайных фичах ограничены (https://arxiv.org/abs/1904.00687), ограничен и такой прунинг, а прунинг весов более могуч.
Главный итог: по сути прунинг случайно инициализированной сети столь же мощен как и оптимизация её весов. То есть “all you need is a good pruning mechanism”.
При всех этих крутых результатах прунинг весов вычислительно труден и не существует эффективного алгоритма, гарантирующего получение оптимальной weight-subnetwork для любого входного распределения. Правда, как и с обучением весов, на практике могут хорошо работать различные эвристики.
Кроме того, про градиентные алгоритмы, основу всего современного обучения нейросетей, известно наличие проблемных мест (кстати, в частности, это подтверждает способность self-distillation получать лучшие результаты, чем обученная градиентными методами родительская сеть на тех же данных). Возможно, алгоритмы на основе прунинга сумеют избежать этих проблем. Who knows.
Что дальше? Найти хорошую практическую эвристику и изменить мир. А также обобщить результаты на другие архитектуры типа свёрточных или резнетов.
Ну если в доказательствах нет ошибок.
Rigging the Lottery: Making All Tickets Winners
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, Erich Elsen
Статья: https://arxiv.org/abs/1911.11134
Код: http://github.com/google-research/rigl
Статья гугловцев про новый метод обучения разреженных сеток, при котором начальная инициализация не играет роли — “все билеты выигрышные”.
Наиболее популярные сейчас методы получения разреженных сетей, когда сначала обучается обычная dense сетка, которая потом урезается (т.н. dense-to-sparse методы), имеют ограничения. В первую очередь таким образом мы ограничиваем сверху размер (и вероятно качество) разреженной сети. Ну и к тому же это неэффективно — мы производим много вычислений для параметров, которые будут нулевыми.
Есть также методы (и появляется всё больше), получающие разреженность в процессе обучения (DeepR, SET, DSR, SNFS — dynamic sparsity стратегии) или даже инициализации (SNIP, т.н. one-shot pruning алгоритм). Эту группу можно назвать sparse-to-sparse методами или sparse training алгоритмами.
Авторы предлагают свой метод обучения разреженных сетей с заданным числом параметров, способный находить модели более высокого качества по сравнению с текущими лучшими методами. Для метода не требуется “удачная инициализация”, поэтому его назвали RigL (читается как wriggle), “The Rigged Lottery”. Метод динамически обновляет сеть в процессе обучения, это dynamic sparse training.
Идея метода в том, что мы регулярно убираем часть соединений (зануляем веса) и создаём новые.
Улучшения в качестве достигаются благодаря двум вещам: новому методу для создания новых соединений и улучшению метода распределения параметров по свёрточным слоям.
Среди методов распределения разреженности рассматриваются три:
1) Равномерное распределение (все слои получают одинаковую разреженность)
2) Эрдёш-Реньи (число соединений масштабируется с учётом числа входящих и выходящих каналов)
3) Эрдёш-Реньи с ядром, ERK (модификация предыдущего, учитывающая размерность свёрточных фильтров)
Последние два метода делают более высокую разреженность в слоях с большим числом параметров и берегут веса в тех слоях, где параметров мало.
ERK показывает себя лучше всех.
Суть обновлений в том, что каждые T шагов обучения сначала дропается часть весов (с минимальной магнитудой), а потом отращиваются новые (те, что дают наибольшие градиенты — и в этом новизна). Новые соединения инициализируются нулями, чтобы не влиять на выход сети. Но ожидается, что они получат градиенты с высокими магнитудами на следующей итерации и быстрее всего уменьшат лосс.
Кроме того используется косинусная функция для определения доли обновляемых соединений.
RigL сравнивали с кучей текущих dense-to-sparse и sparse-to-sparse методов (какие-то имея реализацию, другие по репортам из статей), с плотными сетями аналогичного числа параметров, а также с алгоритмами structured pruning (SBP, L0, VIB).
RigL (или RigL+, стартующий с архитектуры, найденной RigL) рулят.
Показано, что инициализация Lottery Ticket’ом не даёт преимуществ, с RigL выигрывают все билеты.
Среди прочего в работе большой список литературы по теме разреженных сетей (методы, алгоритмы, железо и т.п.).
Также здорово, что в работе есть список багов, которые они нашли у себя в процессе реализации, и как с ними бороться. Полезно. Больше бы такого.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, Erich Elsen
Статья: https://arxiv.org/abs/1911.11134
Код: http://github.com/google-research/rigl
Статья гугловцев про новый метод обучения разреженных сеток, при котором начальная инициализация не играет роли — “все билеты выигрышные”.
Наиболее популярные сейчас методы получения разреженных сетей, когда сначала обучается обычная dense сетка, которая потом урезается (т.н. dense-to-sparse методы), имеют ограничения. В первую очередь таким образом мы ограничиваем сверху размер (и вероятно качество) разреженной сети. Ну и к тому же это неэффективно — мы производим много вычислений для параметров, которые будут нулевыми.
Есть также методы (и появляется всё больше), получающие разреженность в процессе обучения (DeepR, SET, DSR, SNFS — dynamic sparsity стратегии) или даже инициализации (SNIP, т.н. one-shot pruning алгоритм). Эту группу можно назвать sparse-to-sparse методами или sparse training алгоритмами.
Авторы предлагают свой метод обучения разреженных сетей с заданным числом параметров, способный находить модели более высокого качества по сравнению с текущими лучшими методами. Для метода не требуется “удачная инициализация”, поэтому его назвали RigL (читается как wriggle), “The Rigged Lottery”. Метод динамически обновляет сеть в процессе обучения, это dynamic sparse training.
Идея метода в том, что мы регулярно убираем часть соединений (зануляем веса) и создаём новые.
Улучшения в качестве достигаются благодаря двум вещам: новому методу для создания новых соединений и улучшению метода распределения параметров по свёрточным слоям.
Среди методов распределения разреженности рассматриваются три:
1) Равномерное распределение (все слои получают одинаковую разреженность)
2) Эрдёш-Реньи (число соединений масштабируется с учётом числа входящих и выходящих каналов)
3) Эрдёш-Реньи с ядром, ERK (модификация предыдущего, учитывающая размерность свёрточных фильтров)
Последние два метода делают более высокую разреженность в слоях с большим числом параметров и берегут веса в тех слоях, где параметров мало.
ERK показывает себя лучше всех.
Суть обновлений в том, что каждые T шагов обучения сначала дропается часть весов (с минимальной магнитудой), а потом отращиваются новые (те, что дают наибольшие градиенты — и в этом новизна). Новые соединения инициализируются нулями, чтобы не влиять на выход сети. Но ожидается, что они получат градиенты с высокими магнитудами на следующей итерации и быстрее всего уменьшат лосс.
Кроме того используется косинусная функция для определения доли обновляемых соединений.
RigL сравнивали с кучей текущих dense-to-sparse и sparse-to-sparse методов (какие-то имея реализацию, другие по репортам из статей), с плотными сетями аналогичного числа параметров, а также с алгоритмами structured pruning (SBP, L0, VIB).
RigL (или RigL+, стартующий с архитектуры, найденной RigL) рулят.
Показано, что инициализация Lottery Ticket’ом не даёт преимуществ, с RigL выигрывают все билеты.
Среди прочего в работе большой список литературы по теме разреженных сетей (методы, алгоритмы, железо и т.п.).
Также здорово, что в работе есть список багов, которые они нашли у себя в процессе реализации, и как с ними бороться. Полезно. Больше бы такого.
GitHub
GitHub - google-research/rigl: End-to-end training of sparse deep neural networks with little-to-no performance loss.
End-to-end training of sparse deep neural networks with little-to-no performance loss. - GitHub - google-research/rigl: End-to-end training of sparse deep neural networks with little-to-no perform...
Picking Winning Tickets Before Training by Preserving Gradient Flow
Chaoqi Wang, Guodong Zhang, Roger Grosse
Статья: https://arxiv.org/abs/2002.07376
Код: https://github.com/alecwangcq/GraSP
Вот ещё работа про прунинг. На этот раз не прунинг готовых сеток, и не прунинг во время обучения, а прунинг при инициализации!
Как видно, есть разные способы прунинга:
1) Наиболее известный и частый прунинг готовых обученных сетей (со всеми его недостатками, см.предыдущий пост)
2) Прунинг во время обучения, включая dynamic sparse training (см.предыдущий пост, RigL как раз отсюда)
3) Прунинг перед обучением (это уже что-то интересненькое!). Дальше рассматриваем этот кейс.
Lottery ticket hypothesis была бы из этой серии, если бы можно было при инициализации сразу находить эти выигрышные билеты.
В предыдущем посте упоминался метод SNIP (Single-shot Network Pruning, https://arxiv.org/abs/1810.02340), который в этой работе относят к классу foresight pruning.
Идея SNIP проста: у нас есть какая-то инициализированная (рандомом) сетка, давайте оставим в ней самые многообещающие соединения. Самые многообещающие определяются по т.н. connection sensitivity, насколько убирание конкретного веса влияет на лосс — убираются наименее влияющие. То есть SNIP стремится сохранить лосс оригинальной (инициализированной рандомом) сетки.
Авторы текущей работы утверждают, что в начале обучения важнее сохранить общую динамику обучения, чем лосс сам по себе. SNIP явным образом ничего такого не делает и может нарушить поток информации по сети. Например, при высоких pruning ratios (скажем, 99%) он стремится убрать почти все веса определённых слоёв, создавая боттлнек в сети.
Авторы считают, что важнее сохранять поток градиентов в сети и строят свой алгоритм на этом. GraSP (Gradient Signal Preservation) стремится убирать веса, которые не уменьшают поток градиентов в сети (клёво, если это ещё и увеличивают).
Метод в целом работает. Точно лучше случайного прунинга. На низких pruning rate (85-90%) и SNIP и GraSP дают близкие к бейзлайнам (работающим на уже тренированных сетях) результаты, но не превосходят их (что в общем неудивительно). При более серьёзном прунинге и более сложных сетях GraSP обгоняет SNIP и чем дальше, тем больше.
Из интересного, оба метода сравнимы или немного превосходят Lottery ticket с оригинальной инициализацией. Но после оригинальной работы с LT была вторая про обучение больших сетей (https://arxiv.org/abs/1903.01611), и там брали инициализацию не от самого начала, от небольшого числа итераций после, она была лучше.
До DSR (динамический прунинг, сравнение с ним было в предыдущем посте) недотягивают, он лидер. По идее RigL из предыдущей статьи был бы ещё лучше.
Визуализации показывают преференции по прунингу разных частей сети. Оба метода любят прунить много весов в верхних слоях, но GraSP всё же оставляет их больше.
В целом сейчас не выглядит суперпрорывом, но направление интересное. Если научатся делать хороший foresight pruning, то удастся сэкономить много ресурсов на обучении. Возможно, когда-нибудь получится что-то сравнимое по качеству с традиционным прунингом уже обученных сетей.
Chaoqi Wang, Guodong Zhang, Roger Grosse
Статья: https://arxiv.org/abs/2002.07376
Код: https://github.com/alecwangcq/GraSP
Вот ещё работа про прунинг. На этот раз не прунинг готовых сеток, и не прунинг во время обучения, а прунинг при инициализации!
Как видно, есть разные способы прунинга:
1) Наиболее известный и частый прунинг готовых обученных сетей (со всеми его недостатками, см.предыдущий пост)
2) Прунинг во время обучения, включая dynamic sparse training (см.предыдущий пост, RigL как раз отсюда)
3) Прунинг перед обучением (это уже что-то интересненькое!). Дальше рассматриваем этот кейс.
Lottery ticket hypothesis была бы из этой серии, если бы можно было при инициализации сразу находить эти выигрышные билеты.
В предыдущем посте упоминался метод SNIP (Single-shot Network Pruning, https://arxiv.org/abs/1810.02340), который в этой работе относят к классу foresight pruning.
Идея SNIP проста: у нас есть какая-то инициализированная (рандомом) сетка, давайте оставим в ней самые многообещающие соединения. Самые многообещающие определяются по т.н. connection sensitivity, насколько убирание конкретного веса влияет на лосс — убираются наименее влияющие. То есть SNIP стремится сохранить лосс оригинальной (инициализированной рандомом) сетки.
Авторы текущей работы утверждают, что в начале обучения важнее сохранить общую динамику обучения, чем лосс сам по себе. SNIP явным образом ничего такого не делает и может нарушить поток информации по сети. Например, при высоких pruning ratios (скажем, 99%) он стремится убрать почти все веса определённых слоёв, создавая боттлнек в сети.
Авторы считают, что важнее сохранять поток градиентов в сети и строят свой алгоритм на этом. GraSP (Gradient Signal Preservation) стремится убирать веса, которые не уменьшают поток градиентов в сети (клёво, если это ещё и увеличивают).
Метод в целом работает. Точно лучше случайного прунинга. На низких pruning rate (85-90%) и SNIP и GraSP дают близкие к бейзлайнам (работающим на уже тренированных сетях) результаты, но не превосходят их (что в общем неудивительно). При более серьёзном прунинге и более сложных сетях GraSP обгоняет SNIP и чем дальше, тем больше.
Из интересного, оба метода сравнимы или немного превосходят Lottery ticket с оригинальной инициализацией. Но после оригинальной работы с LT была вторая про обучение больших сетей (https://arxiv.org/abs/1903.01611), и там брали инициализацию не от самого начала, от небольшого числа итераций после, она была лучше.
До DSR (динамический прунинг, сравнение с ним было в предыдущем посте) недотягивают, он лидер. По идее RigL из предыдущей статьи был бы ещё лучше.
Визуализации показывают преференции по прунингу разных частей сети. Оба метода любят прунить много весов в верхних слоях, но GraSP всё же оставляет их больше.
В целом сейчас не выглядит суперпрорывом, но направление интересное. Если научатся делать хороший foresight pruning, то удастся сэкономить много ресурсов на обучении. Возможно, когда-нибудь получится что-то сравнимое по качеству с традиционным прунингом уже обученных сетей.
GitHub
GitHub - alecwangcq/GraSP: Code for "Picking Winning Tickets Before Training by Preserving Gradient Flow" https://openreview.…
Code for "Picking Winning Tickets Before Training by Preserving Gradient Flow" https://openreview.net/pdf?id=SkgsACVKPH - alecwangcq/GraSP