ML特训营笔记2

线性代数

矩阵

1.矩阵的加法

设 $A = (a_{ij}),B = (b_{ij})$ 是两个 $m \times n$ 矩阵，则 $m \times n$ 矩阵 $C = c_{ij}) = a_{ij} + b_{ij}$ 称为矩阵A $与B的和，记为A + B = C$

2.矩阵的数乘

设 $A = (a_{ij})$ 是 $m \times n$ 矩阵， $k$ 是一个常数，则 $m \times n$ 矩阵 $(ka_{ij})$ 称为数 $k$ 与矩阵A的数乘，记为 ${kA}$ 。

3.矩阵的乘法

设 $A = (a_{ij})$ 是 $m \times n$ 矩阵， $B = (b_{ij})$ 是 $n \times s$ 矩阵，那么 $m \times s$ 矩阵 $C = (c_{ij})$ ，其中 $c_{ij} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj} = \sum_{k =1}^{n}{a_{ik}b_{kj}}$ 称为 ${AB}$ 的乘积，记为 $C = AB$ 。

4.向量的内积及正交性

两个向量的内积=两个向量的模相乘，再乘以 $cos \theta$ ，角度 $\theta$ 为两个向量的夹角。如果两个向量垂直，则内积为0

$<X,Y>=<Y,X>=X \cdot Y=Y \cdot X=X^T Y=Y^T X$
$<X,Y>= ||X|| ||Y||cos \theta$

其中： $\theta = argcos \frac {<X,Y>}{||X|| * ||Y||}$ 如果n阶方阵A满足， $A^TA=I=A^{-1}A$ 即A的转置等于A的逆，则A是正交矩阵。

5.矩阵乘法运算律

乘法结合律：A(BC)=(AB)C

左分配律：(A+B)C = AC+BC

右分配律：A(B+C)= AB+AC

注意：两个矩阵相乘，要保证：前一个的列数=后一个的行数

一般情况下： $AB \neq BA$ 6.特征值和特征向量的概念及性质

(1) 设 $\lambda$ 是 $A$ 的一个特征值，则 ${kA},{aA} + {bE},A^{2},A^{m},f(A),A^{T},A^{- 1},A^{*}$ 有一个特征值分别为 ${kλ},{aλ} + b,\lambda^{2},\lambda^{m},f(\lambda),\lambda,\lambda^{- 1},\frac{|A|}{\lambda},$ 且对应特征向量相同（A^{T}$ 例外）。

(2)若 $\lambda_{1},\lambda_{2},\cdots,\lambda_{n}$ 为 $A$ 的n个特征值，则 $\sum_{i= 1}^{n}\lambda_{i} = \sum_{i = 1}^{n}a_{{ii}},\prod_{i = 1}^{n}\lambda_{i}= |A|$ 从而 $|A| \neq 0 \Leftrightarrow A$ 没有特征值。

(3)设 $\lambda_{1},\lambda_{2},\cdots,\lambda_{s}$ 为 $A$ 的 $s$ 个特征值，对应特征向量为 $\alpha_{1},\alpha_{2},\cdots,\alpha_{s}$ ，

若: $\alpha = k_{1}\alpha_{1} + k_{2}\alpha_{2} + \cdots + k_{s}\alpha_{s}$

则: $A^{n}\alpha = k_{1}A^{n}\alpha_{1} + k_{2}A^{n}\alpha_{2} + \cdots +k_{s}A^{n}\alpha_{s} = k_{1}\lambda_{1}^{n}\alpha_{1} +k_{2}\lambda_{2}^{n}\alpha_{2} + \cdots k_{s}\lambda_{s}^{n}\alpha_{s}$
7.转置 $(A^T)^T=A$
$(AB)^T={B^T}{A^T}$
$(A+B)^T= A^T + B^T$

8.特殊矩阵

下三角矩阵：左下角都是非零元素
上三角矩阵：右上角都是非零元素
对角阵：对角线是非零元素
单位矩阵：对角线上都是1，其余是0

9.方阵的迹tr

方阵的迹为对角线元素之和

$trA=\sum^n_{i=1}a_{ii}$

性质：

$trA=trA^T$
$tr(A+B)=trA+trB$
$tr(\lambda A)=\lambda trA$
$trAB=trBA$

10.矩阵秩

矩阵的秩：该矩阵中线性无关的列向量的数目

(1) 秩r(A)=行秩=列秩；

(2) $r(A_{m \times n}) \leq \min(m,n);$

(3) $A \neq 0 \Rightarrow r(A) \geq 1$

(4) $r(A \pm B) \leq r(A) + r(B);$

(5) 初等变换不改变矩阵的秩

(6) $r(A) + r(B) - n \leq r(AB) \leq \min(r(A),r(B))$ 特别若 $AB = O$
则： $r(A) + r(B) \leq n$

(7) 若 $A^{- 1}$ 存在 $r(AB) = r(B)$ 若 $B^{- 1}$ 存在 $r(AB) = r(A)$

若 $r(A_{m \times n}) = n \Rightarrow r(AB) = r(B)$ 若 $r(A_{m \times s}) = n\Rightarrow r(AB) = r\left( A \right)$

(8) $r(A_{m \times s}) = n \Leftrightarrow Ax = 0$ 上面的式子只有零解

11.空间

空间是无穷多个向量构成的集合，满足性质：

每个向量线性无关
每个向量可以由其他的向量进行线性表示

12.向量的范数
$||x||*p=(\sum^n_{j=1}|x_j|^p)^{\frac{1}{p}}$

p=1，表示1范数
p=2，表示2范数
p为无穷，表示无穷范数

13.矩阵的范数

假设： $A=(a_{ij}) \in R^{i*j}$

F范数表示为 $||A||*F=(\sum^m_{i=1}\sum^n_{j=1}|a_{ij}|^2)^{\frac{1}{2}}$ 性质： $||cA||=c||A||$
$||A+B|| \leq ||A||+||B||$
$||AB|| \leq ||A||||B||$

最小二乘法

给定数据集合： $(x_1,y_1),(x_2,y_2),…,(x_n,y_n)$ 构建线性回归模型： $\hat y = kx+b$

$y_i$ 表示观测值
$\hat y$ 表示估计值

残差（residual）： $y_i - \hat {y_i} = y_i - (kx_i+b)$ 残差不是指距离，直接两个y值相减即可。

SSE (sum squares of error)： $SSE= \sum ^m_{i=1}(y_i-\hat y_i)^2$ 最小二乘法就是使得残差平方和最小的直线模型。可以求出k、b的值 $b=\hat y - k \hat x$

$k = \frac {\sum^m_{i=1}(y_i-\hat y)(x_i-\hat x)}{\sum^m_{i=1}(x_i-\hat x)^2}$

最小二乘法求解两个参数k,b

先对b求导

$\begin{align} \frac {\partial SSE}{\partial b} & = \sum^m_{i=1} 2 (y_i-k x_i-b)(-1)=0 \\ & = \sum^m_{i=1}{(y_i-k x_i-b)} = 0 \\ & = \sum^m_{i=1}y_i-k\sum^m_{i=1}x_i-\sum^m_{i=1}b=0 \\ & = \sum^m_{i=1}y_i-k\sum^m_{i=1}x_i-mb=0 \\ & b = \frac{1}{m}\sum^m_{i=1}y_i-k \frac{1}{m} \sum^m_{i=1}x_i \\ & b = \hat y-k \hat x \end{align}$

再对k求导

$\begin{align} \frac {\partial SSE}{\partial k} & = \sum^m_{i=1}2(y_i-k x_i-b)(-x_i) = 0 \\ & \sum^m_{i=1}(y_i-k x_i-b)(x_i) = 0 \\ & \sum^m_{i=1}(y_i-k x_i-\hat y+k \hat x)(x_i) = 0 \\ & \sum^m_{i=1}(x_i y_i-k x_i^2-x_i\hat y+k x_i\hat x) = 0 \\ & \sum^m_{i=1}(x_i y_i-x_i\hat y-k x_i^2+k x_i\hat x) = 0 \\ & \sum^m_{i=1}(x_i y_i-x_i \hat y)-k\sum^m_{i=1}(x_i^2-\hat x x_i)=0 \\ & k = \frac{\sum^m_{i=1}(x_i y_i-x_i \hat y)}{\sum^m_{i=1}(x_i^2-\hat x x_i)} \\ \end{align}$

k的另一种表示方法

在上面k的表达式子中

MLYTISpng

$\begin{align} \sum^m_{i=1}x_i \hat y & =\hat y \sum^m_{i=1} x_i \\ & = m \hat y \frac{1}{m}\sum^m_{i=1}x_i \\ & = m\hat y \hat x \\ & = \hat x \sum^m_{i=1}y_i \\ & = \sum^m_{i=1}\hat x y_i \\ & = \sum^m_{i=1} \hat x \hat y \end{align}$

总结上式子推导过程： $\sum^m_{i=1}x_i \hat y=\sum^m \hat x y_i = \sum^m_{i=1} \hat x \hat y$

k 的另一种表达式为： $\begin{align} k & = \frac{\sum^m_{i=1}(x_iy_i-x_i \hat y)}{\sum^m_{i=1}(x_i^2-\hat x x_i)} \\ & = \frac{\sum^m_{i=1}(x_iy_i-x_i \hat y-\hat x y_i+\hat x \hat y)}{\sum^m_{i=1}(x_i^2-\hat x x_i-\hat x x_i+\hat x ^2)} \\ & = \frac{\sum^m_{i=1}(x_i-\hat x)(y_i-\hat y)}{\sum^m_{i=1}(\hat x -x_i)^2} \end{align}$

最小二乘法和最大似然估计的关系

最小二乘法是残差满足正态分布情况下的最大似然估计

$\varepsilon_i=y_i - \hat y_i=y_i-(kx_i+b)$
$y_i=(kx_i+b)+\varepsilon_i=\hat y_i+\varepsilon_i$

参数服从正态分布 $\varepsilon_i-N(0,\delta^2)$
残差的概率密度函数为：
$\begin{align} f(\varepsilon_i|k,b) & = \frac{1}{\sqrt{2\pi}\delta}exp(-\frac{\varepsilon_i^2}{2\delta^2}) \\ & = \frac{1}{\sqrt{2\pi}\delta}exp(-\frac{(y_i- \hat y_i)^2}{2\delta^2}) \\ \end{align}$
似然函数表示为：
$L(k,b,\varepsilon_1,...,\varepsilon_m)=\Pi_{i=1}^m \frac{1}{\sqrt{2\pi}\delta}exp(-\frac{(y_i- \hat y_i)^2}{2\delta^2})$
对数似然函数为：
$\begin{align} I(k,b,\varepsilon_1,...,\varepsilon_m) & =InL(k,b,\varepsilon_1,...,\varepsilon_m) \\ & = \sum^m_{i=1}In{\frac{1}{\sqrt{2\pi}\delta}}-\frac{1}{2\delta^2}\sum^m_{i=1}(y_i-\hat y_i)^2 \end{align}$

最大似然函数为： $\max I(k,b,\varepsilon_1,...,\varepsilon_m)\Leftrightarrow \min \sum^m_{i=1}(y_i-\hat y_i)^2$

凸优化

优化问题简介

机器学习流程

建模
优化问题
1. 复杂优化问题（非凸的，不熟悉的）
2. 简单优化问题（低纬度优化，约束条件的简单优化，已知答案的优化）

优化问题的一般形式

求解最小值

$\min f_0(x)$

给定某个条件：

$f_i(x) \leq, i=1,2,...,m$

优化问题实例

image

凸集合和凸函数

凸集合：如果一个集合上的任何两个点之间的线段上的任何一点还在这个集合中，那么这个集合就是凸集合。

凸函数：如果一个函数 $f$ 的定义域是凸集合，而且对于任何两个点以及两点之间的线段上的任意一点都有 $f(\lambda x_1 + (1-\lambda)x_2) \leq \lambda f(x_1)+(1-\lambda)f(x_2),\lambda \in {0,1}$ 比如开口向上的二次函数

函数的上镜图：上镜图就是函数图像上方的部分区域

凸集合和凸函数的关系：一个函数是凸函数当且仅当函数的上镜图是凸集合。

凸组合

对于任何的n个点 $\{x_i\}^n_{i=1}$ 以及权重系数 $\{w_i\}^n_{i=1}$ ，权重系数小于0，且所有的权重系数之和为1，则S称之为凸组合： $S=\sum^n_{i=1}w_ix_i$
物理意义：n个重心为 $w_i$ 的点的整体重心

凸性质

凸集合形式：假设 $\Omega$ 是一个凸集合，那么它的任意自己都是凸包都仍然包含于 $\Omega$
凸函数性质：琴生不等式

如果 $f:\Omega \rightarrow R$ 是个凸函数，则对于任何 $\{x_i \in \Omega \}^n_{i=1}$ 以及凸组合 $\sum^n_{i=1}w_ix_i$ 都有:

$\sum^n_{i=1}w_if(x_i) \geq f(\sum^n_{i=1}w_ix_i)$
凸函数性质：

局部极值肯定是全局极值；非凸函数的局部最优解未必是全局最优解

凸优化问题

凸优化问题的一般形式:

目标最小化f(x)

$\min f_0(x)$

给定条件

$f_i(x) \leq b_i, i=1,2,3,...m$

对偶问题

拉格朗日常量
$L(x,\lambda,v)=f_0(x)+\sum^m_{i=1}\lambda_if_i(x)+\sum^p_{i=1}v_ih_i(x)$

拉格朗日对偶函数
$\begin{align} g(\lambda,v) & = inf_ {x \in D} L(x,\lambda,v)\\ & = inf_{x \in D}f_0(x) + \sum^n_{i=1}\lambda_if_i(x) + \sum^p_{i=1}v_ih_i(x) \\ \end{align}$

KKT条件

在某个约束条件g(x) \leq 0的情况下最小化f(x)，转化为如下的形式：
$\left\{ \begin {array} ff(x) \leq 0 \\ g(x) = 0 \\ \lambda \geq 0 \\ \lambda f(x) = 0 \\ \end{array} \right.$
上面的条件称之为KKT条件