搜索算法 转移概率 有向图图模型

PageRank搜索：搜索引擎网页排序算法

Posted by 高庆东 on July 12, 2018

搜索引擎的网页排序算法

背景介绍

网页搜索的时候需要对搜索结果进行排序，排序的依据是网页的分数

也可以理解为网页的概率。网页的概率越大排名越靠前。所有网页的

概率和可以使1也可以不是。

该方法主要依靠三个假设：

  • 可以连接到该网页的网页数越多则该网页的概率越大
  • 连接到该网页的网页的概率越大则该网页概率也越大
  • 从一个网页转移到其他网页的概率是相等的（转移概率）

实例

假设现在一共有N个网页，那么初始阶段用户访问每个网页的概率就是N

分之一比如下图中的初始概率向量为(1/4,1/4,1/4,1/4)

(1/4,1/4,1/4,1/4)(1/4, 1/4, 1/4, 1/4)，而因为每个网页都可

能存在着到其他任何网页的链接，所以，我们可以将这些链接以平均的

概率表示成一个概率转移向量。比如下面这张图，网页A中有3个链接，

分别指向B, C, D，则A的概率转移向量为(0,1/3,1/3,1/3)

(0,1/3,1/3,1/3)(0, 1/3, 1/3, 1/3)，向量的维度依次对应的是

网页A指向A, B, C, D四个网页的概率。

网页模型

转移概率矩阵可表示为

转移概率矩阵

经过一次跳转后的概率是

一次转移概率

N次跳转的的概率会趋于一个稳定值

转移公式

问题

一些网页没有连接其他

一些网页只连接了自身

针对以上问题设定一个超参数避免转移概率全为0或者有一个是1

修正概率

a乘转移概率矩阵T乘上一次的概率加（1-a）乘初始概率

a是一个超参数可以是设为0.85

pagerank不足的地方

  • 没有考虑网页本身给出的导航信息
  • 广告和功能连接（考虑网站本身的作用）
  • 对新网页几乎搜不到
CATALOG
    FEATURED TAGS
    c语言 c++ 面向对象 指针 容器 python 函数 数据结构 回归 损失函数 神经网络 机器学习 似然函数 极大似然 标准化 深度学习 卷积网络 参数估计 beta分布 数据处理 gradio 模型工程化 网页 模型加速工具 c++实现 变量 占位符 tensorflow 线性回归 学习tensorflow HMM RNN 强化学习 LSTM pandas 不定长序列损失 pytorch 目标检测 RPN 非极大值抑制 ROIpooling VGG16 Transformer BERT Python 装饰器 方法 Pytorch FPN 图像分类 CNN 多模态 生成 GPT Tranformer 生成模型 audio