# A Framework for an Assessment of the Kernel-target Alignment in Tree
Ensemble Kernel Learning

Dai Feng  Data and Statistical Sciences, AbbVie Inc., North Chicago, IL,
United States of America<EMAIL_ADDRESS>Richard Baumgartner  Biometrics
Research, Merck & Co., Inc., Kenilworth, NJ, United States of America
<EMAIL_ADDRESS>
###### Abstract

Kernels ensuing from tree ensembles such as random forest (RF) or gradient
boosted trees (GBT), when used for kernel learning, have been shown to be
competitive to their respective tree ensembles (particularly in higher
dimensional scenarios). On the other hand, it has been also shown that
performance of the kernel algorithms depends on the degree of the kernel-
target alignment. However, the kernel-target alignment for kernel learning
based on the tree ensembles has not been investigated and filling this gap is
the main goal of our work.

Using the eigenanalysis of the kernel matrix, we demonstrate that for
continuous targets good performance of the tree-based kernel learning is
associated with strong kernel-target alignment. Moreover, we show that well
performing tree ensemble based kernels are characterized by strong target
aligned components that are expressed through scalar products between the
eigenvectors of the kernel matrix and the target. This suggests that when tree
ensemble based kernel learning is successful, relevant information for the
supervised problem is concentrated near lower dimensional manifold spanned by
the target aligned components. Persistence of the strong target aligned
components in tree ensemble based kernels is further supported by sensitivity
analysis via landmark learning. In addition to a comprehensive simulation
study, we also provide experimental results from several real life data sets
that are in line with the simulations.

###### keywords:

tree-based ensembles , kernel learning , kernel-target alignment ,
eigenanalysis , relevant dimensionality

##  1 Introduction

Tree-based ensembles such as random forest (RF) and gradient boosted trees
(GBT) are a mainstay in machine learning and in particular they are considered
as dominant algorithms for tabular data [1]. Tree-based ensembles can be also
interpreted as kernel generators and this interpretation has been expounded
theoretically to investigate their asymptotic properties ([2] and [3]). On the
other hand, the RF and GBT kernels plugged into kernel learning have been
shown to perform well, even outperforming their respective ensembles in
comprehensive simulations and real life data sets [4],[5].

The kernel-target alignment has been first proposed in [6],[7] for
classification and later extended in [8] for regression as a means of
characterization of the relevant information in supervised learning. It has
been shown that the kernel-target alignment can be quantified using
eigenvectors of the kernel matrix and the target variable. The kernel-target
alignment enables assessment of a match of a given kernel to the learning
problem represented by a particular data set. In Refs. [6],[7], the analysis
of kernel-target alignment was applied to classification, in [8] it was used
for regression and in [9] it was applied in the analysis of hidden layers of
deep neural networks.

Landmark (prototype) or (dis)similarity based learning [10], [11], can be used
as an alternative way to develop prediction models in nonlinear feature spaces
via the kernel matrix [12],[13]. In similarity/dissimilarity learning the
kernel entries are explicitly interpreted as pairwise
similarities/dissimilarities between the points (samples). Recasting the
problem this way, prediction models can be built accordingly. Tree ensemble
generated kernels can therefore be readily used within this paradigm.

Kernel-target alignment has never been evaluated for the tree-based ensembles,
however eigenanalysis of the RF kernel matrix was suggested as potentially
useful in [14]. Focus of our investigation is the kernel-target alignment of
the tree ensemble based kernels and its relationship with the performance of
related kernel learning. Furthermore, we propose a sensitivity analysis
through landmark learning. The remainder of the manuscript is organized as
follows: Section 2 introduces the theoretical framework of the tree ensemble
learning, formalizes the notion of the kernel-target alignment and landmark
learning, Section 3 details a simulation study that systematically evaluates
kernel-target alignment and performance of the ensemble based kernels, Section
4 summarizes the experiments on real life data sets and Section 5 provides
discussion, conclusions and future research directions.

##  2 Methods

###  2.1 Terminology

Following Breiman [14] and Refs. [15], [3] and [2], we consider a supervised
learning problem, where training set of $n$ pairs:
$D_{n}=\\{(\mbox{\boldmath${X_{1}}$},Y_{1}),(\mbox{\boldmath${X_{2}}$},Y_{2}),\ldots,({\mbox{\boldmath${X_{1}}$},Y_{n}})\\}$
is provided. $\mbox{\boldmath${X_{i}}$}\in R^{p}$. In our case $Y_{i}$ is a
continuous target, for which the $Y_{i}\in R$. Let the target vector be then
$\mbox{\boldmath${Y}$}=[Y_{i},Y_{2},\ldots,Y_{n}]^{T}$.

###  2.2 Tree Ensemble Based Kernel Learning

Kernel methods in the machine learning literature are a class of methods that
are formulated in terms of a similarity (Gram) matrix ${K}$. The similarity
matrix $K_{i,j}=k(\mbox{\boldmath${X_{i}}$},\mbox{\boldmath${X_{j}}$})$
represents the similarity between two points ${X_{i}}$ and ${X_{j}}$. Kernel
methods have been well developed and there is a large body of references
covering their different aspects [16],[17],[18]. In our work we used a common
kernel algorithm, namely kernel ridge regression (KRR). KRR is a kernelized
version of the traditional linear ridge regression with the L2-norm penalty.
Given the kernel matrix ${K}$ estimated from the training set, first the
coefficients ${\alpha}$ of the (linear) KRR predictor in the non-linear
feature space induced by the kernel $k(.,.)$ are obtained:

${\alpha}$ $\displaystyle=$
$\displaystyle(\mbox{\boldmath${K}$}+\lambda\mbox{\boldmath${I_{n}}$})^{-1}\mbox{\boldmath${Y}$}$
(1)

where $\lambda$ is the regularization parameter.

The KRR predictor $h_{\textrm{KRR}}(\mbox{\boldmath${X}$})$ is given as:

$\displaystyle h_{KRR}(\mbox{\boldmath${X}$})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\alpha_{i}\mbox{\boldmath${k(X_{i},X)}$}=\mbox{\boldmath${Y^{T}}$}(\mbox{\boldmath${K}$}+\lambda\mbox{\boldmath${I_{n}}$})^{-1}\mbox{\boldmath${K_{i}}$}$
(2)

where $\mbox{\boldmath${K_{i}}$}=(k(X_{1},X),\ldots,k(X_{n},X))$.

Tree-based ensembles are aggregated from a set of regression trees
$h_{m}(\mbox{\boldmath${X}$},D_{n}),m=1,2,\ldots,M\\}$, with
$h_{m}(\mbox{\boldmath${X}$},D_{n})$ representing a single tree. Each single
tree partitions the feature space into disjoint regions. Moreover, for a
single tree, each region in the feature partition is given by a unique
decision path from the tree root to its terminal node. As a byproduct a tree-
based kernel is naturally generated via the regression trees and their
respective feature partitions [14],[3]. Thus, a kernel that corresponds to a
tree-based ensemble is obtained as a probability that ${X_{i}}$ and ${X_{j}}$
are in the same terminal node $R_{k}$($h_{m}$) [3]

$\displaystyle
k_{ensemble}(\mbox{\boldmath${X_{i}}$},\mbox{\boldmath${X_{j}}$})=\frac{1}{M}\sum_{m=1}^{M}\sum_{k=1}^{T}I(\mbox{\boldmath${X_{i}}$},\mbox{\boldmath${X_{j}}$}\in
R_{k}(h_{m})).$ (3)

The ensemble based kernels can be obtained by various feature space
partitioning mechanisms [19]. We used the RF and extreme gradient boosting
(XGB) as an implementation of the GBT in our work and their algorithmic
details are provided for completness in the Appendix. We will use GBT and XGB
in the remainder of the manuscript, interchangeably.

###  2.3 Kernel-target Alignment

In the Ref. [6], the sample ordering according to the leading eigenvector of
the kernel matrix was shown to correspond to the class delineation and was
considered as a proxy of the kernel target alignment. This idea was further
developed in [8] via eigenanalysis of the kernel matrix.

We define the spectral (here it is also a singular value) decomposition of the
kernel matrix ${K}$ as:

${K}$ $\displaystyle=$ $\displaystyle U\Lambda U^{T}$ (4)

where $U$ is an orthonormal matrix with the columns $u_{i}$ (eigenvectors of
${K}$) and $\Lambda$ is an $n$ by $n$ diagonal matrix with eigenvalues
$\lambda_{i}$-s on the diagonal. We assume that $\lambda_{i}$-s are ordered
according to their magnitude.

The kernel-target alignment components can be obtained as an absolute value of
the scalar product $|u_{i}^{T}Y|$. The fundamental result of [8] is concerned
with the rate of the decay of kernel-target alignment components. In
particular, it was proved that under mild conditions, the kernel-target
aligned components decay at the same rate as the eigenvalues of the kernel
matrix. As a consequence of this decay, the relevant information pertaining to
the supervised problem is concentrated in the leading eigenvectors of the
kernel matrix that are strongly aligned with the target [8],[9], if such
strongly aligned components exist.

In our investigation, we used normalized kernel-target alignment components
given by the absolute value of the Pearson correlation coefficients between
$u_{i}$-s and ${Y}$, with ${K}$ being the kernel matrix obtained from the
tree-based ensembles.

###  2.4 Landmark Learning in Nonlinear Kernel Feature Spaces

In the landmark learning, the empirical similarity map (data driven embedding)
[13],[12] is generated by selecting a subset of $n_{L}$ data points
(landmarks) also referred to as a reference set [10]. A point in the feature
space is represented by the similarities to the landmarks. This approach is
akin to a dimensionality reduction of the original kernel problem to a lower
$n_{L}$ dimensional problem [13]. A linear model is subsequently developed on
the landmark features and a landmark predictor is obtained as:

$\displaystyle
h_{Landmarks}=(\mbox{\boldmath${L}$}^{T}\mbox{\boldmath${L}$})^{-1}\mbox{\boldmath${L}$}^{T}Y$
(5)

where $L$ is an $n\times n_{L}$ matrix and $n_{L}$ is number of landmarks.
$L_{i,j}=k(i,j)$ is a similarity of the point $i$ to the landmark $j$.
Consider now the singular value decomposition (SVD) of $L$:

${L}$ $\displaystyle=$ $\displaystyle U_{L}\Sigma_{L}V_{L}^{T}$ (6)

where in this case the matrix $U_{L}$ is an orthonormal matrix with the
columns $u_{L_{i}}$ (left singular vectors of ${L}$) and $\Sigma_{L}$ is an
$n_{L}$ by $n_{L}$ diagonal matrix with singular values $\sigma_{L_{i}}$ on
the diagonal. We assume that $\sigma_{L_{i}}$-s are ordered according to their
magnitude. Accordingly, the $\lambda_{L_{i}}=\sigma_{L_{i}}^{2}$-s and
$u_{L_{i}}$-s are the eigenvalues and the eigenvectors of the landmark kernel
matrix $\mbox{\boldmath${K_{L}}$}=LL^{T}$, respectively. Following the
previous considerations for ${K}$ in the section 2.3, the kernel-target
alignment components in landmark learning can be obtained as an absolute value
of the scalar product $|u_{L_{i}}^{T}Y|$. Again, we use here the absolute
value of the Pearson correlation coefficient between $u_{L_{i}}$-s and $Y$,
where $u_{L_{i}}$-s are obtained from the Equation 6.

We used landmark learning in a sensitivity analysis, where increasing number
of landmarks $n_{L}$ was randomly selected from the training set.

The code for the simulation and real life data analysis was developed in the R
programming language [20]. The ranger [21] implementation of RF and xgboost
[22] of XGB was used, respectively. All algorithms were applied using their
default parameters. The regularization parameter $\lambda$ for kernel ridge
regression was chosen at minimum value, such that the matrix,
$\mbox{\boldmath${K}$}+\lambda\mbox{\boldmath${I_{n}}$}$ was invertible.

##  3 Simulation

Simulation scenarios for kernel target alignment evaluation of RF/GBT kernels
were set up according to previously reported simulation benchmarks. They
included Friedman [23], Meier 1, Meier 2 [24], van der Laan [25] and
Checkerboard [26].

###  3.1 Simulation Setup

For each simulation scenario, the predictors were simulated from Uniform
(Friedman, Meier 1, Meier 2, van der Laan) or Normal distributions
(Checkerboard), respectively.

Continuous targets were generated as
$Y_{i}=f(\mbox{\boldmath${X_{i}}$})+\epsilon_{i}$. For the definitions of
$f(\mbox{\boldmath${X_{i}}$})$ for each simulation case see below.

The five functional relationships $f(\mbox{\boldmath${X_{i}}$})$ between the
predictors and target for different simulation settings are specified as
follows.

1\. Friedman. The setup for Friedman was as described in [23].

$\displaystyle X_{ij}$ $\displaystyle\sim$ $\displaystyle
Uniform(0,1),i=1,\ldots,n;j=1,\ldots,p$ $\displaystyle\epsilon_{i}$
$\displaystyle\sim$ $\displaystyle N(0,1)$ $\displaystyle
f(\mbox{\boldmath${X_{i}}$})$ $\displaystyle=$ $\displaystyle 10\sin{(\pi
X_{i1}X_{i2})}+20(X_{i3}-0.5)^{2}+10X_{i4}+5X_{i5}+\epsilon_{i}$

2\. Checkerboard. In addition to Friedman, we simulated data from a
Checkerboard-like model with strong correlation as in Scenario 3 of [26].

${X_{i}}$ $\displaystyle\sim$ $\displaystyle N(0,\Sigma_{p\times
p}),i=1,\ldots,n$ $\displaystyle\epsilon_{i}$ $\displaystyle\sim$
$\displaystyle N(0,1)$ $\displaystyle f(\mbox{\boldmath${X_{i}}$})$
$\displaystyle=$ $\displaystyle 2X_{i5}X_{i10}+2X_{i15}X_{i20}+\epsilon_{i}$

The $(j,k)$ component of $\Sigma$ is equal to $0.9^{|j-k|}$.

3\. van der Laan. The setup was studied in van der Laan et al. [25].

$\displaystyle X_{ij}$ $\displaystyle\sim$ $\displaystyle
Uniform(0,1),i=1,\ldots,n;j=1,\ldots,p$ $\displaystyle\epsilon_{i}$
$\displaystyle\sim$ $\displaystyle N(0,0.5)$ $\displaystyle
f(\mbox{\boldmath${X_{i}}$})$ $\displaystyle=$
$\displaystyle\tilde{X}_{i1}\tilde{X}_{i2}+\tilde{X}_{i3}^{2}+\tilde{X}_{i8}\tilde{X}_{i10}-\tilde{X}_{i6}^{2}+\epsilon_{i}$
$\displaystyle\tilde{X}_{i}$ $\displaystyle=$ $\displaystyle 2(X_{i}-0.5)$ (7)

4\. Meier 1. This setup was investigated in Meier et al. [24].

$\displaystyle X_{ij}$ $\displaystyle\sim$ $\displaystyle
Uniform(0,1),i=1,\ldots,n;j=1,\ldots,p$ $\displaystyle\epsilon_{i}$
$\displaystyle\sim$ $\displaystyle N(0,0.5)$ $\displaystyle
f(\mbox{\boldmath${X_{i}}$})$ $\displaystyle=$
$\displaystyle-\sin(2\tilde{X}_{i1})+\tilde{X}_{i2}^{2}+\tilde{X}_{i3}-\exp(\tilde{X}_{i4})+\epsilon_{i}$
$\displaystyle\tilde{X}_{i}$ $\displaystyle=$ $\displaystyle 2(X_{i}-0.5)$ (8)

5\. Meier 2. This setup was investigated in Meier et al. [24] as well.

$\displaystyle X_{ij}$ $\displaystyle\sim$ $\displaystyle
Uniform(0,1),i=1,\ldots,n;j=1,\ldots,p$ $\displaystyle\epsilon_{i}$
$\displaystyle\sim$ $\displaystyle N(0,0.5)$ $\displaystyle
f(\mbox{\boldmath${X_{i}}$})$ $\displaystyle=$
$\displaystyle-\tilde{X}_{i1}+(2\tilde{X}_{i2}-1)^{2}+\frac{\sin(2\pi\tilde{X}_{i3})}{2-\sin(2\pi\tilde{X}_{i4})}+2\cos(2\pi\tilde{X}_{i4})+4\cos^{2}(2\pi\tilde{X}_{i4})+\epsilon_{i}$
$\displaystyle\tilde{X}_{i}$ $\displaystyle=$ $\displaystyle 2(X_{i}-0.5)$ (9)

For each functional relationship $f(\mbox{\boldmath${X_{i}}$})$ (Friedman,
Checkerboard, Meier 1, Meier 2, and van der Laan), we simulated data from four
scenarios with different samples sizes n = 800 and n = 1600 and number of
features p = 20 and p = 40. Within each scenario, we simulated 200 data sets,
and for each data set we randomly chose 75% of samples as training data and
remaining 25% as test data. We repeated the analysis 200 times to evaluate the
kernel-target alignment of RF and XGB kernels on the training sets and its
relationship with the respective kernel algorithm performance on the
independent test sets.

###  3.2 Simulation Results

The kernel-target alignment spectra of the Friedman, Checkerboard, Meier 1,
Meier 2 and van der Laan simulation settings are shown in the Figs. 1, 2, 3, 4
and 5, respectively. The left and right panels in the Figures correspond to
the results obtained from the RF and XGB, respectively. On the x-axis, the
first thirty components ordered according to the decreasing eigenvalues of the
kernel matrix (singular values) are shown. These components are shown for the
ensemble derived kernel matrix $K_{ensemble}$ and the landmark matrices $L$-s.
The landmark matrices $L$ are built from a varying number of landmarks or
prototypes (nProto) including 100, 200 and 300 prototypes. The y-axis
corresponds to the absolute value of the correlation coefficient between
corresponding eigenvectors of ${K_{ensemble}}$ (or left singular vectors of
$L$) and the target $Y$.

The RF alignment spectrum for Friedman shows strong peaks corresponding to
leading eigenvectors (singular vectors) across the simulation settings Figs.
1(a,c,e,g). These peaks show the same pattern for the prototypes and their
magnitude is monotonically increasing with increasing number of prototypes
(n=100, 200 and 300). The XGB alignment spectra for Friedman are flatter than
those for the RF Figs. 1(b,d,f,h) and they are overlapping with respect to the
increasing number of prototypes.

The RF alignment spectrum for Checkerboard is similar to that of Friedman
across all simulation settings. A strong peak is associated with the second
leading eigenvector (left singular vector) Figs. 2(a,c,e,g). In contrary to
Friedman, the XGB alignment spectrum also shows strong components across all
simulation settings Figs. 2(b,d,f,h). Interestingly, for the Checkerboard,
there is little difference in the alignment spectra with respect to the number
of prototypes.

The Meier 1 and Meier 2 data sets are similar to the Friedman data set. For
the RF alignment spectrum, Meier 1 and Meier 2 show strong peaks, magnitude of
which is increases with the increasing number of prototypes (Figs.3(a,c,e,g)
and Figs. 4(a,c,e,g) for Meier 1 and Meier 2, respectively). The XGB kernel
alignment spectra are flatter, monotonically decreasing and overlapping with
respect to the number of prototypes (Figs.3(b,d,f,h) and 4(b,d,f,h) for Meier
1 and Meier 2, respectively).

For the van der Laan data set, the RF kernel alignment spectrum shows stronger
peaks for leading eigenvectors (singular vectors) as it was for the other
simulated data sets (Figs.5(a,c,e,g)). However, the alignment spectrum for van
der Laan is flat across all scenarios, indicating weak performance of XGB for
this data set.

The kernel-target alignment vs performance of the kernel and XGB kernel for
the different data generating mechanisms and simulation settings is summarized
in Figs.6(a-l). The performance on the test set was evaluated by an absolute
value of the Pearson correlation coefficient between the predicted values and
the target (Ytest) (the y-axis in the Figs.6(a-l)).

Three summaries of the kernel-target alignment on the training set have been
evaluated (the x-axis in the Figs.6(a-l)). On the left side (Figs.6(a,d,g,j)),
the mean of the absolute value of the correlation coefficient between the
first eigenvector corresponding to the largest eigenvalue (singular value) and
Ytrain is shown ([6],[7]). In the middle (Figs.6(b,e,h,k)), the mean
correlation coefficient between the eigenvector with maximum correlation with
Ytrain is shown. On the right, the mean of absolute value of the correlation
coefficient between the eigenvectors (singular vectors) of ${K}$ and Ytrain
from the best 5 (with highest correlation coefficient) among leading 10
eigenvectors is displayed. Overall, the higher the kernel-target alignment
obtained on the training set, the better the performance of the RF/XGB kernels
across the data generating mechanisms and simulation settings. The
eigenvectors corresponding to the largest eigenvalue (singular value) are not
necessarily best aligned with the target, which is demonstrated for the
Checkerboard data for both (RF and XGB) kernels and the van der Laan data set
for the XGB kernel, respectively (Figs.6(a,b,d,e,g,h,j,k)).

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 1: Kernel-target alignment spectra and relevant dimensionality—Friedman

##  4 Application Using Real Life Data Sets

###  4.1 Experimental Setup

We assessed the kernel-target alignment in tree-based ensemble kernel using
real life data sets, the summary of which is given in Table 1.

For the larger data sets (California and Protein) we randomly selected 2000
samples and split them into training and test set, with 1500 and 500 samples,
respectively. We repeated the analysis 200 times to evaluate the kernel-target
alignment of RF and XGB kernels, respectively. For the other data sets we
split the data into training and test set in the ratio 3 to 1, respectively,
and repeated the analysis 200 times. Similarly to the simulation, we evaluated
the kernel-target alignment on the training sets and related it to the
performance on the test sets.

###  4.2 Real Life Data Sets Results

The alignment spectra are given in the Figs. 7, 8, 9, 10 and 11 for
California, Boston, Protein, Concrete and CSM data sets, respectively. There
results from the RF and XGB kernels are provided in sub-figure (a) and (b),
respectively. California, Boston and Protein data sets (Figs. 7(a,b), 8(a,b)
and 9(a,b) data sets are characterized by strong peaks in the alignment
spectra for both RF and XGB kernels. The Concrete data set has multiple strong
peaks for the XGB kernel (Fig.10(b)) in contrast to that of the RF kernel. On
the other hand, the CSM data set has strong peaks for the RF kernel
(Fig.11(a)), whereas the alignment spectrum obtained from the XGB kernel is
flat (Fig.11(b)). The performance of the RF and XGB kernels in terms of the
correlation of the predictions with the target on the test set are provided in
Table 2. In addition, the average of the correlation coefficients of the top
five eigenvector components and target obtained from the training sets are
provided as a summary measure of the kernel-target alignment (see Table 2).
Using this metric, for three data sets (Boston, Protein and CSM) the RF kernel
shows higher alignment with the target than that of the XGB, and in turn, a
better performance. On the other hand, for the Concrete data set, the kernel-
target alignment for the XGB kernel is higher than that of the RF kernel. As a
consequence, the XGB kernel exhibits better performance. For the California
data set, the RF and XGB show comparable kernel-target alignment, with RF
slightly outperforming the XGB. To note, the overall alignment spectra of the
California data set for the RF and the XGB exhibit the same pattern (see
Figs.7(a),(b)).

For completeness, the results of the prediction performance in terms of the
mean squared error (MSE) are given in the Table 3.

Table 1: Summary of the real life datasets Dataset | n | p
---|---|---
California Housing [27] | 20640 | 9
Boston Housing [28],[29] | 506 | 13
Protein Tertiary Structure [29] | 45730 | 9
Concrete Compressive Strength [30], [29] | 1030 | 9
Conventional and Social Movie (CSM) [31], [29] | 187 | 12
Table 2: Performance of the RF and XGB kernels on test set and summary measures of the kernel alignment obtained from the training set. RFk and XGBk refer to the mean correlation coefficients between target and the predictions obtained from the test sets for the RF and XGB kernel, respectively. RFk5 and XGBk5 refer to the average correlation coefficient of top 5 components and target ordered according to the eigenvalues of the kernel matrix for RF and XGB kernel (from training set), respectively. The metrics are provided as means and standard deviations. Dataset | RFk | XGBk | RFk5 | XGBk5
---|---|---|---|---
California Housing | ${0.872(0.016)}$ | 0.856 (0.016) | 0.234 (0.023) | ${0.235(0.023)}$
Boston Housing | ${0.943(0.021)}$ | 0.919 (0.022) | ${0.341(0.020)}$ | 0.311 (0.022)
Protein Tertiary Structure | ${0.671(0.029)}$ | 0.575 (0.033) | ${0.161(0.025)}$ | 0.120 (0.016)
Concrete Compressive Strength | 0.965 (0.007) | ${0.966(0.008)}$ | 0.215 (0.021) | ${0.319(0.025)}$
CSM | ${0.544(0.091)}$ | 0.434 (0.104) | ${0.250(0.027)}$ | 0.144 (0.032)

##  5 Discussion and Future Work

In this paper, we have shown that for regression, the performance of the tree
ensemble (RF/XGB) based kernels is associate with the degree of the kernel-
target alignment. In a comprehensive simulation study and real life data sets
we demonstrated that strong target aligned components of the kernel matrix
${K}$ are translated into high performance of the tree ensemble based kernels.
The strongly target aligned components correspond to (typically a small number
of) eigenvectors of the kernel matrix with larger eigenvalues (i.e. they are
in the left side of the eigenvalue spectrum). However they do not necessarily
exactly follow the magnitude based ordering of the eigenvalues. This suggests
that the target aligned components span a low dimensional manifold that is
implicitly represented by the tree based kernel. Moreover, the strongly
aligned components (peaks) are persistent as shown in the sensitivity analysis
with a landmark tree based kernel learning and an increasing number of
landmarks.

The kernel-target alignment can be applied to other tree ensemble based
kernels, e.g. the recent RF and XGB variants. They include oblique, rotation
or mixup forests ([32], [33] and [34], respectively). Of interest is also the
kernel-target alignment of kernels obtained from Bayesian approaches such as
Mondrian forests [35] or Bayesian non parametric partitions and Bayesian
additive regression trees (BART), ([19] and [36]).

Furthermore, the concept of the tree ensemble based kernel is inherent to
other prediction targets such as the binomial and time to event targets that
represent classification and survival, respectively. For example, the
proximity matrix i.e. ensemble kernel for the survival forest is readily
available [15]. For the estimation of the kernel-target alignment for a
survival target, an additional challenge of incomplete information about the
target due to censoring needs to be addressed and is an interesting topic for
future research.

We used kernel ridge regression as a kernel learning algorithm in our
contribution. There have been also recent advancements in the development of
the response guided principal components [37], [38]. These have focused on
principal component regression and incorporation of sparsity constraints
through the LASSO penalty. As our results support the notion of relevant
dimensionality expressed by the target aligned components for tree ensemble
based kernels, we plan to explore sparse, response (target) guided nonlinear
principal component regression for the tree ensemble kernel learning in the
future.

##  6 Appendix

###  6.1 RF and the RF Kernel

Random Forest (RF) is defined as an ensemble of tree predictors grown on
bootstrapped samples of a training set [14]. When considering an ensemble of
tree predictors $\\{h(.,\Theta_{m},D_{n}),m=1,2,\ldots,M\\}$, with
$\\{h(.,\Theta_{m},D_{n})\\}$ representing a single tree. The
$\Theta_{1},\Theta_{2},\ldots\Theta_{M}$ are iid random variables that encode
the randomization necessary for the tree construction [2], [15].

The RF predictor is obtained as:

$\displaystyle
h_{\textrm{RF}}(\mbox{\boldmath${X}$},\Theta_{1},\ldots,\Theta_{m},D_{n})$
$\displaystyle=$
$\displaystyle\frac{1}{M}\sum_{m=1}^{M}h(\mbox{\boldmath${X}$},\Theta_{m},D_{n})$
(10)

RF kernel ensuing from the RF is defined as a probability that ${X_{i}}$ and
${X_{j}}$ are in the same terminal node $R_{k}(\Theta_{m}$) [14], [2].

$\displaystyle
k_{RF}(\mbox{\boldmath${X_{i}}$},\mbox{\boldmath${X_{j}}$})=\frac{1}{M}\sum_{m=1}^{M}\sum_{k=1}^{T}I(\mbox{\boldmath${X_{i}}$},\mbox{\boldmath${X_{j}}$}\in
R_{k}(\Theta_{m}))$ (11)

where $I(\cdot)$ denotes the indicator function.

###  6.2 Gradient Boosted Trees (GBT) and the GBT Kernel

The GBT are (similarly to RF) ensemble of tree predictors. In contrast to the
RF, the GBT ensemble predictor is obtained as a sum of weighted individual
tree predictors $h_{m}(\mbox{\boldmath${X}$},D_{n})$ through iterative
optimization of an objective (cost) function [39],[40] :

$\displaystyle h_{\textrm{GBT}}(\mbox{\boldmath${X}$},D_{n})$ $\displaystyle=$
$\displaystyle\sum_{m=1}^{M}h_{m}(\mbox{\boldmath${X}$},D_{n})$ (12)

The objective function of GBT comprises of a loss function and for the extreme
gradient boosting a regularization term is added to control the model
complexity. In our work we used the extreme gradient boosting (XGB)
implementation of the GBTs [40].

The objective function of the XGB algorithm $L_{\textrm{XGB}}$ is given
follows:

$\displaystyle L_{\textrm{XGB}}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}l(y_{i},h_{\textrm{XGB}}(X_{i}))+\Omega(h_{m})$
(13) $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}l(y_{i},h_{\textrm{XGB}}(X_{i}))+\gamma
T+0.5\lambda||w||^{2}$ (14)

where
$l(.)$ is the loss function. The loss function used in xgboost is squared
error and logistic loss for regression and classification, respectively
$\Omega$ denotes the regularization penalty
$T$, $\gamma$ is the number of tree terminal nodes and a corresponding
regularization parameter, respectively
$\lambda$ is a regularization parameter controlling for the L2 norm of the
individual tree weights $||w||^{2}$

As for the RF kernel, the XGB kernel is defined as a probability that
${X_{i}}$ and ${X_{j}}$ are in the same terminal node $R_{k}$($h_{m}$) [3].

$\displaystyle
k_{xgb}(\mbox{\boldmath${X_{i}}$},\mbox{\boldmath${X_{j}}$})=\frac{1}{M}\sum_{m=1}^{M}\sum_{k=1}^{T}I(\mbox{\boldmath${X_{i}}$},\mbox{\boldmath${X_{j}}$}\in
R_{k}(h_{m}))$ (15)

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 2: Kernel-target alignment spectra and relevant
dimensionality—Checkerboard

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 3: Kernel-target alignment spectra and relevant dimensionality—Meier 1

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 4: Kernel-target alignment spectra and relevant dimensionality—Meier 2

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 5: Kernel-target alignment spectra and relevant dimensionality—van der
Laan

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

Figure 6: Mean of absolute value of cc between the eigenvector and Ytrain from
the first component (i.e. largest eigenvalue) vs. cc between prediction and
Ytest (left). Mean of absolute value of cc between eigenvector and Ytrain from
the best component (i.e. largest absolute correlation coefficient) vs. cc
between prediction and Ytest (middle). Mean of absolute value of cc between
the eigenvector and Ytrain from the best 5 among first 10 components vs. cc
between prediction and Ytest (right)

(a)

(b)

Figure 7: Kernel-target alignment spectra and relevant
dimensionality—California housing

(a)

(b)

Figure 8: Kernel-target alignment spectra and Relevant Dimensionality—Boston
housing

(a)

(b)

Figure 9: Kernel-target alignment spectra and relevant dimensionality—Protein
Tertiary Structure

(a)

(b)

Figure 10: Kernel-target alignment spectra and relevant
dimensionality—Concrete Compressive Strength

(a)

(b)

Figure 11: Kernel-target alignment spectra and relevant dimensionality—Conventional and Social Movie Table 3: Performance (measured by the MSE) for the RF/XGB and the RF/XGB kernels Dataset | RF | XGB | RFk | XGBk
---|---|---|---|---
California housing | 3.64 $\times 10^{9}$ | 5.46 $\times 10^{9}$ | ${3.24\times 10^{9}}$ | 3.64$\times 10^{9}$
| ($3.97\times 10^{8}$) | ($6.06\times 10^{8}$) | ${(3.89\times 10^{8})}$ | ($3.86\times 10^{8}$)
Boston housing | 12.512 (4.570) | 19.172 (5.697) | ${9.806(3.61)}$ | 13.349 (3.544)
Protein Tertiary Structure | 21.248 (1.560) | 35.121(2.771) | ${20.504(1.651)}$ | 27.385(2.253)
Concrete Compressive Strength | 31.083(4.878) | 38.049(7.849) | 19.851(4.12) | ${18.647(3.907)}$
CSM | 0.727 (0.158) | 1.122(0.266) | ${0.718(0.152)}$ | 0.906(0.183)

## References

  * [1] J. Feng, Y. Yu, Z.-H. Zhou, Multi-layered gradient boosting decision trees, in: S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett (Eds.), Advances in Neural Information Processing Systems, Vol. 31, Curran Associates, Inc., 2018.
URL
https://proceedings.neurips.cc/paper/2018/file/39027dfad5138c9ca0c474d71db915c3-Paper.pdf

  * [2] E. Scornet, Random forests and kernel methods, IEEE Transactions on Information Theory 62 (3) (2016) 1485 – 1500.
  * [3] G. Chen, D. Shah, Explaining the Success of Nearest Neighbor Methods in Prediction, MIT Press, 2018, Ch. Adaptive neighbors and far away neighbors.
  * [4] A. Davies, Z. Ghahramani, The random forest kernel and other kernels for big data from random partitions., arXiv preprint arXiv:1402.4293.
  * [5] D. Feng, R. Baumgartner, (decision and regression) tree ensemble based kernels for regression and classification., arXiv preprint arXiv:2012.10737.
  * [6] N. Cristianini, J. Elisseev, J. Shawe Taylor, et al., On kernel target alignment, in: Proceedings of the Neural Information Processing Systems, NeurIPS, 2001.
  * [7] N. Cristianini, J. Elisseev, J. Shawe Taylor, et al., Innovations in Machinne Learning, Springer, 2006, Ch. On Kernel Target Alignment.
  * [8] M. Braun, J. Buhmann, K. Muller, On relevant dimensions in kernel feature spaces, Journal of Machine Learning Research 9 (2008) 1875–1908.
  * [9] G. Montavon, M. Braun, K. Muller, Kernel analysis of deep networks, Journal of Machine Learning Research 12 (2011) 2563–2581.
  * [10] E. Pekalska, P. Paclik, R. Duin, A generalized kernel approach to dissimilarity-based classification, Journal of Machine Learning Research 2 (2001) 175–211.
  * [11] J. Bien, R. Tibshirani, Prototype selection for interpretable classification, Annals of Applied Statistics 5 (4) (2011) 2403–2424.
  * [12] P. Kar, P. Jain, Similarity-based learning via data driven embeddings, Proceedings of the Advances in Neural Information Processing Systems, (2011) 1998–2006.
  * [13] M. Balcan, A. Blum, S. N, A theory of learning with similarity functions, Machine Learning 72 (2008) 89–112.
  * [14] L. Breiman, Some infinity theory for predictor ensembles, Tech. rep., Technical Report 579, Statistics Dept. UCB (2000).
  * [15] H. Ishwaran, M. Lu, Standard errors and confidence intervals for variable importance in random forest regression, classification, and survival, Statistics in Medicine (2019) 558–582.
  * [16] R. Herbich, Learning kernel classifiers, MIT Press, 2001.
  * [17] B. Schoelkopf, A. Smola, Learning with kernels, MIT Press, 2001.
  * [18] J. Friedman, T. Hastie, R. Tibshirani, The Elements of Statistical Learning, Springer, 2009.
  * [19] X. Fan, B. Li, L. Luo, et al., Bayesian nonparametric space partitions: A survey., arXiv preprint arXiv:2002.11394.
  * [20] R Core Team, R: A Language and Environment for Statistical Computing, R Foundation for Statistical Computing, Vienna, Austria (2017).
URL https://www.R-project.org/

  * [21] M. N. Wright, A. Ziegler, ranger: A fast implementation of random forests for high dimensional data in C++ and R, Journal of Statistical Software 77 (1) (2017) 1–17.  doi:10.18637/jss.v077.i01.
  * [22] T. Chen, T. He, M. Benesty, V. Khotilovich, Y. Tang, H. Cho, K. Chen, R. Mitchell, I. Cano, T. Zhou, M. Li, J. Xie, M. Lin, Y. Geng, Y. Li, xgboost: Extreme Gradient Boosting, r package version 1.2.0.1 (2020).
URL https://CRAN.R-project.org/package=xgboost

  * [23] J. H. Friedman, Multivariate adaptive regression splines, The annals of statistics (1991) 1–67.
  * [24] L. Meier, S. Van de Geer, P. Bühlmann, et al., High-dimensional additive modeling, The Annals of Statistics 37 (6B) (2009) 3779–3821.
  * [25] M. J. Van der Laan, E. C. Polley, A. E. Hubbard, Super learner, Statistical applications in genetics and molecular biology 6 (1).
  * [26] R. Zhu, D. Zeng, M. R. Kosorok, Reinforcement learning trees, Journal of the American Statistical Association 110 (512) (2015) 1770–1784.
  * [27] K. Pace, R. Barry, Sparse spatial autoregressions, Statistics & Probability Letters 33 (3) (1997) 291–297.
  * [28] D. Harrison Jr, D. Rubinfeld, Hedonic housing prices and the demand for clean air., Journal of environmental economics and management 5 (1978) 81–102.
  * [29] D. Dua, C. Graff, UCI machine learning repository (2017).
URL http://archive.ics.uci.edu/ml

  * [30] J. Yeh, Modeling of strength of high-performance concrete using artificial neural networks., Cement and Concrete research 28 (1998) 1797–1808.
  * [31] D. Ahmed, A. Jahnagir, M. A, et al., Using crowd source based features from social media and conventional features to predict the movies popularity., in: IEEE International Conference on Smart City/SocialCom/SustainCom (SmartCity), IEEE, 2015, pp. 273–278.
  * [32] D. Menze, B. Kelm, U. Koethe, et al., On oblique random forests., in: Proceedings ECML/PKDD, Lecture Notes in Computer Science, 6911, Springer, 2011, pp. 453–469.
  * [33] J. Rodriguez, L. Kuncheva, C. Alonso, Rotation forest: A new classifier ensemble method, IEEE Trans Pattern Anal Mach Intell 28 (10) (2006) 1619–30.
  * [34] J. Rodriguez, M. Juez-Gil, A. Arnaiz-González, et al., An experimental evaluation of mixup regression forests, Expert Systems and Applications 151 (2020) 113376.
  * [35] M. Balog, B. Lakshminarayanan, Z. Ghahramani, D. M. Roy, Y. W. Teh, The mondrian kernel, in: Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, 2016, p. 32–41.
  * [36] A. R. Linero, A review of tree-based bayesian methods, Communications for Statistical Applications and Methods 24 (6) (2017) 543–559.
  * [37] W. Lang, H. Zou, A simple method to improve principal components regression., Stat (2020) e288.
  * [38] J. Tay, J. Friedman, R. Tibshirani, Principal component-guided sparse regression., The Canadian Journal of Statistics.
  * [39] J. Friedman, Greedy function approximation: A gradient boosting machine., Annals of Statistics 29 (5) (2001) 1189–1232.
  * [40] T. Chen, G. C, A scalable tree boosting system., in: Proc. 22nd ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2016, pp. 785–794.


# Building Effective Large-Scale Traffic State Prediction System: Traffic4cast
Challenge Solution

Yang Liu  Southeast Univeristy, School of Transportation, Nanjing, China
Email<EMAIL_ADDRESS>Equal Contribution  Fanyou Wu  Purdue University,
Department of Forestry and Natural Resource, West Lafayette, USA  Email:
<EMAIL_ADDRESS>Equal Contribution  Baosheng Yu  The University of Sydney,
UBTECH Sydney AI Centre, School of Computer Science, Sydney, Australia
Zhiyuan Liu  Southeast Univeristy, School of Transportation, Nanjing, China
Jieping Ye  DiDi Chuxing, Didi AI Labs, Beijing, China

###### Abstract

How to build an effective large-scale traffic state prediction system is a
challenging but highly valuable problem. This study focuses on the
construction of an effective solution designed for spatio-temporal data to
predict large- scale traffic state. Considering the large data size in
Traffic4cast Challenge and our limited computational resources, we emphasize
model design to achieve a relatively high prediction performance within
acceptable running time. We adopt a structure similar to U-net and use a mask
instead of spatial attention to address the data sparsity. Then, combined with
the experience of time series prediction problem, we design a number of
features, which are input into the model as different channels. Region
cropping is used to decrease the difference between the size of the receptive
field and the study area, and the models can be specially optimized for each
sub-region. The fusion of interdisciplinary knowledge and experience is an
emerging demand in classical traffic research. Several interdisciplinary
studies we have been studying are also discussed in the Complementary
Challenges. The source codes are available in
https://github.com/wufanyou/traffic4cast-TLab.

##  1 Introduction

Real-time traffic state prediction is an essential component for traffic
control and management in an urban road network. The ability to predict future
traffic state (e.g., flow, speed) can help improve traffic conditions, fleet
organization, utilization rate, and social welfare [1, 2]. Essentially, the
traffic prediction is a time series problem, which is performed based on the
changes of historical demand. A representative time-series prediction tool is
the recurrent neural network (RNN), along with its diverse variants [3, 4].
Apart from the temporal dimension, the correlation in the spatial dimension is
also extensively incorporated by many works. Regions that are close to each
other or share similar land-use structures may exhibit a homogeneous demand
pattern. Techniques widely applied in computer vision like convolutional
neural network (CNN) [2, 5] and the emerging graph-based networks [6, 7, 8, 9]
are often adopted. Furthermore, multi-source data are also introduced in some
literature to allow for the external influencing factors, such as weather
conditions and neighboring points-of-interest [10, 11].

##  2 Data Description and Problem Definition

The organizer provides industrial-scale real-world data for 3 full cities
(Berlin, Istanbul and Moscow) throughout a year. The organizer divides the
whole city into a $436\times 495$ grid, each pixel of which represents a
region of $100\,m\times 100\,m$. There are a totally of 288 frames each day,
and each frame of the raw data represents 5-minutes aggregated information
with three channels, i.e., traffic volume, speed, and direction, respectively.
The sample images are illustrated in Figure 1. The data of volume and speed
are scaled to $[0,255]$ through a min-max scaler. Regarding the direction
data, they are obtained by binning probes into four heading directions of
North-East $(0,90)$, South-East $(90,180)$, South-West $(180,270)$ and North-
West $(270,359]$. In this way, the raw heading values $[0,359]$ are mapped as
four distinct values of $\\{1,85,170,255\\}$ in the order of $(NW,NE,SW,SE)$,
and the major heading bin, e.g. the bin containing the largest number of
points, is selected. Here, missing values are also represented by 0.

Problem: This challenge can be split into three sub-tasks, i.e., use the given
data to predict speed, flow, and direction at each pixel separately in the
given time intervals, which is a typical time series prediction problem.
Pixel-wise mean squared error (MSE) is used to evaluate the performance for
ranking the submitted prediction results.

(a) Berlin

(b) Istanbul

(c) Moscow

Figure 1:  Sample Images from traffic4cast data set for May 1st, 2018. In
general, the greener the color, the heavier the road.

##  3 Solution

###  3.1 Network

Increasing the receptive field. One important attribute of the data is the
spatial correlation. This means that the traffic state in a specific region
can be affected by the adjacent regions. For example, when traffic congestion
occurs in a link of the urban road network, it might propagate upstream, thus
causing traffic congestion in neighboring areas. To capture this phenomenon, a
large receptive field is theoretically better. A simplest way to increase
receptive field is to increase kernel size of convolutional operation.
However, due to the limit of computing devices, increasing the receptive field
through enlarging the convolutional kernels is not applicable. Therefore,
pooling operation is a more feasible way to increase the receptive field.
Considering that this task is similar to pixel-wise image segmentation, we
adopt a structure similar to U-net [12]. Moreover, the inputs are cropped to
further decrease the difference between the size of the receptive field and
the study area (see section 3.3 for more details).

Use mask instead of spatial attention. To address the data sparsity, the
introduction of spatial attention might be possible, but it will lead to a
sharp increase in training time. Therefore, a mask is designed to improve
efficiency. We concatenate one more channel to the last layer before the
$1\times 1$ Conv, which checks whether the mean of input is equal to zero or
not.

###  3.2 Feature Engineering

Convert features into channels. Essentially, this task is a time-series
prediction problem. For one-dimensional time-series prediction, a typical
solution is to transform the problem into a supervised learning problem with
the help of feature engineering. Referring to this idea, the features are
input into the model as different channels. Limited by the computing devices
(i.e., $4\times 2080\text{Ti}$ GPUs), there are 101 input features (i.e., 101
channels). More features can usually bring higher accuracy.

Time smoothness features. Time series data are intrinsically continuous rather
than discrete. Hence, time series seldom produce sharp variations, which means
that the traffic state at a certain time interval has a close resemblance to
traffic state at the adjacent time interval. The feature crosses are also
considered. Therefore, in each prediction subtask, the data of all three
subtasks from the previous 12 time intervals are used. A total of $12\times 3$
channels are used from $[T-12,T-1]$ with the same day, where $T$ denotes the
predicted time index, and the number 3 indicates the data of three subtasks.

Periodic features. The similarity between the traffic states of two different
days can be attributed to the periodic characteristics of traffic states,
which typically repeat every 24 hours. We use in total $16\times 3$ channels
from $\\{D-14\\}\bigcup[D-7,D-1]\bigcup[D+1,D+7]\bigcup\\{D+14\\}$ with the
same time index, where $D$ is the predicted day. To remove random noises,
moving windows with the windows size of 13 are applied to smooth each time
index.

Statistical features. We use in total $5\times 3$ channels from 5 average
given period on the same day.

Time-dependent features. Two channels in total are used to represent month and
week average in the predicted time index and corresponding task.

###  3.3  Region Cropping

We further divide the study area into five sub-regions with size $299\times
299$ (see Figure 2). Region cropping allows our model to be trained on weak
computing devices. As mentioned above, it decreases the difference between the
size of the receptive field and the study area. In addition, the models can be
specially optimized for each sub-region, as the optimal parameters for the
whole city may not be the best parameters suited for each sub-region. We
spliced the prediction results of each sub-region into a complete region, and
the overlapping portions were replaced with average values. To sum up, in our
final solution, we trained in total $3^{\text{cities}}\times
3^{\text{subtasks}}\times 5^{\text{subregions}}=45$ models. Here, it should be
pointed out that our models can be fine-tuned and actually efficient in
training.

Figure 2:  Schematic diagram of region cropping

###  3.4 Training

We train all models in following procedure. First, for each city, we train a
model from scratch for direction prediction task of a $299\times 299$
subregion. Then using those parameters as pre-trained models, we fine-tune all
the rest models. The fine-tune step starts from a larger learning rate, more
data, and no data augmentation to lower learning rate, fewer data, and more
data augmentation. The training process is summarized in Algorithm 1 as below.

Algorithm 1 Training

1: for CITY in {Berlin, Istanbul, Moscow} do

2: Train a model from scratch for direction prediction task with
SUB_REGION$=0$.

3: for SUB_REGION in $[0,4]$ do

4: Use the pre-trained model above, fine-tune the models for the other tasks.

5: end for

6: for SUB_REGION in $[0,4]$ do

7: Fine-tune all the models with lower learning rate, fewer data, and data
augmentation.

8: end for

9: end for

10: return $\bm{x}$

##  4 Complementary Challenges

###  4.1 Alternative Metrics

Pixel-wise mean squared error (MSE) is used to evaluate the performance for
the ranking of submitted prediction results. The MSE is not the idea loss for
this data set due to the sparsity of data and the improper coding of the
heading channel. For Moscow, the MSE of the heading channel is approximate
$3.1\times 10^{-2}$ while speeding, and volume channel are $1\times 10^{-4}$
and $5\times 10^{-3}$ respectively. This magnitude difference also happened in
Berlin and Istanbul. It is clear that the heading channel dominates overall
scores comparing to the leader-board score difference in $10^{-4}$. In other
words, a model which predicts better heading channel will rank higher in the
leader board. If we direct train the model with MSE loss, though the
performance is the best regarding lead board ranking, the predicted values are
meaningless. Table 1 is an example: our best model tries to predict large
value more conservative (trend to out-put small values and made frame
unrealistic and blurry ) because of the punishment of square error. This
characteristic hinders this model to real-world applications when detailed
general directions $(NW,NE,SW,SE)$ are more critical. In real-world traffic
prediction systems, MSE is not also welcome because it cannot give a sense of
how accurate prediction is. Mean Absolute Error (MAE) and Mean Absolute
Percentage Error (MAPE) is more often used in traffic prediction tasks. Given
the above explanations, we consider to apply a multi-loss combine cross-
entropy and weight MAPE together, and define the new loss function
$\mathcal{L}$ as:

$\mathcal{L}=w_{\text{heading}}\cdot\text{CE}(\text{heading})+w_{\text{volume}}\cdot\text{MAPE}(\text{volume})+w_{\text{speeding}}\cdot\text{MAPE}(\text{speeding})$
(1)

Here $\text{CE}(\cdot)$ represents the 2D cross-entropy loss with 5 classes
$(0,NW,NE,SW,SE)$ while $\text{MAPE}(\cdot)$ is the 2D Mean Absolute
Percentage Error.

Table 1:  Average Predicted Values ($\bar{I}_{\text{predict}}$) verse its true value ($I_{\text{true}}$) for heading channel. We select (Moscow, 20181106, 258-260) as an example. $I_{\text{true}}$ | $\bar{I}_{\text{predict}}$
---|---
0 | 8.08
1 | 58.63
85 | 73.44
170 | 93.17
255 | 117.73

###  4.2 Multi-source Data Fusion and Online Learning

Multi-source data fusion is fashion and often be reported as useful in the
research fields, but we did not embed any external information to the models
for the final solution. We report that embedding external information e.g.,
weather, holiday, and the day of week might lead to over-fitting. We tried to
embed 20 external features into 64 dimension vector and add them to the output
of the first $3\times 3$ Conv of U-net, but the MSE error increased
significantly when other features remain unchanged.

Here we propose a method that could apply external information to our model.
For each predicted day, the model will be fine-tuned one more epoch using
similar data of the predicted day. The similarities between data are measured
by time, weather, and holiday features. If we just use the time to rank the
similarity, then this method downgrade to an online learning method - the
model tries to optimize recent inputs instead of global ones. By using this
method, we had a deduction of $10^{-4}$ to loss.

###  4.3 Spatio-Temporal Ensemble Method

The motivation of spatio-temporal ensemble method stems from the large-scale
spatio-temporal predictions performed in many online taxi-hailing service
providers, e.g., Uber, Didi, and Lyft. These predictions are usually completed
by different teams from different domains, with different models. However,
every single model may have some inherent defects due to insufficient
information, and hence it is rational to ensemble the results of these models
to improve the overall performance. It remains a challenging but essential
issue to make an effective combination of multiple base models while
leveraging the spatio-temporal information. To the best of our knowledge, the
research in this vein is very sparse.

The prediction outcome can help the online car-hailing platforms accurately
dispatch the fleet and lower the vehicle vacancy ratio, thus serving more
passengers with their trip requests. Notably, even if the average prediction
error reduction is small, compared with the optimal base model, the cumulative
number of orders for a long period, say, one year, will be considerable in
that the whole city can be seen as thousands of pixels, and DiDi and Uber run
their business in hundreds of cities. Therefore, we design an attention-based
deep ensemble net in dealing with the problems mentioned above [13].

###  4.4 Personalized Intelligent Transportation Prediction Systems

In our recent study, we managed to introduce the concept of personalization in
the recommendation system to the prediction problem in intelligent
transportation systems, and a more intelligent urban transportation system,
which conforms to the individual preferences and is appropriate for regional
traffic conditions, can thus be designed. Therefore, we explore
personalization in the application of intelligent transportation systems.
Aiming at the two common personalized demands in intelligent transportation
systems, we define the two types of personalization in intelligent
transportation systems on the basis of different application scenarios: User
Personalization and Geographic Personalization [14]. Interdisciplinary
knowledge and experience fusion is urgently needed classical traffic research.
In addition to the construction of personalized intelligent transportation
systems, there is also great potential for adversarial examples and transfer
learning.

## References

  * [1] Ke, J., Zheng, H., Yang, H. & Chen, X. M.  Short-term forecasting of passenger demand under on-demand ride services: A spatio-temporal deep learning approach.  _Transportation Research Part C: Emerging Technologies_ 85, 591–608 (2017).
  * [2] Yao, H. _et al._ Deep multi-view spatial-temporal network for taxi demand prediction.  In _Thirty-Second AAAI Conference on Artificial Intelligence_ (2018).
  * [3] Liu, Y., Liu, Z. & Jia, R.  Deeppf: A deep learning based architecture for metro passenger flow prediction.  _Transportation Research Part C: Emerging Technologies_ 101, 18–34 (2019).
  * [4] Fu, R., Zhang, Z. & Li, L.  Using lstm and gru neural network methods for traffic flow prediction.  In _2016 31st Youth Academic Annual Conference of Chinese Association of Automation (YAC)_ , 324–328 (IEEE, 2016).
  * [5] Zhang, J., Zheng, Y. & Qi, D.  Deep spatio-temporal residual networks for citywide crowd flows prediction.  In _Thirty-First AAAI Conference on Artificial Intelligence_ (2017).
  * [6] Geng, X. _et al._ Spatiotemporal multi-graph convolution network for ride-hailing demand forecasting.  In _2019 AAAI Conference on Artificial Intelligence (AAAI’19)_ (2019).
  * [7] Li, Y., Yu, R., Shahabi, C. & Liu, Y.  Diffusion convolutional recurrent neural network: Data-driven traffic forecasting.  In _International Conference on Learning Representations_ (2018).
  * [8] Pan, Z. _et al._ Urban traffic prediction from spatio-temporal data using deep meta learning.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD’19)_, 1720–1730 (ACM, New York, NY, USA, 2019).
  * [9] Yu, B., Yin, H. & Zhu, Z.  Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting.  In _Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI)_ (2018).
  * [10] Koesdwiady, A., Soua, R. & Karray, F.  Improving traffic flow prediction with weather information in connected cars: A deep learning approach.  _IEEE Transactions on Vehicular Technology_ 65, 9508–9517 (2016).
  * [11] Liao, B. _et al._ Deep sequence learning with auxiliary information for traffic prediction.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 537–546 (ACM, 2018).
  * [12] Ronneberger, O., Fischer, P. & Brox, T.  U-net: Convolutional networks for biomedical image segmentation.  In _International Conference on Medical image computing and computer-assisted intervention_ , 234–241 (Springer, 2015).
  * [13] Liu, Y., Liu, Z., Lyu, C. & Ye, J.  Attention-based deep ensemble net for large-scale online taxi-hailing demand prediction.  _IEEE Transactions on Intelligent Transportation Systems_ in press, DOI: 10.1109/TITS.2019.2947145 (2019).
  * [14] Liu, Y., Lyu, C. & Liu, Z.  Exploring personalization in the application of intelligent transportation systems.  In _1st ACM SIGSPATIAL International Workshop on Ride-hailing Algorithms, Applications, and Systems (RAAS’19)_ , in press, DOI: 10.1145/3357140.3365494 (ACM, Chicago, IL, USA, 2019).


# Sums of random multiplicative functions over function fields with few
irreducible factors

Daksh Aggarwal  Department of Mathematics
Grinnell College
1115 8th Ave # 3011
Grinnell, IA
USA
50112<EMAIL_ADDRESS>,  Unique Subedi  Department of Statistics
University of Michigan
1085 University Ave
323 West Hall
Ann Arbor, MI
USA
48109<EMAIL_ADDRESS>,  William Verreault  Département de Mathématiques et
de Statistique
Université Laval
Québec
QC
G1V 0A6
Canada<EMAIL_ADDRESS>,  Asif Zaman  Department of Mathematics
University of Toronto
40 St. George Street, Room 6290
Toronto, ON
Canada
M5S 2E4<EMAIL_ADDRESS>and  Chenghui Zheng  Department of Statistics
University of Toronto
100 St.George Street
Toronto, ON
Canada
M5S 3G3<EMAIL_ADDRESS>
###### Abstract.

We establish a normal approximation for the limiting distribution of partial
sums of random Rademacher multiplicative functions over function fields,
provided the number of irreducible factors of the polynomials is small enough.
This parallels work of Harper for random Rademacher multiplicative functions
over the integers.

##  1\. Introduction

Let $\mathcal{M}$ be the set of monic polynomials belonging to the polynomial
ring $\mathbb{F}_{q}[t]$ with coefficients in the finite field
$\mathbb{F}_{q}$ with $q$ elements, where $q\geq 2$ is a prime power. A random
Rademacher multiplicative function $f:\mathcal{M}\to\\{-1,0,1\\}$ over
$\mathbb{F}_{q}[t]$ is obtained by picking independent random variables $f(P)$
uniformly distributed on $\\{\pm 1\\}$ (that is, taking the value $\pm 1$ with
probability $1/2$ each) for monic irreducible polynomials $P$, extending $f$
multiplicatively to all squarefree monic polynomials, and setting $f$ to be
zero for all non-squarefree monic polynomials. For example, if $F=P_{1}\cdots
P_{k}$ for distinct irreducible monic polynomials $P_{1},\dots,P_{k}$, then
$f(F)=f(P_{1})\cdots f(P_{k})$. For any positive integers $k$ and $n$, set

$\mathcal{P}_{k}(n)=\\{F\in\mathcal{M}:F\text{ squarefree, }\omega(F)=k,\text{
and }\deg(F)=n\\},$

where $\omega(F)$ is the number of distinct irreducible factors of the
polynomial $F$, and $\deg(F)$ is the degree of $F$. The purpose of this
article is to establish the following theorem.

######  Theorem 1.

Let $f$ be a random Rademacher multiplicative function over
$\mathbb{F}_{q}[t]$, where $q\geq 2$ is a fixed prime power. If $k\geq 1$
satisfies $k=o(\log n)$ as $n\to\infty$, then

(1.1)
$\frac{1}{\sqrt{\left|\mathcal{P}_{k}(n)\right|}}\sum_{F\in\mathcal{P}_{k}(n)}f(F)$

converges in distribution to the standard normal distribution $N(0,1)$ as
$n\to\infty$.

This result is motivated by the study of random multiplicative functions over
the integers, which were introduced by Wintner [12] to heuristically model the
Möbius function. A random Rademacher multiplicative function
$f:\mathbb{N}\to\\{-1,0,1\\}$ over the integers is similarly obtained by
picking independent random variables $f(p)$ for each prime $p$, extending it
multiplicatively to all squarefree integers, and setting it to be zero for all
non-squarefree integers. If $\pi_{k}(x)$ is the number of squarefree integers
$\leq x$ with $k$ distinct prime factors, then the sum

(1.2) $\frac{1}{\sqrt{\pi_{k}(x)}}\sum_{\begin{subarray}{c}m\leq x\\\
\omega(m)=k\end{subarray}}f(m)$

parallels the quantity in (1.1). Indeed, integers of size $x$ are known to
correspond to polynomials in $\mathbb{F}_{q}[t]$ of degree $n\approx\log x$.
Improving upon a result of Hough [5], Harper [4] established the following
theorem which motivates our Theorem 1.

######  Theorem 2 (Harper).

Let $f$ be a random Rademacher multiplicative function over the integers. If
$k\geq 1$ satisfies $k=o(\log\log x)$ as $x\to\infty$, then (1.2) converges in
distribution to the standard normal $N(0,1)$ as $x\to\infty$.

Notice the range $k=o(\log\log x)$ in Theorem 2 over the integers corresponds
precisely to the range $k=o(\log n)$ in Theorem 1 over the polynomial ring
$\mathbb{F}_{q}[t]$. Theorem 1 can therefore be viewed as an extension of
Theorem 2 to the function field setting. For an introduction to multiplicative
functions over function fields, we refer the reader to work of Granville,
Harper, and Soundararajan [3], whose conventions we follow here.

The proof strategy for Theorem 1 adapts Harper’s key ideas with the
verification of three conditions in a martingale central limit theorem
(Theorem 3). In Section 2, we prepare this strategy and define our martingale
difference sequence. The analysis of this martingale allows us to efficiently
reduce the theorem to a natural counting problem (Lemma 4), just as Harper did
in Section 4.2 of [4]. However, this counting problem for function fields
introduces cases which did not appear for the integers. The source of these
new cases is simple: two distinct irreducible polynomials can have the same
degree, but two distinct rational primes cannot have the same size. Since our
martingale is filtered based on the degree of the largest irreducible factor
(similar to the size of the prime for integers), this distinction creates new
terms in our sums that we must carefully treat; see the remark following Lemma
4 for details.

In Section 3, we proceed to analyze these sums and complete the proof of
Theorem 1 with some technical estimates. Although these combinatorial sums are
somewhat more intricate, the estimation of these sums is simpler due to the
familiar analytic benefits of function fields over integers. The key technical
lemma for this analysis (Lemma 5) is proved in Section 4. We use recent
results on the size of $\mathcal{P}_{k}(n)$ by Gómez-Colunga et al. [2] and
Afshar and Porritt [1], which respectively parallel classical estimates for
$\pi_{k}(x)$ by Hardy and Ramanujan, and Sathe and Selberg.

We conclude the introduction with a few remarks on the sharpness of Theorem 1
and possible extensions. Harper showed that the range $k=o(\log\log x)$ in
Theorem 2 is optimal [4, Corollary 1]. He further established a normal
approximation for sums like (1.2) with the looser restriction $\omega(m)\leq
k$ and also for a larger class of random multiplicative functions [4, Theorem
3]. It would be of interest to determine whether the range $k=o(\log n)$ in
Theorem 1 is optimal and whether similar extensions hold in our setting. It
seems plausible that such results carry over by similar arguments, but we did
not pursue those investigations. If the range $k=o(\log n)$ is optimal as
Harper’s work would suggest, then this indicates that the proof of Theorem 1
is quite delicate and sensitive to even minor losses.

### Acknowledgments

This research was conducted as part of the 2020 Fields Undergraduate Summer
Research Program. The authors are grateful to the Fields Institute for their
financial support and facilitating our online collaboration.

## Notation

Let $q\geq 2$ be a prime power. Let $\mathbb{F}_{q}[t]$ be the polynomial ring
with coefficients in the finite field $\mathbb{F}_{q}$ with $q$ elements. Let
$\mathcal{M}$ be the set of monic polynomials belonging to
$\mathbb{F}_{q}[t]$. We shall use capital letters to denote a polynomial $F$
in $\mathcal{M}$, writing $\deg(F)$ for the degree of the polynomial $F$,
$\omega(F)$ for the number of distinct irreducible factors of $F$, and
$\mathrm{P}^{+}(F)$ for the maximum degree of an irreducible dividing $F$. The
letters $P$ and $Q$ will be reserved for monic irreducible polynomials. For
integers $k,n\geq 1$, let $\mathcal{P}_{k}(n)$ be the set of squarefree
polynomials $F$ in $\mathcal{M}$ with $\omega(F)=k$ and $\deg(F)=n$. The
letter $f$ denotes a random Rademacher multiplicative function over
$\mathbb{F}_{q}[t]$. The relation $u\ll v$ means that there exists an absolute
positive constant $C$ such that $|u|\leq Cv$. If the constant $C$ depends on a
parameter, say $\varepsilon$, then we shall write $u\ll_{\varepsilon}v$.

##  2\. Plan for the proof of Theorem 1

For integers $k,n\geq 1$ and a random Rademacher multiplicative function $f$
over $\mathbb{F}_{q}[t]$, define

$S^{(k)}(n)=\sum_{F\in\mathcal{P}_{k}(n)}f(F).$

Notice $\mathbb{E}[f(F)]=0$ for any non-trivial squarefree $F$ because $f$ is
multiplicative and $(f(P))_{P}$ is a sequence of independent random variables
with mean zero. Hence, $S^{(k)}(n)$ has mean zero. Also, since
$\mathbb{E}[f(F)f(G)]=1$ if $F=G$ and $0$ otherwise, it follows that

(2.1)
$\mathbb{E}\big{[}S^{(k)}(n)^{2}\big{]}=\mathop{\sum\sum}_{F,G\in\mathcal{P}_{k}(n)}\mathbb{E}[f(F)f(G)]=|\mathcal{P}_{k}(n)|.$

Thus the mean of (1.1) is zero and its variance is indeed one. Our goal is to
prove that $S^{(k)}(n)$, normalized by its standard deviation
$\sqrt{|\mathcal{P}_{k}(n)|}$, converges in distribution to the standard
normal as $n\to\infty$, provided $k=o(\log n)$. The strategy follows that of
Harper [4] with appropriate modifications and simplifications as mentioned
earlier in the introduction.

First, notice $\mathcal{P}_{1}(n)$ is the set of irreducible monic polynomials
of degree $n$, so $S^{(1)}(n)$ is a sum of $|\mathcal{P}_{1}(n)|$ independent
random variables uniform on $\\{\pm 1\\}$. Thus, the classical central limit
theorem implies that $S^{(1)}(n)$ converges in distribution to $N(0,1)$ as
$n\to\infty$. We may therefore assume throughout that $k\geq 2$.

###  2.1. Central limit theorem for martingale difference sequences

To prove convergence in distribution to standard normal, we want to use a
central limit theorem that gives information on the convergence of the partial
sums of a martingale difference sequence. The result we use was obtained by
McLeish [6], but we state it as it appeared in [4].

######  Theorem 3 (McLeish).

For $n\in\mathbb{N}$, suppose that $k_{n}\in\mathbb{N}$, and that $X_{i,n}$,
$1\leq i\leq k_{n}$, is a martingale difference sequence on
$(\Omega,\mathscr{F},(\mathscr{F}_{i,n})_{i},\mathbb{P})$. Write
$S_{n}:=\sum_{i\leq k_{n}}X_{i,n}$ and suppose that the following conditions
hold:

  1. (i)

$\displaystyle\sum_{i\leq k_{n}}\mathbb{E}[X_{i,n}^{2}]\to 1$ as $n\to\infty;$

  2. (ii)

for each $\varepsilon>0$, we have $\displaystyle\sum_{i\leq
k_{n}}\mathbb{E}\left[X_{i,n}^{2}\mathbf{1}_{|X_{i,n}|>\varepsilon}\right]\to
0$ as $n\to\infty$;

  3. (iii)

$\displaystyle\limsup_{\begin{subarray}{c}n\to\infty\end{subarray}}\sum_{i\leq
k_{n}}\sum_{j\leq k_{n},j\neq
i}\mathbb{E}\left[X_{i,n}^{2}X_{j,n}^{2}\right]\leq 1.$

Then, $S_{n}$ converges in distribution to $N(0,1)$ as $n\to\infty$.

Let us describe the martingale difference sequence in our problem. Let $n\geq
k\geq 2$. Write $\mathrm{P}^{+}(F)$ for the maximum degree of the irreducible
factors of $F$. For $d\geq 1$, define

$\mathcal{P}_{k,d}(n):=\\{F\in\mathcal{P}_{k}(n):\mathrm{P}^{+}(F)=d\\},$

and set

$S_{d}^{(k)}(n):=\sum_{F\in\mathcal{P}_{k,d}(n)}f(F).$

Notice the set $\mathcal{P}_{k,n}(n)$ is empty as $k\geq 2$, so
$\mathcal{P}_{k}(n)$ is the union of $\mathcal{P}_{k,d}(n)$ over $1\leq d\leq
n-1$ and therefore $S^{(k)}(n)=\sum_{d=1}^{n-1}S^{(k)}_{d}(n)$.

Writing $F\in\mathcal{P}_{k,d}(n)$ as $F=QF^{\prime}$, where $Q$ is a degree
$d$ factor of $F$ (among possibly many), it follows by multiplicativity and
independence that
$\mathbb{E}[f(F)]=\mathbb{E}[f(Q)]\mathbb{E}[f(F^{\prime})].$ Since
$\mathbb{E}[f(Q)\mid\\{f(P):\deg P<d\\}]=\mathbb{E}[f(Q)]=0$, we get that

$\mathbb{E}\left[f(F)\mid\\{f(P):\deg P<d\\}\right]=0,$

and so by the linearity of expectation, it follows that

$\mathbb{E}\left[S_{d}^{(k)}(n)|\\{f(P):\deg P<d\\}\right]=0.$

Hence, if $\mathscr{F}_{d}$ denotes the sigma algebra generated by
$\\{f(P):\deg P<d\\}$, then $(S_{d}^{(k)}(n))_{d\leq n-1}$ is a martingale
difference sequence with respect to $(\mathscr{F}_{d})_{d\leq n-1}$.

We will therefore apply Theorem 3 to the random variables
$S_{d}^{(k)}(n)/\sqrt{\left|\mathcal{P}_{k}(n)\right|}$, which still form a
martingale difference sequence and whose sum over $d\leq n-1$ equals
$S^{(k)}(n)/\sqrt{\left|\mathcal{P}_{k}(n)\right|}$, the quantity considered
in Theorem 1. For convenience, we also use the notation

$\mathcal{P}_{k,\leq d}(n):=\bigcup_{j\leq d}\mathcal{P}_{k,j}(n).$

###  2.2. Reduction to some counting problems

By a computation similar to (2.1), it follows that
$\mathbb{E}[S_{d}^{(k)}(n)^{2}]=\left|\mathcal{P}_{k,d}(n)\right|$, so that
condition (i) of Theorem 3 holds for all $n$, not just in the limit. Proving
Theorem 1 then boils down to verifying conditions (ii) and (iii) of Theorem 3.
The second condition stated in terms of our normalised random variables asks
that for all $\varepsilon>0$,

$\sum_{d=1}^{n-1}\mathbb{E}\left[\left(S_{d}^{(k)}(n)/\sqrt{\left|\mathcal{P}_{k}(n)\right|}\right)^{2}\mathbbm{1}_{\left|S_{d}^{(k)}(n)\right|/\sqrt{|\mathcal{P}_{k}(n)|}>\varepsilon}\right]\to
0$

as $n\to\infty.$ This quantity is at most

$\varepsilon^{-2}\sum_{d=1}^{n-1}\mathbb{E}\left[S_{d}^{(k)}(n)^{4}/\left|\mathcal{P}_{k}(n)\right|^{2}\right].$

Thus, it suffices to prove that

(2.2)
$\sum_{d=1}^{n-1}\mathbb{E}[S_{d}^{(k)}(n)^{4}]=o(\left|\mathcal{P}_{k}(n)\right|^{2})$

as $n\to\infty$. The third condition becomes

$\limsup_{n\to\infty}\sum_{d=1}^{n-1}\sum_{\begin{subarray}{c}e=1\\\ e\neq
d\end{subarray}}^{n-1}\mathbb{E}\left[\frac{S_{d}^{(k)}(n)^{2}S_{e}^{(k)}(n)^{2}}{\left|\mathcal{P}_{k}(n)\right|^{2}}\right]\leq
1.$

Equivalently, we will show

(2.3) $\sum_{d=1}^{n-1}\sum_{\begin{subarray}{c}e=1\\\ e\neq
d\end{subarray}}^{n-1}\mathbb{E}\left[S_{d}^{(k)}(n)^{2}S_{e}^{(k)}(n)^{2}\right]\leq(1+o(1))\left|\mathcal{P}_{k}(n)\right|^{2}$

as $n\to\infty$. For any $1\leq d,e\leq n-1$, it will therefore be convenient
to express $\mathbb{E}\left[S_{d}^{(k)}(n)^{2}S_{e}^{(k)}(n)^{2}\right]$ in
terms of an explicit counting problem.

######  Lemma 4.

With the same notation as above,

$\mathbb{E}\left[S_{d}^{(k)}(n)^{2}S_{e}^{(k)}(n)^{2}\right]\leq|\mathcal{P}_{k,d}(n)||\mathcal{P}_{k,e}(n)|+I_{k,d,e}(n)+J_{k,d,e}(n),$

where

(2.4)
$I_{k,d,e}(n)=\sum_{t=1}^{k-1}\sum_{\ell=1}^{n-1}\sum_{M\in\mathcal{P}_{2t,\leq\min\\{d,e\\}}(2\ell)}\sum_{\begin{subarray}{c}A\in\mathcal{P}_{t,\leq
d}(\ell)\\\ A\mid
M\end{subarray}}\sum_{\begin{subarray}{c}U\in\mathcal{P}_{k-t,\leq
d}(n-\ell)\\\
\mathrm{P}^{+}(UA)=d\end{subarray}}\sum_{\begin{subarray}{c}B\in\mathcal{P}_{t,\leq
e}(\ell)\\\ B\mid
M\end{subarray}}\sum_{\begin{subarray}{c}V\in\mathcal{P}_{k-t,\leq
e}(n-\ell)\\\ \mathrm{P}^{+}(VB)=e\end{subarray}}1,$

and $J_{k,d,e}(n)=0$ if $d\neq e$, otherwise

(2.5)
$J_{k,d,d}(n)=\mathop{\sum\sum}_{P,Q\in\mathcal{P}_{1}(d)}\sum_{M^{\prime}\in\mathcal{P}_{2k-2}(2n-2d)}\mathop{\sum\sum}_{\begin{subarray}{c}A^{\prime},B^{\prime}\in\mathcal{P}_{k-1}(n-d)\\\
A^{\prime}\mid\,M^{\prime},\>B^{\prime}\mid M^{\prime}\end{subarray}}1.$

###### Proof.

Expanding out the sums and applying linearity of expectation, we get that

(2.6)
$\mathbb{E}\left[S_{d}^{(k)}(n)^{2}S_{e}^{(k)}(n)^{2}\right]=\mathop{\sum\sum}_{W,X\in\mathcal{P}_{k,d}(n)}\mathop{\sum\sum}_{Y,Z\in\mathcal{P}_{k,e}(n)}\mathbb{E}\left[f(W)f(X)f(Y)f(Z)\right].$

Notice the expectation on the righthand side is nonzero only when $WXYZ$ is a
square, in which case it equals $1$. This is the counting problem, which we
proceed to reformulate. We may write $WX$ as the product of a square part
$U^{2}$ and a square-free part $M$ so $W=UA$ and $X=U(M/A)$ for some $A$ that
divides $M$. Note that $U,A,$ and $M/A$ are all relatively prime and the
maximum degree of their irreducible factors is $\leq d$. A similar reasoning
for $YZ$ gives some other square part, say $V^{2}$, and forces their
squarefree part to be $M$ as well so $Y=VB$ and $Z=V(M/B)$ for some $B$ that
divides $M$. Again, $V,B,$ and $M/B$ are all relatively prime and the maximum
degree of their irreducible factors is $\leq e$.

With this notation in mind, we proceed to count the corresponding
contributions according to cases. First, if $M=1$ then $A=B=1$, so this case
contributes at most

$\sum_{U\in\mathcal{P}_{k,d}(n)}\sum_{V\in\mathcal{P}_{k,e}(n)}1=|\mathcal{P}_{k,d}(n)||\mathcal{P}_{k,e}(n)|.$

Next, we count the terms in (2.6) where $M\neq 1$ so $\deg M$ and $\omega(M)$
are both non-zero. As $M$ is non-trivial, we have that $A\in P_{t,\leq
d}(\ell)$ for some $t\in\\{1,\dots,k\\}$ and $\ell\in\\{1,\dots,n\\}$.
Comparing the degrees and number of irreducible factors of $W=UA$ and
$X=U(M/A)$, we deduce that $\mathrm{P}^{+}(UA)=d$ and

$\deg U+\deg A=n,\qquad\deg M=2\deg
A,\qquad\omega(U)+\omega(A)=k,\qquad\omega(M)=2\omega(A).$

As $A\in\mathcal{P}_{t,\leq d}(\ell)$, this implies that
$U\in\mathcal{P}_{k-t,\leq d}(n-\ell)$ and $M\in\mathcal{P}_{2t,\leq
d}(2\ell)$. A similar analysis holds when comparing $Y=VB$ and $Z=V(M/B)$ but,
since the polynomial $M$ is common to both arguments, it follows that $A$ and
$B$ necessarily have the same degree and same number of prime factors and so
do $U$ and $V$. Hence, $B\in\mathcal{P}_{t,\leq
e}(\ell),V\in\mathcal{P}_{k-t,\leq e}(n-\ell)$, and
$M\in\mathcal{P}_{2t,\leq\min\\{d,e\\}}(2\ell)$. The terms in (2.6) with
$M\neq 1,t\in\\{1,\dots,k-1\\}$, and $\ell\in\\{1,\dots,n-1\\}$ therefore
contribute at most $I_{k,d,e}(n)$.

Continuing with this notation, the last case to consider is when $M\neq 1$ and
$t=k$ (or equivalently $\ell=n$) in which case $U=V=1$. Notice $U=V=1$ implies
that $WXYZ=U^{2}V^{2}M^{2}=M^{2}$ has a prime factor of degree $\max\\{d,e\\}$
yet $\mathrm{P}^{+}(M)\leq\min\\{d,e\\}$. If $d\neq e$, this leads to a
contradiction, so this last case occurs if and only if $d=e$. Thus, $M$ has at
least two distinct degree $d$ factors in this case and
$\mathrm{P}^{+}(A)=\mathrm{P}^{+}(B)=d$ where $A$ and $B$ divide $M$. Thus,
there exists a pair of distinct irreducibles $P,Q\in\mathcal{P}_{1}(d)$ such
that $M=PQM^{\prime}$, where $M^{\prime}$ belongs to
$\mathcal{P}_{2k-2}(2n-2d)$ and at least one of the following holds:

$P\mid A\text{ and }Q\mid B,\qquad Q\mid A\text{ and }P\mid B,\qquad P\mid
A\text{ and }P\mid B,\qquad Q\mid A\text{ and }Q\mid B.$

If, say, the first situation holds then $A=PA^{\prime}$ and $B=QB^{\prime}$
for $A^{\prime},B^{\prime}\in\mathcal{P}_{k-1}(n-d)$ dividing $M^{\prime}$. A
similar statement holds for the other cases. Combining all of these
observations, we see that the terms in (2.6) with $M\neq 1$ and $t=k$
contribute at most $J_{k,d,e}(n)$, as required. ∎

######  Remark.

This lemma and its proof possess the key differences between the function
field setting and the integers. Crucially, the product $WXYZ$ can form a
square in a new way and contribute to (2.6). Namely, if $d\leq e$ then $W$ and
$X$ do not need to share the same irreducible factor of degree $d$; these
factors of degree $d$ can instead pair with factors from $Y$ and $Z$. This
manifests in (2.4) by allowing $M$ to have these large irreducible factors of
degree $d=\min\\{d,e\\}$ and also by creating the additional terms (2.5) which
do not appear in Section 4.2 of [4].

If the irreducible factors of degree $d$ from $W$ and $X$ (resp. of degree $e$
from $Y$ and $Z$) are paired in a one-to-one manner, then only $U$ (resp. $V$)
in (2.4) would have these large factors of degree $d$ (resp. degree $e$) and
moreover (2.5) would not exist. This is precisely what happens for Harper in
the integer setting. Namely, if integers $w$ and $x$ have largest prime factor
$p$, then $p^{2}$ always divides $wx$ since the size of the prime corresponds
uniquely to the prime itself.

Now, using Lemma 4 with $d=e$, we see that (2.2) becomes the requirement that

$\sum_{d=1}^{n-1}\big{(}|\mathcal{P}_{k,d}(n)|^{2}+I_{k,d,d}(n)+J_{k,d,d}(n)\big{)}=o\left(|\mathcal{P}_{k}(n)|^{2}\right).$

Similarly, (2.3) holds provided that

$\sum_{d=1}^{n-1}\sum_{e=1}^{n-1}\Big{(}|\mathcal{P}_{k,d}(n)||\mathcal{P}_{k,e}(n)|+I_{k,d,e}(n)\Big{)}\leq(1+o(1))|\mathcal{P}_{k}(n)|^{2}.$

Since

$\sum_{d=1}^{n-1}\sum_{e=1}^{n-1}|\mathcal{P}_{k,d}(n)||\mathcal{P}_{k,e}(n)|=|\mathcal{P}_{k}(n)|^{2},$

both (2.2) and (2.3) will therefore be satisfied provided

(2.7)
$\sum_{d=1}^{n-1}|\mathcal{P}_{k,d}(n)|^{2}+\sum_{d=1}^{n-1}\sum_{e=1}^{n-1}I_{k,d,e}(n)+\sum_{d=1}^{n-1}J_{k,d,d}(n)=o(|\mathcal{P}_{k}(n)|^{2})$

as $n\to\infty$. This establishes Theorem 1 assuming (2.7) holds.

##  3\. Completing the proof of Theorem 1

It remains to prove (2.7), which rests on the following key technical lemma
whose proof is postponed to Section 4.

######  Lemma 5.

Fix an integer $r\geq 1$. If $k$ and $n$ are integers such that $r\leq
k\leq\frac{1}{3}\log n$, then

(3.1)
$\mathop{\mathop{\sum\sum}\cdots\mathop{\sum\sum}}_{\begin{subarray}{c}k_{1},n_{1},\dots,k_{r},n_{r}\geq
1\\\ k_{1}+\cdots+k_{r}=k\\\
n_{1}+\cdots+n_{r}=n\end{subarray}}|\mathcal{P}_{k_{1}}(n_{1})|^{2}\cdots|\mathcal{P}_{k_{r}}(n_{r})|^{2}\ll_{r}\frac{q^{2n}(\log
n+2-\log 2)^{2k-2r}}{n^{2}(k-r)!^{2}}.$

In particular, if $r\geq 2$ is fixed and $k=o(\log n)$ as $n\to\infty$, then
the above is $o(|\mathcal{P}_{k}(n)|^{2})$.

Assuming Lemma 5, it suffices to show that each of the three sums in (2.7) are
$o(|\mathcal{P}_{k}(n)|^{2})$ provided $k=o(\log n)$ as $n\to\infty$. We deal
with each estimate in separate subsections.

###  3.1. Estimate for $\sum_{d=1}^{n-1}\left|\mathcal{P}_{k,d}(n)\right|^{2}$

For $F\in\mathcal{P}_{k,d}(n)$, one has $F=PF^{\prime}$ for some
$P\in\mathcal{P}_{1}(d)$ and $F^{\prime}\in\mathcal{P}_{k-1}(n-d)$. This
implies that
$|\mathcal{P}_{k,d}(n)|\leq|\mathcal{P}_{1}(d)||\mathcal{P}_{k-1}(n-d)|$ and
so

$\sum_{d=1}^{n-1}\left|\mathcal{P}_{k,d}(n)\right|^{2}\leq\sum_{d=1}^{n-1}|\mathcal{P}_{1}(d)|^{2}\left|\mathcal{P}_{k-1}(n-d)\right|^{2}.$

This is a subsum of Lemma 5 with $r=2$ so it is $o(|\mathcal{P}_{k}(n)|^{2})$
as $n\to\infty$, as required.

###  3.2. Estimate for $\sum_{d=1}^{n-1}\sum_{e=1}^{n-1}I_{k,d,e}(n)$

Consider the definition of $I_{k,d,e}(n)$ in (2.4). The condition
$\mathrm{P}^{+}(UA)=d$ implies that at least one of the following holds:
$\mathrm{P}^{+}(U)=d$ or $\mathrm{P}^{+}(A)=d$. Summing over $d$ and, in some
cases, dropping the requirement that the maximum degree of the irreducible
factors of our polynomials is $\leq d$ or $\leq e$, this implies that
$\sum_{d=1}^{n-1}I_{k,d,e}(n)$ is at most

$\displaystyle\sum_{t=1}^{k-1}\sum_{\ell=1}^{n-1}\sum_{M\in\mathcal{P}_{2t}(2\ell)}\sum_{d=1}^{n-1}\Big{(}\sum_{\begin{subarray}{c}A\in\mathcal{P}_{t,d}(\ell)\\\
A\mid
M\end{subarray}}\sum_{\begin{subarray}{c}U\in\mathcal{P}_{k-t}(n-\ell)\end{subarray}}+\sum_{\begin{subarray}{c}A\in\mathcal{P}_{t}(\ell)\\\
A\mid
M\end{subarray}}\sum_{\begin{subarray}{c}U\in\mathcal{P}_{k-t,d}(n-\ell)\end{subarray}}\Big{)}\sum_{\begin{subarray}{c}B\in\mathcal{P}_{t,\leq
e}(\ell)\\\ B\mid
M\end{subarray}}\sum_{\begin{subarray}{c}V\in\mathcal{P}_{k-t,\leq
e}(n-\ell)\\\ \mathrm{P}^{+}(VB)=e\end{subarray}}1$
$\displaystyle=2\sum_{t=1}^{k-1}\sum_{\ell=1}^{n-1}\sum_{M\in\mathcal{P}_{2t}(2\ell)}\sum_{\begin{subarray}{c}A\in\mathcal{P}_{t}(\ell)\\\
A\mid
M\end{subarray}}\sum_{\begin{subarray}{c}U\in\mathcal{P}_{k-t}(n-\ell)\end{subarray}}\sum_{\begin{subarray}{c}B\in\mathcal{P}_{t,\leq
e}(\ell)\\\ B\mid
M\end{subarray}}\sum_{\begin{subarray}{c}V\in\mathcal{P}_{k-t,\leq
e}(n-\ell)\\\ \mathrm{P}^{+}(VB)=e\end{subarray}}1.$

Applying the same argument to the condition $\mathrm{P}^{+}(VB)=e$ and summing
over $e$, it follows that $\sum_{d=1}^{n-1}\sum_{e=1}^{n-1}I_{k,d,e}(n)$ is at
most

(3.2) $\displaystyle
4\sum_{t=1}^{k-1}\sum_{\ell=1}^{n-1}\Big{(}\sum_{M\in\mathcal{P}_{2t}(2\ell)}\sum_{\begin{subarray}{c}A\in\mathcal{P}_{t}(\ell)\\\
A\mid M\end{subarray}}\sum_{\begin{subarray}{c}B\in\mathcal{P}_{t}(\ell)\\\
B\mid
M\end{subarray}}1\Big{)}\Big{(}\sum_{\begin{subarray}{c}U\in\mathcal{P}_{k-t}(n-\ell)\end{subarray}}\sum_{\begin{subarray}{c}V\in\mathcal{P}_{k-t}(n-\ell)\end{subarray}}1\Big{)}.$

Fix $t\in\\{1,\dots,k-1\\}$ and $\ell\in\\{1,\dots,n-1\\}$. Notice that the
double sum with $U$ and $V$ is equal to $|\mathcal{P}_{k-t}(n-\ell)|^{2}$.
Next, consider the triple sum with $M,A,$ and $B$. Writing $G=\gcd(A,B)$, we
have that $A=GA^{\prime},B=GB^{\prime}$, and
$M=GA^{\prime}B^{\prime}M^{\prime}$ for some $M^{\prime}$ coprime to
$A^{\prime},B^{\prime},$ and $G$. Since $A$ and $B$ have the same degree and
same number of prime factors (and hence so do $A^{\prime}$ and $B^{\prime}$),
it follows that $G$ and $M^{\prime}$ must have the same degree and same number
of prime factors. Namely, if $G\in\mathcal{P}_{j}(g)$ for some integer $0\leq
j\leq t$ and some integer $0\leq g\leq\ell$, then
$M^{\prime}\in\mathcal{P}_{j}(g)$ and
$A^{\prime},B^{\prime}\in\mathcal{P}_{t-j}(\ell-g)$. Note the case $j=0$ (and
hence $g=0$) occurs when $G=M^{\prime}=1$ so $M=AB$, and the case $j=t$ (and
hence $g=\ell$) occurs when $A^{\prime}=B^{\prime}=1$ so $M=GM^{\prime}$.
Combining these observations implies that

(3.3)
$\displaystyle\sum_{M\in\mathcal{P}_{2t}(2\ell)}\sum_{\begin{subarray}{c}A\in\mathcal{P}_{t}(\ell)\\\
A\mid M\end{subarray}}\sum_{\begin{subarray}{c}B\in\mathcal{P}_{t}(\ell)\\\
B\mid M\end{subarray}}1$ $\displaystyle\leq
2|\mathcal{P}_{t}(\ell)|^{2}+\sum_{j=1}^{t-1}\sum_{g=1}^{\ell-1}\mathop{\sum\sum}_{G,M^{\prime}\in\mathcal{P}_{j}(g)}\mathop{\sum\sum}_{A^{\prime},B^{\prime}\in\mathcal{P}_{t-j}(\ell-g)}1$
$\displaystyle=2|\mathcal{P}_{t}(\ell)|^{2}+\sum_{j=1}^{t-1}\sum_{g=1}^{\ell-1}|\mathcal{P}_{j}(g)|^{2}|\mathcal{P}_{t-j}(\ell-g)|^{2}.$

Inserting these estimates in (3.2), we conclude that
$\sum_{d=1}^{n-1}\sum_{e=1}^{n-1}I_{k,d,e}(n)$ is at most

$\displaystyle
8\sum_{t=1}^{k-1}\sum_{\ell=1}^{n-1}|\mathcal{P}_{t}(\ell)|^{2}|\mathcal{P}_{k-t}(n-\ell)|^{2}+4\sum_{t=1}^{k-1}\sum_{\ell=1}^{n-1}\sum_{j=1}^{t-1}\sum_{g=1}^{\ell-1}|\mathcal{P}_{k-t}(n-\ell)|^{2}|\mathcal{P}_{j}(g)|^{2}|\mathcal{P}_{t-j}(\ell-g)|^{2}.$

Since $k=o(\log n)$ as $n\to\infty$, both of these sums are
$o(|\mathcal{P}_{k}(n)|^{2})$ by Lemma 5, as required.

###  3.3. Estimate for $\sum_{d=1}^{n-1}J_{k,d,d}(n)$

From (2.5), we have that

$\sum_{d=1}^{n-1}J_{k,d,d}(n)=\sum_{d=1}^{n-1}|\mathcal{P}_{1}(d)|^{2}\sum_{M^{\prime}\in\mathcal{P}_{2k-2}(2n-2d)}\mathop{\sum\sum}_{\begin{subarray}{c}A^{\prime},B^{\prime}\in\mathcal{P}_{k-1}(n-d)\\\
A^{\prime}\mid\,M^{\prime},\>B^{\prime}\mid M^{\prime}\end{subarray}}1.$

Notice the inner triple sum is the same as (3.3) with $\ell=n-d$ and $t=k-1$.
Thus, $\sum_{d=1}^{n-1}J_{k,d,d}(n)$ is at most

$2\sum_{d=1}^{n-1}|\mathcal{P}_{1}(d)|^{2}|\mathcal{P}_{k-1}(n-d)|^{2}+\sum_{d=1}^{n-1}\sum_{j=1}^{k-2}\sum_{g=1}^{n-d-1}|\mathcal{P}_{1}(d)|^{2}|\mathcal{P}_{j}(g)|^{2}|\mathcal{P}_{k-j-1}(n-d-g)|^{2}.$

Since $k=o(\log n)$ as $n\to\infty$, all of these sums are
$o(|\mathcal{P}_{k}(n)|^{2})$ by Lemma 5. This completes the proof of (2.7)
and the proof of Theorem 1. ∎

##  4\. Proof of Lemma 5

All that remains is to prove Lemma 5. To do so, we shall first require an
estimate for the size of $\mathcal{P}_{k}(n)$ that is uniform for all integers
$k$ and $n$. Gómez-Colunga et al. [2] have recently established such a result.

######  Proposition 6 (Gómez-Colunga–Kavaler–McNew–Zhu).

Uniformly for all $k,n\geq 1$,

$|\mathcal{P}_{k}(n)|\leq\frac{q^{n}}{n}\frac{(\log n+2-\log
2)^{k-1}}{(k-1)!}.$

This corresponds to a classical result of Hardy and Ramanujan [7] for the
integers: there exists a constant $B>0$ such that, for all $k\geq 1$ and
$x\geq 2$, we have

$\pi_{k}(x)\ll\frac{x}{\log x}\frac{(\log\log x+B)^{k-1}}{(k-1)!},$

where $\pi_{k}(x)$ is the number of squarefree integers up to $x$ with $k$
prime factors.

Sathe [8, 9] and Selberg [10] famously derived an asymptotic estimate for
$\pi_{k}(x)$ when $k=o(\log\log x)$. We shall also need an asymptotic estimate
for $|\mathcal{P}_{k}(n)|$ that is valid when $k=o(\log n)$. Although the
estimate $|\mathcal{P}_{k}(n)|\sim\frac{q^{n}(\log n)^{k-1}}{n(k-1)!}$ (see,
e.g., [11]) suffices for our purposes, we state here the strongest and most
recent result on an estimate for $|\mathcal{P}_{k}(n)|$, which is a so-called
Sathe–Selberg formula for function fields established by Afshar and Porritt
[1].

######  Proposition 7 (Afshar–Porritt).

Let $A>1$. Uniformly for all $n\geq 2$ and $1\leq k\leq A\log n$,

$|\mathcal{P}_{k}(n)|=\frac{q^{n}(\log
n)^{k-1}}{n(k-1)!}\left(G\left(\frac{k-1}{\log
n}\right)+O_{A}\left(\frac{k}{(\log n)^{2}}\right)\right),$

where

$G(z)=\frac{1}{\Gamma(1+z)}\prod_{\begin{subarray}{c}P\in\mathcal{M}\\\
P\text{ irreducible}\end{subarray}}\left(1+\frac{z}{q^{\deg
P}}\right)\left(1-\frac{1}{q^{\deg P}}\right)^{z},$

and $\Gamma(\cdot)$ is the Gamma function defined as
$\Gamma(z)=\int_{0}^{\infty}x^{z-1}e^{-x}dx.$

Propositions 6 and 7 imply our key technical lemma.

###### Proof of Lemma 5.

The second estimate follows from (3.1) since

$\frac{q^{2n}(\log n+2-\log 2)^{2k-2r}}{n^{2}(k-r)!^{2}}\leq\frac{q^{2n}(\log
n)^{2k-2}}{n^{2}(k-1)!^{2}}\cdot\frac{k^{2r-2}}{(\log
n)^{2r-2}}\Big{(}1+\frac{2-\log 2}{\log n}\Big{)}^{2k-2r},$

and Proposition 7 implies that if $k=o(\log n)$ as $n\to\infty$, then
$|\mathcal{P}_{k}(n)|\sim\frac{q^{n}(\log n)^{k-1}}{n(k-1)!}$.

To prove (3.1), we proceed by induction on $r$. For $r=1$, the claim follows
immediately from Proposition 6. For $r\geq 2$, if $n_{1}+\cdots+n_{r}=n$, then
at least one of $n_{1},\dots,n_{r}$ is at most $\lfloor n/r\rfloor$. By
symmetry, we may assume it is $n_{r}$ so the left side of (3.1) is at most

$\ll_{r}\sum_{k_{r}=1}^{k-r+1}\sum_{n_{r}=1}^{\lfloor
n/r\rfloor}|\mathcal{P}_{k_{r}}(n_{r})|^{2}\Big{(}\mathop{\mathop{\sum\sum}\cdots\mathop{\sum\sum}}_{\begin{subarray}{c}k_{1},n_{1},\dots,k_{r-1},n_{r-1}\geq
1\\\ k_{1}+\cdots+k_{r-1}=k-k_{r}\\\
n_{1}+\cdots+n_{r-1}=n-n_{r}\end{subarray}}|\mathcal{P}_{k_{1}}(n_{1})|^{2}\cdots|\mathcal{P}_{k_{r-1}}(n_{r-1})|^{2}\Big{)}.$

Notice that $n-n_{r}\geq n/2$ as $r\geq 2$. Since $k\leq\frac{1}{3}\log n$ by
assumption, this implies that $k-k_{r}\leq
k-1\leq\frac{1}{3}\log(n/2)\leq\frac{1}{3}\log(n-n_{r})$. Thus, by the
inductive hypothesis, the above is

$\ll_{r}\sum_{k_{r}=1}^{k-r+1}\sum_{n_{r}=1}^{\lfloor
n/r\rfloor}|\mathcal{P}_{k_{r}}(n_{r})|^{2}\frac{q^{2(n-n_{r})}(\log(n-n_{r})+c)^{2k-2k_{r}-2r+2}}{(n-n_{r})^{2}(k-k_{r}-r+1)!^{2}},$

where for brevity we have set $c=2-\log 2$. Applying Proposition 6, we see
that this is at most

$\displaystyle\sum_{k_{r}=1}^{k-r+1}\frac{q^{2n}}{(k_{r}-1)!^{2}(k-k_{r}-r+1)!^{2}}\sum_{n_{r}=1}^{\lfloor
n/r\rfloor}\frac{(\log
n_{r}+c)^{2k_{r}-2}(\log(n-n_{r})+c)^{2k-2k_{r}-2r+2}}{n_{r}^{2}(n-n_{r})^{2}}$
(4.1)
$\displaystyle\ll_{r}\frac{q^{2n}}{n^{2}}\sum_{k_{r}=1}^{k-r+1}\frac{(\log
n+c)^{2k-2k_{r}-2r+2}}{(k_{r}-1)!^{2}(k-k_{r}-r+1)!^{2}}\sum_{n_{r}=1}^{\lfloor
n/r\rfloor}\frac{(\log n_{r}+c)^{2k_{r}-2}}{n_{r}^{2}}.$

Note that for any integer $m\geq 0$,

$\sum_{j=1}^{\infty}\frac{(\log
j+c)^{m}}{j^{2}}\ll\int_{1}^{\infty}\frac{(\log
t+c)^{m}}{t^{2}}\;dt=\int_{c}^{\infty}t^{m}e^{c-t}\;dt\ll\int_{0}^{\infty}t^{m}e^{-t}\;dt=m!.$

Using this estimate on the inner sum over $n_{r}$, it follows that (4.1) is

$\ll_{r}\frac{q^{2n}}{n^{2}}\sum_{k_{r}=1}^{k-r+1}\frac{(2k_{r}-2)!(\log
n+c)^{2k-2k_{r}-2r+2}}{(k_{r}-1)!^{2}(k-k_{r}-r+1)!^{2}}.$

For the final sum over $k_{r}$, notice that the ratio of consecutive summands
is equal to

$\frac{2k_{r}(2k_{r}-1)}{k_{r}^{2}}\frac{(k-k_{r}-r+1)^{2}}{(\log
n+c)^{2}}\leq\frac{4k^{2}}{(\log n)^{2}}\leq\frac{4}{9},$

since $k\leq\frac{1}{3}\log n$ by assumption. Hence, the final sum over
$k_{r}$ is dominated by its value at the endpoint $k_{r}=1$, yielding the
desired estimate. This establishes Lemma 5. ∎

## References

  * [1] Afshar, A., and Porritt, S. The function field Sathe–Selberg formula in arithmetic progressions and ‘short intervals’.  Acta Arithmetica 187 (2019), 101–124.  Publisher: Instytut Matematyczny Polskiej Akademii Nauk.
  * [2] Gómez-Colunga, A., Kavaler, C., McNew, N., and Zhu, M. On the size of primitive sets in function fields.  Finite Fields and Their Applications 64 (2020), 101658.
  * [3] Granville, A., Harper, A. J., and Soundararajan, K. Mean values of multiplicative functions over function fields.  Research in Number Theory 1, 1 (Dec. 2015), 25.
  * [4] Harper, A. J. On the limit distributions of some sums of a random multiplicative function.  Journal für die reine und angewandte Mathematik (Crelles Journal) 2013, 678 (Jan. 2013).
  * [5] Hough, B. Summation of a random multiplicative function on numbers having few prime factors.  Mathematical Proceedings of the Cambridge Philosophical Society 150, 2 (Mar. 2011), 193–214.
  * [6] McLeish, D. L. Dependent Central Limit Theorems and Invariance Principles.  The Annals of Probability 2, 4 (1974), 620–628.  Publisher: Institute of Mathematical Statistics.
  * [7] Ramanujan, S., and Hardy, G. The normal number of prime factors of a number $n$.  Quarterly Jour, of Math 48 (1917), 76–92.
  * [8] Sathe, L. G. On a problem of Hardy on the distribution of integers having a given number of prime factors, I, II.  J. Indian Math. Soc.(NS) 17 (1953), 63–141.
  * [9] Sathe, L. G. On a problem of Hardy on the distribution of integers having a given number of prime factors, III, IV.  J. Indian Math. Soc.(NS) 18 (1954), 27–81.
  * [10] Selberg, A. Note on a paper by L. G. Sathe.  The Journal of the Indian Mathematical Society 18, 1 (1954), 83–87.
  * [11] Warlimont, R. Arithmetical semigroups. IV. Selberg’s analysis.  Arch. Math. (Basel) 60, 1 (1993), 58–72.
  * [12] Wintner, A. Random factorizations and Riemann’s hypothesis.  Duke Mathematical Journal 11, 2 (June 1944), 267–275.