목차
intro
읽기 위해 필요한 지식
원 논문
Bag of Tricks for Efficient Text Classification
Abstract
이 논문은 text classification를 위한 간단하고 효율적인 baseline을 탐구한다.
우리의 실험은 fastText가 accuracy 측면에서 딥 러닝 classifiers와 동등하지만, 훈련과 평가에선 이 모델이 몇 배나 더 빠르다는 것을 보여준다.
이 논문은 standard multicore CPU를 사용하여 10분 이내에 10억 개 이상의 단어에 대해서 빠르게 텍스트를 train할 수 있고, 312K 클래스 중 50만 개의 문장을 1분 이내에 분류할 수 있다.
✨ 즉 빠르게 train하며 빠르게 분류가 가능한 모델을 만들어 냈다는 것이다 ✨
1. Introduction
[기존 모델들의 문제]
- 텍스트 분류는 웹 검색, 정보 검색, 순위 및 문서 분류와 같은 많은 응용 프로그램이 있는 자연어 처리에서 중요한 작업이다.
또한 이는 14도부터 신경망을 기반으로 한 모델이 점점 더 인기를 끌고 있다.
➡ 이러한 모델은 실제로 매우 우수한 성능을 달성하지만,
훈련과 테스트 시간 모두에서 상대적으로 느린 경향이 있어 매우 큰 데이터 세트에서의 사용엔 한계가 존재한다.
[linear classifiers의 잠재력]
- linear classifiers는 텍스트 분류 문제의 강력한 baselines으로 간주된다.
이것은 단순하지만 적절하게 사용하면 stateof-the-art 성능을 얻을 수 있다.
또한 매우 큰 말뭉치로 확장할 수 있는 잠재력도 가지고 있다.
[linear classifiers를 모델에 적용]
- 본 논문은 텍스트 분류의 맥락에서 이러한 baselines을 large output space을 가진 매우 큰 말뭉치로 확장하는 방법을 탐구한다.
- Word2vec의 연구에서 영감을 받아,
rank 제약과 빠른 loss 근사를 가진 linear models이 10분 이내에 10억 단어에 대해 훈련할 수 있는 동시에 최첨단 수준의 성능을 달성할 수 있음을 보여준다. - evaluation: 우리는 태그 예측과 감정 분석이라는 두 가지 다른 작업에서 fastText 접근 방식의 품질을 평가한다.
2. Model architecture
[linear classifiers의 사용]
- 문장 분류를 위한 간단하고 효율적인 기준은 문장을 bag of words (BoW) 으로 표현하고,
linear classifier(예: logistic regression 또는 SVM를 훈련하는 것이다.
[linear classifiers의 개선]
- 그러나 linear classifiers는 features 및 class 간에 매개 변수를 공유하지 않는다.
- 이는 예제가 거의 없는 large output space에서 일반화를 제한할 수 있다.
➡ 이 문제에 대한 일반적인 해결책은 linear classifier를 low rank matrices로 분해하거나 다층 신경망을 사용하는 것이다.
[모델 구성]
본 논문의 모델은 아래와 같다. 이는 rank 제약 조건이 있는 simple linear model을 보여준다.
[Figure 1] Ngram의 features(\(x_1, . ., x_N\))이 있는 문장에 대한 fastText 모델 아키텍처
features들은 hidden variable를 형성하기 위해 embedded되고 평균화된다.
1️⃣ 첫 번째 가중치 행렬 A는 단어 위의 look-up table이다.
2️⃣ 그런 다음 단어 표현은 text representation으로 평균화된다.
3️⃣ text representation은 linear classifier에 입력된다.
※ text representation은 잠재적으로 재사용될 수 있는 hidden variable입니다.
📜 look-up table이란?
Embedding 레이어는 입력으로 들어온 단어를 분산 표현으로 연결해 주는 역할을 하는데,
그것이 Weight에서 특정 행을 읽어오는 것과 같아 이 레이어를 룩업 테이블(Lookup Table)이라고 부르기도 합니다.
이게 무슨 소리냐면, 임베딩 층의 입력으로 사용하기 위해서 입력 시퀀스의 각 단어들은 모두 정수 인코딩이 되어있어야 한다.
특정 단어와 맵핑되는 정수를 인덱스로 가지는 테이블로부터 임베딩 벡터 값을 가져오는 룩업 테이블이라고 볼 수 있다.
이해가 안되다면 이 논문의 기반 논문인 Word2vec를 제대로 알고오자.
이 아키텍처는 중간 단어가 레이블로 대체되는 cbow 모델과 유사하다.
소프트맥스 함수 \(f\)를 사용하여 사전 정의된 클래스에 대한 확률 분포를 계산한다.
N개의 문서 집합의 경우, 이것은 클래스에 대한 negative loglikelihood를 최소화한다.
- 여기서 \(x_n\)은 n번째 document의 정규화된 bag of features이다.
- \(y_n the label\) A와 B의 weight matrices이다.
- 이 model 은 stochastic gradient descent와 linearly decaying learning rate를 사용하여 여러 CPU에서 비동기식으로 훈련된다.
📜 Negative Log-Likelihood (NLL) 보기
실제 softmax을 쓸 때는 negative log-likelihood(NLL)와 사용된다.
즉, 비유를 하자면 소프트맥스함수는 행복지수를 찾는 것이라면,
Negative Log-Likelihood (NLL)는 불행지수를 찾는것이다.
Negative Log-Likelihood (NLL)은 아래와 같은데,
input이 0일 때 무한으로 가고, input이 1일 때 0으로 간다.
즉 정리해보면 아래와 같은 관계를 갖는다.
loss를 계산할 때 우리는 정답 class에 대한 높은 확률은 낮은 loss로 이어지는 것을 볼 수 있다.
2.1 Hierarchical softmax
Hierarchical Softmax은 negative sampling과 같이 연산이 너무 비대해지는 것을 막기 위해 고안된 방식이다.
즉 한마디로 요약하자면 Hierarchical Softmax 방법을 사용하면 백터의 내적을 이진 분류로 바꿔 계산량을 줄일 수 있다는 것이다.
➡ 100만개의 단어를 벡터의 내적으로 구하면 벡터의 내적을 100만번 해야하지만,
Hierarchical Softmax 방법을 통한 이진분류로 구하면 \(log_2(100만)\) 약 19번만 계산하면 되는 것이다.
그렇다면 어떻게 이와 같이 이진분류로 계산하는지 알아보겠다.
예시
이는 모델 구조 자체를 full binary tree 구조로 바꾼 후에 단어들은 leaf node에 배치하는 것으로 부터 시작된다.
예를 들어서 설명해보겠다. 아래와 같은 문장(Context)가 있다고 해보자.
그렇다면 이 문장에서 ‘to’ 라는 중심단어를, window size = 1에 해당하는 주변단어 (want, eat) 들을 사용하여 학습한다고 가정하자.
그렇다면 아래와 같은 tree에서 학습이 될 것이다.
편의를 위해 want와 eat중 want로 만 를 예시로 들었다.
여기서 최종 확률(출력층의 값)은 root부터 leaf까지 가는 길에 있는 확률을 모두 곱하여 계산된다.
더 높은 확률의 edge를 선택해나간다.
그리고 아래에서 보다시피 각 edge의 합은 1이다.(확률)(똑같은 색의 합은 1이다)
즉 I가 나올 확률을 계산해보면, \(0.7\) x \(0.8\) x \(0.6\) 이다.
즉 위의 방법들을 통해 Hierarchical Softmax는 출력층의 값을 softmax 함수로 얻는 것 대신에 binatr tree를 이용하여 얻는 것이다.
일반화
그렇다면 위의 식들을 일반화해보자.
일반화한 노드는 아래와 같다.
각 단어가 output word가 될 확률의 식은 다음과 같이 계산된다.
- \(n()\): node
- \(L(w)\):leaf까지의 childern node의 수
- \(ch(n(w,i))\) : \(ch(n(w,i))\)의 자식 노드 중 한 쪽 (항상 왼쪽노드거나 오른쪽 노드를 뜻함)
- \(n(w,i)\): \(w\)의 leaf까지 가는 \(i\)번째 child node
- \(n(w, L(w))\): leaf node
- \(\begin{Vmatrix}x \end{Vmatrix}\)
- x가 참이면 1: 즉, \(ch(n(w,i))\)가 항상 왼쪽노드를 뜻할 때 가야할 왼쪽이면 1(왼쪽으로 가야하면 1)
- x가 거짓이면 -1: 즉, \(ch(n(w,i))\)가 항상 왼쪽노드를 뜻할 때 가야 노드가 오른쪽이면 -1(오른쪽으로 가야하면 -1)
- \(𝜎\): \(= 1 \over 1+e^{-x}\): 즉 시그모이즈 함수이다.
[식 해석]
-
먼저 \(n(w,j+1) = ch(n(w,j))\) 의 의미를 살펴보자.
그렇다면 우리는 \(ch(n(w,j))\)가 왼쪽 노드를 뜻한다고 해보자,
즉 이는 \(n(w,j+1)\)가 \(\begin{Vmatrix}x \end{Vmatrix}\)에 의해 왼쪽노드이면 1, 오른쪽 노드이면 -1이 된다는 의미이다.
※ \(ch(n(w,i))\)는 \(n(w,i)\)의 자식노드 중 하나를 취하면서 나간다(왼쪽 or 오른쪽 자식노드를 선택하며 나감) - 이렇게 된다면, \(𝜎(x) + 𝜎(-x) = 1\) 이라는 sigmoid function의 특징으로 인해 아래와 같은 식이 성립된다.
- \[p(n, left) = 𝜎(𝑣′_{n}^{T} h)\]
- \(p(n, right) = 1 - 𝜎(𝑣′_{n}^{T} h) = 𝜎(- 𝑣′_{n}^{T} h)\)
➡ 즉, 이는 앞서 언급한 이분된 자식 노드의 두 확률의 합이 1이 된다는 가정을 항상 만족하게된다.
- 그리고 이 hierarchical softmax는 \(\displaystyle\sum_{w=0}^{\|V|}{ℙ(w|w_I)}\)를 만족한다.
즉 \(|V|\)개를 모두 계산하는 것 보다 계산량이 줄어든다.
또한 각 \(ℙ\)가 확률이므로 각 노드의 확률을 곱하는 것이다. 즉 각 단어의 확률이 최종적으로 합이 1이되는 출력층을 도출 가능하다.
※ \(|V|\) 는 전체 단어의 개수이다. 즉 output word가 위의 예시와 같이 ‘I’, ‘want’, ‘to’, ‘eat’, ‘some’, ‘cake’이라면 \(|V|\) = 6이다.
이를 토대로 위 그림에서 \(w_2\)가 나올 확률은 다음과 같다.
따라서 i번째 vector는 학습이 진행됨에 따라 update가 될 것이고 이에 따라 복잡한 연산을 배제할 수 있으며 모든 단어에 대한 학습이 \(log(V)\)로 줄어든다는 큰 장점이 있다.
2.2 N-gram features
Bag of words는 BOW는 단어의 순서 단어들을 담는 가방으로, 아래와 같이 단어를 담는다.
이는 단어 배열 순서에서 얻을 수 있는 정보들을 파악할 수 없다는 단점이 있다.
※ 단어 단위로 쪼개 그냥 넣은 것이므로 Bag of words에선 이 단어들 사이의 배열 정보가 아이에 없다.
이 단점을 보안하기 위해, 우리는 local 단어 순서에 대한 일부 정보를 캡처하기 위한 추가 기능으로 bag of n-grams를 사용한다.
사용 결과는 아래와 같다.(아래 결과는 bi-gram 즉 단어 2개 단위로 쪼개는 것으로 예시를 들었다.)
이는 그래도 두 단어 별로 묶어 양 옆의 단어에 대해서의 순서 정보를 갖고있다.
이 방법은 단어끼리의 순서 정보를 아이에 담을 수 없는 Bag of word보다 더 많은 정보를 담고있다는 것을 알 수 있다.
이는 순서를 명시적으로 사용하는 방법과 비교할 수 있는 결과를 얻으면서 실제로 매우 효율적이다.
본 논문은 위에서 언급한 bigrams을 기반으로 Mikolov et al. (2011)과 동일한 hashing function과 10M bins을 사용하여 n-gram의 빠르고 메모리 효율적인 매핑을 유지하고, bigrams을 사용하지 않으면 100M bins을 사용한다.
3. Experiments
본 논문에선 두가지 task로 FastText를 평가한다.
[1] sentiment analysis와 기존 text classifer와 비교한다.
[2] 그 다음, tag prediction dataset에서 large output space으로 확장할 수 있는 용량을 평가한다.
본 논문의 모델은 Wowpal Wabbit 라이브러리로 구현될 수 있지만, 실제로 우리는 맞춤형 구현이 최소 2-5배 빠르다는 것을 관찰했다.
3.1 Sentiment analysis
[setting]
- Test accuracy [%] on sentiment datasets
- FastText has been run with the same parameters for all the datasets
- 10 hidden units and we evaluate it with and** without bigrams**
- learning rate selected on a validation set from {0.05, 0.1, 0.25, 0.5}
- Training time for a single epoch on sentiment analysis datasets compared to char-CNN and VDCNN.
[Results]
- bigram information improves the performance by 1-4%.
- 이 모델은 char-CNN and char-CRNN보단 정확도가 약간 높지만 VDCNN보단 성능이 낮다.
- n-grams을 사용하면 정확도를 조금 올릴 수 있다(eg, trigrams은 Sogou에서 97.1%까지 올라갔다.)
[setting]
- The hyperparameters are chosen on the validation set
- Comparision with Tang et al. (2015)
- tune the hyperparameters on the validation set
[Results]
- 본 논문의 방법이 Tang et al. (2015)보다 성능이 더 좋다.
*n-grams up to 5가 가장 좋은 성능을 낸다
3.2 Tag prediction
[setting]
- fastText for 5 epochs
- compare it to Tagspace for two sizes of the hidden layer 50 & 200
[Results]
- Both models achieve a similar performance with a small hidden layer, but adding bigrams gives us a significant boost in accuracy