Tokenization

문장에서 의미있는 단위로 나누는 작업을 토큰화라고 한다.

• 문자 단위 토큰화
  • 문자 단위로 토큰화를 하는 것이다.
  • 한글 음절 수는 모두 11,172개이므로 알파벳, 숫자, 기호 등을 고려한다고 해도 단어 사전의 크기는 기껏해야 15,000개를 넘기 어렵다.
  • 장점 : 모든 문자를 포함시켜서 UNK토큰이 잘 발생하지 않는다.
  • 단점 : 의미 있는 단위가 되기 어렵고, 상대적으로 시퀀스가 길어진다.

어제 카페 갔었어 > 어, 제, 카, 페, 갔, 었, 어
어제 카페 갔었는데요 > 어, 제, 카, 페, 갔, 었, 는, 데, 요

• 단어 단위 토큰화
  • 단어 단위로 토큰화를 하는 것이다.
  • 장점 : 공백으로 쉽게 분리할 수 있다.
  • 단점 : 모든 단어들을 다 포함시키기에는 단어 사전의 크기가 상당히 크다. 이는 메모리 문제를 야기!

어제 카페 갔었어 > 어제, 카페, 갔었어
어제 카페 갔었는데요 > 어제, 카페, 갔었는데요

• 서브워드 단위 토큰화
  • 문자 단위와 단어 단위 토큰화의 중간에 있는 형태이다.
  • “자주 등장한 단어는 그대로 두고, 자주 등장하지 않은 단어는 의미있는 서브 워드 토큰들로 분절한다” 라는 원칙에 기반을 둔 알고리즘
  • 단어 사전의 크기를 지나치게 늘리지 않으면서도 UNK 문제를 해결할 수 있다.
  • 희귀 단어, 신조어와 같은 문제를 완화시킬 수 있다.

서브워드 기반 토크나이저

BPE(Byte-Pair Encoding)

• BPE(Byte pair encoding) 알고리즘은 1994년에 제안된 데이터 압축 알고리즘
• 연속적으로 가장 많이 등장한 글자의 쌍을 찾아서 하나의 글자로 병합하는 방식을 수행

aaabdaaabac    # 가장 자주 등장하고 있는 바이트의 쌍(byte pair)은 'aa' , Z=aa
ZabdZabac      # Y=ab
ZYdZYac        # X=ZY
XdXac          # 더 이상 병합할 바이트의 쌍이 없으므로 최종 결과로 하여 종료

자연어 처리에서의 BPE

• 글자(charcter) 단위에서 점차적으로 단어 집합(vocabulary)을 만들어 내는 Bottom up 방식의 접근을 사용

• BPE는 일반적으로 훈련 데이터를 단어 단위로 분절하는 Pre-tokenize 과정을 거쳐야한다.

• Pre-tokenize는 공백 단위나 규칙 기반으로 수행될 수 있다.

• Example)
  ('hug', 10), ('pug', 5), ('pun', 12), ('bun', 4), ('hugs', 5)

  Pre-tokenize를 거쳐서 나온 단어들이라 하고 여기서 정수 값은 각 단어가 얼마나 등장했는지를 나타내는 값이다.
  이때 기본 사전은 [‘b’, ‘g’, ‘h’, ‘n’, ‘p’, ‘s’, ‘u’] 이다.
  기본 사전을 기반으로 단어들을 쪼개면 다음과 같다.

  ('h' 'u' 'g', 10), ('p' 'u' 'g', 5), ('p' 'u' 'n', 12), ('b' 'u' 'n', 4), ('h' 'u' 'g' 's', 5)
  “hu”는 총 15번, “ug”는 총 20번이 나와 가장 많이 등장한 쌍은 “ug”가 되고 “u”와 “g”를 합친 “ug”를 사전에 새로 추가한다.
  그럼 이때 기본 사전은 [‘b’, ‘g’, ‘h’, ‘n’, ‘p’, ‘s’, ‘u’, ‘ug’] 이다.

  ('h' 'ug', 10), ('p' 'ug', 5), ('p' 'u' 'n', 12), ('b' 'u' 'n', 4), ('h' 'ug' 's', 5)
  또 가장 많이 나온 쌍은 16번 등장한 “un”이므로, “un”을 사전에 추가한다. 그 다음은 15번 등장한 “hug”이므로 “hug”도 사전에 추가한다.

  ('hug', 10), ('p' 'ug', 5), ('p' 'un', 12), ('b' 'un', 4), ('hug' 's', 5)
  기본 사전은 [‘b’, ‘g’, ‘h’, ‘n’, ‘p’, ‘s’, ‘u’, ‘ug’, ‘un’, ‘hug’]가 됩니다. 이렇게 처음에는 글자 단위였던 것이 의미있는 서브워드 토큰들로 분절할 수 있다.

• Byte-level BPE(BBPE)

• GPT-2 논문에서 바이트를 사전의 기본 단위로 사용하는 트릭을 사용

• GPT-2 모델은 256개의 기본 바이트 토큰과 <end-of-text> 토큰 그리고 50,000 개의 서브 워드를 더해 총 50,257 개의 단어 집합(vocabulary)을 가진다.

• 256 바이트셋으로 모든 텍스트를 표현할 수 있다.

• UNK 문제없이 모든 텍스트를 분절할 수 있다.

• multilingual일 때, 언어들 사이에서 vocabulary 공유를 가장 많이 한다.

WordPiece

• BERT에서 활용된 서브 워드 토크나이저 알고리즘
• BPE와 마찬가지로 사전을 코퍼스 내 등장한 캐릭터들로 초기화 한 후, 사용자가 지정한 횟수 만큼 서브 워드를 병합하는 방식으로 훈련
• 하지만 WordPiece는 BPE와 같이 가장 많이 등장한 쌍을 병합하는 것이 아니라, 병합되었을 때 코퍼스의 Likelihood를 가장 높이는 쌍을 병합하게 된다.
• 즉, WordPiece에서는 코퍼스 내에서 “ug”가 등장할 확률을 “u”와 “g”가 각각 등장할 확률을 곱한 값으로 나눈 값이 다른 쌍보다 클 경우 해당 쌍을 병합하게 된다.

또 이 학생의 집에서 병든 소를 도축했던 35살 남성도 탄저병에 걸린 것으로 확인됐습니다.

['또', '이', '학생', '##의', '집', '##에', '##서', '병든', '소', '##를', '도축', '##했', '##던', '35', '##살', '남성', '##도', '탄', '##저', '##병', '##에', '걸린', '것', '##으로', '확인', '##됐', '##습', '##니다', '.']

Unigram

• 서브 워드에서 시작해 점차 사전을 줄여나가는 top-down 방식으로 진행
• 매 스텝마다 Unigram은 주어진 코퍼스와 현재 사전에 대한 Loss를 측정한다.
• 또한 각각의 서브 워드에 대해 해당 서브 워드가 코퍼스에서 제거되었을 때, Loss가 얼마나 증가하는지를 측정하여 Loss를 가장 조금 증가시키는 p 개 토큰을 제거한다. (p는 보통 전체 사전 크기의 10-20% 값으로 설정)
• 해당 과정을 사용자가 원하는 사전 크기를 지니게 될 때 까지 반복하게 되고, 기본 캐릭터들은 반드시 사전에서 제거되지 않고 유지되어야한다.
• 매번 같은 토큰 리스트를 반환하는 BPE, WordPiece와 달리 Unigram은 다양한 토큰 리스트가 생길 수 있다.

SentencePiece

• 지금까지 살펴본 모든 방법들은 공백을 기준으로 단어를 분절할 수 없기 때문에 Pre-tokenize 과정을 필요로 했다.

• 하지만 sentencepiece는 공백을 기준으로 단어를 분절할 수 있기 때문에 Pre-tokenize 과정이 필요없다.

• 또한 디코딩 과정에서 모든 토큰들을 붙여준 후, 메타스페이스(”▁”)만 공백으로 바꿔주면 되기 때문에 원상복구가 가능하다는 특징이 있다.

• BPE 혹은 Unigram을 적용하여 사전을 구축하게 된다.

또 이 학생의 집에서 병든 소를 도축했던 35살 남성도 탄저병에 걸린 것으로 확인됐습니다.

['▁또', '▁이', '▁학생', '의', '▁집에서', '▁병', '든', '▁소', '를', '▁', '도', '축', '했던', '▁35', '살', '▁남성', '도', '▁탄', '저', '병', '에', '▁걸린', '▁것으로', '▁확인', '됐', '습니다', '.']

Reference

• https://wikidocs.net/22592
• https://huggingface.co/transformers/master/tokenizer_summary.html
• https://karter.io/huggingface
• https://ratsgo.github.io/nlpbook/docs/preprocess/bpe/
• https://arxiv.org/pdf/1508.07909.pdf