0%

级数收敛最基础判定

充分必要条件

一个级数$an$收敛的充分必要条件是级数的前n项和数列$S_n=\sum{i=1}^{n}ai$收敛,而一般这个判定方法只对于那些能够求出前n项和数列通项公式的级数有很好的判定,然而大多数的级数都无法求出前n项和数列。所以对于一些常见的特殊数列有特别的判定方式

必要条件

级数收敛的必要条件是:

性质

1、如果一个级数收敛,则去掉有限项后的级数仍然收敛。

正项级数的判敛法

充分必要条件

正项级数收敛的充分必要条件是级数的前n项和数列$S_n$有界。

证明:

因为为正项级数,则前n项和$S_n$单调递增,

又因为$S_n$有界,则根据单调有界性原则,数列$S_n$收敛,证毕。

充分条件

比较判敛法

如果有正项级数$\sum u_n$和正项级数$\sum v_n$,如果存在N,当$n>N$时,有$u_n < v_n$,则有:

1、若$v_n$收敛,则$u_n$收敛

2、若$u_n$收敛、则$v_n$收敛

比较判敛法的极限形式

如果有正项级数$\sum un$和正项级数$\sum v_n$,且$\lim{n \to \infty} \frac{u_n}{v_n} = \rho$,则有:

1、若$\rho=0$,则说明存在N,当$n > N$时,有$u_n < v_n$,所以当$v_n$收敛,$u_n$收敛,$u_n$发散,$v_n$发散。

2、若$\rho = \infty$,则说明存在N,当$n > N$时,有$u_n > v_n$,所以当$v_n$发散,$u_n$发散,$u_n$收敛,$v_n$收敛。

3、若$0 < \rho < \infty$,则$u_n$与$v_n$有相同的敛散性。

比值判别法

对于正项级数$\sum an$,有$\lim{n \to \infty} \frac{a_{n+1}}{a_n} = \rho$,则有:

1、若$\rho < 1$,级数收敛

2、若$\rho = 1$,无法判定敛散性

3、若$p > 1$,级数发散

根值判敛法

对于正项级数$\sum a_n$,有$\sqrt[n]{a_n} = \rho$,则有:

1、若$\rho < 1$,级数收敛

2、若$\rho = 1$,无法判定敛散性

3、若$p > 1$,级数发散

交错级数

形如$1+(-\frac{1}{2})+\frac{1}{3}+(-\frac{1}{4})、\cdots = \sum(-1)^{n-1}\frac{1}{n}$的,正负号一直交替出现的级数称为交错级数。

充分条件

对于交错级数$\sum (-1)^n an$,如果$a_n$单调不增(注意这里是$a_n$,不是$(-1)^n a_n$,$a_n$符号是一致的,即要么$a_n$都为正,要没都为负),且$\lim{n \to \infty} a_n = 0$,则该交错级数收敛。

绝对收敛与条件收敛

绝对值级数

对于级数$\sum a_n$,每一项加上绝对值后的级数$\sum | a_n |$,称为绝对值级数。

绝对收敛

对于级数$\sum a_n$,如果其绝对值级数$\sum |a_n|$收敛,则称级数$a_n$绝对收敛。

如果一个级数绝对收敛,则原级数必定收敛

条件收敛

对于级数$\sum a_n$,如果$a_n$收敛,但是其绝对值级数$\sum |a_n|$不收敛,则称$a_n$条件收敛。

绝对收敛的级数满足级数的交换律,收敛的级数满足级数结合律

幂级数

形如$\sum a_n(x-x_0)^n$,其中$a_n、x_0$为常数的级数称为幂级数。

最常用的幂级数为: $\sum a_n x^n$。

阿贝尔定理

对于幂级数$\sum a_n x^n$,如果该级数在$x_0$处收敛,则对于任意$|x| < |x_0|$,级数绝对收敛;如果该级数在$x_0$处发散,则对于任意$|x| > |x_0|$,级数发散。

收敛半径

对于幂级数$\sum an x^n$,如果$\lim{n \to \infty} |\frac{a_{n+1}}{a_n}| = \rho$,则收敛半径

则,对于任意$|x| < |R|$,都有级数绝对收敛;对于任意$|x| > |R|$,都有级数发散。对于 $x=R$和$x=-R$,级数的敛散性需要带入后进一步判断。

如果要求幂级数$\sum a_n(x-x_0)^n$,的收敛半径也是一样的方法,他和级数$\sum a_n x^n$的收敛半径相同,只是相当于x的收敛区间的取值左右平移了而已。

幂级数的性质

1、对幂级数$\sum a_n(x-x_0)^n$逐项积分后或者逐项求导后,级数的收敛半径不变,收敛区间的端点值的敛散性可能发生变化

2、如果级数$\sum a_n(x-x_0)^n$在$x_1$处条件收敛,则该级数的收敛半径为$|x_1-x_o|$

一些特殊级数的敛散性

调和级数

//TODO: finish this part

什么是梯度

梯度本质上来说就是一个向量,这个向量的各个分量是多元函数在某点的各个一阶偏导数。既然是一个向量,那么就可以表示方向。进而由方向导数的定义可以知道,沿梯度方向,函数值增大的速度就越快,相反沿梯度的反方向,函数值减小的速度就越大

为什么要使用梯度下降法

对于一些优化问题时,我们一般需要求解问题的局部最优解,而表现在函数上,局部最优解就是函数的极值点。根据费马定理,如果一个函数一阶可偏导,那么极值点处的一阶偏导数都为0。而一般绝大多数的函数都是一阶可偏导的。

但是直接求出函数的偏导数,然后令偏导数等于0求解方程的这种方法一般很难求出方程的解。所以只有通过数值计算的方法来求解近似解。

梯度下降法的一般形式

首先确定一个初始点$W0$,然后使用迭代公式: $w{n+1}^i = wn^i - \alpha f’{w^i}(W_n)$,$w^i$表示点$W$的第$i$个分量,$\alpha$为学习率,一般为一个接近0的常数,例如0.001。

迭代,直到达到一定的迭代步数或者是目标函数的变化或参数的变化小于某一阈值时停止迭代。

实现细节问题

初始值的设定

一般的,对于不带约束条件的优化问题,可以将初始值设置为0,或者设置为随机数。初始值的设定对算法的收敛很重要,不同的初始值最后可能收敛到不同的极值点。

学习率的设定

一般可以令学习率为一个很小的正数例如0.001,并且在接下来的迭代过程中不再改变学习率。或者可以在迭代的过程中动态的调整学习率的值,例如前10000步迭代时学习率为0.001,然后10000步学习率减半。如果梯地下降算法运行异常的话,可能也是学习率设置得不太合理。

特征缩放

有时候,一个特征的可能取值范围可能很大,这对于梯度下降法来说就可能需要很多次迭代才能最后收敛。所以为了减少迭代次数,可以使用特征缩放的方法。

例如有特征$x_1$,其取值范围为$(0, 2000)$,特征$x_2$,其取值$(0, 100)$,那么就可以对这两个特征进行缩放为$\frac{x_1}{2000}$和$\frac{x_2}{100}$。

一般的,特征缩放后的读取范围一般为$[-1,1]$之间。为此,可以使用均值归一化方法,如果一个特征$x$的均值为$\mu$,其取值区间长度为$n$,则归一化方法缩放方式为$\frac{x-\mu}{n}$。

判断梯度下降法是否收敛

一种方法是设置收敛阈值,即当目标函数的变化值小于某个阈值时表明梯度下降收敛。

令一种方法是画出目标函数值随着迭代步数变化的图形,例如每迭代100次就画出当时的目标函数的函数值。最后根据图像来判断是否收敛。

第一种方法有可能不好设置阈值,两种方法可以配合着使用。

梯度下降法的问题

在大多数非凸优化问题中,极值点不一定就是局部最优解的点,而且,即使某个极值点是局部最优解的点但是局部最优解不一定就是全局最优解。

随机梯度下降

对于某些机器学习问题,我们的目标函数是关于样本的损失函数,例如对于线性规划问题,假设训练集中有N个样本,并且N很大,在进行训练时我们使用均方误差来作为损失函数。即$L(W) = \frac{1}{N} \sum_{k=1}^{N} (Y-WX)^2$,$Y,X$都是N维向量,$W$是我们的自变量。则一次迭代下来,要计算全部样本的话计算量就太大了。

作为改进,可以在一次迭代时,随机选择部分样本来进行近似损失函数,即$L(W) = \frac{1}{M} \sum_{k=1}^{M} (Y-WX)^2, M \ll N$。这就是随机梯度下降法。已经证明,随机梯度下降法产生的梯度的期望值等于全部样本最为产生的梯度。

仿射集

在n维空间中,对于点的集合C,如果集合中的任意两点x,y,对于任意$\theta$,都有$\theta x + (1-\theta)y \in C$,则集合C是一个仿射集合。即在集合中任意两点连线的直线上的点都在集合中。

凸集

定义

在n维空间中,对于点的集合C,如果集合中的任意两点x,y,对于任意$0\leq\theta\leq1$,都有$\theta x + (1-\theta)y \in C$,则集合C为一个凸集。即在集合中任意两点,其连线线段上的点也都在集合中。

凸集和防射集的定义就是$\theta$的取值范围不同。

常见的凸集

n维实向量空间$R^n$

如果有$x,y \in R^n$,则显然有对于任意$0\leq\theta\leq1$,都有$\theta x + (1-\theta)y \in R^n$。

由此可见,如果一个优化问题是不带约束的优化,则其变量可行域是一个凸集

仿射子空间${x \in R^n:Ax=b} $

其中A为$m \times n$的矩阵,b为m维列向量。即非齐次线性方程组的解空间。

证明:

如果有$x,y \in R^n$且$Ax=b,Ay=b$,

则对于任意的$0\leq\theta\leq1$,

都有$A(\theta x+(1-\theta)y) = \theta Ax+(1-\theta)Ay=\theta b + (1-\theta)b=b$。

由此可见,如果变量的约束是线性等式约束,则该线性等式确定的可行域是一个凸集

子空间${x \in R^n:Ax\leq b}$

其中A为$m \times n$的矩阵,b为m维列向量。

证明:

如果有$x,y \in R^n$且$Ax\leq b,Ay\leq b$,

则对于任意的$0\leq\theta\leq1$,

都有$A(\theta x+(1-\theta)y) = \theta Ax+(1-\theta)Ay\leq\theta b + (1-\theta)b=b$

由此可见,如果变量的约束是线性不等式约束,则该线性不等式确定的可行域是一个凸集

凸集的性质

1、多个凸集的交集仍然是凸集

证明:

假设$C1,C_2,…,C_k$为凸集,他们的交集为$C=\bigcap{i=1}^{k}Ci$,并有$0 \leq \theta \leq 1$,

因为$C_1,C_2,…,C_k$为凸集,所以对于$x,y \in C$,有$\theta x + (1-\theta)y \in C_i, \forall i=1,…,k$

即$\theta x + (1-\theta)y \in C$

2、多个凸集的并集不一定是凸集

凸函数

定义

在函数定义域内,如果对于任意的x和y,以及实数$0 \leq \theta \leq 1$,都满足$f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$,则函数为凸函数。可见,凸函数的定义和函数曲线的凹凸性的定义是相反的。

从几何意义上讲,在凸函数上的任意两点的连线线段上的点都在函数的上方。

如果把定义中的$\leq$改为$<$,则称函数是严格凸函数

对于一元函数,凸函数的二阶判定式为$f’’(x) \geq 0$,严格凸函数的二阶判定式为$f’’(x) > 0$。由此也可见凸函数的定义和函数曲线的凹凸性的定义是相反的。

对于多元函数,如果它是凸函数,则其Hessian矩阵为半正定矩阵。如果是严格凸函数,则其Hessian矩阵为正定矩阵。

凸函数的性质

1、凸函数的非负线性组合仍然是凸函数。

Hessian矩阵

Hessian矩阵是有多元函数的二阶偏导数组成的矩阵。如果一个函数二阶可导,其Hessian矩阵定义为:

如果多元函数的混合二阶偏导数连续,则其混合二阶偏导数结果与求导次序无关。大多数多元函数的混合二阶偏导数是连续的,所以Hessian矩阵大多是对称矩阵。

根据多元函数的极值判别法,假设多元函数在点M的梯度为0,则M是函数的驻点,如果:

1、Hessian矩阵正定,函数在该点有极小值

2、Hessian矩阵负定,函数在该点有极大值

3、Hessian矩阵既不正定也不负定,则不能确定是否取得极值

正则表达式是由普通字符以及特殊字符(称为"元字符")组成的文本模式

正则表达式是一个匹配连续串的规则,即匹配会在每个连续的字符串中进行

普通字符

普通字符包括没有显示指定为元字符的所有可打印和不可打印字符。这包括所有的大写和小写字母、所有数字、所有标点符号和一些其他符号

非打印字符

字符 描述
\cx 匹配由x指明的控制字符。例如,\cM匹配一个control-M或回车符。x的值必须为A-Z或a-z之一。否则,将c视为一个原意的'c'字符
\t 匹配一个制表符。等价于\x09和\cl
\n 匹配一个换行符。等价于\x0a和\cJ
\v 匹配一个垂直制表符。等价于\x0b和\cK
\f 匹配一个换页符。等价于\x0c和\cL
\r 匹配一个回车符。等价于\x0d和\cM
\s 匹配任何空白字符,包括空格、制表符、换页符等等。等价于[\f\n\r\t\v]。注意unicode正则表达式会匹配全角空格符
\S 匹配任何非空白字符。等价于\f\n\r\t\v
\d 匹配数字
\w 匹配word(数字、字母)
\W 匹配非word(数字、字母)

特殊字符(元字符)

所谓特殊字符,就是有一些特殊含义的字符,例如”?”,如果要匹配特殊字符,就需要对特殊字符进行转义,例如"\?"

字符 描述
$ 匹配输入字符串的结尾位置。如果设置了RegExp对象的Multiline属性,则$也匹配’\n’或’\r’
() 标记一个子表达式的开始和结束位置,子表达式可以提供以后使用
* 匹配前面的子表达式零次或多次
+ 匹配前面的子表达式一次或多次
. 匹配除换行符\n之外的任何单字符
[ 标记一个中括号表达式的开始
? 匹配前面的子表达式零次或一次,或指明一个非贪婪限定符)
\ 将下一个字符标记为特殊字符或原意字符,或想活引用,或八进制转义符
^ 匹配输入字符串的开始位置,除非在方括号表达式中使用。当该符号在方括号表达式中使用时,表示不接受方括号表达式中的字符集合
{ 标记限定符表达式的开始
指明两项之间的一个选择

举几个🌰:

  • “?” : 例如colou?r可以匹配color和colour

  • “*“ : 例如runoo*b可以匹配runob、runoob、runooooob等

  • “+” : 例如runoo+b可以匹配runoob、runooooob等

  • (abc|bcd|cde):abc、bcd、cde三者之一均可

限定符

限定符是用来制定正则表达式的一个给定组件必须出现多少次才能满足匹配

字符 描述
* 匹配前面的子表达式零次或多次
+ 匹配前面的子表达式一次或多次
? 匹配前面的子表达式零次或一次
{n} n是一个非负整数,匹配确定的n次
{n,} n是一个非负整数,至少匹配n次
{n,m} m和n均为非负整数,其中n<=m,最少匹配n次且最多匹配m次,注意在逗号和两个数之间不能有空格

贪婪限定符和非贪婪限定符

贪婪模式:*、+ 和 ? 限定符都被称为“贪心的”,因为它们匹配尽可能多的文本。
非贪婪模式:通过在 *、+ 或 ? 限定符之后放置 ?,该表达式从“贪心”表达式转换为“非贪心”表达式或者最小匹配即找到第一个满足匹配的就停止

定位符

定位符能够将正则表达式固定到行首或行尾

符号 描述
^ 匹配输入字符串开始的位置。如果设置了RegExp对象的Multiline属性,^还会和\n或\r之后的位置匹配
$ 匹配输入字符串的结尾位置,如果设置了RegExp对象的Multiline属性,$会与\n或\r之前的位置匹配
\b 匹配一个单词边界,即字与空格间的位置
\B 单词边界匹配

不能讲限定符与定位符一起使用,由于在紧靠换行或者单词边界的前面或者后面不能有一个以上位置,因此不允许诸如^*之类的表达式

如果要匹配一行文本开始处的文本,要在正则表达式的开始使用^字符。如果要匹配一行文本结束处的文本,要在正则表达式的结束处使用$字符。
^和$可以在一个正则表达式中同时使用,例如:

1
^Chapter$

表示从文本开始匹配时和从末尾匹配时都是Chapter,说明该行只有Chapter这几个字符

单词边界是单词和空格之间的位置,非单词边界是任何其他位置。

\b字符位于要匹配的字符串的开始,它在单词的开始处查找匹配项,如果它位于字符串的结尾,他在单词的结尾处查找匹配项。

1
2
\bCha
ter\b

选择

AAA | BBB
匹配 AAA 或者 BBB

引用

引用分组和反向引用

对一个正则表达式或部分模式两边添加圆括号将导致相关匹配到一个临时缓冲区中,所捕获的每个子匹配都按照正则表达式模式中从左到右出现的顺序存储。缓冲区的编号从1开始,最多可以存储99个捕获的子表达式。每个缓冲区都可以使用\n访问,其中n为一个标识特定缓冲区的一位或两位十进制数。
例如:

1
\b([a-z]+)\1\b

反向引用只能用于之前出现的分组。

反向引用的一个例子:要用正则表达式匹配日期,日期的格式为yyyy-mm-dd、yyyy/mm/dd和yyyy.mm.dd都是合理的,注意后面的分隔符和前面的分隔符要相等。则正则表达式可以写作:

1
\d{4}(-|/|.)\d{2}\1\d{2}

引用分组中对于括号嵌套的解释

1
((\d)(\d(\d)))\1\2\3\4

假如利用上述表达式去匹配如下字符串:“123”
则\1指代的是123
\2指代的是1
\3指代的是23
\4指代的是3

以左括号出现的顺序为作为编号的顺序

注意对于\10的解释是编号为10的分组,而不是编号为1的分组然后再跟一个0

引用不存在的分组

因为反向引用是引用前面的分组,但我们在正则表达式里引用了不存在的分组时,此时正则不会报错,只是匹配反向引用的字符本身。例如\2,就匹配”\2”,注意”\2”表示对2进行了转意。

非捕获分组

如果只是想要括号最原始的功能,而不想保存捕获的分组,后续不会进行引用,可以使用非捕获分组(?:)
例如:

1
(?:ab)+     //用于匹配ababab...

基本术语

  • 学习(训练) —— 从数据中学得模型的过程
  • 分类 —— 使用学习的模型预测的结果为离散值,此类学习任务称为“分类(classification)”
  • 回归 —— 使用学习的模型预测的结果为连续值,此类学习任务称为“回归(regression)”
  • 根据训练数据是否拥有标记信息,学习任务可大致划分为两大类:“监督学习(supervised learning)”和“无监督学习(unsupervised learning)”,分类和回归是前者的代表,而聚类是后者的代表
  • 学得模型适用于新样本的能力,称为“泛化(generalization)”能力

将离散值转换为连续值

对于离散属性,如果某个属性的取值之间存在“序”的关系,可通过连续化将其转化为连续值,例如对于身高这个属性,它的取值可以为“高”和“矮”,那么可以转化为${1.0, 0.0}$;若取值是“高”,“中”,“低”,则可转化为${1.0,0.5,0.0}$。

若某个属性的取值之间不存在序关系,假定有这个属性有k个取值,则通常转化为k维向量,例如属性“瓜类”的取值“西瓜”,“南瓜”,“黄瓜”可转换为(1,0,0),(0,1,0),(1,0,0)

假设空间

  • 归纳(induction)和演绎(deducation)是科学推理的两大基本手段,前者是从特殊到一般的“泛化”过程,即从具体的事实归结出一般性规律;后者则是从一般到“特殊”的特化过程,即从基本原理推演出具体状况。

  • 模型属于由输入空间到输出空间的映射的集合,这个集合就是假设空间(hypothesis space)

  • 与训练集一致的“假设集合”称之为“版本空间(version space)”

归纳偏好

  • 归纳偏好可看作学习算法自身在一个可能很庞大的假设空间中对假设进行选择的启发式或“价值观”

  • NFL(没有免费的午餐)定理 —— 脱离具体问题,空泛的谈论“什么学习算法更好”毫无意义。

定义:

若有函数y=f(X),其中X为一个矩阵,y为标量,则标量y对矩阵X的导数定义为y对X逐元素求导排列成与X同型的矩阵

但是在实际计算标量对矩阵求导时,并不是直接使用标量对矩阵中的逐元素求导,而是将矩阵当作一个整体来求导

标量对矩阵求导公式推导

若有y=f(X),其中X为$m{\times}n$的矩阵,则由全微分公式可以得到

令:

其中tr表示矩阵的迹(trace),是方阵对角元素之和。所以只要求全微分的公式(1)左边的形式,就可以的得到$\frac{\partial{f}}{\partial{X}}$$

矩阵微分的运算法则

1、加减法、乘法、转置、迹

2、逆

该公式可以使用公式$XX^{-1} = I$,两边同时对X求微分。

3、行列式

其中$X^*$为X的伴随矩阵

4、逐函数乘法

其中$\bigodot$表示同型矩阵逐元素相乘

5、逐元素函数

其中$\sigma(X)=[\sigma(X_{ij})]$是逐元素标量函数的计算

关于矩阵的迹的公式

一个例子

y=ATXB,求$\frac{\partial y}{\partial X}$

解:

应为df为标量,所以

所以$\frac{\partial y}{\partial X}=(AB^T)$

链式法则

在标量对矩阵求导中,没有类似标量对标量求导的链式法则。

此时没有明确的链式法而是要使用公式进行推导,例如有$z = f(Y)$,其中Y为矩阵且$Y=AXB$,A、X、B、都为矩阵,求$\frac{\partial f}{\partial X}$。

推导过程:

所以有$\frac{\partial z}{\partial X}=(A^T\frac{\partial f}{\partial Y}B^T)$