1.问题介绍
在基于标签的推荐系统中 ,经常需要选择一组标签作为用户画像,在相关资料中,有人提到利用最小描述长度MDL的方法来进行选择,例如肖仰华的《知识图谱概念与技术》。
但是在相关资料中,包括网络上其他资料,对于具体做法并不明确。自己之前做的工作中,有涉及到标签选择的任务,因此这里分享一下自己的理解,并结合国家的案例做说明。
2.原理
在资料中,假设CCC是要使用的标签组,X是一组实体,那么针对X,标签CCC的编码长度由以下两部分构成:
MDL(C,X)=−logP(C)+∑xi∈x−logP(xi∣C)MDL(C,X)=-logP(C)+ \sum_{x_i \in x}-logP(x_i|C) MDL(C,X)=−logP(C)+xi∈x∑−logP(xi∣C)
其中第一部分是标签组CCC的先验概率或信息量,第二部分P(xi∣C)P(x_i|C)P(xi∣C)是给定实体xix_ixi能够联想到标签C的概率,MDL的值越小,说明当前标签组C的信息量越多,并且越容易通过标签组C联想到实体组X,具体而言:
logP(C)=lognCnTotallogP(C)=log\frac{n_{C}}{n_{Total}} logP(C)=lognTotalnC
上面公式中,n(C)n_{(C)}n(C)表示当前标签C覆盖的关系数,nTotaln_{Total}nTotal表示总的关系数,
logP(xi∣C)=lognxinClogP(x_i|C)=log\frac{n_{x_i}}{n_{C}} logP(xi∣C)=lognCnxi
上面公式中,nCn_CnC含义不变,仍表示当前标签C覆盖的关系数,而nxin_{x_i}nxi可以表示在关系CCC下,xix_ixi出现的总次数。
3.例子
下面举例说明,例如现在有200个国家,其中亚洲国家50个,东亚国家10个,西亚国家10个,中亚国家10个,东南亚20个。
例子1:
假设现在国家集合XXX={中国,韩国,朝鲜,沙特,伊朗},候选标签组分别为C1C_1C1={亚洲},C2C_2C2={东亚,西亚},C2C_2C2={国家},简化起见,令nxin_{x_i}nxi均为1。按照常识,最合适的标签应该是C2C_2C2。
以标签C1C_1C1为例,
logP(C)=lognCnTotal=log(50200+50+10+10+20)=log(50300)logP(C)=log\frac{n_{C}}{n_{Total}} =log(\frac{50}{200+50+10+10+20} )=log(\frac{50}{300})logP(C)=lognTotalnC=log(200+50+10+10+2050)=log(30050)
针对x1x_1x1=中国:
logP(xi∣C1)=lognxinC=log150logP(x_i|C_1)=log\frac{n_{x_i}}{n_{C}}=log\frac{1}{50} logP(xi∣C1)=lognCnxi=log501
因此在给定XXX和C1C_1C1的情况下,其MDL应为:
-math.log(50/300)+((-math.log(1/50))+(-math.log(1/50))+(-math.log(1/50))+(-math.log(1/50))+(-math.log(1/50)))
# 计算结果:MDL(C1,X)=21.351874496368783
同理,给定XXX和C2C_2C2:
-math.log(10/300)+((-math.log(1/10))+(-math.log(1/10))+(-math.log(1/10)))-math.log(10/300)+(-math.log(1/10))+(-math.log(1/10))
# 计算结果:MDL(C2,X)=18.315320228294542
同理,给定XXX和C3C_3C3:
-math.log(200/300)+((-math.log(1/200))+(-math.log(1/200))+(-math.log(1/200))+(-math.log(1/200))+(-math.log(1/200)))
# 计算结果:MDL(C3,X)=26.897051940848346
结合以上结果,应选择C2C_2C2={东亚,西亚}作为标签组,来描述XXX={中国,韩国,朝鲜,沙特,伊朗},这符合实际感受。
例子2:
下面举例说明,例如现在有200个国家,其中亚洲国家50个,东亚国家10个,西亚国家10个,中亚国家10个,东南亚20个,欧洲、非洲、美洲国家各50个,
且国家集合XXX={中国,韩国,美国,加拿大},为简化起见令nxin_{x_i}nxi均为1
则在标签组C1C_1C1={亚洲,美洲},C2C_2C2={东亚,美洲},C3C_3C3={东亚,美洲,欧洲}下,MDL值分别为:
-math.log(50/450)+(-(math.log(1/50))+(-math.log(1/50)))-math.log(50/450)+(-math.log(1/50)+math.log(1/50))
# 计算结果:C1=12.218495165528731
-math.log(10/450)+(-(math.log(1/10))+(-math.log(1/10)))-math.log(50/450)+(-math.log(1/50)+math.log(1/50))
# 计算结果:C2=10.609057253094631
-math.log(10/450)+(-(math.log(3/10))+(-math.log(2/10)))-math.log(50/450)+(-math.log(1/50)+math.log(1/50))+(-math.log(50/450))
# 计算结果C3=11.014522361202795
因此选择C2C_2C2={东亚,美洲}来解释XXX={中国,韩国,美国,加拿大}。
例子3:
在例子2的基础上,假设现在有一个新的标签“亚洲工业强国”,并且中国,韩国与这个新概念高度相关,即
前面两个例子提到的nxin_{x_i}nxi均不为1,假设分别为4,2,那么C4C_4C4={亚洲工业强国,美洲}下MDL的值为:
-math.log(10/450)+(-(math.log(4/10))+(-math.log(2/10)))-math.log(50/450)+(-math.log(1/50)+math.log(1/50))# 计算结果 C4=8.529615711414795
说明概念C4C_4C4={亚洲工业强国,美洲},比概念C2C_2C2={东亚,美洲}更能解释国家集合XXX={中国,韩国,美国,加拿大},
利用“亚洲工业强国”这个概念,更容易联想到“日本”这样的“工业强国”,而不是“香港”“澳门”这样的“金融城”。