Редактирование: Методы многоклассовой классификации

Пусть рассматривается задача классификации с <math>C</math> классами.

== One-versus-all подход ==

[[Файл:11.png|thumb|322px]]

* Обучим на всех объектах тренировочной выборки <math>C</math> '''бинарных''' классификаторов типа "принадлежит ли объект <math>i</math>-ому классу".
* В результате получим <math>C</math> классификаторов <math>f_c(x)</math>.
* Ответ ищется, как <math>\hat y(x) = \underset{c \in [1, \dots, C] }{\operatorname{argmax}} f_c(x)</math>.

== One-versus-one подход ==

[[Файл:2.png|thumb|284px]]

* Обучим <math>\dfrac{C(C - 1)}{2}</math> ''''бинарных''' классификаторов следующим образом: для каждой пары <math>i, j \in [1, \dots, C], i \ne j</math> обучим бинарный классификатор <math>f_{i, j}(x)</math> на тех объектах тренировочной выборки, ответ которых принимает значение <math>i</math> или <math>j</math>.
* В результате получим <math>\dfrac{C(C - 1)}{2}</math> классификаторов <math>f_{i, j}(x)</math>.
* На этапе предсказания каждый из всех обученных классификаторов возвращает индикатор принадлежности соответствующему классу. Тот класс, за который проголосовало большинство и будет ответом на данном объекте:

<math>\hat y(x) = \underset{c \in [1, \dots, C] }{\operatorname{argmax}} \sum \limits_{i \ne j \in [1, \dots, C]} \mathbb I [f_{i, j}(x) == c]</math>.

== Коды, исправляющие ошибки ==

* Каждый номер класса кодируется бинарным вектором <math>W_i</math>, состоящим из <math>B</math> бит, причем, <math>B \ge \lceil \log_2 C \rceil</math>.
* Строится <math>B</math> бинарных классификаторов <math>f_b(x)</math>, которые предсказывают <math>b</math>-ый бит.
* Ответ ищется как <math>\hat y(x) = \underset{c \in [1, \dots, C] }{\operatorname{argmin}} \sum \limits_{b = 1}^B |W_{cb} - f_b(x)|</math>, где <math>W_{cb}</math> --- <math>b</math>-ый бит кодового слова для класса <math>c</math>.
* Чем больше бит используется при кодировании классов, тем более модель устойчива к ошибкам классификаторов.
* Кодирование производится рандомно или так, чтобы попарные расстояния Хэмминга между кодами были как можно больше.

Ещё по этой теме [[Классификация с кодированием целевой переменной|здесь]].

== Ссылки ==

[http://www.machinelearning.ru/wiki/images/4/4e/Kitov-ML-eng-07-Linear_methods_of_classification.pdf#page=10 слайды Китова]

[http://www.machinelearning.ru/wiki/images/9/95/Kitov-ML-eng-13-Ensemble_methods.pdf#page=5 слайды Китова]