МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Белорусский национальный технический университет Кафедра «Системы автоматизированного проектирова- ния» О.В. Герман Ю.О. Герман ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ Методическое пособие Минск БНТУ 2013 МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Белорусский национальный технический университет Кафедра «Системы автоматизированного проектирования» О.В. Герман Ю.О. Герман ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ Методическое пособие для студентов специализации 1-40 01 02-01 «Информационные системы и технологии в проектировании и производстве» Минск БНТУ 2013 УДК 004.8(075.8) ББК 32.813я7 Г38 Р е ц е н з е н т ы: канд. техн. наук, доцент кафедры ИСИТ БГТУ, Н.И. Гурин; д-р техн. наук, профессор кафедры ИТАС БГУИР, В.С. Муха Г38 Герман, О.В. Искусственный интеллект: методическое пособие для студентов специализации 1-40 01 02-01 «Информационные системы и техно- логии в проектировании и производстве» / О.В. Герман, Ю.О. Гер- ман. – Минск: БНТУ, 2013. – 127 с. ISBN 978-985-525-750-0. Настоящий материал предназначен для использования в качестве методического пособия при изучении дисциплины «Искусственный интеллект». Пособие содержит сведения, которые можно использовать в качестве дополнения и расширения лекци- онного курса, а также как реферативный источник. Представлены важнейшие темы современного теоретического курса по проблематике искусственного интеллекта с ориентацией на практическое применение. Содержит шестнадцать лекций и список литературы. Материал соответствует учебной программе. УДК 004.8(075.8) ББК 32.813я7 ISBN 978-985-525-750-0  Герман О.В., Герман Ю.О., 2013  Белорусский национальный технический университет, 2013 3 СОДЕРЖАНИЕ ЛЕКЦИЯ 1. Основные понятия искусственного интеллекта и интеллектуальных информационных систем. Прикладные системы искусственного интеллекта .................................................... 5 ЛЕКЦИЯ 2. Модели знаний: логические, семантические сети, фреймы, продукционные модели ........................................................ 11 ЛЕКЦИЯ 3. Логический язык. Правила построения логических формул. Понятие логического вывода ............................................... 21 ЛЕКЦИЯ 4. Язык Пролог как продукционная система знаний. Синтаксис языка Пролог. Примеры программ .................................. 28 ЛЕКЦИЯ 5. Основные механизмы языка Пролог ........................... 377 ЛЕКЦИЯ 6. Сложные структуры данных в Прологе: функторы и списки ............................................................................. 443 ЛЕКЦИЯ 7. Экспертные системы. Основные механизмы ................ 52 ЛЕКЦИЯ 8. Основы нечеткой логики ................................................ 63 ЛЕКЦИЯ 9. Нечеткая математика в принятии решений .................. 72 ЛЕКЦИЯ 10. Нечеткий Пролог ........................................................... 79 ЛЕКЦИЯ 11. Принятие решений в условиях риска и неопределенности .............................................................................. 84 ЛЕКЦИЯ 12. Генетические алгоритмы .............................................. 94 ЛЕКЦИЯ 13. Неклассические логики ................................................. 96 4 ЛЕКЦИЯ 14. Примеры экспертных систем (система экологического мониторинга) ........................................... 104 ЛЕКЦИЯ 15. Языки и грамматики .................................................... 112 ЛЕКЦИЯ 16. Информационно-диагностическая экспертная медицинская система “Нефрон”........................................................ 118 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ ......................... 126 5 ЛЕКЦИЯ 1 Основные понятия искусственного интеллекта и интеллектуальных информационных систем. Прикладные системы искусственного интеллекта Искусственный интеллект – это научное и прикладное направле- ние, объединяющее группу теорий и методологий, предназначен- ных для решения интеллектуальных задач. Понятие интеллекту- альной задачи можно считать первичным. Интеллектуальные задачи – это особый тип задач наряду с другими известными задачами. Они характеризуются своими специфическими чертами: □ задача является не полностью определенной; □ критерий, как правило, отсутствует; □ нет “хорошего” алгоритма решения, т.е. либо алгоритм явля- ется переборным, либо алгоритм не известен вовсе; □ задача характеризуется значительным пространством поиска; □ имеются эксперты по рассматриваемой проблематике. Следует заметить, что для отнесения задачи к категории “интел- лектуальных” не обязательно одновременное выполнение всех ука- занных условий. Частичная определенность задачи связана с недостаточными знаниями о предметной области. Для некоторых задач это свойство является определяющим. Сама задача построения логического вы- вода, а также многие оптимизационные задачи комбинаторной и дискретной математики обладают свойством частичной определен- ности, поскольку не для всякой формулы разрешим вопрос о ее ис- тинности. Для интеллектуальных задач, как правило, нет или не известно хо- роших алгоритмов решения. Например, не известно, как искать выиг- рышное продолжение в шахматной партии (кроме перебора вариантов, которых огромное множество), как разместить предметы различной формы в заданной прямоугольной или иной области, как искать цело- численные корни произвольного многочлена от нескольких перемен- ных и т.д. Решение логических задач и построение доказательств так- же относится к категории интеллектуальных задач. 6 Исходя из указанных особенностей можно считать интеллекту- альными многие задачи – постановка диагноза в медицине и техни- ке, прогнозирование исходов событий особенно при отсутствии статистических данных (например, угадывание исхода соревнова- ния), распознавание образов, речи и текста (особенно рукописного), синтез программ (задается что известно и что требуется определить; машина должна сама построить программу для решения), многие комбинаторные задачи на графах – например, отыскание мини- мального покрытия графа множеством вершин, отыскание гамиль- тонова цикла, задача о минимальной раскраске вершин графа и пр., игровые задачи типа шахмат и карт, планирование поведения робо- тов и т.д. Задачу P можно по форме представить таким образом [1, 2]: P =<Модель, Исходное_состояние, Критерий, Решение, Решающая процедура, Доказательство> Модель – это множество формул, описывающих связи в предмет- ной области задачи. В этом смысле модель можно трактовать как базу знаний. Исходное состояние – это то, что известно о значениях объек- тов (переменных) задачи. Критерий – это условие, которое должно быть обеспечено решением задачи. Решение – это набор значений не- известных переменных задачи. Доказательство – это математическое формальное обоснование правильности решения. Обычно в задаче требуется найти Решение и Решающую проце- дуру. Однако имеются задачи, требующие найти исходное состоя- ние, удовлетворяющее решению, и даже критерий. Весьма сложной категорией задач являются задачи, требующие найти решающую процедуру. Эта универсальная проблема, как доказали математики, не имеет алгоритмического решения. Иначе говоря, нет алгоритма для создания алгоритмов решения задач. Вместе с тем указанный факт вовсе не очевиден. Еще великие Лейбниц и Гильберт рассчи- тывали такой универсальный алгоритм построить. Важной особенностью любой технологии, связанной с решением интеллектуальных задач, является использование слабых методов, к которым относятся: 7  ограниченный и направленный перебор;  исключение и отсечение;  эвристики;  индукция. Основной вопрос применения слабых методов поиска решения состоит в том, чтобы на их основе построить точный или статистиче- ски точный метод. Этот момент является важнейшим. Проведем ана- логию со стрельбой по цели. Если вероятность поражения мишени не равна 1, то нужно стрелять много раз. Таким образом, слабый метод должен применяться многократно. При этом каждое очередное его применение должно осуществляться по новой траектории (нельзя направлять пули в оду и ту же точку). Траектория должна сходиться к цели. Для этого слабый метод должен сокращать пространство по- иска, отсекая целые области, где решения быть не может (принцип отсечений). Третье: нужен критерий завершения стрельбы. Как пра- вило, такой критерий имеет вероятностную природу. Таким образом, именно идея использования слабых методов может дать решение «проблемы размерности», присущей точным методам (см. характери- стику класса 1 задач ИИ, помещенную далее по тексту). В настоящее время сфер применения систем искусственного интеллекта достаточно много. Речь идет о разработке интеллекту- альных информационных систем в той или иной области. Прежде всего – это различные экспертные системы (ЭС) в медицине, проек- тировании, военном деле, геологоразведке, машиностроении, бан- ковской сфере и т.д. Например, задача выделения кредитов связана с риском не возврата или несвоевременного возврата и требует оценки надежности клиента по множеству критериев, каждый из которых лишь частично характеризует финансовую благонадеж- ность клиента. Аналогично, вложение денег в рискованные, но су- лящие большие доходы сферы. Например, хорошо известно, что много денег вложили в Интернет в связи с бумом интернет- технологий, однако значительная часть проектов оказалась убыточ- ной. В настоящее время весьма актуальна задача поиска ответов на смысловые вопросы (в том же Интернете). Смысловой вопрос тре- бует точечного (точного) ответа, а не указания множества ссылок на документы, как это делается в поисковиках типа Google. 8 В экспертных системах велика роль человека-решателя. В настоящее время это обусловлено его незаменимостью в части ге- нерации гипотез и обработки неформализованных знаний. Техноло- гия решения задач человеком отличается от машинной арифметики. Интуитивная составляющая механизма угадывания имеет тем большее значение, чем менее формализована задача. Таким образом, представление задачи играет важную роль в плане разделения ролей человека и машины в процессе решения. Общую парадигму ЭС с учетом сказанного можно представить сле- дующим образом: ЭС= База Знаний + Машина Вывода + Человек-решатель (1.1) Эту же парадигму можно применить и к произвольной интеллек- туальной информационной системе (ИИС), расширив ее с учетом функциональной специфики: ИИС= База Знаний (база данных) + Машина Вывода + Человек-решатель+Прикладное_обеспечение (1.2) Прикладное обеспечение может включать систему машинной графики, статистической обработки, формирования отчетности, САПР и пр. Для построения ИИС нужны: 1. математические методы для обработки знаний и модели для представления знаний; 2. программные средства для работы со знаниями. В настоящее время имеется достаточно широкий спектр матема- тических методов для работы со знаниями: методы распознавания образов, методы классической математической логики и неклассиче- ских логик, статистические методы, методы поиска решений на ос- нове эвристических механизмов на деревьях состояний, методы при- нятия решений, использование нейросетевых моделей и др. 9 Имеется спектр программных систем для работы со знаниями. Отметим здесь в первую очередь языки искусственного интеллекта типа Пролога и Лиспа, прикладные экспертные системы типа Project Expert, EMYCIN (известная медицинская экспертная система), GURU (оболочковая экспертная система широкого назначения), различные прикладные пакеты, например, для работы с нейросетями и т.п. Таким образом, констатируем следующее. Имеется набор специфических задач, которые можно назвать ин- теллектуальными. Для решения этих задач разработан широкий набор математических методов. Заметим, что одного какого-то ме- тода нет, поскольку интеллектуальные задачи сложные и требуют многостороннего рассмотрения под различными углами зрения. Вместе с тем можно выделить два главных направления в создании методов решения интеллектуальных задач. Первое. Имитация и подражание естественным механизмам моз- га и живой природы. Это направление включает нейросети, генети- ческие алгоритмы, механизмы эвристического поиска. Второе. Методы, группирующиеся вокруг математической логи- ки (как классической) так и неклассических. Математическая логика работает с объектами произвольной природы и отношениями (предикатами), описывающими связи между объектами. Следовательно, по своему духу математическая логика ориентирована на обработку и представление знаний в наибольшей степени, чем любая иная математическая дисциплина, например та же математическая статистика. Наконец, имеется набор программных средств и технологий для работы со знаниями, позволяющих практически воплотить идеи ис- кусственного интеллекта. Рассмотрим более детально связь методов решения задач в ИИС (ЭС с классами задач, на которые они ориентированы. Класс 1: малое пространство поиска с надежными знаниями и данными. Для этого класса задач основным методом решения явля- ется исчерпывающий перебор или метод отсечений неподходящих вариантов. При исчерпывающем поиске максимальный размер про- странства поиска зависит от времени, необходимого на просмотр 10 одного решения. Если на просмотр одного решения тратится 25 микросекунд, то на 10! решений потребуется 24 часа. Такой раз- мер пространства часто соответствует верхнему пределу для реаль- ных задач при полном перебое. Класс 2: малое пространство поиска с ненадежными знаниями. В этом случае используются методы последовательного анализа вариантов на диаграмме состояния задачи. Стержнем методов явля- ется теорема Байеса, другие вероятностные подходы, например, ме- тод Вальда. Класс 3: модель задачи изменяется со временем. Например, за- дачи планирования поведения роботов и предсказания требуют рас- суждений о всех возможных будущих мирах и событиях. Методы этой группы образуют так называемое ситуационное исчисление, временную логику и т.п. Класс 4: большое пространство состояний. Основным подходом к решению задач такого типа является механизм отсечений, использу- ющий порождение гипотез и их проверку. Ключевым моментом яв- ляется выполнение отсечений на наиболее ранних этапах построения решения, что сокращает перебор и обеспечивает повышение эффек- тивности поиска решения. Механизм отсечений реализован в методе ветвей и границ, принципе сжимающих отображений и др. Класс 5: задачи, требующие выдвижения гипотез и правдопо- добные рассуждения. Методы, используемые для решения этих за- дач, основаны на различных неклассических логиках: вероятност- ной, нечеткой, логике возможностей и др. 11 ЛЕКЦИЯ 2 Модели знаний: логические, семантические сети, фреймы, продукционные модели Имеется несколько хорошо разработанных моделей знаний, обладающих своими достоинствами и недостатками:  логические модели;  продукционные модели;  фреймы;  семантические сети. Каждая из этих моделей допускает также деление. Например, в классе логических моделей имеются модели на основе логики вы- сказываний и логики предикатов. Различают также модели на осно- ве четкой и нечеткой логики, двузначной и многозначной, противо- речивой и непротиворечивой логики и т.д. Логическая модель знаний Логические модели наиболее универсальны и формализованы. Для них имеется мощный математический аппарат. Логическая мо- дель представляет конечное или бесконечное множество логиче- ских формул, называемых предикатами. Для записи формул исполь- зуется язык, содержащий алфавит (набор символов) и множество правил образования правильно построенных формул. Символами логического языка являются:  константы (например, 0,1,2,… или ‘a’,’b’,’c’,…);  переменные: x,y,…,z;  функциональные символы: f,g,h, … (функциональные сим- волы называются также функторами);  символы предикатов (отношений) P,Q,R,…  кванторы всеобщности  и существования ;  логические операции (связки): & (“и”), v (“или”),  (“не”),  (“следует”),  (“эквивалентно”). & называют операцией конъ- юнкции, v – дизъюнкции,  – отрицания,  – импликацией и  – эквиваленцией. 12 Кроме символов языка, рассматриваются синтаксические правила записи предложений (формул) логического языка. Отправным элемен- том является простейшая формула – предикат (в логике предикатов) и булевская переменная (в логике высказываний). Предикат – это простейшая (атомарная) формула (с отрицанием или без него) вида P(…), где в скобках указываются аргументы формулы – переменные, константы или функторы, либо вовсе не указываются аргументы. Предикат принимает одно из двух воз- можных значений: истина или ложь. Аргументы предиката имеют произвольную природу. Каждый предикат есть формула логиче- ского языка. Пусть P, Q – любые две формулы. Тогда формулами также являются следующие выражения [3]: 1. P, Q; 2. P v Q; 3. P & Q; 4. P Q; (2.1) 5. PQ; 6. x P(x); 7. x P(x) В дальнейшем знак &, как правило, будем опускать, а знак  заменять на = или . Определение. 1. Дизъюнктом (в логике высказываний) называ- ется дизъюнкция литер (булевских переменных) с отрицанием или без, например, x v y v z. 2. Дизъюнктом в логике предикатов назы- вается дизъюнкция литералов (атомарных формул), взятых с отри- цанием или без него, например, P(a,z) v Q(z,f(x)). Определение. Конъюнктивной нормальной формой (КНФ) называется конъюнкция дизъюнктов. Определение. Выполняющей интерпретацией I для заданной КНФ называется множество значений переменных этой КНФ, при которых она истинна. Например, КНФ (x1 v x2 )(x1 v x2 )(x2 v x3)(x1 v x3) истинная в интерпретации I= либо в интерпретации . Число различных интерпретаций для дизъюнкта с n>0 перемен- ными равно 2n. Однако не все они являются в общем случае выпол- няющими интерпретациями. 13 Определение. Задача ВЫПОЛНИМОСТЬ (коротко – ВЫП) формулируется так: для данной КНФ установить, имеется ли для нее хотя бы одна выполняющая интерпретация. Определение. Формула B следует из формулы А, если в любой интерпретации, где А истинна, В также истинна. Пишем A  B в этом случае. Определение. Формула A тождественно истинна, если она ис- тинна в любой интерпретации. Тождественно истинная формула называется также тавтологией. Рассмотрим примеры построения логических моделей. Пример1. В хищении подозреваются A, B и C. Известно следующее. 1. Никто, кроме A,B,C в хищении не замешан. 2. A никогда не ходит на дело без соучастников. 3. С не виновен, если виновен B. Спрашивается, виновен ли A? Нужно составить систему логических уравнений, введя необходимые булевские переменные. Система переменных должна быть адекватна условиям задачи. Обозначим: xa – виновен A, xb – виновен B, xc – виновен C. Составим следующую базу знаний: 1. xa v xb v xc 2. xa  xb v xc 3. xb  xc Эти логические формулы полностью соответствуют условиям задачи.Относительно этой модели знаний поставлен вопрос: верно ли что xa =1? Ответ на этот вопрос должна дать машина вывода. Пример 2. Следует назначить по одной работе w1, w2, w3, w4 четырем исполнителям a,b,c,d, если известно, что a может выполнить либо работу w2, либо работу w3; b может выполнить 14 работу w1 или w2; c может выполнить w1 или w3 или w4; d может выполнить работу w2 или w4. Базу знаний для этой задачи можно записать с помощью формул логики предикатов таким образом: //группа условий, показывающих, какие работы могут быть назначены исполнителям P(a,X)  (X=w2) v (X=w3) P(b,Y)  (Y=w1) v (Y=w2) P(c,Z)  (Z=w1) v (Z=w3) v (Z=w4) P(d,R)  (R=w2) v (R=w4) //группа условий, показывающих, какие исполнители могут быть назначены на работы P(X1,w1)  (X1=b) v (X1=c) P(Y1,w2)  (Y1=a) v (Y1=b) v (Y1=d) P(Z1,w3)  (Z1=a) v (Z1=c) P(R1,w4)  (R1=c) v (R1=d) //группа условий, показывающих, что исполнителям не могут назначаться одинаковые работы P(a,X) & P(b,Y)  (X<>Y) P(a,X) & P(c,Y)  (X<>Y) P(a,X) & P(d,Y)  (X<>Y) P(b,X) & P(c,Y)  (X<>Y) P(b,X) & P(d,Y)  (X<>Y) P(c,X) & P(d,Y)  (X<>Y) Для этой системы знаний нужно доказать следующую формулу X Y Z R (P(a,X)&P(b,Y)&P(c,Z)&P(d,R)). Продукционная модель знаний Продукционная модель представляет собой вариант логической 15 модели, записанной с помощью продукционных формул (правил) вида F G, (2.2) где F,G – произвольные, вообще говоря логические формулы. Отмечается, что продукции “более близки” по форме “естественным” умозаключениям. На практике это чрезмерно общее условие можно ограничить, рассматривая формулы так называемого секвенционального вида f1& f2 & … & fz  g1 v g2 v … v gt, (2.3) где все используемые в представлении (2.3) формулы суть атомарные. Формулу (2.3) нетрудно привести к форме дизъюнкта: f1 vf2 &…v fz v g1 v g2 v…v gt, (2.4) так что никакой особенной выгоды представление (2.4) с этой точки зрения не дает. Система логического программирования Пролог использует еще более упрощенные секвенциальные формулы (так называемую нотацию Хорна): f1& f2 & … & fz  g1 (2.5) В (2.5) часть f1& f2 & … & fz называется телом продукции, а g1 - головой. Продукция без головы называется целью (goal). Каждая предикатная формула fi называется в этом случае подцелью. Перейти от общего представления (2.4) к представлению (2.5) просто, если принять во внимание следующую эквивалентность f1vf2 &…vfzvg1vg2v…vgt g2 & g3…&gt& f1&… &fzg1 (2.6) Рассмотрим представление знаний в системе программирования 16 Пролог. Пример1. Владимиру нравится все, что нравится Ире. нравится(владимир,X):- нравится(ира,X). Эта продукция соответствует формуле нравится(ира,X)  нравится(владимир,X). В Прологе тело продукции записывается после символов “:-“. Пример 2. Алексей мечтает о деньгах и карьере. Это предложение определяет два факта: мечтает(алексей, карьера). мечтает(алексей, деньги). Факты – это особый вид правил, которые не нужно доказывать. Такие правила, как можно видеть, представляют продукции без “головы”. При программировании на языке Пролог особую трудность вызывает использование рекурсивных продукций, в которых тело продукции содержит предикат, одновременно стоящий в голове продукции. Рассмотрим пример вычисления суммы чисел от 1 до заданного числа n. sum(0, X, X). sum(Z, S, X):- Z1=Z-1, S1=S+Z, sum(Z1,S1,X). Во-первых, заметим, что переменные в языке Пролог пишут с больших букв. Во- вторых, в данном примере назначение аргументов предиката sum таково: первый аргумент есть текущее число, второй аргумент есть промежуточная накапливаемая сумма, третий аргумент есть результирующая сумма. Продукция sum(0, X, X) является фактом, утверждающим, что если текущее число равно 0, то промежуточная накапливаемая сумма и результирующая 17 сумма совпадают. Вторая продукция как раз и дает пример рекурсии в Прологе. Эту продукцию следует читать таким образом: Если (Z1=Z-1) и (S1=S+Z) и (1+2+3+…+Z1=S1) то (1+2+3+…(Z-1)+Z=S). Запись рекурсивных определений подчиняется некоторым общим правилам. Рекурсия обязана в конце концов сводится к простому факту. Тело рекурсии должно связывать значения аргументов доказываемой формулы с изменяемыми значениями аргументов той же формулы. В рассмотренном примере все эти характеристики рекурсии налицо. Модель знаний на основе фреймов Фреймы предложены Марвином Минским. Минский также ввел терминологию и язык фреймов, включающий понятия “фрейма”, “слота”, “терминала”, “значения по умолчанию”. Фрейм имеет следующую структуру: {<имя-фрейма><имя слота1 ><значение слота1> ……… <имя слотаn ><значение слотаn>} В качестве примера рассмотрим фрейм <выбор скорости>: {<выбор скорости> <состояние дороги>:0.6 <состояние машины>:0.8 <состояние водителя>:0.5 } Наша гипотетическая экспертная система должна определять оптимальную скорость автомобиля (в пределах дозволенной) с учетом состояния дороги, машины и водителя. В данном примере уже указаны конкретные значения, так что необходима процедура оценки скорости по конкретным значениям слотов. Такая процедура называется демоном. Процедура-демон запускается автоматически, когда фрейм удовлетворяет некоторому образцу. 18 Наряду с процедурами-демонами имеются процедуры-слуги, которые используются для установления значений слотам. Так, для определения состояния дороги можно было использовать следующий фрейм: {<состояние дороги> <состояние покрытия>:0.5 <видимость>:1.0 } Такие же фреймы могли быть установлены для состояния машины и состояния водителя. Далее, например, для состояния покрытия можно использоваться фрейм: {<состояние покрытия> <материал покрытия>:0.4 <наличие влаги>:0.0 <изношенность дороги>:0.1 } Ясно, что организация экспертной оценки скорости требует создать все необходимые фреймы и разработать процедуру комплексной оценки. Хорошей основой для такой процедуры является метод Т.Саати. Модель знаний на основе фреймов является сравнительно простой и легко реализуемой. В ее основу можно положить обычную базу данных с визуальным интерфейсом. Семантические сети В реальном мире любую ситуацию можно охарактеризовать следующим образом. Во-первых, указать, какие объекты участвуют в ситуации. Во-вторых, определить, в какие отношения вступают объекты. Наконец, указать свойства объектов и свойства отношений. Таким образом, можно передать знания об очень широком классе ситуаций. Рассмотрим пример. Дано предложение: “Студент Максимов сдал экзамен по химии”. В этой ситуации выделяем объекты: Максимов и экзамен. Отношения между объектами передаются с помощью глаголов. В нашем случае 19 отношением является глагол сдать. Свойством Максимова является <студент>. Свойством экзамена является <по химии>. Свойством отношения <сдать> является время и характер действия (в нашем случае – это прошедшее время). Семантическая сеть – это граф, вершины которого соответствуют объектам и понятиям, а дуги, связывающие вершины, определяют отношения между ними. В нашем случае имеем следующий граф (рис. 2.1). Рис. 2.1. Пример семантической сети Объекты, отношения и свойства отображаются на семантической сети различными типами вершин. Ситуации могут образовывать целые сценарии. Например, рассмотрим второй фрагмент: “Экзамен по химии принимал профессор ZZZ”. Объединенная семантическая сеть представлена на рис. 2.2. Рис. 2.2. Объединенная семантическая сеть 20 В современном программировании получили достаточное распространение текстовые документы XML. Язык XML есть удобное средство для описания сценариев. Так, “содержимое” рис. 2.2 “ложится” в структуру документа XML следующим образом (русские слова заменены на английские) – рис. 2.3. Документы XML обрабатываются во многих современных системах программирования, особенно в контексте Интернет- программирования. Рис. 2.3. Представление семантической сети на языке XML Строки XML-документа представляют собой теги и их значения. Имена тегов мы связали с объектами (object), ситуациями (situation) и отношениями (relation). Свойства передаются через атрибуты тегов. Идея использования XML-документа может состоять в обработке запросов типа “Кто принимал экзамен по химии у Максимова?”. Для реализации этой идеи сам запрос можно перевести в XML-структуру: Maximov Exam ??? Accept 21 Вопрос представляет фрагмент знаний. Значение ??? подлежит определению. Из контекста вопроса ясно, что это значение участвует в отношении Accept (Принять). Вторым объектом данного отношения является ZZZ. Именно это значение и должно быть выдано, поскольку других объектов у отношения Accept нет. Ясно, что ссылка на объект Maximov является наводящей. При обработке запроса система может выйти на связанную ситуацию, определяемую глаголом “Pass” (Сдать), в которой Maximov – действующее лицо. Таким образом, задача системы – выяснить, в какой мере обе ситуации связаны, чтобы считать Maximov существенной характеристикой запроса. Кроме того, при выполнении семантических запросов важно то обстоятельство, что отношения могут включать более двух объектов и не ясно, о каком объекте в запросе идет речь. Эту ситуацию пытаются развязать, используя падежные отношения объектов, передаваемые словами кто, что, как, какой, чем и пр. ЛЕКЦИЯ 3 Логический язык. Правила построения логических формул. Понятие логического вывода Основной задачей любой логической системы является построе- ние логического вывода. Это касается как классической логики, так и неклассических логик. Для того чтобы строить выводы, нужно иметь правила вывода, а сами формулы должны быть приведены к удобному для вывода виду. В этом смысле наиболее удобно пред- ставление логических формул в виде дизъюнктов. Определение. 1.[4] Дизъюнктом (в логике высказываний) назы- вается дизъюнкция литер (булевских переменных) с отрицанием или без, например, x v y v z. 2. Дизъюнктом в логике предикатов называется дизъюнкция литералов (атомарных формул), взятых с отрицанием или без него, например, P(a,z) v Q(z,f(x)). Определение. Конъюнктивной нормальной формой (КНФ) называется конъюнкция дизъюнктов. Определение. Выполняющей интерпретацией I для заданной 22 КНФ называется множество значений переменных этой КНФ, при которых она истинна. Например, КНФ (x1 v x2 )(x1 v x2 )(x2 v x3)(x1 v x3) истинная в интерпретации I= либо в интерпретации . Определение. Задача ВЫПОЛНИМОСТЬ (коротко – ВЫП) формулируется так: для данной КНФ установить, имеется ли для нее хотя бы одна выполняющая интерпретация. Определение. Правилом вывода R называется такое соотноше- ние между формулами A1, A2, …, An и B, которое устанавливает ис- тинность формулы B всякий раз, когда выполняется заданное соот- ношение. Определение. Формула B выводима из формул A1, A2, …, An, если имеется конечная последовательность формул П, начинающа- яся с любой из формул Ai, такая, что каждая очередная формула этой последовательности либо выводима по некоторому правилу вывода из предшествующих членов (или их части), либо совпадает с какой-то из формул Ai. Теорема 3.1 (о полноте в узком смысле логики первого порядка и логики высказываний). Всякая тождественно истинная формула выводима. Задача логического вывода в логике высказываний может быть эффективно сведена к ВЫП. В самом деле, пусть даны дизъюнкты D1, D2, …, Dz. Спрашивается, выводим ли из них дизъюнкт R? (т.е. требуется установить тождественную истинность формулы D1& D2& … & Dz  R . Умножим эту последнюю формулу справа и сле- ва на R. Получим: D1& D2 & … & Dz &R False (3.1) Следовательно, если удастся показать выполнимость системы дизъюнктов D1& D2 & … & Dz &R, то получим опровержение ис- ходной формулы D1& D2 & … & Dz  R. Если докажем, что систе- ма не выполнима, то получим доказательство исходной формулы. Таким образом, задача логического вывода сводится к задаче ВЫП. 23 Приведем пример. Пусть даны формулы . , , 3 2 1 yxecf febf ybcaf    Покажем, что имеет место выводимость: xfffa  321 . Умножим правую и левую части на x :  xyxecfebybcaa )()()( □. Символ □ обозначает ложь (  xx □). Теперь нам надо в левой части раскрыть скобки. При этом может получиться одна из следу- ющих ситуаций: □  □ – выводимость имеет место; S  □ – выводимость не имеет места, если S □. При раскрытии скобок используем известные формулы: baba baba baba    , , (3.2) Две последние формулы называются формулами де Моргана. Итак, имеем  xyxecfebybcaa ))(()( □. Преобразованием получаем:   )())(( ))(()())(()( xyxecfeyabcxyxecfebyabc xyxecfebybcaaxyxecfebybcaa = □ . 24 Таким образом, получили ситуацию типа □  □, т.е. выводи- мость имеет место. С другой стороны, отношение yfffa  321 не выводимо (убедитесь самостоятельно). При приведении формул к виду дизъюнктов используют, кроме указанных выше (3.2) следующие формулы: . )()()( )( ,)( , ababa SacSSca aSSRaa aSaa babaa abaa       (3.3) Пример. Привести к виду дизъюнктов следующую формулу: )()( ebcbbac  Имеем: .)()()( ccacbcbcaccbbacebcbbac  Пояснение. )()( bacbacbac  Сложнее обстоит дело с приведением к виду дизъюнктов в логи- ке предикатов. Такое приведение выполняется в три этапа. На пер- вом этапе все кванторы выносят в начало формулы. Пример. )),(),(( zxzQyxPyx  . Вынесение кванторов в начало формулы дает такой результат: )),(),(()),(),(( zxQyxPzyxzxzQyxPyx  . Как видим, здесь выполняется прямолинейный перенос кванто- ров. Имеется, все же одна зацепка. Изменим формулу следующим образом: 25 )),(),(( yxyQyxPyx  . Мы видим, что имеется два квантора существования с одной и той же связываемой переменной y. В таких ситуациях требуется переход к новым обозначениям, от которых формула не теряет сво- ей тождественности. В нашем случае следует поступить так: )),(),(( )),(),(()),(),(( txQyxPtyx txtQyxPyxyxyQyxPyx   Никаких недоразумений при этом не возникает. На втором этапе отбрасывают кванторы. Здесь имеется специ- фика только в отношении кванторов существования. Смотрят, какие кванторы всеобщности предшествуют кванторам существования. Так, в формуле )),(),(( txQyxPtyx  квантору y предшествует квантор всеобщности x . Аналогич- но, квантору существования t предшествует квантор всеобщно- сти x . Берут самый внутренний квантор существования, и заме- няют переменную t на произвольную функцию от предшествующих переменных в кванторах всеобщности, а сам квантор существова- ния отбрасывают, например: )))(,(),(( xfxQyxPyx  . То же самое делают и с квантором существования y , но ис- пользуют уже другую функцию: )))(,())(,(( xfxQxhxPx  . Приведенная процедура избавления от кванторов существования называется сколемизацией (по фамилии норвежца Skolem). Теперь, когда кванторов существования не осталось, кванторы всеобщности просто отбрасывают: 26 ))(,())(,( xfxQxhxP  . Следующий пример применения сколемизации даем без коммен- тариев. ).),,(,())(,())),,(,())(,(( ))),,(,(),(()),,(),(( zzxfxQxhxPzzxfxQxhxPzx zzxfxQyxPzyxztxQyxPtzyx   Наконец, третья фаза состоит в получении собственно дизъюнк- тов на основании формул (3.2, 3.3). В нашем случае получаем един- ственный дизъюнкт: ).),,(,())(,()),,(,())(,( zzxfxQxhxPzzxfxQxhxP  Следует также указать, как строить отрицания от кванторов. Вот эти правила: )).(,,(),,(),,( ),,(),,( );()( yfycPzyxPzyxzyxzPyx zyxzPyxzyxzPyx xPxxxP    (3.4) Здесь внимательно рассмотрите второй случай. Отрицание по- следовательно «распространяется» по формуле. При этом очеред- ной квантор всеобщности заменяется на квантор существования и наоборот. В конце концов, отрицание «добирается» до самой фор- мулы. После этого мы проводим сколемизацию. И также обращаем внимание на то, что первому квантору существования х не пред- шествует ни один квантор всеобщности. В этом случае переменная x заменяется на произвольную константу c. В заключение этой лекции отметим в качестве универсального правила вывода в логике правило modus ponens (с латыни перево- дится как «правило исключения»). Пример этого правила: 27 Если A и из A следует B, То B. Пример. Если (металл(x), то проводит ток(x)) металл(свинец) Вывод: проводит ток(свинец). В формальном виде это пишут так: )( ____________________________ )()( )( plumbumctricityconductEle xctricityconductElexmetalx plumbummetal  Весьма сильным правилом вывода в логике является правило приведения к абсурду (reduction ad absurdum). Формальная запись этого правила такова:    ____________ Пример. Если стараться, добьешься результата. Результата не добился. . Вывод: не старался. 28 ЛЕКЦИЯ 4 Язык Пролог как продукционная система знаний. Синтаксис языка Пролог. Примеры программ Программа на языке Пролог состоит из секций: domains, predicates, clauses, goal. В секции domains содержатся объявления пользовательских типов данных. В секции predicates содержатся объявления предикатов. В секции clauses помещаются правила и, наконец, в секции goal записывается цель программы. Предикаты (предикатные формулы) являются основой концеп- ции Пролога. Выполнение программы на Прологе заключается в доказательстве целевого предиката. Этот предикат является обычно правилом. Чтобы доказать правило (любое, а не только цель), надо доказать все предикаты, составляющие его тело. Для этого проис- ходит согласование предиката с другим одноименным предикатом, т.е. сопоставление (унификация) соответствующих аргументов этих предикатов. Согласование выполняется успешно, если успешна унификация всех аргументов предикатов. При унификации аргу- ментов возможны следующие случаи [2]:  сопоставление двух констант заканчивается успешно, если они равны, и неудачно – в противном случае;  сопоставление константы и переменной (свободной, т.е. не имеющей значения) – заканчивается успешно, и переменная полу- чает значение константы (становится связанной);  сопоставление двух связанных переменных заканчивается успешно, если значения этих переменных равны, и неудачно, если не равны;  сопоставление двух переменных, одна из которых связана, а другая свободна заканчивается успешно, и свободная переменная принимает значение связанной;  сопоставление двух свободных переменных заканчивается успешно; Если впоследствии одна из переменных получает значе- ние, то и другой переменной присваивается то же значение. Если согласование предикатов закончилось неудачно, то делает- 29 ся попытка согласования данного предиката с другим одноименным клозом. Если таких клозов нет, то происходит возврат (бэктрекинг) к ближайшей “развилке”. Рассмотрим алгебраический пример. Пусть некто сообщает, что он задумал код (шифр) из пяти двухзначных (0 или 1) цифр. Обо- значим цифры Х1, Х2, Х3, Х4, Х5. При этом некто приводит следу- ющие отношения между цифрами: X1+Х2+Х3 >= 2, X2+X3+X4 <= 2, X2+X4+X5 <= 1, X3+X4+X5 >= 1, X1+X5 <= 1. Попробуем заставить Пролог найти эти цифры. Введем предикат znach(X), который устанавливает значение переменной X. Определение этого предиката таково: znach(B):-B=0; B=1. Предикат можно прочитать так: если В = 0 или В = 1, то значе- нием переменной B является соответственно “0” или “1” и другого быть не может. Интересно, как осмыслить предикат без аргумен- тов? Например, рассмотрим клоз: EQUATION:- znach(X1), znach(X2), X1+X2=2. Cистеме предлагается подобрать такие значения для перемен- ных Х1 и Х2, чтобы их сумма равнялась 2. Решение, разумеется, единственное. Но для чего нужен предикат EQUATION? Этот пре- 30 дикат “возглавляет целый клоз”, а потому его надо и рассматривать как структурную единицу программы. Все клозы должны быть яв- ным образом связаны. Для этого используется раздел программы, называемый GOAL (по-английски  цель). Чтобы понять сказанное, рассмотрим уже завершенный вариант нашей программы: predicates nondeterm equation nondeterm znach(integer) goal equation. clauses equation:- znach(X1), znach(X2), znach(X3), znach(X4), znach(X5), X2+X3+X4<=2, X2+X4+X5<=1, X3+X4+X5>=1, X1+X5<=1, write(“X1=”,X1,” X2=”,X2,” X3=”,X3,” X4=”,X4,” X5=”,X5). znach(B):-B=0; B=1. Итак, мы привели законченную программу. Программа на Про- логе состоит из секций PREDICATES, CLAUSES, GOAL (и др.). В секции PREDICATES объявляются предикаты и их аргументы (если есть). Стандартными типами аргументов предикатов являются integer, real, string, char, symbol, long (соответственно  целый, вещественный, строковый – берется в двойные кавычки, символь- ный – берется в одиночные кавычки; символьный также записыва- ется без кавычек малыми буквами, длинный целый – для чисел, превосходящих по абсолютной величине значение 216). В целях со- 31 пряжения с программами в Windows дополнительно к стандартным введены типы: byte (байтовый без знака), sbyte – (байтовый со зна- ком), short короткое целое, ushort  беззнаковое целое, dword – двойное слово, ulong – беззнаковое длинное целое. В секции GOAL удобнее всего объявить один единственный предикат, представля- ющий всю программу как таковую. (Впрочем, это не обязательно). В секции CLAUSES приводятся клозы, определяющие предикаты. Клозы для одного и того же предиката должны быть записаны вме- сте. Теперь рассмотрим важнейший механизм вывода, который неяв- но включался в процессе выполнения программы. Этот механизм можно назвать ветвление-возврат. Данное в программе определе- ние предиката znach можно переписать “более естественно”: znach(B):-B=0. znach(B):-B=1. (4.1) Здесь использованы два клоза вместо одного, хотя смысл дей- ствий при этом не изменился. Именно, система всегда обрабатыва- ет клозы последовательно, в порядке записи. При первом обраще- нии к предикату znach переменная В получает значение В=0. Если это значение не позволяет удовлетворить остальным предикатам, то выполняется повторное обращение к znach и переменная В получа- ет значение из второго клоза, т.е. В = 1. Теперь рассмотрим целиком процесс выполнения логической программы нашего примера. Пер- вым выполняется самый первый предикат раздела GOAL – equation. Система ищет определение этого предиката в разделе CLAUSES. Это определение имеется. Далее система выбирает первое условие из определения предиката equation – znach(X1). Система пытается доказать это условие и ищет определение предиката znach в разделе CLAUSES. Таким определением является (4.1). Система использует первое определение: znach(B):-B=0. Рассмотрим этот момент внимательнее. В определении (4.1) 32 имеется две альтернативы: для В=0 и В=1. Процесс выбора одной из альтернатив называется ветвлением. Всегда выбирается первая по порядку из числа неисследованных альтернатив. Итак, в момент выбора альтернативы имеется два предиката znach: первый из них – это предикат znach(X1), который система пытается доказать; и вто- рой  znach(B):-B=0, который система берет из определения. Си- стема сопоставляет эти два предиката и пытается согласовать их аргументы. Согласование аргументов называется унификацией. При унификации аргументы предикатов сопоставляются в порядке их расположения. У предиката znach только один аргумент. У дока- зываемого – это переменная Х1, у взятого из определения  это В (тоже переменная). Таким образом, выполняется привязка аргумен- та Х1 к аргументу В. Далее выбирается условие B = 0, доказывать которое не надо, т.к. это стандартная арифметическая операция. Переменная В получает значение В = 0. Поскольку Х1 привязана к В, то и Х1 получает значение Х1 = 0. На этом доказательство пре- диката znach(X1) успешно завершено. Процесс доказательства пе- реходит на предикат znach(X2), для которого действия выполняют- ся по аналогии, так что Х2 получает значение Х2 = 0. И далее, та- ким же путем, Х3 = 0, Х4 = 0, Х5 = 0. Теперь система успешно проходит проверку условий X2+X3+X4 <= 2, X2+X4+X5 <= 1, но проверка условия X3+X4+X5 >= 1 заканчивается неудачей. Теперь в действие вступает механизм воз- врата. Система возвращается в точку последнего ветвления. Это опять соответствует определению предиката znach, использованно- му при выборе значения Х5 = 0. На этот раз система воспользуется определением znach(B):- B=1. 33 Поэтому Х5=1 на этот раз и теперь уже все условия X2+X3+X4<=2, X2+X4+X5<=1, X3+X4+X5>=1, X1+X5<=1 будут успешно пройдены. В заключение система выполнит простой стандартный вывод на экран значений переменных, полученных на этом этапе: write(“X1=”, X1, ”X2=”, X2, ”X3=”, X3, ”X4=”, X4, ”X5=”, X5). Итак, мы рассмотрели простейшую структуру программы, ее со- ставные части и описали процесс выполнения логической програм- мы. При этом мы выяснили, в чем состоят логические механизмы ветвления, возврата и унификации. Прежде всего, следует помнить, что Пролог все время «занима- ется» доказательством предикатов. Предикаты (предикатные фор- мулы) являются основой концепции Пролога. Если мы пишем не- кую формулу, например, contain(X,Y), то вкладываем в нее опреде- ленный смысл, скажем, предложение X содержит строку Y, так что для X=”ядро заряжено положительно” и Y=”жено положительно” мы оцениваем формулу contain(X,Y) как истинную. Однако машине следует объяснить, что такое contain(X,Y), т.е. написать правило (или правила) для данного предиката. Эти правила помещают в раз- деле clauses. Для раскрытия формулы, вероятно, придется исполь- зовать новые формулы, но этот процесс должен быть, в конце кон- цов, сведен к стандартным формулам, которые машина «понимает». При этом сведении мы используем не только собственные (пользо- вательские) формулы, но и известные стандартные формулы. Например, пусть дана программа такого вида: goal 34 like(peter,X),write(X),readchar(_). clauses like(john, carrot). like(peter,Z):-like(john,Z). Эта программа требует найти предмет, который нравится peter. В качестве цели выбирается первый предикат секции goal  like(peter,X). Пролог начинает доказывать этот предикат. В резуль- тате такого доказательства, если оно пройдет успешно, переменная X получит значение. Так вот, значения в процессе доказательства переменные получают путем подстановки и унификации. Прежде всего, Пролог начнет рассматривать правила (clauses) для доказыва- емого предиката like(peter,X). Сначала он выберет первое правило like(john, carrot). Пролог сопоставит аргументы в обоих предикатах – в предикате, который доказывается, т.е. в like(peter,X), и в предикате из правила, т.е. like(john, carrot) (рис.4.1): Рис. 4.1. Сопоставление аргументов в предикатах like При сопоставлении аргументов выполняется унификация (по- русски – согласование) и присваивание значений переменным, если согласование закончилось успешно. В данном примере Пролог пы- тается согласовать константы peter и john и переменную X с кон- стантой carrot. С переменными дело обстоит весьма просто – они всегда согласовываются как с другими переменными, так и с кон- стантами. Поэтому Пролог примет X=carrot. С константами дело обстоит, напротив, достаточно ограничительно – просто константы 35 должны совпадать. Но у нас этого нет, ибо peter  john. Таким обра- зом, унификация сработала неудачно и Пролог вынужден отказать- ся использовать для доказательства правило like(john, carrot). Рабо- тает механизм перебора. Этот механизм заставит Пролог выбрать следующее по порядку правило для доказательства цели. Таким правилом является на этот раз like(peter,Z): like(john,Z). Пролог всегда заходит в правило с его головы, т.е. выберет пре- дикат like(peter,Z). Далее снова выполняется унификация в предика- тах (рис. 4.2). Рис. 4.2 На этот раз все благополучно и мы получим X=Z, причем Пролог с этой подстановкой зайдет в выбранное правило и начнет доказа- тельство предикатов из его тела, т.е. будет доказывать предикат like(john,Z). Этот новый предикат становится очередной целью. Заметим, что предикат like (…..) для своего доказательства вызывает снова пре- дикат like(…). Такая ситуация называется рекурсией. Это важное понятие. Насколько оно типично для Пролога? Скажем так, не в меньшей степени, чем для любого другого языка, даже в большей ввиду широкого применения в Прологе списков. Но пока что мы запомним, что X=Z и очередная цель есть like(john,Z). Если эту цель удастся доказать, то найдем Z, а потому (в силу произведенной вы- 36 ше подстановки) и X. Для доказательства цели Пролог снова ищет набор правил с именем like. Этих правил снова два и они просмат- риваются в порядке расположения (рис. 4.3): like(john, carrot). like(peter,Z):-like(john,Z). Рис. 4.3 Первые аргументы унифицировались (согласовались) и вторые тоже, т.е Z=carrot (переменная получила значение константы). До- казательство завершено, так как в данном правиле больше нечего доказывать. Пролог с успехом возвращается к предыдущей цели, т.е. к like(peter,X) и устанавливает X=Z=carrot. Тем самым цель like(peter,X) доказана. Далее в секции goal идет вывод на консоль write(X),readchar(_), это стандартные действия, которые не подлежат доказательству. Программа успешно завершается. 37 ЛЕКЦИЯ 5 Основные механизмы языка Пролог Предикаты (предикатные формулы) являются, как говорилось выше, основой концепции Пролога. Для обработки предикатов Пролог использует следующие основные механизмы:  подстановку и унификацию аргументов;  перебор правил;  отрицание и неудача;  откат (backtracking);  рекурсию. Переделаем программу из предыдущей лекции следующим об- разом: goal like(peter,x),write(x),readchar(_). clauses like(john, carrot). like(john, candies):-fail. like(peter,Z):- not(like(john,Z)). Как и ранее, программа требует найти то, что нравится peter. Од- нако теперь логика программы изменена – peter нравится то, что не нравится john. Это мы передали так like(peter,Z):- not(like(john,Z)). Отрицание передает предикат not. Однако, следует помнить, что данный предикат не может использоваться в голове, недопустимо, например, not(like(peter,Z)):- (like(john,Z)). 38 Есть и второе ограничение: в момент вызова предиката с отри- цанием аргументы предиката должны уже иметь значение. У нас же в программе этого нет. В like(peter,Z):- not(like(john,Z)) Z не имеет значения в момент вызова. Пролог выдаст сообщение об ошибке. Поэтому мы переделали программу иначе: predicates nondeterm like(symbol,symbol) nondeterm znach(symbol) goal like(peter,x),write(x),readchar(_). clauses like(john, carrot). like(john, candies):-fail. like(peter,Z):- znach(Z), not(like(john,Z)). znach(carrot). znach(candies). Теперь перед вызовом not(like(john,Z)) Z получит значение из вызова znach(Z). Ответ иллюстрирует рис. 5.1. Рис. 5.1. Результат работы программы 39 Но как же мы передали факт, что john не любит candies? Мы сде- лали это так like(john, candies):-fail. Fail является одной из важнейших команд Пролога. Эта команда фиксирует неудачу в доказательстве. В нашем случае это равно- сильно тому, что формула like(john, candies) ложна, а потому ее от- рицание истинно. Вообще говоря, Пролог начинает поиск с возвратом, когда дока- зательство какого-либо предиката завершается неудачей. В опреде- ленных ситуациях бывает необходимо инициализировать поиск с возвратом, чтобы найти другое решение. Для таких целей Пролог использует специальный предикат fail-неудача. Рассмотрим программу. predicates nondeterm father(symbol,symbol) nondeterm everybody clauses everybody:- father(X,Y), write(X,"is father"," ",Y), nl, readchar(_),fail. father (leonard,katherine). father (carl,nick). father (carl,marilyn). goal everybody. В этом примере мы ищем отца Y. Для того, чтобы вывести все решения, мы в теле предиката everybody поставили команду fail. 40 После того, как на экран выводятся значения переменных X=leonard и Y=katherine, возникает состояние искусственной неудачи (fail). Происходит возврат к ближайшей развилке father(X,Y), т.к. этот предикат еще не сопоставлялся с двумя оставшимися фактами. При этом переменные X, Y становятся свободными. Теперь предикат father(X,Y) сопоставляется с фактом father(carl,nick). Переменные X, Y получают соответствующие значения и далее вывод осуществля- ется по аналогии. Отсечение Пролог использует отсечение для прерывания поиска с возвра- том. Отсечение обозначается !. Пройдя через отсечение, уже невоз- можно произвести откат к предикатам, расположенным в обрабаты- ваемом предложении перед отсечением, а также невозможно воз- вратиться к другим предложениям, определяющим данный предикат. Например, есть правило: r1:- a,b, !, c. Если с завершится неудачей, то Пролог не сможет произвести откат (поиск с возвратом) через отсечение и найти альтернативные решения для а и b. Он также не сможет обратиться к другому пред- ложению, определяющему предикат r1. Пример. predicates nondeterm buy(symbol,symbol) nondeterm car(symbol,symbol,integer) nondeterm colors(symbol,symbol) clauses buy(Model,Color):- car(Model,Color,Price), colors(Color,good), !, 41 Price<25000, write(Model), readchar(_). car(maserati,green,25000). car(corvette,black,24000). car(corvette,red,26000). colors(red,good). colors(black,mean). colors(green,bad). goal buy(corvette,Y). В данном примере поставлена цель: найти корвет приятного цве- та и подходящий по стоимости. Здесь, получив целевое утвержде- ние buy(corvette,Y), программа отработает следующие шаги: 1. Пролог обращается к car. Выполняет проверку для первой машины. Она – maserati, следовательно, проверка завершается не- удачей; 2. затем проверяет следующее предложение car и находит соот- ветствие, связывая переменную Color со значением black; 3. переходит к следующему предикату и проверяет, имеет ли вы- бранная машина приятный цвет. Черный цвет не является прият- ным, т.о. проверка завершается неудачно; 4. выполняется поиск с возвратом к car и снова ищет Корвет; 5. находит соответствие и снова проверяет цвет. На этот раз цвет оказался нужным, затем переходим к отсечению, которое “замора- живает” все переменные, ранее связанные в этом предложении; 6. переходим к сравнению Price<25000; 7. проверка завершается неудачно, и Пролог пытается совер- шить перебор с возвратом для того чтобы найти другую машину. Однако отсечение не даст это сделать, и наше целевое утверждение завершается неудачно. 42 Рекурсия Итак, рекурсия - это вызов предиката из тела самого предиката. Рекурсия обычно применяется при обработке списков, при вычис- лениях (например, вычислениях сумм, факториала) и в ряде других случаев. Приведем типичный пример программы с использованием ре- курсии: вычисление факториала. predicates nondeterm fact(long,long,long) clauses fact(1,N,M):-M=N. fact(Z,N,M):- N1=Z*N, Z1=Z-1, fact(Z1,N1,M). goal fact(5,1,M),write("factorial=",M),readchar(_). Здесь N – промежуточное значение; M – окончательное значе- ние; Z – исходное число. Пример факториала с двумя аргументами. predicates nondeterm fact(long,long) clauses fact(1,1). fact(N,M):- N1=N-1, fact(N1,M1), M=M1*N. goal fact(5,M),write("factorial=",M),readchar(_). 43 ЛЕКЦИЯ 6 Сложные структуры данных в Прологе: функторы и списки Список представляет собой сложную структуру данных в Проло- ге [2]. Как ранее отмечалось, сложные типы данных (например, списки) необходимо объявлять в секции domains. Список - это последова- тельность из произвольного числа элементов некоторого типа. Ограничений на длину списка нет. Объявление списка осуществля- ется следующим образом: domains списочный_тип=тип*, где “тип” – тип элементов списка это может быть как стандартный тип, так и нестандартный, т.е. заданный пользователем и объявлен- ный в разделе domains ранее. Ниже приведен пример объявления предиката, аргументом кото- рого является список целых чисел: domains list=integer* predicates nondeterm numbers(list) Кроме того, аргументами списка могут быть не только целые числа и строки, но также и сами списки. Например, domains list=integer* list2=string* list3=list* L=[1,2,3,4] L=[“vova”,”petya”] L=[ [1,2],[4],[] ] 44 Ввод списков с клавиатуры выполняется стандартным предика- том readterm (<тип>,<имя_переменной>), где <тип> – списочный тип, который предварительно должен быть объявлен в разделе domains. Например, для ввода списка list нужно использовать пре- дикат readterm(list,L) [2]. При вводе списка на консоль необходимо набирать его точно так же, как он записывается, т.е. в квадратных скобках, через запя- тую и без пробелов. Вывод списка на экран выполняется предикатом write(L), где L-список. Для удобства обработки списков введены понятия головы и хво- ста списка. Голова – это первый элемент списка, хвост – вся осталь- ная часть списка. Т.о. хвост списка сам является списком. Для пред- ставления списка в виде головы и хвоста используется следующая запись: [H|T], где H – голова списка (первый элемент), T – хвост списка (т.е. также список). Запись вида L=[X] обозначает список из одного элемента, причем голова этого списка – X, а хвост – []. Кроме того, пустой список нельзя разделить на голову и хвост. Прежде чем рассматривать пример программы для обработки списков, приведем некоторые общие рекомендации:  в операциях со списками практически всегда используется ре- курсия. Рекурсия – это вызов предиката из самого себя;  обычно предикаты для реализации работы со списками имеют несколько клозов. Первый из них относится к простейшему случаю (например, к операции с пустым списком, со списком из одного элемента, с головой списка). Последующие клозы относятся к более общим случаям и имеют следующее назначение: если список не со- ответствует простейшему случаю, рассмотренному в первом клозе, то его следует уменьшить на один элемент (обычно – исключить голову) и применить рекурсию к укороченному списку;  предикаты, предназначенные для получения одного списка из другого, всегда имеют не менее двух аргументов: один – исходный список, другой – список-результат. К числу основных операций со списками можно отнести следую- щие: проверка принадлежности к списку, добавление элемента в 45 писок, удаление элемента из списка, вывод суммы элементов списка и т.д. На основе этих операций реализуются другие, более сложные операции со списками. Пример 1. Подсчет суммы элементов списка. Начнем с примера, а затем дадим его объяснение. goal sum([1,2,5,-7,4],0,X), write(X),readchar(_). clauses sum([], Z, Y): Y=Z. sum([H|T], W, Y): W1=W+H, sum(T, W1, Y). Списки в языке Пролог являются нестандартными типами дан- ных, т.е. должны быть объявлены явно. Кроме того, в программе они помещаются в квадратные скобки. Наша задача - найти сумму элементов списка ([1,2,5,-7,4]. В такого рода задачах важно правильно «распределить» пере- менные. Так, одну переменную мы установили для результирующей суммы. В предикате sum([1,2,5,-7,4],0,X) – это переменная X. Вто- рая переменная (точнее сказать – аргумент) – это текущая накапли- ваемая сумма. Ей присвоено начальное значение 0. Наша идея про- ста – последовательно «отрывать» первый элемент списка и добав- лять его к текущей накапливаемой сумме. Пролог позволяет представить список в виде [H | T]. Здесь вертикальная черта отделя- ет первый элемент списка (голову списка) от остальных элементов (хвоста списка). Таким образом, нетрудно догадаться о смысле второго правила sum([H|T], W, Y): W1=W+H, sum(T, W1, Y). 46 Голова H добавляется к текущей накапливаемой сумме W, полу- чаем новую накапливаемую сумму W1 и рекурсивно вызываем пре- дикат sum, но уже с новыми аргументами. Заметим при этом, что результирующая сумма не меняется и представлена одной и той же переменной Y. Кроме того, в Прологе нельзя писать W=W+H, т.к. запрещено изменять значение одной и той же переменной в правиле! Должен быть ясен также и смысл первого правила sum([], Z, Y): Y=Z. Если список опустеет, то результирующая сумма приравнивается к текущей накапливаемой сумме. Этот факт можно было передать и иначе sum([], Z, Z). Для объявления списочного типа в программе используется сек- ция domains domains list=integer* predicates nondeterm sum(list,integer,integer) Здесь объявлен списочный тип list. Указано, что list есть список целых чисел list=integer* Именно звездочка и определяет списочный тип. Сумму элементов списка можно найти и через два аргумента: 47 domains list=integer* predicates nondeterm sum(list,integer) goal sum([1,2,5,-7,4],X), write(X),readchar(_). clauses sum([],0). sum([H|T], S):- sum(T, S1), S=S1+H. Пример 2. Вычисление минимального элемента списка. domains list=integer* predicates nondeterm min(list,integer,integer) goal min([3,5,-2,18],3,X), write(X),readchar(_). clauses min([],S,S). min([H|T],S ,X):- H>=S, min(T,S,X). min([H|T],S,X):- H1 переменными. Если минимальное покрытие min матрицы B содержит более n строк, то данная система дизъюнктов не выполнима; в противном случае – выполнима. Принцип групповых резолюций (п.г.р.) позволяет порождать новые – групповые резольвенты, используя любой эвристический метод для отыскания минимального или близкого к нему покрытия. Гарантируется, что рано или поздно будет порожден полностью нулевой столбец. В этом случае алгоритм прекращает работу. Наилучшее из найденных к этому моменту покрытий и является минимальным. В качестве эвристического алгоритма можно использовать сле- дующий. На каждой итерации p отыскиваем столбец (из числа не 59 вычеркнутых) с минимальным числом единиц. Обозначим этот столбец rp и назовем его синдромным. Найдем невычеркнутую строку ip, покрывающую rp и такую, что из всех других строк, по- крывающих rp, она содержит наибольшее число единиц. Включим ip в отыскиваемое на данной итерации p покрытие. Вычеркнем все строки, содержащие в столбце rp “1”, а также все столбцы, покры- ваемые строкой ip. Итерация ведется до тех пор, пока имеется хотя бы один невычеркнутый столбец и одна невычеркнутая строка. Так, выберем столбец D1 и строку x2, которую включим в отыскиваемое покрытие на итерации 1. Вычеркнем строки и столб- цы согласно описанному правилу (рис. 7.5). D2 D3 D5 D7 x1 1 x2 1 1 x3 1 1 1 x1 1 1 x3 1 Рис. 7.5 Выполним теперь вторую итерацию. Выберем столбец D2 и строку x3. Вычеркнем строки и столбцы согласно описанному правилу (рис. 7.6). Остается единственный невычеркнутый столбец, так что включим, например, строку x1 в предполагаемое минимальное покрытие. Таким образом, итерация завершается отысканием покрытия 1 = {x2, x3, x1}. Согласно представленному выше утверждению, данное покрытие минимально и дает выполняющую интерпретацию для исходной системы дизъюнктов. 60 D5 x1 1 x2 x3 x1 1 x3 Рис. 7.6 Описанный эвристический алгоритм не всегда отыскивает минимальное покрытие и необходимо выполнять этап построения групповой резольвенты. Это делается так. Берем текущее найденное покрытие и оставляем в нем любые n+1 строку. Формируем матрицу R из синдромных столбцов, найденных для этих строк. Формируем столбец-резольвенту, исходя из следующего: он содержит “1” в тех и только тех строках, которые в R имеют две или более единиц; в противном случае строка содержит “0”. Этот столбец присоединяется к матрице B и итерации возобновляются снова (все вычеркнутые строки и столбцы восстанавливаем на новой итерации). Так, найденное покрытие 1 = {x2, x3, x1} содержит ровно n = 3 строки. Тем не менее, построим для него матрицу R (рис. 7.7) на синдромных столбцах D1, D2, D5. D1 D2 D5 Резольвента x1 1 1 1 x2 1 x3 1 x1 1 x2 1 x3 Рис. 7.7 В данном случае групповая резольвента содержит единственную “1” в строке x1. Поэтому при возобновлении итераций (если бы это было необходимо), следовало добавить данную резольвенту к матрице B. 61 Недостатком описанного метода является рост размеров матрицы при присоединении новых резольвент. Тем не менее, метод групповых резольвент справляется достаточно быстро с задачами, содержащими сотни логических переменных и дизъюнктов. Его эффективность падает при разреженных матрицах покрытий (с плотностью единиц порядка 0.05–0.1). В качестве еще одного механизма рассмотрим классифицирую- щее дерево. Построение классифицирующего дерева Рассмотрим задачу поиска документов по ключевым словам. Эту задачу можно рассматривать как экспертную задачу. Обычно при поиске документов пользователь указывает список ключевых слов для поиска. Такой поиск полностью инициируется самим пользователем. Имеется и другая возможность. Система мо- жет путем наводящего опросника выяснить, какой документ требу- ется пользователю. Преимуществом такого способа является более точная «наводка». Рассмотрим следующий список документов с указанными для них множествами ключевых слов (рис. 7.8). Документ Ключевые слова Д1 знание, экспертная система, решение задач Д2 знание, диагностика, алгоритм, реше- ние задач, классификация Д3 база данных, язык программирования, запрос Д4 алгоритм, сложность,решение задач Д5 алгоритм, классификация Рис. 7.8. Пример списка документов Чтобы построить минимальное по размеру классифицирующее дерево, составим матрицу различий, столбцами которой являются 62 пары документов, а строками – ключевые слова. В строке  и столбце  пишем “1”, если и только если это ключевое слово раз- личает данные документы, т.е. в одном из них оно присутствует в качестве ключевого слова, а в другом нет. Например, ключевое сло- во «алгоритм» различает документы Д1 и Д4 (у Д1 нет, а у Д4 есть ключевое слово «алгоритм»). Мы приняли для слов сокращения по первым буквам, например, знание – зн, экспертная система – эс и т.д. Матрица различий имеет следующий вид (рис. 7.9). Д1, Д2 Д1, Д3 Д1, Д4 Д1, Д5 Д2, Д3 Д2, Д4 Д2, Д5 Д3, Д4 Д3, Д5 Д4, Д5 зн 1 1 1 1 1 1 эс 1 1 1 1 рз 1 1 1 1 1 1 диа 1 1 1 1 алг 1 1 1 1 1 1 бд 1 1 1 1 яп 1 1 1 1 запр 1 1 1 1 слож 1 1 1 1 класс 1 1 1 1 1 1 Рис. 7.9. Матрица различий Определим покрытие матрицы как множество строк, таких, что для любого столбца хотя бы одна из строк покрытия содержит в нем “1”. Покрытие минимально, если оно содержит минимальное коли- чество строк. Для отыскания минимального покрытия как раз и можно использовать описанный выше метод групповых резолюций. Одно из минимальных покрытий нашей матрицы имеет вид:  = {зн, алг, класс}. Именно с помощью этих трех слов (знание, ал- горитм, классификация) можно однозначно определить документ. Пример соответствующего опросника: 63 – говорится ли в документе про «алгоритм» (Ответ – Нет) – говорится ли в документе про «знание» (Ответ – ДА) Система сообщает – Это Д1. Этот опрос можно представить в виде дерева (рис. 7.10). говорится ли в документе про «алгоритм» ДА НЕТ говорится ли в документе про «знание» ………. ДА НЕТ ЭТО Д1 …….. Рис. 7.10. Пример опросника Разумеется, при большом (сотни и тысячи) числе документов и числе ключевых слов порядка нескольких сотен построение клас- сифицирующего дерева может быть сопряжено со значительными техническими трудностями, так что речь следует вести не о дереве минимального размера, а о близком к минимальному по размерам дереву. ЛЕКЦИЯ 8 Основы нечеткой логики Основы нечеткой логики предложены Л. Заде в 60-х годах. Рас- смотрим, например, следующую логическую формулу 64 21 xx  (8.1) Эта формула при одних значениях переменных может быть ис- тинной, а при других – ложной. Если о значениях переменных ни- чего не известно, то в предположении их равновероятности, можно оценить вероятность формулы быть истинной, как 0.75 (три случая из четырех). С другой стороны, если переменные не равновероятны, то вероятность этой же формулы быть истинной уже может быть не 0.75, а например, 0.9 или 0.6. На практике мы как раз не всегда зна- ем вероятности переменных быть истинными, а используем вместо этого субъективные оценки. Такие субъективные оценки выража- ются словами типа «достаточно правдоподобно», «трудно отдать предпочтение чему-либо», «мало вероятно» и т.п. Подобные оценки называются лингвистическими. Они не являются численными. Однако их следует перевести к числовому виду. Для этого исполь- зуют нечеткую функцию меры. Нечеткую функцию меры обозна- чают, как правило, символом . Она сопоставляет лингвистическим значениям числовые. Такое сопоставление субъективно. Оно не ос- новано на опытных статистических данных, а характеризует пред- ставление эксперта. Между прочим, такие субъективные оценки называются также субъективными вероятностями. Если, напри- мер, мы оцениваем переменную 1x как истинную с вероятностью 0.8, а переменную 2x как истинную с вероятностью 0.4, то какова субъективная вероятность формулы (8.1)? Ведь при этом мы уже не опираемся на какой бы то ни было статистический материал. На помощь нам может прийти диаграмма Венна для решения этой про- блемы. Условно можно разделить предметы на четыре части: A, B, C, D. Часть А составят предметы, у которых нет ни свойства 1x ни свойства 2x . Для них формула (8.1) ложна. Часть B составят пред- меты, у которых нет свойства 1x но есть свойство 2x . Часть С со- ставят предметы, у которых есть свойство 1x но нет свойства 2x . Наконец, часть D составят предметы, обладающие обоими свой- ствами. Обозначим через dba ,,, mmmт c – числа предметов в каж- дой части соответственно. Тогда свойством (8.1) обладает число 65 предметов, равное dcb mmm  . Это простое соображение дает нам первую отправную позицию для исчисления нечетких оценок истинности формул типа (8.1): )&()()()( 212121 xxxxxx  . (8.2) Считая переменные 1x , 2x независимыми, получаем: )()()()()( 212121 xxxxxx  (8.3) Формула (8.3) называется формулой Шортлифа [5]. Она легко обобщается на случай трех и более переменных. Следующая фор- мула также постулируется без доказательств: )(1)( 11 xx  (8.4) Заметим, что Л.Заде использовал не формулу (8.3), а формулу )}();(max{)21 ( 21 xxxx  . (8.5) Насколько (8.3) отличается от (8.5) можно судить из следующей табл. 8.1. Таблица 8.1 1x 2x )3.8)(( 21 xx  )5.8)(( 21 xx  расхождение 0 0 0 0 0 0 0.1 0.1 0.1 0 0 0.3 0.3 0.3 0 0.1 0.6 0.64 0.6 0.04 0.2 0.8 0.84 0.8 0.04 0.5 1 1 1 0 0.6 0.6 0.84 0.6 0.24 0.8 0.8 0.96 0.8 0.16 0.9 0.9 0.99 0.9 0.09 1 1 1 1 0 66 Итак, наиболее значительное расхождение имеет место, когда меры истинности переменных близки друг к другу и группируются в области значений от 0.5 и выше. Наконец, Заде использовал формулу )}();(min{)&( 2121 xxxx  , (8.6) хотя вероятностным аналогом этой формулы является )|()()&( 12121 xxxxx  . (8.7) Опять же, если считать переменные независимыми, то получим )()()&( 2121 xxxx  (8.8) Собственно, (8.3), (8.4) и (8.8) дают нам возможность строить машину нечеткого логического вывода на сравнительно ясной ма- тематической платформе. Это можно показать на примере. Пусть дана система нечетких логических дизъюнктов (0.9) (0.6), 212 211 xxD xxD   (8.9) Требуется найти нечеткое решение этой системы. Запишем си- стему уравнений: 0.6= )()()()()( 212121 xxxxxx  0.9= )()()()()( 212121 xxxxxx  Воспользовавшись (8.4), получим в итоге [6] 0.6= ))(1()()(1)( 2121 xxxx  0.9= ))(1())(1()(1)(1 2121 xxxx  67 Здесь ровно две переменные и два уравнения (уравнения нели- нейные). Кроме того, следует добавить еще ограничения на значе- ния переменных: .1)(0 ;1)(0 21  xx Такую систему легко решить в Excel с помощью пакета Поиск Решения. a b 0,2 0,499999 0,399999 1,1 0,2 0,2 0,499999 0,499999 Мы получили ответ: 5.0)( ;2.0)( 21  xx Если использовать соотношение Заде (8.5), то примем во внима- ние, что )].()([5.0),max( yxabsyxabsyx  Работа с абсолютными значениями (abs) является крайне не- удобной по техническим соображениям. Например, 2)()( yxyxabs  . Поэтому нотацию Заде следу- ет признать плохо приспособленной к вычислениям. Мы далее не будем ее рассматривать в практическом плане. Введем в систему еще один дизъюнкт: (0.7) (0.9), (0.6), 213 212 211 xxD xxD xxD    (8.10) Теперь поиск решения не может найти решения. Поэтому мы 68 ищем приближенное решение, введя новые переменные, как пока- зано ниже min)7.0()9.0()6.0( , , , 2 3 2 2 2 1 213 212 211     DDD xxD xxD xxD (8.11) Эта система перепишется следующим образом: .10 ,10 min)7.0()9.0()6.0( , , , , , , 2 3 2 2 2 1 213 213 212 212 211 211          i i D x DDD xxD xxD xxD xxD xxD xxD (8.12) Теперь нам нужно выяснить, что такое в нечеткой логике опера- ция следования (импликации)  . Здесь мы не выходим за рамки общепринятого подхода:    ()  (). (8.13) Это дает окончательно: 69 .1)(0 ,1)(0 min)7.0)(()9.0)(()6.0)(( ),()(-)()()( ),()(-)()()( ),()(-)()()( 2 3 2 2 2 1 21213 21212 21211       i i D x DDD xxxxD xxxxD xxxxD (8.14) Решим эту систему с помощью пакета Поиск решения и найдем: D1 D2 D3 mx1 mx2 0,583307 0,859066 0,669432 0,252739 0,557627 -4,9E-08 4,92E-08 0,002889 4,92E-08 0,252739 0,252739 0,557627 0,557627 Итак, 557.0)( ;253.0)( 21  xx  . Возникает вопрос, насколько найденное решение хорошо или плохо? Этот же вопрос возникает и тогда, когда число уравнений больше числа переменных или наоборот. Таким образом, общий случай решения нечетких систем уравнений (дизъюнктов) требует искать приближенное решение, наилучшим образом соответствую- щее заданным значениям. Степень доверия найденному решению можно оценить с помощью статистического критерия, например, 2. Вычисляем расчетное значение критерия 2 по формуле: 70 2 1 1 2 2 )(       k k j j jj E En (8.15) Здесь nj  фактическое значение j-го уравнения (значение урав- нения можно связать с вероятностью принятия им истинного значе- ния); Ej – заданная мера истинности j-го уравнения. Данное уравне- ние позволяет найти расчетное значение критерия 2. В нашем слу- чае имеем 2 = 0038.0 7.0 )7.067.0( 9.0 )9.086.0( 6.0 )58.06.0( 222       Это значение следует сравнить с табличной величиной 2 для числа степеней свободы, равной числу переменных, поскольку только переменные определяют значения уравнений (но не наобо- рот). В нашем случае число степеней свободы p равно 3. Должно выполняться соотношение расчетное значение 2 не выше табличного. Для этой цели можно воспользоваться статистическими функ- циями Excel, именно функцией ХИ2ОБР (рис 8.1). Рис 8.1. Табличное значение 2 71 Используя эту функцию, следует ввести число степеней свободы p и вероятность ошибки, например, 0.05. Это значение x=7.814 и будет соответствовать 2 табличному. Так, в нашем случае заклю- чаем, что найденное нами точное решение можно рассматривать как статистически адекватное. Теперь можно с рассмотренных позиций указать, как строить не- четкий логический вывод. Пусть имеется множество формул 1, 2, …, n, для каждой из которых известна нечеткая мера истинности: (1),…, (n). Спрашивается, выводима ли из этого множества формула  с нечеткой мерой истинности ()? Согласно общему правилу, выводимость трактуется так 1, 2, …, n  , если и только если (1 & 2 & …& n )  () в любой интерпретации. Так, относительно системы (8.14) спросим, выводима ли из нее формула )6.0( 14 xD  ? Присоединим к системе отрицание до- казываемой формулы и попытаемся найти решение. Если нам удастся найти статистически адекватное (по критерию 2 ) реше- ние, то выводимость места не имеет. Если решения найти не удаст- ся, то выводимость имеет место. Итак, нам потребуется решить си- стему .1)(0 ,1)(0 min)4.0)(()7.0)(()9.0)(()6.0)(( )()( ),()(-)()()( ),()(-)()()( ),()(-)()()( 2 4 2 3 2 2 2 1 14 21213 21212 21211        i i D x DDDD xD xxxxD xxxxD xxxxD При этом мы добавили в систему формулу )()( 14 xD  и изменили критерий 72 .min)4.0)(()7.0)(()9.0)(()6.0)(( 24 2 3 2 2 2 1  DDDD ЛЕКЦИЯ 9 Нечеткая математика в принятии решений Рассмотрим достаточно простую модель принятия решений на основе следующего уравнения: xyRXY  . (9.1) Здесь Y – нечеткий выходной вектор, а X – нечеткий входной вектор. Нечеткий вектор – этот математический объект типа следу- ющего: <низкий(0.3), средний (0.6), высокий (0.1)> Числа в скобках указывают нечеткую меру истинности данного значения в представлении эксперта или лица, принимающего ре- шения. Например, <низкий (0.3)> означает, что эксперт оценивает некое качество как низкое с оценкой 0.3. Оценки выставляются в диапазоне от 0 до 1. Наивысшая оценка 1 соответствует варианту четкой истины. Впрочем, разница между 0.99 и 1.0 нами вообще никак не воспринимается. Среднее значение 0.5 воспринимается как точка безразличия, когда нельзя ни считать наличие свойства, ни его отсутствие истинными (ложными). Любое значение нечеткой меры, большее 0.5, должно восприниматься как правдоподобно ис- тинное, а меньшее 0.5 – как правдоподобно ложное. В выражении (9.1) xyR называется матрицей нечеткого отноше- ния «вход-выход». Для удобства восприятия рассмотрим такой пример. Пусть входной вектор X характеризует спрос на товар, например X = <низкий(0.3), средний (0.6), высокий (0.1)> (9.2) 73 Выходной вектор Y характеризует цену, которая условно может принимать три значения: низкая, средняя и высокая. Зададим матрицу нечеткого отношения «спрос-цена» (рис. 9.1) следующим образом (матрица составляется экспертом, т.е. является субъективной характеристикой). xyR Х/Y Цена низкая Цена средняя Цена высокая Спрос низкий 0.9 0.7 0.1 Спрос средний 0.6 0.9 0.6 Спрос высокий 0 0.4 0.9 Рис. 9.1. Матрица нечеткого отношения Рассмотрим ячейку [спрос низкий, цена низкая] = 0.9. Эта оценка свидетельствует о том, что весьма разумно при низком спросе держать низкие цены (разумеется, в пределах допустимого). Впрочем, более точно проводить измерение не по шкале «спрос- цена», а по шкале «спрос-цена*объем_выпуска». Общая формула примерно такова constобъемцена (9.3) В связи с этим замечанием нашу таблицу следовало бы сделать трехмерной, но это слишком усложнило бы рассмотрение. Итак, пусть дан входной вектор (9.3). Умножим его на таблицу (матрицу) xyR по правилам нечеткого векторно-матричного умножения. Опять же в интересах простоты умножение будем выполнять традиционно, считая, что нечеткое умножение и обычное умножение совпадают. Нечеткое же сложение определим таким образом: ),max( baba  (9.4) Умножение вектора на матрицу мы иллюстрируем таким образом: 74              36.0 ,54.0 ,36.0 9.01.06.06.01.03.0 ,1.01.09.06.07.03.0 ,01.06.06.09.03.0 0.9 0.4 0 0.6 0.9 0.6 0.1 0.7 0.9 0.1 0.6, 0.3, Теперь пусть цена на товар может быть установлена в приемлемом диапазоне [100, 400], где 100 – минимально приемлемая цена, а 400 – максимально возможная цена. Нами получен выше выходной вектор <низкая(0.36), средняя (0.54), высокая (0.36)>. Окончательный выбор цены произведем по формуле 250 36.054.036.0 36.040025054.010036.0Ц i i         i (9.5) Таким образом, при указанном входном векторе и матрице нечеткого отношения <вход-выход> определено конкретное значение выходной цены на товар, равное 250. Рассмотренный подход не является единственно возможным. Можно рассмотреть задачу принятия многокритериальных нечетких решений в следующей постановке. Пусть даны альтернативы: 321 ,, AAA и матрица нечеткого отношения предпочтения на множестве альтернатив (рис. 9.2): A1 A2 A3 A1 0 0.7 0.5 A2 0.1 0 0.1 A3 0.4 0.8 0 Рис. 9.2. Матрица нечеткого отношения на множестве альтернатив Эту матрицу следует читать таким образом. В ячейках записаны величины, определяющие степень (нечеткой) предпочтительности одной альтернативы против другой. Например, альтернатива A1 предпочтительней A2 с нечеткой оценкой 0.7. Наоборот, 75 альтернатива A2 предпочтительнее альтернативы A1 с нечеткой оценкой 0.1 (должно выполняться соотношение )1 jiij  . Спрашивается, какую альтернативу выбрать? Для решения этой задачи, опять же, можно использовать разные подходы. Один из них просто находит сумму оценок в каждой строке и выбирает альтернативу с максимальной суммой (у нас A1 или A3). С другой стороны, насколько, например, предпочтительность с оценкой 0.55 убедительна? Поэтому можно предложить следующую процедуру. Если мера предпочтительности ij <0.5+ (где  можно назвать порогом чувствительности), то в матрице заменяем это число на 0, в противном случае, т.е. при ij 0.5+ записываем в ячейку 1. В статистике используют, например, максимальную вероятность ошибки на уровне 5%. Поэтому примем =0.05 (1*0.05). Итак, пороговым значением будет 0.55. В итоге наша матрица примет такой вид (рис. 9.3): A1 A2 A3 A1 0 1 0 A2 0 0 0 A3 0 1 0 Рис. 9.3 Теперь выбираем те альтернативы, которые содержат в своих строках максимальное число 1. Наш выбор такой: A1 , A3. Если число выбранных альтернатив превосходит 1, то строим подматрицу на этих альтернативах, выбирая значения из ячеек исходной матрицы (рис. 9.4): A1 A3 A1 0 0.5 A3 0.4 0 Рис. 9.4 76 Теперь опять находим сумму элементов в строках и выбираем альтернативу с максимальной суммой, т.е. A1. Обратимся к общему случаю. Пусть имеется несколько критериев и для каждого критерия имеется соответствующая матрица нечеткого отношения предпочтения (рис. 9.5). Например: Критерий 1: A1 A2 A3 A1 0 0.6 0.4 A2 0.3 0 0.2 A3 0.55 0.6 0 Критерий 2: A1 A2 A3 A1 0 0.3 0.5 A2 0.4 0 0.7 A3 0.4 0.2 0 Рис. 9.5. Матрицы нечеткого отношения для нескольких критериев Находим распределение мест по критериям. Для первого критерия получаем матрицу (рис. 9.6): A1 A2 A3 места A1 0 1 0 2 A2 0 0 0 3 A3 1 1 0 1 Рис. 9.6 Для второго критерия аналогичная таблица имеет такой вид (рис. 9.7): 77 A1 A2 A3 места A1 0 0 0 2-3 A2 0 0 1 1 A3 0 0 0 2-3 Рис. 9.7 Для уточнения мест в последней таблице строим подматрицу на тех альтернативах, для которых вопрос о месте не решен однозначно (рис. 9.8): A1 A3 места A1 0 0.5 2 A3 0.4 0 3 Рис. 9.8 Итак, распределение мест по критериям таково (рис. 9.10): Критерий 1 Критерий 2 A1 2 (сумма баллов 1) 2 (сумма баллов 0.8) A2 3 (сумма баллов 0.5) 1 (сумма баллов 1.1) A3 1 (сумма баллов 1.15) 3 (сумма баллов 0.6) Рис. 9.10. Распределение мест по критериям В качестве итогового ответа выберем альтернативу, набравшую наименьшую сумму мест, а при равенстве этого показателя – альтернативу с максимальной суммой баллов. В нашем примере в качестве ответа будет A1. В заключение рассмотрим, как рассчитываются нечеткие меры. Одним из таких методов является метод интервалов. Он предполагает, что имеется несколько экспертов, каждый из которых 78 ставит интервальную оценку для меры. Например, путь имеется два эксперта А и B, которые поставили такие оценки (рис. 9.11). Рис. 9.11. метод интервалов Оценка А есть интервал [0,25;0.6]. Оценка B есть интервал [0,5;0.75]. Зеленым цветом выделен общий подинтервал – [0.5; 0.6]. Разобьем длину всего интервала [0.25; 0.75] на подинтервалы: I1 = [0.25; 0.5]; I2 = [0.5; 0.6]; I3 = [0.6;0.75]. Эти подинтервалы выбраны таким образом, что на всей их длине представлена оценка одного и того же (одних и тех же) экспертов. Так, на подинтервале I1 имеется только оценка эксперта А. Теперь найдем середины подинтервалов I1, I2, I3: 675.0;55.0,375.0 321  Пусть веса экспертов одинаковы: 5.0 BA Пересчитаем веса подинтервалов по формуле Шортлифа: .75.025.05.05.0 ,5.0 2 31   BABA BA Теперь итоговое значение нечеткой оценки произведем по формуле: 56.0 75.05.05.0 5.0675.075.055.05.0375.0          i ii 79 ЛЕКЦИЯ 10 Нечеткий Пролог Рассмотрим следующее предложение языка Пролог: suit (peter, X):  big_salary (X,_)), good_conditions (X, _). big_salary(mailer, 0.4). big_salary(officer, 0.7). big_salary(bob, 0.8). big_salary(artist, 1.0). good_conditions(mailer, 0.7). good_conditions(officer, 0.3). good _conditions(bob, 0.6). good_conditions(artist, 0.9). В нечетком Прологе вывод осуществляется таким образом, что- бы либо найти ответ с максимальной правдоподобностью, либо “обычным образом”, но учитывая, что значение 0.5 и ниже в каче- стве меры истинности рассматривается как ложное. Рассмотрим, как реализовать два этих подхода. Подход по принципу 0.5 и ниже – ложь. В этом случае наша программа должна быть переписана следу- ющим образом: suit (peter, X): - big_salary (X,Y)), Y>=0.5, 80 good_conditions (X,Z), Z>=0.5. big_salary(mailer, 0.4). big_salary(officer, 0.7). big_salary(bob, 0.8). big_salary(artist, 1.0). good_conditions(mailer, 0.7). good_conditions(officer, 0.3). good _conditions(bob, 0.6). good_conditions(artist, 0.9). Как видим, изменения в этом случае в тексте программы мини- мальные. Теперь рассмотрим второй подход: поиск ветви с наибольшим значением степени истинности. Для реализации второго подхода нам потребуется воспользоваться рекурсией следующим образом: database job(string) suit (peter, R): - big_salary (X,Y)), good_conditions (X,Z), T=Y*Z. T>R, retractall(_), !, assert(job(X)), suit(peter,T). suit (peter, _): - job(X), write (“VYBRANA RABOTA:”,X). big_salary(mailer, 0.4). 81 big_salary(officer, 0.7). big_salary(bob, 0.8). big_salary(artist, 1.0). good_conditions(mailer, 0.7). good_conditions(officer, 0.3). good _conditions(bob, 0.6). Здесь мы используем предикат базы данных job, в котором хра- нится в конце-концов выбранная работа. Цель данной программы должна быть записана в следующем виде goal suit(peter,0). Объясним наиболее сложный участок данной программы: suit (peter, R): - big_salary (X,Y)), good_conditions (X,Z), T=Y*Z. T>R, retractall(_), !, assert(job(X)), suit(peter,T). Сначала последовательно выполняются предикаты: big_salary (X,Y)), good_conditions (X,Z), T=Y*Z. Здесь по порядку выбирается работа, а затем выбирается соот- ветствующая ей зарплата и условия. Вычисляется величина T=Y*Z. После этого выполняется проверка 82 T > R, (10.1) которая в случае удачи вызовет смену содержимого предиката базы данных job, записав в него выбранную работу и снова вызвав пре- дикат suit(peter, T), где T – новая оценка степени истинности прави- ла. Заметим, что хотя бы одна работа всегда будет выбрана. Если нет уже ни одной работы, для которой выполняется условие (10.1), то осуществляется выход в правило: suit (peter, _): - job(X), write (“VYBRANA RABOTA:”,X). Для вывода найденной работы на экран. Более интересным является использование механизмов Пролога и метода многокритериального выбора Саати. Иначе говоря, в Про- логе следует реализовать механизм Саати-оценки альтернатив. Рас- смотрим следующий пример. like(mary, X, Z):- rich(X, Z1), young(X, Z2), Z =A1*Z1+A2*Z2. rich(peter, 0.7). rich(mike, 0.5). rich(jim, 0.3). young (peter, 0.3). young (mike, 0.6). young (jim, 0.9). Для решения задачи должны быть известны веса критериев A1, A2. При этом мы хотим отобрать вариант с максимальным значением итоговой оценки. Этот вариант поиска нами рассмотрен выше. Так что единственно, что привнесено в эти последние рассуждения, – это 83 использование Саати-оценки. Рассмотрим, как в Прологе реализовать выбор значения функции. Это иллюстрируется следующим текстом. fun(X,Y):- funMin(X,Y1), funMax(X,Y2), Y=0.5*(Y1+Y2). funMin(X,Y1):- znach(X1,Y1), X1>=X. funMax(X,Y1):- znach(X1,Y1), X1>=X-1. znach(0,1). znach(1,1). znach(2,4). znach(3,9). znach(4,16). znach(5,25). znach(6,36). znach(7,49). znach(8,64). Найдем fun(7.5,Y). Сначала считается funMin(7.5,Y1). Оно использует znach(8,64) и возвращает значение Y1=64. Затем считается funMax(7.5,Y2). Это вычисление полагает X1=7.5-1=6.5 и затем считает funMin(6.5,Y2), что дает Y2=49. Затем возвращается среднее значение: 0.5*(64+49)=56.5. Описанный способ вычисления функции будет тем точнее, чем меньше разница между соседним значениями x в списке значений znach. 84 ЛЕКЦИЯ 11 Принятие решений в условиях риска и неопределенности В условиях неопределенности экспертная система или иная ин- теллектуальная система должна сделать выбор или последователь- ность выборов из совокупности различных возможных действий, исход которых носит вероятностный (неопределенный) характер. Принципы такого выбора назовем стратегией решения задачи в условиях неопределенности. Для формализации задачи введем по- нятие лотереи – как модели простейшей задачи выбора решения в условиях неопределенности. Лотерея характеризуется набором исходов .,...,, 21 zOutOutOut Для каждого исхода известна вероятность pi и ожидаемый доход Gi (прибыль/убыток). Это можно представить таким образом (рис. 11.1): Рис. 11.1. Лотерея с набором исходов При этом  1ip . Сыграть в лотерею – значит купить ее, но какую прибыль она принесет заранее неизвестно. Известно только, что реализуется 85 один из исходов .,...,, 21 zOutOutOut Проблема выбора состоит в том, что перед лицом, принимающим решение, может стоять задача выбора какой-то одной из нескольких лотерей, либо ни одной. Рас- смотрим пример. Пусть человек решает, брать ему зонтик или нет. Здесь две лотереи. Первая – брать зонтик. Вторая – не брать зонтик. Рассмотрим каждую из них. Лотерея «брать зонт» имеет следующую схему (рис. 11.2): Рис. 11.2. Лотерея «брать зонт» В данной лотерее два исхода – дождь будет (Out1 ) и дождя не будет (Out2 ). Пусть вероятности этих событий известны и равны соответственно: p1 = 0.2, p2 = 0.8. Труднее оценить доходы (потери). Для этой цели в практических задачах применяют функцию полез- ности F. Эта функция безразмерная и принимает значения в интер- вале от 0 до 1 включительно. Значение 1 соответствует наилучшему исходу, значение 0 – наихудшему. Точка 0.5 соответствует точке безразличия (индифферентности). Значения функции полезности выше 0.5 считаются доходными (благоприятствующими), а ниже 0.5 – расходными (неблагоприятствующими). В данной модели зон- тик взят. Следовательно, при наличии дождя можно принять F = 1 (зонтик себя полностью оправдал). При отсутствии дождя F = 0 86 (зонтик взят бессмысленно, пришлось его напрасно таскать). Здесь следует заметить, что функция полезности F определяется субъек- тивно именно тем лицом, которое и собирается брать или не брать зонтик. Следовательно, значения функции полезности для разных лиц, принимающих решение, вообще говоря, будут различными. Теперь мы подошли к самому важному моменту – оценке лотереи. Определение. (Объективной) Ценой лотереи называется величина:  iiGpO . (11.1) В нашем примере O = 0.8*0 + 0.2*1 = 0.2 Цена лотереи и определяет, нужно ли принимать данное реше- ние или нет. Полученная цена ниже 0.5 (по шкале измерения функ- ции полезности), т.е. указывает, что данная лотерея в целом ведет к неблагоприятному исходу. Но для окончательного принятия реше- ния нужно рассмотреть вторую лотерею из рассматриваемой зада- чи «не брать зонтик» (рис. 11.3). Рис. 11.3. Лотерея «не брать зонт» 87 В этой лотерее G1 = 0 (пошел дождь, зонта не взяли), G2 = 1. Цена лотереи составляет O = 0*0.2+1*0.8 = 0.8. Итак, вторая лотерея сулит нам лучший результат. Вывод – при данных вероятностях и функции полезности лучше зонта не брать. Вместе с тем, ситуация может радикально измениться, если про- мокнуть для нас значит значительно больше, чем «бесполезно про- таскать» зонт. Так, в первой лотерее зададим G2 = 0.5. Оценка пер- вой лотереи станет O = 0.8*0.5 + 0.2*1 = 0.60. Во второй лотерее зададим также G2 = 0.7. Оценка второй лоте- реи теперь составит O = 0*0.2+0.8*0.7 = 0.56. Теперь выгоднее брать зонт. Основными двумя вопросами являются измерение функции по- лезности и оценка вероятности. Обе эти задачи могут решаться в условиях неопределенности. Начнем с задания функции полезности. Этот процесс основан на методе Саати. В этом методе сначала нуж- но указать критерии, по которым производится оценка состояний задачи. Обычно в качестве критериев для экономических задач вы- ступают всего два: доходы (прибыли) и расходы (убытки). Сначала мы вкладываем средства (в нечто) и несем расходы, но затем получа- ем прибыли (окупаем расходы). Для задачи о зонтике доходы – это сухая одежда, расходы – это затраты на таскание зонтика. Итак, имеем два очевидных критерия: K1  обеспечиваем одежду сухой; K2  затраты на таскание зонтика. Далее составляется матрица критериев (рис. 11.4): K1 K2 K1 1 4 K2 0.25 1 Рис. 11.4 88 В этой матрице в ячейках записаны относительные значения приоритетов критериев по отношению друг к другу. Числа берут из шкалы Саати: 1,2,3,4,…,10, 1, 2 1 ,..., 8 1 , 9 1 , 10 1 . Иначе говоря, если в ячейке (i,j) записано число z из шкалы Саати, то в симметричной ей ячейке (j,i) записывается число z 1 . Числа выбирают из следующих «практических» соображений. Если критерии примерно равноценны (равнозначны), то пишем в ячейке 1. Если критерий Ki незначительно важнее критерия Kj , то пишем в ячейке (i, j) 2 или 3, а в ячейке (j,i) соответственно 2 1 или 3 1 . При выставлении степени предпочтительности одного критерия по отношению к другому можно использовать ассоциацию с фут- больным матчем. Скажем, победа со счетом 4:1 указывает на боль- шое преимущество победителя, а победа со счетом 8:1 на подавля- ющее преимущество. В нашем примере мы видим, что обеспечить одежду сухой существенно важнее, чем протаскать зонтик. После того, как матрица Саати составлена, находят произведения чисел в строках и из полученных произведений извлекают корень, степень которого равна числу критериев (в нашем примере извлекаем корень второй степени). Получим следующие значения (рис. 11.5): K1 K2 ияпроизведен Приоритеты  K1 1 4 2 8.0 5.2 2  K2 0.25 1 0.5 2.0 5.2 5.0  89 Сумма 2.5 Рис. 11.5. Расчет приоритетов критериев Подсчитываем сумму найденных корней – 2.5. Теперь выполня- ем заключительное действие – отыскиваем приоритеты критериев путем деления найденных значений корней на сумму корней: .2.0,8.0 21  Чтобы использовать эти оценки строим далее функции полезно- сти для критериев. Функции полезности, как ранее указывалось, имеют субъективный характер. Они могут быть дискретными или непрерывными. В нашем примере построим такие функции полез- ности. По критерию K1 – обеспечить одежду сухой (рис. 11.6): Рис. 11.6.Функция полезности по критерию К1 По критерию K2 – затраты на таскание зонтика (рис. 11.7): 90 Рис. 11.7. Функция полезности по критерию К2 Итак, наши графики функций полезности весьма элементарные. Теперь пусть вероятность дождя остается, как и ранее равной 0.2. Снова рассмотрим первую лотерею (рис. 11.8). 91 Рис. 11.8 Рассчитаем G1= 8.002.018.0)()( 2211  таскатьсухая KK Рассчитаем G2= 8.002.018.0)()( 2211  таскатьсухая KK Обратим внимание на то, что в обоих исходах одежда остается сухой и мы таскаем зонтик, так что оценки полезности совпадут. Общая оценка лотереи составит: О = 0.2*0.8+0.8*0.8=0.8. Для второй лотереи получим по аналогии (рис. 11.9): 92 Рис. 11.9 Рассчитаем G1= 2.012.008.0)_()( 2211  таскатьнемокрая KK Рассчитаем G2= 112.018.0)_()( 2211  таскатьнесухая KK Оценка лотереи составит: О = 0.2*0.2+1*0.8=0.84 Эта оценка весьма незначительно превосходит первую лотерею, так что зонтик при этом раскладе можно как брать, так и не брать (результат одинаковый). Однако, при вероятности дождя 0.3 ситуа- ция меняется на противоположную: О(брать зонт)= 0.3*0.8+0.7*0.8=0.8 О(не брать зонт) = 0.3*0.2+1*0.7=0.76 Теперь рассмотрим расчет вероятности. Достаточно общим слу- 93 чаем является применение теоремы Байеса. Это применение осно- вано на использовании имеющихся опытных статистических таб- лиц. Пусть дана такая табл. 11.1. Таблица 11.1 Фактор Дождь (число случаев) Не дождь (число случаев) Всего 18 42 Пасмурно 18 42 Ветрено 5 12 Не ветрено 13 30 Пусть сегодня пасмурно (E1) и не ветрено (E2). Заметим, что все дни наблюдений были пасмурными, поскольку в непасмурный день дождей нет. Всего наблюдалось 60 дней. Определим из этой табли- цы вероятность дождя, полагая, что E1 и E2 независимы. По теоре- ме Байеса получим: )/(*)/(*)( )/(*)/(*)( )/(*)/(*)( ),/( недождьневетреноPнедождьпасмурноPнедождьP дождьневетреноPдождьпасмурноPдождьP дождьневетреноPдождьпасмурноPдождьP неветренопасмурнодождьP    Из таблицы найдем: 75.0 42 30 )/( 1 42 42 )/( 7.0 60 42 )( 7.0 18 13 )/( 1)/( 3.0 4218 18 )(         недождьневетреноP недождьпасмурноP недождьP дождьневетреноP дождьпасмурноP дождьP 94 Здесь в пояснении нуждаются последние две строки. Например, как получена оценка 1 42 42 )/( недождьпасмурноP Дождя не было в 42 случаях. Но пасмурно было всегда, и при дожде и не при нем. Аналогично имеем 75.0 42 30 )/( недождьневетреноP В самом деле, дождя не было в 42 случаях. При этом неветрено было в 30 случаях. Теперь получим окончательно 47.0 1*75.0*7.07.0*1*3.0 7.0*1*3.0 )/(*)/(*)( )/(*)/(*)( )/(*)/(*)( ),/(       недождьневетреноPнедождьпасмурноPнедождьP дождьневетреноPдождьпасмурноPдождьP дождьневетреноPдождьпасмурноPдождьP неветренопасмурнодождьP Итак, при E1, E2 вероятность дождя 0.47. ЛЕКЦИЯ 12 Генетические алгоритмы В основе генетических (эволюционных) алгоритмов лежит простая идея: берут пару наилучших образцов из порожденной совокупности объектов и порождают их потомка путем взаимного обмена характеристиками (этот механизм называется кроссовером). Потомков порождают все время из элитных представителей текущей совокупности. Когда наступает момент и не удается улучшить требуемый функционал, производят мутацию, т.е. порождают новые объекты не в результате «скрещивания» родительских объектов, а путем случайных изменений. Эта процедура ведется до тех пор, пока удается улучшить 95 характеристики функционала. Пример. Пусть требуется максимизировать функцию 0 0 11 ,42),(     y x yx yxyxyxF (12.1) Сформируем начальную популяцию случайным образом (рис.12.1) № x y F(x,y) 1 0 1 4 2 1 0 2 3 2 3 10 4 4 2 8 5 0 5 20 6 1 1 5 7 5 5 5 8 2 9 22 9 6 1 10 Рис. 12.1. Начальная популяция Выберем элиту из четырех наилучших образцов, где функция достигает наибольших значений (рис. 12.2): № x y F(x,y) 3 2 3 10 5 0 5 20 8 2 9 22 9 6 1 10 Рис. 12.2 Породим потомков, например, «скрестим» пятый и восьмой объекты путем обмены координат; получим, например: 96 <0,9> и <2,5> при этом смотрим, чтобы выполнялось ограничение 11 yx . Таблица примет такой вид (рис. 12.3): № x y F(x,y) 3 2 3 10 5 0 5 20 8 2 9 22 9 6 1 10 10 0 9 36 11 2 5 14 Рис. 12.3 Видим, что лишь один потомок дал существенный прирост функции (12.1). Плохих потомков следует отбросить. Будем манипулировать данной популяцией. Скрестим десятый и восьмой объекты. Однако нам не удалось улучшить целевую функцию путем скрещивания. Более лучших значений функции при других значениях x и y мы не достигли, следовательно, прибегнем к мутации. Мутация – небольшие произвольные изменения характеристик совокупности. Осуществим мутацию наилучших двух образцов. Породим объекты:<2,10>,<0,10>. Таблица примет такой вид (рис. 12.4): № x y F(x,y) 3 2 3 10 5 0 5 20 8 2 9 22 9 6 1 10 10 0 9 36 11 2 5 14 12 2 10 24 13 10 10 40 Рис.12.4 97 Таким образом, удалось улучшить функционал. Снова возобновляем скрещивания и т.д., и т.п. Процесс завершаем, когда ни скрещивание, ни мутация не улучшают функционал. ЛЕКЦИЯ 13 Неклассические логики Понятие истины является фундаментальным в естествознании. Под истиной следует понимать соответствие того, что утверждается, тому, что есть в действительности. Здесь имеется два момента. Первый. Как проверить соответствие и как быть, если такая проверка невозможна в принципе? Второй. О какой действительности идет речь? Начнем со второго момента. Еще Аристотель указал на неоднозначность логической интерпретации утверждений о будущих событиях. Например, рассмотрим утверждение «Завтра состоится морское сражение». Это утверждение относится не к тому, что есть, а к тому, что будет (к будущему состоянию мира). Вместе с тем будущее состояние мира в данный момент нельзя знать точно, например, в силу фундаментального закона неопределенности Гейзенберга. Как же можно вести речь о соответствии тому, что точно не определено и принципиально не может быть точно определено в момент высказывания? Иначе говоря, вариантов будущих действительностей множество, а какой из этих вариантов реализуется заранее неизвестно. Поэтому говоря о будущих событиях, мы не знаем о какой действительности идет речь, а имеем в виду любую действительность, что нарушает трактовку истины в традиционном смысле (мы считаем, что действительность единственна). Еще более запутана ситуация в математике, где «действительностью» является мир формальных объектов, например, прямых и точек. Так, геометрия Лобачевского исключает постулат о параллельных в геометрии Евклида, следовательно, эти две геометрии «рассматривают» разные действительности. Обратим внимание на тот принципиальный момент, что математика имеет 98 дело с абстрактными понятиями (например, понятием числа или точки, или бесконечно малой величины и т.п.), поэтому математических действительностей, вообще говоря, бесчисленное множество (в отличие от физической действительности). Неопределенность в отношении к действительности связывается не только с будущим, но и с недостаточностью знаний о ней в настоящем. Например, некто утверждает, что в разложении числа  имеется бесконечное число нулей. Проверка этого утверждения, вообще говоря, может потребовать получить бесконечное разложение числа , что невозможно. Поэтому данное высказывание неопределенно в силу незнания. Итак, отношение высказывания к действительности может иметь неопределенное значение, если действительность не определена или нельзя установить соответствие между тем, что утверждается, и тем, что есть в действительности в силу незнания. Аристотель фактически первым поставил вопрос о необходимости измерения истины с помощью шкалы, содержащей более двух значений. Польский математик Ян Лукасевич разработал теоретическую основу сначала трехзначных, а затем многозначных логик (20-е годы прошлого века). Отметим также работы русского математика Николая Васильева (Казанский университет), который построил логическое исчисление для противоречивых формул. Вместе с тем следует отметить, что работы Лукасевича не сразу нашли признание в научном сообществе. Еще в тридцатые годы прошлого века значительная часть ученых противилась «многозначной» трактовке истины. Ясно, что в отношении физической действительности можно делать упор на ее единственность, так что утверждение «завтра состоится морское сражение» определенно либо будет иметь место, либо нет в той единственной действительности, которая будет завтра. Однако и в физическом мире все не так очевидно даже и без будущих событий. Например, некто говорит «Я умный». Это утверждение может быть истинным в глазах этого некто и ложным в глазах другого некто. Почему так? Потому что каждый человек видит мир своими глазами, т.е. действительностей столько, сколько точек зрения. Отсюда, в частности, следует, что в истории много утверждений 99 измеряются субъективно, не имеют объективной оценки. В математике дело «сложилось» еще более запутанно. Здесь столкнулись с парадоксами. Парадоксы – это утверждения, которым нельзя приписать ни истинное, ни ложное значение. Именно парадоксы объективно мотивируют введение многозначных логик. Перейдем к их рассмотрению. Логические парадоксы и их причины Наиболее известный парадокс – это парадокс лжеца. Пусть некто заявляет: «Я лгу». Спрашивается, говорит ли этот некто правду или лжет. Простой анализ показывает, что приведенное утверждение не может быть ни истинным, ни ложным. Так, если оно истинно, то некто лжет в действительности, т.е. утверждение должно быть ложным. И наоборот, если утверждение ложно, то некто говорит правду, что также невозможно в силу характера утверждения. Причина парадокса в недопустимой самоприменимости формулы к самой себе. Самоприменимость достаточно интересное явление. Например, нельзя себя вытащить за волосы из болота. Любая физическая система не может самой себе сообщить дополнительную энергию. Это случаи невозможной самоприменимости. Вместе с тем есть допустимая самоприменимость. Например, всякую программу (алгоритм) можно применить к самой себе, т.е. подать на вход программы текст этой же программы. Реакция может быть разной – от отторжения до попытки что-то посчитать. Другой знаменитый парадокс – это парадокс «брадобрея». Он звучит так. В одном швейцарском кантоне брадобрей бреет тех и только тех, кто не бреется сам. Спрашивается, бреет ли брадобрей самого себя? Идеи неклассических исчислений Любое логическое исчисление с числом значений истинности, большим 2, является неклассическим. Так, Я. Лукасевич первона- чально сформулировал исчисление с тремя значениями истинности – 100 0, 1, 0.5 (неопределенность). Разумеется, можно к неклассическим отнести и исчисления с двумя значениями истинности, но иным определением правил вывода. Такого рода исчисления мы не рас- сматриваем. Итак, для каждой логической формулы f в неклассическом ис- числении должна быть представлена мера истинности этой форму- лы в любой интерпретации (т.е. при любых значениях аргументов). Обозначим такую меру как val(f). Каковы бы ни были неклассические логики, для них справедли- вы следующие аксиомы. А1. val(false)=0; val(true)=1; 1 val(f)  0. A2. Если , то val()  val(). (13.1) Эти аксиомы настолько общи, что допускают бесконечное число различных неклассических логик. Каждая неклассическая логика задает свой вариант исчисления значений логических операций. Вероятностная логика. Основные аксиомы Пусть P – вероятностная мера [7]. Она удовлетворяет следую- щему определению, в котором T – тождественно истинная, а F – тождественно ложная формула. (A1) 0  P(f)  1 для f , f – логическая формула; (A2) P(T)= 1, P(F)= 0; (A3) Если f  g, то P(f)  P(g) ; (A4) Если f & g = F, то P(f g) = P(f) + P(g) и P(f & g) =0. Легко установить следующее: )&()()()()()()( gfPgPfPgfPfPgffPgfP  , .1)()()&(  gPfPgfP ).()|()(1 ),()()(1)( fPfgPgfP fgPgfPfggfPTP   101 Как следствие находим )|(1 )(1 )|( )(1 )( fgP gfP fgP gfP fP      (13.2) В самом деле, .1)|()|( , )( )( )|( , )( )( )|(   fgPfgPоткуда fP gfP fgP fP fgP fgP Соотношение (13.2) может быть использовано при построении вероятностных выводов. Рассмотрим следующую схему вывода ?)( ___________ )( ,)(    yP byxP axP (13.3) Из (13.2) получим )|(1 1 xyP b a    . Воспользовавшись формулой )( )|()( )|( xP yxPyP xyP   , найдем )|( 1)()( )|( 1 )( yxP yxPxP yxP ba yP     . (13.4) 102 Теперь следует иметь в виду, что величина )|( yxP характеризует меру связи между y и x, поэтому для ее определения нужно иметь, вообще говоря, статистические таблицы. Пусть дана такая таблица наблюдений (табл. 13.1): Таблица 13.1 x y 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 Из этой таблицы непосредственно найдем .75.0)|( yxP Из (13.4), например, для P(x)=0.6 , P(xy)=0.875 получим P(y) = 0.63. Замечание. Величина )|( yxP как и P(xy) являются статистически устойчивыми значениями, характеризующими связь между переменными x, y. Поэтому соотношение (13.4) надо применять на практике при заданной статистической таблице типа табл. 13.1, но вероятность P(x) может быть произвольной, удовлетворяющей лишь ограничению .1 )|( 1)()(   yxP yxPxP Имеет место также следующая аксиома. ).,max()( ),,min()&( __________ )( ,)( bayxP bayxP byP axP     103 Вычисление вероятностей формул Пусть A и B – пропозициональные формулы. В силу законов ве- роятностной логики можно записать: P(AB) = P(A)+P(B)–P(AB) = P(A)+P(AB)+P(AB)– P(AB) = =P(A)+P(AB). (13.5) Здесь P(A) – вероятность того, что произвольная интерпретация I выполняет формулу A. Далее, если A&B=false, то P(AB) = P(A) + + P(B). В этом случае A и B называют ортогональными. Обобщени- ем (13.5) служит P(A B  ... W) = P(A)+ P(AB)+ P(ABC)+…+ + P(ABC…W). (13.6) Ясно, что если формула A тождественно истинна, то P(A) = 1. Если A и B ортогональны, то P(AB) = P(B). (13.7) Важно заметить, что сложность процедуры вычисления вероят- ности экспоненциально растет от размера формулы в общем случае. Следует, что вычисление каждого слагаемого в правой части вида P(ABC…R) можно заменить вычислением 1 P(A'  B'  C'  …  R'), где A', B', C', … ,R' получены соответственно из A, B, C, … , R с помощью следующих правил: 1. xiY(xi  Z) = xiY ; 2. xiY(~xi  Z) = xiYZ. Следовательно, вычисление P(ABC…W) реализуется ре- курсивно, причем на каждом шаге рекурсии пропадает как мини- мум одна переменная, что гарантирует конечность процедуры. Механизм вычисления вероятностей формул можно непосред- ственно использовать для проверки выводимости формул. 104 Пример. Показать, что из формул 32 21 321 , , xx xx xxx    (13.8) выводима формула .3x Согласно технике вывода, основанной на приведении к противоречию, добавляем к (13.8) отрицание доказы- ваемой формулы и показываем, что вероятность выполнимости по- строенной системы равна 0. Имеем систему . , , , 3 32 21 321 x xx xx xxx    (13.9) Необходимо убедиться, что P )( 33221321 xxxxxxxx  =1. Здесь )( 33221321 xxxxxxxx  есть отрицание (13.9). Воспользуемся одним упрощающим вычисления приемом: расположим формулы справа налево так, чтобы каждая последующая формула содержала как можно больше переменных, индексы которых совпадают с индексами предыдущей формулы. Так, можно использовать следующую последовательность: .,,, 32121323 xxxxxxxx Теперь непосредственно получаем P(13.9)= .1 8 1 8 1 4 1 2 1 ))()(()(()()( 21323321323213323   xxxxxxxxPxxxxxPxxxPxP 105 Выводимость доказана. Следует заметить, что в общем случае вычисление вероятностей формул может потребовать экспоненци- альных затрат. ЛЕКЦИЯ 14 Примеры экспертных систем (система экологического мониторинга) В этой лекции мы рассмотрим экспертную систему экологиче- ского мониторинга (наблюдения). Эта система выполняет следую- щую задачу. Ведется наблюдение за концентрацией вредных при- месей в атмосфере промышленной зоны. Если концентрация пре- вышает санитарную норму, то на основании замеров этой концентрации, данных по температуре, направлению ветра, давле- нию и др. делается предположение о виновнике экологического нарушения. Задача сформулирована предельно общо. Поэтому детализируем ее постановку. Пусть на некоторой территории расположены источники про- мышленного загрязнения I1, I2,...,In, а в выделенной локальной зоне Z этой территории, произведены замеры концентрации загрязняю- щих веществ, представленных вектором Х = (х1, х2, ...,хm). Допуска- ется, что некоторые или даже все результаты измерений окажутся выше ПДК (предельно допустимых концентраций). Требуется уста- новить виновников загрязнения окружающей среды в выделенной зоне и степень их вины. Задачу будем решать при следующих условиях:  известны объемы и мощности газо-воздушных выбросов каж- дого загрязняющего вещества из каждого источника загрязнения,  имеется модель рассеивания вредных примесей в приземных слоях атмосферы,  количество измерений должно быть не менее одного, причем, чем больше измерений, тем точнее будет осуществлена экологиче- ская инспекция. В результате будут вычислены некоторые оценки 1, 2,...,n, 106 определяющие систему предпочтений в установлении виновника, при этом i =1 и если ps, то объективно вина источника Ip оце- нивается выше, чем Is. Описание проблемы и этапов ее решения Допустим, что на территории города за счет функционирования промышленных предприятий может возникнуть n кластеров (доме- нов, зон) с различной степенью загрязнения, характеризующихся векторами 1, 2,..., n, создаваемыми I1, I2, ..., In источниками за- грязнения. Пусть P(i  х) - условная вероятность того, что наблю- даемый вектор х относится к домену i. В силу теоремы Байеса по- лучим: )( )()( )( xP xPP xP ii i   , (14.1) где )(xP  вероятность фактического наблюдения вектора х с данными значениями концентраций загрязняющих веществ; )( iP  – априорная вероятность того, что виновник загрязнения – домен I; )( ixP  – вероятность того, что домен i мог привести к появлению вектора х; i  идентификатор (обозначение) домена. Рассматриваются следующие домены: 0 – ни один из источников не является виновником; 1 – 1-й источников виновен, остальные – нет; ................ m – m-й источник виновен, остальные – нет; m+1 – 1-й и 2-й источники виновны, остальные нет; .............. n – все n источников виновны. Введем штрафную оценку 107    n 1i iijj x)P(ωL(x)r , (14.2) где ijL – штраф, который следует заплатить за ошибочную класси- фикацию виновника Ii вместо фактического Ij. С учетом (14.1) перепишем (14.2) в виде    n 1i iiijj )ωP(x)P(ωL P(x) 1 r Поскольку P(x) является общим множителем для всех виновни- ков, то его просто отбрасывают и формула приобретает такой вид    n 1i iiijj )ωP(x)P(ωLr Теперь, приняв Lii =0 и Lij = Lji =1 (для всех i, j, i  j), получим окончательно     n ji 1i iij )ωP(x)P(ωr (14.3) Формула (14.3) служит основой для принятия решений. Итак, P(i) – априорная оценка вероятности виновности источника i. )|( i xP  – вероятность или ее оценка того, что при виновности источника i измеренная концентрация составит указанное (зафик- сированное) значение x . Введя соотношение 108    n i i i i r r 1 , (14.4) можно утверждать, что наименьшему значению i будет соответ- ствовать источник с наименьшим подозрением на виновность. Применение формулы (14.3) потребует нескольких упрощающих допущений. Во-первых, будем считать, что при условии соблюдения техно- логического регламента источником Ii измерение концентрации в зоне Z не может указать на нарушение экологических норм. Во-вторых, предельные распределения значений концентраций газо-воздушных выбросов от каждого источника загрязнения долж- ны подчиняться многомерному нормальному закону. Таким образом, методика расчетов сводится к определению чле- нов формулы (14.3). Для определения множителей P(i ) использу- ется техника многокритериальной оценки на основе процедуры Са- ати, где в качестве альтернатив рассматриваются домены i , а критериями являются факторы, обусловливающие априорные зна- чения P(i). Для оценки значений P(x|i) проводится серия вычис- лительных экспериментов, целью которых является получение ма- тематического ожидания и среднеквадратического отклонения век- торов загрязнений в домене i. Последующее изложение раскрывает существо указанной мето- дики и ее теоретико-практическое наполнение. Оценка )P(ωi – априорной вероятности того, что виновник загрязнения домен i Значение искомой вероятности можно получить путем матема- тической обработки экспертных оценок специалистов с привлече- нием теории многокритериальных решений и функции полезности. Значения dij частных функций полезности, присваиваемые экс- пертами каждому предприятию, могут располагаться в диапазоне [0, 1]. Чем dij ближе к единице, тем, по мнению эксперта, вероятнее соответствие факта нарушения j -го критерия i- м предприятием. 109 Для выявления возможного предприятия - нарушителя выбраны следующие критерии: Т1  степень устарелости технологии и оборудования на i-м предприятии; Т2  склонность к экологическим нарушениям в прошлом на i-м предприятии; Т3  соответствие характера экологического нарушения типу технологического процесса на i-м предприятии; Т4  недостаточность административных мер для повышения от- ветственности за экологические нарушения на i-м предприятии. Для получения обобщенной, комплексной оценки вероятности по p критериям одновременно необходимо определить коэффици- енты sj, характеризующие значимость, приоритеты (статистические веса) каждого критерия. Для этой цели используется алгоритм Са- ати, по которому строится матрица приоритетов  (рис. 14.1): Т1 Т2 Т3 Т4 Т1 1 12 13 14 Т2 21 1 22 24 Т3 31 32 1 34 Т4 41 42 43 1 Рис. 14.1. Матрица приоритетов критериев Для каждой строки находим: p p j sjs    1 . (14.5) Откуда веса: 110      p s s s s 1 . (14.6) Найденные значения статистических весов считаются согласо- ванными, если выполняется условие Саати: 2,0 )1/()( 0 max    x pp (14.7)    p j sjsR 1 (14.8) где    p s ss R 1 max , (14.9) В зависимости от размерности матрицы приоритетов находятся величины х (табл. 14.1): Таблица 14.1 Размер матрицы 1 2 3 4 5 6 7 8 9 10 х 0 0 0,58 0,90 1,12 1,24 1,32 1,41 1,45 1,49 Обобщенную оценку вероятности виновности источника Ii мож- но вычислить по формуле: 111 P(i ) =   jij d . (14.10) Здесь j – вес критерия j. jid – значение функции полезности критерия j. Определение векторов mi оценок воздействия источника Ii на окружающую среду Каждый источник загрязнения характеризовался по следующим параметрам: * координата Х i-го источника загрязнения; * координата Y i-го источника загрязнения; * высота i-го источника загрязнения; * диаметр устья устройства выброса i-го источника загрязнения; * нижняя граница диапазона значений объема выбрасываемой газо-воздушной смеси; * верхняя граница диапазона значений объема выбрасываемой газо-воздушной смеси; * нижняя граница диапазона значений мощности выброса j-го загрязняющего вещества i-го источника загрязнения; * верхняя граница диапазона значений мощности выброса j-го загрязняющего вещества i-го источника загрязнения. Величина максимальной приземной концентрации вредных ве- ществ от одиночного источника с круглым устьем для выброса нагретой газо-воздушной смеси при неблагоприятных метеорологи- ческих условиях, расстояния, на котором эта концентрация достига- ется, а также расчеты приземной концентрации в любой точке терри- ториального прямоугольника в зависимости от координат X и Y осуществлялись по стандартной лицензионной методике ОНД-86. Оценка )( ixP  , вероятности того, что источник Ii мог приве- сти к загрязнению выделенной зоны территории Предельные распределения значений концентраций загрязняю- щих веществ от каждого источника загрязнения должны подчинять- 112 ся многомерному нормальному закону: )()( 2 1 2 1 2 1 )2( 1 )( ii T i mxcmx i mi e c xP      , (14.11) где mi – вектор математических ожиданий концентраций загрязня- ющих веществ от источника Ii; m – размерность вектора х; ci – ковариационная матрица векторов концентраций загрязняю- щих веществ; ci -1 – обратная матрица ci; ic – определитель матрицы сi. Для определения элементов ковариационной матрицы использу- ется соотношение:    iN j lk j l j k i kl mmxx N c 1 ) 1 ( . (14.12) Выводы. Разработаны теоретические основы методики определения ви- новников промышленного загрязнения выделенных зон территории по результатам единичных измерений качества окружающей среды. ЛЕКЦИЯ 15 Языки и грамматики Языки состоят из предложений. Предложения должны состав- ляться по правилам языка. Правила языка образуют грамматику языка. Рассмотрим, как определить понятие целого положительного числа с помощью грамматики. 113 Грамматика любого языка представляет собой набор правил, с помощью которых строятся предложения этого языка. Для записи предложений языка используются символы двух типов: символы- понятия и символы-терминалы (не являющиеся понятиями). Так, определим грамматику, раскрывающую понятие целого числа со знаком. ЧИСЛО  ЗНАК ЧИСЛО ЧИСЛО  ЦИФРА ЧИСЛО ЧИСЛО  ЦИФРА ЗНАК  + ЗНАК  - ЦИФРА  0|1|2|3|4|5|6|7|8|9 В этой грамматике понятиями являются ЧИСЛО, ЦИФРА, ЗНАК. Терминальными символами являются +, , 0, 1,2,…,9. Поня- тия раскрываются через другие понятия и терминальные символы, в то время как терминальные символы не раскрываются через иные символы, т.е. являются конечными (первичными) объектами. На вход программы будем подавать цепочки символов, а про- грамма должна выяснить, является ли переданная цепочка числом, определенным согласно грамматике выше, либо нет. Достаточно просто выполнять разбор языка в среде Пролога. Пролог позволяет выполнить кодирование требуемой программы практически напрямую: predicates nondeterm number(string) nondeterm sign(char) nondeterm digit(char) clauses number(X):- frontchar(X,Y,XR), 114 sign(Y), number(XR). number(X):- frontchar(X,Y,XR), digit(Y), number(XR). number(X):- str_char(X,C), digit(C). sign('+'). sign('-'). digit(R):- R='0';R='1';R='2';R='3';R='4';R='5';R='6';R='7';R='8';R='9'. goal number("-99"),write("YES"),readchar(_); write("NO"),readchar(_). Для проверки аналогий возьмем, например, следующее правило грамматики: ЧИСЛО  ЗНАК ЧИСЛО Этому правилу грамматики соответствует следующее правило (clause) языка Пролог: number(X):- frontchar(X,Y,XR), sign(Y), number(XR). Проверке знака (sign) соответствуют правила 115 sign('+'). sign('-'). Правилу грамматики ЧИСЛО  ЦИФРА ЧИСЛО соответствует правило Пролога number(X):- frontchar(X,Y,XR), digit(Y), number(XR). и т.д. Самыми простыми языками являются регулярные языки. Они имеют самые простые наборы правил. Для распознавания регуляр- ных языков можно использовать регулярные автоматы. Эти автома- ты являются также вариантом алгоритмического устройства, т.е. некоторым «видом» машин Тьюринга. По существу, приведенная выше программа на языке Пролог, реализовала программно авто- мат. Удобно правила регулярного автомата представлять в виде сле- дующих формул Qi ak  Qj (15.1) Такое правило читается следующим образом: если автомат нахо- дится в состоянии Qi и поступает символ ak, то автомат переходит в состояние Qj. Подобный набор правил и определяет поведение ав- томата, т.е. задает автомат. Для того чтобы построить таблицу разбора для регулярного ав- томата, достаточно каждому правилу (15.1) сопоставить фрагмент таблицы следующего вида (рис. 15.1): . . . . . . . ak 116 Qi Qj Рис. 15.1 При построении автоматов, распознающих языки, следует состо- яния автомата определять исходя из того, какого рода символы в этом состоянии ожидаются на входе автомата. Снова рассмотрим простой арифметический язык, но допустим, что кроме переменных языка могут встречаться и числовые константы. Пример. a+5*c a-b+c*10-d a Пусть в состоянии Q0 ожидается поступление буквы или число- вой константы. В состоянии Q1 ожидается поступление знака опе- рации. В состоянии Q2 ожидаем поступления цифры или знака опе- рации. Отсюда получаем правила: Q0 буква → Q1 Q1 знак_операции → Q0 Q0 цифра→ Q2 Q2 знак_операции → Q0 Q2 цифра → Q2 Вместе с тем, если ввести в язык скобки, то нельзя реализовать его распознавание с помощью регулярного автомата, поскольку нужно обеспечить распознавание парности открывающих и закры- вающих скобок. Имеет место следующий интересный результат. Теорема. Всякий недетерминированный регулярный автомат можно реализовать с помощью эквивалентного детерминированно- го регулярного автомата. Доказательство теоремы будет проведено на примере требуемой реализации. 117 Пусть имеется табл. 15.1 недетерминированного автомата. Таблица 15.1 a b Q0 Q1,Q2 Q2 Q1 QSTOP Q2 Q2 Q1 QSTOP Недетерминизм автомата определяется наличием клетки (и по- добных ей в других случаях) вида (рис. 15.2): a Q0 Q1,Q2 Рис.15.2 Здесь переход из состояния Q0 под действием одного и того же символа может вести в состояние Q1 или в состояние Q2. Заменим два этих состояния на новое, например, Q3={Q1,Q2}. Теперь табл. 15.1 примет такой вид: Таблица 15.2 a b Q0 Q3 Q2 Q1 QSTOP Q2 Q2 Q1 QSTOP Q3 QSTOP,Q1 QSTOP,Q2 Объясним содержимое строки Q3. Если под действием a перехо- дим из Q0 в Q1, то под действием a из Q1 перейдем в QSTOP. Если под действием a перейдем из Q0 в Q2, то под действием a перейдем из Q2 в Q1. Отсюда получаем ячейку (рис. 15.3) A Q3 QSTOP,Q1 118 Рис. 15.3 Аналогичным образом получаем ячейку в столбце b. Теперь поступаем аналогично. Заменим состояния QSTOP,Q1 на новое – Q4 (табл. 15.3): Таблица 15.3 a b Q0 Q3 Q2 Q1 QSTOP Q2 Q2 Q1 QSTOP Q3 Q4 QSTOP,Q2 Q4 QSTOP Q2 Следует просто заметить, что из QSTOP уже нет выхода. Таким образом, итоговая таблица примет следующий вид (табл. 15.4): Таблица 15.4 a b Q0 Q3 Q2 Q1 QSTOP Q2 Q2 Q1 QSTOP Q3 Q4 Q5 Q4 QSTOP Q2 Q5 Q1 QSTOP Рассмотрим, например, разбор слова aabb. По последней табли- це попадаем в QSTOP. Варианты цепочек для соответствующего недетерминированного автомата таковы: Q0-Q1-QSTOP; Q0-Q2-Q1-Q2-QSTOP. 119 ЛЕКЦИЯ 16 Информационно-диагностическая экспертная медицинская система “Нефрон” Экспертные системы (ЭС) являются одним из ведущих направле- ний в области искусственного интеллекта. Их основным назначением является поддержка поиска решения так называемых интеллектуаль- ных задач (см. далее). ЭС обеспечивают необходимые механизмы для разработки программных средств, которые при решении интеллекту- альных задач дают результаты, сравнимые по качеству и эффектив- ности с решениями, даваемыми экспертами в данной области. В России и других странах СНГ существуют экспертные систе- мы для ортопедии, кардиологии, почечных заболеваний и пр. Их успех определяется степенью точного понимания реальных медико- технических процессов. Системы часто совмещены с мультимедий- ными устройствами. Ряд интеллектуальных систем позволяют учитывать мнение вра- ча (ДИАГЕН), реализуют механизм корректировки "весов" призна- ков, вводят коэффициенты "уверенности" и др. Такие системы обеспечивают варианты решений: "мягкое решение", "жесткий вы- бор", и др. В практике медицины применяется технология имитационного динамического моделирования для диагностики, в частности, электро-вибростимуляции позвоночного столба человека. Ниже приведено описание информационно-диагностической экспертной медицинской системы для диагностирования почечных заболеваний и определения склонности к хронизации болезни (гло- мерулонефрита). Система использует ряд встроенных механизмов и технологий, описанных ранее в этом курсе. Общая технология ре- шения сложных задач диагностирования и принятия решений со- стоит в следующем. 1. Используя механизм логического вывода в системе ЕСЛИ-ТО, получаем отфильтрованное множество заболеваний, на котором предстоит поставить диагноз. Это отфильтрованное множество вы- 120 бирается из базы данных, в которой хранятся сведения по всем бо- лезням, с зарегистрированными эпикризами. 2. На основе систем многокритериальной оценки поступивший больной оценивается по множеству показателей (функциональных подсистем, таких как кровь, лимфа, мочеполовая система, сердце и легкие, кожа и др.) 3. Полученная комплексная оценка используется для оценки ве- роятности хронизации заболевания. Важность распознавания хронизации болезни на ранних этапах существенна при выборе схемы лечения. Таким образом, решаемая системой задача приобретает очевидный практически значимый характер. ПРОБЛЕМА ДИАГНОСТИРОВАНИЯ В ЭС Байесовская стратегия постановки диагнозов Постановка диагноза  это сложный процесс, связанный с реше- нием так называемой интеллектуальной задачи. Интеллектуальная задача характеризуется следующими признаками [8-10]:  нечеткая постановка или неполнота исходных данных задачи;  отсутствие точного алгоритма решения задачи;  огромное число возможных исходов;  невозможность формализации задачи;  существенное использование эвристических и приближенных методов;  наличие экспертов в области задачи. Легко видеть, что задачи (медицинской) диагностики вполне удовлетворяют этим признакам. Поэтому для решения таких задач используют современные технологии инженерии знаний, главным образом  экспертные системы (ЭС). Наиболее широкое распространение подобные технологии получи- ли в тех медицинских учреждениях, где к точности постановки диа- гноза предъявляются повышенные требования, например, в невропа- тологии и нейрохирургии, сердечной и почечной патологии и т.д. Для математического решения проблемы диагностики в настоя- 121 щее время наиболее широко применяют три группы методов:  статистические;  логические;  нечеткие. Каждая из этих групп методов имеет свои достоинства и недо- статки. Следует заметить, что логические методы предполагают знание точных причинно-следственных связей на множестве при- знаков и причин заболеваний. Это является существенным ограни- чением, поскольку многие признаки являются размытыми или об- щими для нескольких заболеваний. Поэтому применение логиче- ских методов либо не всегда оправдано, либо невозможно. Естественным поэтому является использование математических методов, использующих вероятностные или нечеткие методологи- ческие принципы. Если рассматривать нечеткий подход к диагностике, то его целесо- образность связана с теми ситуациями, когда нельзя сделать статисти- ческие выводы, например, не известно распределение, которому под- чиняется тот или иной признак, либо статистика собрана в недостаточ- ном объеме, либо собранные данные недостоверны. Такие ситуации вполне могут иметь место на практике. Однако в большинстве случаев медицинское учреждение располагает накопленными данными из анамнезов пациентов, по которым можно провести качественную диа- гностику, базируясь на статистических методах. Пусть необходимо производить диагностику между заболевани- ями D1, D2,…, Dn . Для каждого из этих заболеваний известны условные вероятности )|( jDSP , характеризующие появление набора симптомов S при заболевании Dj. Здесь S = { S1 , S2 ,…, Sk } и Sk – различные симптомы. Пусть далее P(Dm)  априорная веро- ятность заболевания Dm. Тогда задача дифференциальной диагно- стики может быть сведена к статистической задаче выбора гипотез, решение которой основывается на использовании известной теоре- мы Байеса: 122 ∑ 1 )|()( )|()( )|( n j jj jj j DSPDP DSPDP SDP     (16.1) Если для какого-нибудь диагноза Dj рассчитанная вероятность (16.1) значительно превосходит значение этой вероятности для дру- гих диагнозов, то оптимальное правило приписывает больному за- болевание Dj . Использование формулы (16.1) встречается со следующими трудностями: если априорные вероятности P(Dm) можно сравни- тельно просто определить из базы данных пациентов медицинского учреждения, то условные вероятности )|( jDSP можно сравни- тельно легко вычислить лишь при небольшом числе признаков S1, S2 ,…, Sk. Во-первых, это может быть связано с тем, что число раз- личных комбинаций признаков может быть гигантским. Например, если каждый симптом имеет только 2 различных значения (ДА/НЕТ) и число симптомов равно 30, то число всех возможных симптомокомплексов может исчисляться величиной 230. Не спасает ситуации даже столь важное предположение, что признаки являют- ся взаимно независимыми. При этом допущении знаменатель    n j jj DSPDP 1 )|()( вычисляется по упрощенной формуле:    n j jkjjj n j jj DSPDSPDSPDPDSPDP 1 21 1 )|(...)|()|()()|()(∑ Однако и теперь может иметь место случай, когда в базе данных ранее не наблюдалась ситуация )|( jα DS , так что получаем в знамена- теле 0, и, следовательно, формула Байеса становится неприменимой. 123 Таким образом, перед нами стоит следующая проблема: усовер- шенствовать механизм диагностирования на основе байесовского разрешающего правила при следующих допущениях:  число различных симптомов велико (десятки-сотни)  симптомы считаются независимыми  возможны ситуации, при которых нет сведений по симптому S для диагноза Dj. Пример расчетов. Пусть по данным статистики при заболева- нии D1 признак S1 встречается в 75% случаев, признак S2 не встре- чается, признак S3 наблюдается в 10% случаев, а S4  в 40%; дан- ные по встречаемости признаков при заболевании D2 таковы: S1  10%, S2  10%, S3  50% , S4  5%; данные по встречаемости при- знаков при заболевании D3 таковы: S1  15%, S2  10%, S3  90% , S4  70% . Эти данные можно представить следующей табл. 16.1. Таблица 16.1 Dj P(Dj) )|( 1 jDSP )|( 2 jDSP )|( 3 jDSP )|( 4 jDSP D1 0.3 0.75 0 0.1 0.4 D2 0.1 0.1 0.1 0.5 0.05 D3 0.6 0.15 0.1 0.9 0.7 Пусть известно, что у пациента имеется признак S1 и признак S2, а признаки S3 и S4 отсутствуют. Считая признаки независимыми, определим вероятности диагнозов. Так, если признак S при диагно- зе D отсутствует, то рассчитываем вероятность )|( βα DSP по формуле )|( -1=)|( βαβα DSPDSP (16.2) 124 ∑ ∑ ∑ )|,,,(*)( ))|(-1(*))|(-1(*)|(*)|(*)( )|,,,(*)( )|(*)|(*)|(*)|(*)( )|,,,()( )|,,,()( ),,,|( 4321 141312111 4321 141312111 4321 143211 43211 jj jj jj DSSSSPDP DSPDSPDSPDSPDP DSSSSPDP DSPDSPDSPDSPDP DSSSSPDP DSSSSPDP SSSSDP      Непосредственно определяем 0 0.7)-(1*0.9)-(1*0.1*0.15*0.6 0.05)-(1*0.5)-(1*0.1*0.1*0.10.4)-(1*0.1)-(1*0*0.75*0.3 0.4)-(1*0.1)-1(*0*75.0*3.0 ),,,|( 43211    SSSSDP 65.0 0.7)-(1*0.9)-(1*0.1*0.15*0.6 0.05)-(1*0.5)-(1*0.1*0.1*0.10.4)-(1*0.1)-(1*0*0.75*0.3 0.05)-(1*0.5)-(1*0.1*0.1*0.1 ),,,|( 43212    SSSSDP 35.0 0.7)-(1*0.9)-(1*0.1*0.15*0.6 0.05)-(1*0.5)-(1*0.1*0.1*0.10.4)-(1*0.1)-(1*0*0.75*0.3 0.7)-(1*0.9)-(1*0.1*0.15*0.6 ),,,|( 43213    SSSSDP Таким образом, следует выдвинуть гипотезу как о наиболее ве- роятном диагнозе D2. В данном примере рассматривается про- странство элементарных событий {D1, D2, D3}, любые два из кото- рых не могут произойти одновременно и одно из этих событий непременно имеет место. Это является упрощающим допущением, 125 поскольку возможны в принципе исходы с двумя и более одновре- менно присутствующими заболеваниями, а также исход, в котором нет ни одного из указанных диагнозов. Следовательно, в общем случае подлежат расчету следующие вероятности: ),,,|( ),,,|( ),,,|( ),,,|( ),,,|( ),,,|( ),,,|( ),,,|( 4321321 4321321 4321321 4321321 4321321 4321321 4321321 4321321 SSSSDDDP SSSSDDDP SSSSDDDP SSSSDDDP SSSSDDDP SSSSDDDP SSSSDDDP SSSSDDDP Опять же и в этом случае используется упрощающее допущение, что диагнозы не зависят друг от друга, так что, например, допускаем правомерным использование следующего расчетного соотношения: ),,,|( 4321321 SSSSDDDP  ),,,|(),,,|( 4321243211 SSSSDPSSSSDP (16.3) ).,,,|( 43213 SSSSDP На практике, однако, формула (16.3) не находит применения, по- скольку при постановке диагноза эксперта интересует, верно ли предположение о конкретном диагнозе (заболевании) вне зависимо- сти от его сочетания с другими возможными заболеваниями. 126 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1. Герман, О.В. Экспертные системы: учебно-методическое пособие / О.В. Герман.  Минск: БГУИР, 2008. – 91 с. 2. Герман, О.В. Экспертные системы: лабораторный практикум / О.В. Герман, Н.В. Батин. – Минск: БГУИР, 2003. 3. Чень, Ч. Математическая логика и автоматическое доказатель- ство теорем / Ч. Чень, Р. Ли. – М.: Наука, 1983. – 358 с. 4. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон.  М.: Мир, 1982. – 600 с. 5. Дюбуа, Д. Теория возможностей / Д. Дюбуа, А. Прад. – М.: Радио и связь, 1990.  288 с. 6. Герман, О.В. Система вывода для нечеткой логики на основе многозначных исчислений Лукасевича / О.В. Герман, И.Г. Блохина, Ю.О. Герман // Актуальные проблемы гуманитарных и естественных наук.  2010.  № 6.  C. 3538. 7. Гиндикин, С.Г. Алгебра логики в задачах / С.Г. Гиндикин.  М.: Наука, 1972.  286 с. 8. Уотермен, Д. Руководство по экспертным системам / Д. Уотер- мен. – М.: Мир, 1989. 9. Построение экспертных систем / под ред Ф. Хейес-Рота. – М.: Мир, 1987. 10. Герман, О.В. Введение в теорию экспертных систем и обра- ботку знаний / О.В. Герман. – Минск: Дизайн-Про, 1995. – 256 c. 127 Учебное издание ГЕРМАН Олег Витольдович ГЕРМАН Юлия Олеговна ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ Методическое пособие для студентов специализации 1-40 01 02-01 «Информационные системы и технологии в проектировании и производстве» Технический редактор О.В. Песенько Компьютерная верстка А.Г. Занкевич Подписано в печать 31.01.2012. Формат 60841/16. Бумага офсетная. Отпечатано на ризографе. Гарнитура Таймс. Усл. печ. л. 7,38. Уч.-изд. л. 5,77. Тираж 100. Заказ 1005. Издатель и полиграфическое исполнение: Белорусский национальный технический университет. ЛИ № 02330/0494349 от 16.03.2009. Проспект Независимости, 65. 220013, Минск.