# 介绍

CF的最流行方法是itemCF。它可以提供高质量的top-k结果。它的主要思想是：计算一个similarity matrix，相应的entries对应于pairwise item相似度（Person相关系数是一种流行选择）。为active users从头到尾计算推荐开销很大，因此，CF-based推荐通常会预计算好item-wise相似度，并以一种可快速检索的方式存储它们。根据该方法，预测active user ($u_i$)在item ($v_j$)上的得分的任务包含了以下steps：

• 1.为$v_j$寻找N个最相似的items（被$u_i$评分过），这被称为$v_j$$u_i$ profile中的N个最近邻。
• 2.基于在这N个items上的用户评分，通过相似度计算一个加权平均

• (1) 我们需要处理：每个candidate item的聚合得分必须通过来自一个不同的lists集合(set)的entries来决定。这是因为：在一个给定user profile中，每个candidate item的N个最相似items可能不同
• (2) 加权平均并不是一个单调聚合函数（monotone aggregate function），该特性会在经典top-k算法中常使用. 在top-k算法中有一些工作是使用非单调聚合函数的[10,18,21]，据我们所知，在top-k问题上还没有工作是使用非单调聚合函数来解决lists的多个集合的组合。

• (i) 数据层（Data layer）: 包含了user/item rating matrix
• (ii) 中间层（Intermediate layer）: 由item-item matrix组成，需要让similarity matrix时刻保持最新
• (iii) 应用层（Application layer）: 在中间层数据之上运行的高效运行topk算法。该层会使用相似度阀值(通过cost-based最优化得到)来调用probe操作，并通过explore操作寻找top-k items

top-k算法可以独立于中间层（intermediate layer），并可以访问中间层最新的数据结构。我们提出了一个two-phase top-k算法。在第一阶段，我们会基于相似度值计算一个阀值。该阀值以这样的方式进行寻找：最大化（最小化）相似度值更大（更小）的items的概率，接着该阀值会介于items的N个最近邻之间。在第一phase后，相似度矩阵的大部分会被过滤，size问题会极大缩减。第二个phase会使用剩下的值来计算要预测的ratings。我们会定义一个目标函数，它是两个phases的期望cost的一个上限，会寻找关于threhold的最优值来最小化该cost。我们会使用概率分布来建模相似度矩阵，以便进行概率分析。我们提出了一种高效算法来寻找top-k推荐。我们的贡献如下：

• 1.为itemCF提出了一种分层系统。
• 2.提出了两种naive算法，作为baseline来校准算法效果。
• 3.我们展示了基于TA/NRA算法扩展的方法
• 4.为itemCF设计了一种新的top-k算法
• 5.根据运行时间和top-k结果质量来评估算法

# 2.相关工作

ItemCF和可扩展性：User-CF算法会基于N个最近邻用户(对该item评过分)来预测未知评分. 它需要计算和维护一个n x n的user-user相似度矩阵。用户数n通常大于items数m。Item-CF可以克服这个缺限。除了对可扩展性改进外，它会寻找pairwise相似度来产生更好的accuracy。在ItemCF中，一个active user在一个candidate item上的rating会基于与该用户在该candidate item相似的N个items上的rating进行预测。

top-K算法：topK算法被广泛研究。大多数相关工作构建在经典的TA/NRA算法之上。这些算法假设有一个单调聚合函数，以及一个关于多个列表的集合，在这之上执行聚合是事先知道的。对比这些算法，在我们的问题中，面临着两个主要挑战：

• i) 我们的聚合函数不是单调的(monotone)
• ii) 列表集合中被聚合的值是不固定的，可能会随着item间相互变化

# 3.先决条件与Naive算法

• R：稀疏的$n \times m$矩阵
• $r_{ij}$：为entry（表示在第i个user上对第j个item的评分(rating)），值采用$\lbrace 1, 2, \cdots, C \rbrace, C>1$来表示

• $u_i$：表示第i个user(row)。注意，从行为角度看，我们可以使用row $u_i$表示第i个user（列也如此）
• $v_j$：表示第j个item(column)
• $r \in u_i$：表示一个在user $u_i$的row上的已存在评分（existing rating）
• $\hat{r}_{ij}$：来做为active user $u_i$在一个candidate item $v_j$上的未知评分(unknown rating)的预测值。
• $\mu_i$：作为被$u_i$评分过的items数目
• $\mu$：表示被任意user评分过的items平均数目

…(1)

## 3.1 Naive-1算法

• 1.使用等式(1)为每个单独的candidate item $v_j$预测score

• 2.一旦每个item的score在前一步被计算，寻找具有最高scores的k个items的时间复杂度为$O(m logk)$

• (i) 探测(Probe)：探测每个candidate item，以便寻找在user profile中的最相似的N个items。
• (ii) 探索(Explore)：探索关于candidate items的list，并计算它们的scores，接着寻找具有最高scores的top-k items。

step (ii)是必要的，以便寻找到具有最好得分的k个items。对于任意item，决定它的score需要我们知道与它最相似的N个items（由step(i)得到）。

probe阶段涉及到$O(m\mu_i logN)$个操作，而explore阶段需要$O(m(logk + N)))$个操作。实际上，N的值通常为30或更小。另外，logk通常不超过5, 主要原因是我们不希望用户被太多的推荐所淹没。在probe开销中$\mu_i$因子的存在，表明：Naive1算法的probe部分的开销占支配地位。例如，在MovieLens数据集中，有100w个ratings，$\mu_i$的平均值为165. 而在Netflix数据集中，100M的ratings、500k users，每个user的ratings平均数目为200.

## 3.2 Naive-2算法

$L_i \in L$表示与item $v_i$相关的list。

• $L_i$的elements：是形如(item_pointer, similarity)的pairs
• lists以非增的相似度(与$v_i$)进行排序；
• item_pointer：是一个指向item所在的实际内存位置的指针，或者简化为item id。所使用的pointers在ratings matrix R以及相似列表L间的具有一个统一的items表示。
• $L_{ij}$：表示list $L_i$的第i个entry。$L_{ij}$的similarity表示对于$v_i$的第j个最相似item。

• 1.标记由$u_i$评分的所有$\mu_i$个items，时间复杂度为$O(\mu_i)$
• 2.对于每个candidate item $v_j$，从该list的头部头取$L_j$，直到发现N个已标记items。
• 3.计算聚合得分，并发现具有最高得分的k个items，时间复杂度为$O(m log k)$

。。。

# 4.经典的top-k算法

• (i) 这种算法可以以有序方式访问L的列，对应于$u_i$评过分的items
• (ii) 这种算法可以访问L的列，对应于candidate items

# 5. two-phase算法

## 5.1 two-phase算法

$LP_{ij}.prob$值可以通过对具有一个合适分布的similarity matrix建模来估计，后续会介绍。当我们使用一个分布来建模similarity matrix时，不需要提供prob values。作为替代，threshold可以被直接转化成一个相似度threshold。出于简洁性，我们假设给定这样的概率。注意：LP的elements包含的similarity值越高，prob值越低。因此，保持LP的列以similarities的非递增顺序进行排序，等同于保持以prob值的非递减顺序进行排序。

# 3

## 3.1 相似度选择

• cosine-based
• Conditional Probality-based

…(2)

# 5.实验评估

## 5.2 网络的设计

• 卷积层(conv layers)具有的size为：48, 64和128. 它们具有一个kernel size: 5x5，padding size：2。
• pooling layers的window size为2x2。
• 第一个和第三个pooling layers，还有第一个conv layer的stride为2.
• 该网络有一个size=3072的fully connected layer，还有一个二级的fully connected layer(分类器)具有output size=372.

# 一、介绍

• 引入通过label partitioning，在一个base scorer上进行加速的概念
• 对于输入划分(input partitioning)，我们提供了一个算法来优化期望的预测（precision@K）
• 对于标签分配（label assignment），我们提供了一个算法来优化期望的预测（precision@K）
• 应用在现实世界中的海量数据集，来展示该方法

# 3.Label Partitioning

• (i)输入分区（input partititoner）: 对于一个给定的样本，将它映射到输入空间的一或多个分区上
• (ii)标签分配（label assignment）: 它会为每个分区分配labels的一个子集

• 1.给定一个测试输入x，input partitioner会将x映射到partitions的某一个集合中： $p=g(x)$
•  2.我们检索每个被分配到分区 $p_j$上的标签集合(label sets)：$$L = \bigcup_{j=1}^{ p } \mathscr{L}{p_j} $，其中$ \mathscr{L}{p_j} \subseteq D$$是分配给分区 $p_j$的标签子集。
• 3.使用label scorer函数$f(x,y)$对满足$y \in L$的labels进行打分，并对它们进行排序来产生我们最终的结果

## 3.1 输入分区（Input Partitioner）

• 一个标签打分函数（label scorer）：$f(x,y)$
• 一个训练集：$(x_i,y_i), i=\lbrace 1,…,m \rbrace$，（注：x为input，y为label）
• 之前定义的label集合D

accuracy的measure（比如：precision@k）为：

• 在一个分区里，相关的标签不在该集合中
• 原始的label scorer在排第一位的分值就低

• 对于共享着高度相关标签的样本，应被映射到相同的分区上
• 当学习一个partitioner时，对于label scorer表现好的样本，应被优先(prioritized)处理

## 3.2 Label Assignment

• 训练集$(x_i,y_i), i=1,…,m$，label set为：D
• input partitioner: g(x)，使用之前的方式构建
• 线性时间label scorer: f(x,y)

• $R_{t,i}$是对于样本t的label i的rank分值：
• $R_{t,y_t}$是样本t的true label的rank分值

…(1)

…(2)

…(3)

• (1) true label必须被分配给该分区
• (2) true label必须是所有被分配labels上排序分值最高的

• (i) 如果训练样本t在原始的label scorer上标记不正确，但由于高度不相关的label不会被分配到该分区上，会被label partitioner正确标注
• (ii) 原始的label scorer可以正确标注样本，但由于相关的label没有被分配到该分区上，会被label partitioner标注不正确

…(4)

$\alpha$的值不再离散（discrete），我们不会使用等式（3)的约束，但在训练后会对连续值$\alpha_{i}$做排序，会采用最大的C label作为分区的成员。

…(5)

…(6)

…(7)

…(8)

…(9)

…(10)

…【略】

# 5.结论

## 参考

Label Partitioning For Sublinear Ranking

# 一、要不要one-hot？

I do not know what you mean by vector. xgboost treat every input feature as numerical, with support for missing values and sparsity. The decision is at the user

So if you want ordered variables, you can transform the variables into numerical levels(say age). Or if you prefer treat it as categorical variable, do one hot encoding.

One-hot encoding could be helpful when the number of categories are small( in level of 10 to 100). In such case one-hot encoding can discover interesting interactions like (gender=male) AND (job = teacher).

While ordering them makes it harder to be discovered(need two split on job). However, indeed there is not a unified way handling categorical features in trees, and usually what tree was really good at was ordered continuous features anyway..

• 1.对于类别有序的类别型变量，比如age等，当成数值型变量处理可以的。对于非类别有序的类别型变量，推荐one-hot。但是one-hot会增加内存开销以及训练时间开销。
• 2.类别型变量在范围较小时（tqchen给出的是[10,100]范围内）推荐使用