High-Dimensional Separability for One- and Few-Shot Learning

Abstract

This work is driven by a practical question: corrections of Artificial Intelligence (AI) errors. These corrections should be quick and non-iterative. To solve this problem without modification of a legacy AI system, we propose special ‘external’ devices, correctors. Elementary correctors consist of two parts, a classifier that separates the situations with high risk of error from the situations in which the legacy AI system works well and a new decision that should be recommended for situations with potential errors. Input signals for the correctors can be the inputs of the legacy AI system, its internal signals, and outputs. If the intrinsic dimensionality of data is high enough then the classifiers for correction of small number of errors can be very simple. According to the blessing of dimensionality effects, even simple and robust Fisher’s discriminants can be used for one-shot learning of AI correctors. Stochastic separation theorems provide the mathematical basis for this one-short learning. However, as the number of correctors needed grows, the cluster structure of data becomes important and a new family of stochastic separation theorems is required. We refuse the classical hypothesis of the regularity of the data distribution and assume that the data can have a rich fine-grained structure with many clusters and corresponding peaks in the probability density. New stochastic separation theorems for data with fine-grained structure are formulated and proved. On the basis of these theorems, the multi-correctors for granular data are proposed. The advantages of the multi-corrector technology were demonstrated by examples of correcting errors and learning new classes of objects by a deep convolutional neural network on the CIFAR-10 dataset. The key problems of the non-classical high-dimensional data analysis are reviewed together with the basic preprocessing steps including the correlation transformation, supervised Principal Component Analysis (PCA), semi-supervised PCA, transfer component analysis, and new domain adaptation PCA.

1. Introduction

1.1. AI Errors and Correctors

The main driver of our research is the problem of Artificial Intelligence (AI) errors and their correction: all AI systems sometimes make errors and will make errors in the future. These errors must be detected and corrected immediately and locally in the networks of AI systems. If we do not solve this problem, then a new AI winter will come. Recall that the previous AI winters came after the hype peaks of inflated expectations and bold advertising: the general overconfidence of experts was a typical symptom of inflated expectations before the winter came [1]. “It was recognised that AI advocates were called to account for making promises that they could not fulfill. There was disillusionment” [2] and “significant investments were made, but real breakthroughs were very rare and both time and patience ran out…” [3]. A richer picture of the AI winter, including the dynamics of government funding, the motivation of AI researchers, the transfer of AI to industry, and hardware development, was sketched in [4]. The winter may come back and we better be ready [5]. For the detailed discussion of AI trust, limitations, conflation, and hype we refer to the analytic review of Bowman and Grindrod [6].

Gartner’s Hype Cycle is a convenient tool to represent of R&D trends. According to Gartner [7], the data-driven Artificial Intelligence (AI) has already left the Peak of Inflated Expectation and is descending into the Trough of Disillusionment. If we look at Gartner’s Hype Cycle in more detail, we will see that Machine Learning and Deep Learning are going down. Explainable AI joined them in 2020, but Responsible AI, Generative AI, and Self-Supervising Learning are still climbing up the peak [8].

According to Gartner’s Hype cycle model, the Trough of Disillusionment will turn into the Slope of Enlightenment that leads to the Plateau of Productivity. The modern Peak and Trough are not the first in the history of AI. Surprisingly, previous troughs (AI winters) did not turn into the performance plateaus. Instead they went through new peaks of hype and inflated expectations (Figure 1) [9].

What pushes the AI downhill now? Is it the same problem that pushed the AI down previous slopes decades ago? Data driven systems “will inevitably and unavoidably generate errors”, and this is of great concern [10]. The main problem for the widespread use of AI around the world is unexpected errors in real-life applications:

• The mistakes can be dangerous;
• Usually, it remains unclear who is responsible for them;
• The types of errors are numerous and often unpredictable;
• The real world is not a good i.i.d. (independent identically distributed) sample;
• We cannot rely on a statistical estimate of the probability of errors in real life.

The hypothesis of i.i.d. data samples is very popular in machine learning theory. It means that there exists a probability measure on the data space and the data points are drawn from the space according to this measure independently [11]. It is worth mentioning that the data point for supervising learning includes both the input and the desired output and the probability is defined on the input × output space. Existence and stationarity of the probability distribution in real life is a very strong hypothesis. To weaken this assumption, many auxiliary concepts have been developed, such as concept drift. Nevertheless, i.i.d samples remain a central assumption of statistical learning theory: the dataset is presumed to be an i.i.d. random sample drawn from a probability distribution [12].

Fundamental origins of AI errors could be different. Of course, they include software errors, unexpected human behaviour, and non-intended use as well as many other possible reasons. Nevertheless, the universal cause of errors is uncertainty in training data and in training process. The real world possibilities are not covered by the dataset.

The mistakes should be corrected. The systematic retraining of a big AI system seems to be rarely possible (here and below, AI skill means the ability to correctly solve a group of similar tasks):

• To preserve existing skills we must use the full set of training data;
• This approach requires significant computational resources for each error;
• However, new errors may appear in the course of retraining;
• The preservation of existing skills is not guaranteed;
• The probability of damage to skills is a priori unknown.

Therefore, quick non-iterative methods which are free from the disadvantages listed above are required. This is the main challenge for the one- and few-shot learning methods.

To provide fast error correction, we must consider developing correctors, external devices that complement legacy Artificial Intelligence systems, diagnose the risk of error, and correct errors. The original AI system remains a part of the extended ‘system + corrector’ complex. Therefore, the correction is reversible, and the original system can always be extracted from the augmented AI complex. Correctors have two different functions: (1) they should recognise potential errors and (2) provide corrected outputs for situations with potential errors. The idealised scheme of a legacy AI system augmented with an elementary corrector is presented in Figure 2. Here, the legacy AI system is represented as a transformation that maps the input signals into internal signals and then into output signals: $inputs\to internal\to outputs$. The elementary corrector takes all these signals as inputs and makes a decision about correction (see Figure 2).

The universal part of the AI corrector is a classifier that should separate situations with erroneous behaviour from normal operation. It is a binary classifier for all types of AI. The generalisation ability of this classifier is its ability to recognise errors that it had never seen before. The training set for corrector consists of a collection of situations with normal operation of the legacy AI system (the ‘normal’ class) and a set of labelled errors. The detection and labelling of errors for training correctors can be performed by various methods, which include human inspection, decisions of other AI systems of their committees, signals of success or failure from the outer world, and other possibilities that are outside the scope of our work.

We can usually expect that a normal class of error-free operations includes many more examples than a set of labelled errors. Moreover, even the situation with one newly labelled error is of considerable interest. All the stochastic separation theorems were invented to develop the one- of few-shot learning rules for the binary error/normal operation classifiers.

A specific component of the AI corrector is the modified decision rule (the ‘correction’ itself). Of course, the general theory and algorithms are focused on the universal part of the correctors. For many classical families of data distributions, it is proved that the well-known Fisher discriminant is surprisingly a powerful tool for constructing correctors if the dimension of the data space is sufficiently high (most results of this type are collected in [13]). This is proven for a wide class of distributions, including log-concave distributions, their convex combinations, and product distributions with bounded support.

In this article, we refuse the classical hypothesis of the regularity of the data distribution and assume that the data can have a rich fine-grained structure with many clusters and corresponding peaks in the probability density. Moreover, the very notion of probability distribution in high dimensions may sometimes create more questions than answers. Therefore, after developing new stochastic separation theorems for data with fine-grained clusters, we present a possibility to substitute the probabilistic approach to foundations of the theory by more robust methods of functional analysis with the limit transition to infinite dimension.

The idea of the presence of fine-grained structures in data seems to be very natural and universal: the observable world consists of things. The data points represent situations. The qualitative difference between situations is in existence/absence of notable things there.

Many approaches to machine learning are based on the correction of errors. A well-known example is the backpropagation of errors, from the classical perceptron algorithms [14] to modern deep learning [15]. The need for correction of AI errors has been discussed in the reinforcement learning literature. In the area of model-based reinforcement learning, the motivation stems from inevitable discrepancies between the models of environments used for training an agent and the reality this agent operates in. In order to address the problem, a meta-learning approach, Hallucinated Replay, was suggested in [16]. In this approach, the agent is trained to predict correct states of the real environment from states generated by the model [17]. Formal justifications and performance bounds for Hallucinated Replay were established in [18]. Notwithstanding these successful developments, we note that the settings to which such strategies apply are largely Markov Decision Processes. Their practical relevance is therefore constrained by dimensionality of the system’s state. In high dimension, the costs of exploring all states grows exponentially with dimension and, as a result, alternative approaches are needed. Most error correction algorithms use large training sets to prevent new errors from being created in situations where the system was operating normally. These algorithms are iterative in nature. On the contrary, the corrector technology in high dimension aims at non-iterative one- or few–shot error corrections.

1.2. One- and Few-Shot Learning

A set of labelled errors is needed for creation of AI corrector. If we have such a set, then the main problem is the fast non-iterative training of classifiers that separate situations with a high risk of error from situations in which the legacy AI system works well. Thus, the corrector problem includes the one- or few-shot learning problem, and one class is presented by a relatively small sample of errors.

Learning new concepts rapidly from small low-sample data is a key challenge in machine learning [19]. Despite the widespread perception of neural networks as monstrous giant systems, whose iterative training requires a lot of time and resources, mounting empirical evidence points to numerous successful examples of learning from modestly-sized datasets [20]. Moreover, training with one or several shots is possible. By definition, which has already become classic, “one-shot learning”, consists of learning a class from a single labelled example [19]. In “few-shot learning” a classifier must generalise to new classes not seen in the training set, given only a small number of examples of each new class [21].

Several modern approaches to enabling this type of learning require preliminary training tasks that are similar but not fully identical to new tasks to be learned. After such preliminary training the system acquires new meta-skills: it can now learn new tasks, which are not crucially different from the previous ones, without the need for large training sets and training time. This heuristic is utilised in various constructions of one- and few-shot learning algorithms [22,23]. Similar meta-skills and learnability can also be gained through previous experience of solving various relevant problems or an appropriately organised meta-learning [21,24].

In general, a large body of one- and few-shot learning algorithms is based on combinations of a reasonable preparatory learning that aims to increase learnability and create meta-skills and simple learning routines facilitating learning from small number of examples after this propaedeutics. These simple methods create appropriate latent feature spaces for the trained models which are preconditioned for the task of learning from few or single examples. Typically, a copy of the same pretrained system is used for different one- and few-shot learning tasks. Nevertheless, plenty of approaches are applicable to few-shot minor modifications of the features using new tasks.

Despite a large number of different algorithms implementing one- and few-shot learning schemes have been proposed to date, effectiveness of one- and few-shot simple methods is based on either significant dimensionality reductions or the blessing of dimensionality effects [25,26].

A significant reduction in dimensionality means that several features have been extracted that are already sufficient for the purposes of learning. Thereafter, a well-elaborated library of efficient lower-dimensional statistical learning methods can be applied to solve new problems using the same features.

The blessing of dimensionality is a relatively new idea [27,28,29,30]. It means that simple classical techniques like linear Fisher’s discriminants become unexpectedly powerful in high dimensions under some mild assumptions about regularity of probability distributions [31,32,33]. These assumptions typically require absence of extremely dense lumps of data, which can be defined as areas with relatively low volume but unexpectedly high probability (for more detail we refer to [13]). These lumps correspond to narrow but high peaks of probability density.

If a dataset consists of k such lumps then, for moderate values of k, this can be considered as a special case of dimensionality reduction. The centres of clusters are considered as ‘principal points’ to stress the analogy with principal components [34,35]. Such a clustered structure in system’s latent space may emerge in the course of preparatory learning: images of data points in the latent space ‘attract similar and repulse dissimilar’ data points.

The one- and few-shot learning can be organised in all three situations described above:

• If the feature space is effectively reduced, then the challenge of large dataset can be mitigated and we can rely on classical linear or non-linear methods of statistical learning.
• In the situation of ‘blessing of dimensionality’, with sufficiently regular probability distribution in high dimensions, the simple linear (or kernel [36]) one- and few-shot methods become effective [13,26,33].
• If the data points in the latent space form dense clusters, then position of new data with respect to these clusters can be utilised for solving new tasks. We can also expect that new data may introduce new clusters, but persistence of the cluster structure seems to be important. The clusters themselves can be distributed in a multidimensional feature space. This is the novel and more general setting we are going to focus on below in Section 3.

There is a rich set of tools for dimensionality reduction. It includes the classical prototype, principal component analysis (PCA) (see, [35,37] and Appendix A.2), and many generalisations, from principal manifolds [38] and kernel PCA [39] to principal graphs [35,40] and autoencoders [41,42]. We briefly describe some of these elementary tools in the context of data preprocessing (Appendix A), but the detailed analysis of dimensionality reduction is out of the main scope of the paper.

In a series of previous works, we focused on the second item [13,25,30,31,32,33,43]. The blessing of dimensionality effects that make the one- and few-shot learning possible for regular distributions of data are based on the stochastic separation theorems. All these theorems have a similar structure: for large dimensions, even in an exponentially large (relatively to the dimension) set of points, each point is separable from the rest by a linear functional, which is given by a simple explicit formula. These blessings of dimensionality phenomena are closely connected to the concentration of measure [44,45,46,47,48] and to the various versions of the central limit theorem in probability theory [49]. Of course, there remain open questions about sharp estimates for some distribution classes, but the general picture seems to be clear now.

In this work, we focus mainly on the third point and explore the blessings of dimensionality and related methods of one- and few-shot learning for multidimensional data with rich cluster structure. Such datasets cannot be described by regular probability densities with a priori bounded Lipschitz constants. Even more general assumptions about absence of sets with relatively small volume but relatively high probability fail. We believe that this option is especially important for applications.

1.3. Bibliographic Comments

All references presented in the paper matter. However, a separate quick guide to the bibliographic references about the main ideas may be helpful:

• Blessing of dimensionality. In data analysis, the idea of blessing of dimensionality was formulated by Kainen [27]. Donoho considered the effects of the dimensionality blessing to be the main direction of the development of modern data science [28]. The mathematical backgrounds of blessing of dimensionality are in the measure concentration phenomena. The same phenomena form the background of statistical physics (Gibbs, Einstein, Khinchin—see the review [25]). Two modern books include most of the classical results and many new achievements of concentration of measure phenomena needed in data science [44,45] (but they do not include new stochastic separation theorems). Links between the blessing of dimensionality and the classical central limit theorems are recently discussed in [49].
• One-shot and few-shot learning. This is a new direction in machine learning. Two papers give a nice introduction in this area [19,20]. Stochastic separation theorems explained ubiquity of one- and few-shot learning [26].
• AI errors. The problem of AI errors is widely recognised. This is becoming the most important issue of serious concern when trying to use AI in real life. The Council of Europe Study report [10] demonstrates that the inevitability of errors of data-driven AI is now a big problem for society. Many discouraging examples of such errors are published [50,51], collected in reviews [52], and accumulated in a special database, Artificial Intelligence Incident Database (AIID) [53,54]. The research interest to this problem increases as an answer of the scientific community to the request of AI users. There are several fundamental origins of AI errors including uncertainty in training data, uncertainty in training process, and uncertainty of real world—reality can deviate significantly from the fitted model. The systematic manifestations of these deviations are known as concept drift or model degradation phenomena [55].
• AI correctors. The idea of elementary corrector together with statistical foundations was proposed in [30]. First stochastic separation theorems were proved for several simple data distributions (uniform distributions in a ball and product distributions with bounded support) [31]. The collection of results for many practically important classes of distributions, including convex combinations of log-concave distributions is presented in [13]. Kernel version of stochastic separation theorem was proved [36]. The stochastic separation theorems were used for development of correctors tested on various data and problems, from the straightforward correction of errors [32] to knowledge transfer between AI systems [56].
• Data compactness. This is an old and celebrated idea proposed by Braverman in early 1960s [57]. Several methods of measurement compactness of data clouds were invented [58]. The possibility to replace data points by compacta in training of neural networks was discussed [59]. Besides theoretical backgrounds of AI and data mining, data compactness was used for unsupervised outlier detection in high dimensions [60] and other practical needs.

1.4. The Structure of the Paper

In Section 2 we briefly discuss the phenomenon of post-classical data. We begin with Donoho’s definition of post-classical data analysis problems, where the number of attributes is greater than the number of data points [28]. Then we discuss alternative definitions and end with a real case study that started with a dataset in the dimension $5\times {10}^5$ and ended with five features that give an effective solution to the initial classification problem.

Section 3 includes the main theoretical results of the paper, the stochastic separation theorems for the data distributions with fine-grained structure. For these theorems, we model clusters by geometric bodies (balls or ellipsoids) and work with distributions of ellipsoids in high dimensions. The hierarchical structure of data universe is introduced where each data cluster has a granular internal structure, etc. Separation theorems in infinite-dimensional limits are proven under assumptions of compact embedding of patterns into data space.

In Section 4, the algorithms (multi-correctors) for corrections of AI errors that work for multiple clusters of error are developed and tested. For such datasets, several elementary correctors and a dispatcher are required, which distributes situations for analysis to the most appropriate elementary corrector. In multi-corrector, each elementary corrector separates its own area of high-risk error situations and contains an alternative rule for making decisions in situations from this area. The input signals of the correctors are the input, internal, and output signals of the AI system to be corrected as well as any other available attributes of the situation. The system of correctors is controlled by a dispatcher, which is formed on the basis of a cluster analysis of errors and distributes the situations specified by the signal vectors between elementary correctors for evaluation and, if necessary, correction.

Multi-correctors are tested on the CIFAR-10 dataset. In this case study, we will illustrate how ‘clustered’ or ‘granular universes’ can arise in real data and show how a granular representation based multi-correctors structure can be used in challenging machine learning and Artificial Intelligence problems. These problems include learning new classes of data in legacy deep learning AI models and predicting AI errors. We present simple algorithms and workflows which can be used to solve these challenging tasks circumventing the needs for computationally expensive retraining. We also illustrate potential technical pitfalls and dichotomies requiring additional attention from the algorithms’ users and designers.

In conclusion, we briefly review the results (Section 5). Discussion (Section 6) aims at explaining the main message: the success or failure of many machine learning algorithms, the possibility of meta-learning, and opportunities to learn continuously from relatively small data samples depend on the world structure. The capability of representing a real world situation as a collection of things with some features (properties) and relationships between these entities is the fundamental basis of knowledge of both humans and AI.

Appendices include auxiliary mathematical results and relevant technical information. In particular, in Appendix A we discuss the following preprocessing operations that may move the dataset from the postclassical area:

• Correlation transformation that maps the dataspace into cross-correlation space between data samples:
• PCA;
• Supervised PCA;
• Semi-supervised PCA;
• Transfer Component Analysis (TCA);
• The novel expectation-maximization Domain Adaptation PCA (‘DAPCA’).

2. Postclassical Data

High-dimensional post-classical world was defined in [28] by the inequality

$$\text{The number of attributes}d\gg \text{The number of examples}N.$$

(1)

This post-classical world is different from the ‘classical world’, where we can consider infinite growth of the sample size for the given number of attributes. The classical statistical methodology was developed for the classical world based on the assumption of

$$d<N\mathrm{and}N\to \infty .$$

Thus, the classical statistical learning theory is mostly useless in the multidimensional post-classical world. These results all fail if $d>N$. The $d>N$ case is not anomalous for the modern big data problems. It is the generic case: both the sample size and the number of attributes grow, but in many important cases the number of attributes grows faster than the number of labelled examples [28].

High-dimensional effects of the curse and blessing of dimensionality appear in a much wider area than specified by the inequality (1). A typical example gives the penomenon of quasiorthogonal dimension [61,62,63]: for a given $\epsilon >0$ and $\vartheta >0$ (assumed small) a random set of N vectors ${\mathit{x}}_i$ on a high-dimensional unit d-dimensional sphere satisfies the inequality

$$|({\mathit{x}}_i,{\mathit{x}}_j)|<\epsilon$$

for all $i\ne j$ with probability $p>1-\vartheta$ when $N<aexp(bd)$ and a and b depend on $\epsilon$ and $\vartheta$ only. This means that the quasiorthogonal dimension of an Euclidean space grows exponentially with dimension d. Such effects are important in machine learning [63]. Therefore, the Donoho boundary should be modified: the postclassical effects appear in high dimension when

$$d\gg logN.$$

(2)

The two different definitions of postclassical area, (1) and (2), are illustrated in Figure 3a.

The definition of the postclassical data world needs one more comment. The inequalities (1) and (2) used the number of attributes as the equivalent of the dimension of the data space. Behind this approach is the hypothesis that there is no strong dependency between attributes. In the real situations, the data dimensionality can be much less that the number of attributes, for example, in the case of the strong multicollinearity. If, say, the data are located along a straight line then for most approaches the dimension of the dataset is 1 and the value of d does not matter. Therefore, the definition (2) of the postclassical world needs to be modified further with the dimension of the dataset, $dim(DataSet)$ instead of d:

$$dim(DataSet)\gg logN.$$

(3)

There are many various definitions of data dimensionality, see a brief review in [64,65]. For all of them, we can assume that $dim(DataSet)<N$ and $dim(DataSet)\le d$ (see Figure 3b). It may happen that the intrinsic dimensionality of the datasets is surprisingly low and variables have hidden interdependencies. The structure of multidimensional data point clouds can have globally complicated organisation which is sometimes difficult to represent with regular mathematical objects (such as manifolds) [65,66].

The postclassical world effects include the blessing and curse of dimensionality. The blessing and curse are based on the concentration of measure phenomena [44,46,47,48] and are, in that sense, two sides of the same coin [33,43].

It may be possible to resolve the difficulties with the data analysis in Donoho area by adequate preprocessing described in Appendix A. Consider an example of successful descent from data dimension $5\times {10}^5$ to five-dimensional decision space [67]. The problem was to develop an ‘optical tongue’ that recognises toxicity of various substances. The optical assay included a mixture of sensitive fluorescent dyes and human skin cells. They generate fluorescence spectra distinctive for particular conditions. The system produced characteristic response to toxic chemicals.

Two fluorescence images were received for each chemical: with growing cells and without them (control). The images were $511\times 511$ arrays of fluorescence intensities as functions of emission and excitation. The dataset included 34 irritating and 28 non-irritating (Non-IRR) compounds (62 chemicals in total). The input data vector for each compound had dimension 522,242. This dataset belonged to the Donoho area.

After selection of a training set, each fluorescence image was represented by the vector of its correlation coefficients with the images from the training set. The size of the training set was 43 examples (with several randomised training set/test set splittings) or 61 example (for leave one out cross-validation). After that, the data matrix was $43\times 43$ or $61\times 61$ symmetric matrix. Then the classical PCA was applied with the standard selection of the number of components by Kaiser rule that returned five components. Finally, in the reduced space the classical classification algorithms were applied (kNN, decision tree, linear discriminant, and other). Both sensitivity and specificity of the 3NN classifiers with adaptive distance and of decision tree exceeded 90% in leave one out cross-validation.

This case study demonstrates that simple preprocessing can sometimes return postclassical data to the classical domain. However, in truly multidimensional datasets, this approach can fail due to the quasiorthogonality effect [61,62,63]: centralised random vectors in large dimensions are nearly orthogonal under very broad assumptions, and the matrix of empirical correlation coefficients with high probability is often close to the identity matrix even for exponentially large data samples [63].

3. Stochastic Separation for Fine-Grained Distributions

3.1. Fisher Separability

Recall that the classical Fisher discriminant between two classes with means ${\mathit{\mu }}_1$ and ${\mathit{\mu }}_2$ is separation of the classes by a hyperplane orthogonal to ${\mathit{\mu }}_1-{\mathit{\mu }}_2$ in the inner product

$$\langle \mathit{x},\mathit{y}\rangle =(\mathit{x},{\mathit{S}}^{-1}\mathit{y}),$$

(4)

where $(·,·)$ is the standard inner product and $\mathit{S}$ is the average (or the weighted average) of the sample covariance matrix of these two classes.

Let the dataset be preprocessed. In particular, we assume that it is centralised, normalised, and approximately whitened. In this case, we use in the definition of Fisher’s discriminant the standard inner product instead of $\langle ·,·\rangle$.

Definition 1.

A point $\mathit{x}$ is Fisher separable from a set $\mathbf{Y}\subset {\mathbb{R}}^n$ with threshold $\alpha \in (0,1]$, or α-Fisher separable in short, if inequality

$$\alpha (\mathit{x},\mathit{x})\ge (\mathit{x},\mathit{y}),$$

(5)

holds for all $\mathit{y}\in \mathbf{Y}$.

Definition 2.

A finite set $\mathbf{Y}\subset {\mathbb{R}}^n$ is Fisher separable with threshold $\alpha \in (0,1]$, or α-Fisher separable in short, if inequality (5) holds for all $\mathit{x},\mathit{y}\in \mathbf{Y}$ such that $\mathit{x}\ne \mathit{y}$.

Separation of points by simple and explicit inner products (5) is, from the practical point of view, more convenient than general linear separability that can be provided by support vector machines, for example. Of course, linear separability is more general than Fisher separability. This is obvious from the everyday low-dimensional experience, but in high dimensions Fisher separability becomes a generic phenomenon [30,31].

Theorem 1 below is a prototype of most stochastic separation theorems. Two heuristic conditions for the probability distribution of data points are used in the stochastic separation theorems:

• The probability distribution has no heavy tails;
• The sets of relatively small volume should not have large probability.

These conditions are not necessary and could be relaxed [13].

In the following Theorem 1 [32] the absence of heavy tails is formalised as the tail cut: the support of the distribution is a subset of the n-dimensional unit ball ${\mathbb{B}}_n$. The absence of the sets of small volume but large probability is formalised in this theorem by the inequality:

$$\rho (\mathit{x})<\frac{C}{r^n{V}_n({\mathbb{B}}_n)},$$

(6)

where $\rho$ is the distribution density, $C>0$ is an arbitrary constant, $V_n({\mathbb{B}}_n)$ is the volume of the ball ${\mathbb{B}}_n$ and $1>r>1/(2\alpha )$. This inequality guarantees that the probability measure of each ball with the radius $R\le 1/(2\alpha )$ decays for $n\to \infty$ in a geometric progression with denominator $R/r$. Condition $1>r>1/(2\alpha )$ is possible only if $\alpha >0.5$, hence, in Theorem 1 we assume $\alpha \in (0.5,1]$.

Theorem 1

([32]). Let $1\ge \alpha >1/2$, $1>r>1/(2\alpha )$, $1>\delta >0$, $Y\subset {\mathbb{B}}_n$ be a finite set, ${|Y|<\delta (2r\alpha )}^n/C$ and $\mathit{x}$ be a randomly chosen point from a distribution in the unit ball with the bounded probability density $\rho (\mathit{x})$. Assume that $\rho (\mathit{x})$ satisfies inequality (6). Then with probability $p>1-\delta$ point $\mathit{x}$ is Fisher-separable from Y with threshold α (5).

Proof. 

For a given $\mathit{y}$, the set of such $\mathit{x}$ that $\mathit{x}$ is not $\alpha$-Fisher separable from $\mathit{y}$ by inequality (5) is a ball given by inequality (5)

$$\left\{\mathit{z}\left|∥\mathit{z}-\frac{\mathit{y}}{2\alpha }∥<\frac{\parallel \mathit{y}\parallel }{2\alpha }\right.\right\}.$$

(7)

This is the ball of excluded volume. The volume of the ball (7) does not exceed $V={\left(\frac{1}{2\alpha }\right)}^n{V}_n({\mathbb{B}}_n)$ for each $\mathit{y}\in Y$. The probability that point $\mathit{x}$ belongs to such a ball does not exceed

$$V\underset{z\in {\mathbb{B}}_n}{sup}\rho (z)\le C{\left(\frac{1}{2r\alpha }\right)}^n.$$

The probability that $\mathit{x}$ belongs to the union of $|Y|$ such balls does not exceed $|Y|C{\left(\frac{1}{2r\alpha }\right)}^n$. For ${|Y|<\delta (2r\alpha )}^n/C$ this probability is smaller than $\delta$ and $p>1-\delta$. □

Note that:

• The finite set Y in Theorem 1 is just a finite subset of the ball ${\mathbb{B}}_n$ without any assumption of its randomness. We only used the assumption about distribution of $\mathit{x}$.
• The distribution of $\mathit{x}$ may deviate significantly from the uniform distribution in the ball ${\mathbb{B}}_n$. Moreover, this deviation may grow with dimension n as a geometric progression:

  $$\rho (\mathit{x})/{\rho }_{\mathrm{uniform}}\le C/r^n,$$

  where ${\rho }_{\mathrm{uniform}}=1/V_n({\mathbb{B}}_n)$ is the density of uniform distribution and $1/(2\alpha )<r<1$ under assumption that $1/2<\alpha \le 1$.

Let, for example, $\alpha =0.8$, $r=0.9$, $C=1$, $\delta =0.01$.

Table 1. The upper bound on $|Y|$ that guarantees separation of $\mathit{x}$ from Y by Fisher’s discriminant with probability 0.99 according to Theorem 1 for $\alpha =0.8$, $r=0.9$, $C=1$ in various dimensions.

n	10	25	50	100	150	200
$|Y|\le$	0.38	91	$8.28\times {10}^5$	$6.85\times {10}^{13}$	$5.68\times {10}^{21}$	$4.70\times {10}^{29}$
$\rho (\mathit{x})/{\rho }_{\mathrm{uniform}}\le$	2.86	13.9	194	$3.76\times {10}^4$	$7.30\times {10}^6$	$1.41\times {10}^9$

shows the upper bounds on $|Y|$ given by Theorem 1 in various dimensions n that guarantees $\alpha$-Fisher separability of a random point $\mathit{x}$ from Y with probability $\ge 0.99$ if the ratio $\rho (\mathit{x})/{\rho }_{\mathrm{uniform}}$ is bounded by the geometric progression $1/r^n$.

For example, for $n=100$, we see that for any set with $|Y|<6.85\times {10}^{13}$ points in the unit ball and any distribution whose density $\rho$ deviates from the uniform one by a factor at most $3.76\times {10}^4$, a random point from this distribution is Fisher-separable (2) with $\alpha =0.8$ from all points in Y with 99% probability.

If we consider Y as a random set in ${\mathbb{B}}_n$ that satisfies (6) for each point then with high probability Y is $\alpha$-Fisher separable (each point from the rest of Y) under some constraints of $|Y|$ from above. From Theorem 1 we get the following corollary.

Corollary 1.

If $Y\subset {\mathbb{B}}_n$ is a random set $Y=\{{\mathit{y}}_1,\dots ,{\mathit{y}}_{|Y|}\}$ and for each j the conditional distributions of vector ${\mathit{y}}_j$ for any given positions of the other ${\mathit{y}}_k$ in ${\mathbb{B}}_n$ satisfy the same conditions as the distribution of $\mathit{x}$ in Theorem 1, then the probability of the random set Y to be α-Fisher separable can be easily estimated:

$$p\ge 1-{|Y|}^{2}C{\left(\frac{1}{2r\alpha }\right)}^n.$$

Thus, let us take, for example, $p>0.99$ if $|Y|<(1/10)C^{-1/2}{(2r\alpha )}^{n/2}$ (

Table 2. The upper bound on $|Y|$ that guarantees $\alpha$-Fisher’s separability of Y with probability $\ge 0.99$ according to Corollary 1 for $\alpha =0.8$, $r=0.9$, $C=1$ in various dimensions.

n	10	25	50	100	150	200
$|Y|\le$	0.61	$9.5$	910	$8.28\times {10}^6$	$7.53\times {10}^{10}$	$6.85\times {10}^{14}$

).

Multiple generalisations of Theorem 1 are proven with sharp estimates of $|Y|$ for various families of probability distributions. In this section, we derive the stochastic separation theorems for distributions with cluster structure that violate significantly the assumption (6). For this purpose, in the following subsections we introduce models of cluster structures and modify the notion of Fisher separability to separate clusters. The structure of separation functionals remains explicit with a one-shot non-iterative learning but assimilates both information about the entire distribution and about the cluster being separated.

3.2. Granular Models of Clusters

The simplest model of a fine-grained distribution of data assumes that the data are grouped into dense clusters and each cluster is located inside a relatively small body (a granule) with random position. Under these conditions, the distributions of data inside the small granules do not matter and may be put out of consideration. What is important is the geometric characteristics of the granules and their distribution. This is a simple one-level version of the granular data representation [68,69]. The possibility to replace points by compacts in neural network learning was considered by Kainen [59]. He developed the idea that ‘compacta can replace points’. In discussion, we will touch also a promising multilevel hierarchical granular representation.

Spherical granules allows a simple straightforward generalisation of Theorem 1. Consider spherical granules $G_z$ of radius R with centres $\mathit{z}\in {\mathbb{B}}_n$:

$$G_z=\{{\mathit{z}}^{\prime }|\parallel {\mathit{z}}^{\prime }-\mathit{z}\parallel \le R\}.$$

Let $G_x$ and $G_y$ be two such granules. Let us reformulate the Fisher separation condition with threshold $\alpha$ for granules:

$$\alpha (\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},{\mathit{y}}^{\prime })\text{for all}{\mathit{x}}^{\prime }\in G_x,{\mathit{y}}^{\prime }\in G_y.$$

(8)

Elementary geometric reasoning gives that the separability condition (8) holds if $\mathit{x}$ (the centre of $G_x$) does not belong to the ball with radius $\frac{1}{2\alpha }\parallel \mathit{y}\parallel +R(1+\frac{1}{\alpha })$ centred at $\frac{1}{2\alpha }\mathit{y}$:

$$\mathit{x}\notin \left\{\mathit{z}\left|∥\mathit{z}-\frac{\mathit{y}}{2\alpha }∥<\frac{\parallel \mathit{y}\parallel }{2\alpha }+R\left(1+\frac{1}{\alpha }\right)\right.\right\}.$$

(9)

This is analogous to the ball of excluded volume (7) for spherical granules. The difference from (7) is that both $\mathit{z}$ and $\mathit{y}$ are inflated into balls of radius R.

Let $\mathbf{B}$ be the closure of the ball defined in (7):

$$\mathbf{B}=\left\{\mathit{z}\left|∥\mathit{z}-\frac{\mathit{y}}{2\alpha }∥\le \frac{\parallel \mathit{y}\parallel }{2\alpha }\right.\right\}.$$

Condition (9) implies that the distance between $\mathit{x}$ and $\mathbf{B}$ is at least $R(1+\frac{1}{\alpha })$. In particular, $\parallel \mathit{x}-\beta \mathit{x}\parallel \ge R(1+\frac{1}{\alpha })$, where $\beta$ is the largest real number such that $\beta \mathit{x}\in \mathbf{B}$. Then $\beta \mathit{x}$ belongs to the boundary of $\mathbf{B}$, hence (5) holds as an equality for $\beta \mathit{x}$:

$$\alpha (\beta \mathit{x},\beta \mathit{x})=(\beta \mathit{x},\mathit{y}),$$

or, equivalently, ${\alpha \beta \parallel \mathit{x}\parallel }^2=(\mathit{x},\mathit{y})$. Then

$$\alpha (\mathit{x},\mathit{x})={\alpha \parallel \mathit{x}\parallel ·\parallel \mathit{x}-\beta \mathit{x}\parallel +\alpha \beta \parallel \mathit{x}\parallel }^2\ge \alpha \parallel \mathit{x}\parallel ·R\left(1+\frac{1}{\alpha }\right)+(\mathit{x},\mathit{y})=(1+\alpha )R\parallel \mathit{x}\parallel +(\mathit{x},\mathit{y}).$$

Thus, if $\mathit{x}$ satisfies (9) then

$$\alpha (\mathit{x},\mathit{x})\ge (1+\alpha )R\parallel \mathit{x}\parallel +(\mathit{x},\mathit{y})\text{that is}\alpha ((\mathit{x},\mathit{x})-R\parallel \mathit{x}\parallel )\ge (\mathit{x},\mathit{y})+R\parallel \mathit{x}\parallel .$$

(10)

Let ${\mathit{x}}^{\prime }\in G_x,{\mathit{y}}^{\prime }\in G_y$. The Cauchy–Schwarz inequality gives $|({\mathit{x}}^{\prime }-\mathit{x},\mathit{x})|\le \parallel {\mathit{x}}^{\prime }-\mathit{x}\parallel \parallel \mathit{x}\parallel \le R\parallel \mathit{x}\parallel$ and $|({\mathit{y}}^{\prime }-\mathit{y},\mathit{x})|\le \parallel {\mathit{y}}^{\prime }-\mathit{y}\parallel \parallel \mathit{x}\parallel \le R\parallel \mathit{x}\parallel$. Therefore, $(\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},\mathit{x})-R\parallel \mathit{x}\parallel$ and $(\mathit{x},\mathit{y})+R\parallel \mathit{x}\parallel \ge (\mathit{x},{\mathit{y}}^{\prime })$. Combination of two last inequalities with (10) gives separability (8).

If the point $\mathit{y}$ belongs to the unit ball ${\mathbb{B}}_n$ then the radius of the ball of excluded volume (9) does not exceed

$$\xi =\frac{1}{2\alpha }+R\left(1+\frac{1}{\alpha }\right).$$

(11)

Further on, the assumption $\xi <1$ is used.

Theorem 2.

Consider a finite set of spherical granules $G_y$ with radius R and set of centres Y in ${\mathbb{B}}_n$. Let $G_x$ be a granule with radius R and a randomly chosen centre $\mathit{x}$ from a distribution in the unit ball with the bounded probability density $\rho (\mathit{x})$. Assume that $\rho (\mathit{x})$ satisfies inequality (6) and the upper estimate of the radius of excluded ball (11) $\xi <1$. Let $1>r>\xi$ and

$$|Y|<\delta \frac{1}{C}{\left(\frac{r}{\xi }\right)}^n.$$

(12)

Then the separability condition (8) holds for $G_x$ and all $G_y$ ($\mathit{y}\in Y$) with probability $p>1-\delta$.

Proof. 

The separability condition (8) holds for the granule $G_x$ and all $G_y$ ($\mathit{y}\in Y$) if $\mathit{x}$ does not belong to the excluded ball (9) for all $\mathit{y}\in Y$. The volume of the excluded ball is $V={\xi }^n{V}_n({\mathbb{B}}_n)$ for each $\mathit{y}\in Y$. The probability that point $\mathit{x}$ belongs to such a ball does not exceed $C{\left(\frac{\xi }{r}\right)}^n$ in accordance with the boundedness condition (6). Therefore, the probability that $\mathit{x}$ belongs to the union of such balls does not exceed $|Y|C{\left(\frac{\xi }{r}\right)}^n$. This probability is less than $\delta$ if $|Y|<\delta \frac{1}{C}{\left(\frac{r}{\xi }\right)}^n$. □

Table 3. The upper bound on $|Y|$ that guarantees separation of granules $G_x$ and all $G_y$ ($\mathit{y}\in Y$) (8) with probability 0.99 according to Theorem 2 for $\alpha =0.9$, $r=0.9$, $C=1$ and $R=0.1$ in various dimensions.

n	25	50	100	150	200
$|Y|\le$	$0.55$	30	$9.26\times {10}^4$	$2.81\times {10}^8$	$8.58\times {10}^{11}$

shows how the number $|Y|$ that guarantees separability (8) of a random granule $G_x$ from an arbitrarily selected set of $|Y|$ granules with probability 0.99 grows with dimension for $\alpha =0.9$, $r=0.9$, $C=1$ and $R=0.1$.

The separability condition (8) can be considered as Fisher separability (5) with inflation points to granules. From this point of view, Theorem 2 is a version of Theorem 1 with inflated points. An inflated version of Corollary 1 also exists.

Corollary 2.

Let $Y\subset {\mathbb{B}}_n$ be a random set $Y=\{{\mathit{y}}_1,\dots ,{\mathit{y}}_{|Y|}\}$. Assume that for each j the density of conditional distribution of vector ${\mathit{y}}_j$ for any given positions of the other ${\mathit{y}}_k$ in ${\mathbb{B}}_n$ exists and satisfies inequality (6). Consider a finite set of spherical granules $G_y$ with radius R and centres $\mathit{y}\in Y$ in ${\mathbb{B}}_n$. For the radius of the excluded ball (11) assume $\xi <r$, where $r<1$ is defined in (6). Then, with probability

$$p\ge 1-{|Y|}^{2}C{\left(\frac{\xi }{r}\right)}^n$$

for every two $\mathit{x},\mathit{y}\in Y$ ($\mathit{x}\ne \mathit{y}$) the separability condition (8) holds. Equivalently, it holds with probability $p>1-\delta$ ($\delta >0$) if

$$|Y|<\sqrt{\frac{\delta }{C}}{\left(\frac{r}{\xi }\right)}^{n/2}.$$

This upper border of $|Y|$ grows with n in geometric progression.

The idea of spherical granules implies that, in relation to the entire dataset, the granules are more or less uniformly compressed in all directions and their diameter is relatively small (or, equivalently, the granules are inflated points, and this inflation is limited isotropically). Looking around, we can hypothesise quite different properties: in some directions, the granules can have large variety, it can be as large of variety as the whole set, but the dispersion decays in the sequence of the granule’s principal components while the entire set is assumed to be whitened. Large diameter of granules is not an obstacle to the stochastic separation theorems. The following proposition gives a simple but instructive example.

Proposition 1.

Let $1\ge \alpha >1/2$, $1>r>1/(2\alpha )$, $1>\delta >0$. Consider an arbitrary set of N intervals $I_j=[{\mathit{u}}_{\mathit{j}},{\mathit{v}}_{\mathit{j}}]\in {\mathbb{B}}_n$ ($j=1,\dots ,N$). Let $\mathit{x}$ be a randomly chosen point from a distribution in the unit ball with the bounded probability density $\rho (\mathit{x})$. Assume that $\rho (\mathit{x})$ satisfies inequality (6) and $N<\frac{\delta }{2C}{(2r\alpha )}^n$. Then with probability $p>1-\delta$ point $\mathit{x}$ is Fisher-separable from any $\mathit{y}\in {\cup }_j{I}_j$ with threshold α (5).

Proof. 

For given $\mathit{x}$ and $\alpha$, the Fisher’s separability inequality defines a half-space for $\mathit{y}$ (5). An interval $I=[u,v]$ belongs to this half-space if and only if its ends, u and v, belong to it, that is, $\mathit{x}$ is $\alpha$-Fisher separable from u and v. Therefore, we can apply Theorem 1 to prove $\alpha$-Fisher separability of $\mathit{x}$ from the set $Y=\{u_j\}\cup \{v_j\}$, $|Y|=2N$. □

The same statements are true for separation of a point from a set of simplexes of various dimension. For such estimates, only the number of vertices matters.

Consider granules in the form of ellipsoids with decaying sequence of length of the principal axes. Let $d_1>d_2>\dots$ ($d_i>0$) be an infinite sequence of the upper bounds for semi-axes. Each ellipsoid granule in ${\mathbb{R}}^n$ has a centre, $\mathit{z}$, an orthonormal basis of principal axes $E=\{{\mathit{e}}_1,{\mathit{e}}_2,\dots ,{\mathit{e}}_n\}$, and a sequence of semi-axes, $A=\{a_1\ge a_2\ge \dots \ge a_n\}$ ($d_i\ge a_i>0$). This ellipsoid is given by the inequality:

$${\mathbf{S}}_{\mathit{z},E,A}=\left\{{\mathit{z}}^{\prime }\left|\sum _{j=1}^n\frac{1}{a_j^2}{({\mathit{z}}^{\prime }-\mathit{z},{\mathit{e}}_j)}^2\le 1\right\}\right..$$

(13)

Let the sequence $d_1>d_2>\dots$ ($d_i>0$, $d_i\to 0$) be given.

Theorem 3.

Consider a set of N elliptic granules (13) with centres $\mathit{z}\in {\mathbb{B}}_n$ and $a_i\le d_i$. Let D be the union of all these granules. Assume that $\mathit{x}\in {\mathbb{B}}_n$ is a random point from a distribution in the unit ball with the bounded probability density $\rho (\mathit{x})\le {\rho }_{max}$. Then for positive ε, ς

$$\mathbf{P}((\mathit{x},{\mathit{z}}^{\prime })<\epsilon forall{\mathit{z}}^{\prime }\in D,\&(\mathit{x},\mathit{x})>1-\varsigma )>1-N{\rho }_{max}{V}_n({\mathbb{B}}_n)aexp(-bn),$$

(14)

where a and b do not depend on the dimensionality.

In proof of Theorem 3 we construct explicit estimates of probability in (14). This construction (Equation (21) below) is an important part of Theorem 3. It is based on the following lemmas about quasiorthogonality of random vectors.

Lemma 1.

Let $\mathit{e}\in {\mathbb{R}}^n$ be any normalised vector, $\parallel \mathit{e}\parallel =1$. Assume that $\mathit{x}\in {\mathbb{B}}_n$ is a random point from a distribution in ${\mathbb{B}}_n$ with the bounded probability density $\rho (\mathit{x})\le {\rho }_{max}$. Then, for any $\epsilon >0$ the probability

$$\mathbf{P}((\mathit{x},\mathit{e})\ge \epsilon )\le \frac{1}{2}{\rho }_{max}{V}_n({\mathbb{B}}_n){(\sqrt{1-{\epsilon }^2})}^n.$$

(15)

Proof. 

The inequality $(\mathit{x},\mathit{e})\ge \epsilon$ defines a spherical cap. This spherical cap can be estimated from above by the volume of a hemisphere of radius $\sqrt{1-{\epsilon }^2}$ (Figure 4). The volume W of this hemisphere is

$$W=\frac{1}{2}{V}_n({\mathbb{B}}_n){(\sqrt{1-{\epsilon }^2})}^n$$

The probability that $\mathit{x}$ belongs to this cap is bounded from above by the value ${\rho }_{max}W$, which gives the estimate (15). □

Lemma 2.

Let ${\mathit{e}}_1,\dots ,{\mathit{e}}_N\in {\mathbb{R}}^n$ be normalised vectors, $\parallel {\mathit{e}}_i\parallel =1$. Assume that $\mathit{x}\in {\mathbb{B}}_n$ is a random point from a distribution in ${\mathbb{B}}_n$ with the bounded probability density $\rho (\mathit{x})\le {\rho }_{max}$. Then, for any $\epsilon >0$ the probability

$$\mathbf{P}((\mathit{x},{\mathit{e}}_i)\le \epsilon foralli=1,\dots ,N)\ge 1-\frac{1}{2}N{\rho }_{max}{V}_n({\mathbb{B}}_n){(\sqrt{1-{\epsilon }^2})}^n$$

(16)

Proof. 

Notice that

$$\mathbf{P}((\mathit{x},{\mathit{e}}_i)\le \epsilon \text{for all}i=1,\dots ,N)\ge 1-\sum _i\mathbf{P}((\mathit{x},{\mathit{e}}_i)\ge \epsilon ).$$

According to Lemma 1, each term in the last sum is estimated from above by the expression $\frac{1}{2}{\rho }_{max}{V}_n({\mathbb{B}}_n){(\sqrt{1-{\epsilon }^2})}^n$ (15). □

It is worth mentioning that the term ${(\sqrt{1-{\epsilon }^2})}^n$ decays exponentially when n increases.

Let ${\mathbf{S}}_{\mathit{z},E,A}$ be an ellipsoid (13). Decompose a vector $\mathit{x}\in {\mathbb{R}}^n$ in an orthonormal basis $E=\{{\mathit{e}}_1,\dots ,{\mathit{e}}_n\}$: $\mathit{x}={\sum }_i(\mathit{x},{\mathit{e}}_i){\mathit{e}}_i=\parallel x\parallel {\sum }_i{\mathit{e}}_{i}cos{\alpha }_i$, where $cos{\alpha }_i=(\mathit{x},{\mathit{e}}_i)/\parallel \mathit{x}\parallel$. Notice that ${\sum }_i{cos}^2{\alpha }_i=1$ (the n-dimensional Pythagoras theorem).

Lemma 3.

For a given $\mathit{x}\in {\mathbb{R}}^n$. Maximisation of a linear functional $(\mathit{x},{\mathit{z}}^{\prime })$ on an ellipsoid (13) gives

$$\underset{{\mathit{z}}^{\prime }\in {\mathbf{S}}_{\mathit{z},E,A}}{max}(\mathit{x},{\mathit{z}}^{\prime })=(\mathit{x},\mathit{z})+\parallel \mathit{x}\parallel \sqrt{\sum _i{a}_i^{2}cos{\alpha }_i^2},$$

(17)

and the maximiser has the following coordinates in the principal axes:

$$z_i^{\prime }=z_i+\frac{a_i^{2}cos{\alpha }_i}{\sqrt{{\sum }_i{a}_i^{2}cos{\alpha }_i^2}},$$

(18)

where $z_i^{\prime }=({\mathit{z}}^{\prime },{\mathit{e}}_i)$, and $z_i=(\mathit{z},{\mathit{e}}_i)$ are coordinates of the vectors ${\mathit{z}}^{\prime }$, $\mathit{z}$ in the basis E.

Proof. 

Introduce coordinates in the ellipsoid ${\mathbf{S}}_{\mathit{z},E,A}$ (13): ${\Delta }_i=z_i^{\prime }-z_i$. In these coordinates, the objective function is

$$(\mathit{x},{\mathit{z}}^{\prime })=(\mathit{x},\mathit{z})+\parallel \mathit{x}\parallel \sum _i{\Delta }_{i}cos{\alpha }_i.$$

For given $\mathit{x}$, $\mathit{z}$ we have to maximise $\sum _i{\Delta }_{i}cos{\alpha }_i$ under the equality constraints:

$$F({\Delta }_1,\dots ,{\Delta }_n)=\frac{1}{2}\sum _i\frac{{\Delta }_i^2}{a_i^2}=\frac{1}{2},$$

because the maximiser of a linear functional on a convex compact set belongs to the border of this compact.

The method of Lagrange multipliers gives:

$$cos{\alpha }_i=\lambda \frac{\partial F}{\partial {\Delta }_i}=\lambda \frac{{\Delta }_i}{a_i^2},{\Delta }_i=\frac{1}{\lambda }{a}_i^{2}cos{\alpha }_i.$$

To find the Lagrange multiplier $\lambda$, we use the equality constrain again and get

$$\frac{1}{{\lambda }^2}\sum _i{a}_i^2{cos}^2{\alpha }_i=1,\lambda =\pm \sqrt{\sum _i{a}_i^2{cos}^2{\alpha }_i},$$

where the ‘+’ sign corresponds to the maximum and the ‘−’ sign corresponds to the minimum of the objective function. Therefore, the required maximiser has the form (18) and the corresponding maximal value is given by (17). □

Proof of Theorem 3.

The proof is organised as follows. Select sufficiently small $R>0$ and find such k that $d_{k+1}<R$. For each elliptic granule select the first k vectors of its principal axes. There will be N vectors of the first axes, N vectors of the second axes, etc. Denote these families of vectors ${\mathcal{E}}_1$, ${\mathcal{E}}_2$, …, ${\mathcal{E}}_k$: ${\mathcal{E}}_i$ is a set of vectors of the ith principal axis for granules. Let ${\mathcal{E}}_0$ be the set of the centres of granules. Select a small $\vartheta >0$. Use Lemma 2 and find the probability that for all $\mathit{e}\in {\mathcal{E}}_i$ and for all $i=1,\dots ,k$ the following quasiorthogonality condition holds: $|(\mathit{x},\mathit{e})|\le \frac{\vartheta }{\sqrt{k}{d}_i}$. Under this condition, evaluate the value of the separation functionals (17) in all granules as

$$(\mathit{x},{\mathit{z}}^{\prime })\le (\mathit{x},\mathit{z})+\parallel \mathit{x}\parallel \sqrt{\sum _i{a}_i^{2}cos{\alpha }_i^2}\le (\mathit{x},\mathit{z})+\sqrt{{\vartheta }^2+R^2},$$

(19)

where $\mathit{z}$ is the centre of the granule. Indeed,

$${\parallel \mathit{x}\parallel }^2\sum _i{a}_i^{2}cos{\alpha }_i^2\le \sum _{i=1}^k{d}_i^2{(\mathit{x},{\mathit{e}}_i)}^2+\sum _{i=k+1}^n{\parallel \mathit{x}\parallel }^2{R}^{2}cos{\alpha }_i^2.$$

The quasiorthogonality condition gives that the first sum does not exceed $\vartheta$. Recall that $\parallel \mathit{x}\parallel \le 1$ and $\sum _{i}cos{\alpha }_i^2=1$. Therefore, the second sum does not exceed $R^2$. This gives us the required estimate (19).

The first term, $(\mathit{x},\mathit{z})$ is also small with high probability. This quasiorthogonality of $\mathit{x}$ and N vectors of the centres of granules follows from Lemma 2. It should be noted that the requirement of qusiorthogonality of $\mathit{x}$ to several families of vectors (N centres and $kN$ principal axes) increases the pre-exponential factor in the negative term in (16). This increase can be compensated by a slight increase in the dimensionality because of the exponential factor there.

Let us construct the explicit estimates for given $\epsilon >0$, $\varsigma >0$. Take

$$\vartheta =R=\epsilon /(1+\sqrt{2}).$$

(20)

Under conditions of Theorem 3 several explicit exponential estimates of probabilities hold:

• Volume of a ball with radius $1-\varsigma$ is $V_n({\mathbb{B}}_n){(1-\varsigma )}^n$. therefore for probability of $\mathit{x}$ belong to this ball, we have

  $$\mathbf{P}((\mathit{x},\mathit{x})\le 1-\varsigma )\le {\rho }_{max}{V}_n({\mathbb{B}}_n){(1-\varsigma )}^n;$$
• For every $\mathit{z}\in {\mathcal{E}}_0$,

  $$\mathbf{P}((\mathit{x},\mathit{z})\ge \vartheta )\le {\rho }_{max}\frac{1}{2}{V}_n({\mathbb{B}}_n){(\sqrt{1-{\vartheta }^2})}^n;$$
• For every $\mathit{e}\in {\mathcal{E}}_i$

  $$\mathbf{P}\left(|(\mathit{x},\mathit{e})|\ge \frac{\vartheta }{\sqrt{k}{d}_i}\right)\le {\rho }_{max}{V}_n({\mathbb{B}}_n){\left(\sqrt{1-{\left(\frac{\vartheta }{\sqrt{k}{d}_i}\right)}^2}\right)}^n.$$

Thus, the probability

$$\begin{array}{cc}\hfill & \mathbf{P}\left((\mathit{x},\mathit{x})\ge 1-\varsigma \&(\mathit{x},\mathit{z})\le \vartheta \text{for all}\mathit{z}\in {\mathcal{E}}_0\&|(\mathit{x},\mathit{e})|\le \frac{\vartheta }{\sqrt{k}{d}_i}\text{for all}\mathit{e}\in {\mathcal{E}}_i,i=1,\dots ,k\right)\hfill \\ \hfill & \ge 1-{\rho }_{max}{V}_n({\mathbb{B}}_n)\left[{(1-\varsigma )}^n+\frac{1}{2}N{(\sqrt{1-{\vartheta }^2})}^n+N\sum _{i=1}^k{\left(\sqrt{1-{\left(\frac{\vartheta }{\sqrt{k}{d}_i}\right)}^2}\right)}^n\right].\hfill \end{array}$$

(21)

If $(\mathit{x},\mathit{z})\le \vartheta$ for all $\mathit{z}\in {\mathcal{E}}_0$ and $|(\mathit{x},\mathit{e})|\le \frac{\vartheta }{\sqrt{k}{d}_i}$ for all $\mathit{e}\in {\mathcal{E}}_i,i=1,\dots ,k$ then, according to the choice of $\vartheta$ (20) and inequality (19), $(\mathit{x},{\mathit{z}}^{\prime })\le \epsilon$ for all points from the granules ${\mathit{z}}^{\prime }\in D$.

Therefore, (21) proves Theorem 3 with explicit estimate of the probability.

If, in addition, $(\mathit{x},\mathit{x})\ge 1-\varsigma$, $0<\alpha \le 1$ and $\alpha (1-\varsigma )>\epsilon$ then

$$\alpha (\mathit{x},\mathit{x})>(\mathit{x},{\mathit{z}}^{\prime })\text{for all}{\mathit{z}}^{\prime }\in D$$

for all points from the granules ${\mathit{z}}^{\prime }\in D$. This is the analogue of $\alpha$-Fisher separability of point $\mathit{x}$ from elliptic granules. □

Theorem 3 describes stochastic separation of a random point in n-dimensional dataspace from a set of N elliptic granules. For given N probability of $\alpha$-Fisher separability exponentially approaches 1 with dimensionality growth. Equivalently, for a given probability, the upper bound on the number of granules that guarantees such a separation with this probability grows exponentially with the dimension of the data. We require two properties of the probability distribution: compact support and the existence of a probability density bounded from above. The interplay between the dependence of the maximal density on the dimension (similarly to (6)) and the exponents in the probability estimates (21) determines the estimate of the separation probability.

In Theorem 3 we analysed separation of a random point from a set of granules but it seems to be much more practical to consider separation of a random granule from a set of granules. For analysis of random granules a joint distribution of the position of the centre and the basis of principal axes is needed. Existence of strong dependencies between the position of the centre and the directions of principal axes may in special cases destroy the separability phenomenon. For example, if the first principal axis has length 1 or more and is parallel to the vector of the centre (i.e., ${\mathit{e}}_1=\mathit{x}/\parallel \mathit{x}\parallel$) then this granule is not separated even from the origin. On the other hand, independence of these distributions guarantees stochastic separability, as follows from Theorem 4 below. Independence by itself is not needed. The essential condition is that for each orientation of the granule, the position of its centre remains rather uncertain.

Theorem 4.

Consider a set of N elliptic granules (13) with centres $\mathit{z}\in {\mathbb{B}}_n$ and $a_i\le d_i$. Let D be the union of all these granules. Assume that $\mathit{x}\in {\mathbb{B}}_n$ is a random point from a distribution in the unit ball with the bounded probability density $\rho (\mathit{x})\le {\rho }_{max}$. Let $\mathit{x}$ be a centre of a random elliptic granule ${\mathbf{S}}_x={\mathbf{S}}_{\mathit{x},E_x,A_x}$ (13). Assume that for any basis of principal axes E and sequence of semi-axes $A=\{a_i\}$ ($a_i\le d_i$) the conditional distribution of the centres of granules $\mathit{x}$ given $E_x=E,A_x=A$ has a density in ${\mathbb{B}}_n$ uniformly bounded from above:

$$\rho (\mathit{x}|E_x=E,A_x=A)\le {\rho }_{max}$$

and ${\rho }_{max}$ does not depend on $E_x,A_x$ Then for positive ε, ς

$$\begin{array}{cc}\hfill \mathbf{P}& ((\mathit{x},{\mathit{z}}^{\prime })\le \epsilon forall{\mathit{z}}^{\prime }\in D\&(\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},\mathit{x})-\epsilon forall{\mathit{x}}^{\prime }\in {\mathbf{S}}_x\&(x,x)\ge 1-\varsigma \hfill \\ \hfill & \ge 1-N{\rho }_{max}{V}_n({\mathbb{B}}_n)aexp(-bn),\hfill \end{array}$$

(22)

where a and b do not depend on the dimensionality.

In the proof of Theorem 4 we estimate the probability (22) by a sum of decaying exponentials, which give explicit formulas for a and b as was done for Theorem 3 in (21).

Proof. 

We will prove (22) for an elipsoid ${\mathbf{S}}_x$ (13) with given (not random) basis E and semiaxes $a_i\le d_i$, and with a random centre $\mathit{x}\in {\mathbb{B}}_n$ assuming that the distribution density of $\mathit{x}$ is bounded from above by ${\rho }_{max}$.

Select sufficiently small $R>0$ and find such k that $d_{k+1}<R$. For each granule, including ${\mathbf{S}}_x$ with the centre $\mathit{x}$ select the first k vectors of its principal axes. There will be $N+1$ vectors of the first axes, $N+1$ vectors of the second axes, etc. Denote these families of vectors ${\mathcal{E}}_1$, ${\mathcal{E}}_2$, …, ${\mathcal{E}}_k$: ${\mathcal{E}}_i$ is a set of vectors of the ith principal axis for all granules, ${\mathbf{S}}_x$. Let ${\mathcal{E}}_0$ be the set of of the centres of granules (excluding the centre $\mathit{x}$ of the granule ${\mathbf{S}}_x$).

For a given $\vartheta >0$ the following estimate of probability holds (analogously to (21)).

$$\begin{array}{cc}\hfill & \mathbf{P}\left((\mathit{x},\mathit{x})\ge 1-\vartheta \&(\mathit{x},\mathit{z})\le \vartheta \text{for all}\mathit{z}\in {\mathcal{E}}_0\&|(\mathit{x},\mathit{e})|\le \frac{\vartheta }{\sqrt{k}{d}_i}\text{for all}\mathit{e}\in {\mathcal{E}}_i,i=1,\dots ,k\right)\hfill \\ \hfill & \ge 1-{\rho }_{max}{V}_n({\mathbb{B}}_n)\left[{(1-\vartheta )}^n+\frac{1}{2}N{(\sqrt{1-{\vartheta }^2})}^n+(N+1)\sum _{i=1}^k{\left(\sqrt{1-{\left(\frac{\vartheta }{\sqrt{k}{d}_i}\right)}^2}\right)}^n\right].\hfill \end{array}$$

(23)

If $(\mathit{x},\mathit{x})\ge 1-\vartheta$ and $(\mathit{x},\mathit{z})\le \vartheta$ for all $\mathit{z}\in {\mathcal{E}}_0$, and $|(\mathit{x},\mathit{e})|\le \frac{\vartheta }{\sqrt{k}{d}_i}$ for all $\mathit{e}\in {\mathcal{E}}_i,i=1,\dots ,k$, then by (19)

$$(\mathit{x},{\mathit{z}}^{\prime })\le \vartheta +\sqrt{{\vartheta }^2+R^2}\&(\mathit{x},{\mathit{x}}^{\prime })\ge 1-\vartheta -\sqrt{{\vartheta }^2+R^2}\text{for all}{\mathit{z}}^{\prime }\in D,{\mathit{x}}^{\prime }\in {\mathbf{S}}_x.$$

Therefore, if we select $R=\frac{\epsilon }{1+\sqrt{2}}$ and $\vartheta =min\left\{\varsigma ,\frac{\epsilon }{1+\sqrt{2}}\right\}$, then the estimate (23) proves Theorem 4. Additionally, for this choice, $(\mathit{x},{\mathit{x}}^{\prime })\ge 1-\epsilon$ for all ${\mathit{x}}^{\prime }\in {\mathbf{S}}_x$. Therefore, if $\epsilon <\frac{\alpha }{1+\alpha }$, then $\alpha (\mathit{x},{\mathit{x}}^{\prime })>(\mathit{x},{\mathit{z}}^{\prime })$ for all ${\mathit{z}}^{\prime }\in D$ and ${\mathit{x}}^{\prime }\in {\mathbf{S}}_x$ with probability estimated in (23). This result can be considered as $\alpha$-Fisher separability of elliptic granules in high dimensions with high probability. □

Note that the the proof does not actually use that $d_i\to 0$. All that we use that $\underset{i\to \infty }{lim\; sup}{d}_i<R$ for $R=\frac{ϵ}{1+\sqrt{2}}$, where $ϵ<\frac{\alpha }{1+\alpha }$. Hence the proof remains valid whenever $\underset{i\to \infty }{lim\; sup}{d}_i<\frac{\alpha }{(1+\sqrt{2})(1+\alpha )}$.

It may be useful to formulate a version of Theorem 4 when ${\mathbf{S}}_{\mathit{x}}$ is the granule of an arbitrary (non-random) shape but with a random centre as a separate Proposition.

Proposition 2.

Let D be the union of N elliptic granules (13) with centres in ${\mathbb{B}}_n$ with $a_i\le d_i$. Let ${\mathbf{S}}_{\mathit{z},E,A}$ be one more such granule. Let $\mathit{x}\in {\mathbb{B}}_n$ be a random point from a distribution in the unit ball with the bounded probability density $\rho (x)\le {\rho }_{\mathit{max}}$. Let ${\mathbf{S}}_{\mathit{x}}={\mathbf{S}}_{\mathit{z},E,A}+(\mathit{x}-\mathit{z})$ be the granule ${\mathbf{S}}_{\mathit{z},E,A}$ shifted such that its centre becomes $\mathit{x}$. Then Theorem 4 is true for ${\mathbf{S}}_{\mathit{x}}$.

The proof is the same as the proof of Theorem 4.

The estimates (21) and (23) are far from being sharp. Detailed analysis for various classes of distributions may give better estimates as it was done for separation of finite sets [13]. This work needs to be done for separation of granules as well.

3.3. Superstatistic Presentation of ‘Granules’

The alternative approach to the granular structure of the distributions are soft clusters. They can be studied in the frame of superstatistical approach with representation of data distribution by a random mixture of distributions of points in individual clusters. We start with the following remark. Notice that Proposition 2 has the following easy corollary.

Corollary 3.

Let ${\mathbf{S}}_{\mathit{x}}$ and D be as in Proposition 2. Let ${\mathit{x}}^{\prime }$ and ${\mathit{z}}^{\prime }$ be the points selected uniformly at random from ${\mathbf{S}}_{\mathit{x}}$ and D, correspondingly. Then for positive $ϵ,\zeta$

$$\mathbf{P}((\mathit{x},{\mathit{z}}^{\prime })\le ϵ\&(\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},\mathit{x})-ϵ\&(\mathit{x},\mathit{x})\ge 1-\zeta )\ge 1-N{\rho }_{\mathit{max}}{V}_n({\mathbb{B}}_n)aexp(-bn),$$

where the constants $a,b$ are the same as in Theorem 4.

Proof. 

Let $f(n)=N{\rho }_{\max }{V}_n({\mathbb{B}}_n)aexp(-bn)$. Let $A\subset {\mathbb{B}}_n$ be the set of $\mathit{x}$ such that (22) holds. Proposition 2 states that $\mathbf{P}(\mathit{x}\in A)\ge 1-f(n)$. Let E be the event that $(\mathit{x},{\mathit{z}}^{\prime })\le ϵ\&(\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},\mathit{x})-ϵ\&(\mathit{x},\mathit{x})\ge 1-\zeta$. By the law of total probability,

$$\begin{array}{cc}\hfill \mathbf{P}(E)& =\mathbf{P}(E|\mathit{x}\in A)\mathbf{P}(\mathit{x}\in A)+\mathbf{P}(E|\mathit{x}\notin A)\mathbf{P}(\mathit{x}\notin A)\hfill \\ \hfill & \ge \mathbf{P}(E|\mathit{x}\in A)\mathbf{P}(\mathit{x}\in A)=1·\mathbf{P}(\mathit{x}\in A)\ge 1-f(n).\hfill \end{array}$$

 □

Corollary 3 is weaker than Proposition 2. While Proposition 2 states that, with probability at least $1-f(n)$, the whole granule ${\mathbf{S}}_{\mathit{x}}$ can be separated from all points in D, Corollary 3 allows for the possibility that there could be a small portions of ${\mathbf{S}}_{\mathit{x}}$ and D which are not separated from each other. As we will see below, this weakening allows us to prove the result in much greater generality, where the uniform distribution in granules is replaced by much more general log-concave distributions.

We say that density $\rho :{\mathbb{R}}^n\to [0,\infty )$ of random vector $\mathit{x}$ (and the corresponding probability distribution) is log-concave, if set $K=\{z\in {\mathbb{R}}^n|\rho (z)>0\}$ is convex and $g(z)=-log(\rho (z))$ is a convex function on K. For example, the uniform distribution in any full-dimensional subset of ${\mathbb{R}}^n$ (and in particular uniform distribution in granules (13)) has a log-concave density.

We say that $\rho$ is whitened, or isotropic, if $\mathbb{E}[\mathit{x}]=\mathbf{0}$, and

$$\mathbb{E}[{(\mathit{x},\theta )}^2)]=1\forall \theta \in {\mathbb{S}}^{n-1},$$

(24)

where ${\mathbb{S}}^{n-1}$ is the unit sphere in ${\mathbb{R}}^n$. Equation (24) is equivalent to the statement that the variance-covariance matrix for the components of $\mathit{x}$ is the identity matrix. This can be achieved by linear transformation, hence every log-concave random vector $\mathit{x}$ can be represented as

$$\mathit{x}=\Sigma \mathit{y}+{\mathit{x}}_0,$$

(25)

where ${\mathit{x}}_0=\mathbb{E}[\mathit{x}]$, $\Sigma$ is (non-random) matrix and $\mathit{y}$ is some isotropic log-concave random vector.

An example of standard normal distribution shows that the support of isotropic log-concave distribution may be the whole ${\mathbb{R}}^n$. However, such distributions are known to be concentrated in a ball of radius $\sqrt{n}(1+\delta )$ with high probability.

Specifically, ([70], Theorem 1.1) implies that for any $\delta \in (0,1)$ and any isotropic log-concave random vector in ${\mathbb{R}}^n$,

$$\mathbf{P}(\parallel \mathit{x}\parallel \le (1+\delta )\sqrt{n})\ge 1-cexp(-c^{\prime }{\delta }^3\sqrt{n})$$

(26)

where $c,c^{\prime }>0$ are some absolute constants. Note that we have $\sqrt{n}$ but not n in the exponent, and this cannot be improved without requiring extra conditions on the distribution. We say that density $\rho :{\mathbb{R}}^n\to [0,\infty )$ is strongly log-concave with constant $\gamma >0$, or $\gamma$-SLC in short, if $g(z)=-log(\rho (z))$ is strongly convex, that is, $g(z)-\frac{\gamma }{2}\parallel z\parallel$ is a convex function on K. ([70], Theorem 1.1) also implies that

$$\mathbf{P}(\parallel \mathit{x}\parallel \le (1+\delta )\sqrt{n})\ge 1-cexp(-c^{\prime }{\delta }^{4}n)$$

(27)

for any $\delta \in (0,1)$, and any isotropic strongly log-concave random vector $\mathit{x}$ in ${\mathbb{R}}^n$.

Fix some $\delta >0$ and infinite sequence $d=(d_1>d_2>\dots )$ with each $d_i>0$ and $d_i\to 0$. Let us call log-concave random vector $\mathit{x}$$(\delta ,d)$-admissible if set $\Sigma ·B(\mathbf{0},(1+\delta )\sqrt{n})+{\mathit{x}}_0$ is a subset of some ellipsoid ${\mathbf{S}}_{{\mathit{x}}_0,E,A}$ (13), where $\Sigma$ and ${\mathit{x}}_0$ are defined in (25) and $B(\mathbf{0},(1+\delta )\sqrt{n})$ is the ball with centre $\mathbf{0}$ and radius $(1+\delta )\sqrt{n}$. Then (26) and (27) imply that $\mathit{x}\in {\mathbf{S}}_{{\mathit{x}}_0,E,A}$ with high probability. In combination with Proposition 2, this implies the following results.

Proposition 3.

Let $\delta >0$ and infinite sequence $d=(d_1>d_2>\dots )$ with each $d_i>0$ and $d_i\to 0$ be fixed. Let $\mathit{x}\in {\mathbb{B}}_n$ be a random point from a distribution in the unit ball with the bounded probability density $\rho (x)\le {\rho }_{\mathit{max}}$. Let ${\mathit{x}}^{″}$ be a point selected from some $(\delta ,d)$-admissible log-concave distribution, and let ${\mathit{x}}^{\prime }={\mathit{x}}^{″}-\mathbb{E}[{\mathit{x}}^{″}]+\mathit{x}$. Let ${\mathit{z}}^{\prime }$ be the point selected from a mixture of N $(\delta ,d)$-admissible log-concave distributions with centres in ${\mathbb{B}}_n$. Then for positive $ϵ,\zeta$

$$\mathbf{P}((\mathit{x},{\mathit{z}}^{\prime })\le ϵ\&(\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},\mathit{x})-ϵ\&(\mathit{x},\mathit{x})\ge 1-\zeta )\ge 1-N{\rho }_{\mathit{max}}{V}_n({\mathbb{B}}_n)aexp(-bn)-2cexp(-c^{\prime }{\delta }^3\sqrt{n}),$$

for some constants $a,b,c,c^{\prime }$ that do not depend on the dimensionality.

Proof. 

If follows from (26) and $(\delta ,d)$-admissibility of the distribution from which ${\mathit{x}}^{″}$ has been selected that

$$\mathbf{P}({\mathit{x}}^{\prime }\notin {\mathbf{S}}_0)\le cexp(-c^{\prime }{\delta }^3\sqrt{n})$$

for some ellipsoid ${\mathbf{S}}_0$ (13). Similarly, since ${\mathit{z}}^{\prime }$ is selected from a mixture of N$(\delta ,d)$-admissible log-concave distributions, we have

$$\mathbf{P}\left({\mathit{z}}^{\prime }\notin \bigcup _{i=1}^N{\mathbf{S}}_i\right)\le cexp(-c^{\prime }{\delta }^3\sqrt{n})$$

for some ellipsoids ${\mathbf{S}}_1,\dots ,{\mathbf{S}}_N$ (13). Let E be the event that $(\mathit{x},{\mathit{z}}^{\prime })\le ϵ\&(\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},\mathit{x})-ϵ\&(\mathit{x},\mathit{x})\ge 1-\zeta$. If E does not happen than either (i) ${\mathit{x}}^{\prime }\notin {\mathbf{S}}_0$, or (ii) ${\mathit{z}}^{\prime }\notin {\bigcup }_{i=1}^N{\mathbf{S}}_i$, or (iii) ${\mathit{x}}^{\prime }\in {\mathbf{S}}_0$ and ${\mathit{z}}^{\prime }\in {\bigcup }_{i=1}^N{\mathbf{S}}_i$, but E still does not happen. The probabilities of (i) and (ii) are at most $cexp(-c^{\prime }{\delta }^3\sqrt{n})$, while the probability of (iii) is at most $N{\rho }_{\max }{V}_n({\mathbb{B}}_n)aexp(-bn)$ by Proposition 2. □

Exactly the same proof in combination with (27) implies the following version for strongly log-concave distributions.

Proposition 4.

Let $\delta ,\gamma >0$ and infinite sequence $d=(d_1>d_2>\dots )$ with each $d_i>0$ and $d_i\to 0$ be fixed. Let $\mathit{x}\in {\mathbb{B}}_n$ be a random point from a distribution in the unit ball with the bounded probability density $\rho (x)\le {\rho }_{\mathit{max}}$. Let ${\mathit{x}}^{″}$ be a point selected from some $(\delta ,d)$-admissible γ-SLC distribution, and let ${\mathit{x}}^{\prime }={\mathit{x}}^{″}-\mathbb{E}[{\mathit{x}}^{″}]+\mathit{x}$. Let ${\mathit{z}}^{\prime }$ be the point selected from a mixture of N $(\delta ,d)$-admissible γ-SLC distributions with centres in ${\mathbb{B}}_n$. Then for positive $ϵ,\zeta$

$$\mathbf{P}((\mathit{x},{\mathit{z}}^{\prime })\le ϵ\&(\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},\mathit{x})-ϵ\&(\mathit{x},\mathit{x})\ge 1-\zeta )\ge 1-N{\rho }_{\mathit{max}}{V}_n({\mathbb{B}}_n)aexp(-bn)-2cexp(-c^{\prime }{\delta }^{4}n),$$

for some constants $a,b,c,c^{\prime }$ that do not depend on the dimensionality.

3.4. The Superstatistic form of the Prototype Stochastic Separation Theorem

Theorem 1 evaluates the probability that a random point $\mathit{x}\in {\mathbb{B}}_n$ with bounded probability density is $\alpha$-Fisher separable from an exponentially large finite set Y and demonstrates that under some natural conditions this probability tends to zero when dimension n tends to ∞. This phenomenon has a simple explanation: for any $\mathit{y}\in {\mathbb{B}}_n$ the set of such $\mathit{x}\in {\mathbb{B}}_n$ that $\mathit{x}$ is not $\alpha$-Fisher separable from $\mathit{y}$ is a ball with radius $\parallel \mathit{y}\parallel /(2\alpha )<1$ and the fraction of this volume in ${\mathbb{B}}_n$ decays as

$${\left(\frac{\parallel \mathit{y}\parallel }{2\alpha }\right)}^n.$$

These arguments can be generalised with some efforts for the situation when we consider an elliptic granule instead of a random point $\mathit{x}$ and an arbitrary probability distribution instead of a finite set Y. Instead of the estimate of the probability of a point $\mathit{x}$ falling into a the ball of excluded volume (7), we use the following proposition for separability of a random point ${\mathit{x}}^{\prime }$ of a granule ${\mathbf{S}}_{\mathit{x}}$ with a random centre $\mathit{x}$ from an arbitrary point ${\mathit{z}}^{\prime }\in {\mathbb{B}}_n$.

Proposition 5.

Let ${\mathbf{S}}_{\mathit{x}}$ be the granule defined in Proposition 2. Let ${\mathit{x}}^{\prime }$ be the point selected uniformly at random from ${\mathbf{S}}_{\mathit{x}}$. Let ${\mathit{z}}^{\prime }\in {\mathbb{B}}_n$ be an arbitrary (non-random) point. Then for positive $ϵ,\zeta$

$$\mathbf{P}((\mathit{x},{\mathit{z}}^{\prime })\le ϵ\&(\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},\mathit{x})-ϵ\&(\mathit{x},\mathit{x})\ge 1-\zeta )\ge 1-{\rho }_{\mathit{max}}{V}_n({\mathbb{B}}_n)aexp(-bn),$$

where the constants $a,b$ do not depend on the dimensionality.

Proof. 

The fact that

$$\mathbf{P}((\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},\mathit{x})-ϵ\&(\mathit{x},\mathit{x})\ge 1-\zeta )\ge 1-{\rho }_{\max }{V}_n({\mathbb{B}}_n)aexp(-bn)$$

is proved in Theorem 4, while the fact that

$$\mathbf{P}((\mathit{x},{\mathit{z}}^{\prime })\le ϵ)\ge 1-{\rho }_{\max }{V}_n({\mathbb{B}}_n)aexp(-bn)$$

follows from Lemma 1. □

Propositions 3 and 4 can be straightforwardly generalised in the same way

Proposition 6.

Let $\delta >0$ and infinite sequence $d=(d_1>d_2>\dots )$ with each $d_i>0$ and $d_i\to 0$ be fixed. Let $\mathit{x}\in {\mathbb{B}}_n$ be a random point from a distribution in the unit ball with the bounded probability density $\rho (x)\le {\rho }_{\mathit{max}}$. Let ${\mathit{x}}^{″}$ be a point selected from some $(\delta ,d)$-admissible log-concave distribution, and let ${\mathit{x}}^{\prime }={\mathit{x}}^{″}-\mathbb{E}[{\mathit{x}}^{″}]+\mathit{x}$. Let ${\mathit{z}}^{\prime }\in {\mathbb{B}}_n$ be an arbitrary (non-random) point. Then for positive $ϵ,\zeta$

$$\mathbf{P}((\mathit{x},{\mathit{z}}^{\prime })\le ϵ\&(\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},\mathit{x})-ϵ\&(\mathit{x},\mathit{x})\ge 1-\zeta )\ge 1-{\rho }_{\mathit{max}}{V}_n({\mathbb{B}}_n)aexp(-bn)-cexp(-c^{\prime }{\delta }^3\sqrt{n}),$$

for some constants $a,b,c,c^{\prime }$ that do not depend on the dimensionality.

Proposition 7.

Let $\delta ,\gamma >0$ and infinite sequence $d=(d_1>d_2>\dots )$ with each $d_i>0$ and $d_i\to 0$ be fixed. Let $\mathit{x}\in {\mathbb{B}}_n$ be a random point from a distribution in the unit ball with the bounded probability density $\rho (x)\le {\rho }_{\mathit{max}}$. Let ${\mathit{x}}^{″}$ be a point selected from some $(\delta ,d)$-admissible γ-SLC distribution, and let ${\mathit{x}}^{\prime }={\mathit{x}}^{″}-\mathbb{E}[{\mathit{x}}^{″}]+\mathit{x}$. Let ${\mathit{z}}^{\prime }\in {\mathbb{B}}_n$ be an arbitrary (non-random) point. Then for positive $ϵ,\zeta$

$$\mathbf{P}((\mathit{x},{\mathit{z}}^{\prime })\le ϵ\&(\mathit{x},{\mathit{x}}^{\prime })\ge (\mathit{x},\mathit{x})-ϵ\&(\mathit{x},\mathit{x})\ge 1-\zeta )\ge 1-{\rho }_{\mathit{max}}{V}_n({\mathbb{B}}_n)aexp(-bn)-cexp(-c^{\prime }{\delta }^{4}n),$$

for some constants $a,b,c,c^{\prime }$ that do not depend on the dimensionality.

We remark that because Propositions 5–7 hold for an arbitrary (non-random) point ${\mathit{z}}^{\prime }\in {\mathbb{B}}_n$, they also hold for point selected from any probability distribution within ${\mathbb{B}}_n$, and in particular if point ${\mathit{z}}^{\prime }$ selected uniformly at random from any set $D\subset {\mathbb{B}}_n$.

3.5. Compact Embedding of Patterns and Hierarchical Universe

Stochastic separation theorems tell us that in large dimensions, randomly selected data points (or clusters of data) can be separated by simple and explicit functionals from an existing dataset with high probability, as long as the dataset is not too large (or the number of data clusters is not too large). The number of data points (or clusters) allowed in conditions of these theorems is bounded from above by an exponential function of dimension. Such theorems for data points (see, for example, Teorem 1 and [13]) or clusters (Theorems 2–4) are valid for broad families of probability distributions. Explicit estimations of probability to violate the separability property were found.

There is a circumstance that can devalue this (and many other) probabilistic results in high dimension. We almost never know the probability of a multivariate data distribution beyond strong simplification assumptions. In the postclassical world, observations cannot really help because we never have enough data to restore the probability density (again, strong simplification like independence assumption or dimensionality reduction can help, but this is not a general multidimensional case). A radical point of view is possible, according to which there is no such thing as a general multivariate probability distribution, since it is unobservable.

In the infinite-dimensional limit the situation can look simpler: instead of finite but small probabilities that decrease and tend to zero with increasing dimension (like in (21) and (23)) some statements become generic and hold ‘almost always’. Such limits for concentrations on spheres and their equators were discussed by Lévy [71] as an important part of the measure concentration effects. In physics, this limit corresponds to the so-called thermodynamic limit of statistical mechanics [72,73]. In the infinite-dimensional limit many statements about high or low probabilities transform into 0-1 laws: something happens almost always or almost newer. The original Kolmogorov 0-1 law states, roughly speaking, that an event that depends on an infinite collection of independent random variables but is independent of any finite subset of these variables has probability zero or one (for precise formulation we refer to the monograph [74]). The infinite-dimensional 0-1 asymptotic might bring more light and be more transparent than the probabilistic formulas.

From the infinite-dimensional point of view, the ‘elliptic granule’ (13) with decaying sequence of diameters $d_1>d_2>\dots$ ($d_i>0$, $d_i\to 0$) is a compact. The specific elliptic shape used in Theorem 3 is not very important and many generalisations are possible for the granules with decaying sequence of diameters. The main idea, from this point of view, is compact embedding of specific patterns into general population of data. This point of view was influenced by the hierarchy of Sobolev Embedding Theorems where the balls of embedded spaces appear to be compact in the image space.

The finite-dimensional hypothesis about granular structure of the datasets can be transformed into the infinite-dimensional view about compact embedding: the patterns correspond to the compact subsets of the dataspace. Moreover, this hypothesis can be extended to the hypothesis about hierarchical structure (Figure 5): the data that correspond to a pattern also have the intrernal granular structure. To reveal this structure, we can apply centralisation and whitening to a granule. After that, the granule will transform into a new unit ball, the external set (the former ‘Universe’) will typically become infinitely far (‘invisible’), and the internal structure can be seeking in the form of collection of compact granules in new topology.

It should be stressed that this vision is not a theorem. It is proposed instead of typical dominance of smooth or even uniform distributions that populate theoretical studies in machine learning. On another hand, hierarchical structure was observed in various data analytics exercises: if there exists a natural semantic structure then we expect that data have the corresponding cluster structure. Moreover, various preprocessing operations make this structure more visible (see, for example, discussion of preprocessing in Appendix A).

The compact embedding idea was recently explicitly used in data analysis (see, for example, [75,76,77]).

The infinite-dimensional representation and compact embedding hypothesis brings light to the very popular phenomenon of vulnerability of AI decisions in high-dimension world. According to recent research, such vulnerability seems to be a generic property of various formalisations of learning and attack processes in high-dimensional systems [78,79,80].

Let Q be an infinite-dimensional Banach space. The patterns, representations of a pattern, or their images in an observer systems, etc. are modelled below by compact subsets of Q.

Theorem 5 (Theorem of high-dimensional vulnerability).

Consider two compact sets, $K_{0,1}\subset Q$. For almost every $\mathit{y}\in Q$ there exists such continuous linear functional $\mathit{l}$ on Q, $\mathit{l}\in Q^{\ast }$, that

$$\mathit{l}({\mathit{x}}_{\mathbf{1}}-{\mathit{x}}_{\mathbf{0}})>0forall{\mathit{x}}_{\mathbf{0}}\in K_0,{\mathit{x}}_{\mathbf{1}}\in (K_1+\mathit{y}).$$

(28)

In particular, for every $\epsilon >0$ there exist such $\mathit{y}\in Q$ and continuous linear functional $\mathit{l}$ on Q, $\mathit{l}\in Q^{\ast }$, that $\parallel \mathit{y}\parallel <\epsilon$ and (28) holds. If (28) holds, then $K_0\cap (K_1+\mathit{y})=\oslash$. The perturbation $\mathit{y}$ takes $K_1$ out of the intersection with $K_0$. Moreover, linear separation of $K_0$ and perturbed $K_1$ (i.e., $(K_1+\mathit{y})$) is possible for almost always (28) (for almost any perturbation).

The definition of “almost always” is clarified in detail in Appendix B. The set of exclusions, i.e., the perturbations that do not satisfy (28) in Theorem 5, is completely thin in the following sense, according to Definition A1. A set $Y\subset Q$ is completely thin, if for any compact space K the set of continuous maps $\Psi :K\to Q$ with non-empty intersection $\Psi (K)\cap Y\ne \oslash$ is set of first Bair category in the Banach space $C(K,Q)$ of continuous maps $K\to Q$ equipped by the maximum norm.

Proof of Theorem 5.

Let $\overline{\mathrm{co}}(V)$ be a closed convex hull of a set $V\subset Q$. The following sets are convex compacts in Q: $\overline{\mathrm{co}}(K_0)$, $\overline{\mathrm{co}}(K_1)$, and $\overline{\mathrm{co}}(K_0)-\overline{\mathrm{co}}(K_1)$. Let

$$\mathit{y}\notin (\overline{\mathrm{co}}(K_0)-\overline{\mathrm{co}}(K_1)).$$

(29)

Then the set $\overline{\mathrm{co}}(K_1)+\mathit{y}-\overline{\mathrm{co}}(K_0)$ does not contain zero. It is a convex compact set. According to the Hahn–Banach separation theorem [81], there exists a continuous linear separating functional $\mathit{l}\in Q^{\ast }$ that separates the convex compact $\overline{\mathrm{co}}(K_1)+\mathit{y}-\overline{\mathrm{co}}(K_0)$ from 0. The same functional separates its subset, $K_1+\mathit{y}-K_0$ from zero, as required.

The set of exclusions, $\overline{\mathrm{co}}(K_0)-\overline{\mathrm{co}}(K_1)$ (see (29)) is a compact convex set in Q. According to Riesz’s theorem, it is nowhere dense in Q [81]. Moreover, for any compact space K the set of continuous maps $\Psi :K\to Q$ with non-empty intersection $\Psi (K)\cap Y\ne \oslash$ is a nowhere dense subset of Banach space $C(K,Q)$ of continuous maps $K\to Q$ equipped by the maximum norm.

Indeed, let $\Psi (K)\cap Y\ne \oslash$. The set $\Psi (K)$ is compact. Therefore, as it is proven, an arbitrary small perturbation $\mathit{y}$ exists that takes $\Psi (K)$ out of the intersection with Y: $(\Psi (K)+\mathit{y})\cap Y=\oslash$. The minimal value

$$\underset{{\mathit{x}}_{\mathbf{1}}\in (\Psi (K)+\mathit{y}),{\mathit{x}}_{\mathbf{2}}\in Y}{min}\parallel {\mathit{x}}_{\mathbf{1}}-{\mathit{x}}_{\mathbf{2}}\parallel =\delta >0$$

exists and is positive because compactness $(\Psi (K)+\mathit{y})$ and Y.

Therefore, ${\Psi }^{\prime }(K)\cap Y=\oslash$ for all ${\Psi }^{\prime }$ from a ball of maps in $C(K,Q)$

$$\left\{{\Psi }^{\prime }\left|\parallel {\Psi }^{\prime }-(\Psi +\mathit{y})\parallel <\frac{\delta }{2}\right.\right\}$$

This proofs that the set of continuous maps $\Psi :K\to Q$ with non-empty intersection $\Psi (K)\cap Y$ is a nowhere dense subset of $C(K,Q)$. Thus, the set of exclusions is completely thin. □

The following Corollary is simple but it may seem counterintuitive:

Corollary 4.

A compact set $K_0\subset Q$ can be separated from a countable set of compacts $K_i\subset Q$ by a single and arbitrary small perturbation $\mathit{y}$ ($\mathit{y}<\epsilon$ for an arbitrary $\epsilon >0$):

$$(K_0+\mathit{y})\cap K_i=\oslash .$$

Almost all perturbations $\mathit{y}\in Q$ provide this separation and the set of exclusions is completely thin.

Proof. 

First, refer to Theorem 5 (for separability of $K_0$ from one $K_i$). Then mention that countable union of completely thin set of exclusions is completely thin, whereas the whole Q is not (according to the Bair theorem, Q is not a set of first category). □

Separability theorems for compactly embedded patterns might explain why the vulnerability to adversarial perturbations and stealth attacks is typical for high-dimensional AI systems based on data [78,79]. Two properties are important simultaneously: high dimensionality and compactness of patterns.

4. Multi-Correctors of AI Systems

4.1. Structure of Multi-Correctors

In this section, we present the construction of error correctors for multidimensional AI systems operating in a multidimensional world. It combines a set of elementary correctors (Figure 2) and a dispatcher that distributes the tasks between them. The population of possible errors is presented as a collection of clusters. Each elementary corrector works with its own cluster of situations with a high risk of error. It includes a binary classifier that separates that cluster from the rest of situations. Dispatcher is based on an unsupervised classifier that performs cluster analysis of errors, selects the most appropriate cluster for each operating situation, transmits the signals for analysis to the corresponding elementary corrector, and requests the correction decision from it (Figure 6).

In brief, operation of multi-correctors (Figure 6) can be described as follows:

• The correction system is organised as a set of elementary correctors, controlled by the dispatcher;
• Each elementary corrector ‘owns’ a certain class of errors and includes a binary classifier that separates situations with a high risk of these errors, which it owns, from other situations;
• For each elementary corrector, a modified rule is set for operating of the corrected AI system in a situation with a high risk of error diagnosed by the classifier of this corrector;
• The input to the corrector is a complete vector of signals, consisting of the input, internal, and output signals of the corrected Artificial Intelligence system, (as well as, if available, any other available attributes of the situation);
• The dispatcher distributes situations between elementary correctors;
• The decision rule, based on which the dispatcher distributes situations between elementary correctors, is formed as a result of cluster analysis of situations with diagnosed errors;
• Cluster analysis of situations with diagnosed errors is performed using an online algorithm;
• Each elementary corrector owns situations with errors from a single cluster;
• After receiving a signal about the detection of new errors, the dispatcher modifies the definition of clusters according to the selected online algorithm and accordingly modifies the decision rule, on the basis of which situations are distributed between elementary correctors;
• After receiving a signal about detection of new errors, the dispatcher chooses an elementary corrector, which must process the situation, and the classifier of this corrector learns according to a non-iterative explicit rule.

Flowcharts of these operations are presented in Appendix C. Multi-correctors satisfy the following requirements:

• Simplicity of construction;
• Correction should not damage the existing skills of the system;
• Speed (fast non-iterative learning);
• Correction of new errors without destroying previous corrections.

For implementation of this structure, the construction of classifiers for elementary correctors and the online algorithms for clustering should be specified. For elementary correctors many choices are possible, for example:

• Fisher’s linear discriminant is simple, robust, and is proven to be applicable in high-dimensional data analysis [13,32];
• Kernel versions of non-iterative linear discriminants extend the area of application of the proposed systems, their separability properties were quantified and tested [36];
• Decision trees of mentioned elementary discriminants with bounded depth. These algorithms require small (bounded) number of iterations.

The population of clustering algorithms is huge [82]. The first choice for testing of multi-correctors [83] was partitioning around centroids by k means algorithm. The closest candidates for future development are multi-centroid algorithms that present clusters by networks if centroids (see, for example, [84]. This approach to clustering meets the idea of compact embedding, when the network of centres corresponds to the $\epsilon$-net approximating the compact.

4.2. Multi-Correctors in Clustered Universe: A Case Study

4.2.1. Datasets

In what follows our use-cases will evolve around a standard problem of supervised multi-class classification. In order to be specific and to ensure reproducibility of our observations and results, we will work with a well-known and widely available CIFAR-10 dataset [85,86]. The CIFAR-10 dataset is a collection of $32\times 32$ colour images that are split across 10 classes:

‘airplane’, ‘automobile’, ‘bird’, ‘cat’, ‘deer’, ‘dog’, ‘frog’, ‘horse’, ‘ship’, ‘truck’

with ‘airplane’ being a label of Class 1, and ‘truck’ being a label of Class 10. The original CIFAR-10 dataset is further split into two subsets: a training set containing 5000 images per class (total number of images in the training set is 50,000), and a testing set with 1000 images per class (total number of images in the testing set is 10,000).

4.2.2. Tasks and Approach

We focus on two fundamental tasks: for a given legacy classifier:

• (Task 1) devise an algorithm to learn a new class without catastrophic forgetting and retraining, and;
• (Task 2) develop an algorithm to predict classification errors in the legacy classifier.

Let us now specify these tasks in more detail.

As a legacy classifier we have used a deep convolutional neural network whose structure is shown in

Table 4. Architecture of the legacy classifier.

Layer Number	Type	Size
1	Input	$32\times 32\times 3$
2	Conv2d	$4\times 4\times 64$
3	ReLU
4	Batch normalization
5	Dropout 0.25
6	Conv2d	$2\times 2\times 64$
7	ReLU
8	Batch normalization
9	Dropout 0.25
10	Conv2d	$3\times 3\times 32$
11	ReLU
12	Batch normalization
13	Dropout 0.25
14	Conv2d	$3\times 3\times 32$
15	ReLU
16	Batch normalization
17	Maxpool	pool size $2\times 2$, stride $2\times 2$
18	Dropout 0.25
19	Fully connected	128
20	ReLU
21	Dropout 0.25
22	Fully connected	128
23	ReLU
24	Dropout 0.25
25	Fully connected	9
26	Softmax	9

. The network’s training set comprised 45,000 images corresponding to Class 1–9 (5000 images per class), and the test set comprised 9000 images from the CIFAR-10 testing set (1000 images per class). No data augmentation was invoked as a part of the training process. The network by stochastic gradient descent with the momentum parameter was set to 0.9 and mini-batches were of size 128. Overall, we trained the network over 70 epochs executed in 7 training episodes of 10-epoch training, and the learning rate was equal to $0.1/(1+0.001k)$, where k is the index of a training instance (a mini-batch) within a training episode.

The network’s accuracy, expressed as the percentage of correct classifications, was 0.84 and 0.73 on the training and testing sets, respectively (rounded to the second decimal point). The network was trained in MATLAB R2021a. Each 10-epoch training episode took approximately 1.5 h to complete on an HP Zbook 15 G3 laptop with a Core i7-6820HQ CPU, 16 Gb of RAM, and Nvidia Quadro 1000 M GPU.

Task 1 (learning a new class). Our first task was to equip the trained network with a capability to learn a new class without expensive retraining. In order to achieve this aim we adopted an approach and algorithms presented in [25,83]. According to this approach, for every input image $\mathit{u}$ we generated its latent representation $\mathit{x}$ of which the composition is shown in

Table 5. Latent representation of an image.

Attributes	${\mathit{x}}_1,\dots ,{\mathit{x}}_9$	${\mathit{x}}_{10},\dots ,{\mathit{x}}_{137}$	${\mathit{x}}_{138},\dots ,{\mathit{x}}_{265}$	${\mathit{x}}_{266},\dots ,{\mathit{x}}_{393}$
Layers	26 (Softmax)	19 (Fully connected)	22 (Fully connected)	23 (ReLU)

. In our experiments we kept all dropout layers active after training. This was implemented by using “forward” method instead of “predict” when accessing feature vectors of relevant layers in the trained network. The procedure enabled us to simulate an environment in which AI correctors operate on data that are subjected to random perturbations.

This process constituted our legacy AI system.

Using these latent representations of images, we formed two sets: $\mathcal{X}$ and $\mathcal{Y}$. The set $\mathcal{X}$ contained latent representations of the new class (Class 10—‘trucks’) from the CIFAR-10 training set (5000 images), and the set $\mathcal{Y}$ contained latent representations of all other images in CIFAR-10 training set (45,000 images). These sets have then been used to construct a multi-corrector in accordance with the following algorithm presented in [83].

Integration logic of the multi-corrector into the final system was as follows [83]:

Remark 1.

Since the set $\mathcal{Y}$ corresponds to data samples from previously learned classes, a positive response in the multi-corrector (condition $({\mathit{w}}_{\ell },{\mathit{x}}_w)>\theta$ holds) ‘flags’ that this data point is to be associated with classes that have already been learned (Classes 1–9). Absence of a positive response indicates that the data point is to be associated with the new class (Class 10).

Task 2 (predicting errors of a trained legacy classifier). In addition to learning a new class without retraining, we considered the problem of predicting correct performance of a trained legacy classifier. In this setting, the set $\mathcal{X}$ of vectors corresponding to incorrect classifications on CIFAR-10 training set, and the set $\mathcal{Y}$ contained latent representations of images form CIFAR-10 training set that have been correctly classified. Similar to the previous task, predictor of the classifier’s error was constructed in accordance with Algorithms 1 and 2.

Testing protocols. Performance of the algorithms was assessed on CIFAR-10 testing set. For Task 1, we tested how well our new system—the legacy network shown in Table 4 combined with the multi-corrector constructed by Algorithms 1 and 2—performs on images from CIFAR-10 testing set. For Task 2, we assessed how well the multi-corrector, trained on CIFAR-10 training set, predicts errors of the legacy network for images of 9 classes (Class 1—9) taken from CIFAR-10 testing set.

Algorithm 1: (Few-shot AI corrector [83]: 1NN version. Training). Input: sets $\mathcal{X}$, $\mathcal{Y}$; the number of clusters, k; threshold, $\theta$ (or thresholds ${\theta }_1,\dots ,{\theta }_k$).

Determining the centroid $\overline{\mathit{x}}$ of the $\mathcal{X}$. Generate two sets, ${\mathcal{X}}_c$, the centralised set $\mathcal{X}$, and ${\mathcal{Y}}^{\ast }$, the set obtained from $\mathcal{Y}$ by subtracting $\overline{\mathit{x}}$ from each of its elements. Construct Principal Components for the centralised set ${\mathcal{X}}_c$. Using Kaiser, broken stick, conditioning rule, or otherwise, select $m\le n$ Principal Components, $h_1,\dots ,h_m$, corresponding to the first largest eivenvalues ${\lambda }_1\ge \cdots \ge {\lambda }_m>0$ of the covariance matrix of the set ${\mathcal{X}}_c$, and project the centralized set ${\mathcal{X}}_c$ as well as ${\mathcal{Y}}^{\ast }$ onto these vectors. The operation returns sets ${\mathcal{X}}_r$ and ${\mathcal{Y}}_r^{\ast }$, respectively: $$\begin{array}{cc}\hfill {\mathcal{X}}_r& =\{\mathit{x}|\mathit{x}=H\mathit{z},\mathit{z}\in {\mathcal{X}}_c\}\hfill \\ \hfill {\mathcal{Y}}_r^{\ast }& =\{\mathit{y}|\mathit{y}=H\mathit{z},\mathit{z}\in {\mathcal{Y}}^{\ast }\},H=\left(\begin{array}{c}{h}_1^T\\ ⋮\\ h_m^T\end{array}\right).\hfill \end{array}$$ Construct matrix W $$W=\mathrm{diag}\left(\frac{1}{\sqrt{{\lambda }_1}},\dots ,\frac{1}{\sqrt{{\lambda }_m}}\right)$$ corresponding to the whitening transformation for the set ${\mathcal{X}}_r$. Apply the whitening transformation to sets ${\mathcal{X}}_r$ and ${\mathcal{Y}}_r^{\ast }$. This returns sets ${\mathcal{X}}_w$ and ${\mathcal{Y}}_w^{\ast }$: $$\begin{array}{cc}\hfill {\mathcal{X}}_w& =\{\mathit{x}|\mathit{x}=W\mathit{z},\mathit{z}\in {\mathcal{X}}_r\}\hfill \\ \hfill {\mathcal{Y}}_w^{\ast }& =\{\mathit{y}|\mathit{y}=W\mathit{z},\mathit{z}\in {\mathcal{Y}}_r^{\ast }\}.\hfill \end{array}$$ Cluster the set ${\mathcal{Y}}_w^{\ast }$ into k clusters ${\mathcal{Y}}_{w,1}^{\ast },\dots ,{\mathcal{Y}}_{w,k}^{\ast }$ (using e.g. the k-means algorithm or otherwise). Let ${\overline{\mathit{y}}}_1,\dots ,{\overline{\mathit{y}}}_k$ be their corresponding centroids. For each pair $({\mathcal{X}}_w,{\mathcal{Y}}_{w,i}^{\ast })$, $i=1,\dots ,k$, construct (normalised) Fisher discriminants ${\mathit{w}}_1,\dots ,{\mathit{w}}_k$: $${\mathit{w}}_i=\frac{{(\mathrm{Cov}({\mathcal{X}}_w)+\mathrm{Cov}({\mathcal{Y}}_{w,i}^{\ast }))}^{-1}{\overline{\mathit{y}}}_i}{\parallel {(\mathrm{Cov}({\mathcal{X}}_w)+\mathrm{Cov}({\mathcal{Y}}_{w,i}^{\ast }))}^{-1}{\overline{\mathit{y}}}_i\parallel }.$$ An element $\mathit{z}$ is associated with the set ${\mathcal{Y}}_{w,i}^{\ast }$ if $({\mathit{w}}_i,\mathit{z})>\theta$ and with the set ${\mathcal{X}}_w$ if $({\mathit{w}}_i,\mathit{z})\le \theta$. If multiple thresholds are given then an element $\mathit{z}$ is associated with the set ${\mathcal{Y}}_{w,i}^{\ast }$ if $({\mathit{w}}_i,\mathit{z})>{\theta }_i$ and with the set ${\mathcal{X}}_w$ if $({\mathit{w}}_i,\mathit{z})\le {\theta }_i$. Output: vectors ${\mathit{w}}_i$, $\overline{\mathit{x}}$, $i=1,\dots ,k$, matrices H and W.

Algorithm 2: (Few-shot AI corrector [83]: 1NN version. Deployment). Input: a data vector $\mathit{x}$, the set’s $\mathcal{X}$ centroid vector $\overline{\mathit{x}}$, matrices H, W, the number of clusters, k, cluster centroids ${\overline{\mathit{y}}}_1,\dots ,{\overline{\mathit{y}}}_k$, threshold, $\theta$ (or thresholds ${\theta }_1,\dots ,{\theta }_k$), discriminant vectors, ${\mathit{w}}_i$, $i=1,\dots ,k$.

Compute $${\mathit{x}}_w=WH(\mathit{x}-\overline{\mathit{x}})$$ Determine $$\ell =arg\underset{i}{min}\parallel {\mathit{x}}_w-{\overline{\mathit{y}}}_i\parallel .$$ Associate the vector $\mathit{x}$ with the set $\mathcal{Y}$ if $({\mathit{w}}_{\ell },{\mathit{x}}_w)>\theta$ and with the set $\mathcal{X}$ otherwise. If multiple thresholds are given then associate the vector $\mathit{x}$ with the set $\mathcal{Y}$ if $({\mathit{w}}_{\ell },{\mathit{x}}_w)>{\theta }_{\ell }$ and with the set $\mathcal{X}$ otherwise. Output: a label attributed to the vector $\mathit{x}$.

4.2.3. Results

Task 1 (learning a new class). Performance of the multi-corrector in the task of learning a new class is illustrated in Figure 7. In these experiments, we projected onto the first 20 principal components. The rationale for choosing these 20 principal components was that for these components the ratio of the largest eigenvalue to the eigenvalue that is associated with the principal component is always smaller than 10. The figure shows ROC curves in which true positives are images from the new class and identified as a new class, and False positives are defined as images from already learned classes (Classes 1–9) but identified as a new class (Class 10) by the combined system. As we can see from Figure 7, performance of the system saturates at about 10 clusters which indicates a peculiar granular structure of the data universe in this example: clusters are apparently not equal in terms of their impact on the overall performance, and the benefit of using more clusters decays rapidly as the number of clusters grows.

We note that the system performance and generalisation depends on both ambient dimension (the number of principal components used) and the number of clusters. This phenomenon is illustrated in in Figure 8. When the number of dimensions increases (top row in Figure 8), the gap between a single-cluster corrector and a multi-cluster corrector narrows. Yet, as can be observed from this experiment, the system generalises well.

When the number of clusters increases from 10 to 300, the system overfits. This is not surprising as given the size of our training set (50,000 images to learn from) splitting the data into 300 clusters implies that each 100-dimensional discriminant in Algorithm 1 is constructed, on average, from mere 170 samples. The lack of data to learn from and ‘diffusion’ and shattering of clusters in high dimension could be contributors to the instability. Nevertheless, as the right plot shows, the system still generalises at the level that is similar to the 10-cluster scenario.

When the ambient dimension increases further we observe a dramatic performance collapse for the multi-corrector constructed by Algorithms 1 and 2. Now 300-dimensional vectors are built from on average 170 points. The procedure is inherently unstable and in this sense such results are expected in this limit.

Task 2 (predicting errors). A very similar picture occurs in the task of predicting errors of legacy classifiers. For our specific case, performance of 10-cluster multi-corrector with projection onto 20 principal components in shown in Figure 9. In this task, true positives are errors of the original classifier which have been correctly identified as errors by the corrector. False positives are data correctly classified by the original deep neural network but which nevertheless have been labelled as errors by the corrector. According to Figure 9, the multi-corrector model generalises well and delivers circa 70% specificity and sensitivity on the test set.

Another interesting phenomenon illustrated by Figure 9 is the apparent importance of how the information from the legacy AI model is aggregated into correcting cascades. Dashed lines in Figure 9 show what happens if latent representations are formed by signals taken from layers 26 and 19 only. In this case the impact of clustering becomes less pronounced, suggesting the importance of feature selection for optimal performance.

Computational efficiency. Computational costs of constructing multi-correctors is remarkably small. For example, learning a new class with a 10-cluster multi-corrector and 20 principal components took 1.32 s on the same hardware used to train the original legacy classifier. When the number of clusters and dimension increases to 300 and 300, respectively, the amount of time needed to construct the multi-corrector was 37.7 s. These figures show that not only clustered universes and multi-correctors are feasible in applications but they are also extremely efficient computationally. We do not wish to suggest that they are a replacement of deeper retraining. Yet, as we see from these experiments, they can be particularly efficient in the tasks of incremental learning—learning an additional class in a multi-class problem—if implemented appropriately.

4.2.4. Dimensionality and Multi-Corrector Performance

The CIFAR-10 training set contains 5000 images per class, and the testing set contains 1000 image per class. The total number of data samples is 60,000. Dimension of the input space is 3072. Dimension of the space of latent representation is 393. The shortened feature space with coordinates $x_1-x_{137}$ is also used. Three versions of PCA dimensionality reduction were tested, with 20, 100, and 300 principal components. We can see that the number of samples significantly exceeds all the dimensions (60,000 versus 20, 100, 137, 300, and 393). The question arises: is this classical or already postclassical zone of data dimensionality (see Figure 3)?

Compare the number of samples to the critical size $|Y|$ of the dataset Y that allows one to separate a random point $\mathit{x}$ from the set Y by Fisher’s discriminant (Definition 1) with threshold $\alpha =0.8$ and probability $p=1-\delta =0.99$. Theorem 1 gives this estimate. If $\mathit{x}$ is uniformly distributed in a ball then, according to Theorem 1, we produce the following table.

Table 6. The upper bound on $|Y|$ that guarantees separation of a random point $\mathit{x}$, uniformly distributed in a ball, from set Y by Fisher’s discriminant with probability 0.99 for $\alpha =0.8$, in various dimensions.

n	20	100	137	300	393
$|Y|\le$	$1.21\times {10}^2$	$2.58\times {10}^{18}$	$9.21\times {10}^{25}$	$1.72\times {10}^{59}$	$1.65\times {10}^{78}$

ensures us that for dimensions 100, 137, 300, and 393 the CIFAR-10 dataset is very deeply in the postclassical area. The only question appeared for dimension 20. Theorem 1 gives that for this dimension, the postclassical area ends at $|Y|>121$. Nevertheless, the multi-correctors work well in this dimension. The reason for this efficiency could be the fine-grained cluster structure of the dataset. Theorem 1 is true for any dataset Y without any hypothesis about data distribution. It estimates the number of points $|Y|$. On the contrary, according to Theorems 2 and 3, for a fine-grained structure the number of granules should be counted and not the number of points.

Stochastic separation theorems are needed to evaluate the areas of applicability of machine learning algorithms in the multidimensional world of postclassical data. They also provide ideas for developing appropriate algorithms. The first stochastic separation theorems led to elementary correctors (Figure 2) [30,31]. The theorems for data with fine-grained distributions are related to the multi-corrector algorithm. Of course, the detailed structure of multi-correctors may vary, and in this work we considered the first and basic version.

5. Conclusions

In this work, we used the modified Donoho’s definition of postclassical data (Section 2). The postclassical data are defined by relations between the intrinsic dimensionality of the data $dim(DataSet)$ and the logarithm of the number of data samples (2), $dim(DataSet)\gg logN$. In the postclassical area (Figure 3), the classical statistical learning approaches may become useless and the phenomena of curse and blessing of dimensionality become important. Among these phenomena are quasiorthogonality [61,62,63], systematically used in our work, and stochastic separation theorems [13,31].

Distributions of data in real life tasks can be far from any regular distribution. One of the typical phenomena is rich cluster structure. Multi-clustering and recently described hubness phenomena are important in high-dimensional data analysis and it is impossible to analyse the real life datasets without accounting of them [66,87,88,89]. We used the granular distributions as models for multi-clustered data. Three models of clusters are proposed: spherical clusters, elliptic clusters, and superstatistical model, where clusters are represented by the peaks of distribution density and the whole distribution is a random mixture of these such peaks.

Hypothesis of compactness of granules has different forms for these cluster models. For spherical clusters, compactness is considered as a relatively small diameter of the granules comparing to the data standard deviation. This approach is close to the Duin measurement of compactness [58]. For the elliptic granules, the diameter can be large, but the sequence of the main diameters should decay. This idea is borrowed from functional analysis, the theory of Kolmogorov n-width [90,91,92] in its simplest form.

In Section 3, we formulated and proved stochastic separation theorems for fine-grained distributions. Instead of separation of random points we considered separation of clusters. The multi-clustered datasets demonstrate the curse and blessing of dimensionality effects for smaller dimensions than the classical distributions with the same number of data points because these effects depend on the number of clusters and their compactness characteristics, see Theorem 2 for spheric granules, Theorems 3 and 4 for elliptic granules, and Propositions 3–5 for granules modelled by the distribution peaks of different shapes.

The probability of a multivariate real-life data distribution is usually unknown and we never have enough data to restore the probability density for postclassical data. Therefore, in Section 3.5 we developed the infinite-dimensional approach that does not use the unobservable probability distributions. For measure concentration on spheres and equators, infinite-dimensional limit was considered by Lévy in his functional analysis book [71]. Instead of spheric or elliptic granules, just compact subsets are considered and Theorem 5 about separability in families of compact sets explains why the vulnerability to adversarial perturbations and stealth attacks is typical for high-dimensional AI systems based on data [78,79]. Two properties are important simultaneously: high dimensionality and compactness of patterns.

Multi-corrector, a special ideal device for correction of AI errors in the worlds of high-dimensional multi-clustered data, is developed and tested (Section 4). It includes a family of elementary correctors managed by a dispatcher (Figure 6). The dispatcher distributes situations between elementary correctors using a classification model created in the course of cluster analysis of diagnosed errors. Each elementary corrector deals with its own cluster. Multi-correctors are tested on the CIFAR-10 database solving two tasks: (i) learn a new class (without catastrophic forgetting and retraining) and (ii) predict classification errors. Testing was organised for a different number of principal components involved and for a different number of clusters. The tests demonstrates that the multi-corrector model generalises well with appropriate specificity and sensitivity on the test set. The details are presented in Figure 7, Figure 8 and Figure 9.

Several directions of future work have become open. The main challenge is to develop a technology for creating reliable and self-correcting augmented AI ecosystems in which each AI is dressed-up with a cloud of correctors. These correctors increase the reliability of AI by removing errors and at the same time serve as a special storage device—a memory of detected errors for further interiorisation. The correctors also enable knowledge transfer between AIs and can be used to protect their “host” AI from various attacks by repairing the effects of malicious actions. In addition, they may model attacks on AIs [78,79], opening new ways to assess the efficiency of defence measures and protocols employed by AI owners. There are also many special technical questions that require further attention and work. These include the analysis of reducibility of multidimensional data and the development of precise criteria, enabling one to decide if a given dataset is a postclassical dataset, to which our current work applies, or if it is the classical one, to which conventional statistical learning approaches may still be applicable.

6. Discussion

The preprocessing in the postclassical data world (Figure 3 and Appendix A) is a challenging task because no classical statistical methods are applicable when the sample size is much smaller than data dimensionality (the Donoho area (Section 2, (1) [28]). The correlation transformation (Appendix A.1) moves data out of the Donoho area yet, certain specific non-classical effects still persist when the sample size remains much smaller than the exponential of the data dimensionality (2). Dimensionality reduction methods should combine two sets of goals: sensible grouping and extraction of relevant features. For these purposes, combining supervised and unsupervised learning techniques is necessary. Data labels from supervised approaches add sense and context to the subsequent analysis of unlabelled data. The simple geometric methods like supervised PCA, semisupervised PCA (Appendix A.2), and Domain Adaptation PCA (DAPCA) (Appendix A.2) may serve as prototypes of more complex and less controllable approaches. They can also be used to simplify large deep learning systems [93].

Data in postlclassical world are rarefied. At the same time, values of regular functionals on data are concentrated near their median values [44,46]. Combinations of these properties produce the ‘blessing of dimensionality’ [27,28,71]. The most important manifestation of these effects for applied data analysis beyond the central limit theorem are quasiorthogonality [61,62,63] and stochastic separation theorems [13,31]. These results give the theoretical backgrounds for creation of intellectual devices of a new type: correctors of AI systems. In this paper, we presented a new family of stochastic separation theorems for fine-grained data distributions with different geometry of clusters (Section 3). These results enable development of multi-correctors for multidimensional AI with a granular distribution of errors. On real data, such correctors showed better performance than simple correctors.

Various versions of multi-correctors that provide fast and reversible correction of AI errors should be supplemented by an additional special operation of interiorisation of corrections. Accumulation of many corrections will, step by step, spend the blessing of dimensionality resource: after implementing elementary corrections, the probability of success for new correctors may decrease. This can be considered as accumulation of technical debt. In psychology, interiorisation is the process of making skills, attitudes, thoughts, and knowledge an integrated part of one’s own being. For large legacy AI systems, interiorisation of corrections means the supervising retraining of the system. Here a complex “legacy system+multi-corrector” acts as a supervisor and labels the data, while the system itself learns by assimilating the fast flow of generated data.

The construction of correctors with their subsequent interiorisation can be considered as a tool for solving the problem of model degradation and concept drift. An increase in the error rate is a signal of degradation of the model and a systematic decrease in performance [55]. The nature of data changes in time, due to the evolution of the system under analysis. Coping with this phenomena required combination of supervised, semi-supervised, and even unsupervised learning. Semi-supervised and unsupervised methods help to self-assess model degradation in preprocessing mode in real time and modify the classification model and features before actual errors occur [94]. Error correctors provide reversible modification of AI systems without iterative retraining and can assimilate significant concept drift.

We refuse the classical hypothesis of the regularity of the data distribution and assume that the data can have a rich fine-grained structure with many clusters and corresponding peaks in the probability density. In this work, we generalise this framework and ideas to a much richer class of distributions. We introduce a new model of data—a possibly infinite-dimensional data universe with hierarchical structure in which each data cluster has a granular internal structure, etc. The idealised concept of granular Hierarchical Universe (Figure 5) is intended to replace the ideal picture of a smooth unimodal distribution popular in statistical science.

The infinite-dimensional version of theorems about separation of compact clusters and families of such clusters demonstrates the importance of the hypothesis about compact embedding of data clusters (Section 3.5). The hypothesis of images compactness appeared in data analysis and machine learning several times in many different forms. Perhaps, it was first introduced by E.M. Braverman [57]. This was a guess about the data structure in the real world. It is now widely accepted that real data are rarely i.i.d samples from a regular distribution. Getting the right guess about the distribution of data is essential to the success of machine learning.

According to a modern deep learning textbook, “the goal of machine learning research is not to seek a universal learning algorithm or the absolute best learning algorithm. Instead, our goal is to understand what kinds of distributions are relevant to the ’real world’ that an AI agent experiences and what kinds of machine learning algorithms perform well on data drawn from the kinds of data generating distributions we care about” ([15], Section 5.5.2]).