中国斜学我术大草 University of Science and Technology of China QuickScorer:a Fast Algorithm to Rank Documents with Additive Ensembles of Regression Trees Claudio Lucchese,Franco Maria Nardini,Salvatore Orlando,Raffaele Perego,... 学号：SA18006079 报告人：魏晓东 育创 天寰 辰 宇 题 才府
QuickScorer: a Fast Algorithm to Rank Documents with Additive Ensembles of Regression Trees 学号: SA18006079 报告人: 魏晓东 Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego,…
中国斜学我术大草 University of Science and Technology of China 文章背景： 2015年SIGIR(Information Retrieval)最佳论文奖 截至19年5月20日，google scholari引用率39次 Claudio Lucchese,Associate Professor,Ca'Foscari University of Venice,Italy 数据挖掘， 340 255 育創 170 85 下 學 2007200820092010201120122013201420152016201720182019 0 题 才
文章背景: 2015年 SIGIR (Information Retrieval)最佳论文奖 截至19年5月20日,google scholar引用率39次 作者:Claudio Lucchese,Associate Professor, Ca' Foscari University of Venice,Italy 数据挖掘
中国斜学我术大草 University of Science and Technology of China 文章结构： 背景与问题 相关工作 且录 QuickScorer?算法 实验结果 总结 育创 天 寰 辰 宇 英學 题 才府
文章结构 : 目录 背景与问题 相关工作 QuickScorer算法 实验结果 总结
中国斜学我术大草 University of Science and Technology of China 背景介纽 1.Learning to Rank(LtR):机器学习排序.在IR系统中，给定(Q,D),通过机器学 习的方式，度量查询和候选文档集合之间的相似度(Score)并进行排序过程 2.排序器中Scorer)原理：Gradient-BoostedRegression Trees(GBRT),Lambda- MART(-MART).都属于基于多颗回归树的集成模型.利用均方误差的负梯 度在当前模型的值作为残差的近似值，从而拟合一个回归树. 3.Scorer模型规模：模型中树的个数：数千，特征数量：数百，叶节点个数：数十. 在每颗树T=(N,L)中，中间node(N)存储特征id,门限等，leaves(L)存储Score. 育剑 TI-I 寰 s(x)= ∑ wh·eh(x).val 感 宇 h=0 题 才府
背景介绍: 1.Learning to Rank(LtR):机器学习排序 . 在IR系统中,给定(Q,D),通过机器学 习的方式,度量查询和候选文档集合之间的相似度(Score)并进行排序过程. 2.排序器中Scorer原理: Gradient-BoostedRegression Trees(GBRT) , LambdaMART(λ-MART) .都属于基于多颗回归树的集成模型.利用均方误差的负梯 度在当前模型的值作为残差的近似值，从而拟合一个回归树. 3.Scorer模型规模:模型中树的个数:数千, 特征数量:数百 ,叶节点个数:数十. 在每颗树T= (N,L)中,中间node(N)存储特征id,门限等,leaves(L)存储Score
中国斜学我术大草 University of Science and Technology of China 存在的问题： 1.树的查询过程只有判断当前节点才能知道下一节点指向，导致程序运行 的控制冲突(control hazard).代码效率依赖于分支预测率. 2.Scoreri过程中空间时间占用都低，Cache命中率低.在模型中存在数千颗 树，而每一颗树规模较小，Scorer过程中依次遍历每一颗树查询得分，导致 Cache命中率低. QS算法 1.基于数据结构布置和内存访问模式设计的可感知cache,编码控制flow达 到了非常低的分支误预测率. 育创 2.基于bt位的回归树，通过逻辑与运算同时遍历多棵树 辰 下 宇 英學 题 才府
存在的问题: 1.树的查询过程只有判断当前节点才能知道下一节点指向,导致程序运行 的控制冲突(control hazard). 代码效率依赖于分支预测率. 2.Scorer过程中空间时间占用都低,Cache命中率低. 在模型中存在数千颗 树,而每一颗树规模较小,Scorer过程中依次遍历每一颗树查询得分,导致 Cache命中率低. QS算法: 1.基于数据结构布置和内存访问模式设计的可感知cache,编码控制flow达 到了非常低的分支误预测率. 2.基于bit位的回归树,通过逻辑与运算同时遍历多棵树
中国斜学我术大草 University of Science and Technology of China 相关工作： 1.IF-THEN-ELSE结构：将决策树模型转化为这种结构，可以用C++实现.这种 存储结构更有效率.这种方法对于小的特征集合有效但仍然存在控制灾难 2.PRED算法：重新设计计算过程，使得当前节点的判断结构能直接作为下 一节点的index,固定的重复d步之后得到Score,将control hazard转化为data hazard.但存在数据依赖性，存储访问模式的设计没有变化，持续d步不能提 前终止等问题 育創 3.VPRED:算法：通过交叉评估小量的文档集，达到比PRED更快的效率和更 天 低的data hazards. 寰 辰 宇 英學 题 才府
相关工作: 1.IF-THEN-ELSE结构 : 将决策树模型转化为这种结构,可以用C++实现.这种 存储结构更有效率.这种方法对于小的特征集合有效但仍然存在控制灾难. 2.PRED算法 : 重新设计计算过程,使得当前节点的判断结构能直接作为下 一节点的index,固定的重复d步之后得到Score ,将control hazard转化为data hazard.但存在数据依赖性,存储访问模式的设计没有变化,持续d步不能提 前终止等问题. 3.VPRED算法 : 通过交叉评估小量的文档集,达到比PRED更快的效率和更 低的data hazards
中国斜学我术大学 University of Science and Technology of China QuickScorer算法-Step1:基于bt向量的树遍历 1.定义： 001111 ①输入的查询特征向量：X Vh=111111A 棵树：Th=(Nh,Lh). 011111 110011 001111A 011111A ③通过X在Th中遍历目标得到exit leafi记为eh ④搜索过程中仍然可能包含eh的集合ch中 10111 111101 111101= 001101 的所有叶节点被记作候选退出叶 (Candidate exit leaf) ⑤X在树中遍历的所有节点中，判断为正确 的节点被记为True Node,判断为错误的节 True node False node Candidate exit leaf 点记为False Node 育创 2.基本过程： 天寰 ①初始化ch=Lh,当前节点判断为正确，则进入左子树，否则进入右子树. 下宇 2 树的遍历从根节点开始，如果当前节点为FalseNode,则从ch中删除左子树驿有？ 的叶子节点，如果是TrueNode,则删除右子树的所有叶子节点， 擅才府 3 当对所有节点遍历完成，则得到最小的包含eh的集合ch:
QuickScorer算法 –- Step1:基于bit向量的树遍历 1.定义: ① 输入的查询特征向量:X ② 一棵树:𝑇ℎ = 𝑁ℎ, 𝐿ℎ . ③ 通过X在𝑇ℎ中遍历目标得到exit leaf记为𝑒h ④ 搜索过程中仍然可能包含𝑒h的集合ch中 的所有叶节点被记作候选退出叶 (Candidate exit leaf) ⑤ X在树中遍历的所有节点中,判断为正确 的节点被记为True Node,判断为错误的节 点记为False Node 2.基本过程: ① 初始化𝑐ℎ = 𝐿ℎ,当前节点判断为正确,则进入左子树,否则进入右子树. ② 树的遍历从根节点开始,如果当前节点为FalseNode,则从𝑐ℎ中删除左子树下所有 的叶子节点,如果是TrueNode,则删除右子树的所有叶子节点. ③ 当对所有节点遍历完成,则得到最小的包含𝑒ℎ的集合𝑐ℎ
中国斜学我术大学 University of Science and Technology of China QuickScorer算法-Step1:基于bt向量的树遍历 3.进一步提升： ①使用FindFalse算法，直接通过特征向量X, 得到所有中间节点中不满足门限的节点 001111 被称为FalseNode,由于树的结构是左子树 Vh=111111 保存判断正确的数据，所以从ch可以删除 011111 110011 001111Λ 011111A 所有FalseNode中左子树的叶节点 110111 111101 111101 001101 ②对每一个中间节点预设一个和节点数目 相等长度的特征向量，用一个V代替所有 的ch,1表示当前位置的叶节点属于ch.最 终的eh为Vh中最左端为1的bit对应的叶节 True node False node Candidate exit leaf 点.此外V的计算过程可以表述为所有 FaleNodeX对应的向量的逻辑气结果 英 才府 题
QuickScorer算法 –- Step1:基于bit向量的树遍历 3.进一步提升: ① 使用FindFalse算法,直接通过特征向量X, 得到所有中间节点中不满足门限的节点 被称为FalseNode,由于树的结构是左子树 保存判断正确的数据,所以从ch可以删除 所有FalseNode中左子树的叶节点 ② 对每一个中间节点预设一个和节点数目 相等长度的特征向量,用一个𝑉ℎ代替所有 的ch,1表示当前位置的叶节点属于ch.最 终的𝑒h为𝑉ℎ中最左端为1的bit对应的叶节 点．此外𝑉ℎ的计算过程可以表述为所有 FalseNode对应的向量的逻辑与结果．
中国斜学我术大学 University of Science and Technology of China QuickScorer算法-Step2.·完整的QS算法 Algorithm 2:The QUICKSCORER Algorithm Input .x:input feature vector .T:ensemble of binary decision trees,with wo,...,WT1:weights,one per tree 特点： thresholds:sorted sublists of thresholds,one sublist per feature ①将一颗颗树的遍历转化为对特征向量X tree_ids:tree's ids,one per threshold bitvectors:node bitvectors,one per threshold 中每一维度的遍历使得模型能够同时遍 offsets:offsets of the blocks of triples v:result bitvectors,one per each tree 历所有子树.提高Cache命中率. leaves:output values,one per each tree leaf Output: ·Final score of x QUICKSCORER(x,T刀： 2 寻找所有的>门限的FalseNode节点，用 foreach h E0,1,...,IT-1 do Lv[hJ←11..11 逻辑与运算得到Vh代替候选退出叶Ch.运 foreach k E0,1,...,F-1 do IStep① 算速度快. i←offsets[k] cnd←-offsets[k+1] while x[k>thresholds[i]do h←-tree_ida[] 每一颗树的V中最左边为1的叶节点为 v[h]v[h]A bitvectors[i] i仁i+1 eh,用该eh对应的score*该树weight与德 10 ifi≥end then 11 break score相加得到最终的score. 天寰 感 12 score←-0 下宇 foreach hE0,1,...,T]-1 do /Step② jindex of leftmost bit set to 1 of v[h] 英 15 lh·lLh+j score←score+wh·leaves[0 题 才府 17 return score
QuickScorer算法 –- Step2:完整的QS算法 特点: ① 将一颗颗树的遍历转化为对特征向量X 中每一维度的遍历.使得模型能够同时遍 历所有子树.提高Cache命中率. ② 寻找所有的>门限的FalseNode节点,用 逻辑与运算得到𝑉ℎ代替候选退出叶𝐶ℎ.运 算速度快. ③ 每一颗树的𝑉ℎ中最左边为1的叶节点为 𝑒ℎ,用该𝑒ℎ对应的score*该树weight与总 score相加得到最终的score
中国斜学我术大学 University of Science and Technology of China QuickScorer算法-Step3:存储结构 特点 thresholds ①将所有子树的组织结构，分解为 tree_ids thresholds,tree_ids,bitvectors三个 部分的数组表示每个数组分为F列 bitvectors 个块，第i块是特征集合「中第ⅰ特征 在所有子树中对应节点的thresholds, offsets tree_ids,bitvectors等.不保留树的左 刀+1 右子树结构，而是特征的顺序为序 um.leave 2 Offset?数组存储每个特征对应的块 oum.leaves 区间地址 leaves um小eaves X num.tnes V数组长度为num.leaves*num.trees, 表示每棵树的Vh: Data structure Marimum Size (bytes Data access modes 4 Leaves存储每棵树从左向右的有 thresholds ·Λ·sizeof(f1oat】 叶节点的值. 天寰 tree_ids T ,∧·sizeof(uint) bitvectors T ·∧·B 1.Sequential (R) ⑤ 每个数组的空间大小，存储形式都可 offsets lF·sizeof(uint) 以估算，消除了左右子树的空间指向 v T·B Random (R/W) 结构减小控制风险(control hazards). 2.Sequential(R) leaves ·Λ·sizeof(double 2.Sc网.Sparse (R 达到了非常低的分支误预测率付
QuickScorer算法 –- Step3:存储结构 特点: ① 将所有子树的组织结构,分解为 thresholds, tree_ids, bitvectors三个 部分的数组表示.每个数组分为|𝐹| 个块,第 i 块是特征集合F中第 i 特征 在所有子树中对应节点的thresholds, tree_ids, bitvectors等.不保留树的左 右子树结构,而是特征的顺序为序 ② Offset数组存储每个特征对应的块 区间地址. ③ V数组长度为num.leaves*num.trees, 表示每棵树的𝑉ℎ. ④ Leaves存储每棵树从左向右的所有 叶节点的值. ⑤ 每个数组的空间大小,存储形式都可 以估算,消除了左右子树的空间指向 结构减小控制风险(control hazards). 达到了非常低的分支误预测率