Beyond Search

《Programming Collective Intelligence》书评

wendell.gu@gmail.com (guwendong) — Mon, 25 Aug 2008 08:05:32 +0800

中国有句老话，叫做“知易行难”。
作算法的朋友应该更有体会，想把 paper 上的公式转变为可以运行的代码，这是件考验功力的事情。
Toby Segaran 写的这本《Programming Collective Intelligence》，是修炼此种功力的武林秘笈之一。

这本书最显著的特点是，实战性极强！
针对每个算法，他从头到尾演示了一个完整的实现过程：从获取数据，组织存储，到算法实现，加载运算，再到最后的结果的分析利用。书中所有的例子均基于实际系统的真实数据，作者演示了大量的开放 API 的使用，Delicious、Amazon、Last.fm、Google News，各个都是大名鼎鼎，每步都是真刀真枪。跟着书中的操作这样一趟走下来，你会豁然开朗，原来这些看似神秘复杂的系统，也不过如此。但不幸的是，其中的大部分 API 已经不能工作了。比如 del.icio.us API，你就得换这个了。

从纯粹算法的角度来讲，这本书里讲解的算法，基本都是入门级的。但即使是这样，能把细节讲述地如此传神，也实属不易。换一个角度来看，简单，也同时意味着常用，熟练掌握了书中的这些算法，也足以解决不少的现实问题。而且，在拥有大规模数据的情况下，简单的算法，往往也可以取得令人吃惊的效果 [1]。

另外一个方面，此书作者用英文遣词造句的能力出神入化，读起来简直行云流水。时常会让自己产生英文超牛的幻觉，体验很爽。

没时间细读的朋友，也建议至少看一下 Toby Segaran 写的 Social Data Mining 这个 slide，一定会有收获。

我得知此书，需感谢个性化技术相关资料后面，KaKa 网友的推荐。
豆瓣猜没有帮助我发现这本书。
这曾让我思考，基于 SNS 的推荐，是否比传统的推荐更有效呢？

五星！

Google 评价 blog 的指标

wendell.gu@gmail.com (guwendong) — Wed, 20 Aug 2008 08:47:32 +0800

读了一下 Google 关于 Blog Ranking 的 Patent，总结如下。

正面的指标：

[0038] 订阅数
统计 blog 在各种 reader 中被订阅的数量。被订阅的越多，ranking 越高。但同时会使用一些方法处理“subscriptions spam”，诸如验证订制人和 IP 的唯一性。
[0039] 搜索点击数
统计 blog 作为搜索结果时被点击的次数。点击次数越多，ranking 越高。
[0040] 在其他 blogger 的 blogroll 里的出现次数
blogger 通常会使用 blogroll 来整理指到其他 blogger 的链接集合。统计所有 blogroll 中，指向某个 blog 的链接越多，ranking 越高。
[0041] 来自高质量的 blogroll 的链接数
高质量的 blogroll 的链接大多都指向著名的或值得信任的 blog。
[0042] 来自高质量的 blog 的 blogroll 的链接数
这里的假定是著名的或值得信任的 blogger 不会放指向 spam blog 的链接。
[0043] 有Tag
blog 作者如果分析了 blog 内容，归类并打上了 tag，起码可以说明作者的态度比较认真。
[0044] 来自邮件和聊天记录的链接数
如果在 Email 正文里或者聊天记录里出现了指向 blog 的链接，会加分。GEmail 和 Gtalk 被用在了这里。
[0045] PageRank
PageRank 越高对应的 blog 也就越重要。考虑到blog的更新比较频繁，最新的 blog post 可能还没有PR。这时可以用对应的 blog 的 PR 来代替。

其中 [0040-0042]，其实是类似于传统网页间 PageRank 计算的一套模式，只不过这里把它限制在了 blog 之间。

负面的指标：

[0047] 更新频率异常
更新过于频繁或者非常有规律，会被认为是在 spam，ranking 会降低。这里提醒喜欢在每天的固定时间更新 blog 的朋友注意一下了。
[0048] feed 内容和 blog 内容的不一致
spammer 有可能会为了提升自己的 ranking 而把有价值的内容放到 feed 里面，同时在 blog 内容里面放一些指向不相关内容的广告链接。为了惩罚这种情况，对于 feed 内容和 blog 内容不一致的情况，要降低 ranking。
[0049] 出现重复内容
有些 spammer 为了让某些内容能够多次长时间的出现在 feed 里面，会重复发布同样的内容。这样的情况会被惩罚。
[0050] 垃圾词过多
通过词频统计（bi-gram 或者 tri-gram 等），如果 blog 内容里垃圾词的比较过高，会降低 ranking。
[0051] 多数 blog 长度相近
这个主要是针对使用机器自动生成 blog 的情况。
[0052] 链接异常
当 blog 里的链接多为指向单一网页，或者单一的外站，会被认为是在 spam，ranking 会降低。
[0053] 广告太多
如果一个 blog 页面内含有过多的广告，会降低 ranking。
[0054] 广告出现在正文里
一般 blog 页面会包括三方面的内容：最近发表的 blog，blogroll 和 metadata。如果广告出现在正文里，会降低 ranking。不知道 adsense 的广告有没有特殊待遇？

Are Machine-Learned Models Prone to Catastrophic Errors?

wendell.gu@gmail.com (guwendong) — Tue, 03 Jun 2008 11:29:02 +0800

最近忙，paper 看得多，blog 看得少，险些错过一些非常有意思的文章。上一次提到的 "Introduction to Google Search Quality" 算一篇，这次要说的是另外一篇 "Are Machine-Learned Models Prone to Catastrophic Errors?"。 不过这两个 blog 都被我们伟大的 GFW 拌掉了。

Peter Norvig 这样的大师的意见，我们需要仔细体会。我整理一下我感兴趣的。

tow phase of google search algorithms
- An offline phase, which is time-consuming and query-independent.
- An on-line phrase, in response to a user query in a few milliseconds.
Tons of training data ... from the armies of "raters" employed by Google
The big surprise is that Google still uses the manually-crafted formula for its search results, despite the fact that, their best machine-learned model is now as good as, and sometimes better than, the hand-tuned formula on the results quality metrics that Google uses.
two reasons

the human experts who created the algorithm believe they can do better than a machine-learned model
Google's search team worries that machine-learned models may be susceptible to catastrophic errors on unforeseen query types, which is different from the training data.

Nassim Taleb divides Black Swan phenomena into two classes
- Mediocristan
- Extremistan
The current generation of machine learning algorithms can work well in Mediocristan but not in Extremistan.

So the thing is, how to figure out whether new machine learning algorithms can be devised that work well in Extremistan, or prove that it cannot be done?

Google Search Quality 官方说明

wendell.gu@gmail.com (guwendong) — Sun, 01 Jun 2008 21:35:15 +0800

"the ranking of Google search results" 是 google 的命脉，因此很少能看到官方的说明。原因倒也无可厚非："competition and abuse"，这两件事情确实哪一个都不容忽视！

不过近日，google 负责搜索质量的 VP， Udi Manber，透露了一些有意思的资料，"Introduction to Google Search Quality"。对 search 感兴趣的千万不要错过！我列举一下我感兴趣的。

more than one thousand programmer/scientist years have gone directly into their development (that is to say "the ranking algorithms").
divided into some teams
- The heart of the group is the team that works on core ranking
- Another team in our group is responsible for evaluating how well we're doing
- Another team is dedicated to new features and new user interfaces
- There is a whole team that concentrates on fighting webspam and other types of abuse
- There are other teams devoted to particular projects
PageRank [1] is still in use today, but it is now a part of a much larger system. ... made significant changes to the PageRank algorithm in January, 2008.
some other parts
- language models (the ability to handle phrases, synonyms, diacritics, spelling mistakes, and so on)
- query models (it's not just the language, it's how people use it today)
- time models (some queries are best answered with a 30-minutes old page, and some are better answered with a page that stood the test of time)
- personalized models (not all people want the same thing).
Google conducts evaluations typically in three manners, (1) automated evaluations every minute, (2) periodic evaluations of our overall quality and (3) evaluations of specific algorithmic improvements.
In 2007, ... more than 450 new improvements, about 9 per week on the average.
.. work on projects where the sole purpose is to simplify the algorithms. Simple is good.

Udi Manber 是我最景仰的几位科学家之一。"Chief Algorithms Officer"这个职位，就是 Amazon 专门为表彰他的贡献而首创出来的。

推荐阅读：

Digg+RDFa

wendell.gu@gmail.com (guwendong) — Mon, 26 May 2008 03:25:40 +0800

5月初，Digg 宣布在其新闻页面里，加入对 semantic markup [1] 的支持。目前支持 3 种：XFN，hCard，以及最重要的 RDFa [1]。

想看实际用法的，可以在 Digg 新闻页面的源代码里，搜索“property”。比如在这个页面里
http://digg.com/tech_news/In_Google_we_trust_but_should_we，你可以找到类似于这样的内容，
“<a href="http://www.guardian.co.uk/technology/2008/may/22/internet.google" rel="dc:source" property="dc:title">
In Google we trust - but should we?</a>”。
如果安装了 RDFa bookmarklets 的话，可以看到更形象的效果，类似下面。

使用 RDFa Highlight 标亮页面上的 N3 Triples。
使用 GetN3 extractor 抽取出来的 N3 Tripes 文本。

最早的 RDF [1] [2]，由于其比较难于理解，并且操作复杂，导致其始终没有推广起来。W3C 组织受到轻量级规范如 Microformats 的启发，推出了新的经过简化的 RDFa [1] 规范。从其官方描述“Embedding Structured Data in Web Pages”，就可以看出来，它是一种嵌入到 HTML/XHTML 中的数据。要说 RDFa 的实现比 Microformats 还是要复杂一些，不过它的适用性更广，对于可以通过 RDF 表达的任何内容，都能够使用 RDFa 添加到 XHTML 文档中，而且不再需要使用繁琐的 XML 语言进行描述。这使得基于现有 Web 内容实现 Semantic Web，成本低了不少，也更靠谱了。

希望可以有更多的 Applicaitons 向 Digg 看齐，让 RDFa 的队伍壮大起来。
这里需要谴责一下 Powerset，号称 Semantic Web 的 Killer App，居然都不支持 RDFa。

推荐阅读：

Word Count as a Measure of Quality on Wikipedia

wendell.gu@gmail.com (guwendong) — Tue, 06 May 2008 05:33:21 +0800

Wikipedia 是个好东东！目前，Wikipedia 上大约有超过 2,000,000 个英文条目，已经成为一部地地道道的百科全书。但由于之前 GFW 作祟，要访问它必须得使用穿墙术，这大大降低了它在国内的影响力。最近沾了奥运会的光，Wikipedia 解封了。
我相信，大多数人都会有这样的印象，“Wikipedia 上的内容是高质量并且可以信赖的”。经常使用 google 的人尤其会这么认为，因为 Wikipedia 的内容经常会出现在 google search 结果的第一页内。随便试验几个例子就可以证明这一点，recommender system，semantic web，或者更 general 一些的，automobile，Olympic。国外有人做过一个实验，结论是，“96.6% of Wikipedia Pages Rank in Google's Top 10”。Wikipedia 的影响力之大，可见一斑。

但实际上，经常使用 Wikipedia 的人们发现， Wikiepedia 上的条目并不像我们想当然认为的那样尽善尽美，它也是鱼龙混杂的。而且要命的是，由于 Wikipedia 百科全书的性质，对于不熟悉的内容，读者很难区分哪些内容是高质量的，哪些又是滥竽充数的。Wikipedia 的管理者已经承认了这一点，并在试图解决这个问题。国外有学者把这个问题引入到了 research 领域，做了不少有意思的工作。

刚刚结束的 WWW2008 会议里有一篇 short paper，《Size Matters: Word Count as a Measure of Quality on Wikipedia》。里面给出了一个令人吃惊的实验结果，在进行 Wikipedia 的文章质量评价时，仅仅只需要使用“Word Count”一个参数，就可以取得 96.31% 的准确率！这个结果，比许多使用复杂模型的算法，都要好！
可以看出来，作者写作这篇 paper 的态度是非常严谨的！但我个人还是认为，对于评价质量这个问题，article length 并不是一个严谨的指标，文章的实验结论似乎仅能说明，使用这个指标得到的结果与 wikipedia 现有数据拟合的更好而已。这篇文章更靠谱的结论应该是，“long articles are featured (good), and featured articles are long”。有这方面实际经验的朋友，欢迎讨论。

Twine Beta：盛名之下，其实难副

wendell.gu@gmail.com (guwendong) — Sat, 03 May 2008 20:48:06 +0800

等了很久之后，终于在4月26日拿到了 Twine Beta 的试用邀请。简单地玩儿了一下，发现用标题这句话形容它再合适不过了——盛名之下，其实难副！
这就是传说中万人瞩目的“The First Mainstream Semantic Web App”？OMG！与 Freebase 的惊艳相比，Twine 差得简直太远了。

用官方的话说，Twine 的核心是“Interest Networks“，又或者是之前更多被提到的“Knowledge Networks”。Twine is a Smartest Way To Organize, Share and Discover Information About Your Interests. You can use Twine alone, with friends, groups and communities, or even in your company. 但以其目前的 Beta 版来看，Twine 最多也就能算个稍微新型的 bookmark 应用而已。

当然，可以看到 Twine 试图在做一些事情，我捡重要的说说。

第一件事情，从网页里抽取实体。
这事儿英文通常称为 Entity Extraction，Semantic Web 中叫做 Ontology Annotation。这个确实是 Sematic Web App 必须要解决地第一件事情。但在这件事情上，Twine 做得很烂。我总共试了 3 篇文章。

第一篇是我的一个中文 blog，“个性化站点：MyStrands”。Twine This，结果是乱码！好吧，你可以说 Beta 对中文的支持还不好，可以容忍。
第二篇是我在 Google Reader 上 share 的一篇英文 blog，“Slide decks from Web 2.0 talks”，里面有两个很棒的 PPT。这次更离谱，完全没有定位准确正文，居然把 “Recent Comments” Panel 里的内容作为了网页正文！好吧，你可以说这篇文章的正文部分字数少，识别有难度，可以容忍。
第三篇是一个分析 Twine 的英文 blog，“Web2Summit: Radar Networks Unwinds twine.com”，长篇大论，以免正文字数少又难倒了 Twine。这次总算顺利通过了，让我们赶紧来看一下 Twine 传说中的 Auto Tag 吧。“People”里加上了“Nova Spivack”，这个不错。“Organizations”里加入了“O'Reilly”和“Radar Networks”，也不错，但有个“Directory Assistance”非常诡异！点链接进去一看，search 结果里大量出现了“Network”这个词，而这篇文章里总共出现了3次“Network”，看来“Network”被当作了“Directory Assistance”的一个 Keyword。由此大概可以推断，对于 Entity Extraction，Twine 使用的是 Meta Model。但关键是此处的结果是有问题的，Network 在本文里是作为“Radar Networks”出现的，并不是本来的 Network，这里产生了歧义，但 Twine 的模型并没能解决这个问题。最后再来看“Other Tags”，“Semantic Edge”、“Semantic Web”和“Web 2.0”还算不错，但称不上好。通篇在评论的 Twine 应用本身，并没有出现在 Auto Tags 里面，但通过验证，其实“Twine”这个 Tag 是存在的。

第二件事情，“Twine”的使用。
这里的“Twine”，不是 Twine.com，而是 Twine team 创造出来的一个概念，用来组织 Interest Networks。用大家都能理解的一个说法，“Twine”基本和我们常见的“频道”差不多，就是一堆相似的文章的集合。在我看来，“Twine”本身其实和 tag 没有本质的区别，不同就在于用作“Twine”的 tag 应该会得到一个比较高的 tag weight，并在 tag hierarchy 中占据更高层的位置。其实，tag weight 与 tag hierarchy，也是我一直在思考的一个问题。比如在使用 del.icio.us 时，我们会给网页打上不同的 tag，潜意识里，各个 tag 的 weight 应该是不同的，并且通常还会使用不同层次的概念。比如“Web2Summit: Radar Networks Unwinds twine.com”这篇文章，Technorati Tags 就是“freebase, radarnetworks, SemanticWeb, web2.0, web20, web2summit”，其中 SemanticWeb 和 radarnetworks 应该 weight 高一些，而 freebase 是 SemanticWeb 和 web2.0 概念之下的一个应用。但常见的 tag 标注方法，是没有办法体现上述两项差别的。“Twine”的使用，似乎就意在 tag 上面再插入一层，定义出重要的 tag，建立 hierachy。如果 Twine 确实是这种思路的话，目前的产品设计至少也有一个问题。用户可以自由地创建 Twine，似乎并没有什么规则/规范。我可以建立一个“Film”的“Twine”，然后把“The Matrix”加进来，打上“Science fiction”的 tag；也可以建立一个“Science fiction”的“Twine”，然后把“The Matrix”加进来，打上“Film”的 tag。这会造成混乱。

Recommendation Panel，是 Twine 上另外一个值得关注的功能，但由于我目前活动度不够，推荐给我的东西很少，留待下一步分析。

个性化技术相关资料

wendell.gu@gmail.com (guwendong) — Sun, 23 Mar 2008 12:14:53 +0800

经常会有朋友发 email 问我，“研究个性化技术应该如何入手”？
这个问题其实挺让我为难的，因为以我目前的水平，尚不足以授人以渔。但又不好不作答，因此，整理了这份资料清单。我争取长期维护下去，力求授人以鱼吧。
注：此清单完全以我个人喜好整理，不周之处还请大家在评论里指明，或者 email/gtalk 也可。

Subjects:

Groups & Researchers:

Conferences:

Selected Papers:

Blogers:

Software Libraries:

Taste, Java, http://taste.sf.net/
Beyond Thoth, C#, http://sf.net/projects/beyondthoth/

Resources:

Books:
完全以个性化技术为中心的书籍很少，但多数讲 Machine Learning 或者 Data Mining 的书籍里面，都会有专门的章节，介绍与此相关的内容。

Programming Collective Intelligence, Toby Segaran, O'Reilly, 2007.8
Personalization Techniques and Recommender Systems, Gulden Uchyigit, World Scientific, 2008.4

个性化站点：MyStrands

wendell.gu@gmail.com (guwendong) — Thu, 20 Mar 2008 15:26:00 +0800

MyStrands 是一家专注于个性化技术的 Start-up。最近，他们搞了一项活动，“Strands $100,000 Call for Recommender Startups”，在个性化圈内被广泛关注。MyStrands 成立于 2003 年，以作 Music 推荐开始起步，目前的产品线涉及到 TV、Mobile、Community 等领域。2007 年 7 月，他们完成了第二轮融资，总额 $25 Million。因此，掏出 $100,000 还是非常轻松的，而且，相比可能收获的好的 project 来讲，这个活动的结果应该也会是物超所值的。

平心而论，技术方面，MyStrands 目前尚没有“必杀技”，即使在他们的主业音乐推荐上，其推荐的质量与 Pandora 相比也尚存在一定的差距。我从外部观察，基本上是以 Item-based Collaborative Filtering 技术为核心，正在逐渐向以 User 为中心的 social recommendation 方向前进，但其社区的活跃度还不够，数据积累尚待时日。产品方面，MyStrands 比较注重各种终端设备的集成，包括 PC（Windows、Mac）、Mobile 以及其他一些可联网设备，都可以运行他们的应用。尤其在 Mobile 方面，其推出的 social player 可以支持 Windows Mobile 与 Symbian 这两个主流平台，并刚刚在 Mobile Rules! Award 2008 上被评为“最佳多媒体应用”。

总体来看，在个性化领域，MyStrands 应该还是走在前面的，他们自己的信心也很足。引一段其 blog 中的文字，“MyStrands raises $25 Million to lead the social recommendation industry”：

We feel strongly that the future of the web is about personalization. Personalized TV stations, personalized advertising, personalized news, personalized shopping, personalized music and entertainment experiences, wherever you happen to be, whether it’s at home, on the go, at your friend’s or at a bar… This is what our 50-person team has been focusing hard on and where we are headed with this funding.

三言两语：隐私问题与个性化服务

wendell.gu@gmail.com (guwendong) — Thu, 28 Feb 2008 05:50:36 +0800

Web 上的隐私保护是个让人头疼的问题！已经有激进点儿的人在说，“Privacy is Dead: Get Over It”。确实，随着计算机存储容量的扩展，以及数据分析能力的提升，我们在 web 上的每个动作，都有可能会被保存下来，被进一步的加工，并被各种形式的应用所利用。

这些大数据的存在，有可能会造成严重的后果，即使初衷是好的。AOL Search Log 事件就是一个鲜活的例子。2006 年 6 月，AOL 实验室发布了一组数据 [1]，“500k User Queries Sampled Over 3 Months” （此乃镜像链接，AOL实验室的原始数据已经被删除了）。刚开始，学术界的人们都欢欣鼓舞，如此大量的数据公开出来确实难能可贵，毋庸置疑会有力地促进相关的学术研究 [2]。但没多久，就出现了一个大问题，AOL 数据集里面的第 4417749 号用户，被人还原出了真实的身份 [3]。一下子，舆论哗然，隐私保护组织也开始不遗余力地展开讨伐。最终，此事以 AOL 关闭实验室相关部门，CTO Maureen Govern 被 fire 掉才告一段落。隐私得到了保护，但世界失去了一次进步的机会 [4]！后面的 Netflix Prize 竞赛，也遭遇了类似的问题，但谢天谢地，这次的影响很小。

而另一方面，基于这些数据所得到的分析结果，无论对个人还是对服务提供商，都有益处。拿我来讲，经常在 Amazon 上面搜索书籍和打分，使得 Amazon 可以向我推销能吸引我的商品；启用了 Google 的搜索历史服务，使得 Google 可以向我提供适合我的搜索结果；向豆瓣贡献着打分数据，使得豆瓣可以帮我找到我会觉得好看的电影。而与此同时，Amazon、Google 甚至是豆瓣，通过大量收集这样的数据，已经建立起了非常高的进入壁垒。后来者由于缺乏这样的数据积累，在类似的服务上也很难再有所超越。

通常情况下，如果你严肃地探讨隐私保护的问题，大多数人也许会发现，这是一个虚幻的命题。大多数人并不见得能够清楚地说明到底在顾虑什么，往往，大家只是担忧而已，甚至仅仅是潜意识型的思维，“我只是不想让别人了解我”。但当我们把问题拉回到现实情况，我们会发现，隐私也许根本不是问题。你在地址栏里主动输入 amazon.com，在 Amazon 的网上超市里面选购商品，下订单并付款，然后给出评价完成交易。Amazon 为我们提供了一种体验很好的服务，我们乐意在 Amazon 上浏览，进行各种活动，看起来 Amazon 似乎有权利使用我们的这些行为数据，提升他们的服务，从而让我们更快乐的购物。因此，虽然 Amazon 记录了我们的一举一动，但并没有人抱怨隐私受到了侵犯。

个性化服务，已经被公认为是下一个十年中的 next big thing 之一，而隐私问题，却一直在困扰着个性化服务的发展。我个人认为，从业人士和相关部门，实在是有必要来共同关注和解决这个问题了。制定相应的行业规范，是非常有必要的，甚至是制定专门的法律都不为过。毕竟，这是一个价值超过10亿$的问题！