没有合适的资源?快使用搜索试试~ 我知道了~
another [3]. Any subsequent measurement on the network (e.g.degree distribution, diameter, clustering coefficient, graph kernels)treats all edges equally, when a path or community in the networkmay only be an error of aggregation.Task-based network model selection addresses the latter chal-lenge by comparing multiple representations for predicting a partic-ular behavior (or context) of interest. In this context, the network isa space which structures a local predictive task (e.g. “my neighborsare most predictive of my behavior”), and model selection reportsthe best structure.Work in network model selection has typically focused on in-ferring parameters of generative models from a given network,according to some structural or spectral features (e.g. degree distri-bution, eigenvalues) [23]. However, preliminary work has extendedmodel selection to criteria on task performance with respect togenerative models for a given network [5], and methodologies rep-resenting underlying data as networks [3].We propose a task-focused network model selection methodol-ogy. Our approach constructs network models from underlying dataand uses minimum description length (MDL) criteria for selection.Our methodology measures efficiency, a general and comparablemeasure of the network’s performance of a local (i.e. node-level)predictive task of interest. This accounts for complexity of both thenetwork structure, and predictive models. Selection on efficiencyfavors parsimonious (e.g. sparse) models to avoid overfitting andcan be applied across arbitrary tasks and representations. We showstability, sensitivity, and significance testing in our methodology.9610使用以任务为中心的最小描述长度进行网络模型选择0Ivan Brugere伊利诺伊大学芝加哥分校芝加哥,伊利诺伊州ibruge2@uic.edu0Tanya Y. Berger-Wolf伊利诺伊大学芝加哥分校芝加哥,伊利诺伊州tanyabw@uic.edu0摘要0网络是几乎每个应用领域中使用的基本数据模型。在大多数情况下,关于网络定义的几个隐含或显式选择会影响底层数据到网络表示的转换,以及关于所表示的底层系统的后续问题。下游网络数据的用户甚至可能不知道这些选择或其影响。我们提出了一种以任务为中心的网络模型选择方法,解决了几个关键挑战。我们的方法从底层数据构建网络模型,并使用最小描述长度(MDL)准则进行选择。我们的方法衡量了网络在感兴趣的本地(即节点级)预测任务中的性能的效率,这是一种通用且可比较的度量。效率选择偏好简洁(例如稀疏)模型以避免过拟合,并且可以应用于任意任务和表示。我们在方法中展示了稳定性、敏感性和显著性测试。0ACM参考格式:Ivan Brugere和Tanya Y.Berger-Wolf。2018。使用以任务为中心的最小描述长度进行网络模型选择。在WWW '18Companion:2018年Web会议伴侣,2018年4月23日至27日,法国里昂。ACM,美国纽约,纽约,8页。https://doi.org/10.1145/3184558.319152501 引言0网络是几乎每个应用领域中使用的基本数据模型。在大多数情况下,关于网络定义的几个隐含或显式选择会影响底层数据到网络表示的转换,以及关于所表示的底层系统的后续问题。下游网络数据的用户甚至可能不知道这些选择或其影响。这些选择是否产生了实际预测底层系统的模型?我们能否发现更好(即更具预测性、更简单)的模型?从某些数据派生的网络通常被认为是底层系统的真实表示。这种假设引入了几个挑战。首先,这些关系可能非常依赖时间:边的聚合可能不反映任何时间点上底层系统的行为[4]。其次,关系可能是上下文相关的:从数据推断出的同一网络可以预测系统的一种行为,但不预测另一种行为[3]。当网络中的路径或社区只是聚合的错误时,对网络进行的任何后续测量(例如度分布、直径、聚类系数、图内核)都会平等对待所有边。基于任务的网络模型选择通过比较多个表示来预测特定行为(或上下文)。在这种情况下,网络是一个结构化本地预测任务(例如,“我的邻居对我的行为最具预测性”)的空间,而模型选择报告最佳结构。网络模型选择的工作通常侧重于根据某些结构或谱特征(例如度分布、特征值)从给定网络中推断生成模型的参数[23]。然而,初步工作已将模型选择扩展到与给定网络的生成模型的任务性能相关的准则[5],以及将底层数据表示为网络的方法[3]。我们提出了一种以任务为中心的网络模型选择方法。我们的方法从底层数据构建网络模型,并使用最小描述长度(MDL)准则进行选择。我们的方法衡量了网络在感兴趣的本地(即节点级)预测任务中的性能的效率,这考虑了网络结构和预测模型的复杂性。效率选择偏好简洁(例如稀疏)模型以避免过拟合,并且可以应用于任意任务和表示。我们在方法中展示了稳定性、敏感性和显著性测试。0本论文发表在知识共享署名4.0国际许可证(CC BY4.0)下。作者保留在个人和公司网站上传播作品的权利,并附上适当的归属。WWW '18Companion,2018年4月23日至27日,法国里昂,© 2018IW3C2(国际万维网会议委员会),根据知识共享CC BY 4.0许可证发布。ACM ISBN978-1-4503-5640-4/18/04。https://doi.org/10.1145/3184558.319152501.1 相关工作0我们的工作与网络结构推断[1,14]相关。这个工作领域构建了一个网络模型表示,用于传感器、在线用户轨迹或其他底层数据收集的属性。以前的工作侧重于这些网络表示作为局部预测任务的模型,这些任务在实体组上执行,例如标签推断[19]和链接预测[11,16]。在这种设置下,“好”的网络是在某种鲁棒性、成本或稳定性度量下表现良好的网络。以前的工作在不同的网络模型、单个或多个任务以及不同的任务方法[2,3]下研究了模型选择。最小描述长度(MDL)原则[21]通过以字节为单位的最小可能编码大小来衡量对象或模型的表示。这个原则被用于预测模型的模型选择,包括回归[9]和分类[18]。MDL方法还被应用于数据表示的模型选择,包括聚类、时间序列[9,12]、网络[25]和网络摘要[15]。MDL已被用于动态网络中的结构异常值和变化检测[7,22]。0跟踪:第三届大型网络学习表示国际研讨会(BigNet 2018)WWW 2018年4月23日至27日,法国里昂iiibfs…i degree bkirandom…ibfsicommunity …9620(c)在节点组样本上训练任务(b)从推断的网络查询节点组(a)输入:节点属性和标签0高活动社区0高度0网络0节点i0标签:黄色0属性:[...]d0网络推断模型0节点样本自举0编码网络模型0和任务0(d)评估0模型效率,0显著性,0鲁棒性。0图1:我们方法的高级概述。(a)给定输入:具有相关属性和标签数据的节点,可以选择提供潜在的网络结构(虚线)。我们使用网络推断模型从数据中构建多个网络(注意:模型堆叠)。(b)对于每个网络模型,对于每个节点‘i’,我们根据不同的样本方法和节点表征启发式(例如‘高度’,‘高活动性’)对节点(由节点颜色表示)及其相关属性和标签进行采样。(c)我们通过每种方法在不同的样本大小k下生成‘b’个样本,每一行是一个经过训练的任务模型(例如随机森林)来预测标签‘i’(‘黄色’),给定采样的属性数据和标签。(d)我们对来自(c)的每个任务模型集合和来自(b)的网络表示进行编码,以衡量执行任务的最高效模型,并选择该网络表示。0[7,22]。我们的方法对预测模型的集合进行编码,以及用于模型选择的底层网络表示。没有已知的工作将这两个对象都编码为模型选择。存在几种生成模型来建模属性、标签和网络结构之间的相关性,包括属性图模型(AGM)[20]和乘法属性图模型(MAG)[13]。这些模型对我们的方法是附加的,可以作为潜在模型在我们的方法中应用和评估。我们的工作与图核函数[24]和图嵌入[8]是正交的。这些方法遍历网络结构以提取路径特征,并将节点表示为低维空间中的节点,或通过共享结构特征来比较节点/图。我们将这种图遍历视为一种可能的节点查询,用于输入到局部任务,但不直接比较图或节点;我们的重点是评估固定模型在所有节点上执行局部任务的效果。01.2 贡献0我们为网络制定了一个以任务为中心的模型选择方法。 •模型选择方法:我们提出了一种广义方法,用于评估在执行特定任务时对任意数据表示的网络。 •网络效率:我们提出了一种通用的最小描述长度(MDL)效率度量,用于对网络表示和任务模型的编码进行比较,该度量在不同模型和数据集上具有可比性。 •验证和显著性:我们通过实验证明了我们的模型选择方法的稳定性、敏感性和显著性测试。02 方法0图1概述了我们的模型选择方法。在图1(a)中,我们输入了属性集A和与实体i ∈V相关联的标签集L。标签是表示某些预测任务(例如标签推断、链接预测)中感兴趣属性的一种便利符号。我们可能会给出一个网络拓扑(虚线),我们将其视为评估中的一种可能的网络模型。我们应用一系列网络推断方法生成单独的网络拓扑。在图1(b)中,对于每个网络拓扑,我们使用几种网络采样方法对属性和标签数据进行采样,以输入到监督分类/回归任务中。方框表示可以进行采样的不同节点表征启发式方法:“高度节点”、“高活跃度节点”或“社区”。节点颜色表示相对于节点i的采样方法的一个样本:绿色节点表示局部样本,橙色节点表示社区样本(两个样本中相同的节点用两种颜色表示)。紫色是高度节点的样本。蓝色表示高活跃度节点的样本(例如与最多交互、最多购买、最多评级的用户),青色表示节点的随机样本。在图1(c)中,每个网络采样方法产生长度为k的样本,并重复采样以创建每种方法的b个监督分类实例。每一行对应于在样本中训练的基于属性和标签的监督分类任务,用于预测i的标签(例如“黄色”)。最后,在图1(d)中,我们使用最小描述长度(MDL)准则对预测模型(例如SVM超平面的系数或随机森林树)和网络进行高效的字节串表示编码,并评估最佳模型。我们提出了一种解决我们感兴趣任务的通用且可解释的效率度量,并展示了在我们的模型集合上的稳定性和显著性测试。0Track: 第三届大型网络学习表示国际研讨会(BigNet 2018)WWW 2018年4月23日至27日,法国里昂96302.1 预备知识和符号表示0设V = {1 ..., i ..., n}为我们称之为“节点”的实体集合。设A = {ai}为属性向量集合,L ={li}为我们要学习的目标标签集合,其中i ∈ V。设Q: V × Z + →Vk为网络查询函数(见下面的完整定义),它产生给定大小k的节点集合S �V的查询集。设C: A × L →L为在节点子集S上训练的基于属性和标签的分类器,用于为节点i生成预测值li'。02.2 网络查询函数0在我们的方法中,我们使用一个网络查询函数在节点i上访问网络,该函数返回一个节点集合,其大小取决于网络拓扑和函数定义。为了比较不同的查询函数在相似输出下的表现,我们引入了一个有界查询大小k。有界网络查询函数Q在给定节点i和搜索大小k的输入下输出一组唯一节点:0Q(i, k) → {j1, j2, ..., jk},其中i ≠ {j1, ..., jk}(1)0一般来说,这些查询从可能的节点集中进行采样,产生对重复输入i的不同结果集样本。我们通过对节点集样本进行分布采样来测量这些函数,采用替换方式,类似于自助采样[6]。网络邻接是一种查询方法,它从子集中随机采样�N(i)k�,带有替换。广度优先搜索Qbfs(i, k,E)将邻接推广到高阶邻居,其中最远层的节点是随机选择的。对于不同的查询大小k,广度优先搜索非常适合衡量网络在查找与查询“更近”的相关节点方面的性能。虽然Q可能对底层实现的网络边集E进行采样,但我们的方法评估任何网络查询函数,不论其底层实现如何。在几何空间中,Ql2可能对从i开始的欧氏距离递增的节点进行采样。查询启发式方法也可以从属性集A中派生出来。例如,活动网络查询Qactivity-net(i, k,A)(如下所定义)可以根据非零属性的数量或其他属性函数查询点,并根据与i的某种相似性进行采样。02.2.1网络效率。我们根据最小描述长度(MDL)准则评估每个网络查询函数。我们重复采样Qr(i,k)(r代表“规则”),以构建大小为k的属性向量和标签的b个样本。我们从这些属性和标签数据中训练每个分类器C(A[S],L[S])。令Cr[i, k]为所得到的训练分类器集合:0Cr[i, k] = {C0C(A[Qr(i, k)b], L[Qr(i, k)b])} |b| (2)0令正确数(Cr[i, k])为任务分类器在测试输入Cr(αi,li)上的正确预测之和。0定义2.1.网络查询函数Qr相对于节点i的效率是每字节的正确预测数量(越高越好)。效率E是由以下最大值给出:0在整个过程中,大写字母表示集合,小写字母表示实例和索引。脚本字符(例如C)和关键字(例如bytes())表示函数,电传(例如KNN-bfs)表示模型,方括号(例如A[S])表示将集合限制为子集。0使得正确预测的最大值除以中位数编码成本的k值,这两者都是b个样本的聚合值:0E(Qr, i) = maxk0�正确数(Cr[i, k])0中值b(字节(Cr[i, k]))0�. (3)0令κi = argmaxk E(Qr,i),其中k与节点i的最大效率相关联。然后,我们对所有i求和字节(Cr[i,κi])和正确数(Cr[i,κi])以获得在从Qr中的样本训练的任务模型上的效率。我们还对Qr进行编码并测量其表0正确数(Cr) = �0i正确数(Cr[i, κi])0字节(Cr) = �0i字节(Cr[i, κi]) (4)0然后,Qr的整体效率由以下公式给出:0E(Qr) = 0字节(Cr) + 字节(Qr). (5)0编码函数Qr有利于简化模型并避免将表示过度拟合到准确性或精确性等评估标准。然而,这种编码需要仔细考虑底层表示,我们在第2.4.1节中进行了介绍。在方程式5中省略Qr的编码成本仅衡量网络查询函数在其前k个样本中训练“好”任务模型的程度。如果我们不关心底层表示的结构,比如其稀疏性,那么这是合适的。为了支持以实际单位(正确/字节)的可解释性和效率,我们避免了效率定义中各项的权重因子。然而,在实践中,这将为约束这些标准中的一个提供更大的灵活性。02.3 问题陈述0我们现在可以正式定义我们的模型选择问题,包括输入和输出:0问题1:MDL面向任务的网络推断模型选择0给定:节点集合 V ,节点属性集合 A ,节点标签集合 L,网络查询函数集合 Q = {Q r } ,其中 Q r ( i , k ) → { v j 1 , v j 2 ,... v j k } ,任务 C ,其中 C( A [ S ] , L [ S ] , � a i ) → l ′ i选择:网络查询函数 Q ′ ∈ Q 其中:Q ′ = argmax r E(Q r )0为简洁起见,我们将“模型选择”简称为选择网络表示及其相关的网络查询函数,以满足我们感兴趣的任务。集合 Q中的底层查询函数可以作为任意表示实现,可以随机采样(例如列表)。该模型选择方法可以衡量网络是否比其他非网络采样启发式方法(例如社区)等更好的模型,考虑到每个模型的表示成本。也就是说,网络是否首先是必要的。因此,我们可能会选择与网络不同的查询表示。以前的工作已经评估了网络模型选择对多个任务(例如链接预测、标签预测)以及不同的底层任务模型(例如随机森林、支持向量机)的鲁棒性[3]。问题1可以直接选择不同的底层网络模型、任务或任务模型来最大化效率。我们简化了选择标准,重点是衡量网络查询函数及其底层表示的效率,但这项工作与在更大的参数空间和模型空间上进行评估是互补的。0Track: 第三届大规模网络学习表示国际研讨会(BigNet 2018)WWW 2018,2018年4月23日至27日,法国里昂We define several networks queried by network query functions Qr .Our focus is not to propose a novel network inference model fromattribute and label data (see: [13, 20]). Instead we apply existingcommon and interpretable network models to demonstrate ourframework. The efficiency of any novel network inference modelshould be evaluated against these baselines.A network model M constructs an edge-set from node attributesand/or labels: Mj : Mj(A, L) → Ej. We use simple k-nearest neigh-bor (KNN) and Threshold (TH) models common in many domains.Given a similarity measure d(�ai, �aj) → sij and a target edgecount ρ, this measure is used to produces a pairwise attribute simi-larity space. We select edges by:•dI NT (�ai, �aj) =l min(ail, ajl )(6)Qactivity-top(i, k, sort(A), ℓ)O(ℓ)Qdegree-top(i, k, sort(E), ℓ)O(ℓ)Qcluster(i, k, cluster(E))O(|V |)Qrandom(i, k, V )O(|V |)Qbfs(i, k, E)O(|E |)Qactivity-net(i, k, sort(A), m, ℓ)O(|V | × m)degree-net i, k, sort E , m, ℓVmbytes(o) = |lz4.dumps(msgpack.dumps(o))|(7)9640我们定义了几个由网络查询函数 Q r查询的网络。我们的重点不是提出一种新的基于属性和标签数据的网络推断模型(参见:[13,20])。相反,我们应用现有的常见和可解释的网络模型来演示我们的框架。任何新的网络推断模型的效率都应该与这些基线进行评估。网络模型 M 从节点属性和/或标签构建边集:M j : M j ( A , L ) → E j。我们使用在许多领域中常见的简单的 k 近邻(KNN)和阈值(TH)模型。给定相似度度量 d (� a i , � a j ) →s ij 和目标边数 ρ ,该度量用于生成一对属性相似性空间。我们通过以下方式选择边:• k 近邻 M KNN ( A , d() , ρ ) :对于固定的 i ,选择前 � ρ02.4 网络模型0| V | � 最相似的 d (� a i , { A \ � a i }) 。在有向网络中,这会产生一个出度为 k的 k -regular 网络,其中 k = � ρ0| V | � 个。• 阈值 M TH ( A , d () , ρ ) :对于所有的 ( i , j ) ∈ V,选择最相似的前 ρ 个 d (� a i , � a j ) 。分别将这些边集表示为 EKNN 和 E TH。我们在这些网络模型上使用不同的网络稀疏度(ρ)来选择“稀疏”或“密集”模型。相似度度量在不同的应用中可能有很大的差异。在我们的背景下,属性数据是用户对项目(例如电影、音乐艺术家)的计数和数值评级。我们使用交集的总和(未归一化),它偏好更高的活动量,并且不惩罚不匹配:02.4.1编码网络和任务。表1总结了我们方法中使用的网络查询函数(方程1)及其输入。我们只定义了一小部分可能的函数,重点是可解释的函数集,有助于描述底层数据。编码成本从上到下递增。20activity-top 和 degree-top是我们定义的最简单的网络查询函数。activity-top按‘活动’对节点进行排序,即 � a i中非零属性的数量,并选择排名前 ℓ 的节点(ℓ << | V|)。通过对此列表进行随机子采样生成排序。degree-top类似地对节点度数进行排序,相对于某个输入 E。cluster 对输入边集E进行图聚类(即社区检测),将网络减少为表示社区归属的列表集合。每个节点最多与一个社区标签相关联。尽管 degree-top 和cluster都是从底层网络派生出来的,但我们只编码了减少的表示。这是有意设计的,以衡量网络是否更适合由简单的排名函数(在 O(ℓ)空间中表示)、在 O(| V |) 空间中的组合集合或在 O(| E |)空间中的边来表示。random 生成随机节点子集,以 O(| V |)空间进行编码。0为简单起见,我们仅通过下标标签来引用模型,例如 KNN s - bfs 表示稀疏 Q bfs ( E KNN) 模型。0网络查询函数编码0表1:网络查询函数的输入签名和空间复杂度。我们定义了四个由非网络结构实现的函数(上),以及三个由网络实现的函数(下)0bfs 是从种子节点 i 开始对底层边集 E进行广度优先搜索。这通过邻接表(一个列表的列表)进行编码,复杂度为 O(| E |)。degree-net 是一个自定义网络,其所有出边都指向degree-top 的前 ℓ 个节点。对于每个节点 i,我们选择 m个最相似的节点,并定义从 i 出发的出边。这是一个 KNN 图,其中k = m,并且限制在高度节点上。相对于 degree-top的额外编码成本衡量了前排个体作为所有节点的任务“示例”的专业化程度。activity-net 与 activity-top类似。为了演示我们的方法,我们使用随机森林任务模型。每个决策树被编码为一个列表的元组,表示左右分支、相关特征 ID和相关决策阈值。随机森林是这些单独树表示的列表。02.5 测量效率现在我们可以将所有网络查询函数和任务模型表示为可字节编码的对象'o'(例如列表)。因此,我们现在可以测量效率(方程5)。为了实现我们的 bytes ( o ) 函数来估计最小描述长度,我们使用 msgpack库将每个对象表示转换为字节字符串,然后使用 LZ4 压缩(类似于zip),它使用霍夫曼编码来减少表示字符串中最常见元素的成本(例如高度节点、随机森林中的频繁特征)。这两种方法仅仅是出于运行时性能的必要性而选择的。最后,我们报告压缩字节字符串的长度:02.5.1 网络查询范围。设 reach ( C r ) 为 C r的范围集合,即至少在训练 C r中的任何模型时访问过一次的节点集合。我们将 Q � r定义为仅包含范围集合中的节点的 Q r 表示。如果 Q r的底层表示是一个图,则 Q � r表示是一个诱导子图,其中边的两个节点都在范围集合中。如果 Q r表示为一个列表,则我们简单地删除不在范围集合中的元素。编码大小 bytes (Q � r ) 仅测量用于创建 C r任务模型集合的底层表示。这是一种更合适的表示成本度量方式,在其中03 https://msgpack.org/ 4https://lz4.github.io/lz4/0论文题目:第三届大规模网络学习表示国际研讨会(BigNet 2018)WWW 2018,2018年4月23日至27日,法国里昂9650数据集|V||A|标签|L|0Last.fm 20K [2] 19,990 1.2B 8 166280MovieLens [10] 138,493 20M 8 431790BeerAdvocate [17] 33,387 1.5M 8 130790表2:本文中数据集的摘要。|L|报告了8个标签集上的正节点标签的总数。0实践|reach(Cr)|<<|V|。对于我们的评估,我们始终报告E(Q�r)。03 数据集0我们在具有高维属性的三个不同在线用户活动数据集的标签预测任务上展示了我们的模型选择方法:来自BeerAdvocate的啤酒评论历史、来自Last.fm的音乐收听历史以及来自MovieLens的电影评分历史。03.1 Last.fm0Last.fm是一个专注于音乐收听、记录和推荐的社交网络。以前的研究收集了整个社交网络和相关的收听历史,将社交网络与音乐流派标签预测的替代网络模型进行了比较[2]。稀疏属性向量�ai∈A对应于艺术家播放次数的计数,其中非零元素是用户i播放特定独特艺术家的次数。Last.fm还有一个由用户声明的显式‘友谊’网络。我们将其视为另一个可能的网络模型,表示为Esocial,并将其与其他模型进行评估。我们评估网络查询函数在标签分类任务中的效率,预测用户‘i’是否是特定流派的听众。如果用户对某个艺术家至少播放了5次,那么他们是该艺术家的‘听众’。如果用户是至少5位在具有该流派标签的前1000位最常标记的艺术家中的听众,那么他们是该流派的‘听众’,由用户提供。我们选择了其中8个流派标签(例如‘dub’,‘country’,‘piano’),根据先前工作对标签信息量的指导进行选择。03.2 MovieLens0MovieLens是一个电影评论网站和推荐引擎。MovieLens数据集[10]包含138K用户对20M个数字评分(1-5星)。稀疏的非零属性值对应于用户对唯一电影的评级。我们选择了最常见的用户生成的标签数据,这些标签数据对应于用户兴趣的各种情绪、流派或其他标准(例如‘inspirational’,‘anime’,‘based on abook’)。我们根据普遍性递减选择了8个标签(即‘horror’,‘musical’,‘Disney’),并预测用户是否是该标签电影的‘观众’(类似于Last.fm的听众),使用网络查询函数采样的属性和标签。03.3 BeerAdvocate0BeerAdvocate是一个包含用户对啤酒的文本评论和数值评分的网站。每种啤酒都与一个类别相关联。0标签(例如‘AmericanPorter’,‘Hefeweizen’)。我们根据类别标签的普遍性递减选择了8个类别。我们预测用户是否是某种类别的啤酒的‘评论者’(类似于Last.fm的听众)。03.4 网络和标签稀疏性0在构建我们的数据的KNN和TH表示时,我们根据边界阈值ρ构建了‘dense’和‘sparse’模型。对于Last.fm,我们将ρ设置为|Esocial|以获得密集网络,并将ρ设置为0.5×|Esocial|以获得稀疏网络。对于BeerAdvocate和MovieLens,网络密度为0.01表示‘dense’网络,0.0025表示‘sparse’网络。然而,根据典型定义,所有这些网络仍然是‘sparse’的。三个数据集上的用户标签都是二进制的(‘this’用户是‘this’流派/类别的听众/评论者),并且是稀疏的。因此,我们使用一个标签‘oracle’,只提供正标签分类问题。这使我们能够评估区分听众等而不是学习空标签分类器,其中标签多数始终是一个良好的基线。表2(|L|列)报告了所有8个标签集上非零标签的数量。这是进行评估的节点总数。因此,每个网络查询函数实例化的任务模型总数为b×|K|×|L|。每个本地任务模型可以独立评估,使我们能够任意扩展。03.5 验证和测试0根据Brugere等人的方法,对于这三个数据集,我们将数据分成时间上连续的'验证'、'训练'和'测试'分区,每个数据集的大约1/3。训练是在中间的1/3,验证是前一段,测试是后一段。模型选择是在验证上进行的,然后在测试上评估该模型。04 评估0在这个评估中,我们展示了我们采样策略的稳定模型排名,以及模型的显著性测试和对噪声的敏感性。04.1 自举和排名稳定性0我们对b=20个样本的不同大小K=[25, 50, ...150]进行了方法评估,以评估给定标签上的节点i。我们现在测试了我们选择的采样参数在b和分区之间的稳定性。图2(左)报告了Cr[i,k]中b个分类器的任务编码成本的变异系数(µ/σ)。对于Last.fm上的social-bfs模型,这些值较小,而对于social-random模型,这些值较大。这些分布的中位数在b=20时估计了b=100时的中位数,误差较小(≤0.02),经过验证的模型选择。图2(右)报告了测试和验证分区之间的效率差异。∆efficiency>0.004(或增加250字节/正确)的模型都是MovieLens上的bfs模型,这可能是效率的合理变化。这表明我们的测量方法对于估计k的编码成本是稳健的,效率在分区之间是稳定的。0Track: 第三届大型网络学习表示国际研讨会(BigNet 2018)WWW 2018,2018年4月23-27日,法国里昂9660图2:(左)对于特定的Cr[i, k]分类实例集合,对Last.fmsocial的b=20个样本的变异系数(µ/σ)分布。这估计了b=100个样本的中位数,误差较小(≤0.02)。(右)验证和测试分区之间的效率变化:E(Qr, test) - E(Qr,validation)。0τ, E(Qr), 验证 vs. 测试 Last.fmMovieLens BeerAdvocate0τ 0.89 0.61 0.820p-值1e-8 5e-4 3e-60τ, E(Qr) vs. correct (Cr)(验证)0τ 0.73 0.38 0.700p-值3e-6 0.03 7e-50表3:(顶部)验证与测试分区模型效率之间的Kendall'stau等级相关系数。(底部)效率与正确预测之间的τ排名相关性。0我们测试了E(Qr)的稳定性及其与正确预测的相关性。表3(顶部)报告了衡量模型'效率'排名之间的Kendall'stau等级相关统计量。这进一步显示了验证和测试分区之间模型的稳定性。相比之下,表3(底部)报告了根据效率和正确预测对模型进行排名的τ。在同一分区内,这种排名相关性低于跨分区的效率排名相关性。这意味着效率在绝对误差和相对排名上非常稳定,效率排名不仅仅是正确预测的替代品。如果是这样的话,我们就不需要对模型进行编码。这些测量指标的排名也不是完全不相关的。04.2 效率特征0我们对效率的定义产生了可解释的特征,可以描述模型并比较数据集。首先,我们通过计算模型编码成本与编码模型和任务模型集合的总成本之比来比较模型和任务编码成本。其次,回想一下,在效率定义中,我们选择每个节点i的最高效κi,其中在我们的评估中κi≤150。这给出了0图3:所有κ i 的均值mean i (κi)与模型成本与总编码成本的比率bytes (Q r)/(bytes (Q r) + bytes(C r))。按网络查询函数着色,按数据集标记。0模型的灵活性允许在每个i的查询函数中更深入地搜索。具有较高κ i的节点可能更难分类,因为任务编码通常随着更多的属性向量实例而变得更昂贵。图3比较了模型和总编码成本的比率(x轴)与所有κ i的均值(y轴)。根据表1,模型大致按照从左到右的顺序排列。所有非网络模型(activity-top、degree-top、cluster、random)与它们的任务模型相比都相对廉价,但是其中几个也选择了较高的κi。相反,degree-net和activity-net模型由于编码一个固定的m >max(K)而持续变得更昂贵,以便在每个值k处进行采样。所有“排序”模型(网络和非网络)在较低的κ i上最有效。这可能表明这些排序节点相对于每个实例更具信息量,并且每个额外的实例合并到任务模型中的成本更高。最后,bfs的编码成本比率在底层拓扑的reach上具有很高的方差(第2.5.1节)。04.3模型选择0我们现在专注于从验证分区的效率排名中选择模型。我们已经展示了在验证和测试分区之间的效率排名具有很高的稳定性,但是正确预测和效率之间的相关性较低(表3)。因此,在这个评估中,我们展示了我们可以使用效率选择标准来恢复相对于正确预测而言在测试中排名最佳的模型(Qbest)。表4的最左列显示了在验证中按照效率排名的三个最高排名模型(Qselect)。比率报告了所选模型(在测试中评估)在效率、总编码大小和正确预测方面的相对性能。第二列-效率比率-不是单调递减的,因为按照效率排名的模型在测试中可能与验证中不同(表3)。通过效率选择显示了编码成本和预测性能之间的直观权衡。对于Last.fm,social - bfs模型表现最佳,但是廉价的social -cluster模型也是一种选择。这与之前的结果一致。0Track: 第三届大型网络学习表示国际研讨会(BigNet 2018)WWW 2018,2018年4月23日至27日,法国里昂In order to compare models with respect to a particular dataset, wemeasure the significance of each model relative to the efficiencyover the complete set of models.We compare the median difference of efficiency of Qr to all othermodels against the median pairwise difference of all model
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 基于嵌入式ARMLinux的播放器的设计与实现 word格式.doc
- 经典:大学答辩通过_基于ARM微处理器的嵌入式指纹识别系统设计.pdf
- 嵌入式系统课程设计.doc
- 基于飞思卡尔控制器的智能寻迹车设计ARM基础课程课程设计.doc
- 下载基于ARM7的压电陶瓷换能器导纳圆测量仪的研制PDF格式可编辑.pdf
- 课程设计基于ARM的嵌入式家居监控系统的研究与设计.doc
- 论文基于嵌入式ARM的图像采集处理系统设计.doc
- 嵌入式基于ARM9的中断驱动程序设计—课程设计.doc
- 在Linux系统下基于ARM嵌入式的俄罗斯方块.doc
- STK-MirrorStore Product Release Notes(96130)-44
- STK-MirrorStore Storage Connectivity Guide for StorageTek Disk A
- 龙虾养殖远程监控系统的设计与实现数据采集上位-机软件模块-本科毕业设计.doc
- 龙虾养殖远程监控系统的设计与实现数据采集上位-机软件模块-.doc
- 龙虾养殖远程监控系统的设计与实现数据采集上位-机软件模块-本科生毕业论文.doc
- 麻阳风貌展示网站的设计与实现毕业论文.pdf
- 高速走丝气中电火花线切割精加工编程设计.doc
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功