Tag Archives: 高级算法

还原谷歌PageRank算法真相

之前写了七篇博客详细介绍了搜索引擎的工作原理。彼时的搜索引擎主要讲查询和网页的相关性匹配,是动态的、在线的、实时的。相关性匹配有一个问题,网页很容易作弊,比如可以在一个网页中写满诸如“免费”、“美容”之类的垃圾关键词,进而提升查询相关性。但是用户在查询时,一定希望返回的网页比较权威可信,比如同样搜索“苹果电脑”,排名第一的应该是Apple的官网,而不应该是中关村在线之类的第三方网站。

权威性是一个静态的(或者说变化较慢的)衡量网页重要性的指标。但是应该怎样度量权威性呢,HITS算法使用authority来度量,即指向自身的网页数量越多,则自身的authority值越大。谷歌的PageRank算法是用PageRank值来衡量权威性的。HITS和PageRank一个比较大的区别是HITS和查询有关,而PageRank和查询无关,所以PageRank可以离线计算。下面主要介绍PageRank算法。

PageRank’s thesis is that a webpage is important if it is pointed to by other important pages.

Continue reading

调查问卷的有效性(2)相对误差

\begin{equation}Pr(|\hat{p}-p|\geq 5\%)\leq 5\%\end{equation}

上一回我们讲到当p本身很小的时候,容易被5%(绝对误差)给淹没掉,导致结果的不可信。我们可以引入相对误差,把(1)式转换为如下的不等式

\begin{equation}Pr(|\hat{p}-p|\geq\delta p)\leq\epsilon\end{equation}

同理,我们可以用

\begin{equation}\hat{p}=\frac{x_1+x_2+...+x_n}{n}\end{equation}

代替\hat{p}(建议先看上一篇博客),转换为

\begin{equation}Pr(|X-np|\geq\delta np)\end{equation}

类似的,X=x_1+x_2+...+x_nE(X)=\mu=np,所以(4)式等价为

\begin{equation}Pr(|X-\mu|\geq\delta\mu)\end{equation}

Continue reading

调查问卷的有效性(1)绝对误差

每年春晚过后,央视又要吹嘘说今年春晚收视率创新高了,但是我们总感觉央视在骗我们,因为我是越长大越不看春晚了[笑cry],所以收视率到底是怎么统计出来的,央视的说法是否靠谱呢?

最近的美国大选真是热闹,很多机构都会发放一些调查问卷,然后统计出希拉里或者唐纳德的民众支持率是多少,但是我并没有收到调查问卷,凭什么就得出了民众支持率了,意思是把我排除在民众之外咯?所以引出这样一个问题,调查问卷是否可信,即调查问卷的有效性。

其实,央视统计收视率并不要问全中国14亿人口有多少人看了春晚,他只需要从14亿人口里面随机抽n个人,问一下这n个人里有多少人看了春晚,然后把看的人数除以总数就大概估计出全国的收视率了。同理调查民众支持率也是一样,只需要随机调查n个人的意向,把支持希拉里的人数除以总数就大概得到了希拉里的支持率。

但是你要问了,通过抽样调查出来的收视率和支持率靠谱吗,需要随机抽样多少人才能得到一个比较好的全局近似解呢?今天我们就来解决这个问题。 Continue reading

有趣的交互式证明

你是否想过如下问题:怎样向色盲证明两只袜子的颜色是不一样的?怎样证明两个图是不同构的?怎样证明一个数是二次非剩余的?

咋听起来觉得很有意思吧,色盲是区分不了颜色的,怎么能让他相信两只袜子的颜色不一样呢。图同构问题目前既没有被证明属于P,也没有被证明属于NP-Complete。二次非剩余问题也没有被证明属于NP。

这些听起来很“难”的问题,却可以通过交互式证明进行证明,下面先通过“向色盲证明两只袜子的颜色不同”这个有趣的例子一窥交互式证明的强大。 Continue reading