Мартингальный ядерный тест двух выборок

Основная информация

• ID статьи: 2510.11853
• Название: A Martingale Kernel Two-Sample Test
• Авторы: Anirban Chatterjee (University of Chicago), Aaditya Ramdas (Carnegie Mellon University)
• Классификация: stat.ME, math.ST, stat.TH
• Дата публикации: 13 октября 2025 г.
• Ссылка на статью: https://arxiv.org/abs/2510.11853

Аннотация

Максимальное среднее расхождение (Maximum Mean Discrepancy, MMD) — широко используемая многомерная метрика расстояния в тестах двух выборок. Стандартная статистика теста MMD имеет сложное нулевое распределение, обычно требующее дорогостоящих методов переборки или перестановки для калибровки. В данной работе, используя мартингальную интерпретацию оценки квадрата MMD, предлагается мартингальный MMD (mMMD) — квадратичная по времени статистика с предельным стандартным гауссовым распределением при нулевой гипотезе. Кроме того, доказывается, что тест является состоятельным для любой фиксированной альтернативной гипотезы, а при больших объёмах выборок mMMD обеспечивает значительную вычислительную экономию по сравнению со стандартным тестом MMD с минимальной потерей мощности.

Исследовательский контекст и мотивация

Описание проблемы

Тест двух выборок — классическая задача в статистике, целью которой является проверка равенства двух распределений P и Q на основе независимых выборок: $H_0: P = Q \quad \text{vs} \quad H_1: P \neq Q$

Ограничения существующих методов

1. Параметрические методы: часто дают сбой при неправильной спецификации модели или на неевклидовых данных
2. Классические непараметрические методы: в основном применимы к одномерным данным, многомерные расширения затруднены
3. Стандартный тест MMD: нулевое распределение представляет собой сумму бесконечно взвешенных переменных χ², веса зависят от неизвестного распределения, требует вычислительно интенсивных методов переборки или перестановки

Исследовательская мотивация

• MMD как метод ядра показывает хорошие результаты при обнаружении различий в распределениях в общих областях
• Определение порога τα является ключевой практической проблемой для теста MMD
• Существующие параметрические приближения на основе моментов не имеют гарантий состоятельности или точности
• Необходим эффективный альтернативный метод с управляемым нулевым распределением

Основные вклады

1. Предложение теста mMMD: новый вариант MMD на основе мартингальной структуры с гауссовым нулевым распределением
2. Теоретические гарантии:
   • Доказана асимптотическая нормальность при нулевой гипотезе (теоремы 2, 3)
   • Установлена состоятельность для фиксированных альтернативных гипотез (теоремы 6, 7)
   • Получена сходимость распределения при альтернативной гипотезе (теорема 8)
3. Вычислительная эффективность: избегает переборки, сохраняет сложность O(n²), но значительно снижает фактическое время выполнения
4. Расширенные приложения:
   • Многоядерный тест (mmMMD)
   • Обобщённое семейство статистик Tn,γ, включающее стандартный MMD и mMMD как частные случаи

Подробное описание методологии

Определение задачи

Даны независимые выборки из двух распределений P и Q в метрическом пространстве X:

• Xn = {X₁, ..., Xn} ~ P
• Yn = {Y₁, ..., Yn} ~ Q

Цель: проверить H₀: P = Q vs H₁: P ≠ Q

Ключевая идея: мартингальная структура

Ключевое наблюдение: модифицированная форма оценки квадрата MMD имеет мартингальную структуру.

Метод функции-свидетеля:

• Теоретически оптимальная функция-свидетель: f₀ = (νP - νQ)/‖νP - νQ‖K
• Для каждого 2 ≤ i ≤ n используется оценка на основе исторических данных: $\hat{f}_i = \frac{1}{i}\sum_{j=1}^{i-1}[K(X_j, \cdot) - K(Y_j, \cdot)]$

Статистика mMMD

$T_n := \frac{1}{n}\sum_{i=2}^n \langle \hat{f}_i, K(X_i, \cdot) - K(Y_i, \cdot) \rangle_K$

Используя ядерный трюк, можно упростить до: $T_n = \frac{1}{n}\sum_{i=2}^n \frac{1}{i}\sum_{j=1}^{i-1}[K(X_i, X_j) - K(X_i, Y_j) - K(X_j, Y_i) + K(Y_i, Y_j)]$

Нормализованная статистика

Для достижения асимптотической нормальности определяется оценка дисперсии: $\sigma_n^2 := \frac{1}{n^2}\sum_{i=2}^n \left(\frac{1}{i}\sum_{j=1}^{i-1}K(X_i, X_j) - K(X_i, Y_j) - K(X_j, Y_i) + K(Y_i, Y_j)\right)^2$

Итоговая тестовая статистика: $\eta_n = T_n/\sigma_n$

Правило принятия решения

$\Psi_n := \mathbf{1}\{\eta_n > z_{1-\alpha}\}$ где z₁₋α — квантиль уровня (1-α) стандартного нормального распределения.

Технические инновации

1. Идентификация мартингальной структуры: впервые выявлена мартингальная разностная последовательность в оценке MMD
2. Избежание переборки: использование мартингальной центральной предельной теоремы для прямого получения гауссова распределения
3. Независимость от размерности: при надлежащих условиях нулевое распределение не зависит от размерности данных
4. Унифицированная структура: семейство Tn,γ объединяет различные варианты MMD

Экспериментальная установка

Эксперименты по проверке теории

Проверка нулевого распределения:

• Размерность: d ∈ {10, 100, 250, 500}
• Распределения данных: Nd(0d, Id) и td(10)
• Ядерные функции: гауссово и лапласово ядра (пропускная способность по медианной эвристике)
• Объём выборки: n = 200, 2000 повторений

Эксперименты по сравнению мощности

Установка:

• P = Nd(0d, Id), Q = Nd(μd,j,ε, Id)
• Конфигурации: (d,j,ε) = (10,5,0.3), (50,5,0.3), (100,5,0.5)
• Методы сравнения: стандартный MMD, линейный MMD (LMMD), блочный MMD (BMMD), кросс-MMD (xMMD), BetMMD

Эксперименты на реальных данных

Набор данных MNIST:

• 5 групп сравнения цифр: постепенно возрастающее перекрытие
• 100 образцов на группу, 100 повторений
• Уровень значимости: α = 0,05

Многоядерные эксперименты

Конфигурация:

• mmMMD Gauss: 3 гауссовых ядра, пропускная способность (1,2,4)λmed
• mmMMD Laplace: 3 лапласовых ядра, одинаковая пропускная способность
• mmMMD Mixed: смешанные гауссовы и лапласовы ядра

Результаты экспериментов

Проверка нулевого распределения

• Основной результат: эмпирическое распределение ηn тесно совпадает со стандартным гауссовым распределением во всех установках
• Робастность: результаты демонстрируют устойчивость к распределению данных, выбору ядра и размерности
• Преимущество сравнения: резкий контраст со сложным нулевым распределением стандартного MMD

Сравнение мощности

Ключевые результаты:

• Мощность mMMD близка к стандартному MMD, превосходит другие вычислительно эффективные варианты
• Производительность сравнима с xMMD, но избегает разделения выборки

Вычислительная эффективность

Результат: mMMD примерно в 100 раз быстрее стандартного MMD, сравним с другими эффективными методами.

Результаты эксперимента MNIST

• Тенденция: мощность всех методов снижается с увеличением номера группы (возрастающее перекрытие)
• Ранжирование производительности: mMMD и xMMD > BMMD > LMMD
• Практическое значение: подтверждает теоретические преимущества на реальных данных

Связанные работы

Развитие ядерных тестов двух выборок

1. Ранние методы: консервативные методы на основе больших отклонений
2. Спектральные методы: спектральное приближение Gretton et al. (2009), требующее сильных предположений
3. Неполные U-статистики: линейный MMD, блочный MMD и т.д.
4. Стратегии разделения выборки: Kübler et al. (2022), Shekhar et al. (2022)

Относительные преимущества данной работы

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

Заключение и обсуждение

Основные выводы

1. Теоретический вклад: впервые использована мартингальная структура для построения теста MMD со стандартным гауссовым нулевым распределением
2. Практическая ценность: значительное снижение вычислительных затрат при сохранении хорошей статистической производительности
3. Расширяемость: структура может быть расширена на многоядерные установки и более общие семейства статистик

Ограничения

1. Теоретические ограничения:
   • Выбор пропускной способности по медианной эвристике не имеет теоретической поддержки
   • Минимаксная оптимальность при γ > 1/2 не определена
2. Практические ограничения:
   • По-прежнему требуется сложность O(n²)
   • В некоторых установках мощность немного ниже стандартного MMD

Направления будущих исследований

1. Теоретические расширения:
   • Теоретические гарантии для зависящих от данных ядер
   • Применимость к более общим ядерным функциям
   • Полная характеристика минимаксной оптимальности
2. Улучшения методов:
   • Комбинация с техниками приближения ядер для снижения сложности
   • Расширение на тесты независимости
   • Приложения к тестам на основе расстояний

Глубокая оценка

Преимущества

1. Высокая инновативность: мартингальная перспектива — новый вклад в исследование MMD
2. Теоретическая строгость: полная асимптотическая теория, включая сходимость типа Берри-Эссена
3. Высокая практическая ценность: решает практическую вычислительную узкую точку тестов MMD
4. Полные эксперименты: всестороннее оценивание от теоретической проверки до реальных приложений
5. Ясное изложение: хороший баланс между техническими деталями и интуитивными объяснениями

Недостатки

1. Теоретические пробелы: анализ зависящих от данных пропускных способностей неполный
2. Потеря мощности: мощность действительно ниже стандартного MMD в некоторых случаях
3. Область применения: в основном проверена на евклидовых пространствах
4. Вычислительная сложность: остаётся O(n²), не достигнуто принципиального улучшения

Влияние

1. Академическая ценность: предоставляет новую перспективу для теории MMD, может вдохновить больше мартингальных методов
2. Практическая ценность: непосредственно применима к крупномасштабным задачам тестирования двух выборок
3. Воспроизводимость: метод прост и ясен, легко реализуется и проверяется
4. Расширяемость: структура имеет хороший потенциал расширения

Сценарии применения

1. Крупномасштабные данные: явные преимущества вычислительной эффективности
2. Высокомерные данные: преимущества независимого от размерности нулевого распределения
3. Приложения в реальном времени: требования к немедленности без тестов перестановки
4. Многоядерные сценарии: mmMMD имеет преимущества при неопределённости выбора ядра

Библиография

1. Gretton, A., et al. (2012a). A kernel two-sample test. JMLR, 13(1), 723-773.
2. Shekhar, S., Kim, I., & Ramdas, A. (2022). A permutation-free kernel two-sample test. NeurIPS, 35, 18168-18180.
3. Li, T. & Yuan, M. (2024). On the optimality of Gaussian kernel based nonparametric tests against smooth alternatives. JMLR, 25(334), 1-62.
4. Fan, X. & Shao, Q. M. (2018). Berry–Esseen bounds for self-normalized martingales. Communications in Mathematics and Statistics, 6(1), 13-27.

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