分类目录归档:优化与模拟

传统统计计算,包括优化方法和统计模拟

共轭梯度法计算回归

共轭梯度示意图(图片来源:维基百科)
轮回眼 共轭梯度示意图(图片来源:维基百科

引子

之所以写这篇文章,是因为前几天统计之都的微信群里有同学提了一个问题,想要对一个很大的数据集做回归。然后大家纷纷给出了自己的建议,而我觉得共轭梯度算回归的方法跟这个背景比较契合,所以就正好写成一篇小文,与大家分享一下。

说到算回归,或许大家都会觉得这个问题太过简单了,如果用 $X$ 表示自变量矩阵,$y$ 表示因变量向量,那么回归系数的最小二乘解就是 $\hat{\beta}=(X’X)^{-1}X’y$。(本文完)



哎等等,别真走啊,我们的主角共轭梯度还没出场呢。前面的这个算系数的公式确实非常简洁、优雅、纯天然、不做作,但要往里面深究的话,还是有很多问题值得挖掘的。

最简单暴力的方法,就是从左向右,依次计算矩阵乘法,矩阵求逆,又一个矩阵乘法,最后是矩阵和向量的乘法。如果你就是这么算的,那么可以先默默地去面壁两分钟了。

更合理的方法,要么是对 $X’X$ 进行 Cholesky 分解,要么是对 $X$ 进行 QR 分解,它们基本上是现在算回归的软件中最常见的方法。关于暴力方法和矩阵分解方法的介绍和对比,可以参见这个B站上的视频。(什么?你问我这么严肃的话题为什么要放B站上?因为大部分时间都是在吐槽啊)

好,刚才去面壁的同学现在应该已经回来了,我们继续。前面这些通过矩阵运算求回归系数的方法,我们可以统称为直接法。叫这个名字,是因为它们都可以在确定数目的步骤内得到最终的结果。而与之相对的,则叫做迭代法,意思是通过不断更新已经得到的结果,来逐渐逼近真实的取值。打个比方,你想要知道一瓶82年的拉菲值多少钱,直接法就是去做调研,原料值多少,品牌值多少,加工费多少,运输费多少……然后加总起来得到最终的定价;而迭代法就是去问酒庄老板,你先随便蒙一个数,然后老板告诉你高了还是低了,反复循环,总能猜个八九不离十。

说到这里,你自然要问了,既然算回归的软件大都是用直接法,为什么还要考虑迭代法?莫非直接法有什么不好的地方?这就说到问题的点子上了。

继续阅读共轭梯度法计算回归

漫谈正态分布的生成

本文作者简介:王夜笙,就读于郑州大学信息工程学院,感兴趣的方向为逆向工程和机器学习,长期从事数据抓取工作(长期与反爬虫技术作斗争~),涉猎较广(技艺不精……),详情请见我的个人博客~
个人博客地址:http://bindog.github.io/blog/

感谢怡轩同学的悉心指导~

之前拜读了靳志辉(@rickjin)老师写的《正态分布的前世今生》,一直对正态分布怀着一颗敬畏之心,刚好最近偶然看到python标准库中如何生成服从正态分布随机数的源码,觉得非常有趣,于是又去查找其他一些生成正态分布的方法,与大家分享一下。

利用中心极限定理生成正态分布

设$X_1,X_2,\cdots ,X_n$为独立同分布的随机变量序列,均值为$\mu$,方差为$\sigma^2$,则

$$Z_n=\frac{X_1+X_2+\cdots+X_n-n\mu}{\sigma \sqrt n}$$

具有渐近分布$N(0,1)$,也就是说当$n \rightarrow \infty$时,

$$P\left \{ \frac{X_1+X_2+\cdots+X_n-n\mu}{\sigma \sqrt n} \leq x \right \} \rightarrow \frac{1}{\sqrt{2\pi} } \int_{-\infty }^{x} e^{ -\frac{t^2}{2} } \, dt$$

换句话说,$n$个相互独立同分布的随机变量之和的分布近似于正态分布,$n$越大,近似程度越好。当然也有例外,比如$n$个独立同分布的服从柯西分布随机变量的算术平均数仍是柯西分布,这里就不扩展讲了。

根据中心极限定理,生成正态分布就非常简单粗暴了,直接生成n个独立同分布的均匀分布即可,看代码

继续阅读漫谈正态分布的生成

嘿,朋友,抢红包了吗?

如果你有一台智能手机,如果你装了一个名叫微信的软件,那么你今年的春节很可能是在下面这样的场景中度过的(图片来自微信群):

lucky_money_3 lucky_money_2 lucky_money_1

这也使得众多的网络大V发出了下面的感慨:

lucky_money_4

而最近几天不少微信群里面又流行起来一种“红包接力”的玩法,大概的规则是:群里面先由一人发一个红包,然后大家开始抢,其中金额最大的那个人继续发新一轮的红包,之后不断往复循环。

这时候大家或许就会问了,一直这么玩下去会有什么结果呢?是“闷声赚大钱”了,还是“错过几个亿”了?是最终实现“共同富裕”了,还是变成“寡头垄断”了?要回答这些问题,我们不妨用统计模拟的方法来做一些随机实验,得到的结果或许会让你大跌眼镜呢。

继续阅读嘿,朋友,抢红包了吗?

自制简单遗传算法实验

我参加完八月份的COS沙龙之后比较闲,忽然想起自己很久以前看的遗传算法的基本思想。本着时不时就应该做一些私活的心态,我就在旅行商问题上面把它实现了一下。

遗传算法

遗传算法是一个仿生学的算法。进化论认为地球上千奇百怪的生物都是进化而来的,如今能生存在地球上的生物是更适应于这个环境的,我们也可以说它们是被“优化过”的。他们是怎么优化的呢?在一个种群中,生物的差异主要来自于两点,不同染色体之间的交叉结合以及染色体自发的随机变异。这些差异实际上是随机发生的,但是生物的外部生存环境会通过生存与死亡让更能适应的个体存活下去。因此随着时间的推移,生物种群对环境的适应能力会越来越高。受到这个现象的启发,有人发明了遗传算法,通过模拟遗传的过程来解决一些优化问题。
继续阅读自制简单遗传算法实验

R 中大型数据集的回归

众所周知,R 是一个依赖于内存的软件,就是说一般情况下,数据集都会被整个地复制到内存之中再被处理。对于小型或者中型的数据集,这样处理当然没有什么问题。但是对于大型的数据集,例如网上抓取的金融类型时间序列数据或者一些日志数据,这样做就有很多因为内存不足导致的问题了。
继续阅读R 中大型数据集的回归