计算几何常用算法,ACM竞赛必备~

来自2010年百度文库

原作者不详

1、矢量减法

设二维矢量 P = (x1,y1) ,Q = (x2,y2)
则矢量减法定义为: P – Q = ( x1 – x2 , y1 – y2 )
显然有性质 P – Q = – ( Q – P )
如不加说明,下面所有的点都看作矢量,两点的减法就是矢量相减;

2、矢量叉积

设矢量P = (x1,y1) ,Q = (x2,y2)
则矢量叉积定义为: P × Q = x1*y2 – x2*y1   得到的是一个标量
显然有性质 P × Q = – ( Q × P )   P × ( – Q ) = – ( P × Q )
如不加说明,下面所有的点都看作矢量,点的乘法看作矢量叉积;
叉乘的重要性质:
> 若 P × Q > 0 , 则P 在Q的顺时针方向
> 若 P × Q < 0 , 则P 在Q的逆时针方向
> 若 P × Q = 0 , 则P 与Q共线,但可能同向也可能反向

3、判断点在线段上

设点为Q,线段为P1P2 ,判断点Q在该线段上的依据是:
( Q – P1 ) × ( P2 – P1 ) = 0 且 Q 在以 P1,P2为对角顶点的矩形内

4、判断两线段是否相交

我们分两步确定两条线段是否相交:

(1)快速排斥试验
设以线段 P1P2 为对角线的矩形为R, 设以线段 Q1Q2 为对角线的矩形为T,如果R和T不相
交,显然两线段不会相交;

(2)跨立试验
如果两线段相交,则两线段必然相互跨立对方,如图1所示。在图1中,P1P2跨立Q1Q2 ,则
矢量 ( P1 – Q1 ) 和( P2 – Q1 )位于矢量( Q2 – Q1 ) 的两侧,即
( P1 – Q1 ) × ( Q2 – Q1 ) * ( P2 – Q1 ) × ( Q2 – Q1 ) < 0
上式可改写成

( P1 – Q1 ) × ( Q2 – Q1 ) * ( Q2 – Q1 ) × ( P2 – Q1 ) > 0
当 ( P1 – Q1 ) × ( Q2 – Q1 ) = 0 时,说明   ( P1 – Q1 ) 和 ( Q2 – Q1 )共线,

但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上;同理,( Q2 – Q1 ) ×(
P2 – Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。

所以判断P1P2跨立Q1Q2的依据是:
( P1 – Q1 ) × ( Q2 – Q1 ) * ( Q2 – Q1 ) × ( P2 – Q1 ) ≥ 0
同理判断Q1Q2跨立P1P2的依据是:
( Q1 – P1 ) × ( P2 – P1 ) * ( P2 – P1 ) × ( Q2 – P1 ) ≥ 0
至此已经完全解决判断线段是否相交的问题。

5、判断线段和直线是否相交

如果线段 P1P2和直线Q1Q2相交,则P1P2跨立Q1Q2,即:
( P1 – Q1 ) × ( Q2 – Q1 ) * ( Q2 – Q1 ) × ( P2 – Q1 ) ≥ 0

6、判断矩形是否包含点

只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。
判断线段、折线、多边形是否在矩形中
因为矩形是个凸集,所以只要判断所有端点是否都在矩形中就可以了。

6、判断矩形是否在矩形中

只要比较左右边界和上下边界就可以了。

7、判断圆是否在矩形中

圆在矩形中的充要条件是:圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最
小值。

8、判断点是否在多边形中

以点P为端点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,
考虑沿着L从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多
边形的内部,遇到第二个交点的时候,离开了多边形,……所以很容易看出当L和多边形的
交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交,有些情况下交点只能计算一个
,有些情况下交点不应被计算(你自己画个图就明白了);如果L和多边形的一条边重合,
这条边应该被忽略不计。为了统一起见,我们在计算射线L和多边形的交点的时候,1。对
于多边形的水平边不作考虑;2。对于多边形的顶点和L相交的情况,如果该顶点是其所属
的边上纵坐标较大的顶点,则计数,否则忽略;3。对于P在多边形边上的情形,直接可判
断P属于多边行。由此得出算法的伪代码如下:

1、count ← 0;
2、以P为端点,作从右向左的射线L;
3、for 多边形的每条边s
4、do if P在边s上
5、then return true;
6、if s不是水平的
7、then if s的一个端点在L上且该端点是s两端点中纵坐标较大的端点
9、then count ← count+1
10、else if s和L相交
11、then count ← count+1;
12i、f count mod 2 = 1
13、then return true
14、else return false;

其中做射线L的方法是:设P’的纵坐标和P相同,横坐标为正无穷大(很大的一个正数),
则P和P’就确定了射线L。这个算法的复杂度为O(n)。

9、判断线段是否在多边形内

线段在多边形内的一个必要条件是线段的两个端点都在多边形内;
如果线段和多边形的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点)
,因为多边形的边的左右两侧分属多边形内外不同部分,所以线段一定会有一部分在多边
形外。于是我们得到线段在多边形内的第二个必要条件:线段和多边形的所有边都不内交

线段和多边形交于线段的两端点并不会影响线段是否在多边形内;但是如果多边形的某个
顶点和线段相交,还必须判断两相邻交点之间的线段是否包含与多边形内部。因此我们可
以先求出所有和线段相交的多边形的顶点,然后按照X-Y坐标排序,这样相邻的两个点就是
在线段上相邻的两交点,如果任意相邻两点的中点也在多边形内,则该线段一定在多边形
内。证明如下:
命题1:
如果线段和多边形的两相邻交点P1 ,P2的中点P’ 也在多边形内,则P1, P2之间的所有点
都在多边形内。
证明:
假设P1,P2之间含有不在多边形内的点,不妨设该点为Q,在P1, P’之间,因为多边形是闭
合曲线,所以其内外部之间有界,而P1属于多边行内部,Q属于多边性外部,P’属于多边性
内部,P1-Q-P’完全连续,所以P1Q和QP’一定跨越多边形的边界,因此在P1,P’之间至少还
有两个该线段和多边形的交点,这和P1P2是相邻两交点矛盾,故命题成立。证毕
由命题1直接可得出推论:
推论2:
设多边形和线段PQ的交点依次为P1,P2,……Pn,其中Pi和Pi+1是相邻两交点,线段PQ在多
边形内的充要条件是:P,Q在多边形内且对于i =1, 2,……, n-1,Pi ,Pi+1的中点也在多
边形内。

在实际编程中,没有必要计算所有的交点,首先应判断线段和多边形的边是否内交,倘若
线段和多边形的某条边内交则线段一定在多边形外;如果线段和多边形的每一条边都不内
交,则线段和多边形的交点一定是线段的端点或者多边形的顶点,只要判断点是否在线段
上就可以了。
至此我们得出算法如下:
1、f 线端PQ的端点不都在多边形内
2、hen return false;
3、点集pointSet初始化为空;
4、for 多边形的每条边s
5、do if 线段的某个端点在s上
6、then 将该端点加入pointSet;
7、else if s的某个端点在线段PQ上
8、then 将该端点加入pointSet;
9、else if s和线段PQ相交           // 这时候可以肯定是内交
10、 then return false;
11、将pointSet中的点按照X-Y坐标排序,X坐标小的排在前面,对于X坐标相同的点,Y坐
标小的排在前面;
12、for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
13、do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
14、then return false;
15、return true;

这个算法的复杂度也是O(n)。其中的排序因为交点数目肯定远小于多边形的顶点数目n,所
以最多是常数级的复杂度,几乎可以忽略不计。

10、判断折线在多边形内

只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段,多边形有n个顶点,
则复杂度为O(m*n)。

11、判断多边形是否在多边形内
只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个
有n个顶点的多边形内复杂度为O(m*n)。

12、判断矩形是否在多边形内

将矩形转化为多边形,然后再判断是否在多边形内。

13、判断圆是否在多边形内

只要计算圆心到多边形的每条边的最短距离,如果该距离大于等于圆半径则该圆在多边形
内。计算圆心到多边形每条边最短距离的算法在后文阐述。

14、判断点是否在圆内

计算圆心到该点的距离,如果小于等于半径则该点在圆内。

15、判断线段、折线、矩形、多边形是否在圆内

因为圆是凸集,所以只要判断是否每个顶点都在圆内即可。

16、判断圆是否在圆内

设两圆为O1,O2,半径分别为r1, r2,要判断O2是否在O1内。先比较r1,r2的大小,如果r
1<r2则O2不可能在O1内;否则如果两圆心的距离大于r1 – r2 ,则O2不在O1内;否则O2在
O1内。

17、计算点到线段的最近点

如果该线段平行于X轴(Y轴),则过点point作该线段所在直线的垂线,垂足很容易求得,
然后计算出垂足,如果垂足在线段上则返回垂足,否则返回离垂足近的端点;
如果该线段不平行于X轴也不平行于Y轴,则斜率存在且不为0。设线段的两端点为pt1和pt
2,斜率为:
k = ( pt2.y – pt1. y ) / (pt2.x – pt1.x );
该直线方程为:
y = k* ( x – pt1.x) + pt1.y
其垂线的斜率为 – 1 / k,
垂线方程为:
y = (-1/k) * (x – point.x) + point.y
联立两直线方程解得:
x = ( k^2 * pt1.x + k * (point.y – pt1.y ) + point.x ) / ( k^2 + 1)
y = k * ( x – pt1.x) + pt1.y;
然后再判断垂足是否在线段上,如果在线段上则返回垂足;如果不在则计算两端点到垂足
的距离,选择距离垂足较近的端点返回。

18、计算点到折线、矩形、多边形的最近点

只要分别计算点到每条线段的最近点,记录最近距离,取其中最近距离最小的点即可。

19、计算点到圆的最近距离
如果该点在圆心,则返回UNDEFINED
连接点P和圆心O,如果PO平行于X轴,则根据P在O的左边还是右边计算出最近点的横坐标为
centerPoint.x – radius 或 centerPoint.x + radius, 如图4 (a)所示;如果如果PO平
行于Y轴,则根据P在O的上边还是下边计算出最近点的纵坐标为 centerPoint.y -+radius
或 centerPoint.y – radius, 如图4 (b)所示。
如果PO不平行于X轴和Y轴,则PO的斜率存在且不为0,如图4(c)所示。这时直线PO斜率为

k = ( P.y – O.y )/ ( P.x – O.x )
直线PO的方程为:
y = k * ( x – P.x) + P.y
设圆方程为:
(x – O.x ) ^2 + ( y – O.y ) ^2 = r ^2,
联立两方程组可以解出直线PO和圆的交点,取其中离P点较近的交点即可。

20、计算两条共线的线段的交点

对于两条共线的线段,它们之间的位置关系有图5所示的几种情况。
图5(a)中两条线段没有交点;图5 (b) 和 (d) 中两条线段有无穷焦点;图5 (c) 中两条线
段有一个交点。设line1是两条线段中较长的一条,line2是较短的一条,如果line1包含了
line2的两个端点,则是图5(d)的情况,两线段有无穷交点;如果line1只包含line2的一个
端点,那么如果line1的某个端点等于被line1包含的line2的那个端点,则是图5(c)的情况
,这时两线段只有一个交点,否则就是图5(c)的情况,两线段也是有无穷的交点;如果li
ne1不包含line2的任何端点,则是图5(a)的情况,这时两线段没有交点。

21、计算线段或直线与线段的交点
设一条线段为L0 = P1P2,另一条线段或直线为L1 = Q1Q2 ,要计算的就是L0和L1的交点。

1、首先判断L0和L1是否相交(方法已在前文讨论过),如果不相交则没有交点,否则说
明L0和L1一定有交点,下面就将L0和L1都看作直线来考虑。
2、如果P1和P2横坐标相同,即L0平行于Y轴
a) 若L1也平行于Y轴,
i. 若P1的纵坐标和Q1的纵坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交
点,假如L1是线段的话可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前
文已讨论过);
ii. 否则说明L0和L1平行,他们没有交点;
b) 若L1不平行于Y轴,则交点横坐标为P1的横坐标,代入到L1的直线方程中可以计算出交
点纵坐标;
3、如果P1和P2横坐标不同,但是Q1和Q2横坐标相同,即L1平行于Y轴,则交点横坐标为Q
1的横坐标,代入到L0的直线方程中可以计算出交点纵坐标;
4、如果P1和P2纵坐标相同,即L0平行于X轴
a) 若L1也平行于X轴,
i. 若P1的横坐标和Q1的横坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交
点,假如L1是线段的话可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前
文已讨论过);
ii. 否则说明L0和L1平行,他们没有交点;
b) 若L1不平行于X轴,则交点纵坐标为P1的纵坐标,代入到L1的直线方程中可以计算出交
点横坐标;
5、如果P1和P2纵坐标不同,但是Q1和Q2纵坐标相同,即L1平行于X轴,则交点纵坐标为Q
1的纵坐标,代入到L0的直线方程中可以计算出交点横坐标;
6、剩下的情况就是L1和L0的斜率均存在且不为0的情况
a) 计算出L0的斜率K0,L1的斜率K1 ;
b) 如果K1 = K2
i. 如果Q1在L0上,则说明L0和L1共线,假如L1是直线的话有无穷交点,假如L1是线段的话
可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前文已讨论过);
ii. 如果Q1不在L0上,则说明L0和L1平行,他们没有交点。
c) 联立两直线的方程组可以解出交点来

说明:这个算法并不复杂,但是要分情况讨论清楚,尤其是当两条线段共线的情况需要单
独考虑,所以在前文将求两条共线线段的算法单独写出来。另外,一开始就先利用矢量叉
乘判断线段与线段(或直线)是否相交,如果结果是相交,那么在后面就可以将线段全部
看作直线来考虑。

22、求线段或直线与折线、矩形、多边形的交点

分别求与每条边的交点即可。

23、求线段或直线与圆的交点

设圆心为O,圆半径为r,直线(或线段)L上的两点为P1,P2。
1、如果L是线段且P1,P2都包含在圆O内,则没有交点;否则进行下一步
2、如果L平行于Y轴,
a) 计算圆心到L的距离dis
b) 如果dis > r 则L和圆没有交点;
c) 利用勾股定理,可以求出两交点坐标,如图6(a)所示;但要注意考虑L和圆的相切情况
3、如果L平行于X轴,做法与L平行于Y轴的情况类似;
4、如果L既不平行X轴也不平行Y轴,可以求出L的斜率K,然后列出L的点斜式方程,和圆方程联立即可求解出L和圆的两个交点;
5、如果L是线段,对于2,3,4中求出的交点还要分别判断是否属于该线段的范围内。

数据挖掘相关的数学基础

来自:张迪的blog

链接:http://www.storagelab.org.cn/zhangdi/2014/01/12/数据挖掘相关的数学基础/

最近我在看《数学之美》和《信息简史》两本书,感觉十分受用。计划在本博客内开放读书专栏,记录心得体会。但在这之前,先大致描述一下我现在热衷的数据挖掘方向的相关基础知识,为了以后写文章做准备也是相当必要的。

引言

数据挖掘,是指从大量数据中获取隐含的、潜在的是有价值信息的过程,是近年来计算机领域火热的研究内容。作为一个大的命题,为了便于引入讨论,这里以本人目前涉及的游戏工业领域的数据挖掘方法展开讨论。

数据挖掘方法在游戏工业领域最初的应用,常常是游戏中的人工智能的开发。例如游戏中的电脑对手,对战类游戏的天梯系统,游戏开发时的关卡自动生成器。这些功能对应着数据挖掘方法中的专家系统、机器学习、模式识别、自然语言理解、自动定理证明、自动程序设计、机器人学、博弈、人工神经网络等。

事实上,数据挖掘的方法本质上就是人工智能的方法,数据挖掘的出现是人工智能发展史上具有重大意义的事件。传统人工智能的研究在20世纪末期事实上进入了一个低谷,这是因为20世纪80年代初,美国、欧洲和日本制定的一批针对人工智能的大型项目都面临了重重困难:一是所谓的交叉问题,即传统方法只能模拟人类深思熟虑的行为,而不包括人与环境的交互行为;二是所谓的扩展问题,即传统人工智能方法只适合于建造领域狭窄的专家系统,不能把这种方法简单地推广到规模更大、领域更宽的复杂系统中去。以上两个根本性问题使人工智能研究进入低谷。而数据挖掘的出现使人们又重新看到了人工智能的希望。 原因就在于数据挖掘方法将人工智能方法带进了广域数据集中,突破了专家系统的限制。

在最近的研究中,游戏行业的研究者们更多地使用数据挖掘方法去分析用户行为,从而进行更精准的商业方案定制。一方面这是因为资本的逐利性使然,现代游戏开发已经走进了一个不断推升制作成本和玩家期望之间的循环,高额的开发费用已经使很多游戏公司不堪重负。另外一方面,大数据时代的数据采集,令大量用户行为成为保存在服务器端的数据,令我们有能力进行分析与研究。通过数据挖掘方法,我们可以做到对游戏用户行为进行建模,并进行自动程序设计。典型的应用例如分析玩家行为和动机,探寻在线角色扮演游戏中的玩家社交群体的变化,识别玩家人物和公会的命名模式,检测游戏玩家感到沮丧的原因,揭露游戏中玩家的社会关系。

数据挖掘过程中相关的主要数学领域

面对复杂数据,数据挖掘的基本流程是:首先对原始数据进行填补遗漏、消除异常、平滑噪声等处理,提高数据挖掘的有效性和准确性。然后使用专门的算法对原始数据进行归纳抽象,去掉取之过多且不均匀的属性和概念层次树中不存在的属性,最终得到一个关系模型。当新的数据加入数据集中时,可以根据该关系模型决定新数据的分类和处理模式。同时,新数据也将带来对整体模型的变化,数据和模型处于动态对应的状态。

从以上过程中可以明显感到,所谓数据挖掘,就是一个典型的数学建模过程。当然,这里已经有较为成熟的工具、方法和理论。例如,统计机器学习所需要的主要理论和技术:泛函分析、逼近论与测度论、统计理论、VC维理论、覆盖数、描述长度理论与算法复杂度研究、核方法、非线性规划技术、几何变换。下文简要介绍涉及的数学学科。

 

1、线性代数和统计学

在这个建模过程中,基础是两大数学学科:线性代数和统计学。这代表了机器学习中最主流的两大类方法的基础。一种是以研究函数和变换为重点的代数方法,比如降维,特征值提取等,一种是以研究统计模型和样本分布为重点的统计方法,比如图模型、信息理论模型等。它们侧重虽有不同,但是常常是共同使用的,对于代数方法,往往需要统计上的解释,对于统计模型,其具体计算则需要代数的帮助。以代数和统计为出发点,继续往深处走,我们会发现需要更多的数学。传统的统计学所研究的主要是渐进理论(大样本情况下的统计性质),而样本数目通常有限(甚至还十分有限)。人们过去一直采用样本数目无穷为假设条件推导各种算法,然后将算法用于样本较小的情况,希望能有较好的效果,然而,算法往往不令人满意。由此,人们提出了学习的推广能力(泛化能力)的重要问题。过去多数工作集中在对大样本统计学习方法的改进和修改,或利用启发式方法设计特殊算法。

2、微积分

微积分只是数学分析体系的基础。其基础性作用不言而喻。机器学习研究的大部分问题是在连续的度量空间进行的,无论代数还是统计,在研究优化问题的时候,对一个映射的微分或者梯度的分析总是不可避免。

3、泛函分析

泛函分析体现了数学模型从特殊到一般的发展过程。

函数在19世纪前期的定义还是数与数的对应关系,空间的概念也只有欧几里德空间。十九世纪以来,数学的发展进入了一个新的阶段。这就是,由于对欧几里得第五公理的研究,引出了非欧几何这门新的学科;对于代数方程求解的一般思考,最后建立并发展了群论;对数学分析的研究又建立了集合论。这些新的理论都为用统一的观点把古典分析的基本概念和方法一般化准备了条件。泛函分析作为数学分析的分支,将函数扩展到函数与函数之间的关系,乃至任意两个集合之间的关系,空间则从有限维空间拓展到无限维空间。

在这个地方,函数以及其所作用的对象之间存在的对偶关系扮演了非常重要的角色。机器学习发展至今,也在向无限维延伸——从研究有限维向量的问题到以无限维的函数为研究对象。内核学习和高斯过程是其中典型的例子。

4、测度理论

这是和实分析关系非常密切的学科。概率本身就是一种测度。测度理论对于机器学习的意义是根本的,现代统计学整个就是建立在测度理论的基础之上——虽然初级的概率论教科书一般不这样引入。在一些统计方面的文章中它们会把统计的公式改用测度来表达,这样做有两个好处:所有的推导和结论不用分别给连续分布和离散分布各自写一遍了,这两种东西都可以用同一的测度形式表达:连续分布的积分基于Lebesgue测度,离散分布的求和基于计数测度,而且还能推广到那种既不连续又不离散的分布中去。而且,即使是连续积分,如果不是在欧氏空间进行,而是在更一般的拓扑空间(比如微分流形或者变换群),那么就不能使用传统的黎曼积分了,需要使用,比如哈尔测度或者Lebesgue-Stieltjes积分。

5、拓扑学

这是学术中很基础的学科。它一般不直接提供方法,但是它的很多概念和定理是其它数学分支的基石。看很多别的数学的时候,会经常接触这样一些概念:开集,闭集,连续函数度量空间,柯西序列,邻接性,连续性。很多这些也许在大学一年级就学习过一些,当时是基于极限的概念获得的。但是看过拓扑学之后,对这些概念的认识会有根本性的拓展。值得一提的是,计算机学科的基础布尔代数与拓扑学有重要的联系。

6、图论

图,由于它在表述各种关系的强大能力以及优雅的理论,高效的算法,越来越受到数据挖掘领域的欢迎。而从目前我所接触的范围内,图论仅在数据结构这门课中提到过。经典图论,在数据挖掘领域中的一个最重要应用就是图模型了,它被成功运用于分析统计网络的结构和规划统计推断。例如,分析社交网络的用户关系,常用邻接链表和邻接矩阵综合表示。在遍历时也离不开深度优先和广度优先算法。

《台大机器学习基石》Linear Regression

By Kubi Code

Source: http://kubicode.me/2015/08/19/Machine%20Learning/Linear-Regression/

Linear Regression

现在相对比于之前的Perceptron Learning Algorithm算法,假如我们现在时的问题不是解决是否发行用卡,而是该发多少额度的问题

也就是输出空间属于一个实数,那么就需要一个回归算法来解决该问题!

那么我们其实可以直接使用特征属性与权重的加权求和来表示需要发的信用额度即可(与PLA类似,但是没有激活函数:二值判断逆函数)

上图中表示的就是为线性回归(Linear Regression),其中wTx就是表示为全部的假设空间(hypothesis set)

如果当前的特征是一维的,那么这里的hypothesis set就表示一条线,(因为总体的特征向量里面还有一个常数值)

如果当前的特征是二维的,那么这里的hypothesis set就一个平面

当然特征更加多得话,最终hypothesis set表示一个超平面
其中图上红色的部分叫做误差(视频里面叫做余数),那么回归分析的目标就是将所有的误差降到最小越好
这里使用平方误差来衡量整体的误差

那么从机器学习的角度来说,这里的误差就可以看做(下面这个表达式就很熟悉了)

相应的

表示这个分类器在未来未训练数据集中产生的误差是多少
那么现在的线性回归的问题就是转为将Ein(w)优化到最小。

Ein(w)最小化

现将上面小节的中的Ein转为矩阵的运算

  1. 向量内积可交换,将wTx转为xTw
  2. 将连加转为向量形式的长度(应该是二范数)
  3. w单独提出来(相当于隔离出了一个特征属性向量的矩阵)
  4. 最终使用缩写来进行整理

到了这一步我们可以发现Ein(w)只与w有关,那么他们的关系图是

可以发现Ein(w)是连续可导,还有它是凸的
那么用Ein(w)w求偏导即可求导最优值(梯度为0的位置)

这样现在问题又转为了 求

首先将
现在对其求偏导

完了之后再将A,b替换回去

进一步将问题转换为
式子中XTXXTy都是已知的,唯一不知道的就是w,这样就变为了一个一次的方程式

  1. 假如有(XTX)-1反矩阵的存在,那么就可以直接得到解了,并且是唯一的
  2. 但是如果(XTX)-1反矩阵不存在,那么得到的解可能就不唯一了

所以这里的核心就是计算虚假的反矩阵(pseudo-inverse),听林老师说这个的计算很多工具都是由现成的^_^

刚刚求Ein(w)最小化的过程中看似直接用公式代替可到,但是其中的pseudo-inverse计算起来麻烦,最终在计算的时候还是需要迭代,然后会触发Ein(w)Eout(w)的变化,是一个深度隐含的学习过程(这种是叫做Analytic Solution)。

Learning happened

那么该如果保证Eout可以是小的呢?
我们先来看一下Ein的平均

其中nosie level表示样本中噪声的一个情况,d+1表示模型的自由度,N表示样本的容量
其中单独表示Ein(w)的话为

这样就形成了两项1-XX+y,也就是相当于将输入喝输出进行了一个分离,其中XX+叫做hat matrix
关于这个hat matrix,它的意义是这样纸的

  1. 红色区块表示向量X的一个扩散,而y^就是落在这个空间上
  2. 目标就是求y-y^的最小化,也就是图种的绿色那条线(y^)向下投影的线
  3. H就是表示这个空间上yy^的一个投影
  4. I-H就是表示误差部分y-y^

相应的会有trace(I-H)=N-(d+1)

好,现在再来看Ein的平均到底是什么意思

  1. 其中如果f(x)为目标函数,那么目标值y就相当于在f(x)上添加噪声
  2. 然后这个噪声通过I-H就可以转为y-y^

现在对噪声作评价的话,那么就可以得到
此时
这两个式子哲学上的意思是Ein的平均是可以看到的,所以当存在噪声的时候看到的线会偏向于噪声方向,而在Eout的平均是未知的,比最好的那个线还要向右边偏一点(没听懂-_-)

他们俩会形成如下的关系线

它描述的是当前的样本量与平均的EinEout的关系,随着样本量N的增长,最终会趋向于nosie level

那么就可以得到

说明N足够大,然后他的noise level够小时,说明了Learning happened

总结

  1. 线性回归最终求出的是一个加权求和的值.
  • 线性回归的Ein的采用的是最小平方误差.
  • 在计算Ein的最小化时,可以将问题转为矩阵之后就逆矩阵相关即可.
  • 通过Ein平均的计算,说明了Learning happened.
  • 其实线性回归去坐分类问题也是可以的^_^,第9课第4个小视频.

参考

  • 《台湾国立大学-机器学习基石》第九讲

配图均来自《台湾国立大学-机器学习基石》

5 insanely great books about mathematics you should read

Kelly J. Rose

Source: https://wp.kjro.se/2013/12/27/5-insanely-great-books-about-mathematics-you-should-read/

I’ve been asked over and over for good books about mathematics for a layperson, someone who hasn’t taken advanced courses in university and is more simply interested in learning about what math is, and some of the more interesting historical figures and results from mathematics. Ironically, when you are a mathematics major at Waterloo, you get the opportunity in 4th year to take a course on the history of mathematics and you get introduced to a few really good books that start to explain the mindset and philosophy behind mathematics and not simply just the theorems and proofs.

Here are the 5 books about I most recommend to those who want to understand the mathematical mind and philosophy.

Boyer’s a History of Mathematics

A History of Mathematics,
Carl B. Boyer

This is the textbook from the History of Mathematics course I took almost a decade ago now, and it is still one of the best and most thorough discussions of how mathematics developed over the past millenia. It starts in with Egyptian and pre-classical mathematics, explaining how simple tasks were complicated by a lack of mathematical tools and then how over time different tools were developed that led to quantum leaps in our understanding of the field. It’s quite a tome, with over 700 pages of details, but it is fully accessible to the non-technical reader.

This is well worth having in any library and it can be read in chunks as each chapter covers a different aspect of mathematical history.

Journeys Through Genius

Journeys Through Genius

Journey through Genius
William Dunham

I picked up this book at a secondhand store many years back simply because it caught my attention and was a good price. I thought it would be an enjoyable read, but I never expected to be as amazed and excited by the contents as I started to dig through it. This book takes some of the most important and paradigm-shifting theorems of mathematics and explains them in a clear and accessible fashion. Historical artifacts around the development of the theorems are displayed in a fun and pleasing fashion, keeping the importance of the discovery in context with the time. As well, most importantly, beyond explaining the theorems, the characters behind the work as shown and their lives are taken into context with the immensity of their work. This is a beautiful read and worth picking up if you want to learn more about the biggest theorems in mathematics.

The Mathematical ExperienceThe Mathematical Experience,
Philip J. David, Reuben Hersh

My professor for the history of mathematics course lent me his copy of this book and it was probably one of the most eye-opening reads I’ve ever had. I spent an entire weekend reading it cover-to-cover and then re-reading it again, devouring and absorbing all of the ideas and concepts within it.

Without a doubt, this is the best book I’ve got on my library from the perspective of discussion what it means to be a mathematician and the experience shared by mathematicians worldwide. This book covers the entire gamut, from the philosophical to the social-emotional experience of a mathematician. It is well-written, concise and strikes a real chord with me. In this book I really felt that I was reading someone who got what it meant to love mathematics and get excited by it without delving really deep into difficult to process material. If there is one book on this entire list that I recommend going and purchasing right now, it is this one.

Go, buy it now!

Proofs from the Book

Proofs from the Book

Proofs from the Book,
Martin Aigner, Günter M. Ziegler

Paul Erdös, one of the most prolific mathematicians of the 20th century would commonly refer to a proof that was singularly beautiful as being “from the book.” As in, “from the book of God himself.” This book is a collection of some of the proofs that many mathematicians think to be essential and important, while still be uniquely beautiful in their elegance. If you want a book which is still accessible, but allows for exploration of the theorems themselves in am ore rigourous fashion, this is the book for you. It’s clean and covers some of the best proofs in a very wide variety of fields.

Proofs and Refutations

Proofs and Refutations

Proofs and Refutations,
Imre Lakatos

This books is probably the most advanced of the books on this list. It is however brilliantly written in the form of a discussion between a professor and their students. Lakatos weaves in and out over the process of mathematics, covering how mathematics is really done and evolves as theorems adapt based on a variety of very easy to understand techniques.

If you, or anyone you know, is actually considering to go into mathematics as a profession, I would recommend reading this book. This especially includes teachers as it explains how working through the technique and philosophy can help with overall understanding and creative use of the new tools learned as you move forward. This is a truly wonderful book and can be a very quick read.

 

机器学习:用初等数学解读逻辑回归

2015-11-03 龙心尘、寒小阳

摘自:http://my.csdn.net/longxinchen_ml

为了降低理解难度,本文试图用最基础的初等数学来解读逻辑回归,少用公式,多用图形来直观解释推导公式的现实意义,希望使读者能够对逻辑回归有更直观的理解。

逻辑回归问题的通俗几何描述

逻辑回归处理的是分类问题。我们可以用通俗的几何语言重新表述它:
空间中有两群点,一群是圆点“〇”,一群是叉点“X”。我们希望从空间中选出一个分离边界,将这两群点分开。

注:分离边界的维数与空间的维数相关。如果是二维平面,分离边界就是一条线(一维)。如果是三维空间,分离边界就是一个空间中的面(二维)。如果是一维直线,分离边界就是直线上的某一点。不同维数的空间的理解下文将有专门的论述。

为了简化处理和方便表述,我们做以下4个约定:

  1. 我们先考虑在二维平面下的情况。
  2. 而且,我们假设这两类是线性可分的:即可以找到一条最佳的直线,将两类点分开。
  3. 用离散变量y表示点的类别,y只有两个可能的取值。y=1表示是叉点“X”,y=0表示是是圆点“〇”。
  4. 点的横纵坐标用表示。

于是,现在的问题就变成了:怎么依靠现有这些点的坐标和标签(y),找出分界线的方程。

如何用解析几何的知识找到逻辑回归问题的分界线?
  1. 我们用逆推法的思路:
    假设我们已经找到了这一条线,再寻找这条线的性质是什么。根据这些性质,再来反推这条线的方程。
  2. 这条线有什么性质呢?
    首先,它能把两类点分开来。——好吧,这是废话。( ̄▽ ̄)”
    然后,两类点在这条线的法向量p上的投影的值的正负号不一样,一类点的投影全是正数,另一类点的投影值全是负数

    • 首先,这个性质是非常好,可以用来区分点的不同的类别
    • 而且,我们对法向量进行规范:只考虑延长线通过原点的那个法向量p。这样的话,只要求出法向量p,就可以唯一确认这条分界线,这个分类问题就解决了。


  3. 还有什么方法能将法向量p的性质处理地更好呢?
    因为计算各个点到法向量p投影,需要先知道p的起点的位置,而起点的位置确定起来很麻烦,我们就干脆将法向量平移使其起点落在坐标系的原点,成为新向量p’。因此,所有点到p’的投影也就变化了一个常量。

    假设这个常量为,p’向量的横纵坐标为。空间中任何一个点到p’的投影就是,再加上前面的常量值就是:

看到上面的式子有没有感到很熟悉?这不就是逻辑回归函数中括号里面的部分吗?

就可以根据z的正负号来判断点x的类别了。

从概率角度理解z的含义。

由以上步骤,我们由点x的坐标得到了一个新的特征z,那么:

z的现实意义是什么呢?

首先,我们知道,z可正可负可为零。而且,z的变化范围可以一直到正负无穷大。

z如果大于0,则点x属于y=1的类别。而且z的值越大,说明它距离分界线的距离越大,更可能属于y=1类。

那可否把z理解成点x属于y=1类的概率P(y=1|x) (下文简写成P)呢?显然不够理想,因为概率的范围是0到1的。

但是我们可以将概率P稍稍改造一下:令Q=P/(1-P),期望用Q作为z的现实意义。我们发现,当P的在区间[0,1]变化时,Q在[0,+∞)区间单调递增。函数图像如下(以下图像可以直接在度娘中搜“x/(1-x)”,超快):

但是Q的变化率在[0,+∞)还不够,我们是希望能在(-∞,+∞)区间变化的。而且在P=1/2的时候刚好是0。这样才有足够的解释力。

注:因为P=1/2说明该点属于两个类别的可能性相当,也就是说这个点恰好在分界面上,那它在法向量的投影自然就是0了。

而在P=1/2时,Q=1,距离Q=0还有一段距离。那怎么通过一个函数变换然它等于0呢?有一个天然的函数log,刚好满足这个要求。
于是我们做变换R=log(Q)=log(P/(1-P)),期望用R作为z的现实意义。画出它的函数图像如图:

这个函数在区间[0,1]中可正可负可为零,单调地在(-∞,+∞)变化,而且1/2刚好就是唯一的0值!基本完美满足我们的要求。
回到我们本章最初的问题,

“我们由点x的坐标得到了一个新的特征z,那么z的具体意义是什么呢?”

由此,我们就可以将z理解成x属于y=1类的概率P经过某种变换后对应的值。也就是说,z= log(P/(1-P))。反过来就是P=。图像如下:

这两个函数log(P/(1-P)) 、看起来熟不熟悉?

这就是传说中的logit函数和sigmoid函数!

小小补充一下:

  • 在概率理论中,Q=P/(1-P)的意义叫做赔率(odds)。世界杯赌过球的同学都懂哈。赔率也叫发生比,是事件发生和不发生的概率比。
  • 而z= log(P/(1-P))的意义就是对数赔率或者对数发生比(log-odds)。

于是,我们不光得到了z的现实意义,还得到了z映射到概率P的拟合方程:

有了概率P,我们顺便就可以拿拟合方程P=来判断点x所属的分类:

当P>=1/2的时候,就判断点x属于y=1的类别;当P<1/2,就判断点x属于y=0的类别。

构造代价函数求出参数的值

到目前为止我们就有两个判断某点所属分类的办法,一个是判断z是否大于0,一个是判断g(z)是否大于1/2。
然而这并没有什么X用,

以上的分析都是基于“假设我们已经找到了这条线”的前提得到的,但是最关键的三个参数仍未找到有效的办法求出来。

还有没有其他的性质可供我们利用来求出参数的值?

  • 我们漏了一个关键的性质:这些样本点已经被标注了y=0或者y=1的类别!
  • 我们一方面可以基于z是否大于0或者g(z) 是否大于1/2来判断一个点的类别,另一方又可以依据这些点已经被标注的类别与我们预测的类别的插值来评估我们预测的好坏。
  • 这种衡量我们在某组参数下预估的结果和实际结果差距的函数,就是传说中的代价函数Cost Function。
  • 当代价函数最小的时候,相应的参数就是我们希望的最优解。

由此可见,设计一个好的代价函数,将是我们处理好分类问题的关键。而且不同的代价函数,可能会有不同的结果。因此更需要我们将代价函数设计得解释性强,有现实针对性。

为了衡量“预估结果和实际结果的差距”,我们首先要确定“预估结果”“实际结果”是什么。

  • “实际结果”好确定,就是y=0还是y=1。
  • “预估结果”有两个备选方案,经过上面的分析,我们可以采用z或者g(z)。但是显然g(z)更好,因为g(z)的意义是概率P,刚好在[0,1]范围之间,与实际结果{0,1}很相近,而z的意思是逻辑发生比,范围是整个实数域(-∞,+∞),不太好与y={0,1}进行比较。

接下来是衡量两个结果的“差距”。

  • 我们首先想到的是y-hθ(x)。
    • 但这是当y=1的时候比较好。如果y=0,则y- hθ(x)= – hθ(x)是负数,不太好比较,则采用其绝对值hθ(x)即可。综合表示如下:
    • 但这个函数有个问题:求导不太方便,进而用梯度下降法就不太方便。
    • 因为梯度下降法超出的初等数学的范围,这里就暂且略去不解释了。
  • 于是对上面的代价函数进行了简单的处理,使之便于求导。结果如下:

代价函数确定了,接下来的问题就是机械计算的工作了。常见的方法是用梯度下降法。于是,我们的平面线形可分的问题就可以说是解决了。

从几何变换的角度重新梳理我们刚才的推理过程。

回顾我们的推理过程,我们其实是在不断地将点进行几何坐标变换的过程。

  • 第一步是将分布在整个二维平面的点通过线性投影映射到一维直线中,成为点x(z)
  • 第二步是将分布在整个一维直线的点x(z)通过sigmoid函数映射到一维线段[0,1]中成为点x(g(z))。
  • 第三步是将所有这些点的坐标通过代价函数统一计算成一个值,如果这是最小值,相应的参数就是我们所需要的理想值。

对于简单的非线性可分的问题。
  1. 由以上分析可知。比较关键的是第一步,我们之所以能够这样映射是因为假设我们点集是线性可分的。但是如果分离边界是一个圆呢?考虑以下情况。
  2. 我们仍用逆推法的思路:
    • 通过观察可知,分离边界如果是一个圆比较合理。
    • 假设我们已经找到了这个圆,再寻找这个圆的性质是什么。根据这些性质,再来反推这个圆的方程
  3. 我们可以依据这个性质:
    • 圆内的点到圆心的距离小于半径,圆外的点到圆心的距离大于半径
    • 假设圆的半径为r,空间中任何一个点到原点的距离为
    • ,就可以根据z的正负号来判断点x的类别了
    • 然后令,就可以继续依靠我们之前的逻辑回归的方法来处理和解释问题了。
  4. 从几何变换的角度重新梳理我们刚才的推理过程。
    • 第一步是将分布在整个二维平面的点通过某种方式映射到一维直线中,成为点x(z)
    • 第二步是将分布在整个一维射线的点x(z)通过sigmoid函数映射到一维线段[0,1]中成为点x(g(z))。
    • 第三步是将所有这些点的坐标通过代价函数统一计算成一个值v,如果这是最小值,相应的参数就是我们所需要的理想值。

 

从特征处理的角度重新梳理我们刚才的分析过程

其实,做数据挖掘的过程,也可以理解成做特征处理的过程。我们典型的数据挖掘算法,也就是将一些成熟的特征处理过程给固定化的结果
对于逻辑回归所处理的分类问题,我们已有的特征是这些点的坐标,我们的目标就是判断这些点所属的分类y=0还是y=1。那么最理想的想法就是希望对坐标进行某种函数运算,得到一个(或者一些)新的特征z,基于这个特征z是否大于0来判断该样本所属的分类。

对我们上一节非线性可分问题的推理过程进行进一步抽象,我们的思路其实是:

  • 第一步,将点的坐标通过某种函数运算,得到一个新的类似逻辑发生比的特征
  • 第二步是将特征z通过sigmoid函数得到新的特征
  • 第三步是将所有这些点的特征q通过代价函数统一计算成一个值,如果这是最小值,相应的参数(r)就是我们所需要的理想值。

对于复杂的非线性可分的问题

由以上分析可知。比较关键的是第一步,如何设计转换函数。我们现在开始考虑分离边界是一个极端不规则的曲线的情况。

我们仍用逆推法的思路:

  • 通过观察等先验的知识(或者完全不观察乱猜),我们可以假设分离边界是某种6次曲线(这个曲线方程可以提前假设得非常复杂,对应着各种不同的情况)。
  • 第一步:将点的坐标通过某种函数运算,得到一个新的特征。并假设z是某种程度的逻辑发生比,通过其是否大于0来判断样本所属分类。
  • 第二步:将特征z通过sigmoid函数映射到新的特征
  • 第三步:将所有这些样本的特征q通过逻辑回归的代价函数统一计算成一个值,如果这是最小值,相应的参数就是我们所需要的理想值。相应的,分离边界其实就是方程=0,也就是逻辑发生比为0的情况嘛

多维逻辑回归的问题

以上考虑的问题都是基于在二维平面内进行分类的情况。其实,对于高维度情况的分类也类似。

高维空间的样本,其区别也只是特征坐标更多,比如四维空间的点x的坐标为。但直接运用上文特征处理的视角来分析,不过是对坐标进行参数更多的函数运算得到新的特征并假设z是某种程度的逻辑发生比,通过其是否大于0来判断样本所属分类。

而且,如果是高维线性可分的情况,则可以有更近直观的理解。

  • 如果是三维空间,分离边界就是一个空间中的一个二维平面。两类点在这个二维平面的法向量p上的投影的值的正负号不一样,一类点的投影全是正数,另一类点的投影值全是负数。
  • 如果是高维空间,分离边界就是这个空间中的一个超平面。两类点在这个超平面的法向量p上的投影的值的正负号不一样,一类点的投影全是正数,另一类点的投影值全是负数。
  • 特殊的,如果是一维直线空间,分离边界就是直线上的某一点p。一类点在点p的正方向上,另一类点在点p的负方向上。这些点在直线上的坐标可以天然理解成类似逻辑发生比的情况。可见一维直线空间的分类问题是其他所有高维空间投影到法向量后的结果,是所有逻辑回归问题的基础

多分类逻辑回归的问题

以上考虑的问题都是二分类的问题,基本就是做判断题。但是对于多分类的问题,也就是做选择题,怎么用逻辑回归处理呢?

其基本思路也是二分类,做判断题。

比如你要做一个三选一的问题,有ABC三个选项。首先找到A与BUC(”U”是并集符号)的分离边界。然后再找B与AUC的分离边界,C与AUB的分离边界。

这样就能分别得到属于A、B、C三类的概率,综合比较,就能得出概率最大的那一类了。

总结

本文的分析思路——逆推法

画图,观察数据,看出(猜出)规律,假设规律存在,用数学表达该规律,求出相应数学表达式。
该思路比较典型,是数据挖掘过程中的常见思路。

两个视角:几何变换的视角与特征处理的视角。

  1. 小结:
    • 几何变换的视角:高维空间映射到一维空间 → 一维空间映射到[0,1]区间 → [0,1]区间映射到具体的值,求最优化解
    • 特征处理的视角:特征运算函数求特征单值z → sigmoid函数求概率 → 代价函数求代价评估值,求最优化解
  2. 首先要说明的是,在逻辑回归的问题中,这两个视角是并行的,而不是包含关系。它们是同一个数学过程的两个方面
    • 比如,我们后来处理复杂的非线性可分问题的时候,看似只用的是特征处理的思路。其实,对于复杂的非线性分离边界,也可以映射到高维空间进行线性可分的处理。在SVM中,有时候某些核函数所做的映射与之非常类似。这将在我们接下来的SVM系列文章中有更加详细的说明
  3. 在具体的分析过程中,运用哪种视角都可以,各有优点
    • 比如,作者个人比较倾向几何变换的视角来理解,这方便记忆整个逻辑回归的核心过程,画几张图就够了。相应的信息都浓缩在图像里面,异常清晰。
    • 于此同时,特征处理的视角方便你思考你手上掌握的特征是什么,怎么处理这些特征。这其实的数据挖掘的核心视角。因为随着理论知识和工作经验的积累,越到后面越会发现,当我们已经拿到无偏差、倾向性的数据集,并且做过数据清洗之后,特征处理的过程是整个数据挖掘的核心过程:怎么收集这些特征,怎么识别这些特征,挑选哪些特征,舍去哪些特征,如何评估不同的特征……这些过程都是对你算法结果有决定性影响的极其精妙的精妙部分。这是一个庞大的特征工程,里面的内容非常庞大,我们将在后续的系列文章中专门讨论
    • 总的来说,几何变换视角更加直观具体,特征处理视角更加抽象宏观,在实际分析过程中,掌握着两种视角的内在关系和转换规律,综合分析,将使得你对整个数据挖掘过程有更加丰富和深刻的认识
    • 为了将这两种视角更集中地加以对比,我们专门制作了下面的图表,方便读者查阅。

原文链接:http://blog.csdn.net/longxinchen_ml/article/details/49284391

封面来源:www.taopic.com

作者介绍:

龙心尘和寒小阳:从事机器学习/数据挖掘相关应用工作,热爱机器学习/数据挖掘

『我们是一群热爱机器学习,喜欢交流分享的小伙伴,希望通过“ML学分计划”交流机器学习相关的知识,认识更多的朋友。欢迎大家加入我们的讨论群获取资源资料,交流和分享。』

联系方式:

龙心尘 johnnygong.ml@gmail.com

寒小阳 hanxiaoyang.ml@gmail.com

 

逻辑回归:从入门到精通

本文由 天眼查创始人 柳超 原创首发于腾讯

导读

与算法、随机森林、支持向量积、神经网络、以及各种算法的花式排列组合相比,逻辑回归在多数人看来似乎是太过传统的统计方法。2014年底的我带着拯救世界的梦想投向硅谷怀抱的时候,也是这么认为的。

但是在工作的过程中我渐渐发现,不管听起来多fancy、多高大上的项目,硅谷的数据分析大佬们多数都会首选逻辑回归。而我之前自以为可以拯救世界的那些花式算法,其实都是逻辑回归的变换和推广,只是原理有轻微的不同。

后来做到了别的领域的项目,比如搜索,比如广告投放,也愈发认识到逻辑回归的重要性。因此,作为一名统计学出身的数据科学家,我极力向不喜欢看教科书的各位读者推荐以下这篇文章。我不知道怎么描述我第一次看到这篇文章的心情,就好比高考的时候突然有人给我了一份答案的感觉(虽然这个比喻不恰当但是真的是那种感觉,相信你们能感受到的)。

至于怎么能看透花式,洞悉一切,请看大神的文章吧!(By纪思亮)

◆ ◆ ◆

Abstract

逻辑回归(Logistic    Regression,简称LR)可以说是互联网领域应用最广的自动分类算法:从单机运行的垃圾邮件自动识别程序到需要成百上千台机器支撑的互联网广告投放系统,其算法主干都是LR。由于其普适性与重要性,大家在工作中都或多或少的谈论着LR,但是笔者发现很多同学对于LR的理解可以进一步提高与深化。所以,笔者准备了这样一个关于逻辑回归从入门到精通的文章和同学们一同探讨。本文的目标不像是基维百科那样泛泛而谈、面面俱到地介绍LR,相反而是更注重对LR的理解和其背后的优化算法的掌握,从而使大家更有信心的实现中需要的大规模LR模型,并根据实际问题持续地改进它。另外,由于求解LR是一个性质很好的优化问题。本文也借此机会比较系统的介绍了从最速梯度下降法,到牛顿方法,再到拟牛顿方法(包括DFP、BFGS、L-BFGS)这一系列数值优化算法的脉络,也算是对数值优化算法中文教程的一个补充吧。最后,请各位领导、大拿、和冲在一线的研究猿与攻城狮们不吝赐教、切磋琢磨、一同进步!

◆ ◆ ◆

    1、动机与目标读者

大家在平时的工作与学习当中经常会遇到各种决策问题:例如这封邮件是不是垃圾邮件,这个用户是不是对这个商品感兴趣,这个房子该不该买等等。熟悉或接触过机器学习(Machine    Learning,简称ML)的同学知道如果我们需要对这类问题进行决策的时候,最常用的方法是构建一个叫做分类器(Classifier)的程序。这种程序的输入待决策问题的一系列特征(feature),输出就是程序判定的结果。以垃圾邮件分类为例,每一封邮件就是一个待决策的问题,而通常使用的特征就是从这个邮件本身抽取一系列我们认为可能相关的信息,例如,发件人、邮件长度、时间、邮件中的关键词、标点符号、是否有多个收件人等等。给定了这些特征,我们的垃圾邮件分类器就可以判定出这封邮件是否是垃圾邮件。至于怎么得到这个垃圾邮件分类器程序,通常的做法是通过某些机器学习算法。之所以称其为”学习“ ,是因为这些算法通常需要一些已经标注好的样本(例如,100封邮件,每封信已经被明确标注为是否是垃圾邮件),然后这个算法就自动的产生一个关于这个问题的自动分类器程序。我们在这篇文章中将要讲得逻辑回归(Logistic    Regression,简称LR)就是最常用的一个机器学习分类算法。

很多同学可能知道机器学习中有几十种分类器,那么我们为什么偏偏挑LR来讲呢?原因有三:

  1. LR模型原理简单,并且有一个现成的叫LIBLINEAR 的工具库,易于上手,并且效果不错。
  2. LR可以说是互联网上最常用也是最有影响力的分类算法。LR几乎是所有广告系统中和推荐系统中点击率(Click    Through    Rate(CTR))预估模型的基本算法。
  3. LR同时也是现在炙手可热的“深度学习”(Deep    Lerning)的基本组成单元,扎实的掌握LR也将有助于你的学好深度学习。

但是文本并不是一篇关于LR的科普性文章,如果你想泛泛地了解LR,最好的办法是去维基百科或者找一本像样的机器学习教材翻一下。相反的,本文的目标是是你不仅仅“知其然”,并且更“知其所以然”,真正做到从入门到精通,从而更加有信心地解决LR实践中出现的新问题。我们可以粗略的把入门到精通分为三个层次。

  • 了解LR:了解LR模型、L1和L2规则化(Regularization)、为什么L1规则化更倾向于产生稀疏模型(Sparse    Model)、以及稀疏模型的优点。
  • 理解LR:理解LR模型的学习算法、能够独自推导基于L-BFGS的L1和L2规则化的LR算法,并将其在MPI平台上并行化实现。
  • 改进LR:能够在实际中自如应用LR,持续改进LR来解决实际中未曾遇见到的问题。例如,当数据中的正样本远远小于负样本的情况下(例如,广告点击率预告问题),该怎么调整LR?当数据中有相当部分缺失时该如何调整算法?

由于求解LR是一个性质很好的无约束优化问题,本文在介绍LR的同时,也相对系统的介绍了无约束优化问题中的几个常用的数值方法,包括最速梯度下降方法、牛顿方法、和拟牛顿方法的DFP、BFGS、与L-BFGS。期望同学们能在知道了解这些算法的同时真正明白其原理与应用场景,例如理解为什么L-BFGS中的二次循环方法(two    iteration    method )能够近似计算牛顿方向,并且可以轻松的并行化。这些算法是关于无约束问题的通过优化算法,应用场景非常广泛,但笔者并未发现关于他们比较系统化的、又同时比较容易理解中文教程,本文也算是填补这方面空白的一个尝试吧。所以,希望能在学习LR的同时将优化算法一并学了,相得益彰吧。

所以,本文预期的读者大概如下几类:

  1. 高阶机器学习人员:硕士毕业后5年及以上的机器学习经历,你就把这个当成一个关于LR和无约束优化算法的回顾材料好了,如有错误和不足请加以斧正。
  2. 中阶机器学习人员:硕士毕业后3~5年的机器学习经历,你可以把这个当做学习资料,把以前学过的东西串在一起,查漏补缺,做到真正懂得LR和相关优化的算法,从而能对工程实践做出正确的指导。
  3. 入门机器学习人员:硕士毕业后少于3年的机器学习经历,请你把纸和笔拿出来,把里面的公式一个个推导一遍,从而当你的leader告诉你某些事情的时候,你知道如何下手。
  4. 机器学习人员以外的高富帅和白富美们:你只需要知道LR是一个好用的自动分类算法,吩咐研究猿和攻城狮做就好了。另外,还可以用这篇文章嘲弄机器学习的屌丝们:累死累活,死那么多脑细胞,挣那两儿钱。

总而言之,不管你在机器学习上的造诣几何,希望这篇文章或多或少的都能给你带来点什么。笔者非常欢迎各方人士对本文以及任何与机器学习、数据挖掘相关问题的垂询、切磋、与探讨,好吧,闲话不多说,进入正题。

◆ ◆ ◆

正文概览

*鉴于文章的长度,这里只对文章内容做标题概览

2、初识逻辑回归

 3、L1    vs.    L2规则化

4、求解L2规则化的逻辑回归

5、OWL-QN:用L-BFGS求解L1规则化的逻辑回归

6、相关工作

7、前沿研究

◆ ◆ ◆

关于作者

柳超博士,天眼查创始人、董事长兼总经理,国家青年“千人计划”专家、北京市特聘专家、北京航空航天大学“大数据”特聘教授、中国大数据专家委员会委员、国家下一代互联网产业技术创新联盟专家。柳超博士创办天眼查之前,曾任搜狗科技首席科学家,美国微软研究院总部研究经理,美国国家自然科学基金数据挖掘方向的评审专家。

柳超于2007年在美国伊利诺伊大学获得计算机博士学位,并获得伊利诺伊大学杰出毕业论文奖,之后在数据挖掘、云计算、大数据分析、软件工程等方面取得了出色的研究成果。2008年至2012年,柳超博士任职于美国微软研究院,主管数据智能团队,期间在信息检索、数据挖掘和机器学习等诸多大数据相关领域作出了突出贡献,共计出版了 3 本英文专著、5篇国际期刊文章,以及30余篇国际一流学术会议文章,共计1300+次独立引用。

柳超博士在美期间曾担任美国国家自然科学基金数据挖掘方向的评审专家,多次应邀赴国际知名会议做主题报告。其工作成果在国际上备受关注,曾被国际电子电气工程师协会的IEEE Computer专业杂志以特邀封面文章的形式进行报道。

2012年,柳超博士回国加入腾讯科技(北京)有限公司,领导“腾讯搜索”的相关数据挖掘与机器学习业务。2014年,在腾讯与搜狗的战略合并之际加入搜狗科技,出任首席科学家,从零组建了搜狗数据科学研究院,全面负责搜狗互联网业务的数据挖掘与机器学习的前沿研究。
柳超博士创办的天眼查公司是中国首款关系发现平台,秉持“让每个人公平地看清这个世界”的使命,天眼查系列产品不仅可以可视化呈现复杂的商业关系,还可以深度挖掘和分析相关数据,预警风险等。目前,天眼查已经形成了针对媒体、金融、政府、法律等众多领域的大数据解决方案。更多精彩,请访问:www.tianyancha.com。

原文下载: LR_intro

How much math do I need to know to program?”

Source:  http://inventwithpython.com/blog/2012/03/18/how-much-math-do-i-need-to-know-to-program-not-that-much-actually/

Here are some posts I’ve seen on the r/learnprogramming subreddit forum:

Math and programming have a somewhat misunderstood relationship. Many people think that you have to be good at math or made good grades in math class before you can even begin to learn programming. But how much math does a person need to know in order to program?

Not that much actually. This article will go into detail about the kinds of math you should know for programming. You probably know it already.

For general programming, you should know the following:

  • Addition, subtraction, division, and multiplication – And really, the computer will be doing the adding, subtracting, dividing, and multiplying for you anyway. You just have to know when you need to do these operations.
  • Mod – The mod operation is the “remainder” and its sign is usually the % percent sign. So 23 divided by 7 is 3 with a remainder of 2. But 23 mod 7 is 2.
  • The even/odd mod test trick – If you want to know if a number is odd or even, mod it by 2. If the result is 0, the number is even. If the result is 1, the number is odd. 23 mod 2 is 1, so you know 23 is odd. 24 mod 2 is 0, so you know 24 is even. If x mod 2 is 0, you know that whatever number is stored in the variable x is even.
  • To get a percentage of a number, multiply that number by the percent number with the decimal point in front of it. So to get 54% of 279, multiple 0.54 * 279. This is why 1.0 often means 100% and 0.0 means 0%.
  • Know what negative numbers are. A negative number times a negative number is a positive. A negative times a positive is negative. That’s about it.
  • Know what a Cartesian coordinate system is. In programming, the (0, 0) origin is the top left corner of the screen or window, and the Y axis increases going down.
  • Know the Pythagorean theorem, and that it can be used to find the distance between two points on a Cartesian coordinate system. The Pythagorean theorem is a^2 + b^2 = c^2. What this usually means in programming is the distance between coordinate (x1, y1) and (x2, y2) will just be sqrt( (x1 – x2)^2 + (y1 – y2)^2 ).
  • Know what decimal, binary, and hexadecimal numbering systems are. Decimal numbers are the numbers we’re used to that have ten digits: 0 to 9. It’s commonly thought that humans develop this system because we have ten fingers and counted on our fingers.

Computers work with binary data, which is a number system with only two digits: 0 and 1. This is because we build computers out of electronics components where it’s cheaper to make them only recognize two different states (one state to represent 0 and the other to represent 1).

The numbers are still the exact same, but they are written out differently because there are a different number of digits in each system. Because hex has 6 more digits than the 0-9 numerals can provide, we use the letters A through F for the digits above 9. The easiest way to show these number systems is with an odometer. The following three odometers always show the same number, but they are written out differently in different number systems:


See the Odometer Number Systems page in a new window.
You don’t even have to know the math of converting a number from one number system to another. Every programming language has functions that can do this for you.

(On a side note, hexadecimal is used because one hexadecimal digit can represent exactly four binary digits. So since 3 in hex represents 0011 in binary and A in hex represents 1010. This has the nice effect that the hex number 3A (which is 58 in decimal) is written in binary as 00111010. Hex is used in programming because it is a shorthand for binary. Nobody likes writing out all those ones and zeros.)

And that’s about it. Other than the number system stuff, you probably already knew all the math you needed to know to do programming. Despite the popular conception, math isn’t really used that much in programming. You would need to know math in order to write programs that do, say, earthquake simulators. But that’s more about needing to know math for earthquakes rather than needing to know math for programming an earthquake simulator.

Advanced Mathematics in Some Areas of Programming

There’s a few areas of programming where some additional math knowledge might be needed (but for 95% of the software you’ll write, you don’t need to know it.)

3D games and 3D graphics – 3D stuff will usually involve knowing trigonometry and linear algebra (that is, math dealing with matrices). Of course, there are many 3D graphics libraries that implement all this math programming for you, so you don’t need to know the math.

2D physics (like Angry Birds) and 3D physics (like many popular 3D games use) – To do programming that involves physics, you’ll need to learn some physics equations and formulas (specifically mechanics, which is the type of physics with springs, gravity, and balls rolling down inclined planes.) However, there are several physics engines and software libraries that implement this stuff for you, so you really don’t need to know the physics equations to make a game like Angry Birds.

Cryptography – And really, by cryptography, I just mean RSA. In which case, you’d have to learn some math about how prime numbers work and doing the Greatest Common Divisor (which is a dead simple algorithm, although plenty of programming languages have gcd() function that does this for you.) Other encryption ciphers are mostly moving data around in specific steps. For example, this Flash animation shows the steps in the AES “Rijndael” cipher. All the steps are basically substituting numbers for other numbers, shifting rows of numbers over, mixing up columns of numbers, and doing basic addition with numbers.

And that’s just if you want to write your own encryption ciphers (which you shouldn’t do, because there are already plenty of good ones and without expertise your cipher will probably suck and be easily cracked.) If you just want to write a program that encrypts data, there are software libraries that implement encryption and decryption functions already.

So even for the above situations, you don’t need to know the math to make programs with 3D graphics, physics, or encryption. Just learn to use the libraries.

What You Do Need to Learn to Do Programming

What you do need to learn is how to model data and devise algorithms. This basically means, how to take some real-world calculation or some data processing, and write out code that makes the computer do it. For example, in the game Dungeons and Dragons the characters and monsters have several different statistics for combat:

  • HP, or hit points, is the amount of damage a person can take before dying. More HP means you can take more damage before dying.
  • AC, or armor class, is a measure of the chance your armor has of blocking an attack. The lower the AC, the more protective the armor is.
  • THAC0 (pronounced “thay-co”), or “To Hit Armor Class 0”, is a measure of how skillful the person is at making a successful hit on an opponent. The lower the THAC0, the more accurate the person’s attack is.
  • The damage of the weapon is written out as something like 1d6+2. This means the damage is the amount from rolling 1 six-sided dice, and then adding 2 to it. A damage stat of 2d4 would be rolling 2 four-sided dice and adding them together. (Dungeons and Dragons uses 4, 6, 8, 10, 12, and 20-sided dice.)

To see if an attacker hits a defender, the attacker rolls a twenty-sided die. If this number is equal to or greater than the attacker’s THAC0 minus the defender’s AC, then the hit is successful and the defender takes damage. Otherwise, the defender has either dodged or blocked the attack and takes no damage.

Let’s take two Dungeon and Dragons characters, Alice and Bob, with the following stats:

  • Alice: HP 14, AC 5, THAC0 18, DAMAGE 1d6
  • Bob: HP 12, AC 7, THAC0 16, DAMAGE 2d4

So Alice has two more hit points than Bob and better armor (remember, lower AC is better). But Bob is more likely to make a successful hit (remember, lower THAC0 is better) and does more damage. We can tell Bob’s damage is better because 2d4 will result in 2 to 8 points of damage, while Alice’s 1d6 will result in 1 to 6 points of damage. (If you knew statistics math, you could calculate that Bob’s expected value of damage is 5, which is larger than Alice’s expected value of damage is 3.5.)

So would you bet on Alice or Bob to win in a fight? It’s hard to tell, they seem pretty evenly matched. Even if you knew a lot of statistics, doing all these calculations would be a pain. But you don’t need to know statistics in order to write a program that simulates Dungeons and Dragons combat (that is, models this process) and then run several hundred or thousand simulated fights and see who wins on average.

Here’s such a program written in Python: (Download source)

import random, copy

NUM_FIGHTS = 1
VERBOSE = True

# Lower thac0 and lower ac values are better. Higher damage & hp values are better.
aliceTemplate = {'name': 'Alice', 'hp': 14, 'ac': 5, 'thac0': 18, 'dmgnum': 1, 'dmgsize':6, 'dmgmod': 0}
bobTemplate   = {'name': 'Bob',   'hp': 12, 'ac': 7, 'thac0': 16, 'dmgnum': 2, 'dmgsize':4, 'dmgmod': 0}

def display(s):
    if VERBOSE:
        print(s)

def attack(attacker, defender):
    if random.randint(1, 20) >= attacker['thac0'] - defender['ac']:
        damage = 0
        for i in range(attacker['dmgnum']):
            damage += random.randint(1, attacker['dmgsize'])
        damage += attacker['dmgmod']
        display('%s (%s hp) hits %s (%s hp) for %s points of damage. %s is reduced to %s hp.' % (attacker['name'], attacker['hp'], defender['name'], defender['hp'], damage, defender['name'], defender['hp'] - damage))
        defender['hp'] -= damage
    else:
        display('%s misses %s.' % (attacker['name'], defender['name']))

aliceWins = 0
bobWins = 0
for i in range(NUM_FIGHTS):
    display('======================')
    display('Start of combat #%s' % (i+1))
    alice = copy.deepcopy(aliceTemplate)
    bob = copy.deepcopy(bobTemplate)
    while True:
        attack(alice, bob)
        if bob['hp'] <= 0:
            break

        attack(bob, alice)
        if alice['hp'] <= 0:
            break
    if alice['hp'] <= 0:
        display('Alice has died.')
        bobWins += 1
    if bob['hp'] <= 0:
        display('Bob has died.')
        aliceWins += 1

print()
print('Alice won %s (%s%%) fights. Bob won %s (%s%%) fights.' % (aliceWins, round(aliceWins / NUM_FIGHTS * 100, 2), bobWins, round(bobWins / NUM_FIGHTS * 100, 2)))

When you run this program, it produces output like this:

======================
Start of combat #1
Alice misses Bob.
Bob (12 hp) hits Alice (14 hp) for 6 points of damage. Alice is reduced to 8 hp.
Alice misses Bob.
Bob misses Alice.
Alice misses Bob.
Bob misses Alice.
Alice misses Bob.
Bob misses Alice.
Alice (8 hp) hits Bob (12 hp) for 5 points of damage. Bob is reduced to 7 hp.
Bob misses Alice.
Alice misses Bob.
Bob misses Alice.
Alice misses Bob.
Bob (7 hp) hits Alice (8 hp) for 2 points of damage. Alice is reduced to 6 hp.
Alice (6 hp) hits Bob (7 hp) for 6 points of damage. Bob is reduced to 1 hp.
Bob misses Alice.
Alice (6 hp) hits Bob (1 hp) for 1 points of damage. Bob is reduced to 0 hp.
Bob has died.

Alice won 1 (100.0%) fights. Bob won 0 (0.0%) fights.

But maybe Alice just got lucky in this one fight. Let’s reprogram this program to turn off the verbose output (displaying text on the screen takes a lot more time than running the simulation) and up the number of fights to 30,000 (this is just changing the NUM_FIGHTS variable to 30000 and the VERBOSE variable to False):

Alice won 12909 (43.03%) fights. Bob won 17091 (56.97%) fights.

So we can see that with the given stats, Bob is at a slight advantage. The computer just ran 30,000 simulated fights. If we were to play 30,000 fights of Dungeons and Dragons with pencil, paper, and physical dice, it would take months to calculate this. But my laptop had the results in less than 8 seconds.

But what if we increased Alice’s hit points from 14 to 20. Who would win then?

Alice won 19438 (64.79%) fights. Bob won 10562 (35.21%) fights.

We see that those 6 extra hit points turns the tables and gives Alice the advantage. How about if her hit points were only increased to 16 instead of 20?

Alice won 15176 (50.59%) fights. Bob won 14824 (49.41%) fights.

We see that just tweaking the stats by 2 hit points is just enough to even out the advantages that Bob gets from his higher level of damage.

And when you look at this program, the only math it uses is addition, subtraction, and multiplication and division to find a percentage. Even if we made the simulation more sophisticated to account for the effects of magic spells, healing potions, multiple attackers, and switching to different weapons in mid-combat, we wouldn’t need to know more math or have made good math grades to do the programming for it.

Sure, go ahead and learn more math. It can only help you become a better programmer. But how much math do you need to know to program? Very little, actually.

UPDATE: I guess I’d add basic algebra to the required knowledge, but only insofar as that if X * 3 = 12 knowing why X is 4.

(Here’s a list of other discussions on Reddit about this topic.)

既懂数学又会编程,全方位解读如何成为一名投行Quant工

2016-04-12 UniCareer

Quant是做什么的?

Quant的工作就是设计并实现金融的数学模型(主要采用计算机编程),包括衍生物定价,风险估价或预测市场行为等。所以Quant更多可看为工程师,按中国的习惯性分类方法就是理工类人才,而不是文科人才,这个和金融有一定的区别(当然金融也有很多理工的内容)。

有哪几种 Quant?

(1) Desk Quant

Desk Quant 开发直接被交易员使用的价格模型,优势是接近交易中所遇到的Money和机会,劣势是压力很大。

(2) Model Validating Quant

Model Validating Quant 独立开发价格模型,不过是为了确定Desk Quant开发的模型的正确性。优势是更轻松,压力比较小,劣势是这种小组会比较没有作为而且远离Money。

(3) Research Quant

Research Quant 尝试发明新的价格公式和模型,有时还会执行Blue-Sky Research(不太清楚是什么),优势是比较有趣(对喜欢这些人来说),而且你学到很多东西。劣势是有时会比较难证明有你这个人存在(跟科学家一样,没有什么大的成果就没人注意你)

(4) Quant Developer

其实就是名字被美化的程序员,但收入很不错而且很容易找到工作。这种工作变化很大,它可能是一直在写代码,或者调试其他人的大型系统。

(5) Statistical Arbitrage Quant

Statistical Arbitrage Quant 在数据中寻找自动交易系统的模式(就是套利系统),这种技术比起衍生物定价的技术有很大的不同,它主要用在对冲基金里,而且这种位置的回报是极不稳定的。

(6) Capital Quant

Capital Quant 建立银行的信用和资本模型,相比衍生物定价相关的工作,它没有那么吸引人,但是随着巴塞尔II银行协议的到来,它变的越来越重要,你会得到不错的收入(但不会很多),更少的压力和更少的工作时间。

人们投资金融行业就是为了赚钱,如果你想获得更多的收入,你就要更靠近那些钱的”生产”的地方,这会产生一种接近钱的看不起那些离得比较远的人的现象,作为一个基本原则,靠近钱比远离钱要来得容易。

Quant工作的领域?

(1) FX

FX就是外汇交易的简写。合同趋向于短期,大量的金额和简单的规定,所以重点在于很快速度的建立模型。

(2) Equities

Equities的意思是股票和指数的期权,技术偏向于偏微分方程(PDE)。它并不是一个特别大的市场。

(3) Fixed Income

Fixed Income的意思是基于利息的衍生物,这从市值上来说可能是最大的市场,他用到的数学会更加复杂因为从根本上来说他是多维的,技术上的技巧会用的很多,他的收入比较高。

(4) Credit Derivatives

Credit Derivatives是建立在那些公司债务还清上的衍生产品,他发展的非常快并有大量需求,所以也有很高的收入,尽管如此,他表明了一些当前经济的泡沫因素。

(5) Commodities

Commodities因为最近几年生活用品价格的普遍涨价,也成为一个发展迅速的领域。

(6) Hybrids

Hybrids是多于一个市场的衍生物市场,典型情况是利息率加上一些其它东西,它主要的优势在于可以学到多种领域的知识,这也是当前非常流行的领域。

Quant一般在哪些公司工作?

(1) 商业银行 (HSBC, RBS)

商业银行对你要求少,也给的少,工作会比较稳定。

(2) 投行 (高盛, Lehman Brothers)

投行需要大量的工作时间但工资很高,不是很稳定的工作,总的来说,美国的银行收入比欧洲银行高,但工作时间更长。

(3) 对冲基金 (Citadel Group)

对冲基金需要大量的工作时间和内容,他们也处在高速发展同时不稳定的情况中,你可能会得到大量的回报,也可能几个月后就被开除。

(4) 会计公司

大型会计公司会有自己的顾问quant团队,有些还会送他们的员工去Oxford读Master,主要的劣势在于你远离具体的行为和决策,而且厉害的人更愿意去银行,所以你比较难找到人请教。

(5) 软件公司

外包quant模型变得越来越流行,所以你去软件公司也是一个选择,劣势和会计公司比较类似。

成为一个Quant需要看哪些书?
UniCareer诚意推荐书单
 
《Options Future and Other Derivatives》
John C. Hull

不管是找工作还是senior quant都会用到。John Hull本人也是非常厉害的,各个方面都有开创性的成果。现在Toronto Uni,经典中的经典,涉猎还算广泛,不过不够数学—-人称华尔街的圣经,自然不算很难。

《Stochastic Calculus for Finance II》
Steven E. Shreve

Shreve的新书,非常elegant, 非常仔细,非常数学完备,适合数学背景, 但是比较厚,对于入门来说还是3好。作者现在CMU纽约。教授。顶尖人物。I是讲离散模型,II讲连续模型。

《Liar’s Poker》
Michael Lewis 

讲以前Solomon brothers的Arb team的,当时是世界最厉害的quant trader。这本书搞trading的人都会看。

《C++ Design Patterns and Derivatives Pricing》
Mark S. Joshi 

对于懂得C++基础的人来说很重要,更重要的是教你学会Monte Carlo。

《Modeling Derivatives in C++ (Wiley Finance)》
Justin London 
学习了一年的金工,其实就这本书最核心最实用,其他的理论书看看就好。很多理论书还有重复部分,注意区分。
《The Concepts and Practice of Mathematical Finance》
Mark S. Joshi 
这本书的目标在于覆盖一个优秀quant应该知道的知识领域,其中包括强列推荐你在应聘工作之前看的一些编程项目。
《Interest Rate Models – Theory and Practice》
Damiano Brigo / Fabio Mercurio 
评价超高的书。这本书最大的精华是关于Libor market model的论述。本书的特点是作者将所有细节和盘托出,包括大量的数值结果,这样可以方便读者自学和验证。
《Probability with Martingales》
David Williams
主要是围绕martingale展开的,前面一部份介绍必要的measure theory的部分,点到即止,都是后面基本的probability theory需要用到的。即使你之前不懂measure theory也能看懂。难怪是给undergraduate用的。Williams是这个方向上文笔最好的数学家了。
 
《Monte Carlo Methods in Financial Engineering》
Paul Glasserman
本书很实用,紧扣标题,就是围绕着金融工程中蒙特卡洛的应用展开,真正读过的人可能会有感受,此书不太适合作为first book来读,最好两方面都已经有所涉及,再来读收获更大也更舒服些。
《My Life as a Quant: Reflections on Physics and Finance》
Emanuel Derman
作者是第一代quant,以前是GS的quant 研究部门head,现在哥大。是stochastic vol领域顶尖人物,其实也是很多其他领域顶尖人物。
福利领取方式
1. 关注公众号:UniCareer2. 回复关键字:我爱读书

3. 按照提示完成操作

3个工作日内,Quant十本书福利就会送到你的邮箱啦~

成为一个Quant需要知道一些什么?

根据你想工作的地方不同,你需要学习的知识变化很大,在写着篇文章的时间(1996),我会建议将我的书全部学会就可以了。很多人错误的把学习这些知识看作仅仅看书而已,你要做的是真正的学习,就像你在准备参加一个基于这些书内容的考试,如果你对能在这个考试里拿A都没有信心的话,就不要去面试任何的工作。

面试官更在乎你对基本知识的了解是否透彻,而不是你懂得多少东西,展示你对这个领域的兴趣也很重要,你需要经常阅读Economist, FT 和Wall Street Journal,面试会问到一些基本微积分或分析的问题,例如Logx的积分是什么。问到类似Black-Scholes公式怎么得出的问题也是很正常的,他们也会问到你的论文相关的问题。

面试同样也是让你选择公司的一个机会,他们喜欢什么样的人,他们关心的是什么之类的答案可以从他们的问题中得出,如果问了很多关于C++语法的问题,那么要小心选择除非那是你想做的工作。一般来说,一个PhD对得到Quant的Offer是必需的。

有一个金融数学的Master学位会让你在银行风险或交易支持方面却不是直接Quant方面的工作,银行业变得越来越需要数学知识,所以那些东西在银行的很多领域都有帮助。

在美国,读了一个PhD之后再读一个Master变得越来越普遍,在UK这依然比较少见。

一般哪些专业对口Quant?

据观察,Quant一般的专业会是数学,物理,金融工程(金融数学)。其实虽然不是特别多,但是还是有一些投行招手Master金工的Quant,一般几个好的FE专业都有去做Quant的硕士生。

编程      

所有类型的Quant都在编程方面花费大量时间(多于一半)。尽管如此,开发新的模型本身也是很有趣的一件事,标准的实现方法是用C++。一个想成为quant的人需要学习C++,有些其他地方使用Matlab所以也是一个很有用的技能,但没C++那么重要。VBA也用的很多,但你可以在工作中掌握它。

收入   

一个Quant能赚多少?一个没有经验的Quant每年大概会挣到税前60k-100k美元。奖金的话不会太高,但是如果行情好的话,也非常的客观,一般我听说的话,刚入职第一年一般可以拿到一两万刀的奖金。如果你的工资超出这个范围,你要问自己Why?收入会迅速的增长,奖金也是总收入中一个很大的组成部分,不要太在乎开始的工资是多少,而是看重这个工作的发展机会和学习的机会。

工作时间 

一个Quant工作的时间变化很大。在RBS我们8:30上班,6pm下班。压力也是变化很大的, 一些美国银行希望你工作时间更长。 在伦敦有5-6个星期的假期,而在美国2-3个是正常的。

怎样让小孩透彻理解基本的数学概念:可汗学院数学小视频合集

这年头,但凡和教育沾点边的,还有谁不知道可汗学院啊-Khan Academy?前段时间他的故事被编成了鸡汤文,弄得我妈都知道,因为比尔盖茨都为他唱赞歌。

好吧,这个故事你多少也知道,咱们就简单回顾一下,再进入正题:

萨尔曼·可汗是美籍孟加拉国移民,毕业于麻省理工学院和哈佛大学。

萨尔曼·可汗有个小侄女叫纳迪亚,2004年她在新奥尔良上七年级,数学成绩一直不好,要求可汗给她辅导。可汗和纳迪亚不在同一个城市,于是通过互联网教纳迪亚学数学,讲得生动有趣,概念清晰,纳迪亚的数学成绩提高神速。

很快,他的朋友就知道了,也让可汗给孩子辅导数学。经过可汗辅导的孩子,数学成绩都直线上升。

可汗想,这样辅导效率太低,不如做成视频,放到互联网上,让大家免费观看。结果回到家他就躲进衣帽间里,把自己关起来,拿摄像头开始录制视频。

他的视频非常生动,基本能在十分钟内把一个数学概念讲完,在互联网上引起了很大的关注。结果一发不可收拾,他把自己关在衣帽间录制了一年的视频,从小学数学,到高中的微积分,再到大学的高等数学,统统讲了个遍,共计4800个视频。

这些视频在互联网上获得了极大的成功,点击率接近5亿,共有4800万人观看。在美国,有2万多所学校,上数学课时老师会让学生不时观看可汗的视频,看完视频后老师负责答疑。老师们说:“如果你在美国教数学,你就不可能没听说过萨尔曼·可汗。”

2011年,可汗做了一次TED演讲,比尔盖茨为他站台,和他问答互动。演讲主题是:什么才是未来的教育模式?有兴趣的朋友可以点开看看。

盖茨是可汗粉。他曾经花费很多时间教3个孩子数学和科学的基本概念,可孩子们总是听得懵懵懂懂。2010年初,有人向他推荐了可汗的网站。没想到,那些他怎么也解释不清的知识点,汗通过短短12分钟的视频,就让孩子融会贯通。

檩子很早就知道可汗和他的小视频了。看过几个,可汗的确很牛,能用一块黑板,一枝笔把抽象的数学概念通过写写画画解释得很明白。

当时很想把可汗推荐给大家,不过这些视频虽好,却是全英文的,不要说小孩,英文六级的大人看得也会很费劲。所以就算了。

这次,既然大家让推荐资料,我又去网上搜了一下,发现网易公开课里可汗的不少小视频已经做了一定程度的汉化,配上了中英文字幕。虽然还没有中文配音,但是看懂是没问题了。

目前,很多可汗的视频都在网易公开课上能找到,有中英文字幕。虽然涵盖多个科目,不过数学小视频仍然是主打。大概有40个主题。
我看了一些,感觉最实际的使用方式是这样的:家长先去看,了解一下可汗的讲解方法,然后参照可汗的方法把这个概念亲自讲给孩子听。可汗视频的价值在于可汗能用简单的语言和例子把一个抽象的概念转化成孩子能听得明白的话,讲解方式是最值得借鉴的。

可汗的视频很多,不过最经典的还是数学的基本概念讲解。檩子做了一点小功课,把可汗学院的算术与代数预备课程的视频目录找出来了,列在这里,供大家检索参考。(点击阅读原文,可以看到所有视频的链接,大家也可以去网易公开课找找)

可汗学院的 算术与代数预备课程,是从零开始学习数学的起始点,是代数课程的先导课。对于那些想从最基础开始学习数学,或者以后想要学习代数课程的幼儿园大班和小学生来说,这套课程比较适合。

1、加法与减法

主要内容:正数和负数的相加减,从1+1=2开始

[第1集] 加法1

[第2集] 加法2

[第3集] 减法1

[第4集] 减法2

[第5集] 减法3

[第6集] 加法3

[第7集] 加法4

[第8集] 减法3

[第9集] 为什么可以借代

[第10集] 加法5

[第11集] 减法4

[第12集] 减法应用题

[第13集] 交替心算减法

[第14集] 负数介绍

[第15集] 加负数

[第16集] 加不同符号的数

[第17集] 加减负数

[第18集] 两位数相加

[第19集] 加减法应用题

2、乘法与除法

主要内容:乘法与除法,正数和负数的乘除法,位值等

[第1集] 基本乘法

[第2集] 乘法表

[第3集] 10 11 12的乘法表

[第4集] 除法1

[第5集] 除法2

[第6集] 将总数平分及其应用

[第7集] 两位数乘一位数

[第8集] 两位数乘两位数

[第9集] 数字相乘及其应用2

[第10集] 格形乘法

 

3、数的性质

主要内容:交换律,结合律,分配率,恒等式等等

[第1集] 加法交换律

[第2集] 乘法交换律

[第3集] 加法结合律

[第4集] 乘法结合律

[第5集] 加法结合律性质

[第6集] 分配律性质

[第7集] 分配律性质2

[第8集] 分配律性质例1

[第9集] 数性质和绝对值

[第10集] 恒等性质1

[第11集] 恒等性质例2

[第12集] 0的恒等性质

[第13集] 加法的逆的性质

[第14集] 乘法的逆的性质

[第15集] 为什么除以0没有定义

[第16集] 为什么0除以0没有定义

[第17集] 没有定义和不确定

 

 

4、分数

主要内容:分数的计算与转换

[第1集] 分数的分子和分母

[第2集] 解释分数的意义

[第3集] 等价分数

[第4集] 等价分数例题

[第5集] 分数比较大小

[第6集] 最简分数

[第7集] 分数比较大小第2部分

[第8集] 分数排序

 

5、小数

主要内容:概念的理解,对小数的计算,转换等

[第1集] 小数加法

[第2集] 小数位值

[第3集] 小数位值2

[第4集] 用数轴表示小数

[第5集] 小数近似

[第6集] 小数估计

[第7集] 小数比较

[第8集] 小数加法

[第9集] 小数减法

[第10集] 小数减法应用题

[第11集] 小数乘以10的指数

[第12集] 小数乘法

[第13集] 小数乘法

[第14集] 小数除以10的指数

[第15集] 小数除法1

[第16集] 小数除法2

[第17集] 小数除法3

[第18集] 小数乘法3

[第19集] 小数和分数互化

[第20集] 把分数化成小数例题

[第21集] 把分数化成小数

[第22集] 把分数转换为小数例1

[第23集] 把分数转换为小数例2

[第24集] 把循环小数化成分数1

[第25集] 把循环小数化成分数2

[第26集] 把小数化成分数1例1

[第27集] 把小数化成分数1例2

[第28集] 把小数化成分数1例3

[第29集] 把小数化成分数2例1

[第30集] 把小数化成分数2例2

[第31集] 百分数和小数

[第32集] 把一个数表示成小数 百分数 分数

[第33集] 把一个数表示成小数 百分数 分数2

[第34集] 数轴上一点

[第35集] 数字排序

 

 

6、负数

主要内容包括:理解与使用负数

[第1集] 负数介绍

[第2集] 负数的大小排序

[第3集] 加负数

[第4集] 加不同符号的数

[第5集] 加减负数

[第6集] 正数和负数相乘

[第7集] 正数和负数除法

[第8集] 为什么负数乘以负数得到正数

 

7、约数与倍数

主要内容:质数,最小公倍数,最大公约数

[第1集] 质数

[第2集] 判断质数

[第3集] 判断整除

[第4集] 共同整除的例题

[第5集] 找一个数的因数

[第6集] 质因数分解

[第7集] 最小公倍数

[第8集] 最小公倍数(LCM)

[第9集] 最大公约数

[第10集] 代数表达式的最小公倍数

[第11集] 3的整除性质

8、指数

主要内容:不用代数来理解指数

 

[第1集] 理解指数

[第2集] 理解指数2

[第3集] 指数第一级

[第4集] 指数第二级

[第5集] 指数第三级

[第6集] 指数法则1

[第7集] 指数法则2

 

9、比率和比例

主要内容:不用代数来理解比率
[第1集] 比例介绍

[第2集] 理解比例

[第3集] 比例分数的最简形式

[第4集] 比例化简

[第5集] 求比例中的未知数

[第6集] 求单位速度

 

10、计算顺序

内容包括:表达式中各种计算的运算顺序

[第1集] 运算顺序介绍

[第2集] 更复杂的运算顺序例子

[第3集] 运算顺序1

[第4集] 运算顺序2

点击阅读原文,去小花生网看这些视频的播放链接。

本文由小花生编写,公众号转载须获授权

相关阅读:

花生快讯:

感谢订阅 “小花生网”

每天推送国内外最优秀的教育资源

周一:新书开团

周二:国外实用的教育方法

周三:英文原版趣味学习资源

周四:不同年龄的中文好书

周五:儿童电影/动画片/纪录片

周六:美好生活画报

周日:引发深度思考的文章

纯粹数学的雪崩效应:庞加莱猜想何以造福了精准医疗?

2016-04-12 顾险峰 赛先生


图1 庞加莱猜想电脑三维模型

顾险峰 (纽约州立大学石溪分校终身教授,清华大学丘成桐数学科学中心访问教授,计算共形几何创始人)

最近英国上议院议员马特瑞德利(Matt Ridley)在《华尔街日报》上撰文《基础科学的迷思》(The Myth of Basic Science)。他认为“科学驱动创新,创新驱动商业”这一说法基本上是错误的,反而是商业驱动了创新,创新驱动了科学,正如科学家被实际需求所驱动,而不是科学家驱动实际需求一样。总之,他认为“科学突破是技术进步的结果,而不是原因”。

瑞德利先生的言论反映了许多人对基础科学的严重误解,会给年轻学子们带来思想混乱和价值观念上的困扰,有必要加以澄清。诚然,商业需求和工程实践会为基础科学提供研究的素材,比如历史上最优传输理论(OptimalMass Transportation Theory)和蒙日-安培方程(Monge-Ampere)起源于土石方的运输,最后猜想被康塔洛维奇解决,康塔洛维奇为此获得了诺贝尔经济学奖。数年前,为了解决医学图像的压缩问题,陶哲轩提出了压缩感知(Compressive Sensing)理论。但是,从根本上而言,基础科学的源动力来自于科学家对于自然真理的好奇和对美学价值的追求。基础科学上的突破,因为揭示了自然界的客观真理,往往会引发应用科学的革命。纯粹数学的研究因为其晦涩抽象,实用价值并不明显直观,普罗大众一直倾向于认为其“无用”。但实际上,纯粹数学对应用科学的指导作用是无可替代的。

计算机科学和技术发展的一个侧面就在于将人类数千年积累的知识转换成算法,使得没有经历过职业训练的人也可以直接使用最为艰深的数学理论。在拓扑和几何领域,往往很多具有数百年历史的定理仅仅在最近才被转换成算法。但是,依随计算机技术的迅猛发展,从定理到算法的过程日益加速。很多新近发展的数学理论被迅速转换成强有力的算法,并在工程和医疗领域被广泛应用。

历史一再表明,以满足人类好奇心为出发点的基础理论研究,其本质突破往往不能引起当时人类社会的重视,宛若冰川旷谷中一声微弱的呐喊,转瞬间随风消逝,但是这一声往往会引发令天空变色,大地颤抖的雪崩。庞加莱猜想的证明就是一个鲜明的实例,虽然雪崩效应还没有被大众所察觉,但是雪崩已经不可逆转地开始了!

1  庞加莱猜想

法国数学家庞加莱(Jules Henri Poincaré)是现代拓扑学的奠基人。拓扑学研究几何体,例如流形,在连续形变下的不变性质。我们可以想象曲面由橡皮膜制成,我们对橡皮膜拉伸压缩,扭转蜷曲,但是不会撕破或粘联,那么这些形变都是连续形变,或被称之为拓扑形变,在这些形变下保持不变的量就是拓扑不变量。如果一张橡皮膜曲面经由拓扑形变得到另外一张橡皮膜曲面,则这两张曲面具有相同的拓扑不变量,它们彼此拓扑等价。如图2 所示,假设兔子曲面由橡皮膜做成,我们象吹气球一样将其膨胀成标准单位球面,因此兔子曲面和单位球面拓扑等价。

图2. 兔子曲面可以连续形变成单位球面,因此兔子曲面和球面拓扑等价。

兔子曲面无法连续形变成轮胎的形状,或者图3中的任何曲面。直观上,图5中小猫曲面有一个“洞”,或称“环柄”;图3中的曲面则有两个环柄。拓扑上,环柄被称为亏格。亏格是最为重要的拓扑不变量。所有可定向封闭曲面依照亏格被完全分类。


图3. 亏格为2的封闭曲面。亏格是曲面最重要的拓扑不变量。

庞加莱思考了如下深刻的问题:封闭曲面上的“洞”是曲面自身的内蕴性质,还是曲面及其嵌入的背景空间之间的相对关系?这个问题本身就是费解深奥的,我们力图给出直观浅近的解释。我们人类能够看到环柄形成的“洞”,是因为曲面是嵌入在三维欧式空间中的,因此这些“洞”反应了曲面在背景空间的嵌入方式,我们有理由猜测亏格反映了曲面和背景空间之间的关系。

图4. 曲面上生活的蚂蚁如何检测曲面的拓扑?

但是另一方面,假设有一只蚂蚁自幼生活在一张曲面上,从未跳离过曲面,因此从未看到过曲面的整体情形。蚂蚁只有二维概念,没有三维概念。假设这只蚂蚁具有高度发达的智力,那么这只蚂蚁能否判断它所生活的曲面是个亏格为0的拓扑球面,还是高亏格曲面?

图5. 亏格为1的曲面上,无法缩成点的闭圈。

庞加莱最终悟到一个简单而又深刻的方法来判断曲面是否是亏格为0的拓扑球面:如果曲面上所有的封闭曲线都能在曲面上逐渐缩成一个点,那么曲面必为拓扑球面。比如,我们考虑图5中小猫的曲面,围绕脖子的一条封闭曲线,在曲面上无论怎样变形,都无法缩成一个点。换言之,只要曲面亏格非零,就存在不可收缩成点的闭圈。如果流形内所有的封闭圈都能缩成点,则流形被称为是单连通的。庞加莱将这一结果向高维推广,提出了著名的庞加莱猜想:假设M是一个封闭的单连通三维流形,则M和三维球面拓扑等价。

图6. 带边界的三流形,用三角剖分表示。

在现实世界中,无法看到封闭的三维流形:正如二维封闭曲面无法在二维平面上实现,三维封闭流形无法在三维欧式空间中实现。图6显示了带有边界的三维流形,例如实心的兔子和实心的球体拓扑等价。这些三维流形用三角剖分来表示,就是用许多四面体粘合而成。如图所示,体的三角剖分诱导了其二维边界曲面的三角剖分。实心球实际上是三维拓扑圆盘,我们可以将两个三维拓扑圆盘沿着边界粘合,就得到三维球面,恰如我们可以将两个二维拓扑圆盘沿着边界粘合而得到二维球面一样。当然,这已经超出人们的日常生活经验。

2  曲面单值化定理

近百年来,庞加莱猜想一直是拓扑学最为基本的问题,无数拓扑学家和几何学家为证明庞加莱猜想而鞠躬尽瘁死而后已。相比那些最后成功的幸运儿,众多默默无闻,潦倒终生的失败者更加令人肃然起敬。老顾曾经访问过吉林大学数学学院,听闻了有关何伯和教授的生平事迹。何教授终生痴迷于庞加莱猜想的证明,苦心孤诣,废寝忘食,愈挫愈奋,九死不悔,直至生命终结,对于庞加莱猜想依然念念不忘。何教授绝对不是为了任何实用价值或者商业利益而奋斗终生的,而是为了对于自然界奥秘的好奇,对于美学价值的热切追求,这种纯粹和崇高,是人类进步的真正动力!


图7. 人脸曲面上连接两点的测地线。

作为拓扑学最为基本的问题,庞加莱猜想的本质突破却来自于几何。给定一个拓扑流形,如给定图6中四面体网格的组合结构,我们可以为每条边指定一个长度,使得每个四面体都是一个欧式的四面体,这样我们就给出了一个黎曼度量。所谓黎曼度量,就是定义在流形上的一种数据结构,使得我们可以确定任意两点间的最短测地线。图7显示了人脸曲面上的两条测地线。黎曼度量自然诱导了流形的曲率。曲率是表征空间弯曲的一种精确描述。给定曲面上三个点,我们用测地线连接它们成一个测地三角形。如果曲面为欧几里德平面,那么测地三角形内角和为180度。球面测地三角形的内角和大于180度,马鞍面的测地三角形的内角和小于180度。测地三角形内角和与180度的差别就是三角形的总曲率。那么,给定一个拓扑流形,我们能否选择一个最为简单的黎曼度量,使得曲率为常数呢?

图8. 曲面单值化定理,所有封闭曲面都可以保角地形变成常曲率曲面。

这一问题的答案是肯定的,这就是曲面微分几何中最为根本的单值化定理。单值化定理是说大千世界,各种几何形状千变万化,但是无论它们如何变化,都是万变不离其宗:所有的曲面都可以共形地变换成三种标准曲面中的一种,单位球面,欧几里德平面和双曲平面。标准空间对应着常数值曲率,+1,0和-1,如图8所示。所谓共形变换,就是保持局部形状的变换,局部上看就是相似变换。相似变换保持角度不变,因此共形变换也被称为是保角变换。图9显示了从曲面到平面的一个共形变换。单值化定理断言了所有封闭曲面可以配有三种几何中的一种:球面几何,欧氏几何和双曲几何。曲面微分几何中几乎所有的重要定理都绕不过单值化定理。


图9. 共形变换保持局部形状。

3  瑟斯顿几何化猜想

为了证明庞加莱猜想,菲尔兹奖得主瑟斯顿推广了单值化定理到三维流形情形。任何三维流形,都可以经历一套标准手续分解成一系列的最为简单的三维流形,即所谓的素流形。素流形本身无法被进一步分解,同时这种分解本质上是唯一的。瑟斯顿提出了石破天惊的几何化猜想:所有的素三维流形可以配有标准黎曼度量,从而具有8种几何中的一种。特别地,单连通的三维流形可被配有正的常值曲率度量,配有正的常值曲率的3维流形必为3维球面。因此庞加莱猜想是瑟斯顿几何化猜想的一个特例。

图10. 瑟斯顿的苹果,几何化猜想。

图10显示了瑟斯顿几何化的一个实例。假设我们有一个苹果,三只蛀虫蛀蚀了三条管道,如左帧所示,这样我们得到了一个带边界的三维流形。根据几何化纲领,这个被蛀蚀的苹果内部容许一个双曲黎曼度量,使得其边界曲面的曲率处处为-1。我们将配有双曲度量的苹果周期性地嵌在三维双曲空间之中,得到右帧所示图形。

4  哈密尔顿的里奇曲率

本质的突破来自于哈密尔顿的里奇曲率流(Hamilton’s Ricci Flow)。哈密尔顿的想法来自经典的热力学扩散现象。假设我们有一只铁皮兔子,初始时刻兔子表面的温度分布并不均匀,依随时间流逝,温度渐趋一致,最后在热平衡状态,温度为常数。哈密尔顿设想:如果黎曼度量依随时间变化,度量的变化率和曲率成正比,那么曲率就像温度一样扩散,逐渐变得均匀,直至变成常数。如图11所示,初始的哑铃曲面经由曲率流,曲率变得越来越均匀,最后变成常数,曲面变成了球面。

图11. 曲率流使得曲率越来越均匀,直至变成常数,曲面变成球面。

在二维曲面情形,哈密尔顿和Ben Chow证明了曲率流的确将任何一个黎曼度量形变成常值曲率度量,从而给出了曲面单值化定理的一个构造性证明。但是在三维流形情形,里奇曲率流遇到了巨大的挑战。在二维曲面情形,在曲率流过程中,在任意时刻,曲面上任意一点的曲率都是有限的;在三维流形情形,在有限时间内,流形的某一点处,曲率有可能趋向于无穷,这种情况被称为是曲率爆破(blowup),爆破点被称为是奇异点(singularity)。

如果发生曲率爆破,我们可以将流形沿着爆破点一切两半,然后将每一半接着实施曲率流。如果我们能够证明在曲率流的过程中,曲率爆破发生的次数有限,那么流形被分割成有限个子流形,每个子流形最终变成了三维球面。如果这样,原来流形由有限个球粘合而成,因而是三维球面,这样就证明了庞加莱猜想。由此可见,对于奇异点的精细分析成为问题的关键。哈密尔顿厘清了大多数种类奇异点的情况,佩雷尔曼解决了剩余的奇异点种类。同时,佩雷尔曼敏锐地洞察到哈密尔顿的里奇流是所谓熵能量的梯度流,从而将里奇流纳入了变分的框架。佩雷尔曼给出了证明的关键思想和主要梗概,证明的细节被众多数学家进一步补充完成。至此,瑟斯顿几何化猜想被完全证明,庞加莱猜想历经百年探索,终于被彻底解决。

5 庞加莱猜想带来的计算技术

庞加莱猜想本身异常抽象而枯燥:单连通的闭3-流形是三维球面,似乎没有任何实用价值。但是为了证明庞加莱猜想,人类发展了瑟斯顿几何化纲领,发明了哈密尔顿的里奇曲率流,深刻地理解了三维流形的拓扑和几何,将奇异点的形成过程纳入了数学的视野。这些基础数学上的进展,必将引起工程科学和实用技术领域的“雪崩”。比如,里奇曲率流技术实际上给出了一种强有力的方法,使得我们可以用曲率来构造黎曼度量

里奇曲率流属于非线性几何偏微分方程,里奇流的方法实际上是典型的几何分析方法,即用偏微分方程的技术来证明几何问题。几何分析由丘成桐先生创立,庞加莱猜想的证明是几何分析的又一巨大胜利。当年瑟斯顿提倡用相对传统的拓扑和几何方法,例如泰西米勒理论和双曲几何理论来证明,也有数学家主张用相对组合的方法来证明,最终还是几何分析的方法拔得头筹。

哈密尔顿的里奇流是定义在光滑流形上的,在计算机的表示中,所有的流形都被离散化。因此,我们需要建立一套离散里奇流理论来发展相应的计算方法。历经多年的努力,笔者和合作者们建立了离散曲面的里奇曲率流理论,证明了离散解的存在性和唯一性。因为几乎所有曲面微分几何的重要问题,都无法绕过单值化定理。我们相信离散曲率流的计算方法必将在工程实践中发挥越来越重要的作用 [1]


图12. 离散里奇流计算的带边曲面单值化。

图8和图12显示了离散里奇流算出的封闭曲面和带边界曲面的单值化。本质上,这两幅图统摄了现实生活中所有可能的曲面,它们都被共形地映到了三种标准曲面上,球面、欧氏平面和双曲平面。这意味着,如果我们发明了一种新的几何算法,适用于这三种标准曲面,那么这一算法也适用于所有曲面。因此,离散曲率流的技术极大地简化了几何算法设计。

6 精准医疗

庞加莱猜想所诱发的离散曲率流方法被广泛应用于精准医疗领域。人体的各种器官本质上都是二维曲面或三维流形,曲率流方法对于这些器官几何特征的分析和比较起到了不可替代的作用。


图13. 虚拟肠镜技术。

虚拟肠镜 

直肠癌是男子的第四号杀手,仅在心脑血管疾病之后。中年之后,每个人都会自然长出直肠息肉,息肉会逐年增长,如果息肉直径达到一定尺寸,由于摩擦息肉会发生溃疡,长期溃疡会导致癌变。但是直肠息肉的生长非常缓慢, 一般从息肉出现直到临界尺寸需要七八年,因此对息肉的监控对于预防直肠癌起着至关重要的作用。中年人应该每两年做一次肠镜检查。传统的肠镜检查方法需要对受检者全身麻醉,将光学内窥镜探入直肠。老年人肠壁比较薄弱,容易产生并发症。同时,肠壁上有很多皱褶,如果息肉隐藏在皱褶中,医生会无法看到而产生漏检。

近些年来,北美和日本采用了虚拟肠镜技术。受检者的直肠图像由断层扫描技术来获取,直肠曲面可以从图像重建出来,如图14所示。我们需要将直肠展开摊平,从而使所有皱褶暴露出来,以便于寻找息肉和测量它们的尺寸。同时,如图13所示,在检查中同一受检者的直肠被扫描两次,每次扫描都是采用不同的姿态。直肠曲面柔软而富有弹性,不同的扫描得到的曲面之间相差很大的弹性形变。我们需要在两张曲面间建立光滑双射。在两张三维曲面间建立映射相对困难,当我们将曲面摊开展平成平面长方形后,在平面区域间计算映射会简单很多。将直肠曲面摊开展平等价于为曲面赋上一个曲率处处为0的黎曼度量,我们可以直接应用里奇曲率流的算法加以实现,如图14所示。

图14. 用里奇曲率流将直肠曲面摊开展平。

目前,虚拟肠镜技术在北美和日本被广泛采用,(但在中国还没有普及),主要是因为这种方法可以提高安全性,降低漏检率,降低人力成本。虚拟肠镜技术的普及极大地提高了早期直肠癌的发现几率,降低了直肠癌的死亡率,为人类的健康事业做出了巨大贡献。


图15. 虚拟膀胱镜。

同样的方法可以用于膀胱等其他器官,如图15所示。膀胱癌的最主要特征是膀胱壁变厚,同时内壁不再光滑,出现菜花状的几何纹理。这些症状可以用虚拟膀胱镜的方法定量得到。传统膀胱镜的方法病人需要忍受很大的痛苦,虚拟膀胱镜的方法极大地减轻了病患的疼痛,因而具有很大的优势。


图16. 用里奇曲率流将大脑皮层曲面共形映到单位球面,以便于对照比较。

脑神经疾病的预防诊断

脑退化症(Alzheimer’s disease,俗称老年痴呆症),癫痫,儿童自闭症等脑神经疾病严重地威胁着人类的健康安全。对于这些疾病的预防和诊断具有重要的现实意义。通过核磁共振成像技术,我们能够获取人类的大脑皮层曲面,如图16所示。大脑皮层曲面的几何非常复杂,有大量的皱褶沟回结构,并且这些几何结构因人而异,依随年龄变化而变化。例如老年痴呆症往往伴随大脑皮层一部分区域的萎缩。为了监控病情的发展,我们需要每隔几个月就扫描一下病人的大脑,然后将不同时期得到的大脑皮层曲面进行精确地对比。在三维空间中直接对比难度很高,我们非常容易将不同的沟回错误地对齐,算法落入在局部最优陷阱中。如图16所示,我们将大脑皮层曲面共形地映到球面上,然后在球面之间建立光滑映射,这种方法更加简单而精确。将大脑皮层映到球面等价于为大脑皮层曲面赋以曲率为+1的黎曼度量,我们可以用里奇曲率流的方法得到。


图17. 大脑海马体的几何分析。

如果说大脑皮层是数据库,那么海马体就是数据库的索引,如图17所示。如果海马体发生病变,长期记忆就无法形成,同时大脑中的长期记忆也无法被取出。很多神经疾病都能够引起海马体的变形,例如癫痫、吸毒、脑退化症等等。对海马体的几何形状进行定量比较分类是非常重要的。一种精确的方法是将海马体共形映到单位球面上,则面积的变化率给出了初始黎曼度量的全部信息,再加上平均曲率,那么海马体的所有几何信息被完美保留。换言之,我们将海马体曲面转换为球面上的两个函数(面积变化率,平均曲率)。在球面上比较不同的海马体曲面,从而精确衡量曲面之间的相似程度,进行分类诊断。相比于传统方法,这种基于几何的诊断方法更加定量而精确。

图18. 人脸曲面的精确匹配。

美容技术

在美容手术领域中,术后效果评估是重要的一个环节,这需要将术前和术后的人脸曲面进行精确的匹配。如图18所示,我们扫描了同一个人的带有不同表情的两张人脸曲面,然后在人脸曲面之间建立了精确的双射。平静表情的人脸上每一个小圆映到微笑表情的人脸上对应的小椭圆,由此我们可以测量对应点的几何变化。因此,三维人脸曲面间精确映射是美容领域中至关重要的技术。


图19. 三维人脸曲面被共形地映到二维平面上,所用方法就是里奇曲率流。

如图19所示,我们用里奇曲率流方法,将人脸曲面的黎曼度量变成曲率为0的平直度量,将三维人脸曲面平铺到二维平面上面,然后在二维平面区域之间建立光滑双射,从而诱导三维人脸曲面间的双射。当然,这种方法也可以用于三维人脸识别,但是人脸识别对于映射的精确度要求没有如此之高。

在精准医疗的其他领域,例如牙齿整形、人造心脏瓣膜、人造骨骼、放射治疗实时监控、肝脏手术计划等等,都需要对各种人体器官进行影像获取、几何重建、特征分析等,里奇流方法都会起到重要的作用。

7 总结和展望

庞加莱猜想本身纯粹而抽象:单连通的闭三维流形是三维球面,这一猜想本身似乎并没有任何实用价值。其结论的简单直观,往往给非数学专业人员无病呻吟之感。但是纯粹数学所追求的严密性迫使无数拓扑和几何学家们前仆后继,奉献终身,终于在众多数学家的共同努力下完成了证明。二维曲面的几何化定理——单值化定理从理论证明到算法提出,历经了百年;三维流形的瑟斯顿几何化纲领从理论证明到算法提出,几乎是同时。三维流形的拓扑理论和计算理论一开始就深刻地纠缠在一起。这表明,在现代,依随计算机技术的发展,纯粹理论到应用算法的开发周期越来越短。

同时,我们看到,在证明庞加莱猜想的过程中,瑟斯顿的几何化纲领将三维流形的风景一览无遗,哈密尔顿的里奇流给出从曲率来构造黎曼度量的强有力的工具,哈密尔顿和佩雷尔曼的奇点演化理论使得原来理论的禁区被彻底打破。笔者和许多数学家发展了离散里奇流的理论和算法,并且系统性地将曲率流应用到许多工程和医疗领域。在实践中,我们深深体会到,在许多关键的应用中,曲率流的方法无法被其它任何方法所取代。目前在社会实践中,里奇流在二维曲面上的应用已经开始逐步展开。但是里奇流在三维流形上的应用更为深邃奥妙,强悍有力,目前还没有任何实际应用。一方面因为三维流形远远超越日常生活经验,另一方面也是因为和曲面微分几何相比,三维流形的拓扑和几何知识远未普及。但是作为自然真理的忠实刻画,迟早三维流形的拓扑和几何会在社会实践中大行其道。庞加莱猜想所引发的雪崩效应终究会改写历史进程。

当庞加莱提出他的拓扑猜想,瑟斯顿洞察三维流形的基本几何结构,哈密尔顿悟出里奇曲率流,佩雷尔曼看出哈密尔顿的曲率流本质上是所谓熵能量的梯度流,他们所追求的是体悟几何结构的壮美,和自然真理的深邃。他们绝不会将实用价值作为其终极目的。实用技术的积累往往只能带来进化(Evolutio),好奇心的满足却能真正带来革命(Revolution)。愿更多的年轻人在万丈红尘中,在浮躁喧嚣中,能够保持诚挚纯真,保持强烈好奇,保持对自然界美丽的敏感,保持对科学真理的激情!

(如果读者对于离散曲面里奇流的理论、算法和应用有兴趣,可以进一步查阅专著【1】)

参考文献

[1] W. Zeng and X. Gu, Ricci Flow for Shape Analysis and Surface Registration Theories, Algorithms and Applications, Springer 2013

延伸阅读

  如果没有基础科学,我们将会失去什么?②  视频 | 拓扑为何?

③  纯粹数学走出象牙塔:丘成桐和三维科技有何关系?