深度学习主机环境配置: Ubuntu16.04+GeForce GTX 1080+TensorFlow

接上文《深度学习主机环境配置: Ubuntu16.04+Nvidia GTX 1080+CUDA8.0》,我们继续来安装 TensorFlow,使其支持GeForce GTX 1080显卡。

1 下载和安装cuDNN

cuDNN全称 CUDA Deep Neural Network library,是NVIDIA专门针对深度神经网络设计的一套GPU计算加速库,被广泛用于各种深度学习框架,例如Caffe, TensorFlow, Theano, Torch, CNTK等。

The NVIDIA CUDA® Deep Neural Network library (cuDNN) is a GPU-accelerated library of primitives for deep neural networks. cuDNN provides highly tuned implementations for standard routines such as forward and backward convolution, pooling, normalization, and activation layers. cuDNN is part of the NVIDIA Deep Learning SDK.

Deep learning researchers and framework developers worldwide rely on cuDNN for high-performance GPU acceleration. It allows them to focus on training neural networks and developing software applications rather than spending time on low-level GPU performance tuning. cuDNN accelerates widely used deep learning frameworks, including Caffe, TensorFlow, Theano, Torch, and CNTK. See supported frameworks for more details.

首先需要下载cuDNN,直接从Nvidia官方下载链接选择一个版本,不过下载cuDNN前同样需要登录甚至填写一个简单的调查问卷: https://developer.nvidia.com/rdp/cudnn-download,这里选择的是支持CUDA8.0的cuDNN v5版本,而支持CUDA8的5.1版本虽然显示在下载选择项里,但是提示:cuDNN 5.1 RC for CUDA 8RC will be available soon – please check back again.

屏幕快照 2016-07-17 上午11.17.39

安装cuDNN比较简单,解压后把相应的文件拷贝到对应的CUDA目录下即可:

tar -zxvf cudnn-8.0-linux-x64-v5.0-ga.tgz

cuda/include/cudnn.h
cuda/lib64/libcudnn.so
cuda/lib64/libcudnn.so.5
cuda/lib64/libcudnn.so.5.0.5
cuda/lib64/libcudnn_static.a

sudo cp cuda/include/cudnn.h /usr/local/cuda/include/
sudo cp cuda/lib64/libcudnn* /usr/local/cuda/lib64/
sudo chmod a+r /usr/local/cuda/include/cudnn.h
sudo chmod a+r /usr/local/cuda/lib64/libcudnn*

继续阅读

发表在 深度学习 | 标签为 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , | 17条评论

深度学习主机环境配置: Ubuntu16.04+Nvidia GTX 1080+CUDA8.0

接上文《深度学习主机攒机小记》,这台GTX1080主机准备好之后,就是配置深度学习环境了,这里选择了比较熟悉Ubuntu系统,不过是最新的16.04版本,另外在Nvidia GTX1080的基础上安装相关GPU驱动,外加CUDA8.0,因为都比较新,所以踩了很多坑。

1. 安装Ubuntu16.04

不考虑双系统,直接安装 Ubuntu16.04,从ubuntu官方下载64位版本: ubuntu-16.04-desktop-amd64.iso 。

在MAC下制作了 Ubuntu USB 安装盘,具体方法可参考: 在MAC下使用ISO制作Linux的安装USB盘,之后通过Bios引导U盘启动安装Ubuntu系统:

1)一开始安装就踩了一个坑,选择”Install Ubuntu”回车后过一会儿屏幕显示“输入不支持”,google了好多方案,最终和ubuntu对显卡的支持有关,需要手动添加显卡选项: nomodeset,使其支持Nvidia系列显卡,参考:安装ubuntu黑屏问题的解决 or How do I set ‘nomodeset’ after I’ve already installed Ubuntu?

2) 磁盘分区,全部干掉之前主机自带的Window 10系统,分区为 /boot, /, /home 等几个目录,同时把第二块4T硬盘也挂载了上去,作为数据盘。

3)安装完毕后Ubuntu 16.04的分辨率很低,在显卡驱动未安装之前,可以手动修改一下grub文件:

sudo vim /etc/default/grub

# The resolution used on graphical terminal
# note that you can use only modes which your graphic card supports via VBE
# you can see them in real GRUB with the command `vbeinfo’
#GRUB_GFXMODE=640×480
# 这里分辨率自行设置
GRUB_GFXMODE=1024×768

sudo update-grub

4)安装SSH Server,这样可以远程ssh访问这台GTX1080主机:

sudo apt-get install openssh-server

5)更新Ubuntu16.04源,用的是中科大的源

cd /etc/apt/
sudo cp sources.list sources.list.bak
sudo vi sources.list

把下面的这些源添加到source.list文件头部:

deb http://mirrors.ustc.edu.cn/ubuntu/ xenial main restricted universe multiverse
deb http://mirrors.ustc.edu.cn/ubuntu/ xenial-security main restricted universe multiverse
deb http://mirrors.ustc.edu.cn/ubuntu/ xenial-updates main restricted universe multiverse
deb http://mirrors.ustc.edu.cn/ubuntu/ xenial-proposed main restricted universe multiverse
deb http://mirrors.ustc.edu.cn/ubuntu/ xenial-backports main restricted universe multiverse
deb-src http://mirrors.ustc.edu.cn/ubuntu/ xenial main restricted universe multiverse
deb-src http://mirrors.ustc.edu.cn/ubuntu/ xenial-security main restricted universe multiverse
deb-src http://mirrors.ustc.edu.cn/ubuntu/ xenial-updates main restricted universe multiverse
deb-src http://mirrors.ustc.edu.cn/ubuntu/ xenial-proposed main restricted universe multiverse
deb-src http://mirrors.ustc.edu.cn/ubuntu/ xenial-backports main restricted universe multiverse

最后更新源和更新已安装的包:

sudo apt-get update
sudo apt-get upgrade
继续阅读

发表在 深度学习 | 标签为 , , , , , , , , , , , , , , , , , , , , | 14条评论

Mecab安装过程中的一些坑

先说一点题外话,最近发现 Linode 因为庆祝13周年活动将所有的Plan加了一倍,又来了一次加量不加价,这一下子和别的产品拉开了差距,可惜目前Linode日本节点并不参加活动,否则52nlp目前所用的这台 Linode 主机性能就可以翻倍了。不过还是搞了一台 Linode 8GB(8G内存,4核,96G SSD硬盘容量) 的VPS套餐(40$/mo),选择了美国西部的 Fremont 节点,据说国内连接速度很不错。在上面选择了64位的Ubuntu14.04 版本,但是在这个环境下安装Mecab的过程中接连踩了几个坑,所以记录一下。

这里曾写过“Mecab中文分词”系列文章,也在github上发布过一个中文分词项目 MeCab-Chinese:Chinese morphological analysis with Word Segment and POS Tagging data for MeCab ,但是这个过程中没有怎么写到Mecab安装的问题,因为之前觉得rickjin的这篇《日文分词器 Mecab 文档》应该足够参考,自己当时也在Mac OS和Ubuntu环境下安装成功并测试,印象貌似不是太复杂。这次在Ubuntu 14.04的环境安装的时候,遇到了几个小坑,记录一下,做个备忘,仅供参考。
继续阅读

发表在 中文分词, 自然语言处理 | 标签为 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , | 留下评论

深度学习主机攒机小记

五月中下旬的时候,GTX1080的公布和发售直接刺激了我攒一台深度学习主机的欲望,攒机对于我来说已经相隔十多年,大学时候的第一台PC就是攒出来的,其实也就是在5000元的预算内,去电脑城里找商家组装了一台台式机,美其名曰DIY。

虽然已经锁定显卡,但是对于其他的搭配还是很模糊,只是需要“好CPU”,“大内存”, “大硬盘”, 于是开始google “深度学习电脑”,“深度学习服务器”,“深度学习PC”, “深度学习主机”,“深度学习机器”,“深度学习工作站”这些关键词,并很快锁定了这篇文章《如何搭建一台深度学习服务器》作为主要参考:

硬件选择:基本思路是单显卡机器,保留升级空间

……

CPU选择:
在深度学习任务中,CPU并不负责主要任务,单显卡计算时只有一个核心达到100%负荷,所以CPU的核心数量和显卡数量一致即可,太多没有必要,但是处理PCIE的带宽要到40。

主板选择:
需要支持X99架构,支持PCIe3.0,还要支持4通道DDR4内存架构。如果要搞四显卡并行,PCIE带宽支持要达到40,并且支持4-Way NVIDA SLI技术。

内存:
达到显存的二倍即可,当然有钱的话越大越好。

电源问题:一个显卡的功率接近300W,四显卡建议电源在1500W以上,为了以后扩展,选择了1600W的电源。

机箱散热:
因为各种部件相当庞大,需要有良好散热功能的大机箱,选择了Tt Thermaltake Core V51机箱,标配3个12cm风扇。未来如果需要还可以加装水冷设备。

……

最后的硬件配置:
CPU: Intel X99平台 i7 5960K
内存: DDR4 2800 32G(8G*4)
主板: GIGABYTE X99-UD4
显卡: GTX Titan X
硬盘: SSD+普通硬盘

继续阅读

发表在 深度学习 | 标签为 , , , , , , , , , , , , | 25条评论

QA问答系统中的深度学习技术实现

应用场景

智能问答机器人火得不行,开始研究深度学习在NLP领域的应用已经有一段时间,最近在用深度学习模型直接进行QA系统的问答匹配。主流的还是CNN和LSTM,在网上没有找到特别合适的可用的代码,自己先写了一个CNN的(theano),效果还行,跟论文中的结论是吻合的。目前已经应用到了我们的产品上。

原理

参看《Applying Deep Learning To Answer Selection: A Study And An Open Task》,文中比较了好几种网络结构,选择了效果相对较好的其中一个来实现,网络描述如下:

qacnn_v2

Q&A共用一个网络,网络中包括HL,CNN,P+T和Cosine_Similarity,HL是一个g(W*X+b)的非线性变换,CNN就不说了,P是max_pooling,T是激活函数Tanh,最后的Cosine_Similarity表示将Q&A输出的语义表示向量进行相似度计算。

详细描述下从输入到输出的矩阵变换过程:

  1. Qp:[batch_size, sequence_len],Qp是Q之前的一个表示(在上图中没有画出)。所有句子需要截断或padding到一个固定长度(因为后面的CNN一般是处理固定长度的矩阵),例如句子包含3个字ABC,我们选择固定长度sequence_len为100,则需要将这个句子padding成ABC<a><a>…<a>(100个字),其中的<a>就是添加的专门用于padding的无意义的符号。训练时都是做mini-batch的,所以这里是一个batch_size行的矩阵,每行是一个句子。
  2. Q:[batch_size, sequence_len, embedding_size]。句子中的每个字都需要转换成对应的字向量,字向量的维度大小是embedding_size,这样Qp就从一个2维的矩阵变成了3维的Q
  3. HL层输出:[batch_size, embedding_size, hl_size]。HL层:[embedding_size, hl_size],Q中的每个句子会通过和HL层的点积进行变换,相当于将每个字的字向量从embedding_size大小变换到hl_size大小。
  4. CNN+P+T输出:[batch_size, num_filters_total]。CNN的filter大小是[filter_size, hl_size],列大小是hl_size,这个和字向量的大小是一样的,所以对每个句子而言,每个filter出来的结果是一个列向量(而不是矩阵),列向量再取max-pooling就变成了一个数字,每个filter输出一个数字,num_filters_total个filter出来的结果当然就是[num_filters_total]大小的向量,这样就得到了一个句子的语义表示向量。T就是在输出结果上加上Tanh激活函数。
  5. Cosine_Similarity:[batch_size]。最后的一层并不是通常的分类或者回归的方法,而是采用了计算两个向量(Q&A)夹角的方法,下面是网络损失函数。t2,m是需要设定的参数margin,VQ、VA+、VA-分别是问题、正向答案、负向答案对应的语义表示向量。损失函数的意义就是:让正向答案和问题之间的向量cosine值要大于负向答案和问题的向量cosine值,大多少,就是margin这个参数来定义的。cosine值越大,两个向量越相近,所以通俗的说这个Loss就是要让正向的答案和问题愈来愈相似,让负向的答案和问题越来越不相似。

实现

代码点击这里,使用的数据是一份英文的insuranceQA,下面介绍代码重点部分:

字向量。本文采用字向量的方法,没有使用词向量。使用字向量的目的主要是为了解决未登录词的问题,这样在测试的时候就很少会遇到Unknown的字向量的问题了。而且字向量的效果也不一定比词向量的效果差,还省去了分词的各种麻烦。先用word2vec生成一份字向量,相当于我们在做pre-training了(之后测试了随机初始化字向量的方法,效果差不多)

原理中的步骤2。这里没有做HL层的变换,实际测试中,增加HL层有非常非常小的提升,所以在这里就省去了改步骤。

t4

CNN可以设置多种大小的filter,最后各种filter的结果会拼接起来。

t5

原理中的步骤4。这里执行卷积,max-pooling和Tanh激活。

t6

生成的ouputs_1是一个python的list,使用concatenate将list的多个tensor拼接起来(list中的每个tensor表示一种大小的filter卷积的结果)t7

原理中的步骤5。计算问题、正向答案、负向答案的向量夹角

t8

生成Loss损失函数和Accuracy。t9

核心的网络构建代码就是这些,其他的代码都是训练数据、验证数据的读入,以及theano构建训练时的一些常规代码。

如果需要增加HL层,可参照如下的代码。Whl即是HL层的网络,将input和Whl点积即可。t10

dropout的实现。

t11

结果

使用上面的代码,Test 1的Top-1 Accuracy可以达到61%-62%,和论文中的结论基本一致了,至于论文中提到的GESD、AESD等方法没有再测试了,运行较慢,其他数据集也没有再测试了。

下面是国外友人用一个叫keras的工具(封装的theano和tensorflow)弄的类似代码,Test 1的Top-1准确率在50%左右,比他这个要高:)

http://benjaminbolte.com/blog/2016/keras-language-modeling.html

Test set Top-1 Accuracy Mean Reciprocal Rank
Test 1 0.4933 0.6189
Test 2 0.4606 0.5968
Dev 0.4700 0.6088

另外,原始的insuranceQA需要进行一些处理才能在这个代码上使用,具体参看github上的说明吧。

一些技巧

  1. 字向量和词向量的效果相当。所以优先使用字向量,省去了分词的麻烦,还能更好的避免未登录词的问题,何乐而不为。
  2. 字向量不是固定的,在训练中会更新
  3. Dropout的使用对最高的准确率没有很大的影响,但是使用了Dropout的结果更稳定,准确率的波动会更小,所以建议还是要使用Dropout的。不过Dropout也不易过度使用,比如Dropout的keep_prob概率如果设置到0.25,则模型收敛得更慢,训练时间长很多,效果也有可能会更差,设置会差很多。我这版代码使用的keep_prob为0.5,同时保证准确率和训练时间。另外,Dropout只应用到了max-pooling的结果上,其他地方没有再使用了,过多的使用反而不好。
  4. 如何生成训练集。每个训练case需要一个问题+一个正向答案+一个负向答案,很明显问题和正向答案都是有的,负向答案的生成方法就是随机采样,这样就不需要涉及任何人工标注工作了,可以很方便的应用到大数据集上。
  5. HL层的效果不明显,有很微量的提升。如果HL层的大小是200,字向量是100,则HL层相当于将字向量再放大一倍,这个感觉没有多少信息可利用的,还不如直接将字向量设置成200,还省去了HL这一层的变换。
  6. margin的值一般都设置得比较小。这里用的是0.05
  7. 如果将Cosine_similarity这一层换成分类或者回归,印象中效果是不如Cosine_similarity的(具体数据忘了)
  8. num_filters越大并不是效果越好,基本到了一定程度就很难提升了,反而会降低训练速度。
  9. 同时也写了tensorflow版本代码,对比theano的,效果差不多
  10. Adam和SGD两种训练方法比较,Adam训练速度貌似会更快一些,效果基本也持平吧,没有太细节的对比。不过同样的网络+SGD,theano好像训练要更快一些。
  11. Loss和Accuracy是比较重要的监控参数。如果写一个新的网络的话,类似的指标是很有必要的,可以在每个迭代中评估网络是否正在收敛。因为调试比较麻烦,所以通过这些参数能评估你的网络写对没,参数设置是否正确。
  12. 网络的参数还是比较重要的,如果一些参数设置不合理,很有可能结果千差万别,记得最初用tensorflow实现的时候,应该是dropout设置得太小,导致效果很差,很久才找到原因。所以调参和微调网络还是需要一定的技巧和经验的,做这版代码的时候就经历了一段比较痛苦的调参过程,最开始还怀疑是网络设计或是代码有问题,最后总结应该就是参数没设置好。

结语

如果关注这个东西的人多的话,后面还可以有tensorflow版本的QA CNN,以及LSTM的代码奉上:)

补充

tensorflow的CNN代码已添加到github上,点击这里

Contact: jiangwen127@gmail.com weibo:码坛奥沙利文

发表在 机器学习, 深度学习, 自然语言处理, 问答系统 | 34条评论

达观数据搜索引擎的Query自动纠错技术和架构详解

1 背景

如今,搜索引擎是人们的获取信息最重要的方式之一,在搜索页面小小的输入框中,只需输入几个关键字,就能找到你感兴趣问题的相关网页。搜索巨头Google,甚至已经使Google这个创造出来的单词成为动词,有问题Google一下就可以。在国内,百度也同样成为一个动词。除了通用搜索需求外,很多垂直细分领域的搜索需求也很旺盛,比如电商网站的产品搜索,文学网站的小说搜索等。面对这些需求,达观数据(www.datagrand.com)作为国内提供中文云搜索服务的高科技公司,为合作伙伴提供高质量的搜索技术服务,并进行搜索服务的统计分析等功能。(达观数据联合创始人高翔)

搜索引擎系统最基本最核心的功能是信息检索,找到含有关键字的网页或文档,然后按照一定排序将结果给出。在此基础之上,搜索引擎能够提供更多更复杂的功能来提升用户体验。对于一个成熟的搜索引擎系统,用户看似简单的搜索过程,需要在系统中经过多个环节,多个模块协同工作,才能提供一个让人满意的搜索结果。其中拼写纠错(Error Correction,以下简称EC)是用户比较容易感知的一个功能,比如百度的纠错功能如下图所示:

图片 1

图 1:百度纠错功能示例

EC其实是属于Query Rewrite(以下简称QR)模块中的一个功能,QR模块包括拼写纠错,同义改写,关联query等多个功能。QR模块对于提升用户体验有着巨大的帮助,对于搜索质量不佳的query进行改写后能返回更好的搜索结果。QR模块内容较多,以下着重介绍EC功能。
继续阅读

发表在 自然语言处理 | 2条评论

非主流自然语言处理——遗忘算法系列(四):改进TF-IDF权重公式

一、前言

  前文介绍了利用词库进行分词,本文介绍词库的另一个应用:词权重计算。

二、词权重公式

  1、公式的定义
    定义如下公式,用以计算词的权重:
    权重公式
  2、公式的由来
    在前文中,使用如下公式作为分词的依据:
    公式推导
    任给一个句子或文章,通过对最佳分词方案所对应的公式进行变换,可以得到:
    公式推导
    按前面权重公式的定义,上面的公式可以理解为:一个句子出现的概率对数等于句子中各词的权重之和。
    公式两边同时取负号使权重是个正值。

三、与TF-IDF的关系

  词频、逆文档频率(TF-IDF)在自然语言处理中,应用十分广泛,也是提取关键词的常用方法,公式如下:
  tf-idf
  从形式上看,该公式与我们定义的权重公式很像,而且用途也近似,那么它们之间有没有关系呢?
  答案是肯定的。
  我们知道,IDF是按文档为单位统计的,无论文档的长短,统一都按一篇计数,感觉这个统计的粒度还是比较粗的,有没有办法将文本的长短,这个明显相关的因素也考虑进去呢,让这个公式更加精细些?
  答案也是肯定的。
  文章是由词铺排而成,长短不同,所包含的词的个数也就有多有少。
  我们可以考虑在统计文档个数时,为每个文档引入包含多少个词这样一个权重,以区别长短不同的文档,沿着这个思路,改写一下IDF公式:
  tf-idf
  我们用所有文档中的词做成词库,那么上式中:
  tf-idf
  综合上面的推导过程,我们知道,本文所定义的词权重公式,本质上是tf-idf为长短文档引入权重的加强版,而该公式的应用也极为简单,只需要从词库中读取该词词频、词库总词频即可。
  时间复杂度最快可达O(1)级,比如词库以Hash表存储。
  关于TF-IDF更完整的介绍及主流用法,建议参看阮一峰老师的博文《TF-IDF与余弦相似性的应用(一):自动提取关键词》。

四、公式应用

    词权重用途很广,几乎词袋类算法中,都可以考虑使用。常见的应用有:
     1、关键词抽取、自动标签生成
        作法都很简单,分词后排除停用词,然后按权重值排序,取排在前面的若干个词即可。
     2、文本摘要
        完整的文本摘要功能实现很复杂也很困难,这里所指,仅是简单应用:由前面推导过程中可知,句子的权重等于分词结果各词的权重之和,从而获得句子的权重排序。
     3、相似度计算
        相似度计算,我们将在下一篇文中单独介绍。

五、演示程序

  在演示程序显示词库结果时,是按本文所介绍的权重公式排序的。
  演示程序与词库生成的相同:
  特别感谢:王斌老师指出,本文公式实质上是TF-ICF。

六、联系方式:

  1、QQ:老憨 244589712
  2、邮箱:gzdmcaoyc@163.com
发表在 自然语言处理 | 标签为 , , | 2条评论

非主流自然语言处理——遗忘算法系列(三):分词

一、前言

  前面介绍了词库的自动生成的方法,本文介绍如何利用前文所生成的词库进行分词。

二、分词的原理

  分词的原理,可以参看吴军老师《数学之美》中的相关章节,这里摘取Google黑板报版本中的部分:
  分词原理
  从上文中,可以知道分词的任务目标:给出一个句子S,找到一种分词方案,使下面公式中的P(S)最大:
  分词原理
  不过,联合概率求起来很困难,这种情况我们通常作马尔可夫假设,以简化问题,即:任意一个词wi的出现概率只同它前面的词 wi-1 有关。
  关于这个问题,吴军老师讲的深入浅出,整段摘录如下:
  分词原理
  另外,如果我们假设一个词与其他词都不相关,即相互独立时,此时公式最简,如下:
  分词原理
  这个假设分词无关的公式,也是本文所介绍的分词算法所使用的。

三、算法分析

  问:假设分词结果中各词相互无关是否可行?
  答:可行,前提是使用遗忘算法系列(二)中所述方法生成的词库,理由如下:
  分析ICTCLAS广受好评的分词系统的免费版源码,可以发现,在这套由张华平、刘群两位博士所开发分词系统的算法中假设了:分词结果中词只与其前面的一个词有关。
  回忆我们词库生成的过程可以知道,如果相邻的两个词紧密相关,那么这两个词会连为一个粗粒度的词被加入词库中,如:除“清华”、“大学”会是单独的词外,“清华大学”也会是一个词,分词过程中具体选用那种,则由它们的概率来决定。
  也就是说,我们在生成词库的同时,已经隐含的完成了相关性训练。
  关于ICTCLAS源码分析的文章,可以参看吕震宇博文:《天书般的ICTCLAS分词系统代码》。
  问:如何实现分词?
  答:基于前文生成的词库,我们可以假设分词结果相互无关,分词过程就比较简单,使用下面的步骤可以O(N)级时间,单遍扫描完成分词:
  逐字扫描句子,从词库中查出限定字长内,以该字结尾的所有词,分别计算其中的词与该词之前各词的概率乘积,取结果值最大的词,分别缓存下当前字所在位置的最大概率积,以及对应的分词结果。
  重复上面的步骤,直到句子扫描完毕,最后一字位置所得到即为整句分词结果。
  3、算法特点
    3.1、无监督学习;
    3.2、O(N)级时间复杂度;
    3.3、词库自维护,程序可无需人工参与的情况下,自行发现并添加新词、调整词频、清理错词、移除生僻词,保持词典大小适当;
    3.4、领域自适应:领域变化时,词条、词频自适应的随之调整;
    3.5、支持多语种混合分词。

四、演示程序下载

  演示程序与词库生成的相同:

五、联系方式:

  1、QQ:老憨 244589712
  2、邮箱:gzdmcaoyc@163.com
发表在 自然语言处理 | 标签为 , , , , | 18条评论

非主流自然语言处理——遗忘算法系列(二):大规模语料词库生成

一、前言

  本文介绍利用牛顿冷却模拟遗忘降噪,从大规模文本中无监督生成词库的方法。

二、词库生成

    算法分析,先来考虑以下几个问题
    问:目标是从文本中抽取词语,是否可以考虑使用遗忘的方法呢?
    答:可以,词语具备以相对稳定周期重复再现的特征,所以可以考虑使用遗忘的方法。这意味着,我们只需要找一种适当的方法,将句子划分成若干子串,这些子串即为“候选词”。在遗忘的作用下,如果“候选词”会周期性重现,那么它就会被保留在词库中,相反如果只是偶尔或随机出现,则会逐渐被遗忘掉。
    问:那用什么方法来把句子划分成子串比较合适呢?
    答:考察句中任意相邻的两个字,相邻两字有两种可能:要么同属于一个共同的词,要么是两个词的边界。我们都会有这样一种感觉,属于同一个词的相邻两字的“关系”肯定比属于不同词的相邻两字的“关系”要强烈一些。
    数学中并不缺少刻划“关系”的模型,这里我们选择公式简单并且参数容易统计的一种:如果两个字共现的概率大于它们随机排列在一起的概率,那么我们认为这两个字有关,反之则无关。
    如果相邻两字无关,就可以将两字中间断开。逐字扫描句子,如果相邻两字满足下面的公式,则将两字断开,如此可将句子切成若干子串,从而获得“候选词”集,判断公式如下图所示:
    切片公式
    公式中所需的参数可以通过统计获得:遍历一次语料,即可获得公式中所需的“单字的频数”、“相邻两字共现的频数”,以及“所有单字的频数总和”。
    问:如何计算遗忘剩余量?
    答:使用牛顿冷却公式,各参数在遗忘算法中的含义,如下图所示:
    牛顿冷却公式的详情说明,可以参考阮一峰老师的博文《基于用户投票的排名算法(四):牛顿冷却定律》。
    牛顿冷却公式
    问:参数中时间是用现实时间吗,遗忘系数取多少合适呢?
    答:a、关于时间:
      可以使用现实时间,遗忘的发生与现实同步。
      也可以考虑用处理语料中对象的数量来代替,这样仅当有数据处理时,才会发生遗忘。比如按处理的字数为计时单位,人阅读的速度约每秒5至7个字,当然每个人的阅读速度并不相同,这里的参数值要求并不需要特别严格。
      b、遗忘系数可以参考艾宾浩斯曲线中的实验值,如下图(来自互联网)
    艾宾浩斯遗忘曲线
      我们取6天记忆剩余量约为25.4%这个值,按每秒阅读7个字,将其代入牛顿冷却公式可以求得遗忘系数:
    遗忘系数
      注意艾宾浩斯曲线中的每组数值代入公式,所得的系数并不相同,会对词库的最大有效容量产生影响。

二、该算法生成词库的特点

    3.1、无监督学习
    3.2、O(N)级时间复杂度
    3.3、训练、执行为同一过程,可无缝处理流式数据
    3.4、未登录词、新词、登录词没有区别
    3.5、领域自适应:领域变化时,词条、词频自适应的随之调整
    3.6、算法中仅使用到频数这一语言的共性特征,无需对任何字符做特别处理,因此原理上跨语种。
三、词库成熟度
  由于每个词都具备一个相对稳定的重现周期,不难证明,当训练语料达到一定规模后,在遗忘的作用下,每个词的词频在衰减和累加会达到平衡,也即衰减的速度与增加的速度基本一致。成熟的词库,词频的波动相对会比较小,利用这个特征,我们可以衡量词库的成熟程度。
四、源码(C#)、演示程序下载
  使用内附语料(在“可直接运行的演示程序”下可以找到)生成词库效果如下:
  演示程序
五、联系方式:
  1、QQ:老憨 244589712
  2、邮箱:gzdmcaoyc@163.com
发表在 自然语言处理 | 标签为 , , , , | 10条评论

非主流自然语言处理——遗忘算法系列(一):算法概述

一、前言

  这里“遗忘”不是笔误,这个系列要讲的“遗忘算法”,是以牛顿冷却公式模拟遗忘为基础、用于自然语言处理(NLP)的一类方法的统称,而不是大名鼎鼎的“遗传算法”!

  在“遗忘”这条非主流自然语言处理路上,不知不觉已经摸索了三年有余,遗忘算法也算略成体系,虽然仍觉时机未到,还是决定先停一下,将脑中所积梳理成文,交由NLP的同好们点评交流。

二、遗忘算法原理

  能够从未知的事物中发现关联、提炼规律才是真正智能的标志,而遗忘正是使智能生物具备这一能力的工具,也是适应变化的利器,“遗忘”这一颇具负能量特征的家伙是如何实现发现规律这么个神奇魔法的呢?

  让我们从巴甫洛夫的狗说起:狗听到铃声就知道开饭了。

  铃声和开饭之间并不存在必然的联系,我们知道之所以狗会将两者联系在一起,是因为巴甫洛夫有意的将两者一次次在狗那儿重复共现。所以,重复是建立关联的必要条件。

  我们还可以想像,狗在进食的时候听到的声音可能还有鸟叫声、风吹树叶的沙沙声,为什么这些同样具备重复特征声音却没有和开饭建立关系呢?

  细分辨我们不难想到:铃声和开饭之间不仅重复共现,而且这种重复共现还具备一个相对稳定的周期,而其他的那些声音和开饭的共现则是随机的。

  那么遗忘又在其中如何起作用的呢?

    1、所有事物一视同仁的按相同的规律进行遗忘;

    2、偶尔或随机出现的事物因此会随时间而逐渐淡忘;

    3、而具有相对稳定周期重复再现的事物,虽然也按同样的规律遗忘,但由于周期性的得到补充,从而可以动态的保留在记忆中。

  在自然语言处理中,很多对象比如:词、词与词的关联、模板等,都具备按相对稳定重现的特征,因此非常适用遗忘来处理。

三、牛顿冷却公式

  那么,我们用什么来模拟遗忘呢?

  提到遗忘,很自然的会想到艾宾浩斯遗忘曲线,如果这条曲线有个函数形式,那么无疑是模拟遗忘的最佳建模选择。遗憾的是它只是一组离散的实验数据,但至少让我们知道,遗忘是呈指数衰减的。

  另外有一个事实,有的人记性好些,有的人记性则差些,不同人之间的遗忘曲线是不同的,但这并不会从本质上影响不同人对事物的认知,也就是说,如果存在一个遗忘函数,它首先是指数形式的,其次在实用过程中,该函数的系数并不那么重要。

  这提醒我们,可以尝试用一些指数形式的函数来代替遗忘曲线,然后用实践去检验,如果能满足工程实用就很好,这样的函数公式并不难找,比如:退火算法、半衰期公式等。

  有次在阮一峰老师的博客上看关于帖子热度排行的算法时,其中一种方法使用的是牛顿冷却定律,遗忘与冷却有着相似的过程、简洁优美的函数形式、而且参数只与时间相关,这些都让我本能想到,它就是我想要的“遗忘公式”。

  在实践检验中,牛顿冷却公式,确实有效好用,当然,不排除有其他更佳公式。

四、已经实现的功能

  如果把自然语言处理比作从矿砂中淘金子,那么业界主流算法的方向是从矿砂中将金砂挑出来,而遗忘算法的方向则是将砂石筛出去,虽然殊途但同归,所处理的任务也都是主流中所常见。

  本系列文章将逐一讲解遗忘算法如何以O(N)级算法性能实现:

  1、大规模语料词库生成
    1.1、跨语种,算法语种无关,比如:中日韩、少数民族等语种均可支持
    1.2、未登录词发现(只要符合按相对稳定周期性重现的词汇都会被收录)
    1.3、领域自适应,切换不同领域的训练文本时,词条、词频自行调整
    1.4、词典成熟度:可以知道当前语料训练出的词典的成熟程度

  2、分词(基于上述词库技术)
    2.1、成长性分词:用的越多,切的越准
    2.2、词典自维护:切词的同时动态维护词库的词条、词频、登录新词
    2.2、领域自适应、跨语种(继承自词库特性)

  3、词权值计算
    3.1、关键词提取、自动标签
    3.2、文章摘要
    3.3、长、短文本相似度计算
    3.4、主题词集

五、联系方式:

  1、QQ:老憨 244589712

  2、邮箱:gzdmcaoyc@163.com

发表在 自然语言处理 | 标签为 , , | 留下评论