Кратко — пересечение заключается в том, что теория информации даёт количественные меры (энтропия, взаимная информация, сжимаемость), а теория вычислимости и сложности даёт формальные границы представимости и затрат (классы формальных грамматик, разрешимость и сложность задач). Вместе они определяют, что принципиально и что практически достижимо в NLP, и какие компромиссы нужно делать.
Ключевые идеи (с формулами):
- Энтропия и предсказуемость:
- Энтропия источника текста $H(X)=-\sum _{x}p(x)\log p(x)$ задаёт нижнюю границу на среднюю длину кода и на среднюю кросс‑энтропию модели.
- Кросс‑энтропия и разница с истинной энтропией:
$H(p,q)=-\sum _{x}p(x)\log q(x)=H(p)+D_{KL}(p\Vert q)$.
- Перплексити связана с энтропией: $\text{Perplexity}=2^H$ (при логарифме по основанию 2). Это даёт теоретический предел качества языковой модели.
- Алгоритмическая сложность и сжимаемость:
- Колмогоровская сложность $K(x)$ — минимальная длина программы, генерирующей $x$. $K(x)$ невычислима, но приближается средствами сжатия (MDL).
- MDL/сжатие: выбирать модель минимизирующую суммарную длину описания $L(M)+L(D\mid M)$.
- Формальные языки и автоматы:
- Иерархия (регулярные ⊂ контекстно‑свободные ⊂ контекстно‑чувствительные …) задаёт, какие синтаксические зависимости устроены формально; конечные автоматы описывают регулярные языки, стековые автоматы — КС‑языки.
- Практические сложности: проверка принадлежности
\displaystyle для конечных автоматов — $O(n)$, для КС‑грамматик (CYK/Earley) — $O(n^3)$ в худшем случае; для более сильных классов задачи могут быть PSPACE‑complete или неразрешимы.
- Информационно‑вычислительные ограничения:
- Длинно‑дистанционные зависимости требуют моделей с большой памятью (взаимная информация между отстоящими позициями убывает, но не всегда быстро).
- Ограниченные автоматы (конечные) не могут формально выразить центр‑вложенность (pumping lemma), но стохастические/нейронные модели могут аппроксимировать многие такие явления при конечных ресурсах.
Практические последствия для разработки NLP‑систем:
1. Выбор формализма под задачу:
- Для морфологии/лемматизации и многих задач последовательностей часто достаточно конечных автоматов или WFST (эффективны и детерминируемы).
- Для синтаксического разбора нужны КС‑грамматики или статистические/нейросетевые парсеры; для сложных семантических зависимостей — более мощные модели (с ростом вычислительности растёт стоимость).
2. Оценка и целевые метрики:
- Кросс‑энтропия / перплексити имеют строгую информационную интерпретацию: нижняя граница задана истинной энтропией корпуса. Нельзя ожидать, что модель превзойдёт эту границу.
- Используйте компрессию и MDL для выбора архитектуры и регуляризации.
3. Компромисс между выразительностью и трактабельностью:
- Более выразительные формализм/модели дают лучшую нарушаемость языка, но приводят к дорогой или неустойчивой инференции. Практически применяют приближённые/эмпирические методы (сконструированные грамматики, обучение с аппроксимацией, нейросети).
4. Ограничения данных и вычислений:
- Энтропия языка и взаимная информация определяют объём данных, необходимый для обучения: высокая энтропия и редкие явления требуют больше примеров/приорной информации.
- Практика: предобучение на больших корпусах и сильные архитектурные приёмы (attention, трансформеры) уменьшают выборочную сложность, но требуют больших ресурсов.
5. Невычислимые/непроверяемые цели и аппроксимации:
- Колмогоровская сложность недоступна; используйте компрессоры/сжатие, регуляризацию, байесовские априори как приближения к оптимальному описанию.
- Для формальных доказательств свойств языка приходится ограничивать класс моделей (чтобы сохранить разрешимость и контролируемую сложность).
Короткие практические рекомендации:
- Для задач с жёсткими временными/памятными ограничениями выбирайте конечные автоматы/WFST; для синтаксиса — КС‑парсеры или нейросети с контролируемой сложностью.
- Оценивайте модели через кросс‑энтропию/перплексити и контролируйте переобучение через MDL/регуляризацию.
- Применяйте приближённые алгоритмы и эвристики там, где точные алгоритмы вычислительно неосуществимы.
- Используйте предобучение и априори (transfer learning), чтобы снизить требуемый объём данных при высокой энтропии задач.
Это сочетание теории информации и вычислимости задаёт реальные границы: что можно сжать/предсказать и что можно эффективно распознать/проанализировать; инженерная задача — подобрать модели и эвристики, которые на практике оптимально балансируют эти ограничения.