wali.su
 
Набережные Челны
Тел.: +7 8552 397129

Картотечно-поисковая дедуктивная машина

 
 

Когда мы рассмотрели все компоненты базы знаний, можно приступать к построению картотечно-поисковой дедуктивной машины. Для упрощения манипуляций отдельными компонентами базы знаний будем считать, что каждое правило как бы размещено на отдельной «справочной карточке». Поскольку для независимых признаков предусмотрены как переводы, так и вопросы-подсказки, для любого признака можно подготовить справочную карточку, на которой размещаются ключевое слово, перевод и подсказка (если последняя вообще имеется для данного признака).

Правила, используемые в нашей базе знаний, сведены в табл. 1, а полный набор карточек признака, содержащих признаки, переводы и подсказки, представлен в табл. 2. Теперь попытаемся реализовать такой набор карточек на практике. Номера шагов в приведенном ниже описании относятся к сеансу консультации по классификации растений, проиллюстрированной табл. 3.

Таблица 3. Пошаговое представление сеанса консультации с помощью картотечно-поисковой дедуктивной машины, иллюстрирующее изменение содержимого стеков

Шаг

Анали-
зируемое
правило

Значение
правила

Ответ на
подсказку

Стек целей

Контекстный стек


правила


отброшенного
правила

Признак


правила

Признак

Значение

1

 

 

 

семейство

 

 

 

 

 

2

1

неизвестн.

 

класс

1

 

 

 

 

3

5

неизвестн.

 

тип

5

 

 

 

 

4

7

неизвестн.

 

стебель

7

 

 

 

 

5

нет


древесный

тип

6

стебель

древесный



6

7

ЛОЖЬ

 

 

 

 

 

 

 

7

8

неизвестн.

 

положение

8

 

 

 

7

8

нет

 

прямой

тип

5

положение

прямой

 

 

9

8

ЛОЖЬ

 

 

 

 

 

 

8

10

9

неизвестн.

 

Осн.ствол

9

 

 

 

 

11

нет

 

да

тип

5

Осн.ствол

да

 

 

12

9

ИСТИНА


класс

1

тип

дерево

9

 

13

5

неизвестн.

 

Шир.+плос

5

 

 

 

 

14

нет

 

нет

класс

1

Шир.+плос

нет

 

 

15

5

ЛОЖЬ

 

 

 

 

 

 

 

16

6

ИСТИНА

 

семейство

 

 

 

 

 

17

1

неизвестн.

 

Форма листа

1

класс

Голосем.

6

 

18

нет

 

 

семейство

 

Форма листа

Чешуеобр.

 

 

19

1

ИСТИНА

чушуеобр

 

 

семейство

кипарис

1

Стек целей

После того как подготовка требуемой базы знаний завершена, можно, пользуясь указанными карточками, шаг за шагом проводить весь цикл консультации. Первый шаг любой консультации состоит в выборе цели конкретного сеанса (шаг 1). В предлагаемом примере конечной целью консультации будет определение СЕМЕЙСТВА. Для начала следует поместить карточку признака, относящуюся к СЕМЕЙСТВУ, в отдельную «колоду», которая называется стеком целей. Признак, находящийся на самом верху стека целей,— это текущая цель.

Выбор правила для оценки

Прежде всего попытаемся отыскать карточку правила, в выводе которого (т. е. в утверждениях, следующих за словом ТО) будут содержаться хоть какие-то сведения о признаках текущей цели. Подобный процесс поиска нужной информации в совокупности выводов правил, приводящий к выполнению поставленных целей, называется обратной цепочкой рассуждений (а также дедукцией от цели или рассуждениями на основе следствий). Если правило, в выводе которого содержатся при жаки текущей цели, найдено, то можно переходить к этапу «Оценка правила»; в противном случае придется обратиться к процедуре, описанной в параграфе «Запрос необходимой информации у абонента».

Оценка правила

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

  1. Правило не поддается оценке. Считается, что значение правила неизвестно, если одно или несколько выражений, входящих в условие рассматриваемого правила, отсутствуют в стеке контекста (см., в частности, правило 1 на шаге 2 в примере, проиллюстрированном таблицей 3). Дальнейшая оценка правила возможна только в случае получения дополнительной информации. Для этого карточку, содержащую первый неизвестный признак (в нашем примере признак КЛАСС), помещают в стек целей вместе с карточкой, где записано неоцененное правило. Цели, расположенные в стеке после конечной цели, иногда называют подцелями. Затем, вернувшись к этапу «Выбор правила для оценки», следует попытаться найти правило с признаком КЛАСС в секции выводов.
  2. Ложное правило. Правило ложно, если одно из утверждений на соответствующей карточке содержит выражение, противоречащее какому-то факту из стека контекста (правило 7 на шаге 6 ставит в соответствие признаку СТЕБЕЛЬ шачение ЗЕЛЕНЫЙ, которому противоречат данные, вводимые пользователем). В таком случае карточку анализируемого правила помещают в колоду сброса, после чего возвращаются к этапу «Выбор правила для оценки».
  3. Правило поддается оценке. Считается, что правило даст истинный результат, если каждое выражение в его условной части согласуется с определенным компонентом в стеке контекста (так, установлено, что правило 9 на шаге 12 приводит к правильному результату). Когда все выражения в условии истинны, утверждения, которые содержатся в выводе правила, также должны быть истинными. Данное правило было отобрано для оценки ввиду того, что его вывод *содержал текущую цель; поэтому необходимо перенести последнюю из верхней части стека целей в стек контекста. Соответстствующую карточку правила, оставленную в ходе анализа в стеке целей (правило 5 в нашем примере), следует переложить на самый верх колоды карточек с правилами, в результате чего это правило можно будет анализировать повторно. Карточка с правилом, которое мы только что оценили (правило 9), хранится вместе с карточкой признака в стеке контекста, показывая значение этого признака и позволяя проследить, каким образом оно было найдено. Эту карточку с правилом можно, кроме того, использовать для ответов на вопросы относительно полученного вывода, которые абонент может задать в дальнейшем. Если стек целей опустел, то можно считать, что задача решена. Если же там еще остались нерассмотренные цели, придется снова вернуться к этапу «Выбор правила для оценки».

Запрос к абоненту

В случае когда невозможно подобрать правило, из которого можно было бы извлечь информацию относительно рассматриваемой цели, за такой информацией приходится обращаться к абоненту (на шаге 5 мы запрашиваем необходимые сведения у абонента, ибо ни одно из правил не содержит в своих выводах признака СТЕБЕЛЬ). Именно здесь и потребуются вопросы-подсказки, которые были записаны на карточках признаков. Если на нужной карточке нет подсказки-вопроса, то абонент не сможет сообщить необходимые сведения. В таком случае все наши возможности оказываются исчерпанными, и мы вынуждены закончить консультацию, не найдя решения поставленной задачи. Это означает, что либо в анализируемых правилах скрыт какой-то дефект. либо нам не удалось разобраться в информации, которая содержится в используемой нами части базы знаний.

Если на карточке текущей цели записана та или иная подсказка, последнюю можно использовать в качестве вопроса к абоненту. После того как абонент предоставит недостающую информацию, мы можем переместить карточку текущей цели из стека целей в стек контекста. Если имеется карточка правила, на которой фигурирует эта цель, то такую карточку следует поместить на самый верх колоды карточек с правилами. Необходимо также изготовить карточку, содержащую значение, и вложить ее в стек контекста вместе с соответствующей карточкой признаков. После этого можно возвратиться к этапу «Выбор правила для оценки».

Как и почему

Нет ничего необычного в том, что у абонента в ходе консультации может возникнуть желание узнать, почему вы задаете тот или иной вопрос. Например, на шаге 13 (см. табл. 3) нам не удалось отыскать правило, которое давало бы какую-нибудь информацию относительно признака ШИРОКАЯ И ПЛОСКАЯ; поэтому мы задали абоненту наводящий вопрос о данном признаке. Прежде чем ответить на него, абонент может поинтересоваться, почему мы задали именно такой вопрос. Чтобы объяснить это, нам не обязательно -заглядывать» дальше самого верхнего правила в стеке целей. Причина, по которой мы пытаемся найти значение признака ШИРОКАЯ И ПЛОСКАЯ, заключается в том, что нам необходимо получить информацию об одном из условий, удовлетворяющих цели КЛАСС в правиле 5. Представив информацию из стека целей в виде следующей записи, мы ответим на вопрос «почему?»:

Мы пытаемся найти значение для класса дерева.
Мы уже знаем, что тип растения — дерево.
Если мы можем сказать, что форма листьев неширокая и
неплоская,
то мы будем знать, что класс дерева — голосемянные. Заметим, что для улучшения восприятия зтой информации мы заменили каждый признак его переводом.

Если затем абонент пожелает узнать: «Почему пажен КЛАСС?», то такую процедуру повторяют, переходя к следующей карточке в стеке целей. Процесс продолжается до тех пор, пока весь набор подцелей в этом стеке не будет исчерпан.

Возможно, абонента удовлетворит ваш ответ на вопрос, почему вам понадобилась информация о признаке ШИРОКАЯ И ПЛОСКАЯ; однако он может спросить: «Как вы узнаёте, что тип растения—дерево?» На такой вопрос можно ответить, найдя, где именно в стеке контекста находится данный признак. Если имеется карточка правила, которая сопутствует карточке с этим признаком, то значение, полученное в соответствии с указанным правилом, было помещено в стек контекста. Для формулировки ответа на вопрос абонента обычно используется информация, которую можно извлечь из рассматриваемого правила:

то, что растение является деревом
      было доказано с помощью правила 9.
      Это правило гласит:
Если стебель растения—древесный и прямостоящий
и растение имеет только один основной ствол,
то тип растения—дерево.

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

Предоставленная абоненту возможность прерывать сеанс консультации для того, чтобы задать вопросы «как и почему?», делает весь этот процесс более попятным и полезным как для абонента, так и для консультанта.

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

Теоретически мы можем отделить правила и признаки, содержащиеся в базе знаний, от самой дедуктивной машины, которая пользуется базой знаний для получения выводов. У нас, разумеется, есть возможность реализовать базу знаний непосредственно в программе экспертной системы, однако структура такой программы оказалась бы негибкой. Если бы мы захотели расширить базу знаний, желая ввести в нее информацию о семействах  лиан или создать другую экспертную систему, например позволяющую распознавать насекомых, то нам пришлось бы переписать всю программу. Существует, однако, иная возможность: программе вменяется «в обязанность» считывание правил, вопросов-подсказок и переводов из файла и преобразование их к виду, которым могла бы пользоваться дедуктивная машина. Именно такого подхода мы и будем придерживаться.

Перевод осуществляется с помощью гак называемого синтаксического анализатора. Это стандартная программа, которая просматривает операторы-предложения в программе, составленной на определенном языке, и выявляет, допустимы ли они на этом языке. Синтаксический анализатор способен, кроме того, трансформировать представление предложения, которым могут воспользоваться другие сегменты программы. Описываемый здесь синтаксический анализатор представляет собой реальную программу, которой можно воспользоваться, обратившись к программному обеспечению сети BYTEnet (BYTEnet - одна из локальных сетей вычислительных машин в США, с помощью которой ее абоненты могут обмениваться информацией и программами).

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

 
 

 
 
Copyright © 2008 Валеев Ильшат
Тел.:(8552) 397129
Создание и продвижение сайтов