算法工程师面试之BPE算法

╰半橙微兮° 2022-08-29 15:53 18阅读 0赞

# 前言 #

*  文章来源：LawsonAbs（CSDN）
 *  如果需要快速掌握，请跳至 3.实例 部分

--------------------

# 1. 简介 #

BPE是`Byte-Pair Encoding`的缩写。在NLP中的应用，主要就是为了词分割，即将一个单词tokenize 的过程。我们都知道在处理NLP问题时，有时候模型碰到的词没有出现在词表中，这就是常说的`OOV` 问题，那么该怎么解决这种问题呢？于是伟大的先行者们就尝试使用subword （就是将一个单词分割成多个段）的方式来解决这个问题。本文要介绍到的BPE算法就属于一种 subword 方法。

# 2. 思想 #

主要思想就是：  
挑选语料库中出现频率最高的两个字符串对（byte-pair），用二者的组合不断地替换原来空格分割的两个字符串，更新该word。循环这个步骤k次，得到一个目标词表（使用这个目标词表处理后面遇到的数据）。  
这里详细讲解一下BPE算法的实现过程。  
先看一下该算法的输入：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdTE2NjU5_size_16_color_FFFFFF_t_70]  
初读上面这句话，一直不理解，其实上面这句话的意思说的是：

> BPE算法通常运行在词内部（不合并跨词的边界），所以输入语料首先是一个空格分割的一组字符串【比如上面的`l o w _`】，每组字符都对应一个词，加上词尾标志`_`，以及这个单词出现的次数。

根据上面这句话，我们结合上面这个示例给出一个解释：

<table> 
 <thead> 
  <tr> 
   <th>单词出现的次数</th> 
   <th>用空格分割得到的字符串</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>l o w _</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>l o w e s t _</td> 
  </tr> 
 </tbody> 
</table>

…  
这里的 vocabulary 其实就是一个起初tokenize 会使用的基本单位，但是会随着算法的深入而逐渐更新（主要是往其中不断地添加新的字符串）

*  step 1. 依次统计相邻两个字符的出现的频率，并将出现字符频率最高的两个字符串替换成某个字符串，并将得到的字符串放入到`vocabulary` 中
 *  step 2.重复执行上一步，直到循环k次
 *  step 3.根据迭代得到的vocabulary，将单词替换掉

# 3.示例 #

下面就以：

<table> 
 <thead> 
  <tr> 
   <th>单词出现的次数</th> 
   <th>单词</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>l o w _</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>l o w e s t _</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>n e w e r _</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>w i n d e r _</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>n e w _</td> 
  </tr> 
 </tbody> 
</table>

为例，逐步分析BPE算法运行的过程，其中`vocabulary = l o w e s t n r i d _`

*  iterate = 1: e r 连续出现的次数最高，为6+3=9次，所以就将二者替换成er，并将`er`放入到 vocabulary 中  
    那么得到的结果就是:

<table> 
 <thead> 
  <tr> 
   <th>单词出现的次数</th> 
   <th>单词</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>l o w _</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>l o w e s t _</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>n e w er _</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>w i n d er _</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>n e w _</td> 
  </tr> 
 </tbody> 
</table>

`vocabulary = l o w e s t n r i d _ er`

*  iterate = 2：接着发现`er _` 出现的次数最高，替换，并将 `er_`放入到词表中，得到`vocabulary = l o w e s t n r i d _ er er_`

<table> 
 <thead> 
  <tr> 
   <th>单词出现的次数</th> 
   <th>单词</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>l o w _</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>l o w e s t _</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>n e w er_</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>w i n d er_</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>n e w _</td> 
  </tr> 
 </tbody> 
</table>

*  iterate = 3：接着发现`n e` 连续出现的频率最高，再次替换，更新`vocabulary = l o w e s t n r i d _ er er_ ne`

<table> 
 <thead> 
  <tr> 
   <th>单词出现的次数</th> 
   <th>单词</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>l o w _</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>l o w e s t _</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>ne w er_</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>w i n d er_</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>ne w _</td> 
  </tr> 
 </tbody> 
</table>

*  iterate = 4：接着发现 `ne w` 出现的次数最高，再次替换，更新`vocabulary = l o w e s t n r i d _ er er_ ne new`

<table> 
 <thead> 
  <tr> 
   <th>单词出现的次数</th> 
   <th>单词</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>l o w _</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>l o w e s t _</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>new er_</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>w i n d er_</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>new _</td> 
  </tr> 
 </tbody> 
</table>

*  iterate = 5: 接着发现 `l o` 出现的次数最高，再次替换，更新`vocabulary = l o w e s t n r i d _ er er_ ne new lo`

<table> 
 <thead> 
  <tr> 
   <th>单词出现的次数</th> 
   <th>单词</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>lo w _</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>lo w e s t _</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>new er_</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>w i n d er_</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>new _</td> 
  </tr> 
 </tbody> 
</table>

*  iterate = 6: 接着发现`lo w`的频率最高，替换，更新`vocabulary = l o w e s t n r i d _ er er_ ne new lo low`

<table> 
 <thead> 
  <tr> 
   <th>单词出现的次数</th> 
   <th>单词</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>low _</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>low e s t _</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>new er_</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>w i n d er_</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>new _</td> 
  </tr> 
 </tbody> 
</table>

*  iterate = 7: 接着发现`new er_`的频率最高【出现了6次】，替换，更新`vocabulary = l o w e s t n r i d _ er er_ ne new lo low newer_`

<table> 
 <thead> 
  <tr> 
   <th>单词出现的次数</th> 
   <th>单词</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>low _</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>low e s t _</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>newer_</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>w i n d er_</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>new _</td> 
  </tr> 
 </tbody> 
</table>

*  iterate = 8: 接着发现`low _`的频率最高，替换，更新`vocabulary = l o w e s t n r i d _ er er_ ne new lo low newer_ low_`

<table> 
 <thead> 
  <tr> 
   <th>单词出现的次数</th> 
   <th>单词</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>low_</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>low e s t _</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>newer_</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>w i n d er_</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>new _</td> 
  </tr> 
 </tbody> 
</table>

…  
迭代指定的次数k（即算法的超参数），算法结束。

下面我们使用得到的vocabulary处理 `newer_`这个单词，首先需要将`newer_` => `n e w e r _`。然后发现vocabulary中依次出现`er er_ ne new newer_` 那么最后tokenize得到的结果就是 `newer_` ；同理处理`lower_` => `l o w e r _`。根据vocabulary 中的`er er_ lo low`，那么最后得到的结果就是： `low er_`

# 4.参考资料 #

*  讲解BPE算法的资料，这个资料是斯坦福大学的`Speech and Language Processing`：https://web.stanford.edu/~jurafsky/slp3/2.pdf

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdTE2NjU5_size_16_color_FFFFFF_t_70]: /images/20220829/c310ea3acd894b24941722765ebc4a62.png