알고리즘 정리 — SVM부터 XGBoost까지

연관 분석 (장바구니 분석)

변수 사이의 연관 규칙을 묶는다. 바탕은 조건부 확률이다.

단계	지표	하는 일
1	지지도	빈발 아이템 세트를 고른다 — Apriori 알고리즘. 많이 팔리는 것부터 추린다
2	신뢰도	최소 신뢰도 기준을 정해 조건을 준다
3	향상도	얼마나 연관되는지 본다. $\text{Lift} > 1$ 이면 양의 상관

Apriori 의 아이디어는 단순하다 — 빈발하지 않은 집합의 상위 집합은 절대 빈발할 수 없다. 그래서 아래에서부터 잘라 나가면 탐색 공간이 확 준다.


장점	결과를 이해하기 쉽고 실제 적용이 쉽다
단점	품목이 많을수록 규칙이 폭증하는데, 그 규칙이 의미 있는지는 사람이 판단해야 한다. 계산량도 크다

군집 분석

개체들 사이의 특징으로 무리를 나눈다. 무엇을 “가깝다”고 볼지가 전부다.

거리	성격
유클리드	L2 놈. 직선 거리
맨해튼	L1 놈. 축을 따라 간 거리
마할라노비스	변수 간 상관과 분산을 고려한 거리
상관 거리	값의 크기가 아니라 변동 패턴의 유사도

변수의 단위가 제각각이면 유클리드는 단위가 큰 변수에 끌려간다. 스케일링을 먼저 하거나 마할라노비스를 쓰는 이유가 그것이다.

KNN

가까운 $K$ 개를 보고 다수결(분류) 또는 평균(회귀)으로 정한다. 학습이 없다 — 예측할 때 전체 데이터를 뒤진다.

하이퍼파라미터	내용
$K$	인접 데이터의 개수 ( $1 \le K \le N$ ). 시행착오로 정한다
거리 척도	어떤 거리를 쓸 것인가

$K$ 가 작으면 노이즈에 흔들리고, 크면 경계가 뭉개진다.

당시 여백에 적어 둔 생각 — “인접한 $K$ 개의 평균과 중앙값을 기준으로 편차 범위를 잡아 중심점을 유추하고, 그것을 가중치로 삼아 분류하면 어떨까?” 지금 보면 이건 거리 가중 KNN(distance-weighted KNN)에 가깝다. 실제로 weights='distance' 옵션으로 존재한다.

의사결정나무

스무고개와 같다. 데이터가 균일해지도록 나눈다.

분류 — 비슷한 범주를 가진 관측치끼리 모은다
예측(회귀) — 비슷한 수치를 가진 관측치끼리 모은다

특성에 대한 질의로 계속 쪼개 나가는 형태다. 뿌리에서 뻗어 나가는, 거꾸로 선 나무다.

회귀 나무

끝노드 $R_m$ 마다 상수 $C_m$ 을 두는 함수다.

\hat{f}(x) = \sum_m C_m I\{(x_1, x_2) \in R_m\}

$I$ 는 지시함수(조건이 참이면 1, 아니면 0)다. 비용함수는 제곱오차이고,

\min \sum_i \left(y_i - \sum_m C_m I\{(x_1,x_2) \in R_m\}\right)^2

이것을 풀면 $\hat{C}_m$ 은 그 영역에 속한 $y_i$ 들의 평균으로 떨어진다.

\hat{C}_m = \mathrm{avg}(y_i \mid x_i \in R_m)

분할 변수 $j$ 와 분할점 $s$ 는 탐욕적(greedy) 으로 정한다 — 매 단계 그 순간 가장 좋은 분할을 고른다. 사실상 가능한 분할을 다 해 보는 것에 가깝다.

분류 나무

범주형 반응 변수가 $K$ 개 있을 때, 끝노드 $m$ 의 관측치 개수를 $N_m$ 이라 하면

\hat{P}_{mk} = \frac{1}{N_m}\sum_{x_i \in R_m} I(y_i = k) \qquad k(m) = \arg\max_k \hat{P}_{mk}

분할 변수와 분할점은 불순도 감소가 최대가 되도록 고른다.

불순도 척도	성격
오분류율	가장 단순하나 미분이 안 돼 최적화에 불리
지니 지수	실무 기본값
교차 엔트로피	정보이론 기반

남은 숙제

트렌드가 변하는 데이터는 시계열 가중치가 필요하다
특이점을 분류할 수 있는 분할점 정의가 필요하다

랜덤 포레스트

의사결정나무의 문제

계층 구조라 위쪽의 에러가 아래로 전파된다
작은 변동이나 노이즈에 크게 반응한다
노드를 더할수록 과적합이 생긴다

앙상블이 푸는 방식

여러 베이스 모델의 예측을 다수결 또는 평균으로 통합해 정확도를 올린다. 조건이 둘 있다 — 베이스 모델들은 서로 독립적이어야 하고, 무작위 추측(0.5)보다는 나아야 한다.

베이스로 의사결정나무를 쓰는 이유는 빨리 만들 수 있고 직관적이며, 데이터 분포에 대한 전제가 필요 없기 때문이다.

두 개의 무작위성

Bootstrap — 복원추출로 원래 데이터 크기만큼 뽑아 여러 학습 세트를 만든다. 각 모델이 서로 다른 데이터를 본다. (중심극한정리를 생각하면 복원 랜덤 샘플링된 세트들의 분포는 가우시안 상 큰 차이가 없다.) 이렇게 만든 개별 세트를 부트스트랩 세트라 부르고, 이 방식을 배깅(Bootstrap Aggregating)이라 한다.

Random subspace — 분할점을 고를 때 후보 변수를 무작위로 제한한다. 나무들이 비슷해지는 것을 막는다.

샘플링을 반복함으로써 계층 구조에서 오는 민감한 오차 반응을 통제하는 것이 요점이다.

Aggregating — 어떻게 합칠 것인가

방법	식
다수결	가장 많이 나온 예측
가중 평균	$\frac{\sum \text{TrainAcc} \cdot I(\hat{y})}{\sum \text{TrainAcc}}$ — 정확도로 가중
확률 평균	모델 전체 판정 확률의 평균 — 샘플보다 예측 모델에 무게를 둘 때

OOB 로 변수 중요도 재기

부트스트랩에서 뽑히지 않고 남은 데이터(Out of Bag)로 에러를 구한다. 그다음 특정 변수의 값만 임의로 뒤섞어 다시 OOB 에러를 구한다. 둘의 차이가 크면 그 변수가 중요한 변수다. 따로 검증 세트를 떼지 않아도 된다는 것이 이 방법의 이점이다.

하이퍼파라미터

	값
나무의 수	2,000개 이상
노드 분할 시 무작위 선택 변수 수	분류: $\sqrt{\text{변수 수}}$ / 회귀: $\frac{\text{변수 수}}{3}$

XGBoost

부스팅 계열. 아홉 가지가 얹혀 있다.

Gradient Boost, Regularization, A Unique Regression Tree, Approximate Greedy Algorithm, Weighted Quantile Sketch, Sparsity-Aware Split Finding, Parallel Learning, Cache-Aware Access, Blocks for Out-of-Core Computation.

앞의 셋은 알고리즘이고 뒤의 여섯은 속도와 규모를 위한 공학이다. XGBoost 가 널리 쓰인 이유는 사실 뒤쪽에 있다.

분할과 가지치기

노드의 분할점은 인접 데이터 사이의 평균으로 잡고 모든 조합을 검토한다. 나무 깊이는 기본 6 레벨로 제한한다.

파라미터	역할
$\lambda$ (정규화)	노드의 similarity 값을 줄인다. 예측 민감도를 낮춘다
$\gamma$ (가지치기 임계)	gain 이 $\gamma$ 보다 작은 분할점의 가지를 쳐 낸다. 클수록 많이 잘라 낸다

$\lambda$ 가 크면 gain 이 루트의 similarity 때문에 0 이하로 내려갈 수 있으므로, $\gamma$ 를 0 으로 두어도 가지치기가 일어난다. 이 둘로 과적합을 막는다.

학습률

첫 트리를 기본 예측값 0.5 에서 시작해 완성하고, 학습률 $\varepsilon$ (기본 0.3)로 조정하며 새 트리를 만든다.

\text{new predict} = 0.5 + \varepsilon \times (\text{각 노드의 output value})

반복할수록 잔차가 작아지는 트리가 쌓인다. 랜덤 포레스트가 독립된 나무들의 평균이라면, XGBoost 는 앞 나무가 남긴 잔차를 다음 나무가 이어받는다. 병렬이냐 순차냐의 차이다.

SVM

용어	뜻
Decision boundary	클래스를 잘 나누는 선
Hyperplane 초평면	마진을 가장 크게 하는 경계. 보통 $D-1$ 차원
Dimension	데이터의 특성(feature) 종류 수
Support vector	경계에 가장 가까이 있는 점들
Margin	서포트 벡터를 지나는 초평면 사이의 거리

마진은 최대화하고 오류는 최소화한다. 두 목표가 상충하므로 그 절충이 SVM 의 본체다.

커널은 원 데이터를 더 높은 차원으로 가공해, 저차원에서 나눌 수 없던 데이터를 나눌 수 있게 한다. 커널 트릭은 데이터를 실제로 옮기지 않고 계산상으로만 고차원으로 올리는 방법이다. 차원을 실제로 올리면 계산이 폭발하므로 이 트릭이 없으면 SVM 은 쓸 수 없다.


장점	분류·회귀·예측에 두루 쓴다. 신경망보다 적은 데이터로 학습된다. 과대·과소 적합이 적다
단점	기본적으로 이진 분류다(다중 분류는 클래스마다 SVM 이 필요). 데이터가 많으면 학습이 오래 걸린다

딥러닝

CNN

합성곱 계층과 풀링 계층으로 이루어진다.

요소	하는 일
필터(커널)	2차원 배열 형태지만 행렬곱과는 계산 방식이 다르다
패딩	테두리를 일괄로 채운다. 가장자리 정보 손실을 막는다
스트라이드	필터를 옮기는 간격. 차원 축소에 영향을 준다
풀링	지정 영역의 특징점을 뽑아 차원을 줄인다. 보통 Max pooling

RNN

중간층이 순환 구조를 이룬다. 가중치와 편향을 시점마다 공유하고, 확률적 경사 하강법으로 학습한다. 가중치 갱신에는 시간 방향으로 펼친 BPTT(Back Propagation Through Time)를 쓴다. 순차 데이터에 유리하다.

파생으로 LSTM 과 GRU 가 있다. 긴 시퀀스에서 기울기가 사라지는 문제를 게이트로 푼 것들이다.

오토인코더


인코더	입력을 저차원 표현으로 매핑하는 함수
디코더	그것을 다시 타깃 도메인으로 되돌리는 역함수

입력을 저차원으로 축약했다가 고차원으로 복원한다. 복원이 잘 된다는 것은 축약된 표현이 원본의 핵심을 담고 있다는 뜻이다. 차원 축소와 이상 탐지에 쓰는 이유가 그것이다.

여백에 적어 둔 CNN 개선 아이디어

당시 슬라이드에 이런 항목을 적어 두었다. 검증한 것은 아니고 생각만 해 둔 것이다.

커널 모양 — 사각형 말고 팔각형, 마름모를 검토
음영 처리 — 방향 가중치 또는 커널 모양 가중치
Delta pooling — max−min 으로 이미지 형성을 평가
특징점 사이 위치 비율 비교
무시(무의미한 영역)를 어떻게 처리할 것인가
함수 구성

지금 보면 1번과 2번은 이후에 실제로 연구된 방향과 닿아 있다 — Deformable Convolution (커널의 샘플링 위치를 학습으로 바꾼다)이 1번을, 어텐션 기반 가중치가 2번을 하고 있다. 4번의 “특징점 간 위치 비율”은 CNN 이 풀링으로 위치 정보를 버린다는 지적이고, Capsule Network 가 정확히 그 문제를 겨냥한 것이었다.