2. Эвристики

В литературе по искусственному интеллекту часто встречается слово эвристика. Поясним его смысл. Краткий оксфордский словарь английского языка толкует это слово следующим образом: "Эвристика - искусство нахождения истины. В частности, применяется для характеристики системы образования, при которой ученика обучают самостоятельно находить объяснение явлений".

Когда-то эвристиками пренебрежительно называли медиков, которые приобрели свои знания на опыте, а не в процессе обучения в специальном медицинском учебном заведении.

Слово "эвристика" (heuristic) имеет те же истоки в древнегреческом языке, как и "эврика" (Eureka). Существуют разногласия относительно верного произношения последнего, и возможно, что известное восклицание Архимеда "Эврика!" ("Я нашел!") следует на самом деле писать не "Eureka!", а "Неureka!".

В литературе по искусственному интеллекту понятию эвристика придается более конкретный смысл - оно противопоставляется понятию алгоритм, который мы и рассмотрим в первую очередь.

Алгоритмы

Алгоритм - это набор инструкций или четко сформулированных операций, составляющих определенную процедуру. Обычное умножение или деление представляют собой алгоритмы; при условии, что входные данные, для которых предназначены эти алгоритмы, находятся в требуемой форме (десятичные числа - для привычных вариантов таких алгоритмов), они всегда приводят к нужному результату. Алгоритмы используются не только в арифметике. Алгебраические преобразования также определяются четко очерченными наборами правил. Например, решение какой-то системы уравнений с числовыми коэффициентами можно производить алгоритмически, как и дифференцирование алгебраического выражения по некоторой переменной (допустим, х), которая в нем встречается. Алгоритмы всегда могут быть реализованы в виде программ для вычислительной машины, если только при этом не возникает каких-либо трудностей количественного характера, скажем таких, как недостаточный объем памяти машины.

На первых этапах изучения математики человек в значительной степени связан с алгоритмическими операциями. Однако с самого начала предполагается, что он усваивает определенные, существенно неалгоритмические знания, поскольку умение выполнять алгоритмические процедуры само по себе не представляет ценности: важно умение применять их к конкретным задачам. Однако то, что мы могли бы назвать "ядром начального математического образования", носит существенно алгоритмический характер.

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

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

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

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

Однако это различие между эвристиками и алгоритмами следует рассматривать с определенной осторожностью. Существуют такие проблемные области - и область доказательств теорем служит тому примером, - где нельзя найти метод, который всегда приводил бы к успеху. В некотором смысле кажущаяся слабость эвристических методов скрыта часто не в них, а в самой проблемной области.

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

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

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

Чтобы ближе познакомиться с некоторыми аспектами эвристического программирования, необходимо различать два типа задач, а именно: задачи, хорошо определенные и плохо определенные.

Хорошо определенные и плохо определенные задачи

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

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

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

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

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

Сложность, конечно, состоит в том, что для нетривиальных задач при любом методе, использующем полный просмотр, решение становится нереальным вследствие слишком большого размера пространства решений. Выражение комбинаторный взрыв относится к такой ситуации, когда размер этого пространства возрастает чрезвычайно быстро с ростом числа элементарных решений, необходимых для выделения каждой из возможностей. Если бы каждое решение было двоичным, то число возможностей равнялось бы 2ⁿ, где n - число решений. Какое-то ощущение скорости роста здесь можно получить, если учесть, что n должно лежать где-то в пределах 20, чтобы число возможностей было равно населению Великобритании, и несколько превышать этот интервал, чтобы число возможностей соответствовало уже населению США или СССР. Число способов пробивки обычной перфокарты (12 строк, 80 колонок) равно 2⁹⁶⁰, что превышает число частиц во Вселенной (согласно оценке Эддингтона) в кубе (в случае, если нет никаких ограничений на конфигурацию пробивок отверстий в карте). Число возможных способов представления буквенно-цифровых данных, согласно существующим стандартам, соответствует примерно квадратному корню из числа Эддингтона.

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

Эвристика (эвристическое правило, эвристический метод) представляет собой некоторое произвольное правило, стратегию, хитрость, упрощение или любое другое средство, которое решительным образом ограничивает объем поиска решений в крупных проблемных пространствах [точнее, пространствах решений].

Вследствие комбинаторного взрыва задачи могут быть решены лишь при условии весьма существенного ограничения объема поиска, обычно до такой степени и таким образом, что он вообще перестает выглядеть как процесс поиска.

Примеры эвристик

Таким образом, эвристики представляют собой правила, руководствуясь которыми интеллектуальная система движется к цели. Многие пословицы можно считать эвристиками, своего рода "руководствами" в повседневной жизни:

Правду погубишь и сам пропадешь. 
Бережливость дороже богатства.

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

Некоторые эвристические правила, которые использовались или по крайней мере предлагались для использования, можно рассматривать как "административные методы". Необходимость в правильном "администрировании" в процессе решения задачи возникает в тех случаях, когда в нашем распоряжении имеется несколько методов решения. Это "администрирование" должно быть таким, чтобы метод, являющийся (по некоторому эвристическому критерию) наиболее обещающим, использовался в первую очередь; однако при этом допускается использование лишь определенного числа этапов вычислений, после чего проверяется одна из возможных альтернатив. Естественно также, чтобы человек, который осуществляет общее руководство, был в состоянии обнаруживать замкнутые цепочки дедукций, с тем чтобы прерывать их, и т. д. Термин "администрирование" говорит о иерархической структуре системы решения задач, которая в вычислительных системах, пожалуй, лучше всего обеспечивается специальными аппаратными средствами. (Современные вычислительные машины коллективного пользования обладают "встроенным администрированием" определенного сорта, поскольку программы находятся под контролем операционной системы. Последняя определяет порядок работы программ пользователей, ограничивает при необходимости время их работы, распределяет физические ресурсы вычислительной машины, ведет учет машинного времени, которое должно быть оплачено пользователями.)

Минский [1] указал на следующие (по существу, административные) характеристики эвристических программ:

а. Методы, в которых новые проблемы рассматриваются как подцели.

б. Методы, в которых новые проблемы рассматриваются как модели.

в. Методы характеризации или описания (см. ниже обсуждение основной эвристики обучения).

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

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

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

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

Как мы увидим в дальнейшем, имеется большой набор эвристик, которые удобнее всего объяснить в связи с игровыми программами. Важный эвристический принцип анализ цели - средства и его использование в универсальном решателе задач будут описаны в следующей главе. Прежде чем закончить этот беглый обзор эвристик, уделим некоторое внимание основной эвристике обучения Минского и Селфриджа [2].

Основная эвристика обучения на первый взгляд кажется настолько очевидной, что, пожалуй, о ней не стоило бы и говорить. Она формулируется так: "В новой ситуации попытайся использовать методы, подобные тем, которые лучше всего работали в аналогичных уже известных ситуациях".

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

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

Мысль о необходимости определенной меры сходства задач для применения основной эвристики обучения обсуждалась также Минским [3] под названием эвристической связи задач. Как будет показано в заключительных главах, эта идея весьма важна и ведет к глубоким выводам относительно природы интеллекта.

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