科学空间|Scientific Spaces

上一篇文章中，我们比较详细地介绍了Johnson-Lindenstrauss引理（JL引理）的理论推导，这一篇我们来关注它的应用。

作为一个内容上本身就跟降维相关的结论，JL引理最基本的自然就是作为一个降维方法来用。但除了这个直接应用外，很多看似不相关的算法，比如局部敏感哈希（LSH）、随机SVD等，本质上也依赖于JL引理。此外，对于机器学习模型来说，JL引理通常还能为我们的维度选择提供一些理论解释。

降维的工具

JL引理提供了一个非常简单直接的“随机投影”降维思路：

给定$N$个向量$v_1,v_2,\cdots,v_N\in\mathbb{R}^m$，如果想要将它降到$n$维，那么只需要从$\mathcal{N}(0,1/n)$中采样一个$n\times m$矩阵$A$，然后$Av_1,Av_2,\cdots,Av_N$就是降维后的结果。

点击阅读全文...

今天我们来学习Johnson-Lindenstrauss引理，由于名字比较长，下面都简称“JL引理”。

个人认为，JL引理是每一个计算机科学的同学都必须了解的神奇结论之一，它是一个关于降维的著名的结果，它也是高维空间中众多反直觉的“维度灾难”现象的经典例子之一。可以说，JL引理是机器学习中各种降维、Hash等技术的理论基础，此外，在现代机器学习中，JL引理也为我们理解、调试模型维度等相关参数提供了重要的理论支撑。

对数的维度

JL引理，可以非常通俗地表达为：

通俗版JL引理： 塞下$N$个向量，只需要$\mathcal{O}(\log N)$维空间。

点击阅读全文...

这篇文章我们讨论一个编程题：如何更优雅地在Python中实现重试。

在文章《新年快乐！记录一下 Cool Papers 的开发体验》中，笔者分享了开发Cool Papers的一些经验，其中就提到了Cool Papers所需要的一些网络通信步骤。但凡涉及到网络通信，就有失败的风险（谁也无法保证网络不会间歇性抽风），所以重试是网络通信的基本操作。此外，当涉及到多进程、数据库、硬件交互等操作时，通常也需要引入重试机制。

在Python中，实现重试并不难，但如何更加简单而又不失可读性地实现重试，还是有一定技巧的。接下来笔者分享一下自己的尝试。

循环重试

完整的重试流程大致上包含循环重试、异常处理、延时等待、后续操作等部分，其标准写法就是用for循环，用“try ... except ...”来捕捉异常，一个参考代码是：

点击阅读全文...

很早之前，就有读者提出希望把Cool Papers上面的数学公式渲染一下，因为很多偏数学的论文，它们的摘要甚至标题上都带有LaTeX代码写的数学公式，如果不把这些公式渲染出来，那么看上去就像是一堆乱码，确实会比较影响阅读体验。然而，之前的测试显示，负责渲染公式的MathJax跟谷歌翻译和延时加载都不大兼容，所以尽管需求存在已久，但笔者一直没有把它加上去。

不过好消息是，经过反复查阅和调试，这两天笔者总算把兼容性问题解决了，所以现在大家看到的Cool Papers已经能够渲染数学公式了。这篇文章总结一下解决方案，供大家参考。

摘要带有公式的论文

点击阅读全文...

随着MathJax的出现和流行，在网页上显示数学公式便逐渐有了标准答案。然而，MathJax（包括其竞品KaTeX）只是负责将网页LaTeX代码转化为数学公式，对于自适应分辨率方面依然没有太好的办法。像本站一些数学文章，因为是在PC端排版好的，所以在PC端浏览效果尚可，但转到手机上看就可能有点难以入目了。

经过测试，笔者得到了一个方案，让MathJax的数学公式也能像图片一样，随着窗口大小而自适应缩放，从而尽量保证移动端的显示效果，在此跟大家分享一波。

背景思路

这个问题的起源是，即便在PC端进行排版，有时候也会遇到一些单行公式的长度超出了网页宽度，但又不大好换行的情况，这时候一个解决方案是用HTML代码手动调整一下公式的字体大小，比如

<span style="font-size:90%">
    \begin{equation}一个超长的数学公式\end{equation}
</span>

点击阅读全文...

关于字标注法

上一篇文章谈到了分词的字标注法。要注意字标注法是很有潜力的，要不然它也不会在公开测试中取得最优的成绩了。在我看来，字标注法有效有两个主要的原因，第一个原因是它将分词问题变成了一个序列标注问题，而且这个标注是对齐的，也就是输入的字跟输出的标签是一一对应的，这在序列标注中是一个比较成熟的问题；第二个原因是这个标注法实际上已经是一个总结语义规律的过程，以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值。

点击阅读全文...

赛题回顾

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

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

点击阅读全文...