Peng Yang∗, Ning Zhang†, Shan Zhang†, Li Yu∗, Junshan Zhang‡, and Xuemin (Sherman) Shen†
∗School of Electronic Information and Communications, Huazhong University of Science and Technology, Wuhan, China
†Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Canada
‡School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona, USA
Email: ∗{yangpeng, hustlyu}@hust.edu.cn, †{n35zhang, s372zhan, sshen}@uwaterloo.ca, ‡junshan.zhang@asu.edu
本文主要围绕机器学习中的岭回归。
Linear model是为了获取线性回归系数做准备;Location differentiated content caching algorithm即是获取回归系数;regret analysis即是回归的显著性检验
Online learning algorithm
Hit rate definition
The number of content Requests
Linear model
Problem definition: max->min
因本文中的hit rate的定义为content Requests rather than rate。最优的文件缓存策略中文件被请求次数与正常情况下的文件请求次数相差越少越好。
Location differentiated content caching algorithm
A. Predicting content hit rate
缓存需要考虑update,更新时间在本文中用文件f在n路侧单元第几次缓存表示。即:文件在路侧单元的缓存频率。实际如何更新并未有明确解释。
其中,
显著性检验部分仍有看不懂。。。再说吧
霍夫丁不等式(此处理解并不系统,待后再补。。。)
-
常见形式
N为样本容量。具体表示见下图。
对于多个预测点:
抽样存在很多情况,难免出现Bad sample(Ein和Eout相差很大的sample)。霍夫丁不等式说明针对一个h出现bad sample的几率很小。但是当有很多个h时,bad data就很可能出现(如课件中抛硬币的例子),当bad sample的Ein又很小时,我们作出选择时就会worse情况。Bad sample也就是Bad Data。
含义: 给出二项分布均值偏离期望的概率上限(置信区间)
-
一般形式
证明过程没看懂。。。霍夫丁不等式及其证明 -
举例
从罐子中抽样100个小球,其中70个绿色,30个橙色。绿球的比例抽样统计值v=70%,以ϵ=10%为衡量标准,不等式变为:P[|0.7-u|>0.1]<=2exp(-20.01100)=0.27
即:真实概率落在[0.6,0.8]区间内的概率为73%;有27%的概率,真实统计值与抽样统计值相差超过10%。