本文由 「AI前线」原创，原文链接：基于深度学习技术的AI输入法引擎
作者｜ 姚从磊
编辑｜Emily、Debra
AI 前线导读：”目前，几乎所有的输入法基本能实现在用户输入第一个字后预测用户接下来输入的文字，并进行推荐。AI 在输入法中的应用，能够通过大量的语言、语义的学习，了解人的用语习惯，甚至是性格和思维。
当输入法可以更加准确地了解用户之后，机器与人类之间的交流的以加深，人机交互的体验得以提升，进而提高用户粘度。输入法引擎 AI 化已成为输入法产品发展的趋势。
Kika 早在 2014 年就推出了首款输入法产品 Kika Keyboard，在海外进入了 140 多个国家，支持 173 种语言，全球用户数量达 4 亿，月活 6000 多万，这与此产品背后的输入法引擎有着密不可分的联系。
以下内容整理自 AI 前线 2018 年 1 月 25 日社群分享
各位好，我是姚从磊，非常高兴能够有这样一个跟大家交流的机会。今天主要想为大家介绍一下手机输入法最核心的模块 - 输入法引擎的技术方案，为什么以及如何从传统 N-gram 引擎演化到深度神经网络引擎的。
主要的内容分为五个部分：
- 什么是输入法引擎；
- 基于传统 N-gram 语言模型的输入法引擎；
- 为什么要转向深度神经网络引擎；
- 深度神经网络输入法引擎的那些坑；
- 高级预测功能。
先用一张图介绍一下我们公司的情况。
作为一家面向全球用户提供 173 种语言输入法的公司，Kika 利用 AI 技术，为用户提供了一流的输入体验，也在全球获得了大量的用户。
这张图中列出了目前全球输入法市场上用户量较大的产品，背后的公司既包括 Kika、百度、搜狗、Go 以及触宝这样国内的公司，也包括 Google(产品为 GBoard)、微软 (Swiftkey) 等国外大公司。大家都在输入法引擎的核心技术上投入大量研发精力，期望为全球各国用户提供一流的输入体验。
什么是输入法引擎
输入法 (Input Method，简称 IME) 是最常用的工具软件之一，也常被称为 Keyboard、键盘等。对每种语言，输入法会提供一个字母布局 (Layout)，上面按照用户习惯将对应语言的基础字母放置在合适的位置，比如英文键盘的 QWERT、汉语键盘的九宫格等。用户输入文字其实就是按照顺序来敲击 Layout 上的字母，字母敲击序列称为键码序列；在用户敲击字母的过程中，键码序列以及之前用户输入的词会被传入 Layout 下层的「输入法引擎」，引擎会根据从大规模数据中训练得到的语言模型，来预测用户当前以及接下来可能输入的词 / 词序列，并将最可能输入的词 / 词序列在键盘的候选区上展示给用户，供用户选择。
例如，如果一位用户期望输入的完整文本内容为「What’s the weather today？」，当前输入到了「weather」的第三个字母「a」，此时词序列「What’s the 」和键码序列「W h a t ’ s SPACE t h e SAPCE w e a」(SPACE 表示空格) 作为输入传送至输入法引擎，引擎基于训练好的语言模型进行预测，并将最有可能的候选词「weather」、「weapon」等展示给用户，供用户选择。在这个 case 中，如果「weather」排在第一位，则可以认为引擎是合格的，可以打 60 分。如果仅输入到「weather」的第一个字母「w」，就可以将「weather」排在第一位，则可以打 70 分。如果在输入到「weather」的第一个字母「w」后，就可以直接预测用户接下来要输入的词序列为「weather today?」，那就会更好，可以认为是 90 分。
总的来讲，输入法引擎的功能可以细分为「纠错」、「补全」和「预测」三类。
- 所谓纠错，指的是在用户输入一个错误的词，比如「westher」，会自动建议改为「weather」；
- 所谓补全，指的是输入一个词的一部分即预测整体，比如「w」预测「weather」；
- 所谓「预测」，指的是用户没有输入任何字母时直接预测用户接下来会输入什么，比如输入「What’s the 」，预测出用户会输入「weather today?」。
同时，在拉丁等语系的输入法中，会提供滑行输入的功能。
用户在键盘上快速滑行词的字母序列，即便滑行轨迹有所偏差（因为滑行速度很快，用户较难准确定位各个字母的位置），也可以准确预测用户所想输入的词。在滑行输入中，引擎的输入是滑行点的轨迹，输出是预测的词。在本文中，我们不会深入探讨滑行输入的引擎实现逻辑。
更进一步，随着用户越来越多地倾向于利用 Emoji、表情图片等非文字内容表达自己的情感，引擎也需要能够根据用户输入词 / 键码序列来预测 Emoji 或表情图片。而 Emoji 往往具有多义性（表情图片也类似），此类预测的复杂度会更高，我们已经利用基于深度学习的建模技术较好地解决了这一问题。本文不会深入探讨，有兴趣的小伙伴可以单独谈讨。
本文主要讨论在手机的按键文本输入场景下，输入法引擎高效准确地预测的相关技术。
此类技术的演化可以分两个阶段：
1）N-gram 统计语言模型阶段；
2）深度神经网络语言模型阶段。
前者主要基于大规模语料进行统计，获取一个词在 N-1 个词组成的序列 (N-gram) 之后紧邻出现的条件概率；但由于手机内存和 CPU 的限制，仅能对 N 较小 (N <= 3) 的 N-gram 进行计算，预测效果存在明显天花板。后者通过构建深度神经网络，利用大规模语料数据集进行训练，不仅可以突破 N-gram 中 N 的限制，且可利用词与词的语义关系，准确预测在训练语料中未出现的词序列，达到远超统计语言模型的预测效果。
基于传统 N-gram 语言模型的输入法引擎
在输入「What’s the weather today？」的这个 case 中，当用户输入到「weather」的第一个字母「w」时，引擎要做的事情，就是根据前面输入的词序列「What’s the」来预测下一个最可能的以「w」打头的单词，而其中最关键的就是如何预测下一个最可能的词。
假设输入词序列为 w1,⋯,wN-1，预测下一个词的问题实际上变成了 argmaxWNP(WN |w1,⋯,wN-1 )，这个简单的模型称为输入法引擎的语言模型。
根据条件概率计算公式，P(WN |w1,⋯,wN-1 )=P(w1,⋯,wN-1, WN )/P(w1,⋯,wN-1, WN )，，根据最大似然估计原则，只有在语料数据规模足够大以至于具备统计意义时，上述概率计算才会具有意义。
但事实上，如果 N 值过大，并不存在「足够大」的语料数据可以支撑所有概率值的计算；并且，由于 WN 实际上仅同 w1,⋯,wN-1 中的部分词相关，上述计算会造成大量的计算资源浪费。
因此，实际计算中，一种方式是引入马尔科夫假设：当前词出现的概率只与它前面有限的几个词有关，来简化计算。如果当前词出现的概率只与它前面的 N-1 个词相关，我们就称得到的语言模型为 N-gram 模型。常用的 N-gram 模型有 Unigram (N=1)，Bigram (N=2)，Trigram (N=3)。显然，随着 N 的增大，语言模型的信息量会指数级增加。
为了得到有效的 N-gram 语言模型，一方面需要确保语料数据规模足够大且有统计意义，另一方面也需要处理「数据稀疏」问题。所谓数据稀疏，指的是词序列 w1,⋯,wN 并没有在语料数据中出现，所以导致条件概率 P(WN |w1,⋯,wN-1 ) 为 0 的情况出现。这显然是不合理的，如果数据规模继续扩大，这些词序列可能就会出现。我们可以引入平滑技术来解决数据稀疏问题。平滑技术通过把在训练语料集中出现过的 N-gram 概率适当减小，而把未出现的概率适当增大，使得全部的 N-gram 概率之和为 1，且全部的 N-gram 概率都不为 0。经典的平滑算法有很多种，个人推荐 Laplace 平滑和 Good-Turing 平滑技术。
在利用 N-gram 语言模型完成下一个词的预测后，还需要根据用户的按键序列来对预测的结果进行调整，可以利用编辑距离等衡量序列相似度的方法，将按键序列同预测词的字母序列进行对比，细节不再赘述。
利用 N-gram 语言模型构建的输入法引擎，在手机端运行时，存在着如下问题：
- 不能充分利用词序列信息进行预测：受制于手机有限的 CPU 和内存资源，N-gram 中的 N 通常都不能太大，基本上 N 为 3 已经是极限。这意味着只能根据最近的 1 到 2 个词来进行预测，会丢失大量的关键信息；
- 不能准确预测语料数据集中未出现的单词序列。例如，如果在语料数据中出现过「go to work」，而没有出现过「go to school」。即使用户输入「A parents guide to go to s」，引擎也不能准确地将「school」排在候选区靠前的位置。
上述问题，利用深度神经网络技术可以很好地解决。
为什么要转向深度神经网络引擎
深度神经网络 (Neep Neural Networks, DNN) 是一种具备至少一个隐层的神经网络，通过调整神经元的连接方式以及网络的层数，可以提供任意复杂度的非线性模型建模能力。基于强大的非线性建模能力，深度神经网络已经在图像识别、语音识别、机器翻译等领域取得了突破性的进展，并正在自然语言处理、内容推荐等领域得到广泛的应用。
典型的深度神经网络技术有卷积神经网络 (Convolutional Neural Networks, CNN) 、递归神经网络 (Recurrent Neural Network，RNN) 、生成对抗网络 (Generative Adversarial Nets, GAN) 等，分别适用于不同的应用场景。其中，RNN（如图 1 所示）特别适合序列到序列的预测场
图1：RNN网络结构
传统的神经网络中层与层之间是全连接的，但层间的神经元是没有连接的（其实是假设各个数据之间是独立的），这种结构不善于处理序列化预测的问题。在输入法引擎的场景中，下一个词往往与前面的词序列是密切相关的。RNN 通过添加跨越时序的自连接隐藏层，对序列关系进行建模；也就是说，前一个状态隐藏层的反馈，不仅仅作为本状态的输出，而且还进入下一状态隐层中作为输入，这样的网络可以打破独立假设，得以刻画序列相关性。
RNN 的优点是可以考虑足够长的输入词序列信息，每一个输入词状态的信息可以作为下一个状态的输入发挥作用，但这些信息不一定都是有用的，需要过滤以准确使用。为了实现这个目标，我们使用长短期记忆网络 (Long-Short Memory Networks, LSTM) 对数据进行建模，以实现更准确的预测。
LSTM（图 2）是一种特殊的 RNN，能够有选择性地学习长期的依赖关系。 LSTM 也具有 RNN 链结构，但具有不同的网络结构。在 LSTM 中，每个单元都有三个门（输入门，输出门和遗忘门）来控制哪部分信息应该被考虑进行预测。利用 LSTM，不仅可以考虑更长的输入序列，并且可以利用三种门的参数训练来自动学习筛选出真正对于预测有价值的输入词，而非同等对待整个序列中所有的词。
图 2 LSTM 网络结构
并且，可以在 LSTM 的网络结构中添加嵌入层 (Word Embedding Layer) 来将词与词的语义关系加入到训练和预测过程中。通过 Word Embedding，虽然在语料数据中没有出现过「go to school」，但是因为「go to work」出现在语料库中，而通过 Word Embedding 可以发现「work」和「school」具有强烈的语义关联；这样，当用户输入「A parents guide to go to s」时，引擎会根据「work」和「school」的语义关联，以及 LSTM 中学习到的「parents」同「school」间存在的预测关系，而准确地向用户推荐「school」，而非「swimming」。
深度神经网络输入法引擎的那些坑
从理论上来讲，LSTM 可以完美解决 N-gram 语言模型的问题：不仅能够充分利用词序列信息进行预测，还可以准确预测语料数据集中未出现的单词序列。但是，在实际利用 LSTM 技术实现在手机上可以准确流畅运行的输入法引擎时，在云端和客户端都存在一些坑需要解决。
在云端，有两个问题需要重点解决：
充分利用词序列和键码序列信息。如前所述，在输入法引擎的预测过程中，LSTM 的输入包含词序列和键码序列两类不同的序列信息，需要设计一个完备的 LSTM 网络可以充分利用这两类信息。对此，我们经过若干实验，最终设计了图 3 所示的两阶段网络结构。在第一个阶段，词序列信息被充分利用，然后将最后一个词对应隐层的输出作为下一个阶段的输入，并和键码序列一起来进行计算，最后通过 Softmax 计算来生成最终结果。同时，在两阶段间加入「Start Flag」，以区隔词序列和键码序列。
图 3 词序列 / 键码序列混合
高质量训练数据的生成：在训练 LSTM 语言模型时，训练语料的质量和覆盖度是关键因素。从质量角度来讲，必须确保其中没有乱码、其他语言以及过短的句子等数据。从覆盖度角度来讲，一方面要确保训练语料的规模，使其能够覆盖语言中的大部分词汇，并足以支持语言模型的统计有效性，一般来讲训练语料的量级应该在千万或者亿；覆盖度的另一个角度为文本类型，需要确保训练语料中文本类型 (比如新闻、聊天、搜索等) 的分布同目标应用场景一致，对于手机输入法来讲，日常聊天类型的数据应该占足够大的比例；覆盖度的第三个维度为时间维度，需要确保训练语料可以覆盖对应国家 / 语言固定时间周期 (通常为年) 中各个时间段的数据，尤其是大型节日的数据。
在客户端，性能和内存是必须解决的关键问题。一个优秀的输入法引擎，在手机端运行时，需要始终稳定地保持低内存占用，确保在 Android Oreo (Go edition) 系统上也可以稳定运行，且保持良好的性能 (每次按键响应时间小于 60ms)。而 LSTM 原始模型通常较大 (例如美式英语的模型超过 1G)，在手机端运行时响应时间也远超 1s，需进行大幅优化。可以利用稀疏表示与学习的技术，来压缩图 3 LSTM 网络中的 word/ch embedding 矩阵及输出端 softmax 向量矩阵，同时基于 Kmeans 聚类对模型参数进行自适应量化学习，最终可以将超过 1G 的模型量化压缩到小于 5M。性能优化则意味着需要控制手机端的计算量，需要在保证效果的前提下优化模型结构，减少不必要的层数和神经元；同时，可基于 TensorFlow Lite (而非 TensorFlow Mobile) 进行手机端计算模块的开发，大幅提升性能和内存占用，唯一的成本是需要自己实现一些必备的 operators。我们采用该方案可以将运行时内存占用控制在 25M 以内，且响应时间保持在 20ms。图 4 是 TensorFlow Mobile 和 TensorFlow Lite 在相同 benchmark 上的对比数据。
图 4 TensorFlow Mobile 和 TensorFlow Lite 在相同 Benchmark 上的对比数据
基于以上的云端建模和客户端预测技术，我们完成了基于深度神经网络 (LSTM) 的输入法引擎方案的整体部署，并在大量语言上，同基于 N-gram 的语言模型进行了对比测试。在对比测试中，我们关注的关键指标为输入效率 (Input Efficiency)：
输入效率 = # 输入的文字长度 / # 完成文字输入所需的按键次数
我们期望输入效率越高越好；同时，我们也会关注每种语言对应的线上用户的回删率，在此不再赘述。
下图是在一些语言上 LSTM 引擎相对 N-gram 引擎输入效率的提升幅度。
图 5 LSTM 引擎相对 N-gram 引擎输入效率的提升幅度
高级预测功能
高级预测功能在第一部分提到过，输入法引擎也需要能够准确预测用户可能输入的 Emoji 或表情图片，而这些内容往往具有多义性，因此此类预测的复杂度会更高。
同时，对于 Emoji 来讲，用户往往会创造出一些有趣的 Emoji 组合，例如「🔑❤️💍」，如何自动挖掘出这样的 Emoji 组合，并将其整合进 LSTM 的模型框架中，也是一个很有趣的问题。
另一方面，从文字输入效率的角度看，如果每次预测能够准确预测不只一个词，而是词组，对用户的体验会是一个很大的提升。如何发现有意义的尽可能长的词组，并且整合进 LSTM 的模型框架中，也会是一个很有挑战的工作。
Q/A 环节
Q1: 请问姚老师，这里 softmax 输出是？
A1: 因为这个网络的目的是预测下一个词，所以 softmax 的输出是预测词的 id 和概率值。在实际产品中，我们会选择 Top 3 的预测词，按照概率值从高到底显示在候选区。
Q2: 输入法本质上就是根据用户前面的输入预测他接下来要输入什么。训练数据集和预测模型是在云端完成然后定期更新到手机端的吗？还是完全在手机上端完成的？
A2: 我们的方案是包含两个部分。对每种语言，我们会在云端迭代训练一个新 general language model，在新 model 效果得到离线评测验证后，下发到手机端。并且，在手机端，会根据每个用户的个人输入历史，来训练 personalized model （这个 model 的训练频率会更高）。在实际预测时，会将这两个 model 的 inference 结果 merge 起来得到最终结果。在手机端的训练，需要尤其注意训练的时机，不能在用户手机负载高的时候执行训练。
Q3:TF Lite 对手机有要求吗？
A3:TF Lite 对手机没有要求。但是 TF Lite 为了性能的考虑，砍掉了很多的 operators，我们在实现的过程中实现了自己模型 inference 必需的 operators.
Q4: 接上 Q1 的问题，针对英文情况，假如词表为 1w，softmax 层 1w 个节点，怎么优化 softmax 层呢？
A4:softmax 层的压缩，本质上就是 softmax 向量矩阵的压缩，其原理就是将巨大的向量矩阵转换为少量的过完备基向量组合，而过完备基向量可以自动学习获得。
Q5: 请问：每训练一次模型 LSTM 需要多少个 cell 这个是由什么决定的？
A5: 每训练一次模型 LSTM 需要多少个 cell，决定因素大体有两类：1）我们可以接受的模型的复杂度，这直接决定了最终量化压缩后的模型的大小；2）我们期望达到的效果。最终的决定主要是在这两类之间进行平衡。当然，也同语言本身的复杂度有关，比如德语同英语对比，会更加复杂，因此 cell 的数量多一些会更好。如果不考虑这个限制，我们可以通过云端 service 的方式来进行 inference.
Q6：未来输入法会支持语音输入吗？
A6: 我们正在开发 Kika 的语音识别和语义理解引擎，目前在英文上的语音识别水平接近 Google 的水平，所以会逐步上线 Kika 的语音输入功能。同时，我们基于 Kika 的一系列语音技术，已经在 CES 2018 发布了 KikaGO 车载语音解决方案，获得了很多好评和 CES 的四项大奖，并正在准备产品的正式发布。我们的全语音解决方案除了为车载场景下提供服务外，还会在场景上做出更多的尝试。
Q7:”可以在 LSTM 的网络结构中添加嵌入层 (Word Embedding Layer) 来将词与词的语义关系加入到训练和预测过程中” 能具体解释下，在实际的数据预处理中，是如何添加的？简单拼接还是啥？LSTM cell 的输入又是啥？
A7:Word Embedding Layer 的作用是将高维的词空间映射到低维的向量空间，确保在低维空间上语义相似的词的向量距离比较小。Word Embedding Layer 的输出作为 LSTM 的输入。TensorFlow 本身自带 Word Embedding Layer，其实就是一个简单的 lookup table。但如果所处理的问题领域不是 general domain，建议用所在 domain 的语料数据利用 Word2vector 来训练得到对应的 domain specific word embedding，用来替换掉 TensorFlow 自带的 Word Embedding Layer。
Q8: 输入法的研究应该是很有挑战的领域，尤其是人类语言太多了。能谈谈这方面的发展趋势吗？
A8:「趋势」都是大拿才可以谈的事情，我只谈一些自己的浅薄想法。输入法本质为了解决人类通过机器 (手机、电脑、智能家居等) 和网络达成的人与人的沟通问题。而这样的沟通问题，最重要的是能够达到或超越人与人在现实世界中利用语音、表情和肢体动作面对面沟通的效果，能够全面、准确、快速地达到意图、信息和情感的沟通。
因此，我们认为输入法的下一步发展一定是围绕着「全」、「准」、「快」三个方面进行的。「全」是指能够提供文字、语音、表情、多媒体内容等的沟通方式，「准」指的是使得接收方能够准确接收到表达方的意图、信息和情感，不会产生误解，「快」指的是表达放产生到接收方接收的时间足够短。
而「全」、「准」、「快」这三方面的用户体验，通过 AI 的技术，都可以大幅提升。
Q9: 我还想提问这样的 ai 输入法和百度输入法怎么竞争。谢谢。
A9: 产品之间的竞争，本质就是如何为用户创造价值。Kika 输入法的定位，就是解决全世界用户在人与人沟通之间产生的问题，就是为用户提供极致的「全」、「准」、「快」的沟通方式，为用户创造更多的价值。从市场划分上来看，两款产品也不在一个维度上竞争—国内的输入法巨头像搜狗、百度主要解决的是中文，而 kika 则重点为中文之外的其他语种的用户创造价值。
更多干货内容，可关注AI前线，ID：ai-front，后台回复「AI」、「TF」、「大数据」可获得《AI前线》系列PDF迷你书和技能图谱。
