Экспертные системы

Модели представления знаний.

1. Семантические модели. Семантические модели создаются на базе семантических сетей, т.е. графических схем с узлами, соединенными дугами. Узлы представляют некоторые понятия (объекты, события, явления), а дуги – отношения между ними. Достоинства: предоставление средств для выражения ограничений, описание связей между объектами, определение операций над объектами. Недостатки: в семантических сетях нет специальных средств, позволяющих определять временные зависимости, поэтому временные значения и события трактуются как обычные понятия. Произвольная структура и различные типы вершин и связей усложняют процедуру обработки информации.

2. Фреймы имеют вид структурированных наборов компонентов ситуаций, называемых слотами. Формальная структура фрейма: F[<N1,V1>,<N2,V2>,...,<Nk,Vk>],

где F имя фрейма; пара <Ni,Vi> i-й слот; Ni имя слота; Vi его значение.

Значение может быть представлено последовательностью <Kl><L1>;...;<Kn><Ln>;<Rl>;..; <Rm>,

где Ki имена атрибутов, характерных для данного слота; Li значения этих атрибутов или множества их значений; Rj различные ссылки на другие слоты.

Фреймы можно разделить на две группы: фреймы-описания и ролевые фреймы.

3. Логические модели. В основе логической модели представления знаний лежит понятие формальной системы в виде четверки: M = <T, P, A, F>, где

T – множество базовых символов теории М (например, буквы алфавита);

P – множество синтаксических правил, посредством которых из базовых символов строятся формулы;

A – множество построенных формул, состоящих из аксиом;

F – правила вывода, определяющие множество отношений между правильно построенными формулами.

В логическом подходе знания представляются посредством формул, которые строятся из предикатов, логических связок, кванторов и т.п. Например, в языке ПРОЛОГ.

4. Продукционные системы - системы, основанные на правилах. Правила формулируют определенные действия при выполнении некоторых заданных условий. В самом простом виде правила продукции близки по смыслу импликации “ЕСЛИ-ТО”, поэтому для правил можно принять обозначение Рi: А->B или Pi: А1 ˄ А2 ˄ А3... ˄Аn -> B, где Аi – условия применимости, образующие конъюнкцию; В – заключение или действие, которое имеет место при истинности конъюнкции.

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

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

§ база знаний - выделенные и определенным образом структурированные знания о предметной области;

· машина логического вывода - общие знания о нахождении решения задач. Механизм вывода, как правило, содержит:

а) интерпретатор, определяющий, каким образом применять правила для вывода новых знаний;

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

§ интерфейс с пользователем - осуществляет обмен информацией между пользователем и системой и дает пользователю возможность наблюдать за процессом решения задачи.

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

· База правил – БЗ системы, содержащая множество правил продукционного типа.

· Рабочая память (РП) (память для кратковременного хранения) – память, содержащая факты, являющиеся предпосылкой решения задачи, и результаты выводов, полученных на их основе.

· Механизм вывода – процедура, реализующая некоторый способ применения правил, и порядок их использования для обеспечения логического вывода.

База знаний состоит из конечного набора правил П={P₁,…P_m}

и конечного набора фактов А = {а₁,...,а_n}, которыми может оперировать система.

Условие применимости любого из правил Р_iÎ П Р_i: a_i1Ùa_i2Ù...Ùa_is ® a_m,

состоит в одновременном наличии фактов a_i1, a_{i2, ×××} a_is в РП.

Где Ù - конъюнкция(“И”); a_m – новый факт, выведенный из фактов-условий a_i1,...,a_is.

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

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

Стратегии управления выводом:

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

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

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

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

Конфликтный набор (КН) – это набор правил логического вывода, которые на некотором этапе вывода могут быть применены одновременно.

Разрешение конфликта – процедура выбора одного правила из конфликтного набора (КН).

Для этого используются два метода:

1. установка ограничений на генерацию конфликтного набора;

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

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

2. использование того или иного алгоритма разрешения конфликтов.

2.1. Правила применяются по порядку их следования в БП.

2.2. Первым применяется правило с более жесткой условной частью (например, имеющее много условий в правой части). Считается, что в этом случае содержимое вывода будет более высокого уровня (“качественней”).

2.3. Правила применяются в зависимости от их приоритета.

2.4. Алгоритм RETE. При добавлении в РП нового образца проверяются правила, в которых он используется. Если этот образец удовлетворяет части правила, то он запоминается именно в этом качестве. Если образец позволяет удовлетворить левую часть всего правила, то это правило включается в конфликтный набор. Иными словами, при добавлении нового образца в РП все правила, которые содержат этот образец, упрощаются (т.е. из них удаляется, по крайней мере, одно условие).