ML整理与实现(党)

Dang YJ 2014.9.24

监督学习

本篇开始，我想我该开始讨论学习关于机器学习的许多经典理论。这些理论在实际中应用非常的广泛，根据学习情况总结。首先我们开始学习监督学习，假设我们通过统计调查，得到了这样一组数据（关于波特兰市不同地区47个商品房的居住面积和价格）。 居住面积（英尺2） 价格（1000＄） 2104 400 1600 330 2400 369 1416 232 3000 0 画出这些数据： House price550500450price(1000$)400350300250200140016001800200022002400260028003000

给出像这样的一个数据，我们应该怎么样去预测波特兰地区其他房子的价格，应该用怎么样关于居住面积的函数进行预测？

首先我们需要建立一些未来学习中会经常使用的到概念：

x(i)表示输入变量（实例中的居住面积），也被叫做输入特征；

Living area(feet2)； y(i)表示输出变量或目标变量，利用它进行预测（房子价格）

x(i),y(i)叫做训练样本；

x(i),y(i);i1,,m叫做训练集；

X表示输入空间；

Y表示输出空间；

本实例中，X==Y=R.

下面我们更加正规化的描述一下监督学习：我们的目标是，给出一个训练集，去学习一个函数h：X=Y，使得h(x)相对于y有一个 “好”的预测值。处于历史原因，h被称为一个假设。过程描绘如下：

训练集

学习算法

x h ( x ) y

当目标变量为连续变量时，回归问题； 当目标变量为离散变量时，分类问题。

第一部分：线性回归

对于上面的数据，我们在加入一组特征，即房间数量，使得其数据类型更加丰富。 居住面积（英尺2） #房间数量 价格（1000＄） 2104 3 400 1600 3 330 2400 3 369 1416 2 232 3000 4 0 这时，x就是一个二维向量，x(i)(x1,x2)R2（一般情况下，特征根据实际情况来选择）。

(i)(i)(i)x1表示第i个房间的居住面积； x2表示第i个房间的房间个数；

为了实施监督学习方法，我们必须确定函数（假设）h。最初的选择，我们

确定关于x的线性函数，其近似于y。

(i)h(x)01x12x2ixiθTx

i0n，其X=Y参数化线性函数空间；在没有混淆的情况下可以去i表示参数（权）

掉h(x)脚标，使其变为h(x)；且为了简化公式，令x01；上式最右边表示矩阵，

求和式中的n表示输入变量的个数（不包括x0）。

现在，给出一个训练集，我们怎么样去选择，去学习参数？？

一个办法就是去使得h(x)与y尽可能的接近，至少对于训练样本应该满足。为了是其公式化，定义一个测量函数，使其对于每一个，h(x(i))与y(i)都尽可能的近。

定义损失函数：

1m(i)(i)2J()h(x)y

2i1为什么选择这样的损失函数呢？？这个后面一小节将专门针对这个问题进行回答，1/2完全是为了计算方便而加的（后面计算时要求导）。

回归主题，我们的目的是为了使得h(x)与y尽可能的接近，即就是要求的

minJ(),怎么办？？方法很多，常用的方法是最小二乘法和梯度下降法。

1. LMS(最小均方)算法

梯度下降法：首先对赋值，这个值可以为随机值，也可以让为全零向量； 其次改变的值，使得J()按照梯度下降方向进行减少。

j:jJ() j（同时对全部的j=0,1…n进行更新；表示学习率或步长；很自然地，每一步沿着J()最陡峭的方向下降）

下面推导我们只针对一个训练样本进行，那么就可以忽略掉求和符号。

12J()h(x)yjj221h(x)yh(x)y2j

nh(x)yxyiiji0h(x)yxj迭代规则可得出：

j:jy(i)h(x(i))x(ji)

其被叫做最小均方迭代规则（LMS）,也被叫做Widrow-Hoff学习规则

该方法看起来很自然和凭借直觉得到的。这种方法迭代的大小与误差项

y(i)h(x(i))成比例；实际中，如果误差项很小（预测准确），参数迭代几乎不

变；同样的，参数改变大，说明误差项很大（预测不准确）。预测呈现慢而准，快而糙，其对于步长太敏感。

批梯度下降法：对全部的训练样本求误差后，再对参数进行更新。

怎么办呢？？上面推导中我们使用的一个训练样本。这儿有两种方法可以对其进行修正：

j:ji1y(i)h(x(i))x(ji)m(对所有的j)

其每一步对训练集中的所有样本进行。 实际上，J是一个凸二次函数。

下面是一个梯度下降的实例，其最小化了个二次函数。

随机梯度下降法：每扫描一步，就要对参数进行更新：

For i=1:m

j:jy(i)h(x(i))x(ji)(对所有的j)

该算法中，我们反复在训练样本中进行，每次遇到一个训练样本，我们就更新参数（对单样本误差梯度），即为随机梯度下降法（增量梯度下降法）

批梯度下降法每步要对全部的样本进行和扫描，如果m很大是，计算成本很高。但是随机梯度法能够开始在总体正确的方向上进行迭代（对每一个样本），其速度要比批梯度下降快，但是其总达不到收敛，只是在最小值旁边徘徊。实际中应用较为广泛，最小值附近的值其实是相对合理的。出于这些原因，尤其是对样本含量较大是，随机梯度更被广泛地使用。 2. 正规方程

最小二乘法：利用矩阵求导的一系列方法，我们得到一个使得J()最小化的

值。

给出训练集，定义设计矩阵X（m by n,实际上是m by n+1,包含常数项），将训练样本的输入值，写成列的形式：

(x(1))T(2)T(x)X(m)T(x) 从训练集中，令y是m维向量，包含全部的目标值

y(1)(2)y y(m)y现在，h(x(i))(x(i))T,我们可以验证

(x(1))Ty(1)(2)T(2)(x)yXyX(m)T(m)(x)y(x)y(2)T(2)(x)y(m)T(m)(x)y而后利用性质zTzizi2

(1)T(1)

11m2T(Xy)(Xy)h(x)y 22i1J()因此，

J()1(Xy)T(Xy)21(Xy)T(Xy)21tr(Xy)T(Xy)21tr(TXTXTXTyyTXyTy) 21(trTXTX2tryTX)21(XTXXTX2XTyT)2XTXXTyT从而得到正规方程：J()XTXXTyT0

(XTX)1XTyT

3. 选用误差函数作为平方和的概率解释

当我们面对回归问题时，为什么在线性回归和最小二乘中，损失函数的选择是合理的？？？

在本段话中，我们将利用概率性假设进行解释。 令目标函数和输入的相关性表示如下方程：

y(i)Tx(i)

其中，(i)是误差项，其包括系统误差（相关特征的考虑）和随机噪音。 假定(i)是同分布的（IDD），根据高斯分布，其均值为零，方差为2。写成

(i)~N(0,2)，也就是说(i)的密度函数写成

1((i))2p()exp() 222(i)这就意味着

p(y(i)1(y(i)Tx(i))2x;)exp() 222(i)符号p(y(i)x(i);)表示，给定参数和x(i)的情况下，y(i)的分布情况。注意：我们不能写成p(y(i)x(i),)，因为参数不是随机变量。分布写成

y(i)x(i);~N(Tx(i),2)

在给定设计矩阵和参数的情况下，y(i)的分布是什么？？？？

数据的概率给出通过p(yX;)。对于一个参数的固定值，（假定X）关于y的函数。我们希望确定的展现出关于参数的函数。

似然函数

L()L(;X,y)p(yX;)

性假设

mL()p(y(i)x(i);)i1mi11(yx)exp()222(i)T(i)2

怎么样合理选择参数，才能是给出的概率模型更好的表现出x(i)和y(i)的关系？？？

最大似然估计回答了这个问题，我们应该选择使得数据尽可能的出现在高概

率区域，也就是说，最大化L()，其为严格递增函数。

l()logL()1(y(i)Tx(i))2logexp()222i1m1(y(i)Tx(i))2logexp() 222i1111m(i)T(i)2mlog2yx22i1mJ()4. 局部加权线性回归

上面提到的线性回归的误差函数里，系数都是1，没有权重。带全的新兴回归加入了权重的信息。 基本假设： a)选择，使得w(i)y(i)Tx(i)最小化

2i1mb)输出Tx

(x(i)x)2其中假设wexp，道理是待测点越近的点权重越（x为待测点）22(i)大，越远的点影响小权重小。权重不是随机变量。

此方法成为非参数学习算法，因为误差函数随着预测值的不同而不同，这样参数值无法实现确定，预测一次需要临时进行计算。感觉有些KNN的意思。

第二部分：分类与logistic回归 logistic回归:

h(x)g(Tx)11eTx

其中，g(z)1称为logistic函数或S形函数。图像如下： 1ez

g(z)d1dz1ez1(ez)z2(1e)111(1ez)(1ez)

g(z)(1g(z))怎么样选择？？？最大似然 假设：

P(y1x;)h(x)P(y0x;)1h(x)

更加简洁地

P(yx;)(h(x))y(1h(x))1y

假设这些训练样本是地，然后我们写出参数似然估计

L()p(yX;)p(y(i)x(i);)i1m

(i)(h(x(i)))y(1h(x(i)))1y(i)容易最大化

l()logL()y(i)logh(x(i))(1y(i))log(1h(x(i)))i1m

怎么样最大化可能性呢？？？本文中应用了类似于梯度下降的方法，梯度上升法 通过

:l()

即：

11Tl()y(1y)g(x)TTj1g(x)jg(x)11TTTy(1y)g(x)(1g(x))x TT1g(x)jg(x)y(1g(Tx))(1y)(1g(Tx))xjyh(x)xj得到j:jy(i)h(x(i))x(ji)

Tx(i)换成了h(x(i))，而h(x(i))实际上是

可以看出，与线性回归类似，只是

Tx(i)通过g(z)映射得到的