1. Основы комбинаторики и классическое определение вероятности в контексте анализа данных
Основы комбинаторики и классическое определение вероятности в контексте анализа данных
Представьте, что вы проектируете систему биометрической идентификации по лицу. Ваша модель должна распознать пользователя среди 10 000 сотрудников компании. Какова вероятность того, что система случайно перепутает двух людей, если она опирается на 15 ключевых точек лица? Или другой пример: вы проводите A/B-тестирование нового интерфейса интернет-магазина. Из 1000 посетителей 50 совершили покупку. Является ли это случайным шумом или реальным трендом? Чтобы ответить на эти вопросы, нам нужно научиться считать. Считать не просто количество объектов, а количество возможных сценариев развития событий. Именно здесь дисциплина «комбинаторика» превращается из абстрактной математики в фундамент машинного обучения.
Пространство элементарных исходов и случайное событие
Прежде чем переходить к формулам, необходимо договориться о терминах. В основе теории вероятностей лежит понятие «эксперимента» или «опыта». Это любое действие, результат которого невозможно предсказать заранее со 100% уверенностью.
Множество всех возможных взаимоисключающих результатов опыта называется пространством элементарных исходов и обычно обозначается греческой буквой (омега). Каждый отдельный результат внутри этого множества — это элементарный исход .
> Случайное событие — это любое подмножество пространства элементарных исходов. Мы говорим, что событие произошло, если результатом опыта стал один из элементарных исходов, входящих в .
Рассмотрим это на примере задачи классификации в Machine Learning. Допустим, модель предсказывает категорию электронного письма: «Спам» или «Не спам».
Классическое определение вероятности, сформулированное еще Пьером-Симоном Лапласом, гласит: если все элементарные исходы равновозможны, то вероятность события равна отношению числа благоприятных исходов к общему числу исходов.
В этой формуле:
Важное ограничение: эта формула работает только тогда, когда исходы равновозможны. Если мы подбрасываем «честную» монету, вероятность выпадения орла , так как исходов всего два, и они симметричны. Но если мы оцениваем вероятность того, что завтра пойдет дождь, мы не можем просто сказать «либо пойдет, либо нет, значит », так как эти исходы не равновероятны и зависят от множества факторов. В ML мы часто стремимся свести сложные задачи к подсчету таких исходов или оценке их частоты.
Правила сложения и умножения: логика комбинаторного счета
Чтобы эффективно использовать классическое определение вероятности, нужно уметь быстро вычислять и . В Data Science объемы данных огромны, и перечислять все варианты вручную невозможно. Комбинаторика базируется на двух фундаментальных правилах.
Правило суммы
Если объект можно выбрать способами, а объект можно выбрать способами, причем выборы и взаимно исключают друг друга, то выбрать «либо , либо » можно способами.Пример из ML: У вас есть две папки с данными для обучения. В первой — 150 изображений кошек, во второй — 200 изображений собак. Вы хотите выбрать одно любое изображение для проверки корректности загрузки. У вас есть вариантов выбора.
Правило произведения
Если объект можно выбрать способами, и после каждого такого выбора объект можно выбрать способами, то пару объектов в указанном порядке можно выбрать способами.Пример из ML: Вы проектируете нейронную сеть. У вас есть 3 варианта функции активации для первого слоя (ReLU, Sigmoid, Tanh) и 4 варианта для второго слоя. Сколько уникальных комбинаций архитектур из двух слоев вы можете составить? Согласно правилу произведения: комбинаций.
Это правило масштабируется на любое количество шагов. Если вы выбираете гиперпараметры модели:
Размещения, перестановки и сочетания
Когда мы работаем с наборами данных, нам важно понимать: важен ли порядок элементов и могут ли они повторяться. В зависимости от этого выделяют три основных типа комбинаций.
Перестановки (Permutations)
Перестановки отвечают на вопрос: «Сколькими способами можно упорядочить различных объектов?».Представьте, что у вас есть 5 признаков (features) в таблице данных: «Возраст», «Доход», «Пол», «Город», «Стаж». Вы хотите проверить, влияет ли порядок подачи этих признаков в модель на её точность. Количество способов расставить эти 5 признаков в разном порядке вычисляется через факториал:
Для наших 5 признаков это будет вариантов. Важно помнить, что по определению. Рост факториала очень стремительный: — это уже более 3.6 миллионов. Именно поэтому в задачах оптимизации (например, поиск кратчайшего пути для курьера между 20 точками) полный перебор всех перестановок невозможен даже для суперкомпьютеров.
Размещения (Arrangements)
Размещения нужны тогда, когда мы выбираем объектов из и нам важен их порядок.Допустим, в вашем отделе Data Science работают 10 специалистов. Вам нужно выбрать двоих: один будет «Тимлидом», а второй — «Рецензентом кода». Здесь порядок важен, так как роли разные. Количество способов сделать такой выбор:
В нашем случае: вариантов. Если бы мы просто выбирали двух человек в рабочую группу без распределения ролей, количество вариантов было бы меньше, так как пара (Иван, Мария) и (Мария, Иван) считались бы одним и тем же исходом.
Сочетания (Combinations)
Это самый важный инструмент для аналитика данных. Сочетания используются, когда мы выбираем объектов из и порядок не имеет значения.Вернемся к признакам. У вас есть 100 доступных признаков в базе данных, но вычислительные мощности позволяют использовать в модели только 10. Порядок признаков внутри этой десятки не важен. Сколько существует способов выбрать такой набор?
Формула сочетаний (биномиальный коэффициент):
Разберем на малом примере: выбрать 3 признака из 5.
В контексте ML сочетания постоянно встречаются в методах случайного леса (Random Forest), где каждое дерево строится на случайном подмножестве признаков, или в кросс-валидации (k-fold cross-validation), когда мы делим данные на блоки.
Комбинаторика с повторениями
В реальности мы часто сталкиваемся с ситуациями, где объекты могут дублироваться.
Перестановки с повторениями
Если у нас есть набор из элементов, среди которых элементов первого типа, — второго и так далее, то количество уникальных перестановок будет:Пример: У вас есть результаты 10 запусков модели: 7 раз она выдала «Успех» и 3 раза — «Отказ». Сколькими способами эти результаты могли распределиться во времени?
Сочетания с повторениями
Представьте, что вы создаете синтетический датасет. У вас есть 3 типа аномалий в данных (пропуски, выбросы, неверный формат). Вам нужно составить выборку из 5 инцидентов для тестирования системы обработки ошибок, при этом типы аномалий в выборке могут повторяться. Количество способов:Для нашего примера ( типа, элементов в выборке):
Геометрическое определение вероятности
Классическое определение пасует, когда количество исходов бесконечно. Например, какова вероятность того, что время обработки запроса сервером составит ровно 120.5000... миллисекунд? В непрерывной среде вероятность конкретной точки равна нулю.
В таких случаях мы переходим к геометрической вероятности. Если результат опыта определяется случайным выбором точки в некоторой области (на прямой, плоскости или в пространстве), то вероятность события (попадание в подобласть ) пропорциональна мере этой области (длине, площади, объему).
Кейс из анализа данных: Представьте, что рекламный баннер показывается пользователю в случайный момент времени в течение часа (60 минут). Какова вероятность, что пользователь увидит баннер в первые 10 минут? Здесь — это отрезок , а событие — отрезок . .
В машинном обучении это понимание критично при работе с непрерывными случайными величинами и функциями плотности распределения, о которых мы будем говорить в следующих главах.
Применение комбинаторики в оценке качества моделей
Рассмотрим классическую задачу на собеседованиях. У вас есть бинарный классификатор. Вы подаете ему на вход 10 объектов, 5 из которых принадлежат классу «1», а 5 — классу «0». Модель выдает предсказания случайным образом (просто подбрасывает монету). Какова вероятность того, что модель случайно угадает все 10 меток правильно?
Это очень маленькое число. Если ваша модель показала 100% точность на 10 объектах, вы можете быть почти уверены, что это не результат случайного угадывания. Но что если модель ошиблась один раз? Количество способов ошибиться ровно в одном объекте из 10 равно числу сочетаний . Тогда вероятность «почти идеального» случайного предсказания (9 из 10): . Это все еще меньше 1%, что в статистике часто считается порогом значимости.
Парадокс дней рождения в хешировании данных
В Data Engineering часто используется хеширование для распределения данных по бакетам (корзинам). Важной проблемой является «коллизия» — ситуация, когда два разных объекта получают один и тот же хеш-код. Комбинаторная природа этой проблемы лучше всего описывается парадоксом дней рождения.
Вопрос: Сколько человек должно быть в комнате, чтобы вероятность того, что хотя бы у двоих дни рождения совпадут, превысила 50%? Интуиция подсказывает числа вроде 180 (половина года). Но математика дает другой ответ.
Проще посчитать вероятность обратного события — «у всех дни рождения в разные дни».
При вероятность , а значит, вероятность совпадения . Всего 23 человека! В ML это означает, что если ваша хеш-функция имеет небольшое количество выходных значений, коллизии начнутся гораздо раньше, чем вы заполните все «ячейки». Это нужно учитывать при проектировании систем поиска дубликатов или признаков на основе хеширования (Feature Hashing).
Граничные случаи и ловушки комбинаторного подхода
При расчетах начинающие специалисты часто допускают две ошибки:
Пошаговый разбор задачи: Оценка точности поисковой выдачи
Представьте, что вы оцениваете качество поискового алгоритма. В топ-5 выдачи попали 3 релевантных документа и 2 нерелевантных. Всего в базе данных 10 релевантных документов и 90 нерелевантных (итого 100). Какова вероятность того, что случайный алгоритм выдаст такой же или лучший результат (минимум 3 релевантных в топ-5)?
Это классическая задача, которая ложится в основу гипергеометрического распределения, но мы решим её через комбинаторику.
Шаг 1: Общее число способов выбрать 5 документов из 100. Порядок в топ-5 для данной задачи (упрощенно) не важен, важен только состав.
Шаг 2: Число способов выбрать ровно 3 релевантных из 10 и 2 нерелевантных из 90. Используем правило произведения: нужно выбрать 3 из 10 И 2 из 90.
Шаг 3: Число способов выбрать ровно 4 релевантных.
Шаг 4: Число способов выбрать все 5 релевантных.
Шаг 5: Итоговая вероятность. Благоприятные исходы .
Вероятность получить такой результат случайно — менее 0.7%. Это дает нам статистическое основание утверждать, что наш поисковый алгоритм действительно работает и находит структуру в данных, а не просто подбрасывает документы наугад.
Замыкание темы: от комбинаторики к теории вероятностей
Комбинаторика предоставляет нам «счетную машинку» для определения вероятностей в дискретных пространствах. Однако в реальном мире данных мы редко знаем точное количество всех возможных исходов. Чаще мы работаем с частотами: если из 10 000 писем 2 000 были спамом, мы принимаем за оценку вероятности появления спама в будущем.
Тем не менее, понимание сочетаний и перестановок критически важно для:
Овладев навыком разбиения сложной задачи на элементарные исходы и умением их подсчитывать, вы закладываете фундамент для понимания более сложных концепций: случайных величин и их распределений, которые правят миром алгоритмов машинного обучения.