Главная » Просмотр файлов » Диссертация

Диссертация (1137435), страница 11

Файл №1137435 Диссертация (Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств) 11 страницаДиссертация (1137435) страница 112019-05-20СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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классификация не определена.

Характеристики

Список файлов диссертации

Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств
Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее