Содержание к диссертации
Введение
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.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 Заключение
- Принцип минимальной длины описания
- Ядровой индекс пригодности
- Методы выбора классификатора
- Методы построения ансамблей кластеризаторов
Введение к работе
На протяжении последних 50 лет теория машинного обучения является одним из важнейших направлений прикладной математики и информатики. Она включает в себя разработку методов решения задач распознавания образов, восстановления регрессии, классификации, выделения кластеров, идентификации объектов, анализа изображений, нахождения скрытых закономерностей в данных и др. Необходимость в обучении ЭВМ возникает при отсутствии адекватных математических моделей исследуемой задачи. В основе теории лежит так называемый прецедентый подход к обучению. Предполагается, что имеется некоторая обучающая выборка признаковых описаний. Требуется извлечь из этих данных объективные закономерности и построить алгоритм, который будет использован (машиной или человеком) для принятия решений при обработке новых данных. Заметим, что задачи такого рода часто возникают в плохоформализованных областях таких как биология, социология, медицина, геология, химия. В последнее время методы машинного обучения находят применение также в таких областях знаний как экономика (особенно банковское дело, кредитование, анализ рынков ценных бумаг), физика. Методы data-mining, составляющие основу теории машинного обучения являются одними из наиболее активно используемых средств извлечения знаний в генной инженерии, лингвистике, анализе баз данных. Первые работы в области теории распознавания и классификации по прецедентам появились в 30-х годах прошлого столетия и были связаны с теорией принятия решений (работы Дж. Неймана, Е. Пирсона [88]), применением разделяющих функций к задаче классификации [51], решением вопросов проверки гипотез [110]. В 50-х годах появились первые нейросетевые модели распознавания (перцептрон Розенблата), связанные с успехами в моделировании головного мозга [26]. К концу 60-х годов уже были разработаны и детально исследованы различные подходы для решения задач распознавания в рамках статистических, перцептронных моделей, и моделей с разделяющими функциями. Большой вклад в развитие теории машинного обучения и распознавания образов внесли отечественные ученые. Так М.А. Айзерман, Э.М. Браверман и Л.И. Розоноэр, разработав теорию потенциальных функций, стали родоначальниками принципиально нового подхода по использованию ядровых методов машинного обучения [1]. Широко известны такие достижения советских (российских) ученых как метод комитетов, изложенный в работах В.Д. Мазурова [23], метод группового учета аргументов А.Г. Ивахненко [20], решающие деревья Г.С. Лбова [22], метод обобщенного портрета В.Н. Вапника и пр. Крупной вехой в развитии теории распознавания образов явились работы академика РАН Ю.И. Журавлева и его учеников (алгебраическая теория распознавания, теория алгоритмов вычисления оценок) [15], [27], [14], [24], [29]. Унифицированный язык описания поведения различных алгоритмов позволил предложить оригинальную схему построения коллективных решений в алгебраическом замыкании множества исходных алгоритмов. Среди современных зарубежных исследований можно отметить работы К. Бишопа [38], Д. МакКая [84], А. Елиссееффа [40], П. Золлиха [99] и др.
В дальнейшем будут рассматриваться преимущественно задачи классификации с учителем и без учителя. Необходимо отметить, что к ним сводятся многие задачи анализа данных (нахождение закономерностей, прогнозирование дискретных состояний, идентификация, прогноз исходов). Рассмотрим классическую постановку задачи классификации с учителем1. Пусть имеется некоторый набор данных, состоящий из независимых однотипных элементов, которые в дальнейшем будут называться объектами или прецедентами. Каждый объект характеризуется d—мерным вектором признаков х Є Pi х ... х Pj и классом t, к которому он принадлежит. Вообще говоря, структура множеств Pi может быть различной. Тем не менее, в дальнейшем будем считать, что все Р{ = R, т.е. х Є Rd. Кроме того, будем полагать, что переменная t принимает конечное число значений из неупорядоченного множества t Є Т. Будем считать объекты элементами вероятностностного пространства Rd х Т,ВХТ ,РХТ , где В является сг-алгеброй Борелевских подмножеств в Rd х Т. 2 Требуется построить такой алгоритм А (алгоритм распознавания или классификации), который по значениям признаков объекта х возвращал бы оценки вероятностей принадлежности х к тому или иному классу. Иными словами A : Rd {PA(8\x)}U Вероятности PA(S\X) будем называть апостериорными вероятностями принадлежности объекта х к классу s. Заметим, что во многих работах под алгоритмом распознавания понимается отображение A:Rd- {1,...,1} (1) бедности методов, позволяющих проводить оценку качества получившегося алгоритма в последнем случае. При необходимости, к алгоритмам вида (1) можно перейти преобразованием вида А(х) = oigmaxi s i PA(S\X). Результат такого преобразования будем брать в качестве итоговой классификации объекта алгоритмом А. Легко видеть, что это преобразование естественным образом обобщается на случай, когда различные виды ошибок классификации имеют разную цену. В настоящей работе, не ограничивая общности, будем исходить из того, что все виды ошибок классификации равноценны.
Пусть имеется некоторая контрольная выборка данных с известным правильным ответом, не участвовавшая в обучении, (у,и) = (Vj Uj) . Два подхода к интерпретации алгоритма распознавания дают две различные возможности для оценивания качества алгоритма относительно рассматриваемых данных. Пусть I(a = Ь) - индикаторная функция, возвращающая единицу, если а = Ь, и ноль в противном случае.
Определение 1. Частотной оценкой алгоритма по контрольной выборке называется величина 1 q 4 3=1 Этот функционал принимает конечное число значений, поэтому крайне неудобен для сравнения различных алгоритмов и поиска оптимального алгоритма. Определение 2. Правдоподобием правильной классификации контрольной выборки объектов называется величина q ЫУ) = Рл(и\у) = ]]_РА(ЩШ j=i
Легко показать, что Рд(гіу) как функция А действительно является функцией правдоподобия. 3 Будем считать, что каждый алгоритм однозначно определяется значением своих параметров w. В дальнейшем, при рассмотрении зависимости работы алгоритма от изменения его параметров для удобства иногда будем обозначать функцию РА(І\Х) как P(t\x,w), а правдоподобие выборки РАЩХ) как P(t\x,w).
Процесс обучения алгоритма распознавания заключается в нахождении значений параметров гу наилучших, в некотором смысле, относительно обучающей выборки Dtrain = (x,t) = (Xifti) w = argmax I?(, x,w) wGQ где Q, - множество допустимых значений параметров алгоритма.
Функционал Ф{Ь,х,га) обычно так или иначе связан с качеством работы алгоритма на обучающей выборке. В частном случае, при Ф(, x,w) = P(t\x, w) получается известный принцип максимального правдоподобия. В общем случае, оптимизация качества на обучающей выборке не приводит к получению наилучшего алгоритма с точки зрения генеральной совокупности. Более того, часто наблюдается даже значительное снижение качества на независимой (тестовой) выборке, т.е. выборке, не предъявлявшейся алгоритму на этапе обучения, но для которой известны правильные алгоритма (overtraining, overfitting). Оно связано с тем, что, вообще говоря, не все закономерности, определяющие классификацию обучающей выборки справедливы для генеральной совокупности. Как правило, задачи с реальными данными содержат зашумленную информацию, что, в частности, приводит к наличию ложных закономерностей в конечных подмножествах генеральной совокупности. Наиболее интригующей задачей машинного обучения является построение общих методов, позволяющих добиться максимальной обобщающей способности алгоритма, т.е. способности выявить как можно больше объективных закономерностей, присущих генеральной совокупности при как можно меньшем количестве ложных закономерностей. Следует отметить, что до сих пор не существует единого общего метода контроля обобщающей способности алгоритмов распознавания. Проблема связана с тем, что понятие обобщающей способности для своей формализации и оценивания требует работы со всей генеральной совокупностью объектов, которая, естественно, недоступна. Различные методы косвенного оценивания обобщающей способности путем анализа используемого алгоритма и обучающей выборки пока не привели к общепринятому решению. Целью настоящей работы является исследование влияния устойчивости (понимаемой в различных смыслах) алгоритмов классификации на их обобщающую способность и разработка методов классификации с высокими обобщающими свойствами.
В первой главе кратко описаны основные идеи, лежащие в основе существующих методов оценки обобщающей способности. Подробно изложен Байесовский подход к машинному обучению, являющийся хорошей стартовой позицией для разработки новых методов контроля обобщающей способности. Предложен и обоснован принцип устойчивости, являющийся модификацией Байесовского принципа наибольшей обоснованности для выбора модели. Изложена схема его практической реализации. Приведено решение имеющей большое прикладное значение проблемы выбора наилучшей ядровой (потенциальной) функции для произвольной задачи классификации.
Во второй главе идея построения устойчивых классификаторов применена к известной задаче синтеза коллективов алгоритмов или коллективных решений (classifier fusion). Предложена схема получения алгоритма классификации с большей обобщающей способностью из конечного набора уже имеющихся обученных алгоритмов путем выпуклой стабилизации. Доказано свойство корректности получаемого классификатора. Получены оценки на его устойчивость на контрольной выборке. В конце главы приведены результаты практических испытаний, подтверждающие эффективность предложенного подхода.
Третья глава посвящена исследованию устойчивости коллективов алгоритмов классификации без учителя (алгоритмов кластеризации). В ней дан обзор существующих методов построения коллективных решений задачи кластерного анализа (ансамблей кластеризаторов). Описан метод учета устойчивости ансамблей кластеризаторов для получения более точной кластеризации в случае наличия сложных структур в данных. Проведена серия экспериментов по исследованию свойств предложенного в работе индекса комбинированной устойчивости ансамбля кластеризаторов.
Автор хотел бы выразить искреннюю признательность своему наставнику д.ф.-м.н. В.В. Рязанову и академику РАН Ю.И. Журавлеву за постоянную поддержку и внимание, оказывавшуюся на всех этапах работы. Данная работа была бы невозможной без помощи Дмитрия Кропотова, друга и коллеги автора. Также автор благодарен всем студентам, принимавшим активное участие в научной работе по данной теме. Исследования, лежащие в основе диссертации, проводились на протяжении нескольких лет при частичной поддержке различных грантов Российского Фонда Фундаментальных Исследований (проекты 02-01-08007, 02-07-90134, 02-07-90137, 03-01-00580, 04-01-08045, 05-01-00332, 05-07-90085, 05-07-90333, 06-01-00492), целевой программы ОМН РАН є2, гранта Президента РФ НШ1721.2003.1, а также фонда INTAS (проект YS04-83-2942).
Принцип минимальной длины описания
Исторически идея минимальной длины описания восходит к работам Колмогорова по алгоритмической сложности [21]. Непосредственно для выбора модели в машинном обучении этот метод был предложен Риссаненом [94] в 1978г. Алгоритм распознавания интерпретируется как архиватор, сжимающий данные (обучающую выборку) для ее последующей передачи по каналу связи. При этом считается, что описание алгоритма необходимо для раскодирования переданой информации и, следовательно, также должно быть передано по каналу связи. Определение 1.5.
Назовем совокупной длиной описания данных, количество информации, необходимое для передачи архивированного сообщения и описания алгоритма архивации в данной модели L Descr — L/Data + Ї АІд т Согласно принципу минимальной длины описания выбор модели осуществляется исходя из минимума совокупной длины описания данных.
Универсальность метода достигается за счет выражения качества работы алгоритма на обучении (степень сжатия исходных данных) и сложности использованного классификатора (длина описания алгоритма) в единых терминах - длине кодового описания. При этом неявно полагается, что чем более сложным является алгоритм, тем он хуже, т.е. тем хуже его обобщающая способность. Такой подход является буквальным математическим выражением известного философского принципа бритвы Оккама.
Теорема 1.2. Пусть имеется некоторая модель алгоритмов, определяющая априорное распределение их параметров P(w). Тогда применение принципа минимальной длины описания для выбора алгоритма эквивалентно максимизации регуляризованного правдоподобия.
Доказательство. Известно, что при оптимальном кодировании алгоритмов модели, длина описания алгоритма равна LAI9 = —log P(w).
Длина описания данных тем меньше, чем больше вероятность исходной классификации при использовании данного алгоритма P(t\x,w). При оптимальном кодировании длина описания данных равна Ьраіа = — log P(t\x,w). Легко видеть, что применение принципа минимальной длины описания в этом случае эквивалентно argmin LDescr = argmin(L ato + LAi9) = argmax(logP(a, w) + log P{w)) = w w w = a,rgmaxlog( P(t\x,w)P(w)) = arg max P(t\x,w)P(w) w w Теорема доказана.
Это преобразование иллюстрирует связь между минимумом длины описания и байесовскими методами. Среди отличий можно отметить следующие 1. Байесовское обучение (описанное далее) позволяет решить задачу выбора наилучшего семейства алгоритмов в случае наличия нескольких конкурирующих моделей. 2. Принцип минимума длины описания, в свою очередь, может быть использован там, где прямое применение вероятностных методов невозможно или нежелательно (например, в нестатистическом подходе к задаче классификации).
Более серьезное возражение против использования принципа минимальной длины описания связано с открытием факта, что более сложное (в алгоритмическом смысле) решающее правило не всегда обладает худшей обобщающей способностью. В частности, эвристически открытая, а затем теоретически обоснованная процедура бустинга (boosting) [98] убедительно иллюстрирует, что за счет грамотного усложнения (часто весьма значительного) вида решающего правила удается улучшить обобщающую способность алгоритмов классификации. При этом суммарная длина описания классификатора и обучающей выборки значительно возрастает. Таким образом и этой идее присущи серьезные концептуальные недостатки.
До сих пор рассматривались ситуации, при которой в качестве решающего правила использовался один алгоритм, взятый из модели. Альтернативный подход заключается в использовании Байесовской оценки апбстериорной вероятности параметров алгоритма w р, u ,_ P(t\x,w)P(w) ПЩ1,Х) JP(t\x,w)P(w)dw l4j
В этом случае происходит отказ от использования единственного алгоритма. Распознавание осуществляется голосованием коллектива алгоритмов причем вес каждого алгоритма пропорционален его апостериорной вероятности P(t\x,t,x)= P(t\x,w)P{w\x,t)dw п
Заметим, что в числителе формулы (4) стоит регуляризованное правдоподобие, объединяющее величину, характеризующую точность алгоритма на обучении и величину, характеризующую относительную предпочтительность конкретного алгоритма модели, выраженные в вероятностных терминах.
Ядровой индекс пригодности
Хотя принцип максимальной обоснованности сформулирован полностью в вероятностных терминах, для него можно предложить иную интерпретацию. Выражение (13) может быть рассмотрено как компромисс между точностью алгоритма на обучающей выборке (значение Qa{iVMp)) и устойчивостью относительно малых изменений параметров (выраженной корнем обратной величины определителя отрицательного гессиана log Qa(wMp)) Выбор модели с помощью принципа максимума обоснованности позволяет избежать прямой установки ограничений на веса в RVM. Тем не менее, вопрос о выборе подходящей ядровой функции остается открытым. Рассмотрим тип ядровой функции как мета-параметр и попытаемся использовать Байесовский подход для его выбора. Далее будем рассматривать популярное семейство ядровых функций К{х, z) = ехр (— 2 $ ) Цель состоит в нахождении наилучшего значения параметра а без трудоемкой процедуры скользящего контроля, используя идею устойчивости.
Легко видеть, что малые значения а ведут к переобучению и, следовательно, к высокой точности на обучающей выборке. Малые значения а означают, что почти все объекты обучающей выборки имеют ненулевые веса w, а влиянием объектов на соседей можно пренебречь. Изменение веса прецедента меняет лишь высоту соответствующей ядровой функции, оставляя при этом ее центр в самом объекте. Таким образом, при изменении веса, затрагивается лишь один объект, находящийся в центре ядровой функции. Это означает, что модификация весов мало меняет значение Qa{w). В то же время, очевидно, что узкие ядровые функции неустойчивы относительно изменения положения их центра (см. рис.2). Для учета неустойчивости относительно изменения положения ядровой функции необходимо расширить испоьзуемую модель.
Устойчивость относительно изменения весов важна при подборе коэффициентов регуляризации ос. Параметры ядровых функций отвечают за устойчивость относительно сдвига центров ядровых функций. Таким образом, для подбора ядровой функции необходимо расширение модели (2) до следующего вида Определение 1.15. Модель M new, W, z) = Sign I WiK(xnew, Z() + w0 J где zi - произвольные точки в пространстве Rd, называется расширеной моделью ядровых классификаторов.
В новой модели прямое вычисление обоснованности (6) становится вычислительно крайне сложной. Применение аппроксимации Лапласа требует оптимизации положения центров ядровых функций Zi для того, чтобы максимизировать
Оптимизация Cff,a(w,z) по z затруднительна вследствие высокой размерности пространства оптимизации, т.к. z Є Rmxn. Кроме того, выражение (17) нелинейно зависит от центров ядровых функций. Это приводит к многоэкстремальности функции, что также осложняет оптимизацию.
Рассмотрим подробнее последнее замечание. Следуя принципу максимума обоснованности, качество модели зависит от величины интеграла (6). При этом предполагается, что решающее правило должно быть построено с помощью уравнения (7). Но в данном случае это невозможно из-за сложности интегрирования. Разумным шагом в такой ситуации является использование классификатора, полученного в результате максимизации Ca a(w,z).
Методы выбора классификатора
В следующем столбце представлены аналогичные результаты, полученные применением кросс-проверки к SVM. Столбец RVM MV содержит результаты работы при подборе ядровой функции по максимуму ядровой пригодности. Столбец SVM MV показывает качество работы SVM с теми оке ядровыми функциями, как и в столбце RVM MV. Заметим, что для выбора ядровой функции в SVM не применялась процедура максимизации ядровой пригодности, а просто использовалась та ядровая функция, которая оказалась лучшей для RVM (в смысле ядровой пригодности). Столбец SVM MV позволяет проверить, определяется ли оптимальная ядровая функция только самой задачей или она также зависит и от алгоритма обучения. Наконец последний столбец содержит минимально возможные ошибки RVM, усредненные по 20 парам обучающих/тестовых выборок.
Для интерпретации данных из таблицы 1 результаты оценивались следующим образом. Наименьшей тестовой ошибке присваивался ранг 1, следующей за ней - ранг 2, и т.д. Худшему результату присваивался ранг 4. Далее оценки были просуммированы по всем девяти задачам из UCI-репозитория. Итоговые результаты показаны в последней строке таблицы. Основываясь на них, можно сделать несколько заключений. Во-первых, можно утверждать, что RVM и SVM показывают примерно одинаковые результаты, хотя сами алгоритмы существенно различны, как и положение релевантных (соответственно, опорных) векторов. Эксперименты подтвердили, что RVM, вообще говоря, намного разреженней SVM, и в среднем использует в 5-8 раз меньше ядровых функций для классификации. Еще одно важное замечание состоит в том, что предложенная в данной работе мера ядровой пригодности работает не хуже, чем альтернативная процедура кросс-проверки. Более того, она требует лишь одного цикла обучения и, следовательно, работает в несколько раз быстрее. Довольно интересным эффектом стало низкое качество SVM при использовании ядровых функций, являющихся лучшими (в смысле ядровой пригодности) для RVM. Это показывает, что качество ядровой функции определяется не только топологией выборки, но и сильно зависит от самого метода обучения. Также следует заметить, что ни кросс-проверка, ни процедура максимизации ядровой пригодности не позволяют достичь минимально возможной тестовой ошибки. Это может быть связано как с особенностями выборок, так и с тем, что тестовая выборка может сама быть смещена относительно генеральной совокупности.
1. Идея устойчивости может быть использована для обобщения принципа максимальной обоснованности. В отличие от структурной минимизации риска, ограничивающей слишком гибкие классификаторы и принципа минимальной длины описания, штрафующего алгоритмическую сложность, концепция Байесовской регуляризации (и ее модификация, описанная выше) основана на поиске модели, в которой решение устойчиво относительно изменений параметров классификатора. Различные реализации принципов Байесовской регуляризации при выборе модели, как и проведенные выше эксперименты, подтверждают, что такой подход в машинном обучении является перспективным. В этой работе была предложена иная, невероятностная интерпретация обоснованности модели. Байесовский подход был модифицирован путем рассмотрения непосредственно идеи устойчивости, а не на применении принципа максимума правдоподобия для моделей. Такая модификация позволяет использовать этот подход для нелинейных моделей, используя один классификатор вместо интегрирования по всему пространству параметров с весами, определяемыми апостериорным распределением P(w\x,t, а).
Методы построения ансамблей кластеризаторов
Покажем теперь, что предлагаемая схема является обобщением некоторых известных методов построения коллективного решения.
Теорема 2.6. Коллективное решение, полученное в результате применения выпуклого кластерного стабилизатора (29), (31) при а = 0, совпадает с результатом применения к исходному коллективу метода областей компетенции (см. [25], [81]).
Доказательство. Обозначим через А результат применения выпуклого кластерного стабилизатора с указанными параметрами к коллективу алгоритмов Аі,...,Ар. В силу (31) очевидно, что для любого объекта результат применения к нему такого стабилизатора совпадает с результатом работы одного из членов коллектива, признанного наилучшим для данной области (А(х) = А{0(х)). При а = 0 компонента устойчивости не учитывается при определении наилучшего алгоритма. Таким образом, наилучшим алгоритмом для заданной области является тот член коллектива, который допускает меньше всего ошибок на объектах контрольной выборки, принадлежащих данному кластеру го = arg max Acck{Ai) t =l,2,...,p Но такой способ получения коллективного решения совпадает с методом областей компетенции Clustering&Selection, описанным, например, в [81]. Теорема полностью доказана.
Теорема 2.7. Коллективное решение, полученное в результате применения выпуклого кластерного стабилизатора (29), (30) при г = ди0 а 1, совпадает с результатом применения к коллективу выпуклого стабилизатора (23), (24) с той же системой весовых функций и F(k) = Р(к).
Доказательство. Очевидно, что при числе кластеров, равных количеству объектов контрольной выборки, в каждый кластер попадет ровно один объект, который и будет являться центром кластера. Следовательно, условия (24) эквивалентны условиям (30). Отсюда вытекает возможность использования идентичных весовых функций в обоих случаях, т.е. каждой системе весовых функций выпуклого стабилизатора можно сопоставить эквивалентную ей систему функций выпуклого кластерного стабилизатора и наоборот.
Осталось показать, что функция G{k) = P(k). Пусть для объекта yk = Dk найдется бы один алгоритм в коллективе, который распознает его правильно. Тогда Р(к) будет равна индексу наиболее устойчивого из них, т.е. обладающего наименьшим значением Z(yk, є). Рассмотрим теперь выражение V(Ai) = Асск{Аі) + aStk(Ai)
Для всех алгоритмов, неправильно классифицирующих ук, значение V(A ) 1, так как АсскЩ = 0, a Stk(Ai) = exp (- ) Є (0,1] и 0 а 1. Любой алгоритм, правильно классифицирующий объект ук, имеет V{Ai) 1, так как Асск(Аг) = 1. Следовательно поиск наилучшего в к-м кластере осуществляется среди алгоритмов, чьи индексы входят в множество Q(k). Наилучшим алгоритмом среди них является классификатор, обладающий наибольшим значением Stk(A). Так как значение Stk(A) монотонно убывает по ZA{yk,) при любых А, то наибольшее значение соответствует наименьшему значению неустойчивости на объекте ук. Следовательно, в случае если 0(к) 0, то G{k) = R(k) = Р(к) В случае когда ни один алгоритм коллектива не может правильно классифицировать объект, аналогичными рассуждениями, учитывая что Acck{Ai) = 0 Vz, можно показать, что G(k) = Т{к) = Р(к) Теорема доказана.
Последняя теорема означает, что выпуклый стабилизатор можно определить как частный случай выпуклого кластерного стабилизатора.
Для проверки практической пригодности изложенного метода была проведена серия экспериментов по построению коллективных решений. Для тестирования использовались широкоизвестные задачи распознавания, взятые из UCI репозитория [39]. Следует отметить, что эти задачи часто используются для сравнения различных парадигм распознавания, представляя собой де-факто полигон для испытания различных идей. Эксперименты проводились с помощью программного комплекса «РАСПОЗНАВАНИЕ» [18] - универсального программного средства для исследования различных задач и методов анализа данных.
