Mycin (мицин), teiresias, emycin- 1976 Г.

ТЕМА ИИ – 9. Примеры ЭС

Лекция ИИ-9.1/2009

КЛАССИЧЕСКИЕ ЭС.

ПР0ИЗВОДСТВЕННЫЕ СИСТЕМЫ ИСКУССТВЕННОГГО ИНТЕЛЛЕКТА (ПСИИ)

КЛАССИЧЕСКИЕ ЭС

1. DENDRAL (Стефанюк, Попов/23)

Химия - одна из первых областей, в кот-х ИИ нашел прямое практическое применение.

Основа нового направления - "экспертные системы" - была заложена разработкой в середине 60-х гг в ВЦ Стэнфордского ун-та системы "Эвристический Дендрал" (Heuristic Dendral), кот-я осущ-сь в рамках Стэнфордского проекта, прод-ся 16 лет: 1965 - 1981.

У истоков разработки - Э. Фейгенбаум, Дж. Ледерберг (1985 - Ноб. премя за работы по генетике бактерий), в дальн-м подключился Б. Букхенен и др.

Цель разработки - создание программы, которая используя богатые знания по химии, заложенные в компьютер,

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

 

Эта задача относится к классу задач интерпретации и требует для своего решения высокой квалиф-ции.

 

1. ОРГАНИЗАЦИЯ ЗНАНИЙ

ЗНАНИЯ в этой ЭС состоят из структур молекул (химических структур), ограничений и правил.

Структуры молекул предст-ся в виде графов, где:

вершины - атомы, дуги - связи между атомами.

Ограничения предст-ся в виде подграфов, наличие которых в структуре молекулы запрещено.

Правила, с помощью которых генерируются возможные структуры молекул.

Они имеют форму "ситуация - действие", где "ситуация" и "действие" представлены в виде подграфов.

 

2. ПРОЦЕДУРА ВЫВОДА - эвристический поиск в три этапа:

"план - генерация - проверка".

 

(1) На этапе "ПЛАН " опред-ся

(возможно, с использованием входных данных от масс-спектрометра и известной химической ф-лы вещества- Е.Т.)

(а) пространство поиска решений [т.е. среди каких структур молекул надо искать структуру молекулы испытываемого вещества.- Е.Т. ]

(б) ограничения, касающиеся допустимых структур молекул (т.е. решений), соответствующие входным данным, полученным от масс-спектрометра. Эти ограничения представлены в виде ЗАПРЕЩЕННЫХ СТРУКТУР (т.е. подграфов).

 

(2) На этапе "ГЕНЕРАЦИЯ" порождаются ВСЕ возмож-е стр-ры молекул (решения), удовлетв-щие ограничениям, т.е. не содержащие запрещенных подграфов (польз-ль может задавать дополнит-е ограничения).

При поиске структур примен-ся стратегия, "направляемая данными" (Попов- п.5.2, с. 124).

 

(3) На этапе "ПРОВЕРКА" осущ-ся отбор ЛУЧШИХ из предложенных решений (структур молекул):

из структур молекул, полученных на этапе "ГЕНЕРАЦИЯ", т.е. удовлетворяющих ограничениям, отбираются те, которые наиболее точно соотв-вуют исходным данным, полученным с пом. масс-спектрометра.

 

В первых версиях ЭС:

- минимальные объяснительные способности,

- простейший язык общения,

- трудоемкий и слабо автоматизир-й процесс приобретения знаний.

Затем была спец-но разр-на с-ма " Мета-Дендрал ", кот-я автоматизир-ет процесс приобретения правил для ЭС ДЕНДРАЛ (Хейес-Рот и др. "Постороение ЭС" с. 19)

Возникают вопросы:

Почему ЭС разработана впервые - в химии?

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

Проект ДЕНДРАЛ - адресовался именно к таким задачам (характерным для химии), в кот-х числовые манипуляции играют второстепенную роль, а наиболее трудной частью явл-ся логические рассуждения.

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

но тратит 2-4 недели, т.е. способ решения з-чи человеку в принципе известен, но его применение слишком трудоемко.

 

Почему такие з-чи не были сформулир-ны для ЭВМ раньше?

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

2) главная особенность и трудность - невычислительный характер таких задач.

 

Для преодоления этой проблемы и создания ЭС потребовалось использ-е всех методов, накопленных в области ИИ и позв-щих применять ВЫЧИСЛИТ. ТЕХНИКУ для решения НЕВЫЧИСЛИТ-Х ЗАДАЧ, а именно:

- методов построения логических рассуждений (док-во теорем),

- методов описания, представления и манипулир-ния в ЭВМ с символьными структурами с пом спциальных языков программир-я типа ЛИСП,

- методов описания, предст-ния и манипулир-ния ЗНАНИЯМИ.

 

Разр-ка с-мы ДЕНДРАЛ – это первая попытка уйти от "игрушечных" задач. Она считается блестящим рез-татом в области ИИ.

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

MYCIN ("МИЦИН"), TEIRESIAS, EMYCIN- 1976 г.

(Попов/24-25 и Гл. 2:34 -54)

MYCIN

С этого м-та развитие ЭС приобрело стремительный характер.

Авторы проекта ДЕНДРАЛ попытались выделить ту часть программы, кот-я явл-ся предметно независимой, в рез-те чего в конце 60-х - начале 70-х гг была создана ЭС МИЦИН (MYCIN), предназначенная для решения задач постановки диагноза и определения методов лечения инфекционных заболеваний крови.

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

При разр-ке ЭС MYCIN ставились след-е треб-ния:

Пр-ма дол-на

1)быть полезной для польз-ля - врача, т.е. давать засл-е доверия реком-ции, не уступ-щие рек-циям спец-та, и быть удобной в экспл-ции;

2) быть ориентир-на на приобретение и модиф-цию знаний;

3) уметь вести диалог, в ходе кот-го объяснять получ-й резт;

4) быть инстр-том, помогающим врачу, а не заменяющим его.

Пример ситуации использ-ния ЭС.

В ходе оперции пац-ту занесена инф-ция, а леч-щий врач не явл-ся спец-м в области инф-х заболеваний и ему треб-ся реком-ция по леч-ю такого забол-ния.

Установление возбудит-ля болезни и точное уст-ние диагноза треб-ет дост. длит-го времени (анализы) - порядка 48 часов, а лечение должно нач-ся немедленно. Выбор: назначить ср-во широкого действия либо специфич-е ср-во с риском не угадать. Предпочтение - первому. Анализ таких сит-ций в США: в теч года пениц-н был прописан каждому четвертому, но в 90% случаев в этом не было необх-ти.

 

ОРГАНИЗАЦИЯ ЗНАНИЙ

ЗНАНИЯ раздел-ся на ФАКТЫ и ПРАВИЛА.

ФАКТЫ предст-ны в виде троек

- "объект- атрибут (т.е. свойство объекта) –значение атрибута",

Каждой из таких "троек" присвоен нек-й коэфф-т определенности (КО)

ПРАВИЛА (их общее число -ок. 400) предст-ны в виде системы продукций в форме "УСЛОВИЕ – ДЕЙСТВИЕ".

УСЛОВИЕ предст-но на языке исчисления предикатов (как булевское выражение предикатных ф-ций, применимых к фактам), а "действие" - факт или операция над фактом.

(P & Q Ú R) M ® Z

Факту, напр., Z, получ-му в рез-те выполнения продукции, присваивается коэффициент оределенности (КО), кот-й выраб-ся по определ-м правилам на основе КО фактов, входящих в условие. Если этот КО менее некот-го принятого порог-го значения, то он приним-ся равным нулю.

 

ПРОЦЕДУРА ВЫВОДА - исчерпывающий поиск, "направляемый целями " (вывод в системе продукций)

Попов- п.5.2

Системе известно 100 заболеваний.

При постановке диагноза система осуществляет поиск в направлении ОТ ЦЕЛИ (т.е. искомого диагноза) к ДАННЫМ.

Базовая стратегия - "поиск в глубину":

система просматривает правые части продукций (т.е. "действия" или "заключения") и выделяет те из них, которые содержат заключения о каком-либо диагнозе (т.е. ЦЕЛИ).

Таким образом формируется множество ВСЕХ правил, в заключении которых устанавливается какой-либо диагноз (ЦЕЛЬ).

Пусть множество таких правил - {X}.

Затем для всех правил множества {X} система выясняет выясняется, истинны ли УСЛОВИЯ выполнения этих заключений, т.е. ЦЕЛЕЙ (представленные левыми частями продукций).

Если для некоторого условия неизвестно, ИСТИННО ли оно, то входящие в это условие факты рассматриваются как подцели (т.е. новые цели) и процесс повторяется:

выбираются ВСЕ правила, в заключении (т.е. в правой части) которых имеются эти подцелии т. д., пока не будет установлена ИСТИННОСТЬ одной из целей (диагнозов), Возможно, что ни одна из целей не окажется истинной.

В рез-те будет найден путь (если он сущ-ет), приводящий от фактов, опис-щих условие задачи, к диагнозу (подробнее - Попов/п. 2.3, с.41).

 

Диалог с врачом: на ограниченном англ-м языке(простой лингв-й процессор - дост-но понимать смысл предл-ний на ур-не ключевых слов).

Объясн-е спос-ти: система анализирует процесс получения решения и отвечает на вопросы ПОЧЕМУ был использован некий факт или КАК этот факт был установлен (Попов/с.44).

Система обл-ет спос-тью модифиц-ть знания и приобретать новые.

Для развития объяснит-х спос-тей и автоматизации приобретения знаний построена инструм-ная с-ма TEIRESIAS.

EMYCIN

Для того, чтобы использовать этот подход для более широкого круга польз-лей авторы проекта MYCIN выделили "в чистом виде" идеи, заложенные в этой прог-мме.

В рез-те была создана ПЕРВАЯ " ПУСТАЯ ЭС", т.е. "оболочка" или инструментальная с-ма, названная EMYCIN (Empty MYCIN - пустая MYCIN).

Это версия MYCIN, не завис-щая от проблемной области, т.е. базовая с-ма для решения задач диагностики. Она позволяет применять процедуры вывода к такой предметной обл-ти, знания о которой могут быть записаны в виде правил MYCIN.

Об ЭС MYCIN. См. подробнее: П. Джексон/с. 72-80;

Попов-1987/с. 34-54 – оч. подробно

3. PROSPECTOR - 1979 -81 (Попов/25)

Геология. Задача - помочь геологу определить наличие месторождения определенной руды на основе анализа геологич-ких данных. Достигла стадии промышленной системы.

Кач-во решений не уступает решениям спец-та.

С пом этой ЭС найдено месторождение молибдена стоимостью ок. 100 млн долл.

ЗНАНИЯ предст-ны в виде моделей, каждая из кот-х соотв-ет месторождению опред-го типа.

При этом используются правила вида "условие -действие".

"Условие" и Действие" – это утверждения о проблемной области, которые могут быть истинными или ложнвми.

"Условие" явл-ся булевской комбинацией утверждений. "Действие" состоит из одного утверждения.

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

Вероятность простого утверждения, т.е. не сод-щего булевские операции, опред-ся из ответов польз-ля (или по правилу Байеса).

Вероятность логического утверждения, т.е. сод-щего булевские операции, вычисляется на основе вер-тей компонент этого утверждения по определ-м правилам (правилам Заде для нечетких множ-в).

 

ПРОЦЕДУРА ВЫВОДА

Возможен поиск, "направляемый ЦЕЛЯМИ" (как в MYCIN) или "направляемый ДАННЫМИ" (от ДАННЫХ к ЦЕЛИ).

Общение польз-ля с ЭС – с пом. обмена простыми предложениями англ. яз.

см. Попов/ с. 25-26

 

………………………..ДРУГИЕ ЭС..........................

4.CADUCEUS (Попов/26) - публ-ция 1977

Пробл. область - Диагностика внутренних болезней.

Содержит инф-ю о 500 болезнях (80% всех изв-х терапевтических заболеваний)

 

5. Коммерческая ЭС R1 1980

Конфигурация ВС VAX 11/780 ф-мы DEC по заказу польз-ля

Попов/с27

6. Инструм-е с-мы OPS 5, ROSIE, HEARSAY III, RLL

Попов/с. 28-33

…………………………………………………………………………………………..