Logo GenDocs.ru


Поиск по сайту:  


Лекции - Архитектура систем искусственного интеллекта - файл 1.doc


Лекции - Архитектура систем искусственного интеллекта
скачать (775.5 kb.)

Доступные файлы (1):

1.doc776kb.18.11.2011 00:32скачать

содержание

1.doc

  1   2   3   4   5
Реклама MarketGid:
АРХИТЕКТУРА СИСТЕМ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА.

База знаний и данных. Понятие модели. Логические модели. Модели знаний на основе продукций. Фреймовая модель знаний. Семантические сети.

Машина вывода. Понятие формальной системы. Примеры стратегии вывода. Как функционирует машина вывода.

Извлечение знаний и обучение. Извлечение знаний от многих экспертов. Проблема непротиворечивости формализованной базы знаний. Обучение системы. Интерфейс с пользователем.

Инструментальные средства создания экспертных систем. Языки программирования. Языки инженерии знаний и инструментальные системы.
^

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


1. АРХИТЕКТУРА СИСТЕМ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

СИИ являются результатом логического развития СОД, которую можно определить как интеллект.

Систему принято считать интеллектуальной, если в ней реализованы три группы основных функций:

  1. представления и обработки данных;

  2. рассуждения;

  3. общения с пользователем на естественном языке.

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

  1. накопление знаний о предметной области;

  2. классификация знаний по критерию прагматической полезности и непротиворечивости;

  3. структурирование знаний в направлении их использования в конкретной области;

  4. автоматическое поддержание базы знаний при ее пополнении;

  5. получение и обработка знаний от нескольких экспертов.



  1. инициализация процессов получения новых знаний;

  2. соотнесение новых знаний со старыми;

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

  4. обобщение знаний на основе более частных знаний;

  5. логическое планирование своей деятельности;

  6. осуществление вывода на основе рассуждений по аналогии и т.п.



  1. общение на естественном языке (или подмножестве профессионального языка);

  2. обучение;

  3. адаптация в процессе взаимодействия к специалистам разной квалификации;

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

  5. формирование по запросу пользователя объяснений своей деятельности;

  6. документирование информации в форме, необходимой пользователю.

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

Рассмотрим обобщенную структурно-функциональную схему СИИ (рис.1).

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

В приведенной схеме можно выделить два основных блока:

  • машины баз знаний;

  • решатель

и вспомогательные блоки: систему общения на ЕЯ, рецепторы и эффекторы.

Это деление на блоки абсолютно четко соответствует обобщенным функциям СИИ.

МБЗ реализуют первую функцию СИИ – функцию представления и обработки знаний и состоит из блоков:

^ База фактов содержит факты, носящие конкретный характер:

а) факты, характеризующие текущую ситуацию, текущее состояние;

б) факты, характеризующие уже имевшие место ситуации (опыт).

^ База правил содержит элементарные выражения, называемые в теории ИИ продукциями. Здесь содержатся закономерности, представляющие, как правило, причинно-следственные связи предметной области. Это предложения типа ЕСЛИ–ТО–ИНАЧЕ.

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

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

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

  • сведения о том, как представляются единицы информации различного типа;

  • сведения о том, как взаимодействуют отдельные части системы;

  • сведения о том, как получено решение любой конкретной задачи.

Другими словами хранятся на том или ином уровне подробности описания самой системы, ее возможностей и способов функционирования.

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

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



^ Монитор баз знаний – это программа управления всеми базами, входящими в базу знаний. Эта программа организует их взаимодействие между собой.

Т.о., база фактов – это база данных, а база правил, база закономерностей, база целей – составляют основу базы знаний предметной области.

МДВ реализует вторую функцию СИИ – функцию рассуждений, она состоит из 7 элементов:

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

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

В процессе индуктивного и дедуктивного выводов возможны ошибки. Чтобы их устранить необходимо использовать определенные указатели правдоподобия сформированных правил, реализуемых в БПВ.

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

Блок планирования – этот блок связан со всеми БМЗ, планирует процесс вывода в зависимости от конкретной ситуации.

^ Монитор решателя – программа, управляющая всеми блоками решателя.

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

^ 1.1 База знаний и данных

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

Переменная - это объект с априорно неизвестным значением. Часто отождествляют все три понятия:

<переменная> = <о6ъект> = <неизвестное значение>.

Переменная может быть связанной и несвязанной (свободной). В последнем случае переменной не приписано какое-либо конкретное значение. Естественно рассматривать само значение как другой объект оп­ределенного типа. С этой точки зрения связанная переменная представляет пару <V1, V2> с исходным объектом V1, представляющим имя переменной, и производным объектом V2, представляющим значение пе­ременной. При этом, как правило, не имеет значения конкретный вид объекта V2. Так, пара <Х, "Петр"> интерпретируется как переменная X, связанная со значением символьной константы "Петр".

Некоторые трудности возникают, когда V2 представляет так называемое автоопределение (рекурсивное определение), например

<Х, Х2 - Х +1 >,

или, в более обычной форме X = Х2 - X + 1. Если последнее интерпретируется как уравнение, то можно вывес­ти, что X = 1.

Если последнее требуется интерпретировать как подстановку (для Х), то следовало писать

< Х, X2 - Х +1>

или <X, Y2 - Y + 1>.

В последнем случае необходимо обеспечить допустимость использования замены. Например, недопустима замена X = Y в формуле ln(X - Y) = ln(X + Y), что приводит к ln 0 = ln 2Y.

Константа, очевидно, может быть представлена как пара <С, С>, где С суть конкретный объект. Обозначение <V, V> со связанной пе­ременной V суть также пример константы. Характеристиками знаний являются следующие.

^ 1. Внутренняя интерпретируемость знаний отождествляется нами с наличием некоторой функции (способа) связывания переменных с теми или иными значениями или иначе, - способом порождения пар <Vi, Vj>. Такая функция или способ называется также интерпрети­рующей функцией (или просто интерпретацией).

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

^ 2. Вторая характерная черта знаний - рекурсивная структурирован­ность и связность. Рекурсивная структурированность определяется через понятие концепта. Концепт есть семантическое целое понятий. Понятие Р1 и Р2 образуют семантическое целое, если имеет место какое-то из перечисленных условий:

(А) Р1 и Р2 связаны друг с другом как отношение и один из его аргументов;

(В) Р1 и Р2 связаны друг с другом как действие и его носитель или субъект;

(С) Р1 и Р2 связаны друг с другом как функция и ее аргумент (объект и его свойство).

По индукции следует, что множество P = {P1, P2, ..., Pn} понятий образует семантическое целое, если каждый Рi в Р образует семанти­ческое целое как минимум с одним из Рj, где Pj  P/{Pi}.

Концепт С есть упорядоченное множество Сi , где Сi - семантичес­кое целое, содержащееся в семантическом целом, представляющем С.

Рассмотрим концепт С: "Студент Петр сдает экзамен по химии". Здесь можно выделить следующие семантические целые:

С1 = <Студент Петр> (объект Петр; свойство -студент)

С2 = <Петр сдает экзамен> (объект Петр; действие - сдает экзамен)

С3 = <Экзамен по химии> (объект экзамен; свойство - по химии)

Таким образом, исходный концепт ^ С образован простым объе­динением

C = C1  C2  C3.

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

C = C1  C2  C3 = C2  C1  C3 = C3  C2  C1 и т.д.

Рекурсивность операции объединения показывается элементарно через тождество

  X = X

{a}  X = {a, X} (1.2)

{a, Y}  X = {a}  {X  Y}

^ 3. Семантическое пространство с метрикой. Это свойство знаний связано с возможностью их измерения в системе оценок (метрики) [истинно, ложь]. В системе с нечеткой логикой используется бесконечное множество оценок истинности знания. Например, заключение ЭС вида "завтра ожидается дождь с вероятностью 0,8" не является ни строго истинным, ни строго ложным, т.е. характеризуется определенной степенью правдоподобия.

^ 4. Активность знаний. Это свойство знаний "адаптироваться" под изменяющиеся факты (т.е. способность к обучению и самокоррекции).

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

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

6. Независимость означает невозможность вывода единого знания из другого формальным способом.

7. Ситуативность. Наличие ситуативных связей определяет совмести­мость тех или иных знаний, хранимых в памяти. В качестве таких связей могут выступать отношения времени, места, действия, причины и пр. Для нас важны модели представления знаний в ЭВМ. При этом основными требованиями к представлению знаний являются однородность представления, простота понимания, непротиворечи­вость и полнота. В существующей практике получили наибольшее распространение следующие модели знаний:

  • логическая;

  • модель, основанная на использовании правил (продукционная модель);

  • фреймы;

  • семантические сети.

^ 1.1.1 Понятие модели

В математике моделью (или реляционной системой) называется не­которое множество М с заданным на нем набором отношений {r1, r2, ..., rn}. Как известно, отношение математически пред­ставляется в следующей форме: имя_отношения (список_аргументов).

Когда идет речь о модели знаний, то отнюдь необязательно, чтобы множество ^ М было однородно (состояло только из объектов одной при­роды). Например, отношение "быть владельцем (х, у)" устанавливает, что х есть владелец у, а экземпляр такого отношения

быть_владельцем (Иван, книга)

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

^ 1.1.2. Логические модели

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

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

Язык логики предикатов задается следующим образом. Алфавит содержит следующие классы символов:

  1. переменные, обозначаемые через x, y, z, v, u, ...,

  2. константы, обозначаемые посредством a, b, c, d, ...,

  3. функциональные символы, представляемые как f, g, h, ...,

  4. символы отношений p, q, r, s, ...,

  5. символы пропозициональных констант: TRUE (истина) и FALSE (ложь)

  6. логические операторы (связки): - (отрицание, НЕ),  (дизъюн­кция, ИЛИ), & (конъюнкция, И),  ( импликация, ЕСЛИ ...ТО),  ( эквиваленция, ЕСЛИ И ТОЛЬКО ЕСЛИ)

  7. кванторы:  (существование),  (всеобщности)

  8. круглые скобки (,) и запятую ",".

Для конъюнкции используется также символ , а для эквиваленции  или .

Каждый символ функции и отношения характеризуется числом аргументов данной функции (отношения) называемым местностью (арностью). Например, функция sin(х) является одноместной, f(x2, x, c) - трехместной и т.п.

Далее определим класс термов:

а) переменная есть терм;

b) константа есть терм;

с) если f есть n - местная функция и t1, ..., tn - термы, f(t1, ..., tn) суть также терм.

Логическая формула задается следующей схемой:

  1. если p - n - местное отношение и t1, ..., tn - термы, то p(t1, ..., tn) есть формула (называемая атомарной)

  2. пропозициональные константы TRUE и FALSE суть формулы

  3. если F и G формулы, то формулами также являются (), (F  G), (F & С), (F С), (F С)

  4. если F - формула и х - переменная, то (х F ) и ( х Р ) - также формулы.

Для упрощения записи логических формул часто отбрасывают скобки, используя отношение порядка (старшинства) между логи­ческими операторами и кванторами. Так, будем считать, что -, ,  связывают сильнее, чем &, который в свою очередь связывает сильнее оператора , а последний связывает сильнее, чем операторы , .

Поэтому формулу

(y (x ((p(x) & ((y))) ((x) (A B))))) (1.3)

можно представить в виде

y (x (p(x) & ((y)) (x) A B) (1.4)

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

x (P(x)  Q(x)),

где Р - эквивалентно Студент;

Q - эквивалентно Сдает-экзамены.

Следовательно, в эквивалентной нотации, можно записать

x (Студент (x)  Сдает-экзамены (x)).

Предложение: "Только артисты восхищаются артистами" получа­ет представление в виде:

x y (B(y, x) & A(x) A(y)),

где А(х) - "x есть артист", В(у, х) - "у восхищается х".

Утверждение ассоциативности арифметической операции сложения имеет следующее формальное представление:

x y z ((x +y) + z = x + (y + z))

Отметим, что последнее выражение с точки зрения правил построения формул логики предикатов следовало записать в виде:

x y z E ((fadd(fadd(x, y), z) fadd(x, fadd(y, z)))),

где Е - предикат равенства ( = );

fadd - двухместная функция сложения;

fadd (t1, t2) - терм, представляющий сумму термов t1 и t2.

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

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

  • установить или опровергнуть выводимость некоторой формулы (в общем случае эта задача алгоритмически неразрешима);

  • доказательство полноты/неполноты некоторой формально логи­ческой системы, представленной множеством логических формул;

  • установление выполнимости системы логических формул (нахож­дение интерпретирующей функции) или отыскание контрпри­мера, опровергающего их;

  • определение следствий из заданной системы формул;

  • доказательство эквивалентности двух формально-логических систем;

  • поиск решения задачи на основе доказательства теоремы существования решения и др.

^ 1.1.3 Модели знаний на основе продукций

В модели знаний на основе продукций знания представлены сово­купностью правил в формате "ЕСЛИ - ТО". Рассмотрим, например, правила порождения родительного падежа слов, задаваемые таблицей 1.1.

Для того, чтобы получить родительный падеж слова "Знахарь" отыскиваем первую подходящую строку, начиная с верхней, в левом ко­лонке табл.1.1. Строка будет подходящей, если указываемое в ней окончание совпадает с окончанием слова (в данном случае выбирается строка 5). Нетрудно, однако видеть, что строка 6 также подходит для нашей цели, хотя выдаваемый ею результат (правая колонка табл. 1.1.) не верен. Прежде чем мы рассмотрим более подробно это свойство сис­темы продукций, выясним их природу. Рассматривая структуру про­дукции, нетрудно видеть, что ее условная часть ("ЕСЛИ...") определяет ситуацию, в которой продукция применима. В примере со словом " знахарь" ситуация определяется его окончанием, т.е. либо окончанием "арь", либо ''-ь".

Таблица 1.1.

№ п/п

Слово или его окончание в именительном падеже

Слово или его окончание в родительном падеже

1.

кино

-кино

2.

-ча

-чи

3.

-ка

-ки

4.





5.

-арь

-аря

6.





7.

-ие

-ия

8.

-мя

-мени

9.





Если ситуация удовлетворяет продукции, то в результате ее применения может быть получен новый объект (состояние) согласно части " ТО ... " в структуре продукции. Так, применение продукции с номером 5 в табл.1.1. к слову "знахарь" порождает слово "знахаря", а применение продукции номер 6 дает слово "знахари". Таким образом, одним из основных вопросов в реализации продукционных систем является стратегия выбора альтернативных правил. В общем случае эта проблема нетривиальна. Условная часть продукции может иметь различные формы, такие например, как в следующих примерах:

 ЕСЛИ (идет - дождь) ;

 ЕСЛИ (a > b2 - b) ;

 ЕСЛИ (P C Q) .

В структуре продукции дополнительно могут указываться метка и строка, содержащая объяснение применения продукции. Метка может быть простым идентификатором (или номером) или некоторым поясни­тельным текстом, например, "определение окраски инфекции по Граму" Строка-объяснение показывает, почему используется продукция. Сле­дующий пример демонстрирует полную продукцию:

МЕТКА: R26 Использование зонтика

УСЛОВИЕ: ЕСЛИ (идет дождь)

ДЕЙСТВИЕ: ТО (возьмите зонтик)

ОБЪЯСНЕНИЕ: (зонтик предохраняет от дождя)

Как правило, задача, формулируемая для продукционной системы, имеет одну из следующих структур

<S0, Sf - ?> (1.5)

<S0 - ?, Sf> (1.6)

<S0, Sf, A - ?> (1.7)

<S0, Sf - ?, A - ?> (1.8)

где: S0 - начальная ситуация

Sf - конечная (желаемая, требуемая ситуация)

А - алгоритм (последовательность выполняемых продукций), переводящий систему из состояния S0 в состояние Sf

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

Задача (1.6) является обратной по отношению к предыдущей.

Задача (1.7) заключается в отыскании алгоритма преобразования начальной ситуации в конечную.

Задача (1 .8) представляет обобщение задач (1 .5) и (1 .7).

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

Продукционные системы впервые изобретены Постом в 1941г. Продукция в системе Поста имеет следующую схему

(1.9)

где t1, t2, ..., tn называются посылками, а t заключением продукции.

Применение схемы (1.9) основывается на подстановке цепочек зна­ков вместо всех переменных, причем вместо вхождений одной и той же переменной подставляется одна и та же цепочка.

В качестве других классических продукционных систем отметим нормальные алгоритмы Маркова и машину Тьюринга.

Развитием модели на основе правил является модель "доски объяв­лений". Эта модель реализована в системе распознавания разговорной речи HEARSAY - 2. Основной принцип организации модели доски объявлений заключается в разбиении продукций по уровням иерархии. При этом заключения продукций на нижних уровнях используются как входные условия для продукций более высокого уровня. На самом ниж­нем уровне модели доски объявлений представлены факты, на самом верхнем - результирующее заключение.

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

В рамках этой модели продукция определяется четверкой:

P = < L, C, N, A >,

где L – метка;

^ С – условие применимости;

N – ядро продукции, описываемое формулой (1.9);

А – постдействие.

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

Приведем алфавит:

G1: А И Х

G2: Б З Р Ы Ь Я В

G3: С О Э Ю

G4: Е Н П Т Ш Г

G5:

G6: Ц Ъ Щ

Данный алфавит был разделен на группы, исходя из внутреннего строения каждого символа.

Таким образом получено следующее множество:

f1– вертикальные наклонные (отвесные) прямые;

f2– горизонтальные прямые;

f3– полуовалы;

f4– большие овалы;

f5– вертикальные прямые;

f6– короткие вертикальные наклонные отрезки;

f7– хвостики.

Данная продукция может быть представлена в виде:

P = < L, C, N, A >, где L=L1, а С – условие применимости данного шрифта.



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

На языке Prolog такая продукция выглядит так:

N1:–G1;G2;G3;G4;G5;G6.

G1:–Pf1’, Pf2’, Pf5’.

……………

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

f1 кривая замкнутая полная (на высоту кадра);

f2 кривая с левосторонней выпуклостью;

f3 кривая с правосторонней выпуклостью;

f4 кривая верхняя с правосторонней выпуклостью;

f5 кривая верхняя с левосторонней выпуклостью;

f6 кривая нижняя с правосторонней выпуклостью;

f7 кривая нижняя с левосторонней выпуклостью;

f8 вертикальный левый отрезок;

f9 вертикальный правый отрезок;

f10 вертикальный центральный отрезок;

f11 вертикальный левый верхний отрезок;

f12 вертикальный левый нижний отрезок;

f13 вертикальный правый верхний отрезок;

f14 вертикальный правый нижний отрезок;

f15 вертикальный центральный верхний отрезок;

f16 вертикальный центральный нижний отрезок;

f17 вертикальный отрезок с углом наклона менее 90;

f18 вертикальный отрезок с углом наклона более 90;

f19 вертикальный верхний отрезок с углом наклона менее 90;

f20 вертикальный верхний отрезок с углом наклона более 90;

f21 вертикальный нижний отрезок с углом наклона менее 90;

f22 вертикальный нижний отрезок с углом наклона более 90;

f23 горизонтальный верхний отрезок;

f24 горизонтальный нижний отрезок;

f25 горизонтальный центральный отрезок;

f26 хвостик.

Рассмотрим символы из второй группы.




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

^ 1.1.4 Фреймовая модель знаний

Фреймовая модель знаний предложена Марвином Минским. Минский также ввел терминологию и язык фреймов. Эта терминология включает такие понятия как "фреймы", "слоты", "терминалы", "значения по умолчанию". Фрейм определяется как структура следующего вида:

{<имя-фрейма> <имя слота1 > <значение слота>1, ...,

<имя слотаn > <значение слота>n }

Так, определим фрейм для объекта "книга":

{<КНИГА>

<АВТОР> <ДюмаА.>

<НАЗВАНИЕ> <Граф Мосте Кристо>

<ЖАНР> <Роман>}

Мы видим, что слоты соответствуют атрибутам (характеристикам, свойствам) объекта. Если значения слотов не определены, то фрейм называется фреймом-прототипом. Заменяя неизвестное значение звездоч­кой ("*") будем иметь следующий фрейм-прототип:

{<КНИГА>

<АВТОР> <*>

<НАЗВАНИЕ> <*>

<ЖАНР> <*>}

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

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

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

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

слоты

факты

процедуры







внутренние

внешние

























Рис1.1

Структура фрейма, содержащего процедуры, показана на рис. 1.1.

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

Примеры систем, работающих с фреймами, это KRL, FRL, GUS, OWL [20, 21] и др.

Развитием концепции фреймовых моделей являются сценарии и ленемы.

^ Понятие сценария введено Р. Шенком и Р. Абельсоном. Сценарий - это фреймоподобная структура, в которой определены такие специаль­ные слоты как сценарий, цель, сцена, роль. Следующий пример сцена­рия взят из:

< сценарий : ресторан

роли: посетитель, официант, кассир

цель: принятие пищи, чтобы насытиться и получить удовольствие

сцена 1: вход в ресторан

войти в ресторан

осмотреть места

выбрать свободное место

пройти к свободному столику

сесть

сцена 2: заказ

взять меню

прочитать меню

решить, что заказать

заказ меню официанту

сцена 3: прием пищи

получение пищи

съедение пищи

сцена 4: уход

просьба рассчитать

получение чека

движение к кассиру

передача денег кассиру

выход из ресторана >

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

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

имя: животное х

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

иер_контекст: млекопитающее,

имеет-шерсть,

четвероногое,

домашнее.

Поле "определитель" и "отрицательный определитель" содержат от­личительные особенности, которыми обладает или (не обладает в слу­чае отрицательного определителя) представитель данного класса. На­пример,

n_опред: о6ладает_развитым_о6онянием;

быстро_обучается;

о-опред: летает;

нападает_на_человека.

Поле "интерпретация" содержит описание домена, представляюще­го множество объектов данного класса, например,

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

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

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

^ 1.1.5 Семантические сети

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





Рис. 1.2



Введен также специальный тип вершин: вершины связи. Вершина связи не соответствует ни объектам, ни отношениям и используется для указания связи.

Основными отношениями в семантической сети являются отношения принадлежности к классу, свойства, специфи­ческие для данного понятия и примеры данного понятия (рис. 1.2).

Отношение принадлежности элемента к некоторому классу либо части к целому в англоязычной литературе определяется соответственно как "IS А", либо как "РАRТ ОF", например, фразе "лев есть хищник" соответствует семантический фрагмент, изображенный на рис. 1.3.






Рис. 1.3 Рис. 1.4




Рис. 1.5

Свойства передаются через связки "IS" и "HAS" ("есть" и "имеет"), например, высказывание "лев имеет гриву" интерпретирует фрагмент сети, показанный на рис.1.4, а фраза "грива густая" (a mane is thick) передается фрагмен­том на рис. 1.5.

Если обозначить фрагменты, показанные на рис.1.3 - 1.5 через Фi, то в общем случае семантическая сеть образуется как соединение () этих фрагментов, т.е. как

Ф1  Ф2 ... Фn,

причем порядок индексации фрагментов не имеет значения (операция соединения коммутативна).

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

Деятель

- понятие исполнителя АКТа

АКТ

- действие, производимое по отношению к объекту

Объект

- вещь, над которой производится действие

Реципиент

- получатель объекта в результате АКТа

Направление

- местоположение, к которому направлен АКТ

Состояние А

- состояние, в котором находится какой-либо объект

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

Обозначения:

РР - класс физических объектов;

О - физические объекты;

АСТ - действия;

РА - свойства объектов;

LОС - местоположение;

Т - времена;

АА - атрибуты (характеристики) действий;

РА - атрибуты (характеристики) объектов;

R. - реципиенты;

I - инструменты, посредством которых выполняется действие;

D - направление действия;

Концептуальные схемы:

 - используется для обозначения концепта действия

(1) PP ACT - некоторые объекты могут производить действия

(2) PP PA - объекты обладают свойства

(3) - АКТы имеют объекты



(4) - АКТы имеют направление



(5) - АКТы имеют реципиентов

(6) - АКТы могут изменять характеристики

(7) PP PP - один PP эквивалентен другому или является

его частной характеристикой

(8) - концепт действия характеризуется местоположением



(9) - один концепт действия является причиной другого

(

10) T - концепт действия характеризуется временем



(11) - концепт действия характеризуется изменением состояния

(12) - действие ACT характеризуется инструментом I

(13) - действие характеризуется объектом 0.

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

Пример 1. Джон съел лягушку.



Джон  съесть лягушка
Y - некоторое неизвестное местоположение.

Пример 2. Билл обидел Джона.




Пример 3. Джон дал Мэри книгу.







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

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

  • добавлять или удалять фрагменты сетей

  • добавлять или удалять связи и вершины

  • проверить, что некоторый фрагмент содержится в сети

  • строить примеры отношений

  • находить фрагменты, общие для двух и более сетей и др.

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

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

    1. Машина вывода

      1. Понятие формальной системы

Прежде чем мы сформулируем понятие машины вывода, нам необходимо дать определение формальной (аксиоматической) системы и правил вывода. Под формальной системой понимается четверка:

М = <Т, Р, А, П>, (1.10)

где ^ Т - множество базовых элементов;

Р - множество правил построения правильных (сложных) объектов из базовых элементов;

А - множество изначально заданных объектов формаль­ной системы (множество аксиом );

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

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

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

В качестве множества правил Р построения правильных (сложных) объектов логики предикатов выступают правила построения формул логики предикатов.

Например, следующая формула является правильно построенной

(x(y( z( P(x, y)(z))))),

в то время как объект ниже

(x P(x, y)) (z ((z)))

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

^ Множество аксиом - это множество формул, истинность которых постулируется без доказательства.

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

Схемы аксиом логики предикатов таковы:

  1. A  (B  A)

  2. (A  B)  ((A  (B  C))  (A  C))

3. A  (B  A & B)

4a. A & B  A

4в. A & B  B

5a. A  A B

5в. B  A B

6. (A  C)  ((B  C)  (A B  C))

7. (A  B)  ((A ) A)

8.  A

9.  x A(x)  A(t)

10. A(t)  xA(x)

Постулаты арифметики:

1. A(o) & x (A(x)  A(x’))  A(x) (аксиома индукции)

2. a = b  a = b

3. a = b  (a = c  b = c)

4. A + 0 = a

5. a 0 = 0

6.

7. a = b  a = b

8. а + b = (а + b)

9. a b = a b + a

Здесь A, B, C - формулы; х - переменная; t - терм; a, b, c - целые числа; операция (’) (штрих) соответствует добавлению к числу единицы: а’ = а + 1.

Рассмотрим, например, схему аксиом (7). Заменим формулу А  В на  В и подставим (7)



Далее по правилам де Моргана: = получаем:



Нетрудно видеть, что схема аксиом (7) является тождественно ис­тинной, если истинна формула A .

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

Воспользуемся примером, иллюстрирующим это положение.

Рассмотрим высказывание "последовательность 0123456789 встре­чается в разложении числа ". Обозначим это высказывание через А. Тогда обратное высказывание означает, что "последовательность 0123456789 не встречается в разложении числа ". Для того, чтобы доказать формулу А (или ) в принципе нужно строить бесконечное представление для числа. Поскольку ни один шаг такого "доказа­тельства", если он не приводит к отысканию требуемой последовательности, не является законченным, мы не вправе считать, что до­казана формула А (). Итак, мы в принципе не в состоянии укачать финитное (конечное) доказательство ни для формулы А, ни для формулы .

Будем записывать десятичное разложение числа  , а под ним деся­тичную дробь  = 0,333.... При записи каждой очередной цифры в разложении  добавляем "3" в . Если окажется, что высказывание А истинно, то стираем записанное представление для  и полагаем



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

Допустим, что справедлива формула В, где В - это высказывание "число рационально", и - обратное высказывание, т.е. число не рационально.

Спросим себя, рационально ли  или нет? Если  не рационально (верно ), то должно быть верно (иначе, если бы была получена последовательность 0123456789), то



где х, у - целые, т.е. было бы рационально. Однако, если справедливо , то  = 1/3 = 0.333... (бесконечная последовательность). Здесь  ра­ционально, что противоречит предположению о его нерациональ­ности. Итак,  не может быть не рациональным. Но значит  рационально. Для этого однако, нужно иметь доказательство А или , чего у нас нет.

Действительно, если  рационально либо мы построили беско­нечную последовательность 0,333... (что невозможно), либо доказали формулу А.

Приведенный пример характеризует так называемое интуицио­нистское направление в математике. Так интуиционисты отрицают правило tertium non datyr (третьего не дано). Ими также подвергается критике само понятие отрицания: ложность любой формулы  трак­туется ими так, что допущение  ведет к противоречию.

Еще один философский пример того же рода демонстрирует так называемый парадокс лжеца: "если некто говорит, что он лжет, то говорит ли он на самом деле правду или лжет?"

Обозначим высказывание "Я лгу " через А. Если А истинно, то "некто в действительности лжет", т.е. должно быть и наоборот. А это означает, что формула A ни истинна, ни ложна (противоречива).

Вернемся, однако, к истине (1.10). Нам осталось определить пра­вила вывода П. Каждое правило вывода имеет структуру вида:

(1.13)

означающую, что если выведены формулы 1, 2, ..., n, называемые по­сылками, то выводима также формула  называемая заключением.

Под выводимостью формулы  из формул 1, 2, ..., n, понимается такое отношение между этими формулами, что всякий раз, когда истин­на каждая из формул 1, 2, ..., n, истинна также формула .

По определению, аксиома  имеет структуру

, (1.14)

т.е. невыводима из других формул (множество посылок пусто).

Отметим следующие основные свойства для отношения выводимости.

1. Рефлективность:

(1.15)

2. Транзитивность:

(1.16)

(если  выводима из  и из  выводима , то из  выводима формула ).

  1. Монотонность:

(1.17)

(если из  выводима формула , то присоединение к  формулы  не от­меняет выводимость ). Отметим, что свойство монотонности в общем случае не имеет места в некоторых неклассических логиках, рассматри­ваемых в главе 3.

  1. Теорема дедукции:

Если из  и  выводима формула , то из  выводима формула    ( - импликация).

(1.18)

Верна также обратная теорема:

(1.19)

Теорема дедукции имеет весьма важное значение в логике. Действи­тельно, чтобы доказать выводимость

(1.20)

заменим формулу  эквивалентной формулой   , где  - символ пус­той формулы (лжи). Используя эквивалентную замену      , по­лучим





. (1.21)

Т

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

В качестве основных правил вывода в логике предикатов используются правила modus ponens и generalization.

Правило modus ponens:

(1.22)

утверждает, что если истинны формулы А и А  В, то истинна формула B.

Правило generalization:

. (1.23)

Справедлива и обратное

(1.24)

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

В частности, если С пустая формула, то имеет место

(1.25)

Пример правила generalization:



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

      1. ^ Примеры стратегии вывода

Рассмотрим формализм нормальных алгоритмов Маркова, в котором правила вывода реализуются на основе операторов подста­новки.

Пусть а и b - произвольные слова. Будем говорить, что слово а входит в слово b, если существуют такие слова с и d, что b = cad.

Основным правилом вывода является подстановка. Оператор под­становки а  Ь используется для замены левого вхождения слова а на слово b. Для того, чтобы применить оператор а  b к слову e, необ­ходимо, чтобы е содержало а. В последнем случае будем говорить, что выполнены условия применимости оператора а  b. Из множества операторов, для которых выполнены условия применимости, всегда выбирается один оператор (например, первый по порядку). Отметим, что вывод считается детерминированным, если всякий раз условия при­менимости выполняются не более чем для одного правила вывода. Алгоритм завершает работу, если либо нет выполнимых операторов, либо выполняется специальный оператор конца (стоп-оператор).

Пример.

(1) a  bc

(2) c  ebcc

(3) c  d

(4) d  

(5) b  

(6) есс  d.

e - символ пробела.

Рассмотрим, как преобразуется в этой системе слово cad:

cad  ebccad  eccad  dad  ad  bcd  cd  ebccd  eccd  dd  d  

Здесь внизу под стрелкой указан номер оператора.

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

Пусть x1, x2, ..., xn - попарно различные переменные, которые име­ют области определения D1, D2, ..., Dm соответственно. Если переменная х связана некоторым значением из Dj, , то будем вместо х, писать .

Образец это конструкция



где каждому xi, сопоставлен терм уi , являющийся либо самой перемен­ной хi, (если она не связана), либо , если xi = .

Например,

1 =

Пусть даны два образца 1 и 2. Будем говорить, что из 1 и 2 выводится образец 3, и писать это: , если выполнены следующие условия:

  1. 1 и 2 содержат общие переменные

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

  3. ^ 3 образуется путем включения (без дублирования) всех перемен­ных из 1 и 2. При этом если общая переменная xi связана, скажем в 1, значением хi = а, а в 2 свободна ( не связана), то в 3 xi будет иметь значение а. В этом случае говорят, что переменные в 3 наследуют значения соответствующих переменных в 1, 2.

Пример вывода по образцам 1, 2 образца 3.

1 =

2 =

из 1, 2 выводим образец 3

3 =

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

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

^ Р(Н) = - априорная вероятность гипотезы Н при отсутствии каких- либо свидетельств;

Р(Н:Е) = - апостериорная вероятность гипотезы Н при наличии свидетельства Е.

Согласно теоремы Байеса:

(1.26)

и

где Р(Н*) оценивает новую вероятность гипотезы Н с учетом свиде­тельства Е.

Введем отношение правдоподобия ОП(Н:Е),

(1.27)

а также формулу для вычисления шансов O(H),

(1.28)

Из (1.28) нетрудно обратным преобразованием получить

(1.29)

Теперь формула Байеса (1.8) на языке шансов принимает следую­щий вид:

O(H*) = O(H) OП(H:E), (1.30)

где O(Н*) - новая оценка шансов для гипотезы Н с учетом свидетельст­ва Е.

Формула (1.30) при наличии многих свидетельств E1, E2, ..., En при­нимает вид:

(1.31)

Таким образом, на основании формул (1.30) и (1.31) имеется воз­можность просто пересчитывать апостериорные вероятности гипотез на основании получаемых свидетельств. Теорема Байеса является основой механизма вывода в экспертных системах PROSRECTOR и HULK.

Рассмотрим пример использования стратегии Байеса. Пусть требуется провести дифференциальную диагностику между заболева­ниями D1, D2, ..., Dn. Для простоты, пусть имеется три заболевания и че­тыре признака, по которым должен быть составлен диагноз.

Заболевания:

D1 - тетрадаФалло, D2 - дефект межпредсердечной перегородки, D3 - незараценный артериальный проток.

Признаки:

S1 - цианоз, S2 - усиление легочного рисунка, S3 - акцент II тона во втором межреберье слева, S4 - правограмма (ЭКГ).

Допустим, известны следующие условные и безусловные вероят­ности (табл. 1.2), полученные на основе накопленной статистики о боль­ных данными заболеваниями.
  1   2   3   4   5

Реклама:





Скачать файл (775.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru