有监督下垂直搜索引擎排序算法的设计思路

有监督下垂直搜索引擎排序算法的设计思路2011-09-30 博客园 xiaotie本文是很久之前写的，刚才翻硬盘翻到了，现在放出来。这只是一个形式化思路，暂时没时间去实现，我简单验证过这个形式化过程，暂时还没发现问题，但不保证这个过程没有问题。如果您发现了问题，还请指正，谢谢！

垂直搜索领域目前没有通用的判断排序结果优劣的标准，为此引入监督者这一角色，希望设计算法，使该算法对搜索引擎的排序结果尽量接近监督者的排序结果。

引入1位专家作为监督者S。S选择关键词K。输入K，检索得到M条结果，然后在M条结果中随机选择N个结果，得到序列S_R={R₀,R₁,……,R_n-1}。

S根据经验，对这N个结果进行排序。得到序列S_S={……,S_i,j,…… }，其中，S_i,j的脚标i代表S_i,j在源序列S_R中的位置，j代表序列 S_i,j在S_S中的位置。如S_4,2代表这个任务在源序列对应为 R₄，在新序列S_S中排第3（脚标是2，但因为元素脚标是从0起始的，因此排第3位。）。

定义函数 Φ_S（R_j）为R_j在序列S_S中的的位置。假设序列S_S={S_5,0, S_2,1,……,S_74,312}，则有 Φ_S（R₅）=0; Φ_S（R₂）=1; Φ_S （R₇₄）=312;

令X是一种排序算法，X对序列S_R排序得到序列S_X。Φ_X （R_j）为R_j在序列S_X中的位置。

令（R_m,R_n）为S_R中不同元素的组合序列。这些序列组成集合：

C = {（R_m,R_n）| m≠n , R_m∈S_R,R_n∈ S_R }。

令Ω_X（R_m,R_n）= -sign（Φ_X（R_m）- Φ_X（R_n））。

其中，

Ω_X（R_m,R_n） >0，意味着排序算法X将R_m排在 R_n的前面。

令E_X,S,R是C中X排序结果和S排序结果不一致的序列的集合：

E_X,S,R= {（R_m,R_n）| （R_m,R_n） ∈C, Ω_X（R_m,R_n） ≠ Ω_S（R_m,R_n）} 。

令λ_（Rm,Rn）是X排序结果和S排序结果不一致的代价函数，采用以下的代价函数：

λ_（Rm,Rn）=|m-n|

令总代价 Λ（E_X,S,R） =Σλ_（Rm,Rn）,（R_m,R_n） ∈ E_X,S,R