«Основы искусственного интеллекта»

Рождение искусственного интеллекта (1956 год)

В Принстонском университете проводил свои исследования еще один авторитетный специалист в области искусственного интеллекта, Джон Маккарти. После получения ученой степени Маккарти перешел в Дартмутский колледж, который и стал официальным местом рождения этой области знаний. Они организовывали двухмесячный семинар в Дартмуте летом 1956 года. Всего на этом семинаре присутствовали 10 участников, включая Тренчарда Мура из Принстонского университета, Артура Самюэла из компании IBM, а также Рея Соломонова и Оливера Селфриджа из Массачусетского технологического института (Massachussets Institute of Technlogies — MIT). Два исследователя из технологического института Карнеги, Аллеи Ньюэлл и Герберт Саймон, буквально монополизировали все это представление. Тогда как другие могли лишь поделиться своими идеями и в некоторых случаях показать программы для таких конкретных приложений, как шашки, Ньюэлл и Саймон уже мог ли продемонстрировать программу, проводящую рассуждения, Logic Theorist (LT). Вскоре после этого семинара программа показала свою способность доказать большинство теорем из главы 2 труда Рассела и Уайтхеда Principia Mathematica. Дартмутский семинар не привел к появлению каких-либо новых крупных открытий, но позволил познакомиться всем наиболее важным деятелям в этой научной области. Они, а также их студенты и коллеги из Массачусетсского технологического института, Университета Карнеги—Меллона, Станфордского университета и компании IBM занимали ведущее положение в этой области в течение следующих 20 лет. Возможно, дольше всего сохранившимся результатом данного семинара было соглашение принять новое название для этой области, предложенное Маккарти, — искусственный интеллект.

Ранний энтузиазм, большие ожидания (период с 1952 года по 1969 год)

Первые годы развития искусственного интеллекта были полны успехов, хотя и достаточно скромных. За первыми успешными разработками Ньюэлла и Саймона последовало создание программы общего решателя задач (General Problem Solver— GPS). Работая в компании IBM, Натаниэль Рочестер и его коллеги создали некоторые из самых первых программ искусственного интеллекта. Герберт Гелернтер сконструировал программу Geometry Theorem Prover (программа автоматического доказательства геометрических теорем), которая была способна доказывать такие теоремы, которые показались бы весьма сложными многим студентам-математикам. Начиная с 1952 года Артур Самюэл написал ряд программ для игры в шашки, которые в конечном итоге научились играть на уровне хорошо подготовленного любителя. В ходе этих исследований Самюэл опроверг утверждение, что компьютеры способны выполнять только то, чему их учили: одна из его программ быстро научилась играть лучше, чем ее создатель. Джон Маккарти перешел из Дартмутского университета в Массачусетский технологический институт и здесь в течение одного исторического 1958 года внес три крайне важных вклада в развитие искусственного интеллекта. Джон Маккарти привел определение нового языка высокого уровня. Lisp, которому суждено было стать доминирующим языком программирования для искусственного интеллекта. В том же 1958 году Маккарти опубликовал статью под названием Рrograms with Соттоп Sense, в которой он описал гипотетическую программу Аdvice Такеr, которая может рассматриваться как первая полная система искусственного интеллекта. Знаменитый 1958 год отмечен также тем, что именно в этот год Марвин Минский перешел в Массачусетсский технологический институт. В 1963 году Маккарти открыл лабораторию искусственного интеллекта в Станфордском университете. Минский руководил работой ряда студентов, выбравших для себя задачи ограниченных масштабов, для решения которых, как в то время казалось, требовалась интеллектуальность. Эти ограниченные проблемные области получили название микромиров.

Столкновение с реальностью (период с 1966 года по 1973 год)

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

Системы, основанные на знаниях: могут ли они стать ключом к успеху

(период с 1969 года по 1979 год)

Основной подход к решению задач, сформированный в течение первого десятилетия исследований в области искусственного интеллекта, представлял собой механизм поиска общего назначения, с помощью которого предпринимались попытки связать в единую цепочку элементарные этапы проведения рассуждений для формирования полных решений. Подобные подходы получили название слабых методов, поскольку они не позволяли увеличить масштабы своего применения до уровня более крупных иди более сложных экземпляров задач, несмотря на то, что были общими. Альтернативным по сравнению со слабыми методами стал подход, предусматривающий использование более содержательных знаний, относящихся к проблемной области, который позволяет создавать более длинные цепочки шагов логического вывода и дает возможность проще справиться с теми проблемными ситуациями, которые обычно возникают в специализированных областях знаний. Одним из первых примеров реализации такого подхода была программа Dendral. Она была разработана в Станфордском университете группой ученых, в которую вошли Эд Фейгенбаум (бывший студент Герберта Саймона), Брюс Бьюкенен (философ, который сменил специальность и стал заниматься компьютерными науками) и Джошуа Ледерберг (лауреат Нобелевской премии в области генетики). Руководствуясь этим опытом, Фейгенбаум и другие специалисты из Станфордского университета приступили к разработке проекта эвристического программирования (Heuristic Programming Project — НРР), целью которого было исследование того, в какой степени созданная ими новая методология экспертных систем может быть применена в других областях интеллектуальной деятельности человека. На очередном этапе основные усилия были сосредоточены в области медицинской диагностики. Фейгенбаум, Бьюкенен и доктор Эдвард Шортлифф разработали программу Мусin для диагностики инфекционных заболеваний кровеносной системы.

Превращение искусственного интеллекта в индустрию

(период с 1980 года по настоящее время)

Первая успешно действующая коммерческая экспертная система, К.1, появилась в компании DEC (Digatal Equipment Corporation). Эта программа помогала составлять конфигурации для выполнения заказов на новые компьютерные системы; к 1986 году она позволяла компании DЕС экономить примерно 40 миллионов долларов в год. К 1988 году группой искусственного интеллекта компании DЕС было развернуто 40 экспертных систем. В компании Du Роnt применялось 100 систем, в разработке находилось еще 500, а достигнутая экономия составляла примерно 10 миллионов долларов в год. В 1981 году в Японии было объявлено о развертывании проекта создания компьютера "пятого поколения" — 10-летнего плана по разработке интеллектуальных компьютеров, работающих под управлением языка Рго1оg. В ответ на это в Соединенных Штатах была сформирована корпорация Мicroelectronics and Соmputег Тесhnologу Сorporation (МСС) как научно-исследовательский консорциум. В целом в индустрии искусственного интеллекта произошел бурный рост, начиная с нескольких миллионов долларов в 1980 году и заканчивая миллиардами долларов в 1988 году. Однако вскоре после этого наступил период, получивший название "зимы искусственного интеллекта".

Возвращение к нейронным сетям (период с 1986 года по настоящее время)

Хотя основная часть специалистов по компьютерным наукам прекратила исследования в области нейронных сетей в конце 1970-х годов, работу в этой области продолжили специалисты из других научных направлений. Такие физики, как Джон Хопфилд, использовали методы из статистической механики для анализа свойств хранения данных и оптимизации сетей, рассматривая коллекции узлов как коллекции атомов. Психологи, включая Дэвида Румельхарта и Джефа Хинтона, продолжали исследовать модели памяти на основе нейронных сетей. Настоящий прорыв произошел в середине 1980-х годов, когда по меньшей мере четыре разные группы снова открыли алгоритм обучения путем обратного распространения, впервые предложенный в 1969 году Брайсоном и Хо. Эти так называемые коннекционистские (основанные на соединениях) модели интеллектуальных систем многими рассматривались как непосредственно конкурирующие и с символическими моделями, разрабатываемыми Ньюэллом и Саймоном, и с логицистским подходом, предложенным Маккарти и другими.

Превращение искусственного интеллекта в науку

(период с 1987 года по настоящее время)

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

Появление подхода, основанного на использовании интеллектуальных агентов (период с 1995 года по настоящее время)

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

Современное состояние разработок

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

• Автономное планирование и составление расписаний. Работающая на удалении в сотни миллионов километров от Земли программа Remote Agent агентства NASA стала первой бортовой автономной программой планирования, предназначенной для управления процессами составления расписания операций длякосмического аппарата [744]. Программа Кетохе А§ет вырабатывала планына основе целей высокого уровня, задаваемых с Земли, а также контролировала работу космического аппарата в ходе выполнения планов: обнаруживала,диагностировала и устраняла неполадки по мере их возникновения.

• Ведение игр. Программа Dеер В1uе компании IВМ стала первой компьютернойпрограммой, которой удалось победить чемпиона мира в шахматном матче,после того как она обыграла Гарри Каспарова со счетом 3,5:2,5 в показательном матче. Каспаров заявил, что ощущал напротив себя за шахматной доской присутствие "интеллекта нового типа". Журнал Newsweek описал этот матч под заголовком "Последний оборонительный рубеж мозга". Стоимость акций IВМ выросла на 18 миллиардов долларов.

• Автономное управление. Система компьютерного зрения Alvin была обучена вождению автомобиля, придерживаясь определенной полосы движения. В университете СМU эта система была размещена в микроавтобусе, управляемом компьютером NavLаЬ, и использовалось для проезда по Соединенным Штатам; на протяжении 2850 миль (4586,6 км) система обеспечивала рулевое управление автомобилем в течение 98% времени. Человек брал на себя управление лишь в течение остальных 2%, главным образом на выездных пандусах. Компьютер NavLаЬ был оборудован видеокамерами, которые передавали изображения дороги в систему Alvinn, а затем эта система вычисляла наилучшее направление движения, основываясь на опыте, полученном в предыдущих учебных пробегах.

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

• Планирование снабжения. Во время кризиса в Персидском заливе в 1991 году в армии США была развернута система DАRТ (Dynamic Аnalysis and Replanning) для обеспечения автоматизированного планирования поставок и составления графиков перевозок. Работа этой системы охватывала одновременно до 50 000 автомобилей, единиц груза и людей; в ней приходилось учитывать пункты отправления и назначения, маршруты, а также устранять конфликты между всеми параметрами. Методы планирования на основе искусственного интеллекта позволяли вырабатывать в течение считанных часов такие планы, для составления которых старыми методами потребовались бы недели. Представители агентстваDАRРА (Defense Advadcend Research Project Agency - управление перспективных исследовательских программ) заявили, что одно лишь это приложение сторицей окупило тридцатилетние инвестиции в искусственный интеллект, сделанные этим агентством.

• Робототехника. Многие хирурги теперь используют роботов-ассистентов в микрохирургии. Например, HipNav — это система, в которой используются методы компьютерного зрения для создания трехмерной модели анатомии внутренних органов пациента, а затем применяется робототехническое управление для руководства процессом вставки протеза, заменяющего тазобедренный сустав.

• Понимание естественного языка и решение задач. Программа Ргоvегb это компьютерная программа, которая решает кроссворды намного лучше, ем большинство людей; в ней используются ограничения, определяющие состав возможных заполнителей слов, большая база с данными о встречавшихся ранее кроссвордах, а также множество различных источников информации, включая словари и оперативные базы данных, таких как списки кинофильмов и актеров, которые играли в этих фильмах. Например, эта программа способна определить, что одним из решений, подходящих для ключа "Nice Story", является слово "ЕТАGЕ", поскольку ее база данных содержит пару ключ—решение "Story in France/ETAGE", а сама программараспознает, что шаблоны "Nice X" и “X in France” часто имеют одно и то жерешение. Программа не знает, что Niсе (Ницца) — город во Франции, но способна разгадать эту головоломку.

Контрольные вопросы.

1. Опишите период развития ИИ с 1943 года по 1955 год.

2. Опишите период появления ИИ (1956 год).

3. Опишите период с 1952 года по 1969 год в истории ИИ.

4. Опишите период с 1966 года по 1973 год в истории ИИ.

5. Опишите период с 1969 года по 1979 год в истории ИИ.

6. Опишите период с 1980 года по настоящее время в истории ИИ.

7. Опишите период с 1986 года по настоящее время в истории ИИ.

8. Опишите период становления ИИ как научного направления.

9. Опишите период появления интеллектуальных агентов.

10. Опишите современное состояние разработок в области ИИ.

2. D2 — данные на материальных носителях информации (таблицы, протоколы, справочники);

3. D3 — модели (структуры) данных в виде диаграмм, графиков, функций;

4. D4 — данные в компьютере на языке описания данных;

5. D5 — базы данных на машинных носителях информации.

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

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

При обработке на ЭВМ знания трансформируются аналогично данным.

1. Z1 — знания в памяти человека как результат мышления;

2. Z2 — материальные носители знаний (учебники, методические пособия);

3. Z3 — поле знаний — условное описание основных объектов предметной области, их атрибутов и закономерностей, их связывающих;

4. Z4 — знания, описанные на языках представления знаний (продукционные языки, семантические сети, фреймы — см. далее);

5. Z5 — база знаний на машинных носителях информации.

Часто используется такое определение знаний.

Знания — это хорошо структурированные данные, или данные о данных, или метаданные.

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

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

Знания могут быть классифицированы по следующим категориям:

Поверхностные — знания о видимых взаимосвязях между отдельными событиями и фактами в предметной области.

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

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

Классификация методов практического извлечения знаний

Подробно рассмотрев теоретические аспекты инженерии знаний, в явном виде никак не определить, каким практическим методом эти знания будут получены. В неявном виде предполагается, что это некоторое взаимодействие инженера по знаниям и эксперта в форме непосредственного живого общения. Однако это не единственная форма извлечения знаний, хотя и довольно распространенная. Существуют около 15 ручных (неавтоматизированных) методов извлечения и более 20 автоматизированных методов приобретения и формирования знаний. Рисунок 3.1 иллюстрирует предлагаемую классификацию методов извлечения знаний, в которой используются наиболее употребительные термины, что позволит инженерам по знаниям в зависимости от конкретной задачи и ситуации выбрать подходящий метод. Из предложенной схемы классификации видно, что основной принцип деления cвязан с источником знаний.

Рис. 3. 1. Классификация методов извлечения знаний

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

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

Активные методы можно разделить на две группы в зависимости от числа экспертов, отдающих свои знания. Если их число больше одного, то целесообразно помимо серии индивидуальных контактов с каждым применять и методы групповых обсуждений предметной области. Такие групповые методы обычно активизируют мышление участников дискуссий и позволяют выявлять весьма нетривиальные аспекты их знаний. В свою очередь, индивидуальные методы на сегодняшний день остаются ведущими, поскольку столь деликатная процедура, как «отъем знаний», не терпит лишних свидетелей. Отдельно следует сказать об играх. Игровые методы сейчас широко используются в социологии, экономике, менеджменте, педагогике для подготовки руководителей, учителей, врачей и других специалистов. Игра — это особая форма деятельности и творчества, где человек раскрепощается и чувствует себя намного свободнее, чем в обычной трудовой деятельности. На выбор метода влияют три фактора: личностные особенности инженера по знаниям, личностные особенности эксперта и характеристика предметной области.

Одна из возможных классификаций людей по психологическим характеристикам делит всех на три типа:

• мыслитель (познавательный тип);

• собеседник (эмоционально-коммуникативный тип);

• практик (практический тип).

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

Для характеристики предметных областей можно предложить следующую классификацию (Рис. 3.2.):

• хорошо документированные;

• средне документированные;

• слабо документированные.

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

Рис. 3.2. Классификация предметных областей

• хорошо структурированными — с четкой аксиоматизацией, широким применением математического аппарата, устоявшейся терминологией;

• средне структурированными — с определившейся терминологией, развивающейся теорией, явными взаимосвязями между явлениями;

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

Разработка моделей на Lisp

Задача 1. Решить задачу упорядочивания элементов по возрастанию в одномерной последовательности с применением продукционных правил.

Решение.

Рассмотрим в качестве предметной области последовательность элементов . Необходимо разработать систему знаний об их переупорядочивании и представить в виде некоторой модели, при этом предполагается отсутствие тех или иных алгоритмов для решения подобного рода задач. В качестве модели данной предметной области выберем продукционные правила. Для того чтобы разработать систему знаний для решения этой задачи рассмотрим его пространство состояний. В качестве состояний исследуемого объекта выберем последовательность расположения его элементов. Так как, каждое следующее состояние объекта получается из предыдущего путем обмена двух смежных элементов, то в качестве системы знаний можно предложить некоторое подмножество этих правил обмена, которые ведут к состоянию . В список подобного рода правил войдут только: →, → и →. В пользу правильности выбора именно этих правил можно привести следующий аргумент – имеющиеся алгоритмы упорядочивания последовательности (тот же самый алгоритм «всплывающего пузырька») строятся на идее обмена двух элементов, нарушающих в ней порядок расположения. Следовательно, применяя в каком-то определенном порядке эти правила к текущему состоянию исследуемого объекта можно прийти к конечному состоянию. Этот результат можно наблюдать в пространстве состояний, построенном на выше приведенных правилах, играющих роль правил переходов из одного состояния в другое (Рис. 4.1.).

Рис. 4.1. Пространство состояний для задачи упорядочивания.

Таким образом, модель знаний предметной области с учетом определения продукционных правил будет иметь вид:

Ясно, что, применяя эти правила в определенном порядке можно прийти к упорядоченному виду исходной последовательности. Механизм извлечения знаний должен позволять получать эти решения. Разработаем механизм извлечения этих правил и их применения. Для этого необходимо разработать терминологию для описания состояния исследуемого объекта и произведения необходимого действия над ним. Роль исследуемого объекта в программе будет играть список sp. Конечное состояние этого объекта представлено списком end. Переменная pos предназначена для хранения начала подпоследовательности, которая в дальнейшем будет подвержена обмену элементами.

(setf pos nil) (setf sp '(c b a c a)) (setf end '(a a b c c))

Функция poisk возвращает в переменную pos начало подпоследовательности,

состоящей из элементов el1 и el2:

(defun poisk (el1 el2) (progn (setf len (length sp))

(setf pos nil) (setf flag t) (dotimes (i (- len 1))

(if (and flag (equal el1 (nth i sp)) (equal el2 (nth (+ i 1) sp)))

(progn (setf pos i) (setf flag nil)))) (if flag nil t)))

Функция zamena производит обмен пары элементов в последовательности с учетом его начала в переменной pos.

(defun zamena (el1 el2) (progn (setf buf nil) (if (or

(and (equal el1 'b) (equal el2 'a)) (and (equal el1 'c) (equal el2 'a))

(and (equal el1 'c) (equal el2 'b))) (progn (setf buf (nth pos sp))

(setf (nth pos sp) (nth (+ pos 1) sp)) (setf (nth (+ pos 1) sp) buf)))))

Применяя эту терминологию базу знаний можно представить в виде списка:

(setf rule (list '(if (poisk 'b 'a) (zamena 'b 'a))

'(if (poisk 'c 'a) (zamena 'c 'a)) '(if (poisk 'c 'b) (zamena 'c 'b))))

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

1. выбрать третье правило через команду (nth 2 rule)

2. вычислить выбранное правило через команду (eval (nth 2 rule))

В этом случае объект перейдет из исходного состояния в следующее

.

Таким образом, программа, в общем, будет выглядеть так:

;установка начальной позиции

(setf pos nil)

;установка описания предметной области - списка

(setf sp '(a b a c c b a c a)) (setf end '(a a a a b b c c c))

;функция нахождения подсписка в списке;

(defun poisk (el1 el2) (progn (setf len (length sp))

(setf pos nil) (setf flag t) (dotimes (i (- len 1))

(if (and flag (equal el1 (nth i sp)) (equal el2 (nth (+ i 1) sp)))

(progn (setf pos i) (setf flag nil)))) (if flag nil t)))

(defun zamena (el1 el2) (progn (setf buf nil) (if (or

(and (equal el1 'b) (equal el2 'a)) (and (equal el1 'c) (equal el2 'a))

(and (equal el1 'c) (equal el2 'b))) (progn (setf buf (nth pos sp))

(setf (nth pos sp) (nth (+ pos 1) sp)) (setf (nth (+ pos 1) sp) buf)))))

;база знаний

(setf rule (list

'(if (poisk 'b 'a) (zamena 'b 'a)) '(if (poisk 'c 'a) (zamena 'c 'a))

'(if (poisk 'c 'b) (zamena 'c 'b)))) ;механизм сопоставления с образцом

(setf len (length sp)) (do () ((equal sp end) sp) (setf mkp nil)

(dotimes (i (length rule)) (if (eval (nth 1 (nth i rule)))

(setf mkp (cons i mkp)))) (setf mkp (reverse mkp))

(princ (+ (car mkp) 1)) (princ ":") (princ sp) (princ "->")

(eval (nth (car mkp) rule)) (print sp))

Задача 2. Разработать семантическую модель и механизм извлечения знаний на Lisp.

Решение.

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

Tконцепты={fly, feathers, bird, ostrich, walk, penguin, brown, opus, canary, tweety, yellow, sing, white, robin, red, animal, fish, swim, skin}

Tотношения={travel, covering, isa, color, sound}

Тогда семантическая сеть, описывающая знания из предметной области будет представлена в следующей форме (Рис. 4.2.):

Рис. 4.2. Семантическая сеть предметной области.

В качестве подхода при разработке этой семантической сети на языке программирования Common Lisp выберем тройки «символ – атрибут - значение». Для разработанной семантической сети программное представление будет иметь вид:

(setf (get 'animal 'covering) 'skin) (setf (get 'bird 'covering) 'feathers)

(setf (get 'bird 'travel) 'flies) (setf (get 'bird 'isa) 'animal)

(setf (get 'fish 'isa) 'animal) (setf (get ' fish 'travel) 'swim)

(setf (get 'ostrich 'isa) 'bird) (setf (get 'ostrich 'travel) 'walk)

(setf (get 'penguin 'isa) 'bird) (setf (get 'penguin 'travel) 'walk)

(setf (get 'penguin 'color) 'brown) (setf (get 'opus 'isa) 'penguin)

(setf (get 'canary 'isa) 'bird) (setf (get 'canary 'color) 'yellow)

(setf (get 'canary 'sound) 'sing) (setf (get 'tweety 'isa) 'canary)

(setf (get 'tweety 'color) 'white) (setf (get 'robin 'isa) 'bird)

(setf (get 'robin 'sound) 'sings) (setf (get 'robin 'color) 'red)

В этом представлении семантической сети уже определена иерархия наследования. Если выполнить поиск по связи isa, то можно определить родительский объект по заданному свойству. Для нахождения родительских объектов используется поиск в глубину, который прекращается при нахождении экземпляра заданного свойства. В качестве стратегии поиска можно также использовать поиск в ширину. Функция inherit-get — это вариация функции get, которая сначала пытается получить свойство данного символа. Если это свойство отсутствует, функция inherit-get вызывает функцию get-from-parents для реализации поиска.

(defun inherit-get (obj property)

(or (get obj property) (get-from-parents (get obj 'isa) property)))

(defun get-from-parents (parents property) (cond ((null parents) nil)

((atom parents) (inherit-get parents property)) (t (or (get-from-parents (car parents) property)

(get-from-parents (cdr parents) property)))))