Стоимость адреса: сколько бит стоит ответ 

Возьмем алфавит из тридцати двух знаков и страницу фиксированной длины в 3200 знаков — сорок строк по восемьдесят. Множество всех таких страниц конечно и полностью определено: в нем 32 в степени 3200 элементов. Никакого отбора, никакой генерации, никакого авторства — множество задано самим фактом определения алфавита и длины.

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

Конструкция принадлежит Борхесу ^[1], и в литературоведении она читается как притча о бессмысленности всеобщего знания. Для инженера в ней есть другое содержание. Как только пространство задано полностью, вопрос «существует ли ответ» теряет смысл: ответ существует по построению. Остается ровно один вопрос — как назвать его место.

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

Разница между 10¹¹⁰ и 10⁴⁸¹⁶ — это не разница в производительности, которую закроет следующее поколение железа. Между этими числами 4706 порядков. Удвоение производительности добавляет к показателю 0,3; чтобы закрыть разрыв, удвоений нужно около пятнадцати тысяч. Перебор здесь запрещен не бюджетом, а размерностью задачи ^[14].

Раз перебор невозможен, к странице нужно приходить сразу — по адресу. Возникает естественное желание сделать адрес компактным: короткий номер полки, ключ из нескольких символов, идентификатор в базе. Это желание неисполнимо, и причина лежит в счете, а не в изобретательности.

Адресация обязана быть взаимно однозначной: разным страницам — разные адреса, иначе по адресу нельзя вернуться. Значит адресов нужно не меньше, чем страниц. Если адрес записывается в том же алфавите, его длина не может быть меньше длины страницы. В битах это выглядит так.

Отсюда следует утверждение, которое стоит проговорить отдельно, потому что оно выглядит как парадокс, а является тавтологией: указать на страницу стоит ровно столько же, сколько стоит сама страница. Никакой «короткой ссылки» на произвольный элемент такого пространства не существует. Ссылки, которые мы используем ежедневно, коротки по другой причине — они указывают не на произвольный элемент, а на элемент заранее суженного множества.

У полного пространства есть свойство, которое в притче Борхеса выглядит декоративным, а в инженерной практике оказывается источником самых дорогих ошибок. В нем нет пустых мест. Любой синтаксически корректный адрес указывает на заполненную страницу. Понятия «здесь ничего нет» в пространстве не существует.

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

Борхес описывает это как каталог библиотеки и тысячи ложных каталогов, от него неотличимых ^[1]. В современной практике то же самое называется галлюцинацией языковой модели, и обсуждается обычно как дефект обучения. Из устройства пространства видно, что это не дефект: механизм, который всегда стоит на какой-то полке, не имеет способа сообщить, что полка не та.

• Отказ «не знаю» требует отдельного механизма — само пространство его не подсказывает.
• Уверенность ответа не связана с его верностью: она измеряется внутри, верность — снаружи.
• Уговоры и инструкции не создают бит информации, а значит не сдвигают адрес.

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

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

Определение восходит к Шеннону ^[2] и в теории информации стандартно ^{[9, 13]}. Практическая его ценность в том, что оно уравнивает в правах вещи, которые обычно обсуждаются на разных языках. Справочник номенклатуры, регламент предприятия, ГОСТ, дообученная модель, удачно составленный промпт и полевой замер — все это поставщики бит, и различаются они только количеством и ценой.

Библиотека Борхеса задает на множестве страниц равномерное распределение: все полки равноправны, никакая не предпочтительнее. Языковая модель задает на том же множестве неравномерное распределение. Множество одно, различие целиком в мере.

Из неравномерности сразу следует экономия записи. Если некоторые страницы вероятнее других, им можно назначить более короткие коды за счет удлинения кодов для маловероятных. Оптимальная длина кода задается логарифмом вероятности, а средняя длина — энтропией ^{[2, 9]}.

Отсюда рабочее определение, которым работа пользуется дальше. Знание — это величина, на которую известное сокращает адрес относительно равномерного случая. Не метафора и не переформулировка: разность измеряется в битах и проверяется замером, который приведен в части V.

Тот же вывод объясняет, почему задача сжатия и задача предсказания — одна задача. Архиватор, который сжимает текст лучше, по построению предсказывает его лучше: длина выхода равна минус логарифму вероятности, назначенной моделью. Это соображение лежит в основе конкурсов на сжатие текста как меры интеллекта ^[10] и в принципе минимальной длины описания ^[16].

Формула (2) дает границу для произвольной страницы. Но конкретные страницы бывают устроены просто: страница из 3200 пробелов описывается фразой «3200 пробелов», и адрес такой длины не нужен. Величина, отвечающая на вопрос «какова длина кратчайшего описания именно этого объекта», введена Колмогоровым и Соломоновым ^{[6, 7]}.

У этой величины два свойства, которые нужно держать в голове вместе. Первое: почти все страницы несжимаемы. Строк длины L ровно A^L, а описаний короче L−k существенно меньше, поэтому доля страниц, для которых адрес удается сократить хотя бы на десять бит, меньше одной тысячной. Второе: величина невычислима — не существует алгоритма, который по строке выдаст длину ее кратчайшего описания.

Из первого свойства следует и практическое ограничение на ожидания. Интуиция подсказывает, что осмысленный текст «должен» сжиматься сильно. Осмысленный — да, и часть V покажет, насколько. Но осмысленные страницы составляют исчезающую долю пространства, и утверждение «почти все несжимаемо» относится к пространству целиком, а не к тому его углу, в котором работают люди.

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

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

Адреса нет, но есть распределение: одни продолжения вероятнее других. Движение идет по градиенту правдоподобия, шаг за шагом, и каждый шаг отсекает часть пространства. Именно это делает авторегрессионная модель, и часть V меряет, сколько бит такой механизм дает на нашем корпусе.

Свойство, из-за которого механизм ставится вторым, а не первым: он приводит туда, где похоже, и не имеет средства отличить это место от того, где верно. Оценка правдоподобия считается внутри пространства, а верность определяется снаружи — в главе 04 показано, что изнутри различие недоступно.

• Скорость: наибольшая среди всех механизмов, цена бита близка к нулю.
• Гарантия: отсутствует; уверенность модели не является оценкой верности.
• Область: там, где нужная страница лежит в плотной области распределения, то есть похожа на виденное при обучении.
• Отказ: невозможен без внешнего механизма — пустых полок в пространстве нет.

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

Ограничение механизма — не в мощности, а в охвате. Выводимо только то, что следует из принятых аксиом. Утверждение о выручке конкретного предприятия за конкретный квартал не выводится ни из какой системы аксиом: оно не следует, оно происходит. Область применимости вывода — формальные объекты, и она исчезающе мала относительно пространства.

Механизм генерирует кандидатов и отбраковывает их проверкой. Полный перебор невозможен (глава 02), поэтому речь всегда о направленном поиске в суженной области. Стоимость складывается из числа проверенных кандидатов и цены одной проверки.

Ключевое условие — асимметрия. Механизм имеет смысл тогда и только тогда, когда проверка существенно дешевле генерации: маршрут проверяется быстрее, чем строится, раскрой считается быстрее, чем подбирается. Там, где проверка стоит столько же, сколько генерация, механизм вырождается в перебор и упирается в главу 02.

Адрес нельзя ни вспомнить, ни вывести, ни угадать — остается пойти и посмотреть. Механизм самый дорогой и самый медленный из семи, и он единственный, который добавляет в систему информацию, которой в ней не было.

Утверждение сформулировано в части IV как закон сохранения и там же разобрано подробно. Здесь достаточно указать на следствие для практики: если задача требует бит, которых нет ни в одном справочнике и ни в одном корпусе, ни одна модель их не создаст. Требуется замер, и стоимость проекта определяется стоимостью замера, а не выбором архитектуры.

Механизм работает не с искомой страницей, а с ее дополнением: каждое действие объявляет часть пространства несовместимой с наблюдениями. По формуле (3) максимум бит дает разбиение на равные половины — это верхняя граница информативности одного вопроса.

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

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

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

Отсюда закон, к которому работа шла с части III. Механизмы памяти, навигации, вывода, перебора и сужения алфавита перераспределяют биты, уже находящиеся в системе. Взаимодействие с реальностью происходит в двух механизмах — измерение и отсечение, — и только они увеличивают взаимную информацию с положением дел.

Корпус обучения состоит из текстов, написанных людьми, которые что-то измеряли, наблюдали или выводили. Модель извлекает из корпуса регулярности и переносит их на новые запросы. Работа полезная и огромная по объему, но по своей природе это перенос, а не порождение: все биты соответствия в модели импортированы вместе с корпусом.

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

• Справочник заказчика не был в корпусе — бит о нем в модели нет, сколько ни спрашивай.
• События после среза обучения не измерялись моделью — сведений о них нет по построению.
• Внутренние регламенты предприятия существуют в одном экземпляре — вероятность их попадания в корпус равна нулю.

Это же соображение объясняет, почему интеграция дает результат, а наращивание размера модели на таких задачах не дает. Размер увеличивает качество перераспределения уже импортированных бит; отсутствующих бит он не создает.

Распространенная практика — добавлять в запрос требования отвечать точно, признаваться в незнании и не выдумывать. Из закона сохранения видно, что происходит на самом деле: инструкция смещает распределение в сторону осторожных формулировок, но не вносит ни одного бита о том, где лежит верная страница.

Наблюдаемый эффект от таких инструкций реален и объясняется без противоречия: меняется не адресация, а форма ответа. Модель чаще выбирает области пространства, где формулировки уклончивы. Доля неверных утверждений может снизиться просто потому, что снизилась доля утверждений вообще.

Мерим кросс-энтропию: сколько бит на знак тратит модель, предсказывая текст, которого не видела. Разность между пятью битами равномерного случая и измеренной величиной, умноженная на длину страницы, и есть K — биты адреса, которые дает знание языка.

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

Сглаживание Виттена-Белла выбрано потому, что вес отката к модели меньшего порядка вычисляется из числа уникальных продолжений контекста и не настраивается вручную ^[8]. Настраиваемый параметр в такой работе означал бы подгонку под ответ.

/** Виттен-Белл: P = (c + T·P_backoff) / (N + T), рекурсивно до равномерного. */
function prob(ctx, ch, k) {
  if (k < 0) return 1 / 32                      // равномерное дно
  const row = tables[k].get(ctx)
  const backoff = prob(k === 0 ? '' : ctx.slice(1), ch, k - 1)
  if (!row) return backoff
  const t = row.counts.size                     // уникальных продолжений
  return ((row.counts.get(ch) ?? 0) + t * backoff) / (row.total + t)
}

let bits = 0
for (let i = order; i < test.length; i++) {
  const ctx = order === 0 ? '' : test.slice(i - order, i)
  bits += -Math.log2(prob(ctx, test[i], order))
}
const bitsPerChar = bits / (test.length - order)

Лучший результат — 1,895 бит на знак при порядке 5. В пересчете на страницу это 6 064 бита вместо 16 000: знание языка и предметной области снимает 9 936 бит, то есть 62 % адреса, и сокращает число кандидатов в 10²⁹⁹¹ раз.

Для сопоставления: классические оценки энтропии печатного английского дают от 0,6 до 1,3 бита на знак по методу угадывания ^{[3, 4]}, около 1,75 бита у моделей PPM середины девяностых ^[11] и порядка 1,75 бита в оценке по большому корпусу ^[5]. Наш результат лежит в том же диапазоне, что ожидаемо: алфавит и метод различаются, порядок величины — нет.

Модель порядка 8 располагает более длинным контекстом, чем модель порядка 5, и формально включает ее в себя. Тем не менее на отложенной части она работает хуже: 2,188 бита против 1,895. Разница в 0,293 бита на знак — это 938 бит адреса, потерянных при переходе к более мощной модели.

Причина в разреженности. Контекстов длины 8 в алфавите из 32 знаков может быть до 32⁸ ≈ 1,1 · 10¹²; в корпусе из 704 тысяч знаков встречается не более 704 тысяч различных, и почти каждый — по одному разу. Счетчик, построенный на одном наблюдении, не является статистикой: он описывает конкретное место корпуса, а не закономерность языка.

Если объяснение из главы 21 верно, положение минимума должно зависеть от объема обучения: на маленьком корпусе оптимальный порядок ниже, на большом выше. Проверяем прямо: обучаем те же модели на урезанных корпусах и меряем на одной и той же отложенной части в 40 000 знаков.

Гипотеза подтверждается: оптимальный порядок сдвигается с третьего на пятый по мере роста корпуса в тридцать пять раз. При этом на последней строке значения для четвертого и пятого порядков практически сравнялись — 1,920 против 1,896, — то есть корпус только-только дорос до того, чтобы пятый порядок стал оправданным.

Полученная зависимость — количественная форма утверждения из части IV. Биты нельзя взять из воздуха: доступное количество ограничено объемом того, что измерено и записано. Наращивание сложности модели поверх недостаточного корпуса не добавляет бит, а убавляет их, и замер показывает, на сколько именно.

Соберем счет. Каждый бит соответствия реальности поступает через измерение (часть IV). Измерение стоит времени, денег и доступа к объекту, то есть пропускная способность канала конечна. Число вопросов, на которые можно захотеть ответа, не ограничено ничем. Конечный поток против неограниченного спроса — этого достаточно, чтобы закрыть вопрос.

К общему счету добавляются три отдельных ограничения, каждое из которых самостоятельно исключает всеведение.

Невычислимость минимума

Длина кратчайшего описания невычислима (глава 07), поэтому даже для одной задачи нельзя узнать, достаточно ли купленных бит.

Недоступность будущего

Адрес страницы о еще не наступившем событии существует, но отличить ее от соседних можно только после наступления. До этого момента цена адреса бесконечна, и никакая модель этого не меняет.

Вопросы без истинностного значения

Часть запросов не имеет верного ответа в принципе — они некорректно поставлены. Пространство ответит и на них, потому что пустых полок не бывает.

Отрицательный ответ предыдущей главы не делает картину безнадежной, и причина в свойстве, которое легко упустить. Импортированные биты не расходуются при использовании. Один замер, будучи записанным, отвечает на неограниченное число будущих запросов.

Наиболее выгодная форма записи — та, что покрывает наибольшую область пространства наименьшим числом бит. Закон механики занимает несколько строк и заменяет неограниченное число измерений падающих тел. В терминах работы это предельный случай сжатия адреса: короткий указатель на огромную область.

Отсюда рабочее определение, которым удобно пользоваться при разборе задач. Теория — это переиспользуемый указатель. Ее ценность измеряется не убедительностью, а отношением покрытой области к длине записи, и по этому признаку теории сравнимы между собой количественно.

Если знание измеряется в битах сокращения адреса, разнородные исторические события выстраиваются в один ряд. Письменность сделала биты переносимыми во времени. Печать снизила цену копирования до величины, при которой переиспользование стало массовым. Научный метод ввел механизм отсечения (глава 13) как обязательный этап. Каждый шаг снижал цену бита, не меняя природы самой величины.

Языковые модели в этом ряду занимают определенное место, и оно скромнее распространенных ожиданий. Они резко удешевили доступ к уже импортированным битам: то, что раньше требовало часов поиска, занимает секунды. Новых бит они не вносят по построению (глава 17). Это существенное удешевление одного из семи механизмов, а не появление восьмого.

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

• Сколько бит стоит задача. Выбор одной позиции из справочника в 50 000 SKU — 15,6 бита; классификация на два класса — 1 бит; свободный текст на страницу — до 16 000. Величина считается по формуле (3) и задает масштаб всего дальнейшего.
• Где эти биты лежат. В обучении модели, в справочниках заказчика, в его регламентах, в еще не проведенном замере. Ответ «в модели» проверяется прямо: если данные не публиковались, их там нет.
• Каким механизмом они берутся. Семь строк таблицы 4. Обычно рабочая цепочка состоит из трех-четырех, и порядок в ней важен: сужение алфавита ставится первым, потому что удешевляет все последующие.
• Чем закрывается остаток. Если после всех доступных механизмов остаются неоплаченные биты, система будет отдавать соседнюю страницу с той же уверенностью. Это допустимо ровно тогда, когда цена такой ошибки посчитана и принята.

Из закона сохранения следует, какие требования в протоколе имеют смысл, а какие нет. Требование «модель не должна выдумывать» не проверяемо и не исполнимо: механизм навигации не имеет состояния отказа. Проверяемы требования к источникам бит и к внешним проверкам.

Источник бит указан

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

Отказ реализован явно

Отказ — не свойство модели, а внешний механизм. В протоколе фиксируется условие отказа и его наблюдаемая доля, иначе система будет отвечать всегда.

Проверка отделена от генерации

Проверяющее звено не должно опираться на ту же меру, что и генерирующее: иначе оно подтверждает правдоподобие, а не верность.

Сложность обоснована объемом

Порядок модели, глубина сети или размер контекста подтверждаются замером на отложенной части. Часть V показывает, что превышение оправданной сложности ухудшает результат, и не проявляется на обучающей выборке.

Класс задачи назван

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

Аппарат бит удобен и потому опасен: он создает ощущение точности там, где величины оценены грубо. Перечень ниже — систематические ошибки, к которым такой счет располагает.

• Считать биты по равномерному распределению. Позиции справочника выбираются не равновероятно: на десяток ходовых SKU приходится большая часть обращений, и реальная величина ниже 15,6 бита.
• Складывать биты зависимых источников. Формула (3) аддитивна для независимых действий. Справочник и регламент, описывающие одно и то же, дают сумму меньше арифметической.
• Мерить энтропию на обучающей выборке. Величина получится сколь угодно малой и не будет означать ничего. Отложенная часть обязательна, и отрезать ее нужно хвостом.
• Переносить наш результат в 1,895 бита на чужой корпус. Величина измерена на технических текстах одной лаборатории; на другом материале она будет другой.
• Считать сжатие достижением само по себе. Оставшиеся 6 064 бита — это 10¹⁸²⁵ кандидатов. Сжатие в 10²⁹⁹¹ раз звучит внушительно и до страницы не доводит.
• Путать уверенность модели с вероятностью верности. Первая измеряется внутри пространства, вторая — снаружи. Связь между ними не гарантирована ничем.
• Считать невозможное дорогим. Перебор (глава 02) не станет доступен при росте бюджета; прогноз до наступления события не купить деньгами.
• Наращивать сложность модели вместо корпуса. Глава 22 показывает цену этой ошибки количественно: 938 бит адреса, потерянных при переходе с пятого порядка на восьмой.