1626434760-4c9f92f9ed5188f8fc024fed893742bb (844133), страница 3

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

Текст из файла (страница 3)

и п.2Think(Иван)(п.6) из п.5. и п.3∅(п.7) из п.6. и п.439Использование метода резолюций длядоказательства теорем в логике 1-го порядкаВпервые метод резолюции был реализовал на ЭВМДж.Робинсоном в 1963 г.В 1970-е г.г. был разработан язык логическогопрограммирования ПРОЛОГ, в основу которого наряду сбэктрекингом был положен метод резолюции.Это позволило определять задачи в форме исчисленияпредикатов первого порядка. В настоящее время существуютмногочисленные версии языка ПРОЛОГ, которые завоевалипопулярность как языки разработки систем искусственногоинтеллекта.40Основные модели представления знаний• Сетевая модель• Продукционная модель• Логическая модель1Основные модели представления знаний• Сетевая модель– Семантические сети• Функциональные сети– Фреймы• Продукционная модель• Логическая модель2Семантические сети (определение)Семантическая сеть (СС) - это ориентированныйграф, вершинам которого сопоставляютсяобъекты (понятия, конкретные объекты, события,процессы, явления и т.п.), а дугам - отношения,существующие между объектами.МашалюбитьлюбитьСашадругдругВася3Типы семантических сетейВ зависимости от вида используемых вершин и дугсети делятся на различные классы.По виду вершин: (1) простые и (2) иерархическиесети.Сети, включающие вершины, не имеющиевнутренней структуры, называются простыми.Если сеть содержит вершины, обладающиенекоторой структурой, например – в виде сети(процесс этот можно рекурсивно продолжать),то она называется иерархической.4Типы семантических сетейПо виду вершин: (1) простые и (2) иерархическиесети.(1)(2)Частным случаем иерархических сетей являютсяобъектно-ориентированные сети.5Типы семантических сетейПо типу дуг (отношений):(1) однородные и неоднородные сети;(2) бинарные и небинарные сети.Если все отношения между вершинами сетиодинаковы (одного типа), то такая сетьназывается однородной, в противном случае неоднородной.Если в сети используются только бинарныеотношения, то такая сеть называется бинарной.Важным случаем бинарных однородных сетейявляются сценарии.6Типы семантических сетейВсценарии в качестве единственного типаотношений выступает отношение нестрогогопорядка.

Семантика этого отношения может бытьразличной: оно может трактоваться как каузальное(причинно-следственное) отношение, временное(темпоральное)отношениеследования,классифицирующее отношение типа род-вид и т.п.В системах искусственного интеллекта сценарии, восновном,используются для формированиядопустимых планов по достижению цели.Сценарии, так же, как и любые другие сети, могутбыть простыми и иерархическими (вложенными).7Неоднородные семантические сетиКлассификация отношений:Класс-подкласс (SUB) - между понятиями.Элемент-класс (ISA) - между экземплярами понятий ипонятиями.Часть-целое (Part_of) - отношение включения одногообъекта в другой.Свойство-значение (цвет, вес, рост и т.п.).Темпоральные отношения (раньше, позже, одновременннои т.п.).Логические отношения (и, или, не, следование).Глубинно-падежныесемантическиеотношенияФилмора (агент, соагент, объект, инструмент, времядействия, место действия и т.п.).8Пример семантической сети9Функциональная сетьФункциональная сеть - представляет собой двудольныйориентированный граф, включающий вершины двух типов- объекты (переменные) и операторы (функции).Дуги отражают функциональные связи между операторами иобъектами.

Дуга, направленная от объекта к оператору,предписывает рассматривать этот объект как аргументданного оператора, дуга обратной ориентации указываетна то, что объект выступает по отношению к оператору вкачестве результата.Функциональные сети отражают некоторую декомпозициюопределенной вычислительной процедуры, а дугипоказываютфункциональную связь, устанавливаемуюмежду частями, возникшими в результате декомпозиции.10Пример функциональной сетиФункциональная сеть, описывающая уравнение:U = I * R.If2*RAf1 *f3 *U11Фреймы• Фрейм-представления были предложеныМ.

Минским – профессором из МТИ в1970-е годы.• «Фрейм - это структура данных,представляющая стереотипную ситуацию».• Существенно,чтофреймявляетсясовокупностью знаний о некоторомпонятии или явлении, например, событии,ситуации, объекте.12Структура фрейма• Фрейм по своей организации похож наиерархическую семантическую сеть.• Фрейм является сетью узлов и отношений,организованных иерархически, где верхние узлыпредставляют общие понятия, а нижние узлы более частные случаи этих понятий.• В системе, основанной на фреймах, понятие вкаждом узле определяется набором атрибутов(например, имя, цвет, размер) и значениями этихатрибутов (например, Петя, белый, средний), аатрибуты называются слотами.• Каждый слот может быть связан с процедурами,которые выполняются, когда информация вслотах меняется.13Структура фреймаFrame Имя_фрейма [is_kind_of Имя_Родителя].Слоты;end.Слот::= Имя_сл, Тип_сл, Значение_по_умолчанию,[Присоединенные процедуры].Присоединенные процедуры ::=Если добавленоЕсли удаленоЕсли требуется14Системы фреймовГруппы родственных фреймов объединяютсяв систему фреймов.Благодаря тому, что различные фреймы одной итой же системы используют общее множествослотов, становится возможным координироватьинформацию, полученную из различныхисточников.Системы фреймов, в свою очередь, связаныинформационно-поисковой сетью.В тех случаях, когда предложенный фрейм неудается привести в соответствие с имеющейсяситуацией, т.е.

когда для его слотов не удаетсянайти требуемых значений, эта сеть поставляетдругой, заменяющий его фрейм.15ПримерОТЧЕТявляетсяOTЧET OПРОДВИЖЕНИИявляетсяTЕХНИЧЕСКИЙОТЧЕТявляетсяOтчет № 216Фрейм отчета о продвижении17Фрейм отчета о продвижении18Фрейм отчета о продвижении19Фрейм отчета о продвижении2 стр.20Фрейм отчета о продвижении2 стр.21Использование фрейм-представленияРазработаны различные языки представлениязнаний на основе фреймов.Наиболее известными среди них являются:-KRL (Knowledge Representation Language)-FRL (Frame Representation Language).22Продукционная модельП р о д у к ц и о н н а я модель предполагает такойспособ организации вычислительного процесса, прикотором программа преобразования некоторойинформационной структуры C задается в видесистемы правил вида:Условие → Действие,где Условие специфицирует некоторые требования ктекущему состоянию структуры C, а Действиесодержит описание тех операций над C, которыенадо выполнить, если C удовлетворяет этимтребованиям.1Продукционная модель• Формальные системы– Системы подстановок– Формальные грамматики• Программные системы2Системы подстановокСистемы подстановок служат для обработки слов,заданных в некотором алфавите.К ним относятся:(1) системы продукций Поста (именно этимсистемам мы обязаны появлению термина "системапродукций", который получил со временем болееширокое употребление) и(2) нормальные алгоритмы Маркова.3Системы продукций ПостаСистемы Поста определяются алфавитом S инабором правил-продукций вида:aiW → Wbi (i = 1,...,m),(1)где ai и bi - некоторые слова в алфавите S.Правило (1) применимо к слову d, если d начинается сai .

В этом случае правило вычеркивает в d префикс aiи приписывает к нему справа слово bi .Например, применяя к слову ababc продукциюabW → Wd, получим слово abcd, к которому еще разможет быть применена та же продукция.4Нормальные алгоритмы МарковаНормальные алгоритмы Маркова определяютсяалфавитом S и последовательностью подстановоквида:ai → biai →. bi ,где ai и bi - некоторые слова в алфавите S,а подстановка, отмеченная точкой являетсязаключительной.5Нормальные алгоритмы Маркова(n+1)-й шаг обработки начального слова d0 :Пусть в последовательности подстановок имеется первая,у которой левая часть ai хотя бы раз входит в слово dn(dn - слово, полученное в результате первых n шагов),тогда в dn вместо самого левого вхождения aiподставляется bi, порождая слово dn+1.Если использованная подстановка не былазаключительной, осуществляется переход к шагу (n+2),в противном же случае dn+1 объявляется результатомработы системы.Если на шаге (n+1) не нашлось ни одной применимойподстановки, то результатом будет слово dn.6Формальные грамматикиФормальные грамматики были введены Хомским,предложившим описывать их четверкой< V, T, P, Z >,где V - алфавит, T ⊆ V - алфавит терминальныхсимволов, P - конечный набор правил подстановки,Z - начальный символ.Накладывая различные ограничения на видправил подстановки, получают грамматикиразличных классов.Формальные грамматики, как и системыПоста, не предусматривают порядка примененияправил и также являются недетерминированными7системами.Формальные грамматикиС самого начала формальные грамматикииспользовались при анализе формальных иестественных языков, что стимулировало ихпостоянное усложнение и развитие в качествеинструментальных средств программирования.Первым продукционным языком программированиябыл язык Флойда, основанный на грамматике ипредназначавшийся для синтаксического анализа.8Программные системыПрограммные продукционные системы - системы,имеющие программную реализацию.

Такие системыдалее называются системами продукций (СП).Программная СП состоит из трех основныхчастей: базы данных (рабочей памяти), множестваправил-продукций и интерпретатора.9Структура программной СПБаза данныхИнтерпретаторПравила10Структура программной СПБаза данных представляет собой рабочую память(различной организации), над которой работаетмножество правил.Правила могут иметь произвольную сложность, ноструктура у них прежняя: левая часть - условиеприменимости, а правая часть - действие, котороеданное правило выполняет.Интерпретатор - поисковый процесс, состоящий,по крайней мере, из двух фаз: выбора продукции иее применения.11Выбор продукцийЗадача выбора продукции сводится к двумподзадачам:(1) максимально ограничить число продукций, условияприменимости которых будут проверяться,(2) из полученного множества продукций выбратьодну – с истинным условием применимости.Задача (1) – часто решается путем активации нужногоподмножества правил-продукций.Задача (2) возникает в связи с тем, в выделенномподмножестве продукций могут оказатьсяистинными условия более чем одной продукции.12Конфликтное множество продукцийМножество продукций, у которых условияприменения истинны в данный момент, называетсяконфликтным.Процедура выбора продукции из такого множестваназывается процедурой разрешения конфликта.13Способы выбора продукцийОсновные способы выбора продукций изконфликтного множества:- случайный выбор;- выбор по статическому критерию(например, первой применяется продукция с самыми жесткимитребованиями - продукция с самым длинным списком условий),либо на продукциях задан полный порядок или иерархия, приэтом первой применяется самая "старшая" продукция и т.п.);-выбор по динамическому критерию(например, приписыванием правилам и/или компонентам базыданных динамически вычисляемых весов (приоритетов); в этомслучае первой для исполнения выбирается продукция снаивысшим приоритетом, или продукция, условия (образец)которой удовлетворяется на данных, имеющих максимальный14приоритет).Управляющие стратегииВыделяется два класса управляющих стратегийприменения продукций: безвозвратная и пробная.При использовании безвозвратной стратегии накаждом шаге вычислений из конфликтногомножества для выполнения выбирается одна изподходящих продукций, и в дальнейшем вернуться кэтой точке вычислений и применить другуюпродукцию невозможно.При пробной стратегии, называемой такжебэктрекингом, обеспечивается возможностьвозврата к уже пройденной точке вычислений иприменения другой (альтернативной) продукции из15конфликтного множества.КфМ0p1p2p2…pnКфМ1КфМ11p11p12…p1np111p112…p11nКфМ2КфМ21p21p22p22…p2np211p212…p21nКфМ3КфМ31p31p32…p3np311p312…p31n…………………………………………16Стратегии применения СППо способу применения продукций выделяют два видасистем продукций: п р я м ы е и о б р а т н ы е.В СП, работающей в прямом направлении, образцом дляпоиска служит левая часть продукции (Условие).

Характеристики

Список файлов лекций