Question

1. LR 模型只考虑特征之间的线性关系，而POLY2 模型考虑了特征之间的非线性关系。

   • 捕获非线性特征的一个常用方法是采用核技巧，如高斯核RBF，将原始特征映射到一个更高维空间。在这个高维空间模型是线性可分的，即：只需要考虑新特征之间的线性关系。

     但是核技巧存在计算量大、内存需求大的问题。

   • 论文 《Training and Testing Low-degree Polynomial Data Mappings via Linear SVM》 提出多项式映射 polynomially mapping 数据的方式来提供非线性特征，在达到接近核技巧效果的情况下大幅度降低内存和计算量。

2. 设低维样本空间为 $ n $ 维度，低维样本 $ \mathbf{\vec x} = [x_1,\cdots,x_n]^T $ 。

   多项式核定义为： $ K(\mathbf{\vec x}_i,\mathbf{\vec x}_j) = (\gamma \mathbf{\vec x}_i\cdot \mathbf{\vec x}_j +r)^d $ 。其中 $ \gamma,r $ 为超参数， $ d $ 为多项式的度degree 。

   根据定义，多项式核等于样本在高维空间向量的内积：

   $ K(\mathbf{\vec x}_i,\mathbf{\vec x}_j) = \phi(\mathbf{\vec x}_i) \cdot \phi(\mathbf{\vec x}_j) $

   其中 $ \phi $ 是映射函数。

   当 $ d=2 $ 时，有：

   $ \phi(\mathbf{\vec x}) = [1,\sqrt{2\gamma}x_1,\cdots,\sqrt{2\gamma}x_n,\gamma x_1^2,\cdots,\gamma x_n^2,\sqrt2 \gamma x_1x_2,\cdots,\sqrt 2 \gamma x_{n-1}x_n ]^T $

   使用 $ \sqrt 2 $ 是为了 $ \phi(\mathbf{\vec x}_i) \cdot \phi(\mathbf{\vec x}_j) $ 的表达更简洁。

3. 如果不用核技巧，仅仅考虑使用一个多项式进行特征映射，则我们得到：

   $ \phi(\mathbf{\vec x}) = [1,x_1,\cdots,x_n,x_1^2,\cdots,x_n^2,x_1x_2,\cdots,x_{n-1}x_n]^T $

   结合LR 模型，则得到 POLY2 模型：

   $ z(\mathbf{\vec x}) = w_0 + \sum_{i=1}^nw_i\times x_i + \sum_{i=1}^n\sum_{j=i}^n w_{i,j}\times x_i\times x_j\\ y(\mathbf{\vec x}) = \frac{1}{1+\exp(-z(\mathbf{\vec x}))} $

   新增的组合特征一共有 $ \frac{n\times (n-1)}{2} $ 个。

4. POLY2 模型的优缺点：

   • 优点：除了线性特征之外，还能够通过特征组合自动捕获二阶特征交叉产生的非线性特征。

   • 缺点：

     • 参数太多导致计算量和内存需求发生爆炸性增长。

       如计算广告场景中，原始样本特征可能达到上万甚至百万级别，则特征的交叉组合达到上亿甚至上万亿。

     • 数据稀疏导致二次项参数训练困难，非常容易过拟合。

       参数 $ w_{i,j} $ 的训练需要大量的 $ x_i,x_j $ 都非零的样本。而大多数应用场景下，原始特征本来就稀疏（非零的样本数很少），特征交叉之后更为稀疏（非零的样本数更少）。这使得训练 $ w_{i,j} $ 的样本明显不足，很容易发生过拟合。