Лекция 9

1.6 Организация работы

В процессе функционирования СИИ можно выделить три режима: 1 - при­обретения (редактирования) знаний, 2 – консультации и 3 – непосредственного  решения задачи. Рассмотрим первые два режима.

В режиме редактирования знаний пользователь формирует и мо­дифицирует базу знаний, т.е. определяет и вводит правила решения задачи (задач) для данной предметной области. Каждое правило ха­рактеризуется набором атрибутов, определяющих ее структуру. Так, ес­ли, например, атрибутами являются А.В.С....К.Е5, то примерами правил являются следующие:

IF A = a1 & B = b1 & C = c1 & ...

     THEN RES = r1

IF A = a2 & B = b2 & C = c2 &

     THEN RES = r2

и т.д.

Система ведет диалог, задает вопросы и дает возможные ответы в форме меню. Результат может представлять диалог, совет или некото­рое числовое (символьно-числовое) выражение.

Рекомендуемые материалы

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

*  вставка и удаление атрибутов;

*  переименование атрибутов и изменение их значений;

*  изменение и добавление вопросов и текстов объяснения;

*  создание правил;

*  просмотр базы знаний;

*  поиск атрибутов и правил; и др.

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

* в значительной мере устраняются отрицательные факторы, свя­занные с взаимодействием эксперта и инженера по знаниям;

* систематизируется процесс ввода знаний;

* появляется возможность редактировать базу знаний неограни­ченное число раз до тех пор, пока результат не будет удовлетво­рять и эксперта, и инженера по знаниям;

* уменьшаются нежелательные эффекты, связанные с вводом не­верной, противоречивой или синтаксически некорректной информации;

* программы редактирования знаний организуют мышление эк­сперта в нужном направлении.

В режиме консультации СИИ осуществляет процесс решения задачи, сформулированной пользователем.

Пример. Познакомимся вкратце с организацией режима консуль­тации в системе Expеrt PRIZ (позднее в этом пособии эта система будет рассмотрена подробно). Прежде всего пользователь выбирает из пред­лагаемого меню тему консультации, например, выбирается задача по выбору скорости автомобиля в зависимости от технических и климати­ческих данных.

Далее система задает пользователю вопрос:

"Является ли дорога ... ?"

и указывает список возможных опций-ответов:

- сухой;

- мокрой;

- скользкой.

Если пользователь выбирает опцию "сухая", то система выводит на экран текст очередного вопроса:

"Что можно сказать о видимости ? Является ли она ... ?"

- до 100 м;

- более 100 м.

Если пользователь выбирает опцию "до 100 м", то система выдает ответ:

"Рекомендуется не превышать 80 км/ч".

После завершения консультации можно просмотреть на экране дисплея возможное объяснение полученного решения задачи. Так, на эк­ране в ответ "да" на вопрос:

"Объяснения ? (да/нет)"

будет выведено, например, следующее объяснение:

"При таких условиях длина тормозного пути не превосходит 2 - 3 м"

Процедуры. В режиме консультации система Expert PRIZ позволяет вычислять значения одних переменных по другим, а также решать урав­нения. Например, зная скорость (v) и время (t), можно записать уравне­ние для расстояния, пройденного за время t:

S = v × t

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

Таким образом, в отличии от традиционных программ СИИ в ре­жиме консультации не только исполняет предписанную последователь­ность операций, но и предварительно формирует задачу, а также пре­доставляет пользователю:

- возможность вмешиваться в процесс решения

- получать объяснения полученного решения.

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

1.4. Инструментальные средства создания экспертных систем

Средства построения СИИ включают:

· языки программирования

· языки инженерии знаний

· вспомогательные средства

· средства поддержки.

Рассмотрим эти средства.

1.4.1. Языки программирования

В качестве языков программирования, используемых дня построе­ния СИИ, наиболее широко используются Си, Лисп, Пролог, Паскаль. Особенно следует отметить языки Лисп и Пролог в первую очередь в силу наличия в них встроенных средств для организации интеллектуальных процедур (унификация, альтернативный поиск, возврат (backtracking), обработка символьной информации, возможности реали­зации функций базы данных). Языки программирования делятся на три класса:

· императивные языки;

· функциональные языки;

· логические языки.

Императивные языки (Паскаль, Си, Форт, Бейсик и др.) позволяют создавать последовательности команд, выполняемых в порядке их рас­положения. Императивная программа одинаково выполняется при каждом последующем прогоне. Среди императивных языков очень по­пулярен Си. Подобно языку Паскаль он является структурированным языком, удобным для управления базой знаний, однако лучше Паскаля подходит для написания пользовательского интерфейса. Программы, написанные на Си, выполняются очень быстро и обеспечивают полный набор сервисных функций для управления дисплеем.

Декларативные языки используются для написания спецификаций некоторой предметной области. Спецификация характеризует некото­рое множество объектов предметной области и заданные на нем отно­шения между объектами. Декларативные языки делятся на логические и функциональные.

Наиболее важным среди функциональных языков является язык Лисп. Лисп основан на функциональном - исчислении Черча. На его базе разработаны мощные инструментальные оболочки экспертных сис­тем KEE, LOOPS, ART, S.I и др. Такие широко распространенные вер­сии языка Лисп как Интерлисп и Мехлисп имеют развитые редакторы и средства отладки.

Лисп был изобретен в 1956 г. Мак Карта. С момента изобретения Лисп трансформировался с языка чисто символьной обработки в язык общецелевого назначения. Большинство лисповских программ записы­ваются в форме функций: значения одних функций являются аргу­ментами других.

Например, если PLUS - функция сложения, то выражение X + Y по­лучает в Лиспе вид

(PLUS X Y),

а выражение (Х + Y + Z) принимает форму

(PLUS X (PLUS Y Z))

Аргументы и имена функций разделяются запятыми или пробела­ми.

Присваивание в форме X = а имеет вид

(SET X a).

Для записи условных выражений используется функция COND, первый аргумент которой представляет условную часть выражения (часть "ЕСЛИ..."), а второй - операционную часть (часть "ТО..."). Например,

(COND ((ZEROP S) (SET X 5)))

представляет условное выражение, условная часть "ЕСЛИ..." которою соответствует (ZEROP S), а операционная (SЕТ X 5). ZEROP есть функция сравнения с нулем. Приведенное выше выражение проверяет, равно ли S нулю, и в случае положительного результата проверки при­сваивает X значение 5.

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

АТОМ - проверяет, является ли аргумент атомом или списком

NULL - проверяет, является ли аргумент связанной или несвязанной переменной

EQUAL - проверяет равенство двух аргументов

GREATERP - проверяет, что один аргумент больше второго.

Пользователь может определять свои функции с помощью l - выражений Черта, например:

(LAMBDA (A B) (DIFFERENCE (TIMES A A) (TIMES B B)))

здесь А, В - аргументы функции, которая сама имеет следующую струк­туру:

(DIFFERENCT (TIMES A A) (TIMES B B))

где DIFFERENCE - функция вычитания X - Y;

      TIMES - функция умножения X * Y.

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

X² - Y².

Для того, чтобы выражение объявить как функцию, используется новая функция - DEFUNE. В общем случае, если f_i - l-выражение для функции f_i, то ее объявление таково:

(DEFUNE (имя_функции (f_i))

Так, в случае выше имеем следующее объявление функции FUN 1 с двумя аргументами:

(DEFUNE (FUN1 (LAMBDA (A B) (DIFFERENCE (TIMES A A) (TIMES B B))))

Теперь, например, подстановка FUN1 (5 3) дает в результате 16.

Важнейшее место в Лиспе занимают операции над списками, ос­новными из которых являются функции CAR. (выделяющая первый эле­мент списка), CDR (выделяющая остаток списка после удаления перво­го элемента) и CONS (соединяющая два списка).

Например, если:

X есть (2 6 4 7)                         то (CAR X) есть 2

X есть (3 2 1)                то (CDR X) есть (2 1)

X есть ((2 6)(4 7)                       то (CDR X) есть (4 7)

X есть (5)                      то (CDR X) есть NIL.

X есть (2 4) и Y есть (6 7), то (CONS X Y) есть ((2 4) (6 7))

NIL - специальное обозначение для "лжи" или пустой список.

Языки программирования, подобные языку Лисп, представляют максимальную гибкость разработчику СИИ, но не подсказывают ему, как представлять знания и строить механизмы их обработки. Это ограни­чение в значительной мере снято в языке Пролог. Язык Пролог "реализует" математическую логику в программировании согласно идее, предложенной А. Кольмероэ и Р. Ковальским. Собственно, Пролог базируется на разновидности исчисления предикатов -так называемом клаузальном исчислении Хорна.

Клоз, это формула вида

"x₁ "x₂ ... "x_s (L₁ Ú ... Ú L_m)                                    (1.48)

где L_i - атомарная формула (литерал), ,

      x_j - переменная, входящая в L_i, j = .

Среди атомарных формул L_i выделяют позитивные (без отрица­ния) и негативные (с отрицанием) литералы:

             (1.49)

или с учетом эквивалентности имеем

"x₁ ... "x_s (A₁ Ú ... Ú A_k ¬ B₁ & B₂ & ... & B_n)                    (1.50)

Определение. Программным клозом называется формула

B₁, B₂, ..., B_n ¬ A,

содержащая ровно один позитивный литерал А, называемый головным (или просто заголовком). Часть клоза B₁, B₂, ..., B_n называется телом клоза (запятая, разделяющая литералы В, эквивалентна логической конъюнкции). Как видим из последнего представления, программный клоз - это логическая формула, имеющая форму продукции "ЕСЛИ- ТО", где часть "ЕСЛИ" соответствует телу клоза, а часть "ТО" - заголовку клоза.

Определение. Фактом называется клоз без тела, т.е. ® А или еще проще: А.

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

Определение. Целью называется клоз без заголовка:

B₁, B₂, ..., B_n  ®.

Предикатные формулы B₁, B₂, ..., B_n входящие в цели, называются под­целями.

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

A(U₁, ..., U_nk):-

               B₁ (X₁, ..., X_n1),

               B₂ (Y₂, ..., Y_n2),

                           ....

               B_m (Z₁, ..., Z_nm),

где символ " :- " стоит вместо "¬", а символ запятая "," соответствует логической конъюнкции.

Выполнение правила заключается в доказательстве его заголовка (головного литерала). Этот процесс заканчивается в случае успеха нахождением подходящей интерпретации для правила. Для того чтобы доказать головную формулу. Пролог последовательно доказывает каждую формулу в теле правила. Так, чтобы доказать формулу A(U₁, ..., U_nk), последовательно доказываются формулы B₁(...), B₂(...), ..., B_m(...). Для каждой из этих формул B_i(...) в свою очередь имеется множество правил, где B_i(...) является заголовком. Рассмотрим следующие правила

(1) площадь (X, Y) :-

     фигура (X, Y),

     write (²X=², X, ²Y=², Y).

(2) фигура (квадрат, ²сторона * сторона²).

(3) фигура (круг, ²p/2 * радиус * радиус²).

(4) фигура (треугольник, ²высота * основание * 1/2²).

(5) фигура (_, ²не известно²).

Пусть целью будет

площадь (круг, Z).

Такая цель означает, что нужно найти значение Z, соответст­вующее площади круга. Пролог пытается сначала нагой правило, в заголовке которого стоит литерал "площадь". В данном случае правило с заголовком указанного вида таково:

(1) площадь (Х, Y) - фигура (Х, Y).

Аргументы обеих формул в этом правиле совпадают и являются пе­ременными (которые принято записывать с заглавных букв). Первый шаг, выполняемый Прологом, это передача значений для X и Y из цели:

Х = круг, Y = Z.

В нашем случае X получает конкретное значение "круг", в то время как запись Y = Z просто устанавливает факт равенства двух перемен­ных. Как только переменная Y получает значение, Z будет присвоено то же значение. Теперь правило (1) трансформировалось в правило сле­дующего вида:

(1’) площадь (круг, Y):- фигура (круг,Y).

Пролог обязан запомнить вид этого правила, которое равносильно следующей записи:

если (фигура(круг, Y)), то (площадь(круг, Y)).

Теперь Пролог формирует новую цель:

фигура (круг, Y).

Для этой новой цели он ищет подходящее правило. В нашей про­грамме таких правил 4 (правила (2) - (5)). Эти правила имеют усеченный вид: в структуре "если (...) то (...)", как видим, в них отсутствует часть "если (...)". С точки зрения логики это означает, что независимо от исходных условий, записываемых в части "если (...)", эти правила ут­верждают истинность частей "то (...)". Следовательно, доказывать такие правила не надо.

Итак, для цели "фигура (круг, Y)" выбирается правило

фигура (квадрат, "сторона * сторона'').

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

круг = квадрат; Y = " сторона * сторона ".

Учитывая, что "круг" и "квадрат" не переменные (первый символ "к" - не заглавный). Пролог вместо присваивания сравнивает их. Ре­зультат сравнения - "ложь". Следовательно, правило (2) использовать нельзя. Однако, есть еще правила с заголовком "фигура". Поэтому Про­лог выбирает следующее по порядку:

(3)  фигура (круг, "p /2*радиус*радиус").

Текущая цель такова:

фигура (круг, Y).

Результат присваивания значений:

круг = круг; Y = "p /2*радиус*раднус".

Цель доказана, поскольку доказывать правило (3) не надо, о чем было сказано выше. Поскольку выше было принято, что Y = Z, то Z ав­томатически получает значение Z = "л /2*радиус*радиус "

Стандартный предикат write выведет найденные значения, напеча­тав:

X = круг, Y = "p /2*радиус*радиус".

Из данного примера мы видим, что выбор подходящего правила для доказательства цели не всегда возможен из-за несоответствия зна­чений параметров.

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

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

нравится (Х, апельсин ).

Допустим, в базе данных имеются следующие факты

® нравится ("Федор" яблоко).

® нравится ("Петр", апельсин).

Пролог выполнит сопоставление аргументов одноименных правил:

X « " Федор "

апельсин « яблоко

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

® нравится ( "Петр", апельсин" ).

В этом случае сопоставление аргументов приводит к следующему результату:

X « "Петр"

апельсин « апельсин.

Это сопоставление совместно, поскольку константы совпадают. В результате свободной переменной X присваивается значение "Петр".

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

Можно выделить следующие шаги выполнения Пролог-програм­мы:

(1)  - выполнение подходящего правила для текущей цели;

(2)  - передача и согласование параметров цели и правила;

(3)  - в зависимости от исхода (2) определение новой цели или возврат к предыдущей цели с отменой значений для переменных, полученных в результате шага (2) для последней цели;

(4)  - создание точек ветвления в программе;

(5)  - восстановление переменных при возврате.

В качестве иллюстрации рассмотрим следующий пример.

(1) нравится ("Пете", X1 ):-

     нравится ("Коле", X1),

     нравится ("Вите", X1).

(2) нравится ("Коле", "рыбалка").

(3) нравится ("Коле", "футбол").

(4) нравится ("Вите", "рыбалка").

(5) нравится ("Сергею", "музыка").

(6) нравится ("Саше", "хоккей").

Нас интересует вопрос, что нравится Пете? Этот вопрос в том или ином виде сводится к следующей записи:

нравится ("Пете",?),

где знак "?" используется для определения объекта, который подлежит поиску.

В Прологе вместо знака "?" используется обозначение переменной. Мы могли задать системе и двойной вопрос:

нравится ("Пете", X), нравится (Y, "хоккей").

Эта сложная цель требует найти такой X, который нравится Пете, и такой Y, которому нравится хоккей. Такая сложная цель будет выпол­нена, если будет доказан каждый входящий в нее предикат.

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

В нашем примере сначала доказывается первая цель: нравится ("Пете", X). Система ищет подходящее правило для этого предиката и выбирает первое такое правило из числа неопробованных:

нравится ("Пете", X1):-

нравится ("Коле", X1),

нравится ("Вите", X1).

Для того чтобы доказать это правило, необходимо доказать два предиката:

  нравится ("Коле", X1)

и

  нравится ("Вите", X1).

Система формирует новую текущую цель: нравится ("Коле",Х1) и аналогичным образом просматривает подходящие правила. Правило (1) не подходит для этой цели, поскольку неудачей заканчивается про­цедура сопоставления аргументов вызывающего и вызываемого преди­катов:

нравится ("Коле", X1)

нравится ("Пете", X1) /* ("Коле" = "Пете")*/.

Будет выбрано правило (факт) (2):

нравится ("Коле", "рыбалка").

В результате переменная X1 получает значение

X1 = "рыбалка".

Система формирует новую текущую цель

нравится ("Вите", "рыбалка").

Эта цель доказывается с помощью правила (4). Итак, Пролог до­казал предикат нравится ("Пете", "рыбалка"). Таким образом, в исход­ной цели нравится ("Пете", Х) переменная X получает значение Х = "рыбалка". Аналогичным образом доказательство предиката

нравится (Y, "хоккей")

завершается присваиванием значения Y = "Саше"

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

Алгоритм интерпретатора Пролога заключается в следующем. Если список целей пуст - работа завершается успехом. Если список це­лей не пуст,' то интерпретатор продолжает работу, выполняя процедуру 'ПРОСМОТР'.

Процедура 'ПРОСМОТР'. Правила программы последовательно просмаливаются от начала к концу до обнаружения первого правила С, такого, что заголовок С сопоставим с первой целью G1. Если такого правила обнаружить не удается, то восстанавливается предыдущий спи­сок целей и для него выполняется процедура 'ПРОСМОТР', начищая с последнего испробованного правила С. Если список целей не пуст, а все правила для первом цели в самом первом списке целей проверены, то алгоритм завершается общей неудачей. Если С найдено и имеет вид

H:- B₁, ..., B_n,

то переменные в С переименовываются, чтобы получить такой вариант С' предложения С, в котором нет общих переменных со списком G₁, ..., G_m.

Пусть С' - это

Сопоставляется G1 с Н'. Пусть S - результирующая конкретизация переменных. В списке G₁, ..., G_m цель G₁ заменяется на список , что порождает новый список целей:

Рекомендуем посмотреть лекцию "Лекция 6".

Заметим, что если С - факт, то из списка целей удаляется первая цель G1.

Переменные в новом списке целей устанавливаются согласно интерпретации S, что порождает новый список целей

Старый список L₀ = G₁, ..., G_m, сохраняется, а система переходит к доказательству нового списка L₁ , т.е. осуществляет переход к процеду­ре 'ПРОСМОТР'.

Мы обратимся к рассмотрению средств языка Пролог для разработки механизмов СИИ во второй части книги. Читателю потребуется 6азовый набор сведений о системе TURBO-PROLOG 2.0, помещенный в Приложении 2. Чтение этого приложения может быть отложено до гла­вы, посвященной разработке базовых механизмов учебной СИИ во вто­рой части пособия.

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