Рассел С., Норвиг П. Искусственный интеллект. Современный подход

2-е изд. — М.: Вильямс, 2007. — 1410 с. — ISBN 5-8459-0887-2, 0-13-790395-2, 978-5-8459-0887-2.В книге представлены все современные достижения и изложены идеи, которые были сформулированы в исследованиях, проводившихся в течение последних пятидесяти лет, а также собраны на протяжении двух тысячелетий в областях знаний, ставших стимулом к развитию искусственного интеллекта как науки проектирования рациональных агентов. Теоретическое описание иллюстрируется многочисленными алгоритмами, реализации которых в виде готовых программ на нескольких языках программирования находятся на сопровождающем книгу Web-узле.Книга предназначена для использования в базовом университетском курсе или в последовательности курсов по специальности. Применима в качестве основного справочника для аспирантов, специализирующихся в области искусственного интеллекта, а также будет небезынтересна профессионалам, желающим выйти за пределы избранной ими специальности. Благодаря кристальной ясности и наглядности изложения вполне может быть отнесена к лучшим образцам научно-популярной литературы.Искусственный интеллект
Введение
Общее определение искусственного интеллекта
Проверка того, способен ли компьютер действовать подобно человеку: подход, основанный на использовании теста Тьюринга
Как мыслить по-человечески: подход, основанный на когнитивном моделировании
Как мыслить рационально: подход, основанный на использовании "законов мышления"
Как мыслить рационально: подход, основанный на использовании рационального агента
Предыстория искусственного интеллекта
Философия (период с 428 года до н. э. по настоящее время)
Математика (период примерно с 800 года по настоящее время)
Экономика (период с 1776 года по настоящее время)
Неврология (период с 1861 года по настоящее время)
Психология (период с 1879 года по настоящее время)
Вычислительная техника (период с 1940 года по настоящее время)
Теория управления и кибернетика (период с 1948 года по настоящее время)
Лингвистика (период с 1957 года по настоящее время)
История искусственного интеллекта
Появление предпосылок искусственного интеллекта (период с 1943 года по 1955 год)
Рождение искусственного интеллекта (1956 год)
Ранний энтузиазм, большие ожидания (период с 1952 года по 1969 год)
Столкновение с реальностью (период с 1966 года по 1973 год)
Системы, основанные на знаниях: могут ли они стать ключом к успеху (период с 1969 года по 1979 год)
Превращение искусственного интеллекта в индустрию (период с 1980 года по настоящее время)
Возвращение к нейронным сетям (период с 1986 года по настоящее время)
Превращение искусственного интеллекта в науку (период с 1987 года по настоящее время)
Появление подхода, основанного на использовании интеллектуальных агентов (период с 1995 года по настоящее время)
Современное состояние разработок
Интеллектуальные агенты
Агенты и варианты среды
Качественное поведение: концепция рациональности
Показатели производительности
Рациональность
Всезнание, обучение и автономность
Определение характера среды
Определение проблемной среды
Свойства проблемной среды
Структура агентов
Программы агентов
Простые рефлексные агенты
Рефлексные агенты, основанные на модели
Агенты, основанные на цели
Агенты, основанные на полезности
Обучающиеся агентыРешение проблем
Решение проблем посредством поиска
Агенты, решающие задачи
Хорошо структурированные задачи и решения
Формулировка задачи
Примеры задач
Упрощенные задачи
Реальные задачи
Поиск решений
Измерение производительности решения задачи
Стратегии неинформированного поиска
Поиск в ширину
Поиск в глубину
Поиск с ограничением глубины
Поиск в глубину с итеративным углублением
Двунаправленный поиск
Сравнение стратегий неинформированного поиска
Предотвращение формирования повторяющихся состояний
Поиск с частичной информацией
Проблемы отсутствия датчиков
Проблемы непредвиденных ситуаций
Информированный поиск и исследование пространства состояний
Стратегии информированного (эвристического) поиска
Жадный поиск по первому наилучшему совпадению
Поиск А*: минимизация суммарной оценки стоимости решения
Эвристический поиск с ограничением объема памяти
Обучение лучшим способам поиска
Эвристические функции
Зависимость производительности поиска от точности эвристической функции
Составление допустимых эвристических функций
Изучение эвристических функций на основе опыта
Алгоритмы локального поиска и задачи оптимизации
Поиск с восхождением к вершине
Поиск с эмуляцией отжига
Локальный лучевой поиск
Генетические алгоритмы
Локальный поиск в непрерывных пространствах
Поисковые агенты, действующие в оперативном режиме, и неизвестные варианты среды
Задачи поиска в оперативном режиме
Агенты, выполняющие поиск в оперативном режиме
Локальный поиск в оперативном режиме
Обучение в ходе поиска в оперативном режиме
Задачи удовлетворения ограничений
Задачи удовлетворения ограничений
Применение поиска с возвратами для решения задач CSP
Упорядочение переменных и значений
Распространение информации с помощью ограничений
Интеллектуальный поиск с возвратами: поиск в обратном направлении
Применение локального поиска для решения задач удовлетворения ограничений
Структура задач
Поиск в условиях противодействия
Игры
Принятие оптимальных решений в играх
Оптимальные стратегии
Минимаксный алгоритм
Оптимальные решения в играх с несколькими игроками
Альфа-бета-отсечение
Неидеальные решения, принимаемые в реальном времени
Функции оценки
Прекращение поиска
Игры, которые включают элемент случайности
Оценка позиции в играх с узлами жеребьевки
Сложность оценки ожидаемых минимаксных значений
Карточные игры
Современные игровые программы
Обсуждение изложенных сведенийЗнания и рассуждения
Логические агенты
Агенты, основанные на знаниях
Мир вампуса
Логика
Пропозициональная логика: очень простая логика
Синтаксис
Семантика
Простая база знаний
Логический вывод
Эквивалентность, допустимость и выполнимость
Шаблоны формирования рассуждений в пропозициональной логике
Резолюция
Прямой и обратный логический вывод
Эффективный пропозициональный логический вывод
Полный алгоритм поиска с возвратами
Алгоритмы локального поиска
Трудные задачи определения выполнимости
Агенты, основанные на пропозициональной логике
Поиск ям и вампусов с помощью логического вывода
Слежение за местонахождением и ориентацией
Агенты на основе логических схем
Сопоставление двух описанных типов агентов
Логика первого порядка
Дополнительные сведения о представлении
Синтаксис и семантика логики первого порядка
Модели для логики первого порядка
Символы и интерпретации
Термы
Атомарные высказывания
Сложные высказывания
Кванторы
Равенство
Использование логики первого порядка
Утверждения и запросы в логике первого порядка
Проблемная область родства
Числа, множества и списки
Мир вампуса
Инженерия знаний с применением логики первого порядка
Процесс инженерии знаний
Проблемная область электронных схем
Логический вывод в логике первого порядка
Сравнение методов логического вывода в пропозициональной логикеи логике первого порядка 3
Правила логического вывода для кванторов 3
Приведение к пропозициональному логическому выводу
Унификация и поднятие
Правило вывода в логике первого порядка
Унификация
Хранение и выборка
Прямой логический вывод
Определенные выражения в логике первого порядка
Простой алгоритм прямого логического вывода
Эффективный прямой логический вывод
Обратный логический вывод
Алгоритм обратного логического вывода
Логическое программирование
Эффективная реализация логических программ
Избыточный логический вывод и бесконечные циклы
Логическое программирование в ограничениях
Резолюция
Конъюнктивная нормальная форма для логики первого порядка
Правило логического вывода с помощью резолюции
Примеры доказательств
Полнота резолюции
Учет отношения равенства
Стратегии резолюции
Средства автоматического доказательства теорем
Представление знаний
Онтологическая инженерия
Категории и объекты
Физическая композиция
Меры
Вещества и объекты
Действия, ситуации и события
Онтология ситуационного исчисления
Описание действий в ситуационном исчислении
Решение проблемы представительного окружения
Решение проблемы выводимого окружения
Исчисление времени и событий
Обобщенные события
Процессы
Интервалы
Флюентные высказывания и объекты
Мыслительные события и мыслимые объекты
Формальная теория убеждений
Знания и убеждения
Знания, время и действия
Мир покупок в Internet
Сравнение коммерческих предложений
Системы формирования рассуждений о категориях
Семантические сети
Описательные логики
Формирование рассуждений с использованием информации, заданной по умолчанию
Открытые и закрытые миры
Отрицание как недостижение цели и устойчивая семантика модели
Логика косвенного описания и логика умолчания
Системы поддержки истинностиПланирование
Основы планирования
Задача планирования
Язык задач планирования
Выразительность и расширения языка
Пример: воздушный грузовой транспорт
Пример: задача с запасным колесом
Пример: мир блоков
Планирование с помощью поиска в пространстве состояний
Прямой поиск в пространстве состояний
Обратный поиск в пространстве состояний
Эвристики для поиска в пространстве состояний
Планирование с частичным упорядочением
Пример планирования с частичным упорядочением
Планирование с частичным упорядочением и несвязанными переменными
Эвристики для планирования с частичным упорядочением
Графы планирования
Применение графов планирования для получения эвристической оценки
Алгоритм Graphplan
Завершение работы алгоритма Graphplan
Планирование с помощью пропозициональной логики
Описание задач планирования в пропозициональной логике
Сложности, связанные с использованием пропозициональных кодировок
Анализ различных подходов к планированию
Планирование и осуществление действий в реальном мире
Время, расписания и ресурсы
Составление расписаний с ресурсными ограничениями
Планирование иерархической сети задач
Представление декомпозиций действий
Модификация планировщика для его использования в сочетании с декомпозициями
Обсуждение вопроса
Планирование и осуществление действий в недетерминированных проблемных областях
Условное планирование
Условное планирование в полностью наблюдаемых вариантах среды
Условное планирование в частично наблюдаемых вариантах среды
Контроль выполнения и перепланирование
Непрерывное планирование
Мультиагентное планирование
Кооперация: совместные цели и планы
Многотельное планирование
Механизмы координации
КонкуренцияНеопределенные знания и рассуждения в условиях
Неопределенность
Действия в условиях неопределенности
Учет наличия неопределенных знаний
Неопределенность и рациональные решения
Проект агента, действующего в соответствии с теорией решений
Основная вероятностная система обозначений
Высказывания
Атомарные события
Априорная вероятность
Условная вероятность
Аксиомы вероятностей
Использование аксиом вероятностей
Теоретическое обоснование аксиом вероятностей
Логический вывод с использованием полных совместных распределений
Независимость
Правило Байеса и его использование
Применение правила Байеса: простой случай
Использование правила Байеса: комбинирование свидетельств
Еще одно возвращение в мир вампуса
Вероятностные рассуждения
Представление знаний в неопределенной проблемной области
Семантика байесовских сетей
Представление полного совместного распределения
Отношения условной независимости в байесовских сетях
Эффективное представление распределений условных вероятностей
Точный вероятностный вывод в байесовских сетях
Вероятностный вывод с помощью перебора
Алгоритм устранения переменной
Сложность точного вероятностного вывода
Алгоритмы кластеризации
Приближенный вероятностный вывод в байесовских сетях
Методы непосредственной выборки
Вероятностный вывод по методу моделирования цепи Маркова
Распространение вероятностных методов на представления в логике первого порядка
Другие подходы к формированию рассуждений в условиях неопределенности
Методы на основе правил для формирования рассуждений в условиях неопределенности
Представление незнания: теория Демпстера-Шефера
Представление неосведомленности: нечеткие множества и нечеткая логика
Вероятностные рассуждения во времени
Время и неопределенность
Состояния и наблюдения
Стационарные процессы и марковское предположение
Вероятностный вывод во временных моделях
Фильтрация и предсказание
Сглаживание
Поиск наиболее вероятной последовательности
Скрытые марковские модели
Упрощенные матричные алгоритмы
Фильтры Калмана
Обновление гауссовых распределений
Простой одномерный пример
Общий случай
Области применения калмановской фильтрации
Динамические байесовские сети
Процедура создания сетей DBN
Точный вероятностный вывод в сетях DBN
Приближенный вероятностный вывод в сетях DBN
Распознавание речи
Звуки речи
Слова
Предложения
Разработка устройства распознавания речи
Принятие простых решений
Совместный учет убеждений и желаний в условиях неопределенности
Основы теории полезности
Ограничения, налагаемые на рациональные предпочтения
В начале была Полезность
Функции полезности
Полезность денег
Шкалы полезности и оценка полезности
Многоатрибутные функции полезности
Доминирование
Структура предпочтений и многоатрибутная полезность
Сети принятия решений
Способы представления задачи принятия решений с помощью сети
принятия решений
Вычисления с помощью сетей принятия решений
Стоимость информации
Простой пример
Общая формула
Свойства показателей стоимости информации
Реализация агента, действующего на основе сбора информации
Экспертные системы, основанные на использовании теории принятия решений
Принятие сложных решений
Задачи последовательного принятия решений
Пример
Оптимальность в задачах последовательного принятия решений
Итерация по значениям
Полезности состояний
Алгоритм итерации по значениям
Сходимость итерации по значениям
Итерация по стратегиям
Марковские процессы принятия решений в частично наблюдаемых вариантах среды
Агенты, действующие на основе теории решений
Принятие решений при наличии нескольких агентов: теория игр
Проектирование механизмаОбучение
Обучение на основе наблюдений
Формы обучения
Индуктивное обучение
Формирование деревьев решений на основе обучения
Деревья решений, рассматриваемые как производительные элементы
Выразительность деревьев решений
Индуктивный вывод деревьев решений на основе примеров
Выбор проверок атрибутов
Оценка производительности обучающего алгоритма
Шум и чрезмерно тщательная подгонка
Расширение области применения деревьев решений
Обучение ансамбля
Принципы функционирования алгоритмов обучения: теория вычислительного обучения
Оценка количества необходимых примеров
Обучение списков решений
Обсуждение полученных результатов
Применение знаний в обучении
Логическая формулировка задачи обучения
Примеры и гипотезы
Поиск текущей наилучшей гипотезы
Поиск на основе оценки наименьшего вклада
Применение знаний в обучении
Некоторые простые примеры
Некоторые общие схемы
Обучение на основе объяснения
Извлечение общих правил из примеров
Повышение эффективности правила
Обучение с использованием информации о релевантности
Определение пространства гипотез
Обучение и использование информации о релевантности
Индуктивное логическое программирование
Практический пример
Нисходящие методы индуктивного обучения
Индуктивное обучение с помощью обратной дедукции
Совершение открытий с помощью индуктивного логического
программированияСтатистические методы обучения
Статистическое обучение
Обучение с помощью полных данных
Обучение параметрам с помощью метода максимального правдоподобия: дискретные модели
Наивные байесовские модели
Обучение параметрам с максимальным правдоподобием: непрерывные модели
Обучение байесовским параметрам
Определение путем обучения структур байесовских сетей
Обучение с помощью скрытых переменных: алгоритм ЕМ
Неконтролируемая кластеризация: определение в процессе обучения смешанных гауссовых распределений
Обучение байесовских сетей со скрытыми переменными
Обучение скрытых марковских моделей
Общая форма алгоритма ЕМ
Определение с помощью обучения структур байесовских сетей со скрытыми переменными
Обучение на основе экземпляра
Модели ближайшего соседа
Ядерные модели
Нейронные сети
Элементы в нейронных сетях
Структуры сетей
Однослойные нейронные сети с прямым распространением (персептроны)
Многослойные нейронные сети с прямым распространением
Определение в процессе обучения структур нейронных сетей
Ядерные машины
Практический пример: распознавание рукописных цифрОбучение с подкреплением
Введение
Пассивное обучение с подкреплением
Непосредственная оценка полезности
Адаптивное динамическое программирование
Обучение с учетом временной разницы
Активное обучение с подкреплением
Исследование среды
Определение функции "действие—стоимость" с помощью обучения
Обобщение в обучении с подкреплением
Приложения методов обучения к ведению игр
Применение к управлению роботами
Поиск стратегииОбщение, восприятие и осуществление действий
Общение
Общение как действие
Основные понятия языка
Составные этапы общения
Формальная грамматика для подмножества английского языка
Словарь языка
Грамматика языка
Синтаксический анализ (синтаксический разбор)
Эффективный синтаксический анализ
Расширенные грамматики
Субкатегоризация глагола
Порождающая мощь расширенных грамматик
Семантическая интерпретация
Семантика небольшой части английского языка
Время события и времена глаголов
Введение кванторов
Прагматическая интерпретация
Применение грамматик DCG для производства языковых конструкций
Неоднозначность и устранение неоднозначности
Устранение неоднозначности
Понимание речи
Разрешение ссылок
Структура связной речи
Индуктивный вывод грамматики
Вероятностная обработка лингвистической информации
Вероятностные языковые модели
Вероятностные контекстно-свободные грамматики
Определение с помощью обучения вероятностей для грамматики PCFG
Определение с помощью обучения структуры правил для грамматики PCFG
Информационный поиск
Сравнительный анализ систем информационного поиска
Совершенствование информационного поиска
Способы представления результирующих наборов
Создание систем информационного поиска
Извлечение информации
Машинный перевод
Системы машинного перевода
Статистический машинный перевод
Определение с помощью обучения вероятностей для машинного перевода
Восприятие
Введение
Формирование изображения
Получение изображения без линз — камера-обскура
Системы линз
Свет: фотометрия формирования изображения
Цвет — спектрофотометрия формирования изображения
Операции, выполняемые на первом этапе обработки изображения
Обнаружение краев
Сегментация изображения
Извлечение трехмерной информации
Движение
Бинокулярные стереоданные
Градиенты текстуры
Затенение
Контуры
Распознавание объектов
Распознавание с учетом яркости
Распознавание с учетом характеристик
Оценка позы
Использование системы машинного зрения для манипулирования и передвижения
Робототехника
Введение
Аппаратное обеспечение роботов
Датчики
Исполнительные механизмы
Восприятие, осуществляемое роботами
Локализация
Составление карты
Другие типы восприятия
Планирование движений
Пространство конфигураций
Методы декомпозиции ячеек
Методы скелетирования
Планирование движений в условиях неопределенности
Надежные методы
Осуществление движений
Динамика и управление
Управление на основе поля потенциалов
Реактивное управление
Архитектуры робототехнического программного обеспечения
Обобщающая архитектура
Трехуровневая архитектура
Робототехнические языки программирования
Прикладные областиЗаключение
Философские основания
Слабый искусственный интеллект: могут ли машины действовать интеллектуально?
Довод, исходящий из неспособности
Возражения, основанные на принципах математики
Довод, исходящий из неформализуемости
Сильный искусственный интеллект: могут ли машины по-настоящему мыслить?
Проблема разума и тела
Эксперимент "мозг в колбе"
Эксперимент с протезом мозга
Китайская комната
Этические и моральные последствия разработки искусственного интеллекта
Настоящее и будущее искусственного интеллекта
Компоненты агента
Архитектуры агентов
Оценка правильности выбранного направления
Перспективы развития искусственного интеллекта
Математические основы
Анализ сложности и система обозначений 0()
Асимптотический анализ
Изначально сложные и недетерминированные полиномиальные задачи
Векторы, матрицы и линейная алгебра
Распределения вероятностей
Общие сведения о языках и алгоритмах, используемых в книге
Определение языков с помощью формы Бэкуса-Наура
Описание алгоритмов с помощью псевдокода
Оперативная помощь