科学空间|Scientific Spaces

在小学的时候，数学老师就教我们除法运算：

被除数 = 除数 × 商 + 余数

其中，余数要小于除数。不过，我们也许未曾想到过，这一运算的成立，几乎是自然数$\mathbb{N}$所有算术（数论）运算性质成立的基础！在代数中，上面的运算等式称为带余除法（division algorithm）。如果在一个整环中成立带余除法，那么该整环几乎就拥有了所有理想的性质，比如唯一分解性，也就是我们说的算术基本定理。这样的一个整环，被称为唯一分解整环（Unique factorization domain）。

欧几里得整环

Euklid-von-Alexandria_1

唯一分解定理说的是在一个整环之中，所有的元素都可以分解为该整环的某些“素元素”之积，并且在不考虑元素相乘的顺序和相差单位数的意义之下，分解形式是唯一的。我们通常说的自然数就成立唯一分解定理，比如$60=2^2\times 3\times 5$，这种分解是唯一的，这看起来相当显然，但实际上唯一分解定理相当不显然。首先，并不是所有的整数环都成立唯一分解定理的，我们考虑所有偶数组成的环$2\mathbb{Z}$，要注意，在$2\mathbb{Z}$中，2、6、10、30都是素数，因为它们无法分解成两个偶数的乘积了，但是$60=6\times 10=2\times 30$，存在两种不同的分解，因此在这样的数环中，唯一分解定理就不成立了。

点击阅读全文...

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

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

研究背景

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

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

点击阅读全文...

最新更新：《用Numpy实现高效的Apriori算法》

最近在做数据挖掘相关的工作，阅读到了Apriori算法。平时由于没有涉及到相关领域，因此对Apriori算法并不了解，而如今工作上遇到了，就不得不认真学习一下了。Apriori算法是一个寻找关联规则的算法，也就是从一大批数据中找到可能的逻辑，比如“条件A+条件B”很有可能推出“条件C”（A+B-->C），这就是一个关联规则。具体来讲，比如客户买了A商品后，往往会买B商品（反之，买了B商品不一定会买A商品），或者更复杂的，买了A、B两种商品的客户，很有可能会再买C商品（反之也不一定）。有了这些信息，我们就可以把一些商品组合销售，以获得更高的收益。而寻求关联规则的算法，就是关联分析算法。

啤酒与尿布

啤酒与尿布

关联算法的案例中，最为人老生常谈的应该是“啤酒与尿布”了。“啤酒与尿布”的故事产生于20世纪90年代的美国沃尔玛超市中，超市管理人员发现“啤酒与尿布两件看上去毫无关系的商品会经常出现在同一个购物篮中”。经过分析，原来在美国有婴儿的家庭中，一般是母亲在家中照看婴儿，年轻的父亲前去超市购买尿布。父亲在购买尿布的同时，往往会顺便为自己购买啤酒，这样就会出现啤酒与尿布这两件看上去不相干的商品经常会出现在同一个购物篮的现象。因此，沃尔玛尝试将啤酒与尿布摆放在相同的区域，让年轻的父亲可以同时找到这两件商品。事实是效果相当不错！

点击阅读全文...

上集回顾

在上一篇文章中，笔者分享了自己对最大熵原理的认识，包括最大熵原理的意义、最大熵原理的求解以及一些简单而常见的最大熵原理的应用。在上一篇的文末，我们还通过最大熵原理得到了正态分布，以此来说明最大熵原理的深刻内涵和广泛意义。

本文中，笔者将介绍基于最大熵原理的模型——最大熵模型。本文以有监督的分类问题来介绍最大熵模型，所谓有监督，就是基于已经标签好的数据进行的。

事实上，第二篇文章的最大熵原理才是主要的，最大熵模型，实质上只是最大熵原理的一个延伸，或者说应用。

最大熵模型

分类：意味着什么？

在引入最大熵模型之前，我们先来多扯一点东西，谈谈分类问题意味着什么。假设我们有一批标签好的数据：
$$\begin{array}{c|cccccccc}
\hline
\text{数据}x & 1 & 2 & 3 & 4 & 5 & 6 & \dots & 100 \\
\hline
\text{标签}y & 1 & 0 & 1 & 0 & 1 & 0 & \dots & 0\\
\hline \end{array}$$

点击阅读全文...

如果一直关注科学空间的朋友会发现，笔者一直对极值原理有偏爱。比如，之前曾经写过一系列《自然极值》的文章，介绍一些极值问题和变分法；在物理学中，笔者偏爱最小作用量原理的形式；在数据挖掘中，笔者也因此对基于最大熵原理的最大熵模型有浓厚的兴趣；最近，在做《量子力学与路径积分》的习题中，笔者也对第十一章所说的变分原理产生了很大的兴趣。

对于一样新东西，笔者的学习方法是以一个尽可能简单的例子搞清楚它的原理和思想，然后再逐步复杂化，这样子我就不至于迷失了。对于变分原理，它是估算路径积分的一个很强大的方法，路径积分是泛函积分，或者说，无穷维积分，那么很自然想到，对于有限维的积分估计，比如最简单的一维积分，有没有类似的估算原理呢？事实上是有的，它并不复杂，弄懂它有助于了解变分原理的核心思想。很遗憾，我并没有找到已有的资料描述这个简化版的原理，可能跟我找的资料比较少有关。

从高斯型积分出发

变分原理本质上是Jensen不等式的应用。我们从下述积分出发
$$\begin{equation}\label{jifen}I(\epsilon)=\int_{-\infty}^{\infty}e^{-x^2-\epsilon x^4}dx\end{equation}$$

点击阅读全文...

前段时间在潮州给韩师的同学讲文本挖掘之余，涉猎到了Boosting学习算法，并且做了一番头脑风暴，最后把Boosting学习算法的一些本质特征思考清楚了，而且得到一些意外的结果，比如说AdaBoost算法的一些理论证明也可以用来解释神经网络模型这么强大。

AdaBoost算法

Boosting学习，属于组合模型的范畴，当然，与其说它是一个算法，倒不如说是一种解决问题的思路。以有监督的分类问题为例，它说的是可以把弱的分类器（只要准确率严格大于随机分类器）通过某种方式组合起来，就可以得到一个很优秀的分类器（理论上准确率可以100%）。AdaBoost算法是Boosting算法的一个例子，由Schapire在1996年提出，它构造了一种Boosting学习的明确的方案，并且从理论上给出了关于错误率的证明。

以二分类问题为例子，假设我们有一批样本$\{x_i,y_i\},i=1,2,\dots,n$，其中$x_i$是样本数据，有可能是多维度的输入，$y_i\in\{1,-1\}$为样本标签，这里用1和-1来描述样本标签而不是之前惯用的1和0，只是为了后面证明上的方便，没有什么特殊的含义。接着假设我们已经有了一个弱分类器$G(x)$，比如逻辑回归、SVM、决策树等，对分类器的唯一要求是它的准确率要严格大于随机（在二分类问题中就是要严格大于0.5），所谓严格大于，就是存在一个大于0的常数$\epsilon$，每次的准确率都不低于$\frac{1}{2}+\epsilon$。

点击阅读全文...

现在我们来关注黎曼曲率。总的来说，黎曼曲率提供了一种方案，让身处空间内部的人也能计算自身所处空间的弯曲程度。俗话说，“不识庐山真面目，只缘身在此山中”，还有“当局者迷，旁观者清”，等等，因此，能够身处空间之中而发现空间中的弯曲与否，是一件很了不起的事情，就好像我们已经超越了我们现有的空间，到了更高维的空间去“居高临下”那样。真可谓“心有多远，路就有多远，世界就有多远”。

如果站在更高维空间的角度看，就容易发现空间的弯曲。比如弯曲空间中有一条测地线，从更高维的空间看，它就是一条曲线，可以计算曲率等，但是在原来的空间看，它就是直的，测地线就是直线概念的一般化，因此不可能通过这种途径发现空间的弯曲性，必须有一些迂回的途径。可能一下子不容易想到，但是各种途径都殊途同归后，就感觉它是显然的了。

怎么更好地导出黎曼曲率来，使得它能够明显地反映出弯曲空间跟平直空间的本质区别呢？为此笔者思考了很长时间，看了不少参考书（《引力与时空》、《场论》、《引力论》等），比较了几种导出黎曼曲率的方式，简要叙述如下。

点击阅读全文...

PS：本文就是梳理了梯度下降与EM算法的关系，通过同一种思路，推导了普通的梯度下降法、pLSA中的EM算法、K-Means中的EM算法，以此表明它们基本都是同一个东西的不同方面，所谓“横看成岭侧成峰，远近高低各不同”罢了。

在机器学习中，通常都会将我们所要求解的问题表示为一个带有未知参数的损失函数(Loss)，如平均平方误差（MSE），然后想办法求解这个函数的最小值，来得到最佳的参数值，从而完成建模。因将函数乘以-1后，最大值也就变成了最小值，因此一律归为最小值来说。如何求函数的最小值，在机器学习领域里，一般会流传两个大的方向：1、梯度下降；2、EM算法，也就是最大期望算法，一般用于复杂的最大似然问题的求解。

在通常的教程中，会将这两个方法描述得迥然不同，就像两大体系在分庭抗礼那样，而EM算法更是被描述得玄乎其玄的感觉。但事实上，这两个方法，都是同一个思路的不同例子而已，所谓“本是同根生”，它们就是一脉相承的东西。

让我们，先从远古的牛顿法谈起。

牛顿迭代法

给定一个复杂的非线性函数$f(x)$，希望求它的最小值，我们一般可以这样做，假定它足够光滑，那么它的最小值也就是它的极小值点，满足$f'(x_0)=0$，然后可以转化为求方程$f'(x)=0$的根了。非线性方程的根我们有个牛顿法，所以
\begin{equation}x_{n+1} = x_{n} - \frac{f'(x_n)}{f''(x_n)}\end{equation}

点击阅读全文...