Представление знаний. Определение Представление (representation) в работе Уинстона [Winston, 1984] определяется как "множество синтаксических и семантических. - презентация

1 Представление знаний

2 Определение Представление (representation) в работе Уинстона [Winston, 1984] определяется как "множество синтаксических и семантических соглашений, которое делает возможным описание предмета". В искусственном интеллекте под "предметом" понимается состояние в некоторой проблемной области, например объекты в этой области, их свойства, отношения, которые существуют между объектами. Описание (description) "позволяет использовать соглашения из представления для описания определенных предметов" [Winston, 1992].

3 Синтаксис Общепринятым в области искусственного интеллекта является синтаксис в виде конструкции предикат- аргумент, которая имеет форму ::= (,..., ) В этой конструкции за к-местным предикатом должны следовать k аргументов. Так, at может быть двухместным отношением, в котором в качестве первого аргумента выступает имя некоторого объекта, а в качестве второго его местонахождение (например, комната): at(робот, комнатаА)

4 Семантика Семантика представления специфицирует, как должно интерпретироваться выражение, построенное в соответствии с синтаксическими правилами, т.е. как из его формы можно извлечь какой-то смысл. Так, присваивая смысл символам at, робот, комнатаА, мы можем сказать, что выражение at(робот, комнатаА) означает: робот находится в комнате А (но не наоборот комната А находится в роботе).

5 Планировщик STRIPS Программа предназначалась для решения проблемы формирования плана поведения робота, перемещающего предметы через множество (анфиладу) помещений. Текущее состояние окружающей среды помещений и предметов в них представляется набором выражений предикат-аргумент, которые в совокупности образуют модель мира. W = { at(poбoт, комнатаА), at(ящик1, комнатаБ), at(ящик2, комнатаВ)} означает, что робот находится в комнате А и имеются два ящика, один из которых находится в комнате Б, а второй в комнате В.

6 Действия, которые может выполнить робот, принимают форму операторов, приложимых к текущей модели мира. Эти операторы позволяют добавить в модель некоторые факты (сведения) или изъять их из модели. Например, выполнение операции "Переместить робот из комнаты А в комнату Б" в модели мира приведет к формированию новой модели W. При этом факт at (робот, комнатаА) будет изъят из модели, а добавлен факт at (робот, комнатаБ). В результате новая модель мира будет иметь вид W' = { at (робот, комнатаБ), at (ящик1, комнатаБ), аt (ящик2, комнатаВ)}

7 Таблицы операторов Допустимые операции, такие как перемещение робота из одной комнаты в другую или проталкивание объектов, кодируются в таблице операторов. Пример элемента этой таблицы, соответствующий операции push (толкать): push(X, Y, Z) Предварительные условия at(poбoT, Y), at(X, Y) Список удалений at (робот, Y), at(X, Y) Список добавлений at (робот, Z), at(X, Z) Здесь выражение push(X, Y, Z) означает, что объект X выталкивается (роботом) из положения Y в положение Z

8 С точки зрения программиста переменные X, К и Z в определении оператора, заданном элементом таблицы, это аналоги формальных параметров в определении процедуры, которая соответствует такому действию: "Вытолкнуть какой-либо объект из какого-либо положения в любое другое положение, если имеют место заданные предварительные условия; затем удалить формулы, указанные в списке удаления, и добавить формулы, указанные в списке добавления".

9 Пример как готовиться к ленчу с потенциальным клиентом. Для этого, во-первых, нужно иметь в своем распоряжении определенную сумму наличных денег, чтобы расплатиться, во-вторых, нужно проголодаться, поскольку речь идет о приеме пищи. Сформулированные условия можно рассматривать в качестве предварительных для достижения цели "ленч". Однако обладание известной суммой наличных денег нельзя рассматривать как естественное состояние клиента. Сначала нужно получить их в банкомате, что, в свою очередь, требует передвижения. Следовательно, нужно добавить в таблицу операторов еще два элемента at cash mashine (передвижение к банкомату) и have money (получение наличности).

10

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

12 метод "средство анализ завершения метода "средство анализ завершения", состоит в том, чтобы с каждой новой операцией отличие между текущим состоянием и целевым уменьшалось, т.е. каждая очередная операция должна приближать нас к цели. Но это предполагает включение в рассмотрение некоторой меры для оценки "расстояния" в пространстве состояний. Такая мера очень походит на оценочную функцию. Если очередная цель сформулирована в виде at(ящик1, комнатаА), а ящик находится в комнате Б, то перемещение робота из комнаты А в комнату В никак не "приблизит" текущее состояние к целевому. А вот перемещение робота из комнаты А в комнату Б уменьшит расстояние между текущим и целевым состоянием, поскольку робот теперь сможет на очередном шаге вытолкнуть ящик из комнаты Б в комнату А.

13 MYCIN Используется для лечения заболеваний крови (1) База знаний содержит фактические знания, касающиеся предметной области, и сведения об имеющихся неопределенностях. (2) Динамическая база данных пациентов содержит информацию о конкретных пациентах и их заболеваниях. (3) Консультирующая программа задает вопросы, выводит заключения системы и дает советы для конкретного случая, используя информацию о пациенте и статические знания. (4) Объясняющая программа отвечает на вопросы и дает пользователю информацию о том, на чем основываются рекомендации или заключения, сформулированные системой. При этом программа приводит трассировку процесса выработки рекомендаций. (5) Программа восприятия знаний служит для обновления знаний, хранящихся в системе, в процессе ее эксплуатации.

14

15 База знаний системы MYCIN База знаний системы MYCIN организована в виде множества правил в форме если условие1 и... и условиет удовлетворяются то прийти к заключению1 и... и к заключению n Эти правила преобразованы в операторы языка LISP

16 Пример Вот как выглядит перевод на обычный язык типичного правила MYCIN: ЕСЛИ 1) организм обладает грамотрицательной окраской, и 2) организм имеет форму палочки, и 3) организм аэробный, ТО есть основания предполагать (0,8), что этот микроорганизм относится к классу enterobacteriaceae.

17 Помимо правил, в базе знаний MYCIN также хранятся факты и определения. Для их хранения используются разные структурные формы: простые списки, например списки всех микроорганизмов, известных системе; таблицы знаний с записями об определенных клинических показаниях и значениях, которые эти показания имеют при разных условиях; примером может служить информация о форме микроорганизмов, известных системе; система классификации клинических параметров соответственно контексту, в котором эти параметры рассматриваются, например являются ли они свойством (атрибутом) пациентов или микроорганизмов.

18 Структуры данных в языке LISP основной структурой данных в нем является список; программы на этом языке также имеют списочную структуру; его базовыми операциями являются операции над списками. Базовым блоком в структуре данных языка LISP является символическое выражение. Простое символическое выражение использует атомарные символы, или атомы строки буквенно- цифровых символов, которые начинаются с буквы, например WOMBAT.

19 В LISP организованы программы и выражения в виде списка. Например, список (+ X Y) представляет математическое выражение в форме ( ),

20 Примитивы в LISP Пусть s множество символических выражений. Можно, например, записать: Е(Х, Y): S x S -> {Т, NIL} Это означает, что Е является функцией двух аргументов, причем оба аргумента символические выражения из множества S, которые могут принимать значение либо Т, либо NIL.

21 (1)Е(Х, Y): S x S -> {Т, NIL} проверяет, равны ли два атома. (2)А(Х): S -> {Т, NIL} проверяет, является ли символическое выражение атомом. (З)Н(Х): S -> S извлекает голову символического выражения, которое не является атомом; если х атом, то результат функции не определен. (4) Т(Х): S > S извлекает хвост символического выражения, которое не является атомом; если х атом, то результат функции не определен. (5)С(Х, Y): S х S > S формирует символическое выражение; если А и в являются символическими выражениями, то можно сформировать новое символическое выражение (А. В).

22 Фактически система, состоящая из трех компонентов (1) единственного атома NIL; (2) условного выражения, проверяющего равенство, в форме if E(X, NIL) then... else... 3) функций Н(Х), Т(Х), С(ХД) к которым добавлена операция композиции функций, вполне позволяет реализовать машину Тьюринга (см.

23 NULL это предикат, который проверяет, не пуст ли список, EQ предикат, который проверяет равенство двух атомов, FIRST функция, которая возвращает головной элемент списка, REST функция, которая возвращает хвост списка

24 Сопоставление с образцом Одним из ключевых компонентов в большинстве программ искусственного интеллекта является анализатор соответствия (pattern matcher) компонент, который некоторым образом сравнивает поступающие на его вход списки (или другие структуры данных) с имеющимися символическими образцами и таким образом выполняет распознавание входных данных

25 На языке LISP несложно разработать простой анализатор соответствия, который будет сравнивать два ординарных списка (т.е. списка, на имеющего подсписков в качестве элементов) и возвращать значение TRUE, если один из них, sample (пример), можно представить как реализацию другого pattern (образец). Предполагается, что образец может иметь любую конечную длину и содержать любое количество символов универсальной подстановки(?)

26 Текст программы (defun match (sample pattern) (cond ((and (null sample) (null pattern)) T) ((or (null sample) (null pattern)) NIL) ((eq (first pattern ?)) (match (rest sample) (rest pattern))) ((eq (first sample) (first pattern)) (match (rest sample) (rest pattern))) (T NIL)) )

27 Системы, основанные на знаниях Канонические системы Системы порождающих правил для решения проблем Управление функционированием интерпретатора

28 Канонические системы Каноническая система это разновидность формальной системы, основанной на следующих компонентах: алфавит А, из символов которого формируются строки; некоторое множество строк, которые рассматриваются как аксиомы, множества порождений в форме а1$1... am$m->b1$'1...bn$'1...bn$'n. Где (I) каждое ai и bi; есть фиксированная строка; (II) а1 и am, часто есть нуль; (III) некоторые или все из ai или bi могут представлять собой нуль; (IV) каждое $i является переменной строкой, которая также может быть нулем; (V) каждое $i заменяется определенным $'i.

29 Пример Пусть А алфавит {а, b, с}, а аксиомы суть: а, b, с, аа, bb, cc. Тогда следующие порождения сгенерируют все палиндромы, базирующиеся на этом алфавите, приняв за отправную точку имеющиеся аксиомы: (Р1)$->а$a (Р2) $ -> ab$ab (РЗ) $ -> с$с.

30 чтобы сгенерировать bacab, нужно применить Р1 к аксиоме с, а затем Р2 к результату. Другими словами, приняв с в качестве аксиомы, можно вывести из нее теорему аса и добавить ее к имеющимся аксиомам. Затем из аса можно вывести новую теорему bacab. Обратите внимание, что эта последовательность порождений не обладает свойством коммутативности, т.е. если применять те же правила, но в ином порядке, получится совсем другой результат. Например, если к аксиоме с применить сначала правило Р2, а затем Р1, то получим abcba.

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

32 Смысл порождений Пусть задано порождающее правило в форме а1$1...am$m-> b1$'1...bn$'n В нем a1$1... аm$m часто называют антецедентом (antecedent) правила, а b,$'1... bn$'n консеквентом (consequent) правила, по аналогии с условным выражением логики высказываний.Условный оператор обычно записывается в виде p U q1 что означает, "если р, то q", например "если вы упали в реку, то будете мокрым".

NP+ VP имеет сле" title="Правило в форме Х->У ( X U Y) говорит о том, что можно записать, сгенерировать или породить консеквент У при заданном анцеденте X. Правила переписывания в теоретической лингвистике называются "порождениями", поскольку правило вида S->NP+ VP имеет сле" class="link_thumb"> 33 Правило в форме Х->У ( X U Y) говорит о том, что можно записать, сгенерировать или породить консеквент У при заданном анцеденте X. Правила переписывания в теоретической лингвистике называются "порождениями", поскольку правило вида S->NP+ VP имеет следующую интерпретацию: "один из способов сформировать предложение S состоит в том, чтобы взять существительное (NР) и добавить к нему глагол (VP)". NP+ VP имеет сле"> NP+ VP имеет следующую интерпретацию: "один из способов сформировать предложение S состоит в том, чтобы взять существительное (NР) и добавить к нему глагол (VP)"."> NP+ VP имеет сле" title="Правило в форме Х->У ( X U Y) говорит о том, что можно записать, сгенерировать или породить консеквент У при заданном анцеденте X. Правила переписывания в теоретической лингвистике называются "порождениями", поскольку правило вида S->NP+ VP имеет сле">