автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Метаматематические исследования правдоподобных рассуждений типа ДСМ

На правах рукописи

Р I I им

ВИНОГРАДОВ

Дмитрий Вячеславович 1 - ;

МЕТАМАТЕМАТИЧЕСКИЕ ИССЛЕДОВАНИЯ ПРАВДОПОДОБНЫХ РАССУЖДЕНИЙ ТИПА ДСМ

Специальность -05.13.17 Теоретические основы информатики

АВТОРЕФЕРАТ

ДИССЕРТАЦИИ НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ КАНДИДАТА ФИЗИКО-МАТЕМАТИЧЕСКИХ НАУК

Москва 2000

Работа выполнена во Всероссийском институте научной i технической информации

Научный руководитель:

доктор технических наук, профессор Финн Виктор Константинович

Официальные оппоненты:

доктор физико-математических наук, профессор Вениаминов Евгений Михайлович

доктор физико-математических наук, профессор Осипов Геннадий Семенович

Ведущая организация:

Вычислительный центр РАН

Защита состоится 26 апреля 2000 г. в 12 час. 00 мин. заседании диссертационного совета Д.003.02.01 Всероссийском институте научной и технической информа по адресу: 125315, Москва А-315, ул. Усиевича, д. ВИНИТИ, комн. 502.

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

Автореферат разослан 24 марта 2000 г.

Ученый секретарь совета Д.003.02.01

доктор биологических наук, профессор М.А. Камен

4M. L N. О

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

уальность темы

Диссертация посвящена исследованию различных (логических, :браических и алгоритмических) вопросов реализации правдоподобных :уждений, основанных на автомагическом порождении гипотез о *стве и различии исследуемых объектов.

гже в начале 1970-х годов стало очевидно, что рассуждения эксперта не ут быть описаны исключительно в дедуктивных терминах. МакКарти, Р. Рейтер и их ученики развили подходы к «рассуждениям шого смысла» на основе различных систем немонотонных логик, арденфорс и др. исследовали математические основы пересмотра >ий. Однако, несмотря на известное изящество предложенных лрукций, все эти теории так и не привели к прикладным системам, цествляющим автоматизированные рассуждения в конкретных сметных областях.

> конце 1970-х годов группа исследователей под руководством рессора В.К. Финна1 существенно продвинулась в формализации [ствами многозначных логик, расширении и обобщении процедур укции (названных в честь Д.С. Милля - создателя концепции уктивных методов - ДСМ-методом автоматического порождения зтез). Правдоподобные рассуждения типа ДСМ соединили в себе укцию на эмпирических данных, рассуждения по аналогии, лруктивную абдукцию и дедуктивные выводы. На основе уложенной теории были созданы прикладные интеллектуальные темы в помощь исследователям-фармакологам при компьютерном лруировании лекарств, ученым-социологам при исследовании ивидуальных поведенческих готовностей и другие. )днако в изложении этой актуальной теории имеются определенные дш. С одной стороны, для понимания основ ДСМ-теории необходимо сомство с многозначными логиками, а также изучение теории 1 и катов с кванторами по конечным множествам. Эти теории не даются в рамках стандартных курсов математической логики, и

>инн В.К. О возможностях формализации правдоподобных рассуждений ;ствами многозначных логик // VII Всесоюзный симпозиум по логике и »дологии науки. - Киев: Наукова думка, 1976. - С. 82-83.

большинство специалистов не знакомо с требуемыми понятиями, 1 препятствует более широкому распространению нового метода. С дру] стороны, построение прикладных систем для социологии породило воп] о структурах для исследуемых свойств (шкалы суждений). Кроме того, I недостаточном внимании к описанию субъектов возможен (и наблюдалс действительности) «комбинаторный взрыв» - огромное число гипот информационная сложность которых превосходит сложность исходи примеров.

Цель работы

Главные цели работы - разработать логический формализм для описа] ДСМ-метода, наиболее знакомый специалистам по искусственнс интеллекту; исследовать вопрос о представлении шкалированных свойст также предложить методы правдоподобных рассуждений типа ДСМ , больших решеток гипотез.

Методы исследования

Они состояли в использовании формализма стратифицировав логических программ, элиминации кванторов в системах части1» изоморфизмов, методов алгебраической теории решеток и дискрет! цепей Маркова.

Научная новизна

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

Практическая и теоретическая ценность

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

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

пбация работы

;зультаты работы докладывались на национальных конференциях по сственному интеллекту, международных конференциях «Integration, •mation Technologies and Telecommunications» 97 и 99, общемосковском шаре по искусственному интеллекту под руководством проф. Вагина и проф. О.П. Кузнецова, научно-исследовательском семинаре ора интеллектуальных систем ВИНИТИ.

»ликации

основные результаты диссертации опубликованы в работах [1-6]. ьем работы

Диссертация содержит 56 страниц и состоит из введения, трех глав и жа литературы, содержащего 24 названия.

СОДЕРЖАНИЕ РАБОТЫ

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

Напомним основную схему правдоподобных рассуждений типа Д Они основаны на возможности вычисления сходства объектов обучающей базы данных. На первом этапе находятся глобальные сход объектов. Происходит шаг индуктивного обобщения. Затем вычисляв условия, препятствующие действию гипотетических «причин». Эти усл< подразделяются на логические (например, запрет на контр-примерь структурные (обобщенная стратегия правдоподобных рассуждений), основании порожденных гипотез предсказываются свойства но объектов. При этом предсказание осуществляет перенос свойств извест объектов на новые объекты по аналогии. Наконец, порожденные гипот проверяются на полное и адекватное описание данных из обучающей £ данных. Если проверка заканчивается успехом, то порожденные гипот представляют собой конструктивную абдукцию. В противном слу объекты, не получившие объяснения, предъявляются эксперту пополнения обучающей базы данных объектами, сходными предъявленными, в (полуАвтоматическом режиме. В дальнейшем возмо итерация вычислений с пополненной базой данных.

Для описания причинно-следственных зависимостей (без у структурных запретов) необходимо рассматривать элементы сорта «объ( (переменные X с индексами), сорта «подобъект» (переменные 2 и индексами) и сорта «(под)множество свойств» (переменные У, и и 1 индексами). Основные отношения «объект X обладает множест свойством У» и «подобъект V является причиной наличия множес свойств "V/» представляются бинарными предикатами X =>, У, V =>; Однако, для формального представления правдоподобных рассужде необходимо расширение классической многосортной логики предика первого порядка в двух направлениях: многозначность и кванторы конечным множествам (или кортежам переменной длины).

Так как исходная база данных содержит неполную информацю

Яствах изучаемых объектов, то приходится вводить дополнительные 1нностные значения. В итоге, получаем следующие внутренние щепляемые в случае итерации) истинностные значения: (+1) -тическая истина, (-1) - фактическая ложь, (0) - фактическое гиворечие, (т) - неопределенность. Кроме того, имеются стандартные синие истинностные значения 1 (логическая истина - выделенное ¡ение) и £ (логическая ложь).

{ля каждого внутреннего истинностного значения вводятся гветствующие .[-операторы Россера-Тькжетта: Л У(А,) = 1, если X = V, и 0 = ^ если X Ф V. Формулы вида I У(Ф), где Ф - произвольная формула, а внутреннее истинностное значение, назовем .1-формулами, Д-формулы а I у(Ф), где Ф - атомарная формула, назовем .Г-атомарными. Формулы, троенные из .Г-формул с помощью обычных логических связок логики вого порядка, назовем внешними. Внешние формулы, содержащие ько .Г-атомарные Л-формулы, назовем нормальными. 1а внутренних истинностных значениях можно определить связки и нторы. Нужно только позаботиться о том, чтобы для любой внешней »мулы существовала эквивалентная ей нормальная формула. Такие позначные логики называются ^определимыми. Критерий феделимости и теорема об аксиоматизируемости многозначных жонечнозначных с конечным числом типов истинностных значений) ик доказаны О. М. Аншаковым, Д. П. Скворцовым и В. К. Финном2. 1о гораздо более радикальным расширением является введение нторов по конечным множествам. Они необходимы для записи условия бальности сходства как необходимого признака причины множества йств. Глобальное сходство примеров определяется через сходство такого >жества примеров, которое не может быть расширено без уменьшения детва. Это условие апеллирует к конечному, но заранее не ссированному числу примеров, что не может быть выражено в логике дикатов первого порядка.

ава I

3 начале главы исследованы вопросы о (не)выразимости в логике вого порядка и фрагментах монадической логики второго порядка

tishakov O.M., Finn V.K., Skvortsov D.P. On axiomatization of many-valued logics iciated with formalization of plausible reasoning // Studia Logica. - 1989. - Vol. 48, L - P. 423-447.

основных фигур правдоподобных рассуждений. Здесь достато1 ограничиться единственным исследуемым свойством. Кроме того, заменяем бинарную операцию локального сходства тернарным предикате Определение. Формула вида ЪА\..ЗАк [фС^ь ••■> Л*)], где А\, ..., А, унарные предикатные переменные, а ср(А\, ..., Ак) - замкнутая форм; первого порядка, в которой кроме А\, ■ ■■, Ак имеются лишь (предикатны функциональные) константы и индивидные переменные, называе монадической Е^-формулой. Аналогично, формула вида \1А\...\1Ак [ср( ...,Ак)] с теми же условиями называется монадической П1 [-формулой.

Сигнатура языка будет включать в себя следующие символы: тернар] предикатная константа а (для операции локального сходства); унар] предикатная константа О (для выделения исходных объек исследования); индивидная константа ± (для тривиального сходства). / случаев индукции и аналогии добавим индивидную константу обозначающую гипотетическое сходство или объект, доопределяемый аналогии.

Задача абдукции. Для всякого ли объекта х найдется нетривиалы сходство V,,.! некоторых объектов ..., г„(п> 1), которое содержится в. Утверждение. Задача абдукции (при отсутствии отрицательных пример задается формулой первого поря,

v* {0(х) зг [0(г) & г & 3 у (у = х л г & v ф 1)]}. Замечание. На этом факте основано то замечательное обстоятельство, при неудаче критерия достаточного основания правдоподобного выв-достаточно к каждому необъясненному объекту добавить единствен^ объект, имеющий нетривиальное сходство с ним.

Задача индукции. Является лиц сходством у„.1 некоторых объектов... (п> 1)?

Теорема. Задача индукции невыразима формулой первого порядка.

Следует отметить, что стандартная техника ограничения кванторов локальные окрестности неприменима, так как из-за аксиомы V* (± = х л любые две точки находятся на расстоянии, не превосходящем 2. Задача аналогии. Найдется ли нетривиальное сходство у„_1 некото{ объектов ¿ь ...,г„(п> 1), которое содержится в q? Теорема. Задача аналогии невыразима формулой первого порядка. Тем не менее, задача аналогии может быть выражена в слабом фрагме монадической логики второго порядка.

Утверждение. Задача аналогии выражается как монадичеа И'гформулой, так и монадической П\-формулой.

первоначальном изложении логика первого порядка была расширена ггорами по конечным множествам3. Однако плата за это решение зтся чрезмерной: возникают трудности при попытке построения 'ктивной системы, корректной и полной относительно стандартных осительно натуральных чисел - мощности множеств) моделей, действительности, никакой такой дедуктивной системы существовать ожет! Этот результат для логики предикатов с кванторами по конечным жествам доказан в первой главе диссертации. Он выводится из теоремы . Трахтенброта4 о рекурсивной неотделимости противоречивых и 5чно-выполнимых формул логики предикатов первого порядка, :ржащего предикатный символ арности > 1.

> главе 1 диссертации описан другой подход, который лишен указанного [е недостатка. Мы пользуемся формализмом стратифицированных веских программ. Этот подход имеет несколько преимуществ: он имеет простую семантику итерированных неподвижных точек; декларативные знания легко записываются в этом языке; существующие РЯОЬОО-машины могут быть встроены как дедуктивная компонента;

синтаксис языка известен как специалистам по искусственному

интеллекту, так и экспертам-прикладникам.

»еделение. Логическая программа - это множество правил вида

Ьа<г-Ь\,Ь2, ...,1ч,

- литералы. Литерал Ьц — голова правила, остальные литералы мируют тело правила. Каждый литерал в теле - это атомарная формула 1, ...,х„) или отрицание атомарной формулы , ...,х„), где <2- один реляционных символов сигнатуры ст, или некоторая реляционная еменная, не содержащаяся в сигнатуре ст. Голова правила - атомарная мула ()(Х], ...,х„), где ()-реляционная переменная. Гогическая программа п, имеющая реляционными переменными волы Би ..., называется стратифицированной, если найдется такое жение и1£]Р, правил программы к, что выполняются следующие два овия:

кворцов Д.П. О некоторых способах построения языков с кванторами по гежам // Семиотика и информатика. - М.: ВИНИТИ. - 1983, Вып. 20. -02-126.

ахтенброт Б.А. О рекурсивной отделимости // Доклады АН СССР. - 1953, Г. 88. 953-955.

• если реляционная переменная встречается без отрицания в • правила из Рт, то каждое правило с »У, в голове содержится в и,<„Р,\

• если реляционная переменная Б, встречается под отрицанием в -правила из Рт, то каждое правило с в голове содержится в иКт1 частности, ни одна переменная не встречается под отрицанием в -правила из первой страты Р\.)

Пусть 9?=(Л; ..., К г) - реляционная структура для сигнатурь Рассмотрим программу пи образованную правилами первой страты Пусть она содержит реляционные переменные ¿ь ..., б1« арности щ, ... соответственно. Программа %\ задает оператор ©ь определенный последовательностях 8=($1, ..., .У^) из /^-местного, ..., я5-мест1 отношения на носителе А структуры 91. Образ ©1(5) представляет со такую же последовательность ©[(¿Ж*^, ..., из и г местного, ..., местного отношения на носителе А. Эти отношения получак «применением» всех правил к отношениям Ль ..., Иг структуры 5 отношениям . -., 5

Точнее, ..., а n)e*Sj (п - арность переменной если найдется та правило З'/хь хп)<г-Ьг, в тгь и для переменных^, гг, ..., г / в Ьг, ..-, Ьк, отличных от ..., хп найдутся такие элементы сь с2, ... носителя Л, что одновременно

• Для литерала имеющего вид Я т), верно (61, .,., Ь т)&Лч\ Ьи = ап еспнуи =хх>, иби= с*., еслиуи = г^.

• Для литерала имеющего вид -Ля(уи ...,ут), верно {Ьи ..., Ът)<£ где6и = ау, если>'11 = ху, и Ьи= с», еслиуи = г„.

• Для литерала Ьр имеющего вид Яр(уи ..., ут), верно {Ьи..., Ьт)е$р; Ьи = я„, если^„ ~Ху, иЬи= =

Получающийся оператор ©1 монотонен, и можно рассмотреть наименьшую неподвижную точку 0,™ (в упорядоченном множес последовательностей £=(<£1, •■■> состоящих из «1-местного отноше! «Уь ..., «^-местного отношения на носителе А, с покомпонентн порядком, на каждой компоненте являющимся теоретико-множественн включением подмножеств из соответствующей декартовой степени Определим, ©,° = 0 = (0, ..., 0) и О,'*1 = ©КвД тогда ©Г = илей®Л объединение берется покомпонентно. Неподвижная точка достигается конечном шаге, так как носитель нашей модели конечен.

После этого рассмотрим расширенную сигнатуру а^аи {6ь <5

[ученная наименьшая неподвижная точка ©^ вместе со структурой 91 азует реляционную структуру 91]=(А; Я\, ..., Яг, -Уь ..., 5.,) для «туры Сть

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

$ случае правдоподобных рассуждений типа ДСМ исходная сигнатура а

гржит следующие предикатные и индивидные константы:

ернарная предикатная константа У=Х1лХ2, представляющая бинарную

операцию локального сходства; (ндивидная константа 1 выделяет тривиальное сходство; !инарные предикатные константы Т<+1,1>(Х=>ЛУ), ^.¡^(Х^Ш) и Х;Т)1>(Х=>1Ш) описывают, какие свойства объект X проявляет, какие -нет, а проявление каких неизвестно, ^ля представления простой (симметричной без проверки существования тр-примеров) стратегии добавим следующие предикатные переменные: »инарные предикатные переменные 1+(У, 1-ОЛ служат для

нахождения всех пересечений; »инарные предикатные переменные 1<-цд>(У=>2^), •Ц111>(У=>2\^0 и представляют гипотезы о причинах проявления свойств, причинах отсутствия свойств и противоречивые гипотезы; }<+11>(Х=>1\У) и Е<.и>(Х=>^) - бинарные предикатные переменные, соответствующие проверке критерия достаточного основания правдоподобного вывода; <+1;1>(Х=>^), Д<.1Д>(Х=>^), 1<о,1>(Х=>^) и - бинарные

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

1а этом языке простая стратегия правдоподобных рассуждений типа М с одним свойством \\^={р} может быть записана как логическая грамма:

:+(у, w)<- ^¡мх^Щ ъ+ю^^у/), у=х,лх2, у*±

+(У, W)<- 1<+1,о>(Х=>^), 1+(Уь W), У=ХАУь

.(V, W)<- 1<.]_о>(Х1=>^), ^.,,о>(Х2=>^), У=Х,АХ2, У*±

:.(У, \\0<- .1<-1,0>(Х^>1\¥), 1.(УЬ W), У=ХдУь У*±

.Г<0Л>(У=>2\У)<- 1+(У, \У), 1.(У, ^ .1<+1Л>(у=>2\у)<- и(у, w), ^<0Л>(У^>2\У) Л>(У=>2\\0<- 1.(У, Щ, '•1<о,1>(У—:^2^) •1<о,1>(Х=>^)<— 1<11о,(Х^1¥), -Г<+и>(У1=^), ,Ц1Л>(У2=>2\У), У!=Х/ У2=ХлУ2

Е<+11>(Х=>^)<- 1<+1о>(Х=>^), ]<+ииУ=>2Щ, У=ХлУ Е<_11>(Х=>^)<— 1<.1,0>(Х=>^), Л<.1л>(У=>2\У), У=ХдУ 1<+11>(Х=>^)<- 1<г_о>(Х=>^), ,1<+и>(Уо2\У), У=ХлУ, -,1<0>]>(Х=>^)

1<т,о>(х=>^), .ци>(У^2\У), У=Хлу, Х^Х^Ш)^ -Л<+1.1>(Х=>,^, -¿<-1,1>(Х=>1

^1<ол>(Х=>^)

Описанную программу полезно сравнить с классическим описан простой стратегии, занимающим три страницы!5 Отметим также, что как "\\/={р}, то все встречающие в вышеприведенной програ! предикатные переменные могут быть заменены унарными, использовали настоящие обозначения лишь для естественности сравне нашего изложения с классическим.

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

Первоначально изложенная в [2] с использованием многознач многосортной логики предикатов с кванторами по конечным множестг несимметричная стратегия правдоподобных рассуждений в диссерта: описана стратифицированной логической программой, с использован; следующих реляционных переменных:

бинарная реляционная переменная А+(2, У, \У) служит для вычисле

всех препятствий гипотезы У=>2\У; переменная В+(Х, V, \У) - для определения заблокированных приме

противоположного знака; С+(У, \У) - для наличия контр-примеров;

0+(Х, V, ЧУ) и Р+ (X, - переменные, служащие для проверки нали незаблокированной причины.

5 Страницы 40-^42 из работы: Финн В.К. Правдоподобные выводы правдоподобные рассуждения // Итоги науки и техники. Сер. Теория вероятное Математическая статистика. Теоретическая кибернетика. Т. 28. - М.: ВИНИ 1988.-С. 3-84.

Остальные переменные обозначают то же, что и ранее. Мы отказались от введения тернарного оператора Т(Х, Е, XV), где 5 -ожество всех минимальных Ъ с У, \У), что можно сделать путем рачительного усложнения программы. Такой тернарный предикат ник при описании (симметричной) обобщенной стратегии шдоподобных рассуждений и использовался в [2]. В диссертации сазано, что при «классической» несимметричной стратегии из базы гных с вычисленными сходствами выводятся в точности те же предикаты

что и из

шеденной ниже программы:

;+(у, \у)*- 1<+1,0>(х,=>^), 1<+1,0>(х2=>^), у=х,дх2, у*± +(у, w)<- 1<+1,0>(х^лу), 1+(у, чу), у=хауь у*± иг, v, 1+(у, \\о, ;<.1,0>(х1=^1\¥), у=х,ау, 1<., 0>(х2=>^), у=х2лу, г=хглх2,

v, \у)<- а+(гь v, \у), ;<.ио>(х=>^), у=хлу, г=хл2и ъм }+(х, v, w)<- а+(2, v, щ, 1<.,,0>(х=>^), :+(у, \у)<- 1+(у, w), л<.1,0>(х=о^), у=хду, -1в+(х, v, \у) <+и>(у=>2\у)<- i +(у, w), -,с+(у, х(х, v, \у)«- -1<+м>(у=>2\у), а+(2, v, w), ъ=хаъ ч(х, \¥)<- 1<+и>(у=>2>у), у=хлу, -,щх, v, w) :<+и>(х=>!\\0<- 1<+1.0>(х=>,^, р+(х, \у) <<.и>(х=>,чу)<- -|б-ц(х,

<+1)1>(х=>^)<- ^(хг^), б+(х, \¥) <.и>(х=^\у)<- 1<т>0>(х=^,ш), -^+1(х, w)

ша II

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

такой ситуации каждый пример исследуемого явления может породить

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

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

тернарные предикатные константы о и и обозначают обычные опера1 пересечения и объединения на множестве связанных переменных; индивидная константа 0 представляет пустое подмножество; бинарные предикатные переменные К+(Х, W) и К_(Х, \У) обозначают, какие-то переменные из подмножества являются положительнь (отрицательными) для объекта X;

тернарные предикатные переменные Ь.(Х, V, W) и Ь+(Х, V, W) служат , записи того факта, что хотя гипотеза ]<+]1>(У=>2^/) (соответстве] -Г<-и>(У=>2\У)) и входит в объект X, она не применима из-за конфликт гипотезой противоположного знака, также входящей в X.

Остальные переменные и константы обозначают то же, что и ранее.

Вот требуемая программа: 1+(У, \\0<- ^^(Х^УО, 1<+1,0>(Х2=^1У2), У=Х,дХ2, ЧГ*0, V

1+(У, 1<+1,о>(Х=>1У), 1+(У1, У=ХлУ], \У=Уп\Уь У*± 1.(У, )<- 1<.ио>(Х,^,У1), :<-1,0>(Х2=>1У2), У=Х,лХ2, >У=У1пУ2, \У*0, V. 1.(У, \¥)<- 1<_|>0>(Х=>1У), 1.(УЬ W1), У=ХлУь Ы=УпУ/ь Ш0, У*±

.Г<0 ^(У^^)*- 1.(У, У/), 1+(У, Wl), W2^0

К+(Х, \\0<- ^+1о>(Х1=>1У), Wl=YnW, W1*0 К.(Х, )<- 1<_1,0>СХ1=>1У), \У1=УгЛ\г, 1<+и>(У=>2>У)^ I +(У, \У), -Л<ол>(У=>2\\0 .Ци>(У=>2\У)<-1.(У, W),

^(Х^^)*- 1<+1,0>(Х=^1У), ^дДУ^ХУ), -,К.(Х, Щ, У=ХлУ, W=YnW

1>(Х=>,У)<- Е<+1д>(Х=>^0, Е<+1,1>(Х=>^2), ¥=№^2 ,>(Х=>^)<- ^.оСХ^У), 5<-11>(У=>2Ш -пК+(Х, W), У=ХлУ, \¥=Уп\У [>(Х=>!У)-е- Е<.и>(Х^^,), Е<.1)1>(Х=>1\^2), У=\уи\*/2 V, W)<- 1<,1,1>(У=>2\У), .1<.1,1>(У1=>2\У), У=ХаУ, У^ХЛУь -^К.(Х, W), ^К+(Х, Ш,), W2=WnWь (,У,\У)<- 1<+1>1>(У11^2\У1), У=ХдУ,

^К+(Х, ^К.(Х, W1), W2=WnWь .(Х=>№)<- 1<+1>1>(У1=>^,), У1=ХлУь

^К.(Х, W1), -пК+(Х, W2), W=W1nW2 .(Х=>1У)<- То.гДХ^^О, ;<о,1>(Х=>^0, У^иХУ >(Х=>,\У)«-1<+1;о>(Х=>^)

>(Х=>1)У)<- 1<т,о>(Х=>1У), -К.(Х, V/),

>(Х=>!У)<- ^л.гДХ^^О, ;<+1>1>(Х=>^2), У=\уи\¥2 >(Х=>№)<- 1<.1,0>(Х=^,\¥)

>(Х=^)<- 1<Г,0>(Х=>,У), J<.U>(V=>2W), ^К+(Х,\\0,

(Х^У)<- и,о>(Х=>1Уо), -Л<+и>(Х=>,У), -^^(Х^У), ^<0Л>(Х=о,У)

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

?ема (Биркхоф, Стоун). Решетка дистрибутивна тогда и только тогда, 1а она изоморфна некоторому кольцу множеств.

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

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

У,=ХАУЬ У2=ХаУ2,

У=ХЛУ,

У=ХлУ,

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

Впрочем, следует отметить, что на практике часто нужен лишь о1 частный случай дистрибутивной решетки - шкала (линейно упорядочег множество). Например, в случае непрерывных значений биологичес активности после задания нескольких порогов возникает шкала.

При исследовании солидарного поведения рабочих знача принимаемые ответами, были +1 (сильная уверенность) и +'А (предпочте перед альтернативой). Возможно несколько моделей причш следственных зависимостей6:

1) Предполагается, что различие в степени несущественно, важна л направленность. Тогда мы истинностные значения (+1 и +Уг) и ( -/4) отождествляются, и мы их представляем единствен переменной, принимающей значения +1 и-1 соответственно.

2) +!4 рассматривается как «слабая» (недостаточно выраженная) Тогда мы используем две связанные переменные, причем представляется комбинацией (+1,+1), а +14 - (0,+1).

3) Механизмы, обуславливающие проявления различных степеней (+14) наличия (или отсутствия) свойств, различны. Снова достатс двух связанных переменных, только теперь +1 представля! комбинацией (+1,0), а +14 - (0,+1>.

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

6 Михеенкова М.А. Развитие ДСМ-метода автоматического порождения гиг дня его применения при анализе социологических данных типа «субъек поведение» // Автореф. дисс. канд. техн. наук. М.: ВИНИТИ. - 1998-28 с.

ава III

Третья глава диссертации посвящена расширению правдоподобных суждений типа ДСМ на ситуации, в которых число глобальных сходств кет быть экспоненциально велико от числа исследуемых объектов. I! такой ситуацией ученые-социологи столкнулись в первых периментах по исследованию солидарного поведения рабочих. Хотя ло опрошенных респондентов не достигало двух сотен, а каждый пондент описывался сотней признаков, число гипотез о причинах, южденных решателем интеллектуальных задач, превзошло 12 с овиной тысяч.

Гакая возможность теоретически всегда наличествует, так как пример к (п-1 )-подмножеств из множества с п элементами показывает, что число бальных сходств может достигать 2"-л-2, хотя число обучающих [меров равно п.

J такой ситуации или приходится мириться с проблемами сложности шслений и трудностью осмысления результатов, или необходимо аничиться быстрым вычислением лишь некоторых из наиболее ересных гипотез о причинах исследуемых свойств. } дальнейшем мы будем предполагать, что обучающие примеры сываются множеством признаков, т.е. являются подмножествами оторого универсального множества Е. Мы ограничимся также нственным свойством {р}.

зеделение. Двудольный граф - это граф G = (V, Е), в котором множество шин разбито на два подмножества (называемых долями) V=V\ uV2, ^V2 = 0, так, что En([V{f u[F2]2) = 0. Иначе говоря, ребра соединяют шины из различных долей (Е с [ Fix V2]).

Тример двудольного графа можно образовать из множества ожительных примеров. Положим V\ - ЭС+, V2 = Е и в Е добавим ребро а), где X е 9С+ и а е 2, если и только если пример X имеет признак а. )еделение. Полным двудольным подграфом в двудольном графе (Vi kjV2,E) называется такая пара подмножеств W\ crFi и W2 cV2, что хЩ с Е. Иначе говоря, каждая вершина одного подмножества смежна дой вершине другого.

»еделение. Полный двудольный подграф (Wh W2) двудольного графа G зшается максимальным (по включению), если никакой полный цольный подграф графа G не содержит графа (Щ uW2, [W\xlV2]).

Другими словами, каждая вершина, не попавшая в IV\ (соответственно И не является смежной некоторой вершине из Щ (соответственно Щ).

Глобальные положительные сходства в смысле ДСМ-мет< соответствуют максимальным полным двудольным подграфам двудольн< графа, построенного по положительным примерам. Определение. Двудольный граф (У\ иУ2, Е) определяет две антитонн функции замыкания (1:2Г\—>2У2 и ¡: 2К2-»2К1 по правит «ТО ={у£Г2\Чхе IV! {*, >;} е Е} и 1(Ж2) = {хе¥,\ \/уе Иг2{х, Я е Е). Определение. Замыканием максимального полного двудольного подгрг (Щ, ^2) в двудольном графе иК2, Е) относительно элемента <хе(^1 \ 1 (соответственно относительно ае(У2 \ Щ)) называется максимальн полный двудольный подграф (¡((1({а}и^)), с!({а}и^)) (соответстве! (1({а}иГ2),с1(К{а}иГ2)))).

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

Пусть О - очень большое (но конечное) множество комбинатор! структур, и пусть (д. - распределение вероятностей на О. Задача - выбр элемент О случайным образом согласно распределению ц. Подход сост в построении конечной цепи Маркова, чьим пространством состоя] является О и чьим стационарным распределением - ц. Цепь должна б эргодической (сходимость к стационарному распределению имеет ме вне зависимости от начального распределения). Теперь, начиная с люб элемента О, мы должны моделировать достаточно большое число Т шг построенной цепи Маркова и выдать заключительное состоя] Эргодичность цепи Маркова гарантирует, что распределе заключительных состояний будет произвольно близко к требуем распределению ц.

Для нашей задачи элементами £2 будут положительные гипот< удовлетворяющие запрету на контр-примеры. Единственным отличиед классического ДСМ-метода будет допущение дополнительно: 1. (наибольшей) гипотезы, имеющей все множество признакот объявленной сходством пустого множества примеров;

гипотез, состоящих из единственного примера с соответствующим множеством признаков, если последнее множество не включается во множество признаков как никакого другого положительного, так и никакого отрицательного примера;

(наименьшей) гипотезы, являющейся сходством всех положительных примеров и имеющей (возможно пустое!) множество общих признаков, гели у нее нет контр-примеров.

да обеспечения эргодичности цепи Маркова достаточно, чтобы она а неприводима и апериодична. Путем добавления гипотез 1) и 2) выше обеспечиваем неприводимость. Апериодичность обеспечивается тем, с вероятностью не меньшей Vi цепь не изменяет свое состояние, ададим переходы из состояния ( Wu W2) следующим правилом: ; вероятностью Уг состояние не изменяется;

з противном случае, из множества (9í+ \ ífi)u(£ \ W2) выберем случайный элемент а (равномерно распределенный), зели ае(2 \ W2), то перейдем на замыкание (Wi, W2) относительно а. гели ае(9^ \ Wi) и если замыкание W2) относительно а не имеет <онтр-примеров, то перейдем на это замыкание; иначе - останемся на

w2y

lar 1) обеспечивает апериодичность. На шаге 4) мы уменьшаем •тезу, вычисляя сходство имеющейся гипотезы с некоторым новым лером. Он соответствует шагу известного алгоритма «замыкай по >му»7 На шаге 3) мы, наоборот, увеличиваем гипотезу, добавляя олько признаков. Поэтому на нем проверка на контр-примеры тствует.

отя эргодичность обеспечивает асимптотическую сходимость к ионарному распределению вне зависимости от начального ределения, мы предлагаем начинать с состояния (i(X), d(i(A))), где X— кество признаков, описывающих пример, предложенный для прогноза, [ы описали «положительную половину» алгоритма, которая посвящена ку сходства положительных примеров. Вторая (отрицательная) овина» устроена аналогично. Теперь остается лишь запустить их ¡временно и ожидать, когда какая-либо процедура возвратит ответ, [ожно привести аргументы в пользу того, что аналогия имеет ятностный характер. (Какой смысл у выражения «удачная аналогия»?)

знецов С.О. Быстрый алгоритм построения всех пересечений объектов из шой полурешетки // НТИ, Сер. 2, № 9, 1993, с. 11-21.

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

На практике, недостатком нового подхода является возможн пропуска интересных гипотез. Но главный недостаток - отсутс механизма управления обучающей выборкой. В классическом ДСМ-ме таким механизмом является проверка критерия достаточного основ индуктивного вывода.

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

Основные результаты работы

Обоснована необходимость расширения логики первого порядка для описания стратегий правдоподобных рассуждений типа ДСМ. Установлена невозможность построения корректной и полной дедуктивной системы для логики с кванторами по конечным множествам.

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

Введены несимметричные стратегии правдоподобных рассуждений, основанных на предположении, что отсутствие проявления свойства объясняется отсутствием (незаблокированной) причины для его проявления.

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

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

Основные результаты диссертации изложены в следую!

публикациях:

1. Виноградов Д.В., Замечание о логическом языке с кванторами конечным множествам // Труды 2-й Всесоюзной конферег «Искусственный интеллект - 90», Минск, САИИ, 1990, Т. 1, С. 124-1

2. Виноградов Д.В., Несимметричный ДСМ-метод с учетом контекс Труды 5-й Национальной конференции «Искусственный интелле! 96», Казань, РАИИ, 1996, Т. 2, С. 322-324.

3. Виноградов Д.В., Связанные ДСМ-активности // Proc. 3d Internat. С "Information Resources, Integration and Technologies" M.: ВИНИТИ, 1 -С. 59.

4. Виноградов Д.В., Логические программы для квази-аксиоматичес теорий // «Научно-техническая информация» Сер. 2, М.: ВИНИ 1999, № 1-2, С. 61-64.

5. Виноградов Д.В., Быстрый поиск аналогий с помощью цепей Марко Proc. 4th Internat. Conf. "Integration, Information Technologies Telecommunications" M.: ВИНИТИ, 1999, Special issue «Intelli Systems for Automated Support of Scientific Research», С. 11-14.

6. Виноградов Д.В., Модель вероятностных алгоритмов // «Hay техническая информация», Сер. 2, М.: ВИНИТИ, 2000, № 3, в печатг

Введение.

Глава 1.

Логические проблемы формализации правдоподобных рассуждений

§ 1. Логика первого порядка.

§2. Кванторы по конечным множествам.

§3. Стратифицированные логические программы.

§4. Несимметричная стратегия правдоподобных рассуждений.

Глава 2.

Алгебраические структуры свойств

§ 1. Стратегии для связанных активностей.

§2. Общие структуры свойств.

§3. Пример: социологические модели.

§4. Напоминание: условия дистрибутивности.

Глава 3.

Рандомизированные алгоритмы правдоподобных рассуждений

§1. Графы для поиска сходств.

§2. Основной алгоритм.

§3. Анализ алгоритма.

Уже в начале 1970-х голов стало очевидно, что рассуждения эксперта не могут быть описаны исключительно в дедуктивных терминах. Дж. МакКарти [5], Р. Рейтер [7] и их ученики [6] развили подходы к «рассуждениям здравого смысла» на основе различных систем немонотонных логик. П. Гарденфорс [4] и др. исследовали математические основы пересмотра теорий. Однако, несмотря на известное изящество предложенных конструкций, все эти теории так и не привели к прикладным системам, осуществляющим автоматизированные рассуждения в конкретных предметных областях.

В конце 1970-х годов группа исследователей под руководством профессора В.К. Финна [18], [19] существенно продвинулась в формализации средствами многозначных логик, расширении и обобщении процедур индукции (названных в честь Д.С. Милля — создателя концепции индуктивных методов [14] — ДСМ-методом автоматического порождения гипотез). Правдоподобные рассуждения типа ДСМ соединили в себе индукцию на эмпирических данных, рассуждения по аналогии, конструктивную абдукцию и дедуктивные выводы. На основе предложенной теории были созданы прикладные интеллектуальные системы в помощь исследователям-фармакологам при компьютерном конструировании лекарств, ученым-социологам при исследовании индивидуальных поведенческих готовностей и другие.

Напомним основную схему правдоподобных рассуждений типа ДСМ. Они основаны на возможности вычисления сходства объектов из обучающей базы данных. На первом этапе находятся глобальные сходства объектов. Происходит шаг индуктивного обобщения. Затем вычисляются условия, препятствующие действию гипотетических «причин». Эти условия подразделяются на логические (например, запрет на контр-примеры) и структурные (обобщенная стратегия правдоподобных рассуждений). На основании порожденных гипотез предсказываются свойства новых объектов. При этом предсказание осуществляет перенос свойств известных объектов на новые объекты по аналогии. Наконец, порожденные гипотезы проверяются на полное и адекватное описание данных из обучающей базы данных. Если проверка заканчивается успехом, то порожденные гипотезы представляют собой конструктивную абдукцию. В противном случае, объекты, не получившие объяснения, предъявляются эксперту для пополнения обучающей базы данных объектами, сходными с предъявленными, в (полу) автоматическом режиме. В дальнейшем возможна итерация вычислений с пополненной базой данных.

Для описания причинно-следственных зависимостей (без учета структурных запретов) необходимо рассматривать элементы сорта «объект» (переменные X с индексами), сорта подобъею» (переменные Z и V с индексами) и сорта «(под)множество свойств» (переменные У, и и \5(7 с индексами). Основные отношения «объект X обладает множеством свойством У» и «подобъект V является причиной наличия множества свойств представляются бинарными предикатами X =>1 У, V =>2 W. Однако, для формального представления правдоподобных рассуждений необходимо было расширение классической многосортной логики предикатов первого порядка в двух направлениях: многозначность и кванторы по конечным множествам (или кортежам переменной длины).

Так как исходная база данных содержит неполную информацию о свойствах изучаемых объектов, то приходится вводить дополнительные истинностные значения. В итоге, получаем следующие внутренние (расщепляемые в случае итерации) истинностные значения: (+1) — фактическая истина, (-1) — фактическая ложь, (0) — фактическое противоречие, (т) — неопределенность. Кроме того, имеются стандартные внешние истинностные значения I (логическая истина — выделенное значение) и £ (логическая ложь).

Для каждого внутреннего истинностного значения вводятся соответствующие 1-операторы Россера-Тьюкетга: = 1:, если X = v, и = £, если А, Ф v. Формулы вида 1У(Ф), где Ф — произвольная формула, а v — внутреннее истинностное значение, назовем 1-формулами. .[-формулы вида 1У(Ф), где Ф — атомарная формула, назовем Д-атомарными. Формулы, построенные из 1-формул с помощью обычных логических связок логики первого порядка, назовем внешними. Внешние формулы, содержащие только 1-атомарные .[-формулы, назовем нормальными.

На внутренних истинностных значениях можно определить связки и кванторы. Нужно только позаботиться о том, чтобы для любой внешней формулы существовала эквивалентная ей нормальная формула. Такие многозначные логики называются .[-определимыми. Критерий 1-опр е делимо сти и теорема об аксиоматизируемости многозначных (бесконечнозначных с конечным числом типов истинностных значений) логик были установлены О. М. Аншаковым, Д. П. Скворцовым и Б. К. Финном [8], [9],

Но гораздо более радикальным расширением было введение кванторов по конечным множествам. Они использовались для записи условия глобальности сходства как необходимого признака причины множества свойств. Глобальное сходство примеров [11] определяется через сходство такого множества примеров, которое не может быть расширено без уменьшения сходства. Это условие апеллирует к конечному, но заранее не фиксированному числу примеров.

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

Главные цели настоящей работы — разработать логический формализм для описания ДСМ-метода, наиболее знакомый специалистам по искусственному интеллекту; исследовать вопрос о представлении шкалированных свойств; а также предложить методы правдоподобных рассуждений типа ДСМ для больших решеток гипотез.

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

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

Результаты работы докладывались на национальных конференциях по искусственному интеллекту, международных конференциях «Intégration, Information Technologies and Telecommunications» 97 и 99, общемосковском семинаре по искусственному интеллекту под руководством проф. В.Н. Вагина, проф. О.П. Кузнецова и проф. В.К. Финна, научно-исследовательском семинаре сектора интеллектуальных систем ВИНИТИ.

Тяава 1

Логические проблемы формализации правдоподобных рассуждений

1. Anshakov О.М., Finn V.K., Skvottsov D.P. On axiomatizarion of many-valued logics associated with fomialization of plausible reasoning / / Stadia Lógica. - 1989. - Vol. 48, № 4. - P. 423-447.

2. Börger E. Decision Problems in Predicate Logic / / Logic CoIloquiuin'82.Amsterdam: North - HoUand, 1984. - P. 263-301.

3. Chandra A., HarelD. Horn clause queries and generalizations / / Journalof Logic Programming, -1985. - Vol. 2, № 1 - P. 1-15.

4. Gardenfors P. Conditionals and Changes of Belief / / Acta PhilosophicaFennica. - 1978. - Vol, 30. - P. 381-404

5. McCarthy}. Application of Circumscription to FormalizingCommonsense ICnowledge / / Artificial InteHigeace J, - 1986. - Vol, 28. - P . 89-116.

6. McDermott D., Doyle J, Non-monotonic Logic I / / Artificial IntelligenceJ. - 1980. - Vol. 13. - P, 41-72.

7. Reiter R. A Logic for Default Reasoning / / Artificial Intelligence J.1980.-Vol 13.-P, 81-132,

8. Аншаков O.M., Скворцов Д-П., Финн B.K, Логические средстваэкспертных систем типа ДСМ / / Семиотика и информатика. — 1986. -Вып, 28-С. 65-101.

9. Аншаков О.М., Скворцов ДП., Финн В.К, Аогические средстваДСМ-метода автоматического порождения гипотез / / Научнотехническая информация, — Сер. 2 — 1987. — № 9. — 9—17.

11. Кемени Дж., Снелл Дж, Конечньге цепи Маркова, М.: Наука, 1970.

12. Кузнецов С О . Быстрый алгоритм построения всех пересеченийобъектов из конечной полурешетки / / Научно-техническая информация, - Сер. 2 - 1993. - № 9. - С, 11-21.

13. Милль Д.С. Система логики силлогистической и индуктивной. М.:Книжное дело, 1900.

14. Михеенкова М.А. Развитие ДСМ-метода автоматическогопорождения гипотез для его применения при анализе социологических данных типа «субъект поведение» / / Автореф. дисс. канд. техн. наук. М.: ВИНИТИ. - 1998 - 28 с,

15. Скворцов Д.П. О некоторых способах построения логическихязыков с кванторами по кортежам / / Семиотика и информатика. 1983.-Вып. 20-С. 102-126.

16. Трахтенброт Б.А. О рекурсивной отделимости / / Доклады АНСССР. - 1953. - Т. 88 - 953-955.

17. ФиннВ.К. О возможностях формализации правдоподобныхрассуждений средствами многозначных логик / / VII Всесоюзный симпозиум по логике и методологии науки. — Киев: Наукова думка, 1976.-С. 82-83.

18. ФиннВ.К. Базы данных с неполной информацией и новый методавтоматического порождения гипотез / / <Диалоговые и фактографические системы информаггионного обеспечения». М: Наука, 1981.-С. 153-156.

19. Финн В.К. О машинно-ориентированной формализацииправдоподобных рассуждений в стиле Ф. Бзкона - Д.С. Милля / / Семиотика и информатика. - 1983. - Вып. 20- 35-101.

20. Финн В.К. Правдоподобные выводы и правдоподобные рассуждения/ / Итоги науки и техники. Сер. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. Т. 28. - М.: ВИНИТИ, 1988. - 3-84.

21. Финн В.К. Об обобщенном ДСМ-методе автоматическогопорождения гипотез / / Семиотика и информатика. - 1989. — Вып. 29- 93-123.

22. ФиннВ.К. ДСМ-метод автоматического порождения гипотез сотношением порядка / / Семиотика и информатика. - 1990. — Вып. 31- 69-103.

23. Финн В.К, Михеенкова М.А. Некоторые проблемы обобщенногоДСМ-метода автоматического поро>едения гипотез / / Семиотика и информатика. - 1993. - Вып. 33 - 136-163.