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

ops/2024/11/29 1:06:45/

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/ops/137522.html

相关文章

后台管理-动态路由配置以及用户权限管理(vue3+element plus+koa+Sequelize )

前言 之前开发了一个校园二手物品交易网站的demo 前端采用Vue2结合Element UI 后端采用了koa 、Sequelize 、Mysql 在工作了一年多之后,突然想针对工作所学来完善一下自己手里的项目 想要做一个针对于该平台或多个平台,来进行路由配置和角色集中管理…

算法篇:贪心算法

题目一:均分纸牌 有n堆纸牌,编号分别为 1,2,…,n1,2,…,n。每堆上有若干张,但纸牌总数必为nn的倍数。可以在任一堆上取若干张纸牌,然后移动。 移牌规则为:在编号为11的…

Kafka日志索引详解以及生产常见问题分析与总结

文章目录 一、Kafka的Log日志梳理1.1、Topic下的消息如何存储1.1.1、log文件追加记录所有消息1.1.2、index和timeindex加速读取log消息日志 1.2、文件清理机制1.2.1、如何判断哪些日志文件过期了1.2.2、过期的日志文件如何处理 1.3、Kafka的文件高效读写机制1.3.1、Kafka的文件…

CBK7运营安全

1 运营部门的角色 ​ prudent man、due care(按要求执行)VS due diligence(承担管理者责任) ​ 应尽关注:执行了负责任的动作降低了风险。 ​ 应尽职责:采取了所有必要的安全步骤以了解公司或个人的实际风…

2024年11月27日Github流行趋势

项目名称:screenshot-to-code 项目维护者:abi clean99 sweep-ai kachbit vagusX项目介绍:通过上传截图将其转换为整洁的代码(支持HTML/Tailwind/React/Vue)。项目star数:62,429项目fork数:7,614…

Spring Boot 的 WebClient 实践教程

什么是 WebClient? 在 Spring Boot 中,WebClient 是 Spring WebFlux 提供的一个非阻塞、响应式的 HTTP 客户端,用于与 RESTful 服务或其他 HTTP 服务交互。相比于传统的 RestTemplate,WebClient 更加现代化,具有异步和…

selinux和防火墙

一、selinux的说明 SELinux 是 Security-Enhanced Linux 的缩写,意思是安全强化的 linux 。 SELinux 主要由美国国家安全局( NSA )开发,当初开发的目的是为了避免资源的误用。 系统资源都是通过程序进行访问的,如果…

C++ 内存布局与字节序详解:类大小、结构体对齐、大小端与字节序转换

文章目录 一、如何计算一个类的大小?二、sizeof 计算的几个关键因素:2.1 特殊情况(空类、静态成员变量):2.2 示例 三、结构体对齐3.1 alignas 关键字:3.2 C 结构体对齐举例3.3 offsetof 宏3.3.1 如何理解偏…