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

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

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

Ю. И. Журавлёвым был предложен [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». Для остальных задач получаются аналогичные соотношения результатов.