2009年4月16日星期四

The Stable Marriage Problem

稳定婚姻问题

这是从社会生活中过分简化、抽象出来的一个组合数学问题。参考:
http://www.cs.columbia.edu/~evs/intro/stable/writeup.html
http://zh.wikipedia.org/wiki/稳定婚姻问题

严格描述如下:
定义:
  • 考虑n个男人,用大写字母表示(X,Y,Z...)、n个女人,用小写字母表示(x,y,z...)
  • 每个人有一个异性的偏好列表,例如X(x>y>z...)表示X喜欢x胜过喜欢y,喜欢y胜过喜欢z...(静态严格全序,即不存在相等或不可比较的情况,可传递,且不随时间改变)
  • 一个婚姻表示为一个序对,例如Xx表示X与x结婚
  • 一个婚姻组合为所有男人到所有女人的一一对应,表示为n个婚姻,恰好没有人单身
  • 称一对男女(X, y)是不满的,若存在Y、x使得Xx、Yy、X(y>x)、y(X>Y)成立,也就是说,X和x结婚,Y和y结婚,但是X和y喜欢彼此胜过喜欢他们现有的配偶,所以X和y不满于现在的婚姻,存在重新组合的不稳定因素
  • 称一个婚姻组合是稳定的,若其中不包含不满的男女对
  • 一个稳定婚姻问题是指:给定n男n女和他们的偏好列表,问是否存在一个稳定的婚姻组合
定理:
  • 任何一个稳定婚姻问题的实例,都是"是"实例。进一步地,存在一个多项式时间算法,求出稳定婚姻问题的解。
算法(被称作求婚算法):
初始时所有男人和女人设为单身
每一步
任选一个当前单身的男人X
X向其列表中尚未标记为"拒绝"的、最喜欢的女人x求婚(其存在性在命题0中证明)
如果x单身,则Xx结婚,X从单身男人集合中移除
否则(存在Y,使得已经有Yx)如果x(X>Y),则Xx,Y放回单身男人集合并从Y的列表中标记x为"拒绝"
否则X留在单身男人集合中并从X的列表中标记x为"拒绝"
直到单身男人集合为空集(可终止性在命题1中证明)

命题0:上述算法每一步的男人X,都能找到可以求婚的x
证明:反证法,假设不然,也就是说这时候X的列表中所有女人都已经拒绝X了。注意到按照算法的构造,只有结过婚的女人才能拒绝男人,而且结过婚的女人只能改嫁不能返回单身,因此这时候所有女人都非单身,从而所有男人都已经结婚了,这与X还单身矛盾。假设不成立,原命题得证。

命题1:上述算法至多n+n^2步终止
证明:每一步要么有一个女人第一次结婚,要么有一个男人被拒绝,注意到n个男人的列表总长度为n^n,因此算法至多n+n^2步终止

命题2:算法的正确性:上述算法终止时,得到一个稳定的婚姻组合
证明:反证法,假设不然,算法终止时存在(X,y)不满,即Xx、Yy、X(y>x)、y(X>Y)
由于X(y>x),因此X向y求婚,发生在X向x求婚之前,而最终Xx,说明存在一个时刻,y拒绝或抛弃了X
若当时y拒绝了X,说明y的配偶Z在y心中比X好,即y(Z>X),而最终Yy,说明要么Y就是Z,要么y(Y>Z),从而都有y(Y>X),与假设y(X>Y)矛盾
若当时y抛弃了X,说明那时候有一个Z向y求婚,而且y(Z>X),而最终Yy,说明要么Y就是Z,要么y(Y>Z),从而都有y(Y>X),与假设y(X>Y)矛盾
得证。

应用:
这个算法北应用到大学联合招生、

2009年4月3日星期五

Technical Details in RBM for CF

Technical Details in RBM for CF
受限玻尔兹曼机的技术细节

参考
[1]http://www.netflixprize.com/community/viewtopic.php?id=1007
[2]http://todwang.blogspot.com/2009/03/understanding-rbm-for-cf.html
[3]http://www.iro.umontreal.ca/~lisa/twiki/bin/view.cgi/Public/DBNPseudoCode
[4]http://imonad.com/blog/2008/10/restricted-boltzmann-machine/
[5]http://www.ics.uci.edu/~welling/teaching/ICS273AFall06/NeuralNets273AFall06.ppt

Gibbs一步采样

在[2]中,我提到训练中要计算<vikhf>data和<vikhf>T,而按照[1]中的讨论,T通常取1,因为实践中发现T取大了也得不到更精确的解。因此,我们下面的讨论都是Gibbs一步采样。
这一步如何采,也有两种方式。[3]中<vikhf>1项中的hf使用了它的期望而不是采样值,而标准的Gibbs采样步骤这步也应该采样。[1]中的讨论中说,[3]的做法精度更好。而我实验发现,这两种方法效果差不多。[3]的具体做法在下一节中一起详细说明。

在线训练

Hinton那篇开创RBM for CF的文章中,用了Batch update weights的方法,也就是我[2]中解释的那样。而[1]讨论中发现,per-case-update(在线训练)也取得很好的效果。具体来说:
1、设trainning case v是一个M×K的0-1阵,表示一个用户的所有评分行为,vik=1表示该用户给电影i评分为k。
2、按照[2]中假设2采样得到隐层的F维0-1向量h,表示用户的特征。
3、按照[2]中假设1采样得到显层的M×K的0-1阵,记作v2,表示重构后的用户评分行为。
4、再按照[2]中假设2计算h的期望Eh,也是F维的向量,元素值取于区间[0,1]。
5、针对这一个trainning case v就可以更新W了:
W[i][k][f]+=LRATE * (v[i][k]*h[f]-v2[i][k]*Eh[f]),foreach i,k,f

利用稀疏性

在我的程序中,v使用了一种相对紧凑的数据结构,注意到v的列和总为1(如果此列不缺失的话)。
ur是一个二元组(mid, rate)的列表,长度和v的非缺失列个数sz相同,rate取值于K,它和v等价:v[ur[j].mid][ur[j].rate]=1恒成立,且v[i][k]=1当且仅当存在j<sz使得ur[j].mid=i,ur[j].rate=k。对应v2为结构ur2。
用这个结构改善上述第5步:
for j in sz
  note u as ur[j], u2 as ur2[j]
  foreach f
    W[u.mid][u.rate][f] += LRATE * h[f];
    W[u2.mid][u2.rate][f]-= LRATE * Eh[f];
这样一来,这一步的复杂度从MKF降到sz×F<<M×F了。

Bias设置与训练

[1]中讨论说hidden unit bias都设为零,也就是[2]中df设为0,visibel unit bias固定为先验概率分布的对数:bik=log(给电影i评k分的用户个数/给电影i有评分的用户数)。bik也可以一起在线训练:
bik+=<vik>data-<vik>T
利用稀疏性表示为:
for j in sz
  note u as ur[j], u2 as ur2[j]
  b[u.mid][u.rate]+=LRATE
  b[u2.mid][u2.rate]-=LRATE
我实践发现,visibel unit bias固定或训练效果差不多。

Weight Decay和Momentum

这是常见的梯度下降技巧,[5]中有详细的解释。
Weight Decay可以理解为一个弹簧,把每个weight拉回0点,防止权变太大:

其中lambda是充分小的正数。
W[u.mid][u.rate][f] += LRATE * (h[f]-WEIGHTDECAY*W[u.mid][u.rate][f]);
Momentum是动量项,用于加速梯度下降,有点自适应步长的意思。

其中γ为小于1的正数。
相当于这一步计算的权变化量不仅对这一步迭代有贡献,而且对以后都有贡献,不过贡献随着迭代的次数指数衰减罢了。
注意到,这两个技巧主要是针对Batch update weights的,用到在线训练中的效果不好估计。

退火

这也可以用在所有迭代学习算法中,主要随着收敛步长减小的格式。[1]中给出了一个反比例函数的降温格式。
lrate = LRATE/(1 + iter / (3 * U));
其中LRATE是初始步长,iter是用过的trainning case的个数。可见,迭代30轮(pass),步长就已经下降一个数量级了。

连续受限玻尔兹曼机

参考[4],注意到评分1,...,5原本是全序的,而不是K个无序的label,而发明RBM的初衷是用于模式分类,最后输出是一个离散label。因此引入连续受限玻尔兹曼机,是自然的。也就是显层向量v不是0-1的,而是连续取值的。这就要求更新[2]中的假设了,需要模型建立者重新假设条件概率分布,也就是重新定义整个贝叶斯网络。[4]引用的那篇Continuous RBM很有意思,用扩散网络建模,求解时用了随机微分方程。以后可以考虑做做这个方向。

结果

可能由于是随机算法,发现rmse随着迭代进行的下降过程有抖动,而不是严格单调的。
目前做到了probe rmse 0.9438 :迭代46步,其算法参数:
100个hidden unit,在线训练、固定bias、没有退火,lrate=0.001,WEIGHTDECAY=0.0001,没有用动量项。