知识卡片
加权多数的错误界对任意前缀成立
共有n位专家,算法连续预测T轮。对任意专家i和任意前T′轮(T′≤T),令m(T′)为加权多数算法犯错次数,mᵢ(T′)为专家i犯错次数。若错误专家的权重每次乘以1−γ,且0<γ≤1/2,则
m(T′) ≤ 2(1+γ)mᵢ(T′) + 2ln(n)/γ。
它不是只在最后一轮成立:任取前缀和任取比较专家都成立。右侧第一项随该专家错误数增长,第二项是从n个专家中竞争付出的代价;γ越大,第二项越小,但第一项系数越大。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第33章 机器学习算法 · 查看原书依据
Theorem 33.4 When running WEIGHTED-MAJORITY, we have, for every expert Ei and every event T′ ≤ T,
参考来源
- 位置:《算法导论(第4版)》第33章《机器学习算法》(OEBPS/chapter033.xhtml,文本字符[30000,40000),定理起于单元07、证明跨至单元08)。
- 结论依据:第33.2节定理33.4的公式图 Art_P1356 给出 m(T′)≤2(1+γ)mᵢ(T′)+2ln n/γ,对每个专家 i 和 T′≤T 成立;算法前提 0<γ≤1/2。势能证明从单元07延续至单元08,Art_P1365–P1376 为后半证明及推论。
- 原始内容:Theorem 33.4 When running W EIGHTED -M AJORITY , we have, for every expert E i and every event T ′ ≤ T ,