Лекционный материал по ИИС для самостоятельного изучения. 2 Модели представления знаний 2 Логическая модель представления знаний
Скачать 2.32 Mb.
|
3.2. Машина вывода экспертных систем Понятие и работа машины вывода. Несмотря на все недостатки, наибольшее распространение получила продукционная модель представления знаний. При использовании продукционной модели база знаний состоит из набора правил. Машина вывода (интерпретатор) – это программа, управляющая перебором правил в базе знаний. Машина вывода(интерпретатор правил) выполняет две функции: во-первых, просмотр существующих фактов из рабочей памяти и правил из базы знаний и добавление (по мере возможности) в рабочую память новых фактов и, во-вторых, определение порядка просмотра и применения правил. Этот механизм управляет процессом консультации, сохраняя для пользователя информацию о полученных заключениях, и запрашивает у него информацию, когда для срабатывания очередного правила в рабочей памяти оказывается недостаточно данных. В подавляющем большинстве систем, основанных на знаниях, механизм вывода представляет собой небольшую по объему программу и включает два компонента, реализующих вышеприведенные функции. Действие компонента выводаосновано на применении правила, называемого modusponens:. 91 «Если известно, что истинно утверждение А и существует правило вида «ЕСЛИ А, ТО В», тогда утверждение В также истинно». Правила срабатывают, когда находятся факты, удовлетворяющие их левой части: если истинна посылка, то должно быть истинно и заключение.Компонент вывода должен функционировать даже при недостатке информации. Полученное решение может и не быть точным, однако система не должна останавливаться из-за того, что отсутствует какая- либо часть входной информации. Управляющий компонентопределяет порядок применения правил и выполняет четыре функции. Сопоставление —правила сопоставляются с имеющимися фактами, полученными от пользователя или в результате срабатывания правила.. Выбор — если в конкретной ситуации может быть применено сразу несколькоправил, то из них выбирается одно, наиболее подходящее по заданному критерию (разрешение конфликта). Срабатывание — выполнение части «ТО» выбранного правила. Действие — рабочая память подвергается изменению путем добавления в нее заключения сработавшего правила. Если в правой части правила содержится указание на какое- либо действие (воздействие), то оно выполняется. Воздействие может понадобиться, например, в системах обеспечения безопасности информации – отключение линии связи, запрет удаления и т.п. 92 Работа машины вывода (интерпретатора). Машина вывода (Интерпретатор продукций) работает циклически. Цикл работы интерпретатора схематически представлен на рис.3.5. Рис.3.5. Цикл работы машины вывода. Информация из рабочей памяти (базы данных) последовательно сопоставляется с условными частямиправил из базы правил для выявления успешного сопоставления. Совокупность успешно отобранных правил составляет так называемое конфликтное множество. Для разрешения конфликта интерпретатор имеет критерий, с помощью которого он выбирает единственное выполняемое правило. 93 После чего оно срабатывает и выполняется действие. Действие может выражаться: в занесении нового факта (заключения сработавшего правила) в рабочую память; в изменении критерия выбора конфликтующих правил, воздействии на что- либо (например, отключение аварийного блока). Затем цикл повторяется снова, до тех пор пока не перестанет образовываться конфликтное множество. Заключение последнего сработавшего правила выдается пользователю в качестве результата решения задачи. Работа машины вывода зависит только от состояния рабочей памяти и от состава базы знаний. Таким образом, в каждом цикле просматриваются все правила, но одном цикле может сработать только одно правило Стратегии управления выводом. От выбранного метода поиска, то есть стратегии вывода, будет зависеть порядок применения и срабатывания правил. Процедура выбора сводится к определению направления поиска и способа его осуществления. Процедуры, реализующие поиск, обычно «зашиты» в механизм вывода, поэтому в большинстве систем инженеры знаний не имеют к ним доступа и, следовательно, не могут в них ничего изменять по своему желанию. Вывод - Получение новых информационных единиц из ранее известных. Частным случаем является логический вывод. При разработке стратегии управления выводом важно определить два вопроса: 94 Какую точку в пространстве состояний принять в качестве исходной? От выбора этой точки зависит и метод осуществления поиска — в прямом или обратном направлении. Какими методами можно повысить эффективность поиска решения? Эти методы определяются выбранной стратегией перебора — глубину, в ширину, по подзадачам или иначе (например, Альфа-бета алгоритм). Прямой и обратный выводы. Обратный вывод - вывод, при котором поиск доказательства начинается с целевого утверждения. При обратном порядке вывода вначале выдвигается некоторая гипотеза (выясняются условия), которая доказывает утверждение. Затем механизм вывода как бы возвращается назад, переходя к фактам, пытаясь найти те, которые подтверждают гипотезу (рис.3.6, правая часть). Если она оказалась правильной, то выбирается следующая гипотеза, детализирующая первую и являющаяся по отношению к ней подцелью. Далее отыскиваются факты, подтверждающие истинность этой (подчиненной) гипотезы и т.д., пока очередная гипотеза не приведет (укажет) к факту (цели). Вывод такого типа называется управляемым целями, или управляемым консеквентами. Обратный поиск применяется в тех случаях, когда цели известны и их сравнительно немного. 95 Рис. 3.6. Стратегии вывода Прямой вывод. В системах с прямым выводом по известным фактам отыскивается утверждение (заключение), которое из этих фактов следует (рис.3.6, левая часть). Если такое заключение удается найти, то оно заносится в рабочую память. Прямой вывод часто называют выводом, управляемым данными, или выводом, управляемым антецедентами. Рассмотрим пример.Имеется фрагмент базы знаний из двух правил: Правило 1: Если «отдых — летом» и «человек — активный», то «ехать в горы». Правило 2: Если «любит солнце», то «отдых летом». Предположим, в систему ввели факты— «человек активный» и «любит солнце». 96 Обратный вывод — подтвердить выбранную цель (в данном случае - «ехать в горы») при помощи имеющихся правил и данных. 1-й цикл Шаг 1.1. Утверждение (Цель) — «ехать в горы»: Проверяем правило П1— не хватает данных (факта) «отдых — летом». Поэтому эти данные (факт) («отдых — летом») становятся новым утверждением (целью) и ищется правило, где такое утверждение (цель) есть в левой части. Шаг 1.2. Утверждение (Цель) «отдых — летом»: Проверяем правило П2. Это правило срабатывает и в системе появляется факт - «любит солнце». 2-й цикл. Шаг 2.1. Проверяем правилоП1: наличие обоих фактов («отдых — летом» и «человек — активный») подтверждают выбранную цель («ехать в горы»). Прямой вывод— нужно исходя из фактических данных, получить рекомендацию. 1-й цикл. Шаг 1.1. Проверяем правило П1: не работает, т.к. не хватает данных «отдых — летом». Шаг 1.2. Проверяем правило П2: работает, т.к. есть факт «любит солнце». Следовательно, образуется новый факт «отдых — летом». 2-й цикл. Шаг 2.1. Проверяем правило П1, работает, т.к. присутствуют оба факта - «отдых — летом» и «человек — активный». Следовательно, становится истинным 97 утверждение (цель) «ехать в горы», которая и выступает как совет, который дает ЭС. Существуют системы, в которых вывод основывается на сочетании упомянутых выше методов — обратного и ограниченного прямого. Такой комбинированный метод получил название циклического. 3.3. Этапы разработки экспертных систем В настоящее время сложилась определенная технология разработки ЭС, которая включает следующие шесть этапов (рис.3.7): идентификация, концептуализация, формализация, выполнение, тестирование опытная эксплуатация. На этапе идентификации определяются задачи, которые подлежат решению, выявляются цели разработки, определяются эксперты и типы пользователей.Идентификация задачи заключается в составлении неформального (вербального) описания, в котором указываются: общие характеристики задачи; подзадачи, выделяемые внутри данной задачи; ключевые понятия (объекты), их входные (выходные) данные; предположительный вид решения, а также знания, относящиеся к решаемой задаче. 98 Результатом данного этапа является ответ на вопрос, что надо сделать и какие ресурсы необходимо задействовать (идентификация задачи, определение участников процесса проектирования и их роли, выявление ресурсов и целей).На выходе этапа – требования к экспертной системе. Рис.3.7 Этапы разработки ЭС. На этапе концептуализации проводится содержательный анализ проблемной области и решаемой задачи, выявляются используемые понятия и их взаимосвязи, определяются методы решения задачи. Этот этап завершается созданием модели предметной области, включающей основные концепты и отношения. На этапе концептуализации определяются следующие особенности задачи: типы доступных данных; исходные и выводимые данные, подзадачи общей задачи; используемые стратегии и гипотезы; виды взаимосвязей между объектами, типы используемых отношений (иерархия, причина — следствие, часть — целое и т.п.); процессы, используемые в 99 ходе решения; состав знаний, используемых при решении задачи; типы ограничений, накладываемых на процессы, используемые в ходе решения; состав знаний, используемых для обоснования решений.На выходе - понятия и их взаимосвязи. На этапе формализации выбираются инструментальные средства разработки, определяются способы представления всех видов знаний, формализуются основные понятия, определяются способы интерпретации знаний, разрабатывается программная оболочка (прототип), моделируется работа системы, оценивается адекватность системы. Выходом этапа формализации является описание того, как рассматриваемая задача может быть представлена в выбранном или разработанном формализме. Сюда относится указание способов представления знаний (фреймы, сценарии, семантические сети и т.д.) и определение способов манипулирования этими знаниями (логический вывод, аналитическая модель, статистическая модель и др.) и интерпретации знаний.В конце этапа имеем структуру системы. На этапе выполнения осуществляется создание одного или нескольких прототипов ЭС, решающих требуемые задачи,наполнение экспертом базы знаний. В связи с тем, что основой ЭС являются знания, данный этап является наиболее важным и наиболее трудоемким этапом разработки ЭС. Процесс приобретения знаний разделяют на извлечение знаний из эксперта, формализацию знаний, обеспечивающую эффективную работу системы, и представление знаний в виде, понятном ЭС. Процесс приобретения знаний осуществляется инженером по знаниям на основе анализа 100 деятельности эксперта по решению реальных задач. На выходе этапа – программная реализация всех структурных элементов экспертной системы (рис.3.2). Этап тестирования. В ходе данного этапа производится оценка выбранного способа представления знаний в ЭС в целом. Для этого инженер по знаниям совместно с экспертом подбирает тестовые примеры, обеспечивающие проверку возможностей разработанной ЭС. При подготовке тестовых примеров следует классифицировать их по подпроблемам предметной области, выделяя стандартные случаи, определяя границы трудных ситуаций и т.п. Степень соответствия решения тестового примера полученного экспертной системой и известного решения характеризует качество разработки системы. Главным в оценке работы системы является полнота и безошибочность работы правил вывода. На этом этапе опытной эксплуатации проверяется пригодность ЭС для конечного пользователя. Пригодность ЭС для пользователя определяется в основном удобством работы с ней и ее полезностью. Под полезностью ЭС понимается ее способность в ходе диалога определять потребности пользователя, выявлять и устранять причины неудач в работе, а также удовлетворять указанные потребности пользователя (решать поставленные задачи). В свою очередь, удобство работы с ЭС подразумевает естественность взаимодействия с ней (общение в привычном, не утомляющем пользователя виде), гибкость ЭС (способность системы настраиваться на различных пользователей, а также учитывать изменения в квалификации одного и того же пользователя) и устойчивость системы к ошибкам (способность не выходить из строя при ошибочных действиях неопытного пользователях). 101 В ходе разработки ЭС почти всегда осуществляется ее модификация. Выделяют следующие виды модификации системы: переформулирование понятий и требований, переконструирование представления знаний в системе и усовершенствование прототипа. 3.4. Коллектив разработчиков ЭС. Под коллективом разработчиков понимается группа специалистов, ответственных за создание ЭС.В разработке ЭС участвуют представители следующих специальностей. Эксперт определяет знания (данные и правила), характеризующие проблемную область, обеспечивает полноту и правильность введенных в ЭС знаний. Инженер по знаниям помогает эксперту выявить и структурировать знания, необходимые для работы ЭС; осуществляет выбор того инструментального средства, которое наиболее подходит для данной проблемной области, и определяет способ представления знаний. Руководит коллективом. Программист(ы)осуществляет программную реализацию ЭС, сопрягает все основные компоненты ЭС. Пользовательосуществляет проверку удобства работы с ЭС на заключительных этапах разработки. Конечно же его нельзя отнести к специалистам, однако его роль достаточно важна. Таким образом, минимальный состав коллектива включает четыре человека; реально же он разрастается до 8- 10 человек. Численное увеличение коллектива разработчиков 102 происходит по следующим причинам: необходимость учета мнения нескольких пользователей, помощи нескольких экспертов; потребность как в проблемных, так и системных программистах. На Западе в этот коллектив дополнительно традиционно включают менеджера и одного технического помощника.При отсутствии профессионального менеджера руководителем, участвующим во всех стадиях разработки, является инженер по знаниям, поэтому к его квалификации предъявляются самые высокие требования. В целом уровень и численность группы зависят от характеристик постав- ленной задачи. Для обеспечения эффективности работы любой творческой группы, в том числе и группы разработчиков ЭС, необходимо возникновение атмосферы взаимопонимания и доверия, которое, в свою очередь, обусловлено психологической совместимостью членов группы; следовательно, при формировании группы должны учиты- ваться психологические свойства участников. Приведем два аспекта характеристик членов коллектива разработчиков ЭС: 1 — психофизиологический, 2 — профессиональный. Эксперт. 1.Психологические качества. Эксперт — чрезвычайно важная фигура в группе. В конечном счете, его подготовка определяет уровень компетенции базы знаний. Желательные качества: а) доброжелательность; б) готовность поделиться своим опытом; в) умение объяснить (педагогические навыки); 103 г) заинтересованность (моральная, а лучше еще и материальная) в успешности разработки. Возраст эксперта обычно почтенный, что необходимо учитывать всем членам группы. Часто встает вопрос о количестве экспертов. Поскольку проблема совмещения подчас противоречивых знаний остается открытой, обычно с каждым из экспертов работают индивидуально, иногда создавая альтернативные базы. 2. Профессиональные качества. Помимо безусловно высокого профессионализма в выбранной предметной области, желательно знакомство эксперта с популярной литературой по искусственному интеллекту и экспертным системам для того, чтобы эффективнее прошел этап извлечения знаний. Инженер по знаниям. 1. Психологические качества. Существуют такие профессии и виды деятельности, для которых природные качества личности (направленность, способности, темперамент) могут иметь характер абсолютного показания или противопоказания к занятиям. По-видимому, инженерия знаний принадлежит к таким профессиям. По различным оценкам, это одна из самых малочисленных, высокооплачиваемых и дефицитных в мире специальностей. Попытаемся дать наброски к портрету инженера по знаниям (без претензии на полноту и точность определений). Пол. Психологи утверждают, что мужчины более склонны к широкому охвату явлений и в среднем у них выше аналитичность, чрезвычайно полезная инженеру по знаниям, которому надо иметь развитое логическое мышление и умение оперировать сложными формальными структурами. 104 Кроме того, при общении с экспертами, которые в большинстве своем настроены скептически по отношению к будущей ЭС, инженер по знаниям – мужчина вызывает более высокую мотивацию успешности со стороны эксперта- женщины. С другой стороны, известно, что у женщин выше наблюдательность к отдельным деталям объектов. Так что пол не является окончательным показанием или проти- вопоказанием к данной профессии. Интеллект. Это понятие вызывает самые бурные споры психологов; существует до 50 определений интеллекта, но с прагматической точки зрения очевидно, что специалист в области искусственного интеллекта должен стремиться к максимальным оценкам по тестам как вербального, так и невербального интеллекта. Стиль общения. Инженер по знаниям «задает тон» в общении с экспертом, он ведет диалог, и от него в конечном счете зависит его продуктивность. Можно выделить два стиля общения: деловой (или жесткий) и дружеский (или мягкий, деликатный). Нам кажется, что дружеский будет заведомо более успешным, так как снижает «эффект фасада» у эксперта, раскрепощает его. Деликатность, внимательность, интеллигентность, ненавязчивость, скромность, умение слушать и задавать вопросы, хорошая коммуникабельность и в то же время уверенность в себе — вот рекомендуемый стиль общения. Безусловно, что это дар и искусство одновременно, однако занятия по психологическому тренингу могут дать полезные навыки. Портрет инженера по знаниям можно было бы дополнить другими характеристиками — широтой взглядов и интересов, артистичностью, чувством юмора, обаянием и т. д. 105 2. Профессиональные качества.При определении профессиональных требований к аналитику следует учиты- вать, что ему необходимы различные навыки и умения для грамотного и эффективного проведения процессов извлечения, концептуализации и формализации знаний. Инженер по знаниям имеет дело со всеми формами знаний Z1 (знания в памяти) Z2 (знания в книгах) Z3 (поле знаний) Z4 (модель знаний) Z5 (база знаний). Работа на уровне Z1 требует от инженера по знаниям знакомства с элементами когнитивной психологии и способами репрезентации понятий и процессов в памяти человека, с двумя основными механизмами мышления – логическим и ассоциативным, с такими способами активизации мышления как игры, мозговой штурм и др., с различными моделями рассуждений. Изучение и анализ текстов на уровне Z2 подразумевает широкую общенаучную подготовку инженера; знакомство с методами реферирования и аннотирования текстов; владение навыками быстрого чтения, а также текстологическими мето- дами извлечения знаний. Разработка поля знаний на уровне Z3 требует квалифицированного знакомства с методологией представления знаний, системным анализом, теорией познания, аппаратом многомерного шкалирования, кластерным и факторным анализом. Разработка формализованного описания Z4 предусматривает предварительное изучение аппарата математической логики и современных языков представле- ния знаний. Модель знаний разрабатывается на основании результатов глубокого анализа инструментальных средств 106 разработки ЭС и имеющихся «оболочек». Кроме того, инженеру по знаниям необходимо владеть методологией разработки ЭС, включая методы быстрого прототипирования. И наконец, реализация базы знаний Z5, в которой инженер по знаниям участвует вместе с программистом, подразумевает овладение практическими навыками работы на ЭВМ и, возможно, одним из языков программирования. Так как инженеров по знаниям «выращивают» из программистов, уровень Z5 обычно не вызывает затруднения, особенно если разработка ведется на традиционных языках типа С или Паскаль. Специализированные языки искусственного интеллекта Лисп и Пролог требуют некоторой перестройки архаично–алгоритмического мышления. Программист. 1. Психологические качества.Известно, что программисты обладают самой низкой потребностью в общениисреди представителей разных профессий. Однако при разработке ЭС необходим тесный контакт членов группы, поэтому желательны следующие его качества: а) общительность; б) способность отказаться от традиционных навыков и освоить новые методы; в) интерес к разработке. 2.Профессиональные качества.Поскольку современные ЭС — сложнейшие и дорогостоящие программные комплексы, программисты должны иметь опыт и навыки разработки программ. Обязательно знакомство с основными структурами представления знаний и механизмами вывода, 107 состоянием отечественного и мирового рынка программных продуктов для разработки ЭС и диалоговых интерфейсов. Пользователь. 1. Психологические качества. К пользователю предъявляются самые слабые требования, поскольку его не выбирают. Он является в некотором роде заказчиком системы. Желательные качества: а) дружелюбие; б) умение объяснить, что же он хочет от системы; в) отсутствие психологического барьера к применению вычислительной техники; г) интерес к новому. От пользователя зависит, будет ли применяться разра- ботанная ЭС. Замечено, что наиболее ярко качества в) и г) проявляются в молодом возрасте, поэтому иногда такие пользователи охотнее применяют ЭС, не испытывая при этом комплекса неполноценности оттого, что ЭВМ им что-то подсказывает. 2. Профессиональные качества. Необходимо, чтобы пользователь имел некоторый базовый уровень квалифи- кации, который позволит ему правильно истолковать рекомендации ЭС. Кроме того, должна быть полная совместимость в терминологии интерфейса к ЭС с той, которая привычна и удобна для пользователя. Обычно требования к квалификации пользователя не очень велики, иначе он переходит в разряд экспертов и совершенно не нуждается в ЭС. 108 Таким образом, успешность выбора и подготовки коллектива разработчиков ЭС определяет эффективность и продолжительность всего процесса разработки. 3.5. Основы разработки экспертной системы Постановка задачи. Прежде всего, поставим задачу, для решения которой будет разрабатываться экспертная система. Подходящей задачей, при решении которой можно использовать обратную цепочку рассуждений, может быть задача, вытекающая из следующей ситуации: к директору крупной технической фирмы пришел человек, желающий устроиться на работу. Директор располагает сведениями о потребностях фирмы в специалистах и общем положении дел в фирме. Ему нужно решить, какую должность в фирме может занять посетитель. Для этого необходимо задать посетителю такие вопросы, ответы на которые дадут возможность сделать правильный выбор должности. На первый взгляд задача не очень сложная, но на решение директора влияет много факторов. Допустим, претендент работает в данной области недавно, но уже сделал важное открытие или он закончил учебное заведение с посредственными оценками, но несколько лет работал по специальности. В данной ситуации люди ведут себя по- разному, и хотя для того, чтобы получить работу необходимо, удовлетворять определенным критериям, в биографии претендента могут быть самые различные факты, анализ которых поможет подобрать для него соответствующую должность.Поскольку в задаче надо выбрать один из нескольких возможных вариантов 109 (должностей), для еѐ решения можно воспользоваться обратной цепочкой рассуждений. Таким образом, необходимо разработать экспертную систему, которая определит подходящую должность посетителю. Экспертная система будет содержать экспертные знания директора и заменит его при решении описанной задачи. Такой системой может пользоваться как сам посетитель, так и менее квалифицированный (не эксперт - директор) сотрудник фирмы. Итак, задача поставлена. Теперь нужно наглядно ее представить. Для описания подобных задач обычно используются диаграммы, которые называются деревьями решений. Деревья решений дают необходимую наглядность и позволяют проследить ход рассуждений. Разработка дерева решений. Дерево решений – это ориентированный граф, вершинами которого являются условия и выводы, а дугами результат выполнения (проверки) условий. Диаграммы называются деревьями решений потому, что, подобно настоящему дереву, имеют ветви. Ветви деревьев решений заканчиваются логическими выводами. Для рассматриваемого примера вывод заключается в том, предложит ли директор должность поступающему на работу, и если да, то какую. Многие задачи сложны, и их непросто представить (или для их решения не собираются использовать экспертную систему). Дерево решений помогает преодолеть эти трудности. 110 На рис.3.8 показано дерево решений для рассматриваемого примера приема на работу. Видно, что диаграмма состоит из кружков и прямоугольников, которые называются вершинами. Каждой вершине присваивается номер. На вершины можно ссылаться по этим номерам. Номера вершин можно выбрать произвольно, т.к они и служат только для удобства идентификации, за исключением первой вершины. Линии, соединяющие вершины, называются дугами. Совокупность вершин и дуг называется ветвями. Кружки, содержащие вопросы, называются вершинами условий. Прямоугольники содержат логические выводы. Линии (стрелки) показывают направление диаграммы. Подписи возле линий это ответы на вопрос, содержащийся в вершине условия. Вершины условий могут иметь сразу по нескольку выходящих линий (стрелок), связывающих их с другими вершинами. В этом случае каждая линия (стрелка) должна быть четко определена. Не может быть две линии, у которых подписи одинаковые, например, подпись «Да». Выбор выходящей из вершины ветви определяется проверкой условия (вопроса), содержащегося в вершине. В программе под каждую вершину отводится переменная, а затем ей присваивается значение (ответ посетителя). Можно сказать, что вершины содержат переменные, а пути - это условия, в соответствии с которыми переменным присваиваются значения. В дереве решений могут быть локальные (частные) выводы или цели. Для рассматриваемого примера локальным выводом может быть содержащийся в прямоугольнике 3 ответ на вопрос,будет ли посетителю предложена должность. Однако эта вершина имеет и исходящие ветви, и, следовательно, через неѐ может проходить путь к следующему логическому выводу. В последнем случае, 111 поскольку исходящая ветвь не содержит условия и она только одна, говорят, что вершина содержит локальный вывод для другой цели. Локальный вывод - это также составляющая условной части (ЕСЛИ) правила. Рис.3.8. Дерево решений для выбора должности Преобразование дерева решений в правила. Как уже говорилось, правило «ЕСЛИ-ТО» состоит из двух частей. Часть ЕСЛИ может включать несколько условий, которые связываются между собой логическими операторами И, ИЛИ и НЕ. Часть ТО правила включается в работу только в том случае, если истинны все условия в 112 условной части. В дереве решений обеим частям правила соответствуют связанные между собой вершина(ы) логического условия(ий) (кружки) и вершина логического вывода (прямоугольник). Условная часть содержит все вершины условия, находящиеся на пути к логическому выводу, т.е. каждая вершина решения на пути к выводу - это одно условие части ЕСЛИ, например, вершины 1 и 4. Вывод же составляет часть ТО правила, в данном примере вершины 6, 8 и т.д. Порядок формирования правил: Выбрать из дерева решений вершину вывода (прямоугольник) и зафиксировать еѐ. В обратном направлении линии (стрелки) найти вершину условия (кружок) и зафиксировать еѐ. Повторять шаг 2 до тех пор, пока не будут исчерпаны все вершины условия, расположенные в обратном направлении стрелок от зафиксированной вершины вывода, или не встретится вершина локального вывода. Если встретилась вершина локального вывода, то еѐ надо зафиксировать и прекратить выполнение шага 2. Каждая вершина условия (кружок), составляющая путь, - это одна из переменных части ЕСЛИ правила. Эти вершины объединяются логическим оператором И. Выбранный на шаге 1 логический вывод перенести в часть ТО правила. Пример создание правила. В качестве примера рассмотрим путь 6, 4, 5, 3. Создание правила начинается с вывода (вершина 6) и дерево решения просматривается в обратную сторону. Просмотр данной ветви (пути) 113 заканчивается на вершине 3, которая является локальным выводом. Если бы вершины 3 не было в дереве решений, то путь закончился бы на вершине 1. Применив полученный путь, запишем правило в следующем виде: ЕСЛИ посетитель, возможно, будет принят на работу = да И средний балл за время учебы >=3,5 И посетитель имеет изобретения = да, ТО предложенная должность = научный сотрудник. Для каждой вершины логического вывода определяется путь и записывается правило. В рассматриваемом дереве решений имеется 6 вершин логического вывода (прямоугольников), в том числе и локальный вывод в вершине 3, значит будет составлено 6 правил. Длинную фразу ―посетитель, возможно, будет принят на работу ‖ можно заменить переменной, принимающей значения ―да‖ или ―нет‖. Список имен переменных, текст, который они заменяют, и номера вершин пути сводят в таблицу, (табл.1). Использование переменных вместо полного текста упрощает формирование и запись правил. Таблица 6.1 Таблица имѐн переменных Имя переменной Условия Вершина(ы) DEGREE Посетитель имеет ученое звание? 1 QUALIFY Посетитель, возможно, будет 3 114 принят на работу PATENT Посетитель имеет изобретения? 4 EXPERIENCE Стаж работы по специальности? 7 GRADE Средний балл за время учебы? 5 POSITION Предложенная должность 2,6,8,9,10 Используя имена переменных из табл.1, вышеприведенное правило можно запишется в следующем виде: ЕСЛИ QUALIFY = да И GRADE>=3,5 И PATENT = да, ТО POSITION = научный сотрудник В табл.2 приведены все правила для дерева решений, показанного на рис.6.1. Правила соответствуют всем шести путям, ведущим к шести возможным целям дерева решений. Правила желательно пронумеровать. Совокупность правил является формализованными знаниями (в рассматриваемом примере – знаниями руководителя) и представляет собой базу знаний. Таблица 2 База знаний № Правило Путь 10 ЕСЛИ DEGREE = НЕТ, ТО POSITION=ОТКАЗАТЬ 2, 1 20 ЕСЛИ DEGREE = ДА, ТО QUALIFY=ДА 3, 1 30 ЕСЛИQUALIFY = ДАИGRADE>=3,5ИPATENT = ДА, ТО POSITION = НАУЧНЫЙ СОТРУДНИК 6,4,5.3 115 40 ЕСЛИQUALIFY = ДАИGRADE>=3,5ИPATENT = НЕТ, ТО POSITION = ИНЖЕНЕР КОНСТРУКТОР 8,4,5,3 50 ЕСЛИ QUALIFY = ДАИ AVERAGE <= 3,5И EXPERIENCE <2, ТО POSITION=ОТКАЗАТЬ 9,7,5,3 60 ЕСЛИ QUALIFY = ДАИ AVERAGE <= 3,5ИEXPERIENCE>2, ТО POSITION = ИНЖЕНЕРПО ЭКСПЛУАТАЦИИ 10,7,5, 3 Таким образом, дерево решений позволяет просто и наглядно представить ход рассуждений эксперта при решении задачи и формировать правила для базы знаний, а без базы знаний экспертную систему не построить. Аналогично можно построить базу знаний для своей проблемной области или решаемой задаче. Структуры данных экспертной системы. При создании экспертной системы для упрощения ответа на вопросы и решения поставленной задачи в систему включается ряд полезных таблиц или структур данных. Структуры данных нужны для работы с базой знаний. После определения метода решения выбранного круга задач можно приступить к разработке системы. Список логических выводов - это структура данных, содержащая упорядоченный список возможных логических выводов. Список состоит из номера правила, логического вывода, связанного с этим правилом, и условий, которые формируют вывод. На каждое правило базы знаний в списке приходится одна запись. Создание записи списка поясним на примере правила 10. Часть ТО правила 10 содержит переменную 116 POSITION, т.е. переменная POSITION связана с логическим выводом правила 10. Список логических выводов используется исключительно для поиска вывода по номеру правила. Когда условия части ЕСЛИ истинны, вызывается часть ТО правила, ей присваивается значение. Например, если надо узнать, будет ли посетителю предложена работа, в списке ищется переменная POSITION. Она содержится в первой же записи, т.е. в правиле 10: ЕСЛИ DEGREE=НЕТ, ТО POSITION=НЕТ Посетитель не будет принят на работу, если переменная DEGREE имеет значение НЕТ. Если же переменная DEGREE имеет значение ДА, тогда обращаться к части ТО правила нельзя, поскольку не выполняется условие части ЕСЛИ (DEGREE=ДА). Поэтому надо продолжить поиск правила, содержащего в части ТО переменную POSITION (в данном случае правило 30). На рис.3.9 приведѐн полностью сформированный список логических выводов для всех правил базы знаний. 10 POSITION 20 QUALIFY 30 POSITION 40 POSITION 50 POSITION 60 POSITION Рис. 3.9. Список логических выводов. 117 Список считается сформированным, когда логический вывод каждого правила помещѐн в запись с номером, совпадающим с номером правила. Список переменных – это перечень имен переменных для всех условных частей правил базы знаний и признак их инициализации. Признак инициализации показывает, присвоено ли переменной значение. Независимо от того, в скольких условиях встречается переменная, в список переменных она включается всего один раз. В этот список также нельзя включать переменные из списка логических выводов, поскольку их значения определяются с помощью правил. Например, правило 20 использует переменную QUALIFY. Список переменных приведѐн в таблице3. Таблица3 Список имен переменных Имя Признак Значение DEGREE I НЕТ PATENT NI EXPEREIENCE NI GRADE NI Первоначально предполагается, что переменным значения еще не присвоены и признак инициализации для всех переменных равен NI. По мере того как полученная от посетителя информация передается системе и переменным присваиваются значения, признак инициализации меняется на I. С этого момента, в каком бы правиле в условной части 118 не встретилась переменная, она будет считаться проинициализированной, имеющей какое либо значение и ее можно использовать для работы с любыми правилами. Таким образом, до того, как правило включается в работу, все переменные, входящие в его условную часть, должны быть проинициализированы. Список переменных условия – это перечень всех переменных для всех условных частей всех правил базы знаний. Условная часть правила (ЕСЛИ) может содержать несколько переменных. Под каждое правило выделяется одинаковое число позиций в списке переменных условия. Минимальное число позиций равно числу переменных условия самого «длинного» правила. Можно добавить еще одну-две позиции «про запас» на случай доработки базы правил. На рис.3.10 показан список переменных условия для шести правил рассматриваемой базы знаний. Для простоты программирования предполагается, что каждое правило не может содержать больше четырех переменных условия (т.к. самое длинное правило, например №40, содержит три переменных условия). Четвертая позиция добавлена «про запас». 119 1 DEGREE 2 3 4 5 DEGREE 6 7 8 9 QUALIFY 10 GRADE 11 PATENT 12 13 QUALIFY 14 GRADE 15 PATENT 16 17 QUALIFY 18 GRADE 19 EXPERIENCE 20 21 QUALIFY 22 GRADE 23EXPERIENCE 24 Рис.3.10. Список переменных условия. Слева от имен переменных даны числа (1-24), указывающие индекс элемента массива (по четыре на правило), в который помещается имя соответствующей переменной. Незанятые элементы массива, отведенные правилу, остаются пустыми. В принципе можно запрограммировать любое число переменных для каждого правила. Однако при отведении места под переменные условия лучше для каждого правила резервировать одинаковое число элементов массива. Это упростит 120 вычисление индекса первого элемента, отведенного правилу в списке. Его можно вычислить с помощью простой формулы: № = 4* (номер правила/10 — 1)+1. Например, переменные правила 50 будут размещаться, начиная с 17-го элемента массива: 4* (50/10—1)+1=17. №=17. Теперь посмотрим, каким образом три описанные структуры данных соотносятся с мыслительной деятельностью человека в процессе обратной цепочки рассуждений. Прежде всего, человек просматривает все возможные пути, способные привести к решению задачи (список логических выводов). Затем он выделяет условия, составляющие эти пути (список переменных и список переменных условия). Такие структуры данных позволяют быстро обрабатывать информацию, не повторяя одни и те же шаги по нескольку раз, потому что значения переменных можно использовать в определенной ситуации для различных логических выводов. Если же при разговоре с человеком, устраивающимся на работу, у директора нет не только компьютера, но даже карандаша и бумаги, ему придется много раз переспрашивать, ведь сразу просто невозможно запомнить. Конечно, в конце концов, он примет решение, но затратит много сил и времени. |