microsoft在《Position-Normalized Click Prediction in Search Advertising》对coec做了介绍。

1.介绍

竞价排名搜索广告的ctr预估系统的目标是:根据其它上下文知识(比如:用户信息),对一个query-ad pair估计CTR。ctr预估对于ad排序、位置分配(allcation),定价(pricing),以及回报(payoff)很关键。通过估计得到的CTR作为query-ad相关度的一种衡量,并且与其它非相关因子相互独立。然而实际上,有许多外围因子影响着基于相关度的ctr系统,通常会在观察到的点击数据(click-through data)上扮演着重要角色。一个经典的示例是:广告展现位置(ad presentation position)。这些外在因子必须小心处理,否则会导致一个次优的ctr预估,许多真实世界的系统都会存在这种缺陷。

我们提出了一个概率因子模型(probabilistic factor model)作为一个总的原则性方法来研究这些效应。该模型很简单并且是线性的,在广告领域会做出经验性的调整。对于纠正在搜索算法上的位置偏差(positional bias)有大量研究,许多研究都是:检测模型(examination model)[12],cascade model[5], 动态贝叶斯网络模型(DBN)[3],而对于搜索广告领域却很少。我们的方法采用了与examination model相似的因子分解假设,也就是说:在item上的点击概率,是一个关于位置先验概率和一个基于相关度的与位置无关的概率的乘积。再者,我们会专门研究广告领域的位置概念,通过合并其它广告特有的重要信号,例如:query-ad keyword match type和广告总数。

来自搜索算法的其它模型(比如:cascade和DBN模型),通常会假设:一个item的估计得到的ctr(estimated CTR)是与展示在搜索结果页的items的相关度(relevance)相互独立的。这些更复杂的假设对于搜索算法结果更合适,其中用户对于结果链接之一上的点击行为具有一个高概率。然而对于广告,在广告上的点击概率总是相当低,通常是一个百分比。因此,效果越高(非点击)的广告是相互接近的因子的乘积。

2.因子模型

假设:

  • i表示一个query-ad pair
  • j表示ad的位置
  • c表示点击次数
  • v表示曝光次数

观察到的CTR是一个条件概率 。对于在竞价搜索广告中的经验假设,我们做出如下简化:

  • 1.一个ad的点击是与它的位置相互独立的 (假设:位置可以物理上进行检查examining)。
  • 2.给定一个ad的位置,检查(examining)一个广告是与它的内容或相关度是相互独立的

正式的,位置依赖的CTR(position-dependent CTR)可以表示为:

…(1)

其中:

  • 第一个因子 :可以简单表示为,它是一个位置归一化的CTR(position-normalized CTR),可以表示ad的相关度
  • 第二个因子 ,可以简单表示为,体现了位置偏差( positional bias)。

有了该CTR因子分解(factorization),我们可以处理关于点击行为的两种自然随机模型,接着在部署模型上通过一个先验进行平滑。【1,9】

3. Binomial模型

很自然的,假设点击数遵循一个二项分布:

。。。

4.POISSON模型

如果尝试次数n足够大,成功概率p (success probability)足够小,那么。由于广告(ad)就是这样一个领域,我们可以导出Poisson模型,它会生成一个相似的且足够有效的更新。该生成模型是:

…(9)

5.GAMMA-POISSON模型

对于empirical和regularization的目的,我们在Poisson模型中在位置因子(positional factor)上引入了一个gamma先验:

…(16)

经验上,观察CTR(observed CTR)几何上会随位置的降低而递减【11】,展示出与gamma信号有一个很好的拟合。实例上,次一点的位置(inferior positions,比如:side bar的底部位置)可能会遭受严峻的数据稀疏性问题,尤其是点击;因此,正则化(regularizing)或平滑(smoothing)这些噪声估计会产生更好的泛化。gamma分布是一个常见的选择,因为它是Poisson的一个共轭先验。

。。。

6.点击模型

一个点击模型或CTR预测模型的目标是:为给定的一个query-ad pair,估计一个位置无偏CTR(positional-unbiased CTR),例如:相关度CTR(relevance CTR) 。上述描述的位置归一化点击模型(positional normalized click model)会做这样的处理,同时也会发生位置先验概率 。factor模型的另一个观点是:在ad位置上做过平滑的kNN模型;当特征空间只包含了query-ad pairs,k=1。对于有足够历史点击数据的query-ad pairs这是可信的,因子模型可以合理执行。而对于一个冷启动问题原则性处理方法是,将queries和ads的一元特征(unigram features)添加到特征空间中,当在预测时遇到新的pairs时对CTR预估做backing-off。

位置归一化点击模型也可以被独立应用,并联合其它点击模型来估计relevance-only CTR。更严厉的,我们会所设位置因子与其它相关度因子相互独立。在模型训练时,需要通过它的位置先验来归一化每个ad曝光。在预测时,CTR预测器会从位置归一化的训练数据中进行学习,并生成完全的relevance-only CTR。

7.实验

7.1 使用人造数据仿真

我们首先在一个通过概率模型(例如:给定一个sound模型)生成的人造数据集上仿造了Gamma-Poisson模型。通过仔细设计模型参数,人造数据可以十分模仿真实的搜索广告数据。尽管模仿数据不能完全反映真实系统,但它至少有两个优点:

  • 1.当从真实噪声中进行抽象时,允许快速研究大量参数
  • 2.通过该数据曝露的真实分布来验证学到的模型,对于真实数据很重要

数据生成如下:

    1. 位置 ,生成一个,以降序对q排序,通过对q进行缩放
  • 2.

参考

lightFM源自于paper: 《Metadata Embeddings for User and Item Cold-start》:

一、介绍

构建推荐系统能在冷启动场景中(新用户、新item)运行良好是个挑战。标准的MF模型在该setting中效果很差:很难有效估计user和item的隐因子,因为协同交互数据很稀疏。

基于内容的(CB)方法,可以通过使用item的metadata来解决该问题。因为这些信息是事先预知的,对于新item(没有协同数据可收集)的推荐依然可以计算。不幸的是,在CB模型中没有迁移学习出来:对于每个用户的建模是以孤立的方式估计得到的,并没有利用其它用户数据。因此,CB模型的执行会比MF模型要差。

最后,解决该问题很关键。我们是一家时尚公司,目标是为我们的用户提供便利的方法进行在线时尚品浏览、购买。为了这个目的,我们维护了一个非常大的商品目标:在写入时,我们会跨网络聚合超过800w的时尚items,并会每天添加上万新的商品。

为我们做出推荐有三个因子。首先,我们的系统包含了一个非常大的items数目。这使得我们的数据很稀疏。第二,我们如下进行处理:通常,最相关的items是那些新释放出的collections,允许我们只有一个短时间窗口来收集数据,并提供有效推荐。最后,我们的用户大比例是首次访问的用户(first-time visitors):我们希望为他们推荐引人注目的推荐,即使只有少量数据。用户和item的冷启动组合,使得纯粹的协同和CB方法不适用。

为了解决该问题,我们使用一个混合content-collaborative模型,称为LightFM,归因于它会对FM进行resemblance。在LightFM中,就像在一个协同过滤模型中一样,users和items被表示成隐向量(embeddings)。然而,正如在一个CB模型一样,这些都通过描述每个商品或用户的内容特征(content features)的函数进行定义。例如,如果该电影“绿野仙踪(Wizard of Oz)”通过以下的features描述:”音乐幻想剧(musical fantasy)”、“朱迪·加兰(Judy Garland)”、以及“Wizard of Oz”,那么它的隐表示可以通过对这些features的隐表示进行求和得到。

通过这么做,LightFM可以将CB和CF的推荐的优点进行联合。在该paper中,我们会对该模型公式化,并在两个数据集上进行实验,展示:

  • 1.在冷启动和低密度场景,LightFM至少与纯CB模型一样好,实质上,当满足以下二者之一(1)在训练集中提供了协同信息 (2) 在模型中包含了用户特征 时,效果要更好。
  • 2.当协同数据很丰富时(warm-start, dense user-item matrix),LightFM至少与MF模型效果一样好。
  • 3.通过LightFM生成的Embeddings,可以编码关于features的重要语义信息,可以被用于相关推荐任务:比如:标签推荐。

这对于真实推荐系统来说有许多好处。因为LightFM在dense和sparse数据上均表现良好,它不需要为每种setting构建和维护多个特定机器学习模型。另外,它可以同时使用user和item的metadata,它可以应用于user和item的冷启动场景。

LightFM python版的Github地址为:https://github.com/lyst/lightfm.

2.LightFM

2.1 动机

LightFM模型的结构受以下两种考虑的启发:

  • 1.该模型必须能从交互数据中学习user和item表示:如果描述为“舞会袍(ball gown)”和”铅笔裙(pencil skirt)”的items均被用户所喜欢,该模型必须能学到ball gowns与pencil skirts相似。
  • 2.该模型必须能为新items和users计算推荐

第1点通过使用隐表示方法来解决。如果ball gowns和pencil skirts均被相同的用户所喜欢,它们的embeddings会更接近;如果ball gowns和机车夹克(biker jackets)不会被相同的用户所喜欢,它们的embeddings会更远。

这样的表示允许迁移学习出现。如果对于ball gowns和pencil skirts的表示很相近,我们可以自信地推荐ball gowns给一个刚与pencil skirts交互过的新用户。

在纯CB模型之上使用降维技术(比如:LSI)也可以达到该目换,因为它们只会编码由feature co-occurrence给定的信息,而非用户动作。例如,假设所有浏览过由“飞行员(aviators)”描述的items的用户,同时也浏览了由“旅行者(wayfarer)”描述的items,但这两个features从未在相同的item中同时描述过。这种情况下,对于wayfarers的LSI vector不会与aviators的相似,即使协同信息建议应该这样做。

第2点通过将items和users表示成它们的content features的线性组合。由于content features被认为是:当一个user或一个item进入该系统时,它允许直接做出推荐。这种结构很容易理解。“牛仔夹克(denim jacket)”的表示看成是denim的表示和jacket的表示的求和(sum);一个来自美国的女性用户(a female user from the US)的表示是US的表示和female users的表示的求和。

2.2 模型

为了公式化描述该模型,假设U是用户集,I是items集合,是user features的集合,是item features的集合。每个用户与多个items交互,正向或者负向。所有user-item交叉pair 是正交互和负交互的联合。

Users和items通过它们的features进行完全描述。每个user u通过一个特征集合描述 。为每个item i它们的特征为。features是提前知道的,可以表示user和item的metadata。

该模型通过d维的user和item的feature embeddings 为每个feature f进行参数化。每个feature也可以通过一个标量bias项(对于user features是,对于item features则是)描述。

user u的隐表示,通过对它的features的隐向量进行求和来表示:

item i的隐表示类似,如下:

user u的bias项,通过对features的biases进行求和得到:

item i的bias项如下:

该模型对于user u 和 item i的预测,接着通过user向量和item向量的点乘,加上对应的偏置给出:

…(1)

有许多函数适合。一个identity函数也能对预测评分很好地运行;在本paper中,我们只对二分类数据预测感兴趣,因而选择sigmoid:

模型的最优化目标是,最大化在该参数上的条件似然。该似然如下:

…(2)

使用ASGD进行训练。4线程。learning rate使用ADAGRAD。

2.3 与其它模型关系

LightFM与协同MF模型间的关系,由user和item的feature sets的结构决定。如果feature sets只包含了每个user和item的指示变量,LightFM相当于MF模型。如果feature sets也包含了metadata features,它们被至少一个item或user所共享,那么LightFM就扩展了MF模型:通过让feature的隐因子来解释用户交互的部分结构。

这在三方面很重要。

  • 1.在大多数应用中,metadata features要比users或items还要少,因为使用一个确定类型/类目的结构,或者因为维护一个固定size的关于最常用项的字典,当使用原始文本特征时。这意味着,从受限的训练数据中,需要估计更少的参数,减小overfitting机率并提升泛化效果。
  • 2.指示变量的隐向量不能为新的、冷启动users和items进行估计。将它们表示成metadata features的组合,可以从训练集中被估计,并做出冷启动预测。
  • 3.如果只有指定变量,LightFM与标准MF模型相当。

当只有metadata特征、没有指示变量时,模型通常不会缩减到一个纯CB模型。LightFM通过对协同交叉矩阵进行因子分解来估计feature embeddings;这不同于CB模型:它会对纯内容共现矩阵进行因子分解。

一个特别的case是,当每个用户通过一个指示变量描述时,并且只与一个item交互时,此时LightFM会变为CB。在该setting中,user vector等价于在LSI公式中的一个document vector,只有在product descriptions中共同出现过的features具有相似的embeddings。

事实上,LightFM一方面包含了在sparse data的纯CB模型,另一方面包含了在dense data上的MF模型。事实上,经验表明,至少与每种场景的单一模型一样好。

参考

Label Partitioning For Sublinear Ranking

1.介绍

我们有一个multi-class或者multi-label问题,其中每个训练样本包含了一个上下文,以及一个关于target classes 的小集合(该集合在一个关于可能classes的大型空间L的范围之外)。例如,我们的问题可能是:给定前面的词汇,预测在句子中的下一个词。

1.1 F(x,y)

我们希望学习到一个兼容函数(compatibility function) ,它会说明关于某个class y以及一个context x间的兼容性。例如——给定该上下文,该class的概率

“穷举(Exhaustive)”训练法,比如:softmax和logistic regression需要我们为每个训练样本,对于每个类去计算F(x,y)。当很大时,计算开销会很大。

1.2

  • target classes(正样本):
  • candidate classes(候选样本):
  • randomly chosen sample of classes(负样本):

“候选采样(Candidate Sampling)”训练法,涉及到构建这样一个训练任务:对于每个训练样本,我们只需要为候选类(candidate classes)评估F(x,y)。通常,候选集合是target classes的union,它是一个随机选中抽样的classes(非正例)

随机样本可能或不可能依赖于和/或

训练算法会采用神经网络的形式,其中表示F(x,y)的layer会通过BP算法从一个loss function中进行训练。

图1

  • : 被定义为:给定context x,根据抽样算法在sampled classes的集合中得到class y的概率(或:expected count)。
  • :是一个任意函数(arbitrary function),不依赖于候选类(candidate class)。由于softmax涉及到一个归一化(normalization),加上这种函数不会影响到计算概率。
  • logistic training loss=
  • softmax training loss =
  • NCE 和Negatvie Sampling可以泛化到是一个multiset的情况。在这种情况中,表示在中y的期望数(expected count)。相似的,NCE,Negative Sampling和Sampled Logistic可以泛化到是一个multiset的情况。在这种情况下,表示在中y的期望数(expected count)。

Sampled Softmax

参考:http://arxiv.org/abs/1412.2007

假设我们有一个单标签问题(single-label)。每个训练样本包含了一个context以及一个target class。我们将作为:给定context x下,一个target class y的概率。

我们可以训练一个函数F(x,y)来生成softmax logits——也就是说,给定context,该class相对log概率:

其中,K(x)是一个任意函数,它不依赖于y。

在full softmax训练中,对于每个训练样本,我们会为在中的所有类计算logits 如果类L很大,计算很会昂贵

在”Sampled Softmax”中,对于每个训练样本我们会根据一个选择抽样函数来选择一个关于“sampled” classese的小集合。每个被包含在中的类,它与概率完全独立。

我们创建一个候选集合,它包含了关于target class和sampled classes的union:

我们的训练任务是为了指出:在给定集合上,在中哪个类是target class

对于每个类,给定我们的先验,我们希望计算target class y的后验概率。

使用Bayes’ rule:

[bayes]{https://math.stackexchange.com/questions/549887/bayes-theorem-with-multiple-random-variables}

…(b)

得到:

接着,为了计算,我们注意到为了让它发生,可以包含y或也可以不包含y,但必须包含所有其它元素,并且必须不包含在任意classes。因此:

其中,是一个与y无关的函数。因而:

这些是relative logits,应feed给一个softmax classifier,来预测在中的哪个candidates是正样本(true)。

因此,我们尝试训练函数F(x,y)来逼近,它会采用在我们的网络中表示F(x,y)的layer,减去,然后将结果传给一个softmax classifier来预测哪个candidate是true样本。

从该classifer对梯度进行BP,可以训练任何我们想到的F。

#

以tensorflow中的tf.random.log_uniform_candidate_sampler为例。

它会使用一个log-uniform(Zipfian)base分布。

该操作会随样从抽样分类(sampled_candidates)中抽取一个tensor,范围为[0, range_max)。

sampled_candidates的元素会使用base分布被无放回投样(如果:unique=True),否则会使用有放回抽样。

对于该操作,基础分布是log-uniform或Zipf分布的一个近似:

当target classes近似遵循这样的一个分布时,该sampler很有用——例如,如果该classes以一个字母序表示的词语,并以频率降序排列。如果你的classes没有通过词频降序排列,就不需要使用该op。

另外,该操作会返回tensors: true_expected_count,

log_uniform_candidate_sampler

1
2
3
4
5
6
7
8
9
tf.random.log_uniform_candidate_sampler(
true_classes,
num_true,
num_sampled,
unique,
range_max,
seed=None,
name=None
)

使用一个log-uniform(Zipfian)的基础分布来采样classes集合。

该操作会对一个sampled classes(sampled_candidates) tensor从范围[0, range_max)进行随机抽样。

sampled_candidates的elements会从基础分布进行无放回抽样(如果unique=True)或者有放回抽样(unique=False)。

对于该操作的base distribution是一个近似的log-uniform or Zipfian分布:

当target classes近似遵循这样的一个分布时,该sampler很有用——例如,如果该classes表示字典中的词以词频降序排列时。如果你的classes不以词频降序排列,无需使用该op

另外,该操作会返回true_expected_count和sampled_expected_count的tensors,它们分别对应于表示每个target classes(true_classes)以及sampled classes(sampled_candidates)在sampled classes的一个平均tensor中期望出现的次数。这些值对应于在上面的。如果unique=True,那么它是一个post-rejection概率,我们会近似计算它。

参考

https://www.tensorflow.org/extras/candidate_sampling.pdf

google在google+这个产品上提出了《Improving User Topic Interest Profiles by Behavior Factorization》,我们来看下具体实现:

1.介绍

2.相关工作

2.1 构建user profiles

对于许多用户而言,社交媒体上共享的信息是过饱和的。因此,主题兴趣画像(topic interest profiles)的构建是个性化推荐系统中很重要的一部分。我们的工作受关于利用行为信号的个性化研究的启发。

搜索引擎研究者已经利用user profiles来提供个性化搜索结果【9,11,4,30,35】。通常,user profiles会被表示成一个在高维空间中的向量,这些向量表示了在不同items上的用户偏好(比如:网页、电影、社交媒体posts),或者在不同空间上的用户偏好(例如:表示主题的关键词、或来自类目树taxonomy的主题类别)

2.1.1 MF & Embedding模型

推荐方法的一大类是CF,系统通常会使用一个user-by-item矩阵,每个条目表示用户在一个相应item上的评分。因此,在输入矩阵中的某一行表示:一个特征用户对items的偏好。关于一个用户在一个指定item上的未知偏好,可以使用矩阵补全(matrix completion)来进行推断(infer),研究者们已经使用MF方法取得了巨大进展。

在我们的paper中,我们并没有使用通过items(发表:posts)偏好来表示user profile的方法,我们更关注对user的主题兴趣(topical interests)进行推断,其中主题通过Google知识图谱的条目进行表示(比如:”basketball”、’video games’)。研究者已经使用MF来创建embedding模型,或者生成式模型(如:LDA)来构建user profiles[21]。MF以及生成式模型可以学到latent embedding空间,其中偏好可以通过user和item间的latent embedding factors的相似度进行计算。

比起item-based方法,topic-based方法在社交媒体中更加可扩展,其中实际items(posts)数目会很大。做为替代,通过计算在user topic兴趣和item(post)兴趣间的相似度,我们可以预测在一个item上的一个用户的兴趣。

2.2 社交媒体的个性化user profiles

正如在其它推荐问题上一样,社交媒体研究者通常将构建一个user profile看成是构建一个个性化推荐系统的首要任务。研究者在社交媒体上已经应用MF和生成式模型(LDA)来建模user-topic矩阵,并专门构建了user profiles[8,7,34,3,6,15,33,27]。例如,Guy等人基于content和item的偏好来构建user profiles,接着为社交媒体items(比如:书签和社交软件)来提供个性化推荐[8,7]。Chen等人在twitter上构建了user topic profiles并提供了会话的个性化推荐。User profile也被用于提供好友推荐[6],社群推荐[33],动作推荐(mentioning推荐[33], commenting[27])。

对于一个user profile来说,用户偏好可以使用隐式反馈(比如:用户活动)进行infer[8]。作为对比,在传统推荐系统中,CF通常需要显式评分,这会带来用户的额外开销。例如,Hu等人提出了一个MF方法来利用稀疏数据的隐式反馈。在该思想基础上,Noel等人在MF上提出了一个新的目标函数,并考虑上在feature-based相似度、以及user-user信息

2.3 上下文个性化

社交媒体平台提供了用户丰富的上下文信息,比如:用户在何时(when)对某用户发表(who’s post)的某主题(what topic)进行了web评论。许多最近研究讨论了如何利用这些丰富的上下文来学习更好的user profiles。Singh等人提出的CMF(协同矩阵因子分解),目标是使用上下文信息来在异构网络上提供推荐。与该工作比较接近的有:

  • (a) Liu提出了 a social-aided context-aware recommender systems for books and movies. 会利用丰富的上下文信息来将user-item矩阵划分为多个矩阵[20]
  • (b) Jamali等人提出了: a context-dependent matrix factorization model to create user profiles for recommendation in social network [14]。

除了矩阵分解技术外,研究者提出了context-aware generative models来在Twitter上帮助创建user profiles和隐语义模型[25,32,36]。例如,Zhang等人使用生成模型提出了一个two-step framework来首先发现不同的主题域,接着使用MF方法在每个域上提供推荐[37]。不同用户可能对不同领域感兴趣,与我们工作相关,但在用户行为上有些区别。我们主要关注:每个用户的主题兴趣是如何通过不同类型的行为进行划分的

研究者们已经使用内存来构建和提升user profiles。Li等人提出了一种 transfer learning方法来对两个领域的两个向量,使用相互间的信息进行因子分解[18]。Hu等人提出了一个三元因子分解(triadic-factorization-based)方法来对user-item-domain的tensor进行因子分解,来提供跨领域的个性化推荐。

2.4 行为因子分解

“如果你将知觉(perception)看成是一种联系(contact)和洽谈(communion)的方式,那么,支配感知就是支配联系,限制和管理感知就是限制和管理联系。”—Erving Goffman, The Presentation of Self in Everyday Lif.

最近工作表明,多种上下文可以提升user profiles的质量。在我们的paper中,展示了社交媒体用户具有不同类型的行为与不同主题进行交互,我们应使用行为类型看成是一种重要的上下文。我们也会为不同行为类型构建多个user profiles,接着在不同行为独立的推荐中,灵活使用这些不同的profiles。例如:推荐阅读(read)的内容,推荐分享(reshare)的内容。等

社会学家表明,人们在他们的每一天生活中,会呈现不同的画面给其它人;他们每天的对话会以不同主题展开,具有不同的听众。社交媒体的出现吸引了社会学家的兴趣,他们在网络社群上研究了该现象。例如,社会学家建立了这样的理论:由于用户对于在公开社交媒体上的准确受众(exact audiences)没有清晰看法,他们的行为具有模糊上下文边界[22]。然而,由于不同类型的行为,比如:发表(posting)和评论(commenting),会影响非常不同的受众,我们以下的分析建议,用户在社交媒体上仍会展示出不同的“身份(’identities’)”,以及对不同的主题展示不同类型的行为。通过定量研究,Zhao等人指出:用户体验社交媒体平台(比如:Facebook),与现实中的多种身份相似。据我们所知,我们的paper是首次提出:用户在一个社交媒体上利用不同的在线表示。

3. google+行为分析

我们分析了在google+上的匿名用户在线行为。我们首先抽取了在发表(posts)上的主题条目作为我们的特征,来为每个post构建特征向量。对于每个用户在posts上的行为动作,我们会聚合post对应的feature vectors来为每个用户-行为组合(user-behavior combination)构建一个entity vector。接着,我们对这些user-behavior entity vectors表示的不同的主题兴趣进行粗粒度的measure。我们展示了在这些向量间存在很大的不同,这启发了我们利用行为因子分解来建模不同的行为类型。

3.1 数据集描述

使用了2014 五月的google+用户公开行为来进行分析。我们在所有公开发现上分析了所有用户行为,每条记录被表示为一个tuple:(u,b,E),其中一个用户u(具有一个匿名id)使用行为b来参与一个包含了实体集合E的post。有4种类型的行为:发表(post),分享(reshare)、评论(comment)、+1.

我们会使用google知识图谱的实体形式(它包含的概念有:computer algorithms, landmarks, celebrities, cities, or movies.)来抽取更高级的语义概念,而非使用更低级向量(比如:word tokens)。它当前包含了5亿实体,在主题覆盖上提供了广度与深度。

我们基于标准的实体识别方法(利用实体间的共现先验,实体间的相关度似然,实体在文本中位置,接着最终对实体主题进行最终排序),使用一个实体抽取器。

对于给定的一个post,我们使用相应的知识图谱实体作为特征来表示它的主题。因此,在input tuple(u,b,E)中每个E是一个关于知识图谱实体的集合。例如,如果一个用户创建了一个关于宠物狗图片的post,与该行为对应的是:(, CreatePost, {“Dog”, “Pet”, …})。如果另一个用户在一个关于Xbox Minecraft的youtube视频post上进行了评论,该行为对应于该tuple:(, Comment, {“Minecraft”, “Xbox”, …})。

3.2 衡量行为间的不同

对于每个user,我们会使用一个特定类型行为来从他交互的posts中聚合实体。最后,对于每个用户,我们对应于4种不同类型的行类会获得4个主题实体集合。

我们接着使用Jaccard相似度来衡量集合间的不同。

t1.png

表1: Average Jaccard similarity between pairs of behavior types

在我们计算了每个用户不同行为的jaccard相似得分后,我们接着在所有用户上对分数进行平均。我们过滤掉了:小于10个实体的用户认为是不活跃。表1展示了平均jaccard相似度的结果。我们可以看到,任意两种行为类型间的平均jaccard系统很低。以comment和+1行为为例,在这两种行为间只有9%的主题重合。我们也衡量了用户的发布(publishing)和消费(cosuming)行为上的不同。我们会将用户comment和+1行为的实体组合成一个consuming实体集合,我们将create post和reshare行为的实体组合成一个publishing实体集合。平均jaccard index为0.122. 关于jaccard得分的低重合率表明:用户在不同行为上差异很大。

3.3 讨论

结果分析表明,对于每个用户,他通常在每个行为上具有不同的主题兴趣。也就是说,她通常会在create posts上的主题与comments上的主题会很不同。结果表明,常见的无指定行为(non-behavior-specific)的user profiles可能会在那些强调不同行为类型的应用上执行效果差。

内容推荐者通常会对用户要消费的内容进行定向预测,它可能会受行为(comment和+1)的影响要更好。在其它上下文中,我们会替代预测:用户会创建什么主题的posts。因此,通过为每种行为类型创建主题偏好,特定行为的user profile在不同的推荐上下文上具有更好的效果

总之,用户在社交媒体上的不同行为包含了重要的上下文信息,它可以帮助我们提升用户个性化profiles上的效果。我们展示了,用户在G+上不同的行为类型会极大影响不同的主题兴趣,使用单独的行为类型构建不同的profiles允许我们为不同的行为上下文定制内容推荐系统。

4.问题定义

4.1 输入行为信号

我们不会为每个用户构建单个profile,相反的,我们提出了为一个用户构建多个profiles来表示它的不同行为类型。特别的,这里我们将社交媒体上的posts行为作为输入,输出一个主题兴趣向量集合来表示每个用户的不同类型的profiles。

给定一个用户集合,不同的行为类型,以及一个可以表示社交媒体内容的特征集合,输入数据可以被表示成:

其中

  • 每个表示一个用户在社交媒体内容的某个特定片段上的动作。例如,一个可以是:创建一个post,或者对某个post进行comment。
  • 是该post的特征集合。

这里由于我们正构建user topic profiles,我们使用Google知识图谱的实体作为我们的特征集。然而,总体上,可以是任意low-level(例如:words)或high-level的特征(例如:其它实体,或地理位置特征)。

4.2 User profiles

我们将user profiles定义成在特征空间E中的向量集合:

其中,

  • 是用户u的user profile,
  • 是用户u在对应于她的行为类型B上的偏好向量。

可以被认为是一个user tensor。

B即可以是单个行为类型(例如:创建一个post),或是一个不同行为类型的组合(例如:创建一个post和reshare一个post组合)。准确表述为:

其中,对于j=1,…,k,是用户u的行为类型 B在特征上的偏好。

5.我们的方法

1.png

图1: 生成矩阵和因子分解框架

我们引入了行为因子分解法来为个性化推荐构建user profiles,它包含了三个steps,如图1和2所示。

  • step 1: 给定第4节中定义的input user action tuples ,我们首先构建不同行为类型的矩阵。这对应于图1中的左部分。
  • step 2: 我们对step 1中生成的矩阵进行因子分解来学到latent embedding space。这对应于图1中的右部分。
  • step 3: 最后,我们使用学到的latent space来对兴趣主题做预测来构建user profiles。这会为每个用户u创建profiles 。这对应于图2.

2.png

图2: 使用latent embedding space构建user profiles

我们会轮流做介绍。

5.1 step 1: 为不同行为类型构建矩阵

在常见的矩阵因子分解技术中,输入的user-item矩阵R被表示成一个的矩阵,其中N表示user的数目,K表示items的数目。R被分解成两个矩阵的乘积,矩阵X (),矩阵Y()。换句话说,R中的行向量和列向量被映射到一个L维的latent embedding space中。有了这个学到的隐向量,对于在user-item矩阵中任意观察到的行向量,学到的embedding空间可以被用于帮助完成特定的行向量来补全一个用户在items上的估计偏好。

由于我们正构建user-topic-based profiles,我们使用users在主题的兴趣( user-topic matrix)作为输入,而非将users在items上的兴趣(的user-item matrix)作为输入。

另外,除了使用一个矩阵作为输入之外,我们构建和因子分解得到多个矩阵,包括:

  • (a) 传统的矩阵,被称为Behavior Non-specific User-topic Matrix(BNUM)
  • (b) Single Behavior-Specific User-topic Matrix(SBSUM)
  • (c) Combined Behavior-Specific User-topic Matrix(CBSUM)

5.1.1 BNUM (Behavior Non-specific User-topic Matrix)

这里,每个条目表示一个用户在特定主题上的隐式兴趣。给定输入用户tuples ,我们首先引入涉及用户u的tuples

接着,我们为每个user和topic pair生成观察值:

也就是说,我们首先抽取所有涉及用户u的tuples ,在给定用户u涉及主题i的tuples下,使用函数r来计算隐式兴趣。该函数有许多可能的形式,对于不同行为可以训练不同的权重。我们使用以下的等式做为baseline来计算隐式兴趣:

…(1)

如果i=e,为1; 否则为0. 也就是说用户u对主题i的隐式兴趣,可以通过i在所有用户u行为上的出现次数,除以所有items的出现总和来计算。我们会使用additive smoothing来对该值进行平滑。

5.1.2 SBSUM (Single Behavior-Specific User-topic Matrix SBSUM)

SBSUM和CBSUM将行为类型单独划分来生成独立的user-topic矩阵。给定一个行为类型的特征集合,我们想构建矩阵,其中每个条目表示从B中行为类型得到的隐式兴趣。

我们使用与等式(1)的相同方法,但增加了限制来过滤不在B中的行为类型:

…(2)

对于每个B,使用该等式,我们可以构建一个矩阵,它使用B中的行为类型来表示用户观察隐式反馈,可以被设置成单个行为类型,或是多个行为类型集合。因此,基于B选择,我们可以构建两个类型的特定行为user-topic矩阵(BSUM):SBSUM, CBSUM。

首先,我们为每个行为类型构建了一个user-topic矩阵,比如:creating post,resharing,commenting或+1. 每个矩阵的条目是观察值,它通过等式(2)计算,其中B是单个行为。给定为所有行为类型集合,我们生成以下M个SBSUM:

…(3)

5.1.3 CBSUM(Combined Behavior Specific User-topic Matrix)

在构建SBSUM时,我们创建了M个矩阵,每个表示单个行为类型。然而,我们也希望捕获多种行为类型组合的主题兴趣。例如,在G+中,creating post和resharing posts会生成内容并广播给所有followers,这两种行为类型可以组合在一起来表示用户的发表(publication)。

同时,commenting和+1两者表示用户对post的消费行为。将两者组合在一起可以表示关于用户消费(consumption)的主题兴趣。因此,给定行为类型集合,每个集合是B 的一个子集,我们构建了P个矩阵,每一个均表示用户的组合行为:

…(4)

5.2 step 2: 学习latent embedding space

这里我们引入了一个矩阵分解(MF)技术来构建用户的主题画像(topic profile)作为baseline方法。另外,我们引入了我们提出的方法,它将baseline算法扩展成行为因子分解。

5.2.1 baseline: MF

在构建BNUM后,我们会学习一个latent embedding space,它可以被用于补全observed user-topic matrix来获得预测的user-topic偏好。在推荐研究中,在学术界和工业界有许多方法尝试改进MF技术。这里我们使用hu[13]提出的因子分解技术。

采用[13]有一个非常特别的原因。在社交媒体平台上,对于大多数用户来说,隐式兴趣信号更容易获取。然而,许多推荐算法并没有考虑显式兴趣 vs. 隐式兴趣信号间的潜在不同。在user-item矩阵上有效的所有其它MF方法,可以被应用到我们的框架中,来使用行为因子分解(behavior factorization)构建user profiles。注意:在后续讨论中,user-topic矩阵中的”topic”与user-item中的item相似。

给定从的隐式兴趣中观察到的user-item矩阵,Hu[13]将观察集划分成两个变量:偏好、置信度。这里是一个二值变量,它表示用户u是否对item i感兴趣:

置信度表示对偏好的置信等级。它表示你对兴趣值有多肯定。它可以通过以下方式进行计算:

接着,该算法会学到一个latent embedding space,它会将每个user u和item i映射到该空间上(对应于)。为了学习该空间,算法会尝试解决以下的最优化等式:

…(5)

结果可以被用于补全user-item矩阵,它会估计一个user会喜欢一个item有多喜欢。[13]提出的算法对于隐式feedback/interest datasets工作良好。

在这一点上,我们使用等式(1)来构建user-topic矩阵,采用MF来学习一个latent embedding space。再者,我们可以通过估计用户u在所有主题上的偏好来建模任意用户u的兴趣。对于没有出现在原始user-topic matrix(用于训练该embedding space)中的任意新用户,我们仍能通过使用学到的topic embedding vectors 来将它们映射到该embedding space中。我们将在第5.3节中讨论。

5.2.2 行为因子分解模型(BF)

不同于上述介绍的矩阵因子分解模型,我们希望将用户不同的行为类型进行划分,并为每个用户对于不同的行为生成主题偏好。因此,我们不再使用对单个user-topic matrix进行因子分解,而是会对step 1生成的多个user-topic矩阵(BNUM, SBSUM, CBSUM)进行因子分解。

有一些在context-aware矩阵分解、张量分解等技术(Liu[20])上进行的早期探索,会创建多个矩阵并同时学习一个latent space。然而,这些技术不能直接用在我们的行为因子分解问题上,因为我们正构建多个user-topic矩阵,它具有相同的列(column)/主题(topic)空间,但具有不同的行(rows)/用户(users)。他们构建的矩阵对于不同的context具有不同的items,相反的我们会使用一个隐式建模方法,也会考虑上行为上下文间的关系,比如:发布行为组合和消费行为组合。

图1展示了行为因子分解(BF)方法与baseline模型对比的区别。在step 1从用户行为构建矩阵时,不再仅构建BNUM,我们也会构建两类矩阵:SBSUM和CBSUM。

在step 2中,我们将所有生成的矩阵因子分解成相同的latent embedding space。我们会学习一个latent embedding space,并将对应每个特定的行为类型的每个用户和每个item映射到该空间中。在每个矩阵中的每个条目是对该用户行为的隐式兴趣值,因此,我们可以以如下方式扩展baseline模型。

这里表示每个矩阵的偏好的置信度。给定所有特定的行为类型,我们使用等式(3)和(4)的,我们通过优化如下的等式来学习embedding space:

….(6)

通过写出在上的求和,我们使用一个与原始等式(5)相似解来求解该最优化问题,并为user-behavior和topics学习embedding space。

对比原始的user-topic矩阵,通过我们方法学到的embedding space的可能在对语义相似度的衡量上会更好,因为从之前分析(第3节),我们知道在user-topic矩阵上的观察值是从不同行为上的多种不同兴趣的混合。将这些信号相隔离可以产生一个更清晰的topic model。一个最近的paper:《how to learn generative graphical models such as LDA in social media》【31】。在该paper中,他们探索了如何将文档聚合成语料,并表示一个特定的context。由于生成式图模型和矩阵分解都是尝式从数据中学习latent space,该意图可以在两种方法上均可采用。我们的假设是,在user-behavior级别上构建矩阵,而非在user级别上;这可以帮忙我们清晰地标识跨主题的语义联合,不会增加太多的稀疏性。

5.3 step 3: 构建user profiles

最终,我们介绍了如何使用学到的latent embedding spaces来构建user profiles。如图2所示,我们介绍两种方法:

  • i) 从profile矩阵的input row vectors构建direct profile
  • ii) 通过一个回归模型学到一个权重集合,合并不同的direct profile进行构建weighted profile

对于每个user u,我们会构建。每个是一个关于用户u在特定行为类型B上的主题偏好向量。我们会构建三种类型的user profiles,对应于三种类型的input矩阵:

  • BNUP:
  • SBSUP:
  • CBSUP:

5.3.1 DPB(Direct Profile Building)

我们会使用一个用户的embedding factors(例如:在学到的latent embedding space中对于user u的向量)来生成他的完整的user profiles: 。在DPB中,input是矩阵中的observed row vectors(对于在中的任意B来说),我们会为每个B构建user profile。

给定一个用户u和B,我们可以获取embedding factor ,接着使用该embedding factor和topic embedding factors ,通过计算点乘:来生成用户u行为B的偏好列表。接着对于每个用户u,她的output user profile可以被表示成:

…(7)

特别的,给定任意B(它是的一个子集),我们使用以下的等式来生成用户的SBSUP和CBSUP:

…(8)

其中,是用户u在行为类型B上的embedding factor。

总之,在DPB中,不同的profiles通过不同的input row vectors来生成,BNUM的row vector会生成BNUP,SBSUM的row vector会生成SBSUP,CBSUM的row vectors会生成CBSUP。例如,为了为每个用户构建BNUP,我们设置,并使用所有他的已观察主题兴趣值(observed topic interest value)来生成他在该embedding space中的embedding factor 。接着为每个topic i计算,来得到他的BNUP。

…(9)

对于不在学到的embedding model中的新用户,我们仍可以使用等式(2)来生成他的row input vectors,接着将该向量投影到一个embedding factor上。

5.3.2 WPB (Weighted Profile Building)

DPB会为一个用户生成一个behavior profile(如果该用户在过往有行为)。通过将用户的行为类型相分隔,我们可以使用DPB来为用户u的行为B生成profile,但这需要用户u在行为B上具有非零的观察值。对于那些在B上没有行为的用户,会为空,这意味着一个没有该行为类型动作的user,不会有一个user profile。这在某种程度上对应于在推荐系统中的冷启动问题。

然而,我们可以通过使用在其它行为类型的user profiles来解决该问题。我们可以使用加权求和(weighted sum)将他们组合来生成一个在主题上的组合偏好向量。这对应于一个transfer learning问题。

这里,为了为用户u的行为类型B生成偏好向量,而非直接使用等式(7)的结果,我们可以使用等式(10)为在中的所有行为类型所生成的所有偏好向量进行加权求和(weighted sum):

…(10)

中不同行为类型的权重是模型级别的参数,例如:我们会为整个数据集的每个学到一个权重。因此,这些权重可以使用一个监督学习方法来从在我们的数据集中具有多种行为类型的所有用户上学到。因此,对于那些在过程历史记录中没有的用户,我们仍可以为他们构建profiles。

在我们的实现中,我们可以使用线性回归和SGD来学习这些参数。因此,WPB可以生成BNUP、SBSUP、CBSUP,具体取决于应用。在大多数内容推荐应用中,常见的信息消费行为(consumption behaviors)非常重要,我们使用用户已观察到消费行为(observed)来学习权重来构建consumption profile。

6.评估

在之前章节,我们提出了行为因子分解法,它可以学习一个强大的latent space,并为多种行为类型构建user profiles。在该实验中,我们希望验证两个假设:

  • H1: 从我们的行为因子分解方法中学到的latent embedding模型在构建user profiles比baseline MF模型要更好
  • H2: 通过从多种行为类型中组合偏好向量,我们可以提升在特定行为类型上的user profiles的覆盖度(coverage)

在乘余章节,我们首先描述了如何设置实验,例如:我们使用了什么datasets,如何评估输出的user profiles的效果。接着我们比较了行为因子模型与baseline模型。我们也比较了在构建user profiles上的我们提出的两个方法,结果表明:通过组合行为类型,可以提升高质量的用户覆盖度。

6.1 实验设置

为了评估构建user profiles的效果,我们检查了在预测用户主题兴趣的不同方法。我们将dataset划分为两部分:training set和testing set。我们使用trainingset来训练和构建user profiles,然后在testing set上比较不同模型的效果。

6.1.1 Dataset

我们的dataset包含了在2014年 5月和6月的公开的Google+ 用户行为。第3.1节描述了dataset的生成。我们会同时使用5月的数据来训练baseline和我们的MF模型。我们随机从6月的行为数据中进行20%抽样来学习5.3.2节WPB的权重。使用乘余80%行为数据来评估不同方法的效果。

输入矩阵:在我们的dataset上,我们包含了所有公开5月和6月的posts数据。有4种类型关于posts的行为数据。我们构建不同的user-behavior-topic矩阵:

  • SBSUM
  • Publication CBSUM
  • Consumption CBSUM
  • BNUM

6.1.2 评估指标

对于一个给定的行为类型,我们构建的user profile是一个关于在主题上的偏好向量。在该vector上的值会估计:用户u是否会喜欢在行为上的每个topic。这可以使用在testing set上使用等式(2)计算的隐式兴趣进行评估。

尽管在的实际值,和不需要是相同的,的一个好的user profile,主题顺序进排序,必须与我们在testing set中观察的相似。

为了比较这两个vectors的顺序,我们会将转换成两个关于在E中主题的排序列表:是由profile building方法生成的关于top N主题的排序列表,是所有观察到主题的排序列表。我们会使用如下指标进行评估:

  • Recall@N: 的top N的主题有多少出现在
  • NDCG@N:
  • AP@N:

7.讨论

7.1 潜在的应用

有许多应用可以使用我们方法构建的user profiles。由于我们将用户行为(还有不同的items集合:比如:posts, communities, users)映射到相同的embedding模型上,用户行为和items间的相似度可以用于为推荐生成排序列表。对比常用的user profiles(它不会分隔用户行为),我们的方法不仅会考虑users和items间的内容相似性,也会考虑不同推荐任务的上下文。例如,consumption profile可以用于为一个正在阅读post的用户推荐相关的posts,publication profile可以用于在一个用户创建一个post后为他推荐新朋友。

7.2 局限性和未来改进

提出的行为因子分解框架确实可以提升用户兴趣画像的效果,然而仍有局限性。其中之一是,我们的框架依赖于:用户不同的行为类型天然能反映用户的不同兴趣。在构建社交媒体的用户兴趣画像(比如G+)能运行良好,但不能泛化到其它领域上(比如:不同行为类型不能反映不同的用户兴趣)。

另外,结果表明我们的方法不能在用户非常稀疏、或者目标行为类型(尝试预测)没有数据的情况下。一个原因是,这些用户可能比其它用户具有更低的活跃度。另一个原因是,我们的方法会最优化多个矩阵,它们可能会对相同的用户丢失跨不同行为类型的相关性。为了解决这个问题,我们对使用tensor factorization技术(比如:PARAFAC)在行为矩阵上很感兴趣。我们的方法可以认为是一个tensor factorization上unfolding-based方法的扩展。

另外,我们想直接部署该框架到现实的推荐系统上,并通过在线实验来评估。

参考

https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/43807.pdf

Fayyad等在paper[1]提到过一种连续值离散化的方法:MDPLP。下面简单来看下:

1.介绍

分类学习算法通常要使用启发法(heuristics)来在多个属性值和类的组合间的可能关系空间上进行搜索。其中有一种这样的启发法(heuristic),它被使用在数据集中的分类上的选择局部最小化信息熵(比如ID3算法、C4、CART等)

机器学习中的属性可以是类别型的,也可以是连续型(数值型)。上述提到的属性选择过程假设所有的属性都是类别型的。连续型的属性在选择之前需要进行离散化(discretized),通过通过将属性的range范围进行划分成subrange范围。总体上,离散化是一个简单的逻辑条件,将数据划分成至少两个子集。

本文主要关注连续型属性的离散化。首先来看下二元离散化(binary discretization)。接着来看多区间离散化(multi-interval discretization)。

2.二元离散化

连续值属性通常在决策树生成时通过将它的值范围离散化成两个区间。对于连续型属性A,阈值为T, $ A \leq T $被分配到左分枝,$ A \gt T $被分配到右分枝。我们将该阈值T称为分割点(cut point)。该方法被用于ID3算法以及它的变种CART算法中的GID3。它可以被用于任何分类树算法,或者用来处理将连续型属性划分成二个区间的规则。尽管这里我们将它应用于离散化,在决策树生成的topdown的特定上下文也有使用。

假设在一个节点(样本集S具有N个样本)上对一个属性进行分枝。对于每个连续型属性A,我们在值的范围上选择最好的(“best”)分割点$ T_A $。样本首先通过属性A的值升序排列,在排完序序列中每个后继样本对(example pair)间的中点会作为一个潜在的分割点进行评估。这样,对于每个连续值属性,会发生N-1次评估(假设样本没有相同的属性值)。对于候选分割点T的每次评估,数据都会划分成两个集合,结果分区的分类熵(class entropy)会被计算。回忆一下,该离散化过程也会在决策树中的每个节点被执行。

样本集S通过T划分成两个子集:S1和S2 。假设存在K个类:$ C_1, …, C_k $,让$ P(C_i, S) $是S中含有类别$C_i$的样本比例。那么子集S的分类熵(class entropy)被定义成:

其中的log基数取2 。 Ent(S)用来衡量在S中的指定的分类信息量,单位为:bits。在集合S被划分成S1和S2后,为了评估生成的分类熵,我们采用它们生成的分类熵的加权平均:

定义1:对于一个样本集S,一个属性A,一个分割值T:假设$ S_1 \in S $是在样本S中的子集,它的A属性值$\leq T$,并且满足$ S_2 = S - S_1 $。分区的分类信息熵通过T索引,E(A,T;S)被定义成:

…(2)

A的二分离散化通过选择分割点$T_A$来决定,其中$E(A, T_A; S)$是所有候选分割点中的最小值。

2.1 分割点选择的讨论

选择标准(selection criterion)的主要问题之一是:它的开销相当昂贵。尽管它是多项式复杂度,它为每个属性必须评估N-1次(假设有N个不同值的样本)。因为机器学习问题通常被设计成很大的训练量,N通常很大。当对一个类别型(离散化)属性进行时,该标准(criterion)只需要对r个分区进行单次评估即可,其中r为类别的数目。通常$ r « N$。确实,像ID3这样的算法在运行连续型属性时确实会慢许多。

其它缺点是:该算法具有一个天生的缺陷,当超过两个分类时,会生成”坏(bad)”的分割点。该缺点基于一个事实:该算法尝试最小化侯选二元划分集合的加权平均熵(如方程1所示)。分割点可能因此将一个分类的样本以最小化平均熵的方式进行分割。图1展示了这种情况。分割点并不会落在边界B1或B2上的其中之一,则是会落在两边的平均熵最小的点上

这不是我们所期望的,因为它没必要将相同分类的样本分隔开,产生更大(但质量更低)的树。

然而,这些缺点不会被证明是对的。下面的理论1会展示,不管有多少分类,不管如何离散化,分割点将总是发生在两个类的边界上(见定义2, 它会对边界点有一个精准的说明)。这确实是该启发法(heuristic)的一个期待的特性,因为它展示了该启发法(heuristic)是“表现良好的(well-behaved)”。它告诉我们该启发法(heuristic)将从不选择一个在结果上(目的论:teleological)被认为是“坏”的分割(cut)。另外,该结果将帮助我们在不改变该功能的情况下提升算法的效果。

2.2 分割点总是在边界上

我们展示了属性A的值$ T_A $会最小化平均分类熵$E(A,T_A;S)$: 对于一个训练集S,必须总是在排序后样本序列不同分类的两个样本间的值。假设A(e)表示样本$ e \in S$的A值。

定义2:范围A中的值T是一个边界点,因此存在两个样本:$ e_1, e_2 \in S$具有不同的分类。比如:$A(e_1) < T < A(e_2) $,不存在着这样的样本$e’ \in S$,使得:$A(e_1) < A(e’) < A(e_2) $。

理论1:如果T能最小化E(A,T;S),那边T就是一个边界点

证明:相当长,忽略。见paper[5]

推论1 用于ID3的该算法,可用于为连续型属性发现一个二分划分,将总是在排好序的属性样本对一个边界点划分数据。

证明:跟据理论1和定义。

推论1的第一个含义是,它可用于支持在离散化时最小化熵。我们使用信息熵的启发法(heuristic),因为我们知道,它控制一些衡量离散化需要的属性。然而,本身并不能排除不希望的情况,比如,图1中的情况。推论声明,“明显坏(obviously bad)”的分割从不会被该启发法(heuristic)所喜欢。该结果可进一步支持在离散化中使用该启发法(heuristic),因为它告诉我们,该启发法(heuristic)从目的论(teleological)的角度是表现良好的。

另外,推论1可以被用于在完全不需要更改效果的情况下增加算法的效果。通过对属性A的值进行排序之后,该算法只需要检查边界点b,而非所有的N-1个侯选。注意:$ k-1 \leq b \leq N-1 $。因为常通k « N,我们会期望节省很大的计算开销。我们演示了对ID3算法的所要评估的潜在分割点的数目上有极大的加速。ID3将连续值属性划分成两个区间。算法会检查多个区间,使用该过程的一个泛化版本(比如:下一节中要讲的一个)来达到更高的加速。算法会搜索规则,而非决策树,在离散化时会花费更多的开销。评估过程的计算加速只是推论1的一个附带效果。它的语义重要性是本文关注的,因为它证明了我们的泛化相同的算法,来生成多个区间,而非两个。

3.泛化该算法

推论1也提供了对扩展该算法的支持,在单个离散化过程中来抽取多个区间,而非两个。该动机是获取更好(“better”)的树。

训练集会做一次排序,接着算法会使用递归,总是选择最好的分割点。所使用的一个原则是:避免对一个给定区间做更进一步的二元划分。事实上,只会考虑这样的边界点:让自顶向下(top-down)的区间的得到更可行(因为该算法从不会在top上提交一个”bad”分割点),并且能减小计算开销。

为了合理地定义这样的一个算法,我们需要用公式来表示这个原则(criterion),以决定对一个给定样本做限制划分。该criterion需要理论支持。期望的测试将在后续被用于验证该理由是否合理。

从树生成的角度上看,为什么多区间(multiple range)的派生版本比二元区间(binary range)有更大的优点呢?通常,“感兴趣(interesting)”的范围可以是在属性值范围内的一个内部区间。为了得到这样的一个区间,单次做二元区间划分(”binary-interval-at-a-time”)的方法将导致不必要的、并会对样本做出超出感兴趣区间范围的过多划分。例如,假设,对于在[0,40]的属性值A,子区间 $ 12 < A \leq 20$是我们感兴趣的。假设A的范围离散化成:$ (-\infty,12), [12,20), [20,25), [25,\infty) $。给定一个算法,比如GID3,它能过滤出不相关的属性值,原则上可以获得如图2(a)所示的决策树。属性选择算法决定着只有2/4的区间是相关的。在区间外的样本会被分组到图中label=S的子集。

为了选择如图2(b)中生成的决策树两个区间范围,可以只使用一个二分区间离散化算法。注意,集S没必要划分成两个子集S1和S2 。对于第一棵树,该算法有机会使用一些其它的属性对S进行划分。该选项在第二种情况下不再使用,进一步的属性选择基于更小的子集:S1和S2. 必要的,这会导至相同的排序问题,会造成不相关值问题(irrelevant valus problem)。关于GID3如何处理该问题,以及如何只有一个子集的值被分支超出了本文的范围。

3.1 分割还是不分割?

给定集合S和一个潜在的二元划分$ \pi_{T}$,它表示在集合S上对属性A的分割值T,我们需要决定是否接受这次划分。该问题天然可以公式化成一个二分决策问题:接受或者拒绝$\pi_T$。假设HT为假设函数,其中$\pi_T$决定着是否接受。也就是说,HT是分类器,它会测试A的值,而非T,接着会对样本进行分类:根据在E中的样本小于T的值,A值<T。相似的,让NT来表示表示零假设(null hypothesis):该假设会导致$\pi_T$被拒绝。NT会根据E中的类别来对所有样本进行分类,不需要检查A值。因为接受或拒绝都只是可能的动作,其中之一必然是正确的;另一个不正确。当然,没有其它办法来直接决定哪个是正确的。

假设$d_A$表示决定着接受划分$ \pi_T$,$d_R$表示拒绝。该情况中可能的决策集合是$ D= \lbrace d_A, d_R \rbrace $,我们具有待解决的一个二分决策问题。如果我们分配了一个cost给错误的决策,那么与一个决策规则(在$ {d_A, d_R} $间进行选择)相关的期望cost如下:

其中$c_{11}$和$c_{12}$表示做出正确选择的costs,而$c_{12}$和$c_{21}$表示做出错误决策的costs。这是期望贝叶斯风险(expected Bayes risk),决策规则被用于选择 $ \lbrace d_A, d_R \rbrace $的其中之一。贝叶斯决策原则(Bayes decision criterion),会调用选择决策规则来最小化期望的cost。

由于我们知道,分配给$c_{12}$和$ c_{21} $是什么值,我们会对均匀error cost分配做重排序。如果$ c_{11} = c_{22} = 0$和 $ c_{12} = c_{21} = 1$,那么最小化Bayes risk会减小一个决策规则PEC(Probalility-of-Error Criterion),它会最小化做出错误决策的概率。接着,它会通过一个简单的派生来展示Bayes决策原则来减小采用的决策规则,给定数据集S,选择假设HT,$ Prob(HT | S)$是计算假设的最大量。我们将该决策原则适用成”贝叶斯决策策略(Bayesian Decision Strategy)”。该策略有时也被称为MAP原则(maximum a posteriori),等价于PEC。

对于我们的决策问题,Bayesian decision strategy会选择$d \in D$的决策,它对应于在数据集S上具有最大概率的hypothesis:这样,如果$ Prob(HT | S) > Prob (NT |S)$,那么我们选$ d_A$。如果我们有一个方法来决策着上述两个要解决问题的概率:简单地选择hypothesis,它具有更高的概率,Bayesian决策策略会保障这是最好的策略。不幸的是,没有简单的方法来直接计算这样的概率。然而,我们应采用这样的方法:它将允许我们直接估计哪个概率更大。

3.2 MDLP(最小描述长度原则)

一个对象的最小描述长度(minimum description)被定义成所需的最小的位数,来唯一指定对象脱离于通用的所有对象。

我们会展示该决策问题,给定一个固定的样本集合,我们使用MDLP来猜测带有更高概率的hypothesis。MDLP是一个通用的原则,它的目的是,对自然界中天然的偏差进行编码,朝着更简单的理论来解释数据的相同部分。MDLP被Rissanen引入,之后被其它人使用。定义如下:

定义3:给定一个假设集合,以及一个数据集S,MDLP会调用假设HT来:$ MLength(HT) + MLength(S |HT) $是在假设集上的最小值。MLength(HT)表示对HT编码的最小可能长度,而 $ MLength(S |HT) $是对给定hypothesis编码的最小编码长度。

为了方便,我们假设长度的单位是:bits。数据的编码可以被认为是对数据点进行编码,它们是对于hypothesis HT来说“异常点(exceptions)”。如果HT能完全拟合数据,那么后一项将为0.

MDLP原则不必要要求与之前讨论的决策原则不同。它可以轻易地展示MDLP和Bayesian risk minimization strategy在理论上是相互相关的。由于篇幅原因,我们忽略了派生版本,它包含着可以包含对数据集S的hypothesis H所需要指定的bits数:$ -log_2 (Prob(H|S)) $,使用Bayes’ rule。最终获得的表达式等价于MDLP。这可以看成是采用MDLP的动机。

基于最早的争论,如果我们具有一种方法来发现真实的hypotheses的最小编码长度,那么采用MDLP来选择一个完整hypotheses的集合会导致使用最大MAP的hypothesis。接着,它等价于PEC决策原则。这意味着,选中的hypothesis将会最小化做出错误选择决策的概率。然而,在物理世界中,我们不会访问概率分布。因而,MDLP被用于对cost的估计,来在hypotheses间做比较。

3.3 应用MDLP:编码问题

现在,一个问题是编码问题(coding problem)。在我们的情况下,决策问题相当简单。完整的hypotheses包含了两个元素:{HT, NT}。我们应采用Quinlan和Rivest的公式,他们在属性选择上使用MDLP来尝试生成紧凑的决策树。在我们的情况下,该问题相当简单。

使用该公式,该问题需要解决的问题是通信问题。目标是通信一个方法(分类器),它可以允许接收器(receiver)来决定在数据集中的样本分类label。假设一个发送器(sender)具有整个训练数据样本集。而接收器具有没有该分类label的样本。sender只需要将合理的分类labeling传送给receiver。sender必须选择最短描述来指定该分类。

对Null Theory NT进行编码:在NT的情况下,sender必须简单地传递在S中的样本的类别。sender发送了N条消息,每个都是一个被编码过的类别label(其中N=$ | S | $)。为了编码在S中的样本的类别,我们必须使用一个最优化算法(比如:Huffman coding)来生成编码来优化平均编码长度。因为我们必须传递在集合S中每个样本的类别,将平均编码长度l乘以N给出了总的cost。另外,需要传递“code book”来用于解码类别。传递的code book的包含了每个类别对应的code word。因而,如果存在着K个分类,code book的长度可以通过(k * l)进行预估。注意,K是一个常数,不能随着N增长,因此,code book的cost是一个小的常数开销。

对划分HT进行编码:选中的分割点会对样本分区,必须由sender根据每两个子集中的分类编码来指定。指定分割点的开销为$log_2(N-1)$ bits,因为我们需要指定序列(分割点在之间落的地方)中N-1个样本的其中之一。

分类器HT对应于二分划分,$ \pi_T $,将集合S划分成子集:S1和S2。其中Sender必须传递分割点的一个说明书,根据S1中的类别序列,根据S2中的类别。再者,我们感兴趣的是,对S1和S2中的类别编码使最小化平均长度,如同在S中的类别编码所做的。其中$ l_1 $和$ l_2 $是对应于S1和S2各自的最小化平均编码长度(单位:bits)。传递HT的cost随着HT的数据一起:

(bits)

我们也需要为S1和S2的类别编码各自传递code books。不同于传递S的情况(k个类别),该情况我们必须通知receiver,哪个类别的子集会在两个子集S1和S2的其一中被表示,接着传递各自的code books。因为我们知道我们的划分是非平凡解(non-trivial)的,例如:$ S_1 \neq S_2 \neq \emptyset $,我们知道S1可能具有$2^k-1$个可能的k个类别的子集。使用一个长度派生版本,它可以被表示成:

是可能的划分数目,超出我们需要指定的。由于我们需要$ log_2(G_k) $ bits。注意:$ log_2(G_k) < 2 log_2(2^k-1) < 2k$.

##