特征交叉与 GBDT+LR

1. 为什么要构造组合特征？

假设要预测用户是否点击影视广告，输入包含语言和类型两个类别特征。语言分为中文、英文，类型分为电影、电视剧。以下四条记录用于说明它们的关系：

语言	类型	是否点击
中文	电影	0
英文	电影	1
中文	电视剧	1
英文	电视剧	0

观察数据：对于电影，英文更容易被点击；对于电视剧，中文更容易被点击。语言的作用取决于影视作品的类型。 在统计学中，这种关系称为交互作用（Interaction Effect）。

1.1 普通逻辑回归的限制

令 x₁=1 表示中文、x₁=0 表示英文；令 x₂=1 表示电视剧、x₂=0 表示电影。普通逻辑回归为：

$$\hat p=\sigma(z),\qquad z=b+w_1x_1+w_2x_2,\qquad \sigma(z)=\frac{1}{1+e^{-z}}$$

采用 0.5 作为分类阈值，相当于 z>0 时预测点击。为了正确分类四条样本，需要同时满足：

$$\begin{aligned} b&>0 &&(\text{英文电影})\\ b+w_1&<0 &&(\text{中文电影})\\ b+w_2&<0 &&(\text{英文电视剧})\\ b+w_1+w_2&>0 &&(\text{中文电视剧}) \end{aligned}$$

但中间两个条件意味着 w₁<−b 和 w₂<−b，因此 b+w₁+w₂<−b<0，与最后一个条件矛盾。

困难在于：普通线性模型把语言和类型的作用相加，每个特征的作用由固定权重决定，无法表达这种随另一个特征而变化的关系。

1.2 把两个类别组合成一个新特征

为四种组合分别设置一个指示特征。某个样本满足对应条件时取 1，其余位置取 0：

组合	中文电影	英文电影	中文电视剧	英文电视剧
中文电影	1	0	0	0
英文电影	0	1	0	0
中文电视剧	0	0	1	0
英文电视剧	0	0	0	1

用 c₁、c₂、c₃、c₄ 表示这四个位置，新模型为：

$$\hat p=\sigma(b+\beta_1c_1+\beta_2c_2+\beta_3c_3+\beta_4c_4)$$

每种组合有独立权重。例如取 b=0，四个权重依次为 −2、2、2、−2，就能把四条记录全部正确分类。

组合特征让模型学到单个特征无法独立表达的关系。 对数值特征，常用乘积表达二阶交互；对类别特征，常用组合类别的独热编码表达交互。

2. 组合特征的参数数量

上面的两个字段各有 2 种取值，一共只有 2×2=4 种组合。推荐系统中的用户 ID 与物品 ID 往往有大量不同取值。

假设有 m 个用户和 n 个物品，为每一种用户—物品组合单独学习权重，则需要：

$$N_{\mathrm{direct}}=m\times n$$

如果有 100 万用户、10 万物品，就需要 1,000 亿个组合权重。此外，大量用户和物品在训练数据中没有直接交互记录，单独学习每个组合的权重也很困难。

2.1 用低维向量表示交互权重

让每个用户拥有一个 k 维向量 pᵤ，每个物品拥有一个 k 维向量 qᵢ，利用内积近似表示交互权重：

$$w_{ui}\approx\mathbf p_u^\top\mathbf q_i =\sum_{f=1}^{k}p_{uf}q_{if}$$

这样需要学习的参数数量为：

$$N_{\mathrm{factorized}}=mk+nk=k(m+n)$$

假设 k=32，则参数从 1,000 亿降为 3,520 万。不同组合还能够共享同一个用户向量或物品向量，并利用其他交互记录学习共同规律。

2.2 为什么这就是矩阵分解？

将全部交互权重组成矩阵 W，把用户向量排成矩阵 P，把物品向量排成矩阵 Q：

$$\underbrace{W}_{m\times n}\approx \underbrace{P}_{m\times k} \underbrace{Q^\top}_{k\times n}$$

这一方法利用低秩结构表示较大的参数矩阵，其秩不超过 k。k 越小，所需参数越少，模型能够表示的交互关系也会受到更多限制。

交互演示：参数数量、矩阵结构与向量内积

单独打开选择不同用户和物品，观察二维向量内积、Sigmoid 转换和参数量变化。

这种低维表示是矩阵分解的核心思想，也有助于理解推荐系统中的 Embedding（嵌入向量）和因子分解机（Factorization Machine，FM）。

3. 用决策树选择组合条件

如果输入包含年龄、性别、用户类型和物品类型，候选组合就会迅速增加。可以利用决策树寻找有预测价值的组合：让模型根据训练数据选择判断条件，将根节点到叶节点的路径表示为一组特征条件。

例如，一棵树先判断年龄是否不超过 35 岁，然后判断性别是否为女。相应路径表示：

$$\phi_1(x)=I(\text{年龄}\le35\ \land\ \text{性别=女})$$

这里 I 表示指示函数：满足条件为 1，否则为 0。

3.1 从判断条件生成组合特征

考虑以下四条组合规则：

1. φ₁：年龄 ≤ 35，且性别为女。
2. φ₂：年龄 ≤ 35，且物品类型为护肤。
3. φ₃：用户类型为付费，且物品类型为食品。
4. φ₄：用户类型为付费，且年龄 ≤ 40。

对样本（28 岁、女、免费、护肤），前两个条件成立，于是：

$$\phi(x^{(1)})=(1,1,0,0)$$

对样本（36 岁、男、付费、食品），后两个条件成立：

$$\phi(x^{(2)})=(0,0,1,1)$$

这些新的 0/1 特征就可以输入逻辑回归：

$$\hat p=\sigma\left(b+\sum_{j=1}^{4}\beta_j\phi_j(x)\right)$$

同一条样本在一棵普通决策树中，只会到达一个叶节点。 上述两条样本分别满足两条规则，因此这里的四条规则可以理解为汇总得到的组合条件。在多棵树生成的特征中，样本可以分别命中不同树的叶节点。

交互演示：改变输入，查看组合特征

单独打开改变年龄、性别、用户类型和物品类型，实时计算四维组合特征，并查看决策树与 GBDT+LR 的流程。

4. GBDT 如何帮助寻找组合特征？

梯度提升决策树（Gradient Boosting Decision Tree，GBDT）可以用于寻找有用的组合。每棵树通过连续的条件判断形成叶节点路径；GBDT 连续训练多棵树，使后面的树进一步改善已有模型的预测。

平方误差损失下，可以把这个过程理解为拟合前一轮的残差；在一般损失函数下，GBDT 通常使用损失函数的负梯度。

4.1 从叶节点生成 LR 的输入

GBDT+LR 使用以下步骤生成特征并预测：

1. 使用训练数据训练 GBDT。
2. 对每条样本，记录它在每棵树中到达的叶节点。
3. 将每棵树的叶节点位置进行独热编码。
4. 连接所有树的编码，输入逻辑回归（Logistic Regression，LR），预测点击概率。

假设有三棵树，分别包含 3、2、3 个叶节点。某条样本依次到达第 2、1、3 个叶节点，对应编码：

$$(0,1,0)\ \Vert\ (1,0)\ \Vert\ (0,0,1)$$

将它们连接后，得到一个 8 维向量：

$$x_{\mathrm{new}}=(0,1,0,1,0,0,0,1)$$

每棵树恰好激活一个叶节点，因此这个向量有三个位置取 1。每个被激活的叶节点，都代表样本满足对应路径上的一组条件。LR 可以学习这些条件与点击结果之间的联系。

GBDT 还可以根据数据自动选择年龄等数值特征的分裂阈值。实际训练时，需要通过树深度、叶节点数量、学习率和验证集来控制模型复杂度。

5. 与推荐系统模型的联系

低维向量内积可以进一步推广到因子分解机（FM）。FM 为每个输入特征学习一个向量，并用向量内积表示二阶交互权重：

$$\hat y=\sigma\left( w_0+\sum_{i=1}^{d}w_ix_i+ \sum_{i=1}^{d}\sum_{j=i+1}^{d} \langle\mathbf v_i,\mathbf v_j\rangle x_ix_j \right)$$

其中第一项是常数，第二项表达每个特征自身的作用，第三项表达两两特征的交互。DeepFM 等模型还利用神经网络学习更复杂的交互关系。

决策树路径编码也是理解 GBDT+LR 的直接起点。这两种方法还可以结合：向量内积表达用户—物品关系，树生成的规则补充年龄、用户类型与物品类型之间的条件组合。

方法	要解决的问题	核心方法
低维向量表示	组合太多，参数数量过大	低维向量、内积、矩阵分解
决策树生成组合条件	候选组合太多，如何找到有用条件	决策树路径、GBDT、叶节点编码