В лекции Стэнфордского университета по курсу CS221 рассматривается фундаментальная концепция поиска как формы логического мышления в детерминированном мире. Лектор объясняет, почему в эпоху доминирования глубокого обучения классический поиск не только сохраняет актуальность, но и становится ключевым элементом современных ИИ-систем благодаря синергии с обучением. В материале подробно разбираются как точные методы (исчерпывающий поиск и динамическое программирование), так и приближенные подходы (алгоритм Best-of-N и лучевой поиск), включая их применение для масштабирования вычислений на этапе тестирования языковых моделей.
🧠 От рефлексов к рассуждениям: почему поиск важен в эпоху ИИ 0:05
Современное машинное обучение во многом опирается на рефлекторные механизмы, преобразующие входные данные в выходные. В задачах регрессии результатом становится число, а в задачах классификации — одна из заданных категорий. Даже глубокие нейронные сети по своей сути представляют собой модели прямого распространения, которые работают быстро и реактивно, выполняя прямое отображение восприятия на действие. Однако многие реальные вызовы — от сложных математических задач до программирования — требуют полноценного логического мышления, планирования и решения проблем. Поиск выступает ключевой формой такого мышления в условиях, когда окружающий мир детерминирован.
В 2025 году может возникнуть резонный вопрос: зачем возвращаться к концепциям символического ИИ 1950-х годов, если они когда-то не оправдали надежд? Ответ кроется в знаменитом эссе Ричарда Саттона «Горький урок» (The Bitter Lesson). По мнению Саттона, общие методы, эффективно использующие вычисления, в конечном счете оказываются наиболее успешными с огромным отрывом. Саттон утверждает, что лишь два метода способны масштабироваться произвольно за счет роста вычислительных мощностей: поиск и обучение. Современный ИИ научился отлично справляться с обучением, но объединение мощных моделей с алгоритмами поиска открывает принципиально новые возможности для решения сложнейших задач.
🛠️ Формализация задачи поиска: анатомия абстракции 5:15
Чтобы алгоритмы могли оперировать абстрактными концепциями, естественное описание проблемы необходимо перевести в строгий программный код. В качестве базового примера лектор предлагает задачу перемещения по улице с блоками от 1 до $n$. Пеший переход между соседними блоками занимает 1 минуту, а поездка на воображаемом трамвае удваивает текущий номер блока и длится 2 минуты. Цель — найти маршрут с минимальными временными затратами.
Стандартная математическая формализация задачи поиска включает в себя фиксированный набор компонентов:
- Начальное состояние (start state), определяющее отправную точку системы.
- Функция преемников (successors), возвращающая список возможных шагов. Каждый шаг состоит из метки действия, стоимости (времени) и результирующего следующего состояния.
- Функция завершения (is end), проверяющая, достигнута ли конечная цель поиска.
По мере усложнения условий — например, при введении лимита на количество билетов для трамвая — структура состояния усложняется. Состояние перестает быть простым числом и становится композитным объектом, хранящим текущую локацию и остаток билетов. Как подчеркивает преподаватель, состояние должно содержать строго ту информацию, которая необходима для корректной оценки будущих действий, затрат и преемников. Включение избыточных данных, таких как вся история перемещений, чревато экспоненциальным ростом пространства состояний, что сделает алгоритмы оптимизации крайне медленными.
🔍 Точные методы: исчерпывающий поиск и его ограничения 20:37
Основная цель любого алгоритма поиска — найти последовательность действий, минимизирующую общую стоимость. Простейший подход заключается в исчерпывающем (полном) переборе всех возможных вариантов. Для перехода к более сложным концепциям лектор вводит понятие «будущей стоимости» (future cost) — функции, определяющей минимальные затраты на путь от текущего состояния до финала. Расчет базируется на рекуррентном соотношении: будущая стоимость текущего узла равна минимуму из сумм немедленной стоимости действия и будущей стоимости следующего узла.
Несмотря на концептуальную простоту, исчерпывающий поиск имеет серьезные недостатки:
- Временная сложность в худшем случае растет экспоненциально, что делает его неприменимым для длинных маршрутов.
- Память расходуется линейно относительно длины решения, поскольку стек рекурсии хранит лишь текущий путь.
- Наличие циклов в графе состояний приводит к бесконечному зацикливанию алгоритма.
Для предотвращения бесконечных циклов разработчики используют специальные инженерные приемы. Лектор предлагает интегрировать счетчик шагов непосредственно в состояние, что заставляет систему двигаться исключительно вперед во времени. При превышении заданного порога шагов функция завершения объявляет состояние конечным, а система присваивает ему бесконечную стоимость, исключая неэффективный путь из итогового выбора.
💾 Динамическое программирование: исчерпывающий поиск плюс кэширование 38:24
Для кардинального повышения эффективности перебора применяется динамическое программирование — метод, предложенный Ричардом Беллманом в 1950-х годах. Под термином «динамическое» понимается процесс принятия последовательных решений во времени, а под «программированием» — математическая оптимизация. В контексте алгоритмов лектор формулирует этот подход максимально просто: исчерпывающий поиск плюс кэширование (или мемоизация).
Интеграция кэша в стандартный алгоритм перебора требует минимальных изменений в коде:
- Инициализируется структура данных для хранения уже вычисленных решений для каждого состояния.
- В начале рекурсивной функции добавляется проверка: если состояние уже есть в кэше, алгоритм мгновенно возвращает готовый ответ.
- После нахождения оптимального пути для нового состояния результат записывается в кэш перед возвратом.
Динамическое программирование обеспечивает экспоненциальное ускорение, снижая временную сложность до линейной или квадратичной. Однако лектор напоминает важное правило компьютерной жизни: память часто оказывается более дефицитным ресурсом, чем время. Кэширование требует сохранения всех уникальных состояний, и если их количество исчисляется триллионами, алгоритм исчерпает доступную оперативную память. Кроме того, мемоизация эффективна только тогда, когда в графе существует множество альтернативных путей, ведущих в одни и те же узлы (решетчатая структура). Если каждый путь уникален (древовидная структура), кэш будет постоянно фиксировать промахи, лишая алгоритм преимуществ.
🎲 Приближенный поиск: алгоритмы Best-of-N и лучевой поиск 50:51
Когда пространство состояний становится бесконечным или слишком огромным (например, при генерации текстовых последовательностей), точный поиск становится невозможным. В таких сценариях инженеры жертвуют гарантиями идеального результата в пользу эвристических методов приближенного поиска. Лектор детально разбирает два популярных алгоритма: Best-of-N и лучевой поиск (Beam Search).
Метод Best-of-N устроен предельно просто: система совершает $N$ независимых случайных запусков (роллаутов) от старта до финиша, руководствуясь заданной стратегией (политикой), после чего выбирает вариант с наименьшей стоимостью. Под политикой понимается функция, отображающая состояние на доступное действие. При росте $N$ до бесконечности алгоритм гарантированно сходится к точному оптимуму. Огромным преимуществом Best-of-N является его идеальная параллелизуемость (embarrassingly parallel): вычисления можно распределить по тысячам изолированных машин, не требуя от них коммуникации друг с другом в процессе работы.
Лучевой поиск предлагает другую стратегию и работает по строго детерминированному принципу. Алгоритм вводит фиксированный параметр — ширину луча (beam width). Процесс развивается пошагово:
- Из текущих промежуточных траекторий генерируются все возможные продолжения.
- Для каждого нового варианта рассчитывается его суммарная стоимость.
- Все кандидаты сортируются, и алгоритм оставляет строго заданное количество лучших путей (равное ширине луча), безжалостно отсекая остальные.
Если ширина луча равна единице, алгоритм превращается в обычный жадный поиск. Если же ширину устремить к бесконечности, лучевой поиск трансформируется в исчерпывающий перебор. Оптимальным значением для текстовых задач в современных системах лектор называет порядок 10 кандидатов.
🤖 Поиск в языковых моделях: вычисления на этапе тестирования 1:11:37
Применение классического поиска к современным большим языковым моделям породило концепцию вычислений на этапе тестирования (test-time compute), ставшую широко известной благодаря линейке моделей OpenAI o1. С точки зрения математики, большая языковая модель представляет собой сложный многоклассовый вероятностный классификатор, принимающий на вход подсказку (промпт) и выдающий распределение вероятностей для следующего токена.
Чтобы превратить генерацию текста в строгую задачу поиска, лектор описывает следующую схему трансформации:
- Состояние: строка, объединяющая исходный промпт и уже сгенерированный к настоящему моменту префикс ответа.
- Действие: предсказание конкретного следующего токена.
- Стоимость действия: отрицательное логарифмическое правдоподобие (negative log probability) токена, что эквивалентно максимизации его вероятности.
- Проверка качества: интеграция внешнего верификатора, который начисляет огромный бонус (срезает 100 единиц стоимости) в случае успешного решения математического или программного условия.
В качестве демонстрации преподаватель приводит пример локального запуска сверхмалой модели Qwen-3 с 0,6 млрд параметров на обычном ноутбуке. Модели предлагается решить арифметическое выражение 3 + 7 * 2. Используя метод Best-of-N, система генерирует независимые цепочки токенов, отбирая те, которые формируют математически корректный ответ. Исследования подтверждают, что интенсивное использование вычислений на этапе генерации позволяет компактным моделям успешно конкурировать по качеству результатов с гораздо более массивными нейросетями. Сочетание глубокого обучения, задающего базовые стоимости, и алгоритмов поиска, находящих глобально оптимальные траектории, лектор называет главным вектором развития устойчивых систем искусственного интеллекта.
