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

Метод II - редукция.

При поиске методом редукции решение задачи сводится к решению образующих ее подзадач. Процесс повторяется для каждой следующей подзадачи до тех пор, пока не будет найдено очевидное решение для всей их совокупности. Процесс разбиения задач на подзадачи представляется в виде ориентированного графа j, который называется “и/или-граф”. Каждая вершина “и/или-графа” представляет собой задачу или подзадачу и может быть конъюнктивной (“и”-вершиной) или дизъюнктивной (“или”-вершиной). Конъюнктивные вершины вместе со своими дочерними вершинами интерпретируются следующим образом: решение задачи сводится к решению всех ее подзадач, соответствующих дочерним вершинам конъюнктивной вершины.

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

С целью сокращения времени поиска решений используются эвристические методы поиска.

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

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

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

К методам поиска, реализованным по требованию пользователя полный состав решений в рамках большого пространства состояний, относят поиск в факторизованном пространстве. Факторизованным пространством называют пространство, которое можно разбить на непересекающиеся подпространства частичными неполными решениями. Здесь используется метод “иерархическая генерация-проверка”. Генератор определяет текущее частичное решение, затем проверяется, может ли привести это решение к успеху. Если текущее решение отвергается, то из рассмотрения без генерации и проверки устраняются все решения данного класса.

И т.д. (очень много методов).

4.  Примеры использования ПМ.

MYCIN - система для диагностики и лечения инфекционных заболеваний.

Был разработан скелетный язык, иначе - оболочка ЭС. Декларативные знания системы MYCIN описываются в виде “объект-атрибут-значение” и каждой тройке приписывается коэффициент уверенности, определяющий степень надежности знаний. Процедурные знания описаны в виде классического правила продукции. Механизм логического вывода основан на обратной цепочке рассуждений. Поиск производится в иерархически упорядоченном пространстве состояний.

В системе EMYCIN (оболочка) усилена предметной области отношению к MYCIN функция редактирования БЗ, доведена до высокого уровня система объяснения хода решения задачи, а также аппарат обучения системы. Написан на ФОРТРАНе.

OPS-5. Универсальный язык инженерии знаний, предназначенный для разработки ЭС, используемых в коммерческих приложениях. Разработчик - университет Корнеги-Меллон. Декларативные знания в системе описаны в виде “объект-атрибут-значение”. Процедурные знания описаны в виде классических правил продукции. В механизме логического вывода используется стратегия прямой цепочки рассуждений, реализуется метод применения одного и того же правила в различных контекстах; для формирования конфликта набора и разрешения конфликта используются специальные методы {RETELEX}, которые позволяют добиться высокой эффективности за счет управляющей структуры, где предпочтение отдается правилам со ссылкой на самый последний сгенерированный элемент “объект-атрибут-значение”.

Методология построения ЭС.

1. Подход к проектированию ЭС.

2. Содержание этапов проектирования.

3. Практические аспекты разработки и внедрения ЭС.

1. Подход к проектированию ЭС.

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

В силу отмеченных особенностей при проектировании ЭС-м применяется концепция “быстрого прототипа”. Ее суть: разработчики не пытаются сразу построить законченный продукт. На начальном этапе создается прототип, к-рый должен удовлетворять двум условиям:

1) он должен решать типичные задачи предметной области;

2) с другой стороны трудоемкость его разработки должна быть очень незначительной.

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

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

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

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

2. Основные этапы разработки ЭС.

1. Идентификация.

2. Концептуализация.

3. Формализация.

4. Выполнение.

6. Тестирование.

a. Переформулирование

b. Переконструирование

c. Усовершенствование

d. Завершение

В состав функций этапа 1 входит:

1) определение команды проектировщиков, их роли, а также формы взаимоотоношений;

2) определение целей разработок и ресурсов;

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

Типичные ресурсы этого этапа: источники знаний, время разработки, вычислительные ресурсы, объем финансирования.

На этапе 2 эксперт и инжинер по знаниям формализуют ключевые понятия, отношения и характеристики, которые выявлены на предыдущем этапе. Данный этап призвн решить следующие вопросы:

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

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

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

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

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

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

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

По результатам 5-го этапа может понадобиться не только модификация программного обеспечения, но и идеологии разработки интерфейса.

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

*            неверно сформулированныые вопросы пользователя;

*            присутствие неопределенности в вопросах пользователя;

*            доступность для пользователя лексики системы;

*            доступность для пользователя объяснений, которые выдает система;

*            проиворечивость и неполнота правил;

*            согласование контекстов действия правил.

По результатам 6-го этапа осуществляется модификация системы. Наиболее простым её видом явл-ся усовершенствование прототипов. Этот вид затрагивает только этапы 4 и 6.

Более серьёзным видом модификации явл-ся переконструирование представлений. Этот вид модификации необходим в том случае, если обнаруживается, что желаемое поведение системы не достигнуто. Предполагается возврат на этап формализации и далее осуществляется весь цикл проектирования. Если проблемы функционирования системы еще более серьёзны, то приходится возвращаться на этапы 2 и 1 для переформулирования требований к системе и основных понятий.

Страницы: 1, 2, 3, 4, 5, 6