Метод один-против-одного

Метод один-против-одного (one-vs-one) представляет собой альтернативный метод многоклассовой классификации с помощью набора бинарных классификаторов.

Для начала рассмотрим похожую задачу, когда у нас есть $C$ футбольных команд, и нам нужно определить среди них самую сильную. Мы не можем заставить играть одновременно больше двух команд, поэтому проведём матчи между каждой парой команд. Всего таких пар будет $C(C-1)/2$. Самой сильной командой тогда можно назначить ту команду, которая победила в максимальном числе матчей. Если лучшие команды побеждали одинаковое число раз, то назначим самой лучшей среди них ту, которая при этом ещё забила в соревнованиях наибольшее число голов.

Аналогично работает и метод один-против-одного. Настраивается $C(C-1)/2$ бинарных классификаторов, определяющих, какой класс лучше подходит объекту, если выбирать только между $i$-м и $j$-м классом:

$$\hat{y}=\text{sign}(g_{ij}(\mathbf{x}))$$

Настройка каждого такого классификатора производится по подвыборке объектов, принадлежащих либо $i$-му, либо $j$-му классу.

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

Сложность оценивания

Метод один-против-одного требует оценки $C(C-1)/2$ бинарных классификаторов, в то время как метод один-против-всех - только $C$ классификаторов. Однако в первом методе оценка производится каждый раз по подвыборке объектов двух соответствующих классов, в том время как во втором методе - каждый раз по всем объектам выборки.

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

Каким методом, один-против-одного или одним-против-всех, вычислительно сложнее строить прогноз?

Если считать, что сложность прогнозирования каждым бинарным классификатором примерно одинаковая, то методом один-против-одного, поскольку для него нужно пропустить объект через $C(C-1)/2$ классификаторов. В методе же один-против-всех объект пропускается только через $C$ классификаторов.