Минимаксный подход к построению оптимального классификатора методом SVM с одновременным выбором оптимального подпространства признаков

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

ОГЛАВЛЕНИЕ

Введение

ГЛАВА 1. Проблема сокращения размерности в задаче обучения классификации

1.1 Постановка задачи обучения классификации

1.2 Задача сокращения размерности

1.3 Методы извлечения признаков

1.3.1 Метод главных компонент

1.3.2 Метод центроидпых компонент

1.3.3 Методы экстремальной группировки параметров

ГЛАВА 2. Современное состояние проблемы выбора признаков в задачах классификации
2.1 Основные постановки задачи выбора признаков
2.1.1 Виды оценок качества подмножества признаков
2.2 Методы оценки вероятности ошибки распознавания
2.2.1 Resubstitution метод
2.2.2 Holdout метод
2.2.3 Cross-validation метод
2.2.4 Jackknife метод
2.2.5 Bootstrap метод
2.3 Вычислительная сложность задачи выбора признаков
2.4 Обзор алгоритмов выбора признаков
2.4.1 Организация пространства поиска
2.4.2 Способ движения в пространстве поиска
2.4.3 Описание основных алгоритмов выбора признаков

ГЛАВА 3. Алгоритмы выбора признаков на основе метода опорных векторов
3.1 Метод опорных векторов
3.2 Алгоритмы выбора признаков на основе БУМ
3.2.1 Градиентный алгоритм Вапника и др
3.2.2 Алгоритм выбора признаков для задачи БУМ в многокритериальной постановке
ГЛАВА 4. Минимаксный подход к построению оптимального классификатора методом БУМ с одновременным выбором оптимального подпространства признаков
4.1 Дискретная постановка задачи выбора признаков
4.2 Непрерывная постановка задачи выбора признаков
4.3 Выпуклая минимаксная постановка задачи выбора признаков
4.4 Седловая постановка задачи выбора признаков
4.5 Алгоритм поиска седловой точки
4.5.1 Вычисление параметра шага алгоритма а
4.5.2 Быстрое вычисление проекций
4.6 Псевдокод еедлового алгоритма выбора признаков
ГЛАВА 5. Экспериментальные результаты
5.1 Схема тестирования алгоритма выбора признаков
5.2 Распознавание искусственных данных
5.3 Распознавание звуков английского языка
5.4 Диагностика заболевания раком женской груди
5.5 Эффективность вычисления проекций методом Дейкстры
5.6 Анализ результатов и направление дальнейшей работы
Заключение

Литература
Приложение А Доказательство предложения
Приложение В Алгоритм недифференцируемой оптимизации решения минимаксной задачи
Приложение С Алгоритм выбора признаков в задаче построения БУМ
регрессии

му закону, обучающая выборка содержит одинаковое количество элементов первого и второго класса и для классификации используется линейная дискриминантная функция. В работе [78] рассмотрена задача нахождения минимального объема выборки, чтобы ВЫПОЛНЯЛОСЬ соотношение Р(7) <1,5 Рос, для нормально распределенных классов с единичной матрицей ковариации. Приведены результаты для различных алгоритмов обучения. Например, для алгоритма /-ближайших соседей и Р = 0, 01 необходим объем выборки равный 1,6п, где n-размерность пространства, которому принадлежат элементы выборки.
Существует ряд методов для оценки вероятности ошибки распознавания. Ниже рассмотрены наиболее распространенные: resubstitution, holdout, cross-validation, jackknife, bootstrap. Краткое описание данных методов следующее: resubstitution: оценка вычисляется на тех же элементах обучающей выборки, на которых производилось обучение. holdout: выборка разбивается на две части: обучение производится по одной части, а оценка вычисляется по другой части выборки. cross-validation: вычисляются holdout оценки для различных регулярных разбиений выборки, затем полученные оценки усредняются. jackknife: предполагается, что математическое ожидание оценки истинного значения Р имеет вид: Р +- + ®г + о {ji), где /-размер выборки. Комбинируя оценки, полученные по всей выборке и подвыборкам длины (I — 1), получают оценку с математическим ожиданием Р -Ьут + о(р), без члена 41.
bootstrap: исходная обучающая выборка длины I выступает в качестве генеральной совокупности. Каждый элемент генеральной совокупности имеет вероятность равную 1/1. Оценка вычисляется на основе нескольких выборок, извлекаемых из генеральной совокупности.
Этим методам посвященно большое количество публикаций, однако автору не встретилось четких теоретических обоснований по применению их