История развития Искусственного Интеллекта

1. История развития Искусственного Интеллекта Исторически, теоретические разработки в области ИИ велись в двух основных направлениях: Первое направление связано с конвентами разработки интеллектуальных машин путем моделирования их биологического прототипа – человеческого мозга. Однако неоправданный оптимизм кибернетиков 50-х годов, возлагавших надежды на это направление не увенчался успехом, ввиду непригодности для этих целей существовавших тогда аппаратных и программных средств. Типичной реализацией этих идей стала система PERCEPTRON, которая представляет собой самоорганизующийся автомат, довольно грубо моделирующий сетчатку человеческого глаза. Хотя его и можно было научить распознавать образы, но это был лишь ограниченный класс зрительных образов. В то время считалось, что если взять сильно связанную систему модельных нейронов, которой вначале ничего не известно, применить к ней программу тренировки из поощрений и наказаний, то в конце концов она будет делать все, что ни задумает ее создатель. (Мозг человека содержит ∼ 1010 нейронов, каждый из которых по сложности соответствует, к примеру, одному транспьютеру (компьютер на одном кристалле, способный выполнять сравнительно небольшую программу и имеющий средства общения с несколькими соседями)). При имеющейся на сегодняшний день аппаратной и программной базе это направление вновь возрождается, причем вполне успешно (биокомпьютеры). Второе направление – разработка методов, приемов, специализированных устройств и программ для ЭВМ, обеспечивающих решение сложных математических и логических задач, позволяющих автоматизировать отдельные интеллектуальные действия человека. Первым шагом в этом направлении можно считать разработку GPS (General Purpose Sold) универсального решателя задач. В основу системы было положено представление об эвристическом поиске, в процессе которого обеспечивалось разбиение задач на подзадачи до тех пор, пока не будет получена легко решаемая подзадача. При разработке авторы начали с программы доказательства теорем, потом перешли к машинным шахматам, затем переключились на поиск общих методов, которые могли бы быть применены к широкому спектру задач. Система GPS была универсальной в том отношении, что «не было конкретного указателя, к какой области относится задача». Пользователь должен был задать «проблемную среду» в терминах объектов и тех операторов, которые к ним применимы. Однако, эта универсальность относилась лишь к ограниченной области математических головоломок с относительно небольшим множеством состояний и четко очерченных формальных правил («Ханойская башня», «Миссионеры и людоеды». (Кстати один из авторов этой системы Герберт Саймон в 1957г. предсказал, что через 10 лет компьютер станет чемпионом мира по шахматам). Попытки уйти от не оправдавших себя универсальных эвристик при решении интеллектуальных задач привели группу ученых Стэндфордского университета под руководством Э.Фейгенбаума к заключению о том, что главное, чем располагает специалист, – это накопленный им в процессе своей профессиональной деятельности некоторый набор разнообразных приемов и неформальных правил. На этом пути была разработана экспертная система DENDRAL, базирующаяся на знаниях, которая явилась прототипом всех последующих экспертных систем. В функционировании этой системы, используемой для решения задач химического анализа, можно выделить 3 основных этапа: – на первом с помощью базы знаний составляется список исходных условий, который на втором этапе дополняется пользователем, затем система генерирует, проверяет и ранжирует возможные решения, после чего выводит их на печать в порядке рангов. После появления системы DENDRAL стало быстро расти количество самых разнообразных экспертных систем. Одна из самых известных – это система MYCIN, разработанная Е.Шортклифом в 1976г. Эта компьютерная система предназначалась для консультационной помощи при диагностике инфекционных заболеваний крови. Она оказалась родоначальником серии медико-диагностических систем, используемых в рутинной клинической практике. Система MYCIN ввела в рассмотрение несколько характеристик, которые стали отличительной чертой экспертных систем. Во-первых, ее знания составляют сотни правил вывода с помощью которых анализируются как изначально заданные данные, так и вводимые пользователем. Во-вторых, эти правила являются вероятностными, то есть позволяющими оценить правдоподобность сделанного вывода по шкале оценок от 0 до 10. В-третьих, система MYCIN может объяснить свой процесс рассуждения шаг за шагом (например, почему был задан тот или иной вопрос). В-четвертых, она может быть использована для диагностики других инфекционных заболеваний. Вообще говоря, система MYCIN допускала возможность замены правил и данных, связанных с диагностикой инфекционных заболеваний, на другие, соответствующие другим областям, поскольку система обладала универсальным механизмом вывода, называемым EMYCIN. Данный механизм использовался, совместно с программой MARK, предназначенной для решения задач метолом конечных элементов. Следующим шагом в развитии ИИ стало появление в 80-х годах систем АМ и Eurisco, разработанных в Стэндфордском университете. Автор основывался на том, что эффективность любой экспертной системы определяется закладываемыми в нее знаниями. По его мнению, чтобы система была способна к обучению, в нее должно быть введено около полумиллиона сведений общего характера (это соответствует такому объему информации, каким располагает 4-х летний ребенок), что привело его к выводу о бесперспективности создания узкоспециализированных ЭС с уменьшенным объемом знаний. В систему АМ первоначально было заложено около 100 правил вывода и боле 200 эвристических алгоритмов обучения, позволяющих строить произвольные математические теории и представления. Хотя вначале результаты работы системы остановилось, и было отмечено, что система не может синтезировать новых эвристических правил, то есть ее возможности определяются только теми эвристиками, что были в нее изначально заложены. При разработке системы Eurisco была предпринята попытка, преодолеть указанные недостатки. Ранние результаты, полученные с ее помощью, были эффективными. Например, эта система 3 года подряд выигрывала в учебной игре, производимой в ВМФ США, хотя правила все время менялись, с ее помощью была разработана стратегия, содержащая ряд оригинальных тактических ходов, кроме того, она произвела переворот в области создания СБИС, изобретя трехмерный узел типа И/ИЛИ. Однако через некоторое время обнаружилось, что система не всегда корректно переопределяет первоначально заложенные в нее правила и также, как и система АМ, остановилась в своем развитии. 2. Особенности знаний Перечислим ряд особенностей, присущих этой форме представления информации в ЭВМ. 1. Внутренняя интерпретируемость. Каждая информационная единица должна иметь уникальное имя, по которому ИС находит ее, а также отвечает на запросы, в которых это имя упомянуто. Для этого в память ЭВМ вводится информация о некоторой протоструктуре информационных единиц.(В противном случае данные должна идентифицировать программа их использующая по указанию программиста). Эта информация размещается в памяти ЭВМ и показывает, в каких ячейках памяти хранятся те или иные информационные поля записей. При этом должны быть созданы специальные словари, в которых перечислены имеющиеся в ОП значения информационных полей. Таким образом, каждая запись будет экземпляром протоструктуры.В настоящее время СУБД обеспечивают реализацию внутренней интерпретируемости всех информационных единиц, хранимых в базе данных. 2. Структурированность. Информационные единицы должны обладать гибкой структурой. Для них должен выполняться «принцип матрешки», т. е. рекурсивная вложимость одних информационных единиц в другие. Каждая информационная единица может быть включена в состав любой другой, и из каждой информационной единицы можно выделить некоторые составляющие ее информационные единицы. Другими словами, должна существовать возможность произвольного установления между отдельными информационными единицами отношений типа «часть — целое», «род — вид» или «элемент — класс». 3. Связность. В информационной базе между информационными единицами должна быть предусмотрена возможность установления связей различного типа, характеризующих отношения между этими единицами. Семантика отношений может носить декларативный или процедурный характер. Например, две или более информационные единицы могут быть связаны отношением <<одновременно>>, две информационные единицы — отношением <<причина — следствие>> или отношением <<быть рядом>>. Приведенные отношения характеризуют декларативные знания. Если между двумя информационными единицами установлено отношение << аргумент — функция>>, то оно характеризует процедурное знание, связанное с вычислением определенных функций. Далее будем различать отношения структуризации, функциональные отношения, каузальные отношения и семантические отношения. С помощью первых задаются иерархии информационных единиц, вторые несут процедурную информацию, позволяющую находить (вычислять) одни информационные единицы через другие, третьи задают причинно-следственные связи, четвертые соответствуют всем остальным отношениям. Между информационными единицами могут устанавливаться и иные связи, например, определяющие порядок выбора информационных единиц из па- мяти или указывающие на то, что две информационные единицы несовместимы друг с другом в одном описании. Перечисленные три особенности знаний позволяют ввести общую модель представления знаний, которую можно назвать семантической сетью, представляющей собой иерархическую сеть, в вершинах которой находятся информационные единицы. Эти единицы снабжены индивидуальными именами. Дуги семантической сети соответствуют различным связям между информационными единицами, причем иерархические связи определяются отношениями структуризации, а неиерархические связи — отношениями иных типов. 4. Семантическая метрика. На множестве информационных единиц может быть задано отношение, характеризующее ситуационную близость информационных единиц, т. е. силу ассоциативной связи между ними. Такое отношение называется отношением релевантности и позволяет выделить в информационной базе некоторые типовые ситуации (например, «регулирование движения на перекрестке»). Такое отношение позволяет находить знания, близкие к уже найденным. 5. Активность. Для ИС неприемлема ситуация, когда данные пассивны, а команды активны. Как и у человека, в ИС актуализации тех или иных действий (команд) должны способствовать знания, имеющиеся в системе. Таким образом, выполнение программ в ИС должно инициироваться текущим состоянием информационной базы, т.е. появление в базе фактов или описаний событий, установление новых связей может стать источником активности системы. Перечисленные пять особенностей информационных единиц определяют ту грань, за которой данные превращаются в знания, а базы данных перерастают в базы знаний (БЗ). Совокупность средств, обеспечивающих работу со знаниями, образует систему управления базой знаний (СУБЗ). В настоящее время не существует баз знаний, в которых в полной мере были бы быть реализованы перечисленные выше пять особенностей. Знания представляют собой совокупность сведений (у индивидуума, общества или у системы ИИ) о мире (конкретной предметной области, совокупности объектов или объекта), включающих в себя информацию о свойствах объектов, закономерностях процессов и явлений, правилах использования этой информации для принятия решений. 3. Модели предоставления знаний Модели предоставления знаний можно условно разделить на декларативные и процедуральные. Декларативная модель представления знаний основывается на предположении, что проблема предоставления некоторой предметной области решается независимо от того, как эти знания потом будут использоваться. So модель условно делится на 2 части: статически описательные модели знаний и механизм вывода, оперирующий этими структурами и практически независимый от их содержательного наполнения. При этом в кокой-то степени оказываются раздельными синтаксически и семантические аспекты знания, что является определенным достоинством указанных форм представления из-за возможности достижения их определенной универсальности. В декларативных моделях не содержатся в явном виде описания выполняемых процедур, и модели представляют собой множество утверждений. Предметная область представляется в виде синтаксического описания ее состояния (по возможности полного). Вывод решений основывается на процедурах поиска в пространстве состояний. В процедуральном представлении, знания содержатся в процедурах – небольших программах, которые определяют как выполнять специфические действия (как поступать в специфических ситуациях). При этом можно не описывать все возможные состояния среды или объекта для реализации вывода. Достаточно хранить некоторые начальные состояния и процедуры, генерирующие необходимые описания ситуаций и действий. При процедуральном представлении знаний, семантика непосредственно заложена в описание элементов базы знаний. За счет чего повышается эффективность поиска решений. По сравнению с процедуральной частью статистическая База знаний у них мала. Она содержит не «неизменные аксиомы», а лишь так называемые «утверждения», которые применимы в данный момент времени, но могут быть изменены или удаленны в любое время. Процедуры могут активировать друг друга, их выполнение может прерываться, а затем возобновляться. Возможно использование процедур – «демонов», активизирующихся при выполнении операции введения, изменения или удаления данных. Главное преимущество процедурных модулей представления знаний заключается в большей эффективности механизмов вывода, за счет введения дополнительных знаний о применении (то есть знаний о том, каким образом использовать накопленные знания для решения конкретной задачи), что, однако, снижает их общность. Другое важное преимущество заключено в выразительной силе, то есть процедуральные системы способны смоделировать практически любую модель представления знаний. Кроме того, их выразительная сила проявляется в расширенной системе выводов, реализуемых в них. /Большинство расширенных форм выводов может быть охарактеризовано понятием «предположение об отсутствии» и сводится к схеме,: If A(предварительное условие) – истинно и нет доказательств против B, то предположить B/ Подобные правила вывода оказываются полезными в 2-х случаях: Неполнота знаний. If в системе представления отдельные факты не представлены или невыводимы, правила вывода позволяют гипотетически признавать их верными при условии, что в системе нет или в ней невыводимы доказательства противного. Вывод в условиях ограниченности ресурсов. Из-за ограниченности ресурсов процессы вывода не могут завершиться, а должны быть остановлены для получения результатов – здесь правила определяют дальнейшие действия системы. В ИС используются различные способы описания знаний: 1. Логические модели. В основе моделей такого типа лежит формальная система, задаваемая четверкой вида М=<Т, Р, А, В>. Множество Т есть множество базовых элементов различной природы, например слов из некоторого ограниченного словаря, причем для этого множества существует некоторый способ определения принадлежности или непринадлежности произвольного элемента к этому множеству. Процедура такой проверки (П(Т)) может быть любой, но за конечное число шагов она должна давать положительный или отрицательный ответ на вопрос, является ли x элементом множества Т. Множество Р есть множество синтаксических правил. С их помощью из элементов Т образуют синтаксически правильные совокупности (например, из слов - правильные фразы). Декларируется существование процедуры П(Р), с помощью которой за конечное число шагов можно получить ответ на вопрос, является ли совокупность X синтаксически правильной. В множестве синтаксически правильных совокупностей выделяется некоторое подмножество А. Элементы А называются аксиомами. Как и для других составляющих формальной системы, должна существовать процедура П(А), с помощью которой для любой синтаксически правильной совокупности можно получить ответ на вопрос о принадлежности ее к множеству А. Множество В есть множество правил вывода. Применяя их к элементам А, можно получать новые синтаксически правильные совокупности, к которым снова можно применять правила из В. Так формируется множество выводимых в данной формальной системе совокупностей. Если имеется процедура П(В), с помощью которой можно определить для любой синтаксически правильной совокупности, является ли она выводимой, то соответствующая формальная система называется разрешимой. Это показывает, что именно правила вывода являются наиболее сложной составляющей формальной системы. Для знаний, входящих в базу знаний, можно считать, что множество А образуют все информационные единицы, которые введены в базу знаний извне, а с помощью правил вывода из них выводятся новые производные знания. Другими словами, формальная система представляет собой генератор порождения новых знаний, образующих множество выводимых в данной системе знаний. Это свойство позволяет хранить в базе лишь те знания, которые образуют множество А, а все остальные знания получать из них по правилам вывода, что делает логические модели притягательными для использования в базах знаний. 2. Сетевые модели. В основе моделей этого типа лежит так называемая семантическая сеть. Сетевые модели формально можно задать в виде Н = . Здесь I есть множество информационных единиц; C1, С2,..., Сп — множество типов связей между информационными единицами. Г отображение, которое задает связи из заданного набора типов связей между информационными единицами, входящими в I. В зависимости от типов связей, используемых в модели, различают классифицирующие сети, функциональные сети и сценарии. В классифицирующих сетях используются отношения структуризации. Такие сети позволяют в базах знаний вводить разные иерархические отношения между информационными единицами. Функциональные сети характеризуются наличием функциональных отношений. Их часто называют вычислительными моделями, так как они позволяют описывать процедуры «вычислений» одних информационных единиц через другие. В сценариях, используются каузальные отношения, а также отношения типов «средство — результат», «орудие — действие» и т. п. Если в сетевой модели допускаются связи различного типа, то ее обычно называют семантической сетью. 3. Продукционные модели. В моделях этого типа используются некоторые элементы логических и сетевых моделей. Из логических моделей заимствована идея правил вывода, которые здесь называются продукциями, а из сетевых моделей—описание знаний в виде семантической сети. В результате применения правил вывода к фрагментам сетевого описания происходит трансформация сети за счет смены ее фрагментов, наращивания сети и исключения из нее ненужных фрагментов. Таким образом, в продукционных моделях процедурная информация явно выделена и описывается иными средствами, чем декларативная информация. Вместо логического вывода, характерного для логических моделей, в продукционных моделях появляется вывод на знаниях. 4. Фреймовые модели. Фреймы - это минимальные структуры информации, необходимые для представления класса объектов, явлений или процессов. В отличие от моделей других типов во фреймовых моделях фиксируется жесткая структура информационных единиц, которая называется протофреймом. В общем виде она выглядит следующим образом: (Имя фрейма: Имя слота 1 (значение слота 1) Имя слота 2 (значение слота 2); . . . . . . . . . . . . . . . . . . . Имя слота n (значение слота n)). Значением слота может быть практически что угодно (числа или математические соотношения, тексты на естественном языке или программы, правила вывода или ссылки на другие слоты данного фрейма или других фреймов). В качестве значения слота может выступать набор слотов более низкого уровня, что позволяет во фреймовых представлениях реализовать «принцип матрешки». При конкретизации фрейма ему и слотам присваиваются конкретные имена и происходит заполнение слотов. Таким образом, из протофреймов получаются фреймы-экземпляры. Переход от исходного протофрейма к фрейму-экземпляру может быть многошаговым, за счет постепенного уточнения значений слотов. Связи между фреймами задаются значениями специального слота с именем <<Связь>>. 1. Логические модели. Классическим механизмом представления знаний средствами математической логики является исчисление предикатов, которое позволяет формально описать понятия предметной области и связей между ними (используется, как правило, в проблемных областях с небольшим пространством поиска решений и достаточно определенными факторами и знаниями). Логика предикатов является расширением логики высказываний, так как основным объектом здесь является переменное высказывание (предикат), истинность и ложность которого зависят от значения его переменных. Элементы логики высказываний. Высказывание есть утвердительное предложение, которое либо истинно (И), либо ложно (Л). Истинным значением высказывания является И или Л, приписываемые ему. В логике высказываний символы P, Q, R и т.д., используемые для обозначения высказываний, называются атомарными формулами. Из высказываний с помощью логических операторов: ¬(отрицание), ∧(конъюнкция), ∨(дизъюнкция), → (если …, то… - импликация), ↔ (тогда и только тогда - равнозначность) строятся составные высказывания. Выражение, которое представляет высказывание или составное высказывание, называется правильно построенной формулой (ППФ) (далее просто формулой).Если P и Q - ППФ, то (¬P), (P∧Q), (P∨Q), (P→Q) и (P↔Q) ППФ. Пусть G - данная пропозициональная формула (пропозиция высказывание) и A1,A2,..An - ее атомарные формулы. Интерпретацией формулы G является такое приписывание истинностных значений атомарным формулам A1,A2,..An, при котором каждому Ai приписано либо И, либо Л (но не оба сразу). Формула G - истинна при некоторой интерпретации тогда и только тогда, когда G получает значение И в этой интерпретации; в противном случае говорят, что G ложна при этой интерпретации. Если формула истинна при всех возможных интерпретациях, то говорят, что она является общезначимой формулой (тавтологией) и обозначают ее . Если формула ложна при всех своих интерпретациях, то говорят, что она является противоречивой (противоречием) и обозначают . (Противоречивая формула невыполнима). Говорят, что две формулы P и Q эквивалентны (P=Q), когда истинные значения P и Q совпадают при каждой интерпретации P и Q. Существует множество эквивалентных формул, называемых законами, которые используются при преобразовании формул из одной формы в другую, особенно в "нормальную форму". Литера - это атомарная формула или ее отрицание. Формула Р находится в конъюнктивной нормальной форме (КНФ) тогда и только тогда, когда Р имеет вид: P P1∧P2∧…∧Pn, n ≥ 1, где каждая из P1, P2, …, Pn - дизъюнкция литер ( - равно по определению). Формула Р находится в дизъюнктивной нормальной форме (ДНФ) тогда и только тогда, когда Р имеет вид: P P1∨P2∨…∨Pn, n ≥ 1, где каждая из P1, P2, …, Pn - конъюнкция литер. Любая формула может быть преобразована в нормальную форму путем использования законов эквивалентных преобразований. P↔Q = (P→Q)∧(Q→P) P→Q = ¬P∨Q P∨(Q∧H) = (P∨Q)∧(P∨H) - Дистрибутивный закон P∧(Q∨P) = (P∧Q)∨(P∧H) - Дистрибутивный закон ¬(¬P) = P - Закон двойного отрицания - Закон де Моргана ¬(P∨Q) = ¬P∧¬Q ¬(P∧Q) = ¬P∨¬Q - Закон де Моргана - Закон исключенного третьего P∨¬P = P∧¬P = - Закон противоречия P∨ = P P∧ = P P∨ = P∧ = При логическом выводе в рамках данной формальной системы стоит задача образования из некоторой совокупности исходных ППФ новых формул, которые являются тавтологиями. Эта задача решается с помощью правил вывода и законов. Формула является выводимой, если она может быть получена из конечной совокупности исходных формул путем конечного числа шагов применения правил вывода. Таким образом, необходимо доказывать, что некоторая формула логически следует из других формул (доказательство теоремы) и проблема поиска решений сводится к проблеме доказательства теоремы. Элементы логики предикатов. В логике предикатов первого порядка (первого сорта) вводится еще три логических понятия: термы, предикаты и кванторы. При этом понятие атомарной формулы в логике предикатов шире аналогичного понятия в логике высказываний, так как там атомарная формула рассматривается как единое целое, ее структура и состав не анализируется, в связи с чем реализация логических рассуждений в логике высказываний невозможна. В логике предикатов для построения атомарных формул используются следующие типы символов: индивидуальные символы (имена объектов), или константы (строчные буквы a,b,c,…); символы предметных переменных (строчные буквы …, x, y, z); функциональные символы (строчные буквы …, f, g, h,…); предикатные символы (прописные буквы P,Q,R,… или слова из прописных букв). Всякая функция или предикатный символ имеет определенное число аргументов n (n-местный функциональный символ). Терм есть всякая константа или переменная. Если f есть n - местный функциональный символ, и t1, …, tn термы, то f (t1, …, tn) - терм. Предикат P(t1, …, tn), где Р - n местный предикатный символ, а t1, …, tn - термы, - является атомарной формулой логики первого порядка. Предикат - это логическая функция, заданная на термах (разной природы: константы, переменные, функции) и принимающая значение И или Л. С помощью атомарных формул (предикатов), пяти логических связок и двух специальных символов (∀ и ∃) можно строить различные формулы и выражения (∀ - квантор общности, ∃ - квантор существования). Областью действия квантора, входящего в формулу, является формула, к которой он применим, причем в формулах, состоящих больше чем из одной предикатной буквы, используются {} для обозначения области действия квантов (Например, ∀ x {}, означает, что любая переменная x в этих скобках относится к квантору ∀). Входящие переменной x в формулу называется связанным, когда x является переменной входящею в эту формулу квантора. В противоположном случаи вхождение переменной x в данную формулу называется свободным. При этом одна и таже переменная может иметь свободные и связанные вхождения в одну и туже формулу. Например, в формуле P(x,y)→∀ x P(x) первое вхождение x свободно, а 2-е и 3-е – связанные. Переменная y свободна, так как единственное вхождение y свободно. Переменная называется свободной (связанной) в данной формуле, если ∃ свободные (связанные) ее вхождения в эту формулу. Формула логики предикатов Р(x) (может показать зависимость Р именно от x, хотя в Р(x) помимо x могут быть другие свободные переменные) свободна для переменной у, если в Р отсутствуют вхождения x, попадающие в область действия кванторов ∀у и ∃у. Подставить переменную у вместо переменной x в предикатную формулу Р – значит заменить каждое свободное вхождение переменной x в Р вхождением у, но если Р(x) есть Н(x,z)→∀yQ(y), то она свободна для у, но если Р(x) есть Н(x) ∨ ∀y Q(x,y), то она не свободна для у. Выражение, которое строится из атомарных формул, логических связок и кванторов, есть ППФ (просто формула) логики предикатов. Атомарная формула есть ППФ. Если P и Q – ППФ, а x переменная в Р, то (¬P), (P∨Q), (P∧Q), (P→Q), (P↔Q), ∀ x P, ∃ x P – ППФ. Формула имеет определенный смысл, то есть обозначает определенное утверждение, если существует какая-либо интерпретация. Интерпретация формулы Р логики предикатов состоит из непустой предметной области D и указания значений всех констант, функциональных символов и предикатов из Р. Каждой константе ставится в соответствие определенный элемент из D; каждому n-местному функциональному символу – n–местная функция, отображающая Dn в D /Dn = {(x1, …, xn) /x1∈ D, …, xn ∈ D}/, каждому n–местному предикатному символу – отображение Dn в {И,Л}. В логике предикатов в качестве нормальной формулы выступает предваренная нормальная формула (ПНФ). Целью преобразования исходных формул в ПНФ является упрощение процедуры доказательства. Формула Р находится в ПНФ, если она имеет вид 1 x1, …, n xn (M), где каждое i xi, i = 1, n есть ∀ xi или ∃ xi, М - формула, не содержащая квантов. При этом 1 x1, …, n xn называется префиксом, М – матрицей формулы Р. Помимо рассмотренных эквивалентных формул логики высказываний в логике предикатов используются другие пары эквивалентных формул, содержащих кванторы. Их так же называют законами. Формулы содержат только переменную x для акцентирования вхождения этой переменной, хотя формулы могут содержать и другие переменные. (10а) x P(x) ∨ Q = x{P(x) ∨ Q} (10б) x P(x) ∧ Q = x{P(x) ∧ Q} (11а) ∀x P(x) = ¬∃x¬P(x) ; ∃x P(x) ∃x P(x) = ¬∀x¬P(x) ; ∀x P(x) ¬∀x P(x) = ∃x¬P(x) ; ∃x P(x) ¬∃x P(x) = ∀x¬P(x) ; ∀x P(x) ∀x P(x) ∧ ∀x H(x) = ∀x{P(x) ∧ H(x)} ∃x P(x) ∨ ∃x H(x) = ∃x{P(x) ∨ H(x)} H(y)} 1x P(x) ∨ 2xH(x) = 1x 2y{P(x) ∨ 1x P(x) ∧ 2xH(x) = 1x 2y{P(x) ∧ (11б) (12а) (12б) (13а) (13б) (14а) (14б) H(y)} В формулах (14) производится переименование связных переменных при условии, что переменная у не появляется в Р(x), если 1= 1=∃ в (14а) и 1= 1=∀ в (14б), то не надо переименовывать x в 1x H(x). Можно использовать (13). Применяя законы 1-9 и законы 10-14, можно преобразовать формулу в ПНФ. Рассмотрим роботизированный участок, оборудованный роботами– манипуляторами, промежуточными накопителями готовых изделий (Hi), транспортным роботом (ТР) и складом изделий (СИ). Задача ТР заключается в последовательном объезде промежуточных накопителей, сборе деталей (если они есть в накопителе) и транспортировке их на склад изделий. Если тележка ТР заполнена, то необходимо раньше заехать на СИ, разгрузиться, а затем продолжить объезд накопителей. Введем следующие предикаты: А = пуст (i-й накопитель) B = пуста (тележка ТР) C = освободить (i-й накопитель) D = перейти (i+1-й накопитель) E = перевезти (на СИ) F = вернуться (i-й накопитель) Тогда алгоритм работы ТР можно сформировать следующим образом: A→D /если i-й накопитель пуст → перейти к i+1 - му ¬A ∧ B → C ∧ D /если i-й накопитель не пуст и тележка пуста → освободить i-й накопитель и перейти к i+1 - му ¬B → E ∧ F /если тележка заполнена → перевезти ее на СИ и вернуться на i-й накопитель Переведем предикаты в каузальную форму A → D = ¬A ∨ D ¬A ∧ B → C ∧ D = ¬(¬A ∧ B) ∨ (C ∧ D) = (A ∨ ¬B) ∨ (C ∧ D) = = (A ∨ ¬B ∨ C) ∧ (A ∨ ¬B ∨ D). Это может быть представлено в виде 2-х ППФ A ∨ ¬B ∨ C A ∨ ¬B ∨ D; ¬B → E ∧ F = B ∨ (E ∧ F) = (B ∨ E) ∧ (B ∨ F). что также разбивается на две ППФ B∨E B∨F Таким образом, алгоритм работы ТР или система правил будет иметь вид ¬A ∨ D A ∨ ¬B ∨ C A ∨ ¬B ∨ D 3. B ∨ E B∨F Основной недостаток систем представления знаний на базе логики предикатов состоит в их ограниченной выразимости, т.к. существует большое число фактов которые тяжело или невозможно выразить средствами исчисления предикатов. Поиск путей преодоления этого недостатка ведётся в основном в 2-х направлениях: 1.Расширение и модификация логики предикатов. использование логик, позволяющих ограничивать применение предикатов и функций рамками некоторого подмножества предметной области и вследствие этого подчинять аргументы определённым семантическим ограничениям; использование логики предикатов второго порядка; использование модальной логики («необходимость» и «возможность»); использование вероятностной логики (вероятность истинности или ложности высказываний); использование многозначных и нечётких логик, в которых оценка истинности высказываний может принимать дискретные или непрерывные значения из интервала между «истиной» и «ложью». 2.Разработка глобальных механизмов представления. Здесь предполагается, что системы, основанные на исчислении предикатов, применимы лишь без представления «локальных» знаний, т. е. небольших и чётко ограниченных областей знаний. Эти знания должны быть затем объединены в глобальную схему. Достоинства представления знаний на базе логики предикатов: - они достаточно хорошо исследованы как формальная система; - их синтаксис и интерпретация хорошо определены. Поскольку существуют достаточно ясные правила, то результаты операций над БЗ также достаточно ясно определены. Утверждения о некоторой предметной области могут быть введены или удалены независимо от др. в БЗ. 2. Сетевые модели. Под П-объектом будем понимать объект, существующий в реальном мире. В БЗ ему соответствует некоторое описание, полнота которого определяется той информацией, которую имеет о П-объекте ИС. Такое представление в БЗ называется М-объектом. (Могут существовать такие Мобъекты, для которых в реальном мире нет соответствующих П-объектов, поскольку такие М-объекты представляют собой абстракции, полученные в результате операций типа обобщения внутри БЗ.) Способ интерпретации взаимосвязных П-объектов называется денотативной семантикой, а способ интерпретации взаимосвязных М-объектов - коннотативной семантикой. П-объект по отношению к соответствующему в БЗ М-объекту называется денотатом или референтом этого М-объекта, а М-объект по отношению к исходному П-объекту – десигнатом (именем, меткой, идентификатором и т. д.). Десигнат – это простейший элемент в СМ и он входит в класс так называемых терминальных объектов СМ. Терминальным объектом называется М-объект, который может быть разложен на более простые объекты. Остальные М-объекты называются производными объектами. Перечень терминальных объектов, которые могут образовывать классы или типы, задаётся при проектировании ИС. Ими могут быть числа, идентификаторы, строки, списки и т. п. Семантика терминальных объектов определяется набором допустимых процедур, оперирующих с ними, например, арифметические действия, сравнение строк или идентификаторов и т. д. Итак, каждая СМ базируется на множестве терминальных типов объектов: T = {D , T1 ,...Ti }. Принадлежность некоторого терминального объекта ti типу Tj0 обозначается ∈ j , символ D здесь обозначает тип десигнатов. Введём понятие фрейма в сетевой модели (так называемый СМ-фрейм). СМ-фрейм может быть задан в виде ассоциативного списка атрибутов (имя_атрибута_1 значение_1 … имя атрибута_N … значение_N). Под атрибутом понимается пара «имя атрибута - значение». Имена атрибутов характеризуют роли объектов, стоящих в позициях значений атрибутов. Рассмотрим высказывание «С 20 по 25 Иванов был командирован в Москву за счёт заказчика». В виде СМ-фрейма оно может быть представлено так: (командирован Иванов куда Москва с_какого_числа 20 по_какое_число 25 за_счёт заказчик) Однако, приведённый способ формализации недостаточен. Во-первых, при переходе к сети фреймов необходимо обеспечить уникальную идентификацию отдельных фреймов с помощью десигнатов или меток. Метки фреймов становятся узлами ассоциации соответствующих наборов атрибутов. Во-вторых, требует уточнения вопрос о коннотативном смысле фреймов. Можно сказать, что смысл задаётся перечнем имён и значений атрибутов. Если перечень имён постоянен и не совпадает с перечнем имён атрибутов фреймов другого вида, то возможно задание коннотативного смысла. Если же набор атрибутов переменен, либо в фреймах с разным смыслом приходится пользоваться одноимёнными атрибутами, а также если используется упорядочивающая атрибутизация с именами 1, 2, 3… или её сокращённый вариант – позиционная запись значений атрибутов без указания имён – порядковых номеров, то возникают осложнения. Т. о., целесообразно сопоставлять смысл фрейма с описанием его типа. С учётом сказанного, сеть фреймов может быть представлена в следующей символьной форме: метка ф. (С1 (С2 (С3 с_какого_числа имя ф. (десигнат) СЕВЕРНЕЕ СЕВЕРНЕЕ КОМАНДИРОВАН 20 по_какое_число 25 список атрибутов пункт_1 Москва пункт_2 Киев) пункт_1 Киев пункт_2 Москва) кто Иванов куда Москва за_счёт заказчика) Представим рассмотренные СМ-фреймы в виде сетей. СЕВЕРНЕЕ Пункт 1 Киев ∈ Пункт 2 С2 С1 Пункт 2 Пункт 1 Одесса Иванов Кто Москва КОМАНДИРОВАН Олег Куда ∈ 20 ∈ имя С3 С какого числа Кто За счет Заказчика С4 По какое число должность фамилия Г.р. Иванов 25 СНС 1968 Атрибут в СМ – это указатель конкретной роли некоторого элемента во фрейме. Благодаря свойству структуризации атрибут также может быть представлен фреймом (С4). На практике всегда решается вопрос об уровне детализации представлений, т.е. в отношении всех атрибутов устанавливается терминальный уровень А0. Иногда такие атрибуты называются системными, поскольку их семантика должна быть заложена на этапе проектирования БЗ. Иногда можно реализовать процедуру обратного преобразования – атрибутивной трансформации фрейма (превращение фрейма в атрибут). При этом фрейм, превращаемый в атрибут, должен иметь собственный атрибут, который имеет в качестве своего значения фрейм. КОМАНДИРОВАН цель ∈ Иванов чего С3 С5 значение ∈ согласование_ТЗ кто (C5 ЦЕЛЬ чего С3 значение согласование_Т3) КОМАНДИРОВАН Иванов ∈ С3 цель согласование_ТЗ кто (С3 КОМАНДИРОВАН цель согласование_ТЗ) Введём несколько понятий: Фактом (конкретным фреймом, фреймом-экземпляром) называется фрейм, у которого значения всех атрибутов являются терминальными объектами. Ситуацией называется выделенная в соответствии с определённым принципом совокупность фреймов. (Один фрейм – это элементарная ситуация. Ситуация, включающая всю модель, может быть охарактеризована как глобальная, а любое её собственное подмножество – как локальная). Вся модель – глобальная ситуация. Любое подмножество модели – локальная ситуация. КОМАНДИРОВАН КТО имя ∈ ∈ Иванов фамилия С4 РАБОТАЕТ ∈ НИИ где кто кто куда ∈ 1968 кто С6 Москва ЦЕЛЬ РАД г. р. С7 С3 чему чего ∈ С5 знач-е ТЗ должность с.н.с. это замкнутая ситуация относительно каждого из фигурирующих в ней термов («Иванов») локальные свойства «Иванова»: командирован с целью согласования ТЗ; является сотрудником НИИ; рад командировке глобальные свойства «Иванова» - объединение всех локальных свойств Других свойств нет согласно данному состоянию сети. Формально почти любая ситуацию можно трансформировать в один фрейм, расширив его соответствующими атрибутами, что, естественно, приводит к резкому возрастанию набора атрибутов соответствующего фрейма, либо к появлению нескольких его вариантов. В некоторых случаях, в частности при сведении в один фрейм элементарных фреймов разного характера, могут возникнуть практически непреодолимые трудности. Т.о., ситуации являются мощным изобразительным средством задания коннотативной семантики и значительно более богатым по изобразительным возможностям, чем фреймы. Замкнутой ситуацией для заданного объекта СМ называется компонент связанности сети, в который входит данный объект, т.е. полный набор фреймов, образующих этот компонент связности. Глобальным свойством М-объекта называется замкнутая относительно него ситуация. Локальным свойством М-объекта называется любая подситуация из ситуации, определяющая его глобальное свойство и включающая данный объект. Последние два определения являются исчерпывающими только для десигнатов (никаких других свойств, ктоме указанных в данном состоянии сети). Другие терминальные объекты помимо этого, как правило, наделяются определённой операционной семантикой (например, чипам приписываются свойства, определяющие способ вычислений арифметических операций, сравнений и т.п.). С другой стороны, правила работы с терминальными объектамидесигнатами могут быть значительно сложнее по сравнению с другими объектами, причём манипуляция подобными объектами часто бывает нетривиальной. (Например, на запрос в реляционную БД по кадрам о сотруднике выдаётся соответствующая запись, в которой заранее предусмотрен набор определённых полей, в СМ речь может идти либо о замыкании десигната «Иванов», либо о том или ином его подсвойстве). Точно так же могут достаточно сложными оказаться правила исключения (например, исключение Иванова из состава сотрудников конкретной организации не ограничивается локальным исправлением (библиотека, жильё и т.п.)). Особые правила работы с объектами влекут за собой необходимость в иерархиях, строящихся на основе отношений «часть - целое». Так, атрибутивные пары являются частями фреймов, фреймы – частями ситуаций и т.д. Сложность описания возрастает, когда одни и те же объекты входят одновременно в несколько иерархических структур (например, Иванов является сотрудником определённого отдела, членом коллектива определённой комнаты и т.д. В то же время он – член семьи, множества пассажиров определённого автобуса и т.д. Поэтому на Иванова должны распространяться правила поведения, которым подчиняются члены упомянутых коллективов). Т.е., при манипулировании объектами должны правильно обрабатываться последствия тех или иных действий. Одним из способов задания иерархических структур является представление множеств в качестве объектов. Необходимость в этом возникает, в частности, если запретить фреймам иметь более одного атрибута с тождественными именами (например, «Иванов был командирован в Москву и Смоленск»). На граф-схемах в этом случае используется однократно помеченное разветвляющееся ребро, а в символьных записях – новый вид объекта: список с типизирующей пометкой :& (С6 КОМАНДИРОВАН Смоленск)) (Кон’юнктивные множества). кто ИВАНОВ куда (:& Москва Повышение выразительных возможностей в СМ достигается также введением в формализм средств представления неопределённой, неполной, неточной информации. В тех случаях, когда текущие знания позволяют указать лишь множество объектов, из которого извлекается пока неопределённая выборка, употребляются объекты типа диз’юнктивного множества (:V): (С30 СДАСТ кто (:V Иванов, Петров, Сидоров что экзамен)) – известно множество сдающих экзамен, но кто конкретно сдаст – неизвестно; (XOR-множества – один объект из совокупности): (С40 партию) ВЫИГРАЕТ кто (:XOR Иванов, Петров) что шахматную -один из множества выиграет. Множество всех указанных типов может фигурировать в качестве самостоятельных объектов, задаваемых десигнатами. При этом фреймами может специфицироваться их мощность, теоретико-множественные соотношения вхождения, пересечения, указания конкретных элементов. Статусы и логическая структура МПОБ Использование фреймов требует фиксации их статусов в МПОБ. Простейшим статусом является статус истинности, а в нём тот статус, при котором фрейму, хранящемуся в базе, присваивается значение абсолютной истинности. Предполагается, что все фреймы, которые в данный момент имеются в базе, абсолютно истинны, а те, которых сейчас там нет, абсолютно ложны. Такая база называется замкнутой, и ей соответствует замкнутая модель представления знаний (БД авиарейсов: включает фреймы с атрибутами: ном_рейса, исх_пункт, пункт_назн, вр_вылета). В замкнутых моделях отсутствует необходимость в операции отрицания, так как оно реализуется исключением соответствующих утверждений из БЗ. Бедность замкнутых моделей проявляется в том, что в них отсутствует статус фреймов, рассматриваемых в отрыве от своей истинной оценки, а также отсутствует возможность работы с неопределённоистинными утверждениями. От этих недостатков избавлена открытая модель, в которой фреймам, отсутствующим в БД, присваивается статус «неопределён», а ложные факты хранятся явно (кроме того, могут использоваться фреймы с набором градаций истинности больше 3, или с бесконечным числом градаций, определённых на отрезке [0,1]). В МПОБ должны присутствовать специальные процедуры, называемые процедурами ассимиляции. Эти процедуры соотносят синтаксически правильные фреймы с текущим состоянием дедуктивного замыкания модели без учёта истинных значений, т.е. ясен смысл, и не заботятся о правильности («Я понял точку зрения собеседника»). Фреймы, по отношению к которым выполнимы процедуры ассимиляции, считаются осмысленными. Возможны случаи частичной осмысленности, а также тактика, при которой система на время допускает неосмысленные фреймы «в надежде», что в последствии процедуры ассимиляции смогут выполняться успешно. В некоторых случаях происходит пробное включение фрейма в модель, после чего дальнейшая работа продолжается в предположении, что ничего плохого не произойдёт. Если не возникает противоречий, то фрейм сохраняется, иначе происходит возврат и исследуется другой вариант ассимиляции, если он есть. В противном случае данный фрейм считается неосмысленным. Вывод в СМ есть последовательное применение правил вывода из заданной системы правил. Он позволяет получать утверждения, ранее в базе не зафиксированные (виртуальные утверждения). Вывод позволяет дать ответ на вопрос о существовании некоторого виртуального утверждения в данном состоянии базы, либо определить значения атрибутов некоторого утверждения. Наличие вывода расширяет диапазон решаемых задач, не перегружая МПОБ множеством явных и легко выводимых утверждений. Модель, пополненная всеми её виртуальными утверждениями, называется дедуктивным замыканием модели. Модель знаний, дедуктивное замыкание которой не содержит утверждений, отрицающих друг лруга, характеризуется модельной непротиворечивостью. При замыкании модели необходимо избегать появления противоречий, поэтому вводится специальный статус утверждений в МПОБ, который называется Д-статусом, а утверждения с таким статусом – Д-истинными (денотационно-истинными). Их истинность в рамках данной модели считается достаточной для решения интересующих систему задач. Д-статус определяется той измерительной процедурой, которая порождает модельное утверждение, или теми ограничениями исходного описания, которые зафиксированы при вводе этого утверждения в базу. Можно считать, что утверждения с Д-статусом являются утверждениями об эмпирических фактах, а утверждения с абсолютно истинным статусом является утверждениями некоторой теории. Т.о., в БЗ возникает как бы 2 истинные системы: теоретическая и эмпирическая, причём теоретически истинные утверждения не могут быть, как правило, эмпирически обоснованы. Истинный статус помимо абсолютного может иметь частный или относительный характер, отражать различные точки зрения на систему утверждений, составляющую конкретную МПОБ. В этом проявляется основное свойство систем представления знаний: многоаспектное моделирование действительности. Замкнутая кон’юнктивная абсолютно истинная МПОБ является «наивной» одновариантной копией фрагмента реального мира, и в общем случае полезно поддерживать множественный истинный статус утверждений (так называемый механизм множественных точек зрения). Понятия экстенсионала и интенсионала Средствами БЗ удобно реализуется механизм обобщения абстракции. Первый шаг на пути к этому – фиксация типа фреймов. лил Запись вида SCH (Pi)=(Pi……), j= 1, N i Будем называть схемой фрейма Pi ∈ {P1,…PT}, где T- количество типов фреймов в МПОБ; aj - имя j-го атрибута фрейма Pi , множество DOM (Pi,aj) – множество, называемое доменом, допустимых значений атрибута aj фрейма Pi , Ni – местность фрейма Pi , т.е. число атрибутов. Имя типа, например, Pi, объединяет факты данного типа Fik ∈ Pi, k=1,…Ei. Факт (схема факта): Fik=(<метка факта> Pi……), где в Fik: i- факт, принадлежащий Pi-му типу, k- номер факта; Vijk – значение атрибута aj. Факт является конкретом схемы SCH(Pi), если ∀j Vijk ∈ DOM (Pi aj), т.е. значения атрибута – конкретны, значения атрибута – терминальные объекты. Экстенсионалом фрейма EXT(Pi) называется множество всех фактов данного типа {FikEPi}, k=1,..Ei, зафиксированных в БД МПОБ. Здесь Ei – мощность множества EXT(Pi). Экстенсионалы фреймов в процессе функционирования ИС могут меняться. Множество экстенсионалов образует суперэкстенсионал SEXT(Pi). При этом для любого состояния МПОБ EXT(Pi) E SEXT(Pi). Прототипом pi фрейма Pi будем называть фрейм, имеющий структуру факта Fik, но в который помимо терминальных значений Vijk ∈ DOM (Pi aj) допускаются Vijk вида (:<имя переменной>), которые будем называть объявлением переменной. Под интенсионалом фрейма Pi будем понимать функцию INT(pi), которая вырабатывает множество фактов {Fj}E SEXT(Pi), являющихся конкретизацией прототипа pi фрейма Pi, либо пустое множество, если пересечение {Fj} и SEXT(Pi) пусто (т.е. pi на самом деле не является прототипом Pi). Пример. Пусть Pi=”сложить” или “+”, понимаемое в обычном арифметическом смысле. Тогда SCH(+)=(+ a1:INTEGER a2:INTEGER a3:INTEGER t-val:BOOLEAN) Пусть МПОБ в некотором своём состоянии содержит факты EXT(+)={(c20 + a15 a23 a38 t-val TRUE) (c21 + a15 a28 a311 t-val FALSE) (c22 + a11 a2-9 a3-8 t-val TRUE)} SEXT(+) представляет собой бесконечное множество, в котором каждой тройке целых чисел ставится в соответствие значение TRUE, если третье число равно сумме первого и второго, и FALSE в противном случае. Ясно, что хранение EXT(+) большого смысла не имеет, а SEXT(+) хранить вообще невозможно. В то же время не составит труда построить функцию INT(+), используя обычные арифметические операции сложения, вычитания и механизм конкретизации переменных, объявленных в прототипе pi [ex: pi=(+ a1:D1 a2:D2 a3:5 t-val TRUE)] Таким образом, использование интенсиональных описаний позволяет полностью виртуализовать соответствующие утверждения. Для фреймов, имеющих интенсиональное описание, бессмысленно вводить в БД МПОБ конкретизирующие их факты: они либо не несут новой информации, либо противоречат модели. Однако, лишь для немногих представляющих практическую ценность типов фреймов удаётся выписать «чистый» интенсионал, и зачастую полезной оказывается даже его аппроксимация. Использование таксономических структур в СМ-моделях Таксономические структуры – это иерархии абстрактных понятий, имеющие структуру дерева, корень которого представляет наиболее общее понятие, а остальные вершины – более частные понятия. Каждое абстрактное понятие таксономии, за исключением наиболее общего, наследует все свойства непосредственного надпонятия и добавляет к ним свои уточнения. Отношения SUP (быть надпонятием) и ему обратное SUB (быть подпонятием) являются транзитивными. Пример таксономии: таксономия понятия «спортивные мероприятия». спортивные мероприятия sup технические общефизкультурные виды sup … sup охота авиапарашютный лёгкая на лис спорт атлетика военно-прикладные sup … sup sup sup … парусный велоспорт спорт спорт … ∈ ∈бег … … прыжки в высоту … … (С70 БЕГ пол мужской длина 100м … …) Положительные стороны использования таксономических структур в СМ: 1.Организация фреймов в виде таксономической структуры существенно облегчает доступ к экстенсионалам соответствующих понятий для любого уровня общности, а также дедукцию при ответах на запросы к системе, в которых фигурируют фреймы, включённые в таксономию. 2.Наличие таксономической структуры может служить основой для рассуждений по аналогии, выполнения индуктивных умозаключений; так подпонятия некоторого абстрактного понятия в некотором смысле более близки, чем подпонятия разных понятий – эта особенность может использоваться в предположениях о формально не заданных свойствах некоторых объектов, либо служить основанием для подсказок и уточнений при диалоге с пользователем в процессе задания деклараций понятий (деклараций фреймов, дающих концептуальное описание соответствующих понятий). Недостатки таксономии заключаются в следующем: 1.Не существует единых принципов построения классифицирующих структур. Вопрос о выделении подклассов решается для каждого уровня таксономического разбиения отдельно. Любые другие аспекты работы с МПОБ классификацией поддерживаться не будут. В подобной ситуации могут использоваться мультииерархические таксономии, в которых отдельное абстрактное понятие может быть подпонятием не одного, а нескольких более общих понятий (например, квадрат – это равносторонний прямоугольник, и с другой стороны – ромб, содержащий прямой угол). При этом возрастает сложность работы, поскольку приходится иметь дело с графом классификации, а не с деревом. 1. Продукционные модели. В общем виде под продукцией понимается выражение следующего вида: (i); Q; P; A ⇒ B; N. Здесь i – имя продукции, в качестве которого может выступать некоторая лексема, отражающая суть данной продукции (например, «набор кода замка», «покупка книги»), или порядковый номер продукции в множестве продукций, хранящихся в памяти системы. Элемент Q характеризует сферу применения продукции (такие сферы легко выделяются в когнитивных структурах человека – то есть наши знания как бы «разложены по полочкам»). Разделение знаний на сферы позволяет экономить время на поиск нужных знаний. Такое же разделение на сферы в БЗ ИС целесообразно и при использовании для представления знаний продукционных моделей. Основным элементом продукции является её ядро А ⇒ В. Интерпретация ядра продукции может быть различной и зависит от того, что стоит слева и справа от знака секвенции ⇒ . Обычное прочтение ядра выглядит следующим образом: ЕСЛИ А, ТО В; более сложные конструкции ядра допускают в правой части альтернативный выбор, например, ЕСЛИ А, ТО В1, ИНАЧЕ В2. Секвенция может истолковываться в обычном логическом смысле как знак логического следования В из истинного А (если А не является истинным выражением, то о В ничего сказать нельзя). Возможны и другие интерпретации ядра продукции, например, А описывает некоторое условие, необходимое для того, чтобы можно было совершить действие В. Элемент Р есть условие применимости ядра продукции. Обычно Р представляет собой логическое выражение (как правило, предикат). Когда Р принимает значение «истина», то ядро продукции активизируется. Если Р ложно, то ядро продукции не может быть использовано (например, если в продукции «Наличие денег; если хочешь купить вещь х, то заплати в кассу её стоимость и отдай чек продавцу» условие применимости ядра продукции ложно, то есть денег нет, то применить ядро продукции невозможно). Элемент N оценивает постусловия продукции. Они актуализируются только в том случае, если ядро продукции реализовалось, и описывают действия и процедуры, которые необходимо выполнить после реализации В (например, после покупки некоторой вещи в магазине необходимо в описи товаров, имеющихся в этом магазине, уменьшить количество вещей такого типа на 1). Заметим, что выполнение N может происходить не сразу после реализации ядра продукции. Если в памяти системы хранится некоторый набор продукций, то они образуют систему продукций. В системе продукций должны быть заданы специальные процедуры управления продукциями, с помощью которых происходит актуализация продукций и выбор для выполнения той или иной продукции из числа актуализированных. В ряде ИС используются комбинации сетевых и продукционных моделей представления знаний. В таких моделях декларативные знания описываются в сетевом компоненте модели, а процедурные – в продукционном. В этом случае говорят о работе продукционной системы над семантической сетью. Классификация ядер продукций. ядра продукций детерминированные недетерминированные (ЕСЛИ А ТО обязательно В) (ЕСЛИ А ТО возможно В) однозначные (-“-) реализ. Ядра (ЕСЛИ А ТО с вероятностью вероятн. оценка р реализовать В) альтернативные лингвист. оценка реализ. Ядра (оценив. весами выбора) уверенности В) вероятностн. оценки веса (ЕСЛИ А ТО с вероятн. 0,5 В1 с вероятн. 0,3 В2 с вероятн. 0,2 В3) лингвистич. оценки веса (ЕСЛИ А ТО с большой долей уверенности В1 с меньшей В2) экспертные оценки веса (ЕСЛИ В ТО чаще В1 реже В2) (ЕСЛИ А ТО с большой долей прогнозирующие (ЕСЛИ А ТО с вероятностью р можно ожидать В) Ядра продукций делятся на 2 больших типа: детерминированные и недетерминированные. В первых при актуализации ядра и при выполнимости А правая часть ядра выполняется обязательно; во вторых В может выполняться и не выполняться. Т.о., секвенция в детерминированных ядрах реализуется с необходимостью, а в недетерминированных – с возможностью (ЕСЛИ А, ТО ВОЗМОЖНО В). Возможность может определяться некоторыми оценками реализации ядра. При этом оценка может быть вероятностной, лингвистической (связанной с понятием терм-множества лингвистической переменной) или какой-либо иной («ЕСЛИ А, ТО С ВЕРОЯТНОСТЬЮ р РЕАЛИЗОВАТЬ В», «ЕСЛИ А, ТО С БОЛЬШОЙ ДОЛЕЙ УВЕРЕННОСТИ В» - вероятностная и лингвистическая). Детерминированные продукции могут быть однозначными и альтернативными. Во втором случае в правой части ядра указываются альтернативные возможности выбора, которые оцениваются специальными весами выбора. В качестве таких весов могут использоваться вероятностные оценки, лингвистические оценки, экспертные оценки и т.п. («ЕСЛИ А, ТО ЧАЩЕ ВСЕГО НАДО ДЕЛАТЬ В1, РЕЖЕ В2»). Особым типом являются прогнозирующие продукции, в которых описываются последствия, ожидаемые при актуализации А, например, «ЕСЛИ А, ТО С ВЕРОЯТНОСТЬЮ р МОЖНО ОЖИДАТЬ В». Дальнейшую классификацию можно провести, опираясь на структуру ИС-мы: если х и y обозначают некоторые структурные составляющие ИС-мы или блоки, то ядро Ах ⇒ Ву обозначает, что информация об А берётся из блока х, а результат срабатывания продукции В посылается в блок у. Например, если в состав ИС входит БД (Д) и БЗ (З), то продукция Ад ⇒ Вз может соответствовать процедуре нахождения закономерностей по эмпирическим данным. Наиболее часто встречающийся тип продукции в такой классификации Аз ⇒ Вз. В этом случае Аз и Вз представляют собой некоторые фрагменты информации, хранящиеся в БЗ (при сетевом представлении это могут быть фрагменты семантической сети, при логических моделях – фрагменты того или иного исчисления). Тогда смысл продукции Аз ⇒ Вз состоит в замене одного фрагмента БЗ-ий другим. Для актуализации этой продукции необходимо, чтобы в БЗ существовал фрагмент, совпадающий с А, т.е. необходимо выполнить процедуру поиска по образцу. Пример: в БЗ для представления знаний используется семантическая сеть, имеющая в данный момент вид R2 R1 R3 a b R3 e R3 f R2 g R1 R2 j R3 c R1 R2 R3 i R1 h d a, b, c,… - вершины; Ri – отношения. И имеется продукция: R3 a R1 x R1 y R2 h ⇒ a h в которой x и y – переменные. Вообще говоря, поиск А в БЗ может быть организован различными способами. Например, можно сначала искать вершину а, затем все выходящие из неё дуги, помеченные отношением R3, затем параллельный процесс поиска дуг с отношением R1 из найденных вершин и т.д. Если поиск оказался успешным, то в семантической сети происходит замена, определяемая В, и возникает трансформированная сеть. R1 R2 a b c R3 d R2 R2 R3 e R3 f R2 g h … Управление системой продукций. При выполнении условия применимости ядер продукции для группы продукций возникает проблема выбора той продукции, которая в данной ситуации будет активизирована. Решение этой проблемы возлагается на систему управления системой продукций. Если, например, ИС реализована на ЭВМ с параллельной архитектурой, то из фронта готовых продукций (продукций, для которых в данный момент времени выполняются условия применимости) может выбираться не одна, а столько, сколько параллельных ветвей может одновременно в данной ситуации выполнять ЭВМ. Однако, независимо от количества актуализированных продукций задача альтернативного выбора остаётся. Возможны 2 пути её решения: централизованный и децентрализованный. В первом случае решение об актуализации принимается специальной системой управления, а во втором – складывающейся в этот момент ситуацией. Если порядок выполнения продукций произволен, то решение определяется текущей ситуацией или системой управления; если порядок важен, то в продукциях должна содержаться информация о требованиях к этому порядку. Если в постусловиях продукций указывается имя продукции, которая должна выполняться после данной, система продукций превращается в обычную программу для ЭВМ, т.е. реализует некоторый алгоритм. Существует несколько стратегий управления выполнением продукций. 1.Принцип «стопки книг». Основан на идее, что наиболее часто используемая продукция является наиболее полезной. Готовые продукции как бы образуют «стопку», в которой порядок определяется накопленной частотой исполнения продукций в прошлом. Подобный принцип особенно выгоден, когда частота исполнения подсчитывается с учётом некоторой ситуации, в которой ранее использовалась продукция, и это исполнение имело положительную оценку. При такой обратной связи метод «стопки книг» может превратиться в обучающуюся процедуру, адаптирующуюся к тем задачам, которые возникают во внешней среде. Управление по этому принципу наиболее целесообразно применять, если продукции относительно независимы друг от друга, например, когда каждая из них есть правило вида «ситуация(А) ⇒ действие(В)». 2.Принцип наиболее длинного условия. Заключается в выборе из фронта готовых продукций той, у которой стало истинным наиболее «длинное» условие выполнимости ядра (опирается на соображение, что частные правила, относящиеся к узкому классу ситуаций, важнее общих правил, т.к. первые учитывают больше информации о ситуации, чем вторые). Управление по этому принципу целесообразно применять в тех случаях, когда знания и сами продукции хорошо структурированы привязкой к типовым ситуациям, на которых задано отношение типа «частное - общее». 3.Принцип метапродукций. Основан на идее ввода в систему продукций специальных метапродукций, задачей которых является организация управления в системе продукций при возможности неоднозначного выбора из фронта готовых продукций. Например, метапродукция может опираться на факт вхождения определённых продукций во фронт готовых продукций. Если необходимые продукции входят во фронт, то определяется порядок их выполнения. 4. Принцип «классной доски». В ИС выделяется специальная рабочая область памяти – аналог классной доски (мелом пишем объявления и при необходимости их стираем). Как правило, на «классной доске» выделяются специальные поля для формирования условий применимости ядер продукций, различные для разных сфер применения продукций; специальные поля для записи результатов срабатывания продукций и для записи постусловий, если они адресованы другим продукциям. С этим принципом может комбинироваться принцип управления с помощью метапродукций, т.к. он требует проверки некоторых условий, которые фиксируются в рабочем поле памяти. Если система продукций работает над некоторой сетевой моделью в БЗ, то фрагмент знаний, которым оперируют продукции, фиксируется на специальном поле «классной доски» (это позволяет защитить знания от порчи работающими продукциями – особенно при наличии альтернативных продукций). 5. Принцип приоритетного выбора. Связан с введением статических или динамических приоритетов на продукции. Первые, как правило, формируются априорно на основании сведений о важности продукционных правил в данной проблемной области (из эксперта). Вторые вырабатываются в процессе функционирования системы продукций и могут представлять, например, время нахождения продукции во фронте готовых продукций. Если продукции работают над семантической сетью, приоритеты могут формироваться не в системе продукций, а в сети. 6. Управление по именам. Основано на задании для имён продукций, входящих в некоторую систему, некоторой формальной грамматики или другой процедуры, обеспечивающей сужение фронта готовых продукций и выбор из него готовой продукции для выполнения: Пример: (б) В&D ⇒ A; (в) A ∨ B ⇒ D; (г) D ⇒ C – эта (а) А ⇒ В; система из 4-х продукций недетерминирована, т.к. при выполнении А выполняется (а) и (в), при выполнении B и D выполняется (б), (в), (г), а должны выполняться все, т.к. условие применимости выполнено у всех (по умолчанию). Для устранения недетерминированности введём некоторую формальную грамматику для имён продукций: (а) ⇒ (б), (в) ⇒ (б), (а) ⇒ (г) – задан порядок выполнения продукций, т.о., фронт сузился (после (б) ⇒ ничего, после (а) ⇒ (б), (г)). 4. Сценарии. Особую роль в системах представления знаний играют стереотипные знания, описывающие известные стандартные ситуации реального мира. Такие знания позволяют восстанавливать информацию, пропущенную в описании ситуации, предсказывать появление новых фактов, которые можно ожидать в данной ситуации, устанавливать смысл происхождения ситуации с точки зрения более общего ситуативного контекста. Наиболее распространённой моделью для описания стереотипного знания являются сценарии. Сценарием называется формализованное описание стандартной последовательности взаимосвязанный фактов, определяющих типичную ситуацию предметной области. Это могут быть последовательности действий или процедур, описывающие способы достижения целей действующих лиц сценария. Наиболее распространёнными являются сценарии: в виде дерева, классифицирующие сценарии и каузальные сценарии. В первом случае в сценариях описывается, как некоторая цель может быть декомпозирована в систему подцелей (применяется при планировании решений). Во втором случае сценарии используются при обобщении знаний и представляют собой сети, между вершинами которых имеются отношения типа «часть - целое», «элемент – класс», «род - вид». В третьем случае сценарии используются для представления проблемно – зависимых каузальных знаний о событиях, действиях и процедурах. Рассмотрим их подробнее. КСЦ задаёт в обобщённом и структурированном виде типичную последовательность действий (или процедур) в заданной предметной области и описывается в виде фрейма следующего вида: (КСЦ имя: имя слота1 (значение слота1); ……………………………….. имя слотаn (значение слота n)). Имена слотов отражают следующие понятия: деятель и участники сценария, цели и мотивы деятеля и участников, время, место, средства реализации сценария, ключ, посылки, следствия, побочные действия, закономерности, системное имя сценария. Формально «значение слота» описывается в нотации Бэкуса-Науэра следующим образом: <значение слота>::=<спецификация значения слота>: <значение>|<спецификация значений>|NIL значения>:<последовательность <спецификация значений слота>::=n|s|p|сц|f|low|sys <значение>::=”имя” <последовательность значений>::=(<значение>,<значение>…<значение>)|(<значение>R1<значение R2>…) Спецификация значения слота указывает класс значений данного слота. Символы обозначают следующие классы значений: символ класс значений n число s субъекты действий p события сц сценарии V объекты f процедуры low закономерности sys системные имена Символы R1, R2,…Rk задают временные или каузальные отношения. Значение слота NIL говорят о его неопределённости. Пример: (КСЦ «посадка на рейс»: № рейса (n:861); деятель (s:дежурная); участники (s:пассажиры); цель деятеля (p:нахождение пассажиров в самолёте); цель участника (p:нахождение пассажиров в конечном пункте полёта); время (f:расчётное время проведения посадки); посылки (сц:(регистрация пассажиров R1 сбор на посадку R1 прохождение контроля R1 подача автобуса R1 подача трапа)); ключ (p:посадка в самолёт); следствия (p:нахождение пассажиров на самолёте); побочные действия (сц:(формирование багажа R1 погрузка багажа на рейс)); закономерности (low:(схема 1, схема 2, схема 3)); системное имя (sys:СЦЗ)). Здесь R1 – отношение «быть раньше». Слот «ключ» задаёт основание события, определяющее тип ситуации. Реализация ключевого события обеспечивает цели деятеля и участников сценария. Слот «посылки» описывает необходимые условия реализации сценария (в них содержится последовательность действий, которые надо выполнить, чтобы создать необходимые условия для осуществления ключевого события). Слот «следствия» задаёт результаты его выполнения. Слот «побочные действия» описывает действия, реализующиеся параллельно с выполнением действий в посылках сценария. Сценарий считается завершённым, если реализовано ключевое событие и достигнута цель деятеля. 4.5. Ленемы. Как мы видим, в ИИ существует множество моделей представления и обработки знаний. Для представления данных с простой ПО можно использовать какую-то одну из известных нам моделей. Если же ПО достаточно сложна, то для представления данных необходимо использовать несколько моделей. В то же время на характер представления знаний влияют 2 конфликтные точки зрения: разработчика и пользователя. Для первого важна просьба и однородность ЯПЗ, для второго – удобство. Рассмотрим модель представления знаний, в которой этот конфликт устранён. Рассмотрим модель представления знаний, в основу которой положена двухуровневая система, состоящая из языка спецификации знаний (L-язык) и базовой формальной системы (БФС), которая представляет собой самостоятельный язык представления знаний (ЯПЗ). Семантика L-языка полностью описывается в терминах БФС. Как и всякий ЯПЗ, он включает средства для формирования МПОБ и подъязык для спецификации конкретных фактов. Специфической единицей L-языка является ленема – конструкция, задающая схему описания понятий. Спецификации МПОБ и конкретных фактов в форме выражений L-языка существуют только на внешнем, пользовательском уровне, а собственно хранение и обработка информации осуществляется на уровне БФС. БФС. Состоит из 3-х компонентов: библиотеки понятий, функциональносемантической сети (ФС-сеть) и продукционной системы над ФС-сетью. Библиотека содержит описания классов (сортов) объектов, отношений и функций. Описания понятий включают 2 уровня: декларативный и интерпретационный (может отсутствовать). На первом вводится обозначение понятия, на втором – интерпретация; для класса объектов – носитель – множество значений (элементами носителя могут быть числа, строки, структуры, построенные на их основе; так, интерпретация может быть сопоставлена с классом ЧИСЛО – целые положительные числа, классом МАРКА_МАШИНЫ – множество соответствующих наименований и т.д.); для отношений и функций – способ их вычисления. Описание функции дополнительно несёт информацию о существовании и единственности её значения при всяком фиксированном наборе аргументов. Эта информация порождает структурный уровень ФС-сети. ФС-сеть объединяет в себе возможности функциональной и семантической сетей. В ней выделяется 3 типа вершин : объекты, функции и отношения. Дуги отражают связи функций и отношений с их аргументами. Каждая объектная вершина как и библиотека понятий имеет 2 уровня представлений : декларативный и интерпретационный. На первом с ней связывается класс (возможно несколько) и имя, на втором значение данного объекта или множество возможных значений. БФС изначально содержит определение класса МНОЖЕСТВО, семантика которого является встроенной. Функциональные вершины, а также отношения, имеющие интерпретацию в рамках ФС-сети, обладают собственной активностью. Отношения и функции, имеющие интерпретацию, пытаются вычислить или скорректировать значения своих аргументов. Функции, независимо от наличия интерпретации стремятся «склеить» объектные вершины, соответствующие их результатам при условии тождественности аргументов. Такие локальные процессы коррекции активизируются при всяком изменении объектных вершин и используются вплоть до полной стабилизации ФСсети. Процесс коррекции ФС-сети рассмотрим на примере: «Поль с 15-го по 25-е мая был в Варшаве. Дональд, сын Поля, в мае выступал на одном из заседаний семинара. Вскоре после выступления он передал материалы отцу.» Используем еще информацию: семинары в мае проводились по числам: 4, 13, 15, 24. ФС-сеть: t2 ∈ {4, 13, 15, 24} ∇ раньше когда ∇ t2 раньше t1={15, 25} когда материалы * * выступал где кто когда что передал кто * находился кому a2 семинар Дональд ∇ сын_отец кто где ∇ сын_отец Поль Варшава - объектные вершины - функциональные вершины (*) и отношения ( ∇ ) Это состояние ФС-сети требует коррекции: вершины А2 и Поль «склеятся» отношение раньше (t3, t1) сформирует значение t3= отношение раньше (t2, t3) скорректирует значения обеих переменных так: t3= <5,14>, t2 ∈ {4,13}. Со всякой объектной вершиной ФС-сети может быть связана продукция или множество продукций, которые активизируются при изменении данной вершины, т.е. можно осуществить привязку группы продукций к конкретному фрагменту ФС-сети. Что касается системы продукций, то существуют некоторые отличия от традиционного исполнения отдельной продукции. Пример: Продукция, отражающая свойство отношения порядка между точками на прямой (х1, х2, х3, х4 – точки, R-функция расстояния): (x1 (х<у); Данная запись описывает класс, элементами которого являются пары упорядоченных чисел. Поле отрицательный определитель содержит условия непринадлежности объектов данному классу. Например, для класса СОБАКА не_определение: (х ∈ ДОМАШНЕЕ ЖИВОТНОЕ) & мяукает (х). Это поле может, в частности, использоваться для вывода «от противного». Поле интерпретация вводит носитель (множество значений) описываемого класса. Поле оболочка является аналогом системы слотов во фрейме. Оболочка выделяет семантическую окрестность (коннетивное пространство) объекта и представляет синтаксические возможности для прямого доступа к своим элементам. Допускается 3 вида слотов: функциональные, предикатные и параметрические. Функциональный слот соответствует унарной функции, определённой на описываемом классе (например, стоимость вещи, название книги). Значением предикатного слота является в общем случае корректируемое множество объектов (сторона_треугольника (значение множества из 3-х отрезков)). В параметрических слотах один из аргументов принадлежит описываемому классу, второй выступает как параметр и выносится в заголовок поле оболочки, третий выступает в качестве значения слота. Примеры таких слотов – возраст, должность, вес…, где в роли параметра выступает время. Вообще говоря, с объектом может связываться несколько оболочек, соответствующих различным сферам знаний, выделяемым в предметной области. Функциональная схема оболочки. Задаёт условия однозначности определения объекта описываемого класса и (или) значений его слотов. Модель оболочки – это совокупность отношений и продукций, связывающих элементы оболочки. имя: интервал t оболочка: начало; ТОЧКА х конец; ТОЧКА у длина; ЧИСЛО у f-схема: x,y; x,g; y,g → t g=R(x,y) Данная ленема вводит класс объектов ИНТЕРВАЛ, а также 3 функции: начало, конец, длина, определённых на этом классе. В f-схеме показано, что значения любой пары слотов однозначно определяют интервал. Выполнение модели эквивалентно утверждению: … ∈ ИНТ (начало(х)<конец(у))(длина(t)=R(начало(t), (конец(t))). По изобразительным возможностям ленемы превосходят такие устоявшиеся традиционные средства представления знаний, как семантическая сеть, фрейм, система продукций, функциональная сеть.