일대일(OvO) 접근¶

(1) 해석적으로. \(C = 3\)이므로 쌍의 개수는

이다. 쌍은 \((0,1)\), \((0,2)\), \((1,2)\)다. \(C = 3\)은 OvO와 OvR의 분류기 수가 같아지는 유일한 경우다. 비율이 \(\frac{C(C-1)/2}{C} = \frac{C-1}{2}\)이므로 \(C = 3\)에서 정확히 \(1\)이다.

훈련 자료는 \(n = 150 \times 0.7 = 105\)개이고 층화추출이므로 범주마다 \(105/3 = 35\)개씩이다. 따라서 분류기 \(f_{c,c'}\)는

개를 본다. 전체의 \(2/3\)이다. 셋을 합치면 처리되는 사례의 총 개수가

이고, OvR이라면 \(Cn = 3 \times 105 = 315\)다. OvO가 오히려 적다. 분류기 수는 같은데도 그런 것은, 각 사례가 OvR에서는 \(C = 3\)개 분류기 모두에 나타나지만 OvO에서는 자기 범주가 참여하는 \(C - 1 = 2\)개에만 나타나기 때문이다.

(2) 표의 산술. 분류기는 하나같이 둘 중 하나에 표를 주고 기권하지 않으므로, 검정점 하나가 받는 표의 총합은 분류기 개수와 같은 \(C(C-1)/2 = 3\)이다. 한 범주는 \(C - 1 = 2\)번의 대결에만 참여하므로 받을 수 있는 최대 표는 \(2\)다. \(2 + 1 + 0\) 또는 \(1+1+1\)만이 가능한 분배이고, 뒤의 것이 바로 앞에서 본 순환이 일으키는 삼중 동점이다.

수치적으로.

from itertools import combinations

import numpy as np
from sklearn.datasets import load_iris
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import train_test_split
from sklearn.multiclass import OneVsOneClassifier

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=0, stratify=y)

# 일대일(OvO)은 범주 쌍마다 이항 분류기를 하나씩 둔다. 분류기 수가
# C(C-1)/2 로 늘지만, 각 분류기가 쓰는 자료는 두 범주 것뿐이라 오히려
# 학습이 빠를 수 있다. 예측은 다수결로 정한다.
model = OneVsOneClassifier(LogisticRegression(max_iter=1000))
model.fit(X_train, y_train)
y_pred = model.predict(X_test)

# C = 3이므로 이항 분류기는 C(C-1)/2 = 3개다
print(f"이항 분류기 개수: {len(model.estimators_)}")
print(f"검정 정확도: {(y_pred == y_test).mean():.4f}")

# 각 쌍이 실제로 몇 개의 사례로 학습되었는지 센다.
counts = np.bincount(y_train)
print(f"훈련 자료 {len(y_train)}개,  범주별 {counts}")
for a, b in combinations(range(3), 2):
    m = counts[a] + counts[b]
    print(f"  f_{a}{b}: {m}개  (전체의 {m / len(y_train):.3f})")

# 다수결의 상한을 확인한다. decision_function 은 표 수에 확신도를
# 아주 작게 섞은 값이므로 반올림하면 표 수가 된다.
votes = np.floor(model.decision_function(X_test) + 0.5).astype(int)
print(f"표 수의 최댓값 {votes.max()},  행별 표 합 {set(votes.sum(axis=1))}")

출력:

이항 분류기 개수: 3
검정 정확도: 1.0000
훈련 자료 105개,  범주별 [35 35 35]
  f_01: 70개  (전체의 0.667)
  f_02: 70개  (전체의 0.667)
  f_12: 70개  (전체의 0.667)
표 수의 최댓값 2,  행별 표 합 {3}

셈이 모두 맞는다. 분류기 \(3\)개, 각 \(70\)개 사례로 전체의 \(0.667 = 2/3\), 표의 총합은 모든 검정점에서 예외 없이 \(3\)이고 최댓값은 \(2 = C-1\)이다. 검정 정확도는 \(1.0000\)으로 \(45\)개를 모두 맞혔다.

눈여겨볼 것은 앞 절의 OvR이 똑같은 분할에서 \(0.9333\)을 냈다는 점이다. 틀린 \(3\)개는 모두 참값이 versicolor인데 virginica로 예측된 것이다. 가운데에 놓인 versicolor를 OvR은 "versicolor 대 setosa \(\cup\) virginica"라는 선형으로 분리되지 않는 문제로 풀어야 하지만, OvO는 그 범주를 한 번에 하나씩만 상대하므로 그런 부담이 없다. 다만 소프트맥스도 같은 분할에서 \(1.0000\)을 내니, 이 한 번의 비교가 OvO의 우월함을 말해 주지는 않는다. 검정 사례가 \(45\)개뿐이어서 \(0.9333\)과 \(1.0000\)의 차이가 세 사례에 걸려 있다는 것도 함께 기억해야 한다. 전략 사이의 체계적인 비교는 소프트맥스와의 비교에 있다.

비율은 \(\frac{C(C-1)/2}{C} = \frac{C-1}{2}\)로 \(C\)에 선형으로 증가한다.

처리되는 사례의 총 개수. 범주가 균형 잡혀 각 범주에 \(n/C\)개가 있다고 하자.

• OvR: 분류기마다 전체 \(n\)개를 쓰므로 총 \(C \cdot n = Cn\).
• OvO: 분류기마다 \(2n/C\)개를 쓰고 분류기가 \(C(C-1)/2\)개이므로

$$ \frac{C(C-1)}{2}\cdot\frac{2n}{C} = (C-1)\,n $$

두 값이 거의 같다는 점이 흥미롭다. \(Cn\) 대 \((C-1)n\)으로 차이가 1인 인자뿐이다. 이는 우연이 아니다. 각 사례는 OvR에서 \(C\)개 분류기 모두에 나타나고, OvO에서는 자기 범주가 참여하는 \(C-1\)개 분류기에 나타난다.

따라서 학습 비용의 차이는 사례 수가 아니라 비용함수의 모양에서 온다. \(T\)가 \(n\)에 선형이면 두 방식이 비슷하고, \(T\)가 초선형이면 작은 문제 여러 개(OvO)가 큰 문제 몇 개(OvR) 보다 싸다. \(T(m) = m^2\)이라면 OvR은 \(C n^2\), OvO는 \(\frac{C(C-1)}{2}(2n/C)^2 = \frac{2(C-1)n^2}{C} \approx 2n^2\)으로, OvO가 \(C/2\)배 빠르다. \(\square\)

승패 관계를 정리하면

이다. 여기서 \(A \succ B\)는 "쌍별 대결에서 A가 B를 이겼다"는 뜻이다.

일관된 순위는 없다. 실제로

라는 순환이 존재한다. A가 B를 이기고, B가 D를 이기고, D가 A를 이긴다. 이런 순환이 있으면 "A가 B보다 낫고 B가 D보다 낫다"에서 "A가 D보다 낫다"를 이끌어 낼 수 없으므로, 범주들을 한 줄로 세우는 어떤 순위도 이 승패표와 일치하지 않는다.

이는 사회선택이론의 콩도르세 역설과 정확히 같은 현상이다. 쌍별 다수결이 개별적으로는 합리적이면서 전체적으로는 이행성을 잃을 수 있다는 것이다.

OvO에 대한 함의.

• 동점은 우연한 사고가 아니라 구조적으로 발생한다. \(C \ge 3\)이면 순환이 가능하고, 순환이 있으면 반드시 동점이 생긴다.
• 따라서 동점 처리 규칙은 부수적인 세부사항이 아니라 알고리즘의 필수 구성요소다.
• 확신도의 합으로 동점을 처리하는 것이 색인 순서보다 나은 이유도 여기 있다. 순환이 있을 때 이항 분류기들이 얼마나 확신했는지가 유일하게 남은 정보이기 때문이다.
• 소프트맥스에는 이 문제가 없다. 하나의 점수 벡터 \(\mathbf{z}\)가 항상 전순서를 정의하므로 순환이 원리적으로 불가능하다. \(\square\)

범주 \(c\)의 크기를 \(n_c\)라 하면 분류기 \(f_{c,c'}\)의 훈련 표본은 \(n_c + n_{c'}\)개다.

균형 잡힌 경우. 모든 \(n_c = n/C\)이므로

이다. 모든 부분문제의 크기가 정확히 같다.

불균형한 경우. 부분문제의 크기가 \(n_c + n_{c'}\)로 쌍마다 달라진다. 더 중요한 것은 각 부분문제 안에서의 균형이다. 이항 문제의 양성 비율은 \(n_c/(n_c + n_{c'})\)이므로, 두 범주의 크기가 크게 다르면 그 쌍은 여전히 불균형하다.

예를 들어 \(n_A = 10{,}000\), \(n_B = 100\)이면 \(f_{A,B}\)의 양성 비율이 \(99\%\)다. 다만 이는 OvR보다는 훨씬 나은 상황이다. OvR에서 범주 B의 분류기는 \(100\) 대 \(10{,}000+\cdots\)를 상대해야 하기 때문이다.

OvO의 실질적 이점. 범주 크기의 최대/최소 비가 \(r\)이면, OvO 부분문제의 불균형은 최악의 경우에도 \(r\)을 넘지 않는다. 반면 OvR에서 가장 작은 범주의 불균형은 \((n - n_{\min})/n_{\min}\)으로, 범주 수가 많아지면 \(r\)보다 훨씬 커진다. 이것이 표에서 "범주 불균형: OvR보다 덜 심각"이라고 한 이유다. \(\square\)

입력 하나를 분류하는 데 필요한 내적 계산은,

소프트맥스와 OvR은 곱셈 횟수가 같다. 소프트맥스가 한 번의 행렬곱 \(\mathbf{x}^\top\mathbf{W}\)(\(p \times C\))로 처리하는 것을 OvR은 \(C\)번의 내적으로 나누어 할 뿐이다. 실제로는 행렬곱이 BLAS로 최적화되어 있어 소프트맥스가 상수배 빠르다.

\(C = 1000\), \(p = 512\)일 때:

OvO가 500배 비싸다. 게다가 모형 저장 공간도 그만큼 커서, 각 이항 모형이 \(p+1\)개의 실수를 가지면 OvO 전체가 \(499{,}500 \times 513 \approx 2.6 \times 10^8\)개의 모수, 배정도로 2GB가 넘는다.

결론: 범주 수가 많으면 OvO는 실용적이지 않다. OvO가 매력적인 것은 \(C\)가 작고(\(\le 10\) 정도) 기저 알고리즘의 학습 비용이 \(n\)에 초선형일 때뿐이다. 그마저도 학습 시간의 이야기이며, 예측 비용은 언제나 OvO가 가장 나쁘다. \(\square\)

쌍별 분류기가 확률을 낸다면 \(r_{cc'} \approx \dfrac{p_c}{p_c + p_{c'}}\)가 성립해야 한다. 미지수는 \(p_1, \ldots, p_C\)(\(C-1\)개의 자유도)인데 방정식은 \(C(C-1)/2\)개이므로, \(C \ge 3\)이면 과결정계다. 쌍별 추정치가 서로 완벽히 일관되지 않으면 정확한 해가 없다.

표준 해법(하스티-팁시라니 결합, 그리고 우와 린 확장). 다음을 푼다.

이는 쌍별 추정치에 가장 잘 맞는 확률벡터를 찾는 것이며, 반복 알고리즘으로 푼다. scikit-learn의 SVC(probability=True)가 내부적으로 이 방식을 쓴다.

문제점 세 가지.

1. 비쌈. 예측마다 반복 최적화를 풀어야 한다.
2. 불일치가 정보를 담고 있다. 쌍별 추정치가 서로 크게 어긋난다는 것은 모형이 이 입력을 잘 다루지 못한다는 신호인데, 결합 과정에서 그 정보가 하나의 확률벡터로 뭉개진다. 연습문제 2의 순환이 극단적인 예다.
3. 보정이 이중으로 필요하다. 각 쌍별 분류기의 \(r_{cc'}\)가 이미 잘 보정되어 있어야 결합 결과도 보정된다. 각각을 플랫 척도화로 보정한 뒤 다시 결합해야 한다.

대조: 소프트맥스는 확률을 직접 최적화 대상으로 삼는다. 복원 문제도, 과결정계도, 이중 보정도 없다. 확률이 필요한 응용에서 고유 소프트맥스를 선호하는 가장 강한 이유다. \(\square\)