加载中…
正文 字体大小:

打回原形

(2016-02-08 21:59:33)
标签:

自然语言处理

有限状态自动机

图灵机

深度学习

rnn/lstm

  数学家比较擅长“打回原形”。

  比如,一个变量的线性函数,一般形式是y=ax+b,这里ab是常数,x是自变量,y是因变量。到了多个自变量、多个因变量的情形,线性函数长得不一样了,又是加又是乘的一大堆,下标也一大堆,变量之间还有各种交叉。结果,数学家发明了矩阵和向量。m个自变量,用一个m维向量X来代表,n个因变量,用一个n维向量来代表。自变量之间那种交叉的线性组合系数,用一个m×n的矩阵来代表。恰当定义矩阵和矩阵、矩阵和向量之间的四则运算以后,m个自变量和n个因变量之间的线性函数关系,仍然能够写成Y=AX+B。这里,X是自变量向量,Y是因变量向量,B是常数向量,A是常数矩阵。线性函数关系又被打回了原形。

  虽说是打回原形,但毕竟升华了。加号还是那个加号,乘号(已省略)还是那个乘号,但是符号的意义已经悄然发生变化。字母从小写换成大写,只不过是为了遵守关于向量和矩阵的有关约定。数学家给我们玩了个狸猫换太子的游戏,公式还是那个公式,但是“瓤”已经偷偷换掉了。加号和乘号、变量和常量都承载了更多的内容。

  打回原形,更容易透过复杂的表象看清简单的本质。从数的加和乘,到矩阵、向量的加和乘,到无穷维的空间里的加和乘,再到更加抽象的线性空间里定义的加和乘,一步步逼近本质,一步步把更广泛的线性变换现象收入囊中。在数学和物理中,公式“长得一样”被赋予了“变换下规律的形式不变性”的深刻含义。就连著名的狭义相对论,也是因为要把相对作匀速直线运动的坐标系变换下物理规律的形式不变性作为硬约束,才通过大胆假设光速不变,赋予洛伦兹变换以新的生命。

  回过头来说说计算机科学。计算机科学领域里,一个很基础的形式化机制,就是“有限状态自动机”。在传统的图表示下,有限状态自动机的状态和状态之间也和多变量的线性函数一样呈交叉网状连接,而且还把输入输出字符做成边上的权。我们试着改变一下描述方式:设字母表里一共有m个字符,状态集里一共有n个状态,把输入字符、输出字符都做成m维布尔向量(是字符k则第k维分量为1,否则为0),把状态做成n维布尔向量(处于状态s则第s维分量为1,否则为0)。再看这输入输出字符和状态随时间的变化更新。我们可以看到这是几个布尔向量的时间序列,如果写成以时间为自变量的数学公式,就是S(t+1)=δ(I(t), S(t))O(t)=σ(I(t), S(t))。如果写成计算机赋值语句,那就更简单了:S:=δ(I,S)O:= σ(I,S)。如果画出图来,就是:

 打回原形 

  再看看最近在语音识别和自然语言处理领域出尽风头的深度学习算法RNN,它本质上不也是这样吗?如果说有什么不同,第一,不要求输入向量I有且仅有一个分量为1,也就是说,允许歧义输入;第二,不要求状态向量S有且仅有一个分量为1,也就是说,允许内部状态存在不确定性;第三,不要求输出向量O有且仅有一个分量为1,也就是说,输出的赢家通吃只是一种特殊情形,一般情形可以允许输出带有不确定性,以方便下一道工序按需选择。

  我们再看大名鼎鼎的图灵机。其实,图灵机的输出,就是写带。这里,图灵机的带子既是存储介质,也是输出介质。为了更加看清楚图灵机的实质,我们在不降低图灵机计算能力的前提下,不妨假定有图灵机有两个带子,一个专门用于输入输出,另一个专门用于存储。也就是说,把图灵机的存储介质和输出介质进行分离。仿照前面的办法,在输入向量I、输出向量O、状态向量S之外,再引入寻址机制如下:M代表完整的存储,函数m(t)代表存储M在时刻t唯一可以访问的地址单元——焦点地址,U(d, t)表示地址d在时刻t所存字符对应的字符向量。定义:

 

S(t+1)=δ(I(t), S(t),U(m(t), t))

                   //当前输入字符、当前状态和焦点地址所存字符决定下一状态

O(t)=σ(I(t), S(t), U(m(t), t));

                   //当前输入字符、当前状态和焦点地址所存字符决定当前输出字符

U(m(t), t+1)=w(I(t), S(t), U(m(t), t));

                   //当前输入字符、当前状态和焦点地址所存字符决定焦点地址写入字符

m(t+1)=c(I(t), S(t), U(m(t), t)))

                   //当前输入字符、当前状态和焦点地址所存字符决定下一时刻焦点地址

 

 

得到下图:

打回原形

  对于图灵机来说,c给出的值不过是左移、右移和不动三个选择的编码。对于下推自动机,c给出的值可以是进栈和出栈。对于计数自动机,c给出相应下标的计数器值。我们也不难看出,LSTM本质上也可以纳入这个范畴。

  将有限状态自动机/图灵机和RNN/LSTM打回共同的原形,意思无非是说,存在着这么一种可能性,就是从规则出发,可以把规则直接编译为相应的RNN/LSTM。这样做可以有以下几个好处:1、可以借用领域专家的显性知识生成RNN/LSTM表示并直接使用;2、可以在编译而成的RNN/LSTM基础上,借助深度学习进行基于统计的局部微调;3、可以借助RNN/LSTM本身的泛化能力和鲁棒性使规则更具弹性。

  过去的刻板印象是:统计和浅层自然语言处理画等号,规则和深层自然语言处理画等号。如今,有了RNN/LSTM,这两个等号全都不对了。从我们的分析可以看出,在打回原形之后,RNN/LSTM和有限状态自动机/图灵机的关系,比跟HMM等基于统计的方法的关系,要亲近得多。



0

阅读 评论 收藏 转载 喜欢 打印举报
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有