第二十四章 度量指标
在机器学习、数据挖掘、推荐算法等学术实验分析阶段，通常要经过一个模型性能评价的过
程。本章主要介绍在各个领域常用的评价或度量指标。
)!*+",$%"&'#(
24.1 度量空间与测度论
24.2 范数
24.2.1. H
¨
older范数
对于无约束范数逼近问题：
min ∥Ax − b∥
p
(24.1)
其中，A ∈ R
m×n
,b∈ R
m
，p>0。
如果p ≥ 2，则范数是ℓ
p
范数或称H
¨
older范数：
f(x) ! ∥Ax − b∥
p
=
%
"
i
|a
T
i
x − b
i
|
p
&
1
p
. (24.2)
我们定义
g(x) ! f(x)
p
= ∥Ax − b∥
p
p
=
"
i
|a
T
i
x − b
i
|
p
由于g(x)二阶处处可微，根据Newton法，可以得到下面的迭代序列：
x
k+1
= x
k
− α
k
(∇
2
g(x
k
))
−1
∇g(x
k
)
= x
k
−
α
k
p−1
(A
T
W
k
A)
−1
A
T
W
k
(Ax
k
− b)
=
p−1−α
k
p−1
x
k
+
α
k
p−1
(A
T
W
k
A)
−1
A
T
W
k
b
=
p−1−α
k
p−1
x
k
+
α
k
p−1
arg min
¯ω
∥W
1/2
k
(A¯ω −b) ∥
2
(24.3)
267
搜索与排名 Searching and Ranking
!"#
其中，x
0
=0，α
k
∈ [0, 1)是固定的，或者根据线性搜索技术迭代变化。W
k
是个对角矩阵：
W
k
!
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝
(a
T
1
x
k
− b
1
)
p−2
0 ··· 0
0 (a
T
2
x
k
− b
2
)
p−2
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
0 0 0(a
T
m
x
k
− b
m
)
p−2
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠
(24.4)
24.2.2. 曼哈顿范数
当p =1时，问题(24.1)转化为最小化ℓ
1
或曼哈顿范数（Manhattan Norm）：
f(x) ! ∥Ax − b∥
1
=
"
i
|a
T
i
x − b
i
|
我们可以藉由下面的线性规划问题进行求解：
min
(
i
ν
i
s.t. |a
T
i
x − b
i
| ≤ ν
i
,i=1,...,m
在机器学习任务中，常涉及到稀疏模型的训练问题，通过优化ℓ
1
正则项的非平滑损失函数学习
模型，比如回归分析中的Lasso算法。
24.2.3. 欧式范数
当p =2时，问题(24.1)就是ℓ
2
或者欧式范数（Euclidean Norm）的最小化：
f(x) ! ∥Ax − b∥
2
=
Q
"
i
(a
T
i
x − b
i
)
2
是典型的最小二乘问题，存在下面等价的二次规划形式：
min f(x)
2
= ∥Ax − b∥
2
2
=
"
i
(a
T
i
x − b
i
)
2
存在解析解（Analytic Solution, Closed Form Solution）
ˆx =(A
T
A)
−1
A
T
b
24.2.4. 切比雪夫范数
当p = ∞时，问题(24.1)转化为最小化ℓ
∞
或者切比雪夫范数（Chebyshev Norm，也称“棋盘
距离”）：
f(x) ! ∥Ax − b∥
∞
= max
i
|a
T
i
x − b
i
|
由于不存在解析解，我们可以将其转化为下面的线性规划问题：
min ν
s.t. |a
T
i
x − b
i
| ≤ ν,i=1,...,m
$%"&'#(
268
)!*+",$
24.3. 距离和相似性度量
!"#
24.2.5. L最大范数
向量ω ∈ R
m
的L最大范数（Largest-L Norm）∥ω∥
[L]
是将ω按照其坐标绝对值降序排列，前L个
最大坐标绝对值之和，即有定义
∥ω∥
[L]
=
L
"
i=1
|ω|
[i]
, 1 ≤ L ≤ m, (24.5)
其中，|ω|
[i]
表示坐标绝对值降序排列第i位的数值，满足|ω|
[1]
≥ |ω|
[2]
≥ ... ≥ |ω|
[m]
。当L =1时，
L最大范数等价于ℓ
∞
范数；当L = m时，等价于ℓ
1
范数；当1 <L<m时，它是一个凸函数，最小
化L最大范数等价于解线性规划问题
min
(
i
c
i
+ Lq
s.t. |a
T
i
x − b
i
| ≤ c
i
+ q,
c
i
≥ 0, 1 ≤ i ≤ m.
(24.6)
多数人在面对最小化L最大范数问题时，会选择复杂的障碍函数法（Barrier Method）或次梯度法
（Subgradient Method），纵然是优化问题专业人员亦鲜有人知可使用模型(24.6)简化问题。
24.3 距离和相似性度量
距离度量衡量对象间的差异程度，距离越远则对象间的差异越大。相似度度量衡量对象间的相
似程度，与距离度量相反，相似度度量值越小，则说明对象间相似度越小，差异越大。其他相似性
度量、距离度量可以参考[270, 271]。
24.3.1. 闵可夫斯基距离
闵可夫斯基距离（Minkowski Distance）是对多个距离度量公式的概括性的表述，公式如下：
d(x, y)=
%
"
i
(x
i
− y
i
)
p
&
1
p
(24.7)
1. 当p =1时，闵可夫斯基距离退化成曼哈顿距离（Manhattan Distance）：
d(x, y )=
"
i
|x
i
− y
i
| (24.8)
它来源于城市区块距离，对多个维度上的距离求和。假设在曼哈顿街区乘坐出租车从一个地
方到另一个地方，白色区域表示高楼大厦，灰色表示街道，三条折线都表示两地间的曼哈顿
距离，三者长度相等。
2. 当p =2时，闵可夫斯基距离退化成欧几里得距离（Euclidean Distance）：
d(x, y)=
Q
"
i
(x
i
− y
i
)
2
(24.9)
$%"&'#(
269
)!*+",$
搜索与排名 Searching and Ranking
!"#
图 24.1: 曼哈顿街区与曼哈顿距离
它是最常见的距离度量，衡量的是多维空间中点与点之间的绝对距离。如图 24.1所示，中间
绿色斜线表示两地之间的欧几里得距离。
3. 当p →∞时，闵可夫斯基距离退化为切比雪夫距离（Chebyshev Distance）：
d(x, y )= lim
p→∞
%
"
i
(x
i
− y
i
)
p
&
1/p
= max
i
|x
i
− y
i
| (24.10)
它起源于国际象棋规则下国王的走法。
图 24.2: 参数p与单位闵科夫斯基距离之间的关系图
24.3.2. Cayley距离
Cayley距离是度量有序变量无序性的指标。假设标准队列为a，b中至少有一个位置与a不同，
通过交换b中的元素的位置可以将其变成标准队列（简称标准交换），Cayley距离对应最小的标准交
换次数。如图24.3，第一个队列是标准队列，我们可以最少交换三次第二个队列的位置对就可以变
成标准队列，因此二者的Cayley距离为3。
24.3.3. Ulam距离
Ulam距离与Cayley距离类似，针对队列b，它可以使用删除-移动-插入的连环动作变成标准队
列（简称标准变换）。Ulam距离对应最小的标准变换次数。如图24.4，第一个队列是标准队列，我
们可以最少交换三次第二个队列的位置对就可以变成标准队列，因此二者的Ulam距离为2。
$%"&'#(
270
)!*+",$
24.3. 距离和相似性度量
!"#
图 24.3: Cayley距离距离演示 图 24.4: Ulam距离计算演示
24.3.4. 汉明距离
1950年，Richard Hamming[272]引入了汉明距离（Hamming distance），亦称“信号距离”，
用于度量两个等长字串相应位置字符不同的位置数目。汉明距离还可以表示将一个字串变成另外
一个字串需要替换的最小数目。对于两个二元字串a, b，它们的汉明距离即a XOR b中1的数目。
24.3.5. 余弦相似度
向量空间两个向量夹角余弦值常用于衡量对象间的差异，具体定义如下：
cos⟨x, y ⟩ =
x
T
y
∥x∥∥y∥
, (24.11)
余弦值越大，则两对象之间的差异越小；反之，则越大。余弦值可以直接用于度量对象之间的相似
程度，此时称作余弦相似度（cosine similarity）。
24.3.6. 杰卡德系数
对于两个集合A和B，如果我们只关心两者具有相同特征的比例，则可以使用如下形式的杰卡
德系数（Jaccard coefficient）
J(A, B)=
|A ∩ B|
|A ∪ B|
(24.12)
度量对象间的相似程度。系数值越大，表明两个对象的相似性越强，反之则越弱。
$%"&'#(
271
)!*+",$
搜索与排名 Searching and Ranking
!"#
24.3.7. 核相似度
在实际应用中，我们可以直接将定义在向量空间上的核函数作为相似性度量，从而可以得到核
相似性度量（kernel similarity）。比如高斯核函数定义的高斯相似性度量：
K(x, y)=exp{−
∥x − y∥
2
2σ
2
}. (24.13)
24.3.8. 皮尔逊相关系数
皮尔逊相关系数（Pearson correlation coefficient）述了两个变量间的线性相关性。对于变
量x和y，假设均值分别是µ
x
,µ
y
，标准差分别是σ
x
, σ
y
，则总体相关系数定义如下：
ρ(x, y)=
cov(x, y)
σ
x
σ
y
=
E
#
(x − µ
x
)(y − µ
y
)
$
σ
x
σ
y
. (24.14)
基于n组样本对协方差和标准差的估计，我们可以使用下式计算样本相关系数：
ρ(x, y)=
(
i
(x
i
− ¯x)(y
i
− ¯y)
R
(
i
(x
i
− ¯x)
2
(
i
(y
i
− ¯y)
2
=
n
(
i
(x
i
y
i
) −
(
i
x
i
(
i
y
i
'
n
(
i
x
2
i
− (
(
i
x
i
)
2
'
n
(
i
y
2
i
− (
(
i
y
i
)
2
. (24.15)
根据定义，皮尔逊相关系数−1 ≤ ρ(x, y ) ≤ 1，通过|ρ(x, y)|的大小可以判定相关程度，|ρ(x, y)|越
大，x和y的相关程度越大。当ρ(x, y)=1时，表示x和y完全正相关；当ρ(x, y)=−1表示完全负相
关；当ρ(x, y)=0表示不相关。如果我们令u
i
= x
i
− ¯x，v
i
= y
i
− ¯y，i =1, 2,...,n，则皮尔逊相关
系数实际上与夹角余弦相似度等价：
ρ(u, v)=
(
i
(x
i
− ¯x)(y
i
− ¯y)
R
(
i
(x
i
− ¯x)
2
(
i
(y
i
− ¯y)
2
= cos⟨u, v⟩ . (24.16)
24.3.9. 等级相关系数
检索系统在执行检索时，对于同一个检索语句，不同搜索引擎由于内部排名算法的差异，可
能检索到不完全相同的数据、产生截然不同的网页排名列表。等级相关系数（rank correlation
coefficient）是度量排名列表间相似性和相关性一类重要的统计量，常见的等级相关系数有：斯
皮尔曼等级相关系数Footrule和Rho、肯德尔等级相关系数Tau、 Goodman–Kruskal等级相关系
数Gamma。研究人员已经将其应用到排名聚合、搜索效果评估问题，具有重要的实际意义。
假设π和σ是个可排列对象单元集上的两个排名列表，可能表示评价主体根据对象单元的两
个基本属性进行有序排列。比如例子9.1中可排列对象单元对应五位民主党总统候选人
,
Clinton，
Warren，Cuomo，O’Malley，Biden
-
，各自包含四个属性：公众熟识比例（Familiar）、公众认同
的比例、公众排斥的比例和公众净认同比例。我们按照第一个属性对五人进行有序排列会产生一个
排名列表（比如π），按照第四个属性排列他们又可以得到一个排名列表（比如σ）。 为 了 度 量 排 名
$%"&'#(
272
)!*+",$
24.3. 距离和相似性度量
!"#
列表π 和σ之间的相似性，我们定义如下一般形式的等级相关系数：
γ(π, σ)=
(
i,j
g(π
i
, π
j
)h(σ
i
, σ
j
)
'
(
i,j
g(π
i
, π
j
)
2
(
i,j
h(σ
i
, σ
j
)
2
, (24.17)
其中函数g(·)和h(·)各自依据排名列表π和σ 评价所有可能的对象单元序对。比如，g(π
i
, π
j
)根
据排名列表π评价对象单元序对(i, j)，h(σ
i
, σ
j
)则根据排名列表σ评价对象单元序对(i, j)。当函
数g(·)和h(·)的形式如下：
g(π
i
, π
j
)=π
i
− π
j
,h(σ
i
, σ
j
)=σ
i
− σ
j
,
对应的等级相关系数就是等级相关系数Rho。如果函数g(·)和h(·)的形式如下：
g(π
i
, π
j
) = sgn(π
i
− π
j
),h(σ
i
, σ
j
) = sgn(σ
i
− σ
j
),
对应的等级相关系数就是等级相关系数Tau。函数g(·) 和h(·)对对象单元序对使用不同的评价标准，
就会产生一种对应的等级相关性度量。此外，当我们把所有可能的对象单元序对逐一展开，函
数g(·)和h(·)对它们的评价就形成两个高维的评价向量V
g
∈ R
n
2
和V
h
∈ R
n
2
：
V
g
=(g
11
,g
12
,g
21
,g
13
,g
31
,...,g
nn
)
T
,g
ij
! g(π
i
, π
j
), (24.18)
V
h
=(h
11
,h
12
,h
21
,h
13
,h
31
,...,h
nn
)
T
,h
ij
! h(σ
i
, σ
j
). (24.19)
利用它们改写一般形式的等级相关系数(24.17)：
γ(π, σ)=
V
T
g
V
h
∥V
g
∥∥V
h
∥
= cos⟨V
g
,V
h
⟩∈[−1, 1], (24.20)
本质上等于两个评价向量V
g
和V
h
的夹角余弦相似度。
I. Spearman’s Footrule与Rho
1904年，实验心理学先驱、英国退伍军官查尔斯·斯皮尔曼Charles Spearman [273]延伸相
关系数的概念，推导出等级相关的计算方法，出Footrule度量，基于此开创出因子分析（factor
analysis）方法 [274]，成为其学术生涯最伟大的成就。
假设对象集合存在两个排名列表π和σ，斯皮尔曼将Footrule定义为两列表差值的ℓ
1
范数：
F(π, σ)=
"
i
|π
i
− σ
i
|. (24.21)
斯皮尔曼等级相关系数Rho统计量则建立在所有对象单元序对之上，具体形式如下：
ρ(π, σ)=
(
i,j
(π
i
− π
j
)(σ
i
− σ
j
)
(
i,j
(π
i
− π
j
)
2
, (24.22)
$%"&'#(
273
)!*+",$
搜索与排名 Searching and Ranking
!"#
其中π
i
，σ
i
分别表示排名对象集合第i个对象在排名列表π与σ上的名次。对于一个长度等于n的排名
列表，存在n(n − 1)个排名指标序对，并且满足
"
i,j
(π
i
− π
j
)
2
=
"
i,j
(σ
i
− σ
j
)
2
.
我们可以根据如下两个事实
"
i
π
i
= 1+2+···+ n = n(n + 1)/2 =
"
i
σ
i
, (24.23)
"
i
π
2
i
=1
2
+2
2
+ ···+ n
2
= n(n + 1)(2n + 1)/6=
"
i
σ
2
i
, (24.24)
简化Rho统计量得：
ρ(π, σ)=1−
6
n
3
− n
"
i
(π
i
− σ
i
)
2
. (24.25)
II. Kendall’s Tau
1938年，莫里斯·肯德尔Maurice Kendall[275]根据两个排名列表中排名对象的排名顺序是否
一致，定义Tau统计量。一般地，Tau值越大，说明列表的差异越大。由于使用冒泡排序方法，将
一个列表按照另一个列表的顺序排列需要移动的次数，恰好等于Tau值，Tau统计量由此又称作
“冒泡排序距离”。
肯德尔定义的等级相关系数Tau是建立在一系列有序对的二元判断之上，表示如下：
τ(π, σ)=
(
i,j
sgn(π
i
− π
j
) sgn(σ
i
− σ
j
)
'
(
i,j
[sgn(π
i
− π
j
)]
2
(
i,j
[sgn(σ
i
− σ
j
)]
2
. (24.26)
它是一个对称的统计量。当i = j时，和因子sgn(π
i
− π
j
) sgn(σ
i
− σ
j
)=0。在不考虑具体和因子的
情况下，我们利用排名序对集P化简Tau统计量的双重加和项
"
i,j
(·)=
n
"
i=1
n
"
j=1
(·)=2
n−1
"
i=1
n
"
j=i+1
(·)=2
"
(i,j)∈P
(·),
其中P =
,
(i, j)|1 ≤ i<j≤ n
-
是由所有可能的序对构成的序对集，容量|P | = n(n-1)/2。我们可
以利用它简化Tau统计量的分子部分：
"
i,j
sgn(π
i
− π
j
) sgn( σ
i
− σ
j
)=2
"
(i,j)∈P
sgn
#
(π
i
− π
j
)(σ
i
− σ
j
)
$
! 2(|P
c
π,σ
| − |P
n
π ,σ
|),
其中P
n
π,σ
与P
c
π,σ
称作排列π和σ上的（异）同序对集（(non-)concordant pairs ）
P
c
π,σ
=
,
(i, j) ∈ P | sgn[(π
i
− π
j
)(σ
i
− σ
j
)] = 1
-
⊂ P, (24.27)
P
n
π,σ
=
,
(i, j) ∈ P | sgn[(π
i
− π
j
)(σ
i
− σ
j
)] = −1
-
⊂ P. (24.28)
$%"&'#(
274
)!*+",$
24.3. 距离和相似性度量
!"#
它们是P上两个不相交的子集，其他部分称作π和σ上的平局序对集（tied pairs）：
P
t
π ,σ
=
,
(i, j) ∈ P | sgn[(π
i
− π
j
)(σ
i
− σ
j
)] = 0
-
⊂ P, (24.29)
并且满足|P
c
π,σ
| + |P
n
π,σ
| + |P
t
π,σ
| = |P|。此外，sgn[(π
i
− π
j
)(σ
i
− σ
j
)] = 0对应三种可能局面：
|σ
i
− σ
j
| > 0, π
i
= π
j
, (24.30)
|π
i
− π
j
| > 0, σ
i
= σ
j
, (24.31)
π
i
= π
j
, σ
i
= σ
j
, (24.32)
统计量的分母部分成分远比比分子部分复杂。为了方便细化分析，我们根据平局产生的排名列表
将P
t
π,σ
分割成两个子集：
P
t
π
=
,
(i, j) ∈ P | π
i
= π
j
-
⊂ P
t
π ,σ
, (24.33)
P
t
σ
=
,
(i, j) ∈ P | σ
i
= σ
j
-
⊂ P
t
π ,σ
. (24.34)
其中P
t
π
和P
t
σ
分别是排名列表π和σ上的平局序对集。
（甲）如果三种局面都没有出现，则集合P
t
π
和P
t
σ
都是空集，此时
"
i,j
[sgn(π
i
− π
j
)]
2
=
"
i,j
[sgn(σ
i
− σ
j
)]
2
= n(n − 1)
那么Tau统计量就可以化简如下：
τ(π, σ)=
2(|P
c
π,σ
| − |P
n
π ,σ
|)
n(n − 1)
=
|P
c
π,σ
|
|P|
−
|P
n
π ,σ
|
|P|
, (24.35)
等于同序对比例和异序对比例的差值，前一项表示两排名列表π和σ之间的相似度，后一项则表示
两者的距离或相异程度，两项差值则衡量两排名列表间的相关程度（或净相似度），Tau值越高相
关度就越高。
（乙）如果(24.30)(24.31)(24.32)三种局面至少出现一种，都需要对分母部分做相应调整：
"
i,j
[sgn(π
i
− π
j
)]
2
=2
"
(i,j)∈P
[sgn(π
i
− π
j
)]
2
=2
*
|P| − |P
t
π
|
+
, (24.36)
"
i,j
[sgn(σ
i
− σ
j
)]
2
=2
"
(i,j)∈P
[sgn(σ
i
− σ
j
)]
2
=2
*
|P| − |P
t
σ
|
+
. (24.37)
Tau统计量可作如下简化：
τ(π, σ)=
|P
c
π ,σ
| − |P
n
π,σ
|
R
*
|P| − |P
t
π
|
+*
|P| − |P
t
σ
|
+
. (24.38)
当π与σ上都没有平局序对时，(24.38)和(24.35)完全等价。如果π = σ，则| P
c
π,σ
| = |P|，Tau统计
量值最大τ(π, σ)=1。如果π和σ彼此完全向逆，则|P
n
π,σ
| = |P|，Tau统计量值最小τ(π, σ)=−1。
其他情况下，−1 < τ(π, σ) < 1。
$%"&'#(
275
)!*+",$
搜索与排名 Searching and Ranking
!"#
对于排名聚合问题，人们比较关心位于前列的对象的质量，然而Footrule和Tau均没有考虑位
置信息对排名效果的影响。为此，有研究人员[276, 277]出两种统计量位置加权形式的扩展模型，
使其满足如下两个基本特点：
1. 假设在理想列表中，A、Z两个排名对象分别排在前列和后列，那么排名算法改变A的次序比
改变Z的次序对整体排名质量的影响更大。
2. 当排名算法的排名结果与理想排名结果完全一致时，二者距离最小；若排名结果完全相悖，
则距离最大。
24.3.10. 对数似然比
对数似然比（log-likelihood ratio，LLR） [278, 279]是子参数空间与全参数空间的最大似然估
计之比 [278]，可用于度量对象之间的相似关系，比如统计用户U和V 的在线购物历史记录，可构
造如24.1所示的表格。表格中n
11
表示两个用户都喜欢的商品数目，n
22
表示两个都不喜欢的商品数
目，n
12
表示用户U喜欢而用户V 不喜欢的数目，n
21
则完全相反。
V + V −
U+ n
11
n
12
U− n
21
n
22
表 24.1: 用户购物的偏好统计矩阵
对数似然比的计算需要一种信息熵，它定义如下：
λ =2× (H
m
− H
r
− H
c
) (24.39)
其中，H
m
= H(n
11
,n
12
,n
21
,n
22
)称作矩阵熵，H
r
= H(n
11
,n
12
)+H(n
21
,n
22
)为行熵，H
c
=
H(n
11
,n
21
)+H(n
12
,n
22
)为列熵。这里信息熵定义如下：
H(X)=−
"
i
x
i
log
x
i
+ z
i
(
i
x
i
(24.40)
其中，Z =(z
1
,z
2
,...,z
n
)是统计变量X对应元素的反示性函数，如果x
i
=0，则z
i
=1，否
则z
i
=0。
24.4 局部敏感哈希
局部敏感哈希（Locality-Sensitive Hashing，LSH）是应用于海量高维数据上的一类近似最近
邻（Approximate Nearest Neighbor）快速查找方法，广泛应用于网页查重、图像检索、音频检
索、数据降维、聚类分析、推荐算法等场景。
$%"&'#(
276
)!*+",$
24.5. 推荐系统评价指标
!"#
24.4.1. SimHash
24.4.2. MinHash
24.5 推荐系统评价指标
衡量推荐系统的评价指标包括：均方根误差（Root Mean Squared Error，RMSE）、 平 均
绝对误差（Mean Absolute Error，MAE）[280]、精度（Precision）、 召 回 率 （ Recall）和DCG
（Discount Cumulative Gain）。 在 真 实 的 推 荐 场 景 中 ， 我 们 还 希 望 推 荐 的 内 容 具 有 新 颖 性
（Novelty）和多样性（Diversity）。
推荐精度是评价推荐算法最基本的指标，它衡量的是推荐算法在多大程度上能够准确预测用户
对推荐商品的喜欢程度。目前大部分的关于推荐系统评价指标的研究都是针对推荐精度的。精度指
标有很多，有些衡量用户对商品的预测评分与真实评分的接近程度，有些只考虑推荐排名[281]。
24.5.1. 均方根误差
目前评价推荐精度的度量指标中，均方根误差（Root Mean Squared Error，RMSE）是使用
最多的一种，也在多次推荐算法比赛中使用作为标准的度量指标。它的数学定义为：
RMSE =
Q
1
N
"
k
(p
k
− q
k
)
2
, (24.41)
其中，N是测试数据集的大小，P =(p
1
,...,p
N
)
T
是待评分项真实评分值，Q =(q
1
,...,q
N
)
T
是模
型预测分值。均方根误差越小，则说明模型预测评分与真实评分越一致，预测精度越高。
24.5.2. 平均绝对误差
平均绝对误差（Mean Absolute Error，MAE）是推荐系统中最容易解释的一种度量指标，其
数学定义如下：
MAE =
1
N
"
k
|p
k
− q
k
|. (24.42)
24.5.3. 多样性
在推荐系统中，多样性体现在两个层次，用户间的多样性（Inter-user Diversity）和用户内
的多样性（Intra-user Diversity）。 前 者 反 映 推 荐 系 统 对 不 同 用 户 推 荐 不 同 商 品 的 能 力 ， 后 者 则
反映推荐系统对一个用户推荐商品多种商品的能力。对于用户u和v，我们可以使用汉明距离
（Hamming Distance）度量两个用户推荐列表I
u
与I
v
的差异程度，具体定义为：
d
uv
=1−
1
L
|I
u
∩ I
v
|, (24.43)
$%"&'#(
277
)!*+",$
搜索与排名 Searching and Ranking
!"#
其中L表示推荐列表的长度，也就是推荐的商品数目。系统中所有的用户对汉明距离的平均值反映
了推荐系统的多样性水平，汉明距离越大，则多样性越强。用户u的商品推荐多样性依赖于推荐列
表中商品相似性状况，定义如下：
d
u
=
1
|I
u
|(|I
u
| − 1)
"
i̸=j
i,j∈I
u
s
ij
, (24.44)
系统中所有用户的用户内多样性均值反映了系统的多样性。
24.5.4. A/B测试
推荐系统的评价可分为在线评价和离线评价两种方式。在线评价其实就是设计在线用户实验，
根据用户在线实时反馈或事后问卷调查等结果来衡量推荐系统的表现。
目前最常用的在线测试方法A/B测试。所谓A/B测试，简单而言就是为一个目标制定两套方
案，相应地将用户也分割成两部分，一部分使用方案A，一部分使用方案B，并记录下用户的使用
状况，选择出更符号设计目的的方案正式上线。A/B测试的基本准则是多方案并行测试、每个方
案只有一个变量不同（单变量）、以种规则优胜劣汰。A/B测试并非只同时测试两个方案，它可
能会设计和测试多个方案，以确定各个方案的优劣[281]。
24.6 排名性能评价指标
在信息检索领域，用于衡量排名性能的指标有多种，比如NDCG[282, 283]，MAP[284]，
MRR[285]等。本节简要介绍常见的几种性能度量指标。
24.6.1. 查准率
在信息检索领域，精度（Precision，又称“查准率”）和召回率（Recall，又称“查全率”）是
两个最常使用的，用以衡量检索性能的指标。精度是指检索到的文档中相关文档比率：
P =
|A ∩ B|
|B|
(24.45)
其中，A表示系统中相关文档集合，B表示检索到的文档集合。
在排名问题中，精度主要用于度量两个级别的排名性能。在训练数据集中，每个排名文档包
含一个相关等级，如果是相关的则记为1，否则记为0，那么排名列表π 的第k个位置上的精度记
为P@k，定义如下：
P@k =
1
k
k
"
i=1
I(y
π
−1
(i)
= 1) (24.46)
其中，I(·)为示性函数。
$%"&'#(
278
)!*+",$
24.6. 排名性能评价指标
!"#
24.6.2. 召回率
召回率是指检索系统中返回的相关文档占所有相关文档的比例，可以表示成如下形式：
R =
|A ∩ B|
|A|
(24.47)
实际上，“在海量的实时动态网络系统中，根本不可能估计系统中同检索词相关的文档数目”
[286]，那么召回率就无法计算。[286, 287]在研究搜索引擎的性能时均以此为由，将召回率从度量
指标中剔除。将召回率直接剔除并不恰当，TREC Web Track使用样本池方法（Pooling Method）
从系统中寻找相关文档，并假设没有落在池子中的样本是不相关的[288]。
对于二元分类问题，我们可以将真实的类别标记与模型预测结果的所有可能组合绘制到
图24.5。图24.5构成一个分类器可信度的混淆矩阵（Confusion Matrix）， 以 医 学 诊 断
➊
为例，其中
图 24.5: 真实标记与预测结果
的阳性（Positive）是“有病”，阴性（Negative）是“无病”，则False Positve是“假阳性”，将实
际“无病（Negative）”的人诊断为“有病（True）”，也称“误诊率”，属于“第I类错误”。False
Negative是“假阴性”，将实际“有病（Positive）”的人诊断为“无病（False）”，也称“漏诊率”，
属于“第II类错误”。统计学家认为犯第I类错误的代价高于犯第II类错误，实际上在不同的治疗阶
段，两类错误的代价是不同的。
根据Precision与Recall的定义，结合图24.5，我们有：
P =
TP
TP + FP
R =
TP
TP + FN
(24.48)
另外，根据预测与真实分类之间的一致性，还可以定义准确率（Accurate）、 真 阳 性 比 率
（True Positive Rate，TPR）、假阳性比率（False Positive Rate，FPR）：
Accurate =
TP + TN
TP + FP + TN + FN
TPR =
TP
TP + FN
FPR =
FP
FP + TN
=1−
TN
FP + TN
(24.49)
➊ 一般来说，阳性表示疾病或体内生理的变化有一定的结果，阴性则基本上否定或排除种病变的可能性
$%"&'#(
279
)!*+",$
搜索与排名 Searching and Ranking
!"#
在20世纪50年代，英国Cranfield大学首先出一套信息检索评价系统（简称Cranfield评价体
系），由查询样本集、正确结果集和评价指标构成，并由此确立了“评价”在信息检索研究中的重
要地位。Cranfield评价体系使用的两个评价指标是查准率和查全率，反映了标准检索系统的具备
的两个基本能力：过滤不相关文档的能力，检索到所有相关文档的能力。查准率与查全率实际上是
相互制约的，一般而言，查准率越高，则查全率下降，反之亦反。以查全率作为横轴，以查准率作
为纵轴，二者的互斥关系可以使用Precison-Recall曲线（简称PR-Curve）[289]述，见图24.6。
图 24.6: PR曲线 图 24.7: ROC曲线
为了融合查准率与查全率两种指标，学术界出了如下定义的F度量（F-Measure）：
F =
1
λ
1
P
+(1−λ)
1
R
(24.50)
其中，P表示查准率，R表示查全率，λ ∈ (0, 1)平衡两个指标的作用，通常取λ =0.5，则有：
F =
2PR
P+R
(24.51)
此时，又称F度量为F
1
度量。
ROC曲线（受试者工作特征――Receiver Operator Characteristic）源于信号检测理论，并广
泛应用于机器学习和数据挖掘领域，是模型选择与评估的一个重要工具。在二元分类问题中，研究
人员使用ROC曲线形象地刻画分类模型的假阳性率（横轴）与真阳性率（纵轴）之间的关系。对
于完全随机分类模型，其ROC 曲线是连接原点与(1, 1) 的45°角平分线，任何优于随机分类的模
型，其ROC曲线都位于45°平分线上方（见图24.7）
➊
。ROC曲线下方面积AUC[290]可用来衡量模
型预测的准确性，指标范围在[0, 1]之间，有趣的是AUC同Wilcoxon-Mann-Whitney统计量是等价
的 [291]，可用于衡量分类模型的排名性能。
➊ 在讨论ROC与PR曲线时，可能涉及到凸壳（Convex Hull）， 也 称 凸 包 （ Convex Envelop）的概念，简单而言，在实数向量空间V 中，
$%"&'#(
280
)!*+",$
24.6. 排名性能评价指标
!"#
24.6.3. 平均精度均值
根据精度的定义，可以定义平均精度（Average Precision）：
AP =
1
n
1
n
"
k=1
I(y
π
−1
(k)
= 1)P@k (24.52)
其中，n是与检索词关联的文档数目，n
1
表示相关文档的数目，在PR曲线中，平均精度近似地等于
曲线下方面积所占比例。
平均精度均值（Mean Average Precision，MAP）是指所有检索词上的AP的平均值，即
MAP =
1
|Q|
"
q ∈ Q
AP(q) (24.53)
24.6.4. 折损累积增益
折损累积增益（Discounted Cumulative Gain，DCG）是评价排名质量的一种标准指标，常
用于度量搜索排名算法的精度，在信息检索领域有广泛使用。它不局限于评价仅含有相关、不相关
两种评分相关等级的排名问题，对于包含多个评分相关等级的排名问题同样适用。给定一个排名列
表，折损累积增益根据文档在排名列表中的位置信息计算其有用性或称增益量，从排名列表的顶部
到底部累积各个位置的增益量，并以各自的位置信息进行折损。一般地，如果相关性越高则越有
用，相应地在排名列表中的位置越靠前，则折损累积增益的值就越高。在评价排序模型的质量时，
如果折损累积增益的值越大，则认为排序模型性能越高。
在折损累积增益诞生之前，常使用一种称为累积增益的指标，它只是将对应位置以后所有对象
的评分相关等级机械相加，没有将位置信息计入增益量。对于给定的排名列表π，在位置k处的累
积增益定义如下：
CG@k =
k
"
i=1
y
π
−1
(i)
(24.54)
其中，π
−1
(i)表示在排名列表中排在位置i的对象，其相关等级用y
π
−1
(i)
表示。在累积增益的计算过
程中，如果调换排名在[1,k]范围内任意两个对象的位置，无论是将相关的对象位置往后挪，还是
将不相关对象的位置向前移，都不会影响累积增益量。折损累积增益克服了累计增益的这一缺陷，
对于不同位置的增益设置不同的折损：位置靠前的对象折损越小，有用性更高。对于位置k处的折
损累积增益定义如下：
DCG@k = y
π
−1
(1)
+
k
"
i=2
y
π
−1
(i)
log i
(24.55)
对于给定集合X的凸包S 是指V 中所有包含X的凸集K的交：
S =
!
X⊆K⊆V
K,
如果X是有限的，则X的凸包可以由X内所有点(x
1
,...,x
n
) 线性组合来构造：
S = {
n
"
i=1
α
i
x
i
| x
i
∈ X,
n
"
i=1
α
i
=1, α
i
∈ [0, 1]}
$%"&'#(
281
)!*+",$
搜索与排名 Searching and Ranking
!"#
或者
DCG@k =
k
"
i=1
2
y
π
−1
(i)
− 1
log(i + 1)
(24.56)
其中，公式加和项分数的分子部分表示增益，分母部分表示折损。通过选择不同截断位置
（Cut-off），折损累积增益可以评价不同位置上的排名质量。
在网络搜索应用中，由于不同搜索引擎所使用的排名算法不同，对于同一个检索词，每个系统
返回的搜索结果数量也不相同。为方便比较不同搜索引擎、不同排名算法，需要对折损累积增益在
检索词上做标准化处理。假设对于每一个检索词，都存在一个真实的排名列表，如果个排序模型
的预测排名与真实排名完全一致，我们称之为理想排名模型，相应排名结果称为理想排名，而根据
理想排名列表计算的折损累积增益也称理想累积增益。理想累积增益在位置k截断值记作Z
k
，利用
它标准化折损累积增益就得到标准累积增益：
NDCG@k =
DCG@k
Z
k
(24.57)
取值范围在[0, 1]，它是评价排序模型或算法质量最常用的一种标准指标。
24.6.5. 倒数排名均值
倒数排名均值（Mean Reciprocal Rank，MRR）是一种衡量两个级别的排名质量的度量方式，
是倒数排名（Reciprocal Rank, RR）在检索词集合Q上的平均值。倒数排名是指对于个检索词，
相关文档最好的排名，即RR = r
−1
，r表示与检索词相关的文档最好的排名。比如，个检索词的
相关文档只有2个，其中一个排在第2位，另一个排在第10 位，那么其倒数排名为2
−1
。对所有检索
词的倒数排名取均值，就是平均倒数排名：
MRR =
1
|Q|
"
q ∈ Q
1
r
q
(24.58)
24.6.6. 倒数排名期望
倒数排名期望（Expected Reciprocal Rank，ERR）由Chapelle等人[292]出，通过用户对搜
索结果满意程度的统计模型分析，ERR表现优于DCG度量。
假设位置j的文档让用户满意的概率为R
j
，则用户在位置r找到心仪的文档并停止浏览和查找
的概率为：
r−1
!
j=1
(1 − R
j
)R
r
一般地，R
j
可以使用对应位置文档的等级表示：
R
j
=
2
y
j
− 1
2
y
max
$%"&'#(
282
)!*+",$
24.7. 信息度量
!"#
ERR可以定义为下式：
ERR =
n
"
r=1
1
r
r−1
!
j=1
(1 − R
j
)R
r
(24.59)
其中n表示待排名的文档数目；y
i
表示排在i的文档等级；y
max
表示文档的最高等级。
24.6.7. pFound
pFound由Gulin等人[293]出，Yandex从2007年就开始用它来评估搜索效果。与ERR类似，
pFound也是一种衡量用户满意程度的概率模型。
pFound =
n
"
r=1
r−1
!
j=1
(1 − b)(1 − R
j
)R
r
=
n
"
r=1
(1 − b)
r−1
r−1
!
j=1
(1 − R
j
)R
r
(24.60)
R
j
与ERR中的含义相同，表示用户在j处找到满意文档的概率；b表示在各个位置停止查找的概率，
默认取值0.15。
ERR和pFound都基于相同的假设：（i）用户从上到下逐个浏览搜索结果页面；（ii）用户逐个
点击搜索结果，直到找到目标文档或者没有找到而放弃搜索。
24.6.8. 胜者全拿
胜者全拿（Winner Takes All，WTA）是一种两级别度量，对于个检索词，如果排名最前的
文档与之相关，则WTA损失为0，否则为1。
24.7 信息度量
信息论是运用概率论与数理统计的方法研究信息、信息熵、通信系统、数据传输、密码学、数
据压缩等问题的应用数学学科。Shannon和Weaver于1948年10月发表在《贝尔系统技术学报》的
论文通信的数学原理[294]，可以视作是现代信息论研究的开端。Claude Shannon由于在信息理论
中的突出贡献被后人尊称为“信息论之父”。
信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。信息传输和
信息压缩是信息论研究中的两大领域，二者又通过信道编码定理、信源－信道隔离定理相互联系。
信源编码和信道编码是信息论的基本研究课题。
24.7.1. 熵
19世纪60年代，德国物理学家Rudolf Clausius在研究实际热机中发现，实际热机工作时会产
生“无法使用”的热量（如摩擦产生的热量），并首次出“熵（Entropy）” 的 概 念 ， 用 来 述 能
量的耗散。19世纪70 年代，Ludwig Boltzmann在分析系统中微观粒子的统计行为时给出熵的统计
学定义，并证明这种统计学意义上的熵与Cluasius给出的热力学熵是等价的，仅仅相差一个常数项
$%"&'#(
283
)!*+",$
搜索与排名 Searching and Ranking
!"#
图 24.8: Left：Rudolf Clausius (1822 - 1888), Middle：Ludwig Boltzmann (1844 - 1906), Right：
Claude Shannon (1916 - 2001)
（Boltzmann常数）。根据熵的统计学定义，热力学第二定律说明一个孤立系统倾向于混乱程度增加
（即“熵增”）。
受此启发，Shannon和Weaver在[294] 中出信息熵（Information Entropy，简称“熵”）的
概念，并证明熵与信息的不确定性存在等价关系，信息熵越大，意味着不确定性越大，从而事件所
包含的信息量越大。
离散随机变量X = {x
1
,...,x
n
}的熵用于度量隐含于变量X的值的不确定性程度，如果
令p(x)表示X = x的概率，那么变量X的熵定义为：
H(X)=E
X
[I(x)] = −
"
x∈X
p(x) log p(x) (24.61)
其中，I(x)表示单个信息的熵分布，有时称作自信息（Self Information）， E
X
表示期望。计算中使
用的对数基底如果是2，熵的单位就是比特（bit）， 在 用 符 号 表 达 信 息 时 ， 熵 用 来 量 化 单 个 字 符 可
以存储或传输的平均比特数。
如果随机变量X是连续的，则熵可以使用积分计算
H(X)=−
>
x
p(x) log p (x )dx. (24.62)
根据连续随机变量X熵的定义，我们可以计算常见连续分布的熵，比如X ∼ N (µ, σ
2
)，则其连续熵
H(X)=−
S
+∞
−∞
1
√
2πσ
exp{−
(x−µ)
2
2σ
2
}
#
−
(x−µ)
2
2σ
2
− log
*
√
2πσ
+$
dx
= log
*
√
2πσ
+
S
+∞
−∞
1
√
2πσ
exp{−
(x−µ)
2
2σ
2
}dx +
1
2σ
2
S
+∞
−∞
(x − µ)
2
1
√
2πσ
exp{−
(x−µ)
2
2σ
2
}dx
=
1
2
#
1 + log(2πσ
2
)
$
,
由此可以看出，服从正态分布的变量，其熵的大小只与方差有关，方差相同则对应的熵也相等，方
差越大熵值越大。
$%"&'#(
284
)!*+",$
24.7. 信息度量
!"#
定理24.1. 对于随机变量X，H(X) ≥ 0，当且仅当随机变量服从均匀分布时，H(X)最大。对于离
散变量X，如果它的可能取值为有限集合{x
1
,...,x
n
}，则有H(X) ≤ log n，当且仅当p(x
i
)=
1
n
时，
等式成立。
24.7.2. 联合熵
如果将两个离散随机变量X和Y 简单联合，构成新的联合随机变量(X, Y )，则新的联合随机变
量的熵（Joint Entropy）定义为：
H(X, Y )=E
X,Y
[I(x, y)] = −
"
x,y
p(x, y) log p(x, y) (24.63)
如果事件X和Y 是相互独立的，则p(x, y)=p(x)p(y)，那么
H(X, Y )=−
"
x,y
p(x)p(y) log(p(x)p(y)) = −
"
x
p(x) log p(x) −
"
y
p(y) log p(y)=H(X)+H(Y )
24.7.3. 交熵
假设随机变量X的概率密度函数为P (X)，许多情况下P (X)是未知的，人们通常使用统计的手
段得到P (X)的近似分布Q(x)，则随机变量X的交叉熵（Cross Entropy）定义为：
H(P (X),Q(X)) = −
"
x∈X
P (x) log Q(x) (24.64)
如果将交叉熵引入计算机语言学，可以处理机器翻译的歧义问题。采用语句的真实语义作为交
叉熵的训练集的先验信息，将机器翻译的语义作为测试集后验信息，使用两者的交叉熵指导对歧义
的辨识和消除。
24.7.4. 条件熵
设有随机变量X, Y ，其联合概率分布为
p(x, y)=P (X = x, Y = y)
条件熵（Conditional Entropy）H(X|Y )表示已知随机变量Y 的条件下，随机变量X的不确定性，
并做如下定义：
H(X | Y )=E
Y
[H(X|Y = y)]
=
(
y
p(y)H(X|Y = y)
= −
(
y
p(y)
(
x
p(x|y) log p(x|y)
= −
(
x,y
p(x, y) log
p(x,y )
p(y)
= H(X, Y ) −H(Y )
(24.65)
H(X|Y )表示随机变量Y 给定条件下，X的条件概率分布熵在Y 上的数学期望。
$%"&'#(
285
)!*+",$
搜索与排名 Searching and Ranking
!"#
24.7.5. KL散度
KL散度（Kullback–Leibler Divergence）[295, 296]，又称相对熵（Relative Entropy）或信
息散度（Information Divergence）是度量两分布（真实概率分布与任意概率分布）之间距离的一
种方式。假设存在真实分布p(X) 及任意一个分布q(X)，则两分布之间的KL散度定义为：
D
KL
(p(X)∥q(X)) =
"
x∈X
p(x) log
p(x)
q(x)
(24.66)
根据交叉熵的定义可知：
D
KL
(p(X)∥q(X)) =
"
x∈X
p(x) log
p(x)
q(x)
= −
"
x∈X
p(x) log q(x ) − H(X)=H(p(X),q(X)) − H(X)
(24.67)
引理24.1. 对任意两个分布p(X)与q(X)，都有D
KL
(p(X)∥q(X)) ≥ 0，当且仅当p(X)=q(X)时，
D
KL
(p(X)∥q(X)) = 0。
引理24.2 (Pythagorean性质). 如果p ∈ P ，q ∈ Q，ˆp ∈ P ∩ Q，则有
D
KL
(p(X)∥q(X)) = D
KL
(p(X)∥ˆp(X)) + D
KL
(ˆp(X)∥q(X)).
定理24.2 (最大熵解). 如果ˆp ∈ P ∩ Q，则解
ˆp = arg max
p
H(p) (24.68)
存在且唯一。
定理24.3 (最大似然解). 如果ˆp ∈ P ∩ Q，则解
ˆp = arg max
q
L(q) (24.69)
存在且唯一。
定理24.4 (对偶定理). 存在唯一的分布ˆp，满足
ˆp = arg max
p
H(p) = arg max
q
L(q) ∈ P ∩Q. (24.70)
根据对偶定理可知，最大熵解可以写作对数线性形式，解出最大似然解就给出了最大熵解。
在数据压缩应用中，假设数据服从分布q(X)并执行压缩，而数据真实分布为p(X)，则KL-散度
表示相对理想情况，压缩数据需要的平均额外的支出（比特）。从信息论的角度来看，如果随机变
量的真实分布为p(X)，然而人们却错误地使用概率密度函数q(X)，则KL散度刻画了由于使用错误
的分布密度函数而导致信息量的增加。
$%"&'#(
286
)!*+",$
24.7. 信息度量
!"#
图 24.9: Solomon Kullback (1907 - 1994) 图 24.10: Richard Leibler (1904 - 2003)
24.7.6. 互信息
互信息（Mutual Information）表示通过观察一个随机变量，从另外一个随机变量中获取的信
息量，它是通信理论中的一个重要指标，常用于最大化发送信号和接收信号间共享的信息量。随机
变量X相对Y 的互信息定义为：
I(X; Y )=
"
X,Y
p(x, y) log
p(x, y)
p(x)p(y)
= H(X) − H(X|Y )=H(X)+H(Y ) − H(X, Y ) (24.71)
由此可知，在知道Y 的情况下为X编码，相比不知道Y 的情况下，可以节省I(X; Y )个比特。由定义
可知，互信息I(X; Y )是对称的。如果随机变量X和Y 是相互独立的，由H(X, Y )=H(X)+H(Y )可
知I(X; Y )=0。
根据等式
D
KL
(p(X|Y = y)∥p(X)) =
"
x∈X
p(x|y) log
p(x|y)
p(x)
=
"
x∈X
p(x|y) log
p(x, y)
p(x)p(y)
可以使用KL-Divergence表示互信息：
I(X; Y )=
"
x∈X
p(x|y)p(y) l og
p(x, y)
p(x)p(y)
= E
p(y)
[D
KL
(p(X|Y = y)∥p(X))]
联合熵、条件熵、互信息三者之间的关系可以通过图24.11形象表示。
$%"&'#(
287
)!*+",$
搜索与排名 Searching and Ranking
!"#
图 24.11: 联合熵、条件熵、互信息三者之间的关系
24.7.7. 詹森–香农散度
詹森–香农散度（Jensen–Shannon Divergence），也称信息半径（Information Radius，IRad），
在统计学中，常用作衡量两个概率分布的相似度。JS散度建立在KL散度之上，但又不同于KL散度：
JS散度是对称的。它最初为Dagan Ido等人用于计算单词的相似性[297]，现在已经成为生物信息学
重要的度量工具。
对于两个概率分布P 与Q，它们的JS散度定义为两个KL散度的均值：
D
JS
(P ∥Q)=
1
2
(D
KL
(P ∥M)+D
KL
(Q∥M)) (24.72)
其中，M =(P + Q)/2表示P, Q的混合概率分布。根据定义可知D
JS
∈ [0, 1]：
D
JS
(P ∥Q)=
1
2
(
(
P log
P
M
+
(
Q log
Q
M
)
= H(M) −
1
2
H(P ) −
1
2
H(Q)
(24.73)
假设X是服从混合分布M的随机变量，Z表示二元示性变量（Binary Indicator Variable）， 如
果X服从P 时，则Z =1，如果X服从Q时，则Z =0。变量X与Z的互信息
H(X; Z)=H(X) − H(X|Z)
=
(
M log M − Pr(Z = 0)H(X|0) − Pr(Z = 1)H(X|1)
= H(M) −
1
2
H(P ) −
1
2
H(Q)
(24.74)
与概率分布P 和Q的JS散度等价。
I. 最小编码长度
哈夫曼编码是由戴维·哈夫曼David A. Huffman于1952年出，属于一种典型的变长编码
（Variable Length Coding, VLC）方式，基于“高频字母短编码，低频字母长编码”的原则实现最
优编码，主要用于文本文件的无损压缩（Lossless Compression）。
$%"&'#(
288
)!*+",$
24.7. 信息度量
!"#
图 24.12: David Albert Huffman (1925 - 1999)
哈夫曼编码的目标是寻找最有效率的编码方式，使得平均编码长度最短。可以证明哈夫曼编码
是满足最小信息熵的编码。
II. Fano不等式
$%"&'#(
289
)!*+",$
