- •Введение
- •Глава 1. Ведение в системы искусственного интеллекта
- •1.1. Архитектура систем искусственного интеллекта
- •1.2. База знаний и данных
- •1.1.1 Понятие модели
- •1.1.2. Логические модели
- •1.1.3 Модели знаний на основе продукций
- •1.1.4 Фреймовая модель знаний
- •1.1.5 Семантические сети
- •1.3. Машина вывода
- •1.3.1. Понятие формальной системы
- •Примеры стратегии вывода
- •Как функционирует машина вывода
- •1.4. Извлечение знаний и обучение
- •1.4.1. Извлечение знаний от многих экспертов
- •1.4.2 Проблема непротиворечивости формализованной базы знаний
- •1.5. Обучение системы
- •1.6. Интерфейс с пользователем
- •1.7. Организация работы
- •1.8. Инструментальные средства создания систем искусственного интеллекта
- •Языки программирования
- •1.8.2. Языки продукционного программирования
- •1. 8. 3. Языки инженерии знаний и инструментальные системы
- •1.8.3.1. Система vpExpert
- •1.8.3.2. Система kas
- •1.8.3.3. Система Expert-Ease
- •Глава 2. База знаний
- •2.1. Методы извлечения знаний
- •2.1.1. Классификация методов извлечения знаний
- •2.1.2. Пассивные методы
- •2.1.2.1. Наблюдения
- •2.1.2.2. Анализ протоколов «мыслей вслух»
- •2.1.2.3. Лекции
- •2.1.3. Активные индивидуальные методы
- •2.1.3.1. Анкетирование
- •2.1.3.2. Интервью
- •2.1.3.3. Свободный диалог
- •2.1.4. Активные групповые методы
- •2.1.4.1. «Круглый стол»
- •2.1.4.2. «Мозговой штурм»
- •2.1.4.3. Экспертные игры
- •2.1.4.3.1. Игры с экспертом
- •2.1.4.3.2. Ролевые игры в группе
- •2.1.4.4. Игры с тренажерами
- •2.1.4.4.1. Компьютерные экспертные игры
- •2.1.5. Текстологические методы
- •2.2.Формальное описание понятий предметной области (по)
- •2.2.1. Методы абстрагирования понятий
- •2.2.1.1.Агрегация и декомпозиция понятий
- •2.2.1.2.Обобщение и специализация понятий
- •2.2.1.3.Типизация и конкретизация понятий
- •2.2.1.4.Ассоциация и индивидуализация понятий
- •2.3.Методы классификации
- •2.3.1. Экстенсиональный и интенсиональный аспекты классификации
- •2.3.2. Таксономия и мерономия
- •2.3.3. Типы классификаций
- •2.3.4. Древовидные классификации
- •2.3.5. Булевы классификации
- •2.3.6. Комбинативные классификации
- •2.4.События и процессы
- •2.4.1. Состояния предметной области
- •2.4.2. Событие
- •2.4.3. Последовательные процессы
- •2.4.4. Рекурсивные процессы
- •2.4.5. Ветвящиеся процессы
- •2.5. Системы продукций: структура, технология, применение
- •2.5.1. Неформальное введение в системы продукций
- •2.5.1.1 Алгоритмические модели
- •2.5.2 Логический вывод
- •2.5.3 Прикладные модели
- •2.5.4. Метамодель систем продукций
- •2.5.4.1. Основные подсистемы
- •2.5.5.2. Метаструктура базы данных и операций
- •2.5.5.2.1. Характер организации данных
- •2.5.5.2.2 Операции над базой данных
- •2.5.5.2.3 Контроль несовместимости
- •2.5.5.2.4 Ассоциативная надстройка
- •2.5.6. Метаструктура модуля правил
- •2.5.6.1 Аппарат активации
- •2.5.6.2 Структура правил
- •2.5.7. Метаструктура модуля управления
- •2.5.8. Технология поддержки разработок продукционных систем
- •2.5.9. Формальные модели систем продукций
- •2.5.9.1. Алгебраическая модель
- •2.5.9.1.1. Основные определения
- •2.5.9.1.2. Операции преобразования ситуации
- •2.5.9.1.3. Условия корректности вычислений над конъюнктивной базой данных
- •2.5.9.1.4. Однозначность вычислений над дизъюнктивной базой
- •2.5.9.2. Управление выводом в системах продукций
- •2.5.9.3. Язык управления применением продукций
- •2.5.9.4. Язык управления выбором данных
- •2.5.9.5. Обзор формальных моделей вычислений
- •2.5.10. Экспериментальные системы продукций
- •2.5.10.1. Система скип
- •2.5.10.2. Система анализа топологических чертежей интегральных схем
- •P(слой) x0, y0 : Dx1, Dy2, .., Dxn-1, Dyn;
- •2.6. Выводы к второй главе
- •3. Машина логического вывода
- •3.1. Формальное определение задачи
- •3.2. Специфика решения задач в сии
- •3.3. Управление процессом решения задачи
- •3.4. Модели эвристического поиска решений
- •3.4.1 Стратегия поиска в глубину
- •3.4.2. Стратегии перебора с отсечениями
- •3.4.2.1. Метод ветвей и границ
- •3.4.2.2. Стратегии поиска на основе эвристической функции оценки
- •3.5. Методы вывода и доказательства теорем
- •3.5.1 Механизм резолюции Робинсона
- •3.5.2. Резолюция в логике высказываний
- •3.5.2.1 Линейная резолюция вL
- •Метод линейного вывода в lЛавленда, Ковальского и Кюнера
- •Эффективная реализация
- •3.5.2.3. Метод поиска в глубину
- •3.5.2.4 Эвристики поиска в дереве
- •3.5.2.5. Семантическая резолюция
- •3.5.3 Резолюция в pl
- •3.6. Методы индуктивного вывода
- •3.6.1. Виды индукции
- •3.6.2. Индукция как вывод и индукция как метод
- •3.6.3. Правила, необходимые для систем автоматического формирования знаний
- •3.7. Дедуктивный вывод на семантических сетях
- •3.7.1. Нерезолютивные методы вывода на семантических сетях
Примеры стратегии вывода
Рассмотрим формализм нормальных алгоритмов Маркова, в котором правила вывода реализуются на основе операторов подстановки.
Пусть а и b- произвольные слова. Будем говорить, что слово а входит в словоb, если существуют такие слова с иd, чтоb=cad.
Основным правилом вывода является подстановка. Оператор подстановки аbиспользуется для замены левого вхождения слова а на словоb. Для того, чтобы применить оператор аbк словуe, необходимо, чтобы е содержало а. В последнем случае будем говорить, что выполнены условия применимости оператора аb. Из множества операторов, для которых выполнены условия применимости, всегда выбирается один оператор (например, первый по порядку). Отметим, что вывод считается детерминированным, если всякий раз условия применимости выполняются не более чем для одного правила вывода. Алгоритм завершает работу, если либо нет выполнимых операторов, либо выполняется специальный оператор конца (стоп-оператор).
Пример.
(1)a bc
(2) c ebcc
(3) c d
(4) d
(5) b
(6) есс d.
e- символ пробела.
Рассмотрим, как преобразуется в этой системе слово cad:
cad ebccad eccad dad ad bcd cd ebccd eccd dd d
Здесь внизу под стрелкой указан номер оператора.
В системах нормальных алгоритмов Маркова выводимость трактуется в конструктивном смысле - как получение из исходного слова (образца) других слов. Это - так называемый вывод по образцу (нашедший применение, например, в системах, использующих фреймы и семантические сети). Каноническая продукционная система Поста также является системой вывода по образцу.
Пусть x1,x2, ...,xn- попарно различные переменные, которые имеют области определенияD1,D2, ...,Dmсоответственно. Если переменная х связана некоторым значениемизDj, , то будем вместо х, писать.
Образец это конструкция
где каждому xi, сопоставлен терм уi, являющийся либо самой переменной хi, (если она не связана), либо, еслиxi=.
Например,
1=
Пусть даны два образца 1и2. Будем говорить, что из1и2выводится образец3, и писать это:, если выполнены следующие условия:
1и2содержат общие переменные
пустьxi- одна (любая) из общих переменных, тогдаxiи в1, и в2либо связана одним и тем же значением, либо как минимум одна из них не связана вовсе.
3образуется путем включения (без дублирования) всех переменных из1и2. При этом если общая переменнаяxiсвязана, скажем в1, значениемхi = а, а в2свободна ( не связана), то в3xiбудет иметь значениеа. В этом случае говорят, что переменные в3наследуют значения соответствующих переменных в1,2.
Пример вывода по образцам 1,2образца3.
1=
2 =
из 1, 2выводим образец3
3 =
Другой важной стратегией, используемой в машинах вывода, является Байесовская стратегия вывода, которая используется в системах, где детерминированность выводов является скорее исключением, чем правилом.
Байесовская стратегия вывода оперирует вероятностными знаниями. Ее основная идея заключается в оценке апостериорной вероятности гипотезы при наличии фактов, подтверждающих или опровергающих гипотезу. Пусть
Р(Н) = - априорная вероятность гипотезы Н при отсутствии каких- либо свидетельств;
Р(Н:Е) = - апостериорная вероятность гипотезы Н при наличии свидетельства Е.
Согласно теоремы Байеса:
(1.26)
и
гдеР(Н*) оценивает новую вероятность гипотезыНс учетом свидетельстваЕ.
Введем отношение правдоподобия ОП(Н:Е),
(1.27)
а также формулу для вычисления шансов O(H),
(1.28)
Из (1.28) нетрудно обратным преобразованием получить
(1.29)
Теперь формула Байеса (1.8) на языке шансов принимает следующий вид:
O(H*) = O(H) OП(H:E), (1.30)
где O(Н*) - новая оценка шансов для гипотезы Н с учетом свидетельства Е.
Формула (1.30) при наличии многих свидетельств E1,E2, ...,Enпринимает вид:
(1.31)
Таким образом, на основании формул (1.30) и (1.31) имеется возможность просто пересчитывать апостериорные вероятности гипотез на основании получаемых свидетельств. Теорема Байеса является основой механизма вывода в экспертных системах PROSRECTORиHULK.
Рассмотрим пример использования стратегии Байеса. Пусть требуется провести дифференциальную диагностику между заболеваниями D1,D2, ...,Dn. Для простоты, пусть имеется три заболевания и четыре признака, по которым должен быть составлен диагноз.
Заболевания:
D1- тетрадаФалло,D2- дефект межпредсердечной перегородки,D3- незараценный артериальный проток.
Признаки:
S1- цианоз,S2- усиление легочного рисунка,S3- акцент II тона во втором межреберье слева,S4- правограмма (ЭКГ).
Допустим, известны следующие условные и безусловные вероятности (табл. 1.2), полученные на основе накопленной статистики о больных данными заболеваниями.
Таблица 1.2
Dj |
P(Dj) |
P(S1/Dj) |
P(S2/Dj) |
P(S3/Dj) |
P(S4/Dj) |
D1 |
0,35 |
0,9 |
0 |
0,05 |
0,6 |
D2 |
0,15 |
0,15 |
0,8 |
0,8 |
0,8 |
D3 |
0,50 |
0,10 |
0,95 |
0,90 |
0,10 |
Пусть у пациента налицо все четыре признака: S1,S2,S3,S4. Каков диагноз заболевания? На основе теоремы Байеса можно оценить апостериорные вероятности заболеваний в предположении, что признакиS1,S2,S3,S4независимые. Найдем
(1.32)
Из условия независимости признаков имеем:
P(S1, S2, S3, S4|Di) = P(S1|Di) P(S2|Di) P(S3|Di) P(S4|Di) (1.32)