Экспертные системы. Нейронные сети

Размещено на http://www.allbest.ru/

Опорный конспект лекций (Р2)

По дисциплине Интеллектуальные информационные системы

Тема 1. Представление и обработка нечетких знаний

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

Неопределенность (не-фактор) может иметь различную природу. Наиболее распространенный тип недостаточной определенности знаний обусловлен объективными причинами: действием случайных и неучтенных обстоятельств, неточностью измерительных приборов, ограниченными способностями органов чувств человека, отсутствием возможности получения необходимых свидетельств. В таких случаях люди в оценках и рассуждениях прибегают к использованию вероятностей, допусков и шансов (например шансов победить на выборах). Другой тип неопределенности обусловлен субъективными причинами: нечеткостью содержания используемых человеком понятий (например "толпа"), неоднозначностью смысла слов и высказываний (например "ключ" или знаменитое "казнить нельзя помиловать"). Неоднозначность смысла слов и высказываний часто удается устранить, приняв во внимание контекст, в котором они употребляются, но это тоже получается не всегда или не полностью.

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

Самым первым, пожалуй, можно считать использование эвристик в решении задач, в которых достаточно отдаленный прогноз развития событий невозможен (как, например, в шахматной игре). Но самое серьезное внимание этой проблеме стали уделять при создании экспертных систем, и первым здесь был применен вероятностный подход (PROSPECTOR), поскольку теория вероятностей и математическая статистика в тот период были уже достаточно развиты и весьма популярны. Однако проблемы, возникшие на этом пути, заставили обратиться к разработке особых подходов к учету неопределенности в знаниях непосредственно для экспертных систем (коэффициенты уверенности в системах MYCIN и EMYCIN). В дальнейшем исследования в этой области привели к разработке особой (нечеткой) логики, основы которой были заложены Лотфи Заде.

В решении рассматриваемой проблемы применительно к экспертным системам, построенным на основе правил (систем продукций), выделяются четыре основных вопроса:

а) как количественно выразить достоверность, надежность посылок?

б) как выразить степень поддержки заключения конкретной посылкой?

в) как учесть совместное влияние нескольких посылок на заключение?

г) как строить цепочки умозаключений в условиях неопределенности?

На языке продукций эти вопросы приобретают следующий смысл. Будем обозначать ct(А) степень уверенности в А (от англ. certainty - уверенность).

Тогда первый вопрос заключается в том, как количественно выразить степень уверенности ct(А) в истинности посылки (свидетельства) А.

Второй вопрос связан с тем, что истинность посылки А в продукции А>С может не всегда влечь за собой истинность заключения С (так высокая температура вызывает лишь определенное подозрение на заболевание гриппом, но не гарантирует правильности диагноза "грипп"). Степень поддержки заключения С посылкой А в продукции А>С обозначим через ct(А>С).

Третий вопрос обусловлен тем, что одно и то же заключение С может в различной степени поддерживаться несколькими посылками (например, заключение С может поддерживаться посылкой А посредством продукции А>С с уверенностью ct(А>С) и посылкой В посредством продукции В>С с уверенностью ct(В>С)). В этом случае возникает необходимость учета степени совместной поддержки заключения несколькими посылками.

Последний вопрос вызван необходимостью оценки степени достоверности вывода, полученного посредством цепочки умозаключений (например, вывода С, полученного из посылки А применением последовательности продукций А>В, В>С, обеспечивающих степени поддержки соответственно сt(А>В) и ct(В>С) ).

нечеткий логика нейрон архитектура

Тема 2. Экспертные системы. Архитектура экспертных систем. Характеристики ЭС. Функции ЭС. Средства построения ЭС. Назначение компонент ЭС

Успех первых экспертных систем стимулировал их разработку и применение в самых различных областях, что обязывает к более внимательному изучению их особенностей и возможностей.

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

1. ЭС ограничены определенной сферой экспертизы - узкой проблемной областью (ПО), что позволяет систематизировать и загрузить в компьютер знания, достаточные для качественного решения реальных задач.

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

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

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

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

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

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

Таблица

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

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

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

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

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

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

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

Чтобы понять суть принципиальных изменений, рассмотрим простой пример. Пусть требуется вычислить выражения и проверить их равенство:

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

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

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

Полностью оформленная экспертная система обязательно имеет следующие четыре основные компоненты (рис.1.1), присущие сегодня всем системам, использующим ИИ:

а) база знаний;

б) машина (механизм) вывода;

в) модуль извлечения (приобретения) знаний;

г) система объяснения (интерфейс).

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

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

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

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

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

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

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

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

По этим причинам наиболее удачные системы комбинируют эти два способа рассуждений. Так, К. Нейлор [8] описал метод, известный как подход с оценкой правил, который сочетает в себе достоинства обеих стратегий и смягчает их недостатки.

Но работает ли процедура вывода в прямом или в обратном направлении, ей приходится сталкиваться с ненадежными данными, фактами, правилами и заключениями, так как экспертные системы имеют дело не с идеализированными, а с реальными ситуациями. Для работы с неполными данными и ненадежными фактами, правилами и заключениями используются различные типы логик (вероятностная логика, многозначная логика, нечеткая логика, коэффициенты уверенности, если назвать только четыре из них). На практике были испробованы разные виды систем нечетких логических операций, но существенной разницы между ними не обнаружено. Объяснение этому, видимо, в том, что организация знаний играет более важную роль в рассуждениях, чем связанные со знаниями числовые значения. Кроме того, большинству баз знаний присуща избыточность, позволяющая экспертной системе прийти к правильному заключению несколькими различными путями. Числа, измеряющие степень доверия к получаемым в процессе поиска результатам, служат лишь ориентирами. По этой причине можно применять любой из удобных в каждом конкретном случае способ измерения ненадежности.

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

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

Программа EURISCO, созданная Д.Б. Ленатом на основе эволюционных алгоритмов Сэмюэля и Холланда, стала предвестником нового поколения обучающихся машин: Р.С. Михальский создал систему, которая обучалась классификации болезней зерновых культур; Дж. Квинлан разработал алгоритм обучения понятиям на основе анализа примеров, содержащихся в базе данных; Р. Форсайт написал программу BEAGLE (Biological Evolutionary Algorithm Generatial Expressions - биологический эволюционный алгоритм, порождающий логические выражения), в которой используется дарвиновская схема естественного отбора. Но особо примечательным в программе EURISCO Лената было то, что используемый ею язык описаний (средство хранения правил и понятий) оказался достаточно выразительным для представления зачаточной формы самосознания в виде "метаправил". Эта система тратит массу времени на самоанализ и управление своим поведением, запоминая обнаруженные правила и применяя их к себе.

Интерфейс. Четвертой важной компонентой экспертной системы являются средства, обеспечивающие возможность ее объяснения с человеком. Одним из самых замечательных свойств, присущих классическим экспертным системам, подобным системе MYCIN, является то внимание, которое было уделено в ней пользовательскому интерфейсу. В любой момент эту систему можно спросить, как (how) она пришла к такому заключению или почему (why) она задала пользователю такой вопрос? В системе, основанной на использовании правил, ответ обычно формируется путем повторного прослеживания тех шагов рассуждения, которые привели к данному вопросу или к данному заключению. Легкость, с которой это можно делать, является важным доводом в пользу систем, основанных на правилах.

Средства объяснений не следует считать специфической чертой, лишь экспертных систем. Доналд Мичи (1982) и другие aвторы указывали на обреченность систем, в которых не предусмотрено "когнитивное окно для человека", т.е. действия которых носят скрытый или непонятный человеку характер. Поэтому метод рассуждения, который не может быть объяснен человеку, неприемлем, даже если он работает лучше, чем специалист.

Общая типология систем ИИ

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

Многие авторы полагают, что термины экспертные системы и системы, основанные на знаниях, являются синонимами. Это не совсем верно. Они так считают потому, что знания (база знаний) и инструмент манипулирования знаниями (машина вывода) разделены в экспертной системе. Благодаря этому разделению база знаний создается независимо от машины вывода. Но в действительности любая компьютерная система основана на знаниях. Часть из них используют теоретические знания, другие - эмпирические знания, часть из них получают знания от человека (эксперта), другие приобретают знания сами путем изучения, обобщения и логического анализа фактов.

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

Таблица

Тип знания	Источник знания
	Человек	Познание
Теоретическое	Системы поддержки решений (DSS)	Системы искусственного интеллекта (AIS)
Эмпирическое	Экспертные системы (ES)	Нейронные сети (NN)

Классификация, приведенная в табл. 1.3, говорит о следующем:

? экспертные системы получают эмпирическое знание от эксперта в виде правил, основанных на его опыте;

? нейронные сети приобретают эмпирическое знание сами, путем тренировки с использованием больших объемов данных;

? системы поддержки решений основаны на теоретическом знании, которое включено исследователями и разработчиками в алгоритмы и программы, помогающие пользователю принимать эффективные решения;

? системы действительно интеллектуальные должны быть способны сами приобретать существующее и создавать новое теоретическое знание (благодаря способности создавать метаправила, этому требованию в некоторой степени удовлетворяет система EURISCO Лената).

Тема 3. Методы поиска решения в пространстве состояний. Классификация методов поиска решений. Простейшие методы поиска в одном пространстве состояний. Поиск методом полного перебора в глубину. Механизм возврата. Поиск методом полного перебора в ширину. Методы эвристического поиска в пространстве с большим числом состояний

Представление знаний в условиях неопределенности. Класссификация видов неопределенности. Формула Байеса и логический вывод на основе теории вероятности. Логический метод на основе коэфициентов неуверенности. Отношения правдоподобия и логический вывод на их основе . Форматы правил экспкртных систем с вероятностным выводом.

Дедуктивный вывод, основанный на нечетких знаниях. Нечеткие знания. Нечеткое множество. Основные операции над нечеткикми множествами. Нечеткое отношение. Лингвистическая переменная.Логический вывод на основе нечеткой логики. Нечеткие высказывания и операции над ними. Этапы нечетких логических выводов.

Методы поиска решений на основе знаний

Вывод заключений в логических моделях

В основу вывода заключений из имеющихся фактов или гипотез в логических моделях положены приемы, получившие название "доказательство теорем на основе резолюции". Метод резолюции позволяет справиться со многими проблемами, осложняющими выбор правил вывода. Чтобы воспользоваться приемами решения задач на основе резолюции (позже они будут рассмотрены более детально), предложения исчисления предикатов в несколько этапов приводят к упрощенному виду записи, называемому "клаузальной формой" (от англ. сlause - утверждение, предложение). Процесс упрощения включает освобождение выражения от кванторов и сведение его к списку предикатов, соединенных связкой ИЛИ.

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

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

;

;

;

.

Необходимы также следующие пары равносильных формул

;

.

Однако следует иметь в виду неравносильность следующих формул

;

.

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

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

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

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

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

Шаг 3. Переименование связных переменных с использованием символов переменных, еще не встречавшихся в выражении.

Шаг 4. Вынесение кванторов в префикс с использованием приведенных выше отношений равносильности формул. После выполнения этого шага формула приобретает префиксный вид.

Рассмотрим простой пример. Пусть дано утверждение "Каждый программист имеет свой пароль". Формула ИП, соответствующая этому предложению, имеет вид

,

где программист(х), пароль(у) - одноместные, а имеет(х,у) - двухместный атомарные предикаты.

Шаг 1 выполняется для исключения импликации с помощью отношения равносильности формул

В итоге получим выражение

.

Шаг 2 и Шаг 3 для данной формулы выполнять не требуется.

Шаг 4 применительно к полученной формуле связан с использованием отношения равносильности формул

на основании которого можно вынести ?у в префикс и получить предложение требуемого вида

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

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

.

Как уже говорилось, если все переменные в некотором выражении подвергнуты квантификации, то мы можем опустить кванторы общности. Однако в данном случае квантор общности относится только к х, но не к у (т.е. не все у удовлетворяют высказыванию). Эта проблема решается путем введения функциональной зависимости у от х вида у=g(x), называемой функцией Сколема. В нашем примере g(x) - это принцип присвоения пароля у каждому программисту х. Перепишем с учетом у=g(x) наше выражение

.

Теперь квантор общности распространяет свое действие на всё выражение и, следовательно, знак квантора общности можно опустить

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

Приоритетность действия кванторов, имеющихся в префиксной форме представления, определяется слева направо. Например, формулу

можно переписать в следующем виде

так как переменной, влияющей на связанную квантором ? переменную y, является только x. Если же исходная логическая формула имеет вид

то переменными, влияющими на переменную с квантором существования, являются x и z и тогда получаем

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

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

Клаузальная форма (форма предложений). На данной стадии полученное для рассматриваемого примера выражение

может быть представлено в общем виде как

Так как , то выражение на самом деле содержит два разных предложения со связкой "или":

,

.

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

,

.

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

В общем случае любое пропозициональное выражение можно привести к конъюнктивной нормальной форме (КНФ) многократным применением дистрибутивных правил. Чтобы затем преобразовать КНФ в клаузальную форму (в форму предложений), исключают символы &, заменяя конъюнкцию выражений на множество выражений . Результатом осуществления таких замен будет некоторое конечное множество выражений, каждое из которых является дизъюнкцией литералов (с отрицаниями или без них). Любая формула, состоящая только из дизъюнкций литералов, называется предложением. Множество предложений, полученных в результате исключения символа &, называется клаузальным множеством.

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

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

Решение задачи в исчислении предикатов равносильно доказательству (или опровержению) истинности формулы

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

Учитывая, что

исходную формулу задачи перепишем в виде

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

 = .

В клаузальной форме формулы

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

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

В основе метода резолюции лежит правило вывода "обобщенное modus ponens"

( ), ( ) + ( )

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

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

1) ,

2) ,

3) .

Далее предположим, что мы хотим доказать, что из истинности этих посылок следует истинность формулы С. Чтобы это сделать, дополним заданный набор предложений отрицанием С

1) ,

2) ,

3) ,

4) .

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

1) ,

2) ,

3) .

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

2) А,

3) .

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

Теперь рассмотрим конкретное содержательное рассуждение.

Предположим установленной истинность двух утверждений:

1) если экономика развивается, то курс валюты не падает,

2) курс валюты падает.

Рассмотрим далее, как из этих утверждений сделать вывод, что экономика не развивается. Для этого представим сначала данные нам утверждения в виде формул исчисления предикатов

1) ,

2) .

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

1)

2)

3)

Из полученных предложений видно, что использование в резолюции третьего и первого из них дает в итоге следующие два предложения

1) ,

2) .

Резолюция этих предложений приводит к пустой резольвенте, что свидетельствует об истинности заключения

Введение клаузальной формы выражений и применение метода резолюции предоставило ЭВМ простую процедуру вывода заключений. К сожалению, сам по себе метод резолюции не указывает, какие предложения следует выбирать для резолюции. В приведенных примерах, по существу, в этом не было необходимости, поскольку предложений было очень мало. Но даже при умеренном их количестве мы сталкиваемся с проблемой комбинаторного взрыва. Так, если мы будем проверять все возможные комбинации предложений, то для 10 предложений будет 50 комбинаций при первой попытке применения метода резолюции, а к десятой попытке их число возрастет до 1017 (для сравнения: в столетии около 1010 секунд). Таким образом, необходимость применения специальных способов предотвращения комбинаторного взрыва очевидна. В последнее время разработан достаточно эффективный метод решения этой проблемы, положенный в основу языка логического программирования Пролог.

Стратегии поиска решений для систем продукций.

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

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

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

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

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

а) затраты на применение правил (стоимость пути к цели);

б) затраты на управление (стоимость поиска правил, ведущих к цели).

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

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

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

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

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

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

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

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

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

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

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

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

Методы поиска решений в сложных пространствах.

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

Особенности ПО - это степень сложности объекта, его количественная сложность (размер, количество элементов) и его качественная сложность (сложность его организации и поведения - статический, динамический, развивающийся объект).

Особенности знаний о ПО - это полнота, определенность, точность знаний о ПО (полнота, определенность, точность данных об объекте, а также полнота и адекватность модели объекта).

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

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

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

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

1. Методы поиска в одном пространстве - применяются в случаях, когда ПО статична и невелика, возможно построение единой полной модели и получение полных и точных данных;

2. Методы поиска в иерархии пространств - применяются в случаях, когда ПО велика, но возможно представление знаний о ней в виде иерархии моделей первого типа и получение полных и точных данных;

3. Методы поиска в условиях неопределенности - применяются в случаях, когда ПО недостаточно изучена, имеющиеся данные неполны, ненадежны и недостаточно точны;

4. Методы поиска в динамических пространствах - применяются в случаях, когда ПО представляет собой эволюционирующий, изменяющийся во времени и в пространстве, развивающийся объект;

5. Методы поиска на основе нескольких моделей - применяются в случаях, когда ПО неоднородна, агрегирована из объектов различной природы, представление которых требует использования специфических моделей.

Методы поиска в одном пространстве.

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

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

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

Игру в шахматы можно теоретически представить тройкой (S0,F,ST), где S0 - начальное состояние (расположение шахматных фигур на доске); ST множество заключительных состояний (расположений фигур, означающих мат или ничью); F - множество допустимых по шахматным правилам ходов, реализация каждого из которых преобразует текущее состояние (расположение фигур) в новое. Заключительные состояния множества ST в шахматах явно перечислить невозможно, поэтому множество ST можно лишь описать через свойства заключительных состояний (расположений фигур, означающих мат или ничью). Задача состоит в том, чтобы найти последовательность ходов (операторов), преобразующих S0 в одно из состояний (каждый из игроков желает свое) множества ST. Описать процесс поиска можно с помощью графа, вершины которого соответствуют состояниям (шахматным позициям), а дуги - переходам из состояния в состояние под действием операторов (выполняемых ходов).

Аналогичным образом может быть описана игра в крестики-нолики. В этой игре позиция задается матрицей 3х3. Исходной позицией является пустая матрица. Два игрока (один из которых играет фишками Х, а другой О) поочередно помещают свои фишки в свободные клетки матрицы. Цель игрока - установить в линию 3 своих фишки. Побеждает тот, кто это сделает первым. В этой игре, в отличие от шахмат, есть лишь один тип оператора - помещение фишки в клетку матрицы.

Методы поиска без информации дают решение задачи, но в процессе поиска создается слишком много вариантов. Поскольку на практике всегда существуют ограничения на время и память для реализации процесса поиска, такие методы оказываются весьма неэффективными. Поэтому не только в шахматах, но и в такой простой игре, как крестики-нолики, возникает вопрос о выборе наилучшего в данной позиции хода. Действительно, простейшая стратегия - перебрать все варианты продолжения игры и выбрать ход, соответствующий выигрышному варианту. Однако подсчитано, что в шахматах просмотр позиции лишь на 5 ходов вперед уже дает 1015 вариантов, а в такой простой игре, как крестики-нолики существует 362880 (9!) позиций, число которых за счет учета симметрии можно сократить до 60000, но это тоже немало. Поэтому вместо полного перебора вариантов используют стратегии с применением "эвристических правил", позволяющих существенно сократить объем перебора за счет снижения гарантии успешности поиска.

...