Часть 1.

Люгер, Дж.Ф.

Искусственный интеллект. Часть 1-2. 2001.

Люгер, Джордж, Ф. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е издание. : Пер. с англ. - М.: Издательский дом "Вильяме", 2003. - 864 с.-С.5-217.

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

Книга будет полезна как опытным специалистам в области искусственного интеллек­та, так и студентам и начинающим ученым.

Оглавление

Предисловие 19

Часть I. Искусственный интеллект: его истоки и проблемы 27

Глава 1. Искусственный интеллект: история развития и области приложения 29

Часть II. Искусственный интеллект как представление и поиск 57

Глава 2. Исчисление предикатов 73

Глава 3. Структуры и стратегии поиска в пространстве состояний 107

Глава 4. Эвристический поиск 149

Глава 5. Управление поиском и его реализация в пространстве состояний 185

Часть III. Представление и разум в ракурсе искусственного

интеллекта 219

Глава 6. Представление знаний 225

Глава 7. Сильные методы решения задач 273

Глава 8. Рассуждения в условиях неопределенности 325

Часть IV. Машинное обучение 369

Глава 9. Машинное обучение, основанное на символьном представлении

информации 371

Глава 10. Машинное обучение на основе связей 435

Глава 11. Машинное обучение на основе социальных и эмерджентных принципов 483

Часть V. Дополнительные вопросы решения задач

искусственного интеллекта 519

Глава 12. Автоматические рассуждения 521

Глава 13. Понимание естественного языка 561

Часть VI. Языки и технологии программирования для

искусственного интеллекта 603

Глава 14. Введение в PROLOG 609

Глава 15. Введение в LISP 685

Часть VII. Эпилог 777

Глава 16. Искусственный интеллект как эмпирическая проблема 779

Библиография 809

Алфавитный указатель авторов 841

Предметный указатель 848

Содержание

Предисловие 19

Добро пожаловать в четвертое издание! 19

Что нового в этом издании 21

Содержание книги 22

Использование книги 24

Дополнительный материал, доступный через Internet 25

Благодарности 25

Часть I. Искусственный интеллект: его истоки и проблемы 27

Попытка дать определение искусственному интеллекту 27

Глава 1. Искусственный интеллект: история развития и области приложения 29

1.1. Отношение к интеллекту, знанию и человеческому мастерству 29

Историческая подоплека 30

Развитие логики 32

Тест Тьюринга 35

Биологические и социальные модели интеллекта: агенты 38

1.2. Обзор прикладных областей искусственного интеллекта 42

Ведение игр 43

Автоматические рассуждения и доказательство теорем 43

Экспертные системы 44

Понимание естественных языков и семантическое моделирование 46

Моделирование работы человеческого интеллекта 47

Планирование и робототехника 48

Языки и среды ИИ 49

Машинное обучение 50

Альтернативные представления: нейронные сети и генетические алгоритмы 51

1.2.10. Искусственный интеллект и философия 52

Искусственный интеллект - заключительные замечания 53

Резюме и дополнительная литература 54

Упражнения 55

Часть П. Искусственный интеллект как представление и поиск 57

Введение в представление знаний 58

Обработка знаний, выраженных в качественной форме 61

Логическое получение новых знаний из набора фактов и правил 62

Отображение общих принципов наряду с конкретными ситуациями 63

Передача сложных семантических значений 63

Рассуждения на метауровне 65

Решение задачи методом поиска 66

Альтернативные схемы представления 70

Глава 2. Исчисление предикатов 73

Введение 73

Исчисление высказываний 7 3

Символы и предложения 73

Семантика исчисления высказываний 75

2.2. Основы исчисления предикатов 77

Синтаксис предикатов и предложений 78

Семантика исчисления предикатов 83

Значение семантики на примере "мира блоков" 87

2.3. Правила вывода в исчислении предикатов 89

Правила вывода 89

Унификация 92

Пример унификации 96

Приложение: финансовый советник на основе логики 100

Резюме и дополнительная литература 103

Упражнения 104

Глава 3. Структуры и стратегии поиска в пространстве состояний 107

3.0. Введение 107

З.1.Теория графов ПО

Структуры данных для поиска в пространстве состояний 110

Представление задачи в пространстве состояний 112

3.2. Стратегии поиска в пространстве состояний 118

Поиск на основе данных и от цели 118

Реализация поиска на графах 121

Поиск в глубину и в ширину 124

Поиск в глубину с итерационным заглублением 131

3.3. Представление рассуждений в пространстве состояний на основе

исчисления предикатов 132

Описание пространства состояний логической системы 132

Графы И/ИЛИ 133

Примеры и приложения 135

Резюме и дополнительная литература 145

Упражнения 146

Глава 4. Эвристический поиск 149

Введение 149

Алгоритм эвристического поиска 153

"Жадный" алгоритм поиска 153

Функции эвристической оценки состояний 156

Эвристический поиск и экспертные системы 163

4.2.Допустимость, монотонность и информированность 164

Мера допустимости 165

Монотонность 166

Информированные эвристики 167

4.3. Использование эвристик в играх 169

Процедура минимакса на графах, допускающих полный перебор 169

Минимакс при фиксированной глубине поиска 171

Процедура альфа-бета-усечения 175

Проблемы сложности 178

Резюме и дополнительная литература 181

Упражнения 181

Глава 5. Управление поиском и его реализация в пространстве состояний 185

Введение 185

Рекурсивный поиск 186

Рекурсия 186

Рекурсивный поиск 187

5.2. Поиск по образцу 190

Пример рекурсивного поиска: вариант задачи хода конем 191

Усовершенствование алгоритма поиска по образцу 194

5.3. Продукционные системы 196

Определение и история развития 196

Примеры продукционных систем 200

Управление поиском в продукционных системах 205

Преимущества продукционных систем для ИИ 211

Архитектура "классной доски" 212

Резюме и дополнительная литература 215

Упражнения 216

Часть III. Представление и разум в ракурсе искусственного

интеллекта 219

Представление и интеллект 219

Глава 6. Представление знаний 225

Вопросы представления знаний 225

Краткая история схем представления ИИ 226

Ассоционистские теории смысла 226

Ранние работы в области семантических сетей 230

Стандартизация сетевых отношений 232

Сценарии 237

Фреймы 241

6.2. Концептуальные графы: сетевой язык 245

Введение в теорию концептуальных графов 245

Типы, экземпляры и имена 246

Иерархия типов 249

Обобщение и специализация 250

Пропозициональные узлы 253

Концептуальные графы и логика 253

6.3.Альтернативы явному представлению 255

Гипотезы Брукса и категориальная архитектура 256

Архитектура Copycat 259

6.4. Агентно-ориентированное и распределенное решение проблем 261

Агентно-ориентированное решение задач: определение 262

Примеры и проблемы агентно-ориентированной парадигмы 264

Резюме и дополнительная литература 266

Упражнения 269

Глава 7. Сильные методы решения задач 273

Введение 273

Обзор технологии экспертных систем 275

Разработка экспертных систем, основанных на правилах 275

Выбор задачи и процесс инженерии знаний 276

Концептуальные модели и их роль в приобретении знаний 279

7.2. Экспертные системы, основанные на правилах 282

Продукционная система и решение задач на основе цели 282

Объяснения и прозрачность при рассуждениях на основе цели 286

Использование продукционной системы для рассуждений

на основе данных 287

7.2.4. Эвристики и управление в экспертных системах 290

7.3.Рассуждения на основе моделей, на базе опыта и гибридные системы 292

Введение в рассуждения на основе модели 292

Рассуждения на основе моделей: пример NASA 296

Введение в рассуждения на основе опыта 299

Гибридные системы: достоинства и недостатки систем

с сильными методами 303

7.4. Планирование 307

Введение 307

Использование макросов планирования: STRIPS 311

Адаптивное планирование 316

Планирование: пример NASA 318

Резюме и дополнительная литература 321

Упражнения 322

Глава 8. Рассуждения в условиях неопределенности 325

Введение 325

Абдуктивный вывод, основанный на логике 327

Логика немонотонных рассуждений 327

Системы поддержки истинности 331

Логики, основанные на минимальных моделях 336

Множественное покрытие и логическая абдукция 338

8.2. Абдукция: альтернативы логическому подходу 341

Неточный вывод на основе фактора уверенности 342

Рассуждения с нечеткими множествами 344

Теория доказательства Демпстера-Шафера 350

8.3. Стохастический подход к описанию неопределенности 354

Байесовские рассуждения 355

Байесовские сети доверия 359

Резюме и дополнительная литература 365

Упражнения 367

Часть IV. Машинное обучение 369

Символьное, нейросетевое и эмерджентное обучение 369

Глава 9. Машинное обучение, основанное на символьном представлении

информации 371

Введение 371

Символьное обучение 374

Поиск в пространстве версий 380

Операция обобщения и пространство понятий 380

Алгоритм исключения кандидата 381

Программа LEX: индуктивное изучение эвристик поиска 388

Обсуждение алгоритма исключения кандидата 391

9.3. Индуктивный алгоритм построения дерева решений ID3 392

Построение дерева решений сверху вниз 394

Выбор свойств на основе теории информации 396

Анализ алгоритма ID3 398

Вопросы обработки данных для построения дерева решений 399

9.4. Индуктивный порог и возможности обучения 400

Индуктивный порог 400

Теория изучаемости 403

9.5. Знания и обучение 405

Алгоритм Meta-DENDRAL 406

Обучение на основе объяснения 407

Алгоритм EBL и обучение на уровне знаний 411

Обоснование по аналогии 412

9.6. Обучение без учителя 415

Научная деятельность и обучение без учителя 415

Концептуальная кластеризация 417

Программа СОВ-WEB и структурные таксономические знания 419

9.7. Обучение с подкреплением 424

Компоненты обучения с подкреплением 425

Пример: снова "крестики-нолики" 427

Алгоритмы вывода и их применение к обучению с подкреплением 429

Резюме и ссылки 431

Упражнения 432

Глава 10. Машинное обучение на основе связей 435

Введение 435

Основы теории сетей связей 437

10.1.1. Ранняя история 437

Обучение персептрона 439

Алгоритм обучения персептрона 439

Пример: использование персешронной сети для классификации образов 442

Обобщенное дельта-правило 445

10.3. Обучение по методу обратного распространения 448

Вывод алгоритма обратного распространения 448

Пример применения метода обратного распространения ошибки:

система NETtalk 452

10.3.3. Применение метода обратного распространения для решения задачи

"исключающего ИЛИ" 454

10.4. Конкурентное обучение 455

Алгоритм обучения "победитель забирает все" для задачи классификации 455

Сеть Кохонена для изучения прототипов 457

Нейроны Гроссберга и сети встречного распространения 459

10.5. Синхронное обучение Хебба 462

Введение 462

Пример алгоритма обучения Хебба без учителя 463

Обучение Хебба с учителем 466

Ассоциативная память и линейный ассоциатор 467

10.6. Аттракторные сети (сети "ассоциативной памяти") 471

Введение 471

Двунаправленная ассоциативная память 472

Примеры обработки данных в сети ДАП 475

Автоассоциативная память и сети Хопфилда 477

Резюме и дополнительная литература 481

Упражнения 482

Глава 11. Машинное обучение на основе социальных и эмерджентных

принципов 483

Социальные и эмерджентные модели обучения 483

Генетические алгоритмы 485

11.1.3. Два примера: описание задачи в конъюнктивной нормальной

форме и задача коммивояжера 488

11.1.4. Обсуждение генетического алгоритма 491

11.2. Системы классификации и генетическое программирование 495

Системы классификации 495

Программирование с использованием генетических операторов 500

11.3. Искусственная жизнь и эмерджентное обучение 505

Игра "Жизнь" 506

Эволюционное программирование 509

Пример эмерджентности 511

Резюме и дополнительная литература 515

Упражнения 516

Часть V. Дополнительные вопросы решения задач

искусственного интеллекта 519

Автоматические рассуждения и естественный язык 519

Глава 12. Автоматические рассуждения 521

Введение в слабые методы доказательства теорем 521

Система решения общих задач и таблицы отличий 522

Доказательство теорем методом резолюции 528

12.2.1. Введение 528

Построение дизъюнктивной формы для опровержения разрешения 530

Процедура доказательства на основе бинарной резолюции 533

Стратегии и методы упрощения резолюции 538

Извлечение ответов в процессе опровержения 543

12.3. Язык PROLOG и автоматические рассуждения 546

Введение 546

Логическое программирование и язык PROLOG 547

12.4. Дополнительные вопросы автоматических рассуждений 552

Единое представление для реализации слабых методов решения 552

Альтернативные правила вывода 555

Стратегии поиска и их использование 557

Резюме и дополнительная литература 558

Упражнения . 559

Глава 13. Понимание естественного языка 561

Проблема понимания естественного языка 561

Разбор языка: символьный анализ 564

Введение 564

Стадии анализа языка 565

13.2. Синтаксический анализ 567

Спецификация и синтаксический анализ с использованием

контекстно-свободных грамматик 567

Анализаторы на основе сети переходов 569

Иерархия Хомского и контекстно-зависимые грамматики 573

13.3. Синтаксис и знания в ATN-анализаторах 576

Анализаторы на основе расширенных сетей переходов 576

Объединение знаний о синтаксисе и семантике 580

13.4. Стохастический подход к анализу языка 585

Введение 585

Подход на основе марковских моделей 586

Подход на основе дерева решений 588

Грамматический анализ и другие приложения стохастического подхода 590

13.5. Приложения задачи анализа естественного языка 592

Обучение и ответы на вопросы 592

Интерфейс для базы данных 592

Извлечение информации и системы автоматического

резюмирования для Web 596

13.5.4. Использование алгоритмов обучения для обобщения извлеченной

информации 598

Резюме и дополнительная литература 598

Упражнения 600

Часть VI. Языки и технологии программирования

для искусственного интеллекта 603

Обзор языков PROLOG и LISP 606

PROLOG 606

LISP 607

Выбор языка реализации 608

Глава14.Введение в PROLOG 609

Введение 609

Синтаксис для программирования логики предикатов 610

Представление фактов и правил 610

Создание, изменение и мониторинг среды PROLOG 614

Списки и рекурсия в языке PROLOG 615

Рекурсивный поиск в языке PROLOG 618

Использование оператора отсечения для управления поиском

в языке PROLOG 620

14.2. Абстрактные типы данных в PROLOG 622

Стек 622

Очередь 624

Приоритетная очередь 624

Множество 625

Пример продукционной системы на языке PROLOG 626

Разработка альтернативных стратегий поиска 631

Поиск в глубину с использованием списка closed 631

Поиск в ширину в языке PROLOG 633

Реализация "жадного" алгоритма поиска на языке PROLOG 634

Реализация планировщика на языке PROLOG 636

Метапредикаты, типы и подстановки унификации в языке PROLOG 639

Металогические предикаты 639

Типы данных в языке PROLOG 640

Унификация, механизм проверки соответствия предикатов и оценка 643

14.7. Метаинтерпретаторы в языке PROLOG 646

Введение в метаинтерпретаторы: PROLOG в языке PROLOG 646

Оболочка для экспертной системы на основе правил 649

Семантические сети в языке PROLOG 657

Фреймы и схемы в языке PROLOG 659

14.8. Алгоритмы обучения в PROLOG 661

Поиск в пространстве версий языка PROLOG 661

Алгоритм исключения кандидата 666

Реализация обучения на основе пояснения на языке PROLOG 668

14.9. Обработка естественного языка на PROLOG 671

Семантические представления для обработки естественного языка 671

Рекурсивный анализатор на языке PROLOG 672

Рекурсивный анализатор на основе семантических сетей 675

Резюме и дополнительная литература 678

Упражнения 680

Глава 15. Введение в LISP 685

Введение 685

LISP: краткий обзор 686

Символьные выражения как синтаксическая основа LISP 686

Управление оцениванием в LISP: функции quote и eval 689

Программирование на LISP: создание новых функций 690

Управление программой в LISP: условия и предикаты 69

Функции, списки и символьные вычисления 694

Списки как рекурсивные структуры 696

Вложенные списки, структуры и рекурсия car-cdr 698

Связывание переменных с помощью функции set 701

Определение локальных переменных с помощью функции let 703

15.1.10. Типы данных в Common LISP 705

15.2. Поиск в LISP: функциональный подход к решению задачи переправы

человека, волка, козы и капусты 706

15.3. Функции и абстракции высшего порядка 711

Отображения и фильтры 711

Функциональные аргументы и лямбда-выражения 713

15.4. Стратегии поиска в LISP 714

Поиске ширину и в глубину 714

"Жадный" алгоритм поиска 717

Проверка соответствия шаблонам LISP 718

Рекурсивная функция унификации 720

Интерпретаторы и внедренные языки 724

Логическое программирование на языке LISP 727

Простой язык логического программирования 727

Потоки и их обработка 729

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

на основе потоков 731

15.9. Потоки и оценивание с задержкой 736

15.10. Оболочка экспертной системы на LISP 739

Реализация факторов достоверности 740

Архитектура оболочки lisp-shell 741

Классификация с использованием оболочки lisp-shell 744

Семантические сети и наследование в LISP 746

Объектно-ориентированное программирование с использованием CLOS 749

Определение классов и экземпляров в CLOS 751

Определение родовых функций и методов 753

Наследование в CLOS 755

Пример: моделирование термостата 756

15.13. Обучение в LISP: алгоритм ID3 761

Определение структур с помощью функции defstruct 761

Алгоритм ЮЗ 767

Резюме и дополнительная литература 772

Упражнения 773

Часть VII. Эпилог 777

Рассуждения о природе интеллекта 777

Глава 16. Искусственный интеллект как эмпирическая проблема 779

Введение 779

Искусственный интеллект: пересмотренное определение 781

Интеллект и гипотеза о физической символьной системе 781

Коннцкционистские, или нейросетевые, вычислительные системы 786

16.1.3. Агенты, интеллект и эволюция 789

16.2. Теория интеллектуальных систем 792

Ограничения психологии 793

Вопросы эпистемологии 795

Внедренный исполнитель и экзистенциальный разум 801

Искусственный интеллект: текущие задачи и будущие направления 803

Резюме и дополнительная литература 807

Библиография 80

Моей жене, Кэтлин, и нашим детям - Саре, Дэвиду и Питеру.

Si quid est in me ingenii, judices... Цицерон (Cicero)

— Джордж Люгер (George Luger)

Предисловие

Чтобы научиться что-то делать, надо делать это.

— Аристотель (Aristotle), Этика

—

Добро пожаловать в четвертое издание!

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

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

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

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

19

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

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

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

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

20

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

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

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

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

Что нового в этом издании

Я, Джордж Люгер (George Luger), - единственный автор четвертого издания. Несмотря на то что интересы Билла Стабблефилда (Bill Stubblefield) сместились в сторону новых областей компьютерных наук, его след останется и в настоящем, и в последующих изданиях книги. На самом деле эта книга является результатом моей работы в качестве профессора компьютерных наук в университете Нью-Мексико и труда моих коллег, аспирантов и дру­зей - членов сообщества специалистов в области искусственного интеллекта, а также мно­гих читателей, направивших по электронной почте свои комментарии, пожелания и уточ­нения. Данная книга продолжает традиции предыдущих изданий, поэтому, чтобы отразить коллективный вклад в ее написание, при изложении материала я буду по-прежнему упот­реблять местоимение "мы". Отдельные слова благодарности за участие в подготовке чет­вертого издания приводятся в соответствующем разделе этого предисловия.

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

21

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

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

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

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

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

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

Содержание книги

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

В главах 2, 3,4 и 5 (часть П) описаны средства решения задач ИИ. К ним относятся язык теории предикатов, предназначенный для описания основных свойств предметной области (глава 2), методы поиска, применяемые для рассуждения об этих описаниях (глава 3), а также алгоритмы и структуры данных, используемые для реализации этого поиска. В главах 4 и 5 обсуждается важная роль эвристик в фокусировке и ограничении пространства поиска. Представлено множество архитектур, предназначенных для построения алгоритмов поиска, вклю­чая методологию "классной доски" и продукционные системы.

22

Главы 6, 7 и 8 составляют третью часть книги. В них описаны представления для задач искусственного интеллекта и методы решения задач, интенсивно использующих зна­ния. В главе 6 рассматривается эволюция схем представлений для ИИ. Сначала обсуж­даются семантические сети и расширение этой модели на теорию концептуальной зави­симости, фреймы и сценарии. Затем глубоко анализируется конкретный формализм - концептуальные графы. Основное внимание уделяется вопросам образования понятий в процессе представления знаний и решению этих вопросов в современном языке представления. В главе 13 показано, как концептуальные графы можно использовать для реа­лизации интерфейса с базой данных, работающего на основе естественного языка. В за­ключении главы 6 рассмотрены более современные подходы к представлению, включая агентно-ориентированные архитектуры и систему Copycat.

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

В главе 8 приводятся модели рассуждений в условиях неопределенности и методы использования ненадежной информации. Здесь обсуждаются байесовские модели, сети доверия (belief network), модель Демпстера-Шафера и неточный вывод с учетом фактора уверенности, применяемые для рассуждения в условиях неопределенности. Описаны приемы поддержания истинности, рассуждения на основе минимальных моделей и логической абдукции, а также алгоритм дерева клик для байесовских сетей доверия.

В части IV (главы 9-11) подробно изложены вопросы машинного обучения. В главе 9 детально изучаются алгоритмы символьного обучения - обширной области исследований, связанной с решением множества различных задач. Эти алгоритмы различаются по своему назначению, используемым обучающим данным, стратегиям обучения и представлениям знаний. К символьным алгоритмам обучения относятся индукция, концепту­альное обучение, поиск в пространстве версий и ID3. Подчеркивается роль индуктивного порога, обобщения на основе реальных данных и эффективного использования знаний при обучении на единственном примере на основе объяснения. Изучение категорий и кластеризация понятий представлены в ракурсе обучения без учителя. Главу завершает раздел, посвященный обучению с подкреплением, - способности интегрировать обрат­ную связь от внешней среды и политику принятия новых решений.

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

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

23

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

В части V (главы 12 и 13) продолжается представление важных областей применения технологий ИИ. Одной из старейших областей является автоматическое доказательство теорем, которое зачастую называют автоматическими рассуждениями. В главе 12 описываются первые программы, реализующие этот подход, включая Logic Theorist и Gen­eral Problem Solver. В этой главе основное внимание уделяется разрешающим процеду­рам доказательства теорем, а особенно резолюции на основе опровержения. Рассмотре­ны также более сложные методы вывода на основе гиперрезолюции и парамодуляции. В заключении интерпретатор PROLOG описан как система вывода на основе хорновских выражений и резолюции, а вычисления на PROLOG - как пример парадигмы логиче­ского программирования.

Глава 13 посвящена проблеме понимания естественного языка. Традиционный подход к пониманию языка, проиллюстрированный с использованием многих описанных в главе 6 семантических структур, в этом издании дополнен описанием стохастического подхода. Здесь рассмотрены марковские модели, CART-деревья, метод взаимной кластеризации информации и статистического грамматического разбора. В заключении главы приводится несколько примеров, включая приложения по восполнению текста и методы реферирования текстов для использования в WWW.

В части VI описаны языки LISP и PROLOG. В главе 14 рассматривается PROLOG, а в главе 15 - LISP. Эти языки представлены как средства решения задач искусственного интеллекта на основе изложенных в предыдущих главах методов поиска, включая алгоритмы поиска в ширину, глубину и "жадный" алгоритм. Реализация этих методов поиска проблемно-независима, поэтому ее можно применять для создания оболочек поиска в экспертных системах на основе правил построения семантических сетей, систем пони­мания естественного языка и обучения.

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

Использование книги

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

Предполагается, что студенты уже прослушали курсы дискретной математики, включая теорию предикатов и теорию графов. Если это не так, то при изучении начальных разделов (2.1 и 3.1) необходимо уделить этим теориям больше внимания. Надеемся так­же, что студенты изучили курс по структурам данных, в том числе деревьям, графам, ме­тодам рекурсивного поиска с помощью стеков, очередей и приоритетных очередей. Если это не так, то обратите особое внимание на начальные разделы глав 3, 4 и 5.

24

В семестровом курсе мы кратко останавливаемся на первых двух частях книги. После такой подготовки студенты готовы к восприятию материала части III. Затем мы изучаем PROLOG и LISP (часть VI) и требуем от студентов построения различных представлений и реализации стратегий поиска, описанных в первых главах. Один из языков, к примеру PROLOG, можно ввести в первой части курса, а затем использовать его при изучении структур данных и алгоритмов поиска. По нашему мнению, полезным средством построения систем решения задач на основе правил и знаний являются метаинтерпретаторы, пред­ставленные в главе, посвященной обработке естественного языка. PROLOG, в свою оче­редь, - отличное средство для построения систем понимания естественного языка.

В двухсеместровом курсе имеется возможность рассмотреть области применения ИИ, описанные в частях IV и V. Особенно это касается машинного обучения. Кроме того, студенты реализуют гораздо более серьезные программные проекты. На наш взгляд, во втором семестре очень важно, чтобы студенты познакомились с основными первоисточниками знаний по искусственному интеллекту. Студенты должны понимать, где мы на­ходимся в данный момент, как мы к этому пришли, и представлять себе перспективы развития ИИ. Для этой цели мы используем обзор [Luger, 1995].

Упомянутые в книге алгоритмы написаны на паскалеподобном псевдокоде. При этом используются управляющие структуры языка Паскаль (Pascal) и описания проверок и операций на родном языке. К числу управляющих структур Паскаля мы добавили две новые полезные конструкции. Первая из них - модифицированный оператор case, который не просто сравнивает значение переменной с постоянной меткой, как в обычном Паскале, но и позволяет связывать с каждым элементом произвольную логическую про­верку. Оператор case по порядку выполняет эти проверки до тех пор, пока результат одной из них не примет значение "истина". Тогда выполняется соответствующее дейст­вие. Все остальные действия игнорируются. Читатели, знакомые с языком LISP, сразу же заметят, что этот оператор обладает той же семантикой, что и оператор cond из LISP.

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

Дополнительный материал, доступный через Internet

Представленный в книге код на языках PROLOG и LISP читатели могут получить через Internet. Там же можно найти подробные методические рекомендации по использованию этой книги для преподавателей. Эти файлы находятся по адресу www.booksites .net/luger или на личной странице автора www. сs. uran .edu/-luger/.

Дополнительные материалы и программные средства, в том числе публикуемые издательствами Addison-Wesley и Pearson Education, находятся по адресу www. aw. com/cs/ и www.pearsoneduc .com/computing. Автор с удовольствием ожидает электронных писем читателей по адресу luger@cs. unm. edu.

Благодарности

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

25

которые помогли подготовить эти четыре издания. В их числе Дэннис Бахлер (Dennis Bahler), Скона Бриттэн (Skona Brittain), Филипп Чен (Philip Chan), Питер Колингвуд (Peter Collingwood), Джон Дональд (John Donald), Сара Дуглас (Sarah Douglas), Кристоф ЖиредКарьер (Christophe Giraud-Carrier), Эндрю Косорезов (Andrew Kosoresov), Крис Малкольм (Chris Malcolm), Рэй Муни (Ray Mooney), Брюс Портер (Bruce Porter), Джуд Шавлик (Jude Shavlik), Карл Стерн (Carl Stern), Марко Валторта (Marco Valtorta) и Боб Верофф (Bob Ver-off). Мы также благодарны за многочисленные предложения и комментарии, направляемые непосредственно авторам книги ее читателями по электронной почте.

За помощь в реорганизации материала автор признателен своим аспирантам. Благодаря им была переработана часть III, в которой впервые описана эволюция схем представлений для задач искусственного интеллекта, создан отдельный раздел по машинному обучению, а вопросы понимания естественных языков перенесены в конец книги. Мы благодарны Дану Плессу (Dan Pless) за его вклад в подготовку материала по абдуктивному выводу для главы 8, Карлу Стерну (Carl Stern) за помощь в написании главы 10, посвященной коннекционистскому обучению, Яреду Сайа (Jared Saia) за помощь в описании стохастических моделей для гла­вы 13. "Внешними" рецензентами четвертого издания стали Леон ван дер Торре (Leon van der Torre) и Меди Дастани (Mehdi Dastard) из Нидерландов, а также Леонардо Ботгачи (Leonardo Bottaci) и Джулиан Ричардсон (Julian Richardson) из Великобритании. Среди американских рецензентов следует отметить Марека Перковски (Marek Perkowski) из портлендского университета и Джона Шеппарда (John Sheppard) из университета имени Джона Хопкинса. Барак Пермуттер (Barak Pearmutter) рецензировал главы по машинному обучению. И, наконец, Джо­зеф Льюис (Joseph Lewis), Крис Малколм (Chris Malcolm), Брэнден Мак-Гоннигл (Brendan McGonnigle) и Акаша Танг (Akasha Tang) приняли участие в обсуждении главы 16.

Автор благодарен издательству Academic Press за разрешение на перепечатку большей части материала из главы 10, которая была ранее опубликована в [Luger, 1994]. И, наконец, большое спасибо студентам университета Нью-Мексико, которые более десяти лет изучали эту книгу и описанные в ней программные средства. Они существенно рас­ширили наш горизонт, а также позволили избавиться от опечаток и неточностей.

Спасибо моим друзьям из издательства Addison-Wesley за поддержку при написании книги, особенно Алану Апту (Alan Apt) за помощь в подготовке первого издания, Лизе Моллер (Lisa Moller) и Мэри Тюдор (Mary Tudor) за участие в подготовке второго, Виктории Хендерсон (Victoria Henderson), Луизе Вилсон (Louise Wilson) и Карен Мосман (Karen Mosman) за содействие в работе над третьим, а также Кэйт Мансфилд (Keith Mansfield), Карен Сюзерланд (Karen Sutherland) и Аните Аткинсон (Anite Atkinson) за поддержку этого четвертого издания. Особая благодарность Линде Цицарелле (Linda Ci-carella) из университета Нью-Мексико за помощь в подготовке рисунков.

Спасибо большое Томасу Бэрроу (Thomas Barrow) - всемирно признанному художнику и профессору искусств университета Нью-Мексико, который сделал семь фотогра­фий для этой книги.

Во многих местах мы использовали рисунки и цитаты из работ других авторов. Мы благодарны авторам и издателям за разрешение на использование этого материала.

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

Джордж Люгер 1 июля 2001 года

26

Часть I

Искусственный интеллект: его истоки и проблемы

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

- Мэри Шелли (Mary Shelley), Франкенштейн

Попытка дать определение искусственному интеллекту

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

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

Итак, проблема определения искусственного интеллекта сводится к проблеме определения интеллекта вообще: является ли он чем-то единым, или же этот термин объеди­няет набор разрозненных способностей? В какой мере интеллект можно создать, а в

27

какой он существует априори? Что именно происходит при таком создании? Что такое творчество? Что такое интуиция? Можно ли судить о наличии интеллекта только по наблюдаемому поведению, или же требуется свидетельство наличия некоего скрытого ме­ханизма? Как представляются знания в нервных тканях живых существ, и как можно применить это в проектировании интеллектуальных устройств? Что такое самоанализ и как он связан с разумностью? И, более того, необходимо ли создавать интеллектуальную компьютерную программу по образу и подобию человеческого разума, или же достаточно строго "инженерного" подхода? Возможно ли вообще достичь разумности посредст­вом компьютерной техники, или же сущность интеллекта требует богатства чувств и опыта, присущего лишь биологическим существам?

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

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

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

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

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

28