해당 포스트에서는 tokenizer의 한 종류인 BPE(Byte-Pair Encoding)에 대해 알아보겠습니다.
BPE Algorithm
BPE Algorithm은 이미 오래 전에 제안되었던 데이터 압축 알고리즘이지만 OOV(Out-Of-Vocabulary)를 해결하기 위해 NLP분야에 도입되었습니다.
BPE Algorithm을 간단히 설명하자면 글자(character)단위에서 빈도수에 기반해서 점차적으로 단어 집합(vocabulary)을 만들어가는 알고리즘입니다.
더 자세한 방법은 아래의 예시를 통해 설명드리겠습니다.
BPE Algorithm Training
Pre-tokenize
Pre-tokenize를 띄어쓰기를 기준으로 했다고 했을 때의 결과가 아래와 같다고 가정을 하고 설명드리겠습니다.
Token Frquency hug 10 pug 5 pun 12 bun 4 hugs 5 Split character
Initial(base) vocabulary가
h,u,g,p,n,b,s와 같다면 아래와 같이 위의 token들을 분리할 수 있습니다.Token Frquency h, u, g 10 p, u, g 5 p, u, n 12 b, u, n 4 h, u, g, s 5 Byte-Pair
위에서 분리한 token 쌍의 빈도 수를 살펴봅니다. 이때 token 쌍을 Byte-Pair라고 부르며 연속된 두 token을 하나의 쌍으로 만든 것을 말합니다.
Byte-Pair Frquency Formula Frquency h, u 10(hug) + 5(hugs) 15 u, g 10(hug) + 5(pug) + 5(hugs) 20 p, u 5(pug) + 12(pun) 17 u, n 12(pun) + 4(bun) 16 b, u 4(bun) 4 g, s 5(hugs) 5 Merge 빈도 수가 가장 큰
u, g를 하나의 token으로 merge 합니다. 그럼h,u,g,p,n,b,s,ug로 vocabulary가 update됩니다. 그 결과는 아래와 같습니다.Token Frquency h, ug 10 p, ug 5 p, u, n 12 b, u, n 4 h, ug, s 5 Iteration 이후 3번과 4번을 사용자가 정한 vocabulary 크기가 될 때까지 진행합니다.
만약 사용자가 vocabulary 크기를
10으로 정했다면 아래와 같은 순서로 3번과 4번을 반복하니다.Vocabulary :
h,u,g,p,n,b,s,ugByte-Pair Frquency Formula Frquency h, ug 10(hug) + 5(hugs) 15 p, ug 5 (pug) 5 p, u 12 (pun) 12 u, n 12(pun) + 4(bun) 16 b, u 4 (bun) 4 ug, s 5 (hugs) 5 Token Frquency h, ug 10 p, ug 5 p, un 12 b, un 4 h, ug, s 5 Vocabulary :
h,u,g,p,n,b,s,ug,unByte-Pair Frquency Formula Frquency h, ug 10(hug) + 5(hugs) 15 p, ug 5 (pug) 5 p, un 12 (pun) 12 b, un 4 (bun) 4 ug, s 5 (hugs) 5 Token Frquency hug 10 p, ug 5 p, u, n 12 b, u, n 4 hug, s 5 Vocabulary :
h,u,g,p,n,b,s,ug,un,hug
Result
사용자가 정한 크기(
10)의 vocabulary가 되면 아래와 같은 결과들을 얻을 수 있습니다.- Vocabulary :
h,u,g,p,n,b,s,ug,un,hug - Merge order:
ug➡️un➡️hug
- Vocabulary :
BPE Algorithm Apply
위에서 학습한 BPE Algorithm을 pug bug mug에 적용해 보겠습니다.
Pre-tokenize
pug bug mug➡️pug,bug,mug
Split character
pug➡️p,u,gbug➡️b,u,gmug➡️m,u,g
Byte-Pair
pug➡️p,u,g➡️pu,ugbug➡️b,u,g➡️bu,ugmug➡️m,u,g➡️mu,ug
Compare merge order & Merge
해당 순서에서는 merge order를 비교하고 우선순위에 있는 byte-pair를 먼저 merge 하고 merge가 불가능할 때까지 merge를 해주면 됩니다. 그러나 만약 merge order에 비교하려는 쌍이 없는 경우 우선순위가 없는 것으로 판단하여 merge가 불가능한 경우로 판단하면 됩니다.
Merge order:
ug➡️un➡️hugpug➡️p,u,g➡️pu,ug➡️p,ug(더 이상 merge 불가능)bug➡️b,u,g➡️bu,ug➡️b,ug(더 이상 merge 불가능)mug➡️m,u,g➡️mu,ug➡️m,ug(더 이상 merge 불가능)
Check in vocabulary
위에서 찾은 쌍들이 vocabulary에 있는지 확인해야 합니다. 만약 vocabulary에 없는 경우
<unk>토큰을 부여합니다.Vocabulary :
h,u,g,p,n,b,s,ug,un,hugpug➡️p,u,g➡️pu,ug➡️p,ug➡️p,ugbug➡️b,u,g➡️bu,ug➡️b,ug➡️b,ugmug➡️m,u,g➡️mu,ug➡️m,ug➡️<unk>,ug