Методы сэмплирования

Сэмплирование — это способ, которым ИИ исследует пространство возможностей.

Тип: Практика Язык: Python Предварительные требования: Фаза 1, уроки 06–07 (вероятность, теорема Байеса) Время: ~120 минут

Цели обучения

• Реализовать с нуля сэмплирование через обратную CDF, отбраковку и важностное сэмплирование, используя только равномерные случайные числа.
• Построить сэмплирование с температурой, top-k и top-p (nucleus) для генерации токенов языковой моделью.
• Объяснить трюк репараметризации и почему он делает возможным обратное распространение ошибки через сэмплирование в VAE.
• Запустить MCMC Метрополиса — Гастингса для выборки из ненормированного целевого распределения.

Проблема

Языковая модель завершает обработку вашего промпта и выдаёт вектор из 50 000 логитов — по одному для каждого токена в её словаре. Теперь ей нужно выбрать один токен. Как?

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

Сэмплирование не ограничивается генерацией текста. Обучение с подкреплением оценивает градиенты политики, сэмплируя траектории. VAE обучаются представлениям скрытого пространства, сэмплируя из выученных распределений и распространяя градиент через случайность. Диффузионные модели генерируют изображения, сэмплируя шум и итеративно устраняя его. Методы Монте-Карло оценивают интегралы, не имеющие решения в замкнутой форме. Алгоритмы MCMC исследуют многомерные апостериорные распределения, которые невозможно перечислить.

Каждая генеративная система ИИ — это система сэмплирования. Стратегия сэмплирования определяет качество, разнообразие и управляемость результата. В этом уроке мы построим с нуля все основные методы сэмплирования: начнём с равномерных случайных чисел и закончим техниками, лежащими в основе современных LLM и генеративных моделей.

Концепция

Почему сэмплирование важно

В ИИ и машинном обучении сэмплирование встречается в четырёх фундаментальных ролях:

Генерация. Языковые модели, диффузионные модели и GAN получают результат с помощью сэмплирования. Алгоритм сэмплирования напрямую управляет креативностью, связностью и разнообразием. Температура, top-k и nucleus-сэмплирование — это регуляторы, которыми инженеры пользуются ежедневно.

Обучение. Стохастический градиентный спуск сэмплирует мини-батчи. Dropout сэмплирует нейроны для деактивации. Аугментация данных сэмплирует случайные преобразования. Важностное сэмплирование перевзвешивает образцы, уменьшая дисперсию градиента в обучении с подкреплением (PPO, TRPO).

Оценивание. Многие величины в ML не имеют решения в замкнутой форме: ожидаемые потери по распределению данных, статистическая сумма энергетической модели, правдоподобие в байесовском выводе. Оценивание Монте-Карло приближает всё это усреднением по сэмплам.

Исследование. Алгоритмы MCMC исследуют апостериорные распределения в байесовском выводе. Эволюционные стратегии сэмплируют возмущения параметров. Сэмплирование Томпсона уравновешивает исследование и использование в многоруких бандитах.

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

Равномерное случайное сэмплирование

Каждый метод сэмплирования начинается здесь. Генератор равномерных случайных чисел выдаёт значения в [0, 1), где каждый подинтервал одинаковой длины имеет одинаковую вероятность.

U ~ Uniform(0, 1)

P(a <= U <= b) = b - a    for 0 <= a <= b <= 1

Свойства:
  E[U] = 0.5
  Var(U) = 1/12

Чтобы равномерно выбрать элемент из дискретного множества из n элементов, сгенерируйте U и верните floor(n * U). Чтобы сэмплировать из непрерывного диапазона [a, b], вычислите a + (b - a) * U.

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

Метод обратной CDF (inverse transform sampling)

Функция распределения (CDF) отображает значения в вероятности:

F(x) = P(X <= x)

Свойства:
  F не убывает
  F(-inf) = 0
  F(+inf) = 1
  F maps the real line to [0, 1]

Обратная CDF отображает вероятности обратно в значения. Если U ~ Uniform(0, 1), то X = F_inverse(U) подчиняется целевому распределению.

Алгоритм:
  1. Сгенерировать u ~ Uniform(0, 1)
  2. Вернуть F_inverse(u)

Почему это работает:
  P(X <= x) = P(F_inverse(U) <= x) = P(U <= F(x)) = F(x)

Пример с экспоненциальным распределением:

PDF: f(x) = lambda * exp(-lambda * x),   x >= 0
CDF: F(x) = 1 - exp(-lambda * x)

Решим F(x) = u относительно x:
  u = 1 - exp(-lambda * x)
  exp(-lambda * x) = 1 - u
  x = -ln(1 - u) / lambda

Поскольку (1 - U) и U имеют одинаковое распределение:
  x = -ln(u) / lambda

Этот подход отлично работает, когда F_inverse можно записать в замкнутой форме. Для нормального распределения замкнутой формулы обратной CDF нет, поэтому используются другие методы (Box–Muller или численное приближение).

Дискретная версия: для дискретных распределений постройте CDF как накопленную сумму, сгенерируйте U и найдите первый индекс, в котором накопленная сумма превышает U. Именно так работает sample_categorical в уроке 06.

Сэмплирование с отбраковкой

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

Целевое распределение: p(x)  (можно вычислить, возможно ненормированное)
Распределение-предложение: q(x)  (из него можно сэмплировать)
Граница: M такое, что p(x) <= M * q(x) для всех x

Алгоритм:
  1. Сэмплировать x ~ q(x)
  2. Сэмплировать u ~ Uniform(0, 1)
  3. Если u < p(x) / (M * q(x)), принять x
  4. Иначе отклонить и перейти к шагу 1

Доля принятия = 1/M

Чем точнее граница M, тем выше доля принятых сэмплов. В малой размерности (1–3) сэмплирование с отбраковкой работает хорошо. В высокой размерности доля принятия экспоненциально падает, потому что отбрасывается большая часть объёма распределения-предложения. Это проклятие размерности для сэмплирования с отбраковкой.

Пример: сэмплирование из усечённого нормального распределения. Используйте равномерное распределение-предложение на усечённом диапазоне. Огибающая M — максимум PDF нормального распределения на этом диапазоне.

Пример: сэмплирование полукруга. Предлагайте точки равномерно в ограничивающем прямоугольнике. Принимайте точку, если она попадает внутрь полукруга. Так методом Монте-Карло вычисляют pi: доля принятия равна отношению площадей pi/4.

Важностное сэмплирование

Иногда вам не нужны сэмплы из целевого распределения p(x). Вам нужно оценить математическое ожидание по p(x), но сэмплы у вас есть из другого распределения q(x).

Цель: оценить E_p[f(x)] = integral of f(x) * p(x) dx

Перепишем:
  E_p[f(x)] = integral of f(x) * (p(x)/q(x)) * q(x) dx
            = E_q[f(x) * w(x)]

где w(x) = p(x) / q(x) — важностные веса.

Оцениватель:
  E_p[f(x)] ~ (1/N) * sum(f(x_i) * w(x_i))    где x_i ~ q(x)

Это критично для обучения с подкреплением. В PPO (Proximal Policy Optimization) вы собираете траектории при старой политике pi_old, но хотите оптимизировать новую политику pi_new. Важностный вес равен pi_new(a|s) / pi_old(a|s). PPO ограничивает эти веса, чтобы новая политика не ушла слишком далеко от старой.

Дисперсия оценивателя важностного сэмплирования зависит от того, насколько q похоже на p. Если q сильно отличается от p, несколько сэмплов получают огромные веса и доминируют в оценке. Самонормированное важностное сэмплирование делит на сумму весов, чтобы уменьшить эту проблему:

E_p[f(x)] ~ sum(w_i * f(x_i)) / sum(w_i)

Оценивание Монте-Карло

Оценивание Монте-Карло приближает интегралы усреднением случайных сэмплов. Закон больших чисел гарантирует сходимость.

Цель: оценить I = integral of g(x) dx на области D

Метод:
  1. Сэмплировать x_1, ..., x_N равномерно из D
  2. I ~ (Volume of D / N) * sum(g(x_i))

Ошибка: O(1 / sqrt(N))   независимо от размерности

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

Оценивание pi:

Сэмплировать (x, y) равномерно из [-1, 1] x [-1, 1]
Посчитать, сколько точек попало внутрь единичной окружности: x^2 + y^2 <= 1
pi ~ 4 * (число внутри) / (общее число)

Оценивание математических ожиданий:

E[f(X)] ~ (1/N) * sum(f(x_i))    где x_i ~ p(x)

Выборочное среднее сходится к истинному математическому ожиданию.
Дисперсия оценивателя = Var(f(X)) / N

Марковские цепи Монте-Карло (MCMC): Метрополис — Гастингс

MCMC строит марковскую цепь, стационарным распределением которой является целевое распределение p(x). После достаточного числа шагов сэмплы из цепи (приблизительно) являются сэмплами из p(x).

Цель: p(x)  (известна с точностью до нормирующей константы)
Предложение: q(x'|x)  (как предложить следующее состояние на основе текущего)

Алгоритм Метрополиса — Гастингса:
  1. Начать с некоторого x_0
  2. Для t = 1, 2, ..., T:
     a. Предложить x' ~ q(x'|x_t)
     b. Вычислить отношение принятия:
        alpha = [p(x') * q(x_t|x')] / [p(x_t) * q(x'|x_t)]
     c. Принять с вероятностью min(1, alpha):
        - Если u < alpha (u ~ Uniform(0,1)): x_{t+1} = x'
        - Иначе: x_{t+1} = x_t
  3. Отбросить первые B сэмплов (разогрев)
  4. Вернуть оставшиеся сэмплы

Для симметричных предложений (q(x’|x) = q(x|x’)) отношение упрощается до p(x’)/p(x). Это исходный алгоритм Метрополиса.

Почему это работает. Правило принятия обеспечивает детальный баланс: вероятность находиться в x и перейти в x’ равна вероятности находиться в x’ и перейти в x. Детальный баланс означает, что p(x) — стационарное распределение цепи.

Практические соображения:

• Разогрев (burn-in): отбрасывайте ранние сэмплы до достижения цепью равновесия.
• Прореживание (thinning): сохраняйте каждый k-й сэмпл, чтобы уменьшить автокорреляцию.
• Масштаб предложения: слишком малый — цепь движется медленно (высокое принятие, медленное исследование); слишком большой — большинство предложений отвергается (низкое принятие, цепь застревает на месте).
• Оптимальная доля принятия для гауссовского предложения в высокой размерности примерно равна 0.234.

Сэмплирование Гиббса

Сэмплирование Гиббса — частный случай MCMC для многомерных распределений. Вместо предложения перемещения сразу во всех измерениях оно обновляет по одной переменной из её условного распределения.

Цель: p(x_1, x_2, ..., x_d)

Алгоритм:
  Для каждой итерации t:
    Сэмплировать x_1^{t+1} ~ p(x_1 | x_2^t, x_3^t, ..., x_d^t)
    Сэмплировать x_2^{t+1} ~ p(x_2 | x_1^{t+1}, x_3^t, ..., x_d^t)
    ...
    Сэмплировать x_d^{t+1} ~ p(x_d | x_1^{t+1}, x_2^{t+1}, ..., x_{d-1}^{t+1})

Сэмплирование Гиббса требует, чтобы вы могли сэмплировать из каждого условного распределения p(x_i | x_{-i}). Для многих моделей это просто:

• Байесовские сети: условные распределения следуют из структуры графа.
• Смеси гауссиан: условные распределения гауссовские.
• Модели Изинга: условное распределение каждого спина зависит только от его соседей.

Доля принятия всегда равна 1 (принимается каждое предложение), поскольку сэмплирование из точного условного распределения автоматически удовлетворяет детальному балансу.

Ограничение. Когда переменные сильно коррелированы, сэмплирование Гиббса смешивается медленно: обновление по одной переменной за раз не может делать большие диагональные перемещения по распределению.

Сэмплирование с температурой (используется в LLM)

Языковые модели выдают логиты z_1, …, z_V для каждого токена в словаре. Softmax преобразует их в вероятности. Температура масштабирует логиты перед softmax:

p_i = exp(z_i / T) / sum(exp(z_j / T))

T = 1.0: стандартный softmax (исходное распределение)
T -> 0:  argmax (детерминированный, всегда выбирает наибольший логит)
T -> inf: равномерное распределение (все токены равновероятны)
T < 1.0: заостряет распределение (больше уверенности, меньше разнообразия)
T > 1.0: сглаживает распределение (меньше уверенности, больше разнообразия)

Почему это работает. Деление логитов на T < 1 усиливает различия между ними. Если z_1 = 2 и z_2 = 1, то деление на T = 0.5 даёт z_1/T = 4 и z_2/T = 2, делая разрыв больше. После softmax токен с наибольшим логитом получает гораздо большую долю.

На практике:

• T = 0.0: жадное декодирование, лучше всего для фактологических вопросов и ответов.
• T = 0.3-0.7: немного креативности, хорошо для генерации кода.
• T = 0.7-1.0: баланс, хорошо для общего разговора.
• T = 1.0-1.5: творческое письмо, мозговой штурм.
• T > 1.5: всё более случайный результат, редко полезно.

Температура не меняет, какие токены возможны. Она меняет распределение вероятностной массы между ними.

Top-k-сэмплирование

Top-k-сэмплирование ограничивает множество кандидатов k токенами с наибольшими вероятностями, затем нормализует вероятности заново и сэмплирует из ограниченного множества.

Алгоритм:
  1. Вычислить softmax-вероятности для всех V токенов
  2. Отсортировать токены по вероятности (по убыванию)
  3. Оставить только k лучших токенов
  4. Нормализовать заново: p_i' = p_i / sum(p_j for j in top-k)
  5. Сэмплировать из нормализованного распределения

k = 1:  жадное декодирование
k = V:  без фильтрации (стандартное сэмплирование)
k = 40: типичная настройка, отсекает длинный хвост маловероятных токенов

Top-k не даёт модели выбирать крайне маловероятные токены (опечатки, бессмыслицу), находящиеся в длинном хвосте распределения словаря. Проблема в том, что k фиксировано независимо от контекста. Когда модель уверена (один токен имеет вероятность 95%), k = 40 всё равно допускает 39 альтернатив. Когда модель не уверена (вероятность распределена по 1000 токенам), k = 40 отсекает правдоподобные варианты.

Top-p-сэмплирование (nucleus sampling)

Top-p-сэмплирование динамически подстраивает размер множества кандидатов. Вместо фиксированного числа токенов оно сохраняет наименьшее множество токенов, суммарная вероятность которого превышает p.

Алгоритм:
  1. Вычислить softmax-вероятности для всех V токенов
  2. Отсортировать токены по вероятности (по убыванию)
  3. Найти наименьшее k, для которого сумма вероятностей top-k >= p
  4. Оставить только эти k токенов
  5. Нормализовать заново и сэмплировать

p = 0.9:  сохраняет токены, покрывающие 90% вероятностной массы
p = 1.0:  без фильтрации
p = 0.1:  очень строгое ограничение, почти жадное декодирование

Когда модель уверена, nucleus-сэмплирование сохраняет мало токенов (возможно, 2–3). Когда модель не уверена, оно сохраняет много токенов (возможно, 200). Благодаря этому адаптивному поведению nucleus-сэмплирование обычно даёт текст лучше, чем top-k.

Распространённые комбинации:

• Температура 0.7 + top-p 0.9: хорошая настройка общего назначения.
• Температура 0.0 (жадное декодирование): лучше всего для детерминированных задач.
• Температура 1.0 + top-k 50: настройка из исходной статьи Fan et al. (2018).

Top-k и top-p можно объединять. Сначала примените top-k, затем top-p к оставшемуся множеству.

Трюк репараметризации (используется в VAE)

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

Стандартное сэмплирование (недифференцируемое):
  z ~ N(mu, sigma^2)

  Случайность блокирует прохождение градиента.
  d/d_mu [sample from N(mu, sigma^2)] = ???

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

Репараметризованное сэмплирование:
  epsilon ~ N(0, 1)          (фиксированный случайный шум без параметров)
  z = mu + sigma * epsilon   (детерминированная функция параметров)

  Теперь z — детерминированная дифференцируемая функция mu и sigma.
  d(z)/d(mu) = 1
  d(z)/d(sigma) = epsilon

  Градиенты проходят через mu и sigma.

Это работает, потому что N(mu, sigma^2) имеет то же распределение, что и mu + sigma * N(0, 1). Ключевая идея: перенести случайность в источник без параметров (epsilon), а затем выразить сэмпл как дифференцируемое преобразование параметров.

В цикле обучения VAE:

1. Энкодер выдаёт mu и log(sigma^2) для каждого входа.
2. Сэмплируется epsilon ~ N(0, 1).
3. Вычисляется z = mu + sigma * epsilon.
4. z декодируется для восстановления входа.
5. Обратное распространение проходит через шаги 4, 3, 2, 1 (это возможно, потому что шаг 3 дифференцируем).

Без трюка репараметризации VAE нельзя обучать стандартным обратным распространением ошибки. Именно это наблюдение сделало VAE практичными.

Gumbel-Softmax (дифференцируемое категориальное сэмплирование)

Трюк репараметризации работает для непрерывных распределений (гауссовского). Для дискретных категориальных распределений нужен другой подход. Gumbel-Softmax предоставляет дифференцируемое приближение категориального сэмплирования.

Трюк Gumbel-Max (недифференцируемый):

Чтобы сэмплировать из категориального распределения с лог-вероятностями log(p_1), ..., log(p_k):
  1. Сэмплировать g_i ~ Gumbel(0, 1) для каждой категории
     (g = -log(-log(u)), где u ~ Uniform(0, 1))
  2. Вернуть argmax(log(p_i) + g_i)

Так получаются точные категориальные сэмплы.

Gumbel-Softmax (дифференцируемое приближение):

Замените жёсткий argmax мягким softmax:
  y_i = exp((log(p_i) + g_i) / tau) / sum(exp((log(p_j) + g_j) / tau))

tau (температура) управляет приближением:
tau -> 0:  приближается к one-hot-вектору (жёсткая категория)
tau -> inf: приближается к равномерному распределению (1/k, 1/k, ..., 1/k)
tau = 1.0: мягкое приближение

Gumbel-Softmax создаёт непрерывную релаксацию дискретного сэмпла. Результат — вектор вероятностей (мягкий one-hot), а не жёсткий one-hot. Градиенты проходят через softmax. Во время прямого прохода обучения можно использовать оцениватель «straight-through»: взять жёсткий argmax для прямого прохода, но мягкие градиенты Gumbel-Softmax для обратного прохода.

Применения:

• Дискретные скрытые переменные в VAE.
• Поиск архитектуры нейросети (выбор дискретных операций).
• Механизмы жёсткого внимания.
• Обучение с подкреплением с дискретными действиями.

Стратифицированное сэмплирование

Стандартное Монте-Карло-сэмплирование может случайно оставлять пробелы в пространстве сэмплов. Стратифицированное сэмплирование обеспечивает равномерное покрытие, разделяя пространство на страты и выбирая сэмплы из каждой.

Стандартное Монте-Карло:
  Сэмплировать N точек равномерно из [0, 1]
  В одних областях могут возникнуть кластеры, в других — пробелы

Стратифицированное сэмплирование:
  Разделить [0, 1] на N равных страт: [0, 1/N), [1/N, 2/N), ..., [(N-1)/N, 1)
  Сэмплировать одну точку равномерно внутри каждой страты
  x_i = (i + u_i) / N   где u_i ~ Uniform(0, 1),  i = 0, ..., N-1

Стратифицированное сэмплирование всегда имеет меньшую или равную дисперсию по сравнению со стандартным Монте-Карло:

Var(stratified) <= Var(standard Monte Carlo)

Улучшение наибольшее, когда f(x) меняется плавно.
Для кусочно-постоянных функций стратифицированное сэмплирование точно.

Применения:

• Численное интегрирование (квази-Монте-Карло).
• Разделения обучающих данных (обеспечение баланса классов в каждом фолде).
• Важностное сэмплирование со стратификацией (сочетание обеих техник).
• NeRF (Neural Radiance Fields) использует стратифицированное сэмплирование вдоль лучей камеры.

Связь с диффузионными моделями

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

Прямой процесс (известный):
  x_t = sqrt(alpha_t) * x_{t-1} + sqrt(1 - alpha_t) * epsilon
  где epsilon ~ N(0, I)

  После T шагов: x_T ~ N(0, I)  (чистый шум)

Обратный процесс (выученный):
  x_{t-1} = (1/sqrt(alpha_t)) * (x_t - (1 - alpha_t)/sqrt(1 - alpha_bar_t) * epsilon_theta(x_t, t)) + sigma_t * z
  где z ~ N(0, I)

  Каждый шаг удаления шума — это шаг сэмплирования.

Связь с методами из этого урока:

• Каждый шаг удаления шума использует трюк репараметризации (сэмплирование шума и применение детерминированного преобразования).
• Расписание шума {alpha_t} управляет формой температурного отжига.
• Обучение использует оценивание Монте-Карло для приближения ELBO (evidence lower bound).
• Предковое сэмплирование в диффузионных моделях — это марковская цепь (каждый шаг зависит только от текущего состояния).

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

monte-carlo-pi

Соберите это

Шаг 1: Равномерное сэмплирование и обратная CDF

import math
import random

def sample_uniform(a, b):
    return a + (b - a) * random.random()

def sample_exponential_inverse_cdf(lam):
    u = random.random()
    return -math.log(u) / lam

Сгенерируйте 10 000 экспоненциальных сэмплов и убедитесь, что среднее равно 1/lambda.

Шаг 2: Сэмплирование с отбраковкой

def rejection_sample(target_pdf, proposal_sample, proposal_pdf, M):
    while True:
        x = proposal_sample()
        u = random.random()
        if u < target_pdf(x) / (M * proposal_pdf(x)):
            return x

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

Шаг 3: Важностное сэмплирование

def importance_sampling_estimate(f, target_pdf, proposal_pdf, proposal_sample, n):
    total = 0
    for _ in range(n):
        x = proposal_sample()
        w = target_pdf(x) / proposal_pdf(x)
        total += f(x) * w
    return total / n

Оцените E[X^2] при нормальном распределении, используя равномерное предложение. Сравните с известным ответом (mu^2 + sigma^2).

Шаг 4: Оценивание pi методом Монте-Карло

def monte_carlo_pi(n):
    inside = 0
    for _ in range(n):
        x = random.uniform(-1, 1)
        y = random.uniform(-1, 1)
        if x*x + y*y <= 1:
            inside += 1
    return 4 * inside / n

Шаг 5: MCMC Метрополиса — Гастингса

def metropolis_hastings(target_log_pdf, proposal_sample, proposal_log_pdf, x0, n_samples, burn_in):
    samples = []
    x = x0
    for i in range(n_samples + burn_in):
        x_new = proposal_sample(x)
        log_alpha = (target_log_pdf(x_new) + proposal_log_pdf(x, x_new)
                     - target_log_pdf(x) - proposal_log_pdf(x_new, x))
        if math.log(random.random()) < log_alpha:
            x = x_new
        if i >= burn_in:
            samples.append(x)
    return samples

Сэмплируйте из бимодального распределения (смеси двух гауссиан). Визуализируйте траекторию цепи.

Шаг 6: Сэмплирование Гиббса

def gibbs_sampling_2d(conditional_x_given_y, conditional_y_given_x, x0, y0, n_samples, burn_in):
    x, y = x0, y0
    samples = []
    for i in range(n_samples + burn_in):
        x = conditional_x_given_y(y)
        y = conditional_y_given_x(x)
        if i >= burn_in:
            samples.append((x, y))
    return samples

Шаг 7: Сэмплирование с температурой

def softmax(logits):
    max_l = max(logits)
    exps = [math.exp(z - max_l) for z in logits]
    total = sum(exps)
    return [e / total for e in exps]

def temperature_sample(logits, temperature):
    scaled = [z / temperature for z in logits]
    probs = softmax(scaled)
    return sample_from_probs(probs)

Покажите, как температура меняет выходное распределение для набора логитов токенов.

Шаг 8: Top-k- и top-p-сэмплирование

def top_k_sample(logits, k):
    indexed = sorted(enumerate(logits), key=lambda x: -x[1])
    top = indexed[:k]
    top_logits = [l for _, l in top]
    probs = softmax(top_logits)
    idx = sample_from_probs(probs)
    return top[idx][0]

def top_p_sample(logits, p):
    probs = softmax(logits)
    indexed = sorted(enumerate(probs), key=lambda x: -x[1])
    cumsum = 0
    selected = []
    for token_idx, prob in indexed:
        cumsum += prob
        selected.append((token_idx, prob))
        if cumsum >= p:
            break
    sel_probs = [pr for _, pr in selected]
    total = sum(sel_probs)
    sel_probs = [pr / total for pr in sel_probs]
    idx = sample_from_probs(sel_probs)
    return selected[idx][0]

Шаг 9: Трюк репараметризации

def reparam_sample(mu, sigma):
    epsilon = random.gauss(0, 1)
    return mu + sigma * epsilon

def reparam_gradient(mu, sigma, epsilon):
    dz_dmu = 1.0
    dz_dsigma = epsilon
    return dz_dmu, dz_dsigma

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

Шаг 10: Gumbel-Softmax

def gumbel_sample():
    u = random.random()
    return -math.log(-math.log(u))

def gumbel_softmax(logits, temperature):
    gumbels = [math.log(p) + gumbel_sample() for p in logits]
    return softmax([g / temperature for g in gumbels])

Покажите, как уменьшение температуры приближает выход к one-hot-вектору.

Полные реализации со всеми визуализациями находятся в code/sampling.py.

Используйте это

С NumPy и SciPy используйте производственные версии:

import numpy as np

rng = np.random.default_rng(42)

exponential_samples = rng.exponential(scale=2.0, size=10000)
print(f"Exponential mean: {exponential_samples.mean():.4f} (expected 2.0)")

from scipy import stats
normal = stats.norm(loc=0, scale=1)
print(f"CDF at 1.96: {normal.cdf(1.96):.4f}")
print(f"Inverse CDF at 0.975: {normal.ppf(0.975):.4f}")

logits = np.array([2.0, 1.0, 0.5, 0.1, -1.0])
temperature = 0.7
scaled = logits / temperature
probs = np.exp(scaled - scaled.max()) / np.exp(scaled - scaled.max()).sum()
token = rng.choice(len(logits), p=probs)
print(f"Sampled token index: {token}")

Для масштабного MCMC используйте специализированные библиотеки:

• PyMC: полное байесовское моделирование с NUTS (адаптивный HMC).
• emcee: ансамблевый MCMC-сэмплер.
• NumPyro/JAX: MCMC с ускорением на GPU.

Вы построили эти методы с нуля. Теперь вы знаете, что делают вызовы библиотек.

Упражнения

1. Реализуйте сэмплирование через обратную CDF для распределения Коши. CDF равна F(x) = 0.5 + arctan(x)/pi. Сгенерируйте 10 000 сэмплов и постройте гистограмму поверх истинной PDF. Обратите внимание на тяжёлые хвосты (экстремальные значения далеко от центра).

2. Используйте сэмплирование с отбраковкой для генерации сэмплов из распределения Beta(2, 5), используя предложение Uniform(0, 1). Постройте принятые сэмплы поверх истинной Beta PDF. Какова теоретическая доля принятия?

3. Оцените интеграл sin(x) от 0 до pi методом Монте-Карло с 1 000, 10 000 и 100 000 сэмплов. Сравните ошибку на каждом уровне. Убедитесь, что ошибка масштабируется как O(1/sqrt(N)).

4. Реализуйте Метрополиса — Гастингса для выборки из двумерного распределения p(x, y), пропорционального exp(-(x^2 * y^2 + x^2 + y^2 - 8x - 8y) / 2). Постройте сэмплы и траекторию цепи. Поэкспериментируйте с разными стандартными отклонениями предложения.

5. Создайте полную демонстрацию генерации текста: для словаря из 10 слов с логитами сгенерируйте последовательности из 20 токенов с помощью (a) жадного декодирования, (b) temperature=0.7, (c) top-k=3, (d) top-p=0.9. Сравните разнообразие результатов в 5 запусках.

Ключевые термины

Термин	Как обычно говорят	Что это на самом деле означает
Сэмплирование	«Извлечение случайных значений»	Генерация значений согласно распределению вероятностей. Механизм, лежащий в основе всего генеративного ИИ
Равномерное распределение	«Все одинаково вероятны»	Каждое значение в [a, b] имеет одинаковую плотность вероятности 1/(b-a). Начальная точка для всех методов сэмплирования
Обратная CDF	«Преобразование вероятности»	F_inverse(U) преобразует равномерный сэмпл в сэмпл из любого распределения с известной CDF. Точно и эффективно
Сэмплирование с отбраковкой	«Предложить и принять/отклонить»	Генерировать из простого предложения, принимать с вероятностью, пропорциональной отношению цель/предложение. Точно, но тратит сэмплы впустую
Важностное сэмплирование	«Перевзвесить сэмплы»	Оценивать ожидания по p(x), используя сэмплы из q(x) и взвешивая каждый на p(x)/q(x). Основа PPO в RL
Монте-Карло	«Усреднить случайные сэмплы»	Приближать интегралы средними по сэмплам. Ошибка O(1/sqrt(N)) независимо от размерности
MCMC	«Случайное блуждание, которое сходится»	Построить марковскую цепь со стационарным целевым распределением. Метрополис — Гастингс — фундаментальный алгоритм
Метрополис — Гастингс	«Принимать подъём, иногда — спуск»	Предлагать перемещения, принимать по отношению плотностей. Детальный баланс обеспечивает сходимость к целевому распределению
Сэмплирование Гиббса	«По одной переменной за раз»	Обновлять каждую переменную из её условного распределения, удерживая остальные фиксированными. Доля принятия 100%
Температура	«Регулятор уверенности»	Делит логиты на T перед softmax. T<1 заостряет (больше уверенности), T>1 сглаживает (больше разнообразия)
Top-k-сэмплирование	«Оставить k лучших»	Обнулить всё, кроме k токенов с наибольшей вероятностью, нормализовать и сэмплировать. Фиксированный размер множества кандидатов
Nucleus-сэмплирование (top-p)	«Оставить вероятные»	Оставить наименьшее множество токенов, чья накопленная вероятность превышает p. Адаптивный размер множества кандидатов
Трюк репараметризации	«Вынести случайность наружу»	Записать z = mu + sigma * epsilon, где epsilon ~ N(0,1). Делает сэмплирование дифференцируемым. Необходим для обучения VAE
Gumbel-Softmax	«Мягкое категориальное сэмплирование»	Дифференцируемое приближение категориального сэмплирования: шум Гумбеля + softmax с температурой
Стратифицированное сэмплирование	«Принудительное покрытие»	Разделить пространство сэмплов на страты и сэмплировать из каждой. Всегда меньшая дисперсия, чем у наивного Монте-Карло
Разогрев (burn-in)	«Период прогрева»	Начальные MCMC-сэмплы, отбрасываемые до того, как цепь достигнет стационарного распределения
Детальный баланс	«Условие обратимости»	p(x) * T(x->y) = p(y) * T(y->x). Достаточное условие, чтобы p было стационарным распределением марковской цепи
Диффузионное сэмплирование	«Итеративное удаление шума»	Генерация данных из шума путём применения выученных шагов удаления шума. Каждый шаг — условная операция сэмплирования

Дополнительное чтение

• Holbrook (2023): алгоритм Метрополиса — Гастингса — подробный учебник по основам MCMC.
• Jang, Gu, Poole (2017): категориальная репараметризация с Gumbel-Softmax — исходная статья о Gumbel-Softmax.
• Holtzman et al. (2020): любопытный случай деградации текста нейросети — статья о nucleus-сэмплировании (top-p).
• Kingma & Welling (2014): Auto-Encoding Variational Bayes — статья о VAE, в которой представлен трюк репараметризации.
• Ho, Jain, Abbeel (2020): вероятностные диффузионные модели удаления шума — DDPM связывает сэмплирование с генерацией изображений.

---

Источник: Sampling Methods · ревизия c8b9b9244f3210b840776675175662dacf208264

← 01.15 — Статистика для машинного обучения · Фаза 1 — Математические основы · Полный каталог · 01.17 — Линейные системы →