Комбинаторные оценки полного скользящего контроля и методы обучения монотонных классификаторов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Гуз, Иван Сергеевич

  • Гуз, Иван Сергеевич
  • кандидат физико-математических науккандидат физико-математических наук
  • 2011, Москва
  • Специальность ВАК РФ05.13.17
  • Количество страниц 113
Гуз, Иван Сергеевич. Комбинаторные оценки полного скользящего контроля и методы обучения монотонных классификаторов: дис. кандидат физико-математических наук: 05.13.17 - Теоретические основы информатики. Москва. 2011. 113 с.

Оглавление диссертации кандидат физико-математических наук Гуз, Иван Сергеевич

Введение.

Глава 1. Монотонные классификаторы.

1.1. Задача обучения по прецедентам.

1.2. Ограничения монотонности.

1.3. Монотонные корректирующие операции.

1.4. Проблема переобучения.

Глава 2. Оценки ССУ для монотонных классификаторов.

2.1. Методы вычисления оценок ССУ.

2.1.1 Оценка ССУ в худшем случае.

2.1.2 Учет структуры монотонного классификатора.

2.2. Одномерная выборка.

2.2.1 Состав множества безошибочных выборок.

2.2.2 Мощность множества безошибочных выборок.

2.2.3 Алгоритм расчета оценок ССУ.

2.2.4 Фильтрация шумовых объектов.

2.3. Многомерная выборка.

2.3.1 Метод обучения монотонных классификаторов.

2.3.2 Гибридная оценка ССУ.

2.3.3 Экспериментальная проверка точности гибридной оценки.

Глава 3. Методы построения монотонных композиций классификаторов.

3.1. Независимое обучение базовых алгоритмов.

3.1.1 Принципы построения монотонных композиций.

3.1.2 Результаты экспериментов.

3.2. Монотонный бустинг.

3.2.1 Наивный метод.

3.2.2 Экспериментальная оценка качества наивного метода.

3.2.3 Минимизация комбинаторной оценки ССУ.

3.2.4 Экспериментальная оценка качества метода минимизации комбинаторной оценки ССУ.

3.2.5 Минимизация гибридной оценки ССУ.

3.2.6 Экспериментальная оценка качества метода минимизации гибридной оценки ССУ.

Рекомендованный список диссертаций по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК

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

Проблема синтеза алгоритмов на основе обучения по конечным выборкам прецедентов и изучения их качества на всем множестве прецедентов является одним из важнейших вопросов теории обучения по прецедентам. В качестве прецедентов рассматриваются пары: объект, описанный набором признаков, и класс, к которому принадлежит объект. Задача классификации, являющаяся подклассом более общего класса задач обучения по прецедентам, состоит в том, чтобы на основании известного конечного множества прецедентов научиться определять априори неизвестную принадлежность объектов к классам. Обучение или настройка параметров алгоритма на обучающей выборке происходит путем решения задачи численной оптимизации. Практика показала, что при решении прикладных задач классификации очень часто возникает ситуация, когда ни один из существующих алгоритмов в отдельности не решает задачу с достаточным качеством. В таких случаях, согласно алгебраическому подходу [18, 19, 20] к проблеме распознавания, развиваемого школой академика РАН* Ю.И. Журавлева, пытаются учесть сильные стороны каждого отдельного алгоритма за счет построения из них некоторой композиции.

В работе рассматривается проблема повышения качества классификации при помощи построения алгоритмических композиций для задач, описываемых некоторой выборкой объектов, где каждый объект принадлежит одному из двух непересекающихся классов, -1 и +1. Подобные задачи встречаются на практике очень часто и носят название задач бинарной классификации. Задачи, в которых объект описывается большим числом классов, могут быть сведены к последовательному решению нескольких задач бинарной классификации. Предполагается, что существует набор базовых алгоритмов, причем каждый базовый алгоритм определяет для каждого объекта не только его класс, но и оценку принадлежности классу +1. Этим свойством обладают многие известные алгоритмы классификации, например, байесовские классификаторы [30], нейронные сети [X], логистическая регрессия [25], деревья решений [27] и другие. В байесовских классификаторах оценка принадлежности интерпретируется как апостериорная вероятность того, что объект принадлежит классу +1. Однако в данной работе никаких предположений о вероятностной природе данных не делается, и оценки принадлежности интерпретируются в более широком смысле. Чем больше оценка, тем с большей уверенностью можно утверждать, что объект принадлежит классу +1.

В качестве алгоритмической композиции в работе рассматривается монотонная корректирующая операция [22], которая является монотонным классификатором в пространстве оценок принадлежности. Использование монотонного классификатора оправдано естественным требованием, что если для одного объекта оценки принадлежности не меньше, чем для другого, то и оценка принадлежности первого объекта, рассчитанная с помощью композиции, должна быть не меньше, чем для второго. Монотонные корректирующие операции образуют более широкое семейство по сравнению с выпуклыми (линейными с неотрицательными коэффициентами), используемыми в методах голосования, в частности, в бустинге. Это позволяет точнее настраиваться на данные и использовать существенно меньшее число базовых алгоритмов, но одновременно с этим, повышает риск переобучения.

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

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

Работа состоит из трех глав.

В первой главе формализуется задача обучения по прецедентам, и описываются прикладные области применения монотонных алгоритмов классификации, называемых в работе монотонными классификаторами. Описывается алгебраический подход к решению задач бинарной классификации с помощью построения монотонных корректирующих операций над базовыми алгоритмами. Вводится понятие метода обучения на объектах с весами. Формализуется понятие риска переобучения с помощью определения функционала полного скользящего контроля (complete cross-validation, CCV).

Вторая глава состоит из двух частей.

В первой части доказываются полиноминально вычислимые верхние и нижние оценки CCV для семейства монотонных алгоритмов и одномерной обучающей выборки, в которой объекты описываются единственным вещественно-значным признаком. Доказанные оценки в явном виде включают в себя зависимость от весов объектов, используемых при настройке монотонного алгоритма. Используя эту зависимость, численными методами решается задача минимизации верхней оценки CCV с помощью обнуления весов некоторых объектов. Результаты вычислительных экспериментов показали, что минимум верхней оценки полного скользящего- контроля в этом случае достигается при обнулении весов всех объектов, нарушающих монотонность выборки.

Во второй части рассматривается многомерная обучающая выборка, в которой объекты описываются конечным множеством вещественнозначных признаков. Для этого случая предлагается вычислительно эффективный метод построения монотонного классификатора, минимизирующего количество ошибок на обучающей выборке. Доказывается новая комбинаторная оценка CCV, названная гибридной, для семейства монотонных алгоритмов, учитывающая как свойства задачи, так и особенности используемого семейства. Основное достоинство полученной оценки в том, что она применима к любым обучающим выборкам, причем для монотонных обучающих выборок значение совпадает с фактическим значением функционала ССУ. Предложенная оценка на обучающих выборках размерности больше двух оказалась точнее оценок, полученных ранее другими авторами.

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

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

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

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

Для уменьшения риска переобучения описывается второй подход, основанный на минимизации комбинаторной оценки ССУ, доказанной в работе К. В. Воронцова [10], при последовательном добавлении базовых алгоритмов в композицию. Недостатком этого подхода является относительно низкое качество классификации построенной с его помощью монотонной композиции.

Третий подход, основан на идее построения базовых алгоритмов таким образом, чтобы в пространстве их оценок принадлежности объектов к классу + 1 гибридная оценка полного скользящего контроля монотонного классификатора, была минимальна. Для этого построение всех базовых алгоритмов происходит одновременно, причем каждый базовый алгоритм настраивается на объектах обучающей выборки с уникальными для него весами. Поэтому, настраиваемыми параметрами является матрица Ьхт весов объектов обучающей выборки, где т - количество алгоритмов в композиции.

Метод минимизации гибридной оценки ССУ основан на принципах метода градиентного спуска, реализованных для дискретного случая. Изначально вся матрица весов объектов инициализируются произвольными значениями из отрезка [1,2]. Аналитически оценивается вклад каждого объекта генеральной выборки в величину текущего значения гибридной оценки ССУ. Эвристически оценивается направление изменения весов для каждого объекта, которое привело бы к максимальному уменьшению гибридной оценки ССУ, если бы веса всех остальных объектов были бы фиксированы. Используя величину вклада объекта в гибридную оценку ССУ в качестве модуля вектора изменения и рассчитанное направление изменения, проводится итеративный пересчет весов. Процедура останавливается, когда не удается улучшить гибридную оценку ССУ больше, чем заданное число итераций подряд.

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

Благодарности

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

Похожие диссертационные работы по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК

Заключение диссертации по теме «Теоретические основы информатики», Гуз, Иван Сергеевич

Заключение

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

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

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

Таким образом, основные результаты диссертационной работы следующие:

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

2. Предложен вычислительно эффективный метод построения оптимального монотонного классификатора, минимизирующего эмпирический риск.

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

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

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

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

2. Воронцов К. В. Комбинаторные обоснования обучаемых алгоритмов. ЖВМ и МФ. 2004. Т. 44, № 11. С. 2099-2112.

3. Воронцов К. В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания. ЖВМ и МФ. 2000. Т. 40 № 1. С. 166-176

4. Воронцов К.В. Качество восстановления зависимостей по эмпирическим данным // Математические методы распознавания образов—VII: Тез. докл. М. 1995.

5. Воронцов К.В. О проблемно-ориентированной оптимизации базисов задач распознавания // ЖВМ и МФ. 1998. Т. 38, № 5. С. 870-880.

6. Воронцов К.В. О синтезе проблемно-ориентированных базисов в задачах распознавания // Математические методы распознавания образов-УШ: Тез. докл. М. 1997. ' 4

7. Воронцов К.В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания //ЖВМ и МФ.

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

9. Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики. — 2004. —N0. 13. — С. 5— 36.

10. Воронцов К. В. Локальные базисы в алгебраическом подходе к проблеме распознавания — Диссертация на соискание ученой степени к.ф.-м.н., М.: ВЦ РАН— 1999.

11. Гуз И. С. Гибридные оценки полного скользящего контроля для монотонных классификаторов. // Докл. всеросс. конф. Математические методы распознавания образов-15. — М.: МАКС Пресс, 2011. — С. 98-103.

12. Гуз И. С. Конструктивные оценки полного скользящего контроля для пороговой классификации // Математическая биология и биоинформатика. — Т.6. — В.2. —2011. http://www.matbio.org/2011/Guz2011(6173).pdf

13. Гуз И. С. Минимизация эмпирического риска при построении монотонных композиций классификаторов // Труды МФТИ -2011.- Т.З, №3 (11) С. 115121.

14. Гуз И. С. Нелинейные монотонные композиции классификаторов // Докл. всеросс. конф. Математические методы распознавания образов-13. — М:: МАКС Пресс, 2007. — С. 111-114.

15. Гуз И. С. Обобщающая способность монотонных композиций классификаторов // Докл. межд. конф. Интеллектуализация обработки информации, ИОИ-7, — Симферополь. 2008, — С. 75-77.

16. Гуз И.С. Исследование обобщающей способности семейства монотонных функций // Моделирование и обработка информации: Сб.ст./Моск.физ.-тех. ин-т. М., 2008. - С. 114-120.

17. Журавлёв Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации*// Проблемы кибернетики. — 1978. — Т. 33. — С. 5-68.

18. Журавлёв Ю.И., Рудаков К.В. Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. М. Наука. 1987. С. 187-198.

19. Журавлёв Ю. И. Корректные алгебры над множеством некорректных (эвристических) алгоритмов. I-III // Кибернетика. 1977. №4 С. 14-21. 1997 №6 . С. 21-27. 1978. №2 С. 35-43.

20. Махина Г. А. Оценка обобщающей способности для монотонных алгоритмов классификации // 16-я международная конференция. Проблемы теоретической кибернетики. Нижний Новгород, 20-25 июня 2011

21. Рудаков К.В. Монотонные и унимодальные корректирующие операции для алгоритмов распознавания // Математические методы распознавания обра-зов-VII: Тез. докл. М. 1995.

22. Рудаков К.В., Воронцов К.В. О методах оптимизации и монотонной коррекции в алгебраическом» подходе к проблеме распознавания. Доклады РАН. 1999. Т. 367, №3. С. 314-317.

23. Рудаков К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания. — Диссертация на соискание учёной степени д.ф.-м.н., М.: ВЦ РАН. — 1992.

24. Agresti A. Building and applying logistic regression models. An Introduction to Categorical Data Analysis. Hoboken, New Jersey: Wiley, p. 138.

25. Blake C., Merz C. UCI repository of machine learning Department of Information and Computer Science, University CA, 1998. http://www.ics.uci.edu/~mlearn/MLRepository.html.

26. Breiman L.; Friedman J.H., Olshen R.A., Stone C.J. Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software. 1984

27. Cortes C., Vapnik V. Support-Vector Networks, Machine Learning, 20, 1995.

28. Cover T.M., Hart P.E. Nearest neighbor pattern classification. IEEE Transactions on Information Theory 13 (1): 21-27.

29. Domingos, Pedro & Michael Pazzani (1997) «On the optimality of the simple Bayesian classifier under zero-one loss». Machine Learning, 29:103-137.

30. Fine T.L. Feedforward Neural Network Methodology, 3rd ed. New York: Springer-Verlag. 1999.

31. Hastie T., Tibshirani R., Friedman J. The elements of statistical learning. — Springer-Verlag, 2001.

32. Hopcroft J.E., Karp R.M. An n5/2 algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing 2 (4): 225-231

33. Kass G.V. An Exploratory Technique for Investigating Large Quantities of Categorical Data. Applied Statistics, Vol. 29, No. 2, 1980, pp. 119-127.i

34. König D. Gräfok es mätrixok. Matematikai es Fizikai Lapok 38: 116-119.

35. Loh W.-Y., Shih Y.-S. Split selection-methods for classification trees, Statistica Sinica, vol. 7, 815-840, 1997

36. Marina Velikova. Monotone Prediction Models in Data Mining. VDM Verlag Dr. Müller, 2008

37. Mullin M., Sukthankar R. Complete cross-validation for nearest neighbor classifiers // Proceedings of International Conference on Machine Learning. 2000. http://citeseer.ist.psu.edu/309025.html.

38. Quinlan R. 2011, http://rulequest.com/see5-win.html

39. Vapnik V. The nature of statistical learning theory. — 2 edition. — SpringerVerlag, New York, 2000.

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