科学空间|Scientific Spaces

最近由于数据挖掘上的研究，需要想办法通过电脑远程控制手机（主要是安卓），遂查找了网络上的一些工具，这里记录一下结果，纯粹做备忘。有同样需要的读者可以参考。

之前在阿里云的服务器和树莓派上都做过远程控制的，记得Linux下的远程控制工具叫做VNC，于是我google和百度了vnc server android、vnc server apk等，发现这类工具确实不少，比如最知名的当属droid vnc server。但是同类的几个软件我都测试了，它确实是VNC软件，但是在我的几个安卓4.x上，显示都不正常（花屏），无奈抛弃了。再看一下日期，发现原来这些软件基本到2013年就停止更新了，一般支持到安卓2.3而已，怪不得。

点击阅读全文...

斯特灵近似，或者称斯特灵公式，最开始是作为阶乘的近似提出
$$n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$
符号$\sim$意味着
$$\lim_{n\to\infty}\frac{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n}{n!}=1$$
将斯特灵公式进一步提高精度，就得到所谓的斯特灵级数
$$n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1+\frac{1}{12n}+\frac{1}{288n^2}\dots\right)$$
很遗憾，这个是渐近级数。

相关资料有：
https://zh.wikipedia.org/zh-cn/斯特灵公式

https://en.wikipedia.org/wiki/Stirling%27s_approximation

本文将会谈到斯特灵公式及其渐近级数的一个改进的推导，并解释渐近级数为什么渐近。

点击阅读全文...

路径积分是量子力学的一种描述方法，源于物理学家费曼[5]，它是一种泛函积分，它已经成为现代量子理论的主流形式. 近年来，研究人员对它的兴趣愈发增加，尤其是它在量子领域以外的应用，出现了一些著作，如[7]. 但在国内了解路径积分的人并不多，很多量子物理专业的学生可能并没有听说过路径积分.

从数学角度来看，路径积分是求偏微分方程的Green函数的一种方法. 我们知道，在偏微分方程的研究中，如果能够求出对应的Green函数，那么对偏微分方程的研究会大有帮助，而通常情况下Green函数并不容易求解. 但构建路径积分只需要无穷小时刻的Green函数，因此形式和概念上都相当简单.

本章并没有新的内容，只是做了一个尝试：从随机游走问题出发，给出路径积分的一个简明而直接的介绍，展示了如何将抛物型的偏微分方程问题转化为路径积分形式.

从点的概率到路径的概率

在上一章对随机游走的研究中，我们得出从$x_0$出发，$t$时间后，走到$x_n$处的概率密度为
$$\frac{1}{\sqrt{2\pi \alpha T}}\exp\left(-\frac{(x_n-x_0)^2}{2\alpha t}\right).\tag{22}$$
这是某时刻某点到另一个时刻另一点的概率，在数学上，我们称之为扩散方程$(21)$的传播子，或者Green函数.

点击阅读全文...

逐层识别

当图像有效地进行分层后，我们就可以根据前面的假设，进一步设计相应的模型，通过逐层处理的方式找出图像中的文字区域.

连通性

8邻接

可以看到，每一层的图像是由若干连通区域组成的，文字本身是由笔画较为密集组成的，因此往往文字也能够组成一个连通区域. 这里的连通定义为8邻接，即某个像素周围的8个像素都定义为邻接像素，邻接的像素则被定义为同一个连通区域.

定义了连通区域后，每个图层被分割为若干个连通区域，也就是说，我们逐步地将原始图像进行分解，如图9.

点击阅读全文...

路径积分方法为解决某些随机问题带来了新视角.

一个例子：股票价格模型

考虑有风险资产(如股票)，在$t$时刻其价格为$S_t$，考虑的时间区间为$[0,T]$，0表示初始时间，$T$表示为到期日. $S_t$看作是随时间变化的连续时间变量，并服从下列随机微分方程:
$$dS_t^0=rS_t^0 dt;\quad dS_t=S_t(\mu dt+\sigma dW_t).\tag{70}$$
其中，$\mu$和$\sigma$是两个常量，$W_t$是一个标准布朗运动.

关于$S_t$的方程是一个随机微分方程，一般解决思路是通过随机微积分. 随机微积分有别于一般的微积分的地方在于，随机微积分在做一阶展开的时候，不能忽略$dS_t^2$项，因为$dW_t^2=dt$. 比如，设$S_t=e^{x_t}$，则$x_t=\ln S_t$
$$\begin{aligned}dx_t=&\ln(S_t+dS_t)-\ln S_t=\frac{dS_t}{S_t}-\frac{dS_t^2}{2S_t^2}\\
=&\frac{S_t(\mu dt+\sigma dW_t)}{S_t}-\frac{[S_t(\mu dt+\sigma dW_t)]^2}{2S_t^2}\\
=&\mu dt+\sigma dW_t-\frac{1}{2}\sigma^2 dW_t^2\quad(\text{其余项均低于}dt\text{阶})\\
=&\left(\mu-\frac{1}{2}\sigma^2\right) dt+\sigma dW_t\end{aligned}
,\tag{71}$$

点击阅读全文...

写在前面：前面的博文已经提过，在上个月我参加了第四届泰迪杯数据挖掘竞赛，做的是A题，跟OCR系统有些联系，还承诺过会把最终的结果开源。最近忙于毕业、搬东西，一直没空整理这些内容，现在抽空整理一下。

把结果发出来，并不是因为结果有多厉害、多先进（相反，当我对比了百度的这篇论文《基于深度学习的图像识别进展：百度的若干实践》之后，才发现论文的内容本质上还是传统那一套，远远还跟不上时代的潮流），而是因为虽然OCR技术可以说比较成熟了，但网络上根本就没有对OCR系统进行较为详细讲解的文章，而本文就权当补充这部分内容吧。我一直认为，技术应该要开源才能得到发展（当然，在中国这一点也确实值得商榷，因为开源很容易造成山寨），不管是数学物理研究还是数据挖掘，我大多数都会发表到博客中，与大家交流。

点击阅读全文...

经过第一部分，我们已经较好地提取了图像的文本特征，下面进行文字定位. 主要过程分两步：1、邻近搜索，目的是圈出单行文字；2、文本切割，目的是将单行文本切割为单字.

邻近搜索

我们可以对提取的特征图进行连通区域搜索，得到的每个连通区域视为一个汉字. 这对于大多数汉字来说是适用，但是对于一些比较简单的汉字却不适用，比如“小”、“旦”、“八”、“元”这些字，由于不具有连通性，所以就被分拆开了，如图13. 因此，我们需要通过邻近搜索算法，来整合可能成字的区域，得到单行的文本区域.

图13 直接搜索连通区域，会把诸如“元”之类的字分拆开

邻近搜索的目的是进行膨胀，以把可能成字的区域“粘合”起来. 如果不进行搜索就膨胀，那么膨胀是各个方向同时进行的，这样有可能把上下行都粘合起来了. 因此，我们只允许区域向单一的一个方向膨胀. 我们正是要通过搜索邻近区域来确定膨胀方向(上、下、左、右)：

邻近搜索* 从一个连通区域出发，可以找到该连通区域的水平外切矩形，将连通区域扩展到整个矩形. 当该区域与最邻近区域的距离小于一定范围时，考虑这个矩形的膨胀，膨胀的方向是最邻近区域的所在方向.

既然涉及到了邻近，那么就需要有距离的概念. 下面给出一个比较合理的距离的定义.

距离

图14 两个示例区域

如上图，通过左上角坐标$(x,y)$和右下角坐标$(z,w)$就可以确定一个矩形区域，这里的坐标是以左上角为原点来算的. 这个区域的中心是$\left(\frac{x+w}{2},\frac{y+z}{2}\right)$. 对于图中的两个区域$S$和$S'$，可以计算它们的中心向量差
$$(x_c,y_c)=\left(\frac{x'+w'}{2}-\frac{x+w}{2},\frac{y'+z'}{2}-\frac{y+z}{2}\right)\tag{10}$$
如果直接使用$\sqrt{x_c^2+y_c^2}$作为距离是不合理的，因为这里的邻近应该是按边界来算，而不是中心点. 因此，需要减去区域的长度：
$$(x'_c,y'_c)=\left(x_c-\frac{w-x}{2}-\frac{w'-x'}{2},y_c-\frac{z-y}{2}-\frac{z'-y'}{2}\right)\tag{11}$$
距离定义为
$$d(S,S')=\sqrt{[\max(x'_c,0)]^2+[\max(y'_c,0)]^2}\tag{12}$$
至于方向，由$(x_c,y_c)$的幅角进行判断即可.

然而，按照前面的“邻近搜索*”方法，容易把上下两行文字粘合起来，因此，基于我们的横向排版假设，更好的方法是只允许横向膨胀：

邻近搜索 从一个连通区域出发，可以找到该连通区域的水平外切矩形，将连通区域扩展到整个矩形. 当该区域与最邻近区域的距离小于一定范围时，考虑这个矩形的膨胀，膨胀的方向是最邻近区域的所在方向，当且仅当所在方向是水平的，才执行膨胀操作.

结果

有了距离之后，我们就可以计算每两个连通区域之间的距离，然后找出最邻近的区域. 我们将每个区域向它最邻近的区域所在的方向扩大4分之一，这样邻近的区域就有可能融合为一个新的区域，从而把碎片整合.

实验表明，邻近搜索的思路能够有效地整合文字碎片，结果如图15.

图15 通过邻近搜索后，圈出的文字区域

由于图像质量等原因，性能再好的识别模型，都会有识别错误的可能性，为了减少识别错误率，可以将识别问题跟统计语言模型结合起来，通过动态规划的方法给出最优的识别结果.这是改进OCR识别效果的重要方法之一.

转移概率

在我们分析实验结果的过程中，有出现这一案例.由于图像不清晰等可能的原因，导致“电视”一词被识别为“电柳”，仅用图像模型是不能很好地解决这个问题的，因为从图像模型来看，识别为“电柳”是最优的选择.但是语言模型却可以很巧妙地解决这个问题.原因很简单，基于大量的文本数据我们可以统计“电视”一词和“电柳”一词的概率，可以发现“电视”一词的概率远远大于“电柳”，因此我们会认为这个词是“电视”而不是“电柳”.

从概率的角度来看，就是对于第一个字的区域的识别结果$s_1$，我们前面的卷积神经网络给出了“电”、“宙”两个候选字(仅仅选了前两个，后面的概率太小)，每个候选字的概率$W(s_1)$分别为0.99996、0.00004；第二个字的区域的识别结果$s_2$，我们前面的卷积神经网络给出了“柳”、“视”、“规”(仅仅选了前三个，后面的概率太小)，每个候选字的概率$W(s_2)$分别为0.87838、0.12148、0.00012，因此，它们事实上有六种组合：“电柳”、“电视”、“电规”、“宙柳”、“宙视”、“宙规”.

点击阅读全文...