Тестирование и композиция методов

Если обучающее множество очень большое, его можно случайным образом разбить на два подмножества $\mathbb{X}_L=\mathbb{X}_l\cup \mathbb{X}_t$. На множестве $\mathbb{X}_l$ производится обучение алгоритма, а на $\mathbb{X}_t$ - его тестирование. Такой метод называется тестированием на отложенных данных (hold-out).

Для не очень больших множеств используют метод скользящего контроля (cross-validation). Для этого метод hold-out повторяют $M$ раз (на различных случайных разбиениях $\mathbb{X}_l\cup \mathbb{X}_t$) и усредняют полученные эмпирические ошибки.

Бустинг - композиция алгоритмов

Пусть есть два класса, т.е. множество обучающих примеров $\mathbf{x}_i$ n-мерного пространства признаков отображается на $Y=\{0,\,1\}$. Когда классов много, можно выделить один из них, назвав его объекты положительными примерами, а все остальные классы объединить в другой класс отрицательных примеров. Может оказаться, что для такого бинарного разделения классов, легче построить эффективный алгоритм классификации (подобную процедуру, естественно, можно проделать для каждого класса).

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

Представим $m$ различных алгоритмов распознавания в виде функций $a_1(\mathbf{x}),....,a_m(\mathbf{x})$ дающих $1$, если $\mathbf{x}\in$ первому классу ("положительным примерам") и $0$ - если второму ("отрицательным примерам"). Промежуточные значения функций интерпретируются как вероятность принадлежности первому классу. Например, $a(\mathbf{x})$ может быть результатом работы нейронной сети с одним выходом.

Композицией алгоритмов называется функция $f(\mathbf{x}) = f(a_1(\mathbf{x}),...,a_m(\mathbf{x})),$ которая также возвращает значения в диапазоне $[0...1]$ с той-же вероятностной интерпретацией. Простейший пример такой функции - это взвешенное голосование: $$f(\mathbf{x}) = \sum^m_{i=1} \omega_i\,a_i(\mathbf{x}),~~~~~~~~~~~~~~~\sum^m_{i=1} \omega_i = 1,~~~~~~~~\omega_i \gt 0.$$ Весовые коэффициенты $\omega_\mu$, обычно, отражают качество работы $\mu$-того алгоритма.

Можно также определить решающее правило $Y=A(f(\mathbf{x}))$, которое по вероятности даёт номер класса или отказывается проводить распознование ($1,0.5,0$ = "он, не знаю, не он"). Например $A(p)$ может быть пороговой функцией ($p\gt 0.9$ - это $1$, $p \lt 0.1$ - это $0$, в остальных случаях - "не знаю").

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

AdaBoost - adaptive boosting

AdaBoost (adaptive boosting) - бустинг в котором каждый следующий классификатор учится на примерах, которые плохо классифицируются предыдущими классификаторами. При обучении, объектам присваиваются веса (сначала равные). Если объект неверно классифицировался, вес его увеличивается и далее такой объект становится более важным (новые классификаторы работают в основном с ним). Рассмотрим этот алгоритм подробнее

Пусть есть $N$ обучающих примеров с двумя классами $+1,-1$. И пусть имеется $m$ классификаторов, т.е алгоритмов $A_i(\mathbf{x}) = +1$, если $\mathbf{x}\in$ первому классу и $A_i(\mathbf{x}) = -1$ - второму ($i=1,...,m$). Качество работы классификатора $C_\mu$ будем оценивать следующей функцией стоимости: $$\mathrm{Cost}_i = \sum^N_{\mu=1} w_\mu\,\exp(-\alpha_i\,Y_\mu\,A_i(\mathbf{x}_\mu)),~~~~~~~~~~~~~~~ Y_\mu= \left\{ \begin{array}{ll} +1, & \mathbf{x}_i\in первому~классу,\\ -1 & \mathbf{x}_i\in второму~классу. \end{array} \right.$$ Если результат классификатора совпадает со значением класса $\pm 1$, то произведение $Y_\mu\,A_\mu(\mathbf{x}_\mu)$ положительно и функция стоимости уменьшается. Если не совпадает, то Cost увеличивается. Параметры $\alpha_i$ подлежат подбору (обучение метода). В начале у $N$ примеров равные веса $w_1=...=w_N=1/N$.

Полезная информация

• Отрывок из семинара