Экспертные системы (стр. 6 )

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

В ряде приложений не удается все решаемые задачи свести к фик­сированному набору подзадач. План реше­ния задачи в таком случае должен иметь переменную структуру и не может быть сведен к фиксированному набору подзадач. Для решения подобных задач может быть использован метод нисходящего уточнения (top-down refinement). Для того чтобы упростить процесс решения некоторой задачи в сложном пространстве, целесообразно получить обобщенное пространство (пространство меньшей размерности) и попробовать получить решение в этом пространстве. Указанный при­ем можно повторять многократно. При этом полный процесс решения задачи можно представить как нисходящее движение в иерархии пространств от наиболее абстрактного к конкретному, в котором получа­ется окончательное решение. Существенной характеристикой такого процесса являются поиск решения задачи в абстрактном пространстве, преобразование этого решения в решение более низкого уровня и т. д. Причем на каждом уровне вырабатывается окончательное решение и только затем осуществляется переход на следующий, более конкретный уровень. Внутри каждого уровня подзадачи рассматриваются как независимые, что создает частичное упорядочение абстрактных состоянии. Формирование более абстрактного про­странства осуществляется путем игнорирования части описаний менее абстрактного пространства (на первом шаге — конкретного про­странства). Игнорирование описаний осуществляется на основе ран­жирования описаний по степени важности. Часто ранжирование осу­ществляется на основе учета степени неизменности фактов (наиболее абстрактны те описания, которые не могут изменяться). При этом абстрактные пространства, с одной стороны, должны для упрощения решения задачи обеспечивать значительное упрощение исходного пространства, а с другой стороны, должны быть подобны друг другу и конкретному пространству, чтобы процесс нисходящего переноса решения из более абстрактных пространств в менее абстрактные не требовал больших вычислительных затрат.

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

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

2. решения, принимаемые на верхних уровнях, нет необходимости отменять на более нижних.

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

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

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

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

1. определить, когда накопилось достаточно информации для при­нятия решения;

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

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

4. объединять информацию, полученную различными подзадачами.

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

При решении любой задачи многократно возникает вопрос: «Что делать на следующем шаге?» В простейшем случае решение предоп­ределено методом поиска решения. При поиске в абстрактных и кон­кретных пространствах на каждом шаге решался вопрос о том, какой из операторов, существующих в проблемной области, применить к текущему состоянию проблемной области. Вопрос о том, как ре­шающая программа это сделает, не обсуждался. Можно оказывать не явное, а косвенное влияние на определение того, «что делается на следующем шаге в проблемной области» путем выбора того или иного метода, известного решателю. Подобный подход требует явного разграничения знаний о процессе решения и знаний о проблемной области. Для этого необходимы знания на метауровне. Решатель в метапространстве содержит явное описание процесса организации поиска, то есть описание состояний, операторов, условий применимости операторов, описание доступных методов (стратегий) поиска и способов их взаимодействия. Получить решение в метапространстве – это значит определить, какой метод (программа) будет применен на следующем шаге, другими словами, составить метаплан решения задачи. Метаплан, в отличие от абстрактного плана, выражается не в терминах операто­ров проблемной области, а в терминах методов (программ), из­вестных решателю. Не существует причин ограничивать метазнания одним уровнем.

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

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

1. все утверждения, описывающие состояние, являются истинными;

2. применение оператора к некоторому состоянию формирует некоторое новое состояние, описание которого состоит только из ис­тинных фактов.

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

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

Любая формальная система является монотонной, то есть если А, В и С есть некоторые высказывания, такие, что если В выводится из А, то В будет выводиться и из А Ù С. Система немонотонна, если В выводится из А, но ØB выводится из А Ù С.

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

Мнение В можно представлять в виде отношения, состоящего из субъекта мнения а (индивида или системы, имеющих рассматриваемое мнение), объекта мнения р (то, о чем субъект имеет мнение) и обосно­вания мнения т (причины, по которым субъект имеет данное мнение), или в формальном виде — В(а, р, r) (а думает, что р, так как r).

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

Остановимся на особенностях механизма поиска в альтерна­тивных пространствах. В рассмотренных ранее методах поиск в неко­тором направлении прерывался при достижении целевого или терми­нального состояния. Если достигалось целевое состояние, то либо работа завершалась(при поиске одного решения), либо продолжался поиск следующего решения. При достижении терминального состоя­ния необходимо вернуться в некоторое предыдущее состояние про­странства и продолжить поиск в новом направлении. Обычно при реализации поиска использовался механизм бэктрекинга (backtracking). Бэктрекинг работает по принципу «Last In, Last Out» («последним вошел, первым вышел»), то есть сначала устраняется последнее рассматриваемое состояние, для реализации которого может быть применен механизм стека.

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

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

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

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

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

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

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

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

5. МЕТОДЫ ФОРМАЛИЗАЦИИ ЗНАНИЙ О ПРЕДМЕТНОЙ ОБЛАСТИ

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

Сущность — это объект произвольной приро­ды, принадлежащий реальному или виртуальному миру. На самом общем уровне сущности делятся на следующие ка­тегории (классы): предмет, свойство (атрибут), состояние, процесс, событие, оценка, модификатор, квантификатор, модальность. Лю­бое понятие относится к одной из этих категорий.

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

Под понятием (концептом) понимается класс сущностей, объ­единяемых на основе общности признанных (атрибутивных) структур.

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

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

Под простым понятием понимается тройка, со­стоящая из имени, интенсионала и экстенсионала понятия.

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

Сложные понятия — это понятия, образованные из ранее определенных понятий применением некоторых правил.

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

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

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

Совокупность существенных признаков, характеризующих поня­тие, называется его содержанием (интенсионалом). В силу ограни­ченного числа существенных признаков A1,...,Aj,...,Ak будем пред­ставлять содержание понятия А множеством A = {A1,...,Aj,...,Ak}. При этом содержание понятия должно отвечать взаимнопротивоположным требованиям полноты и неизбыточности. Совокупность существенных признаков можно рассматривать как координаты k-мерного признакового пространства. Оно должно отличаться от признакового пространства, характеризующего другое понятие. Если отойти от двух градаций 1-го признака — его наличия, либо отсутствия в анализируемом понятии — и определить меру схоже­сти, то можно решать задачу выявления аналогии понятий.

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

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

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

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

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

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

¾ имена способны замещать денотаты. Например, имя понятия
АВТОМОБИЛЬ может использоваться в качестве заместителя лю­бого конкретного автомобиля;

¾ имя нетождественно денотату, оно не может полностью заменить денотат. Так, при алгебраических преобразованиях мы можем использовать буквенные обозначения чисел. Однако если не­
обходимо вычислить числовое значение выражения, то требуется
подставить конкретные числа (денотаты) вместо букв;

¾ связь «имя — денотат» многозначна, т. е. некоторое имя может обозначать множество денотатов — омонимия, и наоборот, од­ному денотату можно поставить в соответствие несколько имен — синонимия.

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