Введение в искусственный интеллект.Введение в представление знаний.Продукционные правила.    

ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ – АНОО ВПО Факультет информационных технологий Кафедра информационных систем и технологий Н.В. Акамсина ЛЕКЦИИ по дисциплине «Представление знаний в информационных системах» для студентов очной формы обучения по направлению 230100 «Информатика и вычислительная техника» Воронеж 2009 Лекция 1. Введение в искусственный интеллект 1. История развития искусственного интеллекта. 2. Основные направления искусственного интеллекта. 1. История развития искусственного интеллекта Идея искусственного подобия человека для решения сложных задач и моделирования человеческого разума витала в воздухе еще в древнейшие времена. Так, в древнем Египте была создана «оживающая» механическая статуя бога Амона. У Гомера в «Илиаде» бог Гефест ковал человекоподобные существа – автоматы. Однако родоначальником искусственного интеллекта (ИИ) считается средневековый испанский философ, математик и поэт Раймонд Луллий, который еще в XIII веке попытался создать механическую машину для решения различных задач, на основе разработанной им всеобщей классифика­ции понятий. В XVIII веке Лейбниц и Декарт независимо друг от друга продолжили эту идею, предложив универсальные языки классификации всех наук. Эти работы можно считать первыми теоретическими работами в области искусственного интеллекта. Окончательное рождение искусственного интеллекта, как научного направления, произошло только после создания ЭВМ в 40-х годах ХХ века. В это же время Норберт Винер создал свои основополагающие работы по новой науке – кибернетике. Термин “искусственный интеллект” был впервые предложен в 1956 г. на семинаре с аналогичным названием в Дартмутском колледже (США). В нашей стране началом исследований в направлении искусственного интеллекта принято считать семинар “Автоматы и мышление”, начавший свою работу в МГУ в 1954 г. под руководством академика Ляпунова А.А. Впоследствии, в 60-80х годах исследования в области искусственного интеллекта происходили в рамках школы ситуационного управления, основателем которой был проф. Поспелов Д.А. В 1974 году при Комитете по системному анализу при президиуме АН СССР был создан Научный совет по проблеме “Искусственный интеллект”. В 1988 г. была создана АИИ – Ассоциация искусственного интеллекта, членами которой являются более 300 исследователей. В рамках Ассоциации проводится большое количество исследований, организуются школы для молодых специалистов, семинары, симпозиумы, издается научный журнал. Исторически сложились три основных подхода в моделировании ИИ. В рамках первого подхода объектом исследований являются структура и механизмы работы мозга человека, а конечная цель заключается в раскрытии тайн мышления. Необходимыми этапами исследований в этом направлении являются построение моделей на основе психофизиологических данных, проведение экспериментов с ними, выдвижение новых гипотез относительно механизмов интеллектуальной деятельности, совершенствование моделей и т. д. Второй подход в качестве объекта исследования рассматривает ИИ. Здесь речь идет о моделировании интеллектуальной деятельности с помощью вычислительных машин. Целью работ в этом направлении является создание алгоритмического и программного обеспечения вычислительных машин, позволяющего решать интеллектуальные задачи не хуже человека. Наконец, третий подход ориентирован на создание смешанных человеко-машинных, или, как еще говорят, интерактивных интеллектуальных систем, на симбиоз возможностей естественного и искусственного интеллекта. Важнейшими проблемами в этих исследованиях является оптимальное распределение функций между естественным и искусственным интеллектом и организация диалога между человеком и машиной. 2. Основные направления искусственного интеллекта В настоящее время в исследованиях по искусственному интеллекту выделились шесть основных направлений: 1. Представление знаний. В рамках этого направления решаются задачи, связанные с формализацией и представлением знаний в памяти системы ИИ. Для этого разрабатываются специальные модели представления знаний и языки описания знаний, внедряются различные типы знаний. Проблема представления знаний является одной из основных проблем для системы ИИ, так как функционирование такой системы опирается на знания о проблемной области, которые хранятся в ее памяти. 2. Манипулирование знаниями. Чтобы знаниями можно было пользоваться при решении задачи, следует научить систему ИИ оперировать ими. В рамках данного направления разрабатываются способы пополнения знаний на основе их неполных описаний, создаются методы достоверного и правдоподобного вывода на основе имеющихся знаний, предлагаются модели рассуждений, опирающихся на знания и имитирующих особенности человеческих рассуждений. Манипулирование знаниями очень тесно связано с представлением знаний, и разделить эти два направления можно лишь условно. 3. Общение. В круг задач этого направления входят: проблема понимания и синтеза связных текстов на естественном языке, понимание и синтез речи, теория моделей коммуникаций между человеком и системой ИИ. На основе исследований в этом направлении формируются методы построения лингвистических процессов, вопросно-ответных систем, диалоговых систем и других систем ИИ, целью которых является обеспечение комфортных условий для общения человека с системой ИИ. 4. Восприятие. Это направление включает разработку методов представления информации о зрительных образах в базе знаний, создание методов перехода от зрительных сцен к их текстовому описанию и методов обратного перехода, создание средств для порождения зрительных сцен на основе внутренних представлений в системах ИС. 5. Обучение. Для развития способности систем ИИ к обучения, т.е. к решению задач, с которыми они раньше не встречались, разрабатываются методы формирования условий задач по описанию проблемной ситуации или по наблюдению за ней, методы перехода от известного решения частных задач (примеров) к решению общей задачи, создание приемов декомпозиции исходной задачи на более мелкие и уже известные для систем ИИ. В этом направлении ИИ сделано еще весьма мало. 6. Поведение. Поскольку системы ИИ должны действовать в некоторой окружающей среде, то необходимо разрабатывать некоторые поведенческие процедуры, которые позволили бы им адекватно взаимодействовать с окружающей средой, другими системами ИИ и людьми. Это направление в ИИ разработано очень слабо. Прямо или косвенно проблемы искусственного интеллекта затрагивают следующие области научной и практической деятельности: • системы, основанных на знаниях (экспертные системы) • естественно-языковые и интеллектуальные интерфейсы и машинный перевод; • анализ данных (data mining) и поиск закономерностей в хранилищах данных; • системы поддержки принятия решений; • системы прогнозирования • распознавание речи и образов; • нейроинформатика и нейронные сети; • генетические алгоритмы; • многоагентные системы; • нечеткая логика и мягкие вычисления. Вопросы для самоконтроля: 1. Дайте определение, что такое искусственный интеллект? 2. Перечислите шесть основных направлений в развитии искусственного интеллекта? 3. Что представляет собой направление – Представление знаний? 4. Что представляет собой направление – Манипулирование знаниями? 5. Что представляет собой направление – Общение? 6. Что представляет собой направление – Восприятие? 7. Что представляет собой направление – Обучение? 8. Что представляет собой направление – Поведение? Лекция 2. Введение в представление знаний. 1. Основные понятия. 2. Классификация знаний. 3. Основы инженерии знаний. 1. Основные понятия Представление знаний является одним из важнейших разделов искусственного интеллекта. Искусственный интеллект как научное направление связан с попыткой формализовать мышление человека – разработать методы, которые позволили бы запрограммировать машину таким образом, чтобы она могла воспроизводить или даже превосходить способности человеческого интеллекта. Исследования в этой области тесно связаны со смежными дисциплинами – информатикой, лингвистикой, психологией и философией. Существуют разные точки зрения на главное предназначение исследований. Некоторые ученые склоняются к тому, что искусственный интеллект является ответвлением технических наук. Подход с точки зрения информатики. Другие делают акцент на изучении механизмов познания, процессов обработки информации в мозге человека (нейробионики). Так или иначе, основными понятиями дисциплины являются понятия, связанные с процессами восприятия и обработки информации. Информация с точки зрения ее возникновения и совершенствования проходит следующий путь: человек наблюдает некоторый факт окружающей действительности, это факт отражается в виде совокупности данных, при последующем структурировании в соответствии с конкретной предметной областью данные превращаются в знания. Таким образом, верхним уровнем информации как результата отражения окружающей действительности (результата мышления) являются знания. Знания возникают как итог теоретической и практической деятельности. Информация в виде знаний отличается высокой структурированностью, что позволяет выделить полезную информацию при анализе окружающих нас физических, химических и прочих процессов и явлений. Обобщая вышесказанное, можем теперь дать основные определения в области искусственного интеллекта: • Информация – совокупность любых сведений о каком-либо событии, сущности, процессе и т.п., являющихся объектом некоторых операций: восприятия, передачи, преобразования, хранения или использования. • Данные – фиксированная в определенной форме информация об объектах предметной области, их свойствах и взаимосвязях, отражающих события и ситуации в этой области. • Предметная область – это сфера деятельности человека, в рамках которой осуществляется интерпретация получаемой и обрабатываемой информации. • Знания – это закономерности предметной области (принципы, связи, законы), полученные в результате практической деятельности и профессионального опыта, позволяющие специалистам ставить и решать задачи в этой области. На основе структурированной информации формируется информационная модель объекта. 2. Классификация знаний Знания могут быть классифицированы на следующие категории: • Поверхностные – знания о видимых взаимосвязях между отдельными событиями и фактами в предметной области. • Глубинные – абстракции, аналогии, схемы, отображающие структуру и природу процессов, протекающих в предметной области. Эти знания могут использоваться для прогнозирования поведения объекта. Например, поверхностные знания могут быть описаны следующим предложением: «Если болит голова, то следует выпить аспирин». При этом можно также рассмотреть глубинные знания: «Знания физиологов и врачей высокой квалификации о причинах, видах головных болей и методах их лечения». Знания, которыми обладает человек, делятся на формализованные (точные) и слабо формализованные (неточные). Формализованные знания можно зафиксировать в виде определений, формул, алгоритмов, моделей и т.п. Неформализованные знания – это знания, для которых отсутствует алгоритм (модель, метод) их получения. Эти знания трудно сформулировать, так как они, как правило, являются результатом обобщения многолетнего опыта человека. Например, мы не всегда можем ответить: почему мы приняли то или иное решение, говорим, что оно пришло на интуитивном уровне. 3. Основы инженерии знаний Инженерия знаний – достаточно молодое направление искусственного интеллекта, появившаяся тогда, когда практические разработчики столкнулись с весьма нетривиальными проблемами трудности «добычи» и формализации знаний. Инженерия знаний напрямую связана с проектированием баз знаний, т.е. получению и структурированию знаний специалистов для последующей разработки интеллектуальных информационных систем (ИИС). Для БЗ характерны информационные массивы небольшого объема (в отличие от баз данных) являющиеся исключительно дорогими. В базе знаний можно проводить выбор по запросу информации, явно не хранимой, а выводимой из имеющихся данных. Базы знаний используются для хранения знаний и построения на их основе ИИС. Для этого знания необходимо представить в форме, понятной компьютеру. Таким образом, идеология создания базы знаний в основном связана с формализацией знаний (или памяти человека). Модели памяти разрабатываются когнитивной психологией. Когнитивная психология (психология познания) занимается, прежде всего, изучением способов восприятия и понимания знаний человеком. Процесс представления знаний представляет собой формализацию знаний об определенной области. В конечном итоге, знания должны быть представлены в форме, которая будет пригодна для создания интеллектуальной системы. Таким образом, необходимо создание определенных схем, позволяющих описать знания на некотором формальном языке. Выделяют декларативные и процедурные знания. Декларативные знания хранятся в виде фактов и утверждений об объектах и отношений между этими объектами. К моделям представления таких знаний относятся, предикаты, семантические сети, фреймы. Процедурные знания хранятся в процедурах и выводятся в виде алгоритмов. К моделям их представления относятся правила продукции. Особенности, присущие некоторым слабоструктурированным задачам, такие, как разнородность информации, неполнота и неопределенность исходных данных и т.д. делают привлекательным использование качественных знаний. Для их формализации используются методы нечеткой математики. Извлечение знаний – это процедура взаимодействия специалиста с источником знаний, в результате которой становится явным процесс рассуждений специалиста при принятии решения и структура его представления о предметной области. Условно этот процесс включает можно разбить на три этапа: 1. Формулировка проблемы – определение целей и задачей получения знаний; 2. Сбор информации из различных источников. Следует отметить, что в качестве эксперта может выступа не только человек, но и любой другой источник информации (справочники, статьи, видеозаписи и т.д.); 3. Разработка формализма (модели) знаний о предметной области. Рис. 2.1 – Методы получения знаний Стратегии получения знаний 1. Извлечение знаний без использования вычислительной техники путем непосредственного контакта инженера по знаниям и источника знания (будь то эксперт, специальная литература или другие источники). 2. Приобретение знаний от эксперта с использованием ЭВМ при наличии подходящего программного инструментария. 3. Формирование знаний с использованием программ обучения при наличии репрезентативной (т.е. достаточно представительной) выборки примеров принятия решений в предметной области и соответствующих пакетов прикладных программ. Приобретение знаний подразумевает, что автоматизированные системы действительно непосредственно приобретают уже готовые фрагменты знаний в соответствии со структурами, заложенными разработчиками систем. Большинство этих инструментальных средств специально ориентировано на конкретные базы знаний с жестко обозначенной предметной областью и моделью представления знаний, т.е. не являются универсальными. Например, система TEIRESIAS, ставшая прародительницей всех инструментариев для приобретения знаний, предназначена для пополнения базы знаний системы MYCIN и ее дочерних ветвей в области медицинской диагностики с использованием продукционной модели представления знаний. Термин «формирование знаний» традиционно закрепился за областью инженерии знаний, которая занимается разработкой моделей, методов и алгоритмов обучения. Он включает индуктивные модели формирования знаний и автоматического порождения гипотез, обучение по аналогии и др. Эти модели позволяют выявить причинно- следственные зависимости в базах данных. Вопросы для самоконтроля: 1. Дайте определение, что такое информация? 2. Дайте определение, что такое знания? 3. Дайте определение, что такое данные? 4. Как классифицируются знания? 5. Дайте определение, что такое инженерия знаний? 6. Какие этапы включает процесс извлечения знаний? 7. Какие стратегии получения знаний вы знаете? Лекция 3. Продукционные правила. 1. Понятие продукционных правил. 2. Системы продукций с обратными выводами. 3. Системы продукций с прямыми выводами. 1. Понятие продукционных правил В основе человеческой деятельности лежит мышление. Когда утром звонит будильник, мозг человека дает команду руке выключить его. Следует заметить, что это не автоматическая реакция, а решение конкретной задачи. При этом конечный результат, на который мы рассчитываем, на который направлены наши мыслительные процессы, называется целью. Как только цель (в данном случае выключение будильника) достигнута, перед человеческим мозгом сразу встают новые цели, например, одеться, позавтракать, выйти на остановку и т.д. Осуществление всех этих целей приводит к осуществлению главной цели – не опоздать в институт. Для достижения цели используется некоторая совокупность фактов и способов их применения – правил. На этих понятиях основан наиболее распространенный метод представления знаний – правила продукции или продукционные правила. Этот метод был предложен Э. Постом (1943 г.). Продукционные правила объясняют логическую связь между понятиями предметной области. Системы с базами знаний, основанных на этой модели, называются продукционными системами. Эти системы бывают двух диаметрально противоположных типов – с прямыми и обратными выводами. Правило продукции представляет собой подстановку следующего вида: где – конечная связка факторов, B – действие, которое выполняется, если – истинно. Иначе говоря, примером правил продукции может являться выражение следующего типа: ЕСЛИ <условие> ТО <действие>. При этом факты и правила могут быть разной сложности. Они связаны между собой с помощью логических функций И, ИЛИ, НЕ. Например: Факт1 Тихие, темные улицы опасны Факт2 Пожилые люди обычно не совершают дерзких преступлений Факт3 Моя милиция меня бережет Правило1 ЕСЛИ на темной, тихой улице вы встретите пожилого человека ТО можно не очень беспокоится Это простое правило можно усложнить добавив факты, объединенные в связку с помощью логической функции И: Правило2 ЕСЛИ на тихой темной улице вы видите милиционера И вы не преступали закон ТО можно чувствовать себя в полной безопасности Правила продукции можно отнести к категорическим знаниям, т.е. они всегда верны. Однако, в некоторых предметных областях (например, медицинская диагностика, системы управления и т.п.) преобладают вероятностные знания. Эти знания являются «мягкими» в том смысле, что говорить об их применимости к любым практическим ситуациям возможно только до некоторой степени. В таких случаях правила продукции дополняют вероятностной оценкой: ЕСЛИ <условие> ТО <действие> С УВЕРЕННОСТЬЮ <значение> Например: Правило1 ЕСЛИ на тихой темной улице вы видите милиционера И вы не преступали закон ТО можно чувствовать себя в полной безопасности С УВЕРЕННОСТЬЮ 0,3 Факты в правилах могут быть представлены в двух видах: в виде списков или в виде изолированной тройки: атрибут→ объект→ значение, при этом с каждым фактом связан коэффициент уверенности, изменяющийся в пределах [0,1]. Представление знаний в виде правил продукции обладает следующими преимуществами: • независимостью правил, выражающих самостоятельные фрагменты знаний; • легкостью и естественностью модификации знаний (правила продукции по структуре весьма похожи на рассуждения естественного языка); • отделением управляющих знаний (правил) от предметных знаний (фактов). Это позволяет применять различные стратегии управления. Основной недостаток продукций состоит в том, что при их большом количестве становится трудоемкой проверка непротиворечивости системы продукции. Например, при добавлении новых правил необходимо проверить, насколько они согласуются с уже существующими в базе знаний правилами. Как уже отмечалось выше, правила продукции относятся к процедурным моделям представления знаний. Даже самое простое правило продукции (т.е. правило, не содержащие присоединенных процедур) есть элемент «процедурности», т.к. предполагается, что это правило будет использовано для выполнения некоторого действия. Именно это отличает процедурное представление знаний от декларативного, поскольку декларативные знания не несут никакой информации о том, как они будут использованы. 2. Системы продукций с обратными выводами В системе продукций с обратными выводами с помощью правил строится дерево И/ИЛИ, связывающее в единое целое факты и заключения; оценка этого дерева на основании фактов, имеющихся в базе данных, и есть логический вывод. Логические выводы бывают прямыми, обратными и двунаправленными. При прямом выводе отправной точкой служат предоставленные данные, процесс оценки приостанавливается в узлах с отрицанием, причем в качестве заключения (если не все дерево пройдено) используется гипотеза, соответствующая самому верхнему уровню дерева (корню). Однако для такого вывода характерно большое количество данных, а также оценок дерева, не имеющих прямого отношения к заключению, что излишне. Преимущество обратных выводов в том, что оценивается только те части дерева, которые имеют отношение к заключению, однако если отрицание или утверждение невозможны, то порожденное дерево лишено смысла. В двунаправленных выводах сначала оценивается небольшой объем полученных данных и выбирается гипотеза, а затем запрашиваются данные необходимые для принятия решения о пригодности данной гипотезы. На основе этих выводов можно реализовать более гибкую и мощную систему. 3. Системы продукций с прямыми выводами Системы продукций с прямыми выводами среди систем, основанных на использовании знаний, имеют наиболее древнюю историю, поэтому они являются в некотором смысле основополагающими. Эти системы включают три компонента: базу правил, состоящую из наборов правил (правила вывода), базу данных, содержащую множество фактов, и интерпретатор для получения логического вывода на основании этих знаний. База правил и база данных образуют базу знаний, а интерпретатор соответствует механизму логического вывода. Вывод выполняется в идее цикла «понимание - выполнение», причем в каждом цикле выполняемая часть выбранного правила обновляет базу данных. В результате содержимое базы данных преобразуется от первоначального к целевому, т.е. целевая система синтезируется в базе данных. Иначе говоря, для системы продукций характерен простой цикл выбора и выполнения (или оценки) правил, однако из-за необходимости периодического сопоставления с образом в базе правил (отождествлением) с увеличением числа последних (правил) существенно замедляется скорость вывода. Следовательно, такие системы не годятся для решения крупномасштабных задач. Итак, упорядочим сильные и слабые стороны хорошо известных систем продукций. Сильные стороны: 1. Простота создания и понимания отдельных правил; 2. Простота пополнения и модификации 3. Простота механизма логического вывода. Слабые стороны: 1. Неясность взаимных отношений правил 2. Сложность оценки целостного образа знаний 3. Крайне низкая эффективность обработки 4. Отличие от человеческой структуры знаний 5. Отсутствие гибкости в логической выводе. Таким образом, если объектом является небольшая задача, выявляются только сильные стороны системы продукций. Вопросы для самоконтроля: 1. Дайте определение, что такое правила продукции? 2. Каким выражением характеризуется правила продукции? 3. Дайте определение, что такое система продукций с прямыми выводами? 4. Дайте определение, что такое система продукций с обратными выводами? 5. Какое строится дерево в системе продукций с обратными выводами? 6. Какие компоненты входят в состав системы продукций с прямыми выводами? 7. Перечислите основные недостатки системы продукций? Лекция 4-5. Семантические сети и фреймы 1. Семантические сети. 2. Фреймы. 1. Семантические сети Сетевая модель представления знаний является более наглядной, нежели продукционная. Она позволяет более ясно структурировать информацию и представлять ее в графическом виде. Понятие семантической сети основано на древней и очень простой идее о том, что «память» формируется через ассоциации между понятиями. Понятие «ассоциативная память» появилось еще во времена Аристотеля. В информатику оно вошло в связи с работами по использованию простых ассоциаций для представления значений слов в базе данных. Разработка семантических сетей относится к 1960 г., когда они использовались для моделирования обработки естественного языка, для представления смысла (семантики) выражения. Отсюда и происходит их название. Квиллиан предположил, что наша способность понимать язык может быть охарактеризована некоторым множеством базовых понятий (концептов) и правил. Так с помощью 100 базовых понятий был смоделирован словарь в 15 000 слов. Процесс восприятия текста включает в себя «создание некоторого рода мысленного символического представления». Квиллиан первым предложил использовать для моделирования человеческой памяти сетевые структуры. Теперь же они используются в качестве структуры, пригодной для представления информации общего вида. Базовыми функциональными элементами семантической сети служит структура из двух компонентов – узлов и связывающих их дуг. Таким образом, семантической сетью называется ориентированный граф с конечными вершинами. Каждый его узел представляет собой некоторое понятие, а дуга – отношение между парой понятий. Можно считать, что каждая из таких пар отношений представляет простой факт. Узлы в семантической сети соответствуют объектам, понятиям или событиям. Они обладают определенной маркировкой, позволяющий идентифицировать этот узел. Основной принцип семантической сети: знания, которые семантически связаны между собой (связаны по смыслу) должны храниться рядом. В семантической сети имеется два типа дуг: 1. является (is) 2. имеет частью (has part) Дуги обладают свойством транзитивности – устанавливают отношения иерархии наследования в сети (элементы низкого уровня наследуют свойства высокого) В качестве простого примера семантической сети рассмотрим предположения: «Студент Иванов является мужчиной»; «Мужчина является человеком» Студент Иванов мужчиной человеком. Очевидно, что отношение «является» транзитивно, т.е. из этой сети мы можем вывести третье утверждение, хотя оно и не было сформулировано в чистом виде «Студент Иванов является человеком». Свойство транзитивности позволяет экономить память, поскольку информация о сходных узлах может не повторяться в каждом узле сети, а храниться в одном центральном узле. Это свойство модели памяти получило наименование когнитивной экономии. Например, на рис. 4.1 информация об узле с маркировкой «сердечная мышца» присоединена к узлу с маркировкой «система органов кровообращения», а информация о том, что сердечная мышца является частью человека задана неявно. Рис. 4.1 – Диаграмма семантической сети. Квиллиан также ввел разделение между видами узлов. Один вид узлов он назвал узлами-типами. Такой узел представляет концепт, связанный с конфигурацией других узлов, узлов-лексем. Это в определенной степени напоминает толковый словарь, в котором каждое понятие определяется другими понятиями, также присутствующими в этом словаре, причем и их смысл толкуется с помощью еще каких либо понятий в этом словаре. Например, можно определить смысл слова «машина» как конструкцию из связанных компонентов, которые передают усилия для выполнения определенной работы. Это потребует присоединения узла-типа для слова «машина» к узлам-лексемам «конструкция», «компонент» и т.д. Однако в дополнение к связям, сформированным для определения смысла, могут существовать связи к другим узлам-лексемам, например «телетайп», «офис». Эти связи представляют знания о том, что телетайпы являются одним из видов машин, которые используются в офисе. Проблема поиска решений в базе знаний типа семантической сети сводится к задаче поиска фрагмента сети, соответствующего некоторой подсети, отражающей поставленный запрос к базе. Существует довольно обширный перечень проблем, при решении которых представление, базирующееся на формализме семантических сетей, оказывается весьма полезным. И использование узлов и связей в сети для представления понятий и отношений может показаться само сбой разумеющимся. Однако следует учитывать следующие недостатки семантических сетей: • В различных вариантах спецификаций структуры сети далеко не всегда можно четко определить смысл маркировки узлов. Так если рассмотреть узел-тип, имеющий маркировку «телетайп», то часто бывает непонятно, представляет ли этот узел понятие «телетайп», или класс всех агрегатов типа «телетайп», или какой-то конкретный телетайп. Аналогично, и узел-лексема открыт для множества толкований. Разные толкования влекут за собой и разный характер влияния этого узла на другие узлы сети. Иначе говоря, семантические сети являются логически неадекватными. • Процесс поиска информации в сети сам по себе знаниями не управляется. Другими словами, этот механизм не предполагает наличия какого-либо знания о том, как искать нужную нам информацию в представленных знаниях. Таким образом, сети является эвристически неадекватными. Эти два недостатка иногда усиливают друг друга. Например. Если невозможно представить логическое отрицание или исключение (логическая неадекватность), то это приведет к определенным «провалам» в знаниях, которые к тому же нельзя ликвидировать, прекратив поиск в этом направлении (эвристическая неадекватность). Одним из способов ликвидировать эти недостатки является переход к специальному представлению узлов в сети и унификация связей между узлами (фреймами). 2 Фреймы Термин фрейм (от англ. Frame – каркас, рамка) был предложен Марвином Минским в 70-е годы. Эта структура знаний изначально предназначалась для восприятия пространственных сцен. В философии и психологии известно понятие абстрактного образа. Например, произнесенное вслух слово «комната» вызывает у нас образ комнаты: «жилого помещения с четырьмя стенами, полом, потолком, окнами и дверью, площадью 6–20м2. В теории фреймов этот образ называют фреймом комнаты. Из этого описания нельзя ничего убрать (например, убрав окна, мы получим уже не комнату, а подвал). В нем есть «дырки» – незаполненные значения некоторых атрибутов (например количество окон), эти «дырки» называют слотами (от англ. щель). Таким образом, можно дать определение фрейму как минимально возможному описанию сущности какого- то явления, события, ситуации, процесса или объекта. Минимально возможное означает, что при дальнейшем упрощении описания теряется его полнота, оно перестает определять ту единицу знаний, которой предназначено. В системе фреймов предпринимается попытка судить о классе объектов, используя представление знаний о прототипах, которые хорошо представляют различные объекты данного класса. Например, «прототипическая» птица, пусть это будет воробей, может летать, а потому есть основания полагать, что это свойство всех птиц, хотя существуют редкие виды птиц, которые этим свойством не обладают, например пингвины. Именно в этом смысле воробей является лучшим экземпляром категории «птицы», чем пингвин, поскольку он представляет более типичные свойства объектов своего класса. При решении практических задач подобных исключений весьма много, а границы между классами оказываются очень размыты. Система фреймов оказывается полезной по той причине, что она дают средства структурирования знаний, связанных с приложением правил и классификации объектов. Марвин Минский определил фрейм как «структуру данных для представления стереотипных ситуаций». Идея состояла в том, чтобы сконцентрировать знания в единой структуре данных, а не распределять их между множеством более мелких структур. Такие знания либо сосредоточены в самой структуре данных, либо доступны из этой структуры (например, хранятся в другой структуре, связанной с фреймом). Доступ к связанным структурам осуществляется посредством присоединенных процедур. Таким образом, по существу, фрейм оказался тем средством, которое помогло связать декларативные и процедурные знания. По своей структуре фреймы похожи на семантические сети. Можно считать, что фрейм – это сложный узел сети. Часть специалистов по системам ИИ даже считает, что нет необходимости выделять фреймовые модели представления знаний, так как в них объединены все основные особенности моделей остальных типов. В качестве идентификатора фрейму присваивается имя фрейма. Это имя должно быть единственным во всей фреймовой системе. Фрейм имеет определенную внутреннюю структуру, состоящую из множества элементов, называемых слотами, которым также присваиваются имена. Каждый слот в свою очередь представляется определенной структурой данных. В значение слота подставляется конкретная информация, относящаяся к объекту, описываемому этим фреймом. Таким образом, каждый фрейм имеет специальный слот, заполненный наименованиями сущностей, и слоты, заполненные значениями различных атрибутов, ассоциирующихся с объектом. Как правило, фреймы организованы в виде «ослабленной иерархии» (или «гетерархии») в которой фреймы, расположенные ниже в иерархии, могут наследовать значения слотов разных фреймов, расположенных выше. Фундаментальная идея состоит в том, что свойства и процедуры, расположенные выше, являются более или менее фиксированными, поскольку они представляют те вещи или понятия, которые в большинстве случаев являются истинными для интересующей нас сущности. В то же время, фреймы более нижних уровней имеют слоты, которые должны быть заполнены наиболее динамической информацией, подверженной частым изменениям. Если такая динамическая информация отсутствует из-за неполноты наших знаний о предмете, то слоты фреймов более нижних уровней заполняются данными, унаследованными от фреймов верхних уровней. Ниже в качестве простого примера показан фрейм, описывающий человека. Фрейм: Человек Имя слота: Значение слота Класс: Млекопитающее Структурный элемент: Голова, шея, руки, … Рост: 40 220 см Масса: 1  200 кг Хвост: Нет Язык: Русский, английский, китайский … Фрейм аналогии: Обезьяна Значением слота может быть практически что угодно: числа, формулы, тексты на естественном языке или программы, правила вывода или ссылки на другие слоты данного фрейма или других фреймов. Кроме того, со слотами может, ассоциирована любая дополнительная информация, например, процедура вычисления значения этого слота в случае отсутствия его явного заполнения, процедура обновления значения слота при изменении значения другого слота. В качестве значения слота даже может выступать набор слотов более низкого уровня, что позволяет реализовывать во фреймовых представлениях «принцип матрешки». Связи между фреймами задаются значениями специального слота с именем «Связь». Фреймы с заполненными слотами называются экземплярами фрейма. Для описания объекта. Ситуации или события строится сеть фреймов. Фрейм представляет собой сложный узел такой сети. Как уже отмечалось выше, слоты фрейма обладают присоединенными процедурами, позволяющими осуществлять связь в структуре фрейма. С каждым фреймом связана информация о том, как его использовать, как поступать в чрезвычайных ситуациях. Присоединенные процедуры бывают двух типов – демоны и слуги. Процедуры-слуги необходимо активизировать всякий раз, когда осуществляется доступ к фрейму или его обновление. Идея состоит в том, чтобы выполнение большей части вычислений, связанных с решением проблемы, явилось побочным эффектом передачи данных во фрейм или извлечения данных из него. Процедуры, подключенные к структуре данных и запускаемые на выполнение при появлении запроса или обновлении информации в структуре, называют демонами. Те демоны, которые вычисляют некоторые значения по запросу, называются демонами по требованию. Поиск решения во фреймовой модели представления знаний означает поиск по всем фреймам (сети фреймов) модели, которая наилучшим образом описывает ситуацию. В процессе поиска слоты фреймов заполняются информацией. Полученные экземпляры фреймов проверяются на адекватность рассматриваемой ситуации. Если выявлено хотя бы одно несовпадение, рассматривается следующий фрейм. Подводя итог всему сказанному выше о семантических сетях и фреймах, можно отметить, что семантические сети являются весьма мощным средством представления знаний, но для них характерна неоднозначность и неоднородность связей. Структура сетей, как правило, не дает четкий ответ на два важных вопроса: • Что же действительно стоит за узлами и связями в сети? • Как можно эффективно обрабатывать информацию, хранящуюся в такой структуре? Для автоматизации процесса использования и представления знаний предпочтительной является унифицированная, однородная форма представления информации. Поэтому в большинстве последних исследований, касающихся представления знаний, предпочтение отдается фреймам. Узлы в сети представлены как иерархия фреймов, связи организованы связями между фреймами. Эффективность обработки обеспечивается подключением к узлам специфических процедур, на которые возлагаются вычисление значений переменных в ответ на запросы или при обновлении значений других свойств узла- фрейма. Вопросы для самоконтроля: 1. Дайте определение, что такое семантическая сеть? 2. Из каких базовых элементов состоит семантическая сеть? 3. Каким свойством обладают дуги в семантических сетях? 4. Что такое логически неадекватная семантическая сеть? 5. Что такое эвристически неадекватная семантическая сеть? 6. Дайте определение, что такое фрейм? 7. Дайте определение, что такое слот фрейма? 8. Дайте определение, что такое экземпляр фрейма? 9. Какие присоединенные процедуры бывают в фреймах? 10. Дайте определение, что такое демоны по требованию? Лекция 6. Представление знаний и процедура вывода с помощью логики предикатов 1. Понятие формальной системы. 2. Исчисление высказываний как формальная система. 3. Исчисление предикатов первого порядка. 4. Логический вывод и логическое программирование. 1. Понятие формальной системы Появление формальных систем было обусловлено осознанием того факта, что совершенно различные системы, будь то технические, социальные, экономические или биологические, обладают глубоким сходством. В формальной системе (ФС), оперирующей теми или иными символами, эти символы воспринимаются просто как элементы, с которыми обращаются согласно определенным правилам, зависящим только от формы выражений, образованных из символов. Понятие истинности появляется только в связи с возможными приложениями (интерпретациями) этой системы. Формальные системы – это аксиоматические системы, т.е. системы с наличием определенного числа исходных заранее выбранных и фиксированных высказываний, называемых аксиомами. Формальная система считается заданной, если выполнены следующие условия. 1. Задано некоторое множество, состоящее из конечного или бесконечного числа элементов, которые носят название термов. Имеется другое конечное множество, элементы которого есть связки или операции. 2. Любую линейную упорядоченную совокупность термов и операций называют формулой. Из множества формул выделяют подмножеств правильно построенных формул (ППФ). Для ППФ задают правила их конструирования, т.е. определяется эффективная процедура, позволяющая по данному выражению выяснять, является ли оно ППФ в данной ФС. 3. Выделено некоторое множество ППФ, называемых аксиомами ФС. При этом должна иметься эффективная процедура, позволяющая для произвольной ППФ, решить, является ли она аксиомой. 4. Имеется конечное множество отношений между ППФ называемых правилами вывода. Понятие «вывода» также должно быть эффективным, т.е. должна существовать эффективная процедура, позволяющая для произвольной конечной последовательности ППФ решать, можно ли каждый член этой последовательности вывести из одной или нескольких предшествующих ППФ посредством некоторых фиксированных правил вывода. Выводом ФС называется любая последовательность ППФ такая, что для любого i () ППФ Аi есть либо аксиома ФС, либо непосредственное следствие каких-либо предыдущих ППФ по одному из правил вывода. Любая ФС задается четверкой , где T – множество термов и операций; H – множество правил конструирования ППФ; A – система аксиом; R – множество правил вывода. Сама формальная система не является ни языком, ни системой знания, она не содержит никаких утверждений об объектах, а является просто исчислением – некоторого рода действиями по определенным правилам над последовательностями термов. Два класса формальных систем являются математической базой для построения систем ИИ: исчисление высказываний и исчисление предикатов первого порядка. 2. Исчисление высказываний как формальная система Сложное высказывание имеет истинностное значение, которое однозначно определяется истинностными значениями простых высказываний, из которых оно составлено. Например: «Если студент ложится поздно спать и пьет кофе, то утром он встанет в плохом настроении или с головной болью». Это сложное высказывание состоит из следующих простых высказываний: «Студент ложиться поздно спать» «Студент пьет на ночь кофе» «Утром студент встанет в плохом настроении» « Утром студент встанет с головной болью» Обозначив сложное высказывание через X, а простые соответственно через Y, Z, U, V, можно записать Или Каждую логическую связку можно рассматривать как операцию, которая образует новое высказывание – сложное из более простых. Таким образом, всякое сложное высказывание можно записать в виде некоторой формулы, содержащей логические связки и символы, которые обозначают простые высказывания, называемые атомами. Чтобы узнать, истинно или ложно сложное высказывание, достаточно узнать истинные значения всех атомов, из которых оно составлено. Для формулы состоящей из n атомов существует 2n интерпретаций. Формула исчисления высказываний, которая истинна во всех интерпретациях, называется тавтологией или общезначимой формулой. Формула исчисления высказываний называется противоречием, если она ложна во всех интерпретациях. 3. Исчисление предикатов первого порядка Исчисление высказываний оказывается недостаточным для обоснования, например, таких рассуждений: «Всякое положительное целое число есть натуральное число. Число 5 есть положительное целое число. Следовательно, 5 есть натуральное число». Это объясняется тем, что исчисление высказываний ограничивается структурой предложений в терминах простых высказываний, а приведенные рассуждения требуют анализа структуры предложения в смысле связи субъекта и предиката, как это делается в грамматике. Слово «предикат» имеет два значения. В грамматике – сказуемое, в логике – логическое сказуемое, то, что в суждении высказывается о предмете суждения. Пусть задано некоторое множество , в котором – какие-то определенные предметы из этого множества. Обозначим любой предмет из этого множества через x и назовем x предметной переменной. Тогда высказывания об этих предметах будем обозначать в виде , и т.д., причем такие высказывания могут быть истинными и ложными. Например, если , то высказывание «4 есть четное число» является истинным, а «7 есть четное число» – ложным. Если вместо конкретных чисел 4 и 7 поставим предметную переменную x, то получим предикат «x есть четное число», обозначенный P(x). Таким образом, предикат, который не содержит переменных, совпадает с высказыванием. Исчисление предикатов первого порядка представляет собой формальную систему, с помощью которой можно выразить большое разнообразие утверждений. Неотъемлемой функцией языка предикатов является задание слов, которые описывают сущности изучаемого мира, и слов, которые описывают атрибуты, т.е. свойства этих сущностей, их поведение и отношения. Первый тип слов является термами, второй – предикатами. Элементарными компонентами языка предикатов являются предикатные символы и символы констант, переменных и функций. Атомарными предикатом называется последовательность из n ( и конечно) термов, заключенная в круглые скобки, которые следуют за предикатным символом. Имя предикатного символа выражено некоторой последовательностью букв. Например: отец(x, y) – атомарный предикат, описывающий отношение x к y. В логике предикатов атомарные предикаты задают формулы для описания отношений между сущностями, определяемыми аргументами предикатов. Если конструктор намеревается описать некоторую предметную область, используя для этого логику предикатов, он может определять предикаты по своему усмотрению в соответствии с конкретной ситуацией. Определение соответствия между элементами языка и отношениями, элементами и функциями в указанной области рассуждения и составляет семантику языка исчисления предикатов. Очевидно, что определение предиката должно быть однозначным. Квантер – логические операции, позволяющие перевести одну форму высказывания в другую и указывающие объем переменных, для которых высказывание истинно Таким образом, исчисление предикатов первого порядка представляет собой расширение исчисления высказываний. 4. Логический вывод и логическое программирование Логика – это некоторый способ представления высказываний, создаваемый для того, чтобы, используя формальную процедуру проверить справедливость этих высказываний. Иначе говоря, это наука о способах рассуждений, приводящих к истине. Изучая эти способы логика, интересуется в первую очередь, формой, а не содержанием доводов в том или ином рассуждении. Рассмотрим, например следующие два вывода: 1. Все люди смертны. Сократ – человек. Следовательно, Сократ смертен. 2. Все кошки любят молоко. Мурка – кошка. Следовательно, Мурка любит молоко. Оба вывода имеют одну и ту же форму: все А суть В; С есть А; следовательно С есть В. Истинность или ложность отдельных посылок не является предметом логики. Например, истинность утверждения «все кошки любят молоко» обосновывается значением фактического положения в жизни кошек – это эмпирический факт. Логический вывод осуществляется из некоторых исходных утверждений с помощью имеющихся схем умозаключений. Используется так же термин «дедукция». Схемы рассуждений принято называть правилами логического вывода. 1. объявляется некоторый набор фактов, высказываний и отношений между объектами; 2. определяются правила, которые описывают отношения между объектами; 3. формируется вопрос об объектах и отношениях между ними. Вопрос – это средство извлечения информации из логической программы. Правило – общее утверждение об объекте. Программа объединяет конечное количество фактов и правил. Концепция логического вывода в программировании эквивалентна понятию алгоритма. Например: женщина (Алиса) женщина (Виктория) мужчина (Эдуард) мужчина (Джон) родители (Алиса, Виктория Джон) родители (Эдуард), Виктория Джон) сестра (Эдуард, Х)? Характерным представителем логического программирования является язык ПРОЛОГ. Вопросы для самоконтроля: 1. Дайте определение, что такое формальная система? 2. Когда формальная система считается заданной? 3. Дайте определение, что такое тавтология? 4. Дайте определение, что такое противоречие? 5. Что такое предикат? 6. Когда предикат совпадает с высказыванием? 7. Дайте определение, что такое атомарный предикат? 8. Что представляет собой семантика языка исчисления предикатов? Лекция 7. Системы нечеткого рассуждения 1. Основы теории нечетких множеств. Правило Байеса. 2. Операции с нечеткими множествами. 3. Метрики в нечетком подмножестве. Методы построения функции принадлежности в нечетком подмножестве. 4. Метод выбора альтернативы с использованием шкалы Саати. 5. Нечеткая логика и теория возможностей. 1. Основы теории нечетких множеств. Правило Байеса При попытке формализовать человеческие знания исследователи вскоре столкнулись с проблемой, затрудняющей использование традиционного математического аппарата для их описания. Существует целый класс описаний, оперирующих качественными характеристиками объекта (много, мало, очень мало). Эти характеристики обычно размыты и не могут быть точно интерпретированы, однако содержат ценную информацию (например: если НЕМНОГО рискнуть, то можно МНОГО получит, при этом НЕМНОГО и МНОГО принципиально субъективны). Кроме того, часто приходится пользоваться неточными знаниями, которые не могут быть интерпретированы как истинные или ложные (true/ false). Для разрешения таких проблем в начале 70-х годов американский математик Лотфи Заде предложил аппарат нечеткой (fazzy) логики. Позже это направление положило начало одной из ветвей ИИ под названием мягкие вычисления (soft computing). Л. Заде ввел одно из главных понятий в нечеткой логике – понятие лингвистической переменной. Лингвистическая переменная – это переменная, значение которой определяется набором вербальных (т.е. словесных) характеристик некоторого свойства. Значение лингвистической переменной определяется через т.н. нечеткие множества. Они в свою очередь, определены через некоторую базовую шкалу В и функцию принадлежности. Понятие принадлежности. Пусть Е – множество, А – подмножество в этом множестве. В множестве Е существуют элементы хi принадлежащие этому подмножеству. Тогда хi принадлежит А если существует функция: • функция принадлежности. Таким образом, нечеткое множество – это совокупность пар вида . Основным отличием нечеткой логики от классической, как явствует из названия, является наличие не только двух классических состояний (значений), но и промежуточных: . Функция принадлежности определяет субъективную степень уверенности эксперта в том, что данное конкретное значение базовой шкалы соответствует определяемому нечеткому множеству. Эту функцию не стоит путать с вероятностью, которая определяется математически. Например, для двух экспертов определение нечеткого множества «ВЫСОКАЯ» для лингвистической переменной «ОПЛАТА ЗА ОБУЧЕНИЕ» существенно отличается в зависимости от их социального и финансового положения. Для разрешения этой проблемы существует правило Байеса. Правило Байеса позволяет определить относительное правдоподобие конкурирующих гипотез, исходя из силы свидетельств. В основе этого правила лежит формула: , где отношение правдоподобия О определяется как вероятность события или свидетельства Е при условии заданной конкретной гипотезы Н, деленная на вероятность этого свидетельства при условии ложности данного свидетельства. Используя правило Байеса, удобнее работать с шансами. Шансы в пользу чего-то О и вероятность Р преобразуются друг в друга следующим образом . Преобразование оценки «шансы против» в оценку «шансы за» осуществляется с помощью зависимости . Байесовская формула может быть сведена к виду: , где – априорные шансы в пользу Н, а – результирующие шансы при условии наступления события Е, в соответствии с отношением правдоподобия. При заданных априорных шансах для конкурирующих гипотез, про которые известно, что они произошли легко вычисляются результирующие шансы. Отношение правдоподобия получается из простой двумерной таблицы, показывающей, насколько часто случается каждое событие при каждой из гипотез. Таким образом, отношения правдоподобия дают два преимущества: 1. Они допускают комбинирование нескольких независимых источников данных. 2. Их можно корректировать, если свидетельство ненадежно само по себе. 2. Операции с нечеткими множествами ~ 1. Неравенство. (подмножество В включается в А), когда для всех x выполняется: . 2. Равенство. , тогда и только тогда, когда для всех х выполняется: . 3. Дополнение. , если: . 4. Пересечение. , если: . 5. Объединение. , если: Иными словами, геометрическая близость представляет собой сходство между элементами нечетких множеств. Геометрическая близость между объектами двух нечетких множеств определяется на основе применения различных метрик (расстояний). Для выявления степени различия между признаками используется расстояние Хэмминга: . Относительное расстояние Хэмминга: , где . Методы получения функции принадлежности подразделяются на: • прямые, • косвенные, • методы, на основе терм множеств. Каждый из этих классов включает в себя методы, основанные на единичной и групповой экспертизе. К прямым методам получения функции принадлежности относится метод семантического дифференциала. 3. Метод семантического дифференциала Для каждой предметной области для описания объекта можно выбрать некоторую шкалу измерений, используя следующие рекомендации: 1. Составить список свойств, которые должны описывать объект исследования. 2. В этом списке для каждой характеристики найти полярные значения 3. Для каждой пары полярных определений найти, как сильно выражено положительное свойство характеристики. Полученный профиль представляет собой значение функции принадлежности по каждой характеристике. Оценивая полюсные значения [0;1], мы гарантируем, что значения функции будут находиться в интервале[0;1]. 4. Шкала Саати Пусть необходимо выбрать работу на основе на основе следующей информации: Места работы – . Критерии оценки – зарплата, перспективность, расстояние от дома и т.д. – . 1. Выбор альтернативы можно производить по одному критерию. Тогда: С – критерий, – нечеткое множество характеристик этого критерия. Лучшая альтернатива . 2. Выбор альтернативы можно проводить на основе нескольких критериев, которым присваивается одинаковая важность. Тогда: – одинаковы по важности: ; . Лучшая альтернатива . 3. Выбор альтернативы производится по критериям, которым присвоена разная важность. Тогда вводится параметр . Нечетким множеством - уровня называется множество пар вида Например: Параметр α и называется показателем значимости. Важность того или иного критерия определяется весовым коэффициентом. Он определяется экспертными оценками и зависит от заданного показателя значимости. Для того чтобы получить групповые веса, Саати предложил шкалу оценок важности. Эта шкала базируется на основе парных сравнений. Возможность bij равная 1 а1 немного важнее а2 3 а1 важнее а2 5 а1 значительно важнее а2 7 а1 на много важнее а2 9 На основе экспертной оценки по собственным значениям составляется матрица ранжирования и на ее основе вычисляются весовые коэффициенты. 5.Нечеткая логика и теория возможностей Ранее нами уже был рассмотрен аппарат формальной логики и логического вывода. Благодаря Л. Заде она получила широкое толкование с точки зрения теории множеств. В теории нечетких множеств роль двузначной булевой логики играет нечеткая логика. В нечеткой логике предположения о принадлежности объекта множеству могут принимать значения в интервале от 0 до 1. Возникает вопрос: как использовать концепцию неопределенности для вычисления значения истинности сложного высказывания? В классической логике предположение Является истинным в том и только в том случае, если истинны оба члена этого выражения. В нечеткой логике существует соглашение: если F и G являются нечеткими предикатами, то и аналогично . Таким образом, можно получить, что если , то . Теперь рассмотрим следующую ситуацию. Пусть имеем отрицание: По приведенной выше формуле дополнения: . А теперь рассмотрим следующее выражение: Вероятность истинности этого утверждения равна 0, поскольку: Однако в нечеткой логике значение этого выражения будет равно 0,1. Суть этого состоит в том, что значение выражения можно считать показателем принадлежности кошки к нечеткому множеству других имен. Смысл выражения заключается в том, что мы только на 90% уверены в принадлежности этой кошки к кошкам по имени Мурка. Вполне резонно предположить, что существует некоторая уверенность в том, что кошку зовут иначе. Из вышесказанного, очевидно, что нечеткая логика имеет дело с ситуациями, когда знания, которыми мы располагаем, выражены нечеткими понятиями. Однако нечеткость понятий является не единственным источником неопределенности. Иногда просто нет уверенности в самих фактах. В этом случае нечеткая логика строится на основе теории возможностей. Возможность гипотезы – это уровень, на котором рассматривает гипотезу человек, принимающий решения, чтобы она была возможной. Возможность несколько отличается от вероятности в том, что вероятность показывает силу уверенности появления гипотезы. Измерение возможности требует, чтобы ее значения находились в диапазоне [0,1]. Неизбежность гипотезы определяется как единица минус возможность обратной гипотезы. Например, предположим, что возможность хорошего отношения к вам преподавателя равна 0,95 и возможность нехорошего отношения равна 0,3. Тогда неизбежность хорошего отношения равна 0,7. Чтобы понять смысл теории возможностей рассмотрим классический пример. Предположим, что в коробке лежит 10 шаров. Известно, что несколько из них красные. Какова вероятность того, на удачу из них будет вынут красный шар? Если бы нам было известно количество красных шаров, рассчитать вероятность с помощью классического аппарата математики не составило бы труда. Но у нас есть лишь неопределенное понятие несколько. Определим понятие «несколько» как нечеткое множество, например, так: f={(2/0.1),(3/0.6),(4/1.0),(5/1.0),(6/0.6),(7/0.3),(8/0.3),(9/0.1)}. В этом определении выражение (2/0.1) f означает, что 2 из 10 вряд ли можно назвать «несколько». В то же время(5/1.0) f идеально согласуются с понятием «несколько». И уж конечно, мы не назовем несколькими 1 или 10 из 10, поскольку интуитивно ясно, что «несколько» означает «больше одного» и «не все». Поэтому в определение нечеткого подмножества значения 1 и 10 не входят. Теперь распределение возможностей для подмножества красных шаров представляется формулой: , которая после подстановки дает f={(0.2/0.1),(0.3/0.6),(0.4/1.0),(0.5/1.0),(0.6/0.6),(0.7/0.3),(0.8/0.3),(0.9/0.1)}. Выражение (0.2/0.1) fk что шанс на то, что вероятность вытащить красный шар из коробки имеет значение 0,2, равен 10%. И, в то же время, можно с уверенностью заявить, что значение вероятности равно 0,4 или 0,5. Вопросы для самоконтроля: 9. Дайте определение, что такое лингвистическая переменная? 10. Как задается нечеткое множество? 11. Что такое объединение двух множеств? 12. Что такое пересечение двух множеств? 13. Дайте определение, что такое функция принадлежности? 14. В чем суть метода семантического дифференциала? 15. Что такое возможность гипотезы? 16. Что такое неизбежность гипотезы? Лекция 8. Методика построения и архитектура экспертных систем 1. Методика построения экспертных систем. 2. Классификация экспертных систем. 3. Архитектура экспертных систем. 1. Методика построения ЭС Экспертная система – это программа, которая заменяет эксперта в той или иной области. Экспертная система предназначена для решения задач, возникающих в слабоструктурированных и трудноформализованных предметных областях. В настоящее время сложилась следующая технология разработки ЭС, которая включает этапы: 1. идентификация 2. концептуализация 3. формализация 4. выполнение 5. тестирование 6. опытная эксплуатация Идентификация. Этап идентификации связан с осмыслением тех задач, которые предстоит решать будущей экспертной системе и формировать требования к ней. Результатом этого этапа является ответ на вопрос: «Что надо сделать и какие ресурсы необходимо задействовать?». Обычно в разработке ЭС участвуют: один эксперт или несколько экспертов, один инженер по знаниям, один или несколько программистов. При разработке ЭС определяются основные ресурсы, к которым относятся: источники знаний, время разработки, вычислительные средства, объем финансирования. Концептуализация. На данном этапе проводится содержательный анализ проблемной области, выявляют используемые понятия и их взаимосвязи, определяются методы решения задачи. Этап завершается созданием модели предметной области и определением следующих задач: - типов доступных данных; - исходные и выходные данные; - используемые стратегии и гипотезы; - типы используемых отношений; - состав знаний, используемых для решения задачи; - состав знаний, используемых для обоснованного решения. Существует 2 подхода к процессу построения моделей предметной области: 1. атрибутивный 2. структурный Атрибутивный подход предполагает получение от эксперта информации в виде тройки: Объект, Атрибут, Значение атрибута. Структурный подход реализуется путем выделения элементов предметной области их взаимосвязях. На этом этапе выделяют понятия предметной области, который должен образовывать систему, обладающую следующим свойством: уникальностью, полнота, достоверность, непротиворечивость. Существуют различные методы построения системы понятий: 1. Метод локального представления. Эксперты просят разбить задачу на подзадачи, перечислить условия состояния и описать общие категории цели. Затем для каждого разбиения (локальные представления) эксперты формулируют факты и деятельность или наименования. При этом число информационных факторов в каждом локальном представлении, которыми должен одновременно манипулировать человек, должно быть равно 7. 2. Ролевой метод. Эксперту дается задание обучить инженера по знаниям решению некоторой задачи предметной области. При этом эксперт играет роль учителя, инженер по знаниям ученика. Затем третье лицо анализирует процесс такого обучения, выделяя все понятия употребляемые учеником и учителем. 3. Эффект свободных ассоциаций. Эксперта просят ответить на заданное слово первым, пришедшем на ум словом. Строится цепочка таких слов, и количество переходов в цепочке служит мерой смыслового расстояния между двумя понятиями. Исследования показали, что для любых двух понятий существует ассоциативная цепочка не более чем из семи слов. 4. Прямой метод устанавливается семантическим отношением. В настоящее время выявлено около 200 базовых отношений (части, целые, род, вид, причина, следствие). Метод основан на непосредственном осмыслении каждой такой взаимосвязи. При этом формируются тройки (понятие 1 – связь – понятие 2). Рядом с каждой тройкой записывается предложение, поставленное таким образом, чтобы понятие 1 и 2 входили в это предложение. В качестве связок используется только содержательное отношение, т.е. не используется неопределенность связки. Этап формализации. На этом этапе все ключевые понятия и отношения выражаются на некотором формальном языке, который либо выбирается из уже существующих, либо разрабатывается заново. Выполнение. На этом этапе создается один или несколько прототипов экспертных систем, затем по результатам тестирования и опытной эксплуатации, на основе этих прототипов создается конечный продукт годный для использования. Одним из основных моментов при создании прототипов является обеспечение проверки адекватности методов и способа представления знания решаемых задач. Тестирование. В ходе данного этапа производится оценка выбранного способа представления знаний в целом. Для этого инженер по знаниям подбирает тестовый пример, обеспечивающий проверку всех возможностей разработанной ЭС. Опытная эксплуатация. На этом этапе проверяется пригодности ЭС для конечного пользователя. Под пригодностью ЭС понимается полезность и удобство работы с ней. ПОЛЕЗНОСТЬ ЭС – это способность в ходе диалога определять потребности пользователя, выявлять и устранять причины неудачи в работе и удовлетворять указанные потребности пользователя. 2. Архитектура ЭС ЭС включает в себя 2 основных компоненты. 1. Базу Знаний (БЗ) 2. Программный инструмент доступа и обработки знаний, который включает: механизм вывода, механизм приобретения знаний, механизм объяснения результата и интеллектуальный интерфейс. БЗ – это совокупность единиц знаний, которые представляют собой формализованное отражение объектов предметной области и их взаимосвязей, действия над объектами и неопределенности с которыми эти действия осуществляются. Интеллектуальный интерфейс осуществляет обмен данными между пользователем и экспертной системой. Механизм вывода. Получает от интеллектуального интерфейса информацию, преобразовывает ее во внутренний запрос, формирует конкретный алгоритм решения задачи, выполняет алгоритм и представляет результат интеллектуальному интерфейсу. При этом механизм вывода находит в БЗ единицы знаний в соответствии с конкретной ситуацией и связывает их в цепочку рассуждений. Механизм объяснения. В процессе решения задачи или по получению результата пользователь может запросить объяснение или обоснование хода решения. В этом случае экспертная система должна предоставлять соответствующее объяснение. Механизм приобретения знаний. Механизм приобретения знаний – представление интеллектуальный редактор, который позволяет ввод единицы знаний в БЗ, проводить их синтаксический и семантический контроль и проверку на непротиворечивость. 3. Классификация ЭС В настоящее время ЭС классифицируются по следующим основным признакам: 1. По способу формирования решения ЭС делятся на: ◦ аналитические; ◦ синтетические. Аналитические системы предлагают выбор решения из множества известных альтернатив, т.е. осуществляет определение характеристик объекта. Синтетические предполагают генерации неизвестных решений, т.е. формирование объектов. 2. По способу учета временного фактора ЭС делятся на: • статические; • динамические. Статические системы решают задачи при неизменном процессе решения данных и знаний. В динамических системах такое изменение допускается. 3. По видам используемых данных и знаний: • системы с детерминированными знаниями; • системы с неопределенными знаниями. 4. По числу используемых источников знаний могут быть построены с использованием одного или множества источников знаний. В случае множества источников знаний они могут быть либо альтернативными, либо дополняющими друг друга. В соответствии с перечисленными признаками классификация ЭС делится на четыре основных класса. Анализ Синтез Детерминированная Классифицирующая Трансформирующая Один источник знаний Неопределенные знания Доопределяющая Многоагентная Много источников Статика Динамика Классифицирующая, как правило, это система, решающая задачи распознавания ситуаций, т.е. определяющая принадлежность анализируемой ситуации к некоторому классу. При этом по набору заданных признаков, факторов выявляется сущность некоторой ситуации в зависимости, от которой выбирается последовательность действий и среди альтернативных решений находится одно наилучшим образом удовлетворяющее поставленной цели и ограничениям. Доопределяющая. С помощью таких систем решаются более сложный класс аналитических задач на основе неопределенности исходных данных и применяемых знаний. В этом случае система должна доопределять недостающее значение, а в пространстве решений может получится несколько возможных решений с различной вероятностью или уверенностью в необходимости их выполнения. Доопрделяющая система также используется для формирования решения на основе нескольких источников знаний. В этом случае используются эвристические методы выбора единиц знаний из альтернативного набора, с использованием теории конфликта или нечетких множеств. Трансформирующая. В отличие от аналитических (статических) ЭС синтезирующие динамические ЭС предполагают повторяющиеся преобразования знаний в процессе решения задач. В этом случае учитывается динамика самой проблемной области, а также тех проблемных отраслей, в которых результат задач нельзя предугадать. В этих системах на основании исходных данных осуществляется генерация гипотез, а затем осуществляется проверка сформулированных гипотез на подтверждение поступивших фактов. Многоагентные. Это динамические системы, в которых БЗ сформулирована из нескольких разнородных источников знаний которые обмениваются между собой результатами на динамической основе. Вопросы для самоконтроля: 1. Дайте определение, что такое экспертная система? 2. Что входит в состав экспертных систем? 3. Какая существует технология разработки экспертных систем? 4. Как классифицируются экспертные системы? 5. Дайте определение, что такое классифицирующая экспертная система? 6. Дайте определение, что такое доопределяющая экспертная система? 7. Дайте определение, что такое трансформирующая экспертная система? 8. Дайте определение, что такое многоагентная экспертная система? ЛИТЕРАТУРА 1. Базы знаний интеллектуальных систем / Т. А. Гаврилова, В. Ф. Хорошевский— СПб: Питер, 2000. 384 с. 2. Девятков В. В,. Системы искусственного интеллекта: Учеб. пособие для вузов.— М.: Изд- во МГТУ им. Н. Э. Баумана, 2001. 352 с. 3. Зацепина С. А., Львович Я. Е., Фролов М. В. Управление в биотехнических и медицинских системах: Учеб. пособие.— Воронеж: Изд- во ВГТУ, 1994. 145 с. 4. Змитрович А. И. Интеллектуальные информационные системы.— Мн.: НТООО «ТерраСистемс», 1997. 368 с. 5. Острейковский В. А. Информатика: Учеб. для вузов.— М.: Высшая школа, 2000. 511 с. 6. А. Тейз, П. Грибоман, Ж. Луи и др. Логический подход к искусственному интеллекту: от классической логики к логическому программированию: Пер. с франц.— М.: Мир, 1990. 432 с. 7. Аверкин А. Н., Батыршин И. З., Блишун А. Ф. и др. Нечеткие множества в моделях управления и искусственного интеллекта:— М.: Наука, 1986. 312с 8. Леденева Т. М. Моделирование процесса агрегирования информации в целенаправленных системах. Воронеж: Изд. ВГТУ, 1999. 155 с. 9. П. Джексон. Введение в экспертные системы: Пер. с англ.: Учеб. пос.— М.: Издательский дом «Вильямс», 2001. 624 с. 10. Статические и динамические экспертные системы: Учеб. пособие/ Э. В. Попов, И. Б. Фоминых, Е. Б. Кисель, М. Д. Шапот.— М.: Финансы и статистика, 1996. 320 с. 11. Рындин А. А., Сапегин С. В., Хаустович А. В. Автоматизация проектирования сетей передачи данных распределенных информационно- телекомуникационных систем: Воронеж: Изд. ВГТУ, 2001, 223 с. 12. Чопоров О. Н., Бухонова О. В. Базы и банки данных: Учеб. пособие.— Воронеж: Изд- во ВГТУ, 2000. 146 с.