2014年2月1日星期六

使用PageRank对金庸武侠的功夫进行排名


金庸武侠人物功夫排名是互联网上的年经帖。这种排名首先是在同一本小说的武侠世界进行,然后又扩展到整个金庸武侠世界。各种版本排名依据不一,又带有很强的主观性,因而得出的结论往往引发极大的争议。

在理想状况下,所有侠客切磋过且能得到一个偏序关系。这时候得出的排名最没有争议。举例来说,在《笑傲江湖》里,左冷禅败给岳不群、令狐冲,岳不群败给令狐冲,令狐冲败给东方不败。如果仅考虑这四个人,其排名自然为:东方不败、令狐冲、岳不群、左冷禅。可是在一般武侠世界里,首先并不是所有人物之间都打斗过;其次比武时胜负也不一定能够构成一个偏序链。比如《笑傲江湖》几个主要高手之间切磋的结果大致为:

如何排列这些人物之间的功夫就成了问题。

关于这个问题,我们可以用PageRank向心值算法来解决。其想法如下,一个人的功夫,可以由其他人的评价来进行估计。这个评价可以是比武,也可以是间接评价,比如任我行曾对风扬清有过很高的评价。如果甲败给乙,那么甲必然对乙的功夫有较好的评价。在甲乙打平的情况下,可以认为双方对彼此的功夫有好的评价。当然,从功夫好的人得到的好评要比从功夫差的人得到的好评要好。所以一个人$i$的功夫(用$p_i$来表示): \[
p_i = \alpha \cdot \sum_j A_{ji} f_j p_j + \beta_i, \quad \sum_i p_i = 1.
\] 这里,$\alpha$ 和 $\beta_i$ 是两个基于先验经验确定的值,$f_j$ 是一个关于评价者的函数,$A_{ji}$是该图的邻接矩阵或『评价矩阵』。根据这些『评价』种类的不同,我们可以赋予不同的权重。一般的胜负定为1,令狐、任、向三人围攻定为3,佩服、欣赏亦定为1,左冷禅击败任我行以后受伤严重,不能再战斗,可为0.9。在最简单的PageRank里,$f_i = 1/\max(1, d^{\text{out}}_i)$,换句话说,一个人被打败的次数越多,他对别人的评价贡献越小。在改进模型中$f_i$也可以换成其他合适的函数。

我们将这个想法应用于上面提到的《笑傲江湖》的排行问题。令$\alpha=0.85$, $\beta = (1-\alpha)/N$, 这里N为顶点个数。得到的风评分使用『权重』和不使用『权重』两种情况为:

第一种情况得到排名为:东方不败、任我行、令狐冲、方证、风清扬、左冷禅、岳不群、冲虚、向问天。 讨论:左冷禅的功夫高于岳不群是因为左冷禅曾战胜高手任我行。任我行排名比令狐冲高是因为他跟多个高手过过招。

第二种情况得到的排名为:任我行、令狐冲、东方不败、方证、风清扬、冲虚、左冷禅、岳不群、向问天。讨论:任我行、令狐冲排名比东方不败靠前是因为他们参与的决斗比较多,而在这里东方不败的名声主要来源于她与三大高手的决斗。假如不将此赋予较高权重的话,东方不败无法鹤立鸡群。这也显示了权重的重要性。

当然所有的参数可以根据读者的经验调节,从而得到一个合适的排名。为了得到合适的排名,也需要深度挖掘其他次要人物的贡献。由于很多出场人物并没有比较得到过评价,这时候他们先验的江湖名声就变得重要起来。进一步地,如果能找到一些连结各个金庸武侠小说的人物(比如少林寺、丐帮、武当派等),这个办法也可以用来做金庸武侠世界的综合排名。

参考:
cf. Liyun: 十八般武艺,谁主天下。写成此文后,搜到这篇文章用PR来给金庸小说中的武器打分。