Формальные логические модели

Традиционно в представлении знаний выделяют формальные логические модели, основанные на классическом исчислении предикатов 1^го порядка, когда предметная область или задача описывается в виде набора аксиом. Мы же опустим описание этих моделей по следующим причинам. Исчисление предикатов 1^го порядка в промышленных экспертных системах практически не используется. Эта логическая модель применима в основном в исследовательских «игрушечных» системах, так как предъявляет очень высокие требования и ограничения к предметной области.

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

Вывод на знаниях

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

I. Машина вывода

Машина вывода (интерпретатор правил) выполняет две функции:

1) просмотр существующих фактов из рабочей памяти (базы данных) и правил из базы знаний и добавление (по мере возможности) в рабочую память новых фактов;

2) определение порядка просмотра и применения правил.

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

В подавляющем большинстве систем, основанных на знаниях, механизм вывода представляет собой небольшую по объему программу и включает два компонента — один реализует собственно вывод, другой управляет этим процессом. Действие компонента вывода основано на применении правила, называемого modus ponens.

Правило modus ponens: если известно, что истинно утверждение А и существует правило
вида «ЕСЛИ А, ТО В», тогда утверждение В также истинно.

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

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

1) сопоставление — образец правила сопоставляется с имеющимися фактами.

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

3) срабатывание — если образец правила при сопоставлении совпал с какими-либо фактами из рабочей памяти, то правило срабатывает.

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

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

В одном цикле может сработать только одно правило. Если несколько правил успешно сопоставлены с фактами, то интерпретатор производит выбор по определенному критерию единственного правила, которое срабатывает в данном цикле. Цикл работы интерпретатора схематически представлен на рисунке:

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

II. Стратегии управления выводом

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

При разработке стратегии управления выводом важно определить два вопроса:

1) Какую точку в пространстве состояний принять в качестве исходной? От выбора этой точки зависит и метод осуществления поиска — в прямом или обратном направлении.

2) Какими методами можно повысить эффективность поиска решения? Эти методы определяются выбранной стратегией перебора — глубину, в ширину, по подзадачам или иначе.

III. Прямой и обратный вывод

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

Стратегии вывода представлены на рисунке:

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

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

IV. Методы поиска в глубину и ширину

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

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

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

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

Нечеткие знания

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

Кроме того, в задачах, решаемых интеллектуальными системами, часто приходится пользоваться неточными знаниями, которые не могут быть интерпретированы как полностью истинные или ложные (логические true/false или 0/1). Существуют знания, достоверность которых выражается некоторой промежуточной цифрой.

Как, не разрушая свойства размытости и неточности, представлять подобные знания формально? Для разрешения таких проблем в начале 70^х американский математик Лотфи Заде предложил формальный аппарат нечеткой (fuzzy) алгебры и нечеткой логики. Позднее это направление получило широкое распространение и положило начало одной из ветвей ИИ под названием — мягкие вычисления (soft computing).

Л. Заде ввел одно из главных понятий в нечеткой логике — понятие лингвистической переменной.

Лингвистическая переменная (ЛП) — это переменная, значение которой определяется
набором вербальных (то есть словесных) характеристик некоторого свойства.

Основы теории нечетких множеств

Значения лингвистической переменной (ЛП) определяются через так называемые нечеткие множества (НМ), которые в свою очередь определены на некотором базовом наборе значений или базовой числовой шкале, имеющей размерность. Каждое значение ЛП определяется как нечеткое множество.

Нечеткое множество определяется через некоторую базовую шкалу В и функцию принадлежности НМ - µ(х), хϵВ, принимающую значения на интервале [0...1] Таким образом, нечеткое множество В — это совокупность пар вида (х, µ(х)), где хϵВ. Часто встречается и такая запись:

где x_i – i ^тое значение базовой шкалы.

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

Пример: пусть перед нами стоит задача интерпретации значений ЛП «возраст», таких как «молодой» возраст, «преклонный» возраст или «переходный» возраст. Определим «возраст» как ЛП. Тогда «молодой», «преклонный», «переходный» будут значениями этой лингвистической переменной. Более полно, базовый набор значений ЛП «возраст» следующий:

В = {младенческий, детский, юный, молодой, зрелый, преклонный, старческий}.

Для ЛП «возраст» базовая шкала — это числовая шкала от 0 до 120, обозначающая количество прожитых лет, а функция принадлежности определяет, насколько мы уверенны в том, что данное количество лет можно отнести к данной категории возраста. На рисунке отражено, как одни и те же значения базовой шкалы могут участвовать в определении различных НМ:

Например, определить значение НМ «младенческий возраст» можно так:

График иллюстрирует оценку НМ неким усредненным экспертом, который ребенка до полугода с высокой степенью уверенности относит к младенцам (m = 1). Дети до четырех лет причисляются к младенцам тоже, но с меньшей степенью уверенности (0.5< m <0.9), а в десять лет ребенка называют так только в очень редких случаях. Таким образом, нечеткие множества позволяют при определении понятия учитывать субъективные мнения отдельных индивидуумов.

Операции с нечеткими знаниями

Для операций с нечеткими знаниями, выраженными при помощи лингвистических переменных, существует много различных способов. Эти способы являются в основном эвристиками. Мы не будем останавливаться на этом вопросе подробно, укажем лишь для примера определение нескольких операций. К примеру, операция «ИЛИ» часто задается так:

(так называемая логика Заде) или так:

(вероятностный подход).

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

Одним из первых применений теории НМ стало использование коэффициентов уверенности для вывода рекомендаций медицинской системы MYCIN. Этот метод использует несколько эвристических приемов. Он стал примером обработки нечетких знаний, повлиявших на последующие системы.
В настоящее время в большинство инструментальных средств разработки систем, основанных на знаниях, включены элементы работы с НМ, кроме того, разработаны специальные программные средства реализации так называемого нечеткого вывода, например «оболочка» FuzzyCLIPS.

Прикладные интеллектуальные системы

Центральная парадигма интеллектуальных технологий сегодня — это обработка знаний. Системы, ядром которых является база знаний или модель предметной области, описанная на языке сверхвысокого уровня, приближенном к естественному, называют интеллектуальными. Будем называть такой язык сверхвысокого уровня — языком представления знаний (ЯПЗ). Чаще всего интеллектуальные системы (ИС) применяются для решения сложных задач, где основная сложность решения связана с использованием слабо-формализованных знаний специалистов-практиков и где логическая (или смысловая) обработка информации превалирует над вычислительной.

Фактически сейчас прикладные интеллектуальные системы используются в десятках тысяч приложений. А годовой доход от продаж программных и аппаратных средств искусственного интеллекта еще в 1989 г. в США составлял 870 млн долларов, а в 1990 г. — 1,1 млрд долларов. В дальнейшем почти тридцатипроцентный прирост дохода сменился более плавным наращиванием темпов.

Наиболее распространенным видом ИС являются экспертные системы.

Экспертные системы (ЭС) — это наиболее распространенный класс ИС, ориентированный на тиражирование опыта высококвалифицированных специалистов в областях, где качество принятия решений традиционно зависит от уровня экспертизы (например, медицина, юриспруденция, геология, экономика, военное дело и др).

ЭС эффективны лишь в специфических «экспертных» областях, где важен эмпирический опыт специалистов.

Ежегодно крупные фирмы разрабатывают десятки ЭС типа «in-house» для внутреннего пользования. Эти системы интегрируют опыт специалистов компании по ключевым и стратегически важным технологиям. В начале 90^х гг. появилась новая наука — «менеджмент знаний» (knowledge management), ориентированная на методы обработки и управления корпоративными знаниями.

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

Приведем некоторые условия, которые могут свидетельствовать о необходимости разработки и внедрения экспертных систем:

· нехватка специалистов, затрачивающих значительное время для оказания помощи другим;

· выполнение небольшой задачи требует многочисленного коллектива специалистов, поскольку ни один из них не обладает достаточным знанием;

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

· большое расхождение между решениями самых хороших и самых плохих исполнителей;

· наличие конкурентов, имеющих преимущество в силу того, что они лучше справляются с поставленной задачей.

Подходящие задачи имеют следующие характеристики:

· являются узкоспециализированными;

· не зависят в значительной степени от общечеловеческих знаний или соображений здравого смысла;

· не являются для эксперта ни слишком легкими, ни слишком сложными.

Экспертные системы достаточно молоды — первые системы такого рода, MYCIN и DENDRAL, появились в США в середине 70^х годов. В настоящее время в мире насчитывается несколько тысяч промышленных ЭС, которые дают советы:

· при управлении сложными диспетчерскими пультами, например сети распределения электроэнергии, - Alarm Analyser;

· при постановке медицинских диагнозов — ARAMIS, NEUREX;

· при поиске неисправностей в электронных приборах, диагностика отказов контрольно-измерительного оборудования — Intelligence Ware, Plant Diagnostics, FOREST;

· по проектированию интегральных микросхем — DAA, NASL, QO;

· по управлению перевозками — AIRPLAN;

· по прогнозу военных действий — ANALYST, BATTLE;

· по формированию портфеля инвестиций, оценке финансовых рисков — RAD, налогообложению - RUNE и т. д.

Наиболее популярные приложения ИС отображены на рисунке:

Главное отличие ИС и ЭС от других программных средств — это наличие базы знаний (БЗ), в которой знания хранятся в форме, понятной специалистам предметной области, и могут быть изменены и дополнены также в понятной форме. Это и есть языки представления знаний — ЯПЗ.

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

· продукции (OPS5, ROSIE);

· семантические сети (SIMER+MIR, NET);

· фреймы (FRL);

· логическое программирование (ПРОЛОГ);

· объектно-ориентированные языки (SMALLTALK, CLOS).

Для перечисленных выше моделей существует соответствующая математическая нотация, разработаны системы программирования, реализующие эти ЯПЗ, и имеется большое количество реальных коммерческих ЭС.

Наибольшие трудности в разработке ЭС вызывает сегодня не процесс машинной реализации систем, а домашинный этап анализа знаний и проектирования базы знаний. Этим занимается специальная наука — инженерия знаний.

Разработка систем, основанных на знаниях

Введение в экспертные системы. Определение и структура.

Воспользуемся рабочим определением экспертной системы.

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

Обобщенная структура экспертной системы представлена на рисунке:

Следует учесть, что реальные ЭС могут иметь более сложную структуру, однако, блоки, изображенные на рисунке, непременно присутствуют в любой действительно экспертной системе.

В целом процесс функционирования ЭС можно представить следующим образом:

пользователь, желающий получить информацию, отправляет запрос к ЭС через пользовательский интерфейс

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

Пользователь — специалист предметной области, для которого предназначена система. Обычно его квалификация недостаточно высока, и поэтому он нуждается в помощи и поддержке своей деятельности со стороны ЭС.

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

Интерфейс пользователя — комплекс программ, реализующих диалог пользователя с ЭС как на стадии ввода информации, так и при получении результатов.

База знаний (БЗ) — ядро ЭС, совокупность знаний предметной области, записанная на машинный носитель в форме, понятной эксперту и пользователю (обычно на некотором языке, приближенном к естественному).

Решатель — программа, моделирующая ход рассуждений эксперта на основании знаний, имеющихся в БЗ.

Подсистема объяснений — программа, позволяющая пользователю получить ответы на вопросы: «Как была получена та или иная рекомендация?» и «Почему система приняла такое решение?» Ответ на вопрос «как?» — это трассировка всего процесса получения решения с указанием использованных фрагментов БЗ, то
есть всех шагов цепи умозаключений. Ответ на вопрос «почему?» — ссылка на умозаключение, непосредственно предшествовавшее полученному решению, то есть отход на один шаг назад. Развитые подсистемы объяснений поддерживают и другие типы вопросов.

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

Классификация систем, основанных на знаниях

Класс ЭС сегодня объединяет несколько тысяч различных программных комплексов, которые можно классифицировать по различным критериям. Полезными могут оказаться классификации, представленные на рисунке:

Классификация по решаемой задаче

· Интерпретация данных. Это одна из традиционных задач для экспертных систем. Под интерпретацией понимается процесс определения смысла данных, результаты которого должны быть согласованными и корректными. Обычно предусматривается многовариантный анализ данных.

Ø Обнаружение и идентификация различных типов океанских судов по результатам аэрокосмического сканирования – SIAP;

Ø определение основных свойств личности по результатам психодиагностического тестирования в системах АВАНТЕСТ и МИКРОЛЮШЕР.

· Диагностика. Под диагностикой понимается процесс соотнесения объекта с некоторым классом объектов и/или обнаружение неисправности в некоторой системе. Неисправность — это отклонение от нормы.

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

Ø Диагностика и терапия сужения коронарных сосудов — ANGY;

Ø диагностика ошибок в аппаратуре и математическом обеспечении ЭВМ — система CRIB.

· Мониторинг. Основная задача мониторинга — непрерывная интерпретация данных в реальном масштабе времени и сигнализация о выходе тех или иных параметров за допустимые пределы. Главные проблемы — «пропуск» тревожной ситуации и инверсная задача «ложного» срабатывания. Сложность этих проблем в размытости симптомов тревожных ситуаций и необходимость учета временного контекста.

Ø Контроль за работой электростанций СПРИНТ, помощь диспетчерам атомного реактора — REACTOR;

Ø контроль аварийных датчиков на химическом заводе — FALCON.

· Проектирование. Проектирование состоит в подготовке спецификаций на создание «объектов» с заранее определенными свойствами. Под спецификацией понимается весь набор необходимых документов — чертеж, пояснительная записка и т. д. Основные проблемы здесь — получение четкого структурного описания знаний об объекте и проблема «следа». Для организации эффективного проектирования и в еще большей степени перепроектирования необходимо формировать не только сами проектные решения, но и мотивы их принятия. Таким образом, в задачах проектирования тесно связываются два основных процесса, выполняемых в рамках соответствующей ЭС: процесс вывода решения и процесс объяснения.

Ø Проектирование конфигураций ЭВМ VAX – 11/780 в системе XCON, проектирование БИС – CADHELP;

Ø синтез электрически цепей – SYN.

· Прогнозирование. Прогнозирование позволяет предсказывать последствия некоторых событий или явлений на основании анализа имеющихся данных. Прогнозирующие системы логически выводят вероятные следствия из заданных ситуаций. В прогнозирующей системе обычно используется параметрическая динамическая модель, в которой значения параметров «подгоняются»
под заданную ситуацию. Выводимые из этой модели следствия составляют основу для прогнозов с вероятностными оценками.

Ø Предсказание погоды — система WILLARD;

Ø оценки будущего урожая – PLANT;

Ø прогнозы в экономике – ECON.

· Планирование. Под планированием понимается нахождение планов действий, относящихся к объектам, способным выполнять некоторые функции. В таких ЭС используются модели поведения реальных объектов с тем, чтобы логически вывести последствия планируемой деятельности.

Ø Планирование поведения робота – STRIPS;

Ø планирование промышленных заказов – ISIS;

Ø планирование эксперимента – MOLGEN.

· Обучение. Под обучением понимается использование компьютера для обучения какой-то дисциплине или предмету. Системы обучения диагностируют ошибки при изучении какой-либо дисциплины с помощью ЭВМ и подсказывают правильные решения. Они аккумулируют знания о гипотетическом «ученике» и его характерных ошибках, затем в работе они способны диагностировать слабости в познаниях обучаемых и находить соответствующие средства для их ликвидации. Кроме того, они планируют акт общения с учеником в зависимости от успехов ученика с целью передачи знаний.

Ø Обучение языку программирования ЛИСП в системе «Учитель ЛИСПа»;

Ø система PROUST — обучение языку Паскаль.

· Управление. Под управлением понимается функция организованной системы, поддерживающая определенный режим деятельности. Такого рода ЭС осуществляют управление поведением сложных систем в соответствии с заданными спецификациями.

Ø Помощь в управлении газовой котельной — GAS;

Ø управление системой календарного планирования Project Assistant.

· Поддержка принятия решений. Поддержка принятия решения — это совокупность процедур, обеспечивающая лицо, принимающее решения, необходимой информацией и рекомендациями, облегчающими процесс принятия решения. Эти ЭС помогают специалистам выбрать и/или сформировать нужную альтернативу среди множества выборов при принятии ответственных решений.

Ø Выбор стратегии выхода фирмы из кризисной ситуации — CRYSIS;

Ø помощь в выборе страховой компании или инвестора — CHOICE.

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

Дата добавления: 2014-01-07