一、曲线拟合

1、问题引入

①假设现在有一份关于某城市的住房面积与相应房价的数据集

表1    居住面积与房价关系

图1    居住面积与房价关系

那么给定这样一个数据集，我们怎么学习出一个以住房面积大小为自变量的用于预测该城市房价的函数？

问题可形式化为

给定大小为m的训练样本集

我们希望学习的目标函数为

房价预测本质上是回归问题

a、回归分析挖掘自变量与因变量之间的关系

b、有监督的学习问题，所有的样本点都带有目标变量

c、输出变量为连续值，可取任意实数

②假设现在我们有份更详尽的数据集，它还记录了卧室的数量

输入，X=(x1,x2)

假设每个自变量都与因变量Y存在线性相关

目标是学习出假设函数

1、怎样建模

①基本概念

Relationship

l Linear correlated?

l Nonlinear correlated?

Mining relation

l Correlation coefficient

 = 1时，称X,Y完全相关，X,Y之间具有线性函数关系

l Special Case

  e.g. 猜想Y与X存在指数关系，观察

      ln Y与X的线性相关性

l General---Polynomial Curve Fit（多项式曲线拟合）

          找到合适的阶数k，使等式成立，譬如logistic regression。

②多元变量线性回归

上文提到假设函数：

参数或权重(反映每个自变量对输出的影响)，使线性函数空间参数化(h形式已知,用参数来刻画)

为了表示方便，令x0(对应截距项)，则上式可写成

注：k与自变量的个数有关，此处k=2

3、怎样获取参数

合理的选择策略:对于该数据集的每一个样本，选定的参数使得尽可能接近y。在实际中，尽可能接近用代价函数来表示。

Cost Function(代价函数)

描述预测值与真实值之间的差距，从而优化目标函数参数，可以利用0-1损失，绝对值损失，平方损失，对数损失。

对于线性回归问题，我们采用的目标函数为

这是普通最小二乘回归模型(statistics)，可以利用概率论知识解释为什么可以，如下。

二、概率解释

1、选择最小二乘(平方损失)代价函数的理由：

我们做出如下假设：

E(i)：误差项(没有model出的效应，e.g.遗漏了某些因素的影响)或随机噪声

进一步假设：

即

注意，下面式子与这条式子等价。

等价于

之后我们就可以利用似然函数解释最小二乘代价函数：

定义:给定随机变量X与参数，我们观察到结果Y的可能性

由E(i)之间的独立性假设，得

简单解释一下，我们的目标，是实现在给定的情况下，对于m个样本的输入，能输出的m个y的概率的总乘积最大，那构建的模型就越准确了，即最大似然估计。

定义：最大似然估计(maximum likelihood estimation)

    当给定似然函数(关联y与x的概率模型)时，一种合理的参数估计方法是尽可 能选择使数据出现的概率最大，即最大化似然函数。

实际上，常用的是对数似然：

因而，最大似然估计等价于最小化平方损失函数，得证。

三、模型求解

1、梯度下降法(steepest gradient descent)

负梯度方向是函数值下降的方向，利用负梯度方向来决定每次迭代的新的搜索方向，使得每次迭代能使待优化的目标函数逐步减小。

其中（关键）：

LMS更新法则：

注意：每次参数更新只用到一个训练样本，样本维数等于维数。

2、批量梯度下降(batch gradient descent)

每次参数更新，需要依赖训练集的所有样本。

对于线性回归问题，代价函数是凸二次规划函数，有全局最优解

图1  梯度下降法迭代过程

3、随机梯度下降

特点: 

1.每次随机选取一个样本点 立即更新参数

        2.单个样本点的代价函数值下降近似于总体的代价函数值下降

        3.对步长选择敏感 可能会出现overshoot the minimum

3、方法比较

1．梯度下降法是批量更新算法，随机梯度是在线算法

2．梯度法优化的是经验风险，随机梯度法优化的是泛化风险

3．梯度法可能陷入局部最优，随机梯度可能找到全局最优

4．梯度法对步长不敏感，随机梯度对步长选择敏感 

5．梯度法对初始点(参数)选择敏感

5、输入预处理

a. 归一化

输入特征归一化，确保特征在相似的尺度里，但不一定所有的数据都需要归一化。

    理由：梯度下降法可能会存执之字形地下降，影响算法的收敛速度。

一般做法：

其中均值，最大值与最小值之差或标准差。

b.步长的选择

对于梯度下降法：

注意两个问题：

1、“调试”：如何确保梯度下降算法正确的执行；

2、如何选择正确的步长(learning rate):  α

 如何选择α-经验的方法：

…, 0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1… 

     特别对于随机梯度下降法，步长的选择需满足两点：

①保证算法收敛性

②保证有机会搜索到全局最优解

5、正规方程

假设函数作用于每个样本：

则：

代价函数可改成：

此问题等价于：

即两个向量之间的欧氏距离：

几何意义：

需保证可逆(可逆的充分条件:矩阵X各列线性无关)

回顾一下，上面我们的方法是利用迭代的方式求出，从而使代价函数值最小，并没有求出代价函数。也就是说，所谓的最优解能否求得，不管是通过迭代的方式或是其它方式也好，符合上面的条件才行。

但现实中的数据不是那么理想的。

若不可逆，如何求解？ 

1、求伪逆(statistics的解决方案)

2、去掉冗余的特征（线性相关）

3、去掉过多的特征，例如m <= n (m为样本数, n为特征数)

四、小结

1、梯度下降法

需要选择合适的learning rate α;

需要很多轮迭代

即使n很大的时候效果也很好（n为特征数，即维度）

2、正规方程

不需要选择α

不需要迭代，一次搞定

需要计算，其时间复杂度是

n很大，就非常慢，可以考虑降维

【machine learning】linear regression