d0evi1 Reading time ~2 minutes

hinton在《Dynamic Routing Between Capsules》中提出了“dynamic routing”的概念。我们来看下这篇paper：

abstract

一个capsule是一组neurons，它的activity vector表示了一个特定类型的实体(entity)（比如：一个object或一个object part）的实例参数()。我们使用activity vector的长度(length)来表示实体存在的概率，使用它的方向(orientation)表示实体参数。在一个层级上的Active capsules通过转移矩阵为高级capsules的实例参数做出预测。当多个预测达到一致时，一个更高级别的capsule会变成active态。我们会展示：当训练完后，多层capsule系统会在MNIST上达到state-of-art的效果，它在识别高度重叠的数字上要比CNN要好。为了达到这样的结果，我们使用了一个迭代式routing-by-agreement机制：一个更低层级的capsule会偏向于将它的output发送到更高层级的capsules上，它的activity vectors会与来自低层级capsule的预测做一个大的点积。

1.介绍

人类视觉会通过使用一个关于注视点(fixation points)的细致判别序列，忽略掉不相关细节，来确保只有一小部分的光学阵列（optic array）在最高分辨率上被处理。内省（Introspection）对于理解以下情况效果很差：关于某个场景的知识有多少是来自该注视点序列，以及我们从单个fixation能得到多少知识。但在本paper中，我们将假设，比起单个已被识别的目标和它的属性，单个fixation会带给我们更多。我们假设，我们的multi-layer可视化系统会在每个fixation上创建一个类parse tree结构，我们会忽略：这些单个fixation parse trees是如何协调的。

parse trees通常会通过动态内存分配即时构建。然而，根据【hinton 2000】，我们假设：对于单个fixation，一个parse tree可以从一个确定的multi-layer神经网络（比如： 雕塑从一块岩石中中雕刻出）中雕刻出。每个layer将被划分成许多被称为“capsules”的neurons小分组，在parse tree中每个node会对应一个active capsule。通过使用一个迭代路由过程（iterative routing process），每个active capsule会选择在layer中的一个capsule，作为它在树中的父节点(parent)。对于一个可视化系统中越高层级，该迭代过程会解决将部件分配到整体(assigning parts to wholes)的问题。

在一个active capsule中的neurons的activities，可以表示出现在该图片中一个特定实体(entity)的多种属性。这些属性可能包含许多不同类型的实例参数，比如：pose（位置、大小、方向），deformation（变型）、velocity（速率）、albedo（反射率）、hue(色彩)、texture(纹理)等。一个非常特别的属性是，在图片中实例化实体(instantiated entity)的存在(existence)。表示存在的一个很明显的方式是，通过使用一个独立的logistic unit，它的输出是该实体存在的概率。在本paper中，我们会探索一个有意思的方法，它会使用实例参数向量的整体长度(overall length)来表示实体的存在，并强制向量的方向(orientation)来表示实体的属性。我们会确保：一个capsule的向量输出(vector output)的长度不能超过1，通过使用一个非线性（non-linearity）函数来确保向量在方向保持不变、在幅值上进行缩放。

事实上，一个capsule的输出就是一个向量，使得它可以使用一个很强大的dynamic routing机制，来确保capsule的输出发送到上层(layer above)的一个合适的父胶囊(parent)上。首先，该output会被路由到所有可能的父胶囊上，但它会通过总和为1的耦合系数进行缩减。对于某个capsule的每个可能的父胶囊，该capsule通过将它的output乘以一个权重矩阵计算得到一个“预测向量（prediction vector）”。如果该预测向量与某一父胶囊的输出具有一个大的点积(scalar product，注：标量积、点积、内积、向量的积 dot product = scalar product)，那么这就存在一个自顶向下的反馈（top-down feedback）：该feedback会增大与该父胶囊的耦合系数(coupling coefficient)，而对于其它父胶囊该系数则会降低。这样就增大了该capsule对该父胶囊的贡献，并进一步增大该capsule的预测向量与父胶囊的输出间的点积。这种类型的”routing-by-agreement”远比原始版本的通过max-pooling实现的routing机制要更有效的多。我们会进一步展示，我们的dynamic routing机制是实现该“解释消除(explaining away)”的一种有效方法，解释消除对于将高度重叠的目标进行分割是必须的。

CNN会使用所学到的特征检测器的平移副本（translated replicas）。这允许他们将在一个图片中某一位置获得的较好权重值(good weight values)的知识平移到另一位置上。这在图片解释中被证明是相当有用的。尽管我们使用vector-output capsules来替换CNNs的scalar-output feature detectors、以及使用routing-by-agreement来替代max-pooling，我们仍希望跨空间的复用学到的知识。为了达到该目标，我们让除了capsules的最后一层之外的所有层都是conv的。有了CNNs，我们可以让更高层级的capsules覆盖该图片的更大区域。不同于max-pooling，我们不会丢掉关于该实体在该区域内的准确位置信息。对于低级别的capsules，位置信息是由active capsule所进行“基于位置的编码(place-coded)”。随着结构的上升，在某个capsule的output vector的实值元素（real-valued components）中，越来越多的位置信息是”rate-coded”。从place-coding到rate-coding的转换，加上更高层capsules可以以更多自由度来表示更复杂实体，表明capsules的维度应随着结构的上升而增加。

2.一个capsule的inputs和outputs向量是如何计算的

有许多可能的方式来实现capsules的通用思想。该paper的目的并不是探索整个实现空间，而是提供一种可以运转良好的简单实现，并且能用上dynamic routing。

我们希望：一个capsule的output vector的长度用来表示：通过该capsule表示的实体在当前输入中出现的概率。因此，我们使用一个非线性的“压扁（squashing）”函数，来确保短向量长度收缩到几乎为0，长向量收缩到长度在1以下。我们将它留给判别式学习，以便充分利用这种非线性。

\[v_j = \frac{\| s_j \|^2}{ 1+ \| s_j \|^2} \frac{s_j}{\|s_j\|}\]

…(1)

其中：

  • \(v_j\)是capsule j的向量输出
  • \(s_j\)是它的总输入(total input)

对于除了第一层外的其它层capsules，一个capsule的总输入\(s_j\)是一个在所有“预测向量（prediction vectors）”\(\hat{u}_{j \mid i}\)的加权求和。这些预测向量来自于下层（layer below）的capsules，通过将在下层（layer below）中的一个capsule的输出\(u_i\)乘以一个加权矩阵\(W_{ij}\)得到：

\[s_j = \sum\limits_i c_{ij} \hat{u}_{j \mid i}, \hat{u}_{j|i} = W_{ij} u_i\]

…(2)

其中，\(c_{ij}\)是耦和系数，它通过迭代式dynamic routing过程决定。

在capsule i和在上层（layer above）中的所有capsules间的耦和系数，总和为1, 通过一个”routing softmax”来决定，该softmax的intial logits \(b_{ij}\)是关于capsule i与capsule j相耦合的log先验概率。

\[c_{ij} = \frac{exp(b_{ij})}{\sum_k exp(b_{ik})}\]

…(3)

该log先验(priors)可以同时与所有其它权重一起通过判别式学习学到。他们取决于两个capsules的位置(location)和类型(type)，但不会依赖于当前输入图片。接着通过对每个在上层(layer above)中capsule j的当前输出\(v_j\)，以及由capsule i做出的预测\(\hat{u}_{j \mid i}\)的一致性（agreement）进行measure，以对初始化的耦合系数进行迭代式地提升。

该agreement就是简单的点积\(a_{ij}=v_j \cdot \hat{u}_{j \mid i}\)。该agreement就好像被看成是：它是一个log似然，并且在为capsule i连接到更高层级capsules上的所有耦合系数计算新值之前，被添加到initial logit \(b_{ij}\)中。

在conv capsule layers上，每个capsule会将一个关于向量的local grid，并为grid中每个成员、以及对于每种类型的capsule使用不同的转换矩阵，输出到上层（layer above）中每种类型的capsule。

算法1 routing算法

3.数字存在性的margin loss

我们正使用实例向量的长度来表示一个capsule实体存在的概率。我们希望，对于数字类别k，当且仅当该数字出现在该图片上时，顶层（top-level） capsule会具有一个长的实例向量。为了允许多个数字，对于每个数字胶囊（digit capsule）k，我们使用一个独立的margin loss，\(L_k\)：

\[L_k = T_k max(0, m^+ - \| v_k \|)^2 + \lambda(1-T_k) max(0, \|v_k \| - m^-)^2\]

…(4)

其中：

  • \(T_k=1\)表示某个数字分类k出现
  • \(m^+=0.9\)和\(m^-=0.1\)
  • \(\lambda\)会对于没出现的数字类别会降权(down-weighting) loss，从所有digit capsules的activity vectors的长度进行收缩(shrinking)，从而停止初始化学习(initial learning)。 我们使用\(\lambda=0.5\)。

total loss可以简单认为是所有数字胶囊的losses求和。

4.CapsNet架构

图1 一个具有3 layers的简单CapsNet。该模型会与CNN (Chang 2015)进行比较。在DigitCaps中的每个capsule的activity vector的长度，表示每个数字类别（class）的一个实例的出现，并被用于计算分类loss。\(W_{ij}\)是一个在PrimaryCapsules中每个\(u_i, i \in (1, 32 \times 32 \times 6)\)和\(v_j, j\in (1, 10)\)间的权重矩阵。

一个简单的CapsNet结构如图1所示。该结构是浅层的，只有两个卷积层和一个FC layer。

第一层Conv1

具有256个9x9的conv kernels，它的stride=1, 并使用ReLU activation。该layer会将像素强度转化到局部特征检测器的activities，接着被用于primary capsules的输入。

primary capsules是最低层的多维实体，从一个倒转图的角度看，将primary capsules激活(activating)对应于将渲染过程进行反转(inverting)。比起将实例部件(instantiated parts)组装成熟悉的整体的方式，这是一种非常不同类型的计算，capsules的设计很擅长这种计算。

第二层（PrimaryCapsules）

它是一个convolutional capsule layer，它使用：

  • 32 channels的conv 8D capsules(例如：每个primary capsule包含了8个conv units，它具有9x9 kernel以及stride=2)。
  • 每个primary capsule的输出会看到所有256 x 81 Conv units，它们的receptive fields与capsule中心位置重叠。
  • 在总的PrimaryCapsules中，有\([32 \times 6 \times 6]\)个capsule outputs（每个output是一个8D vector），在\([6 \times 6]\) grid中的每个capsule会相互共享它们的权重。

你可以将PrimaryCapsules看成是Conv layer，其中等式1看成是它的block非线性函数。

最后一层(DigitsCaps)

对于每个digit类具有一个16D的capsule，这些capsules的每一个会接受来自在layer below中的所有capsules的输入。

我们会在两个连续的capsule layers间（比如：PrimaryCapsules和DigitCaps）进行路由（routing），由于Conv1的输出是1维的，在它的空间上没有方向取得一致(agree)。因此，在Conv1和PrimaryCapsules间不会使用routing。所有的routing logits(\(b_{ij}\))被初始化为0。因此，初始化时，一个capsule的output(\(u_i\))会被等概率的(\(c_{ij}\))发送到所有的父胶囊（parent capsules(\(v_0 \cdots v_9\))）上，我们会使用Adam optimizer及tensorflow中的初始参数，包含exponentially decaying learning rate来最小化等式(4)的margin losses的和。

4.1 重构成一个正则方法

我们使用一个额外的reconstruction loss来支持digit capsules将输入数字的实例参数进行编码(encode)。在训练期间，除了正确digit capsule的activity vector外，我们会遮住所有其它digit capsule的vector。接着，我们使用该activity vector来重构输入图片。digit capsule的输出被feed给一个decoder（它由3个FC layer组成，会如图2所示建模像素强度）。我们会对logitsic units的输出和像素强度间的微分平方和做最小化。我们使用乘0.0005将该reconstruction loss缩放，以便它在训练期间不会主导着margin loss。如图3所示，来自CapsNet的16D output的reconstructions是健壮的，它只保留重要细节。

图2 Decoder结构，用于将来自DigitCaps layer的representation重构成一个数字. 图片和Sigmoid layer的output间的欧氏矩离(euclidean distance)，在训练期间最小化。在训练期间，我们使用true label来重构target。

图3 一个使用3个routing迭代的CapsNet的样本MNIST test重构。(l,p,r)表示label，prediction和reconstruction。

5.Capsules on MNIST

我们在28x28 MNIST图片集上（它们会在每个方向上shift两个像素，并使用zero padding）执行训练。没有使用其它的数据扩增/变形(augmentation/deformation)。对于训练集和测试集，dataset分别具有60K和10K的图片。

我们使用单一模型进行测试，没有使用任何模型平均方法(model averaging)。Wan 2013使用ensembling、并将数据进行旋转和缩放进行数据扩充，达到了0.21%的test error。如果不使用这两者，仅能达到0.39%。我们在一个3 layer网络上获得了一个较低的test error (0.25%), 该结果之前只能在更深的网络上才能达到。表1展示了不同CapsNet设置在MNIST上的test error，并展示了routing和reconstruction regularizer的重要性。通过增强在capsule vector中的pose encoding，添加reconstruction regularizer可以增强routing的效果。

表1 CapsNet分类的test arruracy。

baseline是一个标准的CNN，它具有(256, 256, 128)三通道的三层conv layer。每个具有5x5 kernels，stride=1。最后的conv layers会通过size为328､129的两个FC layers。最后的FC layer会使用dropout、连接到一个10分类的softmax layer上，并使用cross entropy loss。baseline也会使用Adam optimizer在2-pixel shifted MNIST上训练。baseline被设计成：计算开销接近CapsNet，在MNIST上达到最好的效果。在参数数目上，baseline具有35.4M，而CapsNet具有8.2M参数，不使用reconstruction subnetwork会有6.8M参数。

5.1 一个capsule表示的独立维度(individual dimensions)

由于我们会将单个数字的encoding进行传递，并将其它数字置为0, 一个digit capsule的维度应学到：以该类的数字被实例化的方式跨越变种空间。这些变种（variations）包括笔划粗细、倾斜、宽度。他们也包含了特定数字的变种，比如：数字2的尾部长度. 我们可以看到，可以使用decoder网络来表示独立维度(individual dimensions)。在为正确的digit capsule计算activity后，我们可以feed一个该activity vector的扰动版本给decoder网络，并观察扰动是如何影响reconstruction的。这些扰动的示例如图4所示。我们发现，该capsule的某一维度(out of 16)几乎总是表示该数字的宽度。一些维度表示全局变种的组合，而其它维度则表示在该数字的一个局部上的变种。例如，对于数字6的上半部的长度，以及下半部圈的size，使用不同维度。

图4

5.2 仿射变换的健壮性

实验表明，对比一个传统的卷积网络，对于每个类，每个DigitCaps capsule会学到一个更健壮的表示。由于在手写数字上的倾斜、旋转、样式等上存在天然的变种，训练好的CapsNet必须对于训练数据的仿射变换有一定的健壮性。

为了测试CapsNet对于仿射变换的健壮性，我们在一个padded和translated MNIST训练集上训练了一个CapsNet和一个传统的CNN（maxpooling和dropout）。在该数据集上，每个样本是一个MNIST数字，随机放置在一个40x40像素的黑色背景上。我们接着在affNIST数据集上测试该网络，在该数据集上每个样本是一个随机进行小的仿射变换的MNIST数字。我们的模型不会使用仿射变换进行训练，而是使用在标准MNIST中可见的平移和自然变换。一个使用early stopping并且训练不够的CapsNet，可以在expanded MNIST测试集上达到99.23% accuracy，并在affNIST测试集上达到79%的accuracy。一个传统的CNN可以在expanded MNIST达到99.22%相近的accuracy，在affnist测试集上达到66%。

6.高度重叠数字的分割

dynamic routing可以被看成是一个并行注意力（parallel attention）机制，它允许在一个level上的每个capsule会留意一些在level below上的active capsules, 并忽略其它。这使得该模型可以识别在图片中的多个物体(objects)，即使物体(objects)有重叠。Hinton 2000提出了分割和识别高度重叠数字的任务，其它的(Goodfellow 2013等)已经在相同领域测试了他们的网络。routing-by-aggrement使它可以使用一个关于物体形状的先验来帮助分割（segmentation）。

6.1 MultiMNIST数据集

我们通过将一个数字置于另一个不同数字之上，来生成了MultiMNIST训练集和测试集。每个数字会在每个方向上shift最多4个像素生成一张36x36的图片。考虑到在28x28图片中的一个数字被限定在一个20x20的box中，两个数字的bounding box平均有80%部分有重合。对于在MNIST数据集中的每个数字，我们生成了1K的MultiMNIST样本。因此，训练集的size是60M，测试集size为10M。

6.2 MultiMNIST结果

我们的3 layer CapsNet模型，重新使用MultiMNIST训练数据进行训练，它会比我们的baseline CNN模型达到更高的测试分类accuracy。我们在高度重合数字对上达到相同的分类错误率5%，而Ba 2014的sequential attention模型在一个更简单的任务上（更低重合度）才能达到。在测试图片上，它由来自测试集的成对图片组成，我们将由capsules网络生成的两个最可能active digit capsules作为分类。在reconstruction期间，我们一次选中一个数字，并使用所选数字对应的capsule的activity vector来重构所选数字的图片（我们知道该图片，因为我们使用它来生成组合图片）。与我们的MNIST模型唯一的不同之处是，对于learning rate，我们增加了decay step的周期大于10x，因为训练数据集更大。

图5

重构（reconstructions）如图5所示，它展示了CapsNet可以将该图片划分成两个原始的数字。由于该分割（segmentation）并不在像素级别，我们观察到：模型可以正确处理重合（同时出现在两个数字中的一个像素），从而解释所有的像素。每个数字的position和style在DigitCaps中被编码。decoder已经学到了给定该encoding，来重构一个数字。事实上，尽管有重叠它仍能够重构数字，展示了每个digit capsule可以从PrimaryCapsules layer接收到的投票中选择style和position。

我们将两个最可能的active DigitCaps capsules进行编码，一次一个，来获取两个图片。接着，通过使用非零强度给每个数字来分配像素，我们可以为每个数字获得segmentation的结果。

7.其它数据集

我们使用7个模型的ensemble，每个模型通过在24x24 patches的图片上进行3个routing迭代，还在CIFAR10上测试了我们的capsule模型，并达到了10.6%的error。每个模型具有和MNIST上的简单模型相同的架构，除了使用三种颜色channels、以及使用64个不同类型的primary capsule外。我们也发现，它可以为routing softmaxes帮助引入一个“none-of-the-above”类型，因为我们不能期望具有10个capsules的最后一层来解释图片中的everything。当首次应用到CIFAR10时(zeiler 2013)，标准CNN达到10.6% test error。

Capsules与生成模型存在同样的一个缺点是，它可能解释在图片中的任何东西，因此，对比起在dynamic routing中使用一个额外的“孤类(opphan category)”时，当建模杂乱东西(clutter)时它会更好。在CIFAR-10中，背景更多变化，从而不能以一个合理size的网络来建模，这可以帮助解释为什么会有更差的效果。

我们也在smallNORB上测试了与MNIST相同的网络构架，它可以达到2.7%的test error rate，这基本上是state-of-the-art的效果。

另外，我们也在SVHN上训练了一个更小的网络。达到4.3%的test error。

参考

d0evi1 Reading time ~2 minutes

阿里在2019又发布了一篇关于tdm（新的称为JTM）的paper:《Joint Optimization of Tree-based Index and Deep Model for Recommender Systems》, 我们来看下：

介绍

为了打破内积形式的限制，并使得任意的关于用户偏好的高级模型对于从整个语料中检索候选的方式在计算上变得可行，之前提出的TDM使用树结构作为index，可以极大提升推荐的accuracy。TDM使用一个树结构来组织items，树中的每个leaf node对应于一个item。TDM假设：每个user-node偏好是指在所有子节点的偏好中具有最大值的节点，就如同一个max-heap一样。在训练阶段，每个user-node偏好的预测模型用于拟合这种类max-heap的偏好分布。与vector kNN-based搜索（index结构需要内积形式）不同的是，在TDM中对偏好建模的形式没有任何限制。在预测时，由训练模型给出的偏好得分，会被用于在tree index中执行layer-wise beam search来检索候选items。在树索引中的beam search的复杂度是log(corpus size)，在模型结构上没有限制，这使得高级用户偏好模型在推荐中检索候选变得可行。

index结构在kNN-based搜索、tree-based方法中扮演着不同的角色。在kNN搜索中，user和item的向量表示会首先通过学习得到，接着建立vector search index。而在tree-based方法中，tree-index的结构(hierarchy)也会影响检索模型的训练。因此，如果对tree index和用户偏好模型进行联合训练是一个重要的问题。tree-based方法在学术上也是一个活跃的话题。在已经存在的tree-based方法中，会学到tree结构，以便在在样本/标签空间（sample/label space）中得到一个更好的结构(hierarchy)。然而，在tree-learning阶段，sample/label划分任务的目标与最终目标（比如：精准推荐）并不完全一致。index learning与prediction模型训练间的不一致，会导致整个系统达到一个次优的状态。为了解决该挑战，更好地将tree index和用户偏好预测相协调，我们的工作聚焦于：通过对一个统一的偏好measure进行最优化，来开发一种同时学习树层级结构（tree hierearchy）和用户偏好预测模型。该paper的主要贡献可以归纳为：

  • 我们提出了一种joint optimization框架，为tree-based推荐学习树结构和用户偏好预测模型，其中，会对一个统一的performance measure(比如：用户偏好的accuracy)进行最优化
  • 我们演示了提出的树结构学习算法，它等同于二分图(bipartite graph)的最大权匹配（max weighted matching）问题，并给出了一个近似算法来学习树结构
  • 我们提出了一种新方法，它可以更好利用tree index来生成层次化用户偏好（hierarchical user representation），它可以帮助学到更精准的用户偏好预测模型。
  • 我们展示了树结构学习和层次化用户表示两者可以同时提升推荐accuracy。这两个模块可以相互提升，来达到更大的效果提升。

本paper的其余部分如下方式组织：

  • 在第2节，我们会比较一些大规模推荐方法来展示不同
  • 在第3节，我们首先给出一个TDM之前工作的简短介绍，接着详细描述joint learning
  • 在第4节，离线对比和在线A/B test实验结果对比
  • 在第5节，结论

2.相关工作

  • Youtube DNN
  • Yahoo news RNN
  • Label Partitioning for Sublinear Ranking (LPSR)
  • Partitioned Label Trees (Parabel)
  • Multi-label Random Forest (MLRF)
  • FastXML

3.joint optimization

在本节中，我们首先给出了一个TDM的简单回顾。TDM使用一个tree hierarchy作为index，并允许高级深度模型作为用户偏好预测模型。接着，我们提出了关于tree-based index和deep模型的joint learning框架。它会选择性在一个全局loss function下最优化index和预测模型。提出了一个greedy-based tree learning算法来最优化index。在最后一个子节，我们会指定用于模型训练中的层次化用户偏好表示。

3.1 tree-based深度推荐模型

推荐系统需要返回给用户感兴趣的一个items候选集合。实际上，如何从一个大的item库中有效做出检索是个大挑战。TDM使用一棵树作为index，并提出了在该tree上的一个类max-heap的概率公式，其中对于每个非叶子节点n在level l上的用户偏好为：

\[p^{(l)}(n | u) = \frac{ \underset{n_c \in \lbrace n's \ children \ in \ level \ l+1 \rbrace}{max} {p^{(l+1)}(n_c | u)} }{\alpha^{(l)}}\]

…(1)

其中：

  • \(p^{(l)}(n \mid u)\)是用户u喜欢节点n的ground truth概率。
  • \(\alpha^{(l)}\)是一个layer归一化项

上述公式意味着：在一个节点上的ground truth的user-node概率，等于它的子节点的最大user-node概率除以一个归一化项。因此，在level l上的top-k节点，必须被包含在在level（l-1)的top-k节点的子节点中，在不损失accuracy的前提下，top-k的leaf items的检索必须被限制在每个layer的top-k节点上。基于这一点，TDM将推荐任务转换成一个层次化检索问题(hierarchical retrieval problem)。通过一个自顶向下的过程，候选items可以从粗到细被逐渐选中。TDM的候选生成过程如图1所示。

图1: Tree-based deep推荐模型 (a) 用户偏好预测模型。我们首先以层次化的方式在对应的layers上的节点上对用户行为进行抽象。接着，用户行为抽象和目标节点（target node）、以及与其它特征（比如：user profile）一起被用于模型的输入。 (b) 树结构(tree hierarchy)。每个item首先会通过一个投影函数\(\pi(\cdot)\)分配到一个不同的leaf node上。在leaf level上的红色节点(items)会被选中作为候选集

在corpus中的每个item被分配到树层次结构（tree hierarchy）上的一个\(\tau\)的leaf node上。non-leaf nodes可以被看成是一个关于子节点的更粗粒度的抽象。在检索时，为了进行打分，用户信息与节点组合在一起，首先会被向量化成一个用户偏好表示，作为深度神经网络M（例如：FC networks）的输入。接着，用户对该节点感兴趣的概率值通过模型M返回，如图1(a)所示。而对于检索top-k个items（leaf nodes）来说，会以level-by-level的方式执行一个自顶向下的（top-down）beam search策略，如图1(b)所示。在level l中，只有在level l-1上带有top-k概率的子节点被打分和排序来选择k个候选节点。该过程会一直持续，直到达到k个leaf items。

有了tree index，一个用户请求的整体检索复杂度，会从线性降到log(corpus size)，而对于偏好模型结构没有任何限制。这使得TDM会打破用户偏好建模的内积形式的限制（它通过引入vector kNN search index和特有的高级深度模型来检索整个corpus的候选），这可以极大提升推荐的accuracy。

3.2 Joint Optimization框架

根据检索过程，TDM的推荐accuracy会通过用户偏好模型M和tree index T的质量(quality)来决定。给定n个关于正例训练数据\((u_i, c_i)\) pairs（它表示user \(u_i\)对target item \(c_i\)感兴趣），\(T\)决定着模型M会为用户\(u_i\)选择哪些non-leaf nodes来达到\(c_i\)。为了替换之前单独学习M和T的方式，我们提出了一个全局loss函数来对M和T进行jointly learn。正如我们在实验中所见，对M和T进行jointly optimizing可以提升最终的推荐accuracy。

\(p(\pi(c_i) \mid u_i; \pi)\)表示：给定一个user-item pair \((u_i,c_i)\)，用户u在leaf node \(\pi(c_i)\)上的偏好概率。其中：\(\pi(\cdot)\)是一个投影函数，它将一个item投影到在T上的一个leaf node上。注意，投影函数\(\pi(\cdot)\)实际决定着在树中的item的层次结构，如图1(b)所示。模型M被用于估计和输出user-node偏好\(\hat{p}(\pi(c_i) \mid u_i; \theta, \pi)\)，其中\(\theta\)为模型参数。如果pair \((u_i, c_i)\)是一个正样本，根据多分类设置，我们具有ground truth偏好 \(p(\pi(c_i) \mid u_i; \pi) = 1\)。

根据max-heap特性，所有\(\pi(c_i)\)的祖先节点（ancestor nodes）的用户偏好概率(注：每一层都有，构成一条路径)，例如 \(\lbrace p(b_j(\pi(c_i)) \mid u_i; \pi)\rbrace_{j=0}^{l_{max}}\)应该为1，在其中\(b_j(\cdot)\)是在level j上从一个节点到它的祖先节点(ancestor node)投影，\(l_{max}\)是在T上的最大level。为了拟合这样一个user-node偏好分布，全局loss函数被公式化成：

\[L(\theta, \pi) = - \sum_{i=1}^n \sum_{j=0}^{l_{max}} log \hat{p} (b_j(\pi(c_i)) | u_i; \theta, \pi)\]

…(2)

其中：n为训练样本正例数，我们将在所有正训练样本上对预测的user-node偏好的负log概率进行求和，它们的祖先user-node pairs作为global empirical loss。

算法1

由于对投影函数\(\pi(\cdot)\)最优化是一个组合优化问题(combinational optimization)，它几乎不可能使用基于梯度的算法来同时优化\(\theta\)。为了解决它，我们提出了如算法1所示的joint learning framework。它可以根据用户偏好模型和tree hierarchy交替(alternativel)对loss function (2)进行最优化。在模型训练和树学习中，training loss的一致性，可以促进框架的收敛。实际上，如果模型训练和树学习两者可以同时减小(2)的值，算法1确实会收敛，因为\(\lbrace L(\theta_t, \pi_t)\rbrace\)是一个递减序列，最低界为0。在模型训练中，\(min_{\theta} L(\theta, \pi)\)是为了为每一layer学习一个user-node偏好模型。受益于tree hierarchy，\(min_{\theta} L(\theta, \pi)\)被转换成学习user-node偏好分布，因此可以使用任意的高级深度模型，它们可以通过流行的最优化算法：SGD、Adam等求解。在归一化用户偏好设定中，由于节点数会随着node level指数增加，使用NCE估计\(\hat{p}(b_j(\pi(c_i)) \mid u_i; \theta, \pi)\)，通过sampling策略来避免计算归一化项。树学习的任务是为了在给定\(\theta\)时求解\(min_{\pi} L(\theta, \pi)\)，它是一个组合优化问题。实际上，给定树结构，\(min_{\pi} L(\theta, \pi)\)等于发现在corpus C中items与T中的leaf nodes间的最优匹配。更进一步，我们有：

推论1： \(min_{\pi} L(\theta, \pi)\)本质上是一个分配问题(assignment problem)：在一个加权二分图中发现一个最大权值匹配。

证明：假如第k项item \(c_k\)被分配到第m个leaf node \(n_m\)，即：\(\pi(c_k) = n_m\)，以下的加权值可以被计算：

\[L_{c_k,n_m} = \sum\limits_{(u,c) \in A_k} \sum_{j=0}^{l_{max}} log \hat{p} (b_j (\pi(c)) \mid u; \theta, \pi)\]

…(3)

其中:

  • \(A_k\)包含了所有正样本抽样对(u,c)
  • \(c_k\)是target item c

如果我们将在T中的leaf nodes和在corpus C中的items看成是顶点(vertices)，将leaf nodes和items间的完全连接(full connection)看成是边（edges），我们可以构建一个加权二分图V，\(L_{c_k,n_m}\)是在\(c_k\)和\(n_m\)间边的权重。更进一步，我们可以学到，每个在items和leaf nodes间的assignment \(\pi(\cdot)\)，等于一个关于二分图V的matching。给定一个assignment \(\pi(\cdot)\)，total loss(2)可以通过下式计算：

\[L(\theta, \pi) = -\sum_{i=1}^{|C|} L_{c_i, \pi(c_i)}\]

其中\(\mid C \mid\)是corpus size。因此，\(min_{\pi} L(\theta, \pi)\)等于寻找V的最大权匹配(maximum weighted matching)。

对于分配问题，传统算法（比如：经典的匈牙利算法）很难应用于大语料上，因为它们具有很高复杂度。即使对于最简单的贪婪算法，它们会使用最大权\(L_{c_k,n_m}\)矩阵来贪婪地选择未分配对\((c_k,n_m)\)，该矩阵是一个大的权重矩阵，需要事先计算和存储，这是不可接受的。为了克服该问题，我们提出了一个segmented tree learning算法。

我们不会将items直接分配给leaf nodes，作为替代，我们会自顶向下每隔d个levels会分配items。给定投影函数\(\pi(\cdot)\)，我们将从level s到level d的\(L_{c_k, \pi(c_k)}\)的partial weight，表示为：

\[L_{c_k, \pi(c_k)}^{s,d} = \sum\limits_{(u,c) \in A_k} \sum_{j=s}^d log \hat{p}(b_j(\pi(c_k)) | u; \theta, \pi)\]

我们首先会根据投影函数\(\pi(\cdot)\)来发现一个分配(assignment)来最大化\(\sum\limits_{i=1}^{\mid C \mid} L_{c_i, \pi(c_i)}^{1,d}\)，该投影函数等价于分配所有items到level d的节点上。对于一个具有最大level=\(l_{max}\)的完全二叉树T（complete binary tree），每个level d上的节点，会分配不超过\(2^{l_{max}-d}\)的items。这是一个最大匹配问题（maximum matching problem），可以使用贪婪算法进行有效求解，因为如果d选得够好，对于每个item可能位置的数目会极大减小(比如：d=7时, 该数目为\(2^d=128\))。接着，每个item c对应在level d（\(b_d(\pi(c)))\)）上的祖先节点保持不变，我们接着相继最大化next d levels，递归直到每个item被分配到一个叶子节点后停止。提出的算法在算法2中详细介绍。

算法2

算法2中的第5行，我们使用一个greedy算法，它使用再平衡策略（rebalance strategy）来求解这个子问题（sub-problem）。每个item \(c \in C_{_i}\)会首先将最大权重\(L_c^{l-d+1,l}\)被分配给在level l中的\(n_i\)子节点。接着，为了保证每个子节点的分配不超过\(2^{l_{max}-l}\)个items，会使用一个rebalance过程。为了提升tree learning的稳定性，以及促进整个框架的收敛，对于那些具有超过\(2^{l_{max}-l}\)items的节点，我们优先将在level l中具有相同的assignment的这些节点，保持使用前一轮迭代（比如：\(b_l(\pi'(c))==b_l(\pi_{old}(c)))\)）。被分配给该节点的其它items会以权重\(L_{\cdot,n}^{(l-d+1,l)}\)的降序进行排序，items的超出部分，会根据每个item权重\(L_{c,\cdot}^{(l-d+1,l)}\)的降序，被移到仍有富余空间的其它节点上。算法2会帮助我们避免存储单个大的权重矩阵。另外，每个子任务可以并行运行，进一步提升效率。

3.3 层次化用户偏好表示

如3.1节所示，TDM是一个层次化检索模型，用来从粗到细的方式层次化地生成候选items。在检索时，会通过用户偏好预测模型M贯穿tree index执行一个自顶向下的（top-down）beam search。因此，在每个level中的M任务是异构的(heterogeneous)。基于此，一个关于M的特定层输入（layer-specific input），必须提升推荐的accuracy。

一系列相关工作表明【9,19,22,35,37-39】，用户的历史行为在预测用户兴趣时扮演着重要角色。另外，由于在用户行为中的每个item是一个one-hot ID特征，在deep model输入的生成上，常见的方法是首先将每个item嵌入到一个连续的特征空间上。一个non-leaf node是一个在tree hierarchy中它的子节点的一个抽象。给定一个用户行为序列\(c=\lbrace c_1, c_2, ..., c_m \rbrace\)，其中\(c_i\)是用户交互的第i个item，我们提出使用\(c^l = \lbrace b_l(\pi(c_1)), b_l(\pi(c_2)), \cdots, b_l(\pi(c_m)) \rbrace\)与target node、以及其它可能特征（比如：user profile）一起来生成M在layer l的input，来预测user-node偏好，如图1(a)所示。在这种方式中，用户交互的items的祖先节点被当成抽象的用户行为使用。训练M时，在对应的layer上，我们使用该抽象来替换原始的user-behavior序列。总之，层次化用户偏好表示带给我们两个优点：

  • 层的独立性（layer independence）：对于不同layers来说，在layers间共享item embeddings，会像用户偏好的预测模型那样，在训练M时会带来在一些噪声（noises），因为对于不同layers来说targets是不同的。解决该问题的一个显式方法是，对于每一layer，将一个item与一个独立的embedding相绑定来生成M的输入。然而，这会极大增加参数的数目，使得系统很难优化和应用。我们提出的抽象用户行为会使用相应layer上的node embeddings来生成M的input，在训练时达到layer independence，无需增加参数的数目。
  • 精准描述（Precise description）：M会以层次化方式贯穿tree index来生成候选items。随着所检索的level的增加，在每一level上的候选节点会以从粗到细的方式描述最终的推荐items，直到达到leaf level。提出的层次化用户偏好表示（hierarchical user representations）会抓住检索过程的本质，并在相应layer的nodes上给出一个关于用户行为的精准描述，这可以提升用户偏好的预测，通过减少因太过详细或太过粗粒度描述而引入的混淆(confusion)。例如，在upper layers中M的任务是粗粒度选择一个候选集，用户行为也会在训练和预测时在相同的upper layers上使用均匀的node embeddings进行粗粒度描述。

参考

d0evi1 Reading time ~3 minutes

microsoft在开放了inner product快速计算的方法:《Speeding Up the Xbox Recommender System Using a Euclidean Transformation for Inner-Product Spaces》。主要解决inner product top-k search问题，我们来看下：

介绍

在线服务数据的大量增长，对于更好的信息过滤信息提出了新的风险与挑战。在推荐系统中，包括：

  • (1) item目录(catalog)
  • (2) users
  • (3) 用户反馈(ratings)

推荐系统的目标是：为每个用户找到一个关于items的限定集合，使得它们具有最大可能的机会被该用户消费。现代推荐系统有两个主要部分：

  • 第一部分：学习阶段，基于user feedback的离线模型学习
  • 第二部分：检索阶段，对每个用户(在线)推荐items

该paper主要在第二阶段，推荐系统基于MF。特别的，对一个用户的推荐，我们引入了一个新方法来在运行时长（running time）和结果质量间做权衡。

MF是CF中最流行的方法。该方法要比其它近邻方法要好。在MF模型中，users和items通过latent feature vectors表示。Bayesian MF模型是Xbox推荐系统的核心，它每天会为数百万的用户提供游戏、电影、音乐推荐服务。在该系统中，users和items通过\(R^{50}\)的低维向量表示。用户u通过向量\(x_u\)表示，item i通过\(y_i\)表示，它们间的匹配质量(match quaity)通过两个向量间的内积\(x_u \cdot y_i\)来表示。内积越高表示该用户越愿意消费该item。

检索问题：理想情况下，给定一个用户u（它由向量\(v_u\)表示），所有item vectors \((y_1, \cdots, y_n)\)都会被检索。对于每个这样的item vector \(y_i\)，我们会计算它的匹配度\((x_u \cdot y_i)\)，items根据它们的匹配度进行排序。在该列表中具有最高匹配度的该items会被选中来形成最终的推荐列表。然而，在有限搜索时间内，items的catalog通常因为太大而不能对所有内积进行穷举计算。

Xbox的catalog包含了上百万的items。如果使用线性扫描，每个推荐都需要数百万内积计算。user vectors会吸收上下文信息，这些信息只在用户有行为时（engagement）提供。因而，user vector的计算是实时(online)的。结果是，推荐的items列表的检索只能在线(online)执行，不能离线预计算。该任务构成了在online servers引入的单个最大密集计算任务。因此，该过程需要有个快速的替代方案。

我们的贡献：该paper展示了如何来极大地加速推荐检索过程。该最优化item-user match检索与一个近似搜索相关：对与user vector检索高内积(high inner product)的items，但没必要检索最高的。该方法会由多个构建块组成。首先，我们定义了一个新的转换（transformation），它将内积问题转换成一个Euclidean最近邻问题（第3节）。作为一个预处理过程，该转换会被应用到item vectors上。在item检索期间，另一个转换会被应用到user vector上。在转换后空间中的具有最小欧氏距离（Euclidean distance）的item会被检索到。为了加快最近邻搜索，会使用PCA-Tree数据结构与一个新的邻近增强法（neighborhood boosting scheme）(第4节)。

为了演示提出方法的效果，它被应用到一个Xbox推荐数据集上，以及公开的Yahoo Music dataset上。实验表明，在推荐质量推化以及检索时间提升的trade-off曲线（第5节）。另外，time-accuracy trade-offs由两个baseline方法组成，基于LSH和对于在MF近似推荐上的当前state-of-art方法。我们展示了我们的方法具有更高的加速。

概念：我们使用：

  • 小写字母表示scalars
  • 粗体小写字母表示vector
  • 粗体大写字母表示matrix

例如，x是scalar，x是vector，X是matrix。

给定一个向量\(x \in R^d\)，有：

  • \(x_i\)表示在维度i上的measure，具有：\((x_1, x_2, \cdots, x_d)^T \in R^d\)
  • norm通过\(\| \cdot \|\)来表示；欧氏空间中，\(\|x\|=\sqrt{\sum\limits_{i=1}^d x_i^2}\)。
  • 我们通过\(x \cdot y\)来表示x和y间的内积dot product (inner product)。
  • 最终，我们使用\((a, x^T)^T\)来表示一个标量a与一个向量x进行拼接。

3.简化搜索问题（REDUCIBLE SEARCH PROBLEMS）

该paper的一个关键贡献是，在search problem间进行有效的简化。在该部分，我们对search problem的概念进行公式化，并展示了在已知变种间的有效简化。

我们将search problem定义为：

定义1:

一个search problem \(S(I, Q, s)\)包含了一个关于n个items的实例集合\(I = \lbrace i_1, i_2, \cdots, i_n \rbrace \in I\)，一个query \(q \in Q\)，以及一个search function：

\[s : I \times Q \rightarrow \lbrace 1,2, \cdots, n \rbrace\]

函数s用于：对于一个给定query q，检索在I中的某一item的索引。我们的目标是，对items使用\(g: I \rightarrow I'\) 进行预处理，以便每个query都能有效得到结果。预处理函数g可以涉及到一个从某一domain到另一domain的转换，以便转换后的search problem可以在一个不同的domain上执行。以下的定义对search problems间的概念的简化做了公式化：

定义二：

一个search problem \(S_1(I, Q, s_1)\)被简化成一个search problem \(S_2(I', Q', s_2)\)，其中\(S_1 \leq S_2\)，如果存在函数\(g: I \rightarrow I'\)和\(h: Q \rightarrow Q'\)，那么：

\[j = s_1(I,q) \ 当且仅当 j=s_2(g(I), h(q))\]

该简化不会对g和h的运行时长做任何限制。注意，g只当成一个预处理step运行，而h会被应用到query时。这提出了一个要求：h必须有\(O(1)\)的运行时间。我们将该问题公式化为：

定义三：

我们会说：\(S_1 \leq_{O(f(n))} S_2, \ if \ S_1 \leq S_2\)，g和h的运行时间分别为\(O(f(n))\)和\(O(1)\)。

对于在\(R^d\)中的一个query vector，我们会在该paper中考虑三个search problem：

  • MIP：在\(R^d\)中的n个vectors上的最大内积(maximum inner product)。为\(MIP_{n,d}\)
  • NN：在\(R^d\)中n个vectors的最近邻(nearest neighbor)，为(\(NN_{n,d}\))
  • MCS：在\(R^d\)中n个向量的最大cosine相似度。(\(MCS_{n,d}\))

它们的正式定义如下：

实例(Instance)：一个包含n个item向量的矩阵 \(Y=[y_1, y_2, \cdots, y_n]\)，其中\(y_i \in R^d\); 因此 \(I = R^{d \times n}\)

查询(Query)：一个vector \(x \in R^d\); \(Q = R^d\)

目标(objective)：根据以下公式进行检索index：

\[\begin{align} s(Y,x) &= argmax_i (x \cdot y_i) && MIP_{n,d} \\ s(Y,x) &= argmin_i \| x - y_i \| && NN_{n,d} \\ s(Y,x) &= argmax_i \frac{x \cdot y_i}{\| x\| \| y_i \|} && MCS_{n,d} \end{align}\]

其中i表示Y的第i列。

下一节展示了这三个问题间是如何进行转换的，可以使用：

  • \[MCS_{n,d} \leq_{O(n)} MIP_{n,d} \leq_{O(n)} NN_{n,d+1}\]
  • \[NN_{n,d} \leq_{O(n)} MCS_{n,d+1} \leq_{O(n)} MIP_{n,d+1}\]

来达成上述目标。

3.1 保序转换(Order Preserving Transformations)

当对三个向量进行一个内积比较时，vectors x、\(y_i\)和\(y_j\)间不支持三角不等式(triangle inequality)，因为这是在MIP中的情况。许多高效的搜索数据结构依赖于三角不等式，如果MIP可以被转换成使用欧氏距离的NN，这些数据结构立马变得可用。我们的第一个定理论声明是，通过使用比原始问题多一维Euclidian metric，MIP可以被简化到NN。

定理1

\[MIP_{n,d} \leq_{O(n)} NN_{n,d+1}\]

证明：

假设：\(\phi \triangleq max_i \| y_i \|\)，

对输入(input)预处理：\(\hat{y}_i = g(y_i) = (\sqrt{\phi^2 - \|y_i\|^2}, y_i^T)^T\)

在query时：\(\hat{x} = h(x)=(0, x^T)^T\)。因为：

\[\begin{align} & \| \hat{x} \|^2 = \| x \|^2 \\ & \|\hat{y}_i \|^2 = \phi^2 - \| y_i ||^2 + \|y_i\|^2 = \phi^2 \\ & \hat{x} \cdot \hat{y}_i = \sqrt{\phi^2 - \| x_i \|^2} \cdot 0 + x \cdot y_i = x \cdot y_i \end{align}\]

我们有：

\[\| \hat{x} - \hat{y} \|^2 = \|\hat{x} \|^2 + \|\hat{y} \|^2 - 2 \hat{x} \cdot \hat{y}_i = \|x\|^2 + \phi^2 - 2x \cdot y_i\]

最终，\(\phi\)和x是与index i相互独立的：

\[j = argmin_i || \hat{x} - \hat{y}_i ||^2 = argmax_i (x \cdot y_i)\]

定理1是基础。在余下章节，我们会表述它的特性以及相关转换。

如果知道转化后的\(\hat{Y} = [\hat{y}_1, \hat{y}_2, \cdots, \hat{y}_n]\)在一个mainifold上，如上，我们期望通过使用\(NN_{n,d} \leq_{O(n)} MIP_{n,d-1}\)反向化简来恢复Y。然而，在常见case中，该transformation只可能通过再增加一维：

定理2

\[NN_{n,d} \leq_{O(n)} MIP_{n,d+1}\]

证明：

输入的预处理：\(\hat{y}_i = g(y_i) = (\| y_i \|^2, y_i^T)^T\)

在查询时：\(\hat{x} = h(x) = (1, -2 x^T)^T\)。

我们有：\(\hat{x} \cdot \hat{y}_i = \| y_i \|^2 - 2 x \cdot y_i\)。

最终：

\[j = \underset{i}{argmax} \ \hat{x} \cdot \hat{y}_i = \underset{i}{argmin} (\|x\|^2 + \|y_i \|^2 - 2x \cdot y_i) \\ = \underset{i}{argmin} \ \|x - y_i \|^2\]

MIP搜索可以被嵌入到一个MCS search中，通过增加1维来实现：

定理3

\[MIP_{n,d} \leq_{O(n)} MCS_{n,d+1}\]

证明：

预处理(preprocessing)和查询转换(query transformation)与定理1相同。输入的预处理为：

\(\phi \triangleq max_i \|y_i \|\)，假设：\(\hat{y}_i = g(y_i) = (\sqrt{\phi^2 - \|y_i\|^2}, y_i^T)^T\)。

在query时：

\[\hat{x} = h(x)= (0, x^T)^T\]

最终:

\[j = \underset{i}{argmax} \frac{\hat{x} \cdot \hat{y}_i}{\| \hat{x} \| \|\hat{y}_i \|} = \underset{i}{argmax} \frac{x \cdot y_i}{\| x \| \phi} = \underset{i}{argmax} x \cdot y_i\]

然而，MCS可以通过归一化向量来简化MIP查询：

定理4

\[MCS_{n,d} \leq_{O(n)} MIP_{n,d}\]

证明：

输入预处理：\(\hat{y}_i = g(y) = \frac{y_i}{\|y_i\|}\)。

在query时：\(\hat{x} = h(x) = x\)。

最终：

\[j = argmax_i \hat{x} \cdot \hat{y}_i = argmax_i \frac{x \cdot y_i}{\|x \| \|y_i \|}\]

我们的最终结果表明，一个NN search可以被转换成一个MCS search，通过增加1维来实现：

定理5

\[NN_{n,d} \leq_{O(n)} MCS_{n,d+1}\]

证明：

与定理1中的简化相同。输入的预处理为：\(\phi \triangleq max_i \| y_i \|\)，以及 \(\hat{y}_i = g(y_i) = (\sqrt{\phi^2 - \|y_i\|^2}, y_i^T)^T\)。

在query时：\(\hat{x} = h(x)=(0, x^T)^T\)。

加上定理1:

\[j = argmax_i \frac{\hat{x} \cdot \hat{y}_i}{ \|\hat{x}\| \|\hat{y}_i \|} = argmax_i \frac{x \cdot y_i}{\|x\| \phi} = argmax_i x \cdot y_i = argmin_i \|\hat{x} - \hat{y}_i \|^2\]

接下来，我们利用定理1来加速在Xbox中和其它基于MF的推荐系统的检索。

4.我们的方法

我们的解决方案基于两个部分：

  • 1.将问题简化到一个Euclidian search problem
  • 2.使用一个PCA-Tree来求解它。

简化过程（reduction）与定理1的定义非常相似，但会使用一个额外的平移（shift）和旋转（rotation），因此，MIP search problem会被简化到NN search，所有的vectors与它们的主成分（pricipal components）相对齐。

4.1 简化

我们首先根据定理1定义了第一个简化函数。假设：\(\phi \triangleq max_i \| y_i \|\)，以及：

\[\begin{align} y_i^* &= g_1(y_i) = ( \sqrt{\phi^2 - \|y_i \|^2}, y_i^T)^T \\ x^* &= h_1(x)=(0, x^T)^T \end{align}\]

…(2)

其中，当应用到Y上时，给定元素\(y_i^* \in R^{d+1}\)。这会将MIP化简到NN。由于NN在输入空间中（input space）对于平移(shift)和旋转(rotations)是不变的，我们可以使用PCA rotation来构成(compose)该转换（transformations），并且可保证一个等价的search problem。

我们对数据进行mean-center并进行rotate：假设\(\mu = \frac{1}{n} \sum\limits_i y_i^*\)是在第一次化简后的均值，并且\(M \in R^{(d+1) \times n}\)是一个使用\(\mu\)沿着它的列进行复制的矩阵。该中心数据矩阵的SVD为：

\[(Y^* - M) = W \Sigma U^T\]

其中，数据项(data items)出现在\(Y^*\)的列中。矩阵W是一个\((d+1) \times (d+1)\)的矩阵。\(W=[w_1, \cdots, w_{d+1}]\)的每一列定义了一个正交单位长度的特征向量（eigenvector），因此，每个\(w_j\)定义了一个超平面，每个\(y_i^* - \mu\)被投影到它上面。矩阵W是一个旋转矩阵，它会将这些vectors对齐到它的主成分(principal components)上。我们定义了中心旋转（centered rotation）作为我们的第二个转换：

\[\begin{align} \hat{y}_i = g_2(y_i^*) = W^T (y_i^* - \mu) \\ \hat{x} = h_2(x^*) = W^T (x^* - \mu) \end{align}\]

…(3)

其成分（composition）为：

\[g(y_i) = g_2(g_1(y_i)), h(x) = h_2(h_1(x))\]

…(4)

仍定义了一个从MIP到NN的简化(reduction)。使用\(\hat{y}_i = g(y_i)\)，为我们给出了一个关于输入向量\(\hat{Y}\)的转换后集合，可以在其上执行一个Euclidian search。另外，在该转换后，该点会被旋转，因而它们的成分（compoments）会减小方差的阶数（order of variance）。接着，我们会使用一个PCA-Tree数据结构来索引在\(\hat{Y}\)中的转换后的item vectors。我们将上述逻辑表述在算法1中。

算法1

4.2

略

参考

d0evi1 Reading time ~1 minute

hinton在2012 《Transforming Auto-encoders》中提出了胶囊“capsules”的概念。我们来看下这篇paper：

1.介绍

当前在图片中识别目标（objects）的方法效果很差，并且所使用的方法仍不够智能。一些最好的计算机视觉系统使用方向梯度直方图（ histograms of oriented gradients）作为“visual words”，并使用一个天然空间金字塔（crude spatial pyramid）来将这些元素的局部分布进行建模。这样的方法无需精确知道目标在哪就可以正确识别目标（objects）——这种能力用于诊断人类大脑损伤。最好的人工神经网络使用手工编码的、权重共享的schemes（hand-coded weight-sharing schemes）来减小自由参数的数目，并通过对相同kernel的平移拷贝(transpated replicas)的局部池子(local pools)的激活(activities)做子抽样(subsampling)来达到局部平移不变性(local translational invariance)。该方法可以处理在图片中的变化（视角的变化引起），但它很明显不能处理识别任务，比如：脸部识别（facial identity recognition），这类任务需要知道高级部位间的精准局部关系(比如：鼻子和嘴)。在经过使用卷积网络做subsampling的多个stages后，在这些姿态（poses）中的高级特征具有许多不确定性。这通常被看成是一个合理的特性，因为它相当于在受限范围内的姿态是不变的，但这使得计算精准的局部关系来说是不可行的。

该paper会讨论CNN尝试这样去做时会误入岐途。作为对在“neurons”的activities的视角不变性（它使用单个标量输入对重复的特征检测器的一个local pool的activities进行归纳）的替代，人工神经网络应使用局部”capsules”来执行对输入的一些相对复杂的内部计算，并接着封装这些计算结果到一个包含高度信息化输出的小向量中。每个capsule会学习识别在一定受限视角条件(viewing conditions)和变形(deformations)等范围内的一个隐式定义的可视化实体(visual entity)，它会同时输出在该限定范围内的该实体概率、以及一个“实例参数(instantiation parameters)“的集合，它会包含该可视化实体的精准姿态(pose)、光线照明(lighting)、变形(deformation)，与该实体的一个隐式定义的规范版本相关联。当该capsule正常工作时，可视化实体的概率是局部不变的（locally invariant）——随着实体在各种可能出现方式(在capsule覆盖的受限区域内)上移动，该概率不会改变。该实例参数是“等变化的（equivariant）”——随着视角条件（viewing condition）的改变，实体会在appearance manifold上进行移动，该实例参数会通过一个相应的量进行变化，因为他们表示该实体在appearance manifold上的本征坐标。

capsules的主要优点之一是：输出显式的实例参数。该方法提供了一种简单方式通过识别它们的部件（parts）来识别整体（wholes）。如果一个capsule通过学习以向量形式输出它的可视化实体的姿态(pose)，那么该向量与该pose在计算机显卡(computer graphics)中的“天然表示(nature representations)”成线性相关，这里存在着一个简单且高度选择性的测试方法，来判断该可视化实体表示是否可以通过两个active capsules(A和B)进行表示，这两个capsules具有合理的局部关系（spatial relationship）来激活一个更高层级的capsule C。假设capsule A的pose outputs通过一个矩阵\(T_A\)来表示，该矩阵指定了在A的标准可视化实体（canonical visual entity）与通过capsule A发现的该实体的实际实例（actual instantiation）之间的坐标转换。如果我们使用part-whole坐标转换\(T_{AC}\)乘以\(T_A\)，这样就会将A的标准可视化实体与C的标准可视化实体相关联，我们就可以得到\(T_C\)的一个预测。相似的，我们使用\(T_B\)和\(T_{BC}\)来获取另一个预测。如果这些预测是一个好的匹配，通过capsules A和B发现的实例（instantiations）会在合理的局部关系以便激活capsule C，并且该预测的平均值会告诉我们：通过C表示的更大的可视化实体是如何对应于C的标准可视化实体进行转换的。例如，如果A表示一张嘴（mouth），B表示一个鼻子（nose），他们可以为面部姿态(pose of face)做出预测。如果这些预测达成一致，嘴和鼻子就必须在合理的局部关系内来形成一个脸。关于这种执行形态识别(shape recognition)的方法，其中一个有意思的特性是，局部-整体关系（part-whole）的认识是视角不变性的（viewpoint-invariant），可以通过权重矩阵进行表示，然而，关于当前已观察目标、及它相对应部件(parts)的实例参数的认知是视角等变化的（viewpoint-equivariant），并且可以通过neural activities来表示。

为了获取这个的一个part-whole的结构，“capsules”会实现在该结构中最低层的部件(parts)，来从像素强度(pixel intensities)上抽取显式的姿态参数。该paper展示了，如果该神经网络可以直接、非可视的方式访问该变换（direct, nonvisual access to transformations），这些capsules相当容易从成对的转换图片中学习得到。从人类视角上看，例如，一次扫视会引起关于该视网膜图片的一个纯变换（pure translation），皮质(cortex)可以不可见地访问关于眼部移动的信息。

2.学习第一层capsules

一旦像素强度被转换成一个active集合的outputs时，第一层capsules中的每个capsule会生成一个关于它的可视化实体的pose的显式表示，很容易看到，越大越复杂的可视化实体是如何通过使用active、低级capsules的关于poses预测的方式来识别的。但是，第一层capsules是从哪里来的？一个人工神经网络是如何学到将像素强度的表示(language)转换成关于姿态参数（pose parameters）的表示的？该paper提出的该问题会有一个很令人吃惊的简单答案，我们称之为“transforming auto-encoder”。通过使用简单的2D图片和capsules，我们解释了该思想，pose outputs是一个关于x和y的位置。后面我们会泛化到更复杂的姿态(poses)。

图1: 一个transforming auto-encoder的三个capsules，会建模平移(translations)。图中的每个capsule具有3个recognition units和4个generation units。在连接(connections)上的权重可以通过在实际outputs和target outputs之差进行BP学到

如图1所示，考虑该前馈神经网络。一旦它已经被学到，该网络就是确定的（deterministic），输入一张图片，进行平移shifts（\(\Delta x\)和\(\Delta y\)），它会输出shifted后的图片。该网络由多个独立的capsules组成，它们只会在最后一层进行交叉，一起合作生成期望得到的shifted后的图片。每个capsule具有自己的logistic “识别单元（recognition units）”，它们扮演着hidden layer的角色，来计算三个数(numbers)：x, y, p，capsule会将它的输出发送给视觉系统的更高层。p是capsule的可视化实体出现在输入图片中的概率。capsule也具有它自己的“生成单元（generation units）”，可以被用于计算capsule对转换后图片的贡献。generation units的输入是\(x + \Delta x\)和\(y+\Delta y\)，capsule的generation units对输出图片的贡献，会乘以p，因而 inactive capsules会无效。

为了让transforming auto-encoder生成正确的输出图片，通过每个active capsule计算得到的x和y值，会对应于它的可视化实体的实际x和y位置。并且我们不需要事先知道该可视化实体或它的坐标框架的原点(origin)。

图2: 左图：一个散点图. 其中纵轴表示其中一个capsule对于每张数字图片的x输出，横轴表示如果该图片在x方向上以(+3 或 -3)像素进行shift时该相同capsule的x输出。如果原始图片已经接近该capsule在x坐标可以表示的极限，在该方向上进一步shifting会造成capsule生成错误的答案，但如果对于该capsule为管辖区域外的数据，将它的概率设置为0, 这不会有影响。 右图：9个capsules（纵），10个generative(横) units，对应的outgoing weights

对于该transforming auto-encoder的简单效果演示，我们训练了一个带30个capsules的网络，每个都有10个recognition units和20个generation units。每个capsule会看到一张MNIST数字图片的整体。输入和输出图片都可以使用-2, -1, 0, +1, +2像素在x和y方向上随机进行shift，transforming auto-encoder会将生成的\(\Delta x\)和\(\Delta y\)看成是一个额外输入。图2展示了当输入图片进行shift后，该capsules会以合理的方式输出shift后的x和y值。图2展示了，capsules会学习带高度局部化投影域（projective fields）的generative units。recognition units的receptive fields噪声较多，局部化更少些。

图3 Top: 完全仿射变换，使用一个带有25个capsules的 transforming auto-encoder，每个capsule具有40个recognition units和40个generation units。顶部行展示了输入的图片；中间行展示了输出的图片，底部行展示了被正确变换的输出图片. Bottom：该transforming anto-encoder的前20个generation units，前7个capsules的output weights。

2.1 更复杂的2D转化

如是每个capsule会给出9个real-valued outputs，它们被看成是一个3x3矩阵A，一个transforming auto-encoder可以被训练来预测一个完整的2D仿射变换（affine transformation：平移translation, 旋转rotation, 缩放scaling，裁减shearing）。一个已知矩阵T会被用于capsule A的output上，来获得matrix TA。当预测目标输出图片时，TA的元素接着被当成genreation units的输入。

2.2 在3D视角上建模变化

图4 左：对于训练数据，输入、输出和目标的立体像对（stereo-pairs）。右：对于在训练期间未见过的汽车模型的input、output和target stereo-pairs

使用矩阵乘法来建模视角效果的一个主要潜在优点是，它很容易拷贝到3D上。我们的前置实验（见图4）使用计算机显卡来生成从不同视角上关于汽车的不同类型的立体图片。transforming autoencoder包含了900个capsules，每个具有两个layers（32，64）的RLRU(rectified linear recognition units)。capsules具有11x11像素的receptive fields，它由一个在96x96图片上的30x30 grid组成，两个相邻capsules间的stride为3个pixels。它们不是weight-sharing的。从该layer的64个recognition units中生成的每个capsule，3D方向上的特征(可以用于调参来检测)的一个3x3矩阵表示，同时隐式定义特征出现的概率。该3x3矩阵接着乘以真实的在源图片和目标图片间的转换矩阵，结果被feed给capsule的具有128个GRLU（generative rectified linear units）的单个layer上。该generation unit activities会乘以capsules的“特征出现（feature presence）”概率，结果被用于增加在重构图片（它以capsule的11x11 receptive field的中心为中心）上一个22x22 patch上的强度。由于该数据由图片的立体对组成，每个capsule必须同时在立体对的成员上查看一个11x11 patch，同时也会在重构的22x22 patch的每个成员上进行。

3.讨论

略。

参考

d0evi1 Reading time ~2 minutes

netflix在recsys 2018的paper《Calibrated Recommendations》提出了Calibrated的概念, 我们来看下：

抽要

当一个用户观看了70个爱情片(romance)和30个动作片(action)时，那么很合理的期望结果是：电影推荐的个性化列表中由70%的爱情片和30%的动作片组成。这是个很重要的特性，称为“校准(calibration)”，最近在机器学习的关于公平性（fairness）的背景下重新获得关注。在items推荐列表中，calibration可以保证：一个用户的多个（过往）兴趣领域，受它对应的占比影响。Calibration特别重要，因为推荐系统在离线环境下通常对accuracy(比如：ranking metrics)进行最优化，会很容易导致这样的现象：一个用户的兴趣过少，推荐会被用户的主兴趣”占满”——这可以通过“校正推荐（calibrated recommendations）”来阻止。为了这个目的，我们会描述用于量化calibration程度（degree）的指标，以及一种简单有效的re-ranking算法来对推荐系统的输出进行后处理（post-processing）。

1.介绍

推荐系统在许多不同应用领域提供了个性化的用户体验，包括：电商、社交网络、音乐视频流。

在本paper中，我们展示了：根据accuracy（例如：ranking指标）训练的推荐系统，很容易为一个用户生成集中在主要兴趣领域（main areas）上的items——当用户的兴趣领域越少时，items会趋向于未被充分表示（underrepresented）或者缺失（absent）。随着时间流逝，这样的不平衡推荐会让用户的兴趣领域越来越窄——这与”回音室(echo chambers)效应”或”过滤气泡(filter bubbles)效应”相似。该问题也会在以下情况中存在：一些用户共享相同的账号，其中：使用相同账号的少量活跃用户的兴趣会在推荐中“挤出”。我们会在第2节的一些思维实验(thought experiments)、以及第6节的真实数据实验中展示该效果。

Calibration在机器学习中是一个通用概念，最近在机器学习算法关于公平性(fairness)中开始流行起来。如果关于多个分类的预测比例与实际数据点的比例相一致，那么这个分类算法被称为”calibrated”。相类似的，在本paper中，calibrated recommendations的目标是：影响在推荐列表中一个用户的多种兴趣，以及它们合适的比例。为了这个目的，我们在第3节描绘了calibration degree的量化指标。在第4节，我们提出了一个算法，目标函数使它更接近calibrated，来对一个给定推荐的ranked list进行post-processing。等等

为了方便，我们会使用进行如下释义：

  • 与items交互的用户：观看了电影的用户
  • items类目(categories)：genres

2.动机

在本节中，我们描述了一种思维实验，它演示了会造成推荐items列表变得不平衡（unbalanced）的核心机制。我们会使用三个steps开发，从最极端情况开始。

我们会考虑常用的离线环境（offline setting），其中数据集由历史的user-item交互组成，它们被分割成trainset和testset（例如：基于时间、或者随机划分）；评估目标(evaluation objective)是：预测在testset中哪些items与用户交互时会达到最佳的accuracy，通常会根据ranking metrics进行量化。该setting的优点是很容易实现，并且可应用到用于CF的公开数据集上。

在我们的示例中，假设一个电影用户在离线训练数据中播放了70部爱情片和30部动作片：我们的objective是生成一个包含10个推荐电影的列表，可以让预测该用户的test-movies的概率最大化（例如：在offline test data中被该用户播放的held-out movies）。这会最大化推荐accuracy。出于简洁性，我们假设：两个genres是完全互斥的（例如：一个电影可以是动作片、或者是爱情片，但不能是动作爱情片）

2.1 分类不平衡（class imbalance）

在第一个以及最极端情况下，假设：我们只知道用户在genres上的偏好，但我们没有在每个genre内的单个电影的额外信息。在缺少任何额外信息的情况下，该问题与机器学习中的不平衡分类问题（imbalanced classification）相类似：通过预测majority class的label，总是会获得最好的预测accuray。在一个二分类问题中，已知有70%的数据点的label为+1的，而剩余30%数据点的label为-1，在缺少其它额外信息的情况下，为所有数据点预测label为+1总是最好的——因为会有70%的数据点是正确的。相反的，如果我们随机使用概率70%和30%（出现在数据中的概率）来预测label +1和label -1，我们期望的预测labels只有0.7 · 70% + 0.3 · 30% = 58%的数据点会是正确的。

回到我们的推荐示例：在缺少其它额外信息情况下，如果我们推荐100%的爱情片给用户（一部动作片也没有），在test data上会获得最好的accuracy。

我们的极端假设是：没有额外信息提供。在真实世界中，会有更多数据提供——然而，数据总是有限或带噪声的，因而，该效应在某种程度上仍会出现。注意，该问题与任何特定的机器学习模型无关。在第6节的真实数据中，我们会展示不平衡推荐的风险：当根据accuracy对推荐系统最优化时，用户只有很少兴趣的genres很容易被“挤出”，而用户兴趣的主要领域(main areas)则会被放大。

该问题的另一个视角是，从有偏推荐（biases recommendations）的角度：在理想情况下，提供的数据是没有任何偏差的(biases)，在有限数据上的朝着accuracy进行的训练会引入在推荐列表中的一个bias，例如，它会偏向(bias)于用户的主兴趣方向。

相反的，做出更平衡（balanced）或校正（calibrated）的推荐的objective，会减少推荐的accuracy，这并不令人吃惊。

2.2 变化的电影概率

该节开发了一种略微更复杂些的思维实验（thought experiment）：我们假设：

  • \(p(i \mid g)\)：用户u决定从genre g播放，电影i被播放的概率

之前的示例中，我们已知：

  • \(p(g_r \mid u)=0.7\) （r: romance movies即爱情片）
  • \(p(g_a \mid u)=0.3\) （a: action movies即动作片）

假设两个电影集合genres是相互排斥的，用户u播放在genre g上的电影i的概率可以通过以下公式得到：

\[p(i \mid u) = p(i \mid g) \cdot p(g \mid u)\]

为了得到最佳预测accuracy，我们必须找到被该用户播放的具有最高概率\(p(i \mid u)\)的10部电影i。我们考虑下：最可能播放的动作片\(i_{g_a,1}\)（例如：在动作片中排序第1的），以及最可能播放的第10个爱情片\(i_{g_r,10}\)，我们会获得：

\[\frac{p(i_{g_r,10} | u)}{p(i_{g_a,1} | u)} = \underbrace{\frac{p(i_{g_r,10} | g_r)}{p(i_{g_a,1} | g_a)}}_{\approx 1/2.1} \cdot \underbrace{\frac{p(g_r | u)}{p(g_a | u)}}_{=\frac{0.7}{0.3} \approx 2.33} \approx \frac{2.33}{2.1} > 1\]

…(1)

其中：

  • 值2.1通过MovieLens 20 Million数据集[13]确定。在该示例的变种中，第10部爱情片要比最好的动作片具有一个更大的播放概率。

因此，根据accuracy，待推荐的最优的10个titles可以全是爱情片title（没有一部动作片）。

2.3 LDA

该示例受LDA的启发。LDA描述了一个用户会以一个2-step方式来选择一个电影：用户首先选择一个genre(topic)，然后在该选中genre中选择一个电影(word)。提到LDA有三个原因。

首先，如果我们假设，真实用户选择一部电影会遵循2-step过程，那么LDA模型是合适的模型。当该LDA被训练时，它可以捕获每个用户兴趣的正确平衡(correct balance)，以及正确的比例。因而，当遵循该生成过程时，会得到平衡的推荐，推荐列表会通过一次添加一个title的方式迭代式生成：

  • 首先，为用户u学到的genre分布\(p(g \mid u)\)中抽样一个genre g，
  • 接着根据genre g从学到的分布\(p(i \mid g)\)中抽样一个电影i。

与根据\(p(i \mid u)\)进行ranking的电影相对比，Sampling出来的电影会产生更低的accuracy，其中:

\[p(i \mid u) = \sum_g p(i \mid g) \cdot p(g \mid u)\]

原因是，具有较小概率值\(p(i \mid u)\)的电影i，会在接近推荐列表的top位置的被抽样到。相反的，ranking是deterministic的，并能保证：用户u喜欢具有最大概率\(p(i \mid u)\)的电影i，会在推荐列表的top，很明显：如果学到的概率\(p(i \mid u)\)被正确估计，那么可以在test data上达到最佳的accuracy。

。。。

第二：注意，unbalanced推荐问题，不论当显示类目（例如：genres）被使用时，还是当使用latent topics或embeddings都会存在。

第三：unbalanced推荐问题会提出：不管一个电影是否属于单个genre（硬分配），或者是否属于多个genres（例如：LDA model）

3.Calibration指标

在本节中，我们描述了关于推荐电影列表的量化calibration degree的指标。我们考虑两个分布，两者都基于每个电影i的genres g分布\(p(g \mid i)\)，假设如下：

  • \(p(g \mid u)\)：用户u在过去播放过的电影集合H在genres g上的分布:
\[p(g | u) = \frac{\sum\limits_{i \in H} w_{u,i} \cdot p(g | i)}{\sum\limits_{i \in H} w_{u,i}}\]

…(2)

其中，\(w_{u,i}\)是电影i的weight，例如：用户u最近播放有多近。等式(7)有一个正则版本。

  • \(q(g \mid u)\)：推荐给user u的电影列表I在genres g上的分布：
\[q(g | u) = \frac{\sum\limits_{i \in I} w_{r(i)} \cdot p(g | i)}{\sum\limits_{i \in I} w_{r(i)}}\]

…(3)

其中，I是推荐电影的集合。电影i的weight会因为它在推荐中的rank r(i)被表示为\(w_{r(i)}\)。可能选项包括在ranking指标中所使用的weighting schemes，比如：MRR和nDCG.

有许多方法来决定这两个分布\(q(g \mid u)\)和\(p(g \mid u)\)是否相似。为了说明这样的分布从有限数据中（由N个推荐电影和M个被该用户播放电影组合）估计得到，使用零假设：两个分布是相同的。这通常将一个独立检验转化成在两个随机变量上的多项分布：genres g，以及一个影响两个电影集合(I和H)的变量。给定：N或M可能实际很小，这对于exact tests是必需的（像多项检验和fisher test）。这些tests在实际上是不可计算的。一种计算高效的方法是：渐近检验（asymptotic tests），比如：G-test或\(x^2\)-test。

我们不会计算p值，我们会忽略有限数据的大小N和M的影响，直接计算分布\(p(g \mid u)\)和\(q(g \mid u)\)。为了该目的，我们会使用KL散度作为calibration metric \(C_{KL}(p, q)\)：

\[C_{KL}(p, q) = KL(p || \hat{q}) = \sum\limits_{g} log \frac{p(g | u)}{\hat{q}(g | u)}\]

…(4)

其中，我们会使用\(p(g \mid u)\)作为target分布。如果\(q(g \mid u)\)与它相似，\(C_{KL}(p, q)\)会具有小值。给定，对于一个genre g，如果\(q(g \mid u)=0\)并且\(p(g \mid u) > 0\)，则KL散度会背离（diverge），我们会使用下式替代：

\[\hat{q}(g | u ) = (1-\alpha) \cdot q(g | u) + \alpha \cdot p(g | u)\]

…(5)

其中，\(\alpha > 0\)，\(\alpha\)值小，以便\(q \approx \hat{q}\)。在我们的实验中，我们会使用\(\alpha = 0.01\)。KL散度具有许多属性，正是在推荐中calibration degree的量化所需：

  • (1) 完美校正(perfect calibration)时，KL为0：\(p(g \mid u) = \hat{q}(g \mid u)\)
  • (2) 当\(p(g \mid u)\)很小时，对于在\(p(g \mid u)\)和\(\hat{q}(g \mid u)\)间的微小差异很敏感。例如，如果一个用户播放的genre只有2%的时间，推荐该genre 1%在KL散度上会被认为是一个较大的差异。比起（一个genre被播放50%，但推荐只有49%）的case差异要更大。
  • (3) 它喜欢更平均、并且更不极端的分布：如表1所示，如果一个用户播放一个genre 30%的时间，推荐31%该genre 会被认为要比29%要好。

这些属性确保了该用户很少播放的genres也可以在推荐列表中相应的比例被影响。作为KL散度的替代，你也可以使用其它f-散度，比如：在p和q间的Hellinger距离，\(C_H(p,q) = H(p,q) = \| \sqrt{p} - \sqrt{q} \|_2 / 2\)，其中\(\| \cdot \|_2\)表示概率向量(跨geners)的2-norm。Hellinger距离在零值上是定义良好的；它也对p和q间的小差异敏感，并且当p很小时，degree会小于KL散度。

整体calibration metric C可以通过跨所有users进行\(C(p, q)\)平均。

4.Calibration方法

推荐的calibration是一个与list相关的特性（list-property）。由于许多推荐系统以用一种pointwise/pariwise的方式进行训练，在训练中可能不包括calibration。因而建议：对推荐系统的预测列表以post-processing方式进行re-rank，这也是机器学习中一种calibrating常用方法。为了决定N个推荐电影的最优集合\(I^*\)，我们会使用最大间隔相关度MMR（maximum marginal relevance）：

\[I^* = \underset{I,|I|=N}{argmax} \lbrace (1-\lambda) \cdot s(I) - \lambda \cdot C_{KL} (p, q(I)) \rbrace\]

…(6)

其中，\(\lambda \in [0, 1]\)决定着两项间的trade-off:

  • (1) s(I)：\(s(i)\)表示电影\(i \in I\)被推荐系统预测的scores，其中：\(s(I) = \sum_{i \in I} s(i)\)。注意，你可以为每个电影的score使用一个单调转换。
  • (2) \(C_{KL}\)：calibration metric(等式4)，我们已经显式表示了在推荐电影I上的q依赖，它会在等式(6)进行优化

同时注意，更好的calibration会引起一个更低的calibration score，因此我们在最大化问题中必须使用它的负值。

在关注accuracy的推荐与calibration间的trade-off，可以通过等式(6)的\(\lambda\)进行控制。我们会考虑calibration作为推荐列表的一个重要属性，如第5节所示，它会需要一个相当大的值\(\lambda\)。

寻找N个推荐电影的最优集合\(I^*\)是一个组合优化问题，它是NP-hard的。在附录中，我们会描述该最优化问题的贪婪最优化（greedy optimization）等价于一个代理次模函数（surrogate submodular）函数的贪婪最优化。次模函数的贪婪最优化可以达到一个\((1-1/e)\)的最优化保证，其中e是欧拉数。贪婪最优化会从empty set开始，迭代式地每次添加一个电影i：在step n，当我们已经具有n-1个电影组成的集合\(I_{n-1}\)，对于集合\(I_{n-1} \cup \lbrace i \rbrace\)可以最大化等式(6)的电影i被添加进行来获得\(I_n\)。该贪婪方法具有额外优点。

  • 首先，它会生成一个关于电影的有序列表（ordered/ranked list）。
  • 第二，该贪婪方法在每个step产生的list在相同size的lists间是\((1-1/e)\)最优的。

即使我们可以生成一个关于N部电影的ranked list，用户可能只会看到前n部（n<N）的推荐，比如：剩余电影只会在下滑后在视见区（view-port）变得可见。除此之外，用户可能会自顶向下扫描关于N部电影的list。在两种情况下，次模函数的greedy optimization会自动保证推荐列表中每个sub-list的前n部电影(n<N)是(1-1/e)最优的。

注意，该方法允许一个电影i根据可能的多个genres g进行加权，如等式(2)和(3)中所用的\(p(g \mid i)\)。再者，如果你根据多个不同的categories（例如：genres、subgenres、languages、movie-vs.-TV-show, etc）对推荐列表进行calibrate，会为每个category添加一个独立的calibration项 \(C_{KL}^{(category)}\)，并使用期望的weight/importance \(\lambda^{(category)}\)。生成的多个次模函数的和(sum)仍是一个次模函数，因而最优化问题仍然有效。

5.相关概念

Calibration在机器学习中常被使用，主要在分类中，通常发现简单的post-processing方法很有效。在最近几年，calibration再获关注，特别是在机器学习的fairness中。

在推荐系统文献中，除了accuracy外还有许多指标（详见[21]），其中diversity与calibration比较接近。

5.1 Diversity

Diversity在许多papers中有定义，例如：最小冗余（minimal redundancy）或推荐items间的相似度，可以帮助避免推荐中100%都是爱情片：假设只有两种电影，最diverse的推荐为50%的爱情片和50%的动作片。如果有额外的电影类型，推荐的diversity可以通过推荐用户没观看过的其它genres来增加，比如：儿童片或记录片。Diversity不会保证将动作片的比例从0%增加到30%，从而影响用户的兴趣度。如果在accuracy和diversity之间的trade-off被选定，你可以获得well-calibrated推荐。这在实际中很难达到，因为该trade-off对于每个用户是不同的。这表明，diversity的目标并不使用合适比例来直接影响一个用户的多种兴趣。这与calibrated推荐有一个主要的不同之处。

第二个关键不同点是：diversity可以帮助用户逃脱可能的filter bubble现象，因为它可能包括用户未曾播放过的genres。而calibrated recommendations并没有提供这个重要特性。这驱使我们对calibrated推荐进行一个简单扩展，以便从用户过往兴趣之外的genres的电影可以被添加到推荐列表中：假设\(p_0(g)\)表示一个先验分布，对于所有genres g会使用正值，从而提升在推荐中的diversity——两个明显选择是：均匀分布（uniform distribution）、或所有用户在genre分布上的平均。这种diversity-promoting先验\(p_0(g)\)以及calibration target \(p(g \mid u)\)的加权平均：

\[\bar{p}(g|u) = \beta \cdot p_0(g) + (1-\beta) \cdot p(g | u)\]

…(7)

其中，参数\(\beta \in [0, 1]\)，决定了在diversity和calibration间的trade-off。这种extended calibration probability \(\bar{p}(g \mid u)\)可以被用于替代\(p(g \mid u)\)。

在许多paper中，如果一个list只有少量的冗余度或者 在items相似度低，就认为是diverse的。已经提出的大多数方法会生成这样的diverse推荐，比如：[4,15,31,32]，包括DPP(行列式点过程)【8，11】，次模最优化【1，2，19】。

第二条研究线是：在还未选择任意n-1个items ranked/displayed上（比如：一个浏览模型），对用户从推荐列表中选择第n个item的概率进行建模。该思想会产生ranking metric（称为：ERR），也被用于生成一个更diverse ranked list的方法中。

只有少量paper解决了该重要的issue：推荐会以适当比例影响用户的多种兴趣[9,25,26]，我们会在下面讨论。

比例性的思想首先在[9]中关于搜索结果多样化中提出。在[9]中，提出的指标，称为DP，本质上是一个在分布\(p(g \mid u)\)和\(g(g \mid u)\)间的平方差的修改版本。当它满足calibration metrics的性质1时，它不会表现出其它两个性质：如表1所示，对于target proportions为：60%:40%，当两个genres中具有7:3会接收更不平衡的推荐，但会与均匀5:5的情况一样，得到相同的DP=1。假设：两者都脱离6:4的理想推荐（将某一电影放到另一个genre中），根据性质（3），5:5可以比7:3接收一个更好的calibration score。性质（2）也不会满足，因为当10部电影被评建时，对于1部电影是如何与target分布相背离的程度，DP=1——理想上，该得分对于target distribution 70%:30%会更糟糕，因为它比60%:40%更极端。注意，KL散度会满足表1的性质。在[9]中，生成一个proportional list的算法会使用用于在选举(election)之后坐位安排(seat assignment)的过程，因此，每个party的坐位会与它们收来的投票数(votes)成比例。他们为该过程(procedure)开发了一个概率化版本来解决items属于多个类目的问题，并发现该方法的效果要好于在实验中的原始实验。在完美比例不能达到的情况下，会发现具有某些偏差(deviations)的一个近似解，它们的算法必须将偏差(deviaitons)看成与现有metric不同，因为他们在概念上是无关的。关于该近似解是否服从在calibrated recommendations中所期望的属性是不明显的。

在[25]中，个性化多样性(personalized diversification)从次模化（submodularity）的角度解决。而他们在[25]中提出的一个次模目标函数（等式(2)），由一个log-sum项组成，与我们附录中的等式(8)相似，它与[25]中未描述的KL散度有关。在[25]中仍未讲明的是，该次模函数的实际目标是，推荐多个与它们的weights（例如：[25]中的CTR）成比例的item-categories。

[26]中提出的metric叫BinomDiv，是精心制作的，并且满足性质(2)和(3)：例如：关于表1中的target proportions 60%:40%，7:3更极端的推荐是，比更平衡的5:5得到一个更差的分值。这对于proportionality是很重要的性质。它们的指标不满足性质1，然而，即使更放松，采用在perfect calibration情况下的相同固定值（替代0）：如果\(p(g \mid u)=q(g \mid u)\)，该指标可以采用不同值，取决于推荐列表的长度、以及genres \(p(g \mid u)\)的分布，见表1. 这有两个缺点：首先，metric的一个给定值，不能为提供一种该推荐是如何calibrate的感觉——对于一个特定用户，它只允许你根据不同推荐列表做出相对比较。第二，假如每个用户趋向于具有不同分布的兴趣/类目(interests/genres)，该指标不能简单地跨用户平均的方式来获得一个聚合指标。为了评估，该指标会转化成一个z-score。我们也发现：当推荐电影的数目超过数百时，指标计算会遭受数值下溢（numerical underflow）——这在许多应用中会引起问题，比如：top10推荐，同时也有推荐数百items的场景，比如：Netflix主页。除此之外，我们注意到，增加一个先验（prior）的思想在[26]有提及。该算法会基于最大间隔相关度（maximum marginal relevance）[6]。这些指标可能不是次模的（submodular），然而，他们可能不存在一个最优保证。

5.2 公平性（Fairness）

在机器学习领域中，fairness的重要性越来越大，例如：[33]。Fairness是避免对在总体（polulation）中特定人或人群的歧视，例如，基于gender、race、age、等。它通常与总体中个人的scores或class labels有关。

在文献中，提出了许多公平性准则（fairness criteria），包括：calibration、等可能性(equalized odds)、机会均等（equal opportunity）、统计平等（statistical parity）。[12]中提出了一种post-processing方法，使用equalized odds作为fairness-metric。[28]提出了将fairness集成到training objective中。

在CF的内容中，[29]讨论了在user-base中的少量亚种族（sub-populations，例如：人口不均衡），以及更低活跃的亚种族（例如：提供更少评分的人）可能会收到更偏的推荐。除此之外，[29]还关注在rating prediction和RMSE，替代隐式反馈数据和ranking metrics的更相关场景。

在该paper中，我们会考虑fairness的一个完整概念：除了考虑人的fairness外，我们会考虑一个用户多种兴趣(various interests)上的公平性（fairness），目标是根据它相应的兴趣比例进行影响。在本节剩余部分，我们会描述，为什么calibration criteria对于fairness的非标准概念特别有用。

如[16]所示，calibration和equalized odds/equal opportunity不会被同时满足（精确，非近似）——除了两个特例：当机器学习模型做出perfect predictions（它们会被公平对待），或者当不同分组的用户具有相同的base rate时，例如：相同比例的positive classification-labels，它通常不会在真实中hold。假设一个用户通常使用不同比例播放genres（比如：70%爱情片，30%动作片），这两种genres（在fairness文献中被称为”groups”）的base rate很明显不同，对于在这两个genres中的电影的平均预测得分也不同。因此，fiarness criteria equalized odds、equal opportunity以及statistical parity不能立即应用到我们的context中。这驱使我们在推荐中将calibration作为一种合适的fairness criteria。

参考