Публикация:Воронцов 2010 Комбинаторная теория

Материал из MachineLearning.

Версия 15:25, 4 февраля 2010

Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр РАН, 2010. — 271 с.

 @phdthesis{voron10doct,
   author = "Воронцов, К. В.",
   title = "Комбинаторная теория надёжности обучения по прецедентам: 
           Дис. док. физ.-мат. наук: 05-13-17",
   school = "Вычислительный центр РАН",
   pages = "271",
   url = "http://www.machinelearning.ru/wiki/images/b/b6/Voron10doct.pdf",
   year = "2010",
   language = russian
 }

Данная диссертационная работа является теоретическим исследованием по теории статистического обучения (statistical learning theory, SLT). Предлагается комбинаторный подход, позволяющий получать точные оценки обобщающей способности методов обучения по прецедентам. Отличительными особенностями комбинаторного подхода являются:

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

Результаты, выносимые на защиту

1. Слабая вероятностная аксиоматика, основанная на единственном вероятностном предположении -- о независимости наблюдений в конечной выборке. Общая постановка задач эмпирического предсказания.
2. VC-оценки вероятности переобучения, учитывающие степень некорректности метода обучения.
3. Методика эмпирического измерения факторов завышенности VC-оценок вероятности переобучения.
4. Метод получения точных оценок вероятности переобучения, основанный на выделении множеств порождающих и запрещающих объектов для каждого алгоритма в семействе.
5. Рекуррентный алгоритм вычисления точных, верхних и нижних оценок вероятности переобучения.
6. Блочный метод вычисления точных оценок вероятности переобучения.
7. Точные оценки вероятности переобучения для ряда модельных семейств алгоритмов: слоя и интервала булева куба, монотонных и унимодальных цепочек, единичной окрестности.
8. Оценка вероятности переобучения, учитывающая профиль расслоения и связности семейства алгоритмов.
9. Точные оценки полного скользящего контроля для метода ближайшего соседа, выражающиеся через профиль компактности выборки.
10. Верхние оценки полного скользящего контроля для семейства монотонных алгоритмов, выражающиеся через профиль монотонности выборки.

См. также

• Воронцов, Константин Вячеславович — страница участника
• Теория вычислительного обучения
• Слабая вероятностная аксиоматика
• Обобщающая способность
• Переобучение
• Расслоение и сходство алгоритмов (виртуальный семинар)