Московский государственный университет имени М.В. Ломоносова

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

Дорофеев Николай Юрьевич

О свойствах задач и алгоритмов разметки

точечных конфигураций

Специальность 01.01.09 – дискретная математика и математическая

кибернетика

АВТОРЕФЕРАТ

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

Москва – 2012

Работа выполнена на кафедре математических методов прогнозирования факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.

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

Научный руководитель:

Чехович Юрий Викторович доктор физико-математических наук

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

Сметанин Юрий Геннадиевич кандидат физико-математических наук Филипенков Николай Владимирович Московский физико-технический институт

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

(государственный университет)

Защита диссертации состоится « 15 » марта 2013 г. в 11 часов на заседании диссертационного совета Д в Московском 501.001. государственном университете имени М. В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685.

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».

Автореферат разослан « 13 » февраля 2013 г.

Ученый секретарь диссертационного совета профессор Н.П. Трифонов

Общая характеристика работы

Актуальность темы. Задачи распознавания образов возникают в различных областях человеческой деятельности, и решение таких задач является трудомкой теоретической и технической задачей. Во второй половине XX века академиком РАН Ю.И. Журавлвым были заложены основы алгебраического подхода к проблеме распознавания образов. В рамках алгебраического подхода для получения корректных (точных на прецедентах) алгоритмов используются эвристические распознающие операторы, к которым применяются корректирующие операции с целью компенсировать недостатки одних эвристических алгоритмов за счт других. Благодаря активной научной деятельности Ю.И. Журавлва и учеников его школы к настоящему времени завершено создание и исследование основ алгебраического подхода.

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

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

В работах кандидата физико-математических наук Ю.В. Чеховича и К.В.

Рудакова была разработана общая проблемно-ориентированная теория для задач синтеза обучаемых алгоритмов выделения трендов и задач классификации с теоретико-множественными ограничениями. В этих работах было показано, как задачу выделения трендов можно свести к задаче разметки точечных конфигураций. Однако задача выделения трендов является лишь одним из примеров задачи, сводимой к задаче разметки элементов конечных плоских конфигураций. К этому виду сводятся многие инженерные, экономические и медицинские задачи. Так в работах кандидата физико-математических наук Коваленко Д.С. и кандидата технических наук Костенко В.А. упомянутая теория была успешно применена в процессе исследования задачи определения нештатного поведения динамических систем по показаниям датчиков. Таким образом, создание полноценной проблемно-ориентированной теории для решения задач в таком виде является актуальным направлением для исследований. При этом существует значительный класс задач, к которым результаты, полученные в работах Ю.В. Чеховича и К.В. Рудакова, были плохо применимы или неприменимы вовсе. В настоящей работе исследуется расширенная постановка задачи: исследуется новый класс задач, в которых метки являются непрерывными. Переход от дискретного словаря разметки к континуальному пространству меток позволяет применить результаты работы к более широкому классу задач и существенно дополнить имеющуюся проблемноориентированную теорию для задач синтеза обучаемых алгоритмов разметки точечных конфигураций как задач с теоретико-множественными ограничениями.

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

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

получить критерии разрешимости и регулярности таких задач;

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

Научная новизна. Все результаты, полученные в работе, являются новыми.

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

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

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

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

Апробация работы. Результаты работы докладывались и обсуждались на:

XVI Международной научной конференции студентов, аспирантов и молодых учных «Ломоносов-2009» (Москва, 2009 г.) 14-й Всероссийской конференции «Математические Методы Распознавания Образов (ММРО-14)» (Суздаль, 2009 г.) XVII Международной научной конференции студентов, аспирантов и молодых учных «Ломоносов-2010» (Москва, 2010 г.) 8-й Международной конференции «Интеллектуализация Обработки Информации (ИОИ-2010)» (Республика Кипр, Пафос, 2010 г.) XIX Международной научной конференции студентов, аспирантов и молодых учных «Ломоносов-2012» (Москва, 2012 г.) 9-й Международной конференции «Интеллектуализация Обработки Информации (ИОИ-2012)» (Черногория, Будва, 2012 г.) научном семинаре отдела Интеллектуальных систем Вычислительного центра имени А.А. Дородницына РАН Описание отдельных результатов работы включены в отчты по проектам РФФИ №№ 07-01-00711-а, 10-07-00717-а, 10-01-09406-моб_з, 12-01-09366-моб_з.

Личный вклад. Все результаты, выносимые на защиту, получены автором самостоятельно. Постановка задачи была выполнена совместно с научным руководителем.

Публикации. Материалы диссертации опубликованы в 9 работах [1-9], из них работы [4, 8] опубликованы в рецензируемых изданиях из списка ВАК.

Структура и объм диссертации. Работа состоит из оглавления, введения, трх глав, заключения, списка иллюстраций и списка литературы. Содержание работы изложено на 76 страницах. Список литературы включает наименования. Текст работы иллюстрирован 22 рисунками.

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

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

В разделе 1.1 описываются пространства начальных и финальных информаций (окрестностей и меток соответственно). Конечной плоской конфигурацией (КПК) называют конечное множество точек на плоскости в заданной системе i1 i2.

Определение 1. Окрестностью точки S i S d называется пара, содержащая саму включающую эту точку: OS S i S i, PS,1 i d. Точку Si называют опорной точкой окрестности OS S i. d Под словами разметка (метка) окрестности понимается метка опорной точки окрестности.

Окрестность, содержащая одну лишь опорную точку, называется вырожденной.

На конфигурации задана система окрестностей OS, если каждой точке d конфигурации поставлена в соответствие некоторая ее окрестность. Система окрестностей задана на K, если на каждой конфигурации из K задана система окрестностей. Пусть далее на K задана невырожденная система окрестностей, т.е. система, не содержащая окрестностей, которые были бы вырожденными.

Словарь разметки — конечное множество меток Множество M M, M, где — специальная метка, интерпретируемая как не размечено, будем называть расширенным словарем разметки.

При фиксированном множестве меток M и, соответственно, расширенном множестве меток M разметкой длины d называется любая последовательность d длины d1, если i M, или частичной разметкой длины d, если i M.

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

Определим результат работы алгоритма разметки конфигураций A как вектор, полученный в результате применения алгоритма разметки окрестностей A к окрестности каждой точки конфигурации: A S d A OS S 1,, A OS S d.

Будем считать, что на множестве окрестностей задана некоторая метрика.

Метрику, заданную на пространстве меток M* обозначим l(1,2). Доопределим l(1,2) на M, потребовав, чтобы расстояние от всякой метки из M* до равнялось 0.

Введм — параметр задачи, устанавливающий соответствие между метриками и l. Этот параметр указывает, насколько должны быть близки метки, в зависимости от близости окрестностей. При больших значениях параметра точкам, окрестности которых значительно близки, можно будет сопоставить достаточно различные метки. При малых значениях, наоборот, потребуется даже мало похожим окрестностям сопоставлять близкие метки. В предельном случае при задача сводится к случаю сдвиг-эквивалентности: сдвигэквивалентным окрестностям должны назначаться одинаковые метки, в то время как на разметку остальных окрестностей никакие ограничения, связанные с локальностью, не накладываются.

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

Для описания требований к подходящим разметкам, вводятся системы аксиом дополнительные знания эксперта о предметной области. Из аксиом вытекают ограничения на семейства алгоритмов разметки.

эффективно вычислимых предикатов = {1, …, k}:

Тот же символ используется и для обозначения конъюнкции предикатов i:

Действие аксиом на пространстве конфигураций K задатся как:

Метка M называется допустимой для окрестности O, если выполнено равенство (O, ) = 1. Частичная разметка d конфигурации S d называется допустимой, если выполнено равенство S d, d 1.

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

Определение 4. Система аксиом разметки = {i} называют непрерывно подходящими метками, удовлетворяющими условию близости, и произвольной новой окрестности существует метка, которую можно было поставить в соответствие новой окрестности, продолжив тем самым имеющуюся разметку, таким образом, что метки будут подходящими и удовлетворяющими условию близости.

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

Пусть имеется некоторое конечное множество шаров в пространстве M*:

Система аксиом R задатся таким образом, чтобы для всякой окрестности из множество допустимых меток являлось одним из шаров в R:

Теорема 1. Для того чтобы система аксиом R являлась непрерывно покрывающей необходимо выполнение следующего условия:

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

В дальнейшем предполагается, что зафиксирована некоторая непрерывно покрывающая система аксиом ={i}.

В разделе 1.3 доказываются критерии разрешимости и регулярности задач разметки точечных конфигураций.

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

Множеством окрестностей OH набора прецедентов H в смысле системы окрестностей называется множество окрестностей всех точек всех конфигураций набора H. Множеством размеченных окрестностей OH набора прецедентов называется множество: OH O, O OH, M.

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

Определение 5. Алгоритм разметки A называется --H-локальным тогда и только тогда, когда для любых окрестностей O1 и O2 выполнено условие:

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

Определение 6. Задача Z называется --локально разрешимой, если и только если для нее существует подходящий корректный --H-локальный алгоритм A.

Определение 7. Задача Z --локально разрешима тогда и только тогда, когда существует непрерывная функция f : M такая, что (O, f(O)) = 1 для всякой окрестности O из.

Теорема 2. Определения 6 и 7 эквивалентны.

противоречивым, если для всех i выполнено Sid, id 1, но существуют O1, 1, O2, 2 OH такие, что l(1, 2) > (O1, O2).

Теорема 3. Задача Z --локально разрешима тогда и только тогда, когда набор прецедентов H не является --локально противоречивым.

Определение 9. Задача разметки конечных плоских конфигураций Z называется --локально регулярной тогда и только тогда, когда Z --локально разрешима для любых допустимых разметок всех окрестностей из OH.

Теорема 4. --локально разрешимая задача Z является --локально регулярной тогда и только тогда, когда для произвольных O1, O2 OH из правил разметки вытекает выполнение условия:

где 1 и 2 — произвольные допустимые метки для O1 и O2 соответственно.

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

В разделе 2.1 вводятся основные конструкции и понятия, использующиеся в этой главе.

Рассматривается задача синтеза алгоритмов, реализующих отображения из информаций f. Предполагается, что на пространстве i определена метрика i, а на пространстве f задана метрика f. Структурным параметром задачи является масштабирующая константа, устанавливающая соответствие между Конструкции алгебраического подхода к проблеме синтеза корректных алгоритмов основаны на использовании промежуточного по отношению к i и f пространства оценок e. При этом корректные алгоритмы синтезируются на базе эвристических информационных моделей, т.е. параметрических семейств отображений из i в f, представляющих собой специальные суперпозиции алгоритмических операторов (отображений из i в e ) и решающих правил (отображений из ep в f, где p — арность решающего правила). Пространства начальных и финальных информаций определяются проблемной областью и далеко не всегда удобны для непосредственной работы с ними. В то же время пространство оценок может быть выбрано из некоторых произвольных соображений: в зависимости от вида алгоритмических операторов, желаемого семейства корректирующих операций и др. Введение пространства оценок позволяет в дальнейшем определить понятие корректирующих операций на основе операций над пространством оценок.

отображение:

Для рассматриваемых в диссертационной работе задач с теоретикомножественными ограничениями модели алгоритмов M строятся на базе структурных индексов. В этом случае модель M строится в виде где при всех L и W выполнено равенство Для формализации понятия теоретико-множественных ограничений вводится корректных алгоритмов для начальной информации I i0.

Для формализации требования назначать похожим начальным информациям схожие финальные информации вводится множество:

Набор называется покрывающим, если для любого Ii из i выполнено условие Ii. Набор называется непрерывно покрывающим, если для любого Ii из i выполнено условие R Ii.

В дальнейшем рассматривается произвольный фиксированный непрерывно покрывающий набор.

Множеством наборов допустимых прецедентов называется множество множество наборов длины q попарно различных элементов.

Определение 10. Модель M называется -полной, если выполнены условия:

Условия (1) и (2) независимы. Кроме того, при выполнении условия (2), условие (1) эквивалентно условию (1'):

Цель данного и следующего разделов — описание условий, которым должны удовлетворять семейства M1, F и M 0, чтобы в совокупности обеспечивать Определение 11. Семейство решающих правил M1 называется -полным, если является -полной.

Определение 12. При фиксированном -полном семействе решающих правил M1 семейство корректирующих операций F называется M1 --полным, если Определение 13. При фиксированном -полном семействе решающих правил алгоритмических операторов M 0 называется F - M1 --полной, если модель В разделе 2.2 описываются условия, которым должны удовлетворять семейства любом неотрицательном целом p выполняется M1p C | C : ep f, т.е.

множество M1p составляют p-арные решающие правила из M1. При этом для любого X e оказывается, естественно, выполненным условие:

Определение 14. Для произвольного I i из i множеством p M1, Ii называется пересечение в p-ой декартовой степени пространства оценок e всех полных прообразов множества R I i относительно решающих правил арности p:

Множество всех допустимых p-проекций для семейства M1 и элемента I i обозначается p M1, Ii. Для произвольного I i из i вводится множество M1, I i функций выбора допустимых проекций:

где B e — множество всех подмножеств e.

Для каждой функции выбора допустимых проекций из M1, Ii вводятся следующие обозначения:

Теорема 5. Для -полноты семейства решающих правил M1 необходимо и достаточно, чтобы при любом I i из i было выполнено условие:

Далее считается, что зафиксировано произвольное -полное семейство решающих правил M1.

называется M1 -полной для Ii, если выполнены следующие условия:

Пусть множество Fp составляют p-арные корректирующие операции из F, где Определение 17. Для произвольных из L, Ii из i и произвольной функции выбора допустимых проекций из M1, Ii множеством p Ii, называется пересечение в p-ой декартовой степени пространства оценок e всех полных прообразов множества X Ii, относительно корректирующих операций из Fp :

Определение 18. Для произвольных из L, Ii из i и произвольной из допустимой p-проекцией, если выполнены условия:

Множество всех F - M1 -допустимых p-проекций для L и Ii i и функции выбора допустимых проекций из M1, Ii обозначается как p Ii,,. Для функций выбора F - M1 -допустимых p-проекций задатся как:

Для каждой функции выбора F - M1 -допустимых p-проекций из множества Ii,, вводятся обозначения:

F {F | L} необходимо и достаточно, чтобы Ii i существовала M1 полная для Ii система подмножеств G Ii {X Ii, | X Ii, e, Ii } такая, что для любого из Ii существует в L такое, что Далее считается, что зафиксировано произвольное M1 --полное семейство корректирующих операций F F | L.

Определение 19. Пусть зафиксирована M1 -полная система подмножеств выполнено условие:

Можно заметить, что по своей структуре полученные критерии напоминают аналогичные критерии в работах К.В. Рудакова и Ю.В. Чеховича. Отличие от результатов, полученных в этих работах, заключается в том, что вместо дискретного пространство f имеет непрерывный характер, а множество, прообразы которого строятся относительно семейств решающих правил, корректирующих операций и моделей алгоритмических операторов является более узким в силу дополнительно наложенных метрических ограничений.

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

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

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

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

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

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

На защиту выносятся следующие результаты:

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

2. Получены и доказаны критерии разрешимости и регулярности задач синтеза обучаемых алгоритмов разметки точечных конфигураций при наличии согласованных метрик на объектах и классах.

3. Получены и доказаны критерии полноты моделей алгоритмов, моделей алгоритмических операторов, семейств корректирующих операций и семейств расширенной постановке.

4. Разработан программный стенд и проведены вычислительные эксперименты, подтверждающие полученные теоретические результаты.

Публикации по теме диссертации:

1. Дорофеев Н.Ю. Разрешимость и регулярность задач «нечткой» разметки точечных конфигураций // Сборник тезисов XVI Международной научной конференции студентов, аспирантов и молодых учных «Ломоносов-2009», секция Вычислительная Математика и Кибернетика. Изд.: Москва, Издательский отдел факультета ВМК МГУ, 2009. С. 2. Дорофеев Н.Ю. Разрешимость и регулярность задач нечткой разметки точечных конфигураций // Сборник тезисов лучших дипломных работ года. Изд.: Москва, Издательский отдел факультета ВМК МГУ, 2009. С. 94-95.

3. Дорофеев Н.Ю. Разрешимость и регулярность задач нечткой разметки точечных конфигураций // Доклады 14-й Всероссийской конференции «Математические Методы Распознавания Образов (ММРО-14)». Изд.:

Москва, МАКС Пресс, 2009. С. 29– 4. Doropheev N.Yu. The Criteria for Completeness of Algorithms of Fuzzy Marking of Point Configurations // Pattern recognition and image analysis. 2010. Vol. 20. № 4. Pub.: MAIK Nauka/Interperiodica. pp. 419–426.

5. Дорофеев Н.Ю. Разрешимость задач нечткой классификации элементов точечных конфигураций // Сборник тезисов XVII Международной научной конференции студентов, аспирантов и молодых учных «Ломоносов-2010», секция Вычислительная Математика и Кибернетика. Изд.: Москва, Издательский отдел факультета ВМК МГУ, 2010. С. 83- 6. Дорофеев Н.Ю. Критерии полноты моделей алгоритмов нечткой разметки точечных конфигураций // Доклады 8-й Международной конференции «Интеллектуализация Обработки Информации (ИОИ-2010)». Изд.: Москва, МАКС Пресс, 2010. С. 35– 7. Дорофеев Н.Ю. О свойствах задач и алгоритмов нечткой разметки элементов точечных конфигураций // Сборник тезисов XIX Международной научной конференции студентов, аспирантов и молодых учных «Ломоносов-2012», секция Вычислительная Математика и Кибернетика. Изд.: Москва, Издательский отдел факультета ВМК МГУ, 2012. С. 92- 8. Дорофеев Н.Ю. Критерии полноты алгоритмов нечткой разметки точечных конфигураций // Журнал вычислительной математики и математической физики. Изд.: МАИК "Наука/Интерпериодика", 2012. Т. 52. № 8. С. 1551– 1568.

9. Дорофеев Н.Ю. О свойствах задач и алгоритмов разметки элементов точечных «Интеллектуализация Обработки Информации (ИОИ-2012)». Изд.: Москва, Торус Пресс, 2012. С. 63–