Теория информации
Info Theory на собеседовании
На FAANG-интервью теория информации встречается неожиданно часто: «объясните KL-дивергенцию», «почему L2-регуляризация помогает обобщению», «что такое information bottleneck». Эти вопросы отделяют тех, кто понимает ML теоретически, от тех, кто просто использует библиотеки.
- **Google Brain** публично рассказывал, что кандидаты, умеющие объяснить ELBO через информационные принципы, получают significantly higher оценки на ML Research интервью.
- **Meta AI Research** часто задаёт вопросы вида «как измерить, сколько информации о входе сохраняет скрытое представление?» - прямо в контексте Information Bottleneck.
- **OpenAI** использует KL-дивергенцию как центральный компонент RLHF (обучение ChatGPT) - понимание этого помогает на интервью в команды alignment и RL.
Предварительные знания
Вопросы про энтропию
Энтропия - самая частая тема теории информации на интервью. Базовые вопросы: «что такое энтропия?», «чему равна энтропия монеты?», «как изменится энтропия если добавить событие с вероятностью 0?». Более сложные: «минимальная/максимальная энтропия при n исходах?», «как связаны энтропия и количество бит для кодирования?».
**Главные факты об энтропии:** H(X) = −∑ p(x) log₂ p(x) бит. H = 0 ↔ детерминированный X. H = log₂ n ↔ равномерное распределение (максимум). H(X|Y) ≤ H(X) (conditioning reduces entropy). H(X,Y) = H(X) + H(Y|X). H(X) ≥ 0. Нулевое событие: 0·log(0) = 0 по определению.
| Вопрос | Ответ | Трюк |
|---|---|---|
| H(Xoracle)=? (X детерм.) | 0 бит | −1·log(1) = 0 |
| H(равном. {1..n})=? | log₂(n) бит | Максимум |
| H(X,Y) когда X=Y? | H(X) = H(Y) | H(X|X) = 0 |
| H(X+Y) vs H(X)+H(Y)? | ≤ сумме | Корреляция уменьшает |
| 0·log(0) = ? | 0 (по соглашению) | lim p→0 p·log(p) = 0 |
Историческая справка
Эти вопросы - стандарт для ML-инженерных интервью в Google, Meta, Amazon. Обычно начинают с «что такое энтропия интуитивно?» и двигаются к более конкретным задачам. Ключ: уметь связать формальное определение с интуицией «неопределённости».
Высокая вероятность одного исхода означает высокую энтропию
Наоборот: чем один исход вероятнее, тем ниже энтропия. Энтропия максимальна при равномерном распределении.
Энтропия = неопределённость. Если один исход почти наверняка (p≈1), нет неопределённости, нет информации, энтропия ≈ 0.
На интервью спрашивают: «У монеты p(H)=0.99. Чему примерно равна энтропия?» Лучший ответ:
Вопросы про кодирование
Частый тип задач: «придумайте оптимальный код для алфавита с такими-то вероятностями». Ожидается построение дерева Хаффмана, вычисление средней длины и сравнение с энтропией. Другой тип: «чему равен минимальный размер файла из N символов с энтропией H?» - ответ nH бит (плюс маленький overhead).
**Хаффман на интервью:** 1. сортируем вероятности 2. объединяем два наименьших 3. повторяем. Средняя длина L: H(X) ≤ L < H(X)+1. Если спрашивают «можно ли достичь H(X)?» - только при вероятностях степенях двойки. Иначе арифметическое кодирование / ANS.
| Задача | Метод | Главный факт |
|---|---|---|
| Мин. бит для n символов | nH(X) | AEP: нужно ровно nH бит |
| Среднее кодовое слово | Хаффман дерево | H ≤ L < H+1 |
| Мин. сжатие 1 символа | Хаффман | Цел. число бит, ≥ H(X) |
| Мин. сжатие блока n→∞ | Арифм. / ANS | → H(X) бит/символ |
| Нельзя сжать ниже... | H(X) | Теорема кодирования |
Историческая справка
Задачи на кодирование - стандарт Systems Design и ML Engineering интервью в FAANG. Особенно часто спрашивают связь между энтропией и минимальным размером: ответ «nH бит» из теоремы об исходном кодировании Шеннона (1948).
Lossless сжатие всегда уменьшает размер файла
Lossless сжатие не может уменьшить случайный файл - он уже при максимальной энтропии. Некоторые файлы при «сжатии» увеличиваются.
Pigeonhole: не все строки длины n можно сжать до меньше n бит. Для каждого «хорошо сжатого» входа есть входы, которые увеличатся.
Файл содержит 10000 символов из алфавита {A, B, C, D} с вероятностями 1/2, 1/4, 1/8, 1/8. Минимальный размер при lossless-сжатии?
Вопросы про пропускную способность
Вопросы о пропускной способности часто задают на System Design интервью: «как оценить теоретический предел скорости Wi-Fi канала?». Ожидается применение формулы Шеннона C = B log₂(1+SNR), понимание BSC и простых расчётов. ML-инженерам также задают: «что такое взаимная информация?» и «как она связана с пропускной способностью?».
**Вопросы на интервью:** 1. C = B log₂(1+SNR) для AWGN. 2. BSC(p): C = 1−H(p). 3. I(X;Y) = H(X) − H(X|Y) = H(Y) − H(Y|X). 4. При независимых X,Y: I(X;Y)=0. 5. I(X;Y) ≥ 0 всегда. 6. Data processing: I(X;Y) ≥ I(X;g(Y)).
| Вопрос интервью | Главный ответ | Формула |
|---|---|---|
| I(X;Y) при X⊥Y? | 0 | I = H(X) − H(X|Y) = H(X) − H(X) |
| I(X;Y) максимум? | min(H(X), H(Y)) | При функц. зависимости |
| C = ? для идеального канала | ∞ (без шума) | SNR→∞: C→∞ |
| Что ограничивает интернет? | Bandwidth + SNR | C = B log(1+SNR) |
| Data processing inequality | I(X;Y) ≥ I(X;g(Y)) | Обработка не увеличивает I |
Историческая справка
Вопросы про пропускную способность и взаимную информацию часто появляются в контексте «Как спроектировать систему рекомендаций?» - I(пользователь;рекомендация) как метрика качества. Это реальное применение теории Шеннона в ML-продуктах.
Feature engineering может увеличить взаимную информацию между признаками и целевой переменной
По DPI, feature engineering не может увеличить I(X;Y) - только сохранить или уменьшить. Цель - не потерять нужную информацию при преобразованиях.
Марков: X → g(X) → Y. По DPI: I(X;Y) ≥ I(g(X);Y). Признаки g(X) - это функции X; информация о Y не может быть больше, чем в исходных X.
Вопрос на интервью: «Что такое Data Processing Inequality и почему она важна для ML?»
Практические применения
Финальный тип вопросов: «где теория информации встречается в реальных системах?» Здесь важно связать теорию с конкретикой: JPEG → R-D трейдофф; рекомендательные системы → I(user;recommendation) как метрика; A/B тесты → KL-дивергенция между группами; differential privacy → информационное ограничение на утечку.
**Применения IT в ML-индустрии:** 1. Entropy regularization в RL (SAC, максимизация политики-энтропии). 2. KL-дивергенция в RLHF (KL от reference policy). 3. Mutual Information в feature selection. 4. Differential privacy: ε-DP ↔ ограничение на I(алгоритм;данные). 5. Model compression = минимизация I(веса;данные).
| Система | Применение IT | Метрика |
|---|---|---|
| SAC (RL) | Entropy regularization: max H(π) | Entropy H(π) |
| RLHF (ChatGPT) | KL penalty от ref policy | KL[π||π_ref] |
| Recommender | Max I(user;item) | Mutual Information |
| Differential Privacy | ε-DP ≈ ограничение на I | ε, δ параметры |
| Knowledge Distillation | KL[soft_teacher||student] | KL дивергенция |
Историческая справка
Soft Actor-Critic (Haarnoja et al., 2018) формализовал entropy regularization в RL. RLHF (InstructGPT, 2022) использует KL-дивергенцию как штраф для предотвращения «mode collapse» политики. Differential Privacy (Dwork, 2006) - информационно-теоретическая гарантия приватности.
Теория информации применима только к сжатию и телекоммуникациям
IT пронизывает ML: VAE (ELBO), RLHF (KL penalty), differential privacy (ε-DP), feature selection (MI), model compression (MDL). Это универсальный язык для описания информации в системах.
Информация - фундаментальная концепция. Где есть данные, обучение, неопределённость - там есть IT. ML - это в значительной мере «обучение эффективным информационным представлениям».
В RLHF для ChatGPT добавляют KL[π || π_ref] штраф. Зачем?
Ключевые идеи
- **Энтропия:** H = 0 (детерм.) до log₂(n) (равном.). Нечестная монета p=0.99 имеет H≈0.08 бит. Conditioning reduces entropy.
- **Кодирование:** Хаффман даёт H ≤ L < H+1. nH бит - минимальный размер n символов. При вероятностях-степенях-2 Хаффман = оптимум.
- **Пропускная способность:** C = B log₂(1+SNR) для AWGN. BSC(p): C = 1-H(p). I(X;Y) = H(X) − H(X|Y) ≥ 0.
- **Применения в ML:** RLHF (KL штраф), SAC (entropy reg), VAE (ELBO), differential privacy (ε-DP). Data processing inequality: обработка не создаёт информацию.
Связанные темы
Подготовка к интервью опирается на все предыдущие темы:
- Энтропия и взаимная информация — Базовые определения - необходимое условие для всех остальных вопросов
- Information Theory в ML — ELBO, IB, MINE - самые частые продвинутые вопросы на ML-интервью
- Канал связи и пропускная способность — Формула Шеннона и концепция пропускной способности - стандарт System Design
Вопросы для размышления
- Если интервьюер спрашивает «объясните интуицию KL-дивергенции», как ответить за 2 минуты без формул?
- Как ответить на вопрос «почему ChatGPT иногда уверен неправильно?» используя концепции IT (энтропия выхода, KL от reference)?
- Предположим, задача: «дано N видео, нужно выбрать 10 для показа пользователю». Как information-theoretic подход помог бы здесь?