Искусственный интеллект

Для СС используются 4 основные операции: объединение, копирование, упрощение и конкретизация.

Если есть 2 семантические сети с₁ и с₂, содержащие общие объекты, то в результате операции объединения получится сеть, в которой одинаковые вершины отождествляются: с₁с₂.

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

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

Операция конкретизации: создается новый концептуальный граф, в котором имя типа заменяется именем подтипа или объекта. Например, Жан написал книгу «БД» и послал книгу Мери.

Для введения кванторов в состав СС концептуального графа вводятся пропозициональные вершины, т. е., вершины, обозначающие отдельные фрагменты СС. Например: Жан посылает некоторую книгу Мери. Жан посылает всякую написанную им книгу Мери. Жан посылает эту книгу Мери.

Для использования пропозициональных вершин в СС вводится понятие «метка концептуального графа».

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

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

- аналитические (свойства типа);

- синтетические (свойства множеств).

Решетка типов образуется путем использования отношений: «это» и конкретизация.

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

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

Между решеткой типов и решеткой множеств введено отношение абстракций.

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

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

a) Проверка наличия свойства у конкретного экземпляра объекта.

b) Проверка наличия данного свойства в описании типа.

c) Проверка наличия этого свойства у соответствующих надтипов.

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

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

Клауза - это выражение вида:

B₁B₂…B_n - A₁A₂…A_m

Где:

B_i и A_j - атомарные формы;

A_j - посылки клаузы;

B_i - заключения.

Аналогом клаузы является логическая формула вида:

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

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

Если m=0, то клауза безусловная (т. е., тождественно истинное высказывание), если n=0 - тождественно ложное высказывание.

Если m=0, n=0, то клауза пустая.

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

Рассмотрим расширенную СС: вершины соответствуют объектам, помеченные ориентированные дуги - бинарным предикатам. Т. е., СС - помеченный граф.

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

Условия клаузы будем объединять двойными линиями, заключения - жирными линиями:



- правило modus ponens.

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

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

В данном случае вывод выполняется на неизменяемой СС.

Дедуктивный вывод на семантических сетях.

Логико-лингвистической моделью (ЛЛМ) называется язык исчисления предикатов 1-ого порядка, имеющий следующий вид:

Где:

Bⁱ_j - условия ввода;

Aⁱ_k - заключения.

Формулы используются в ССФ, т. е., переменные, связанные квантором существования, заменены функциями или константами, и все используемые переменные считаются связанными квантором всеобщности.

ЛЛМ ставится в соответствие некоторая СС.

Задача дедуктивного вывода может быть рассмотрена в следующем виде: имеется описание модели предметной области в виде ЛЛМ и совокупность утверждений вида: А₁,…,A_z. Необходимо получить пустой дизъюнкт.

Запрос к ИС формируется в виде:



Результат запроса - значения констант, т. е., объектов БД, для которых запрос принимает истинное значение, или, что то же самое, для которых отрицание запроса позволяет получить в СС пустой дизъюнкт.

В СС выделяются 4 типа отношений:

- структурные (студент-дисциплина);

- логические (студент - успевающий);

- процедурные (средняя успеваемость: группа-предмет);

- теоретико-множественные.

В основном в СС используются структурные отношения. Среди объектов можно выделить следующие основные группы:

- собственные объекты;

- объекты-события;

- объекты-характеристики (одноместные предикаты).

Кроме того, выделяется особый класс объектов - пропозициональные вершины, т. е., вершины, соответствующие высказыванию в целом.

Методы дедукции на семантических сетях.

Существует 4 основных класса методов:

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

2) Метод наложений: утверждение считается истинным, если в исходной сети существует фрагмент, в который изоморфно вкладывается посылка. Пример: классификация молотка;

3) Специальные методы, основанные на свойствах используемых отношений. Например, транзитивность;



- modus tollens, Л - ложь.

4) Методы, основанные на получении пустого дизъюнкта.

Идея дедуктивного вывода на СС состоит в следующем: все утверждения записываются в клаузальной форме. При этом истинные высказывания имеют вид: B_i<, а ложные: A_j>.

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

Пустому дизъюнкту соответствует пустая семантическая сеть.

Алгоритм унификации.

Сорт - имя, данное совокупности известных элементов в предметной области. Понятие «сорт» является аналогом понятия «тип» в предметной области.

Алгоритм унификации сводим к определению пересечений поддеревьев в СС.

В общем виде алгоритм унификации может быть сформулирован следующим образом, есть 2 терма: v_k, t_k.

Возможны следующие случаи:

1. v_k и t_k - переменные, области их значений заданы перечислениями. Унификация возможна, если пересечение множеств не пусто.

2. v_k и t_k - переменные, области значений заданы в виде сортов:

v_k / S_k - t_k / S²_k

Унификация возможна, если пересечение сортов не пусто.

3. v_k - переменная, t_k - функция. Пересечение области значения функции и переменной не пусто. Унификация возможна, если вместо переменной подставляется функция, область определения которой сужается таким образом, чтобы область значений функции было подмножеством области значений переменной.

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

5. v_k - переменная, t_k - константа того же сорта. В этом случае имеет место подстановка константы вместо переменной.

На СС посылки будем обозначать непрерывными линиями, а заключения - пунктирными.

Наличие контрарной пары означает наличие предикатов вершины, к которой ведут стрелки двух типов.

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

Алгоритм дедукции с использованием операторов удаления и расщепления вершин.

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

Замечания к предыдущему алгоритму.

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

Оператор удаления вершины.

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

Пусть с предикатной вершиной Р связаны дизъюнкты g₁,g₂,…,g_n. После вычисления всех возможных резольвент, дизъюнкты вершины g₁,g₂,…,g_n удаляются и к сети добавляются новые вершины, являющиеся результатом резольвирования вершин g_i.

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

Последовательно применяя операторы расщепления и удаления вершин, можно прийти к пустой сети.

Формально оператор расщепления вершины определяется следующим образом:

Пусть имеется множество дизъюнктов:

S = {P - Г Ф}

Где:

Р - некая предикатная литера;

Г - дизъюнкт, соединяющий предикат Р;

Ф - множество некоторых дизъюнктов.

В результате расщепления вершины Р получается множество дизъюнктов:

S = {P₁ - Г₁ Ф^{[P | P1]} Ф}

Где:

запись Ф^{[P | P1]} - замена всех вхождений литеры Р в формуле Ф литерой Р₁. Алгоритм вывода на СС с использованием операторов удаления и расщепления не является полным, т. е., это значит, что если исходное множество дизъюнктов является невыполнимым, то в общем случае пустая сеть не может быть выделена.

Алгоритм вывода состоит из следующих шагов:

1. Если в СС присутствуют вершины, которые могут быть удалены, они удаляются.

2. Если в СС имеются вершины с мульти дугами, то выполняется операция расщепления вершин.

После этого снова переходим к пункту 1.

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

Пример 1: пусть множество дизъюнктов имеет вид:

Соответствующая логическая сеть показана на рисунке:

Пример 2:



Пример 3: имеем невыполнимое множество дизъюнктов:

Пример 4: имеем множество дизъюнктов:



Пример 5: имеем множество дизъюнктов:

Полный алгоритм вывода на СС.

Пусть имеется множество дизъюнктов: S₁,S₂,…,S_n. Выберем из каждого дизъюнкта какую-нибудь литеру L₁,L₂, …,L_n. Такую последовательность литер назовем путём на множестве S.

Алгоритм:

1. Выделяем некоторый путь p из исходного множества S.

2. Выводим все возможные дизъюнкты на этом пути, т. е., если имеются контрольные пары, они резольвируются и результат добавляется к СС.

3. Литеры, соответствующие вновь сформированным дизъюнктам, добавляются в путь р.

4. Процесс продолжается до получения пустого дизъюнкта.

В СС выделению литеры соответствует процесс выделения вершины по дуге. Обозначим:

- выделение литеры, связанной с вершиной p дугой 1-го типа.

Алгоритм параллельного вывода на СС.

Дедуктивному выводу присущи 2 вида параллелизма:

- OR-параллелизм (Один и тот же дизъюнкт. Одна литера в СС резольвируется во всех возможных местах, параллельно выполняется унификация и генерация новых дизъюнктов);

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

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

При параллельном выводе на СС возможно параллельное выполнение следующих операций:

1. параллельная унификация: выполняется внутри одной вершины, свободной от мульти дуг;

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

3. параллельная стяжка мульти дуг одного цвета;

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

5. параллельное расщепление различных вершин, имеющих мульти дуги.

Нечеткая математика и ее применение в ЭС.

Введение в нечеткую теорию множеств.

Пусть имеется универсальное множество Щ.

Нечетким множеством А называется пара:

А = (Щ м_А) м_А: Щ - [0, 1]

- функция принадлежности.

В классической теории множеств м_А называется индикатором.

А - мА В - м_В

С = м_С = 1 - м_А

С = A - B

м_С = max * (м_А м_В)

С = A - B м_С = min(м_А, м_В)

Заметим, что при данном определении операций, все свойства сохраняются для нечетких множеств.

Меры возможности и нечеткие множества.

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

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

Уверенность - показатель надежности информационной единицы.

Неточность - это характеристика качества значения признака, а неопределенность - это соответствие данного значения действительности.

Понятия правдоподобности и доверия соответствуют способу вывода в БЗ. Например, заслуживает доверия все то, что непосредственно выводимо дедуктивно в БЗ. Правдоподобно все то, что не противоречит БЗ.

Пример: скорее всего, рост среднего человека не менее 170 см. Для каждого конкретного человека данный факт либо ложь, либо истина. Если:

g (A - B) = min * (g(A) g(B))

- получаем меру необходимости - N.

Практически функции принадлежности занимают некое промежуточное положение между мерами возможности и необходимости.

Пусть у нас есть система нечетких множеств: Щ, м_А.

Срез нечеткого множества, называется множество:

F = {щ | щ - Щ м_А (щ) >}

Нечеткие множества:

А (Щ,м_А) В(Щ, м_В) м_А - м_В

Два нечетких множества считаются равными, если совпадают их функции принадлежности: A=B.

Методы построения функции принадлежности.

Существует два основных случая:

1) функция принадлежности отражает субъективное предпочтение о некоторой расплывчатой категории;

2) функция принадлежности строится на основе статистических данных.

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

1) оцениваемый объект является простой категорией, определенный на объективно линейном упорядоченном универсальном множестве («большой и высокий»);

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

3) отсутствие универсальной шкалы («красивый»).

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

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

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

x_j : b_ij=м_i / м_j

Далее считается, что:

Где:

щ_i - собственный вектор матрицы В.

Нечеткие числовые величины.

Способы задания нечетких числовых величин.

Нечеткая числовая величина f, задается своей функцией принадлежности м_f.

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

Арифметическая операция над числами А и В, это некая функция, отображающая g:

м_С (х) = sup * (м_A(y) м_B(z)) g (y, z) = x y - S_Az - S_B

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

Пусть f_A, f_B, f_C - плотности распределения вероятностей случайных величин A, B, C. Тогда считая, что случайные величины А и В независимы, получаем:

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

1) явное задание функции принадлежности;

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

A- [m_A M_A] - S_A

3) треугольное представление: любому нечеткому числу ставится в соответствие тройка:

А - [m_A * V_A * M_A]

Притом предполагается:

м_{A *} (V_A) = 1 - [m_A M_A] - S_A



4) трапециевидные числа: любое число характеризуется парой А=M_A.

S_A= [m_A-_A, M_A+_A]

- носитель.

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

A, B - нечеткие числа.

Можно доказать:

max (A B) + min (A B) = A + B

max (A, B) = A - min (A, B) = B

Для трапециевидных чисел предложена методика решения нечетких уравнений и нечетких систем линейных уравнений.

Замечание.

При использовании принципа обобщения возможны два варианта его применения при вычислении сложных выражений:

С = А / (А + В) D = A + B - C' = A / D

Нечеткая числовая величина С=C.

Экспертоны, R-экспертоны.

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

Пусть N экспертов строят доверительный интервал для некой числовой величины:

Эксперт выражает свою оценку с помощью семейства значений.

Доказано, что данная шкала является достаточной для получения объективных оценок:

Получившаяся в результате совокупность интервалов b_i является функцией принадлежности нечеткой числовой величины.

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

Пример:

Пусть необходимо оценить объем продаж фирмы.

- стоимость товара, S - количество.

Пусть возможные цены продаж оценивает группа экспертов N_C.

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

Пусть получены следующие оценки: 41, 54 - обобщенный интервал.

0,2	0,4
0,3	1
0	0,6
0,2	0,3
0,9	0,9
0,7	0,7
0,5	0,7

Этап А - считаем частоту, с которой встречается каждая граница.

0	1		1	1	54	54	9720	9720
0,1	-		0,85	1	52	54	9396	9720
0,2	1		0,85	1	52	54
0,3	1	1	0,5	1	48	54
0,4	-		0,42	0,85	46	52
0,5	1	1	0,42	0,7	46	50
0,6		1	0,29	0,7	45	50
0,7	1	2	0,29	0,57	45	48
0,8			0,14	0,29	43	45
0,9	1	1	0,14	0,29	42,8	44,7

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

Выполнив обратные преобразования, можно получить б-уровни для представления числа V.

Нечеткие рассуждения.

Возможны следующие типы нечетких высказываний:

Пример:

A. Знания студента отличные.

B. Знания студента средние с большой вероятностью.

C. Если студент ориентируется в теме «Исчисление высказываний», то его знания не менее, чем средние.

D. Если студент задает вопросы со степенью разумности 0,75, то его знания хорошие.

Пример:

1. Если х владеет машиной VW и х читает газету Washington Post, то х будет голосовать за демократов.

2. Если х не любит Р. Рейгана и х против войны, то х будет голосовать за демократов:

S₁ - (Q | S₁)

S₂ - (Q | S₂)

Должна быть разложима в ряд Тейлора.

Тогда получается, что вид функции должен быть таким, чтобы было легко искать max. информация реляционный программирование

Данные и знания. Перспективы развития ЭС.

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

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

Данные - это отдельные факты, характеризующие предметную область.

Знания - это хорошо структурированные данные, данные о данных или метаданные.

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

Информация - интерпретация:

- Внутренняя (типы).

Размещено на Allbest.ru

...