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

Метод кодирования с исправлением ошибок (error-correcting output codes [1]) также решает задачу многоклассовой классификации с помощью набора бинарных классификаторов.

Для этого каждому классу назначается свой бинарный код (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$ бинарных классификаторов, обучающихся предсказывать отдельные биты бинарного представления класса для объектов.

Для классификации нового объекта эти $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], то есть второго класса, поскольку L1-норма расхождения вероятностей будет ниже:

||\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

Описание реализации метода в библиотеке sklearn см. в [2].

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

Литература​

Литература