Оценки вероятности переобучения многомерных семейств алгоритмов классификации тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Ботов, Павел Валентинович

• Ботов, Павел Валентинович
• кандидат физико-математических наук
• 2011

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

Введение

1 Комбинаторная теория переобучения

1.1 Основные понятия и обозначения.

1.2 Постановка задачи.

2 Методы получения комбинаторных оценок вероятности переобучения

2.1 Послойный метод.

2.2 Метод индикаторов.

2.3 Метод Монте-Карло для решения задачи о семействе алгоритмов

3 Модельные семейства алгоритмов

3.1 Пара алгоритмов.

3.2 Монотонная и унимодальная цепи.

3.2.1 Монотонная цепь

3.2.2 Унимодальная цепь.

3.3 Многомерные симметричные модели.

3.3.1 Единичная окрестность.

3.3.2 Единичный гиперкуб.

3.3.3 Монотонная сеть.

3.3.4 Связка цепей.

3.3.5 Унимодальная сеть.

3.3.6 Мажорируемость многомерных семейств.

3.4 Несимметричные модели.

3.4.1 Монотонная несимметричная сеть.

3.4.2 Несимметричная связка цепей.

3.4.3 Унимодальная несимметричная сеть.

3.4.4 Мажорируемость многомерных семейств.

4 Применение модельных семейств алгоритмов в эксперименте

4.1 Аппроксимация семейств.

4.1.1 Аппроксимация унимодальной сети монотонной сетью удвоенной размерности.

4.1.2 Отбрасывание старших слоев семейства.

4.1.3 Сопоставление графиков <2е полученных в эксперименте с графиками <3£ от монотонных сетей.

4.1.4 Аппроксимация семейств, получаемых на практике, унимодальной несимметричной сетью.

4.1.5 Использование метода Монте-Карло для оценки вероятности переобучения семейств.

4.2 Метод минимизации предсказанного риска.

4.2.1 Бинарное решающее дерево

4.2.2 Эксперимент на реальных данных.

Введение диссертации (часть автореферата) на тему «Оценки вероятности переобучения многомерных семейств алгоритмов классификации»

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

Актуальность темы. Проблема переобучения является одной из важнейших при решении задач восстановления зависимостей по эмпирическим данным. [24] Она заключается в том, что частота ошибок на независимой контрольной выборке как правило, оказывается несколько выше частоты ошибок на обучающей выборке. Получением количественных оценок обобщающей способности, то есть вероятностного распределения величины этого смещения, занимается статистическая теория обучения. Многие подходы, разработанные в рамках этой теории, дают сильно завышенные оценки переобучения, поэтому их практическое применение не всегда приводит к улучшению качества восстановления зависимости. В комбинаторной теории надёжности обучения по прецедентам, предложенной К.В.Воронцовым [7, 8, 9, 10], показано, что для получения точных оценок необходимо* совместно учитывать свойства расслоения и связности семейства алгоритмов. Под расслоением семейства имеется в виду распределение алгоритмов по частоте ошибок, порождаемое заданной выборкой. Связность предполагает, что для каждого алгоритма в семействе найдётся множество похожих алгоритмов, отличающихся от него только на одном объекте выборки. Семейства, не обладающие свойствами расслоения и связности, могут переобучаться настолько сильно, что их практическое применение становится нецелесообразным.

Точные комбинаторные оценки вероятности переобучения были ранее получены для модельных семейств алгоритмов — монотонных и унимодальных цепей, интервалов, шаров и слоёв булева куба, обладающих тем или иным видом симметрии. Реальные семейства, порождаемые практическими задачами, как правило, имеют более сложную нерегулярную структуру, что препятствует получению точных комбинаторных оценок. Кроме того, согласно существующим в статистической теории обучения представлениям, размерность или число свободных параметров, как мера сложности семейства, определяющим образом влияет на его обобщающую способность. Поэтому актуальной теоретической проблемой является построение и изучение таких модельных семейств, которые обладали бы расслоением, связностью, размерностью, несимметричностью, то есть всеми ключевыми свойствами реальных семейств, и могли бы использоваться для их аппроксимации. Актуальной практической проблемой является применение оценок переобучения для повышения качества решения прикладных задач распознавания и классификации.

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

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

Методы исследования. Для получения оценок вероятности переобучения использовалась перестановочная вероятностная аксиоматика, комбинаторная теория надёжности обучения по прецедентам, элементы комбинаторики и теории вероятностей. Для проверки точности оценок проводились численные эксперименты на модельных данных методом Монте-Карло. Для сравнения предлагаемых методов классификации со стандартными проводились эксперименты на реальных данных из репозитория 11С1.

Положения, выносимые на защиту.

1. Методы получения комбинаторных оценок вероятности переобучения на основе послойного разложения семейства.

2. Оценки вероятности переобучения модельных семейств алгоритмов: связки цепей, монотонной сети, унимодальной сети и их несимметричных аналогов.

3. Методика повышения обобщающей способности итерационных методов обучения с помощью комбинаторных оценок вероятности переобучения.

Теоретическая значимость. Данная работа вносит существенный вклад в развитие комбинаторной теории надёжности обучения по прецедентам.

Метод послойного разложения семейства (глава 2) может быть применён для получения оценок вероятности переобучения в более широком классе семейств.

Практическая значимость. Метод минимизации предсказанного риска (глава 4) может быть применён для повышения качества классификации в широком классе итерационных методов обучения, включая решающие деревья, решающие списки, композиции логических закономерностей, алгоритмы вычисления оценок, и другие.

Апробация работы. Результаты работы докладывались, обсуждались и получили одобрение специалистов на следующих научных конференциях и семинарах:

• Всероссийская конференция «Математические методы распознавания образов» ММРО-14, 2009 г. [1];

• Международная конференция «Интеллектуализация обработки информации» ИОИ-8, 2010 г. [2];

• Всероссийская конференция «Математические методы распознавания образов» ММРО-15, 2011 г. [4];

• Результаты работы неоднократно докладывались на семинарах отдела Интеллектуальных систем ВЦ РАН.

Публикации по теме диссертации. Всего публикаций по теме диссертации — четыре, в том числе в изданиях из Списка, рекомендованного ВАК РФ — одна [3].

Краткое содержание работы по главам. Работа состоит из четырёх глав.

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

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

В третьей главе вводятся различные модельные семейства, начиная с простейшего, состоящего из двух алгоритмов, и заканчивая унимодальной несимметричной сетью. Для всех рассмотренных модельных семейств доказываются соответствующие теоремы о вероятности переобучения семейства и о вероятности выбора алгоритма из слоя семейства. Все теоремы и алгоритмы прошли проверку на корректность численных результатов с аналогичными результатами, полученными методом Монте-Карло.

В четвёртой главе предлагается методика аппроксимации оценок вероятности переобучения реальных семейств точными оценками вероятности переобучения модельных семейств, в частности, унимодальной несимметричной сетью. А также вводится метод минимизации предсказанного риска (МПР) позволяющий повысить обобщающую способность итерационных методов обучения, в частности, решающих деревьев, с помощью комбинаторных оценок вероятности переобучения.

Благодарности Автор выражает глубокую признательность научному руководителю д. ф.-м. н. Константину Вячеславовичу Воронцову за постановку задачи и постоянную поддержку в ходе исследований. А также Александру Фрею и Андрею Ивахненко за плодотворные дискуссии.

Заключение диссертации по теме «Теоретические основы информатики», Ботов, Павел Валентинович

Основные результаты диссертации:

1. Предложены и использованы методы вывода комбинаторных оценок вероятности переобучения, основанные на теоремах о послойном разложении семейства и группировки эквивалентных индикаторов;

2. Выведены оценки вероятности переобучения модельных семейств алгоритмов: связки цепей, монотонной сети, унимодальной сети их несимметричных аналогов;

3. Предложен метод аппроксимации оценок вероятности переобучения реальных семейств точными оценками вероятности переобучения модельных семейств;

4. Предложена методика применения оценок вероятности переобучения для повышения обобщающей способности итерационных методов обучения, в частности, решающих деревьев. Методика основана на выборе шага обучения с учётом рисков, связанных с переобучением.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Ботов, Павел Валентинович, 2011 год

1. Ботов П. В. Точные оценки вероятности переобучения для монотонных и унимодальных семейств алгоритмов // Докл. всеросс. конф. Математические методы распознавания образов-14. — М.: МАКС Пресс, 2009.— С. 7-10.

2. Ботов П. В. Точные оценки вероятности переобучения для несимметричных многомерных семейств алгоритмов // Докл. межд. конф. Интеллектуализация обработки информации, ИОИ-8. — М.: МАКС Пресс, 2010. — С. 20-23.

3. Botov P. V. Exact estimates of the probability of overfitting for multidimensional modeling families of algorithms // ISSN 1054-6618, Pattern Recognition and Image Analysis, 2010, Vol. 20, No. 4, pp. 52-65. — Pleiades Publishing, Ltd., 2010.

4. Ботов П. В. Уменьшение вероятности переобучения итерационных методов статистического обучения // Докл. всеросс. конф. Математические методы распознавания образов-15. — М.: МАКС Пресс, 2011.— С. 44-47.

5. Воронцов К. В. Точные оценки вероятности переобучения // Доклады РАН, 2009, Vol. 429, No. 1, стр. 15-18. — М.: Наука

6. Воронцов К. В. Комбинаторный подход к проблеме переобучения // Всеросс. конф. Математические методы распознавания образов-14— М.: МАКС Пресс,—2009,—18-21

7. Воронцов К. В. Комбинаторная теория надёжности обучения по прецедентам // Диссертация на соискание учёной степени д.ф.-м.н., М.: ВЦ РАН,-2010

8. Graham R. L., Knuth D. E., Patashnik 0. Concrete Mathematics: A Foundation for Computer Science // ISBN 0-201-55802-5, Massachusetts: Addison-Wesley-Professional, 1994.

9. Asuncion A., Newman D.J. UCI Machine Learning Repository // University of California, Irvine, School of Information and Computer Sciences, 2007.

10. Дьяконов А. Г. Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab (практикум на ЭВМ кафедры математических методов прогнозирования) // М.: МАКС Пресс, 2010.

11. Донской В. И., Баъита А. И. Дискретные модели принятия решений при неполной информации. — Симферополь: Таврия, 1992.— С. 166.

12. Breslow L. A., Aha D. W. Simplifying decision trees: a survey // Knowledge Engineering Review.—1997.—Vol. 12, no. 1,—Pp. 1-40.

13. Quinlan J. Induction of decision trees // Machine Learning.—1986.—Vol. 1, no. l.-Pp. 81-106.

14. Ивахненко А. А. Комбинаторные оценки вероятности переобучения и их применение в логических алгоритмах классификации // Диссертация на соискание учёной степени к.ф.-м.н., — 2010

15. Dubner Р. N. Statistical tests for feature selection in KORA recognition algorithms // Pattern Recognition and Image Analysis.—1994.— Vol. 4, no. 4.— P. 396.

16. Schapire R. E., Singer Y. Improved boosting using confidence-rated predictions // Machine Learning —1999.—Vol. 37, no. 3.—Pp. 297-336.

17. Breiman L. Technical note: Some properties of splitting criteria // Machine Learning.—1996—Vol: 24 —Pp. 41-47.

18. Prey A. I. Accurate estimates of the generalization ability for symmetric sets of predictors and randomized learning algorithms // Pattern Recognition and Image Analysis.-2010,— Vol. 20, No. 3. — Pp. 241-250.

19. Фрей А. И. Точные оценки вероятности переобучения для симметричных семейств алгоритмов // Докл. всеросс. конф. Математические методы распознавания образов-14. — М.: МАКС Пресс, 2009. — С. 66-69.

20. Толстихин И. О. Вероятность переобучения плотных и разреженных семейств алгоритмов // Докл. межд. конф. Интеллектуализация обработки информации, ИОИ-8. — М.: МАКС Пресс, 2010. — С. 83-86.

21. Вапник В. Н., Червоненкис А. Я. // Теория распознавания образов. М.: Наука, 1974.

22. Ваппик В. Н. Восстановление зависимостей по эмпирическим данным. // М.: Наука, 1979.

23. Хайкин С. Нейронные сети. Полный курс. // 2-е изд., испр.: Пер. с англ.— М.: ООО «И. Д. Вильяме», 2006. —1104 с.

24. Jackson J., Shamir Е., Shwartzman С. Learning with queries corrupted by classification noise // Discrete Applied Mathematics.—1999.— Vol. 92, no. 2-3.— Pp. 157-175.

25. Kearns M. Efficient noise-tolerant learning from statistical queries // Proceedings of the 25-th annual ACM symposium on Theory of computing, May 16-18, 1993, San Diego, California, United States —ACM, 1993.—Pp. 392-401.

26. Kearns M. Efficient noise-tolerant learning from statistical queries // Journal of the ACM.-1998.—Vol. 45, no. 6.—Pp. 983-1006.

27. Jackson J. On the efficiency of noise-tolerant рас algorithms derived from statistical queries // Annals of Mathematics and Artificial Intelligence. — 2003.— Vol. 39, no. 3.-Pp. 291-313.

28. Langford J. Quantitatively Tight Sample Complexity Bounds: Ph.D. thesis / Carnegie Mellon Thesis — 2002.

29. Langford J. Tutorial on practical prediction theory for classification // // Journal of Machine Learning Research —2005—Vol. 6—Pp. 273-306.

30. Langford J., Blum A. Microchoice bounds and self bounding learning algorithms // Computational Learing Theory—1999—Pp. 209-214.

31. Shawe-Taylor J., Bartlett P. L. Structural risk minimization over data-dependent hierarchies // IEEE Trans, on Information Theory —1998—Vol. 44, no. 5.—Pp. 1926-1940.

32. Herbrich R., C.Williamson R. Algorithmic luckiness // Journal of Machine Learning Research—2002 —no. 3—Pp. 175-212.

33. Philips P. Data-Dependent Analysis of Learning Algorithms: Ph.D. thesis / The Australian National University, Canberra.— 2005.

34. Бушмапов О. H., Дюкова Е. В., Журавлёв Ю. И., Кочетков Д. В., Рязанов В. В. Система анализа и распознавания образов // Распознавание, классификация, прогноз 2,-1989,-250-273.

35. Загоруйко Н. Г. Прикладные методы анализа данных и знаний // Новосибирск: ИМ СО РАН,- 1999.

36. Загоруйко Н. Г., Елкина В. Н., Лбов Г. С. Алгоритмы обнаружения эмпирических закономерностей // Новосибирск: Наука,—1985.

37. Кочедыков Д. А., Ивахненко А. А., Воронцов К. В. Система кредитного скоринга на основе логических алгоритмов классификации // Математические методы распознавания образов-12 М.: МАКС Пресс,— 2005,— 349-353.

38. Кочедыков Д. А., Ивахненко А. А., Воронцов К. В. Применение логических алгоритмов классификации в задачах кредитного скоринга и управления риском кредитного портфеля банка // Математические методы распознавания образов-13 М.: МАКС Пресс,-2007,—484-488.

39. Лбов Г. С. Методы обработки разнотипных экспериментальных данных // Новосибирск: Наука,—1981.

40. Wai-Ho Au, Keith С. С. Chan, Xin Yao A novel evolutionary data mining algorithm with applications to churn prediction // IEEE Trans. Evolutionary Computation—Vol.7—no. 6—2003,—Pp. 532-545.