Предикатное описание дополнительных ограничений в задачах распознавания образов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

Таханов Рустем Серикович

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

01 01 09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

□ОЗ176334

Москва - 2007

003176334

Работа выполнена на кафедрв< Интеллектуальные системы» факультета Управления и Прикладной Математики Московского Физико-

Технического Института

Научный руководитель: член-корреспондент РАН, доктор физико-

математических наук, профессор Рудаков Константин Владимирович.

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор

Леонтьев Владимир Константинович,

кандидат физико-математических наук Дьяконов Александр Геннадиевич.

Московский Государственный Педагогический Университет

Защита диссертации состоится_»_2007 г в_

часов на заседании диссертационного совета Д002 017 02 в Вычислительном Центре РАН по адресу 119991, Москва, ул Вавилова, 40

С диссертацией можно ознакомиться в библиотеке ВЦ РАН Автореферат разослан_»_2007 г

Учёный секретарь диссертационного совета

доктор физико-математических наук,

профессор В В Рязанов

Актуальность темы исследования

Интенсивное развитие технологии хранения информации, произошедшее за последние 30 лет, послужило стимулом для нового витка исследований по классической тематике проблемам связанным с автоматизацией ее интеллектуального анализа Одним из важных инструментов для решения мой задачи являются алгебраические методы распознавания образов, развиваемые с конца 70-х годов прошлого века школой академика Ю И Журавлеьа

Центральным в алгебраическом подходе к задачам распознавания образов является понятие универсальных ограничении, предъявляемых как к конечным функциям, так и функциям возникающим на промежуточных этапах построения классификатора — алгоритмическим операторам, корректирующим операциям решающим правилам При этом важное значение приобретают ыкне языки описания данных 01раниченин, коюрые удовлетворяют условию сохранения структурных свойств при всевозможных суперпозициях Одним нз таких языков и является предикатное задание

Примером такого задания служат монотонные функции, которые можно определить как множество функций, которые сохраняют некоторые частичные порядки на множествах значений и определения В общем случае, задаются два предиката одинаковой арности, и функция должна каждый набор, удовлетворяющий первому предикату, переводить в набор, удовлетворяющий второму

Для всякого способа(языка) описания дополнительных ограничений возникают свои чисто математические вопросы, которые в распознавании образов в первую очередь связаны чибо с диекриптивными(какие множества отображений можно задать посредством предикатных пар) и сложностнымн аспекта\ш(то есть трудоемкость работы с этим языком), гтибо с обобщающей способпостыо(качество получаемых алгоритмов) В данной работе мы разносторонне исследуем аппарат предикатного задания и, в основном, концентрируемся на первом аспекте

Проблемная ситуация заключается в том, что богатство языка предикатных пар для описания дополнительных ограничений подразумевает серьезную проблем} — согласование обучающей выборки с такими ограничениями, как правило, ^-трудная задача Отсюда и возникает стремление четко очертить области эффективной разрешимости Решению данной проблемы и посвящена бопылая часть работы

Цель работы

Основной целью работы является разработка математического аппарата методов распознавания образов основанных иа идее задания дополнительных ограничений в виде предикатных пар Изучаются дискриптивпые и слож-ностпые аспекты предикатных моделей, ставится вопрос о классификации предикатых ираничений с эффектвно-ралрешимои задачей со!ласования с обучающей выборкой

Основные задачи

• Исследование возможности выделения такого подмножества пар предикатов, которое обладало бы той же описательной силой для определения множеств отображений, что и все множество пар

• Характеризация предикатных ограничений е зффектпвио-рапрешимои задачей согласования с обучающей выборкой

• Построение алгоритмов согласования с обучающей выборкой для наиболее часто встречающегося типа предикатных ограничении — ограничении монотонности Исследования теоретической сложности данной задачи

о

Методы исследований

В процессе работы использовались методы теории сложности вычислении, ИР-трудиости, максимизации супермодулярпых функции Активно использовался аппарат универсальной алгебры, а именно теории замкнутых классов функции многозначной логики, предикатного описания таких классов, классификация Поста

Научная новизна

• Из множества всех возможных преднкатпых описании выделены максимальные и полечены необходимые и достаточные условия максимальности Показана связь условии максимальности слева с алгебраическим подходом Условия максимальности исследованы па примере отношения частичного порядка и предикатного описания множества выполняющих наборов 2-КНФ Исходя из требовании максимальности слева, для отношения «между» предложена аксиоматика и рассмотрены примеры подобных отношении

• Поставлена задача характеризации предикатных ограничении с эффективно-разрешимой задачей согласования с обучающей выборкой Предложен подход к ее получению через классификацию пар по свойствам предиката па множестве значений, при произвольном предикате на множестве определения Показана связь такой постановки с замкнутыми классами предикатов и функции многозначной логики Поставлена задача полного описания максимальных классов предикатов в общем случае Дапа полная классификация эффективно согласуемых с обучающей выборкой предикатных ограничении в булевом случае В общем случае введен важный с практической точки зрения порядковый класс предикатов и показана его эффективная разрешимость

• Рассмотрена задача выделения максимальной подвыборки обучающей выборки, не противоречащей ограничениям монотонности Показывается, что

данная задача является КР-трудиои и равносильна задаче о максимальном независимом множестве в специальных орграфах Подробно рассмотрены очень важные практически случаи последней задачи, когда частичный порядок, заданный на множестве ответов, является полным порядком либо имеет размерноеть 2 Показывается, что второй случаи сводится к максимизации квадратично-выпуклои функции па выпуклом множестве Для этого случая строится приближенный полипомиальпыи алгоритм, основанный па выпуклой оптимизации

• Введена схема определения допустимых категории алгебраического подхода через аппарат предикатного описания множеств отображении

Практическая и теоретическая ценность

Совокупность результатов, полученных в диссертации, представляет собой первое исследование по сложности методов распознавания основанных па предикатных ограничениях Разработанные критерии эффективной разрешимости, а также алгоритмы согласования с выборкой в случае монотонных ограничении, предназначены для непосредственного применения на практике

Аппробация работы

Положения и выводы, сформулированные в диссертации, получили квалифицированную аппробацию па XII, XIII Всероссийских конференциях «Математические методы распознавания образов» (Москва, 2005-2007 г), па международной научной конференции «Интеллектуализация обработки информации МОИ - 2006» (Алушта, Крым, 2000 г), на научной конференции МФТИ (Москва, 2006 г)

Публикации

По теме диссертации опубликовано 7 работ, в том числе 2 статьи в рецензируемых журналах 3 в трудах конференции, 2 электронные публикации

Структура н объем диссертационной работы

Диссертация изложена на 70 страницах машинописного текста и состоит из введения, 4 глав, заключения и списка литературы Список литературы состоит из 51 наименования

СОДЕРЖАНИЕ РАБОТЫ ВВЕДЕНИЕ

Во введении дается обоснование актуальности работы, с (формулированы цель и задачи диссертациоииои работы, определена научная новизна полученных результатов Описана общая структура диссертации

ГЛАВА 1. Предикатные пары как язык описания множеств отображений и максимальные предикатные пары

Глава 1 посвящена дискриптивным вопросам аппарата предикатных пар Рассматривается задача выделения такого подмножества пар предикатов которое обладает той же описательной силой для определения множеств отображении, что и все множество пар Глава состоит ю пяти параграфов

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

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

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

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

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

Первый параграф вводит основное понятие сохранения функцией предикатной пары

Определение 1. Пусть на множествах А и В заданы т-честные предикаты ра и рв, те рл С А"1 и рв С Вт Тогда будем говорить, что функция ¡р А -> В сохраняет пару (рл,Рв). если для любого набора (¡4,'2, ,гт) 6 рА имеем (<р0 Д^'г), 6 Рв Множество функ-

ций, сохраняющих пару (ра.Рв). будем обозначать Н (рл.Рв)

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

Во втором и третьем параграфах вводятся понятия максимальной пары относительно множества отображении и просто максимальной пары

П^сть зафиксировано множество отображении Н С {/ А —► В} и число т 6 N Рассмотрим множества пар отношении 21 = {(рА, рв) \рА С Ап Рв С В"1} и 21я {(ра, Рв) Iра Я: А"1, рв С Вт,Н С- Н (ра, Рв)} С 21 Множество 21я пеп>-сто, так как пара предикатов (Л™, Вт) сохраняется для любого отображения / А В Будем называть элементы 21# допустимыми относительно Я парами предикатов

Введем на множестве 21 два частичных порядка >', >'

(Ра. Рв) >' (Л. Рв) ^ Рл 2 Ра. Рв = Рв (Ра> Рв) >' (Р"ьР"в) ^ Ра = Ра Рв ^ Рв Определение 2. Пара (ра. Рв) называется Я-максималыюи слева, если элемент (ра. Рв) £ является максимальным в множестве 21я с частичным порядком >'

Определение 3. Пара (ра.Рв) называется Я-максималыюй справа, если элемент (рл, Рв) 6 21я является максимальным в множестве 21# < частичным порядком >'

Определение 4. Пара (рл,рв) называется #-максималыюй, если она является максимальной справа и слева одновременно Введем па множестве 21 частичные порядки >-', >-'

(РА'Рв) >■' (Ра Рв) н(Рл,Рв) = н{РьРв)^Ра 2 р'^р'в = Рв

(РА'Рв) (Рл Рв) & Н(р'а'Рв) = Н{р"А,р'в),р'А = р"А р'в С ¡)"в Определение 5 Пара (рл,рв) называется максимальной слева, если элемент (рА рв) € 21 является максимальным относительно частичного порядка у1

Определение 6 Пара (рл рв) называется максимальной справа, если элемент (рл,рв) 6 21 является максимальным относительно частичного порядка >-'

Определение 7 Пара (ра,Рв) называется максимальной, если она максимальна слева и справа одновременно

Показывается, что эти 2 понятия связаны следующим предложением Предложение 1. Пара {р\,рв) £ 21 максимальна справа(слева) тогда и только тогда, когда она ^-максимальна справа(слева), при Н = Н (рА,рв) Другая характеризация максимальных слева предикатных пар получается пз следующей доказанной теоремы Введем некоторые определения

Определение 8 Пусть дано множество г, 6 А, где г = 1,п, причем па А задан т-местпыи предикат р\ Обозначим БЬ (ра, {/,}"=1) и назовем рл - (труктурои {/,} с ледующее подмпожес тво В"1, где Д, = {1,2, , п }

(А4,{МГ=1) = {('ь (''и, ,1,т)Ерл}

Например, в случае, когда 1, = г и (г, , г) £ рл, {£,}"=1) = В™

Определение 9. Пусть на множествах Ах, , А, заданы т-местные предикаты ра^ ,рл, соответственно Тогда назовем декартовым произведением этих предикатов и обозначим х х р^ т-местиыи предикат па Ах х х Ач, такой, что {(«}, , , , , а™)) 6 рА1 х х ра, тогда, и только тогда,

когда для любого г = 1, ь , а™) 6

Определение 10. Пусть на множестве А задан т-местшлй предикат рд Тогда т-местный предикат рл х У- Ра па назовем ь-ои степенью рд и обозначим р\

Теорема 1. Пусть даны множества и и на обоих множествах заданы т-местные предикаты р, и рг, и пусть 9Л0 - Н С Н {р,,р<>) Обозначим

- {Я % — Я{ г) = (к (г), , Ьр{ >)), Ь, € 9Л0} Для того, чтобы пара (р,,рс) была Я-максимальпа слева необходимо и достаточно, чтобы для всякого натуральною п и для любого множества ч3 6 3,, где ^ = 1,?!, существовали такие число р и функция Я €Е 9Лу, что 5^т(/),, {г^}".^) =

В параграфе 4 выясняется смысл максимальности слева предикатных пар в случаях частичных порядков и предикатного описания выполняющих наборов 2-КНФ Для частичных порядков доказано следующее

Предложение 2. Пусть заданы множества А, В и пара бинарных предикатов (рл,Рв), где рв ~ частичным порядок, ие являющийся тривиальной эквивалентностью Пара (ра,Рв) максимальна слева тогда и только тогда, когда предикат рл удовлетворяет свойствам транзитивности и рефлексивности

В параграфе 5 исходя из условий максимальности слева предлагается следующая аксиоматика отношения «между»

Определение 11. Тернарный предикат М заданный на множестве X назовем отношением «между», если он удовлетворяет условиям 1-4

1 АЬ('1,у,г) => Мк{г,у,1)

2 Мк(1, 1,у)&Мк(1,у,у)

3 Мк(1,у,г) Мк (у, 1, у)

4 А/, (/, у, ',)кМ, (//, г)ЬМк(у, 1, >/) =■> Л/, (т, t, г)

ГЛАВА 2 О предикатных ограничениях с эффективно-разрешимой задачей согласования с обучающей выборкой

Глава 2 посвящена характеризации предикатных ограничении с эффективпо-разрешимои задачей согласования с обучающей выборкой Глава состоит из пяти параграфов

1 Введение

2 Алгебраическая структура эффективно разрешимых классов предикатов

3 Максимальные классы предикатов в булевом случае

4 Эффективная разрешимость порядкового класса предикатов в общем случае

5 Открытые вопросы

В введении главы даются основные определения

Определение 12 Пусть задана модель Я = (А, Р,™1, , Р™'), где Р™' есть предикат арности т,, заданный па множестве А Сигпатурои модели Н называется последовательность (rrii, Jiik)

Определение 13. Пусть задана конечная модель Н — (А, Р™1, , Р™1) Назовем задачей FTS (P")(Fittmg to Training Set) оптимизационную задач}, входом для которой является некоторая конечная модель I — (B,Q™\ jQk'k) (с 1011 же сигнатурой что и Н) и конечный набор пар

П = {(т,, у,, w,) € В, у, £ А, ш, £ Длиной входа считаем J2 \B\W' +

где Нот (/, Н) — множество гомоморфизмов из / в Н

Таким образом, параметром всякой задачи являются лишь предикаты на множестве значении, или, иначе говоря, модель множества значении И под

к

■п

(п + 1) \В\ + г> |Л| + У] [log u',"| Требуется паиги

V

задачей классификации мы подразумеваем задачу перечисления таких моделей Я, для которых FTS (Н) является эффективно разрешимой задачей

Предложенный подход к классификации предикатных ограничении с эффективно-разрешимой задачей согласования может быть оправдан тем, что множество значении в задачах распознавания является конечным, и реляционная структура па нем бывает достаточно простои, чтобы явно проверить выполнение критериев эффективной разрешимости FTS(H) Эффективная же разрешимость FTS(H), в свою очередь, гарантирует, что оптимальная функция может быть эффективно найдена для любой конечной модели I (о которой можно думать как об объединении обучающей и контрольной выборок) Уточним понятие эффективной разрешимости

Определение 14. Пусть задано множество А и на нем задан класс предикатов S = {p"G- С Л"-}а€Д Если для любой модели Я = (А, Pf1, , Pf*), где Р™' £ S, задача FTS (Я) является разрешимой па машине Тьюринга за полпиомиалыюе от длины входа число шагов, то S называется эффективно разрешимым классом

Заметим, что эффективно разрешимые классы предикатов образуют частичный порядок по включению Интерес представляет вопрос о характе-ризации максимальных элементов данного порядка, то есть таких классов, которые не содержаться пи в каких других Назовем такие классы максимальными

В параграфе 2 выявляется алгебраическая структура эффективно разрешимых к пасс ов предикатов

Определение 15. Пусть р С А™ и / А" —> А Функция / сохраняет предикат р, если для любых (¡"i, , i'm) G р,г = 1 ,п справедливо

(/('1. .'")> >M'L -О) ер

Для множества функций F обозначим Inn (F) множество предикатов сохраняющихся для любой функции из F

Доказывается следующий основной результат

Теорема 2 Всякий максимальный класс предикатов S определяется

некоторым классом функции F, то есть 5 = Inu (F) При атом, для любого J € F,f Ап —> А, справедливо, что / (/1, /„) G {/i, , r„}, то есть j консервативна

Ясно, что F можно считать замкнутым относительно суперпозиций и замен переменных классом функций, так как взятие замыкания не изменяет Iriv (F) Параграф 3 по< вящен с ттедствням из этого факта и из широко известной классификации Поста замкнутых классов булевых функций Напомним стандартные обозначения из теории замкнутых классов булевых функций Т(д—функции сохраняющие 0 и 1, Л/01—монотонные функции сохраняющие О и 1 îSqi—самодвойственные функции сохраняющие 0 и 1 Основной результат таков

Теорема 3 Классы предикатов Irw (Toi), Inu (ЛУщ), Inu (Soi) и только они, максимальны в булевом случае то есть когда А = {0,1}

Как известно, в небулевом случае замкнутых классов функций континуальное множество Потому, подход основанный иа рассмотрении каждого замкнутого класса в отдельности неприменим Представляет интерес описать через отношение сохранения функцией предиката как можно более широкие эффективно разрешимые классы предикатов

Очевидно, что класс Inn (Moi) соответствует ограничениям монотонности и, как показано, такие охрапичешш в булевом случае эффективно разрешимы Обобщению этого факта и посвящен параграф 4

Пусть на А = {0,1, , А — 1} задан полный порядок < Для простоты будем полагать, что 0 < 1 < < А — 1 Положим для г, у е A, i А у = нтш {¿, у} , 7 Vу = шах {г, у} и введем класс предикатов Inn ({г A у, iV у}) Теорема 4. Класс Inu ({т A у, i V у}) — эффективно разрешимый класс предикатов

Следствие Для предиката полного порядка / >л у l — i V у справедливо что FT S (H = (А, >А) ) — полиномиально разрешимая задача

В доказательстве этого резучьтата активно использовался аппарат ушг-версатиной алгебры и теории максимизации супермодупярных функций

В параграфе 5 обсуждены некоторые открытые вопросы

ГЛАВА 3. Задача монотонизации выборки

В главе 3 рассматривается практически важная задача минимальной коррекции обучающей выборки для построения на основе скоректированнои монотонного отображения Глава состоит из шести параграфов

1 Постановка задачи мопотонизации выборки

2 Задача монотонизации выборки и максимальные независимые подмножества

3 NP-полнота MaxCMS

4 1-MaxCMS

5 2-MaxCMS

6 Приближенный алгоритм для 2-MaxCMS

В параграфе 1 поставлена следующая задача, обозначенная как MaxCMS(Maximal Consistent with Monotonicity Set)

MaxCMS. Заданы конечные множества Bn,Bm, где В, = {1, ,г} и на них частичные порядки >',>2 соответственно и функция ip В„ —» Вт Для каждого элемента г S В„ задан положительный целочисленный вес w, Требуется найти максимальное по весу подмножество В С В„, такое, что функция р, ограниченная на В, является монотонной, то есть Vi,j G

B[f>lj-xp(i) >2p(j)}

Определение 16. Множества. В С В„, такие, что функция <р, ограниченная на В, является монотонной, называются допустимыми

В параграфе 2 обсуждается связь между данной оптимизационной задачей и максимальным независимым множеством в орграфах специального типа

Введем на множестве В„ частичный предпорядок (напомним, что так называется трапзитивпыи и рефлексивный бинарный предикат)

Рассмотрим орграф <2 = (У,Е), где V = В„, а Е = i' —1 а'г5 (') 22 у (у)} Орграф также может быть задан равенствами V = Вп и Е — >1 ПХ, где Я- — дополнение бинарного предиката

Определение 17. Всякий орграф, множество дуг которого может быть представлено как пересечение некоторых частичного порядка и дополнения частичного предпорядка па вершинах орграфа называется специальным

Предложение 3 Максимальное допустимое множество равно максимальному независимому множеству специального орграфа С

Предложение 4. Пусть произвольный специальный орграф С задается множеством вершин V' = В„ с весами и1' и дуг Е' =>' П>-', причем заданы по отдельности >' и >-' (то есть множество дуг Е' не нужно декомпозировать) Тогда задача нахождения максимального независимого множества в таком орграфе полиномиально сводится к МахСМБ

В параграфе 3 доказана ЫР-трудпость МахСМБ Параграф 4 посвящен подзадачам МахСМБ — сЬМахСМБ Введем это понятие

Всякий частичный порядок па конечном множество можно представить как пересечение полных порядков на нем

Определение 18 Пусть па конечном множестве М задан частичный порядок > Размерностью частичного порядка > назовем минимальное число (I полных порядков >1, , >4, что > = >1 П П ~>,1

Рассмотрим задачу МахСМЭ с входом (>*, >2, <р, ш) для случая, когда размерность частичного порядка >2 равна с7 В этом случае >2=>1 Л Л >г/ Для соответствующего ¿тон задаче специального орграфа (3 = (У,Е) будет справедливо V = В.„ и Е =>х Л"х, где г х ] о 1 1 >-<1 3 и

/ >-„ ] (р (/) >„ р 0) И тогда,

Е =>1 п^Гп п>,1 л (Я" и и Я/) = (>' пхТ) и и (>! пх^)

Так как каждый из предикатов является транзитивным, то Е можно пред< тавить как объединение <1 транзитивных предикатов

Определение 19. Задача МахСМБ с входом (>', >2, <р, и;) для случая, когда размерность частичного порядка >2 равна с/, называется ^-МахСМБ Фактически доказано

Предложение 5. ¿-МахСМБ сводится к нахождению максимального независимого множества в орграфе С = (У,Е), где Е и и >-'1, и предикаты >-' трашитивпы, причем в (? нет циклов

Из предложения следует, что ЬМахСМБ сводится к нахождению максимального независимого множества в орграфе С = (V, Е) без циктов, удовлетворяющему условию транзитивности дуг если (и, и), (о,() € Е, то (и, I) £ Е Эта задача имеет полиномиальным алгоритм решения, так как граф, получаемый из орграфа й преобразованием дуг в неориентированные ребра, является графом сравнимости некоторого частичного порядка, то есть совершенным Далее в параграфе приведен один из алгоритмов ее решения, следуя Мохриигу

Параграфы 5 и б посвящены задаче 2-МахСМБ Показано, что задача сводится к квадратично-вогнутому программированию Кроме того, дтя пес строится приближенный полиномиальный алгоритм решения

ГЛАВА 4 Предикатное задание универсальных ограничений алгебраического подхода

В главе 4 вводится схема определения допустимых категории алгебраического подхода через аппарат предикатного описания множеств отображении Рассмотрим некоторый класс множеств I Пусть па каждом множестве А £ I задан ш-местпыи предикат рд и пусть дана категория Ф(1 р), объектами которой являются множества А и их декартовы степени А\ 8=1,2,3, , а множества морфизлов для любых А, В 6 I и л, г € N определяются равенством Нтп{А\В') — Н(р\,р'в) Скажем, что категория Ф(1,р) порождена классом всех таких пар {А,рд)

Доказан следующий результат

Теорема 5. Ранее введенные симметрические, функциональные категории допускают подобное описание

ВЫВОДЫ

• Из множества всех возможных предикатных описании выделены максимальные и получены необходимые н достаточные условия максимальности Как видно из полученных критериев дтя случаев описания монотонных функции и выполняющих наборов 2-КНФ, при заданном предикате на множестве значений, условие максимальности слева позволяет сделать выводы о некоторых алгебраических свойствах соответствующего предиката на множестве определения

• Ал1 ебраическая ссрукгура позволяет дать полную классификацию эффективно согласуемых с обучающеи выборкой предикатных ограничений в булевом случае В общем случае введен важный с практической точки зрения порядковый класс предикатов и показана его эффективная разрешимость

• Рассмотрена задача выделения максимальной подвыборки обучающей выборки, не противоречащей ограничениям монотонности Показывается, что данная задача является КР-труднои и равносильна задаче о максимальном независимом множестве в специальных орграфах

• Введена схема определения допустимых категорий алгебраического подхода через аппарат предикатного описания множеств отображении В рамках предлагаемой схемы показано, что ранее изученные монотонные, симметрические и функциональные категории допускают предикатное описание

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Таханов Р С Предикатное задание универсальных ограничений в алгебраическом подходе к задачам распознавания , : ЖВМ и МФ 2007, 47, № 3 527-532

[2] Таханов Р С Максимальные предикатные задания множеств отображений //' ЖВМ и МФ, 2007 47, № 9, 1G69-1G81

[3] Таханов Р С О классах функций, сохраняющих отношения, в алгебраическом подходе к проблеме распознавания // Труды 49 конференции МФТИ, 264-265

[4] Таханов Р С Предикатное описание множеств отображений и максимальные предикатные пары // Искусственный интеллект 2006, № 2

[5] Таханов PC Задача монотонизации выборки // Доклады Всероссийской конференции ММРО-13, 2007

[6] Takhanov R Oil the monotonization of the tiammg bet '/ Available online http ','aixiv org/abs/ 0705 2765

[7] Takhanov R On predicate constraints with efficiently solvable task of fitting to tiammg set // Available online http arxiv org/abs/0708 3226

Подписано в печать 02 10 2007г Формат 60x90 1/16 уел Печ л 2,3 п л Тираж 100 экз Заказ №132 Отпечатано в типографии «Полиграф экспресс» 194223, Санкт-Петербург, ул Курчатова, 9 Тел (812)702-14-15,297-48-97

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 NP-полнота MaxCMS.

3.4 1-MaxCMS

3.5 2-MaxCMS

3.6 Приближенный алгоритм для 2-MaxCMS.

3.6.1 Обсуждение

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

4.1 Основные понятия и формализм.

4.1.1 Ограничения монотонности.

4.1.2 Симметрические ограничения.

4.1.3 Функциональные ограничения.

Интенсивное развитие технологий хранения информации, произошедшее за последние 30 лет, послужило стимулом для нового витка исследований по классической тематике—проблемам связанным с автоматизацией ее интеллектуального анализа. Одним из важных инструментов для решения этой задачи являются методы распознавания образов, развиваемые с начала 50-х годов прошлого века[2, 12, 28, 24, 5, 13].

Характерной особенностью задач решаемых посредством методов распознавания является сложность количественного описания или моделирования сущностных процессов исследуемых систем. При этом, порой практически устраивающим исследователя решением является отображение из заранее заданных множества начальных информаций(называемых дальше объектами) во множество ответов. Информация же о виде этой зависимости задается в виде конечного массива прецедентов вида «объект - ответ». Таким образом, с формальной точки зрения есть все предпосылки рассматривать задачу распознавания образов как частный случай задачи экстраполяции функции.

Очевидная неполнота информации, заданной в конечной структуре (массив прецедентов) об искомом отображении, которое, вообще говоря, может определяться бесконечным числом степеней свободы, привела исследователей к разработке большого числа моделей алгоритмов. Модель алгоритмов, или иначе говоря, некоторое подмножество отображений из множества объектов во множество ответов, должна была сыграть роль той недостающей информации для полного либо частичного восстановления искомого отображения. При этом, разработанные модели алгоритмов, как правило, были основаны на интуитивных эвристических соображениях, вроде удовлетворения искомого отображения условиям гладкости, краткости описания, структурной простоты, линейности и т. д.

Удобным и часто используемым способом описания дополнительных ограничений являются предикатные пары. Примером такого описания служат монотонные функции, которые можно определить как множество функций, которые сохраняют некоторые частичные порядки на множествах значений и определения. В общем случае, задаются два предиката одинаковой арности, и функция должна каждый набор, удовлетворяющий первому предикату, переводить в набор, удовлетворяющий второму.

Одной из причин рассмотрения аппарата предикатных пар для описания дополнительных ограничений стало развитие алгебраического подхода к задачам распознавания[6, 18, 21, 7, 8, 9].

В алгебраическом подходе результирующее отображение ищется как суперпозиция некоторых алгоритмических операторов из множества объектов в заранее заданное множество оценок, корректирующих операций над множеством оценок и, наконец, решающих правил, действующих из множества оценок во множество ответов. При этом, суперпозиция строится таким образом, чтобы ее результат удовлетворял как прецедентным ограничениям, так и некоторым дополнительным ограничениям (называемым также универсальными), которые могут быть свойственны задаче.

Поиск языка подходящего для описания дополнительных ограничений алгебраического подхода привел к созданию теории локальных и универсальных ограничепий[18, 21, 14, 15, 16, 17, 19]. Так как в алгебраическом подходе требуется удовлетворить дополнительным ограничениям при построении достаточно сложных суперпозиций, неудивительно, что математической моделью этих ограничений стали допустимые категории[3]. Условие замкнутости операции суперпозиции морфизмов категории в контексте алгебраического подхода приобретает новое понимание, так как именно это условие наиболее созвучно идее сохранения некоторого структурного свойства отображениями при их суперпозиции.

Однако предикатное описание удовлетворяет подобным же свойствам. Определяя на множествах А, В, С произвольные m-местные предикаты Ра,Рв,Рс) легко видеть, что если а £ II (рл,Рв) ,b £ Н (рв,рс), то bo а — с Е Н(рА,рс), где II (рх,ру) — множество функций / : х —> у сохраняющих предикатную пару (рх, Ру). Именно вышеупомянутое свойство предикатного описания множеств отображений, то есть способность описывать структурные ограничения на множества отображений, которые сохраняются при их суперпозиции, и было основным побудительным мотивом обращения к нему в данной работе.

Заметим, что для всякого способа(языка) описания дополнительных ограничений возникают свои чисто математические вопросы, которые в распознавании образов в первую очередь связаны либо со сложностными аспектами (то есть трудоемкость работы с этим языком), либо с обобщающей способно-стью(качество получаемых алгоритмов).

В данной работе мы разносторонне исследуем аппарат предикатного задания и, в основном, концентрируемся на первом аспекте. Здесь, в первую очередь, подразумевается классификация предикатных ограничений со сложност-ной точки зрения. Специфика задач распознавания заключается в том, что весьма желательным свойством предикатной пары, задающей дополнительные ограничения, является возможность эффективно разрешить оптимизационную задачу согласования дополнительных ограничений с ограничениями обучающей выборки(массива прецедентов). И потому интерес представляет вопрос о характеризации таких предикатных пар.

Работа состоит из четырех глав.

Первая глава посвящена дискриптивным вопросам аппарата предикатных пар. Рассматривается задача выделения такого подмножества пар предикатов, которое обладает той же описательной силой для определения множеств отображений, что и все множество пар.

Вводится основное понятие сохранения функцией предикатной пары. Рассматривается вопрос однозначности соответствия между множествами отображений и предикатными парами. На множестве всех предикатных пар задающих данное множество отображений вводится естественный частичный порядок и исследуются максимальные относительно этого порядка предикатные пары. Далее дается альтернативное описание максимальных предикатных пар, которое оказывается созвучным идеологии алгебраического подхода. Вопрос о максимальности предикатных пар рассматривается для некоторых частных случаев, в том числе случая частичных порядков, отношений «между». Рассматривается предикатное описание множества выполняющих наборов 2-КНФ и дается полное описание максимальных пар задающих данное множество.

Вторая глава посвящена характеризации предикатных ограничений с эффективно-разрешимой задачей согласования с обучающей выборкой. Одним из подходов к ее получению является классификация пар по свойствам предиката на множестве значений, при произвольном предикате на множестве определения. Показана связь такой постановки с замкнутыми классами предикатов и функций многозначной логики. Дана полная классификация эффективно согласуемых с обучающей выборкой предикатных ограничений в булевом случае. В общем случае, введен важный с практической точки зрения порядковый класс предикатов и показана его эффективная разрешимость. Заметим, что в исследованиях по задаче «Обобщенная выполнимость»[33, 40, 41] рассматривалась похожая проблема. В этих работах ставилась задача описания предикатных пар, для которых нахождение сохраняющей пару функции может быть проведено эффективно.

В третьей главе рассматривается практически важная задача минимальной коррекции обучающей выборки для построения на основе скоректирован-ной монотонного отображения. Показывается, что эта задача в общем случае NP-трудна. Рассматривается ее частный случай, когда частичный порядок на множестве значений имеет размерность 2. Данная задача сводится к квадратично-вогнутому программированию. Кроме того, для нее строится приближенный полиномиальный алгоритм решения.

Во четвертой главе вводится схема определения допустимых категорий алгебраического подхода через аппарат предикатного описания множеств отображений. В рамках предлагаемой схемы показывается, что ранее изученные монотонные, симметрические и функциональные категории допускают предикатное описание.

Благодарности

Чувство глубочайшей благодарности автор выражает своему Учителю члену-корреспонденту РАН Константину Владимировичу Рудакову, за постановку задачи и неоценимую помощь на всех этапах работы.

Заключение

Работа выполнена в рамках алгебраического подхода и посвящена проблеме описания дополнительных ограничений посредством пар ш-местных предикатов.

1) Из множества всех возможных предикатных описаний выделены максимальные и получены необходимые и достаточные условия максимальности. Показана связь условий максимальности слева с алгебраическим подходом.

2) Условия максимальности исследованы на примере отношения частичного порядка и предикатного описания множества выполняющих наборов 2-КНФ. Показано, что при заданном предикате на множестве значений из необходимых условий максимальности слева следуют некоторые свойства предикатов на множестве определения.

3) Исходя из требований максимальности слева, для отношения «между» предложена аксиоматика и рассмотрены примеры подобных отношений.

4) Поставлена задача характеризации предикатных ограничений с эффективно-разрешимой задачей согласования с обучающей выборкой. Предложен подход к ее получению через классификацию пар по свойствам предиката на множестве значений, при произвольном предикате на множестве определения. Показана связь такой постановки с замкнутыми классами предикатов и функций многозначной логики. Поставлена задача полного описания максимальных классов предикатов в общем случае.

5) Дана полная классификация эффективно согласуемых с обучающей выборкой предикатных ограничений в булевом случае.

6) В общем случае введен важный с практической точки зрения порядковый класс предикатов и показана его эффективная разрешимость.

7) Рассмотрена задача выделения максимальной подвыборки обучающей выборки, не противоречащей ограничениям монотонности. Показывается, что данная задача является NP-трудной и равносильна задаче о максимальном независимом множестве в специальных орграфах.

8) Подробно рассмотрены очень важные практически случаи последней задачи, когда частичный порядок, заданный на множестве ответов, является полным порядком либо имеет размерность 2. Показывается, что второй случай сводится к максимизации квадратично-выпуклой функции на выпуклом множестве. Для этого случая строится приближенный полиномиальный алгоритм, основанный на выпуклой оптимизации.

9) Введена схема определения допустимых категорий алгебраического подхода через аппарат предикатного описания множеств отображений. В рамках предлагаемой схемы показано, что ранее изученные монотонные, симметрические и функциональные категории допускают предикатное описание.

1. Боднарчук В.Т., Калужнин JT.A., Котов В.Н., Ромов Б.А. Теория Галуа для алгебр Поста // Кибернетика, 1969, № 3, 1-10, № 5, 1-9.

2. Бонгард М.М. Проблема узнавания. М.: Наука, 1967. 320 с.

3. Букур И., Деляну А. Введение в теорию категорий и функторов. М.: Мир, 1972. 260 с.

4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. Мир. 1982.

5. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. 511 с.

6. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики, 1979, Вып. 33, 5-68

7. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. I // Кибернетика. 1977. № 4. С. 5-17.

8. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. II // Кибернетика. 1977. № 6. С. 21-27.

9. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. III // Кибернетика. 1978. № 2. С. 35-43.

10. Журавлев Ю.И., Рудаков К.В. Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. М.: Наука, 1987. С. 187-198.

11. Марчепков С.С. Замкнутые классы булевых функций // М. ФИЗМАТ-ЛИТ. 2004.

12. Минский М., Пейперт С. Персептроны. М.:Мир, 1971.262 с.13 14 [1516 1718 19 [2021