Пояснения к лабораторной работе №6

 

1. Механизм вывода на графах

Модели знаний являются основой компьютерных системах искусственного интеллекта. Назначение таких систем состоит в поиске решений задач, ответов на вопросы (запросы) пользователя, консультациях и т.п. В каждом таком случае требуется получать новые знания на основе уже имеющихся в БЗ. Способ получения новых знаний называется механизмом вывода. То есть, механизм вывода - это способ (в частном случае, алгоритм) поиска решения задачи на основе исходных данных и моделей знаний, представленных в БЗ.

Пример 1. Пусть нужно получить функциональную семантическую сеть - ФСС, т.е. получить семантическую модель знаний о ромбе в форме двудольного графа.

Ромб имеет 7 характеристик: длину стороны а, острый угол a, тупой угол g, площадь S, периметр Р и диагонали и .

Эти величины связаны следующими формулами:

, , , , .

Двудольный граф - разновидность графа, в котором присутствуют вершины только двух типов (двух долей), назовем их «черными» и «белыми». «Черным» вершинам ставятся в соответствие объекты (понятия), «белым» - связи между ними. Любая дуга на таком графе проходит между двумя вершинами только разных цветов (рисунок 1).

Построим двудольный граф с семью «черными» вершинами (а, a, g, S, Р, , ) и пятью «белыми» (для каждой из пяти формул).

Отметим, что связи в ФСС - функциональной семантической сети заданы формулами. Формула определяет способ вычисления входящей в нее величины через остальные. Например, из формулы F3: S = a² sinα

можно вычислить S, если заданы а и α;

можно вычислить а, если заданы α и S;

можно вычислить α, если заданы а и S.

 

 

 

 

Рис. 1. Функциональная семантическая сеть

 

Пример 2. Рассмотрим процесс решения задачи на основе двудольного графа на рис. 1, представляющего модель знаний о ромбе в форме ФСС. Введем обозначения для формул, связывающих характеристики ромба:

F1: α + γ = 180,

F2: Р = 4а,

F3: S = a² sinα,

F4: S = d1d2/2

F5: d1² + d2² = 4а².

Дано (входные данные): длины диагоналей d1 и d2.

Требуется определить (выходные искомые величины): углы ромба α и γ.

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

Стратегии вывода. Вывод новых знаний идет в 2-х направлениях:

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

Для данного примера прямой поиск пойдет от известных ве­личин - d1 и d2 - к искомым - α и γ. Обратный поиск - от искомых α и γ к заданным d1 и d2.

Ход и путь вывода. Последовательность шагов прямого поиска отобразим в виде таблицы 5.

Таблица 5

Прямой поиск

№ шага	Что известно	Что требуется	Какие связи можно применить	Какую связь применим	Что найдем
	d1, d2	α, γ	F5, F4	F5	a
	d1, d2, a	α, γ	F4, F2	F4	S
	d1, d2, a, S	α, γ	F2, F3	F2	P
	d1, d2, a, S, P	α, γ	F3	F3	α
	d1, d2, a, S, P, α	γ	F1	F1	γ
	d1, d2, a, S, P, α, γ

 

1) Для начала проверим, не принадлежат ли искомые данные к множеству уже известных. В данном случае это не так: известны d1 и d2, требуется найти а и γ. Начнем поиск. Зная диагонали, имеем достаточно данных для того, чтобы применить связи F5 и F4. Выберем одну из них случайным образом, например F5. Преобразовав соответствующее математическое выражение, найдем а - длину стороны ромба.

2) Множество известных данных расширилось, поэтому в начале второго шага снова проверим, а не входят ли искомые величины в множество уже известных? Нет. Продолжим поиск. Известные величины - d1, d2, a - позволяют применить три связи: F5, F4, F2. Применять связь F5 нет смысла: ее уже использовали и ничего нового она не даст. Остаются F4 и F2. Выберем случайным образом одну из них, например F4. Применение этой связи позволит отыскать площадь ромба S.

3) Третий шаг опять начнем с проверки, не получен ли результат? Поскольку это не так, оценим достигнутое. Четыре известные характеристики ромба позволяют применить две связи F2 и F3 (не считая уже отработанных F4 и F5). Выберем случайным образом одну из них, скажем F2. Применив ее, найдем длину периметра Р. Замечание. Здесь описан формальный алгоритм, пригодный для программирования. Человек не стал бы делать этот шаг, для него совершенно лишний. А вот программа его сделать вполне может, поскольку здесь в ней работает механизм случайного выбора.

4) Искомые величины все еще не найдены, поэтому продолжим поиск. Единственная связь, которой до сих пор не воспользовались и которая готова к применению, это связь F3. Воспользовавшись ей, найдем угол α.

5) Одно из искомых значений найдено. Осталась одна неопределенная величина и единственная неиспользованная связь - F1. Применим F1 и найдем с ее помощью второй угол - угол γ.

6) Сравнение множества известных данных и множества искомых данных показывает, что все требуемые данные найдены. Значит, задача решена.

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

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

Ход и путь вывода. Последовательность шагов обратного поиска отобразим в виде таблицы 5.

Таблица 5

Обратный поиск

№ шага	Что известно	Что требуется	Применение каких связей даст искомые величины	Что будем искать	Какую связь применим	Что нужно для применения этой связи
	d1, d2	α, γ	F1, F3	γ	F1	α
	d1, d2	α	F3	α	F3	a, S
	d1, d2	a, S	F2, F4, F5	a	F5	d1, d2
	d1, d2	S, d1, d2,	F4	S	F4	d1, d2
	d1, d2	d1, d2

 

1) Начинаем поиск от вершин двудольного графа, содержащих углы ромба (цели). Вычислить их можно с помощью связей F1 и F3. Случайным образом выберем одну из искомых переменных и одну из связей, которая способна ее вычислить. Пусть это будет γ и F1. Если удастся использовать эту связь, то сможем найти целевую величину γ. Но сделать это можно только в том случае, если будет известна величина α. Запланируем примене­ние связи F1. В множестве искомых данных оставим α.

2) Проверим, все ли искомые данные есть в множестве известных? Не все. В множестве целевых данных один единственный элемент - α, и вычисление его возможно с помощью единственной связи - F3. Для применения этой связи нужны а и S. Планируем применение связи F3, не удаляя из целевого множества а, добавляем в него S.

3) Все ли искомые данные известны? Нет. Выберем случайно одну из целевых переменных, например а, и одну из связей для ее вычисления, например F5. Для ее применения нужны d1 и d2. Планируем применение связи F5, вычеркиваем а из множества искомых переменных, дописываем в это множество d1 и d2.

4) В множестве искомых данных три переменные, но две из них входят в множество исходных данных. Искать надо только одну переменную - S. Для этого есть связь F4. Планируем применение этой связи. Для ее использования нужно знать значения переменных d1 и d2. Запишем их в целевое множество, удалив оттуда переменную S.

5) Все требуемые данные известны. Значит, если начать с этих данных и последовательно применять запланированные связи, то в конце получим решение поставленной задачи. Планирование закончено.

Полученный план определяет следующий порядок применения формул для решения задачи: F4 → F5 → F3 → F1. Сравните этот план с тем, что получен методом прямого поиска. Отсюда очевидна неоднозначность пути решения задачи.

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

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

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

ЗНАЯ М ВЫЧИСЛИТЬ Y₁, Y₂, …, Y_N ПО X₁, X₂, …, X_К.

Здесь М, Y₁, Y₂, …, Y_N, X₁, X₂, …, X_К - величины, которые имеют смысл, определяемый их вхождением в задачу - в ее постановку и условия; значит X₁, X₂, …, X_К - входные данные, Y₁, Y₂, …, Y_N - выходные искомые величины, значения их требуется вычислить, найти, определить. М - величина, которая выражает условие задачи. Идентификаторы ЗНАЯ, ВЫЧИСЛИТЬ и ПО имеют фиксированный смысл и служат для разделения известных данных X₁, X₂, …, X_К от искомых величин Y₁, Y₂, …, Y_N.

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

Пролог-программа triangle.pro

triangle.pro /* triangle - имя программы, pro - расширение, указывающее, */

/* что программа написана на Прологе*/

Predicates /* раздел описания предикатов */

point(4, 2). /* point(4, 2) - факт, полученный из предиката point(X, Y) */

/*подстановкой X=4, Y=2; ниже точка point(4, 2) обозначена как P3 и т.п.*/

point(6, 4).

point(7, 1).

seg1(P3, P4).

seg1(point(4, 2), point(6, 4)).

…

Clauses /* раздел клауз: правил А В, имеющих в Прологе вид А: - В*/

/* раздел утверждений, условий и т.п.*/

area(X, Y, Z): - Z is X*Y/2. /* здесь area(X, Y, Z) - площадь, ее числовое */

/* значение присваивается переменной Z*/

/* X= h_a - высота на Y=a - основание или */

/* X= h_с и Y=с, или же X= h_b и Y=b */

…

zapros: - makewindow(“Введите координаты точки”).

 

Goal /* раздел целей*/

zapros.

 

В программе triangle.pro отсутствуют следующие разделы:

Constans /* раздел констант, не обязательный */

Domens /* характеризация типов переменных и т.д.*/

/* (например) name = symbol - тип переменной symbol */.

Разделы

Clauses /* раздел правил, условия, предложения, правила, утверждения */

Goal /* раздел целей */

представлены лишь указанными выше фрагментами.

 

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

 

12345

Поделиться:

Популярное:

1. АБСОЛЮТНАЯ И ОТНОСИТЕЛЬНАЯ АДРЕСАЦИЯ ПРИ РАБОТЕ С ФОРМУЛАМИ
2. Аденовирусы. Характеристика возбудителей, принципы лабораторной диагностики.
3. Акценты в работе с финансовой (инвестиционной) информацией
4. Анализ результатов. Вывод по работе
5. БЕЗОПАСНОСТЬ В РАБОТЕ С ПЧЕЛАМИ
6. Библиографический список должен всесторонне охватывать исследуемую тему. В курсовой работе он должен содержать 10-15 наименований.
7. Библиографическое описание документов, представленных в списке использованных источников к работе
8. Бруцеллез. Этиология, принципы лабораторной диагностики, профилактика.
9. В РАБОТЕ С ДЕТЬМИ С ЗАДЕРЖКОЙ
10. В список должны включаться только те источники, которые действительно использовались в работе.
11. Виды и методы защиты информации при работе с компьютером
12. Вместо заключения (теоретические пояснения)