Экспертная система

Лекции по ТЭС для ПРО-IIIcз 1. Экспертные системы – основные понятия ..................................................................................1 2. Классификация экспертных систем .............................................................................................5 3. Модели представления знаний .....................................................................................................8 4. Основы построения и использования механизмов логического вывода................................13 5. Разработка ЭС ..............................................................................................................................17 1. Экспертные системы – основные понятия 1.1. Характеристика и назначение Главная идея использования технологии экспертных систем заключается в том, чтобы получить от эксперта его знания и, загрузив их в память компьютера, использовать всякий раз, когда в этом возникнет необходимость. Являясь одним из основных приложений искусственного интеллекта, экспертные системы представляют собой компьютерные программы, трансформирующие опыт экспертов в какой-либо области знаний в форму эвристических правил (эвристик). Эвристики не гарантируют получения оптимального результата с такой же уверенностью, как обычные алгоритмы, используемые для решения задач в рамках технологии поддержки принятия решений. Однако часто они дают в достаточной степени приемлемые решения для их практического использования. Все это делает возможным использовать технологию экспертных систем в качестве советующих систем. Экспертная система должна демонстрировать компетентность, т.е. достигать в конкретной предметной области того же уровня, что и специалисты-эксперты. Недостаточно находить хорошие решения, это надо делать быстро. Системы должны иметь не только глубокое, но и достаточно широкое понимание предмета. Сходство информационных технологий, используемых в экспертных системах и системах поддержки принятия решений, состоит в том, что обе они обеспечивают высокий уровень поддержки принятия решений. Однако имеются три существенных различия: 1. Решение проблемы в рамках систем поддержки находится на уровне понимания ее пользователем. Технология экспертных систем, наоборот, предлагает пользователю принять решение, превосходящее его возможности. 2. Способность экспертных систем пояснять свои рассуждения в процессе получения решения. Очень часто эти пояснения оказываются более важными для пользователя, чем само решение. 3. Использование нового компонента информационной технологии — знаний. Экспертные системы (ЭС) создаются для решения задач, обладающих следующими характеристиками: z отсутствие математической модели задачи и методов ее решения; z большой объем пространства (исходные данные, параметры управления, искомые переменные), в котором ищется решение; z наличие «шума» в исходных данных (ошибки, недостаточность или избыточность информации); z наличие квалифицированных экспертов в данной области; 1 z возможность структуризации (формализации) знаний предметной области Т.о., экспертная система - это информационная система, построенная на знаниях экспертов-специалистов в определенной области и предназначенная для поддержки решения не формализуемых (интеллектуальных) задач пользователей, т.е. это программа, которая заменяет эксперта в той или иной области. Преимущества экспертных систем по сравнению с использованием опытных специалистов состоят в следующем: z достигнутая компетентность не утрачивается передаваться, воспроизводиться и наращиваться; и может документироваться, z имеют место более устойчивые результаты, отсутствуют эмоциональные и другие факторы человеческой ненадежности; z высокая стоимость разработки уравновешивается низкой стоимостью эксплуатации, возможностью копирования, а в совокупности они дешевле высококвалифицированных специалистов. Отличиями экспертных систем от обычных компьютерных являются: z экспертные системы манипулируют знаниями, тогда как любые другие системы — данными; z экспертные системы, как правило, дают эффективные оптимальные решения и способны иногда ошибаться, но в отличие от традиционных компьютерных систем они имеют потенциальную способность учиться на своих ошибках. Экспертная система достигает более высокой эффективности за счет перебора большого числа альтернатив при выборе решения, опираясь на высококачественный опыт группы специалистов, анализирует влияние большого объема новых факторов, оценивая их при построении стратегий, добавляя возможности прогноза. Недостатки ЭС: z значительные трудозатраты, необходимые для пополнения базы знаний Получение знаний от экспертов и внесение их в базу знаний представляет собой сложный процесс, сопряженный с значительными затратами времени и средств. Проектирование экспертных систем также имеет определенные трудности и ограничения, которые влияют на их разработку. Важность экспертных систем состоит в следующем: • технология экспертных систем существенно расширяет круг практически значимых задач, решаемых на компьютерах, решение которых приносит значительный экономический эффект; 1.2. Структура экспертной системы В основе экспертной системы находится обширный запас знаний о конкретной проблемной области, организованные в большинстве случаев как некоторая совокупность правил, которые позволяют сделать заключения на основе исходных данных или предположений. Такой подход в корне меняет традиционную схему ДАННЫЕ + АЛГОРИТМ = ПРОГРАММА на новую ЗНАНИЯ + ЛОГИЧЕСКИЙ ВЫВОД = СИСТЕМА. 2 Для выполнения своих функций современная экспертная система должна включать в себя следующие компоненты: 1. База знаний - организованная определенным образом область памяти ЭВМ, содержащую знания как совокупность отношений между данными (фактами) из заданной предметной области. Эти отношения чаще всего представлены как правила вывода, представляющие собой долговременную информацию о том, как выводить новые факты или гипотезы из того, что сейчас известно. Измерители или блоки, их модулирующие Объект управления База данных База знаний Подсистема принятия решений Подсистема интерфейса ЭС Эксперт Оператор Рис.1. Структура ЭС 2. База данных - область памяти ЭВМ, в которой хранятся различного рода данные, факты, объекты и т.д., заданные человеком или выведенные при помощи правил, хранящихся в базе знаний, т.е. предназначена для хранения исходных и промежуточных данных решаемой в текущий момент задачи. Это наиболее подверженная изменениям область памяти ЭВМ. 3. Подсистема принятия решений - комплекс программ, решающий на основе имеющихся в системе знаний и данных, предъявляемую задачу. Решение конкретной задачи включает в себя два органически связанных и дополняющих процесса пополнение недостающих в рабочей области фактов, используя диалог с человеком, и получение новых фактов с использованием логики, порожденной системой правил заложенных в базе знаний правил вывода. В реальном мире экспертной системе как правило приходится работать в условиях той или иной степени неопределенности и неуверенности в полной достоверности фактов и данных. Такая ситуация необходимо требует использования методов нечеткой логики, использующих коэффициенты уверенности, многозначность, вероятностные оценки событий и т.п. 4. Подсистема интерфейса, осуществляющая диалоговое взаимодействие с пользователем на языке близком к естественному и ориентированная на организацию дружественного общения с пользователем как в ходе решения задач, так и в процессе приобретения новых знаний и объяснения результатов работы. Мощность экспертной системы обусловлена в первую очередь мощностью базы знаний и возможностью ее пополнения. ЭС подразделяются на два класса: статические и динамические. Статические ЭС используются в тех приложениях, где можно не учитывать изменения окружающего мира, происходящие за время решения задачи. В динамические ЭС вводятся еще два компонента: подсистема моделирования внешнего мира и подсистема связи с внешним окружением (датчики, контроллеры, СУБД и т.п.). Кроме того, традиционные компоненты статической ЭС претерпевают существенные изменения, чтобы отразить временную логику происходящих в реальном мире событий. 3 1.3. Методика применения ЭС Методика решения задач управления с помощь ЭС, как правило, делится на несколько шагов (этапов) 1. Ввод в ЭС известных руководителю исходных данных по задаче и формулировка самой задачи. 2. Выбор системой модели представления знаний и метода оптимального решения задачи и представление их руководителю. 3. Оценка руководителем предложений ЭС, утверждение их или, как правило, внесение коррективов в исходные данные и формулировку задачи. Диалог уточнения данных и самой задачи между руководителем и ЭС может занимать несколько шагов. 4. После принятия решения ЭС выдает руководителю рекомендации по принятию решения и пояснения, почему система приняла такое решение. 5. Руководитель, проанализировав рекомендуемое ЭС решение, может: z принять рекомендуемое системой решение и претворять его в жизнь; z продолжать уточнение решения задачи путем диалога с ЭС; z закончить работу с ЭС ввиду ее отказа в решении или неприемлемости предлагаемого решения. 1.4. Основные классы решаемых задач z Интерпретация данных (определение основных свойств личности по результатам психодиагностического тестирования в системах АВТАНТЕСТ); z Диагностика (диагностика и терапия сужения коронарных сосудов "ANGY", диагностика ошибок в аппаратуре и мат. Обеспечении ЭВМ "CRIB"); z Мониторинг (контроль за работой электростанций СПРИНТ, контроль аварийных датчиков на химическом заводе "FALCON"); z Проектирование (проектирование конфигураций ЭВМ "CADHELP" и др.); z Прогнозирование (предсказание погоды "WILLARD", оценки будущего урожая "PLANT", прогнозы в экономике "ECON"); z Планирование (планирование промышленных заказов "ISIS" и др.); z Обучение (обучение языку Паскаль "PROUST" и т.д.). Зарубежный опыт показывает, что экспертные системы разрабатываются в основном в университетах, научно-исследовательских центрах и коммерческих организациях, в том числе и для финансовой индустрии. В сфере финансового обслуживания эти системы помогают страховым компаниям анализировать и оценивать коммерческий риск, устанавливать размеры ссуд при кредитовании организаций, составлять сметы проектов и т.д. Опыт использования ЭС свидетельствует, что во многих случаях они помогают найти решения в сложных неформализуемых задачах НО!: искусственная компетентность экспертных систем не заменяет полностью человека. 1.5. Оболочки ЭС Оболочка экспертных систем представляет собой готовую программную среду, которая может быть приспособлена к решению определенной проблемы путем создания 4 соответствующей базы знаний. В большинстве случаев использование оболочек позволяет создавать экспертные системы быстрее и легче в сравнении с программированием. Другие термины: пустые, каркасные, наполняемые, инструментальные оболочки ЭС, среда разработки (development environment). В пустой ЭС заранее зафиксирована модель представления знаний в БЗ и методы поиска решения. Для обслуживания баз «пустой» экспертной системы предусмотрены диалоговые средства. Работая с ними, пользователь получает на экране дисплея персонального компьютера соответствующие шаблоны для заполнения, коррекции и просмотра информации из баз, т.е. оболочка – это незаполненная ЭС. Достоинство оболочек в том, что они вообще не требуют программистов для создания готовой ЭС. Требуется только специалист(ы) в предметной области для заполнения базы знаний. Однако если предметная область плохо укладывается в модель, используемую в оболочке, заполнить базу знаний в этом случае очень непросто. Примеры: EMYCIN, ЭКО, Leonardo, Nexpert Object, Kappa, EXSYS RuleBook. 2. Классификация экспертных систем 2.1.Тип приложения Тип приложения характеризуют следующие наборы параметров. 1. Возможность взаимодействия приложения с другими программными средствами: • изолированное приложение, состоящее из ЭС, не способной взаимодействовать с другими программными системами, используемыми конечным пользователем (например, с БД, электронными таблицами, пакетами прикладных программ, контроллерами, системой датчиков и т. п.); • интегрированное приложение, состоящее из ЭС и других программных систем, с которыми ЭС взаимодействует в ходе работы. Подчеркнем, что большинство современных (особенно динамических) ЭС, используемых для решения практически значимых задач, являются интегрированными. 2. Возможность исполнять приложение на разнородной аппаратуре и переносить его на различные платформы: • закрытые приложения, которые исполняются только в программной среде данной фирмы и могут быть перенесены на другие платформы только путем перепрограммирования приложения; • открытые приложения, которые ориентированы на исполнение в разнородном программно-аппаратном окружении и в идеале могут быть перенесены на другие платформы без перепрограммирования. 3. Архитектура приложения: • приложение реализуется как централизованное, на базе центральной ЭВМ, с которой связаны терминалы; • децентрализованное распределенное приложение; в настоящее время обычно используется архитектура клиент-сервер [2]. 2.2. Стадия существования Стадия существования характеризует степень проработанности и отлаженности ЭС. Обычно выделяют следующие стадии: 5 • исследовательский прототип; • действующий прототип; • промышленная система; • коммерческая система. Исследовательским прототипом называют систему, которая решает представительный класс задач приложения, но может быть неустойчива в работе и не полностью проверена. При наличии развитых инструментальных средств (ИС) для разработки исследовательского прототипа требуется примерно 2 - 4 месяца. Действующий прототип надежно решает все задачи, но для решения сложных задач может требовать чрезмерно много времени и (или) памяти. Доведение системы от начала разработки до стадии действующего прототипа требует примерно 6 - 9 месяцев. ЭС, достигшая стадии промышленной системы, обеспечивает высокое качество решений всех задач при минимуме времени и памяти. Обычно процесс преобразования действующего прототипа в промышленную систему состоит в расширении базы знаний и ее тщательной отладке. Доведение ЭС от начала разработки до стадии промышленной системы на развитом ИС требует примерно 12 - 18 месяцев. Обобщение задач, решаемых ЭС на стадии промышленной системы, позволяет перейти к стадии коммерческой системы, т.е. к системе, пригодной не только для собственного использования, но и для продажи различным потребителям. Доведение системы до коммерческой стадии требует примерно 1,5 - 2 года. Приведенные выше сроки справедливы для ЭС средней сложности. 2.2.Масштаб ЭС Многие специалисты классифицируют ЭС (приложения) по их сложности (типу используемой ЭВМ) на малые, средние, большие и символьные. 1. Малые ЭС реализуются на ПК типа PC или Mac, часто являясь изолированными ЭС. Малые ЭС обычно используются в целях первичного обучения или для исследования возможности использования технологии ЭС в данной области. 3. Средние ЭС реализуются на рабочих станциях. Они бывают изолированными и интегрированными с БД и электронными таблицами. Данные приложения охватывают весь спектр использования ЭС. 4. Большие ЭС реализуются на рабочих станциях или ЭВМ общего назначения (mainframe). Они, как правило, имеют доступ к огромным БД. 5. Символьные ЭС реализуются на символьных ЭВМ или с использованием ИС типа Lisp и Prolog. Эти ЭС, как правило, являются исследовательскими и не используются для решения реальных задач. 6 7 Принятые сокращения: ЯП – язык программирования; ФЯ – формализованный язык; ЕЯ – естественный ограниченный язык; ЯПИ – язык пиктограмм и изображений. 3. Модели представления знаний 3.1. Данные и знания Данные - это отдельные факты, характеризующие объекты, процессы и явления в предметной области, а также их свойства. При обработке данные трансформируются, условно проходя следующие этапы: • данные как результат измерений и наблюдений; • данные на материальных носителях информации (таблицы, протоколы, справочники; • модели (структуры) данных в виде диаграмм, графиков, функций; • данные в компьютере на языке описания данных; • базы данных на машинных носителях. Знания связаны с данными, основываются на них, но представляют результат мыслительной деятельности человека, обобщают его опыт, полученный в ходе выполнения какой-либо практической деятельности. Они получаются эмпирическим путем. Знания - это выявленные закономерности предметной области (принципы, связи, законы), позволяющие решать задачи в этой области. При обработке знания трансформируются аналогично данным: • знания в памяти человека как результат мышления; • материальные носители знаний (учебники, методические пособия); • поле знаний - условное описание основных объектов предметной области, их атрибутов и закономерностей, их связывающих; • знания, описанные на языках представления знаний (продукционные языки, семантические сети, фреймы - см. далее); • базы знаний. Часто используются такие определения знаний: знания - это хорошо структурированные данные, или данные о данных, или метаданные. Для хранения данных используются базы данных (для них характерны большой объем и относительно небольшая удельная стоимость информации), для хранения знаний - базы знаний (небольшого объема, но исключительно дорогие информационные массивы). База знаний - основа любой интеллектуальной системы. Знания могут быть классифицированы по следующим категориям: • поверхностные - знания о видимых взаимосвязях между отдельными событиями и фактами в предметной области; 8 • глубинные - абстракции, аналогии, схемы, отображающие структуру и процессы в предметной области. Современные экспертные системы работают в основном с поверхностными знаниями. Это связано с тем, что на данный момент нет адекватных моделей, позволяющих работать с глубинными знаниями. Кроме того, знания можно разделить на процедурные и декларативные. Исторически первичными были процедурные знания, т.е. знания, "растворенные" в алгоритмах. Они управляли данными. Для их изменения требовалось изменять программы. Однако с развитием искусственного интеллекта приоритет данных постепенно изменялся, и все большая часть знаний сосредоточивалась в структурах данных (таблицы, списки, абстрактные типы данных), т.е. увеличивалась роль декларативных знаний. Сегодня знания приобрели чисто декларативную форму, т.е. знаниями считаются предложения, записанные на языках представления знаний, приближенных к естественному и понятных неспециалистам. Существуют десятки моделей (или языков) представления знаний для различных предметных областей. Большинство из них может быть сведено к следующим классам: • продукционные; • семантические сети; • фреймы; • формальные логические модели. 3.2. Продукционная модель Продукционная модель, или модель, основанная на правилах, позволяет представить знания в виде предложений типа: Если (условие), то (действие). Под, условием понимается некоторое предложение-образец, по которому осуществляется поиск в базе знаний, а под действием - действия, выполняемые при успешном исходе поиска (они могут быть промежуточными, выступающими далее как условия, и терминальными или целевыми, завершающими работу системы). При использовании продукционной модели база знаний состоит из набора правил, Программа, управляющая перебором правил, называется машиной вывода. Чаще всего вывод бывает прямой (от данных к поиску цели) или обратный (от цели для ее подтверждения - к данным). Пример. Имеется фрагмент базы знаний из двух правил: П1: Если "отдых - летом" и "человек - активный", то "ехать в горы", П2: Если "любит солнце", то "отдых летом", Предположим, в систему поступили данные - "человек активный" и "любит "солнце" Прямой вывод - исходя из данных, получить ответ. 1-й проход. Шаг 1. Пробуем П1, не работает (не хватает данных "отдых - летом"). Шаг 2. Пробуем П2, работает, в базу поступает факт "отдых - летом". 2-й проход. 9 Шаг 1. Пробуем П1, работает, активируется цель "ехать в горы", которая и выступает как совет, который дает ЭС. Обратный вывод - подтвердить выбранную цель при помощи имеющихся правил и данных. 1-й проход. Шаг 1. Цель - "ехать в горы": пробуем П1 - данных, "отдых - летом" нет, они становятся новой целью, и ищется правило, где она в правой части. Шаг 2. Цель "отдых - летом": правило П2 подтверждает цель и активирует ее. 2-й проход. Шаг 1. Пробуем П1, подтверждается искомая цель. Продукционная модель чаще всего применяется в промышленных экспертных системах. Она привлекает разработчиков своей наглядностью, высокой модульностью, легкостью внесения дополнений и изменений и простотой механизма логического вывода. Имеется большое число программных средств, реализующих продукционный подход (язык OPS 5, EXSYS, инструментальные системы ИЭС и СПЭИС и др., а также промышленных ЭС на его основе (ФИАКР) и др.). 3.3. Семантические сети Термин семантическая означает смысловая, а сама семантика - это наука, устанавливающая отношения между символами и объектами, которые они обозначают, т.е. наука, определяющая смысл знаков. Семантическая сеть (СС) - это ориентированный граф, вершины которого - понятия, а дуги отношения между ними. Понятиями обычно выступают абстрактные или конкретные объекты, а отношения - это связи типа: "это" ("is"), "имеет частью" ("has part"), "принадлежит" и пр. Характерной особенностью семантических сетей является обязательное наличие трех типов отношений: • класс - элемент класса; • свойство - значение; • пример элемента класса. По количеству типов отношений СС бывают: • однородные (с единственным типом отношений); • неоднородные (с различными типами отношений). Наиболее часто в семантических сетях используются следующие отношения: • связи типа "часть-целое" ("класс-подкласс", "элемент-множество" и т.п.); • функциональные связи (определяемые обычно глаголами "производит", "влияет"...); • количественные (больше, меньше, равно...); • пространственные (далеко от, близко от, за, под, над...); • временные (раньше, позже, в течение...); • атрибутивные связи (иметь свойство, иметь значение...); 10 • логические связи (и, или, не) и др. Проблема поиска решения в базе знаний типа семантической сети сводится к задаче поиска фрагмента сети, соответствующего некоторой подсети, соответствующей поставленному вопросу. Пример. На рис. 3 изображена семантическая сеть. В качестве вершин понятия: Человек, Иванов, Волга. Автомобиль, Вид транспорта. Двигатель. Рис.3. Семантическая сеть. Основное преимущество модели - в соответствии современным представлениям об организации долговременной памяти человека. Недостаток модели - сложность поиска вывода на семантической сети. Для реализации семантических сетей существуют специальные сетевые языки, например NET и др. Широко известны экспертные системы, использующие семантические сети в качестве языка представления знаний - PROSPECTOR, CASNBT, TORUS. 3.4. Фреймы Под фреймом понимается абстрактный образ или ситуация. Например, слово "комната" вызывает у слушающих образ комнаты: "жилое помещение с четырьмя стенами, полом, потолком, окнами и дверью, площадью 6-20 м2 ". Из этого описания ничего нельзя убрать (например, убрав окна мы получим уже чулан, а не комнату), но в нем есть "дырки", или "слоты", - это незаполненные значения некоторых атрибутов - количество окон, цвет стен, высота потолка. покрытие пола и др. В теории фреймов такой образ называется фреймом. Фреймом называется также и формализованная модель для отображения образа. Структуру фрейма можно представить так; ИМЯ ФРЕЙМА: (имя 1-го слота: значение 1-го слота), (имя 2-го слота: значение 2-го слота), ---11 (имя N-го слота: значение N-гo слота). В качестве значения слота может выступать имя другого фрейма. Так образуют сети фреймов. Различают фреймы-образцы, или прототипы, хранящиеся в базе знаний, и фреймыэкземпляры, которые создаются для отображения реальных ситуаций на основе поступающих данных. Модель фрейма является достаточно универсальной, поскольку позволяет отобразить все многообразие знаний о мире через: • фреймы-структуры, для обозначения объектов и понятий (заем, залог, вексель); • фреймы-роли (менеджер, кассир, клиент); • фреймы-сценарии (банкротство, собрание акционеров, празднование именин); • фреймы-ситуации (тревога, авария, рабочий режим устройства) и др. Важнейшим свойством теории фреймов является заимствованное из теории семантических сетей наследование свойств. И во фреймах, и в семантических сетях наследование происходит по АКО-связям (A-Kind-Of = это). Слот АКО указывает на фрейм более высокого уровня иерархии, откуда неявно наследуются, т.е. переносятся, значения аналогичных слотов. Пример. Например, в сети фреймов на рис. 4 понятие "Ученик" наследует свойства фреймов "Ребенок" и "Человек", которые находятся на более высоком уровне иерархии. Так, на вопрос: "Любят ли ученики сладкое?" следует ответ: "Да", так как ним свойством обладают все дети, что указано во фрейме "Ребенок". Наследование свойств может быть частичным, так, возраст для учеников не наследуется ил фрейма "Ребенок", поскольку указан явно в своем собственном фрейме. Основным преимуществом фреймов как модели представления знаний является способность отражать концептуальную основу организации памяти человека, а также гибкость и наглядность. Специальные языки представления знаний в сетях фреймов FRL (Frame Representation Language) и другие позволяют эффективно строить промышленные ЭС. Широко известны такие фреймо-ориентированные экспертные системы, как ANALYST, МОДИС. 12 Рис. 4. Сеть фреймов 3.5. Формальные логические модели Традиционно в представлении знаний выделяют формальные логические модели, основанные на классическом исчислении предикатов 1 порядка, когда предметная область или задача описывается в виде набора аксиом. Исчисление предикатов 1 порядка в промышленных экспертных системах практически не используется. Эта логическая модель применима в основном в исследовательских "игрушечных" системах, так как предъявляет очень высокие требования и ограничения к предметной области. В промышленных же экспертных системах используются различные ее модификации и расширения, изложение которых выходит за рамки данного курса. 4. Основы построения и использования механизмов логического вывода Механизм логического вывода — неотъемлемая часть ЭС, реализующая функции вывода (формирования) умозаключений (новых суждений) на основе информации из базы знаний (БЗ) и рабочей памяти (РП). Как следует из определения, для работы МЛВ необходима как «долговременная» информация, содержащаяся в БЗ в выбранном при разработке ЭС виде, так и «текущая», оперативная информация, поступающая в РП после обработки в лингвистическом процессоре запроса пользователя. Таким образом, БЗ отражает основные (долговременные) закономерности, присущие предметной области. Запрос пользователя, как правило, связан с появлением каких-либо новых фактов и/или с возникновением потребности в их толковании. Перед рассмотрением конкретных МЛВ подчеркнем несколько важных обстоятельств: 13 • единого МЛВ для произвольных ЭС не существует; • МЛВ полностью определяется моделью представления знаний, принятой в данной системе; • существующие МЛВ не являются строго фиксированными («узаконенными») для каждого типа ЭС. 4.1. Механизм логического вывода в продукционных системах Из всех известных механизмов вывода данный механизм является формализованным (предопределенным). Различают два типа логического вывода: наиболее • прямой вывод (прямая цепочка рассуждений); • обратный вывод (обратная цепочка рассуждений). Сущность прямого логического вывода в продукционных ЭС состоит в построении цепочки выводов (продукций или правил), связывающих начальные факты с результатом вывода. В терминах «факты — правила» формирование цепочки вывода заключается в многократном повторении элементарных шагов «сопоставить — выполнить». Рассмотрим следующий пример. В базе знаний некоторой ЭС содержатся три правила, а в рабочей памяти до начала вывода — пять фактов: В, С, Н, G, Е (рис. 5, а). Пусть на вход системы (в РП) поступил факт А. Механизм вывода «просматривает» левые части правил с целью нахождения таких из них, которые позволяют извлечь новые факты (процедура «сопоставить»). В нашем примере на основе третьего правила выводится факт D. Происходит элементарный шаг «выполнить» — данный факт заносится в РП (рис. 5, б). Процедура «сопоставить» по фактам С и D выявляет факт F. После шага «выполнить» в РП попадает этот факт (рис. 5, в). По фактам F и В выводится факт Z, и дальнейший «просмотр» правил БЗ новой информации не дает. Рис. 5. Иллюстрация прямой цепочки рассуждений: «сопоставить»; «выполнить» Таким образом, прямая цепочка рассуждений состоит из следующих фактов: А - D - F - Z. Иными словами, из факта А на основе имеющихся в БЗ правил «получен» факт Z. Несмотря на очевидную простоту прямого вывода для пользователя ЭС, от которого требуется лишь сообщить системе о вновь поступивших или интересующих его фактах, для БЗ со значительным числом правил могут возникнуть две проблемы: 14 • когда завершить вывод?; • как обеспечить непротиворечивость правил? Последнее обстоятельство требует формирования и хранения в ЭС метаправил - правил «работы с правилами». Кроме того, прямая цепочка рассуждений иногда требует значительного времени. Механизм обратного вывода имеет иной алгоритм. Его идея заключается в проверке справедливости некоторой гипотезы (некоторого суждения, факта), которая выдвигается пользователем и проверяется ЭС. При этом осуществляется проверка истинности не левых, а правых частей продукций, а вопрос формулируется так: «Что нужно, чтобы правая часть данного правила была справедлива и есть ли необходимые суждения в рабочей памяти?» На рис. 6 показана работа механизма обратного вывода для того же примера, что и для прямой цепочки рассуждений (в предположении, что факт А занесен в РП). При реализации данного механизма пополнения РП новыми (выведенными) фактами не производится, а лишь проверяется наличие необходимых суждений на очередном шаге алгоритма. Как следует из рис. 2а, поскольку непосредственно факта Z в РП нет, производится анализ правых частей правил до поиска такого правила, которое обосновывает справедливость суждения Z. Чтобы факт Z был истинным, необходимы факты F и В. Факт В есть, факта F нет (рис. 2б). Чтобы факт В был истинным, необходимы факты С и D. Факт С есть, факта D нет (рис. 6в). Наконец, чтобы был справедлив факт D нужно наличие факта А, и так как он в РП имеется, обратный вывод закончен. Окончательный результат — на основании имеющихся в ЭС правил и фактов гипотеза о справедливости факта Z подтверждается. Рис. 6. Иллюстрация обратной цепочки рассуждений Обратная цепочка рассуждений предъявляет к квалификации пользователя ЭС определенные требования — он должен уметь формулировать «правдоподобные» гипотезы. В противном случае ЭС совершает непродуктивную работу, проверяя и отвергая одну гипотезу за другой (в качестве примера аналогичной ситуации представим себе врача, ставящего один диагноз за другим и пользующего пациента лекарствами от самых разных болезней). Платой за выполнение данного требования служит, как правило, сокращение времени реакции ЭС на запрос пользователя. Для обеспечения уверенности пользователя в получаемых ЭС суждениях после обратного вывода часто прибегают к прямой цепочке рассуждений. Совпадение результатов работы обоих механизмов служит гарантией получения истинного вывода. 15 4.2. Понятие о механизме логического вывода в сетевых системах Механизм логического вывода в сетевых системах основан на использовании двух ведущих принципов: • принцип наследования свойств; • принцип сопоставления по совпадению. Принцип наследования свойств, в свою очередь, базируется на учете важнейших связей, отражаемых в семантической сети. К таким связям относятся: • связь «есть», «является» (англ. IS-A); • связи «имеет часть», «является частью» (англ. HAS-PART, PART-OF). Последовательно переходя от одного узла сети к другому по направлению соответствующих связей, можно выявить (извлечь) новую информацию, характеризующую тот или иной узел. На рис. 7а показан малый фрагмент некоторой семантической сети и обозначена так называемая ветвь наследования свойств. Из этого фрагмента можно вывести заключения типа «Иван — человек», «у Ивана есть голова», «мужчина имеет голову» и т.п. Принцип сопоставления по совпадению основан на представлении вопроса к системе в виде фрагмента семантической сети с использованием тех же названий сущностей (узлов) и связей, что и в основной сети, и реализации процедуры «наложения» вопроса на сеть и поиска такого его положения, которое соответствует ответу на вопрос. На рис. 7б, помимо уже известной связи «есть», представлено отношение владения (связь «владеет»). Вопрос «Чем владеет Иван?» формализуется с помощью узла «Иван» и отношения «владеет». Далее в простейшем случае осуществляется перебор узлов сети, имеющих имя «Иван» (если они имеются) и поиск такого из них, который имеет связь «владеет». Далее может быть задействован принцип наследования свойств. Ответами на поставленный в примере вопрос будут суждения «Иван владеет автомобилем» и «Иван владеет (автомобилем) ВАЗ 2105». Понятно, что в практике использования ЭС такого типа приходится реализовывать значительно более сложную процедуру поиска, включающую элементы семантического анализа. Рис. 7. Иллюстрация механизма логического вывода в семантической сети 16 4.3. Понятие о механизме логического вывода во фреймовых системах Обычно фреймовая модель знаний имеет сложную иерархическую структуру, отражающую реальные объекты (понятия) и отношения (связи) некоторой предметной области. Механизм логического вывода в таких ЭС основан на обмене значениями между одноименными слотами различных фреймов и выполнении присоединенных процедур «если-добавлено», «если-удалено» и «если-нужно». Условная схема таких действий для простейшего варианта представлена на рис. 8. Рис. 8. Иллюстрация механизма вывода во фреймовой модели Запрос к ЭС в виде сообщения поступает в старший по иерархии фрейм (фрейм А). Если ответа на запрос нет ни в одном из слотов этого фрейма или их совокупности, соответствующие сообщения (запросы) передаются во все фреймы, где имеются слот (слоты), имена которых содержатся в запросе или необходимы для поиска ответа на него (фреймы В и D). Если в них содержится искомый ответ, значение соответствующего слота передается в старший по иерархии фрейм (из фрейма D во фрейм А). Если для этого нужна дополнительная информация, предварительно передается сообщение (из фрейма В во фрейм С) и получается значение (из фрейма С во фрейм В). Значения, передаваемые в ответ на сообщения, либо непосредственно содержатся в соответствующих слотах фреймов, либо определяются как результат выполнения присоединенных процедур. В современных фреймовых системах, как правило, для пользователя реализована возможность формулировать запросы на языке, близком к реальному. Интерфейс (лингвистический процессор) должен «уметь» по результатам анализа запроса определять, в какой/какие слот/слоты необходимо поместить значение/значения для инициализации автоматической процедуры поиска ответа. 5. Разработка ЭС Минимальный коллектив разработчиков ЭС: 1. инженер по знаниям (аналитик) 2. эксперт 3. программист 4. пользователь 17 Роли разработчиков (эксперт, программист, пользователь и аналитик) постоянными на протяжении всей разработки. Совмещение ролей нежелательно. являются После того как инженер по знаниям убедился, что: ¾ данная задача может быть решена с помощью экспертной системы; ¾ экспертную систему можно создать предлагаемыми на рынке средствами; ¾ имеется подходящий эксперт; ¾ предложенные критерии производительности являются разумными; ¾ затраты и срок их окупаемости приемлемы для заказчика, он составляет план разработки. План определяет шаги процесса разработки и необходимые затраты, а также ожидаемые результаты. 5.1. Разработка прототипа Прототипная система является усеченной версией экспертной системы, спроектированной для проверки правильности кодирования фактов, связей и стратегий рассуждения эксперта. Объем прототипа — несколько десятков правил, фреймов или примеров. Стадии разработки прототипа ЭС (рис. 9): Э+А+П Идентификация проблемы Проблема А+Э Получение знаний Знания А Структурирование Поле знаний А+Пр Формализация БЗ на языке представления знаний Пр Реализация прототипа Программа-прототип ЭС Э+А+Пр+ П Тестирование Рис. 9. Стадии разработки прототипа ЭС: Э — эксперт; А — аналитик (инженер по знаниям); Пр — программист; П — пользователь 5.1.1. Идентификация проблемы Уточняется формулировка (спецификация) задачи, планируется ход разработки прототипа экспертной системы, определяются: ¾ необходимые ресурсы (время, люди, компьютеры, деньги и т. д.) ¾ источники знаний (книги, дополнительные эксперты, методики); ¾ имеющиеся аналогичные экспертные системы; 18 ¾ цели (распространение опыта, автоматизация рутинных действий и др.); ¾ классы решаемых задач и т. д. Идентификация проблемы — знакомство и обучение членов коллектива разработчиков, а также создание неформальной спецификации задачи. Средняя продолжительность 1—2 недели. 5.1.2. Извлечение знаний На этой стадии происходит перенос знаний от эксперта к инженеру по знаниям с использованием различных методов (см. гл. 2): ¾ анализ текстов; ¾ дискуссии; ¾ диалоги; ¾ интервью; ¾ экспертные игры; ¾ наблюдение ¾ лекции; Извлечение знаний — получение инженером по знаниям наиболее полного из возможных представлений о предметной области и способах принятия решения в ней. Средняя продолжительность 1—3 месяца. 5.1.3. Структурирование или концептуализации Через выявление структуры полученных знаний о предметной области определяются: ¾ терминология; ¾ список основных понятий и их атрибутов; ¾ отношения между понятиями; ¾ структура входной и выходной информации; ¾ стратегия принятия решений; ¾ ограничения стратегий и т. д. Структурирование (или концептуализация) знаний — разработка неформального наглядного описания знаний о предметной области в виде графа, таблицы, диаграммы или текста, которое отражает основные концепции и взаимосвязи между понятиями предметной области. Такое описание называется полем знаний. Средняя продолжительность этапа 2—4 недели. 5.1.4. Формализация знаний Строится формализованное представление концепций предметной области на основе выбранного языка представления знаний (ЯПЗ). Традиционно на этом этапе используются: ¾ логические методы (исчисления предикатов 1-го порядка и др.); ¾ продукционные модели (с прямым и обратным выводом); ¾ семантические сети; 19 ¾ фреймы; ¾ объектно-ориентированные языки, основанные на иерархии классов, объектов. Формализация знаний — разработка базы знаний на языке представления знаний, который, с одной стороны, соответствует структуре поля знаний, а с другой - позволяет реализовать прототип системы на следующей стадии программной реализации. Все чаще на этой стадии используется симбиоз языков представления знаний, например, фреймы + семантические сети + полный набор возможностей языка исчисления предикатов. Средняя продолжительность 1—2 месяца. 5.1.5. Программная реализация Создается прототип экспертной системы, включающий базу знаний и остальные блоки, при помощи одного из следующих способов: ¾ программирование на традиционных языках типа Pascal, C++ и др.; ¾ программирование на специализированных языках, применяемых искусственного интеллекта: LISP, FRL , SMALLTALK и др.; в задачах ¾ использование инструментальных средств разработки ЭС (G2); ¾ использование оболочек. Программная реализация — разработка программного комплекса, демонстрирующего жизнеспособность подхода в целом. Чаще всего первый прототип отбрасывается на этапе реализации действующей ЭС. 5.1.6. Тестирование Оценивается и проверяется работа программ прототипа с целью приведения в соответствие с реальными запросами пользователей. Прототип проверяется: ¾ на удобство и адекватность интерфейсов ввода/вывода (характер вопросов в диалоге, связность выводимого текста результата и др.); ¾ на эффективность стратегии управления (порядок перебора, использование нечеткого вывода и др.); ¾ на качество проверочных примеров; ¾ на корректность базы знаний (полнота и непротиворечивость правил). Тестирование — выявление ошибок в подходе и реализации прототипа и выработка рекомендаций по доводке системы до промышленного варианта. Средняя продолжительность 1—2 недели. 20 Переформулирование Перепроектирование Требования Как охарактеризо вать важные аспекты знаний? Понятия Какие понятия необходимы для решения? Идентификация Уточнение Структура Как формально представить знания? Концептуализация Правила Какие правила воплощают знания? Формализация Как подтвердить правила? Реализация Тестирование Рис. 10. Этапы разработки ЭС Процедуры уточнения, перепроектирования и переформулирования (рис.10) не являются обязательными и характерны для разработки достаточно сложных ЭС и предполагают проведение нескольких итераций. Но сами этапы являются обязательными. 5.2. Развитие прототипа до промышленной ЭС При неудовлетворительном функционировании прототипа эксперт и инженер по знаниям имеют возможность оценить, что именно будет включено разработку окончательного варианта системы. Если первоначально выбранные объекты или свойства оказываются неподходящими, их необходимо изменить. Выделяют следующие этапы для перехода: ¾ демонстрационный прототип; ¾ исследовательский прототип; ¾ действующий прототип; ¾ промышленная система; ¾ коммерческая система. Однако чаще реализуется плавный переход от демонстрационного прототипа к промышленной системе, при этом, если программный инструментарий был выбран удачно, не обязательно даже переписывать окончательный вариант другими программными средствами. Демонстрационный прототип ЭС - система решает часть задач, демонстрируя жизнеспособность подхода (несколько десятков правил или понятий). Размер – 10-100 правил БЗ. Исследовательский прототип ЭС - система решает большинство задач, но неустойчива в работе и не полностью проверена (несколько сотен правил или понятий). 200-500 правил. Действующий прототип ЭС - система надежно решает все задачи на реальных примерах, но для сложной задачи требует много времени и памяти. 500-1000 правил. Промышленная система - система обеспечивает высокое качество решений при минимизации требуемого времени и памяти; переписывается с использованием более эффективных средств представления знаний. 1000-1500 правил. 21 Коммерческая система - промышленная система, пригодная документирована и снабжена сервисом. 1500-3000 правил. к продаже, хорошо Основная работа на данном этапе заключается в существенном расширении базы знаний, т. е. в добавлении большого числа дополнительных правил, фреймов, узлов семантической сети или других элементов знаний. Эти элементы знаний обычно увеличивают глубину системы, обеспечивая большее число правил для трудноуловимых аспектов отдельных случаев. В то же время эксперт и инженер по знаниям могут увеличить базу знаний системы, включая правила, управляющие дополнительными подзадачами или дополнительными аспектами экспертной задачи (метазнания). После установления основной структуры ЭС знаний инженер по знаниям приступает к разработке и адаптации интерфейсов, с помощью которых система будет общаться с пользователем и экспертом. Необходимо обратить особое внимание на языковые возможности интерфейсов, их простоту и удобство для управления работой ЭС. Система должна обеспечивать пользователю возможность легким и естественным образом уточнять непонятные моменты, приостанавливать работу и т. д. В частности, могут оказаться полезными графические представления. Затем проводится тестирование системы. 22