Гипотеза лотерейного билета

Материал из MachineLearning.

Перейти к: навигация, поиск
Статья написана с использованием LLM GPT-5.5 и проверена участником Nikolai Agafonov 05:48, 16 июля 2026 (MSD)


Содержание

Определение

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

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

Гипотеза была сформулирована Джонатаном Фрэнклом и Майклом Карбином в 2018 году и опубликована на конференции ICLR в 2019 году.

История возникновения

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

Однако возник вопрос: можно ли обучить такую разреженную модель непосредственно с нуля?

Ранние исследования показывали, что случайно инициализированные разреженные сети обычно обучаются хуже плотных моделей. Работа Дж. Фрэнкла и М. Карбина показала, что проблема связана не только со структурой сети, но и с конкретной начальной инициализацией весов.

Формальная постановка

Пусть задана нейронная сеть f(x;\theta), где \theta\in\mathbb{R}^{d} — вектор всех обучаемых параметров.

Обучение модели заключается в минимизации функции потерь:

\mathcal{L}(\theta)= \frac{1}{N} \sum_{i=1}^{N} \ell(f(x_i;\theta),y_i),

где:

  • x_i — входной объект;
  • y_i — правильная метка;
  • \ell — функция потерь;
  • N — размер обучающей выборки.

Пусть \theta_0 — случайная начальная инициализация параметров, а \theta_T — параметры после обучения.

Выигрышный билет задаётся бинарной маской:

m\in\{0,1\}^{d},

где m_i=1 означает сохранение параметра, а m_i=0 — его удаление.

Разреженная подсеть имеет параметры: \theta'=m\odot\theta_0, где \odot — поэлементное произведение.

Гипотеза утверждает, что существует такая маска m, что после обучения:

\mathcal{L}(m\odot\theta_0) \approx \mathcal{L}(\theta_T).

То есть небольшая часть исходной сети способна достичь качества всей модели.

Поиск выигрышных билетов

В оригинальной работе использовался алгоритм итеративного прореживания по величине весов (англ. Iterative Magnitude Pruning, IMP).

Алгоритм:

  1. Инициализировать сеть параметрами \theta_0.
  2. Обучить сеть до сходимости.
  3. Удалить параметры с наименьшими абсолютными значениями.
  4. Вернуть оставшиеся параметры к значениям из \theta_0.
  5. Повторять процедуру.

Удаление параметров определяется маской:

m_i= \begin{cases} 1,&|\theta_i|>\tau,\\ 0,&|\theta_i|\leq\tau, \end{cases}

где \tau — выбранный порог.

После применения маски обучение выполняется только для оставшихся параметров:

\theta^{(t+1)} = m\odot (\theta^{(t)}-\eta\nabla_\theta\mathcal{L}),

где \eta — скорость обучения, а

\nabla_\theta\mathcal{L} — градиент функции потерь.

Разреженность модели

Количество параметров после прореживания является одной из основных характеристик выигрышного билета.

Пусть исходная модель содержит d параметров, а найденная подсеть — k параметров.

Тогда степень разреженности:

s=1-\frac{k}{d}.

Например, если из десяти миллионов параметров остаётся один миллион:

s=1-\frac{10^6}{10^7}=0.9,

то есть модель имеет 90 % разреженности.

Роль начальной инициализации

Главный результат гипотезы состоит в том, что важна не только структура подсети, но и её начальные значения.

Рассмотрим две модели: m\odot\theta_0 и m\odot\theta'_0, где \theta'_0 получена независимой случайной инициализацией.

Эксперименты показывают, что первая модель обычно обучается лучше:

\mathcal{L} (m\odot\theta_0) \lt \mathcal{L}(m\odot\theta'_0).

Следовательно, выигрышный билет определяется парой: (m,\theta_0), а не только архитектурой подсети.

Метод rewinding

Первоначальная версия гипотезы плохо масштабировалась на большие модели.

Позднее был предложен метод rewinding («откат» параметров).

Вместо возврата к начальному состоянию \theta_0, используется состояние после небольшого числа шагов обучения:\theta_t, где 0 \lt t \lt T.

Таким образом, сохраняется информация о ранней стадии оптимизации, но удаляются избыточные параметры.

Метод позволил находить выигрышные билеты в более крупных архитектурах, включая ResNet.

Теоретические результаты

Оригинальная работа Дж. Фрэнкла и М. Карбина имела в основном экспериментальный характер.

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

Например, Эран Малах и соавторы показали, что достаточно большие случайно инициализированные сети содержат подсети, способные аппроксимировать заданные модели.

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

Практическое значение

Основные применения:

  • уменьшение размера моделей;
  • ускорение инференса;
  • снижение требований к памяти;
  • обучение моделей на устройствах с ограниченными ресурсами;
  • исследование структуры больших моделей.

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

Ограничения

Несмотря на большое влияние, гипотеза имеет ограничения:

  • поиск выигрышного билета может требовать многократного обучения модели;
  • алгоритмы прореживания являются вычислительно дорогими;
  • для очень больших моделей поиск эффективных подсетей остаётся сложной задачей;
  • отсутствует полное объяснение того, почему такие подсети существуют.

Современные исследования

Современные работы изучают:

  • поиск разреженных моделей без предварительного обучения;
  • применение LTH к трансформерам;
  • динамическое изменение архитектуры во время обучения;
  • связь разреженности и способности модели к обобщению;
  • применение идеи выигрышных билетов к большим языковым моделям.

См. также

Литература

  • Frankle J., Carbin M. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. ICLR, 2019.
  • Frankle J., Dziugaite G., Roy D., Carbin M. Linear Mode Connectivity and the Lottery Ticket Hypothesis. ICML, 2020.
  • Malach E., Yehudai G., Shalev-Shwartz S., Shamir O. Proving the Lottery Ticket Hypothesis: Pruning is All You Need. ICML, 2020.
  • Lee N., Ajanthan T., Torr P. SNIP: Single-shot Network Pruning based on Connection Sensitivity. ICLR, 2019.
  • Wang C., Zhang G., Grosse R. Picking Winning Tickets Before Training by Preserving Gradient Flow. ICLR, 2020.
Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%93%D0%B8%D0%BF%D0%BE%D1%82%D0%B5%D0%B7%D0%B0_%D0%BB%D0%BE%D1%82%D0%B5%D1%80%D0%B5%D0%B9%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B1%D0%B8%D0%BB%D0%B5%D1%82%D0%B0»