- 모델을 만들 때 너무 flexible하게 만들면 모델이 특정한 데이터셋(훈련 데이터셋)에 너무 적합해진다.
- 모델이 훈련 데이터셋을 넘어선 일반적인 데이터셋에는 잘 적용되지 않는 경우이다.
- 모델은 새로운 데이터 개체도 잘 예측해야 한다.
2. 근본적인 부작용
- 더 복잡한 모델을 사용하면 정확도는 높아지겠지만, outfitting의 가능성 또한 높아진다.
- 한번에 overfitting을 제거할 방법은 없다.
- 가장 좋은 전략은 overfitting을 인지하고, 원칙적인 방법으로 복잡도를 조절하는 것이다.
- fitting graph : 복잡도 함수로써 모델의 정확도를 보여주는 그래프이다.
- 보통 모델을 만들 때 훈련 데이터에서 일정 부분을 holdout data로 빼놓고 훈련 데이터로 모델을 만든 다음 정답을 알고 있는 테스트 데이터로 정확도를 평가한다.
- 조금 더 general한 정확도를 측정할 수 있다.
- 위의 그림에서 오른쪽이 fitting graph이다.
3. overfitting 인지
- 모델이 충분히 복잡하지 않을 때 : 훈련데이터와 테스트 데이터 모두에서 정확도가 낮다. → underfitting
- 모델이 너무 복잡해질 때 : 훈련데이터에서는 정확도가 높아진다. 하지만, 테스트 데이터에서는 정확도가 낮아진다. → overfitting
- (ex) : customer churn table model.
- 극단적인 예시는 fitting graph가 독특할 것이다.
- 행의 개수가 많을수록 복잡도가 커질 수 있다.
- learning에 'churn' data만 넣고, 여기에 없는 데이터는 'stay' data로 인식하도록 했다.
- 모델이 증가하면서 훈련 데이터의 에러는 감소하지만, 테스트 데이터의 에러는 어느 특정 값에서 시작해서 변하지 않는다.
- 이유 : 학습을 할 때 churn data만 put했다. 그러면 테스트 데이터는 그 안에 포함되어 있지 않기 때문에 모두 'stay' data로 인식한다. 하지만 그 중에 churn data가 있을 것이다. 따라서 (holdout 'churn' data) / (holdout data) 의 값이 holdout data의 base error rate (=b) 가 된다.
4. overfitting in tree induction
- 극단적인 classification tree : 모든 leaf node들이 pure할 때까지 데이터를 나눈 tree
- 정확도는 100% 일 것이다.
- overfitting 되었을 확률도 ^^..
- tree 모델의 복잡도는 노드의 개수에 비례한다.
- tree 노드 개수에 제한이 없다면 어느 정확도에도 맞출 수 있을 것이다.
- 따라서, tree가 자람에 따라 overfit 되는 경향이 있다.
- fitting graph for tree induction
- ex) tree가 모집단의 특징이 아니라 훈련 데이터의 디테일한 부분을 고려하기 시작했을 때..
- holdout data의 정확도가 떨어지는 순간 (= overfit이 시작되는 순간) 을 "sweet spot" 이라고 한다.
- 그러므로 위의 경우 노드가 100개 정도 되는 순간부터 overfitting이 된다고 볼 수 있다.
- 따라서 우리는 tree의 크기를 이 사이즈 (100) 로 제한해야 한다.
- 하지만, 이론적으로 sweet spot을 정확하게 찾을 방법은 없다.
- 따라서 이 부분은 데이터 과학자의 경험에 의해 결정해야 한다.
5. overfitting in mathematical functions
- 수학적 함수를 복잡하게 만드는 한 가지 방법은 변수나 항의 수를 늘리는 것이다.
- 더 많은 속성들을 사용하면서 모델은 훈련 데이터에 더 적합해질 수 있다. ( + overfitting 위험성)
- 즉, 변수나 항을 늘릴수록 훈련 데이터셋에서의 정확도는 증가한다.
- overfitting을 피하기 위해서는 오직 정보를 얻을 수 있는 유용한 속성들만 사용하고,
- holdout technique을 활용해서 overfitting을 확인할 수 있다.
6. Holdout Evaluation
- 모델을 만들 때 holdout data를 빼놓고 형성한다.
- holdout data를 가지고 모델의 정확도를 평가한다.
- 목표는 모델의 일반화 성능을 추정하는것이다.
- 답을 알고 있고, 훈련할 때 사용하지 않았기 때문에 정확도를 평가할 수 있다.
- 문제
- 이 테스트로부터 얻은 성능의 추정값은 단지 한번의 테스트를 통한 추정값이다.
- 한 번의 추정만으로 모델 정확도에 확신을 얻는 방법은 운이 좋게 테스트 데이터를 한번에 잘 고르는 방법이 있겠다.
7. Cross-Validation (CV)
- holdout evaluation 의 더욱 정교화된 방법이다.
- holdout 평가를 여러번 진행한 뒤 그것의 통계값을 이용하는 방법이다.
- 추정된 성능에 대해 몇가지 통계값을 얻을 수 있다.
- mean 평균 : 평균적으로 어느 정도의 성능이 예상되는가
- variance 분산 : 데이터셋마다 성능이 얼마나 다른가
- k-fold cross-validation : 데이터셋을 k번으로 나누어서 나눈만큼 평가를 반복하는 방법이다.
- (ex) predict which customers are going to churn
1) information gain
2) classification tree
3) 언제 tree building을 멈추는가?
- 그렇게 복잡해지기 전에 멈춰야 한다.
- 이 문제는 model generality와 overfittingr과 밀접한 관련이 있다.
4) tree를 원래 데이터셋에 적용했을 때 정확도가 73%이다.
- 이 값을 믿을 수 있는가? 다른 데이터셋에 적용해도 73%가 나올까?
- 정확도가 73%인 것이 이 모델이 좋다는 의미인가? 좋지 않다는 의미인가?
8. Learning Curves
- 일반적으로, 모델의 일반화 성능은 어떠한 지점까지는 훈련 데이터 수를 증가시킴으로써 가능하다.
- learning curve : tree와 logistic regression에서 훈련 데이터 크기에 따른 일반화 성능을 나타낸 그래프이다.
- observations
- decision tree가 logistic regression에 비해 더 유연하다.
- 크기가 작은 데이터셋에 대해서는 logistic regression이 더 낫다.
- 크기가 큰 데이터셋에 대해서는 tree가 더 nonlienar 관계를 잘 표현한다.
- learning curve vs. fitting graphs
- learning curve : 훈련 데이터의 일반화 성능을 보여준다. (x축 : training data 양)
- fitting graph : 훈련 데이터 성능과 holdout 데이터 성능 2가지 모두 보여준다.
9. Overfitting Avoidance and Complexity Control
- Regularization : 가장 대표적인 overfitting avoid 방법, 모델의 복잡도를 줄이는 방법이다.
9-1. for tree induction
- main problem
- leaf node들이 순수해질 때까지 tree를 키우는 것
- 이로 인해 크고 복잡한 데이터가 데이터에 맞지 않을 수 있다.
- 3 regularization
- 더 복잡해지기 전에 멈추기
- 충분히 tree 크기가 커질 때가지 키운 다음에, '가지치기' 해나가면서 다시 사이즈 줄이기
- 서로 다른 크기를 가진 tree를 여러 개 만든 다음, 최선의 모델 선택하기
1) limit tree size
- 분할된 leaf node에 들어갈 개체의 최소 개수를 정해둔다.
- 즉, 최소 개수 이하의 수가 되면 더이상 분할하지 않는다.
- 이 경우, 최소 개수를 20개로 정했기 때문에 각 그룹의 개체 수가 20개 이하가 되었을 때 growing을 멈췄다.
2) Prune An Overly Large Tree
- node와 branch들을 잘라내고, 그자리를 leaf node로 바꾸는 방법이다.
- 대체했을 때 정확도가 낮아지지 않을 때까지 진행한다.
- 성능이 떨어지지 않을 때까지 하위 그룹에서 반복되며 진행될 수 있다.
3) Build Many Trees And Pick The Best
- tree를 많이 만들어놓고, 그 중 가장 정확도가 높은 tree를 택하는 방법이다.
9-2. for linear models
- 항이 많을수록 복잡하다.
1) Sequential forward selection (SFS)
- 순차적으로 항을 한 개씩 골라서 성능을 테스트한다. 그 중 가장 정확도가 높은 xᵢ를 선택하여 f(x) 에 넣는다.
- 그 다음, 처음으로 추가한 항을 포함하여 또 한 개의 항을 골라서 성능을 테스트한다. 그 중에서 가장 성능이 좋은 xᵢ를 선택하여 f(x) 에 넣는다.
- 이 과정을 계속 반복한다.
- 항을 추가하는 것이 테스트 데이터에서의 정확도를 더이상 높이지 않을 때까지 반복한다.
2) Sequential backward elimination (SBE)
- 위의 과정을 반대로 진행하는 것이다.
- 전체 f(x)에서 항을 한 개씩 선택하여 제거한 후 성능을 테스트한다.
- 제거했을 때 가장 성능이 좋은 xᵢ를 선택하여 제거한 후, 그 다음 또 항을 한 개 골라서 제거하고 성능을 테스트한다.
- 이 과정을 계속 반복한다.
- 마찬가지로 항을 제거하는 것이 더이상 정확도를 높이지 않을 때까지 반복한다.
10. Nested Cross-Validation
- 중첩된 CV
- 모델의 복잡도를 가장 크게 좌우하는 파라미터가 무엇인지 모를 때 사용한다.
- (ex) decision tree → number of nodes, linear model → number of features ···
- 즉, 복잡도 파라미터의 최적값을 찾기 위해 사용한다.
- (ex) What is the best number of nodes in a decision tree?
- (양쪽 경계 값들의 차이) : (키 값과 왼쪽 경계 값의 차이) = (양쪽 범위의 거리) : (탐색 위치와 왼쪽 경계의 거리 차이)
#include <stdio.h>
int interpolate_serarch (int list[], int size, int key);
void main()
{
int size = 12;
int key = 39;
int pos;
int list[] = {2, 3, 5, 7, 8, 10, 13, 20, 25, 39, 45, 55};
pos = interpolate_search(list, size, key);
printf("%d is in %d\n", key, pos);
key = 2;
pos = interpolate_search(list, size, key);
printf("%d is in %d\n", key, pos);
key = 55;
pos = interpolate_search(list, size, key);
printf("%d is in %d\n", key, pos);
}
int interpolate_search(int list[], int size, int key)
{
int pos;
int left = 0;
int right = size - 1;
while (left <= right) {
pos = left + (key - list[left]) * (right - left) / (list[right] - list[left]);
if (list[pos] < key)
left = pos + 1;
else if (list[pos] > key)
right = pos - 1;
else return pos;
}
return -1;
}
5. 해싱 탐색
- 탐색 키에 직접 산술적인 연산을 적용하여 탐색 키의 정보가 저장되어 있는 테이블 상의 위치를 계산하고 이 주소를 통해서 정보에 접근하는 방식이다.
- 즉, 반복적인 비교를 수행하는 것이 아니라, 키 자체에 있는 해답을 해시 함수를 통해 찾아내는 것이다.
- 시간 복잡도는 이론적으로 O(1)로 입력의 수 n에 상관없이 일정한 상수 시간을 갖는다.
- (ex) Dictionary
- Entry (key, value) // (word, definition)
- Applications
- Word / Thesaurus references
- Spelling checker in word processor or editor
- Electronic signature encoding/decoding
- Operations
- determine if a particular symbol(key) exists in the table (단순조회)
- retrieve the attributes of a key (키의 속성값을 참조하는 연산)
- modify the attributes of a key (키의 속성값 변경)
- insert a new entry with a key and value (새로운 entry 추가)
- delete an entry (entry 삭제)
해싱의 원리
5-1. Terms
- 해시 테이블 : 명칭(identifier)들이 저장된 고정된 크기의 표
- 명칭 밀도(ID) : 전체 명칭의 개수(T) 중 해시 테이블에 적재된 명칭 개수(n)의 비율 = n / T
- 적재 밀도(LD) : 해시 테이블의 크기에 대해 적재된 명칭 개수의 비율 = n / N
- 동의어(synonym) : 해시 테이블의 동일한 버켓 주소로 매핑된 서로 다른 명칭들, f(i₁) = f(i₂) 이면 i₁와 i₂는 동의어이다.
- 오버플로우 (overflow) : 명칭 i가 이미 꽉 찬 버켓으로 해싱(매핑)되는 경우 오버플로우가 발생한다고 말한다.
- 충돌 (collision) : 두 개의 서로 다른 명칭이 해시 테이블의 같은 버켓 주소로 매핑되면 충돌이 발생한다고 한다. 버켓의 크기가 1이면 충돌과 오버플로우가 동시에 발생한다.
- 해시 함수 : 해시 함수는 계산이 쉬워야 하고 명칭 간의 충돌을 최소화하여야 한다. 또한, 비대칭 편중분포를 막아야 한다.
- 균등 해시 함수 : 각 버켓에 적재될 확률이 1/b 인 해시 함수 (P[f(x) = i] = 1 / b
- 중간 제곱 해시 함수 : 명칭을 2진수로 변환한 후 제곱한 결과값에서 중간의 일부분을 해시 테이블 주소로 활용하는 함수, 테이블에 2ⁿ개의 버켓이 존재한다면 n개의 비트를 추출한다. collision을 최소화하기 위해 사용된다.
- 나눗셈 해시 함수 : 명칭을 특정 수로 나눈 나머지를 해시 테이블 주소로 사용하는 방법,예를 들어 해시 테이블 크기가 D라면 명칭 x를 D로 나눈 나머지 (0 ~ D-1)을 주소 값으로 사용한다. 이때 D는 분포에 영향을 주기 때문에 "소수"를 사용하는 것이 가장 좋고, 짝수는 사용하지 않는다. 나누는 수로 짝수를 사용하면 편중분포가 나타나기 때문이다.
- 폴딩 해시 함수 : 명칭에 해당하는 비트 열을 해시 테이블 크기만큼 여러번 접어서 주소값으로 사용하는 것이다.
- 이동 폴딩 : 명칭을 k 자리수로 분할한 뒤 순서대로 더한 결과값을 오른쪽에서 k자리 만큼 추출하여 주소 값으로 사용
- 경계 폴딩 : 분할한 문자열에서 짝수 번째 문자열을 뒤집어서 덧셈을 수행한 후 k 자리의 문자열을 추출하여 사용
- 키 분석 해시 함수 : 명칭의 구성과 내용을 미리 예측할 수 있는 경우에는 명칭을 분석하여 해시 테이블 주소로 사용할 키 값을 추출하는 방법을 사용할 수 있다. 예를 들어서 명칭이 학번일 경우, 앞의 두 자리는 입학년도임을 알고 그 부분은 배제하고 생각할 수 있다.
5-2. Static Hashing
- 해시 테이블의 크기가 고정되어있어 프로그램을 변경하지 않는 한 크기가 변경되지 않는 해싱 탐색 방법이다.
cf) Dynamic Hashing - 키 충돌 빈도에 따라 유연하게 해시 테이블 크기를 재구성하는 방법이다.
1) 탐색된 버켓에 삽입하려는 명칭이 이미 저장되어 있는 경우 : 중복된 명칭으로 보고하고 오류 처리 or 특정 필드 값 갱신
2) 탐색된 버켓이 비어 있는 경우 : 해당 버켓에 명칭 저장
3) 탐색된 버켓이 x가 아닌 다른 명칭을 포함하고 있는 경우 : 다음 버켓 탐색 지속
4) 탐색 결과 홈 버켓ㅇ로 다시 돌아온 경우 : 전체 버켓이 모두 꽉 찬 상태 → 오류 보고 후 종료
- 문제점 : 명칭들이 서로 모여서 클러스터를 형성한다. 충돌 횟수가 증가할수록 탐색 속도도 느려진다.
- 해시 함수 정의
- 키 (명칭)들을 ASCII 숫자값으로 변환한 뒤 해시 주소를 계산하는 방법이다.
// sum of ASCII codes of string chars
int transform (char *key)
{
int number = 0;
while (*key) // NULL 값이 아니면
number += *(key++); // 정수 + 문자 -> 문자가 ASCII 코드로 변환됨
return number;
}
int hash (char *key)
{
return (transform(key) % TABLE_SIZE);
}
- (ex)
F
O
R
\0
이 경우 number는 F, O, R 의 ASCII 코드의 합이 된다. 그리고 그 합을 table size로 나눈 나머지가 주소가 된다.
- 따라서 함수를 호출할 때마다 함수의 지역 변수, 복귀 주소 등 컨텍스트 정보를 활성 레코드에 저장해야 한다.
- 장점 : 알고리즘을 깔끔하게 표현할 수 있다.
- 단점 : 함수를 실행할 때마다 메모리에 환경 변수를 저장하기 때문에 메모리의 소모가 일어난다.
2. 팩토리얼 예제
- n! = 1 x 2 x ... x (n-1) x n = (n-1)! x n
- 같은 일 (곱셈) 을 반복하면서 n = 0이면 n! = 1 이라는 종결 조건이 포함되어있기 때문에 재귀 호출을 사용할 수 있다.
long factorial (int n)
{
if (n == 0)
return 1;
else
return n * factorial (n-1);
}
이와 같이 n = 0 이면 1을, n > 0 이면 n * (n-1)! 을 반환하는 형식으로 표현할 수 있다.
3. 최대공약수 (GCD) 예제
- 공통으로 나누는 수 중 가장 큰 수
- 조건 (by 유클리드 호제법)
- gcd (x, y) = gcd (y, x % y) (if (y > 0))
- gcd (x, 0) = x
ind gcd (x, y)
{
if (y == 0)
return x;
else return gcd (y, x % y);
}
4. Binary Search 이진 탐색
- 정렬된 항목 리스트에 대해서 중간값과 크기를 비교하고 그 결과에 따라 가능성이 있는 절반의 리스트에 대해서만 과정을 반복하는 탐색 알고리즘이다.
- 한 번 비교할 때마다 탐색 대상 원소의 수가 절반으로 감소한다.
- 원소의 수가 n개일 때 이진탐색은 총 log₂ⁿ 번의 비교 횟수를 요구한다. 따라서 순차 탐색보다 속도가 빠르다.
- 조건은 리스트 안에 겹치는 숫자가 없어야 한다는 것이다.
-while문과 if문을 이용한 이진탐색
#include <stdio.h>
int binsearch (int mylist[], int item, int left, int right);
void main()
{
int pos, maxnum = 12, item = 60;
int mylist[] = {5, 8, 9, 11, 13, 17, 23, 42, 45, 52, 60, 72};
pos = binsearch(mylist, item, 0, maxnum - 1);
printf("position = %d", pos);
}
int binsearch (int list[], int item, int left, int right)
{
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (list[mid] == item)
return mid;
else {
if (item < list[mid]
right = mid - 1;
else
left = mid + 1;
}
}
return -1;
}
- 재귀호출 형식의 이진탐색
#include <stdio.h>
int rbinsearch (int mylist[], int item, int left, int right);
void main()
{
int pos, maxnum = 12, item = 60;
int mylist[] = {5, 8, 9, 11, 13, 17, 23, 42, 45, 52, 60, 72};
pos = binsearch(mylist, item, 0, maxnum - 1);
printf("position = %d", pos);
}
int rbinsearch (int list[], int item, int left, int right)
{
int mid;
if (left <= right)
{
mid = (left + right) / 2;
if (item == list[mid]
return mid;
else if (list[mid] < item)
return rbinsearch(list, item, mid + 1, right);
else
return rbinsearch (list, item, left, mid - 1);
}
return -1;
}
5. 하노이 타워 예제
- 세 개의 기둥과 크기가 다양한 원판이 존재한다.
- 해결할 문제는 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮기는 것이다.
- 조건
- 한 번에 하나의 원판만 옮길 수 있다.
- 큰 원판이 작은 원판 위에 놓일 수 없다.
- 알고리즘
- 세 개의 기둥 A, B, C 가 있고, A에서 B로 n개의 원판을 옮긴다.
1) A에서 (n-1)개의 원판을 C로 옮긴다.
2) A에 남은 1개의 원판을 B로 옮긴다.
3) C에 있는 (n-1)개를 B로 옮긴다.
- 기둥 a = 1, b = 2, c = 6 - a - b // a, b 제외한 빈 기둥이 c
- 총 이동횟수 : 2ⁿ - 1
#include <stdio.h>
void htower(int n, int a, int b);
int count = 0;
void main()
{
int n;
count = 0;
printf("Enter disc number = ");
scanf("%d", &n);
htower(n, 1, 2);
printf("# move for %d discs : %d\n", n, count);
}
void htower (int n, int a, int b)
{
int c;
count ++;
if (n == 1)
printf("Disc %d, moved from Pole (%d) to (%d)\n", n, a, b);
else {
c = 6 - a - b;
htower(n-1, a, c);
printf("Disc %d, moved from Pole (%d) to (%d)\n", n, a, c);
htower(n-1, c, b);
}
}
// i : start index of range
// n : end index of range
void perm(char list[], itn i, int n)
{
int j;
if (i == n) // list print
{
for (j = 0; j <= n; j++)
printf("%c", list[j]);
printf(" ");
}
else {
for (j = i; j <= n; j++) {
Swap(list[i], list[j]); // 두 수 교환
perm(list, i + 1; n);
Swap(list[i], list[j]);
}
}
}
