Now, we have a problem, given 10 million users and their preference on X items, how to make recommendation for users by user-based collaborative filtering? The key step of usercf is to calculate user-user similarity. However, calculate user-user similarity between 10 million users in a 4G RAM computer is impossible. Thus, we can only use [...]
ItemCF和UserCF是推荐的两个基本算法。UserCF是很早就提出来了，ItemCF是从2001年左右开始流行，从amazon的文章开始，大家都觉得ItemCF好。但是，所有的文章说ItemCF好，都是从复杂度的角度说的，主要是user数大大超过item数，所以算item的相似度比较快速。（比如Netflix数据有40W用户，但只有1.7W电影，计算用户相似度代价是很大的）。不过这个原因始终不能让我觉得信服，因为在有些推荐中，比如文章，新闻的推荐，item数也是很多的，所以单从复杂度的角度，这两个算法在不同的系统中各有优势。 不过最近意识到，ItemCF的优点有两个。在一个非SNS的网站，相关Item本身是很重要的推荐，甚至比对user的推荐更重要。比如在youtube，但你看一个视频的时候，他会告诉你相关的视频。这个推荐的重要性远远超过了youtube首页对用户的综合推荐。在这里，itemCF的相似度成为了用户浏览的重要手段。另一个优点是ItemCF便于做推荐解释，在一个非SNS的网站中，我给你推荐一本书，如果给你的解释是某某和你有相似兴趣的人也看了这本书，你可能不相信因为你不认识那个人。但如果我说是因为这本书和你以前看的某本书相似，你可能就觉得合理了。 当然UserCF也不是一无是处，特别是现在SNS网站的流行，然UserCF又重要了起来，UserCF加上社会网络信息，可以增加用户对推荐解释的信服程度。
UserCF和ItemCF是协同过滤中最为古老的两种算法，在top-N的推荐上被广泛应用。这两个算法之所以重要，是因为他们使用了两个不同的推荐系统基本假设。UserCF认为一个人会喜欢和他有相同爱好的人喜欢的东西，而ItemCF认为一个人会喜欢和他以前喜欢的东西相似的东西。这两个假设都有其合理性。根据我的测试，用UserCF和ItemCF做出的推荐列表中，只有50%是一样的，还有50%完全不同。但是这两个算法确有相似的精度。所以说，这两个算法是很互补的。 我一直认为这两个算法是推荐系统的根本，因为无论我们是用矩阵，还是用概率模型，我们都非常的依赖于前面说的两种假设。如果用户的行为不符合那两种假设，推荐系统就没必要存在了。因此我一直希望能够找出这两种算法的本质区别。他们有相似的精度，但是coverage相差很大，ItemCF coverage很大而UserCF很小。我还测试了很多其他指标，不过要从这些表象的指标差异找出这两个算法的本质区别还是非常困难。不过上周我基本发现了这两个算法推荐机理的本质区别。 我们做如下假设。每个用户兴趣爱好都是广泛的，他们可能喜欢好几个领域的东西。不过每个用户肯定也有一个主要的领域，对这个领域会比其他领域更加关心。给定一个用户，假设他喜欢3个领域A,B,C，同时A是他喜欢的主要领域。这个时候我们来看UserCF和ItemCF倾向于做出什么推荐。 结果如下，如果用UserCF, 它会将A,B,C三个领域中比较热门的东西推荐给用户。而如果用ItemCF，它会基本上只推荐A领域的东西给用户。因为UserCF只推荐热门的，所以UserCF在推荐长尾上能力不足。而ItemCF只推荐A领域给用户，这样他有限的推荐列表中就可能包含了一定数量的不热门item，所以ItemCF推荐长尾的能力比较强。不过ItemCF的推荐对某一个用户而言，显然多样性不足。但是对整个系统而言，因为不同的用户的主要兴趣点不同，所以系统的coverage会很大。 显然上面的两种推荐都有其合理性，但都不是最好的选择，因此他们的精度也会有损失。最好的选择是，如果我们给这个用户推荐30个item，我们既不是每个领域挑选10个最热门的给他，也不是推荐30个A领域的给他，而是比如推荐15个A领域的给他，剩下的15个从B,C中选择。 认识到这一点，可以给我们设计高精度的算法指明一个方向。就是当一个系统对个人推荐的多样性不足时，我们增加个人推荐的多样性可以提高精度。而当一个系统的整体多样性不足（比如只推荐popular的)，我们增加整体的多样性同样可以提高精度。
在传统的推荐算法中，有两个基本算法，也就是所谓的user-based和item-based。其实，前一种算法的观点是认为用户的行为比较受舆论的影响，而后一种认为用户的行为受自己喜好的影响。当然这两者算法都是偏于极端的，现实社会中用户的行为往往受两种的共同影响，而两种影响的大小主要取决于用户和舆论谁更强势。 就比如拿最近的孔子来说，其实本人自从来了北京之后，每个月都会看一部电影，不管好还是烂，反正我个人看电影的习惯就是放松，不管多烂的电影，只要能放松就行了。而且我个人还是比较有主见的，不大受社会太多的影响（当然这也是相比较而言）。但是，有的时候舆论的影响却是潜移默化的，鉴于我的社会圈子里的舆论都认为孔子不怎么样，首先这就降低了我的期望，也就是说我去看孔子也不抱大希望了，但因为我的习惯，我还是觉得去看孔子，也就是说，在我到电影院之前，我的行为还是受我的习惯影响，舆论虽然有影响，但还没有大到改变我决定的地步。 不过当我到了电影院，发现孔子打折票还买50，这时我犹豫了，身在价格和舆论的双重context下，再强的人也不得不改变习惯了，于是经过激烈的思想斗争，我放弃了看孔子，用8元钱去买了个面包（现烤的，味道很不错）吃了一下，算是本周末奢侈了一把。 由此可见，舆论和个性的博弈在我看孔子这件事情上体现的非常的明显，当一个个人还在如此犹豫的时候，去追求推荐的精度还有什么意义了？也许我明天又后悔了，而这个事情推荐系统拿到了我没看孔子的数据，还在沾沾自喜着准备利用这个信息来调整精度。
问答系统一直是人工智能的重点，因为图灵测试就是一个问答系统。不过研究者们从早期的追求智能问答已经发展到了更为实际的问题：如何为人们找到答案。这个最好的解决方案是社区问答，比如百度知道，天涯问答。这些系统吸引人问问题并回答问题。这些系统提供了很好的实际解决方案，但还是有很多问题。 最大的问题是问问题者和回答者不能交流，而且很多人就是为了赚取积分来回答问题。更重要的是，当一个人问了问题后，只能听天由命，如果有人回答了，就谢天谢地，不然只能自认倒霉。 vark是一个很特别的网站，他并不为问题提供答案，而是提供可能知道答案的专家。不过他没有更进一步，并没有让提问者和专家很好的交流。 提供专家的好处是，提问者可以问更深入的问题，而且认识专家后，以后遇到类似的问题，提问者可以直接找到专家。
融合算法大概可以分成两类，一类是用同样的算法，不同的训练集，训练出模型然后融合；另一类是用不同的算法，同样的训练集，训练出模型然后融合。第一种已经非常成熟了，所谓的adaboost就是这一种，第二章又叫做stacked regression。这方面的权威论文可以见： http://www.springerlink.com/index/JRK78356016V13JW.pdf 不过如果具体到推荐算法的融合上，就可以有更加细分的问题。我现在觉得一个重要的问题就是给定一个算法，然后如何将用户分类，比如分成两类，使得一类包含了非常适合这个算法的用户，另一类包含了不适合这个算法的用户。当然这种分类是先验的，不是说拿个这算法实际的测了测每个用户的精度，然后分类。 所以对任何一个算法，我们需要找出一个度量p(u)，使得p(u)和这个算法给这个用户的推荐精度非常相关。其实设计出这个p(u)也不是很困难，只需要我们深刻理解每个算法的内涵。 比如举个例子，user-based算法中，我们是假设用户会喜欢那些和他有相同喜好的用户喜欢的东西。这句话谁都会说，几乎所以人写论文都会写。不过我们仔细想想就可以发现一个问题，如果一个用户没有相同喜好的朋友，那user-based的算法岂不是就没用了，所以一个用户对user-based算法的适应度是和他有多少共同喜好用户成正比的。
前一段时间和wendong聊天，他提到userbased算法的结果多样性不如itembased算法。对此，我觉得有几个问题 1) 我们知道所谓多样性，是指推荐结果两两都不怎么相似，从而不同的相似度度量其实产生不同的多样性度量。 2)常用的相似度有两种，一种是基于content的，一种是基于collaborative filtering的，那么根据我的实验，在这两种相似度的度量下，userbased的结果多样性都好于itembased的算法 3)但我觉得还是存在一种相似度，而这个相似度对应的多样性在item-based的方法下比较好 不知道大家对这个问题怎么看，在实际系统中userbased和itembased谁能产生多样的结果？
通过这几天设计google reader的推荐系统，我发现还是user-based算法比较实用，这主要是因为文章更新的太快，而用户增加的很慢。我现在的策略是，定期的算一下用户之间的相似度，然后对一个给定用户，找出和他最相似的100个用户，然后找出这100个用户最近3天share和like的文章，并对这些文章进行排序，选择前50个，作为最后的结果。 user-based算法非常适合于item快速更新的场合，在google reader上，每秒钟都会出现很多新的文章，所以实时计算文章直接的相似度是很困难的。
