Лекции - Архитектура систем искусственного интеллекта

Подождите немного. Документ загружается.

консультации - установить физические кондиции пациента. В этом случае, задавая

вопросы типа

"Каков возраст пациента?"

"Каков вес пациента?"

"Потребляет ли пациент жиры?" и т.д.

Система создает контекст, представляющий множество переменных и их значений,

например:

Возраст = 35

Вес = 85

Потребление жиров = 50 и т.д.

С другой стороны, контекст может быть наращен и с помощью правил. Например,

если есть следующее правило:

ЕСЛИ (ВЕС = X) & (ВОЗРАСТ < 40), ТО

(ИДЕАЛЬНЫЙ_РОСТ = 100 + X),

то контекст будет расширен путем вычисления и добавления факта

ИДЕАЛЬНЫЙ_РОСТ = 185

Простейший алгоритм, осуществляющий построение трассы вывода, заключается в

следующем:

1. Определить исходный контекст.

2. Занести все переменные исходного контекста в очередь переменных логического

вывода, а их значения (если заданы) - в список переменных.

3. Просмотреть список переменных и найти ту переменную, имя которой стоит в

начале очереди переменных логического вывода. Если переменная найдена, записать в

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

перейти к шагу 6.

4. Присвоить значения непроинициализированным переменным условной части

найденного правила (если такие есть). Имена переменных содержатся в списке

переменных условия правила. Проверить все условия правила и в случае их истинности

обратиться к части "ТО" правила.

5. Присвоить значение переменной, входящей в часть "ТО" правила, и поместить ее

в конец очереди переменных логического вывода.

6. Удалить переменную, стоящую в начале очереди переменных логического

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

7. Закончить процесс рассуждений, как только опустеет очередь переменных,

логического вывода. Если в очереди есть еще переменные, вернуться к шагу 3.

На машину вывода возлагаются следующие основные задачи:

1 .Построение трассы вывода.

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

3 . Повышение эффективности поиска.

Формальное понятие трассы вывода дается ниже. Задача построения трассы вывода

заключается в отображении в памяти ЭВМ последовательности шагов вывода,

применяемых правил и получаемых значений переменных. Множество значений

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

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

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

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

эффективность системы (быстродействие ЭС), поэтому необходимы меры по обеспечению

достаточной эффективности машины вывода.

Существует два базовых подхода к построению трассы вывода. Первый основан на

логике решения в направлении "от того, что известно - к тому, что надо найти"; второй

подход, наоборот, использует движение в обратном направлении: "от того, что надо

найти - к тому, что известно" Первый подход характеризует системы с прямым выводом,

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

цели известны и их сравнительно немного.

В системах диагностики чаще применяется прямой вывод, в то время как в

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

комбинированный вывод, основанный на сочетании прямого и обратного поиска.

Комбинированный вывод называется также циклическим.

Проблема организации трассы вывода напрямую связана с повышением

эффективности поиска. Мы подробно исследуем эти вопросы в последующих разделах.

Сейчас формализуем задачу организации трассы вывода. Для этого введем понятие

дерева решения. Рассмотрим пятерку

, S

, A, R

, R

>, (1.34)

где S

- исходное состояние системы (объекта, модели);

- конечное (искомое) состояние системы (объекта, модели);

А - алгоритм отображения

S S

 

;

- список ограничений на реализацию алгоритма А;

- список ограничений на 8у (критерий).

Состояние исследуемой системы (объекта) S

, непосредственно достигаемое из S

назовем преемником S

, а состояние S

- предшественником S

. Граф Г(S, ) с множеством

вершин состояний S

 S и дуг , связывающих предшественников и преемников, образует

дерево решения с корнем S

и листом S

если:

1) -й ярус в Г образуют те преемники ( - 1)-го яруса ( = 1,2,...), которые не

входят в ярусы ( - 2), ( - 3) и т.д.;

2) листьями в Г являются состояния, все преемники которых содержатся в

верхних ярусах (исключение, возможно, составляет S

Возможными вариантами постановки задачи относительно (1.34) являются (1.5) -

(1.8).

Все эти задачи так или иначе упираются в проблему отыскания маршрута М в Г(S, ),

связывающего S

и S

. Некоторая (любая) законченная часть этого маршрута называется

трассой вывода. Очевидно, что эффективность стратегии вывода определяется в первую

очередь тем, насколько "близко" она держится М и, во-вторых, насколько велики затраты

(памяти и процессорного времени) для реализации этой стратегии вывода. В качестве

одной из оценок эффективности стратегии поиска определена оценка меры близости

трассы вывода и М в виде

P =

(1.35)

где L - длина найденного пути к цели (длина М),

Т - общее число вершин, пройденных при поиске цели в Г(S, ).

Очевидно, что детерминированная оптимальная стратегия обеспечивает

максимальную меру близости Р, равную 1. Повышение эффективности поиска по-разному

достигается в существующих системах вывода:

(1) использование эвристических функций оценки;

(2) использование приоритетов для правил;

(3) использование метаправил (правил для правил).

Эти вопросы будут обсуждены позже.

Лекция 3 по СИИ

1.3 Извлечение знаний и обучение

Модуль извлечения знаний в составе экспертной системы не является обязательным

компонентом. СИИ должна обеспечивать функцию ввода и обновление знаний. Эта

функция либо реализуется в направлении "эксперт  система", либо СИИ извлекает

новые знания из тех, которые уже содержатся в базе знаний. Последняя возможность

осуществляется на основе механизмов вывода знаний и обучения. Существующие

сложности, связанные с формированием понятий машиной, а также отсутствием

эффективных формализмов для оперирования абстрактными значениями. Это

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

обучения (самообучения) в составе экспертных систем. Вместе с тем, поскольку проблема

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

ожидать в областях, где СИИ работает с задачами классификации и распознавания.

Остановимся на этих вопросах подробнее.

1.3.1 Извлечение знаний от многих экспертов

Извлечение знаний от экспертов ставит следующие проблемы:

(1) в какой форме осуществляется диалог с экспертами?

(2) как обрабатывать информацию, представленную экспертами?

Первая проблема состоит в том, что СИИ "не имеет представлений" о том, что она

призвана решать. Иначе говоря, она либо ведет один и тот же сценарий диалога, либо

вообще является пассивной стороной, представляя эксперту набор директив редактора

базы знаний. Однако, даже и в этом последнем случае встает проблема, чтобы введенная

экспертом информация:

(а1) была непротиворечивой;

(а2) не нарушала целостность существующей базы знаний;

(а3) не была "пустой" или избыточной.

Таким образом, обеспечение требований (а1 - а3) является важнейшей функцией

модуля извлечения знаний и обучения.

Рассмотрим, как осуществляется обработка экспертной информации на примере

системы диагностирования. Предположим, эксперты оценивают некоторый диагноз

(гипотезу), указывая оценки правдоподобности (коэффициенты уверенности - КУ) этой

гипотезы. Таким образом, каждый эксперт формирует пару (Н, КУ

), где Н - некоторая

гипотеза. Если обозначить через 

, 

, ..., 

- степени компетентности экспертов (веса),

то результирующее значение КУ* для гипотезы Н полагаем равным:

КУ* = КУ

i i

i=1

 

 

(1.36)

При отсутствии информации о компетентности экспертов можно положить 

= 1

(i = 1, n)

Для оценки статистической значимости найденного значения КУ* находят

дисперсию

  

i i

i=1

= (КУ - КУ*) 

 

(1.37)

и далее, задавшись вероятностью ошибки Р

ош

, определяют вероятность (1 - Р

ош

), с

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

[КУ* - ; КУ* + ], (1.38)

где

 = t n 

и t - коэффициент Стьюдента, устанавливаемый из таблиц по

значению Р

ош

и n.

Другой важной задачей при экспертизе является ранжирование продукций с учетом

их важности. Очевидно, что от того, насколько точно ранжированы правила, определяется

эффективность стратегии вывода.

В результате процедуры ранжирования строится следующая таблица (табл. 1.4)

Таблица 1.4.

Эксперты

Продукция

1 2 m

1 r

2 r

рангов r

В нижней строке табл. 1.4 записываются суммы рангов, полученные каждой

продукцией (чем больше сумма, тем продукция важнее). Результирующее упорядочение

продукций осуществляется согласно оценкам r

Статистическая согласованность (значимость) ранжирования проверяется для случая

отсутствия равных рангов в ранжировке каждого эксперта, на основании коэффициента

конкордации (согласованности) W:

 

W =

12 r -

n(m + 1)

n (m - m)

i=1

2 3



(1.39)

В случае нестрогого ранжирования (при наличии равных рангов) используется

формула:

 

W =

12 r -

n(m + 1)

n (m - m) - n (t - t )

i=1

2 3

j=1

i=1





(1.40)

где k - число групп равных рангов, введенных i-м экспертом;

t - число одинаковых элементов в j-ой группе i-го эксперта.

Пусть значение W найдено. Вычисляется величина n(m - 1)W, для которой задаются

вероятностью ошибки Р

ош

. Согласно 

- распределения с (m - 1) степенью свободы для Р

ош

находят табличное значение W

таб

. Если найденное значение WW

таб

, то W считается

статистически значимой.

Другой вариант извлечения знаний, связан с ответом системы на запросы

пользователя. При этом вопрос интерпретируется как теорема, которая подлежит

доказательству, а нахождение ответа на вопрос ищется на основании метода

доказательства теорем. В рамках этой концепции построена система логического

пропсам- минования Пролог, рассматриваемая позднее. В качестве иллюстрации

рассмотрим следующий Пролог - подобный пример.

Здоровое_тело (Y)  Здоровый_дух (Y).

Спортсмен (Х) & Ведет_здоровый_образ_жизни (Х)  Здоровое_тело (Х).

Здоровый_дух (Z)  Подходящий_партнер (Z).

Спортсмен (Сидоров).

Спортсмен (Иванов).

Спортсмен (Петров).

Здоровое_тело (Федоров).

Ведет_здоровый_образ_жизни (Петров).

Ведет_здоровый_образ_жизни (Сергеев).

Зададим вопрос системе в форме

? - Подходящий партнер (Т).

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

цепочку с чаключением в виде теоремы-вопроса. Не приводя способа построения этой

цепочки, укажем ее Симу (одну ич подходящих цепочек):

Спортсмен (Петров)  Ведет_здоровый_образ_жизни (Петров)  Здоровое_тело

(Петров)  Здоровый_дух (Петров)  Подходящий партнер (Петров).

Следовательно, ответом на вопрос является Т = Петров.

1.3.2 Проблема непротиворечивости формализованной базы знаний

При добавлении информации от экспертов в базу знаний, необходимо обеспечить

непротиворечивость базы знаний. Непротиворечивость означает, что в базе знаний не

выводимы никакие два факта (формулы) вида а и

(из которых один отрицает другой).

Проблема непротиворечивости не является тотальной, т.е. вполне допустимы противо-

речивые системы, однако, нужно иметь в виду следующее.

Во-первых, практически многие хорошо разработанные теории вывода работают с

непротиворечивыми системами формул. Действительно, если система противоречива, то

в ней выводимо все что угодно! Это обстоятельство практически лишает смысла само

понятие вывода в противоречивой системе. В такой системе, следовательно, вывод

заменяется иными механизмами (например, механизмами классификации -

распознавания и принятия решений).

Во-вторых, сам характер задачи, стоящей перед СИИ, не допускает противоречивого

толкования знаний (например, заключения



: "пациента нужно немедленно

прооперировать" и



: "пациента не нужно немедленно оперировать" таковы, что

неясность в смысле их выбора может стоить жизни человеку. (Такова, к примеру, фабула

романа А. Хейли "Окончательный диагноз").

В формальных логических системах первого порядка противоречивость

эквивалентна выводимости в системе пустой формулы (интерпретируемой как ложь).

Неизбыточность. Требование незбыточности означает, что в базе знаний хранятся

лишь независимые друг от друга знания. Формула



зависима от формул 

, 

, ..., 

если



выводима из 

, 

, ..., 

в силу правил вывода. Неизбыточность знаний не

является императивным требованием. Фактически, избыточность имеет сильный

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

Пусть СИИ в результате доказательства цели построила цепочку

, П

, ..., П

i n-1

 C

 ...  C

где С

- k-ый контекст вывода (k-ое состояние трассы вывода);

- правило вывода (продукция), применяемое к контексту С

j-1

Это позволяет ввести в базу знаний новую продукцию

 С П

* *

где является выводом по образцу из С

и С

- условная часть продукции П

П* = <П

, П

, ..., П

i n-1

> - представляет последовательную цепочку операционных частей

продукций П

, П

, ..., П

i n-1

Добавление продукции

 С П

* *

в базу знаний при следующем решении задачи

, C

- ?> избавит от необходимости строить план решения задачи снова, т.е. приводит

к увеличению быстродействия СИИ. Рассмотрим, как определяется зависимость формул в

логике высказывании, являющейся тон частью логики предикатов, которая позволяет

формализовать фактуальные знания (т.е. знания, представленные совокупностью фактов).

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

представленной в виде

G = g

 g

 ...  g

, (1.41)

где g

- формулы (гипотезы), взятые с отрицанием или без него, из формулы F

произвольного вида, т.е. доказать справедливость:

F  g

 g

 ...  g

, (1.42)

Суть предлагаемого метода заключается в последовательном умножении обеих

частей (1.42) на

i = 1, m

. Например, в порядке возрастания индекса i, пока не будет

получена одна из следующих ситуаций:

(a1) F*  

(a2) F*  F* (   или F*  1)

(a3)   F*,

где  - символ пустой формулы,  = х &

;

F - непустая формула формальной системы.

Тогда справедливы следующие заключения:

Ситуация (а1) означает невыводимость G из F (G не находится в отношении

логического следствия из F);

Ситуация (а2 и а3) означает, что G логически следует из F, 1 = х 

Таким образом, для доказательства произвольной формулы F  G, ее необходимо

привести к виду (1.42) и выполнить описанную процедуру, доказательство которой здесь

опускается.

Пример. Пусть даны формулы

= a  b&c&

= b 

&f,

= c 

 x  y.

Покажем, что имеет место

a&f

 x.

Умножим обе части на х:

a(a bcy)(b ef)(c e x y)x    

 .

Заменим (p  q) на

p g