Regression: Output a Scalar

• stock market forecast
• self-driver car
• recommendation

Example Application

estimating the combat power(CP) of a pokemon after evolution.

Step 1: Model

liner model: $$y = b + \sum{w_ix_i}$$
$y = b + w * x_{cp}$
假设根据domain knowledge我们认为进化后的cp值和进化之前的cp($x_{cp}$)值存在线性关系。

Step 2: Goodness of Function

利用training set，根据Loss function来衡量model中的无数个function的好坏。

$$L(f) = \sum_{i=1}^{N}(\hat{y}^n - f(x_{cp}^{n}))^2$$ $$L(w, b) = \sum_{i=1}^{N}(\hat{y}^n - (b + w*x_{cp}^n))^2$$

Step 3: Best Function

对最优化问题进行求解：
$$w^{*}, b^{*} = argmin_{w, b} \ L(w, b)$$

Gradient Descent

只要定义了合理的Loss function，并且损失函数对于参数是可微分的，那么就可以使用Gradient Descent来进行optimization problem的求解。

• 只有一个参数w的时候

• 有两个参数w和b的时候

需要注意的是，不仅仅只有local minima和global minima处的梯度为0，saddle point的梯度也为0，并且梯度的更新在plateau上非常慢。

Model Selection

A more complex model does not always lead to better performance on testing data. This is overfitting.

Regularization

$$L(w, b) = \sum_{n=1}^{N}\big(\hat{y}^n - (b + \sum w_ix^n_i)\big)^2 + \lambda \sum (w_i)^2$$

现在通过gradient descent系列类的方法最小化loss function的同时，要考虑参数w的影响，所以参数w更小的function会是更好的解，而w很小的function是很平滑的（极端情况下，如果所有的w都是0，那么function是一条水平线），平滑可以理解为当输入有扰动时，输出的变化是很小的（如下两个等式所示，当w小的时候，扰动对结果的影响小）。为什么更加平滑的模型可能是更好的呢？奥卡姆剃刀原理：如无必要，勿增实体。

$$y = b + \sum w_i x_i \longrightarrow y + \sum w_i \Delta x_i = b + \sum w_i (x_i + \Delta x_i)$$

Review: Gradient Descent

在机器学习的第三步，我们需要求解一个包含模型参数的最优化问题：
$$\theta^{*} = argmax_{\theta} \mathcal{L}(\theta)$$
假设$\theta = \{\theta_1, \theta_2\}$
$$\bigtriangledown L(\theta) =
\left[
\begin{matrix}
\frac{\partial L}{\partial \theta_1} \\
\frac{\partial L}{\partial \theta_2}
\end{matrix}
\right]
$$
梯度下降过程：
$$
\theta^1 = \theta^0 - \eta \bigtriangledown L(\theta^{0}) \\
\theta^2 = \theta^1 - \eta \bigtriangledown L(\theta^{1}) \\
\cdots
$$

Learning Rate

set the learning rate carefully.

Adaptive Learning Rate

Popular & Simple idea: reduce the learning rate by some factor every few epochs, e.g. $\eta^{t} = \frac{\eta}{\sqrt{t + 1}}$
But
learning rate cannot be one-size-fit-all, giving different parameters different learning is better !

Adagrad

每一个参数的learning rate除以该参数之前所有偏微分的平方和的开方。所以每一个参数的learning rate都是不同的。

Adagrad的计算过程

$$ w^1 = w^0 - \frac{\eta^0}{\sigma^0}g^{0} ,\ \sigma^0 = \sqrt{(g^0)^2} \\\ w^2 = w^1 - \frac{\eta^1}{\sigma^1}g^{1} ,\ \sigma^1 = \sqrt{\frac{1}{2}((g^0)^2+(g^1)^2)} \\\ w^3 = w^2 - \frac{\eta^2}{\sigma^2}g^{2} ,\ \sigma^2 = \sqrt{\frac{1}{3}((g^0)^2+(g^1)^2+(g^1)^2)} \\\ \cdots \\\ w^{t+1} = w^{t} - \frac{\eta^t}{\sigma^t}g^{t} ,\ \sigma^t = \sqrt{\frac{1}{t+1}\sum_{i}^{t}(g^i)^2} $$ where $$\eta^{t} = \frac{\eta}{\sqrt{t+1}}, g^{t} = \frac{\partial L(w^t)}{\partial w}$$

所以

$$w^{t+1} = w^{t} - \frac{\eta^t}{\sigma^t}g^{t} = w^{t} - \frac{\frac{\eta}{\sqrt{t+1}}}{\sqrt{\frac{1}{t+1}\sum_{i=0}^{t}(g^i)^2}}g^{t} = w^{t} - \frac{\eta}{\sqrt{\sum_{i=0}^{t}(g^i)^2}}g^{t}$$

Larger Gradient, Larger Step(why Adagrad work)?

在Adagrad的参数更新方法中，分母位置的$g^{t}$表明梯度越大，更新的步幅越大（梯度大，距离最优解远，更新的步幅应该大一点）；但是分子位置的$\sqrt{\sum_{i=0}^{t}(g^i)^2}$表明梯度越大，更新的步幅越小。这是不是有什么冲突的地方？

如上图，对于$x_0$来说，其最佳的更新步幅是$|x_0 + \frac{b}{2a}|$，这样可以直接得到最佳的解$-\frac{b}{2a}$，而$|x_0 + \frac{b}{2a}|$的分子$|2ax_0 + b|$正好是损失函数在$x_0$处的一阶微分，所以对于单变量的最优化问题来说，更新的步幅和微分的大小成正比是合理的（微分越大的点离最优解越远）。但这样的结论仅限于单变量问题，当存在多个变量的时候，并不是gradient的值越大，距离最优解越远。

图中c和a相比，$a$距离最优解更远，更新的步幅相比$c$而言应该更大才合理，但是$\text{gradient(c)}>\text{gradient(a)}$，显然$a$更新的慢。此时我们想到最佳的更新步幅$|x_0 + \frac{b}{2a}|$其分母$2a$正好是损失函数在$x_0$处的二阶微分，所以最好的步幅不仅仅要正比于一次微分，还要反比与二次微分。$\frac{\text{first derivative}}{\text{second derivation}}$的大小才能反映到最佳解的真实距离，所以
$${best step} = \frac{\text{first derivative}}{\text{second derivation}}$$

Adagrad算法正是利用了best step，并且采用类似在一次微分上进行采样的方式$\sqrt{\sum_{i=0}^{t}(g^i)^2}$近似了二次微分，如下图所示：

Stochastic Gradient Descent

Feature Scaling

Gradient Descent Theory

给定一个Loss function，我们无法一步确定最优的解，但是可以通过泰勒公式在一个很小的范围内找到使得Loss function最小的解，从而进行参数的更新，然后在新的邻域内再找使得Loss function最小的解。

• single variable
  $$h(x) = \sum_{0}^{\infty}\frac{h^{(k)}(x)}{k!}(x - x_0)^k = h(x_0) + h^{'}(x_0)(x - x_0) + \cdots$$
  当$x \rightarrow x_0$的时候，有
  $$h(x) \approx (x_0) + h^{'}(x_0)(x - x_0)$$
  

• multivariable taylor series
  $$h(x, y) = h(x_0, y_0) + \frac{\partial L(x_0, y_0)}{\partial x}(x - x_0) + \frac{\partial L(x_0, y_0)}{\partial y}(y - y_0) + \cdots$$
  当$(x, y)\rightarrow (x_0, y_0)$的时候，有
  $$h(x, y) \approx h(x_0, y_0) + \frac{\partial L(x_0, y_0)}{\partial x}(x - x_0) + \frac{\partial L(x_0, y_0)}{\partial y}(y - y_0)$$

Back to Formal Derivation

在足够小的红色邻域内，根据泰勒公式，有：
$$L(\theta) \approx L(a, b) + \frac{\partial L(a, b)}{\partial \theta_1}(\theta_1 - a) + \frac{\partial L(a, b)}{\partial \theta_2}(\theta_2 - b)$$

令:
$$u = \frac{\partial L(a, b)}{\partial \theta_1}, \ v = \frac{\partial L(a, b)}{\partial \theta_2}$$
$$L(\theta) \approx L(a, b) +u(\theta_1 - a) + v(\theta_2 - b) \tag1$$
使得$L(\theta)$最小的$(\theta_1, \theta_2)$满足（$L(a, b)$是常数，与$\theta$的取值无关）：
$$
\left[
\begin{matrix}
\theta_1 \\
\theta_2
\end{matrix}
\right]=
\left[
\begin{matrix}
a \\
b
\end{matrix}
\right]-\eta
\left[
\begin{matrix}
u \\
v
\end{matrix}
\right]
$$
因为当$\{\theta_1 - a, \theta_2 - b\}$与$\{u, v\}$的方向相反时$L(\theta)$的值最小，$\eta$表示邻域的半径。
这样我们就得到了梯度下降的公式（其中a，b为参数的初始值，$\eta$为learning rate）：
$$
\left[
\begin{matrix}
\theta_1 \\
\theta_2
\end{matrix}
\right]=
\left[
\begin{matrix}
a \\
b
\end{matrix}
\right]-\eta
\left[
\begin{matrix}
\frac{\partial L(a, b)}{\partial \theta_1} \\
\frac{\partial L(a, b)}{\partial \theta_2}
\end{matrix}
\right]
$$
上式成立的条件是在足够小的邻域中，所以learning rate在理论上是要无穷小的，但是实际操作中只要足够小就可以了。通过把泰勒公式中的二次项考虑进来理论上可以将learning rate设置的稍大一点，但是这样做通过得不偿失。

More Limitation of Gradient Gradient

where does the error come from?

• bias
• variance

Estimator

仍然以预测宝可梦进化之后的cp值为例，假设真实的函数为$\hat{f}$，从收集到的数据中我们可以得到$\hat{f}$的一个估计$f^{*}$。$f^{*}$和$\hat{f}$的差异来源于bias和variance。

Bias and Variance of Estimator

• 估计随机变量$x$的均值，假设其均值为$\mu$，方差为$\sigma^2$。随机采样$N$个点${x^1, x^2, \cdots, x^N}$，那么$m = \frac{1}{N}\sum_n x^{n} \ne \mu$，但是$E[m] = E\big[\frac{1}{N}\sum_n x^{n}\big]=\frac{1}{N}\sum_n E[x^n] = \mu$。所以$m$为$\mu$的无偏估计。$m$会均匀散布在$\mu$的周围，并且数据量越大，散布的越近。（variance的来源）
  

• 估计随便变量$x$的方差，$s^2 = \frac{1}{N}\sum_n (x^n - m)^2$，$E[s^2] = \frac{N-1}{N}\sigma^2$。所以$s^2$是$\sigma^2$的有偏估计(biased estimator)。（bias的来源）
  

Bias v.s. Variance

如下图（第四个）所示，$f^{*}$和$\hat{f}$之间的差距来源于两个地方：

• 有没有瞄准，或者说estimator是不是有偏的。因为$E[f^{*}]=\bar{f}\ne\hat{f}$，所以是有偏的。这会导致Bias，$\bar{f}$和$\hat{f}$的差距。
• 有没有射准。这会导致Variance，$\bar{f}$和$\hat{f}$的差距。

Parallel Universes(different training data)

• different model
  

• Variance
  
  如上图：复杂的model有更多的variance，怎么解释呢？简单的model比较不会受到data的影响，考虑一种极端的情况，最简单的model可以是一个常数的输出，那么不管什么样的数据喂到这样的模型中，输出都是一样的，所以variance为0.

• Bias
  bias衡量的是$E[f^{*}]=\bar{f}$到$\hat{f}$的差异，但是$\hat{f}$是未知的，这里假设一个，并从假设的模型中进行数据的采样。
  
  
  为什么会出现这种情况呢？一个简单的model，或者说是function set，它的space是比较小的，可能最优的解并不能被包含在这么小的space中；但是复杂的model由于其space很大所以可以包含最优的$\hat{f}$，同时由于它的space很大，所以会很散，这时候就有比较大的variance.

What to do

• Diagnosis

  • if your model cannot even fit the training examples, then you have a large bias.
  • if you can fit the training data, but large error on testing data, probably have a large variance.

• For bias

  • redesign your model
    • add more feature
    • a more complex model

• For variance

  • more data
    
  • regularization: reduce variance, while increase bias due to more small space.
    

Cross Validation

N-fold Cross Validation

人工智能是目标，机器学习是手段，深度学习是机器学习其中的一种方法。

Machine Learning = looking for a function from data.

机器学习的framework

• 定义模型（define a set of functions）
• 定义衡量方法好坏的标准（goodness of function）
• 从数据中利用算法找出最好的$f^*$（pick the best function）

supervised learning v.s. reinforcement learning

• learning from teacher
• learning from critics

Three Steps for Deep Learning

• Step 1: define a set of functions(Neural Network)
• Step 2: goodness of functions
• Step 3: pick the best function

Step 1: Neural Network

神经元不同的连接方式会导致不同的网络结构，即不同的function set。当固定了神经网络的架构，那么就定义了function set。

• Fully Connected Network
  相邻两层之间的神经元都有连边的神经网络成为全连接神经网络。
  

• Matrix Operation
  

• Neural Network
  

Deep learning将问题从如何抽取feature转换为如何设计好的神经网络结构。

Step 2: Loss for Training Data

• loss for an Example
  

• loss for Total
  

Step 3: Gradient Descent

Step 1: Function Set

对于二分类问题，我们想要找一个posterior probability: $P(C_1|x)$，如果$P(C_1|x) \gt 0.5$，那么类别为$C_1$；如果$P(C_1|x) \lt 0.5$，那么类别为$C_2$。通过计算$\mu_1,\mu_2,\Sigma$我们可以得到：

$$P(C_1|x) = \sigma(z)$$

其中：
$$ \sigma(z) = \frac{1}{1 + exp(-z)}, z = wx + b$$

Function Set:
$$f_{w, b}(x) = P_{w, b}(C_1|x)$$
including all different w and b.

Step 2: Goodness of a Function

对于N笔training data，$\{(x^1, C_1),(x^2, C_1),(x^3, C_2),\cdots,(x^N, C_1)\}$，假设这些data是由我们所定义的posterior probability所产生的，那么某一组$(w, b)$产生training data的几率为：

$$L(w, b) = f_{w, b}(x^1)f_{w, b}(x^2)\big(1 - f_{w, b}(x^3)\big)\cdots f_{w, b}(x^N)$$

$$w^{*}, b^{*} = argmax_{w, b} L(w, b)$$

等同于

$$w^{*}, b^{*} = argmin_{w, b} -ln L(w, b)$$

$$ \begin{align} -ln L(w, b) &= -ln f_{w, b}(x^1)f_{w, b}(x^2)\big(1 - f_{w, b}(x^3)\big)\cdots f_{w, b}(x^N)\\\ & = -ln f_{w, b}(x^1) - ln f_{w, b}(x^2) -ln (1 - f_{w, b}(x^3)) - \cdots - ln f_{w, b}(x^N) \end{align} $$

设定$C_1$对应的label为1，即$\hat{y} = 1$；$C_2$对应的label为0，即$\hat{y}=0$，这样
$$ln f_{w, b}(x^n) = \hat{y}^n ln f(x^n) + (1 - \hat{y}^n)ln(1 - f(x^n))$$

$$w^{*}, b^{*} = argmin_{w, b} \sum_{n}^{N} -[\hat{y}^n ln f(x^n) + (1 - \hat{y}^n)ln(1 - f(x^n))]$$

其中：$-[\hat{y}^n ln f(x^n) + (1 - \hat{y}^n)ln(1 - f(x^n))]$是两个伯努利分布的cross entropy。

p分布：$p(x=1) = \hat{y}^n, p(x=0) = 1 - \hat{y}^n$
q分布：$q(x=1) = f(x^n), q(x=0) = 1 - f(x^n)$
p和q的交叉熵：$H(p, q) = -\sum_x p(x)lnq(x)$

$$J(w, b) = \sum_{n}^{N} -[\hat{y}^n ln f(x^n) + (1 - \hat{y}^n)ln(1 - f(x^n))] = \sum_{n}^{M}C(f(x^n), \hat{y}^n)$$

Step 3: Find the best function

$$\frac{\partial J(w, b)}{\partial w_i} = \sum_{n}^{N}-[\hat{y}^n\frac{1}{\sigma(z^n)}\frac{\partial \sigma(z^n)}{\partial w_i} - (1 - \hat{y}^n)(\frac{1}{1 - \sigma(z^n)})\frac{\partial \sigma(z^n)}{\partial w_i}]$$

$$\frac{\partial\sigma(z^n)}{\partial w_i} = \frac{\partial\sigma(z^n)}{\partial z^n}\frac{\partial z^n}{\partial w_i} = \sigma(z^n)(1 - \sigma(z^n))x_i$$

$$ \begin{align} \frac{\partial J(w, b)}{\partial w_i} &= \sum_{n}^{N}-[\hat{y}^n(1 - \sigma(z^n))x_i - (1 - \hat{y}^n)\sigma(z^n)x_i]\\\ & = \sum_{n}^{N}-[\hat{y}^n - \hat{y}^n\sigma(z^n) - \sigma(z^n) + \hat{y}^n\sigma(z^n) ]x_i\\\ & = \sum_{n}^{N}-(\hat{y}^n - \sigma(z^n))x_i \\\ & = \sum_{n}^{N}-(\hat{y}^n - f_{w, b}(x^n))x_i \\\ \end{align} $$

$$w_i = w_i - \eta\sum_{n}^{N}-(\hat{y}^n - f_{w, b}(x^n))x_i $$

why not logistic regression + square error

如果logistic regression使用mean square error的话，cost function如下：

$$J(w, b) = \frac{1}{2}\sum_{n}^{N}(f_{w, b}(x^n) - \hat{y}^n)^2$$

此时：
$$\frac{\partial (f_{w, b}(x^n) - \hat{y}^n)^2}{\partial w_i} = 2(f_{w, b}(x^n) - \hat{y}^n)\frac{\partial f_{w, b}(x^n)}{\partial z}\frac{\partial z}{\partial x} = 2(f_{w, b}(x^n) - \hat{y}^n)f_{w, b}(x^n)(1 - f_{w, b}(x^n))x_i$$

当$\hat{y}^n = 1$：

• 如果$f_{w, b}(x^n) = 1$，说明模型已经学习的很好了，通过上式计算得到$\frac{\partial L}{\partial w}=0$， 这是合理的。
• 如果$f_{w, b}(x^n) = 0$，说明模型还差很远，但是此时$\frac{\partial L}{\partial w}$仍然等于0，这是不合理的。

当$\hat{y}^n = 0$的时候存在同样的问题。所以如果在logistic regression中使用square error，在距离目标值很近的时候，梯度很小，这是合理的；但是在距离目标值很远的地方，梯度也很小，这将会使得学习变得很困难。但是如果使用cross entropy，在距离目标值很远的地方，梯度很大（因为正比于$\hat{y}^n - f_{w, b}(x^n)$）.

1 - Why CNN for Image?

• Some patterns are much smaller than the whole image. A neurons does not to have to see the whole image to discover the pattern. connecting to small region with less parameters is enough.
• The some patterns appear in different regions.
• Sub-sampling the pixels will not change the object, so we can sample the pixel to make the image smaller, so that less parameters for the network to process the image.

1.1 - Convolution

Conv Net是Fully Connected Net的特例，可以将卷积神经网络的function set space看成是全连接网络的function set space的子集，已经去掉了那些明显不合理的functions。

1.2 - CNN for colorful image

The number of channels in filter is equal to the number of channels of the input.

1.3 - FC Net v.s. Conv Net

• sparse connected -> less parameters
  

• shared parameters -> ever less parameters
  

1.4 - Pooling Layer

• max pooling
• average pooling

1.5 - FC Layer

2 - What does machine learning?

2.1 - looking filters on the trained first layer

查看第一层的卷积核是有意义的，因为它的输入是图像，但从第二层开始，其filter的训练是基于前一层filter的输出，所以很难分析。以下是AlexNet的第一层11*11的卷积核。

2.2 - other methods

假设我们已经在MNist数据上训练了一个神经网络（部分结构如下），如果我们想要分析第2层的第k个filter学到了什么，我们可以尝试通过如下的方式得到：

第2层的第k个filter的输出为一个11$\times$11的matrix，定义

$$a^k = \sum_{i=1}^{11}\sum_{j=1}^{11}a_{ij}^{k}$$

我们想要做的是找一个$x^*$（x.shape=(28,28)），使得

$$x^* = arg max_x a^k$$

也就是通过求解一个最优化的问题来找到使得$a^k$最大的输入$x$，同样也是使用gradient descent（$\frac{\partial a^k}{\partial x_{ij}}$）。

实际求解得到的结果如下（前12个）：

• 该方法同样可以用于分析fully connected layer中的neuron：
  

• 同样将该方法用于最后一层中的neuron，得到能够使得最后一层中各个神经元得到最大激活值的输入分别如下图所示，并不是我们算想象的数字的形状
  

通过这样的结果一方面我们可以认为神经网络学习得到的模型很容易别欺骗，因为一张在我们看来完全是噪声的图片被模型非常confident的识别为某一个数字。另一方面我们可以认为神经网络并不是仅仅把它所看到的的东西记住，而是通过某种方式进行了学习。

在上面的问题中通过在目标函数中加入一些constrain可以得到更好的结果。

$$x^* = arg max_x \big(y^i + \sum_{i, j}|x_{ij}|\big)$$

3 - Analysis

通过计算模型的输出$y_k$对每一个像素$x_{ij}$的偏微分$\frac{\partial y_k}{\partial x_{ij}}$，可以得到该像素对识别该类的重要性，以下是一些结果，亮度越大说明越重要：

也可以通过对区域进行遮挡来进行相似的分析，下图越蓝的地方表示当该区域被遮挡之后，对识别的影响越大：

Probabilistic Generative Model

classification：

• credit scoring
• medical diagnosis
• handwritten character recognition
• face recognition

Example Application

任务：根据宝可梦的属性，预测宝可梦的类别。

How to do Classification?

• Training data for Classification
  将编号400以下的作为训练集，400以后的作为测试集，训练模型来预测以后产生的宝可梦的类别。

• Classification as Regression for binary task?
  可以利用回归模型来解决二类分类问题吗？将类别1的target value设定为1；将类别2的target value设定为-1，在这样的数据上训练一个regression模型。在测试阶段，如果output大于0，那么为类别1；如果output小于0，那么为类别2。
  这并不是一个好的做法：对于下图左边的数据似乎是没有什么问题的，但是如果数据的分布如下图右，那么一个好的classifier应该如绿线所示，但是利用regression model得到的结果会如蓝线所示，因为在regression model看来，右下角的那些蓝色数据点不是confidence很高的、被正确划分的样本点（在classification model看来是这样），反而是error，因为对于这些点，回归模型计算得target value远远大于1，这会使得mean square error变大。从而regression model会将分类边界从绿线偏向蓝线以获得更小的error，而这显然不是一个好的结果。
  penalize to the examples that are too correct.
  另外对于多分类问题，如果也当做regression task来做的话，其类标签之间会被隐式的添加不存在距离关系。
  

Ideal Alternatives

loss function不是可微分的，所以不可以用gradient descent来进行求解，但是SVM，感知器可以用于解决这类问题。

Two Boxs

随机抽取一个篮球，来自盒子1的概率$P(B_1|Blue)$的计算公式如下：
$$P(B_1|\text{Blue}) = \frac{P(B_1)P(\text{Blue}|B_1)}{P(B_1)P(\text{Blue}|B_1) + P(B_2)P(\text{Blue}|B_2)}$$

Two Class

对于给定的x，其属于类别1的概率：
$$P(C_1|x) = \frac{P(C_1)P(x|C_1)}{P(C_1)P(x|C_1) + P(C_2)P(x|C_2)}$$
这样的模型称为$\text{generative model}$，因为我们可以知道某一个x产生的概率：
$$P(x) = P(C_1)P(x|C_1) + P(C_2)P(x|C_2)$$

要计算$P(C_1|x)$，需要知道的有prior probability：$P(C_1), P(C_2)$，还有probability from class：$P(x|C_1), P(x|C_2)$。

Prior Probability

在这个二分类问题中，id小于400的水系和一般系宝可梦为训练集，id大于400的水系和一般系为测试集。
Training set: 79 water(class 1);61 normal(class 2)
$$P(C_1) = \frac{79}{79 + 61} = 0.56, P(C_2) = \frac{61}{79 + 61}=0.44$$

Class Probability Distribution

$$P(x|C_1) = ?$$

如果此时的x不存在于training set中，那么$P(x|C_1)$的概率等于0吗？显然不是的。事实上，我们假设这些样本点（水系宝可梦的攻击力值和特殊攻击力值，如下图所示），是从某个特定的高斯分布中抽样出来的。所以每一个x存在的可能性都不为0.

Gaussian Distribution

$$f_{\mu, \Sigma}(x) = \frac{1}{(2\pi)^{D/2}}\frac{1}{|\Sigma|^{1/2}}exp{\big(-\frac{1}{2}(x-\mu)^{T}\Sigma^{-1}(x-\mu)\big)} \tag1$$

如果可以找到描述这个高斯分布的$\mu$和$\Sigma$，那么对于任意一个样本点，都可以根据（1）计算其产生的可能性。求解$\mu$和$\Sigma$的方法称为$\text{maximum likelihood}$。

maximum likelihood

任何的高斯分布（左边正圆表示的高斯分布或者右边斜椭圆表示的高斯分布）都可能sampling到上图中的79个样本点，但是这些高斯分布sampling出这些样本点的可能性大小是不同的。使用似然函数可以描述这种可能性的大小：

$$L(\mu,\Sigma) = f_{\mu, \Sigma}(x^{1})f_{\mu, \Sigma}(x^{2})\cdots f_{\mu, \Sigma}(x^{79})$$

能够使得上式最大的$\mu, \Sigma$所决定的高斯分布就是我们想要的可以用来描述$C_1$类的高斯分布。

$$\mu^{*}, \Sigma^{*} = arg max_{\mu, \Sigma} L(\mu,\Sigma) $$

经过计算（求微分使之为0）得到最佳的$\mu^{*}, \Sigma^{*}$满足：

$$\mu^{*} = \frac{1}{79}\sum_{n=1}^{79}x^n$$ $$\Sigma^{*} = \frac{1}{79}\sum_{n=1}^{79}(x^n- \mu^{*})(x^n- \mu^{*})^T$$

经过计算，最有可能抽样出这79只宝可梦的高斯分布的$\mu, \Sigma$为：

$$ \mu = \begin{bmatrix} 75.0 \\\ 71.3 \end{bmatrix} , \Sigma= \begin{bmatrix} 874 & 327 \\\ 327 & 929 \end{bmatrix} $$

Now we can classification

---

Modifying Model

对于上述问题，比较常见的做法是不同的class可以共享一个$\Sigma$，因为$\Sigma$中参数的个数是和feature size的平方成正比的，所以减少参数的个数可以降低模型的复杂度，减少variance。

其均值向量和协方差矩阵的求解方法如下：

其结果如下，可以看到，当共用$\Sigma$之后，我们的得到了一个线性的分类器，并且在使用了所有的7个特征之后，分类的准确率上升到73%。

Three Steps of ML

• function set(model):
  $$P(C_1|x) = \frac{P(C_1)P(x|C_1)}{P(C_1)P(x|C_1) + P(C_2)P(x|C_2)}, \text{if }P(C_1|x) > 0.5, \text{output: class 1}$$
• Goodness of a function:
  the mean and covariance that maximizing the likelihood (the probability of generating data)
• Find the best function: easy

Naive Bayes Classifier

如果我们假设feature中不同的维度是由不同的一维高斯分布所独立产生的，这样就得到朴素贝叶斯模型：
$$P(x|C_1) = P(x_1|C_1)P(x_2|C_1)\cdots P(x_n|C_1)$$

---

Posterior Probability

$$ \begin{align} P(C_1|x) &= \frac{P(C_1)P(x|C_1)}{P(C_1)P(x|C_1)+P(C_2)P(x|C_2)} \\\ & = \frac{1}{1 + \frac{P(C_2)P(x|C_2)}{P(C_1)P(x|C_1)}} \\\ & = \frac{1}{1 + exp(-z)} \\\ & = \sigma(z) \end{align} $$ 其中，令： $$z = ln\frac{P(C_1)P(x|C_1)}{P(C_2)P(x|C_2)}$$

$$P(C_1|x) = \sigma(z)$$

下来我们来看看$z$是什么？

$$ \begin{align} z & = ln\frac{P(C_1)P(x|C_1)}{P(C_2)P(x|C_2)} \\\ & = ln{\frac{P(x|C_1)}{P(x|C_2)}} + ln{\frac{P(C_1)}{P(C_2)}} \\\ & = ln{\frac{P(x|C_1)}{P(x|C_2)}} + ln(\frac{\frac{N_1}{N_1 + N_2}}{\frac{N_2}{N_1 + N_2}}) \\\ & = ln{\frac{P(x|C_1)}{P(x|C_2)}} + ln{\frac{N_1}{N_2}} \\\ & = ln\big(\frac{\frac{1}{(2\pi)^{D/2}}\frac{1}{|\Sigma^1|^{1/2}}exp{\big(-\frac{1}{2}(x-\mu^1)^{T}(\Sigma^{1})^{-1}(x-\mu^1)\big)}}{\frac{1}{(2\pi)^{D/2}}\frac{1}{|\Sigma^2|^{1/2}}exp{\big(-\frac{1}{2}(x-\mu^2)^{T}(\Sigma^{2})^{-1}(x-\mu^2)\big)}}\big) \\\ & = ln(\frac{|\Sigma^2|^{1/2}}{|\Sigma^1|^{1/2}}exp\{-\frac{1}{2}[(x-\mu^1)^{T}(\Sigma^{1})^{-1}(x-\mu^1)-(x-\mu^2)^{T}(\Sigma^{2})^{-1}(x-\mu^2)]\}) \\\ & = ln\frac{|\Sigma^2|^{1/2}}{|\Sigma^1|^{1/2}}-\frac{1}{2}[(x-\mu^1)^{T}(\Sigma^{1})^{-1}(x-\mu^1)-(x-\mu^2)^{T}(\Sigma^{2})^{-1}(x-\mu^2)] \\\ \end{align} $$

$$ \begin{align} (x - \mu^1)^T(\Sigma^1)^{-1}(x - \mu^1) & = x^T(\Sigma^1)^{-1}x - x^T(\Sigma^1)^{-1}\mu^1 - (\mu^1)^T(\Sigma^1)^{-1}x + (\mu^1)^T(\Sigma^1)^{-1}\mu^1\\\ & = x^T(\Sigma^1)^{-1}x - 2(\mu^1)^T(\Sigma^1)^{-1}x + (\mu^1)^T(\Sigma^1)^{-1}\mu^1 \\\ \end{align} $$

$$ \begin{align} z &= ln\frac{|\Sigma^2|^{1/2}}{|\Sigma^1|^{1/2}} - \frac{1}{2}x^T(\Sigma^1)^{-1}x + (\mu^1)^T(\Sigma^1)^{-1}x - \frac{1}{2}(\mu^1)^T(\Sigma^1)^{-1}\mu^1 + \frac{1}{2}x^T(\Sigma^2)^{-1}x - (\mu^2)^T(\Sigma^2)^{-1}x + \frac{1}{2}(\mu^2)^T(\Sigma^2)^{-1}\mu^2 - ln\frac{N_1}{N_2}\\\ & = (\mu_1 - \mu_2)^T\Sigma^{-1}x - \frac{1}{2}(\mu^1)^T(\Sigma^1)^{-1}\mu^1 + \frac{1}{2}(\mu^2)^T(\Sigma^2)^{-1}\mu^{2} + ln\frac{N_1}{N_2} \\\ \end{align} $$

令

$$w^T = (\mu_1 - \mu_2)^T\Sigma^{-1}$$ $$b = - \frac{1}{2}(\mu^1)^T(\Sigma^1)^{-1}\mu^1 + \frac{1}{2}(\mu^2)^T(\Sigma^2)^{-1}\mu^{2} + ln\frac{N_1}{N_2}$$

那么$z = w^T x + b$

因为posterior probability可以表示成：$P(C_1|x) = \sigma(z)$
所以
$$P(C_1|x) = \sigma(w^Tx + b)$$
这就解释了为什么当$\Sigma^1=\Sigma^2$的时候，classifier boundary是linear的。

在generative model中，我们需要从训练数据中计算出$N_1, N_2, \mu^1, \mu^2, \Sigma$，然后计算$w$和$b$，就可以计算$P(C_1|x)$。为什么我们不直接从数据中学习$w$和$b$呢，直接求解$w$和$b$的方法就是$\text{logistic regression}$。

Recipe for Deep Learning

bad performance do not always blame overfitting. 下图所示并不是overfitting，因为在training set上，56-layer的结果就比20-layer的结果差，为什么在56-layer上的结果会比在20-layer上的结果差呢？

Improve Performance on Training Set

1 - Activation Function

当layer越多的时候，一般结构的神经网络并不能保证在training set上的结果一定会变好。这主要是源于Vanishing Gradient Descent：接近input layer的那些层的gradient比较小，而接近output layer的那些层的gradient比较大；当整个network的learning rate都一样的话，前面那几层的参数学习的较慢，后面那几层的参数学习较快；这样的话，前面那几层的的参数还几乎是随机的时候，后面的参数已经收敛了，但是此时并不能得到好的结果，因为后面收敛的参数是基于前面随机的参数学习而来的。

这个现象的来源是sigmoid function。

为什么前面层参数的gradient比较小，而后面层参数的gradient比较大呢？（通过观察参数改变$\Delta w$时loss改变的大小$\Delta l$，可以用来估算该参数的gradient，而不必使用back propagation来计算）。

从下图可以看到，sigmoid函数会将输入的改变缩小。

从下图可以看到，越位于前面的参数其$\Delta w$所带来的$\Delta l$越小，故其gradient越小。

1.1 - ReLU

• fast to compute
• biological reason
• infinite sigmoid with different bias
• handle the problem of vanishing gradient descent

为什么ReLU可以避免梯度弥散呢？ReLU有两个operation range：当输入小于0时，输出为0；当输入大于0时，此时ReLU退化为一个线性的激活函数。那么对于某一个输入来说，神经网络会变为一个参数更少的线性的神经网络（一些neuron的activation function变为linear activation function；另一些neuron的activation function的输出为0，即失效），此时便不会再有vanishing gradient descent的问题（因为没有sigmoid activation function）：

需要注意的是这样的神经网络并不是线性的，当输入只有很小的变动时，或许ReLU的opertation range没有改变；但是当输入变化超过一定范围的时候，改变了neuron的operation range的时候，从整体来看就不是线性的了。

1.2 - ReLU - variant

1.3 - Maxout

让神经网络自己学习每一个neuron的激活函数的方法叫做$Maxout$。以下会看到ReLU是Maxout的一个特例。

Maxout的网络结构如下：

ReLU激活函数$a$和$x$之间的关系如下：
$$a = relu(z), z = wx + b$$

Maxout可以通过学习的方式来得到激活函数ReLU：

如上图所示，case 1可以自动学习得到ReLU函数；case 2可以学习得到另一种激活函数。所以Maxout可以从训练数据中自动的学习到最合适的激活函数。激活函数的大致形状取决于将几个neuron放在一起取最大值。

Maxout network的训练过程实际上是一个linear neural network的训练的过程，所以可以计算back propagation。

2 - Adaptive Learning Rate

2.1 - Adagrad

$$w^{t+1} = w^{t} - \eta\frac{g^{t}}{\sqrt{\sum_{i=0}^{t}(g^t)^2}}, \text{ where } g^{t} = \frac{\partial L}{\partial w^t}$$

其基本的**是使用一次微分来估算二次微分。

2.2 - RMSProp(variant of Adagrad)

$$w^{t+1} = w^{t} - \eta\frac{g^{t}}{\sigma^{t}}, \text{ where } \sigma^{t} = \sqrt{\alpha(\sigma^{t-1})^2 + (1 - \alpha)(g^t)^2}$$

2.3 - Momentum

在优化过程中会有很多gradient为0的地方（local minima，plateau，saddle point），这是导致优化结果不好的主要原因。

Momentum优化算法的基本**是将惯性加入gradient descent中，希望可以利用惯性冲出某些梯度为0的地区，如下图：

• 一般的gradient descent的过程如下：
  
  $$\theta^{t+1} = \theta^{t} - \eta \nabla L(\theta^{t})$$
• gradient descent with momentum的过程如下：
  

$$ \begin{align*} v^{0} = 0 \\\ v^{t+1} = \lambda v^{t} - \eta \nabla L(\theta^{t}) \\\ \theta^{t+1} = \theta^{t} + v^{t+1} \end{align*} $$

$$ \begin{align*} v^1 = -\eta \nabla L(\theta^{0}), \\\ v^2 = \lambda (-\eta \nabla L(\theta^{0})) - \eta \nabla L(\theta^{1}), \\\ v^3 = \lambda \{\lambda (-\eta \nabla L(\theta^{0})) - \eta \nabla L(\theta^{1})\} - \eta \nabla L(\theta^{2})\\\ ... \end{align*} $$

2.4 - Adam

$$\text{Adam = Momentum + RMSProp}$$

1 - Chain Rule

• case 1：
  $$y = g(x), z = h(y) \longrightarrow \frac{dz}{dx} = \frac{dz}{dy}\frac{dy}{dx}$$

• case 2：
  $$x = g(x), y = h(s), z = k(x, y) \longrightarrow \frac{dz}{ds} = \frac{\partial z}{\partial x}\frac{dx}{ds} + \frac{\partial z}{\partial y}\frac{dy}{ds}$$

2 - BackPropagation

因为总的损失是各个样本损失的和：$L(\theta) = \sum_{n=1}^{N}l^n(\theta)$，所以总的损失对参数的偏导是各个样本上损失对参数偏导的求和：
$$\frac{\partial L(\theta)}{\partial w}=\sum_{n=1}^{N}\frac{\partial l^n(\theta)}{\partial w}$$

如下图：
$$\frac{\partial l}{\partial w} = \frac{\partial l}{\partial z}\frac{\partial z}{\partial w}$$
其中

• 在forward pass中计算$\frac{\partial z}{\partial w}$
• 在backward pass中计算$\frac{\partial l}{\partial z}$

2.1 - Forward pass

$$\frac{\partial z}{\partial w_1} = x_1, \frac{\partial z}{\partial w_2} = x_2$$

2.2 - Backward pass

$$\frac{\partial l}{\partial z} = ?$$

$$\frac{\partial l}{\partial z} = \frac{\partial l}{\partial a}\frac{\partial a}{\partial z}$$

$$\frac{\partial l}{\partial a} = \frac{\partial z'}{\partial a}\frac{\partial l}{\partial z'} + \frac{\partial z''}{\partial a}\frac{\partial l}{\partial z''} =w_3 \frac{\partial l}{\partial z'} + w_4 \frac{\partial l}{\partial z''}$$

假设：$\frac{\partial l}{\partial z'}$和$\frac{\partial l}{\partial z''}$是已知的，那么$\frac{\partial l}{\partial z}$的计算公式如下以及下图所示：

$$\frac{\partial l}{\partial z} = \frac{\partial a}{\partial z}[w_3 \frac{\partial l}{\partial z'} + w_4 \frac{\partial l}{\partial z''}] = \sigma'(z)[w_3 \frac{\partial l}{\partial z'} + w_4 \frac{\partial l}{\partial z''}]$$

上面的计算基于$\frac{\partial l}{\partial z'}$和$\frac{\partial l}{\partial z''}$是已知的，那么$\frac{\partial l}{\partial z'}$和$\frac{\partial l}{\partial z''}$如何计算呢？

• case 1：
  如果$z'$和$z''$是输出层神经元的输入，那么问题就结束了。
  
  $$\frac{\partial l}{\partial z'} = \frac{\partial y_1}{\partial z'} \frac{\partial l}{\partial y_1}, \frac{\partial l}{\partial z''} = \frac{\partial y_2}{\partial z''} \frac{\partial l}{\partial y_2}$$

• case 2：
  如果$z'$和$z''$不是输出层神经元的输入，从最后一层反向计算$\frac{\partial l}{\partial z}$
  

3 - Summary