Сайт о роботах

История создания искусственного интеллекта


Статья об искусственном интеллекте
Навигация
Самые интересные статьи
В Англии создали бионического человека

Полностью бионического человека удалось создать в Англии группе ученых под руководством Бертольда Майера. Робот имеет человекоподобное лицо и глаза способные с помощью...

Обратите внимание Будьте в курсе событий.

История создания искусственного интеллекта


07.04.2007, 13:21

В статье рассматривется история создания програм и алгоритмов ИР.

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

Дуглас Б. Ленат

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

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

Уже на протяжении около 30 лет относительно немногочисленная группа исследователей пытается иногда более, иногда менее успешно создавать программы, позволяющие ЭВМ "разумно" решать задачи. В середине 70-х годов после двух десятилетий медленного и едва заметного прогресса в этой новой области искусственного интеллекта исследователи пришли к следующему фундаментальному выводу о разумном поведении вообще: оно требует колоссального количества знаний, которыми люди обладают, как чем-то само собой разумеющимся, но которые нужно постепенно "скормить" машине. Оказавшись перед перекрестком в штате Небраска, путешественник вспомнит о том, что Сан-Франциско лежит к западу от штата Небраска, что вечером солнце заходит на западе и что, двигаясь в направлении заходящего солнца, он будет на правильном пути. Таким образом, ему не нужно будет проверять, куда ведут две другие дороги.

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

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

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

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

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

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

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

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

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

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

Рассмотрим программу MYCIN, разработанную Э. Шортлиффом в Станфордском университете для диагностирования бектериальных инфекций в крови. Проблема, решаемая этой системой, состоит в том, чтобы определить, который из возможных микроорганизмов вызвал данное заболевание, и рекомендовать курс лечения на основе поставленного диагноза. При этом система MYCIN располагает базой знаний, состоящей из 500 эвристических правил. Вот некоторые типичные примеры: "Если (1) окраска организма грамположительна и (2) морфология организма соответствует кокку, а также если (3) организм растет в сгустках, то имеются основания полагать (0,7), что этот организм является стафилококком".

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

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

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

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

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

Формальные методы, даже если ими нельзя воспользоваться как основным средством рассуждения, могут сыграть полезную роль в управлении экспертными системами. В некоторых системах, например, при решении таких вопросов, как, оправданы ли затраты на дальнейший поиск, применяются логические или статистические процедуры. Более того, поскольку в экспертных системах эвристические правила типа "если - то", вообще говоря, не выражают отношений, которые всегда истинны, с каждым правилом может быть ассоциирована величина, характеризующая степень уверенности в справедливости этого правила ("0,7" - в примере, приведенном выше при описании системы MYCIN). Эти оценки, присоединяющиеся на каждом шаге последовательности заключений, объединяются, чтобы охарактеризовать достоверность окончательного решения. Это делается с использованием формулы Байеса или какой-нибудь другой формальной процедуры из теории вероятностей.

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

Одна из наиболее успешных программ, обладающих свойствами искусственного интеллекта, оказалась также исторически первой экспертной системой. Это программа DENDRAL, созданная Э. Фейгенбаумом и его коллегами в Станфордском университете в конце 60-х годов. Как и ее последователь, система GENOA, она широко используется в органико - химических лабораториях многих стран. Система DENDRAL, устанавливает структуру органических молекул, основываясь на данных масс - спектрометрии, ядерного магнитного резонанса и других видов информации. Как и MYCIN, система DENDRAL по существу является диагностической.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В последнее время в кругах специалистов по искусственному интеллекту все чаще приходится слышать слово "параллелизм". Оно обозначает еще один потенциальный источник эффективности для систем искусственного интеллекта. В настоящее время большинство ЭВМ обрабатывает информацию последовательно, одна операция следует за другой. Однако некоторые группы специалистов по вычислительной технике, включая тех, которые работают в Японии над созданием "ЭВМ пятого поколения" и в США над "стратегическим проектом по вычислительной технике", разрабатывают сейчас машины, состоящие из порядка миллиона процессоров, действующих "в параллель", т.е. одновременно. Перспектива увеличения скорости обработки информации в миллион раз настолько вдохновила некоторых исследователей, что они пророчат революционные изменения в программном обеспечении систем искусственного интеллекта.

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

Есть и еще одно основание, чтобы не верить в параллельную обработку информации как в панацею. Оно несколько более тонкого характера и основано на эмпирическом опыте, полученном автором и его коллегами. Когда EURISKO моделировала работу постепенно возрастающего числа процессоров, работающих одновременно над задачами, поставленными перед системой, выяснилось, что производительность программы в порождении интересных концепций была максимальной, когда моделировалась параллельная работа четырех процессоров; при дальнейшем увеличении числа процессоров роста производительности не наблюдалось. Объяснение этого явления заключается в том, что в ходе работы над первоочередной задачей в своем списке EURISKO обычно наталкивалась на другую задачу, которую она считала более интересной, чем все оставшиеся задачи в списке. Там, где хорошие эвристики позволяют реализовать поиск по правилу "сначала наилучший вариант", эффект параллельной обработки может оказаться не столь значительным.

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

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

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

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

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

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

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

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

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

Приложения

"РАЗУМНАЯ" ПРОГРАММА

"РАЗУМНАЯ" ПРОГРАММА выполняется на машине, демонстрирующей в нескольких "окнах" дисплея различные аспекты совершаемых программой действий. Программа EURISKO, написанная автором и его коллегами, работала в различных областях, включая те, которые перечислены в маленьком окошке в нижней части дисплея. В данном случае система занята подбором эскадры кораблей, чтобы соревноваться в военной игре "Трэвеллер". База знаний программы содержит сложные правила игры, а также эвристики общего характера, направляющие программу на поиск оптимального состава эскадры. Программа только что закончила моделирование сражения, в котором "сторона 1" одержала решительную победу над "стороной 2", и, проанализировав различия между эскадрами, обеспечившие победу "стороне 1", текущая эвристика указала на то, что нужно извлечь полезный опыт из результатов сражения. Поскольку главное различие состояло в том, что у "стороны 1" лишь один тип кораблей, EURISKO выдвигает гипотезу, что желательно свести к минимуму число типов кораблей, и предлагает провести эксперимент, позволяющий проверить эту гипотезу. В соревнованиях с людьми эскадра EURISKO, состоящая главным образом из маленьких быстрых кораблей, вышла победителем.

МЕТОД РЕЗОЛЮЦИИ

МЕТОД РЕЗОЛЮЦИИ - один из методов доказательства, используемый в формальной логике. Его можно применять при построении ответов на вопросы, однако он требует слишком много машинного времени, когда задача сложна. Метод по существу представляет собой "доказательство от противного". Справедливость гипотезы устанавливается доказательством того, что ее отрицание, сопоставленное с аксиомами, или заведомо справедливыми утверждениями, приводит к противоречию. Сначала отрицание гипотезы и аксиомы представляется в рамках логического формализма, т.е. как предложения, являющиеся дизъюнкциями литеров. Затем в множестве аксиом отыскивается аксиома, содержащая такой литерал, который после соответствующих подстановок значений переменных входит в противоречие с каким-либо литералом в отрицании гипотезы. Когда к двум предложениям применяется резолюция, противоречащие друг другу литералы взаимно уничтожаются. Затем та же процедура применяется уже к результирующему предложению и т.д. В конце концов, если исходная гипотеза была справедливой, этот процесс приводит к явному противоречию. В качестве примера здесь рассмотрена гипотеза "Марк ненавидит Цезаря". В идеализированном случае, когда фактов, известных о "мире", очень мало (слева), только одна аксиома (5) содержит литерал, противоречащий отрицание гипотезы, и программа быстро завершает доказательство. Когда информации становится больше (аксиомы, выделенные цветом) и появляется еще одна причина для ненависти (8), программа может выбрать не ту аксиому и продолжать процесс, пока не зайдет в тупик, так и не придя к противоречию (справа). В реальных задачах количество возможных вариантов выбора является экспоненциальной функцией от числа аксиом, последнее же обычно очень велико. Поэтому отыскать решение в процессе "слепого" поиска практически невозможно. Рассмотренный здесь пример придуман Е. Рич.

ЭКСПЕРТНАЯ СИСТЕМА

ЭКСПЕРТНАЯ СИСТЕМА пользуется знаниями, которыми она обладает в своей узкой области, чтобы ограничить поиск на пути к решению задачи. DENDRAL, первая и наиболее успешная экспертная система, основана на синергетическом взаимодействии четырех типов знаний, позволяющем сузить круг возможных структур исследуемой органической молекулы. Если известна лишь молекулярная формула C20H43N, то математически возможны 43 миллиона конфигураций атомов. Однако знание основ химической топологии, например того, что валентность атома углерода равна четырем, сужает круг структур - кандидатов до 15 миллионов. Данные о молекуле, полученные при помощи масс - спектрометра, а также эвристические знания о том, какие структуры наиболее стабильны и, стало быть, наиболее вероятны, еще больше ограничивают поиск. Наконец, данные по ядерномагнитному резонансу позволяют программе DENDRAL правильно идентифицировать структуру молекулы.

ДОСКА ДЛЯ ЗАПИСЕЙ

ДОСКА ДЛЯ ЗАПИСЕЙ позволяет организовать большое количество знаний, которыми располагает "разумная" программа. Информация хранится в независимых модулях, каждый из которых "наблюдает" лишь за небольшой областью на доске и активируется только тогда, когда другие модули отправляют туда какие-либо данные. Модульная структура помогает решить проблему, возникающую каждый раз при выборе компоненты базы знаний, которую следует применить в данный момент. Рассматриваемый пример взят из системы распознавания речи, разработанной Р. Редди, Л. Эрманом и их коллегами. Горизонтальная ось - время, отсчитываемое от начала произнесенной фразы; вертикальная ось - уровни абстракции, начиная с отдельных звуковых волн и кончая полным предложением. Третье измерение характеризует уровень достоверности, ассоциируемый с каждой гипотезой, записанной на доске: наиболее вероятные предположения, возможные в каждый данный момент на каждом уровне абстракции, расположены ближе к передней поверхности куба, показанного на рисунке. При помощи доски модули знаний различных уровней могут взаимодействовать между собой. Например, если программа, проанализировав интонацию, установила, что предложение является вопросом, эта информация направляет процесс формирования гипотез на уровне слова или фразы.

Фреймы

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

ИСТОЧНИКИ "интеллекта"

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


Источник: Неизвестен, © Prof 2003-2004