Функции доверия
В теории Демпстера—Шефера т — это функция присвоения базовых вероятностей (bра — basic probability assignment), которая определена на множестве 2O значений из интервала [0,1], такая, что
m(пустое множество) = 0
и
[(т(Аi) - 1];
суммирование выполняется по всем
Ai
2O. Суммарное доверие Bel для любого фокального элемента А может быть найдено суммированием значений т по всем подмножествам в А. Таким образом, Bel является функцией, определенной на множестве 2е значений из интервала [0,1], такой, что
Bel(A) =
B Am(B). Ве1(0) всегда равно 1, независимо от значения т(O). Это следует из определения функции присвоения базовых вероятностей. Соотношение Ве1(O) = 1 означает следующее: можно с полной уверенностью утверждать, что в пространстве 0 обязательно имеется корректная гипотеза, поскольку по определению набор гипотез является исчерпывающим. Значение m(O) отображает вес свидетельства, еще не учтенного в подмножествах, входящих в пространство 0. Значения Bel и т будут равны для множеств, состоящих из единственного элемента.
Оценка вероятности фокального элемента А будет ограничена снизу оценкой доверия к А, а сверху — оценкой привлекательности А, которая равна 1 - Веl(Aс)> где Aс — дополнение к A.
Оценка привлекательности A, Рls(A), представляет степень совместимости свидетельства с гипотезами в А и может быть вычислена по формуле
Рls(A)=
A^B не равно пустому множеству m(B). Поскольку определенная таким образом оценка привлекательности А есть не что иное, как мера нашего недоверия к -A, то можно записать:
Рls (A) = 1 - Вel (-A).
Значение оценки привлекательности А можно рассматривать как предел, до которого можно улучшить гипотезы из А при наличии свидетельств в пользу гипотез-конкурентов. Удобно рассматривать информацию, содержащуюся в оценке Bel для данного подмножества, в виде доверительного интервала в форме [Вel(A), Pls(A)]. Ширина интервала может служить оценкой неуверенности в справедливости гипотез из А при имеющемся наборе свидетельств.
Правила Демпстера позволяют вычислить новое значение функции доверия по двум ее значениям, базирующимся на разных наблюдениях. Обозначим Bel1 и Веl2 два значения функции доверия, которым соответствуют два значения функции присвоения базовых вероятностей т1 и тг. Правило позволяет вычислить новое значение т1+т2, а затем и новое значение функции доверия Веl1+ Веl2, основываясь на определениях, приведенных выше.
Для гипотезы А значение т1+т2(А) есть сумма всех произведений в форме т1(Х) m2(Y), где X и Y распространяются на все подмножества в в, пересечением которых является А. Если в таблице пересечений будет обнаружен пустой элемент, выполняется нормализация. В процедуре нормализации значение k определяется как сумма всех ненулевых значений, присвоенных в множестве 0, затем т1+т2(0) присваивается значение нуль, а значения m1+m2 для всех других множеств гипотез делится на (1 - k).
Таким образом,
m1+m2= X^Y=A[m1(X)m2(Y)]/[1- X^Y=пустое множество{m1(X)m2(Y)}]
Следует учитывать, что значения т1 и m2 сформированы по независимым источникам свидетельств в пределах того же пространства гипотез. Обратите внимание и на тот факт, что вследствие коммутативности операции умножения правило Демпстера дает один и тот же результат при любом порядке объединения свидетельств.
МетодикПерла
Альтернативой теории Демпстера—Шефера является методика Перла [Pearl, 1986], в которой свидетельства учитываются на основе Байесовского подхода к группированию и распространению влияния свидетельств на достоверность гипотез. Как и в методике, предложенной Гордоном (Gordon) и Шортлиффом (Shortliffe), предполагается, что в пространстве гипотез выделено некоторое подмножество гипотез, представляющих интерес в определенном семантическом контексте, причем это подмножество имеет иерархическую структуру.
Предполагается также, что еще до получения свидетельств с каждой отдельной гипотезой связано определенное значение степени доверия к ее правдоподобности. Перл не уточняет, каким именно способом формируются эти исходные значения, но скорее всего это должен сделать эксперт в предметной области при формулировке гипотез.
От эксперта также требуется выделить множество гипотез S, на которые непосредственно распространяется определенное множество свидетельств Е. Если свидетельства из Е непосредственно влияют на гипотезы из S, то должен существовать какой-то причинный механизм, связывающий каждый член множества S со свидетельствами, причем он является уникальным для каждого из них. Однако сами по себе свидетельства в множестве Е не несут никакой информации, которая позволила бы нам отдать предпочтение одному из членов S перед другими.
Это отображение множеств друг на друга позволяет ввести понятие условной независимости между свидетельствами и отдельными гипотезами hi:
Р(Е | S, hi) = Р(Е | S, h1), для всех hi
S. С помощью отношения вероятностей можно количественно оценить степень, с которой свидетельства подтверждают или опровергают множество гипотез S:
лS=[P(E|S)] / [P(E|-S)].
Влияние свидетельств Е на множество S вычисляется следующим образом. Каждая отдельная гипотеза hi, принадлежащая множеству S, получает вес Wi = лS , в то время как каждая гипотеза из дополняющего множества SC получает вес Wi = 1. Все это выполняется на фазе распределения весов.
Затем, когда наступает фаза обновления, вычисляется новое значение функции доверия ВЕL'(hi) по ее прежнему значению ВЕL(hi):
Применение теории Демпстера—Шеферк системе MYCIN
Гордон (Gordon) и Шортлифф (Shortliffe) предложили использовать теорию Демпстера—Шефера в качестве альтернативы операциям с коэффициентами уверенности, применяемым в системе MYCIN. Они обратили внимание на то, что при определении организмов система MYCIN часто сужает множество рассматриваемых гипотез до определенного подмножества, включая в него, например, только грамотрицательные микроорганизмы. (Это пример того, что Кленси (Clancey) назвал применением структурных знаний.) Правила, которые порождают такое сужение пространства гипотез, ничего не говорят об относительном правдоподобии отобранных гипотез.
При использовании Байесовского подхода можно было бы предположить, что отобранные гипотезы об искомых микроорганизмах имеют равные априорные вероятности, и, следовательно, равномерно распределить между этими гипотезами веса свидетельств. Но это может привести к тому, что система не будет способна отличить случаи, когда имеются равные свидетельства в пользу каждой гипотезы, от случаев, когда такие свидетельства отсутствуют вовсе. Функция присвоения базовых вероятностей в теории Демпстера—Шефера не делает различия между априорными и апостериорными вероятностями, а потому и не приводит к такому распределению вероятностей.
Функции доверия в теории Демпстера—Шефера позволяют также избежать и другого следствия применения Байесовского подхода, противоречащего нашей интуиции. При использовании Байесовского подхода субъективная интерпретация вероятностей означает, что, доверяя в определенной степени гипотезе Я, мы тем самым изменяем степень доверия к остальным гипотезам, т.е.
Р(H) = 1 - Р(-H).
Однако одна из слабостей модели подтверждения, которая в MYCIN использует коэффициенты уверенности, состоит в том, что свидетельство, частично подтверждающее определенную гипотезу, не может рассматриваться одновременно и как свидетельство, эту гипотезу опровергающее. В теории Демпстера—Шефера изменение степени доверия к подмножеству гипотез А не принуждает к изменению степени доверия к остальным гипотезам, поскольку Веl(A) + Веl(Aс)=< 1.
Остаток после суммирования степеней доверия А и к Ас — это степень игнорирования гипотезы А.
Гордон и Шортлифф показали также, как можно применить теорию Демпстера— Шефера в MYCIN для вывода суждений о гипотезах на основании поступивших свидетельств. Триада (объект-атрибут-значение), включенная в правую часть правил, представляет в каждом из них единственную гипотезу (т.е. множество гипотез, состоящее из единственного элемента), "ответственную" за данное значение определенного атрибута в определенном объекте. Следовательно, любое множество таких триад, имеющих те же самые объекты и те же самые атрибуты, например (ORGANISM-1 IDENTITY <значенае>), образует пространство гипотез в том смысле, как это трактуется в теории Демпстера— Шефера. Если параметр имеет единственное значение, условие взаимной исключительности гипотез не нарушается. Набор значений в правилах также должен быть исчерпывающим.
Таким образом, правила в системе должны быть построены как своего рода описания функций доверия в теории Демпстера—Шефера. Если посылка в правиле подтверждает заключение о гипотезе H со степенью d и d имеет значение, превышающее определенный порог активизации правила, то значение коэффициента уверенности, связанного с этой гипотезой H, можно рассматривать как функцию присвоения базовых вероятностей, которая присваивает значение d множеству {H}, состоящему из одной гипотезы, а значение 1 - d— пространству 6. Если же посылка опровергает гипотезу со степенью уверенности d, то мы присваиваем значение d множеству {H}c, значение 1 -d— пространству O, а значение коэффициента уверенности, связанного с этой гипотезой Я, будет равно -d.
Авторы выделили три варианта комбинирования свидетельств в результате выполнения правил при использовании модели Демпстера—Шефера.
(1)Оба правила либо подтверждают, либо опровергают одно и то же заключение {H}, причем правила характеризуются базовыми вероятностями т1 и т2. В этом случае некоторый вес свидетельства будет распределен между {H} и O.
Обновленные значения доверия для этих двух множеств будут иметь вид т1+т2({Н}) и т1+т2(O). При этом нет необходимости применять k-нормализацию, поскольку {H} ^ O не равно 0. Оказывается, что в этом случае теория Демпстера—Шефера дает тот же результат, что и метод обработки коэффициентов уверенности.
(2) Одно правило подтверждает гипотезу {H} со степенью т1, а другое правило ее опровергает со степенью т2, т.е. подтверждает {H}с. В этом случае необходима нормализация, поскольку {H}^{H}с = 0. Иначе значения вероятностей будут комбинироваться, как и ранее:m1+m2({H}), т1+т2({Н}с) и т1+т2(O).
В этом случае результаты отличаются от полученных при использовании коэффициентов уверенности. Если применить правило Демпстера, то оказывается, что такое противоречивое свидетельство приводит к снижению поддержки и гипотезы {H}, и ее оппонентов {H}с, а растет доверие к 0. (В результате появления противоречивого свидетельства для каждого из множеств гипотез увеличивается оценка привлекательности Pls, поскольку поддержка оппонента снижается. Этот результат не согласуется с нашим интуитивным представлением о привлекательности, но следует отметить, что в теории Демстера—Шефера этот термин имеет несколько отличный от обыденного смысл.) Применение тех функций комбинирования коэффициентов уверенности, которые используются с MYCIN, скажется только на той гипотезе, которая характеризуется большим значением коэффициента уверенности.
(3) Правила выносят заключения, касающиеся двух конкурирующих гипотез {H1} и {H2}, т.е. двух множеств, каждое из которых содержит только по одному элементу. Если {H1} ^ {H2} =0, то потребуется нормализация и нужно будет вычислить значения оценок m1+m2({H1}), ml+m2({H2}) и т1+т2(O).
Правило Демпстера и в этом случае оказывается более общим, чем функции комбинирования коэффициентов уверенности в MYCIN. Это проявляется в том, что если между {H1} и {H2} существует отношение подмножества, то доверие к подмножеству будет расцениваться как доверие к супермножеству, но не наоборот.
Таким образом, при использовании модели Демпстера—Шефера появление нового свидетельства оказывает большее влияние, чем при использовании прежней модели, основанной на коэффициентах уверенности.
Гордон и Шортлифф предложили приближенные методы вычислений, позволяющие снизить объем вычислительных операций по сравнению с оригинальной теорией Демпстера—Шефера. Они также обратили внимание на то, что разделение пространства поиска, подобное выполненному в системе INTERNIST, поможет выделить достаточно малое множество конкурирующих гипотез, образующих текущую область анализа. Однако в таких системах, как INTERNIST, при формировании множества конкурирующих гипотез невозможно выполнить прямое отображение вида Г:U —> 2O между отдельными свидетельствами и множествами гипотез, полагая, что симптомы могут быть причастны к разделению множеств гипотез на уровни иерархии.
За последние десять лет популярность теории Демпстера—Шефера неуклонно растет. Она находит применение в различных областях, например при решении задач диагностирования [Biswas and Anand, 1987] и машинного зрения [Provan, 1990]. Хотя эта теория и не позволяет решить проблему условной зависимости, о которой шла речь в главе 9, она предоставляет инженеру по знаниям определенную гибкость в том, что можно назначать степень доверия к подмножествам в пространстве гипотез, состоящим более чем из одного элемента. Такое назначение может служить средством кодирования зависимостей между группами свидетельств. Иерархическая организация областей распознавания способствует упрощению этой технологии обработки.
Рекомендуемая литература
В своей книге [Pearl, 1988] Перл уделяет основное внимание методам, основанным на Байесовском подходе, демонстрируя их возможности на множестве примеров, взятых из различных областей искусственного интеллекта. Эту книгу можно рекомендовать в качестве отправной точки для детального изучения проблемы обработки неопределенности в задачах искусственного интеллекта, поскольку изложенный в ней материал является самодостаточным. Структура книги позволяет читателям с разным уровнем подготовки выбирать нужный для себя материал. Более поздняя работа [Pearl, 1997] содержит описание последних исследований в этой области, включая и теорию сетей доверия. Среди других книг на эту тему я бы выделил [Jensen, 1996] и [Shafer and Pearl, 1990].
в котором основное внимание сосредоточено
В работах Горвица (Horvitz) и Гекермана (Heckerman) продемонстрирован типичный теоретический подход к проблеме неопределенности, в котором основное внимание сосредоточено на сравнении семантик различных формальных языков вычисления оценки степени доверия. Однако нужно иметь в виду, что классическая теория вероятностей также допускает неоднозначное семантическое толкование. Например, в работе [Shafer and Tversky, 1985] отмечаются три способа интерпретации формализма Байеса:
семантика частотности — мы задаемся вопросом, как часто при наличии данного свидетельства гипотеза оказывается истинной;
семантика пари — мы определяем, каковы шансы на успех при заключении пари в пользу истинности определенной гипотезы в свете имеющихся свидетельств;
семантика склонности — мы изучаем причинно-следственную модель и пытаемся ответить на вопрос, насколько хорошо данная гипотеза объясняет наблюдаемую ситуацию.
Частотная интерпретация меры доверия используется в экспертных системах чрезвычайно редко. Например, в работе [Buchanan and Shortliffe, 1984, Chapter 11] авторы предпочитают рассматривать оценку доверия как степень подтверждаемости гипотезы, что очень близко к семантике пари. Эта же интерпретация имеет совершенно очевидную связь с оценкой степени риска, используемой в эвристических правилах MYCIN. Модель, используемая в системе INTERNIST, ближе к интерпретации склонности, поскольку в ней значительное внимание уделено возможности формирования пояснений и анализу причинно-следственных связей между свидетельствами и гипотезами.
Таким образом, ясно просматривается тенденция к повышению уровня обоснованности как в теоретических работах, так и в практическом воплощении соответствующих методов в реальных системах.
Сети доверия
21.1. Теория Демпстера—Шефера
21.2. Методика Перла
21.3. Сравнение методов неточных рассуждений
21.4. Резюме
Рекомендуемая литература
Упражнения
В этой главе мы рассмотрим два количественных метода реализации логических рассуждений при наличии неопределенности в структурированном пространстве гипотез, базирующихся на теории свидетельств Демпстера—Шефера [Gordon and Shortliffe, 1985] и Байесовском формализме [Pearl, 1986]. Каждый из этих подходов предполагает, что на множестве гипотез каким-то способом определена функция доверия (belieffunction), а затем по мере накопления новых свидетельств применяется специфический механизм обновления текущего множества допущений.
Оба подхода будут описаны достаточно подробно, а затем будет проведено их сравнение. Будет показано, что оба метода имеют под собой более убедительное математическое обоснование, чем метод, базирующийся на эмпирических коэффициентах неопределенности, о котором шла речь в главе 9. Их можно рассматривать как альтернативу эвристическим методам обработки неопределенности, использованным в системах INTERNIST и CENTAUR, описанным в главе 13.
Сравнение методов неточных рассуждений
В работе [Horvitz et al, 1986] предлагается обобщенная модель, которая может служить в качестве оболочки для сравнения альтернативных формализмов оценок доверия к гипотезам. Описанная модель появилась в ходе обширной дискуссии, призванной пролить свет на проблемы неточных рассуждений, которые проявились в процессе эксплуатации системы MYCIN. Авторы этой работы, основываясь на работах Кокса [Сох, 1946], выделили набор свойств, которыми должны обладать параметры, предлагаемые в качестве меры доверия. Идея состояла в том, чтобы обеспечить некоторый единый теоретико-вероятностный базис для сравнения альтернативных формализмов.
Предлагаемые Горвицем свойства перечислены ниже.
(Р1) Ясность. Высказывания должны быть сформулированы настолько четко, чтобы всегда можно было выполнить проверку истинности условий в них.
(Р2) Скалярная непрерывность. Степень доверия к высказыванию должна выражаться действительным числом, значение которого может непрерывно изменяться в диапазоне от полного доверия к истинности до полного отрицания истинности.
(РЗ) Полнота. Должна быть обеспечена возможность приписать значение степени доверия любому правильно сформулированному высказыванию.
(Р4) Зависимость от контекста. Степень доверия к одному высказыванию может зависеть от степени доверия к другим высказываниям.
(Р5) Гипотетическая условность. Должна существовать функция, которая позволяла бы вычислить оценку доверия к совокупности высказываний по степени доверия к одному из высказываний и оценкам доверия к другим высказываниям в предположении, что первое истинно.
(Р6) Комплементарность. Оценка доверия к отрицанию высказывания должна быть монотонно убывающей функцией от оценки доверия к самому высказыванию.
(Р7) Совместимость. Высказывания с одинаковыми значениями истинности должны иметь одинаковые оценки доверия.
Можно показать, что аксиомы теории вероятности являются логическим следствием из этих аксиом, т.е. существует непрерывная монотонная функция Ф, такая, что
(А2) Ф(TRUЕ|е)=1;
(А4) Ф(QR |e)=Ф(Q|e)Ф(R | е).
Семантические свойства оценки доверия (Р1)-(Р7) могут служить базисом для сравнения таких формализмов, которые сложно сравнивать по их аксиоматике. Этот же перечень свойств может помочь исследователям выделить такие области, в которых применение теории вероятностей в качестве базиса для оценки степени доверия не подходит. И наконец, этот перечень может помочь определить ситуации, в которых различные формализмы действительно вступают в противоречие с аксиомами теории вероятностей.
Для классификации подходов к оценке степени доверия, не основанных на теории вероятностей, Горвиц использует четыре категории:
(С1) обобщение — определенные свойства ослабляются или исчезают вовсе;
(С2) специализация — определенные свойства усиливаются или добавляются новые;
(СЗ) внутренняя несовместимость — (С2) приводит к тому, что набор свойств становится несовместимым;
(С4) подстановка — изменения свойств нельзя отнести к категориям (С1) или (С2).
Для демонстрации практического использования предлагаемой модели Горвиц сравнивает формализмы нечеткой логики (см., например, [Zadeh, 1981]), теории Демпстера — Шефера [Shafer, 1976] и коэффициентов уверенности в системе MYCIN с теорией вероятностей.
Для нечетких логик характерно ослабление свойства (Р1), поскольку в них предполагается назначение оценки доверия расплывчатым высказываниям. Формализм нечеткой логики может быть отнесен к категории (С 1 ). Расплывчатость представления об истинности в нечетких логиках несовместима со свойством гипотетической условности (Р5). Формализм нечеткой логики оценивает доверие к совокупности высказываний по минимальному значению оценки для компонентов, что противоречит аксиоме (А4). В результате Горвиц относит эти формализмы к категории (С4).
Наиболее существенным отличием теории Демпстера—Шефера от классической теории вероятностей Горвиц считает ослабление свойства полноты (РЗ). Эта теория позволяет утверждать, что определенные априорные и условные вероятности не могут быть оценены, и в ней вводится понятие отношения совместимости между допущениями.Это приводит к нарушению свойств скалярной непрерывности комплементарноети (Р6). В результате Горвиц относит эту теорию к категории обобщения теории вероятностей (С1).
В использованной в MYCIN модели на основе коэффициентов уверенности применяются более строгие предположения, чем в вероятностной модели оценки доверия, а потому ее следовало бы отнести к категории (С1). Но мы уже отмечали, что для этой модели характерна внутренняя несовместимость, и Горвиц относит ее к категории (СЗ). Предложенная в [Heckerman, 1986] новая формулировка коэффициентов уверенности в терминах отношения вероятностей является, однако, весьма удачной специализацией.
Теория Демпстера—Шефера
В теории Демпстера—Шефера (Dempster—Shafer) предполагается, что гипотезы — компоненты пространства гипотез 6 — являются взаимно исключающими, а набор гипотез — исчерпывающим. В терминологии авторов пространство гипотез 0 называется областью анализа (frame of discernment). Также предполагается, что мы располагаем средством получения свидетельств не только в пользу отдельных гипотез h1.....hn, принадлежащих 6, но и в пользу подмножеств гипотез A1 ..., Ak, которые могут перекрываться.
Можно рассматривать эти свидетельства как элементы множества U и построить отображение
Г:U -> 2O,
которое будет связывать каждый элемент в U с подмножеством пространства в. Такое подмножество называется фокальным элементом. Отметим, что предположение об исчерпывающей полноте набора гипотез означает, что ни один из элементов u
U не отображается на пустое множество. Другими словами, для любого свидетельства существует хотя бы одна гипотеза, достоверность которой подтверждает это свидетельство.Теория Демпстера—Шефера предлагает средства вычисления функции доверия на таких множествах гипотез и правила объединения функций доверия, сформулированных на основании разных свидетельств.
приведена схема простого пространства
1. На рис. 21. 1 приведена схема простого пространства гипотез для задачи поиска неисправности в автомобиле. Корневой узел, неисправность автомобиля, представляет множество неисправностей {неисправность системы подачи топлива, неисправность электрооборудования}. Узел неисправность системы подачи топлива представляет множество {неисправность карбюратора, неисправность бензопровода}, а узел неисправность электрооборудования — множество {неисправность аккумуляторной батареи, неисправность распределителя}. Таким образом, узел неисправность автомобиля можно рассматривать как представляющий всю область анализа.
Э = {неисправность системы подачи топлива, неисправность электрооборудования, неисправность карбюратора, неисправность бензопровода}.
Рис. 21.1. Пространство гипотез о неисправностях в автомобиле
I) Предположим, что степень подтверждения диагноза неисправность карбюратора имеющимися свидетельствами оценивается значением 0.8. Вычислите т(неисправность бензопровода), т(неисправность электрооборудования) и m(0).
II) Предположим, что степень опровержения диагноза неисправность системы подачи топлива имеющимися свидетельствами оценивается значением 0.6. Вычислите т{неисправность электрооборудования).
Ill) Предположим, что степень подтверждения диагноза неисправность карбюратора имеющимися свидетельствами оценивается значением 0.2, а диагноза неисправность бензопровода— значением 0.5. Вычислите т(неисправность системы подачи топлива). .
2. Используя пространство гипотез, представленное на рис. 21.1, предположим, что степень подтверждения диагноза неисправность системы подачи топлива имеющимися свидетельствами оценивается значением 0.3, а диагноза неисправность аккумуляторной батареи — значением 0.6. Вычислите значения т для всех узлов графа, используя правило Демпстера.
3. Пусть на пространстве гипотез, представленном на рис. 21.1, априорные вероятности отдельных гипотез равны:
Равноправность карбюратора) = 0.4;
Р(неисправность бензопровода) = 0.1;
Р(неисправность аккумуляторной батарей) = 0.3.
Предположим, что имеется свидетельство е, такое, что
Р(е| неисправность карбюратора) = 0.3;
Р(е| —неисправность карбюратора) = 0.5;
Р(е| неисправность бензопровода) = 0.2;
Р(е| —(Неисправность бензопровода) = 0.4;
Р(е| неисправность аккумуляторной батареи) = 0.6;
Р(е| —(Неисправность аккумуляторной батареи) - 0.3;
Р(е| неисправность распределителя) = 0.7;
Р(е| —(неисправность распределителя) = 0.1.
Вычислите новые значения оценок доверия к каждой из гипотез, используя метод Перла.
Базпрецедентов
Приведенная выше аналогия с библиотекой удобна, но является далеко не полной. Прецеденты — это не книги; хотя их и связывают с книгами некоторые общие абстрактные свойства, имеются и существенные отличия.
Прецеденты напоминают книги (конечно же, не из разряда беллетристики) тем, что содержат определенную специфическую информацию, "вставленную" в некоторый контекст. Содержимое прецедента — это знание, а контекст описывает некоторое состояние внешнего мира, в котором это знание применяется. Однако прецедент содержит знание в такой форме, которая может быть воспринята программой. Другими словами, знания, содержащиеся в описании прецедента, "готовы к употреблению" в том же смысле, в каком порождающие правила готовы к применению.
Прецедент должен представлять решение проблемы в определенном контексте и описывать то состояние мира, которое получится, если будет принято предлагаемое в нем решение. Это свойство часто можно встретить и в содержимом книг, но, опять же, разница состоит в том, что информация не представлена в форме, удобной для восприятия программой.
Хотя описания прецедентов и варьируются по размеру, они все-таки значительно уступают книгам в этом смысле. Информация в описаниях прецедентов значительно более сжата и представляется на каком-либо формальном языке.
Если прецедент — это модуль знаний, который может быть считан программой, то в чем его отличие от других способов представления знаний, множество которых мы уже рассмотрели в этой книге? Самый короткий ответ на этот вопрос — прецедент, как правило, реализуется в виде фрейма (см. главу 6), в котором структурированы информация о проблеме, решение и контекст. Так же, как фрейм или порождающее правило, описание прецедента может быть сопоставлено с данными или описанием цели. Но для извлечения описания прецедента из базы таких описаний используется совсем другой механизм, чем для извлечения фрейма или порождающего правила. Первое, что делается в процессе применения прецедента, — его адаптируют к текущей ситуации. Поэтому поиск описания прецедента требует использования достаточно сложного механизма индексирования.
Формирование отчетов в системе FRANK
Работая над каким-либо отчетом, авторы могут преследовать совершенно различные цели. В одних случаях составляется беспристрастный обзор состояния дел, в других материал отчета должен подвести читателя к определенному выводу (желательному для автора), в третьих — обосновать определенное решение, принятое ранее. От того, с какой целью составляется отчет, зависит и подбор информации в нем, и стратегия ее освещения. Например, готовя обзор состояния исследований в определенной области для научного журнала, автор старается охватить как можно больший материал, в то время как адвокат в своем отчете ограничивается только теми прецедентами, которые интересуют его клиента.
Система FRANK [Rissland et al., 1993] относится к классу систем с доской объявлений, в которой объединены парадигмы вывода суждений на основе правил и прецедентов и которая предназначена для формирования отчетов по медицинской диагностике. (Название FRANK — искаженная аббревиатура от Flexible Report and Analysis System.) Основной упор при разработке системы был сделан на взаимодействие между целями высокого уровня, которые ставит перед собой автор отчета, и информационными подцелями, такими как извлечение подходящих прецедентов.
В состав системы FRANK входят три главных компонента (рис. 22.3).
Модуль планирования обеспечивает управление функционированием системы. Он выбирает заготовку плана из библиотеки планов, а затем выполняет иерархическое планирование, конкретизируя выбранную заготовку.
Модуль формирования суждений на основе прецедентов и модуль продукционной системы (в действительности эту функцию выполняет модуль OPS5) выполняют логический вывод в предметной области, опираясь на соответствующие базы знаний.
Модуль формирования отчета для пользователя имеет в своем распоряжении разнообразные стратегии, которые базируются на знаниях из области риторики.
Знания, которыми располагает система FRANK, разделены между тремя иерархическими структурами.
В иерархии отчетов отчеты классифицированы соответственно целям их создания.
Например, является ли отчет суммирующим или аргументирующим, отстаивающим определенную позицию или нейтральным и т.д.
В иерархии стратегий решения проблем представлены знания о том, как собирать информацию для отчета определенного типа, например как отыскать подходящие данные или как поступать с данными, поддерживающими противоположное заключение.
Из иерархии стратегий презентации система черпает знания о том, как скомпоновать выводы в отчете. Например, стоит ли сначала располагать веские аргументы или лучше начать с анализа достоинств и недостатков альтернативных вариантов.
Рис. 22.3. Архитектура системы FRANK
Поток управления в системе можно описать в терминах последовательности шагов обращения к источниками знаний, которые манипулируют данными на доске объявлений (см. об этом в главе 18). Вместо того чтобы по очереди описывать каждый источник знаний, мы представим основные этапы обработки, в результате которых формируется и выполняется план построения отчета. Исходные данные имеют формат перечня тем (например, нужно ли, чтобы определенная медицинская процедура была подтверждена случаями из практики), а выход системы — это отчет, в котором темы изложены в соответствии с заявленными предпочтениями.
Начальный источник знаний формирует скелет отчета, в котором зарезервированы разделы для определенных фрагментов информации.
Затем формируются стратегии для отдельных разделов, для чего привлекаются другие источники знаний. Стратегии извлекают планы разделов из библиотеки планов.
Специальный источник знаний конкретизирует каждый план и выполняет его, активизируя соответствующую цель. После формирования цепочки "цель—подцель" удовлетворяются цели нижних уровней. Как правило, такие подцели заполняют слоты шаблона отчета.
Другие источники знаний проверяют совместимость разделов отчета. Если противоречия не обнаруживаются, выходной документ формируется в соответствии со стратегией презентации. В противном случае корректируется план.
Таким образом, сначала система на основании введенной пользователем информации выбирает тип отчета.
Например, пользователь может запросить у системы отчет с предложением, который должен обосновать определенный диагноз. В этом случае система FRANK выберет отчет типа Diagnosis-with-Alternatives (диагнозы и варианты) и воспользуется стратегией уравнивающее сравнение (equitable comparison), которая назначается для этого типа отчета по умолчанию.
Комбинируя тип отчета и стратегию, система строит определенный план, в котором, в частности, есть место и для информации о прецедентах, подходящих для текущего диагноза. Наиболее подходящий прецедент выбирается по совпадению большинства симптомов с анализируемым случаем, но возможны и другие стратегии.
Например, более аргументированная стратегия может потребовать, чтобы прецедент считался подходящим, если:
он совпадает по большинству симптомов с текущим случаем; Ф имеет совпадающий диагноз;
не содержит никаких свойств, подобных прецедентам, имеющим другой диагноз.
А что произойдет, если не будет найден прецедент, отвечающий перечисленным требованиям? Тогда требования ослабляются (например, убирается последнее из перечисленных), и поиск повторяется.
Формирование запросов к базе прецедентов выполняется под присмотром источника знаний, который играет роль механизма планирования задач. Такие запросы могут быть частичными, т.е. определенные атрибуты запроса заполняются значениями по умолчанию. Этот же модуль обеспечивает различные варианты поведения системы, если поиск не даст результата. В частности, могут быть изменены ограничения на значения параметров в запросе, после чего поиск возобновляется.
Система FRANK поддерживает две методологии формирования суждений на основе прецедентов:
стиль поиска ближайшего соседа, как в системе CHEF;
группирование прецедентов по степени "похожести" в соответствии с определенным набором факторов верхнего уровня, как в системе САТО.
Выбор той или иной методологии зависит от контекста отчета. Например, атрибуты низкого уровня (вроде возраста и пола пациента) могут быть менее важными, чем факторы высокого уровня, используемые для классификации медицинских процедур.Но возможен и такой вариант, когда к определенной проблеме никак не удается применить факторы верхнего уровня и остается полагаться только на атрибуты нижнего уровня.
Такая гибкость в выборе методологии позволяет уравновесить влияние целей высокого уровня и результатов низкого уровня.
Методы извлечения и адаптации прецедентов
В системах формирования суждений на основе прецедентов используются разные схемы извлечения прецедентов и их адаптации к новым проблемам.
В таких программах, как CHEF, сопоставляются описания имеющихся прецедентов и полученная спецификация цели, причем в качестве основного средства сопоставления выступает семантическая сеть (см. главу 6). В примере, рассмотренном в предыдущем разделе, модулям извлечения и модификации известно, что и брокколи, и зеленый горошек — это свежие овощи. Модуль извлечения использует эту информацию для вычисления оценки степени близости прецедента и целевой спецификации, а модуль модификации использует эту же информацию для подстановки в рецепт одного ингредиента вместо другого. Это фоновое знание играет весьма существенную роль в решении обеих задач.
Сложность поиска решения и выявления различий между прецедентами в значительной степени зависит от используемых термов индексации. По сути, прецеденты в базе прецедентов конкурируют, пытаясь "привлечь" к себе внимание модуля извлечения, точно так же, как порождающие правила конкурируют за доступ к интерпретатору. В обоих случаях необходимо использовать какую-то стратегию разрешения конфликтов. С этой точки зрения прецеденты должны обладать какими-то свойствами, которые, с одной стороны, связывают прецедент с определенными классами проблем, а с другой — позволяют отличить определенный прецедент от его "конкурентов". Например, в программе CHEF прецеденты индексируются по таким атрибутам, как основной ингредиент блюда, гарнир, способ приготовления и т.п., которые специфицируются в заказе.
Механизм сопоставления должен быть достаточно эффективным, поскольку исчерпывающий поиск можно применять только при работе с базами прецедентов сравнительно небольшого объема. Одним из популярных методов эффективного индексирования является использование разделяемой сети свойств (shared feature network). При этом прецеденты, у которых какие-либо свойства совпадают, включаются в один кластер, в результате чего формируется таксономия типов прецедентов.
При качественном сопоставлении свойств достаточно будет использовать двоичные оценки или вычислять расстояние в абстрактной иерархии. Так, в абстрактной иерархии ингредиентов кулинарных рецептов "брокколи" ближе к "горошку", чем к "цыплятам", и вычисленное значение должно отражать этот неоспоримый факт. Количественное сопоставление будет включать и шкалирование.
Для адаптации найденного прецедента к текущим целевым данным программы также используют разные методы. В большинстве случаев можно обойтись заменой некоторых компонентов в имеющемся решении или изменением порядка операций в плане. Но существуют и другие подходы, которые перечислены ниже.
Повторная конкретизация переменных в существующем прецеденте и присвоение им новых значений. Например, сопоставление переменной овощи со значением брокколи вместо прежнего значения горошек.
Уточнение параметров. Некоторые прецеденты могут содержать числовые значения, например время выполнения какого-либо этапа плана. Это значение должно быть уточнено в соответствии с новым значением другого свойства. Например, если в рецепте требуется заменить один ингредиент другим, то, вероятно, придется соответственно изменить и время его обработки.
Поиск в памяти. Иногда требуется найти способ преодоления затруднения, возникшего как побочный эффект замены одних компонентов решения другими. Примером может послужить уже упоминавшийся выше эффект нежелательного изменения свойств брокколи при обжаривании вместе с кусочками баранины. Такой способ можно отыскать в той же базе прецедентов или в специальной базе знаний.
Большинство из перечисленных методов жестко связано со способом представления иерархии абстракций, который используется в конкретной программе. Это может быть система фреймов или семантическая сеть, и в каждом из этих вариантов подстановка одних концептов вместо других должна быть организована по-своему.
В следующем разделе мы рассмотрим систему, в которой используется довольно специфический способ представления знаний для моделирования предметной области.Для организации базы прецедентов в этой системе используется не разделяемая сеть свойств, а факторы более высокого уровня абстракции, связанные со спецификой предметной области. Такое представление требует применения более сложного механизма индексирования прецедентов и их поиска, чем тот, который использовался в модуле извлечения программы CHEF.
Обучение с помощью компьютера: системСАТО
В главах 11 и 12 мы уже говорили о том, что при работе над экспертными системами второго поколения исследователи пришли к выводу, что представление знаний внутри экспертной системы должно со временем привести к созданию систем обучения с помощью компьютера (CAI — computer-aided instruction). Если в нашем распоряжении имеется программа, которая успешно решает определенный круг проблем, то она, вероятно, может быть использована и для того, чтобы научить студентов решать аналогичные проблемы.
Однако оказалось, что превратить экспертную систему в эффективное средство обучения далеко не так легко, как это кажется с первого взгляда. Программа должна отдавать себе отчет в том, как именно она решает проблему и почему на данном этапе процесса отдает предпочтение именно таким знаниям. Исследователи пришли к выводу, что в процессе обучения особую важность имеет набор стратегий решения проблем и что эти стратегии должны быть представлены в программе в явном виде, а не просто реализованы в программном коде.
В этом разделе мы опишем программу САТО, которая была создана для обучения студентов-юристов методике ведения судебных дел. В основу программы положена абстрактная модель процесса прения сторон. Программа является развитием системы HYPO, в которой используется описанная выше методика анализа прецедентов для юриспруденции. База прецедентов этой системы содержит множество отчетов о судебных делах; получив спецификацию нового дела, система отыскивает наиболее близкий прецедент и анализирует отличия между ним и полученными данными. Мы увидим, что методика сравнения и противопоставления (compare and contrast) является таким же мощным средством решения проблем, как и ранее рассмотренные методики предложение и применение и предположение и проверка.
Обучение с помощью системы САТО
При разработке системы САТО преследовалась цель предоставить в распоряжение студентов-юристов среду, в которой они могли бы научиться вести рассуждения в ходе разбора судебного дела и проверять гипотезы относительно применения статей закона [Ashley and Aleven, 1997], [Aleven and Ashley, 1997]. Как было сказано в предыдущем разделе, в процессе обсуждения дела в судебном заседании нужно уметь формулировать собственные аргументы и опровергать аргументы противной стороны. Важной частью судебных прений является также умение формулировать и проверять гипотезы о возможности применения тех или иных статей закона к рассматриваемым обстоятельствам дела.
Задача студента при работе в этой среде состоит в том, чтобы проанализировать обстоятельства дела с юридической точки зрения и сформулировать аргументы в пользу обеих сторон, т.е. как в пользу истца, так и в пользу ответчика. Эти аргументы должны включать список прецедентов, выбранных из базы прецедентов системы, которые каждая из сторон может использовать, отстаивая свою точку зрения. В той версии системы, которая существует в настоящее время, представлены юридические знания о соблюдении секретности при выполнении торговых сделок, т.е. законы, касающиеся контроля конфиденциальной коммерческой информации, которая не должна использоваться в нечестной конкурентной борьбе.
В типичном судебном деле о торговых секретах истец утверждает, что ответчик каким-то образом получил доступ к конфиденциальной информации и затем использовал ее для получения преимущества в конкурентной борьбе. Сторонами в процессе, как правило, но не всегда, являются компании, а конфиденциальная информация носит технический характер. Для всех дел такого рода характерны некоторые общие черты. Например, предпринимал ли истец меры для защиты информации от несанкционированного доступа, давал ли ответчик обязательство не использовать полученную информацию или воспрепятствовать доступу к ней со стороны третьих лиц.
Для анализа конкретного дела можно использовать специальный словарь, ассоциированный с этими темами.
База системы САТО содержит около 150 прецедентов, которые проанализированы в отношении ряда факторов. Ниже представлены примеры типичных факторов и их определения.
Преимущество в конкуренции. Получение ответчиком доступа к секретной информации истца дает ответчику преимущество в конкуренции.
Раскрытие секретов. Истец по собственной воле не предоставлял посторонним доступ к информации.
Подкуп служащих. Ответчик подкупил служащих истца, для того чтобы они нарушили обязательства, данные при приеме на работу.
Такие факторы используются для организации индексации прецедентов в базе. Факторы классифицированы в соответствии с тем, аргументы какой из сторон они поддерживают. Эта информация вместе со знанием, какая же из сторон в конце концов выиграла дело, позволяет выполнить довольно интересный анализ прецедентов.
Задав булеву комбинацию факторов по своему выбору, студент может извлечь из базы соответствующие прецеденты и выяснить, какая часть дел была выиграна каждой из сторон в указанных обстоятельствах.
Студент может выбрать из базы те прецеденты, в которых сочетание факторов аналогично рассматриваемому случаю, и проанализировать поведение сторон в ходе судебных прений.
База данных САТО содержит не полные отчеты о судебном разбирательстве, а "выжимки" из него, но поиск в базе осуществляется не по тексту протокола заседания, а по индексированным факторам, что упрощает общение студента со средой.
Информация о прецеденте, извлеченная из базы данных, содержит список факторов этого прецедента, указание, какие из факторов обнаружены и в текущем деле, а какие в нем отсутствуют, в пользу какой из сторон "сыграл" каждый из факторов. Использование более сложного механизма индексации позволяет моделировать и более интеллектуальные методы рассуждений.
Спор вокруг подобия и различия между рассматриваемым делом и прецедентами в значительной мере зависит от того, на каком уровне абстрагирования он ведется. Каждая из сторон выбирает определенную интерпретацию пунктов текущего дела в сравнении с прецедентами.
Аргументируя близость, адвокат должен выбрать такие факторы, которые подобны в рассматриваемом деле и прецеденте, и доказать, что именно они играют существенную роль на данном уровне абстракции, в то время как несовпадающие факторы можно игнорировать как несущественные. Если же цель состоит в том, чтобы отвергнуть прецедент, на который ссылается противоположная сторона, нужно доказать, что наиболее существенные факторы в рассматриваемом случае как раз отличаются от прецедента.
Такой способ рассуждения уже не может опираться на обычную семантическую сеть. В иерархии факторов, помимо маркирования каждого из факторов, в чью пользу, истца или ответчика, он "играет", в явном виде должны быть представлены отношения между ними. Лучше проиллюстрировать это соображение примером.
На рис. 22.2 показан фрагмент иерархии факторов в системе САТО. Верхний узел на представленном фрагменте, средства поддержания секретности, представляет фактор, посредством которого истец, ссылающийся на нарушение режима конфиденциальности, утверждает, что с его стороны были предприняты необходимые меры обеспечения секретности. (Утолщенная рамка вокруг этого узла указывает, что данный фактор "работает" в пользу истца.)
Рис. 22.2. Фрагмент иерархии факторов в системе САТО ([Ashley and Aleven, 1997])
Существуют субфакторы, которые поддерживают это утверждение. Например, факт, что были предприняты определенные меры обеспечения безопасности, которые должны были предотвратить утечку информации, очевидно, поддерживает в споре позицию стороны истца. (Связи таких субфакторов с родительским узлом помечены знаком "плюс", поскольку они поддерживают родительский узел в иерархии — "усиливают" завоеванную им позицию.) Существуют, однако, и субфакторы, которые "ослабляют" эффект утверждения, порождаемого родительским фактором. Например, если истец однажды подписал отказ от режима конфиденциальности или разрешил своему служащему ознакомить с этой информацией посторонних на каком-нибудь общедоступном форуме, например, на технической конференции.Такие факторы ослабляют позицию, завоеванную родительским фактором, и потому соответствующие связи маркируются знаком "минус".
Субфакторы, в свою очередь, могут иметь собственные субфакторы, которые также объединены с родительскими узлами положительными или отрицательными связями. В САТО используется несколько алгоритмов, с помощью которых выносится решение, на каком уровне абстракции в этой иерархии нужно сфокусировать аргументы, если желательно подчеркнуть подобие случаев или их различие. Подробное .описание этих алгоритмов выходит за рамки настоящей книги, но главная их особенность заключается в том, что они основаны на применении очень специфичной схемы индексирования, связанной с базой знаний о предметной области.
Предметная область программы САТО
Ежедневно в апелляционных судах США выносится около 500 судебных решений. Каждое из них представляет собой определенный прецедент в судебной практике (подборки таких отчетов распространяются через сеть World Wide Web или на компакт-дисках). Решение, принимаемое апелляционным судом, как правило, основывается на так называемом "прецедентном праве" и включает интерпретацию соответствующих статей существующего законодательства и набор прецедентов, в которых были приняты аналогичные решения. Для юриста одним из главных компонентов знания законодательства, касающегося дел определенного вида, например о банкротстве или об ответственности за выпуск продукции, является знакомство с ранее расследованными подобными делами.
Другая часть юридического знания — умение найти в законодательстве аргументы за или против определенных обстоятельств в конкретном деле. Поскольку квалифицированный юрист должен уметь выступать в обеих ипостасях— и как защитник, и как прокурор, — такие знания должны быть обобщены. Они непременно должны включать стратегию поведения обеих сторон в судебном процессе при определенных обстоятельствах. Эти обстоятельства включают по большей части мириады фактов, сопряженных с рассматриваемым делом, т.е. кто кому что сделал или что точно сказал и в каком контексте.
Хотя кажется невероятным, что компьютер может взять на себя роль советчика в юридических делах, юристы вполне могут воспользоваться им для поиска прецедентов, имеющих отношение к тому, что их интересует в настоящее время. Поиск и интерпретация таких прецедентов представляет собой отнюдь не тривиальную задачу, которую с полным правом можно отнести к классу интеллектуальных. Однако нас сейчас интересует не столько такая экспертная система, сколько структура программы, которая могла бы обучить будущего юриста.
ПрограммCHEF
Для демонстрации возможностей экспертной системы, базирующейся на прецедентах, рассмотрим систему CHEF, которая предназначалась для формирования кулинарных рецептов [Hammond, 1986]. Эта программа принимает информацию о целевых характеристиках блюда (тип, вкусовые качества, своеобразие) и формирует подходящий рецепт. Например, программа может получить следующий "заказ":
блюдо из баранины (beef);
включает брокколи (broccoli);
использует поджаривание (stir-fry);
блюдо должно получиться хрустящим (crisp).
Заказ оформляется в виде выражения на специальном формальном языке:
dish(beef), include(broccoli), method(stir-frv), texture(crisp)
Результатом работы программы должен быть рецепт— последовательность операций, позволяющая приготовить такое блюдо.
Получив заказ, программа просматривает свою базу прецедентов, отыскивает в ней рецепт приготовления аналогичного блюда и адаптирует его в соответствии с особенностями текущего заказа (проблемы). Например, если в базе уже имеется рецепт для баранины с зеленым горошком, его можно скопировать и вместо горошка вставить брокколи. Этим, правда, адаптация не исчерпывается, поскольку горошек варится, а не жарится, как указано в заказе. Раз блюдо будет жариться, значит, брокколи придется сначала измельчить (если бы нужно было варить, то качанчики брокколи можно было бросать в воду целиком), следовательно, первоначальный план придется дополнить еще одной операцией. Кроме того, если кусочки баранины и броколли жарить вместе, то броколли, вероятно, пропитается соком. Значит, в системе нужно иметь правило, которое определит этот факт и изменит первоначальный простой план, — предложит сначала обжарить брокколи, а затем вынуть их.
На рис. 22.1 представлена упрощенная схема той части программы CHEF, которая имеет отношение к манипуляциям с базой прецедентов.
Рис. 22.1. Архитектура программы CHEF
Модель извлечения отыскивает в базе прецедентов рецепты, наиболее близкие к текущему заказу. Очевидно, что этот модуль должен обладать способностью обращаться к базе прецедентов как к памяти, адресуемой по содержанию, оценивать степень соответствия между набором входных спецификаций и характеристиками выбранного прецедента и ранжировать отобранные прецеденты на основании этой оценки.
Модуль модификации затем копирует и переименовывает выбранный прецедент и пытается скорректировать его в соответствии с полученной целевой спецификацией. В приведенном выше примере подстановка "брокколи" вместо "зеленый горошек" и модификация плана выполняются именно этим модулем.
После выполнения всех необходимых коррекций новый рецепт записывается модулем сохранения в базу прецедентов.
В программе CHEF корректировка неудачного плана (рецепта) в действительности выполняется отдельным модулем, который имеет доступ к специальному словарю термов, описывающих отказы, и индексированному множеству стратегий восстановления. Имеется также и специальный "симулятор", который позволяет "проиграть" сформированный рецепт и выявить в нем подводные камни, не заметные на первый взгляд. По основные модули работы с прецедентами выполняют именно те функции, которые мы описали выше.
Расследования и рассуждения в юриспруденции
И расследования, и рассуждения в юриспруденции направляются аргументацией, а более точно — аргументами, выражающими противоположные интересы, с помощью которых стороны процесса пытаются склонить на свою строну судью или присяжных, убедить их в том, что именно предлагаемая интерпретация закона и фактов является корректной в данном случае. Забота сторон в процессе, т.е. юристов, выступающих от имени сторон, не столько установить истину (это — забота судьи и присяжных), сколько наилучшим образом представить в судебном процессе интересы клиента. Следовательно, в том, что происходит в судебном заседании, имеется некоторый аспект игрового соперничества — стороны делают определенные ходы в борьбе за преимущество.
Базовая предпосылка, сделанная разработчиками системы САТО, состоит в том, что эти ходы могут быть описаны в рамках какой-то системы и затем использованы для обучения. Для выполнения очередного хода в игре нужно выбрать прецеденты в базе знаний о прецедентах, причем выбор должен учитывать как информацию о текущем случае, так и возможные ходы оппонентов. Таким образом, поведение сторон можно рассматривать как планирование трехходовой комбинации в игре:
одна сторона с помощью своего набора прецедентов "продвигает" свою позицию в игре;
противоположная сторона выдвигает другой набор прецедентов для представления своих аргументов;
первая сторона наносит новый удар, выдвигая соображения, парирующие в определенной степени аргумент противной стороны.
Ходы и контрходы можно анализировать в терминах суждений, основанных на прецедентах. Эшли считает, что в основе такой модели аргументации лежит следующий процесс [Ashley, 1990].
(1) Сравнение текущего случая с прецедентом с прицелом на обоснование аналогичного результата.
(2) Определение отличия (противопоставление) между текущим случаем и прецедентом, чтобы найти аргумент против того же результата.
(3) Поиск контрпримера к (1), в котором аналогичный прецедент привел к другому результату.
(4) Формулировка гипотетических прецедентов, которые дали бы аргументы за и против определенной позиции.
(5) Комбинирование сравнений и противопоставлений в аргумент, который включает оценку конкурирующих аргументов.
Эта модель аргументации реализована в системе HIPO, в которой процесс формирования аргумента выполняется за шесть шагов.
(1) Анализ факторов, присущих текущему случаю.
(2) Извлечение прецедентов на основе этих факторов.
(3) Упорядочение извлеченных прецедентов по степени близости к текущему случаю.
(4) Выбор наиболее подходящих прецедентов как с точки зрения одной стороны, так и с точки зрения другой.
(5) Формирование аргументов для трехходовой комбинации по каждому из пунктов текущего дела.
(6) Проверка результатов на гипотетических случаях.
Выполнение шага (5) усложняется тем обстоятельством, что судебное дело может содержать более одного пункта. Например, дело о разводе может содержать множество пунктов, касающихся раздела имущества, обеспечения детей и т.д., по каждому из которых стороны должны представить свои аргументы.
Рассуждения, основанные нпрецедентах
22.1. База прецедентов
22.2. Обучение с помощью компьютера: система САТО
22.3. Формирование отчетов в системе FRANK
22.4. Сравнение систем, основанных на правилах и прецедентах
Рекомендуемая литература
Упражнения
В главе 2 мы отмечали, что в ранних программах искусственного интеллекта отчетливо прослеживалась тенденция использовать по возможности единообразные методы решения проблем. Логические рассуждения строились на основе небольшого количества предположений или аксиом, а множество правил, применяемых для формирования нового состояния проблемы, также было невелико. Такие классические области искусственного интеллекта, как игры и доказательство теорем, являются формальными системами, которые по самой своей сути годятся для подобной комбинации логического анализа и эвристического поиска. Хотя в подавляющем большинстве экспертных систем применяется большое количество правил, специфичных для определенной предметной области, и используются разнообразные методы решения проблем, способы поиска и организации логического вывода, по сути, не очень отличаются от тех, что использовались в ранних программах искусственного интеллекта.
Например, в процессе работы производящей системы представление состояния проблемы в рабочей памяти последовательно изменяется, все более приближаясь к состоянию, характеризующему искомое решение. Такой пошаговый процесс очень напоминает последовательность ходов, дозволенных правилами игры, а отличие заключается в основном в семантике используемых правил. Программа игры в шахматы, основанная на знаниях, должна опираться не только на правила выполнения ходов, но и на информацию о стратегии, типовых ситуациях на доске, способах распознавания стадий игры (дебют, миттельшпиль или эндшпиль) и т.д.
Существует, однако, множество рутинных задач, выполняемых человеком, которые не вписываются в эту парадигму. Трудно себе представить, что, решая задачу, куда пойти сегодня вечером (в какой ресторан или кинотеатр), человек сознательно или подсознательно выполняет логический анализ или эвристический поиск.
Если обратиться к менее тривиальным примерам, то также трудно поверить, будто судья, архитектор или ваш шеф, принимая решение, всегда прибегают к логическому анализу. Скорее всего, в большинстве случаев в основе наших действий в повседневных ситуациях лежит другой механизм рассуждений и принятия решения.
В отличие от большинства машин, человек почти всегда чем-то занят или озабочен, а потому при решении повседневных проблем уже на подсознательном уровне стремится сэкономить время и силы. И здесь на помощь всегда приходят память и прежний опыт — для человека проще распознать ситуацию и найти для нее аналог, чем заново формировать решение.
Но как все это можно реализовать в компьютерной модели рассуждений? Мы уже знаем, что воспоминания и приобретенный опыт не так просто свести к набору правил, но можно представить себе некоторую "библиотеку" ситуаций, встречавшихся в прошлом, которые имеют отношение к возникшей проблеме, например "репертуар" указаний шефа, или судебные решения, принятые в прошлом по аналогичным делам, или наброски архитектурных планов для сооружений аналогичного назначения и т.п. Естественно, что такая библиотека должна быть индексирована каким-то разумным способом, чтобы в массиве хранящихся описаний ситуаций можно было довольно быстро распознать аналогичную текущей. Кроме того, понадобится также и некоторый механизм, который позволит адаптировать ранее принятое решение к новой проблеме (текущей ситуации).
Описанный подход получил наименование рассуждение, основанное на прецедентах (case-based reasoning). Мы рассмотрим эту новую технологию на трех примерах, взятых из разных предметных областей, — кулинарии, юриспруденции и делопроизводства. После этого мы вновь вернемся к сравнению рассуждений, основанных на прецедентах, с более привычной технологией логического вывода в экспертных системах и покажем, что эти технологии не противоречат, а дополняют друг друга. В главе 23 этот тезис будет подкреплен примерами и дальнейшим анализом.
Рекомендуемая литература
Единственной книгой, в которой достаточно полно рассмотрена технология использования прецедентов в системах искусственного интеллекта, является [Kolodner, 1993]. В перечень кратких обзорных статей, которые можно рекомендовать для первого знакомства, я бы включил [Blade, 1991], [Harmon, 1992], [Kolodner, 1992] и [Watson and Marir, 1994]. Обзор инструментальных средств, предназначенных для работы с базами данных прецедентов, представлен в работе [Harmon and Hall, 1993].
Описания действующих систем, основанных на прецедентах, читатель найдет в работах [Acorn and Walden, 1992], [Allen, 1994], [Nguyen et al, 1993], [Hislop andPracht, 1994],-[Barren etal, 1993].
Сравнение систем, основанных нправилах и прецедентах
Существует достаточно сильная аналогия между системами, основанными на правилах и прецедентах. И те и другие необходимо каким-то образом индексировать, чтобы обеспечить эффективное извлечение. И те и другие выбираются в результате сопоставления, причем выбор и ранжирование производятся на основании фоновых знаний, хранящихся в каких-либо дополнительных структурах, например в виде фреймов (в MYCIN аналогичную роль выполняют таблицы знаний).
Однако нас больше интересуют различия между этими двумя классами систем. Они суммированы в работе [Kolodner, 1993].
Правила являются образцами — содержат переменные и не описывают непосредственно решение, а прецеденты являются константами.
Правило выбирается на основе точного сопоставления антецедента и данных в рабочей памяти. Прецедент выбирается на основе частичного сопоставления, причем учитываются еще и знания о сущности характеристик, по которым выполняется сопоставление.
Применение правил организовано в виде итерационного цикла — последовательности шагов, приводящих к решению. Прецедент можно рассматривать как приближенный вариант полного решения. Иногда, однако, появляется возможность итеративно проводить аналогию с разными прецедентами, которые "подходят" для различных частей проблемы.
Построение суждений на основе прецедентов поддерживает и другую стратегию решения проблем, которую мы назвали "извлечение и адаптация". Эта стратегия существенно отличается и от эвристической классификации, и от стратегии "предложение и проверка", как, впрочем, и от всех остальных, рассмотренных в главах 11-15. В новом подходе есть нечто очень близкое нам интуитивно, поскольку весьма напоминает наш повседневный опыт. Даже на первый взгляд ясно, как привлекательно вспомнить аналогичный случай, принесший успех в прошлом, и поступить так же. Редко кто из нас затрудняет себя "нудными рассуждениями", когда можно быстро извлечь готовое решение.
Нужно, однако, предостеречь тех, кто считает, будто использование прецедентов поможет нам избавиться от утомительной работы по извлечению знаний и построению обоснованного логического заключения.
Человеческая память подвержена сильному эмоциональному влиянию — нам свойственно помнить успехи и забывать о неудачах. Прошлые успехи всегда предстают в розовом свете, а потому во многих случаях нельзя рассматривать прецеденты как достаточно надежную основу для правильных выводов. Есть и еще одно существенное соображение, которое не позволяет нам безоговорочно довериться прецедентам, — масштабность. Можно говорить об анализе десятков прецедентов, но когда масштаб решаемой проблемы потребует сопоставления сотен и тысяч прецедентов, существующему механизму анализа задача окажется не по плечу.
Но, тем не менее, мы можем оптимистически смотреть на перспективы систем, использующих в ходе рассуждений прецеденты. Это, без сомнения, один из способов использовать прошлый опыт, и будет весьма интересно проследить, как исследователи и инженеры смогут воспользоваться потенциальными достоинствами этой технологии.
Что представляет собой библиотека прецедентов?
1. Что представляет собой библиотека прецедентов? В чем ее отличие от обычной книги?
2. В чем состоит основное отличие методики формирования суждений на основе прецедентов от логического вывода на основе правил?
3. Как соотносятся прецеденты и фреймы? Как можно применить концепцию фреймов по отношению к прецедентам?
4. Предположим, вы купили омара и желаете приготовить из него какое-нибудь блюдо для себя и гостей. Библиотека прецедентов о блюдах из омаров состоит из записей такого формата.
Свойство |
Вес |
Свойство Вес |
|||
Наименование |
0.0 |
Приправы |
0.7 |
||
Основной соус |
0.9 |
Алкоголь |
0.5 |
||
Число в графе Вес указывает относительную важность соответствующей характеристики в рецепте.
Например, блюдо "Омар в сметане" будет представлено в этой библиотеке следующей записью.
Свойство | Значение | ||
Наименование |
Омар в сметане |
||
Основной соус |
Сметана |
||
Основная приправа |
Паприка |
||
Алкоголь |
Шерри |
||
I) Каков будет результат выполнения алгоритма сопоставления с ближайшим соседом при обработке рецепта "Омар в сметане" и приведенного ниже рецепта "Омар о-Гратен"?
Свойство | Значение | ||
Наименование |
Омар о-Гратен |
||
Основной соус |
Сметана |
||
Основная приправа |
Паприка |
||
Алкоголь |
Коньяк |
||
II) К какому из рецептов будет ближе "Омар в сметане" — к "Омару о-Гратен" или к "Омару франко-американскому"?
Свойство | Значение | ||
Наименование |
Омар франко-американский |
||
Основной соус |
Пищевая глазурь |
||
Основная приправа |
Стручковый красный перец |
||
Алкоголь |
Шерри |
||
III) Подумайте над тем, как более разумно выполнить сопоставление рецептов при следующих условиях:
блюда могут включать не один вариант соуса, например, "Омар в сметане" в действительности подается не только со сметаной, но и с голландским соусом;
блюда могут содержать не один алкогольный компонент, например, "Омар о-Гратен" может содержать помимо коньяка еще и белое вино;
некоторые приправы, соусы или алкогольные добавки более близки к одним, чем к другим, например, паприка ближе к карри, чем к орегано, белый шерри можно заменить мадерой, но не коньяком.
Как эти соображения могут повлиять на сопоставления с ближайшим соседом?
5. Подумайте над тем, как можно учесть перечисленные ниже факторы при вынесении решения, можно или нельзя оправдать человека в соответствии со статьей 35 Закона о
наказаниях как применившего для самозащиты при нападении "насилие, повлекшее за собой смерть".
Такой приговор считается обоснованным, если:
насилие использовано в качестве чрезвычайной меры, чтобы избежать угрозы поражения, не спровоцированного обвиняемым;
обвиняемый не имел возможности отступить или каким-либо другим способом избежать применения силы;
обвиняемый имел основания полагать, что другое лицо подвергается угрозе похищения, изнасилования или ограбления.
Такой приговор не может быть вынесен в случае, если:
обвиняемый является инициатором происшествия;
физическая сила была применена в обстоятельствах, не предусмотренных законом, например на дуэли;
обвиняемый имел возможность убежать с места происшествия или каким-либо другим способом избежать нападения, но не воспользовался им.
Существуют еще и усложняющие дело факторы, например:
лицо не обязано убегать, если находится в собственном доме;
применение силы со смертельным исходом считается недопустимым, если угрозе подвергается только собственность обвиняемого;
ответное применение силы со смертельным исходом считается недопустимым, если оно неадекватно угрозе, возникшей со стороны нападавшего.
Постройте иерархию этих фактов, аналогичную приведенной на рис. 22.2.
Будущее гибридных систем
Итак, вы могли убедиться на представленном в этой главе материале, что гибридные системы потенциально являются довольно мощным инструментом решения сложных проблем, которые не под силу отдельным "чистым" подходам. На примере сравнения систем ODYSSEUS и EMYCIN вы могли убедиться в том, что в первой использована гораздо более сложная методология построения и настройки базы знаний, которая не идет ни в какое сравнение с методикой синтаксического контроля, примененной в EMYCIN. Предстоит еще очень много сделать в теории экспертных систем, прежде чем такие системы смогут эмулировать способность к постоянному совершенствованию, которой обладает человек-эксперт.
Аналогично, комбинирование парадигм использования правил и прецедентов позволяет повысить эффективность обработки исключений, не усложняя при этом набор правил.
В системе SCALIR продемонстрирована возможность комбинированного использования в рамках одной системы символического и субсимволического подходов, которые обычно рассматриваются многими специалистами как взаимно исключающие.
Следует надеяться, что в будущем мы станем свидетелями еще более значительного прогресса в этом направлении. Однако в теории искусственного интеллекта наблюдаются и тенденции движения в совершенно другом направлении, противоположном созданию гибридных систем. Имеет смысл здесь кратко упомянуть о них.
Программное обеспечение систем искусственного интеллекта в значительной мере привязано к определенным платформам и реализовано на языках, которые используются только в области искусственного интеллекта.
Методология разработки программного обеспечения систем искусственного интеллекта все еще отстает от современной практики создания программ, предполагающей использование объектно-ориентированного анализа и разработки, так же, как и технологии разработки распределенных многокомпонентных приложений.
Для программ систем искусственного интеллекта характерны все недостатки, присущие исследовательским продуктам, — отсутствие полноценной документации, низкая надежность, возможность использования только в организации, где она была создана.
Существует еще и психологический барьер, который трудно преодолеть современным исследователям, многие из которых стояли у истоков тех или иных подходов и не склонны переходить на сторону "конкурентов". Но этот барьер, скорее всего, будет преодолен новым поколением исследователей и разработчиков.
Гибридные системы
23.1. Методы обучения в системе ODYSSEUS
23.2. Системы ODYSSEUS и MINERVA
23.3. Использование прецедентов для обработки исключений
23.4. Гибридный символический подход и нейронные сети
23.5. Будущее гибридных систем
Рекомендуемая литература
Упражнения
Раньше уже неоднократно высказывалась идея, что экспертная система может содержать не одну форму представления знаний. Даже в таких ранних системах, как MYCIN (см. главу 3), информация, специфическая для предметной области, хранилась в разных формах — например, в виде порождающих правил и в виде таблиц медицинских параметров. Программы, аналогичные CENTAUR (см. главу 13), уже можно было считать гибридными в том смысле, что в них объединялись разные способы представления знаний, а затем эти знания использовались с разной целью — для решения проблемы и формирования пояснений.
Поздние исследовательские системы, такие как XPLAN (см. главу 16), имели более сложную архитектуру, в которой для разработки и обслуживания экспертных систем объединялись разнообразные программные инструменты и модели. Такие системы можно рассматривать как очередной шаг вперед по сравнению с простейшей оболочкой, поддерживающей единственную парадигму программирования. В системах на базе доски объявлений (см. главу 18), подобных HEARSAY и ВВ, объединялись разнообразные источники знаний, которые могли иметь совершенно отличную внутреннюю структуру.
Системы, которые мы рассмотрим в этой главе, ознаменовали дальнейшее продвижение по этому пути — в них объединяются традиционные программы решения проблем и компоненты самообучения и критического анализа. Система ODYSSEUS [Wilkins, 1990] способна обучаться тому, как уточнять базу знаний. Для этого используются две разные методики: одна основана на анализе прецедентов, а вторая — на анализе пояснений. Обе методики являются сравнительно новыми, и читатель сможет вкратце ознакомиться с ними в данной главе. Далее будет описана программа, в которой логический вывод на основе прецедентов используется для обработки исключений из правил, а основным инструментом решения проблем являются порождающие правила. Программа обладает потенциальными возможностями обучения новым правилам [Golding and Rosenbloom, 1991]. В конце главы будет рассмотрена система извлечения информации SCALIR [Rose, 1994], в которой множество обычных символических методов комбинируется с подходом, основанным на сетях подключений.
Хотя все перечисленные системы нельзя считать полноценными коммерческими продуктами — это скорее инструменты исследования новых методик и алгоритмов, — мы уделяем им внимание в данной книге, поскольку, по нашему мнению, за ними будущее.
Гибридный символический подход и нейронные сети
В этом разделе будет рассмотрена перспектива использования нейронных сетей в экспертных системах. Нейронные сети предполагают совершенно другую модель вычислительного процесса, принципиально отличную от той, которая традиционно используется в экспертных системах. В качестве примера будет рассмотрена система SCALIR (Symbolic and Connectionist Approach to Legal Information Retrieval) [Rose, 1994].
Эта система помогает пользователю отыскать правовые документы — описания прецедентов или статьи законов, — имеющие отношение к определенному делу. Поскольку юридическая практика охватывает все области жизни современного общества, использование традиционного подхода, основанного на обычных базах знаний, к поиску и извлечению правовой информации потребует представления в системе огромного объема знаний, в большинстве нетривиальных, представляющих такие сложные понятия, как права, разрешения, обязанности, соглашения и т.п. Проблема усугубляется использованием естественного языка при составлении запросов. Большинство поисковых систем, имеющих дело с запросами на естественном языке, которые используются для поиска в сети World Wide Web, основаны на статистическом подходе, а не на базах знаний.
В системе предпринята попытка решить эту проблему посредством сочетания статистического подхода к извлечению информации и подхода, основанного на базах знаний, в которых учитываются смысловые связи между документами.
Использование прецедентов для обработки исключений
23.3. Использование прецедентов для обработки исключений
В этом разделе мы рассмотрим способ совместного использования правил и прецедентов, отличный от того, какой применен в системе ODYSSEUS. Роль прецедентов при новом подходе состоит не в том, чтобы содействовать модификации правил, а в том, чтобы при обработке исключений служить дополнением тем знаниям, которые представлены в правилах. Таким образом, каждый из компонентов занимается тем, что у него лучше получается, — правила имеют дело с обобщениями предметной области, а прецеденты — с отдельными нетипичными случаями.
Как уже было не раз продемонстрировано в предыдущих главах (см., например, главы 10-15), построение набора правил для экспертной системы— задача далеко не тривиальная. Помимо сложностей, сопряженных с извлечением и представлением знаний, существует еще и проблема полноты охвата предметной области набором правил. В идеале база правил должна быть корректной, непротиворечивой (по крайней мере, в рамках принятой стратегии разрешения конфликтов) и полной. Но по мере того, как количество правил расширяется, а сами правила усложняются, достичь такого идеального состояния становится все труднее.
Особенно сложно учесть в правилах все возможные исключения. Такая попытка приводит к чрезвычайному усложнению правил. Утверждение, что не бывает правил без исключений, давно уже стало общим местом. Иногда эту проблему пытаются решить включением в набор множества "мелких" правил, которые должны активизироваться в таких исключительных ситуациях. Но это означает возлагать на правила несвойственную им функцию — обрабатывать не общий случай, а частный.
Голдинг и Розенблум предложили использовать в экспертных системах гибридную архитектуру, в которой при решении проблем методика использования порождающих правил сочетается с методикой использования прецедентов [Gaiding and Rosenbloom, 1996]. Идея состояла в том, что механизм обработки прецедентов должен использоваться для критического анализа результатов применения правил.
Это выполняется путем поиска прецедентов, аналогичных рассматриваемому случаю, если последний можно считать исключением из правила. Такой подход требует, чтобы база прецедентов была индексирована по применяемым правилам. Авторы предложили и соответствующую меру близости, которая позволяет оценить степень подобия текущего случая и прецедента (рис. 23.1).
Рис. 23.1. Архитектура гибридной системы, использующей правила и прецеденты
Основная идея системы очень проста и элегантна. Сначала для решения текущей проблемы применяются правила, в результате чего формируется некоторое решение. Затем просматривается библиотека прецедентов на предмет выявления в ней ранее ветречавшегося случая исключения из использованных правил. Алгоритм работы системы приведен ниже.
Цикл, ПОКА не будет получено решение
{
1 . Для выбора следующей операции использовать правила.
2. Поиск в библиотеке "неотразимых" прецедентов, которые предлагают противоположный вариант выбора операции.
3. Если прецедент найден, использовать предлагаемый в нем вариант операции. Иначе использовать тот вариант, который предлагается правилами.
}
Обратите внимание на то, что обращение к правилам и прецедентам выполняется в каждом цикле. (Если программа не сможет найти ни правила, которое можно было бы применить, ни прецедента, она останавливается.)
Для того чтобы предложенная идея стала работоспособной, прецеденты в библиотеке должны быть проиндексированы по правилам, которым они противоречат. Рассмотрим, например, правило страховки водителей транспортных средств:
"Мужчины не старше 25 лет платят страховой взнос по повышенному тарифу".
Такое правило должно быть связано в библиотеке с прецедентом, в котором упоминается 18-летний юноша, успешно прошедший тесты повышенной сложности и выплачивающий взнос по сниженному тарифу.
На основании каких соображений принимается решение, является ли прецедент "неотразимым" или нет? Предложенное Голдингом решение состоит в следующем.
Когда мы проводим аналогию между прецедентом и текущим случаем, мы тем самым формируем некое неявное правило, скрытое от посторонних глаз. Предположим, что в нашем примере речь идет о водителе-мужчине 20 лет, который имеет квалификацию повышенной категории, и мы обнаружили аналогичный прецедент, но в нем речь шла о 1 8-летнем водителе. Эта аналогия сформирует неявное правило в виде
"Мужчины не старше 25 лет, имеющие повышенную квалификационную категорию, платят страховой взнос по сниженному тарифу".
Предположим, что при оценке степени близости, которая необходима для извлечения и последующего анализа прецедентов, возраст водителей разделяется на диапазоны, скажем "до 25 лет", "от 25 до 65 лет" и "свыше 65 лет". Эта мера близости оценит рассматриваемый нами случай и прецедент как очень похожие, поскольку совпадают возрастная категория и пол.
Можно протестировать это правило и на остальных прецедентах в библиотеке и оценить, какой процент выявленных прецедентов оно накрывает. Любой прецедент с мужчиной-водителем повышенной квалификационной категории, чей возраст не превышает 25 лет и который выплачивает взнос по повышенному тарифу, будет считаться исключением и, следовательно, снижать рейтинг прецедента. Если же случаи достаточно похожи, а правило достаточно точное, то аналогия считается "неотразимой" и компонент обработки прецедентов "выигрывает". В противном случае выигрыш будет за применяемым правилом, и в окончательном решении будет использован вариант, следующий из правила.
Таким образом, "неотразимость" зависит от трех факторов:
степени близости случаев, которая должна превышать определенный порог;
точности неявного правила, сформулированного в результате выявленной аналогии; в качестве меры точности берется пропорция прецедентов, которые подтверждают применение этого правила;
4 достоверности оценки точности, которая определяется размером выборки, на которой эта оценка сформирована.
Авторы продемонстрировали возможности предложенной архитектуры на примере задачи определения произношения имен. Реализованная ими система, получившая название ANAPRON, содержит около 650 лингвистических правил и 5000 прецедентов. Результаты испытания системы показали, что она обладает более высокой производительностью, чем системы-аналоги, использующие либо только правила, либо только прецеденты.
Методы обучения в системе ODYSSEUS
Методы обучения, которые рассматривались в главе 20 (пространство версий и IDЗ), иногда называют методами, основанными на подобии (similarity-based). Реализация обучения на основе этих методов требует обработки больших объемов информации — позитивных и негативных примеров, — из которой извлекаются характерные свойства нового концепта.
Альтернативой таким методам являются методы, основанные на пояснениях (explanation-based), которые позволяют выполнить обобщение на осно.ве единственного обучающего экземпляра. Это становится возможным, поскольку в таких методах процессом обобщения "руководят" знания, специфические для конкретной предметной области. Обучение, основанное на пояснениях, является дедуктивным или аналитическим, а не эмпирическим или индуктивным [Bergadano and Gunetti, 1996]. Иными словами, при такой методике описание нового концепта формируется в результате анализа предъявленного экземпляра в свете имеющихся фоновых знаний.
Методика логического вывода на основе прецедентов, которой была посвящена глава 22, позволяет решить новую проблему, адаптируя ранее полученные решения аналогичных проблем. Эта же методика может быть использована и для обучения, поскольку если уж ранее сформированное решение адаптировано применительно к новой проблеме, его можно добавить в базу прецедентов для использования в будущем.
Ниже будут более подробно рассмотрены методика обучения на основе пояснений и возможность использования прецедентов для машинного обучения.
Термином обобщение на основе пояснений (EBG — explanation-based generalization) обозначается независимый от, предметной области метод использования знаний, специфических для предметной области, для контроля процесса обобщения по единственному обучающему экземпляру.
Использование метода EBG предполагает, что система располагает следующей информацией:
позитивным экземпляром обучающей выборки;
теорией предметной области;
определением концепта, который система должна "изучить".
Для формализации этих идей обычно используется язык логического программирования (см.
главу 8). В частности, концепт, как правило, представляется в форме предиката, который характеризует то подмножество пространства объектов, которое нас интересует. Например, предикат сuр(Х) может представлять понятие "cuphood" (чашкообразность), которое определено в стиле языка PROLOG как сосуд малого объема (small), обладающий свойствами open (открытый), stable (устойчивый). Напомним, что выражение
а :-b.
читается как "а истинно, если b истинно". Тогда:
cup(X) :- small(X), stable(X), open(X).
Знания о предметной области должны включать описания условий, выполнение которых необходимо для того, чтобы объект можно было считать "устойчивым" (stable), например указано, что объект должен иметь плоское дно, определение свойства "открытый" (open) — например, объект должен иметь вогнутую форму, причем центр кривизны должен быть расположен выше основания.
В качестве экземпляра обучающей выборки укажем объект с плоским дном вогнутой формы, диаметр которого не превышает нескольких дюймов. Экземпляр должен "сопровождаться" пояснением, что указанные свойства вполне достаточны для представления понятия "cuphood". Образец обычно описывается некоторым количеством фундаментальных литералов (ground literals), например:
color(red, obj). diameter(4, obj).
flat(bottom, obj). concave(top, obj).
Эти литералы представляют определенный объект obj красного цвета (red) с плоским дном (flat bottom), вогнутый, причем центр кривизны располагается сверху (concave top). Знания о предметной области, представленные ниже, позволяют распознать этот экземпляр как представляющий концепт сир:
small(X) :- diameter(Y, X), Y < 5.
stable(X) :- flat(bottom, X).
open(X) :- concave(top, X).
Обратите внимание — то, что объект obj является чашкой, логически следует из этого фрагмента знаний. Наше пояснение, почему obj является чашкой, фактически есть доказательство. Этим завершается фаза пояснений в EBG.
Далее начинается фаза обобщения— вырабатывается набор достаточных условий, которые существовали при пояснении.
Главное, что нужно при этом сделать, — определить самые слабые условия, которых достаточно, чтобы на основании имеющихся знаний прийти к заключению, что obj — это чашка. Полученное в результате обобщение концепта состоит в том, что чашкой является объект с плоским дном, вогнутый, с центром кривизны вверху и диаметром менее 5:
cup(X) :- flat (bottom, X), concaveftop, X), diameter(Y, X), Y < 5.
Обратите внимание на то, что это обобщение логически следует из исходного определения понятия "чашкообразности" и базовых знаний о том, что такое "малый объем", "устойчивость" и "открытость". В этом смысле новое обобщение уже было неявно представлено в ранее имевшихся знаниях. Анализ представленного образца позволил сделать это обобщение явным. Кроме того, использование сформированного заранее обобщенного определения "чашкообразности" позволило нам совершенно безболезненно проигнорировать несущественные характеристики, в данном случае — цвет.
Обучение на основе прецедентов (CBL — case-based learning) представляет собой подход к обучению, совершенно противоположный методу EBG. Как было показано в главе 22, извлечение информации при таком подходе базируется в основном на подобии аргументов, а не на их логическом анализе. Можно с полным правом утверждать, что процесс адаптации сформулированного ранее решения к новой проблеме не включает обобщения в смысле логического программирования. В качестве дополнительного средства, обеспечивающего использование знаний об отношениях между сущностями предметной области, можно использовать иерархию абстракций, в частности в форме семантической сети. Однако результатом будут не новые правила, включающие переменные, а скорее новые прецеденты, сформированные из старых подстановкой констант.
Рассуждения на основе прецедентов — это, по сути, рассуждения по аналогии, а не логический вывод. Если некто придет к заключению, что Джон, владелец Порше, — водитель, склонный к риску, поскольку имеется прецедент, что Джек, который ездит на Ферра-ри, тоже склонен к риску, то фактически по аналогии делается вывод— Джон похож на Джека, так как автомобиль Порше имеет много общего с Феррари.
Напрашивается заключение, что, когда строится такая аналогия, каждый прецедент неявно генерирует определенное правило. В нашем примере такое обобщенное правило состоит в том, что люди, которые ездят на спортивных автомобилях, склонны к риску. Но такое правило не является полным. Все ли водители спортивных машин склонны к риску, или только водители-мужчины, или молодежь? Программа, использующая методику рассуждений на основе прецедентов, не может ответить на такой вопрос. Она способна только отыскать прецедент, наиболее близкий к рассматриваемому случаю.
Между методами CBL и EBG есть и кое-что общее. Оба метода можно противопоставить индуктивным методам, рассмотренным в главе 20, поскольку ни тот ни другой не предполагает анализа большого количества данных. Мы уже показали, что методу EBG достаточно иметь один обучающий экземпляр, а метод CBL для формирования аналогии может обойтись одним подходящим прецедентом.
Но обучение — это нечто большее, чем просто накопление сведений. Система, основанная на анализе прецедентов, должна обладать способностью выявить неподходящие прецеденты, которые не позволяют получить удовлетворительное решение насущной проблемы. В противном случае она будет накапливать прецеденты с ошибочными решениями.
Программа CHEF, описанная в главе 22, способна выявить ситуацию, в которой она формирует неудачный рецепт, и предпринимает попытку исправить его. Чтобы сделать это, программа должна объяснить, почему она полагает рецепт неудачным. Для этого программе требуется воспользоваться определенными знаниями из предметной области, которые в таком случае должны иметь форму правил причинной связи.
Например, модули извлечения и модификации могут предложить замариновать креветок, а потом уже их чистить. Но в этом случае креветки станут слишком влажными, и в рецепте не удастся реализовать заданное в заказе свойство "очищенные креветки". Программа обнаружит это, когда попытается смоделировать процесс приготовления блюда по созданному рецепту.Тогда другой модуль системы, ответственный за восстановление, обратится к знаниям о типах ошибок в рецептах, отыщет подходящую стратегию исправления ситуации и повторит этап составления рецепта. В новом рецепте сначала нужно очистить креветки, а уже потом их мариновать.
Даже после того, как будет получено решение для нового случая, программа не сможет его правильно индексировать до тех пор, пока не поймет, почему это решение считается успешным. Если пользователь заказывает легкое, нежирное блюдо и если программа, манипулируя прежними рецептами, сформировала новый, то этот результат можно использовать в будущем только после того, как с ним будут ассоциированы признаки "легкий" и "нежирный".
Нейронные сети
В отношении систем искусственного интеллекта вообще и экспертных систем, в частности, иногда можно услышать следующие критические замечания.
Такие системы слишком "хрупкие" в том смысле, что, встретившись с ситуацией, не предусмотренной разработчиком, они либо формируют сообщения об ошибках, либо дают неправильные результаты. Другими словами, эти программы довольно просто можно "поставить в тупик".
Они не способны непрерывно самообучаться, как это делает человек в процессе решения возникающих проблем.
Еще в середине 1980-х годов многие исследователи рекомендовали использовать для преодоления этих (и других) недостатков нейронные сети.
В самом упрощенном виде нейронную сеть можно рассматривать как способ моделирования в технических системах принципов организации и механизмов функционирования головного мозга человека. Согласно современным представлениям, кора головного мозга человека представляет собой множество взаимосвязанных простейших ячеек — нейронов, количество которых оценивается числом порядка 1010. Технические системы, в которых предпринимается попытка воспроизвести, пусть и в ограниченных масштабах, подобную структуру (аппаратно или программно), получили наименование нейронные сети.
Нейрон головного мозга получает входные сигналы от множества других нейронов, причем сигналы имеют вид электрических импульсов. Входы нейрона делятся на две категории — возбуждающие и тормозящие. Сигнал, поступивший на возбуждающий вход, повышает возбудимость нейрона, которая при достижении определенного порога приводит к формированию импульса на выходе. Сигнал, поступающий на тормозящий вход, наоборот, снижает возбудимость нейрона. Каждый нейрон характеризуется внутренним состоянием и порогом возбудимости. Если сумма сигналов на возбуждающих и тормозящих входах нейрона превышает этот порог, нейрон формирует выходной сигнал, который поступает на входы связанных с ним других нейронов, т.е. происходит распространение возбуждения по нейронной сети.
Типичный нейрон может иметь до 10J связей с другими нейронами.
Было обнаружено, что время переключения отдельного нейрона головного мозга составляет порядка нескольких миллисекунд, т.е. процесс переключения идет достаточно медленно. Поэтому исследователи пришли к заключению, что высокую производительность обработки информации в мозге человека можно объяснить только параллельной работой множества относительно медленных нейронов и большим количеством взаимных связей между ними. Именно этим объясняется широкое распространение термина "массовый параллелизм" в литературе, касающейся нейронных сетей.
Подход, базирующийся на нейронных сетях, часто рассматривается как несимволический, или субсимволический (subsymbolic), поскольку основная информационная единица, подлежащая обработке, является не символом (как это определено в главе 4), а чем-то более примитивным. Например, символ в LISP-программе, скажем МУ LAPTOP, можно было бы представить схемой активности некоторого числа связанных нейронов в нейронной сети. Но, поскольку нейронные сети часто моделируются программно, сам нейрон представляется некоторой программной структурой, которая, в свою очередь, может быть реализована с использованием символов. Например, роль нейрона может исполнять объект данных, располагающий подходящими свойствами и методами и связанный указателями с другими объектами в сети. Таким образом, на концептуальном уровне в субсимволической системе, реализованной компьютерной программой, которая содержит символы, нет ничего парадоксального.
Независимо от способа реализации, нейронную сеть можно рассматривать как взвешенный ориентированный граф такого типа, который описан в главе 6. Узлы в этом графе соответствуют нейронам, а ребра — связям между нейронами. С каждой связью ассоциирован вес — рациональное число, — который отображает оценку возбуждающего или тормозящего сигнала, передаваемого по этой связи на вход нейрона-реципиента, когда нейрон-передатчик возбуждается.
Поскольку нейронная сеть носит явно выраженный динамический характер, время является одним из основных факторов ее функционирования.
При моделировании сети время изменяется дискретно, и состояние сети можно рассматривать как последовательность мгновенных снимков, причем каждое новое состояние зависит только от предыдущего цикла возбуждения нейронов.
Для выполнения обработки информации с помощью такой сети необходимо соблюдение определенных соглашений. Для того чтобы сеть стала активной, она должна получить некоторый входной сигнал. Поэтому некоторые узлы сети играют роль "сенсоров" и их активность зависит от внешних источников информации. Затем возбуждение передается от этих входных узлов к внутренним и таким образом распространяется по сети. Это обычно выполняется посредством установки высокого уровня активности входных узлов, которая поддерживается в течение нескольких циклов возбуждения, а затем уровень активности сбрасывается.
Часть узлов сети используется в качестве выходных, и их состояние активности считывается в конце процесса вычислений. Но часто интерес представляет и состояние всей сети после того, как вычисления закончатся, либо состояние узлов с высоким уровнем активности. В некоторых случаях интерес может представлять наблюдение за процессом установки сети в стабильное состояние, а в других — запись уровня активизации определенных узлов перед тем, как процесс распространения активности завершится.
На рис. 23.2 показан фрагмент нейронной сети, состоящий из четырех сенсорных узлов S1—S4, возбуждение от которых передается другим узлам сети. Один узел, R, является выходным. Если веса связей в сети неизвестны, то узел R будет возбужден тогда, когда будут возбуждены узлы S1 и S4 Но если будут возбуждены также узлы S2 и S3, это приведет к подавлению возбуждения R даже при возбужденных узлах 5) и S4. Будет ли узел R действительно возбужден при таком состоянии сигналов на входах сенсорных узлов, зависит от весов связей в сети.
Количество возможных конфигураций сети такого типа очень велико. Велико и количество способов вычисления состояния нейрона при заданной сумме состояний на его входах.
Эти детали теории нейронных сетей выходят за рамки данной книги. Далее мы будем следовать идеям Роуза (Rose) и рассмотрим относительно простую модель нейронной сети, в которой любой узел может быть связан с любым другим узлом и в которой выходом узла является его состояние активности (т.е. не делается различия между активностью нейрона и сигналом на его выходе).
Рис. 23.2. Фрагмент нейронной сети с возбуждающими и тормозящими связями
Для более строгой формулировки такой модели введем следующие обозначения:
wij — вес связи от узла j к узлу i,
neti = Zj wij— состояние в текущий момент времени входов узла l, связанного с другими узлами сети.
При любом определении нейронной сети необходимо принимать во внимание и фактор времени, поскольку состояние любого нейрона в некоторый момент времени зависит от его предыдущего состояния и от предыдущего состояния нейронов, связанных с его входами.
Определение
Сеть связности (connectionist network) может рассматриваться как взвешенный ориентированный граф, в котором для каждого узла i выполняются следующие требования:
(1) состояние активности узла в любой момент времени t является действительным числом (будем обозначать его как ai(t));
(2) вес связи, которая связывает узел i с любым другим узлом у сети, является действительным числом wij,
(3) активность узла в момент t+1 является функцией от
его активности в момент времени t, ai(t);
взвешенной суммы сигналов на входах в момент времени t, neti{f);
произвольного внешнего входного сигнала xi(t).
Простая функция вычисления состояния активности узла i, удовлетворяющая требованию (3) приведенного выше определения, имеет вид
ai(t+1) = Cуммаj [wijaj(t)+xl(t)]
Это, однако, не единственно возможный способ определения активности. Функции других видов включают добавление термов, соответствующих росту или спаду активности, или имеют вид нелинейных дифференциальных функций (см., например, [Hinton, 1989]). В данной книге они рассматриваться не будут.
При конструировании сети веса связей могут быть назначены априори или изменяться со временем.
В последнем случае изменение весов является одним из следствий активности сети. Веса можно рассматривать как отражение знаний, а процесс их настройки и уточнения — как процесс обучения системы. Поскольку веса существенно влияют на распространение активности по сети, от них во многом зависит и поведение сети, а следовательно, изменяя веса, можно изменять поведение сети в желаемом направлении.
Как отмечено выше, знания в сети связности представлены неявно, поскольку нельзя выделить один определенный структурный элемент сети, который представлял бы отдельное правило или сущность предметной области. Знание отражено именно во взвешенных связях между мириадами отдельных элементов сети. Таким образом, в данном случае мы имеем дело с распределенными знаниями, которые нельзя представить в виде простого перечисления числовых или символических элементов. По этой причине часто можно встретить утверждение, что в нейронных сетях выполняется субсимволическая обработка информации.
В сетях связности знания сохраняются не в декларативном виде, а потому они не могут быть доступны для интерпретации со стороны какого-либо внешнего процессора [Rumelhart and McClelland, 1986]. Доступ к знаниям и процесс логического вывода могут быть описаны только в терминах активности сети.
Конечно, ничто не препятствует конструктору сети ассоциировать отдельные ее узлы с определенными сущностями предметной области, как это сделал Роуз в системе SCALIR. Однако такое отражение понятий на узлы сети не противоречит ранее сделанному утверждению, что отношения между сущностями неявно представлены в виде связей между узлами и обычно не могут интерпретироваться в форме правил. Следовательно, хотя мы и частично приоткрыли завесу таинственности, скрывающую, что же стоит за узлами сети, сущность взвешенных связей между ними остается по-прежнему "субсимволической".
Даже в случае, если узлы представляют сущности предметной области, общая картина активности мириад узлов сети может скрывать понятия достаточно высокого уровня, объединяющие определенные аспекты сущностей, представленных узлами.Пусть, например, узлы представляют слова и пусть узлы "гонки", "машина", "водитель" возбуждены. Этим может быть представлено понятие "водитель гоночной машины" или, наоборот, факт вождения гоночной машины. В любом случае такое представление может расцениваться как субсимволическое, поскольку составляющие его узлы не могут быть оформлены в виде какой-нибудь синтаксической структуры, имеющей явно выраженный смысл. Точно так же нельзя выполнить и семантический анализ состояния мириад узлов с помощью какого-либо внешнего набора правил.
Оболочкэкспертной системы MINERVA
MINERVA— это оболочка экспертной системы, разработанная на базе EMYCIN и NEOMYCIN (см. главы 10-12). Система MINERVA обеспечивает ODYSSEUS базой знаний и методом решения проблем и разработана специально для поддержки метода обучения EBL. Одно из главных отличий системы MINERVA от EMYCIN состоит в том, что в ней представлены не только знания о предметной области, но и стратегические знания, отражающие способ мышления практикующего врача. Такие знания можно рассматривать как дальнейшее развитие метаправил систем MYCIN, EMYCIN и NEOMYCIN.
Главным компонентом этой системы является база медицинских знаний о диагностировании менингита и других неврологических заболеваний. MINERVA реализована на языке PROLOG, и знания о предметной области представлены в этой системе в виде фраз Хорна (см. главу 8), но правила по содержанию аналогичны тем, что использовались в MYCIN. Например, следующее выражение представляет тот факт, что фотофобия может быть связана с головной болью:
conclude(migraine-headache, yes)
:- finding(photophobia, yes).
Знания о состоянии проблемы записываются в виде выражений для фактов в процессе работы системы. Например, выражение
rule-applied(rulel63).
утверждает, что в процессе работы системы было активизировано правило 123 и что эта информация доступна программе в процессе дальнейшей работы. Другое простое выражение
differential(migraine-headache, tension-headache).
зафиксирует тот факт, что мигрень и повышенное давление — текущие гипотезы, выдвинутые программой.
Очевидно, что такая информация может быть представлена и зарегистрирована любым способом, например установкой флагов или переменных, но наиболее целесообразно использовать такое же представление, какое принято в базе знаний предметной области.
Несложное метаправило может быть представлено в следующем виде: goal(findout(Р)) :- not(concluded(P)), ask-user(P).
Это правило утверждает, что если текущая цель системы — найти значение параметра Р и если система не может прийти к заключению о значении этого параметра на основании имеющихся у нее знаний, то она должна запросить его у пользователя. Поскольку Р является переменной, то головная часть выражения goal (findout (Р)) сопоставляется с выражением цели системы, представленным в явном виде, например goal (f indout (temperature)). Подцели вроде not(concluded(P)) могут быть сопоставлены (успешно или нет) с системными данными, описывающими текущее состояние процесса вычислений, например concluded (temperature).
Такие стратегические знания используются для выработки суждения о текущем состоянии проблемы и принятия решения о том, располагает ли система в данном случае достаточными знаниями. Кроме того, наличие таких знаний упрощает программу обучения, которая может обращаться к структурам на метауровне экспертной системы.
Обучение в системе ODYSSEUS
Способ обучения, который используется в системе ODYSSEUS, существенно отличается от рассмотренных в главе 20. При разработке этой системы преследовалась цель наделить ее способностью расширять существующую неполную базу знаний, а не включать в базу знаний новые понятия на основании анализа обучающей выборки большого объема. Система обучается, "наблюдая" за тем, как эксперт решает задачу, примерно так, как прилежный ученик постигает таинства мастерства учителя, стоя у него за спиной.
Основной вид действий, которые выполняются экспертом в процессе решения проблемы диагностики, — определение значений разнообразных переменных, т.е. характеристик пациента, таких как температура и т.п. Программа, наблюдая за работой эксперта, расширяет свои знания, пытаясь понять, почему эксперту понадобился ответ на тот или иной вопрос.
Таким образом, концепция процесса обучения в системе ODYSSEUS очень близка к формулированию пояснений. Фактически в контексте работы этой системы смысл термина "пояснение" отличается как от общепринятого, так и от того, какой мы придавали ему в главе 16. В ODYSSEUS пояснение — это вид доказательства, которое несет информацию о том, почему эксперт задает определенный вопрос на конкретном этапе решения проблемы диагноза. Смысл определенного вопроса связан как с текущим состоянием проблемы, так и с той стратегией, которой пользуется эксперт. Поэтому, "уразумев", почему был задан вопрос, программа как бы постигает стратегию действий эксперта.
Если программа располагает исчерпывающими знаниями, она способна сформулировать вопрос (а точнее, высказывание, которое стоит за ним) как логическое следствие текущего состояния проблемы, стратегических знаний, заключенных в метаправилах, знаний о предметной области и одной из текущих целей.
Например, если задан вопрос askuser(temprature), то обратный просмотр приведет нас к ближайшей цели goal (f indout (temperature)).
Но эта цель, в свою очередь, сформирована целью более высокого уровня, например желанием применить определенное правило или произвести разделение гипотез.
Наличие в текущей ситуации такой цели высокого уровня объясняет, почему была сформирована цель более низкого уровня, а следовательно, почему был задан определенный вопрос. Эта обратная цепочка рассуждений от подцелей к целям выполняется обычными средствами языка PROLOG или даже MYCIN, но обратите внимание — эти рассуждения выполняются на метауровне, т.е. на уровне, который определяет, почему программа работает именно так, а не иначе. Применяемая в системе ODYSSEUS стратегия обучения "из-за спины" включает три основные фазы.
Определение изъяна в базе знаний. Такой изъян обнаруживает себя, когда не удается сформировать объяснения действиям эксперта, используя описанный выше метод обратного просмотра. Неудача такого рода служит сигналом, что пора приступить к обучению.
Формирование предложений для внесения изменения в базу знаний. Если не удалось сформировать доказательство (пояснение в терминологии ODYSSEUS), значит, можно предположить, что в знаниях о предметной области или о состоянии проблемы имеется какой-то изъян. Если это изъян в знаниях о предметной области, можно временно добавить в базу подходящую фразу и посмотреть, будет ли после этого сформировано доказательство. Если же изъян существует в знаниях о состоянии проблемы, программа должна поискать другое доказательство.
Внесение изменения в базу знаний. Метод, который используется в системе ODYSSEUS для внесения изменений в базу знаний, называется "процедурой подтверждения принятого решения". Если не вдаваться в детали, то при этом требуется, чтобы разработчик системы сформировал процедуру, которая будет обрабатывать новые правила, определив, например, на сколько сократится количество конкурирующих гипотез в результате применения правила.
Детали реализации перечисленных фаз выходят за рамки обсуждения в данной книге, но основные принципы довольно очевидны. В применяемой методике экземпляр обучающей выборки представляет собой отдельную пару атрибут—значение, но в процессе сеанса обучения может возникнуть множество таких пар, так как программа пытается объяснить, почему она придает значение каждому из этих экземпляров.
Если сформировать объяснение не удается, программа предпринимает попытку модифицировать базу знаний.
Для модификации правил или добавления новых правил в базу знаний программа ODYSSEUS использует также в примитивном виде и метод CBL. Программа располагает библиотекой прецедентов, каждый из которых содержит и соответствующий правильный диагноз. Эту библиотеку программа может использовать для тестирования. Если при тестировании окажется, что сформирован неверный диагноз, программа назначает использованным при этом правилам нечто вроде штрафов.
Предпосылки правил, которые привели к ошибочному заключению, "ослабляются", т.е. сужается зона их" применения. Если же применение правил подтвердило вынесенный ранее правильный диагноз, то соответствующие предпосылки "усиливаются". В этой процедуре есть много общего с тем методом, который используется в системе Meta-DENDRAL, описанной в главе 20. Конечно, этот метод модификации правил не гарантирует решения проблемы, но он может пригодиться для настройки новых правил.
Организация обучения в системе SCALIR
Поскольку веса С-связей могут регулироваться системой в процессе работы, она способна таким образом самообучаться в соответствии с информацией, вводимой пользователем. Ниже мы опишем, как это делается в системе SCALIR, опуская несущественные детали.
Предположим, что один из входов узла i связан с выходом узла j, причем связь имеет вес Wij. Если узел i представляет документ, имеющий отношение к термину, представленному узлом j, то в процессе обучения нам может потребоваться усилить эту связь. Если же пользователь посчитает, что документ имеет мало общего с этим термином, то потребуется ослабить эту связь. Главный вопрос, который нужно при этом решить, — в какой степени нужно менять значение веса. Одно из простых правил вычисления значения изменения веса Wij может быть выражено формулой
Wi = nfiaj,
где n| — константа скорости обучения (learning rate), a fi — коэффициент обратной связи от пользователя, который, например, может принимать значение +1 или—1.
Однако применение такого правила не настолько очевидно, как это может показаться с первого взгляда, по следующим причинам.
Определить значения уровня активности а, не так просто, поскольку активизированный при возникновении запроса входной узел может снизить свою активность после того, как запрос будет снят.
Соседи узлов, которые получают обратную связь, также должны, по-видимому, получать некоторую информацию обратной связи от пользователя, подтверждающую, что они представляют документы, имеющие отношение к запросу.
Узел i может находиться в конце сети распространения активности, а следовательно, информация от пользователя (обратная связь) должна распространяться по сети в обратном направлении.
Таким образом, получаемая от пользователя информация обратной связи должна распространяться по сети примерно так же, как активность. Максимальное значение обратной связи для каждого узла записывается и обновляется в процессе распространения, и эти значения в дальнейшем играют роль членов fi и аj в приведенном выше выражении. Далее полученные значения весов нормализуются таким образом, чтобы их сумма для каждого отдельного узла была равна 1.0.
Конечно, в реальной системе SCALIR процесс самообучения несколько сложнее, поскольку в ней существуют связи разных типов. Читателям, интересующимся деталями этого процесса, следует познакомиться с работой [Rose, 1994], Но идея комбинированного использования символических и субсимволических методов заслуживает дальнейшего углубленного изучения. В системе SCALIR продемонстрирован довольно прагматический компромисс между чисто статистическим подходом к извлечению информации и традиционным подходом для экспертных систем, требующим большого объема знаний о предметной области.
Рекомендуемая литература
В последнее время появилось множество программных продуктов, в которых комбинируются методики, основанные на применении правил и прецедентов. Примером может служить система CBR Express, разработанная фирмой Inference Corp., которая используется в качестве надстройки над системой ART-IM [Davles and May, 1995].
Разработки оболочек экспертных систем, в которых комбинируется применение правил логического вывода и обучения или нейронных сетей, находятся пока что в зачаточном состоянии. Попытки использовать нейронные сети в сочетании с традиционными экспертными системами описаны в работе [Кат et al, 1991]. В этой связи следует упомянуть и систему NeuroShell 2, разработанную фирмой Neuron Data, в которой порождающие правила используются для предварительной обработки информации, после чего она передается в нейронную сеть. Полученная на выходе нейронной сети информация также может быть обработана с помощью системы правил.
SCALIR — гибридная системдля извлечения правовой информации
Узлы в сетевой структуре системы SCALIR представляют прецеденты (дела, ранее рассмотренные судами), статьи правовых актов и важные (ключевые) слова, которые встречаются в подобных документах. Таким образом, структурно сеть разделена на три части (слоя), как показано на рис. 23.3. В этой сети слой прецедентов и слой законодательных актов разделены слоем узлов, представляющих ключевые слова (термины). Последние связаны с документами, в которых они встречаются.
Таким образом, в базовой структуре сети связь между узлами терминов и документов образует схему индексации с взвешенными связями. В результате массив терминов отображается как на массив прецедентов, так и на массив правовых актов.
Вместо того чтобы связывать каждый термин с каждым документом, в котором он встречается, в SCALIR вычисляется вес термина для каждого ключевого слова, связанного с документом, как функция от частоты упоминания этого термина в данном документе и частоты его упоминания во всем массиве документов. Интуитивно кажется, что термином, наиболее подходящим для индексации некоторого документа, будет такой, который часто появляется в этом документе, но редко во всех остальных. Полученное значение сравнивается с пороговым, в результате чего каждый документ индексируется примерно десятком ключевых слов. (Обращаю ваше внимание на тот факт, что на схеме сети системы SCALIR показаны двунаправленные связи. Фактически каждая из них представлена в системе парой однонаправленных связей, причем эти связи могут иметь разные веса. Таким образом, не только термин позволяет найти документ, но и по документу можно отыскать термин.)
Рис. 23.3. Сеть связности в системе SCAUR ([Rose, 1994])
При конструировании сети в SCALIR сначала были организованы узлы для всех отобранных терминов, а затем они связывались с узлами документов, причем связям назначались веса в зависимости от значимости того или иного термина в контексте данного документа.
Такой тип связей (в документации они названы С-связями) не является единственным в SCALIR.
Существуют и символические связи (S-связи), которые во многом напоминают связи в семантических сетях, поскольку маркированы и имеют постоянные веса. С помощью связей этого типа в сети представлены отношения между документами, например один документ цитирует другой, в одном судебном решении критикуется другое, один правовой акт ссылается на другой и т.д. Таким образом, S-связи представляют знания в явном виде.
В целом сеть сиетемы SCALIR содержит порядка 13 000 узлов терминов, около 4 000 узлов прецедентов и около 100 узлов законодательных актов. Между узлами терминов и прецедентов организовано приблизительно 75 000 связей, а между узлами терминов и законодательных актов — около 2 000 связей. Кроме того, существует около 10 000 символических связей между узлами прецедентов. Роуз не счел нужным останавливаться на том, каких усилий потребовало создание подобной сети, но можно предположить, что такие ключевые задачи, как извлечение терминов и цитирование, были решены программно, а затем на основании этой информации автоматически сформированы узлы сети и связи между ними. Нужно принять во внимание и тот факт, что большинство горидических документов было уже ранее обработано публикаторами, которые составили достаточно полные индексы цитирования и ключевых слов.
Описанная сеть была затем использована в качестве базовой информационной структуры для извлечения документов. В основу функционирования системы положен принцип распространяющейся активности (spreading activation). Этот принцип не нов — ранее он использовался Квиллианом для работы с семантическими сетями (см. об этом в главе 6). Использование этого формального аппарата позволяет выяснить, существует ли какое-либо отношение между узлами в сети. Для этого запускается процесс распространения маркеров от узлов, представляющих интерес, и анализируется, произошло ли где-либо в сети "пересечение" распространяющихся маркеров.
Основная идея, положенная в основу работы SCALIR, состоит в том, что уровень активности данного узла должен быть пропорционален его "уместности" в рассматриваемом контексте.
Если в результате обработки запроса возбуждается некоторое число узлов слоя терминов, это должно привести к возбуждению узлов тех документов, которые касаются данного запроса, причем уровень возбуждения зависит от того, насколько тот или иной документ отвечает сути запроса. Узлы, воспринимающие запросы, являются, по сути, сенсорными узлами нейронной сети, от которых возбуждение по С-связям передается другим узлам. В процессе распространения возбуждения в дело включаются и S-связи, которые передают возбуждения от одних узлов документов другим, связанным с ними. Таким образом, символические связи отражают знания о том, что если определенный документ имеет отношение к полученному запросу, то, скорее всего, и связанный с ним другой документ также имеет отношение к этому запросу. Веса символических связей фиксированы, поскольку сила такой ассоциативной зависимости может быть оценена заранее.
Существуют два свойства функции активизации сети, которые представляются крайне желательными с точки зрения приложений, требующих ассоциативного поиска информации. Эти свойства влияют на выбор способа возбуждения сенсорных узлов, воспринимающих запросы пользователей, методики назначения весов связям и формы функции активизации.
(1) Количество активности, которое вносится в систему, не должно зависеть от размерности запроса.
(2) В каждом очередном цикле распространения активность не должна возрастать.
Если первое из указанных требований не будет выполняться, то запрос, состоящий из одного слова, приведет к меньшей активности сети, чем многословный. При этом окажется, что в ответ на более ограниченный многословный запрос система извлечет больше документов, чем в ответ на более свободный однословный, а это противоречит нашим интуитивным ожиданиям. Если же сеть не обладает вторым из сформулированных свойств, то будет извлечено слишком много документов, имеющих крайне слабое касательство к сути запроса, т.е. система будет производить много "информационного мусора".
Для того чтобы система обладала первым свойством, нужно на стадии предварительной обработки запроса распределить между входными узлами фиксированное количество активности.
Вторым свойством система будет обладать в том случае, если сумма весов выходных связей не будет превышать единицы и, следовательно, значение функции активизации будет меньше или равно ее аргументу.
С-связи используют линейную функцию активизации, которая содержит константу сдерживания (retention constant) р, как показано в приведенном ниже выражении. Значение этой константы определяет, какая часть активности узла сохраняется в последующем цикле возбуждения, а какая распространяется дальше по сети.
ai(t + 1) = р аj(t) + (1 - p) Sumj [Wij aj(t)]
Совершенно очевидно, что приведенная функция активизации будет удовлетворять сформулированным требованиям, поскольку ai(t +1)=< ai(t) до тех пока, пока Sumj[Wij= < 1]
Функция такого же вида использована и в работе [Belew, 1986]. Роуз следует идеям, изложенным в этой работе, и в отношении организации управления активностью сети в SCALIR.
Для выделения узлов, активность которых достаточна для участия в процессе извлечения информации, вводится параметр Os — порог значимости (significance threshold). Значение этого порога уменьшается по мере распространения активности по сети.
Для выделения узлов, активность которых слишком слаба и которые поэтому можно игнорировать в процессе извлечения информации, вводится параметр Oq — порог успокоения (quiescence threshold). Использование этого порога позволяет избежать непроизводительных затрат времени на анализ малоактивных узлов.
Эти параметры используются в алгоритме распространения активности по сети SCALIR, который в упрощенном виде представлен ниже. Этот алгоритм реализует метод поиска в ширину, начиная со входных узлов восприятия запроса (QUERY-NODES) и заканчивая всеми взвешеннымисвязями.
Установить исходное значение OS.
Включить в множество ACTIVE-NODES узлы из множества QUERY-NODES.
Цикл {
Если имеется запрос, установить уровни активности узлов в QUERY-NODES.
Включить в множество RESPONSE-SET все узлы из ACTIVE-NODES, чья активность превышает OS.
Удалить из множества ACTIVE-NODES все узлы, чья активность ниже Oq.
Добавить в множество ACTIVE-NODES все узлы, связанные с узлами, уже включенными в ACTIVE-NODES.
Обновить значение активности всех узлов множества ACTIVE-NODES, используя функцию активизации.
Рассортировать узлы в множестве ACTIVE-NODES по уровню активности. Уменьшить значение Os.
}
пока не будет выполнено (OS =< Oq) или (ACTIVE-NODES = 0).
В упрощенном варианте не рассматривается использование параметра, ограничивающего ширину пространства поиска. Кроме того, мы опустили в этой формулировке алгоритма и анализ максимального размера множества выходных узлов. Ограничение множества выходных узлов прекращает выполнение поиска после того, как выделено предельное количество извлекаемых документов.
Значение большинства параметров, используемых в процессе управления активностью сети, устанавливается эмпирически. Настройка же весов связей между узлами сети Wij представляет собой, по сути, процесс обучения системы, который мы вкратце рассмотрим в следующем разделе.
Системы ODYSSEUS и MINERVA
Программа ODYSSEUS обучается тому, как совершенствовать базы знаний экспертных систем, предназначенных для решения проблем эвристической классификации (см. главы 11 и 12). Она наблюдает за тем, как эксперт решает проблему, и формирует пояснение каждого действия эксперта (например, запрашивая эксперта, почему некоторому атрибуту присвоено то или иное значение). Формирование пояснений базируется на тех знаниях о проблемной области и стратегии решения проблем, которыми располагает программа. Если программе не удается сформировать пояснение, инициируется процесс коррекции базы знаний.
В какой мере можно отнести
1. В какой мере можно отнести MYCIN и CENTAUR к гибридным системам?
2. Можно ли считать системы с доской объявлений гибридными?
3. Почему компонентам, реализующим обучение, отводится такая важная роль в экспертных системах?
4. Какой смысл придается термину "обобщение на основе пояснений"? В чем отличие этой функции экспертной системы от методов обучения, рассмотренных в главе 20?
5. Рассмотрите следующее определение арки, состоящей из двух колонн (pillar) и перемычки (lintel), вместе с представленными за ним фактами.
Arch(X, Y, Z) :-left_pillar(X),
right_pillar(Y), lintel(Z),
supports(X, Z), supports(У, Z), apart(X, Y).
supports(X, Z), on(X, ground),
on(Y, X), not(on(Y, ground)).
apartfX, Y) :- not(touch(X, Y)).
;; Факты
left_pillar(objl). right_pillar(obj2).
on(obj1, ground). on(obj2, ground).
Iintel(obj3). on(obj3, p1). on(obj3, p2).
Как из этих фактов и правил, пользуясь методикой обобщения на основе пояснений, можно вывести определение понятия "арочность" (archhood)?
6. В чем заключаются сильные и слабые стороны подходов на основе правил и прецедентов и как их можно использовать совместно?
7. Что такое нейронная сеть? Какие преимущества сулит использование нейронных сетей по сравнению с символическими методами?
8. Проанализируйте фрагмент нейронной сети, представленный на рис. 23.4.
Рис. 23.4. Фрагмент нейронной сети
I) Что случится с узлом R, если узлы S1, и S3 будут возбуждены?
II) Как изменится состояние узла R, если дополнительно будет возбужден и узел S2?
9. Можете ли вы предложить вариант комбинирования символических и субсимволических парадигм, отличный от того, который использован в системе SCALIR? Сначала задумайтесь над возможностями его использования в задачах извлечения информации, а затем в других задачах, связанных с обработкой больших объемов информации, например распознавания речи.
Архитектурэкспертных систем
В данной книге мы представили классификацию инструментальных средств для проектирования экспертных систем, которая учитывает разнообразные подходы к представлению знаний и управлению процессом принятия решений. В частности, были выделены следующие категории систем.
Оболочки экспертных систем, которые поддерживают какой-либо язык представления знаний и комбинацию режимов управления. Такие оболочки хорошо зарекомендовали себя в ряде приложений, разработанных во времена становления экспертных систем.
Языки программирования высокого уровня, такие как интерпретаторы порождающих правил и объектно-ориентированные системы, которые образуют основные компоненты для представления знаний и управления ходом логического вывода.
Программные среды, использующие смешанные парадигмы, которые обеспечивают пользователя широким спектром средств представления и множеством механизмов управления.
Архитектуры решения проблем, такие как системы с доской объявлений, представляют собой объектно-ориентированные оболочки, на основе которых можно создавать конкретные приложения.
Полезные программные пакеты, которые можно использовать для решения определенных подзадач, например моделирования или анализа правдоподобия. Такие пакеты могут работать в тесном взаимодействии с основной программой решения проблемы.
Было показано, что программы построения экспертных систем первого поколения представляли собой, по существу, адаптацию экспертных систем, хорошо зарекомендовавших себя на практике. Многие из них показали затем свою жизнеспособность и эффективность. Например, система EMYCIN была использована для построения множества прикладных экспертных систем для областей, весьма далеких от медицины, включая структурный анализ и поиск неисправностей в электронных схемах. К этому же периоду относится и появление специализированных языков программирования, таких как OPS5 и FLAVORS.
Для систем второго поколения характерно использование смешанной архитектуры, объединяющей различные парадигмы.
Использование соответствующих инструментальных средств продемонстрировало, что с их помощью можно создавать системы с самой разнообразной архитектурой, поддерживающей разные способы представления знаний и механизмы управления процессом.
В прошлом часто высказывалось предположение, что использование в процессе разработки более мощных инструментальных средств будет способствовать упрощению программирования экспертных систем. Существует, однако, некоторый баланс между "мощностью" инструмента, принимающего решение за разработчика, и гибкостью, допускающей возможность выбрать решение, наиболее подходящее для конкретной системы. Чрезмерное упрощение оболочек зачастую оборачивалось слишком большими ограничениями для разработчиков прикладных систем, в то время как смешивание разных парадигм программирования предоставляло такую свободу, с которой не всякий программист мог разумно управиться. Как показала практика, наиболее эффективным путем оказалось предоставление разработчику тщательно продуманных готовых модулей, таких как системы анализа правдоподобия, которые способны эффективно решать отдельные важные нетривиальные задачи. Применение таких модулей существенно сокращает сроки разработки прикладных экспертных систем.
Языки программирования систем искусственного интеллекта
Правила логического вывода, теория ориентированных графов и математическая логика были изобретены задолго до появления такой области исследований, как искусственный интеллект. Но именно исследования в этой области позволили адаптировать формальный аппарат этих теорий к задачам представления знаний и отыскать высокоэффективные средства их реализации. Развитие современных продукционных, объектно-ориентированных систем и систем процедурной дедукции в значительной мере определяется такими приложениями искусственного интеллекта, как проблемы классификации и конструирования, описанные в ряде глав данной книги.
Хотя в ходе исследований искусственного интеллекта появилось множество самых различных языков представления, все они обладают рядом сходных свойств.
Во-первых, все такие языки являются декларативными в том смысле, что позволяют описывать знания, имеющие отношение к решению конкретной задачи, а не способ ее решения. В большинстве экспертных систем используется архитектура, в которой знания отделены от машины логического вывода. Это позволяет проводить эксперименты с использованием одних и тех же знаний в разных режимах обработки. Некоторые новые архитектурные решения, например использующие доску объявлений, позволяют представлять управляющие знания декларативно и обрабатывать их так же, как и другие виды знаний.
Во-вторых, все такие языки организованы по модульному принципу. Подобно тому, как сам язык скрывает от пользователя детали механизма реализации, отдельные модули знаний скрывают детали своей реализации друг от друга, общаясь через глобальную структуру данных (в продукционных системах и системах на основе доски объявлений) или посредством определенных протоколов (в объектно-ориентированных системах). Это позволяет наращивать объем базы знаний и использовать методику отработки проектируемой системы на прототипах.
В-третьих, механизм вызова процедур в таких языках основан на сопоставлении образцов в той или иной форме. Активизация правил в продукционных системах, включение источников знаний в системах с доской объявлений и резолюция фраз в дедуктивных системах в той или иной форме используют такое сопоставление.
Это очень мощный и достаточно общий механизм, который способствует модульной организации компонентов системы, хотя и требует определенных вычислительных ресурсов.
Языки представления знаний обычно реализуются в виде системы логического вывода, управляемой сопоставлением образцов. Программа на любом из языков такого рода состоит из множества относительно независимых модулей (правил, структур или фраз), которые сопоставляются со входными данными и манипулируют имеющимися в памяти данными. В любой такой системе имеются три существенных компонента.
Набор модулей, каждый из которых может быть активизирован данными, поступающими на вход системы, если эти данные соответствуют образцу, определенному для этого модуля.
Одна или несколько динамических структур данных, которые могут анализироваться и модифицироваться активизированным модулем.
Интерпретатор, который циклически управляет выбором и активизацией модулей.
Исследования в этой области в последние годы концентрируются вокруг следующих задач:
поиск эффективных методов реализации интерпретаторов;
создание на основе "чистых формализмов" программных средств, пригодных для практического применения;
проведение экспериментов со "смешанными" формализмами, объединяющими разные парадигмы.
На сегодняшний день такие языки, как CLIPS, предоставляют в распоряжение пользователя множество разнообразных средств представления знаний и манипулирования ими, которые в руках специалистов позволяют создавать программы для решения широкого круга практических проблем.
Представление знаний
В определенном смысле любая компьютерная программа содержит знания. Программа сортировки по методу "пузырька", написанная на языке BASIC, содержит знания программиста о том, как упорядочить элементы списка. Так чем же все-таки представление знаний отличается от обычного программирования?
Разобраться в сути компьютерной программы, решающей задачу сортировки списков, совсем непросто. Она, конечно же, содержит знания программиста о методе решения задачи, но, помимо этих знаний, в ней содержатся и другие:
как манипулировать языковыми конструкциями используемого языка программирования;
как добиться высокой производительности программы;
как выбрать подходящие методы решения частных проблем обработки данных, играющих, тем не менее, важную роль в достижении конечного результата, и как организовать управление процессом.
Языки представления знания являются языками высокого уровня, специально предназначенными для кодирования в явном виде фрагментов знаний человека, таких как правила влияния и набор свойств типовых объектов, причем высокий уровень языка проявляется в том, что от пользователя скрываются, насколько это возможно, технические подробности механизма представления знаний. Конечно, пользователь при желании может познакомиться со всеми деталями, но идея состоит в том, что это совсем не обязательно делать в процессе разработки программы. В отличие от более привычных языков профаммирования, языки представления знаний исключительно экономичны в смысле объема программного кода. В значительной мере это объясняется тем, что заботу о множестве мелочей берет на себя интерпретатор языка. Можно показать, что большинство из них обладает всеми признаками машины Тьюринга, другими словами, такие интерпретаторы теоретически способны выполнять любые вычисления, которые под силу машине, реализующей программу, написанную на любом из "обычных" языков программирования.
Несмотря на отмеченные достоинства таких языков, нельзя забывать и о существовании определенных проблем при их применении.
Решение практических проблем
В главах с 10 по 15 мы познакомили вас с идеей, которая состоит в том, что существует несколько обобщенных задач, которые в том или ином виде решаются в большинстве экспертных систем. В частности, мы показали, чем отличаются задачи классификации от задач конструирования, и что для своего решения эти задачи требуют применения совершенно разных стратегий поиска.
При решении задач классификации основной акцент делается на отыскании приемлемого, но, возможно, приближенного соответствия между данными и решениями на некотором уровне абстракции. Нужно учесть все имеющиеся свидетельства, объединить их каким-то образом, а затем уточнить и ранжировать решения-кандидаты. В таких задачах пространство решений, как правило, известно заранее, и представленные в нем категории могут быть перенумерованы. Для работы с таким пространством вполне подходят методы исчерпывающего поиска, которые используют наличие определенности для упорядочения и отсечения путей поиска. Для работы с пространствами поиска большого объема, которые не удается разбить на несколько относительно независимых подпространств, приходится использовать более сложные методы, настроенные на определенную форму организации пространства гипотез (например, иерархическую и причинную).
Суть задачи конструирования состоит в построении некоторого сложного объекта, который должен удовлетворять заданным ограничениям. Естественно, что при этом пространство решений оказывается очень большим. Обычно не удается проследить все возможные пути на пространстве решений в поиске оптимального, чаще всего отыскивается одно из приемлемых решений, удовлетворяющих ограничениям. Ограничения могут влиять друг на друга, и в такой ситуации для разрешения конфликтов нужно использовать знания о предметной области. Наиболее общей для решения задач конструирования оказалась стратегия предложение и пересмотр. Суть ее состоит в том, что частичные решения расширяются до тех пор, пока не будут нарушены заданные ограничения, а затем такое нарушение устраняется с помощью эвристик.
Несмотря на то, что в большинстве случаев можно считать, что типичной задачей классификации является диагностирование, а задачей конструирования — планирование, соответствие между реальными приложениями и обобщенными задачами носит более сложный характер.
Вы имели возможность убедиться, что такие программы диагностирования, как INTERNIST, фактически используют методику решения задачи конструирования. Элементами решения являются отказы, которые объединяются в составную гипотезу. Таким образом, оказывается, что нет никакого смысла заранее нумеровать узлы пространства решений, поскольку пациент может страдать десятью и более заболеваниями. Более того, в общем виде проблема отыскания "наилучшего" объяснения имеющемуся набору симптомов относится к классу необозримых. Без использования мощного механизма концентрации внимания программы на определенном участке пространства не удается отыскать даже приблизительное решение проблемы. Поэтому для решения подобных задач дифференциального диагностирования используются средства, типичные для задач конструирования.
Ряд программ, например R1/XCON, обладает знаниями, достаточными для того, чтобы решить задачу конструирования без использования рекурсии предположений и возврата назад. В рамках стратегии нисходящего уточнения, которая предполагает разбиение задачи построения конфигурации вычислительной системы на ряд практически независимых подзадач, система R1 иногда переключается на восходящую методику логического вывода. На примере системы планирования ONCOCIN мы показали, что для решения проблемы планирования могут иногда использоваться стратегии, характерные для задач эвристической классификации. Благодаря тому, что в этой системе применяется довольно жестко формализованное представление протоколов лечения онкозаболеваний, появилась возможность выбирать подходящую заготовку плана лечения из библиотеки, а затем адаптировать ее к конкретному случаю.
Но как бы там ни было, разграничение задач классификации и конструирования оказалось исключительно полезным, поскольку помогло автоматизировать процесс приобретения знаний.
Было также показано, что функциональные возможности программных средств извлечения знаний могут быть существенно расширены, если такие средства будут включать в свой состав декларативную модель предметной области и некоторые знания, касающиеся решаемой задачи, в частности — как будут использованы в приложении получаемые знания. Хотя разработка систем извлечения знаний с ограничением ролей, таких как MORE и RIME, еще не вышла из стадии лабораторных экспериментов, они ознаменовали собой появление новой мощной методологии построения баз знаний. В ее основу положена концепция "извлечение знаний также должно базироваться на знаниях". Первые полученные результаты дают основание надеяться, что на основе этой методологии будут созданы эффективные средства, которые позволят устранить одно из основных "узких" мест в практике проектирования экспертных систем. Автоматический анализ целостности базы знаний и компиляция их в форму выполняемых модулей также в значительной мере упрощается при использовании модели предметной области и информации о принципах решения проблем, используемых в проектируемом приложении.
Загадкискусственного интеллекта
Тема искусственного интеллекта всегда была в информатике "страной плохишей", населенной массой "неправильных" проблем, не поддающихся решению традиционными способами. Эта область привлекла внимание прежде всего разносторонних специалистов, которых не испугало ее открытое, лишенное всякой организации пространство, — людей, которых влечет задача узнать, как мы мыслим. Такие исследователи, как Марвин Минский (Marvin Minsky), Джон Мак-Карти (John McCarthy), Герберт Саймон (Herbert Simon), Пат Хейес (Pat Hayes), Дональд Мичи (Donald Michie) и Бернард Мельтцер (Bernard Meltzer), стали первопроходцами для тех, кто следовал за ними по пути, пролегающем через информатику, психологию и математическую логику.
Я предлагаю вам задуматься над вопоосами: "Зачем при построении экспертных систем нам вообще нужны технологии, используемые в задачах искусственного интеллекта? Почему нас не устраивают традиционные информационные технологии, такие как матемагическое моделирование? Или, другими словами, тот факт, что экспертные системы начали развиваться в русле задач искусственного интеллекта, является случайностью либо в этом была своя логика?"
Не вдаваясь в длительные рассуждения, можно ответить, что нет ничего плохого в использовании для построения экспертных систем подходящих традиционных технологий, если это приводит к желаемому результату. Например, генерация гипотез в системе DENDRAL (см. главу 20) основана на алгоритме перечисления вершин плоского графа, а в системе MYCIN (см. главу 3) использован статистический подход для выбора способа лечения на основе анализа чувствительности организма к тем или иным лекарственным препаратам. Использование методов поиска или языков программирования, характерных для систем искусственного интеллекта, не запрещает инженерам по знаниям применять методики, заимствованные из прикладной математики, исследования операций или других подходящих дисциплин. Для некоторой части рассматриваемой проблемы решение может быть получено чисто алгоритмически или математически, и было бы непозволительной роскошью отказываться от таких методов, если они способствуют достижению нужного результата.
В этой главе мы еще
24.1. Загадка искусственного интеллекта
24.2. Представление знаний
24.3. Языки программирования систем искусственного интеллекта
24.4. Решение практических проблем
24.5. Архитектура экспертных систем
Рекомендуемая литература
В этой главе мы еще раз вспомним темы, рассмотренные в данной книге, и порекомендуем, что нужно прочесть тем, кто пожелает еще глубже изучить их. Обзор организован таким образом, что в нем в сжатом виде будет суммирован материал, разбросанный по разным разделам. В ходе изложения тех или иных тем вам встретятся ссылки на предыдущие главы, но я старался не злоупотреблять ими. В этой главе представлены некоторые прогнозы дальнейших путей развития исследований в области искусственного интеллекта и, в частности, экспертных систем, которые могут послужить материалом для последующей очной или заочной дискуссии. Эти прогнозы представляют мое личное мнение, если только не оговорено обратное, и читатели вольны отнестись к ним с известной долей скептицизма.
Дополнительные модули
Под дополнительными модулями понимаются те полезные программы, которые можно выполнять вместе с приложением. Как правило, такие программы реализуют некоторые специальные функции, как бы "снимая их с полки", причем для обращения к таким функциям не требуется что-либо программировать в основном приложении или заниматься его индивидуальной настройкой. Одним из примеров такого рода дополнительного модуля может служить программный пакет Simkit из комплекта среды КЕЕ. Этот пакет позволяет оснастить экспертную систему методами моделирования.
Другой функцией, которая поддерживается дополнительными модулями сред КЕЕ и ART, является механизм обработки множества различных контекстов логических рассуждений. В первом приближении можно считать, что контексты формируются теми ветвями в пространстве поиска, которые допускают использование более чем одного оператора. Рассмотрим представленный ниже сценарий, в котором имеются два правила, в каждом из которых условная часть удовлетворяется в текущем контексте рассуждений.
[Правило 1]
ЕСЛИ: сегодня рабочий день И
нет признаков недомогания, ТО: посетить занятия по информатике.
[Правило 2]
ЕСЛИ: сегодня рабочий день И
погода прекрасна, ТО: покататься на яхте.
В большинстве систем, основанных на порождающих правилах, выбор того единственного правила, которое будет активизировано, зависит от реализуемой стратегии разрешения конфликтов. Но в некоторых приложениях предпочтительным вариантом будет разделить текущий контекст на два разных, в одном из которых будет активизировано правило 1, а в другом — правило 2 (рис. 17.1). В каждом из этих контекстов будет сделано разное заключение, однако можно так организовать процесс, чтобы в каждый контекст была включена и информация из родительского контекста. Тогда в обоих контекстах будет учитываться, что сегодня понедельник и за окном прекрасная погода.
Теперь можно раздельно обрабатывать каждый контекст, причем в процессе дальнейшей обработки не исключено и аналогичное повторное разделение контекстов.
В результате будет сформировано несколько вариантов решения проблемы.
Но можно в процессе обработки попасть в такую ситуацию, которая расценивается как неудача процесса вывода, например нарушение исходных ограничений. В нашем примере такой неудачей может быть заключение о том, что экзамен по информатике будет провален вследствие выполнения правила
[Правило 3]
ЕСЛИ: не посещать занятия по информатике,
ТО: экзамен по информатике будет провален
Получение такого заключения должно было бы привести к тому, что линию рассуждений, порожденную, правилом 2, следует исключить из рассмотрения. Говорят, что соответствующий контекст отравлен. Как правило, удаляется вся цепочка рассуждений, вплоть до последнего "размножения" контекстов. Таким образом, контексты, выделенные утолщенными прямоугольниками на рис. 17.1, должны быть исключены из рассмотрения, и останется только одна цепочка, в соответствии с которой будет сделан вывод о необходимости посетить занятия по информатике, несмотря на все соблазны.
Таким образом, множество контекстов соответствует альтернативным вариантам решений или альтернативным предположениям на разных стадиях процесса логического вывода. Проблема обработки множества предположений и зависимостей между ними достаточна сложна и выделена в отдельное направление исследований, получившее наименование обработки правдоподобия (truth maintenance) или обработки причинности (reason maintenance). Детальнее мы остановимся на этом вопросе в главе 19, где будут рассмотрены альтернативные варианты организации вычислений.
Рис. 17.1. Пример множества контекстов
Тенденция использования дополнительных модулей будет скорее всего развиваться, поскольку пользователи экспертных систем часто нуждаются в разного рода дополнительных функциональных возможностях, специфичных для конкретного приложения, а также в возможности интегрировать экспертную систему с программными продуктами других классов. На практике экспертная система часто используется вместе в базой данных или системой управления движением робота, получает информацию от систем обработки сигналов или пакетов статистической обработки.
Мы постарались дать вам общее представление о возможностях инструментальных средств, применяемых при разработке и эксплуатации экспертных систем, не вдаваясь в подробности реализации разных моделей таких средств. В следующем разделе основное внимание будет уделено выбору подходящих средств, обучению методике работы с ними и внедрению этих средств в практику проектирования систем. Вы увидите, что каждая из этих фаз сопряжена со множеством проблем, но некоторых из них при рациональном подходе можно избежать.
17.2. Логический вывод в разных контекстах
Ниже приведен программный код на языке CLIPS, в котором реализована описанная выше стратегия работы со множеством контекстов.
;; ШАБЛОНЫ
;; Fact представляет собой субъект с определенными
;; свойствами.
;; Поле "world" несет информацию о контексте,
(deftemplate fact
(field subj (type SYMBOL))
(field attr (type SYMBOL))
(field world (type INTEGER))
)
;; Act представляет действие с объектом.
;; Поле "world" несет информацию о контексте.
(deftemplate act
(field action (type SYMBOL))
(field object (type SYMBOL))
(field world (type INTEGER))
)
;; Context имеет статус либо OK ,
;; либо NG (no good - плохой).
(def template context
(field id (type INTEGER))
(field status (type SYMBOL))
)
;; Модель мира в исходном состоянии.
(def facts model
(context (id 1) (status OK))
(fact (subj weather) (attr sunny) (world 1))
)
; ; ПРАВИЛА
; ; Если дождя нет,
;; создать новый контекст, в котором можно
;; пропустить занятия.
(def rule skip
(fact (subj weather) (attr ?W&~rainy) (world ?C)) =>
(assert (act (action skip) (object class)
(world (+ ?C 1)))) (assert (context
((id (+ ?C 1)) (status OK)))
)
;; Если пропустить занятия,
;; то на экзамене вас ждет провал.
(defrule fail
(act (action skip) (object class) (world ?W)) =>
(assert (act (action fail) (object exam) (world (?W)))
)
;; Если контекст содержит действие fail,
;; пометить его маркером NG. (defrule poison
(act (action fail) (world ?W)) .
?C <- (context (id ?W) (status OK)) =>
(modify ?C (status NG))
)
Как только контекст будет помечен маркером NG, с ним можно будет выполнять операции, предусмотренные для отравленного контекста, например удалить все связанные с ним факты и действия (см. упр. 8 в конце главы).
Характерные сложности и способы их избежать
В своей книге Уотерман перечисляет следующие "ловушки", поджидающие разработчика экспертной системы на этапе внедрения, и дает рекомендации, как их избежать [Waterman, 1986, Chapter 19].
Знания, касающиеся предметной области, слишком тесно переплетены с остальной частью программы. В частности, невозможно разделить эти знания и знания общего применения, касающиеся способов поиска в пространстве решений. Уотерман предполагает, что этого можно достичь, положив в основу организации базы знаний набор правил, хотя из замечаний, сделанных Кленси и Эйкинс, следует, что такая организация отнюдь не гарантирует достижение ожидаемого результата.
Та база знаний, которая сформировалась после извлечения и представления сотен правил в процессе опроса экспертов, может оказаться все-таки настолько неполной, что не позволит решить и простую задачу, поскольку в ней отсутствуют фундаментальные концепты предметной области или эти концепты представлены с ошибками. Уотерман рекомендует последовательно наращивать объем базы знаний, причем начинать с фундаментальных понятий. Это позволит еще на ранних стадиях разработки обнаружить указанную проблему. Он советует выполнять тестирование на каждом этапе разработки, используя для этого подходящие инструментальные средства инженерии знаний.
Среда разработки не располагает встроенными средствами формирования функций пояснения экспертной системы, а добавление таких функций в уже спроектированную систему — задача не из легких. Уотерман советует позаботиться о прозрачности экспертной системы с первых же шагов ее разработки. Это очень ценный совет, поскольку без хорошего "окна", через которое можно заглянуть в "машинный зал" программы, даже ее создатель не сможет понять, что же она на самом деле делает.
Система содержит чрезмерно большое количество слишком специфических правил. Это, во-первых, приводит в замедлению работы системы, а во-вторых, затрудняет управление ею. Уотерман рекомендует объединять, где только возможно, мелкие правила в более общие.
Инструментальные средствразработки экспертных систем
17.1. Общая характеристика инструментальных средств для построения экспертных систем
17.2. Оболочки экспертных систем
17.3. Языки программирования высокого уровня
17.4. Использование инструментальных средств
17.5. Некоторые максимы разработки экспертных систем
Рекомендуемая литература
Упражнения
Эту главу не следует рассматривать в качестве исчерпывающего справочника по доступным на сегодняшний день инструментальным средствам разработки экспертных систем. Представленный в ней материал скорее претендует на то, чтобы дать читателю общее представление о состоянии разработок в этой области и возможностях типовых средств подобного назначения. Хотя некоторые из рассматриваемых в этой главе программ и упоминались ранее, здесь мы старались систематизировать имеющиеся о них сведения, обращая основное внимание на использованную методику и способы практического применения.
Как и в предыдущих главах, при необходимости проиллюстрировать те или иные методы программирования мы пользуемся языком CLIPS, хотя вы встретите и несколько фрагментов программ на других языках. Более сложные и специализированные инструментальные средства, в частности системы с доской объявлений и системы обработки правдоподобия, будут детально рассмотрены в главах 18 и 19. В этой же главе мы представим общие тенденции в разработке и использовании инструментальных средств для построения экспертных систем.
Использование инструментальных средств
Хотя на этапе внедрения экспертной системы возникает очень много сложностей, до сих пор не предпринималось попытки их каким-либо образом систематизировать. В этом разделе мы ставили перед собой задачу познакомить пользователя с проблемами, наиболее часто возникающими при внедрении, и тем, как их избежать, как выбрать подходящие инструментальные средства для инженерии знаний, как организовать освоение и использование этих средств на практике. Возможно, приведенный ниже материал покажется вам в определенной мере противоречивым, но мы старались представить в нем как можно более широкий спектр существующих на сей счет мнений.
Языки логического программирования экспертных систем
Критически оценивая первый опыт применения инструментальных средств типа оболочек при проектировании экспертных систем, в частности опыт использования EMYCIN, многие исследователи полагали, что более перспективным является альтернативный подход, основанный на логическом программировании (см., например, [Kowalski, 1982]). Например, предполагалось, что порождающие экспертные системы, аналогичные MYCIN, могут быть довольно просто реализованы на языке PROLOG [Clark and McCabe, 1982]. Правила можно представить в виде фраз Хорна (см. об этом в главе 8), в которых головной (позитивный) литерал соответствует заключению, а прочие (негативные) литералы будут соответствовать условиям.
Встроенный в PROLOG режим управления приблизительно соответствует стратегии обратного логического вывода, которая используется в системах, подобных MYCIN. Таблицы знаний и другие данные можно представить с помощью утверждений. Рекурсивные структуры данных — графы и деревья — можно организовать с помощью фраз языка PROLOG, которые содержат комплексные термы. Языковые средства PROLOG позволят программисту разработать собственный механизм обработки неопределенности, причем не исключается и использование коэффициентов уверенности.
С практической точки зрения, пользуясь языком PROLOG, программист в качестве "бесплатного приложения" получает в свое распоряжение следующие возможности:
индексированную базу данных фраз, которые можно использовать для представления правил, процедур или данных;
универсальный механизм сопоставления, который позволяет выполнять сопоставление данных и шаблонов, включающих переменные, и возвращать подстановку, которая может обеспечить их совпадение;
стратегию управления (поиск в глубину — depth-first search), основанную на правилах нисходящего поиска (фразы, которые размещены в базе данных ближе к "голове", обрабатываются первыми) и вычислении слева направо (подцели обрабатываются в том порядке, в котором они перечислены в списке).
Действительно, дедуктивную порождающую систему довольно ПРОСТО эмулировать на языке PROLOG. Можно без особого труда разработать и простой интерпретатор, реализующий стратегию построения прямой цепочки вывода. Модификация рабочей памяти выполняется операторами assert и retract, которые добавляют или удаляют формулы из базы данных. Вы уже знаете из главы 11, как можно организовать локальное управление ходом процесса в системе, основанной на фреймах, как организовать обработку значений по умолчанию и исключений, хотя эти методы и не вписываются в стандартную логику.
Успешный опыт применения идей логического программирования, в частности создание программы МЕСНО (см. главу 11), продемонстрировал ряд явных отклонений от синтаксиса исчисления предикатов первого порядка и его процедурной интерпретации в стандартной версии PROLOG. Некоторые семантические и синтаксические ограничения в программах МЕСНО и PLANNER до сих пор не преодолены в системах, базирующихся на языках логического программирования.
Языки описания порождающих правил
Но, естественно, возможности языков высокого уровня также не беспредельны — каждый из них имеет свои ограничения. Например, в языке OPS5 возможности динамической памяти ограничены размещением векторов в рабочей памяти, что не позволяет строить в ней рекурсивные структуры данных, такие как графы или деревья. При разработке системы MORE (о ней речь шла в главе 12) из-за этого возникли серьезные сложности [Kahn, 1988]. Некоторые типы структур управления ходом выполнения, например рекурсивные и итерационные циклы, также с трудом реализуются в этом языке. В общем, это та цена, которую приходится платить за относительную простоту программного кода на языке OPS5 и эффективность его выполнения.
В ранних моделях систем, основанных на порождающих правилах, до 90% времени работы уходило на выполнение операций сопоставления условий. Но позднее Форджи обратил внимание на возможные источники низкой эффективности такого упрощенного подхода [Forgy, 1982]. Алгоритм сопоставления RETE, предложенный Форджи и реализованный в языках описания порождающих правил семейства OPS, базируется на двух наблюдениях.
В левых частях порождающих правил, которые размещаются в рабочей памяти, часто встречаются повторяющиеся условия. Если одно и то же условие встречалось в N правилах, то при прежнем упрощенном подходе выполнялось N операций сопоставления. Это пример внутрицикловой итерации (within-cycle iteration).
Простейший подход при сопоставлении условий предполагает просмотр в каждом цикле всех элементов рабочей памяти, хотя содержимое рабочей памяти от цикла к циклу изменяется очень мало. Форджи назвал это межцикловой итерацией (between-cycle iteration).
Предложенный Форджи алгоритм значительно снижает количество внутрицикловых итераций за счет использования сети сортировки, имеющей древовидную структуру. Выражения в левой части порождающих правил компилируются и включаются в эту сеть, а алгоритм сопоставления довольно просто определяет конфликтующее множество, просматривая состояние сети в текущем цикле.
Количество межцикловых итераций сокращается за счет обработки множества лексем, которые являются индикаторами удовлетворения условий, размещенных в рабочей памяти. Это множество лексем отображает изменения, происходящие в рабочей памяти от цикла к циклу, и таким образом позволяет выявить те условия, которые подлежат проверке. Поскольку никаких других процессов управления, кроме цикла распознавание-действие, в системе не существует, то обработать полученное в результате конфликтующее множество не представляет особого труда. Механизм разрешения конфликтов выполняет это, не обращая внимания на другие аспекты текущего контекста вычислений.
Совершенно очевидно, что попытка использовать рекурсивные структуры данных потребует серьезного усложнения описанного процесса обработки правил. Точно так же и изменение режима управления приведет к тому, что механизм разрешения конфликтов вынужден будет анализировать дополнительную информацию. Разработчики языков, подобных OPS, всегда вынуждены искать компромисс между мощностью выразительных средств языка и эффективностью выполнения программного кода. До сих пор в среде исследователей предметом оживленных дискуссий является вопрос о том, удалось ли разработчикам OPS5 найти такой компромисс. Разработанные позже языки КЕЕ, КАРРА и CLIPS унаследовали от OPS5 синтаксис и механизм активизации правил. Все эти языки используют различные версии алгоритма RETE при формировании множества конфликтующих правил.
Преодоление недостатков программирования порождающих правил лежит не на пути усложнения существующих языков программирования, а скорее на пути объединения их с другими парадигмами программирования, позволяющими использовать рекурсивные структуры данных и управления. Примером такого объединения может служить комбинирование порождающих правил и фреймов, что позволяет сопоставлять условия, специфицированные в правилах, с содержимым слотов фреймов (см. главу 13). Для решения проблем управления в последнее время все чаще используется включение наборов правил в более мощную.вычислительную среду, которая позволяет работать со списками заявок и с множеством источников знаний (подробнее об этом — в главе 18).
Языки программирования высокого уровня
Языки высокого уровня являются в руках опытного программиста прекрасным средством быстрого создания прототипа экспертной системы, позволяют обеспечить гибкость процесса разработки при одновременном снижении материальных затрат и сокращении сроков выполнения проекта. Как правило, среда разработки таких языков обеспечивает совмещение интерфейса разработки и времени выполнения, что позволяет совместить вставку, редактирование и тестирование фрагментов программного кода. Но пользовательский интерфейс такой среды уступает интерфейсу оболочек по части "дружественности", что, правда, не мешает опытному программисту быстро ее освоить.
Языки описания порождающих правил, объектно-ориентированные языки и процедурные дедуктивные системы предоставляют проектировщику экспертных систем значительно большую свободу действий, чем оболочки. Особенно это касается программирования процедур управления и обработки неопределенности. Как отмечалось выше, обычно оболочка имеет встроенный режим управления и методы обработки неопределенности, которые не могут быть затем изменены в процессе построения на ее основе конкретной экспертной системы. Та гибкость, которую предоставляют программисту языки высокого уровня, особенно важна при создании экспериментальных систем, в которых заранее выбрать оптимальный режим управления вряд ли возможно.
Многофункциональные программные среды
17.3.4. Многофункциональные программные среды
Многофункциональные программные среды позволяют опытному программисту экспериментировать при решении новых классов проблем, выбирая подходящие сочетания различных методов, представленных в имеющемся модульном наборе. Поскольку не существует единственного универсального языка представления знаний для произвольной экспертной системы, у разработчиков возникает желание объединить несколько различных схем представления, особенно на этапе создания прототипа. Хотя исчерпывающей теории таких гибридных систем и не существует, эксперименты с разными схемами представления и логического вывода показали, что каждая из них имеет свои слабые стороны. Поэтому понятно желание объединить разные методики таким образом, чтобы достоинства одних компенсировали слабости других.
Мы уже не раз обращали ваше внимание на то, что порождающие правила позволяют представить в программе эмпирически выявленные связи между условиями и действиями, между наблюдениями и гипотезами, но они значительно хуже подходят для представления отношений между объектами предметной области, включая и такие важнейшие, как отношения множество/элемент или множество/подмножество. Структурированные объекты, например фреймы, оказываются более удобным средством для хранения и манипулирования описаниями объектов предметной области, но применение таких знаний требует включения в программу фрагментов программного кода (например, на языке LISP), которые затем трудно анализировать. Рациональное зерно в первых попытках свести вместе стили, основанные на правилах и фреймах, состояло в том, чтобы объединить способность представлять объекты, характерные для фреймов, с возможностями связывать условия и действия с помощью порождающих правил.
Одной из первых многофункциональных сред искусственного интеллекта является LOOPS [Bobrow and Steflk, 1983], в которой в рамках единой архитектуры обмена сообщениями были объединены четыре парадигмы программирования, перечисленные ниже.
Процедурно-ориентированное программирование. Эта парадигма была представлена языком LISP, в котором активным компонентом являются процедуры, а пассивным — данные, несмотря на то, что в LISP процедуры сами по себе также являются данными, поскольку имеют вид списков.
В рамках единой среды процедуры могут быть использованы для обработки внешних данных, в частности изменения значений общедоступных переменных.
Программирование, ориентированное на правила. Эта парадигма аналогична предыдущей, но роль процедур играют правила "условие-действие". В среде LOOPS наборы правил сами по себе являются объектами, которые можно рекурсивно вкладывать один в другой. Таким образом, часть "действие" одного правила, в свою очередь, может активизировать подчиненный набор правил. С множествами правил связываются управляющие компоненты, с помощью которых в простейшей форме выполняется разрешение конфликтов.
Объектно-ориентированное программирование. Структурированные объекты обладают свойствами и процедур, и данных, причем побочные эффекты обычно локализуются в пределах объекта. Обработка поступающих сообщений приводит к передаче данных или изменению их значений, но все манипуляции данными выполняются под управлением того компонента, который обратился к объекту. При этом вызывающий объект совершенно не интересует, как хранятся данные и как они модифицируются внутри объекта.
Программирование, ориентированное на данные. Доступ к данным и обновление данных запускает определенные процедуры, причем не имеет значения, почему изменен компонент данных, — то ли это результат побочного эффекта, то ли результат действия других процедур. С переменными, в которых хранятся значения данных, связываются определенные процедуры, подобно тому, как это делается в слотах фрейма, причем такие переменные часто называют активными величинами. В таких приложениях, как моделирование, этот стиль программирования оказывается довольно продуктивным, поскольку позволяет распространить эффект изменения какого-либо компонента на прочие, с ним связанные.
В рамках основной объектно-ориентированной парадигмы модули среды, поддерживающие разные стили программирования, можно комбинировать. Обычно условия в порождающих правилах и логические фразы связываются со значениями слотов структурированных объектов, а правила модифицируют значения этих слотов.
Именно такой стиль объединения парадигм в настоящее время реализован в языке CLIPS.
В системах КЕЕ и LOOPS поведение объектов описывается в терминах множества порождающих правил, как это сделала Эйкинс (Aikins) в системе CENTAUR (см. об этой системе в главах 13 и 16). В средах КЕЕ и Knowledge Craft к перечисленным выше парадигмам добавлено и логическое программирование в стиле языка PROLOG. Новая версия КЕЕ, известная под названием КАРРА-РС, предоставляет в распоряжение программиста еще более широкий набор стилей для комбинирования правил, объектов и процедур.
17.1. CUPS как многофункциональная среда программирования
Кроме поддержки интерпретатора порождающих правил, описанного в главе 5, CLIPS обладает следующими функциональными возможностями:
для определения стандартных функций используется синтаксис, подобный LISP (сведения о LISP вы найдете в главе 4);
предоставляет в распоряжение разработчика родовые функции, аналогичные мультиметодам CLOS (см. главу 7);
располагает встроенным объектно-ориентированным языком 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-фрагменты как подпрограммы. Это позволяет внедрять функции искусственного интеллекта в компоненты больших программных комплексов.
Некоторые максимы разработки экспертных систем
Чтобы не заканчивать эту главу на такой печальной ноте, я решил включить в последний раздел избранные максимы о построении экспертных систем, почерпнутые из классической работы Бучанана [Buchanan et al., 1983]. Следование им избавит проектировщика экспертных систем от опасности "наступить на грабли", многократно "опробованной" его коллегами. Другим прекрасным источником умных мыслей по тому же поводу может служить книга Преро [Ргегаи, 1990].
Нежизнеспособность некоторых проектов закладывается еще на самых ранних стадиях работы над ними. Приведенные ниже рекомендации помогут избежать этого.
Задача, которую предполагается решать с помощью проектируемой системы, должна быть вполне под силу эксперту-человеку.
Задача должна быть четко сформулирована.
Уже на первой стадии работы над системой подумайте над тем, как она будет совершенствоваться.
Особенно важно с самого начала очертить границы, которых должна достичь система в процессе эволюции. Для этого весьма полезно четко определить, что система не сможет делать. Лучше создать систему, которая сможет надежно решать ограниченную задачу, чем систему, претендующую на решение широкого класса задач, но дающую верное решение лишь время от времени. Конечно, надежность системы, т.е. степень ее правоты, можно оценить, только располагая соответствующим критерием этой самой правоты.
Тщательно отработайте поведение системы на наборе репрезентативных частных случаев и организуйте библиотеку таких случаев для проектируемой системы.
Отделите те знания, которые специфичны для определенной предметной области, от знаний, касающихся общей методики решения проблем. Старайтесь, насколько это возможно, упростить машину логического вывода в системе.
Убедитесь, что те примеры, которыми вы располагаете на этапе проектирования, репрезентативны. С самого начала постарайтесь либо самостоятельно разработать, либо заимствовать программный код, который упростит опробование принятых проектных концепций на этих примерах.
Большую помощь в этом может оказать программная среда, которая позволяет подробно документировать сеанс работы с такой экспериментальной системой, включая и фиксацию всех вводимых пользователем данных. Проблема разделения различных видов знаний довольно подробно освещалась в главах 10, 11 и 16.
В отношении формулировки правил авторы упомянутых работ советуют следующее.
Если правило выглядит большим, то так оно и есть.
Если несколько правил очень похожи друг на друга, обратите внимание на те концепты проблемной области, на которых они базируются.
Как и при программировании задач общего назначения, следуйте золотому правилу "краткость — залог надежности". Наличие избыточности почти всегда является признаком того, что возможна какая-то упрощающая абстракция.
У Преро вы встретите и рекомендации, касающиеся этапа реализации экспертной системы. Ниже приведены некоторые из них.
Группируйте правила в отдельные множества.
В системе COMPASS все правила разделены на 18 групп. Только семь из них относятся действительно к процессу решения проблем, т.е. к тому, чем в обычной "бескомпьютерной" жизни занимается эксперт, а остальные обеспечивают выполнение функций поддержки, сбора данных и т.п. В системе используются также демоны, которые расширяют возможности выполнения действий, в частности организуя передачу сообщений между объектами (см. о демонах в главе 6).
Постарайтесь на самых ранних стадиях разработать систему соглашений об оформлении программы. Это придаст ей единообразный вид.
Как уже отмечалось выше, многие программисты, попав в ситуацию, когда можно использовать множество парадигм программирования, забывают о необходимости (или желательности) разрабатывать структурированный программный код. Единственный способ избежать этого — стараться реализовать похожие функции похожими методами во всех компонентах программного кода и оформлять их в едином стиле. Тогда, увидев в каком-либо модуле такой фрагмент кода, программист сможет легко распознать применяемый в данном фрагменте метод или подход.
Особенно важно следовать этой рекомендации при разработке отдельных модулей базы данных или индивидуальных баз данных.
Пожертвуйте производительностью программы, если это сделает ее более понятной (в том числе и в смысле читабельности программного кода) и упростит сопровождение.
Программисты часто состязаются друг с другом, кто придумает более "сжатый" код, разобраться в котором постороннему зачастую просто невозможно. От такого кода в подавляющем большинстве экспертных систем нет никакого проку, поскольку в интерактивных консультирующих системах все равно большая часть времени уходит на диалог с пользователем и обращение к базам данных.
Бучанан также останавливается на проблеме разработки системы-прототипа, называя его условно системой Mark I. Он советует заняться разработкой такого прототипа, как только станут понятными два-три типовых примера (типовых задачи) для проектируемой экспертной системы. Однако действительным самородком в наборе советов является следующий.
Как только встанет вопрос о разработке второго прототипа, выбросите первый в мусорную корзину.
Многие проекты "пошли ко дну" лишь потому, что их авторы не могли избавиться от приверженности к первому варианту реализации собственных идей. В связи с этим возникает и такой вопрос, а когда имеет смысл прекратить отработку первого прототипа. Программисты часто впадают в состояние бесконечного "вылизывания" программного кода, которому все равно уже уготовано место на свалке. Конечно, при разработке второго прототипа нужно учитывать опыт создания первого, но опыт, а не программный код.
Процесс проектирования экспертной системы неразрывно связан с экспериментированием.
Этот принцип не утратил своей актуальности и на сегодняшний день. Тех, кто, прочитав какую-нибудь брошюру под броским названием "Экспертная система за NN часов", доверят ее проектирование первому встречному, ожидает горькое разочарование. Разработка приложения, которое будет успешно работать, требует настойчивости и терпения профессионального программиста, привлечения к работе опытного эксперта в своей области и определенного уровня принуждения со стороны руководства.
Объектно-ориентированные языки
В главе 12 мы уже обращали ваше внимание на то, что формат правил хорошо согласуется с представлением знаний в форме "при выполнении условий Сь ..., С„ выполнить действие А", но менее подходит для описания сложных объектов и отношений между ними. Языки объектно-ориентированного программирования предоставляют в распоряжение программиста альтернативную программную среду для организации знаний в терминах декларативного представления объектов предметной области. Все, связанное с процедурной стороной решения проблем, распределяется между этими объектами, которые в таком случае располагают собственными процедурами и могут общаться друг с другом посредством протоколов передачи сообщений.
Другим приятным аспектом объектно-ориентированного программирования является возможность использования таких стилей представления знаний, которые не встречаются в исчислении предикатов и в порождающих правилах. Вместо "размывания" знаний об объекте предметной области между множеством правил или аксиом, на которые они ссылаются, эти знания концентрируются в едином месте — в программном описании объекта. Эта концентрация является виртуальной в том смысле, что нет необходимости, чтобы вся информация об объекте предметной области хранилась в соответствующем ему программном объекте, но любая команда или запрос к этому объекту может быть реализована только через посылку сообщения этому объекту.
В реальном мире вещей существует множество систем, в которых обмен энергией или информацией может быть представлен через обмен сообщениями между их компьютерными представлениями, и такая связь с технологией моделирования является очень важным достоинством данного подхода (см., например, [McArthur et al, 1986]). Не вызывает сомнений, что моделирование является одним из мощнейших средств решения проблем и что, рассматривая процесс логических рассуждений в контексте сложной системы, его иногда понять значительно легче, чем в контексте применения правил. Объектно-ориентированное программирование интегрирует символические вычисления в операционную среду, базирующуюся на средствах графического интерфейса, — меню, пиктограммы и т.п.
Хотя само по себе оснащение экспертной системы этими средствами и не решает проблему ее прозрачности для пользователя, в руках умелого программиста они позволяют лучше представить пользователю процессы, происходящие в системе (см., например, [Richer andClancey, 1985]).
Основная сложность в использовании средств объектно-ориентированного программирования — уяснить для себя, что именно должен представлять программный объект по отношению к предметной области. В ранних версиях объектно-ориентированных языков, которые были предназначены в основном для разработки программ моделирования, такая проблема не возникала — программные объекты представляли объекты моделируемой системы. Например, при моделировании производственной линии отдельные программные объекты представляли те или иные механизмы этой линии, а сообщения между программными объектами — информационные, энергетические и материальные потоки. Задача программиста серьезно облегчалась тем, что существовало достаточно очевидное соответствие между программными и реальными объектами.
Но для того чтобы внедрить объектно-ориентированный стиль в проектирование экспертных систем, нужно задуматься над тем, как соотнести программные объекты с абстрактными понятиями и категориями предметной области. Объекты должны представлять факты и цели, наборы правил или отдельные гипотезы. Поэтому далеко не очевидно, какими сообщениями должны обмениваться такие объекты и какой смысл должен вкладываться в эти сообщения.
Многое зависит от того, на каком уровне абстракции будет использоваться объектно-ориентированный механизм. Если объекты представляют собой низкоуровневую реализацию определенной схемы формирования суждений, то отпадает необходимость в использовании каких бы то ни было эпистемологических последовательностей. Если же объекты будут видимы и для эксперта в процессе разработки и совершенствования системы, и для пользователя во время эксплуатации системы, то схема отображения понятий и категорий на программные объекты должна быть тщательно продумана.
Общая характеристикинструментальных средств для построения экспертных систем
При разработке практически всех инструментальных средств за основу принимается методология автоматизации проектирования на базе использования прототипов. По отношению к программному обеспечению термин прототип означает "работающую модель программы, которая функционально эквивалентна подмножеству конечного продукта" [Schach, 1993]. Идея состоит в том, чтобы на ранней стадии работы над проектом разработать упрощенную версию конечной программы, которая могла бы послужить доказательством продуктивности основных идей, положенных в основание проекта. Прототип должен быть способен решать какую-либо из нетривиальных задач, характерных для заданной области применения. На основе анализа опыта работы с прототипом разработчики могут уточнить требования к системе в целом и ее Основным функциональным характеристикам. Работоспособность прототипа может послужить очевидным доказательством возможности решения проблем с помощью создаваемой системы еще до того, как на ее разработку будут потрачены значительные средства.
После всестороннего анализа прототип откладывается в сторону и начинается разработка рабочей версии программы, которая должна решать весь комплекс задач, определенных в спецификации проекта. Процесс разработки экспертной системы, как правило, состоит из последовательности отдельных этапов, на которых наращиваются возможности системы, причем каждый из этапов подразделяется на фазы проектирования, реализации, компоновки и тестирования. В результате после каждого этапа наращивания возможностей в распоряжении пользователя имеется система, которая способна справляться со все более сложными вариантами проблемы.
Такая методика проектирования несколько отличается от методики разработки программ других видов. При создании большинства программных продуктов чаще используется другая модель процесса— сначала разрабатывается спецификация продукта, затем выполняется планирование, проектирование компонентов, их реализация, компоновка комплекса и тестирование конечного варианта.
Тот факт, что при разработке экспертных систем есть возможность сначала построить и всесторонне испытать прототип, позволяет избежать множества переделок в процессе создания рабочей версии системы. Но технология последовательного наращивания функциональных возможностей таит в себе и проблему интеграции новых функций с реализованными в предыдущих вариантах. Инструментальные средства разработки экспертных систем и создавались, в первую очередь, с целью преодоления возникающих при этом сложностей на основе модульного представления знаний, которое мы уже обсуждали в главах 5-8.
По своему назначению и функциональным возможностям инструментальные программы, применяемые при проектировании экспертных систем, можно разделить на четыре достаточно больших категории.
(1) Оболочки экспертных систем (expert system shells). Системы этого типа создаются, как правило, на основе какой-нибудь экспертной системы, достаточно хорошо зарекомендовавшей себя на практике. При создании оболочки из системы-прототипа удаляются компоненты, слишком специфичные для области ее непосредственного применения, и оставляются те, которые не имеют узкой специализации. Примером может служить система EMYCIN, созданная на основе прошедшей длительную "обкатку" системы MYCIN. В EMYCIN сохранен интерпретатор и все базовые структуры данных — таблицы знаний и связанный с ними механизм индексации. Оболочка дополнена специальным языком, улучшающим читабельность программ, и средствами поддержки библиотеки типовых случаев и заключений, выполненных по ним экспертной системой. Дальнейшим развитием оболочки EMYCIN явились системы S.1 и М.4, в которых механизм построения цепочки обратных рассуждений, заимствованный в EMYCIN, объединен с фреймоподобной структурой данных и дополнительными средствами управления ходом рассуждений.
(2) Языки программирования высокого уровня. Инструментальные средства этой категории избавляют разработчика от необходимости углубляться в детали реализации системы — способы эффективного распределения памяти, низкоуровневые процедуры доступа и манипулирования данными.
Одним из наиболее известных представителей таких языков является OPS5, о котором уже шла речь в главах 5, 14. Этот язык прост в изучении и предоставляет программисту гораздо более широкие возможности, чем типичные специализированные оболочки. Следует отметить, что большинство подобных языков так и не было доведено до уровня коммерческого продукта и представляет собой скорее инструмент для исследователей.
(3) Среда программирования, поддерживающая несколько парадигм (multiple-paradigm programming environment). Средства этой категории включают несколько программных модулей, что позволяет пользователю комбинировать в процессе разработки экспертной системы разные стили программирования. Среди первых проектов такого рода была исследовательская программа LOOP, которая допускала использование двух типов представления знаний: базирующегося на системе правил и объектно-ориентированного (см. об этой программе в главе 5). На основе этой архитектуры во второй половине 1980-х годов было разработано несколько коммерческих программных продуктов, из которых наибольшую известность получили KEE, KnowledgeCraft и ART. Эти программы предоставляют в распоряжение квалифицированного пользователя множество опций и для последующих разработок, таких как КАРРА и CLIPS, и стали своего рода стандартом. Однако освоить эти языки программистам далеко не так просто, как языки, отнесенные нами к предыдущей категории.
(4) Дополнительные модули. Средства этой категории представляют собой автономные программные модули, предназначенные для выполнения специфических задач в рамках выбранной архитектуры системы решения проблем. Хорошим примером здесь может служить упоминавшийся в главе 15 модуль работы с семантической сетью, использованный в системе VT. Этот модуль позволяет отслеживать связи между значениями ранее установленных и новых параметров проектирования в процессе работы над проектом. Подобные модули управления семантической сетью можно использовать для распространения внесенных изменений на все компоненты системы.
В последующих разделах этой главы мы более подробно рассмотрим перечисленные выше категории.
Практическое освоение инструментальных средств
В рекламном проспекте множества программных средств для проектирования экспертных систем можно встретить утверждение, что данным инструментом "может успешно пользоваться даже непрограммист" или программист, малознакомый с технологиями искусственного интеллекта. В этом разделе мы попытаемся критически рассмотреть, насколько справедливы подобные утверждения, основываясь на имеющихся обзорах и опубликованных сведениях об опыте работы с такого рода программами. Имеющиеся в нашем распоряжении данные свидетельствуют, что, как правило, овладение типовыми инструментальными средствами проектирования экспертных систем не легче, чем овладение новым языком программирования. Даже опытный программист на начальном этапе освоения такой программы допускает ошибки, свойственные только студентам-новичкам, приступившим к изучению обычного программирования.
В работе [Ward and Sleeman, 1987] представлены результаты мониторинга процесса изучения опытными программистами методики работы с оболочкой для проектирования экспертных систем S.1 [Teknowledge, 1985]. Прародителем S.1 является известная система EMYCIN, а дальнейшим развитием — система М.4. Базы знаний в S.1 содержат множество объектов разного назначения — управляющие выражения, классы, типы классов, порождающие правила, иерархии значений и функций. Таким образом, выбранная для S.1 архитектура, с одной стороны, позволила расширить возможности, которыми обладала система EMYCIN, а с другой — весьма усложнила саму систему. Это замечание еще более справедливо в отношении системы М.4 (см. врезку 17.3).
Среда S.1 поддерживает четыре режима работы:
подготовка и редактирование базы знаний;
использование базы знаний для выполнения консультации, т.е. прогон программы;
выявление и устранение ошибок на стадии компиляции;
выявление и устранение ошибок на стадии выполнения.
Как показал опрос, программисты с трудом осваивают методику совместного использования этих режимов в процессе проектирования экспертной системы, хотя все они имеют большой опыт работы и владеют такими распространенными навыками, как работа с файлами, компилирование файлов, выполнение программ, поиск и устранение ошибок.
Те сообщения об ошибках, которые формируются инструментальной средой, несут информации не больше, чем стандартные сообщения об ошибках в большинстве компиляторов обычных языков программирования. По этим сообщениям трудно отличить место возникновения ошибки от места в программном коде, в котором эта ошибка проявилась. Учитывая, что разработка базы данных ведется в режиме постепенного наращивания ее объема (а такая стратегия рекомендуется всеми авторитетными специалистами), переключение с режима на режим в среде разработки должно выполняться как можно проще, поскольку инженеру по знаниям приходится выполнять итеративные процедуры пополнения базы знаний значительно чаще, чем обычному программисту выполнять расширение функций программы.
Анализ опыта освоения этой инструментальной среды также показал, что если программисты отдают предпочтение простейшей стратегии отладки (эта стратегия включает этапы ввода данных, обращения к системе с запросом о значении какого-либо параметра на основе анализа небольшого множества правил и вывода результата), то они сталкиваются с рядом проблем, касающихся методов представления информации и управления поиском. По мере увеличения сложности проектируемой системы — увеличение объема базы знаний, включение в рассмотрение неопределенностей разного рода, включение в алгоритм работы системы дополнительных режимов — стратегия проектирования требует все более тщательной предварительной подготовки. Авторы обзора [Ward and Sleeman, 1987] пришли к выводу, что хотя освоение системы S.1 и не сложнее освоения нового языка программирования уровня PASCAL, но утверждать, что эта система проще, тоже нельзя.
Утверждение, что эту систему могут освоить люди, не имеющие навыков программирования, "не нашло подтверждения на практике", а если уж говорить совсем откровенно, то это не более чем рекламный трюк. Мой собственный опыт наблюдения за аспирантами, которые пользовались такого рода инструментальными системами, полностью согласуется с этими выводами.
В своих аналитических заметках Робинсон [Robinson, 1987] обращает внимание на то, что выбор инструментальной среды разработки экспертной системы представляет собой достаточно сложную задачу по следующим причинам:
большинство развитых сред разработки настолько дороги, что покупать их для проведения сравнительного анализа перед выбором подходящего не по средствам разработчикам;
время, необходимое для освоения навыков работы с системой и выявления ее сильных и слабых сторон, также слишком велико, а потому редко кто может себе позволить проводить сравнение конкурирующих моделей на практике;
терминология, которую применяют в документации изготовители разных систем, существенно отличается, причем это относится даже к понятиям и технологиям, ставшим стандартными в области искусственного интеллекта. Поэтому проводить сопоставление разных моделей по тем сведениям, которые публикуются в технической документации, также достаточно трудно.
Последнее замечание справедливо в отношении большинства программных продуктов, предлагающихся на рынке. Когда же речь идет о программных средствах, связанных с областью искусственного интеллекта, то новизна и необычность терминологии еще более усугубляет проблему. Уже давно в среде специалистов бытует мнение, что сравнение конкурирующих систем одного класса можно выполнять только после тщательного изучения их на практике.
17.3. Правила и процедуры в инструментальной среде М.4
Основным средством представления знаний в оболочке М.4 являются порождающие правила, ориентированные на построение обратной цепочки логического вывода, причем применяется тот же синтаксис, что и в системе EMYCIN (см. главу 1.1), Приведенное ниже правило выбирает болт определенного размера, принимая во внимание ограничения на длину, диаметр и шаг резьбы. Прописными буквами в тексте правила выделены наименования переменных.
If recommended type = bolt and
recommended length = LENGTH and
recommended diameter = DIAMETER and
recommended thread_pitch = PITCH and
fastener(bolt, LENGTH, DIAMETER, PITCH) = BOLT
then recommended fastener = BOLT
Построение прямой цепочки логического вывода моделируется конструкциями whenfound и whencached, которые выполняют функции демонов (см. главу 6). Например, оператор whencached разрешает выполнение определенного действия при установке значения определенного элемента данных. Выполнение такого действия, как правило, включает вызов процедуры, причем на его характер накладывается меньше ограничений, чем на характер действия, специфицированного в правой части порождающего правила в CLIPS. Например, в приведенном ниже фрагменте утверждается, что обнаружен самолет в определенной точке LOC в момент времени TIME, как только при считывании показаний сенсора в момент времени TIME обнаруживается наличие реактивного двигателя или пропеллера, и эти показания согласуются с аналогичными показаниями соседнего сенсора в предыдущий момент времени.
whencached (sensor_reading
( SENSOR, TIME) = SIGNATURE) =
((signature-type (SIGNATURE) = jet or
signature-type (SIGNATURE) = prop)
and TIME -1 = PREVIOUS and cached
( sensor jreading) OTHER, PREVIOUS = SIGNATURE)
and
neighbor (SENSOR) = OTHER and location
(SENSOR) = LOC and do ( set plane_detected ( LOC , TIME ) ) ) .
Насколько этот фрагмент программы читабелен, судить вам.
Процедуры в М.4 имеют синтаксис, весьма напоминающий синтаксис языка программирования С или PASCAL. Например, ниже приведен текст простой процедуры.
procedure ( determine_and_display recs ( FAULT ) ) =
{
f ind_recomendations( FAULT) ;
LIST := listof( recommendations (FAULT) };
COUNT := 1;
while (LIST == [ITEM | REST])
{
display ([COUNT, ". ", ITEM, nl]);
COUNT := COUNT + 1; LIST := REST;
)
В этом фрагменте конструкция LIST == [ITEM (REST] заимствована из языка PROLOG. Она разделяет список LIST на головной элемент ITEM и хвост REST. Читатель может судить по этому фрагменту, насколько просто в среде М.4 программировать процедуры.
Рекомендуемая литература
Каталог экспертных систем, разработанных в 70-х — начале 80-х годов, опубликован в книге [Waterman, 1986, Chapters 27-28]. К сожалению, сейчас этот материал уже устарел. Критический анализ некоторых инструментальных средств для инженерии знаний, разработанных в 80-х годах, можно найти в работе [Laurent et al, 1986]. Обзор современных средств разработки экспертных систем и используемых при этом методологий, в который включены как системы, базирующиеся на правилах, так и более современные, базирующиеся на прецедентах (case-based), и объектно-ориентированные, приведен в работе [Harmon and Hall, 1993].
Читатели могут и самостоятельно сравнить характеристики имеющихся на рынке систем подобного назначения, заглянув на Web-сайты фирм Intellicorp, Teknowledge и Inference Corp. Немало полезной информации можно найти и в разделах FAQ (часто задаваемые вопросы) многочисленных групп новостей, имеющих отношение к проблематике искусственного интеллекта. Перечень ftp-серверов таких разделов можно найти по адресу http://hps.elte/hu/ai-faq.html. Но я не могу гарантировать, что представленная на них информация будет полной и злободневной.
Стиль программирования
В литературе о программировании задач общего назначения часто обсуждается понятие "стиль программирования". Существует огромное множество книг о том, как писать программы, и кажется, что в них можно найти рекомендации на все случаи жизни.
Но эти рекомендации слабо соотносятся со спецификой программирования задач искусственного интеллекта и, в частности, систем, основанных на знаниях. Тот массив программ на языке LISP, который накопился за многолетнюю практику применения этого языка в программировании задач искусственного интеллекта, повергнет в ужас любого студента, проштудировавшего классические труды по структурному программированию. В программах зачастую используются нестандартные способы управления последовательностью выполнения операторов, непредусмотренное никакими канонами динамическое связывание переменных и совершенно "безответственные" манипуляции со структурами данных, такими как списки свойств. Но в последние годы ситуация здесь значительно улучшилась (с точки зрения приверженцев строго структурированного стиля оформления текста программы). Чтобы убедиться в этом, сравните, например, обзоры [Winston and Horn, 1983] и [Winston and Horn, 1981]. Как бы там ни было, но написать хорошую программу на языке LISP — это искусство, которым владеют единицы, хотя тексты большинства самых лучших программ искусственного интеллекта можно демонстрировать студентам в качестве наглядного пособия, как не надо писать программы.
Но, к сожалению, более чем 25-летний опыт совершенствования стиля программирования на LISP не востребуется разработчиками новых языков и инструментальных сред. Для меня, например, остается загадкой, что же представляет собой хороший стиль программирования по отношению к языку (и среде) КЕЕ. Мне приходилось наблюдать, как инженеры по знаниям, много лет проработавшие с языками структурного программирования, буквально падали в обморок от мешанины подключения процедур, комбинированных методов и активных значений в КЕЕ-программах. Это не следует рассматривать как серьезную критику в адрес функциональных возможностей языка, а скорее как констатацию того факта, что любые сложные инструментальные средства нуждаются в адекватной методологии пользования ими. Единственным исключением, на мой взгляд, является язык OPS5, о методике использования которого написана прекрасная книга [Brownston et al, 1985].
Проведите сравнительный анализ возможностей инструментальных
1. Проведите сравнительный анализ возможностей инструментальных средств разных классов — оболочек, языков программирования высокого уровня и многофункциональных сред— применительно к проектированию экспертных систем для задач классификации и проектирования.
2. Почему бывает желательно строить рассуждения в разных контекстах и почему некоторые контексты оказываются "отравленными"?
3. Насколько сказываются на конечном варианте проектируемой экспертной системы характеристики начального прототипа?
4. Критически проанализируйте характеристики той инструментальной среды разработки экспертных систем, с которой вы лучше всего знакомы. Анализ должен включать следующие моменты:
I) детальное рассмотрение функциональных возможностей среды, наиболее привлекательных с вашей точки зрения; каким образом эти возможности облегчают проектирование?
II) детальное рассмотрение тех характеристик среды, которые вы считаете неудачными; почему, на ваш взгляд, эти характеристики затрудняют работу?
III) перечень дополнительных возможностей, которые, по-вашему, имеет смысл реализовать в этой среде разработки.
В последнем разделе анализа выделите те дополнительные функции, которые довольно легко встроить в имеющийся вариант, и те, которые потребуют его значительной переделки или приведут к снижению производительности существующего варианта.
5. Попробуйте сформулировать рекомендации, касающиеся инженерии знаний, основываясь на собственном опыте, например на опыте выполнения упражнений из предыдущих глав этой книги. (Только не нужно приводить вариации Законов Мерфи.)
6. Постарайтесь задокументировать процесс освоения новой для вас инструментальной среды. Попробуйте классифицировать те трудности, с которыми вам довелось столкнуться. Например, можно начать с выделения проблем следующих видов.
Проблема управления режимами работы среды — насколько болезненным был процесс освоения пользовательского интерфейса таких компонентов, как редактор, отладчик, интерпретатор и т.п.
Проблемы освоения синтаксиса языка — как быстро вы освоились с правилами расстановки скобок, знаков препинания и т.п.
Концептуальные проблемы. Сложности в освоении процедурных или декларативных конструкций. Например, методики работы с демонами, контекстами и т.п.
7. В этом примере демонстрируется, как в языке CLIPS организована интеграция правил и объектов. Основной механизм взаимодействия правил и объектов состоит в том, что действия, специфицированные в правилах, посылают сообщения экземпляру класса.
Предположим, например, что мы имеем дело с экспертной системой, которая дает пользователю советы, касающиеся покупки музыкальных инструментов. Пусть это будет гитара, причем ее характеристики представлены содержимым слотов. Тогда в этой экспертной системе должны быть правила, подобные приведенному ниже.
(defrule describe-guitar
(option ?guitar) =>
(send (symbol-to-instance-name ?guitar) show) )
В этом правиле show — метод класса guitar, который выводит на экран содержимое слота экземпляра класса в нужном формате. Определение класса guitar может иметь следующий вид:
(defclass guitar (is-a USER) (slot make)
(slot model) (slot wood) (slot pickups))
Метод show этого класса можно представить следующим образом:
(definessage-handler guitar show ()
(printout t
"The " ?self:make " " ?self:model "
is a " ?self:wood " guitar with " ?selfspickups " pickups.")
;; ?self:make " " ?self:model " это "
;; ?self:wood " гитара с "
;; ?self:pickups " звукоснимателем.")
)
Для экземпляра этого класса
(GibSG of guitar
(make Gibson)
(model SG)
(wood mahogany)
(pickups humbucking) )
метод выведет сообщение
"The Gibson SG is a mahogany guitar
with humbucking pickups."
Включите подобную функцию в одну из программ-советчиков, которые предлагалось разработать в упражнениях предыдущих глав, в частности в упр. 7 главы 14 и в упр. 4 главы 16.
8. Разработайте два правила, которые будут удалять все действия и факты, связанные с "отравленным" контекстом, в примере, представленном в разделе 17.3.5. Почему таких правил должно быть два?
Выбор подходящего инструментария для разработки экспертной системы
В работе [Hayes-Roth et al, 1983, Chapter 1] собраны рекомендации по выбору подходящих инструментальных средств построения экспертной системы. В основу рекомендаций положено сопоставление характеристик задач, решаемых проектируемой экспертной системой, и необходимых функциональных возможностей инструментального комплекса.
Общность. Выбрать инструмент со степенью общности, не превышающей той, которая необходима для решения данной задачи. Например, если для данной задачи сложный механизм управления не является жизненно необходимым, использовать его не только расточительно, но и нежелательно.
Выбор. Выбор инструментария должен определяться в первую очередь характеристиками задачи, решаемой экспертной системой, а не другими привходящими обстоятельствами, например тем, что какой-то инструмент уже есть под рукой или знаком вам лучше остальных. Авторы цитируемой работы затем развили свою мысль, опираясь на классификацию экспертных систем, о которой речь пойдет ниже.
Быстрота. Если успех проекта зависит от срока разработки, то следует выбирать инструментальную среду со встроенными средствами формирования пояснений и развитым пользовательским интерфейсом. Разработка интерфейса — одна из наиболее трудоемких стадий проектирования системы, и чем большую часть этой работы можно переложить на среду разработки, тем быстрее будет завершен проект.
Испытание. Постарайтесь как можно быстрее провести испытания новой для вас инструментальной среды. Без сомнения, это полезный совет, однако открытым остается вопрос о том, как определить степень совершенства инструмента по результатам испытаний.
Важнейшим для выбора инструментальной среды является вопрос о способе определения характеристик проблемы, решаемой проектируемой экспертной системой. Этот вопрос обсуждается в работе [Stefik et al, 1983], где предлагается схема анализа, основанная на свойствах пространства поиска решения. Я позволил себе несколько обобщить предлагаемые авторами работы категории проблем и свел 11 Категорий к четырем, хотя основные принципы классификации остались прежними.
(1) Малое пространство решений, надежные данные и знания. Предполагается, что количество альтернатив, которые следует принимать во внимание при поиске решения, невелико и что все данные достоверны, а истинность правил не вызывает сомнений. В таком случае возможно выполнять исчерпывающий поиск в пространстве решений и при необходимости организовать возврат с прослеживанием в обратном порядке. Для решения проблем этой группы можно воспользоваться готовыми решениями, т.е. ранее созданной оболочкой на базе экспертной системы, решавшей аналогичную проблему в другой предметной области. Распространено мнение, что такой подход позволяет получить удовлетворительное, а не оптимальное решение проблемы, т.е. достаточно хорошее, а не лучшее решение. Учтите, что попытка отыскать оптимальное решение неизбежно сопряжена с перебором нескольких вариантов, что таит в себе опасность "комбинаторного взрыва".
(2) Ненадежные данные или знания. Если данные и/или знания ненадежны, т.е. существует опасность, что вводимые в систему данные недостоверны, а правила в базе знаний неоднозначны, то в экспертной системе нужно комбинировать информацию от нескольких источников и использовать в какой-либо форме логику неточных рассуждений. Авторы цитируемой работы весьма мудро решили воздержаться от конкретных рекомендаций, какой именно формализм неточных рассуждений следует выбрать, но круг кандидатов в любом случае довольно ограничен — формализм коэффициентов уверенности (см. главу 3) или нечеткой логики (см. главу 9). Обсуждение альтернативных методов, таких как использование функций доверия (belief function) и обновляемых оценок по Байесу (Bayesian belief updating), мы отложим до главы 21.
(3) Большое, но факторизуемое пространство решений. В литературе можно найти два варианта толкования термина "факторизуемый". Пространство поиска можно назвать факторизуемым, если существует "правило исключения", которое помогает уменьшить размер пространства на ранней стадии решения проблемы [Stefik et al, 1983, p. 99]. Есть и другое определение — пространство поиска является факторизуемым, если возможно разделить его на несколько независимых подпространств, которые можно обрабатывать по отдельности, причем для разных подпространств могут быть использованы и разные множества правил или отдельные подмножества одного и того же множества правил [Nilsson, 1980, р. 37]. Обычно такое разбиение выполняется на уровне решаемой проблемы, т.е.
большая общая проблема разбивается на несколько более мелких. Успех в достижении главной цели, таким образом, оценивается по совокупности успехов в достижении более или менее независимых подцелей. .Если система потерпит неудачу в достижении одной из подцелей, то это будет означать неудачу и решения проблемы в целом. В любом случае для решения проблем такого класса наиболее предпочтительным является метод порождения и проверки (generate-and-test). Этот метод позволяет "обрезать" ветви, уводящие нас от решения, и разделить большое пространство решений на подпространства.
(4) Большое нефакторизуемое пространство решений. Пространство решений может оказаться и нефакторизуемым, в каком бы смысле мы не трактовали этот термин. Очень часто оказывается, что проблема проектирования допускает выработку частного решения какого-либо компонента только в контексте всего проекта. При сборке головоломки нельзя предсказать, найдено ли верное решение, пока последний элемент мозаики не станет на свое место. Общий подход к работе в большом пространстве поиска состоит в том, чтобы последовательно рассматривать его на разных уровнях абстракции, т.е. использовать варианты описания пространства с разным уровнем учета деталей. Решение проблемы таким методом часто называют нисходящим уточнением (top-down refinement) (см. об этом в главе 14). Применение метода нисходящего уточнения требует исключить, по возможности, обратное прослеживание между уровнями, реализация которого требует значительных вычислительных ресурсов. Но это срабатывает только в случае, если между уровнями нет тесного взаимодействия. Как было показано в главе 15, эффективной стратегией решения такого рода задач является стратегия наименьшего принуждения (least commitment), подкрепленная адекватным механизмом разрешения конфликтов.
В книге [Hayes-Roth et al, 1983] проблема выбора инструментальных средств представлена в терминах схемы рис. 17.2. Выяснив характеристики проблемы, решаемой проектируемой экспертной системой, можно определиться со свойствами пространства решений, которые перечислены выше.
Затем они рассматриваются совместно с предполагаемыми характеристиками разрабатываемой системы — характеристиками порождающих правил, прямой цепочки вывода или возможностями формирования пояснений, — и вырабатываются желаемые характеристики инструментальной среды. Последние и позволяют подобрать нужную модель инструментальной среды. Нужно сказать, что все это прекрасно выглядит на картинке, но очень сложно реализуется на практике, хотя вряд ли кто-нибудь будет спорить с тем, что такой подход более логичен, чем какой-либо другой. Как показывает практика, большинство разработчиков явно или неявно следует именно такому подходу при создании экспертных систем.
Рис. 17.2. Схема выбора инструментальной среды проектирования экспертной системы
Например, разработчики экспертной системы COMPASS, описанной в главе 10, следующим образом аргументировали свое решение выбрать для выполнения проекта инструментальную среду КЕЕ.
Эта среда предоставляет в распоряжение разработчика большее разнообразие парадигм программирования, чем какая-либо другая.
Среда оснащена лучшими средствами интерфейса и более развитыми средствами редактирования.
Поддержка этой среды со стороны фирмы-производителя организована лучше, чем у ее конкурентов.
Проанализировав возможные варианты, разработчики остановились на выборе в качестве основного инструментального средства компонента COTS среды КЕЕ.
При выборе инструментальной среды немаловажное значение имеет и то, насколько проста среда в обращении и как быстро проектировщики экспертной системы смогут овладеть методикой работы в этой среде, какую поддержку в этом готова оказать им фирма-изготовитель среды, и, конечно же, цена этого программного продукта.