科学空间|Scientific Spaces

前言：一年前国赛的时候，很初级地做了一下B题，做完之后还写了个《碎纸复原：一个人的数学建模》。当时就是对题目很有兴趣，然后通过一天的学习，基本完成了附件一二的代码，对附件三也只是有个概念。而今年我们上的数学建模课，老师把这道题作为大作业让我们做，于是我便再拾起了一年前的那份激情，继续那未完成的一个人的数学建模...

与去年不同的是，这次将所有代码用Python实现了，更简洁，更清晰，甚至可能更高效~~以下是论文全文。

研究背景

2011年10月29日，美国国防部高级研究计划局（DARPA）宣布了一场碎纸复原挑战赛（Shredder Challenge），旨在寻找到高效有效的算法，对碎纸机处理后的碎纸屑进行复原。[1]该竞赛吸引了全美9000支参赛队伍参与角逐，经过一个多月的时间，有一支队伍成功完成了官方的题目。

近年来，碎纸复原技术日益受到重视，它显示了在碎片中“还原真相”的可能性，表明我们可以从一些破碎的片段中“解密”出原始信息来。另一方面，该技术也和照片处理领域中的“全景图拼接技术”有一定联系，该技术是指通过若干张不同侧面的照片，合成一张完整的全景图。因此，分析研究碎纸复原技术，有着重要的意义。

点击阅读全文...

在拙作《“熵”不起：从熵、最大熵原理到最大熵模型（一）》中，笔者从比较“专业”的角度引出了熵，并对熵做了诠释。当然，熵作为不确定性的度量，应该具有更通俗、更形象的来源，本文就是试图补充这一部分，并由此给出一些妙用。

熵的形象来源

我们考虑由0-9这十个数字组成的自然数，如果要求小于10000的话，那么很自然有10000个，如果我们说“某个小于10000的自然数”，那么0～9999都有可能出现，那么10000便是这件事的不确定性的一个度量。类似地，考虑$n$个不同元素（可重复使用）组成的长度为$m$的序列，那么这个序列有$n^m$种情况，这时$n^m$也是这件事情的不确定性的度量。

$n^m$是指数形式的，数字可能异常地大，因此我们取了对数，得到$m\log n$，这也可以作为不确定性的度量，它跟我们原来熵的定义是一致的。因为
$$m\log n=-\sum_{i=1}^{n^m} \frac{1}{n^m}\log \frac{1}{n^m}$$

读者可能会疑惑，$n^m$和$m\log n$都算是不确定性的度量，那么究竟是什么原因决定了我们用$m\log n$而不是用$n^m$呢？答案是可加性。取对数后的度量具有可加性，方便我们运算。当然，可加性只是便利的要求，并不是必然的。如果使用$n^m$形式，那么就相应地具有可乘性。

点击阅读全文...

前言：这个暑假花了不少时间在中文分词和语言模型上面，碰了无数次壁，也得到了零星收获。打算写一个专题，分享一下心得体会。虽说是专题，但仅仅是一些笔记式的集合，并非系统的教程，请读者见谅。

中文分词

关于中文分词的介绍和重要性，我就不多说了，matrix67这里有一篇关于分词和分词算法很清晰的介绍，值得一读。在文本挖掘中，虽然已经有不少文章探索了不分词的处理方法，如本博客的《文本情感分类（三）：分词 OR 不分词》，但在一般场合都会将分词作为文本挖掘的第一步，因此，一个有效的分词算法是很重要的。当然，中文分词作为第一步，已经被探索很久了，目前做的很多工作，都是总结性质的，最多是微弱的改进，并不会有很大的变化了。

目前中文分词主要有两种思路：查词典和字标注。首先，查词典的方法有：机械的最大匹配法、最少词数法，以及基于有向无环图的最大概率组合，还有基于语言模型的最大概率组合，等等。查词典的方法简单高效（得益于动态规划的思想），尤其是结合了语言模型的最大概率法，能够很好地解决歧义问题，但对于中文分词一大难度——未登录词（中文分词有两大难度：歧义和未登录词），则无法解决；为此，人们也提出了基于字标注的思路，所谓字标注，就是通过几个标记（比如4标注的是：single，单字成词；begin，多字词的开头；middle，三字以上词语的中间部分；end，多字词的结尾），把句子的正确分词法表示出来。这是一个序列（输入句子）到序列（标记序列）的过程，能够较好地解决未登录词的问题，但速度较慢，而且对于已经有了完备词典的场景下，字标注的分词效果可能也不如查词典方法。总之，各有优缺点（似乎是废话～），实际使用可能会结合两者，像结巴分词，用的是有向无环图的最大概率组合，而对于连续的单字，则使用字标注的HMM模型来识别。

点击阅读全文...

关于字标注法

上一篇文章谈到了分词的字标注法。要注意字标注法是很有潜力的，要不然它也不会在公开测试中取得最优的成绩了。在我看来，字标注法有效有两个主要的原因，第一个原因是它将分词问题变成了一个序列标注问题，而且这个标注是对齐的，也就是输入的字跟输出的标签是一一对应的，这在序列标注中是一个比较成熟的问题；第二个原因是这个标注法实际上已经是一个总结语义规律的过程，以4tag标注为为例，我们知道，“李”字是常用的姓氏，一半作为多字词（人名）的首字，即标记为b；而“想”由于“理想”之类的词语，也有比较高的比例标记为e，这样一来，要是“李想”两字放在一起时，即便原来词表没有“李想”一词，我们也能正确输出be，也就是识别出“李想”为一个词，也正是因为这个原因，即便是常被视为最不精确的HMM模型也能起到不错的效果。

关于标注，还有一个值得讨论的内容，就是标注的数目。常用的是4tag，事实上还有6tag和2tag，而标记分词结果最简单的方法应该是2tag，即标记“切分/不切分”就够了，但效果不好。为什么反而更多数目的tag效果更好呢？因为更多的tag实际上更全面概括了语义规律。比如，用4tag标注，我们能总结出哪些字单字成词、哪些字经常用作开头、哪些字用作末尾，但仅仅用2tag，就只能总结出哪些字经常用作开头，从归纳的角度来看，是不够全面的。但6tag跟4tag比较呢？我觉得不一定更好，6tag的意思是还要总结出哪些字作第二字、第三字，但这个总结角度是不是对的？我觉得，似乎并没有哪些字固定用于第二字或者第三字的，这个规律的总结性比首字和末字的规律弱多了（不过从新词发现的角度来看，6tag更容易发现长词。）。

双向LSTM

点击阅读全文...

暑假期间做了一下百度和西安交大联合举办的核心实体识别竞赛，最终的结果还不错，遂记录一下。模型的效果不是最好的，但是胜在“端到端”，迁移性强，估计对大家会有一定的参考价值。

比赛的主题是“核心实体识别”，其实有两个任务：核心识别 + 实体识别。这两个任务虽然有关联，但在传统自然语言处理程序中，一般是将它们分开处理的，而这次需要将两个任务联合在一起。如果只看“核心识别”，那就是传统的关键词抽取任务了，不同的是，传统的纯粹基于统计的思路（如TF-IDF抽取）是行不通的，因为单句中的核心实体可能就只出现一次，这时候统计估计是不可靠的，最好能够从语义的角度来理解。我一开始就是从“核心识别”入手，使用的方法类似QA系统：

1、将句子分词，然后用Word2Vec训练词向量；

2、用卷积神经网络（在这种抽取式问题上，CNN效果往往比RNN要好）卷积一下，得到一个与词向量维度一样的输出；

3、损失函数就是输出向量跟训练样本的核心词向量的cos值。

点击阅读全文...

之前已经写过用LSTM来做分词的方案了，今天再来一篇用CNN的，准确来说是FCN，全卷积网络。其实这个模型的主要目的并非研究中文分词，而是练习tensorflow。从两年前就开始用Keras了，可以说对它比较熟了，也渐渐发现了它的一些不足，比如处理变长输入时不方便、加入自定义的约束比较困难等，所以干脆试试原生的tensorflow了，试了之后发现其实也不复杂。嗯，都是python，能有多复杂。本文就是练习一下如何用tensorflow处理不定长输入任务，以中文分词为例，并在最后加入了硬解码，将深度学习与词典分词结合了起来。

CNN

另外，就是关于FCN的。放到语言任务中看，（一维）卷积其实就是ngram模型，从这个角度来看其实CNN远比RNN来得自然，RNN好像就是为序列任务精心设计的，而CNN则是传统ngram模型的一个延伸。另外不管CNN和RNN都有权值共享，看上去只是为了降低运算量的一个折中选择，但事实上里边大有道理。CNN中的权值共享是平移不变性的必然结果，而不是仅仅是降低运算量的一个选择，试想一下，将一幅图像平移一点点，或者在一个句子前插入一个无意义的空格（导致后面所有字都向后平移了一位），这样应该给出一个相似甚至相同的结果，而这要求卷积必然是权值共享的，即权值不能跟位置有关系。

点击阅读全文...

信息抽取

众所周知，百度知道上有大量的人提了大量的问题，并且得到大量的回复。然而，百度知道上的回复者貌似懒人居多，他们往往喜欢直接在网上复制粘贴一大片来作为回答内容，而且这些内容可能跟问题相关，也可能跟问题不相关，比如

https://zhidao.baidu.com/question/557785746.html

问：广州白云山海拨多高

答：广州白云山（Guangzhou Baiyun Mountain），是新 “羊城八景”之首、国家4A级景区和国家重点风景名胜区。它位于广州市的东北部，为南粤名山之一，自古就有“羊城第一秀”之称。山体相当宽阔，由30多座山峰组成，为广东最高峰九连山的支脉。面积20.98平方公里，主峰摩星岭高382米（注：最新测绘高度为372.6米——国家测绘局，2008年），峰峦重叠，溪涧纵横，登高可俯览全市，遥望珠江。每当雨后天晴或暮春时节，山间白云缭绕，蔚为奇观，白云山之名由此得来

点击阅读全文...

最后，我们来看一下词向量模型$(15)$会有什么好的性质，或者说，如此煞费苦心去构造一个新的词向量模型，会得到什么回报呢？

模长的含义

似乎所有的词向量模型中，都很少会关心词向量的模长。有趣的是，我们上述词向量模型得到的词向量，其模长还能在一定程度上代表着词的重要程度。我们可以从两个角度理解这个事实。

在一个窗口内的上下文，中心词重复出现概率其实是不大的，是一个比较随机的事件，因此可以粗略地认为
\[P(w,w) \sim P(w)\tag{24}\]
所以根据我们的模型，就有
\[e^{\langle\boldsymbol{v}_{w},\boldsymbol{v}_{w}\rangle} =\frac{P(w,w)}{P(w)P(w)}\sim \frac{1}{P(w)}\tag{25}\]
所以
\[\Vert\boldsymbol{v}_{w}\Vert^2 \sim -\log P(w)\tag{26}\]
可见，词语越高频（越有可能就是停用词、虚词等），对应的词向量模长就越小，这就表明了这种词向量的模长确实可以代表词的重要性。事实上，$-\log P(w)$这个量类似IDF，有个专门的名称叫ICF，请参考论文《TF-ICF: A New Term Weighting Scheme for Clustering Dynamic Data Streams》。

点击阅读全文...