# pGMM Kernel Regression and Comparisons with Boosted Trees

Ping Li and Weijie Zhao

Cognitive Computing Lab
Baidu Research
10900 NE 8th St. Bellevue, WA 98004, USA

{pingli98<EMAIL_ADDRESS>
(June 2022)

###### Abstract

In this work, we demonstrate the advantage of the pGMM (“powered generalized
min-max”) kernel in the context of (ridge) regression. In recent prior
studies, the pGMM kernel has been extensively evaluated for classification
tasks (Li, 2017b, 2018; Li and Zhao, 2022b), for logistic regression, support
vector machines, as well as deep neural networks. In this paper, we provide an
experimental study on ridge regression, to compare the pGMM kernel regression
with the ordinary ridge linear regression as well as the RBF kernel ridge
regression. Perhaps surprisingly, even without a tuning parameter (i.e., $p=1$
for the power parameter of the pGMM kernel), the pGMM kernel already performs
well. Furthermore, by tuning the parameter $p$, this (deceptively simple) pGMM
kernel even performs quite comparably to boosted trees.

Boosting and boosted trees are very popular in machine learning practice. For
regression tasks, typically, practitioners use $L_{2}$ boost, i.e., for
minimizing the $L_{2}$ loss. Sometimes for the purpose of robustness, the
$L_{1}$ boost might be a choice. In this study, we implement $L_{p}$ boost for
$p\geq 1$ and include it in the package of “Fast ABC-Boost” (Li, 2009, 2010;
Li and Zhao, 2022a). Perhaps also surprisingly, the best performance (in terms
of $L_{2}$ regression loss) is often attained at $p>2$, in some cases at $p\gg
2$. This phenomenon has already been demonstrated by Li et al. (2010) in the
context of k-nearest neighbor classification using $L_{p}$ distances. In
summary, the implementation of $L_{p}$ boost provides practitioners the
additional flexibility of tuning boosting algorithms for potentially achieving
better accuracy in regression applications.

##  1 Introduction

Kernels, which can be either linear or nonlinear, are classical tools in
machine learning (Vapnik, 1999; Schölkopf and Smola, 2002; Bishop and
Nasrabadi, 2006; Hastie et al., 2009). In general, machine learning
researchers and practitioners are often familiar with the Gaussian (a.k.a.
RBF, radial basis function) kernels, the polynomial kernels, etc. In this
paper, we introduce the “pGMM” ($p$-powered generalized min-max) kernel for
regression tasks.

The idea of the pGMM kernel has been developed in a series of works over the
recent years by Li (2017b, 2018); Li and Zhao (2022b). To explain the pGMM
kernel, we would need to first introduce the GMM (“generalized min-max”)
kernel (Li, 2017a; Li and Zhang, 2017). The original “min-max” similarity
(kernel) was defined on non-negative data (Kleinberg and Tardos, 1999;
Charikar, 2002; Manasse et al., 2010; Ioffe, 2010). Thus, in order to define
the GMM kernel for general data types, the first step is to apply a
transformation on the original data to remove negative entries via a simple
dimensionality expansion.

Specifically, consider the original data vector $u_{i}$, $i=1$ to $d$. The
following transformation, depending on whether an entry $u_{i}$ is positive or
negative,

$\displaystyle\left\\{\begin{array}[]{cc}\tilde{u}_{2i-1}=u_{i},\hskip
7.22743pt\tilde{u}_{2i}=0&\text{if }\ u_{i}>0\\\ \tilde{u}_{2i-1}=0,\hskip
7.22743pt\tilde{u}_{2i}=-u_{i}&\text{if }\ u_{i}\leq 0\end{array}\right.$ (3)

converts general data types to non-negative data. Take a concrete example
here. When $d=3$ and $u=[-3\ \ 17\ \ -0.8]$, the transformed data vector
becomes $\tilde{u}=[0\ \ 3\ \ 17\ \ 0\ \ 0\ \ 0.8]$. The GMM kernel is then
defined as the following form:

$\displaystyle{\text{GMM}}(u,v)=\frac{\sum_{i=1}^{2d}\min\\{\tilde{u}_{i},\tilde{v}_{i}\\}}{\sum_{i=1}^{2d}\max\\{\tilde{u}_{i},\tilde{v}_{i}\\}}.$
(4)

Note that, unlike the popular Gaussian (RBF) kernel, the GMM kernel (4) has no
tuning parameter. To introduce tuning parameters, the following pGMM kernel is
one (deceptively) simple strategy:

$\displaystyle{\text{pGMM}}(u,v;p)=\frac{\sum_{i=1}^{2d}\left(\min\\{\tilde{u}_{i},\tilde{v}_{i}\\}\right)^{p}}{\sum_{i=1}^{2d}\left(\max\\{\tilde{u}_{i},\tilde{v}_{i}\\}\right)^{p}},$
(5)

where $p\in\mathbb{R}$ is a tuning parameter. Readers have probably realized
that this operation is mathematically equivalent to applying a $p$-power
transformation on the data before computing the GMM kernel. However, directly
applying power transformations on the original data is typically not a good
idea due to numerical issues. As demonstrated in Li (2017b, 2018); Li and Zhao
(2022b), the pGMM kernel can be conveniently “hashed” using for example
consistent weighted sampling (CWS) (Manasse et al., 2010; Ioffe, 2010) or
extremal process (Li et al., 2021). Those hashing methods provide a
numerically stable framework for applying the power transformation.

As one can see, this pGMM kernel (and the related hashing algorithms) are
constructed from the original data without knowing the subsequent tasks, which
can be clustering, regression, or classification. As demonstrated in the
previous papers or unpublished technical reports (Li, 2017b, 2018; Li and
Zhao, 2022b), the pGMM kernel (with merely one tuning parameter) performs
surprisingly well in many classification tasks. It is expected that pGMM
kernel should also work well for other tasks such as regression. Nevertheless,
readers might be still interested in seeing those experiments. This motivates
us to report the regression experiments using pGMM kernels.

Summary of contributions. In this paper, we collect a set of regression
datasets to compare pGMM kernel (ridge) regression with linear (ridge)
regression and RBF kernel regression. Since the authors have been working on
boosting and trees (Li, 2009, 2010; Li and Zhao, 2022a), we also provide the
$L_{p}$ regression results on those datasets using boosted trees. The
experimental results confirm the following:

  * •

The pGMM kernel performs (perhaps surprisingly) well on regression tasks.

  * •

Boosted trees typically outperform the pGMM kernel, but usually not by too
much.

  * •

$L_{p}$ boost with $p>2$ in many cases outperforms the standard $L_{2}$ (or
$L_{1}$) boost.

##  2 pGMM Kernel Ridge Regression

Consider a training dataset: $X\in\mathbb{R}^{n\times d}$ and
$Y\in\mathbb{R}^{n}$, where $n$ is the number of training examples and $d$ is
the number of dimensions. Given a testing set $X_{t}$, the classical ridge
linear regression (LR) outputs the prediction $\hat{Y}_{t}$ as

$\displaystyle\hat{Y}_{t}=X_{t}\left(X^{T}X+\lambda I_{d}\right)^{-1}X^{T}Y,$
(6)

where $I_{d}$ is the identity matrix of size $d\times d$ and $\lambda\geq 0$
is the regularization coefficient.

To help readers understand (pGMM) kernel regression, we make use of the
following standard linear algebra trick (i.e., the “push-through identity”):

$\displaystyle\left(X^{T}X+\lambda
I_{d}\right)^{-1}X^{T}=X^{T}\left(XX^{T}+\lambda I_{n}\right)^{-1}$ (7)

to re-write ridge regression into a mathematically equivalent form:

$\displaystyle\hat{Y}_{t}=X_{t}X^{T}\left(XX^{T}+\lambda I_{n}\right)^{-1}Y,$
(8)

or in a “kernel” form:

$\displaystyle\hat{Y}_{t}=K_{t}\left(K+\lambda I_{n}\right)^{-1}Y,\hskip
14.45377ptK_{t}=X_{t}X^{T},\hskip 14.45377ptK=XX^{T}$ (9)

The kernels $K=XX^{T}$ and $K_{t}=X_{t}X^{T}$ are simple linear kernels. One
can of course also use nonlinear kernels, for example, the well-known Gaussian
kernel or polynomial kernel. In this paper, we focus on the pGMM kernel

$\displaystyle
K(u,v;p)={\text{pGMM}}(u,v;p)=\frac{\sum_{i=1}^{2d}\left(\min\\{\tilde{u}_{i},\tilde{v}_{i}\\}\right)^{p}}{\sum_{i=1}^{2d}\left(\max\\{\tilde{u}_{i},\tilde{v}_{i}\\}\right)^{p}}.$
(10)

where $u$ and $v$ are two data vectors in the training set $X$ or testing set
$X_{t}$.

Thus, in a most naive format, conducting kernel (ridge) regression can be
extremely simple if the dataset size is small, e.g., with fewer than $30,000$
training examples, so that we can store the kernel matrix. This is of course
not realistic (and not necessary) for larger datasets. The prior studies (Li,
2017b, a; Li and Zhang, 2017; Li, 2018; Li et al., 2021; Li and Zhao, 2022b)
have already provided very extensive experiments to demonstrate how to
effectively linearize the min-max kernel and variants via hashing, for
classification tasks. In this paper, for the sake of easy reproducibility, we
just provide experiments directly using kernels, on relatively small datasets.

Table 1: Datasets for testing regression algorithms. We report the best test mean square error (MSE) for each method, over the range of regularization coefficients and parameters. dataset | # train | # test | dim | LR | RBF | GMM | pGMM |  $L_{2}$-Boost
---|---|---|---|---|---|---|---|---
ENBcool | 384 | 384 | 8 | 10.24 | 3.20 | 1.70 | 1.28 | 1.21
ENBheat | 384 | 384 | 8 | 9.00 | 0.495 | 0.191 | 0.188 | 0.186
Airfoil | 752 | 751 | 5 | 24.26 | 8.35 | 7.50 | 3.56 | 3.09
CPUsmall | 4096 | 4096 | 12 | 102.12 | 9.05 | 7.22 | 7.05 | 6.89
CPU | 4096 | 4096 | 21 | 98.35 | 6.42 | 5.17 | 5.03 | 4.69
WECPerth | 5000 | 5000 | 32 | $1.1\times 10^{9}$ | $2.3\times 10^{8}$ | $2.4\times 10^{8}$ | $2.3\times 10^{8}$ | $2.5\times 10^{8}$
Cadata | 10320 | 10320 | 8 | $4.8\times 10^{9}$ | $3.8\times 10^{9}$ | $2.4\times 10^{9}$ | $2.4\times 10^{9}$ | $2.1\times 10^{9}$
House16H | 11392 | 11392 | 16 | $2.1\times 10^{9}$ | $1.3\times 10^{9}$ | $1.2\times 10^{9}$ | $1.1\times 10^{9}$ | $1.0\times 10^{9}$
House16L | 11392 | 11392 | 16 | $1.9\times 10^{9}$ | $1.1\times 10^{9}$ | $9.9\times 10^{8}$ | $9.4\times 10^{8}$ | $8.6\times 10^{8}$
CASP | 22865 | 22865 | 9 | 26.63 | 23.94 | 15.30 | 15.29 | 13.51
Splice | 1000 | 2175 | 60 | 0.1205 | 0.0967 | 0.0589 | 0.0589 | 0.0352
Mnoise1 | 2519 | 454 | 784 | 0.0484 | 0.0344 | 0.0311 | 0.0169 | 0.0145
Mnoise6 | 2519 | 454 | 784 | 0.0215 | 0.0165 | 0.0195 | 0.0129 | 0.0131
Mimage | 2538 | 10524 | 784 | 0.0540 | 0.0323 | 0.0263 | 0.0125 | 0.0149

Next, we move directly to experiments. In Table 1, we collect 14 datasets for
regression from public sources, and report the test mean square errors (MSEs)
for ordinary ridge linear regression (LR), RBF kernel regression, GMM kernel
regression, pGMM kernel regression, and $L_{2}$ boost. Most of the datasets
are from the UCI repository. The “CPU” and “CPUsmall” datasets are available
at http://www.cs.toronto.edu/~delve/data/datasets.html . In Table 1, the last
three datasets (“Mnoise1”, “Mnoise6”, and “Mimage”) were created by Larochelle
et al. (2007) for testing deep learning algorithms by modifying the original
MNIST (hand-written digits) dataset. Here, we only use the samples
corresponding to digit “0” and digit “1”. Note that those three datasets as
well as the “Splice” dataset are originally for classification tasks. We
simply treat them as regression data for regressing on the {0,1} label values.
In addition, we preprocess all datasets in the same fashion, by linearly
scaling each feature to [0, 1]. Some kind of data preprocessing such as
scaling is typically needed for kernel (similarity) based methods. Note that
tree methods are invariant to monotonic scaling of each feature.

For “LR” (ordinary ridge linear regression), we report the best test (i.e.,
lowest) MSE over a wide range of the regularization coefficients $\lambda$.
The left column of Figure 1 plots, for selected datasets, the MSEs with
respect to $\lambda$. For “RBF” (Gaussian kernel ridge regression), we report
the best test MSEs over a wide range of regularization coefficients and the
RBF kernel parameters. As expected, the RBF kernel regression achieves
substantially lower MSEs than LR. Note that (only) for LR we added the
“intercept” (i.e., an additional “1” in the data vector) which slightly
improves LR.

Unlike the RBF kernel, the GMM kernel has no tuning parameter (i.e., the
parameter $p=1$). Perhaps surprisingly, as reflected in Table 1, this tuning-
free GMM kernel outperforms the best-tuned RBF kernel in most datasets, in
some datasets quite substantially so. By adding a tuning parameter $p$, the
pGMM kernel further improves the performance for essentially all datasets. The
right column of Figure 1 provides more details by plotting the MSEs of the
pGMM kernel, for a wide range of regularization coefficients and selected $p$
values, for selected datasets.

Figure 1: Test MSEs for selected datasets with respect to the ridge regression
regularization $\lambda$, for ordinary ridge linear regression (LR, left
panels) and pGMM kernel regression (right panels).

Finally, the last column of Table 1 reports the test MSEs of $L_{2}$ boost,
which is implemented using the same codebase of “Fast ABC-Boost” (Li and Zhao,
2022a, c). Interestingly, we can see that, while $L_{2}$ boost often improves
over the pGMM kernel, the improvements are usually quite small. This
observation might be also surprising because one would expect complicated
boosted tree models should substantially improve this simple one-parameter-
only pGMM kernel. Of course, the prior studies in Li (2017b, 2018) have
already demonstrated the same phenomenon, i.e., the tunable GMM kernels
(including the pGMM kernel) perform quite close to boosted trees.

The next section will be devoted to $L_{p}$ boosting which often improves
$L_{2}$ boost. To conclude this section, we should mention that the pGMM
kernel might be further improved by introducing more tuning parameters as
shown in Li (2017b, 2018), or by combination with other types of kernels such
as the strategy in the design of the “CoRE Kernel” (Li, 2014) (which combines
the cosine kernel with the (0/1)-min-max kernel).

##  3 Regression by $L_{p}$ Boosting

Boosting algorithms (Schapire, 1990; Freund, 1995; Freund and Schapire, 1997;
Bartlett et al., 1998; Schapire and Singer, 1999; Friedman et al., 2000;
Friedman, 2001) are popular in machine learning research and applications. It
is the standard practice to integrate boosting with trees (Brieman et al.,
1983) to produce accurate and robust prediction results. In this paper, we
adopt the same codebase of “Fast ABC-Boost” (fast adaptive base class boost)
(Li and Zhao, 2022a, c) to implement $L_{p}$ boost:

  1. 1.

The explicit gain formula for tree split using second-order information is re-
derived for $L_{p}$ boosting regression. The same type of explicit second-
order formula as derived in Li (2010) for classification has become the
standard implementation in popular tree platforms.

  2. 2.

We use the same adaptive binning strategy developed in Li et al. (2007) to
preprocess the features into discrete integer values. This type of histogram-
based implementation of trees is also common in popular tree platforms. As
reported in Li and Zhao (2022c), this simple (fixed-length) binning method is
still surprisingly effective, compared with more sophisticated binning
algorithms implemented in other tree platforms.

To learn more about the ABC-Boost package, readers are also welcome to consult
the following links (lecture notes, tutorials, and discussions):

http://statistics.rutgers.edu/home/pingli/STSCI6520/Lecture/ABC-LogitBoost.pdf
.
http://www.stat.rutgers.edu/home/pingli/doc/PingLiTutorial.pdf (pages 15–77).
https://hunch.net/?p=1467 .

###  3.1 $L_{p}$ Boosting for Regression Using Second-Order Information

We denote a training dataset by $\\{y_{i},\mathbf{x}_{i}\\}_{i=1}^{n}$, where
$n$ is the number of training samples, $\mathbf{x}_{i}$ is the $i$-th feature
vector, and $y_{i}$ is the $i$-th observation value. Our goal is to build a
model $F(\mathbf{x})$ to minimize the $L_{p}$ loss as follows:

$\displaystyle
L_{p}=\frac{1}{n}\sum_{i=1}^{n}L_{p,i}=\frac{1}{n}\sum_{i=1}^{n}|y_{i}-F_{i}|^{p},\hskip
14.45377pt\text{where }F_{i}=F(\mathbf{x}_{i}).$ (11)

Following the “additive model” paradigm (Friedman et al., 2000; Friedman,
2001), we let $F$ be a function of $M$ terms:

$\displaystyle F^{(M)}(\mathbf{x})=\sum_{m=1}^{M}f_{m}(\mathbf{x}),$ (12)

where $f_{m}(\mathbf{x})$, the base learner, is a regression tree and learned
from the data in a stagewise greedy fashion. Following the idea from Friedman
et al. (2000), at each boosting iteration, we fit $f_{m}$ by weighted least
squares, with responses $\\{z_{i}\\}$ and weights $\\{w_{i}\\}$:

$\displaystyle z_{i}=\frac{-L_{p,i}^{\prime}}{L_{p,i}^{\prime\prime}},\hskip
14.45377ptw_{i}=L_{p,i}^{\prime\prime},\hskip 14.45377pt$ (13)
$\displaystyle\text{where}\ \
L_{p,i}^{\prime}=\frac{\partial{L_{p,i}}}{\partial F_{i}}\ \ \text{and }\
L_{p,i}^{\prime\prime}=\frac{\partial^{2}{L_{p,i}}}{\partial F_{i}^{2}}.$

We adopt the derivation from Li (2010) to obtain the corresponding gain
formula needed for deciding the split location in building regression trees
using responses $\\{z_{i}\\}$ and weights $\\{w_{i}\\}$. Historically,
boosting based on the weighted least square procedure was believed to have
numerical issues (Friedman et al., 2000, 2008), and hence later Friedman
(2001) proposed using only the first derivatives to fit the trees, i.e.,

$\displaystyle z_{i}=-L_{p,i}^{\prime},\hskip 14.45377ptw_{i}=1.$ (14)

Of course, it is now clear that, as shown in Li (2010), one can derive the
explicit and numerically stable/robust formula for computing the gains using
second-order information.

Specifically, for the $L_{p}$ loss (11), we can write down its first derive,
for $p\geq 1$:

$\displaystyle\frac{\partial L_{p,i}}{\partial
F_{i}}=-p|y_{i}-F_{i}|^{p-1}\text{sign}\left(y_{i}-F_{i}\right),$ (15)

and the second derivative, for $p\geq 2$:

$\displaystyle\frac{\partial^{2}L_{p,i}}{\partial
F_{i}^{2}}=p(p-1)|y_{i}-F_{i}|^{p-2}.$ (16)

Note that $\frac{\partial^{2}L_{p,i}}{\partial F_{i}^{2}}=2$ when $p=2$.

###  3.2 Tree-Splitting Criterion Using Second-Order Information

Here we repeat derivations in Li (2010). Consider a tree node with $N$ data
points and consider one particular feature. We have the weights $w_{i}$ and
the response values $z_{i}$, $i=1$ to $N$. The data points are already sorted
according to the feature values. The tree-splitting procedure is to find the
index $s$, $1\leq s<N$, such that the weighted square error (SE) is reduced
the most if split at $s$.

That is, we seek the $s$ to maximize

$\displaystyle Gain(s)=$ $\displaystyle SE_{total}-(SE_{left}+SE_{right})$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{N}(z_{i}-\bar{z})^{2}w_{i}-\left[\sum_{i=1}^{s}(z_{i}-\bar{z}_{L})^{2}w_{i}+\sum_{i=s+1}^{N}(z_{i}-\bar{z}_{R})^{2}w_{i}\right],$

where $\bar{z}=\frac{\sum_{i=1}^{N}z_{i}w_{i}}{\sum_{i=1}^{N}w_{i}}$,
$\bar{z}_{left}=\frac{\sum_{i=1}^{s}z_{i}w_{i}}{\sum_{i=1}^{s}w_{i}}$,
$\bar{z}_{right}=\frac{\sum_{i=s+1}^{N}z_{i}w_{i}}{\sum_{i=s+1}^{N}w_{i}}$.

With some algebra, one can obtain

$\displaystyle\sum_{i=1}^{N}(z_{i}-\bar{z})^{2}w_{i}=$
$\displaystyle\sum_{i=1}^{N}z_{i}^{2}w_{i}+\bar{z}^{2}w_{i}-2z_{i}\bar{z}w_{i}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{N}z_{i}^{2}w_{i}+\left(\frac{\sum_{i=1}^{N}z_{i}w_{i}}{\sum_{i=1}^{N}w_{i}}\right)^{2}\sum_{i=1}^{N}w_{i}-2\frac{\sum_{i=1}^{N}z_{i}w_{i}}{\sum_{i=1}^{N}w_{i}}\sum_{i=1}^{N}z_{i}w_{i}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{N}z_{i}^{2}w_{i}-\frac{\left(\sum_{i=1}^{N}z_{i}w_{i}\right)^{2}}{\sum_{i=1}^{N}w_{i}}$
$\displaystyle\sum_{i=1}^{s}(z_{i}-\bar{z}_{left})^{2}w_{i}=$
$\displaystyle\sum_{i=1}^{s}z_{i}^{2}w_{i}-\frac{\left(\sum_{i=1}^{s}z_{i}w_{i}\right)^{2}}{\sum_{i=1}^{t}w_{i}}$
$\displaystyle\sum_{i=s+1}^{N}(z_{i}-\bar{z}_{right})^{2}w_{i}=$
$\displaystyle\sum_{i=s+1}^{N}z_{i}^{2}w_{i}-\frac{\left(\sum_{i=s+1}^{N}z_{i}w_{i}\right)^{2}}{\sum_{i=s+1}^{N}w_{i}}$

Therefore, after simplification, we obtain

$\displaystyle Gain(s)=$
$\displaystyle\frac{\left[\sum_{i=1}^{s}z_{i}w_{i}\right]^{2}}{\sum_{i=1}^{s}w_{i}}+\frac{\left[\sum_{i=s+1}^{N}z_{i}w_{i}\right]^{2}}{\sum_{i=s+1}^{N}w_{i}}-\frac{\left[\sum_{i=1}^{N}z_{i}w_{i}\right]^{2}}{\sum_{i=1}^{N}w_{i}}$

Plugging in $z_{i}=-L_{i}^{\prime}/L_{i}^{\prime\prime}$,
$w_{i}=L_{i}^{\prime\prime}$ yields,

$\displaystyle Gain(s)=$
$\displaystyle\frac{\left[\sum_{i=1}^{s}L_{i}^{\prime}\right]^{2}}{\sum_{i=1}^{s}L_{i}^{\prime\prime}}+\frac{\left[\sum_{i=s+1}^{N}L_{i}^{\prime}\right]^{2}}{\sum_{i=s+1}^{N}L_{i}^{\prime\prime}}-\frac{\left[\sum_{i=1}^{N}L_{i}^{\prime}\right]^{2}}{\sum_{i=1}^{N}L_{i}^{\prime\prime}}.$
(17)

This procedure is numerically robust/stable because we never need to directly
compute the response values $z_{i}=-L_{i}^{\prime}/L_{i}^{\prime\prime}$,
which can (and should) approach infinity easily. Because the original
LogitBoost (Friedman et al., 2000) directly used the individual response
values $z_{i}=-L_{i}^{\prime}/L_{i}^{\prime\prime}$, the procedure was
believed to have numerical issues, which was one motivation for Friedman
(2001) to use only the first derivatives to build tress i.e.,
$z_{i}=L_{i}^{\prime}$ $w_{i}=1$. Thus the gain formula becomes:

$\displaystyle UGain(s)=$
$\displaystyle\frac{1}{s}\left[\sum_{i=1}^{s}L_{i}^{\prime}\right]^{2}+\frac{1}{N-s}\left[\sum_{i=s+1}^{N}L_{i}^{\prime}\right]^{2}-\frac{1}{N}\left[\sum_{i=1}^{N}L_{i}^{\prime}\right]^{2}.$
(18)

Note that in the above derivations, we simply use $L_{i}$, $L_{i}^{\prime}$,
and $L_{i}^{\prime\prime}$ by dropping the subscript $p$ (e.g., $L_{p,i}$)
because the formulas are really applicable to general loss functions, not just
the $L_{p}$ loss.

###  3.3 $L_{p}$ Boosting Algorithm

Algorithm 1 describes Robust LogitBoost using the tree split gain formula (17)
(for $p\geq 2$) or the tree split gain formula (18) (for $1\leq p<2$). Note
that after trees are constructed, the values of the terminal nodes are
computed by

$\displaystyle\frac{\sum_{node}z_{i,k}w_{i,k}}{\sum_{node}w_{i,k}}=\frac{\sum_{node}-L_{i}^{\prime}}{\sum_{node}L_{i}^{\prime\prime}},$

which explains Line 5 of Algorithm 1. When $1\leq p<2$, because the second
derivative $L^{\prime\prime}_{i}$ does not exist, we follow Friedman (2001) by
only using the first derivatives to build the trees using the tree split gain
formula (18), and we update the note values by

$\displaystyle\frac{\sum_{node}z_{i,k}w_{i,k}}{\sum_{node}w_{i,k}}=\frac{\sum_{node}-L_{i}^{\prime}}{p\times\\#|node|},$

which explains Line 9 of Algorithm 1. Note that we use $p\times\\#|node|$
instead of just $\times\\#|node|$ to avoid potential ambiguity at $p=2$.

In retrospect, deriving Eq. (17), the explicit tree split gain formula using
second-order information, is straightforward. Nevertheless, until the formula
was first presented by Li (2010), the original LogitBoost was believed to have
numerical issues and the more robust MART algorithm was a popular alternative
(Friedman et al., 2000, 2008). As shown in Li (2010), in many datasets,
because MART used only the first derivative information for tree split, MART
typically did not achieve as good accuracy as Robust LogitBoost. Nowadays, the
split gain formula in Eq. (17) is the standard implementation in popular tree
platforms. On the other hand, we should emphasize that it is not guaranteed
that boosting using second derivatives would always improve over boosting
using only first derivatives. It might be good to maintain the implementations
of both approaches for practitioners to choose from (Li and Zhao, 2022c).

1 $F_{i}=0$, $i=1$ to $n$

2 For $m=1$ to $M$ Do

3 If $p\geq 2$ Do

4 $\left\\{R_{j,m}\right\\}_{j=1}^{J}=J$-terminal node weighted regression
tree from $\\{z_{i}=-L_{i}^{\prime}/L_{i}^{\prime\prime},\ \
w_{i}=L_{i}^{\prime\prime},\ \ \mathbf{x}_{i}\\}_{i=1}^{n}$, using the tree
split gain formula Eq. (17).

5 $\beta_{j,m}=\frac{\sum_{\mathbf{x}_{i}\in
R_{j,m}}-L_{i}^{\prime}}{\sum_{\mathbf{x}_{i}\in
R_{j,m}}L_{i}^{\prime\prime}}$

6 End

7 If $1\leq p<2$ Do

8 $\left\\{R_{j,m}\right\\}_{j=1}^{J}=J$-terminal node regression tree from
$\\{z_{i}=-L_{i}^{\prime},\ \ \mathbf{x}_{i}\\}_{i=1}^{n}$, using the tree
split gain formula Eq. (18).

9 $\beta_{j,m}=\frac{\sum_{\mathbf{x}_{i}\in
R_{j,m}}-L_{i}^{\prime}}{p\times\\#|R_{j,m}|}$

10 End

11 $F_{i}=F_{i}+\nu\sum_{j=1}^{J}\beta_{j,m}1_{\mathbf{x}_{i}\in R_{j,m}}$

End

Algorithm 1 $L_{p}$ boosting.
$L^{\prime}=-p|y_{i}-F_{i}|^{p-1}\text{sign}\left(y_{i}-F_{i}\right)$,
$L^{\prime\prime}=p(p-1)|y_{i}-F_{i}|^{p-2}$.

###  3.4 Experiments

We have implemented $L_{p}$ regression using the same codebase of “Fast ABC-
Boost” (Li and Zhao, 2022a, c) and we test it on the same datasets as listed
in Table 1. How to evaluate $L_{p}$ regression and compare it with other
algorithms is an interesting question. While the optimization procedure of
$L_{p}$ regression is to minimize the $L_{p}$ loss

$\displaystyle L_{p}=\frac{1}{n}\sum_{i=1}^{n}|y_{i}-F_{i}|^{p},$

we decide to report the $L_{2}$ loss:
$L_{2}=\frac{1}{n}\sum_{i=1}^{n}|y_{i}-F_{i}|^{2}$ in Figure 2, regardless of
which $p$ we use in the $L_{p}$ regression. Note that in Figure 2, we also
call the $L_{2}$ loss as the MSE in the y-axis. In the open-source code (Li
and Zhao, 2022c), we output the $L_{2}$ loss as well as the $L_{p}$ loss.

We experiment with parameters $J\in\\{6,10,20\\}$, $\nu\in\\{0.06,0.1,0.2\\}$,
and $M=10000$ iterations. We adopt a conservative early stopping criterion and
exit after the $L_{p}$ loss is lower than

$\displaystyle\epsilon^{p/2}\times\frac{1}{n}\sum_{i=1}^{n}{|y_{i}|^{p}},$
(19)

where $\epsilon=10^{-5}$ by default which can be adjusted by users.

Figure 2 reports the best test MSEs overall $J$, $\nu$, and iterations, for
each fixed $p$ value. We can see that, for some datasets, $L_{p}$ boosting
with $p=2$ indeed achieves (close to) the best (lowest) $L_{2}$ loss. However,
for many other datasets, $L_{p}$ boost with $p>2$ achieves lower $L_{2}$ loss
than $L_{2}$ boost. These results indicate that practitioners might be able to
effectively treat $p$ as a tuning parameter in order to achieve better $L_{2}$
loss.

Figure 3 plots the test $L_{2}$ losses (MSEs) for all the iterations of the
Mimage dataset, at a particular set of parameters $J$, $\nu$, $p$. From the
plots, it appears that the (conservative) stopping criterion in Eq. (19) is
quite reasonable at least for $p\geq 2$. It might be too conservative for
$p<2$.

Figure 2: Test MSEs with respect to $p$, using $L_{p}$ boosting. The dashed
horizontal lines represent the test MSEs of the pGMM kernel. $L_{p}$ boosting
outperforms the pGMM kernel but differences are often not too large.
Interestingly, for many datasets, $p=2$ is not the optimal choice in $L_{p}$
boosting.

Figure 3: Test MSE history at each set of parameters $(J,\nu,p)$, for the
Mimage dataset. The stopping criterion in Eq. (19) is used which appears to be
perhaps too conservative for $p<2$.

##  4 Conclusion

In the context of regression, this paper combines two contributions: 1) kernel
ridge regression using the pGMM kernel; and 2) $L_{p}$ boosting for
regression. The simple (one-parameter only) pGMM kernel is surprisingly
effective for regression. The parameter $p$ in the pGMM kernel is
mathematically equivalent to applying a $p$-powered transformation on the
original data before computing the GMM kernel. In practice, the pGMM kernel
can be effectively hashed via consistent weighted sampling or extremal process
sampling (Li et al., 2021), which are numerically stable regardless of the $p$
values. If instead we directly apply the power transformation on the original
data, numerical problems can easily occur. We hope the presented experiments
on pGMM kernel for regression would help encourage the use of the pGMM kernel
and variants in machine learning research and practice.

$L_{p}$ boosting is also effective for regression. Different from the $p$ in
the pGMM kernel, the parameter $p$ in $L_{p}$ boosting is for tuning the loss
function used for training. While $L_{2}$ boosting is popular and standard in
practice, using $L_{p}$ boosting is as convenient as $L_{2}$ when boosting is
equipped with the explicit gain formula using second derivatives of the loss
function. Practitioners can simply treat the $p$ as an additional tuning
parameter which might help achieve lower regression errors. $L_{p}$ boost has
been implemented and included in the “Fast ABC-Boost” package (Li and Zhao,
2022c). Typically, $L_{p}$ boosting could achieve lower regression errors than
the pGMM kernel, but the gap in performance is often quite small especially if
the original data are reasonably preprocessed.

## References

  * Bartlett et al. (1998) Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E. Schapire.  Boosting the margin: a new explanation for the effectiveness of voting methods.  _The Annals of Statistics_ , 26(5):1651–1686, 1998.
  * Bishop and Nasrabadi (2006) Christopher M Bishop and Nasser M Nasrabadi.  _Pattern recognition and machine learning_ , volume 4.  Springer, 2006.
  * Brieman et al. (1983) Leo Brieman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone.  _Classification and Regression Trees_.  Wadsworth, Belmont, CA, 1983.
  * Charikar (2002) Moses S. Charikar.  Similarity estimation techniques from rounding algorithms.  In _Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC)_ , pages 380–388, Montreal, Canada, 2002.
  * Freund (1995) Yoav Freund.  Boosting a weak learning algorithm by majority.  _Inf. Comput._ , 121(2):256–285, 1995.
  * Freund and Schapire (1997) Yoav Freund and Robert E. Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  _J. Comput. Syst. Sci._ , 55(1):119–139, 1997\.
  * Friedman (2001) Jerome H. Friedman.  Greedy function approximation: A gradient boosting machine.  _The Annals of Statistics_ , 29(5):1189–1232, 2001.
  * Friedman et al. (2000) Jerome H. Friedman, Trevor J. Hastie, and Robert Tibshirani.  Additive logistic regression: a statistical view of boosting.  _The Annals of Statistics_ , 28(2):337–407, 2000\.
  * Friedman et al. (2008) Jerome H. Friedman, Trevor J. Hastie, and Robert Tibshirani.  Response to evidence contrary to the statistical view of boosting.  _J. Mach. Learn. Res._ , 9:175–180, 2008.
  * Hastie et al. (2009) Trevor J. Hastie, Robert Tibshirani, and Jerome H. Friedman.  _The elements of statistical learning: data mining, inference, and prediction_.  Springer, 2 edition, 2009.
  * Ioffe (2010) Sergey Ioffe.  Improved consistent sampling, weighted minhash and L1 sketching.  In _Proceedings of the 10th IEEE International Conference on Data Mining (ICDM)_ , pages 246–255, Sydney, Australia, 2010.
  * Kleinberg and Tardos (1999) Jon Kleinberg and Eva Tardos.  Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields.  In _Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 14–23, New York, NY, 1999.
  * Larochelle et al. (2007) Hugo Larochelle, Dumitru Erhan, Aaron C. Courville, James Bergstra, and Yoshua Bengio.  An empirical evaluation of deep architectures on problems with many factors of variation.  In _Proceedings of the Twenty-Fourth International Conference on Machine Learning (ICML)_ , pages 473–480, Corvalis, Oregon, 2007.
  * Li (2009) Ping Li.  ABC-Boost: Adaptive base class boost for multi-class classification.  In _Proceedings of the 26th Annual International Conference on Machine Learning (ICML)_ , pages 625–632, Montreal, Canada, 2009.
  * Li (2010) Ping Li.  Robust logitboost and adaptive base class (abc) logitboost.  In _Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI)_ , pages 302–311, Catalina Island, CA, 2010.
  * Li (2014) Ping Li.  CoRE Kernels.  In _Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence (UAI)_ , pages 496–504, Quebec City, Canada, 2014.
  * Li (2017a) Ping Li.  Linearized GMM kernels and normalized random Fourier features.  In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 315–324, 2017a.
  * Li (2017b) Ping Li.  Tunable GMM kernels.  _arXiv preprint arXiv:1701.02046_ , 2017b.
  * Li (2018) Ping Li.  Several tunable GMM kernels.  _arXiv preprint arXiv:1805.02830_ , 2018.
  * Li and Zhang (2017) Ping Li and Cun-Hui Zhang.  Theory of the GMM kernel.  In _Proceedings of the 26th International Conference on World Wide Web (WWW)_ , pages 1053–1062, Perth, Australia, 2017.
  * Li and Zhao (2022a) Ping Li and Weijie Zhao.  Fast ABC-Boost: A unified framework for selecting the base class in multi-class classification.  _arXiv preprint arXiv:2205.10927_ , 2022a.
  * Li and Zhao (2022b) Ping Li and Weijie Zhao.  GCWSNet: Generalized consistent weighted sampling for scalable and accurate training of neural networks.  _arXiv preprint arXiv:2201.02283_ , 2022b.
  * Li and Zhao (2022c) Ping Li and Weijie Zhao.  Package for Fast ABC-Boost.  _https://github.com/pltrees/abcboost_ , 2022c.
  * Li et al. (2007) Ping Li, Christopher J. C. Burges, and Qiang Wu.  Mcrank: Learning to rank using multiple classification and gradient boosting.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 897–904, Vancouver, Canada, 2007.
  * Li et al. (2010) Ping Li, Michael W. Mahoney, and Yiyuan She.  Approximating higher-order distances using random projections.  In _Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence (UAI)_ , pages 312–321, Catalina Island, CA, 2010.
  * Li et al. (2021) Ping Li, Xiaoyun Li, Gennady Samorodnitsky, and Weijie Zhao.  Consistent sampling through extremal process.  In _Proceedings of the Web Conference (WWW)_ , Virtual, 2021.
  * Manasse et al. (2010) Mark Manasse, Frank McSherry, and Kunal Talwar.  Consistent weighted sampling.  Technical Report MSR-TR-2010-73, Microsoft Research, 2010.
  * Schapire (1990) Robert E. Schapire.  The strength of weak learnability.  _Mach. Learn._ , 5:197–227, 1990.
  * Schapire and Singer (1999) Robert E. Schapire and Yoram Singer.  Improved boosting algorithms using confidence-rated predictions.  _Mach. Learn._ , 37(3):297–336, 1999.
  * Schölkopf and Smola (2002) Bernhard Schölkopf and Alexander J Smola.  _Learning with kernels: support vector machines, regularization, optimization, and beyond_.  MIT press, 2002.
  * Vapnik (1999) Vladimir Vapnik.  _The nature of statistical learning theory_.  Springer science & business media, 1999.