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

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

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

Введение

1 Алгоритмы вычисления оценок.

2 Операции над ABO. Алгебры.

3 Корректные алгоритмы. Теорема существования корректного алгоритма.

4 Оптимальный метод поиска ABO максимальной высоты.

4.1 Переход к вспомогательной задаче.

4.2 Обоснование оптимальности метода.

4.3 Метод поиска оптимального параллелепипеда во вспомогательном пространстве.

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

4.5 О трудоёмкости задачи поиска оптимального прямоугольника.

5 Приближенные методы поиска оптимального прямоугольника.

5.1 Алгоритм построения тестовых выборок.

5.2 Жадный алгоритм.

5.3 Метод покоординатного подъема.

5.4 Генетический алгоритм

-35.5 Тестирование методов.

6 Реализация метода распознавания на основе алгоритмов поиска ABO максимальной высоты.

6.1 Оптимальная схема.

6.2 Приближённый метод, программная реализация.

6.3 Результаты тестирования.

Введение диссертации (часть автореферата) на тему «Синтез полиномов над экстремальными алгоритмами вычисления оценок»

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

Основой для исследований послужили результаты теории распознавания, полученные Ю.И. Журавлёвым в 70-х годах прошлого века. В частности, им была доказана возможность представления алгоритмов распознавания в виде композиции распознающего оператора и решающего правила [14], что позволило ввести разнообразные операции на множестве алгоритмов и перейти к рассмотрению алгебраических замыканий моделей алгоритмов.

Тогда же [15] в качестве модельного алгоритма для теоретических выкладок был предложен алгоритм вычисления оценок (ABO) [18,19]. Несмотря на то, что ABO во многом используется как некий универсальный язык описания алгоритмов распознавания, он может быть использован и использовался для решения прикладных задач самостоятельно. В частности, В.В. Рязановым предложен метод обучения ABO, основанный на оптимизации по параметрам, характеризующим представительность эталонных строк [33].

Понятие корректности алгоритма [14] возникло из практики проверки качества распознавания на независимой выборке. Алгоритм корректен для заданной выборки, если не делает на ней ошибок.

В [15] было введено понятие регулярности задачи распознавания и доказана теорема о существовании корректного алгоритма в алгебраическом замыкании ABO для любой регулярной задачи. Основным ограничением, которое накладывает определение регулярности, является неизморфность объектов контрольной выборки. В.Л. Матросо-вым позже было показано [25], что вероятность изоморфизма объектов в евклидовом пространстве равна нулю.

В [16] были получены первые оценки степени корректного полинома и рассмотрены вопросы его устойчивости.

Результаты Ю.И. Журавлёва получили дальнейшее развитие в работах его учеников. Основные исследования корректности алгебраических замыканий развивались в двух направлениях.

Во-первых, велись исследования по оценке степени корректного полинома для регулярных задач. Первые результаты были получены в работе [17]. Было показано, что степень полинома зависит от некоторой вычисляемой характеристики слагаемых, которая в дальнейшем для краткости будет называться высотой. Это разность минимальной среди оценок контрольных объектов за класс, к которому они принадлежат, и максимальной - за класс, к которому они не принадлежат. Идея максимизации высоты слагаемых является ключевой для настоящей диссертации.

Дальнейшие результаты по оцениванию степени корректного полинома были получены JI.B. Матросовым. В частности, им был доказан критерий корректности замыкания семейства ABO конечной степени [23]. На основании этого критерия была показана неполнота линейного замыкания модели ABO и квадратичного её замыкания, соответственно, JI.B. Матросовым [26] и Т.В. Плохониной [28]. Аналогичный результат был получен для общего случая: замыкание фиксированной степени не содержит корректного алгоритма для всех задач распознавания [27].

Также JI.B. Матросов улучшил верхние оценки степени и количества слагаемых для классического семейства ABO и его замыкания [24]. Кроме того, им было предложено обобщение ABO, так называемое, семейство ABO над упорядоченным полем G [27], в котором оценки принадлежности являются не числом, а элементом поля G. Было показано, что это семейство, расширенное с помощью дополнительных многоместных операций, содержит корректный алгоритм в линейном замыкании [27].

Неулучшаемая верхняя оценка степени корректного полинома была получена А.Г. Дьяконовым [13] с использованием введённых Л.В. Матросовым операторов разметки [22].

Параллельно К.В. Рудаковым была разработана теория универсальных и локальных ограничений [32]. В основе этой теории лежит идея, что одной прецедентной информации, или корректности на заданной выборке, недостаточно, чтобы гарантировать хорошее качество алгоритма. К.В. Рудаков предложил математический язык описания дополнительных ограничений на отображения, реализующие распознающий алгоритм, которые он назвал универсальными, в отличие от локальных прецедентных [29, 30]. В рамках этой теории были исследованы проблемы разрешимости задач и регулярности с точки зрения непротиворечивости локальных и универсальных ограничений; проблема полноты классов алгоритмов, т.е. разрешимости в его рамках всех регулярных задач [31].

Также К.В. Рудаковым были получены оценки минимальной степени полиномиальных семейств корректирующих операций [32]. Эти результаты отличаются от результатов А.Г. Дьяконова, поскольку К.В. Рудаков рассматривает распознающие операторы в виде композиции собственно распознающего оператора и корректирующей операции. Им же доказано, что неполнота семейства корректирующих операций не влечёт неполноты семейства алгоритмов, поскольку множество распознающих операторов может быть достаточно разнообразно само по себе.

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

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

1. Дивеев А.И., Северцев Н.А. Метод выбора оптимального варианта технической системы. М.: ВЦ РАН. 2003.

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

3. Докукин А.А. Индуктивный метод построения корректного алгоритма в алгебрах над моделью вычисления оценок // Ж. вычисл. матем. и матем. физ. 2003, т. 43, №8, стр. 1311-1315.

4. А.А. Dokukin. One Approach for the Optimization of Estimates Calculating Algoritms // International Journal „Information Theoris & Applications", 2003, vol. 10, pp. 465-467.

5. Докукин А.А. Об одном подходе к оптимизации АВО // Доклады 11-й Всероссийской конференции „Математические методы распознавания образов (ММРО-11)", 2003, стр. 68-70.

6. Dokukin А.А. Optimal method for constructing of AEC of maximal height in the context of pattern recognition // Pattern Recogn. and Image Analys. V. 15. No. 1. 2005. pp. 49-51.

7. Докукин А.А. О сложности поиска оптимального в некотором смысле АВО // Доклады 12-й Всероссийской конференции „Математические методы распознавания образов (ММРО-12)", 2005, стр. 299-302.

8. Докукин А.А. Об одном методе построения оптимального алгоритма вычисления оценок // Ж. вычисл. матем. и матем. физ.,-992006, т. 46, т, стр. 754-760.

9. Докукин A.A. О построении выборок для тестирования приближённых методов оптимизации алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ., 2006, т. 46, №5, стр. 978-983.

10. Dokukin A.A. Generilization of the Method for Constructing Maximum-Height Estimate-Calculating Algorithms to Recognition Problems // Pattern Recogn. and Image Analys. V. 16. No. 4. 2006. pp. 689-694.

11. Докукин A.A. Индуктивный поиск оптимального алгоритма вычисления оценок II Доклады 13-й Всероссийской конференции „Математические методы распознавания образов (ММРО-12)", 2007, стр. 122-124.

12. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976, 511 с.

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

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

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

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

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

18. Журавлёв Ю.И., Камилов М.М., Туляганов Ш.Е. Алгоритмы вычисления оценок и их применение Ташкент: „Фан", 1971.

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

20. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука. Д984.

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

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

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

24. Матросов B.JI. О вероятности изоморфизма пар допустимых объектов регулярных задач // Ж. вычисл. матем. и матем. физ., 1983, т. 23, т.

25. Матросов B.JI. О неполноте модели ABO // Ж. вычисл. матем. и матем. физ., 1983, т. 23, №2.

26. Матросов B.JI. Корректные алгебры алгоритмов распознавания ограниченной ёмкости: Дис. . докт. физ.-матем. наук. М. 1985.

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

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

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

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

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

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

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

34. Ryazanov V.V. Recognition Algorithms Based on Local Optimality Criteria // Pattern Recognition and Image Analysis. 1994. Vol.4, no.2. pp. 98-109.

35. Ryazanov V.V. About some approach for automatic knowledge extraction from precedent data // Proceedings of the 7th international conference „Pattern recognition and image processing", Minsk, May 21-23, 2003, vol. 2, pp. 35-40.

36. Обухов А.С., Рязанов В.В. Применение релаксационных алгоритмов при оптимизации линейных решающих правил // Доклады 10-й Всероссийской конференции „Математические методы распознавания образов (ММРО-Ю)", Москва, 2001, 102-104.

37. William Н. Wolberg and O.L. Mangasarian Multisurface method of pattern separation for medical diagnosis applied to breast cytology // Proceedings of the National Academy of Sciences, U.S.A., Volume 87, December 1990, pp. 9193-9196.