ПОЗНАВАТЕЛЬНОЕ

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

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ВЫПОЛНЕНИЯ

Лабораторная работа № 1, 2.

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

Цель работы

1. Овладение навыкам представления предметных областей формально-логическими моделями.

2. Овладение навыкам представления предметных областей в продукционных моделях баз знаний.

3. Овладение навыкам представления предметных областей во фреймовых моделях.

4. Овладение навыкам представления предметных областей в семантических моделях.

Краткие теоретические сведения

Типичные модели представления знаний: логические модели; модели, основанные на использовании правил (продукционные модели); семантические сети; фреймовые модели.

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

Основная идея подхода при построении логических моделей представления знаний состоит в том, что вся информация, необходимая для решения прикладных задач, рассматривается как совокупность фактов и утверждений, которые представляются как формулы в некоторой логике. Знания отображаются совокупностью таких формул, а получение новых знаний сводится к реализации процедур логического вывода. В основе логических моделей представления знаний лежит понятие формальной теории, задаваемое четверкой: S = < В, F , A , R >, где В — счетное множество базовых символов (алфавит), F — множество, называемое формулами, А — выделенное подмножество априори истинных формул (аксиом), R — конечное множество отношений между формулами, называемое правилами вывода.

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

Высказыванием называется предложение, смысл которого можно выразить значениями: истина (T) или ложь (F). Из простых высказываний можно получить сложные высказывания. В свою очередь, сложные высказывания можно разделить на частичные. Элементарным (атомарным) называется высказывание, которое нельзя разделить на части. Элементарные высказывания рассматриваются как переменные логического типа, над которыми разрешены следующие логические операции:

Ø - отрицание;

Ù - конъюнкция;

Ú - дизъюнкция;

® - импликация;

« - эквивалентность.

Смысл операций очевиден из следующей таблицы истинности:

Таблица 1.1.

A	ØA	B	AÙB	AÚB	A®B	A«B
T	F	T	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	T	F	F	F	T	T

Приоритет операций убывает в следующем порядке: Ø, Ù, Ú, ®, «. Для изменения порядка операций при составлении логического выражения (логической формулы) используются скобки. Результат импликации A®B совпадает с результатом выражения ØAÚB. Имеет место также тождество: A«B = (A®B)Ù(AB).

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

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

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

1. AÚB=BÚA, AÙB=BÙA (коммутативность);

2. (AÚB)ÚС=AÚ(BÚС), (AÙB)ÙС=AÙ(BÙС) (ассоциативность);

3. (AÚB)ÙС=(AÙС)Ú(BÙC), (AÙB)ÚС=(AÚС)Ù(BÚC) (дистрибутивность);

4. AÙA=A, AÚA=A (идемпотентность);

5. ØØA=A (двойное отрицание);

6. Ø(AÙB)=ØAÚØB, Ø(AÚB)=ØAÙØB (законы де Моргана);

7. AÙT=A, AÚT=T (свойство истинны);

8. AÙF=F, AÚF=A (свойство лжи);

9. AÙØA=F (закон противоречия), AÚØA=T (закон исключения третьего);

10. (AÚB)ÙA = A, (AÙB)ÚA = A (законы поглощения).

Всякое выражение исчисления высказываний может быть приведено либо к дизъюнктивной, либо к конъюнктивной нормальной форме (с использованием правил 1-10 или составления таблицы истинности).

Формула F находится в конъюнктивной нормальной форме тогда и только тогда, когда она имеет вид: FºF₁Ù…ÙF_n, n³1, где каждая из F_i, 1³i³n есть дизъюнкция литер.

Формула F находится в дизъюнктивной нормальной форме тогда и только тогда, когда она имеет вид: FºF₁Ú…ÚF_n, n³1, где каждая из F_i, 1³i³n есть конъюнкция литер.

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

В логике предикатов первого порядка рассматриваются функции, предикаты, кванторы, логические формулы.

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

Функции могут являться аргументами предикатов, а предикаты — нет. Количество переменных списка переменных функции или предиката называется их арностью (местностью). Формально рассматриваются 0-арные предикаты и функции. Функции с 0-й арностью (без аргументов) являются аналогами констант. Предикат с 0-й арностью (без аргументов) эквивалентен высказыванию.

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

Кроме того, в логике предикатов вводятся кванторы: квантор всеобщности (") и существования ($). С помощь их производится связывание переменных в логических формулах, в результате чего их арность уменьшается (на число кванторов). После связывания всех переменных в логических формулах образуется предложение (обычное высказывание). Так, ("x)A(x) – означает высказывание, состоящее в том, что для любого элемента x имеет место высказывание A(x); ($x)A(x) – означает высказывание, состоящее в том, что существует хотя бы один такой элемент x, для которого имеет место высказывание A(x).

Приоритет операций в логике предикатов убывает в следующем порядке: ", $, Ø, Ù, Ú, ®, «.

Справедливы следующие свойства кванторов, вытекающие из их смысла:

1. ("x)A(x)®A(t);

2. A(t) ®($x)A(x), где терм t свободен для переменной x в логической формуле A;

3. Ø("x)A(x) = ($x)ØA(x), Ø($x)A(x) = ("x)ØA(x);

4. ("x)(A(x)ÙB(x)) = ("x)A(x)Ù("x)B(x), ($x)(A(x)ÚB(x)) = ($x)A(x)Ú($x)B(x);

5. ("x)("y)A(x, y)=("y)("x)A(x, y), ($x)($y)A(x, y) = ($y)($x)A(x, y);

6. ("x)(A(x)ÙC)=("x)A(x)ÙC, ("x)(A(x)ÚC)=("x)A(x)ÚC;

7. ($x)(A(x)ÙC) = ($x)A(x)ÙC, ($x)(A(x)ÚC) = ($x)A(x)ÚC;

8. C®("x)A(x) = ("x)(C®A(x)), C®($x)A(x) = ($x)(C®A(x));

где формула C не содержит никаких вхождений переменной x.

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

2.Продукционные модели

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

i : S; L; A→B; Q,

где i — индивидуальный номер продукции;

S — описание класса ситуаций, в котором данная структура может использоваться;

L — условие, при котором продукция активизируется;

А→В — ядро продукции, например: «ЕСЛИ A₁, A₂,,..., А_n ТО В» . Такая запись означает, что «если все условия от A₁ до А_n являются истиной, то В также истина» или же «когда все условия от A₁ до А_n становятся истиной, то следует выполнить действие B»;

Q — постусловие продукционного правила, описывает операции и действия (процедуры), которые необходимо выполнить после выполнения В. Например, внести изменения в данные либо в саму продукцию.

Пример:

ЕСЛИ у является отцом х, (A₁), z является братом у, (A₂) ТО z является дядей х , (В)

Суть использования правил продукции для представления знаний состоит в том, что левой части ставится в соответствие некоторое условие, а правой части — действие: ЕСЛИ <перечень условия>, ТО <перечень действий>. В продукционном правиле «ECЛИ A, ТО B» (A®B), A называется анцедентом, а B – консеквентом. В такой интерпретации левая часть правил оценивается по отношению к базе данных (известному набору фактов) системы, и если эта оценка в определенном смысле соответствует логическому значению «ИСТИНА», то выполняется действие, заданное в правой части продукции.

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

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

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

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

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

3. Фреймовые модели

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

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

В общем случае фрейм определяется следующим образом:

f=[(r₁, v₁,), … , (r_n, v_n)], где

f — имя фрейма - служит для идентификации фрейма и должно быть уникальным;

v_i — значение слота, или (ИМЯ ФРЕЙМА: (имя 1-го слота: значение 1-го слота), (имя 2-го слота: значение 2-го слота),…(имя n-го слота: значение n-го слота)).

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

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

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

Указатели наследования. Показывают, какую информацию об атрибутах слотов из фрейма верхнего уровня наследуют слоты с аналогичными именами в данном фрейме. Характерны для фреймовых систем иерархического типа, основанных на отношении «абстрактоное – конкретное» (AKO).

U (Unique) – значение слота не наследуется;

S (Same) – значение слота наследуется;

R (Range) – значение слота должны находиться в пределах интервала значений, указанных в одноименном слоте родительского фрейма;

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

Указатель типа данных. Оно показывает тип значения слота. Например, frame – указатель на фрейм; real – вещественное число; integer – целое число; boolean - логический тип; text – фрагмент текста; list – список; table – таблица; expression – выражение; lisp – связанная процедура.

Значение слота.Оно должно соответствовать указанному типу данных и условию наследования.

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

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

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

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

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

· фреймы-роли (менеджер, кассир, клиент);

· фреймы-сценарии (банкротство, собрание акционеров, празднование именин);

· фреймы-ситуации (тревога, авария, рабочий режим устройства и т. д.).

4. Семантические модели

Способ представления знаний с помощью сетевых моделей наиболее близок к тому, как они представлены в текстах на естественном языке. В его основе лежит идея о том, что вся необходимая информация может быть описана как совокупность троек (a ,r, b), где а и b — объекты или понятия, а r — бинарное отношение между ними.

Формально сетевые модели представления знаний могут быть заданы в виде H = < I , C₁ ,…, C_n , Г>,

где I — множество информационных единиц,

С₁ ,..., С_п — множество типов связей между элементами I,

отображение Г задает между информационными единицами, входящими в I, связи из заданного набора типов связей {С_i}.

В зависимости от типов связей {С_i} различают:

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

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

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

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

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

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ВЫПОЛНЕНИЯ

Задание 1.

Представьте приведенные ниже высказывания в логике предикатов первого порядка, используя совместимый словарь (который вы должны определить).

а) Некоторые студенты участвовали в экзамене по французскому языку весной 2001 года.

б) Каждый студент, который участвует в экзамене по французскому языку, сдает его.

в) Только один студент участвовал в экзаменах по греческому языку весной 2001 года.

г) Лучшая оценка по греческому всегда выше, чем лучшая оценка по французскому.

д) Любой человек, рожденный в Великобритании, каждым из родителей которого является британский гражданин или британский резидент, является британским гражданином по рождению.

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

Задание 2.

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

Обнаружив на недельном графике восходящую тенденцию по 13-периодной экспоненциальной скользящей средней цен закрытия, подождите, когда дневные стохастические линии (стохастического осциллятора с параметрами 7-4-3) опустятся за нижнюю пограничную линию (20%). Затем, не дожидаясь их пересечения или поворота вверх, дайте приказ о покупке над максимумом последнего дня. Открыв длинную позицию, разместите защитный стоп приказ под минимумом данного или предыдущего дня, ориентируясь на более низкую величину.

Обнаружив на недельном графике нисходящую тенденцию по 13-периодной экспоненциальной скользящей средней цен закрытия, подождите, пока дневные стохастические линии (стохастического осциллятора с параметрами 7-4-3) не поднимутся над своей верхней пограничной линии (80%). Затем, не дожидаясь их пересечения или поворота вниз, разместите приказ о короткой продаже под минимумом последнего дня. Начав игру на понижение, разместите защитный стоп приказ над максимумом данного или предыдущего дня, ориентируясь на более высокую величину.

Что в описанной предметной области невозможно и не следует формализовать?

Задание 3.

Представьте формально-логической моделью описание правил получения кредита по следующим условиям его предоставления.

Некий банк «Инвест-банк» предоставляет кредиты для физических лиц на следующих условиях. Возраст заемщика не моложе 20 лет и не старше 50 лет. Сумма кредита от 100 тыс. руб. до 500 млн. руб. Кредит предоставляется, если ежемесячный доход заемщика составляет не менее 10% от суммы кредита. Другое условие предоставления: залог под актив, денежная стоимость которого составляет не менее 90% от суммы кредита. При этом не допускается, чтобы этот актив уже был заложен какому-либо банку. Кредит также предоставляется при условии поручительства. При этом требования к поручителю сводятся к следующим. Возраст поручителя от 20 до 50 – ти лет, обладание активом, денежная стоимость которого составляет не менее 90% от суммы кредита и, кроме того, этот актив не заложен ни в одном из банков.

Задание 4.

Некая рекрутинговая компания занимается подбором кадров для иностранных компаний на должности разработчиков баз данных в среде Oracle. Претенденты принимаются на две должностные категории разработчиков: младший программист и старший программист. К претендентам предъявляются следующие требования. Прохождение теста по английскому языку – прошедшим тест считается набравший не менее 7 баллов из 10. Опыт работы с Oracle не менее 3 лет и сдача теста по предмету на не менее чем 6 баллов из 10. Также допускается наличие опыта работы с системой Oracle менее 3 лет, но не меньше 1 года при условии сдачи теста по предмету на не менее чем 9 баллов из 10. Для получения должности младший программист необходимо иметь возраст от 23 до 29 лет. Для получения должности старший программист необходимо быть в возрасте от 27 лет, иметь опыт работы с системой Oracle не менее 4 лет и сдать тест по предмету не менее чем на 8 баллов из 10. Разработайте набор продукционных правил для экспертной системы, позволяющей по результатам испытаний отбирать претендентов на должности младшего и старшего программистов.

Задание 5.

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

Низкий долг - процент долга не выше 100%; средний долг – процент долга выше 100%, но не выше 130%.

Низкий рост – с приростом меньше 10%; средний рост – с приростом не меньше 10% и не больше 30%; высокий рост – с приростом выше 30%.

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

Задание 6.

Разработайте

а) структурный фрейм для обозначения понятия заем;

б) ролевой фрейм для описания роли менеджер;

в) фрейм-сценарий для описания сценария банкротство;

г) фрейм-ситуацию для описания ситуации тревога.

Задание 7.

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

Задание 8.

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

Задание 9.

Постройте семантическую сеть для заемщика кредита в банке на ведение бизнеса. В качестве вершин используйте понятия: Заемщик, Сидоров, Банк, ОАО Инвест-банк, Кредит, Процентная ставка, 18%, Фермерское хозяйство, с. Лосиный. Выделите все отношения между перечисленными понятиями.

Задание 10.

Постройте семантическую сеть для описания следующей ситуации: «Операционист ВТБ банка Иванова Нина Ивановна заключила 3 марта 2010 г. договор о предоставлении кредита в размере 16 млн. рублей с процентной ставкой 18% годовых на срок 5 лет директору малого предприятия Автосервис, находящемуся по адресу г. Артемовский под залог его офиса». Выделите все понятия и отношения между ними.

Контрольные вопросы

1. Что такое высказывание?

2. Перечислите логические операции над высказываниями и дайте им определения.

3. Дайте описание логики предикатов первого порядка? Что такое предикаты? Что такое кванторы?

4. Дайте определение фрейма. Перечислите его компоненты. Какие типы фреймов Вы знаете?

5. Дайте определение семантической модели данных. Опишите ее составные элементы.

6. Перечислите типы семантических сетей. Дайте им определения.