Предикатное описание дополнительных ограничений в задачах распознавания образов

• Автор: Таханов, Рустем Серикович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 70 с.

0 Введение

1 Предикатные пары как язык описания множеств отображений

и максимальные предикатные пары

1.1 Основное понятие

1.2 Максимальность пар предикатов относительно множеств отображений

1.3 Максимальность пар предикатов

1.4 Максимальные предикатные пары в примерах

1.4.1 Необходимые и достаточные условия максимальности в случае, когда рв — частичный порядок

1.4.2 Предикатное описание выполняющих наборов 2-КНФ

1.5 Аксиоматика отношения «между»

2 О предикатных ограничениях с эффективно-разрешимой задачей согласования с обучающей выборкой
2.1 Введение
2.2 Алгебраическая структура эффективно разрешимых классов предикатов
2.3 Максимальные классы предикатов в булевом случае
2.4 Эффективная разрешимость порядкового класса предикатов в общем случае
2.5 Открытые вопросы
3 Задача монотонизации выборки
3.1 Постановка задачи монотонизации выборки
3.2 Задача монотонизации выборки и максимальные независимые подмножества

3.3 ЫР-полнота МахСМЭ
3.4 ЬМахСМЭ
3.5 2-МахСМЭ
3.6 Приближенный алгоритм для 2-МахСМЭ
3.6.1 Обсуждение
4 Предикатное задание универсальных ограничений алгебраического подхода
4.1 Основные понятия и формализм
4.1.1 Ограничения монотонности
4.1.2 Симметрические ограничения
4.1.3 Функциональные ограничения
5 Заключение

Глава О
Интенсивное развитие технологий хранения информации, произошедшее за последние 30 лет, послужило стимулом для нового витка исследований по классической тематике—проблемам связанным с автоматизацией ее интеллектуального анализа. Одним из важных инструментов для решения этой задачи являются методы распознавания образов, развиваемые с начала 50-х годов прошлого вска[2, 12, 28, 24, 5, 13].
Характерной особенностью задач решаемых посредством методов распознавания является сложность количественного описания или моделирования сущностных процессов исследуемых систем. При этом, порой практически устраивающим исследователя решением является отображение из заранее заданных множества начальных информаций(называсмых дальше объектами) во множество ответов. Информация же о виде этой зависимости задается в виде конечного массива прецедентов вида «объект - ответ». Таким образом, с формальной точки зрения есть все предпосылки рассматривать задачу распознавания образов как частный случай задачи экстраполяции функции.
Очевидная неполнота информации, заданной в конечной структуре (массив прецедентов) об искомом отображении, которое, вообще говоря, может определяться бесконечным числом степеней свободы, привела исследователей к разработке большого числа моделей алгоритмов. Модель алгоритмов, или иначе говоря, некоторое подмножество отображений из множества объектов во множество ответов, должна была сыграть роль той недостающей информации для полного либо частичного восстановления искомого отображения. При этом, разработанные модели алгоритмов, как правило, были основаны на интуитивных эвристических соображениях, вроде удовлетворения искомого отображения условиям гладкости, краткости описания, структурной простоты, линейности и т. д.
Удобным и часто используемым способом описания дополнительных огра-

наоборот), можно считать, что максимум функционала достигается на целочисленных векторах.
Предложение 5. Справедливо
тах ф (х, у) = тах 7 Сх, у), хеП(С1),»еП(С2) х€П((?1),й€П(С?2)

7 (х,у) =-^2 шу + У у)2 ~ Щ (ху + уу)

v&V
Доказательство.
тах У' %иуХуУу-= тах -У го„ (х„ + уу)2 — гс„ (х*, + у1) > х£ЩС1)]уеЩС2) ^ хеЩв1),у€П(в3) 2 ^ V у)
г/€К ьеУ
тах 7 (х* + У«)2 ~ (ХУ + Уу)
хеща1),уеЩс2) 2 “

Однако, так как максимум левой части неравенства достигается на целочисленных векторах, ясно, что здесь необходимо равенство. Учитывая, что функционал 7 (х, у) является выпуклым, наша задача свелась к максимизации выпуклой функции на выпуклом множестве.
3.6 Приближенный алгоритм для 2-MaxCMS
Рассмотрим функционал
Ч> (г> У) = - Wv (Xv ~ УWv (Xv + У")
2 ■
v£V
Предложение 6. Справедливо
max ip (х, у) > max ф (х, у),
5en(Gi),Fen(G2) Ten(Gi).yen(G2)
причем на целочисленных точках политопа х € II(G'i),p € П(С?г) значения уз (х, у) и ф (ж, у) совпадают.
Доказательство. Проверка второго утверждения очевидна. Из него следует первое, в связи с тем, что максимум правой части по предложению 4 достигается и на целочисленных векторах.
Рассмотрим теперь следующую оптимизационную задачу:
шеЩСО
y_€jl(G2)
<р (х, у) —► max