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

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

Экспертные игры, как подкласс АСИЗ (п. 1.5), имеют следующие отличительные признаки [34,64]:

• БАЗА СВЕДЕНИЙ О ПРОБЛЕМНОЙ ОБЛАСТИ содержит примеры проблемных ситуаций. Каждый пример состоит из описания проблемной ситуации и правильного решения.
• СЦЕНАРИЙ ИЗВЛЕЧЕНИЙ ЗНАНИЙ задается правилами компьютерной игры. Для эксперта правила определяют игровую цель и средства ее достижения. С точки зрения базовой классификации сценариев извлечения знаний экспертные игры реализуют принцип заочной консультации (п.п. 1.4, 1.5).
• БЛОК АНАЛИЗА ПРОТОКОЛОВ состоит из подсистемы предварительного анализа протоколов и подсистемы выявления знаний. Первая подсистема предназначена для выявления продуктивной части протокола игровых действий эксперта; при этом существенно используются правила игры. Вторая подсистема преобразует протокол (или его часть) в формальные структуры знаний в соответствии с гипотезами о стиле рассуждений эксперта в ходе игры.

Рассмотрим конкретные версии экспертных игр, реализованные в системе КАПРИЗ [65].

6.1 Экспертная игра "Черный ящик"

Игра "Черный ящик" [7] была первой нетривиальной реализацией экспертных игр. Именно эта игра во многом определила общую методологию игровых методов опроса эксперта.

6.1.1 Правила игры

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

Формально i+1-й тур игры может начаться, если в i-ом туре выполняется условие

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

Если в i-ом туре игры эксперт уменьшил некоторую ставку на E очков, то на его счет возвращается только EQ^i-1 очков, где Q - знаменатель прогрессии, 0 < Q < 1.

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

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

В первой реализации игры минимальный размер платы за факт (параметр L) устанавливался в размере 100 очков. Стартовый капитал эксперта (параметр D) составлял 950 очков. Коэффициент прогрессии Q = 0.66.

6.1.2 Анализ протоколов

В игре "Черный ящик" протокол фактически представляет собой матрицу ставок ||С(р,j)||, где р ∈ Р, j = 1, ..., K - номер тура игры. Для удобства расчетов необходимо дополнительно иметь величины:
 D(j) - неизрасходованный остаток очков в j-ом туре игры, и

F(j) =	Σ	С(p,j) - сумма всех ставок в j-ом туре игры.
	р ∈ Р

ОСНОВНАЯ ГИПОТЕЗА метода анализа протоколов игры "Черный ящик" состоит в том, что эксперт, корректируя ставки в i-ом туре игры, учитывает все известные к этому моменту факты описания. Соответственно программная реализация должна поддерживать эту гипотезу и сохранять на экране факты Ф₁, ..., Ф_i.

6.1.2.1 Предварительный анализ протоколов

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

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

1-й факт - за	0	очков
2-й факт - за	L - LQ	очков
...
i-й факт - за	L - LQi-1	очков
...

Сознательно реализовать стратегию покупки фактов можно, например, с использованием всего лишь двух решений: a и b. При этом протокол имеет вид:

                     1  2  3  4  5  6  7 ...
                ...
                 a   L  0  L  0  L  0  L ...
                ...
                 b   0  L  0  L  0  L  0 ...
                ...

Другими словами, в игре "Черный ящик" самое неблагоприятное поведение эксперта состоит в том, что в первых турах игры он расчетливо "покупает" факты, не вкладывая в истраченные очки смысл ставок на выигрыш. Только собрав достаточное количество фактов, эксперт в последнем туре "включает" свои знания и делает единственную окончательную ставку. В общем случае неблагоприятная стратегия поведения проявляется в виде свойства функции F(j): F(j) = L для j < K. График такой функции имеет вид:

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

Таким образом, первая обязанность когнитолога состоит в том, чтобы определить H - номер тура игры, начиная с которого эксперт как бы отказывается от оптимальной стратегии и начинает существенно использовать свои знания. Фактически, когнитолог должен выбрать одно из чисел 1, ..., K-1. Эту задачу удобно решать в режиме меню с помощью графика функции F(j), как показано на рисунке:

Определившись с номером H, когнитологу необходимо более детально рассмотреть элементы множества решений. Если исходить из основной гипотезы, то в протоколе рекомендуется оставить только такие решения р, для которых функция f(j) = С(р,j) на множестве [H,K] имеет либо унимодальный, либо неубывающий характер:

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

6.1.2.2 Выявление знаний

При попытке объяснить игровые действия эксперта открывается следующая картина. Вот, скажем, в третьем туре игры (H ≤ 3) эксперт, зная факты Ф₁, Ф₂ и Ф₃, ставил некоторую сумму очков на решение р; в дальнейшем ставка на р уменьшалась. Можно предположить, что эксперт неявно пытался использовать правило продукции вида:

В общем случае в посылках неполной продукции участвуют факты Ф₁, ..., Ф_n, где

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

Окончательно правило продукции для решения р имеет вид:

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

В приведенных соображениях по восстановлению продукционных правил неявно участвует предположение о значительном объеме множества решений. В этом случае, делая ставки, эксперт не может идти путем только лишь отсеивания решений, несовместимых с уже известным набором фактов. Он вынужден полагаться на свои ассоциативные связи, намечая посредством ставок область поиска решения. Именно вынужденная нацеленность на самые вероятные решения и позволяет точно формулировать правую часть продукционного правила. Такое правило будет сохранять свою силу при всех модификациях множества решений. Вместе с тем, в рамках, выделенных ставками решений, эксперт все-таки использует метод отсеивания, что проявляется в форме аннулирования ставок. Скажем, в i-ом туре, зная факты Ф₁, ..., Ф_i, эксперт снял ставку с решения р. Это означает, что перечисленные факты вкупе с решением р образуют ЗАПРЕТ(Ф₁, ..., Ф_i, р).

6.1.2.3 Модификации игры

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

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

В связи с этим приведем одно вспомогательное утверждение.

Лемма 6.1
Если числа m, n, g, c₁, ..., c_n удовлетворяют условиям:
1. 0 < m ≤ n,
2. 0 < c_j (j = 1, ..., m),
3. 0 ≤ c_j (j = m+1, ..., n),
4. c₁ + ... + c_n < gc_j (j = 1, ..., m),
то m < g.

Доказательство. Суммируя левые и правые части неравенств 4, имеем:

Предположим, что в последнем, K-ом туре игры из всех решений ненулевые ставки сделаны только на р₁, ..., р_l. Обозначим: c₁ = C(р₁,K), ..., c_l = C(p_l,K). Фактически эксперт заявил, что спрятанное решение р является одним из р₁, ..., р_l. Если это заявление соответствует действительности, то было бы обидно не получить призовых очков только потому, что

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

Нетрудно убедиться, что эти неравенства эквивалентны следующим:

Как следует из леммы 6.1 (при m = l, n = l + 1, g = 2), в этом случае m < 2, то есть l = 1.

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

Итак, в распоряжении когнитолога имеются следующие параметры:
D - начальный ресурс очков;
L - минимальный размер платы за факт;
Q - знаменатель прогрессии;
G - кратность увеличения ставки.

Рассмотрим вопрос о возможном количестве туров игры.

Во-первых, прогрессивный налог на возвращаемую сумму очков фактически ограничивает количество туров игры. Так, при Q = 0.7 уже в восьмом туре эксперту возвращается менее 10% очков, и процесс уменьшения ставок становится практически бессмысленным.

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

Зная параметры игры, рассчитать максимальный номер тура K не составляет труда. Так, для параметров первой реализации игры (D = 950, L = 100, G = 2, Q = 0.66) эксперт теоретически может выиграть не далее, чем в седьмом туре игры.

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

Особого разговора заслуживает процедура предъявления очередного факта. Простейший вариант ее реализации состоит в том, что эксперт нажимает клавишу ДАЙ-СЛЕДУЮЩИЙ-ФАКТ. Однако такое решение располагает к выработке оптимальной стратегии поведения, так как явно наводит на мысль о наличии у противника определенного порядка предъявления фактов.

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

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

Извлечение знаний с помощью экспертной игры "Черный ящик" отводит когнитологу активную роль. Характерно, что от его решений по выбору способа интерпретации протокола зависит конечный итог извлечения знаний.

6.2 Экспертная игра "Буриме"

В игре "Черный ящик" эксперт фактически выполняет обязанности машины вывода. Он анализирует внешние проявления искомого решения и вынужденно раскрывает ход своих рассуждений. Можно считать, что эксперт имитирует прямой вывод на множестве продукций. При таком взгляде на положение вещей интерес представляет игра "Буриме" [9], в которой эксперт рассуждает в направлении от решения к фактам, то есть имитирует обратный вывод.

Как и ранее, для описания проблемных ситуаций в игре "Буриме" используется язык признаковых моделей. В качестве дополнительной структуры данных в игре используется модель проблемной области. Средства просмотра позволяют выбирать из модели отдельные факты.

6.2.1 Правила игры

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

По ходу игры эксперт предпринимает попытки отгадать неизвестный ему набор фактов. Каждая попытка представляет собой выборку фактов из модели проблемной области. Ответ эксперта считается законченным, когда в выборку попадают ровно N_D фактов. Компьютер сравнивает полученную выборку и задуманное им описание, после чего сообщает эксперту краткую сводку "точных попаданий". Например: "Вы угадали 3 факта. Попытайтесь еще раз." либо "Вы угадали все N_D фактов". В последнем случае игра заканчивается и на "банковский счет" эксперта переводится некоторая призовая сумма очков.

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

6.2.2 Анализ протоколов

В игре "Буриме" протокол представляет собой древовидную структуру описаний. Корнем дерева является описание Z₁, построенное в первой попытке. В общем случае непосредственным предком описания Z_i (1 < i) является описание Z, присутствовавшее на экране в начале построения Z_i. Пример структуры протокола приведен на рисунке:

Помимо структуры описаний, в протоколе необходимо иметь задуманный компьютером набор фактов Z_и, что позволяет вычислять количество совпадений для любого описания Z:

6.2.2.1 Подход к выявлению знаний

Метод выявления знаний из протоколов игры "Буриме" основывается на трех гипотезах, фиксирующих способ представления знаний и приемы рассуждений эксперта.

Гипотеза 6.2
Каждому описанию соответствует дерево вывода в некоторой продукционной системе. Например, описанию { Ф1, Ф2, Ф3, Ф4, Ф5, Ф6 } может отвечать дерево вывода

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

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

Гипотеза 6.4.
Новое описание Z_j, как правило, генерируется из базового описания Z_i посредством замены одного из его поддеревьев. Иллюстрация этого принципа приведена на рисунке.

Оговорка "как правило" означает, что для некоторых переходов гипотеза 6.4 может и не выполняться, однако это обстоятельство необходимо мотивировать.

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

6.2.2.2 Предварительный анализ протоколов

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

Содержание игровой задачи эксперта подсказывает подходы к выделению компонент. Приведем некоторые из них.
1. Из дерева описаний имеет смысл исключить вершины Z, для которых и(Z) = 0.
2. Из дерева описаний можно исключить ребра (Z_i,Z_j), для которых и(Z_i) = и(Z_j) = 0.
3. Из дерева описаний можно исключить ребра (Z_i,Z_j), для которых Z_i ∩ Z_j = ∅.

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

В ходе предварительного анализа когнитолог должен рассмотреть возможность объединения пары описаний в одно общее описание. Если, например, протокол имеет вид:

Особого внимания заслуживает задача когнитолога по линеаризации компонент связности. Поясним эту задачу на примере. Допустим, что некоторая компонента имеет вид

Если предположить, что переход Z₂ → Z₃ объясняется преобразованием дерева вывода (гипотеза 6.4), то обратное преобразование деревьев способно объяснить переход Z₃ → Z₂. В связи с этим, исходное дерево (по крайней мере теоретически) можно преобразовать к виду

Повторяя рассуждения для перехода Z₃ → Z₄, исходную структуру можно свести к окончательному виду линейной последовательности описаний

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

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

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

6.2.2.3 Метод восстановления И/ИЛИ-дерева

Выявление формальных структур знаний основано на эвристической процедуре восстановления И/ИЛИ-деревьев специального вида. Процедура является рекурсивной и использует в качестве исходных данных последовательность описаний

Внешняя (корневая) структура искомого И/ИЛИ-дерева может проявляться в одном из трех видов: И-дерево, ИЛИ-дерево, ALT-дерево.

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

Дальнейшее изложение метода построим в соответствии со схемой вычислений.

Корректное определение рекурсивной процедуры предусматривает отдельную обработку частных случаев исходных данных. В связи с этим, интерес представляет вырожденный случай последовательности - единичное описание { Ф₁, ..., Ф_q }. Если q = 1, то, в соответствии с гипотезой 6.3, результатом восстановления является терминальная вершина дерева с меткой Ф₁. Если q > 1, то результатом восстановления является И-дерево

Согласно гипотезе 6.2, каждому описанию Z_i соответствует некоторое дерево вывода T_i. Предположим, что во всех деревьях T_i (i = 1, ..., k) для окончательного вывода искомого решения используется одна и та же продукция П. Обозначим m - количество посылок этой продукции.

Существование общей продукции П позволяет разбить каждое описание Z_i ровно на m непустых, непересекающихся подмножеств:

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

Обозначим S_i - разбиение { S_i,1, ..., S_i,m }. В соответствии с гипотезой 6.4, переход от описания Z_i к описанию Z_i+1 возможен лишь тогда, когда выполняется

Условие 6.6
||S_i|| = ||S_i+1|| = m
||S_i ∩ S_i+1|| = m - 1     (i = 1, ..., k-1).

Другими словами, свойство 6.6 означает, что множества S_i и S_i+1 содержат равное количество элементов и отличаются ровно по одному из них. Не ограничивая общности, можно считать, что переход от Z_i к Z_i+1 заключается в замене подмножества фактов S_i,j на S_i+1,j, где j = j(i).

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

Задача 6.7 (Задача разбиения)
Дано. Последовательность множеств Z₁, ..., Z_k   (k > 1).
Требуется. Найти число m и разбиения S_i множеств Z_i, удовлетворяющие условию 6.6.

Тривиальным решением задачи 6.7 является: m = 1, S_i = { Z_i } ( i = 1, ..., k). В общем случае задача не имеет единственного решения, поэтому интерес представляет решение модифицированной задачи разбиения.

Задача 6.8 (Модифицированная задача разбиения)
Дано. Последовательность множеств Z₁, ..., Z_k   (k > 1).
Требуется. Найти максимальное число m и разбиения S_i множеств Z_i, удовлетворяющие условию 6.6.

Нетрудно убедиться, что модифицированная задача имеет единственное решение. Более того, любое покрытие V_i, являющееся решением задачи 6.7, раскладывается по элементам покрытия S_i, полученного из решения задачи 6.8. Более точно:

Если v ∈ Vi, то v =	∪	s.
	s ⊂ v
	s ∈ Si

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

Алгоритм решения задачи 6.8 основывается на построении бинарных отношений на описаниях Z_i. Элементы, связанные этим отношением, относятся к одному подмножеству разбиения S_i. Предварительно введем альтернативное представление последовательности описаний в виде совокупности множеств:
I(Z₁) = { Z₂ },    I(Z₂) = { Z₁, Z₃},    ...,    I(Z_k-1) = { Z_k-2, Z_k-1 },   I(Z_k) = { Z_k-1 }.

Определение 6.9
Элементы a и b множества Z_i связаны отношением SML_i(a,b), если
 либо {a,b} ⊂ Z_i \ Z для некоторого Z из I(Z_i),
 либо SML_j,*(a,b) для некоторого Z_j из I(Z_i).

Первый вариант определения позволяет сразу выявить некоторые пары элементов, связанные искомыми отношениями. Второй вариант позволяет распространить найденные связки на соседние описания. Процесс построения отношений заканчивается, когда посредством распространения не удается выявить ни одной новой пары элементов, связанных отношениями SML_i,*. Искомые разбиения S_i представляют собой классы эквивалентности отношений SML_i,*, при этом m = ||S_i||.

До сих пор мы опирались на предположение о существовании общей продукции П. Однако это не всегда верно. В соответствии с гипотезой 6.3, решение задачи 6.8 следует считать успешным, если m > 1. Соответственно, решение задачи 6.8 следует считать неуспешным, если m = 1. С этих позиций любую последовательность описаний можно квалифицировать либо как допускающую, либо как недопускающую свертку.

В случае успешного решения, зная разбиения S_i, можно восстановить внешнюю структуру в виде И-дерева, в котором Д_j (j = 1, ..., m) есть И/ИЛИ-дерево для описаний S_1,j, ..., S_k,j. Таким образом, восстановление структуры И/ИЛИ-дерева по исходной последовательности Z₁, ..., Z_k сводится к восстановлению И/ИЛИ-деревьев по описаниям S_1,j, ..., S_k,j. Однако, прежде чем выполнить рекурсивные обращения, в этих последовательностях необходимо оставить по одному вхождению от каждой группы одинаковых смежных описаний. В результате чистки очередная j-ая последовательность приводится к виду Q₁, ..., Q_r (r ≤ k).

Рассмотрим вариант неуспешного решения задачи 6.8. Под этот случай, в частности, подпадают все последовательности Q₁, ..., Q_r. Поскольку построение общего И-дерева оказывается невозможным, имеет смысл отказаться от гипотезы 6.4 для некоторых пар соседних описаний. Другими словами, должна быть решена

Задача 6.10 (Задача рассечения)
Дано. Последовательность множеств Z₁, ..., Z_k (k > 1).
Требуется. Найти числа n и k(1), ..., k(n-1) такие, что подпоследовательности

    6.10(1)    Z1       , ..., Zk(1)   (1     ≤ k(1)),
    6.10(2)    Zk(1)+1  , ..., Zk(2)   (k(1)  < k(2)),
    ...
    6.10(n)    Zk(n-1)+1, ..., Zk      (k(n-1) < k  )

В общем случае задача 6.10 решается неоднозначно. Тривиальным, но абсолютно неинтересным решением является рассечение на одиночные описания (n = k). В связи с этим имеет смысл ужесточить требования к решению.

Задача 6.11 (Модифицированная задача рассечения)
Дано. Последовательность множеств Z₁, ..., Z_k (k > 1).
Требуется. Найти минимальное число n и числа числа k(1), ..., k(n-1) такие, что подпоследовательности 6.10(1), ..., 6.10(n) допускают свертку.

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

Например, последовательность

В общем случае алгоритм решения задачи 6.11 вычисляет N способов рассечения исходной последовательности описаний на n подпоследовательностей. Алгоритм основывается на существовании неперекрывающихся зон разрывов исходной последовательности. Формально зоны определяются парами чисел:

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

Этап 1.	Считаем K0 = 0. Kn = Kn-1 + Fmax(ZK(n-1)+1, ..., Zk), Этап заканчивается, когда Kn = k.
Этап 2.	Считаем Hn = k. Hi = Hi+1 - Fmax(ZHi+1, ..., Z1) для i = n-1, ..., 1

По результатам решения задачи 6.11 искомое И/ИЛИ-дерево восстанавливается одним из двух способов.

Если N = 1, то И/ИЛИ-дерево имеет вид:

(Можно считать, что ИЛИ-дерево представляет собой структуру первого и единственного способа рассечения, причем постановка задачи 6.11 гарантирует успешное восстановление структуры И-дерева для каждой подпоследовательности 6.10(i).)

Если N > 1, то внешняя структура И/ИЛИ-дерева имеет вид

В заключении приведем пример восстановления И/ИЛИ-дерева для последовательности

Результирующее дерево имеет вид

6.2.2.4 Выявление знаний

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

Функциональные возможности редактора обеспечивают:

• наглядное представление И/ИЛИ-дерева;
• уточнение структуры И/ИЛИ-дерева;
• конкретизацию промежуточных вершин;
• документирование выявленных продукций.

Редактор берет на себя заботы, связанные с обработкой ALT-вершин. Такой подход оказывается особенно полезным, когда в исходном дереве имеется соподчиненность ALT-вершин:

С точки зрения программной реализации каждая ALT-вершина представляет собой самостоятельный объект, содержащий указатель на текущий вариант дочернего ИЛИ-дерева. При инициализации объектов, указатели получают некоторые начальные значения. В дальнейшем, по ходу уточнения структуры дерева, значения указателей могут изменяться. Редактор поддерживает на экране только текущую структуру И/ИЛИ-дерева. Сами ALT-вершины на экран не выводятся, однако ИЛИ-вершины, допускающие альтернативные реализации, выделяются на экране значком "+" (или иным способом).

Так, для примера, завершающего предыдущий раздел, восстановленная структура предъявляется пользователю либо в виде:

Вершины ИЛИ+ можно рассматривать как элементы меню, посредством которых пользователь выбирает вариант реализации ALT-вершин, изменяя, таким образом, структуру И/ИЛИ-дерева. Конечная цель таких преобразований состоит в том, чтобы подобрать версию И/ИЛИ-дерева, поддающуюся интерпретации.

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

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

В принципе, задачу именования можно было бы ограничить только ИЛИ-вершинами, считая, что И-вершины наследуют названия своих непосредственных предков. При этом мы невольно постулируем 100% качество И/ИЛИ-дерева, чего на самом деле ожидать не приходится. Иное дело, что при конкретизации И-вершин было бы удобно просто сослаться на имя ее предка.

По результатам уточнения структуры и конкретизации вершин в И/ИЛИ-дереве появляются поименованные И-вершины с полным спектром поименованных дочерних вершин. Такого рода И-вершины естественным образом записываются в виде продукций на языке представления знаний. В первой реализации игры "Буриме" для записи продукций использовался входной язык системы ФИАКР.

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

Рассмотрим подробнее вопрос о выборе вариантов для ALT-вершин. Теоретически последовательность описаний может быть произвольной. В данном случае нас будут интересовать последовательности следующей структуры:

Если Z_a = Z_b, то каждая ALT-вершина, представленная в общем И/ИЛИ-дереве, имеет своего двойника. Естественно считать, что выбор варианта реализации одной ALT-вершины должен автоматически изменять вариант реализации ее двойника. Таким образом, структура последовательности, будучи деревом по форме предъявления, на самом деле, имеет более общий вид ациклического графа. С этой точки зрения интерес представляет возможность неполного совпадения вариантов ALT-вершин. Покажем, что такая ситуация возможна. С этой целью рассмотрим две последовательности описаний.
  Z_a = {c,d,e,f}, {c,g,h,p}, {c,g,q,t}, {u,v,q,t}.
  Z_b = {c,d,e,f}, {u,v,q,f}, {u,v,h,p}, {c,g,h,p}.
Структуры соответственно первой и второй последовательностей имеют вид:

Если закодировать варианты реализации ALT-вершин утверждениями V₁, V₂, V₃, V₄, то обе структуры, представленные в рамках одного дерева, можно рассматривать как систему альтернатив: < V₁, V₂, V₃ >, < V₁, V₄ > .

Итак, совокупность ALT-вершин следует рассматривать как систему альтернатив общего вида. Сделанный вывод определяет алгоритм перестройки текущего И/ИЛИ-дерева в связи с выбором нового варианта реализации некоторой ALT-вершины.

6.3 Экспертная игра "Угадай-ка"

Извлечение знаний посредством экспертных игр отводит когнитологу весьма активную роль. Самая трудная его задача состоит в том, чтобы правильно оценить мотивы поведения эксперта. По-видимому, полностью снять с когнитолога эту заботу никогда не удастся, но можно придумать такие правила игры, при которых сложность его задачи упростится до минимума. В экспертной игре "Угадай-ка" [10] выбор когнитолога ограничивается всего двумя вариантами интерпретации протоколов.

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

6.3.1 Правила игры

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

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

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

Алгоритм вычисления q(i) исходит из того, что эксперт существенно использует свойство однозначности атрибутов и не задает лишних вопросов. Следовательно, выяснить описание примера можно не более, чем за F - A туров игры, и

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

6.3.2 Анализ протоколов

Каждое вычеркнутое решение можно однозначно связать с последними на данный момент результатами проверки. Поэтому протокол игры представляет собой последовательность троек < Ф_i, S_i, P_i > (i = 1, ..., T), где
Ф_i - факт, предъявленный экспертом в i-м туре игры,
S_i - результат проверки факта Ф (ДА или НЕТ),
P_i - множество решений, вычеркнутых экспертом по результатам предъявления и проверки. ||P_T|| = 1, P_i ∩ P_j = ∅ при i ≠ j.

Учитывая однозначность атрибутов, приведем результаты проверки фактов к общепринятым формулам исчисления высказываний

В игре "Угадай-ка" этап предварительного анализа протокола сводится к выбору подходящего представления формул. Для однозначных атрибутов, каждая формула V_i может быть представлена эквивалентной формулой W_i, использующей другие значений того же атрибута. В связи с этим, формальная замена в протоколе игры пары < V_i, P_i > на пару < W_i, P_i > не меняет его содержание. Однако с практической точки зрения одна из этих формул может оказаться более перспективной. В частности, когнитолог должен учитывать возможность последующих модификаций атрибутов и их значений.

Извлечение знаний из протоколов игры "Угадай-ка" связано с действиями эксперта по вычеркиванию тех или иных решений.

Первый (полный) вариант извлечения знаний исходит из того, что, исключая в i-ом туре игры решение p, эксперт опирается на всю информацию о примере, доступную ему в данный момент:

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

Второй (усеченный) вариант интерпретации протокола предполагает, что эксперт опирается только на самые последние сведения о примере, поэтому в основе его действий лежит

Поскольку каждый факт, предъявленный экспертом для проверки, связан с тем или иным атрибутом, то протокол игры "Угадай-ка" можно рассматривать как анкету опроса. Естественно, что при этом следует удалить все повторные вхождения атрибутов. Анкета опроса - это еще один модуль знаний, извлекаемый из протокола игры.

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

Шаг номер 1. Аргументы: V1.
             Следствия: ¬p (для каждого p из P1).
. . .
Шаг номер T. Аргументы: VT.
             Следствия: ¬p (для каждого p из PT).

С другой стороны, любая машина вывода, по-крайней мере теоретически, позволяет провести пошаговый вывод по известной базе знаний и заданной последовательности аргументов V₁, ..., V_T. В частности, машина вывода системы ФИАКР реализует такую возможность в качестве стандартного режима работы. Сравнивая протокол игры и трассу, построенную машиной вывода, можно выявить несовпадения в следствиях, а затем - найти и устранить причины этих несовпадений.

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