Математика рекомендаций: исследование Воутера Кулена 0:09
Современные алгоритмы машинного обучения, отвечающие за выбор контента в лентах соцсетей или подбор лечения в медицине, опираются на фундаментальную концепцию «задачи о многоруком бандите» (multi-armed bandit). В ходе глубокого интервью для канала Machine Learning Street Talk доктор Воутер Кулен (Wouter Koolen) из CWI Amsterdam объяснил, почему эта абстрактная модель, возникшая как попытка описать выбор между немедленной выгодой и поиском новой информации, остается «золотым стандартом» для понимания принятия решений.
🎰 Что такое многорукий бандит? 1:02
Аналогия с игорным залом, где игроку нужно решить, на какой рычаг нажать и как часто это делать, чтобы максимизировать выигрыш, стала классической метафорой. По словам Кулена, каждый «рычаг» (arm) — это источник данных, скрывающий неизвестное распределение вероятностей.
Ключевым для теории является конфликт между исследованием (exploration) и эксплуатацией (exploitation):
- Эксплуатация: Использование имеющихся знаний для максимизации награды (например, чаще выдавать контент, который уже нравится пользователю).
- Исследование: Поиск новых возможностей, чтобы собрать больше информации, даже если это временно снижает награду.
Кулен подчеркивает, что задача о бандите — это «упрощенная версия» проблем, которые мы действительно хотим решать: от разработки вакцин до управления сложными системами ИИ, такими как Monte Carlo Tree Search (MCTS), используемый в AlphaGo.
🧪 Разница между максимизацией награды и чистым исследованием 4:18
Одной из центральных тем обсуждения стало различие целей. Кулен выделяет режим чистого исследования (pure exploration), где целью не является получение награды «здесь и сейчас».
- В клинических испытаниях (например, при тестировании вакцин против COVID-19) приоритет — найти максимально эффективный препарат для масштабирования на миллиарды людей, а не вылечить конкретных пациентов, участвующих в тесте.
- В режиме максимизации награды (regret minimization) алгоритм играет оптимальную стратегию логарифмически часто, в то время как в режиме чистого исследования (pure exploration) он вынужден тестировать даже «плохие» варианты линейно часто — фиксированную долю времени — чтобы убедиться в их неэффективности.
Собеседники пришли к выводу, что это создает неразрешимое противоречие: алгоритм, оптимальный для одной задачи, крайне плохо справляется с другой.
🛠 Мечта о «компиляторе чистого исследования» 10:32
Воутер Кулен представил свою концепцию «компилятора чистого исследования» — инструмента, который позволял бы задавать структуру проблемы и априорные знания в виде контракта или доменного языка.
- Пользователь формулирует задачу (например, «найти лучшую руку» или «найти оптимальное действие в игровом дереве»).
- Система использует нижние границы (lower bounds) для вычисления оптимальной стратегии распределения выборок.
- Алгоритм выдает готовую стратегию, не требуя от исследователя написания кода «с нуля».
На данный момент, по признанию гостя, область еще не обладает «полным каталогом» методов, и каждый новый тип задачи требует оригинальных математических «трюков». Одним из таких элегантных трюков Кулен называет метод Murphy sampling (сэмплирование Мерфи), который позволяет эффективно решать задачи выбора в условиях, где часть вариантов контролируется «противником».
🤖 Применимость в Deep Learning и реальных системах
Дискуссия затронула и современные вопросы масштабируемости. Кулен объяснил, что добавление признаков (features) превращает обычного бандита в контекстный бандит (contextual bandit), где задача — обучить функцию отображения от признаков пользователя к лучшему решению.
- Использование методов типа FTRL (Follow The Regularized Leader) или Mirror Descent позволяет оптимизировать алгоритмы в условиях, когда пространство параметров бесконечно или крайне велико.
- Кулен отметил, что при работе с матрицами признаков (например, в нейросетях) эффективным подходом является их аппроксимация низкоранговой факторизацией, что позволяет удерживать «логарифмическое сожаление» по важным измерениям, жертвуя точностью на малозначимых.
В завершение гость подчеркнул, что в индустрии часто наблюдается упрощенный подход (например, A/B-тесты), но с развитием теории бандитов мы приближаемся к созданию алгоритмов, способных к «ускоренному обучению» (accelerated learning), которые могут объективно улучшить принятие решений в таких критических областях, как социальная политика и медицина.
