Множества, сочетания и подсчёт

Зачем это нужно

Словарь токенизатора — это множество: в нём нет повторов, и порядок не важен (урок 4.2). Чтобы очистить данные для претрейна от дубликатов, документы превращают в множества кусочков текста и сравнивают, какая доля у них общая (урок 5.1.2). В MoE-модели DeepSeek-V3 каждый токен выбирает 8 экспертов из 256 — и полезно уметь посчитать, сколько существует таких «команд» (модуль 5.3). Метрика pass@k для задач по программированию (урок 7.3.2) и биномиальное распределение (урок 1.3.1) тоже сводятся к одному вопросу: сколькими способами можно выбрать?

Этот урок даёт два инструмента. Первый — язык множеств: значки $\in$, $\cup$, $\cap$, $\lvert A \rvert$, которые встречаются в статьях постоянно. Второй — подсчёт: правило произведения, факториал и сочетания. На них построена классическая вероятность.

Множество: элементы и размер

МножествомножествоEN setНеупорядоченный набор уникальных элементов. Пустое множество — set(), а {} — пустой словарь. — набор различных объектов, его элементов. Записывают перечислением в фигурных скобках: $V = \{\text{я}, \text{люблю}, \text{чай}\}$. Два правила: повторы не считаются ($\{1, 1, 2\} = \{1, 2\}$) и порядок не важен ($\{1, 2\} = \{2, 1\}$). В Python это set из урока 0.2.1 — он ведёт себя ровно так же.

Запись	Читается	Пример	В Python
$x \in A$	$x$ принадлежит $A$	$\text{чай} \in V$	"чай" in V
$x \notin A$	$x$ не принадлежит $A$	$\text{кофе} \notin V$	"кофе" not in V
$\lvert A \rvert$	размер (мощность) $A$	$\lvert V \rvert = 3$	len(V)
$\varnothing$	пустое множество	$\lvert \varnothing \rvert = 0$	set()
$A \subseteq B$	$A$ — подмножество $B$	$\{\text{чай}\} \subseteq V$	A <= B

ПодмножествоподмножествоEN subsetA ⊆ B — каждый элемент A есть и в B. В Python: A <= B. У множества из n элементов 2ⁿ подмножеств. $A \subseteq B$ значит: каждый элемент $A$ есть и в $B$. Размер множества $\lvert A \rvert$ — просто число его элементов (те же вертикальные черты, что у модуля в уроке 1.0.1, но смысл другой). Когда в статье пишут «размер словаря $\lvert V \rvert$», имеют в виду именно это: у Qwen $\lvert V \rvert \approx 152$ тысячи.

Часто множество задают не перечислением, а условием: $\{x \in A : x > 0\}$ читается «все $x$ из $A$, такие что $x > 0$». Например, $\{i : p_i > 0.01\}$ — номера токенов, которым модель дала вероятность больше 1%. В Python это генератор множества: {i for i, p in enumerate(probs) if p > 0.01}.

Операции: объединение, пересечение, разность

Возьмём два текста и превратим их в множества слов: $A$ — «я люблю зелёный чай», $B$ — «я люблю чёрный чай».

Операция	Запись	Смысл	Python	Результат
объединениеобъединение множествEN unionA ∪ B — элементы, которые есть хотя бы в одном из множеств. В Python: A | B.	$A \cup B$	есть хотя бы в одном	A | B	я, люблю, зелёный, чёрный, чай
пересечениепересечение множествEN intersectionA ∩ B — элементы, которые есть в обоих множествах. В Python: A & B.	$A \cap B$	есть в обоих	A & B	я, люблю, чай
разностьразность множествEN set differenceA ∖ B — элементы A, которых нет в B. В Python: A - B.	$A \setminus B$	есть в $A$, но нет в $B$	A - B	зелёный

Тексты «я люблю зелёный чай» и «я люблю чёрный чай» как множества слов. Пересечение — общая часть кругов, объединение — оба круга целиком, разность — «свой» полумесяц.

Размеры связаны простой формулой. Если сложить $\lvert A \rvert$ и $\lvert B \rvert$, общие элементы будут посчитаны дважды, поэтому их надо один раз вычесть:

$$\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$$

Проверка: $4 + 4 - 3 = 5$. Эту формулу называют формулой включений-исключений.

Где это в ML. Разность множеств отвечает на вопрос «каких слов текста нет в словаре?» — это слова вне словаря (OOVслово вне словаря (OOV)EN out-of-vocabulary word (OOV)Слово, которого нет в словаре; словарный токенизатор заменяет его на <unk>. Byte-level BPE этой проблемы не имеет., урок 4.2.1). Пересечение — «какие примеры теста попали в обучающие данные?»: так ищут утечку тестазагрязнение данных (утечка бенчмарка в обучение)EN data contaminationЗадачи из тестового бенчмарка попали в обучающий корпус LLM — оценка становится завышенной. Родственное явление — «шуабан», подгонка модели под лидерборд. (урок 7.3.1). Объединение словарей двух языков — первый шаг к многоязычному токенизатору.

Сходство Жаккара

Насколько похожи два документа? Посчитаем долю общих элементов среди всех различных:

$$J(A, B) = \frac{\lvert A \cap B \rvert}{\lvert A \cup B \rvert}$$

Читаем: «сходство Жаккарасходство ЖаккараEN Jaccard similarity|A ∩ B| / |A ∪ B| — доля общих элементов двух множеств. — размер пересечения, делённый на размер объединения». Одинаковые множества дают 1, не имеющие общих элементов — 0. У наших текстов $J = 3/5 = 0.6$.

a = set("я люблю зелёный чай".split())      # split() режет строку по пробелам → список слов → множество
b = set("я люблю чёрный чай".split())

print(a & b)                     # {'я', 'люблю', 'чай'} — порядок при печати может отличаться
print(len(a | b))                # 5
print(a - b, b - a)              # {'зелёный'} {'чёрный'}
print(len(a & b) / len(a | b))   # 0.6 — сходство Жаккара

В уроке 5.1.2 элементами будут не слова, а шинглы — все цепочки по 5 слов подряд. Если $J$ двух веб-страниц больше 0.7–0.8, это почти-дубликаты, и одну из них выбрасывают. На миллиардах страниц считать $J$ для каждой пары невозможно, поэтому придумали MinHash — вероятностный трюк, который мы разберём в конце урока.

Правило произведения

Перейдём к подсчёту. Главный инструмент — правило произведенияправило произведенияEN rule of productЕсли первый выбор можно сделать a способами, а второй — b способами, то пару выборов — a·b способами. Отсюда Vᵀ последовательностей из T токенов.: если первый выбор можно сделать $a$ способами, а второй (при любом первом) — $b$ способами, то пару выборов — $a \cdot b$ способами.

Пример: 3 футболки и 4 пары брюк дают $3 \cdot 4 = 12$ нарядов — к каждой футболке подходит любая из 4 пар. ПИН-код из 4 цифр: на каждое место 10 вариантов, всего $10 \cdot 10 \cdot 10 \cdot 10 = 10^4$ кодов.

Сколько бывает текстов. Пусть в словаре $V$ токенов, а текст состоит из $T$ токенов. На каждое место — $V$ вариантов, поэтому различных текстов $V^T$. Числа для $V = 50\,000$ (словарь GPT-2 — 50 257 токенов):

Длина $T$	Число последовательностей $V^T$
1	$5 \cdot 10^4$
2	$2.5 \cdot 10^9$
10	$\approx 9.8 \cdot 10^{46}$

Уже пар токенов 2.5 миллиарда — столько ячеек было бы в таблице биграммной модели (урок 4.1.2). А последовательностей длины 10 так много, что все тексты, на которых когда-либо обучали модели (DeepSeek-V3 — 14.8 триллиона токенов, то есть около $1.5 \cdot 10^{13}$), — ничтожная доля. Модель не может «запомнить все варианты»: ей приходится обобщать. Это одна из причин, почему языковые модели — нейросети, а не таблицы.

Сколько подмножеств. У множества из $n$ элементов каждый элемент либо входит в подмножество, либо нет — 2 варианта на элемент. По правилу произведения подмножеств $2^n$. У $\{a, b, c\}$ их 8: $\varnothing$, $\{a\}$, $\{b\}$, $\{c\}$, $\{a, b\}$, $\{a, c\}$, $\{b, c\}$, $\{a, b, c\}$.

Есть и правило суммы: если варианты делятся на непересекающиеся группы, их количества складываются. Пароль из 3 или 4 цифр: $10^3 + 10^4 = 11\,000$ вариантов.

Перестановки и факториал

Сколькими способами можно выстроить в ряд $n$ разных предметов? На первое место — $n$ кандидатов, на второе — $n - 1$ (один уже стоит), на третье — $n - 2$, и так до последнего, на которое остаётся один. По правилу произведения:

$$n! = n \cdot (n - 1) \cdot (n - 2) \cdots 2 \cdot 1$$

Это факториалфакториалEN factorialn! = 1·2·…·n — число способов выстроить n предметов в ряд; 0! = 1. Растёт быстрее любой экспоненты: 20! ≈ 2.4·10¹⁸. («эн факториал»), а способы выстроить — перестановкиперестановкаEN permutationУпорядочивание набора предметов; перестановок n предметов n!. Упорядоченный выбор k из n (размещение) — n!/(n − k)! способов.. Для трёх токенов «я», «люблю», «чай» перестановок $3! = 6$: я люблю чай, я чай люблю, люблю я чай, люблю чай я, чай я люблю, чай люблю я. По соглашению $0! = 1$: пустой набор можно упорядочить одним способом — ничего не делать.

Факториал растёт быстрее любой экспоненты (урок 1.0.2):

$n$	1	3	5	10	20	52
$2^n$	2	8	32	1024	$\approx 10^6$	$\approx 4.5 \cdot 10^{15}$
$n!$	1	6	120	3 628 800	$\approx 2.4 \cdot 10^{18}$	$\approx 8.1 \cdot 10^{67}$

Колоду из 52 карт можно перетасовать примерно $8 \cdot 10^{67}$ способами: почти наверняка ваша тасовка никогда не встречалась в истории. Поэтому задачи «перебрать все порядки» на практике невыполнимы уже при $n$ около 20 — и в ML их заменяют сэмплированием.

Упорядоченный выбор части. Если из $n$ предметов нужно выбрать $k$ по порядку (первое, второе, …, $k$-е место), вариантов $n \cdot (n-1) \cdots (n-k+1)$ — тот же факториал, но оборванный через $k$ множителей. Пьедестал (3 места) из 5 бегунов: $5 \cdot 4 \cdot 3 = 60$. В Python — math.perm(5, 3).

Сочетания: выбрать k из n без порядка

Теперь главный случай: выбрать $k$ предметов из $n$, когда порядок не важен. Роутер MoE выбирает «команду» экспертов — ему всё равно, кого назвать первым. Пусть экспертов 4, а выбрать нужно 2.

Упорядоченных пар $4 \cdot 3 = 12$. Но пары (1, 2) и (2, 1) — одна и та же команда $\{1, 2\}$. Каждую команду из двух мы посчитали $2! = 2$ раза, значит, команд $12 / 2 = 6$: $\{1,2\}$, $\{1,3\}$, $\{1,4\}$, $\{2,3\}$, $\{2,4\}$, $\{3,4\}$.

То же рассуждение в общем виде: упорядоченных выборов $n(n-1)\cdots(n-k+1)$, и каждый неупорядоченный набор из $k$ элементов встречается среди них $k!$ раз (столько у него перестановок). Получаем число сочетанийчисло сочетаний (биномиальный коэффициент)EN binomial coefficient, "n choose k"C(n, k) = n! / (k!(n − k)!) — сколькими способами выбрать k предметов из n без учёта порядка. В Python: math.comb(n, k).:

$$\binom{n}{k} = \frac{n (n-1) \cdots (n-k+1)}{k!} = \frac{n!}{k!\,(n-k)!}$$

Читается «цэ из эн по ка», пишут также $C(n, k)$ или $C_n^k$. Вторая форма получается, если домножить числитель и знаменатель на $(n-k)!$: числитель «дорастает» до полного $n!$. Числа: $\binom{5}{2} = \frac{5 \cdot 4}{2} = 10$, $\binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{6} = 120$.

Три свойства, которые легко понять без формул:

• Симметрия: $\binom{n}{k} = \binom{n}{n-k}$. Выбрать 2 эксперта из 16 в команду — то же, что выбрать 14, которые в неё не войдут.
• Сумма по всем $k$ равна $2^n$: $\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n}$ — это все подмножества, разложенные по размеру. Для $n = 5$: $1 + 5 + 10 + 10 + 5 + 1 = 32$.
• Правило треугольника: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$. Посмотрите на последний элемент: либо он в наборе (тогда остальные $k - 1$ выбираем из $n - 1$), либо нет (тогда все $k$ — из $n - 1$). Если выписать числа $\binom{n}{k}$ строками, каждое окажется суммой двух соседних сверху — это треугольник Паскаля, в Китае — треугольник Ян Хуэя (см. «Китайский угол»).

import math
from itertools import combinations

def comb(n, k):
    """C(n, k) без больших факториалов: после каждого шага результат остаётся целым."""
    if k < 0 or k > n:
        return 0
    k = min(k, n - k)                  # симметрия: C(16, 14) = C(16, 2) — меньше шагов
    result = 1
    for i in range(k):
        result = result * (n - i) // (i + 1)   # C(n, i+1) = C(n, i) · (n − i) / (i + 1)
    return result

print(comb(4, 2), list(combinations([1, 2, 3, 4], 2)))
# 6 [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
print(comb(16, 2), comb(64, 8), math.comb(64, 8))   # 120 4426165368 4426165368
print([comb(5, k) for k in range(6)])               # [1, 5, 10, 10, 5, 1] — сумма 32 = 2⁵

Почему внутри цикла сначала умножение, потом целочисленное деление //? Произведение $i + 1$ подряд идущих чисел всегда делится на $(i + 1)!$, поэтому на каждом шаге получается точное целое число $\binom{n}{i+1}$. А считать через math.factorial(n) при $n = 10^6$ было бы очень долго: в таком числе больше пяти миллионов цифр.

Сочетания в LLM

Команды экспертов. В статье DeepSeekMoE разобран пример: 16 экспертов, каждый токен выбирает 2 — всего $\binom{16}{2} = 120$ возможных команд. Разрежем каждого эксперта на 4 маленьких (параметров и вычислений столько же) и будем выбирать 8 из 64: $\binom{64}{8} = 4\,426\,165\,368$ — в 37 миллионов раз больше вариантов. Знания для каждого токена собираются из более точно подобранных «кусочков». У DeepSeek-V3 8 из 256: $\binom{256}{8} \approx 4.1 \cdot 10^{14}$. Подробно — в уроке 5.3.2.

Пары. Частный случай $\binom{n}{2} = \frac{n(n-1)}{2}$ — число пар. Миллиард документов дают около $5 \cdot 10^{17}$ пар: сравнить каждую пару невозможно, отсюда MinHash и LSH (урок 5.1.2). Внимание в трансформере (урок 4.4) считает оценку для каждой пары токенов, поэтому его стоимость растёт как квадрат длины текста.

От подсчёта к вероятности

Если все исходы опыта равновероятны, вероятность события — доля подходящих исходов:

$$P(A) = \frac{\lvert A \rvert}{\lvert \Omega \rvert}$$

Здесь $\Omega$ («омега») — множество всех исходов, $A \subseteq \Omega$ — исходы, при которых событие произошло. Это классическая вероятностьклассическая вероятностьEN classical probabilityКогда все исходы равновероятны, P(A) = |A| / |Ω| — доля подходящих исходов среди всех.. Бросаем два кубика: по правилу произведения исходов $6 \cdot 6 = 36$, а сумма 7 выпадает в шести: (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1). Значит, $P(\text{сумма} = 7) = 6/36 \approx 0.167$. Вся сложность таких задач — правильно посчитать $\lvert A \rvert$ и $\lvert \Omega \rvert$, а для этого и нужны правило произведения и сочетания. В уроке 1.3.1 сочетания появятся в биномиальном распределении: $\binom{n}{k}$ там считает, какие именно $k$ попыток из $n$ оказались удачными.

MinHash: вероятность, равная Жаккару. Перемешаем все элементы $A \cup B$ в случайном порядке и посмотрим, какой элемент $A$ окажется первым и какой элемент $B$ окажется первым. Они совпадут, только если самый первый элемент всего объединения лежит в пересечении. Все элементы объединения равновероятно могут оказаться первыми, поэтому

$$P(\text{первые совпали}) = \frac{\lvert A \cap B \rvert}{\lvert A \cup B \rvert} = J(A, B)$$

Повторив такое перемешивание 100 раз, мы оценим $J$ по доле совпадений, не сравнивая множества целиком. Проверим симуляцией:

import random

A = set(range(0, 60))            # элементы 0…59
B = set(range(20, 100))          # элементы 20…99: общих 40, всего разных 100 → J = 0.4
union = sorted(A | B)
rng = random.Random(0)

hits = 0
for _ in range(2000):
    rank = {x: rng.random() for x in union}            # случайный «номер в очереди» для каждого элемента
    if min(A, key=rank.get) == min(B, key=rank.get):   # первые элементы A и B совпали?
        hits += 1
print(len(A & B) / len(A | B), hits / 2000)            # 0.4 0.3895 — оценка близка к точному J

pass@k. Модель сгенерировала $n = 10$ решений задачи, из них $c = 3$ верных. Какова вероятность, что среди $k = 2$ случайно выбранных решений хотя бы одно верное? Проще посчитать обратное: «оба неверные». Выбрать 2 из 7 неверных можно $\binom{7}{2} = 21$ способом, а всего пар $\binom{10}{2} = 45$. Ответ: $1 - 21/45 \approx 0.533$. Это ровно формула метрики pass@k, которую вы реализуете в уроке 7.3.2.

Практика

Реализуйте факториал, свои сочетания (без math.comb), сходство Жаккара и вероятность «хотя бы одного верного из $k$».

Сочетания, Жаккар и подсчёт команд экспертов7 тестов

def factorial(n):
    """n! = 1 · 2 · … · n. По соглашению 0! = 1. Для n < 0 бросьте ValueError.

    Пример: factorial(5) → 120.
    """
    # TODO: result = 1 и цикл умножений
    ...


def comb(n, k):
    """Число сочетаний C(n, k): сколькими способами выбрать k предметов из n без учёта порядка.

    Не используйте math.comb — посчитайте сами. Если k < 0 или k > n, верните 0.
    Ответ — целое число (int), даже для больших n: comb(256, 8) → 409663695276000.
    Примеры: comb(5, 2) → 10, comb(16, 2) → 120.
    """
    # TODO: мультипликативная формула C(n, k) = n·(n−1)·…·(n−k+1) / k!
    ...


def words(text):
    """Множество слов текста в нижнем регистре (слова разделены пробелами).

    Пример: words("Я люблю чай") → {"я", "люблю", "чай"}.
    """
    # TODO
    ...


def jaccard(a, b):
    """Сходство Жаккара двух множеств: |A ∩ B| / |A ∪ B|.

    Если оба множества пустые, верните 1.0.
    Пример: jaccard({1, 2, 3}, {2, 3, 4}) → 0.5.
    """
    # TODO
    ...


def prob_at_least_one(n, c, k):
    """Из n сгенерированных ответов c верных. Выбираем k ответов случайно (без повторов).
    Какова вероятность, что среди них есть хотя бы один верный?

    Подсказка: посчитайте вероятность обратного события «все k неверные».
    Пример: prob_at_least_one(10, 3, 2) → 1 − C(7, 2) / C(10, 2) = 1 − 21/45 ≈ 0.5333.
    """
    # TODO
    ...


# Проверьте себя кнопкой «Запустить»:
print(factorial(5))                                          # 120
print(comb(16, 2), comb(64, 8))                              # 120 4426165368
print(jaccard(words("Я люблю зелёный чай"), words("я люблю чёрный чай")))   # 0.6
print(prob_at_least_one(10, 3, 2))                           # ≈ 0.5333

ЗапуститьПроверитьПодсказкаСбросить

Китайский угол: треугольник Ян Хуэя и словарь комбинаторики

Треугольник сочетаний в Китае знали за 400 лет до Паскаля. Математик Ян Хуэй в книге «Подробный разбор методов „Девяти глав“» (1261) привёл таблицу биномиальных коэффициентов и указал, что её составил Цзя Сянь ещё в XI веке. Поэтому в китайских учебниках его называют треугольником Ян Хуэя или треугольником Цзя Сяня, а в Европе — треугольником Паскаля (1654). Вот его первые строки — каждое число равно сумме двух соседних сверху:

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
  1 5 10 10 5 1

Слова. Китайские термины теории множеств и комбинаторики переводятся почти дословно: множество, элемент, подмножество, пересечение, объединение, разность, перестановка (размещение), сочетание, факториал. Классическая вероятность там называется «классической моделью вероятности», а в «сходстве Жаккара» фамилия записана по звучанию. В китайских учебниках число сочетаний обычно пишут $C_n^k$, а число размещений — $A_n^k$ (от английского arrangement — «расстановка»).

MoE по-китайски. Мелкозернистые эксперты — главная идея DeepSeekMoE (январь 2024), и обе крупнейшие китайские линейки пришли к «много маленьких экспертов»: у DeepSeek-V3 8 из 256 маршрутизируемых экспертов плюс 1 общий, у Qwen3-235B-A22B — 8 из 128. Число возможных команд: $\binom{256}{8} \approx 4.1 \cdot 10^{14}$ и $\binom{128}{8} \approx 1.4 \cdot 10^{12}$.

Проверь себя

Проверь себя6 вопросов·

1 Дано $A = \{1, 2, 3, 4\}$, $B = \{3, 4, 5\}$. Чему равно сходство Жаккара $J(A, B)$? Округлите до двух знаков.

2 Какие записи верны для $A = \{\text{я}, \text{люблю}, \text{чай}\}$?Можно выбрать несколько ответов

$\lvert A \rvert = 3$$\{\text{чай}, \text{я}\} \subseteq A$$\{\text{я}, \text{я}, \text{чай}\}$ имеет размер 3$A \setminus \{\text{чай}\} = \{\text{я}, \text{люблю}\}$

3 Роутер выбирает 2 эксперта из 8, порядок не важен. Сколько существует разных команд?

4 Почему $\binom{n}{k} = \binom{n}{n-k}$?

Это совпадение, верное только для маленьких чиселВыбрать $k$ предметов, которые войдут, — то же самое, что выбрать $n - k$, которые не войдутПотому что $n! = (n-k)!$

5 Сколько существует различных последовательностей из 3 токенов при словаре из 10 токенов (повторы разрешены)?

6 Бросаем два кубика. Какова вероятность, что выпадут две шестёрки? Округлите до трёх знаков.

Проверить ответы

Итоги

• Множество — набор различных элементов без порядка; $\in$, $\subseteq$, $\lvert A \rvert$, $\cup$, $\cap$, $\setminus$ — те же операции, что in, <=, len, |, &, - у set в Python. $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$.
• Сходство Жаккара $\lvert A \cap B \rvert / \lvert A \cup B \rvert$ измеряет долю общего; на нём стоит дедупликация данных для претрейна.
• Правило произведения: последовательностей из $T$ токенов $V^T$, подмножеств $2^n$, перестановок $n!$ — и все эти числа растут взрывообразно.
• Сочетания $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ — выбор без порядка. Они считают команды экспертов MoE, пары документов и удачные попытки в биномиальном распределении.
• Классическая вероятность — «подходящие исходы / все исходы»; так выводятся pass@k и свойство MinHash.

Дальше: модуль 1.1 «Линейная алгебра». Векторы, скалярное произведение и нормы — то, что стоит за записями $\mathbf{w}^\top \mathbf{x}$ и $\lVert \mathbf{x} \rVert$, и за косинусом угла между эмбеддингами.