原书出处
Introduction to Algorithms, Fourth Edition
33 第33章 机器学习算法
weight, which is initially 1, is multiplied by 1 – γ, and so we have for t = 1, 2, …, T.
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
In an iteration where the algorithm does not make a mistake, some of the weights decrease
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter033.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea