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≥log2L)? Тогда получаем 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.
П.С.
На самом деле, мой опыт подсказывает, что связываться с такими кодировками, как правило, не стоит (если нет априорной информации о структуре классов). Лучше всё-таки решать «многоклассовыми» методами, например, случайными лесами. Но некоторая эстетика во всём этом есть;)
С точки зрения красоты, безусловно что-то есть. Но вот практичность страдает.
Вообще такой подход чем-то напоминает feature hashing, и в случае огромного числа классов это было бы, кажется, полезно.
[…] это подробно смотрите здесь. Основная идея — в задаче с l классами сделать […]