연금술사

요약

- 이미지 분류, 언어모델, 번역, 등의 다양한 문제에서의 이 방법론을 적용하여 해소됨을 보임.

사전지식(Preliminary)

방법론(method)

실험으로는 이미지 분류를 진행했고 MNIST에서는 오차율이 약간 크게나왔습니다. (Table 1). 하지만 그레디언트의 크기자체는 다른 방법론보다 작아진 것을 볼 수 있는데요.이는 더 빨리 수렴했음을 의미합니다.(FIgure 1)

요약

일반적으로 딥러닝이 텍스트나, 이미지 데이터셋에서의 고성능을 보이지만, 정형데이터(Tabular dataset)에서 성능이 우월한지는 잘 밝혀지지 않았습니다. 오히려 안좋은 경우도 있습니다. 이 논문은 실제로 그런지 딥러닝과 트리기반모델(RF / XGBoost)을 비교했고, 뉴럴넷(NN)이 성능이 그렇지 좋지 못하였다는 실험결과를 보여줍니다. 그리고, 이 이유에 대해서는 아래와 같이 설명합니다.

1. 정보량이 별로 없는 특징값에 대해서도 강건하다는 것(robust)
2. 데이터 방향(orientation을 유지해서) 학습이 잘 되도록 한다는 것
3. 비정형적인 함수도 쉽게 학습이 된다는 것입니다(딱딱 끊기는 함수도 학습이 잘됨).

Preliminary

• Inductive bias: 훈련되어지지 않은 입력에 출력을 예측하는 것. 학습을 한적이 없지만, 그간 보아왔던(학습했던)데이터를 이용하여(=귀납적 추론), 알고리즘이 예측하도록하는 가정입니다. 예를 들어, CNN은 Locality & Translational invariance, RNN은 Sequntial & temporal invariant, GNN은 permutational invariant 입니다.

도입

트리기반 모델은 대체로, 인공신경망보다 정형데이터에서 많이 성능의 우월함을 보였습니다. 아쉽지만, 이렇게 좋은 트리 기반모델은 미분이 불가능하기 때문에, 딥러닝과 혼합하여 사용하기 어렵습니다. 이 논문은 왜 트리기반 모델이 정형데이터에서 딥러닝 보다 우월한지를 보여주는 논문입니다.

방법론: 45개의 데이터셋에서, 딥러닝모델과 Tree기반 모델의 비교

OpenML에서 총 45개의 데이터셋을 만들었습니다. 이 데이터셋은 다음과 같은 선정기준으로 뽑혔습니다.

• Heterogenous columns: 컬럼이 매우 이질적일 것.
• Not high demiensional: 컬럼수가 행수에 비해서 1/10미만일것
• Undocumented dataset: 너무 정보가 없는 경우는 제외.
• IID: 이전 데이터가 직전데이터의 예측에 연관된 경우(예, 타임시리즈 제외)
• Realworld data: 합성데이터 아닐 것 6. Not too small: 너무 적지 않을 것 (특징값 <4 , 행수 <3,000)
• Not too easy: linear만해도 오차율 5%미만인경우는 제외
• Not deterministic: 변수 몇가지에 직접적으로 정해지지 않을 것.

모델은 아래와 같이 준비했습니다.

• MLP
• Resnet: MLP에 dropout, batch norm, skip connection을 추가한 형태입니다.
• FT-Transformer: 정형데이터에서 꽤 성능이 좋았던 네트워크
• SAINT: 이 네트워크도 정형데이터에서 성능이 좋았던 네트워크.

결과: Tree기반 모델이 더 고성능

• 벤치마크에서 분류든, 예측이든 트리기반모델이 더 고성능을 보였습니다. (Figure 1, Figure 2). Figure 1은 연속데이터만 있는 경우, Figure 2은 연속+카테고리데이터 둘다 있는 데이터입니다. 두 종류의 여러 데이터에서도 트리기반이 더 우수했습니다.

Dicussion:왜 Tree 모델이 Tabular데이터에서는 더좋은가? 3가지 이유

Discussion왜 더 좋을까? 크게 3가지 이유 때문에 좋다고 주장합니다.

• 뉴럴넷은 smooth solution 을 inductive bias을 갖기 때문에: 연구자들이 훈련데이터를 가우시안 커널을 이용하여 조금더 soothing하게 펼친 데이터를 만들고, 트리기반모델과 신경망모델을 비교했습니다. 신경망모델은 성능이 적게 떨어지는 반면, 트리기반모델은 급격히 떨어집니다 (Figure3). 이는 트리 기반모델이 예측시에 비선형 if, else등으로 자잘하게 쪼개는 반면, 뉴럴넷은 부드럽게 예측구분을 나눠주기 때문이라는 근거의 결과가 됩니다 (Figure 20).

•  인공신경망은 별로 정보량없는 데이터에대해 영향을 많이 받음: 정형데이터는 꽤 정보량없는 특징값이 많습니다. 랜덤포레트를 이용하여, Feature importance가 작은순으로 특징값을 제외시켜나가면서, GBT(Gradient boosting Tree)을 학습시켜나갔더니, 특징값이 꽤 많이 없어질때까지 좋은 성능을 냅니다 (Figure 4).인공신경망에서도 비슷한 패턴이보이긴합니다 (Figure 5). 하지만, 불필요한 정보를 특징값으로 넣는 비율이 클수록, 트리기반 모델보다 급격히 성능이 하락합니다 (Figure 6) 

• 인공신경망은 데이터를 rotation해도 비슷한 성능을 낸다고 합니다. [Andre Y. Ng, 2004]. 딥러닝자체가 rotationally invariant하다는 것인데, 데이터를 회전시켜도 학습이 잘된다는 말입니다. 즉, 메트릭스 중에 행 또는 열을 일부를 제거한다고해도 , 딥러닝알고리즘은 rotation에 맞게 학습한다는것입니다. Tabular 데이터는 실제로 돌리면 다른 데이터인데, 인공신경망은 학습을 이렇게 해왔기 때문에, 성능이 감소한다는 것입니다. 실제로 데이터를 돌려서 학습시켜도 다른 모델에 비해서 성능이 하락하지 않습니다 (Figure 6).

요약

흔히, 딥러닝모델을 예측치에 대한 설명이 되지않아 블랙박스 모델이라고 한다. Influnence function은 특정 테스트 데이터포인트를 예측하는데 도움을 주었던, 도움을 주지 않았던 훈련데이터를 정량적으로 측정할 수 있는 방법이다. 즉, 훈련데이터에서 특정데이터가 빠진 경우, 테스트데이터를 예측하는데 어느정도 영향이 있었는지를 평가한다. 이를 쉽게 측정할 수 있는 방법은 모델에서 특정 데이터를 하나 뺴고, 다시 훈련(Re-training)하면 된다. 하지만 딥러닝 학습에는 너무 많은 자원이 소모되므로, 훈련후에 이를 influence function으로 추정하는 방법을 저자들은 고안을 했다.

Influence function 계산을 위한 가정

훈련데이터에 대한 정의를 다음과 같이 한다. 예를 들어, 이미지와 같이 입력값을 $z$라고 한다.

• 훈련데이터 포인트(개별 하나하나의 데이터)를 $z_{n}$라고 한다.
• 이 훈련 데이터 포인트에 개별 관측치는 입력값 x와 라벨y로 이루어져 다음과 같이 표기한다 $z_{i}=(x_{i}, y_{i})$
• 그리고, 모델의 학습된 파라미터를 $\theta$라고 한다.
• 주어진 파라미터한에서, 데이터포인트 z를 주었을 때의 loss 값을 $L(z,\theta)$ 라고한다.
• 훈련데이터 1부터 n개까지의 총합 로스를 emprical loss라고 정의한다 $1/n \sum_{i=1}^{n}L(z_{i},\theta)$
• 학습과정을 통해 얻어진 파라미터가 위의 empirical loss을 가장 줄일 수 있게 학습된 파라미터를 $\hat{\theta}=argmin_{\theta\in\Theta}1/n\sum_{i=1}^{n}L(z_{i}\theta)$

Influence function 의 종류

Influence functiond은 training point가 모델의 결과에 어떤 영향을 주었는지 이해하기위해서 3가지 방법론을 고안했다.
1. 해당 훈련데이터포인트가 없으면, 모델의 결과가 어떻게 변화하냐? (=가중치가 어떻게 바뀌어서 결과까지 바뀌게 되나?)
= 이 방법론은 loss가 얼마나 변화하냐로도 확인할 수 있다.
연구에서는 이를 up-weighing 또는, up,params이라는 표현으로 쓴다. up-weighting이라는 표현을 쓰는 이유는 특정 훈련데이터가 매우작은 $\epsilon$ 만큼 가중치를 둬서 계산된다고하면, 이 $epsilon$을 0으로 고려해서 계산하기 때문이다. 또는 이를 loss에 적용하면 "up,loss"라는 표현으로 기술한다.
2. 해당 훈련데이터포인트가 변경되면(perturnbing), 모델의 결과가 어떻게 변경되나?

Influence function 의 계산(up,loss)

아래의 계산식에서 좌측($I_{up,loss}(z,z_{test})$)은 예측값 $z_{test}$을 예측하는데있어, 특정 훈련데이터포인트 $z$가 얼마나 영향을 주었나(=loss을 얼마나 변화시켰나)를 의미한다. 마지막줄의 각 계산에 들어가는 원소는 다음 의미를 갖는다.

• $-\nabla_{\theta}L(z_{test},\hat{\theta})^{T}$: 특정 테스트 z포인트를 넣었을 때, 나오는 loss을 학습파라미터로 미분한 값이다. 즉
• $H_{\hat{\theta}}^{-1}$: 학습된 파라미터의 hessian의 inversed matrix이다.
• $\nabla_{\theta}L(z,\hat{\theta})^{T}$: 특정 훈련데이터포인트 z를 넣었을 때, 나오는 loss을 학습파라미터로 미분한 값이다.

위의 세 값을 다 계산하여 곱해주기만하면 특정 훈련데이터z가 테스트데이트를 예측하는데 로스를 얼마나 변화시켰는지 파악할 수 있다.

여기서 문제는 해시안 메트릭스($H_{\hat{\theta}}^{-1}$)를 계산하는 것이 매우 오래걸린다는 것이다. 따라서 저자들은 아래와 같이 추정방법으로 해시안메트릭스의 역행열을 구한다.

Influence function 계산의 어려움(비용)

Influence function 계산이 어려운 부분(계산비용이 큰 이유) 2부분 때문이다.

1. 해시안 메트릭스의 역행렬을 구해야함: 해시안 메트릭스는 각 행렬에 파라미터의 개수가 p개라고 하면, $O(np^{2}+p^{3})$의 계산량이 든다는 것이다.
2. 훈련 데이터 포인트에 대해서 모든 데이터포인트를 다 찾아야한다는 것. 예측에 도움이 안되는 데이터포인트를 찾으려면 훈련데이터가 n개면 n개의 데이터포인트를 찾아야한다.

다행이도 첫 번째 문제인 해시안 메트릭스이 역행렬을 그하는 것은 잘 연구가 되어있어서 해결할 수 있다. 명시적으로 해시안의 역행렬을 구하는것 대신에 해시안 역행렬과 손실값을 곱한 Heissan-vector product(HPV) 을  구하는 것이다



Inversed hessian matrix 구하기(HPV구하기, 중요)

조금더 구체적으로는 저자들은 해시안메트릭스의 역행열을 구하기보다는, 해시안메트릭스의 역행렬과 loss에 해당하는 vector($\nabla_{\theta}L(z_{test},\hat{\theta})^{T}$)을 한번에 구하는 방법을 소개한다. 이는 책 또는 github코드에서 주로 Inversed hessian vector product (inversed HVP)라고 불린다.

이를 구하는 2가지 방법이 있다.

1. Conjugate gradient (CG)
2. Stocahstic estimtation

저자들은 주로 Stocahstic estimation 방법으로 이를 해결하려고 한다. 

다음의 서술은 위의 HVP을 구하는 방법에 관한 것이다.

1. 훈련 데이터 포인트 전체 n개에서 매번 t개만을 샘플링 한다.
2. HVP의 초기값은 v을 이용한다 (이 때, v은 $\nabla_{\theta}L(z_{test}, \hat{\theta})^{T}$을 사용한다. 테스트세트에 대한 로스값의 gradient이다.)
3. $\tilde{H_{j}}^{-1}v=v+(I-\nabla_{\theta}^{2}L(z_{s_{j}, \hat{\theta}})\tilde{H}_{j-1}^{-1}v$ 을 계속한다.
4. 위의 과정(1-3)을 반복한다.

위와 과정을 충분히 반복하고, t을 충분히 크게 뽑는 경우 HVP값이 안정화되고 수렴된다고 한다. 이 방법이 CG방법보다 빠르다고 언급이 되어있다.

하이라이트 결과

Leave one out 방법과 유사하게 Influence function이 loss값의 변화를 추정한다.

개인적으로 아래의 Figure 2가 제일 중요해보인다. 훈련데이터를 하나 뻈을때(leave-one-out)의 방법과 Inlfuence function으로 예측한 예측값이 거의 정확하다면 선형을 이룰것이다. 아래의 그림은 이를 뒷받침하는 결과로 사용된다.

손실함수를 미분할 수 없는 경우도, 손실함수를 대략적으로 추정(Smooth approximation)  한 경우 추정할 수 있다.

아래의 결과는 Linear SVM을 이용하여 예측한 loss의 값과, 실제 retraining한 경우의 예측값을 보여주고 있다. Linear SVM 자체에서는 Hinge 값이 쓰이는데 (ReLU와 유사하게) 미분이 불가능하다. 따라서, 저자들은 0에서 미분불가능할 때 smooth하게 변경하기위해서 아래와 같이 smooth hinge라는 것을 만들어서 어느정도 추정한 값을 쓰고 있다($smooth ~hinge(s,t)=tlog(1+exp((1-s)/t)$). 즉 이 함수는 t가 0이되면 0이될수록 미분이 불가능한 hinge loss와 동일해진다. 이렇게 적용했을 때 결과가 (b)와 같다. 미분불가능한 함수를 미분 가능하게 조금 수정한다면, (b) 와 같이 t=0.001인 경우, t=0.1인 경우와 같이 어느정도 influence function이 데이터를 빼고 재학습한 것과 같이 추정이 가능하다는 것이다)

Influence function의 유즈케이스

아래는 influence function을 언제 쓰는지에 관한 것이다. 

1. 모델이 어떤 방식으로 행동하는지를 알 수 있다.: 아래의 그림 (Figure 4)은 SVM과 Inception(CNN기반)에서의 물고기 vs 개의 분류문제이다. 이 Figure 은 여러가지를 우리에게 알려준다.

1. 우리의 직관은 "SVM은 딱히 이미지의 위상정보을 이용하지 않으니, 이미지의 거리(L2 dist)가 클수록 분류에 도움이 안될 것"으로 생각할 수 있다. Figure 4을보면 x축이 Euclidean dist인데, 400이상인경우 influcen function의 크기가 0에 가까워지는 것을 볼 수 있다.
2. 녹색의 데이터포인트는 물고기의 학습데이터이다. 물고기를 예측하는데 있어, 물고기의 이미지만 도움을 주는 것으로 파악할 수 있다.
3. 반대로, Inception 은 딱히 위상정보가 아니어도, 이미지의 외형(contour)을 잘 학습하기 때문에, 거의 모든 이미지가 분류에 영향을 주는 것을 알 수 있다. 즉 물고기의 예측하는데 있어서, 일부 강아지 이미지가 도움을 줄 수 있다는 것이다.

요약

RandomForest 의 Feature importance은 여러가지가 있을 수 있지만 크게는 대표적으로 1) 불순도 기반 방식(Impurity based): tree을 나눌 때, 쓰이는 특징값으로 나눴을 때, 클레스가 잘 나뉘는 가 얼마나 변화하는지 측정하는 방식. 불순도의 변화가 크면 클수록 트리를 잘 나눴다는 것을 의미중요한 특징 값이라는 것, 2) 순열 기반 방식(Permutation based): 각 특징값을 데이터 포인터에 대해서 랜덤하게 순서를 바꿔서, 정확도가 떨어지는지 확인하는 방식. 정확도가 크게 떨어질 수록 중요한 특징값임을 가정하는 방식이 있다.

선행

랜덤포레스트는 이 포스팅에서 깊게 다루지는 않지만, 트리구조를 만들 때, 배깅(bagging) 중복을 포함해서 임의로 데이터를 N개씩 뽑고, Feature bagging (속성을 뽑을 때도 랜덤하게 K)만큼 뽑아서 각각의 트리를 만든다. 그렇게 만들어진 약한 분류기(Tree)을 여러개 만들고 분류모델이면 Voting하여 얻은 값을 반환한다.

Gini importance / Mean Decrease in Impurity (MDI)

이 방식은 Gini importance라고도 불리고, MDI라고도 불리는 방식이다. 의미하는 것은 모든 랜덤포레스트의 각각의 트리에서 해당 특징값으로 트리를 나눌 때, 감소한 불순도의 평균을 의미한다(For each feature we can collect how on average it decreases the impurity. The average over all trees in the forest is the measure of the feature importance[1]).

Gini impurity은 아래와같이 계산한다 (주의: Gini coefficient와 다른 내용이다).

$Gini impurity = 1 - Gini$

$Gini = p_{1}^{2}+p_{2}^{2}+...+p_{n}^{2}$

n은 데이터의 각 클레스를 의미한다. 가령 아래와 같이 주황색 데이터와, 파란색데이터를 구분하는 문제라면 n은 2가된다. 노드를 나누기전을 부모노드라고하면, 부모노드에서의 Gini은 파란색공이 5개중에 3개, 노란색이 5개중에 2개이므로 $Gini=(3/5)^{2}+(2/5)^{2}$가 된다. 따라서, Gini impurity은 $Gini impurity=1-(3/5)^{2}+(2/5)^{2}$이다. 그리고 나눈 후를보면, 좌측은 $Gini imputiry = 1- ((2/3)^{2}+(1/3)^{2}$. 우측은 $Gini imputiry = 1-((1/2)^{2}+(1/2)^{2})$ 이다. Gini impurity의 변화량이 얼마나 변화했는지를 파악하는 것이기 때문에, 다음과 같이 부모의 impurity - (자식노드의 imputiry의합)과 같이 계산한다.

$1-(3/5)^{2}+(2/5)^{2} - [(1- ((2/3)^{2}+(1/3)^{2}) - 1-((1/2)^{2}+(1/2)^{2})]$

위의 계산에서 중요한 것을 빠뜨렸는데 특징값 A에 대해서 위와 같은 과정을 진행했다고하면, 모든 노드 중에서 A을 이용한 분기에를 모든 트리에서 찾은다음에 평균낸 값이 Gini importance이다. 혹은, 어떤 방식에서는 나누려는 노드의 가중치를 곱해서 많이 나눴던 노드에서는 더 가중치를 주기도 한다.

아래의 그림을 보면 feature importances (MDI)라는 것이 표시되어있다. 이는 위의 과정(Gini importance)을 이용해서 각 노드를 나눴을때 불순도가 크게 변화하는 정도의 평균을 계산했다는 의미이다. (이 데이터셋은 타이타닛 데이터셋). 생존자와 사망자를 구분할 때, sex을 이용해서 구분했을 때, sex을 안썼을 때보다 평균적으로 더 트리구조가 깔끔하게 나뉘어져나갔다는 것을 의미한다. 

[1] https://mljar.com/blog/feature-importance-in-random-forest/#:~:text=Random%20Forest%20Built%2Din%20Feature%20Importance&text=It%20is%20a%20set%20of,sets%20with%20similars%20responses%20within.

Permutational importance / Mean Decrease in Accuracy (MDA)

Permutation importance은 트리를 만들때 사용되지 않았던 데이터들 OOB(Out of bagging, 랜덤포레스트의 각 트리를 만들 때, 랜덤으로 N개의 데이터를 중복을 포함하여 뽑는데, 그 때 사용되지 않았던 데이터들)을 이용하여, OOB인 데이터들에 대해서 해당 특징값을 랜덤하게 섞은후에 예측력을 비교한다.

아래와 같이 a,b,c,d,e,의 특징값을 가진 1,2,3,4,5번 데이터가 있다고하자. 모델을 빌딩할 때, 랜덤으로 뽑은 데이터가 1,3,5였고, 안타깝게 2,4번은 중복을 포함혀어 뽑았지만 뽑히지 않았던 데이터라고 하자. 

이 때, 특징값 a에 대해서 1,2,3,4,5번의 a특징값의 순서를 랜덤하게 바꿔버리고 원래 데이터셋으로 만든 모델과 성능을 비교한다. 성능차이가 크면 클수록 랜덤으로 돌리지 말았어야할 중요한 별수라는 것이다. 또는 2번과 4번의 데이터 또는 바꿔서 차를 계산해도 이론상 큰 차이는 안날 것이다. 이렇게 특징값a에 대해서, 순서변경 전후의 성능을 비교하고, b,c,d,e,f에 대해서도 비교하면 permutation feature importance가 계산된다.

아래와 같이 permuation importance을 계산하면 성별이 나온다. boxplot으로 나온 이유는 random forest의 각 tree에서의 틀린정도의 분포를 그렸기 때문이다. 해석은 다음과 같다. 테스트 세트에서 생존여부를 맞추는 정도는 sex을 랜덤하게 바꿀 경우 가장 많이 성능이 떨어졌다는 것을 의미한다. 각 트리별로 고려했을 때, 평균적으로 0.25정도 성능이 떨어졌음을 의미한다.반대로 random_num, age등은 어떤 tree에서는 빼나 안빼나 구별력차이가 없었던 것을 의미하기도 한다 (box plot에 0에 맞닿아있다 (이는 랜덤으로 뽑은 데이터셋이 운이 안좋게 구별을 못한 경우일 수도 어서 0이 나왔을 수도있다.

요약

Quadruplet loss은 Triplet loss에서 같은 클레스끼리 더 응집할 수 있도록 제약을 추가한 손실함수이다. Quadruplet loss함수를 기반으로 딥러닝 네트워크를 만든 것이 Quadruplet loss이다. 이 Quadruplet loss을 이용하면 같은 클레스(Intra-class)는 더 응집력 있게 임베딩이 되며, 다른 클레스(Inter-class)끼리는 더 거리가 멀어지게 임베딩할 수 있게 학습을 한다. 또한 Quadruplet network에서는 학습을 더 잘할 수 있게, 이미 구별이 어려운 데이터포인터들을 먼저 학습할 수 있게하는 전략도 함께 구사한다(=어려운 문제를 잘 풀다보면 쉬운 문제를 잘 푸는 것과 같은 이치)

Quadruplet loss

Quadruplet loss의 핵심은 아래의 손실함수의 정의이다 (식3).  $x_{i}$의 의미는 Anchor에 해당하는 데이터 포인터이다. (즉 쿼리에 해당하는 데이터포인터임). $x_{j}$은 $x_{i}$의 클레스와 같은 클레스를 지닌 데이터포인터이다(=Positive sample이라고도 한다). 한편, $x_{k}$은 $x_{i}$와 다른 클레스를 지닌 데이터포인터이다. 여기까지가 Triplet loss의 정의를 위한 과정인데, Quadruplet은 $x_{l}$이라는 다른 데이터포인터의 고려사항을 두는데, $x_{k}$랑은 다른 클레스의 negative sample을 의미한다. 식 3에서의 마지막 s들은 class을 의미한다.

식(3)에서의 g(x1, x2)은 무엇인가? g()함수는 "learned metric"이라고 영어로 표현한다. 쉽게 말하면, 딥러닝 네트워크에서 뱉어주는 유사도에 해당한다. learned metric에서 여기서 쓰는 g(x1, x2)은 두 이미지(x1, x2)사이의 유사도를 의미한다. g(x1, x2)가 크면 클수록 이미지가 다른 것을 의미하며, 유사한 이미지일수록 같은 클레스의 이미지일 것이라고 학습시킨 것이다.

다시 돌아와서, 식(3)을 그림으로 표현하면 다음과 같다. 식(3)에서의 첫 번째 term은 아래의 그림의 좌측에 해당하고, 두 번째 term은 아래의 그림의 우측에 해당한다. 좌측그림을 보면, $x_{i}, x_{j}$은 같은 클레스이다. 따라서 두 클레스의 유클리디언 공간에서의 위치는 유사해야하기에, 두 거리에 해당하는 g(x1, x2)은 가까워야한다(=0에 수렴). 반대로 $x_{k}$은 고양이 이다. 따라서, $x_{i}, x_{k}$은 멀어져야 의미론적으로 임베딩이 되었다고 할 수 있다. 즉, 첫 번째 Term은 같은 클레스의 그림은 가깝게, 다른 클레스의 그림은 멀게 표현하라는 제약을 둔 것이다. 

반대로, 우측의 이미지를 첫항에 해당하는 $x_{i}, x_{j}$은 같은 클레스이다. 따라서 두 클레스의 유클리디언 공간에서의 위치는 유사해야하기에, 두 거리에 해당하는 g(x1, x2)은 가까워야한다(=0에 수렴). 그 다음항은 $x_{l}, x_{k}$이다. $l$은고래이다.  $k$와도 다르고 $x_{i}$와도 다르다. 즉, negative samples의 클레스 사이끼리도 거리가 멀어야한다는 것을 의미한다.

Quadruplet network

그리고 나서, 아래의 그림과 같이, 모델을 구성하여 학습한다. 아래의 그림중, 흰색배경에 해당하는 부분은 Triplet network (withtriplet loss)으로 구성과 동일한 부분이다. 빨간색 쉐딩이 되어있는 부분은 본 연구에서 추가한 항목이다. 좌측의 입력(Quadruplet)부터보면 Ref와 Pos은 같은 이미지이다. Neg은 흰색옷을 입은 Ref와 다른 이미지이다. 그리고, 마지막 Neg2은 Neg1과도 다르고, Ref와도 다르다. 그리고, 뉴럴네트워크를 이미지 4개를 한번에 입력값으로 받는다.이 뉴럴네트워크는 (Shared)라고 표기한 것처럼, 가중치를 공유한다. 즉, 단일 네트워크를 각각 학습시키는 것이 아닌, 동시에 같은 네트워크를 학습시키는 것이다. 그 후, g(x1, x2)에 해당하는 FC8을 통과하여 이미지의 유사도에 해당하는 벡터를 반한다. (주의할 것은 triplet에서 적용한 g(x1, x2)은 상수를 반환하고, 본 연구에서 반환하는 것은 2차원 vector을 반환한다). 벡터를 반환시, 벡터의 첫원소는 두 이지의 유사도를 의미할 것이라고 가정하여 softmax을 취한 normalization값을 얻는다(=0과 1사이). 그 후에 quadruplet loss을 적용한다.

Margin-based online hard negative mining

문제는 이 이미지 4개를 어떤 조합으로 넣을지, 어떤 순서로 넣을지이다. 본 연구에서는 Margin-based online hard negative mining이라는 방법으로 학습방법을 정의했다. 직관적으로 해석하면, 구분하기 쉬운문제-> 구분하기 어려운문제로 학습하는 것보다, 애초에 구분하기 어려운문제부터 학습하는 것이 더 좋을 것이라는 직관에 해당한다. 또한, 얼마나 멀어야 구분하기 어려운지(margin)을 정의하기는 어렵다. 여기서는 다음의 방법을 이용했다.

마진은 $\alpha$로 표현하는데, Anchor와 negative class와의 learn metric(=g(x1, x2), 유사도)의 평균과 Anchor와 positive class의 learned matrix의 차이를 이용한다 (식 4).  아래의 각 $\mu_{n}, \mu_{p}$은  Anchor와 negative class와의 learn metric의 평균, Anchor와 positive class의 learned matrix을 의미한다. 여기서의 $x_{l}$은 등장하지 않는다. 본문에는 등장하지 않지만, $l$보다는 $i, j, k$와의 마진을 구현하기 위하기 위함일 것이다.  

실제로 이렇게 구하는 $alpha$은 각각 식(3)에 다시 할당이되어야 한다.문제는 식(3)에서 에서 $alpha_{1}, alpha_{2}$을 각각 구하기위해서는 식4와 같이 N까지의 모든 샘플을 구해야한다는 것인데, 각 iteraion마다 g(x1, x2)의 파라미터가 바뀌니, $alpha$도 각 이터레이션마다 업데이트해주어야한다. 즉, 모든 샘플에 대해서 1회 이터레이션당 $\mu_{n}, \mu_{p}$을 계산해야한다는 것이다. 본 연구에서는이를 간단하게 해결하기위해서, N개의 이미지쌍을 구현하는 것이 아니라, 배치사이즈 M을 이용하기로했다. 학습할 때, 1회업데이트에 쓰이는 배치사이즈(M)에 대해서만 계산한다는 것이다. 즉, $N_{p}=M, N_{n}=2M$이 된다. 

또한, 파라미터의 최적화를 위해서, 스토케스틱 그레디언트 디센트(SGD)을 계산에서도 $\alpha$가 껴있기 때문에 계산이 어려울 수 있으니 아래의 식을 이용한다.

요약

본 연구는 단어를 숫자로 표현하는 과정에 해당하는 continous word representations(=word embedding, =denser representation)중에서 언어의 모양새(형태학적인) 구조를 최대한 살려서 벡터화하는 것에 초점을 두고 있다. 기존의 word2vec, glove처럼 단어를 훈련데이터에서만 찾을 수 있는 구조(dictionary: vocabulary을 포함한 구조)에서 찾을 수 없는 경우는 적용이 어렵기 때문이다(=이를 OOV, out of vocabulary라고 함). 따라서, unseend word(rare words)에 대해서 강건한 모델을 만들기 위해서, n-grams을 이용해서, 각 단어를 <n-gram1, n-gram2..., 원형단어>의 세트로 처리하여, 단어를 표현하고 Skip-gram을 이용해서 훈련한 모델을 제시한다.

방법론

방법론을 이해하려면, word2vec의 skip-gram을 이해가 요구된다. 가장 중요한건 Skip-gram은 주어진 단어 하나로, 주변단어를 예측하는 문제이기 때문에, 아래의 같은 목적함수를 가진다. $w_{t}$은 t번 째의 주어진 단어이며, $w_{c}$은 t번째 단어의 주변단어이다. 즉, 한 단어가 주어졌을 때, 주변단어를 얼마나 잘 맞추는지에 관한 목적함수이다. 이 목적함수를 최대화하면된다. 그리고나서, 각 단어를 잘맞추는지(잘 분류해서 선택했는지) Softmax함수로 평가하면된다.

추가로, 기술적으로 할만한 것으로는 절대 주변에 없을 것 같은 단어들을 추가로 전달하여 손실함수로 사용해볼 수 있다. 이에 관한식이 아래와 같다. log()의 안에있는 식을 L()로 표현하면 아래의 식으로 변환할 수 있다.

Fasttext의 핵심을 subword model이다. 주어진 단어가 w가 있다고 했을떄, 각 단어를 w의 bag of n-gram으로 표현하는 것이다. 예를 들어, where이라는 단어가 주어졌을 때, <whe, her, ere>로 표현할 수 있다. 추가로 Fasttext은 원래 단어까지를 넣어 하나의 bag-of-n-gram을 구성한다. 즉, where -> <whe, her, ere, where>까지를 하나의 세트로 구성해서 표현한다.  이는 <her>의 단어와는 다르다. 왜냐하면 <her>은 하나의 세트가아니라 독립적인 단어이며 <whe, her, ere, where>안에 있는 "her"은 구별될 수 있기 떄문이다. 각각 bag-of-ngram에 표현될 수 있는 집합을 g라고 표현하고, 각n-gram으로 표현한게 G만큼의 사이즈를 가지면 아래와 같이 표현할 수 있다. $z_{g}$은 bag of n-gram에서 표현된 서브단어(subword)이고, v은 맞춰야할 단어를 의미한다. 따라서, subword와 원래단어를 동시에 임베딩하는 형식으로 OOV문제를 개선한 모델이라고 할 수 있다.

결과

1. word similarity: sg(skip-gram), cbow(continous bag of words), sisg-(subword information skipgram with OOV->null vector표기), sisg(subword로 처리한경우) AR, DE등은 아랍, 체코, 덴마크등의 언어인데, human judgement간의 유사도를 비교하였을때 가장 높은 성능을 보였다.

2. word analogy: analogical reasoning task로 word2vec에서 king-man=queen과 같은 논리적 추론을 의미한다. 과거에 각 언어별로 만들어 놓았던 analogical reaskong task로 실험해본 결과 sisg이 syntatic한 부분에서 우수한 성능을 보였다.

"y Mikolov et al. (2013a) for English, by Svoboda and Brychcin (2016) for Czech, by Köper et al. (2015) for German and by Berardi et al. (2015) for Italian."

3. morphological representation을 진행했던 사전연구와 human judgment와 모델의 스코어관의 상관관계를 봤을때, 스피어만 상관계수가 높을수록 사람의 판단과 유사한 성능을 내서 높은 성능이라는 해석할 수 있다. 

Doc2vec, Word2vec처럼 각각의 단어를 벡터로 표현하고자하는 시도가 꽤 있어왔다. 이런 벡터표현은 단순히 bag-of-words으로 표현하거나, one-of-k (흔히 one-hot vector)라고 부르는 방법으로 표현할 수 있다. 그러나 이러한 시도들은 여러 문제가 있었고, word2vec으로 더 밀도있는 표현방식(denser representation)을 사용했다. 한 단어를 doc2vec으로 임베딩하여 표현할 수 있었듯이, document 또는 paragraph을 벡터로 표현할 수 있는데 왜 supervised paragraph2vec가 필요한건가? 이에 대한 장점은 있는건가? 이에 대한 대답을 Supervised Paragraph Vector: Distributed representations of words, documents, and class에서 찾을 수 있다.

Supervised paragraph vector가 필요한 이유?

범용적인 임베딩모델(예, doc2vec, paragraph2vec 이하 PV)은 정말 단순한 알고리즘으로 hidden layer가 하나만 존재하여 매우 학습이 편하고, 쓰기도 편하지만, 임베딩에 다음과 같은 문제가 있다. word2vec의 CBOW(continous bag of words)을 생각하면, 단어벡터(word vector, 단어를 임베딩한 벡터)를 구문론적(syntactical)으로 학습하기도하고, 의미론적(semantic)적으로 학습하기도 한다. 예를 들어, "the cat sat on the mat"이라면, cat을 예측할땐, 주변단어인 the와 sat을 이용해서 예측한다. 따라서 유사한 단어가 동시에 많이 출현될수록, 같은 벡터로 표현될 확률이 높고, 주변단어의 쓰임이 비슷하게 나왔을 때도, 유사한 벡터로 임베되는 경향이 있다 (Figure 1. A). 하지만, 해결해야하는 문제가 감정분석(sentimental analysis)로, wonderful과 amazing이 같은 그룹으로, terrible, awful이 부정그룹으로 분리되서 해야한다면 어떨까? 동시출현 또는 유사한 단어가 많이 출현하는 것을 학습하여 임베딩하는 word2vec의 이런 학습방식은 특정테스크에 모두 걸맞게 쓰기가 쉽지가 않다. 이런 일반화된 분석방법으로는 이런 임베딩의 표현의 의사결정바운더리(decision boundary)을 긋기가 쉽지않다. 본 논문은 word2vec, paragraph2vec, doc2vec의 제한점을 해결하고자 시도했던 논문이다. 

word2vec의 출력에이어의 

SPV의 핵심 아키텍처

해결방법은 다음과 같다. word2vec의 아키텍처와 같이 하나의 입력레이어, 하나의 히든레이어, 하나의 출력레이어로 구성한다(Figure 4-A). 좌측에 아키텍처의 구성을보면, $x1,..., x_{\gamma}$까지는 한 문단에 들어가있는 단어가 one hot vector로 변환된 벡터를 의미한다. 각각 one-hot vector로 표시할 때, 총 단어의 개수가 V라면, V개 원소의 개수를 가지고, 원소중 하나만 1인 벡터가 된다. 차이점이라면, 다음과 같은 벡터들도 입력값에 전달된다. 바로 도큐먼트의 one-hot vector인 $p$와 클레스의 라벨인 $z$가 추가로 전달된다는 것이다. 아래의 그림에서는 $p$은 전체 문서(documents)의 수를 의미한다. $z$은 클레스라벨을 의미해서, $M$개의 클레스가 존재한다고 했을 때, 각각 하나하나를 one-of-K(one-hot)벡터로 인디케이팅한 것을 의미한다. 그리고 h에 해당하는 히든레이어의 출력을 $\delta$개의 원소를 가진 벡터라고하자.

위와 같이 셋팅한 경우, $W^{(1)}$은 임베딩을 위한 dense layer의 가중치 메트릭스로 $\mathbb{R}^{V\times\delta}$가 된다(V개의 one-hot vector을 $\delta$개로 압축하는 fully connected layer 이기 때문). $W^{(2)}$은 출력레이어의 가중치로 W1의 전치행렬과 크기가 같다(왜냐하면, 출력해야하는 단어도 V개의 벡터여야 하기 때문이다). 

위의 아키텍처에서 목적함수를 클레스라벨이랑 도큐먼트의 인덱스 단어에 최대한 학습할 수 있게 다음과 같이 정의하였다. 

1. SPV-DM(여러 단어가 주어진 경우, 한단어를 예측하는문제):  아래의 우변의 시그마 내 첫 항은 "CBOW와 같이 주변단어가 주어졌을 때, 예측하고자하는 단어를 예측하기위한 손실함수", 두 번째 항은 "문서내에 해당 예측하고자 하는 단어가 있을 확률", 세 번째 항은 "문서의 라벨이 주어졌을 때, 해당 단어가 있을 확률"을 모두 더한 값이다.

$L_{SPV-DM} = \frac{1}{T}\sum_{t=1}^{T}\sum_{j=1}^{\gamma}log(p(w_{t}|w_{t+j})+log(p(w_{t}|d))+log(p(w_{t}|c)))$

2. SPV-DBOW(한 단어가 주어진 경우, 여러단어를 예측하는 문제)

$L_{SPV-DBOW} = \frac{1}{T}\sum_{t=1}^{T}\sum_{j=1}^{\gamma}log(p(w_{t+j}|c))$

논문에는 등장하지 않는 limitations

1. 본 모델은 word2vec에 사용되는 모델과 구조가 유사해서, OOV(out of vocabulary)의 문제를 그대로 갖고있다. 따라서 unseen data에 대해서는 모델이 강건하지 않을 수 있다.

Summary: BERT(Bidirecitonal Encoder Representations from Transformer)

사전학습이 된 양방향 표현법으로 각 모든레이어에서 우측과 좌측의 문맥정보(context)을 결합하는 것을 사용하는 언어모델이다. BERT는 Transformer의 목적함수가 변형된 형태이다. 이전 개발된 Transformer에서는 이전단어들을보고 다음단어를 예측하는 Uni-directional(일방향)의 언어모델이었다면, BERT은 다음의 차이가 있다.

• 사전학습을 양방향으로 해서, 문맥정보를 더 파워풀하게 학습 (=Deeply bidirectional. 예, 나는 밥을 ???.    ???->밥을->나는) (Transformer와 유사한 언어를 인코딩해서 압축하는 형식이나, Transfoermed은 한번에 모든 단어들은 한거번에 보지만, BERT은 left-to-right, right-to-left순차적으로 본다)
• 사전학습시에 Pre-traniing 과 fine tuning을 두 단계를 모두 활용하는 형식(BERT은 2가지의 손실함수를 가지고있고, 이 두 가지의 손실함수의 합을 손실함수로하여 동작한다)

Introduction

Pre-training: 대용량 데이터를 일단 학습시켜놓고, 이후에 재학습하는 것을 의미한다. 이러한 사전학습으로 튜닝하는 방식은 크게 두가지로 나뉜다.

1. Feature-based (Parameters are fixed): 파라미터를 고정시켜놓고(e.g. tensorflow에서는 freezing). e.g) ELMO
2. Fine-tuning (Parameters are not fixed): 특정 테스크에는 굉장히 적은 파라미터. GPT 계열이나 Uni-directional 언어모델.

그런데, 여태까지 이런 접근법은 언어를 표현하기위해, 1) 단방향의 언어를 사전학습(예, 좌측에서 우측으로만 단어를 예측), 2) 파라미터를 고정하든 안하든 같은 목적함수를 가지고 사전학습을 한다. 

=> 저자들은 이러한 기술이 사전학습을 더 잘 쓸수 있는것에 오히려 제한을 둔다고 얘기한다. 특히, fine-tuning을 하는 방법에서는 더욱 그렇다고 얘기한다 (아마도, 글자는 좌측에서 우측으로만 예측해야하니까, 반대로 우측에서 좌측으로 이해해서 얻을 수 있는 단어들 ([] 먹었다) 이런 정보들도 활용을 못하지 않나?) 생각이든다. 저자들도 가장큰 단점은 단방향모델이 가장 단점이라고 하고 있다(The major limitation is that standard language models are unidirectiona). GPT2 같은 경우도, sentence level task(문장단위의 예측모델)이나 token level task(예, question anwering)에서는 최적의 성능을 보여주지 못했는데, 양방향의 문맥정보를 활용하지 못했기 때문이라고 한다.

BERT는 Transformer의 목적함수가 변형된 형태이다. 특히, fine-tuning based approaches이다. 그리고, 단방향의 단점을 개선한 MLM(Masked language model)이다. 즉, 이전 개발된 Transformer에서는 이전단어들을보고 다음단어를 예측하는 Uni-directional(일방향)의 언어모델이었다면, BERT은 양방향으로 파악한다는 것이다.

. BERT은 2가지의 손실함수를 가지고있고, 이 두 가지의 손실함수의 합을 손실함수로하여 동작한다.

손실함수의 종류는 다음과 같다.

1. Loss function 1: BERT은 문장에 15%정도를 Masking을 해놓고, 처리한후에 masking된 단어를 에측하는 방법에 관한 손실함수를 가지고 있다. (일종의 CBOW다). 다만, CBOW와의 차이점은 양방향으로 단어를 예측한다. 
2. Loss function 2: 문장들 사이에 관계를 학습하여, 주어진 문장과 다음문장이 연속된 문장인지 문맥을 학습(contextual)할 수 있게끔 손실함수를 설계했다. 예를 들어, 문장A가 문장B와 연속된 문장인지? 아닌지를 학습하기위한 장치를 마련했다. 다음 문장이라는 라벨링을 추가했다. 

Pre-requisite

Pretraning language model은 어떤것들이 있어왔고, 어떤 제한점이 있었는가?

1. Unsupervised feature-based approaches: 주로 좌측에서, 단어들을 임베딩하기위해사용되었고, 우측으로 언어모델링을 하는 방법들이 많이 사용되었거나(Mnih and Hinton, 2009), 좌측의 잘못 입력된 단어들과 우측의 문맥으로 단어들이 적절하게 쓰였는지 판단하는 목적으로 주로 쓰였었다. 이 접근법들은 일반화되면서, 문장을 임베딩하는 방법이나(Kiros et al., 2015; Logeswaran and Lee, 2018), 문단을 임베딩 하는 방법들로도 사용되었다s (Le and Mikolov, 2014). 예를들어, 문장(senstence)을 표현하기위해서는 다음 문장들 어떤게 적절한지 적절한 문단을 훈련하는 목적함수를 갖게 사용했거나, 좌측의 단어들이 있을떄, 다음문장을 생성(generation)하는 방법, 또는 오토인코더에 사용되는 목적함수들이 사용되었다. ELMo와 이전세대들이 에애 해당한다. 2017년~2018년에 개발된 ELMo은 전통적인 단어임베딩을 위해 쓰였고, 좌측->우측과 우측->좌측의 다른 언어모델로부터 문맥정보를 담은 feature들을 추출해냈다. 그 다음에 left-to-right, right-to-left표현을 단순히 concatenatation시켜서 이 특징값을 사용했다. ELMo와 유사하게, 다른모델들도 있었는데 단순히 feature based으로 사전학습했지만, deeply bidrectional을 사용하진 않았다. 
2. Unsupervised Fine-tuning approaches: 유사하게, 사전에 학습된 가중치에 목적에 맞게 모델의 가중치 전체를 다시 학습하는 방법으로는 단어를 표현한는 방법으로는 2008년에  연구(Collobert and Weston, 2008)가 시작되었다. 이후에는 일단 인코더에서 문장이나 문서를 임베딩한 후에, 목적에 맞게 재학습하는 연구들이 2015~2018년에 주로 있었다. 이러한 접근법의 가장 큰 장점은 스크레치(scratch) 모델의 적은수의 파라미터만 다시 재학습된다는 것이다. 이에 해당하는 것이 OpenAI GPT, GLUE에 해당한다.
3. Transfer learning from supervised data: 자연어, 기계번역등에서의 많은 연구들이 이에 해당한다. 

본문

BERT은 크게 2단계의 프레임워크의 순서를 따른다. 첫 번째는 pre-tranining, 둘 째로는 fine-tuning이 이에 해당한다. 사전 학습때는 모델은 여러 테스크에 적용하기위해서, 라벨이 없는 데이터셋(비지도학습)을 학습한다. 그 후, fine-tuning단계에서는 BERT model을 초기파라미터가 세팅된후에, 모든 파라미터를 다시 목적에 맞는 테스크(down stream task)를 위해 재학습한다.

아래의 그림처럼, 출력부문을 제외하고는 같은 모델을 쓴다. 그러나, 출력부도 초기에는 BERT가 사전학습된 파라미터로 초기세팅이 이뤄진다. 가장 두드러진 특징은 BERT은 어떤 목적의 테스크든, 동일한 아키텍처라는 것이다. 즉, pre-tranied model의 아키텍처와 final downstream model가 거의 차이가 없다는 것이다.

• 모델: 모델은 multi-layer bidirecitonal transformer encoder이다. Transformer은 2017년에 개발된 transformer을 이용했다. Transformer의 적용은 거의 동일하고, 파라미터 사이즈들만 좀 다르다. BERT base은 GPT등 성능비교를위해 만들어낸것들이고 BERT Larget은 꽤 큰 사이즈의 파라미터를 가진 모델이다.
• 입출력의 표현: 이 모델은 다양한 downstream task을 쓰기위해서, 명확한 표현이 필요하다고 한다. 입력은 1개의 문장 또는 2개의 문장인데, 따로 묶인 형태로 입력값이 전달된다. 모든 문장에서의 첫토큰은 문장의 시작임을 알려줄수 있는 CLS라는 스페셜한 토큰을 전달해준다. 만일 두개의 문장이라면 두 문장을 이어붙인 후에 하나의 CLS 토큰을 부여한다. 이 문장이 그럼에도 다른문장임을 나타내기 위해서는 스페셜 토큰을 하나 붙여주는데 [SEP] 토큰이다.
•  

Pre-tranining BERT

손실함수의 종류는 다음과 같다.

1. Loss function 1: BERT은 문장에 15%정도를 Masking을 해놓고, 처리한후에 masking된 단어를 에측하는 방법에 관한 손실함수를 가지고 있다. (일종의 CBOW다). 다만, CBOW와의 차이점은 양방향으로 단어를 예측한다. 
2. Loss function 2: 문장들 사이에 관계를 학습하여, 주어진 문장과 다음문장이 연속된 문장인지 문맥을 학습(contextual)할 수 있게끔 손실함수를 설계했다. 예를 들어, 문장A가 문장B와 연속된 문장인지? 아닌지를 학습하기위한 장치를 마련했다. 다음 문장이라는 라벨링을 추가했다. 

예를 들어, 아래와 같다. 연속적인 문장인 경우는 라벨을 True, 아니면 False

RNN계열에서도 Bi-direcitonal RNN(=shallow)도 가능하지 않은가?

정답은 Yes이다. RNN계열에서도 bi-directional RNN으로 예측하고자하는 Y을 양방향으로 예측한다. 아래의 그림과 같이 Bi-directional RNN은 "The results clearly show that"의 첫 번째 토큰인 The을 이용해서 예측값을 만들고자할때, reverse된 문장의 가장 첫 번째 단어인 "that"의 결과값과 concat시킨 후에 softmax을 적용해서 예측한다. 즉 LSTM의 unit이 d이면, 반환되는 hidden state의 vector size가 2d가 된다.

Key contribution

• We cast few-shot learning as a supervised message passing task which is trained end-to-end using graph neural networks.

• We match state-of-the-art performance on Omniglot and Mini-Imagenet tasks with fewer parameters.

• We extend the model in the semi-supervised and active learning regimes

=> 그레프에서 노드분류에 많이 사용되는 메시지 패싱(A노드를 분류하고자할 때, A와 인접한 노드의 라벨을 참조하여 라벨을 예측하는 방법)을 이용해서 few-shot을 진행함. 위의 전략으로 실제 데이터 Omnigolot(알파벳분류), 이미지분류(Mini-imagenet)에서 우수한 성능을 보임. 이 모델을 준지도학습과 엑티브러닝에 확장함.

Problem setting

아래와 같이 입력값(T)과 출력(Y)가 있다고하자. T을 자세히보면 s까지 x와 l개가 있는데, 이는 라벨이 있는데이터가 s개가 있다는 것이다. 그리고 x_r까지 있는 데이터는 라벨이 없는 입력값이며, x_t은 분류하고자하는 test data이다. l의 라벨은 K개로, 멀티라벨분류문제이다. 또한, 각 입력x끼리는 독립적이며, 같은분포p 에서 나왔다고 가정한다(=train, test split가 랜덤하게 주어진것과 비슷한 상황).

Y는 x_t의 라벨을 의미한다.

이런 데이터셋에서 다음의 3가지의 문제가 등장한다.

1.  Few shot learning: r=0 (라벨이 없는 데이터는 없으며), 라벨이 있는 데이터만 있고, 예측해야할 데이터가 1개일 경우(t=1). 그리고, 훈련데이터 샘플의 개수인 s 가 비교적 넉넉하여 s=qk 인경우. 예를 들어 예측해야할 라벨(K=5) 5개인데, q=10이어서, 데이터가 50개인경우를 의미한다. 이러한 경우는 10-shot, 5 way learning이라고 한다.

2. Semi-supervised learning: r>1 인경우여서, 라벨이 없는 훈련데이터세트가 존재하는 경우를 의미한다. 위의 문제는 같이 훈련데이터 내 라벨이 있든,없든 같은 분포에서 x가 나왔기 때문에, 라벨이없는데이터를 최대한 활용하는 것을 목표로 한다. 주요한 가정은 x와 x'(라벨이없는데이터)는 같은 분포에서 나왔기 때문에, 둘은 같은 라벨일 것이다라는 것이 주요 가정이다.

3. Active learning: 모델이 학습하고자하는 데이터의 라벨을 인간에게 요청하고, 계속학습하는 학습방법. Semi-superivsed의 특별한 경우라고 생각되며, s+r << s0 , S <<S0. 라벨이 없는 학습데이터의 개수보다 라벨이 있는 학습데이터의 개수가 충분히큰 상황. 본 연구에서는 semi-supervised보다 active learning이 얼마나 더효과적인지를 분석하고자한다.

- 몇가지 배경지식이 필요하다. Human In The Loop (HITL)은 컴퓨터는 빠르고, 정확하지만, 문제를 푸는 방법은 멍청하고, 인간은 느리고, 똑똑하지만 문제푸는 방법은 현명하다. 이 둘을 머신러닝 학습에 혼합하는게 HITL이라는 개념이다. 사실 모든 기계학습과정은 HITL의 연속이다. 예를 들어, 사소한 하이퍼파라미터만 해도 사람의 과정이 들어가기 때문이다. Active learning은 이 HITL에서 인간의 개입이 명시적으로 들어간 반복적인 작업이다. 

1. Oracle(인간)이 모델과 라벨이 있는 데이터를 생성함. ground truth을 제공하는 원천. 라벨러+ 모델생성자로 생각할 수 있음.
2. 모델은 오라클이 준 라벨을 학습함. (추가적으로 인간이 준 검증용 데이터 세트에 학습로그를 제공)
3. 모델은 데이터에 라벨을 붙이고자하는 라벨없는 데이터를 인간에게 요청함
4. 이 과정을 반복

모델링

기본적으로 언어는 계층구조를 갖는다. 구(Phrase)와 절(Clause)처럼 단어가 모여서 구(phrase)을 이루고, 구가 모여서 절(clause)을 이룬다. 예를 들어, 형용사절을 들어본적이 있는가? "men in black"과 같이 "in black"이 형용사절을 이루고, 이러한 구가 모여서 명사절 등을 이룬다. 사람은 이와 같이 계층구조를 이루는 것을 이애할 수 있다. 유사하게, "이런 계층구조의 모델링을 명시하진 않았지만 Tree 구조를 이용한다면, 더 좋게 할 수 있지는 않을까"에 대한 질문이 본 페이퍼의 핵심이다.

본 페이퍼를 읽기 위해 다음의 배경지식이 필요함

1. Inductive bias (aka learning bias): 귀납적 편향. 학습편향. 모델이 경험하지 않은 데이터를 입력받았을 때, 출력을 예측하는데 사용하는 가정의 집합임. 정확히 학습되지 않은 것들을에 대해서 귀납적으로 학습한 것들이 있으니, 예측을 할 수 있지 않느냐의 대한 가정임. 

=> 본 연구에서는 이러한 학습편향을 정보의 주기(생성~삭제)를 따로따로 관리하여(differentiation) 증진하겠다는 전략이다. High ranking neuron과 low ranking neuron으로 나눠서, 고순위의 뉴런들에서는 정보를 오래 가지고 있게하고, 저순위 뉴런에서는 정보를 빨리 잊게하는 테크닉을 보임.

Key technique: ON-LSTM

1. Cumax: Cumax은 Cumsum(cummulative summation)과 softmax을 합친것이다(합성함수다). 이를 사용하는 이유는뉴런의 랭킹을 결정할때 지나치게 명확히 high, low랭킹을 구분하는것을 피하기위해 사용되었다고한다. " To avoid a strict division between high-ranking and low-ranking neurons, we propose a new activation function, the cumulative softmax, or cumax(), to actively allocate neurons to store long/short-term information". Cumax에서 반환되는 값은 누적합이기에 연산도중에 1이뜨면, 그 이후의 인덱스의 값들은 모두 1일 것이다. 따라서, 어느 인덱스부터 1인지에 대한 기준이 되는 지를 표기했는데, $d_{t}^{f}$이다.

import tensorflow as tf

# Equation (6)
def cumax(x, axis=-1):
    return tf.math.cumsum(tf.nn.softmax(x, axis), axis)

def split_point(x):
    x = x.numpy()
    return np.where(x == 1)[0].min()

2. LSTM : Ordered neuron LSTM은 기본적인 LSTM연산을 필요로하고, 그 위에다가 master gate을 부착한다. 그렇기에 LSTM연산도 포함된다.

    
class ONLSTM(tf.keras.layers.Layer):
    def __init__(self, input_dim, hidden_unit):
        super(ONLSTM, self).__init__()
        self.input_dim = input_dim
        self.hidden_unit = hidden_unit
    
    def build(self):
        # Equation 1-5: basic LSTM model
        self.w_f = self.add_weight(shape=(self.input_dim, self.hidden_unit), name='standard_lstm_kernel')
        self.w_i = self.add_weight(shape=(self.input_dim, self.hidden_unit), name='lstm_input_kernel')
        self.w_o = self.add_weight(shape=(self.input_dim, self.hidden_unit), name='lstm_output_kernel')
        self.w_c = self.add_weight(shape=(self.input_dim, self.hidden_unit), name='cell_memory_kernel')

        self.u_f = self.add_weight(shape=(self.hidden_unit, self.hidden_unit), name='standard_recurrent_kernewl')  # u_f
        self.u_i = self.add_weight(shape=(self.hidden_unit, self.hidden_unit), name='lstm_input_recurrent_kernel')
        self.u_o = self.add_weight(shape=(self.hidden_unit, self.hidden_unit), name='lstm_input_recurrent_kernel')
        self.u_c = self.add_weight(shape=(self.hidden_unit, self.hidden_unit), name='lstm_input_recurrent_kernel')

        self.b_f = self.add_weight(shape=(1, self.hidden_unit), name='forget_bias')
        self.b_i = self.add_weight(shape=(1, self.hidden_unit), name='input_bias')
        self.b_o = self.add_weight(shape=(1, self.hidden_unit), name='output_bias')
        self.b_c = self.add_weight(shape=(1, self.hidden_unit), name='cell_bias')
        
        
   def _base_lstm_op(self, x, h):
        f_out = tf.nn.sigmoid(tf.tensordot(x, self.w_f) + tf.tensordot(h, self.u_f) + self.b_f)
        i_out = tf.nn.sigmoid(tf.tensordot(x, self.w_i) + tf.tensordot(h, self.u_i) + self.b_i)
        o_out = tf.nn.sigmoid(tf.tensordot(x, self.w_o) + tf.tensordot(h, self.u_o) + self.b_o)
        c_out = tf.nn.tanh(tf.tensordot(x, self.w_c) + tf.tensordot(h, self.u_c) + self.b_c)
        return o_out * tf.nn.tanh(c_out)

3. ON-LSTM: strucure gate mechanism:

    def call(self, x, h):
        h, outputs = self._base_lstm_op(x, h)

        lstm_f = outputs[0]
        lstm_i = outputs[1]
        lstm_c_hat = outputs[2]


        # Equation 9: master forget gate.
        wx = tf.einsum('ij,jk->ik', x, self.w_f)  # (1xhidden)
        uh = tf.einsum('ij,jk->ik', h, self.u_f)  # (1xhidden)
        f_t = cumax(wx + uh + self.b_f)  # (1 x hidden)

        # Equation 10: master input gate.
        i_t = 1 - cumax(wx + uh + self.b_i)  # (1 x hidden)

        # Equation 11:
        w_t = f_t * i_t #  (1 x hidden)

        # Equation 12:
        f_t_hat = f_t * (lstm_f * i_t + 1 - i_t)

        # Equation 13:
        i_t_hat = i_t * (lstm_i * f_t + 1 - f_t)

        # Equation 14: first d_t neuron of the previous cell state will be complete erased.
        c_t = f_t_hat * self.c_t + i_t_hat + lstm_c_hat
        self.c_t = c_t

        return h

Reference: https://openreview.net/forum?id=B1l6qiR5F7