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.
Что дальше? Найти хорошую практическую эвристику и изменить мир. А также обобщить результаты на другие архитектуры типа свёрточных или резнетов.
Ну если в доказательствах нет ошибок.