|
一个几乎最优的PAC算法
An Almost Optimal PAC Algorithm |
|
| |
| 课程网址: |
https://videolectures.net/videos/colt2015_simon_pac_algorithm
|
| 主讲教师: |
Hans U. Simon
|
| 开课单位: |
信息不详。欢迎您在右侧留言补充。
|
| 开课时间: |
2015-08-20
|
| 课程语种: |
英语
|
| 中文简介: |
在PAC框架（可实现的情况）中，学习一个概念类所需的标记样例数量的目前已知的最好的一般下界和上界并不完全匹配：它们留下了顺序$\log(1/\eps)$ （resp）的差距。（在另一个相关参数中是对数的间隙）。是否存在与一般下界具有完全相同数量级的一般上界的“最优PAC算法”是一个尚未解决的问题。根据Auer和Ortner的结果，没有办法证明任意一致性算法是最优的，因为它们可以证明与最优性相差因子$\log(1/\eps)$。与此结果相反，我们证明了每个一致算法$L$（即使是可证明的次优算法）都可以导出一个族$(L)_K)_{K\ge1}$的PAC算法（$2K-1$调用$L$作为子程序）非常接近最优性：$L所需的标记示例的数量_K$仅比一般下界多一个因子_K(1/ / eps)$ where $\_K$表示（截断版）K$-次迭代对数。此外,美元左_K$适用于任何有限vc维的概念类$C$，只要$C$的一致性问题可行，它就能有效地实现。进一步证明，对于每一个一致算法$L$, $L_2$是Auer和Ortner用来证明次优一致性算法存在的概念类的最优PAC算法。这可以看作是$L_K$的表现可能比我们的最坏情况分析所建议的还要好
|
| 课程简介: |
The best currently known general lower and upper bounds on the number of labeled examples needed for learning a concept class in the PAC framework (the realizable case) do not perfectly match: they leave a gap of order $\log(1/\eps)$ (resp.~a gap which is logarithmic in another one of the relevant parameters). It is an unresolved question whether there exists an ``optimal PAC algorithm'' which establishes a general upper bound with precisely the same order of magnitude as the general lower bound. According to a result of Auer and Ortner, there is no way for showing that arbitrary consistent algorithms are optimal because they can provably differ from optimality by factor $\log(1/\eps)$. In contrast to this result, we show that every consistent algorithm $L$ (even a provably suboptimal one) induces a family $(L_K)_{K\ge1}$ of PAC algorithms (with $2K-1$ calls of $L$ as a subroutine) which come very close to optimality: the number of labeled examples needed by $L_K$ exceeds the general lower bound only by factor $\ell_K(1/\eps)$ where $\ell_K$ denotes (a truncated version of) the $K$-times iterated logarithm. Moreover, $L_K$ is applicable to any concept class $C$ of finite VC-dimension and it can be implemented efficiently whenever the consistency problem for $C$ is feasible. We show furthermore that, for every consistent algorithm $L$, $L_2$ is an optimal PAC algorithm for precisely the same concept classes which were used by Auer and Ortner for showing the existence of suboptimal consistent algorithms. This can be seen as an indication that $L_K$ may have an even better performance than it is suggested by our worstcase analysis.
|
| 关 键 词: |
概念类：PAC框架; 相差因子
|
| 课程来源: |
视频讲座网
|
| 数据采集: |
2025-04-20：zsp
|
| 最后编审: |
2025-04-20：zsp
|
| 阅读次数: |
4
|
|
图 书 馆