- •Алгоритм а
- •Структуры управления в mycin
- •Математическое определение нечетких множеств. Определение уиниверсума. Примеры.
- •Сценарий посещения ресторана
- •Структуры данных в языке lisp
- •Обработка списков
- •Сопоставление с образцом
- •Определение функции принадлежности. Виды и примеры функций принадлежности. Примеры.
- •Классический период: игры и доказательство теорем Поиск в пространстве состояний
- •Графы, деревья и сети
- •Представление неопределенности знаний и данных
- •Источники неопределенности
- •Определение ядра, высоты и границ нечеткого множества. Пример.
- •Машина логического вывода и база знаний. Представление знаний: принципы и методы. Представление знаний: принципы и методы
- •Системы, основанные на знаниях
- •Канонические системы
- •Объектно-ориентированный анализ и конструирование экспертных систем
- •Нормальное нечеткое множество (определение). Равенство и доминирование нечетких множеств. Пример.
- •Планировщик strips
- •Представление типовых объектов и ситуаций
- •Основные понятия концепции фреймов
- •Фреймы и графы
- •Объектно-ориентированный анализ и конструирование экспертных систем
- •Операции пересечения, объединения и разности нечетких множеств. Примеры.
1В
Типовые задачи, решаемые экспертными системами и характеристики экспертных систем.
Экспертная система — это программа для компьютера, которая оперирует со знаниями в определенной предметной области с целью выработки рекомендаций или решения проблем.
Перечень типовых задач, решаемых экспертными системами, включает:
извлечение информации из первичных данных (таких как сигналы, поступающие от гидролокатора);
диагностика неисправностей (как в технических системах, так и в человеческом организме);
структурный анализ сложных объектов (например, химических соединений);
выбор конфигурации сложных многокомпонентных систем (например, распределенных компьютерных систем);
планирование последовательности выполнения операций, приводящих к заданной цели (например, выполняемых промышленными роботами).
Характеристики экспертных систем:
Экспертная система отличается от прочих прикладных программ наличием следующих признаков.
Моделирует не столько физическую (или иную) природу определенной проблемной области, сколько механизм мышления человека применительно к решению задач в этой проблемной области. Это существенно отличает экспертные системы от систем математического моделирования или компьютерной анимации.
Система, помимо выполнения вычислительных операций, формирует определенные соображения и выводы, основываясь на тех знаниях, которыми она располагает. Знания в системе представлены, как правило, на некотором специальном языке и хранятся отдельно от собственно программного кода, который и формирует выводы и соображения. Этот компонент программы принято называть базой знаний.
При решении задач основными являются эвристические и приближенные методы, которые, в отличие от алгоритмических, не всегда гарантируют успех. Эвристика, по существу, является правилом влияния (rule of thumb), которое в машинном виде представляет некоторое знание, приобретенное человеком по мере накопления практического опыта решения аналогичных проблем. Такие методы являются приблизительными в том смысле, что, во-первых, они не требуют исчерпывающей исходной информации, и, во-вторых, существует определенная степень уверенности (или неуверенности) в том, что предлагаемое решение является верным.
Экспертные системы отличаются и от других видов программ из области искусственного интеллекта.
Экспертные системы имеют дело с предметами реального мира, операции с которыми обычно требуют наличия значительного опыта, накопленного человеком. Экспертные системы имеют ярко выраженную практическую направленность в научной или коммерческой области.
Одной из основных характеристик экспертной системы является ее производительность, т.е. скорость получения результата и его достоверность (надежность). Экспертная система должна за приемлемое время найти решение, которое было бы не хуже, чем то, которое может предложить специалист в этой предметной области.
Экспертная система должна обладать способностью объяснить, почему предложено именно такое решение, и доказать его обоснованность. Пользователь должен получить всю информацию, необходимую ему для того, чтобы быть уверенным, что решение принято "не с потолка". Экспертная система проектируется в расчете на взаимодействие с разными пользователями, для которых ее работа должна быть, по возможности, прозрачной.
Эвристический поиск. Алгоритм А.
Поскольку слепой поиск возможен только в небольшом пространстве вариантов, напрашивается совершенно естественный вывод, что необходим некоторый способ направленного поиска. Если такой способ использует при поиске пути на графе в пространстве состояний некоторых знаний, специфических для конкретной предметной области, его принято называть эвристическим поиском. Лучше всего рассматривать эвристику в качестве некоторого правила влияния, которое, хотя и не гарантирует успеха (как детерминированный алгоритм или процедура принятия решения), в большинстве случаев оказывается весьма полезным.
Простая форма эвристического поиска — это восхождение на гору.
Лучшими свойствами обладает другая форма эвристического поиска, которая получила наименование сначала наилучший (best-first search). Так же, как и в варианте восхождения на гору, в нашем распоряжении имеется оценочная функция, с помощью которой можно сравнивать состояния в пространстве состояний. Основное же отличие нового метода от ранее рассмотренного состоит в том, что сравниваются не только те состояния, в которые возможен переход из текущего, но и все, до которых "можно достать".
Алгоритм а
Существует хорошо известный алгоритм поиска, который относится к группе первый лучший, получивший наименование А (произносится "А со звездочкой"). Основная идея алгоритма состоит в использовании для каждого узла п на графе пространства состояний оценочной функции вида
f(n) = g(п) + h(n).
Здесь g(п) соответствует расстоянию на графе от узла п до начального состояния, a h(n) —оценка расстояния от п до узла, представляющего конечное (целевое) состояние. Чем меньше значение оценочной функции f(n), тем "лучше", т.е. узел п лежит на более коротком пути от исходного состояния к целевому. Идея алгоритма состоит в том, чтобы с помощью f(n) отыскать кратчайший путь на графе от исходного состояния к целевому.
Отсюда следует, что если h(n) — нижняя оценка действительного расстояния до целевого состояния, т.е. если h(n) никогда не дает завышенной оценки расстояния, то алгоритм А всегда отыщет оптимальный путь до цели при помощи оценочной функции f(n). Алгоритм, обладающий таким свойством, называется разрешимым (более подробное обсуждение этого вопроса читатель найдет в специальной литературе, в частности в работах Нипьсона [Nilsson, 1980, Chapter 2] и Перла [Pearl, 1984, Chapter 2]).
Обозначения:
s — узел начального состояния;
g— узел целевого состояния;
OPEN — список, который содержит, выбранные, но необработанные узлы;
CLOSED — список, который содержит обработанные узлы.
Программа MYCIN. Структуры управления в MYCIN.
MYCIN
MYCIN используется в области диагностики и лечения заболеваний крови.
Назначение этой программы — быть ассистентом врача, который не является узким специалистом в области применения антибиотиков при лечении заболеваний крови. В процессе работы программа формирует гипотезы диагноза и придает им определенные веса, но самостоятельно, как правило, не делает окончательного выбора.
После 1976 года система неоднократно модифицировалась и обновлялась, но базовая версия состояла из пяти компонентов.
(1) База знаний содержит фактические знания, касающиеся предметной области, и сведения об имеющихся неопределенностях.
(2) Динамическая база данных пациентов содержит информацию о конкретных пациентах и их заболеваниях.
(3) Консультирующая программа задает вопросы, выводит заключения системы и дает советы для конкретного случая, используя информацию о пациенте и статические знания.
(4) Объясняющая программа отвечает на вопросы и дает пользователю информацию о том, на чем основываются рекомендации или заключения, сформулированные системой. При этом программа приводит трассировку процесса выработки рекомендаций.
(5) Программа восприятия знаний служит для обновления знаний, хранящихся в системе, в процессе ее эксплуатации.
Подсистема, в которую входят компоненты 1, 2 и 3, отвечает за решение проблемы. Эта подсистема строит гипотезы относительно причин заболевания и формирует рекомендации, основываясь на этих гипотезах.
Структуры управления в mycin
Целевое правило самого верхнего уровня в системе MYCIN можно сформулировать примерно так:
ЕСЛИ 1) существует микроорганизм, который требует проведения курса терапии, и 2) заданы соображения относительно любых других микроорганизмов, которые требуют проведения курса терапии,
ТО сформировать список возможных курсов терапии и выделить наилучший из них.
В ходе консультации выполняется простая двухэтапная процедура:
формируется контекст пациента в форме самого верхнего узла контекстного дерева;
предпринимается попытка применить целевое правило к этому контексту пациента.
Применение правила включает в себя оценку сформулированных в нем предпосылок, а этот процесс, в свою очередь, включает проверку, существует ли микроорганизм, который требует проведения курса терапии.
Структура управления правилами в MYCIN использует И/ИЛИ-граф и по сравнению с программами искусственного интеллекта довольно проста — в ней, по сути, использована методика исчерпывающего поиска, описанная в главе 2, в которую внесены только незначительные изменения.
(1) Формулировка каждой подцели всегда представляет собой обобщенную форму исходной цели. Так, если подцель состоит в том, чтобы доказать справедливость суждения "организм— это E.Coli", то формулировка такой подцели— определение типа организма. Этим инициируется исчерпывающий поиск, в который вовлекаются все возможные сведения об организмах.
(2) В множестве правил, подходящих для сформулированной цели, выискивается такое, которое определенно удовлетворяется. Если для заключения об определенном параметре, например о природе организма, подходит несколько правил, то их результаты объединяются (см. врезку 3.2). Если коэффициент уверенности какой-либо из выдвинутых гипотез оказывается в диапазоне от -0.2 до +0.2, то гипотеза отбрасывается.
Такой вид структуры управления правилами получил наименование цепочки обратного вывода (backward chaining), поскольку путь рассуждений идет от того, что нужно доказать, к фактам, на которых основывается доказательство. При прямой цепочке рассуждение ведется, отталкиваясь от имеющихся фактов.