Tag: 正则化

Categories
读书有感

Binning in Computational Methods: Gaussian Kernel Regularization, etc.

成天跟大数据打交道，最恨的就是out of memory这种错误。诚然，可以通过加大内存等方式来保证运行，但是随着数据量的增长，时间上的损耗也是很厉害的——比如时间复杂度为O(n^2)甚至更高。所以为了一劳永逸的保证计算的运行，需要在算法的改良上做一些文章。有了一个简单的类似于binning的idea，就去厚颜无耻的骚扰施老师了。

然后就顺利的套到了一篇paper，我能说我是瞎猫走狗屎运了么？居然还真问对人了，如获至宝的搞到一篇paper：

Yu, Bin, and Tao Shi. "Binning in Gaussian Kernel Regularization." (2005).

兴致勃勃的读起来，page 1 the history, interesting; page 2, ok...loss and penalty function ; page 3, oh...; page 4, fine...page 5, what the hell?瞬间扑面而来的各种公式一下子把我打回了原形——没学过就是没学过，再装还是读起来一片茫然。

然后开始迅速的往后找，找到了binning method的定义，嗯，不就是画格子嘛，和我本来要的思路差不多，多少找回一点感觉（binning的想法就是直方图，只不过是高维的扩展，把点aggregate到一个个格子，然后统计频数就可以啦，或者固定点的数量来确定格子）。跳过若干公式...直到后面的结果，眼前一亮：

2013-07-03 02_20_25-2006_Shi_Yu_Stat_Sinc(1).pdf - Adobe Reader

嘻嘻，就是这个！时间缩短至0.4%！神啊，比我想象的效率还高很多。这点loss in accuracy完全可以忍受嘛，重要的是——时间！时间！

然后问题就是，这个binning该怎么定义为好呢？看他simulate的结果，嗯，好像在这个case中每个格子的点到了9以上误差开始上升。

2013-07-03 02_20_10-2006_Shi_Yu_Stat_Sinc(1).pdf - Adobe Reader

还好啦对不对。具体的格子数量可以用实际数据测试一下，看看哪个更符合实际需求，直觉上应该是跟X以及Y的（联合）分布有关的...

好吧，我这是高射炮打蚊子么？我只是想在一个很简单的线性回归上面做一些binning...喵。多学一点总是好的，俗语嘛，“不畏浮云遮望眼，只缘身在最高层”。

p.s. 我也不知道为什么作为一个算法基础极为薄弱的、数学公式看起来依然会晕晕的、看到各种hilbert space开始感觉眼前飘过一团云雾的孩子会开始研究算法的问题...真的是被折磨太久了么？不过有时候看看这类的paper还蛮有裨益的...

相关文章

Categories
读书有感

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记（七）

例行的废话。刚刚看了一下Google Analytics里面的统计，那篇七天搞定SAS果然不负众望的摘得了（单篇博文）点击量桂冠。意外的是居然有那么多人会点击到“关于我”这个页面...呃，对我这么好奇么？

2 /learning-sas-in-7-days-1/
3 /coursera上的r语言课程/
4 /r会议小记/
5 /使用lyxxetex编译中文tex和输出中文pdf/
6 /中文文本聚类小尝试（text-clustering-in-r）/
7 /me/
8 /?统计学习精要the-elements-of-statistical-learning?课堂笔记（一）/
9 /快速将word的doc文件转为latex！/
10 /?统计学习精要the-elements-of-statistical-learning?课堂笔记（三）/

不过他的后续就比较悲催了，点击量寥寥。然后还不出意外的，weibo超越google成为了流量来源第一：

1 weibo.com / referral
2 (direct) / (none)
3 baidu / organic
4 google / organic
5 rss / rss
6 r-ke.info / referral
7 cloudlychen.net / referral
8 h2w.iask.cn / referral
9 so.360.cn / referral
10 yihui.name / referral

果然最近墙发威比较厉害...google啊google...

另外，出乎意料的是一些旧文反而受欢迎，哎~还好看到《统计学习精要(The Elements of Statistical Learning)》课堂笔记系列一直有点击，也算是这一系列写的比较值得吧。今天继续。

----------------笔记开始-----------------

貌似是第五章，不过老师一直在讲一些非常基础的数学预备工具：基展开与正则化，其中用到泛函概念若干。我不知道该开心呢，还是不开心呢，还是开心呢，毕竟泛函学过，毕竟泛函忘得也差不多了...

1. 预备知识

在P维欧氏空间内，我们定义两个运算：加法（x+y）和数乘()，然后定义一下函数空间：上的平方可积函数，同样的定义加法和数乘：f+g和).

接下来还有若干概念...呜呼：

  • 线性组合：
  • 线性独立
  • 线性子空间：我们可以定义线性子空间， , 有.
  • 基
  • 维数

这些概念连上运算加法和数乘一起，构成线性空间。进一步的，我们可以定义内积空间：

  • 内积：（离散）或连续
  • 之后的正交就很容易定义了：或者
  • 还可以定义正交基...
  • 还有正交子空间：
  • 正交补： , 使得 且，比如最简单的二维空间里面，X轴和Y轴...
  • 范数：

有了范数以后，我们就可以进一步的定义极限：如果 , 则 ；或者连续的，。

然后就是闭子空间的概念了：如果 ，且 ，则必有 ，即极限点都在空间内。注，在有限维空间内，只有空集和全集既开又闭。

还有完备基...总之大致的就是一步步的：定义内积 ->; 内积空间 ->; 存在可数的完备正交基 ->; Hilbert空间（有限维完备空间）

2.B-splines（样条）

2.1 定义

B-splines更多的是一种用离散逼近连续的感觉...好吧我承认我是完全的没有接触过这个东西，扫盲中...

首先，我们有一个闭区间[a,b],然后有个点聚集在其中，且依次增大。然后我们就可以定义一个函数集合： ，然后对于d=0 ,定义分段函数 ，然后就可以递归的定义

举个例子呢，就有. 这样下去，有：

  • d=0，0阶的时候，只有一段函数上有非零值；
  • d=1，1阶的时候，有两段函数有非零值；
  • d=2，2阶的时候，有三段函数有非零值...

2.2 性质

  • 性质一： 是分段的d次多项式；
  • 性质二：局部性：， 当 或者；
  • 性质三：光滑：是d-1阶光滑的多项式，即d-1阶导数都等于0；
  • 性质四：如果某一函数满足性质三，则必然和只相差一个常数因子。

2.3 d阶B-splines

我们可以用B-splines来逼近任意一个函数，则有，从这个角度看B-splines有点基底的味道。从分段多项式，到光滑的分段多项式，再到d-1阶光滑的d次多项式，我们就有了 d阶B-splines...

------笔记结束---------

讲了这么多，我一直在猜这些到底是用来干什么的呢...不知道接下来的哪些内容用到了完备内积空间、基展开和线性逼近呢？