t-SNE 의 개념 및 알고리즘 설명

/* DeepPlay 2022-09-11 */

t-SNE (t-distributed Stochastic Neighbor Embedding) 는 고차원 데이터를 저차원 데이터로 변환하는 차원 축소 (dimensionality reduction) 기법이며, 대표적이며, 좋은 성능을 보이는 기법이다. 

차원 축소을 하는 목적은 시각화, 클러스터링, 예측 모델의 일반화 성능 향상 등의 목적을 들 수 있다. t-SNE 의 경우, 고차원 공간상의 데이터 포인트들의 위치를 저차원 공간상에서의 극적으로 표현을 해주기 때문에 데이터에 존재할 수 있는 군집들을 시각화해서 표현해주는데 강점을 갖고, 시각화에 주로 사용된다. t-SNE 는 직접적으로 클러스터를 만들어서 레이블링까지 해주는 클러스터링 알고리즘은 아니다. 따라서 클러스터링에 직접적으로 활용되기 보다는 t-SNE 의 결과에 다시 k-means 와 같은 알고리즘을 적용하는 방식으로 클러스터링을 수행하기도 한다 (참고: https://www.quora.com/Can-TSNE-be-used-for-clustering). t-SNE 는 PCA 와 같이 저차원에서 요약된 변수에 의미가 있는 것은 아니다. (PCA 의 경우, 저차원 공간의 변수가 고차원 공간상의 변수들의 선형 결합이라는 의미가 있다.)

차원 축소의 3가지 카테고리

1) feature selection: univariate association test, ensemble feature selection, step-wise regression 등

2) matrix factorization: SVD (singluar vector decomposition)

3) neighbor graphs: t-sne, UMAP (Uniform Manifold Approximation and Projection) 등

우선, t-sne 는 비선형 차원 축소 (nonlinear dimensionality reduction) 기법이다. 따라서 아래와 같은 데이터에 대해서도 적용할 수 있다. 반면 PCA (principle component analysis) 와 같은 선형 차원 축소 방법의 경우 아래 데이터에 적용하여 유의미한 결과를 내기는 어렵다.

t-SNE 알고리즘

sne, t-sne, UMAP 과 같은 차원 축소 방법은 아래의 공통된 절차를 수행한다.

원래 데이터가 있는 공간을 high dimension, 축소된 공간을 low dimension 이라고 하자. 

------------------------------------------------------------------------------------------------

1) high dimensional probabilities p 를 계산한다.
2) low dimensional probabilities q 를 계산한다.
3) 두 분포의 차이를 반영하는 cos function C(p,q) 를 정의한다. 
4) Cost function 이 최소화 되도록 저차원 공간상의 데이터를 변환한다. 

------------------------------------------------------------------------------------------------

대략적인 절차는 매우 심플하다. t-sne 에서는 각 절차를 실제로 어떻게 수행하는지 알아보자. 

1) high dimensional probabilities p 를 계산한다.

p_(i,j) 를 어떤 데이터 포인트 i,j의 similarity 를 반영하는 스코어라고 하자. 두 포인트가 가까이 위치할 수록 p_(i,j) 의 값은 커지게 된다. 그리고 i,j 의 euclidean distance 를 e_(i,j) 라고 하자. 다른 데이터들에 대해서도 서로의 eucliean distance 를 계산할 수가 있고, 그 값들이 어떤 분포 g 를 따른다고 가정하자. p_(i,j) 는 그 분포상에서의 likelihood 라고 할 수 있는, g(e(i,j)) 로 정의해보자. 

예를 들어 설명하면, 위 두 데이터 포인트를 각각 (2,9) 와 (3,10) 이라고 하자. e= sqrt((3-2)^2 + (10-9)^2)=sqrt(2) = 1.41 이다. 

t-sne 에서 사용하는 g 확률 분포는 아래와 같다.

$$ g(x) = exp(-x^2 / 2\sigma_i^2) $$ 

$$ g(e(i,j)) = exp(-||x_i-x_j||^2 / 2\sigma_i^2) $$ 

모든 g 값의 합이 1이 되도록 아래 식으로 변환한다. 

$$ p_{j|i} = \frac{exp(-||x_i-x_j||^2 / 2\sigma_i^2)}{\sum_{k \neq l} exp(-||x_k-x_l||^2 / 2\sigma_i^2)} $$

그러면, p(j|i) 의 값이 p(i|j) 의 값은 다른데, 최종적으로 두 값의 평균을 취하고, 마찬가지로 모든 값의 합이 1이 되도록 하기 위하여 최종적인 i,j 의 similarity score p(i,j) 를 아래와 같이 계산한다 (N은 계산 가능한 쌍의 수). 이러면, p 를 이산확률분포처럼 다룰 수 있게 된다. 

$$ p_{i,j} = \frac{p(j|i) + p(i|j)}{2N} $$

2) low dimensional probabilities q 를 계산한다.

마찬가지의 방법으로 q(i,j) 를 다음과 같이 구한다. 

$$ q_{j|i} = \frac{(1+||y_i - y_j||^2)^{-1})}{\sum_{k \neq l} (1+||y_k - y_l||^2)^{-1})  } $$ 

$$ q_{i,j} = \frac{q(j|i) + q(i|j)}{2N} $$ 

σ 는 어떻게 정해지는가?

이를 위해하기 위해 우선, entropy 와 perplexity 라는 개념에 대한 설명이 필요하다. perplexity = 2^entropy 로 정의되며, entropy 는 '어떠한 확률 분포에 대하여, 관측값을 예측하기 어려운 정도' 를 의미하는 수치이다. 어떤 분포 q 에대한 entropy 는 아래와 같다. 

$$ H(q) = -\sum_{c=1}^{C} q(y_c)log(q(y_c)) $$ 

entropy 를 설명하기 위해, 빨간공과 녹색공이 20:80 으로 들어 있는 가방에서 1개의 공을 꺼내서 관찰 값을 확인하는 이산 확률 분포를 예로 들어보자. 그 확률 분포 q의 entropy 는 H(q)=-(0.2log(0.2)+0.8log(0.8))=0.5 이다. 그리고, perplexity = 2^0.5 = 1.41 이다. 

perplexity 값에 따라 t-SNE 의 결과가 민감하게 반응하기 때문에 perplexity 는 중요한 파라미터이다. 보통 t-SNE 는 입력받은 perplexity 를 맞추는 σ 를 찾기 위하여 binary search 를 수행한다. 일반적으로 perplexity 를 조정하면서 시각화를 해보고, 가장 군집을 잘 보여주는 값을 최종적으로 선정하는 방법을 택한다. 

왜 p, q 분포는 위와 같이 정해지는가?

p분포는 정규 분포와 유사하며, q분포는 t분포와 유사한 형태를 띈다. q 분포의 경우, p 분포 대비 빠르게 하락하고, 꼬리가 두터운 형태의 분포를 갖는다.  q분포를 썼을 때의 효과는 한 점에 데이터가 뭉치는 crowding problem 을 완화시킨다는데 있다. 따라서, 시각화시 저차원 공간상에서 너무 한 점에 뭉치지 않도록 하는 효과가 있기 때문에 p 분포를 썼을 때보다 이점이 있다. (이는 개인적인 이해를 위한 해석이며, 이와 관련한 좀 더 디테일한 설명은 original paper 를 참고) 

구현 레벨에서의 최적화

t-SNE 는 데이터가 커질수록 연산량이 기하급수적으로 늘어나는 O(n^2) 의 시간 복잡도를 갖는다. 실제 구현 레벨에서는 Barnes hut t-SNE 라는 방법을 통해 더 계산 효율적인 구현 방식을 택한다. scikit-learn 의 t-sne 구현체는 이 방식을 활용한다.

t-SNE 의 optimization

t-SNE 에서의 optimization 이란 고차원 공간상에서의 p분포 (high dimensional probabilities p) 와 저차원 공간상의 q분포 (low dimensional probabilities q ) 의 차이를 줄이는 것이다. 이 때, cost function 을 정의하고, 이를 최소화하는 방식으로 optimization 이 수행된다. 

3) 두 분포의 차이를 반영하는 cos function C(p,q) 를 정의한다. 

cost function C(p,q) 로는 Kullback-Leibler divergence 를 사용한다. p,q는 이산확률분포이고, KL divergence의 식에 적용하면 cost 를 실제로 구해볼 수도 있다. 

4) Cost function 이 최소화 되도록 저차원 공간상의 데이터를 변환한다. 

KL divergence 을 최소화 시키는 저차원 공간상의 데이터의 위치를 gradient optimization 방식을 통해 구할 수 있다. 설명하자면, 결국 저차원 공간상에 랜덤하게 뿌려진 데이터 포인트들이 각각 어떤 방향으로 가야지 cost function 을 줄일 수 있을지 알아야 하는 것인데, 이는 cost function 을 미분한 뒤에 각 데이터 포인트 별로 gradient 를 구함으로써 알 수 있다. 

참고자료

• https://arize.com/blog/t-sne-vs-umap/
• https://towardsdatascience.com/t-sne-clearly-explained-d84c537f53a
• https://distill.pub/2016/misread-tsne/
• https://towardsdatascience.com/t-sne-machine-learning-algorithm-a-great-tool-for-dimensionality-reduction-in-python-ec01552f1a1e
• https://lovit.github.io/nlp/representation/2018/09/28/tsne/
• https://towardsdatascience.com/t-sne-python-example-1ded9953f26

Semi-supervised learning 이란? 

예를 들어, 우리의 친구 Justine 이 좋아할만한 소설을 예측하고 싶다고 가정하자. 현재 가지고 있는 정보는 "그녀가 최근 읽은 몇 가지 소설" 및 "그 소설들에 대해 그녀가 좋아했는지 안 좋아했는지 여부" 를 알고 있다. 

표준적인 supervised machine learning 패러다임에서는 positive example 과 negative example 들의 feature들을 비교하여, 새로운 소설 (unseen) 에 대해 그녀가 좋아할지 안좋아할지를 예측하는 모델을 만든다. 

반면, semi-supervied paradigm 은 Justine 이 읽은 소설만 활용하는 것이 아니라 그녀가 읽지 않은 소설 (unlabeled) 까지 활용하여 그녀가 선호할만한 소설을 예측하는 시스템을 만든다. 당연히 전체 소설중, 그녀가 읽지 않은 소설이 훨씬 많을 것이며, 놀랍게도, 이를 활용하면 (unlabeled 데이터를 활용하면) 더욱 효율적인 시스템을 만들 수 있다는 것이다.

Why semi-supervised learning works?

왜 unlabeld 데이터가 예측에 도움이 될 수 있는지를 이해하기 위해 위 그림을 보자. 

초록색: positive cases

빨간색: negative cases

선: decision line

unlabeled 데이터를 활용하면 오른쪽 그림처럼 더욱 정교한 decision line 을 그릴 수 있다. 이를 통해 모델의 성능 및 일반화에 도움을 줄 수 있다. 

PU learning 의 직관적 이해 

Positive-unlabeled learning 은 semi-supervised learning 은 한 가지 패러다임으로, positive case 와 unlabeld case 만 존재하는 문제에서, 사용할 수 있는 방법이다. 위 예시에서 Justine 이 좋아하는 소설에 대한 데이터만 갖고 있는 것이다. real-world 에서 이러한 상황은 생각보다 자주 존재한다. (항상 toy 문제처럼 positive case 와 negative case 가 잘 들어가 있지는 않다.)

초록색: positive cases

선: decision line

PU learning 이 왜 워킹 하는지에 대해 직관적으로 이해해보자. 

1) 왼쪽 그림만을 보고, positive와 negative 를 구분하는 선을 만들라고 하면 어떻게 할 것인가? (머신러닝 모델이 아닌 사람의 직감으로) 다른 데이터들이 어떻게 놓여있는지를 알 수 없기 때문에, 타원 모양의 decision boundary 를 그리는 것이 한 가지 방법이 될 것이다. 

2) 오른쪽 그림을 보고, 다시 positive 와 negative 를 구분하는 선을 만들라고 하면 어떻게 할 것인가? 왼쪽 그림과 비교하여 추가적인 정보 (unlabeled 데이터가 어디에 놓여있는지) 를 알고 있다. 그렇기 때문에 그림처럼 다른 decision boundary 를 그릴 수 있게 된다. 

PU learning 의 몇 가지 테크닉들

1) Direct application of a standard classifier

가장 기본적인 접근 방법은 unlabeled case 를 negative 로 취급하고 분류 모델을 학습하는 것이다. 이 모델은 각 데이터 포인트에 점수를 주는데, positive case 에 대해서 평균적으로 더 높은 점수를 준다. 만약 unlabeled 데이터 중에 높은 점수를 받은 데이터 포인트가 있다면, positive case 일 확률이 높을 것이다.

이러한 '가장 나이브한 방식' 의 정당성은 이 논문에서 확인되었다 (2008년도). 이 논문의 주요 결과는, 몇 가지 특정한 가정하에, positive+unlabeled 데이터로 학습한 모델의 성능은 positive+negative 데이터로 학습한 결과와 비례한다는것이다.  

저자의 코멘트에 따르면, 이 의미는 다음과 같다: "모델이 잘 학습되었다고 가정하면, PU 모델은 어떤 데이터 포인트가 positive 에 속할 가능성에 대한 순위를 매기는데 활용할 수 있다." 

2) PU bagging

더욱 정교한 접근 방법은 bagging 의 변형을 활용하는 것이다. 

- positive data 와 함께 "unlabeled data 로 부터 random sampling 한 데이터(with replacement)" 를 같이 활용한다. 

- 위 boostrap sample 을 negative 로 하여 모델을 학습한다. 

- out of bag 샘플 (boostrap sample 에 포함되지 않은 unlabled data) 에 대해 스코어를 매기고, 저장한다.

- 이러한 방법을 반복적으로 적용하고, unlabeled 데이터들에 대해 나온 스코어들을 평균낸다. 

이러한 접근 방법이 소개된 논문 (2013년) 에서 저자들은 특히, 갖고 있는 positive sample 숫자가 적고, unlabeled 데이터 중, negative 의 비율이 적은 PU learning 상황에서 state-of-the-art 성능을 달성했다고 주장했다 (2013년도 기준). 또한 unlabeled 데이터의 규모가 큰 경우, 이러한 bagging 방식은 더 빠르게 모델을 학습할 수 있다. 

3) Two-step approaches

많은 PU learning 전략은 two-step 접근 방법 카테고리에 속한다. (이 방법이 소개된 논문 (2014년))

Step1 - unlabeled 중에 negative 인 것이 가장 확실한 포인트들을 찾는다. (이를 reliable negative 라고 한다.)

Step2 - positive 와 reliable negative 로 모델을 학습하고, 나머지 unlabeled 데이터에 적용한다. 

일반적으로 Step2 의 결과를 통해 Step1 으로 되돌아가서, reliable negative 를 찾고 이를 반복하게 된다. 당연히 reliable negative 의 규모가 충분히 크고, 실제 negative 를 많이 포함하고 있을 수록 더 좋은 모델을 구축할 수 있다. 얼마나 반복해서 적절한 수의 reliable negative 를 찾을 수 있을지가 핵심적인 부분이라고 할 수 있다. 

https://roywrightme.wordpress.com/2017/11/16/positive-unlabeled-learning/

https://github.com/AaronWard/PU-learning-example

언제할까?

최근 다양한 도메인에서 머신러닝이 활용되고 있다. 머신러닝의 문제점은 training data 가 필요하다는 것이다. 

현실에서는 label 이 있는 데이터를 수집하기 어렵거나 높은 비용이 요구되는 상황이 많다.

semi-supervised learning 이러한 상황에서 전체 데이터의 일부에만 label 이 있을 때 사용한다.

왜할까?

semi-supervised learning 의 핵심 과정 중 하나는 unlabled data 를 labled data 로 변환하는 것이다. (이를 pseudo-labeling 이라고 한다.) 그런데, 전체 데이터의 일부에 lable 이 있다고 하면, 그 데이터를 training 데이터로 모델을 만들면 안 되는가?

위 그림을 보면, 소수의 labeled data 로 만든 decision boundary 보다 unlabled data 를 사용한 것이 더 세밀하다는 것을 직관적으로 알 수 있다. 즉, 더 많은 데이터들에 대한 generalization 이 잘 된다는 것이다. 

semi-supervised learning 의 이점

• labled data 와 unlabled data 를 combine 하는 것은 accuracy 를 상승시킨다. (may be due to generalization)
• unlabled data 를 획득하는 것은 상대적으로 cheap 하다. -> 잘만 되면 더 비용효율적이다. 

semi-supervised learning 의 가정

1) Continuity / smoothness assumption

"다차원 공간 상에서 가까운 거리에 있는 샘플들은 labeld 이 아마 같을 것이다." 라는 가정이다. 이는 지도학습에서도 마찬가지로 있는 가정이다. 다만 semi-supervised learning 에서는 가까운 거리에 있는 샘플들은 예외 없이 같은 label 이 된다. 라는 점이 다르다. 

2) Cluster assumption

"데이터는 클러스터를 형성할 것이며, 같은 클러스터에 속한 샘플은 같은 label 을 공유할 가능성이 높다"라는 가정이다. (같은 label 을 가진 샘플들이 다양한 클러스터에 존재할 수는 있다.) 이는 clustering 알고리즘에서의 smoothness assumption 으로 볼 수 있다. 

3) Manifold assumption

"고차원 공간의 데이터를 저차원 공간에 표현할 수 있다." 라는 가정이다. 이는 모델링에서는 당연한 가정이라고 볼 수 있다. 예를 들어, 수많은 피쳐 x 를 통해 하나의 y를 예측하는 과정이니 말이다. manifold assumption 성립하지 않으면 예측이 불가능하다고 볼 수 있다. 

pseudo-labeling

labeled data 를 통해 unlabled data 를 labled data 로 변환하는 것을 말한다. 

Active Learning

labeled data 를 주어진대로만 사용하지 않고, 재구성하는 전략을 말한다. 

가장 성능을 높이는데 효과적인 샘플 (labeled or unlabeld) 에 대해 labeling 을 수행하는 전략이다.  

• supervised learning 에서 학습이 잘되는 일부 labeling data 만 사용할 수 있다.
• semi-supervised learning 에서 pseudo-labeling 하는 것도 active learning 의 일종이다. 

Margin sampling

margin sampling 은 active learning 의 예시로 decision boundary 를 효율적으로 찾는 방법중 하나로 가장 애매한 (uncertain) 샘플을 labeled data 로 변환해 나가면서 decision boundary 를 업데이트 해나가는 방법이다. 아래와 같이 random 하게 업데이트 하는 것보다 빠르게 클래스를 잘 분류할 수 있는 boundary 를 찾을 수 있다. 

Weak supervision

ground truth label 이 없을 때, subject matter expert (SME) 가 휴리스틱한 방법으로 labeling 하는 것을 말한다.

만약 이 방법으로 어떤 샘플이 A 레이블에 할당되었다고 하더라도, 실제로는 A 레이블이 아닐 가능성을 갖고 있다. 

이를 noisy label 이라고 한다. 

Snorkel 

스탠포드에서 2016년에 개발되었다. manual labeling 을 줄이는 방법으로 training data 를 구축하기위한 라이브러리이다. snokel 은 weak supervision 상황을 해결하는 것을 돕는다. 

semi-supervised learning 의 분야

semi-supervised learning 의 핵심과정인 pseudo-labeling 을 어떻게 수행할 것인가? 

단순히 model prediction 을 통해  pseudo-labeling 을 하는 것보다 성능이 좋은 다양한 방법론들이 존재한다. 

위 분류에서는 semi-supervised learning 을 크게 transductive 와 inductive로 나눈다. [1]

ㄴ transductive 와 inductive 의 차이를 데이터 과점에서 본 포스팅 (link)

참고자료 [2] 에서는 1) graph-based 방법과 2) consistency-based 방법으로 나누기도했다. Graph-based method은 대표적으로 Label propagation 방법이 있다. consitency-based method 는 최근 각광받고 있는 방법으로 Mixmatch 를 예로 들 수 있다. 

참고자료

[1] Van Engelen, Jesper E., and Holger H. Hoos. "A survey on semi-supervised learning." Machine Learning 109.2 (2020): 373-440

[2] https://www.youtube.com/watch?v=coezwQw6my0 

Scikit-learn Gradient Boosting 모델 예측값이 매번 달라지는 문제와 해결

아래 코드는 k-fold cross-validation 을 통해 best parameter 를 찾은 후, test set 에 대해 예측하는 코드이다. 이 코드에서 random_state=2020 을 지정하지 않으면, GridSearchCV 를 통해 구한 best parameters set이 매번 달라졌다. 즉 이말은 Gradient Boosting Tree 가 fitting 할 때마다 달라진다는 뜻이다. 

def cv_and_prediction(x_vars, name, model=False):

    train_x = metadata_valid[x_vars]

    train_y = metadata_valid["case"]

    test_x = metadata_test[x_vars]

    test_y = metadata_test["case"]



    model = GradientBoostingClassifier(random_state=2020)

    param_test = {

        "n_estimators": range(50, 100, 25),

        "max_depth": [1, 2, 4],

        "learning_rate": [0.0001, 0.001, 0.01, 0.1],

        "subsample": [0.7, 0.9],

        "max_features": list(range(1, len(x_vars), 2)),

    }



    gsearch = GridSearchCV(

        estimator=model,

        param_grid=param_test,

        scoring="roc_auc",

        n_jobs=4,

        iid=False,

        cv=5,

    )



    gsearch.fit(train_x, train_y)



    print(name)

    print("Best CV Score", gsearch.best_score_)

    print("Best Params", gsearch.best_params_)



    model = GradientBoostingClassifier(**gsearch.best_params_)

    model.fit(train_x, train_y)

    metadata_test[name] = model.predict_proba(test_x)[:, 1]

        

    return model

왜 이런문제가 발생하는가 ?

구글링을 통해 문제가 발생할 수 있을만한 원인을 찾았다. 

1. 우선 Decision tree 를 적합하는 방법은 heuristic algorithm (greedy algorithm) 이다. 왜냐하면 optimal 한 decision tree 를 찾는 것은 np-complete 문제이기 때문이다. 하지만 직접적인 문제는 아닌듯하다. greedy 한 방법으로 tree 를 만들더라도 매번 같은 greedy 한 방법을 이용하면 같은 tree 가 생성되기 때문이다.

2. Gradient Boosting 과 같은 ensemble 방법에서는 매 iteration 마다 subsample 을 만들어서 negative gradient 를 예측하는 모델을 만들어서 합치게 되는데 이 때, subsample 이 random 하게 설정되기 때문에 매 번 모형이 달라지고 이로 인해 예측 값이 조금씩 달라지게 된다.  

정확한 원인이 무엇이든 Gradient boosting tree 를 만드는 것에는 randomness가 있으며 reproducible 한 코드를 작성하고 싶으면 GradientBoostingClassifier(random_state=2020) 와 같이 random_state 를 지정해야한다. 

참고

https://scikit-learn.org/stable/modules/tree.html#tree

구글 번역기는 하나의 긴 문장을 두 개의 문장으로 쪼개주기도 한다.

임상 정보 기반 위험도 평가부는 임상 정보와 유전체 정보에 따른 위험도를 산출하는 모듈로, 유전체/가족력 정보를 통해 대상자를 몇 가지 표현형 (phenotype) 으로 나눈 후, 각 표현형의 나이에 따른 유방암 발생 확률에 임상 정보를 통해 추정한 상대 위험도 (relative risk)를 곱하는 방법을 통해 위험도를 산출한다. 

The clinical information-based risk assessment unit is a module that calculates the risk according to clinical information and genomic information. After dividing the subject into several phenotypes through genome / family history information, the risk of breast cancer according to the age of each phenotype and clinical It is calculated by the squared relative risk estimated from the information.

빠르게 영문 번역해야할 일이 있어 번역기의 도움을 받았는데 정말 좋은 것 같다. RNN seq to seq 의 개념에서 마침표를 하나의 단어로 인식한다면 기술적으로 불가능한것은 아니겠지만 어떻게 트레이닝을 했을지 정말 놀랍다. 

One shot learning, Siamese Network 이해

Problem Definition 

이미지 인식 분야에서 각 label 의 이미지 수가 적을 때 이를 인식하고 분류하는 것은 challenging 합니다. 예를 들어 얼굴 인식 분야에서는 단 몇 장의 이미지만을 통해 동일인인지 여부를 구분해야하는 문제가 있습니다. 물론 augmentation 과 같은 방법으로 샘플 수를 늘려서 CNN 으로 multi-class classification 문제를 풀도록 학습시키는 방법이 가능합니다. 하지만 이 경우, 새로운 사람이 데이터 베이스에 추가되었을 때, 모델을 새로 학습해야한다는 문제가 생깁니다. 즉, 실시간 시스템에 적합하지 않은 방법입니다. 

이러한 문제를 해결하는 한 가지 방법은 "Distance function" 을 이용하는 것입니다. 

D(x_1, x_2) = degree of difference between images 

Distance function 을 이용해, 예를 들어, D(Image1, Image2) <= k 인 경우 같은 사람이라고 예측하고, > k 인 경우 다른 사람이라고 예측할 수 있습니다. 또는 DB 에 있는 모든 Image 에 대해사 distance 를 계산한 후에 가장 distance 가 작은 사람으로 분류할 수 있습니다. 이러한 아이디어의 의미는 face recognition 에서는 누구인지 구분하는 것보다 "동일인지 여부" 가 중요하다는 것입니다. 또한 이를 이용해 multiclass classification 을 할 수도 있습니다. 이는 아이디어 측면에서 머신러닝의 고전적인 방법인 nearest neighbor 방법과 비슷합니다. 본 포스팅은 Distance function 의 인풋으로 넣기 위한 representation 을 만드는 함수 f 를 딥러닝으로 학습하는 방법에 관한 것입니다. 이미지의 distance 를 계산하기 위한 representation learning 개념입니다. 

Siamese Network + Triple loss

Our approach is to build a trainable system that nonlinearly maps the raw images of faces to points in a low dimensional space so that the distance between these points is small if the images belong to the same person and large otherwise. Learning the similarity metric is realized by training a network that consists of two identical convolutional networks that share the same set of weights - a Siamese Architecture (Sumit Chopra, 2005, CVPR)

함수 f 를 딥러닝 방법을 통해 학습할 수 있는 한 가지 방법은 Siamese network 을 이용하는 것입니다. Siamese network 는 2005년에 CVPR 에 발표된 방법으로, weights 를 공유하는 두 개의 CNN 입니다. 이 CNN은 Image1과 Image2를 f(Image1) 과 f(Image2) 라는 vector representation 으로 변환시킵니다. 그리고 f 를 학습시키기 위해 loss function 을 정의하고, distance 를 나타낼 수 있는 representation 을 만드는 방향으로 weights가 학습됩니다. 이미지1과 이미지2의 distance 를 f(Image1)과 f(Image2)의 l2 norm 으로 정의해봅시다. 

$$ D(x_1, x_2) = ||f(x_1) - f(x_2) || ^2 $$

loss function 으로 사용할 수 있는 한 가지는 Triplet loss 입니다. Triplet loss 는 3개의 이미지로부터 loss function 을 만드는 방법이며, 아이디어는 같은 사람의 이미지의 distance 가 다른 사람의 이미지의 distance 보다 작아지도록 하자는 것입니다. 이는 기술적으로  D(Anchor, Positive) 가 D(Anchor, Negative) 보다 작아지도록 잡자는 것입니다. 이 때, Anchor 와 Positive 는 같은 사람의 다른 이미지이고, Negative 는 Anchor, Positive 와 다른 사람입니다. 이 때, alpha 라는 margin 을 주어 충분한 차이가 벌어지도록 합니다. 

이러한 아이디어를 이용해 실제로 정의되는 triplet loss 는 아래와 같습니다.

$$ L(A, P, N) = max(||f(A) - f(P)||^2 - || f(A)-f(N) || ^2 + \alpha, 0) $$

실제 배치 트레이닝시 loss 는 아래와 같이 계산될 것입니다. m 은 배치 샘플 수입니다. 

$$ J = \sum^{m}_{i=1} L(A^i, P^i, N^i) $$

Triplet loss 의 문제는, A, P, N 을 random 하게 골랐을 때, loss 가 0이 되는 것이 너무 쉽게 만족한다는 것입니다. 그래서 실제 트레이닝시 중요한 것은 구분하기 어려운 샘플을 고르는 것입니다. 즉, A-P 와 A-N의 distance 의 차이가 크지 않은 두 이미지를 우선적으로 사용하는 것이 좋습니다. 이 방법은 Triplet loss 를 제시한 논문에 설명되어 있습니다.  

https://omoindrot.github.io/triplet-loss

트레이닝 데이터에서 Triple loss 로 하나의 CNN 을 구현한 후 학습한 후, 테스트 데이터에서는 예를 들어, 이미지의 representation 을 얻은 후, DB 에 있는 representation 과의 distance가 k 미만일 때, 같은 사람이라고 verification 할 수 있습니다.

Siamese Network + Binary loss

아래와 같이 문제를 Binary classification 으로 formulation 해서 face recognition 을 구현할 수도 있습니다. 실제로 많이 사용하며, 성능도 괜찮은 방법입니다. 

https://medium.com/predict/face-recognition-from-scratch-using-siamese-networks-and-tensorflow-df03e32f8cd0

이 방법에서 Siamese Network 는 두 이미지를 input 으로 하고, 같은 사람을 1, 다른 사람을 0 로 encoding 된 label 을 통해 training 됩니다. triplet loss 를 사용한 방법에서는 max(l2 distance 의 차이+alpha, 0) 을 줄이는 방향으로 training 이 되었지만, binary classification 을 활용한 방법의 경우 구조가 약간다릅니다. 

Siamese network와 binary classification 을 결합한 방법에서 CNN 이후 아키텍쳐는 다음과 같습니다.  

참고 

• https://www.youtube.com/watch?v=96b_weTZb2w&t=29s
• https://towardsdatascience.com/one-shot-learning-with-siamese-networks-using-keras-17f34e75bb3d
• https://arxiv.org/pdf/1503.03832.pdf
• http://yann.lecun.com/exdb/publis/pdf/chopra-05.pdf
• https://www.cs.toronto.edu/~ranzato/publications/taigman_cvpr14.pdf
• https://medium.com/predict/face-recognition-from-scratch-using-siamese-networks-and-tensorflow-df03e32f8cd0

잘 정리된 사이트가 있어 공유합니다. H-index 기준 1위 CVPR, 2위 NIPS, 3위 EECV, 4위 ICML, 5위는 얼마전 서울에서 열렸던 ICCV 네요. 

무엇을 기준으로 한지는 잘 모르겠으나, 아래와 같이 Conference 와 Journal 의 Rank 를 분류한 자료도 있습니다. SIGIR, WWW, ACL, KDD, AAAI, IJCAI, ICML, NIPS, ICLR가 아래 기준 Rank 1 에 속한 conference 들입니다. 

참고

https://sites.google.com/site/lyangwww/resources?tmpl=%2Fsystem%2Fapp%2Ftemplates%2Fprint%2F&showPrintDialog=1

http://www.guide2research.com/topconf/machine-learning

https://jackietseng.github.io/conference_call_for_paper/conferences.html

딥러닝 분야별 State-of-the-art (SOTA) 브라우저

딥러닝 분야 (Image Classification, Semantic Segmentation, Object Detection, Medical 등) 별 SOTA 알고리즘을 확인할 수 있는 사이트를 찾게 되어 공유합니다. Data set 별로 가장 성능이 좋은 방법들을 나열해놓고 있습니다. 최신 기술의 업데이트를 한 곳에서 확인할 수 있어 매우 유용한 사이트인것 같습니다. Semantic Segmentation 분야의 경우, DeepLab 이 최신 기술이라고 알고 있었는데 이외에도 들어보지 못한 ACNet, HRNet 등의 방법들도 좋은 성능을 내고 있네요.

https://paperswithcode.com/sota?fbclid=IwAR16wLSr-BAcl-eZAwMVIHdsmpgBF6dN4ETR5kRGg02f_5xBBOlN6uMapo4

일반 Softmax 함수 

import tensorflow as tf
import numpy as np

z = [1,2,3,4,5,6]

def softmax(a) : 
    c = np.max(a) 
    exp_a = np.exp(a-c) 
    sum_exp_a = np.sum(exp_a)
    y = exp_a / sum_exp_a
    return y

q = softmax(z)

Softmax with Temperature Parameter

def softmax_with_temperature(z, T) : 
    z = np.array(z)
    z = z / T 
    max_z = np.max(z) 
    exp_z = np.exp(z-max_z) 
    sum_exp_z = np.sum(exp_z)
    y = exp_z / sum_exp_z
    return y

calibrated_q2 = softmax_with_temperature(z, 2)
calibrated_q10 = softmax_with_temperature(z, 10)

Temperature 를 크게 줄 수록 각 확률 값들의 차이가 줄어듬을 확인할 수 있음

하지만, 순서는 변하지 않기 때문에 정확도에 영향을 주지 않음 

fig = sns.barplot(x=np.array([0,1,2,3,4,5]), y=q)
fig.set(ylim=(0,1))
plt.show()

fig2 = sns.barplot(x=np.array([0,1,2,3,4,5]), y=calibrated_q2)
fig2.set(ylim=(0,1))
plt.show()

fig3 = sns.barplot(x=np.array([0,1,2,3,4,5]), y=calibrated_q10)
fig3.set(ylim=(0,1))
plt.show()

[논문리뷰] 현대 딥러닝의 Calibration 에 대하여

현대 Neural network 의 calibration 에 관하여라는 논문을 리뷰하여 포스팅하겠습니다. 딥러닝의 성능 (performance) 이라 하면 일반적인 용어 '정확도' 를 뜻하는 경우가 많습니다. 그 정확도란 1) 예측 한 것중에 얼마나 맞았는가? 2) 데이터가 얼마나 잘 분류가 되었는가? 두 관점이 있으며, accuracy, precision (positive predictied value), recall (sensitivity), f1-score (precision 과 recall 의 조화평균) 등 대표적이고 많이 사용되는 measure 라고 할 수 있습니다. 하지만 calibration 도 정확도 못지 않게 중요한 성능이라고 할 수 있습니다. 본 논문에서는 '현대 뉴럴넷' 이 과거의 뉴럴넷보다 정확도는 향상되었지만, calibration 이 좋지 않다 (poorly calibrated) 라는 점을 문제로 삼으며, post-processing calibration method 인 temperature scaling 을 제시하고 있습니다.

Calibration 이란?

Calibration 이란 모형의 출력값이 실제 confidence (또는 이논문에서 calibrated confidence 로 표현) 를 반영하도록 만드는 것입니다. 예를 들어, X 의 Y1 에 대한 모형의 출력이 0.8이 나왔을 때, 80 % 확률로 Y1 일 것라는 의미를 갖도록 만드는 것입니다. 일반적으로 현대 딥러닝은 overconfident 합니다. 아래 그림은 1998 년 제시된 LeNet 과 2016년 제시된 ResNet (110 layer) 의 calibration 을 비교한 그림입니다. LeNet 의 경우 모형의 출력이 0~1 사이에 균일하게 분포되어있는 것을 볼 수 있지만, ResNet 의 경우 1 근처에 집중되어 있다는 것을 볼 수 있습니다. 그 결과로 아래 그림을 보면, ResNet 의 경우, confidence 와 accuracy가 많이 어긋난다는 것을 볼 수 있습니다. 모형의 출력이 실제 confidence 를 반영한다면 (calibrated confidence), confidence 와 accuracy 가 일치해야합니다. 

왜 Calibration 이 중요한가? 

모형의 예측값이, 실제 확률을 반영하는 것 (Calibration) 은  중요합니다. 딥러닝이 실제 세계에 응용될 때, 의사결정 프로세스의 하나의 구성요소가 되는 경우가 많습니다. 예를 들어, 의학적 진단 (computer-aided diagnosis)을 예로 들어보면, 딥러닝을 전적으로 신뢰해서 모든 판단을 딥러닝에 맡기는 식으로 의사결정이 이루어지는 경우는 적습니다. 딥러닝 모델의 confidence 가 낮은 경우에만 사람이 보는 방식으로 사람의 노동력을 줄이거나, false negative 가 치명적인 암 진단과 경우에는, cancer negative 로 예측한 것들 중, confidence 가 낮은 것만 사람이 재확인 하는 방식으로 하는 것도 가능합니다. 결국 이러한 의사 결정이 가능하기 위해서는 모형의 confidence 를 보는 것이 필요하고 이 confidence가 calibrated confidence 여야지 그 값에 신뢰성이 있다고 할 수 있습니다. 

Calibration Measures

모형의 Calibration 이 잘되었는지를 어떻게 확인할 수 있을까요? 논문에 나와있는 3가지 measure 를 정리해보았습니다. 

1) Reliability Diagram

Reliability diagram 은 expected accuracy 와 observed accuracy 를 각각 x, y 축으로 하여 그린 그래프를 말합니다. 이 때, expected accuracy (confidence) 를 기준으로 bin 을 쪼개서 (ex. decile) 각 bin 에서 observed accuracy 를 아래와 같이 구함으로써 그래프를 그릴 수 있습니다. 

파이썬 코드로 Reliability diagram 그리는 법을 참고 바랍니다. 

2) Expected Calibration Error (ECE) 

ECE 는 confidence와 실제 accuracy 의 차이의 기댓값으로 연속형 변수에서 이를 실제로 구할 수 있는 방법은 없습니다. 따라서 "binning" 을 통해 위와 같이 approximation 됩니다. ECE는 M 개의 bin 에 대하여 각 bin 마다의 expected accuracy 와 confidence 의 차이를 가중 평균 (weighted mean) 한 것입니다. 이 때 가중치는 위 식에 나와있듯, bin 의 sample size / 전체 sample size 입니다. 

3) Negative log likelihood

Negative log likelihood 는 통계 모형의 quality 를 평가하는데 표준적으로 많이 쓰이는 measure 입니다. 딥러닝/머신러닝 분야에서는 cross-entropy loss 라고도 불립니다 (분류 문제에 있어서). 이러한 log likelihood 와 cross-entropy 와의 관련성은 제 블로그 포스팅에서도 다룬적이 있으니 참고 바랍니다. Logistic regression 은 이 negative log likelihood 를 최소화 하는 계수를 찾게되며, 딥러닝도 cross-entropy 를 손실함으로 놓는다면, 마찬가지입니다. NLL 은 calibration 을 의미하는 measure 로 보기는 어려우나, calibration 도 어느정도 반영하고 있다고 볼 수 있습니다.  

현대 딥러닝 기법과 Calibration 의 관계

본 논문에서는 Model capacity 와 Regularization 방법이 miscalibration 과 관계가 있다는 실험 결과를 제시하고 있습니다. 하지만 이 부분에 대해 인과성을 단정할 수는 없습니다. 

1) Model capacity

최근 등장하는 딥러닝 모형들은 매우 많은 layer 를 갖고 있습니다. 적게는 수백개에서부터 수천개의 layer 가 있으며, layer 마다 수백개의 convolution filter 가 사용됩니다. 최근 연구에 따르면, 많은 layer 를 가질 수록 traninig set 의 특징을 더욱 잘 학습하고, generalization 도 더 좋다는 것을 보여주었습니다. 

위 figure 에서 가장 왼쪽 그림은 ResNet 에 대하여 64개의 filter 로 고정 후, depth 를 올리면서 error와 ece를 관찰한 그림입니다. depth 가 증가할 수록 error 는 줄어들지만 ECE는 증가하는 것을 확인할 수 있습니다. 왼쪽에서 두 번째 그림은 depth 를 고정시킨 후, filter 의 수를 증가시키면서 error와 ece 를 관찰한 것인데, 마찬가지로 error는 줄어들지만 ece 는 증가합니다. 후반부에는 유지되지만 초반부에 매우 빠르게 ece 가 증가하는 것을 확인할 수 있습니다. 즉, model capacity 가 클 수록 ece는 증가합니다. 이 이유는 모델이 training set 에 대한 loss 를 최소화하는 방향으로 학습되기 때문입니다. 그렇기 때문에 training set 을 완벽하게 분류할 수 있기 되더라도 loss 를 줄이기 위하여 confidence 를 높여 1에 가까운 값을 예측하기 때문입니다. 따라서 test set 에 대해 예측할 때도 마찬가지의 현상을 보이게 됩니다.  

2) Batch Normalization (BN)

Batch normalization 방법은 distribution shifts in activations 을 최소화해서 딥러닝의 optimization 및 regularization 을 향상시키는 방법입니다. batch normalization 의 도입은 매우 깊은 모델 (resnet, densenet 과 같은) 을 학습시킬 수 있는 한 가지 breakthrough 였습니다. 위 figure 의 3번째 그림을 보면 BN 이 calibration 에 미치는 영향을 볼 수 있습니다. 결론은 BN 의 도입은 calibration 을 낮추며, 원인은 알 수 없다는 것입니다. 

3) Weight decay 

BN 의 도입 이후 최근 weight decay 가 많이 쓰이지 않는 regularization 방법입니다. BN 논문에서 L2 regularization 를 쓰지 않는게 일반화에 도움이 된다는 내용이 보고되기도 했습니다. 따라서 최근에는 weight decay 를 과거와 비교하여 매우 작게 주는 것이 일반적입니다. 하지만 안타깝게도 이것은 calibration 에 좋지 않은 영향을 준다고 합니다. 위 figure의 가장 오른쪽 그림을 보면 weight decay 를 크게 줄 수록 오히려 ece 가 좋아지며, weight decay 가 적을 수록 ece 가 증가합니다. 직관적으로도, weight decay 가 적으면 training set 에 대해 loss 를 최소화 시키는 weight 가 얻어지는 것이기 때문에 test set 에 대해 overconfident 한 모델이 얻어질 것이라는 것을 짐작할 수 있습니다. 

Calibration 방법 

Post-processing calibration 은 모델의 예측 확률로부터 Calibrated probability 를 구하는 과정입니다. 이 방법은 validation set 이 필수적으로 필요합니다 (물론 이 validation set 은 training 할 때 쓰인 validation set 과 같은 set 이어야 합니다.).

Post-processing calibration의 목적은 모델의 예측값 p 로부터 calibrated probability q 를 구하는 것입니다. 간단하게 positive class, negative class 로 나뉘어진 binary prediction 을 예로 들어봅시다. 첫 번째로 소개할 방법은 Histogram binning 방법입니다. 

1) Histogram Binning : Zadrozny 는 2001 년 ICML 에서 decision trees and naive bayesian classifier 의 예측값을 calibration 하는 방법을 제시했습니다. Histogram binning 은 매우 간단하고 직관적인 calibration 방법으로 non-parametric calibration 방법입니다. 절차는 아래와 같습니다. 

* Bin-wise squared loss

여기서 1은 indicator function 입니다. 이를 최소화하는 theta1~theta_m 을 구해서 이를 bin 마다의 score로 쓰는 것입니다. 위 식을 최소화하면 결국 스코어는 해당 bin 에서의 positive-class 의 비율이 됩니다. 즉, histogram binning 방법은 예측값을 binning 한 후, 각 bin 에서의 positive-class 의 비율로 확률을 재할당하는 것으로 이해할 수 있습니다. 

2) Platt scaling: Platt scaling 은 1999년 Platt 이 제시한 방법으로 SVM 의 출력을 '확률화' 하기 위한 방법으로 제시되었습니다. Platt scaling 은 histogram binning 과는 다르게 parametric 방법입니다. 최초로 제시된 이 방법에서는 모형의 출력을 logistic regression 의 input 으로 넣습니다. 뉴럴넷의 경우, 최종 모델의 출력값이 sigmoid 되기 전의 값 z 를 아래와 같이 변환합니다. 

$$ q_i = \sigma(az_i + b) $$

이 때, a, b 는 validation set 에 대해서 NLL (=binary cross entropy) 을 최소화 시키는 방향으로 학습이 됩니다. 당연하지만 이 과정에서 학습된 뉴럴넷의 weight는 영향을 받지 않습니다. 

3) Temperature scaling: Temperature scaling 은 Platt scaling 에 기초한 방법입니다. K 개의 label 이 있는 다중 분류 문제에서 Temperature scaling 방법에서는 단일 scalar parameter T 를 이용해 logit vector z 를 아래와 같이 변환합니다. 

본 논문의 저자는 T 를 temperature 라고 부릅니다. T 는 soft max function 을 "soften" 시키는 일을 합니다. T 가 커질 수록 최종 calibrated probability q 는 1/K 로 수렴합니다 (이것은 uncertainty가 극대화 된다는 의미입니다). 식을 보면 T 가 1일 때가 원래 softmax를 이용하여 confidence 를 구하는 방법이라는 것을 알 수 있습니다. T는 validation set 에 대해 NLL 을 최소화 하는 식으로 optimization 하는 방법입니다. T 의 장점은 argmax 를 바꾸지는 않는다는 것입니다. 즉, T 는 모델의 정확도에는 영향을 주지 않고, Calibration 에만 영향을 줍니다. 

참고

https://arxiv.org/pdf/1706.04599.pdf

https://machinelearningmastery.com/calibrated-classification-model-in-scikit-learn/