АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. II. Контроль исходного уровня знаний студентов
  2. III. Основы медицинских знаний и здорового образа жизни.
  3. IV. КОНТРОЛЬ ЗНАНИЙ
  4. V Усвоение новых знаний
  5. VI. Основы медицинских знаний.
  6. VII. КОНТРОЛЬ ЗНАНИЙ
  7. Актуализация знаний
  8. Актуализация знаний.
  9. Актуализация опорных знаний.
  10. Базы знаний на ЭВМ
  11. ВЗАИМОСВЯЗЬ КОРРЕКЦИОННОЙ ПЕДАГОГИКИ С ДРУГИМИ ОТРАСЛЯМИ ЗНАНИЙ
  12. Взаимосвязь накопления знаний и глобализации бизнеса

Л. В. Литвинцева, Д. А. Поспелов Основные определения

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

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


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

Можно указать несколько подходов к пополнению знаний: модели «здравого смысла» [Шенк, 1980], сценарии (см. § 1.5) [Литвинцева, 1986], подход, опи­рающийся на идею о том, что физические закономерности внешнего мира могут быть описаны в рамках специальных псевдофизических логик [Поспелов Д., 1986J. Все эти подходы в той или иной мере используют идею продукционных правил (см. § 1.4).

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

х <содержится в> у, у <содержится в> z=>x <содержится в> z (свой­ство вложенности, которое выполняется в «матрешках»);

х <находится на> у, z <находится на> x=*>z <находится над> у.

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

Псевдофизические логики

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

1. ПФЛ есть логики отношений: временных, пространственных, каузальных,
действия.

2. Часть рассуждений в ПФЛ связана со шкалами: метрическими (абсолют*
ними
и относительными) и топологическими. На абсолютной метрической шкале
задан некоторый масштаб и выбрана точка отсчета; на относительной указыва­
ется лишь расстояние между точками, а начало отсчета может «плавать». Топо­
логическая шкала представляет собой порядковую шкалу. На ней указываются
отношения порядка (строгого, нестрогого, размытого) между упорядочиваемыми
объектами. Различные абсолютные шкалы преобразуются друг в друга. Для
перехода от относительной шкалы к абсолютной требуется определить абсолют­
ное значение начальной точки отсчета, после чего легко переводятся остальные
точки шкалы. Изоморфизма между топологическими шкалами не существует.

3. ПФЛ содержат в качестве аксиом утверждения, вытекающие из восприя­
тия мира человеком, которые подтверждаются результатами соответствующих
психологических экспериментов.

4. Совокупность ПФЛ характеризуется связями между отдельными частя­
ми— логиками (например, логика времени тесно связана с логиками простран­
ства и действий).

Существуют модели временных логик [Литвинцева и др., 1986], статической пространственной логики [Варосян и др., 1982], фрагменты логики действий и каузальной логики [Кандрашина и др., 1989].

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


Рассмотрим примеры конкретных ПФЛ и пополнение знаний на их основе.

Логика времени. Введем множество T*={t\, t2, t3,...}, элементы которого назовем моментами времени, и множество Р={Р\, Р2> ■ ■ •, Рп), элементы которого назовем событиями. Будем говорить, что событие р/ происходит в момент вре­мени tj, если ему можно приписать момент времени /,-. Если для pj существует лишь один момент времени, в который оно происходит, то событие р/ называет­ся точечным; если оно сопоставляется с некоторой непрерывной последователь­ностью моментов, то оно называется интервальный.

За исходные свойства времени примем однонаправленность, линейность, не­прерывность, бесконечность, гомогенность. Заметим, что из свойств однонаправ­ленности и линейности вытекает свойство транзитивности времени.

На множестве sczPi точечных событий зададим шесть временных отноше­ний трех типов: неметрические 0 — одновременно, г\ — быть раньше, г2 — быть позже); метрические и частотные (r3n>L — быть раньше на п единиц (п=\, 2, 3,...) по шкале L, г+Ч — происходить в момент t на шкале L, rsLn — происхо­дить с частотой л на шкале L, где Leif — множество шкал).

На множестве sczP2 интервальных событий зададим 14 временных отноше­ний: R\ — строго предшествовать во времени; R2 строго следовать; /?3 — пере­секаться и др. [Литвинцева и др., 1986].

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

Зададим множество М правил построения ППФ в логике времени, которы­ми являются комбинации троек типа (piRpi), где pi, p/e=P, /?<={г„, ru..., гъ,

R\, /?2.......... Ru}- Множество аксиом Г составляют продукции вида а, рЬ-V-

Имеется также три правила вывода:

Приведем примеры схем аксиом в логике времени:

0) (2) (3) (4)

(Pi гпъ'1 Pi), (Pi rlL a) |- (p{ $+»*pk),

(Pi r\ t), (pt rl'L p}) h P} r\ (t®n), где ф —операция сложения времен на шкалах,

(Pi гх Pj), (pf rx pk) \- (pt rx pk).

Посмотрим, как работают эти схемы в задаче пополнения знаний. Пусть на вход ИС поступает следующее описание ситуации в виде текста на естествен­ном языке: «Самолет, следовавший рейсом Баку—Москва, совершил посадку в аэропорту в 15 ч 20 мин. Через 10 мин был подан трап. Затем прибыл авто­бус. Пассажиры покинули самолет. Через 3 мин автобус доставил их в здание аэровокзала:». Для простоты будем считать, что события данного текста точеч­ные. Выделим их: рх~ «посадка самолета», р2 «подача трапа>, р3 — «прибытие автобуса>, р* — «выход пассажиров из самолета», р& — «доставка пассажиров в здание аэровокзала». Описание ситуации на языке М выглядит так:

где /=15 ч 20 мин на шкале L с единицей измерения «минута».

Формальное представление событий текста обрабатывается процедурой по­полнения, которая выведет следующие факты:

(Pirtt), (Plrl°'Lp2)\-(parit,).

где /.-=15 ч 30 мин на шкале L (по схеме 2);


(Pi r\OtL Pi) h (Pi ri Pi) (п0 схеме 3>;

(Pi ri P2). (P% ri Pt) h (Pi rx fa) (по схеме 4);
(Pt r*'L Ръ) \- (Pa ri Рь) (п0 схеме 3> •

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

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

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

Л1 — необходимая и достаточная причина. Действия d\, d2 связаны отно­шением пи если реализация d\ всегда вызывает реализацию d$t н, наоборот, по­явление d% всегда вызывается d\\ чаще всего лх отражает различные физические законы реального мира (например, сверкнула молния — грянул гром).

л,__ достятпчняя причина, которая означает, что реализация di всегда вы­
зывает d2y однако из появления d2 не всегда следует появление d\ (например,
«нырнул в реку, оказался в воде»).

Яд — обусловливающая причина. Действия d\, d2 связаны отношением Яз, если реализация d\ обеспечивает необходимые условия для реализации dt, кото­рое, однако, может и не произойти (например, «вошел в комнату, включил свет»).

Опишем действия в виде предикатов dt (Sk, О/, Im, tt, lp), где в качестве
аргументов выступают глубинные падежи данного действия: субъект, объект,
инструмент, время реализации действия и его локализация. Введем следующие
множества: множество действий £><={ii, d2,..., dn); множество объектов О—
"{Oi, 02,..., От); множество инструментов 1—{1\, 12.............................. //}; множество вре­
мен T={U, h........... U}\ множество локализаций L={h, ls....................... /Р}.

На множестве действий рассмотрим множество из восьми отношений, харак­теризующих их взаимосвязь: Ri° — действие di является частью действия dfi #2° — действие dt приводит к результату dj; R»D —действие dt сопровождается действием d}\ RtD субъект действия di(Sk) имеет цель dj; /?sD — субъект дей­ствия di(Sn) имеет мотив d} (считается, что в качестве результатов, целей и мотивов выступают другие действия). Сюда же относятся три каузальных от­ношения л/ между действиями. Выделенная группа отношений составляет базо­вую систему отношений ПФЛД.

Схемы аксиом ПФЛД описывают семантические и прагматические свойства физических действий. Приведем несколько схем правил, описывающих действия:

1) di(U)Rdj(fi)\- U <быть раньше> tf, где R={nu n2, п3);

2) di(ti)RiDd/(t}) \—ti <пересекается t};

3) <&(S/, Oj, 1э, tm)\—d'(Oh Ik, tm), где <Г={находиться около}, dt&D'cD;

4) di(Sit Oj, ^) |— d'(St, Oj, tk), где dr {находиться около}, di<=D'czD\

5) diRt»di, djRtDdk\~dtJbdk; 6) di(Sj)\~diR^d

{переместиться

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

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

8) d'(Sit lP, th), (/р<часть>/т)|— d'(Sit lm, h), где ^/'={войти;... и т. п.};

10) d'(Oit lm, h), d"(Sp, Ot, tk)\~d'(SP, lmt th), где ^-{двигаться к;
мчаться; помчаться;... и т. п.}, с?'/={находиться в; сидеть;... и т. п.}.

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


I


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

огня»);

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


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

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

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

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

тушения»);

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

Согласно [Michalski et al., 1983] можно выделить модели обобщения по выборкам, и модели обобщения по данным. В первом случае совокупность фак­тов F имеет вид обучающей выборки — множества объектов elit Ш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), такого, что <р истинно на Afa, должна быть мала (например, меньше 0,05).

Для оценки обоснованности гипотезы в ДСМ-методе [Забежайло и др., 1982; Финн, 1983] используется квантор Jm, 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 объ­ектов и множество П={я1}, /el,л, признаков. Для каждого я/<=П, геС/Г задана область его определения А. Каждый объект s&Z однозначно определя­ется вектором Па значений его признаков: ПяеДХ •■• XDn. Известно, что классы Ки Кг,-.,Кт являются подмножествами Z. Для каждого Kj, /si, от, задана информация // в виде обучающей выборки <vt+, v,-~> множеств по­ложительных и отрицательных при меро в: i>,-+e/0; Vj-()Kj —0. Требуется по­строить решающие правила ijjy, /si, от, позволяющие определить принадлеж­ность произвольного объекта seZ классам Kj.

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

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

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


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

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

()

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

Отметим, что методы разделения применимы только в том случае, когда реальный вид классов 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 = R2] => К, (расширение),
где ^CR.C. DOM (L)

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

СТХ &[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, /2,..., /п>, где М — непустое множество из некоторого семей­ства ЗЙ, a /i, /2,.... fn — набор логических функций, определенных на этом мно­жестве.

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

Тогда если ам
, Ьм
М с»

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

2 1

м
яЬмМ

ного квантора условие Asf9<-W2, ф, у> = 1 влечет Asf(7<jW1, ф, у>=]. Определение импликативного квантора аналогично для условий а

Для задания GUHA-метода требуется определить ассоциативный или им-лликативный квантор ~, квантор эквивалентности **=*- и еще ряд характери­стик (например, запрет или разрешение использовать дедуктивные правила вывода). Особое внимание уделяется методам формирования гипотез ф~ф, таких, что ф представляет собой элементарную конъюнкцию, а ф — элементар­ную дизъюнкцию одноместных предикатов. С помощью языка, использующего повятие случайной модели <Mj, fu /2,.... fn>, где а<=2 — случайный пара­метр, вводится вероятностная мера достоверности гипотез и рассматриваются статистические гипотезы. Важный класс ассоциативных (и имлликативных) кванторов образуют кванторы, функции Asf которых являются тестами для проверки статистических гипотез. GUHA-метод нашел применение в медицине [Тшпа, 1970], социологии [Havranek et al., 1977], лингвистике, строительстве,

В [Ефимов, 1979] предложен алгоритм индуктивного формирования понятий ви Да)*! *iv * ■ -. >!„ Xin C{*ix,-•■> *{п). ■., где каждый }^ — квантор всеобщности

илн существования, a C(xix................................. ytn) —выражение в конъюнктивной нормальной

форме.

Понятие формируется из определения конкретного набора кванторов и оп­ределения содержимого понятия С(х/1,..., Х(п) (см. § 4.3). В [Погосян,.1977] процедура индуктивного обобщения формализована для задачи форми­рования описаний (см. гл. 6).

Вопросы взаимосвязи теории вероятностей и индуктивной логики рассмат­риваются в [Сагпар, 1950; Hintikka, 1965], где разработана концепция индук­тивной вероятности., а также установлена связь между отношением логическо­го следования и понятием индуктивной вероятности.

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


нятий) играет в данном случае выбираемый формализм семантической сети.

Рассмотрим методы обобщения на сетях [Вагин и др., 1982; 1985]. Пусть
2 — множество объектов. Каждый объект s^Z представляется сетью, называв
мой семантическим графом (СГ), который включает вершины двух типов: объ­
ектные и предикатные. Объектной вершине приписывается имя (объекта), имя
базового класса объекта и вектор ею признаков; предикатной вершине —имл
отношения, выполняющегося между объектами (возможно, с отрицанием).
Семантический граф, предназначенный для представления объекта seZ, распа­
дается на иерархически упорядоченное множество двухуровневых р-лодграфов,
служащих для представления объекта s, его «частей» (р-лотомков), частей его
частей и т. д.; р-подграф содержит на первом уровне объектную.вершину vt,
связанную отношением р (целое — часть) с объектными вершинами второго
уровня, которые связаны между собой отношениями через предикатные вер­
шины. *;

Обобщенный семантический граф (ОСГ) также представляется в виде на­бора обобщенных р-подграфов (op-подграфов). Каждый ор-подпраф g пред­назначен для представления множества M—m{g) объеков. Объектной вершине первого уровня ар-подграфа приписывается имя множества М: M=m(g), имя базового класса Т: М^Т и совокупность рк ограничений на изменения значе­ний признаков объектов из М. Объектная вершина v второго уровня взвешена именем множества Mv, которое может быть получено из множеств, представк мых на op-подграфах применением к ним конечного числа операций объедине­ния и пересечения. Предикатным вершинам op-подграфов приписаны выражения логики исчисления высказываний, в которых роль высказываний играют име­на отношений между объектами. На л-предикатных вершинах ОСГ отобража­ются отношения, выполняющиеся на множестве значений признаков различных объектов.

Каждый ор-подграф § определяет множество m(g) объектов g, таких, что g изоморфно наложим на некоторый частичный подграф g и выполняются за­данные условия наложимости вершин (в соответствии с трактовкой их весов).

Обобщенное представление искомого класса К ищется по обучающей вы­борке <i>+, и~> в виде покрывающей совокупности ОСГ §и Ш1к, таких, что

U

U

В [Вагин и др., 1982] обобщения g получаются применением к элемен­там geu+ операторов обобщения, таких, например, как удаление вершины из графа, замена значения признака множеством значений, замена имени отно­шения Q на предикатной вершине выражением L=Q\/R. В [Вагин и др., 1985] обобщения g формируются «от противного». За исходный принимается «наиболее общий» граф go, покрывающий все элементы базового класса Т. Все остальные ОСГ получаются в результате применения к go конечного числа ограничивающих операторов, таких, например, как ввод предикатной вершины в ОСГ, ввод конъюнктивного члена в предикатную вершину, удаление дизъ­юнктивного члена из предикатной вершины, сужение допустимого множества изменения значений признаков, ввод отношения (я-цредикатной вершины) на множестве значений признаков. В последнем случае, следуя [Бонгард, 1967], изначально выбирается достаточно богатый набор допустимых отношении. Процесс формирования обобщенных представлений классов ведется по уровням ОСГ (согласно иерархии р-<подг,рафов), начиная с нижних, методом ветвей и границ.

В [Гитлина и др., 1981а, б] предложен алгоритм структурного обобщения, в котором обобщенное описание класса К также ищется в виде множества подграфов gtt /е/х, в совокупности покрывающих элементы обучающей вы­борки. Подграф g покрывает граф g, если он изоморфен одному из частичных подграфов g в классическом смысле. Метод успешно применялся для распоз­навания структуры химических соединений.


В [Уинстон, 1978] описан алгоритм структурного обобщения для решения задач анализа сцен. Эта задача подробно рассматривается в [Дула и nv 1976].

Особое место занимают задачи «алгоритмической структурной индукнии». Целью является автоматический синтез алгоритмов и программ по конкретным (числовым) примерам их работы [Biermann, 1978; Бардзинь, 1982].


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.036 сек.)