机器学习笔记

该总结来自于去年一门线上付费课程,由于今年终于在实际工作中用到了,所以整理了下该门课程中通用的思路和公式。另外该课程中有的主讲人还是比较靠谱的。


目录

  • 矩阵等理论
  • 类聚
  • 推荐系统
  • 决策数和随机森林
  • Adaboost、GBDT、GBRT以及组合算法
  • SVM
  • 神经网络
  • 贝叶斯
  • 主题模型
  • 卷积神经网络

矩阵等理论


矩阵


有矩阵 $A \in R^{m \times n}$,则定义:

  • 列空间:$C(A) = \{y|y = Ax\}$
  • 行空间:$C(A^{T}) = \{y|y = A^{T}x\}$
  • 零空间:$N(A) = \{x \neq 0|Ax = 0\}$
  • 左零空间:$N(A^{T}) = \{x \neq 0|A^{T}x = 0\}$

易知 $C(A^{T}) \perp N(A)$ 和 $C(A) \perp N(A^{T})$。

且有 $rank(C(A^{T})) + rank(N(A)) = n$ 和 $rank(C(A)) + rank(N(A^{T})) = m$。


特征值


  • 对称矩阵($A^{T} = A$)的特征值是实数,反对称矩阵($A^{T} = -A$)的特征值是纯虚数。大多数矩阵的特征值是复数。

  • 若有对称矩阵 $A \in R^{n \times n}$ 且 $rank r \leq n$,则有:$\underbrace{|\lambda_{1}| \geq ... \geq |\lambda_{r}|}_{r} > \underbrace{\lambda_{r+1} = ... = \lambda_{n}}_{n - r} = 0$

  • Rayleigh商:$max_{x \neq 0} \frac{x^{T}Ax}{x^{T}x} = max_{x^{T}x = 1} \frac{x^{T}Ax}{x^{T}x} \lambda_{max}$


谱分解


若有对称矩阵 $A \in R^{n \times n}$ 且其特征值均不相同,则所有特征向量正交($UU^{T} = U^{T}U = I$),即: $ A = U \Lambda U^{T}
= [u_{1},...,u_{n}]\begin{bmatrix}\lambda_{1} \\& ... \\& &\lambda_{n}\end{bmatrix}\begin{bmatrix}u^{T}_{1} \\...\\u^{T}_{n}\end{bmatrix} = \sum \lambda_{i}u_{i}u^{T}_{i} $


PCA


给定矩阵 $X = {x_{1}, ..., x_{n}} \in R^{m \times n}$,选择 $k < m$ 个正交基进行降维。降维后,确保行向量间的协方差为0,而每个行向量的方差尽可能大(即使得行与行之间尽可能没关系,而各行的能量尽量大)。

假设 $X$ 各行向量已减去均值,则其协方差矩阵(对称半正定)为:$C_{X} = \frac{1}{n}XX^{T} = \frac{1}{n}\begin{bmatrix}x_{1}x^{T}_{1}&...&x_{1}x^{T}_{n}\\...&...&...\\x_{n}x^{T}_{1}&...&x_{n}x^{T}_{n}\end{bmatrix}$

所以,即使得 $x_{i}x^{T}_{j}, i \neq j$ 的值尽量为0,且保留尽量大的 $x_{i}x^{T}_{i}$

对协方差进行分解可得:$C_{X} = U\Lambda U^{T} \Rightarrow \Lambda = U^{T} C_{X} U$

将矩阵 $X$ 变换为方阵 $Y = U^{T}X, Y \in R^{n \times n}$,则 $Y$ 的协方差为:$C_{Y} = \frac{1}{n}YY^{T} = U^{T}C_{X}U = \Lambda$

故降维后的矩阵即保留 $\Lambda$ 中较大的特征值所对应的 $U^{T}$ 中的特征向量后与 $X$ 相乘所得的矩阵。


SVD


秩为 $r$ 的矩阵 $A \in R^{m \times n}$ 可被分解为:

$ A = \underbrace{\begin{bmatrix}U_{1}&U_{2}\end{bmatrix}}_{m \times m}
\underbrace{ \begin{bmatrix} \sum_{1}&0_{r \times (n - r)}\\ 0_{(m - r) \times r}&0_{(m - r) \times (n - r)}
\end{bmatrix} }_{m \times n} \underbrace{\begin{bmatrix}V^{T}_{1}\\V^{T}_{2}\end{bmatrix}}_{n \times n} = U\sum V^{T} = U_{1}\sum_{1}V^{T}_{1} = \sum^{r}_{i = 1}\sigma_{i}u_{i}v^{T}_{i} $

其中,$\sum_{1} = diag(\sigma_{1},...,\sigma_{r}), \sigma_{i} > 0$

又 $ AA^{T} = U\sum\sum^{T}U^{T} =
U
\begin{bmatrix} \sum^{2}_{1}&0\\ 0&0
\end{bmatrix} U^{T}
$

即 $U$ 是 $AA^{T}$ 的特征向量,$\sigma_{1},...,\sigma_{r},0,...,0$ 为特征值,有:

$\sigma_{k} = \sqrt{\lambda_{k}(AA^{T})} = \sqrt{\lambda_{k}(A^{T}A)}$


由 $ AX = \begin{bmatrix}U_{1}&U_{2}\end{bmatrix}
\begin{bmatrix} \sum_{1}&0_{r \times (n - r)}\\ 0_{(m - r) \times r}&0_{(m - r) \times (n - r)}
\end{bmatrix} \begin{bmatrix}V^{T}_{1}\\V^{T}_{2}\end{bmatrix} x
= \begin{bmatrix}U_{1}&U_{2}\end{bmatrix} \begin{bmatrix} \sum_{1}&0_{r \times (n - r)}\\ 0_{(m - r) \times r}&0_{(m - r) \times (n - r)}
\end{bmatrix} \begin{bmatrix}c_{1}\\c_{2}\end{bmatrix} = \begin{bmatrix}U_{1}&U_{2}\end{bmatrix} \begin{bmatrix}\sum_{1}c_{1}\\0\end{bmatrix} = U_{1}(\sum_{1}c_{1}) = U_{1}y $

可知,$C(A) = C(U_{1})$,即 $U_{1}$ 是矩阵 $A$ 的正交基集合。

同理可知 $C(A^{T})=C(V_{1})$。


又设 $x = V_{2}c$,有:

$ Ax = \begin{bmatrix}U_{1}&U_{2}\end{bmatrix}
\begin{bmatrix} \sum_{1}&0_{r \times (n - r)}\\ 0_{(m - r) \times r}&0_{(m - r) \times (n - r)}
\end{bmatrix} \begin{bmatrix}0\\c\end{bmatrix} =0 $

可知 $V_{2}$ 是 $N(A)$ 的正交基,即 $N(A) = C(V_{2})$。

同理可知 $N(A^{T}) = C(U_{2})$


推荐系统


基本定义


  • 对于集合被推荐集合(通常是用户) $C(c \in C,\|C\| = n)$ 和推荐集合(通常是商品)$S( s \subset S,\|S\| = m)$,设映射 $\hat{u}: c,s \to F$ 为把 $s$ 推荐给 $c$ 的好坏评价函数,则推荐是指找到集合 $\hat{s}_{c} \in S$,使得:

    $\forall c \in C, \hat{s}_{c} = argmax(\hat{u}(c, s)), s \subset S$

  • 映射 $u(c, \hat{s}_{c})$ 为实际情况下 $c$ 对 $\hat{s}_{c}$ 的评分

  • $s(i,j)$ 表示推荐对象 $s_{i},s_{j}$ 之间的相似度
  • $m \times n$ 的打分矩阵 $V$,其中 $v_{ij}$ 等于 $u(c_{i}, s_{j})$。

相似度计算


  • 欧式距离:$dist(X,Y) = (\sum |x_{i} - y_{i}|^{q})^{\frac{1}{q}}$
  • Jaccard相似度,常用于值只有0,1的向量:$J(X,Y) = \frac{|X \bigcap Y|}{|X \bigcup Y|}$,其中,对于向量的交集是指有多少位相等。
  • 余弦距离:$cos(\theta) = \frac{X^{T}Y}{|X|\dot|Y|}$
  • Pearson相似度,在向量各值减去向量均值后的向量的余弦相似度:$\frac{\sum (X_{i} - \mu_{X})(Y_{i} - \mu_{Y})}{\sqrt{\sum(X_{i} - \mu_{X})^{2}}\sqrt{\sum(Y_{i} - \mu_{Y})^{2}}}$

案例


基于推荐对象相似度的协同过滤

已有的打分值 $v_{ij}$ 可以组成推荐对象 $s_{j}$ 的打分向量,从而得到两推荐对象的相似度 $s(i, j)$,再通过相似度作对推荐对象的打分值做加权,预测未知的 $\hat{v}_{pq}$:

$\hat{v}_{pq} = \frac{\sum^{K}_{r \in N(q,K)} s(q, r) \dot v_{pr}}{\sum^{K}_{r \in N(q,K)} s(q, r)}$,其中,$K$ 为TopKK值,$N(q,K)$ 为其它推荐对象与 $s_{q}$ 相似度最高的K个对象的下角标的集合。


基于被推荐对象相似度的协同过滤

和前者相似,只是对打分矩阵转置后重复上一过程


基于隐语义模型

假设有R个隐含的变量,找到矩阵$P \in R^{n \times R},Q \in R^{m \times R}$,使得:

$V \approx P \times Q^{T} = \hat{V}$

$\hat{v}_{ij} = p^{T}_{i}q_{j}$

选取最佳PQ的方法:

  • 梯度下降法,定义损失函数为$c^{2}_{ij} = (v_{ij} - (\mu + b_{i} + b_{j} + \hat{v}_{ij}))^{2} + (\lambda_{1} \sum \|p_{i}\|^{2} + \lambda_{2} \sum \|q_{j}\|^{2} + \lambda_{3} \sum \|b_{i}\|^{2} + \lambda_{4} \sum \|b_{j}\|^{2})$,其中 $\mu$ 为全部$v_{ij}$的平均,$b_{i},b_{j}$ 为对应行和列的平均

  • NFM(非负矩阵分解),常用于保证可解释性


评价标准


准确率

对于打分系统

$T$ 为 $c$ 打分的集合,则评判标准有两种:

  • $RMSE = \sqrt{\frac{\sum(u(c, \hat{s}_{c}) - \hat{u}(c, \hat{s}_{c})))^{2}}{|T|}}$
  • $MAE = \frac{\sum|u(c, \hat{s}_{c}) - \hat{u}(c, \hat{s}_{c})|}{|T|}$

对于TopN推荐

$s_{c}$ 为测试集上 $c$ 实际的选择,则评价标准有两种:

  • 准确率:$Precision = \frac{\sum_{c \in C} |\hat{s}_{c} \bigcap s_{c}|}{\sum_{c \in C} |\hat{s}_{c}|}$
  • 召回率:$Recall = \frac{\sum_{c \in C} |\hat{s}_{c} \bigcap s_{c}|}{\sum_{c \in C} |s_{c}|}$

覆盖率

表征对推荐对象的发掘能力(希望推荐系统消除马太效应),两种评价方式如下:

  • $Coverage = \frac{\bigcup_{c \in C} \hat{s}_{c}}{\|S\|}$
  • $H = - \sum p(i)log(p(i))$,其中 $p(i)$ 为第 $i$ 个推荐对象的被推荐次数除以所有推荐对象的被推荐的总次数

多样性

表征对于某个被推荐对象,其所被推荐的推荐对象的丰富性(差异性),则评价方式计算步骤如下:

  • 先计算对于 $c$ 的被推荐对象的平均多样性(不相似度):$Diversity(\hat{s}_{c}) = 1 - \frac{\sum_{s_{i},s_{j} \in \hat{s}_{c}, i \neq j} s(i, j)}{\frac{1}{2}|\hat{s}_{c}|(|\hat{s}_{c}| - 1)}$
  • 再计算所有 $C$ 的被推荐对象的平均多样性(实际工程中经常采用随即抽样计算):$Diversity = \frac{1}{|C|}\sum_{c \in C}Diversity(\hat{s}_{c})$

其他标准

  • 新颖度
  • 惊喜度
  • 信任度
  • 实时性
  • ...

贝叶斯


基本定义


  • $A$:未知参数/类别
  • $B$:已知数据(层次贝叶斯中也可以是参数)
  • $P(A)$:根据常理指定不同参数/类别的先验概率
  • $P(B|A)$:模型假设的分布

总体思路:$P(B|A) \to P(A|B)$

xiehao

Read more posts by this author.