Исчисление предикатов

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

Иван и Пётр братья

Брат отца дядя

Сын дяди дв.брат

Системы продукций

Под продукцией будем понимать выражение:

Если <x₁,x₂…x_n>то<{y₁,D₁}…{ y_m,D_m}> D_i (0,1) (0,100)

x_i y_i –логические выражения

D_i-фактор достоверности (0, 1)

D_m-фактор уверенности (0,100)

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

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

Преимущества продукционных систем

1.простота и гибкость выделения знаний

2.отделение знаний от программы поиска

3.модульность продукционных правил, правила не вызывают другие правила

4.возможность эвристического управления поиска

5.возможность трассировки цепочки рассуждений

6.независимость от выбора языка программирования

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

Рассмотрим пример использования продукционной системы:

Задача: дана шахматная доска 3х3. Пройти поле конем, на каждой клетке быть не больше 1 раза:

Исходное поле 1;

Целевое поле 2;

Если конь в i позиции – делать ход в j позицию;

P1	1 → 8
P2	1→6
P3	2→7
P4	2→9
P5	3→4
P6	3→8
P7	4→9
P8	4→3
P9	6→1
P10	6→7
P11	7→2
P12	6→7
P13	8→3
P14	8→1
P15	9→2
P16	9→4

№ п/п	Текуще	Цель	Коэффициентцы	Активное правило
			1,2
			13,14
			5,6
			7,8
			15,16
				Выход

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

Семантическая сеть – граф, дуги которого – отношение между вершинам.

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

· Агент – то или что вызывает действие

· Объект – то, на кого или на что направленно действие

· Инструмент – средство, используемое агентом для выполнения фунеции

· Салит - подчиненный главному агенту партнер

· Пункт направления/назначения – начальная и конечная позиция при перемещении

· Траектория

· Средство доставки – то, в чем или на чем происходит перемещение

· Местоположение – место, где произошло или происходит действие

· Потребитель – лицо, для которого выполняется действие

· Сырье

· Время – момент совершения действия

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

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

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

Свойства семантической связи выражается через рефлективность, симметричность и транзитивность.

Нечеткая логика

При формализации знаний часто встречаются качественные знания(молодой специалист, …)

Для формирования представления таких качественных знаний американский математик из университета Беркли в Калифорнии Лофти А.заде в 1965 году предложил формальный аппарат нечеткой логики(fuzzy logic).

Нечетное подмножество N множества M определяется, как множество упорядоченных пар N;

N = {Mn(x)/x} где М – характеристическая функция принадлежности Mn(x) прин [0,1] и указывает степень или уровень принадлежности элемента x подмножеству N.

По другому нечеткое множество можно записать так:

N = где Xi – iе значение, + имеет смысл объединения;

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

Например, лингвистическая переменная обозначающая возраст:

ЛП = МиВ, ДВ, ОВ, ЮВ, МВ, ЗВ, ПВ.

Множеством М будет шкала прожитых человеком лет от 0 до 120

М [0…120]

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

Эксперт определил, что МВ:

Возраст	Степень уверенности
	0,8
	0,95
	0,95
	0,7

М(х1) = 0,8; М(х2) = 0,95; М(х3) = 0,95; М(ч4) = 0,7

МВ = (М(х1)/х1) + (М(х2)/х2) + (М(х3)/х3)+ М(х4)/4

Некоторые множества позволяют учитывать отдельные мнения экспертов.

Графически,функция принадлежности:

Нечеткое или:

М(х) = max(M1(x), M2(x))

M(x) = M1(x) * M2(x) – M1(x) * M2(x) – при вероятностном подходе

Нечеткое или позволяет реализовывать такие понятия как неполнота, неточность, некорректность.

Операции над нечеткими множествами

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

1. Операция дополнения: ; (Ui);

2. Операция объединения: F v G =

3. , где v – взятие максимума

4. Операция пересечения: F G = ; , где - взятие минимума

5. Операция симметричная разность:

F G = (F v G) = D ()

D () =

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

Нечетким отношением R между полными множеством U и другим V называется нечеткое подмножество прямого векторного произведения U x V, которое определяется:

R =

U = {U1, U2,…Un}, V={V1,V2,…Vm}

Пусть между элементами на ней, представленными нечеткими множествами F и G существует связь, которая задается правилом, если F то G и F U, G V

Один из способов построения нечеткого отношения – импликация F -> G

R = FxG=

F = 1/1 + 0.6/2 + 0.1/4 маленькое число

G = 0.1/2 + 0.6/3+1/4 большое число

«Если U – маленькое число, то V – большое число»

R = FxG

R =

Свойства нечетких отношений:

Объединение:

Пересечение:

Операция включения:

Поглощение:

Коммутативность:

Ассоциативность:

Дистрибутивность:

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

Если

Симметричность:

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

Композиция нечетких отношений

Пусть R – нечеткое отношение из области U в область V

S – нечеткое отношение из области V в область W, тогда из U в W:

R*S =

Пример применения максиминной свертки:

R – «если U – маленькое, то V - большое»

U = V = {1,2,3,4}

При парных сравнениях элементов i-стоки и j- столбца, из них выбираются наименьшие, затем из 4х минимальных элементов выбирают максимальный, который является результатом и записывают в ячейку с координатами (i, j)

Нечеткие выводы

Рассмотрим правило вывода modus ponens среди нечетких знаний

«если А – истинно и импликация А ->В истинна, то В - истинно»

А и А* и образец А* не всегда совпадают

В* = А* (*)R, где R – нечеткое отношение A->B

В* - приближенное значение, которое выражается нечетким множеством

Вариант№10

При формализации знаний часто встречаются качественные знания(молодой специалист, …)

Нечетное подмножество N множества M определяется, как множество упорядоченных пар N;

По другому нечеткое множество можно записать так:

N = где Xi – iе значение, + имеет смысл объединения;

Нечеткое или:

М(х) = max(M1(x), M2(x))

M(x) = M1(x) * M2(x) – M1(x) * M2(x) – при вероятностном подходе

Нечеткое или позволяет реализовывать такие понятия как неполнота, неточность, некорректность.

Операции над нечеткими множествами

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

6. Операция дополнения: ; (Ui);

7. Операция объединения: F v G =

8. , где v – взятие максимума

9. Операция пересечения: F G = ; , где - взятие минимума

10. Операция симметричная разность:

F G = (F v G) = D ()

D () =

R =

U = {U1, U2,…Un}, V={V1,V2,…Vm}

Один из способов построения нечеткого отношения – импликация F -> G

R = FxG=

F = 1/1 + 0.6/2 + 0.1/4 маленькое число

G = 0.1/2 + 0.6/3+1/4 большое число

«Если U – маленькое число, то V – большое число»

R = FxG

R =

Свойства нечетких отношений:

Объединение:

Пересечение:

Операция включения:

Поглощение:

Коммутативность:

Ассоциативность:

Дистрибутивность:

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

Если

Симметричность:

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

Композиция нечетких отношений

Пусть R – нечеткое отношение из области U в область V

S – нечеткое отношение из области V в область W, тогда из U в W:

R*S =

Пример применения максиминной свертки:

R – «если U – маленькое, то V - большое»

U = V = {1,2,3,4}

Вариант№11

Когда решение готово, нужно воплотить его в жизнь и измерить достигнутый результат.

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

Для получения рационального решения нужно:

1. Достоверная оценка текущей ситуации;

2.Сформировано множество допустимых решений;

3.Для каждого решения из этого множества нужно оценить последствия их принятия

2) Процесс принятия решений имеет итерационный многошаговый характер.

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

ОПРЕДЕЛЕНИЯ:

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

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

Состояние системы – это множество существенных свойств, которыми она обладает в определенный момент времени.

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

Поведение системы во времени - это процесс изменения состояний системы. Оценивается по степени достижения цели, ее функционирования.

Действие - происходящее с системой событие, вызванное другим событием.

Событие – изменение по крайней мере одного свойства системы.

Законом функционирования, описывающим процесс функционирования системы во времени, называется зависимость y(t) = F(x,n,k,t). Оператор F преобразует независимые переменные в зависимые и отражает поведение системы во времени.

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

Процесс выработки решений

Вариант№12

Основные виды задачи принятия решений:

5. Формализуемые: Особенности – хорошо структурированные, хорошо формализуемые, т.е. описание процессов в количественной среде достаточное для получения адекватных моделей.

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

7. Трудноформализуемые: Особенности – слабо структурированные. Информативные переменные можно измерить или оценить, но в разнотипных шкалах (качественных и количественных). Множество возможных решений конечно и имеет сравнительно невысокую мощность.

8. Задачи теории игр: Особенности – различают неантогонестические и антогонистические игры. Совокупность целенаправленных действий называется операцией.

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

· Перечень субъектов, участвующих в конфликте;

· Определением множеств их выборов;

· Интересами, определяющими выбор;

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

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

Теория игр – это математическая теория принятия решений в конфликтных ситуациях.

Основной задачей игр является не описание, а разрешение конфликта.

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

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

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

Вариант№13

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: