subword tokenization

기계에 단어를 학습시킬때 갑자기 기계가 학습한적 없던 단어가 나타난다면 학습이나 정답 도출이 어려울 것이다.

학습한 단어 집합에 없는 단어는 OOV(out of vocabulary)라고 하는데, 이런 경우를 해결하기 위해

subword tokenization이라는 방법론이 생겼다.

 

어떤 단어를 더 작은 단어로 분리해서 인코딩 하고 임베딩하겠다는 것인데,

예를 들면 annoyingly라는 단어가 잘 등장하지 않는다면 궂이 이 단어를 그냥 쓰는게 아니라,

더 자주 등장하는 annoying과 ly로 뜯어서 정리해 두는것이다.

이렇게 하면 몇번 등장하지 않는 단어때문에 사전이 엄청나게 커질 필요도 없고,

OOV나 잘쓰이지 않는 단어, 새롭게 생긴 단어등에 대응하기가 더 쉬워진다.

이는 영어든, 한국어에든, 일본어에든 의미있는 방법이다.

 

# BPE(Byte Pair Encoding) 알고리즘(arxiv.org/abs/1508.07909)

원래는 1994년에 제안된 데이터 압축 알고리즘인데, 자세한 작동방법은 아래와 같다.

aaabdaaabac

문자열에서 aa 라는 글자쌍이 가장 자주 등장하므로 이를 Z로 바꾼다.

 

ZabdZabac

Z=aa

문자열에서 ab라는 글자쌍이 가장 자주 등장하므로 이를 Y로 바꾼다.

 

ZYdZYacY=abZ=aa문자열에서 ZY라는 글자쌍이 가장 자주 등장하므로 이를 X로 바꾼다.

 

XdXacX=ZYY=abZ=aa이제 더 이상 2번 이상 등장하는 문자열은 없다.

 

# BPE 알고리즘을 자연어 처리에 어떻게 적용할 것인가

데이터로부터 다음과 같이 단어의 빈도수를 체크했다고 하자.

low : 5, lower : 2, newest : 6, widest : 3

low, lower, newest, widest

 

bpe 알고리즘은 사용자가 동작횟수를 결정하는데 여기서는 10이라고 하자

일단 1회로 가장 빈도수가 높은 e s를 es로 합치고 단어목록에 추가한다.

l o w : 5, l o w e r : 2, n e w es t : 6, w i d es t : 3

l, o, w, e, r, n, w, s, t, i, d, es

 

2회로 es t가 빈도수가 높으므로 est로 합치고 단어목록에 추가한다.

l o w : 5,

l o w e r : 2,

n e w est : 6,

w i d est : 3

l, o, w, e, r, n, w, s, t, i, d, es, est

 

3회로 l o가 빈도수가 높으므로 lo로 합치고 단어목록에 추가한다.

lo w : 5,

lo w e r : 2,

n e w est : 6,

w i d est : 3

l, o, w, e, r, n, w, s, t, i, d, es, est, lo

 

10회까지 진행하면 아래와 같이 된다.

low : 5,

low e r : 2,

newest : 6,

widest : 3

l, o, w, e, r, n, w, s, t, i, d, es, est, lo, low, ne, new, newest, wi, wid, widest

 

테스트 과정에서 lowest가 등장하면 단어목록에 없는 단어이기 때문에 OOV가 되었겠지만,

low와 est가 단어목록에 있어서 lowest는 low와 est로 뜯어져서 인코딩 된다.

즉, BPE를 적용하지 않았다면 lowest가 l o w e s t 로 뜯어져서 인코딩되었겠지만,

BPE가 적용되어 low est로 뜯어져서 인코딩되는것이다.

 

같은 방식으로 loki라는 단어가 들어오면 lo k i이렇게 3개로 뜯어져서 인코딩된다.

정말로 아무 서브워드도 존재하지 않는다면 어쩔수 없이 모두 뜯을수 밖에없다.

highing라는 단어는 h i g h i n g이라는 단어로 뜯어져서 인코딩 되는 것이다.

 

# wordpiece model(static.googleusercontent.com/media/research.google.com/ja//pubs/archive/37842.pdf)

언어모델에서 유니그램 모델은 각 단어가 몇번 등장했는지에 대한 횟수를 전체 단어수로 나누어서 학습해둔다.

text	0.2
mining	0.1
association	0.01
clustering	0.02
…	…
food	0.00001
total	1

만약 예를 들어서 위와같이 likelihood가 학습이 되었다면,

등장하는 text mining clustering이 동시에 등장하는 확률은 다음과 같다.

즉, 학습해놓은 데이터에 따라서 likelihood는 바뀔 수 있다.

wordpiece model은 BPE의 변형 알고리즘인데, BPE는 빈도수인데 반해,

WPM은 likelihood를 가장 높이는 쌍을 병합한다.

예를 들어, 위에서 es라는 단어가 등장할 확률 / ( e가 등장할 확률 * g가 등장할 확률)이 다른 쌍보다 높은 경우,

합병하게 되는 것이다.

즉, 병합하기 전에 병합할 가치가 충분한지 판단한 다음에 병합을 하는 것이다.

WPM에서는 원래 단어의 앞부분에 _를 붙인채로 띄어쓰리고 분리한다.

예를 들면, 아래 문장은 다음과 같이 분리해낼 수 있다.

Jet makers feud over seat width with big orders at stake

_J et _makers _fe ud _over _seat _width _with _big _orders _at _stake

 

기존 값을 복원해 내는 디코딩때는 띄어쓰기를 모두 없애고 _를 띄어쓰기로 바꾸기만 하면된다.

 

# unigram(arxiv.org/pdf/1804.10959.pdf)

앞의 두 방법이 모두 서브워드를 만들어 나간다면,

유니그램은 모든 서브워드에서 시작해서 사전에서 줄여나가는 방식이다.

코퍼스와 현재 사전에 대한 loss를 구한 다음에,

각각의 서브워드가 코퍼스에서 제거된다면 loss가 얼마나 증가하는지 측정하고,

loss를 가장 조금 증가시키는 10~20%의 서브워드를 제거한다.

즉, 사용자가 원하는 사전크기가 될때까지 반복된다.

다만, 이렇게 제거되더라도 기본 글자들은 사전에서 삭제되지 않고 유지된다.

예를 들어, ['b', 'g', 'h', 'n', 'p', 's', 'u', 'ug', 'un', 'hug'] 라는 사전을 얻게 되었을때,

hugs라는 단어는 ['hug', 's'], ['h', 'ug', 's'], ['h', 'u', 'g', 's'] 세가지 방법으로 뜯을 수 있다.

사전이 구축될때는 확률값도 저장되므로 세가지 모두 조합의 확률을 구할 수 있다.

이 중에 가장 높은 확률을 가지는 것으로 뜯어내면 되는 것이다.

 

# sentence piece(arxiv.org/pdf/1808.06226.pdf)

위에서의 방법들은 공백을 기준으로 단어를 뜯어내는데,

띄어쓰기가 없거나 띄어쓰기만으로 단어를 구분할 수 없는 경우가 언어마다 다르다.

sentence piece에서는 문장을 로우스트림으로 인식해서 공백을 포함한 모든 글자들에 대해서 BPE, WPM 또는 Unigram을 적용하는것이다.

 

# 참고

ai-information.blogspot.com/2019/02/word-piece-embedding.html

Word Piece Embedding

wikidocs.net/22592

위키독스

huffon.github.io/2020/07/05/tokenizers/

HuggingFace 내 토크나이저 종류 살펴보기 - Programador | Huffon Blog

ratsgo.github.io/from%20frequency%20to%20semantics/2017/09/16/LM/

언어모델(Language Model) · ratsgo's blog