大数据机器学习算法与计算机视觉应用05:乘法权重算法

embedded/2024/11/30 20:00:55/

The Multiplicative Weight Algorithm

  • The Experts Problem
  • Weighed Majority Algorithm
  • Lower Bound for Deterministic Algorithms
  • Randomized Weighed Majority Algorithm

The Experts Problem

假设现在有 n n n位专家对 T T T天的做出预测
在第 t t t天,第 i i i位专家给出的预测值是 o u t i t out_i^t outit
你做出一个预测 g u e s s t guess^t guesst

做出预测之后,你将看到当天的实际结果 o u t t out^t outt

how to choose your guess on each days?

A Simpler Version 简单的情况

假设存在一个完美的专家总是做出准确的预测。

并且假设所有的专家都针对一个二值问题做预测(例如股票,预测涨或者跌)
我们能否找到一个犯错次数不超过 [ log ⁡ 2 n ] [\log_2n] [log2n] 的方法呢?

Majority-and-halving algorithm

每天,我们选出投票最多的专家预测值。如果该预测结果是错的,就去除所有做出这个预测的专家。
因此不超过 [ log ⁡ 2 n ] [\log_2n] [log2n] 次错误次数,就可以找到那个完美的专家。

同样地,这一样适用于预测非二值化问题的情况。

No Perfect Expert

事实上,在更实际的问题中几乎不可能存在这样的一个“完美的专家”。这个时候我们的算法应该是什么样子的呢?

我们假设最好的专家在此时也会犯 M M M次错误,那么我们将执行 M M M次上面的简单算法。当某次算法丢弃了场上所有的专家之后,我们让所有的专家重新加入并且继续执行。这种情况下,我们最多执行 ( M + 1 ) ( log ⁡ 2 n + 1 ) (M+1)(\log_2n+1) (M+1)(log2n+1)次错误,也就是 O ( M log ⁡ n ) O(M\log n) O(Mlogn)次错误

在这个问题中,我们发现 M M M似乎是一个下界, log ⁡ n \log n logn似乎也是一个下界,我们能不能将复杂度改为这两个下界相加,而不是这两个下界相乘的形式?

Weighed Majority Algorithm

下面的加权算法就可以做到这一点。我们先来看看这个算法的流程是什么:

  1. 给每位专家分配一个初始为1的权重。
  2. 每次做出预测时,我们统计做出每个预测的所有专家的权重和
  3. 当某些专家做出了错误的预测时,将其权重减半。

接下来我们证明如下定理:

在最好的专家产生M次错误的情况下,我们最多犯 2.41 ( M + log ⁡ 2 n ) 2.41(M+\log_2n) 2.41(M+log2n)次错误。

证明:

X X X是所有专家的权重和。
当我们每次预测错误的时候,都有 X n e w ≤ 3 4 X o l d X_{new} \leq \frac{3}{4}X_{old} Xnew43Xold
这是因为至少 1 2 X \frac{1}{2}X 21X的权重被减半了,所以总权重至少减少了 1 4 X \frac{1}{4}X 41X
而我们没有犯错的时候, X n e w ≤ X o l d X_{new} \leq X_{old} XnewXold,这是显而易见的。

假设我们到某个阶段总共犯了 m m m次错误,并且由于最好的专家最多犯 M M M次错误,因此有:

( 1 2 ) M ≤ X ≤ ( 3 4 ) m (\frac{1}{2})^M \leq X\leq (\frac{3}{4})^m (21)MX(43)m

也就是

( 4 3 ) m ≤ 2 M ⋅ n (\frac{4}{3})^m \leq 2^M \cdot n (34)m2Mn

两边取对数就有:
m ≤ M + log ⁡ 2 n log ⁡ 2 4 3 = 2.41 ( M + log ⁡ 2 n ) m\leq \frac{M+\log_2n}{\log_2\frac{4}{3}} = 2.41(M+\log_2n) mlog234M+log2n=2.41(M+log2n)

一般来说,我们可以忽略 l o g 2 n log_2n log2n,所以犯的错误上界的数量一般取决于最好的专家犯几次错误。

Improved Weighed Majority Algorithm

改进后的算法唯一的改动是:当一个专家在第 t t t天犯错时,我们将其权重乘 1 − ϵ 1-\epsilon 1ϵ

改进后的算法复杂度算法是一样的:

( 1 − ϵ ) M ≤ ( 1 − ϵ 2 ) m n (1-\epsilon)^M \leq (1-\frac{\epsilon}{2})^mn (1ϵ)M(12ϵ)mn

两边同时取对数:
M ln ⁡ ( 1 − ϵ ) ≤ m ln ⁡ ( 1 − ϵ / 2 ) + ln ⁡ n M\ln(1-\epsilon) \leq m \ln(1-\epsilon/2) + \ln n Mln(1ϵ)mln(1ϵ/2)+lnn

也就是

m ln ⁡ 1 1 − ϵ / 2 ≤ M ln ⁡ 1 1 − ϵ + ln ⁡ n m \ln \frac{1}{1-\epsilon/2} \leq M \ln \frac{1}{1-\epsilon} + \ln n mln1ϵ/21Mln1ϵ1+lnn

又有
ln ⁡ 1 1 − ϵ / 2 ≥ ϵ 2 ln ⁡ 1 1 − ϵ ≤ ϵ + ϵ 2 \ln\frac{1}{1-\epsilon/2}\geq \frac{\epsilon}{2}\\ \ln \frac{1}{1-\epsilon} \leq \epsilon + \epsilon^2 ln1ϵ/212ϵln1ϵ1ϵ+ϵ2

可得:
m ≤ 2 M ( 1 + ϵ ) + 2 ln ⁡ n ϵ m\leq 2M(1+\epsilon)+\frac{2\ln n }{\epsilon} m2M(1+ϵ)+ϵ2lnn

Lower Bound for Deterministic Algorithms

关于上述确定算法的下界有如下定理:如果最好的专家犯M次错误,那么加权主元算法最多犯 2 ( 1 + ϵ ) M + O ( log ⁡ 2 n ϵ ) 2(1+\epsilon)M + O(\frac{\log_2n}{\epsilon}) 2(1+ϵ)M+O(ϵlog2n)次错误。

关于这个下界的解释是这样的:如果我们想要找到那个最好的专家,由于最好的专家会犯M次错误,因此我们至少也要试错2M次。

Randomized Weighed Majority Algorithm

那么怎样做的比上面的下界更好?答案是采用不确定的算法,也就是下面讲到的随机加权主元算法

算法的流程如下:

  1. 对所有专家赋予一个权重
  2. 在每一天做出预测时(假设是0,1)我们有 预测 1 的专家权重 总权重 \frac{预测1的专家权重}{总权重} 总权重预测1的专家权重的概率预测1,反之预测0。
  3. 预测错误时的处理方式不变。

这个随机算法的期望复杂度将会是 ( 1 + ϵ ) M + ln ⁡ n ϵ (1+\epsilon)M+\frac{\ln n}{\epsilon} (1+ϵ)M+ϵlnn
,证明如下:

假设某一天预测错误的所有专家的权重占比和为 F t F_t Ft

那么我们期望的犯错次数就是 Σ t F t \Sigma_tF_t ΣtFt

那么我们预测错误时的权重和满足:
X n e w = ( 1 − F t ) X o l d + F t ⋅ X o l d ( 1 − ϵ ) X_{new} = (1-F_t)X_{old} + F_t\cdot X_{old}(1-\epsilon) Xnew=(1Ft)Xold+FtXold(1ϵ)

也就是
X f i n a l ≥ ( 1 − ϵ ) M X f i n a l ≤ n ⋅ ( 1 − ϵ ⋅ F t ) X_{final} \geq (1-\epsilon)^M\\ X_{final}\leq n\cdot(1-\epsilon\cdot F_t) Xfinal(1ϵ)MXfinaln(1ϵFt)

转化得到
( 1 − ϵ ) M ≤ n ⋅ e − ϵ Σ t F t (1-\epsilon)^M \leq n\cdot e^{-\epsilon\Sigma_tF_t} (1ϵ)MneϵΣtFt

也就是说:
ϵ Σ t F t ≤ M 1 1 − ϵ + ln ⁡ n \epsilon\Sigma_tF_t \leq M\frac{1}{1-\epsilon} + \ln n ϵΣtFtM1ϵ1+lnn

加入常见不等式 ln ⁡ 1 1 − ϵ ≤ ϵ + ϵ 2 \ln \frac{1}{1-\epsilon} \leq \epsilon + \epsilon ^2 ln1ϵ1ϵ+ϵ2可以得到:

Σ t F t ≤ M ( 1 + ϵ ) + ln ⁡ n ϵ \Sigma_tF_t \leq M (1+\epsilon) + \frac{\ln n}{\epsilon} ΣtFtM(1+ϵ)+ϵlnn


http://www.ppmy.cn/embedded/141826.html

相关文章

如何将钉钉新付款退款单数据集成到MySQL数据库

如何将钉钉新付款退款单数据集成到MySQL数据库 钉钉数据集成到MySQL的技术案例分享 在企业信息化建设中,数据的高效流转和准确存储是关键环节。本文将聚焦于一个具体的系统对接集成案例:将钉钉平台上的新付款退款单数据集成到MySQL数据库中,…

回文链表(java)

什么是回文链表 回文链表是指一个链表,其节点值从前往后和从后往前读是相同的。例如,链表 1->2->3->2->1 就是一个回文链表,因为无论从头到尾还是从尾到头读,节点值都是一样的 题目描述: 给你一个单链表…

Diffusion中的Unet (DIMP)

针对UNet2DConditionModel模型 查看Unet的源码,得知Unet的down,mid,up blocks的类型分别是: down_block_types: Tuple[str] ("CrossAttnDownBlock2D","CrossAttnDownBlock2D","CrossAttnDownBlock2D","DownBlock2…

性能监控框架的底层原理

性能监控框架的原理可以分为数据采集、数据传输、数据分析与展示三个主要步骤。本质上,这些框架通过与应用程序运行的底层系统(如CPU、内存、线程、网络等)以及语言级机制(如字节码、虚拟机、操作系统接口等)交互&…

基于深度学习的手势识别算法

基于深度学习的手势识别算法 概述算法原理核心逻辑效果演示使用方式参考文献 概述 本文基于论文 [Simple Baselines for Human Pose Estimation and Tracking[1]](ECCV 2018 Open Access Repository (thecvf.com)) 实现手部姿态估计。 手部姿态估计是从图像或视频帧集中找到手…

linux 文件权限,修改权限,c库调用

参考chmod 777 到底是啥 ???看完这个你就完全懂了!-CSDN博客 ls -l 查看当前目录文件的权限 会有一个十位的东西 分别为 d:这是一个文件夹 后面3*3位分别表示所有者用户,同组用户,其他用户的读(r),写(w),执行(x)…

DeSTSeg: Segmentation Guided Denoising Student-Teacher for Anomaly Detection

DeSTSeg: Segmentation Guided Denoising Student-Teacher for Anomaly Detection 清华、苹果 个人感觉 Introduction 很自然的让读者理解作者问题的提出,也有例子直接证明了这个问题的存在,值得借鉴!! Related work写的也很不…

Matlab 答题卡方案

在现代教育事业的飞速发展中,考试已经成为现代教育事业中最公平的方式方法,而且也是衡量教与学的唯一方法。通过考试成绩的好与坏,老师和家长可以分析出学生掌握的知识多少和学习情况。从而老师可以了解到自己教学中的不足来改进教学的方式方…