Модуль 5. Взаимная информация: сколько один объект говорит о другом — упражнения с решениями · Теория информации для машинного обучения

Упражнение 1. Нелинейная зависимость без корреляции

Пусть $X$ равномерно распределена на $\{-2,-1,1,2\}$ , а $Y=X^2$ .

Найдите $\mathbb E[X]$ , $\mathbb E[Y]$ и $\operatorname{Cov}(X,Y)$ .
Найдите $H(Y)$ и $I(X;Y)$ в битах.
Объясните, почему пример не противоречит утверждению $I(X;Y)=0\Leftrightarrow X\perp Y$ .

Показать ответ и решение

Пусть

X\sim\operatorname{Unif}\{-2,-1,1,2\}, \qquad Y=X^2.

Из симметрии

\mathbb E[X]=0.

Далее,

\mathbb E[Y] = \mathbb E[X^2] = \frac{4+1+1+4}{4} = \frac52.

Поскольку $XY=X^3$ ,

\mathbb E[XY] = \mathbb E[X^3] = \frac{-8-1+1+8}{4} = 0.

Следовательно,

\operatorname{Cov}(X,Y) = \mathbb E[XY]-\mathbb E[X]\mathbb E[Y] =0.

При этом $Y$ принимает значения $1$ и $4$ с вероятностями $1/2$ , поэтому

H(Y)=1\ \text{бит}.

Так как $Y$ — детерминированная дискретная функция $X$ ,

H(Y\mid X)=0

и

\boxed{I(X;Y)=H(Y)=1\ \text{бит}}.

Противоречия нет. Равенство нулю получила ковариация, а не MI. Переменные явно зависимы: зная $X$ , мы точно знаем $Y$ . Поэтому $I(X;Y)>0$ , как и должно быть.

Упражнение 2. XOR и провал одномерного отбора признаков

Пусть $X_1,X_2\overset{\mathrm{iid}}\sim\operatorname{Bern}(1/2)$ и $Y=X_1\oplus X_2$ .

Покажите, что $I(X_1;Y)=I(X_2;Y)=0$ .
Найдите $I((X_1,X_2);Y)$ и $I(X_1;Y\mid X_2)$ .
Объясните, какой тип ошибки возникает при ранжировании признаков по $I(X_i;Y)$ .

Показать ответ и решение

Пусть $X_1$ и $X_2$ — независимые честные биты, а

Y=X_1\oplus X_2.

Зафиксируем $X_1=x_1$ . Поскольку $X_2$ остаётся честным битом, $Y=x_1\oplus X_2$ также равномерна на $\{0,1\}$ . Значит, распределение $Y$ не зависит от значения $X_1$ :

P(Y=y\mid X_1=x_1)=P(Y=y)=\frac12.

Следовательно,

I(X_1;Y)=0.

По симметрии

I(X_2;Y)=0.

Но пара $(X_1,X_2)$ однозначно определяет $Y$ , а $Y$ — честный бит. Поэтому

H(Y)=1\ \text{бит}, \qquad H(Y\mid X_1,X_2)=0,

и

\boxed{I((X_1,X_2);Y)=1\ \text{бит}}.

После фиксации $X_2$ значение $Y$ однозначно определяет $X_1$ и наоборот. Поэтому

H(Y\mid X_2)=1\ \text{бит}, \qquad H(Y\mid X_1,X_2)=0,

и

\boxed{I(X_1;Y\mid X_2)=1\ \text{бит}}.

Индивидуальное ранжирование по $I(X_i;Y)$ присвоит обоим признакам нулевую релевантность и может удалить их. Ошибка состоит в игнорировании синергии: информация появляется только в комбинации признаков.

Упражнение 3. Сжатие нерелевантных факторов без потери целевой информации

Пусть $Y$ и $N$ — независимые честные биты, а вход $X=(Y,N)$ .

Рассмотрите представления

T_1=X, \qquad T_2=Y, \qquad T_3=Y\oplus E, \quad E\sim\operatorname{Bern}(0.1).

Найдите $I(Y;X)$ , $I(Y;T_1)$ , $I(Y;T_2)$ и $I(Y;T_3)$ .
Какое представление удаляет нерелевантный фактор, не теряя информацию о целевой переменной?
Почему желаемая компрессия относится к $I(X;T)$ , а не к намеренному уменьшению $I(Y;T)$ ?

Показать ответ и решение

Имеем два независимых честных бита $Y$ и $N$ , вход

X=(Y,N)

и представления

T_1=X, \qquad T_2=Y, \qquad T_3=Y\oplus E, \quad E\sim\operatorname{Bern}(0.1).

Поскольку $Y$ входит в $X$ без искажений,

I(Y;X)=H(Y)=1\ \text{бит}.

Для $T_1=X$ :

I(Y;T_1)=1\ \text{бит}.

Для $T_2=Y$ :

I(Y;T_2)=I(Y;Y)=1\ \text{бит}.

$T_3$ — выход binary symmetric channel с crossover probability $0.1$ . При равномерном входе

I(Y;T_3) = 1-h_2(0.1) \approx 0.531004\ \text{бита}.

Итак,

\boxed{ I(Y;X)=I(Y;T_1)=I(Y;T_2)=1, \qquad I(Y;T_3)\approx0.531 }.

Именно $T_2=Y$ удаляет нерелевантный фактор (nuisance) $N$ , не теряя информации о целевой переменной. Это видно и по объёму сохранённой информации о входе:

I(X;T_1)=H(X)=2\ \text{бита},

тогда как

I(X;T_2)=H(T_2)=1\ \text{бит}.

Хорошее сжатие под конкретную задачу (task-specific compression) стремится сохранить $I(Y;T)$ близкой к $I(Y;X)$ , одновременно уменьшая ненужную часть $I(X;T)$ . Намеренно уменьшать $I(Y;T)$ — значит выбрасывать информацию, полезную для предсказания целевой переменной.

Упражнение 4. Python: корреляция, оценка MI и перестановочная проверка

Сгенерируйте три набора данных:

Y_{\mathrm{lin}}=X+0.5\varepsilon,

Y_{\mathrm{nonlin}}=X^2+0.3\varepsilon,

Y_{\mathrm{ind}}=\varepsilon,

где $X,\varepsilon\sim\mathcal N(0,1)$ независимы.

Для нескольких размеров выборки:

посчитайте корреляцию Пирсона;
оцените MI методом $k$ ближайших соседей;
случайно переставьте значения $Y$ и получите перестановочный контрольный уровень;
повторите эксперимент для нескольких начальных состояний генератора.

Цель — увидеть нелинейную зависимость при почти нулевой корреляции, ненулевой контрольный уровень на конечной выборке и нестабильность оценивателя при малом числе наблюдений.

Показать ответ и решение

Ниже один воспроизводимый вариант эксперимента. mutual_info_regression использует оцениватель на основе ближайших соседей (kNN estimator) и возвращает результат в натах. Отрицательные численные значения библиотека обрезает до нуля, поэтому перестановочная базовая линия (permutation baseline) обычно имеет небольшое положительное среднее.

Python

import numpy as np
import pandas as pd
from sklearn.feature_selection import mutual_info_regression


def estimate_once(n: int, seed: int) -> list[dict[str, float | int | str]]:
    rng = np.random.default_rng(seed)
    x = rng.normal(size=n)

    datasets = {
        "linear": x + 0.5 * rng.normal(size=n),
        "nonlinear": x**2 + 0.3 * rng.normal(size=n),
        "independent": rng.normal(size=n),
    }

    rows = []
    for name, y in datasets.items():
        corr = float(np.corrcoef(x, y)[0, 1])
        mi = float(
            mutual_info_regression(
                x.reshape(-1, 1),
                y,
                n_neighbors=5,
                random_state=seed,
            )[0]
        )
        y_perm = rng.permutation(y)
        mi_perm = float(
            mutual_info_regression(
                x.reshape(-1, 1),
                y_perm,
                n_neighbors=5,
                random_state=seed,
            )[0]
        )
        rows.append(
            {
                "n": n,
                "relation": name,
                "corr": corr,
                "mi_nats": mi,
                "mi_perm_nats": mi_perm,
            }
        )
    return rows


records = []
for n in (200, 1000, 5000):
    for seed in range(30):
        records.extend(estimate_once(n, seed))

df = pd.DataFrame(records)
summary = (
    df.groupby(["n", "relation"])
    .agg(
        corr_mean=("corr", "mean"),
        corr_sd=("corr", "std"),
        mi_mean=("mi_nats", "mean"),
        mi_sd=("mi_nats", "std"),
        perm_mean=("mi_perm_nats", "mean"),
        perm_sd=("mi_perm_nats", "std"),
    )
    .reset_index()
)

with pd.option_context("display.max_rows", None, "display.width", 160):
    print(summary.round(4).to_string(index=False))

Для указанного протокола с 30 начальными состояниями генератора получаем:

text

   n    relation  corr_mean  corr_sd  mi_mean  mi_sd  perm_mean  perm_sd
 200 independent     0.0057   0.0686   0.0177 0.0287     0.0141   0.0204
 200      linear     0.8934   0.0140   0.8143 0.0761     0.0070   0.0132
 200   nonlinear    -0.0556   0.1287   0.9368 0.0804     0.0151   0.0255
1000 independent     0.0041   0.0269   0.0060 0.0097     0.0045   0.0067
1000      linear     0.8950   0.0062   0.8235 0.0338     0.0086   0.0096
1000   nonlinear    -0.0279   0.0688   1.0913 0.0392     0.0052   0.0076
5000 independent     0.0000   0.0131   0.0037 0.0050     0.0048   0.0052
5000      linear     0.8949   0.0024   0.8127 0.0127     0.0030   0.0050
5000   nonlinear     0.0011   0.0284   1.1378 0.0119     0.0013   0.0030

Главные наблюдения:

Для линейной зависимости и корреляция, и MI велики.
Для $Y=X^2+\text{noise}$ средняя корреляция стремится к нулю, но MI остаётся высокой.
Для независимых данных оценка MI не обязана быть ровно нулевой на конечной выборке.
С ростом $n$ разброс уменьшается, а перестановочная базовая линия приближается к нулю.
Абсолютное значение зависит от оценивателя, n_neighbors, масштабирования и размера выборки; здесь важнее сравнительная картина.

Упражнение 5. Python: чему равна граница InfoNCE на известном канале

Пусть $X$ равномерна на $K$ классах, а $Y$ совпадает с $X$ с вероятностью $1-\varepsilon$ и иначе равномерно выбирается среди остальных $K-1$ классов.

Выведите точную MI:

I(X;Y) = \log K-h_2(\varepsilon)-\varepsilon\log(K-1).

Используйте идеальную функцию совместимости

s^*(x,y)=\log\frac{p(y\mid x)}{p(y)}

и методом Монте-Карло оцените InfoNCE-потерю для $N\in\{4,16,64,256\}$ .

Сравните $\log N-\widehat{\mathcal L}_{\mathrm{NCE}}$ с точной MI.
Проверьте, что $\log N$ ограничивает эту границу, но не саму MI и не качество представления.

Математическое углубление. Неравенство Фано

Если $Y$ принимает $M$ значений, а $\widehat Y$ строится по $X$ , то

H(Y\mid X) \le h_2(P_e)+P_e\log(M-1),

где $P_e=\Pr(\widehat Y\ne Y)$ . Используйте формулу, чтобы связать остаточную неопределённость $H(Y\mid X)$ с информационно-теоретическим ограничением на достижимую долю ошибок. Отдельно объясните, почему граница может быть слабой и не заменяет построение байесовски оптимального классификатора.

Показать ответ и решение

Пусть $X$ равномерна на $K$ классах, а канал оставляет класс без изменения с вероятностью $1-\varepsilon$ и с вероятностью $\varepsilon$ выбирает один из остальных $K-1$ классов равномерно.

Из симметрии $Y$ также равномерна, поэтому

H(Y)=\log K.

Условное распределение имеет одну вероятность $1-\varepsilon$ и $K-1$ вероятностей $\varepsilon/(K-1)$ . Следовательно,

H(Y\mid X) = h_2(\varepsilon)+\varepsilon\log(K-1),

и

\boxed{ I(X;Y) = \log K-h_2(\varepsilon)-\varepsilon\log(K-1) }.

В коде ниже используются натуральные логарифмы. Отрицательные примеры (negatives) независимо выбираются из маргинального распределения $p(y)$ , а функция оценки (critic) равна идеальному логарифму отношения плотностей.

Можно проверить и $\varepsilon=0$ или $1$ : в энтропии принимаем $0\log0=0$ , а невозможной паре $(x,y)$ присваиваем critic $-\infty$ . Положительная пара генерируется самим каналом, поэтому её score остаётся конечным и знаменатель InfoNCE не обращается в ноль.

Python

import math
import numpy as np
from scipy.special import logsumexp

K = 64
epsilon = 0.25
rng = np.random.default_rng(20260712)

if K < 2 or not 0.0 <= epsilon <= 1.0:
    raise ValueError("Use K >= 2 and 0 <= epsilon <= 1")

# Exact MI in nats for the K-class symmetric channel.
h_eps = -sum(p * math.log(p) for p in (epsilon, 1.0 - epsilon) if p > 0.0)
mi_exact = math.log(K) - h_eps - epsilon * math.log(K - 1)


def sample_positive(x: np.ndarray) -> np.ndarray:
    """Sample Y from p(y|x) without rejection loops."""
    y = x.copy()
    flip = rng.random(x.size) < epsilon
    offsets = rng.integers(1, K, size=flip.sum())
    y[flip] = (x[flip] + offsets) % K
    return y


def estimate_infonce(n_candidates: int, total_trials: int = 100_000, chunk_size: int = 2_000) -> tuple[float, float]:
    loss_sum = 0.0
    loss_sq_sum = 0.0
    seen = 0

    log_ratio_match = math.log(K * (1.0 - epsilon)) if epsilon < 1.0 else -math.inf
    log_ratio_mismatch = math.log(K * epsilon / (K - 1)) if epsilon > 0.0 else -math.inf

    while seen < total_trials:
        batch = min(chunk_size, total_trials - seen)
        x = rng.integers(0, K, size=batch)
        positive = sample_positive(x)
        negatives = rng.integers(0, K, size=(batch, n_candidates - 1))
        candidates = np.concatenate([positive[:, None], negatives], axis=1)

        scores = np.where(
            candidates == x[:, None],
            log_ratio_match,
            log_ratio_mismatch,
        )
        losses = logsumexp(scores, axis=1) - scores[:, 0]
        loss_sum += float(losses.sum())
        loss_sq_sum += float(np.square(losses).sum())
        seen += batch

    mean_loss = loss_sum / total_trials
    variance = max(loss_sq_sum / total_trials - mean_loss**2, 0.0)
    standard_error = math.sqrt(variance / total_trials)
    return mean_loss, standard_error


print(f"Exact MI: {mi_exact:.6f} nats ({mi_exact / math.log(2):.6f} bits)")
print(" N    loss       bound      log(N)     SE(bound)")
for n_candidates in (4, 16, 64, 256):
    loss, se = estimate_infonce(n_candidates)
    bound = math.log(n_candidates) - loss
    print(
        f"{n_candidates:3d}  {loss:9.6f}  {bound:9.6f}  "
        f"{math.log(n_candidates):9.6f}  {se:9.6f}"
    )

Результат:

text

Exact MI: 2.560764 nats (3.694402 bits)
 N    loss       bound      log(N)     SE(bound)
  4   0.429934   0.956360   1.386294   0.002479
 16   0.991886   1.780702   2.772589   0.004612
 64   1.867571   2.291312   4.158883   0.006330
256   3.061057   2.484121   5.545177   0.007008

В этом запуске все оценки Монте-Карло для нижней границы лежат ниже точной MI. Теоретическая гарантия относится к population-границе; её конечновыборочная оценка может отклониться вверх, поэтому рядом указана стандартная ошибка. При увеличении $N$ граница становится плотнее, но для любого фиксированного $N$

\log N-\mathcal L_{\mathrm{NCE}} \le \log N.

Важное различие: это потолок выбранной нижней границы, а не потолок истинной $I(X;Y)$ . В примере при $N=4$

\log 4\approx1.386<2.561=I(X;Y),

поэтому граница InfoNCE принципиально не может достичь истинного значения даже с идеальной функцией оценки.

Математическое углубление. Неравенство Фано

Из

H(Y\mid X) \le h_2(P_e)+P_e\log(M-1)

следует: если после наблюдения $X$ остаётся большая неопределённость о $Y$ , то вероятность ошибки не может быть произвольно малой. Например, при равномерном $Y$ имеем

H(Y\mid X)=H(Y)-I(X;Y)=\log M-I(X;Y).

Чем меньше $I(X;Y)$ по сравнению с $\log M$ , тем больше неопределённости должен устранить классификатор без доступного сигнала — что невозможно.

Однако Фано обычно даёт нижнее ограничение, а не точное значение байесовской ошибки (Bayes error). Оно может быть слабым и не сообщает, какая модель или процедура обучения достигнет оптимума.