Локальные базисы в алгебраическом подходе к проблеме распознавания

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

Оглавление

Введение
1 Локальные базисы и методы их построения
1.1 Задачи обучения по прецедентам
1.2 Оптимизационный и алгебраический подходы
1.3 Оптимизационные задачи построения локальных базисов
1.4 Проблемно-независимые и проблемно-зависимые подзадачи
2 Решение задач оптимизации при построении локальных базисов
2.1 Линейные корректирующие операции
2.1.1 Задача восстановления регрессии
2.1.2 Задача классификации
2.2 Полиномиальные корректирующие операции
ч'У'-
2.2.1 Задача восстановления регрессии . т i
2.2.2 Задача классификации
2.3 Монотонные корректирующие операции
2.3.1 Оптимизация базиса при построении корректного алгоритма
2.3.2 Оптимизация базиса при фиксированном числе операторов
2.3.3 Задача классификации
2.3.4 Задача восстановления регрессии
2.3.5 0 методах построения монотонных корректирующих операций
2.3.6 Монотонные корректирующие операции в задаче классификации
2.3.7 Монотонные корректирующие операции в задаче восстановления регрессии
2.3.8 Некоторые алгоритмы монотонизации выборок
3 Проблемно-зависимые подзадачи и язык SOIL
3.1 Введение в язык алгоритмических суперпозиций

3.2 Модель данных SDL
3.2.1 Терминология
3.2.2 Массивы
3.2.3 Методы и алгоритмы
3.3 Некоторые элементы языка SBL
3.4 Обоснование достаточности модели данных для решения прикладных задач
3.4.1 Метод наименьших квадратов
3.4.2 Метод построения линейной разделяющей поверхности
3.4.3 Вычисление дефекта набора алгоритмических операторов
3.4.4 Метод монотонной интерполяции
3.4.5 Метод монотонизации выборки
3.4.6 Метод нормировки признаков
3.4.7 Метод генерации признаков по функции расстояния
3.4.8 Метод упорядочивания объектов по убыванию расстояний
3.4.9 Метод генерации метрик по признакам
3.4.10 Метод ближайших соседей
3.4.11 Метод таксономии
3.4.12 Метод вычисления расстояния между признаками
3.5 Примеры описания алгоритмических суперпозиций
3.5.1 Абстрактные методы с алгоритмами стандартной структуры
3.5.2 Линейная коррекция в задаче восстановления регрессии
3.5.3 Монотонная коррекция в задаче восстановления регрессии
3.5.4 Полиномиальная коррекция в задаче классификации
4 Заключение
Список рисунков
Литература

Диссертация выполнена в рамках алгебраического подхода к проблеме распознавания, развиваемого школой академика РАН Ю.И. Журавлёва. Целью работы является создание специальных методов, необходимых для эффективного использования конструкций алгебраического подхода при решении прикладных задач распознавания, классификации и прогнозирования. Данные методы ориентированы на непосредственное практическое применение и обеспечивают требуемое качество распознавания при относительно невысокой сложности алгоритмов. Рассматривается новая для алгебраического подхода задача построения локальных базисов, приводящая к построению алгоритмических операторов путём решения последовательности оптимизационных задач. Предлагается общая методология решения прикладных задач, основанная на использовании специального языка для описания настраиваемых алгоритмических суперпозиций.
Введение
Методы распознавания образов и восстановления зависимостей по неполным, неточным и разнородным данным используются при создании интеллектуальных информационных и аналитических систем в самых разных прикладных областях. Предпосылкой для их применения являются сбор и первичная обработка данных, в результате которых формируются описания объектов, ситуаций или явлений предметной области. Вслед за этим возникают задачи классификации объектов, восстановления неизвестных значений некоторых их свойств, прогнозирования их состояний, и т. д. Во всех этих случаях требуется строить алгоритмы, преобразующие исходную (начальную) информацию об объектах в выходную (финальную) информацию об этих же объектах.
Как правило, в задачах такого класса наличие некоторой зависимости между начальными и финальными информациями представляется несомненным, однако она может оказаться сложной и неявной, а предметная область — недостаточно формализованной, чтобы построить её адекватную модель. В таких случаях зави-

Опираясь на теорему 1, докажем, что при некоторых не слишком сильных ограничениях на модель 9Я° процесс построения корректного алгоритма сходится за конечное число шагов.
Теорема 2 (О сходимости). Пусть модель ЗЛ° такова, что для любой пары (],к) є <0>2, j Ф к, найдётся алгоритмический оператор В Є 9Л°, для которого В(хф < В(хф). Тогда при произвольном Вг Є потребуется не более р» = = С(Ві) +1 операторов, чтобы (д(Р(Ві, Д2, , ВР,)) = 0 при некоторой И Є $м.
Доказательство. Предположим, что оператор Вх уже выбран. Будем последовательно строить операторы _В2, В3
сэ(Р(в1
Теорема доказана.
Более сильная оценка числа операторов получается в случае, когда модель 9Я° допускает построение алгоритмического оператора, воспроизводящего правильный порядок на произвольных та парах одновременно. Соответствующая теорема доказывается аналогично.
Теорема 3 (О сходимости). Пусть модель 9Л° такова, что для любого множества та пар, т 1,
{(Ім к) € О2 | ф ф кг, і = 1
найдётся алгоритмический оператор В Є 2Д°, для которого ни одна из этих пар не является дефектной. Тогда при произвольном Вх Є ЗЯ° потребуется не более р* = [<2(і?і)| +1 алгоритмических операторов, чтобы ((Р(Вх