返回主题:线性模型与优化算法

知识卡片

普通读书笔记卡 · 3710.d.1.a.1.a.1

加权多数的错误界对任意前缀成立

理解等级:高级

共有n位专家,算法连续预测T轮。对任意专家i和任意前T′轮(T′≤T),令m(T′)为加权多数算法犯错次数,mᵢ(T′)为专家i犯错次数。若错误专家的权重每次乘以1−γ,且0<γ≤1/2,则

m(T′) ≤ 2(1+γ)mᵢ(T′) + 2ln(n)/γ。

它不是只在最后一轮成立:任取前缀和任取比较专家都成立。右侧第一项随该专家错误数增长,第二项是从n个专家中竞争付出的代价;γ越大,第二项越小,但第一项系数越大。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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 ,