ECOC — это «Error-Correcting Output Code». Пишу, поскольку мои студенты не знают, как этот зверь применяется в машинном обучении.

Допустим, Вы решаете задачу классификации с L (L>2) классами, а у Вас есть только бинарные классификаторы (т.е. решают задачу с двумя классами). Как быть?

Подход One-vs-All

Решаете L задач, в i-й отделяете i-й класс от остальных (объекты i-го класса имеют метку 1, а остальные — метку 0). При классификации нового объекта прогоняете его через L настроенных классификаторов, относите к тому классу, в котором соответствующий классификатор максимально уверен (ясно, что тут надо использовать не только ответы алгоритмов, но ещё оценки их правильности).

Подход One-vs-One

Аналогично, но теперь уже решаете L(L-1)/2 задач, в каждой отделяете i-й класс от j-го (для всех 1≤i<j≤L). Тут уже надо подумать, как классифицировать новый объект. Например, оценку принадлежности к i-му классу можно определить как сумму степеней уверенности в принадлежности к i-му классу всех классификаторов, который отделяют i-й класс от какого-то другого (их ровно L-1). Относим к классу с максимальной оценкой.

Подход ECOC

А что если каждый класс закодировать каким-то k-мерным бинарным вектором (k≥log₂L)? Тогда получаем k бинарных задач. Скажем, кодировка

1 - 1000
2 - 0100
3 - 0010
4 - 0001

соответствует первому подходу. Кодировка

1 - 111---
2 - 0--11-
3 - -0-0-1
4 - --0-00

— второму (здесь прочерк — это «не-кодирование», в соответствующей задаче этот класс не участвует). Ну, и возможна, например, такая кодировка

1 - 11
2 - 10
3 - 01
4 - 00

Ясно, что тут строится два бинарных классификатора, новый объект даётся им на вход, а выходы формируют бинарный вектор — код соответствующего класса.

Теперь, причём тут коды, исправляющие ошибки (Error-Correcting Output Code). Дело в том, что когда мы прогнали объект через k классификаторов и получили бинарный k-мерный вектор, то среди кодовых слов классов может такого не оказаться. Например, в такой кодировке

1 - 111
2 - 100
3 - 010
4 - 001

при получении (011). Куда его следует отнести? В класс, код которого «максимально похож» на полученный, т.е. ближе всего находится по метрике Хэмминга. В данном случае — в 1й или 3й (к сожалению, тут есть неоднозначность). Так вот, кодировок классов может быть много. Выбор оптимальной — отдельная задача. Исправляющие ошибки коды как раз обеспечивают кодировки с нужными свойствами, ведь каждый построенный нами классификатор всё-таки ошибается. Надо, чтобы несмотря на эти ошибки, объект был классифицирован верно.

Кто придумал

Dietterich  T.G.,  Bakiri  G. Solving multiclass learning problems via error-correcting output codes // Journal of Artificial Intelligence Research, 1995. Vol. 2. P. 263–286.

П.С.

На самом деле, мой опыт подсказывает, что связываться с такими кодировками, как правило, не стоит (если нет априорной информации о структуре классов). Лучше всё-таки решать «многоклассовыми» методами, например, случайными лесами. Но некоторая эстетика во всём этом есть;)