Проблема «Троицы предсказаний»
В области искусственного интеллекта существует фундаментальное противоречие, которое автор называет «троицей предсказаний» (prediction trinity). Идеальный алгоритм должен обладать тремя свойствами одновременно:
- Мощность (Power): способность выявлять сложные паттерны реального мира.
- Эффективность (Efficiency): возможность работы на практике в разумное время.
- Формальные гарантии (Formal guarantees): математически доказанные пределы точности и ошибок.
Современные решения жертвуют одним из пунктов. Глубокое обучение (Deep Learning) эффективно и мощно, но лишено строгих гарантий. Индукция Соломонова (Solomonoff induction) дает идеальные гарантии, но вычислительно неразрешима. Новая работа Ohad A. (опубликованная в рамках fellowship PIBBSS 2026 под руководством Ванессы Косой) фокусируется на третьем углу: создание эффективных алгоритмов с доказуемыми гарантиями, но без «черного ящика» нейросетей.
Прямые программы (SLP) и сложность строк
Вместо перебора всех возможных компьютерных программ (что невозможно), исследователи используют Straight-Line Programs (SLP) — программы, состоящие только из присваивания символов и конкатенации строк. Сложность строки $C(x)$ определяется размером наименьшей SLP, генерирующей эту строку. Для повторяющихся структур, таких как слова Фибоначчи, $C(x)$ растет логарифмически от длины строки, что делает их идеальными кандидатами для такого типа предсказания.
От LZP к Run-Length BWT
Предыдущая работа Ванессы Косой представила алгоритм LZP (Lempel-Ziv Plurality), который предсказывает следующий символ, опираясь на контекст последней факторизации Лемпеля-Зива. Он имеет гарантию ошибок $O(C(x) ext{polylog}(n))$, но его узким местом была необходимость перестраивать индекс SA (Suffix Array) при каждом обновлении строки, что замедляло процесс.
Новый подход заменяет статический индекс на Run-Length Burrows-Wheeler Transform (RLBWT). Эта структура позволяет:
- Быстро искать вхождения подстрок через ранговые запросы (rank queries).
- Компрессировать данные: для повторяющихся строк RLBWT занимает место, пропорциональное сложности $C(x)$, а не длине строки $n$.
Сравнение производительности
Ключевое преимущество новой архитектуры — переход от статической к динамической обработке данных. Ниже приведено сравнение подходов:
| Характеристика | LZP (Косой, 2026) | Efficient LZP (Ohad A., 2026) |
|---|---|---|
| Базовая структура | SA (Suffix Array) | Run-Length BWT |
| Тип структуры | Статическая (перестраивается при обновлении) | Динамическая (адаптируется к потоку) |
| Сложность построения индекса | $O(n)$ или хуже при частых обновлениях | Полиномиальная от $C(x)$ |
| Гарантия ошибок | $O(C(x) ext{polylog}(n))$ | $O(C(x) ext{polylog}(n))$ |
| Применимость | Повторяющиеся последовательности | Повторяющиеся последовательности (оптимизировано) |
Почему это важно для AI
Эта работа демонстрирует, что можно достичь высокой эффективности и строгих математических гарантий, не полагаясь на эвристики глубокого обучения. Хотя алгоритм пока не способен к «общему интеллекту» уровня человека, он закладывает фундамент для compositional learning theory — теории, где структура гипотезы явна и интерпретируема. Это шаг к созданию AI-систем, которые не только предсказывают, но и объясняют свои выводы через явные структурные паттерны, а не через скрытые слои нейронных сетей.
Источник: LessWrong ↗