有监督学习(Supervised Learning)
回归(Regression)
使用方差作为代价函数 $J$(cost function)较为常见,$\Theta$ 为参数向量。
$h_\Theta(x)=\Theta^TX\\\\J(\Theta)=\frac{1}{2m} \sum_{i=0}^{m}(h_{\Theta}(X^{(i)})-Y^{(i)})^{2}$
梯度下降(Gradient descent)求解局部最优解(线性回归中均为全局最优解):
$\Theta := \Theta-\alpha\frac{\partial}{\partial\Theta}J(\Theta) $ ($\alpha$ refers learning rate)
应用至线性回归(Batch Gradient Descent):
$define\ \ X_0=1\\\\h_\Theta(X^{(i)})=\Theta^TX^{(i)}\\\\\Theta:=\Theta-\alpha \frac{1}{m}\sum_{i=1}^{m}(h_{\Theta}(X^{(i)})-Y^{(i)})X^{(i)}$
Batch: Each step of gradient Descent uses all the training examples.
特征缩放(Feature Scaling)/ 均值归一化(Mean normalization):使 $X_i$ 的规模相近,提高梯度下降效率。
$x_i\ := \frac{x_i}{Maxof(x_i)\ in\ X_i}\ \ or\ \ x_i\ :=\frac{x_i-\mu_i}{\sigma_i}$
正规方程(Normal Equation)求线性回归解析解:
$Y_{m\times 1}=X_{m\times (n+1)}\Theta_{(n+1)\times 1}\\\\\Rightarrow \Theta_{min\ J_{(\Theta)}}=(X^TX)^{-1}X^TY$
正则化(Regulation):
$J(\Theta)=\frac{1}{2m} [\ \sum_{i=0}^{m}(h_{\Theta}(X^{(i)})-Y^{(i)})^{2}+\lambda\sum_{j=1}^n\theta_j^2\ ] $
引入额外的正则化项 $\lambda\sum_{j=1}^n\theta_j^2$ 用于缩小所有参数($\Theta$)的规模
正则化后进行梯度下降:
$\theta_0:=\theta_0-\alpha \frac{1}{m}\sum_{i=1}^{m}(h_{\Theta}(X^{(i)})-Y^{(i)})X_0^{(i)}\\\\\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)}\\\\\Theta=(X^TX+\lambda\begin{bmatrix}
{0}&{}&{}&{}\\
{}&{1}&{}&{}\\
{}&{}&{\ddots}&{}\\
{}&{}&{}&{1}\\
\end{bmatrix}^{-1}X^TY$
Tips:
- 随着迭代次数的增加, $J$ 应该单调递减;可以画出 $J$ 随迭代次数变化曲线或者设置 $J$ 的收敛条件。
- 若 $J$ 递增或出现增减周期性变化,可以考虑减小 $\alpha$ 。
- 对线性回归而言,只要 $\alpha$ 足够小,$J$ 一定单调递减。
- 可以尝试以三倍间隔取 $\alpha$,如 0.001,0.003,0.01,0.03 等。
- 使用换元可以用线性回归模型处理多项式回归问题(注意特征缩放)。
- 一般来说,在特征向量维数较高(维数上万时开始考虑)时使用梯度下降法,相反则使用正规方程。
- 因为需要计算$(X^TX)^{-1}$正规方程解法复杂度为O($n^3$)。
- 若$X^TX$不可逆,考虑剔除多余特征或者计算伪逆,进行正则化也可以避免求伪逆。
- 使用向量化方法可以提高代码运行效率。
Logistic Regression 分类
Logistic/Sigmoid Function:
$f(x)=\frac{1}{1+e^{-x}}\ \ x\in(-\infty,\infty)$
Single Example Logistic Regression:
$h_{\Theta}(X)=\frac{1}{1+e^{-\Theta^T X}}\\\\J(\Theta)=\frac{1}{m}\sum_{i=1}^{m}Cost(h_\Theta(X^{(i)}),Y^{(i)})\\\\Cost(h_\Theta(X^{(i)}),Y^{(i)})=-Y^{(i)}log(h_\Theta(X^{(i)}))-(1-Y^{(i)})log(1-h_\Theta(X^{(i)}))\\\\\Theta:=\Theta-\alpha \frac{1}{m}\sum_{i=1}^{m}(h_{\Theta}(X^{(i)})-Y^{(i)})X^{(i)}$
Tip:这里以向量形式隐藏了参数 $\Theta$ 与特征 $X$ 的具体形式。
Gradient Descent (梯度下降法)的优化算法:
- Conjugate gradient(共轭梯度法)
- BFGS(牛顿法)
- L-BFGS(limited-牛顿法)
一对多分类:构造多个 Logistic Regression Classifier 进行多次划分。
减缓过拟合现象:
- 减少特征数量
- 正则化
Regulation logistic regression:
$Cost\ function:J(\Theta)=-\frac{1}{m}[\sum_{i=1}^{m}Y^{(i)}log(h_\Theta(X^{(i)}))+(1-Y^{(i)})log(1-h_\Theta(X^{(i)}))]+\frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2\\\\\theta_0:=\theta_0-\alpha \frac{1}{m}\sum_{i=1}^{m}(h_{\Theta}(X^{(i)})-Y^{(i)})X_0^{(i)}\\\\\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)}$
和线性回归的形式化表达式完全一样,区别仅在于 $h_\Theta(X)$ 与 $J(\Theta)$ 的具体形式。
神经网络(Neural Networks)
当特征数增长时,使用 Logistic Regress 以增加多项式阶数的形式构造非线性分类器(non-linear classifier)的复杂度过高。
Sigmoid(Logistic)activation function
Input Layer (X) -> Hidden Layers -> Output Layer (Y)
若网络在第 $j$ 层有 $s_j$ 个神经元,则 $\Theta^{(j)}$ 的维度为 $s_{j+1}\times(s_j+1)$。
Forward propation in the hidden layers:
$define A^{(0)}=X\\\\then\ A^{(i)}=g(\Theta^{(i)}A^{(i-1)})\ while \ the\ function\ g \ refers\ Sigmoid/Logistic\ function$
计算单元下标通常从1开始,实际运算时添加值恒为1的下标为0的偏置单元。
简单来说,神经网络的每一层都将学习一个参数矩阵 $\Theta$ 用于将上一层的特征以线性变换的形式进行复合,再将复合特征作为下一层网络的输入特征。
Cost function:
$J(\Theta)=-\frac{1}{m}[\sum_{i=1}^{m}\sum_{k=1}^KY^{(i)}_{k}log((h_\Theta(X^{(i)}))_k)+(1-Y^{(i)}_k)log(1-(h_\Theta(X^{(i)}))_k)]+\frac{\lambda}{2m}\sum_{l=1}^{L-1}\sum_{i=1}^{s_l}\sum_{j=1}^{s_{l+1}}(\theta_{ji}^{(l)})^2$
Backpropagation algorithm:
若网络共 $L$ 层,则最后一层为输出,根据输出 $Y$ 得到 $\delta^{(L)}=A^{(L)}-Y$
第 $l$ 层的误差为 $\delta^{(l)}=(\Theta^{(l)})^T\delta^{(l+1)}.*g’(z^{(l)})\ \ while\ \ l\in[2,L-1]$
反向传播至第一层为输入,不进行修改。
Gradient Descent:
$\Delta^{(l)}:=\Delta^{(l)}+\delta^{(l+1)}(A^{(l)})^T\\\\\frac{\partial}{\partial\Theta^{(l)}_{ij}}J(\Theta):=\frac{1}{m}\Delta^{(l)}_{ij}+\lambda\Theta^{(l)}_{ij}\ \ if\ \ j≠0\\\\\frac{\partial}{\partial\Theta^{(l)}_{ij}}J(\Theta):=\frac{1}{m}\Delta^{(l)}_{ij}\ \ if\ \ j=0$
Gradient checking:
$check:\ \ \frac{\partial}{\partial\Theta}J(\Theta)≈\frac{J(\Theta+\epsilon)-J(\Theta-\epsilon)}{2\epsilon}$
支持向量机(Support Vector Machine)
Cost Function:
$min\ \ J(\Theta)=C\sum^m_{i=1}[Y^{(i)}cost_{1}(\Theta^TX^{(i)})+(1-Y^{(i)})cost_0(\Theta^TX^{(i)})]+\frac{1}{2}\sum^{n}_{i=0}\theta^2_i$
Also described as large margin classifier , especially when C is large. SVM is effective in describing nonlinear functions. Large C: Lower bias, high variance; Small C: Higher bias, low variance.
Mathmetic detail: $\sum_{i=1}^{n}\theta_i^2$ could be replaced by $\Theta^TM\Theta$
SVM Decision Boundary:
$min\ \ \frac{1}{2}\sum^{n}_{i=1}\theta_i^2=\frac{1}{2}||\theta||^2\\\\s.t.\theta^TX^{(i)}=p^{(i)}\cdot||\theta||≥1\ \ \ \ if\ \ Y^{(i)}=1\\\\\\ \ \ \ \ \ \ \ \theta^TX^{(i)}=p^{(i)}\cdot||\theta||≤-1\ \ \ \ if\ \ Y^{(i)}=0\\\\where\ p^{(i)}\ is\ the\ projection\ of\ X^{(i)}\ onto\ the\ vector\ \theta.\\\\Simplification:\theta_0=0$
Kernel Function:
The kernel function is also called similarity function. Need to satisfy technical condition called “Mercer’s Theorem” to make sure SVM package’s optimizations run correctly, and do not diverge.
Gaussian Kernel: $K(x,l^{(i)})=exp(-\frac{||x-l^{(i)}||^2}{2\sigma^2})$
Polynomial Kernel: $K(X,l)=(X^Tl+constant)^{degree}$
String Kernel, chi-square kernel, histogram intersection kernel and so on.
SVM is a convex optimization problem and it always gives the global minimum, we don’t need to worry about the local optima in neural network.
无监督学习(Unsupervised Learning)
聚类(Clustering)
K-means 流程:
- 选取 K 个聚类中心
- 遍历样本并一一对应地分配给聚类中心形成 K 个簇
- 分别移动每个聚类中心至对应簇的平均位置,若有聚类中心移动则重复步骤 2 ,否则达到均衡状态
代价函数 $J(\mu^{k},c^{m})=\frac{1}{m}\sum_{i=1}^m(c^{i}-\mu_{c^i})^2$
通常会将簇内样本数为零的聚类中心移除,如果确需 K 类,则将该聚类中心再次进行随机初始化
为了剔除局部最优解,应多次(50-1000)运行 K-means 算法,取 $J_{min}$ 对应的分类形式,这种做法在 K 取值较小时效果明显