知识卡片
总权重势能受错误轮次压低
令W为所有专家权重之和。
算法若预测错误,错误一侧至少占当前总权重一半,更新后W至多乘1−γ/2;预测正确时W也不会增加。
每位专家权重仍给W一个下界,由此可比较算法与任意专家的错误数。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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