王元涛的Blog
wangyuantao@msn.com
2013年4月5日星期五
use window.postMessage to hack a page
2013年3月9日星期六
the center of gravity of affinity parameters locates in the origin
Modeling
$I$ users, $F$ features and $C$ categories.Training data: $x_{if}$ is the feature value of user $i$ for feature $f$. $x_{i}$ is the feature vector of user $i$.
Labeling: $y_{ic}$ is the category value of user $i$ for category $c$, for binary categorization, it is in $\{0, 1\}$. In weighed/generalized model, it can be any real number.
Take $\beta_{fc}$ as the affinity parameter (to train) between feature $f$ and category $c$. $\beta_{c}$ is the feature vector of category $c$.
Scoring
$p_{ic}$ is the probability that user $i$ belongs to category $c$.$p_{ic} \propto e^{x_{i}\beta_{c}}$
Since $\sum_c{p_{ic}}=1$, we have $p_{ic}=\frac{e^{x_{i}\beta_{c}}}{\sum_c{e^{x_{i}\beta_{c}}}}$
We also take $p_{ic}$ as the score of user $i$ for category $c$.
Maximize Likelihood
The likelihood of $\beta$ is$L(\beta) = \prod_{i,c}{p_{ic}^{y_{ic}}}$
$- ln(L(\beta)) = - \sum_{i,c}{y_{ic}ln(p_{ic})}$
With L2 regularization, we will minimize:
$$\Phi(\beta)= \frac{1}{2}\|\beta\|^2 - \sum_{i,c}{y_{ic}ln(p_{ic})}$$ Calculate the derivative:
Fixing any $f_0 < F, c_0 < C$ $$ \frac{\partial\Phi(\beta)}{\partial \beta_{f_0 c_0}} =\beta_{f_0 c_0} - \sum_{i,c}\frac{y_{ic}}{p_{ic}}\frac{\partial p_{ic}}{\partial \beta_{f_0 c_0}} $$ Where $$ \begin{align*} \frac{\partial p_{ic}}{\partial \beta_{f_0 c_0}} &=\frac{1_{c=c_0} e^{x_{i}\beta_{c}} x_{if_0} \sum_c{e^{x_{i}\beta_{c}}} - e^{x_{i}\beta_{c}} e^{x_{i}\beta_{c_0}} x_{if_0}}{(\sum_c{e^{x_{i}\beta_{c}}})^2} \\ &=1_{c=c_0} p_{ic} x_{if_0} - p_{ic} \frac{e^{x_{i}\beta_{c_0}}}{\sum_c{e^{x_{i}\beta_{c}}}} x_{if_0} \\ &=p_{ic} x_{if_0} (1_{c=c_0} - p_{ic_0}) \end{align*} $$ So $$ \begin{align*} \frac{\partial\Phi(\beta)}{\partial \beta_{f_0 c_0}} &=\beta_{f_0 c_0} - \sum_{i,c}{y_{ic} x_{if_0} (1_{c=c_0} - p_{ic_0})} \\ &=\beta_{f_0 c_0} - \sum_{i}{x_{if_0} (y_{ic_0} - p_{ic_0} \sum_c{y_{ic}})} \end{align*} $$
Lemma 1
Take $\sum_c{y_{ic}}=1$ and ignor regulizer $\beta_{f_0 c_0}$, $$\frac{\partial\Phi(\beta)}{\partial \beta_{f_0 c_0}}=- \sum_{i}{x_{if_0} (y_{ic_0} - p_{ic_0})}$$ If we under score category $c_0$ for all users, that is to say $$p_{ic_0} < y_{ic_0}$$ Then $$\frac{\partial\Phi(\beta)}{\partial \beta_{f_0 c_0}} < 0$$ So we should enlarge $\beta_{f_0 c_0}$Lemma 2
If $\beta$ is the local minimization point $$\frac{\partial\Phi(\beta)}{\partial \beta_{f_0 c_0}} = 0 , \forall f_0, c_0$$ That is to say $$\beta_{f_0 c_0} = \sum_{i}{x_{if_0} (y_{ic_0} - p_{ic_0} \sum_c{y_{ic}})} , \forall f_0, c_0$$ Summarize over all $c_0$, we have $$\sum_{c_0}{\beta_{f_0 c_0}} = \sum_{i}{x_{if_0}(\sum_{c_0}{y_{ic_0}} - \sum_{c_0}{p_{ic_0}} \sum_c{y_{ic}})} = 0, \forall f_0$$ It means: as long as we have L2 regularization, no matter if $\sum_c{y_{ic}}=1$, the center of gravity of affinity parameters locates in the origin.2013年2月3日星期日
2012年12月25日星期二
Fwd: surface试用小计
2012年12月1日星期六
推荐系统论坛2012参后感
Facebook开篇就提到做unified organic and sponsored recommendation。这恰恰是session亮点和我一直以来的梦想:将广告和推荐结合起来。从某种角度上说,内容推荐是Facebook自己作为广告商的广告,目的是让用户在Facebook上更活跃。基于此,他们建立了统一的优化目标,而不是向淘宝那样广告部和推荐部掐架。
给定用户和上下文:
max predicted CTR * (ad bid + p * click value)
predicted CTR是用户在当前上下文点击被推荐对象的概率。
ad bid是广告投标价格。
p是神奇的pacing parameter,通过一个负反馈系统在线动态调整。
click value是点击被推荐对象对Facebook的价值,反映了Facebook的长期利益。计算方法大致是推荐对象给用户在当前上下文带来的相对边际收益。比如给一个只有2个好友的用户推荐一个好友的相对边际收益是50%,给一个有1000个好友的用户推荐一个好友的相对边际收益是0.1%。
假设Facebook的Inventory也就是右侧栏广告位要被Facebook用于投资,短线投资回报快风险小,也就是卖给广告商在这里打广告,但是要牺牲长远利益即用户体验,长线投资回报慢风险高,也就是内容推荐。所谓Facebook决策者的投资组合,就是设定一个threshold三七开还是二八开,当organic spend > total spend * threshold 时,p减小,反之增加。这样就可以让投资比例稳定在设定值上了。这里非常天才的一点在于,p无需人工设定,系统可以自己收敛到一个稳定值,同时完成量纲转化,鬼知道click value是个什么物理量,和ad bid怎么比。
另外,关于如何向广告商收费。为了防止广告商和广告系统无聊地在线博弈,Facebook采用了符合经济学原理的方式:在Facebook投放广告的价格等于Facebook投放他的机会成本,也就是说,因为投放了你,系统受到多大损失。实现的时候,相当于系统处理两个recommandation request,第一个是有你的情况下,计算按照上述算法推荐的投资组合的收益,第二个request假装没有你,计算投资组合的收益,两者求差,就是机会成本。好像有一套叫VCG的理论支撑这个拍卖模型。
一个好的广告,不仅有ad bid带来的短期价值,还有click value带来的长期价值。好的生态是用户在Facebook上和广告商互动生产内容。
模型:Logistic Regression,理由,大量feature,在线更新。牺牲准确性,应对快速变化,因为需要推荐的对象类型五花八门层出不穷,例如照片,游戏应用等等。
几个特别好用的feature
上次点击这种类型推荐对象的时间到现在的时间间隔。刚点过一段时间不会再点了,但是过一段时间还有可能点。Bucket feature。
上下文类型,比如在照片页面推荐照片,就比较好。
基础设施:hive, scribe,不同的索引用不同的硬件,小一点的用memcached,大一点的用flash disk。
一些数字:
在线更新model时间间隔:30分钟。带来收益约3%。
每个user有billion量级的待推荐对象。
统一organic recommand和sponsored recommand之后,user活跃度上升10%,广告收益也上升10%。
Hulu
在视频里面放弃一些广告位,推荐内容。
推荐相关度直接弹窗问用户,CTR不靠谱。
当全站使用推荐系统时,它将影响用户行为习惯,从而反过来影响自身。就好像成为一个隐函数。不再是y=f(x),而是g(x,y)=0
腾讯
模糊集从公理出发三步就能推出悖论。
百度
技术悲观主义。
2012年9月15日星期六
My Adventure to "Wacity"
人上了岁数就爱怀旧。周末一个人在家无聊,整理资料,翻出来一篇2005年的英语写作课的作业。发现自己年轻的时候想象力真犀利啊。
My Adventure to "Wacity"
I would like to tell you about my adventure to a wacity last Friday, which was very exciting.
I am a farmer in 31 century, and now the scientists can enable people to breathe and live in the water as in the air. So years ago, my family emigrate to a village down the sea, earning lives by growing coral.
Last Friday, when I was working on my coral farm, a shark came out toward to me quickly. I felt so terrified that I hurried jumped into my wajeep (the jeep in water) and escaped away. I speeded it up to the limit, but still couldn't get rid of the shark, which was chasing me nearer and nearer. I do not know how far did I rush, until there came across a watruck suddenly and knocked mine down.
When I woke up, I found myself in a wacity I had never been. My wajeep was gone, and so was the shark. A huge tube appeared in my sight, with a hole on it. I swam to the hold curiously, and when I was at a distance about one meter away, there came an enormous force absorbing me into it! "Hey, where are you from, freshman?" someone asked me. "Coral land" I replied," and what it is, I mean this tube?" "Wahighway." "Wa-highway? But where are the wacars?" At the moment I asked that foolish question, the water in the tube began to flow toward a direction. All the people in the tube, no, the wahighway, floated following the stream. Then I saw what the wahighway meant. "Where are we going?" I asked that man. "The centre of the wacity." he answered.
"Nice," I said to myself, "There I will find the police station and ask them to help me back home!"
When the stream stopped, there opened a hole on the tube. "Excuse me, can you tell me where the nearest police station is please?" I asked an old woman in the street, having come out of the tube. "Well, young man, go along this street and turn left at the first cross, and then turn up at the corner. Then you will find it." "Thank you madam, but what do you mean by 'turn up'?" "You see, in a wacross, we have five choices, instead of three as cross on the ground. You can turn left or right, up or down, or go ahead. Do you understand?" "I've got it, here we have three dimensions! Thank you very much!"
Several minutes later, I arrived at the police station building. I search around it but didn't find any door! I pondered for a while, and then I opened a window and got into it for help. "This wacity must be designed by Microsoft, or everyone here has got used to windows," I thought associate with the hole on the wahighway tube. In the station, the police officers offered me a lunch, and in the afternoon, they send me back.
"Thanks for the shark, or I won't know there is a wacity in the world!" I thought to myself on my way home.