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

Модуль 10. Алгоритмическая теория информации: кратчайшие описания, MDL и универсальное предсказание

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

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

Вопрос 10.2.1

10.2. Кратчайшая программа как длина описания

Что измеряет префиксная колмогоровская сложность $K_U(x)$ ?

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

x

CВремя работы самого быстрого алгоритмаDДлину кратчайшей самоделимитирующейся программы для

x

на фиксированной универсальной машине

U

A) Семантическую ценность строки

B) Энтропию неизвестного распределения, породившего $x$

C) Время работы самого быстрого алгоритма

D) Длину кратчайшей самоделимитирующейся программы для $x$ на фиксированной универсальной машине $U$

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

Правильный ответ: D. K_U(x) измеряет длину программы. Она не определяет время вычисления, смысл объекта или вероятность без заданной модели.

Вопрос 10.2.2

10.2. Кратчайшая программа как длина описания

Почему в общей верхней границе для префиксной сложности появляется надбавка к $|x|$ ?

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

x

A) Универсальная машина обязана работать медленно

B) Префиксная сложность определена только для случайных строк

C) Строка всегда предварительно шифруется

D) Программа должна быть самоделимитирующейся: декодер должен понять, где заканчивается описание длины и начинается $x$

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

Правильный ответ: D. Типичная граница имеет вид K(x)≤|x|+K(|x|)+O(1).

Вопрос 10.2.3

10.2. Кратчайшая программа как длина описания

Что утверждает теорема инвариантности?

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

x

BВсе универсальные машины имеют одну и ту же кратчайшую программуC

K(x)

совершенно не зависит от языка программированияDЦена интерпретатора всегда равна нулю

A) Оптимальная универсальная машина имитирует другую префиксную машину с аддитивной константой, не зависящей от $x$

B) Все универсальные машины имеют одну и ту же кратчайшую программу

C) $K(x)$ совершенно не зависит от языка программирования

D) Цена интерпретатора всегда равна нулю

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

Правильный ответ: A. Машина остаётся частью определения; теорема ограничивает различие фиксированной ценой интерпретатора.

Вопрос 10.2.4

10.2. Кратчайшая программа как длина описания

Как следует интерпретировать $K(x\mid y)$ ?

Один правильный вариантAДлину кратчайшего дополнительного описания

x

, когда

y

уже доступен декодеруBРасстояние Хэмминга между

x

y

CВремя декодирования

x

DЭнтропию

y

после наблюдения

x

A) Длину кратчайшего дополнительного описания $x$ , когда $y$ уже доступен декодеру

B) Расстояние Хэмминга между $x$ и $y$

C) Время декодирования $x$

D) Энтропию $y$ после наблюдения $x$

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

Правильный ответ: A. y выступает дополнительной информацией; величина относится к двум индивидуальным объектам.

Вопрос 10.2.5

10.2. Кратчайшая программа как длина описания

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

Один правильный вариантAОно автоматически даёт причинную модель объектаBОно доказывает, что объект создан разумным агентомCЕго всегда находит gzipDОно свидетельствует о регулярности, но не гарантирует смысл, истинность, полезность или быстрое вычисление

A) Оно автоматически даёт причинную модель объекта

B) Оно доказывает, что объект создан разумным агентом

C) Его всегда находит gzip

D) Оно свидетельствует о регулярности, но не гарантирует смысл, истинность, полезность или быстрое вычисление

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

Правильный ответ: D. Длина описания и семантические или вычислительные свойства — разные уровни анализа.

Вопрос 10.3.1

10.3. Несжимаемость, невычислимость и реальные компрессоры

Какова максимальная доля $n$ -битных строк с $K(x)<n-c$ по подсчёту коротких программ?

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

1/c

BМеньше

2^{-c}

CРовно

1/2

DОна стремится к единице

A) $x$

B) Меньше $x$

C) Ровно $1/2$

D) Она стремится к единице

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

Правильный ответ: B. Программ короче n-c меньше 2^(n-c), а строк длины n — 2^n.

Вопрос 10.3.2

10.3. Несжимаемость, невычислимость и реальные компрессоры

Какое вычислительное свойство имеет $K(x)$ ?

Один правильный вариантAОна вычислима, но только экспоненциально медленноBОна полувычислима снизуCОна равна длине лучшего ZIP-архиваDОна полувычислима сверху, но невычислима

A) Она вычислима, но только экспоненциально медленно

B) Она полувычислима снизу

C) Она равна длине лучшего ZIP-архива

D) Она полувычислима сверху, но невычислима

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

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

Вопрос 10.3.3

10.3. Несжимаемость, невычислимость и реальные компрессоры

Что даёт реальный без потерь компрессор $C$ для $K(x)$ ?

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

K(x)\le |C(x)|+c_C

A) Точное значение с ошибкой не более одного бита

B) Нижнюю границу

C) Несмещённую статистическую оценку

D) Вычислимую верхнюю границу $x$

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

Правильный ответ: D. Константа оплачивает декомпрессор, формат и соглашения о входе.

Вопрос 10.3.4

10.3. Несжимаемость, невычислимость и реальные компрессоры

Почему поток псевдослучайного генератора (PRNG) с коротким начальным значением (seed) может плохо сжиматься gzip, хотя иметь малую $K(x)$ относительно длины?

Один правильный вариантAGzip ищет ограниченный класс регулярностей, а не перебирает все программыBPRNG обязательно использует истинную физическую случайностьCКолмогоровская сложность применима только к текстуDSeed не является частью описания

A) Gzip ищет ограниченный класс регулярностей, а не перебирает все программы

B) PRNG обязательно использует истинную физическую случайность

C) Колмогоровская сложность применима только к тексту

D) Seed не является частью описания

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

Правильный ответ: A. Короткое генеративное описание может лежать вне языка конкретного компрессора.

Вопрос 10.4.1

10.4. Где встречаются Шеннон и Колмогоров

Как связаны энтропия вычислимого распределения $P$ и ожидаемая префиксная сложность?

Один правильный вариантAОни точно равны для каждого отдельного исходаB

\mathbb E K(X)\le0

H_2(P)\le\mathbb E K(X)\le H_2(P)+K(P)+O(1)

DМежду ними нет связи даже в среднем

A) Они точно равны для каждого отдельного исхода

B) $x$

C) $y$

D) Между ними нет связи даже в среднем

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

Правильный ответ: C. Верхняя граница дополнительно оплачивает описание самого распределения; на длинном блоке эта цена на символ исчезает.

Вопрос 10.5.1

10.5. Алгоритмическая вероятность и индукция Соломонова

Почему префиксной программе $p$ естественно назначить вес $2^{-|p|}$ ?

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

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

B) Префиксные программы удовлетворяют неравенству Крафта, поэтому их веса суммируются не более чем в единицу

C) Такой выбор делает универсальный предиктор вычислимым

D) Вес не зависит от универсальной машины

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

Правильный ответ: B. Префиксность превращает длины программ в допустимые кодовые веса.

Вопрос 10.5.2

10.5. Алгоритмическая вероятность и индукция Соломонова

Чем последовательная соломоновская $M(x)$ отличается от обычной вероятностной меры?

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

A) Она всегда равномерна

B) Это полумера: часть массы может приходиться на остановившиеся или бесконечно вычисляющие программы

C) Она не использует программы

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

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

Правильный ответ: B. Поэтому в общем случае M(x)≥M(x0)+M(x1).

Вопрос 10.5.3

10.5. Алгоритмическая вероятность и индукция Соломонова

Что выражает универсальное доминирование?

Один правильный вариантAВсе вычислимые модели получают одинаковый априорный весB

M

совпадает с истинным источником после первого символаC

M

назначает данным под любой вычислимой моделью

\mu

вероятность не меньше

\mu(x)

, умноженной на коэффициент, зависящий от сложности моделиDЛюбая LLM реализует

M

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

B) $x$ совпадает с истинным источником после первого символа

C) $M$ назначает данным под любой вычислимой моделью $\mu$ вероятность не меньше $\mu(x)$ , умноженной на коэффициент, зависящий от сложности модели

D) Любая LLM реализует $M$

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

Правильный ответ: C. Обычно M(x)≥2^(-K(μ)-O(1))μ(x), что ограничивает суммарную избыточную логарифмическую потерю.

Вопрос 10.5.4

10.5. Алгоритмическая вероятность и индукция Соломонова

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

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

A) Универсальная смесь невычислима из-за проблемы остановки

B) Ей требуется слишком большой, но конечный набор данных

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

D) Она не допускает условных вероятностей

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

Правильный ответ: A. Нельзя решить, какие ещё программы когда-нибудь внесут вклад в требуемый префикс.

Вопрос 10.5.5

10.5. Алгоритмическая вероятность и индукция Соломонова

[Факультативно]

Какое различие скрывает популярная запись «универсальная вероятность $\approx2^{-K}$ »?

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

A) Эти две записи тождественны для любой модели универсальной машины

B) Одна формула использует биты, а другая всегда наты

C) Последовательная полумера не содержит программ

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

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

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

Вопрос 10.6.1

10.6. MDL: модель тоже должна оплатить себя

Что минимизирует простой двухчастный MDL-код?

Один правильный вариантAТолько обучающую функцию потерьBТолько число параметровC

L(h)+L(D\mid h)

DТолько время обучения

A) Только обучающую функцию потерь

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

C) $L(h)+L(D\mid h)$

D) Только время обучения

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

Правильный ответ: C. Модель оплачивается вместе с остатком данных, который она не объяснила.

Вопрос 10.6.2

10.6. MDL: модель тоже должна оплатить себя

Что дополнительно измеряет предиктивно-последовательный код (prequential code) по сравнению с одной итоговой точностью?

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

A) Только размер файла с весами

B) Насколько быстро алгоритм обучения начинает назначать хорошие вероятности новым меткам

C) Температуру ускорителя

D) Точную колмогоровскую сложность

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

Правильный ответ: B. Ранние ошибки увеличивают длину сообщения даже при одинаковом конечном качестве.

Вопрос 10.6.3

10.6. MDL: модель тоже должна оплатить себя

Когда гауссовское априорное распределение приводит к $L_2$ -штрафу в MAP-оценивании?

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

A) В фиксированной параметризации при соответствующих априорном распределении и функции правдоподобия

B) Для любого оптимизатора и любой параметризации без дополнительных условий

C) Только для дискретных параметров

D) Никогда

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

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

Вопрос 10.7.1

10.7. Сходство через общую структуру

Что практическая NCD подставляет вместо невычислимой $K$ ?

Один правильный вариантAКорреляцию ПирсонаBЕвклидово расстояниеCДлины, полученные конкретным компрессором

C

DЧисло параметров нейросети

A) Корреляцию Пирсона

B) Евклидово расстояние

C) Длины, полученные конкретным компрессором $L(h)+L(D\mid h)$

D) Число параметров нейросети

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

Правильный ответ: C. Поэтому NCD наследует индуктивное смещение, заголовки и ограничения выбранного компрессора.

Вопрос 10.7.2

10.7. Сходство через общую структуру

Почему для NCD иногда вычисляют и $C(xy)$ , и $C(yx)$ ?

Один правильный вариантAРеальный компрессор может быть чувствителен к порядку конкатенацииBЧтобы удвоить набор данныхCПотому что

K(x)=K(y)

DТеоретическая NID всегда отрицательна

A) Реальный компрессор может быть чувствителен к порядку конкатенации

B) Чтобы удвоить набор данных

C) Потому что $L(h)+L(D\mid h)$

D) Теоретическая NID всегда отрицательна

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

Правильный ответ: A. Минимум или среднее двух порядков уменьшает искусственную асимметрию.

Вопрос 10.8.1

10.8. LLM и универсальное предсказание

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

Один правильный вариантAВероятностный предиктор плюс согласованный энтропийный кодер дают компрессор без потерьBНизкая перплексия (PPL) доказывает пониманиеCРазмер контекста равен колмогоровской сложности текстаDLLM суммирует все вычислимые программы

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

B) Низкая перплексия (PPL) доказывает понимание

C) Размер контекста равен колмогоровской сложности текста

D) LLM суммирует все вычислимые программы

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

Правильный ответ: A. Эквивалентность предсказания и сжатия операциональна; семантические выводы требуют отдельной проверки.

Вопрос 10.8.2

10.8. LLM и универсальное предсказание

Как корректнее описать байесовскую интерпретацию обучения в контексте (in-context learning, ICL)?

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

A) Это универсальная теорема для всех трансформеров и промптов

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

C) ICL не зависит от распределения предобучения

D) Она делает LLM эквивалентной соломоновскому предиктору

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

Правильный ответ: B. Например, строгий анализ возможен для структурированной смеси скрытых марковских моделей (HMM).

Вопрос 10.9.1

10.9. Математическое углубление: AIXI

[Факультативно]

Каков точный статус AIXI?

Один правильный вариантAПрактический алгоритм с полиномиальным временемBМашинно-независимая верхняя граница интеллектаCНевычислимый нормативный объект, соединяющий универсальное предсказание и планирование ожидаемой наградыDВариант обычного классификатора с учителем

A) Практический алгоритм с полиномиальным временем

B) Машинно-независимая верхняя граница интеллекта

C) Невычислимый нормативный объект, соединяющий универсальное предсказание и планирование ожидаемой награды

D) Вариант обычного классификатора с учителем

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

Правильный ответ: C. Её свойства зависят от универсальной машины, класса сред, награды и других деталей постановки.

Вопрос 10.10.1

10.10. Факультативный физический мост

[Факультативно]

К чему непосредственно относится предел $k_BT\ln2$ ?

Один правильный вариантAК каждой операции с плавающей точкой (FLOP) независимо от устройстваBК минимальному среднему тепловыделению при квазистатическом стирании равновероятного битаCК длине кратчайшей программыDК каждому токену LLM

A) К каждой операции с плавающей точкой (FLOP) независимо от устройства

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

C) К длине кратчайшей программы

D) К каждому токену LLM

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

Правильный ответ: B. Для связи с реальным устройством нужно определить физическую реализацию и логически необратимые операции.

Вопрос 10.12.1

10.12. Итоги

Какое утверждение лучше всего суммирует границы модуля?

Один правильный вариантAЛучший архиватор вычисляет

K(x)

BСжатие, предсказание, понимание и интеллект — одно и то же числоCПеред сравнением «сложности» нужно уточнить код, язык, декодер, точность, вычислительный бюджет и включённые затратыDКороткая программа всегда быстро исполняется

A) Лучший архиватор вычисляет $x$

B) Сжатие, предсказание, понимание и интеллект — одно и то же число

C) Перед сравнением «сложности» нужно уточнить код, язык, декодер, точность, вычислительный бюджет и включённые затраты

D) Короткая программа всегда быстро исполняется

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

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