SVD-특이값 분해

선형변환 A에 의한 변환 결과가 자기 자신의 상수배가 되는 0이 아닌 벡터를 고유 벡터라고 하고 이 상수배를 고유값이라고 한다. 

고유값, 고유벡터는 정방행렬에 대해서만 정의된다.

여기서 v는 열벡터고, h는 상수이다. 

Av=hv라면, h는 행렬 A의 고유값, v는 행렬 A의 h에 대한 고유벡터.

즉, 고유값과 고유벡터는 행렬에 따라 정의되는 값으로서 어떤 행렬은 이러한 고유값-고유벡터가 아에 존재하지 않을수도 있고, 어떤 행렬은 하나만 존재하거나 또는 최대 n개까지 존재할 수 있다.

기하학적인 의미로 보면, A의 고유벡터는 방향은 보존되는 방향벡터, 그 고유값은 그 세기를 나타내는 상수값이다.

정사각행렬 A는 자기 자신의 고유벡터들을 열벡터로 하는 행렬과 고유값을 대각원소로 하는 행렬의 곱으로 대각화 분해가 가능하다. 이걸 Eigendecomposition

A=PVP-1 로 둘 수 있다는 것. V는 고유값을 대각원소로 하는 것. 

이런 고유값 분해(EVD)가 가능하려면, 정방행렬 A가 n개의 일차독립인 고유벡터를 가져야 한다.

특이값 분해.  

GAMBLE 알고리즘

Efficient Multiclass Boosting Classification with Active Learning
- Jian Huang, Seyda Ertekin, Yang Song, Hongyuan Zha, C.Lee Giles

GABMLE - Gentle Adaptive Multiclass Boosting Learning algorithm

Features
- K-class Classification 문제를 여러개의 binary class classification문제로 바꾸는 게 아니라 그대로 적용하여 다룬다.
- 각 iteration마다 오직 하나의 regression function이 fit 되는 것.
- 기본적으로 outlier에 덜 예민하고, unseen data에 강하다는 것.
- Active sample selection을 통해, 더 빠르고 효과적인 prediction이 가능하다.
- 알고리즘 구조가 간결하고 명확하며 쉽다.

기존연구
- 기존에 multiclass classification 을 위해 먼저 제안된 것은 AdaBoost.M1 algorithm.
이것은 기존 AdaBoost의 Indicator function에서의 hk를 바꾼것으로 기존것의 연장선상에 있다. 그리고 AdaBoost.Discrete에서 사용한 binary 용 loss function을 그대로 사용하였기 때문에 AdaBoost.M1은 샘플의 절반이상에서 Misclassification 된다는 단점이 발생하였다. error rate이 1/2보다 커지면 종료되므로 사용 불가. 부적합

- 그뒤에 나온 것이 AdaBoost.M2. Pairwise 전략을 사용해서 multiclass problem을 해결한다. 하지만 weak learner의 설계를 복잡하게 한다는 단점 존재.

- AdaBoost.MH는 M2 대체용으로 등장, 이건 one-against-all 방식으로 k class classification 문제를 k binary classification 문제로 변환하여 사용. Correcting output code를 사용하는 AdaBoost.MO도 존재.

- SAMME와 같은 AdaBoost에 multiclass exponential loss function을 적용한 파생 부스트 알고리즘이 존재하는데, 샘플에 outlier가 많다면, 그것들에 overemphasize하여 결국 inferior한 결과를 끌어내기도 한다는 단점 존재. 그것을 위해 Gentle AdaBoost와 같은 방법이 제안되었지만 이것은 여전히 one-against-all과 가은 전략을 사용한다는 게 단점으로 지적되고 있다.

-Active learning기법을 위해, Query By Committee, QBC가 active learning method로 잘 알려지고 사용되고 있다. 그리하여 QBC와 AdaBoost를 결합한 QBoost가 있는데 이 논문해서는 해당 기법에서의 active sample selection method를 그대로 이용하고, 이를 multiclass로 확장한다.

Boosting SVM

기존 SVM의 가장 큰 단점은 트레이닝시에 running time이 상당히 오래걸린다는 데 있다.

따라서 오직 몇개의 트레이닝 example만 실제 계산에 사용된다면 그 시간을 굉장히 줄일 수 있다. 이걸 Adaboost를 이용해서 해결할 수 있는데, 중요한 샘플데이터에만 더 큰 가중치를 주는 것이다. 이렇게 0<v<1인 vm개의 샘플을 이용하게 되면, 보다 빠른 계산이 가능하다.

두 번째로, learner의 입장에서보았을 때, SVM처럼 strong한 learner는 Adaboost에 적용하였을 때, 반대로 iteration이 점점 높아질수록 error rate가 향상되지 않고 오히려 나빠지는 경우가 많이 발생하였다.

이를 위해, weak learner version of SVM을 만들기 위해, SVM의 트레이닝 데이터중 low weight를 가진 데이터를 지운다. 그렇게 약화를 시킨다음에 Adaboost에 그냥 넣어돌린다.

다른점은 마지막 weak learner 결합시 hyperplane 형태로 나타난다는 점이다.

기본적인 ML 개념 - hypothesis

Classification rule은 hypothesis라고도 불리는데, 이것은 input space X를 class label인 Y에 사상시키는 함수를 말한다.
이것이 binary classification problem이라면, x->1 or -1로 사상된다.
기호꼴로 h(x)로 나타낸다.
그래서 h(x)의 부호가 x의 predicted label로 나타나고,
|h(x)| 크기는 그 prediction의 confidence를 나타낸다.

대문자 H는 hypothesis의 class를 말한다. H에 h1(x) 가 속하는 형태라는 것.

그래서 learning algorithm이라는 것은, labeled 된 example들 집합 S를 받아서 hypothesis h included in H 을 출력하는 알고리즘이다.

Combined classifier H(x)는 convex combination of several hypothesis 이다.

H(x) = summation i=1 to T ( ai * hi(x) )
ai가 0보다 크고, ai가 1에서 T까지의 합이 1이라면 각각 hypothesis hi는 base classifier이다.

Boosting 알고리즘

Boosting 알고리즘 이라는 것은 약한 learner들을 합쳐서 강한 learner로 만들어주는 알고리즘을 말한다.

그중에서 AdaBoost는 Adaptive boosting algorithm의줄임말로써,
misclassified 된 데이터에 더 높은 가중치를 주어 다음번 학습때 더 좋은 결과를 내도록 하는 것이다.

기본적인 알고리즘은 다음과 같다.


우선 데이터 x와 그것의 클래스 1 또는 -1값이있고. 초기의 가중치는 1/m으로 동일하다.

그때 1~T까지 루프를 돌면서 아래의 것을 반복한다.

어떤 classfied 되는 rule (직선?) 과 같은걸 찾는데 error값이 가장 작은걸로 잡는다.
그 error값은 만약 prediction이 틀렸을 때, 그것과 가중치를 곱한 값이고, 그것을 에러값이라고 한다.

에러값이 1/2보다 크면 랜덤보다 못하므로 그만두고, 그거보다 작다면 알파값을 계산한다.

이 알파값은 에러값이 작으면 커지는 현상으로

iteration이 증가할 수록 에러 줄어들기 때문에 알파값은 커지고, 그것에 곱해지는 가중치 D의 잘못된 prediction 결과 i는 더 높은 값을 띄게된다.

그래서 이게 T가 되거나 또는 에러가 1/2보다 커지면 종료되고,
이때 결과는 그것들의 합으로 나타나진다.

 일단은 이것이 binary classification 대상이기 때문에, multiple classification의 경우에는
AdaBoost.MH나 AdaBoost.MI와 같은것을 사용해야한다.

일단 부스팅의 개념은 이와같고, 다음은 Boosting SVM을 봐야지

m-cross validation

m-cross validation: 

m개의 subset으로 나누고, m-1개를 가지고 training, 나머지 1개로 validation

이것을 한번씩 번갈아 가며 수행하고, m번으로 평균을 계산한다.

이것을 하는 목적은, 해당 만들어낸 모델이 얼마나 데이터 셋과 무관하게 얼마나 잘 예측을 할 것인지 평가하기 위한 것이다. Predictive model이 실제 환경에서 얼마나 성능이 좋은지 보고자 하는 것. 

Overfitting

Overfitting문제: 

Supervised learning을 통해 만들어진 시스템이 학습 데이터 내에서는 데이터 분류를 매우 잘 하지만, 새로운 데이터에서는 그 분류 성능이 많이 떨어지는 상황을 말한다.

보통 그 이유는 학습을 너무 많이 했거나, 지나친 튜닝을 했거나, 데이터 셋이 편향되어 있거나 등이 있다. 데이터를 가지고 만든 모델과 시스템에서의 오버피팅은 어쩔 수 없는 문제.

따라서 가능한 많은 데이터를 가지고 학습을 하여 unseen data의 범위를 좁히거나, cross validation을 많이 하여 보다 general model을 도출하거나, 여러 개의 model을 가지고 비교하거나 하면된다.