机器学习导论-1 绪论与数学参考

二刷机器学习导论

参考书: 统计机器学习 PRML(贝叶斯) ESL(统计学派) MLAPP UML

绪论

  1. 学习过程

    1. 训练数据,经过
    2. 学习算法训练,得到
    3. 模型(决策树,射精网络,支持向量机,Boosting,贝叶斯网……),可以判断
    4. 新数据样本,得到结论
  2. 机器学习的局限性,失效条件:

    1. 特征信息不充分
    2. 样本信息不充分
  3. 机器学习的理论基础(计算学习理论),概率近似正确(PAC):

    $P(|f(x)-y|\le \epsilon)\ge 1-\delta$

    f(x)是预测值,y是真实值,目的是尽可能贴近真实值也就是$|f(x)-y|\le \epsilon$,然后这件事情有一个概率的保证,一定大于$1-\delta$的概率确保这件事情的完成。一句话总结就是很高的概率得到很好的结果的模型。

    如果你能确定百分百正确,就不用整机器学习了

数学参考

范数

  • 在实数域中,数的大小和两个数之间的距离是通过绝对值来度量的。将数推广到向量就引入了范数。范数(Norm)是一个函数,其赋予某个向量空间(或矩阵)中的每个向量以长度或大小。对于零向量,另其长度为零。直观的说,向量或矩阵的范数越大,则我们可以说这个向量或矩阵也就越大。

    在算例子的时候我觉得其实是不同维度到0点的距离

向量的范数
  • 范数标准定义:

    • 正定性:$||x||\ge 0$,且$||x||= 0$当且仅当$x=0$;
    • 齐次性:对任意实数 $\alpha$ ,都有$||\alpha x||=|\alpha|\ ||x||$
    • 三角不等式: 对任意$x,y\in R^n$,都有$||x+y|| \le ||x|| + ||y||$

    则称$||x||$为$R^n$上的向量范数

  • 范数表达式:

  • L1范数:

    向量元素绝对值之和

    L2范数:

    Euclid范数(欧几里得范数,常用计算向量长度)

    Lp范数:

    image-20210308113014539

    Lp的形状随p的变化的图

    L$\infty $范数:

所有向量元素绝对值中的最大值

L$-\infty$范数:

所有向量元素绝对值中的最小值

L0范数:

也就是非零元素的数量

  • 例子:$x=(1,4,3,0)^T$的常用范数:

    $||x||_0=3$

    $||x||_1=|1|+|4|+|3|+|0|=8$

    $||x||_2=\sqrt{|1|^2+|4|^2+|3|^2+|0|^2}=\sqrt{26}$

    $||x||_{\infty}=|4|=4$

矩阵的范数
  • 推广到矩阵,矩阵相容范数的定义:

    • 正定性:$||A||\ge 0$,且$||A||= 0$当且仅当$A=0$;
    • 齐次性:对任意实数 $\alpha$ ,都有$||\alpha A||=|\alpha|\ ||A||$
    • 三角不等式: 对任意$A,B\in R^{n\times n}$,都有$||A+B|| \le ||A|| + ||B||$
    • 相容性:对任意$A,B\in R^{n\times n}$,都有$||AB|| \le ||A||\ ||B||$

    则称$||A||$为$R^{n\times n}$上的一个矩阵范数

  • 列范数:

    $A$的每一列的绝对值的最大值,称作$A$的列范数

  • 行范数:

    $A$的每一行的绝对值的最大值,称作$A$的行范数

  • L2范数:

    其中$\lambda_{max}$表示$A^TA$的特征值的绝对值的最大值

  • F-范数(Frobenius):

    它相当于矩阵$A$各项元素的绝对值平方的总和,也就是矩阵张成向量之后的L2范数

求导

  • 一阶导数:雅可比矩阵

    假设函数$F:{R_n} \to {R_m}$是一个从欧式n维空间转换到欧式m维空间的函数.这个函数由m个实函数组成:$y1(x1,…,xn), …, ym(x1,…,xn)$. 这些函数的偏导数(如果存在)可以组成一个m行n列的矩阵, 这就是所谓的雅可比矩阵:

此矩阵表示为: ${J_F}({x_1}, \ldots ,{x_n})$,或者$\frac{ {\partial {({y_1}, … ,{y_m})} } } { {\partial {({x_1}, … ,{x_n})} } }$.

hexo 两个{之间要加空格不然会报错: expected variable end

如果$p$是$R_n$中的一点,$F$在$p$点可微分,那么这一点的导数由$J_F(p)$给出.在此情况下, 由$F(p)$描述的线性算子即接近点$p$的$F$的最优线性逼近, $x$逼近于$p$:

  • 二阶导数:海森矩阵

    海森矩阵(Hessian matrix或Hessian)是一个自变量为向量的实值函数的二阶偏导数组成的方块矩阵, 此函数如下:

    如果$f$所有的二阶导都存在,那么有:

    也就是:

  • 链式法则的式子里面有转置的原因可以从维度的角度来思考;

奇异值

  • 共轭:$z=a+bi$,z的共轭$\bar{z}=a-bi$;实数的共轭是他自身;

  • 矩阵概念:

    • 对称矩阵:

      $A^T=A$

    • Hermite矩阵,将实数范围讨论的对称矩阵延伸到复数范围:

      其中,用$\bar{A}$表示以$A$的元素的共轭复数为元素构成的矩阵,那么$A^H=(\bar{A}^T)$,这个称作$A$的复共轭转置矩阵;

      • 特征值都是实数。
      • 任意两个不同特征值所对应的特征向量正交。
    • 正交矩阵:

      $A^TA=E$

    • 酉矩阵:

      $A^HA=E$

      这玩意其实就是正交矩阵在复数范围的推广

    • 奇异矩阵:

      $|A|=0$称作奇异矩阵,否则称作非奇异矩阵;$A$是可逆矩阵的充要条件是$|A|\neq0$,因此可逆矩阵就是非奇异矩阵

    • 正规矩阵:

      $A^HA=AA^H$,如果都是实数矩阵,那么$A^T=A^H,A^TA=AA^T$

    • 幂等矩阵:

      $A^2=A$

    • 正定矩阵:它是对称矩阵/Hermite矩阵的进一步延伸

      设$A$为n阶Hermite矩阵,如果对任意n维复向量$x$都有$x^HAx\ge 0$,则称A是半正定矩阵;如果对任意n维复向量$x$都有$x^HAx> 0$,则称A是正定矩阵。

      • Hermite矩阵$A$为正定(半正定)矩阵 $\leftrightarrow$$A$的所有特征值是正数(非负数)。
      • Hermite矩阵$A$为正定矩阵 $\leftrightarrow$存在n阶非奇异矩阵$P$,使得$A=P^HP$
      • Hermite矩阵$A$为半正定矩阵$\leftrightarrow $存在n阶矩阵$P$,使得$A=P^HP$
  • 特征值与特征分解:

    特征值特征向量定义:$\lambda$是特征值,$x$是特征向量,A是方阵

    求解走:

    $Ax=\lambda x\rightarrow Ax=\lambda E x\rightarrow (\lambda E-A)x=0\rightarrow|\lambda E-A|=0$解出特征值带入得到特征向量

    特征分解:对于mxm的满秩对称矩阵A

    其中,Q是这个矩阵A的特征向量组成的矩阵,Σ是一个对角矩阵,每一个对角线元素就是一个特征值,里面的特征值是由大到小排列的,这些特征值所对应的特征向量就是描述这个矩阵变化方向(从主要的变化到次要的变化排列)。也就是说矩阵A的信息可以由其特征值和特征向量表示。

    特征值分解也有很多的局限,比如说变换的矩阵必须是方阵。

奇异值与奇异值分解
  1. 运用到的理论:

    1. 对于n阶方阵,$Ax=\lambda x$;
    2. 如果$\vec{a}$与$\vec{b}$正交,那么有$\vec{a} \cdot \vec{b} = 0$
    3. 一个内积空间的正交基(orthogonal basis)是元素两两正交的基,基中的元素称为基向量。如果一个正交基的基向量的模长都是单位长度1,则称这正交基为标准正交基或”规范正交基”(Orthonormal basis);
    4. A与A的转置矩阵是有相同的特征值,但是他们各自的特征向量没有关系;
  2. SVD推导之矩阵分解:

    对于矩阵$A$,有$A^TA = \lambda_{i} v_{i}$(因为$A^TA$肯定是方阵);$\lambda_i$是特征值,$v_i$是特征向量;假设$(v_{i}, v_{j})$是一组正交基,那么有$v_{i}^{T} \cdot v_{j} = 0$,那么:

    可以得到$Av_{i}, Av_{j}$;根据公式$(1)$可以推导得到$(Av_{i}, Av_{i}) = \lambda_{i} v_{i}^{T} v_{i}=\lambda_{i}$;又因为行列式的性质$|AB|=|A||B|\rightarrow|(Av_{i})^{T} \cdot Av_{i}|=|Av_{i}^{T} ||Av_{i}|=|Av_{i}|^2$,所以有:

    根据公式(2),有$\frac{Av_{i} }{|Av_{i}|} = \frac{1}{\sqrt{\lambda_{i} } } Av_{i}$,令$\frac{1}{\sqrt{\lambda_{i} } } Av_{i}= u_{i}$,可以得到:

    其中$\delta_{i} = \sqrt{\lambda_{i} }$(这个称作奇异值),进一步推导成矩阵形式:

    从而得到:

  3. SVD推导之矩阵计算:

    已知$A$怎么算$U$和$V$呢?

    首先计算$A$的转置$A^T$,而$A^T$相当于:

    然后计算$A^TA$:

    通过公式(7),会发现这不就是特征值分解嘛!!!可以得到$A^TA v_{i} = \lambda_{i}v_{i}$,只需要求出$A^TA$的特征向量就可以得到$V$了

    同理计算$AA^T:$

    通过公式(8),可以得到$AA^T u_{i} = \lambda_{i}u_{i}$,只需要求出$AA^T$的特征向量就可以得到$U$了

    $\Sigma$是上面公式(7)或者公式(8)中求到的非零特征值从大到小排列后开根号的值

  4. SVD计算例子:

    假设有一个矩阵$A$:

    要计算:

    中的$U,V,\Sigma$

    1. 计算$U$

      $AA^T=\begin{bmatrix} 2&2&0\\2&2&0\\0&0&0\end{bmatrix}$,进行特征分解,得到特征值[4,0,0]以及对应的特征向量$[\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0]^T,[-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0]^T,[0,0,1]^T$,可以得到:

  5. 计算$V$

    $A^TA=\begin{bmatrix} 2&2 \\ 2&2 \end{bmatrix}$,进行特征分解,得到特征值[4,0]以及对应的特征向量$[\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}]^T,[-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}]^T$,可以得到:

  6. 计算$\Sigma$

    因为特征值是[4,0],因此:

    所以$A$的SVD分解是:

  7. 代码求解方法:

    1
    2
    3
    import numpy as np
    A=np.array([1,1],[1,1],[0,0])
    print(np.linalg.svd(A))

以下主要是优化的部分

拉格朗日乘子法

To be done

参考博客