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

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

Во второй главе было также рассмотрено применение концепции поиска в пространстве состояний на примере игры в 8, тоже ориентированное на использование эвристической оценочной функции эффективности ходов. Для вычисления "перспективности" вершин можно применить, например, следующую оценочную функцию. Обозначим эту функцию символом f. Тогда f(n) будет давать ее значение в вершине n дерева поиска. Будем считать, что вершина дерева с меньшей оценкой имеет большую вероятность оказаться на оптимальном пути. Тогда в качестве оценочной функции можно взять выражение f(n) = d(n) + W(n), где d(n) -глубина вершины n на дереве поиска и W(n) - число не находящихся на нужном месте клеток в базе данных, связанной с вершиной n. Таким образом, в процессе поиска варианты его продолжения следует рассматривать в порядке возрастания значения функции f(n). Использование этого правила будет способствовать сокращению среднего числа ходов, затрачиваемых на решение задачи.

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

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

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

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

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

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

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

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

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

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

Поиск в факторизуемых пространствах. Пространство поиска называют факторизуемым, если оно разбивается на непересекающиеся подпространства (области поиска, классы) частичными (неполными) решениями. Примерами действующих систем, в которых реализован этот способ поиска, являются системы Heuristic DENDRAL и Meta-DENDRAL, предназначенные для определения структуры химических молекул по масс-спектрограммам. Необходимость в создании этих систем обусловлена тем, что человеку очень трудно представить себе по масс-спектру структуру молекулы, включающей от 100 до 300 элементов.

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

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

Многие из правил-продукций планировщика весьма эффективно сужают область поиска, не только ограничивая поиск типом соединения, но и количественными характеристиками. Например, знание о том, что спектр содержит 8С, 16Н, 1О, сокращает число возможных структур с 698 до 3, так как в список BADLIST будут занесены все структуры, кроме содержащих "этил-кетон-3".

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

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

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

Ассоциативный и каузальный поиск решения. Основные замечания в адрес систем MYCIN и PROSPECTOR состояли в следующем:

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

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

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

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

Система INTERNIST разработана в Питтсбургском университете (США). Прототип создан в 1974 г. и с тех пор совершенствуется и используется. Создана и новая версия этой системы (CADUCEUS). Одно из замечательных свойств этой системы состоит в том, что процесс постановки диагноза явно приближается к модели человеческого мыслительного процесса, позволяя тем самым установить взаимосвязь между конкретными болезнями (причинами) и их проявлениями. INTERNIST решает только задачу постановки диагноза, но не лечения. Процесс постановки диагноза включает две стадии:

а) ограничение пространства диагностирования путем выбора правдоподобных гипотез о возможных заболеваниях ("дифференциальная модель диагностирования");

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

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

Знания о заболеваниях в INTERNIST представлены деревом заболеваний (его фрагмент показан на рис. 4.5). Уровни дерева заболеваний связаны между собой отношением тип-разновидность.

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

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

а) симптомы наблюдаемые, но не относящиеся к заболеванию;

б) симптомы не зарегистрированные, но которые должны быть;

в) симптомы наблюдаемые и относящиеся к заболеванию;

г) симптомы ожидаемые, но не зарегистрированные.

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

Система CASNET (Causal ASsociational NETwork) разработана в первой половине 70-х годов в Рутгерском университете (США) для исследования стратегий диагностирования на основе психологических и функциональных моделей заболеваний. В качестве предметной области при разработке этой системы была выбрана глаукома из-за ее локальности и относительной структурной простоты.

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

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

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

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

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

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

Примененный в системе CASNET подход имеет ряд своих преимуществ:

а) представление процесса заболевания в явном виде позволяет отслеживать состояния пациента в процессе заболевания и, значит, анализировать реакции на лечение;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подход на основе условных вероятностей.

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

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

Примем для дальнейших рассуждений следующие обозначения:

- априорная вероятность истинности гипотезы H (от англ. Hypothesis - гипотеза);

- апостериорная вероятность истинности гипотезы Н при условии, что получено свидетельство Е (от англ. Evidence - свидетельство);

- вероятность получения свидетельства Е при условии, что гипотеза Н верна;

- вероятность получения свидетельства E при условии, что гипотеза Н неверна.

По определению условных вероятностей имеем

и

Учитывая, что = , получаем теорему Байеса

Так как = + и =1- , получаем формулу, позволяющую уточнять вероятность истинности проверяемой гипотезы Н с учетом полученного свидетельства Е

.

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

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

Шансы и вероятности связаны между собой следующей формулой

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

Переходя к шансам в рассмотренных нами формулах, получим

.

Если же перейти к логарифмам величин, а в базе знаний хранить логарифмы отношений Р(Е:Н)/Р(Е:неН), то все вычисления сводятся просто к суммированию, поскольку

= + .

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

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

Первое замечание касается возможности вычисления величины . Эту величину легко определить, если есть возможность вычислить , а это не всегда можно сделать (например, можно подсчитать вероятность наличия температуры у пациента при наличии гриппа, но как определить вероятность наличия температуры у пациента при отсутствии гриппа?).

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

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

Подход с использованием коэффициентов уверенности.

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

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

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

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

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

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

Коэффициенты уверенности для правила с одной посылкой. В данном случае речь идет о вычислении коэффициентов уверенности для правил вида Е>С ("если Е то С").

Если иметь возможность присваивать коэффициент уверенности как посылке, так и импликации, то их можно использвать для оценки степени определенности заключения, выводимого по данному правилу. Шортлифф применяет в данном случае коэффициенты уверенности подобно вероятностям: коэффициент уверенности ct(E) в посылке подобен p(E); коэффициент уверенности сt(Е>С) в импликации подобен p(C:E). Для определения коэффициента уверенности в заключении Шортлифф использует схему: ct(посылка) ct(импликация) = ct(заключение).

Пример: "если вы обучались в ТПУ, то вы прекрасный специалист". Неопределенность здесь имеет место как в посылке (обучался еще не значит, что обучился), так и в импликации (не всякий, кто даже обучился, становится прекрасным специалистом).

Логические комбинации посылок в одном правиле. Посылкой в правиле считается все, что находится между если и то. В MYCIN избран принцип: делать все правила простыми. Тогда простейшими логическими комбинациями посылок являются их конъюнкия или дизъюнкция, т.е. правила вида

или .

Коэффициент уверенности конъюнкции посылок в MYCIN принято оценивать по наименее надежному свидетельству

.

Соответственно, коэффициент уверенности дизъюнкции посылок в MYCIN принято оценивать по наиболее надежному свидетельству

.

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

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

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

.

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

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

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

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

Пусть - степень поддержки i-м правилом заключения С, i = 1,2,…,n. Пусть также . Тогда степень совместной поддержки заключения С всеми n правилами можно вычислить по формуле

согласно которой величина ct равна площади квадрата (т.е. равна1) за вычетом ее части , не входящей ни в один из овалов.

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

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

Биполярные схемы для коэффициентов уверенности. Коэффициенты уверенности, примененные в MYCIN, представляют собой грубое подобие вероятностей. В усовершенствованной системе EMYCIN для выражения степени определенности использован интервал [-1,+1] в следующем смысле:

+1 - полное доверие посылке или заключению;

0 - отсутствие знаний о посылке или заключении;

-1 - полное недоверие посылке или заключению.

Промежуточные значения выражают степень доверия или недоверия к ситуации. Все описанные для однополярных коэффициентов процедуры здесь тоже имеют место, но при вычислении max и min учитываются знаки при величинах коэффициентов (например, что +0,1 > -0,2). Биполярность коэффициентов повлияла и на вид используемых формул.

Так, для вычисления коэффициента уверенности отрицания посылки достаточно лишь поменять знак коэффициента, т.е. ct(неЕ) = -ct(E).

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

а) если оба коэффициента положительны, то

б) если оба коэффициента отрицательны, то

;

в) если один из коэффициентов положителен, а другой отрицателен, то

при этом, если один из коэффициентов равен +1, а другой -1, то ct = 0.

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

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

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

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

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

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

"если вам меньше 8 лет или больше 60 лет, то с уверенностью 0.7 можно заключить, что у вас уязвимый возраст";

"если у вас грипп и не уязвимый возраст, то с уверенностью 0.4 можно заключить, что вам следует принять аспирин и лечь в постель";

"если у вас острый фарингит, то с уверенностью 1.0 можно заключить, что вам следует вызвать врача".

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

На рис. 3.3 сплошными стрелками указаны условия без отрицания, а пунктирными - с отрицанием; жирными стрелками отмечены обратимые (реверсивные) правила, а стрелками обычной толщины - необратимые (нереверсивные); числа в прямоугольниках жирным шрифтом - это коэффициенты уверенности в свидетельствах (Evidence), а обычным шрифтом - это вычисленные по правилам коэффициенты уверенности в соответствующих заключениях (Conclusion); надписи min и max обращают внимание на то, что операции конъюнкция (&) и дизъюнкция ( ) в нечеткой логике означают выбор соответственно наименьшего и наибольшего элемента.

Процесс вычислений идет снизу (от свидетельств Е1, Е2, Е3, Е4, Е5) вверх (к заключению С5).

Коэффициент увереннности в С1 определяется через простую необратимую импликацию, но коэффициент уверенности в Е1 положителен и правило можно применять:

ct(C1) = 0,9*0,8 = 0,72.

Заключение С2 поддерживают два обратимых правила, дающих коэффициенты уверенности с разным знаком, поэтому их объединение осуществляется по формуле для этого случая

(C2) = 0,9*0,9 = 0,81;

(C2) = -0,3*0,7 = -0,21;

ct(C2) = (0,81 - 0,21) / (1 - 0,21) = 0,74.

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

ct(C3) = 0,3*0,5 = 0,15.

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

ct(C2&C3) = min{ct(C2); ct(C3)} = min{0,15;0,74} = 0,15.

Cледовательно, ct(C4) = 0,15*0,9 = 0,13.

Заключение С5 поддерживается дизъюнкцией посылок, поэтому из них выбирается посылка с наибольшим коэффициентом уверенности:

ct(C1 C4) = max{ct(C1); ct(C4)} = max{0,72;0,13} = 0,72.

следовательно, сt(C5) = 0,72*0,8 = 0,58.

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

Нечеткая логика Заде.

Нечетким множеством , по Лотфи Заде, называется множество, определенное на произвольном непустом множестве Х как множество пар вида

={A(x)/x}

где xX, A(x)[0,1].

Множество Х называется базовым множеством, или базовой шкалой (если множество Х линейно упорядочено). Функция ?A(x) : Х ? [0,1] называется функцией принадлежности множества . Величина ?A(x) для каждого конкретного x?X называется степенью принадлежности элемента х нечеткому множеству . Принято, что в нечеткое множество не входят элементы x?X, имеющие ?A(x) = 0. Подмножество А?Х, содержащее все те элементы x?X, для которых ?A(x) > 0, называется носителем нечеткого множества .

Пример. В рейтинговой системе оценки знаний по каждой дисциплине задается некоторая базовая шкала баллов (обычно используется шкала [0,1000]), на которой задаются интервалы, дающие студенту право на получение оценки "неудовлетворительно", "удовлетворительно", "хорошо", "отлично". Фактически эти интервалы выступают в качестве носителей нечетких множеств "неудовлетворительно", "удовлетворительно", "хорошо", "отлично", так как за разные баллы из одного и того же интервала преподаватель ставит одну и ту же оценку с разной степенью уверенности. На рис.3.4 приведены графики функций принадлежности оценок, характеризующие степень уверенности некоторого преподавателя в оценке знаний студента по дисциплине, в зависимости от величины набранного им по рейтингу балла.

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

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

Мера истинности нечеткого высказывания определяется функцией принадлежности A(x), xX, заданной на множестве Х = {"ложь", "истина"}.

При таком определении нечеткого высказывания несомненно истинное высказывание характеризуется функцией принадлежности A("истина") = 1 (или A("ложь") = 0). Соответственно несомненно ложное высказывание будет характеризоваться функцией принадлежности A("истина") = 0 (или функцией A("ложь") = 1). Нечеткие высказывания, характеризующиеся равной степенью уверенности и сомнения (т.е. когда A("истина") = 0.5 и A("ложь") = 0.5), называют нечетко индифферентными.

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

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

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

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

Отрицанием нечеткого высказывания называется нечеткое высказывание ¬ , степень истинности которого определяется выражением ¬ = 1 - . Отсюда следует, что степень ложности ¬ равна степени истинности .

Конъюнкцией нечетких высказываний и называется нечеткое высказывание & , степнь истинности которого определяется выражением & =min( , ), т.е. есть степень истинности нечеткого высказывания & определяется наименее истинным высказыванием.

Дизъюнкцией нечетких высказываний и называется высказывание ( ), степень истинности которого определяется выражением ( )=max( , ). То есть степень истинности нечеткого высказывания () определяется наиболее истинным высказыванием.

Импликацией нечетких высказываний и называется нечеткое высказывание , степень истинности которого определяется выражением =max(1- , ).

Данное выше определение импликации основано на логической равносильности формулы и формулы ¬ .

Эквиваленцией (эквивалентностью) нечетких высказываний и называется нечеткое высказывание , степень истинности которого определяется выражением В=min(max(1- , ),max( ,1- )). Данное определение эквиваленции основано на равносильности формулы формуле ( ) &( ).

Нечеткие высказывания и называются нечетко близкими, если 0.5 (т.е.степень эквивалентности высказываний не ниже 0.5), нечетко индифферентными, если =0.5, и нечетко неблизкими, если 0.5.

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

Пример. Вычислите степень истинности составного нечеткого высказывания при условии, что входящие в него простые нечеткие высказывания имеют значения степеней истинности =0.7, =0.4, =0.9, а формула =( &¬ ¬ & ) ¬( & ). Если вы правильно используете определения логических операций над нечеткими высказываниями и будете следовать принятому порядку их применения при отсутствии скобок, то вы получите =0.4.

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

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

Нечеткие логические формулы и их свойства. Нечеткое высказывание, степень истинности которого может принимать произвольное значение из интервала [0,1], Заде называет нечеткой логической переменной. В определении понятия нечеткой логической формулы логические переменные и их значения (константы из интервала [0,1]) считаются простейшими нечеткими логическими формулами, а само понятие нечеткой логической формулы вводится индуктивно.

Нечеткой логической формулой называется:

а) нечеткая логическая переменная или константа из интервала [0,1];

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

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

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

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

Понятие равносильности нечетких логических формул

( , ,…, ) и ( , ,…, )

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

Степень равносильности ( , ) двух формул

( , ,…, ) и ( , ,…, )

определяется выражением

Формулы и называют: нечетко равносильными, если (, ) 0.5 (пишут ); взаимно нечетко индифферентными, если (, ) = 0.5 (пишут ); нечетко неравносильными, если (, ) 0.5 (пишут ).

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

( , ) = ( ) и ( , ) = ( & )

степень равносильности которых при {0,8; 0,6; 0,7} и {0,3; 0,4} равна 0,6.

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

Тема 4 Нейронные сети. Основные понятия об естесвенных и искуственных нейронных сетях и нейронах. Классификация нейронных сетей. Программная и аппаратная реализация нейронных сетей

Использование нечетких знаний в моделях нейронных сетей. Основные понятия теории нейронных сетей

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

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

Нейрон мозга имеет четыре основные части (рис. 6.1): тело, входные каналы, выходной канал и соединительные точки между нейронами, называемые синапсами.



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

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

...