Ch5. Overfitting and Its Avoidance
- 숙명여자대학교 소프트웨어학부 데이터사이언스개론 - 박동철 교수님
# Overfitting
- data science의 가장 중요하고 근본적인 개념 중 하나
- model을 만드는 것에 있어 flexibility를 너무 허용하면 만들어진 model이 내가 가지고 있는 특정한 dataset에만 상응될 수도 있음
- Overfitting
> model이 training dataset을 넘어 일반화하지 못할 때
> 새로운(that we have not yet seen) instances에 대해 예측하지 못할 때
# A Hypothetical Example
- 고객 이탈을 줄여야하는 manager가 있음
- data scientist는 아래 내용을 따라야 함
> manager로부터 고객이 남을지 이탈할지에 대한 과거의 데이터(historical data)를 받음
> data로부터 model을 구축하고 model에 대한 code를 manager에게 다시 보냄
- manager는 아래 내용에 따라 model의 수행을 확인함
> model을 통해 historical data를 검증해 봄
> model이 100% 정확도를 보임
- 이 모델은 좋은 모델인가? NO → 그런(정확도가 100%인) model을 만들기 매우 쉽기 때문
- Example (table model)
> training data를 모두 기억하고 같은 data가 있는지 찾아 예측함
table model의 복잡도: table에 들어있는 entry의 숫자 = row의 개수
- table model의 문제점은 무엇인가?
> training data에 완벽하게 맞음
> 새로운(previously unseen) data를 일반화하지 못함
# A Fundamental Trade-Off
- 더 복잡한 model을 사용한다면
> 실제 복잡성을 더 잘 포착하여 보다 더 정확함
> overfitting의 가능성이 증가함
- best 전략
> overfitting을 제거하는 단일 과정이 없음
> overfitting을 인지하고 원리 원칙적으로 complexity를 조절함 → overfitting ↑ → complexity ↓해야 함
# How To Recognize Overfitting
- Fitting graph
> complexity에 대한 함수로써 model의 정확도를 보여줌 → 구체적으로는 정확도의 변화를 보여주는 것임
* complexity에 대한 함수 = 모델이 더 복잡해져 가는 것에 따라 변함
70~80% training data를 가지고 모델을 만든 후
Holdout data를 사용해 모델의 complexity에 대한 정확도의 변화를 보이는 것
* 그래프의 error 축은 accuracy로 나타낼 수도 있으며 이에 대한 관계는 반대다
(error ↑→ accuracy↓)
- Holdout Data
> 이미 target value를 아는 data를 hold out 한 것
> model을 구축할때 사용하는 것이 아닌 model의 일반화 수행을 평가하는 데 사용
fitting graph
- model이 충분히 복잡하지 않을 때
> training 그리고 holdout data 둘 다에 대해 정확하지 않음 → underfitting
- model이 너무 복잡할 때
> training data에 대해 더 정확해짐
> 그러나 holdout data에 대해서는 덜 정확해짐 → overfitting
- Example: 고객이탈 table model
> 극단적인 예에서 fitting graph는 특이함
> row의 수는 model의 complexity로 생각됨
- model이 복잡해짐에 따라..
> training data set의 더 많은 부분을 기억할 수 있음 (error ↓)
> holdout data error는 어떤 값에서 시작하고 감소하지 않음
> b: the percentage of churn cases in the population(holdout data)
ex) training data(stay:2만 명, churn:5만 명), holdout(stay:2만 명, churn:1만 명)이라 할 때
table model에는 churn하는 5만 명의 data가 있을 것임 이 model에 대해 holdout data를 적용하면
1만 명의 churn data가 model에 있는 churn(5만 명)의 데이터와 overlap 되지 않으므로 stay라고 분류됨.
따라서 2만명의 stay 값을 가지는 data는 잘 분류되고 1만 명의 churn data를 가지는 data는
잘못 분류되므로 base error rate가 1/3가 되는 것임
# Overfitting in Tree induction
- 우리는 반복적으로 data를 작고 작은 data subset으로 나누면서 classification tree를 만듦
- 극적인 classification tree: 모든 leaf node가 pure 해질 때까지 data를 나눔
이 tree에서 training data에 대한 정확도는 100% 임
- tree의 complexity = node의 개수
> tree는 어느 accuracy나 가질 수 있게 만들 수 있음
> tree가 커질수록, 그것은 ovefit 할 경향을 가짐
overfit 된 tree의 test(holdout data)에 대한 정확성은 optimal tree보다 떨어짐
* Sweet spot: training data의 정확성 ↑되고 holdout data의 정확성은 ↓되기 시작하는 구간으로
holdout dataset의 성능, training dataset의 성능이 적당히 절묘하게 비슷해지는 지점.
즉, holdout dataset에서 성능이 떨어지기 시작하는 지점으로 optimal 한 성능을 보여주는 지점임
> Tree size = 1,..., 100 → training accuracy: ↑, holdout accuracy: ↑
> Tree size = 100,..., 1000 → training accuracy: ↑, holdout accuracy: ↓
* tree의 size가 너무 커지면 tree는 일반적인 모집단의 특성이 아닌 training set의 detail들을 갖기 시작함
→ 따라서 tree의 size를 제한해야 함
> 그러나 정확한 sweet spot을 이론적으로 찾을 수 있는 방법이 없음
→ 기술적인 경험에 의존해야 함
# Overfitting in Mathematical Function
- 더 복잡한 mathematical function을 만드는 한 가지 방법은 항이나 변수를 추가하는 것임
- example
> A linear model: f(x) = w0 + w1x1 + w2x2 + w3x3
> A more complex model: f(x) = w0 + w1x1 + w2x2 + w3x3 + w4x1² + w5x4
- 더 많은 속성을 사용하면, model이 training data에 더 잘 맞을 수 있음 (overfitting의 위험도 함께)
- To avoid overfitting
> informative attributes만 고를 수 있음
> overfitting을 확인하기 위해 holdout technique을 사용할 수 있음
# Overfitting Linear Function
①
②
| original dataset (Both Logistic regression 과 SVM은 같은 line을 학습함) |
Logistic regression: 상당히 많이 움직임 SVM: 거의 움직이지 않음 → Logistic regression이 overfitting처럼 보임 * 가운데의 빨간 별 처럼 outlier 하나까지 모두 분류하는 것이 좋은 것은 아님 |
| Logistic regression과 SVM이 f(x) = w0 + w1*Sepal + w2*Petal 일 때 |
Logistic regression과 SVM이 f(x) = w0 + w1*Sepal + w2*Petal + w3*Petal² → More flexibility (단순한 선이 아닌 포물선임) |
# From Holdout Evaluation to Cross-Validation
- holdout evaluation
> 약간의 data를 hold out 하고 holdout data를 제외하고 model을 만듦
> holdout data에 대해 model의 accuracy를 평가함
> model의 일반적 수행을 평가하는 것이 목표임
* test data = holdout data
- 문제점
> single estimate
> model의 정확도를 한번 측정하는 것으로 확신을 얻을 수 있나?
> test data의 운 좋은 단일 선택일 수 있음
# Cross-Validation (CV)
- 더 정교한 holdout 평가 방법
> dataset에 걸쳐 holdout 평가를 여러 번 수행함
- 평가된 수행에 대해 statistic을 얻을 수 있음
> 평균(Mean): 평균적으로 기대할 수 있는 수행
> 변화(Variable): dataset에 따라 성능이 어떻게 달라지는지 알 수 있음
# k-fold Cross-Validation
- k-fold: data를 몇 개의 구간으로 나눌까?
# (Revisited) The Churn Dataset
- 고객 이탈 문제를 다시 고려해 봄
> data에 기반하여 어떤 고객이 이탈할지 예측해 봄
- Our data
> 20000명 고객의 historical data 집합이 있음
> 각 고객은 아래 속성에 의해 묘사됨
- 첫 번째 질문: 이 속성들은 각각 얼마나 좋은가?
> 이것에 대해 각 속성에 대해 information gain을 측정해볼 수 있음
- churn data로부터 학습된 classification tree
- tree를 구축하는 것을 언제 멈춰야 할까?
> 20000 예시에 대해 20000개의 leaves를 가질 때까지 분류해야 하나?
→ Yes, 그러나 모델이 너무 복잡해지기 전에 멈춰야 함
> 이 문제는 모델의 일반성 그리고 overfitting과 밀접하게 연관되어 있음
- tree의 정확성은 어떻게 측정할까?
> 원래 dataset에 tree를 적용하고 tree가 73%의 정확도를 수행했다고 가정하자
> 이 수치를 믿어도 되는가? 다른 datset에 적용했을 때도 73%의 정확성을 얻을 수 있을까?
> 73%의 정확성이 좋은 것을 의미하는 가? 쓸만한 가치가 있는 정확도인가?
# The Churn Dataset Revisited
- churn dataset 예시에서 우리는 정확성 73%를 믿을 수 있는가?
> No, 이 수행 측정은 training datset에 대해 이뤄진 것임
> overfitting이 일어날 가능성 ↑
- 그래서 더 잘 평가하기 위해 cross-validation을 사용
- 10-fold cross validation의 결과
> claasifiaction tree의 평균 정확도(cross validation 해서 얻은 accuracy) = 68.6% < 73%
→ 일반적으로 만든 model의 정확도 73%는 overfitting이 있었다는 것을 보여줌
> 다른 fold에 대한 수행에 있어 변화가 있음 따라서 우리는 수행이 어떻게 달라지는 지를 추정하기 위해
변화를 사용할 수 있음
> Logistic regression은 약간 낮은 수행을 보임
→ 큰 변화(그래프 각각의 폭의 변화가 큼)를 보이는 낮은 평균의 정확도 (64.1%)
> 이 특정한 datset에서만, classification tree가 더 좋은 수행을 보이는 것
항상 절대적으로 classification tree가 좋은 것은 아님
# Learning Curves
- 일반적으로, model의 일반적인 수행은 한 시점까지 더 많은 training data를 사용할 수 있게 되면서 개선됨
- Learning curve
> training data size에 대해 일반적 성능을 나타낸 그래프
> 즉, training data size에 따라 성능이 어떻게 달라지는지 보여주는 것임
- Learning curve에 대한 observation
> decision tree는 logistic regression보다 더 flexible 함
→ linear model(ex. SVM, linear regression, logistic regression): not flexible/ tree: flexible
> For smaller data: tree induction이 더 잘 overfit 되는 경향 있음
→ tree induction에서 leaf node가 거의 끝까지 갈 수 있음
→ logistic regression이 smaller data에서 더 잘 수행함
> For larger data: tree induction의 flexibility가 이점이 됨
→ tree는 feaures과 target 사이에 상당히 nonlinear 한 관계를 나타낼 수 있음
→ Logistic regression은 더 overfit 한 경향이 있음
- Learning Curve VS. fitting graphs
> Learning curve는 training data에 대한 일반적인 성능을 보여줌 → training data의 양이 중요
> fitting graph는 training data로 만든 model에 대한 성능을 holdout data로 검증함 → model의 복잡도
# Overfitting Avoidance and Complexity Control
- Regularization
> overfitting을 피하기 위해 model의 복잡성을 조절하는 것
* model의 복잡도가 높으면 overfitting도 증가하므로 복잡도를 낮춰야 함
- Example
# Regular for Tree Induction
- tree induction의 주요 문제점
> leaf node가 pure 해질 때까지 계속 구축됨
> 큰 결과가 만들어지고, data에 overfit 되는 복잡한 tree가 될 가능성이 있음
- overfitting을 피하기 위한 3가지 정규화 기술
① Stop growing the tree before it gets too complex
② Grow the tree until it is too large, then "prune" it back, reducing its size
③ Build trees with different numbers of nodes and pick the best
# (1) Limit Tree Size
- 분할할 leaf node의 최소 instance 수를 지정함
> instance의 수가 적은 node는 더 이상 split하지 않고 멈춤
- Example (minimum-instance stopping criterion = 20)
> 각 leaf node의 instance 개수가 20개 미만이면 stop growing
# (2) Prune An Overly Large Tree
- leaves와 branch를 자르고, leaf로 대체함
> 대체하는 leaf는 정확성을 줄이면 안 됨
> pruning가 accuracy를 감소시킬 때까지 이 process는 진행성 subtree에서 반복될 수 있음
- Example
# (3) Build Many Trees And Pick The Best
- 다양한 nodes를 가진 여러 개의 tree를 만들고 그중 좋은 것을 고름 → best accuracy를 가진 것
- Example
# Regularization for Linear Models
- 모델에 사용되는 특징은 어떻게 고를 수 있을까?
- Sequential forward selection (SFS)
> 단지 하나의 feature을 사용하여 만들어진 model을 모두 test 함으로써 가장 best 한 feature xi를 고름
> 처음에 고른 속성에 두 번째 속성을 추가한 모든 model을 test 함으로써 두 번째 best 한 속성 xj를 고름
> 같은 과정으로 3번째 , 4번째.. best 한 속성을 찾아나감
> feature가 test data에 대해 정확성을 더 이상 증가시키지 않을 때 멈춤
- Sequential backward elimination: 선택하는 속성의 개수를 줄여가며 SFS의 과정을 거치는 것
# Nested Cross-Validation
- cross-validation: 이미 모델이 정해져 complexity가 fix 된 상태
ex) The number of nodes in a decision tree = 20
- Nested cross-validation
> complexity parameter의 best 값을 모를 때 사용함
ex) decision tree의 node 수, linear model에서의 특징의 수
> complexity parameter의 best value를 찾을 때 사용
> Nested loop folds (outer loop and inner loop)
- hyperparameter가 선택된 model의 평가에 대한 outer loop
* hyperparameter = complexity parameter
- hyperparameter tuning을 하는 inner loop
> 단점: inner loop의 수의 요소에 따라 run time이 상당히 증가함
> Test: inner cross-validation에서 찾아진 complexity parameter의 best vlaue로 만든 model을
평가하는 데 사용됨
> Training: complexity parameter의 best value 값을 선택하기 위해 사용됨
> inner cross-validation: 각 complexity parameter 값에 대해서, sub-training set을 사용하여
model을 만들고 validation set을 가지고 그것을 평가함.
그리고 best 성능을 보여주는 complexity parameter의 best value를 선택함
> outer loop to select best model
① outer loop에서 각각 나누어진 training data를 위해, 각각 나누어진 best hyperparameter를 결정하고자 inner loop로 들어감
② 결정된 hyperparameter로 model을 수행시킴
③ 변화에 대한 점수를 평균 내고 가장 높은 점수를 가진 model을 선택함
④ 모든 data를 사용해서 선택된 model을 다시 수행시킴
⑤ test data에 대해 test 점수를 계산함
> inner loop to select best hyperparameter
① 각각의 분할된 inner loop에서 모든
hyperparameter set을 가지고 model을 수행시킴
② 변화에 대한 점수를 평균을 내고 높은 점수를 가지면서
가장 best 한 hyperparameter set을 선택함
# (EX) Nested Cross-Validation
- node의 후보 수를 10. 15, 20, 25, 30이라고 가정
> ①에서 tree의 node의 개수가 15일 때의 평균 점수가 가장 높았다고 생각하면
> training으로 그 값을 반환함 즉, node가 15개가 되는 모델을 training datset을 가지고 만드는 것
# Summary
- There is a trade-off between model complexity and the possibility of overfitting
> a complex model may be necessary to model complex data
> But is has the risk of modeling details of a particular data
> An overfitted model will not generalize to other data well
- There is no single choice or technique to eliminate overfitting
> The best strategy is to recognize overfitting by testing with a holdout set
> fitting graph: Has two curves showing the model performance on the training
and test data as a function of model complexity.
The model performance on the test data decreases as overfitting sets in.
- Cross-validation
> A common experimental methodology to estimate the generalization performance of a model
> Split up a single dataset to generate multiple performance measures
> We can obtain the estimated average and variance of performance
- Regularization
> The general method for reining in model complexity to avoid overfitting
> Decision tree: limiting tree size, tree pruning,...
> Linear model: feature selection,...
