LambdaMART-郑扬锋

毕业设计

---

论文地址：
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/MSR-TR-2010-82.pdf

---

1. 关于$\lambda_i$

在2.1节 Factoring RankNet: Speeding Up Ranknet Training中，作者把下面式子：

$$\sum_{\{i,j\}\in I}(\lambda_{ij}\frac{\partial s_i}{\partial w_k}-\lambda_{ij}\frac{\partial s_j}{\partial w_k})$$

整理成：

$$\sum_i\lambda_i\frac{\partial s_i}{\partial w_k}$$

其中

$$\lambda_i=\sum_{j:\{i,j\}\in I}\lambda_{ij}-\sum_{j:\{j,i\}\in I}\lambda_{ij}$$

这里$\{i,j\}$是url $U_i,U_j$组成的对。根据原文

it is convenient to adopt the convention that $I$ contains pairs of indices $\{i,j\}$ for which $U_i\triangleright U_j$, so that $S_{ij}$ = 1

即$U_i$的相关性强于$U_j$，而对$\{j,i\}$不计入求和里。

现在假设一个查询里有三条url，$U_1,U_2,U_3$，且$U_1\triangleright U_2\triangleright U_3$，那么：

$$\sum_{\{i,j\}\in I}(\lambda_{ij}\frac{\partial s_i}{\partial w_k}-\lambda_{ij}\frac{\partial s_j}{\partial w_k})\\ =\lambda_{12}\frac{\partial s_1}{\partial w_k}-\lambda_{12}\frac{\partial s_2}{\partial w_k}+\lambda_{13}\frac{\partial s_1}{\partial w_k}-\lambda_{13}\frac{\partial s_3}{\partial w_k}+\lambda_{23}\frac{\partial s_2}{\partial w_k}-\lambda_{23}\frac{\partial s_3}{\partial w_k}$$

并没有$\sum_{j:\{j,i\}\in I}\lambda_{ij}$项出现（这个求和里的项$\lambda_{ij}$有这样的特征：$U_j\triangleright U_i$）
反而，我觉得应该是：

$$\lambda_i=\sum_{j:\{i,j\}\in I}\lambda_{ij}-\sum_{j:\{j,i\}\in I}\lambda_{ji}$$
这样定义$\lambda_i$，才能在我举的例子中正确的化简：
$$\lambda_1\frac{\partial s_1}{\partial w_k}=\lambda_{12}\frac{\partial s_1}{\partial w_k}+\lambda_{13}\frac{\partial s_1}{\partial w_k}\\ \lambda_2\frac{\partial s_2}{\partial w_k}=\lambda_{23}\frac{\partial s_2}{\partial w_k}-\lambda_{12}\frac{\partial s_2}{\partial w_k}\\ \lambda_3\frac{\partial s_3}{\partial w_k}=-\lambda_{13}\frac{\partial s_3}{\partial w_k}-\lambda_{23}\frac{\partial s_3}{\partial w_k}$$

所以，我觉得论文里的$\lambda_i$是不正确的。

---

2. MART叶子节点的值

在第6节 MART for Two Class Classification 中，作者简单讲了一下MART的原理。在求叶子节点值时

$$\gamma_{jm}=\arg\min_{\gamma}\sum_{x_i\in R_{jm}}g(\gamma)$$
（其中$R_{jm}$是叶子节点region，$g$是损失函数）
使用了牛顿迭代法求局部极值。
$$\gamma_{n+1}=\gamma_n-\frac{g'}{g''}$$
这应该是个逐步迭代逼近极小值的过程。但是作者直接用
$$\gamma_{jm}=-\frac{g'}{g''}$$
作为了叶子节点值，也就是说迭代就进行了一步。虽然这个值可用，但肯定不够好。这样也可以吗？

---

3. LambdaMART的算法

下面是LambdaMART算法伪代码：

这里的子学习器（回归树）学习对象是梯度$\lambda_i$，这个$\lambda_i$根据前面的步骤，是同一个查询中不同对的组合计算偏导得出的，它跟本查询中第i个url是密切相关的。
但是原文里说

In LambdaMART, each tree models the λi for the entire dataset (not just for a single query).

这是怎么做到的？一个文档的梯度在不同查询中方向、强度可能都会不一样，为什么能综合多个查询来算$\lambda_i$？从下面给出的式子看，$\lambda_i$的求法和之前单个查询的求法也没什么区别？