谷歌工作推荐

2015年毕业的同学马上就要开始准备找工作了。
我可以推荐一些优秀的应届毕业生面试谷歌。大陆毕业的同学也可以直接申请谷歌总部的职位。
如果你是社招,也可以找我推荐。
目前仅限Software Engineer这个职位,当然这个职位其实很宽泛。

是否需要找人推荐?
只要你希望拿到谷歌的offer,你就一定需要找人推荐。
找人推荐可以优先选择面试时间,会被谷歌重点关注。负责的推荐人也会提供一些准备面试的方法。
请尽早找人推荐,以便优先选择面试的大致时间点,以及尽早做准备。即使现在推荐,你也可以选择几个月之后等你喜欢的时间点面试。

是否需要找我推荐?
从我的角度来说:如果你有能力拿到offer,欢迎找我推荐。
从你的角度来说:请找一个对你熟悉的谷歌员工或准员工推荐。推荐候选人需要如实的附上一些非常具体的评价,其中包括对候选人的了解程度。因此一个熟悉你的人,所提供的评价会更真实可信,增加拿到offer的可能性。如果你觉得我对你熟悉,请找我推荐。否则,请找其他人推荐。如果你实在找不到熟悉你的人推荐,欢迎找我试试。

什么样的人容易被推荐?
我个人认为的一些加分项包括但不限于:
1)有一定份量的奖项;
2)有一定份量的奖学金;
3)开源项目,或其他有意思的项目;
4)领导能力,团队合作经验;
5)技术博客;
6)英语口语能力(如果申请总部职位);
7)有意思的研究经历;
8)过硬的编程能力;
9)过硬的学习能力。
对于以上提到的这些,最好能有具体的事例佐证。当然,每一条都不是必须的,但一条都沾不上就非常危险。
每个人的情况都不一样,如果你有特殊的闪光点,也是可以的。

如何找我推荐?
请在慎重考虑后,尽早找我推荐。
我尚未入职,还没有公司邮箱。请将英文简历PDF发至这个邮箱 diaorui1987 at gmail.com
请补充一些必要的文字说明到邮件正文中。如果我们认识,正文适当简写即可。

我会如何处理你的简历?
每个人能推荐的候选人总数是非常有限的,所以我不可能来者不拒。
如果我不打算推荐你的简历,我会告诉你,也会尽可能给一些建议。
如果我有可能推荐你的简历,我会与你进一步沟通。
如果我确定推荐你的简历,我会提供力所能及的帮助。

从回转寿司到数值代数

最近一直在写毕业论文, 也想不起来更新博客. 发现很久没写了, 上来补一篇.
过年的时候和好友聚餐, 去吃回转寿司(配图从网上随便找的, 非去过的店铺, 仅供参考). 回转寿司里有一个很长的转盘, 厨师把寿司放到传送带上, 然后传送带不断旋转, 这样顾客能够随意挑选自己想要的寿司.

我的好朋友吃饱了以后就开始犯强迫症了. 他看转盘上的寿司摆放不均匀, 每次看到一个寿司到左边的寿司和到右边的寿司距离不相等, 他就把那个寿司挪一下位置, 让它刚好在左右两个寿司的正中间. 挪着挪着他就问我: 你说我这么一直挪着, 如果没其他人放寿司或者拿走寿司, 最终这些寿司能摆放均匀么?
我说我感觉上可以, 他也说感觉上可以. 我们怎么证明呢? 当时给了他一个解答, 后来又想到一个更有意思的解答. 仅仅用到一些数值代数知识.
记我们有$n$个寿司, 顺时针或者逆时针顺序编号, 第$i$个寿司到第$i+1$个寿司的距离是$d_{i}$. 因为是个转盘, 所以第$n+1$个寿司实际上就是第$1$个寿司, 为了描述方便, 后面凡出现$n+1$的时候都认为是$1$, 这样就不用特殊说明了. 另外$d_{1}+d_{2}+\cdots+d_{n}=L$, 也即转盘长度. 我好友的操作实际上就是对向量$d$左乘一个矩阵. 举个例子来说明一下, 为了写着方便, 以$n=3$为例, 他只会有挪动三个寿司的操作, 也就是三种不同操作, 分别相当于对$d$左乘的矩阵是这三种:
$
\left(
\begin{array}{ccc}
0.5 & 0.5 &0 \\
0.5& 0.5 &0 \\
0 & 0 & 1
\end{array}
\right)
$,
$
\left(
\begin{array}{ccc}
1 & 0 & 0 \\
0 & 0.5 & 0.5 \\
0 & 0.5& 0.5
\end{array}
\right)
$,
$
\left(
\begin{array}{ccc}
0.5 & 0 & 0.5 \\
0 & 1 &0 \\
0.5 & 0 & 0.5
\end{array}
\right)
$.
这种矩阵有什么特点? 稍微变型一下. 我们定义$n$个列向量$u_1, u_2, \ldots, u_n$: 其中$u_i$是这个样子的, 他的第$i$个分量是$1/\sqrt{2}$, 第$i+1$个分量是$-1/\sqrt{2}$, 其余分量全是$0$. 于是可以验证前面提到的矩阵实际上可以写成这样: $I-u_1u_1^T, I-u_2u_2^T, \ldots, I-u_nu_n^T$. 这个非常像Householder变换. 因为这几个矩阵都差不多, 我们拿出其中一个$I-u_iu_i^T$来分析一下.
很显然$I-u_iu_i^T$的秩是$n-1$, 它有唯一一个$0$特征值, $u_i$就是它的特征向量. 而其余特征值都是$1$.
我们需要想办法说明, 每一次挪动寿司都会导致一个量发生不可逆的变化, 这样才能证明, 不会操作了半天又退回到某个状态. 这里我们用向量的模长.
对于任意一个向量$d$, 如果将$I-u_iu_i^T$左乘$d$, 那么$d$的模长会变小, 除非$d$和$u_i$垂直. 具体是这样的:
$\| (I-u_iu_i^T)d \|^2 = \| d – u_iu_i^Td \|^2 = d^Td – 2(u_i^Td)^2 + (u_i^Td)^2 = d^Td – (u_i^Td)^2$
所以, 除非$d$和所有的$u_1,u_2,\ldots,u_n$都垂直, 否则在这$n$个矩阵的轮流作用下, $d$肯定是会一直变化的, 因为他模长变小了. 收敛到什么状态呢? 那就是$d$和所有的$u_1,u_2,\ldots,u_n$都垂直, 所以我们来看他们一列列堆起来构成的矩阵 $M=(u_1, u_2, \ldots, u_n)$, 如果收敛了, 只能是$M^Td=0$. 很显然$M$这个矩阵的秩至少是$n-1$, 因为我们观察他的前$n-1$列, 第$i$列的第$i$行元素非零, 其他列的那一行却是$0$, 所以线性无关. 因此$M^Td=0$的解空间至多是一维的. 容易找到一组解是$(1,1,\ldots,1)^T$, 所以所有解都是它的常数倍. 因此不停操作, 不停左乘矩阵, 不停迭代, 最终收敛到所有分量都相等, 也就是相邻寿司之间的距离都相等.
那从$d$出发开始迭代, 收敛到什么状态呢. 可以发现$d_1 + d_2 + \ldots + d_n=L$这个在操作过程中是保持不变的. 实际上看, 寿司距离加起来肯定永远是转盘长度. 从计算上看, 如果定义$e$是各个维度全是$1$的向量, 可以验证$e^T u_i = 0$ , 所以 $e^T (I-u_i u_i^T) d = e^T d – e^T u_i u_i^T d = e^Td = L $ , 这个就说明在每次变化后, $d_1 + d_2 + \ldots + d_n$不变. 所以最终收敛的时候, $d_i = L / n$.
也就是说, 经过我好友的不懈努力, 最终是可以让所有寿司均匀摆放的!

找工作总结

明年毕业,找工作目前已告一段落,做一个总结。

面试过的公司共八家,按照第一轮面试的时间顺序分别是:淘宝、百度、华为、美团、谷歌、京东、葫芦、有道。
最终选择谷歌总部,这其实是之前不在考虑范围的一个选择。

我的情况
我专业是计算数学,研究方向是最优化计算方法。
因为和大部分应聘者的背景不同,简历里面会有半页纸可能面试官也看不懂写的是啥。当然,因为毕竟占了简历不小篇幅,面试一般还是会问一下的。一般我会讲讲问题是什么,算法设计和改进思路是什么。大致上还是可以讲清楚的。
我因为有ACM竞赛经历,加上后来自己学了很多计算机相关知识,如果面试官没看简历(有的面试官是直接问问题的),只要别问到类似TCP/IP什么的问题,很基础但属于我没兴趣学的,很可能会误以为我是计算机系。

关于数学系应聘IT公司
一般来讲这不是个主流的选择,主流选择应当是去高校和研究所继续做相关研究,而不是去抢别的专业人的饭碗。
关于数学系进IT公司,我一个本科同学的评价是:大多数人入职前半年都是需要学习各种基本知识的,但一般学的比较快。
这个看法我觉得比较可信。以下是三种数学系学生应聘IT公司可能会有的奇葩状况。
1,如果某个基本概念没听说过,面试官可能会一惊,然后觉得你这个人基础太差而pass掉。
2,如果某个基本概念没听说过,面试官惊讶过后解释了一下这个概念,然后问一个相关的问题,如果很快就答出来了,面试官会觉得这人真聪明。
3,如果问过的问题都表示知道,会被面试官误以为是计算机专业,于是被按照计算机专业标准要求。实际上不一定达得到计算机专业优秀学生的标准,于是就悲剧了。

选择工作的出发点
投IT相关公司,具体没什么大的倾向性。关注点有
1,和mm的上班地点近(但是她也明年毕业,工作还没定);
2,稍微用上点算法,用的多则更好,算法最好和优化有关,比如机器学习;
3,薪水符合预期。
我没有对任何一家公司表示我很想去,这很可能是部分公司面完终面都没告诉我是否有offer的原因之一。因为我不清楚我这个背景去哪里对自己更合适,更多的是抱着试试看的心理。
我平时除了和mm聊这些公司以外,其他大部分时候都是在QQ上和其他专业的人聊这些公司,所以不敢说有多了解,基本也都是网上看的。因为学计算数学的一般还是去研究所和高校的占主流,这也是最应该去的地方。即使去公司一般也是IBM这种类型的公司,一年也没有一两个人。查了一下我们所上一届就一个人去公司。有的面试官似乎觉得我对公司没有明确偏好很不可思议……去看看数学系往届都去哪就觉得没什么不可思议了,我投的公司已经是我们所应届生似乎从来没去过的了,我觉得这一点上看已经够明确了,我没有更好的分辨能力了。
但学统计的去IT公司的好像多一些,那我就不太了解了。

选择出国
我最早是不考虑出国的,这也是我没有投Facebook的原因。
不出国的原因有三个:重新融入一堆陌生人的圈子;出国生活不容易习惯;我mm之前的出国访问签证有回国居住两年的限制。
我其实比较在乎和mm的上班地点距离近,如果选择出国反而逃避了这个事情。如果我们的上班地点之间坐车太久,即使对各自职业发展有好处,也会非常纠结。
我投的公司只有谷歌一家有出国的选择,因为也有北京的选择才投的,而且也没觉得一定会拿到offer,后来HR说很有可能有offer的时候反而就纠结了,9月最后几天一直在纠结。感觉就是意外有了一个offer要出国,而之前从来没做过这个打算。最后决定选择谷歌总部主要原因也不是为了职业发展和薪资,更多是为了环境好,联想到之前身边发生的某些事情(具体就不说了),觉得环境好还是很重要的。
选择出国还一个风险是最近两年H1B签证配额紧缺,都需要抽签,如果没抽中的话就需要在国内等一年,这我倒是无所谓,正好可以等mm一年。

各个公司的面试情况

  • 淘宝
    淘宝是走的提前批,非常早,上学期面试的。部门是阿里妈妈,做在线广告的。实际上不是自己投的,是严强推荐的,他去年进了袁全那个组,也推荐我去。我在面试之前对阿里妈妈基本没有什么了解。这个部门在阿里里面似乎是比较受重视的,因为在线广告是阿里盈利的很大一部分,阿里妈妈的技术团队基本都在北京,大约有几百人。他们已经有一些比较成熟的技术了,但也还有很多事情可做,无论是工程还是算法,应该对成长比较有利,里面硕士博士不少。
    第一次去时总共有两轮面试,之后过了一阵子通知我去终面,终面是章文嵩面的,随便一搜就知道他是超级大牛,在开源软件上做过很大贡献。从聊天中感觉他对阿里未来前景非常看好,很有活力的一个大牛。
    整个面试过程比较顺利,应该会有special offer,但是我猜测由于今年阿里北京招聘规模太大等众所周知的原因,目前还没有收到正式offer,不知道网传的薪水是否真实。
  • 百度
    同样投的是提前批,上学期有一阵子在小圈子里传出一个邮箱地址,投了简历就可能参加提前批面试。总共三面,一个下午面完的。面试的那个组是做百度知道、百度文库等产品的推荐系统,问了很多想法题,他们做的东西还是挺有挑战性的。
    9月底收到offer,是普通offer,而且薪水基本和硕士普通offer差不多,虽然这是第一个offer,由于和预期不符,还是没有签,觉得会等到更好的offer。
  • 华为
    这是唯一一个面试过程比较奇葩的公司,以至于我不知道他们到底要什么样的人。
    华为的博士招聘和本科硕士是分开的,博士在8月招。面试基本没有讨论任何学术或技术相关的问题,全是聊天。一面的时候就问类似“如果给你offer,你来的可能性有多大”这种问题,我直接愣了。问了其他数学专业的同学,面试也是几乎一样的过程。
    第一次面了一面,然后回去做在线心理测试,然后又面了一面,目前没有下文,个人估计挂了。
  • 美团
    之前有一些了解,觉得现在发展势头还挺不错的。8月底在网上看到校招内推,里面有提到算法工程师,于是抱着好奇的心理问了问在里面工作的wzc1989,然后他给我推荐了一下,很快就面试了。一共三面,第三面类似聊天。他们今年是第一年找算法工程师,目前相对其他大公司来讲还处于起步阶段,可做的事情很多。9月底HR来电询问找工作近况,没有说是否有offer。
    三面的面试官是我本科隔壁学校的ACMer,他说如果有同学合适的可以推荐去面试看看。我后来跟两个本科ACM协会的同学提到可以去面美团,不过他们都不感兴趣。
  • 谷歌
    原计划只申请国内的职位,而北京的部门感兴趣程度有限,曾经一度认为去的可能性不太大。但申请职位的时候选择的是中国或美国,反正多选又没坏处。
    谷歌每次去都是两面,基本上在同一周内就会得到通知是否要继续面试。HR很nice,会提醒面试大致流程,建议做一些准备什么的,如果有英文面试也会事先告诉。我面了四面的时候刚刚8月底,然后HR说我系统设计题面的非常一般,需要加面,建议我好好准备一下,第五面可以安排晚一些,于是第五面定在了中秋节那一周。他知道我数学专业的,设计模式和面向对象都不了解,让我好好看一下相关的书。第五面面完之后他提交总部review,并建议我考虑美国的职位,因为北京的职位非常少,需要排队等着。之后纠结了很久,以至于有几天晚上都睡不着觉,最终还是选了美国的职位。10月1日电话通知获得offer以及offer的细节,10月8日签了。
  • 京东
    一开始完全没考虑过这个公司,因为校招职位里面都没有提到算法,而且也不认识谁在里面工作。
    后来在微博上收到刘思喆的私信,他说京东也有推荐系统和在线广告方面的职位,只是这类职位一般不校招。然后他推荐我投了简历。第一次去面了四面,第二次去面了一面HR。京东最大的优势大概是发展空间大一些,这点可能和美团类似。目前还没有通知是否有offer。
  • 葫芦
    我个人挺喜欢的公司,是个视频网站,用机器学习很多,非典型美企,因为技术部门都在北京。据说投简历的人少,因为知道的人就少。葫芦是挺适合博士去的公司,当然也有不少人硕士本科。可能属于那种小而美的公司,规模不大,很多清华帮,以往招聘都是小道消息传出来的,没大规模宣传,现在稍微宣传一些了。面试风格和谷歌类似。
    这家公司是我面试体验最好的一个。一共三面,一个下午面完,一面一小时,据说也有可能会四面,不知道是不是根据面试情况决定。也是唯一一家公司问了我很多机器学习的算法问题,应该是博士才会问这些。可能因为我之前强调过我是数学系,一面都是先问我关于xxx,你知道些什么,然后才针对性的问我问题。二面是考算法和代码。第三面接近聊天,期间讨论了一个他们实际遇到并已经解决了的一个问题。
    转天就通知我终面,然后再转天去面终面,基本就是聊意向,没有技术问题。joycezhang在嗓子哑了的情况下还是来跟我聊了一小会,真不好意思。
    有说法认为葫芦比谷歌要难进。目前也没告诉我是否有offer。
  • 有道
    传闻有道很多清华帮,很多人跳槽去谷歌,挺锻炼人的,也是小而美的感觉。不过现在可能不如以前了,搜索换成了360,有道饭饭搞了没多久就不搞了。不过还是觉得值得一试。这是我唯一一个参加了校招笔试的公司,其他内推也要笔试的都没去了。据说有道只有极少数人内推不用笔试。笔试完了以后,9月底面了一面,十月初通知二面,我因为已经有offer就拒掉了。

一些没有投简历的公司
Facebook没投是因为一开始没打算出国。
还有一些公司其实投了,但是内推也要笔试就没去……
另外提一下两个例外,微软和腾讯。

  • 微软
    我个人对微软已经累觉不爱。我08年在MSRA实习过,虽然这么多年过去,连实习带我的mentor都已经不在微软了,但按照微软的规定,这样也是允许参加转正面试的。我猜测是由于mentor已经离职等原因,投了转正后没有任何回音。我今年上半年在微软编程之美大赛中取得名次,比赛声称会有资格参与校园招聘直通车活动,但是似乎石沉大海,我猜测是庞大的微软在内部协调沟通上有问题。
  • 腾讯
    北京似乎没有我感兴趣的职位,深圳上海不想去。如果是搞产品的人可能比较适合去腾讯。

感谢
最后感谢一些人吧。都是或多或少在我找工作期间给了一些帮助的。尤其有些是很希望我去某个公司工作才推荐我面试的,但结果因各种原因没有成,实在抱歉。
名字无先后顺序:严强、袁全、牛章鹏、吴致淳、李鑫、刘思喆、项亮、杨哲、曹鹏、刘利祥、徐涵、李岩、朱涛。可能脑抽遗漏一些人,见谅。

下一步
既然已经签了offer,后面即使再来offer应该也是会拒掉了。
或者被HR知道已经签了别的offer,可能干脆就不发了。
后面准备一心一意的把博士论文搞定,在坤师兄说的好,博士论文不是为了给别人看,更多的是自己的一个总结。希望能把总结写的让自己满意一些。

优化算法在应用问题中的常见技巧

这是今天去Hulu交流时用的PDF,比较简短。总结了在做应用问题时的一点点感觉。
点击下面链接下载。
Techniques for Optimization Methods in Applications

秒针系统RTB大赛总结

比赛地址:http://www.miaozhen.com/2013/CACC2013.html

发布一下昨天在盒子咖啡交流时所用的文件。
可以点这里下载,或者在下面直接阅读。

0-1背包问题与子集合加总问题的近似算法

最近没有怎么更新博客,因为一直比较忙。最近发现所里在做的一个项目中,可以抽出一部分内容和0-1背包问题、子集合加总问题非常相似(虽然表面上不容易看出相似点),所以看了一些这方面的资料和论文,这里主要对问题特点和算法思想做一些整理。
这类问题其实很有意思,做数学和做计算机的人都会研究,而且我这里将要提到的论文都是做计算机的人所写的。

问题简述
0-1 Knapsack Problem (0-1背包问题,下面简称KP)和Subset Sum Problem (子集合加总问题,下面简称SSP)是经典的NP完全问题。
两个问题简要描述如下:

KP:有$n$个物品要放入背包,第$i$个物品的价值为$c_i$,占据体积为$v_i$,背包的总容积为$V$,要选择一部分物品放入背包,使得他们的总价值最大。对应的优化问题是
$\max_{x_i} \sum c_i * x_i $
$\mbox{s.t.} \sum v_i * x_i \le V, x_i \in \{ 0, 1 \} $
这里$x_i$代表是否选取第$i$个物品进背包,等于$1$就代表放入背包,等于$0$代表不放入背包。

SSP: 给一个集合$\{c_1, c_2, \ldots, c_n \}$,还有一个目标值$V$,问能否选出一个子集,使得子集中元素求和刚好等于$V$。我们一般考虑的是他的另一种表述方式:选出一个子集,使得子集中元素求和不超过$V$,且尽量大。对应的优化问题是
$\max_{x_i} \sum c_i * x_i $
$\mbox{s.t.} \sum c_i * x_i \le V, x_i \in \{ 0, 1 \} $
这里$x_i$代表是否选入子集,等于$1$就是选入子集,等于$0$就是不选入子集。

SSP是KP的特殊情况,也即当$c_i = v_i$的时候,KP退化为SSP,从问题式子上看,也完全一样了。
尽管如此,研究了KP不代表就不用研究SSP了,后面会说明这一点。

精确算法与近似算法
这两个问题都有很简单的动态规划算法可以精确求解,但可惜算法的时间复杂度是伪多项式的,也即和$V$相关,但$V$不是问题输入数据的规模,$n$才是。在ACM竞赛等算法比赛中,经常会遇到一些问题属于KP的变种,而伪多项式算法也就足够了。由于网上资料很多,而且难度不大,这里就不详细介绍了。如果你不知道,请你搜索“动态规划求解0-1背包问题”。
这里我们更关心多项式近似算法,也即PTAS(Polynomial Time Approximation Scheme),也即对任意给定的$\epsilon$,算法可以在关于$n$的多项式时间内求得一个解,且该解和真实最优解的最多相差$\epsilon$倍。
实际上这两个问题都有FPTAS(Fully PTAS)算法,也即时间复杂度不仅要是$n$的多项式,而且还要是$\frac{1}{\epsilon}$的多项式。

KP的近似算法
KP有非常简单的近似算法。
对任意$\epsilon$,令$P = \max_i c_i$,$K = \frac{\epsilon * P } { n}$,记$c_i’ = \lfloor \frac{c_i}{K} \rfloor$ (这里$\lfloor \cdot \rfloor$表示向下取整)
则使用$c_i’$代替$c_i$求0-1背包问题,求得的$x$即为$\epsilon$近似解。这是因为每一个物品由于取整而产生的误差都很小。
而这时候,由于$c_i’$都是整数,可以使用动态规划算法求解,容易算得动态规划的状态数至多$n \lfloor \frac{ P}{K} \rfloor$个,因此整个算法的时间复杂度为$\mbox{O}(n^2\lfloor \frac{ P}{K} \rfloor) = O(n^2 \lfloor \frac{n}{\epsilon} \rfloor ) $,
算法复杂度之所以能够达到多项式,是由于取整减小了动态规划的状态数,而$K$的出现是为了控制因取整而产生的误差,$K$足够小的时候就能保证解的相对误差不会超过$\epsilon$
此算法参考 Vijay V. Vazirani写的书 Approximation Algorithms(点击下载) , 第8.1,8.2章节(第69页-70页)
虽然这不一定是最快的多项式近似算法,但暂时没看到别的算法在任何情况下复杂度都能更低。
我自己也没有想到更好的。而有趣的是我最近在思考另一个等价的问题,但在发现等价性之前,我也想出了一个思路几乎相同,复杂度完全一致的算法。现在看来,其实本质是同一个算法。

SSP的近似算法
根据前面所述,SSP是KP的特殊情况。所以KP的近似算法就可以认为是SSP的近似算法了。但是,之所以单独考虑SSP,是因为他可以求得更快。
SSP也有思路非常类似的算法,可以在一些国外的教学资料上看到。如这一篇(点击下载)。但是时间复杂度都比较高,事实上,SSP有$\mbox{O}(\min \{ \frac{n}{\epsilon} , n + \frac{1}{\epsilon^2} \log(\frac{1}{\epsilon}) \} )$的算法。我认为这个结论是比较漂亮的,复杂度严格比上面提到的KP的算法要低,而且低很多。
为了说明算法思想,我们先再深入理解一下前面的算法。
前面的算法是用取整来控制复杂度,取整的本质事实上是将状态空间划分成若干段,每一段只取一个端点作为“代表”,这样状态数就会是多项式的,总的算法复杂度也就是多项式的。在SSP中,我们可以不事先取整,但仍然将状态空间分段,让每个段记录两个数值(也即选两个“代表”),一个是落在该段上的最小子集和(最小代表),一个是落在该段上的最大子集和(最大代表)。这样我们的状态数相当于比前面KP的算法多了一倍,而且是需要动态维护的,但是由于误差控制的更好(极端的例子是如果集合只有一个数,这么做就没有误差),没有取整那么大的误差,所以不需要分那么多段就能保证解的相对误差不超过$\epsilon$,因此最终算法复杂度会低。
此算法参考 Hans Kellerer等人的论文 An efficient fully polynomial approximation scheme for the Subset-Sum Problem (点击查看) Journal of Computer and System Sciences 66 (2003) 349–370
可以发现,这个算法是不能简单推广到0-1背包问题上的。

SSP的拓展问题——ISSP
Anshul Kothari等人在2005年研究Uniform-Price Auction Clearing(其实我也不知道这是啥问题)的论文中提出了Interval Subset Sum Problem (下面简称ISSP),他是SSP的一个推广。这个问题没有前面的问题这么有名(事实上我没看到第二篇论文讨论这个问题),但刚好我也发现了另外一个实际问题可以抽象成这个模型,所以我觉得还是很有意义的。问题简要描述如下:
给定$n$个区间$[a_i,b_i]$,对每个区间可以选择上面的一个数,也可以什么都不选,使这些数的和不超过目标值$V$,且尽量接近。对应的优化问题是
$\max_{x_i,y_i} \sum y_i * x_i $
$\mbox{s.t.} \sum y_i * x_i \le V, x_i \in \{ 0, 1 \}, y_i \in [a_i, b_i] $
至少从形式上看,他不再是线性的了,而且当$a_i=b_i$时退化为SSP。所以似乎更难了。
实际上这个问题也能改写为线性模型。
$\max_{x_i,y_i} \sum y_i $
$\mbox{s.t.} \sum y_i \le V, x_i \in \{ 0, 1 \}, y_i \in [x_i * a_i, x_i * b_i] $
从直观上看,如果$a_i$很小,$b_i – a_i$很大,这个问题似乎很容易解。我已经可以给出看上去不是太强的条件,在该条件下,ISSP是多项式可解的,具体这里就不给出了。但无论如何,In general,ISSP也是NP难问题。
Anshul Kothari等人的论文中也给出了一个FPTAS算法,比较有趣的是,这个算法和上面的SSP的算法思想是一致的,时间复杂度也是一致的。因此这一算法应当是受到上面所述的SSP的算法启发而设计的,而且是一个比较简单的推广。
此ISSP算法参考论文为 Interval Subset Sum and Uniform-Price Auction Clearing (点击查看) Computing and Combinatorics, Lecture Notes in Computer Science Volume 3595, 2005, pp 608-620

一些启示
1,SSP是KP的一个特殊情况,但是他们的近似算法复杂度却可以完全不同,这说明特殊问题可以有特殊算法。使用General的算法是可以的,但需要仔细想想问题是否有特殊的地方没发现,是否有更具针对性的算法没找到。
2,ISSP是SSP的一个推广,也即SSP是ISSP的特殊情况。但事实上ISSP并没有更难,甚至某些时候很可能有多项式算法,这说明推广了,也有可能变简单,特殊情况也有可能更难。但是特殊情况的算法思想可以借鉴用来解决推广了的问题。

如何快速计算交叉项求和——从libFM联想到的一类数学问题

libFM里面有一个很好的idea是遍历特征的交互作用。也即$\sum_{i \ne j} x_i * x_j$。
但是遍历交互作用需要计算$O(n^2)$次乘法,于是作者做了一个变换,成为$ 0.5 * ((\sum_i x_i)^2 – \sum_i x_i^2) $。变换后只需要线性次的乘法和加法即可。
听严强说,实际使用的时候常常不需要遍历所有交叉项,因为很多特征之间是没有关系的。如果那样,问题就变成了$v = \sum_{(i,j)\in S} x_i * x_j $,其中$S$是给定的指标集。可能在实际中$S$里面元素是比较少的,但无论如何,这引发一个数学问题:如何给出一个等价变换,使得用尽量少的乘法和加法就能求得这个式子?如果设计一个智能算法,自动选择有用的特征对,这时候可能就真的需要一个算法找到相应的等价变换式。
确定这个定价变换可以不用特别快速,因为只需计算一次,但是得到的结果应该是可以尽量快速计算的。

这和我以前考虑过的一个问题非常类似,但是不完全一样。
首先我们考虑“相对精确”地去找计算量最少的等价变换。说“相对精确”是因为我还没想到以一个便捷的方式处理完美的精确。我们考虑近似化为一个优化问题。
假设我们要找到一个需要至多$m$次乘法的等价表达式,则有$v = \sum_{k=1}^m \left( \sum_{i=1}^n (a_{ki} * x_i) * \sum_{j=1}^n (b_{kj} * x_j) \right)$,这里$a_{ki}$和$b_{kj}$都只从$1$,$-1$,$0$之间选择,所以他们与$x$的乘法实际是不需计算的。这样的话,根据对应项系数相等(也可以是不等号,只要覆盖到交叉项也可以认为考虑了这种特征组合,不一定非要系数为1),我们会得到$n*(n+1)/2$个约束,未知变量数目是$m*2*n$个,从自由度的角度考虑,$m$至少需要和$n$一个量级才有可行解,实际上只要$m$取$n$就一定有可行解了,可以举出例子来,只是那样可能需要计算非常多次加法,所以不是好办法。我们可以用运算量作为目标,假设一次加法的代价为$C_{add}$,一次乘法的代价为$C_{mul}$,则目标函数为$\min. C_{add}*\sum_{k,i} |a_{ki}| + C_{add}*\sum_{k,j} |b_{kj}| + C_{mul}*\sum_{k=1}^n \max_{i,j} ( |a_{ki}|, |b_{kj}| )$。这个目标其实并不精确,不过不妨碍理解问题。
可以看到,目标是线性的,约束是二次的,且为整数规划,所以非常难。如果放缩到$a$, $b$都为实数,则问题简化了一些。但是仍然是非常困难的问题,非线性,非凸,不过可以尝试计算。虽然不能保证得到最优解,但是可能会得到较好的解。一个小问题是如果$a$, $b$为实数则他们和$x$乘积的运算量稍微不好量化一些。这里面很多地方描述不精确,比如$a$, $b$确实也不需要是整数,只是取特殊值相当于少了一次计算。
一句话描述这个优化问题,就是:给定一个0-1矩阵,把他化成尽量少的rank=1的小矩阵相加,且小矩阵等于两个尽量稀疏的向量相乘。

也可以有启发式的办法,例如交叉项相似的分到一组,可以用一次乘法计算出来。但效果很难说。

和这个问题很相似的问题还有:使用最少的乘法,求矩阵乘。比如Strassen algorithm就使用了7次乘法计算2*2的矩阵乘,而传统方法需要8次乘法。如何使用更少的乘法计算矩阵乘,和上述问题很类似。这也是一个非常困难的问题,目前还没有人能精确指出任意阶矩阵乘法所需的最少乘积次数。

从函数近似角度看softmax

我不懂softmax,但是最近好友licstar在做这方面的实验,我就了解了一点点。
我用自己的理解复述一遍。
问题大概是针对分类的,有多个$m$维观测向量且我们知道他们的类别。样本个数记为$C$,类别数量记为$n$。
现在我们构造一个线性分类器,它包括了一个$n$行$m$列的矩阵$A$,将矩阵左乘观测向量$x$,就得到某个向量$b$,这个向量各个数中最大的一个设为$b_i$,则观测向量就是第$i$类的。

从维基百科就能看到这个问题的目标函数,貌似是和概率有关,我概率学得一般,但是发现可以从函数近似的角度去看。也许很多人已经这么做了,毕竟我不了解这个模型。
我们实际上有个很直观的目标是: minimize $ sgn(\max_j b_j – b_i) $
其中$sgn(\cdot)$是符号函数,也即当$t$为正时$sgn(t)=1$,当$t$为负时$sgn(t)=-1$,当$t=0$时$sgn(t)=0$。也即$b_i=\max_j b_j$的时候,目标函数取$0$,否则取$1$,含义就是有多少个被分类错误了。然后我们求这个函数的极小值。
但是这个目标明显非常难算,不连续更不可导。
首先我们替换掉$\max $,它的一个常用光滑近似函数是 $\max_j b_j \approx \mu \ln \sum_j exp(b_j / \mu )$ ,在参数$\mu$很小的时候,他们近似相等,但是参数太小函数会性质不好。这是一个凸近似。
然后需要再来近似符号函数$sgn$,近似他的办法有很多种,为了得到凸近似,考虑到复合函数为凸的一个必要条件(不是充分条件):若$f$和$g$都是凸函数,且$f$递增,则有$f(g(x))$是凸函数。所以我们需要找一个凸的,递增的函数来近似$sgn$,并且最主要是在零点处接近$sgn$,这还真不是太好找,这个函数需要在零点从负突然上升到正,而且要凸。如果不要求是凸的话倒是很好找。
一个简单的近似就是线性函数$f(u)=u / \mu $ 当$\mu$很小的时候,他在零点附近和符号函数接近,而且线性函数也是特殊的凸函数。

综上,目标就变成了 minimize $ \ln \sum_j exp(b_j / \mu ) – b_i / \mu $
化简一下,上式中目标函数
$ = \ln \sum_j exp(b_j / \mu ) – \ln exp(b_i / \mu) $
$ = \ln (\sum_j exp(b_j / \mu ) / exp(b_i / \mu)) $
也即等价于 maximize $ \ln (exp(b_i / \mu) / (\sum_j exp(b_j / \mu ))) $
这看上去就和维基百科上给出的目标函数一致了。

百度电影推荐系统算法大赛新数据集的简单分析

上一篇博文 http://diaorui.net/?p=419 意外的火了。如果你还没看过,请先去看看再回来看这篇。
后来今晚看啥@汪冠春 与我取得了联系。他和百度的多个技术人员一起对比赛进行了调整。赛前的准备工作不太充分,希望弥补后还能顺利吧。
百度学院的迅速响应和公开真实数据的精神是值得赞一个的~

调整后的比赛包括两个问题:
1, 传统的预测评分问题。给定一个只包括活跃用户的真实评分(而不包括“喜欢”),要求预测其他评分,仍然是RMSE作为评价指标。这部分数据包括大约1万用户、大约8000电影(评分的Sparsity约为0.2)。
2, 基于社交、标签和喜欢数据的开放性问题。给定用户喜欢的电影数据,社交数据,电影标签数据,要求自己挖掘一些有意思的话题,写成报告。这部分数据包括约15万用户和约1.7万电影。

数据集下载地址 http://pan.baidu.com/share/link?shareid=340221&uk=2000006609
这组数据应该没有人工干扰。我之前配合他们提了一些改进建议。后因收到邀请,我再简单总结一下新数据集的特点,可能会对参赛选手有帮助。
所有内容我尽量不写的太细节以免误导。

Continue reading »

数据真实性的探索——对百度电影推荐系统算法大赛的质疑


更新:
没有想到本文获得这么多人的关注。

@袁全V 的如下评价是个很好的建议。
—–
@袁全V:如果喜欢数据占大多数,只选”喜欢”数据,用recall或ndcg当metric也可以,没必要去套rmse. ID没有匿名化是硬伤
—–
我也收到了今晚看啥的来信。
—–
@汪冠春:看了你的分析和建议,很细致。我们在出题准备数据的时候有了一些不科学之处,望理解。明天我会和百度学院的朋友确认是否会对比赛有影响并确认处理方法。
—–
从公开数据集、办比赛来讲,这次这种形式我是非常支持的。也期待有更多的数据能够公开出来方便大家学习。办比赛确实有难度,要考虑的很多。虽然这次有很多问题,但以后总会做的更好。也期待百度今后继续办这样的活动,给我们提供从实践中学习的机会。
百度已经调整了比赛规则和数据,新的数据集简要分析请见 http://diaorui.net/?p=510


摘要
本文主要通过一系列数据上的探索,论证百度电影推荐系统算法大赛的数据集并非真实。旨在让做相关研究的人不要直接去使用这组不真实的数据去检验自己的算法,以免误导。本文并非只是为了批评,文中也指出了若干条建议,希望此次比赛主办方以及希望举办类似比赛的人参考。
文中纯属个人观点,如有错误,请不吝赐教。

Continue reading »