[NLP] Byte Pair Encoding

https://arxiv.org/pdf/1508.07909.pdf

https://huggingface.co/docs/transformers/tokenizer_summary#subword-tokenization

Summary of the tokenizers

개요

단어 단위로 vocab을 구성을 하면 임베딩을 사용할 때 임베딩의 매개변수가 많이 커지게 되는 단점이 있다. 이는 RNN층의 매개변수의 수보다 압도적으로 많게 됩니다.

 

이런 매개변수 비중의 비대칭성을 해결하기 위해 문자 단위 토큰화가 주목을 받았으나 너무 길어진 sequence와 성능 저하의 문제점이 발생하게 됩니다.

 

따라서 서브워드 단위로 토큰화를 진행하게 되었는데 서브워드의 토큰화의 장점으로는 OoV(Out of Vocabulary) 문제가 없다는 점이 있습니다. 학습 데이터에서 등장하지 않은 데이터는 <UNK> 토큰으로 처리하게 되는데 <UNK> 토큰이 많아지면 성능이 떨어지게 되어있습니다.

 

하지만 서브워드 단위로 토큰화를 진행하게 되면 최악의 경우에는 문자 단위로도 토큰화가 진행될 수 있기 때문에 OoV문제가 발생하지 않습니다.

Byte Pair Encoding

BPE는 subwork 토큰화의 대표적인 방법이다.

 

- vocab 만들기

다음과 같은 말뭉치가 있다고 가정해 보자

low lower lowest newest

 

우선은 공백을 제외한 모든 문자를 vocab에 추가를 하고 각 단어의 끝에 '_'를 붙여 단어를 구분 짓는다.

Vocab: d e i l n o r s t w _
[ l o w _ ], [ l o w e r _ ], [ l o w e s t _ ], [ w i d e s t _ ]

 

다음으로 가장 많이 등장한 연속한 두 토큰을 찾아 Vocab에 추가를 하고 토큰을 붙입니다. 아래와 같은 경우는 'lo'가 세 번 등장으로 가장 많이 등장하였습니다.

Vocab: d e i l n o r s t w _ lo
[ lo w _ ], [ lo w e r _ ], [ lo w e s t _ ], [ w i d e s t _ ]

 

다음으로는 low가 세번 등장하므로 low를 추가합니다.

Vocab: d e i l n o r s t w _ lo low
[ low _ ], [ low e r _ ], [ low e s t _ ], [ w i d e s t _ ]

 

다음으로 es가 두번 등장하므로 es를 추가합니다.

Vocab: d e i l n o r s t w _ lo low es
[ low _ ], [ low e r _ ], [ low es t _ ], [ w i d es t _ ]

 

다음은 est가 두번 등장하므로 est를 추가합니다.

Vocab: d e i l n o r s t w _ lo low es est
[ low _ ], [ low e r _ ], [ low est _ ], [ w i d est _ ]

 

이러한 과정을 거쳐 모든 단어가 추가되거나 원하는 vocab size에 도달할 때까지 서브워드를 vocab에 추가합니다.

 

- BPE 인코딩

만들어지 Vocab으로 텍스트를 인코딩하는 방법은 몇 가지가 있습니다. 

첫 번째 방법은 앞에서부터 토큰화하되 가장 긴 것부터 Greedy로 매칭 하는 방법입니다.

Vocab: bcde ab cd bc de a b c d e _
abcde ==> ab cd e _

 

두 번째 방법은 가장 길게 매칭 되는 것을 먼저 매칭 하여 토큰화 하는 방법입니다.

Vocab: bcde ab cd bc de a b c d e _
abcde ==> a bcde _

 

- BPE 디코딩

BPE 디코딩은 해당 Id를 vocab에서 해당하는 서브 워드로 치환을 하고 합치면 됩니다. 이후 '_'은 공백으로 처리합니다.

[ 196 62 20 6 ] ==> [ I_ li ke_ it_ ] ==> "I_like_it_" ==> "I like it " ==> "I like it"