箭扣长城

国庆前的事情了也没有来得及整理，简单记录下

去的过程很曲折

1. 一行人包车前往，坑爹的师傅导航到了前山，结果又绕了100里路才到了后山住的地方


2. 去住的地方在所谓的生态园内，过路费按人头


3. 从上地过去花了5个小时- -

农家乐还是挺不错的，吃的很实在，尤其是我们饿了，晚上住通铺，各种基情，第二天一大早出发了，路程还是比较惊险，有的地方甚至用到了绳子，上几张图。

推荐Coursera.org

最近在学习machine learning的课程，感觉Coursera的这个课程非常赞，不过分的说，是我从出生以来觉得上的最好的课程，没有之一，好东西不敢独享，拿出来和大家share一下。

该站点创始人为Andrew Ng（斯坦福的机器学习大牛教授，同时也是Google 的员工，搞过ML的同学应该了解）。

该站点致力于：

Take the World's Best Courses, Online, For Free.

• Learn with videos, quizzes, and assignments


•  Interact with thousands of other students


• Advance your knowledge and career

目前有大约124个courses，跨越了17个categories，来自16所美国的顶级大学，详情可以到站点了解。

说点干货：为什么我认为这个课程非常赞（针对ML课程）

• video很赞，循序渐进，基础要求低；板书详细而且写写画画一应俱全；这个是最好的干活


• course wiki全，将课程所述核心全部记录并解释


• review question和programming exercise针对性强，rq针对每个解答都有解释，pe结合实践较强


• 其他discussion，help等，通过和其他同学交互，学习更多

六一泰山行

作为组织bui委会一员，6.1下午带领大家浩浩荡荡杀向五岳至尊。行程是这么滴，下午高铁过去，吃喝山东菜，晚上好好睡，第二天早起爬山，下午缆车下来，火速返京，恩。

北京-泰安的高铁，两个小时，两把三国杀的时间。

安顿在实现安排的汉庭，品尝了山东菜，头天晚上在路边摊high了很久，各种吃西瓜，喝啤酒，吃烧烤，不亦乐乎。

翌日，5点大家就爬起来了，兴奋异常，肯德基还没开张，只好坐等。

酒足饭饱之后，登上咯。

哥哥我起初走起轻盈的小步伐

 

逐渐地，台阶渐陡



等到中天门，好多妹子已经hold不住了，改作缆车，哥当然杠杠的，不过还是备个红牛先（事实证明了哥的远见）。中天门之后，路变得更陡，山也更加险峻

到了18盘，是这么个情况了，肿么样，软了没有，不是吓软，而是累的，各种用拐杖有木有，这个时候红牛就给上力了。



终于到顶了，路过一堆文艺的地方，不知道叫啥 - -，这个地方人比路上人多，主要是好多做缆车上来的，他们亏大了，没有走18盘



看日出那地方，附件有个宾馆，我管它叫“宾馆有个球用”

下面就是返程了，按下不表鸟。

tips：

• 关于带衣服，晴天的话顶多需要外套，男生甚至于可以不带，T恤足以（我被一哥们坑了，让我带毛衣，累死爹啊）


• 爬台阶走蛇形路线，腿舒服一点


• 红牛搞起


• 且爬且休息，欣赏风景，一鼓作气反倒更累

《搜索引擎信息检索实践》 notes 之showing the result

此章节主要描述通常的搜索引擎的搜索结果的组成部分，以及可能涉及的比较关键的问题，问题的解决简单提及，并未深究。

1.结果页和snippet

Google搜索flower的结果，其中最上面有底色的是广告。

搜索结果由一系列的文档摘要组成，每条摘要包括title，url，cache，snippet（概述文档内容），匹配的关键字往往会高亮（加粗或者其他颜色），而这其中snippet对用户判断搜索结果是否相关至关重要，下面就来看一下相关的知识。

snippet generation
snippet是文本摘要提取的一个分支。区别在于snippet产生不仅要包括和query无关的摘要，而且还要包括和query相关的摘要。

文本摘要技术始于1950s（Luhn），他的方法是基于重要度因子（significance factor，即为SF）对文档中的所有句子进行排序，选择top的几个句子作为摘要。而句子的SF取决于word的SF。而重要的word是指中等频率的word。
计算句子的SF方法如下

• 找到重要的word


• 找到重要的text span，text span由重要的word，和其他word组成，而其中两个重要的word中间的非重要的word数目不能超过k（通常为4），然后计算text span的重要度，为m2/n，m为重要的word的个数，n为text span的长度


• 句子中重要度最大的text span的重要度即为句子的重要度因子

snippet的生成可以看成是Luhn的方法在寻找重要的word和如何选择句子的阶段做一些变体。如选择重要word，计算word的频度的时候，可能会针对文档中句子的个数做一些平滑。而如何选择句子往往会考虑到句子在文档中的位置信息，是否是标题，是否是第一行，句子中的query term的个数等等。在网页中，有时候考虑metadata，这些数据中包括description，而其他的如wiki，则有对应的简单的入口可以作为摘要。

最重要的一点是，query中的所有term尽可能出现在snippet中，以表明query和文档的关系。

2.搜索和广告

广告是搜索引擎的收入来源，搜索结果中展示广告称为sponsored search。

sponsored search并不是简单的文本搜索，需要考虑到更多经济学和博弈论相关的知识。
先从retrieval的角度来看，问题的关键是做短文本之间的匹配，query和广告都很短，假如做匹配或者相似度计算，内容显得单薄，因此文本扩展的技术非常重要，文本扩展通常使用的技术包括两种：

• query reformation，利用session log来扩展出query reformation的list来代表query


• 使用搜索结果扩展，将广告的文本或者query的文本的搜索结果来代表query或者广告

关于排序，广告的排序往往会考虑广告的质量和bid，而质量往往和相关性和点击率相关，即大概是rank by(ctr * relative * bid)

3.结果聚类

记得上学的时候我做过相关的工作，不过是基于语义网的对象识别，相对来说可能容易一些。而对于通用搜索引擎，据我所知，目前貌似主界面没有采用聚类的方式展示的，不过最近google的knowledge graph展示了比聚类更好的对象识别技术。

结果聚类的时候两个问题至关重要

•  首先是效率，因为聚类往往是实时的，算法的效率要高，即使有cache，大多数的query还是需要在线计算


• 结果的可理解性，目前有两种主流方式




• 类别实现没有，从算法聚类的结果总抽取word来代表聚类，有点是简单，缺点是可理解性差


• 事先定义类别，然后将聚类结果和类别进行match，优缺点同上述方法想法

推出互联网广告观察博客

inside adwords中文 blog升级为互联网广告观察blog http://www.adobserve.info/

之前自己仅仅致力于翻译adwords，同时自己时间有限，因此blog定位也很窄。今天hardygu给了我点建议，1是独立域名，2是可以扩大影响。自己思索了一下，也挺有道理的，独立域名也省得被墙，扩大影响确实有必要，但是目前仍需要谨慎，在新增作者之前，仍然主打adwords，做到专注。后续有其他作者之后，可以增加翻译的领域（更多的国外ad 相关的blog等）以及原创评论等等。

感谢liangqing提供的空间：）

 

《搜索引擎信息检索实践》 notes 之query transformation and refinement

整理一下最近看书的notes，一来share一下自己的理解，顺便可以交流，二来不让自己的note荒废，乱乱七八糟。没有按照书的顺序阅读，当然到最后有整理一个list，更加有序地列出来。

这一篇是query transformation and refinement，讲述了一下几点

• stopping and stemming


• spell checking and suggestions


• query expansion


• relevance feedback


• context and personalization

1. stopping and stemming revisited

• stopping即stopwords相关的工作，


• stemming主要是涉及单词多态，找到单词的原始态，甚至是同义词match的问题

这个大家都了解的比较多，不赘述

2. spell checking and suggestions

这二者是用户最常见的query变化的形式了，二者的方法比较类似，区别在于前者的原始query是wrong的或者un populoar的，SE会猜测是不是输入错误了，只给出一个候选，而后者是在用户输入任何queyr的时候，给出top k的候选，协助用户输入的同时给出建议。

形式如下

checking：

suggestion：

二者的方法比较相通，可以概述如下

普通文本最basic的方法是使用拼写字典，计算拼错的word和字典中的word的编辑距离

编辑距离：

1. insertion


2. deletion


3. substitution


4. transposition

计算拼错的word和字典中的word的距离计算量很大（要有一定的候选），有一些手段，包括一些近似的方法

1. word A和B的start letter必须相同


2. 相同或者类似的长度


3. 发音类似，等（在英语中应用）

得到候选之后就是ranking所有的corrections

1. 典型的有按照降序排列


2. 对于搜索引擎，通常只需要best one

需要noisy channel model这个framework来ranking，在language model中，word w的概率分布为p(w)，用word occurrence即可。noisy channel为P(e|w)即persion想写w，却写成了e的概率，该概率成为error model，编辑距离长的概率更小，使用的时候对于编辑距离一样的e，概率可以假设相同，而rank的时候使用的是P(w|e)，做一个贝叶斯变化即可=P(e|w)*P(w)/P(e)，p(e)不变，等价于，P(e|w)*P(w)，这个是上下文无关的rank

考虑到上下文有关的，可以考虑二元的贡献，即前一个word的因素，word的language可以使用一个混合的概率模型，即为lamda P(w) + (1-lamda)P(w|wp) wp为previous word，在p(w)相同的情况下，P(w|wp) 利用上下文来判断选择谁

spell checking的流程

1. 切词


2. 使用词典和query log等资源寻找候选corrections


3. 使用noisy channel model选择最好的correction


4. 迭代上述的过程，知道找不到更好的correction（注意假如迭代多了会转义）

实验表明，query log的language model是correction accuracy中最重要的部分，error model比较次要，但是假如没有使用qurey log（只使用doc集合）的话，error model更加重要，好的实践是query log + application的dictionary，构建noisy channel model query expansion

3. query expansion

通常用于

1. 搜索的时候会利用query的同义扩展或者相关的query来增加召回


2. 用户交互界面的半自动化query提示，即suggestion

query expansion技术通常基于word或者term的共现（co-occurrence），集合可以是整个文档集合，query的机会，或者是搜索结果中的排名靠前的一些docs，著名的有pseudo-relevance feedback后续会提到，term association measure在expanseion中非常重要，有以下一些度量

1. Dice's coefficient = 2*Nab/(Na + Nb) (rank等价于) Nab/(Na + Nb)


2. 互信息mutual information = log(P(a,b)/(P(a)P(b)))，而P(a,) = na/N，因此上式等价于 log(N*Nab/(Na*Nb))等价于Nab/(Na*Nb)


3. 混信息的期望expected mutual information = P(a,b) *log(P(a,b)/(P(a)P(b))) 等价于 Nab*log(N*Nab/(Na*Nb))


4. 皮尔逊系数 pearson's chi-squared(x2) measure =(Nab - N * Na/N * Nb/N)^2 / (N * Na/N * Nb/N)

其中2和4偏向于低频的terms

4. relevance feedback

rf是基于query session的，而不是基于历史数据的，即点击数据可能用不上

rf是基于retrieval model相关的假设的，如假设搜索的前几条结果靠谱，从中抽取相关的term来扩展query，进一步去retriveal

事实证明suggestions要比是使用rf要好，目前也更加流行，因此不铺开说了

5.context and personalization

why:起初多数搜索引擎的特点是一个query的返回结果是相同的，不管是谁提交的query，为什么提交，在哪里提交，抑或在同一个session中其他的query是什么样的。然而事实上，我们在提交query的时候，是处在某上下文中的，而这些上下文，不仅影响检索到哪些文档，还影响到如何ranking。而上下文信息往往很难捕捉，或者不能一直保证效果。

1. personalization

user model和user profile

user model和user profile被研究用来代表用户的insterests，以便将搜索个性化。例如：同时搜索“rose”，对花感兴趣的人和对电影感兴趣的人所得到的结果理应是不同的。

然而这种思想有下面的问题。

• user model的准确度问题。构造user model往往基于用户看过的文档，访问过的web页面，email信息，以及桌面文档等等。然后从中提取term，进行tf，idf之类的计算，最终获取一个term的权重列表。


• 然而，在这些文档中，一方面用户感兴趣的只是文档其中某一部分，并非文档的全部，另一方面，这些文档仅仅代表了用户的一部分兴趣，而不是全部， 即从文档中抽取的兴趣和用户的真实兴趣的match程度是不确定的

predefined category 

还有的方法询问user的兴趣，然后把user划入预定义的类别

• 这个方法的弊端在于，喜欢鲜花的人，也可能去询问一个和电影相关的query


• 因此事先将user划入类别也是不好的，query粒度的category仿佛更好，然而这还不如输入更加确定的query来的方便，如输入rose titanic，而不是输入rose的时候再选择category是film

隐私问题

人们现在越来越关注自己的隐私，建立user profile现在的利弊还不是很清楚（Google+也带来了诟病）

2. context information

• 利用query log和点击数据来改进搜索，这里的context包括session中的previous searches以及实现挖掘的similar search session（利用统计）


• local search，从query中识别出location相关的信息，然后和对应的location相关的文档match上，流程通常如下

1. 对web pages预处理，识别出其中的地理位置


2. 人工添加的location 元数据


3. 文本解析，识别出地名


4. 识别出query中隐含的地理位置，可以通过query中包含的location，或者设备的ip，等。可以通过分析query log，发现包含location的query是非常多的，15%左右，（在中国这个比例更高）。


5. 结合locatioin信息进行rankking

总结，最有效的是利用past interactions，即query log和session history，而对于location相关的，可以进一步使用local search，而这些工作的目的是对不是specific的query进行expansion，使得更加specific，已达到context和personalization的效果

 

Inside AdWords 中文

blog除草，先推广下维护的AdWords相关的blog http://adwordszh.blogspot.com/

主要翻译Inside Adwords，还有一些关于AdWords的相关分析和报道，当然偶尔也会涉猎一下bing，yahoo，yandex，百度等相关search engine的sponsored search。

维护这个blog两个原因

1. 做一项翻译工作，而且能够长期坚持（现在看来还凑合 -  -）


2. 更多了解sponsored search

盘点下2012-1

流水帐记录大事件

• 完成论文


• 拿到驾照


• 毕业了


• 北漂，开始在度娘的工作


• 转正

学业：

写论文的过程非常好的描绘了一幅power law分布图，最后差点没难产。答辩的过程中老板提前走了，没有最终合影成功，算是一个遗憾吧。没有要学校坑爹的毕业照，一来是研究生的生活对于本科来说简直天上人间（别想歪），二来照片做得是在太差，把照片的电子档搞到手之后扔在了box.net，这样大家都好了。

工作：

苦逼的研究生升级为苦逼码农，老人说对比实习时候的我，哥带来的欢乐已经弱于当年（都是苦逼闹的有没有）。吐槽能力和概率下降，流氓能力下降、愤青指数上升。

被扔在海里，结果没有被淹死，然后就修炼升级了，于是在技术上也被升级了。

生活：

校园：

各种happy啊

工作：

说一点北京和南京的区别吧，从生活的总体享受上来说，已经差了一大截了（富二代、官二代、榜上大腿的请无视，四环内同学请绕行）。

空气质量差，当然南京也不好，但是不像北京都TMD的要爆表了有木有，pm2.5吓死人啊，小时候得亏喝过××奶粉、吃过地沟油，要不顶不住。

干燥，这个因人而异，好处是省得晒被子，坏处是夜里都得爬起来喝水，太坑爹了。

以上两点直接导致我颇费3600买了个净化器and加湿器，京东账户直逼金牌- -，不过确实效果不错（已经过滤社会认同影响力带来的判断）

超市贵，特指家乐福，到金润发面前就是个渣。

消费过程中，遇到的服务水平较南京差，当然好处是简单直接

在北京生活的过程中要特别感谢老婆在生活上的造诣，让我得以天天可以得瑟，mua mua mua

其他：

参加过几场婚礼，蒋狗的、哥的、凯子的，还有落下的，老大和马驴的，在这里一并祝福他们

修炼：

肉体：夏季踢球，没有比赛了玩乒乓，天冷了玩羽毛球，来年要健身，ps，期间去滑雪，很赞，发现我还蛮有天赋：）

灵魂：思考时间增多，读了几本闲书、很是震撼，推荐下《叔本华美学随笔》和《影响力》，决定以后多读点好书，入了kindle touch，多读书