yahoo在《Ad Serving Using a Compact Allocation Plan》提了：
摘要
大部分在线展示广告通过保证合同（guaranteed contracts）进行售卖：一个publisher会保证advertiser一部分特定数目的用户，。
ALE atari介绍
关于ALE (Arcade Learning Environment)的介绍来自于Marlos C. Machado发表的paper:《Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents》
1.介绍
ALE (电玩学习环境：Arcade Learning Environment)： ALE提供了一个关于Atari 2600游戏的数百个游戏环境的接口，这些游戏每个都是不同的、很有趣。ALE提供了对reinforcement learning, model learning, model-based planning, imitation learning, transfer learning, 和 intrinsic motivation的研究挑战。更重要的是，它为这些问题提供了一个严格的testbed来评估和比较方法。我们使用AI技术(reinforcement learning/learning)通过开发和测试domain-independent agents来展示ALE。我们也提供了一个evaluation技术，在超过55个不同游戏上有结果。
#
略…
接口
ALE在Stella（一个开源的Atari 2600模拟器）上构建。它允许用户通过接收joystick动作、发送screen/RAM信息、并模拟平台的方式来与Atari 2600交互。ALE提供了一个游戏处理层（game-handling layer），它通过标记累积得分、以及游戏是否已经结束，可以将每个游戏转化成一个标准的增强学习问题。缺省的，每个observation包含了单个游戏屏幕（game screen: frame）：一个关于7bit像素的2D数组，160 pixels宽 x 210 pixels高。action space包含了18个离散（discrete）的actions，它们通过操纵杆控制器（joystick controller）来定义。game-handling layer也指定了需要玩一个特定游戏的关于actions的最小集合。当运行时，该仿真器会每秒生成60帧，最高速度的仿真可以达到每秒6000帧。在每个time-step上的reward通过game basis来定义，通常通过在帧之间的得分(score/points)的不同来指定。一个episode会在reset命令后的第一帧(frame)处开始，当游戏结束时终止。game-handling layer也提供了在预定义帧数后终止episode的能力。user因此可以通过单个公共接口来访问数十个游戏，并可以很简单地增加新游戏。
图1 18个action
ALE也提供了保存(save)和恢复(restore)仿真器的状态(state)的功能。当发出一个save-state命令时，ALE会保存关于当前游戏所有相关数据，包括RAM、寄存器（registers）、地址计数器（address counters）的内容。restore-state命令会resets该游戏到之前saved state时的状态。这允许ALE作为一个生成模型来研究主题：planning、model-based RL。
图2 load/save
3.Benchmark结果
Planning 和 reinforcement learning是可以在ALE framework中研究的两个主要AI问题。在benchmark results中我们的目标是两者：第一，这些结果提供了一个对于传统技术的baseline performance，并确立了一个与更高级方法的比较点。第二，这些结果可以做经验上的validation。
3.1 RL
我们使用SARSA(\(\lambda\))来提供benchmark结果，这是一种model-free RL的传统技术。注意，在RL setting中，agent不会访问一个关于游戏动态性（game dynamics）的模型。在每个time-step上，agent会选择一个action并接收一个reward和一个observation，该agent的目标是：最大化它的累积回报（acumulated reward）。在这些实验中，我们会讨论：线性函数近似、replacing traces, e-greedy exploration。
3.1.1 特征构建
Basic：Basic方法来自于Naddaf’s BASS (2010)，会对Atari 2600 screen上的颜色进行编码。Basic方法首先移除了图片背景色，它通过在每个像素位置的颜色频率存储在一个histogram中。每个游戏背景是离线预计算好的，使用从sample trajectories中收集到的18000个observations。sample trajectories根据一个人工提供（human-provided）的trajectory，取随机数目的steps、并且随机均匀选择actions的方式来生成。该screen接着被划分成16x14 tiles。Basic会为每个128种颜色、每个tiles生成一个binary feature，共28672个features。
BASS：与BASIC相似。首先，BASS的特征集是pairwise组合。第二，BASS使用一个更小的、 8色的encoding来确保pairwise组合数目保持可跟踪。
DISCO：DISCO方法的目标是检测在Atari 2600 screen中的对象。为了这样做，与Basic方法生成的sample trajectories相似，它会首先预处理来自sample trajectories的36000个observations。DISCO会执行背景减少steps。接着抽取的对象标记(label)成classes。在实际训练期间，DISCO会infer所检测对象的class label，并将它们的位置和速度使用tile coding进行编码。
LSH：LSH方法会将原始的Atari 2600 screens使用Locally sensitive hashing映射到关于binary features的一个小集合上。
RAM：RAM方法会使用整个不同的observation space。它直接将Atari 2600的1024位内存进行observes。RAM的每一位可以当成一个binary feature提供。
3.1.2 评估技术
我们首先构建两个集合：一个用于training、一个用于testing。我们使用training games来进行调参，testing games用于评估。我们的training set包含了5个游戏：Asterix, Beam Rider, Freeway, Seaquest 和 Space Invaders。参数搜索涉及到发现SARSA算法最适合的参数值：比如：learning-rate、exploration rate、discount factor、decay rate \(\lambda\)。我们也会搜索特征生成参数的空间，例如：Bass agent的abstraction level等。我们的testing set通过从381个游戏中半随机选择。这些游戏中，128个游戏有它的wikipedia介绍页，具有单人模式、没有成人主题、可以在ALE中进行模拟。50个游戏被随机选中来形成test set。
在每个游戏上，每个方法的评估执行如下。一个episode从reset命令后的第一帧开始，当游戏结束条件被检测到、或者在5分钟后（即18000帧）玩后时结束。在episode期间，agent会每5帧进行acts，或者等价于gameplay的每秒12次。RL的实验(trial)包含了5000个training episodes，以及500个evalution episodes。agent的效果通过在evaluation episodes期间的平均得分进行measure。对于每个游戏，我们会在30个实验上报告我们的平均效果。
…
略
参考
xDeepFM介绍
前几天微软提出了一个xDeepFM算法：
介绍
传统交叉特征工程主要有三个缺点，以下部分来自paper：
- 1.获取高质量特征代价高昂
- 2.大规模预测系统(比如：推荐系统)，存在大量原始特征(raw features)，很难人工抽取所有交叉特征
- 3.人工交叉特征不能泛化到在训练数据中未见过的交叉上
FM会将每个特征i嵌入到一个隐因子向量 \(v_i = [v_{i1}, v_{i2}, ..., v_{iD}]\)上，pairwise型特征交叉可以被建模成隐向量的内积：\(f^{(2)}(i,j)=\langle v_i, v_j \rangle x_i x_j\)。在本paper中，我们使用术语bit来表示在隐向量中的一个元素（比如：\(v_{i1}\)）。经典的FM可以被扩展到专门的高阶特征交叉上，但一个主要缺点是：会建模所有的特征交叉，包括有用组合和无用组合。无用组合会引入噪声、以及效果的下降。最近几年，DNNs越来越流行。利用DNNs可以学习复杂和可选择的特征交叉。[46]提出来FNN用于学习高阶特征交叉。它会使用对于field embedding的预训练FM，然后应用于DNN。[31]提出了PNN，它不依赖预训练的FM，而是在embedding layer和DNN layer之间引入了一个product layer。FNN和PNN的主要缺点是，它们主要更多关注高阶特征交叉，而非低阶交叉。Wide&Deep模型和DeepFM模型通过引入混合结构克服了上面的缺点，它包含了一个shallow组件以及一个deep组件，可以学到memorization和generalization。因而可以联合学习低阶和高阶特征交叉。
上面的所有模型都使用DNN来学习高阶特征交叉。然而，DNN可以以一个隐式的方式建模高阶特征交叉。由DNN学到的最终函数可以是任意形式，关于特征交叉的最大阶数（maximum degree）没有理论上的结论。另外，DNNs在bit-wise级别建模征交叉，这与FM框架不同（它会在vector-wise级别建模）。这样，在推荐系统的领域，其中DNN是否是用于表示高阶特征交叉的最有效模型，仍然是一个开放问题。在本paper中，我们提供了一个基于NN的模型，以显式、vector-wise的方式来学习特征交叉。我们的方法基于DCN（Deep&Cross Network）之上，该方法能有效捕获有限阶数（bounded degree）的特征交叉。然而，我们会在第2.3节讨论，DCN将带来一种特殊形式的交叉。我们设计了一种新的压缩交叉网络CIN(compressed interaction network)来替换在DCN中的cross network。CIN可以显式地学到特征交叉，交叉的阶数会随着网络depth增长。根据Wide&Deep模型和DeepFM模型的精神，我们会结合显式高阶交叉模块和隐式交叉模型，以及传统的FM模块，并将该联合模型命名为“eXtreme Deep Factorization Machine (xDeepFM)”。这种新模型无需人工特征工程，可以让数据科学家们从无聊的特征搜索中解放出来。总结一下，主要有三个贡献：
- 提出了一种新模型xDeepFM，可以联合训练显式和隐式高阶特征交叉，无需人工特征工程
- 设计了CIN来显式学习高阶特征交叉。我们展示了特征交叉的阶（degree）会在每一层增加，特征会在vector-wise级别进行交叉。
- 我们在三个数据集中进行了实验，结果展示xDeepFM效果好于其它state-of-art模型
2.PRELIMINARIES
2.1 Embedding Layer
在CV或NLP领域，输入数据通常是图片或文本信号，它们空间相关（spatially correlated）或时序相关(temporally correlated)，因而DNN可以被直接应用到dense结构的原始特征上。然而，在推荐系统中，输入特征是sparse、高维、没有明显地空间相关或时序相关。因此，multi-field类别形式被广泛使用。例如，一个输入实例为： [user_id=s02,gender=male,organization=msra,interests=comedy&rock]
通过field-aware one-hot进行编码成高维稀疏特征:
\[[\underbrace{0, 1, 0, 0, ..., 0}_{userid}] [\underbrace{1, 0}_{gender}] [\underbrace{0, 1, 0, 0, ..., 0}_{organization}] [\underbrace{0, 1, 0, 1, ..., 0}_{interests}]\]在原始特征输入上使用一个embedding layer，可以将它压缩到一个低维、dense、real-value vector上。如果field是一阶的（univalent），feature embedding被当成field embedding使用。以上述实例为例，特征（male）的embedding被当成field gender的embedding。如果field是多阶的(multivalent)，feature embedding的求和被用于field embedding。embedding layer如图1所示。embedding layer的结果是一个wide concatenated vector：
\[e = [e_1, e_2, ..., e_m]\]其中，m表示fields的数目，\(e_i \in R^D\)表示一个field的embedding。尽管实例的feature长度可以是多变的，它们的embedding具有相同的长度 m x D, 其中D是field embedding的维数。
图1: field embedding layer。本例中embedding的维度是4
2.2 隐式高阶交叉
FNN, Deep&Cross，以及Wide&Deep的deep part会使用一个在field embedding vector e上的feed-forward神经网络来学习高阶特征交叉。forward process是：
\[x^1 = \delta(W^{(1)} e + b^1)\]…(1)
\[x^k = \delta(W^{(k)} x^{(k-1)} + b^k)\]…(2)
其中，k是layer depth，\(\delta\)是激活函数，\(x^k\)是第k层的output。可视化结构与图2展示的非常像，但不包括FM layer或Product layer。该结构会以bit-wise的方式建模交叉。也就是说，相同field embedding vector中的元素也会相互影响。
PNN和DeepFM在上述结构上做了小修改。除了在embedding vector e上应用了DNNs外，它们在网络中添加了一个2-way interaction layer。因而，bit-wise和vector-wise的交叉都能在模型中包含。PNN和DeepFM中主要不同是，PNN会将product layer的输出连接到DNNs中，而DeepFM会直接将FM layer连接给output unit。
图2: DeepFM和PNN的架构。我们复用了符号，其中红色边表示weight-1 connections（没有参数），灰色边表示normal connections（网络参数）
2.3 显式高阶交叉
[40]提出的Cross Network（CrossNet）它的结构如图3所示:
图3:
它可以显式建模高阶特征交叉。不同于经典的fully-connected feed-forward network，它的hidden layers通过以下的cross操作进行计算：
\[x_k = x_0 x_{k-1}^T w_k + b_k + x_{k-1}\]…(3)
其中，\(w_k, b_k, x_k \in R^{mD}\)是第k层的weights，bias以及output。对于CrossNet能学到一个特殊类型的高阶交叉这一点我们有争论，其中，CrossNet中的每个hidden layer是一个关于\(x_0\)的标量乘积。
theorem 2.1: 考虑到一个k层cross network，第i+1层的定义为：\(x_{i+1} = x_0 x_i^T w_{i+1} + x_i\)。接着，cross network的output \(x_k\)是一个关于\(x_0\)的标量乘积。
证明如下：
k=1时，根据矩阵乘法的结合律和分配律，我们具有：
\[x_1 = x_0 (x_0^T w_1) + x_0 = x_0 (x_0^T w_1 +1) = \alpha^1 x_0\]…(4)
其中，标量\(\alpha^1 = x_0^T w_1 + 1\)实际上是关于\(x_0\)的线性回归。其中，\(x_1\)是关于\(x_0\)的一个标量乘。假设标量乘适用于k=i。对于k=i+1, 我们可以有：
\[x_{i+1} = x_0 x_i^T w_{i+1} + x_i = x_0 (( \alpha^i x_0)^T w_{i+1}) + \alpha^i x_0 = \alpha^{i+1} x_0\]…(5)
其中，\(\alpha^{i+1} = \alpha^i (x_0^T w_{i+1} + 1)\)是一个标量。其中，\(x_{i+1}\)仍是一个关于\(x_0\)的标量乘。通过引入hypothesis，cross network的output \(x_k\)是一个关于\(x_0\)的标量乘。
注意，\(标量乘(scalar multiple)\)并不意味着\(x_k\)是与\(x_0\)是线性关系的。系数\(\alpha^{i+1}\)是与\(x_0\)敏感的。CrossNet可以非常有效地学到特征交叉（复杂度与一个DNN模型对比是微不足道的），然而，缺点是：
- (1) CrossNet的输出受限于一个特定的形式，每个hidden layer是关于\(x_0\)的一个标量乘
- (2) 交叉是以bit-wise的方式进行
3.新模型
3.1 CIN
我们设计了一个新的cross network，命名为CIN（Compressed Interaction Network），具有如下注意事项：
- (1) 交叉是在vector-wise级别上进行，而非bit-wise级别
- (2) 高阶特征的交叉显式衡量
- (3) 网络的复杂度不会随着交叉阶数进行指数增长
由于一个embedding vector被看成是一个关于vector-wise 交叉的unit，后续我们会将field embedding公式化为一个矩阵：\(X^0 \in R^{m \times D}\)，其中，假设\(H_0=m\)，\(H_k\)表示在第k层的(embedding)feature vectors的数量。对于每一层，\(X^k\)通过以下方式计算：
\[x_{h,*}^k = \sum_{i=1}^{H_{k-1}} \sum_{j=1}^{m} W_{ij}^{k,h} (x_{i,*}^{k-1} \circ x_{j,*}^{0})\]…(6)
其中\(1 \le h \le H_i\)，\(W^{k,h} \in R^{H_{k-1} \times m}\)是第h个feature vector的参数矩阵，\(\circ\)表示Hadamard product，例如：\(\langle a_1,a_2,a_3 \rangle \circ \langle b_1,b_2,b_3 \rangle = \langle a_1 b_1, a_2 b_2, a_3 b_3 \rangle\)。注意，\(X^k\)通过在\(X^{k-1}\)和\(X^0\)间的交叉产生，其中，特征交叉会被显式衡量，交叉的阶数会随着layer depth增长。CIN的结构与RNN非常相似，其中下一个hidden layer的outputs取决于最近一个(the last)的hidden layer和一个额外的input。我们在所有layers上都持有embedding vectors的结构，这样，即可在vector-wise级别上使用交叉。
图4
有意思的是，等式(6)与CNN具有很强的关联。如图4a所示，我们引入了一个内部张量（intermediate tensor） \(Z^{k+1}\)，其中，它是hidden layer\(X^k\)和原始特征矩阵\(X^0\)的外积（outer products：沿着每个embedding维度）。\(Z^{k+1}\)被看成是一个特殊类型的图片，\(W^{k,h}\)看成是一个filter。我们如图4b所示跨\(Z^{k+1}\)沿着该embedding dimension(D)滑动该filter，获得一个hidden vector \(X_{i,*}^{k+1}\)，这在CV中通常被称为一个feature map。在CIN命名中所使用的术语”compressed”表示了第k个hidden layer会将 \(H_{k-1} \times m\)向量的隐空间压缩到\(H_k\)向量中。
图4c提供了CIN的一个总览。假设T表示网络的深度。每个hidden layer \(X^k, k \in [1,T]\)具有一个与output units的连接。我们首先在hidden layer的每个feature map上使用sum pooling：
\[p_i^k = \sum_{j=1}^D X_{i,j}^k\]…(7)
其中，\(i \in [1, H_k]\)。这样，我们就得到一个pooling vector：\(p^k = [p_1^k, p_2^k, ..., p_{H_k}^k]\)，对于第k个hidden layer相应的长度为\(H_k\)。hidden layers的所有polling vectors在连接到output units之前会被concatenated：\(p^{+} = [p^1, p^2, ..., p^T] \in R^{\sum_{i=1}^T H_i}\)。如果我们直接使用CIN进行分类，output unit是在\(p^+\)上的一个sigmoid节点：
\[y = \frac{1} {1 + exp(p^{+^T} w_o)}\]…(8)
其中，\(w^o\)是回归参数。
3.2 CIN详解
我们对CIN进行分析，研究了模型复杂度以及潜在的效果。
3.2.1 空间复杂度
在第k层的第h个feature map，包含了\(H_{k-1} \times m\)个参数，它与\(W^{k,h}\)具有相同的size。因而，在第k层上具有\(H_k \times H_{k-1} \times m\)个参数。考虑到对于output unit的当前最近(the last)的regression layer，它具有\(\sum_{k=1}^T H_k\)个参数，CIN的参数总数是 \(\sum_{k=1}^T H_k \times (1 + H_{k-1} \times m )\)。注意，CIN与embedding dimension D相互独立。相反的，一个普通的T-layers DNN包含了\(m \times D \times H_1 + H_T + \sum_{k=2}^T H_k \times H_{k-1}\)个参数，参数的数目会随着embedding dimension D而增长。
通常，m和\(H_k\)不会非常大，因而，\(W^{k,h}\)的规模是可接受的。当有必要时，我们可以利用一个L阶的分解，使用两个小的矩阵\(U^{k,h} \in R^{H_{k-1} \times L}\)以及\(V^{k,h} \in R^{m \times L}\)来替换\(W^{k,h}\)：
\[W^{k,h} = U^{k,h} (V^{k,h})^T\]…(9)
其中\(L \ll H\)以及\(L \ll m\)。出于简洁性，我们假设每个hidden layer都具有相同数目（为H）的feature maps。尽管L阶分解，CIN的空间复杂度从\(O(mTH^2)\)下降到\(O(mTHL + TH^2L)\)。相反的，普通DNN的空间复杂度是\(O(m D H + TH^2)\)，它对于field embedding的维度D是敏感的。
3.2.2 时间复杂度
计算tensor \(Z^{k+1}\)的开销是O(mHD)。由于我们在第一个hidden layer上具有H个feature maps，计算一个T-layers CIN会花费\(O(m H^2 DT)\)时间。相反的，一个T-layer plain DNN，会花费\(O(m H D + H^2 T)\)时间。因此，CIN的主要缺点是在时间复杂度上。
3.2.3 多项式近似（Polynomial Approximation）
接下来，我们检查了CIN的高阶交叉属性。出于简洁性，我们假设，在hidden layers上的feature maps数目，等于fields m的数目。假设[m]表示小于或等于m的正整数集。在第1层上的第h个feature map，表示为\(x_h^1 \in R^D\)，通过下式计算：
\[x_h^1 = \sum_{i \in [m], j \in [m]} W_{i,j}^{1,h} (x_i^0 \circ x_i^0)\]…(10)
因此，在第1层的每个feature map会使用\(O(m^2)\)个系数来建模pair-wise特征交叉。相似的，在第2层的第h个feature map为：
\[x_h^2 = \sum_{i \in [m], j \in [m]} W_{i,j}^{2,h} (x_i^1 \circ x_j^0) \\ = \sum_{i \in [m], j \in [m]} \sum_{l \in [m], k \in [m]} W_{i,j}^{2,h} W_{l,k}^{1,i} (x_j^0 \circ x_k^0 \circ x_l^0\]…(11)
注意，l和k相关的所有计算在前一个hidden layer已经完成。我们在等式(11)扩展的因子是为了清晰。我们可以观察到，在第二层的每个feature map会使用\(O(m^2)\)新参数来建模3-way交叉。
一个经典的k阶多项式具有\(O(m^k)\)系数。我们展示了CIN会逼近这类型多项式，根据一个feature maps链，只需要\(O(k m^3)\)个参数。通过引入hypothesis，我们可以证明，在第k层的第h个feature map为：
\[x_h^k = \sum_{i \in [m], j \in [m]} W_{i,j}^{k,h} (x_i^{k-1} \circ x_j^0) \\ = \sum_{i \in [m], j \in [m]} ... \sum_{r \in [m], t \in [m]} \sum_{l \in [m], s\in [m]} W_{i,j}^{k,h} ... W_{l,s}^{1,r} (x_j^0 \circ ... \circ x_s^0 \circ x_l^0)\]…(12)
为了更好地演示，我们参考了[40]的注解。假设\(\alpha = [\alpha_1, ..., \alpha_m] \in N^d\)表示一个multi-index，其中\(\| \alpha \| = \sum_{i=1}^m \alpha_i\)。我们会从\(x_i^0\)中忽略原始的上标，使用\(x_i\)来表示它，因为对于最终展开的表达式，我们只关心来自第0层（等同于field embedding）的feature maps。现在，使用一个上标来表示向量操作，比如\(x_i^3 = x_i \circ x_i \circ x_i\)。假设\(V P_k(X)\)表示一个multi-vector 多项式的阶数k：
\[V P_k(X) = \{ \sum_{\alpha} w_{\alpha} x_1^{\alpha_1} \circ x_2^{\alpha_2} \circ ... \circ x_m^{\alpha_m} | 2 \le | \alpha | \le k \}\]…(13)
在该类中的每个向量多项式都具有\(O(m^k)\)个系数。接着，我们的CIN接似系数\(w_{\alpha}\)：
\[\hat{w}_{\alpha} = \sum_{i=1}^m \sum_{j=1}^m \sum_{B \in P_{\alpha}} \prod_{t=2}^{|\alpha|} W_{i, B_t}^{t,j}\]…(14)
其中，\(B=[B_1, B_2, ..., B_{\| \alpha \|}]\) 是一个multi-index，\(P_\alpha\)是索引(\(1, ..., 1, ..., m, ..., m\))的所有排列。
3.3 与隐式网络的组合
在第2.2节，plain DNNs可以学到隐式高阶特征交叉。由于CIN和plain DNNs可以互补，一个直观的做法是，将这两种结构进行组合使模型更强。产生的模型与Wide&Deep和DeepFM非常像。结构如图5所示，我们将新模型命名为eXtreme Deep Factorization Machine（xDeepFM），一方面，它同时包含了低阶和高阶特征交叉；另一方面，它包含了隐式特征交叉和显式特征交叉。它产生的output unit如下：
\[\hat{y} = \sigma(w_{linear}^T a + w_{dnn}^T x_{dnn}^k + w_{cin}^T p^{+} + b)\]…(15)
其中，\sigma为sigmoid函数，a是原始特征。\(x_{dnn}^k, p^{+}\)分别是是plain DNN和CIN的outputs。\(w_*\)和b是可学习的参数。对于二分类，loss函数为log loss：
\[L = - \frac{1}{N} \sum_{i=1}^N y_i log \hat{y}_i + (1-y_i) log(1-\hat{y}_i)\]…(16)
其中，N是训练实例的总数。Optimization过程是最小化下面的目标函数：
\[J = L + \lambda_{*} \| \theta \|\]…(17)
其中\(\lambda_{*}\)表示正则项，\(\theta\)表示参数集，包含linear part，CIN part，DNN part。
图5: xDeepFM的结构
3.3.1 与FM和DeepFM的关系
假设所有field是一阶的（univalent）。如图5所示，当depth和CIN part的feature maps同时设为1时，xDeepFM就是DeepFM的一个泛化，通过为FM layer学习线性回归权重实现（注意，在DeepFM中，FM layer的units直接与output unit相连，没有任何系数）。当我们进一步移去DNN part，并同时为该feature map使用一个constant sum filter（它简单采用输入求和，无需任何参数学习），接着xDeepFM就变成了传统的FM模型。
4.实验
实验主要回答下述问题：
- (Q1) CIN在高阶特征交叉学习上是如何进行的？
- (Q2) 对于推荐系统来说，将显式和隐式高阶特征交叉相组合是否是必要的？
- (Q3) xDeepFM的网络设置如何影响效果？
4.1 实验设置
4.1.1 数据集
1. Criteo Dataset：ctr预测的benchmarking dataset，对外开放。给定一个用户和他访问的页面，目标是预测它点击一个给定广告的概率。
2. Dianping Dataset：收集了6个月的关于大众点评的用户check-in活动用于餐厅推荐实验。给定一个用户的profile，一个餐厅的相应属性，该用户最近三次访问POIs（point of interest），我们希望预测它访问该餐厅的概率。对于在一个用户的check-in样本中的每个餐厅，我们会通过POI流行度抽样出在3公里内的4个餐厅作为负样本。
3.Bing News Dataset.：Bing News是微软Bing搜索引擎的一部分。我们收集了在新闻阅读服务上连续5天的曝光日志。使用前3天数据用于训练和验证，后两天数据用于测试。
对于Criteo dataset和Dianping dataset，随机将样本划分为8:1:1进行训练、验证、测试。三个数据集的特性如表1所示。
表1:评估数据计的统计。
4.1.2 评估metrics
我们使用两种metrics：AUC和LogLoss。有时更依赖logloss，因为我们需要使用预测概率来估计一个排序系统带来的收益（比如常见的CTR x bid）
4.1.3 Baselines
我们比较了xDeepFM, LR, FM, DNN, PNN, Wide&Deep, DCN, DeepFM.
4.1.4 Reproducibility
使用tensorflow来实现模型。每个模型的超参数通过在validation set上进行grid-searching调参，然后选择最好的settings。
- learning rate设置为0.001.
- optimization方法使用Adam。
- mini-batch size=4096.
- 对于DNN, DCN, Wide&Deep, DeepFM和xDeepFM，使用L2正则，对应的\(\lambda=0.0001\)
- 对于PNN，使用dropout=0.5
- 每层neurons数目的缺省setting为：
- (1) DNN layers为400
- (2) 对于Criteo dataset，CIN layers为200; 对于DIanping和Bing News datasets，CIN layers=100
- 由于本文主要关注网络结构，所有field embedding的维度统一设为固定值=10.
- 本试验在并行化在5块tesla K80 GPUs上跑.
- 源码为： https://github.com/ Leavingseason/ xDeepFM
效果展示部分:
表3: depth列表示单模型中的最佳深度，分别表示(cross layers, DNN layers)
4.2 Q1: 单一Neural组件间的效果比较
我们想知道CIN单独是如何执行的。注意FM会显式衡量2阶特征交叉，DNN模型可以隐式衡量高阶特征交叉，CrossNet尝试使用较少参数来建模高阶特征交叉，CIN则会显式建模高阶特征交叉。由于它实际依赖于数据集，单一模型（individual model）间的比较优势没有理论保证。例如，如果实际数据集不需要高阶特征交叉，FM可能是最好的单一模型。对于该实验，我们并不期望哪个模型表现最好。
表2展示了单一模型在三个实际数据集上的效果。令人惊讶的是，CIN的表现都要好些。另一方面，结果表明，对于实际数据集，稀疏特征上的高阶交叉是必要的，可以证实：DNN，CrossNet, CIN的效果要远好于FM。另一方面，CIN是最好的单一模型，图中展示了CIN在建模高阶特征交叉上的效果。注意，一个k-layer的CIN可以建模k阶的特征交叉。有趣的是，在Bing News dataset上，它会采用5 layers的CIN来达到最佳结果。
表2: 不同数据集下的模型表现。Depth列表示每个模型最好的网络深度
4.3 Q2: 集成模型的效果
xDeepFM会将CIN和DNN集成一个end-to-end模型。而CIN和DNN能cover在特征交叉学习上两种不同的属性，我们感兴趣的是，是否确实有必要将两者组合在一起进行explicit和implicit的joint learning。这里，我们比较了一些比较强的baselines，如表3所示。另一个有意思的观察是，所有基于neural的模型并不需要非常深的网络结构来达到最佳效果。常见的depth超参数设置为2或3, xDeepFM的最佳深度是3,可以表示最多学习4阶的交叉。
4.4 Q3: 超参数学习
- 1.hidden layers的数目
- 2.每层的neurons数目
- 3.激活函数
参考
transformer介绍
google在2017年paper《Attention Is All You Need》提出了transformer，我们可以看下：
1.介绍
在序列建模(sequence modeling)和转换问题(transduction problems，比如：语言建模和机器翻译)上，RNN, LSTM和GRNN已经成为state-of-art的方法。大多数努力源自于recurrent语言模型和encoder-decoder架构的持续推动。
recurrent模型通常会沿着输入和输出序列的符号位置(symbol position)进行因子计算。在计算时对位置（position）进行排列，他们可以生成一个hidden states \(h_t\)的序列，它是关于前一hidden state \(h_{t-1}\)和位置t做为输入的一个函数。这种天然的序列特性排除了在训练样本中的并发性(这对于更长序列长度很重要)，因为内存约束会限制在样本上进行batching。最近工作表明，因子分解tricks[18]和条件计算[26]可以在计算效率上进行有效提升，同时也会提升模型效果。然而，序列化计算的基本限制仍然存在。
Attention机制已经在许多任务中成为序列建模（sequence modeling）和转化模型（transduction model）的不可欠缺的一个部件，它可以在无需考虑input或output序列上的距离[2,16]的情况下来建模依赖(dependencies)。除了极少的cases外，几乎所有这样的attention机制都会与一个recurrent network一起使用。
在该工作中，我们提出了Transformer，这种模型结构可以避免recurrence，它完全依赖attention机制来抽取在input和output间的全局依赖性。Transformer允许更大的并行度(parallelization)，在eight P100 GPUs上训练12小时后，在翻译质量上可以达到一种新的state-of-art效果。
2.背景
减小序列化计算开销的目标，也构成了Extended Neural GPU [20], ByteNet [15] and ConvS2S [8]的基础，它们都使用CNN作为基本构建块，对所有input和output positions并行计算hidden representations。在这些模型中，两个专门的input或output positions的相关信号所需要的ops数目，会随着positions间的距离而增长：这对于ConvS2S是线性的，对于ByteNet是成log关系。这使得很难学习在较远位置（distant positions）间的依赖[11]。在Transformer中，操作（operations）的数目可以减小到常数级别，虽然在有效识别率上会有损失的代价（因为会对attention-weighted positions进行平均），我们会使用第3.2节中的Multi-Head Attention来消除这现象。
self-attention，有时被称为”intra-attention”，是一种与单个序列上不同位置有关的attention机制，它的目的是计算该序列的一种表示（representation）。self-attention已经被成功用于许多任务，包括：阅读理解(reading comprehension)、抽象式摘要(abstractive summarization)、文字蕴含（textual entailment）、独立句子表示任务[4,22,23,19]。
end-to-end memory networks基于一个recurrent attention机制（而非基于sequence-aligned recurrence），已经展示出在单语言问答上和语言建模任务上很好的效果[28]。
据我们所知，Transformer是首个完全依赖于self-attention的转换模型（transduction model），它无需使用sequence-aligned RNNs或convolution，就可以计算input和output的表示(representations)。在以下部分，我们会描述Transformer、motivation self-attention、以及在模型上的优点[14,15]，[8]。
3.模型结构
大多数比赛采用的神经序列转换模型(neural sequence transduction models)都有一个encoder-decoder结构[5,2,29]。这里，encoder会将一个关于符号表示\((x_1, \cdots, x_n)\)的输入序列映射到一个连续表示\(z=(z_1, \cdots, z_n)\)的序列上。在给定z后，decoder接着生成一个关于符号(symbols)的output序列\((y_1, \cdots, y_m)\)，一次一个元素。在每个step上，模型是自回归的（auto-regressive），当生成下一输出时，它会消费前面生成的符号作为额外输入。
Transformer会遵循这样的总体架构：它使用stacked self-attention、point-wise FC-layers的encoder-decoder，如图1的左右所示：
图1 Transformer模型结构
3.1 Encoder Stacks和Decoder Stacks
Encoder：encoder由一个N=6的相同层（identical layers）的stack组成。每一layer具有两个sub-layers。第1个是一个multi-head self-attention机制，第2个是一个简单的position-wise FC 前馈网络。我们在两个sub-layers的每一个上采用一个residual connection[10]，后跟着layer nomalization[1]。也就是说：每一sub-layer的output是 \(LayerNorm(x + Sublayer(x))\)，其中Sublayer(x)是通过sub-layer自身实现的函数。为了促进这些residual connections，模型中的所有sub-layers以及embedding layers会生成维度 \(d_{model}=512\)的outputs。
Decoder：该decoder也由一个N=6的相同层（identical layers）的stacks组成。除了包含在每个encoder layer中的两个sub-layers之外，decoder会插入第三个sub-layer，从而在encoder stack的output上执行multi-head attention。与encoder相似，我们在每个sub-layers周围采用residual connections，后跟layer normalization。同时我们在decoder stack中修改了self-attention sub-layer，来阻止position与后序位置有联系。这种masking机制，结合上output embeddings由一个位置偏移(offset by one position)的事实，可以确保对于位置i的预测只依赖于在位置小于i上的已知outputs。
3.2 Attention
attention函数可以被描述成：将一个query和一个key-value pairs集合映射到一个output上，其中：query, keys, values和output都是向量(vectors)。output由对values进行加权计算得到，其中为每个value分配的weight通过query和对应的key的一个兼容函数计算得到。
图2 (左) Scaled Dot-Product Attention (右) Multi-Head Attention，包含了并行运行的多个attention layers
3.2.1 归一化点乘Attention（Scaled Dot-Product Attention）
我们将这种特别的attention称为”Scaled Dot-Product Attention”（图2）。输入包含：querys、维度为\(d_k\)的keys、以及维度为\(d_v\)的values。我们会计算query和所有keys的点乘（dot products），每个点积都会除以\(\sqrt{d_k}\)，并使用一个softmax函数来获取在values上的weights。
实际上，我们会同时在一个queries集合上计算attention函数，并将它们打包成一个矩阵Q。keys和values也一起被加包成矩阵K和V。我们会计算矩阵的outputs：
\[Attention(Q, K, V) = softmax(\frac{Q K^T}{ \sqrt{d_k}}) V\]…(1)
两种最常用的attention函数是：additive attention[2]，dot-product（multiplicative） attention。dot-product attention等同于我们的算法，除了缩放因子\(\frac{1}{\sqrt{d_k}}\)。additive attention会使用一个单hidden layer的前馈网络来计算兼容函数。两者在理论复杂度上很相似，dot-product attention更快，空间效率更高，因为它使用高度优化的矩阵乘法代码来实现。
如果\(d_k\)值比较小，两种机制效果相似; 如果\(d_k\)值很大，additive attention效果要好于未经缩放的dot-product attention。我们怀疑：对于具有较大的\(d_k\)值，dot-product会更大，从而将softmax函数推到具有极小梯度值的区域上。为了消除该影响，我们将dot-product缩放至\(\frac{1}{\sqrt{d_k}}\)。
3.2.2 Multi-Head Attention
我们不会使用\(d_{model}\)维的keys、values和queries来执行单个attention函数，我们发现：使用学到的不同线性投影将queries、keys和values各自投影到\(d_k\)、\(d_k\)、\(d_v\)维上是有好处的。在关于queries、keys和values的每一个投影版本上，我们会并行执行attention函数，生成\(d_v\)维的output values。这些值被拼接在一起(concatenated)，再进行投影，产生最后值，如图2所示。
Multi-head attention允许模型联合处理在不同位置处来自不同表示子空间的信息。使用单个attention head，求平均会禁止这样做。
\[MultiHead(Q, K, V) = Concat(head_1, \cdots, head_h) W^O \\ head_i = Attention(Q W_i^Q, KW_i^K, V W_i^V)\]其中，投影是参数矩阵：
\[W_i^Q \in R^{d_{model} \ \ \times d_k}, \\ W_i^K \in R^{d_{model} \ \ \times d_k}, \\ W_i^V \in R^{d_{model} \ \ \times d_v}, \\ W^O \in R^{h d_v \ \times d_{model}}\]在本工作中，我们使用h=8的并行attention layers或heads。对于每一者，我们会使用\(d_k = d_v = d_{model}/h = 64\) 。由于每个head的维度缩减，总的计算开销与具有完整维度的single-head attention相似。
3.2.3 在模型中Attention的应用
Transformer以三种不同的方式使用multi-head attention：
- “encoder-decoder attention” layers中：queries来自前一decoder layer，memory keys和values来自encoder的output。这允许在decoder中的每个position会注意(attend)在输入序列中的所有位置。这种方式模仿了在seq2seq模型中典型的encoder-decoder attention机制[31,2,8]。
- encoder中：encoder包含了self-attention layers。在一个self-attention layer中，所有的keys, values和queries来自相同的地方：在encoder中的前一layer的output。在encoder中每个position可以注意（attend）在encoder的前一layer中的所有位置。
- decoder中：相似的，在decoder中self-attention layers允许在decoder中的每一position注意到在decoder中的所有positions，直到包含该position。我们需要阻止在decoder中的左侧信息流，来保留自回归(auto-regressive)属性。我们通过对softmax（它对应到无效连接）的输入的所有值进行掩码（masking out，设置为\(-\infty\)）来实现该scaled dot-product attention内部。见图2.
3.3 Position-wise前馈网络
除了attention sub-layers之外，在我们的encoder和decoder中的每一层，包含了一个FC前馈网络，它可以独自和等同地应用到每个position上。在两者间使用一个ReLU来包含两个线性转换。
\[FFN(x) = max(0, x W_1 + b_1) W_2 + b_2\]…(2)
其中，线性转换在不同的positions上是相同的，在层与层间它们使用不同参数。另一种方式是，使用kernel size为1的两个convolutions。输入和输出的维度是\(d_{model}=512\)，inner-layer具有维度\(d_{ff}=2048\)。
3.4 Embedding和softmax
与其它序列转换模型相似，我们使用学到的embeddings来将input tokens和output tokens转换成\(d_{model}\)维的向量。我们也使用常见的学到的线性转换和softmax函数来将decoder output转换成要预测的下一token的概率。在我们的模型中，我们在两个embedding layers和pre-softmax线性转换间共享相同的权重矩阵，这与[24]相同。在embedding layers中，我们会使用\(\sqrt{d_{model}}\)乘以这些权重。
3.5 Positional Encoding
由于我们的模型不包含循环（recurrence）和卷积（convolution），为了让模型利用序列的顺序，我们必须注入一些关于tokens在序列中的相对或绝对位置的信息。为此，我们在编码器(encoder)和解码器(decoder)栈底部添加“位置编码(positional encoding)”到input embedding中。该positional encodings与input embeddings具有相同的维度\(d_{model}\)，因而两者可以求和。positinal encodings有许多选择，可以采用可学习（learned）或者固定（fixed）。
在本工作中，我们使用不同频率的sin和cosine函数：
\[PE_{(pos, 2i)} = sin(pos / 10000 ^{2i/d_{model}}) \\ PE_{(pos, 2i+1)} = cos(pos / 10000 ^{2i/d_{model}})\]其中：
- pos是position，i是维度
也就是说：positional encoding的每个维度对应于一个正弦曲线（sinusoid）。波长(wavelengths)形成了一个从\(2 \pi\)到\(10000 \cdot 2\pi\)的等比数列（也称几何级数：geometric progression）。我们选择该函数的原因是：假设它允许该模型可以很容易学到通过相对位置来进行关注（attend），因为对于任意固定offset k，\(PE_{pos+k}\)可以被表示成一个关于\(PE_{pos}\)的线性函数。
我们也使用学到的positional embeddings进行实验，发现两者版本几乎生成相同的结果（见表3 第E行）。我们选择正弦曲线版本，是因为它可以允许模型对序列长度长于训练期遇到的长度进行推导。
4.为什么用self-attention
在本节中，我们比较了self-attention layers与recurrent layers、convolutional layers的多个方面（它们常用于将一个变长序列的符号表示\((x_1, \cdots, x_n)\)映射到另一个等长的序列\((z_1, \cdots, z_n)\)上，其中：\(x_i, z_i \in R^d\)），比如：在一个常用的序列转换encoder或decoder中的一个hidden layer。启发我们使用self-attention主要有三方面考虑：
- 1.每一layer的总体计算复杂度
- 2.可以并行计算的计算量，通过所需序列操作(ops)的最小数目进行衡量
- 3.在长范围依赖（long-range dependencies）间的路径长度。学习长范围依赖在许多序列转换任务中是一个关键挑战。影响该能力（学习这样的依赖）一个的关键因素是，forward和backward信号的路径长度必须在网络中可穿越（traverse）。在input和output序列中任意位置组合间的路径越短，学习长范围依赖就越容易[11]。这里，我们也比较了由不同layer types构成的网络上，在任意两个input和output positions间最大路径长度。
表1
如表1所示，一个self-attention layer会使用常数数目的序列执行操作（sequentially executed operations）来连接所有positions；而一个recurrent layer需要O(n)个序列操作（sequential operations）。根据计算复杂度，当序列长度n比representation维度d要小时(通常大多数情况下，使用state-of-art模型的句子表示，比如：word-piece和byte-pair表示)，self-attention layers要比recurrent layers快。为了提升非常长序列任务的计算性能，self-attention可以限制到只考虑在input序列中围绕各自output position为中心的一个size=r的邻居。这可以将最大路径长度增大到\(O(n/r)\)。我们在未来会计划研究该方法。
kernel宽度\(k < n\)的单个convolutional layer，不会连接上input和output positions的所有pairs。在连续kernels的情况下，这样做需要一个\(O(n/k)个\) convolutional layers的stack；在扩大卷积(dilated convoluitons)的情况下需要\(O(log_k(n))\)，这会增加在网络中任意两个positions间的最长路径的长度。卷积层(convolutional layers)通常要比recurrent layers开销更大，会乘以一个因子k。然而，可分离卷积(Separable convolutions)，将复杂度减小到\(O(k \cdot n \cdot d + n \cdot d^2)\)。有了\(k=n\)，然而，一个可分离卷积的复杂度等于一个self-attention layer和一个point-wise前馈layer，在我们的模型中采用该方法。
另一个好处是，self-attention可以生成更多可解释模型。我们从我们的模型中内省(inspect)出attention分布，并在附录部分讨论示例。单独的attention heads不仅可以很明确地学习执行不同的任务，出现在展示行为中的多个（）还可以与句子的形态结构和语义结构相关。
5.训练
5.1 训练数据和Batching
我们在标准的WMT 2014 English-German dataset上进行训练，它包含了将近450w句子对（sentence pairs）。句子使用byte-pair encoding进行编码，它具有一个37000 tokens的共享的source-target词汇表。对于英译法，我们使用更大的WMT 2014-English-French数据集，它包含了36M句子，32000个word-piece词汇表。句子对(sentence pairs)通过近似的序列长度进行打包。每个training batch包含了一个句子对集合，它会近似包含25000个source tokens和25000个target tokens。
5.2 硬件与schedule
在8块nvidia P100 GPUs上进行模型训练。对于我们的base models，它使用paper上描述的超参数，每个training step会花费0.4s。我们会为base models训练10w个steps 或12小时。对于我们的大模型（表3底部描述），step time是1s。大模型会训练30000 steps（3.5天）。
5.3 Optimizer
我们使用Adam optimizer，\(\beta_1=0.9, \beta_2=0.98, \epsilon=10^{-9}\)。我们会根据训练过程调整learning rate，根据以下公式：
\[lrate = d_{model}^{-0.5} \cdot min(step\_num ^{-0.5}, step\_num \cdot warmup\_steps^{-1.5})\]…(3)
这对应于为前warmup_steps阶段线性增加learning rate，然后之后与step_num的平方根成比例减小。我们使用的warmup_steps=4000.
6.结果
6.1 机器翻译
在WMT 2014 English-to-German翻译任务上，big transformer model(见表2: Transformer(big))的效果要比之前最好的模型（包括ensembles）要好2.0 BLEU，达到一个新的state-of-art BLEU分:28.4. 该模型的配置列在了表3的底部。训练会在8张P100 GPUs上训练3.5天。我们的base model胜过之前发布的所有模型和ensembles，训练开销只是其他模型的一小部分。
表2:
在WMT 2014 English-to-French翻译任务上，我们的big model的BLEU得分为41.0, 比之前发布的single models都要好，训练开销只有之前state-of-art model的1/4. 对于English-to-French所训练的Transformer(big)模型，使用dropout rate为：\(P_{drop}=0.1\)，而非0.3。
对于base models，我们使用一个single model，它通过最后的5个checkpoint进行平均获得，每个checkpoint会有10分钟的时间间隔。对于big models，我们则对最后的20个checkpoints进行平均得到。我们使用的beam search的beam size为4, length penalty为 α = 0.6. 这些超参数会在实验之后选择。我们在推断(inference)期间设置最大的output length为: (input length+50)，当可能时会提前终止。
表2归纳了我们的结果，并比较了与其它模型结构间的翻译质量和训练开销。我们估计了用于训练一个模型的浮点操作的数目，乘以训练时间，所使用的GPUs数目，以及每个GPU的持续的(sustained)单精度浮点能力(single-precision floating-point capacity)。
6.2 模型变种
为了评估Transformer中不同组件的重要性，我们以不同的方式区分我们的base model，并在数据集newstest2013上测量了在English-to-German翻译上的效果。我们使用前一节描述的beam serach，但没有进行checkpoint averaging。我们的结果在表3中。
表3
在表3 rows(A)，我们会使用不同的attention heads数目、attention key和value维度，来保持常数级的计算量，如3.2.2节所描述的。而single-head attention是0.9 BLEU，它比最佳setting要差，如果有太多heads质量也会下降。
在表3 rows(B)，我们观察到减小attention key size \(d_k\)会伤害模型质量。这建议我们，决定兼容并不容易，一个dot-product更复杂的兼容函数可能会更有意义。进一步观察（C）和（D），模型越大越好，dropout在避免over-fitting上更有用。在row(E)上，我们使用已经学到的positional embedding[8]来替换了我们的sinusoidal positional encoding，结果与base model几乎相同。
7.结论
Transformer是首个完全基于attention的序列转换模型（sequence transduction model），它使用multi-headed self-attention来替换在encoder-decoder架构中常用的recurrent layers。
对于翻译任务，Transformer训练要比基于recurrent或convolutional layers的结构要快很多。在WMT 2014 English-to-German和WMT 2014 English-to-French翻译任务上，我们达到了一个新的state-of-the-art效果。
我们对attention-based模型的将来很激动，计划应用到其它任务上。我们计划将Transformer扩展到涉及输入输出形态的非文本问题，研究local, restricted attention mechanisms以有效处理大的inputs和outputs（比如：图片、音频、视频）。生成更少序列是另一个研究目标。
代码在：https://github.com/tensorflow/tensor2tensor
参考
starspace介绍
Facebook在2017年提出了《StarSpace: Embed All The Things!》，我们可以看下：
介绍
StarSpace是一种神经嵌入模型（neural embedding model ），可以广泛解决多种问题：
- 文本分类，或者其它标注任务，比如：语义分类
- 实体排序，比如：给定一个query，对web文档进行排序
- 基于CF的推荐，例如：文档、音乐、或视频推荐
- 基于内容的推荐，其中，内容通过离散特征（例如：词）定义
- 图谱嵌入（mebedding graphs），例如，Freebase这样的多关系图谱
- 学习词、句、文档的embeddings
相关工作
隐文本表示（或称为embeddings），是在一个大语料上使用非监督学习得到的关于词、文档的向量表示。相应的方法有：Bengio 2003 embedding, Mikolov word2vec 2013, Bojanowski fastText 2017。
在监督式embeddings领域，方法有：SSI，WSABIE， (Tang, Qin, and Liu 2015), (Zhang and LeCun 2015), (Conneau et al. 2016), TagSpace(Weston, Chopra, and Adams 2014) and fastText(Joulin et al. 2016) 。
在推荐领域，embedding模型很成功，有：SVD (Goldberg et al. 2001)， SVD++ (Koren and Bell 2015)，(Rendle 2010; Lawrence and Urtasun 2009; Shi et al. 2012)。这些方法中的一些方法主要关注于：CF的setup，其中user IDs和movie IDs具有单独的embeddings，比如：在Netflix挑战赛的setup（例如： (Koren and Bell 2015),新的users和items不能天然合并进去）。我们展示了StarSpace是如何天然地迎合该settings和基于content的settings，其中users和items可以被表示成features，具有天然的out-of-sample扩展，而非只是一个固定集合。
在知识图谱中的链接预测上。有s(Bordes et al. 2013) and (GarciaDuran, Bordes, and Usunier 2015)。StarSpace也可以应用于此，匹配TransE方法。
模型
StarSpace模型由学习实体（learning entities）组成，每个通过一个离散特征（bag-of-features）的集合描述。一个像（文档、句子）这样的实体可以通过bag-of-words或n-grams进行描述，一个像user这样的实体可以通过bag-of-documents、movies、items的方式进行描述。重要的是，StarSpace模型可以自由比较不同类型的实体（entities）。例如，一个用户实体可以与一个item实体、或者一个文档实体(推荐)、一个文带标签实体的文档实体等进行比较。这可以通过学习来完成，并将它们嵌入到相同的空间中，这样的比较才有意义————通过根据各自的metric进行最优化。
字典D，特征为F，那么有一个D X F的矩阵，其中\(F_i\)表示第i维特征（行），它有d维的embedding，我们可以使用\(\sum_{i \in a} F_i\)来嵌入一个实体a。
这就是说，像其它embedding模型，我们的模型通过为在该集合（称为字典，它包含了像words这样的特征）中的每个离散特征分配一个d维向量。实体由特征组成（比如：文档），被表示成一个bag-of-features，它们的embeddings可以隐式被学到。注意，一个实体可以由像单个特征（唯一）组成，比如：单个词(word)、名字(name)、user ID、Item ID。
为了训练我们的模型，我们必须学到比较实体。特别的，我们希望最小化以下的loss function：
\[\sum_{(a,b)\inE^+, b^- \in E^-} L^{batch} (sim(a,b), sim(a,b_1^-), ..., sim(a,b_k^-))\]注意：
- 正实体对 positive entity pairs (a,b)的生成器来自于集合\(E^+\)。这是任务非独立的，将会在下面描述。
- 负实体\(b_i^-\)的生成器来自于集合\(E^-\)。我们使用一个k-negative sampling策略（Mikolov 2013）来为每个batch update选择k个这样的负样本对。我们会从在该实体集内随机选择，它们可能出现在相似函数的第二个参数上（例如：对于文本标注任务, a是文档，b是标签，因此我们可以从labels集合上抽样\(b^-\)）。k的因素分析将在第4部分讨论。
- 相似函数\(sim(\cdot, \cdot)\)。在我们的txxik，我们的实现有：cosine相似度和内积，可以通过一个参数进行选定。总之，对于较少数目的label features（比如：分类），它们的工作机制很像；对于更大数目（比如：句子或文档相似度）时，cosine更好。
- loss function为 \(L_{batch}\)，它比较了positive pair (a,b)，negative pairs(a, b_i^-)，其中i=1,…, k. 我们也实现了两个概率：margin ranking loss（例如：\(max(0, \mu-sim(a,b))\)，其中\(\mu\)是margin参数），negative loss loss of softmax。所有的实验都使用前者，因为表现更好。
我们使用SGD进行最优化，例如，每个SGD step是从在outer sum中\(E^+\)上的一个抽样，在多CPU上使用Adagrad，hogwild。我们也应用一个max norm的embeddings来将学到的向量限制在球半径为r的空间\(R^d\)上。
在测试时，可以使用学到的函数\(sim(\cdot,\cdot)\)来测量实体间的相似度。例如，对于分类，在测试时为给定输入a预测一个label，使用\(max_{\hat{b}} sim(a,\hat{b})\)来表示可能的label\(\hat{b}\)。或者，对于ranking，通过similarity对实体进行排序。另外，embedding向量可以直接被下游任务使用，例如：word embbeding models。然而，如果\(sim(\cdot,\cdot)\)直接满足你的应用需要，我们推荐使用StarSpace，它很擅长这一块。
接着，我们会描述该模型如何被应用到其它任务上：每个case会描述\(E^+\)和\(E^-\)是如何生成的。
\(Multiclass分类（例如：文本分类）\)：positive pair generator直接来自于一个标注数据训练集，(a,b) pairs，其中，a是文档（bags-of-words），b是labels（单个features）。负实体(\(b^-\))从可能的labels集合中被抽样。
\(Multilabel Classification\): 在该case中，每个文档a可以具有多个正标签，其中之一在每个SGD step中从b中抽样，来实现multilabel分类。
\(基于CF的推荐\)：训练数据包含了：一个用户集合，其中每个用户通过bag-of-items进行描述（字典里的唯一特征）。positive pair生成器会选择一个user，选择a作为该user ID的唯一单个特征，以及单个item b。负实体\(b^-\)从该可能的items中进行抽样。
基于CF的推荐，使用out-of-sample用户扩展：经典CF的一个问题是，不能泛化到新用户上，每个user ID可以学到一个独立的mebedding。与之前方法使用相同的训练数据，可以使用StarSpace学到一个新模型。该方法中，positive pair genterator会选择一个user，选择a作为除它之外的所有item，b作为left out item。也就是说，该模型会学到估计：如果一个用户喜欢一个item，可以将该用户建模成，。
基于内容的推荐：该任务包含了一个用户集合，其中，每个用户通过一个bag-of-items进行描述，其中每个item通过一个bag-of-features（来自字典）进行描述。例如，对于文档推荐，每个用户通过bag-of-documents进行描述，其中，每个文档通过bag-of-words进行描述。现在，a可以被选成除它外的所有items，b表示left out item。该系统可以扩展到新items和新users上，只要两都被特征化。
多关系知识图谱(例如：逻接预测)：给定一个graph三元组(h,r,t)，包含了一个head conecpt：h，一个relation：r，一个tail concept t，例如：(Beyonce,´born-in, Houston），一个可以从该graph中学习embeddings。对h, r, t的实例可以被定义成字典里中唯一features。我们可以随机均匀选择：
- (i) a由bag-of-features：h和r 组成，其中b只包含t；
- (ii) a由h组成，b包含了r和t.
负实体\(b^-\)从可能的concepts中抽样得到。学到的embeddings可以通过学到的sim(a,b)被用于回答link prediction问题，比如：(Beyonce, born-in, ?) ´ or (?, born-in, Houston).
信息检索IR（例如：文档搜索）和文档嵌入：给定监督式训练数据，包含了（搜索关键词，相关文档）pairs，可以直接训练一个信息检索模型：a包含了搜索关键词，b是一个相关文档，\(b^-\)是另一个不相关的文档。如果只提供了非监督式训练数据，它包含了未标注文档的集合，从文档中选择a的一个方法是，作为随机关键词，b作为保留词。注意，两种方法可以隐式地学习文档嵌入，可以被用于该目的。
学习word embedding：我们可以使用StarSpace来学习非监督式word embeddings，它使用训练raw text组成的数据。我们会选择a作为一个窗口的词（例如：4个words，两边各两个），b作为中间词。
学习sentence embeddings：当你可以直接学习句子的embeddings，使用上述方法来学习word embeddings、并使用它们来嵌入看起来不是最优的。给定一个未标注文档的训练集，它们由句子组成，我们选择a和b作为来自相同文档的一个句子对(pair of sentences)；\(b^-\)是来自其它文档的句子。直觉上，句子间的语义相似度在同一个文档内共享（如果文档很长的话，也可以只选择在特定距离内的句子）。再者，embeddings将会自动为关于句子长度的words sets进行最优化，因此，训练时间会与测试时间相匹配，而使用短窗口进行训练来使用word embeddings进行特殊学习——window-based embbedings可以变差，当一个句子中的words总和变得更大时。
多任务学习：任何这些任务可以组合，如果它们共享在基础字典F中的一些特征时可以同时训练。例如，可以使用非监督式word/sentence embedding，并结合监督式分类，来给出半监督式学习。
实验
略。