科学空间|Scientific Spaces

赛题回顾

不得不说，2013年的全国数学建模竞赛中的B题真的算是数学建模竞赛中百年难得一遇的好题：题目简洁明了，含义丰富，做法多样，延伸性强，以至于我一直对它念念不忘。因为这个题目，我已经在科学空间写了两篇文章了，分别是《一个人的数学建模：碎纸复原》和《迟到一年的建模：再探碎纸复原》。以前做这道题的时候，还只有一点数学建模的知识，而自从学习了数据挖掘、尤其是深度学习之后，我一直想重做这道题，但一直偷懒。这几天终于把它实现了。

如果对题目还不清楚的读者，可以参考前面两篇文章。碎纸复原共有五个附件，分别代表了五种“碎纸片”，即五种不同粒度的碎片。其中附件1和2都不困难，难度主要集中在附件3、4、5，而3、4、5的实现难度基本是一样的。做这道题最容易想到的思路就是贪心算法，即随便选一张图片，然后找到与它最匹配的图片，然后继续匹配下一张。要想贪心算法有效，最关键是找到一个良好的距离函数，来判断两张碎片是否相邻（水平相邻，这里不考虑垂直相邻）。

点击阅读全文...

跳出单循环

不管是什么编程语言，都有可能会有跳出循环的需求，比如枚举时，找到一个满足条件的数就终止。跳出单循环是很简单的，比如

for i in range(10):
    if i > 5:
        print i
        break

然而，我们有时候会需要跳出多重循环，而break只能够跳出一层循环，比如

for i in range(10):
    for j in range(10):
        if i+j > 5:
            print i,j
            break

这样的代码并非说找到一组i+j > 5就停止，而是连续找到10组，因为break只跳出了for j in range(10)这一重循环。那么，怎么才能跳出多重呢？在此记录备忘一下。

点击阅读全文...

中文语料库中，质量高而又容易获取的语料库，应该就是维基百科的中文语料了，而且维基百科相当厚道，每个月都把所有条目都打包一次（下载地址在这里：https://dumps.wikimedia.org/zhwiki/），供全世界使用，这才是真正的“取之于民，回馈于民”呀。遗憾的是，由于天朝的无理封锁，中文维基百科的条目到目前只有91万多条，而百度百科、互动百科都有千万条了（英文维基百科也有上千万了）。尽管如此，这并没有阻挡中文维基百科成为几乎是最高质量的中文语料库。（百度百科、互动百科它们只能自己用爬虫爬取，而且不少记录质量相当差，几乎都是互相复制甚至抄袭。）

门槛

尽量下载很容易，但是使用维基百科语料还是有一定门槛的。直接下载下来的维基百科语料是一个带有诸多html和markdown标记的文本压缩包，基本不能直接使用。幸好，已经有热心的高手为我们写好了处理工具，主要有两个：1、Wikipedia Extractor；2、gensim的wikicorpus库。它们都是基于python的。

然而，这两个主流的处理方法都不能让我满意。首先，Wikipedia Extractor提取出来的结果，会去掉{{}}标记的内容，这样会导致下面的情形

西方语言中“数学”（；）一词源自于古希腊语的（）

点击阅读全文...

这个系列慢慢写到第7篇，基本上也把分词的各种模型理清楚了，除了一些细微的调整（比如最后的分类器换成CRF）外，剩下的就看怎么玩了。基本上来说，要速度，就用基于词典的分词，要较好地解决组合歧义何和新词识别，则用复杂模型，比如之前介绍的LSTM、FCN都可以。但问题是，用深度学习训练分词器，需要标注语料，这费时费力，仅有的公开的几个标注语料，又不可能赶得上时效，比如，几乎没有哪几个公开的分词系统能够正确切分出“扫描二维码，关注微信号”来。

本文就是做了这样的一个实验，仅用一个词典，就完成了一个深度学习分词器的训练，居然效果还不错！这种方案可以称得上是半监督的，甚至是无监督的。

点击阅读全文...

提前祝各位读者新年快乐，2017行好运～

这篇文章主要想回答两个“为什么”的问题：1、为啥我就对SVD感兴趣了？；2、为啥我说SVD是一个聚类过程？回答的内容纯粹个人思辨结果，暂无参考文献。

为什么要研究SVD？

从2015年接触深度学习到现在，已经研究了快两年的深度学习了，现在深度学习、数据科学等概念也遍地开花。为什么在深度学习火起来的时候，我反而要回去研究“古老”的SVD分解呢？我觉得，SVD作为一个矩阵分解算法，它的价值不仅仅体现在它广泛的应用，它背后还有更加深刻的内涵，即它的可解释性。在深度学习流行的今天，不少人还是觉得深度学习（神经网络）就是一个有效的“黑箱”模型。但是，仅用“黑箱”二字来解释深度学习的有效性显然不能让人满意。前面已经说过，SVD分解本质上与不带激活函数的三层自编码机等价，理解SVD分解，能够为神经网络模型寻求一个合理的概率解释。

点击阅读全文...

过程

在Python中，如果要多进程运算，一般是通过multiprocessing来实现的，常用的是multiprocessing中的进程池，比如：

from multiprocessing import Pool
import time

def f(x):
    time.sleep(1)
    print x+1
    return x+1

a = range(10)
pool = Pool(4)
b = pool.map(f, a)
pool.close()
pool.join()

print b

这样写简明清晰，确实方便，有趣的是，只需要将multiprocessing换成multiprocessing.dummy，就可以将程序从多进程改为多线程了。

点击阅读全文...

这篇文章要带来一个“重磅”消息，如标题所示，居然连大名鼎鼎的深度学习词向量工具Word2Vec都只不过是个SVD！

当然，Word2Vec的超级忠实粉丝们，你们也不用太激动，这里只是说模型结构上是等价的，并非完全等价，Word2Vec还是有它的独特之处。只不过，经过我这样解释之后，估计很多问题就可以类似想通了。

词向量=one hot

让我们先来回顾一下去年的一篇文章《词向量与Embedding究竟是怎么回事？》，这篇文章主要说的是：所谓Embedding层，就是一个one hot的全连接层罢了（再次强调，这里说的完全等价，而不是“相当于”），而词向量，就是这个全连接层的参数；至于Word2Vec，就通过大大简化的语言模型来训练Embedding层，从而得到词向量（它的优化技巧有很多，但模型结构就只是这么简单）；词向量能够减少过拟合风险，是因为用Word2Vec之类的工具、通过大规模语料来无监督地预训练了这个Embedding层，而跟one hot还是Embedding还是词向量本身没啥关系。

有了这个观点后，马上可以解释我们以前的一个做法为什么可行了。在做情感分类问题时，如果有了词向量，想要得到句向量，最简单的一个方案就是直接对句子中的词语的词向量求和或者求平均，这约能达到85%的准确率。事实上这也是facebook出品的文本分类工具FastText的做法了（FastText还多引入了ngram特征，来缓解词序问题，但总的来说，依旧是把特征向量求平均来得到句向量）。为什么这么一个看上去毫不直观的、简单粗暴的方案也能达到这么不错的准确率？

点击阅读全文...

如果依次阅读该系列文章的读者，就会发现这个系列共提供了两种从0到1的无监督分词方案，第一种就是《【中文分词系列】 2. 基于切分的新词发现》，利用相邻字凝固度（互信息）来做构建词库（有了词库，就可以用词典法分词）；另外一种是《【中文分词系列】 5. 基于语言模型的无监督分词》，后者基本上可以说是提供了一种完整的独立于其它文献的无监督分词方法。

但总的来看，总感觉前面一种很快很爽，却又显得粗糙；后面一种很好很强大，却又显得太过复杂（viterbi是瓶颈之一）。有没有可能在两者之间折中一下？这就导致了本文的结果，达到了速度与效果的平衡。至于为什么说“更好”？因为笔者研究词库构建也有一段时间了，以往构建的词库总不能让人（让自己）满意，生成的词库一眼看上去，都能够扫到不少不合理的地方，真的要用得需要经过较多的人工筛选。而这一次，一次性生成的词库，一眼扫过去，不合理的地方少了很多，如果不细看，可能就发现不了了。

分词的目的

点击阅读全文...