Диссертация (1137435), страница 12
Текст из файла (страница 12)
В этом случае можно применять методыдругого типа, например, основанные на статистических подходах. В [23]классификации называются "гипотезами второго рода”.В [52, 73, 53] отмечалось, что для классификации можно ограничиться только минимальными (по вложению ⊆) гипотезами, положительными и отрицательными, поскольку объектное содержание содержит положительную (отрицательную) гипотезу тогда и только тогда, когда оно содержит некоторую минимальную гипотезу.Рассмотрим также другое, более слабое определение гипотезы (в [20,23] называемое "простой (+)-гипотезой 1-го рода по методу сходства")Определение 5.
Подмножество ⊆ называется положительной предгипотезой (или (+)-предгипотезой) контекста обучения K± , если являетсясодержанием контекста K+ и не является содержанием контекста K− .Аналогично определяется отрицательная предгипотеза (или (-)предгипотеза).4.1.Теоретико-решеточная интерпретация гипотез и классификацииВ терминах решетки B(K+ ) положительных понятий, каждый отри-цательный пример вырезает из решетки (+)-контекста некоторый порядковый фильтр.Для решетки B± ситуация выглядит иначе. Мы можем выделить тритипа понятий этой решетки: понятия типа (, ∪{}), где – содержаниеконтекста K+ , понятия типа (, ), где – содержание K− и понятия типа87(, ), где не является содержанием ни K+ , ни K− .Утверждение 12.
Положительные гипотезы соответствуют понятиям контекста обучения K± , которые представимы как (, ∪ {}), причем неявляется содержанием K±Действительно, если является содержанием контекста K± , то естьпримеры у которых все признаки из , но ни один не содержит признак, а это значит, что содержится в каком-то отрицательном примере.Отрицательная гипотеза соответствует понятию K± , которое представимокак (, ), ∈/ и ( ∪ {})± = ∅. Это эквивалентно тому, что у K± несуществует понятия, у которого непустой объем и содержание не меньше,чем ∪ {}.В решетке понятий B(K± ) понятия соответствуют (+)- и (-)гипотезам, лежащим ниже понятий, которые не являются гипотезами.В терминах этой решетки задача классификации неопределенного примера ∈ выглядит следующим образом.
Рассмотрим порядковыйфильтр решетки B(K± ), заданный максимальными подмножествами{ } ∪ {}, которые являются содержаниями K± . Если существуетпонятие (, ∪ {}), лежащее в этом порядковом фильтре, такое, что ∈/ и ( ± , ) не является понятием B(K± ), тогда – гипотеза дляположительной классификации .
Отсутствие гипотезы для отрицательной классификации означает, что для любого понятия (, ) решеткиB(K± ), такого, что ∈/ и (, ) лежит в порядковом фильтре B(K± ),заданного максимальными подмножествами { } ∪ {}, которые являются содержаниями K± , выполнено ( ∪ {})′ ̸= ∅ или существует понятие снепустым объемом, лежащее не выше, чем (( ∪ {})′ , ( ∪ {})′′ ).88Интерпретация задачи о существовании положительной предгипотезы в терминах решеток понятий еще более наглядна.Утверждение 13. Для контекста обучения K± существует положительнаяпредгипотеза тогда и только тогда, когда решетка B(K+ ) не является подрешеткой решетки B(K− ).Аналогично, существование отрицательной предгипотезы эквивалентно тому, что решетка B(K− ) не является подрешеткой решетки B(K+ ).Ниже приведен пример обучающей выборки и некоторое его естественное шкалирование:G∖Mцветяблокожелтоенетгрейпфрутжелтыйкивитвердый гладкийформафруктдакруглое+нетнеткруглый+зеленоенетнетовальное+сливасиняянетдаовальная+кубикзеленыйдадакубический-яйцобелоедадаовальное-теннисный мячбелыйнетнеткруглый-89G∖Mяблоко×× ×грейпфрут××киви×кубикяйцо×теннисный мяч ×фрукт×+×× ×+×××+× ××+×××-×××-×слива×× ×-Рис.
4.1. Шкалирование обучающей выборки (контекст K± )Условные обозначения: - зеленый, - желтый, - белый, - синий; - твердый, - нетвердый; - гладкий, - негладкий; - круглый, - некруглый;(+)-Гипотезы: { , }, { , }, {, , , }, {, , , }, {, , }, {, , , },{, , , }(+)-Предгипотезы: { }, { , }, { , }, { , }, {, , , }, {, , , },{, , }, {, , , }, {, , , }90Рис. 4.2. Решетка понятий положительного контекста (K+ )4.2.Перечисление гипотез и дуализация монотонных булевыхфункций на решеткахВ [52] было показано, что все гипотезы могут быть перечислены сполиномиальной задержкой (||2 | |) с помощью алгоритма, являющегося адаптацией Next Closure [54].
На самом деле можно использовать любой алгоритм перечисления замкнутых множеств в лектическом порядке(лексикографическом порядке на характеристических векторах). Действительно, рассмотрим контекст K = (− ∪ + , , ℐ+ ∪ ℐ− ) (это в точностиконтекст K± без целевого признака). Введем линейный порядок на объектах этого контекста, такой, что любой объект из − меньше, чем любойобъект из + . Заметим, что множество ′ будет гипотезой тогда и только тогда, когда является объемом контекста K и ∩ − = ∅, а такженаоборот – для любой гипотезы множество ′ есть объем контекста Kи ′ ∩ − = ∅.
Таким образом, множество гипотез взаимно-однозначносоответствует множеству объемов контекста K, которые не пересекаются c91− . Поэтому достаточно перечислять объемы контекста K в лектическомпорядке до тех пор, пока мы не встретим объем, содержащий объект из− .Выше мы писали, что при классификации достаточно одних толькоминимальных гипотез. Поэтому возникает следующая задача:Задача 10. Перечисление минимальных гипотез (MHE)ВХОД:ПоложительныеиотрицательныеконтекстыK+=(+ , , ℐ+ ), K− = (− , , ℐ− )ВЫХОД: Все минимальные гипотезы контекста K± .К сожалению, эта задача не может быть решена за полиномиальноеот выхода время, если ̸= .
Для того, чтобы доказать этот результатмы изучим сложность следующей зщадачи.Задача 11. Дополнительная минимальная гипотеза (AMH)ВХОД:Положительные(+ , , ℐ+ ), K−иотрицательныеконтекстаK+== (− , , ℐ− ) и подмножество минимальных гипо-тез ℋ = {1 , . . . , }.ВОПРОС: Существует ли дополнительная минимальная гипотеза обучающего контекста K± т.е. такая минимальная гипотеза , что∈/ ℋ?Мы сведем -полную задачу выполнимость КНФ (SAT) к AMH.Приведенное ниже сведение похоже на то сведение, которое мы использовали для доказательства трудности задачи распознавания псевдосодержания.Рассмотрим произвольный вход задачи SAT – 1 , .
. . , с перемен-92ными 1 , . . . , , где = (1 ∨ . . . ∨ ), 1 ≤ ≤ и ∈ {1 , . . . , } ∪{¬1 , . . . , ¬ } (1 ≤ ≤ , 1 ≤ ≤ ) – некоторые переменные илиих отрицания, называющиеся литералами. По этой КНФ мы построимположительный контекст K+ = (+ , , ℐ+ ) и отрицательный контекстK− = (− , , ℐ− ) . Определим = {1 , . . . , } ∪ {1 , ¬1 , . . . , , ¬ }+ = {1 , ¬1 , . . . , , ¬ } ∪ {1 , . . . , }− = {1 , . . . , }Отношение положительного контекста определяется следующим образом ℐ+ = ℐ ∪ ℐ̸= ∪ ℐ= , гдеℐ = {( , ) | ∈/ , 1 ≤ ≤ , 1 ≤ ≤ }∪ {(¬ , ) | ¬ ∈/ , 1 ≤ ≤ , 1 ≤ ≤ }ℐ̸= = {1 , ¬1 , . . . , , ¬ } × {1 , ¬1 , . .
. , , ¬ }− {(1 , 1 ), (¬1 , ¬1 ), . . . , ( , ), (¬ , ¬ )}ℐ= = {(1 , 1 ), . . . , ( , )}т.е. для -й клаузы(дизъюнкции) + ∩{1 , ¬1 , . . . , , ¬ } является множеством литералов не встречающихся в , ℐ̸= – отношение контраноминальной шкалы.Отношение отрицательного контекста задается, как ℐ− = ℐℒ , гдеℐℒ = − × {1 , ¬1 , .
. . , , ¬ }− {(1 , 1 ), (1 , ¬1 ), . . . , ( , ), ( , ¬ )}.93В качестве подмножества минимальных гипотез мы берем ℋ ={{1 }, {2 }, . . . , { }}. Очевидно, K± вместе с ℋ является корректнымвходом задачи AMH.K+1 2 · · · 1 ¬1 · · · ¬ℐℐ̸=1¬1...¬1...ℐ=K−1...ℐℒМы будем называть гипотезу (не обязательно минимальную) дополнительной, если она не входит в ℋ.Утверждение 14. Если – дополнительная минимальная гипотеза обучающего контекста K± , то ⊆ {1 , ¬1 , .
. . , , ¬ }.Доказательство. Допустим * {1 , ¬1 , . . . , , ¬ }, тогда т.к. не пусто, то найдется некоторая дизъюнкция ∈ , 1 ≤ ≤ . Но является минимальной гипотезой и поэтому оно не содержит(строго)никакую другую гипотезу. Следовательно = , что противоречит тому,что дополнительная минимальная гипотеза.294Для любого ⊆ {1 , ¬1 , . . . , , ¬ } такого, что для всех 1 ≤ ≤ выполнено { , ¬ } * мы определим булево назначение переменных естественным образом: ( ) =⎧⎪⎪⎨,if ∈ ;⎪⎪⎩ , if ∈/ ;В случае { , ¬ } ⊆ для некоторого 1 ≤ ≤ , назначение неопределено.Симметрично, для назначения определим множество = { |( ) = } ∪ {¬ | ( ) = }.Ниже для удобства в случае, если ⊆ {1 , ¬1 , .
. . , , ¬ } мы обозначим дополнение в {1 , ¬1 , . . . , , ¬ } как .Утверждение 15. Если подмножество ⊆ {1 , ¬1 , . . . , , ¬ } не содержится в содержании ни в одного отрицательного понятия (т.е. ∀ ∈− , * − ), то корректно определено. Обратно, для булева назначения множество не содержится ни в содержании ни одного отрицательногопонятия.Доказательство. Доказательство очевидно.2Следующая теорема доказывает NP-трудность задачи AMH.Теорема 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
