没有合适的资源?快使用搜索试试~ 我知道了~
首页弱学习力的力量:提高无监督学习算法准确性
弱学习力的力量:提高无监督学习算法准确性
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 190 浏览量
更新于2024-07-05
收藏 1.76MB PDF 举报
本文档"The Strength of Weak Learnability"发表于1990年,由罗伯特·S.舍普利撰写,收录在《机器学习》(Machine Learning)杂志第5卷,197-227页。该论文主要关注的是分布自由(PAC学习模型)中的学习算法性能提升问题。在传统的机器学习理论框架中,一个概念类被称为强学习(strong learnability)如果学习算法能够在未知概念的数据源中,以高概率输出一个在大部分实例上都正确预测的假设。这意味着学习者能够接近完美地理解并模仿概念。 然而,弱学习(weak learnability)的概念则相对宽松,它指的是学习算法能产生的假设仅比随机猜测稍有优势。尽管这些学习方式在准确性上有所妥协,但弱学习的重要性在于它反映了在实际应用中,即使有限的改进也可能带来实质性的效果。 论文的核心贡献是证明了强学习和弱学习实际上在某些情况下是等价的,即通过特定的方法,一个弱学习算法可以转化为一个能够达到任意高准确度的学习器。这一转化方法具有重要的实践意义,因为它提供了一种策略,使得原本在准确性上可能表现不佳的弱学习算法可以通过某种形式的迭代或增强过程,变得更有效率,从而在实际场景下实现更好的性能。 这个理论成果对于理解和设计实际的机器学习算法有着深远的影响,特别是在那些数据不确定性较高、完美学习困难的领域。通过揭示弱学习的力量,它启示我们如何利用有限的信息来构建适应性强、实用性高的学习系统,这对于当前大数据和复杂环境下的学习任务具有显著的指导价值。这篇文章对于深化我们对学习理论的理解,以及优化实际机器学习算法的性能具有不可忽视的作用。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/84996437/bg6.jpg)
202 R.E. SCHAPIRE
Yj
0.5
0.4
0.3
0.2
0.1
0.0
0.0 0.1 0.2 0.3 0.4 0.5
Figure 1. A graph of the function g(x) = 3x 2 - 2x 3.
Finally, D3 is constructed by filtering from D those instances on which hi and
h2
agree.
That is, a third oracle EX3 simulates the choice of an instance according to D3 by requesting
instances from EX until one is found for which hi(v) ~ h2(v). (Again, we will later show
how to limit the time spent waiting in this loop for a desired instance.) For a third time,
algorithm A is simulated with examples drawn this time by EX3, producing hypothesis h3.
At last, A' outputs its hypothesis h: given an instance v, if h~(v) = hz(v) then h predicts
the agreed upon value; otherwise, h predicts h3(v). (In other words, h takes the "majority
vote" of h~, h2 and h3.) Later, we show that h's error is bounded by g(a) - 3or 2 - 2a a.
This quantity is significantly smaller than the original error or, as can be seen from its
graph depicted in Figure 1. (The solid curve is the function g, and, for comparison, the
dotted line shows a graph of the identity function.)
3.2. A strong learning algorithm
An idea that follows naturally is to treat the previously described procedure as a subroutine
for recursively boosting the accuracy of weaker hypotheses. The procedure is given a desired
error bound c and a confidence parameter ~, and constructs an e-close hypothesis from
weaker, recursively computed hypotheses. If c >_ 1/2 - 1/p(n, s) then an assumed weak
learning algorithm can be used to find the desired hypothesis; otherwise, an c-close hypoth-
esis is computed recursively by calling the subroutine with e set to g-l(e).
Unfortunately, this scheme by itself does not quite work due to a technical difficulty:
because of the way EX2 and EX3 are constructed, examples may be required from a very
small portion of the original distribution. If this happens, the time spent waiting for an
example to be chosen from this region may be great. Nevertheless, we will see that this
![](https://csdnimg.cn/release/download_crawler_static/84996437/bg7.jpg)
THE STRENGTH OF WEAK LEARNABILITY
203
Learn(e, ~, EX)
Input:
error parameter e
confidence parameter 5
examples oracle
EX
(implicit) size parameters s and n
Return:
hypothesis h that is e-close to the target concept c with probability > i - 5
Procedure:
if e >_ 1/2-
1/p(n, s)
then return NeakLearn(5, EX)
a ~- g-'(~)
EX1 e- EX
hi +-- Learn(a, ~/5,
EX1)
rl *- e/3
let &a be an estimate of el =
PrveD[hl(v) ~
c(v)]:
choose a sample sufficiently large that lal - gql -< rl with probability > 1 -
5/5
if ~x _< e - ~-1 then return hi
defun
EX20
{ flip coin
if
heads,
return the first instance v from
EX
for which
ha(v) = c(v)
else return the first instance v from
EX
for which hi(v) ¢
c(v) }
h2 ~-- Learn(a,
5/5,
EX2)
~2 ~-
(1 - 2a)e/S
let ~ be an estimate of e =
PrvcD[h2(v) #
c(v)]:
choose a sample sufficiently large that ]e - ~1 < T2 with probability > 1 - 5/5
if $ < e- r2 then return h2
defun EX30
{ return the first instance v from
EX
for which
hi(v) ~ h2(v) }
h3 e-- Learn(a, ~/5,
EX3)
defun
h(v)
{ ~1 ~- hi(v), b~ ~ h~(,,)
if bx = b2 then return bl
else return h3(v) }
return h
Figure
2. A strong learning algorithm
Learn.
difficulty can be overcome by explicitly checking that the errors of hypotheses h~ and h 2
on D are not too small.
Figure 2 shows a detailed sketch of the resulting strong learning algorithm Lea rn. The
procedure takes an error parameter e and a confidence parameter 6, and is also provided
with an examples oracle
EX.
The procedure is required to return an hypothesis whose
error is at most e with probability at least 1 - & In the figure, p is a polynomial and
Weak Lea r n(6, EX) is an assumed weak learning procedure that outputs an hypothesis (1/2
-
1/p(n,
s))-close to the target concept c with probability at least 1 - 6. As above, g(o0
剩余30页未读,继续阅读
![application/pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/11124d2ce5db41368adec8b1ad4e99f7_xxzhaoming.jpg!1)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/user-vip.1c89f3c5.png)
应用市场
- 粉丝: 889
- 资源: 4152
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Lombok 快速入门与注解详解
- SpringSecurity实战:声明式安全控制框架解析
- XML基础教程:从数据传输到存储解析
- Matlab实现图像空间平移与镜像变换示例
- Python流程控制与运算符详解
- Python基础:类型转换与循环语句
- 辰科CD-6024-4控制器说明书:LED亮度调节与触发功能解析
- AE particular插件全面解析:英汉对照与关键参数
- Shell脚本实践:创建tar包、字符串累加与简易运算器
- TMS320F28335:浮点处理器与ADC详解
- 互联网基础与结构解析:从ARPANET到多层次ISP
- Redhat系统中构建与Windows共享的Samba服务器实战
- microPython编程指南:从入门到实践
- 数据结构实验:顺序构建并遍历链表
- NVIDIA TX2系统安装与恢复指南
- C语言实现贪吃蛇游戏基础代码
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)