有监督学习（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 取值较小时效果明显