机器学习基石的泛化理论及VC维部分整理

 第四讲 机器学习的可行性

一、Hoeffding's Inequality

(P[left | u -mu   ight |>epsilon ] leq 2exp(-2epsilon^{2}N))              (1)

in-sample error, 也就是在样本里出现的error,(E_{in}) is probably close to out-of-sample error (E_{out}) (within (epsilon))

推出一个类似的公式: (P[left | E_{in} - E_{out}   ight |>epsilon ] leq 2exp(-2epsilon^{2}N))    (2)

也就是说,公式(2)说明了问题可以学习的两个条件:

(1)( E_{in} approx E_{out}) :这个代表 ( E_{out}) 要和 ( E_{in})差不多大

(2)( E_{in}(h) approx 0) :这个代表( E_{in})要差不多是0

这就推出,( h approx f)  with respect to (P)

我们的学习思路就是,从一些hypothesis set 中找到最好的 (h),使得( h approx f) 

二、真实的学习

面对多个( h ) 时,容易出现问题。

BAD Sample:( E_{in} and E_{out} ) far away

那么,Bad Sample的概率有多大呢?我们认为,在众多的hypothesis set上的每一个(h_{i}),只要有一个是坏的,则都是坏的

(P_{mathfrak{D}}left [ BAD   mathfrak{D} ight ]  )

( = P_{mathfrak{D}}left [ BAD  mathfrak{D}  for   h_{1} or  BAD   mathfrak{D}  for  h_{2}  or ...  or  BAD  mathfrak{D}  for  h_{M}  ight ] ) 

( leq P_{D} left [ BAD  D for  h_{1} ight ] + P_{D} left [ BAD  D for h_{2} ight] + ... +  P_{D} left [ BAD  D for h_{M} ight] )

(( Union Bound ))

( leq 2exp(-2epsilon^2N) + 2exp(-2epsilon^2N) + ... + 2exp(-2epsilon^2N) )

( = 2Mcdot exp(-2epsilon^2N))

当hypothesis set为有限时,(( M) 固定),当(N)足够大时,因为后面的(exp(-2epsilon^2N)) 随着(N)增大会变得特别小,故总体值是很小的。

此时学习是有效的。

当hypothesis set 为无穷大时,( M = infty )  则有问题了,具体问题下一部分讨论。

原文地址:https://www.cnblogs.com/tsat/p/3543012.html