← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

33 第33章 机器学习算法

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.773Z

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