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

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

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

Введение

§0. Обозначения

Глава 1. Описание алгебраических замыканий обобщённой модели алгоритмов вычисления оценок

§1.1. Модель алгоритмов вычисления оценок (АВО)

§1.2. Алгебра над алгоритмами

§1.3. Системы эквивалентностей

§1.4. Операции внешнего и покоординатного произведений

§ 1.5. Матрицы оценок операторов из алгебраических замыканий

Глава 2. Критерии корректности и разрешимости

§2.1. Характеристические матрицы систем эквивалентностей

§2.2. Метрики систем эквивалентностей

§2.3. Обобщённые характеристические матрицы и метрики систем эквивалентностей

§2.4. Описание корректных полиномов

§2.5. Характеристические матрицы в задачах распознавания с двумя классами

Глава 3. Оценки степени корректного алгебраического замыкания

§3.1. Модель АВО с общей функцией близости

§3.2. Неулучшаемая оценка степени корректного алгебраического замыкания

§3.3. Задачи распознавания с непересекающимися классами

§3.4. Модель АВО с системой одноэлементных опорных множеств

§3.5. Исследование некоторых подмоделей

Глава 4. Алгебра над алгоритмами, пополненная операциями нормировки и деления

§4.1. Основные определения. Замыкания относительно операций

§4.2. Нормировка по сумме

§4.3. Нормировка по максимуму

§4.4. Нормировка по отрезку

§4.5. Сравнение различных видов нормировок. Деление матриц распознающих операторов)

Глава 5. Корректность относительно множества решающих правил

§5.1. Решающие правила

§5.2. Общие критерии получения классификации

§5.3. Критерии корректности относительно семейств построчно и постолбцово монотонных решающих правил

§5.4. Корректность в задаче распознавания с непересекающимися классами

§5.5. Сведение задач распознавания

Глава 6. Критерии вырожденности матрицы попарных 1Х -расстояний и их обобщения

§6.1. к -сингулярные системы точек

§6.2. Описание А:-сингулярных систем точек

§6.3. Приложение результатов о &-сингулярных системах к распознаванию

Введение диссертации (часть автореферата) на тему «Алгебраические замыкания обобщённой модели алгоритмов распознавания, основанных на вычислении оценок»

В начале 1970х годов Ю.И. Журавлёвым была описана модель алгоритмов вычисления оценок (АВО) для решения- задач распознавания^ [ЖН71], [ЖКТ74]. Каждый алгоритм модели представлялся в виде суперпозиции распознающего оператора и решающего правила. Распознающий оператор строил матрицу оценок принадлежности контрольных объектов (которые алгоритм должен классифицировать) классам, анализируя схожести подописаний контрольных и эталонных объектов (классификация которых уже известна). Решающее правило на основе этой матрицы оценок классифицировало контрольные объекты. В АВО5были-отражены многие эвристические методы, которые применялись тогда при решении прикладных задач, и модель стала своеобразным универсальным языком описания алгоритмов распознавания [Ж98]. Например, представителями модели были тестовые алгоритмы [ДЖК66], [Яд71] и алгоритмы «Кора» [Бн67], [Вн73], успешно зарекомендовавшие себя на практике.

В конце 1970х годов Ю.И.Журавлёвым был предложен алгебраический, подход к решению • задач распознавания: корректный-алгоритм (который не делает ошибок на контрольный выборке) было предложено искать в виде алгебраического выражения над некорректными (эвристическими) алгоритмами [Ж77а], [Ж776], [Ж77в]. Над распознающими операторами были введены операции сложения, умножения на константу и умножения как операции над их матрицами оценок (умножение проводилось поэлементно). При фиксированном решающем правиле эти операции индуцировали операции над алгоритмами распознавания. Множество алгоритмов, состоящее из всех полиномов степени не выше к над алгоритмами- некоторой^ модели, было* названо алгебраическим замыканием к-й степени этой модели. Множество всех полиномов - алгебраическим замыканием (если ясно из контекста, то

- Задачу распознавания образов по традиции российской научной литературы последних лет называем задачей распознавания (изначально термин «образ» был не совсем корректен РКГ89]). алгебраическим замыканием также называется алгебраическое замыкание конечной степени). Для модели кусочно-линейных решающих поверхностей и АВО было доказано, что существует и в явном виде выписывается корректный алгоритм-полином над некорректными алгоритмами. Отметим, что основное достижение алгебраического подхода — строгое доказательство того, что в теории распознавания возможно построение «хороших» алгоритмов на базе «плохих», устраняя недостатки одного конкретного алгоритма достоинствами остальных. Эту идею используют многие конструкции, в том числе самые современные и практически эффективные: комитеты- [Мз71], [Мз90], бустинг (boosting) [Sc90], [FS95], смешение мнений экспертов (mixtures of experts) [JJ91], усреднение по ансамблю [Н98], модульное обучение (modular learning) [OWS90], области компетентности [РЭ81], нелинейные монотонные корректирующие операции [В98], [BQ0], [РВ99]. Само доказательство было проведено «чисто алгебраическими» методами, что продемонстрировало возможность применения- «классической» математики в . неформализованных областях анализа данных, в которых изначально господствовали лишь эвристические методы и для-каждой новой задачи заново создавался свой алгоритм.

Алгебраический подход к решению1 задач распознавания интенсивно развивался- [ЖР87], [Ж88], [Ж98], [РЧОЗ]. В нём можно выделить отдельную ветвь - теорию локальных и универсальных ограничений К.В'. Рудакова [Р89], [Р92], [Р871], [Р872], [Р873], [Р874], [Р881], которая поставила своей целью создание универсального языка, пригодного для-описания и исследований задач преобразования, информации. В процессе своего развития алгебраический подход приобрёл не только- сторонников, но и противников. В основном, критика алгебраического- подхода фокусирует внимание на «непрактичность теории» и невозможность в явном виде применять корректные алгоритмы-полиномы при решении прикладных задач. B.JI. Матросов показал, что существуют подмодели алгебраических замыканий АВО, которые содержат корректные алгоритмы и «ничем не хуже» большинства современных моделей

- б с точки зрения общепринятой теории надёжности В.Н. Вапника -А.Я.Червоненкиса [ВЧ74], [V98]. К.В. Воронцов предложил методы эффективного использования конструкций алгебраического подхода для решения прикладных задач [В98], [В99], [В00].

Отметим, что все исследования, в основном, были сконцентрированы на оптимизации алгоритмов модели [Рз76], [Рз88], [ЖРС06] и алгебраических выражений над ними [В99]. При этом и сторонниками и противниками алгебраического подхода упускался важный объект исследования; Напомним, что в классических работах [Ж77а], [Ж776], [Ж77в] предложено искать алгоритмы в рамках алгебраических замыканий. Доказано, что там существуют корректные алгоритмы. Доказательства являются^ типичными теоремами существования. Не постулируется, что решать прикладные задачи нужно именно с помощью алгоритмов, построенных в этих доказательствах. Таким образом, предметом исследований могут быть (и должны быть) алгебраические замыкания как таковые, но до настоящего- времени они не были даже достаточно хорошо» описаны. Споры, которые велись вокруг алгебраического подхода (например, по вопросам его практической эффективности) концентрировались вокруг методов.построения алгоритмов, свойств.этих алгоритмов и т.д., но не вокруг алгебраических замыканий. Только имея полное и точное описание алгебраических замыканий, можно анализировать: есть ли в них «хорошие» алгоритмы, как их синтезировать, и т.д.

Технику анализа алгебраических конструкций в рамках классической теории1 удалось построить В.Л. Матросову [М85], [М89]. Изначально она рассматривалась как аппарат для решения задачи о теоретическом обосновании надёжности^ алгоритмических построений^ в алгебраическом подходе [М80], [М81ж], [М82], [М84ж], [М84], [М85ж]'. Наверное поэтому, с её помощью удалось решить лишь несколько, но очень важных проблем, связанных с

- «Классической» здесь называем теорию, которая непосредственно связана с работами [Ж77а], [Ж776], [Ж77в]. В ней исследуется такая же модель АВО и такой же вид алгебраических замыканий. корректностью алгебраических замыканий (возможностью получить операторами замыкания произвольную матрицу оценок в рассматриваемой задаче распознавания1): найти критерии корректности алгебраических замыканий (В.Л: Матросов [М81]), оценку степени корректного алгебраического замыкания (B.JI. Матросов- [М85], Т.В. Плохонина [П87]), примеры задач распознавания, которые не решаются (точно) алгоритмами из алгебраического замыкания конечной степени (В.JI. Матросов [М81], Т.В. Плохонина [П85]). Эти результаты, в определённом смысле, поставили гораздо больше проблем, причём, более сложных: нахождение «наглядных» критериев- корректности, получение пониженных оценок, описание всех задач, разрешимых алгоритмами из алгебраического замыкания конечной степени.

Настоящая работа посвящена исследованию алгебраических замыканий конечных степеней модели АВО. Отметим; что все результаты получены для обобщённой, модели АВО-(и справедливы для стандартной). Основной целью работы было исследование именно классической модели (сохраняя, все традиционные алгебраические конструкции)-. Обобщения вызваны* желанием сделать модель «более современной», адаптировав её'для решения прикладных задач, которые появляются в последнее десятилетие. Первое обобщение модели связано с введением в формулу вычисления' оценок слагаемых, которые учитывают удалённость классифицируемого объекта от объектов рассматриваемого класса и его близость к объектам других классов. Идея, подобного изменения формулы принадлежит Ю.И. Журавлёву и реализована в работе А.А. Докукина [До08] (без исследования специфики новой- модели). Второе обобщение связано с изменением учёта близости между объектами, которая в классическом случае определялась как взвешенная* сумма близостей признаковых подописаний этих объектов [Ж78а]. Модель выписывается для

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

2 Для стандартной модели АВО в работе часто удаётся получить более сильные результаты. произвольного способа задания объектов, в том числе отличного от признакового. Единственное требование - возможность вычислять для любой пары объектов значение функции, которая является аналогом расстояния, но на которую не накладывается никаких существенных ограничений. В задаче может быть задано семейство таких функций (каждая формализует своё понятие «похожести» пары объектов), при этом их значения принадлежат некоторому частично упорядоченному множеству. Ниже перечислим основные результаты, полученные в работе, с кратким историческим обзором предыдущих исследований.

Получение «наглядных» конструкций алгебраического подхода

До настоящего времени не была разработана техника, которая не только предоставляет арсенал методов для анализа алгебраических замыканий модели АВО, но и даёт простую геометрическую интерпретацию алгебраических конструкций. Большинство известных алгоритмов распознавания имеют очень простые и наглядные описания определяемых ими разделяющих поверхностей (в задаче с двумя непересекающимися классами это поверхность в признаковом пространстве, по одну сторону которой лежат объекты, которые алгоритм относит к первому классу, а по другую - ко второму). Например, для линейного классификатора - это гиперплоскость [TF78], для метода ближайшего соседа — последовательность рёбер диаграммы Вороного [ПШ89], для нейросети с несколькими слоями и персептронными элементами — граница полиэдрального множества [Мс]. Алгоритмы алгебраических замыканий конечных степеней до сих пор подобного описания разделяющих поверхностей не имели, несмотря на полученные критерии корректности алгебраических замыканий АВО и разрешимости задач. Критерии [М81], [М85] были изложены в терминах теории систем линейных неравенств G.H. Черникова. [468] и не допускали простой интерпретации в терминах самой задачи распознавания. В. работе получены именно геометрические критерии корректности модели и разрешимости задач алгоритмами модели, описан вид разделяющих поверхностей, в терминах преобразования метрики представлен переход от линейного замыкания к алгебраическому замыканию конечной степени (гл. 2, 6, [Д085] [Д08д] [Д09д]).

Отметим, что параллельно предложена новая техника анализа алгебраических конструкций: техника систем эквивалентностей (гл. 1, 2 [Д08о]). Показано, что матрица оценок оператора алгебраического замыкания конечной степени является' линейной комбинацией характеристических векторов (записанных в матричной форме) классов эквивалентностей некоторой системы эквивалентностей. Элементарно описывается преобразование системы, соответствующее переходу от линейного замыкания модели к алгебраическому произвольной степени, при этом весь анализ во многих случаях может быть проведён лишь для линейного замыкания. Отметим также, что между задачами распознавания и системами эквивалентностей имеется соответствие (гл. 2, 3), которое позволяет весь анализ проводить в терминах систем. Большинство классических результатов, например центральный результат алгебраического подхода о корректности алгебраического замыкания модели АВО в классе регулярных задач, является следствием простых свойств-эквивалентностей (и даже получается в более общем виде, см. гл. 1). Описание всех задач, для,которых некорректно алгебраическое замыкание конечной' степени

После создания B.JI. Матросовым техники описания алгебраических замыканий модели АВО много результатов удалось получить буквально «слёту». Была обоснована некорректность алгебраического замыкания второй степени на множестве всех регулярных задач [М81], затем некорректность алгебраического замыкания произвольной конечной степени [П85]1. Следующая естественная проблема — полное описание класса (регулярных) задач, для которых алгебраическое замыкание фиксированной, степени некорректно.

- Данная публикация имеет неточное название: вместо «конечной степени» в заглавии написано «второй степени», что вводит в заблуждение многих исследователей, см., например, [Ро08]. Отметим, что в [М85] также упоминается некорректность алгебраического замыкания произвольной конечной степени, но строгого доказательства не приводится.

Однако более 20 лет существенных продвижений в решении этой задачи не было. В работе такие классы задач описаны, причём в самом общем случае (см. гл. 6, [Д09д]). Отметим, что параллельно описаны семейства алгоритмов, содержащие корректные алгоритмы минимальной степени (гл. 2). В частности, одно из таких семейств - множество классических полиномов Ю.И. Журавлёва над алгоритмами [Ж776].

Теоретическое обоснование понятия, корректность

В алгебраическом подходе к решению задач распознавания- принято рассматривать модели алгоритмов с фиксированным-решающим правилом. На него накладывают достаточно необременительное требование: корректность решающего правила (сюръективность. реализуемого им отображения), а на множество распознающих операторов — достаточно жёсткое требование: корректность модели (возможность получить произвольную матицу оценок в рассматриваемой задаче распознавания). Единственная цель всех этих ограничений — гарантировать получение произвольной* классификации* контрольных объектов; Так почему же изначально не сделать это определением корректности модели? Этот вопрос не исследовался; и строгих обоснований- традиционно-принимаемых допущений- нет. В работе- исследована корректность относительно семейства решающих правил (гл. 5, [Д05м], [ДОби]). Модель называется корректной относительно семейства (в задаче распознавания), если для любой классификации контрольных объектов существует распознающий оператор модели и решающее правило семейства, суперпозиция которых даёт эту классификацию. Оказалось, что для «естественных» семейств решающих правил понятия корректность и корректность относительно семейства совпадают. На семейства решающих правил, при этом, накладывались лишь незначительные ограничения частичной монотонности. Такая формализация понятия «естественное отображение» принадлежит К.В. Рудакову [Р95],

РВ99]: правила не должны «портить» оценки принадлежности, полученные распознающими операторами1.

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

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

Степень корректных алгоритмов-полиномов, построенных Ю.И. Журавлёвым в [Ж776] асимптотически равнялась qlogq, где q - число контрольных объектов (1977г.). Хотя вопрос оценки'сложности обычно встаёт первым при построении подобного рода конструкций, проблема имеет достаточно долгую* историю. Первая нетривиальная, оценка степени к -корректного алгебраического замыкания модели АВО была получена B.JI. Матросовым: к <q + 1 -2, где / — число классов в задаче распознавания (1985г., [М85]). Отметим, что оценки Ю.И. Журавлёва и B.JL Матросова были получены для модели АВО с одноэлементными опорными множествами (частный случай модели при специальном выборе основного её параметра — системы опорных множеств). Используя разработанную в [М85] технику, Т.В. Плохонина получила оценку к<т, где т - число эталонных объектов (1987г., [П87]). С помощью методов теории категорий К.В. Рудакову удалось получить оценку k<\\og2ql\ (1989г., [Р89]), которая долгое время ошибочно1 считалась

1 Изначально требования монотонности накладывались на корректирующие операции. неулучшаемой для модели АВО (считалось, что для любых натуральных qui существует задача распознавания, в которой некорректно алгебраическое замыкание степени к при l<^<|log2^r/J). Отметим, что в [Р89] исследовался другой тип алгебраических замыканий: вместо «классических» полиномов над распознающими операторами с нулевым свободным членом рассматривались полиномы с ненулевым свободным членом, который интерпретировался как оператор, получающий матрицу оценок с одинаковыми, элементами1. Хотя, как следует из полученных ниже результатов, для модели АВО это не имеет значения. В данной работе впервые более чем за четверть века исследований удалось получить неулучшаемую оценку, зависящую от параметров q и I гл. 3, [Д05с]). Для важных частных случаев получены пониженные неулуч-шаемые оценки (гл. 3, [Д08о]). Пополнение алгебры над алгоритмами

Классическая алгебра над алгоритмами распознавания содержит операции сложения, умножения и умножения на константу. Пополнение этой алгебры новыми операциями или замена умножения другой операцией уже исследовались (см. [Р92]). Однако особого интереса результаты этих исследований не представляли, поскольку эксплуатировали стандартную идею: новая операция, применённая к представителям «хорошего» множества матриц оценок, должна получить базис пространства матриц. «Хорошим» множество считалось, если в нём для любой позиции существует матрица, в которой элемент на этой позиции по модулю больше остальных. До сих пор не были найдены «естественные» операции, которые значительно упрощают критерии корректности, не делая их вырожденными. В работе найдены и исследованы такие операции: нормировки (гл. 4, [Д07], [Д09]). До сих пор также не было исследовано пополнение алгебры над алгоритмами операцией деления. В данной работе показано, что деление является достаточно «мощной»

- Это факт часто не учитывается исследователями. алгебраической операцией (гл. 4, [Д07]). Попутно в работе введено понятие «замыкание в стандартной форме» (когда алгебраические выражения с новой операцией строятся специальным «простым» способом). Почти все замыкания, представленные в работе, достаточно рассматривать в стандартной форме. Например, алгебра алгоритмов с делением эквивалентна замыканию в стандартной форме относительно операции взятия обратной (по Адамару) матрицы1. Связь алгебраических замыканий модели АВО с другими моделями алгоритмов распознавания

В описании модели АВО нашли отражение многие идеи «успешных» методов распознавания XX века. В работе продемонстрирована связь между алгебраическими замыканиями АВО и некоторыми современными моделями алгоритмов распознавания (гл. 2, 6, [Д085]). Например, переход к алгебраическим замыканиям АВО соответствует применению специальных ядер в методе опорных векторов (SVM) [BGV], [Виг]. Эта связь позволяет учитывать достоинства одного метода при настройке другого. Например, при построении классических корректных алгоритмов-полиномов над АВО неявно использовался переход в пространство, в котором есть линейное разделение объектов-, а затем само разделение производилось фиксированной гиперплоскостью. Естественно, такие конструкции непрактичны, переобучены [В04] и служат лишь для доказательств теорем существования. Из результатов, полученных в работе, следует способ синтеза более надёжных алгоритмов, используя идею SVM построения оптимальной (а не какой-нибудь) разделяющей гиперплоскости. Причём её можно строить и при отсутствии линейного разделения объектов, не переходя в • алгебраическое замыкание высокой степени (при этом будет получен, вообще говоря, некорректный алгоритм). С другой стороны, в SVM можно использовать идею АВО работать

- Это, видимо, объясняет, почему алгебра алгоритмов с делением не встречалась в литературе: не было найдено удобной формы для представления результатов.

- Здесь слово «объект» используется в общем смысле (т.е. не обязательно это объект распознавания, см. гл. 2). не в исходном признаковом пространстве (объекты часто вообще задаются не признаковым описанием), а в пространстве значений функций близости1 В алгебраических замыканиях АВО, по сути, используются два ядра: одно -функция близости, второе - полиномиальное (для перехода в соответствующее алгебраическое замыкание). В работе также показана связь линейного замыкания ^ АВО с линейной регрессией и жёсткой интерполяцией (гл. 6), из которой следуют методы настройки алгоритмов'из алгебраических замыканий. Отметим, что эти- методы в работе не излагаются, поскольку выходят за рамки основной тематики. Работа, помимо всего прочего, иллюстрирует то, что в современном распознавании мало принципиально различных методов. Все используют одни и те же идеи, часто «превращаются» друг в друга- при специальном- выборе параметров, имеют схожие геометрические интерпретации. И чем сложнее модель, тем к большему числу других моделей- она» сводится (примером также могут служить нейронные сети, см. [Н98]), естественно, тем актуальнее проблема эффективной- настройки параметров модели. При этом алгебраические замыкания (сложной)' модели АВО достаточно просто описываются.

Нахождение критериев вырожденности матрицы попарных 1Х-расстояний и их обобщений

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

- Отметим, что на похожей идее базируются результаты теории беспризнакового распознавания в гильбертовом пространстве [Ср01].

Матрицы попарных расстояний возникают во многих задачах, связанных с интерполяцией, например с помощью радиальных базисных функций (RBF) [Вх91] или жёстких функций (riddle functions) [RS93]. Один из результатов, полученных И.Шёнбергом в серии работ [S37], [S38], [S38a] о вложении-метрических пространств в гильбертово, - невырожденность таких матриц для конечной системы попарно различных точек пространства R"1 и метрики lp, 1 <р<2, q> 1. Особый интерес представляет случай р = 1, для- которого многие' исследователи пытались найти «геометрический» критерий вырожденности матрицы попарных расстояний1. В' [DLC] показано, что системы точек плоскости R , которые соответствуют вырожденным, матрицам, л должны содержать замкнутые пути- (closed^ paths) — подсистемы вида {(al,bl),(alibl+l)Yl=l, br+x = bx. Прямое обобщение' этого понятия* на случай пространства R'" при произвольном натуральном т даёт только достаточное условие- вырожденности матрицы, см. [L89], [RS93]. Критерий был впервые получен в [RS93] с помощью-техники размеченных прямоугольников (signed rectangles). В» этой работе используется обобщение этого- понятия' — размеченные параллелепипеды. Отметим, что подобные конструкции часто встречаются в теоретических работах по теории интерполяции. Например, введённый в [ВР93] брусок (brick) является проекцией размеченного параллелепипеда на плоскость.

В. работе показано, что задача о невырожденности матрицы попарных ^-расстояний, возникает также при нахождении критериев корректности алгебраических замыканий конечной степени модели АВО (гл. 2; [Д08д]). Более того, интерес представляет задача' о размерности пространства значений

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

- Идея «замкнутого пути» появилась в [DS51] (эта работа, согласно [L89] и [Мд92], содержит неточности). Такая же конструкция под названием «замкнутая молния» использовалась при решении тринадцатой проблемы Гильберта [А57]. всевозможных полиномов степени не выше к от столбцов такой матрицы (с адамаровым умножением). В работе введено понятие А:-сингулярности, формализующее «полноту» пространства таких полиномов. Получены критерии А;-сингулярности (один из критериев является обобщением результата [RS93], при этом предлагается неиндукционный способ доказательства), в том числе новые критерии вырожденности матрицы /, -расстояний (гл. 6, [Д09д]).

Ниже дадим дополнительную характеристику работы.

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

Практическая ценность. Работа носит теоретический характер. Для иллюстрации возможных практических применений в приложении описаны прикладные задачи, при решении которых использовались результаты работы. Задачи были поставлены в рамках Международных соревновании учёных по интеллектуальному анализу данных (data mining).

Публикации. Результаты работы изложены в четырёх сообщениях журнала «Доклады Академии наук» [ДООд], [Д08д], [Д08о], [Д09д], шести статьях «Журнала вычислительной математики- и математической физики» [Д00], [Д05с]; [Д05м], [ДО7], [Д085], [Д09], статье журнала «Искусственный интеллект» [ДОби], обзорной- статье журнала «Таврический вестник информатики и математики» [Д08т], учебном пособии [Д06], трудах конференции [Д06т]> и докладах конференций [ДООт]; [Д05Ь], [ДОбк], [Д07т], [Д08к], [Д08и] (всего 20 публикаций). Описания отдельных результатов работы включались в ежегодные научные отчёты факультета ВМК МГУ, а также в научные отчёты по проектам РФФИ 08-07-00305-а, 08-01-00636-а, 08-01-90016-Бела, 06-01-08045-офи, 05-01-00332-а, 02-01-00558-а, 99-01-00433-а, грантам Президента МК-533.2007.9, МК-1660.2005.9, НШ-5294.2008.1, НШ-5833.2006.1, программам научных исследований Президиума РАН и ОМН РАН.

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

Апробация работы. Основные результаты работы и отдельные её части докладывались на

- научном семинаре кафедры, математических методов прогнозирования факультета ВМК МГУ (2009 г.);

- научном семинаре «Алгебрологические методы в задачах классификации и прогнозирования» (руководитель: Ю.И. Журавлёв, Москва, МГУ, ВМК, 1999 - 2000, 2003 - 2009 г.);

- научном семинаре «Дискретный анализ» (руководители: А.А. Сапоженко, Н.Н.< Кузюрин, Москва, МГУ, ВМК, 2003'г.);

- научном семинаре «Дискретная математика и математическая кибернетика» (руководители: В.Б. Алексеев, А.А. Сапоженко, С.А. Ложкин, Москва, МГУ, ВМК, 2008 г.);

- Ломоносовских чтениях (Москва, МГУ, ВМК, 2008 - 2009 г.);

- Международных научных конференциях «Интеллектуализация обработки информации - 2000, 2006, 2008» (Симферополь, Крымский научный центр НАН Украины, ТНУ, 2000; 2006, 2008 гг.) [ДООт], [ДОбк], [Д08и];

- 7й и 8й Международных конференциях «Дискретные модели в теории управляющих систем» (Москва,- 2006, 2009 гг.) [ДОбт];

- 15й Международной конференции «Проблемы теоретической кибернетики» (Казань, 2008 г.) [Д08к];

- девятнадцатой Крымской осенней математической школе-симпозиуме KROMSH-2008 (Украина, Крым, Ласпи-Батилиман, 2008 г.);

- 12-й и 13-й Всероссийских конференциях «Математические методы распознавания образов» (Москва, 2005, 2007 гг.) [Д05Ь], [Д07т].

Материалы работы легли в основу обязательного кафедрального курса лекций «Алгоритмы, модели, алгебры» для студентов 317 группы ф-та ВМК МГУ и спецкурса «Эффективное представление алгоритмов из алгебраических замыканий» для студентов ф-та ВМК МГУ.

За цикл работ [Д05с], [Д05м], [ДОби], [Д07], [Д085], [Д08д] автору была присуждена Медаль РАН для молодых учёных (постановлением Президиума РАН №59 от 24.02.2009), за цикл работ [ДООд], [ДООт], [Д00] - Медаль РАН для студентов ВУЗов (постановлением Президиума РАН №197 от 6.09.2001). За цикл работ «Алгебра над алгоритмами вычисления оценок» [Д05с], [Д05м], [Д05Ь], [ДОбт], [Д06] был получен грант поддержки талантливых студентов, аспирантов и молодых учёных Московского государственного университета имени М.В. Ломоносова 2006 года. Также во время выполнения работы автор был лауреатом конкурса «Грант Москвы» в области естественных наук (2001 г.), поддержан стипендиями МГУ для молодых преподавателей и учёных, добившихся значительных результатов в преподавательской и научной деятельности (присуждены решениями Ученого Совета МГУ от 24.12.07 и 22.12.08).

Структура работы. Работа состоит из оглавления, введения, нулевого параграфа (с перечнем основных обозначений), шести глав, разбитых на параграфы (всего 28 параграфов), списка литературы (129 наименований), приложения. В списке литературы все публикации перечислены в алфавитном порядке по фамилиям авторов, публикации одного автора (группы авторов) следуют в хронологическом порядке. Публикации автора работы приведены отдельно в конце общего списка. В работе используется тройная нумерация: в номерах теорем, лемм, формул, примеров и рисунков через точку указывается номер главы, номер параграфа и порядковый номер в этом параграфе идентифицируемого объекта. Для удобства номера сносок напечатаны полужирным подчёркнутым шрифтом. В работе утверждение называется леммой не только в случае, если носит технический характер (служит для доказательства других утверждений), но и в случае, если оно носит иллюстративный характер (и не представляет особой теоретической ценности, по сравнению с другими теоремами данной главы). Доказательство теоремы (леммы) заканчивается словами «теорема доказана» («лемма доказана»). Все примеры, кроме 1.1.1 и 2.5.1, занимают ровно один абзац (поэтому не отделяются пустой строкой от основного текста). В приложении дан перечень обозначений, которые вводились по ходу изложения (не в нулевом параграфе), приведены некоторые результаты об эффективной реализации алгоритмов модели АВО на ЭВМ (при каких значениях параметров такая реализация возможна), а также информация о1 прикладных задачах, решённых автором в 2005—2008 гг. Основной текст занимает 258 страниц, приложение занимает 34 страницы.

Автор выражает огромную благодарность своему учителю, Юрию Ивановичу Журавлёву, который оказал значительное влияние на формирование научного мировоззрения автора, а также всем своим коллегам из МГУ и ВЦ РАК

§0. ОБОЗНАЧЕНИЯ

Используем следующие обозначения: 1 = (1,.,1)т - вектор, состоящий из одних единиц; 0 = (0,.,0)т - вектор, состоящий из одних нулей; et = (0,.,0,1,0,.,0)т — бинарный вектор1, /-я координата которого равна единице, а остальные координаты равны нулю; Е — матрица, состоящая из одних единиц (размерность векторов и размеры матриц будут ясны из контекста), I - бинарная матрица размера q х q, у которой только элементы на главной диагонали равны единице. Для вектора а = (al,.,al)r введём также следующие обозначения: а = 1 - a- (\-ax,.,\-aiY, lnd{a) = {iG{l,2,.,l}\ai ^0}, \\а \\=ах + . + «/, через (a)i будем обозначать его i -ю координату ai. Если вектор а является бинарным, то вектор а называется его инверсией (или отрицанием), а число || а || - его нормой. Для конечного множества векторов Х = {х1,.,хг}, \Х\=г все элементы в котором попарно различны), обозначим через mat(X) = [3cj. xr ] матрицу, составленную из всех векторов этого множества (порядок записи вектор-столбцов в матрице не будет играть роли или будет специально оговорен). Для матрицы Н обозначим через row(Н) множество её строк, через col(#) — множество её столбцов. Запись || htJ ||ахй обозначает матрицу hu . hlb К\ ••• Кь

- Бинарным вектором называется вектор, состоящий из нулей и единиц.

- В работе не используются мультимножества, поэтому, например, |/|=2 и ^а, =ах+а2 при I = {1,2,2,1,1}. часто будем указывать размеры матрицы с помощью нижнего индекса: НахЬ — матрица Н размера axb. ХахЬ - множество матриц размера axb с элементами из множества X.

Пусть R — поле (множество) вещественных чисел, Q — поле (множество) рациональных чисел, Z - кольцо (множество) целых чисел. Любой из этих символов с верхним индексом «+» обозначает подмножество всех неотрицательных чисел соответствующего множества, например R+ = [0,+00),

Z+={0,1,2,.}. Большинство результатов, полученных в работе, будет сформулировано с использованием символа Q (для поля рациональных чисел), который может быть заменён символом R (все они справедливы и для поля вещественных чисел), если не оговорено противное. Выражение F(|| hy ||ах6) при некотором преобразовании F: Q -» Q обозначает матрицу || F(hj) \\axb.

Запись {xj/e/ обозначает множество (Jl*,}. Если из. контекста ясно, iel какое множество пробегает индекс i, то это множество не будем указывать-, используя обозначение {х(}г-. Аналогичные обозначения используем, если элементы множества параметризованы набором индексов. При I = {ix,.,ik},

111= к, считаем, что порядок на множестве / не будет важен или будет указан), а также a,-)!=i ••>«/) •

Для любого множества X векторов линейного пространства над полем Q через щ{Х) обозначаем максимальное число линейно независимых векторов в этом множестве. В случае конечного множества X эта величина

- Сам индекс указывается, поскольку {х,} - множество, состоящее из одного элемента xt. совпадает с рангом матрицы mat(X). Для матрицы Н выражение щ{Н) обозначает её ранг, а выражение det(i/) - её определитель.

Далее используем также обозначения: [х] — целая часть числа х снизу (наибольшее целое число, не превосходящее числа х ), [х~] - целая часть числа х сверху (наименьшее целое числом: х < у),

QL = {О', j) I ie {1,2,., q), j е {1,2,., /} },

2Л = {Y | Y <z X} - множество всех подмножеств множества X,

Ckx={Ye 2Х\ | Y\=k}.

Для множеств

15.,^)|1 <tx<.<tk<n}\, \{{tx,.,tk}\\<tx<.<tk<n}\ используем одно обозначение: (это не вызовет путаницы), ск-\ск I-п] число всех сочетаний из п элементов без повторений объёма к (из п по к).

Как принято, системы равенств и неравенств записываем, объединяя все равенства и неравенства, входящие в систему, фигурной скобкой (слева). Таким образом, фигурная скобка обозначает логическое условие «и». По аналогии, логическое условие «или» обозначаем квадратной скобкой, например, запись х = 1 х = 2 эквивалентна записи л; е {1,2}.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Дьяконов, Александр Геннадьевич

ЗАКЛЮЧЕНИЕ

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

Описана обобщённая модель алгоритмов вычисления оценок (АВО) для решения задач распознавания при произвольном способе задания объектов, для-которой получены следующие результаты, (справедливые и для классической модели):

1Л. Предложена теория* систем, эквивалентностей* для описания' И' исследования- алгебраических, замыканий конечных степеней. Каждой задаче распознавания, ставится в соответствие система эквивалентностей; по которой строятся характеристическая матрица и матрица попарных 1\-расстояний. В терминах этих матриц просто описываются алгебраические замыкания модели. Переходу к алгебраическому замыканию фиксированной степени соответствуют специальные преобразования матриц.

2. Получены новые критерии корректности^ алгебраического замыкания конечной степени и критерии разрешимостш задач алгоритмами этого замыкания: Критерии имеют простую геометрическую интерпретацию, позволяют описывать разделяющие поверхности алгоритмов, алгебраических замыканий в пространстве контрольных объектов. Найдены простые семейства корректных полиномов (в частности, доказано, что классические полиномы Ю.И: Журавлёва образуют базис в алгебраическом замыканииконечной степени).

3. Получена1 неулучшаемая* в общем случае оценка степени» корректного алгебраическогозамыкания модели АВО!, Для важных частных случаев получены пониженные оценки: для задачи распознавания с непересекающимися классами, для-.задачи с разнесёнными эталонами и модели

АВО с системой всех одноэлементных опорных множеств, для подмоделей модели АВО (при обнулении параметров учёта близости и антиблизости).

4. Исследовано пополнение новой операцией^ линейного замыкания множества полиномов ограниченной степени^ над АВО. В качестве новой операции рассматривались нормировка (при различных способах её определения: по сумме, максимуму, отрезку) и деление. Во всех случаях получена формула для размерности соответствующего замыкания, найдены критерии корректности. Показано, что многие замыкания* (в том числе при пополнении другими операциями) пред ставимы в стандартной форме (алгебраические выражения» можно строить не используя вложение новых операций).

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

6. Исследована^-сингулярность конечной-системы точек (неполнота размерности пространства значений полиномов ограниченной степени над* столбцами матрицы попарных /i-расстояний этой системы).* Показана связь ^-сингулярности с 1-сингулярностью. Полностью описаны все ^-сингулярные системы (как содержащие подсистемы, специального вида). Найдены новые критерии вырожденности матрицы попарных 1\-расстояний конечной системы точек, в частности связанные с разделимостью её подмножеств гиперплоскостью.

Список литературы диссертационного исследования доктор физико-математических наук Дьяконов, Александр Геннадьевич, 2009 год

1. АБР. Айзерман М.А., Браверманн Э.М., Розоноэр Л.И. Метод потенциальных функций в.теории обучения машин. -М.: Наука, 1970.

2. АЖ85. Алексанян А.А., Журавлёв Ю.И. Об одном подходе к вопросу построения эффективных алгоритмов распознавания // Ж. вычисл. матем. и матем. физ. 1985. - Т.25. - №2. - С.283-291.

3. А57. Арнольд В.И. О функциях трёх переменных // Докл. АН СССР. 1957. — Т. 114. — №4. — С.679-681.

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

5. Вн73. Ванцвайг М.Н. Алгоритм обучению распознаванию образов «Кора» // Алгоритмы обучению распознаванию образов. — М.: Сов: радио, 1973. — С.82-91.

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

7. В 98. Воронцов КВ. О «проблемно-ориентированной оптимизации базисов задач распознавания // Ж. вычисл. матем. и матем. физ. 19981 - Т.38. - №5. -С.870-880.

8. В99. Воронцов КВ. Локальные базисы в алгебраическом подходе к проблеме распознавания: Дис. . канд. физ.-матем. наук / ВЦ РАН. М., 1999. -107 с.

9. В00. Воронцов КВ. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // Ж. вычисл. матем. и матем. физ: — 20001 — Т.40. — №1. — С. 166-176.

10. В04. Воронцов КВ. Обзор современных исследований- по проблеме качества обучения алгоритмов // Таврический вестник информатики и математики. Симф. 2004. - №1. - С.5-24.

11. Вл. Воронцов КВ. Курс лекций «Математические методы обучения по прецедентам»//http://www.ccas.ru/voron/ (на 17.11.08).

12. Гу04. Гуров С.И. Упорядоченные множества и универсальная алгебра (вводный курс): Учебное пособие. — М.: Издательский отдел ф-та ВМиК МГУ, 2004г. 104 с.

13. ДЛ01. ДезаМ.М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001.-736с.дм74. Дискретная математика и математические вопросы кибернетики / Под ред. С.В. Яблонского и О.Б. Лупанова. М.: Наука, 1974. - 312с.

14. ДЖК66. Дмитриев А.Н., Журавлёв Ю.И., Кренделев Ф.П. О математических принципах' классификации предметов и явлений // Дискретный анализ. — Новосибирск: Наука, 1966. Вып.7. - С.3-15.

15. До01. Докукин А.А. О построении в алгебраическом замыкании одного алгоритма распознавания // Ж. вычисл. матем. и матем. физ. — 2001. — Т.41. — № 12.-С. 1873-1877.

16. До08. Докукин А.А. Синтез, полиномов над экстремальными» алгоритмами вычисления' оценок: Дис. . канд. физ.-матем. наук. / ВЦ РАН. — М., 2008.- 102 с.

17. Д11. Дюкова Е.В., Песков Н.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // Ж. вычисл. матем. и матем. физ. 2002. - Т.42. - №5. - С.741-753.

18. Ж76. Журавлёв Ю.И. Непараметрические задачи распознавания образов // Кибернетика. 1976. - №6. - С.93-103.

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

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

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

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

23. Ж88. Журавлёв Ю.И. Об алгебраических методах в . задачах распознавания и классификации // Распознавание, классификация, прогноз. 1988. — Т.1. -С.9-16.

24. Ж98. Журавлёв Ю.И. Избранные научные труды. — М.: «Магистр», 1998. — 420 с.

25. ЖГ89. ЖуравлёвЮ.И., ГуревичИ.Б. Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. Математические методы и их применение. М.: Наука, 1989. — Вып. 2. - С. 5-72.

26. ЖИ79. Журавлёв Ю.И., Исаев ИВ. Построение алгоритмов распознавания,, корректных для заданной контрольной выборки // Ж. вычисл. матем. и матем. физ. 1979. - Т.19. - № 3: - С.726-738.

27. ЖКТ74. ЖуравлёвЮ.И, Каминов М.М., Туляганов Ш.Е. Алгоритмы вычисленияюценок и их применение. «ФАН»,Ташкент, 1974.

28. ЖН71. Журавлёв Ю.И, Никифоров В:В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. — 1971*. №3. - С. 1-11.

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

30. ЖРС06. ЖуравлёвЮ.И, Рязанов В.В., Сенъко О.В «РАСПОЗНАВАНИЕ». Математические методы. Программная система. Практические применения. М.: Фазис, 2006. - 176 с. (ISBN 5-7036-0108-8).

31. ЖФВ06. Журавлёв Ю.И, Флёров Ю.А., Вялый М:Н. Дискретный анализ. Основы высшей алгебры. М.: МЗ Пресс, 2006. — 208 с.

32. Зыков А'.А. Теория конечных графов I. Сибирское отделение. Наука, 1969.-543 с.

33. Зыков А.А. Основы теории графов. -М.: Наука, 1987.

34. ИК98. Ильин В.А., КимГ.Д. Линейная алгебра и аналитическая геометрия: Учебник. -М.: Изд-во Моск. ун-та, 1998. 320 с.

35. Кс77. Кострикин А.И: Введение в алгебру. М.: «Наука», 1977. - 496 с.

36. Крбб. Куратовский К. Топология: В 2 т. -М.: Мир, 1966-1969. Т. 1-2.

37. Мй04. Майсурадзе А.И. Об оптимальных разложениях конечных метрических конфигураций в задачах распознавания образов // Ж. вычисл. матем. и матем. физ. 2004. - Т.44. - №9. - С. 1697-1707.

38. Мз71. Мазуров В:Д. Комитеты системы неравенств и задача распознавания // Кибернетика. 1971. -№ 3. - С. 140-146.

39. Мз90. Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации. -М.: Наука, 1990.

40. Мл97. Малюгин ВД. Параллельные логические вычисления посредством арифметических полиномов. М.: Наука. Физматлит, 1997.

41. ММ04. Маркус М., МинкХ. Обзор по теории матриц и матричных неравенств. М.гЕдиториал УРСС, 2004. - 232 с.

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

43. М81ж. Матросов В.Л. Корректные алгебры ограниченной ёмкости над множеством алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ. 1981.-Т.21.-№5.-С. 1276-1291.

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

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

46. М84ж. Матросов B.JI. Нижние оценки ёмкости многомерных алгебр алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ. —1984. Т.24. - №12. - С. 1881-1892.

47. М84. Матросов B.JI. Ёмкость алгебраических расширений модели алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ. — 1984. — Т.11. — №5. С. 1719—1730.

48. М85ж. Матросов В.Л. Ёмкость полиномиальных расширений множества алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ.1985. Т.25. — №1. - С.122—133.

49. М85. Матросов В.Л. Корректные алгебры алгоритмов1 распознавания ограниченной ёмкости: Дис. . докт. физ.-матем. наук. / Гос. пед. инст-т им. В .И. Ленина. М., 1985. - 220 с.

50. М89. Матросов В.Л. Синтез оптимальных алгоритмов в алгебраических замыканиях моделей алгоритмов распознавания // Распознавание, классификация, прогноз. Математические методы и их применение. — М.: Наука, 1989. Вып. 1. - С. 149-176.

51. Мд92. Медведев В.А. Опровержение одной теоремы Дилиберто и Страуса // Мат. заметки. 1992. - Т. 51. - № 4 - С. 78-80.

52. Мс. Местецкий Л.М. Математические методы распознавания образов. Курс ■ лекций, ВМиК МГУ, кафедра ММП. - 2002. // http://www.ccas.ru/frc/ papers/mestetskii04course.pdf (на 17.11.08).

53. Оре О. Теория графов М.: Наука, 1980. - 336 с.

54. П85. Плохонина Т.В. О некорректности алгебраического замыкания второй степени семейства алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ. 1985.-Т.25.-№7.-С.1073-1086.

55. П87. Плохонина Т.В. Вопросы корректности алгебраических замыканий конечной степени семейства алгоритмов вычисления оценок для регулярных задач // Ж. вычисл. матем. и матем. физ. — 1987. — Т.27. — № 5. — С.763-770.

56. ПШ89. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. — М.: Мир, 1989.

57. Пр70. Проскуряков И.В. Сборник задач по линейной алгебре. М.: Наука, 1970.-384 с.

58. РЭ81. Растригин Л.А., Эренштейн P.X. Коллективные правила распознавания. М.: Энергия, 1981.-244 с.

59. Ри82. РиорданДж. Комбинаторные тождества. — М.: Наука, 1982.

60. Ро08. Романов М.Ю. Построение обобщённых полиномов минимальной степени над алгоритмами вычисления оценок: Дис. . канд. физ.-матем. наук. / ВЦ РАН. М., 2008. - 81 с.

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

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

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

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

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

66. Р89. Рудаков KB: Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. Математические методы и их применение. М.: Наука, 1989. — Вып. 1. - С.176—201.

67. Р92. Рудаков КВ. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания: Дис. . докт. физ.-матем. наук. / ВЦ РАН. М., 1992. - 144 с.I

68. Р95. Рудаков КВ. Монотонные и унимодальные корректирующие операции для алгоритмов распознавания // Математические методы распознавания образов—VII: Тез. Докл. -М.: 1995.

69. РВ99. Рудаков КВ., Воронцов КВ. О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания // Докл. РАН. 1999. - Т.367. - №3. - С.314-317.

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

71. Рз76. Рязанов В.В. Оптимизация алгоритмов вычисления оценок по параметрам, характеризующим представительность эталонных строк // Ж. вычисл. матем. и матем. физ. 1976. - Т. 16. — №6. - С. 1559-1570.

72. Рз88. Рязанов В.В. О построении оптимальных алгоритмов распознавания и таксономии (классификации) при решении прикладных задач // Распознавание, классификация, прогноз. Математические методы и их применение. М.: Наука, 1988. - Вып. 1. - С.229-279.

73. С77. Сачков В.Н. Комбинаторные методы дискретной математики. М.: Наука, 1977. - 320 с.

74. Ср01. Середин О. С. Методы и алгоритмы беспризнакового распознавания образов: Дис. . канд. физ.-матем. наук. / ТулГУ, ВЦ РАН. М., 2001. — 142 с.

75. Т88. Татт У. Теория графов. М.: Мир, 1988. - 424 с.

76. ТГ78. ТуДж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.

77. У77. Уилсон Р. Введение в теорию графов. М.: Мир, 1977. - 208 с.

78. Х63. Халмош П. Конечномерные векторные пространства. М.: Физматгиз, 1963.-264 с.

79. Черников С.Н. Линейные неравенства. М. Наука, 1968. - 488 с.

80. Я01. Яблонский С.В. Введение в дискретную математику: Учебное пособие для вузов. / Под ред. В.А. Садовничего. 3-е изд., стер. - М.: Высш.шк.; 2001.-384 с.

81. As80. AssouadP. Caracte'risations de sous-espaces norme's de L\ de dimension finie // Se'minaire d'Analyse Fonctionnelle. — Ecole Polytechnique Palaiseau, 1979-1980.-№19.

82. Av77. Avis D. Some Polyhedral Cones Related to Metric Spaces: PhD thesis / Stanford University, 1977.

83. Bx91. Baxter B.J.C. Conditionally positive functions and/?-Norm distance matrices // Constr. Approx. 1991. - №7. - Pp.427-440.

84. Bh05. BhatiaR. Infinitely Divisible Matrices // Indian Statistical Institute, Delhi Centre, -http://www.isid.ac.in/~statmath/eprints (на 17.11.08).

85. BGV. Boser В., Guy on I., Vapnik V.N. A training algorithm for optimal margin classifiers // Fifth Annual Workshop on Computational Learning Theory. — San Mateo, С A: Morgan Kauftnann, 1992. Ppi 144-152.

86. BP93. Braess D., Pinkus A. Interpolation by ridge functions // J. Approx. Theory. -V.73. — 1993. Pp.218-236.

87. BG04. Breitenbach M., Grudic G.Z. Clustering with Local and Global Consistency // Technical Report CU-CS-973-04. 2004. - http://www.cs.colorado.edu/ department/publications/reports/greggrudic.html (на 20.01.09).

88. Bur. Burges C.J.C. A Tutorial on Support Vector Machines for Pattern Recognition I I Data Mining and Knowledge Discoveiy. 1998. - V.2. - №2. - Pp.121167.

89. DD02. Deza M., Dutour M. Data mining for cones of metrics, quasi-metrics, hemi-metrics and super-metrics. // CNRS/ENS Paris, Tokyo: 2002. - http:// arxiv.org/pdf/math/0201011 (на 17.11.08).

90. DS51. Diliberto S.P., Straus E.G. On the approximation of a function of several variable by the sum of functions of fewer variables // Pacific J. Math. — 1951.1. — Pp.195-210.

91. DLC. Dyn N., Light W:A., Cheney E. W. Interpolation by piecewise-linear radial basis functions // J. Approx. Theory. 1989. - №59. - Pp.202-223.

92. FS95. Freund Y., Schapire R.E. A decision-theoretic generalization of on-line learning and an application to boosting // European- Conference on Computational Learning'Theory. 1995. — Pp.23-37.

93. GP71. Graham R.L., PollakH.O. On the addressing problem for loop-switching // Bell System Tech. J. 1971. - №50. - Pp.2495-2519.

94. H135. Hall P. On representatives of subsets // J. London Math. Soc. 1935. - V.10.1. Pp.26-30.

95. H98. Haykin S.S. Neural Networks: A Comprehensive Foundation. Prentice-Hall, second edition, 1998. (перевод: Хайкин С. Нейронные сети: полный курс, 2-е издание. — М. Издательский дом «Вильяме», 2006. - 1104'с.)

96. JJ91. Jacobs R.A., Jordan M.I., Nowlan S.J., Hinton G.E. Adaptive mixtures of local experts //Neural Computation. 1991. - №3. - Pp:79-87.

97. Light W.A. The singularity of distance matrices // Multivariate Approximation Theory. Birkhauser-Verlag, 1989. -Pp.233-240.

98. Mi86. Micchelli C.A. Interpolation of scattered data: Distance matrices and conditionally positive definite functions // Constructive Approximation. -1986.-V.2.-Pp. 11-22.

99. OWS90. Osherson D.N., Weinstein S., Stoli M. Modular learning // Computational Neuroscience. Cambridge, MA: MIT Press, 1990. - Pp.3 69-3 77.

100. RS93.Reid L., SunX. Distance matrices and ridge function interpolation // Canadian Journal of Mathematics. 1993. - V.45. -Pp.1313-1323.

101. Sc90. Schapire R.E. The strength of weak learnability // Machine Learning. — 1990. -V.5.-Pp. 197-227.

102. S37. Schoenberg I.J. On certain metric spaces arising from Euclidean spaces by a change of metric and their imbedding in Hilbert space // Ann. Math. — 1937. — №38: — Pp.787—793.

103. S3 8. Schoenberg I.J. Metric spaces and positive definite functions // Trans. Amer. Math. Soc. 1938. - №44. - Pp:522-536.

104. S3 8a.', Schoenberg I.J. Metric spaces and: completely monotone functions // Ann. Math. 1938. - №39. - Pp.811-841.

105. Sn93. SunX. Solvability of multivariate interpolation by radial or related functions // Journal of Approximation Theory. 1993. - №72. - Pp.252-267.

106. V98. Vapnik V. Statistical Learning Theoiy. Wiley, New York, 1998.

107. Zd65.'Zadeh L.A. Fuzzy sets // Information and Control. 1965. - V.8. - Pp.338353.1. Список работ автора

108. ДООд. Дьяконов А.Г. О выборе системы опорных множеств для эффективной реализации алгоритмов распознавания типа вычисления оценок // Докл. РАН. 2000. - Т.371. - №6. - С.750-7521.

109. ДОО. Дьяконов А.Г. О выборе системы опорных множеств для эффективной реализации алгоритмов распознавания типа вычисления оценок // Ж. вычисл. матем. и матем. физ. 2000. - Т.40. - №7. —

110. С.1104-1118. (перевод: D'yakonov A.G. On the choice of a system of support sets for an efficient implementation of recognition algorithms of the estimate-computing type // Comput. Math. Math. Phys. 2000. - V.40. - №7. -Pp. 1060-1074.)

111. Д05Ь. Дьяконов А.Г. Об одном подходе к решению задач из области BCI // Сборник докладов XII Всероссийской конференции ММРО-12. М.: МАКС Пресс, 2005. - С.95-97.

112. ДОбт. Дьяконов А.Г. Графовые и матричные критерии корректности алгоритмов распознавания образов // Труды VII международной конференции «Дискретные модели в теории управляющих систем», Покровское, 4-6 марта 2006 г. М.: МАКС Пресс, 2006. - С. 114-118.

113. Д06. Дьяконов А.Г. Алгебра над алгоритмами вычисления оценок: Учебное пособие. М.: Издательский отдел ф-та ВМиК МГУ им. М.В. Ломоносова, 2006. - 72 с. (ISBN 5-89407-252-2).

114. ДОбк. Дьяконов А.Г. Корректность относительно семейства решающих правил // Интеллектуализация обработки информации: тезисы докладов Международной научной конференции. Симферополь. Крымский научный центр НАН Украины, 2006. - С.77-78.

115. ДОби., Дьяконов А:Г. Корректность относительно семейства решающих правил // Искусственный интеллект. 2006. - №2. — С.61-64.

116. Д07т. Дьяконов А.Г. Анализ кластерных конфигураций в одной проблеме фильтрации спама // Математические методы распознавания- образов: 13"-я Всероссийская конференция: Сборник докладов. — М.: МАКС Пресс, 2007. С.476-478.

117. Д08тYДьяконов А.Г. Исследование алгебраических замыканий алгоритмов распознавания: операторы разметки» // Таврический вестник информатики и математики. 2008. — №1г. — G.199—2031

118. Generalizations // Dokl. Math. 2009. - V.79. - №.2. - Pp. 150-152.)