Кодирование с исправлением ошибок

Метод кодирования с исправлением ошибок (error-correcting output codes) также решает задачу многоклассовой классификации с помощью набора бинарных классификаторов. Для этого каждому классу назначается свой бинарный код (binary code) - $K$-мерный вектор, состоящий только из нулей и единиц, которые, в отличие от one-hot кодирования, могут содержать в кодировках несколько единиц.

Пример кодирования классов 5-мерными бинарными кодами ($K=5$):

класс	код
1	[0,0,0,0,0]
2	[0,1,1,1,0]
3	[1,1,1,1,1]

Далее вектор откликов представляется кодировочной матрицей $Y'\in\mathbb{R}^{N\times K}$, полученной из исходного вектора классов $Y\in\mathbb{R}^N$ заменой каждого класса его бинарным кодом, как показано ниже:

y	Y'
1	[0,0,0,0,0]
1	[0,0,0,0,0]
2	[0,1,1,1,0]
3	[1,1,1,1,1]
2	[0,1,1,1,0]

После этого обучаются K бинарных классификаторов, обучающихся предсказывать 1-й, 2-й, ... K-й бит бинарного представления класса для объектов.

Для классификации нового объекта эти $K$ классификаторов применяются к объекту, предсказывая его бинарный код. В итоге назначается тот класс бинарный код которого ближе всего к предсказанному. Совпадение может быть не идеальным, поскольку часть бит могли быть неверно предсказанными.

Вычислительная эффективность

Этот метод может работать с минимальной длиной кодовых слов (равной $\lceil \log_2 C\rceil$), обеспечивающей однозначное восстановление классов по их кодовым представлениям. В этом случае он будет строить прогнозы вычислительно эффективнее, чем методы один-против-всех и один-против-одного, требующие запуска $C$ и $C(C-1)/2$ бинарных классификаторов соответственно.

Точность прогнозов

На практике используются более длинные кодовые слова, чем минимально необходимые для однозначного восстановления классов. В этом случае, даже если небольшая часть классификаторов ошибётся и неверно предскажет свои биты кодового слова, всё ещё сохранится возможность восстановить верный класс.

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

Другой подход повышения точности - предсказывать не сами биты кодовой последовательности, а вероятность единицы в каждом бите. Именно в такой конфигурации метод и реализован в библиотеках. Точность повышается за счёт того, что учёт вероятностей позволяет более тонко различать уверенность прогноза каждого бита.

Для кодирования классов, представленного выше, мы могли получить для нового объекта следующее кодовое слово [0,0,0,1,0], которое ближе всего к [0,0,0,0,0], то есть к кодировке первого класса. Однако вероятности единицы могли оказаться [0,0.4,0.4,1,0], что указывает на то, что скорее всего это прогноз для [0,1,1,1,0], то есть второго класса, поскольку $L_1$ норма расхождения вероятностей будет ниже:

$$||\mathbf{p}-\mathbf{p}_1||=|0-0|+|0.4-0|+|0.4-0|+|1-0|+|0-0|=1.8$$ $$||\mathbf{p}-\mathbf{p}_2||=|0-0|+|0.4-1|+|0.4-1|+|1-1|+|0-0|=1.2$$