前言

Machine Learning definition

• Arthur Samuel(1959)Machine Learning: Field of study that gives computers the ability to learn without being explicitly programmed.
• TomMitchell(1998)Well-posed Learning Problem: A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.

机器学习（Machine Learning，ML）是多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等。机器学习专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构，使之不断改善自身的性能。

机器学习能让我们从数据集中受到启发，换句话说，我们会利用计算机来彰显数据背后的真实含义，这才是机器学习的真实含义。它既不是只会模仿的机器人，也不是具有人类感情的仿生人。

学习资源——在线课程

Coursera: Machine Learning

机器学习-白板推导系列-开篇

Stanford CS229: Machine Learning

UCB CS189: Introduction to Machine Learning

学习资源——书籍

《统计学习方法（第2版）》分为监督学习和无监督学习两篇，全面系统地介绍了统计学习的主要方法。包括感知机、k近邻法、朴素贝叶斯法、决策树、逻辑斯谛回归与大熵模型、支持向量机、提升方法、EM算法、隐马尔可夫模型和条件随机场，以及聚类方法、奇异值分解、主成分分析、潜在语义分析、概率潜在语义分析、马尔可夫链蒙特卡罗法、潜在狄利克雷分配和PageRank算法等。

学习路线

以下不是针对回答评论，而是对现在初学者一上来就推荐统计学习方法的回答的评价（来自豆瓣）

初学者不适合看《统计学习方法》，但是从事相关行业的人必定要看，本书精简不啰嗦，面面俱到，从原理上给你整得明明白白的，辅以适当的例子，没有多余的图表，因为人工智能不是什么画图跑demo的专业，你需要有扎实的数学基础。

建议路线，ng课程入门，知道有哪些算法，大致怎么做，然后去kaggle打个入门赛，别做特征工程，把会的算法全用上。然后放下比赛，开始读这本书，同时看机器学习基石或其他比较数学化的进阶课程，这一步不需要你敲代码，你要会的是滚瓜烂熟的推导，做到这一步，再去kaggle参加奖金赛，阅读kernel，学习state of the art 模型，学习特征工程，再在学习过程中阅读最新的论文或者经典的论文，不断迭代这个过程，别淹死在什么机器学习实战上，有现成的轮子不用，非得费那个劲，除非你科班毕业，代码能力扎实，不然你能不能从头实现一遍决策树对你找不找到工作没有任何一毛钱关系。笔试不会考你如何实现hmm，只会考数据结构与算法，面试只会让你推导。

面过一些学过吴恩达公开课和《统计学习方法》之类教材的同学，一方面在实现上，C++水平不行，然后就想要来做算法，说实话，看过这些东西对于机器学习的面有所了解。了解人家转述的算法，连论文都没读过就想要来做研究也是醉了。说PCA，对于SVD分解的方法讲的头头是道，但是问他怎么用基本的特征分解来做，就说自己不了解。说K均值和EM好像很熟悉，问他K均值跟EM什么关系，不知道。说EM熟悉吧，高斯混合模型不了解……说梯度下降很熟悉吧，问他什么是线性最小二乘法什么是非线性最小二乘法，都支支吾吾不懂。一言以蔽之，知其然而不知其所以然，要做算法研究就踏踏实实以书本为纲，找到感兴趣的点去读相关论文。要做算法实现就老老实实地把C++学好，只会一点点python加上读过两本普及教材说真的没有公司要招你。

个人认为各种ML算法（含监督式/非监督式/强化学习）难度从小到大以及学习的顺序应该是这样的：

入门：线性回归/逻辑回归，kNN，k-means，决策树，神经网络（MLP/CNN/LSTM），反向传播，RL的bandit/MDP/动态规划/TD/MC

初级：贝叶斯线性回归/逻辑回归，NLP的Transformer/BERT/GPT, GMM/HMM，EM/Baum-Welch/Viterbi/卡尔曼滤波，概率图模型和BP，Junction tree，SVM/核方法/RKHS，model-based RL/policy gradient/actor-critic

中级：helmholtz/boltzmann machine/RBM/DBN，高斯过程，t-SNE/manifold learning/非线性降维，各种近似推断（平均场，期望传播，变分贝叶斯，loopy BP，kikuchi，stein），各种采样和MCMC方法（MH, Gibb’s, HMC, SMC, AIS, particle filter)，各种积分方法（MC/高斯数值求积/无迹变换）。以及一些核方法延伸的主题如MMD，HSIC之类的

高级：统计学习理论（ERM/VC维/PAC/rademacher等），贝叶斯非参（DP/CRP/IBP等）

另外附一份（个人认为）按以上各“等级”的数学要求：

入门：多元微积分，线性代数，基本概率论（随机变量，基本分布，期望和方差）

初级：凸优化（尤其constrained opt/KKT condition），图论，高维概率论（尤其是正态分布，包括正态分布的线性变换，条件概率分布），贝叶斯推断，随机过程

中级：更多的概率论（指数族分布和GLM，skewness, kurtosis，测度论）和凸优化，统计力学（spin glass model），凸分析，泛函分析

Introduction

对概率的诠释有两大学派，一种是频率派另一种是贝叶斯派。后面我们对观测集采用下面记号： $$X_{N\times p}=(x_1,x_2,\cdots ,x_N{)}^T,x_i=(x_{i1},x_{i2},\cdots ,x_{ip}{)}^T$$ 这个记号表示有 $N$ 个样本，每个样本都是 $p$ 维向量。其中每个观测都是由 $p(x|\theta )$ 生成的。

频率派的观点

$p(x|\theta )$中的 $\theta$ 是一个常量。对于 $N$ 个观测来说观测集的概率为 $p(X|\theta )\underset{iid}{=}\prod _{i=1}^{N}p(x_i|\theta ))$ 。为了求 $\theta$ 的大小，我们采用最大对数似然MLE的方法：

$${\theta }_{MLE}=\underset{\theta }{\mathrm{argmax}}\log p(X|\theta )\underset{iid}{=}\underset{\theta }{\mathrm{argmax}}\sum _{i=1}^N\log p(x_i|\theta )$$

贝叶斯派的观点

贝叶斯派认为 $p(x|\theta )$ 中的 $\theta$ 不是一个常量。这个 $\theta$ 满足一个预设的先验的分布 $\theta \sim p(\theta )$ 。于是根据贝叶斯定理依赖观测集参数的后验可以写成：

$$p(\theta |X)=\frac{p(X|\theta )\cdot p(\theta )}{p(X)}=\frac{p(X|\theta )\cdot p(\theta )}{\underset{\theta }{\int }p(X|\theta )\cdot p(\theta )d\theta }$$ 为了求 $\theta$ 的值，我们要最大化这个参数后验MAP：

$${\theta }_{MAP}=\underset{\theta }{\mathrm{argmax}}p(\theta |X)=\underset{\theta }{\mathrm{argmax}}p(X|\theta )\cdot p(\theta )$$ 其中第二个等号是由于分母和 $\theta$ 没有关系。求解这个 $\theta$ 值后计算$\frac{p(X|\theta )\cdot p(\theta )}{\underset{\theta }{\int }p(X|\theta )\cdot p(\theta )d\theta }$ ，就得到了参数的后验概率。其中 $p(X|\theta )$ 叫似然，是我们的模型分布。得到了参数的后验分布后，我们可以将这个分布用于预测贝叶斯预测： $$p(x_{new}|X)=\underset{\theta }{\int }p(x_{new}|\theta )\cdot p(\theta |X)d\theta$$ 其中积分中的被乘数是模型，乘数是后验分布。

小结

频率派和贝叶斯派分别给出了一系列的机器学习算法。频率派的观点导出了一系列的统计机器学习算法而贝叶斯派导出了概率图理论。在应用频率派的 MLE 方法时最优化理论占有重要地位。而贝叶斯派的算法无论是后验概率的建模还是应用这个后验进行推断时积分占有重要地位。因此采样积分方法如 MCMC 有很多应用。

数学基础

线性代数基础

Matrix derivatives

For a function $f:{\mathbb{R}}^{n\times d}\mapsto \mathbb{R}$ mapping from $n$-by-d matrices to the real numbers, we define the derivative of $f$ with respect to $A$ to be:

$${\nabla }_{A}f(A)=[\begin{array}{ccc}\frac{\partial f}{\partial A_{11}}& \cdots & \frac{\partial f}{\partial A_{1d}}\\ ⋮& \ddots & ⋮\\ \frac{\partial f}{\partial A_{n1}}& \cdots & \frac{\partial f}{\partial A_{nd}}\end{array}]$$

Thus, the gradient ${\nabla }_{A}f(A)$ is itself an $n$-by-$d$ matrix, whose $(i,j)$-element is $\partial f/\partial A_{ij}$. For example, suppose $A=\left[\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right]$ is a 2-by-2 matrix, and the function $f:{\mathbb{R}}^{2\times 2}\mapsto \mathbb{R}$ is given by

$$f(A)=\frac{3}{2}{A}_{11}+5A_{12}^2+A_{21}{A}_{22}.$$

Here, $A_{ij}$ denotes the $(i,j)$ entry of the matrix $A$. We then have

$${\nabla }_{A}f(A)=[\begin{array}{cc}\frac{3}{2}& 10A_{12}\\ A_{22}& A_{21}\end{array}].$$

概率论基础

高斯分布

• 一维情况 MLE
• 多维情况

一维情况 MLE

高斯分布在机器学习中占有举足轻重的作用。在 MLE 方法中：

$$\theta =(\mu ,\Sigma )=(\mu ,{\sigma }^2),{\theta }_{MLE}=\underset{\theta }{\mathrm{argmax}}\log p(X|\theta )\underset{iid}{=}\underset{\theta }{\mathrm{argmax}}\sum _{i=1}^N\log p(x_i|\theta )$$ 一般地，高斯分布的概率密度函数PDF写为：

$$p(x|\mu ,\Sigma )=\frac{1}{(2\pi {)}^{p/2}|\Sigma {|}^{1/2}}{e}^{-\frac{1}{2}(x-\mu {)}^T{\Sigma }^{-1}(x-\mu )}$$ 带入 MLE 中我们考虑一维的情况

$$\log p(X|\theta )=\sum _{i=1}^N\log p(x_i|\theta )=\sum _{i=1}^N\log \frac{1}{\sqrt{2\pi }\sigma }\exp (-(x_i-\mu {)}^2/2{\sigma }^2)$$ 首先对 $\mu$ 的极值可以得到 ： $${\mu }_{MLE}=\underset{\mu }{\mathrm{argmax}}\log p(X|\theta )=\underset{\mu }{\mathrm{argmax}}\sum _{i=1}^N(x_i-\mu {)}^2$$ 于是： $$\frac{\partial }{\partial \mu }\sum _{i=1}^N(x_i-\mu {)}^2=0⟶{\mu }_{MLE}=\frac{1}{N}\sum _{i=1}^N{x}_i$$ 其次对 $\theta$ 中的另一个参数 $\sigma$ ，有： $$\begin{array}{rl}{\sigma }_{MLE}=\underset{\sigma }{\mathrm{argmax}}\log p(X|\theta )& =\underset{\sigma }{\mathrm{argmax}}\sum _{i=1}^N[-\log \sigma -\frac{1}{2{\sigma }^2}(x_i-\mu {)}^2]\\ & =\underset{\sigma }{\mathrm{argmin}}\sum _{i=1}^N[\log \sigma +\frac{1}{2{\sigma }^2}(x_i-\mu {)}^2]\end{array}$$ 于是： $$\frac{\partial }{\partial \sigma }\sum _{i=1}^N[\log \sigma +\frac{1}{2{\sigma }^2}(x_i-\mu {)}^2]=0⟶{\sigma }_{MLE}^2=\frac{1}{N}\sum _{i=1}^N(x_i-\mu {)}^2$$ 值得注意的是，上面的推导中，首先对 $\mu$ 求 MLE， 然后利用这个结果求 ${\sigma }_{MLE}$ ，因此可以预期的是对数据集求期望时 ${\mathbb{E}}_{\mathcal{D}}[{\mu }_{MLE}]$ 是无偏差的： $${\mathbb{E}}_{\mathcal{D}}[{\mu }_{MLE}]={\mathbb{E}}_{\mathcal{D}}[\frac{1}{N}\sum _{i=1}^N{x}_i]=\frac{1}{N}\sum _{i=1}^N{\mathbb{E}}_{\mathcal{D}}[x_i]=\mu$$ 但是当对 ${\sigma }_{MLE}$ 求 期望的时候由于使用了单个数据集的 ${\mu }_{MLE}$，因此对所有数据集求期望的时候我们会发现 ${\sigma }_{MLE}$ 是 有偏的：

$$\begin{array}{rl}{\mathbb{E}}_{\mathcal{D}}[{\sigma }_{MLE}^2]& ={\mathbb{E}}_{\mathcal{D}}[\frac{1}{N}\sum _{i=1}^N(x_i-{\mu }_{MLE}{)}^2]={\mathbb{E}}_{\mathcal{D}}[\frac{1}{N}\sum _{i=1}^N(x_i^2-2x_i{\mu }_{MLE}+{\mu }_{MLE}^2)\\ & ={\mathbb{E}}_{\mathcal{D}}[\frac{1}{N}\sum _{i=1}^N{x}_i^2-{\mu }_{MLE}^2]={\mathbb{E}}_{\mathcal{D}}[\frac{1}{N}\sum _{i=1}^N{x}_i^2-{\mu }^2+{\mu }^2-{\mu }_{MLE}^2]\\ & ={\mathbb{E}}_{\mathcal{D}}[\frac{1}{N}\sum _{i=1}^N{x}_i^2-{\mu }^2]-{\mathbb{E}}_{\mathcal{D}}[{\mu }_{MLE}^2-{\mu }^2]={\sigma }^2-({\mathbb{E}}_{\mathcal{D}}[{\mu }_{MLE}^2]-{\mu }^2)\\ & ={\sigma }^2-({\mathbb{E}}_{\mathcal{D}}[{\mu }_{MLE}^2]-{\mathbb{E}}_{\mathcal{D}}^2[{\mu }_{MLE}])={\sigma }^2-Var[{\mu }_{MLE}]\\ & ={\sigma }^2-Var[\frac{1}{N}\sum _{i=1}^N{x}_i]={\sigma }^2-\frac{1}{N^2}\sum _{i=1}^{N}Var[x_i]=\frac{N-1}{N}{\sigma }^2\end{array}$$ 所以： $${\hat{\sigma }}^2=\frac{1}{N-1}\sum _{i=1}^N(x_i-\mu {)}^2$$

多维情况

多维高斯分布表达式为： $$p(x|\mu ,\Sigma )=\frac{1}{(2\pi {)}^{p/2}|\Sigma {|}^{1/2}}{e}^{-\frac{1}{2}(x-\mu {)}^T{\Sigma }^{-1}(x-\mu )}$$ 其中 $x,\mu \in {\mathbb{R}}^p,\Sigma \in {\mathbb{R}}^{p\times p}$ ，$\Sigma$ 为协方差矩阵，一般而言也是半正定矩阵。这里我们只考虑正定矩阵。首先我们处理指数上的数字，指数上的数字可以记为 $x$ 和 $\mu$ 之间的马氏距离。对于对称的协方差矩阵可进行特征值分解，$\Sigma =U\Lambda U^T=(u_1,u_2,\cdots ,u_p)diag({\lambda }_i)(u_1,u_2,\cdots ,u_p{)}^T=\sum _{i=1}^p{u}_i{\lambda }_i{u}_i^T$ ，于是：

$${\Sigma }^{-1}=\sum _{i=1}^p{u}_i\frac{1}{{\lambda }_i}{u}_i^T$$

$$\Delta =(x-\mu {)}^T{\Sigma }^{-1}(x-\mu )=\sum _{i=1}^p(x-\mu {)}^T{u}_i\frac{1}{{\lambda }_i}{u}_i^T(x-\mu )=\sum _{i=1}^p\frac{y_i^2}{{\lambda }_i}$$

我们注意到 $y_i$ 是 $x-\mu$ 在特征向量 $u_i$ 上的投影长度，因此上式子就是 $\Delta$ 取不同值时的同心椭圆。

下面我们看多维高斯模型在实际应用时的两个问题

1. 参数 $\Sigma ,\mu$ 的自由度为 $O(p^2)$ 对于维度很高的数据其自由度太高。解决方案：高自由度的来源是 $\Sigma$ 有 $\frac{p(p+1)}{2}$ 个自由参数，可以假设其是对角矩阵，甚至在各向同性假设中假设其对角线上的元素都相同。前一种的算法有 Factor Analysis，后一种有概率 PCA(p-PCA) 。

2. 第二个问题是单个高斯分布是单峰的，对有多个峰的数据分布不能得到好的结果。解决方案：高斯混合GMM 模型。

下面对多维高斯分布的常用定理进行介绍。

我们记 $x=(x_1,x_2,\cdots ,x_p{)}^T=(x_{a,m\times 1},x_{b,n\times 1}{)}^T,\mu =({\mu }_{a,m\times 1},{\mu }_{b,n\times 1}),\Sigma =\left(\begin{array}{cc}{\Sigma }_{aa}& {\Sigma }_{ab}\\ {\Sigma }_{ba}& {\Sigma }_{bb}\end{array}\right)$，已知 $x\sim \mathcal{N}(\mu ,\Sigma )$。

首先是一个高斯分布的定理：

定理：已知 $x\sim \mathcal{N}(\mu ,\Sigma ),y\sim Ax+b$，那么 $y\sim \mathcal{N}(A\mu +b,A\Sigma A^T)$。

证明：$\mathbb{E}[y]=\mathbb{E}[Ax+b]=A\mathbb{E}[x]+b=A\mu +b$，$Var[y]=Var[Ax+b]=Var[Ax]=A\cdot Var[x]\cdot A^T$。

下面利用这个定理得到 $p(x_a),p(x_b),p(x_a|x_b),p(x_b|x_a)$ 这四个量。

1. $x_a=\left(\begin{array}{cc}{\mathbb{I}}_{m\times m}& {\mathbb{O}}_{m\times n})\end{array}\right)\left(\begin{array}{c}{x}_a\\ x_b\end{array}\right)$，代入定理中得到： $$\begin{gathered} \mathbb{E}[x_a]=\left(\begin{array}{cc}\mathbb{I}& \mathbb{O}\end{array}\right)\left(\begin{array}{c}{\mu }_a\\ {\mu }_b\end{array}\right)={\mu }_a \\ Var[x_a]=\left(\begin{array}{cc}\mathbb{I}& \mathbb{O}\end{array}\right)\left(\begin{array}{cc}{\Sigma }_{aa}& {\Sigma }_{ab}\\ {\Sigma }_{ba}& {\Sigma }_{bb}\end{array}\right)\left(\begin{array}{c}\mathbb{I}\\ \mathbb{O}\end{array}\right)={\Sigma }_{aa} \end{gathered}$$ 所以 $x_a\sim \mathcal{N}({\mu }_a,{\Sigma }_{aa})$。

2. 同样的，$x_b\sim \mathcal{N}({\mu }_b,{\Sigma }_{bb})$。

3. 对于两个条件概率，我们引入三个量： $$\begin{gathered} x_{b\cdot a}=x_b-{\Sigma }_{ba}{\Sigma }_{aa}^{-1}{x}_a \\ {\mu }_{b\cdot a}={\mu }_b-{\Sigma }_{ba}{\Sigma }_{aa}^{-1}{\mu }_a \\ {\Sigma }_{bb\cdot a}={\Sigma }_{bb}-{\Sigma }_{ba}{\Sigma }_{aa}^{-1}{\Sigma }_{ab} \end{gathered}$$ 特别的，最后一个式子叫做 ${\Sigma }_{bb}$ 的 Schur Complementary。可以看到： $$x_{b\cdot a}=\left(\begin{array}{cc}-{\Sigma }_{ba}{\Sigma }_{aa}^{-1}& {\mathbb{I}}_{n\times n}\end{array}\right)\left(\begin{array}{c}{x}_a\\ x_b\end{array}\right)$$ 所以： $$\begin{gathered} \mathbb{E}[x_{b\cdot a}]=\left(\begin{array}{cc}-{\Sigma }_{ba}{\Sigma }_{aa}^{-1}& {\mathbb{I}}_{n\times n}\end{array}\right)\left(\begin{array}{c}{\mu }_a\\ {\mu }_b\end{array}\right)={\mu }_{b\cdot a} \\ Var[x_{b\cdot a}]=\left(\begin{array}{cc}-{\Sigma }_{ba}{\Sigma }_{aa}^{-1}& {\mathbb{I}}_{n\times n}\end{array}\right)\left(\begin{array}{cc}{\Sigma }_{aa}& {\Sigma }_{ab}\\ {\Sigma }_{ba}& {\Sigma }_{bb}\end{array}\right)\left(\begin{array}{c}-{\Sigma }_{aa}^{-1}{\Sigma }_{ba}^T\\ {\mathbb{I}}_{n\times n}\end{array}\right)={\Sigma }_{bb\cdot a} \end{gathered}$$ 利用这三个量可以得到 $x_b=x_{b\cdot a}+{\Sigma }_{ba}{\Sigma }_{aa}^{-1}{x}_a$。因此： $$\mathbb{E}[x_b|x_a]={\mu }_{b\cdot a}+{\Sigma }_{ba}{\Sigma }_{aa}^{-1}{x}_a$$

   $$Var[x_b|x_a]={\Sigma }_{bb\cdot a}$$

   这里同样用到了定理。

4. 同样： $$\begin{gathered} x_{a\cdot b}=x_a-{\Sigma }_{ab}{\Sigma }_{bb}^{-1}{x}_b \\ {\mu }_{a\cdot b}={\mu }_a-{\Sigma }_{ab}{\Sigma }_{bb}^{-1}{\mu }_b \\ {\Sigma }_{aa\cdot b}={\Sigma }_{aa}-{\Sigma }_{ab}{\Sigma }_{bb}^{-1}{\Sigma }_{ba} \end{gathered}$$ 所以： $$\mathbb{E}[x_a|x_b]={\mu }_{a\cdot b}+{\Sigma }_{ab}{\Sigma }_{bb}^{-1}{x}_b$$

   $$Var[x_a|x_b]={\Sigma }_{aa\cdot b}$$

下面利用上边四个量，求解线性模型：

已知：$p(x)=\mathcal{N}(\mu ,{\Lambda }^{-1}),p(y|x)=\mathcal{N}(Ax+b,L^{-1})$，求解：$p(y),p(x|y)$。

解：令 $y=Ax+b+ϵ,ϵ\sim \mathcal{N}(0,L^{-1})$，所以 $\mathbb{E}[y]=\mathbb{E}[Ax+b+ϵ]=A\mu +b$，$Var[y]=A{\Lambda }^{-1}{A}^T+L^{-1}$，因此： $$>p(y)=\mathcal{N}(A\mu +b,L^{-1}+A{\Lambda }^{-1}{A}^T)>$$ 引入 $z=\left(\begin{array}{c}x\\ y\end{array}\right)$，我们可以得到 $Cov[x,y]=\mathbb{E}[(x-\mathbb{E}[x])(y-\mathbb{E}[y]{)}^T]$。对于这个协方差可以直接计算： $$>\begin{array}{rl}>Cov(x,y)& =\mathbb{E}[(x-\mu )(Ax-A\mu +ϵ{)}^T]=\mathbb{E}[(x-\mu )(x-\mu {)}^T{A}^T]=Var[x]A^T={\Lambda }^{-1}{A}^T>\end{array}>$$ 注意到协方差矩阵的对称性，所以 $p(z)=\mathcal{N}\left(\begin{array}{c}\mu \\ A\mu +b\end{array}\right),\left(\begin{array}{cc}{\Lambda }^{-1}& {\Lambda }^{-1}{A}^T\\ A{\Lambda }^{-1}& L^{-1}+A{\Lambda }^{-1}{A}^T\end{array}\right))$。根据之前的公式，我们可以得到： $$>\mathbb{E}[x|y]=\mu +{\Lambda }^{-1}{A}^T(L^{-1}+A{\Lambda }^{-1}{A}^T{)}^{-1}(y-A\mu -b)>$$

$$>Var[x|y]={\Lambda }^{-1}-{\Lambda }^{-1}{A}^T(L^{-1}+A{\Lambda }^{-1}{A}^T{)}^{-1}A{\Lambda }^{-1}>$$

线性回归

• 概述
• 小结

概述

Given data like this, how can we learn to predict the prices of other houses in Portland, as a function of the size of their living areas?

To establish notation for future use, we'll use $x^{(i)}$ to denotc the “input” variables (living area in this example), also called input featurcs, and $y^{(i)}$ to denote the “output” or target variable that we are trying to predict $(\mathrm{price}).$ A pair $(x^{(i)},y^{(i)})$ is called a training example, and the dataset that we'll be using to learn—a list of $n$ training examples $\{(x^{(i)},y^{(i)});i=$ $1,\dots ,n\}$—is called a training set. Note that the superscript “$(i)$” in the notation is simply an index into the training set, and has nothing to do with exponentiation. We will also use $\chi$ denote the space of input values, and $\gamma$ the space of output values. In this example, $\mathcal{X}=\mathcal{Y}=\mathbb{R}.$

To describe the supervised learning problem slightly more formally, our goal is, given a training set, to learn a function $h:\mathcal{X}\mapsto \mathcal{Y}$ so that $h(x)$ is a “good” predictor for the corresponding value of $y.$ For historical reasons, this function h is called a hypothesis.

When the target variable that we're trying to predict is continuous, such as in our housing example, we call the learning problem a regression problem.When $y$ can take on only a small number of discrete values (such as if, given the living area, we wanted to predict if a dwelling is a house or an apartment, say), we call it a classification problem.

Here, the $x$'s are two-dimensional vectors in ${\mathbb{R}}^2$. For instance, $x_1^{(i)}$ is the living area of the $i$-th house in the training set, and $x_2^{(i)}$ is its number of bedrooms. (In general, when designing a learning problem, it will be up to you to decide what features to choose, so if you are out in Portland gathering housing data, you might also decide to include other features such as whether each house has a fireplace, the number of bathrooms, and so on. We'll say more about feature selection later, but for now let's take the features as given.)

To perform supervised learning, we must decide how we're going to represent functions/hypotheses $h$ in a computer. As an initial choice, let's say we decide to approximate $y$ as a linear function of $x:$

$$\begin{array}{r}{h}_{\theta }(x)={\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2\end{array}$$

Here, the ${\theta }_i$ 's are the parameters (also called weights) parameterizing the space of linear functions mapping from $\chi$ to $\gamma$. When there is no risk of confusion, we will drop the $\theta$ subscript in $h_{\theta }(x)$, and write it more simply as $h(x).$ To simplify our notation, we also introduce the convention of letting $x_0=1$(this is the intercept term), so that

$$h(x)=\sum _{i=0}^d{\theta }_i{x}_i={\theta }^{T}x,$$

where on the right-hand side above we are viewing $\theta$ and $x$ both as vectors, and here $d$ is the number of input variables (not counting $x_0).$

Now, given a training set, how do we pick, or learn, the parameters $\theta ?$ One reasonable method seems to be to make $h(x)$ close to $y$, at least for the training examples we have. To formalize this, we will define a function that measures, for each value of the $\theta$'s, how close the $h(x^{(i)})$'s are to the corresponding $y^{(i),}$s. We define the $\cos$t function:

$$\begin{array}{rl}J(\theta )& =\frac{1}{2}\sum _{i=1}^n(h_{\theta }(x^{(i)})-y^{(i)}{)}^2.\end{array}$$

If you've seen linear regression before, you may recognize this as the familian least-squares cost function that gives rise to the ordinary least squares regression model. Whether or not you have seen it previously, let's keep going, and we'll eventually show this to be a special case of a much broader family of algorithms.

两种求解方式的比较：

可见特征方程得到的是解析解，无需迭代，也没有设置学习速率的繁琐，需要特征归一化，但是求解正规方程需要求矩阵的逆，然而不是所有的矩阵都可逆，而且有些可逆矩阵的求逆极其耗费时间，所以特征方程法看似简单，其实使用场景并不多。只有当特征值比较小的时候，可以考虑使用特征方程法。

小结

线性回归模型是最简单的模型，但是麻雀虽小，五脏俱全，在这里，我们利用最小二乘误差得到了闭式解。同时也发现，在噪声为高斯分布的时候，MLE 的解等价于最小二乘误差，而增加了正则项后，最小二乘误差加上 L2 正则项等价于高斯噪声先验下的 MAP解，加上 L1 正则项后，等价于 Laplace 噪声先验。

传统的机器学习方法或多或少都有线性回归模型的影子：

1. 线性模型往往不能很好地拟合数据，因此有三种方案克服这一劣势：
   1. 对特征的维数进行变换，例如多项式回归模型就是在线性特征的基础上加入高次项。
   2. 在线性方程后面加入一个非线性变换，即引入一个非线性的激活函数，典型的有线性分类模型如感知机。
   3. 对于一致的线性系数，我们进行多次变换，这样同一个特征不仅仅被单个系数影响，例如多层感知机（深度前馈网络）。
2. 线性回归在整个样本空间都是线性的，我们修改这个限制，在不同区域引入不同的线性或非线性，例如线性样条回归和决策树模型。
3. 线性回归中使用了所有的样本，但是对数据预先进行加工学习的效果可能更好（所谓的维数灾难，高维度数据更难学习），例如 PCA 算法和流形学习。

线性回归——梯度下降法求解

• LMS algorithm
• Batch Gradient Descent
• Repeat until convergence {
• Stochastic Gradient Descent

LMS algorithm

We want to choose $\theta$ so as to minimize $J(\theta ).$ To do so, let's use a search algorithm that starts with some “initial guess” for $\theta$, and that repeatedly changes $\theta$ to make $J(\theta )$ smaller, until hopefully we converge to a value of $\theta$ that minimizes $J(\theta ).$ Specifically, let's consider the gradient descent algorithm, which starts with some initial $\theta$, and repeatedly performs the update:

$${\theta }_j:={\theta }_j-\alpha \frac{\partial }{\partial {\theta }_j}J(\theta ).$$

(This update is simultaneously performed for all values of $j=0,\dots ,d.)$ Here, $\alpha$ is called the learning rate. This is a very natural algorithm that repeatedly takes a step in the direction of steepest decrease of $J.$

In order to implement this algorithm, we have to work out what is the partial derivative term on the right hand side. Let's first work it out for the case of if we have only one training example $(x,y)$, so that we can neglect the sum in the definition of $J$. We have:

$$\begin{array}{rl}\frac{\partial }{\partial {\theta }_j}J(\theta )& =\frac{\partial }{\partial {\theta }_j}\frac{1}{2}{\left(h_{\theta }(x)-y\right)}^2\\ & =2\cdot \frac{1}{2}\left(h_{\theta }(x)-y\right)\cdot \frac{\partial }{\partial {\theta }_j}(h_{\theta }(x)-y)\\ & =(h_{\theta }(x)-y)\cdot \frac{\partial }{\partial {\theta }_j}\left(\sum _{i=0}^d{\theta }_i{x}_i-y\right)\\ & =\left(h_{\theta }(x)-y\right)x_j\end{array}$$ For a single training example, this gives the update rule:${}^1$

$${\theta }_j:={\theta }_j+\alpha \left(y^{(i)}-h_{\theta }(x^{(i)})\right)x_j^{(i)}.$$

The rule is called the LMS update rule (LMS stands for “least mean squares”), and is also known as the Widrow-Hoff learning rule. This rule has several properties that seem natural and intuitive. For instance, the magnitude of the update is proportional to the error term $(y^{(i)}-h_{\theta }(x^{(i)}));$ thus, for instance, if we are encountering a training example on which our prediction nearly matches the actual value of $y^{(i)}$, then we find that there is little need to change the parameters; in contrast, a larger change to the parameters will be made if our prediction $h_{\theta }(x^{(i)})$ has a large error (i.e., if it is very far from $y^{(i)}).$

We'd derived the LMS rule for when there was only a single training example. There are two ways to modify this method for a training set of more than one example.

Batch Gradient Descent

The first is replace it with the following algorithm:

Repeat until convergence $\{$

$${\theta }_j:={\theta }_j+\alpha \sum _{i=1}^n\left(y^{(i)}-h_{\theta }(x^{(i)})\right)x_j^{(i)},\text{(for every }j)$$

}

By grouping the updates of the coordinates into an update of the vector $\theta$, we can rewrite update (1.1) in a slightly more succinct way:

$$\theta :=\theta +\alpha \sum _{i=1}^n\left(y^{(i)}-h_{\theta }(x^{(i)})\right)x^{(i)}$$

The reader can easily verify that the quantity in the summation in the update rule above is just $\partial (J(\theta ))/\partial {\theta }_j$( for the original definition of $J$) . So, this is simply gradient descent on the original cost function $J.$ This method looks at every example in the entire training set on every step, and is called batch gradient descent. Note that, while gradient descent can be susceptible to local minima in general, the optimization problem we have posed here for linear regression has only one global, and no other local, optima; thus gradient descent always converges (assuming the learning rate $\alpha$ is not too large) to the global minimum. Indeed, $J$ is a convex quadratic function. Here is an example of gradient descent as it is run to minimize a quadratic function.

Stochastic Gradient Descent

The above results were obtained with batch gradient descent. There is an alternative to batch gradient descent that also works very well. Consider the following algorithm:

Loop $\{$ for $i=1$ to $n,$

$${\theta }_j:={\theta }_j+\alpha \left(y^{(i)}-h_{\theta }(x^{(i)})\right)x_j^{(i)},\text{(for every }j)$$

$\}$

By grouping the updates of the coordinates into an update of the vector $\theta$, we can rewrite update (1.2) in a slightly more succinct way:

$$\theta :=\theta +\alpha \left(y^{(i)}-h_{\theta }(x^{(i)})\right)x^{(i)}$$

In this algorithm, we repeatedly run through the training set, and each time we encounter a training example, we update the parameters according to the gradient of the error with respect to that single training example only. This algorithm is called stochastic gradient descent (also incremental gradient descent). Whereas batch gradient descent has to scan through the entire training set before taking a single step—a costly operation if $n$ is large—stochastic gradient descent can start making progress right away, and continues to make progress with each example it looks at. Often, stochastic gradient descent gets θ “close” to the minimum much faster than batch gradient descent. (Note however that it may never “converge” to the minimum, and the parameters θ will keep oscillating around the minimum of J(θ); but in practice most of the values near the minimum will be reasonably good approximations to the true minimum.)

For these reasons, particularly when the training set is large, stochastic gradient descent is often preferred over batch gradient descent.

线性回归——正则方程法求解

• Least squares revisited
• 最小二乘法
• 噪声为高斯分布的 MLE
• 权重先验也为高斯分布的 MAP

假设数据集为： $$\mathcal{D}=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$$ 其中$x_i\in R^p,y_i\in R,i=1,2,...,N$

考虑截距的话，则$x_i\in R^{p+1},y_i\in R,i=1,2,...,N$，此时X、W和Y的表达式如下：

$${X=(\begin{array}{cccc}{x}_1& x_2& \cdots & x_N\end{array})}^T=\left(\begin{array}{c}{x}_1^T\\ x_2^T\\ ⋮\\ x_N^T\end{array}\right)={\left(\begin{array}{ccccc}1& x_{11}& x_{12}& \cdots & x_{1p}\\ 1& x_{21}& x_{22}& \cdots & x_{2p}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ 1& x_{N1}& x_{N2}& \cdots & x_{Np}\end{array}\right)}_{N\ast （p+1）}$$

$$W={\left(\begin{array}{c}{w}_0\\ w_1\\ w_2\\ ⋮\\ w_p\end{array}\right)}_{(p+1)\times 1}$$

$$Y={\left(\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_N\end{array}\right)}_{N\times 1}$$

方便起见，后面我们记： $$X=(x_1,x_2,\cdots ,x_N{)}^T,Y=(y_1,y_2,\cdots ,y_N{)}^T$$ 对每一个样本数据，作出如下的线性回归假设： $$f(w)=w^{T}x$$

Least squares revisited

Armed with the tools of matrix derivatives, let us now proceed to find in closed-form the value of θ that minimizes J(θ). We begin by re-writing J in matrix-vectorial notation.

Given a training set, define the design matrix X to be the n-by-d matrix (actually n-by-d + 1, if we include the intercept term) that contains the training examples’ input values in its rows:

$$X=[\begin{array}{c}-(x^{(1)}{)}^T-\\ -(x^{(2)}{)}^T-\\ ⋮\\ -(x^{(n)}{)}^T-\end{array}].$$

Also, let $\vec{y}$ be the $n$-dimensional vector containing all the target values from the training set:

$$\vec{y}=[\begin{array}{c}{y}^{(1)}\\ y^{(2)}\\ ⋮\\ y^{(n)}\end{array}].$$

Now, since $h_{\theta }(x^{(i)})=(x^{(i)}{)}^T\theta ,$ we can easily verify that

Thus, using the fact that for a vector $z,$ we have that $z^{T}z={\sum }_i{z}_i^2:$

$$\begin{array}{rlrl}\frac{1}{2}(X\theta -\vec{y}{)}^T(X\theta -\vec{y})& & =& \frac{1}{2}\sum _{i=1}^n(h_{\theta }(x^{(i)})-y^{(i)}{)}^2\\ & & =& J(\theta )\end{array}$$

Finally, to minimize $J$ let's find its derivatives with respect to $\theta$. Hence,

$$\begin{array}{rl}{\nabla }_{\theta }J(\theta )& ={\nabla }_{\theta }\frac{1}{2}(X\theta -\vec{y}{)}^T(X\theta -\vec{y})\\ & =\frac{1}{2}{\nabla }_{\theta }((X\theta {)}^{T}X\theta -(X\theta {)}^T\vec{y}-{\vec{y}}^T(X\theta )+{\vec{y}}^T\vec{y})\\ & =\frac{1}{2}{\nabla }_{\theta }\left({\theta }^T(X^{T}X)\theta -{\vec{y}}^T(X\theta )-{\vec{y}}^T(X\theta )\right)\\ & =\begin{array}{rc}\frac{1}{2}{\nabla }_{\theta }& \left({\theta }^T(X^{T}X)\theta -2(X^T\vec{y}{)}^T\theta \right)\end{array}\\ & =\frac{1}{2}\left(2X^{T}X\theta -2X^T\vec{y}\right)\\ & \begin{array}{rc}=& X^{T}X\theta -X^T\vec{y}\end{array}\end{array}$$ In the third step, we used the fact that $a^{T}b=b^{T}a$, and in the fifth step used the facts ${\nabla }_x{b}^{T}x=b$ and ${\nabla }_x{x}^{T}Ax=2Ax$ for symmetric matrix $A$ (fon more details, see Section 4.3 of “Linear Algebra Review and Reference”). To minimize $J,$ we set its derivatives to zero, and obtain the normal equations:

$$X^{T}X\theta =X^T\vec{y}$$

Thus, the value of $\theta$ that minimizes $J(\theta )$ is given in closed form by the equation

$$\theta =(X^{T}X{)}^{-1}{X}^T\vec{y}$$

最小二乘法

对这个问题，采用二范数定义的平方误差来定义损失函数： $$L(w)=\sum _{i=1}^N||w^T{x}_i-y_i|{|}_2^2$$ 展开得到： $$\begin{array}{rl}L(w)& =(w^T{x}_1-y_1,\cdots ,w^T{x}_N-y_N)\cdot (w^T{x}_1-y_1,\cdots ,w^T{x}_N-y_N{)}^T\\ & =(w^T{X}^T-Y^T)\cdot (Xw-Y)=w^T{X}^{T}Xw-Y^{T}Xw-w^T{X}^{T}Y+Y^{T}Y\\ & =w^T{X}^{T}Xw-2w^T{X}^{T}Y+Y^{T}Y\end{array}$$ 最小化这个值的 $\hat{w}$ ： $$\begin{array}{rl}\hat{w}=\underset{w}{\mathrm{argmin}}L(w)& ⟶\frac{\partial }{\partial w}L(w)=0\\ & ⟶2X^{T}X\hat{w}-2X^{T}Y=0\\ & ⟶\hat{w}=(X^{T}X{)}^{-1}{X}^{T}Y=X^{+}Y\end{array}$$ 这个式子中 $(X^{T}X{)}^{-1}{X}^T$ 又被称为伪逆。对于行满秩或者列满秩的 $X$，可以直接求解，但是对于非满秩的样本集合，需要使用奇异值分解（SVD）的方法，对 $X$ 求奇异值分解，得到 $$X=U\Sigma V^T$$ 于是： $$X^{+}=V{\Sigma }^{-1}{U}^T$$ 在几何上，最小二乘法相当于模型（这里就是直线）和试验值的距离的平方求和，假设我们的试验样本张成一个 $p$ 维空间（满秩的情况）：$X=Span(x_1,\cdots ,x_N)$，而模型可以写成 $f(w)=X\beta$，也就是 $x_1,\cdots ,x_N$ 的某种组合，而最小二乘法就是说希望 $Y$ 和这个模型距离越小越好，于是它们的差应该与这个张成的空间垂直： $$X^T\cdot (Y-X\beta )=0⟶\beta =(X^{T}X{)}^{-1}{X}^{T}Y$$

噪声为高斯分布的 MLE

对于一维的情况，记 $y=w^{T}x+ϵ,ϵ\sim \mathcal{N}(0,{\sigma }^2)$，那么 $y\sim \mathcal{N}(w^{T}x,{\sigma }^2)$。代入极大似然估计中： $$\begin{array}{rl}L(w)=\log p(Y|X,w)& =\log \prod _{i=1}^{N}p(y_i|x_i,w)\\ & =\sum _{i=1}^N\log (\frac{1}{\sqrt{2\pi \sigma }}{e}^{-\frac{(y_i-w^T{x}_i{)}^2}{2{\sigma }^2}})\\ \underset{w}{\mathrm{argmax}}L(w)& =\underset{w}{\mathrm{argmin}}\sum _{i=1^N}(y_i-w^T{x}_i{)}^2\end{array}$$ 这个表达式和最小二乘估计得到的结果一样。

权重先验也为高斯分布的 MAP

取先验分布 $w\sim \mathcal{N}(0,{\sigma }_0^2)$。于是：  $$\begin{array}{rl}\hat{w}=\underset{w}{\mathrm{argmax}}p(w|Y)& =\underset{w}{\mathrm{argmax}}p(Y|w)p(w)\\ & =\underset{w}{\mathrm{argmax}}\log p(Y|w)p(w)\\ & =\underset{w}{\mathrm{argmax}}(\log p(Y|w)+\log p(w))\\ & =\underset{w}{\mathrm{argmin}}[(y-w^{T}x{)}^2+\frac{{\sigma }^2}{{\sigma }_0^2}{w}^{T}w]\end{array}$$ 这里省略了 $X$，$p(Y)$和 $w$ 没有关系，同时也利用了上面高斯分布的 MLE的结果。

我们将会看到，超参数 ${\sigma }_0$的存在和下面会介绍的 Ridge 正则项可以对应，同样的如果将先验分布取为 Laplace 分布，那么就会得到和 L1 正则类似的结果。

线性回归正则化

• L1 Lasso
• L2 Ridge

在实际应用时，如果样本容量不远远大于样本的特征维度，很可能造成过拟合，对这种情况，我们有下面三个解决方式：

• 加数据
• 特征选择（手动删除一些不重要的特征）、特征提取（降维如PCA）
• 正则化

正则化一般是在损失函数（如上面介绍的最小二乘损失）上加入正则化项（表示模型的复杂度对模型的惩罚），下面我们介绍一般情况下的两种正则化框架。 $$\begin{array}{rl}L1& :\underset{w}{\mathrm{argmin}}L(w)+\lambda ||w|{|}_1,\lambda >0\\ L2& :\underset{w}{\mathrm{argmin}}L(w)+\lambda ||w|{|}_2^2,\lambda >0\end{array}$$ 下面对最小二乘误差分别分析这两者的区别。

L1 Lasso

L1正则化可以引起稀疏解。

从最小化损失的角度看，由于 L1 项求导在0附近的左右导数都不是0，因此更容易取到0解。

从另一个方面看，L1 正则化相当于： $$\begin{gathered} \underset{w}{\mathrm{argmin}}L(w) \\ s.t.||w|{|}_1<C \end{gathered}$$ 我们已经看到平方误差损失函数在 $w$ 空间是一个椭球，因此上式求解就是椭球和 $||w|{|}_1=C$的切点，因此更容易相切在坐标轴上。

L2 Ridge

$$\begin{array}{rl}\hat{w}=\underset{w}{\mathrm{argmin}}L(w)+\lambda w^{T}w& ⟶\frac{\partial }{\partial w}L(w)+2\lambda w=0\\ & ⟶2X^{T}X\hat{w}-2X^{T}Y+2\lambda \hat{w}=0\\ & ⟶\hat{w}=(X^{T}X+\lambda \mathbb{I}{)}^{-1}{X}^{T}Y\end{array}$$

可以看到，这个正则化参数和前面的 MAP 结果不谋而合。利用2范数进行正则化不仅可以是模型选择 $w$ 较小的参数，同时也避免 $X^{T}X$不可逆的问题。

Linear Classification线性分类

两分类-硬分类-感知机算法

我们选取激活函数为： $$sign(a)=\{\begin{array}{c}+1,a\ge 0\\ -1,a<0\end{array}$$ 这样就可以将线性回归的结果映射到两分类的结果上了。

定义损失函数为错误分类的数目，比较直观的方式是使用指示函数，但是指示函数不可导，因此可以定义： $$L(w)=\sum _{x_i\in {\mathcal{D}}_{wrong}}-y_i{w}^T{x}_i$$ 其中，${\mathcal{D}}_{wrong}$是错误分类集合，实际在每一次训练的时候，我们采用梯度下降的算法。损失函数对 $w$ 的偏导为： $$\frac{\partial }{\partial w}L(w)=\sum _{x_i\in {\mathcal{D}}_{wrong}}-y_i{x}_i$$ 但是如果样本非常多的情况下，计算复杂度较高，但是，实际上我们并不需要绝对的损失函数下降的方向，我们只需要损失函数的期望值下降，但是计算期望需要知道真实的概率分布，我们实际只能根据训练数据抽样来估算这个概率分布（经验风险）：

\mathbb{E}{\mathcal D}[\mathbb{E}\hat{p}[\nabla_wL(w)]]=\mathbb{E}{\mathcal D}[\frac{1}{N}\sum\limits{i=1}^N\nabla_wL(w)]

我们知道， $N$ 越大，样本近似真实分布越准确，但是对于一个标准差为 $\sigma$ 的数据，可以确定的标准差仅和 $\sqrt{N}$ 成反比，而计算速度却和 $N$ 成正比。因此可以每次使用较少样本，则在数学期望的意义上损失降低的同时，有可以提高计算速度，如果每次只使用一个错误样本，我们有下面的更新策略（根据泰勒公式，在负方向）： $$w^{t+1}\leftarrow w^t+\lambda y_i{x}_i$$ 是可以收敛的，同时使用单个观测更新也可以在一定程度上增加不确定度，从而减轻陷入局部最小的可能。在更大规模的数据上，常用的是小批量随机梯度下降法。

两分类-硬分类-线性判别分析 LDA

在 LDA 中，我们的基本想法是选定一个方向，将试验样本顺着这个方向投影，投影后的数据需要满足两个条件，从而可以更好地分类：

1. 相同类内部的试验样本距离接近。
2. 不同类别之间的距离较大。

首先是投影，我们假定原来的数据是向量 $x$，那么顺着 $w$ 方向的投影就是标量： $$z=w^T\cdot x(=|w|\cdot |x|\cos \theta )$$ 对第一点，相同类内部的样本更为接近，我们假设属于两类的试验样本数量分别是 $N_1$和 $N_2$，那么我们采用方差矩阵来表征每一个类内的总体分布，这里我们使用了协方差的定义，用 $S$ 表示原数据的协方差： $$\begin{array}{rl}{C}_1:Va{r}_z[C_1]& =\frac{1}{N_1}\sum _{i=1}^{N_1}(z_i-\overline{z_{c1}})(z_i-\overline{z_{c1}}{)}^T\\ & =\frac{1}{N_1}\sum _{i=1}^{N_1}(w^T{x}_i-\frac{1}{N_1}\sum _{j=1}^{N_1}{w}^T{x}_j)(w^T{x}_i-\frac{1}{N_1}\sum _{j=1}^{N_1}{w}^T{x}_j{)}^T\\ & =w^T\frac{1}{N_1}\sum _{i=1}^{N_1}(x_i-\overline{x_{c1}})(x_i-\overline{x_{c1}}{)}^{T}w\\ & =w^T{S}_{1}w\\ C_2:Va{r}_z[C_2]& =\frac{1}{N_2}\sum _{i=1}^{N_2}(z_i-\overline{z_{c2}})(z_i-\overline{z_{c2}}{)}^T\\ & =w^T{S}_{2}w\end{array}$$ 所以类内距离可以记为： $$\begin{array}{r}Va{r}_z[C_1]+Va{r}_z[C_2]=w^T(S_1+S_2)w\end{array}$$ 对于第二点，我们可以用两类的均值表示这个距离： $$\begin{array}{rl}(\overline{z_{c1}}-\overline{z_{c2}}{)}^2& =(\frac{1}{N_1}\sum _{i=1}^{N_1}{w}^T{x}_i-\frac{1}{N_2}\sum _{i=1}^{N_2}{w}^T{x}_i{)}^2\\ & =(w^T(\overline{x_{c1}}-\overline{x_{c2}}){)}^2\\ & =w^T(\overline{x_{c1}}-\overline{x_{c2}})(\overline{x_{c1}}-\overline{x_{c2}}{)}^{T}w\end{array}$$ 综合这两点，由于协方差是一个矩阵，于是我们用将这两个值相除来得到我们的损失函数，并最大化这个值： $$\begin{array}{rl}\hat{w}=\underset{w}{\mathrm{argmax}}J(w)& =\underset{w}{\mathrm{argmax}}\frac{(\overline{z_{c1}}-\overline{z_{c2}}{)}^2}{Va{r}_z[C_1]+Va{r}_z[C_2]}\\ & =\underset{w}{\mathrm{argmax}}\frac{w^T(\overline{x_{c1}}-\overline{x_{c2}})(\overline{x_{c1}}-\overline{x_{c2}}{)}^{T}w}{w^T(S_1+S_2)w}\\ & =\underset{w}{\mathrm{argmax}}\frac{w^T{S}_{b}w}{w^T{S}_{w}w}\end{array}$$ 这样，我们就把损失函数和原数据集以及参数结合起来了。下面对这个损失函数求偏导，注意我们其实对 $w$ 的绝对值没有任何要求，只对方向有要求，因此只要一个方程就可以求解了： $$\begin{array}{rl}& \frac{\partial }{\partial w}J(w)=2S_{b}w(w^T{S}_{w}w{)}^{-1}-2w^T{S}_{b}w(w^T{S}_{w}w{)}^{-2}{S}_{w}w=0\\ & ⟹S_{b}w(w^T{S}_{w}w)=(w^T{S}_{b}w)S_{w}w\\ & ⟹w\propto S_w^{-1}{S}_{b}w=S_w^{-1}(\overline{x_{c1}}-\overline{x_{c2}})(\overline{x_{c1}}-\overline{x_{c2}}{)}^{T}w\propto S_w^{-1}(\overline{x_{c1}}-\overline{x_{c2}})\end{array}$$ 于是 $S_w^{-1}(\overline{x_{c1}}-\overline{x_{c2}})$ 就是我们需要寻找的方向。最后可以归一化求得单位的 $w$ 值。