Содержание к диссертации
Введение
Глава 1 Что такое ДСМ-метод автоматического порождения гипотез? 7
Глава 2 Теоретико-множественный подход 30
Глава 3 Обобщенный ДСМ-метод для работы в условиях неравнозначности признаков 48
Глава 4 Другие модификации 63
Заключение 78
Список литературы 81
Приложение 1 87
Приложение 2 89
Приложение 3
- Что такое ДСМ-метод автоматического порождения гипотез?
- Теоретико-множественный подход
- Обобщенный ДСМ-метод для работы в условиях неравнозначности признаков
- Другие модификации
Введение к работе
За последние два десятилетия произошел стремительный рост технических возможностей для сбора и хранения больших массивов данных. И этот рост продолжается. Уже накоплены миллионы баз данных, которые охватывают практически все области человеческого знания. Подобный рост объема хранимых данных остро поднимает проблему поиска данных, а также, что еще более важно, порождает необходимость в средствах, позволяющих автоматически извлекать полезные знания из больших массивов данных. Именно к таким средствам и относится Интеллектуальный анализ данных (ИАД) .
ДСМ-метод автоматического порождения гипотез, о котором пойдет речь в данной работе, объединяет в себе целое семейство методов, задача которых заключается в том, чтобы на основании имеющейся базы фактов сделать предположения о причинах наличия или отсутствия определенных свойств у объекта.
Интеллектуальный анализ данных (англ. Data Mining) - выявление скрытых закономерностей или взаимосвязей между переменными в больших массивах необработанных данных. Подразделяется на задачи классификации, моделирования и прогнозирования и другие.
Термин «Data Mining» веден Григорием Пятецким-Шапиро в 1989 году. Английский термин «Data Mining» не имеет однозначного перевода на русский язык (добыча данных, вскрытие данных, информационная проходка, извлечение данных/информации) поэтому в большинстве случаев используется в оригинале. Наиболее удачным непрямым переводом считается термин «интеллектуальный анализ данных» (ИАД) [3].
Особенно актуальным является разработка методов ИАД, которые могут действовать в условиях неполноты данных, а также когда эти данные содержат объекты, характеризуемые семантически неравнозначными атрибутами, т.е. какая-то часть атрибутов считается более значимой, а какая-то - менее, что позволяет ранжировать атрибуты по их значимости.
Цель работы
Разработать систему правил и алгоритмов такого варианта ДСМ-метода автоматического порождения гипотез, который позволял бы оперировать объектами, имеющими неравнозначные атрибуты.
Новизна
В работе автор впервые предлагает версию ДСМ-метода, позволяющую работать с предметными областями, где объекты описываются набором неравнозначных атрибутов (атрибутов с весами), решая задачи интеллектуального анализа данных в предметных областях связанных с оценкой рисков (страхование, инвестиции, управление проектами).
Автору неизвестно работ, в полной мере охватывающих излагаемый материал.
Теоретическая значимость
Разработан понятийный аппарат для разновидности ДСМ-метода, предназначенной для работы в предметных областях, где структура объектов характеризуется неравнозначными атрибутами.
Проведено систематическое изложение основных понятий, положений и правил ДСМ-метода на язык теории множеств, что позволяет говорить на одном языке с разработчиками систем анализа данных, которые зачастую далеки от имеющейся в рамках ДСМ-метода традиции. Также было введено понятие семантической силы гипотезы и доказан ряд утверждений о выразительной и семантической силах гипотез.
Практическая значимость
На данный момент существует множество систем ИАД, однако лишь незначительная их часть занимается работой с контестно-зависимыми данными. Также невелика доля систем, работающих с объектами, описываемыми атрибутами, неравнозначными между собой. При этом, как правило, два этих множества не пересекаются.
Предлагаемый метод призван заполнить эту нишу, возникшую из-за нехватки систем, ориентированных на работу с контекстно-зависмыми данными, где атрибуты объектов были бы неравнозначны между собой.
Основные результаты
1. Был построен формальный аппарат для описания ДСМ-метода автоматического порождения гипотез, использующий язык теории множеств. Такой подход к описанию ДСМ-метода делает его более понятным рядовому программисту, не требуя от него дополнительных специфических знаний.
2. Был разработан логико-математический аппарат для описания разновидности ДСМ-метода, работающей с объектами, характеризуемыми семантически неравнозначными атрибутами.
3. Был построен алгоритм работы ДСМ-системы на основе упомянутого выше варианта ДСМ-метода.
4. Была разработана экспериментальная версия ДСМ-системы, реализующей упомянутые выше алгоритмы.
Апробация
Промежуточные результаты и итоги проведенной работы докладывались на 49-й научной конференции МФТИ [28] и на 50-й юбилейной научной конференции МФТИ [29], а также на научном семинаре "Вычислимые методы прогнозирования" при ВЦ РАН. Основные результаты диссертации опубликованы в [30]. Итоговые результаты докладывались и обсуждались в ВИНИТИ на семинаре В.К. Финна.
Структура работы
Предлагаемая вашему вниманию работа состоит из четырех глав, введения, заключения и трех приложений. В первой главе будут рассмотрены различные виды ДСМ-метода автоматического порождения гипотез в своей канонической формулировке. Во второй главе будет предложена формализация методов, рассмотренных в первой главе, на языке алгебры и теории множеств. В третьей главе излагается новая вариация ДСМ-метода, являющаяся модификацией для контекстных ДСМ-методов (несимметричного и обобщенного), предназначенная для работы в условиях неравнозначности составляющих исходных. В четвертой главе вашему вниманию будет предложено описание прототипа ДСМ-системы, разработанной на основании ДСМ-метода для работы в условиях семантической неравнозначности структурных элементов, а также излагается ряд других модификаций, опирающихся на инженерные решения по оптимизации работы ДСМ-системы. В приложениях приводится информация по экспериментальной ДСМ-системе, созданной на основании излагаемых принципов. В первом приложении описываются требования к формату файла исходных данных. Во втором приложении описываются настройки конфигурационного файла приложения. А в третьем приложении приводится листинг с исходным кодом приложения, разбитым по классам.
Что такое ДСМ-метод автоматического порождения гипотез?
ДСМ-метод как метод ИАД В течении последних двух десятилетий произошел стремительный рост технических возможностей для сбора и хранения больших массивов данных. И этот рост продолжается. Уже накоплены миллионы баз данных, которые охватывают практически все области человеческого знания. Подобный рост объема хранимых данных остро поднимает проблему поиска данных, а также, что еще более важно, порождает необходимость в средствах, позволяющих автоматически извлекать полезные знания из больших массивов данных. Именно к таким средствам и относится Интеллектуальный анализ данных (ИАД).
ДСМ-метод автоматического порождения гипотез - это один из методов ИАД (Интеллектуального анализа данных). ДСМ-метод позволяет при помощи анализа имеющейся базы фактов сделать предположения о причинах наличия или отсутствия определенных свойств (целевые свойства) у объектов предметной области. Этот метод предложил В.К. Финн [39-41]. Примером задач, решаемых ДСМ-методом, может служить выявление причинно-следственных закономерностей вида структура-активность в фармакологии, анализ сложных химических соединений и белковых структур в химии [37, 38], медицинская Формализация структурной индукции ДСМ-метода, или JSM-метода, как его иногда еще называют, берет свое начало от известного английского философа, логика, историка и социолога Д.С.Милля, чьи инициалы и составляют название метода [32] диагностика[ 16,23], криминалистика[21], анализ социального поведе-ния[22,33,34], задачи управления роботами [24]. ДСМ-метод может использоваться для анализа данных в различных предметных областях. Однако он предъявляет определенные требования: к характеру данных, к характеру закономерностей в предметной области. ДСМ-системы обрабатывают небольшие массивы данных, так как алгоритмы ДСМ-метода имеют достаточно большую вычислительную сложность. Объекты ДСМ-метода должны быть структурированы таким образом, чтобы мы имели возможность определять их сходство (то общее, что есть у этих объектов). Закономерности предметной области должны иметь детерминистский (нестатистический) характер. [20] ДСМ-метод решает две задачи: обнаружить закономерную связь между структурирой объектов и множествами целевых свойств, предсказать наличие или отсутствие множеств целевых свойств для тех объектов с известной структурой, для которых отсутствуют сведения о наличии или отсутствии целевых свойств
В работах, посвященных ДСМ-методу, принято интерпретировать закономерную связь между структурой объекта и его целевыми свойствами как причинно-следственную. Т.е. либо считается, что фрагмент структуры объекта является возможной причиной (наличия или отсутствия) множества целевых свойств (прямой ДСМ-метод), ли бо наоборот, считается, что набор целевых свойств является возможной причиной структурных особенностей объекта (обратный ДСМ-метод).
Характерной чертой ДСМ-метода является сочетание трех разновидностей правдоподобных рассуждений:
Индуктивные рассуждения определяют некоторый способ обучения на примерах и позволяют сформировать гипотезы о возможных причинах рассматриваемых свойств объектов предметной области.
С помощью рассуждений по аналогии формируются гипотезы о наличии или отсутствии интересующего нас набора свойств у тех объектов предметной области, для которых информация (о наличии у них этих свойств) неполна или противоречива. Процедуры ДСМ-метода обрабатывают некоторое множество исходных данных (фактов или примеров). В результате исполнения процедур, соответствующих индуктивным рассуждениям и рассуждениям по аналогии, формируется некоторое множество гипотез.
Рассуждения по абдукции, основанные на применении следующего правила: если каждый факт (пример) может быть объяснен с помощью имеющихся гипотез, то гипотезы принимаются, т.е. предполагается, что они сформированы на достаточном основании. В том случае, когда посылка правила абдукции ложна, делается вывод о необходимости расширения исходного набора фактов с помощью внешних источников.
Описание формальных понятий Теоретические аспекты ДСМ-метода принято излагать на языке многозначных логик [10]. Истинностные значения в ДСМ-методе принято делить на два вида: внешние и внутренние, имеющие следующую интуитивную интерпретацию. Внешние истинностные значения — это обычные «истина» и «ложь», которые принято обозначать через t и f. С точки зрения интерпретации познавательных процессов внешние истинностные значения соответствуют внешнему, теоретическому или конвенциональному, уровню знания. С ними должна оперировать классическая логика и классические дедуктивные правила вывода [12].
Внутренние истинностные значения соответствуют внутреннему (эмпирическому или индивидуальному) уровню знания. Их четыре: «эмпирическая истина», «эмпирическая ложь», «эмпирическое противоречие» и «неопределенность». В работах по ДСМ-методу эти истинностные значения обозначаются через +1, -1, 0 и т, соответственно. Если говорить более точно, теория ДСМ-метода строится на основе бес-нонечнозначной логики, где + 1, -1, 0 и т считаются типами внутренних значений.[14]
Логика, которая используется для формализации ДСМ-метода, является гибридной, у нее есть внешняя и внутренняя часть. Внешняя часть ведет себя как классическая двузначная логика. По поводу того, как должна быть устроена внутренняя часть, существуют различные мнения. В.К.Финн предложил ряд четырехзначных логик под общим названием «логики аргументации» [46] в качестве кандидатов на роль внутренней логики ДСМ-метода. В работах Д.В.Виноградова [18] в качестве возможной внутренней логики фактически предлагается логика Белнапа.
Еще раз отметим различие между значением угловых скобок и обычных скобок. Угловые скобки обозначают, что гипотеза была получена именно на указанном шаге, в то время как обычные скобки указывают на то, что гипотеза была получена или на текущем шаге, или па одном из предыдущих. Однако следует отметить, что правила ДСМ-метода не используют логических связок внутренней логики. Т.е., та гибридная логика, которой достаточно для формализации ДСМ-метода может содержать внешние связки классической логики и J-операторы и ничего больше, что наводит на мысль о том, что можно обойтись и без использования J-операторов, средствами одной только классической логики. [12] Во второй главе будет показана одна из разновидностей подобной формализации.
В ДСМ-рассуждении кроме истинностных значений рассматривается еще три универсума: универсум объектов, универсум фрагментов и универсум свойств. Все три универсума предполагаются конечными. Кроме того, считается, что универсум объектов входит в универсум фрагментов, так как каждый объект является (максимальным) фрагментом самого себя [12].
Теоретико-множественный подход
При создании компьютерных систем на основе ДСМ-метода автоматического порождения гипотез возникает проблема компьютерного представления знаний из Базы Фактов. Наиболее естественным способом организации оказывается представление данных в виде множеств. Кажется естественным применить подобный же подход в организации данных и к теории. Определение 2.1. ДСМ-структурой будем называть кортеж J = A,0,P,V,F,H [13],rfle А — непустое конечное множество атомов, Ос р(А) - непустое конечное множество объектов (каждый объект представлен в виде множества атомов) , Р - непустое конечное множество (возможных целевых) свойств объектов , V = {+1,-1, 0, т} - множество (типов) внутренних истинностных значений (+1- истинно, -1 - ложно, 0 - противоречиво, т - неопределенно), F : О х Р — V, отображение F будем называть функцией обладания свойством, 1 Через р(А) обозначено множество всех подмножеств множества А. " Атомы, объекты и свойства - сущности произвольной природы. Например, в зависимости от конкретной области, в роли атомов могут выступать пары вида атрибут-значение, функциональные группы химических соединений, ключевые слова - любые единицы, выступающие в рамках решаемой задачи как неделимая сущность. H : р(А) xP- V, отображение Н будем называть функцией причинности . Определение 2.2. Утверждение о наличии или отсутствии у объекта целевого свойства будем называть фактом. Множество фактов образует базу фактов (БФ). Математическим представлением базы фактов является отображение F из определения 2.1.
Интуитивный смысл функции F можно описать следующим образом: F(o, р) = +1, если объект о є О обладает свойством/? є Р (утверждение о том, что объект о обладает свойством р, истинно). Объект о будем называть плюс-примером свойства р. Множество всех плюс-примеров для свойства/? будем обозначать через О (р). F(o, р) = -1, если объект о не обладает свойством р. Объект о будем называть минус-примером свойства р. Множество всех минус-примеров для свойства/? будем обозначать через 0 (/?). F(o, р) = т, если неизвестно обладает ли объект о свойством/?. Объект о будем называть т-примером свойства р. Множество всех т-примеров для свойствар будем обозначать через От(р). F(o, р) - О, если для объекта о и свойства р установлено фактическое противоречие. Объект о будем называть нуль-примером свойства /?. Множество всех нуль-примеров для свойства р будем обозначать через О (/?). Определение 2.3. Любое подмножество множества атомов А будем называть фрагментом . " Будем считать, что свойства атомистичны и их можно рассматривать по отдельности. Поэтому здесь и далее будем говорить для случая, когда целевое свойство одно. В противном случае вместо множества Р выступает р(Р). Заметим, что согласно последнему определению объект является частным случаем фрагмента [14]. Интуитивный смысл функции Н можно описать следующим образом: H(s, р) — + 1, если фрагмент s с: А является причиной наличия свойства/? є Р (плюс-причиной для свойствар). Множество всех плюс-причин для свойствар будем обозначать через S+(p). H(s, р) — -1, если фрагмент s является причиной отсутствия свойства/? є Р (минус-причиной для свойства/?). Множество всех минус-причин для свойства р будем обозначать через S (p). Щя, р) — О, если фрагмент s является нуль-причиной для свойства/? є Р. Множество всех нуль-причин для свойства/? будем обозначать через S(/?). H(s, р) = т, если фрагмент s является т-причиной для свойства/? є Р. Множество всех х-причин для свойства/? будем обозначать через S». Определение 2.4. Будем говорить, что между двумя объектами О/, о? є О имеется сходство, если о і Г) о? 0. На предмет того, что именно брать за сходство есть две точки зрения. Согласно первой, которая является классической, некоторый фрагмент/с: А является сходством двух объектов о/, 02 є О, если 0 Ф f— (о/ П о2). Однако порой более удобно бывает рассматривать наличие сходства не как равенство, а как включение. Там мы будем говорить, что некоторый фрагмент/с А является сходством двух объектов о і, о2 є О, если 0 ь/с (о/ П о2).5
Рассмотрим алгоритм работы ДСМ-системы. Наглядно он представлен на приведенной ниже схеме (рис. 2-1). Кратко обозначенные на этой схеме этапы можно описать следующим образом:
Напомним, что любой обьект мы представляем в виде множества атомов (см. определение 2.1.) Обработка базы фактов (препроцессинг): получение данных из БФ, формирование множеств плюс-примеров и минус-примеров.
Пересечение: построение множества всех возможных непустых пересечений плюс-примеров и построение множества всех возможных непустых пересечений минус-примеров.
Индукция: выдвижение кандидатов в плюс-гипотезы и выдвижение кандидатов в минус-гипотезы.
Аналогия: выдвижение гипотез о наличии / отсутствии целевого свойства у объектов, доопределение базы фактов.
Условие завершения: Процесс работы ДСМ-алгоритма может быть как одношаговым, так проходящим в несколько шагов. В таком случае требуется некоторое условие, означающее прекращение итераций. Подробнее это будет рассмотрено ниже.
Проверка на "объяснимость": проверка каузальной полноты, все факты в исходной базе фактов должны объясняться при помощи порожденных системой гипотез. Если этого не происходит, значит требуется изменение исходной базы фактов экспертом.
Данная на Рис. 2-1. схема отражает основной принцип работы ДСМ-системы, вне зависимости от того, какая конкретно разновидное і ь ДСМ-метода реализована. На вход такой системы поступает база фактов, заданная специалистом, а на выходе выдается доопределенная БФ, т.е. БФ с устраненной неполнотой данных.
Обобщенный ДСМ-метод для работы в условиях неравнозначности признаков
Выше было рассмотрено два метода из семейства контекстных ДСМ-мстодов: несимметричный и обобщенный. Напомню, что в рамках обобщенного ДСМ-метода гипотеза о возможной причине наличия / отсутствия свойства у объекта выглядит не просто как некоторая совокупность атомарных признаков (фрагмент), но как пара фрагмент, множество тормозов для этого фрагмен-та , т.е. ищутся не глобальная анти причина, а локальные тормоза для каждого конкретного фрагмента-кандидата в гипотезы. Тормоз - это такой фрагмент, что если он есть у объекта, содержащего соответствующий фрагмент-причину, гипотеза блокируется и не срабатывает, т.е. наличие целевого свойства у данного объекта по данной гипотезе не может быть установленным (см. определение 2.7.).
Однако подобный подход рождает ряд вопросов: все ли гипотезы равнозначны между собой? Не является ли по каким-то причинам одна из гипотез предпочтительнее другой? Что, если не все признаки равнозначны? Что, если контекст является семантически неоднородным и семантически неравнозначным! Что если гипотеза, по которой определено наличие свойства у объекта, содержит в фрагменте-причине исключительно причины с низким уровнем значимости, в то время как гипотезы с более "сильными" фрагментами-причинами были заблокированы тормозами? Имеем ли мы, в данном случае, право однозначно утверждать, что объект обладает целевым свойством? В данной главе будет предложен вариант ответа на этот вопрос.
Будем предполагать, что объект представлен в виде множества признаков и значимость разных признаков для характеризации объекта может быть различной. В таком случае будем говорить, что признаки семантически неравнозначны. В качестве примера предметной области, где наблюдается подобная семантическая неравнозначность признаков, можно привести страхование и связанную с ним оценку рисков. Так при описании потенциального клиента для задачи медицинского страхования есть некоторые параметры, которые более значимы (например, "работает на вредном производстве" или "является активным курильщиком"), а есть некоторые параметры, которые не столь существенны (например, "живет на верхних этажах в доме, где нет лифта" или "в детстве болел ветрянкой"). Сразу отметим, что сохраняются все требования, предъявляемые к характеру данных и характеру закономерностей в предметной области, необходимые для корректной работы ДСМ-метода вообще (см. Главу 1): Объекты ДСМ-метода должны быть структурированы таким образом, чтобы мы имели возможность определять их сходство. Закономерности предметной области должны иметь детерминистский (нестатистический) характер [20].
На основании вышесказанного получается, что семантическая неравнозначность должна также носить детерминистский характер. А значит, семантическая неоднородность должна рассматриваться относительно структуры объектов, а не самих объектов. Это позволяет разделить все имеющиеся признаки (а они и образуют структуру объектов) на категории, в зависимости от их значимости, и этим категориям присвоим некоторые числовые веса3. Признаки, относящиеся к одной и той же категории, имеют одинаковые веса.
Для простоты, разделим признаки на две категории: значимые и малозначимые. Делается это исключительно из соображений наглядности, на самом деле количество категорий признаков неограниченно, вплоть до того, что у каждого признака может иметься свой индивидуальный вес. Множество возможных значений весов составляет отрезок от 0 до I6.
Однако ДСМ-метод работает не с отдельными признаками, а с фрагментами, и возникает вопрос, каким образом проводить соответствие между значимостью фрагмента и значимостью признаков, его составляющих. Делается это также при помощи численных весов, которые ставятся в соответствие каждому фрагменту. Определение 3.1. Введем функцию оценки фрагмента W(s): S - R, которая будет ставить в соответствие каждому фрагменту s его вес. Эта функция определяется через S-норму. Например, через максимум - весь фрагмент имеет такой же вес, как и наиболее значимый из признаков, входящих в его состав: W(s) = max (W(a) а є s} Замечание. Возможны и другие подходы к реализации функции оценки (другие S-нормы), зависящие от конкретной предметной области и предпочтительной стратегии. С точки зрения автора, чаще всего интуитивно оправданным является выбор именно максимума - "если в фрагмент входит значимый признак, значит и весь фрагмент значим", т.е. нас интересует только качественный состав фрагмента, а не количественный [29].
Определение 3.2. С каждым объектом о свяжем некоторый числовой параметр, назовем его "правдоподобность наличия свойства". Этот параметр будет выражать то, насколько правдоподобным мы считаем факт обладания свойством р для данного объекта. Будем обозначать этот параметр через р п(о,р), где о - объект, р - свойство, п - номер текущего шага индукции.
Другие модификации
Одной из основных проблем при работе с ДСМ-методом является его высокая вычислительная сложность и, следовательно, низкое быстродействие при работах с большими объемами данных [20]. В данной главе будет приведен ряд инженерных решений по оптимизации работа ДСМ-системы, базирующейся на несимметричном или обобщенном ДСМ-методах, а также уменьшению ее вычислительной сложности.
Модификации для объектов, описываемых семантически равнозначными признаками При практической реализации ДСМ-процедуры для несимметричного и обобщенного ДСМ-методов можно произвести ряд упрощений, направленных на уменьшение объема памяти, требующегося для хранения кандидатов в гипотезы, гипотез и тормозов внутри гипотезы [30].
Например, имеет смысл объединить этапы построения множества кандидатов в плюс-гипотезы1 с этапом поиска тормозов к ним. Что дает подобное объединение? Как только удается выявить очередной кандидат в плюс-гипотезы (фрагмент, являющийся непустым пересечением двух и более плюс-примеров), сразу же запускается поиск тормозов для этого фрагмента. Если для данного кандидата в гипотезы не существует минус-примеров, его содержащих, или же 1 Здесь и далее, если не оговорено отдельно, считается, что минус-гипотезы ведут себя в точности также, как и плюс-гипотезы, только двойственно, т.е. с "заменой знака". удается выявить тормоза - кандидат в гипотезы принимается. В противном случае он бракуется и не принимается. Ниже, на рис. 4-1 данная процедура изображена более наглядно, в виде блок-схемы. Из блока обработки БФ Построение нового пересечения Г К блоку \ - рассуждений по ) V аналогии J Поиск минус-примеров, содержащих данного кандидата в гипотезы Кандидат в гипотезы отвергается Кандидат в гипотезы принимается Выявление тормозов для данного кандидата і гипотезы
Объединение поиска тормозов и поиска кандидатов в гипотезы При этом, если использовать трактовку тормоза, по которой фрагмент-причина входит в тормоз, процедуру поиска тормозов к причине можно упростить еще сильнее. Например, для кандидата в плюс-причины достаточно найти такие элементы из множества пересечений минус-примеров, которые бы включали в себя эту плюс-причину. Эти элементы уже будут удовлетворять всем необходимым для понятия тормоза плюс-причины условиям. Аналогично ищутся тормоза для минус-причин.
Однако, возможно даже еще большее уменьшение объема хранимых гипотез: можно не просто проверять кандидаты в гипотезы на наличие дубликатов, чтобы избежать хранения одинаковых гипотез. В значение "новая гипотеза" можно вложить куда больший смысл, чем абсолютное равенство.
Определение 4.1. Будем говорить, что гипотеза первого рода Hi имеет большую выразительную силу, чем гипотеза первого рода Н2, если все, что может быть порождено с помощью гипотезы Н2 может быть порождено и гипотезой Нь
Как несложно увидеть из этого определения, если одна гипотеза имеет большую выразительную силу, чем другая, то гипотезу с меньшей выразительной силой можно исключить без потерь (все, что может быть порождено с ее помощью, и так будет порождено при помощи гипотезы с большей выразительной силой).
Для начала проиллюстрируем это понятие на достаточно простом примере. Допустим, у нас есть гипотеза Нь являющаяся абсолютной причиной наличия свойства р у объекта о, т.е. Hi состоит только из фрагмента fj, являющегося причиной, а множество тормозов пусто. Пусть есть другая гипотеза Н2, содержащая причину/? такую что//С . Утверждается что: 1. гипотеза Н2 - абсолютная гипотеза. 2. гипотеза Hi имеет большую выразительную силу, чем гипотеза Н2. Покажем первое. Это легко доказывается методом "от противного": Допустим, для гипотезы Н2 существует минус пример. Это означает, что существует объект, содержащий/ и не обладающий свойством/?, то этот же объект содержал бы и// (в силу того, что fiClfz), а значит являлся бы и минус-примером для гипотезы Hi. Однако нам известно, что гипотеза Hi является абсолютной гипотезой, т.е. для гипотезы Hi нет минус-примеров (см. определение 2.8.). Противоречие получено. Следовательно, минус-примеров для гипотезы Н2 не существует и она является абсолютной.
Докажем это утверждение. Доказывать будем также по методу "от противного". Допустим, что гипотеза Н2 применима к некоторому объекту о. Это означает, что объект о содержит фрагмент / и не содержит тормозов гипотезы Н2.
Пусть к этому объекту о не применима" гипотеза Hi. Это означает, что объект о не содержит фрагмента//. Однако он уже его содержит: объект о содержит фрагмент/, а т.к./с/, а значит, объект о содержит и фрагмент//! Получили противоречие.
В силу доказанных выше утверждений получаем не только то, что гипотеза Hi имеет большую выразительную силу, чем гипотеза Н2, но и то, что гипотезой Н2 можно пренебречь: всегда, когда применима она, применима и гипотеза Hi, а т.к. обе эти гипотезы - абсолютные гипотезы, если они применимы, то они срабатывают. Таким образом гипотезу Н2 в понятие "новая гипотеза" включать не стоит.
Теперь рассмотрим общий случай, когда у нас гипотезы не обязательно являются абсолютными причинами наличия или отсутствия свойств.
2 Гипотеза Н] является абсолютной, т.е. не имеет тормозов, а значит, если она применима к объекту, то она для него срабатывает - ее нечему блокировать.
Предположим, имеется гипотеза Н (s, Т k(s,p) , где s є S к(р), и найдена гипотеза Н2: (f, T+k(f,p) , где/є S+k(p), такая, что/с s. Найдем условие достаточное для того, чтобы гипотеза Н2 имела большую выразительную силу, чем гипотеза Hj.
Тот факт, что гипотеза Н2 применима всегда, когда применима гипотеза Ні уже был доказан выше. Значит, достаточно показать, что если гипотеза Hi блокируется каким-то тормозом, то и гипотеза Н2 также будет блокироваться, а если гипотеза Hi срабатывает, то срабатывает и гипотеза Н2.
Нетрудно показать, что множество минус-примеров для фрагмента / будет не меньшим, чем для фрагмента s - фрагмент s включает в себя фрагмент/ а значит все минус-примеры для фрагмента s будут являться и минус примерами для фрагмента/ Однако это и значит, что множество тормозов T+k(s,p)czT+k(f,p) (см. определение 2.7.). Это означает, что гипотеза Н2 не только применима всегда, когда применима гипотеза Нь но и блокируется всегда, когда блокируется гипотеза Hi.
Однако этого недостаточно, чтоб утверждать, что гипотезу (s,T k(s,p) можно исключить без потерь. Необходимо еще показать, что гипотеза Н2 будет срабатывать всегда, когда срабатывает гипотеза Hi. Но это как раз не обязательно так!
Действительно, возможна ситуация, когда для некоторого объекта о будет выполняться условие срабатывания гипотезы Hi: s с:о & —i3t Є T k(s,p)(t сто), но не будет выполняться условие срабатывания гипотезы Н2: / с: о & БҐ є 1 k(f,p)(t cz о). Такое возможно, если в объекте о обнаружится тормоз / є (Ґ к([,р)ХҐk(s,p)) . Отсюда следует, что гипотезу (s, T+k(s,p)) молено исключить без потерь только в том случае, когда Ґк ,р)\ Ґк(8,р)= 0.
Утверждение 4.1. В общем случае можно говорить, что одна гипотеза имеет большую выразительную силу, чем другая тогда и только тогда, когда причина первой гипотезы включается в причину второй, а множества тормозов для этих двух гипотез совпадают.
