Ensemble Methods

Bias-Variance Tradeoff

ML모델을 학습 시킬 때, 항상 문제가 되는 것이 Overfitting입니다.
아무리 Training Data에 딱 맞게 완벽하게 맞춰놓는 것은 의미가 없습니다.
결국은 Test Data가 들어왔을 때 벙찌기 때문이죠.

파란색 점의 위치를 regression하는 문제를 떠올린다면,
다항함수 (k-1차)로 표현을 할 때,
k = 1일 때에는 정확도가 낮지만, k=2, k=3일 때는 정확도가 좋습니다.

근데, k=7까지 높여버리니, 파란 점의 위치를 아주 정확히 맞췄네요.

근데, 오차범위가 상당합니다. 일반성이 떨어져서, 일반데이터 (검증 / 테스트 데이터)에는 일을 제대로 못하네요.

Classification도 똑같습니다. 결정경계를 이렇게 복잡하게 만들어버리면,
overfitting의 가능성이 농후해집니다.

그래서, MSE의 기댓값을 나타낼 때,
기댓값에 영향을 미치는 값이 몇 가지 있는데,

그 중 Bias와 Variance는 서로 반비례 관계를 가집니다.
Bias (내가 만든 모델이 평균적으로 정답과 얼마나 떨어져 있나)
는 모델이 복잡할수록 낮아지고,
Variance(데이터셋이 바뀌면 모델이 얼마나 많이 바뀌나)는 모델이 복잡할수록 높아집니다.

Test Error는 Bias와 Variance의 Tradeoff를 잘 고려해서 그 사이 어귀를 찾아야 합니다.

Bias / Variance

Bias는 모델에서 예측한 값과, 실제 값 사이의 평균적 차이입니다.
적을수록 좋겠죠.

Variance는
Observation Variance : 데이터셋의 참 분포에서, 거기서부터 나오는 불확실성, 측정 오차같은, 어쩔 수 없는 분산. 이 값은 바꿀 수 없는 값이겠죠.

Estimated Model Variance : 우리가 만든 모델이 학습 데이터에 얼마나 많이 영향을 받는가.

이렇게 2종류의 Variance가 존재합니다.

Bias가 높고 Variance가 낮다면, 다음과 같이 approximation은 좀 못하지만,
데이터셋이 바뀌어도 stable한 예측이 유지가 됩니다.

반대로 Bias가 낮고 Variance가 높으면, approximation이 뛰어난데,
데이터셋이 조금만 바뀌어도 예측모델이 미친듯이 널뜁니다.

결국, Bias나 Variance나 둘 다 작으면 좋은데, overfitting 문제 때문에 어쩔 수 없이 Tradeoff를 갖는 것이죠.

Regularization

모델을 바꾸지 않으면서도, 모델의 Complexity를 조정하여
Bias와 Variance 사이를 잘 조정하는 방법 중 하나가 Regularization입니다.

이런 단순한 모델이 존재합니다. (단순?)
$\mathcal{L}(f(x^{(i)}), y^{(i)})$는 예측값과 실제 label 사이의 loss이며,

$\frac{1}{n} \sum_{i=1}^{n} \mathcal{L}(f(x^{(i)}), y^{(i)})$는 결국 loss함수를 정의한 식이 되겠네요.

원래는 저 오차함수를 최소화하는 $\theta$를 찾는 것이 목표였는데,

여기에 이제 $\lambda\Omega(\theta)$를 추가하면서 parameter $\theta$에 대한 값도 우리가 요구하는 듯이
수식을 수정할 수 있습니다.

즉, 원래는 오차함수를 최소화하는 $\theta$만 구하는 것이었는데,

이젠 $\theta$ 자신에 대한 식도 포함해서 전체를 최소화 해야 하는 거죠.

그리고 $\lambda$를 통해 empirical loss와 complexity 조정 중 어디에 더 무게를 둘지 정할 수 있구요.

그래서 $\lambda$가 커질 수록 empirical loss를 줄이는 데에는 크게 신경을 안 쓸테니,
underfitting이 발생할 것이고,

$\lambda$가 작아질 수록 complexity 조정의 의미가 없어지니 overfitting에 가까워지게 됩니다.

위로 갈수록 $\lambda$가 큽니다. bias는 내주고, variance를 챙기겠다는 뜻이죠.
그래서 그런지 데이터가 많이 바뀌어도 엄청 유사한 값이 유지되지만,
정답 (초록색)과는 거리가 있네요.

아래는 $\lambda$가 작습니다. 데이터가 살짝만 변해도 모델이 엄청 튑니다.
대신 정답은 기깔나게 맞췄네요.

Variance가 높을 때에도, 그 변동성 있는 모델들의 평균을 내서 가져가면 되게 Robust한 모델이 나오는 것 아닌가요?

어느정도는 참입니다.

이 아이디어를 기반으로 나온게 Ensemble Method입니다.

Ensemble Methods

조금씩 다른 base model들을 합쳐서, 그 약점들을 보완해보자!
라는 방법론입니다.

모델들이 가진 한계를 극복하고, Generalization과 Robustness를 추구합니다.
하나의 모델이 가진 한계를 조금씩 다른 여러 모델을 합쳐서? 보완하자!

물론, 학습되는 모델들은 조금씩 달라야 하죠.
학습데이터가 다를 수도 있고,
학습데이터가 같아도 알고리즘이 다를수도 있고, (NeuralNet, LR ..)
학습데이터/알고리즘이 같아도 hyperparameter를 다르게 가져갈 수도 있죠.

구현은 쉽습니다. 어떻게 ensemble을 구현할지가 문제에요.

Bagging

Bootstrap Aggregating의 약자입니다.

Bootstrap이라는 샘플링 방식을 적용해 모델을 여러개 만들고,
모델들의 결과를 합친다는 뜻입니다.

각각의 모델 학습은 병렬적으로 가능합니다.
각 모델은 자기에게 주어진 독립적 데이터만 읽기 때문이죠.
RandomForest가 유명합니다.

Boosting

원래 학습데이터로 모델 1을 만듭니다.
모델 1이 오분류한 아이템들은 가중치를 높여 원래 데이터에서 가중치가 조정된 새 데이터를 만들고, 그를 바탕으로 모델2를 학습시킵니다.
모델2가 오분류한 아이템들은 가중치를 높여 . . .

이 경우는 이전모델의 동작에 따라 현재 모델이 쓸 데이터의 instance의 가중치가 바뀝니다.
즉, 직렬적입니다.

AdaBoost가 유명합니다.

우리가 특정 데이터에 대한 전체 데이터 분포 $p_{data}$를 안다고 해봅시다,
보통은 모르긴 해요.

그럼 이 분포를 활용해서 수많은 데이터셋을 생성할 수 있습니다.
밀도를 얼추 반영해서 3개의 dataset을 같은 분포로부터 i.i.d하게 생성했습니다.
(independent, identically distributed)

그리고, 3개의 i.i.d한 dataset에 대해서 classifier $h_i$를 만듭니다.
그 후 초록색 X sample에 대해 red일지 blue일지 예측을 때려보면,
3개의 분류기의 결과가 다를 수 있겠죠? (model을 생성한 base dataset이 다르니까요)

결과적으로는 Red로 예측한게 Blue로 예측한 것보다 많으니, 해당 점에서의 예측 결과를
Red로 두면 됩니다.

Regression도, 수많은 dataset을 바탕으로 수행한 수많은 regression model들은
하나의 data point (점선)에 대해 서로 다른 예측 결과를 냅니다.

이 수많은 model들이 특정 query point에 대해 내는 예측값은?
아마 정규분포..를 따르겠죠? (후에 증명할겁니다.)

Motivation of Bagging

m개의 data set을 i.i.d하게 만들었습니다.
각 data set을 $D_i$ 라고 표현합시다.

그 $D_i$를 바탕으로 학습시킨 분류기를 $h_i$라고 둘 때,
특정 data point $x$에 대해 $h_i$가 내뱉는 값을 $\hat{y_i}$라고 합시다. (그러면 $\hat{y_i} = h_i(x)$가 성립하겠죠.)

그리고 전체 m개의 분류기가 뱉은 $\hat{y_i}$들의 평균을 $\hat y$라고 합시다.
($\hat y = \frac {1}{m}\sum^m_{i=1}\hat{y_i}$)

그럼 이 때의 bias와 variance를 한번 구해봅시다.

$\mathbb{E}[\hat{y}] = \mathbb{E}\left[\frac{1}{m} \sum_{i=1}^{m} \hat{y}_i\right] = \frac{1}{m} \mathbb{E}\left[\sum_{i=1}^{m} \hat{y}_i\right] = \mathbb{E}[\hat{y}_i]$

우선 bias는 변하지 않습니다. $\hat{y_i}$의 합의 평균은 $mE[\hat{y_i}]$가 되니, bias는 불변이죠.

즉, $\hat{y}$의 기댓값은 특정 분류기가 뱉은 $\hat{y_i}$의 기댓값과 같습니다.

즉, $\hat{y}$를 이용해 값들을 표현해도, 수많은 i.i.d한 dataset으로 생성한 $\hat{y_i}$들보다 덜 정확해지지도, 더 정확해지지도 않습니다.

$\text{Var}[\hat{y}] = \text{Var}\left[\frac{1}{m} \sum_{i=1}^{m} \hat{y}_i\right] = \frac{1}{m^2} \sum_{i=1}^{m} \text{Var}[\hat{y}_i] = \frac{1}{m} \text{Var}[\hat{y}_i]$

Variance는 줄어듭니다.
$\text{Var}[\sum{\hat{y_i}}] = \text{Var}(\hat y_1+\hat y_2 + \hat y_3 + ...)$인데, 각 $\hat {y_i}$끼리 독립이라 $\text{Cov}$가 0이고,
그래서 결국 $\text{Var}[\sum{\hat{y_i}}] =m\text{Var} [\hat{y_i}]$가 됩니다.

즉, m개의 모델을 합쳤더니 Variance가 $\frac {1}{m}$으로 줄어들었습니다.
bias는 그대로인데, Variance가 줄어든 매우 행복한 경우네요.

결과적으로,
m을 늘리면 늘릴 수록, 즉 수많은 데이터를 학습시킨 독립적 모델들의 평균을 내면 낼수록,
Variance는 점점 줄어들어, 거의 0이 됩니다.

하지만 현실적으로 computation cost가 너무 커지고,
estimated model variance만 줄일 수 있는거라 결국 전체 Variance가 0이 되는 것은 아닙니다.
또한, 각각의 base model을 만들기 위해 쓴 dataset이 다 독립이다 라는 가정을 했기 때문에,
위에서 $\text{Cov}$가 0이 되어 계산이 편해진건데,
실제 세상에선 그렇지 못합니다.

또, 우린 $p_{data}$를 보유해서, $D_i$를 무한히 뽑아낼 수 없죠.
실제로는 그냥 sampling된 데이터셋 $D$만 보유합니다.

그래서!

학습 데이터를 Random Sampling하여 dataset을 증폭시키는 기술이
Bootstrap Aggregating, Bagging입니다.

원래 dataset에 대해 size가 n인 data를, replacement를 허용하여 생성합니다.
물론 각자는 조금씩 다르죠. 근데 중복데이터는 존재합니다.

원래 데이터셋이 1~10이라면,
$D_1$은 이렇게 중복을 허용하여 10개를 뽑고,
$D_2$도 10개를 뽑고, 그렇게 3개를 만드는거죠.

각 instance 는 한번 뽑힐 때 $\frac{1}{n}$의 확률로 뽑힙니다.
그리고, $(1-\frac{1}{n})^n$의 확률로 단 한번도 안 뽑힙니다.

수학적으로, 각 dataset은 원래 dataset의 $(1-\frac{1}{e})$개의 data만 포함하게 됩니다.

그래서, 원래 Dataset을 바탕으로 여러 dataset을 만들고,
그걸 바탕으로 여러 classifier를 만들고, majority voting을 통해 하나로 합치는 것이
Bagging이 되겠습니다.

원래 데이터셋에서, Bootstrapping으로 3개의 dataset을 만들고,

독립적으로 훈련하여 majority voting을 하여 값을 예측하게 됩니다.

Problem of Correlation

아까 이상적인 case에서는, 각 Dataset끼리 독립이었기에 Cov가 존재하지 않았습니다.
근데, Bootstrap된 데이터들은 하나의 Dataset에서 나온 데이터들이기 때문에, 어쩔 수 없이 독립이 아니게 됩니다.
어떤 상관관계가 존재할 수밖에 없습니다.

그래서, 실제로는 Correlation에 해당하는만큼 덜 줄어들게 됩니다.
$\rho$는 correlation이고, $\sigma^2$는 sample된 데이터셋이 생성한 결과의 variance입니다.

식 자체만 보면, $\rho = 0$인 경우에는 서로 independent하여 $\frac{1}{m}\sigma ^2$로, variance가 줄게 되지만,
$\rho = 1$인 경우에는 $\sigma^2$만 남습니다.

그래서 이걸 완화하기 위해, $\rho$를 낮추기 위해,
모델에 추가적인 변동성을 일부러 넣게 됩니다.
모델의 hyperparameter를 조금씩 더 차이를 준다던가, 해서
그나마 모델들간의 독립성을 좀 더 높여 Correlation를 줄이려고 하죠.

RandomForest

Bagging된 Decision Tree입니다.
추가적인 Random성을 조금 더 가미합니다. (Correlation을 줄이기 위함이겠죠?)

Bootstrapping을 통해 데이터셋을 조금씩 다르게 여러개 만들고,
각 node에서 쪼갤 때 특정 기준 (Entropy)에 따라 attribute마다 정량적인 지표를 갖고 제일 좋은 attribute를 찾아 splitting을 했었는데,
그렇게 해버리면 random으로 sampling을 하더라도 첫번째 dataset에서 좋은 쪼개기 지표가 두번째 dataset에서도 좋은 쪼개기 지표일 가능성이 매우 높습니다.

그래서, 이 경우에는 연관성이 생겨버리기 때문에,
전체 attribute 중 최적 1개를 선택하는게 아니라,
우리가 만든 작은 부분 attribute 중에서 제일 좋은 attribute를 택해 split합니다.

우선 Bootstrapping을 통해 dataset을 만들고,
일부 attribute들 중 제일 좋다고 판단하는 걸로 tree를 만듭니다.
그리고 그 decision tree들을 합칩니다.

각 쪼개진 sample tree들은, 전체 attribute에서 판단하지 않고,
랜덤하게 전체 attribute 중 일부 attribute만 뽑아서 그걸 갖고 tree를 만듭니다.

최악의 경우에는 [키, 몸무게, 성별, ...] 등 좋은 attribute들 냅두고 [학번, 손가락 길이]같이 이상한 attribute가 골라질수도 있겠죠.
하지만 어쨌든 좋은 attribute가 골라질 가능성도 농후합니다!

Boosting

이전 분류기가 잘 분류하지 못한 애들을 가중치를 줘서, 새로 분류기를 거칩니다.

이런 weighted set을 이용해 각각의 분류기를 거치는 겁니다.

AdaBoost

Base Model (Weak Learner)를 여러개 조합을 합니다.
이전에 틀렸던 애들이 있으면, 걔네한테 가중치를 더 줍니다.

처음에 선을 저렇게 그었더니, 3개가 틀렸네요.
그러면, 그 3개에 가중치를 줍니다.

그 다음 분류는 가중치를 더 준 애들을 포함하게 선이 오른쪽에 그어졌습니다.
이번엔 또 다른 3개가 틀립니다.

다음 분류기는 그 틀린 3개를 잘 분류하게끔 분류기가 만들어집니다.

그리고 그 분류기들을 다 합치면 이쁜 분류기가 완성이 되네요.

AdaBoost에선 각각의 단계에서 분류기를 만들어야 하는데,
그 분류기들이 복잡한 알고리즘을 사용하지 않고,
정말 단순하지만, 빠르게 분류하게끔 Weak한 모델들을 사용합니다.

대신 그 Weak model들을 누적해서 전체 성능을 달성하죠.
그 각각을 Weak Learner, 지금은 분류 얘기 하고 있으니 Weak Classifier로 말할 수 있습니다.

Weak Learner는 빠르고 단순해야 해서, Decision Tree를 쓰기도 하는데,
보통 이거보다 더 단순한 Decision Stump (딱 1번만 split하는 거)를 사용합니다.

딱 1번만 자르는 decision tree가 decision stump입니다.

Vertical Classifier : 나는 7개나 맞췄다. (+ 2개, - 5개)
+ 3개를 틀리기는 했는데, 그건 후대에게 넘기겠다. 후대 classifier가 알아서 해다오.

Horizontal Classifier : 오냐, 너가 맡긴 3개 다 분류해줬다.

Weighted Training Set

아까, Boosting에서 틀린 sample에 대해 가중치를 부여하여 더 중요하게 본다고 했습니다.
이것의 구현은 어떻게 될까요?

원래는 이렇게 이진분류만 따졌습니다.
$\sum_{i=1}^{n} \frac{1}{n} \mathbb{I}[h(x^{(i)}) \neq y^{(i)}]$

전체 데이터셋에 대해 틀리게 예측한 것들에 $\frac{1}{n}$이라는 가중치를 줘서 오차로 간주했습니다.
$\sum_{i=1}^{n} w^{(i)} \mathbb{I}[h(x^{(i)}) \neq y^{(i)}]$

이제는 전체 데이터셋에 대해 틀리게 예측한 것에 학습 도중에 바뀌는 weight의 가중치를 줍니다.

물론 처음에는 $w^{(i)}$가 $\frac{1}{n}$이죠.
대신, 이후에 진행할 수록, $w^{(i)}$가 높은 놈을 틀렸을 때 더 많은 오차가 발생하게끔 하여
최대한 Weak Learner들이 가중치 높은 애들을 덜 틀리게끔 합니다.

일반적으로는, $w^{(i)}$를 다 더하면 1이 나오게 normalize합니다.

Overall process of AdaBoost

AdaBoost를 배우기 전에, 용어정리를 먼저 합시다.

Dataset은 이진분류용 dataset입니다. -1이든, +1이든.
그래서 각 Weak Learner들은 입력이 주어졌을 때 -1 또는 +1로 출력합니다.
Loss Function은 정답이면 0, 정답이 아니면 1.

Weak Learner를 T개 학습하며,
각 iteration마다 Weak Learner를 1개 학습시킨다고 합시다.

iteration마다 지금의 Weak Learner가 몇개 맞았는지 Error를 계산하고,
그걸 바탕으로 Classifier Coefficient,
즉 지금 Weak Learner가 최종 모델을 만들 때 얼마나 많은 투표권을 행사할건지를 계산합니다.

그리고, 이 값들을 바탕으로 Data의 weight를 업데이트하여,
다음 Weak Learner가 학습할 수 있게 틀을 세워줍니다.

1. 우선 Sample의 weight를 결정합니다.

맨 처음에는 $w^{(i)} = \frac{1}{n} \text{for all i}$이어야 하죠.

2. 최대한 덜 틀리게끔 구성된 decision stump를 만듭니다.

저 값이 (오차) 최대한 작아지게 하는 모델 h가 t번째 iteration에서 만들어진 weak learner ${h_t}$겠죠.

3. error와 classifier coefficient를 구성합니다.

t번째 stump가 얼마나 좋냐, 안좋냐를 평가하는 지표입니다.
앞서 만든건 저 '오류'를 최소화하는 모델인 $h_t$를 얻어낸거고,
여기서 쓰는건 그 $h_t$의 오차가 얼마나 되는지를 가져온겁니다.

그 후, 그 $error_t$를 이용하여 $\alpha_t$를 구성합니다.

$\alpha_t$는 t번째 stump가 가진 투표권입니다.
$\alpha_t$가 크다는건, 지금 학습하는 $h_t$의 정답이 최종 정답에 반영되는 비율이 높다-
를 의미합니다.

4. 그 $\alpha_t$를 이용해 전체 weight를 update해줍니다.
   

i번째 샘플에 대해서, 정답과 예측값의 곱에 -1을 곱해서,
정답 = 예측값이면 가중치를 낮추고,
정답 != 예측값이면 가중치를 높여서 다음 classifier가 더 잘 분류할 수 있게끔 해주는거죠.

5. 최종적으로는 이런 방식으로 T개의 stump를 학습시킵니다.

Test Data를 넣고, x라는 query point에 대해 모든 stump로 분류를 해봅니다.

물론, 그냥 분류하진 말고 투표권을 보유해서 분류해줘야죠.
그래서, 그 전체 식의 부호를 가지고 분류를 한다~ 해주시면 이해가 될겁니다.

투표권 큰 놈이 $h_t(x)$는 +1이다. 라고 말하면, 그 친구의 영향은 크게 작동하겠죠.
투표권 작은 애가 $h_t(x)$는 -1이다. 라고 해봤자 얼추 무시될거구요.
(Classifier Coefficient에 의해서요!)

Updating Sample Weights

아까 공식에 의해서,

Sample이 오분류 되었다면 $w^{(i)}$는 $w^{(i)}exp(\alpha_t)$, 즉 $w^{(i)}\sqrt{\frac{1-err_t}{err_t}}$로 업데이트됩니다.

아까 $\alpha_t$를 정의할 때 ln을 사용했기 때문에, exp와 합쳐지면 ln이 사라지죠.

Sample이 정분류 되었다면 $w^{(i)}$는 $w^{(i)}exp(-\alpha_t)$, 즉 $w^{(i)}\sqrt{\frac{err_t}{1-err_t}}$로 변합니다.

물론, 재밌는 고찰점은, $err_t$가 0.5보다 작다면, 정분류된 경우에도 weight가 늘고, 정분류된 경우에도 weight가 늘어납니다.

그래서 $err_t$가 0.5보다 작다, 즉 random하게 맞추는 것보다 이 decision stump가 조금은 잘 맞춘다 라는 가정은 필수불가결하게 들어갑니다.

아니, 틀렸는데 오차 weight를 줄여버리면 그 후에는 더 틀릴거잖아요.
AdaBoost를 하는 의미가 없죠.

Example of AdaBoost

맨 처음 $D_1$을 $h_1$이 열심히 분류했습니다.
자기 딴에 최선을 다해서, 초록색 선을 그었습니다.
다음 공식을 이용하면, $h_1$은 총 3개를 틀렸는데요,
initial weight는 $w^{(i)} = \frac{1}{10}$으로 고정됨을 감안하면, $err_1 = 0.3$이 되고,
$\alpha_1$ = $\frac{1}{2} ln\frac{0.7}{0.3} \approx 0.42$가 나옵니다.

그러면 weight의 update도 가능하죠.
각 샘플에 대해서,

오분류된 샘플은 기존 weight인 $\frac{1}{10}$에 $e^{\alpha_t}$을 곱한 $\frac {1}{10} \times \sqrt{\frac{7}{3}}$으로 업데이트가 되고,
정분류된 샘플은 $\frac {1}{10} \times \sqrt{\frac{3}{7}}$로 업데이트가 됩니다.

어차피 error들을 normalize해야 하니,
$10\sqrt{21}$을 각 가중치에 다 곱해주면, (루트 있고 하면 계산이 어렵잖아요.)

정분류된 샘플은 weight가 3이 되고, 오분류된 샘플은 weight가 7이 됩니다.
weight합은 1이어야 하니, 최종적으로 normalize 해주면

정분류샘플은 weight가 1/14가 되고, 오분류샘플은 weight가 1/6이 됩니다.

다음 round에선 새로운 weak learner가 3개를 틀리게 되고,
error공식에 의해 1/14짜리 3개를 틀렸으니 $err_2 = \frac{3}{14} = 0.21$이 되네요.
$\alpha_t = \frac{1}{2} ln \frac{1-err_t}{err_t}$를 이용하면 $\alpha_t \approx 0.66$이 되구요.

이 친구는 좀 더 가중치 높은 애들을 많이 맞춰서 그런지
앞선 weak classifier보다 투표권이 좋습니다.

마찬가지로,
정분류 샘플은 $w^{(i)}\sqrt{\frac{err_t}{1-err_t}}$, 오분류 샘플은 $w^{(i)}\sqrt{\frac{1-err_t}{err_t}}$로 가중치가 업데이트 됩니다.

그리고 또 normalize해주구요.

이래저래 T번 (여기선 3) 계산하여 얻은 classifier들의 투표권 (Classifier Coefficient)까지 고려를 하여, 최종적인 모델을 얻어낼 수 있습니다.

Test Data에 대해 위의 sign식을 대입해서 어떻게 분류할 지 경계를 세울 수 있죠.

RandomForest와 AdaBoost가 둘 다 DecisionTree보다는 같거나 더 좋네요.
일반적으로 Ensemble을 하면 만들어진 결정 경계가 더 안정적이다 라고 볼 수 있을 것 같습니다.

하나 더 볼 것은, AdaBoost와 RandomForest의 결과는 Ensemble로 만들어진 것이라,
완전 새빨갛고 완전 새파란 부분은 모든 모델이 동의한 경계지만,

조금 애매한 색깔의 부분은 모델들마다 하는 말이 달랐다- 정도로 이해하면 될 것 같습니다.

AdaBoost Minimizes Training Error

각각의 Weak Learner의 Error를 $0.5$보다 $\gamma$만큼 낮다고 가정을 하면,
즉 Random Predictor보다는 $\gamma$만큼 낫다 라고 가정을 한다면,

최종 모델의 Error가 $exp(-2\gamma^2T)$보다 작다 라고 합니다.

그냥 쉽게, $\gamma$가 크다면, 즉 random한 경우보다 weak learner의 성능이 훨씬 보장이 되어있다면,
iteration을 적게 잡아도 충분히 error를 줄일 수 있고,
$\gamma$가 크다면, iteration을 크게 잡아야 error를 충분히 줄일 수 있다는 것입니다.

이걸 Geometrical Convergence라고 칭합니다.

쉽게, iteration 많이 박으면 error가 줄어든다는 뜻입니다.

Test Error는요?

Generalization Error of AdaBoost

뭐 T를 많이 박으면 Train Error는 많이많이 줄어들겠죠.
0으로 수렴할겁니다.

근데, 그러면 뭐 Overfitting의 가능성이 존재하지는 않을까요?
test error는 어떻게 될까요?

Overfitting이 가능하긴 합니다. 근데 보통은 안 그래요!

Training Error의 수렴과 동시에 Test Error도 쭉 줄어들어 어느 부분에 수렴합니다.

되게 Robust하죠.

데이터의 특성에 따라 Overfitting이 일어날 수도! 있습니다.
근데 그나마 robust하다, 이정도.

Summary

Ensemble method는 여러 모델을 합쳐서 안정적 모델을 만드는 방법입니다.
Bagging / Boosting이 있습니다.

Bagging에선 Bias는 안 줄어들고,
Variance는 줄어듭니다.
물론 완벽히 줄진 않지만, Observational Variance때문에 0은 불가능하고,
Bootstrapping 과정에서의 dataset간의 correlation때문에 역시 0은 안됩니다.

Boosting에선 Bias는 줄어듭니다.
대신 역시 overfitting 가능성도 존재합니다.

Boosting을 하고 나면 일반적으로는 Variance가 낮아지기를 기대합니다.