Комбинаторика
Правила суммы и произведения
- Произведение: если первый выбор — $m$ вариантов, второй — $n$, то пар $m \cdot n$. Пароль из 4 цифр: $10^4$ вариантов.
- Сумма: если выбираем либо одно из $m$, либо одно из $n$ (без пересечений) — $m + n$ вариантов.
Перестановки, размещения, сочетания
| Что считаем | Формула | Пример |
|---|---|---|
| Перестановки $n$ объектов | $n! = 1 \cdot 2 \cdots n$ | порядков 5 карт: 120 |
| Упорядоченный выбор $k$ из $n$ | $\frac{n!}{(n-k)!}$ | призовые места 3 из 10: 720 |
| Неупорядоченный выбор $k$ из $n$ | $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ | пары из 5 человек: 10 |
| С повторениями, порядок важен | $n^k$ | последовательностей из 10 токенов словаря 50k: $50000^{10}$ |
$n!$ растёт быстрее экспоненты: $10! \approx 3.6 \cdot 10^6$, $20! \approx 2.4 \cdot 10^{18}$.
Бином Ньютона и треугольник Паскаля
$$ (a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k} $$
Коэффициенты — строки треугольника Паскаля (1; 1 1; 1 2 1; 1 3 3 1; …). Отсюда биномиальное распределение: вероятность $k$ успехов из $n$ — $\binom{n}{k}p^k(1-p)^{n-k}$.
Где в ML
- Пространство поиска: перебрать все подмножества из 30 признаков — $2^{30} \approx 10^9$ вариантов; поэтому используют жадные методы и регуляризацию.
- Попарные сравнения: для $n$ объектов $\binom{n}{2} \approx n^2/2$ пар — столько пар нужно для contrastive loss или кластеризации.
- Beam search с шириной $k$ хранит $k$ лучших из $k \cdot V$ продолжений вместо всех $V^T$ последовательностей.
🏋️ Практика Б9
Б9.1. Сколько разных батчей по 4 примера можно составить из 10?
▶️ Ответ
$\binom{10}{4} = 210$.Б9.2. Вероятность ровно 3 орлов из 5 бросков честной монеты?
▶️ Ответ
$\binom{5}{3}/2^5 = 10/32 = 0.3125$.Б9.3. Сколько пар для contrastive loss в батче из 256 примеров (каждый с каждым)?