системы искусственного интеллекты часть1

Министерство образования и науки Российской Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

С. Н. Павлов

СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

Часть 1

Учебное пособие

Томск «Эль Контент»

2011

УДК 004.89(075.8) ББК 32.813я73

П 12

Рецензенты:

Сергеев В. Л., докт. техн. наук, проф. кафедры геологии и разработки нефтяных месторождений Томского политехнического университета;

Кориков А. М., проф., зав. кафедрой автоматизированных систем управления ТУСУРа

Павлов С. Н.

П12 Системы искусственного интеллекта : учеб. пособие. В 2-х частях. /

С.Н. Павлов. — Томск: Эль Контент, 2011. — Ч. 1. — 176 c.

ISBN 978-5-4332-0013-5

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

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

УДК 004.89(075.8) ББК 32.813я73

ISBN 978-5-4332-0013-5 © Павлов С. Н., 2011 © Оформление.

ООО «Эль Контент», 2011

Оглавление

Введение	5
1 Структура исследования в области искусственного
интеллекта	9
1.1 Понятие «искусственный интеллект» . . . . . . . . . . . . . . . . . . . .	9

1.2Этапы развития искусственного интеллекта . . . . . . . . . . . . . . . . 13

1.3Классификация искусственного интеллекта . . . . . . . . . . . . . . . . 19

1.3.1 Нейробионическое направление . . . . . . . . . . . . . . . . . . 22

1.3.2Информационное направление . . . . . . . . . . . . . . . . . . . 26

1.3.3Примеры различных классификаций систем искусственного интеллекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2 Задачи и методы их решения

47

2.1Задачи систем искусственного интеллекта . . . . . . . . . . . . . . . . . 47

2.2 Общие способы решения задач . . . . . . . . . . . . . . . . . . . . . . . 49

2.3Методы решения задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

2.3.1	Поиск решений в одном пространстве . . . . . . . . . . . . . .	53
2.3.2	Поиск в иерархических и альтернативных пространствах . .	66
3 Основные виды логических выводов		71

3.1Дедуктивный вывод и автоматическое доказательство теорем . . . . . 72

3.1.1Рассуждения и принципы дедуктивного вывода . . . . . . . . . 72

3.1.2Методы доказательства в логике . . . . . . . . . . . . . . . . . . 77

3.1.3Представление и решение задач в виде теорем . . . . . . . . . 81

3.1.4Прямой и обратный дедуктивный вывод . . . . . . . . . . . . . 92

3.2 Абдуктивный вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

3.3Индуктивный вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

3.3.1	Виды индукции . . . . . . . . . . . . . . . . . . . . . . . . . . . .	96
3.3.2	Индукция как вывод и индукция как метод . . . . . . . . . . .	99
4 Неопределенность знаний и способы их обработки		105

4.1Виды неопределенности описания задачи . . . . . . . . . . . . . . . . . 105

4.2Особенности данных и знаний . . . . . . . . . . . . . . . . . . . . . . . . 108

4.3Нечеткие знания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 4.3.1 Нечеткие множества . . . . . . . . . . . . . . . . . . . . . . . . . . 126

4.3.2 Нечеткие отношения . . . . . . . . . . . . . . . . . . . . . . . . . 133

4.3.3Элементы теории приближенных рассуждений . . . . . . . . . 136

4.3.4Лингвистическая переменная . . . . . . . . . . . . . . . . . . . . 139

5 Продукционные системы

147

4	Оглавление

5.1Представление продукционных систем . . . . . . . . . . . . . . . . . . . 147

5.2Интерпретатор продукционной системы . . . . . . . . . . . . . . . . . . 154

5.3Эффективность поиска решений в продукционных системах . . . . . 161

5.4Механизм разрешения конфликтов . . . . . . . . . . . . . . . . . . . . . 165

5.5 Продукционные системы в приложениях . . . . . . . . . . . . . . . . . 168

5.6Объяснение выводов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

5.7 Достоинства и недостатки продукционных систем . . . . . . . . . . . 171

ВВЕДЕНИЕ

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

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

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

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

Дисциплина «Системы искусственного интеллекта» играет фундаментальную роль в подготовке специалистов в области информатики и вычислительной техники. Различные учебные курсы, относящиеся к проблематике искусственного интеллекта (ИИ), включены в учебные планы многих институтов, университетов по рекомендациям международных ассоциаций ACM, AIS, AITP в 1997 г.

6

Введение

Настоящее учебное пособие «Системы искусственного интеллекта» посвящено вопросам организации, проектирования, разработки и применения систем, предназначенных для обработки информации, базирующихся на применении базовых принципов, подходах, методах и стратегиях разработки систем обычного назначения.

В настоящее время имеется достаточно обширная литература по системам искусственного интеллекта и программам в «демонстрационном варианте», т. е. при относительно небольшой базе знаний. Но для настоящей предметной области требуется весь арсенал средств и методов, накопленных за последние 40 лет. Разработка этого учебного пособия и есть попытка представления методов ИИ для серьезных практических областей: информатики, экономики, машинного перевода, распознавания образов и т. д.

Учебное пособие ставит цель: познакомить читателя с принципами создания

ифункционирования систем искусственного интеллекта; приобрести студентами

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

Для изучения учебного пособия «Системы искусственного интеллекта» предполагаются знания по программированию, ЭВМ, высшей математике, дискретной математике, базам данных, теории информации и математической статистике.

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

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

Во втором разделе представлены задачи и общие методы решения хорошо определенных задач.

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

Четвертый раздел посвящен неопределенностям знаний и способам их обработки: виды неопределенности описания задач; особенности данных и знаний

иподходов представления неопределенностей (теорий вероятности, свидетельств, возможности); нечеткие знания (множества, отношения, лингвистические переменные, элементы теории приближенных рассуждений на примерах modus ponens

иmodus tollens).

Впятом разделе представлены продукционные системы логического вывода

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

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

Соглашения, принятые в книге

7

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

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

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

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

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

Учебное пособие в большей степени основано на материалах отечественных

ив меньшей — зарубежных работ, являясь обобщением опыта, накопленного в этой области. Из отечественных работ следует отметить огромный вклад следующих специалистов: Д. А. Поспелова, Т. А. Гавриловой, В. Ф. Хорошевского, Ю. Ю. Тельнова, Э. В. Попова, Д. В. Гаскарова, А. В. Андрейчикова, И. П. Норенкова, В. Л. Стефанюка, Г. В. Рыбиной, В. Н. Вагина, В. Н. Аверина и др.

Взаключение автор благодарит профессора А. М. Корикова за помощь в издании, критику и полезные замечания.

Автор осознает, что объем и качество учебного пособия не могут соответствовать общему стандарту представления о системах искусственного интеллекта

ибудет благодарен читателям за замеченные недостатки.

Соглашения, принятые в книге

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Эта пиктограмма означает определение или новое понятие.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

Введение

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Эта пиктограмма означает теорему. Данный блок состоит из Названия теоремы (Слова Теорема и Номера теоремы) и Текста теоремы.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . Пример . . . . . . . . . . . . . . . . . . . . . . . . .

Эта пиктограмма означает пример. В данном блоке автор может привести практический пример для пояснения и разбора основных моментов, отраженных в теоретическом материале.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . Выводы . . . . . . . . . . . . . . . . . . . . . . . . .

Эта пиктограмма означает выводы. Здесь автор подводит итоги, обобщает изложенный материал или проводит анализ.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Контрольные вопросы и задания к главе

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Литература к главе

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Глава 1

СТРУКТУРА ИССЛЕДОВАНИЯ В ОБЛАСТИ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

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

Слово «интеллект» происходит от латинского слова «intelligentie», которое, в свою очередь, образовалось от глагола «intellgere», означающего способность понимать, определять смысл.

1.1 Понятие «искусственный интеллект»

Несмотря на все попытки дать точное определение понятию «искусственный интеллект» (ИИ), строгого определения до сих пор не существует, да и при появлении новых научных идей оно изменяется. Обозначим хотя бы границы этого понятия. И. Рич определяет ИИ как область исследования, направленную на создание компьютеров, которые выполняют такие функции, которые в настоящий момент человек выполняет лучше [16]. К таким функциям, которые проявляются у человека, относят восприятие, анализ, рассуждение, использование знаний, планирование действий, логический вывод и т. д. Очень близкое определение ИИ дает Дж. Ален: «ИИ — это наука о создании машин, решающих задачи, которые могут решать люди. . . » [15]. Здесь в фокусе ИИ оказываются те задачи, которые успешно решаются человеком и плохо — компьютерами. Эти два определения сопоставляют возможности человека и машин. Еще в 1950 году был предложен эмпирический тест А. Тьюринга для определения уровня интеллектуальности машин. В соответствии с тестом эксперт мог вступать в диалог либо с компьютером, либо с человеком. Тьюринг считал поведение компьютера интеллектуальным, если в диалоге

10	Глава 1. Структура исследования в области ИИ

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

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

1)Способность успешно реагировать на любую, особенно новую ситуацию путем надлежащих корректировок поведения.

2)Способность понимать взаимосвязи между фактами действительности для выработки действий, ведущих к достижению поставленной цели.

3)Разработка новых моделей и методов решения задач, традиционно считавшихся интеллектуальными и не поддававшихся ранее формализации и автоматизации.

4)Разработка новых технологий программирования и переход на новые архитектуры ЭВМ.

5)Способность решать прикладные задачи, для которых ранее создаваемые системы были непригодны.

6)Область компьютерной науки, занимающейся автоматизацией разумного поведения.

7)Формализованные методы, позволяющие решать с помощью компьютера задачи управления не хуже, чем естественный интеллект.

8)Новые идеи, подходы решения задач на ЭВМ — новая технология программирования, переход на параллельные машины.

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

10)Ветвь информатики, которая связана с автоматизацией интеллектуального поведения.

11)Наука о вычислениях, которые делают возможными восприятие, логический вывод и действие.

12)Информационная технология, связанная с процессами логического вывода, обучения и восприятия.

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

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