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

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

One-versus-all подход

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

One-versus-one подход

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

$\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]$.

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

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

Ещё по этой теме здесь.

Ссылки

слайды Китова

слайды Китова