Эвристика

Материал из MachineLearning.

Статья написана с использованием LLM Qwen3.7 и проверена участником Камиль Багдалов

Эвристика (от греч. heuristicos — поисковый, способствующий поиску, восходит к heurisko — нахожу, открываю) — в широком смысле это метод решения задач, основанный на опыте, догадках, интуиции и приближённых рассуждениях, а не на строгом формальном алгоритме, гарантирующем нахождение точного и оптимального решения. В контексте искусственного интеллекта и машинного обучения эвристика представляет собой правило, функцию или стратегию, позволяющую отсечь заведомо бесперспективные ветви поиска, сузить пространство решений или найти достаточно хорошее приближение за приемлемое время, тем самым преодолевая проблему комбинаторного взрыва.

Исторический контекст и философия ограниченной рациональности

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

Аллен Ньюэлл и Герберт Саймон выдвинули гипотезу, что человеческое мышление при решении нетривиальных задач опирается не на перебор, а на эвристики. В своей программе General Problem Solver (GPS) они заложили основы эвристического поиска, опираясь на концепцию «ограниченной рациональности» (bounded rationality), разработанную Саймоном. Согласно этой концепции, интеллект — это не способность находить абсолютно оптимальное решение (что требует неограниченных вычислительных ресурсов), а способность находать удовлетворительное решение (satisficing) в условиях жестких ограничений по времени и памяти. Эвристики стали тем мостом, который позволил ранним системам ИИ имитировать человеческий подход, используя правила «большого пальца» (rules of thumb) для приоритизации направлений поиска.

Математический и алгоритмический аппарат

В теории алгоритмов и исследовании операций эвристика формализуется как оценочная функция , которая сопоставляет каждому узлу в графе состояний числовую оценку близости к цели.

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

1. Допустимость (admissibility): Эвристика никогда не завышает реальную стоимость достижения цели. Формально: , где — истинная минимальная стоимость.
2. Монотонность (consistency): Оценка эвристики удовлетворяет неравенству треугольника. Формально: , где — стоимость перехода из узла в . Монотонная эвристика гарантирует, что алгоритм не будет раскрывать один и тот же узел повторно.

Если требование оптимальности не является строгим, используются недопустимые эвристики (например, взвешивание на коэффициент , как в алгоритме WA*). Это приводит к потере гарантии оптимальности, но позволяет найти решение значительно быстрее, жертвуя точностью ради скорости (trade-off между optimalitу и efficiency).

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

Классификация эвристик

В современной литературе эвристики принято делить на несколько категорий в зависимости от природы пространства поиска и решаемой задачи:

1. Эвристики поиска (Search heuristics). Функции оценки, определяющие приоритет раскрытия узлов в графе состояний. Примеры: расстояние по Манхэттену или Евклиду для задач поиска пути на сетке, эвристика числа неверно расставленных фишек в задаче «15 головоломка».
2. Метаэвристики (Metaheuristics). Высокоуровневые стратегии, которые не гарантируют глобальный оптимум, но позволяют эффективно исследовать огромные пространства параметров. Сюда относятся имитация отжига (simulated annealing), поиск с запретами (Tabu search), методы роя частиц и генетические алгоритмы. Они часто используют элементы случайности для выхода из локальных оптимумов.
3. Жадные эвристики (Greedy heuristics). Алгоритмы, делающие локально оптимальный выбор на каждом шаге в надежде на глобальный оптимум. Жадные эвристики часто используются как базовый уровень (baseline) в машинном обучении и исследовании операций (например, жадный алгоритм для задачи о покрытии множества).
4. Предметно-ориентированные vs Предметно-независимые эвристики. Первые используют специфические знания о конкретной задаче (например, правила шахматного дебюта), вторые универсальны и применимы к широкому классу задач (например, случайный поиск или общие метаэвристики).

Эвристики в современном машинном обучении

Хотя современный ИИ сместился от символьных систем к статистическим и нейросетевым моделям, эвристики не исчезли — они трансформировались и стали неотъемлемой частью конвейеров машинного обучения:

• Ансамбли моделей и градиентный бустинг. Алгоритмы градиентного бустинга (XGBoost, CatBoost, LightGBM) строятся по принципу жадной эвристики. На каждом шаге к ансамблю добавляется новый базовый алгоритм (обычно дерево решений), который аппроксимирует антиградиент функции потерь. Это локально жадная стратегия оптимизации в пространстве функций, которая на практике показывает выдающиеся результаты на табличных данных.
• Игровой ИИ и MCTS. В алгоритме MCTS (Monte Carlo Tree Search), лежащем в основе систем уровня AlphaGo и AlphaZero, эвристики используются для баланса между исследованием новых веток дерева и эксплуатацией уже найденных перспективных ходов. Классическая эвристика UCB1 (Upper Confidence Bound) задаёт формулу выбора узла: , где первое слагаемое отвечает за эксплуатацию (средний выигрыш), а второе — за исследование (штраф за недостаток посещений узла).
• Поиск нейросетевых архитектур (NAS). При автоматическом проектировании нейронных сетей (Neural Architecture Search) пространство возможных архитектур дискретно и колоссально. Для его поиска применяются эвристики, такие как эволюционные алгоритмы или обучение с подкреплением, которые «угадывают» удачные блоки (свертки, skip-connections), экономя тысячи часов вычислений по сравнению со случайным поиском.
• Эвристики отбора признаков и инициализации. Правила для быстрого отсева неинформативных переменных до применения сложных моделей (фильтрация по дисперсии, взаимной информации). Также эвристические правила применяются для выбора начальных весов нейронных сетей или аугментации данных, что значительно ускоряет сходимость градиентного спуска.

Эвристики в теории вычислительной сложности

В теории сложности эвристики играют ключевую роль при решении NP-трудных задач, для которых не существует полиномиальных точных алгоритмов (при условии ). Эвристические алгоритмы (аппроксимационные алгоритмы) позволяют находить решения, близкие к оптимальным, за полиномиальное время. Например, жадная эвристика для задачи коммивояжера (метод ближайшего соседа) или 2-аппроксимационный алгоритм для задачи о вершинном покрытии. Изучение границ применимости таких эвристик (например, PCP-теорема и невозможность аппроксимации) является одним из центральных направлений современной теоретической информатики.

Философский и эпистемологический аспект

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

Эвристика кодирует в себе неявное знание (tacit knowledge) о структуре конкретной задачи, которое трудно выразить в виде строгих аксиом. В философии ИИ это перекликается с дискуссией о том, может ли машина обладать подлинным пониманием, или она лишь искусно манипулирует эвристиками. Переход от жестких, закодированных разработчиком правил (символьный ИИ) к обучаемым эвристикам (глубокое обучение) показывает смену парадигмы: современные нейросети не используют явные эвристики для поиска, а *выучивают* собственные, скрытые в весах связей, эвристические представления (distributed representations) прямо из данных. Таким образом, интеллект можно рассматривать как способность вырабатывать эффективные эвристики для выживания и решения задач в неидеальной, зашумленной среде.

См. также

• Искусственный интеллект
• Дартмутский семинар
• Метод ветвей и границ
• Алгоритм A*
• Жадный алгоритм
• Монте-Карло поиск по дереву
• Генетический алгоритм
• Метаэвристика
• NP-трудная задача

Источники

• Newell A., Simon H.A. GPS, A Program That Simulates Human Thought // Proc. of the Int. Congress on Cybernetics. 1959.
• Simon H.A. Models of Bounded Rationality: Empirically Grounded Economic Reason. MIT Press, 1982.
• Russell S., Norvig P. Artificial Intelligence: A Modern Approach. 4th ed. Pearson, 2020.
• Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984.
• Browne C. B. et al. A Survey of Monte Carlo Tree Search Methods // IEEE Transactions on Computational Intelligence and AI in Games. 2012.
• Vazirani V.V. Approximation Algorithms. Springer, 2001.