Теория информации для машинного обучения6 / 16

Модуль 6. Кодирование источника: от энтропии к реальным битам

Выберите ответы и нажмите «Проверить». Для чисел подходят точка, запятая и простые дроби. Ответы и черновики сохраняются в этом браузере и общие для RU/EN.

Проверено: 0 / 29 · Верно: 0

Вопрос 6.1.1

6.1. Инженерная постановка: вероятностная модель и энтропийный кодер

Как интерпретируется $D_{\mathrm{KL},2}(P\|Q)$ при идеальном кодировании данных из $P$ с помощью модели $Q$ ?

Один правильный вариантAКак максимальная длина кодового словаBКак ожидаемая дополнительная длина из-за рассогласования модели, в битах на символCКак размер алфавитаDКак накладные расходы округления целых длин кодовых слов

A) Как максимальная длина кодового слова

B) Как ожидаемая дополнительная длина из-за рассогласования модели, в битах на символ

C) Как размер алфавита

D) Как накладные расходы округления целых длин кодовых слов

Ответ и разбор

Правильный ответ: B. Кросс-энтропия раскладывается как H₂(P) + D_KL,2(P‖Q), поэтому член KL и есть надбавка за рассогласование. Округление — отдельная плата, добавляющаяся сверху.

Вопрос 6.2.1

6.2. Префиксные коды и неравенство Крафта—Макмиллана

Какое свойство определяет префиксный код?

Один правильный вариантAВсе кодовые слова имеют одинаковую длинуBКаждый символ использует не более двух битCДлины кодовых слов растут с вероятностью символаDНи одно кодовое слово не является началом другого

A) Все кодовые слова имеют одинаковую длину

B) Каждый символ использует не более двух бит

C) Длины кодовых слов растут с вероятностью символа

D) Ни одно кодовое слово не является началом другого

Ответ и разбор

Правильный ответ: D. Именно это позволяет декодировать слева направо без разделителей. Одинаковые длины дают префиксный код, но необходимыми не являются, а длины должны убывать с вероятностью, а не расти.

Вопрос 6.2.2

6.2. Префиксные коды и неравенство Крафта—Макмиллана

Какие длины могут быть длинами двоичного префиксного кода?

Один правильный вариантAЛюбые положительные целые длиныBТолько длины, сумма которых равна единицеCТолько длины, удовлетворяющие

\sum_i2^{-\ell_i}=1

DРовно положительные целые длины, удовлетворяющие

\sum_i2^{-\ell_i}\le1

A) Любые положительные целые длины

B) Только длины, сумма которых равна единице

C) Только длины, удовлетворяющие $\sum_i2^{-\ell_i}=1$

D) Ровно положительные целые длины, удовлетворяющие $\sum_i2^{-\ell_i}\le1$

Ответ и разбор

Правильный ответ: D. Это критерий Крафта. Требование равенства, как в варианте C, исключило бы коды, оставляющие часть дерева неиспользованной, — а такие коды существуют и вполне корректны.

Вопрос 6.3.1

6.3. Теорема кодирования источника для одного символа

Что утверждает нижняя граница $L\ge H_2(P)$ для сжатия без потерь?

Один правильный вариантAОжидаемая длина кода для заданного источника не может быть меньше его энтропииBКаждый отдельный файл должен иметь длину не менее

nH(P)

CНикакая конкретная строка не может быть сжата ниже среднего по источникуDНикакой код не может сжать ни одну строку ниже её исходной длины

A) Ожидаемая длина кода для заданного источника не может быть меньше его энтропии

B) Каждый отдельный файл должен иметь длину не менее $nH(P)$

C) Никакая конкретная строка не может быть сжата ниже среднего по источнику

D) Никакой код не может сжать ни одну строку ниже её исходной длины

Ответ и разбор

Правильный ответ: A. Граница относится к ожиданию при заданном источнике. Отдельные последовательности могут выходить короче среднего — именно это отрицают варианты B, C и D.

Вопрос 6.3.2

6.3. Теорема кодирования источника для одного символа

Когда односимвольный префиксный код может достичь $L=H_2(P)$ точно?

Один правильный вариантAДля любого распределения после перенумерации символовBТолько для равномерного распределенияCКогда

p_i=2^{-\ell_i}

при целых длинах, то есть бюджет Крафта израсходован полностьюDКогда размер алфавита является степенью двойки

A) Для любого распределения после перенумерации символов

B) Только для равномерного распределения

C) Когда $\sum_i2^{-\ell_i}=1$ при целых длинах, то есть бюджет Крафта израсходован полностью

D) Когда размер алфавита является степенью двойки

Ответ и разбор

Правильный ответ: C. Такое распределение называется двоично-рациональным. Равномерное подходит только при размере, равном степени двойки, поэтому варианты B и D описывают частные случаи, а не условие.

Вопрос 6.4.1

6.4. Кодирование Хаффмана, арифметическое и range-кодирование

Что оптимизирует алгоритм Хаффмана?

Один правильный вариантAМаксимальную длину кодового словаBОжидаемую длину среди двоичных префиксных кодов для известного конечного распределенияCРазмер параметров языковой моделиDОжидаемую длину среди всех однозначно декодируемых кодов, включая блочные

A) Максимальную длину кодового слова

B) Ожидаемую длину среди двоичных префиксных кодов для известного конечного распределения

C) Размер параметров языковой модели

D) Ожидаемую длину среди всех однозначно декодируемых кодов, включая блочные

Ответ и разбор

Правильный ответ: B. Оптимальность действует внутри одного класса: двоичные префиксные коды с одним словом на символ. Кодирование блоками может быть лучше — поэтому вариант D утверждает слишком много.

Вопрос 6.4.2

6.4. Кодирование Хаффмана, арифметическое и range-кодирование

Для двоичного источника $P=(0.99,0.01)$ односимвольный двоичный префиксный код даёт $L=1$ , хотя $H_2(P)\approx0.0808$ . Какой вывод верен?

Один правильный вариантAТеорема Шеннона нарушенаBЭнтропия должна быть не меньше одного битаCАлгоритм Хаффмана здесь не нашёл оптимумаDЦелые односимвольные длины могут стоить почти лишний бит на символ

A) Теорема Шеннона нарушена

B) Энтропия должна быть не меньше одного бита

C) Алгоритм Хаффмана здесь не нашёл оптимума

D) Целые односимвольные длины могут стоить почти лишний бит на символ

Ответ и разбор

Правильный ответ: D. Граница H ≤ L < H + 1 допускает ровно такое поведение. Хаффман оптимален в своём классе; сам класс односимвольных целых длин слишком груб для сильно смещённого источника.

Вопрос 6.4.3

6.4. Кодирование Хаффмана, арифметическое и range-кодирование

Какова ширина финального идеального интервала арифметического кодирования для $x_{1:n}$ ?

Один правильный вариантA

q(x_{1:n})=\prod_tq(x_t\mid x_{<t})

BСредняя вероятность токенаC

1/n

2^{-n}

A) $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$

B) Средняя вероятность токена

C) $1/n$

D) $2^{-n}$

Ответ и разбор

Правильный ответ: A. Интервал сужается мультипликативно на каждом шаге, поэтому его ширина равна вероятности последовательности, а идеальная длина — это −log₂ q(x_(1:n)).

Вопрос 6.4.5

6.4. Кодирование Хаффмана, арифметическое и range-кодирование

Какое утверждение о практическом range-кодере или ANS наиболее точно?

Один правильный вариантAОн выдаёт ровно

-\log_2q(x)

бит без оговорокBОн не использует вероятности моделиCКонечная точность, метаданные и правила границ могут добавить небольшую избыточностьDОн требует статической вероятностной модели

A) Он выдаёт ровно $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$ бит без оговорок

B) Он не использует вероятности модели

C) Конечная точность, метаданные и правила границ могут добавить небольшую избыточность

D) Он требует статической вероятностной модели

Ответ и разбор

Правильный ответ: C. Идеальная информационная длина остаётся ориентиром, но у реализации есть свой протокол и накладные расходы. Адаптивные модели — обычный случай, а не исключение.

Вопрос 6.5.1

6.5. Длинные последовательности: блочное кодирование, AEP и скорость создания энтропии

Что следует из кодирования i.i.d. блоков длины $n$ как суперсимволов?

Один правильный вариантA

L_n/n=0

для любого источникаB

H(X)\le L_n/n<H(X)+1/n

CДекодирование обязано иметь ненулевую вероятность ошибкиD

H(X)\le L_n/n<H(X)+1

A) $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$ для любого источника

B) $H(X)\le L_n/n<H(X)+1/n$

C) Декодирование обязано иметь ненулевую вероятность ошибки

D) $H(X)\le L_n/n<H(X)+1$

Ответ и разбор

Правильный ответ: B. Одна единица округления размазывается по n символам. Вариант D — это односимвольная граница, которую блочное кодирование как раз и улучшает.

Вопрос 6.5.2

6.5. Длинные последовательности: блочное кодирование, AEP и скорость создания энтропии

Что утверждает AEP для i.i.d. источника?

Один правильный вариантAВсе последовательности равновероятныBКаждая последовательность длины

n

имеет вероятность около

2^{-nH}

CЭнтропия одного символа стремится к нулюD

-n^{-1}\log_2p(X^n)

концентрируется около

H_2(X)

A) Все последовательности равновероятны

B) Каждая последовательность длины $nH(P)$ имеет вероятность около $2^{-nH}$

C) Энтропия одного символа стремится к нулю

D) $-n^{-1}\log_2p(X^n)$ концентрируется около $H_2(X)$

Ответ и разбор

Правильный ответ: D. Типичные последовательности приблизительно равновероятны и несут почти всю массу. Вариант B опускает слово «типичные» и потому делает ложное утверждение обо всех последовательностях.

Вопрос 6.5.3

6.5. Длинные последовательности: блочное кодирование, AEP и скорость создания энтропии

Чем код на типичном множестве обычно отличается от безошибочного кода переменной длины?

Один правильный вариантAОн может быть кодом фиксированной скорости с вероятностью ошибки, стремящейся к нулюBОн обязан быть длиннее несжатого сообщенияCОн применим только к одному символуDОн достигает скорости строго ниже скорости создания энтропии

A) Он может быть кодом фиксированной скорости с вероятностью ошибки, стремящейся к нулю

B) Он обязан быть длиннее несжатого сообщения

C) Он применим только к одному символу

D) Он достигает скорости строго ниже скорости создания энтропии

Ответ и разбор

Правильный ответ: A. Нетипичные последовательности либо считаются ошибками, либо требуют отдельного механизма исключений. Асимптотически ни один код не обходит скорость создания энтропии — это исключает вариант D.

Вопрос 6.5.4

6.5. Длинные последовательности: блочное кодирование, AEP и скорость создания энтропии

Какая величина определяет асимптотическую стоимость кодирования стационарного зависимого источника?

Один правильный вариантAТолько

H(X_1)

BМаксимальная длина токенаCСкорость создания энтропии

h=\lim_nH(X_{1:n})/n

DСреднее значение

H(X_i)

по позициям

A) Только $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$

B) Максимальная длина токена

C) Скорость создания энтропии $h=\lim_nH(X_{1:n})/n$

D) Среднее значение $H(X_i)$ по позициям

Ответ и разбор

Правильный ответ: C. Зависимости могут опустить стоимость намного ниже маргинальной энтропии, а варианты A и D игнорируют их, рассматривая позиции по отдельности.

Вопрос 6.6.1

6.6. Метрики языковых моделей: PPL, BPC и BPB

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

Один правильный вариантAПерплексия определена только для ASCII-символовBЛюбой токенизатор даёт одну и ту же PPLCБольший словарь всегда снижает перплексиюDСредний NLL нормируется на разные единицы: токены разного размера и состава

A) Перплексия определена только для ASCII-символов

B) Любой токенизатор даёт одну и ту же PPL

C) Больший словарь всегда снижает перплексию

D) Средний NLL нормируется на разные единицы: токены разного размера и состава

Ответ и разбор

Правильный ответ: D. Даже при фиксированной вероятности текста другая группировка даёт другое среднее на единицу. Направление изменения тоже не фиксировано, так что вариант C не спасает.

Вопрос 6.6.2

6.6. Метрики языковых моделей: PPL, BPC и BPB

Какое утверждение о BPC и BPB верно?

Один правильный вариантAОни дают общий знаменатель, но не гарантируют инвариантности к смене токенизатора и моделиBОни всегда равны восьмиCОни не зависят от предобработкиDОни делают результаты сравнимыми между корпусами

A) Они дают общий знаменатель, но не гарантируют инвариантности к смене токенизатора и модели

B) Они всегда равны восьми

C) Они не зависят от предобработки

D) Они делают результаты сравнимыми между корпусами

Ответ и разбор

Правильный ответ: A. Фиксация единицы убирает один источник несравнимости и оставляет остальные: данные, нормализацию, модель, политику контекста. Поэтому же вариант D утверждает слишком много.

Вопрос 6.6.3

6.6. Метрики языковых моделей: PPL, BPC и BPB

Что произойдёт, если фиксированную вероятность текста просто перегруппировать с отдельных токенов на пары, не меняя $q(x)$ ?

Один правильный вариантAОбщее число бит удвоитсяBBPB обратится в нольCОбщее число бит останется прежним, а перплексия на пару станет квадратом токеннойDИ общее число бит, и перплексия останутся прежними

A) Общее число бит удвоится

B) BPB обратится в ноль

C) Общее число бит останется прежним, а перплексия на пару станет квадратом токенной

D) И общее число бит, и перплексия останутся прежними

Ответ и разбор

Правильный ответ: C. Вероятность сообщения не изменилась, поэтому длина кода измениться не может. Меняется единица, по которой берётся среднее, — именно в этом и различаются варианты C и D.

Вопрос 6.7.1

6.7. Языковая модель как часть компрессора

Какое ограничение важно для сырых коэффициентов сжатия, приведённых для Chinchilla 70B у Delétang и соавторов?

Один правильный вариантAВосстановление было с потерямиBИспользовался словарь всего в один битCОценивание проводилось на одном языкеDСтоимость параметров модели не входила в сырое отношение

A) Восстановление было с потерями

B) Использовался словарь всего в один бит

C) Оценивание проводилось на одном языке

D) Стоимость параметров модели не входила в сырое отношение

Ответ и разбор

Правильный ответ: D. Самодостаточный архив обязан нести и веса, а это радикально меняет картину для гигабайта данных. Утверждение о предсказательной логарифмической потере при этом остаётся верным.

Вопрос 6.8.1

6.8. Размер модели, законы масштабирования и полная длина описания

Что нельзя вывести из одного лишь гладкого убывания тестовой кросс-энтропии по закону масштабирования?

Один правильный вариантAЧто более крупная модель имела меньшие потери в измеренном диапазонеBЧто подогнанная асимптота равна истинной скорости создания энтропии, а разрыв KL стремится к нулюCЧто потери можно измерять в натах или битахDЧто тренд держался на тех масштабах, которые действительно проверялись

A) Что более крупная модель имела меньшие потери в измеренном диапазоне

B) Что подогнанная асимптота равна истинной скорости создания энтропии, а разрыв KL стремится к нулю

C) Что потери можно измерять в натах или битах

D) Что тренд держался на тех масштабах, которые действительно проверялись

Ответ и разбор

Правильный ответ: B. Экстраполяция подгонки к асимптоте и объявление её энтропией источника требуют предположений об источнике, семействе моделей, оптимизации и контексте. Остальные три — просто переформулировки измеренного.

Вопрос 6.8.2

6.8. Размер модели, законы масштабирования и полная длина описания

Какая длина соответствует самодостаточному двухчастному компрессору?

Один правильный вариантAТолько

L(x\mid\theta)

BТолько число параметровC

L(\theta)+L(x\mid\theta)

плюс необходимые метаданныеDТолько

L(\theta)

, ведь данные следуют из модели

A) Только $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$

B) Только число параметров

C) $L(\theta)+L(x\mid\theta)$ плюс необходимые метаданные

D) Только $L(\theta)$ , ведь данные следуют из модели

Ответ и разбор

Правильный ответ: C. Передать нужно обе части и протокол их декодирования. Валидационный NLL обычно измеряет только вторую часть, потому что модель уже известна обеим сторонам.

Вопрос 6.10.1

6.10. Качество сжатия и способности модели

Какое итоговое утверждение о сжатии и интеллекте наиболее защитимо?

Один правильный вариантAЛучший компрессор обязан быть лучше в любой форме интеллектаBКачество сжатия точно связано с предсказательной логарифмической потерей и может быть прокси для некоторых способностей, но не является универсальным определением интеллектаCМежду предсказанием и сжатием нет математической связиDСвязь работает только для текста и ломается на других модальностях

A) Лучший компрессор обязан быть лучше в любой форме интеллекта

B) Качество сжатия точно связано с предсказательной логарифмической потерей и может быть прокси для некоторых способностей, но не является универсальным определением интеллекта

C) Между предсказанием и сжатием нет математической связи

D) Связь работает только для текста и ломается на других модальностях

Ответ и разбор

Правильный ответ: B. Связь предсказания и сжатия — точная конструкция. Переход от неё к общему понятию интеллекта — гораздо более сильная эмпирическая и философская гипотеза, а сама конструкция текстом не ограничена.

Вопрос 6.4.4

6.4. Кодирование Хаффмана, арифметическое и range-кодирование

Почему пятибитный префикс 01111 не является корректным завершением для $[0.45,0.48)$ ?

Один правильный вариантAЧисло

15/32

лежит вне интервалаBАрифметические коды обязаны иметь чётную длинуCДвоично-рациональный интервал

[15/32,16/32)

не помещается целиком в целевойDПять бит меньше идеальной длины примерно в 5.06 бита

A) Число $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$ лежит вне интервала

B) Арифметические коды обязаны иметь чётную длину

C) Двоично-рациональный интервал $[15/32,16/32)$ не помещается целиком в целевой

D) Пять бит меньше идеальной длины примерно в 5.06 бита

Ответ и разбор

Правильный ответ: C. Поместиться должен весь интервал двоичных продолжений, а не одна точка. Число 15/32 как раз лежит внутри целевого интервала — поэтому вариант A и соблазнителен, и неверен.

Вопрос 6.5.5

6.5. Длинные последовательности: блочное кодирование, AEP и скорость создания энтропии

Как следует читать теорему Шеннона—Макмиллана—Бреймана?

Один правильный вариантAДля стационарного эргодического источника нормированная информационная плотность сходится к скорости создания энтропии при стандартных условияхBУ любого текста универсальная энтропия в один бит на символCЛюбая нейросеть достигает шенноновского пределаDОна верна для любого стационарного источника, эргодического или нет

A) Для стационарного эргодического источника нормированная информационная плотность сходится к скорости создания энтропии при стандартных условиях

B) У любого текста универсальная энтропия в один бит на символ

C) Любая нейросеть достигает шенноновского предела

D) Она верна для любого стационарного источника, эргодического или нет

Ответ и разбор

Правильный ответ: A. Теорема относится к заданному стохастическому источнику, а не к неопределённому объекту «язык». Эргодичность входит в условие и отбросить её нельзя.

Вопрос 6.9.1

6.9. Математическое углубление: универсальное кодирование, онлайн log-loss и ICL

Каков regret байесовской смеси $Q=\sum_jw_jP_j$ относительно модели $P_j$ на конкретной последовательности?

Один правильный вариантAНе более

\log_2(1/w_j)

битBРовно

n

битCВсегда бесконеченDНе более

\log_2(1/w_j)

бит на символ

A) Не более $q(x_{1:n})=\prod_tq(x_t\mid x_{<t})$ бит

B) Ровно $n$ бит

C) Всегда бесконечен

D) Не более $\log_2(1/w_j)$ бит на символ

Ответ и разбор

Правильный ответ: A. Это следует прямо из Q(x) ≥ w_j P_j(x). Граница относится ко всей последовательности, поэтому на символ она стремится к нулю — это и упускает вариант D.

Вопрос 6.9.2

6.9. Математическое углубление: универсальное кодирование, онлайн log-loss и ICL

Какова аккуратная связь между универсальным предсказанием и обучением в контексте?

Один правильный вариантAЛюбая LLM доказанно является оптимальным байесовским предсказателем для любого промптаBКонтекст может адаптировать предсказания без обновления весов, но теоремы требуют явных структурных предположенийCICL не связано с вероятностным предсказаниемDICL — это в точности байесовское предсказание смесью по известному классу моделей

A) Любая LLM доказанно является оптимальным байесовским предсказателем для любого промпта

B) Контекст может адаптировать предсказания без обновления весов, но теоремы требуют явных структурных предположений

C) ICL не связано с вероятностным предсказанием

D) ICL — это в точности байесовское предсказание смесью по известному классу моделей

Ответ и разбор

Правильный ответ: B. Конкретные теоретические модели дают полезные механизмы, а не универсальную гарантию для реальных систем. Вариант D выдаёт за факт то, что эти модели предполагают.

Вопрос 6.11.1

6.11. Практический протокол оценивания LLM как компрессора

Почему при оценивании causal-LM со скользящим окном цели нужно считать после сдвига меток?

Один правильный вариантAМодель сравнивает logits[:, :-1] с labels[:, 1:], поэтому наивная длина суффикса даёт ошибку на единицуBЛогиты не содержат вероятностейCЧтобы искусственно снизить перплексиюDПотому что первый токен каждого окна непредсказуем

A) Модель сравнивает logits[:, :-1] с labels[:, 1:], поэтому наивная длина суффикса даёт ошибку на единицу

B) Логиты не содержат вероятностей

C) Чтобы искусственно снизить перплексию

D) Потому что первый токен каждого окна непредсказуем

Ответ и разбор

Правильный ответ: A. Корректный протокол проверяет, что каждый исходный токен попал в функцию потерь ровно один раз. Первый токен окна действительно не оценивается, но это следствие сдвига, а не причина считать аккуратно.

Вопрос 6.C.1

Вычислительный блок

Для $P=(0.40,0.20,0.15,0.15,0.10)$ оптимальный код Хаффмана имеет длины $(1,3,3,3,3)$ . Вычислите ожидаемую длину кода в битах на символ. (допуск 0.005)

ОтветАбсолютный допуск: ±0.005

Ответ и разбор

Числовой ответ: 2.2 (допуск 0.005). Ожидаемая длина равна 0.40 · 1 + 0.60 · 3 = 2.20 бита, тогда как энтропия равна 2.146 бита. Зазор около 0.054 бита — это цена целых длин, с большим запасом внутри гарантии H ≤ L < H + 1.

Вопрос 6.C.2

Вычислительный блок

Данные приходят из $P=(0.5,0.25,0.25)$ , а идеальные дробные длины кода построены по модели $Q=(0.25,0.25,0.5)$ . Вычислите ожидаемую длину в битах на символ. (допуск 0.002)

ОтветАбсолютный допуск: ±0.002

Ответ и разбор

Числовой ответ: 1.75 (допуск 0.002). Ожидаемая длина равна кросс-энтропии H₂(P,Q) = 1.75 бита, а энтропия P равна 1.5 бита. Разность в 0.25 бита — это D_KL(P‖Q), надбавка за рассогласование, ещё до всякого округления.

Вопрос 6.C.3

Вычислительный блок

При $p(A)=0.5$ , $p(B)=0.3$ и $p(C)=0.2$ вычислите идеальную длину арифметического кода строки ACB в битах. (допуск 0.005)

ОтветАбсолютный допуск: ±0.005

Ответ и разбор

Числовой ответ: 5.059 (допуск 0.005). Финальный интервал имеет ширину 0.5 · 0.2 · 0.3 = 0.03, поэтому идеальная длина равна −log₂ 0.03 = 5.059 бита. Для завершения кода нужен целый двоично-рациональный интервал внутри целевого — поэтому реально выдаётся шестибитный префикс, а не пятибитный.

Вопрос 6.C.4

Вычислительный блок

(факультативно)

Байесовская смесь назначает модели $P_j$ вес $w_j=1/64$ . Каков наихудший regret смеси относительно $P_j$ на любой последовательности, в битах? (допуск 0.005)

ОтветАбсолютный допуск: ±0.005

Ответ и разбор

Числовой ответ: 6 (допуск 0.005). Regret не превышает log₂ 64 = 6 бит на всю последовательность, какой бы длинной она ни была. На символ он поэтому стремится к нулю — именно это делает смесь пригодным универсальным кодом.