05.18.05.02 부스팅 방법
작성자: admin 작성일시: 2017-07-12 18:14:11 조회수: 3354 다운로드: 268
부스팅 방법¶
부스트(boost) 방법은 미리 정해진 갯수의 모형 집합을 사용하는 것이 아니라 하나의 모형에서 시작하여 모형 집합에 포함할 개별 모형을 하나씩 추가한다. 모형의 집합은 위원회(commitee) $C$라고 하고 $m$개의 모형을 포함하는 위원회를 $C_m$으로 표시한다. 위원회에 들어가는 개별 모형을 약 분류기(weak classifier)라고 하며 $k$로 표시한다.
부스트 방법의 특징은 한번에 하나씩 모형을 추가한다는 것이다.
$$ C_1 = \{ k_1 \} $$$$ C_2 = C_1 \cup k_2 = \{ k_1, k_2 \} $$$$ C_3 = C_2 \cup k_3 = \{ k_1, k_2, k_3 \} $$$$ \vdots $$$$ C_m = C_{m-1} \cup k_m = \{ k_1, k_2, \ldots, k_m \} $$
그리고 $m$번째로 위원회에 추가할 개별 모형 $k_m$의 선택 기준은 그 전단계의 위원회 $C_{m-1}$의 성능을 보완하는 것이다.
위원회 $C_m$의 최종 결정은 다수결 방법을 사용하지 않고 각각의 개별 모형의 출력을 가중치 $\alpha$로 가중선형조합한 값을 판별 함수로 사용한다. 또한 부스트 방법은 이진 분류에만 사용할 수 있으며 $y$값은 1또는 -1의 값을 가진다.
$$ y = -1 \text{ or } 1 $$$$ C_{m}(x_i) = \text{sign} \left( \alpha_1k_1(x_i) + \cdots + \alpha_{m}k_{m}(x_i) \right) $$
에이다부스트¶
에이다부스트(adaboost)라는 이름은 적응 부스트(adaptive boost)라는 용어에서 나왔다. 에이다부스트는 위원회에 넣을 개별 모형 $k_m$을 선별하는 방법으로는 학습 데이터 집합의 $i$번째 데이터에 가중치 $w_i$를 주고 분류 모형이 틀리게 예측한 데이터의 가중치를 합한 값을 손실함수 $L$로 사용한다. 이 손실함수를 최소화하는 모형이 $k_m$으로 선택된다.
$$ L_m = \sum_{i=1}^N w_{m,i} I\left(k_m(x_i) \neq y_i\right)$$
위 식에서 $I$는 $k(x_i) \neq y_i$라는 조건이 만족되면 1, 아니면 0을 가지는 지시함수(indicator function)이다. 따라서 틀린 문제에 대한 가중치의 합이다.
위원회 $C_m$에 포함될 개별 모형 $k_m$이 선택된 후에는 가중치 $\alpha_m$를 결정해야 한다. 이 값은 다음처럼 계산한다.
$$ \epsilon_m = \dfrac{\sum_{i=1}^N w_{m,i} I\left(k_m(x_i) \neq y_i\right)}{\sum_{i=1}^N w_{m,i}} $$$$ \alpha_m = \frac{1}{2}\log\left( \frac{1 - \epsilon_m}{\epsilon_m}\right) $$
데이터에 대한 가중치 $w_{m,i}$는 최초에는(m=1)모든 데이터에 대해 같은 값을 가지지만 위원회가 증가하면서 값이 바뀐다. 가중치의 값은 지수함수를 사용하여 위원회 $C_{m-1}$이 맞춘 문제는 작게, 틀린 문제는 크게 확대(boosting)된다.
$$ w_{m,i} = w_{m-1,i} \exp (-y_iC_{m-1}) = \begin{cases} w_{m-1,i}e^{-1} & \text{ if } C_{m-1} = y_i\\ w_{m-1,i}e & \text{ if } C_{m-1} \neq y_i \end{cases} $$
$m$번째 멤버의 모든 후보에 대해 위 손실 함수를 적용하여 가장 값이 작은 후보를 $m$번째 멤버로 선정한다.
에이다부스팅은 사실 다음과 같은 손실함수를 최소화하는 $C_m$을 찾아가는 방법이라는 것을 증명할 수 있다.
$$ L_m = \sum_{i=1}^N \exp(−y_i C_m(x_i)) $$
개별 멤버 $k_m$과 위원회의 관계는
$$ C_m(x_i) = \sum_{j=1}^m \alpha_j k_j(x_i) = C_{m-1}(x_i) + \alpha_m k_m(x_i) $$
이고 이 식을 대입하면
$$ \begin{eqnarray} L_m &=& \sum_{i=1}^N \exp(−y_i C_m(x_i)) \\ &=& \sum_{i=1}^N \exp\left(−y_iC_{m-1}(x_i) - \alpha_m y_i k_m(x_i) \right) \\ &=& \sum_{i=1}^N \exp(−y_iC_{m-1}(x_i)) \exp\left(-\alpha_m y_i k_m(x_i)\right) \\ &=& \sum_{i=1}^N w_{m,i} \exp\left(-\alpha_m y_i k_m(x_i)\right) \\ \end{eqnarray} $$
$y_i$와 $k_M(x_i)$가 1 또는 -1값만 가질 수 있다는 점을 이용하면,
$$ \begin{eqnarray} L_m &=& e^{-\alpha_m}\sum_{k_m(x_i) = y_i} w_{m,i} + e^{\alpha_m}\sum_{k_m(x_i) \neq y_i} w_{m,i} \\ &=& \left(e^{\alpha_m}-e^{-\alpha_m}\right) \sum_{i=1}^N w_{m,i} I\left(k_m(x_i) \neq y_i\right) + e^{-\alpha_m}\sum_{i=1}^N w_{m,i} \end{eqnarray} $$
$L_m$을 최소화하려면 $\sum_{i=1}^N w_{m,i} I\left(k_m(x_i) \neq y_i\right)$을 최소화하는 $k_m$ 함수를 찾은 다음 $L_m$을 최소화하는 $\alpha_m$을 찾아야 한다.
$$ \dfrac{d L_m}{d \alpha_m} = 0 $$
이 조건으로부터 $\alpha_m$ 공식을 유도할 수 있다.
다음은 scikit-learn의 ensemble 서브패키지가 제공하는 AdaBoostClassifier 클래스를 사용하여 분류 예측을 하는 예이다. 약분류기로는 깊이가 1인 단순한 의사결정나무를 채택하였다.
여기에서는 각 표본 데이터의 가중치 값을 알아보기 위해 기존의 AdaBoostClassifier 클래스를 서브클래싱하여 가중치를 속성으로 저장하도록 수정한 모형을 사용하였다.
n_samples=100, n_features=2,
class MyAdaBoostClassifier(AdaBoostClassifier):
learning_rate=1.,
algorithm='SAMME.R',
super(MyAdaBoostClassifier, self).__init__(
self.sample_weight = [None] * n_estimators
def _boost(self, iboost, X, y, sample_weight, random_state):
sample_weight, estimator_weight, estimator_error = \
super(MyAdaBoostClassifier, self)._boost(iboost, X, y, sample_weight, random_state)
self.sample_weight[iboost] = sample_weight.copy()
return sample_weight, estimator_weight, estimator_error
model_ada = MyAdaBoostClassifier(DecisionTreeClassifier(max_depth=1, random_state=0), n_estimators=20)
model_ada.fit(X, y)
def plot_result(model, title="분류결과", legend=False, s=50):
xx1, xx2 = np.meshgrid(np.arange(x1_min, x1_max, 0.02), np.arange(x2_min, x2_max, 0.02))
Y = model.predict(np.c_[xx1.ravel(), xx2.ravel()]).reshape(xx1.shape)
cs = plt.contourf(xx1, xx2, Y, cmap=plt.cm.Paired, alpha=0.5)
for i, n, c in zip(range(2), "01", "br"):
plt.scatter(X[idx, 0], X[idx, 1], c=c, s=s, alpha=0.5, label="Class %s" % n)
plt.colorbar(cs)
plot_result(model_ada, "에이다부스트(m=20) 분류 결과")
각 단계의 분류 모형에 대한 가중치 값과 분류 모형의 분류 결과를 시각화하면 다음과 같다. 데이터의 가중치는 스캐터플롯의 점의 크기로 표현하였다. 단계가 진행될 수록 가중치값의 변화가 커지는 것을 볼 수 있다.
plt.subplot(421);
plot_result(model_ada.estimators_[0], "1번 분류모형의 분류 결과", s=10)
plt.subplot(422);
plot_result(model_ada.estimators_[1], "2번 분류모형의 분류 결과", s=(4000*model_ada.sample_weight[0]).astype(int))
plt.subplot(423);
plot_result(model_ada.estimators_[2], "3번 분류모형의 분류 결과", s=(4000*model_ada.sample_weight[1]).astype(int))
plt.subplot(424);
plot_result(model_ada.estimators_[3], "4번 분류모형의 분류 결과", s=(4000*model_ada.sample_weight[2]).astype(int))
plt.subplot(425);
plot_result(model_ada.estimators_[4], "5번 분류모형의 분류 결과", s=(4000*model_ada.sample_weight[3]).astype(int))
plt.subplot(426);
plot_result(model_ada.estimators_[5], "6번 분류모형의 분류 결과", s=(4000*model_ada.sample_weight[4]).astype(int))
plt.subplot(427);
plot_result(model_ada.estimators_[6], "7번 분류모형의 분류 결과", s=(4000*model_ada.sample_weight[5]).astype(int))
plt.subplot(428);
plot_result(model_ada.estimators_[7], "8번 분류모형의 분류 결과", s=(4000*model_ada.sample_weight[6]).astype(int))