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

知识卡片

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

Hedge按专家权重随机预测

理解等级:中级

Hedge把专家权重归一化为概率,按此分布抽取专家并采用其预测;错误专家再按损失更新权重。

它和加权多数的确定性投票不同;题目给出的期望错误界是待证明结论,不能当作已推导的保证。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Another variant in the multiplicative-weights framework is known as HEDGE. It differs from WEIGHTED MAJORITY in two ways. First, HEDGE makes the prediction randomly—in iteration t, it assigns a probability to expert Ei, where . It then chooses an expert Ei′ according to this probability distribution and predicts according to Ei′. Second, the update rule is different. If an expert makes a mistake, line 16 updates that expert’s weight by the rule , for some 0 < ϵ < 1. Show that the expected number of mistakes made by HEDGE, running for T rounds, is at most m* + (ln n)/ϵ + ϵT. 33-3 Nonoptimality of Lloyd’s procedure in one dimension Give an example to show that even in one dimension, Lloyd’s procedure for finding clusters

    参考来源

    - 位置:《算法导论(第4版)》第33章《机器学习算法》(OEBPS/chapter033.xhtml,文本字符[70000,75000))。 - 结论依据:原文第33.3节或章末题目、注记;相关公式图已核对,未解答书中练习。 - 原始内容:Another variant in the multiplicative-weights framework is known as H EDGE . It differs from W EIGHTED M AJORITY in two ways. First, H EDGE makes the prediction randomly—in iteration t , it assigns a probability to expert E i , where . It then chooses an expert E i ′ according to this probability distribution and predicts according to E i ′ . Second, the update rule is different. If an expert makes a mistake, line 16 updates that expert’s weight by the rule , for some 0 < ϵ < 1. Show that the expected number of mistakes made by H EDGE , running for T rounds, is at most m * + (ln n )/ ϵ + ϵ T . 33-3 Nonoptimality of Lloyd’s procedure in one dimension Give an example to show that even in one dimension, Lloyd’s procedure for finding clusters