如何利用knowledge base来做推荐

本文描述的是推荐系统使用Linked Data做为主要数据源的情况。

       注:文中的SparQL语句可以在这里查询


首先介绍一点背景信息。Dr. Gautam Shroff在《Web Intelligence and Big Data》里提到语义网(semantic web)大致的vision是:将facts和rules从现有的web里面提取出来。老的facts又和rules产生新的facts,于是semantic web不断壮大。他指出这样的semantic web虽然没有被实现,但能跨领域地表示knowledge(facts和rules)的技术已经出现了:RDF(Resource Description Framework)RDFS(RDF Vocabulary Definition Language),OWL(Web Ontology Language)等。

<----------------------------------------

小知识:RDF使用3元组的形式组织数据:subject(主语),predicate(谓语),object(宾语)。其中,subject和object可以均是由URI标识的resource,也可以分别是resource和字符串。RDFS和OWL能用于创建描述entity和entity之间联系的vocabularies。Vocabularies是classes和 properties 的集合,他们被表示成RDF格式,使用的是RDFS和OWL中的术语。(摘译自[29])

----------------------------------------->


Linked Data可以看成一种协议,它用于描述如何将有关联的data连接起来,以形成一个knowledge base(可以简单地当做存储knowledge的datasets)。不同的knowledge base又可以相互连接,最终形成LOD(Linked Open Data) cloud,部分截图如下(来自这里):


图1

图中每个圈表示一个knowledge base,圈内部又是很多相互连接的data。来看张内部放大图,大致是这样子的:


图2    from [22]

从图中,我们可以获取挺多信息。比如,《洛奇II》的导演是史泰龙,他同时也是里面的主角。


回到图1。其中,DBpedia是从Wikipedia中抽取knowledge而建立起来的。Wikipedia中的每一篇文章在DBpedia里都有对应的URI。因此,DBpedia也被称为Linked Data version of Wikipedia。由于Wikipeida内容本身涉及不同领域,DBpedia便成为了LOD cloud 的一个core,或者说是hub —— 连接了来自不同领域的knowledge bases。其他的knowledge bases有LinkedMDB(RDF version of IMDB),Freebase等。


<-----------------------------------------

小知识:DBpedia如何从Wikipedia提取ontology?

首先,Wikipedia里有个叫infobox的模板,通常位于文章的最右上角,用来概括每篇文章的重要内容。比如,英文维基百科中,关于Leonardo DiCaprio的infobox如下:

fromWikipedia

采用模板的好处是能使信息的描述更加标准化,提高复用率。而且,由于infobox是采用键值对(attribute-value pair)的形式描述,这就方便DBpedia从infobox抽取文章的信息。具体地,DBpedia定义从infobox到DBpedia ontology的Mapping,从DBpedia 3.5起还允许external contribution to the mapping.具体可以看这里

----------------------------------------->


可以看到,整个LOD cloud跟传统的互联网很相似。搜索引擎可以顺着data间的链接将数据爬下来,以提供类似传统搜索引擎的搜索功能。查询使用的语言是SPARQL,有点类似SQL语句。很多knowledge base都提供了SPARQL endpoint,方便用户查询。当然,相互连接起来的data作用不止供用户查询、浏览这么简单。更重要的,在linked data 格式下,data以及data之间的关系能够被计算机理解、处理。其实,linked data主要是给机器看的!


机器能理解数据后,会有什么好处?举个简单的例子。回想最简单的搜索方法:关键字匹配。它的问题在于一个词在不同的语境下有不同的含义,而且还会存在近义词。因此,基于关键词匹配的上下文广告推荐效果不好。但若将关键词对应的概念(concept)映射到knowledge base中,就能大大消除概念之间的歧义和模糊性。因为与其相连的resource能够确定该concept的上下文环境。


接下来才是文章的重点,我们如何把knowledge base运用到推荐系统中?首先,要利用knowledge base中的关系网络,就要把现实里的item映射到里面去。由于[22]使用Movielens数据集,因此它首先通过SPARQL查询语句将MovieLens里的电影映射到DBpedia(即movie id -> URI in DBpedia)。使用如下SparQL查询语句:(注:其实用id映射感觉更好,因为DBpedia Ontology中有个property就是imdbId )

SELECT DISTINCT ?movie ?label ?year WHERE {

?movie rdf:type dbpedia-owl:Film.
?movie rdfs:label ?label.
?movie dcterms:subject ?cat .
?cat rdfs:label ?year .
FILTER langMatches(lang(?label), "EN") .
FILTER regex(?year, "^[0-9]{4} film", "i")
}

ORDER BY ?label

然后借鉴文本处理中词袋(bag-of-word)模型的思想,将一个item用tf-idf向量表示。然后使用SVM来对item分类:(大于3分的)喜欢和(否则)不喜欢(就像将邮件分类为spam和not spam一样)。[23]整体上采用相同的方法,不过它另外使用了 Freebase 和 LinkedMDB 。作者没有重新将MovieLens中的电影重新映射到这两个knowledge base上,而是使用property owl: sameAs 直接将DBpedia里的resource 与 Freebase 和 LinkedMDB 的resource联系起来。


作者指出使用SVM出于它的两个优点:(1) SVM在过拟合方面是很鲁棒的,因此做不做term(也就是feature) selection不太重要。(2) 不需要调参数。但本人并不赞同(2)的说法。其实共有两个参数要调:一个参数C调整对SVM分类器误差的敏感度;还有因为作者使用了RBF核,因此还有个RBF的参数lamba。这两个是很重要的参数,不像作者说的不需要投入human effort。Moreover,个人觉得[22]一个更大的问题在于:要实现个性化推荐的话,该系统得为每一个用户都训练一个分类器。耗时不说,更大的问题在于每个用户的评分数据都是很少的(训练样本少),而且物品的特征向量维度又很大。因此就算是SVM,也严重存在over-fitting的嫌疑。

回到item的表示上来。具体如何计算每个物品对应的tf-idf向量,可以参见[23]。大致是将movie看成document,与movie通过某一property相连的resource看成keyword。可见作者是将不同property分别考虑的。由于与电影相关的property不只一个,如starring,director等等。因此,一部movie相当于是按property分段表示的。有了向量表示(也被称为Vector Space Model),作者使用cosine计算两个向量的相似度。这里又涉及如何结合不同属性对应的similarity,以得到最终similarity的问题。基本思想是为不同property赋予不同的权值。[23]提供了两种方案:(1)采用遗传算法。(2)使用Amazon给用户的推荐。具体地,如果Amazon推荐电影b给看过电影a的用户,那么连接a和b的属性p对应的权值加1,最后进行归一化。这两个方法求得的property权值向量都是全局的。


然而如何选择property?话句话说,哪些property能体现两部电影的客观相似性,或者(从用户角度来说)主观相似性。 [23]指出三种情况:(1) 两部电影直接相关,如同属一个系列的,如The Ring I,The Ring II。可以使用dbpedia-owl:previousWork和subsequentWork表示。(2) 对同一个property来说,两部电影共享一个object。(3) 对同一个property来说,两部电影共享一个subject。最终,作者使用了如下propery:(1) dcterms:subject计算电影所属类别,并使用skos:broader获得更高层类别(可以看到适当的类别expansion是有益的);(2) dbpedia-owl:wikiPageWikiLink:用以指示Wikipedia中两个page间的链接;(3) dbpedia-owl中的property,如dbpedia-owl:starring, dbpedia-owl:director。更多使用如下SparQL查询语句查看:


SELECT ?p, COUNT(?p) AS ?n WHERE {
?s a dbpedia-owl:Film .
?s ?p ?o .
FILTER(regex(?p, "^http://dbpedia.org/ontology/"))
}
GROUP BY ?p
ORDER BY DESC(?n)


最后梳理一下:

I 准确度不高。虽然[23]没有将纯基于knowledge base的推荐系统与传统的基于CF的推荐系统对比,但[22]的结果显示,它跟CF-based之间的准确度是有差别的。

II 只适用于隐式评分。基于knowledge base的推荐系统只适用于隐式评分问题。因为,语义不能捕捉一部电影的好坏,同样题材的片子:有的好,有的就烂。因此只能反过来推:从用户喜欢的物品里推出knowledge base里他喜欢的东西。

III 个性化推荐是个问题。[23]训练出来的是一个全局property权值向量。这个不符合common sense:不同用户的侧重点不同,有人偏爱演员,有人篇导演。而[22]的方法,如果我没有理解错的话,是行不通的。而且使用某一用户的数据单独训练,就无法捕捉用户之间行为的联系。CF证明这种关系是vital的。因此,如何更好地实现个性化推荐是个问题。

IV property选择是个问题。在多级评分(如1-5)可用的情况下,将其转化为binary评分这一过程本身就损失了很多信息。所映射到的knowledge base的质量又是另一个更大的问题:比如ontology里面的属性乱不乱,即具有推荐参考价值的属性占多少。因为,我们自己去看DBpedia film ontology里的属性的话,会看到很多相当生僻的属性。无关的属性会引入噪声,SVM虽然在最大margin的限制下VC维度有上限,但也不能把所有属性一股脑考虑进去。feature数比样本数大很多时,SVM的效果不好。

IV 信息的缺失。将物品的映射到人工构造的knowledge base会带来或多或少的信息缺失。理想地,应该从包含更多信息的源数据直接做推荐。何况而且已有的FM被证明是十分有效的。

V 所以,个人觉得用knowledge base作为唯一数据源来做推荐的效果不会超过传统的CF。但是可以把它集成进现有的CF算法中去。而且它还有很多其他的用途:用来做推荐的解释,在跨领域推荐问题中发挥作用以及有助于解决推荐系统冷启动问题。


update:

————————————————————————————————————————

针对上面总结的I、IV两点,这篇补充介绍一个使用knowledge的CF混合模型。之前就有文章提出使用ontologies来缓解推荐系统的冷启动问题,但是它们大多针对评分预测问题。而且这个模型使用近来越来越热的learning to rank方法进行训练。

回想以往利用ontology作为辅助的推荐系统。它们要么使用用户的demographic信息来辅助计算用户的相似度,要么使用物品的类别信息来辅助计算物品间的相似度。因此,容易想到的是使用knowledge base辅助计算物品间的相似度,然后使用协同过滤算法。这是个方法,不过这里我们要使用Learning to rank。作者使用图模型结合评分记录和knowledge:knowledge base本身是一张图,而用户和物品也可以看成一张二分图。因此,这两张图可以无缝地拼接起来。如下图:

from[27]

其中,蓝色代表用户,红色代表物品。绿色代表knowledge中的点。

作者的做法是从这张图中抽取基于路径的特征向量。具体的,向量中的一个item对应一种类型的路径的数量。由于路径类型数几乎是指数级别的,无法考虑所有路径。而且,不同的路径应该有不同的权重。因此,作者考虑长度不大于L的路径。至于权值问题,可以交给机器学习算法自己解决。

文中的机器学习算法采用RF和GBRT的结合体——Bagboo。具体地,它将RF中的每棵树都替换成了gradient boosted tree。因此,Bagboo即具有RF不会over-fitting的健壮性,又有GBRT高accuracy的特性。

<----------------------

小知识:

Random Forest和Gradient Boosted Regression Tree是两个强大的机器学习算法。其中,Random Forest的主要思想是使用booststrap sampling训练多个decision tree(high variance),然后将所有树的结果平均起来,以减少variance。与RF训练一个森林不同,GBRT训练一棵树。从一棵小树开始,每次迭代都加入一个high bias的树(weak learner),以针对当前的训练error。

------------------------->

数据处理方面 作者将MovieLens和LastFM中少于20个评分项的用户删掉。将剩下的物品使用类似的方法映射到DBpeida ,再 去掉没有映射的物品。然后迭代式地查询与物品直接相关、间接相关的entity。如查询Adele写的歌: SELECT ?s WHERE
{ ?s dbpedia-owl:writer dbpedia:Adele. }


参考文献:

[22] Exploiting the Web of Data in Model-based Recommender Systems

[23] Linked Open Data to support Content-based Recommender Systems

[27] Top-N Recommendations from Implicit Feedback leveraging Linked Open Data

[29] Linked Data - The Story So Far
相关文章
相关标签/搜索