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

知识卡片

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

总权重势能受错误轮次压低

理解等级:高级

令W为所有专家权重之和。

算法若预测错误,错误一侧至少占当前总权重一半,更新后W至多乘1−γ/2;预测正确时W也不会增加。

每位专家权重仍给W一个下界,由此可比较算法与任意专家的错误数。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第33章 机器学习算法 · 查看原书依据

      We use a potential function , summing the weights for all n experts after iteration t of the for loop of lines 3–18. Initially, we have W(0) = n since all n weights start out with the value 1. Because each expert belongs to either the set U or the set D (defined in lines 5 and 7 of WEIGHTED-MAJORITY), we always have W(t) = upweight(t) + downweight(t) after each execution of line 8. Consider an iteration t in which the algorithm makes a mistake in its prediction, which means that either the algorithm predicts 1 and the outcome is 0 or the algorithm predicts 0 and the outcome is 1. Without loss of generality, assume that the algorithm predicts 1 and the outcome is 0. The algorithm predicted 1 because upweight(t) ≥ downweight(t) in line 9, which implies that Each expert in U then has its weight multiplied by 1 – γ, and each expert in D has its weight unchanged. Thus, we have Therefore, for every iteration t in which the algorithm makes a mistake, we have

    参考来源

    - 位置:《算法导论(第4版)》第33章《机器学习算法》(OEBPS/chapter033.xhtml,文本字符[30000,35000))。 - 结论依据:原文第33.2节加权多数算法与势能证明,或第33.3节梯度、步长和局部极小讨论;相关公式图已核对。 - 原始内容:We use a potential function , summing the weights for all n experts after iteration t of the for loop of lines 3–18. Initially, we have W (0) = n since all n weights start out with the value 1. Because each expert belongs to either the set U or the set D (defined in lines 5 and 7 of W EIGHTED -M AJORITY ), we always have W ( t ) = upweight ( t ) + downweight ( t ) after each execution of line 8. Consider an iteration t in which the algorithm makes a mistake in its prediction, which means that either the algorithm predicts 1 and the outcome is 0 or the algorithm predicts 0 and the outcome is 1. Without loss of generality, assume that the algorithm predicts 1 and the outcome is 0. The algorithm predicted 1 because upweight ( t ) ≥ downweight ( t ) in line 9, which implies that Each expert in U then has its weight multiplied by 1 – γ , and each expert in D has its weight unchanged. Thus, we have Therefore, for every iteration t in which the algorithm makes a mistake, we have