Пополнение знаний

6) d^f(S_u l_h **)|-^W<nS«, //, t_m), где t_m
внутрь; войти;... и т. п.}, (*"*={находиться в};

7) d'(S_u tj, h)\~d'R₂°d"(S_u t_h t_m), где tm-U+At, ^-{переместиться
изнутри; выйти;... и т. п.}, d"= {находиться вне);

8) d'(S_it l_P, t_h), (/_р<часть>/_т)|— d'(S_it l_m, h), где ^/'={войти;... и т. п.};

10) d'(O_it l_m, h), d"(S_p, Ot, tk)\~d'(S_P, l_mt t_h), где ^-{двигаться к;
мчаться; помчаться;... и т. п.}, с?'^/={находиться в; сидеть;... и т. п.}.

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

I

на юг вдоль проселочной дороги. Промелькнуло несколько деревень. Он вышел, когда поезд остановился у берега». Выпишем действия, упомянутые в расск-зе; d\ — «вошел», dz — «помчался», rf₃ — «промелькнуло», d± — «вышел», й$~- «остановился». Используя схемы правил, получаем:

rfi(OH, вагон, Л), (вагон<часть> поезд) \—d\ (ОН), поезд, /J;

di{OU, поезд, t\)\—d'{OU., поезд, /i-t-Л/), где d'^= {находиться в};

d'(OW, поезд, ti+At), d₂ (поезд, юг, Л+Д/)> da (ОН, юг, ti+At);

d₄(OH, вагон, t₂) \— d"(OH, вагон, г^+ДО. ^гДе d"= {находиться вне}.

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

Пополнение знаний на основе сценариев

Пополнение знаний можно выполнить с помощью сценариев (см. § 1.5). Опишем основные схемы рассуждений на сценариях, используемых при выво­де. Часть схем является интерпретацией значений слотов сценария (СЦ).

Схема 1. Пусть в СЦ значением слота «ключ» является имя события р+, а значением слота «посылки» — список имен событий (p_iy p2,-..,ph). В этом случае имеют место соотношения (PiR\p>), (р^ьр*), С-=1, 2,...,«, где Н\ — от­ношение предшествования во времени, я₃ — каузальное отношение.

Схема 2. Пусть в СЦ значением слота «ключ» является имя события /?*, а значением слота «следствия» — список имен событий {р_и р2,...,р_т). Тогда имеют место соотношения (piRip*), (риьр*), t=l, 2,.... А, где ^ — отношение «следовать за».

Схема 3. Обозначим множество значений слотов «посылки» через X, а мно' жество значений слота «следствие» через У. Имеют место следующие утверж­дения: для Vpi^X и УРз<=У верно (p_t «предшествует» р^).

Схема 4. Пусть ц — значение слота «цель деятеля» в СЦ, р, — имя ключе­вого события. Верно следующее: (p*Riu), (р*л₃ц).

Схема 5. Пусть р\* — значение слота «ключ» в СЦ1, р₂* — значение анало­гичного слота в СЦ2. Известно, что pt*n₃p_z*. Обозначим множество значений слота «посылки» в СЦ1 через Х_и а в СЦ2 —через Х₂; множество значений слота «следствие» в СЦ1 — через Y_h а в СЦ2 — через Y₂. Имеют место сле­дующие отношения: из \р^Х_у и \р^Х₂ следует (ptRipj); из Ypk^Yj и Yp_m€=Y₂ следует {PhR\p_m).

Схема 6. Рассмотрим случай схемы 5— р^лзрг*. Имеет место следующее: из Vpi€=X следует (рцг&ра*), где X=Xi{JX₂.

Рассмотрим использование каузальных сценариев (КСЦ) для планирова­ния действий во времени. Представим ситуацию «пожар», в которой находит­ся робот. Цель его поведения — устранение пожара. Для нахождения последо­вательности действий, удовлетворяющей поставленной цели, планирующая си­стема робота обращается к базе знаний, в которой находятся следующие сце­нарии:

1. (КСЦ «тушение пожара»: деятель (s:)

цель деятеля (р: «устранение пожара»); местоположение объекта пожара (/: be*); посылки (СЦ («поиск средств тушения» R_u транспортировка средств

тушения к объекту пожара»); ключ (/: «контакт средства тушения с огнем до полного прекращения

огня»);

следствие (р: «прекращение огня»); системное имя (sys: СЦ*1)). 2. (КСЦ «поиск средств тушения», деятель ($:);

цель деятеля (р: <Снахождение средств тушения»);

средства тушения (р: "Свода»);

посылки (/ («определение местонахождения средства тушения»» R_u

«движение к местонахождению средства тушения»)); кйюч (/.'«схватывание средства тушения»); следствие (р: «нахождение в месте расположения объекта средства

тушения»);

системное имя (sys: СЦ*2)).

3. (КСЦ «транспортировка средства тушения к объекту пожара»: деятель (s:)

цель деятеля (р: «наличие средства тушения в месте пожара»); посылки (/ («наличие средства тушения у деятеля» R_u «наличие ко­ординат местоположения объекта пожара»)); ключ (/: «передвижение к объекту пожара»), следствие (р; «нахождение у объекта пожара»); системное имя (sys: СЦ*3)).

Спецификация значения слота / означает, что далее идет название про­цедуры, которая должна быть выполнена при реализации данного сценария. Отношение Ri представляет временное отношение «предшествовать на п еди­ниц по шкале /,».

Общая схема построения плана достижения цели по сценариям такова:

1. Из описания проблемной области выбирается сценарий, значение слота
«цель» которого соответствует поставленной цели (для рассматриваемого слу­
чая — первый сценарий).

2. Анализируются значения всех слотов указанного сценария и строится
последовательность П_ь являющаяся значением слотов «посылки» и «ключ» с их
спецификациями. Для примера П: = СЦ («поиск средств тушения») Ri (СЦ «транс­
портировка средства тушения к объекту пожара») #i (f: «контакт средства
тушения с огнем до полного прекращения огня»). Заметим, что второе отноше­
ние Ri получено с использованием схемы I.

3. Выполняется последовательное обращение к сценариям, указанным в П]. При этом фрагмент последовательности Пь имеющий вид (СЦ <имя>), за­меняется соответствующей последовательностью Пг, построенной аналогич­но П|:

IIi=(f «определение местонахождения средства тушения») Ri (/ «движе­ние к местонахождению оредства тушения») Ri (/ «схватывание сред­ства тушения»).

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

Второй фрагмент Ш со спецификацией СЦ заменяется на следующий: Пз=(/ «наличие средства тушения у робота») /?i (/ «наличие координат местоположения объекта пожара») Ri (/ «передвижение к объекту по­жара»).

Последовательность Пз также не содержит спецификаций СЦ. На этом ее по­строение заканчивается.

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

IIi=(/ «определение местонахождения средства тушения») Ri (f «движе­ние к местонахождению средства тушения») Rt (/ «схватывание средства ту­шения») Ri [f «наличие средства тушения у деятеля») R_x (f «наличие коорди­нат местоположения объекта тушения») Ri (f «передвижение к объекту пожа­ра») R_t (f «контакт средства тушения с огнем до полного прекращения огня»).

2.3. Обобщение и классификация знаний

В. И. Вагин, Н. П. Викторова

Суть проблемы

Способность человеческого мышления к обобщению лежит в основе любого научного исследования. Именно в результате обобщения получаются новые зна­ния, т. -е. знания, не следующие непосредственно из ранее известных. В систе­мах, моделирующих мышление, обобщение понимают как процесс получения знаний, объясняющих имеющиеся факты и способных объяснять, классифициро­вать или предсказывать новые. В общем виде задача обобщения формулирует­ся следующим образом [Michalski et al., 1983]: по совокупности наблюдений (фактов) F, совокупности требований и допущений к виду результирующей гипотезы Я и совокупности базовых знаний и предположений, включающих зна­ния об особенностях предметной области, выбранном способе представления знаний, наборе допустимых операторов, эвристик и др., сформировать гипотезу Н: H=$-F (Я «объясняем F).

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

Согласно [Michalski et al., 1983] можно выделить модели обобщения по выборкам, и модели обобщения по данным. В первом случае совокупность фак­тов F имеет вид обучающей выборки — множества объектов e_lit Ш1, каждый из которых сопоставляется с именем класса Kj, jeJ. Целью обобщения в этом случае может являться:

формирование понятий: построение по данным обучающей выборки для каждого класса Kj, /е/, максимальной совокупности его общих характеристик [Бонгард, 1967; Oohen, 1977; Уинстон, 1978; Глтлина и др., 1981а, б];

классификация: построение по данным обучающей выборки для каждого класса Kj, /е/, минимальной совокупности характеристик, которая отличала бы элементы Kj от элементов других классов [Quinlan, 1979; Michalski, 1980; Харалик, 1982; Вагин и др., 1985);

определение закономерности последовательного появления событий [Diette-rich, 1979].

К моделям обобщения по выборкам относятся лингвистические модели [Фу, 1977], методы автоматического синтеза алгоритмов и программ по при­мерам [Biermann, 1978; Бардэинь, 1982] и др.

В моделях обобщения по данным априорное разделение фактов по клас­сам отсутствует. Здесь могут ставиться следующие цели:

формулирование гипотезы, обобщающей данные факты [Morgan, 1971; Plotkin, 1971; Финн, 1<>83];

выделение образов на множестве наблюдаемых данных, группировка дан­ных по признакам [Бонгард, 1967; Александров н др., 1983] (задача формиро­вания понятий, определенная в модели обобщения по выборкам, также часто ставится без априорного разбиения обучающей выборки по классам);

установление закономерностей, характеризующих совокупность наблюдае­мых данных [Загоруйко, 1981; Гаек и др., 1984].

С точки эрения способа представления знаний и допущений на общий вид объектов наблюдений е,- методы обобщения делятся на методы обобщения по признакам и структурно-логические (или концептуальные) методы. В первом случае объекты e^F, iel, представляются в виде совокупности значений кос­венных признаков я_А, A&Q [Хант и др., 1970; Харалик, 1982]. Методы обоб­щения и распознавания по признакам различаются для качественных и коли­чественных (измеримых) значений признаков.

В формально-логических системах, использующих структурно-логические методы обобщения, вывод общих следствий из данных фактов называют ин­дуктивным выводом. Правило вывода F\=H гипотезы Я из фактов F называ­ют индуктивным, если из истинности Я следует истинность F, а обратное не­верно [Забежайло и др., 1982; Финн, 1983; Гаек и др., 1984; Michalski et al., 1983]. В [Plotkin, 1971] сформулированы основные вопросы, на которые долж­ны давать ответы индуктивные логики и логики выдвижения гипотез: 1. Явля­ется гипотеза Я обоснованной данным знанием? 2. Существуют методы обосно­вания Я при данном знании? 3. Каковы условия для Я при данном знании, такие, что Я дает наиболее разумное и интересное объяснение? 4. Существуют методы для выдвижения гипотез на основании данного знания, дающих наи­более разумное и интересное объяснение изучаемого явления?

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

Моделям обобщения на семантических сетях [Гитлина и др., 19816; Вагин и др., 1985] свойственны черты как алгоритмов обобщения по признакам, так к индуктивной логики. Здесь также определяется набор операторов, используе­мых при формировании обобщенного представления (гипотезы) Я и выдвига­ются критерии оценки «интересности» и обоснованности гипотез. Кроме того, в этих моделях широко используется характерный для обобщения по качест­венным признакам [Гуревич и др., 1974; Харалик, 1982] аппарат теории по­крытий (см. гл. 4) и устанавливаются отношения на множестве значений при­знаков объектов — элементов сети. Методами структурного обобщения реша­ются обычно задачи классификации, формирования понятий, анализа сцен [Уинсток, 1978].

Для задачи обобщения по признакам известен следующий результат: каков бы ни был реальный вид разделяющей функции я|? (в общем случае индуктив­ной гипотезы Я) и алгоритм ее формирования по обучающей выборке, всегда найдется такая (непустая) обучающая выборка, что сформированная функция ф' (гипотеза Я') явится некорректной (ложной).

■В связи с этим гипотезы принято оценивать с точки зрения их «разумно­сти:», «рациональности», «интересности». Так, в [Гаек и др., 1984] рациональ­ность ответа на вопрос 1 индуктивного вывода понимается следующим обра­зом. Пусть Ф—истинные утверждения, <р — эмпирические данные. Тогда для

каждой 2-зависимой структуры U, если Ф, ф|=ф, то при условии ложности i|j на U вероятностная мера наблюдения ^_a(MgU, asS), такого, что <р истинно на Af_a, должна быть мала (например, меньше 0,05).

Для оценки обоснованности гипотезы в ДСМ-методе [Забежайло и др., 1982; Финн, 1983] используется квантор J_m, me{0, l/(n— 1), 2/(л— 1),..., 1}. Значение т~1/(л—1) соответствует гипотезам, достоверность которых неиз­вестна, значение т=1—истинным гипотезам. Если применяемое правило вы­вода подтверждает гипотезу, то значение m возрастает, если не подтверждает, то уменьшается.

В алгоритмах обобщения, использующих аппарат покрытий [Гитлина и др., 1981 а, б; Вагин и др., 1982; Харалик, 1982], принято оценивать гипотезы с точки зрения мощностей подмножеств покрываемых ими элементов обучаю­щей выборки.

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

Методы обобщения находят применение в экспертных системах, системах распознавания образов и анализа сцен, в задачах автоматизированного иссле­дования закономерностей явлений физики, химии, биологии, медицины [Bucha­nan et al., 1978; Гитлина и др., 1981а, б; Hajek et al., 1982]. На-

-Ч.

личие подсистем, решающих задачи обобщения, обязательно для систем ситуационного управления [Поспелов Д., 1982, 1986], в которых должны решаться задачи формирования обобщенных описаний классов ситуа­ций системы, соответствующих различным управляющим воздействиям, задачи структуризации ситуаций, получения по текущей ситуации ее иерархической модели — «слоеного пирога». Формирование иерархической модели требует решения как задач формирования понятий 1на этапе обучения, так и непосред­ственно задачи структуризации [Фомина, 1985].

Рассмотрим кратко связь между задачей обобщения и классификации и задачами, решаемыми в рамках теории вероятностей и математической стати­стики. Фактически в математической статистике также ставятся и решаются задачи вывода новых знаний на основании анализа совокупности наблюдений. В статистике устанавливаются частотные закономерности появления событий, т. е. определяются общий вид и параметры функций распределения вероятно­стей событий по данным наблюдений, делаются выводы о степени статистиче­ской зависимости наблюдаемых случайных величин, принимаются решения о выборе гипотезы о характеристиках случайного события на основании при­менения байесовской процедуры последовательного анализа наблюдений [Вальд, 1962; Барабаш и др., 1967; Хазея, 1968]. Общая задача формирования гипотез по данным наблюдений, рассматриваемая как одно из направлений развития ИС, не ограничивается установлением статистических закономерностей. Извест­ны формально-логические модели выдвижения статистических гипотез [Гаек и др., 1984]. Действительно, ставя перед собой задачу формализации представ­ления и вывода знаний о реальшм мире, нельзя не учитывать наличия стати­стических закономерностей в его проявлениях.

Методы обобщения по признакам

На признаковых структурах решаются обычно задачи классификации и формирования понятий. Обзор и анализ методов обобщения по признакам можно найти в [Журавлев, 1978а, б; Ту и др., 1978; Хант, 1978; Поспелов Д., 1986], а также в гл. 4.

Задача классификации по признакам ставится следующим образом [Журав­лев, 1978а, б; Поспелов Д., 1986]. Пусть имеется некоторое множество Z объ­ектов и множество П={я₁}, /el,л, признаков. Для каждого я/<=П, геС/Г задана область его определения А. Каждый объект s&Z однозначно определя­ется вектором Па значений его признаков: П_яеДХ •■• XD_n. Известно, что классы Ки Кг,-.,Кт являются подмножествами Z. Для каждого Kj, /si, от, задана информация // в виде обучающей выборки <v_t⁺, v,-~> множеств по­ложительных и отрицательных при меро в: i>,-+e/0; Vj-()Kj —0. Требуется по­строить решающие правила ijjy, /si, от, позволяющие определить принадлеж­ность произвольного объекта seZ классам Kj.

В задаче формирования понятий по обучающей выборке v^Z требуется по тем или иным критериям выделить совокупность классов {К}} и построить для них решающие правила if,-. В случае, когда области D_it i&u~n, обладают метрикой, каждый объект обучающей выборки можно представить точкой «-■мерного признакового пространства; тогда классы будут являться областями этого пространства и решающие правила ф^ /si, от, можно цредставить в виде разделяющих поверхностей в пространстве признаков. В процессе обобщения происходит настройка коэффициентов разделяющих функций, которые, как правило, выбираются линейными, квадратичными или кусочно-линейными. Опи­санный метод называется методом разделения.

Метод потенциальных функций [Айзерман и др., 1970] также применим лишь в случае, когда признаки являются измеримыми величинами. Потенци­альная функция \р_к для класса К строится так, чтобы ее значение на множе­стве объектов sf=K было максимальным.

^в [Журавлев и др., 1974; Журавлев, 1978а, 6J предлагаются способы классификации по признакам, основанные на вычислении оценок (методы го­лосования). Вначале определяется совокупность 2? решающих подмножеств на 84

множестве признаков (обычно это множества тупиковых тестов или подмно­жества выбранной мощности), а затем определяется мера близости объекта s каждому из классов Kj на основании сравнения значений признаков объекта 5 из заданных подмножеств с соответствующими значениями признаков эталон­ных объектов. Данные модели пригодны также для обработки качественных (неизмеримых) признаков и используют методы покрытии (см. гл. 4).

Для решения задачи классификации по качественным признакам чаще все­го применяют технику покрытий. В [Харалик, 1982] эта задача формулирует­ся следующим образом. Пусть С — множество классов: С={Ки Ki,...,K_m}, Z — множество образов, у —множество примеров. Тогда T^vxC — обучаю­щая выборка, представляющая собой отношение принадлежности примеров классам. Решающее правило if является отношением 7*si{>eZX£. В результа­те обобщения формируется совокупность 9? подмножеств, покрывающих у и обладающих следующими свойствами при ЬеЗ?: 1) Ь[\оФ0\ 2) /feC ( /C)7\

()

Классическим методом формирования решающих правил на множестве булевых переменных является метод минимизации частично определенных бу­левых функций [Me Cluskey, 1956]. Вариант этого метода для небулевых пе­ременных предложен в [Michalski, I973]. В [Haralick, 1977; Харалик, 1982] описан метод покрытия, предназначенный для распознавания как /г-мерных векторов, так и цепочек символов. В.основе метода лежит идея покрытия обу­чающей выборки цилиндрическими множествами, где под цилиндрическим понимается такое подмножество LsAX/JjX- Х^п, что для выделенной со­вокупности индексов /ь /₂,..., /а значения признаков фиксированы, а для ос­тальных совпадают с областями их определения.

Отметим, что методы разделения применимы только в том случае, когда реальный вид классов Kj, /^1,от, допускает разделение функциями выбранно­го вида. Так, невозможно получить методом разделения характеристические функции множеств четных или нечетных чисел. В [Бонгард, 1967] дл)Я данной области применения выбирается богатый набор логических функции, опреде­ленных на множестве признаков, значения которых могут вычисляться про­цедурно. Указанные функции могут отображать логические, арифметические или иные отношения на признаках. Решающее правило строится в виде буле­вой функции в процессе анализа элементов обучающей выборки.

Перспективным с точки зрения использования в ИС является метод обоб­щения, называемый методом растущих пирамидальных сетей (РПС) [Гладун, 1970; Гладун и др., 1975; Гладун, 1977; Поспелов Д., 1986]. Решающее пра­вило формируется в виде РПС путем многократного просмотра обучающей выборки. На нулевом уровне РПС находятся вершины-рецепторы, соответст­вующие множеству всех возможных значений признаков. Метод применим, в частности, для формирования понятий, зависимых от времени или имеющих динамическую природу.

Методы формирования понятий по обучающей выборке v^Z без ацриор* ного разбиения на классы рассматриваются в кластерном анализе [Классифи­кация, 1980; Александров и др., 1983]. В класс (кластер) группируются объ­екты, близкие друг к другу в признаковом пространстве. В [Бонгард, 1967] цредложен метод формирования понятий, называемый «развал на кучи» и со­стоящий в группировании объектов вокруг некоторого «ядра».

Для решения задачи обобщения по признакам необходимо первоначально выделить совокупность «информативных» признаков, характеризующих объек­ты seZ. Методы определения словаря признаков предложены в [Горелик, 1973; Горелик и др., 1977].

В синтаксических методах распознавания [Нарасимхан, 1969; Фу, 1977; Fu, 1978] образы (элементы s^Z) представляются в виде цепочек' символов-слов некоторого языка. Решающее правило ищется в виде грамматики G, та­кой, что цепочки символов из с+ (множества положительных примеров) по­рождаются G, а цепочки из v~ (множества контрпримеров) не порождаются. Для этой цели также часто используют аппарат покрытий.

Структурно-логические методы обобщения

Структурно-логические методы в отличие от признаковых предназначены для решения задачи обобщения на множестве объектов, имеющих внутреннюю логическую структуру (последовательности событий, иерархически организован­ные сети, характеризуемые как признаками и свойствами объектов — элементов сети, так я отношениями между ними, алгоритмические и программные схемы) [Кайберг, 1978; Michalski et al., 1983; Финн, 1984; Поспелов Д., 1986]. Снача­ла рассмотрим методы индуктивного вывода в формальных исчислениях, а затем — методы обобщения на семантических сетях.

Основой каждой модели индуктивного вывода является набор правил (схем) индуктивного вывода. В [Plotkin, 1970; Plotkin, 1971] за основную схему вы­вода была выбрана схема индуктивной резолюции (обозначения по [Michalski et al, 1983])

&

или в другой форме

(знак |= обозначает отношение индуктивного следования).

Эта схема применяется в классическом исчислении предикатов первого по­рядка вместе с алгоритмом антиунификации. Результатом применения прави­ла индуктивной резолюции к двум предложениям является их «наименее об­щее обобщение».

В [Michalski et al., 1983] строится система индуктивного вывода в рамках модификации языка исчисления предикатов первого порядка, включающей обоб­щенные кванторы и префиксную запись отношений равенства и неравенства. Помимо принципа индуктивной резолюции используются следующие схемы вывода:

СТХ & S => К |= СТХ =£ К (селекция),

СТХ & [L= flj => К |= СТХ St [I = R₂] => К, (расширение),
где ^CR.C. DOM (L)

CTXj =? К И CTXj V CTX₂ => К (добавление);

СТХ &[L=a]=>K

. • • =CTX&[Ls=[a, z]]=$K (переход к интервалу);

F{a\

... =yvF(v) (классическая индукция)

и др..

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

Правила индуктивного вывода, используемые в ДСМ-методе [Финн и др., 1981; Забежайло и др., 1982; Финн, 1983] основываются на схемах, предло­женных в [Милль, 1900].

Получивший широкую известность GUHA-метод [Гаек и др., 1984] позво­ляет формировать множество «всех интересных гипотез» о наблюдаемых дан-

ных. Гипотезы, порождаемые GUHA-методом, имеют вид ty~q>, где ур и <р —
утверждения, имеющие единственную свободную переменную х, а------------------------------- связы­
вающий х ассоциативный или индуктивный квантор: (~*)(г|>, <р). Выражение
*|>~Ф в зависимости от выбранного квантора может.служить для представле­
ния широкого диапазона зависимостей между ■§ и <р (от логического следова­
ния до статистической корреляции). Для утверждений специального класса ме­
тод позволяет сформировать такое подмножество гипотез, что все остальные
следуют из них в соответствии с принятым набором правил вывода.

В качестве языка представления знаний (отдельно рассматриваются язы­ки представления эмпирических и теоретических утверждений) используется модификация языка исчисления предикатов первого порядка с обобщенными кванторами в смысле [Mostovski, 1957]. Каждому квантору q ставится в со­ответствие функция Asfg, вычисляющая значение его истинности на каждой модели <.М, /i, /₂,..., /п>, где М — непустое множество из некоторого семей­ства ЗЙ, a /i, /2,.... fn — набор логических функций, определенных на этом мно­жестве.

Квантор q, определенный на моделях <М, t|>, <p> типа <1,1> (кортеж арностей функций), называют ассоциативным в следующем случае. Пусть ам — количество элементов М, на которых гр и <р одновременно истинны, Ьм —ко­личество элементов, на которых ч> истинно, а ф ложно; См: <р истинно, ty лож­но; du: как ф, так и ф ложно.

_м, то для ассоциатив-

2 1