1
2011-8-16 9:18:25    信息论  人工智能  信息论与熵 

继续阅读《信息论基础》一书,这回说到了第6章:博弈与数据压缩。这一章开始用信息熵来探讨一类非常不同的问题,这就是如何在博弈中挣钱。我们会看到,其实熵这个概念是和不确定性以及收益、价值这些概念深刻地联系到一起的。只不过我觉得这本书把这块知识安排到这个位置来讲很不合适,因为这个主题实际上是与我们通常理解的信息论,即编码和通信的理论是联系不大的。

为了更清楚地看出熵与收益之间的联系,书中举了一个赛马的例子。

赛马

假设在一场赛马中有m匹马参赛,令第i匹马获胜的概率为pi,如果第i匹马获胜,那么马民能够获得的收益是oi比1,也就是说如果你在这匹马上下注了100元的话,你就能获得100oi的收益。如果马民赢了会得到oi元的收益,如果输了就一分钱都得不到。假设某马民将其资金分散购买所有参赛的马匹的马票,bi表示其下注在第i匹马的资金占总资金的比例,那么bi>=0,并且Σbi=1,

这样,我们可以定义一个叫做相对收益的量,Si=bi oi来表示如果马民在第i匹马上下注比例bi,并且如果马匹i获胜了的话,他就能获得相对的收益Si,如果他对赛马总的下注资金是1000元,那么它的收益就是1000Si。很显然i能否获胜的概率是pi,因此Si也就是一个随机变量,我们关心的是Si的期望值。又因为Si是一个比例值,所以我们关心它的对数值的期望,

为此,我们定义一个叫做双倍率的变量为:

W(b,p)=E(logSi)=Σi=1mpilog(bioi)

这个定义是合理的。因为假设同样的一群赛马进行了n场独立的比赛(即第i匹马在任意一场比赛中获胜的比例始终是pi不变),并且在这n场比赛中,马民始终按照b1,b2,...,bi,...,bn的比例对这群赛马进行下注,而且每下注完一次马民都会把在这一场比赛中所获得的收益全部投注在下一场比赛中,比如说开始马民有1000元,第一场比赛他赢了1000bioi元,那么第二场比赛它就会按照总额为1000bioi的资金按照比例bi投注在这群赛马上。这样,n场比赛下来该马民的总收益就是:

Sni=1n Si=S1*S2*S3...

那么这n场比赛下来马民的总收益的对数平均值就是:

(logSn)/n=Σi=1npilog(Si)/n

根据大数定律,这个平均值在n趋于无穷大的时候,会趋近于随即变量log(Si)的数学期望也就是

(logSn)/n=Σi=1npilog(Si)/n→E(logSi)=W(b,p)

所以

Sn=2nW(b,p)

由此看出,Sn与W(b,p)有着等同的增减性质,如果要让收益最大化,只需要最大化双倍率W(b,p)即可。

信息熵

我们的问题是,马民应该如何下注才能获得最大的收益(也就是最大的双倍率)?下面我们就来求解这个优化问题。定义:

W*(p)=maxb W(b,p)=maxbi Σi=1mpilog(bioi)

需要满足的约束条件是:

 Σi=1mbi=1

于是,利用Langrange乘子法,原问题化为无求条件极值:

J(b)=Σpilog(bioi) +λΣbi

所以:

∂J/∂bi=pi/bi+λ=0 bi=-pi

而根据 Σbi=1,得到λ=-1,所以

bi=pi

也就是说,如果按照每匹马获胜的概率来对这m匹马下注的话,马民能获得最大的收益,并且这个时候最优的双倍率是:

W*(p)=Σpilogoi+Σpilogpi=C-H(p)

最优的双倍率W*(p)与信息熵H(p)之和为一个常数Σpilogoi,我们看到了一种马民所获得的收益以及信息熵之间的对偶关系,从这个公式上可以说,马民在赛马中获得的最优收益不是别的,恰恰是该赛马比赛所带来的负熵(信息)。

所以,双倍率W(b,p)是一个非常重要的量,它实际上还可以写成下面的形式:

W(b,p)=Σpilog(bi/pi * pi/oi) =Σpilog(bi/pi)+Σpilog(pi/oi)=D(p||o)-D(p||b)

其中D(p||b)=Σpilog(pi/bi)表示的是两个概率分布pi与bi之间的Kullback-Leibler距离(也叫相对熵),参见本书第一章。因此,上面的公式就可以概括为双倍率就是赛马获胜概率的真实分布pi与它们的兑换比例分布oi之间的距离与真实分布pi与马民对各种马进行下注的比例分布bi之间的距离之差。所以马民只有通过提高D(p||b)这一项,使得自己的投资比例分不仅可能靠近真实的概率分布来提高它自己的收益。

这一章最吸引我的地方在于它让我们看到信息熵与收益之间的深刻联系。在经济学中,价值是一种重要的概念,但是它始终没有一个合理的定义,也许通过研究信息论,我们可以为经济学中的价值概念奠定基础。在本章的赛马的例子中我们看到,其实价值、收益、风险、信息熵这些概念是深刻地联系在一起的。

扩展1:做中学

虽然本书的这一章后续部分还有很多展开的讨论,包括信息压缩与博弈之间的关系,英文的熵率等问题,但是我个人觉得这样的内容编排并不是很好(也许这是本书最大的败笔之处)。与其照本宣科讲述原书的内容,不如我们来做一些更加有趣一些的探讨。

在上述内容中,我们已经知道马民如果要想获得最大的收益就必须使得他的下注分布尽可能地靠近这些马获胜概率的真实概率分布。在这个推理过程中,我们是假设这个真实的概率分布是一个已知的概念,然而在现实生活中,马民往往并不能获得有关pi的真实信息。他们只能通过观测来获得有关pi的采样数据。比如,如果我们让这m匹马比赛N次,我们可以计算出来任意一匹马在这N次比赛中的获胜次数ni,于是我们会用ni/N来估计pi,这样,根据大数定律,当N趋向无穷的时候,经验估计ni/N就会越来越趋近于真实的pi了。那么根据这些估计的值,马民再来调整自己的下注比例bi,就有可能达到最优的收益。

可是,现实中的情况却是,马民并不可能真的保持投资策略bi不变而让这群马比赛N次,他们必须边试验边投资,在做的过程中学习。并且还要保证最后的收益足够大。那么,马民应该采取一种怎样的动态投资策略,使得他能够在尽可能短的时间里面学习到有用的知识而又能保证自己的投资不失误呢?

我们不妨做这样一种表述:假设一个马民进行总共N场赛马的比赛,并且它的投注策略交给一个机器自动执行,他一共有T<N次更改自己策略的机会,那么他应该如何分配这T次更改机会呢?

也就是说,该马民有T个时间点的序列t1<t2<...<tT,在任意一个时间点tj上,马民就可以根据前面的tj次赛马的比赛结果(也就是每批马获胜次数的经验分布ni/N)来调整自己的投资策略。假设马民就是根据贝叶斯准则来调整自己的投资策略,也就是根据公式:

b′i=biP(ni|bi)/ΣbbP(ni|b)

其中ni为前tj次赛马的经验比赛结果,即第i匹马的获胜的次数,bi为调整策略前的投资到第i匹马的策略,b′i为调整后的投资到i上的策略。P(ni|bi)表示假设第i匹马的获胜概率是bi的话,那么得到结果ni的概率,它显然与tj有关,ΣbbP(ni|b)表示对所有可能导致结果ni的情况进行概率求和。这样给定了策略调整方法,我们实际上就能得到一个投资分布的动力学,因此就会得到一个最后的总收益。那么究竟如何分配tj这些时间点使得最后的总收益最大呢?这是一个很有趣的数学问题,有兴趣的朋友不妨对此进行一些探讨。

扩展1:多人博弈

在最优双倍率的表达式中:

W*(p)=Σpilogoi+Σpilogpi

我们知道oi表示的是每批赛马的回报比例,也就是说如果你押在赛马i上面的钱是bi,那么如果i赢了,你就能得到回报bi oi。在前面的讨论中,我们一直假设oi不变。但是,在现实的赛马(或者股票市场)中,oi显然与其它的马民在这m匹马上的下注总额有关的。比如,一个赛马的规则是:假如有N个马民,每个人j都投资m匹马,并得到分布bij,每个人的投资总额是I1,I2,...,IN,这样整个赛马场中的投资总额就是:

I=ΣjIj

第j个马民在第i匹马上面的投资额就是:

Yij=Ij*bij

如果在比赛中第i匹马获胜,那么赛马场按照如下原则分配这些马民的财富:将所有的财富都分配给投资到第i匹赛马上的马民,并且按照他们投资的比例进行分配,也就是赛马i能够给马民j的回报比率是:

oij=(I YijjYij)/bij=IjΣsIssIsbis

假如所有马民的总的赌博投资额都一样,也就是Ij=c,那么:

oi=I /Σsbis

也就是说第i匹马给任何一个马民带来的回报率取决于所有其他马民对该马的下注比例,如果别人的投资比例的和越小,那么第i匹马给马民的回报率也就越大。在这种情况下,这N个马民就会进行一场非常有趣的博弈。我们完全可以做出一个多Agent的模拟程序来模拟这N个人对m匹马的赌博游戏。

 

2013年初,我们举办了这一章的读书会,有关问题的后续讨论参见:http://www.swarma.org/swarma/detail.php?id=18399

 

2011-8-18 14:04:00
   这个很有意思,跟那位兄弟贴的自动交易法有些像啊。


>zcard200在回复:《信息论基础》第6章——博弈与数据压缩中写道:
---------------------------

很多东西,我喜欢比较平实的叙述方法。有一本书是介绍 威利公式的,里面就比较简单的解释了 关于这样的东西。我把那个内容说下,看看大家是否有启示。

有两匹马进行赛马比赛,......

 

2014-01-01 03:56:59
   “又因为Si是一个比例值,所以我们关心它的对数值的期望” 为什么比例的期望要用对数呢?

2014-01-06 19:38:42
   那是因为可以把乘法变成加法,除法变成减法。
2015-10-12 07:26:31
   Jake,你好!我想请教一下这个问题和凯利公式http://www.360doc.com/content/15/0901/18/27469688_496295844.shtml得出的结论好像是不一致的.我想问到底哪一个才是比较接近实际情况.我认为这一步有点问题.""比赛它就会按照总额为1000bioi的资金按照比例bi投注在这群赛马上。这样,n场比赛下来该马民的总收益就是:

Sni=1n Si=S1*S2*S3...""

这个Sn不能这样算吧,因为如果某一次输掉了就不正确了,不知道是我没看明白还是这里真的有问题,请指点迷津,谢谢!

2015-10-13 11:32:54
   问题的性质应该是不一样的。这里面一个容易让人误解的地方是,那个i指标到底指代不同的马还是不同的比赛。事实上,bi指代的是i这匹马的投资比例。而每一个周期,投资人都会按照一定比例投资到1,2,3.。。。,m匹马上面。在这样一个分布下,即使马i输掉了,投资人的收益也不是0,因为他还投资了别的马了。

这样,给定固定的bi,我可以运行N轮,每一轮赚取收益为Sj,注意这里的j是时间轮次指标。
2015-10-22 14:23:27
   Jake,你好!谢谢你的回答.但我还是不太理解.举个实例,有10匹实力相同马在进行多次比赛,投资中了赢的马的赔率是1:7(即投资1块拿回7块),那按照这个理论应该怎样下注,谢谢!
2015-10-31 06:33:32
   10匹相同的马那自然是所有的马都投资同样的钱了。
2015-11-01 04:11:46
   Jake,但按照这个方法下下去只会慢慢亏钱,直到亏光.我想问在我的假设下有没有办法可以持续赚钱.
2015-11-17 08:55:31
    Jake,但按照这个方法下下去只会慢慢亏钱,直到亏光.我想问在我的假设下有没有办法可以持续赚钱.
登录后才可以评论,马上登录
2012-2022 www.swarma.org, all rights reserved