Kejin Jin作者Hao Wang, Panda编辑

马尔可夫链、MLP和LSTM:谁是最好的电子邮件类别预测方法?

据估计,大约有 90% 的用户收到的电子邮件是机器生成的,其中包括收据、订单确认信息、广告、新闻订阅、密码找回邮件等等。其中有的包含了用户需要记录的信息,比如航班时间、电影座位号等等。通过自动提取这些有用的信息,邮件提供商可以帮助用户将这些信息添加到日历中或设置账单提醒等,从而提升用户体验。伊利诺伊大学厄巴纳-香槟分校和谷歌的研究者提出使用 MLP 和 LSTM 神经网络来预测邮件类别,并与马尔可夫链模型进行了比较。机器之心技术分析师对该研究进行了解读。

论文地址:https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/45896.pdf

引言

电子邮件类别预测可被视为一个多类分类任务,因为带有相似主题的电子邮件可能是使用相似的模板自动创建的。这篇论文的目的是基于用户之前收到的电子邮件预测未来将收到的电子邮件。也就是说,如果一位用户收到了一封特定主题的电子邮件,那么一些时日之后,他可能还会收到使用同样或相关模板的另一封邮件。

这篇论文有很高的实用意义,可直接助益我们的日常生活。通过准确预测电子邮件所属的类别,我们可以基于其对应的模板更好地提取出其中的有用信息。电子邮件服务提供商会认为这个功能很有用,举个例子,它们可以将提取出的信息自动添加到用户日历中,帮助安排用户日程,由此提升用户体验。

这篇论文分别使用了 MLP 和 LSTM 神经网络来做预测,并与之前所用的马尔可夫链模型进行了比较。

这篇论文提出的 MLP 和 LSTM 模型取得了一些最高的 MRR 分数,分别为 0.918 和 0.923;相比而言,5-dependent 马尔可夫链模型的表现为 0.840。所以,新模型的预测准确度相比之前最佳提升约 9%。

除了这些结果,该论文还强调,为了预测未来电子邮件的类别,不仅要考虑之前发生过的类别,还要考虑有关时间戳的信息。这篇论文在映射输入特征时就选择了这一做法。

比较三种模型

1.马尔可夫链模型

Gamzu et al. 提出的马尔可夫链模型是求解电子邮件分类预测问题的最有影响力的模型之一。马尔可夫链可通过“状态对(state pairs)”的形式表示为:

其中,a^(1) 到 a^(n) 是指用户收到的 n 封电子邮件的邮件类别序列,根据收到邮件的时间戳排序;k 是指我们选择的预测窗口,这意味着每个状态我们会考虑 k 封电子邮件,这种方法也因此被称为 k-dependent 马尔可夫链。然后我们可以构建有向图,其中的节点表示不同的状态,两个状态之间的边将两者链接成一个状态对。每条边的权重表示从一个状态到另一个状态的“转换概率”。这种类型的马尔可夫链模型可用于预测未来邮件,通过结合时间信息,该模型的精度可达到 45% 左右。

2.多层感知器(MLP

这篇论文提出的首个神经网络模型是一个简单的前馈模型:多层感知器(MLP)。该论文在神经元中没有使用普通的 sigmoid 或双曲正切激活函数,而是使用了修正线性单元(ReLU),这能更好地模拟真实神经元的“稀疏激活”,因此更具有生物合理性。(举个例子,对于广泛应用的 sigmoid 函数,有接近一半的神经元会被激活,这与我们大脑中真实神经元的实际情况不一样。)其校准函数可写成:

其中 h_l 指第 l 层的输出,W 指第 l-1 层到第 l 层的权重矩阵,b 是偏置向量。

如果这个 MLP 有 L 个隐藏层,则其输出层会首先使用一个 logit 函数得到一个向量 z:

然后,再使用 softmax 函数创建一个概率向量,如下所示:

其中 A 是指所有电子邮件类别的数量。未来的电子邮件属于第 a 个类别的概率 P(a) 即为 [y]a

需要优化的训练损失函数写为:

其中,u 指代一个特定用户,a_u^t 指类别,m_u^t 是在时间 t 所收到的邮件的时间戳。Δ 是预测时间窗的大小,表示我们将考虑在 Δ 时间内连续收到的邮件。1() 函数在两封邮件之间的时间间隔不超过 Δ 时取值为 1,否则取值为 0(在这篇论文中,Δ 设置为一周)。然后,使用 “Adam 随机优化算法”来优化 L,使用“沿时间的截断反向传播算法”来根据参数 W 和 b 计算 L 的梯度(参见 D. Kingma and J. Ba. Adam,2014 和 I. Goodfellow, Y. Bengio, and A. Courville,2016)。

3. 长短期记忆(LSTM)

另一个神经网络模型是长短期记忆(LSTM),研究已经证明其能非常有效地求解序列问题。不同于 MLP 的相对简单的结构,LSTM 的每一层中都有“记忆单元”来逐一处理电子邮件以及存储之前层的输出和前一封电子邮件的信息。更正式的表示可写成:

通过下面的图可以更清楚地理解:

图 1:LSTM 结构更进一步查看 LSTM Block 的工作方式,我们能够了解记忆单元 c 能够记忆的原因:

图 2:LSTM Blockh_1^0 和 c_1^0 都被初始化为零向量;在每个处理状态,LSTM Block 会按以下方式同时更新上面图中的各个参数

其中 σ 是一个 sigmoid 函数。σ 和 tanh 都是逐元素处理的,两个式子之间的 ⊙ 是逐元素的乘法运算符。

该论文中强调的几点

1.输入映射

如前所述,该论文提出未来电子邮件所属类别的概率不仅与之前邮件的类别有关,而且还与这些邮件的时间信息有关。所以,当将输入的 k 封收到的邮件映射到实数向量时,每个电子邮件向量都由三部分组成:

  • 类别向量 a,使用 one-hot 表示的电子邮件。(向量 A 的长度是所有类别的数量,其中第 a 维设置为 1,其它维都设置为 0。)如果我们有 a 个类别,那么其类别向量将是 a 维的。
  • 每周所在的天向量 d,同样也映射成 one-hot 表示(因为一周 7 天,所以 d 在该论文中设置为 7)。
  • 旬向量 p,同样也映射成 one-hot 表示(论文中 p 设置为 3,分别表示一个月的上旬、中旬、下旬)。

两封电子邮件之间时间间隔设置为实数。如果不超过一周,则该值为 1;如果长于一周则取 0 值。因此,k 封电子邮件的整个输入向量有 k*s 个值,其中 s 是每个邮件向量的长度,s=a+d+p+1。

2.数据集划分

该论文使用了 102,743 位用户在 90 天内收到的 2,562,361 封电子邮件,这些电子邮件分为 17 个类别。

该论文的作者对问题的所有方面都进行了成熟的考虑,并按两种方式对数据集进行了划分。第一种方式是让测试集包含已知一组用户收到的电子邮件,而训练集和验证集的用户则是未知的。第二种方式则是进一步确保测试集中的电子邮件属于一组新用户。

图 3:数据划分

3.衡量预测的准确度

这篇论文使用了 MRR(Mean Reciprocal Rank/平均倒数排名)来衡量预测的准确度。RR 是指首个正确预测到的类别的位置的倒数,按概率的降序排序,也称为排名(rank);M 的意思是取所有排名的平均。

另外,该论文还使用了在 r 处的成功率(SR@r)来衡量准确度,其表示:在预测时间窗内,排名小于或等于 r 的测试邮件的比例。

举个例子,当按以上提到的两种方式划分数据集并逐渐增大预测窗口 k 时,马尔可夫链模型的MRR 和 SR@r 将按下图所示变化。

图 4:马尔可夫链模型的 MRR 和 SR@r4.预防过拟合

这篇论文采用了 dropout 正则化方法来降低循环神经网络过拟合(参见 V. Pham, T. Bluche, C. Kermorvant, and J. Louradour, 2014)。简单来说,dropout 的意思是随机清除隐藏层中的某些神经元(即将它们设置为 0)。下图表明,使用一些正向 dropout,LSTM 模型可以得到更高的 MRR。这张图还表明,对于 LSTM 模型,单个隐藏层得到的结果就足够让人满意了,而 MLP 可能还需要更多隐藏层才能得到同样的结果。图 5:dropout 正则化

结果

实验结果提供了以下五个方面的见解:

a)马尔可夫链模型不足以描述电子邮件的有用信息,因为它无法很好地映射过去电子邮件的时间特征。因为 MLP 和 LSTM 模型都能更好地描述时间信息,所以它们显然比马尔可夫链模型更优。其中 LSTM 是这三种模型中表现最好的。

图 6:比较使用不同时间窗的三个模型

b)将隐藏层的数量增加到 2 以上,以及增加 MLP 和 LSTM 中每层中的神经元数量都不会带来显著的性能提升,如下所示:

图 7:在 MLP 的第一个隐藏层使用不同数量的神经元的比较

c)只有当预测窗口大小 k 不大于 5 时,增大 k 才会显著提升准确度,如图 7 所示。增大预测时间窗大小也能提升准确度,如图 6 所示。

d)当使用图 3 中描述的第二种数据划分方法时,即测试集中的用户不会在训练集和验证集中的出现,所有三种模型的准确度都会变低,但只有 5-dependent 马尔可夫链模型下降很显著,其它两种模型下降不多。如下面的表格所示。

e)如果我们最小化这三种模型的“记忆能力”(对于马尔可夫链和 MLP 模型,即设置 k=1;对于 LSTM 模型则意味着清除所有记忆单元),则这三种模型的表现都只会稍微变差,也如下面的表格所示。

表 1:按图 3 中第一种方式划分数据后,模型得到的表现

表 2:按图 3 中第二种方式划分数据后,模型得到的表现

总结

这篇论文提出的 MLP 和 LSTM 模型实现了最高的 MRR 分数,分别为0.918 和 0.923,相比而言 5-dependent 马尔可夫链模型为 0.840。即使清除这三种模型的所有记忆能力,LSTM 的表现依然是最优的。

这是一个相当全面的实验,通过研究如何映射过去邮件的更多特征,而不是当前的类别信息和时间信息,还能实现进一步的提升。

分析师简评

在这篇论文中,我们看到 LSTM 神经网络在这三种模型中表现最优。事实上,LSTM 能够有效处理很多不同的问题,尤其是序列问题(时间序列和空间序列都可以)。LSTM 最出色的应用领域之一是自然语言处理——从词性标注和句法结构分析到机器翻译语音识别,所有这些任务都需要模型有能力处理长期语境或输入序列中符号之间的依赖。

某些语言还有固定的“语法模板”,比如汉语和日语中的连词,其中某些连词很可能会出现在某些其它“配对”连词之后。这篇论文提出的方法有望为自然语言生成或自然语言理解领域的研究提供灵感。

参考文献

[1] Aston Zhang, Lluis Garcia-Pueyo, James B. Wendt, Marc Najork, Andrei Broder, Email Category Prediction

Source:https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/45896.pdf

[2] D. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint:1412.6980, 2014. 

[3] V. Pham, T. Bluche, C. Kermorvant, and J. Louradour. Dropout improves recurrent neural networks for handwriting recognition. In 14th International Conference on Frontiers in Handwriting Recognition, pages 285–290, 2014.

理论
相关数据
激活函数技术

在 计算网络中, 一个节点的激活函数定义了该节点在给定的输入或输入的集合下的输出。标准的计算机芯片电路可以看作是根据输入得到"开"(1)或"关"(0)输出的数字网络激活函数。这与神经网络中的线性感知机的行为类似。 一种函数(例如 ReLU 或 S 型函数),用于对上一层的所有输入求加权和,然后生成一个输出值(通常为非线性值),并将其传递给下一层。

权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

多层感知机技术

感知机(Perceptron)一般只有一个输入层与一个输出层,导致了学习能力有限而只能解决线性可分问题。多层感知机(Multilayer Perceptron)是一类前馈(人工)神经网络及感知机的延伸,它至少由三层功能神经元(functional neuron)组成(输入层,隐层,输出层),每层神经元与下一层神经元全互连,神经元之间不存在同层连接或跨层连接,其中隐层或隐含层(hidden layer)介于输入层与输出层之间的,主要通过非线性的函数复合对信号进行逐步加工,特征提取以及表示学习。多层感知机的强大学习能力在于,虽然训练数据没有指明每层的功能,但网络的层数、每层的神经元的个数、神经元的激活函数均为可调且由模型选择预先决定,学习算法只需通过模型训练决定网络参数(连接权重与阈值),即可最好地实现对于目标函数的近似,故也被称为函数的泛逼近器(universal function approximator)。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

损失函数技术

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学等领域,损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

词性标注技术

词性标注是指为分词结果中的每个单词标注一个正确的词性的程序,也即确定每个词是名词、动词、形容词或其他词性的过程。

验证集技术

验证数据集是用于调整分类器超参数(即模型结构)的一组数据集,它有时也被称为开发集(dev set)。

机器翻译技术

机器翻译(MT)是利用机器的力量「自动将一种自然语言(源语言)的文本翻译成另一种语言(目标语言)」。机器翻译方法通常可分成三大类:基于规则的机器翻译(RBMT)、统计机器翻译(SMT)和神经机器翻译(NMT)。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

反向传播算法技术

反向传播(英语:Backpropagation,缩写为BP)是“误差反向传播”的简称,是一种与最优化方法(如梯度下降法)结合使用的,用来训练人工神经网络的常见方法。该方法计算对网络中所有权重计算损失函数的梯度。这个梯度会反馈给最优化方法,用来更新权值以最小化损失函数。 在神经网络上执行梯度下降法的主要算法。该算法会先按前向传播方式计算(并缓存)每个节点的输出值,然后再按反向传播遍历图的方式计算损失函数值相对于每个参数的偏导数。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

规范化技术

规范化:将属性数据按比例缩放,使之落入一个小的特定区间,如-1.0 到1.0 或0.0 到1.0。 通过将属性数据按比例缩放,使之落入一个小的特定区间,如0.0到1.0,对属性规范化。对于距离度量分类算法,如涉及神经网络或诸如最临近分类和聚类的分类算法,规范化特别有用。如果使用神经网络后向传播算法进行分类挖掘,对于训练样本属性输入值规范化将有助于加快学习阶段的速度。对于基于距离的方法,规范化可以帮助防止具有较大初始值域的属性与具有较小初始值域的属相相比,权重过大。有许多数据规范化的方法,包括最小-最大规范化、z-score规范化和按小数定标规范化。

过拟合技术

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

神经元技术

(人工)神经元是一个类比于生物神经元的数学计算模型,是神经网络的基本组成单元。 对于生物神经网络,每个神经元与其他神经元相连,当它“兴奋”时会向相连的神经元发送化学物质,从而改变这些神经元的电位;神经元的“兴奋”由其电位决定,当它的电位超过一个“阈值”(threshold)便会被激活,亦即“兴奋”。 目前最常见的神经元模型是基于1943年 Warren McCulloch 和 Walter Pitts提出的“M-P 神经元模型”。 在这个模型中,神经元通过带权重的连接接处理来自n个其他神经元的输入信号,其总输入值将与神经元的阈值进行比较,最后通过“激活函数”(activation function)产生神经元的输出。

语音识别技术

自动语音识别是一种将口头语音转换为实时可读文本的技术。自动语音识别也称为语音识别(Speech Recognition)或计算机语音识别(Computer Speech Recognition)。自动语音识别是一个多学科交叉的领域,它与声学、语音学、语言学、数字信号处理理论、信息论、计算机科学等众多学科紧密相连。由于语音信号的多样性和复杂性,目前的语音识别系统只能在一定的限制条件下获得满意的性能,或者说只能应用于某些特定的场合。自动语音识别在人工智能领域占据着极其重要的位置。

自然语言处理技术

自然语言处理(英语:natural language processing,缩写作 NLP)是人工智能和语言学领域的分支学科。此领域探讨如何处理及运用自然语言;自然语言认知则是指让电脑“懂”人类的语言。自然语言生成系统把计算机数据转化为自然语言。自然语言理解系统把自然语言转化为计算机程序更易于处理的形式。

自然语言生成技术

自然语言生成(NLG)是自然语言处理的一部分,从知识库或逻辑形式等等机器表述系统去生成自然语言。这种形式表述当作心理表述的模型时,心理语言学家会选用语言产出这个术语。自然语言生成系统可以说是一种将资料转换成自然语言表述的翻译器。不过产生最终语言的方法不同于编译程式,因为自然语言多样的表达。NLG出现已久,但是商业NLG技术直到最近才变得普及。自然语言生成可以视为自然语言理解的反向: 自然语言理解系统须要厘清输入句的意涵,从而产生机器表述语言;自然语言生成系统须要决定如何把概念转化成语言。

马尔可夫链技术

马尔可夫链,又称离散时间马尔可夫链,因俄国数学家安德烈·马尔可夫得名,为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质:下一状态的概率分布只能由当前状态决定,在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。

推荐文章
暂无评论
暂无评论~