Диссертация (1137435), страница 11
Текст из файла (страница 11)
, | |}, которая будет равна количеству вызововоперации decrease_all() и , которая будет равна индексу первого непустогосписка. При инициализации элемент с ключом добавляется в -й список(set(,) добавляет элемент с ключом ). При вызове increase() нужно переложить элемент из его текущего списка в список с индексом на 1больше текущего (список и место в списке, где находится элемент можноузнать с помощью вспомогательного массива). Операция get_min возвращает − , а при вызове extract_min необходимо увеличивать до тех пор,пока не встретится непустой список.Таким образом мы получаем следующую теорему:Теорема 6.
Алгоритм _2() вычисляет для произвольногоподмножества признаков ⊆ и контекстов K1 = (1 , , 1 ), . . . , K =∑︀( , , ) за время ( 1≤≤ | |).Задача поиска максимального (по мощности) замкнутого множества′′относительно операторов (·) и (·)* , очевидно решается за полиномиальное время: достаточно просто проверить все объектные содержания и найти максимальное. Но в отличие от этих операторов замыкания, аналогичная задача поиска максимального общего содержания, отличного от (напрактике это может соответствовать "максимальной схожести двух контекстов") для оператора (·) NP-полна, как показано в следующей теореме.Утверждение 9.
ЗадачаВХОД Два формальных контекста 1(2 , , 2 ), и целое число 0 ≤ ≤ | |.=(1 , , 1 ), 2=79ВОПРОС Существует ли такое , что = , ⊂ и || ≥ ? -полна.Доказательство. По теореме 5 = может быть проверено за полиномиальное время, таким образом эта задача лежит в . Для доказательства -трудности мы сведем хорошо известную -полную задачуо минимальном покрытии (МП) к нашей. Задача МП формулируется следующим образом [55]:ВХОД Конечное множество , множество его подмножеств :={1 , 2 , . . .
, }, ⊆ , и целое число .ВОПРОС Существует ли подмножество ⋃︀∈⊆ такое, что = и | | ≥ ?Рассмотрим произвольное конечное множество = {1 , 2 , . . . , },и множество его подмножеств := {1 , 2 , . . . , }, ⊆ для всех1 ≤ ≤ , и целое число 0 ≤ ≤ ||. Пусть = {1 , 2 , . . . , ||+|| }1}. Теперь построим контекст 1 = (1 , , 1 ), где 1и 1 = {11 , 21 , . . . , ||определено как: 1 1 для ≤ ||, если и только если ∈/ и 1 1 для > || тогда и только тогда, когда − || ̸= . Тогда покрытия находятся во взаимно однозначном соответствии с содержаниями 1 , которыене содержат ни одного ∈ , ≤ ||. Более того, для любого покрытияразмера , соответствующее содержание будет размера || − .Теперь построим контекст 2=(2 , , 2 ), где 2=2{12 , 22 , .
. . , ||}, 2 определено как: для 2 , где 1 ≤ ≤ ||, ′ = ∖( ∪ {||+ }). Очевидно, множество всех содержаний этого контекста этов точности множество всех подмножеств множества , которые не пересекаются с . Следовательно существует взаимно однозначное соответствие80между общими содержаниями контекстов 1 и 2 отличными от , имножеством всех покрытий . Более того минимальные покрытия соответствуют максимальным общим содержаниям, и наоборот. Сведение доказано2и его полиномиальность очевидна.Насколько большим может быть минимальный контекст, задающийобщие содержания двух заданных контекстов? Ответ дан в следующемутверждении:Утверждение 10.
Существуют два контекста 1 и 2 такие, что множество их максимальных (по включению) общих содержаний экспоненциально относительно размеров 1 и 2 .Доказательство.Рассмотримконечноемножество{1 , 2 , . . . , 3 },имножествоегоподмножеств⋃︀Существует0≤≤−1 {{3+1 , 3+2 }, {3+1 , 3+3 }, 3+2 , 3+3 }}.==ровно3 минимальных покрытий , поскольку для любого 0 ≤ ≤ − 1подмножество {3+1 , 3+2 , 3+3 } может быть покрыто только тремя способами, используя ровно 2 элемента из . Таким образом, если построитьконтексты 1 и 2 как в Утверждении 9 в соответствии с и , у этихконтекстов будет 3 максимальных (по мощности) общих содержаний. 2Следствие. Существуют два контекста 1 и 2 такие, что минимальноеколичество объектов в контексте с оператором замыкания (·) экспоненциально относительно размеров 1 и 2 .3.5.Сцепления и общие содержанияВ [54] было дано следующее определение сцеплений81Определение 2.
Пусть 1 = (1 , 1 , 1 ) и 2 = (2 , 2 , 2 ) — формальные контексты. Отношение ⊆ 1 × 2 называется сцеплением из1 = (1 , 1 , 1 ) в 2 = (2 , 2 , 2 ), если – объем контекста 1 длялюбого ∈ 2 , и – содержание контекста 2 для любого ∈ 1 .112122Напомним некоторые определение из [54]. Прямое произведение контекстов 1 = (1 , 1 , 1 ) и 2 = (2 , 2 , 2 ) определяется как1 × 2 := (1 × 2 , 1 × 2 , ∇)где (1 , 2 )∇(1 , 2 ) ⇔ 1 1 1 or 2 2 2 .Контрноминальная шкала – это контекст (, , ̸=).Двойственный контекст для контекста = (, , ) определяетсякак = (, , ), где ⇔ .Утверждение 11. Отношение ⊆ 1 × 2 является сцеплением из контекста 1 = (1 , 1 , 1 ) в контекст 2 = (2 , 2 , 2 ) тогда и только тогда, когда является общем содержанием контекстов 1 × 2 и (1 × ).2Доказательство.
Пусть ⊆ 1 × 2 — общее содержание контекстов 1 ×2 = (1 ×2 , 1 ×2 , ∇2 ) и (1 ×) = (1 ×2 , 1 ×2 , ∇1 ) .2Поскольку — содержание контекста 1 × 2 , то=⋂︁(,ℎ)∈ ∇2{(, ) | (, ℎ)∇2 (, )}82×××× ××× × ×× ××× ×× ×Таблица 3.1. Пример сцепления двух контекстов=⋂︁ ⋂︁({(, ) | ℎ2 } ∪ {(, ) | ̸= }), ℎ∈()где (, ) ∈ 1 × 2 ,⋂︀2взято по всем таким, что (, ℎ) ∈ ∇ для2некоторого ℎ, и () = {ℎ | (, ℎ) ∈ ∇ }.
Следовательно, если = для⋂︀⋂︀некоторого , рассмотрев пересечение , мы получим = ℎ∈() ℎ2 ,⋂︀т.е. замкнуто в 2 , и если ̸= для всех , взяв , получим = 2 . Аналогично, поскольку – содержание контекста (1 × ) , мы можем2доказать, что замкнуто в контексте 1 для любого ∈ 2 .Пусть ⊆ 1 × 2 - сцепление из контекста 1 в контекст 2 . Тогда замкнуто в 2 для любого ∈ 1 . Обозначим () = ( )2 , тогда⋂︀ = ℎ∈() ℎ2 . Рассмотрим=⋂︁ ⋂︁({(, ) | ℎ2 } ∪ {(, ) | ̸= }). ℎ∈()Выше мы показали, что это множество является содержанием обоих кон текстов 1 × 2 и (1 × ) , т.е., общим содержанием этих контекстов.2Тогда = для любого ∈ 1 и = для любого ∈ 2 ,следовательно = , и – общее содержание контекстов 1 × 2 и83 ).(1 × 22Следствие. Оператор замыкания для сцеплений контекстов1 = (1 , 1 , 1 ) и 2 = (2 , 2 , 2 ) может быть вычислен за время((|1 | · |2 | + |1 | · |2 |) · |2 ||1 |).Доказательство. Нужно применить утверждение 11 и теорему 5.844.
Обучение гипотезамТеперь мы опишем модель обучения по гипотезам в духе [20, 23] втерминах АФП [52]. Эта модель соответствует общей парадигме обученияпо положительным и отрицательным примерам (см., например [52, 73]):даны положительные и отрицательные примеры целевого признака, нужнопостроить обобщения положительных примеров, которые бы не покрывалини один отрицательный пример.Пусть признаки из описывают "структуру"объектов, а - целевойпризнак, отличный от всех признаков из . Например, в фармакологических приложениях структурные признаки могут соответствовать подграфам молекулярных графов химических соединений, а целевой признак биологическим свойствам этих соединений.Входные данные для контекста обучения могут быть представленымножествами положительных, отрицательных и неопределенных примеров.
Положительные примеры (или (+)-примеры) – это объекты, о которых известно, что они обладают признаком , а отрицательные примеры(или (−)-примеры) – это объекты, о которых известно, что они не обладаютпризнаком Определение 3. Рассмотрим положительный контекст K+ = (+ , , ℐ+ ) иотрицательный контекст K− = (− , , ℐ− ).
Контекст K± = (+ ∪ − , ∪{}, ℐ+ ∪ ℐ− ∪ + × {}) называется контекстом обучения. Оператор Галуа85для этого контекста обозначается как ±.Определение 4. Подмножество ⊆ называется положительной гипотезой (или (+)-гипотезой) контекста обучения K± , если - содержаниеконтекста K+ и не является подмножеством ни одного содержания контекста K− .Аналогичноопределяютсяотрицательныегипотезы(или(-)-гипотезы). Содержание контекста K+ , которое принадлежит хотя быодномуотрицательномупримеру,называетсяфальсифицированным(+)-обобщением.В [23] гипотезы называются "гипотезами первого рода с запретом наконтрпример”, причем дополнительно требуется, чтобы гипотеза подтверждалась не менее, чем двумя примерами, т.е. | + | ≥ 2.Помимо положительных и отрицательных примеров обычно имеютсяобъекты, для которых значение целевого признака неизвестно.
В [23] этиобъекты называются неопределенными примерами, они могут быть заданыконтекстом K := ( , , ), соответствующий оператор Галуа обозначается через (·) .Гипотезы могут быть использованы для классификации неопределенных примеров: если содержание := { ∈ | (, ) ∈ }объекта ∈ содержит положительную и ни одной отрицательной гипотезы, то классифицируется положительно. Отрицательные классификации определяются аналогично. Если содержит гипотезы обоих знаков,то классификация противоречива. Если вообще не содержит гипотез, то86классификация не определена.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
