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

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

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

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

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

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

кибернетика

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

005050823

Москва-2012

I 1 МАР 2013

005050823

Работа выполнена на кафедре математических методов прогнозирования

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

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

Чехович Юрий Викторович Официальные оппоненты: доктор физико-математических наук

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

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

Московский физико-технический институт (государственный университет)

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

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

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

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

профессор

Н.П. Трифонов

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

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

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

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

В работах кандидата физико-математических наук Ю.В. Чеховича и К.В. Рудакова была разработана общая проблемно-ориентированная теория для задач синтеза обучаемых алгоритмов выделения трендов и задач классификации с

3

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

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

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

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

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

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

4

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

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

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

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

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

• XVI Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009» (Москва, 2009 г.)

• 14-й Всероссийской конференции «Математические Методы Распознавания Образов (ММРО-14)» (Суздаль, 2009 г.)

• XVII Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2010» (Москва, 2010 г.)

• 8-й Международной конференции «Интеллектуализация Обработки Информации (ИОИ-2010)» (Республика Кипр, Пафос, 2010 г.)

• XIX Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2012» (Москва, 2012 г.)

• 9-й Международной конференции «Интеллектуализация Обработки Информации (ИОИ-2012)» (Черногория, Будва, 2012 г.)

• научном семинаре отдела Интеллектуальных систем Вычислительного центра имени A.A. Дородницына РАН

Описание отдельных результатов работы включены в отчёты по проектам РФФИ №№07-01-00711-а, 10-07-00717-а, 10-01-09406-моб_з, 12-01-09366-моб_з.

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

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

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

Содержание работы

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

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

б

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

В разделе 1.1 описываются пространства начальных и финальных информации (окрестностей и меток соответственно). Конечной плоской конфигурацией (КПК) называют конечное множество точек на плоскости в заданной системе координат. Конфигурацию можно представить в виде вектора =(5',...,£"') = ((/',V1),...,(/'',V1')). Обычно считается, что либо <...</'', либо

<...<[и, причем при /' = /'*'выполнено Множество всевозможных с1-

точечных плоских конфигураций обозначают 1С1, при этом ^ = есть

множество всех конфигураций. Подконфигурацией Р-,, конфигурации .V'' называется любое подмножество точек из Б11: Р-„ с Я'', при этом подконфигурация называется связанной, если =(.<?'', У1 ) с 5'', где

/,<г-2.

Определение 1. Окрестностью точки с 5''называется пара, содержащая саму точку $ и некоторую связную подконфигурацию А,, конфигурации .V'',

включающую эту точку: О^ (»5') = {5',}, 1 <гс?. Точку 5" называют опорной

точкой окрестности О-,,

Под словами ''разметка (метка) окрестности" понимается метка опорной точки окрестности.

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

Словарь разметки — конечное множество меток М = {/Д...,//"},т£1. Множество МА =Мид, ДеМ, где А — специальная метка, интерпретируемая как "не размечено", будем называть расширенным словарем разметки. При фиксированном множестве меток М и, соответственно, расширенном множестве меток МЛ разметкой длины <1 называется любая последовательность Д11 длины (¡>1, если // б М, или частичной разметкой длины с1, если // е МЛ. Пусть зафиксирован некоторый словарь разметки, для элементов которого тем или иным образом задано отношение близости. Осуществим погружение этого множества в метрическое пространство с сохранением имеющегося отношения сходства. Это погружение может быть осуществлено различными способами в зависимости от эмпирических соображений эксперта. Результат погружения будем называть пространством меток и обозначать М'. Аналогично расширенному словарю разметки строится расширенное пространство меток

М1 = М' и д.

Определение 2. Алгоритмом разметки окрестностей А называется отображение А: П -»Мд, которое ставит в соответствие всякой нетривиальной окрестности некоторую метку из Л/д.

Определим результат работы алгоритма разметки конфигураций А как вектор, полученный в результате применения алгоритма разметки окрестностей А к окрестности каждой точки конфигурации: = (Л'1Л(бь, (з^)))-

Будем считать, что на множестве окрестностей задана некоторая метрика р. Метрику, заданную на пространстве меток М* обозначим Кр1 .¡х). Доопределим 1(ц',1-12) на , потребовав, чтобы расстояние от всякой метки из М' до А равнялось 0.

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

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

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

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

Определение 3. Аксиомами (правилами) разметки называется набор эффективно вычислимых предикатов П = {Я1.....лк}:

л,:С1хМ' ->{0,1}.

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

Метка ¡л е М\ называется допустимой для окрестности ОеС1, если выполнено равенство П(0, р) = 1. Частичная разметка р? конфигурации З1* называется допустимой, если выполнено равенство П{8'' ,/2^ = 1.

Система аксиом называется покрывающей, если для каждой окрестности существует допустимая в смысле этой системы аксиом метка: У О е СВ/.1,, еМ':П(0,//„)=1.

Подходящим называется алгоритм разметки А, для которого верно П(0,Л(0)) = 1,У0еП.

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

9

*

П = р|л'(,П:Г2хЛ/' —»{0,1}.

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

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

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

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

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

VOбОЗЛ„ :П"(О) = R0,R0eR.

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

l^c^aFy+r.+r^R^zR,

где 7 = sup р(0„0.),П4=(0еП|пЛ(0) = лЛ-

О.еЦ.Г 4 1 '

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

/(c,,c-,) + r, + rl<arIJ\fRt,RJ^R, 10

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

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

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

Множеством окрестностей Ои набора прецедентов Н в смысле системы окрестностей О называется множество окрестностей всех точек всех конфигураций набора Н. Множеством размеченных окрестностей О"н набора прецедентов называется множество: <УН = |(0,//)|0еОн,/ле А/}.

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

Корректным называется алгоритм разметки А, который удовлетворяет следующему условию: Л(0) = е .

Определение 5. Алгоритм разметки А называется а-€1-Н-локапьным тогда и только тогда, когда для любых окрестностей О1 и О2 выполнено условие:

1(А{0,),А(02))1ар(0>,02).

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

Определение 6. Задача 2 называется а-0,-локально разрешимой, если и только если для нее существует подходящий корректный а-П-//-локальный алгоритм А.

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

всякой окрестности О из О. Теорема 2. Определения б и! эквивалентны.

Определение 8. Набор прецедентов Н называется а-Г1-локально противоречивым, если для всех г выполнено П , ) = 1, но существуют (01,/ц),(02,^)б0^ такие, что /(ць ц2) > ар(Оь 02).

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

Теорема 4. а-О-локально разрешимая задача 2 является а-О-локально регулярной тогда и только тогда, когда для произвольных Ох,Ог е<9„ из правил разметки вытекает выполнение условия:

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

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

Рассматривается задача синтеза алгоритмов, реализующих отображения из пространства начальных информации 3, в пространство финальных информации 3,. Предполагается, что на пространстве 3, определена метрика рп а на пространстве задана метрика рГ Структурным параметром задачи является масштабирующая константа а, устанавливающая соответствие между

метриками. Решение ищется в рамках модели алгоритмов Ш, где

Конструкции алгебраического подхода к проблеме синтеза корректных алгоритмов основаны на использовании "промежуточного" по отношению к 3, и пространства оценок Зе. При этом корректные алгоритмы синтезируются на базе эвристических информационных моделей, т.е. параметрических семейств отображений из 3, в 3/, представляющих собой специальные суперпозиции алгоритмических операторов (отображений из 3, в Зе) и решающих правил (отображений из 3£ в , где р — арность решающего правила). Пространства начальных и финальных информации определяются проблемной областью и далеко не всегда удобны для непосредственной работы с ними. В то же время пространство оценок может быть выбрано из некоторых произвольных соображений: в зависимости от вида алгоритмических операторов, желаемого семейства корректирующих операций и др. Введение пространства оценок позволяет в дальнейшем определить понятие корректирующих операций на основе операций над пространством оценок.

В диссертации исследуются алгоритмы, осуществляющие локальное отображение:

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

и 5 = {3"'|Ле/.}, где ЩА) и I — множества структурных индексов. В этом случае модель ШТ строится в виде

ял = и 11 эл'^К»).

Ле/. ШУ(Л)

где при всех X б Ь и со б IV(Я) выполнено равенство

.....)) е ал1, д,..., е ал0}.

Для формализации понятия теоретико-множественных ограничений вводится набор П = {л'1,...,,т<.} предикатов я,: 3, х Зх -» {0,1}.

Для — произвольного элемента пространства 3, вводится

11(7'') = !^ |/7 е Зу,— множество всех допустимых ответов корректных алгоритмов для начальной информации /".

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

Набор П называется покрывающим, если для любого /, из 3, выполнено условие П(/,)*0. Набор П называется непрерывно покрывающим, если для любого /, из 3, выполнено условие

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

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

Для произвольного множества 3 и деМ символом (3") обозначается

множество наборов длины q попарно различных элементов 3. Определение 10. Модель ЯЛ называется П-полной, если выполнены условия:

У/,:ОТ(/,)={л(/,) |ЛеОЯ}с (1)

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

V/, : от(/,)={л(/,)|л 6 от} = R(If). (1 ■)

Цель данного и следующего разделов — описание условий, которым должны удовлетворять семейства ОТ', S и ОТ", чтобы в совокупности обеспечивать полноту модели m = U (J ая'о^^ОТ^).

M. ае» (Я)

Определение 11. Семейство решающих правил ОТ' называется П-полный, если существуют модель алгоритмических операторов ОТ" и семейство корректирующих операций £ такие, что модель OT = (J (J

является П-полной.

Определение 12. При фиксированном П-полном семействе решающих правил ОТ1 семейство корректирующих операций J называется ОТ' -ïl-полньш, если существуют модель алгоритмических операторов ОТ" такая, что модель OT = U (J ОТ1 является П-полной.

>Л1 теВ'(Д)

Определение 13. При фиксированном П-полном семействе решающих правил ffll1 и ОТ' -П-полном семействе корректирующих операций 5 > модель алгоритмических операторов ОТ" называется 5-ОТ'-П-полной, если модель OT = (J (J ОТ'=5л(ОТд 0)) является П-полной.

ЛеЛ «)61Г(Я)

В разделе 2.2 описываются условия, которым должны удовлетворять семейства ОТ1, У и ОТ", чтобы в совокупности обеспечивать полноту модели

OT = U U ЯЛ'°5Д(ОТ°,0).

;.€/. (0€lV{A)

со

Рассматривается непустое семейство решающих правил OT' = [jOT),, где при

любом неотрицательном целом р выполняется Ш'р с |с | С : }, т.е.

множество ОТ), составляют р-арные решающие правила из ОТ1. При этом для любого Л- с Зс оказывается, естественно, выполненным условие:

^ч*)=Скм=йи и ФУ

р-о r-ocvm'r*eX'

Определение 14. Для произвольного /, из 3, множеством ар{ш\1^ называется пересечение в р-ой декартовой степени пространства оценок 3, всех полных прообразов множества Л(/() относительно решающих правил арности р\

сеал; I '

Определение 15. Для семейства Ш]п и элемента /, пространства 3, подмножество Х(1,) пространства оценок Зе называется допустимой р-проекцией, если выполнены условия:

х{1,у I), -зг с з,: (х (/,) с г) а [г" с «„ (т', /()).

Множество всех допустимых р-проекций для семейства ОТ1 и элемента /, обозначается ^ДйЛ1,/,). Для произвольного /, из 3, вводится множество ф(Ш1\/,) функций выбора допустимых проекций:

*{(т\*0) ^ОО^Дап',/,)))},

где 5(3,) —множество всех подмножеств 3,.

Для каждой функции выбора допустимых проекций ф из Ф(ЯЯ',/,) вводятся следующие обозначения:

х{1„ф)=[\ф(р), ф(ж\1) = {ф\ф*ф{т\1),х(1пф)*0).

р. о

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

и ЯП ■(*(/,,*)) = *(/,).

«е ф(®1'.1,)

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

Определение 16. Система подмножеств 0(11) = {х(1„у)[х(11,у)с311,уег(11)} называется ГОТ' -полной для 7/( если выполнены следующие условия:

и эл'те.г)) = *(/,).

Пусть множество составляют р-арные корректирующие операции из 5я. где г = {гя|Аб1}.Тогда =

г-0

Определение 17. Для произвольных X из Ь, I, из 3, и произвольной функции выбора допустимых проекций ф из Ф(9Л',/,) множеством /}* (1пф) называется пересечение в р-ой декартовой степени пространства оценок Зс всех полных прообразов множества Х(11гф) относительно корректирующих операций из :

Определение 18. Для произвольных >* из Ь, /,■ из 3, и произвольной ф из ф(ЯЛ',/,) подмножество У(1,,ф,Х) пространства оценок Зс называется З^-ЗЛ'-допустимойр-проекцией, если выполнены условия:

Множество всех 5'1-ОТ1 -допустимыхр-проекций для ЛеЬ и /, е3, и функции выбора допустимых проекций ф из Ф(ЗЛ',/() обозначается как Ср(/,,ф,1)■ Для произвольных Д е£ и /, е3, и функции ф из ф(2Л',/,) множество *¥(1,,ф,Х) функций выбора и-1' -ОТ' -допустимых р-проекций задаётся как:

Хр:[№=0) =>И/>) = 3.))л

Для каждой функции выбора - ОТ' -допустимых р-проекций у/ из множества ^(/,,(¿,/1) вводятся обозначения:

,7-0

Теорема 6. Для ЯЛ1 -П-полноты семейства корректирующих операций необходимо и достаточно, чтобы V/, е. 3, существовала ОТ1 -полная для 1, система подмножеств С(/,) = {Л'(/,,/)|^(/.,/)с Зг,у еГ(/)} такая, что для любого у из Г(/() существует Л в Ь такое, что

и Г{г{1пф,Л,у)) = Х{1„ф).

Далее считается, что зафиксировано произвольное ЯП1 -П-полное семейство корректирующих операций 5 =

{5я\ЛеЬ].

Определение 19. Пусть зафиксирована ЯЛ' -полная система подмножеств = X(/,,/)с 3,,/еГ(/,)}. Система подмножеств

Н (/„ б) = {Г (/,, у Д, | К {I,, У, Л, <?) е 3„, у е Г (/,), 8 е Д (/,, 6')} называется З'-ЯЯ1-полной для /,, если выполнены следующие условия:

V 84 Л 3 ф 3 1//:У(/,у,Л,8)сГ(/„ф,Л,р),

Теорема 7. Для % -Ш' -П-полноты модели алгоритмических операторов 9Я" = ¡Я е /.,« е необходимо и достаточно, чтобы V/, е 3, было

выполнено условие:

У Л V а 3 ф 3 ^: ОТ" (/,)<= ^С^Д,^)

и чтобы существовала ЯЯ1 -полная система подмножеств = и З-Ш'-полная система подмножеств

Я(/„0) = {к(/„гД,<У)|1'(/„гД.^)еЗ.,уеГ(/(),геД(/„с:)} такие, что V уЭЛ V 8 3 (Л.

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

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

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

Полученные в ходе вычислительных экспериментов практические результаты

подтверждают теоретические результаты, которые были получены в

предыдущих главах.

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

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

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

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

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

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

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

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

3. Дорофеев Н.Ю. Разрешимость и регулярность задач нечёткой разметки

точечных конфигураций // Доклады 14-й Всероссийской конференции

20

«Математические Методы Распознавания Образов (ММРО-14)». Изд.: Москва, МАКС Пресс, 2009. С. 29-32

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-84

6. Дорофеев Н.Ю. Критерии полноты моделей алгоритмов нечёткой разметки точечных конфигураций // Доклады 8-й Международной конференции «Интеллектуализация Обработки Информации (ИОИ-2010)». Изд.: Москва, МАКС Пресс, 2010. С. 35-38

7. Дорофеев Н.Ю. О свойствах задач и алгоритмов нечёткой разметки элементов точечных конфигураций // Сборник тезисов XIX Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2012», секция Вычислительная Математика и Кибернетика. Изд.: Москва, Издательский отдел факультета ВМК МГУ, 2012. С. 92-93

8. Дорофеев Н.Ю. Критерии полноты алгоритмов нечёткой разметки точечных конфигураций // Журнал вычислительной математики и математической физики. Изд.: МАИК "Наука/Интерпериодика", 2012. Т. 52. № 8. С. 15511568.

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

Напечатано с готового оригинал-макета

Подписано в печать 11.02.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 033.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Введение

1 Формализация, разрешимость и регулярность задач разметки точечных конфигураций

1.1 Окрестности, разметки, метрики.

1.2 Аксиомы разметки.

1.3 Разрешимость и регулярность.

2 Вопросы полноты

2.1 Полнота семейств и моделей алгоритмов

2.2 Критерии полноты.

3 Программный стенд 51 Заключение 66 Список иллюстраций 68 Список литературы

Настоящая работа выполнена в рамках алгебраического подхода к проблеме синтеза алгоритмов распознавания. Основные идеи и конструкции алгебраического подхода были сформулированы академиком РАН Ю. И. Журавлёвым в конце 70-х годов прошлого века [12-15] и в последствии развивались его учениками. К тому времени накопилась существенная потребность решения задач обработки информации, которые возникали в различных плохо формализованных областях, для которых, как правило, отсутствовали удовлетворительные математические модели. Примерами таких задач могут послужить задачи анализа социально-демографических и экономических временных рядов, геологической разведки, оценки привлекательности заёмщиков при выдаче кредитов и многие другие.

Идея, послужившая отправной точкой для формирования алгебраического подхода заключается в следующем: в случае, когда отсутствует как адекватная математическая модель, описывающая исследуемую ситуацию, так и модель того, как схожие задачи решает человек, можно строить алгоритмы, осуществляющие требуемое преобразование информации, исходя из имеющихся эмпирических данных и соображений здравого смысла. Чаще всего в таких задачах математическая модель заменялась прецедентной информацией — множеством пар вида «входная информация — ответ». Постепенное накопление примеров удачно решённых прикладных задач послужило практическим доказательством того, что решение плохо формализованных задач, для которых отсутствуют адекватные математические модели реальных процессов, возможно на основе ряда общих информационных принципов. С накоплением алгоритмов решения различных практических задач стало заметно, что различные задачи решают алгоритмы, устроенные сходным образом. Это наблюдение позволило постепенно перейти от принципа «прикладная задача — алгоритм-решение», к принципу «семейство алгоритмов — прикладная задача»: возникли достаточно общие параметрические семейства алгоритмов, называемые моделями алгоритмов распознавания, а решение практических задач сводилось к выбору параметров, которые выделяли из этих параметрических семейств алгоритмы, решающие конкретную задачу оптимальным образом. Эти модели, обычно, возникают в результате формализации некоторых интуитивных представлений о том, как устроены зависимости между входными и выходными данными в задаче, поэтому их ещё называют эвристическими информационными моделями. Решение задач распознавания на основе параметрических семейств получило ряд обоснований, в основе которых лежало принятие различных гипотез метрического, статистического и комбинаторного характера [2,3,19,20,24-26,33]. Работы в первом направлении проводились непосредственно Ю. И. Журавлёвым и его последователями, в то время как исследования второго типа осуществлялись академиком РАН В. Л. Матросовым [27-32]. Третье направление развивает д.ф.-м.н. К. В. Воронцов [4-7].

Однако использование фиксированных параметрических семейств алгоритмов несло в себе некоторое противоречие. С одной стороны для поиска решения следовало выбрать по возможности наиболее «богатое» семейство, так как оно с большей вероятностью содержит алгоритм, дающий наилучший результат. С другой стороны «богатые» семейства обычно достаточно сложно устроены, что приводит к возникновению сложных, а порой неразрешимых, оптимизационных задач и необходимости довольствоваться приближёнными методами. При этом локальный экстремум, найденный в рамках «богатого» семейства, может оказаться хуже, чем глобальный оптимум, найденный в более «бедном», но зато просто устроенном семействе. Основной приём алгебраического подхода, направленный на разрешение этого противоречия, состоит в том, что из эвристических семейств некоторым образом выбираются алгоритмы, использующиеся в качестве базовых операторов, а оптимальный алгоритм-решение для конкретной задачи строится путём применения к ним подходящих корректирующих операций над алгоритмами исходного семейства [1,12-14]. При применении корректирующих операций реализуется естественная идея совместно использовать различные эвристические алгоритмы с целью компенсировать недостатки одних за счёт других. Одним из наиболее распространённых подходов к заданию корректирующих операций, является определение их как операций над пространством ответов исходных эвристических алгоритмов. Однако, вид и структура пространства возможных ответов алгоритмов (финальных информации) задаются из содержательных требований к виду допустимых ответов и потому оно далеко не всегда является удобным для задания на нём корректирующих операций. В связи с этим ещё одним важным приёмом алгебраического подхода стало введение промежуточного по отношению к пространствам начальных информации (входные данные) и финальных информации (ответов) пространства оценок. Алгоритмы при этом строятся в виде суперпозиций алгоритмических операторов, осуществляющих отображение входных данных в пространство оценок, и решающих правил, дающих ответ, на основании полученных оценок. Корректирующие операции, в свою очередь, применяются к оценкам, полученным с помощью алгоритмических операторов. Использование описанных приёмов позволило перейти от принципа «семейство алгоритмов — прикладная задача» к принципу «прикладная область — модель алгоритмов».

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

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

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

Основным объектом исследования в данной работе являются конечные плоские конфигурации (КПК) — конечные множества точек на плоскости в заданной системе координат. Это может быть множество объектов, представленных в виде точек на плоскости, или, скажем, временной ряд. Примеры конечных точечных конфигураций можно увидеть на рисунках, приведённых ниже. . ■ . ■ * ■ .

20 40 60 80

2800 2700 2600 2500 2400 2300 2200 2100 2000 1ЭОО

1945 1950 1955 1960

Рис. 1. Пример КПК: множество точек на Рис. 2. Пример КПК: временной ряд. плоскости.

Наиболее распространённым примером КПК может служить временной ряд. Временной ряд это последовательность значений, обычно измеренных через равные последовательные промежутки времени. Примеры временных рядов встречаются повсеместно: финансовые индексы, показания различных датчиков в динамических системах, акустические сигналы и многое другое. Задача анализа временных рядов возникла достаточно давно и хорошо исследована [48]. Одним из частых промежуточных шагов в процессе исследования временного ряда является выделение внутри ряда так называемых трендов. Строгого определения тренда не существует, но обычно под трендом подразумевается участок временного ряда или аппроксимирующей его кривой, который не содержит экстремумов. В работах члена-корреспондента РАН К. В. Рудакова и к.ф.-м.н. Ю. В. Чеховича [40, 41, 45, 46] задача выделения трендов была сведена к задаче классификации точек в плоских точечных конфигурациях. Это позволило использовать хорошо исследованные методы распознавания и классификации, развивавшиеся школой Ю. И. Журавлёва. К задаче разметки точек в КПК как к задаче с теоретико-множественными ограничения нельзя было непосредственно применить теорию универсальных и локальных ограничений, разработанную К. В. Рудаковым. Поэтому в рамках работ [42-44] была разработана специализация этой теории, предназначенная для решения задач с теоретико-множественными ограничения, частным случаем которых являются задачи выделения трендов. Были получены критерии разрешимости и регулярности этих задач, а также критерии полноты моделей алгоритмов выделения трендов. Теоретическое и экспериментальное исследование конкретных примеров моделей, решающих поставленную задачу, было проведено в работах к.ф.-м.н. В. В. Сарапаса [51]. В дальнейшем теоретические результаты, полученные Ю.В. Чеховичем и К. В. Рудаковым были успешно применены в работах к.ф.-м.н. Д. С. Коваленко [21-23] для решения задачи синтеза обучаемых алгоритмов распознавания нештатного поведения динамических систем. Построенные семейства алгоритмов характеризовались высокой устойчивостью к искажениям фазовых траекторий нештатных режимов работы по сравнению с известными аналогами.

Следует отметить, что полученные в работах [40-46] критерии опирались на понятия сдвиг-эквивалентности конфигураций и сдвиг-эквивалентности окрестностей, в которых конфигурации и окрестности считались эквивалентными, если они совпадали с точностью до сдвига. Неразрешимыми в этом случае считались задачи, в которых эквивалентным конфигурациям и окрестностям соответствовали различные разметки.

2800

2700 - , •

• 8 .

2600 - * » • •

2500 - •

2400

2300

2200 • * 8

2100

2000

1900'-'-1-1-1

1940 1945 1950 1955 1960

Рис. 3. Зашумлённая конфигурация.

Особенностью использования отношения сдвиг-эквивалентности является высокая чувствительность к изменениям конфигураций. Так, даже незначительные изменениях одной из сдвиг-эквивалентных конфигураций, например, как следствие шумов в данных, приводит к потере сдвиг-эквивалентности. Конфигурация, представленная на рис. 3 была получена из конфигурации, которая была приведена ранее на рис. 2, в результате измерения значений в восьмой, двенадцатой и шестнадцатой точках конфигурации с погрешностью (исходные значения обозначены красными выколотыми точками).

Эксперт, скорее всего, заметит, что эти конфигурации идентичны, но с точки зрения отношения сдвиг-эквивалентности эти конфигурации различаются, а следовательно, могут иметь сколь угодно разные разметки.

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

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

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

Первая часть работы посвящена формализации предметной области с учётом дополнительных требований, налагаемых на алгоритмы разметки. В этой же части получены и доказаны критерии разрешимости и регулярности описанных задач [8,9,11].

Вторая часть работы посвящена исследованию вопросов полноты моделей алгоритмов выделения трендов. В ней получены критерии полноты как для моделей алгоритмов в целом, так и для семейств алгоритмических операторов, семейств корректирующих операций и решающих правил по отдельности (при соблюдении определённых условий на остальные части суперпозиции) [10,11,49].

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

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

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

Заключение

Важным направлением дальнейшего развития алгебраического иод-хода является создание проблемно-ориентированных теорий, которые позволят применять результаты алгебраического подхода в конкретных практических областях. В работах Ю. В. Чеховича и К. В. Рудакова была создана такая теория для задач разметки конечных точечных конфигураций, которые рассматривались как задачи с теоретико-множественными ограничениями. К задачам разметки КПК могут быть сведены такие практические задачи, как задача выделения трендов, задача поиска паттернов во временных рядах и др. В работе исследуется расширение теории, созданной в [40,41,45,46], основанное на переходе от дискретного словаря к непрерывному пространству разметки и введении согласованных метрик на пространствах начальных и финальных информаций, что позволяет применить полученные результаты к существенно более широкому кругу практических задач.

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

В последующих главах было описано расширение исходно рассматривавшейся задачи разметки точечных конфигураций, как задачи с теоретико-множественными ограничениями. Были исследованы вопросы полноты семейств алгоритмов разметки точечных конфигураций при замене дискретного пространства финальных информаций на непрерывное. В результате были получены соответствующие критерии полноты: П-полноты семейств решающих правил, ЗЯ1-П-полноты семейств корректирующих операций и 5г-9Я1-П-полноты моделей алгоритмических операторов.

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

1. Айзенберг Н. Н., Журавлев Ю. И., Пилюгин С. В. Применение свер-точных алгебр для построения корректных распознающих алгоритмов // ЖВМиМФ. —1987. — Т. 27, №6.-С.912-923.

2. ВапникВ.Н., Червоненкис А. Я. Теория распознавания образов.— М.: Наука, 1974.-418 С.

3. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.-448 С.

4. Воронцов К. В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // ЖВМиМФ. 2000. - Т. 40, № 1. - С. 166-176.

5. Воронцов К. В. Комбинаторные обоснования обучаемых алгоритмов // ЖВМиМФ.-2004.-Т.44, №11.-0.2099-2112.

6. Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О. Б. Лупанов —М.: Физматлит, 2004.-Т. 13.-С.5-36.

7. Воронцов К. В. Точные оценки вероятности переобучения // ДАН. — 2009. Т. 429, №1.-С. 15-18.

8. Дорофеев Н. Ю. Разрешимость и регулярность задач нечёткой разметки точечных конфигураций // Математические методы распознавания образов: Тез. докл. 14-й Всероссийской конф. — Суздаль, 2009.-С. 29-32.

9. Дорофеев Н. Ю. Критерии полноты моделей алгоритмов нечёткой разметки точечных конфигураций // Интеллектуализация обработки информации (ИОИ-2010): Тез. докл. 8-й Междунрародной конф. — Республика Кипр, г. Пафос, 2010. — С. 35-38.

10. Дорофеев Н. Ю. Критерии полноты алгоритмов нечёткой разметки точечных конфигураций // ЖВМиМФ. — 2012. — Т. 52, №8.— С. 1551-1568.

11. Дорофеев Н. Ю. О свойствах задач и алгоритмов разметки элементов точечных конфигураций // Интеллектуализация обработки информации (ИОИ-2012): Тез. докл. 9-й Междунрародной конф. — Черногория, г. Будва, 2012. — С. 63-66.

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

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

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

15. Журавлёв Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации // Проблемы кибернетики. — 1978. — Т.33-С. 5-68.

16. Журавлёв Ю.И. Локальные алгоритмы вычисления информации. Часть I // Кибернетика —1965 г. — № 1. — С. 12-19.

17. Журавлёв Ю. И. Локальные алгоритмы вычисления информации. Часть II // Кибернетика-1966 г. — №2. — С. 1-11.

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

19. Зуев А. Ю. Вероятностная модель комитета классификаторов // ЖВМиМФ. -1986. Т. 26, № 2. - С. 276-292.

20. Зуев А. Ю. О статистических свойствах принятия решений большинством голосов в задачах классификации // ДАН СССР. — 1986. — Т.288, №2.-С.320-322.

21. Коваленко Д. С., Костенко В. А., Васин Е. А. Исследование применимости алгебраического подхода к анализу временных рядов // Методы и средства обработки информации. — Изд. факультета ВМиК МГУ, 2005.-С.553-559.

22. Коваленко Д. С. Метод автоматического построения алгоритмов распознавания участков фазовых траекторий // Моделирование и анализ информационных систем. — 2009. — Т. 16, № 4. — С. 6-21.

23. Кочетков Д. В. Распознающие алгоритмы, инвариантные относительно преобразований пространства признаков. Часть I // Распознавание, классификация, прогноз. —М.: Наука, 1989. — С. 82-113.

24. Кочетков Д. В. Распознающие алгоритмы, инвариантные относительно преобразований пространства признаков. Часть II // Распознавание, классификация, прогноз. — М.: Наука, 1989. — С. 178-206.

25. Кукулиев Б. М., Матросов В. Л. Оценка прогнозирующей способности решения задачи обучения распознаванию образов // Математические методы распознавания образов: Тез. докл. Всесоюзн. конф. — Рига: МИПКР-РиС при СМ ЛатвССР, 1989. С. 43-45.

26. Матросов В. Л. Корректные алгебры ограниченной ёмкости над множествами некорректных алгоритмов // ДАН СССР. —1980.— Т. 253, №1, —С. 25-30.

27. Матросов В. Л. О критериях полноты модели алгоритмов вычисления оценок и её алгебраических замыканий // ДАН СССР. —1981. — Т. 258, №4.-С. 791-796.

28. Матросов В. Л. Оптимальные алгоритмы в алгебраических замыканиях операторов вычисления оценок // ДАН СССР. — 1982.—Т. 262, №4. -С. 818-822.

29. Матросов В. Л. Емкость алгебраических расширений модели алгоритмов вычисления оценок // ЖВМиМФ. —1984. — Т. 24, №11.— С. 1719-1730.

30. Матросов В. Л. Нижние границы ёмкости многомерных алгебр алгоритмов вычисления оценок // ЖВМиМФ. —1984.—Т.24, №12.— С.1881-1892.

31. Матросов В. Л. Ёмкость алгоритмических многочленов над множеством алгоритмов вычисления оценок // ЖВМиМФ. — 1985.—Т. 25, №1.- С. 122-133.

32. Рудаков К. В. О числе гиперплоскостей, разделяющих конечные множества в эвклидовом пространстве // ДАН СССР.— 1976.— Т.231, №6.-С. 1296-1299.

33. Рудаков К. В. О симметрических и функциональных ограничениях для алгоритмов классификации // ДАН СССР. —1987.—Т.297, № 1. — С. 43-46.

34. Рудаков К. В. Универсальные и локальные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. -1987. № 2. - С. 30-35.

35. Рудаков К. В. Полнота и универсальные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. -1987. № 3. - С. 106-109.

36. Рудаков К. В. О некоторых универсальных ограничениях для алгоритмов классификации // ЖВМиМФ. — 1988. — Т. 26, №11.— С. 1719-1729.

37. Рудаков К. В. О применении универсальных ограничений при исследовании алгоритмов классификации // Кибернетика. — 1988. — № 1. — С. 1-5.

38. Рудаков К. В. Об алгебраической коррекции процедур обработки (преобразования) информации // Распознавание, классификация, прогноз. М.: Наука, 1989. - С. 176-201.

39. Рудаков К. В., Чехович Ю. В. О проблеме синтеза обучаемых алгоритмов выделения трендов (алгебраический подход) // Прикладная математика и информатика. — 2001. — № 8. — С. 97-113.

40. Рудаков К. В., Чехович Ю. В. Алгебраический подход к проблеме синтеза обучаемых алгоритмов выделения трендов // ДАН. — 2003. — Т. 388, №1,-С. 33-36.

41. Рудаков К. В., Чехович Ю. В. Критерии полноты моделей алгоритмов и семейств решающих правил для задач классификации с теоретико-множественными ограничениями // ДАН. — 2004. — Т. 394, №4.-С.459-461.

42. Рудаков К. В., Чехович Ю. В. Критерии полноты семейств корректирующих операций и моделей алгоритмических операторов для задач классификации с теоретико-множественными ограничениями // ДАН. 2004. - Т. 395, № 6. - С. 749-750.

43. Рудаков К. В., Чехович Ю. В. Критерии полноты для задач классификации с теоретико-множественными ограничениями // ЖВ-МиМФ. 2005. - Т. 45, № 2. - С. 344-353.

44. Чехович Ю. В. Об обучаемых алгоритмах выделения трендов // Искусственный интеллект (научно-теоретический журнал HAH Украины). 2002. - № 2. - С. 298-305.

45. Чехович Ю.В. Мощности окрестностей в задачах выделения трендов // Математические методы распознавания образов: Тез. докл. 11-й Всероссийской конф. — Пущино, 2003. — С. 215-216.

46. Berndt D., Clifford J. Using dynamic time warping to find patterns in time series // AAAI Workshop on Knowledge Discovery in Databases. — 1994.-pp. 229-248.

47. BoxG., Jenkins G. Time series analysis: forecasting and control — Holden-Day, 1976.

48. Doropheev N. Yu. The Criteria for Completeness of Algorithms of Fuzzy Marking of Point Configurations // Pattern Recognition and Image Analysis. 2010. - Vol. 20, № 4. - pp. 419-426.

49. SakoeH., ChibaS. Dynamic programming algorithm optimization for spoken word recognition // Transactions on acoustics, speech, and signal processing. -1978. Vol. 26, № 1. - pp. 43-49.

50. Sarapas V. V. Experimental study of synthesis methods of algorithms of trends allocation // Pattern Recognition and Image Analysis.— 2010. — Vol.20, №2.-pp. 145-151.

51. Wang K., Gasser Th. Allignment of curves by dynamic time warping // The annals of statistics. —1997. — Vol. 25, №3. — pp. 1251-1276.