计算几何常用算法,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.