On Supervised Classification of Feature Vectors with Independent and Non-Identically Distributed Elements

Abstract

In this paper, we investigate the problem of classifying feature vectors with mutually independent but non-identically distributed elements that take values from a finite alphabet set. First, we show the importance of this problem. Next, we propose a classifier and derive an analytical upper bound on its error probability. We show that the error probability moves to zero as the length of the feature vectors grows, even when there is only one training feature vector per label available. Thereby, we show that for this important problem at least one asymptotically optimal classifier exists. Finally, we provide numerical examples where we show that the performance of the proposed classifier outperforms conventional classification algorithms when the number of training data is small and the length of the feature vectors is sufficiently high.

1. Introduction

1.1. Background

Supervised classification is a machine learning technique that maps an input feature vector to an output label based on a set of correctly labeled training data. There is no single learning algorithm that works best on all supervised learning problems, as shown by the no free lunch theorem in [1]. As a result, there are many algorithms proposed in the literature whose performance depends on the underlying problem and the amount of training data available. The most widely used algorithms in the literature are decision trees [2,3], Support Vector Machines (SVM) [4,5], Rule-Based Systems [6], naive Bayes classifiers [7], k-nearest neighbors (KNN) [8], logistic regressions, and neural networks [9,10].

1.2. Motivation

In the following, we discuss the motivation for this work.

1.2.1. Lack of Tight Upper Bounds on the Performance of Classifiers

In general, there are no tight upper bounds on the performance of the classifiers used in practice. Many of the previous works only provide experimental performance results. However, this approach has drawbacks. For example, one has to rely on the trial-and-error approach in order to develop a good classifier for a given problem, which impacts the reliability. Next, the algorithms whose performance has been verified only experimentally may work for a given problem, but may fail to work when applied to a similar problem. Finally, experimental results do not provide intuition into the underlying problem, whereas the analytical results provide the understanding of the underlying problem and the corresponding solutions.

Motivated by this, in the paper, we aim to investigate classifiers with analytical upper bounds on their performance.

1.2.2. Independent and Non-Identically Distributed Features

In general, we can categorize the statistical properties of the feature vectors, which are the input to the classifier, into three types. To this end, let $Y^n\left(X\right)=\left[Y_1\left(X\right),Y_2\left(X\right),\dots ,Y_n\left(X\right)\right]$ denote the input feature vector to the supervised classifier, where n is the length of the feature vector and X is the label to which the feature vector $Y^n\left(X\right)$ belongs. Then, we can distinguish the following three types of feature vectors depending on the statistics of the elements in the feature vector $Y^n\left(X\right)$.

The first type of feature vector is when the elements of $Y^n\left(X\right)$ are independent and identically distributed (i.i.d.). This is the simplest features model, but also the least applicable in practice. This model is identical to hypothesis testing, which has been well investigated in the literature [11,12,13]. As a result, tight upper bounds on the performance of supervised learning algorithms for this type of feature vector are available in the hypothesis testing literature. For instance, the authors in [11] showed that the posterior entropy and the maximum a posterior error probability decay to zero with the length of the feature vector at the identical exponential rate, where the maximum achievable exponent is the minimum Chernoff information. In [12], the authors determine the requirements for the length of the vector $Y^n\left(X\right)$ and the number of labels m in order to achieve vanishing exponential error probability in testing m hypothesis that minimizes the rejection zone. In [13], the authors provide an upper bound and a lower-bound on the error probability of Bayesian m-ary hypothesis testing in terms of conditional entropy.

The second type of feature vectors is when the elements of $Y^n\left(X\right)$ are mutually dependent and non-identically distributed (d.non-i.d.). This type of features model is the most general model and the most applicable in practice. However, it is also the most difficult to tackle analytically. As a result, supervised learning algorithms proposed for this features model lack analytical tight upper bounds on their performance [14,15,16,17,18,19,20,21,22,23]. This is because there are not any frameworks that produce closed-form results when deriving statistics of vectors with d.non-i.d. elements when the underlying distributions are unknown. Then how can we investigate analytically classifiers for practical scenarios when the feature vectors have d.non-i.d. elements? A possible approach leads us to the third type of feature vectors, explained in the following.

The third type of feature vectors is when the elements of $Y^n\left(X\right)$ are mutually independent but non-identically distributed (i.non-i.d.). This features model is much simpler than the d.non-i.d. features model and, more importantly, it is analytically tractable, as we show in this paper. Furthermore, this features model is applicable in practice. Specifically, there exists a class of algorithms, known as Independent Component Analysis (ICA), that transform vectors with d.non-i.d. elements into vectors with i.non-i.d. elements with a zero or a negligible loss of information [24,25,26,27,28]. The origins of ICA can be traced back to Barlow [29], who argued that a good representation of binary data can be achieved by an invertible transformation that transform vectors with d.non-i.d. elements into vectors with i.non-i.d. elements. Finding such a transformation with no prior information about the distribution of the data has been considered an open problem until recently [28]. Specifically, the authors in [28] show that this hard problem can be accurately solved with a branch and bound search tree algorithm, or tightly approximated with a series of linear problems. Thereby, the authors in [28] provide the first efficient set of solutions to Barlow’s problem. So far, the complexity of the fastest such algorithm is $\mathcal{O}\left(n\times 2^n\right)$ [28]. Nevertheless, since there exist such invertible transformations (i.e., no loss of information) which can transform vectors with d.non-i.d. elements into vectors with i.non-i.d. elements, we can tackle the features model comprised of d.non-i.d. elements by first transforming it (without loss of information) into the features model comprised of i.non-i.d. elements and then tackling the i.non-i.d. features model.

Motivated by this, in this paper, we investigate supervised classification of feature vectors with i.non-i.d. elements.

1.2.3. Small Training Set

The main factor that impacts the accuracy of supervised classification is the amount of training data. In fact, most supervised algorithms are able to learn only if there is a very large set of training data available [30]. The main reason for this is the curse of dimensionality [31,32], which states that “the higher the dimensionality of the feature vectors, the more training data are needed for the supervised classifier” [33]. For example, supervised classification methods such as random forest [34,35] and KNN [36] suffer from the curse of dimensionality. However, having large training data sets is not always possible in practice. As a result, designing a supervised classification algorithm that exhibits good performance even when the training data set is extremely small is important.

Motivated by this, in this paper, we investigate supervised classifiers for the case when t training feature vectors per label are available, where $t=1,2,...$

1.3. Contributions

In this paper, we propose an algorithm for supervised classification of feature vectors with i.non-i.d. elements when the number of training feature vectors per label is t, where $t=1,2,...$ Next, we derive an upper bound on the error probability of the proposed classifier for uniformly distributed labels and prove that the error probability exponentially decays to zero when the length of the feature vector, n, grows, even when only one training vector per label is available, i.e., when $t=1$. Hence, the proposed classification algorithm provides an asymptotically optimal performance even when the number of training vectors per label is extremely small. We compare the performance of the proposed classifier with the naive Bayes classifier and to the KNN algorithm. Our numerical results show that the proposed classifier significantly outperforms the naive Bayes classifier and the KNN algorithm when the number of training feature vectors per label is small and the length of the feature vectors n is sufficiently high.

The proposed algorithm is a form of the nearest neighbor classification algorithm, where the nearest neighbor is searched in the domain of empirical distributions. As a result, we refer to the algorithm as the nearest empirical distribution. The nearest empirical distribution algorithm is not new and, to the best of our knowledge, it was first proposed in [37] for the case when the elements of $Y^n\left(X\right)$ are i.i.d., i.e., for the equivalent problem of hypothesis testing. However, in this paper, we propose the nearest empirical distribution algorithm for the case when the elements of $Y^n\left(X\right)$ are i.non-i.d., which is much more complex than the problem of hypothesis testing where the elements of $Y^n\left(X\right)$ are i.i.d.

To the best of our knowledge, this is the first paper that investigates the important problem of classifying feature vectors with i.non-i.d. elements and provides an upper bound on its error probability. The novelty of this paper is not with the classifier itself, but rather in showing the importance of the problem of classifying feature vectors with i.non-i.d elements and in showing analytically that at least one classifier with an asymptotically optimal error probability exists when at least one training feature vectors per label is available.

The remainder of this paper is structured as follows. In Section 2, we formulate the considered classification problem. In Section 3, we provide our classifier and derive an upper bound on its error probability. In Section 4, we provide numerical examples of the performance on the proposed classifier. Finally, Section 5 concludes the paper.

2. Problem Formulation

The machine learning model is comprised of a label X, a feature vector $Y^n\left(X\right)=[Y_1\left(X\right),Y_2\left(X\right),$$\dots ,Y_n\left(X\right)]$ of length n mapped to the label X, and a learned label $\widehat{X}$, as shown in Figure 1. In this paper, we adopt the information-theoretic style of notations and thereby random variables are denoted by capital letters and their realizations are denoted with small letters. The feature vector $Y^n\left(X\right)$ is the input to the machine learning algorithm whose aim is to detect the label X from the observed feature vector $Y^n\left(X\right)$. The performance of the machine learning algorithm is measured by the error probability ${\mathbb{P}}_{\mathrm{e}}=\mathrm{Pr}\left\{X\ne \widehat{X}\right\}$.

We adopt the modeling in [38,39,40] and represent the dependency between the label X and the feature vector $Y^n\left(X\right)$ via a joint probability distribution $p_{X,Y^n}(x,y^n)$. Now, in order to gain a better understanding of the problem, we include the joint probability distribution $p_{X,Y^n}(x,y^n)$ into the model in Figure 1. To this end, since $p_{X,Y^n}(x,y^n)=p_{Y^n|X}\left(y^n\right|x)p_X\left(x\right)$ holds, instead of $p_{X,Y^n}(x,y^n)$, we can include the conditional probability distribution $p_{Y^n|X}\left(y^n\right|x)$ and the probability distribution $p_X\left(x\right)$ into the model in Figure 1, and thereby obtain the model in Figure 2.

Now, the classification learning model in Figure 2 is a system comprised of a label generating source X according to the distribution $p_{{}_X}\left(x\right)$, a feature vector generator modelled by the conditional probability distribution $p_{{}_{Y^n|X}}\left(y^n\right|x)$, a feature vector $Y^n$, a classifier that aims to detect X from the observed feature vector $Y^n$, and the detected label $\widehat{X}$. Note that the system model in Figure 2 can be seen equivalently as a communication system comprised of a source X, a channel with input X and output $Y^n$, and a decoder (i.e., detector) that aims to detect X from $Y^n$. The notation used in this paper, letter X for labels and letter Y for features, is based on the notation used in information theory for modelling communication systems. In the classification model shown in Figure 2, we assume that the label X can take values from the set $\mathcal{X}$, according to $p_{{}_X}\left(x\right)=1/\left|\mathcal{X}\right|$, where $|·|$ denotes the cardinality of a set. Next, we assume that the i-th element of the feature vector $Y^n$, $Y_i$, for $i=1,2,\cdots ,n$, takes values from the set $\mathcal{Y}=\left\{y_1,y_2,\dots ,y_{\left|\mathcal{Y}\right|}\right\}$, according to the conditional probability distribution $p_{{}_{Y_i|X}}\left(y_i\right|x)$.

Moreover, we assume that the elements of the feature vector $Y^n$ are i.non-i.d. As a result, the feature vector $Y^n$ takes values from the set ${\mathcal{Y}}^n$ according to the conditional probability distribution $p_{{}_{Y^n|X}}\left(y^n\right|x)$ given by

$$p_{{}_{Y^n|X}}\left(y^n\right|x)=p_{{}_{Y_1,Y_2,\dots ,Y_n|X}}(y_1,y_2,\dots ,y_n|x)\stackrel{\left(a\right)}{=}\prod _{i=1}^n{p}_{{}_{Y_i|X}}\left(y_i\right|x)\stackrel{\left(b\right)}{=}\prod _{i=1}^n{p}_{{}_i}\left(y_i\right|x),$$

(1)

where $\left(a\right)$ comes from the fact that elements in the feature vector $Y^n$ are mutually independent and $\left(b\right)$ is for the sake of notational simplicity, where $p_{{}_i}$ is used instead of $p_{{}_{Y_i|X}}$. As a result of (1), the considered classification model in Figure 2 can be represented equivalently as in Figure 3.

Next, we assume that $p_{{}_i}\left(y_i\right|x)$, $\forall i$, and thereby $p_{{}_{Y^n|X}}\left(y^n\right|x)$ are unknown to the classifier. Instead, the classifier knows $\mathcal{X}$, $\mathcal{Y}$, and for each $x_i\in \mathcal{X}$, where $i=1,2,\dots ,\left|\mathcal{X}\right|$, it has access to a finite set of t correctly labelled input–output pairs $(x_i,{\widehat{y}}_{i_1}^n),(x_i,{\widehat{y}}_{i_2}^n),\dots ,$ $(x_i,{\widehat{y}}_{i_t}^n)$, denoted by ${\mathcal{T}}_i$, referred to as the training set for label $x_i$.

Finally, we assume that the following holds

$$\sum _{l=1}^n{p}_l\left(y\right|x_i)\ne \sum _{l=1}^n{p}_l\left(y\right|x_j),\mathrm{for}y\in \mathcal{Y}\mathrm{and}i\ne j.$$

(2)

The condition in (2) means that the distribution of the feature vectors $Y^n\left(X\right)$ for label $X=i$ is not a perturbation of distribution of the feature vectors $Y^n\left(X\right)$ for label $X=j$. As a result, the proposed classifier only applies to the subset of data vectors with i.non-i.d. elements that satisfy (2).

For the classification system model defined above and illustrated in Figure 3, we wish to propose a classifier that exhibits an asymptotically optimal error probability ${\mathbb{P}}_{\mathrm{e}}=\mathrm{Pr}\left\{X\ne \widehat{X}\right\}$ with respect to the length of $Y^n$, n, for any $t\ge 1$, i.e., for any $t\ge 1$, ${\mathbb{P}}_{\mathrm{e}}\to 0$ as $n\to \infty$. Moreover, we wish to obtain an analytical upper bound on the error probability of the proposed classifier for a given t and n.

3. The Proposed Classifier and Its Performance

In this section, we propose our classifier, derive an analytical upper bound on its error probability, and prove that the classifier exhibits an asymptotically optimal performance when the length of the feature vector $Y^n$, n, satisfies $n\to \infty$. This is conducted in the following.

For a given vector ${\mathrm{v}}^n=(v_1,v_2,\dots ,v_n)$, let the Minkowski distance r be defined as

$$\begin{array}{c}\hfill {∥\mathrm{v}∥}_r={\left(\sum _{i=1}^n{v}_i^r\right)}^{(1/r)}.\end{array}$$

(3)

Moreover, for a given feature vector $y^k=(y_1,y_2,,\dots ,y_k)$, let $\mathcal{I}[y^k=y]$ be a function defined as

$$\begin{array}{c}\hfill \mathcal{I}[y^k=y]=\sum _{i=1}^k\mathcal{Z}[y_i=y],\end{array}$$

(4)

where $\mathcal{Z}[y_i=y]$ is an indicator function assuming the value 1 if $y_i=y$ and 0 otherwise. Hence, $\mathcal{I}[y^k=y]$ counts the number of elements in $Y^k$ that have the value y.

3.1. The Proposed Classifier

Let ${\widehat{y}}_i^{nt}$ be a vector obtained by concatenating all training feature vectors for the input label $x_i$ as

$$\begin{array}{c}\hfill {\widehat{y}}_i^{nt}=\left({\widehat{y}}_{i_1}^n,{\widehat{y}}_{i_2}^n,\dots ,{\widehat{y}}_{i_t}^n\right).\end{array}$$

(5)

Let $P_{{\widehat{y}}_i^{nt}}$ be the empirical probability distribution of the concatenated training feature vector for label $x_i$, ${\widehat{y}}_i^{nt}$, given by

$$\begin{array}{c}\hfill P_{{\widehat{y}}_i^{nt}}=\left[{\displaystyle \frac{\mathcal{I}\left[{\widehat{y}}_i^{nt}=y_1\right]}{nt}},{\displaystyle \frac{\mathcal{I}\left[{\widehat{y}}_i^{nt}=y_2\right]}{nt}},\dots ,{\displaystyle \frac{\mathcal{I}\left[{\widehat{y}}_i^{nt}=y_{\left|\mathcal{Y}\right|}\right]}{nt}}\right].\end{array}$$

(6)

Let $y^n$ be the observed feature vector at the classifier whose label it wants to detect and let $P_{y^n}$ denote the empirical probability distribution of $y^n$, given by

$$\begin{array}{c}\hfill P_{y^n}=\left[{\displaystyle \frac{\mathcal{I}\left[y^n=y_1\right]}{n}},{\displaystyle \frac{\mathcal{I}\left[y^n=y_2\right]}{n}},\dots ,{\displaystyle \frac{\mathcal{I}\left[y^n=y_{\left|\mathcal{Y}\right|}\right]}{n}}\right].\end{array}$$

(7)

Using the above notations, we propose the following classifier.

Proposition 1.

For the considered system model, we propose a classifier with the following classification rule

$$\begin{array}{c}\hfill \widehat{x}=x_i,\mathit{where}i=arg\underset{i}{min}{∥P_{y^n}-P_{{\widehat{y}}_i^{nt}}∥}_r,\end{array}$$

(8)

where $r\ge 1$ and ties are resolved by assigning the label among the ties uniformly at random. (For example, if ${∥P_{y^n}-P_{{\widehat{y}}_i^{nt}}∥}_r={∥P_{y^n}-P_{{\widehat{y}}_j^{nt}}∥}_r$ holds for, $i\ne j$, we set $\widehat{x}=x_i$ or $\widehat{x}=x_j$ uniformly at random).

As seen from (8), the proposed classifier assigns the label $x_i$ if the empirical probability distribution of the concatenated training feature vector mapped to label $x_i$, $P_{{\widehat{y}}_i^{nt}}$ is the closest, in terms of Minkowski distance r, to the empirical probability distribution of the observed feature vector $P_{y^n}$. In that sense, the proposed classifier can be considered as the nearest empirical distribution classifier.

3.2. Upper Bound on the Error Probability

The following theorem establishes an upper bound on the error probability of the proposed classifier.

Theorem 1.

Let ${\overline{\mathrm{P}}}_j$, for $j=1,2,\dots ,\left|\mathcal{X}\right|$, be a vector defined as

$$\begin{array}{c}\hfill {\overline{\mathrm{P}}}_j=\left[\overline{\mathrm{p}}\left(y_1|x_j\right),\overline{\mathrm{p}}\left(y_2|x_j\right),\dots ,\overline{\mathrm{p}}\left(y_{\left|\mathcal{Y}\right|}|x_j\right)\right],\end{array}$$

(9)

where $\overline{\mathrm{p}}\left(y\right|x_j)$ is given by

$$\begin{array}{c}\hfill \overline{\mathrm{p}}\left(y\right|x_j)={\displaystyle \frac{1}{n}}\sum _{k=1}^n{p}_{{}_k}\left(y\right|x_j).\end{array}$$

(10)

Then, for a given $r\ge 1$, the error probability of the proposed classifier is upper bounded by

$$\begin{array}{c}\hfill {\mathbb{P}}_{\mathrm{e}}\le 2\left|\mathcal{Y}\right|{\mathrm{e}}^{-2n{ϵ}^2}+2\left|\mathcal{Y}\right|{\mathrm{e}}^{-2n{t}^{1/3}{ϵ}^2},\end{array}$$

(11)

where ϵ is given by

$$\begin{array}{c}\hfill ϵ=\underset{\begin{array}{c}i,j\\ i\ne j\end{array}}{min}{\displaystyle \frac{{∥P_{{\widehat{y}}_i^{nt}}-{\overline{\mathrm{P}}}_j∥}_r}{(2+t^{-1/3}){\left|\mathcal{Y}\right|}^{1/r}}}.\end{array}$$

(12)

Proof of Theorem 1. 

Without loss of generality we assume that $x_1$ is the input to $p_{{}_{Y^n|X}}\left(y^n\right|x)$ and $y^n$ is observed.

Let ${\mathcal{A}}_k^{ϵ}$, for $1\le k\le \left|\mathcal{Y}\right|$, be a set defined as

$$\begin{array}{c}\hfill {\mathcal{A}}_k^{ϵ}=\left\{y^n:|{\displaystyle \frac{\mathcal{I}\left[y^n=y_k\right]}{n}}-\overline{\mathrm{p}}\left(y_k\right|x_1)|\le ϵ\right\}.\end{array}$$

(13)

Furthermore, let ${\mathcal{B}}_k^{ϵ}$, for $1\le k\le \left|\mathcal{Y}\right|$, be a set defined as

$$\begin{array}{c}\hfill {\mathcal{B}}_k^{ϵ}=\left\{{\widehat{y}}^{nt}:|{\displaystyle \frac{\mathcal{I}\left[{\widehat{y}}^{nT}=y_k\right]}{nt}}-\overline{\mathrm{p}}\left(y_k\right|x_1)|\le \frac{ϵ}{\sqrt[3]{t}}\right\}.\end{array}$$

(14)

Let ${\mathcal{A}}^{ϵ}={\displaystyle \bigcap _{k=1}^{\left|\mathcal{Y}\right|}}{\mathcal{A}}_k^{ϵ}$ and ${\mathcal{B}}^{ϵ}={\displaystyle \bigcap _{k=1}^{\left|\mathcal{Y}\right|}}{\mathcal{B}}_k^{ϵ}$. Now, for any $y^n\in {\mathcal{A}}^{ϵ}$, we have

$$\begin{array}{c}\hfill {\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-\overline{\mathrm{p}}\left(y_k\right|x_1){|}^r\right)}^{1/r}\stackrel{\left(a\right)}{\le }{\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}{ϵ}^r\right)}^{1/r},\end{array}$$

(15)

where $\left(a\right)$ follows from (13). Moreover, for ${\widehat{y}}_1^{nt}\in {\mathcal{B}}^{ϵ}$, we have

$$\begin{array}{c}\hfill {\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_1^{nt}=y_k]}{nt}}-\overline{\mathrm{p}}\left(y_k\right|x_1){|}^r\right)}^{1/r}\stackrel{\left(a\right)}{\le }{\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}{\left(\frac{ϵ}{\sqrt[3]{t}}\right)}^r\right)}^{1/r},\end{array}$$

(16)

where $\left(a\right)$ follows from (14). Next, we have the following upper bound

$$\begin{array}{cc}\hfill & {\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_1^{nt}=y_k]}{nt}}{|}^r\right)}^{1/r}\hfill \\ & ={\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-\overline{\mathrm{p}}\left(y_k\right|x_1)-\left({\displaystyle \frac{\mathcal{I}[{\widehat{y}}_1^{nt}=y_k]}{nt}}-\overline{\mathrm{p}}\left(y_k\right|x_1)\right){|}^r\right)}^{1/r}\hfill \\ & \stackrel{\left(a\right)}{\le }{\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-\overline{\mathrm{p}}\left(y_k\right|x_1){|}^r\right)}^{1/r}+{\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_1^{nt}=y_k]}{nt}}-\overline{\mathrm{p}}\left(y_k\right|x_1){|}^r\right)}^{1/r},\hfill \end{array}$$

(17)

where $\left(a\right)$ follows from the Minkowski inequality. Combining (15)–(17), we obtain

$$\begin{array}{c}\hfill {\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_1^{nt}=y_k]}{nt}}{|}^r\right)}^{1/r}\le {\left|\mathcal{Y}\right|}^{1/r}ϵ+{\left|\mathcal{Y}\right|}^{1/r}\frac{ϵ}{\sqrt[3]{t}}.\end{array}$$

(18)

Hence, the Minkowski distance between the empirical probability distribution of the observed vector $y^n$ and the empirical probability distribution of the concatenated training vector for label $x_1$ is upper bounded by the right hand side of (18). We now derive a lower bound for ${\widehat{y}}_i^{nt}$, where $i\ne 1$. For any $x_i$, such that $i\ne 1$, we have

$$\begin{array}{cc}\hfill & {\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_i^{nt}=y_k]}{nt}}{|}^r\right)}^{1/r}+{\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}{ϵ}^r\right)}^{1/r}\hfill \\ \hfill & \stackrel{\left(a\right)}{\ge }{\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_i^{nt}=y_k]}{nt}}{|}^r\right)}^{1/r}+{\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-\overline{\mathrm{p}}\left(y_k\right|x_1){|}^r\right)}^{1/r}\hfill \\ \hfill & \stackrel{\left(b\right)}{\ge }{\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_i^{nt}=y_k]}{nt}}-\overline{\mathrm{p}}\left(y_k\right|x_1){|}^r\right)}^{1/r},\hfill \end{array}$$

(19)

where $\left(a\right)$ follows from (15) and $\left(b\right)$ is again due to the Minkowski inequality. The expression in (19), can be written equivalently as

$$\begin{array}{cc}\hfill & {\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_i^{nt}=y_k]}{nt}}{|}^r\right)}^{1/r}\hfill \\ & \ge {\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_i^{nt}=y_k]}{nt}}-\overline{\mathrm{p}}\left(y_k\right|x_1){|}^r\right)}^{1/r}-{\left|\mathcal{Y}\right|}^{1/r}ϵ,\hfill \end{array}$$

(20)

where $i\ne 1$. Now, using the definitions of $P_{{\widehat{y}}_i^{nt}}$ and ${\overline{\mathrm{P}}}_1$ given by (6) and (9), respectively, into (20) we can replace the expression in the right-hand side of (20) by ${∥P_{{\widehat{y}}_i^{nt}}-{\overline{\mathrm{P}}}_1∥}_r$, and thereby for any $i\ne 1$ we have

$$\begin{array}{cc}\hfill {\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_i^{nt}=y_k]}{nt}}{|}^r\right)}^{1/r}\ge & {∥P_{{\widehat{y}}_i^{nt}}-{\overline{\mathrm{P}}}_1∥}_r-{\left|\mathcal{Y}\right|}^{1/r}ϵ.\hfill \end{array}$$

(21)

The expression in (21) represents a lower bound on the Minkowski r distance between the empirical probability distribution of the observed vector $y^n$ and the empirical probability distribution of the concatenated training vector for any label $x_i$, where $i\ne 1$.

Using the bounds in (18) and (21), we now relate the left-hand sides of (18) and (21). As long as the following inequality holds for each $i\ne 1$,

$$\begin{array}{c}\hfill {\left|\mathcal{Y}\right|}^{1/r}ϵ\left(1+\frac{1}{\sqrt[3]{t}}\right)<\parallel P_{{\widehat{y}}_i^{nt}}-{\overline{\mathrm{P}}}_1{\parallel }_r-{\left|\mathcal{Y}\right|}^{1/r}ϵ,\end{array}$$

(22)

which is equivalent to the following for $i\ne 1$

$$\begin{array}{c}\hfill ϵ<{\displaystyle \frac{{∥P_{{\widehat{y}}_i^{nt}}-{\overline{\mathrm{P}}}_1∥}_r}{(2+t^{-1/3}){\left|\mathcal{Y}\right|}^{1/r}}},\end{array}$$

(23)

$$\begin{array}{cc}\hfill {\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_1^{nt}=y_k]}{nt}}{|}^r\right)}^{1/r}& \stackrel{\left(a\right)}{\le }{\left|\mathcal{Y}\right|}^{1/r}ϵ\left(1+\frac{1}{\sqrt[3]{t}}\right)\hfill \\ \hfill & \stackrel{\left(b\right)}{<}\parallel P_{{\widehat{y}}_i^{nt}}-{\overline{\mathrm{P}}}_1{\parallel }_r-|\mathcal{Y}{|}^{1/r}ϵ\hfill \\ & \stackrel{\left(c\right)}{\le }{\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_i^{nt}=y_k]}{nt}}{|}^r\right)}^{1/r},\hfill \end{array}$$

(24)

where $\left(a\right)$, $\left(b\right)$, and $\left(c\right)$ follow from (18), (22), and (21), respectively. Thereby, from (24), we have the following for $i\ne 1$

$$\begin{array}{c}\hfill {\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_1^{nT}=y_k]}{nT}}{|}^r\right)}^{1/r}<{\left(\sum _{k=1}^{\left|\mathcal{Y}\right|}|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_i^{nT}=y_k]}{nT}}{|}^r\right)}^{1/r}.\end{array}$$

(25)

Note that the right- and left-hand sides of (25) can be replaced by the Minkowski distance of the vectors

$$\begin{array}{c}\hfill {\mathrm{v}}_1=\left[{\displaystyle \frac{\mathcal{I}\left[y^n=y_1\right]}{n}}-{\displaystyle \frac{\mathcal{I}\left[{\widehat{y}}_1^{nt}=y_1\right]}{nt}},\dots ,{\displaystyle \frac{\mathcal{I}\left[y^n=y_{\left|\mathcal{Y}\right|}\right]}{n}}-{\displaystyle \frac{\mathcal{I}\left[{\widehat{y}}_1^{nt}=y_{\left|\mathcal{Y}\right|}\right]}{nt}}\right],\end{array}$$

(26)

and

$$\begin{array}{c}\hfill {\mathrm{v}}_2=\left[{\displaystyle \frac{\mathcal{I}\left[y^n=y_1\right]}{n}}-{\displaystyle \frac{\mathcal{I}\left[{\widehat{y}}_i^{nt}=y_1\right]}{nt}},\dots ,{\displaystyle \frac{\mathcal{I}\left[y^n=y_{\left|\mathcal{Y}\right|}\right]}{n}}-{\displaystyle \frac{\mathcal{I}\left[{\widehat{y}}_i^{nt}=y_{\left|\mathcal{Y}\right|}\right]}{nt}}\right],\end{array}$$

(27)

respectively. Now, (26) and (27) can be replaced by $P_{y^n}-P_{{\widehat{y}}_1^{nt}}$ and $P_{y^n}-P_{{\widehat{y}}_i^{nt}}$, respectively, by the definitions of $P_{y^n}$ and $P_{{\widehat{y}}_i^{nt}}$ given by (7) and (6), respectively. Therefore, (25) can be written equivalently as

$$\begin{array}{c}\hfill {∥P_{y^n}-P_{{\widehat{y}}_1^{nt}}∥}_r<{∥P_{y^n}-P_{{\widehat{y}}_i^{nt}}∥}_r.\end{array}$$

(28)

Now, let us highlight what we have obtained. We obtained that there is an $ϵ$ for which if (23) holds for $i\ne 1$, and for that $ϵ$ there are sets ${\mathcal{A}}^{ϵ}$ and ${\mathcal{B}}^{ϵ}$ for which $y^n\in {\mathcal{A}}^{ϵ}$ and ${\widehat{y}}_1^{nt}\in {\mathcal{B}}^{ϵ}$ then (28) holds for $i\ne 1$, and thereby our classifier will detect that $x_1$ is the correct label. Using this, we can upper bound the error probability as

$$\begin{array}{cc}\hfill {\mathbb{P}}_{\mathrm{e}}& =1-\mathrm{Pr}\left\{{\widehat{x}}_1=x_1\right\}\hfill \\ & \le 1-\mathrm{Pr}\{\left(y^n\in {\mathcal{A}}^{ϵ}\right)\cap \left({\widehat{y}}_1^{nt}\in {\mathcal{B}}^{ϵ}\right)\left|ϵ\in \mathcal{S}\right\},\hfill \end{array}$$

(29)

where $\mathcal{S}$ is a set defined as

$$\begin{array}{c}\hfill \mathcal{S}=\left\{ϵ:ϵ\le \underset{\begin{array}{c}i\\ i\ne 1\end{array}}{min}{\displaystyle \frac{{∥P_{{\widehat{y}}_i^{nt}}-{\overline{\mathrm{P}}}_1∥}_r}{(2+t^{-1/3}){\left|\mathcal{Y}\right|}^{1/r}}}\right\}.\end{array}$$

(30)

In the following, we derive the expression in (29). The right-hand side of (29) can be upper bounded as -4.6cm0cm

$$\begin{array}{cc}\hfill 1-\mathrm{Pr}\{\left(y^n\in {\mathcal{A}}^{ϵ}\right)\cap \left({\widehat{y}}_1^{nt}\in {\mathcal{B}}^{ϵ}\right)\left|ϵ\in \mathcal{S}\right\}& =\mathrm{Pr}\{\left(y^n\notin {\mathcal{A}}^{ϵ}\right)\cup \left({\widehat{y}}_1^{nt}\notin {\mathcal{B}}^{ϵ}\right)\left|ϵ\in \mathcal{S}\right\}\hfill \\ \hfill & \stackrel{\left(a\right)}{\le }\mathrm{Pr}\left\{y^n\notin {\mathcal{A}}^{ϵ}|ϵ\in \mathcal{S}\right\}+\mathrm{Pr}\{{\widehat{y}}_1^{nt}\notin {\mathcal{B}}^{ϵ}\left|ϵ\in \mathcal{S}\right\},\hfill \end{array}$$

(31)

where $\left(a\right)$ follows from Boole’s inequality. Now, note that we have the following upper bound for the first expression in the right-hand side of (31)

$$\begin{array}{cc}\hfill \mathrm{Pr}\left\{y^n\notin {\mathcal{A}}^{ϵ}|ϵ\in \mathcal{S}\right\}& =\mathrm{Pr}\{y^n\notin \bigcap _{k=1}^{\left|\mathcal{Y}\right|}{\mathcal{A}}_k^{ϵ}\left|ϵ\in \mathcal{S}\right\}\hfill \\ \hfill & =\mathrm{Pr}\{y^n\in \bigcup _{k=1}^{\left|\mathcal{Y}\right|}\overline{{\mathcal{A}}_k^{ϵ}}\left|ϵ\in \mathcal{S}\right\}\hfill \\ & \stackrel{\left(a\right)}{\le }\sum _{k=1}^{\left|\mathcal{Y}\right|}\mathrm{Pr}\left\{y^n\in \overline{{\mathcal{A}}_k^{ϵ}}|ϵ\in \mathcal{S}\right\}\hfill \\ & =\sum _{k=1}^{\left|\mathcal{Y}\right|}\mathrm{Pr}\left\{\right|{\displaystyle \frac{\mathcal{I}[y^n=y_k]}{n}}-\overline{\mathrm{p}}\left(y_k\right|x_1)|>ϵ\left|ϵ\in \mathcal{S}\right\}\hfill \\ & =\sum _{k=1}^{\left|\mathcal{Y}\right|}\mathrm{Pr}\left\{\right|\sum _{j=1}^n{\displaystyle \frac{\mathcal{Z}[y_j=y_k]}{n}}-\overline{\mathrm{p}}\left(y_k\right|x_1)|>ϵ\left|ϵ\in \mathcal{S}\right\},\hfill \end{array}$$

(32)

where $\overline{{\mathcal{A}}_k^{ϵ}}$ is the complement of ${\mathcal{A}}_k^{ϵ}$ and $\left(a\right)$ follows from Boole’s inequality. Note that $\mathcal{Z}[y_1=y_k],\mathcal{Z}[y_2=y_k],\dots ,\mathcal{Z}[y_n=y_k]$ in (32) are n independent Bernoulli random variables with probabilities of success $p_{{}_1}\left(y_k\right|x_1),p_{{}_2}\left(y_k\right|x_1),\dots ,p_{{}_n}\left(y_k\right|x_1)$, respectively. Let $\mathcal{W}\left[y_k\right]$ be a binomial random variable with parameters $\left(n,\overline{\mathrm{p}}\left(y_k\right|x_1)\right)$. We proceed the proof by introducing the following well-known Hoefdding’s Theorem from [41]. □

Theorem 2

(Hoeffding [41]). Assume that $Z_1,Z_2,\dots ,$ and $Z_n$ are n independent Bernoulli random variables with probabilities of success $p_{{}_1},p_{{}_2},\dots ,$ and $p_{{}_n}$, respectively. Next, let $\mathrm{Z}$ be defined as $\mathrm{Z}=Z_1+Z_2+\dots +Z_n$ and, let $\overline{\mathrm{p}}$ be defined as $\overline{\mathrm{p}}=\left(p_{{}_1}+p_{{}_2}+\dots +p_{{}_n}\right)/n$. Let $\mathrm{W}$ be a binomial random variable with parameters $(n,\overline{\mathrm{p}})$. Then, for a given a and b, where $0\le a\le n\overline{\mathrm{p}}\le b\le n$ holds, we have

$$\begin{array}{c}\hfill \mathrm{Pr}\left\{a\le \mathrm{W}\le b\right\}\le \mathrm{Pr}\left\{a\le \mathrm{Z}\le b\right\}.\end{array}$$

(33)

In other words, the probability distribution of $\mathrm{W}$ is more dispersed around its mean $n\overline{\mathrm{p}}$ than is the probability distribution of $\mathrm{Z}$. Except in the trivial case when $a=b=0$, the bound in (33) holds with equality if and only if $p_1=\dots =p_n=\overline{\mathrm{p}}$.

Proof of Theorem 2. 

Please refer to [41]. □

Setting $a=n(\overline{\mathrm{p}}-\delta )$ and $b=n(\overline{\mathrm{p}}+\delta )$ in (33), we obtain

$$\begin{array}{c}\hfill \mathrm{Pr}\left\{n(\overline{\mathrm{p}}-\delta )\le \mathrm{W}\le n(\overline{\mathrm{p}}+\delta )\right\}\le \mathrm{Pr}\left\{n(\overline{\mathrm{p}}-\delta )\le \mathrm{Z}\le n(\overline{\mathrm{p}}+\delta )\right\}.\end{array}$$

(34)

Using (34), we have the following upper bound

$$\begin{array}{cc}\hfill \mathrm{Pr}\left\{|{\displaystyle \frac{\mathrm{Z}}{n}}-\overline{\mathrm{p}}|>\delta \right\}& =1-\mathrm{Pr}\left\{n(\overline{\mathrm{p}}-\delta )\le \mathrm{Z}\le n(\overline{\mathrm{p}}+\delta )\right\}\hfill \\ & \stackrel{\left(a\right)}{\le }1-\mathrm{Pr}\left\{n(\overline{\mathrm{p}}-\delta )\le \mathrm{W}\le n(\overline{\mathrm{p}}+\delta )\right\}\hfill \\ & =\mathrm{Pr}\left\{|{\displaystyle \frac{\mathrm{W}}{n}}-\overline{\mathrm{p}}|>\delta \right\},\hfill \end{array}$$

(35)

where $\left(a\right)$ follows from (34).

We now turn to the proof of Theorem 1. According to Theorem 2, the probability distribution of $\mathcal{W}\left[y_k\right]$ is more dispersed around its mean $n\overline{\mathrm{p}}\left(y_k\right|x_1)$ than is the probability distribution of ${\sum }_{1\le j\le n}\mathcal{Z}[y_j=y_k]$. Therefore, we can upper bound the probability in the last line of (32) as

$$\begin{array}{c}\hfill \mathrm{Pr}\left\{\right|\sum _{j=1}^n{\displaystyle \frac{\mathcal{Z}[y_j=y_k]}{n}}-\overline{\mathrm{p}}\left(y_k\right|x_1)\left|>ϵ\left|ϵ\in \mathcal{S}\right\}\stackrel{\left(a\right)}{\le }\mathrm{Pr}\right\{|{\displaystyle \frac{\mathcal{W}\left[y_k\right]}{n}}-\overline{\mathrm{p}}\left(y_k\right|x_1)|>ϵ|ϵ\in \mathcal{S}\},\end{array}$$

(36)

where $ϵ\in \mathcal{S}$ is defined in (30) and $\left(a\right)$ follows from (35). Now, let us introduce another well-known Hoeffding’s Theorem from [42].

Theorem 3

(Hoeffding’s inequality [42]). Let $W_1,W_2,\dots ,W_n$ be n independent random variables such that for each $1\le i\le n$, we have $\mathrm{Pr}\left\{W_i\in [a_i,b_i]\right\}=1$. Then for $S_n$, defined as $S_n={\displaystyle \sum _{i=1}^n}{W}_i$, we have

$$\begin{array}{c}\hfill \mathrm{Pr}\left\{S_n-\mathbb{E}\left[S_n\right]\ge \delta \right\}\le exp\left(-\frac{2{\delta }^2}{{\sum }_{i=1}^n{(b_i-a_i)}^2}\right),\end{array}$$

(37)

where $\mathbb{E}\left[S_n\right]$ is the expectation of $S_n$.

Proof of Theorem 3. 

Please refer to [42]. □

Back to (36), by using the result of (37) for $a_i=0$ and $b_i=1$ since the binomial random variable $\mathcal{W}\left[y_k\right]$ can take values 0 or 1, respectively, we have

$$\begin{array}{cc}\hfill \mathrm{Pr}\left\{\right|\sum _{j=1}^n{\displaystyle \frac{\mathcal{Z}[y_j=y_k]}{n}}-\overline{\mathrm{p}}\left(y_k\right|x_1)\left|>ϵ\right|ϵ\in \mathcal{S}\}& \le 2exp\left(-\frac{2n^2{ϵ}^2}{{\sum }_{1\le i\le n}{(1-0)}^2}\right)\hfill \\ \hfill & \le 2{\mathrm{e}}^{-2n{ϵ}^2},\hfill \end{array}$$

(38)

where $ϵ\in \mathcal{S}$ is defined in (30). Inserting (38) into (32), we obtain the following upper bound

$$\begin{array}{c}\hfill \mathrm{Pr}\left\{y^n\notin {\mathcal{A}}^{ϵ}|ϵ\in \mathcal{S}\right\}\le 2\left|\mathcal{Y}\right|{\mathrm{e}}^{-2n{ϵ}^2}.\end{array}$$

(39)

Similarly, we have the following result for the second expression in the right-hand side of (31)

$$\begin{array}{cc}\hfill \mathrm{Pr}\{{\widehat{y}}_1^{nt}\notin {\mathcal{B}}^{ϵ}|ϵ\in \mathcal{S}\}& =\mathrm{Pr}\{{\widehat{y}}_1^{nt}\notin \bigcap _{k=1}^{\left|\mathcal{Y}\right|}{\mathcal{B}}_k^{ϵ}|ϵ\in \mathcal{S}\}\hfill \\ \hfill & =\mathrm{Pr}\{{\widehat{y}}_1^{nt}\in \bigcup _{k=1}^{\left|\mathcal{Y}\right|}\overline{{\mathcal{B}}_k^{ϵ}}|ϵ\in \mathcal{S}\}\hfill \\ & \stackrel{\left(a\right)}{\le }\sum _{k=1}^{\left|\mathcal{Y}\right|}\mathrm{Pr}\left\{{\widehat{y}}_1^{nt}\in \overline{{\mathcal{B}}_k^{ϵ}}|ϵ\in \mathcal{S}\right\}\hfill \\ & =\sum _{k=1}^{\left|\mathcal{Y}\right|}\mathrm{Pr}\left\{\right|{\displaystyle \frac{\mathcal{I}[{\widehat{y}}_1^{nt}=y_k]}{nt}}-\overline{\mathrm{p}}\left(y_k\right|x_1)\left|>\frac{ϵ}{\sqrt[3]{t}}\right|ϵ\in \mathcal{S}\}\hfill \\ & =\sum _{k=1}^{\left|\mathcal{Y}\right|}\mathrm{Pr}\left\{\right|\sum _{j=1}^{nt}{\displaystyle \frac{\mathcal{Z}[y_j=y_k]}{nt}}-\overline{\mathrm{p}}\left(y_k\right|x_1)\left|>\frac{ϵ}{\sqrt[3]{t}}\right|ϵ\in \mathcal{S}\},\hfill \end{array}$$

(40)

where again $\left(a\right)$ follows from Boole’s inequality. Note that due to (5), for any integer number l such that $0\le l\le t-1$ the random variables $\mathcal{Z}[y_{nl+1}=y_k],\mathcal{Z}[y_{nl+2}=y_k],\dots ,$ and $\mathcal{Z}[y_{nl+n}=y_k]$ in (40) are n independent Bernoulli random variables with the probabilities of success $p_{{}_1}\left(y_k\right|x_1),p_{{}_2}\left(y_k\right|x_1),\dots ,$ and $p_{{}_n}\left(y_k\right|x_1)$, respectively $(y_{nl+1},y_{nl+2},\dots ,y_{nl+n}$ are elements of ${\widehat{y}}_{1_{l+1}}^n)$. In addition, note that

$$\begin{array}{cc}\hfill \overline{\mathrm{p}}\left(y_k\right|x_1)& ={\displaystyle \frac{1}{n}}\sum _{j=1}^n{p}_{{}_j}\left(y_k\right|x_1)\hfill \\ & ={\displaystyle \frac{1}{nt}}\left(\sum _{l=0}^{t-1}\sum _{j=1}^n{p}_{{}_j}\left(y_k\right|x_1)\right).\hfill \end{array}$$

(41)

Notice that for each $0\le l\le t-1$, $p_{{}_1}\left(y_k\right|x_1)+p_{{}_2}\left(y_k\right|x_1)+\dots +p_{{}_n}\left(y_k\right|x_1)$ is the summation of the probabilities of success of the random variables $\mathcal{Z}[y_{nl+1}=y_k],\mathcal{Z}[y_{nl+2}=y_k],\dots ,$ and $\mathcal{Z}[y_{nl+n}=y_k]$. Thereby, the last expression on the right-hand side of (41) is the average probability of success of random variables $\mathcal{Z}[y_j=y_k]$ for $1\le j\le nt$. Now, let $\mathcal{W}\left[y_k\right]$ be a binomial random variable with parameters $\left(nt,\overline{\mathrm{p}}\left(y_k\right|x_1)\right)$. Once again, according to Theorem 2, the probability distribution of $\mathcal{W}\left[y_k\right]$ is more dispersed around its mean $nt\overline{\mathrm{p}}\left(y_k\right|x_1))$ than is the probability distribution of ${\sum }_{1\le j\le nt}\mathcal{Z}[y_j=y_k]$. Therefore, the probability in the last line of (40) can be upper bounded as

$$\begin{array}{cc}\hfill \mathrm{Pr}\left\{\right|\sum _{j=1}^{nt}{\displaystyle \frac{\mathcal{Z}[y_j=y_k]}{nt}}-\overline{\mathrm{p}}\left(y_k\right|x_1)\left|>\frac{ϵ}{\sqrt[3]{t}}\right|ϵ\in \mathcal{S}\}& \stackrel{\left(a\right)}{\le }\mathrm{Pr}\left\{\right|{\displaystyle \frac{\mathcal{W}\left[y_k\right]}{nt}}-\overline{\mathrm{p}}\left(y_k\right|x_1)\left|>\frac{ϵ}{\sqrt[3]{t}}\right|ϵ\in \mathcal{S}\}\hfill \\ \hfill & \stackrel{\left(b\right)}{\le }2exp\left(-\frac{2{\left(nt\right)}^2{\left(t^{-1/3}ϵ\right)}^2}{{\sum }_{1\le i\le nt}{(1-0)}^2}\right)\hfill \\ \hfill & \le 2{\mathrm{e}}^{-2nt\left(t^{-2/3}{ϵ}^2\right)}\hfill \\ \hfill & =2{\mathrm{e}}^{-2n{t}^{1/3}{ϵ}^2},\hfill \end{array}$$

(42)

where $ϵ\in \mathcal{S}$, defined in (30), $\left(a\right)$ follows from (35) (in which n is replaced by $nt$), and $\left(b\right)$ is the result of (37) for $a_i=0$ and $b_i=1$ since the binomial random variable $\mathcal{W}\left[y_k\right]$ can take values 0 or 1, respectively. Inserting (42) into (40), we have the following upper bound

$$\begin{array}{c}\hfill \mathrm{Pr}\{{\widehat{y}}_1^{nt}\notin {\mathcal{B}}^{ϵ}|ϵ\in \mathcal{S}\}\le 2\left|\mathcal{Y}\right|{\mathrm{e}}^{-2n{t}^{1/3}{ϵ}^2}.\end{array}$$

(43)

Inserting (39) and (43) into (31), and then inserting (31) into (29), we obtain the following upper bound for the error probability

$$\begin{array}{c}\hfill {\mathbb{P}}_{\mathrm{e}}\le 2\left|\mathcal{Y}\right|{\mathrm{e}}^{-2n{ϵ}^2}+2\left|\mathcal{Y}\right|{\mathrm{e}}^{-2n{t}^{1/3}{ϵ}^2},\end{array}$$

(44)

where

$$\begin{array}{c}\hfill ϵ=\underset{\begin{array}{c}i,j\\ i\ne j\end{array}}{min}{\displaystyle \frac{{∥P_{{\widehat{y}}_i^{nt}}-{\overline{\mathrm{P}}}_j∥}_r}{(2+t^{-1/3}){\left|\mathcal{Y}\right|}^{1/r}}},\end{array}$$

(45)

which is the optimal value of $ϵ$ that exhibits the tightest upper bound for the error probability ${\mathbb{P}}_{\mathrm{e}}$ given by (44). This completes the proof of Theorem 1.

The following corollary provides a simplified upper bound on the error probability when $t\to \infty$.

Corollary 1.

When the number of training vectors per label reaches infinity, i.e., when $t\to \infty$, which is equivalently to the case when the probability distribution $p\left(y^n\right|x)$ is known at the classifier, the error probability of the proposed classifier is upper bounded as

$$\begin{array}{c}\hfill {\mathbb{P}}_{\mathrm{e}}\le 2\left|\mathcal{Y}\right|{\mathrm{e}}^{-2n{ϵ}^2},\end{array}$$

(46)

where ϵ is given by

$$\begin{array}{c}\hfill ϵ=\underset{\begin{array}{c}i,j\\ i\ne j\end{array}}{min}{\displaystyle \frac{{∥{\overline{\mathrm{P}}}_i-{\overline{\mathrm{P}}}_j∥}_r}{{2\left|\mathcal{Y}\right|}^{1/r}}}.\end{array}$$

(47)

Proof. 

The proof is straightforward. □

As can be seen from (8) and (11), the performance of the proposed classifier depends on r. We cannot derive the optimal value of r that minimizes the error probability since we do not have the exact expression of the error probability, we only have its upper bound. On the other hand, in practice, the optimal r with respect to the upper bound on the error probability also cannot be derived since the upper bound depends on ${\overline{\mathrm{P}}}_j$, which would be unknown in practice due to $p_{Y^n|X}\left(y^n\right|x)$ being unknown. As a result, for our numerical examples, we consider the Euclidean distance $(r=2)$, which is one of the most widely used distance metrics in practice.

The following corollary establishes the asymptotic optimality of the proposed classifier with respect to n.

Corollary 2.

The proposed classifier has an error probability that satisfies ${\mathbb{P}}_{\mathrm{e}}\to 0$ as $n\to \infty$ if $\left|\mathcal{Y}\right|\le \mathcal{O}\left(n^m\right)$, m is fixed, and $r>2m$. Here, $n^m$ indicates the dimension of our space, i.e., maximum number of alphabets each element in the feature vector $y^n$ can take. Thereby, the proposed classifier is asymptotically optimal.

Proof. 

For the proof, please see Appendix A. □

4. Simulation Results

In this section, we provide simulation results of the performance of the proposed classifier for $r=2$ and compare it to benchmark schemes. The benchmark schemes that we adopt for comparison are the naive Bayes classifier and the KNN algorithm. We cannot adopt a classifier based on a neural network since neural networks require a very large training set, which we assume is not available. For the naive Bayes classifier, the probability distribution $p_{{}_{Y^n|X}}\left(y^n\right|x)$ is estimated from the training vectors as follows. Let again ${\widehat{y}}_i^{nt}$ be a vector obtained by concatenating all training feature vectors for the input label $x_i$ as in (5). Then, the estimated probability distribution of $p(y_j=y|x_i)$, denoted by $\widehat{p}(y_j=y|x_i)$, is found as

$$\begin{array}{c}\hfill \widehat{p}(y_j=y|x_i)={\displaystyle \frac{\mathcal{I}\left[{\widehat{y}}_i^{nt}=y\right]}{nt}},\end{array}$$

(48)

and the naive Bayes classifier decides according to

$$\begin{array}{c}\hfill \widehat{x}=arg\underset{x_i}{max}\prod _{k=1}^n\widehat{p}\left(y_k\right|x_i).\end{array}$$

(49)

The main problem of the naive Bayes classifier occurs when an alphabet $y_j\in \mathcal{Y}$ is not present in the training feature vectors. In that case, $\widehat{p}\left(y_j\right|x_i)$ in (48) is $\widehat{p}\left(y_j\right|x_i)=0$, $\forall x_i\in \mathcal{X}$ and, as a result, the right hand side of (49) is zero since at least one of the elements in the product in (49) is zero. In this case, the naive Bayes classifier fails to provide an accurate classification of the labels. In what follows, we see that this issue of the naive Bayes classifier appears frequently when we have a small number of training feature vectors. On the other hand, the KNN classifier works as follows. For the observed feature vector $y^n$, the KNN classifier looks for the k nearest feature vectors to $y^n$, among all training feature vectors ${\widehat{y}}_{r_s}^n$, for all $1\le r\le \left|\mathcal{X}\right|$ and $1\le s\le T$. Then by considering a set of K input–output pairs $(x_k,{\widehat{y}}_{k_l}^n)$, for $k\in \{1,2,\dots ,|\mathcal{X}\left|\right\}$ and $l\in \{1,2,\dots ,|T\left|\right\}$, the KNN classifier decides a label which is the most frequent among $x_k$-s. The optimum value of k for $t=1$ is $k=1$.

In the following, we provide numerical examples where we illustrate the performance of the proposed classifier when $p_{{}_{Y^n|X}}\left(y^n\right|x)$ is artificially generated.

4.1. The I.I.D. Case with One Training Sample per Label

In the following examples, we assume that the classifiers have access to only one training feature vector for each label, the elements of the feature vectors are generated i.i.d., and the alphabet size of the feature vector, $\left|\mathcal{Y}\right|$, is fixed.

In Figure 4 and Figure 5, we compare the error probability of the proposed classifier with the naive Bayes classifier and the KNN algorithm for the case when $\left|\mathcal{Y}\right|=6$ and $\left|\mathcal{Y}\right|=20$, respectively. In both examples, we have two different labels, i.e., $\left|\mathcal{X}\right|=2$. As a result, we have two different probability distributions $p_{{}_{Y^n|X_1}}\left(y^n\right|x_1)$ and $p_{{}_{Y^n|X_2}}\left(y^n\right|x_2)$. The probability distributions $p_{{}_{Y^n|X_1}}\left(y^n\right|x_1)$ and $p_{{}_{Y^n|X_2}}\left(y^n\right|x_2)$ are randomly generated as follows. We first generate two random vectors of length 6 and length 20 for Figure 4 and Figure 5, respectively, where the elements of these vectors are drawn independently from a uniform probability distribution. Then we normalize these vectors such that the sum of their elements is equal to one. These two normalized randomly generated vectors then represent the two probability distributions $p_{{}_{Y_i|X_1}}\left(y_i\right|x_1)=p_{{}_{Y|X_1}}\left(y\right|x_1)$ and $p_{{}_{Y_i|X_2}}\left(y_i\right|x_2)=p_{{}_{Y|X_2}}\left(y\right|x_2)$, $\forall i$. Then, $p_{{}_{Y^n|X_k}}\left(y^n\right|x_k)$ is obtained as $p_{{}_{Y^n|X_k}}\left(y^n\right|x_k)={\prod }_{i=1}^n{p}_{{}_{Y_i|X_k}}\left(y_i\right|x_k)$, for $k=1,2$. The simulation is carried out as follows. For each n, we generate one training vector for each label, using the aforementioned probability distributions. Then, as test samples, we generate 1000 feature vectors for each label and pass these feature vectors through our proposed classifier, the naive Bayes classifier, and the KNN algorithm, and compute the errors. The length of the feature vector n is varied from $n=1$ to $n=100$. We repeat the simulation 5000 times and then plot the error probability. Figure 4 and Figure 5 show that the proposed classifier outperforms both the naive Bayes classification and KNN. The main reason for this performance gain is because when only one training vector per label is available, the proposed classifier is more resilient to errors than the naive Bayes classifier, whereas the KNN algorithm has very poor performance because of the “curse of dimensionality”. Specifically, the naive Bayes classifier cannot perform an accurate classification for small n compared to $\left|\mathcal{Y}\right|$ since the chance that an alphabet will not be present in one of the training feature vectors is close to 1. On the other hand, the KNN algorithm cannot perform an accurate classification for large n since the dimension of the input feature vector becomes much larger than the training data and the “curse of dimensionality” occurs.

In Figure 6, we compare the performance of the proposed classifier for different values of r when $\left|\mathcal{Y}\right|=6$ with the derived upper bounds. As can be seen, for this example, the derived theoretical upper bounds have similar slope as the exact error probabilities. Moreover, we can see that for this example, the optimal r is $r=1$. However, this is not always the case and it depends on $p_{{}_{Y^n|X_k}}\left(y^n\right|x_k)$, $\left|\mathcal{Y}\right|$, and $\left|\mathcal{X}\right|$.

4.2. The Overlapping I.Non-I.D. Case with One Training Sample per Label

In this example, we consider the i.non-i.d. case where the probability distributions $p_{{}_i}\left(y_i\right|x_k)$ are overlapping for all i, as shown in Figure 7. The small orthogonal lines on the x-axis in Figure 7 represent alphabets, i.e., the elements in $\mathcal{Y}$, and the probability of occurrence of an alphabet $y_i$ is equal to the intersection between the corresponding orthogonal line to the represented probability distribution $p_{{}_i}\left(y_i\right|x_k)$ for $k=1,2$. By “overlapping”, we mean the following. Let ${\mathcal{Y}}_v$ and ${\mathcal{Y}}_u$ denote the set of outputs generated by $p_{{}_v}\left(y_v\right|x_k)$ and $p_{{}_u}\left(y_u\right|x_k)$, respectively. If for any v and u, ${\mathcal{Y}}_v\cap {\mathcal{Y}}_u\ne \varnothing$ holds, we say that the output alphabets are overlapping.

To demonstrate the performance of our proposed classifier in the overlapping case, we assume that we have two different labels, $\mathcal{X}=\{x_1,x_2\}$, where the corresponding conditional probability distributions $p_{{}_i}\left(y_i\right|x_1)$ and $p_{{}_i}\left(y_i\right|x_2)$ are obtained as follows. For a given n, let $\mathcal{Y}=\left\{-n,-n+1,\dots ,0,\dots ,n-1,n\right\}$ be the set of all alphabets. Note that the size of $\mathcal{Y}$ grows with n. Moreover, let ${\mathbf{u}}_i$ and ${\mathbf{v}}_i$$(1\le i\le n)$ be vectors of length $2n+1$, given by

$$\begin{array}{cc}\hfill {\mathbf{u}}_i& =\left[0,\dots ,0,{\displaystyle \frac{1}{i(i+1)}},{\displaystyle \frac{2}{i(i+1)}},\dots ,{\displaystyle \frac{i}{i(i+1)}},{\displaystyle \frac{i+1}{i(i+1)}},{\displaystyle \frac{i}{i(i+1)}},\dots ,{\displaystyle \frac{1}{i(i+1)}},0,\dots ,0\right],\hfill \end{array}$$

(50)

$$\begin{array}{cc}\hfill {\mathbf{v}}_i& =\left[0,\dots ,0,{\displaystyle \frac{1}{i(i+1)}},{\displaystyle \frac{1}{i(i+1)}},\dots ,{\displaystyle \frac{1}{i(i+1)}},{\displaystyle \frac{1}{i(i+1)}},0,\dots ,0\right].\hfill \end{array}$$

(51)

The number of zeros in each side of the vectors ${\mathbf{u}}_i$ and ${\mathbf{v}}_i$ is $(n-i)$. To generate a feature vector from label $x_1\left(x_2\right)$, we generate the vector $y^n=(y_1,y_2,\dots ,y_n)$, where $y_k$ takes values from the set $\mathcal{Y}$, with a probability distribution $p_{{}_i}\left(y_i\right|x_1)={\mathbf{u}}_i\left(1+2(n+y_i)\right)$$\left(p_{{}_i}\left(y_i\right|x_2)={\mathbf{v}}_i\left(1+2(n+y_i)\right)\right)$.

The simulation is carried out as follows. For each n, we generate one training feature vector for each label. Then, we generate 1000 feature vectors for each label and pass them through our proposed classifier, the naive Bayes classifier, and the KNN algorithm and calculate the error probability. We change the length of the feature vector from $n=1$ to $n=100$ and repeat the simulation 1000 times and then plot the error probability.

As shown in Figure 8, there is a huge difference between the performance of the two benchmark classifiers and the proposed classifier. The error probability of the naive Bayes classifier is almost $0.5$ for all shown values of n as it is susceptible to the problem of unseen alphabets in the training vectors. The error probability of the KNN classifier is also almost $0.5$ for $n>20$ as it is susceptible to the “curse of dimensionality”. However, the error probability of our proposed classifier continuously decays as n increases.

In Figure 9, we run the same experiments as in Figure 8 but with $T=100$, i.e., 100 training feature vectors per label. As can be seen from Figure 9, the performance of the proposed classifier is better than the naive Bayes classifier, for $n>15$. Since $\left|\mathcal{Y}\right|=2n+1$, for small values of n, the naive Bayes classifier has access to many training samples and, thereby, its performance is very close to the case when the probability distribution $p_{{}_{Y^n|X}}\left(y^n\right|x)$ is known, i.e., to the maximum-likelihood classifier, and hence it has the optimal performance. As n increases, the number of alphabets rises, i.e., $\left|\mathcal{Y}\right|$ rises, and due to the aforementioned issue of the naive Bayes classifier with unseen alphabets, our proposed classifier performs much better classification than the naive Bayes classifier. Furthermore, note that the error probability of our proposed classifier decays exponentially as n increases which is not the case with the naive Bayes classifier. Moreover, Figure 9 also shows the theoretical upper bound on the error probability we derived in (11).

4.3. The Non-Overlapping I.Non-I.D. Case with One Training Sample for Each Label

In this example, we consider the i.non-i.d. case where the probability distributions $p_{{}_j}\left(y_j\right|x_i)$ are non-overlapping for all j as shown in Figure 10, where we defined “overlapping” in Section 4.2. Hence, we test the other extreme in terms of possible distribution of the elements in the feature vectors $Y^n$.

To demonstrate the performance of our proposed classifier in the non-overlapping case, we assume that we have two different labels $\mathcal{X}=\{x_1,x_2\}$, the corresponding conditional probability distributions $p_{{}_i}\left(y_i\right|x_1)$ and $p_{{}_i}\left(y_i\right|x_2)$ are obtained as follows. For a given n, let $\mathcal{Y}=\left\{1,2,3,\dots ,{(n+1)}^2-1\right\}$ be the set of all alphabets of the element in the feature vectors. Note again that the size of $\mathcal{Y}$ grows with n. in addition, let ${\mathbf{u}}_i$ and ${\mathbf{v}}_i$ for $(1\le i\le n)$, be vectors of length ${(n+1)}^2-1$, given by

$$\begin{array}{cc}\hfill {\mathbf{u}}_i& =\left[0,\dots ,0,{\displaystyle \frac{1}{i(i+1)}},{\displaystyle \frac{2}{i(i+1)}},\dots ,{\displaystyle \frac{i}{i(i+1)}},{\displaystyle \frac{i+1}{i(i+1)}},{\displaystyle \frac{i}{i(i+1)}},\dots ,{\displaystyle \frac{1}{i(i+1)}},0,\dots ,0\right],\hfill \end{array}$$

(52)

$$\begin{array}{cc}\hfill {\mathbf{v}}_i& =\left[0,\dots ,0,{\displaystyle \frac{1}{i(i+1)}},{\displaystyle \frac{1}{i(i+1)}},\dots ,{\displaystyle \frac{1}{i(i+1)}},{\displaystyle \frac{1}{i(i+1)}},0,\dots ,0\right].\hfill \end{array}$$

(53)

The number of zeros in the left-hand sides of ${\mathbf{u}}_i$ and ${\mathbf{v}}_i$ is $i^2-1$. To generate a feature vector from the label $x_1\left(x_2\right)$, we generate the vector $y^n=(y_1,y_2,\dots ,y_n)$, where $y_k$ take values from the set $\mathcal{Y}$, with probability distribution $p_{{}_i}\left(y_i\right|x_1)={\mathbf{u}}_i\left(y_i\right)$$\left(p_{{}_i}\left(y_i\right|x_2)={\mathbf{v}}_i\left(y_i\right)\right)$.

The simulation is carried out as follows. For each n, we generate one training feature vector for each label. Then we generate 250 feature vectors for each label and pass it through our proposed classifier, the naive Bayes classifier and KNN and calculate the error probabilities. We change the length of the vector from 1 to 80 and repeat the simulation 250 times and then plot the error probability. As shown in Figure 11, there is a huge difference between the performance of the proposed classifier and the two benchmark classifiers. The error probability of the naive Bayes classifier is almost $0.5$ for all shown values of n as it is susceptible to the issue with unseen alphabets in the training feature vector. The error probability of the KNN classifier is almost $0.5$ for all shown values of $n>30$ as it becomes susceptible to the “curse of dimensionality”. However, the error probability of our proposed classifier still decays continuously as n increases.

Note that, in our numerical examples, we compared our algorithm with the benchmark schemes on two extreme cases of i.non-i.d. vectors, referred to as “overlapping” and “non-overlapping”. Any other i.non-i.d. vector can be represented as a combination of the “overlapping” and “non-overlapping” vectors. Since our algorithm works better than the benchmark schemes for small t on both these cases, it will work better than the benchmark schemes on any combination between “overlapping” and “non-overlapping” vectors, i.e., for any other i.non-i.d. vectors.

5. Conclusions

In this paper, we proposed a supervised classification algorithm that assigns labels to input feature vectors with independent but non-identically distributed elements, a statistical property found in practice. We proved that the proposed classifier is asymptotically optimal since the error probability moves to zero as the length of the input feature vectors grows. We showed that this asymptotic optimality is achievable even when one training feature vector per label is available. In the numerical examples, we compared the proposed classifier with the naive Bayes classifier and the KNN algorithm. Our numerical results show that the proposed classifier outperforms the benchmark classifiers when the number of training data is small and the length of the input feature vectors is sufficiency large.