»стори€ создани€ искусственного интеллекта


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

≈сли вы хотите видеть на нашем сайте больше статей то кликните ѕоделитьс€ в социальных сет€х! —пасибо!
—мотрите также:

ќбратите внимание полезна€ информаци€.