Извлечение ответа методом резолюции

Метод резолюции реализует два этапа решения задач. Первый этап: доказывается теорема следует ли целевая функция G из множества ПФ Е, то есть существует ли такой х для которого G(x). Второй этап: найти значение этого существующего х.

1 этап: доказывается теорема, следует ли целевая функция G из множества ПФ Е, т.е. существует ли такой Х для которого G(x) (ƎxG(x))

2 этап: найти значение этого существующего x.

Пример: Если Саша всегда ходит за Машей, а Маша находится в кино, то где Саша?.

Находится (Маша, Кино) – факт.

На языке предикатов факт: находится (маша, кино)

Правило: ∀x(находится(маша,Х))→находится(саша,Х)

Аксиомы: nahod(masha,kino)

∀X(nahod(masha,X))→nahod(sasha,X)

Целевая функция: ƎX(nahod(sasha,X))

Теорема: ƎX(nahod(sasha,X))

Проведем доказательство теоремы методом резолюции.

Доказательство: Согласно следствию из основной теоремы логического вывода ПФ F₁&F₂&…F_n&G –противоречие G=ƎX(nahod(sasha,X))

G=(ƎX(nahod(sasha,X))) не существует ни одного Х, где находится Саша.

Согласно формуле ƎXP(X)=(∀XP(X))

∀X(nahod(sasha,X))

(ƎX(nahod(sasha,X)))= ∀X(nahod(sasha,X))

Образуем множество Е ПФ состоящих из множества исходных предложений баз знаний объединенного с множеством предложений отрицания целевой функции.

Е=F∪G

F={F₁,F₂}, где
F₁ {nahod(masha,kino)} F₂ ={∀X(nahod(masha,X))→nahod(sasha,X)}

В результате множество Е имеет вид:

Е={nahod(masha,kino), ∀X(nahod(masha,X))→nahod(sasha,X), ∀X(nahod(sasha,X)))}

Согласно закону логики A→B=A∨B, преобразуем ПФ в соответсвии с правилами баз знаний.

∀X(nahod(masha,X))→nahod(sasha,X) = ∀X(nahod(masha,X)) ∨ nahod(sasha,X))

Опускаем знаки кванторов во всех ПФ входящих в множество {Е}. В результате множество Е примет вид:

E={nahod(masha,kino),(nahod(masha,X)∨nahod(sasha,X)),(nahod(sasha,X))}

Далее осуществляется вычисление резольвенты по формуле:

r_ij {{L_i } – { l_i }}_N’ ∪ {{M_i}-{m_i}}_N’

Шаг 1:

1) Принимаем за множество Li отрицание цели {L_i}={nahod(sasha,X)}

2) Выбираем за {l_i}⊂{L_i} ={nahod(sasha,X)}

3) Принимаем за множество {Mi} преобразованную аксиому F2

{M_i}={nahod(masha,X) ∨ nahod(sasha,X)}

4) Принимаем за {m_i}⊂{M_i}, где {li}N’={mi}N’ {mi}={nahod(sasha,X)}

5) Определим c_i ={Li}-{li}

ci={ nahod(sasha,X)N’-{ nahod(sasha,X)}N’={}

cj = {Mi}-{mi}

cj={ nahod(masha,X)∨ nahod(sasha,X)}N’-{nahod(sasha,X)}={ nahod(masha,X)}

Вычислим rij = {ci}∪{cj}={}∪{ nahod(masha,X)}

 

nahod(sasha,X)

nahod(masha,X)∨ nahod(sasha,X)

nahod(masha,X)

 

Рисунок -дерево опровержения

 

Шаг 2: Принимаем за множество Li-отрицание.

1) L_i={nahod(masha,X)}

2) Выбираем за {l_i}⊂{L_i}

{l_i}={ nahod(masha,X)}

3) Выбираем за множество M_i – аксиому F₁={ nahod(masha,X)}

{M_i}={ nahod(masha,kino)}

4) Выбираем за {m_i} ⊂ {M_i}, где {l_i}_N’={m_i}_N’

НОУ N’ = {kino/x}

{m_i}_N’={ nahod(masha,kino)}

{l_i}_N’={ nahod(masha,X)}

5) Определим c_i и c_j

c_i={L_i}_N’- {l_i}_N’ ={ nahod(masha,kino)}_N’ -{ nahod(masha,kino)}_N’={ }

c_j={M_i}_N’-{m_i}_N’

c_j={ nahod(masha,kino)}_N’-{ nahod(masha,kino)}_N’={ }

Тогда r_ij=c_i ∨ c_j={ } { }

nahod(sasha,X)

nahod(masha,X)∨ nahod(sasha,X) d nahod(sasha,X)

nahod(masha,X)

nahod(masha,kino)

N∪L

 

Результат: резольвента r_ij является пустым множеством { }, следовательно множество Е является противоречивым ⇒ существует такой Х, что ∃Xnahod(sasha,X)

Для извлечения ответа из дерева опровержения методом резолюции строится дерева доказательства.

Алгоритм построения дерева доказательства

1) Добавить каждой ПФ(предложению), возникающий из отрицания целевой функции её собственное отрицание.

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

3) Использовать предложения в корневой вершине в качестве ответного утверждения.

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

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

Шаг 1.

1) Добавляем к каждому предложению, возникающей из отрицания целевой функции его собственное отрицание и строим множество {L_i}

{L_i}={nahod(sasha,X)∨(nahod(sasha,X))}

Преобразуем {L_i} по закону логики А=A, а так же учитываем что A∨A = Истина,

Где А=nahod(sasha,X)

{L_i}={nahod(sasha,X)∨(nahod(sasha,X))}

2) {l_i}⊂{L_i}, {L_i}={ nahod(sasha,X)}

3) Принимаем {M_i} аксиому F₂, {M_i} = { nahod(masha,X)∨(nahod(sasha,X)}

4) {m_i}⊂{M_i}, где {li}_N’={m_i}_N’={ nahod(sasha,X)}

5) c_i={{L_i}-{l_i}}_N’={ nahod(sasha,X)∨ nahod(sasha,X)}-{ nahod(sasha,X)}={ nahod(sasha,X)}

c_j={{M_i}-{m_i}}={ nahod(masha,X)∨ nahod(sasha,X)} - { nahod(sasha,X)}={ nahod(masha,X)}

r_ij=c_i ∪ c_j = { nahod(sasha,X)} ∪ { nahod(masha,X)} = { nahod(sasha,X)∨ nahod(masha,X)}

 

nahod(sasha,X)∨ nahod(sasha,X)

nahod(masha,X)∨ nahod(sasha,X) d nahod(sasha,X)

nahod(sasha,X)∨ nahod(masha,X)

nahod(masha,kino)

N∪L

Шаг 2.

1.Принимаем за множество

2.Выбираем за

3.Принимаем за аксиому F₁ = =

4

N=

m_i =

l_i=

5.C_i=

-

C_j = _Ni

r_ij =

r_ij =C_i C_j

r_ij =

 

V

V

 

Рисунок – Дерево отвержения

НОУ =

Представление процесса логического вывода с помощью И/ИЛИ дерева

И/ИЛИ дерево представляет собой рисунок:

 

 

F1(Y), F2(Y), F3(Y)

F1(Y)

F2(Y)

F3(Y)

 

 

Нейронные сети

 

Одним из наиболее перспективной ИИ системы. Это многопроцессорная система.

1.Недостатки и преимущества использования нейронных сетей

Преимущества:

1. 1.Параллельная обработка информации. Резко сокращается время на задачу

2. 2.Надежность функционирования

3. 3.Возможность обучения

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

Нейронные сети реализуются на нейрокомпьютерах. Они могут менять свое поведение в зависимости от составления окружающей среды. После анализа входных сигналов они самонастраиваются и обучаются. Первые нейронный сети создали в 50ые годы XX века. Первые искусственные нейронные сети в 70ые годы XX века. А в 90ые годы появился нейрокомпьютер на одном кристалле.

Пример: Многослойная, полносвязная нейронная сеть прямого распространения сигнала.

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

Входы 1 слой 2 слой Выходы

 

 

 

=f - Формула одного нейрона

 

Выход нейрона слоя i+1 рассчитывается как функция от суммы произведения веса на dход со слоя i это x.

N –число весов.

Обучение нейронных сетей: под обучением нейронных сетей понимается:

1) Процесс настройки архитектуры сетей (структуры связей между нейронами)

2) Настройка весов в ходах каждого нейрона.

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

Существует 3 вида обучения:

1) с учителем – известны правильные ответы к каждому входному примеру. Веса подстраиваются так, чтобы минимизировать ошибку;

2) обучение без учителя – распределение образцов по категориям за счет раскрытия внутренней структуры данных;

3) смешанное обучение – комбинация первого и второго.

Недостатки использования нейронных сетей:

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

2) Традиционные нейронные сети не способны объяснить как они решают задачу, что затрудняет проверку достоверности результата.

3) Высокая стоимость.

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

Преимущества нейронных сетей:

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

2) Решение задач в реальном времени.

3) Возможность решать интеллектуальные задачи без участия человека.

Области применения нейронных сетей:

1) Оборонная промышленность. Решение зада, распознавание образов.

2) Сети и телекоммуникации – расчет трафика между узлами сети.

3) Информационные технологии. Определение тематики текстовых сообщений.

4) Реклама и маркетинг.

5) Экономика и финансы. Используется в банках для отслеживания клиентов при использовании кредитных и банковских карт.

6) Здравоохранение. Проверка и анализ слуха у грудных детей

Перспективы развития нейронных сетей:

1) «Умные дома».

2) Разработка нейрокомпьютеров, способных общаться на естественном для человека языке.

3) Использование нейронных сетей в роботах.