Совместная и условная энтропия

Decision tree выбирает лучший признак не случайно - он вычисляет H(Y) - H(Y|X) для каждого кандидата. Information gain - это разница энтропий. Тот же принцип: в LLM-трансформере каждый следующий токен имеет меньшую H из-за контекста. Conditioning reduces entropy - и это не метафора, а теорема.

• **Decision Trees, XGBoost, LightGBM**: information gain = H(Y) - H(Y|X_признак) определяет порядок разбиения в каждом узле
• **scikit-learn** `mutual_info_classif`: MI-based feature selection ловит нелинейные зависимости, которые Pearson пропускает
• **LLM inference**: KV-cache эксплуатирует то, что H(токен | контекст) < H(токен). Longer context = less entropy per token
• **Pointwise MI (PMI)**: сила ассоциации между словами в NLP; лёг в основу word2vec и ранних embedding техник

Предварительные знания

• Shannon Entropy: the Math of Uncertainty

Joint Entropy

Одна случайная величина - понятно. Но реальные системы работают с парами, тройками, миллионами переменных одновременно. Язык - это не набор независимых букв. Пиксель в изображении - не независим от соседей. И H(X, Y) отражает это.

**Совместная энтропия** H(X, Y) - общая неопределённость двух величин сразу. Формально это энтропия пары (X, Y) как единой случайной величины над пространством всех пар.

Вот почему JPEG и PNG дают разные размеры для одного изображения. JPEG эксплуатирует совместную статистику соседних пикселей: H(пиксель_i, пиксель_j) << H(пиксель_i) + H(пиксель_j). PNG тоже - через LZ77, который ловит структуру строк целиком.

KV-cache в трансформерах работает именно потому, что $H(\text{токен}_t \mid \text{контекст}) \ll H(\text{токен}_t)$. Контекст снимает огромную часть неопределённости. Чем длиннее контекст - тем меньше H(следующий токен | предыдущие). Это не просто интуиция - это прямое следствие chain rule энтропии.

Conditional Entropy

1988 год. Quinlan публикует C4.5 - алгоритм, который обучает половину production decision trees в мире. Главный вопрос в каждом узле дерева: *какой признак X выбрать, чтобы сильнее всего уменьшить неопределённость в метке Y?*

Ответ - **условная энтропия** H(Y|X): остаточная неопределённость в Y после того, как стало известно X. Это именно то количество информации, которое ещё нужно передать, зная X.

**scikit-learn** в `DecisionTreeClassifier` с `criterion='entropy'` вычисляет в каждом узле именно H(Y) - H(Y|X) для каждого кандидата-признака. Побеждает тот, кто больше снижает энтропию. В XGBoost и LightGBM используется вариация - gain по Гессиану, но принцип тот же.

Chain Rule

Арифметическое кодирование (zstd, AV1) кодирует поток символов последовательно. Главный вопрос: сколько бит нужно в среднем, чтобы описать символы x₁, x₂, ..., xₙ? Ответ - chain rule.

Именно chain rule объясняет, почему контекст помогает GPT-4 предсказывать. При знании предыдущих 128K токенов $H(\text{следующий} \mid \text{контекст})$ близко к 1-2 битам - против 15.6 бит без контекста ($\log_2 50257$). Каждый дополнительный токен контекста уменьшает $H(X_{t+1} \mid X_1,...,X_t)$.

В **сжатии данных** chain rule - прямое обоснование контекстных моделей. gzip кодирует байт с учётом предыдущих (LZ77 = неявная контекстная модель). zstd делает то же самое быстрее. LLM-токенизатор с BPE - это тоже chain rule: слова сжимаются с учётом частотности пар.

Mutual Information

Корреляция Пирсона измеряет линейную связь. Spearman - монотонную. Ни одна из них не поймает: X = sin(Y) при равномерном Y, XOR-зависимость, периодические паттерны. Mutual information - ловит всё.

**I(X; Y)** - количество информации, которое знание одной переменной даёт о другой. Симметрично: I(X;Y) = I(Y;X). Нулевое - только при независимости.

Tishby et al. (2017) - Information Bottleneck: нейросеть в процессе обучения максимизирует I(представление; метка) и минимизирует I(представление; вход). Это объясняет, почему deep networks сжимают данные, а не просто запоминают.

Ключевые идеи

• **Joint entropy** H(X,Y) ≤ H(X) + H(Y): зависимость только уменьшает совместную неопределённость
• **Conditioning reduces entropy**: H(Y|X) ≤ H(Y) - знание X не может навредить предсказанию Y
• **Chain rule**: H(X,Y) = H(X) + H(Y|X) - аналог цепного правила для вероятностей, основа контекстного сжатия
• **Mutual information** I(X;Y) = H(Y) - H(Y|X) - ловит любую зависимость, не только линейную; в основе decision trees и feature selection

Связанные темы

Условная энтропия и MI - мост к KL-дивергенции:

• Энтропия Шеннона — Все концепции этого урока строятся на H(X) = -Σ p log p
• KL-дивергенция — MI - это KL-дивергенция между P(X,Y) и P(X)P(Y). Следующий уровень

Вопросы для размышления

• Почему mutual information лучше корреляции Пирсона для feature selection? Приведи пример нелинейной зависимости, которую MI поймает, а корреляция - нет.
• Если H(Y|X) = 0, что это означает на практике? Приведи реальный пример из ML.
• Как chain rule для энтропии используется в контекстных языковых моделях? Почему длиннее контекст = ниже perplexity?

Связанные уроки

• it-01 — Базовая энтропия Шеннона H(X) - фундамент для совместной H(X,Y)
• it-03 — Mutual information I(X;Y) = H(X)+H(Y)-H(X,Y) - прямое следствие урока
• prob-03-conditional
• stat-11-bayesian