25
Nov
三顾碎纸复原：基于CNN的碎纸复原
By 苏剑林 | 2016-11-25 | 39964位读者 | 引用赛题回顾
不得不说，2013年的全国数学建模竞赛中的B题真的算是数学建模竞赛中百年难得一遇的好题：题目简洁明了，含义丰富，做法多样，延伸性强，以至于我一直对它念念不忘。因为这个题目，我已经在科学空间写了两篇文章了，分别是《一个人的数学建模：碎纸复原》和《迟到一年的建模：再探碎纸复原》。以前做这道题的时候，还只有一点数学建模的知识，而自从学习了数据挖掘、尤其是深度学习之后，我一直想重做这道题，但一直偷懒。这几天终于把它实现了。
如果对题目还不清楚的读者，可以参考前面两篇文章。碎纸复原共有五个附件，分别代表了五种“碎纸片”，即五种不同粒度的碎片。其中附件1和2都不困难，难度主要集中在附件3、4、5，而3、4、5的实现难度基本是一样的。做这道题最容易想到的思路就是贪心算法，即随便选一张图片，然后找到与它最匹配的图片，然后继续匹配下一张。要想贪心算法有效，最关键是找到一个良好的距离函数，来判断两张碎片是否相邻（水平相邻，这里不考虑垂直相邻）。
6
Jan
获取并处理中文维基百科语料
By 苏剑林 | 2017-01-06 | 115932位读者 | 引用中文语料库中，质量高而又容易获取的语料库，应该就是维基百科的中文语料了，而且维基百科相当厚道，每个月都把所有条目都打包一次（下载地址在这里：https://dumps.wikimedia.org/zhwiki/），供全世界使用，这才是真正的“取之于民，回馈于民”呀。遗憾的是，由于天朝的无理封锁，中文维基百科的条目到目前只有91万多条，而百度百科、互动百科都有千万条了（英文维基百科也有上千万了）。尽管如此，这并没有阻挡中文维基百科成为几乎是最高质量的中文语料库。（百度百科、互动百科它们只能自己用爬虫爬取，而且不少记录质量相当差，几乎都是互相复制甚至抄袭。）
门槛
尽量下载很容易，但是使用维基百科语料还是有一定门槛的。直接下载下来的维基百科语料是一个带有诸多html和markdown标记的文本压缩包，基本不能直接使用。幸好，已经有热心的高手为我们写好了处理工具，主要有两个：1、Wikipedia Extractor；2、gensim的wikicorpus库。它们都是基于python的。
然而，这两个主流的处理方法都不能让我满意。首先，Wikipedia Extractor提取出来的结果，会去掉{{}}标记的内容，这样会导致下面的情形
西方语言中“数学”（；）一词源自于古希腊语的（）
23
Feb
SVD分解(三)：连Word2Vec都只不过是个SVD？
By 苏剑林 | 2017-02-23 | 102679位读者 | 引用这篇文章要带来一个“重磅”消息，如标题所示，居然连大名鼎鼎的深度学习词向量工具Word2Vec都只不过是个SVD！
当然，Word2Vec的超级忠实粉丝们，你们也不用太激动，这里只是说模型结构上是等价的，并非完全等价，Word2Vec还是有它的独特之处。只不过，经过我这样解释之后，估计很多问题就可以类似想通了。
词向量=one hot
让我们先来回顾一下去年的一篇文章《词向量与Embedding究竟是怎么回事？》，这篇文章主要说的是：所谓Embedding层，就是一个one hot的全连接层罢了（再次强调，这里说的完全等价，而不是“相当于”），而词向量，就是这个全连接层的参数；至于Word2Vec，就通过大大简化的语言模型来训练Embedding层，从而得到词向量（它的优化技巧有很多，但模型结构就只是这么简单）；词向量能够减少过拟合风险，是因为用Word2Vec之类的工具、通过大规模语料来无监督地预训练了这个Embedding层，而跟one hot还是Embedding还是词向量本身没啥关系。
有了这个观点后，马上可以解释我们以前的一个做法为什么可行了。在做情感分类问题时，如果有了词向量，想要得到句向量，最简单的一个方案就是直接对句子中的词语的词向量求和或者求平均，这约能达到85%的准确率。事实上这也是facebook出品的文本分类工具FastText的做法了（FastText还多引入了ngram特征，来缓解词序问题，但总的来说，依旧是把特征向量求平均来得到句向量）。为什么这么一个看上去毫不直观的、简单粗暴的方案也能达到这么不错的准确率？
11
Mar
【中文分词系列】 8. 更好的新词发现算法
By 苏剑林 | 2017-03-11 | 245615位读者 | 引用如果依次阅读该系列文章的读者，就会发现这个系列共提供了两种从0到1的无监督分词方案，第一种就是《【中文分词系列】 2. 基于切分的新词发现》，利用相邻字凝固度（互信息）来做构建词库（有了词库，就可以用词典法分词）；另外一种是《【中文分词系列】 5. 基于语言模型的无监督分词》，后者基本上可以说是提供了一种完整的独立于其它文献的无监督分词方法。
但总的来看，总感觉前面一种很快很爽，却又显得粗糙；后面一种很好很强大，却又显得太过复杂（viterbi是瓶颈之一）。有没有可能在两者之间折中一下？这就导致了本文的结果，达到了速度与效果的平衡。至于为什么说“更好”？因为笔者研究词库构建也有一段时间了，以往构建的词库总不能让人（让自己）满意，生成的词库一眼看上去，都能够扫到不少不合理的地方，真的要用得需要经过较多的人工筛选。而这一次，一次性生成的词库，一眼扫过去，不合理的地方少了很多，如果不细看，可能就发现不了了。
分词的目的
4
May
记录一次半监督的情感分析
By 苏剑林 | 2017-05-04 | 55100位读者 | 引用本文是一次不怎么成功的半监督学习的尝试：在IMDB的数据集上，用随机抽取的1000个标注样本训练一个文本情感分类模型，并且在余下的49000个测试样本中，测试准确率为73.48%。
思路
本文的思路来源于OpenAI的这篇文章：
《OpenAI新研究发现无监督情感神经元：可直接调控生成文本的情感》
文章里边介绍了一种无监督（实际上是半监督）做情感分类的模型的方法，并且实验效果很好。然而文章里边的实验很庞大，对于个人来说几乎不可能重现（在4块Pascal GPU花了1个月时间训练）。不过，文章里边的思想是很简单的，根据里边的思想，我们可以做个“山寨版”的。思路如下：
我们一般用深度学习做情感分类，比较常规的思路就是Embedding层+LSTM层+Dense层(Sigmoid激活)，我们常说的词向量，相当于预训练了Embedding层（这一层的参数量最大，最容易过拟合），而OpenAI的思想就是，为啥不连LSTM层一并预训练了呢？预训练的方法也是用语言模型来训练。当然，为了使得预训练的结果不至于丢失情感信息，LSTM的隐藏层节点要大一些。
6
Jun
通用爬虫探索（一）：适用一般网站的爬虫
By 苏剑林 | 2017-06-06 | 39927位读者 | 引用这是笔者参加今年的泰迪杯C题的论文简化版。虽然最后只评上了一个安慰奖，但个人感觉里边有些思路对爬虫工作还是有些参加价值的。所以还是放出来供大家参考一下。
简介
一个爬虫可以分为两个步骤：1.把网页下载下来；2.从网页中把所需要的信息抽取出来。这两个步骤都存在相应的技术难点。对于第一个步骤，难度在于如何应对各大网站的反爬虫措施，如访问频率过高则封IP或者给出验证码等，这需要根据不同网站的不同反爬虫措施来设计，理论上不存在通用的可能性。对于第二个步骤，传统的做法是设计对应的正则表达式，随着网站设计上日益多样化，正则表达式的写法也相应变得困难。
显然，想要得到一个通用的爬虫方案，用传统的正则表达式的方案是相当困难的。但如果我们跳出正则表达式的思维局限，从全局的思维来看网站，结合DOM树来解析，那么可以得到一个相当通用的方案。因此，本文的主要内容，是围绕着爬虫的第二个步骤进行展开。本文的工作分为两个部分进行：首先，提出了一个适用于一般网站的信息抽取方案，接着，将这个方案细化，落实到论坛的信息抽取上。
6
Jun
通用爬虫探索（二）：落实到论坛爬取上
By 苏剑林 | 2017-06-06 | 26291位读者 | 引用前述的方案，如果爬取的页面仅仅有单一的有效区域，如博客页、新闻页等，那么基本上来说已经足够了。但是，诸如像论坛这样的具有比较明显的层次划分的网站，我们需要进一步细分。因为经过上述步骤，我们虽然能够把有效文本提取出来，但结果是把所有文本放在一块了。
深度优先
而为了给内容进一步“分块”，我们还需要利用DOM树的位置信息。如上一篇的DOM树图，我们需要给每个节点和叶子都编号，即我们需要一个遍历DOM树的方式。这里我们采用“深度优先”的方案。
深度优先搜索算法（英语：Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
7
Jun
最近评论