BPE(Byte Pair Encoding) 알고리즘

글자 단위에서 점진적으로 서브워드 어휘집을 만들어내는 BPE(Byte Pair Encoding) 알고리즘

 

 

BPE(Byte Pair Encoding)는 텍스트를 서브워드 단위로 분할하는 토크나이저(Tokenization) 알고리즘이다.

BPE는 기존의 고정된 어휘 사전(Vocabulary)을 사용하는 토크나이저와는 달리, 데이터에 기반하여 동적으로 서브워드 단위로 텍스트를 분할한다. BPE 알고리즘은 가장 빈번하게 등장하는 문자열의 쌍을 합치고, 이를 반복하여 언어의 특성을 고려한 서브워드 분할을 수행한다.

BPE는 자연어 처리에서 널리 사용되며 기계 번역, 문장 분류, 개체명 인식 등 다양한 작업에 적용된다. BPE 토크나이저는 단어의 일부가 아닌 의미 있는 서브워드 단위로 텍스트를 분할하기 때문에 희귀한 단어나 희소성을 감소시킬 수 있어 효과적인 토크나이저로 알려져 있다.

 

{"low": 5, "lower": 2, "newest": 6, "widest": 3} *숫자는 코퍼스 내 등장한 빈도수

기존의 단어 토큰화 시, 만약 "lowest"라는 단어가 등장한다면 OOV(Out-of-Vocabulary) 문제가 발생한다.

 

BPE(Byte Pair Encoding) 알고리즘을 적용하면

1. 빈도수에 따라 정리된 dictionary 내 모든 단어들을 글자 단위로 분리한다.

   - dictionary: {"low": 5, "lower": 2, "newest": 6, "widest": 3}

   - vocabulary: l, o, w, e, r, n, s, t, i, d

 

2. vocabulary에서 가장 빈도수가 높은 쌍을 하나의 집합으로 통합한다.

   -  vocabulary: l, o, w, e, r, n, s, t, i, d, es *업데이트

   - 이 과정을 여러 회차 반복한다.

.

.

.

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

 

3. vocabulary에서 "lowest"를 조합할 수 있게 된다. OOV 문제를 해결!

 

import re, collections

# 쌍(pair) 빈도 계산
def get_freq(dictionary):
  pairs = collections.defaultdict(int)
  for word, freq in dictionary.items(): # 키(word 변수)-값(freq 변수) 쌍(pair) 반환
    symbols = word.split()
    for i in range(len(symbols)-1):
      pairs[symbols[i], symbols[i+1]] += freq
  
  print('현재 pair들의 빈도수: ', dict(pairs))
  return pairs

# 어휘 사전 업데이트
def merge_dictionary(target_pair, input_dict):
  output_dict = {}
  bigram = re.escape(' '.join(target_pair))
  p = re.compile(r'(?<!\S)' + bigram + r'(?!\S)') # 공백 아닌 문자열의 앞에 오는 경우, 뒤에 오는 경우
  for word in input_dict:
    w_out = p.sub(''.join(target_pair), word)
    output_dict[w_out] = input_dict[word]
  return output_dict

dictionary = {'l o w' : 5, 'l o w e r' : 2, 'n e w e s t' : 6, 'w i d e s t' : 3}
vocab = ["l", "o", "w", "e", "r", "n", "s", "t", "i", "d"]

num_merges = 10
for i in range(num_merges):
  print(f"{i+1}번째 BPE")
  pairs = get_freq(dictionary)
  best = max(pairs, key=pairs.get)
  dictionary = merge_dictionary(best, dictionary)
  vocab.append("".join(best))

  print(f"new merge: {best}")
  print(f"dictionary: {dictionary}")
  print(f"vocabulary: {vocab}")

출력 결과:

 

1. get_freq 함수는 쌍(pair)의 빈도를 계산한다.

- 주어진 사전(dictionary)의 각 단어의 쌍(pair)를 계산한다.

- 단어 사전의 각 단어를 공백을 기준으로 분리한 뒤, 연속된 단어 쌍을 찾아 빈도수를 계산한다.

- 마지막 요소 다음에는 더 이상 다음 요소가 없기 때문에 쌍을 더 계산할 필요가 없으므로 -1을 해준다.
- 계산된 쌍의 빈도를 출력하고 반환한다.

2. merge_dictionary 함수는 어휘 사전을 업데이트한다.

- 주어진 쌍을 사용하여 어휘 사전을 업데이트한다.

- 정규표현식을 사용하여 타겟 쌍을 찾아 업데이트한다.

- 업데이트된 어휘 사전을 반환한다.

 

3. num_merges 횟수 만큼 BPE 알고리즘을 반복한다.