ML笔记

模型

graph TD;
ts(Training set);
la(Learning algorithm);
h(hypothesis function);
1((x))
2((y))
ts-->la-->h;
1-->h-->2;

训练集

$\{(x^{(i)},y^{(i)})|i=1,2,...,m\}$
$x_j^{(i)}$表示第$i$个训练数据的第$j$个特征。

标准化

$x_i:=\frac{x_i-\bar{x}}{\sigma}$

回归问题——线性回归

令$x_0=1$，$x=\begin{bmatrix}x_0\\x_1\\...\\x_n\end{bmatrix}$，$\theta=\begin{bmatrix}\theta_0\\\theta_1\\...\\\theta_n\end{bmatrix}$。
hypothesis函数：$h_\theta (x)=\theta^Tx$。
总cost函数：$J(\theta)=\frac{1}{2}\text{mean}(||h-y||^2)$

（多项式回归：将$x_1^2, x_1x_2^3$等高次项作为特征）

梯度下降法

不断迭代：$\theta :=\theta-\alpha \nabla J(\theta)$
其中：

• $\alpha$为学习速率
• $\nabla J(\theta)=\text{mean}(x(h-y))$为梯度

一般方程

求$X\theta=y$的最小二乘解：$\theta=(X^TX)^{-1}X^Ty$

（若$X^TX$不可逆，可能是feature过多）

二分类问题——logistic回归

sigmoid函数：$g(z)=\frac{1}{1+e^{-z}}$。
hypothesis函数：$h_\theta (x)=g(\theta^Tx)=\frac{1}{1+e^{-\theta^Tx}}=P(y=1|x;\theta)$。

决策函数：$y=[h_\theta(x)>0.5]$
决策边界： $h_\theta(x)=0.5$，即$\theta^Tx=0$。

cost函数：

$\text{Cost}(h_\theta(x),y)=\begin{cases}-\log(h_\theta(x))&y=1\\-\log(1-h_\theta(x))& y=0\end{cases}\\=-y\log(h_\theta(x))-(1-y)\log(1-h_\theta(x))$

总cost函数：

$J(\theta)=\text{meanCost}(h_\theta(x),y)\\=-\text{mean}(y\log(h)+(1-y)\log(1-h))\\=\text{mean}(y\log(1+e^{-\theta^Tx})+(1-y)\log(1+e^{\theta^Tx}))$

梯度下降法

不断迭代：$\theta :=\theta-\alpha \nabla J(\theta)$
其中：

• $\nabla J(\theta)=\text{mean}(x(h-y))$为梯度

（多分类问题：面对每个新的数据集，都逐类进行检验（把要检验的类当作1，其余当作0），选择可能性最高的那类）

随机梯度下降法

对于规模较大的数据集，可以随机选一个样本算cost

online learning

每次获得一个新的训练集，都用它的cost进行一次梯度下降

正则化

增加penalty以控制$\theta$规模。（$\theta_0$除外）

• L1范数（绝对值和）：Lasso回归
• L2范数（平方和）：岭回归

回归问题
$J(\theta)=\frac{1}{2}\text{mean}(||h-y||^2+\frac{\lambda}{2m}(||\theta||^2)$
分类问题

$J(\theta)=-\frac{1}{m}(y^T\log(h)+(1-y)^T\log(1-h))+\frac{\lambda}{2m}(||\theta||^2)$

$\theta_j :=\theta_j(1-\alpha\frac{\lambda}{m})-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} (j\ne 0)$

一般方程
$\theta=(X^TX+\lambda \begin{bmatrix}0&O\\O&I_n\end{bmatrix})^{-1}X^Ty$
（可以解决矩阵不可逆的问题）

overfit与underfit

	overfit: high variance	underfit: high bias
	$J_{CV}>>J_{train}>0$	$J_{CV}>J_{train}>>0$
fix	fewer features, more examples, increase $\lambda$	more/polynomial features, decrease $\lambda$

神经网络

神经网络是一个多层感知机。从输入到输出共有$L$层，第$l$层$a^{(l)}$有$s_l$个unit。（$K$分类问题中$s_L=K$）

相邻两层之间的转移是Logistic回归（一个线性变换+一个sigmoid函数）：

$z^{(l+1)}=W^{(l)}a^{(l)}+b^{(l)}, a^{(l+1)}=g(z^{(l+1)})$

其中$W^{(l)}\in R^{s_{l+1}\times s_l}, b^{(l)}\in R^{s_{l+1}}$，$g(z)=\frac{1}{1+e^{-z}}$。

$J=-\text{mean}(y\log h-(1-y)\log (1-h))+||W||^2$

我们的目标是求$W,b$以最小化$J$。

梯度下降法需要知道每一步的$\frac{\partial}{\partial W_{i,j}^{(l)}}J$以及$\frac{\partial}{\partial b_{i}^{(l)}}J$。

Hadamard积

即矩阵对应位置元素乘积运算。

$S_{n\times m}\circ T_{n\times m}=\begin{bmatrix}s_{11}t_{11}&s_{12}t_{12}&...&s_{1m}t_{1m}\\ s_{21}t_{21}&s_{22}t_{22}&...&s_{2m}t_{2m}\\ ...&...&...&...\\ s_{n1}t_{n1}&s_{n2}t_{n2}&...&s_{nm}t_{nm}\end{bmatrix}$

反向传播算法

https://blog.csdn.net/qq_47903865/article/details/113839061

支持向量机

目标：

$\min_\theta C\sum(y \text{cost}_1(\theta^Tx)+(1-y)\text{cost}_0(\theta^Tx))+\frac{1}{2}||\theta||^2$

其中$C=\frac{1}{\lambda}$

当 $\begin{cases}\theta^Tx\ge 1&h=1\\\theta^Tx\le -1&h=0\end{cases}$时，$y \text{cost}_1(\theta^Tx)+(1-y)\text{cost}_0(\theta^Tx)=0$。

tip: Gaussian kernal

选取landmark $l$，利用正态分布曲线：

$f=\exp(-\frac{||z-l||^2}{2\sigma^2})$

	high bias, low variance	low bias, high variance
$C(=\frac{1}{\lambda})$	small	large
$\sigma^2$	large	small

$n$ large(>10,000), $m$(<1,000)	$n$ small(<1,000), $m$ intermediate(<10,000)	$n$ small(<1,000), $m$ large(>50,000)
linear kernel	Gaussian kernel	add features+linear kernel

tip: 扩大数据规模

在原数据上增加干扰

tip: map reduce

把训练集分给多台计算机并行计算。

tip: 上限分析

分析机器学习流水线各阶段准确率上限，从而避免无用功

聚类问题

将训练集分成多个团

K-means算法

1. 随机初始化$K$个质心$\mu_1,\mu_2,...,\mu_K$（可以随机取$K$个训练数据）
2. 找出每个点最近的质心$\mu_{c^{(i)}}$，并将质心更新为其关联点的均值。不断迭代。

optimization objective: $J(c,\mu)=\text{mean}(||x^{(i)}-\mu_{c^{(i)}}||^2)$

可能会取局部极小值，因此需多次实验

全局最小值随$K$递减

数据压缩

把$n$维数据集$X=\{x_1,x_2,...,x_m\}\in R^{n\times m}$

降到$k$维$Y\in R^{k\times m}$

PCA

1. feature scaling，去中心化
2. 求出协方差矩阵$\Sigma=\frac{1}{m}XX^T$，进行特征值分解$\Sigma=U^T\Lambda U$
3. 取$U$前$k$列，组成$P\in R^{n\times k}$
4. $Y=P^TX$，$X_{approx}=PY$

choice of $k$ : $\frac{\sum_{i=1}^k\lambda_i}{\sum_{i=1}^n\lambda_i}\ge 0.99$

可以减小数据规模、方便可视化

不推荐用来处理overfit（更推荐正则化）

异常检测

根据训练集，确定数据的异常程度

正态分布

训练集$X=\{x_1,x_2,...,x_m\}\in R^{n\times m}$

一维：$p(x;\mu,\sigma)=\frac{1}{\sqrt{2\pi}\sigma}\exp(-\frac{(x-\mu)^2}{2\sigma^2})$。

$p(x)=\prod_{i=1}^n p(x_i;\mu_i,\sigma_i)$。

$n$维：$p(x;\mu,\sigma)=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}\exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))$，其中$\Sigma$为协方差矩阵。（要求$m>n$，否则$\Sigma$不可逆）

决策函数：$y=[p(x)\le \varepsilon]$

评价依据：F1分数（精准率和召回率的调和平均数）

异常检测	监督学习
少量异常样本，大量正常样本	正常、异常样本数目接近
异常样本缺乏共性	异常样本有共性

推荐系统

$n_u$个用户，$n_m$部电影，用户$j$对电影$i$的评分为$y(i,j)$，有缺失。

协同过滤

电影$i$有特征$x^{(i)}$，用户$j$有偏好$\theta^{(j)}$。

先随机初始化$X$和$\Theta$。

然后梯度下降，目标函数$J(X,\Theta)=\frac{1}{2}||X\Theta^T-Y||^2+\frac{\lambda}{2}||X||^2+\frac{\lambda}{2}||\Theta||^2$。

对缺失的$y(i,j)$，可补齐缺失评分$y(i,j)=\theta^{(j)T}x^{(i)}$。

推荐时，选择缺失评分较高的几个电影。