承接上一篇分享，这次内容的主题是《广告与网页相关性》。
现在地球人都喜欢刷微博，我不知道大家平时都刷些神马，我自己就比较喜欢刷娱乐新闻，关注下明星们的一些八卦。看八卦是挺欢乐的，不过有时候看网友们转发的那种盖楼评论，你会发现更欢乐，更搞笑。比如说下面这个：
当时看到这个的时候，我也邪恶地笑了（纯洁的同学就不要问什么意思了，自己google去吧）。欢乐过后，你会不会有这样的问题：为什么网友们都提到“信息量”这个词？“信息量”到底是什么东西？为什么这条微博的“信息量”就太大了呢？
好，我们先来个直观认识。我们平时看到的文字、图片，听到的声音，不管什么，它们或多或少，都会给你带来一些信息。而这些信息，其实是具有一定的统计特性的（statistical），在我们得到消息之前，对它的内容有一种“不确定性”，而信息就是对这种不确定性的定量描述。当我们得到消息后，如果事前认为消息中所描述的事件发生的可能性小，那么就认为这个消息给我们带来的信息量大；相反，如果我们事前就对事件非常了解，预期它发生的机会非常大，那么就认为消息带来的信息量小。所以，信息量是跟消息所代表的事件发生的概率有关的。信息论（Information Theory）利用统计学概念，提出了一个衡量信息的物理量，也就是我们说的信息量。
设消息代表的事件出现的概率为P(X)，那么这个消息所含有的信息量就为：
I = log(1/P(x)) = - logP(x)
上式中的对数如果底为2，那么信息量的单位就是我们非常熟悉的比特（bit）了。所以，假如我说，下个月又要经常加班了，那这个事件应该说没什么信息量；但假如我说，下个月我们组要集体涨工资，那这个事件的信息量就太大了。（这怎么听着有点不幸福啊。。。一定是我举例子的方式不对！）
除了单个事件之外，我们的消息也可能由n个事件组成。例如“今年NBA季后赛的总冠军”这个消息，它的信息量实际上是由各个球队（季后赛总共会有16支球队）夺冠的可能性共同决定的。对于这个问题，我们信息论的祖师爷——香农（Claude Shannon）提出，如果一个消息由n个事件共同决定，每个事件发生的概率为P1(x)、P2(x)、……、Pn(x)，那么这个消息的信息量（这里，应该理解为平均信息量）等于这些事件自身信息量的数学期望，也就是：
H = ∑ Pi(x)*Ii
= ∑ Pi(x)*log(1/Pi(x))
= -∑ Pi(x)*logPi(x) (1 <= i <= n)
这个定义和统计热力学中的熵的定义类似，所以在信息论里，它有一个类似的名字，叫信息熵（Entropy，也叫信源熵）。除了信息熵，信息论里面还有一个重要的概念，叫做相对熵（Kullback-Leibler_divergence）。给定两个概率密度函数P(x)和Q(x)，它们的相对熵为：
D(P||Q) = ∑ P(x)*log(P(x)/Q(x)) (x ∈ X)
相对熵描述的是两个随机分布之间的差异程度。当两随机分布的差异增大时，它们的相对熵也会增大。考虑下面这个搭配倾向性模型的问题：设A、B是两个随机事件，且P(A)>0，若A、B相互独立，则有P(B|A) = P(B)。我们用相对熵D(P(B|A)||P(B))衡量两者的近似程度，若P(B|A)和P(B)的近似度越大（相对熵越小），说明A与B的独立性越强；若近似度越小（相对熵越大），说明A与B之间的独立性越弱，也就意味着A与B的相关性越强。这个东西有个用途是从大量文本文件挖掘词对组合，也就是生成我们的2-gram语料库，不过等下将会看到，它与我们的主题有着密切的关系。
好，在思考广告与网页的相关性之前，我们先换一个角度，思考一个类似的问题。搜索引擎有这么一个基本问题：给出一个查询Q，它由n个关键词组成，我们需要找出包含（或包含部分）这些关键词的网页，并根据它们之间的相关性，进行排序。那么，如何度量一个查询与网页的相关性呢？
我们来举个例子，比如说，一个查询“贝叶斯定理的应用”，它可以分为“贝叶斯”、“定理”、“的”、“应用”这几个关键词。对于某个关键词，如果在一个网页出现的频率很高，那说明这个关键词应该是跟网页有紧密联系的。我们用一个归一化的变量——单文本词汇频率（Term Frequency，下面简称TF）来描述它。TF的定义很简单，就是指一个单词在某个网页里出现的概率，也就是单词本身在某个网页出现的次数，除以网页文本的总词数。当然做这个之前，首先得对网页做分词，不然你就无从下手了（所以说，分词分得好，什么都好搞）。
TF的解释与我们的直觉相符，但光有TF是不行的。因为对于每个单词，它们对主题的预测性是不一样的。就拿我们上面举的查询词串（“贝叶斯”、“定理”、“的”、“应用”）作为例子，像“的”这种单词，一点信息量也没有，我们称之为“应删除词”(stopwords），可以直接无视它的存在。而“应用”虽然比“的”多一点信息量，但由于它“感觉上”是个很泛的词，我们无法从这个词了解网页的主题。再看“定理”这个词，它的出现要比“应用”显得“有价值”，这可能是个跟学术有关的网页。要是再考虑到“贝叶斯”这个词的出现，那我们几乎可以大致判断网页的主要内容了，因为“贝叶斯”是个非常专业的词（专业到我手上的语料库里也找不到它的出现），不会“到处都看到”。所以，我们应该根据关键词的预测能力，给各个关键词分配一个权重。在信息检索（Information Retrieval）里，有个非常著名的权重——逆文本频率指数（Inverse Document Frequency，下面简称IDF），它的公式是：
IDF = log(D / Dw)
其中D是全部网页总数（样本空间），Dw表示出现w的网页数量。从这个式子可以看出，越是到处可见的关键词，它的IDF越低；而越是罕见的单词，它的IDF越高。IDF的解释也是与我们的直觉相符的，但至于它为什么是一个log函数，稍后见分晓。
有了TF和IDF后，我们计算一个关键词与网页的相关性就变成TF*IDF。而对于一个包含n个关键词的查询，相关性的计算就是词频的加权求和：
∑ TFi*IDFi （1<=i<=n）
根据这个公式，我们对包含查询关键词的网页进行计算（map），得到与这些网页的一个相关性数值，然后进行排序（reduce），最后把结果返回到用户页面。
到这里，终于轮到我们的广告匹配问题了。实际上一开始要做广告相关性的匹配，我并不清楚业界是怎么做的。但是这个搜索引擎对关键词和网页相关性的计算，让我觉得，广告相关性也许可以用类似的方法进行计算。我们对每一个广告素材定义一组关键词，那么这个广告就可以看成是一个“查询”了。广告关键词与网页的相关性计算，我们依旧用的是TF*IDF，不过最后阶段排序的不是网页，而是这些“查询”。所以前者解决的问题是，给出一个查询，返回页面的一个相关性排序；而后者解决的则是，给出一个网页，对所有查询进行排序，看哪个查询“最可能找到”这个页面。
这里有个小问题，就是假如有两个广告它们都拥有同一个关键词，对于一个网页都匹配到这一个关键词（简单地假设只有这一个），那么它们的相关性数值计算出来会是一模一样的。那是因为我们的TF*IDF“倾向于”描述我们的网页，而无论哪一个广告，当前计算的都是同一个页面。为了避免这种情况，我们可以在TF*IDF的基础上，再乘以关键词在查询词组的词频TF'。因为广告的关键词只会定义一次，所以这里的TF'就是所有关键词总数的倒数，你越是为广告定义越多的关键词，就说明每个关键词“分摊”的重要性降低。
另外，由于网页一般不是纯文本，而是带有大量标签的，每种标签里的关键词，权重应该是不同的。例如“h1标签”里面的词可能要比一个“a标签”里面的词要重要，“title标签”里的词也许要比“p标签”里面的词重要，等等。总而言之，TF*IDF是核心的算法，而围绕它，还需要做很多细节上的调优，来增强匹配的程度。
其实后来我又想到另外一种方法，就是为每个广告定义一组带权重的关键词，比如说{"游戏":1, "Dota": 5, "魔兽": 3}，里面的数字直接说明关键词的出现频率（也就是重要性），那么广告也可以看成一个页面分词后的“文档”了。我们分别计算所有广告关键词的TF*IDF（注意TF所在的样本空间），还有需要匹配的网页的所有实词的TF*IDF，然后对两者的TF*IDF向量，用余弦定理计算它们的夹角。如果它们的夹角越接近零，则说明它们越相似，越匹配；否则越不匹配。这样，广告匹配的问题就可以用新闻分类的方法解决了。不过这样做的缺点是定义广告关键词需要做的工作增多了，而且靠人工定义词频这个不好拿捏。先观望下前面做法的效果，再做定夺。
TF*IDF可以说是信息检索中最重要的发明，尤其是IDF，它是由英国一位非常杰出的女科学家——斯巴克-琼斯（Karen Sp?rck Jones）提出的。聪明的同学可能已经发现，TF*IDF跟上文提到的搭配倾向性模型非常相似。令P(w)为w在文档d中出现的概率（也就是TF），P(w|d)为d中出现w的概率（也就是IDF里的Dw/D），我们计算P(w)与P(w|d)的相对熵：
D(P(w)||P(w|d)) = ∑ P(w)*log(P(w)/P(w|d))
= ∑ P(w)*log(P(w)) - ∑ P(w)*log(P(w|d))
式子的前一项与排序无关，我们把它拿开：
D(P(w)||P(w|d)) ∝ - ∑ P(w)*log(P(w|d))
∝ ∑ P(w)*log(1 / P(w|d))
∝ ∑ P(w)*log(D / Dw)
∝ ∑ TF*IDF
D(P(w)||P(w|d))越大，说明P(w)与P(w|d)的近似程度越低，也就说明w和d之间的独立性越弱，也就意味着w和d的相关性越强。到这你会发现，信息检索相关性计算的解释，又回到了信息论。想更加深入理解IDF的同学，可以参考下Stephen Robertson写的这篇paper。
文章的最后，不得不感叹说，数学可以把这么复杂的现实问题，解决得这么简单而优美。无论是上回的贝叶斯，还是这次关于信息论的东西，都让人深深地感受到数学工具的鬼斧神工。可以大胆地说，这些问题如果不是用数学方法来解决，而是靠我们写一堆规则、流程，那么无论你的程序写得多么的工程化，多么工业级的水平，都是无法很好地解决的（起码是如此简单地解决）。好，智能广告的系列就到这里吧，期待下次为大家带来更多有趣的分享。See you next time！