Авторы: Новикова В.А.
Андреева Е.Ю.
Туйкина Д.К.

КГУ, кафедра Прикладной математики, гр 947.

 

Искусственный интеллект и экспертные системы

  1. Искусственный интеллект и экспертные системы

    1.1. Основные понятия искусственного интеллекта
    1.2. История развития искусственного интеллекта
    1.3. Задачи искусственного интеллекта
    1.4. Экспертные системы - направление исследований по искусственному интеллекту
    1.5. Классификация и виды экспертных систем
    1.6. Область применения экспертных систем
  2. Структура и функционирование экспертных систем

    2.1. Типовая структура экспертных систем
    2.2. Интерфейс пользователя
    2.3. Подсистема приобретения знаний
    2.4. База знаний
    2.5. База данных
    2.6. Механизм логического вывода
    2.7. Объяснение решений
    2.8. Функционирование экспертных системах
  3. Представление знаний

    3.1. Основные понятия и состав знаний
    3.2. Модели представления знаний
    3.3. Представление нечетких знаний
  4. Методы поиска решений

    4.1. Поиск решений в одном пространстве
    4.2. Поиск решений в иерархии пространств
    4.3. Поиск решений в альтернативных пространствах
    4.4. Поиск решений с использованием нескольких моделей
    4.5. Выбор метода решения задач
  5. Инструментальные средства разработки экспертных систем

    5.1. Классификация инструментальных средств
    5.2. Языки программирования
    5.3. Языки инженерии знаний
    5.4. Средства автоматизации разработки экспертных систем
    5.5. Оболочки экспертных систем
  6. Технология разработки экспертных систем

    6.1. Стадии создания экспертных систем
    6.2. Этапы разработки экспертных систем
    6.3. Разработка прототипа экспертной системы



1.1 Основные понятия искусственного интеллекта.

Достаточно трудно дать точное определение, что такое интеллект человека, потому что интеллект - это сплав многих навыков в области обработки и представления информации. Интеллект ( intelligence ) происходит от латинского intellectus - что означает ум, рассудок, разум; мыслительные способности человека. С большой степенью достоверности интеллектом можно называть способность мозга решать (интеллектуальные) задачи путем приобретения, запоминания и целенаправленного преобразования знаний в процессе обучения на опыте и адаптации к разнообразным обстоятельствам.
Искусственный интеллект (ИИ) - совокупность научных дисциплин, изучающих методы решения задач интеллектуального (творческого) характера с использованием ЭВМ.
Искусственный интеллект - одно из направлений информатики, целью которого явлвется разработка аппаратно-программных средств, позволяющих пользователю-непрограммисту ставить и решать свои, традиционно считающиеся интеллектуальными задачи, общаясь с ЭВМ на ограниченном подмножестве естественного языка.
[9]
Системы искусственного интеллекта (СИИ) - это системы, созданные на базе ЭВМ, которые имитируют решение человеком сложных интеллектуальных задач.
Знания: в общем случае знание - проверенный практикой результат познания действительности, верное ее отражение в мышлении человека, обладание опытом и пониманием, которые являются правильными и в субъективном, и в объективном отношении, на основании которых можно по-строить суждения и выводы, кажущиеся достаточно надежными для того, чтобы рассматриваться как знание. Поэтому в контексте ИТ термин зна-ния - это информация, присутствующая при реализации интеллектуальных функций. Обычно это отклонения, тенденции, шаблоны и зависимости, обнаруженные в информации Другими словами, интеллектуальные системы являются в то же время системами обработки знаний.

1.2 История развития искусственного интеллекта

В развитии СИИ можно выделить три основных этапа:

1.3 Задачи искусственного интеллекта

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

  1. доказательства теорем;
  2. распознавание образов;
  3. робототехника;
  4. моделирование игр;
  5. инженерия знаний;
  6. экспертные системы
1.4 Экспертные системы - направление исследований по искусственному интеллекту

В середине семидесятых годов в исследованиях по искусственному интеллекту сформировалось самостоятельное направление, получившее название экспертные системы. Цель исследований по экспертным системам состоит в разработке программ (устройств), которые при решении задач, трудных для эксперта-человека, получают результаты, не уступающие по качеству и эффективности решениям, получае-мым экспертом. В большинстве случаев экспертные системы решают трудно формализуемые задачи или задачи, не имеющие алгоритмического решения.
Рассмотрим несколько определений.
Экспертная система - программно-техническое средство, позволяющее пользователю в диалоговом режиме получать от компьютера консультационную помощь в конкретной предметной области, где сконцентрированы опыт и знания людей-экспертов (специалистов в данной области).
Экспертные системы - программы для компьютера, которые могут воспроизводить процесс решения проблемы человеком-экспертом.
[2]
Эспертная система - программа, которая использует знания специалистов (экспертов) о некоторой конкретной узко специализированной предметной области и в пределах этой области срособна принимать решения на уровне эксперта-профессилнала. [13]
Экспертные системы - прикладные программы ИИ, в которых база знаний представляет собой формализованные эмпирические знания высококвалифицированных специалистов (экспертов) в какой-либо узкой предметной области.[14]
Экспертная система - программа для компьютрера, которая оперирует со знаниями в определенной предметной области с целью выработки рекомендаций или решения проблем.[14]
В основе функционирования ЭС лежит использование знаний, а манипулирование ими осуществляется на базе эвристических правил, сформулированных экспертами. ЭС выдают советы, проводят анализ, выполняют классификацию, дают консультации и ставят диагноз. Они ориентированы на решение задач, обычно требующих проведения экспертизы человеком-специалистом. В отличие от машинных программ, использующий процедурный анализ, ЭС решают задачи в узкой предметной области (конкретной области экспертизы) на основе дедуктивных рассуждений. Главное достоинство экспертных систем - возможность накапливать знания, сохранять их длительное время, обновлять и тем самым обеспечивать относительную независимость конкретной организации от наличия в ней квалифицированных специалистов.[1]

1.5 Классификация и виды экспертных систем

Для классификации ЭС [4] используют следующие признаки:

  • Способ формирования решения;
  • Способ учета временного признака;
  • Вид используемых данных;
  • Число используемых источников решения знаний;

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

1.6 Область применения экспертных систем

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

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

Критерий применимости ЭС.

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

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

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

  4. Прогнозирующие системы предсказывают возможные результаты или события на основе данных о текущем состоянии объекта. Программная система "Завоевание Уолл-Стрита" может проанализировать конъюнктуру рынка и с помощью статистических методов алгоритмов разработать для вас план капиталовложений на перспективу. Она не относится к числу систем, основанных на знаниях, поскольку использует процедуры и алгоритмы традиционного программирования. Хотя пока еще отсутствуют ЭС, которые способны за счет своей информации о конъюнктуре рынка помочь вам увеличить капитал, прогнозирующие системы уже сегодня могут предсказывать погоду, урожайность и поток пассажиров. Даже на персональном компьютере, установив простую систему, основанную на знаниях, вы можете получить местный прогноз погоды.
  5. Планирование.

  6. Планирующие системы предназначены для достижения конкретных целей при решении задач с большим числом переменных. Дамасская фирма Informat впервые в торговой практике предоставляет в распоряжении покупателей 13 рабочих станций, установленных в холле своего офиса, на которых проводятся бесплатные 15-минутные консультации с целью помочь покупателям выбрать компьютер, в наибольшей степени отвечающий их потребностям и бюджету. Кроме того, компания Boeing применяет ЭС для проектирования космических станций, а также для выявления причин отказов самолетных двигателей и ремонта вертолетов. Экспертная система XCON, созданная фирмой DEC, служит для определения или изменения конфигурации компьютерных систем типа VAX и в соответствии с требованиями покупателя. Фирма DEC разрабатывает более мощную систему XSEL, включающую базу знаний системы XCON, с целью оказания помощи покупателям при выборе вычислительных систем с нужной конфигурацией. В отличие от XCON система XSEL является интерактивной.
  7. Интерпретация.

  8. Интерпретирующие системы обладают способностью получать определенные заключения на основе результатов наблюдения. Система PROSPECTOR, одна из наиболее известных систем интерпретирующего типа, объединяет знания девяти экспертов. Используя сочетания девяти методов экспертизы, системе удалось обнаружить залежи руды стоимостью в миллион долларов, причем наличие этих залежей не предполагал ни один из девяти экспертов. Другая интерпретирующая система- HASP/SIAP. Она определяет местоположение и типы судов в тихом океане по данным акустических систем слежения.
  9. Контроль и управление.

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

  12. В этой сфере системы, основанные на знаниях, незаменимы как при ремонте механических и электрических машин (автомобилей, дизельных локомотивов и т.д.), так и при устранении неисправностей и ошибок в аппаратном и программном обеспечении компьютеров.[5], [6], [7]
  13. Обучение.

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

Наиболее известные ЭС, разработанные в 60-70-х годах, стали в своих областях уже классическими. По происхождению, предметным областям и по преемственности применяемых идей, методов и инструментальных программных средств их можно разделить на несколько семейств.
  1. META-DENDRAL.

  2. Система DENDRAL позволяет определить наиболее вероятную структуру химического соединения по экспериментальным данным (масс- спектрографии, данным ядерном магнитного резонанса и др.).М-D автоматизирует процесс приобретения знаний для DENDRAL. Она генерирует правила построения фрагментов химических структур.
  3. MYCIN-EMYCIN-TEIREIAS-PUFF-NEOMYCIN.

  4. Это семейство медицинских ЭС и сервисных программных средств для их построения.
  5. PROSPECTOR-KAS.

  6. PROSPECTOR- предназначена для поиска (предсказания) месторождений на основе геологических анализов. KAS- система приобретения знаний для PROSPECTOR.
  7. CASNET-EXPERT.

  8. Система CASNET- медицинская ЭС для диагностики выдачи рекомендаций по лечению глазных заболеваний. На ее основе разработан язык инженерии знаний EXPERT, с помощью которой создан ряд других медицинских диагностических систем.
  9. HEARSAY-HEARSAY-2-HEARSAY-3-AGE.

  10. Первые две системы этого ряда являются развитием интеллектуальной системы распознавания слитной человеческой речи, слова которой берутся из заданного словаря. Эти системы отличаются оригинальной структурой, основанной на использовании доски объявлений - глобальной базы данных, содержащей текущие результаты работы системы. В дальнейшем на основе этих систем были созданы инструментальные системы HEARSAY-3 и AGE (Attempt to Generalize- попытка общения) для построения ЭС.
  11. Системы AM (Artifical Mathematician- искусственный математик) и EURISCO.

  12. Были разработаны в Станфордском университете доктором Д. Ленатом для исследовательских и учебных целей.
  13. Среди современных коммерческих систем хочется выделить экспертную систему - оболочку G2 американской фирмы Gensym (USA) [8] как непревзойденную экспертную коммерческую систему для работы с динамическими объектами. Работа в реальном времени с малыми временами ответа часто необходима при анализе ситуаций в корпоративных информационных сетях, на атомных реакторах, в космических полетах и множестве других задач. В этих задачах необходимо принимать решения в течение миллисекунд с момента возникновения критической ситуации.
  14. В качестве примера быстродействующей системы для отслеживания состояния корпоративной информационной сети (КИС) можно привести основанную на знаниях систему мониторинга OMEGAMON [10] фирмы Candle (IBM с 2004 г.) . OMEGAMON - типичный представитель современных экспертных мультиагентных динамических систем, работающих в реальном времени. OMEGAMON позволяет за считанные минуты ввести и отладить правила мониторинга внештатных ситуаций для объектов КИС.
Итак, основными областями применения ЭС являются:
  • медицина
  • электроника
  • вычислительная техника
  • геология
  • математика
  • космос
  • сельское хозяйство
  • управление
  • финансы
  • юриспруденция и т.д.
В России исследования и разработки в области ЭС включены в ряд государственных и отраслевых научно-технических программ. Системы с базами знаний не только стали находить практическое применение в бизнесе и в решении серьезных информационных задач, но и продемонстрировали ощутимый эффект от их использования. Например, чрезвычайно эффективными с точки зрения применения ЭС оказались системы поддержки организационного управления и планирования распределения ресурсов.

2.1 Типовая структура экспертных систем

Обобщенная структура экспертной системы представлена на рисунке [17]. Следует учесть, что реальные ЭС могут иметь более сложную структуру, однако блоки, изображенные на рисунке, непременно присутствуют в любой действительно экспертной системе, поскольку представляют собой стандарт структуры современной ЭС.


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

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

2.3 Подсистема приобретения знаний

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

2.4 База знаний

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

2.5 База данных

База данных (рабочая память) предназначена для хранения исходных и промежуточных данных решаемой в текущий момент задачи.[3]

2.6 Механизм логического вывода

Основу ЭС составляет подсистема логического вывода [13] , которая использует информацию из базы знаний (БЗ), генерирует рекомендации по решению искомой задачи. Чаще всего для представления знаний в ЭС используются системы продукций и семантические сети. Допустим, БЗ состоит из фактов и правил (если <посылка> то <заключение>). Если ЭС определяет, что посылка верна, то правило признается подходящим для данной консультации и оно запускается в действие. Запуск правила означает принятие заключения данного правила в качестве составной части процесса консультации. Цель ЭС - вывести некоторый заданный факт, который называется целевым утверждением (то есть в результате применения правил добиться того, чтобы этот факт был включен в рабочее множество), либо опровергнуть этот факт (то есть убедиться, что его вывести невозможно, следовательно, при данном уровне знаний системы он является ложным). Целевое утверждение может быть либо "заложено" заранее в базу знаний системы, либо извлекается системой из диалога с пользователем. Работа системы представляет собой последовательность шагов, на каждом из которых из базы выбирается некоторое правило, которое применяется к текущему содержимому рабочего множества. Цикл заканчивается, когда выведено либо опровергнуто целевое утверждение. Цикл работы экспертной системы иначе называется логическим выводом Логический вывод может происходить многими способами, из которых наиболее распространенные - прямой порядок вывода и обратный порядок вывода. Прямой порядок вывода - от фактов, которые находятся в рабочем множестве, к заключению. Если такое заключение удается найти, то оно заносится в рабочее множество. Прямой вывод часто называют выводом, управляемым данными. Для иллюстрации добавим к нашему примеру базы знаний о погоде еще одно правило:

ЕСЛИ скоро пойдет дождь

ТО нужно взять с собой зонтик. (правило2)

Предположим также, что факты "Небо покрыто тучами" и "Барометр падает" имеются в рабочем множестве, а целью системы является ответ на вопрос пользователя: "Нужно взять с собой зонтик?"
При прямом выводе работа системы будет протекать следующим образом:

Шаг 1. Рассматривается правило 1. Его условие истинно, так как оба элемента конъюнкции имеются в рабочем множестве. Применяем правило 1; добавляем к рабочему множеству факт "Скоро пойдет дождь".
Шаг 2. Рассматривается правило 2. Его условие истинно, т.к. утверждение из условия имеется в рабочем множестве. Примеряем правило 2; добавляем к рабочему множеству факт "Нужно взять с собой зонтик". Целевое утверждение выведено.
Обратный порядок вывода: заключения просматриваются до тех пор, пока не будет обнаружены в рабочей памяти или получены от пользователя факты, подтверждающие одно из них. В системах с обратным выводом вначале выдвигается некоторая гипотеза, а затем механизм вывода в процессе работы, как бы возвращается назад, переходя от нее к фактам, и пытается найти среди них те, которые подтверждают эту гипотезу. Если она оказалась правильной, то выбирается следующая гипотеза, детализирующая первую являющаяся по отношению к ней подцелью. Далее отыскиваются факты, подтверждающие истинность подчиненной гипотезы. Вывод такого типа называется управляемым целями. Обратный поиск применяется в тех случаях, когда цели известны и их сравнительно немного.

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

Шаг 1. Рассматривается правило 1. Оно не содержит цели в правой части. Переходим к правилу 2.
Шаг 2. Рассматривается правило 2. Оно содержит цель в правой части правила. Переходим к правой части правила и рассматриваем в качестве текущей цели утверждения "Скоро пойдет дождь".
Шаг 3. Текущей цели нет в рабочем множестве. Рассмотрим правило 1, которое содержит цель в правой части. Обе компоненты его условия имеются в рабочем множестве, так что условие истинно. Применяем привило 1; в результате выводим утверждение "Скоро пойдет дождь"; которое было нашей предыдущей целью.
Шаг 4. Применяем правило 2. условием которого является данное утверждение. Получаем вывод исходного утверждения.

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

2.7 Объяснение решений

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

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

Как видно из этого примера, в ходе консультации инициатива диалога принадлежит системе, а сама консультация у ЭС выглядит так же, как и консультация у эксперта- человека: задается ряд вопросов и на основании их анализа выдается экспертное заключение. Однако в отличие от беседы со специалистом, диалог с ЭС имеет свои психологические особенности: большинство пользователей (по вполне понятным причинам, таким, как отсутствие опыта работы на компьютерах, лаконичность диалога с ЭС, отсутствие пояснений в ходе консультации и другим) склонны меньше доверять "мнению" ЭС, чем мнению "живого" эксперта. Чтобы удостовериться в "разумности" и "компетентности" ЭС, пользователь может обратиться к ее подсистеме объяснения. Рассмотрим теперь работу подсистемы объяснения. Для получения объяснения в процессе консультации пользователь может "перехватить инициативу" диалога в тот момент, когда система задает очередной вопрос, "переспросив" в ответ систему, почему она его задала. Таким образом, вместо ответа на вопрос системы, пользователь может задать ей встречный вопрос: ПОЧЕМУ? (" Почему система задала такой вопрос?"). Система интерпретирует вопрос "Почему?" в "понятных" ей терминах дерева вывода, поднимаясь по нему на один ярус выше и находя правило, для применения которого система задает этот вопрос. Пользователю выдается информация об этом правиле, о состоянии вычисления его условиям о заключении данного правила (текущей цели). Пусть в нашем примере диалога с ЭС пользователь вместо ответа на вопрос системы: "Верно ли, что барометр падает?" задает ей встречный вопрос: "ПОЧЕМУ?". ЭС обращается к подсистеме объяснения, которая выдает пользователю следующее сообщение:

[1.0] Эта информация необходима, чтобы установить, что скоро пойдет дождь.
Ранее было установлено, что:
[1.1] Небо покрыто тучами.
Следовательно, если:
[1.2] Барометр падает, то скоро пойдет дождь.(Правило 1).

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

ПОЧЕМУ?
("Почему необходимо установить, что скоро пойдет дождь?"). Второй ответ системы аналогичен первому; в нем указывается, что это необходимо для применения правила 2 с целью установить, что нужно взять с собой зонтик:
[2.0] Эта информация необходима, чтобы установить, что нужно взять с собой зонтик. Если: [2.1] Скоро пойдет дождь, то нужно взять с собой зонтик. (Правило 2).

Утверждение [2.0] является исходным целевым утверждением системы. Таким образом, теперь ход рассуждений системы пользователю полностью понятен. Вопрос "ПОЧЕМУ?" позволяет проследить ход рассуждений системы от посылок к заключениям. Однако для более детального осмысления процесса вывода удобно было бы иметь возможность изучать его и в противоположном порядке- от заключений к посылкам. Для этого служит другой вопрос, который также "понимает" подсистема объяснений:

КАК N?

где N- номер утверждения, выданный подсистемой объяснения на одном из предыдущих шагов диалога. Например, в ответ на вопрос:

КАК 2.0?

"Как получен утверждение 2.0?" подсистема объяснения выдает информацию в правиле, которое было применено для его получения: [3.1] Используется правило 2, заключением которого является, что нужно взять с собой зонтик. Чтобы получить более подробную информацию о том, как было использовано правило 2, следует повторно задать вопрос "КАК?":

КАК 3.1? "Как было использовано правило 2?".
Ответ системы: Ранее установлено, что: [4.1] Скоро пойдет дождь. Следовательно, нужно взять с собой зонтик. Выясним теперь, как получено утверждение 4.1:

КАК 4.1?
Ответ системы: [5.1] Используется правило 1, заключением которого является, что скоро пойдет дождь. Наконец, выясним, как использовано правило 1:

КАК 5.1?
Ответ системы:
Ранее установлено, что:
[6.1] Небо покрыто тучами.
[6.2] Барометр падает.
Следовательно, скоро пойдет дождь.

Как были получены утверждения 6.1 и 6.2, пользователь помнит, поскольку он отвечал на вопросы системы относительно этих утверждений. Если все же он задаст системе вопрос КАК 6.1? или КАК 6.2?, то система напомнит ему об этом. Описанная модель объяснения используется в системе MYCIN. Достоинством ее является возможность получения объяснения любого шага работы системы, недостатком - жесткая привязка к дереву вывода. Для пользователя- непрограммиста такой способ объяснения может показаться излишне детализованным и слишком формальным, а нужно было бы объяснение на "более высоком уровне"- с точки зрения здравого смысла и без углубления в детали. Подобные модели объяснения только начинают появляться в ЭС и требуют более сложной организации знаний.

2.8 Функционирование ЭС

ЭС работает в двух режимах [3]:

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

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

3.1 Основные понятия и состав знаний.

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

Состав знаний.

    В отличие от данных знания обладают следующими свойствами:

  1. Внутренняя интерпретируемость.

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

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

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

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

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

    Также знания можно разделить на:

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

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

3.2 Модели представления знаний.

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

    Типичными моделями представления знаний являются:

  • Продукционная модель;
  • Модель, основанная на использовании фреймов;
  • Модель семантической сети;
  • Логическая модель.

Продукционная модель.

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

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

        ЕСЛИ клиент работает на одном месте более двух лет,
        ТО клиент имеет постоянную работу.
[11]

    Как условие, так и действие правила могут учитывать несколько выражений, объединенных логическими связками И, ИЛИ, НЕ:

        ЕСЛИ клиент имеет постоянную работу
        И клиенту более 18 лет
        И клиент НЕ имеет финансовых обязательств,
        ТО клиент может претендовать на получение кредита.[11]

    Помимо продукционных правил база знаний должна включать и простые факты, поступающие в систему через интерфейс пользователя или выводимые в процессе поиска решения задачи. Факты являются простыми утверждениями типа 'клиент работает на одном месте более двух лет'. И когда в процессе интерпретации правил машиной вывода какой-либо факт согласуется с частью правила ЕСЛИ, то выполняется действие, определяемое частью ТО этого правила. Новые факты, добавляемые в базу знаний в результате действий, описанных в правилах, также могут быть использованы для сопоставления с частями ЕСЛИ других правил. Последовательное сопоставление частей правил ЕСЛИ с фактами порождает цепочку вывода. Цепочка вывода, полученная в результате последовательного выполнения правил П1 и П2 показана ниже (см. Рисунок 1. Пример цепочки вывода.). Эта цепочка показывает, как на основании правил и исходных фактов выводится заключение о возможности получения кредита. Цепочки вывода экспертной системы могут быть предъявлены пользователю и помогают понять, как было получено решение.

Рисунок 1. Пример цепочки вывода.[11]

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


Фреймовая модель.

    Впервые термин 'фрейм' был предложен в 70-е годы Марвином Минским [12], который определил его следующим образом:
    'Фрейм - это структура данных, представляющая стереотипную ситуацию, вроде нахождения внутри некоторого рода жилой комнаты, или сбора на вечеринку по поводу дня рождения ребенка. К каждому фрейму присоединяется несколько видов информации. Часть этой информации - о том, как использовать фрейм. Часть о том, чего можно ожидать далее. Часть о том, что следует делать, если эти ожидания не подтвердятся'.
    Фрейм - это минимальное возможное описание сущности какого-либо явления, события, ситуации, процесса или объекта. Минимальность означает, что при дальнейшем упрощении описания теряется его полнота, она перестает определять ту единицу знаний, для которой предназначено. Например, слово "комната" вызывает у слушающих образ комнаты: "жилое помещение с четырьмя стенами, полом, потолком, окнами и дверью, площадью 6-20 м2 ". Из этого описания ничего нельзя убрать (например, убрав окна мы получим уже чулан, а не комнату), но в нем есть "дырки", - это незаполненные значения некоторых атрибутов - количество окон, цвет стен, высота потолка. покрытие пола и др. [11].     В теории фреймов такой образ называется фреймом.
    Фрейм имеет определенную структуру, состоящую из множества элементов - слотов. Каждый слот в свою очередь, представляется определенной структурой данных, процедурой, или может быть связан с другим фреймом.

    Структуру фрейма можно представить так:

ИМЯ ФРЕЙМА :
(имя 1-го слота: значение 1-го слота),
(имя 2-го слота: значение 2-го слота),
- - - -
(имя N-го слота: значение N-гo слота).

    Ту же запись представим в виде таблицы, дополнив двумя столбцами.

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

  1. Процедура на событие 'если добавлено' (IF-REMOVED). Выполняется, когда новая информация записывается в слот.
  2. Процедура на событие 'если удалено' (IF-ADDED). Выполняется, когда информация удаляется из слота.
  3. Процедура на событие 'по требованию' (IF-NEEDED). Выполняется, когда запрашивается информация из пустого слота.

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

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

    Важнейшим свойством теории фреймов является заимствованное из теории семантических сетей наследование свойств. И во фреймах, и в семантических сетях наследование происходит по АКО-связям (A-Kind-Of = это). Слот АКО указывает на фрейм более высокого уровня иерархии, откуда неявно наследуются, т.е. переносятся, список и значения слотов. Возможно наследование свойств от нескольких прототипов. Такой вид наследования получи название 'множественное наследование'.
    В качестве примера можно рассмотреть формирование понятия заказ товара (см. Рисунок 2. Пример описания знаний с помощью фреймов.).

Рисунок 2. Пример описания знаний с помощью фреймов.[11]

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

Модель семантической сети.

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

  • класс - элемент класса;;
  • свойство - значение;
  • пример элемента класса.

    В качестве примера на Рисунке 3 показана весьма простая семантическая сеть для представления объекта 'чайник'.

Рисунок 3.

    Наиболее часто в семантических сетях используются следующие отношения:

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

    Можно ввести несколько классификаций семантических сетей.
    Например, по количеству типов отношений:

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

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

Рисунок 4. Пример простейшей семантической сети [11].

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

Логическая модель.

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

        Предикат ЛЮБОВЬ (Виктор, Ирина) означает: Виктор любит Ирину
        Предикат СТОЛИЦА (Москва) означает: Москва - столица

    Преимущества логической модели:

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

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

3.3 Представление нечетких знаний.[11]

    Модели представления нечетких знаний используются для формализации человеческих знаний, описывающих качественные характеристики (например, большой, сильный, очень сильный, высокий и т.п.) объектов предметной области, которые могут интерпретироваться неоднозначно, но содержат важную информацию.
    При решении реальных задач часто возникают ситуации неопределенности, которые можно разделить на две категории: отсутствие достаточно полного и достоверного знания о предметной области и отсутствие возможности получить исчерпывающую информацию о конкретном состоянии среды, объекте, ситуации и т.п. В первом случае речь может идти о плохо изученных явлениях, противоречивых теориях или нечетко сформулированных концепциях. Так, например, применение в терапии новых препаратов часто дает совершенно неожиданный результат, который невозможно предсказать. Возможна также и противоположная ситуация: предметная область хорошо изучена, но эксперты предпочитают прибегать к неформальным, но более эффективным, эвристическим приемам, вместо использования рутинных точных методов. Например, при поиске неисправности в электрической схеме, как правило, заменяют несправный блок целиком, вместо поиска сгоревших узлов. Существуют и более прозаичные источники неопределенности знаний. Типичный пример - это ненадежные или неточные данные. Любая информация, поступающая с датчиков, обладает некоторой погрешностью. Социологические опросы также подразумевают некоторый процент ошибок, обусловленных 'человеческим фактором'. Информация может быть зашумлена так, что полностью полезный сигнал невозможно выделить из общего потока данных. Возможно, также, что приходиться пользоваться информацией, полученной ранее, и которую невозможно не проверить, не дополнить не получить повторно. Для преодоления проблемы неопределенности знаний в области искусственного интеллекта были разработаны различные методы, применяемые при построении экспертных систем. Наиболее неформальный подход - это использование коэффициентов уверенности, выражающих степень достоверности знания. Альтернативный способ заключается в использовании теории вероятности. Однако не ясно, как с помощью вероятности представить такие понятия как 'часто', 'иногда', 'старый', 'высокий' и т.п. Кроме того, теория вероятности подразумевает значительное количество вычислений, для обновления вероятностных оценок. Широкое распространение получили также аппараты нечеткой логики теории и функций доверия. Однако в последние годы внимание исследователей все больше привлекает теория вероятностей, с ее развитым и строго формализованным аппаратом.

Коэффициенты уверенности.

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

    Если условие1 и:и условиеM, то прийти со степенью уверенности x к заключение1 и : и к заключениеN.

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

    Если условие1 удовлетворяется с истинностью x1 и : и условиеM удовлетворяется с истинностью xM, то прийти к заключению1 со степенью уверенности y1 и : и к заключениюN со степенью уверенности yN.

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

        CF (заключение) = CF (предпосылки) * CF (правила).

    Если в БЗ найдется несколько правил для данной предпосылки, то в системе MYCIN заключения этих правил объединяются. Пусть X и Y - коэффициенты уверенности одинаковых заключений, полученные при применении разных правил, тогда


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

        Если условие1,
        то прийти со степенью уверенности x1 к заключение.
        :
        Если условиеM,
        то прийти со степенью уверенности xN к заключение.

Следует использовать одно правило вида:

        Если условие1 и : и условиеM, то прийти со степенью уверенности x к заключение.

Правило Байеса.

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

    Как видно из данной формулы, условная вероятность определяется через понятие совместности или одновременности событий, то есть вероятности совпадения событий d и s, разделенное на вероятность события s. Из приведенной формулы очевидно, что вероятность совпадения или произведения двух событий равна произведению вероятности одного из них и условной вероятности другого, вычисленную при условии, что первое имело место:

    Подставляя последнюю формулу в определение условной вероятности можно получить правило Байеса в простейшем виде:

    Это правило позволяет определить вероятность P(d | s) появления события d при условии, что произошло событие s через заранее известную условную вероятность P(s | d). В полученном выражении P(d) - априорная вероятность наступления события d, а P(d | s) - апостериорная вероятность, то есть вероятность того, что событие d произойдет, если известно, что событие s свершилось. Данное правило иногда называют инверсной формулой для условной вероятности, так как она позволяет вычислить вероятность P(d | s) через P(s | d).
    Для систем, основанных на знаниях, правило Байеса гораздо удобнее формулы определения условной вероятности через вероятность одновременного наступления событий P(d . s).В этом достаточно просто убедится. Пусть у пациента X имеется некоторый симптом симптом_Y и необходимо узнать, какова вероятность того, что этот симптом является следствием заболевания заболевание_Z. Для того чтобы непосредственно вычислить P(заболевание_Z | симптом_Y), нужно оценить каким либо образом, сколько человек в мире страдают этим заболеванием, и сколько человек одновременно имеют заболевание_Z и симптом_Y. Такая информация, как правило, недоступна или отсутствует вообще. Особенно, что касается вычисления P(заболевание_Z | симптом_Y).
    Однако, если посмотреть на вероятность не как на объективную частотность событий при достаточно долгих независимых испытаниях, а как на субъективную оценку совместного наступления событий, то ситуация значительно упрощается. Например, врач может не знать или не иметь возможности определить, какая часть пациентов имеющих симптом_Y страдают от заболевание_Z. Но на основании, например собственного опыта или литературных данных, врач в состоянии оценить какой части пациентов имеющих заболевание_Z встречается симптом_Y. Следовательно, можно вычислить P(симптом_Y | заболевание_Z) и применить инверсную формулу для условной вероятности.
    Ситуация значительно усложняется, если речь пойдет о множестве симптомов и множестве заболеваний. Если необходимо вычислить условную вероятность для одного симптома из некоторого множества симптомов, то потребуется m .n + m + n вычислений, где m - количество возможных диагнозов, а n - число разнообразных симптомов. Учитывая, что в медицинской диагностике используются тысячи видов заболеваний и огромное количество симптомов, эта задача становится нетривиальной.
    Ситуация еще усложниться, если включить в процесс постановки диагноза сразу несколько симптомов. Правило Байеса в обобщенной форме выглядит следующим образом:

    Данная формула требует (m *n)k + m + nk вычислений оценок вероятностей, что даже при небольшом k является большим числом. Такое количество оценок требуется по той причине, что для вычисления P(s1.:.sk) в общем случае сначала требуется вычислить P(s1|s2.:.sk). P(s2|s3.:.sk).:.P(sk). Однако если предположить что симптомы независимы, то количество вычислений резко снижается и становиться таким же, как и в случае учета единственного симптома, так как в для независимых si и sj P(si . sj) = P(si) . P(sj). Даже, если в действительности установить независимость невозможно, можно предположить наличие так называемой условной независимости. Это предположение может основываться на каких-либо фоновых знаниях. Например, если в автомобиле нет бензина и не работает свет, то исходя из общих представлений о конструкции автомобиля можно предположить, что эти симптомы независимы. Но если автомобиль не заводится и не работает освещение, то такое предположение сделать уже нельзя. Соответственно, в системе, использующей вероятностные оценки достоверности, необходимо предусмотреть средства отслеживания зависимости между используемыми данными.

Нечеткие множества и нечеткая логика.

    Эксперты при формировании оценок тех или иных признаков, симптомов или ситуаций, как правило, используют знания, основанные не на информации о конкретных примерах объектов, данных, отношений, а оперируют скорее понятиями классов объектов, отношений, гипотез и пр. Методы решений задач, таким образом, должны включать этап классификации данных или знаний. То есть конкретные экземпляры объектов, сигналов и т.п. рассматриваются как представители более общих классов, категорий. Но в реальных ситуациях редко встречаются объекты, которые точно соответствуют той или иной категории или классу. У конкретного экземпляра часть признаков может присутствовать, а другая часть отсутствовать. Таким образом, принадлежность этого объекта к какому-либо классу является размытой. Для формирования суждений о подобных категориях и принадлежащих к ним объектов был предложен формализм теории нечетких множеств. Эта теория легла в основу нечеткой логики, позволяющей использовать понятие неопределенности в логических вычислениях.
    Классическая теория множеств базируется на булевой, двухзначной логике. Принадлежность объекта а к классу А может принимать значения ИСТИНА, если объект а входит в множество А, или ЛОЖЬ - в противоположном случае. После появления понятия 'нечеткие множества', обычные множества стали также называть 'жесткими'. Именно присущая классической теории множеств 'жесткость' при определении категорий, явилась источником проблем, при попытке применить ее для описания нечетко определенных категорий.
    Суть теории нечетких множеств лучше всего рассмотреть на примере. Возьмем в качестве нечеткой категории понятие 'быстрый'. Если применить его к автомобилям, то тогда возникает вопрос: какой автомобиль можно считать быстрым. В классической теории множество А 'быстрых автомобилей' можно сформировать либо перечислением конкретных представителей данного класса, либо введя в рассмотрение характеристическую функцию f, такую, что для любого объекта X
        f(X) = ИСТИНА тогда и только тогда, когда X принадлежит A.
    Например, эта функция может отбирать только те автомобили, которые могут развивать скорость более 150 км в час:

    Эта функция, используя предикат CAR(X) и функцию MAX_SPEED(X) представляет множество:
        { X принадлежит CAR | MAX_SPEED(X) > 150 }.
    Эта формула утверждает, что элементами нового множества являются только те элементы множества CAR, для которых максимальная скорость превышает 150 км в час.
    Представляя все множество 'быстрых' автомобилей, интуитивно кажется, что границы этого множества должны быть размыты, а принадлежность элементов этому множеству может быть каким либо образом ранжирована (см. Рисунок 5. Нечеткое множество быстрых автомобилей.).

Рисунок 5. Нечеткое множество быстрых автомобилей.

    Можно говорить, что каждый элемент (автомобиль) множества 'быстрых' автомобилей более или менее типичен для данной категории. Следовательно, с помощью некоторой функции можно выразить степень принадлежность элемента к множеству. Пусть функция f (X) определена на интервале [0, 1]. Тогда, если для объекта X функция f(X) = 1, то этот объект определенно является членом множества, а если для него f(X) = 0, то он определенно не является членом множества. Все промежуточные значения f(X) выражают степень принадлежности к множеству. В примере с автомобилями требуется функция, оперирующая со скоростью. Ее можно определить таким образом, что fFAST(80) = 0 и fFAST(180) = 1, а все промежуточные значения представляются некоторой монотонной кривой, имеющей значения в интервале [0, 1] (см. Рисунок 6. Функция от скорости для понятия "быстрый".).

Рисунок 6. Функция от скорости для понятия "быстрый".

    Для определения множества FAST_CAR 'быстрых' автомобилей, на основании приведенной выше функции можно ввести новую характеристическую функцию, определенную на множестве всех автомобилей:
        fFAST_CAR(X) = fFAST(MAX_SPEED(X)).
    Членами этого множества, таким образом, становятся пары (объект, степень), например:
        FAST_CAR = {(Porshe 944, 0,9), (BMW 316, 0,6), (Chevy NIVA, 0,1)}.
    Для вычисления значений сложных выражений принадлежности элементов к множеству в классической теории множеств используется булева логика. Для нечетких множеств, принадлежность к которым выражается функцией, принимающей значения от 0 до 1, была создана нечеткая логика. Аппарат этой логики включает операции отрицания, конъюнкции, дизъюнкции и пр., учитывающие концепцию неопределенности.
    Аналоги операций конъюнкции и дизъюнкции в нечеткой логике не связаны с теорией вероятности и имеют следующие определения:
        f(F ^G)(X) = min(fF(X), fG(X)),
        f(F ^G)(X) = max(fF(X), fG(X)).
    Например, фраза 'Porshe 944 является быстрым и представительским автомобилем' может быть представлена с помощью предикатов FAST_CAR(Porshe-944) и PRETENTIOUS_CAR(Porshe-944). Значение FAST_CAR(Porshe-944) = 0,9, а значение PRETENTIOUS_CAR(Porshe-944) пусть будет равно 0,7. Соответственно, можно вычислить значение конъюнкции этих предикатов:
        FAST_CAR(Porshe-944) ^PRETENTIOUS_CAR(Porshe-944)= =min(0,9, 0,7)=0,7.
    Кроме 'быстрых' автомобилей существуют также 'медленные' и 'средние'. Выражение FAST_CAR(Porshe-944) = 0,9 означает, что можно только с 90% уверенностью отнести этот автомобиль к категории 'быстрый', так как существуют еще, например, и более быстрые автомобили, принимающие участия в соревнованиях Формулы 1. Поэтому полученное значение 0,1 говорит о том, что Porshe-944 принадлежит также и категории 'среднескоростных' автомобилей, которые в чем-то близки к 'быстрым', а в чем-то к 'медленным'.
    Операторы нечеткой логики обладают свойствами коммутативности, ассоциативности и взаимной дистрибутивности. Как к операторам в стандартной логике, к ним применим принцип композитивности, то есть значения составных выражений вычисляются только по значениям входящих в них подвыражений. В этом операторы нечеткой логики составляют полную противоположность законам теории вероятностей, согласно которым при вычислении вероятности конъюнкции и дизъюнкции величин нужно принимать во внимание условные вероятности.
    Одним из направлений в нечеткой логике является теория возможности, рассматривающая точно поставленные вопросы на нечетко сформулированных знаниях. Примером такого вопроса является утверждение 'Вероятно, что X связан с Y'. Существование объектов X и Y не вызывает сомнений, а вот наличие между ними связи ставится под вопрос.
    Основные идеи теории возможности лучше всего рассмотреть на примере. Предположим, что в ящике находится 10 шаров, но известно, что только несколько из них являются красными. Какова вероятность того, что из ящика будет извлечен красный шар? Непосредственно вычислить эту вероятность невозможно, так как нам известно, только, что красных шаров несколько, а сколько именно не задано. Тем не менее, для каждого значения вероятности P(RED) того, что шар является красным можно определить некоторое значение в диапазоне [0, 1]. Для этого следует определить понятие 'несколько', как нечеткое множество, например:
        fSEVERAL = {(2, 0.1), (3, 0.2), (4, 0.6), (5, 1.0), (6, 1.0), (7, 0.6), (8, 0.3) , (9, 0.1)}.
    Из этого определения следует, что 3 из 10 с небольшой вероятностью можно считать синонимом 'несколько', так как fSEVERAL(3) = 0.2. Числа 5, 6 полностью согласуются с термином 'несколько', а числа 1 и 10 не рассматриваются вовсе, как соответствующие этому понятию. Нечеткое множество, определенное на множестве чисел получило название нечеткие числа. Аналогичным образом можно определить нечеткие множества для понятий 'мало', 'почти' и пр.
    Распределение возможностей теперь можно вычислить по формуле:

    Подставляя в данную формулу множество, определенное выше получается новое множество:
        {(0.2,0.1), (0.3,0.2), (0.4,0.6), (0.5,1.0), (0.6,1.0), (0.7,0.6), (0.8,0.3) , (0.9,0.1)}.
    Таким образом, возможность того, что P(RED) = 0.3 составляет 20%. Множество fP(RED) также называют нечеткой вероятностью.
    С помощью данного механизма можно ввести в рассмотрение любую функцию, поэтому удобно использовать понятие нечеткого правдоподобия. Например, некоторое утверждение может быть оценено как 'очень правдоподобное' или 'частично правдоподобное'. Эти понятия представляются на множестве, где областью определения и областью значений функции являются значения правдоподобия в нечеткой логике fTRUE: [0, 1]>[0, 1]. Следовательно, можно рассматривать значения, меньшие единицы, как 'достаточно правдоподобные'. Например, для ситуации с быстрыми автомобилями можно определить
        TRUE(FAST_CAR(Porsche-944)) = 1.
    Таким образом, можно с полной уверенностью утверждать, что Porsche-944 является быстрым автомобилем, несмотря на то, что на рынке имеются и более скоростные автомобили.

4. Методы поиска решений.

    Методы решения задач, основанные на сведении их к поиску, зависят от особенностей предметной области, в которой решается задача, и от требований, предъявляемых пользователем к решению. Особенности предметной области:

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

4.1 Поиск решений в одном пространстве.

    Методы поиска решений в одном пространстве обычно делятся на:

  • поиск в пространстве состояний (рассмотрим подробно);
  • поиск методом редукции;
  • эвристический поиск;
  • поиск методом "генерация-проверка".

Поиск в пространстве состояний.

Задача поиска в пространстве состояний обычно формулируется в теоретико-графовой интерпретации.
    Пусть задана тройка (S0, F, SТ), где S0 - множество начальных состояний (условия задачи), F - множество операторов задачи, отображающих одни состояния в другие, SТ - множество конечных (целевых) состояний (решений задачи).
    Цель: определять такую последовательность операторов, которая преобразует начальные состояния в конечные.
    Процесс решения в виде графа G=(Х, Y), где X={х0, х1,...} - множество (в общем случае бесконечное) вершин графа, состояний, а Y - множество, содержащее пары вершин (xi, xj), (xi, xj)?X. Если каждая пара (xi, xj) неупорядочена, то ее называют ребром, а граф - неориентированным. Если для каждой пары (xi, xj) задан порядок (направление), то пару (xi, xj) называют дугой (ориентированным ребром), а граф называют ориентированным (направленным). Вершины пары (xi, xj) называют концевыми точками ребра (дуги).
    Поиск в пространстве состояний естественно представить в виде ориентированного графа. Наличие пары (xi, xj) свидетельствует о существовании некоторого оператора f (f?F), преобразующего состояние, соответствующее вершине xi, в состояние xj. Для некоторой вершины xi выделяем множество всех направленных пар (xi, xj)?Y, т.е. множество дуг, исходящих из вершины хi, (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины xi, соответствует множеству операторов, которые могут быть применены к состоянию, соответствующему вершине хi.
    В множестве вершин X выделяют подмножество вершин Х0 принадлежит Х, соответствующее множеству начальных состояний (So),, и подмножество вершин Хт?X, соответствующее множеству конечных (целевых) состояний (SТ). Множество Хт может быть задано как явно, так и неявно, т.е. через свойства, которыми должны обладать целевые состояния.
    Отметим, что граф С может быть задан явно и неявно. Неявное задание графа G стоит в определении множества Х0?Х (соответствующего множеству начальных состояний) и множества операторов, которые, будучи применимы к некоторой вершине графа, дают все ее дочерние вершины.
    Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решения. Построение пространства осуществляется с помощью следующего процесса. Берется некая вершина х0?Х, к ней применяются все возможные операторы, порождающие все дочерние вершины. Этот процесс называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. Процесс построения пространства состояний заканчивается, когда все нераскрытые вершины являются целевыми, или терминальными (т.е. вершинами, к которым нельзя применить никаких операторов). В связи с тем, что пространство состояний может содержать бесконечное количество вершин, на практике процесс порождения пространства ограничивают либо временем, либо объемом памяти.
    На практике требуется обеспечить полноту поиска, т.е. организовать поиск так, чтобы все целевые вершины были найдены, если они существуют. Надежным способом обеспечения полноты является полный перебор всех вершин. Для задания процесса перебора необходимо определить. порядок, в котором будут перебираться вершины графа. Обычно выделяют два основных способа поиска:

  • поиск в глубину (сначала раскрывается та вершина, которая была построена самой последней). Рисунок 7.a.
  • поиск в ширину. (вершины раскрываются в том же порядке, в котором они порождаются.) Рисунок 7.б.

Рисунок 7. Пространство состояний, построенное поиском в глубину (а) и поиском в ширину (б).


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

Поиск методом редукции.

    При поиске методом редукции решение задачи сводится к решению совокупности образующих ее подзадач. Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Процесс решения задачи разбиением ее на подзадачи можно представить в виде специального направленного графа G, называемого И/ИЛИ-графом; Каждой вершине этого графа ставится в соответствие описание некоторой задачи (подзадачи). В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины.
    Решение задачи при поиске методом редукции (при поиске в И/ИЛИ-графе) сводится к нахождению в И/ИЛИ-графе решающего графа.
    Цель процесса поиска в И/ИЛИ-графе - показать, что начальная вершина разрешима, т.е. для этой вершины существует решающий граф. Определение разрешимой вершины в И/ИЛИ-графе можно сформулировать рекурсивно следующим образом:

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

Графическое представление разбиения задачи на подзадачи.

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

Пример И/ИЛИ графа

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

Рисунок 9.Пример разбиения задачи на подзадачи при поиске в ширину(а) и при поиске в глубину(б).

Эвристический поиск.

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

Поиск методом "генерация-проверка".

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

4.2. Поиск решений в иерархии пространств.

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

  • поиск в факторизованном пространстве;
  • поиск в фиксированном множестве пространств;
  • поиск в изменяющемся множестве пространств.

Поиск в факторизованном пространстве.

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

Поиск в фиксированном множестве пространств.

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

Поиск в изменяющемся множестве иерархических пространств.

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

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

4.3. Поиск решений в альтернативных пространствах.

     Рассмотренные выше методы поиска исходят из молчаливой предпосылки, что знания о предметной области и данные о решаемой задаче являются точными и полными и для них справедливо следующее:

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

4.4. Поиск решений с использованием нескольких моделей.

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

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

4.5. Выбор метода решения задач.

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

5.1 Классификация инструментальных средств.

Инструментальные средства подразделяются на следующие категории:

  • Языки программирования
  • Языки инженерии знаний
  • Средства автоматизации разработки экспертных систем
  • Оболочки экспертных систем

5.2 Языки программирования.[18]

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

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

  • Оболочки экспертных систем (expert system shells). Системы этого типа создаются, как правило, на основе какой-нибудь экспертной системы, достаточно хорошо зарекомендовавшей себя на практике. При создании оболочки из системы-прототипа удаляются компоненты, слишком специфичные для области ее непосредственного применения, и оставляются те, которые не имеют узкой специализации. Примером может служить система EMYCIN, созданная на основе про-шедшей длительную "обкатку" системы MYCIN. В EMYCIN сохранен интерпрета-тор и все базовые структуры данных - таблицы знаний и связанный с ними меха-низм индексации. Оболочка дополнена специальным языком, улучшающим читабельность программ, и средствами поддержки библиотеки типовых случаев и заключений, выполненных по ним экспертной системой. Дальнейшим развитием оболочки EMYCIN явились системы S.1 и М.4, в которых механизм построения цепочки обратных рассуждений, заимствованный в EMYCIN, объединен с фреймоподобной структурой данных и дополнительными средствами управления ходом рассуждений.
  • Языки программирования высокого уровня. Инструментальные средства этой категории избавляют разработчика от необходимости углубляться в детали реализации системы - способы эффективного распределения памяти, низкоуровневые процедуры доступа и манипулирования данными. Одним из наиболее известных представителей таких языков является OPS5. Этот язык прост в изучении и предоставляет программисту гораздо более широкие возможности, чем типичные специализированные оболочки. Следует отметить, что большинство подобных языков так и не было доведено до уровня коммерческого продукта и представляет собой скорее инструмент для исследователей.
  • Среда программирования, поддерживающая несколько парадигм (multiple-paradigm programming environment). Средства этой категории включают несколько программных модулей, что позволяет пользователю комбинировать в процессе разработки экспертной системы разные стили программирования. Среди первых проектов такого рода была исследовательская программа LOOP, которая допускала использование двух типов представления знаний: базирующегося на системе правил и объектно-ориентированного. На основе этой архитектуры во второй половине 1980-х годов было разработано несколько коммерческих программных продуктов, из которых наибольшую известность получили KEE, KnowledgeCraft и ART. Эти программы предоставляют в распоряжение квалифицированного пользователя множество опций и для последующих разработок, таких как КАРРА и CLIPS, и стали своего рода стандартом. Однако освоить эти языки программистам далеко не так просто, как языки, отнесенные нами к предыдущей категории
  • Дополнительные модули. Средства этой категории представляют собой автономные программные модули, предназначенные для выполнения специфических задач в рамках выбранной архитектуры системы решения проблем. Хорошим примером здесь может служить модуль работы с семантической сетью, использованный в системе VT. Этот модуль позволяет отслеживать связи между значениями ранее установленных и новых параметров проектирования в процессе работы над проектом. Подобные модули управления семантической сетью можно использовать для распространения внесенных изменений на все компоненты системы.

   Объектно-ориентированные языки

     Формат правил хорошо согласуется с представлением знаний в форме "при выполнении условий Сь ..., С' выполнить действие А", но менее подходит для описания сложных объектов и отношений между ними. Языки объектно-ориентированного программирования предоставляют в распоряжение программиста альтернативную программную среду для организации знаний в терминах декларативного представления объектов предметной области. Все, связанное с процедурной стороной решения проблем, распределяется между этими объектами, которые в таком случае располагают собственными процедурами и могут общаться друг с другом посредством протоколов передачи сообщений.
    Другим приятным аспектом объектно-ориентированного программирования является возможность использования таких стилей представления знаний, которые не встречаются в исчислении предикатов и в порождающих правилах. Вместо "размывания" знаний об объекте предметной области между множеством правил или аксиом, на которые они ссылаются, эти знания концентрируются в едином месте - в программном описании объекта. Эта концентрация является виртуальной в том смысле, что нет необходимости, чтобы вся информация об объекте предметной области хранилась в соответствующем ему программном объекте, но любая команда или запрос к этому объекту может быть реализована только через посылку сообщения этому объекту
    В реальном мире вещей существует множество систем, в которых обмен информацией может быть представлен через обмен сообщениями между их компьютерными представлениями, и такая связь с технологией моделирования является очень важным достоинством данного подхода. Не вызывает сомнений, что моделирование является одним из мощнейших средств решения проблем и что, рассматривая процесс логических рассуждений в контексте сложной системы, его иногда понять значительно легче, чем в контексте применения правил. Объектно-ориентированное программирование интегрирует символические вычисления в операционную среду, базирующуюся на средствах графического интерфейса, - меню, пиктограммы и т.п. Хотя само по себе оснащение экспертной системы этими средствами и не решает проблему ее прозрачности для пользователя, в руках умелого программиста они позволяют лучше представить пользователю процессы, происходящие в системе.
    Основная сложность в использовании средств объектно-ориентированного программирования - уяснить для себя, что именно должен представлять программный объект по отношению к предметной области. В ранних версиях объектно-ориентированных языков, которые были предназначены в основном для разработки программ моделирования, такая проблема не возникала - программные объекты представляли объекты моделируемой системы. Например, при моделировании производственной линии отдельные программные объекты представляли те или иные механизмы этой линии, а сообщения между программными объектами - информационные, энергетические и материальные потоки. Задача программиста серьезно облегчалась тем, что существовало достаточно очевидное соответствие между программными и реальными объектами.
    Но для того чтобы внедрить объектно-ориентированный стиль в проектирование экспертных систем, нужно задуматься над тем, как соотнести программные объекты с абстрактными понятиями и категориями предметной области. Объекты должны представлять факты и цели, наборы правил или отдельные гипотезы. Поэтому далеко не очевидно, какими сообщениями должны обмениваться такие объекты и какой смысл должен вкладываться в эти сообщения.
    Многое зависит от того, на каком уровне абстракции будет использоваться объектно-ориентированный механизм. Если объекты представляют собой низкоуровневую реализацию определенной схемы формирования суждений, то отпадает необходимость в использовании каких бы то ни было эпистемологических последовательностей. Если же объекты будут видимы и для эксперта в процессе разработки и совершенствования системы, и для пользователя во время эксплуатации системы, то схема отображения понятий и категорий на программные объекты должна быть тщательно продумана.
    Пример:

  • Smalltalk[19] - объектно-ориентированный язык программирования с динамической типизацией, разработанный в Xerox PARC Аланом Кэйем, Дэном Ингаллсом, Тедом Кэглером, Адель Голдберг, и другими в 1970-х годах. Язык был представлен как Smalltalk-80 и с тех пор широко используется. Smalltalk продолжает активно развиваться и собирает вокруг себя преданное сообщество пользователей.
         Smalltalk оказал большое влияние на развитие многих других языков, таких как: Objective-C, Actor, Java и Ruby. Многие идеи 1980-х и 1990-х по написанию программ появились в сообществе Smalltalk. К ним можно отнести рефакторинг, шаблоны проектирования (применительно к ПО), карты Класс-Обязанности-Взаимодействие и экстремальное программирование в целом. Основатель концепции WikiWiki, Вард Каннингем, также входит в сообщество Smalltalk.
         Основные идеи Smalltalk'а Основными идеями Smalltalk'а являются:
    • 'Всё - объекты'. Строки, целые числа, логические значения, определения классов, блоки кода, стеки, память - всё представляется в виде объектов. Выполнение программы состоит из посылок сообщений между объектами. Любое сообщение может быть послано любому объекту; объект-получатель определяет, является ли это сообщение правильным, и что надо сделать, чтобы его обработать.
    • Всё доступно для изменения. Если вы хотите изменить интегрированную среду разработки, вы можете сделать это в работающей системе, без остановки, перекомпиляции и перезапуска. Если вам необходима в языке новая управляющая структура, вы можете добавить её. В некоторых реализациях вы можете также изменить синтаксис языка или способ работы сборщика мусора.
    • Динамическая типизация - это означает, что вы не указываете типы переменных в программе, что делает язык гораздо лаконичней. (Как объяснено выше, является ли операция правильной, определяет объект-получатель, а не компилятор).
    • Model-view-controller (MVC) шаблон структуры пользовательского интерфейса. (В последнее время используют и другие концепции реализации пользовательского интерфейса - например, Morphic в Squeak и Pollock в VisualWorks).
    • Dynamic translation: современные коммерческие виртуальные машины компилируют байткоды в машинные коды для быстрого выполнения.

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

        Одной из неожиданных особенностей Smalltalk'а является то, что традиционные конструкции: if-then-else, for, while, и т. д. не являются частью языка. Все они реализованы с помощью объектов. Например, решение принимается с помощью посылки сообщения ifTrue: логическому объекту, и передаёт управление фрагменту кода если логическое значение истинно. Есть всего три конструкции:
    • посылка сообщения объекту;
    • присваивание объекта переменной;
    • возвращение объекта из метода;
    и несколько синтаксических конструкций для определения литеральных объектов и временных переменных.
        Чтобы лучше понять, как работает механизм обмена сообщениями, можно представить каждый объект как веб-сервер, отвечающий на запросы. При этом, на запросы можно просто выдавать заранее предопределённый ответ, аналог этому - выдача веб-страницы, расположенной по определённому пути; можно перенаправить запрос-сообщение другому объекту, аналог - прокси-сервер; изменить запрос по определённым правилам, аналог - техника url rewriting. Если для реакции на сообщение нет предопределённого метода, то вызывается метод #doesNotUnderstand:, так же, как веб-сервер открывает страницу с сообщением об ошибке, если задан несуществующий путь к веб-странице.
        Следующий пример показывающий нахождение гласных в строке иллюстрирует стиль Smalltalk'а. Символ ( | определяет переменные, : определяет параметры, а символы [ и ] можно, для начала, воспринимать, как аналог фигурных скобок { и } в С-подобных языках:
    | aString vowels |
    aString := 'This is a string'.
    vowels := aString select: [:aCharacter | aCharacter isVowel].

        В последней строке посылается сообщение select: с аргументом в виде блока кода. Дальше идёт код в суперклассе Collection который выполняет работу:
    | newCollection |
    newCollection := self species new.
    self do: [:each |
    (aBlock value: each)
    ifTrue: [newCollection add: each]].
    ^newCollection

        Он отвечает на сообщение путём перебора своих элементов (это метод do:) выполняя код aBlock для каждой буквы; когда выполняется aBlock (aCharacter isVowel) он создаёт логическое значение, которому затем посылается ifTrue:. Если это значение true, буква добавляется в возвращаемую строку. Из за того что select определён в абстрактном классе Collection, мы также можем использовать его так:
    | rectangles aPoint|
    rectangles := OrderedCollection
    with: (Rectangle left: 0 right: 10 top: 100 bottom: 200)
    with: (Rectangle left: 10 right: 10 top: 110 bottom: 210).
    aPoint := Point x: 20 y: 20.
    collisions := rectangles select: [:aRect | aRect containsPoint: aPoint].

        История
        Smalltalk был создан группой исследователей возглавляемой Аланом Кэйем в исследовательском центре Xerox PARC. Первая реализация, известная как Smalltalk-71, была создана за несколько месяцев как результат спора о том, что язык программирования, основанный на идее посылки сообщений, подсказанной Симулой, должен реализовываться на 'странице кода'. Более поздняя версия, действительно использованная для исследовательской работы, известна сейчас как Smalltalk-72. Его синтаксис и модель исполнения сильно отличались от современного Smalltalk'а, настолько, что его надо рассматривать как другой язык. После существенных переработок которые зафиксировали несколько сторон семантики выполнения для увеличения эффективности, была создана версия известная как Smalltalk-76. В этой версии добавились наследование, синтаксис более близкий к Smalltalk-80, и среда разработки включающую большинство инструментов знакомых сейчас Smalltalk-ерам. В Smalltalk-80 были добавлены метаклассы, что делало фразу 'всё объекты' истинной путём связывания с индивидуальными классами свойств и поведения (например, поддержки различных способов создания экземпляров). Smalltalk-80 был первой версией доступной за пределами PARC, сначала как Smalltalk-80 Version 1, розданной небольшому количеству компаний и университетов для 'экспертной оценки'. Позже (в 1983) общедоступная реализация, известная как Smalltalk-80 Version 2, стала доступна как образ (независимый от платформы файл содержащий объекты) и спецификации виртуальной машины. Сейчас существует две реализации Smalltalk, являющихся прямыми потомками Smalltalk-80. Это Squeak и VisualWorks. Как выглядел Smalltalk-80 можно увидеть на скриншоте. Образ Smalltalk-80 version 2 запущен на Hobbes, виртуальной машине ST-80 реализованной на VisualWorks.
5.3 Языки инженерии знаний.
  • Характеристика системы OPS5
        Возможности языков высокого уровня также не беспредельны - каждый из них имеет свои ограничения. Например, в языке OPS5 возможности динамической памяти ограничены размещением векторов в рабочей памяти, что не позволяет строить в ней рекурсивные структуры данных, такие как графы или деревья. При разработке системы MORE из-за этого возникли серьезные сложности. Некоторые типы структур управления ходом выполнения, например рекурсивные и итерационные циклы, также с трудом реализуются в этом языке. В общем, это та цена, которую приходится платить за относительную простоту программного кода на языке OPS5 и эффективность его выполнения.
        В ранних моделях систем, основанных на порождающих правилах, до 90% времени работы уходило на выполнение операций сопоставления условий. Но позднее Форджи обратил внимание на возможные источники низкой эффективности такого упрощенного подхода. Алгоритм сопоставления RETE, предложенный Форджи и реализованный в языках описания порождающих правил семейства OPS, базируется на двух наблюдениях:
    • В левых частях порождающих правил, которые размещаются в рабочей памяти, часто встречаются повторяющиеся условия. Если одно и то же условие встречалось в N правилах, то при прежнем упрощенном подходе выполнялось N операций сопоставления. Это пример внутрицикловой итерации (within-cycle iteration).
    • Простейший подход (в OPS5) при сопоставлении условий предполагает просмотр в каждом цикле всех элементов рабочей памяти, хотя содержимое рабочей памяти от цикла к циклу изменяется очень мало. Форджи назвал это межцикловой итерацией (between-cycle iteration).

        Предложенный Форджи алгоритм значительно снижает количество внутрицикловых итераций за счет использования сети сортировки, имеющей древовидную структуру. Выражения в левой части порождающих правил компилируются и включаются в эту сеть, а алгоритм сопоставления довольно просто определяет конфликтующее множество, просматривая состояние сети в текущем цикле. Количество межцикловых итераций сокращается за счет обработки множества лексем, которые являются индикаторами удовлетворения условий, размещенных в рабочей памяти. Это множество лексем отображает изменения, происходящие в рабочей памяти от цикла к циклу, и таким образом позволяет выявить те условия, которые подлежат проверке. Поскольку никаких других процессов управления, кроме цикла распознавание-действие, в системе не существует, то обработать полученное в результате конфликтующее множество не представляет особого труда. Механизм разрешения конфликтов выполняет это, не обращая внимания на другие аспекты текущего контекста вычислений.
        Совершенно очевидно, что попытка использовать рекурсивные структуры данных потребует серьезного усложнения описанного процесса обработки правил. Точно так же и изменение режима управления приведет к тому, что механизм разрешения конфликтов вынужден будет анализировать дополнительную информацию. Разработчики языков, подобных OPS, всегда вынуждены искать компромисс между мощностью выразительных средств языка и эффективностью выполнения программного кода. До сих пор в среде исследователей предметом оживленных дискуссий является вопрос о том, удалось ли разработчикам OPS5 найти такой компромисс. Разработанные позже языки КЕЕ, КАРРА и CLIPS унаследовали от OPS5 синтаксис и механизм активизации правил. Все эти языки используют различные версии алгоритма RETE при формировании множества конфликтующих правил.
        Преодоление недостатков программирования порождающих правил лежит не на пути усложнения существующих языков программирования, а скорее на пути объединения их с другими парадигмами программирования, позволяющими использовать рекурсивные структуры данных и управления. Примером такого объединения может служить комбинирование порождающих правил и фреймов, что позволяет сопоставлять условия, специфицированные в правилах, с содержимым слотов фреймов. Для решения проблем управления в последнее время все чаще используется включение наборов правил в более мощную.вычислительную среду, которая позволяет работать со списками заявок и с множеством источников знаний .
  • Язык логического программирования PROLOG

    Пролог (Prolog) - язык логического программирования, основанный на логике дизьюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.
        Начало истории языка относится к 70-м годам XX века. Будучи декларативным языком программирования, Пролог воспринимает в качестве программы некоторое описание задачи, и сам производит поиск решения, пользуясь механизмом бэктрекинга и унификацией.
        Встроенный в PROLOG режим управления использует стратегию обратного логического вывода, которая используется в системах, подобных MYCIN. Таблицы знаний и другие данные можно представить с помощью утверждений.Такие структуры данных, как графы и деревья , можно организовать с помощью фраз языка PROLOG, которые содержат комплексные термы. Языковые средства PROLOG позволят программисту разработать собственный механизм обработки неопределенности, причем не исключается и использование коэффициентов уверенности.
        С практической точки зрения, пользуясь языком PROLOG, программист в качестве "бесплатного приложения" получает в свое распоряжение следующие возможности:

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

        Действительно, дедуктивную порождающую систему довольно ПРОСТО эмулировать на языке PROLOG.(как используется эмуляция) Можно без особого труда разработать и простой интерпретатор, реализующий стратегию построения прямой цепочки вывода. Модификация рабочей памяти выполняется операторами assert и retract, которые добавляют или удаляют формулы из базы данных. Вы уже знаете как можно организовать локальное управление ходом процесса в системе, основанной на фреймах, как организовать обработку значений по умолчанию и исключений, хотя эти методы и не вписываются в стандартную логику.
        Успешный опыт применения идей логического программирования, в частности создание программы МЕСНО, продемонстрировал ряд явных отклонений от синтаксиса исчисления предикатов первого порядка и его процедурной интерпретации в стандартной версии PROLOG. Некоторые семантические и синтаксические ограничения в программах МЕСНО и PLANNER до сих пор не преодолены в системах, базирующихся на языках логического программирования.
  • Язык функционального программирования LISP

        Лисп (LISP, от англ. LISt Processing - 'обработка списков') - семейство языков программирования, основанных на представлении программы системой линейных списков, которые притом являются основной структурой данных языка. Лисп считается вторым после Фортрана старейшим высокоуровневым языком программирования.
        Традиционный Лисп имеет строгую динамическую систему типов, содержит императивные свойства, но в общем поощряет функциональную парадигму программирования. Существует объектно-ориентированное расширение языка - CLOS
        Основная особенность Лиспа - представление программы в виде списков - определяет однородность и простоту синтаксиса. Внешне исходный код программы на Лиспе отличается обилием круглых скобок; редактирование программ значительно упрощается использованием текстового редактора, поддерживающего автоматическое выравнивание кода, подсветку соответствующих пар скобок и команды рода 'перейти через список вправо'. Хорошо приспособлен к кодированию на Лиспе редактор Emacs (большая часть которого написана на Лиспе), кроме того в коммерческих реализациях (например в LispWorks) IDE содержит удобные редакторы, сохраняющие все достоинства Emacs.
        Одним из самых распространённых диалектов Лиспа является Common Lisp. Его реализации существуют для большинства платформ. Есть реализации распространяемые свободно под лицензиями, позволяющими использовать Лисп без ограничений в коммерческих приложениях, кроме этого существуют коммерческие реализации, предлагающие дополнительные возможности (IDE, дополнительные библиотеки и т. п.), в том числе техническую поддержку. С полным списком реализаций можно ознакомиться здесь: Common Lisp Implementation.
    Синтаксис
        Любая программа на Лиспе состоит из последовательности выражений (форм). Результат работы программы состоит в вычислении этих выражений. Все выражения записываются в виде списков - одной из основных структур Лиспа, поэтому они могут легко быть созданы посредством самого языка. Это позволяет создавать программы, изменяющие другие программы или макросы, позволяющие существенно расширить возможности языка.
        Список является последовательностью элементов любого рода, в том числе других списков. Например, (1 3/7 'foo #'+) состоит из целого числа, рациональной дроби, символа foo и указателя на функцию сложения. Выражения представляются списками в префиксной записи: первый элемент должен быть формой, то есть функцией, оператором, макросом или специальным оператором; прочие элементы суть аргументы, передаваемые форме для обработки. Функция list возвращает список состоящий из ее аргументов: например, (list 1 3/7 'foo #'+) возвращает список, упомянутый ранее. Если некоторые элементы являются выражениями, то сначала вычисляется их значение: (list 1 2 (list 1 2)) возвращает (1 2 (1 2)). Арифметические операторы действуют так же, например (+ 4 (* 2 3)) выдаёт 10.
        Специальные операторы позволяют управлять последовательностью вычислений. С их помощью реализуются ветвление и циклы. Оператор if позволяет вычислить одно из двух выражений в зависимости от выполнения условия, которое тоже является выражением. Если его результат не nil, то вычисляется первый аргумент, иначе вычисляется второй. Например, (if nil (list 1 2 "foo") (list 3 4 "bar")) всегда возвращает (3 4 "bar").
    Примеры
        Пример куина (программы, выводящей свой исходный код) на Лиспе:
    ((lambda (x) (list x (list 'quote x))) '(lambda (x) (list x (list 'quote x))))

        Данная программа должна работать на большинстве диалектов Лиспа, в том числе и на Scheme.
        Итеративная версия функции определения N-го числа Фибоначчи:
    (defun fibonacci (x)
    (if (= x 0)
    1
    (loop with result = 1
    with prev = 1
    for i from 0 below (1- x)
    do (psetq result (+ result prev) prev result))))

Многофункциональные программные среды

    Многофункциональные программные среды позволяют опытному программисту экспериментировать при решении новых классов проблем, выбирая подходящие сочетания различных методов, представленных в имеющемся модульном наборе. Поскольку не существует единственного универсального языка представления знаний для произвольной экспертной системы, у разработчиков возникает желание объединить несколько различных схем представления, особенно на этапе создания прототипа. Хотя исчерпывающей теории таких гибридных систем и не существует, эксперименты с разными схемами представления и логического вывода показали, что каждая из них имеет свои слабые стороны. Поэтому понятно желание объединить разные методики таким образом, чтобы достоинства одних компенсировали слабости других.
    Мы уже не раз обращали ваше внимание на то, что порождающие правила позволяют представить в программе эмпирически выявленные связи между условиями и действиями, между наблюдениями и гипотезами, но они значительно хуже подходят для представления отношений между объектами предметной области, включая и такие важнейшие, как отношения множество/элемент или множество/подмножество. Структурированные объекты, например фреймы, оказываются более удобным средством для хранения и манипулирования описаниями объектов предметной области, но применение таких знаний требует включения в программу фрагментов программного кода (например, на языке LISP), которые затем трудно анализировать. Рациональное зерно в первых попытках свести вместе стили, основанные на правилах и фреймах, состояло в том, чтобы объединить способность представлять объекты, характерные для фреймов, с возможностями связывать условия и действия с помощью порождающих правил.
    Одной из первых многофункциональных сред искусственного интеллекта является LOOPS. в которой в рамках единой архитектуры обмена сообщениями были объединены четыре парадигмы программирования, перечисленные ниже
[18]:

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

    В рамках основной объектно-ориентированной парадигмы модули среды, поддерживающие разные стили программирования, можно комбинировать. Обычно условия в порождающих правилах и логические фразы связываются со значениями слотов структурированных объектов, а правила модифицируют значения этих слотов. Именно такой стиль объединения парадигм в настоящее время реализован в языке CLIPS.
    В системах КЕЕ и LOOPS поведение объектов описывается в терминах множества порождающих правил, как это сделала Эйкинс (Aikins) в системе CENTAUR. В средах КЕЕ и Knowledge Craft к перечисленным выше парадигмам добавлено и логическое программирование в стиле языка PROLOG. Новая версия КЕЕ, известная под названием КАРРА-РС, предоставляет в распоряжение программиста еще более широкий набор стилей для комбинирования правил, объектов и процедур.

CLIPS как многофункциональная среда программирования(инженерии знаний)

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

  • для определения стандартных функций используется синтаксис, подобный LISP;
  • предоставляет в распоряжение разработчика родовые функции, аналогичные мультиметодам CLOS;
  • располагает встроенным объектно-ориентированным языком COOL, который, в отличие от CLOS, включает и средства поддержки обмена сообщениями.

    Обращение к стандартным функциям допускается включать в правую часть правил и в этом случае они выполняются так, как если бы являлись компонентом действий, специфицированных в правиле. Функции вызываются либо с целью получить побочный эффект, либо для использования явно возвращаемого функцией результата, который может быть сохранен с помощью оператора присваивания. Для работы с переменными в этом случае используется тот же синтаксис, что и в языке описания правил. Например, можно определить функцию between (X, Y, 2), оперирующую с целыми переменными. Эта функция будет проверять выполнение неравенств X|Y|Z:
(deffunction between (?lb ?value ?ub)

(and (<= ?lb ?value) (<=?value ?ub))),

    Родовые функций (generic function) в CLIPS играют ту же роль, что и перегружаемые операторы в языке C++. Они обеспечивают возможность выполнять обработку разными методами последовательностей данных различного типа. Например, для конкатенации двух строковых значений оператором '+' можно следующим образом перегрузить этот оператор:
(defmethod + ((?a STRING) (?b STRING)) (art-cat ?a ?b)}

Тогда результатом вычисления выражения

(+ "dog" "fish") будет "dogfish".

    В такой функции можно смешивать ограниченные и неограниченные параметры, причем ограничение может касаться типов данных на произвольном уровне обобщения, например числовых данных, целых, положительных целых чисел и т.д.
    Вычисление родовых функций выполняется под "надзором" родового алгоритма диспетчирования (generic dispatch algorithm), который формирует индексированный список подходящих методов. Методы из этого списка затем вызываются соответственно уровню ограничений, указанному для параметров при обращении к функции. Алгоритм также принимает во внимание любые управляющие программные конструкции, представленные явно в тексте программы метода, например call-next-method или override-next-method.
    Механизм передачи сообщений реализован по тому же способу, что и в языках SmallTalk и LOOPS, и требует, чтобы программист разработал свой обработчик сообщений для каждого отдельного класса. Диспетчер сообщений работает так же, как в исполняющей системе языка CLOS, и различает обработчики типов primary, around, before и after.
    В программе на языке CLIPS можно вызывать и функции, написанные на языке С, хотя это и выполняется несколько необычно. Исполняющая система CLIPS может выступать в качестве внедренного приложения, т.е. программа на CLIPS может быть скомпилирована и скомпонована с программой на языке С, которая будет вызывать CLIPS-фрагменты как подпрограммы. Это позволяет внедрять функции искусственного интеллекта в компоненты больших программных комплексов.

5.4 Средства автоматизации разработки экспертных систем.

Дополнительные модули
    Под дополнительными модулями понимаются те полезные программы, которые можно выполнять вместе с приложением. Как правило, такие программы реализуют некоторые специальные функции, как бы "снимая их с полки", причем для обращения к таким функциям не требуется что-либо программировать в основном приложении или заниматься его индивидуальной настройкой. Одним из примеров такого рода дополнительного модуля может служить программный пакет Simkit из комплекта среды КЕЕ. Этот пакет позволяет оснастить экспертную систему методами моделирования.
    Другой функцией, которая поддерживается дополнительными модулями сред КЕЕ и ART, является механизм обработки множества различных контекстов логических рассуждений. В первом приближении можно считать, что контексты формируются теми ветвями в пространстве поиска, которые допускают использование более чем одного оператора. Рассмотрим представленный ниже сценарий, в котором имеются два правила, в каждом из которых условная часть удовлетворяется в текущем контексте рассуждений.

[Правило 1]
  ЕСЛИ: сегодня рабочий день И
  нет признаков недомогания,
  ТО: посетить занятия по информатике.

[Правило 2]
  ЕСЛИ: сегодня рабочий день И
  погода прекрасна,
  ТО: покататься на яхте.

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

[Правило 3]
  ЕСЛИ: не посещать занятия по информатике,
  ТО: экзамен по информатике будет провален

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


Рис. Пример множества контекстов


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

5.5 Оболочки экспертных систем.


    Оболочки экспертных систем - программный продукт, обладающий средствами представления знаний для определенных предметных областей. Задача пользователя заключается не в непосредственном программировании, а в формализации и вводе знаний с использованием предоставленных оболочкой возможностей. Недостатком этих систем можно считать невозможность охвата одной системой всех существующих предметных областей. Примером могут служить ИНТЕРЭКСПЕРТ, РС+, VP-Expert.
    Оболочка, shell - базовый элемент операционной системы, определяющий интерпретацию команд и действий пользователя.
    CLIPS (Язык C, интегрированная Продукционная Система) - OPS-ПОДОБНАЯ продукционная система, использующая вывод от фактов к цели, написанная на C в ANSI NASA. Механизм логического вывода CLIPS включает сопровождение , динамическое добавление правил и настраиваемые cтратегии разрешения противоречий. CLIPS, включая динамическую версию , легко встраивается в другие прикладные программы. CLIPS включает объектно-ориентированный язык, названный COOL(Объектно-ориентированный Язык CLIPS), который прямо интегрирован с механизмом логического вывода. CLIPS выполняется на многих платформах, включая IBM PC ( Windows 3.1 и версии МС-ДОС 386). Домашняя страница Software Technology Branch - http://www.jsc.nasa.gov/stb/STB_homepage.html NASA, домашняя страница Nasa Information Services http://hypatia.gsfc.nasa.gov/NASA_homepage.html и домашняя страница CLIPS - http://www.jsc.nasa.gov/~clips/CLIPS.html Cписок ЧАСТО ЗАДАВАЕМЫХ ВОПРОСОВ по CLIPS и ошибки располагаются на jsc.nasa.gov:/pub/clips/ и поддерживаются Gary Riley.
    DYNACLIPS (динамические Утилиты CLIPS ) - включает доску объявлений, механизм динамического обмена знаниями и инструментальные средства для CLIPS v5.1 и v6.0. Она существлена как набор библиотек, который может быть связан с CLIPS v5.1 или CLIPS v6.0. Исходный текст не предоставляется. Для связи с другими интеллектуальными средствами используется доска объявлений. Она находится в ИИ архиве на ftp.cs.cmu.edu:/user/ai/areas/expert/systems/clips/dyna/
    FuzzyCLIPS 6.02 - версия CLIPS, оболочка экспертной системы, основанная на правилах, используется для представления и управления нечеткими фактами и правилами. В дополнение к функциональным возможностям CLIPS, FuzzyCLIPS может иметь дело с точными, нечеткими (или неточными) знаниями, сложными рассуждениями, которые можно свободно смешивать в правилах и фактах экспертной системы. Система использует две базисных концепции о неточности , нечеткость и неопределенность. Имеются версии для систем UNIX, Macintosh и IBM PC.Программное обеспечение распространяется бесплатно, но документация по FuzzyCLIPS имеет сроки использования. Находится на http://ai.iit.nrc.ca/home_page.html или более прямо, на URL http://ai.iit.nrc.ca/fuzzy/fuzzy.html или анонимном ftp-сервере ai.iit.nrc.ca:/pub/fzclips/
    WxCLIPS снабжает CLIPS v5.1, CLIPS v6.0 и CLIPS v6.0 с нечетким представлением знаний простым графическим внешним интерфейсом.Имеется WxCLIPS для Windows 3.1, 32-разрядного Windows и Windows 95. WxCLIPS находится на анонимном FTP-сервере Ftp.aiai.ed.ac.uk:/pub/packages/wxclips / [192.41.104.6] Или на http://www.aiai.ed.ac.uk/~jacs/wxclips/wxclips.html Чтобы Вас добавили к пользователям wxclips , пошлите сообщение по адресу wxclips-users-request@aiai.edinburgh.ac.uk. Другие оболочки экспертных систем
    SOAR - ftp.cs.cmu.edu : /afs/cs.cmu.edu/project/soar/public/Soar5/ - Версия на лиспе /afs/cs.cmu.edu/project/soar/public/Soar6/ - Версия на C Контакт: soar-request@cs.cmu.edu OPS5 - содержит механизмы представления знаний и управления. Хотя эта система обеспечивает основные потребности инженерии знаний, она не ориентирована на конкретные стратегии решения задач или схемы представления знаний. Система разрешает программисту использовать символы и представлять отношения между символами, однако эти символы и отношения не имеют заранее определенных значений. Последние полностью определяются порождающими правилами, которые пишет программист. Механизм управления интерпретатора OPS5 представляет собой простой цикл, называемый "циклом распознавания", детали которого пользователь разрабатываетсам в соответствии со своими потребностями. Находится по адресу: ftp.cs.cmu.edu:/user/ai/areas/expert/systems/ops5/ops5.tar.gz
    BABYLON - среда для разработки для экспертных систем . Она включает фреймы , модели данных, Пролог-подобный логический формализм, и язык для написания диагностических прикладных программ. Она написана на Лиспе и переносима на широкий диапазон аппаратных платформ. Располагается на анонимном ftp-сервере tp.gmd.de:/gmd/ai-research/Software/Babylon/ [129.26.8.84] как BinHexed stuffit архив, в WEB- сети по адресу http://www.gmd.de/
    MIKE (Микро Интерпретатор для инженерии знаний) - это полная, свободная и переносимая программная среда, разработанная для целей обучения в Открытом Университете ВЕЛИКОБРИТАНИИ. Она включает прямые и обратные правила вывода от цели к фактам с определяемыми пользователем cтратегиями разрешения противоречий, и фреймовый язык представления знаний с наследственностью и ' демонами', плюс определенные пользователем cтратегии наследования. Правила вывода автоматически снабжаются, объяснениями 'как ', пользователь может сформировать объяснения ' почему '. Порядок применения правил в процессе трассировки и выполнения может отображаться графически на дисплее. MIKE, который формирует ядро курса по Инженерии знаний Открытого Университета, написан на консервативном и переносимом подмножестве Пролога, исходный текст программы свободно распространяется. MIKE версии 1 был написан в октябре / ноябре 1990. MIKE v1.50, который прежде находился на ftp- сервере, был заменен двумя более новыми версиями: MIKE v2.03, полная версия исходного текста на Пролога, включая RETE алгоритм для быстрого поиска вперед, систему сопровождения , обработки неопределенности, и гипотетических миров, и MIKE V2.50, (DOS-версия под ключ) с интерфейсом, управляемым с помощью меню,и инструментальными средствами для создания и просмотра фреймов, полностью совместимая с MIKE V2.03, но без исходного текста. Они располагаются на анонимном ftp-сервере hcrl.open.ac.uk [137.108.81.16] в виде файлов: /pub/software/src/MIKEv2.03/* MIKEv2.50: /pub/software/pc/MIKEV25.ZIP Для получения дальнейшей информации войдите в контакт с Marc'ом Eisenstadt'ом M.Eisenstadt@open.ac.uk.
    ES: октябрь / ноябрь 1990 -экспертная система. ES поддерживают прямой / обратный вывод цепочки, нечеткие отношения , и содержит подсистему объяснения. Это - автономная программа, выполняемая на IBM-PC. ES располагается на анонимном ftp-сервере ftp.uu.net:/pub/ai/expert-sys/ [192.48.96.9] как summers.tar. Z. ftp.uu.net отражен на unix.hensa.ac.uk [129.12.21.7] под /pub/uunet/.
    WindExS (Экспертная система под Windows) - полнофункциональная экспертная система, использует вывод от фактов к цели, работает на базе Windows. Ее модульная архитектура позволяет пользователю заменять модули так, как это требуется для расширения возможностей системы. WindExS содержит процессор Правил на Естественном языке, Механизм логического вывода, Диспетчер файлов, Интерфейс пользователя, Администратор Сообщений и модули Базы знаний. Она поддерживает вывод от фактов к цели, и графическое представление базы знаний. Для получения документации и системы пишите по адресу etoupin@aol.com .
    RT-EXPERT - экспертная система общего назначения , что позволяет программистам C интегрировать правила экспертной системы в прикладные программы на языке C или C++. В состав RT-EXPERT входит транслятор правил, который компилирует правила в код C, и библиотека, содержащая механизм выполнения правил. RT-EXPERT под DOS работает с трансляторами Borland Turbo C, Borland C++, и C / C Microsoft ++.Лицензионная версия программы используется в области образования, исследований и хобби.Прикладные программы, созданные с помощью RT-EXPERT , не лицензированы для коммерческих целей. Профессиональные издания пригодны для коммерческих прикладных программ, использующих DOS, Windows, и Unix среды. RT-EXPERT располагается на анонимном ftp-сервере Word.std.com:/vendors/rtis/rtexpert

6.1 Стадии создания экспертных систем.[21]:

    По стадии создания выделяют:

  • Исследовательский образец ЭС, разработанный за 1-2 месяца с минимальной БЗ.
  • Демонстрационный образец ЭС, разработанный за 2-4 месяца, например, на языке типа LISP, PROLOG, CLIPS
  • Промышленный образец ЭС, разработанный за 4-8 месяцев, например, на языке типа CLIPS с полной БЗ.
  • Коммерческий образец ЭС, разработанный за 1,5-2 года, например, на языке типа С++, Java с полной БЗ.

6.2 Этапы разработки экспертных систем.

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

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

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

Этап выполнения.
    Цель этого этапа - создание одного или нескольких прототипов ЭС, решающих требуемые задачи. Затем на данном этапе по результатам тестирования и опытной эксплуатации создается конечный продукт, пригодный для промышленного использования. Разработка прототипа состоит в программировании его компонентов или выборе их из известных инструментальных средств и наполнении базы знаний.
    Главное в создании прототипа заключается в том, чтобы этот прототип обеспечил проверку адекватности идей, методов и способов представления знаний решаемым задачам. Создание первого прототипа должно подтвердить, что выбранные методы решений и способы представления пригодны для успешного решения, по крайней мере, ряда задач из актуальной предметной области, а также продемонстрировать тенденцию к получению высококачественных и эффективных решений для всех задач предметной области по мере увеличения объема знаний.
    После разработки первого прототипа ЭС-1 круг предлагаемых для решения задач расширяется, и собираются пожелания и замечания, которые должны быть учтены в очередной версии системы ЭС-2. Осуществляется развитие ЭС-1 путем добавления "дружественного" интерфейса, средств для исследования базы знаний и цепочек выводов, генерируемых системой, а также средств для сбора замечаний пользователей и средств хранения библиотеки задач, решенных системой.
    Выполнение экспериментов с расширенной версией ЭС-1, анализ пожеланий и замечаний служат отправной точкой для создания второго прототипа ЭС-2. Процесс разработки ЭС-2 итеративный. Он может продолжаться от нескольких месяцев до нескольких лет в зависимости от сложности предметной области, гибкости выбранного представления знаний и степени соответствия управляющего механизма решаемым задачам (возможно, потребуется разработка ЭС-3 и т.д.). При разработке ЭС-2, кроме перечисленных задач, решаются следующие:


    Если ЭС-2 успешно прошла этап тестирования, то она может классифицироваться как промышленная экспертная система. Этап тестирования.
    В ходе данного этапа производится оценка выбранного способа представления знаний в ЭС в целом. Для этого инженер по знаниям подбирает примеры, обеспечивающие проверку всех возможностей разработанной ЭС.
    Различают следующие источники неудач в работе системы: тестовые примеры, ввод-вывод, правила вывода, управляющие стратегии. Показательные тестовые примеры являются наиболее очевидной причиной неудачной работы ЭС. В худшем случае тестовые примеры могут оказаться вообще вне предметной области, на которую рассчитана ЭС, однако чаще множество тестовых примеров оказывается слишком однородным и не охватывает всю предметную область. Поэтому при подготовке тестовых примеров следует классифицировать их по подпроблемам предметной области, выделяя стандартные случаи, определяя границы трудных ситуаций и т.п.
    Ввод-вывод характеризуется данными, приобретенными в ходе диалога с экспертом, и заключениями, предъявленными ЭС в ходе объяснений. Методы приобретения данных могут не давать требуемых результатов, так как, например, задавались неправильные вопросы или собрана не вся необходимая информация. Кроме того, вопросы системы могут быть трудными для понимания, многозначными и не соответствующими знаниям пользователя. Ошибки при вводе могут возникать также из-за неудобного для пользователя входного языка. В ряде приложения для пользователя удобен ввод не только в печатной, но и в графической или звуковой форме.
    Выходные сообщения (заключения) системы могут оказаться непонятны пользователю (эксперту) по разным причинам. Например, их может быть слишком много или, наоборот, слишком мало. Также причиной ошибок может являться неудачная организация, упорядоченность заключений или неподходящий пользователю уровень абстракций с непонятной ему лексикой.
    Наиболее распространенный источник ошибок в рассуждениях касается правил вывода. Важная причина здесь часто кроется в отсутствии учета взаимозависимости сформированных правил. Другая причина заключается в ошибочности, противоречивости и неполноте используемых правил. Если неверна посылка правила, то это может привести к употреблению правила в неподходящем контексте. Если ошибочно действие правила, то трудно предсказать конечный результат. Правило может быть ошибочно, если при корректности его условия и действия нарушено соответствие между ними.
    Нередко к ошибкам в работе ЭС приводят применяемые управляющие стратегии. Изменение стратегии бывает необходимо, например, если ЭС анализирует сущности в порядке, отличном от "естественного" для эксперта. Последовательность, в которой данные рассматриваются ЭС, не только влияет на эффективность работы системы, но и может приводить к изменению конечного результата. Так, рассмотрение правила А до правила В способно привести к тому, что правило В всегда будет игнорироваться системой. Изменение стратегии бывает также необходимо и в случае неэффективной работы ЭС. Кроме того, недостатки в управляющих стратегиях могут привести к чрезмерно сложным заключениям и объяснениям ЭС.
    Критерии оценки ЭС зависят от точки зрения. Например, при тестировании ЭС-1 главным в оценке работы системы является полнота и безошибочность правил вывода. При тестировании промышленной системы превалирует точка зрения инженера по знаниям, которого в первую очередь интересует вопрос оптимизации представления и манипулирования знаниями. И, наконец, при тестировании ЭС после опытной эксплуатации оценка производится с точки зрения пользователя, заинтересованного в удобстве работы и получения практической пользы

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

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

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

6.3 Разработка прототипа экспертной системы[18]:


    При разработке практически всех инструментальных средств за основу принимается методология автоматизации проектирования на базе использования прототипов. По отношению к программному обеспечению термин прототип означает "работающую модель программы, которая функционально эквивалентна подмножеству конечного продукта". Идея состоит в том, чтобы на ранней стадии работы над проектом разработать упрощенную версию конечной программы, которая могла бы послужить доказательством продуктивности основных идей, положенных в основание проекта. Прототип должен быть способен решать какую-либо из нетривиальных задач, характерных для заданной области применения. На основе анализа опыта работы с прототипом разработчики могут уточнить требования к системе в целом и ее Основным функциональным характеристикам. Работоспособность прототипа может послужить очевидным доказательством возможности решения проблем с помощью создаваемой системы еще до того, как на ее разработку будут потрачены значительные средства.
    После всестороннего анализа прототип откладывается в сторону и начинается разработка рабочей версии программы, которая должна решать весь комплекс задач, определенных в спецификации проекта. Процесс разработки экспертной системы, как правило, состоит из последовательности отдельных этапов, на которых наращиваются возможности системы, причем каждый из этапов подразделяется на фазы проектирования, реализации, компоновки и тестирования. В результате после каждого этапа наращивания возможностей в распоряжении пользователя имеется система, которая способна справляться со все более сложными вариантами проблемы.
    Такая методика проектирования несколько отличается от методики разработки программ других видов. При создании большинства программных продуктов чаще используется другая модель процесса- сначала разрабатывается спецификация продукта, затем выполняется планирование, проектирование компонентов, их реализация, компоновка комплекса и тестирование конечного варианта. Тот факт, что при разработке экспертных систем есть возможность сначала построить и всесторонне испытать прототип, позволяет избежать множества переделок в процессе создания рабочей версии системы. Но технология последовательного наращивания функциональных возможностей таит в себе и проблему интеграции новых функций с реализованными в предыдущих вариантах. Инструментальные средства разработки экспертных систем и создавались, в первую очередь, с целью преодоления возникающих при этом сложностей на основе модульного представления знаний.
    При неудовлетворительном функционировании прототипа эксперт и инженер по знаниям имеют возможность оценить, что именно будет включено в разработку окончательного варианта системы.
    Если первоначально выбранные объекты или свойства оказываются неподходящими, их необходимо изменить. Можно сделать оценку общего числа эвристических правил, необходимых для создания окончательного варианта экспертной системы. Иногда при разработке промышленной системы выделяют дополнительные этапы[22]:
  • демонстрационный прототип
  • исследовательский прототип
  • действующий прототип
  • промышленная система.

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

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

Список литературы

  1. Попов Э.В. Экспертные системы: Решение неформализованных задач в диалоге с ЭВМ. - М.: Наука. Гл. ред. физ.-мат. Лит., 1987 г.
  2. Марселлус Д. Программирование экспертных систем на Турбо Прологе: Пер. с англ. - М.: Финансы и статистика, 1994 г.
  3. Моисеев В.Б. Представление знаний в интеллектуальных системах. Информатика и образование,. ?2, 2003 г. с. 84-91
  4. Андрейчиков А.В., Андрейчикова О.Н. Интеллектуальные информационные системы: М. Наука, 2004 г.
  5. Зубов В. В., Макушкин В. А., Оглоблин А. Г. Экспертная система диагностирования цифровых устройств и БИС. Средства связи, ?3, 1988, с. 32-36.
  6. Зубов В. В., Макушкин В. А. Экспертная система диагностирования цифровых устройств ДИЭКС на персональной ЭВМ.ЭКСПЕРТНЫЕ СИСТЕМЫ НА ПЕРСОНАЛЬНЫХ КОМПЬЮТЕРАХ, М.: МДНТП, 1990, с. 115-120.
  7. Макушкин В. А., Щербицкий К. А. Экспертная система для контроля и диагностирования цифроаналоговых устройств. НОВЫЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В ПЛАНИРОВАНИИ, УПРАВЛЕНИИ И В ПРОИЗВОДСТВЕ, М.: МДНТП, 1991, с. 121-125.
  8. Попов Э. В., Фоминых И. Б., Кисель Е. Б., Шапт М. Д.Статические и динамические экспертные системы. М.: Финансы и статистика, 1996 г.
  9. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб: Питер, 2001г.
  10. Володичев Д.С., Макушкин В.А. OMEGAMON - эффективная система управления вычислительными ресурсами. М: Научная сессия МФТИ-2004, том 12, с.199-201.
  11. Муромцев Д.И. Введение в технологию экспертных систем. СПб: СПб ГУ ИТМО, 2005.
  12. Минский М.Л. Фреймы для представления знаний. М.:Энергия, 1979.
  13. www.intuit.ru
  14. www.ai.tsi.lv
  15. knpi-iip.mipk.kharkiv.edu
  16. www.libray.narod.ru
  17. expro.kzn.ru
  18. 256bit.ru
  19. ru.wikipedia.org
  20. 256bit.ru
  21. tver.mesi.ru
  22. www.ssti.ru
  23. Моделирование управления движением человека М.: СпортАкадемПресс, 2003. 360 с., сборник научных трудов под ред. Шестакова М. П. и Аверкина А. Н.
  24. Люгер Д. Искусственный интеллект М.: Мир, 2003. 690 с.
  25. Макаров И. М., Топчиев Ю. И. Робототехника. История и перспективы М.: Наука, МАИ, 2003. 350 с.
  26. Ярушкина Н. Г Основы теории нечетких и гибридных систем Учебное пособие, М.: Финансы и статистика, 2004. 320 c.
  27. Рыбина Г. В., Пышагин С. В., Смирнов В. В., Левин Д. Е., Душкин Р. В. Инструментальный комплекс АТ-ТЕХНОЛОГИЯ для поддержки разработки интегрированных экспертных систем учебное пособие, М.: МИФИ, 2001, 100 с.
  28. Частиков А. П., Гаврилова Т. А., Белов Д. Л. Разработка экспертных систем. Среда CLIPS BHV-Санкт-Петербург, 2003 г., 606 стр.
  29. И. Абдуллин. Программирование в промышленности. - М.: Логос. 2000г
  30. Г. Долин. Что такое ЭС. - Компьютер Пресс, 2002 г.
  31. К. Нейлор. Как построить свою экспертную систему.- М.: Энегроатомиздат, 2001.
  32. В.О. Сафонов. Экспертные системы - интеллектуальные помощники специалистов. - СПб.: Санкт-Петербургская организация общества 'Знания Росси', 2002.
  33. К. Таусенд, Д. Фохт. Проектирование и программная реализация экспертных систем на персональных ЭВМ. М.: Финансы и статистика. 2000.
  34. Н. Убейко. Экспертные системы. - М.: МАИ, 2002.
  35. Д. Джарратано, Г. Райли. Экспертные системы. Принципы разработки и программирование. Изд. Вильямс, 2006.
  36. В.В. Круглов. Интеллектуальные информационные системы. 2002.
  37. В. Л. Афонин, В.А. Макушкин. Интеллектуальные робототехнические системы. ИНТУИТ.РУ, 2005.