다운로드
작성자: 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 클래스를 서브클래싱하여 가중치를 속성으로 저장하도록 수정한 모형을 사용하였다.

In [1]:
from sklearn.datasets import make_gaussian_quantiles
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import AdaBoostClassifier

X1, y1 = make_gaussian_quantiles(cov=2.,
                                 n_samples=100, n_features=2,
                                 n_classes=2, random_state=1)
X2, y2 = make_gaussian_quantiles(mean=(3, 3), cov=1.5,
                                 n_samples=200, n_features=2,
                                 n_classes=2, random_state=1)
X = np.concatenate((X1, X2))
y = np.concatenate((y1, - y2 + 1))

class MyAdaBoostClassifier(AdaBoostClassifier):
    
    def __init__(self,
                 base_estimator=None,
                 n_estimators=50,
                 learning_rate=1.,
                 algorithm='SAMME.R',
                 random_state=None):

        super(MyAdaBoostClassifier, self).__init__(
            base_estimator=base_estimator,
            n_estimators=n_estimators,
            learning_rate=learning_rate,
            random_state=random_state)
        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):
    x1_min, x1_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    x2_min, x2_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    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"):
        idx = np.where(y == i)
        plt.scatter(X[idx, 0], X[idx, 1], c=c, s=s, alpha=0.5, label="Class %s" % n)
    plt.xlim(x1_min, x1_max)
    plt.ylim(x2_min, x2_max)
    plt.xlabel('x1')
    plt.ylabel('x2')
    plt.title(title)
    plt.colorbar(cs)
    if legend:
        plt.legend()
    plt.grid(False)

plot_result(model_ada, "에이다부스트(m=20) 분류 결과")

각 단계의 분류 모형에 대한 가중치 값과 분류 모형의 분류 결과를 시각화하면 다음과 같다. 데이터의 가중치는 스캐터플롯의 점의 크기로 표현하였다. 단계가 진행될 수록 가중치값의 변화가 커지는 것을 볼 수 있다.

In [2]:
plt.figure(figsize=(10, 15))
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))
plt.tight_layout()