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

• Автор: Докукин, Александр Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 102 с. : ил.

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

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

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

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

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

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

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

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

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

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

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

5.2 Жадный алгоритм
5.3 Метод покоординатного подъема
5.4 Генетический алгоритм

5.5 Тестирование методов
6 Реализация метода распознавания на основе алгоритмов поиска АВО максимальной высоты
6.1 Оптимальная схема
6.2 Приближённый метод, программная реализация
6.3 Результаты тестирования
Список литературы

Данная работа посвящена поиску алгоритмов вычисления оценок для задач распознавания, классификации и прогнозирования по прецедентам, обладающих некоторыми экстремальными свойствами, и построения корректных и высокоточных алгоритмов в виде полиномов над ними.
Основой для исследований послужили результаты теории распознавания, полученные Ю.И. Журавлёвым в 70-х годах прошлого века. В частности, им была доказана возможность представления алгоритмов распознавания в виде композиции распознающего оператора и решающего правила [14], что позволило ввести разнообразные операции на множестве алгоритмов и перейти к рассмотрению алгебраических замыканий моделей алгоритмов.
Тогда же [15] в качестве модельного алгоритма для теоретических выкладок был предложен алгоритм вычисления оценок (АВО) [18,19]. Несмотря на то, что АВО во многом используется как некий универсальный язык описания алгоритмов распознавания, он может быть использован и использовался для решения прикладных задач самостоятельно. В частности, В.В. Рязановым предложен метод обучения АВО, основанный на оптимизации по параметрам, характеризующим представительность эталонных строк [33].
Понятие корректности алгоритма [14] возникло из практики проверки качества распознавания на независимой выборке. Алгоритм корректен для заданной выборки, если не делает на ней ошибок.

Действительно, на каждом шаге получается не более ю — к + 1 задач, в каждой из которых исключается один признак. Кроме того, в каждой из полученных задач последовательно исключаются объекты.
В случае, если число объектов равно размеру окна, сложность алгоритма равна 1, не зависимо от количества признаков:
Кроме того силу теоремы 4 имеется оценка для двумерного случая:
Используя оценки (4.6)-(4.8) получим первое утверждение теоремы с помощью индукции. При п = 2 утверждение теоремы справедливо в силу (4.8). Предположим, что оно верно при всех п — 2 N — 1 и докажем его при п = N.
В силу выражения (4.6) и предположения индукции (4.4) при п
1 N1 верна следующая оценка:
В свою очередь сумму, находящуюся в правой части выражения можно оценить , используя известные свойства выражений вида
7(п, к, к) = 1.
(4.7)
7(2, го, к) — го — к + 1.
(4.8)
ги—к
7(77, ги, к) < ^7(77— 1,к + г,к) <
Е£=1 [21]: