Entropy и information theory на собеседовании Data Scientist

Зачем разбирать на собесе

Информационная теория — фундамент multiple ML концепций. На собесе DS: «зачем cross-entropy в classification», «отличие KL и cross-entropy».

Энтропия Шеннона

H(X) = -Σ p(x) · log p(x)

Мера неопределённости distribution. В битах (log2) или nats (ln).

Свойства:

• H = 0 для deterministic distribution.
• H максимальна для uniform distribution.
• Для бинарной с p: H(p) = -p log p - (1-p) log(1-p), max в p=0.5.

Cross-entropy

H(p, q) = -Σ p(x) · log q(x)

Между «истинной» distribution p и predicted q. Минимизация cross-entropy = q ближе к p.

В классификации: p — one-hot true label, q — softmax output модели.

L = -Σ y_true · log y_pred

Это objective function для logistic regression / neural network classifiers.

KL divergence

KL(p || q) = Σ p(x) · log(p(x) / q(x)) = H(p, q) - H(p)

«Distance» (не симметричная) между distributions. KL ≥ 0, = 0 ⟺ p = q.

Связь с cross-entropy: H(p, q) = H(p) + KL(p || q).

При обучении (p — fixed labels, H(p) const) минимизация cross-entropy ≡ минимизации KL.

Variational Inference, Diffusion — KL играет ключевую роль.

Mutual Information

I(X; Y) = H(X) - H(X|Y) = KL(p(x,y) || p(x)·p(y))

Сколько information о X даёт знание Y.

• I = 0 если X, Y независимы.
• I = H(X) если Y полностью определяет X.

Применение:

• Feature selection (mutual_info_classif в sklearn).
• Image registration.
• Communications (Shannon's theory).

Information Gain

В decision trees:

IG(parent, split) = H(parent) - Σ (|child_i|/|parent|) · H(child_i)

Снижение энтропии при split. Best split — максимизирует IG.

В CART используется Gini impurity или entropy. Оба работают похоже.

Применения в ML

Cross-entropy loss. Стандарт для classification.

KL в VI / VAE. Tradeoff между reconstruction и regularization.

KL в RLHF. PPO loss = reward - β · KL(policy || reference).

Information Bottleneck. Theory обучения NN.

Drift detection. KL divergence между old / new distributions.

Maximum entropy classifiers. Logistic regression — частный случай.

Частые ошибки

KL не симметричен. KL(p || q) ≠ KL(q || p). Использовать осторожно.

Cross-entropy с continuous output. Разные формулы для discrete (categorical) vs continuous.

Игнорировать base log. В битах vs nats — разные numbers (factor ln 2).

MI between binary variables как correlation. Похоже, но не идентично. MI ловит non-linear dependencies.

KL(p || q) при q(x) = 0 где p(x) > 0. Бесконечность. Smoothing нужно.

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

• Loss функции на собесе DS
• Linear vs logistic regression на собесе DS
• Decision trees на собесе DS
• Feature engineering на собесе DS
• Подготовка к собесу Data Scientist

FAQ

Mutual information — это correlation?

Похоже, но MI ловит nonlinear, correlation — только linear.

Это официальная информация?

Нет. Статья основана на классических работах (Shannon 1948, Kullback-Leibler 1951).

Тренируйте Data Science — откройте тренажёр с 1500+ вопросами для собесов.