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

• Романов, Михаил Юрьевич
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Романов, Михаил Юрьевич

Введение

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

Список литературы диссертационного исследования кандидат физико-математических наук Романов, Михаил Юрьевич, 2008 год

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