이 글에서는 ImageNet Challenge에서 2012~2015년까지 좋은 성능을 낸 대표적인 모델인 AlexNet, ZFNet, VGG, GoogLeNet(InceptionNet), ResNet을 살펴본다.

ImageNet에서 사람의 오류율(이미지 class를 잘못 분류한 비율)은 5.1%로 나와 있음을 참고한다.
각각에 대해 간단히 설명하면,

• AlexNet: ImageNet Challenge에서 사실상 최초로 만든 Deep Neural Network 모델이다(이전에는 Shallow model이 대세였다). 2012년, 8 layers, 오류율 16.4%.
• ZFNet: AlexNet을 최적화한 모델이다. 2013년, 8 layers, 오류율 11.7%.
• VGGNet: Filter의 size를 크게 줄이고 대신 더 깊게 layer를 쌓아 만든 모델이다. 2014년, 19 layers, 오류율 7.3%.
• GoogLeNet: InceptionNet 으로도 부른다. 이름답게 Google에서 만들었으며 한 layer에서 여러 크기의 Conv filter를 사용하여 성능을 높였다. 2014년, 19 layers, 오류율 6.7%.
• ResNet: Residual Network를 개발한 논문으로 identity mapping을 추가하는 기술을 통해 깊이가 매우 깊어진 모델의 학습을 가능하게 하였다. 2015년, 152 layers, 오류율 3.6%. 이때부터 사람의 정확도를 능가하였다고 평가받는다.
• Inception v2,3, v4: GoogleNet(Inception)을 개량한 버전으로 ResNet보다 더 높은 성능을 보여준다. 2016년.

AlexNet

논문 링크: AlexNet

2012 NIPS에서 발표된 ImageNet Challenge에서의 (사실상) 최초의 Deep Neural Network이다.

8개의 layers를 쌓은 지금으로서는 상당히 간단한 모델이지만 당시에는 꽤 복잡한 모델이었다.

8개의 layers라는 말은 학습가능한 parameter가 있는 layer의 개수를 의미하며 learnable parameters가 없는 pooling layer 등은 제외한다.

입력 이미지 크기는 [224, 224, 3]이며 이 이미지는

• conv - pooling - layer norm을 총 2번 거친 다음
• conv layer를 3번 연속 통과하고
• pooling layer를 1번 통과한 뒤
• fully connected layer를 3번 통과하여 최종적으로 1000개의 class일 확률을 예측하는 [1000, 1] 벡터를 출력한다.

첫 2개의 conv layer에서는 각각 크기가 11, 5인 filter를 사용하는데, 이는 지금 기준으로 매우 큰 크기이다. 이는 이후 모델이 발전하면서 작아지는 쪽으로 바뀌게 된다.

전체 구조를 정리하면 다음과 같다.

살펴볼만한 특징은,

• 이 논문은 최초의 CNN 기반 모델로 ReLU를 처음 사용하였다.
• Normalization Layer를 사용하였는데, 참고로 최근에는 거의 쓰이지 않는다.
• Data Augmentation을 상당히 많이 사용하였다.
• Dropout 0.5, Batch size 128, SGD(Momemtum 0.9)
• Learning rate는 0.01 이후 성능이 정체되면 1/10으로 줄인다.
• L2 weight decay(5e-4)를 hyperparameter로 사용하였다.

ZFNet

논문 링크: ZFNet

AlexNet을 최적화하여 다음 연도(2013년)에 발표된 논문으로, 모델의 구조는 딱히 다를 것이 없으나 filter size 등 여러 hyperparameter를 최적화하여 성능을 상당히 높인 모델이다.

VGGNet

논문 링크: VGGNet

AlexNet의 필터 크기는 11, 5로 상당히 크다. 이는 parameter의 수와 계산량을 크게 증가시키는데, 2014년 발표된 VGGNet에서는 filter 크기를 3인 것만 사용하고, 대신 모델의 깊이를 더 깊게 쌓아서 더 좋은 성능을 얻는 데 성공한다.

예로 [5 x 5] filter 1개를 사용하는 경우와 2개의 [3 x 3] filter를 사용하는 경우를 비교하면, 둘 다 [5 x 5] 범위를 살펴볼 수 있다. 그러나,

• 1개의 [5 x 5] filter는 총 $1 \times (5 \times 5) \times C^2 = 25C^2$개의 parameter를 사용한다.
• 2개의 [3 x 3] filter는 총 $2 \times (3 \times 3) \times C^2 = 18C^2$개의 parameter를 사용한다.

즉 갈은 범위를 처리할 수 있으면서도 필요한 parameter 수는 크게 줄어든다. [11 x 11]의 경우는 차이가 훨씬 크게 나게 된다.

VGGNet의 경우 버전이 여러 개 있는데, 보통 각각 16, 19개의 layer를 사용한 VGG16과 VGG19가 현재까지도 곧잘 사용된다. filter size와 layer의 수를 제외하면 큰 구조는 AlexNet과 꽤 비슷하다.

오류율이 7.3%로 줄어들어 사람의 성능(?)과 매우 근접한 수준까지 온 모델이다. VGGNet의 상세한 사항은 AlexNet과 비슷하지만, AlexNet에서는 사용한 local-response Normalization(LRN) layer를 사용하지 않았다. Batch size는 256으로 증가되었다.

GoogLeNet

논문 링크: GoogLeNet

역시 2014년 발표된 논문이다. 모델이 점점 더 깊어진다는 뜻에서 inception module이라는 것을 사용한다(영화 인셉션을 생각하라..).
각 conv layer에서, filter size를 1,3,5로 다양하게 사용하여 여러 receptive field size를 취하고 channel별로 concat하여 사용한다. 이를 통해 좀 더 다양한 정보를 학습할 수 있다.

왼쪽이 Inception Module의 구상이고, 오른쪽은 계산량을 줄이기 위해 [1 x 1] conv를 앞에다 붙여서 사용한 것을 나타낸다. 각 layer마다 사용하는 filter가 3개씩(+pooling) 있기 때문에 계산량이 매우 많아지는데, 계산량이 많을 수밖에 없는 [3 x 3]과 [5 x 5] 필터를 사용하기 전 [1 x 1] filter를 적용하여 채널 수를 줄인 다음 계산하면 계산량이 3~4배 줄어들게 된다.

전체 구조는 다음과 같다. 각 layer마다 inception module이 들어가기 때문에 매우 복잡해 보이지만, 총 깊이는 22 layer이다.

크게 4부분을 떼어 놓고 볼 수 있다.

1. 맨 앞부분(빨간색 박스)은 input image를 받는 부분인데, Stem Network라 부른다. 이전 모델인 AlexNet과 VGGNet과 비슷하게, Conv-Pool-Norm-Conv-Conv-Norm-Pool Layer로 구성되어 있다.
2. 중간 부분(노란색 박스)은 inception module를 쌓아 만든 부분이다.
3. 마지막 부분(파란색 박스)은 앞에서 얻은 feature를 가지고 class를 분류하는 부분으로 Classifier output을 최종적으로 내보낸다.
4. 아래쪽에 달려 있는 초록색 박스로 표시한 두 부분이 있는데, 이는 Auxilizary Classification loss를 사용하는 부분이다. GoogLeNet이 꽤 깊기 때문에 loss가 앞 layer까지 backprop이 잘 일어나지 않는다. 따라서 중간에 auxiliary classification loss를 추가하여 앞 부분에도 잘 전파될 수 있도록 하는 부분이다.

기타 살펴볼 특징은 다음과 같다.

• 22층의 layer를 사용하였다.
• AlexNet보다 12배, VGG16보다 27배 더 적은 parameter를 사용하면서도 성능이 더 좋다.
• Learning rate는 매 8 epoch 마다 4%씩 감소시킨다.

ResNet

논문 링크: ResNet

Microsoft에서 개발한 모델로 2015년 발표되었고, 최초로 사람의 분류 성능을 뛰어넘은 모델로 평가된다.

매우 깊은 모델(152층)이며, 이 이후부터는 매우 깊고 큰 모델을 사용하게 된다.

ResNet의 출발점은 다음과 같다. 어떤 shallow 모델이 있고, 여기에 더해 Layer를 몇층 더 쌓은 deep 모델이 있다. 그러면 deep model은, shallow 모델을 포함하니까 적어도 shallow 모델만큼은 성능이 나와 주어야 하는데(추가한 layer는 identity mapping을 한다고 하면 명백하다), 실제로 실험을 해보면 그렇지 않은 결과가 나온다. 이는 깊은 모델일수록 학습이 잘 이루어지지 않기 때문이다.

어쨌든 deep 모델이 shallow 모델만큼의 성능을 확보하려면, 강제적으로 이미 학습한 부분을 identity mapping으로 다음 layer에 전달하면 최소한 shallow 모델만큼은 성능이 확보될 것이다. 이 내용이 ResNet의 motivation이다.

그래서 그냥 identity mapping(혹은 Shortcut Connection이라고도 함)을 layer의 끝에다 그냥 더해버린다.

이러한 residual block을 152개까지 쌓는다. GoogLeNet과 비슷하게 Stem network가 처음에 있으며, 추가 FC layer는 사용하지 않는다.

각 block 내에는 각각 크기 1, 3, 1인 conv filter를 사용한다. ResNet도 여러 버전이 있는데(18, 34, 50, 101, 152 layers) 50 이후로는 사용하는 메모리에 비해 성능이 그닥 크게 증가하지는 않는다.

버전별 ResNet 구조는 다음과 같다.

• Xavier Initialization을 사용하였다.
• 모든 conv layer 이후 batch norm이 사용되었다.
• Dropout은 사용하지 않는다.

InceptionNet v2,3, v4

논문 링크: Inception v2, 3, Inception v4

기존의 InceptionNet(GoogLeNet)을 발전시킨 모델이다.

v2, 3에서는 Conv Filter Factorization과 Grid Size Reduction을 통해 기존 모델을 발전시켰다.

Conv Filter Factorization은 [n x n] filter를 [1 x n], [n x 1] 2개로 나누어 계산하는 방법으로 $n \times n$ 범위를 처리할 수 있으면서 계산량을 줄일 수 있는 방법이다.

Grid size Reduction은 Pooling-Inception 순서로 할 경우 계산은 빠르지만 spatial 정보 손실이 일어나는 점, Inception-Pooling 순서의 경우 정보는 보존되지만 계산량이 많다는 점을 착안해, 이 두가지 방식을 적절히 섞어서(즉, 크기를 줄인 채 두 방법 모두를 사용하여) 2가지 장점을 모두 가지려 한 방법이라 생각하면 된다.

Inception v4는 ResNet 이후에 나온 모델이다. 그래서 Inception v3에다가 Residual 기법을 사용한 모델로, ResNet152보다 Inception v4의 성능이 더 좋다.

이후 모델은 ResNeXt, DenseNet, MobileNets 등이 있다.

이번 글에서는 HGT란 알고리즘에 대해 다뤄보겠다. 상세한 내용은 논문 원본을 참고하길 바라며, 본 글에서는 핵심적인 부분에 대해 요약 정리하도록 할 것이다. 저자의 코드는 Github에서 확인할 수 있다.

Heterogeneous Graph Transformer 설명

1. Background

기존의 많은 GNN이 Homogenous Graph에만 집중된 것에 반해, HGT는 여러 node type, edge type을 가진 Heterogenous Graph 데이터에 대해 적합한 알고리즘으로 제안되었다.

Heterogenous Graph에 대한 접근법은 여러 가지가 있지만 대표적으로 meta-path를 이용한 방법과 GNN을 이용한 방법이 존재한다. 그런데 이러한 방법에는 몇 가지 결점이 존재한다.

• heterogenous graph의 각 type에 맞는 meta-path design을 하려면 구체적인 domain 지식이 필요하다.
• 다른 type의 node/edge가 같은 feature를 공유하거나, 혹은 아예 다른 feature를 갖는 경우 graph의 특징을 온전히 포착하기는 어렵다.
• 모든 graph의 동적 특성은 대부분 무시되고 있다.

HGT의 목표는 다음과 같다.

• Network dynamics는 포착하면서 각 node/edge-type에 적합한 representation 학습
• customized meta-path를 특별히 설계하지 않음
• Web-scale graph에 적합하도록 highly scalable할 것

2. Heterogenous Graph Mining

Heterogenous Graph의 정의에 대해 살펴보자.

[G = (\mathcal{V}, \mathcal{E}, \mathcal{A}, \mathcal{R})]

각 집합은 node, edge, node type, edge type을 의미한다. 이 때 각 node $v \in \mathcal{V}$ 이고, 각 edge $e \in \mathcal{E}$ 이다. 그리고 다음과 같은 type mapping 함수가 존재한다.

[\tau(v): V \rightarrow \mathcal{A}, \phi(e): E \rightarrow \mathcal{R}]

본격적인 구조 설명에 앞서 몇 가지 개념들에 대해 짚고 넘어간다.

Meta Relation
edge $e = (s, t)$ 가 존재할 때, 각 node $s, t$ 는 물론 edge $e$ 도 각자의 type을 가질 것이다. 이 때 이들 관계의 meta relation은 아래와 같이 표현할 수 있다.

[<\tau(s), \phi(e), \tau(t)>]

이는 기존의 여러 meta-path 방법론에서도 설명된 개념이다. 3개의 요소 모두가 같아야만 같은 관계로 인식된다. 그런데 HGT는 여기에서 시간의 개념을 추가한다.

Dynamic Heterogenous Graph
앞서 예시로 들었던 edge $e=(s, t)$ 에 timestamp $T$ 를 할당해보자. 이는 node $s$ 가 $T$ 시점에 node $t$ 와 연결되었음을 의미한다. 이러한 관계가 처음으로 나타났다면 $s$ 에게 $T$ 시점이 할당된다. 물론 node $s$ 가 여러 번 연결된다면 복수의 timestamp를 갖게 될 것이다.

이는 edge의 timestamp는 불변함을 의미한다. 당연하다. 예를 들어 어떤 논문이 WWW에 1994년에 등재되었다면, 이 때의 timestamp는 1994년인 것이다.

3. Heterogenous Graph Transformer

HGT의 목표는 source node로 부터 정보를 통합하여 target node $t$ 에 대한 contextualized representation을 얻는 것이다.

3.1. Heterogenous Message Passing & Aggregation

아래 그림은 전체적인 구조를 나타낸다. 총 $L$ 개의 Layer를 쌓는 방식으로 되어 있고, $H^l$ 은 $l$ 번째 HGT layer의 output이다.

(1), (2), (3)으로 구분되어 있듯이 이 과정은 크게 3가지로 구분되며, 효과적인 학습을 위해 3가지의 추가적인 장치가 배치된다. 추가적인 장치는 3.2에서 설명하도록 하겠다.

Step1: Heterogenous Mutual Attention
Step2: Heterogenous Message Passingg
Step3: Target-specific Aggregation

일단 주어진 상황은 다음과 같다. 특정 target node $t$ 가 존재할 때, 2개의 source node $s_1, s_2$ 가 $e_1, e_2$ 라는 edge를 통해 target node와 관계를 맺고 있는 것이다. 이 때 node인 $t, s_1, s_2$ 의 경우 node feature 벡터를 갖는다. (node feature가 없으면 인위적으로 생성해야 한다.) 각 feature 벡터의 길이는 일단 $d$ 로 같다고 가정한다. 실제로는 최초의 Projection Layer에서 같은 길이로 통일되기 때문에 node type별로 다른 feature 길이를 가져도 무방하다. 어쨌든 지금은 $d$ 라는 길이로 통일되어 있다고 생각하자. 그렇다면 지금까지의 이야기로 2개의 meta relation이 존재하는 것이다.

[<\tau(s_1), \phi(e_1), \tau(t)>, <\tau(s_2), \phi(e_2), \tau(t)>]

1번째 meta relation을 기준으로 이야기를 이어나가 보겠다. Step1, 2에서 해야할 일은 source node $s_1$ 이 $e_1$ 이라는 edge를 통해 target node $t$ 에 주는 영향력을 수식으로 나타내는 것이다. 이는 Multi-head Attention으로 구현되는데, 기존의 Vanilla Transformer를 사용하면 다른 source/target node, 여러 node type 모두 같은 feature distribution을 공유하게 되므로 이는 현재 상황에 적합한 세팅은 아니다.

Step1: Heterogenous Mutual Attention

이러한 단점을 보완하기 위해 Heterogenous Mutual Attention 메커니즘이 도입된다. 이 메커니즘은 Multi-head Attention의 핵심 구조는 그대로 따르지만 몇 가지 차이점이 있다. 먼저 target node 벡터와 source node 벡터는 각각 Query 벡터, Key 벡터로 매핑되는데 이 때 각각의 node type에 따라 projection weight parameter가 다르다. 즉 만약 node type이 10개 있다고 하면, Query 벡터를 만들기 위한 weight matrix는 기본적으로 10 종류가 있는 것이다. (후에 여기에 attention head 수를 곱해야 한다.)

여기가 끝이 아니다. edge type도 weight parameter를 구분한다. $W_{\phi(e)}^{ATT}$ 가 edge type에 dependent한 weight으로 Query 벡터와 Key 벡터의 유사도를 반영한다. 지금까지 설명한 것을 식으로 보자.

[Attention(s, e, t) = Softmax_{\forall s \in N(t)} ( \Vert_{i \in [1, h]} ATT {\text -} head^i(s, e, t) )]

[ATT {\text -} head^i(s, e, t) = (K^i(s) W_{\phi(e)}^{ATT} Q^i(t)^T)) \cdot \frac{\mu <\tau(s), \phi(e), \tau(t)>}{\sqrt{d}}]

2번째 식을 $h$ 개 만들고 이를 concat한 뒤 target별로 softmax 함수를 적용한 것이 최종 결과이다. 즉 2번째 식은 head 1개에 대한 결과물을 의미한다.

식의 좌측이 앞서 설명한 부분으로 아래와 같이 좀 더 세부적으로 표현할 수 있다.

[K^i(s) = K {\text -} Linear^i_{\tau(s)} (H^{l-1}[s])]

[Q^i(t) = Q {\text -} Linear^i_{\tau(t)} (H^{l-1}[t])]

위는 node type에 따라 weight를 구분하는 projection layer다. 이전 layer의 결과물을 받아 linear layer 하나를 통과시켜 Query/Key 벡터를 얻는다. 최종적으로 $h$ 개의 attention head를 얻기 때문에 Query/Key 벡터는 $\mathcal{R}^d \rightarrow \mathcal{R}^{\frac{d}{h}}$ 로 바뀐다. $W_{\phi(e)}^{ATT}$ 는 $\mathcal{R}^{\frac{d}{h}, \frac{d}{h}}$ 의 형상을 갖는다.

지금까지의 과정을 종합해보면, 이 Heterogenous Mutual Attention 메커니즘이 여러 종류의 semantic relation을 충분히 포착할 수 있을 구조를 갖고 있다는 느낌이 들기 시작한다. 그 효용성에 대해서는 검증해보아야겠지만 일단 장치는 마련해둔 셈이다.

2번째 식에서 우측을 보면 아래와 같은 수식이 있다.

[\frac{\mu <\tau(s), \phi(e), \tau(t)>}{\sqrt{d}}]

논문에서는 이 식을 prior tensor라고 지칭하고 있다. 생각해보면, 모든 node/edge type이 같은 영향력을 지니지는 않을 것이다. 즉 데이터 전반을 볼 때 특정 node/edge type이 더 강한 영향력을 지닐 수도 있는 것이다. 이를 반영하기 위해 만들어진 tensor라고 생각하면 된다. 이 tensor를 통해 attention에 대해 adaptive scaling을 수행한다.

코드를 잠시 보고 지나가겠다.

self.relation_pri = nn.Parameter(torch.ones(num_relations, self.n_heads))

논문 원본에는 모든 node/edge type에 따른 prior를 부여하였는데, 저자의 코드는 이를 좀 단순화하여 나타냈다. 만약 원본 코드를 사용할 계획이라면 상황에 따라 수정을 가할 수도 있을 것이다. 만약 수정을 원한다면 아래 부분에서 행렬 곱 연산을 수행한 후에 합 연산을 수행하는 형태로 바꿔줘야 한다.

res_att[idx] = (q_mat * k_mat).sum(dim=-1) * self.relation_pri[relation_type] / self.sqrt_dk

코드에 대한 자세한 리뷰는 추후에 업로드하도록 하겠다.

앞서 언급하였듯이 최종 단계에서의 softmax는 target node를 기준으로 이루어지기 때문에 현재와 같이 1번째 meta relation 만을 기준으로 연산을 수행한다면 각각의 head에 대해 softmax가 아닌 sigmoid 함수가 적용되게 될 것이다. 2번째 meta relation까지 한번에 계산했다면 2개의 target node에 대해 softmax 함수가 적용되어 결과물로 길이 $h$ 의 벡터가 2개 주어질 것이다.

이를 그림으로 나타내면 아래와 같다.

Step2: Heterogenous Message Passing

이전 섹션에서 주어진 edge type 하에서 source node와 target node 사이의 유사성에 대해 계산하였다면, 본 섹션에서는 이제 source node로부터 수집한 정보를 target node로 전달할 차례이다. 이 때 일반적인 honogenous graph network에서는 이러한 정보가 동일한 파라미터를 통해 업데이트되었겠지만, Heterogenous Message Passing 메커니즘에서는 source node type과 edge type에 따라 다른 파라미터를 지정하여 진행하게 된다.

[Message(s, e, t) = \Vert_{i \in [1, h]} MSG {\text -} head^i(s, e, t)]

[MSG {\text -} head^i(s, e, t) = M {\text -} Linear^i_{\tau(s)} (H^{l-1}[s]) W_{\phi(e)}^{MSG}]

Mutual Attention 과정을 보았기 때문에 특별히 어려울 것은 없다. 다만 위 수식에서의 M은 Transformer의 V 부분을 의미하고 실제 저자의 코드에서는 V-Linear라고 표기되어 있음에 유의하자.

Step3: Target-specific Aggregation

이전 2개 과정을 통해 attention score와 message를 수집/계산하였다. 지금부터는 이를 target node에 맞춰 통합하는 과정으로 이어진다.

[<\tau(s_1), \phi(e_1), \tau(t)>, <\tau(s_2), \phi(e_2), \tau(t)>]

위 meta relation 들에 대하여 attention score와 message를 모두 얻었다면 이 둘을 곱하여 updated vector를 얻을 차례이다.

[\tilde{H}^l [t] = \oplus_{\forall s \in N(t)} ( {\text Attention}(s, e, t) \cdot {\text Message} (s, e, t) )]

이 과정을 거치면 다른 feature distribution을 갖는 source node의 이웃들이 target node $t$ 로 정보를 통합하게 될 것이다. 이제 target node $t$ 의 updated vector를 맞는 type에 따라 다시 한 번 linear layer를 통과시킨다. 그리고 이전 layer의 output을 직접적으로 더해주어 residual connection 또한 추가해준다.

[H^l[t] = A {\text -}Linear_{\tau(t)} ( \sigma (\tilde{H}^l [t]) + H^{l-1}[t] )]

이와 같은 과정을 $L$ 번 반복해주면 바로 그 결과물이 target node의 contextualized representaion이 되는 것이고, 이를 통해 node classification이나 link prediction과 같은 downstream task에 활용하면 된다.

정리를 좀 해보면, HGT는 분명 meta relation을 활용하여 각 type에 맞는 weight matrix를 따로 설정하고 이를 자연스럽게 통합하고 있다. 다만 이렇게 별개의 weight matrix를 모두 만들 경우 분명 model이 무거워지는 것은 사실이다. 따라서 실제 적용 시에는 이러한 부분에 대해 유의해야 할 것이다.

3.2. Additional setting

앞서 효과적인 학습을 위해 3가지의 추가적인 장치가 구현되어 있다고 언급한 바 있다. 이제 이 부분에 대해 살펴볼 것이다.

1번째 장치: Relative Temporal Encoding

RTE는 graph dynamic을 다루기 위해 도입된 개념이다. 시간적 정보를 활용하기 위해 시간대 별로 분리된 graph를 구성하는 이전의 방법은 여러 time slot간의 구조적인 연결성을 잃어버리기 때문에 효과적인 방법으로 보기 어렵다. dynamic graph를 모델링하는 것의 핵심은 바로 모든 node/edge가 다른 timestamp에서도 서로 상호작용할 수 있게 만들어주는 것이다.

이러한 철학은 Transformer의 positional encoding을 변형하여 구현된다.

source node $s$ 의 timestamp는 $T(s)$ 이고 target node $t$ 의 timestamp는 $T(t)$ 이다. 이 둘 사이의 relative time gap은 $\Delta T(t, s) = T(t) - T(s)$ 로 표현할 수 있고, relative temporal encoding을 $RTE(\Delta T(t, s))$ 라고 표기한다.

학습 데이터셋이 모든 time gap을 커버하는 것은 아니기 때문에 RTE는 본 적 없는 시간에 대해서도 일반화할 수 있어야 한다. 이를 위해 논문에서는 sinusoid 함수를 basis로 놓고 학습 가능한 projection layer를 하나 더 둔다.

[Base(\Delta T(t, s), 2i) = sin (\Delta T(t, s) / 10000^{\frac{2i}{d}})]

[Base(\Delta T(t, s), 2i+1) = cos (\Delta T(t, s) / 10000^{\frac{2i+1}{d}})]

[RTE(\Delta T(t, s)) = T{\text -}Linear (Base(\Delta T(t, s)))]

최종적으로 target node $t$ 에 대한 temporal encoding은 source node $s$ 의 representation에 더해진다.

[\hat{H}^{l-1} [s] = H^{l-1}[s] + RTE(\Delta T(t, s))]

이 과정을 그림으로 나타내면 아래와 같다.

코드로 구현하면 아래와 같다.

class RelTemporalEncoding(nn.Module):
    # Implement the Temporal Encoding (Sinusoid) function.
    def __init__(self, n_hid, max_len=240):
        super(RelTemporalEncoding, self).__init__()
        position = torch.arange(0., max_len).unsqueeze(1)
        div_term = torch.exp(torch.arange(0, n_hid, 2) * -(math.log(10000.0) / n_hid))

        emb = nn.Embedding(max_len, n_hid)
        emb.weight.data[:, 0::2] = torch.sin(position * div_term) / math.sqrt(n_hid)
        emb.weight.data[:, 1::2] = torch.cos(position * div_term) / math.sqrt(n_hid)
        emb.requires_grad = False

        self.emb = emb
        self.lin = nn.Linear(n_hid, n_hid)
    def forward(self, x, t):
        return x + self.lin(self.emb(t))

edge_time이 주어지고, meta relation이 주어졌을 때 temporal encoding이 source node $s$ 의 representation에 더해지는 과정은 아래와 같이 구현된다.

rte = RelTemporalEncoding(n_hid=10)

source_node_vec = rte(source_node_vec, edge_time[idx])

2번째 장치: HGSampling

지금부터 설명할 2개의 방법론은 모두 scalibility를 향상시키기 위해 도입된 장치들이다.

작은 graph가 아니라면 full-batch GNN 학습은 현실적으로 힘든 경우가 많다. 그리고 속도와 효율을 중시하는 실제 서비스에 적용하기에는 부담스러운 측면도 있다. 이를 위해 sampling 방법이 많이 도입 되었는데, 이를 node-level로 추출할 수도 있고, grpah-level로 추출할 수도 있다. 이와 관련된 연구는 매우 많지만 node-level sampling을 적용한 알고리즘으로는 GraphSAGE, PinSAGE가 있고, IGMC, GraphSAINT는 graph-level sampling을 적용하였다.

그런데 앞서 소개한 방법들을 그대로 heterogenous graph에 적용할 경우, 만약 node type별 분포가 크게 다를 경우 상당히 불균형적이고 왜곡된 subgraph가 추출될 수 있다. 따라서 이를 위해 HGSampling이라는 방법이 제안된다.

HGSampling은 각 node/edge type에 속하는 수를 유사하게 맞춰주면서 정보 손실을 최소화하고 sample variance를 줄이기 위해 추출된 subgraph를 dense하게 유지할 수 있는 알고리즘이다.

아래 도식에서 HGSampling의 수행 과정을 살펴볼 수 있다. 기본적으로 각 node type $\tau{r}$ 에 대해 budget 딕셔너리 $B[\tau{r}]$ 를 만들어준다. 그리고 중요도 기반의 sampling을 사용하여 node type 별로 같은 수의 node를 추출해준다.

node $t$ 가 이미 추출되었다고 할 때, 이 node의 직접적인 이웃들을 모두 상응하는 budget에 추가해준다. 추가하는 방식은 아래와 같다.

그리고 이 이웃들에게는 node $t$ 의 normalized degree를 더해준다. 이 값은 추후에 sampling 확률을 계산하기 위해 사용된다. 이러한 normalization은 high-degree node에 의해 크게 좌지우지 되는 sampling 방식을 피하면서도, 이웃들에 대한 각 sampled node의 random walk 확률을 모으는 것과 같은 효과를 지닌다.

budget이 업데이트된 이후, 알고리즘1의 line9에서 각 budget 속에 있는 각 node $s$ 의 cumulative normalized degree를 계산한다. 이러한 sampling probability는 sampling variance를 감소시키는 효과를 지닌다.

이후 계산된 확률에 기반하여 type $\tau$ 의 $n$ 개의 node를 추출하고 이를 output node set에 추가하고, 이웃목록을 budget에 업데이트한다. 추출된 node는 budget에서 제거된다.

최종적으로 우리는 이렇게 sampled된 node에 기반하여 adjacency matrix를 다시 생성한다.

위와 같은 과정으로 생성한 subgraph는 node type별로 유사한 수의 node를 갖게 되고, sampling variance를 감소시킬 수 있을만큼 충분히 dense하다. 따라서 이를 활용하여 web-scale heterogenous graph를 효과적으로 학습할 수 있다.

그림으로 표현하면 아래와 같다.

3번째 장치: Inductive Timestamp Assignmant

지금까지 우리는 각 node $t$가 timestamp $T(t)$ 에 assign되었다고 가정했는데 실 세계의 heterogenous graph에서 많은 node들은 고정된 시간으로 묶여있지 않다. 따라서 그러한 node에게는 다른 timestamp 들을 할당해주어야 하는데, 이러한 node를 plain nodes라고 한다.

또한 명시적인 timestamp를 갖고 있는 node들이 있는데 이들을 event nodes라고 한다. 본 논문에서는 event node의 timestamp에 기반하여 plain node의 timestamp를 assign하는 inductive timestamp assignment 알고리즘을 제안한다. plain node는 event node로 부터 timestamp를 상속받게 된다.

4. Evaluation and Conclusion

이번 포스팅에서는 SQL 기본 구문에 대해 정리해본다. 평소에 자주 사용하지만 정확히 숙지하지 못한 부분들을 정리하는 데에 목적이 있으며 아주 기초적인 부분은 생략한다.

SQL 기본

1. Basic

SELECT문의 기본적인 쓰임은 아래와 같다. 순서를 지켜야 한다.

/* 블록 주석 */
--한줄주석
SELECT select_expr
FROM table_reference
WHERE where_condition
GROUP BY column_name/expression/position
HAVING where_condition
ORDER BY column_name/expression/position

WHERE 절 뒤에는 조건/관계 연산자가 오게 된다. 조건 연산자에는 =, <, >, <=, >=, != 가 있고, 관계 연산자에는 or, and, not, between A and B, in, not in 가 있다.

ORDER BY는 정렬을 위해 사용되며, 큰 테이블에 직접적으로 사용하는 것은 많은 부하를 유발하게 된다.

--ORDER BY height ASC
--ORDER BY height DESC
SELECT name
FROM table
ORDER BY height asc, weight desc

위와 같이 2개 이상의 칼럼으로 정렬할 때는 왼쪽부터 우선순위를 갖는다.

LIMIT 5 OFFSET 3

위 구문은 3번째 row부터 5개를 반환한다는 뜻을 갖는다.

GROUP BY는 기준을 세워 집계하는 용도로 사용한다. 집계 함수에는 count, sum, avg, min, max 등이 있다. 예시는 아래와 같다.

SELECT user_id, sum(amount*price)
FROM table
GROUP BY user_id
HAVING sum(amount * price) > 1500;

GROUP BY에서 where 조건 절을 추가하고 싶다면 위와 같이 HAVING을 이용하면 된다.

NULL을 처리하는 방법을 정리한다. IS NULL은 null 여부를 조건식으로 나타낸다.

--IS (NOT) NULL
SELECT * FROM table WHERE name IS NULL
-- SELECT * FROM table WHERE name IS NOT NULL

IF NULL의 경우 특정 칼럼이 null값이 아니면 그 값 그대로, null이면 2번째 인자 값으로 채워주는 기능을 갖는다.

--IFNULL (혹은 NVL, ISNULL)
SELECT animal_type, IFNULL(NAME, ‘no name’) as name
FROM table
--→ null이면 ‘no_name’ 아니면 NAME 그대로

COALESCE는 정의된 열 중 null이 아닌 1번째 값을 출력한다.

SELECT animal_type, COALESCE(NAME, TAG, ‘nothing’) as KEY
FROM table
--→ NAME에 값이 있으면 NAME의 값을, NAME에 값이 없지만 TAG에 값이 있으면 TAG의 값을 출력함

IF는 말 그대로 조건식을 나타내는데, True일 경우 2번째 인자 값을 False일 경우 3번째 인자 값을 반환한다.

SELECT name, IF(price > 100, ‘expensive’, ‘normal’) as judgement
FROM table

LIKE의 몇 가지 사용법은 아래와 같다.

WHERE user_id like ‘a%’

• ‘a%’: a로 시작하는 모든 것
• ‘_a%’: 2번재 자리에 a가 들어가는 모든 것
• ‘a_%_%’: a로 시작하고, 길이가 최소 3이상인 것

서브쿼리는 쿼리 속의 쿼리이다. 서브쿼리의 결과물은 여러 값일 경우 이를 조건으로 사용하기 힘들 때가 있다. 이 때 ANY, ALL, SOME을 이용할 수 있다.

• ANY(SOME): 서브쿼리의 결과 중 하나라도 해당되면 OK (or의 역할)
• ALL: 서브쿼리의 결과 모두에 해당해야 함 (and의 역할)

2. Case

조건을 쓰고 이를 만족했을 때와 만족하지 않았을 때의 반환 값을 지정하여 하나의 칼럼으로 생성하는 구문이다. ELSE를 생략하면 Null 값이 반환될 수 있다.

SELECT user_id,
    CASE
        WHEN (age BETWEEN 0 and 40) THEN 'YOUNG'
        WHEN (age BETWEEN 41 and 70) THEN
            CASE
                WHEN (mind = 'good') THEN 'not young but good mind'
                ELSE 'not young and bad mind'
            END
        ELSE '?'
    END AS condition
FROM table

위 예시와 같이 기본적으로 CASE ~ END라는 큰 틀 안에 조건식을 채워넣는 개념이며, 조건식은 WHEN ~ THEN ~ + ELSE로 짜여지게 된다.

3. With

WITH는 특정 질의 결과에 이름을 부여하여 재사용을 가능하게 함과 동시에 가독성을 높여준다. 또한 WITH 구문을 사용할 경우 반복적으로 실행 계획을 수립하는 것이 아니기 대문에 쿼리의 성능 또한 향상된다.

WITH 구문은 여러 번 연속해서 쓸 수도 있다. 아래 예시를 참고하자.

WITH ex1 AS (
    query
),
ex2 AS (
    query
)

반복적으로 쿼리를 수행하는 WITH RECURSIVE 구문의 좋은 예시는 아래와 같다.

WITH RECURSIVE TIMETABLE AS (
    SELECT 0 AS HOUR FROM DUAL
    UNION ALL
    SELECT HOUR + 1 FROM TIMETABLE
    WHERE HOUR < 23
)

SELECT T.HOUR, IFNULL(COUNT, 0) as COUNT
FROM TIMETABLE as T
    LEFT JOIN (
        SELECT HOUR(datetime) as HOUR, COUNT(animal_id) as COUNT
        FROM animal_outs
        GROUP BY HOUR
        HAVING HOUR BETWEEN 0 and 23
        ORDER BY HOUR
    ) AS animal
    ON T.HOUR = animal.HOUR

4. Join

INNER JOIN의 틀은 다음과 같다.

SELECT col
FROM table1
  INNER JOIN table2
  ON table1.key = table2.key
WHERE condition
GROUP BY
HAVING
ORDER BY

OUTER JOIN의 틀은 다음과 같다.

SELECT col
FROM table1
  <LEFT/RIGHT/FULL> JOIN table2
  ON table1.key = table2.key
WHERE condition
GROUP BY
HAVING
ORDER BY

5. 문자열 함수

SUBSTRING은 문자열을 시작위치로부터 자르는 함수이다.

SELECT SUBSTRING('1234', 2);
-- 12 

SELECT SUBSTRING('abc', -2);
-- cb

SELECT SUBSTRING('12345', 2, 2);
-- 23

SUBSTRING_INDEX는 문자열을 자른 후 주어진 INDEX까지의 문자를 추출한다.

SELECT SUBSTRING_INDEX('이름,나이,시간', ',', 2)
-- 이름, 나이

위의 두 함수를 조합하면 split & get element를 구현할 수 있다.

SELECT SUBSTRING_INDEX(SUBSTRING_INDEX('이름,나이,시간', ',', 2), ',', -1)
-- 나이

CHAR_LENGTH는 string의 길이를 문자 단위로 반환한다. 이 함수의 경우 bytes도 문자 수로 반환하는데, LENGTH 함수는 바이트는 바이트 수로 반환하는 차이점이 있다.

CONCAT은 여러 값을 하나의 결과로 연결한다.

SELECT CONCAT('Summer', ' ', 1923) as release_date
-- Summer 1923

CONTAINS_SUBSTR은 대소문자를 구분하지 않는 정규화된 검색을 수행하여 값이 표현식에 있는지 확인한다. 값이 있으면 True, 없으면 False를 반환한다.

SELECT CONTAINS_SUBSTR('the blue house', 'Blue house') AS result
-- True

SELECT * FROM Recipes WHERE CONTAINS_SUBSTR(Recipes, 'toast')
+-------------------+-------------------------+------------------+
| Breakfast         | Lunch                   | Dinner           |
+-------------------+-------------------------+------------------+
| Potato pancakes   | Toasted cheese sandwich | Beef stroganoff  |
| Avocado toast     | Tomato soup             | Blueberry samon  |
+-------------------+-------------------------+------------------+

2번째 값이 1번째 값의 suffix이면 ENDS_WITH 함수는 True를 반환한다. STARTS_WITH는 당연히 반대로 생각하면 된다.

WITH items AS
  (SELECT 'apple' as item
  UNION ALL
  SELECT 'banana' as item
  UNION ALL
  SELECT 'orange' as item)

SELECT
  ENDS_WITH(item, 'e') as example
FROM items;

+---------+
| example |
+---------+
|    True |
|   False |
|    True |
+---------+

LEFT, RIGHT 함수는 아래와 같은 쓰임새를 갖는다.

WITH examples AS
(SELECT 'apple' as example
UNION ALL
SELECT 'banana' as example
)
SELECT example, LEFT(example, 3) AS left_example
FROM examples;

+---------+--------------+
| example | left_example |
+---------+--------------+
| apple   | app          |
| banana  | ban          |
+---------+--------------+

LTRIM, RTRIM, TRIM은 공백을 제거할 때 사용된다.

REPLACE 함수는 문자열 값을 바꾸는 함수이다.

WITH desserts AS
  (SELECT 'apple pie' as dessert
  UNION ALL
  SELECT 'cherry pie' as dessert)

SELECT REPLACE(dessert, 'pie', 'cobbler') as example
FROM desserts;

+--------------------+
| example            |
+--------------------+
| apple cobbler      |
| cherry cobbler     |
+--------------------+

TRANSLATE 함수는 REPLACE와 비슷하지만 차이가 있다. REPLACE 함수는 위 문자열을 하나로 취급한다. 즉, 위 예시에 나온 pie라는 문자열이 정확히 존재해야만 변환이 일어난다. 그러나 TRANSLATE 함수는 각 문자 하나 하나에 대한 변환을 수행한다.

SELECT TRANSLATE('abcde', 'ce', 'XY') FROM DUAL
-- abXdY

REPEAT은 지정한 수 만큼 문자열을 반복 반환한다.

SELECT REPEAT('abc', 3) as REPEAT
-- abcabcabc

REVERSE는 문자열을 역으로 반환한다.

SPLIT 함수는 delimiter 인수를 사용하여 value를 분할하여 array로 반환한다.

WITH letters AS
  (SELECT 'b c d' as letter_group)

SELECT SPLIT(letter_group, ' ') as example
FROM letters;

+----------------------+
| example              |
+----------------------+
| [b, c, d]            |
+----------------------+

6. 집합 연산자

Union은 복수의 쿼리 결과를 합친다. 중복을 제거하기 때문에 만약 중복을 그대로 유지하고 싶다면 Union All을 사용하면 된다.

SELECT *
FROM jan
UNION ALL
SELECT *
FROM mar

INTERSECT와 MINUS는 각각 교집합, 차집합 결과를 반환한다.

7. 날짜 함수

DATE_FORMAT 함수는 DATE_FORMAT(DATETIME, ‘%Y-%m-%d’)와 같이 사용하며, datetime 칼럼을 원하는 형식에 맞게 변환할 수 있다.

DATE_DIFF 함수는 두 datetime 사이의 차이를 구하는 함수인데, 차이의 기준을 지정할 수 있다.

-- end_date - start_date 구조임
SELECT DATE_DIFF(HOUR, start_date, end_date) FROM DUAL

YEAR, MONTH, DAY, WEEK, HOUR, MINUTE 등을 사용할 수 있다.

SYSDATE 함수는 현재 일자와 시간을 date 형식으로 반환하는 함수이다. 이를 원하는 형식으로 바꾸기 위해서 다음과 같은 작업을 수행할 수 있다.

SELECT TO_CHAR(SYSDATE, 'YYYYMMDD') FROM DUAL

8. 정규 표현식 함수

REGEXP_CONTAINS(value, regexp)는 value가 정규표현식 regexp와 부분적으로 일치하면 True를 반환한다.

REGEXP_EXTRACT(value, regexp, position, occurrence)은 REGEXP_SUBSTR와 같은 함수로, value에서 정규표현식 regexp와 일치하는 첫 번째 하위 문자열을 반환하고, 일치하는 항목이 없으면 Null을 반환한다. position은 optional 인자로, position이 지정되면 검색은 value의 이 위치에서 시작한다. position은 양의 정수여야 한다.

REGEXP_EXTRACT_ALL은 위 함수와 같은 효과이나 일치하는 value의 모든 하위 문자열 배열을 반환한다는 차이가 있다.

WITH email_addresses AS
  (SELECT 'foo@example.com' as email
  UNION ALL
  SELECT 'bar@example.org' as email
  UNION ALL
  SELECT 'baz@example.net' as email)

SELECT
  REGEXP_EXTRACT(email, r'^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.([a-zA-Z0-9-.]+$)')
  AS top_level_domain
FROM email_addresses;

+------------------+
| top_level_domain |
+------------------+
| com              |
| org              |
| net              |
+------------------+

REGEXP_REPLACE(value, regexp, replacement)는 regexp와 일치하는 모든 value 하위 문자열이 replacement로 바뀐 string을 반환한다.

WITH markdown AS
  (SELECT '# Heading' as heading
  UNION ALL
  SELECT '# Another heading' as heading)

SELECT
  REGEXP_REPLACE(heading, r'^# ([a-zA-Z0-9\s]+$)', '<h1>\\1</h1>')
  AS html
FROM markdown;

+--------------------------+
| html                     |
+--------------------------+
| <h1>Heading</h1>         |
| <h1>Another heading</h1> |
+--------------------------+

References

1) 프로그래머스 SQL 고득점 Kit
2) 참고블로그1
3) 참고블로그2
4) BigQuery문서

이번 포스팅에서는 AB Test를 진행할 때 거의 필수적으로 고려해야 하는 Sample Size를 구하는 과정에 대해 정리해본다.

AB Test Sample Size 구하기

1. Basic

귀무가설과 대립가설이 아래와 같다고 해보자.

[H_0: \mu = \mu_0]

[H_a: \mu > \mu_0]

실험의 특성을 고려하여 유의수준과 검정력을 설정하면 이를 통해 최소 Sample Size를 추정할 수 있다. 1 - 검정력인 $\beta$ 는 $\mu = \mu_a$, \mu_a > \mu_0$ 과 같이 $\mu$ 를 특정 값으로 지정하였을 때 구할 수 있다.

Reject Region(기각역)이 아래와 같이 정의된다고 하자. $\hat{\theta}$ 는 물론 추정량을 의미한다.

[RR = { \hat{\theta}: \hat{\theta} > k }]

$k$ 는 기각역이 시작되는 point이다.

2종 오류가 발생할 확률인 $\beta$ 는 대립가설이 참일 때 귀무가설을 적절히 기각하지 않을 확률을 의미한다. 이를 위 수식과 이어서 설명하면, 아래와 같이 표현할 수 있다.

[\beta = P(\hat{\theta} \leq k, \theta = \theta_a)]

위 사실들을 고려하여 다시 한 번 $\alpha$ 와 $\beta$ 를 구해보자.

[\alpha = P(\bar{Y} > k, \mu = \mu_0)]

[= P( \frac{\bar{Y} - \mu_0}{\sigma / \sqrt{n}} > \frac{k - \mu_0}{\sigma / \sqrt{n}}, \mu = \mu_0 )]

[= P(Z > \mathcal{z}_{\alpha})]

[\beta = P(\bar{Y} \leq k, \mu = \mu_a)]

[= P( \frac{\bar{Y} - \mu_a}{\sigma / \sqrt{n}} \leq \frac{k - \mu_a}{\sigma / \sqrt{n}}, \mu = \mu_a )]

[= P(Z \leq - \mathcal{z}_{\beta})]

위 2개 식에서 우리는 아래 사실들을 정리할 수 있다.

[\frac{k - \mu_0}{\sigma / \sqrt{n}} = \mathcal{z}_{\alpha}]

[\frac{k - \mu_a}{\sigma / \sqrt{n}} = -\mathcal{z}_{\beta}]

위 식을 $k$ 에 대해 정리하면 다음과 같다.

[k = \mu_0 + \mathcal{z}{\alpha} (\frac{\sigma}{\sqrt{n}}) = \mu_a - \mathcal{z}{\beta} (\frac{\sigma}{\sqrt{n}})]

따라서 위 식에서 $k$ 를 제외하고 $n$ 에 대해 다시 정리하면, Sample Size for an Upper-tail $\alpha$ - level Test를 얻을 수 있다.

[n = \frac{(\mathcal{z}{\alpha} + \mathcal{z}{\beta})^2 \sigma^2}{(\mu_a - \mu_0)^2}]

이 때 분모에서 제곱항 내부에 위치한 값을 Effect Size라고 표현하며, 실험에서 확인하고 싶은 유의미한 차이를 의미한다.

[\delta = \mu_a - \mu_0]

그리고 위 공식은 $n$ 이 충분히 클 때 성립한다.

2. Proportion Test

애플리케이션 상에서 AB Test를 할 때에는 비율의 차이를 metric으로 두는 경우가 많다. 예를 들어 새로운 모델을 배포하였을 때 Conversion Rate이 충분히 상승하였는지 알고 싶을 수 있다. 이 경우 귀무가설과 대립가설은 아래와 같다.

[H_0: p = p_0]

[H_a: p > p_0]

이 경우도 결국 똑같이 구할 수 있다. 신청 여부에 따른 분포이기 때문에 본 Test에서는 이항 분포가 사용된다. 그렇다면 분산은 아래와 같이 구할 수 있다.

[\sigma_0^2 = p_0 (1-p_0)]

새로운 모델에서의 목표 Conversion Rate을 $p_a$ 라고 하면 Effect Size는 $p_a - p_0$ 가 될 것이다. 그리고 표본 평균의 분산은 아래와 같이 구할 수 있다.

[\sigma^2 = p_0(1-p_0) + p_a(1-p_a)]

위 사실을 모두 종합하여 Sample Size를 구해보면 다음과 같다.

[n = \frac{(\mathcal{z}{\alpha} + \mathcal{z}{\beta})^2 (p_0(1-p_0) + p_a(1-p_a)) }{(p_a - p_0)^2}]

만약 아래와 같은 실험 설정이라면,

[\alpha = 0.05, 1 - \beta = 0.8, p_0 = 0.02, p_a = 0.022]

필요한 최소 Sample Size는 63215이다.

References

1) Mathematical Statistics with Applications(Denis D. Wackerly, …) Ch 10.4
2) Comparing Two Proportions – Sample Size

이번 포스팅에서는 AB Test에 대해 정리해본다. 사실 AB Test를 완벽히 설명하기 위해서는 정말 많은 자료와 깊은 고민의 경험이 필요하다. 본 글은 단지 필자가 생각을 정리하기 위해 작성한 글임을 밝혀둔다.

AB Test 기본

1. Background

AB Test는 간단히 말해서 User를 무작위로 2개의 그룹으로 구분한 뒤, 서로 다른 Action을 수행했을 때의 반응의 차이를 파악하는 분석 기법이다. Bayesian AB Test를 사용할 수도 있지만, 일반적으로는 Frequentist AB Test 관점이 더욱 자주 사용되는 것으로 보인다.

Null Hypothesis를 $H_0$, Alternative Hypothesis를 $H_1$ 이라고 한다면, 일반적으로 우리의 목표는 Null Hypothesis(귀무가설)를 기각하는 것이 된다. 만약 기각하지 못할 경우 우리는 귀무가설을 기각할 충분한 근거가 없다고 판단내려야 한다.

1종 오류는 귀무가설이 True임에도 우리가 실험을 통해 이를 기각하는 오류를 의미하며 $\alpha$ 라고 표기한다. 2종 오류는 반대로 귀무가설이 False임에도 우리가 이를 기각하지 않는 오류를 의미하며 $\beta$ 라고 표기한다. 그리고 귀무가설이 False인데 우리가 이를 잘 기각할 확률을 의미하는 검정력은 $1-\beta$ 로 계산한다.

이러한 가설을 기각할 것인가를 판단하는 기준으로 우리는 P-value를 사용하게 된다. P-value는 간단히 말해서 귀무가설 $H_0$ 이 True라고 가정하고 얻은 확률 분포에서 현재의 실험 결과가 나올 확률을 의미한다. 만약 이렇게 얻은 P-value가 0.01이라고 하면, 귀무가설이 True일 때 현재의 결과가 나올 확률이 1%란 이야기이므로, 우리가 일반적으로 사용하는 유의수준 0.05보다 한참 낮은 값이다. 따라서 보통 이 경우 귀무가설을 기각하고, 통계적으로 유의미한 차이가 있다고 결론 내리게 된다.

2. Netflix: What is an A/B Test?

이번 장에서는 AB Test에 대해 쉽게 풀어쓴 Netflix의 게시물을 소개한다. 원문 링크는 글 하단에 있는 참고 문헌 목록에서 확인할 수 있다.

위와 같이 2개의 선택지를 놓고 어떤 방식이 더 우수한 결과를 이끌어내는지 확인해 볼 수 있다. 좌측에 위치한 선택지가 기존 방식이라고 하면 이 방식의 UI를 경험할 고객 군을 Control Group이라고 지칭한다. 반면 새로운 선택지, 즉 우측에 위치한 방식의 UI를 경험할 고객 군은 Treatment Group이라고 한다.

위 사례 처럼 UI 관련 실험에서는 여러 변인들에 대해서도 살펴보아야 한다. 예를 들어 앱을 로딩하는데 시간이 더 걸린다거나, 네트워크 상태에 따라 영상의 질이 변하는 것은 아닌지 등을 반드시 체크해야 한다.

실험의 성과를 결정할 지표(metric)이 결정되었다면, 이 지표가 무엇을 의미하는지 명확히 파악해야 한다. 예를 들어 CTR을 metric으로 정했다고 하자. 단순히 CTR이 높다고 좋은 일일까? 어떤 고객들은 뒤집힌 영화의 제목을 보면서 제대로 보기 위해 컨텐츠를 클릭했을 수도 있다. 단순히 CTR이 높다고 좋은 실험이었다고 결론을 내려버리면 서비스를 제대로 이해하지 못한 것이라고 할 수 있다.

Netflix에서는 고객에게 주는 만족감을 더욱 잘 포착할 수 있는 일반적인 지표를 본다. 이를 member engagement with Netflix라고 표현할 수 있는데, 결국 이는 고객들이 Netflix를 이용하는 것을 취미로써 계속 선택하고 있는지에 관한 문제이다.

Holding everything else constant
무작위 추출로 2개의 그룹을 추출하였다 하더라도, 성과에 큰 영향을 줄 수 있는 여러 변인에 대한 점검은 필수적이다. Netflix에서는 멤버십의 길이, 컨텐츠의 선호도, 언어 등과 같은 요소들을 예시로 들고 있다. 오직 테스트하고자 하는 그 변수 하나만 달라야 한다.

It all starts with and idea
Netflix에서는 AB Test는 하나의 아이디어에서 출발한다고 강조하고 있다. 그것이 UI에 대한 변화일 수도 있고, 개인화 시스템이 될 수도 있고 가입 절차의 변화가 될 수도 있다. 이제는 익숙한 Top10 컨텐츠도 처음에는 테스트 가설에서 시작했다고 한다. 이 아이디어에서 얻고자 했던 것은 2가지이다. popular 컨텐츠를 소개함으로써 보는 이로 하여금 공유된 경험을 느끼게 만들고자 했던 것이 첫 번째 목표이고, 다른 사람들이 자주 보는 컨텐츠를 같이 향유함으로써 같은 주제로 다른 사람들과 대화하고 싶어하는 인간의 내재된 욕망을 이끌어 내는 것이 두 번째 목표였다고 한다.

특히 2번째 목표가 인상적인데, 주위를 슬쩍 둘러봐도 Netflix에서 히트작이 나오면 그 작품에 대해 이야기를 주고 받는 사람들을 자주 목격할 수 있다.

그렇다면 이 가설이 맞다는 것을 어떻게 증명했을까? 메인 지표로는 멤버십 구독이 설정되었는데 왜냐하면 이것이 결국 engagement with Netflix과 큰 상관 관계가 있기 때문이다. 그 외에도 Top10 목록에 나타난 제목 및 다른 부분에 대한 viewing과 같은 보조 지표 역시 검증의 기준으로 활용되었다.

마지막으로 모든 아이디어가 성공으로 이어지는 것이 아니기 때문에 일종의 guardrail이 설정되었다. 실험 역시 중요하지만 이것이 고객 경험의 질의 악화로 이어져서는 안된다. 따라서 실험 때문에 Treatment Group에 있는 고객들이 비정상적으로 서비스 센터로 연락을 더 많이 한다거나 하는 현상이 발생하면 이를 확인하여 조치하도록 하였다.

본 글을 통해 Netflix의 AB Test 철학에 대해 알 수 있었다.

3. 생각할 수 있는 문제점

다시 기본 주제로 돌아온다. 1장에서 설명한 수준으로 AB Test를 진행하고 의사 결정을 내린다면 운이 따르지 않을 경우 좋지 않은 결과를 떠안아야 할 수도 있다. 본 Chapter에서는 AB Test에서 발생할 수 있는 여러가지 문제점에 대해 짚어보고 해결책에 대해 논의한다. Reference에 링크를 첨부한 여러 블로그와 Medium에 있는 Tech Company의 포스팅 및 몇 가지 교재를 참조하였음을 밝힌다.

일단 첫 번째로 생각할 수 있는 부분은 유의 수준에 관한 것이다. 0.05라는 수치는 적절한 것일까? 이 부분에 대해서는 꽤 많은 챌린지가 발생했으며 일부 통계학자들은 0.05 대신 최소한 0.005 수준의 P-value를 고려하는 것이 적절하다고 이야기하고 있다.

그 다음으로는 실험 기간과 표본 수에 대해 생각해볼 수 있다. 실험 결과에서 같은 수준의 차이를 보였다 하더라도, 더 오랫동안 실험하거나, 더 많은 수의 표본을 모으면 표본 오차가 작아지기 때문에 더 작은 P-value를 얻을 가능성이 높아진다. 실제 서비스에서 AB Test를 실행한다고 하면 이 또한 비용이 들어가는 것이므로 실험 기간에 대해서는 신중해질 수 밖에 없다. 따라서 무작정 더 오래 실험해야 합니다! 라고 이야기할 수는 없는 것이다.

그래서 반드시 고려되어야 할 부분이 바로 Effect Size이다. P-value는 표본의 크기가 커질 때도 작아지지만 Effect Size가 커질 때도 작아진다. Effect Size의 수치 자체도 중요하지만, 이 수치가 실제 서비스에서 어느 정도의 의미를 갖는지를 명확히 판단하는 것이 더욱 중요하다.

• 0.1%의 CTR 향상은 성공이라고 말할 수 있는가?
• 이번에 새롭게 모델을 배포했다면 어느 정도의 향상을 기대해야 성공이라고 이야기할 수 있는가?

위와 같은 형식의 질문에 답해보고, 이를 바탕으로 실험 계획을 수립하고 이후의 분석 및 action item 선정 작업을 진행해야 할 것이다.

4. 적절한 실험 규모

목표하는 Effet Size, 1종 오류 및 2종 오류의 수준 등을 모두 고려하면 적절한 실험 규모를 산정할 수 있다. 2가지 오류 모두 고려하는 것이 마냥 쉽지만은 않다. 효과/차이가 없다는 것을 판별하는 것도 중요하고 유의미한 효과가 존재할 때 이를 잘 뒷받침하는 것 또한 놓칠 수 없는 것이 AB Test의 본질이다.

본 내용에 대해서는 더욱 자세한 설명이 필요하므로 추후 다른 글에서 정리해보도록 하겠다.

References

1) 블로그: AB Test에서 p-value에 휘둘리지 않기
2) Netflix: What is an A/B Test?