Диссертация (Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств), страница 6

Описание более поздних версий можно найтив [23], см. также обзор [12]. Правдоподобные рассуждения в ДСМ-методеформализованы в рамках бесконечнозначной логической теории первогопорядка с кванторами по кортежам переменной длины. Логические аспекты ДСМ-метода наиболее подробно освещены в [25, 23], вопросы об определимости правдоподобных ДСМ-рассуждений в логике первого порядкаисследованы в [6], где показано, что определимость в логике первого порядка возможна в случае конечных моделей и требует слабой логики предикатов второго порядка в случае бесконечных моделей.

Как метод анализа данных, ДСМ-метод есть система автоматического обучения по положительным и отрицательным примерам [12, 16, 52]. Примеры суть объекты, представляемые подмножествами некоторого множества 1 . Свойствасуть объекты, представляемые подмножествами некоторого множества 2 ,1 ∩2 = ∅.

Положительными относительно свойства ⊆ 2 называютсяпримеры, про которые известно, что они обладают свойством . Отрица­тельные примеры - это примеры, про которые заведомо известно, что онине обладают свойством .Основу метода составляют правила правдоподобного вывода, опре-37деляемые через предикаты сходства. Например, простой положительныйпредикат сходства ℳ+, — аналог метода согласия (method of agreement)Дж.С. Милля — выглядит следующим образом:̃︁ +ℳ+, (, )∃ ℳ, (, , ),̃︁ +ℳ, (, , )∃1 . . .

∃ ∃1 . . . ( & ⟨1,⟩ ( ⇒1 ) &=1& ∀ (⟨1,⟩ ( ⇒1 )→ ⊂ )) &&(1 ∩ . . . ∩ ) = & ̸= ∅ & ̸= ∅& ∀ ∀(( ̸= ) & 1 ≤ , ≤ )→ ̸= ) && ∀ ∀ ((⟨1,⟩ ( ⇒1 ) && ∀(⟨1,⟩ ( ⇒1 )→ ⊆ ) && ⊂ )→( ⊆ &( ∨ ( = )))) & ≥ 2).=1Здесь соответствует простому предикату сходства (в ДСМ-методе есть идругие предикаты), обозначает шаг применения правил правдоподобноговывода к исходным примерам, есть оператор Россера-Тюркета, сопоставляющей многозначной формуле классическое истинностное значение измножества {, }, так что () = если имеет многозначную оценку и () = в противном случае. ⇒1 означает, что объект обладаетсвойством .

Точные определения см. в [23].Интуитивный смысл предиката сходства заключается в том, что предположительная причина общности свойств объектов1 . . . , (положительных примеров) заключается в , сходстве структур этих объектов (представляемом в данном случае теоретикомножественным пересечением описаний структур положительных примеров, представленных множествами признаков).38Другие предикаты простого метода получаются из предиката сходства конъюнктивным добавлением некоторых условий. Например преди­кат с запретом на контрпример получается из предиката простого сходства добавлением условия (1)+:(1)+∀ ∀ (( ⊂ & ⊆ )→→((+1,) ( ⇒1 ) ∨ (0,) ( ⇒1 ) ∨ (,) ( ⇒1 ))Интуитивный смысл этого условия следующий: сходство объектов 1 ,.

. ., (т.е. пересечение их описаний), обладающих свойством (т.е. положительных примеров), есть гипотетическая причина этого свойства, если это сходство не принадлежит объектам, которые заведомо не обладаютсвойством (т.е. отрицательным примерам).Предикаты упорядочены по логическому следствию: предикат 1сильнее предиката 2 если 1 → 2 . В работах [21, 23] приводится решетка предикатов, задаваемая отношением логического следствия.Гипотезы, то есть объекты, удовлетворяющие тем или иным предикатам, могут использоваться для классификации недоопределенных приме­ров, т.е. объектов, про которые неизвестно, обладают ли они свойством или нет. Правило положительной классификации (называемое правиломвывода II рода в [23]) выглядит следующим образом.39̃︀ +Π (, )∃1 .

. . ∃ [( & ∃ (⟨+1,⟩ ( ⇒2 ) & ⊂ ) &=1&(∪=1 = ) & ∀ (∃(⟨1,⟩ ( ⇒2 ) & ⊂ )→→( ∨ ( = ))] & ∀ [( ⊆ & ̸= ∅)→=1→¬∃(⟨−1,⟩ ( ⇒2 ) & ⊆ ))].Содержательно оно означает, что недоопределенный пример классифицируется положительно (то есть как предположительно обладающийсвойством ) если он содержит в качестве подмножества какую-либо положительную гипотезу и не содержит ни одной отрицательной. Недоопределенный пример классифицируется отрицательно в противоположном случае (т.е. если он содержит отрицательную гипотезу и не содержит положительной гипотезы). Если недоопределенный пример содержит как положительные гипотезы, так и отрицательные гипотезы в качестве подмножеств, то его классификация противоречива, если не содержит ни тех ине других - то его классификация неопределенна. Логическая конструкцияДСМ-метода допускает возможность итеративного пополнения множестваположительных и отрицательных примеров результатами классификации.Этот процесс, описываемый на языке бесконечнозначной логики предикатов, может продолжаться вплоть до стабилизации, т.е.

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

Вглаве 2 нами будут сформулированы некоторые основные понятия ДСМметода на алгебраическом языке АФП.По определению гипотез и классификации на их основе (ДСМ-метод)достаточно использовать только минимальные по вложению гипотезы. Таким образом множество минимальных гипотез является полным множеством гипотез (с помощью него можно произвести те же классификации,что и с помощью множества всех гипотез).

В связи с этим встает вопросо возможности порождения минимальных гипотез с полиномиальной задержкой (или хотя бы за полиномиальное от выхода время), как это имеетместо для множества всех гипотез. Вопросы, связанные с обучением минимальным гипотезам, исследованы в статье [68, 74]. Задача о вычислительной сложности порождения минимальных гипотез оставалась до сих пороткрытой.Особое место в ДСМ-методе занимают обобщенные гипотезы [22, 23],в определении которых варьируется основная идея: сходство положительных примеров как гипотетическая причина целевого свойства можеттормозиться элементами отрицательных примеров, причем тормозами выступают минимальные сходства отрицательных примеров, содержащие в качестве подмножества. Ввиду громоздкости логической формулировкиобобщенного метода, мы не приводим их здесь, а отсылаем за ними читателя к работам [25, 22, 23, 24].

Формулировка обобщенного метода на языкеАФП приводится в главе 2. Заметим, что обобщенная гипотеза является гипотезой в вышеуказанном смысле только если множество тормозов пусто.41Применение обобщенных гипотез основанно на более сильных допущениях о природе причинности (ее тернарной природе: причина - блокиратор- следствие) и происходит обычно при отутствии или малом количестве“обычных” (простых в терминологии [23]) гипотез описанных выше.На основе представления о тернарной причинности в [24] предложентакже ситуационный ДСМ-метод, где ситуация, в отличии от блокиратора в обобщенном методе, может содействовать причине, а не противодействовать ей. В ситуационном методе возможно наличие противоречивостив исходных данных (что может приводить к противоречивым классификациям без наличия положительных и отрицательных гипотез).422.

Базисы импликаций и функциональныхзависимостей2.1.Квазизамкнутые множества и псевдосодержанияПодмножество ⊆ удовлетворяет импликации → , если из ⊆ следует ⊆ . Любое множество импликаций J на множестве определяет оператор замыкания (·)J на , где подмножество замкнутотогда и только тогда, когда это множество удовлетворяет всем импликациям из J. Подмножество импликаций, из которого все остальные импликации контекста могут быть выведены по правилам Армстронга называетсяпокрытием импликаций.

Заметим, что J является покрытием импликацийконтекста K тогда и только тогда, когда система замыканий, которую задает J, совпадает с системой замыканий контекста K. Одно из минимальныхпо мощности (далее будем писать просто минимальный) покрытие импликаций (минимальный базис импликаций) было приведено в [41]. Это подмножество импликаций называется базисом Дюкена-Гига, каноническимбазисом или stembase в литературе. Множество посылок импликаций в каноническом базисе является в точности множеством псевдосодержаний(см.например [54]): множество ⊆ называется псевдосодержанием, если ̸= ′′ и ′′ ⊂ для любого псевдосодержания ⊂ .

Для множества ⊆ такого, что * и является содержанием или псевдосодержанием пересечение ∩ является содержанием (см. [54]). Таким образом,43объединение множества псевдосодержаний с множеством содержаний образует систему замыканий. Множество ⊆ называется квазизамкнутым(квазисодержанием), если для любого ⊆ выполнено ′′ ⊆ или′′ = ′′ . Например, замкнутые множества – квазизамкнуты. Для квазисодержания выполнено ( ∩ )′′ = ( ∩ ) для любого содержания такого, что * .

Мы также будем использовать другое эквивалентноеопределение псевдосодержания: незамкнутое множество ⊆ являетсяпсевдосодержанием тогда и только тогда, когда квазизамкнуто и ′′ ⊆ для любого квазизамкнутого подмножества ⊂ (см. [41, 76, 78]). Множество ⊆ называется существенным содержанием (существенно за­мкнутое подмножество признаков), если существует псевдосодержание ⊆ такое, что ′′ = .Пусть = {1 , . .

. , } и = {1 , . . . , } – множества одинаково мощности . Тогда контекст K = (, , ℐ̸= ) называется контраноми­нальной шкалой, где ℐ̸= = × ∖ {(1 , 1 ), . . . , ( , )}. У контраноминальной шкалы есть следующее свойство, которое мы будем использоватьдальше: любое подмножество признаков ⊆ замкнуто ( ′′ = ) и ′ = { | ∈/ , 1 ≤ ≤ }.2.2.Структура минимальных базисов импликацийПусть K = (, , ) – формальный контекст, а J – произвольныйминимальный базис импликаций контекста K. Рассмотрим любую импликацию → ∈ J.Сначала мы покажем, что = J∖(→) является квазизамыканиеммножества т.е. = . Заметим, что ̸= ′′ , поскольку иначе система44замыканий базиса J совпадает с системой замыканий базиса J ∖ ( → ).Рассмотрим произвольное подмножество ⊂ .

Если ⊆ J∖(→) , то тогда ′′ = J = J = ′′ . Если * ∖(→) , то ′′ = J = J∖(→) ⊆ .Таким образом, квазизамкнуто. Допустим существует другое квазизамкнутое множество такое, что ⊆ ⊂ . Тогда существует импликация → ∈ J ∖ ( → ) такая, что ⊆ и * , т.к. иначе = J∖(→) ⊆ . Поэтому ′′ * и, следовательно, ′′ = ′′ = ′′ , чтопротиворечит тому, что ′′ ⊆ .Теперь мы покажем, что, если J – минимальный базис импликаций,то для любой импликации → ∈ J квазизамыкание посылки является псевдосодержанием. Рассмотрим псевдосодержание . Поскольку не замкнуто, то существует импликация → ∈ J такая, что ⊆ и * . Допустим, что для некоторой импликации → ∈ J существует хотя бы два псевдосодержания 1 и 2 такие, что ⊆ 1 , * 1и ⊆ 2 , * 2 . Тогда ⊆ 1 ∩ 2 . Если 1 ⊂ 2 , то ′′ ⊂ 2 , ноэто невозможно, поскольку ⊆ ′′ .