통계학

Quantile normalization

생물정보학에서 자주 사용되는 정규화 방법 중 하나인 quantile normalization이다. Quantile normalization은 비교하려는 샘플들의 분포를 완전히 동일하게 만들고 싶을 때, 또는 기준이 되는 분포(reference distribution)가 있는 경우 샘플들의 분포를 모두 기준 분포와 동일하게 만들고 싶을 때 사용할 수 있다.

복잡한 방식을 사용하는 과정이 아닌지라 쉽게 이해하고 쉽게 써먹을 수 있다.

 

알고리즘

  1. 샘플 내 값을 오름차순 정렬
  2. 아래 과정을 모든 n에 대하여 반복
    1. (기준 분포가 있을 떄)
      1. 모든 샘플의 n 번째 값들을 기준 분포의 n 번째 분위수로 대체
    2. (기준 분포가 없을 때)
      1. 각 샘플의 n 번째 값들을 평균(또는 중간값)
      2. 각 샘플의 n 번째 값들을 모두 2-1.의 값으로 대체
  3. 정렬된 데이터를 원래 데이터의 순서대로 복구

 

이해가 어렵다면 바로 아래 “예시”로 넘어가도 된다.

“값들을 순서대로 나열했을 때 n 번째 값”이 바로 통계학에서의. n 번째 분위수(n-th quantile)의 개념에 해당하고, 각 샘플 분포의 n 번째 분위수를 동일하게 조정해주는 작업이므로 quantile normalization이라는 이름이 붙었다.

딱히 알고리즘이랄 것도 없다. 1.에서 정렬 시 오름차순 대신 내림차순을 써도 아무 상관이 없다. 기준 분포가 없을 때 2-1.에서 평균, 중간값 대신 가중평균 등 자신에게 적합한 대푯값을 사용해도 된다.

 

예시

1. 이해를 위한 간단한 예시

다음 테이블과 같은 세 샘플(A, B, C)의 데이터가 있다고 하자. A, B, C의 분포가 동일해지도록 median quantile normalization해보자. 셀 색상은 원래 데이터의 순서를 표시하기 위해 넣어보았다.

qn_whole

  1. 열 별로 값을 정렬한다.
  2. 정렬된 데이터에서 행 별로 중간값을 계산한다.
  3. 각 행의 값을 2.에서 계산한 중간값으로 바꾼다.
  4. 정렬을 해제하여 기존 데이터와 같은 순서로 돌려준다

 

2. 규모가 좀 더 큰 예시

서로 다른 샘플에 어떤 실험을 한 결과 데이터가 세 세트(A, B, C) 있다고 하자. 세 샘플을 용이하게 비교하기 위해 샘플의 분포를 quantile normalize하여 동일하게 만들어보자.

 

기준 분포가 있을 때

표준정규분포를 기준 분포로 삼는다고 하자.

정규화 전 각 샘플의 분포는 아래와 같다.

A  B   C
0   3.570614    5.015660    6.526778
1   5.965098    1.258324    2.285988
2   3.767857    0.974910    4.374467
3   3.538398    3.362349    1.779624
4   5.178286    1.575602    3.065568
5   3.578033    3.434900    5.086503
6   5.330161    3.431059    3.573926
7   5.002079    4.885904    2.318780
8   5.694074    4.000688    4.615286
9   6.026262    -0.499165   1.999979
before

 

표준정규분포의 101-quantile을 사용하여 quantile normalization하면,

A  B   C
0   -1.000990   1.410420    1.410420
1   0.960838    -1.180947   -1.000990
2   -0.922178   -1.346263   0.162024
3   -1.086568   0.162024    -1.232341
4   0.162024    -0.848716   -0.476577
5   -0.960838   0.263612    0.620918
6   0.289397    0.238000    -0.187224
7   -0.012409   1.232341    -0.922178
8   0.651302    0.682300    0.368003
9   1.042824    -2.330079   -1.132497
after_ref

모든 샘플의 분포가 표준정규분포와 일치하는 것을 확인할 수 있다.

 

기준 분포가 없을 때

기준 분포가 없이 median을 사용하여 정규화하면,

A  B   C
0   -1.000990   1.410420    1.410420
1   0.960838    -1.180947   -1.000990
2   -0.922178   -1.346263   0.162024
3   -1.086568   0.162024    -1.232341
4   0.162024    -0.848716   -0.476577
5   -0.960838   0.263612    0.620918
6   0.289397    0.238000    -0.187224
7   -0.012409   1.232341    -0.922178
8   0.651302    0.682300    0.368003
9   1.042824    -2.330079   -1.132497
after

역시 마찬가지로 모든 샘플의 분포를 동일하게 만들 수 있다.

 

참고

이 코드를 돌리면 예시 2-2를 직접 해볼 수 있다.

Sequence Motif 등장 확률

전체 n ntd로 이루어진 target RNA 한 가닥이 있다고 하자. 이 RNA는 완전히 랜덤하게 만들어진 가닥이라고 가정한다. 즉, 각 위치에 A, U, G, C가 같은 확률로 존재할 수 있다.

이제 k-mer sequence motif가 하나 있다고 하자. 이 sequence motif는 특정되어 있다.

이 때 Target RNA 가닥에서 이 motif가 한 번이라도 등장할 확률은 얼마일까?

우연한 기회에 이 문제에 대해 생각해보게 되어 여사건의 확률 등의 방법을 생각해보다 이런 방법으로는 쉽게 풀리지 않는다는걸 알게 되었다.

검색을 해봐도 정확한 해답을 제시하는 사람은 많지 않았다 (너무 쉬운 문제여서 인지?). 여기서는 확률의 inclusion-exclusion principle을 이용한 해답을 소개하려 한다.

마주서기 문제

본 문제와 비슷하지만 비교적 단순한 문제를 먼저 살펴보자.

n쌍의 부부가 있다. 한 쪽에는 남편끼리, 다른 쪽에는 부인끼리 늘어 설 때, 적어도 한 쌍의 부부가 서로 마주보고 설 확률은 얼마일까?

이 문제 역시 여사건의 확률을 이용해서 풀기는 쉽지 않다 (재귀함수를 만들게 된다). 대신 inclusion-exclusion principle을 사용해서 풀어보자.

사건 A_i를 “i번째 부부가 서로 마주보고 서는 사건”이라고 하자. 그러면

\begin{array}{lcl} &&P(A_i) = \dfrac{(n-1)!}{n!} \text{, } i=1, ..., n \\ &&P(A_i \cap A_j) = \dfrac{(n-2)!}{n!} \text{, } i < j \\ && ... \\ &&P(A_1 \cap A_2 \cap ... \cap A_n) = \dfrac{1}{n!} \end{array}

이므로

\begin{array}{lcl} P(\cup_{i=1}^{n} A_i) &=& \sum_{i=1}^{n}P(A_i) - \sum_{i<j}P(A_i \cap A_j) \\ & & + ... + (-1)^{n+1}\sum_{i<j<...<l}P(A_i \cap A_j \cap ... \cap A_l) \\ &=& \sum_{i=1}^{n} (-1)^{i+1} \dfrac{1}{i!} \end{array}

이다.

본 문제

사건 A_i \text{, } i=1, ..., m를 “i번째 위치에 motif가 등장하는 사건”이라고 하자. 단 mnk로 나눈 몫이다. 그러면

\begin{array}{lcl} &&P(A_i) = \dfrac{4^{n-k}}{4^n} \text{, } i \leq n-(k-1) \\ &&P(A_i \cap A_j) = \dfrac{4^{n-2k}}{4^n} \text{, } i<j \text{ and } i, j \leq n-2(k-1) \\ &&P(A_i \cap A_j \cap A_k) = \dfrac{4^{n-3k}}{4^n} \text{, } i<j<k\text{ and } i, j, k \leq n-3(k-1) \\ &&... \\ &&P(A_1 \cap A_2 \cap ... \cap A_m) = \dfrac{4^{n-mk}}{4^n} \end{array}

이므로 마주서기 문제에서와 같은 방법으로

P(\cup_{i=1}^{m} A_i) = \sum_{i=1}^{m} (-1)^{i+1} \binom{n-i(k-1)}{i} 4^{-ki}

임을 알 수 있다.

이 방법으로 1~500 ntd의 random target sequence에 3, 4, 7-mer fixed motif가 존재할 확률을 그래프로 나타내보면 다음과 같다.

Thu Oct 25 00:15:46 2018

Update:

위 방법이 일부 상황에서 정확한 값을 반환하지 않는다고 한다. 더 일반적인 경우에도 사용 가능한 Markov chain 방법을 쓴 Udaqueness 님의 글을 참고.


참고

Batch Normalization 이해하기

현대적인 딥러닝 모델을 디자인할 거의 항상 빠지지 않고 쓰이는 테크닉들이 있다. 하나는 recurrent 구조 (LSTM, Attention)이고 다른 하나는 batch normalization (BatchNorm)이다. LSTM과 attention 대해서는 recurrent neural net 다루면서 자세히 살펴보도록 하고 이번 글에서는 학습 과정에서 뉴럴넷을 안정시켜주는 표준화 기법 하나인 batch normalization 대해 다뤄보겠다.

 

  • 기존 방법의 문제점
  • BatchNorm
    • 알고리즘
    • 테스트할 때
    • BN layer
  • TensorFlow 구현

 

기존 방법의 문제점

BatchNorm이 어떤 의미를 가지는지를 알기 위해서는 BatchNorm이 고안되기 이전의 딥러닝 모형 초기화 및 학습 과정 표준화 과정을 둘러볼 필요가 있다.

뉴럴넷이 안정적으로 잘 학습되기 위해서는 입력층에 넣을 인풋과 각 층의 weight를 표준화할 필요가 있다. BatchNorm이 고안되기 전에는 두 가지 방법을 주로 사용했는데, 이전 포스트[1, 2]에서 각각의 방법을 간단히 다룬 바 있다. 간단히 복기하자면 이렇다: (1) 인풋은 centering scaling하고 (2) 인풋 뉴런 n개인 층의 weight \div \sqrt{n/2}로 표준화한다. 단순한 방법이지만 표준화하지 않은 입력, 가중치값을 사용했을 때에 비해 더 빨리, 더 좋은 성능으로 수렴하는 것을 경험적으로 확인할 수 있다.

여기서 중요한 문제가 발생한다. 입력층에 넣는 인풋은 표준화할 수 있다. 뉴럴넷에 넣기 전에 우리가 원하는 방식으로 원하는 만큼 preprocessing을 하면 된다. 그 결과 입력층의 input distribution은 항상 비슷한 형태로 유지가 되고 안정적으로 가중치 학습을 진행할 수 있다.

e18489e185b3e1848fe185a6e1848ee185b53.png

그러나 은닉층은 인풋의 분포가 학습이 진행됨에 따라 계속 변한다. 은닉층은 이전 레이어의 activation f(XW)을 입력으로 받는다. 학습 과정에서 가중치 W의 값이 W^\prime로 업데이트되면 이전 레이어의 activation 또한 f(XW^\prime)로 바뀌게 된다. 은닉층의 입장에서는 인풋 값의 분포가 계속 널뛰는 것이나 마찬가지이다. 입력 분포의 형태가 유지되지 않으므로 학습도 잘 진행되지 않는다. 그라디언트 값이 큰 학습 초기일수록 문제가 더 심각해진다.

스케치

 

Batch Normalization

알고리즘

바로 위에서 언급한 문제를 internal covariate shift라고 한다. 그대로 입력층보다 깊은, 내부에 있는(internal) 층의 입력값, 공변량(covariate) 고정된 분포를 갖지 않고 이리저리 움직인다(shift) 의미이다. BatchNorm 바로 internal covariate shift 해결하는 테크닉이다.

[1]

은닉층의 입력도 표준화한다면 안정적으로 깊은 레이어의 가중치도 학습시킬 수 있을 것이다. “은닉층의 입력을 표준화한다는 것은 곧이전 층의 출력(raw activation)을 표준화한다는 의미와 같다.

딥러닝은 거의 항상 전체 샘플을 mini batch로 나누어 학습하고 가중치를 업데이트하므로 이전 층의 raw activation을 표준화할때도 각 batch마다 따로 표준화하면 된다.

스케치

이와 같이 각각의 minibatch 평균 \mu_{\mathcal{B}} = \frac{1}{m} \sum_i {x_iw_i} 표준편차 \sigma_{\mathcal{B}} = \frac{1}{m} \sum_i {(x_iw_i - \mu_{\mathcal{B}})^2} 표준화한 activation a_s = f(\frac{XW_1 - \mu_{\mathcal{B}}}{\sigma_{\mathcal{B}}}) 은닉층 B 입력으로 사용하면 은닉층 B 입력은 고정된 분포를 따른다.

쉬워도 너무 쉽다. 이렇게만 하면 될 것 같지만..

[1 문제점]

문제가 가지 있다. 이렇게 은닉층의 입력을 표준화하면 gradient update 과정에서 bias(편향)값이 무시된다. [1]만을 사용해서 표준화한다고 그라디언트 업데이트 과정을 자세히 살펴보자. Raw activation a_r = wx + b라고 E(a_r) = \frac{1}{n} \sum_i a_{r_{i}}이므로

  1. 그라디언트를 계산한다.
    • \Delta b \propto - {\partial L}/{\partial b},  where L is a loss function.
  2. 편향(과 가중치)을 업데이트한다.
    • b \gets b + \Delta b
  3. 편향을 업데이트한 이후의 raw activation:
    • a_r ^\prime = wx + (b + \Delta b)
  4. [1] 이용해서 센터링만 raw activation:
    • \begin{array}{lcl} a_{r_{centered}} ^\prime &=& a_r ^\prime - E(a_r ^\prime) \\ &=& \{(wx + b) + \Delta b\} - \{ E[wx + b] + \Delta b \} \\ &=& (wx + b) - E[wx + b] \end{array}

Bias b 업데이트 \Delta b 완벽하게 캔슬되었다. 초기 편향값에서 이상 업데이트가 되지 않는 것이다. 종류의 파라미터 w, b 사용했는데 파라미터 w 가지만 사용하는 단순한 모형으로 irreversible하게 변환된 것이다.

이 때문에 b 대신 편향의 역할을 할 파라미터를 추가해야한다. 이 파라미터는 그라디언트 업데이트 과정에서 무시되어서는 안된다.

다른 문제도 있다. raw activation 분포를 고정시키는 것은 좋지만 항상 N(0, 1) 고정시킬 필요는 없다. 적절하게 scaling, shifting activation \gamma \cdot \frac{a_r - \mu_{\mathcal{B}}}{\sigma_{\mathcal{B}}} + \beta 사용하는 것이 학습에 도움될 수도 있다.

형태의 activation 사용할 경우 필요하다면 표준화를 되돌릴 수도 있다. \gamma = \sigma_{\mathcal{B}}, \beta = \mu_{\mathcal{B}} \gamma \cdot \frac{a_r - \mu_{\mathcal{B}}}{\sigma_{\mathcal{B}}} + \beta = a_r이기 때문이다.

[2]

위의 문제를 극복하기 위해 표준화한 scaling shifting raw activation, 즉

a_{BN} = \gamma \cdot \frac{XW_1 - \mu_{\mathcal{B}}}{\sigma_{\mathcal{B}}} + \beta

activation function f 입력으로 사용한다. 은닉층 B 입력으로는 f(a_{BN}) 사용한다. 방법을 BatchNorm이라고 한다. \gamma, \beta 파라미터로 학습 과정에서 업데이트되는 값이다.

BatchNorm 장점이 꽤나 많은데

  • bias 업데이트를 무시하지 않는다. \beta bias처럼 행동한다. \beta 업데이트는 표준화해도 캔슬되지 않는다.
  • 은닉층마다 적절한 input distribution 가질 있다. scaling factor \gamma shifting factor \beta 사용해서 적절한 모양으로 입력분포를 조정할 있다.
  • 필요한 경우 표준화를 하지 않을 수도 있다. 위에서 언급한 \gamma = \sigma_{\mathcal{B}}, \beta = \mu_{\mathcal{B}} 경우이다.
  • Activation 값을 적당한 크기로 유지하기 때문에 vanishing gradient 현상을 어느정도 막아준다. 덕분에 tanh, softmax같은 saturating nonlinearity 사용해도 문제가 생긴다.
  • batch-wise로 계산하기 때문에 컴퓨팅하기 용이하다.
  • 위의 장점들을 모두 가지면서, 동시에 층마다 입력 분포를 특정 형태로 안정시켜서 internal covariate shift 방지할 있다.
  • 입력 분포가 안정되므로 학습시 손실함수가 더 빨리, 더 좋은 값으로 수렴한다.
  • 초기 learning rate를 크게 설정해도 안정적으로 수렴한다고 한다.
  • Weak regularizer로도 작용한다고 한다.

이쯤 되면 거의 만능이다.

테스트

지금까지 다룬 내용은 모두 학습 과정에서 일어나는 일들이다. 학습 과정에서는 raw activation minibatch mean, stdev 표준화하면 됐었다. 그런데 학습을 마치고 테스트(또는 evaluation, inference) 때에는 minibatch mean, stdev 존재하지 않는다.

테스트 과정에서는 대신 전체 training data mean, stdev 사용해서 BatchNorm 한다. 전체 training data mean, stdev 번에 계산하기에는 메모리의 제약이 있으므로, minibatch statistic 평균낸 값을 대신 사용한다.

, n개의 minibatch 있을 ,

\hat{\mu} = \frac{1}{n} \sum_i {\mu_{\mathcal{B}}^{(i)}}
\hat{\sigma} = \frac{1}{n} \sum_i {\sigma_{\mathcal{B}}^{(i)}}

Minibatch statistic 따로 저장할 필요 없이 학습 과정에서 moving average \hat{\mu}, \hat{\sigma} 계산하면 된다. Exponential moving average 사용해도 좋다.

i번째 minibatch statistic 각각 \mu_{\mathcal{B}}^{(i)}, \sigma_{\mathcal{B}}^{(i)}라고 ,

\hat{\mu} \gets \alpha \hat{\mu} + (1-\alpha) \mu_{\mathcal{B}}^{(i)}
\hat{\sigma} \gets \alpha \hat{\sigma} + (1-\alpha) \sigma_{\mathcal{B}}^{(i)}

BatchNorm layer

ReLU activation 뉴럴넷의 레이어로 나타낼 있듯 BatchNorm 또한 레이어로 표현할 있다. BN layer raw activation activation function 사이에 위치한다. Convolutional layer에 BatchNorm을 적용하고 싶을 때에도 동일하게 raw feature map과 ReLU layer 사이에 BN layer를 추가하면 된다.

e18489e185b3e1848fe185a6e1848ee185b57.png

BN layer mini batch raw activations a_r 입력받아 아래와 같은 연산을 수행하여 다음 레이어(activation function f) 전달한다.

BN_{\gamma, \beta}(a_r) = \gamma \cdot \frac{a_r - \mu_{\mathcal{B}}}{\sigma_{\mathcal{B}}} + \beta

또한 테스트 사용하기 위해 학습 과정에서 minibatch statistic exponential moving average(또는 그냥 MA) minibatch마다 업데이트한다.

 

TensorFlow 구현

구글에서 고안한 방법답게 TensorFlow에 이 내용들이 친절히 함수로 구현되어 있다. tf.nn.batch_normalization, tf.contrib.slim.batch_norm를 쓰면 간단히 위 알고리즘을 모형 구축에 사용할 수 있다.

tf.nn.batch_normalization을 사용할 경우, minibatch statistic의 EMA를 계산하는 코드를 따로 작성해야 한다.

tf.contrib.slim.batch_norm를 사용할 경우 is_training 옵션을 True로 주면 자동으로 EMA를 계산해서 저장하고, False로 주면 저장된 EMA 값으로 activation을 표준화한다.

TF-Slim 레이어에도 쉽게 적용시킬 수 있다.

import tensorflow as tf
import tensorflow.contrib.slim as slim

bn_params = {"decay": .9,
             "updates_collections": None,
             "is_training": tf.placeholder(tf.bool)}
net = slim.fully_connected(input, 1024,
                           normalizer_fn=slim.batch_norm,
                           normalizer_params=bn_params)

Convolutional layer에도 마찬가지다.

net = slim.conv2d(input, 64, [5,5], padding="SAME",
                  normalizer_fn=slim.batch_norm,
                  normalizer_params=bn_params)

 

 

참고