Поиск в пространстве состояний

Мы продолжаем серию постов про искусственный интеллект, написанных по мотивам выступления в «Технопарке» Mail.ru Константина Анисимовича — директора департамента разработки технологий ABBYY. Вторая статья будет посвящена алгоритмам поиска.


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

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

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

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

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

Поиск с помощью полного перебора

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

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

Поиск с итеративным углублением — это оптимизация поиска в глубину и в ширину, которая гарантированно позволяет найти самое близкое к начальному состоянию решение, избегая экспоненциальной сложности. Каким образом реализуется этот алгоритм? Мы ищем в глубину с ограничением глубины константой N. Нашли решение – хорошо. Не нашли — повторяем поиск в глубину с константой N+1 и так далее, пока не отыщется. Этот алгоритм, хотя и несложен в реализации, пригоден только для самых простейших задач.

Эвристический поиск

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

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

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

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

У лучевого поиска есть свои достоинства и недостатки. Основной его минус в том, что, в отличие от жадного, лучевой поиск не гарантирует нахождения конечного состояния с наилучшим качеством, потому что в процессе движения фронта лучшее состояние может из него выпасть. На практике с этим можно бороться, настраивая ширину фронта. Чем фронт уже, тем быстрее работает алгоритм, но тем чаще он ошибается. Чем шире фронт, тем алгоритм работает лучше, но дольше. Это одно из его важных преимуществ – возможность легко балансировать между скоростью и качеством. Лучевой поиск очень популярен в академической среде, особенно среди китайских ученых. Он прост в реализации и работает достаточно неплохо.

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

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

Недостатком алгоритма А* является необходимость придумать эвристику. Справедливости ради нужно сказать, что во многих задачах эта эвристика находится достаточно легко и естественно. В таких задачах и рекомендуется использовать А*. Если эвристику придумать не получается, тогда на помощь вам приходит лучевой поиск.

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