The generalization ability of logistic regression with Markov sampling

1.   Introduction

The logistic regression model has become one of the most popular machine learning methods in classification ^[1,2,3,4]. Besides the advantages of good performance and strong interpretability in practical applications, the logistic regression model also has a complete theoretical basis in terms of consistency and generalization performance when the training samples are independent and identically distributed (i.i.d) ^[5,6,7,8]. However, the hypothesis of i.i.d is quite hard to be proved in practice, so it is natural to consider the logistic regression model with non-i.i.d samples.

The relaxation of the i.i.d hypothesis has been discussed for a long time in machine learning and statistical literature. For example, Wang et al. ^[9] pointed out that the statistical learning theory in the case of small samples cannot be directly applied to large samples and proposed the generalization bounds of under-sample models based on strict Bayesian network processing. Sun and Wu ^[10], Sun and Guo ^[11] and Chu and Sun ^[12] used mixed samples to analyze the error of $l_2$-norm least squares and $l_1$-norm least squares regression, respectively. Guo and Shi ^[13] proved that the learning speed of regularized least squares regression was faster than the classical method. Machine learning algorithms in the non-i.i.d case are solved by concentration inequalities because the concentration inequalities can provide probability upper bounds for the deviation ^[14]. Modha and Masry ^[15] extended the classical inequalities in the condition from i.i.d to m-correlation and strong mixing, respectively. Merlevède et al. ^[16] obtained a Bernstein type inequality for a class of weakly dependent and bounded random variables. Fan et al. ^[17] studied the Hoeffding inequality for general Markov chains and time-dependent functions.

In the paper, we enhance the performance of the logistic regression model from small samples to large samples. Machine learning usually performs well in Markov chain samples ^[18], so we develop the uniformly ergodic Markov chain algorithm (ueMC algorithm) for the logistic regression model. The ueMC algorithm can identify samples with classification errors and close to the decision boundary, and determine the final Markov samples used in the pre-training models. Compared with the algorithm proposed by Thongkam et al. ^[19], the ueMC algorithm does not directly eliminate the misclassified samples, as they are based on a random probability. Similar to the method proposed by Miranda et al. ^[20], the previous eliminated samples may be selected later. Inspired by ^[21], we study the generalization ability of the ueMC algorithm, and establish the optimal learning rate of the logistic regression classification for ueMC samples. Through numerical study and the simulation, it is verified that the performance of the ueMC algorithm based on ueMC samples is more effective than the algorithm based on other random samples, and the performance of the ueMC algorithm is also better than of the classical machine learning algorithm.

The paper is organized as follows. In Section 2, some definitions and notations are given. In Section 3, we present and prove the main results on the learning rates of the logistic regression model with ueMC samples. In Section 4, we develop a new ueMC algorithm, and present the numerical studies on the generalization performance of the logistic regression model based on Markov sampling for benchmark datasets. Finally, the conclusions are given in Section 5.

2.   Preliminaries

In this section we introduce the definitions and notations throughout this paper.

2.1.   Logistic regression model

Let $(\mathcal{X}, d)$ be a compact metric space and $\mathcal{Y} = \{0, 1\}$. A binary classifier is a function $\hat{f}: \mathcal{X} \rightarrow \mathcal{Y}$ which labels every point $x \in \mathcal{X}\subseteq \mathbb{R}$ with some $y \in \mathcal{Y}$. Let $\varphi$ be a probability distribution on $\mathcal{Z} = \mathcal{X} \times \mathcal{Y}$ and $(X, Y)$ be the corresponding random variable. Given $X_i = \left(1, x_{i 1}, \ldots, x_{i k}\right)^T \subseteq \mathbb{R}^{\mathrm{k}+1}$, $i = 1, 2, \ldots, N$, the form of the separating hyperplane is as follows:

where $W = \left(w_0, w_1, \ldots, w_k\right)^T$ is the coefficient of the variable.

Let $P\left(Y_i \mid X_i, W\right) = \frac{1}{1+e^{-W^T X_i}} = sigmod(\hat{f})$ represent the probability of the sample being a positive sample $\left(Y_i = 1\right)$, and $1-P\left(Y_i \mid X_i, W\right)$ represent the probability of the sample being a negative sample $\left(Y_i = 0\right)$. So we have:

where $P\left(Y_i = 1 \mid X_i, W\right) = \frac{e^{W^T X_i}}{1+e^{W^T X_i}}$.

The log-likelihood function is:

The objective function of the logistic regression model is:

Linear models are easy to over-fitting in high dimensions because of the correlation between features. In the paper, the weight term of the model is constrained to alleviate the problem of over-fitting by adding a regular term $c\left(W\right)$. We choose norm $l_2$ regularization and use BFGS (Broyden-Fletcher-Goldfarb-Shanno) algorithm ^[22] to solve the parameters.

Let $\mathcal{H}$ be Hilbert space, a set of real function on space $\mathcal{X} \subseteq \mathbb{R}$. If there is a kernel function $K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ satisfying $\forall x \in \mathcal{X}, K\langle\cdot, x\rangle \in \mathbb{R}$, then $\mathcal{H}_K$ is called a reproducing kernel Hilbert space satisfying $\forall x \in \mathcal{X}, \forall f \in \mathcal{H}, f(x) = \langle f, K\langle\cdot, x\rangle\rangle$.

For a function $f$ : $\mathcal{X} \rightarrow \mathbb{R}$, sign function $\operatorname{sgn}(f) = 1$ if $f(x) \geq 0$ and $\operatorname{sgn}(f) = 0$ if $f(x) < 0$. Then the logistic regression model is defined as $\operatorname{sgn}\left(f_{z, \lambda}\right)$, where $f_{z, \lambda}$ is a minimizer of the following optimization problem involving a set of random sample $S = \left\{z_i\right\}_{i = 1}^m \in \mathcal{Z}^m$ :

In Formula (2.6), $\ell(f, z) = -[y \ln (\operatorname{sigmoid}(f(x)))+(1-y) \ln (1-\operatorname{sigmoid}(f(x)))]$ is the loss function, $\mathcal{E}_z(f) = \frac{1}{m} \sum_{i = 1}^m \ell\left(f, z_i\right)$ is the empirical error, $\mathcal{E}(f) = E[\ell(f, z)]$ denotes the generalization error of the corresponding function $f$. $\lambda = 1 /(2 C)$ is the regularization parameter, where $C$ is a constant which depends on $m: C = C(m)$ and often $\lim\limits_{m\to\infty} C(m) = \infty$.

2.2.   Uniformly ergodic Markov chains (ueMC)

Suppose a Markov chain on $(\mathcal{Z}, \mathcal{S})$ is a sequence of random variables $\left\{Z_i\right\}_{i \geq 1}$ with a set of transition probability measures $P^{(n)}\left(A \mid z_i\right), A \in \mathcal{S}, z_i \in \mathcal{Z}$. It is assumed that

For any Markov chain, if the transition probability is independent of time, the Markov chain is stationary ^[23].

Definition 1. Given two probabilities $\nu_1, \nu_2$ on the measure space $(\mathcal{Z}, \mathcal{S})$, we define $\left\|\nu_1-\nu_2\right\|_{T V} = \sup_{A \in \mathcal{S}}\left|\nu_1(A)-\nu_2(A)\right|$ as the total variation distance between the measures $\nu_1$ and $\nu_2$. Meyn and Tweedie ^[24] pointed out that for a Markov chain $\left\{Z_i\right\}_{i \geq 1}$, if there are $0 < \gamma_0 < \infty$ and $0 < \rho_0 < 1$,

where $\pi(\cdot)$ is the stationary distribution of $\left\{Z_i\right\}_{i \geq 1}$, then $\left\{Z_i\right\}_{i \geq 1}$ is a ueMC.

Another equivalent definition of ueMC is the following Doeblin condition ^[25].

Proposition 1. (Doeblin condition): Suppose $\left\{Z_i\right\}_{i \geq 1}$ is a Markov chain with transition probability $P^n(\cdot \mid \cdot)$, and $\mu$ is a specific non-negative metric with nonzero mass $\mu_0$. If there is some integer $k$ such that $\forall z\in\mathcal{Z}$ and for all measurable sets $A, P^k(A \mid z) \leq \mu(A)$, then for any integer $n$, $\forall z_1, z_2\in \mathcal{Z}$, we have

where $\beta_1 = 1-\mu_0$.

3.   Bounds of generalization ability

In this section, we estimate the bounds on the generalization performance of the logistic regression model based on the ueMC sampling by following the enlightening ideas of ^[26].

3.1.   Bounds of generalization ability

To measure the generalization ability of $f_{z, \lambda}$, we identify how $\operatorname{sgn}\left(f_{z, \lambda}\right)$ converges (with respect to the misclassification error) to the best classifier as $C(m)$ tends to infinity. Recall the regression function of $\varphi$, $f_{\varphi} = \int_y y d \varphi(y|x)$, $x\in\mathcal{X}$. Then the Bayes rule is given by the sign of the regression function $f_c = \operatorname{sgn}(f_{\varphi})$. Referring to Vapnik ^[27], the speed at which $f_{z, \lambda}$ approaches $f_{\varphi}$ is measured by excess generalization error $\mathcal{E}\left(f_{z, \lambda}\right)-\mathcal{E}(f_{\varphi})$. Since the minimization (2.6) is taken over the discrete quantity $\mathcal{E}_z(f)$, we have to regulate the capacity of the function set. Here the capacity is measured by the covering number.

We should estimate the excess misclassification error $\mathcal{R}\left(\operatorname{sgn}\left(f_{z, \lambda}\right)\right)-\mathcal{R}\left(f_c\right)$ to bound the generalization ability of $f_{z, \lambda}$. The relation between excess misclassification error and excess generalization error $\mathcal{E}(f)-\mathcal{E}\left(f_{\varphi}\right)$ for convex loss is for $f:\mathcal{X} \rightarrow \mathbb{R}$,

Definition 2. Let $U > 0$, and $\mathcal{B}_U = \left\{f: f \in \mathcal{H}_K, \|f\|_{\mathcal{H}_K} \leq U\right\}$ be the sphere with radius $U$ in $\mathcal{H}_K$, let $\mathcal{N}(\epsilon) = \mathcal{N}\left(\mathcal{B}_U, \epsilon\right), \epsilon > 0$ be the covering number of $\mathcal{B}_U$.

Definition 3. The complexity index of $\mathcal{H}_K$ is $s$, if there is some $C_s > 0$ such that $\forall \epsilon > 0$,

Proposition 2. Let $f_{z, \lambda}$ be the function defined by (2.6), and define $f_\lambda: = \arg\min_{f \in \mathcal{H}_K}\{\lambda\|f\|_{\mathcal{H}_K}^2+\mathcal{E}(f)\}$ as a regularizing function, then for any $\lambda > 0$,

where sample error:

and regularization error:

Proof. According to the definition of $f_{z, \lambda}$,

we have

So

In Proposition 2, sample error

where $\xi_1 = \ell\left(f_{z, \lambda}, z\right)-\ell(f_{\varphi}, z)$ and $\xi_2 = \ell\left(f_\lambda, z\right)-\ell(f_{\varphi}, z)$. □

Definition 4. We say the function $f_{\varphi}$ can be approximated by $\mathcal{H}_K$ with exponent $0 < \beta \leq 1$, if there exists a constant $C_\beta$ such that for any $\lambda > 0, R_\lambda \leq C_\beta \lambda^\beta$. In the paper, we assume that there is a constant $B$ such that $\left|f_{\varphi}\right| \leq B$.

3.2.   Main tools

To prove the main results, there are four lemmas.

Lemma 1. Let $f$ be a continuous function defined on $\mathcal{X}$ and $\|f\|_{\infty} = \sup_{x \in \mathcal{X}}|f(x)|$. Let $\kappa = \sup_{x \in \mathcal{X}} \sqrt{K\langle x, x\rangle}$, then $\|f\|_{\infty} = \sup_{x \in \mathcal{X}}|f(x)| \leq \kappa\|f\|_{\mathcal{H}_K}, \forall f \in \mathcal{H}_K$.

Proof. According to the Cauchy-Schwartz inequality of PSD kernel and the reproducing property of reproducing kernel Hilbert space, we have:

it follows that

□

Lemma 2. $\xi_2 = \ell\left(f_\lambda, z\right)-\ell(f_{\varphi}, z)$, $|f_{\varphi}|\leq B$, we have

Proof. Due to

then $\left\|f_\lambda\right\|_{\mathcal{H}_K} \leq \sqrt{R_\lambda / \lambda}$. By applying Lemma 1, there holds $\left\|f_\lambda\right\|_{\infty} \leq \kappa \sqrt{R_\lambda / \lambda}$ as $\xi_2 = \ell\left(f_\lambda, z\right)-\ell(f_{\varphi}, z)$ and $|f_{\varphi}| \leq B$, and when $y = 1$,

when $y = 0$,

Then, the proof ends with $\left|\xi_2\right| = |\ell\left(f_\lambda, z\right)-\ell(f_{\varphi}, z)| \leq|f_\lambda|+|f_{\varphi}|+|\ln (1+e^{f_{\varphi}})|+|\ln (1+e^{f_\lambda})|$. □

Lemma 3. (proved in ^[21]): Hoeffding's inequality: Let $Z = \left\{Z_i\right\}_{i = 1}^m$ be a ueMC sample and $\mathcal{F}$ be a set of bounded and measurable functions, i.e. there is a constant $C$, such that $\forall z \in \mathcal{Z}$, $\forall g\in\mathcal{F}$, $\quad 0\leq g(z)\leq C$. For any $\varepsilon > 0$, we have

where $\Gamma_0 = \sqrt{2} /(1-\beta^{1 / 2 t})$ and $\beta = 1-\mu_0$. Here $\mu_0$ and $t$ are from Doeblin condition ^[25].

According to Lemma 3, for any $\varepsilon > 0$,

Let $\delta_1 = \exp \left\{\frac{-\varepsilon m}{56\left\|\Gamma_0\right\|^2 d}\right\}$, so $\varepsilon = \frac{-56\left\|\Gamma_0\right\|^2 d \ln \left(\delta_1\right)}{m}$ and $\sqrt{\varepsilon} \sqrt{\varepsilon(f)+\varepsilon} \leq \frac{1}{2} \varepsilon(f)+\varepsilon$. Then for any $0 < \delta_1 < 1$, we obtain

with probability at least $1-\delta_1$.

Let $U > 0$ and $\mathcal{F}_U = \{g = \ell(f, z)-\ell(f_{\varphi}, z), f\in\mathcal{B}_U\}$, we have

From the definition of $\mathcal{B}_U$, it can be seen that for any $f \in \mathcal{B}_U$, there are $\|f\|_{\infty} \leq \kappa\|f\|_{\mathcal{H}_K} \leq \kappa U$ and then $\left|f_{\varphi}\right| \leq B$. It follows that

Under the condition of Lemma 3, for any $\epsilon > 0$

For any $g_1, g_2\in\mathcal{F}_U$, $\left|\ln \left(1+e^{x_1}\right)-\ln \left(1+e^{x_2}\right)\right| \leq\left|x_1-x_2\right|$, it follows that $\left|g_1(x)-g_2(x)\right| \leq\left\|f_1-f_2\right\|_{\infty}$.

According to inequality (3.7), for any $\varepsilon > 0$

Therefore, according to $\mathcal{N}\left(\frac{\varepsilon}{U}\right) \leq \exp \left\{C_s\left(\frac{U}{\varepsilon}\right)^s\right\}$ by Definition 3, there holds, for $f_{z, \lambda}$,

In the (3.9), let

so

it is obtained that

Lemma 4. (Lemma 4 in ^[28]) Let $c_1$, $c_2 > 0$, and $p_1 > p_2 > 0$, then the equation $x^{p_1}-c_1 x^{p_2}-c_2 = 0$ has a unique positive zero $x^*$. In addition, $x^* \leq \max \left\{\left(2 c_1\right)^{1 /\left(p_1-p_2\right)}, \ \left(2 c_2\right)^{1/p_1}\right\}$.

3.3.   Main results

Through the above inference process, we form the following main results.

Theorem 1. Let $Z = \left\{Z_i\right\}_{i = 1}^m$ be a ueMC sample, then for any $0 < \delta < 1$,

holds true with probability at least $1-\delta$, where

here $\beta_1$ and $t$ are defined as that in Proposition 1.

Proof. According to Lemma 4, Eq (3.10) has a solution $\hat{\varepsilon} = \max \left\{\varepsilon_1, \varepsilon_2\right\}$ with

Since $\sqrt{\varepsilon} \sqrt{\varepsilon(f)+\varepsilon} \leq \frac{1}{2} \varepsilon(f)+\varepsilon$, in combination with inequality (3.9), inequality (3.12) holds at least with a probability of $1-\delta_2$,

Combining inequality (3.6) with inequality (3.12), inequality (3.13) holds at least $1-\delta$ probability for any $0 < \delta < 1$,

□

Theorem 2. Let $Z = \left\{Z_i\right\}_{i = 1}^m$ be a ueMC sample, Taking $\lambda = (1 / m)^{\vartheta}$. For any $\epsilon > 0$ and $0 < \delta < 1$, there exists a constant $\hat{C}$ independent of $m$ such that

holds true with probability at least $1-\delta$, providing $m \geq 112 b\left\|\Gamma_0\right\|^2 \ln (1 / \delta)\left(\ln (1 / \delta) / C_s\right)^{1 / s}/U$, where

Proof. The proof is easily obtained from Theorem 1 with the proof of Theorem 2 in ^[21]. □

4.   Markov sampling and numerical studies

In this section, we introduce a ueMC algorithm to generate the samples from a given dataset. We give numerical studies on the learning performance of the logistic regression model and present some useful discussions.

4.1.   Markov sampling algorithm

Here are the notations:

● $S_T$: the initial training set

● $S_{iid}$: a i.i.d sample from $S_T$

● $S_{mkv}$: a ueMC sample from $S_T$

● $N_T$: the number of positive samples in $S_{mkv}$

● $N_F$: the number of negative samples in $S_{mkv}$

● $k, m, N, n, a$, $max\_$iteration: super-parameters

The pseudocode of the ueMC algorithm is as follows:

Compared with data noise, the over-fitting problem caused by small sample size has a stronger impact on the generalization performance of the classifier (^[29]). Different from the methods from ^[11,19] based on threshold to eliminate noise data, the ueMC is constructed to avoid the problem of over-fitting caused by small training samples.

The ueMC algorithm uses the initial model $f_0$ of $S_{iid}$ and the loss function $\ell(f, z)$ to construct the transition probability $p_1, p_2, p_3$ of ueMC. Since $p_1, p_2, p_3$ is greater than 0 and the sample size in $S_T$ is limited, $S_{mkv}$ obtained by the ueMC algorithm is a ueMC, according to the research conclusion of ^[30].

Different from the MCMC algorithm proposed by ^[31,32], the ueMC algorithm does not need to know the probability distribution information of the training set samples. In addition, when $k = 0$, the algorithm degenerates into the classical logistic regression model. In order to make the following experimental results without loss of generality, we take $k = 2$ and $a = 1.2$.

4.2.   Experiment results

In this subsection, we present the numerical study on the learning performance of the logistic regression model based on linear prediction models for 9 real-world datasets (from http://archive.ics.uci.edu/ml/datasets and https://www.fml.tuebingen.mpg.de/). The information of these data sets is summarized in Table 1, and all these datasets are 2-classes realworld datasets. The samples in these datasets obey non-independent identical distribution. We use the SMOTE algorithm to deal with unbalanced data. For each data set, it is randomly divided into two parts: the training set and the test set.

In order to simplify the experimental process, we take $N = m$ in the ueMC algorithm, and carry out 50 repeated experiments for each dataset. The experimental results are shown in Table 2, where "MR (i.i.d.)" and "MR (Markov)" denote the misclassification rates of the logistic regression model based on random sampling and Markov sampling, respectively. In the following, we also discuss the experimental results based on $N < m$.

From Table 2, we can find that for 500 training samples, the standard deviations and means of average misclassification rates of the logistic regression model based on Markov sampling are smaller than that of random sampling except UCI-Heart Disease and UCI-Skin, and the means of average misclassification rates based on Markov sampling in UCI-Heart Disease and UCI-Skin datasets are still smaller than that of random samples. To show the learning performance of the logistic regression model based on Markov sampling, we present the average misclassification rates for 50 experimental results of the logistic regression model based on Markov sampling (non-i.i.d) and random sampling (i.i.d.) for different training sizes and four datasets in Figures 1–4.

To have a better understanding of learning performance of the logistic regression model based on Markov sampling, the following figures are presented to show the 50 experimental misclassification rates of the logistic regression model based on Markov sampling.

Figures 1–8 show that for UCI-HTRU2, UCI-Waveform, ELEC2 and UCI-Diabetes, the logistic regression model based on Markov sampling would have better learning performance than that of random sampling as the number of training samples is large. For other datasets, since the experimental results are similar, we do not present all of them here.

For the case of $N < m$, Table 3 shows that for the datasets of UCI-HTRU2, ELEC2 and UCI-Waveform, the logistic regression model based on smaller Markov chain samples (600 samples for UCI-HTRU2, ELEC2 and UCI-Waveform) can present smaller misclassification rates compared to more i.i.d. samples (2000 samples).

We compare the performance of the logistic regression model with the ueMC samples with the classical logistic regression model, SVMC, Adaboost, RandomForest and other classical machine learning models on UCI-HTRU2, UCI-Skin and MNIST. Tables 4 and 5 show the average classification error rates and Wilkeson signed rank test results of 50 experiments.

On the three real data sets, the difference between the logistic regression model based on the ueMC sampling and classical logistic regression models in classification error rates is statistically significant. It can be concluded that: 1) The generalization ability of the logistic regression model based on the ueMC sampling is better than that of the classical logistic regression model classifier, and it is robust. 2) The generalization ability of the logistic regression model with the ueMC samples is comparable to that of complex classifiers, such as random forest and Adaboost.

4.3.   Explanation of learning performance

The ueMC algorithm divides the samples into three categories according to the model pre-trained in the previous step. The first one is the samples with correct classification and close to the decision boundary, the second one is the samples with correct classification but far away from the decision boundary, and the third one is the samples with wrong classification.

According to the definition of the loss function, the distance between the sample and the decision boundary determines the size of the loss. Samples close to the decision boundary would train a better decision boundary for classification. The ueMC algorithm designs the acceptance probability $p_1$ and $p_2$ which ensure that the samples obtained according to the acceptance probability are close to the decision boundary. Therefore, when the initial logistic regression model can better fit the data set, the ueMC algorithm can ensure that the ueMC samples are excellent samples. In addition, we do not directly eliminate the samples with classification errors or far away from the decision boundary, but accept them with a small probability, which not only ensures the excellent properties of the training set, but also maintains the diversity of the training set samples to a certain extent, and can reduce the error caused by the misjudgment of the pre-training model. Therefore, the learning performance of the logistic regression model based on Markov sampling is better than that of random sampling, and the classifier based on Markov sampling is more sparse compared to random sampling.

5.   Conclusions

To study the generalization performance of the logistic regression model based on the ueMC sampling, inspired by the idea from ^[21], we estimate first the generalization error of logistic model algorithm based on the ueMC sampling. The generalization error is deconstructed into sample error and regularization error by error decomposition, and the convergence of the algorithm is proved. In addition, we also generate the samples from given dataset by the ueMC algorithm. The numerical studies show that as the number of training samples is large, the learning performance of the logistic regression model based on Markov sampling is better than that of random sampling, and its performance is also better than that of classical machine model algorithms, such as random forest and Adaboost. In other words, the ueMC algorithm significantly improves the learning performance of the logistic regression model. To our knowledge, this study is the first on this topic.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work is supported by the Innovation and Talent Base for Digital Technology and Finance (B21038) and "the Fundamental Research Funds for the Central Universities", Zhongnan University of Economics and Law (2722023EJ002).

Conflict of interest

The authors declare there is no conflicts of interest.