Масленникова О.Е., Попова И.В. Основы искусственного интеллекта
Подождите немного. Документ загружается.
Министерство образования и науки Российской Федерации
ГОУ ВПО «Магнитогорский государственный университет»
О.Е. Масленникова, И.В. Попова
Основы искусственного интеллекта
Учебное пособие
Магнитогорск
2008
- 2 -
УДК 681.142.1.01
ББК З97
М
Рецензенты:
Доктор физико-математических наук, профессор
С.И. Кадченко
Доктор технических наук, профессор
А,С. Сарваров
Масленникова О.Е., Попова И.В.
Основы искусственного интеллекта : учеб. пособие / О.Е. Масленникова,
И.В. Попова. — Магнитогорск : МаГУ, 2008. — 282 c.
ISBN 978-5.86781-609-4
В учебном пособии излагаются модели представления знаний, теория
экспертных систем, основы логического и функционального
программирования. Большое внимание уделено истории развития
искусственного интеллекта. Изложение материала сопровождается большим
количеством иллюстраций, предлагаются упражнения и вопросы для
самоконтроля.
Работа ориентирована на студентов очного и заочного отделений,
обучающихся по направлениям «Информатика», «Физико-математическое
образование (Профиль – информатика)».
УДК 681.142.1.01
ББК З97
ISBN 978-5.86781-609-4
Масленникова О.Е., Попова И.В., 2008
Магнитогорский государственный университет, 2008
М
- 3 -
ОГЛАВЛЕНИЕ
ГЛАВА 1. ВВЕДЕНИЕ В ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ ................... 5
1.1. ИСТОРИЯ РАЗВИТИЯ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА КАК НАУЧНОГО
НАПРАВЛЕНИЯ ........................................................................................................ 9
1.2. ОСНОВНЫЕ НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ В ОБЛАСТИ ИСКУССТВЕННОГО
ИНТЕЛЛЕКТА ......................................................................................................... 13
1.3. ФИЛОСОФСКИЕ АСПЕКТЫ ПРОБЛЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА ....... 16
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ............................................................................ 21
ЛИТЕРАТУРА ......................................................................................................... 21
ГЛАВА 2. МОДЕЛИ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ ................................... 22
2.1. ЗНАНИЯ .......................................................................................................... 22
2.2. ЛОГИЧЕСКАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ .......................................... 25
2.3. СЕМАНТИЧЕСКИЕ СЕТИ .................................................................................. 58
2.4. ФРЕЙМЫ ......................................................................................................... 59
2.5. ПРОДУКЦИОННАЯ МОДЕЛЬ ............................................................................ 62
2.6. ДРУГИЕ МОДЕЛИ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ .................................................. 64
УПРАЖНЕНИЯ ....................................................................................................... 78
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ............................................................................ 83
ЛИТЕРАТУРА ......................................................................................................... 84
ГЛАВА 3. ЭКСПЕРТНЫЕ СИСТЕМЫ .......................................................... 86
3.1. ПОНЯТИЕ ОБ ЭКСПЕРТНОЙ СИСТЕМЕ ............................................................. 86
3.2. ВИДЫ ЭКСПЕРТНЫХ СИСТЕМ И ТИПЫ РЕШАЕМЫХ ЗАДАЧ ............................. 89
3.3. СТРУКТУРА И РЕЖИМЫ РАБОТЫ ЭКСПЕРТНОЙ СИСТЕМЫ .............................. 99
3.4. ТЕХНОЛОГИЯ РАЗРАБОТКИ ЭКСПЕРТНЫХ СИСТЕМ ...................................... 102
3.5. ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ЭКСПЕРТНОЙ СИСТЕМЫ .......................... 113
3.6. ИНТЕЛЛЕКТУАЛЬНЫЕ ИНФОРМАЦИОННЫЕ СИСТЕМЫ ................................. 129
УПРАЖНЕНИЯ ..................................................................................................... 135
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ .......................................................................... 136
ЛИТЕРАТУРА ....................................................................................................... 138
ГЛАВА 4. ПРОЛОГ КАК ЯЗЫК ЛОГИЧЕСКОГО
ПРОГРАММИРОВАНИЯ ................................................................................ 139
4.1. ПРЕДСТАВЛЕНИЕ О ЛОГИЧЕСКОМ ПРОГРАММИРОВАНИИ ............................ 139
4.2. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ О ПРЕДМЕТНОЙ ОБЛАСТИ ВИДЕ ФАКТОВ И ПРАВИЛ
БАЗЫ ЗНАНИЙ ПРОЛОГА ...................................................................................... 140
4.3. ДЕСКРИПТИВНЫЙ, ПРОЦЕДУРНЫЙ И МАШИННЫЙ СМЫСЛ ПРОГРАММЫ
НА ПРОЛОГЕ ....................................................................................................... 148
4.4. ОСНОВНЫЕ ПРИЁМЫ ПРОГРАММИРОВАНИЯ В ПРОЛОГЕ ............................. 151
4.5. СРЕДА VISUAL PROLOG ................................................................................ 154
УПРАЖНЕНИЯ ..................................................................................................... 194
ЛИТЕРАТУРА ....................................................................................................... 197
- 4 -
ГЛАВА 5. ПРЕДСТАВЛЕНИЕ О ФУНКЦИОНАЛЬНОМ
ПРОГРАММИРОВАНИИ ................................................................................ 199
5.1. ИСТОРИЯ ФУНКЦИОНАЛЬНОГО ПРОГРАММИРОВАНИЯ ................................ 200
5.2. СВОЙСТВА ЯЗЫКОВ ФУНКЦИОНАЛЬНОГО ПРОГРАММИРОВАНИЯ ................ 203
5.3. ЗАДАЧИ ФУНКЦИОНАЛЬНОГО ПРОГРАММИРОВАНИЯ .................................. 207
УПРАЖНЕНИЯ ..................................................................................................... 210
ОТВЕТЫ ДЛЯ САМОПРОВЕРКИ ............................................................................. 210
ЛИТЕРАТУРА ....................................................................................................... 211
ГЛОССАРИЙ ..................................................................................................... 213
ПРИЛОЖЕНИЕ 1 .............................................................................................. 221
ПРИЛОЖЕНИЕ 2 .............................................................................................. 252
ПРИЛОЖЕНИЕ 3 .............................................................................................. 265
- 5 -
ПРЕДИСЛОВИЕ
В последнее время наблюдается возрастание интереса к искусственному
интеллекту, вызванное повышением требований к информационным
системам. Человечество неуклонно движется к новой информационной
революции, сравнимой по масштабам с развитием Интернета.
Искуственный интеллект – направление информатики, целью которого
является разработка аппаратно-программных средств, позволяющих
пользователю-непрограммисту ставить и решать свои, традиционно
считающиеся интеллектуальными задачи, общаясь с ЭВМ на ограниченном
подмножестве естественного языка.
История искусственного интеллекта как нового научного направления
начинается в середине XX века. К этому времени уже было сформировано
множество предпосылок его зарождения: среди философов давно шли споры
о природе человека и процессе познания мира, нейрофизиологи и психологи
разработали ряд теорий относительно работы человеческого мозга и
мышления, экономисты и математики задавались вопросами оптимальных
расчѐтов и представления знаний о мире в формализованном виде; наконец,
зародился фундамент математической теории вычислений — теории
алгоритмов — и были созданы первые компьютеры.
Целью настоящего пособия является изложение основных направлений
и методов, применяемых в искусственном интеллекте, а также определение
возможности их использования в профессиональной педагогической
деятельности.
В данное учебное пособие состоит из пяти глав. В первой приводится
краткое введение в искусственный интеллект: рассматривается история его
развития как научного направления, выделяются основные области
искусственного интлеекта, рассматриваются такие философские аспекты
проблемы как возможность существования, безопасность, полезность
искусственного интлеекта. Вторая глава посвящена описанию классических
моделей представления знаний: логической, семантической, фреймовой,
продукционной и нейросетевой. В третьей главе рассматриваются
теоретические и практические вопросы разработки экспертных систем;
приводится описание оболочки XpertRule. В чѐтвѐртой главе излагаются
основные принципы программирования на языке Пролог, описывается среда
Visual Prolog. Пятая глава описывает основы функционального
программирования с примерами на языке LISP.
Пособие содержит большое количество иллюстраций, упражнения и
вопросы для самоконтроля. Для удобства изучения материала предусмотрен
глоссарий.
- 6 -
ГЛАВА 1. ВВЕДЕНИЕ В ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ
Искусственный интеллект (ИИ) - это новое направление информатики,
предметом изучения которого является любая интеллектуальная
деятельность человека, подчиняющаяся заранее известным законам. Образно
это направление называют «старшим сыном информатики», так как многие
нерешенные ею задачи постепенно находят свое решение в рамках
искусственного интеллекта. Известно, что предметом информатики является
обработка информации. К области же ИИ относятся такие случаи (задачи) из
этой обработки, которые не могут быть выполнены с помощью простых и
точных алгоритмических методов, и которых насчитывается великое
множество.
ИИ опирается на знания о процессе человеческого мышления. При этом
точно не известно, как работает человеческий мозг, однако для разработки
эффективно работающих программ с элементами ИИ уже достаточно тех
знаний об особенностях человеческого интеллекта, которыми располагает
наука сегодня. При этом ИИ не пытается копировать в точности работу
человеческого мозга, а пытается моделировать его функции с помощью
средств вычислительной техники.
С самого момента своего рождения ИИ развивается как
междисциплинарное направление, взаимодействующее с информатикой и
кибернетикой, когнитивными науками, логикой и математикой,
лингвистикой и психологией, биологией и медициной (рис. 1).
Информатика и кибернетика. Многие специалисты пришли в ИИ из
информатики и кибернетики. Также многие комбинаторные задачи, не
решаемые традиционными методами в информатики, перекочевали в область
ИИ. Кроме того, результаты, полученные в ИИ, заимствуются при создании
программного обеспечения и становятся частью Computer Science
(информатики).
Когнитивные науки. Когнитивные науки - это науки о знаниях. ИИ
также занимается знаниями. Но когнитивные науки используют при этом не
только информационный и нейробиологический подходы, но также
рассматривают социальные и психолингвистические аспекты использования
знаний.
Логика и математика. Логика лежит в основе всех известных
формализмов представления знаний, а также таких языков
программирования, как Lisp и Prolog. Для решения задач ИИ используются
методы дискретной математики, теории игр, теории операций. В свою
очередь ИИ может применяться для доказательства теорем, решения задач в
различных областях математики: геометрии, интегрального исчисления.
Психология и лингвистика. В последнее время специалисты по ИИ
заинтересовались психологическими аспектами поведения людей с целью его
моделирования. Психология помогает строить модели ценностных оценок,
принятия субъективных решений. Представляет интерес психология общения
- 7 -
«человек-компьютер», психолингвистика. Компьютерная лингвистика - это
часть ИИ, которая базируется на математических методах обработки
естественного и искусственных языков, с одной стороны, и на
феноменологии языка с другой стороны.
Биология и медицина позволяет лучше изучить и понять работу мозга,
систем зрения, слуха и других естественных датчиков и дать новый импульс
в области моделирования их работы.
Рис. 1. Взаимодействие ИИ с другими дисциплинами
Не существует единого определения ИИ так же, как не существует
единого определения естественного интеллекта. Среди многих точек зрения
на эту научную область сейчас доминируют три.
1. Исследования в области ИИ являются фундаментальными
исследованиями, в рамках которых разрабатываются модели и
методы решения задач, традиционно считавшиеся
интеллектуальными и неподдающиеся ранее формализации и
автоматизации.
2. ИИ - это новое направление информатики, связанное с новыми
идеями решения задач на ЭВМ, с разработкой принципиально
иной технологии программирования, с переходом к архитектуре
ЭВМ, отвергающей классическую архитектуру, которая восходит
еще к первым ЭВМ.
3. В результате работ в области ИИ рождается множество
прикладных систем, решающих задачи, для которых ранее
создаваемые системы были не пригодны.
- 8 -
Для иллюстрации первого подхода можно привести пример с
калькулятором. В начале века арифметические вычисления с многозначными
цифрами были уделом немногих одаренных личностей и способность
производить в уме такие арифметические действия по праву считалась
уникальным даром природы и являлась объектом научных исследований. В
наше время изобретение калькулятора сделало эту способность доступной
даже третьекласснику. То же самое и в ИИ: он усиливает интеллектуальные
возможности человека, беря на себя решение ранее не формализуемых задач.
Для иллюстрации второго подхода можно рассмотреть историю с
попыткой создания ЭВМ пятого поколения. В середине 80-х годов Япония
объявила о начале амбициозного проекта по созданию ЭВМ пятого
поколения. В основе проекта была положена идея аппаратной реализации
языка ПРОЛОГ. Однако проект окончился неудачей, хотя и имел сильное
влияние на развитие и распространение языка ПРОЛОГ как языка
программирования. Причиной неудачи было поспешное заключение о том,
что один язык (пусть и достаточно универсальный) может обеспечить
единственное решение для всех задач. Практика показала, что пока
универсальной парадигмы программирования для решения всех задач не
придумано и вряд ли она появится. Это связано с тем, что каждая задача - это
часть предметной области, требующая тщательного изучения и
специфического подхода. Попытки создания новых архитектур ЭВМ
продолжаются и связаны с параллельными и распределенными
вычислениями, нейрокомпьютерами, вероятностными и нечеткими
процессорами.
Работы в области создание экспертных систем (ЭС) можно отнести к
третьему, наиболее прагматическому направлению в ИИ. Экспертные
системы - это программные комплексы, заменяющие человека-специалиста в
узких областях интеллектуальной деятельности, требующих применения
специальных знаний. Создание ЭС в области медицины (типа MYCIN)
позволяет распространять знания в самые отдаленные районы. Таким
образом в сочетании с телекоммуникационным доступом любой сельский
врач может получить консультацию у такой системы, заменяющей ему
общение со специалистом по узкому вопросу.
В России ИИ нашел своих сторонников практически с момента своего
появления. Однако официальное признание эта дисциплина получила далеко
не сразу. ИИ подвергался критике как под-отрасль кибернетики, считавшейся
«лженаукой». До какого-то момента времени играло отрицательную роль и
эпатирующее название «искусственный интеллект». Так, в Президиуме АН
ходила шутка о том, что «искусственным интеллектом занимаются те, кому
не хватает естественного». Однако сегодня ИИ - это официально признанное
в России научное направление, выпускаются журналы «Управляющие
системы и машины» и «Новости ИИ», проводятся научные конференции и
семинары. Существует Российская Ассоциация ИИ, насчитывающая около
200 членов, президентом которой является доктор техн.наук Д.А.Поспелов, а
- 9 -
почетным президентом академик РАН Г.С.Поспелов. Существует
Российский Институт Искусственного Интеллекта при Совете Президента
Российской Федерации по информатике и ВТ. В рамках РАН существует
Научный Совет по проблеме «Искусственный интеллект». При участии этого
Совета издано немало книг по тематике ИИ, переводов. Хорошо известны
работы Д.А.Поспелова, Литвинцевой и Кандрашиной - в области
представления и обработки знаний, Э.В. Попова и Хорошевского - в области
обработки естественного языка и экспертных систем, Аверкина и Мелихова -
в области нечеткой логики и нечетких множеств, Стефанюка - в области
обучающихся систем, Кузнецова, Финна и Вагина - в области логики и
представления знаний.
В России существует традиционно сильная компьютерная
лингвистическая школа, которая берет начало от работ по модели «Смысл-
Текст» Мельчука. Среди известных компьютерных лингвистов можно
назвать Апресяна, Городецкого, Падучеву, Нариньяни, Леонтьеву,
Шаляпину, Зализняка-старшего, Кибрика-старшего, Баранова и мн. др.
1.1. История развития искусственного интеллекта как научного
направления
Идея создания искусственного подобия человеческого разума для
решения сложных задач и моделирования мыслительной способности витала
в воздухе с древнейших времен.
В древнем Египте была создана «оживающая» механическая статуя бога
Амона. У Гомера в «Илиаде» бог Гефест ковал человекоподобные существа-
автоматы. В литературе эта идея обыгрывалась многократно: от Галатеи
Пигмалиона до Буратино папы Карло. Однако родоначальником
искусственного интеллекта считается средневековый испанский философ,
математик и поэт Р. Луллий (ок.1235-ок.1315), который в XIV в. пытался
создать машину для решения различных задач на основе всеобщей
классификации понятий.
В XVIII в. Г. Лейбниц (1646 - 1716) и Р. Декарт (1596 - 1650) независимо
друг от друга развили эту идею, предложив универсальные языки
классификации всех наук. Эти идеи легли в основу теоретических разработок
в области создания искусственного интеллекта (рис. 2).
Развитие искусственного интеллекта как научного направления стало
возможным только после создания ЭВМ. Это произошло в 40-х гг. XX в. В
это же время Н. Винер (1894 - 1964) создал свои основополагающие работы
по новой науке — кибернетике.
Термин искусственный интеллект (artificial intelligence) предложен в
1956 г. на семинаре с аналогичным названием в Станфордском университете
(США). Семинар был посвящен разработке логических, а не вычислительных
задач. Вскоре после признания искусственного интеллекта самостоятельной
отраслью науки произошло разделение на два основных направления:
нейрокибернетику и кибернетику «черного ящика». И только в настоящее
- 10 -
время стали заметны тенденции к объединению этих частей вновь в единое
целое.
В СССР в 1954 г. в МГУ под руководством профессора А.А.Ляпунова
(1911 - 1973) начал свою работу семинар «Автоматы и мышление» . В этом
семинаре принимали участие крупнейшие физиологи, лингвисты, психологи,
математики. Принято считать, что именно в это время родился
искусственный интеллект в России. Как и за рубежом, выделились
направления нейрокибернетики и кибернетики «черного ящика».
В 1956 -1963 гг. велись интенсивные поиски моделей и алгоритма
человеческого мышления и разработка первых программ. Оказалось, что ни
одна из существующих наук - философия, психология, лингвистика - не
может предложить такого алгоритма. Тогда кибернетики предложили создать
собственные модели. Были созданы и опробованы различные подходы.
Первые исследования в области ИИ связаны с созданием программы для
игры в шахматы, так как считалось, что способность играть в шахматы
является показателем высокого интеллекта. В 1954 году американский
ученый Ньюэлл задумал создать такую программу. Шеннон предложил, а
Тьюринг уточнил метод создания такой программы. Американцы Шоу и
Саймон в содружестве с группой голландских психологов из Амстердама под
руководством де Гроота создали такую программу. Попутно был создан
специальный язык ИПЛ1 (1956), предназначенный для манипулирования
информацией в символьной форме, который явился предшественником языка
Лисп (MacCarthy, 1960).
Однако первой программой искусственного интеллекта была программа
Логик-теоретик, предназначенная для доказательства теорем в исчислении
высказываний (9 августа 1956). Программа для игры в шахматы была создана
в 1957 году (NSS - Newell, Shaw, Simon). Ее структура и структура
программы Логик-теоретик легли в основу создания программы
Универсального Решателя Задач (GPS-General Problem Solving). Эта
программа, анализируя различия между ситуациями и конструируя цели,
хорошо решает головоломки типа «Ханойская башня» или вычисляет
неопределенные интегралы. Программа EPAM (Elementary Perceiving and
Memorizing Program) - элементарная программа для восприятия и
запоминания, задумана Фейгенбаумом. В 1957 году появилась статья
Хомского, одного из основателей компьютерной лингвистики, по
трансформационным грамматикам.
В конце 50-х гг. родилась модель лабиринтного поиска. Этот подход
представляет задачу как некоторый граф, отражающий пространство
состояний
1
, и в этом графе проводится поиск оптимального пути от входных
данных к результирующим. Была проделана большая работа по разработке
этой модели, но в решении практических задач идея большого
распространения не получила.
1
Пространство состояний - это граф, вершины которого соответствуют ситуациям, встречающимся в задаче
(―проблемные ситуации‖), а решение задачи сводится к поиску пути в этом графе.