Модели представления знаний. Продукционные правила

Министерство  образования науки, молодежи и спорта Украины

Донецкий  национальный университет

Кафедра компьютерных технологий

 

 

 

 

 

Реферат

 

по дисциплине «Введение в специальность»

Тема: Модели представления знаний. Продукционные правила.

 

 

 

 

 

 

 

 

 

 

 

Выполнил  студент:

2 курса кафедры  КТ

специальности КН

Колесников  Владимир Григорьевич

 

 

 

 

 

 

 

 

 

Донецк 

2013

 

Раздел 1__________________________________________________________3

Раздел 2__________________________________________________________5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Раздел 1

 

1.Какие блоки  дисциплин учебного плана бакалаврата   “Компьютерные науки” я изучал  и, какие буду изучать:

Я изучал «Основы программирования и алгоритмические языки»

 и «Организация  и функционирование ЭВМ и систем» , а также буду изучать такие дисциплины как web-дизайн.

2.Что мне  уже читали по компьютерным  наукам:

- Основы программирования и алгоритмические языки

-Английский  язык;

- Организация  и функционирование ЭВМ и систем;

-Аналитическая  геометрия и Линейная алгебра;

-История  Украины;

-История  Украинской Культуры;

3.Специализации:

Компьютерные  науки (Программирование, администрирование, дизайн, КЭЭМ)

Все специальности  связанные с компьютером (изучение компьютера) и создание что-то нового для компьютера

Программирование: Создание программ и игр для компьютеров  таких программ как С++ и Java.

Администрирование: Создание html  файлов для сайтов и полное ознакомление с компьютером.

Дизайн: Создание и оформление сайтов Cinema 4d , Photoshop.

4.Кем я  хотел бы работать после окончания  университета:

После окончания  университета я думаю работать разработчиком игровых приложений для мобильных операционных систем. Таких как: Android, iOS, Windows phone.

5.Какую специализацию  я выбрал:

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

6.Какую тему  курсовой работы 2 курса я хотел  бы взять:

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

7.Кого из  преподавателей кафедры я хотела  бы выбрать руководителем курсовой  работы:

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

8.После окончания  Вуза:

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Раздел 2

 

1. Основные понятия

 

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

ЕСЛИ  условие ТО действие.

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

Пример. «Игра в восемь» (упрощенные пятнашки).

Задача. Дана доска, на которой  девять клеток, по которым перемещается восемь фишек. Их следует расположить  по порядку.

//рисунки – пример  начального расположения фишек  и правильное расположение фишек, которое должно получиться. (1)

2		3		1	2	3
1	6	4		8		4
8	7	5		7	6	5

 

Сформулируем правила. Условно  считаем, что мы как бы перемещаем не фишки, а пустую клетку (дырку).

A) Если дырка не в верхнем ряду, переместить ее вверх.

B) Если дырка не а правом столбце, переместить ее вправо.

С) Если дырка не в левом столбце, переместить ее влево.

D) Если дырка не в нижнем ряду, переместить ее вниз.

//рисунок хода игры (2)

 

2		3	←		2	3	↓	1	2	3	↓
1	6	4		1	6	4			6	4
8	7	5		8	7	5		8	7	5

 

 

1	2	3	→	1	2	3	↑	1	2	3
8	6	4		8	6	4		8		4
	7	5		7		5		7	6	5

 

Последнее состояние здесь  является терминальным (правильная расстановка  цифр).

Продукционные модели часто  используются при построении ЭС. Эта  модель удобна тем, что язык представления  ГБД может выбираться произвольно  в зависимости от задачи (в предикатных  языках ГБД представляется в виде набора предикатов). Структура ЭС описана в 2.2.7. Здесь, вспомним, что конечная цель – достижение терминального состояния ГБД.

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

Представление ГБД. (x,y,z,s).

x,y,z,s = 0 - соответствующий предмет на левом берегу

x,y,z,s =1 – соответствующий предмет на правом берегу

Таким образом,  (0,0,0,0) – исходное состояние, а (1,1,1,1) – терминальное состояние.

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

Исходя, их этого соображения  можно построить следующую таблицу:

Правило	Условие применимости
прямая перевозка волка – (0,y,z,0)->(1,y,z,1)	ù(y=0 Ùz=0)
прямая перевозка козы – (x,0,z,0)->(x,1,z,1)	всегда
прямая перевозка капусты – (x,y,0,0)->(x,y,1,1)	ù(x=0 Ù y=0)
прямая пустая перевозка	ù(y=0 Ù z=0) Ù ù(x=0 Ù y=0)
обратная перевозка волка – (1,y,z,1)->(0,y,z,0)	ù(y=1 Ùz=1)
обратная перевозка козы – (x,1,z,1)->(x,0,z,0)	всегда
обратная перевозка капусты – (x,y,1,1)->(x,y,0,0)	ù(x=1 Ù y=1)
обратная пустая перевозка – (x,y,z,1)->(x,y,z,0)	ù(y=1 Ù z=1) Ù ù(x=1 Ù y=1)

Очевидно, что на продукциях, можно поставить  задачи четырех типов:

1. Определить существует ли решение вообще?
2. Найти любое решение задачи.
3. Найти всевозможные решения задачи.

D) Найти из множеств решений оптимальное в каком-либо смысле. При этом в простейшем случае, под оптимальным понимается решение, требующее как можно меньше операций преобразования ГБД. В более сложных случаях, приходится оперировать с весовыми коэффициентами, соответствующими правилам.

 

2. Стратегии управления

 

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

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

Например – игра в девять. В рассмотренном в 3.1 примере, в качестве такового выступает число фишек, находящихся «не на своем месте».

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

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

 

2.1. Поиск с возвратом.

Самоназвание метода говорит о том, какие идеи в нем реализованы.

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

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

 

2.2. Поиск в пространстве состояний.

В данном случае в качестве вершин выступают состояния БД, а в качестве дуг – продукционные правила. Под раскрытием вершины, в данном случае, понимается применение к состоянию всех возможных правил. Рассмотрим применение метода на примере.

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

//пример – рисунок (3)

 

 

3. Понятие о коммутативных системах  продукций

 

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

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

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

1. Каждое правило, применимое к определенному состоянию ГБД, применимо ко всем состояниям, полученным из него посредством применения конечного множества правил.
2. Если цель (терминальное состояние ГБД) может быть достигнуто из состояния D, то она может быть достигнута и из всех состояний, полученных из D.

Следствием перечисленных  выше свойств является гарантия достижения цели (если это в принципе возможно) с помощью безвозвратных стратегий.

 

4. Понятие о нечетком выводе  на продукциях

 

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

Если в обычных детерминированных  моделях предполагается, что каждое правило является либо применимым или неприменимым, то в нечетких моделях для каждого состояния задана таблица вероятностей применения тех или иных правил. Можно высчитать вероятности достижения целей с помощью применения определенных последовательностей правил, можно определить самое вероятное решение, или найти решение, удовлетворяющее заданному вероятностному порогу (p>a, 0<=a<=1).

Пример. Опишем на продукциях задачу распознавания почтовых индексов (задача, аналогичная описанной в 2.3).

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

//рисунок (4 - рис. 24 из 2-й главы)

 

Сформулируем, например, следующие  правила.

//выдержки из  примеров правил в продукционном  виде. (5)

l₃, l₄, l₈ → 1    0,97     (1)

l₃, l₄     → 1    0,75      (2)

l₄, l₈     → 1    0,6       (3)

l₃, l₈     → 1    0,5       (4)

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

//пример вычисления  вероятностей (6)

Пусть:

p (l₃) = 0,9         p (l₄) = 0,9               p (l₈) = 0,95,

тогда:

по первому правилу:

p (1) = 0,9 ∙ 0,9 ∙ 0,95 ∙ 0,97 = 0,95 ∙ 0,81 ∙ 0,97 ≈ 0,75