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



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

Романов Михаил Юрьевич

Построение обобщённых полиномов

минимальной степени над алгоритмами вычисления оценок

Специальность 05 13 17 —теоретические основы информатики

Автореферат

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

Москва 2008

□□344Э189

003449189

Работа выполнена в Вычислительном центре им А А Дородницына Российской Академии наук

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

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

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

доктор физико-математических наук, профессор, академик РАН Журавлев Юрий Иванович

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

кандидат физико-математических наук Кольцов Петр Петрович

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

Защита диссертации состоится <10 >_1L) 2008 г в t часов на заседании диссертационного совета Д002 017 02 в Вычислительном центре им А А Дородницына Российской Академии Наук по адресу 119333, Москва, ул Вавилова, 40

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

Автореферат разослан «2-^ » О}I 2008 г

Ученый секретарь

диссертационного совета

Д002 017 02 при Вычислительном центре

им А А Дородницына РАН

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

Рязанов В В

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

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

К концу 50-х годов прошлого века были сформулированы многие параметрические семейства алгоритмов распознавания Ю И Журавлевым разработан класс алгоритмов вычисления оценок (ABO), который также можно использовать в качестве языка описания методов распознавания Следующим важным этапом развития теории распознавания стало создание Ю И Журавлевым алгебраического подхода, который является эффективным способом описания алгоритмических композиций В рамках этого подхода наибольший интерес представляют полиномиальные композиции В частности, было показано, что для любой регулярной задачи существует корректный алгоритм среди полиномов над ABO Это привело к широкому применению полиномиальных алгоритмических структур при исследовании и решении прикладных проблем Поэтому одной из ключевых задач стало уменьшение сложности алгебраических композиций Значительное количество работ посвящено оценке степени и числа слагаемых корректного полинома над алгоритмами распознавания Этой задачей занимались Ю И Журавлев, И В Исаев, В Л Матросов, Т В Плохонина, К В Рудаков, А С Дьяконов В настоящей диссертации продолжены эти исследования и приведен метод построения полинома минимальной степени над заданным набором алгоритмов

Цель работы состоит в разработке метода построения обобщенного полиномиального алгоритма наименьшей степени в алгебре над множеством алгоритмов вычисления оценок

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

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

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

Апробация работы. Результаты, изложенные в диссертации, докладывались на Всероссийской конференции «Математические методы распознавания образов» XIII (Москва, 2007 г), «Интеллектуализация обработки информации»-2008 (Алушта, Украина, 2008 г), а также на научных семинарах МФТИ

Основные результаты диссертации

1) Введено понятие обобщенного полиномиального алгоритма в алгебре над множеством алгоритмов вычисления оценок

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

3) Предложен метод декомпозиции рассмотренной оптимизационная задачи на множество вспомогательных задач

4) Построен алгоритм решения вспомогательных задач

5) Рассмотрены два подхода повышения эффективности предложенного метода Первый подход позволяет сократить число решаемых вспомогательных задач, второй — снизить их сложность

6) Приведено развитие этого подхода, позволяющее понизить степень обобщенного полинома за счет уменьшения числа слагаемых (распознающих операторов)

7) Рассмотрен вопрос многопроцессорной реализации приведенных методов

8) Проведена серия экспериментов по практической реализации предложенного метода На рассмотренных примерах показана высокая эффективность метода

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

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

Публикации. По теме диссертации автором опубликованы 4 работы

Структура и объем работы. Работа состоит из введения, четырех глав и списка литературы из 33 наименований Общий объем работы — 80 страниц, включая 4 рисунка и 27 таблиц

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

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

В первой главе вводятся основные понятия и определения используемые в работах Ю И Журавлева, посвященных алгебраическому подходу к решению задач распознавания и классификации Рассматриваются алгоритмы вычисления оценок (ABO) Описывается формальная постановка задачи построения распознающего алгоритма следующим образом

Множество из М объектов разделяется на обучающую выборку Sm и контрольную выборку Sq _

Задача распознавания Z = (7о, S9) определяется начальной информацией /о о принадлежности объектов классам и контрольной выборкой Sq Для каждого контрольного вектора необходимо найти информационный вектор

/3 {sl) = (д, = Р, (5') ЕЕ (S* е К,) ,3 = м)

Рассматривается множество алгоритмов {Л} решения задачи Z = (/о, Sq), представленных в виде произведения операторов А = В-С Здесь оператор В определяет матрицу оценок В (Z) = ||ГЧ||?xj, где Гц — действительные числа, а оператор С — матрицу ответов

C(l|ry||gx¡) = Klexj, где /Зц £ {0,1, Д}.

Возможность представления произвольного алгоритма распознавания в таком виде показана Ю И Журавлевым

Определение 1.1. Алгоритм А называется корректным для задачи Z, если выполнено равенство А ^/о, Sgj = ||ац ||?xj Алгоритм А, не являющийся корректным для Z, называется некорректным

Определение 1.2. Решающее правило С называется корректным на М, если для всякого конечного набора Sm € М существует хотя бы одна числовая матрица ||atj||?x¡ такая, что С (||

Для распознающих операторов (РО) можно ввести операции сложения, умножения на константу и операторного умножения таким образом, что это будут операции над оценками, то есть над значениями операторов Эти операции индуцируют соответствующие операции над алгоритмами распознавания Это позволяет ввести над множеством РО операции линейного и алгебраического замыкания Определение 1.3. Множества L({.A}), U({A}) алгоритмов А = В

и соответственно таких, что В 6 L({B}), В 6 U({B}), называется соответственно линейным и алгебраическим замыканиями {Л}

Множество алгоритмов, построенное на алгебраическом замыкании к-й степени над некоторым набором РО, будем называть алгебраическим расширением к-й степени

Для краткости степенью алгоритма А будем называть степень алгебраического расширения, в котором построен этот алгоритм Иначе говоря, это можно понимать, как степень полинома над операторами {Вь}, который является распознающим оператором алгоритма А

В работах Ю И Журавлева получены следующие результаты Теорема 1.1. Пусть {А} — совокупность некорректных алгоритмов, {В} — соответствующее множество операторов, С — фиксированное корректное решающее правило Тогда L{A} = {L{B} С} является корректным относительно {Z}, если {Z} состоит из задач, полных относительно {В}

Теорема 1.2 Пусть выполнены все условия предыдущей теоремы и, кроме того, [{5}] есть замыкание {В} относительно операций умножения на константу и операторного умножения Тогда U {А} = {U {В} С} является корректным относительно {Z}, если {Z} состоит из задач, полных относительно [{В}]

Для алгоритмов вычисления оценок (ABO) предполагается, что элемент матрицы распознающего оператора В равен Гу = Гj(S") и является оценкой объекта 5г по классу К}

В качестве решающего правила используется стандартное корректное пороговое решающее правило С (||Г

qXl>

с (Гц) = {о, Гу сь 1, Гц > а, Д, d < Гц < с2}

Элементы матрицы ответов можно разбить на два множества

HAJgxi = Mo U Mi, где М, = |(и,и) : /?„„ = г|, q — число объектов, I — число классов

Оператор В с матрицей оценок В (Z) = ||Г,;||дхг называется допустимым для задачи Z, если существует хотя бы одна пара (и, v) € Mi такая, что для всех (i,j) € Mo выполняется Ги„ (В) > |Гу (В) |

Такая пара (и, v) называется отмеченной в В, и множество отмеченных в В пар обозначим через М (В) Фактически, это означает, что отмеченные пары «отделены» от всех пар (t,j) таких, что объект 51* не принадлежит классу Поэтому, при некоторых порогах Ci, С2 алгоритм В С будет давать правильные ответы для всех пар, отмеченных в В

Допускается альтернативный способ определения отмеченных точек Пара (и, v) называется отмеченной в В при некоторой фиксированной величине 6, если для всех (i,j) е Mo имеет место неравенство

Гт{В)>\Г13(В)\ + 6

При таком определении все дальнейшие рассуждения остаются справедливыми

Пусть TUB) - Г UB) = (jmn{B)|r4(B)|

Введем Г(В) = [г^ш(В)]Q(B) = Г°шах(В)/ Г^П(В)

Для оператора В можно ввести оператор В' = Г(В) В. Определив в задаче Z — (iojS4^ элементы матрицы оценок, как В' (Z) — ||Гу||гх/,

получим (В) =Г(В) Гц (В)

Ю И Журавлевым показано следующее утверждение Лемма 1.3. Если (u,v) отмечена в В, то Гц(В) > 1, если {u,v) не отмечена, в В, то Т[: (В) < Q(B) < 1

Тогда, учитывая, что матрица оценок В' (Z) получается из В (Z) поэлементным умножением, получим, что пара (u, v) является отмеченной в В' тогда и только тогда, когда она отмечена в В

Пусть {Впроизвольная конечная система распознающих операторов

Определение 1.4. Система {В*;} является базисной для Z, если

м,= и М(вк) к=1

В работе Ю И Журавлева приводится теорема о том, что полиномиальный алгоритм со степенями, определяемые некоторой формулой, является корректным для 2 При этом, указанные в теореме степени распознающих операторов оказываются заведомо большими, чем необходимо для выполнения условий корректности

В работах К В Рудакова и А Г Дьяконова получена точная верхняя грань степени полинома, необходимой для корректности алгоритма Для любого набора операторов, если существует корректный полиномиальный алгоритм, мы можем полагать, что степень этого алгоритма не превосходит величину [1о§2 ql]

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

В параграфе 2 1 рассматривается обобщение введенных полиномиальных алгоритмов В отличие от предыдущего, степень распознающего оператора предполагается действительным числом, а не только целым Определение 2.1. Обобщённым алгебраическим замыканием множества, распознающих операторов В* = {В\,В2, ,ВП} будем называть множество

и(в*) = ь({в? вр в*1 д ев*,ек,» = 175,1

Элементы этого множества назовем обобщёнными полиномами над В*, а слагаемые этого полинома —обобщенными мономами

Аналогично, множество 0(А*) алгоритмов А = В С таких, что Вей (В*), назовем обобщенным алгебраическим замыканием А*

Определение 2 2 Пусть задано множество РО В* = {В\,В2, ,£?„}

Степенью обобщённого монома В*1 В*' будем называть

величину х\ + Х2 + . • + х3

Степенью обобщённого полинома В £ О (В*) будем называть максимальную из степеней входящих в него обобщенных мономов

Степенью алгоритма А = В С из обобщенного алгебраического замыкания будем называть степень обобщенного полинома В

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

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

Пусть задан набор РО Вь, строящих матрицы оценок В^ (Я) = = ||Г™||?><|, и оператор С задан стандартным пороговым решающим

правилом С (ГН = {о, ГГ < С1; 1, Г™ > с2, Д, С1 < ГГ < с2}, которое определяется параметрами с\, с%

Замечание 2 1. Без ограничения общности будем считать, что для параметров с\, с? выполнено условие С1 + С2 — 1 В противном случае, эти параметры следует разделить на сумму с\ + с2

Определение 2.3. Набор распознающих операторов {Вк} будем называть правильным, если для него выполняются следующие условия

1) Каждый оператор является допустимым, т е существует хотя бы одна пара (и, V) е Му отмеченная в В

2) Каждый оператор является нормированным, т е по лемме 1 3 если (и, у) отмечена в В, то ^ 1, иначе Г^ < 1

п

3) Система {В^} является базисной для 2, т е М\ = и М (Вк)

к=1

В противном случае набор операторов будет называть неправильным

В дальнейшем описывается алгоритм, корректный для задачи Z, в следующем виде А = Щ*} 0 С(й.сг). Сформулируем теоре-

му, которая накладывает условия на степени обобщенных полиномов, при которых рассматриваемый алгоритм является корректным Теорема 2.1. Пусть задан набор операторов {Вк} , к = 1, п, дающих матрицы оценок Вк (/?) = на обучающей выборке задачи И

Пусть для набора степеней {а^} имеют место следующие условия

1) для любой пары (и, у) 6 М0 выполняется Ги„ = 22=1 (ГТТ* ^ с1>

2) для любой пары (и, и) 6 Мх выполняется Ги„ = (Г^)1* ^ с2 Тогда алгоритм

Л={Х>Г}°С(С1,С2) (1)

является корректным для 2

Пусть также набор операторов {Вк} является правильным по определению 2 3, т е операторы являются допустимыми, нормированными и образуют базисную систему для 2 Тогда существует набор степеней {хк} определяющий алгоритм А, корректный для задачи

Теперь сформулируем оптимизационную задачу для определения набора степеней {х^ удовлетворяющих условиям теоремы 2 1 и дающих обобщенный полином минимальной степени

\(и,у)ем0. П=г(1ГГ<*1. <УМ)еМ1 Е£=1 (17)** > са, (2)

тахх* —+ тт

Кк=1,п

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

Введем замену переменных у¡, = еХк, 7™ = 1пГ™, <риу(у) = — 2ь=1 У~к Тогда, учитывая результаты параграфа 1 3, оптимизационная задача (2) принимает вид

!<Рт{у) 4 сь для всех (и,у) е М0, 1 У <Рт{у) с2, для всех (и, V) € Ми > (3)

0 ^ Ук ^ М = <3^, для всех к = 1, п )

Я= \ у €11, тах ук —> шш (4)

I ЫТл J

В параграфе 2 3 описывается метод декомпозиции рассматриваемой оптимизационной задачи Для каждого непустого множества индексов I = {«1, ,гт} С {1, ,п} рассматривается задача

Л/ = {у е иТ, г/п ппп} (5)

с множеством ограничений

VI = {у € и, уп = Уг2= = Угт) Уг\ > Ук, к 1} (6)

Таким образом, исходной задаче Я ставится в соответствие 2" — 1 вспомогательных задач Я/ В последующих параграфах будет показано, что задачу Я с нелинейным функционалом можно решить, найдя решение более простых задач Я/ с линейным функционалом В следующей главе будут приведены методы, позволяющие существенно сократить количество решаемых задач

В параграфе 2 4 рассматривается геометрическая интерпретация предложенного метода декомпозиции

В параграфе 2 5 приводится теорема о существовании решения оптимизационной задачи

Теорема 2.2. Существует непустое множество индексов

1 = Оъ С {1, . , п}

такое, что решение задачи Я/ является решением задачи К

В параграфе 2 6 рассмотрены алгоритмы решения вспомогательных задач Rj Описан метод линеаризации, позволяющий свести задачу к последовательности задач квадратичного программирования Так как все ограничения множества £// являются полиномиальными, то такое сведение удается сделать аналитически

Далее описаны алгоритмы решения задачи квадратичного программирования методом линеаризации и обобщенным методом Ньютона

В настоящий момент наиболее эффективным методом решения задачи нелинейной оптимизации (задача Ri) считается метод последовательного квадратичного программирования (Sequential Quadratic Programming, или SQP) Он позволяет сводить исходную нелинейную задачу к последовательности задач квадратичного программирования, на каждом шаге осуществляя аппроксимацию Гессиана функции Лагран-жа с помощью обобщенного метода Ньютона

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

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

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

Для описания свойств вспомогательных оптимизационных задач вводятся некоторые специальные операторы Пусть для некоторой оптимизационной задачи Л/ при наборе / = {г:, . , гт} С {1, , п}, решением является вектор у (Л/) размерности п Тогда для задачи Л/ введем следующие обозначения

= тах у (Л/) , в1 = у{А1) (7)

к=1,п к Ч

Для задачи Д с решением у* введем Е(К) — Е* — шах у*к При этом

к=1,п

для любого набора I выполняется б/ < Сформулируем несколько свойств для введенных операторов

Теорема 3 1. Пусть заданы два набора индексов I1 С /2, где Тогда 1) Уп Э иР, 2) б/. ^

Теорема 3.2. Яусть для набора Г- {г^, г^, С {1,2, ,п},

решение задачи Д/. совпадает с решением задачи Д Тогда для любого набора I = {«1,12, , гт1} С {1,2, , п}, выполняется Е^ ^

Замечание 3.1. В теореме 2 2 решение задачи Л сводится к выбору среди решений задач Д/ Таким образом, необходимо найти набор /*, определяющий вспомогательную задачу, решение которой является решением задачи Л Тогда, по теореме 3.2 достаточно искать минимум величины шах^/А не на всем множестве £7, а лишь среди всех решений

к=1,п

задач Д/ Для них эта величина равна .Р/, и в новых обозначениях задачу минимизации можно сформулировать следующим образом

I* — аге пип Л

/С{1, ,п}

Лемма 3 3 Пусть для некоторых I1 и I2 выполняется следующее свойство <7/: > Ер Тогда для любого набора I, содержащего I1, решение задачи Дг является решением задачи Д только тогда, когда задача Яр дает решение задачи Д

Замечание 3.2. Из доказанной леммы 3 3 следует, что если найдены наборы I1 и I2, удовлетворяющие условию леммы, то все 7, содержащие поднабор I1, следует исключить из рассмотрения Это утверждение лежит в основе рассматриваемого далее алгоритма эффективного перебора вспомогательных задач

Описывается эффективный алгоритм поиска вспомогательной задачи Д/*, дающей решение задачи Д

1) Рассматриваем упорядоченное множество наборов

Н — {I 1С {1,2,. ,п}, I ф 0},

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

2) Выбираем первый нерассмотренный набор / из Н и решаем задачу Дг

3) Вычисляем значения С/ и ^ Если ^ < то присваиваем

4) Если (3; ^ ^тш. Т0 удаляем из Н все наборы, которые содержат поднабор I (см замечание 3 2)

5) Если в Н рассмотрены не все наборы, то переходим к шагу 2

6) Искомое решение, согласно теореме 3 2 и замечанию 3 1, определяется тем набором Г, для которого = Рт1П

В параграфе 3 2 приводится следующий метод сокращения общего количества вычислений Множество II (см формулу (3)) содержит ограничения

О < у, < М, г = 17п,

где полагается М = согласно результатам параграфа 1 3

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

Замечание 3.3. Во многих случаях оказывается полезным в первую очередь решить задачу П[ при / = {1,. , п}, тем самым уже на первом шаге существенно уменьшив область ограничений

В экспериментах, приведенных в параграфе 4 3, наиболее существенное уменьшение области ограничений происходило именно на таком первом шаге

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

В параграфе 3 4 рассматривается возможность уменьшения степени полиномиального алгоритма за счет уменьшения количества РО

Рассмотрим начальный набор распознающих операторов 23 = {Вк}, который является базисным для задачи распознавания 2 Решение задачи Д(2$) дает алгоритм Л(23), корректный для 2, причем степень обобщенного полинома запишем, как ^(93) = ^ (Д(23)) Определение 3.1. Пусть для набора 93' заданы функции (у), определяющие ограничения оптимизационной задачи Будем говорить, что

• набор 93' С 93 имеет тип 1, если для некоторой пары (и, у) € М\ выполняется (р'ш (у) = сг,

• на бор 93' С 23 имеет тип 0, если для некоторой пары (и, и) 6 Мо выполняется <р'т (у) — С\

Теорема 3.4 Из распознающих операторов набора 93 обобщенный полином наименьшей степени может быть образован либо всем набором 93, либо поднабором 23' С 93, соответствующим тупиковому покрытию множества М\ При этом 93 является оптимальным тогда и только тогда, когда имеет тип 1

Из теоремы 3 4 следует, что достаточно решить задачу К для набора 23 и всех его тупиковых (или базисных) поднаборов

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

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

1) Решаем задачу Д(93) По определению 2 3 проверяем тип набора !8 Если получен тип 1, то задача решена Иначе, переходим на следующий шаг

2) Для каждого оператора из набора 58 = {Дь} находим множество М(Вк) — множество отмеченных пар

3) Находим все тупиковые покрытия множества М\ множествами М(Вк), к = 1,п Пронумеруем наборы, соответствующие покрытиям {03г, г = ЦМ}

4) Последовательно решаем задачи и среди полученных решений выбираем то, которое дает наименьшую степень

Аналогично результатам параграфа 3 2 описан метод упрощения перебора тупиковых, основанный на уменьшении ограничения М Пусть нар-й итерации минимальным решением является = я < р,

тогда при решении задачи Л(03р+1) мы можем положить М = Таким образом, мы на каждом шаге будем сужать область ограничения последующих задач, за исключением тех шагов, где область ограничения окажется пуста Здесь также возможно применение приближенного подхода

Описан подход к эффективному распараллеливанию рассматриваемого алгоритма, аналогичный приведенному в параграфе 3 3

В главе 4 приведены результаты экспериментального исследования рассмотренных методов

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

В параграфе 4 3 приведены практические эксперименты В качестве источника данных используются задачи из репозитория 11С1

Для практического исследования работы алгоритма нахождения обобщенного полинома минимальной степени на заданном наборе из п распознающих операторов, этот алгоритм реализован на языке MATLAB Каждая вспомогательная задача сводится методом линеаризации к последовательности задач квадратичного программирования (см параграф 2 6 1) В качестве процедуры решения задачи квадратичного программирования используется метод quadprog из пакета Optimization Toolbox, который основан на обобщенном методе Ньютона (см параграф 2 6 3) Для обработки случая, когда набор операторов не является базисом, используются результаты параграфа 4 2 В качестве первой вспомогательной задачи рассматривается задача R[ при I = {1,. , п} для уменьшения величины М (см замечание 3 3) Затем применяется алгоритм сокращения перебора вспомогательных задач (см параграф 3 1) При решении рассматриваемых задач используется набор алгоритмов из пакетов MatLabArsenal и WEKA

Предложенный алгоритм сравнивается в режиме скользящего контроля с алгоритмом голосования

Результаты скользящего контроля (в %)

Задача Iris Sonar Musk Breast Cancer

А = {ELi вкХк\ с 2 0 9 6 1784 3 51

Голосование 73 14 9 18 46 3 87

Уменьшение области ограничений

M = ql 450 416 952 1138

М после первого шага 0 59 0 58 0 59 0 38

max ук к=1,п 0 53 0 53 0 53 0 34

Для всех рассмотренных задач можно отметить преимущество обобщенного полиномиального алгоритма над алгоритмом голосования Во всех экспериментах наиболее существенное уменьшение области ограничений происходило на первом шаге Кроме того, метод сокращения числа решаемых оптимизационных задач позволил уменьшить их количество с 2" - 1 до п + 1

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

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

Список публикаций по теме диссертации

1 Романов М Ю Об одном методе построения распознающего алгоритма в алгебре над множеством вычисления оценок //Ж вычисл матем и матем физ -2007 -Т 47, №8 -С 1426-1430

2 Романов М 10 Построение корректного распознающего алгоритма минимальной степени в алгебре над множеством алгоритмов вычисления оценок // ММРО-13 -М МАКС Пресс, 2007 - С 60-62

3 Романов М Ю Реализация одного метода построения распозаю-щего алгоритма в алгебре над множеством алгоритмов вычисления оценок //Ж вычисл матем и матем физ —2008 — Т 48, №9

4 Романов М Ю Полиномиальный корректный распознающий алгоритм минимальной степени в алгебре над множеством алгоритмов вычисления оценок // ИОИ-2008 — Симферополь, 2008

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

Издательство ООО "МАКС Пресс" Лицензия ИДN00510от01 12 99г Подписано к печати 26 09 2008 г Формат 60x90 1/16 Услпечл 1,25 Тираж 100 экз Заказ 525 Тел 939-3890 Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им МВ Ломоносова, 2-й учебный корпус, 627 к

Введение

1 Основные определения и обозначения

1.1 Вводные понятия.

1.2 Условия существования корректного алгоритма.

1.3 Оценка степени полинома.

2 Оптимизационная задача

2.1 Алгоритмы в обобщённом алгебраическом замыкании

2.2 Формулировка оптимизационной задачи.

2.3 Декомпозиция оптимизационной задачи.

2.4 Геометрическая интерпретация.

2.5 Теорема о существовании решения.

2.6 Решение вспомогательной задачи.

2.6.1 Сведение к последовательности задач квадратичного программирования

2.6.2 Решение задачи квадратичного программирования методом линеаризации.

2.6.3 Решение задачи квадратичного программирования обобщённым методом Ньютона.

2.6.4 Метод последовательного квадратичного программирования

3 Эффективные методы решения

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

3.2 Последовательное уменьшение области ограничений

3.3 Модификация алгоритма для работы на многопроцессорных системах.

3.4 Минимизация числа слагаемых.

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

4 Проведение экспериментов

4.1 Описание экспериментов.

4.2 Обобщённый полиномиальный алгоритм над неправильным набором распознающих операторов.

4.3 Решение задач.

4.3.1 Методика проведения экспериментов.

4.3.2 Задача «Iris»

4.3.3 Задача «Sonar».

4.3.4 Задача «Musk».

4.3.5 Задача «Breast Cancer»

4.3.6 Выводы.

4.4 Оценка эффективности.

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

Основы алгебраического подхода в теории распознавания были заложены в работах Ю. И. Журавлёва и его учеников. Этот взгляд на теорию распознавания стал возможен благодаря показанном}'" в работе [б] представлению алгоритмов распознавания в виде композиции распознающего оператора и оператора, задающего решающее правило. Такое разделение • на два разнотипных оператора позволило описывать алгоритмы в виде композиции более простых алгоритмов, используя для этого элементы из алгебраического замыкания.

Ю. И. Журавлёвым был предложен [4, 5, 7] алгоритм вычисления оценок (ABO). АВО используется, как универсальный язык описания алгоритмов распознавания в теоретических вопросах, а также и для решения прикладных задач.

В [7] вводится понятие регулярности задачи распознавания и доказывается теорема существования корректного алгоритма в алгебраическом замыкании АВО для любой регулярной задачи. Первые оценки степени корректного полинома и вопросы его устойчивости были получены в [8].

Задача нахождения полиномов наименьшей степени является весьма существенной для построения алгоритмов высокой точности. Это определяет постоянный интерес исследователей к данному вопросу.

Дальнейшие результаты оценки степени корректного полинома были получены B.J1. Матросовым. В работе [12] был получен критерий корректности замыкания семейства АВО конечной степени. На основании этого критерия им была показана неполнота линейного замыкания модели АВО [14]. В работе [16] Т. В. Плохонина развила этот результат, показав неполноту квадратичного замыкания модели АВО. В своей докторской диссертации B.JI. Матросовым [15] получен аналогичный результат для общего случая —при любой фиксированной степени существует задача распознавания, для которой в замыкании этой степени нельзя получить корректный алгоритм.

B.JI. Матросову удалось улучшить верхние оценки степени и количества слагаемых для замыкания классического семейства АВО [13]. Кроме того, им было предложено обобщение АВО (семейство АВО над упорядоченным полем G) и показано, что это обобщение содержит корректный алгоритм в линейном замыкании [15].

К. В. Рудаковым была создана теория локальных и универсальных ограничений [24], в основе которой лежит идея о том, что только прецедентной информации недостаточно для полного описания множества алгоритмов. При этом был разработал математический аппарат описания дополнительных ограничений, названных универсальными [21, 22]. В рамках этой теории были исследованы проблемы разрешимости задач и регулярности с точки зрения непротиворечивости локальных и универсальных ограничений, а также проблема полноты классов алгоритмов [23]. Кроме этого, были получены оценки минимальной степени полиномиальных семейств корректирующих операций [24]. Этот результат существенным образом используется в настоящей работе.

Используя введённые B.JI. Матросовым операторы разметки [11], А. Г. Дьяконов получил неулучшаемую верхнюю оценку степени корректности полинома [3].

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

В главе 1 вводятся основные понятия и определения, используемые в работах Ю. И. Журавлёва [6, 9, 10].

В главе 2 вводятся обобщения понятий главы 1. Строится оптимизационная задача, решение которой определяет степени искомого обобщённого полинома. Описывается метод решения этой задачи. Приводится описание и сравнение различных подходов к решению поставленной задачи. Основные результаты этой главы приведены в работе [17].

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

В главе 4 приведены результаты экспериментального исследования рассмотренных методов.

4.3.6 Выводы

Приведём сводную таблицу средних значений ошибки на скользящем контроле по всем задачам.

Задача {ELi BS>}-C Голосование

Iris 2.0 7.3

Sonar 9.6 14.9

Musk 17.84 18.46

Breast Cancer 3.51 3.87

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

Во всех экспериментах наиболее существенное уменьшение области ограничений происходило иа первом шаге.

Задача M = ql M после первого шага max.yk k—l,n

Iris 450 0.59 0.53

Sonar 416 0.58 0.53

Musk 952 0.59 0.53

Breast Cancer 1138 0.38 0.34

Кроме того, метод сокращения числа решаемых оптимизационных задач позволил уменьшить их количество с 2" — 1 до п + 1.

4.4 Оценка эффективности

Приведём сравнение эффективности методов решения задачи R различными подходами.

1) Решение задачи R методом fmincon пакета Optimization Toolbox системы MATLAB, без использования всех подходов, предложенных в данной работе. При этом задача R решается методом SQP.

2) Применение предыдущего метода к решению вспомогательных задач Rj. При этом вспомогательные задачи решаются методом SQP, потом выбирается решение задачи R. Используется метод сокращения перебора и метод уменьшения области ограничений.

3) Применение метода, использовавшегося в предыдущем параграфе, т. е. линеаризация вспомогательных задач Rj и решение полученных задач квадратичного программирования методом quadprog из пакета Optimization Toolbox системы MATLAB.

В эксперименте использовалась задача «Iris». Для остальных задач получаются аналогичные соотношения результатов.

1. Васильев Ф. П. Численные методы решения экстремальных задач. — М.: Наука, 1988.

2. Голиков А. И., Евтушенко Ю.Г., Моллаверди Н. Применение метода Ньютона к решению задач линейного программирования большой размерности // Ж. вычисл. матем. и матем. физ. — 2004. — Т. 44, №9.-С. 1564-1573.

3. Дьяконов А. Г. Алгебра над алгоритмами вычисления оценок: минимальная степень корректного алгоритма // Ж. вычисл. матем. и матем. физ. 2005. - Т. 45, №6.-С. 1134-1145.

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

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

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

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

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

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

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

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

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

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

14. Матросов В. Л. О неполноте модели АВО // Ж. вычисл. матем. и матем. физ. —1983—Т. 23, №2.

15. Матросов В. Л. Корректные алгебры алгоритмов распознаванияограниченной ёмкости — Дис. .докт. физ.-матем. наук, М.: 1985.

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

17. Романов М. Ю. Об одном методе построения распознающего алгоритма в алгебре над множеством вычисления оценок // Ж. вычисл. матем. и матем. физ. — 2007. — Т. 47, №8. —С. 1426-1430.

18. Романов М. Ю. Построение корректного распознающего алгоритма минимальной степени в алгебре над множеством алгоритмов вычисления оценок // MMPO-13. — М.: МАКС Пресс, 2007.-С. 60-62.

19. Романов М. Ю. Реализация одного метода построения распозаю-щего алгоритма в алгебре над множеством алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ. — 2008.—Т. 48, №9.

20. Романов М. Ю. Полиномиальный корректный распознающий алгоритм минимальной степени в алгебре над множеством алгоритмов вычисления оценок // ИОИ-2008.— Симферополь, 2008.

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

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

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

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

25. Хемди А. Таха Введение в исследование операций. Глава 3. Симплекс-метод. — М.: «Вильяме», 2007, С. 95-141.

26. Biggs М. С. Constrained Minimization Using Recursive Quadratic Programming // Towards Global Optimization (L.C.W. Dixon and G.P. Szergo, eds.), North-Holland, pp. 341-349, 1975.

27. Gill P.E., Murray W., Wright M.H. Practical Optimization — London, Academic Press, 1981.

28. Gill P. E., Murray W., Saunders M. A., Wright M. H. Procedures for Optimization Problems with a Mixture of Bounds and General Linear Constraints // ACM Trans. Math. Software, Vol. 10, pp. 282-298, 1984.

29. Gill P. E., Murray W., Wright M. H. Numerical Linear Algebra and Optimization // Vol. 1, AddisonWesley, 1991.

30. Fletcher R. Practical Methods of Optimization // Vol. 1, Unconstrained Optimization, and Vol. 2, Constrained Optimization, John Wiley and Sons, 1980.

31. Hock W., Schittkowski K. A Comparative Performance Evaluation of 27 Nonlinear Programming Codes // Computing, Vol. 30, p. 335, 1983.

32. Powell М. J. D. Variable Metric Methods for Constrained Optimization // Mathematical Programming: The State of the Art, (A. Bachem, M. Grotschel and B. Korte, eds.) Springer Verlag, pp. 288-311, 1983.

33. Schittkowski K. NLQPL: A FORTRAN-Subroutine Solving Constrained Nonlinear Programming Problems // Annals of Operations Research, Vol. 5, pp. 485-500, 1985.i ! 1