Monthly Archives: February 2009

下载videolectures.net里的视频的方法

videolectures.net是一个很好很强大的网站,里面有各种学科的大量学术讲座视频,其中尤其又以CS的为多。视频可以在线观看,还有配套的slides可供下载。唯一不爽的是视频用通常的方法是下载不了的,即使得到了mms开头的URL,再用快车或影音传送带等软件下载也不行。虽然在线看的话流畅性也完全没有问题,但对于大部分教育网学生用户来说,毕竟流量宝贵,所以我只好找了一堆软件来试,发现这个Replay Media Catcher这个软件很好使,只要先把它打开,再访问包含流媒体的网页,它就会自动探测到视频并开始下载,而且在下载过程中你无须再一直播放着那个视频,完全可以把网页关了去干别的事,等下完了再慢慢看,非常的方便。下载以后得到的是flv文件,半个小时的视频大概是100M左右,应该也不算很大。软件的具体使用请参考其官方主页,在此不再赘述。

另外要说的是这个软件只能免费下到Demo版,Demo版的限制是对于Youtube之外的其他网站,只能记录下70%的视频。所以大家要想用得爽的话就去买一个吧,也不贵,$39.95而已……囧……

(以下反白, BS盗版的正义人士请无视,嘿嘿……)

我在本地传了一个破解版(点此下载,11.0M),内含原程序安装文件及一个破解补丁,经卡巴斯基检验无毒。请自行决定是否使用,本人不对其可能产生的后果负责任。:)

IR笔记(6) – Relevance feedback

本打算仔细看一下第七章,讲的是一个完整的检索系统的实现。但发现多是技术细节,看过一遍后没记住什么。而关于搜索引擎的具体实现似乎有更专门的书作介绍,所以先跳过了,等以后有机会再仔细看。

这次说下另一个比较有意思的东西,Relevance feedback(翻译成“相关性反馈”?)。它是指在第一次返回检索结果之后,用户可以标记出哪些结果是自己认为相关(Relevance,或者翻译成“中肯”?)的,哪些是不相关的,然后系统根据用户的反馈再进行检索,以得到更好的结果。这个过程还可以持续进行下去。这种想法的动机是,在一开始的时候用户自己也往往不清楚自己想要的东西应该怎样用Query表示,但是给已有的结果标记是否相关就相对容易得多。

继续用向量空间模型考虑问题,把Query也看成一个向量,现在用户已经对一些文档进行了“相关”或“不相关”的标记,我们的目标是找到一个新的Query,使得它离相关文档较近而离不相关文档较远。假设所有的文档都做了标记,如果我们用前面所说的Cos相似度的话,这个新Query应该是全部相关文档的质心(centroid,即各个维度的平均数)与全部非相关文档质心之差。但现在用户的标记只是一部分,我们不能跳得太厉害,这样就得到下式:

$$vec q=alpha vec q_0 + beta frac{1}{|D_r|} sum_{vec d_j in D_r} vec d_j – gamma frac{1}{|D_{nr}|} sum_{vec d_j in D_{nr}} vec d_j$$

这里q0是初始的Query,Dr是指相关文档的集合,Dnr是非相关文档的集合。也就是说把q0向着相关文档质心移动一点,背离非相关文档质心移动一点。这里alpha,beta,gamma都是可调的参数。这个貌似叫Rocchio算法。

在实际的搜索引擎中这项技术应用得并不多(Google和百度好像都没有吧?),主要原因大概是这项技术主要是改进Recall,而Web上的搜索大家都不太care这个,Precision相对更重要,而且很少有人有耐心给检索结果一个个作标记。所以恐怕只有在某些专门的场合,比如我们在图书馆费尽心机想找到一本老书的时候,这项技术才比较有用处。基于同样的原因,那三个参数里通常beta设得较高,gamma设得较低,甚至为零,即正反馈的结果更受重视,这也是为了改进Recall。

鉴于用户往往懒得去作标记,这里有两种改进方法:一个叫Pseudo(Blind) Relevance Feedback,指针对用户的Query先进行一次检索,把得到的排名最高K条结果自动标记为相关,然后执行Relevance Feedback算法(个人感觉这个很不靠谱呢-_-);另一个叫Indirect Relevance Feedback,指不显式地要求用户作标记,而从用户接下来行为中去判断,比如用户点击了某条结果链接,那么通常就可以认为这条结果是相关的,对于流量很大的搜索引擎,这样获得的信息已经相当可观。

另外一点是这种方法不止能应用于向量空间模型,还可以用在概率模型中,后面马上要提到。

贝叶斯公式在ACM比赛中的应用

我承认这个标题很囧,但是我今天确实用这个很囧的方法过了一道POJ月赛题:POJ 3716 Panda’s Birthday Present

题意是说,有4个六面的骰子,在一开始的时候对每一面各以50%的概率染成红色或蓝色,然后掷了两次,每次的得分为4个骰子里面掷出红色向上的数目。给定两次的得分x,y (0 <= x,y <= 4),问第三次的得分的期望是多少。

个人认为,这道题目最后的“期望”的定义不甚明确。如果按照解ACM题的思路,我会这样考虑问题:把四个骰子的红色面数组合成一个状态<s1,s2,s3,s4>,求出每个这种四元组的概率,然后利用x,y这两个值,可以排除掉肯定不可能的四元组,把剩下的概率重新归一化,再求第三次的期望,但是按这种算法无论如果对不上样例(也可能是我写错的),一囧之下我就yy出下面一个算法:

从贝叶斯概率的角度来想这个问题,在不知道x,y时计算出的四元组<s1,s2,s3,s4>的概率作为先验概率P(<s1,s2,s3,s4>),然后我们进行一次试验,设得到的值为x,则由贝叶斯公式,后验概率

$$P(<s_1,s_2,s_3,s_4>|x) = frac{P(x|<s_1,s_2,s_3,s_4>) P(<s_1,s_2,s_3,s_4>)}{P(x)}$$

在等号右面,先验概率P(<s1,s2,s3,s4>)通过dp和组合公式容易得出,似然函数P(x|<s1,s2,s3,s4>)也可由dp得到,P(x)是归一化因子,可以先不予考虑。于是得到观测值<x,y>的后验概率为

$$P(<s_1,s_2,s_3,s_4>|<x,y>) = \ frac{P(<s_1,s_2,s_3,s_4>) P(x|<s_1,s_2,s_3,s_4>) P(y|<s_1,s_2,s_3,s_4>) }{Z}$$

这里Z是归一化因子,即为对所有四元组<s1,s2,s3,s4>求得的P(<s1,s2,s3,s4>|<x,y>)之和。

求得了这个之后,第三次得分的期望即为 $$E = sum_{i=0}^{4} P(<s_1,s_2,s_3,s_4>|<x,y>) P(i|<s_1,s_2,s_3,s_4>) $$

ps. 据说有人得到超级简单的公式,最后结果就是(x+y+10)/7,我不知道是怎么推出来的,望大牛指点……

再ps. 这次月赛单挑拿了个第三,居然是在退役后拿到历史最好成绩……

IR笔记(5) – Vector Space Model

利用上次提到的TF-IDF或其它加权方式,我们可以对每篇文档里的每个单词赋一个权值,这样,一篇文档就可以看作一个向量(vector)——实际上也就是如果把反向索引那个表再看成矩阵,那么每个列向量就对应一篇文档——这样就得到了所谓的向量空间模型。这个模型不只在文本检索中,在分类、聚类等很多问题中都起核心作用。

来看这样一个问题:如何衡量两篇文档的相关程度?这个问题如果解决了,文本检索就可以自然解决,因为一个Query也可以看作一篇(通常是很短的)文档。一个自然的想法是用两个向量之差的长度(即两个向量端点的[欧氏?]距离),但这个选择并不太好,比如有文档A和B,其中B只不过是把A简单地重复了两遍得到的,按理说这两篇文档应该非常相似,但它们的长度差了一倍,所以结果并不好。一个更好的选择是所谓Cosine Similarity,也就是两个向量夹角的余弦值。设两向量分别为$$vec V_1$$和$$vec V_2$$,根据基本的线性代数知识得到:

$$sim(vec V_1,vec V_2) = cos(alpha) = frac{vec V_1 cdot vec V_2}{|vec V_1||vec V_2|}$$

其中分子部分是向量点积,分母部分是两个向量的欧氏长度之积。

进一步地,每次都计算|V|是没有必要的,我们可以直接把长度“归一化”:$$vec v_i = vec V_i / |vec V_i|$$,这样就得到:

$$sim(vec v_1,vec v_2) = vec v_1 cdot vec v_2$$

按照前面所说的,把Query也看作文档,对Query里的每个词t也计算TF-IDF,记为w(t,q),对文档d里的每个词t计算TF-IDF记为wf(t,d),则算法如下:

1. 置所有文档得分Score[d]=0

2. 对Query中的每个词t,扫描t所对应的posting——posting的每个节点处记录着(d,wf(t,d))这一对值,即文档编号和对应的TF-IDF权值——则Score[d] += wf(t, d) * w(t, q)

3. 对每个Score[d]归一化:Score[d] /= length[d],这里length[d]表示向量的长度

4. 选择Score[ ]中最大的K个,这就是最相关的K篇文档

当然这样的计算效率是不高的,难以实用,所以还需要后面提到的各种优化才行。

另外在实际情况中,除了这种相关度,我们还需要考虑其他的东西,比如文档自身也有重要性上的区别,所以我们还需要有一个衡量文档自身重要性的指标(比如大名鼎鼎的PageRank),然后可以把相关度和重要性做一个加权组合。

IR笔记(4) – TF-IDF

本篇开始讨论比Boolean Retrieval更复杂的检索,想象一下我们平常用的搜索引擎,一个很明显的特点是返回的结果是有序的,越相关越重要的结果排得越靠前(竞价排名除外- -),下面主要就讨论如何给文档打分排序的问题。

这回把扯淡的话先放在前面说,我长久以来抱持一个想法:无论外表看上去多么复杂的一个方法或理论,其核心思想或者说原始动机往往都是很朴素很直观的,只不过在其发展、完善、实现的过程中不得不变得复杂,如果我们顺着方法的创始人当初的思路来看问题,看看他当时已知什么,面对的困难是什么,再印证最终的解决方法是如何巧妙地把问题搞定的,这样就不会经常迷失在具体的细节中,知其然不知其所以然了。当然,直观的同时也一定是不严谨的,所以再次回归复杂而严格的表述也必不可少。我不知道这个看法对不对,至少在研究ACM比赛里用到的算法时经常会有这种感觉。所以我在下面讲述方法的时候也往往先描述遇到的困难,再看那些方法是如何解决困难的,而不是一上来就给一坨莫名其妙的数学公式。我认为我的方法是比较符合人的学习过程的,当然因为水平有限,错误在所难免了,呵呵。

扯淡完毕,回到给文档打分的问题。一般来说,如果文档中出现了我们查询的词,我们就认为这篇文档是和此查询相关的。那么很自然的想法就是,如果一篇文档中出现要查询的词的次数越多,相关性应该越大。所以定义一个Term-Frequency TF(t,d)表示单词t在文档d中的出现次数,以它作为一个度量相关度的标准。但是只考虑次数还不够,因为不同词的重要性是不同的,比如考虑一个小型的文本库,里面都是各位ACMer的文章,可以想见,“算法”这个词会出现在大部分的文章中,而“ppmm”这个词只在少数文章中才有。现在我要查询“算法 ppmm”,结果找到两篇文档同时出现了这两个词,第一篇是RoBa写的,里面出现了1次“算法”和10次“ppmm”,另一篇文章是另一位ACMer写的,里面出现了10次“算法”和1次“ppmm”,如果我们只累计TF,会发现两篇文档都是11,但是实际上RoBa的文章应该排在前面,因为“ppmm”这个词相对来说较为稀缺,所以它的权重也应该比较大。为了量化这个稀缺度,引入Inverse Document Frequency(IDF),定义为IDF(t) = log(N / DF(t)),这里的DF(t)是指单词t在多少篇文档中出现过(Document Frequency),N是指总的文档数,log的底数实际上可以随便取,因为最后我们只关心相对大小。容易发现,如果单词越普遍,它的IDF越小,极端情况是DF(t)=N时,IDF(t)=0,从下面的式子能看出,这实际上就起到了stop list的效果。把这两项结合起来,对单词t和文档d,定义TF-IDF(t,d) = TF(t,d) * IDF(t)。直观来解释就是:一个单词在一篇文档中出现次数越多,它的权重越大;文档中单词越是“只此一家别无分店”,它的权重越大。现在我们就有了一个简单的打分方法:一篇文档和一条Query的相关度为Query中所有单词在这篇文档中的TF-IDF值之和。当然还有更强大的计分方法,后面慢慢再提。

另外说一下,TF-IDF并不是唯一的加权方式。比如我们可能认为这个值和term的出现次数成正比这一点太夸张了,一篇出现了10次“ppmm”的文章未必就比一篇出现1次“ppmm”重要10倍,所以可以搞出一个sublinear TF:当tf(t,d)>0时,定义wf(t,d) = 1 + log tf(t,d),然后用这个wf代替tf去和idf相乘。另外还有其他一些方法,在此不再赘述。