机器学习基石

发表于   |   分类于   |  

机器学习基石

第四讲feasibility of learning

1.Learning is impossible

​ 我们无法证明hypothesis是否和目标f一致，也就不知道hypothesis对未知数据的处理是否是正确的，就好像我们没有从数据集中学到什么有用的东西。我们称这样的一个问题叫no free lunch.

2.Probability to the Rescue

Hoeffding’s inequality
$$
P[|\upsilon-\mu| > \epsilon]\leq2\exp(-2\epsilon^2N)
$$
我们拿抽样得来的ν来估计μ，当样本容量N越大时，ν越接近μ。

3.Connection to Learning

对任意已经确定的假设函数h，都可以通过已知的
$$
E{in} = \frac{1}{N}\sum{i=1}^{n}{[[h(x_i)\neq f(xi)]]}
$$
求出未知的
$$
E{out}=E_{x~p}[[h(x_i)\neq f(xi)]]
$$
再运用霍夫丁不等式
$$
P[|E{in}(h)-E{out}(h)| \geq \epsilon] \leq 2exp(-2\epsilon^2N)
$$
总结下，在
$$
E{in}(h) \approx E{out}(h)
$$
的情况下，加上
$$
E{in}(h)
$$
很小，可以推出
$$
E_{out}(h)
$$
也很小，即在整个输入空间中
$$
h \approx f
$$

4.Connection to Real Learning

​ 对一个hypothesis来说，坏的data是这样的：hypothesis在它上面的Ein很小，而Eout很大。Hoeffding’s inequality是说我们抽到这样的坏数据的几率很小。现在我们有M个hypothesis，那我们选到坏的data的几率肯定是增大了。

因此如果|H|=M的这种有限情况下，抽样样本N足够大时，可以确保假设空间中每个假设都满足$E{in}(g) \approx E{out}(g)$，如果通过算法找出的g满足$E{in}(g) \approx 0$ ，则通过PAC的规则可以保证$E{out}(g) \approx 0$

第五讲training versus testing

Recap and preview

​ 前面的课程得出了这样一个结论：在训练数据集足够大，H中包含的hypothesis个数有限的前提下，我们可以证明每一个hypothesis的Ein和Eout是相当的。在这样的结论下，我们就可以从H中选择一个Ein(g)≈0的hypothesis作为我们的g，且大概差不多（PAC）可以说Eout(g)≈0，也就说明了学习是可行的。

​ 先回顾前四讲的内容，第一讲，说问题会有一个未知的目标f能够完美的解决问题，我们可以找到一个g满足Eout(g)≈0，然后用这个很接近f的g去处理问题。第二讲，说怎么去找到g呢，我们引入Ein(g)≈0来衡量hypothesis，找到合适的g。第三讲，我们介绍了机器学习的分类，并指出本课程研究的问题都是基于批量的监督式二元分类。第四讲，我们尝试着去证明Ein≈Eout，并证明学习是可行的。

Effective Number of Lines

Effective Number of Hypotheses

Break Point

​ 上面我们介绍了四种不同的成长函数。我们原本打算用$m{h}(N)$来代替M。如果我们的mH(N)像positive rays和positive intervals的那样是一个多项式，那随着N的增长，$E{in}(g)$和$E{out}(g)$相差很大的几率会越来越小，逐渐趋于零，这正是我们想要的；而如果我们的$m{h}(N)$像convex sets的那样是指数类型的，那我们还不能确定这个几率。

​ 现在我们来确定一下二维感知机的mH(N)是那种类型的，但这个问题在这一讲还不能解决，要等到下一节。前面提到，当N=4时，我们的$m_h(N)<2N$.我们把4这样$m_h(N)<2N$的点称为break point。现在我们有这样一个猜想：对于没有break point的， 其成长函数就是2N；而对于有break point的，或许从break point上，成长函数就变成了$m_H(N) = O(N^{k-1})$。如果这个猜想成立，那我么就可以说二维感知机的成长函数的增长速度是$N^3$左右。

二维感知机的break point

第六讲theory of generalization

Restriction of Break Point

第九讲 linear regression

Linear Regression Problem

​ 线性回归与二元分类假设函数的表示只差了一个取正负号的函数sign

Linear Regression Algorithm

Generalization Issue

​ 该部分为重点。

​ 线性回归不像前面的PLA一样通过迭代得到最后的hypothesis，更像是通过分析的方法，直接通过公式得到了参数w。线性回归仍属于机器学习算法，因为它做了下面几个工作：

  • 对Ein进行优化，找到其最小值
  • 使Eout≈Ein
  • 迭代的过程在pseudo-inverse内部完成

Linear Regression for Binary Classification

​ 一般都将通过线性回归求得的解析解$w_{lin}$作为PLA或者pocket的初始值$w_0$，达到快速求解的目的 。

Logistic Regression

Logistic Regression Problem

Logistic Regression Error

​ 交叉熵错误$error(w,x,y)=ln(1+exp(-yw^Tx))$

Gradient of Logistic Regression Error

错误：$E{in}(w)=\frac{1}{N}\sum\limits{n=1}^{N}ln(1+exp(-y{n}w^TX{n}))$

梯度：$\nabla E{in}(w)=\frac{1}{N}\sum\limits{n=1}^{N}\theta(-y_nw^Tx_n)(-y_nx_n)$

Gradient Descent

重点，参见博客园。