3. Regression : Output a scalar

如果找到的function输出的是数值，这样的任务就叫做Regression，例如Stock Market Forecast，Self-driving Car，Recommendation。

• 问题：预测宝可梦的CP值

  Estimating the Combat Power(CP) of a pokemon after evolution

  我们期望根据已有的宝可梦进化前后的信息x，来预测某只宝可梦进化后的cp值的大小y

  设定具体参数
  X： 表示一只宝可梦，用下标表示该宝可梦的某种属性

  X_cp ：表示该宝可梦进化前的cp值

  X _s ： 表示该宝可梦是属于哪一种物种，比如妙瓜种子、皮卡丘…

  X _hp ：表示该宝可梦的hp值即生命值是多少

  X_w： 代表该宝可梦的重量

  X _h： 代表该宝可梦的高度

  f ( )： 表示我们要找的function

  y： 表示function的output，即宝可梦进化后的cp值，是一个scalar

  

我们要做的就是找出这样期望的function。

回顾一下machine Learning的三个步骤：

• 定义一个model即function set
• 定义一个goodness of function损失函数去评估该function的好坏
• 找一个最好的function

Step1:Model(function set)

可以先假设进化后的cp值与进化前的cp值有很大关系，即假设function set里面的function中y与x有y = b + w * X_cp的关系（w和b就称为模型的参数，can be any value）。

由于w和b可以取任意值，所以现在的function set里面有无穷个function（这些function里面当然有合理的，也有不合理的如f₃）。

实际上这是一种Linear Model，但只考虑了宝可梦进化前的cp值，因而我们可以将其扩展为：

Linear Model：

\[y=b+\sum w_ix_i \]

x_i： an attribute of input X ( x_i is also called feature，即特征值)

w_i：weight of x_i

b： bias

Step2:Goodness of Function

让model有办法衡量某个function是好还是不好。

做法：

1.收集一些训练的资料（Training Data），训练的资料要告诉机器这个input和output之间的对应关系。

参数说明
\(x^i\) ：用上标来表示一个完整的object的编号，表\(x^i\)示第i只宝可梦(下标表示该object中的component)；

\(\hat{y}^i\)：用y表示一个实际观察到的object输出，上标为i表示是第i个object；

注：由于regression的输出值是scalar，因此y里面并没有component，只是一个简单的数值；但是未来如果考虑structured Learning的时候，我们output的object可能是有structured的，所以我们还是会需要用上标下标来表示一个完整的output的object和它包含的component。

Loss Function（损失函数）

Loss Function（input ：model里的function，output ：how bad/good it is），是一个function的function，简称L(f)，来衡量input的function多好或者多不好，实际上是在衡量一组参数w和b的好坏，所以也可以写成L(w,b)。

之前提到的model是由我们自主选择的，这里的Loss Function也是.

最常用的方法就是采用类似于方差和的形式来衡量参数的好坏，即预测值与真值差的平方和；这里真正的数值减估测数值的平方，叫做估测误差**，Estimation error，将10个估测误差合起来就是loss function。

\[L(f)=\sum^{10}_{n=1}(\hat y^n-f(x^n_{cp}))^2 \]

\[L(w,b)=\sum^{10}_{n=1}(\hat y^n-(b+w*x^n_{cp}))^2 \]

Loss function可视化

上图是Loss Function的可视化，该图中的每一个点都代表一组(w,b)，也就是对应着一个function；而该点的颜色对应着Loss Function的结果L(w,b)。

颜色越偏红色代表Loss Function的数值越大，这个function的表现越不好，越偏蓝色代表Loss Function的数值越小，这个function的表现越好。比如图中用红色箭头标注的点就代表了b=-180 , \(w=-2\)对应的function，即\(y = ? 180 ? 2 *x_{cp}\)。该点所在的颜色偏向于红色区域，因此这个function的loss比较大，表现并不好。

Step3：Pick the Best Function
我们已经确定了Loss Function，它可以衡量我们的Model里面每一个function的好坏，接下来我们要做的就是，从这个function set里面，挑选一个最好的function。

挑选最好的function这一件事情，写成formulation/equation的样子如下：

\[f^*=arg \min_{f}L(f) \]

或者

\[w*，b*=arg \min_{w，b}L(w，b) =arg \min_{w，b}\sum^{10}_{n=1}(\hat y^n-(b+w*x^n_{cp}))^2 \]

即，使\(L(f)=L(w,b)=Loss\)最小的\(f\)或\(( w , b )\) ，就是我们要找的\(f^*\) 或者\((w^*,b^*)\)(有点像极大似然估计的思想)。

利用线性代数的知识，可以解得这个closed-form solution，但这里采用的是一种更为普遍的方法——Gradient Descent(梯度下降法)。

Gradient Descent(梯度下降法)

对于更普遍的问题来说，Gradient Descent的厉害之处在于，只要\(L(f)\)是可微分的，Gradient Descent都可以拿来处理这个\(f\)，从而找到表现比较好的parameters。

单个参数的问题
考虑带单个参数\(w\)的Loss Function的\(L(w)\)为例，首先保证\(L(w)\)是可微的。我们的目标就是找到最好的function，即找到满足下式的\(w^*\):

\[w^*=arg\min_{w}L(w) \]

\(w\)的变化画图如下：

想要找到\(w^*\),有一个暴力的方法是穷举所有的w值，从而找到使Loss最小的\(w^*\)。

而更有效率的方法就是用Gradient Descent。

Gradient Descent的做法如下：

1.随机选取一个初始的点\(w_0\) (当然也不一定要随机选取，如果有办法可以得到比较接近\(w^*\)的表现得比较好的\(w^0\) 当初始点，可以有效地提高查找 \(w^*\)的效率)

2.计算\(L\)在\(w=w^0\)的位置的微分，即\(\frac{d L}{d w}|_{w=w^0}\),几何意义就是切线的斜率。

如果切线斜率是negative负的，那么就应该使\(w\)变大，即往右踏一步；

如果切线斜率是positive正的，那么就应该使\(w\)变小，即往左踏一步;

(每一步的步长step size就是\(w\)的改变量)

\(w\)的改变量step size的大小取决于两件事:

• 一是现在的微分值\(\frac{d L}{d w}\)有多大，微分值越大表示图像在一个越陡峭的地方，那它要移动的距离就越大，反之就越小；

• 二是一个常数项\(\eta\)，被称为Learning Rate，即学习率，它决定了每次踏出的step size不只取决于现在的斜率，还取决于一个事先就定好的数值。如果Learning Rate比较大，那每踏出一步的时候，参数\(w\)更新的幅度就比较大，反之参数更新的幅度就比较小。(如果Learning Rate设置的大一些，那机器学习的速度就会比较快；但是Learning Rate如果太大，可能就会跳过最合适的global minima的点。)

计每次参数更新的大小是\(\eta\frac{d L}{d w}\),为了满足斜率为负时\(w\)变大，斜率为正时\(w\)变小，应当使原来的\(w\)减去更新的数值，即

\[\begin{aligned} w^1&=w^0-\eta\frac{d L}{d w}|_{w=w^0}\\ w^2&=w^1-\eta\frac{d L}{d w}|_{w=w^1}\\ w^3&=w^2-\eta\frac{d L}{d w}|_{w=w^2}\\ ...\\ w^{i+1}&=w^i-\eta\frac{d L}{d w}|_{w=w^i}\\ \end{aligned} \]

\[if(\frac{d L}{d w}|_{w=w^i}==0)\ then\ stop; \]

当\(L(w)\)对应的斜率为0，我们找到了一个极小值Local minima。

但这就出现了一个问题，当找到一个Local minima的时候，微分为0，参数就会一直卡在这个点上没有办法再继续更新了，因此通过Gradient Descent找到的solution其实并不是最佳解Global minima。（这就是看人品的时候了！）

但幸运的是，在Linear Regression上，是没有Local minima的，因此不用担心solution不是最优解。

两个参数的问题

Gradient Descent的做法如下：

1.随机选取一个初始的点\(w_0\) 和\(b_0\)；

2.计算\(L\)在\(w=w^0\)的位置的偏微分，即\(\frac{\partial L}{\partial w}|_{w=w^0}\),和在\(b=b^0\)的位置的偏微分，即\(\frac{\partial L}{\partial b}|_{b=b^0}\)。

同单个参数一样，计每次参数\(w\)更新的大小是\(\eta\frac{\partial L}{\partial w}\),每次参数\(b\)更新的大小是\(\eta\frac{\partial L}{\partial b}\)，即

\[\begin{aligned} w^1&=w^0-\eta\frac{\partial L}{\partial w}|_{w=w^0}\ \ \ \ \ d^1=d^0-\eta\frac{\partial L}{\partial d}|_{d=d^0}\\ w^2&=w^1-\eta\frac{\partial L}{\partial w}|_{w=w^1}\ \ \ \ \ d^2=d^1-\eta\frac{\partial L}{\partial d}|_{d=d^1}\\ w^3&=w^2-\eta\frac{\partial L}{\partial w}|_{w=w^2}\ \ \ \ \ d^3=d^2-\eta\frac{\partial L}{\partial d}|_{d=d^2}\\ ...\\ w^{i+1}&=w^i-\eta\frac{\partial L}{\partial w}|_{w=w^i}\ \ \ \ \ d^{i+1}=d^i-\eta\frac{\partial L}{\partial d}|_{d=d^i} \end{aligned} \]

\[if(\frac{\partial L}{\partial w}|_{w=w^i}==0 \&\& \frac{\partial L}{\partial d}|_{d=d^i}==0)\ then\ stop; \]

实际上，L 的gradient就是微积分中的那个梯度的概念，即可表示为（L对所有参数的偏微分组成的vector向量）：

\[\nabla L=\begin{bmatrix}\frac{\partial L}{\partial w}\\\frac{\partial L}{\partial d}\end{bmatrix}_{gradient} \]

Loss function可视化

可视化效果如下：(三维坐标显示在二维图像中，loss的值用颜色来表示)

横坐标是\(b\)，纵坐标是\(w\)，颜色代表Loss的值，越偏蓝色表示Loss越小，越偏红色表示Loss越大。

每次计算得到的梯度gradient，即由\(\frac{\partial L}{\partial w}\) 和\(\frac{\partial L}{\partial d}\)组成的vector向量，就是该等高线的法线方向(对应图中红色箭头的方向)；

而(\(-\eta\frac{\partial L}{\partial w}\) , \(-\eta\frac{\partial L}{\partial d}\) ) 的作用就是让原先的\((w^i,b^i)\)朝着gradient的方向(即等高线法线方向)前进，其中\(\eta\)(Learning Rate)的作用是每次更新的跨度(对应图中红色箭头的长度)，经过多次迭代，最终gradient达到极小值点。

注：这里两个方向的\(\eta\)(Learning Rate)必须保持一致，这样每次更新坐标的step size是等比例缩放的，保证坐标前进的方向始终和梯度下降的方向一致，否则坐标前进的方向将会发生偏移。

Gradient Descent的问题

这个问题是Gradient Descent每次迭代完毕，寻找到的梯度为0的点可能stuck at local minima/saddle point，不一定是最小值点（global minima）

这会造成一个问题是说，如果Loss Function长得比较坑坑洼洼(function比较复杂，极小值点比较多)，而每次初始化\(w^0\)的取值又是随机的，那么每次Gradient Descent停下来的位置可能并不是最小值点。除外，在现实工作时，往往在遇到梯度比较平缓(gradient≈0)的时候，迭代就会停下，此时Gradient Descent可能会更效率低下。

综上，在Model比较复杂的情况下，用Gradient Descent需要担心local minima，saddle point，plateau的问题。

而Linear Regression不需要考虑这个问题，因为在Linear Regression里，Loss Function实际上是convex的，是一个凸函数，是没有local optimal局部最优解的，它只有一个global minima。visualize出来的图像就是从里到外一圈一圈包围起来的椭圆形的等高线(就像前面的等高线图)，因此随便选一个起始点，根据Gradient Descent最终找出来的，都会是同一组参数。

偏微分的计算

• How is the results？

根据Gradient Descent，我们得到的\(y=b+w*x_{cp}\) 中最好的参数是\(b=-188.4, w=2.7\)

评估这个结果的好坏，可以计算Training Data的误差Error值。

这里我们把每个宝可梦\(i\)进化后的实际cp值跟预测的红色斜线（计算出的function）之间的差距记作\(e^i\)，而误差之和为：

\[Average\ Error\ on\ Training\ Data=\sum_{n=1}^{10}e^n=31.9 \]

• What we really care about is the error on new data (testing data)

当然,我们真正关心的是Generalization的case，也就是用这个Model去估测新抓到的pokemon，也就是testing data的误差,于是又抓了10只新的pokemon，等它进化，然后计算误差:

\[Average\ Error\ on\ Testing\ Data=\sum_{n=1}^{10}e^n=35.0>31.9 \]

虽然Testing Data算出来的误差结果稍微大于Training Data的误差结果，但其实是合理的。

• How can we do better？

上述是直线情况，下面考虑其他的Model。

考虑\(（x_{cp}）^2\)的Model：

\(y=b+w_1*x_{cp}+w_2*（x_{cp}）^2\)

经过Gradient Descent之后，得到Best Function为\(b=-10.3,w_1=1.0,w_2=2.7*10^{-3}\)，用Training Data计算出的误差\(Average\ Error=15.4\)。

用Testing Data计算出的误差\(Average\ Error=18\).4。

注意：虽然这个Model的图像是曲线，但是它仍是Linear Model（所谓Model是不是Linear Model，是看参数对output是不是linear的），可以把\(x_{cp}\)看作一个feature，把\(x_{cp}^2\)看作是一个feature,其他情况同理。

考虑\(（x_{cp}）^3\)的Model：

\(y=b+w_1*x_{cp}+w_2*（x_{cp}）^2+w_3*(x_{cp})^3\)

经过Gradient Descent之后，得到Best Function为\(b=6.4,w_1=0.66,w_2=4.3*10^{-3},w_3=-1.8*10^{-6}\)，用Training Data计算出的误差\(Average\ Error=15.3\)。

用Testing Data计算出的误差\(Average\ Error=18.1\)。

考虑\(（x_{cp}）^4\)的Model：

\(y=b+w_1*x_{cp}+w_2*（x_{cp}）^2+w_3*(x_{cp})^3+w_4*（x_{cp}）^4\)

经过Gradient Descent之后，用Training Data计算出的误差\(Average\ Error=14.9\)。

用Testing Data计算出的误差\(Average\ Error=28.8\)。

The results become worse

考虑\(（x_{cp}）^5\)的Model：

\(y=b+w_1*x_{cp}+w_2*（x_{cp}）^2+w_3*(x_{cp})^3+w_4*（x_{cp}）^4+w_5*（x_{cp}）^5\)

经过Gradient Descent之后，用Training Data计算出的误差\(Average\ Error=12.8\)。

用Testing Data计算出的误差\(Average\ Error=232.1\)。

The results are so bad

• 5个Model对比

5个model的training data的表现：

随着\((x_{cp})^i\)的高次项的增加，model越复杂，对应的average error会不断地减小；

实际上这件事情非常容易解释：低次的式子是高次的式子的特殊情况(令高次项\((x_{cp})^i\)对应的\(w_i\)为0，高次式就转化成低次式)。也就是说，在Gradient Descent可以找到Best Function的前提下(多次式为Non-linear model，存在local optimal局部最优解，Gradient Descent不一定能找到global minima)，function所包含的项的次数越高，越复杂，error在training data上的表现就会越来越小。

但是，我们关心的不是model在training data上的error表现，而是model在testing data上的error表现。

5个model的testing data的表现：

在training data上，model越复杂，error就会越低；但在testing data上，model复杂到一定程度之后，error非但不会减小，反而会暴增。在该例中，从含有\((x_{cp})^4\)项的model开始往后的model，testing data上的error出现了大幅增长的现象，通常被称为overfitting过拟合。

因此model不是越复杂越好，而是选择一个最适合的model。在本例中，考虑Testing Data的情况，合适的Model应该是取到\((x_{cp})^3\)的model。

• 怎么解决Overfitting的问题

解决方法一：收集更多的数据。

在收集到更多的数据后，就会发现有些之前Model里没有发现的隐藏因素，比如宝可梦的物种，宝可梦的重量，宝可梦的高度，宝可梦的HP值。

考虑宝可梦的物种：

重新辉到Step1，重新设计Model。

也就是根据不同的物种，设计不同的linear model(这里\(x_s=species\ of\ x\))，那如何将上面的四个if语句合并成一个linear model呢？

这里引入\(\delta\) ( 条件表达式 ) 的概念，当条件表达式为true，则对应的\(\delta\) 为1；当条件表达式为false，则对应的\(\delta\) 为0。因此可以通过下图的方式，将4个if语句转化成同一个linear model。

用新的function得到的结果为（绿线上有两条重合）：

一起考虑宝可梦的物种、重量、高度、HP值：

重新回到Step1，重新设计Model。

得到结果为：

算出的training error=1.9，但是，testing error=102.3！

这么复杂的model很大概率会发生overfitting(按照我的理解，overfitting实际上是我们多使用了一些input的变量或是变量的高次项，使曲线跟training data拟合的更好，但不幸的是这些项并不是实际情况下被使用的，于是这个model在testing data上会表现得很糟糕)。overfitting就相当于是那个范围更大的韦恩图，它包含了更多的函数更大的范围，代价就是在准确度上表现得更糟糕。

解决方法二：Regularization

原来的loss function只考虑了prediction的error，即\(\sum_{i}^{n}(y^i-(b+\sum_{j}w_ix_j))^2\);

而Regularization则是在原来的loss function的基础上加上了一项\(\lambda\sum(w_i)^2\),即\(\sum_{i}^{n}(y^i-(b+\sum_{j}w_ix_j))^2+\lambda\sum(w_i)^2\)，就是把这个model里面所有的参数的平方和用\(\lambda\)加权(其中i代表遍历n个training data，j代表遍历model的每一项)

有比较小参数的function更好，因为这意味着function更加平滑。（平滑就是对输入有一些变化，但是对输出的变化是小的）

举例来说，对\(y=b+\sum w_ix_i\)这个model，当input变化\(\Delta x_i\),output的变化就是\(w_i\Delta x_i\)，也就是说，如果\(w_i\)越小越接近0的话，输出对输入就越不敏感，function就是一个越平滑的function。

那为什么我们要选择平滑的function呢？

一般来说，平滑的function更可能是对的。

大多数情况下，如果我们有一个比较平滑的function，由于输出对输入是不敏感的，测试的时候，一些noises噪声对这个平滑的function的影响就会比较小，而给我们一个比较好的结果。

注：这里的\(\lambda\)需要我们手动去调整以取得最好的值，\(\lambda\)值越大代表考虑smooth的那个regularization那一项的影响力越大，我们找到的function就越平滑

说到这里你会发现，我们之前没有把bias——b这个参数考虑进去的原因是bias的大小跟function的平滑程度是没有关系的，bias值的大小只是把function上下移动而已。

观察上图可知，当我们的\(\lambda\)越大的时候，在training data上得到的error其实是越大的，但是这件事情是非常合理的，因为当\(\lambda\)越大，就越倾向于考虑\(w\)的值而越少考虑error的大小；但是有趣的是，虽然在training data上得到的error越大，但是在testing data上得到的error可能会是比较小的。如图，当\(\lambda\)从0到100变大的时候，training error不断变大，testing error反而不断变小；但当\(\lambda\)太大的时候(>100)，在testing data上的error就会越来越大。

注意：这里的error指的是\(\frac{1}{n}\sum_{i=1}^{n}|\hat{y}^i-y^i|\)

我们喜欢比较平滑的function，因为它对noise不那么sensitive；但是我们又不喜欢太平滑的function，因为它就失去了对data拟合的能力。而function的平滑程度，就需要通过调整\(\lambda\)来决定。就像图中，当\(\lambda\)=100时，在testing data上的error最小，因此我们选择λ=100。

• Conclusion