算术

前一阵子也参加了一个Yahoo的面试，因为方向特殊，没有经过HR的面试，直接就跑了过去，问的全是概率相关的问题。这里我想说的是最后一个开放式的问题。其实这已经不是面试题了，而是他们当时正在考虑的项目，说出来挺有意思的。谁叫没让我签保密合同呢。

Yahoo!自己有一个照片分享网站，就是flickr。flickr有两个功能，一个是可以给每个照片加标签，以便於搜索，另一个就是每个照片可以关联到地图上的一个位置上。想象一下大家都给照片加什么样的标签呢？最多的恐怕就是照片里的人物和拍摄的地点了。于是雅虎开始考虑能不能用用户输入的标签和图片的地理位置信息给Yahoo!地图作标注。好比在yahoo地图上用户正在显示某个区域，我们可以用算法来计算出一个最恰当的名字。比如，你正在看北京海淀区附近的地图，那么它应该显示这里是海淀，而不要说北京或是中国，也不能是海淀里面的某个镇某个村。怎么做这个算法呢？

我当时给了他们一个方案，看面试者的反映，显然比他们已经想到的要好不少。其实方法很简单就一个公式：

arg_i max - p_i log q_i

这里，p_i 是在当前显示范围内标签 i 出现的概率（占所有标签出现次数的比率），q_i 是在一个背景区域（比如上例中的背景区域可以是中国或亚洲）中这个标签出现的概率。按照信息论，-log q_i 是这个标签在背景区域中每出现一次所提供的信息量，p_i 则对应着这个标签在当前范围中出现的次数。因此这个公式实际上选择了相对于背景区域在当前范围内提供信息最多的标签。

他们当时手工检测了一些例子， 看着表情很惊讶的样子。所以我就蒙混过关了。不过现在想起来，下面这个类似信息增益的式子可能更合适：

 arg_i max p_i log q_i/p_i

至少对于和背景区域相比没有什么变化的标签（比如上例中的中国），因为p_i ≈ qi ，所以提供的有效信息很少。这是比较合理的。 这个公式表示的是当前范围中这个标记提供的信息比在背景区域中增加了多少。