Data science (94)

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 를 구함으로써 알 수 있다. 

 

참고자료

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/

 

Positive-unlabeled learning

A subfield of semi-supervised machine learning, where the only labeled data points available are positive.

roywrightme.wordpress.com

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

 

GitHub - AaronWard/PU-learning-example: An example repo for how PU Bagging and TSA works.

An example repo for how PU Bagging and TSA works. - GitHub - AaronWard/PU-learning-example: An example repo for how PU Bagging and TSA works.

github.com

 

 

언제할까?

최근 다양한 도메인에서 머신러닝이 활용되고 있다. 머신러닝의 문제점은 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 하다. -> 잘만 되면 더 비용효율적이다. 

다양한 SSL 방법론에 따른 decision boundaries

 

 

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 

Autoregressive Processes

Autoregressive process 란 history 가 현재 값에 직접적인 영향을 주는 time series 를 말한다. 식으로 표현하면 아래와 같다. 

현재시점 (t) 의 값은 과거 시점들 (t-1 ~ t-p) 의 값을 가중치를 두고 합한 값에 error term (Z) 을 더한 값이다. 

 

$$ X_t = Z_t + \phi_1(X_{t-1})  + \phi_2(X_{t-2}) ... + \phi_p(X_{t-p}) $$

 

Example

p=2 이고, 가중치가 0.7, 0.2 인 autoregressive process 는 아래와 같다.

 

$$ X_t = Z_t + 0.7X_{t-1} + 0.2X_{t-2} $$

 

이를 R 코드로 구현하면 아래와 같다. 선차트를 통해 보면 현재 값이 과거 값과 높은 상관성이 있다는것을 확인할 수 있다. correlogram 을 통해 가까운 시간에 측정된 값이 현재값과 더 높은 상관성이 있다는것을 확인할 수 있다. (가중치가 0.7, 0.2 이므로)

set.seed(2017)
X.ts <- arima.sim(list(ar=c(0.7,0.2)), n=1000)
par(mfrow=c(2,1))
plot(X.ts, main="AR(2) Time series, phi1=0.7, phi2=0.2")


X.acf <- acf(X.ts, main="Autocorrelation of AR(2) Time series")
X.acf

 

Moving average process 와의 관계 

Autoregressive process 는 moving average process 의 무한 수열로 나타낼 수 있다. 

 

차수 (p) 가 1인 AR 을 생각해보자.

아래와 같이 식을 쓸 수 있다. (Z는 평균이 0, 분산이 sigma^2 을 따른다고 가정하고, phi 를 theta 로 치환하자.) 

 

$$ X_t = Z_t + \phi X_{t-1} = Z_t + \phi Z_{t-1} + \phi^2 X_{t-2} ... = Z_t + \theta_1 Z_{t-1} + \theta_2 X_{t-2} ... $$

 

AR (1) 의 통계량

위와 같이 식을 써서 moving average 처럼 표현하면 AR process 에서의 X(t) 의 기댓값과 분산을 쉽게 구해볼 수 있다. 

 

$$ E(X_t) = 0 $$

$$ V(X_t) = \sigma^2 \sum^{\infty}_{i=0}\theta_i^2  $$ 

 

time series 가 stationarity 를 만족하기 위해서는 분산이 t 에따라 바뀌지 않고, 일정해야한다. 그렇기 때문에 phi 의 절댓값이 1보다 작은것은 stationarity 에 대한 필요 조건이라고 할 수 있다. 

 

AR(1) 의 auto covariance function 

MA process 의 acf 와 유사한 형태라는것을 확인할 수 있다. (link)

 

$$ \gamma(k) = \sigma^2 \sum^{\infty}_{i=0} \theta_i \theta_{i+k} $$ 

 

AR(1) 의 auto correlation coefficient 

 

$$ \rho(k) = \frac{\sum^{\infty}_{i=0} \theta_i \theta_{i+k}}{\sum^{\infty}_{i=0} \theta_i \theta_i} $$ 

 

theta 를 phi 로 치환하여 AR(1) 의 auto covariance 와 auto covariance coefficient 를 구해보자. (무한등비수열 공식 사용하여 정리) 

 

$$ \gamma(k) = \sigma^2 \frac{\phi^k}{1-\phi^2} $$

$$ \rho(k) = \phi^k $$

 

AR Process 의 Stationarity 를 확인하는 방법

Example: AR(1) process

 

$$ X_t = Z_t + \phi X_{t-1} $$ 

 

위 AR(1) process 에서 Z 를 제외한 나머지 텀들을 한쪽으로 옮겨서 아래와 같은 식을 만들 수 있다.

 

$$ \phi(B) = 1-\phi B $$ 

 

이 때, 우변을 0으로 만드는 B 의 해를 찾는다. 해는 B = 1/phi 이다. B 의 해가 단위원 (unit circle) 바깥에 있는 것이  stationarity 를 만족하기 위한 조건이 된다. 따라서 AR(1) 모델에서는 phi 의 절댓값이 1 미만이어야 stationarity 를 만족한다. 

 

Example: AR(2) process 

 

$$ X_t = \frac{1}{3} X_{t-1} + \frac{1}{2} X_{t-2} + Z_t $$

 

$$ \phi(B) = 1-\frac{1}{3} B-\frac{1}{2} B^2 $$

 

위 식에서 B 의 해를 찾으면 (-2+sqrt(76))/6, (-2-sqrt(76))/6 이 된다. 위 두 값이 모두 단위원 바깥에 있기 때문에 위 AR(2) process 는 stationarity 를 만족한다. 

 

 

Week stationarity

이전 포스팅에서 개념을 직관적으로 소개하였다. 이번엔 좀 더 포멀한 정의와 함께 예시를 통해 설명해보려고한다.

 

아래 조건을 만족할 때 weekly stationary 라고 부른다. 

 

1) 시간에 따른 평균이 같다. 

$$ \mu(t) = \mu  $$ 

 

2) Auto covariance function 이 time spacing 에만 의존한다. (t2=t1+tau 라고 생각하면 이해가 쉽다.)

$$ \gamma(t_1, t_2) = \gamma(t_2-t_1) = \gamma(\tau) $$

: 이는 시간에 따른 분산이 같다는 조건을 포함하는 조건이다. 

 

Examples

실제 시계열 데이터의 예시를 통해 stationarity 에 대해 더 이해해보려고한다. 

 

1) White noise 는 stationarity 를 만족한다.

 

White noise model

$$ X_t \sim N(0, \sigma) $$

 

White noise model은 시간에 따른 평균이 같다. 

$$ \mu = 0 $$

 

White noise model은 Auto covariance function 이 time spacing 에만 의존한다.

$$ \gamma(t_1, t_2) = 0, \ when \ t_1 = t_2 $$

$$ \gamma(t_1, t_2) = \sigma^2, \ when \ t_1 \neq t_2 $$

 

2) Random walk 는 stationarity 를 만족하지 않는다.

 

Random walk model

random walk 모델은 시간이 갈수록 분산이 커진다.

아래 식에서 X(t) 를 random walk model 이라고 한다. 

$$ Z_t \sim iid(\mu, \sigma^2) $$

$$ X_t = X_{t-1} + Z_t = \sum^{t}_{i=1}Z_i $$

 

따라서 Random walk model 의 시간에 따른 평균은 t*mu 이고, 분산은 t*sigma^2 이다. 만약 Z의 평균이 0이라고 가정하더라도 분산이 시간에 따라 점점 커진다는 것을 알 수 있다. 따라서 Random walk model 은 stationarity 를 만족하지 않는다. 

 

3) Moving average model 는 stationarity 를 만족한다. 

 

moving average model 

$$ X_t = Z_t + \theta_1 Z_{t-1} + \theta_2 Z_{t-2} ... + \theta_q Z_{t-q} $$

$$ Z_t \sim Normal(\mu, \sigma) $$

 

moving average 의 parameter q 와 가중치 theta 를 고정해놓고 계산을 하면, 평균과 분산은 t 와는 관계 없이 고정된다는 것을 알 수 있다. 따라서 moving average model 은 stationarity 를 만족한다. 

 

추가적으로 Moving average model 의 auto covariance function 을 구해보자. 

moving average model 은 stationarity 를 만족하기 때문에 auto covariance function 은 time spacing 에만 의존한다. 또한 이전 포스팅에서 time spacing 이 최대 q 인 경우에만 자기상관성이 존재한다는 것을 correlogram 을 통해 확인할 수 있었다. moving average model 의 노이즈의 평균이 0일 때를 가정하고 covaraicne 를 구해보자.

 

$$ Z_t \sim Normal(0, \sigma) $$

$$ Cov(X_t, X_{t+k}) = E(X_t X_{t+k}) - E(X_t)E(X_{t+k}) =  E(X_t X_{t+k}) $$

 

위 기댓값을 정리하면 아래와 같은 식이 된다.

 

$$ Cov(X_t, X_{t+k}) = E(X_t X_{t+k}) = \sigma^2 \sum_{i=0}^{q-k} \beta_i \beta_{i+k}, \ when \ k \leq q $$

$$ Cov(X_t, X_{t+k}), \ when \ k \gt q $$ 

 

참고) 위 식의 정리에는 아래 기댓값과 분산의 성질을 이용하면 된다.

$$ V(X) = E(X^2) - E(X)^2 $$

$$ E(XY) = E(X)E(Y), \ when \ X, \  Y \ is \ independent $$ 

 

 

Moving average process

특정 시점 t에서의 주가를 X_t 라고하자. 또한 특정 시점 t 에서의 회사의 공지 Z_t (noise) 가 주가에 영향을 미친다고 하자. 그런데 과거 시점 (t-1, t-2...) 에 회사의 공지도 주가에 영향을 미친다. 이런 경우에 X_t 를 다음과 같이 모델링할 수 있다.

 

$$ X_t = Z_t + \theta_1 Z_{t-1} + \theta_2 Z_{t-2} ... + \theta_q Z_{t-q} $$

$$ Z_t \sim Normal(\mu, \sigma) $$

 

이 때, q는 어떤 시점의 noise 까지 현재값에 영향을 미치는지를 의미하며, MA(2) 는 이와 같이 정의된다. 

 

MA(2) Process

 

$$ X_t = Z_t + \theta_1 Z_{t-1} + \theta_2 Z_{t-2} $$

$$ Z_t \sim Normal(\mu, \sigma) $$

 

MA(2) process 의 예를 들면 아래와 같다. 

 

$$ X_t = Z_t + 0.7 Z_{t-1} + 0.2 Z_{t-2} $$

 

MA(2) simulation

 

위에 예시로 든 MA(2) process 를 R 을 통해 simulation 해보자.

# noise 생성
noise <-rnorm(10000)

ma_2 = NULL

# ma(2) 생성을 위한 loop
for (i in 3:10000) {
  ma_2[i] = noise[i] + 0.7*noise[i-1]+0.2*noise[i-2]
}

# shift 
moving_average_process <- ma_2[3:10000]
moving_average_process <- ts(moving_average_process)

par(mfrow=c(2,1))

plot(moving_average_process, main = "A moving average process of order 2", ylab = "")
acf(moving_average_process, main = "Correlogram of ma (2)", ylab = "")

correlogram 을 보면 time step 이 0,1,2 인 경우에만 상관성이 있는 것을 확인할 수 있다. 우선, time step 이 0 인 경우는 항상 auto correlation coef 1이다. 또한 현재값에는 최대 2 time step 전의 noise 까지 반영이 되기 때문에, 최대 2 time step 의 값과 상관성이 있다는 것을 확인할 수 있따. 

Random walk model

아래와 같이 정의되는 X_t 를 random walk 이라고 한다. X_t 는 이전 time step 에서의 값 X_t-1 에 noise Z가 더해진 값이다. random sampling 과 다른점은 현재값이 이전값에 더해진다는것이다. 이는 랜덤하게 어떤 한 방향으로 걷는것과 비슷하다. 매번 시작점에서 한발짝 걷는 것이 아니라 한발짝 걸어서 도착한 곳에서 다시 한발짝을 간다. 

 

$$ X_t = X_{t-1} + Z_t $$

$$ Z_t \sim Normal(\mu, \sigma) $$

 

이러한 random walk 모델에서 X_t 는 이전 time step 에서의 값 X_t-1 과 매우 큰 연관성을 갖는다. 따라서 non-stationary time series 데이터이다. 

 

Random walk model simulation in R

R 로 random walk 모델을 만들어보자. 아래는 1000개의 random walk 데이터를 생성하는 예제이다. 시계열 그래프를 그려보면, 이 데이터는 non-stationary time series 데이터라는 것을 확인할 수 있다. 구간을 나눠서보면 트렌드를 보이기 때문이다. 

x <- NULL
x[1] <- 0
for(i in 2:1000){
  x[i] <- x[i-1]+rnorm(1)
}

random_walk <- ts(x)
plot(random_walk, main="A random walk", ylab="", xlab=" Days", col="black")

위 그림은 전형적인 random walk 그래프이다.

 

random walk 데이터에서 correlogram 을 그려보자. 인접한 time step 에서 auto correlation coefficient 가 큰 패턴을 보이기 때문에 non-stationary time series 라는 것을 다시 확인할 수 있다. 

acf_result <- acf(random_walk)

random walk 모델에서 noise Z는 stationary time series 라고 볼 수 있다. 

 

$$ Z_t \sim Normal(\mu, \sigma) $$

 

noise 가 stationary time series 라는 것을 데이터로 실제로 확인해보자. 

random_walk_diff <- diff(random_walk)
plot(random_walk_diff, main="A random walk diff", ylab="", xlab=" Days", col="black")

 

 

참고자료

https://people.duke.edu/~rnau/411rand.htm

Auto correlation coefficient 

앞선 포스팅에서 auto covariance coefficient 에 대해 설명하였다. auto covariance coefficient 은 time series 데이터에서의 각각의 time point 간 연관성을 의미하는데, stationary time series 에서는 k 라고하는 parameter 에 의해 달라진다. auto covariance coefficient 의 추정값 c_k 는 아래와 같이 계산된다. 

 

$$ c_k = \frac{\sum^{N-k}_{t=1}(x_t - \bar{x})(x_{t+k}-\bar{x})} {N-k} $$

 

이번에는 auto correlation coefficient 에 대해 정리해보려고 한다. auto correlation coefficient 도 auto covariance coefficient 와 마찬가지로 time series 데이터에서 time step 별 값의 연관성을 의미하는데 범위를 -1~1로 조정한 것으로 이해할 수 있다. 마치 공분산과 상관계수의 관계와 같다.

 

auto correlation coefficient 의 계산식은 아래와 같다. 

 

$$ -1 \leq \rho_k = \frac{\gamma_k}{\gamma_0} \leq 1 $$

 

이 때, rho_k 의 추정값 r_k 는 아래와 같다. c0 는 time step (=lag) 이 0일 때의 auto covariance coefficient 로 이는 분산과 같다.  

 

$$ \rho_k \sim r_k = \frac{c_k}{c_0} $$

$$ c_0 = \frac{\sum^{N}_{t=1}(x_t-\bar{x})^2}{N}  $$

 

Correlogram

rho_k 의 추정값을 k 에 따라 구한 뒤, 이를 시각화해서 표현한 것을 correlogram 이라고 한다. 이 때, rho_0 은 항상 1이다. (자기 자신과의 연관성이기 때문이다.) 

 

$$ r_0 = \frac{c_0}{c_0} , r_1 = \frac{c_1}{c_0} ... $$ 

 

R 에서 correlogram 은 acf 함수를 통해 쉽게 그려볼 수 있다.

 

예제 1)

아래 R 코드는 100개의 표준정규분포를 따르는 데이터를 만든 후, correlogram 을 그리는 코드이다. 파란선은 연관성이 유의한지에 대한 임계치를 의미한다. 유의한 데이터 포인트가 하나 밖에 없고, lag 에 따른 패턴이 보이지 않으므로, 전체적으로 시계열 데이터가 자기상관성이 없다고 결론 내릴 수 있다.  

 

purely_random_process <- ts(rnorm(100))
print(purely_random_process)
plot(purely_random_process)

auto_correlation_coef_by_lags <- acf(purely_random_process)
print(auto_correlation_coef_by_lags)

예제 2)

실제 데이터를 correlogram 을 그려보자. 다음은 모 어플리케이션의 월간 활성 이용자수 (MAU, monthly active user) 추이이다. 이 서비스는 점점 성장하는 추이를 보여주고 있다. 시계열 데이터의 관점에서는 시간에 따른 평균의 변화 (trend) 를 보이는 non-stationary time series 이다. 

위 데이터에서 correlogram 을 그리면 아래와 같이 나타난다. lag 에 따른 auto correlation coef 의 패턴이 보이며 (점점 감소), 인접한 데이터 포인트에서는 유의한 상관성을 보이고 있는 것을 확인할 수 있다. 

Time series data (시계열 데이터) 

어떤 종류의 데이터이든 상관 없으며, 그저 시간에 따라 수집된 데이터를 시계열 데이터 (timeseries data) 라고 한다. 

한국의 일별 코로나19 신규 확진자수 추이

예를 들어, 일별 코로나 확진자수는 1일이라고 하는 time step 으로 수집된 시계열 데이터의 한 종류이다. 

 

Week stationary time series 

week stationary time series 란 다음의 조건을 만족한다. 

 

1) 시간에 따른 평균 (mean) 에 변화가 없다. 

2) 시간에 따른 분산 (variance) 의 변화가 없다. 

3) 주기적인 등락 (flucation) 이 없다.

 

이러한 조건을 만족하긴 위해서는 time series 의 한 섹션 (A 섹션) 고른 후, 다른 섹션 (B 섹션) 을 골랐을 때, A, B 섹션이 비슷하면 된다. 

 

Stochastic process

random variable 의 collection - X1,X2,X3 .. 가 있다고 하자. 이들이 각각 다른 모수를 가진 분포를 따를 때, 이를 stochastic process 라고 한다. stochastic process 의 반대개념은 deterministic process 이다. deterministic process 는 모든 step (t) 에 대해서 예측 가능하다. 예를 들어, 어떤 함수에 대한 미분함수는 특정 X 에서의 Y 값을 정확하게 알 수 있다. 이와 반대로 stochastic process 는 매 step 이 random 이기 때문에 어떤 확률 분포에서 왔다는 것만을 알 수 있을 뿐, 값을 정확하게 예측할 수 없다.

 

$$ X_t \sim distribution(\mu_t, \sigma_t) $$

 

예를 들어, 다음과 같은 시계열 데이터가 있다고 해보자. 

 

$$ X_1 = 30, X_2 = 29, X_3 = 57 ... $$ 

 

시계열 데이터를 바라보는 한 가지 관점은 stochastic process 의 실현 (realization) 으로 보는것이다. 매 timestep 별로 어떤 확률 변수가 정해지고 우리는 그 확률변수에서 나온 하나의 샘플값을 관찰하는 것이다. 

 

Autocovariance function

stationary time series 라는 가정을 하자. 두 가지 timestep s,t 에서의 covariance 를 정의해볼 수 있다. (확률 변수이기 때문)

 

$$ \gamma(s,t) = Cov(X_s, X_t) $$

$$ \gamma(s,s) = Var(X_s)   $$  

 

또한 아래처럼 covariance function 을 정의할 수 있는데, 이 함수는 stationary time series 라는 가정 하에 t 에 따라서는 값이 바뀌지 않으며, k가 결정하는 함수가 된다. (아래 식에서 c 는 추정값이다.) 이러한 time step (k) 에 따른 공분산의 식을  autocovariance function  이라고 한다. 

 

$$ \gamma_k = \gamma(t, t+k) \sim c_k $$ 

 

즉, stationary time series 에서는 Cov(X1, X2) 나 Cov(X10,X11) 이나 기댓값은 같다고 할 수 있다. 그 이유는 데이터에서 두 가지 섹션을 선택했을 때, 그 모습이 똑같다고 기대하는것이 stationary time series 이기 때문이다.  

 

또한 gamma(t_k, t) 는 autocovariance coefficient 라고 하며, stochastic process 에서의 실제 autocovariance 값이다. 데이터를 통해 구한 c_k 를 통해 autocovariance coefficient 를 추정한다. 

 

Autocovariance coefficient

그러면 Autocovariance coefficient 의 추정값은 어떻게 구할까? timestep 을 k 라고 할 때, 추정값은 아래와 같다. 

 

$$ c_k = \frac{\sum^{N-k}_{t=1}(x_t - \bar{x})(x_{t+k}-\bar{x})} {N} $$

 

이는 time series 데이터에서 k time step 만큼 차이나는 점들의 묶음 (x_t, x) 을 확률 변수의 관찰값으로 놓고 추정한 covariance 와 같다.

 

참고로 확률 변수 X,Y 의 covariance 의 추정값은 아래와 같이 구할 수 있다. 

 

$$ s_{xy} =  \frac{\sum^{N}_{t=1}(x_t - \bar{x})(y_t-\bar{y})} {N-1} $$

 

R 에서는 acf 함수를 통해 auto covariance coefficient 추정값을 계산할 수 있다. 

purely_random_process <- ts(rnorm(100))
print(purely_random_process)
plot(purely_random_process)

auto_covariance_coef_by_lags <- acf(purely_random_process, type = "covariance")
print(auto_covariance_coef_by_lags)


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


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


Decision trees can be unstable because small variations in the data might result in a completely different tree being generated. This problem is mitigated by using decision trees within an ensemble.


The problem of learning an optimal decision tree is known to be NP-complete under several aspects of optimality and even for simple concepts. Consequently, practical decision-tree learning algorithms are based on heuristic algorithms such as the greedy algorithm where locally optimal decisions are made at each node. Such algorithms cannot guarantee to return the globally optimal decision tree. This can be mitigated by training multiple trees in an ensemble learner, where the features and samples are randomly sampled with replacement.


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


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