Содержание
0 Введение С
1 Выбор модели с помощью принципа устойчивости 14
1.1 Проблема выбора модели........................................14
1.2 Общие методы выбора модели....................................18
1.2.1 Структурная минимизация риска...........................19
1.2.2 Принцип минимальной длины описания......................21
1.2.3 Байесовское обучение....................................24
1.3 Принцип устойчивости..........................................28
1.4 Метод релевантных векторов....................................37
1.5 Ядровой индекс пригодности....................................40
1.6 Результаты экспериментов .....................................49
1.6.1 Модельная задача .......................................49
1.6.2 Реальные данные.........................................50
1.7 Обсуждение и выводы...........................................54
2 Выпуклая стабилизация коллективов алгоритмов 57
2.1 Особенности построения коллективных решений...................57
2.2 Методы получения коллективных решений.........................59
2.2.1 Общие положения.........................................59
2.2.2 Комитетные методы.......................................61
2.2.3 Методы выбора классификатора ...........................65
2.3 Выпуклый стабилизатор.........................................67
2.3.1 Неустойчивость классификаторов..........................67
2
2.3.2 Стабилизация корректных алгоритмов.......................71
2.3.3 Стабилизация некорректных алгоритмов.....................73
2.4 Выпуклая кластерная стабилизация...............................76
2.5 Результаты экспериментов ......................................81
2.6 Выводы.........................................................83
3 Устойчивость ансамблей кластеризаторов 86
3.1 Специфика задачи кластерного анализа...........................86
3.2 Методы оценки устойчивости и построения ансамблей
алгоритмов кластерного анализа.................................89
3.2.1 Методы построения ансамблей кластеризаторов 89
3.2.2 Устойчивость методов кластеризации.......................92
3.2.3 Использование устойчивости для определения числа
кластеров...............................................94
3.3 Описание эксперимента..........................................96
3.3.1 Устойчивость ансамблей относительно исходных
алгоритмов кластеризации...............................101
3.3.2 Связь между устойчивостью ансамбля и его точностью. . 102
3.3.3 Использование устойчивости ансамблей для определения числа кластеров...................................107
3.4 Выводы........................................................110
4 Заключение 115
3
Список обозначений
d размерность признакового пространства I количество классов в задаче классификации Ci,..., Q классы в задаче классификации
Агат = (®> 0 обучающая выборка (признаковые описания и значения неизвестной компоненты)
DVaUd = (у, и) контрольная выборка
Dtest тестовая выборка
т объем обучающей выборки
q объем контрольной выборки
х совокупность признаковых описаний объектов обучающей выборки {хi,t{) г-ый объект обучающей выборки Х( признаковое описание 2-ого объекта обучающей выборки tj значение неизвестной компоненты 2-ого объекта обучающей выборки х? значение признака j объекта (Xi, U)
w совокупность параметров алгоритма, настраивающихся в ходе обучения Wj значение j-ого параметра
а совокупность мега-параметров модели, подлежащих определению при выборе модели
4
а;* значение ^'-ого мета-параметра
(Уа(и;) значение регуляризованного правдоподобия
обучающей выборки алгоритмом распознавания
Са(іи) значение логарифма регуляризованного классификации обучающей выборки
классификации
правдоподобия
5
О Введение
На протяжении последних 50 лет теория машинного обучения является одним из важнейших направлений прикладной математики и информатики. Она включает в себя разработку методов решения задач распознавания образов, восстановления регрессии, классификации, выделения кластеров, идентификации объектов, анализа изображений, нахождения скрытых закономерностей в данных и др. Необходимость в обучении ЭВМ возникает при отсутствии адекватных математических моделей исследуемой задачи. В основе теории лежит так называемый прецедентый подход к обучению. Предполагается, что имеется некоторая обучающая выборка признаковых описаний. Требуется извлечь из этих данных объективные закономерности и построить алгоритм, который будет использован (машиной или человеком) для принятия решений при обработке новых данных. Заметим, что задачи такого рода часто возникают в плохоформализованных областях таких как биология, социология, медицина, геология, химия. В последнее время методы машинного обучения находят применение также в таких областях знаний как экономика (особенно банковское дело, кредитование, анализ рынков ценных бумаг), физика. Методы data-mining, составляющие основу теории машинного обучения являются одними из наиболее активно используемых средств извлечения знаний в генной инженерии, лингвистике, анализе баз данных. Первые работы в области теории распознавания и классификации по прецедентам появились в 30-х годах прошлого столетия и были связаны с теорией принятия решений (работы Дж. Неймана, Е. Пирсона [88]), применением разделяющих функций к задаче классификации [51],
6
решением вопросов проверки гипотез [110]. В 50-х годах появились первые нейросетевые модели распознавания (перцептрон Розенблата), связанные с успехами в моделировании головного мозга [26]. К концу 60-х годов уже были разработаны и детально исследованы различные подходы для решения задач распознавания в рамках статистических, перцептронных моделей, и моделей с разделяющими функциями. Большой вклад в развитие теории машинного обучения и распознавания образов внесли отечественные ученые. Так М.А. Айзерман, Э.М. Браверман и Л.И. Розоноэр, разработав теорию потенциальных функций, стали родоначальниками принципиально нового подхода по использованию ядровых методов машинного обучения [1]. Широко известны такие достижения советских (российских) ученых как метод комитетов, изложенный в работах В.Д. Мазурова [23], метод группового учета аргументов А.Г. Ивахненко [20], решающие деревья Г.С. Лбова [22], метод обобщенного портрета В.Н. Вапника и пр. Крупной вехой в развитии теории распознавания образов явились работы академика РАН Ю.И. Журавлева и его учеников (алгебраическая теория распознавания, теория алгоритмов вычисления оценок) [15], [27], [14], [24], [29]. Унифицированный язык описания поведения различных алгоритмов позволил предложить оригинальную схему построения коллективных решений в алгебраическом замыкании множества исходных алгоритмов. Среди современных зарубежных исследований можно отметить работы К. Бишопа [38], Д. МакКая [84], А. Елиссееффа [40], П. Золлиха [99] и др.
В дальнейшем будут рассматриваться преимущественно задачи классификации с учителем и без учителя. Необходимо отметить, что к
7
ним сводятся многие задачи анализа данных (нахождение закономерностей, прогнозирование дискретных состояний, идентификация, прогноз исходов). Рассмотрим классическую постановку задачи классификации с учителем1. Пусть имеется некоторый набор данных, состоящий из независимых однотипных элементов, которые в дальнейшем будут называться объектами или прецедентами. Каждый объект характеризуется <1—мерным вектором признаков х £ Р\ X ... х Р^ к классом £, к которому он принадлежит. Вообще говоря, структура множеств Pi может быть различной. Тем не менее, в дальнейшем будем считать, что все Р* = М, т.е. х £ Ма. Кроме того, будем полагать, что переменная I принимает конечное число значений из неупорядоченного множества £ £ Т. Будем считать объекты элементами вероятностностного пространства < х Т,Вхт, Рхт >, где В является а-алгеброй Борелевских подмножеств в х Т. 2 Требуется построить такой алгоритм А (алгоритм распознавания или классификации), который по значениям признаков объекта х возвращал бы оценки вероятностей принадлежности х к тому или иному классу. Иными словами
А : К* -> {Рл(Ф)}19=1
Вероятности Ра(з\х) будем называть апостериорными вероятностями принадлежности объекта х к классу 5. Заметим, что во многих работах под алгоритмом распознавания понимается отображение
(1)
В данной работе такой подход не рассматривается ввиду относительной
Постановка задачи классификации без учителя (кластеризация данных) будет рассмотрена в главе 3
2В дальнейшем, для удобства обозначений, индексы вероятностной меры (о-алгебры) будем опускать, если из контекста понятно о какой мерс (о-алгебре идет речь.
8
бедности методов, позволяющих проводить оценку качества получившегося алгоритма в последнем случае. При необходимости, к алгоритмам вида
Результат такого преобразования будем брать в качестве итоговой классификации объекта алгоритмом А. Легко видеть, что это преобразование естественным образом обобщается на случай, когда различные виды ошибок классификации имеют разную цену. В настоящей работе, не ограничивая общности, будем исходить из того, что все виды ошибок классификации равноценны.
Пусть имеется некоторая контрольная выборка данных с известным правильным ответом, не участвовавшая в обучении, (у,и) =
Два подхода к интерпретации алгоритма распознавания дают две различные возможности для оценивания качества алгоритма относительно рассматриваемых данных. Пусть 1(а = Ь) - индикаторная функция, возвращающая единицу, если а = Ь, и ноль в противном случае.
Определение 1. Частотной оценкой алгоритма по контрольной выборке называется величина
Этот функционал принимает конечное число значений, поэтому крайне неудобен для сравнения различных алгоритмов и поиска оптимального алгоритма.
Определение 2. Правдоподобием правильной классификации контрольной
л
(1) можно перейти преобразованием вида А(х) = а^тахі<3<{Р,і(5|:г).
9
выборки объектов называется величина
я
Му) = РаЫу) = Y[PA(uj\yj)
з=1
Легко показать, что РА(и\у) как функция А действительно является функцией правдоподобия. 3 Будем считать, что каждый алгоритм однозначно определяется значением своих параметров w. В дальнейшем, при рассмотрении зависимости работы алгоритма от изменения его параметров для удобства иногда будем обозначать функцию Рл(£|ж) как Р(£|:г,ги), а правдоподобие выборки Ра{Ь\х) как P(t\x,w).
Процесс обучения алгоритма распознавания заключается в нахождении значений параметров наилучших, в некотором смысле, относительно обучающей выборки Dtrain = (#> t) = (я*, U)^
w* = arg max Ф(£, x, w)
где fl “ множество допустимых значений параметров алгоритма.
Функционал Ф(£,ж,1/;) обычно так или иначе связан с качеством работы алгоритма на обучающей выборке. В частном случае, при Ф(^,ж,<ш) = P(t|ж,го) получается известный принцип максимального правдоподобия. В общем случае, оптимизация качества на обучающей выборке не приводит к получению иаилучшего алгоритма с точки зрения генеральной совокупности. Более того, часто наблюдается даже значительное снижение качества на независимой (тестовой) выборке, т.е. выборке, не предъявлявшейся алгоритму на этапе обучения, но для которой известны правильные
ответы. Такое явление получило название переобучения или перенастройки
3 достаточно убедиться, что при фиксированном алгоритме А и входных данных у функция Рд(и|у) задаст распределение вероятностей всевозможных классификаций объектов выборки
10
алгоритма (overtraining, overfitting). Оно связано с тем, что, вообще говоря, не все закономерности, определяющие классификацию обучающей выборки справедливы для генеральной совокупности. Как правило, задачи с реальными данными содержат зашумленную информацию, что, в частности, приводит к наличию ложных закономерностей в конечных подмножествах генеральной совокупности. Наиболее интригующей задачей машинного обучения является построение общих методов, позволяющих добиться максимальной обобщающей способности алгоритма, т.е. способности выявить как можно больше объективных закономерностей, присущих генеральной совокупности при как можно меньшем количестве ложных закономерностей. Следует отметить, что до сих пор не существует единого общего метода контроля обобщающей способности алгоритмов распознавания. Проблема связана с тем, что понятие обобщающей способности для своей формализации и оценивания требует работы со всей генеральной совокупностью объектов, которая, естественно, недоступна. Различные методы косвенного оценивания обобщающей способности путем анализа используемого алгоритма и обучающей выборки пока не привели к общепринятому решению. Целью настоящей работы является исследование влияния устойчивости (понимаемой в различных смыслах) алгоритмов классификации на их обобщающую способность и разработка методов классификации с высокими обобщающими свойствами.
В первой главе кратко описаны основные идеи, лежащие в основе существующих методов оценки обобщающей способности. Подробно изложен Байесовский подход к машинному обучению, являющийся хорошей стартовой
11
- Київ+380960830922