==== Front
Entropy (Basel)
Entropy (Basel)
entropy
Entropy
1099-4300 MDPI 

33287049
10.3390/e22111281
entropy-22-01281
Article
Linear and Fisher Separability of Random Points in the d-Dimensional Spherical Layer and Inside the d-Dimensional Cube
https://orcid.org/0000-0003-2883-6427Sidorov Sergey  https://orcid.org/0000-0003-4542-9233Zolotykh Nikolai * Institute of Information Technologies, Mathematics and Mechanics, Lobachevsky State University, 603950 Nizhni Novgorod, Russia; sergey.sidorov@itmm.unn.ru
* Correspondence: nikolai.zolotykh@itmm.unn.ru
12 11 2020 
11 2020 
22 11 128121 10 2020 10 11 2020 © 2020 by the authors.2020Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).Stochastic separation theorems play important roles in high-dimensional data analysis and machine learning. It turns out that in high dimensional space, any point of a random set of points can be separated from other points by a hyperplane with high probability, even if the number of points is exponential in terms of dimensions. This and similar facts can be used for constructing correctors for artificial intelligent systems, for determining the intrinsic dimensionality of data and for explaining various natural intelligence phenomena. In this paper, we refine the estimations for the number of points and for the probability in stochastic separation theorems, thereby strengthening some results obtained earlier. We propose the boundaries for linear and Fisher separability, when the points are drawn randomly, independently and uniformly from a d-dimensional spherical layer and from the cube. These results allow us to better outline the applicability limits of the stochastic separation theorems in applications.

stochastic separation theoremsrandom points1-convex setlinear separabilityFisher separabilityFisher linear discriminant
==== Body
1. Introduction
It is generally accepted that the modern information world is the world of big data. However, some of the implications of the advent of the big data era remain poorly understood. In his “millennium lecture”, D. L. Donoho [1] described the post-classical world in which the number of features d is much greater than the sample size n: d≫n. It turns out that many phenomena of the post-classical world are already observed if d≫logn, or, more precisely, when ID≫logn, where ID is the intrinsic dimensionality of the data [2]. Classical methods of data analysis and machine learning become of little use in such a situation, because usually they require huge amounts of data. Such an unlimited appetite of classical approaches for data is usually considered as a phenomenon of the “curse of dimensionality”. However, the properties ID≫n or ID≫logn themselves are neither a curse nor a blessing, and can be beneficial.

One of the “post-classical” phenomena is stochastic separability [3,4,5]. If the dimensionality of data is high, then under broad assumptions any sample of the data set can be separated from the rest by a hyperplane (or even Fisher discriminant—as a special case) with a probability close to 1 even the number of samples is exponential in terms of dimensions. Thus, high-dimensional datasets exhibit fairly simple geometric properties.

Recently, stochastic separation theorems have been widely used in machine learning for constructing correctors and ensembles of correctors of artificial intelligence systems [6,7], for determining the intrinsic dimensionality of data sets [8,9], for explaining various natural intelligence phenomena, such as grandmother’s neuron [10,11].

In its usual form a stochastic separation theorem is formulated as follows. A random n-element set in Rd is linearly separable with probability p>1−ϑ, if n<aebd. The exact form of the exponential function depends on the probability distribution that determines how the random set is drawn, and on the constant ϑ (0<ϑ<1). In particular, uniform distributions with different support are considered in [5,12,13,14]. Wider classes of distributions (including non-i.i.d.) are considered in [7]. Roughly speaking, these classes consist of distributions without sharp peaks in sets with exponentially small volume. Estimates for product distributions in the cube and the standard normal distribution are obtained in [15]. General stochastic separation theorems with optimal bounds for important classes of distributions (log-concave distribution, their convex combinations and product distributions) are proposed in [2].

We note that there are many algorithms for constructing a functional separating a point from all other points in a data set (Fisher linear discriminant, linear programming algorithm, support vector machine, Rosenblatt perceptron, etc.). Among all these methods the computationally cheapest is Fisher discriminant analysis [6]. Other advantages of the Fisher discriminant analysis are its simplicity and the robustness.

The papers [5,6,7,12] deal with only Fisher separability, whereas [13,14] considered a (more general) linear separability. A comparison of the estimations for linear and Fisher separability allows us to clarify the applicability boundary of these methods, namely, to answer the question of what d and n are sufficient in order to use only Fisher separability and so that there is no need to search a more sophisticated linear discriminant.

In [13,14], there were obtained estimates for the cardinality of the set of points that guarantee its linear separability when the points are drawn randomly, independently and uniformly from a d-dimensional spherical layer and from the unit cube. These results give more accurate estimates than the bounds obtained in [5,12] for Fisher separability.

Our interest in the study of the linear separability in spherical layers is explained, among other reasons, by the possibility of applying our results to determining the intrinsic dimension of data. After applying PCA to the data points for the selection of the major components and subsequent whitening we can map them to a spherical layer of a given thickness. If the intrinsic dimensionality of the initial set of n points is ID, then we expect that the separability properties of the resulting set of points are similar to the properties of uniformly distributed n points in dimension d. In particular, we can use the theoretical estimates for the separation probability to estimate ID (cf. [8,9]).

Here we give even more precise estimations for the number of points in the spherical layer to guarantee their linear separability. We also consider the case of linear separability of random points inside a cube in more detail than it was done in [13]. In particular, we give estimates for the probability of separability of one point. We also report results of computational experiments comparing the theoretical estimations for the probability of the linear and Fisher separabilities with the corresponding experimental frequencies and discuss them.

2. Definitions
A point X∈Rd is linearly separable from a set M⊂Rd if there exists a hyperplane separated X from M; i.e., there exists AX∈Rd such that (AX,X)>(AX,Y) for all Y∈M.

A point X∈Rd is Fisher separable from the set M⊂Rd if (X,Y)<(X,X) for all Y∈M [6,7].

A set of points {X1,…,Xn}⊂Rd is called linearly separable [5] or 1-convex [3] if any point Xi is linearly separable from all other points in the set, or in other words, the set of vertices of their convex hull, conv(X1,…,Xn), coincides with {X1,…,Xn}. The set {X1,…,Xn} is called Fisher separable if (Xi,Xj)<(Xi,Xi) for all i, j, such that i≠j [6,7].

Fisher separability implies linear separability but not vice versa (even if the set is centered and normalized to unit variance). Thus, if M⊂Rd is a random set of points from a certain probability distribution, then the probability that M is linearly separable is not less than the probability that M is Fisher separable.

Denote by Bd={X∈Rd:∥X∥≤1} the d-dimensional unit ball centered at the origin (∥X∥ means Euclidean norm), rBd is the d-dimensional ball of radius r<1 centered at the origin and Qd=[0,1]d is the d-dimensional unit cube.

Let Mn={X1,…,Xn} be the set of points chosen randomly, independently, according to the uniform distribution on the (1−r)-thick spherical layer Bd\rBd, i.e., on the unit ball with spherical cavity of radius r. Denote by P∘(d,r,n) the probability that Mn is linearly separable, and by P∘F(d,r,n) the probability that Mn is Fisher separable. Denote by P1∘(d,r,n) the probability that a random point chosen according to the uniform distribution on Bd\rBd is separable from Mn, and by P1∘F(d,r,n) the probability that a random point is Fisher separable from Mn.

Now let Mn={X1,…,Xn} be the set of points chosen randomly, independently, according to the uniform distribution on the cube Qd. Let P□(d,n) and P□F(d,n) denote the probabilities that Mn is linearly separable and Fisher separable, respectively. Let P1□(d,n) and P1□F(d,n) denote the probabilities that a random point chosen according to the uniform distribution on Qd is separable and Fisher separable from Mn, respectively.

3. Previous Results
3.1. Random Points in a Spherical Layer
In [5] it was shown (among other results) that for all r, ϑ, n and d, where 0<r<1, 0<ϑ<1, d∈N, if
 (1) n<r1−r2d1+2ϑ(1−r2)d/2r2d−1, 
then n points chosen randomly, independently, according to the uniform distribution on Bd\rBd are Fisher separable with a probability greater than 1−ϑ, i.e., P∘F(d,r,n)>1−ϑ.

The following statements concerning the Fisher separability of random points in the spherical layer are proved in [12].

For all r, where 0<r<1, and for any d∈N
 (2) P1∘F(d,r,n)>(1−rd)1−(1−r2)d/22n. 

For all r, ϑ, where 0<r<1, 0<ϑ<1, and for sufficiently large d, if
 (3) n<ϑ(1−r2)d/2, 
then P1∘F(d,r,n)>1−ϑ.

For all r, where 0<r<1, and for any d∈N
 (4) P∘F(d,r,n)>(1−rd)1−(n−1)(1−r2)d/22n. 

For all r, ϑ, where 0<r<1, 0<ϑ<1 and for sufficiently large d, if
 (5) n<ϑ(1−r2)d/4, 
then P∘F(d,r,n)>1−ϑ.

The authors of [5,12] formulate their results for linearly separable sets of points, but in fact in the proofs they used that the sets are only Fisher separable.

Note that all estimates (1)–(5) require 0<r<1 with strong inequality. This means that they are inapplicable for (maybe the most interesting) case r=0, i.e., for the unit ball with no cavities.

A reviewer of the original version of the article drew our attention that for r=0 better results are obtained in [6,15]. Specifically,
 (6) P1∘F(d,0,n)≥1−n2d+1, 
 (7) P∘F(d,0,n)≥1−n(n−1)2d+1>1−n22d+1, 
and P1∘F(d,0,n)>1−ϑ provided that n<ϑ·2d+1. See details in Section 4.4.

The both estimates (1) and (5) are exponentially dependent on d for fixed r, ϑ and the estimate (1) is weaker than (5).

The following results concerning the linear separability of random points in the spherical layer were obtained in [14]:For all r, where 0≤r<1, and for any d∈N
 (8) P1∘(d,r,n)>1−n2d. 

For all r, ϑ, where 0≤r<1,
0<ϑ<1, and for any d∈N, if
 (9) n<ϑ2d, 
then P1∘(d,r,n)>1−ϑ.

For all r, where 0≤r<1, and for any d∈N
 (10) P∘(d,r,n)>1−n(n−1)2d. 

For all r, ϑ, where 0≤r<1,
0<ϑ<1, and for any d, if
 (11) n<ϑ2d, 
then P∘(d,r,n)>1−ϑ.



We note that the bounds (8)–(11) do not depend on r. We remove this drawback in this paper, giving more accurate estimates (see Theorems 1 and 3 and Corollaries 1 and 2).

3.2. Random Points Inside a Cube
In [5], a product distribution in the Qd is considered. Let the coordinates of a random point X=(x1,…,xd)∈Qd be independent random variables with variances σi2>σ02>0
(i=1,…,d). In [5], it is shown that for all ϑ and n, where 0<ϑ<1, if
 (12) n<ϑe0.5dσ043, 
then Mn is Fisher separable with a probability greater than 1−ϑ. As above, the authors of [5] formulate their result for the linearly separable case, but in fact they used only the Fisher separability.

If all random variables x1,…,xd have the uniform distribution on the segment [0,1] then σ02=112. Thus, the inequality (12) takes the form
 (13) n<ϑed/2883. 

We obtain that if n satisfies (13), then P□F(d,n)>1−ϑ.

In [13], it was shown that if we want to guarantee only the linear separability, then the bound (13) can be increased. Namely, if
 n<ϑcdd+1,c=1.18858, 
then P□(d,n)>1−ϑ. Here we give related estimates including ones for the linear separability of one point (see Theorems 5 and 6 and Corollary 3).

We note that better (and in fact asymptotically optimal) estimates for the Fisher separability in the unit cube are derived in [15]. The papers [13,15] were submitted to the same conference, so these results were derived in parallel and independently. Corollary 7 in [15] states that n points are Fisher separable with probability greater than 1−ϑ provided only that n<ϑeγd for γ=0.23319… See details in Section 5.

4. Random Points in a Spherical Layer
4.1. The Separability of One Point
The theorem below gives the probability of the linear separability of a random point from a random n-element set Mn={X1,…,Xn} in Bd\rBd. The proof develops an approach borrowed from [3,16].

The regularized incomplete beta function is defined as Ix(a,b)=B(x;a,b)B(a,b), where
 B(a,b)=∫01ta−1(1−t)b−1dt,B(x;a,b)=∫0xta−1(1−t)b−1dt 
are beta function and incomplete beta function, respectively (see [17]).

Theorem 1. 
Let 0≤r<1, α=4r2(1−r2),β=1−r2,d∈N. Then
(1)  
for 0≤r≤12
 (14) P1∘(d,r,n)>1−n·1−0.5Iαd+12,12+(2r)d·Iβd+12,122d(1−rd); 


(2)  
for 12≤r<1
 (15) P1∘(d,r,n)>1−n·0.5Iαd+12,12−(2r)d·Iβd+12,122d(1−rd). 





Proof.  A random point Y is linearly separable from Mn={X1,…,Xn} if and only if Y∉conv(Mn). Denote this event by C. Thus, P1∘(d,r,n)=P(C). Let us find the upper bound for the probability of the event C¯. This event means that the point Y belongs to the convex hull of Mn. Since the points in Mn have the uniform distribution, then the probability of C¯ is
 P(C¯)=Vol(conv(Mn)\(conv(Mn)∩rBd))Vol(Bd)−Vol(rBd). 

First, estimate the numerator of this fraction. We denote by Si the ball with center at the origin, with the diameter 1, and the point Xi lies on this diameter (see Figure 1). Then
 conv(Mn)\(conv(Mn)∩rBd)⊆⋃i=1nSi\(Si∩rBd)=W 
and
 Vol(conv(Mn)\(conv(Mn)∩rBd))≤Vol(W)≤∑i=1nVolSi\(Si∩rBd) 
 =∑i=1n(Vol(Si)−Vol(Si∩rBd))=n(Vol(S1)−Vol(S1∩rBd)) 
 =nγd12d−Vol(S1∩rBd), 
where γd is the volume of a ball of radius 1. Hence
 P(C¯)≤nγd12d−Vol(S1∩rBd)γd(1−rd). 

Now find Vol(S1∩rBd). It is obvious that Vol(S1∩rBd) is equal to the sum of the volumes of two spherical caps. We denote by Cap(R,H) the volume of a spherical cap of height H of a ball of radius R. It is known [18] that
 Cap(R,H)=12γdRdI(2RH−H2)/R2d+12,12 
if 0≤H≤R.

Consider two cases: 0≤r≤12 and 12≤r<1 (see Figure 2)

Case 1 If 0≤r≤12, then the centers of the balls S1,S2,…,Sn are inside of the spherical caps of height h of the ball rBd (see the left picture on Figure 2). Therefore, the following equalities are true:
 r2−(r−h)2=122−r−h−122, 
 r2−(r−h)2=−(r−h)2+(r−h), 
 h=r−r2, 
 V1=Cap12,r−h=Cap12,r2,V2=Cap(r,h)=Cap(r,r−r2). 

If R=12,
H=r2, then (2RH−H2)/R2=4r2(1−r2)=α, hence
 V1=12γd12dIαd+12,12. 

If R=r,
H=r−r2, then (2RH−H2)/R2=2H/R−(H/R)2=2(1−r)−(1−r)2=1−r2=β, hence
 V2=12γdrdIβd+12,12. 

Thus,
 Vol(S1∩rBd)=V1+V2=γd1212dIαd+12,12+12rdIβd+12,12. 

Hence
 P(C)=1−P(C¯)≥1−nγd12d−Vol(S1∩rBd)γd(1−rd) 
 =1−n·1−0.5Iα(d+12,12)+(2r)d·Iβ(d+12,12)2d(1−rd). 

Case 2 If 12≤r<1, then the centers of the balls S1,S2,…,Sn are outside of the spherical caps of height h of the ball rBd (see the right picture on Figure 2). Therefore, the following equalities are true:
 r2−(r−h)2=122−r−h−122, 
 r2−(r−h)2=−(r−h)2+(r−h), 
 h=r−r2, 
 V1=Vol12Bd−Cap12,1−(r−h)=Vol12Bd−Cap12,1−r2. 

If R=12,
H=1−r2, then (2RH−H2)/R2=4r2(1−r2); hence,
 V1=γd12d−12γd12dIαd+12,12, 
where α=4r2(1−r2),
 V2=Cap(r,h)=Cap(r,r−r2)=12γdrdIβd+12,12, 
where β=1−r2. Thus,
 Vol(S1∩rBd)=V1+V2=γd12d−1212dIαd+12,12+12rdIβd+12,12. 

Hence
 P(C)=1−P(C¯)≥1−nγd12d−Vol(S1∩rBd)γd(1−rd)=1−n·0.5Iα(d+12,12)−(2r)d·Iβ(d+12,12)2d(1−rd). 

The estimates (14) and (15) for P1∘(d,r,n) are monotonically increasing in both d and r and decreasing in n, which corresponds to the behavior of the probability P1∘(d,r,n) itself (see Figure 3 and Figure 4). On the contrary, the estimate (3) for the probability P1∘F(d,r,n) is nonmonotonic in r (see Figure 5).

Note that the estimates (14), (15) obtained in Theorem 1 are quite accurate (in the sense that they are close to empirical values), as is illustrated with Figure 4. The experiment also shows that the probabilities P1∘(d,r,n) and P1∘F(d,r,n) (more precisely, the corresponding frequencies) are quite close to each other, but there is a certain gap between them.

The following corollary gives an estimate for the number of points n guaranteeing the linear separability of a random point from a random n-element set Mn in Bd\rBd with probability close to 1.

Corollary 1. 
Let 0<ϑ<1,α=4r2(1−r2),β=1−r2,d∈N. If
(1)  
 n<N1(d,r,ϑ)=ϑ2d(1−rd)1−0.5Iα(d+12,12)+(2r)d·Iβ(d+12,12),0≤r≤12 
or


(2)  
 n<N2(d,r,ϑ)=ϑ2d(1−rd)0.5Iα(d+12,12)−(2r)d·Iβ(d+12,12),12≤r<1, 






then P1∘(d,r,n)>1−ϑ.


The theorem below establishes asymptotic estimates.

Theorem 2. 
(1)  
If 0≤r<12 then
 N1(d,r,ϑ)∼ϑ2d. 


(2)  
If r=12 then
 N1(d,r,ϑ)=N2(d,r,ϑ)∼ϑ2d+1. 


(3)  
If 12<r<1 then
 N2(d,r,ϑ)∼ϑ2π·r(2r2−1)1−r2·d+1·1r1−r2d. 





Proof.  The paper [19] gives the following asymptotic expansion for the incomplete beta function
 B(x;a,b)∼xaa∑k=0∞fk(b,x)akfor0≤x<1,a→∞ 
and
 fk(b,x)=dkdwk(1−xe−w)b−1w=0. 

Since f0(b,x)=(1−x)b−1 then
 B(x;a,b)∼xaa(1−x)b−1+xaa∑k=1∞fk(b,x)ak∼xaa(1−x)b−1forb,xfixed,a→∞. 

Since B(a,b)∼Γ(b)ab for b fixed and a→∞, then
 Ix(a,b)=B(x;a,b)B(a,b)∼xa(1−x)b−1a1−bΓ(b) 
for b,x fixed and a→∞.

We have x=α=4r2(1−r2) or x=β=1−r2 and a=d+12,
b=12; hence,
 Iαd+12,12∼2αd+12πd+11−4r2+4r4=2π·1|1−2r2|·αd+12d+1, 
 (2r)dIβd+12,12∼(2r)d2(1−r2)d+1rπd+1=2π·12r2·αd+12d+1. 

If r=0, then α=0,
β=1; hence, N1(d,r,ϑ)∼ϑ2d.

If 0<r<12, then 0<α<1; hence,
 Iαd+12,12+(2r)dIβd+12,12∼0 
and
 N1(d,r,ϑ)∼ϑ2d. 

If r=12, then α=1,
β=12; hence,
 N1(d,r,ϑ)=N2(d,r,ϑ)∼ϑ2d(1−rd)0.51−2π·1d+1∼ϑ2d+1. 

If 12<r<1, then 0<α<1; hence,
 Iαd+12,12−(2r)dIβd+12,12∼2π·12r2(2r2−1)·αd+12d+1=2π·1−r2r(2r2−1)·2d(r1−r2)dd+1 
and
 N2(d,r,ϑ)=ϑ2d(1−rd)0.5Iα(d+12,12)−(2r)d·Iβ(d+12,12)∼ϑ2d0.52π·1−r2r(2r2−1)·2d(r1−r2)dd+1 
 =ϑ2π·r(2r2−1)1−r2·d+1·1r1−r2d. 

□

4.2. Separability of a Set of Points
The theorem below gives the probability of the linear separability of a random n-element set Mn in Bd\rBd.

Theorem 3. 
Let 0≤r<1, α=4r2(1−r2),β=1−r2 and d,n∈N. Then
(1)  
for 0≤r≤12
 (16) P∘(d,r,n)>1−n(n−1)·1−0.5Iα(d+12,12)+(2r)d·Iβ(d+12,12)2d(1−rd); 


(2)  
for 12≤r<1
 (17) P∘(d,r,n)>1−n(n−1)·0.5Iα(d+12,12)−(2r)d·Iβ(d+12,12)2d(1−rd). 





Proof.  Denote by An the event that Mn is linearly separable and denote by Ci the event that Xi∉conv(Mn\{Xi}) (i=1,…,n). Thus, P∘(d,r,n)=P(An). Clearly, An=C1∩…∩Cn and P(An)=P(C1∩…∩Cn)=1−P(C¯1∪…∪C¯n)≥1−∑i=1nP(C¯i). Let us find an upper bound for the probability of the event C¯i. This event means that the point Xi belongs to the convex hull of the remaining points, i.e., Xi∈conv(Mn\{Xi}). In the proof of the previous theorem, it was shown that if 0≤r≤12, then
 P(C¯i)≤(n−1)·1−0.5Iα(d+12,12)+(2r)d·Iβ(d+12,12)2d(1−rd)(i=1,…,n); 
and if 12≤r<1, then
 P(C¯i)≤(n−1)·0.5Iα(d+12,12)−(2r)d·Iβ(d+12,12)2d(1−rd)(i=1,…,n). 

Therefore, using the inequality
 P(An)≥1−∑i=1nP(C¯i) 
we obtain what is required. □

The graphs of the estimates (16), (17) and corresponding frequencies in 60 trials for n=1000 and n = 10,000 points are shown in Figure 6 and Figure 7, respectively. The experiment shows that our estimates are quite accurate and close to the corresponding frequencies.

Another important conclusion from the experiment is as follows. Despite the fact that the estimates for both probabilities P∘F(d,r,n) and P∘(d,r,n) and corresponding frequencies are close to 1 for sufficiently big d, the "threshold values" for such a big d differ greatly. In other words, the blessing of dimensionality when using linear discriminants comes noticeably earlier than if we only use Fisher discriminants. This is achieved at the cost of constructing the usual linear discriminant in comparison with the Fisher one.

The following corollary gives an estimate for the number of points n guaranteeing the linear separability of a random n-element set Mn in Bd\rBd with probability close to 1.

Corollary 2. 
Let 0<ϑ<1,α=4r2(1−r2),β=1−r2. If
(1)  
 0≤r≤12andn<N1(d,r,ϑ)=ϑ2d(1−rd)1−0.5Iα(d+12,12)+(2r)d·Iβ(d+12,12) 
or


(2)  
 12≤r<1andn<N2(d,r,ϑ)=ϑ2d(1−rd)0.5Iα(d+12,12)−(2r)d·Iβ(d+12,12), 
then P∘(d,r,n)>1−ϑ.





The theorem below establishes asymptotic estimates for the number of points guaranteeing the linear separability with probability greater than 1−ϑ.

Theorem 4. 
(1)  
If 0≤r<12 then
 N1(d,r,ϑ)∼ϑ2d/2. 


(2)  
If r=12 then
 N1(d,r,ϑ)=N2(d,r,ϑ)∼ϑ2(d+1)/2. 


(3)  
If 12<r<1 then
 N2(d,r,ϑ)∼ϑ2π4·r(2r2−1)1−r24·d+14·1r1−r2d/2. 





4.3. Comparison of the Results
Let us show that the new estimates (16) and (17) for linear separability tend to be 1 faster than the estimate (4) in [12] for Fisher separability.

Statement 1. 
Let 0<r<1,α=4r2(1−r2),β=1−r2 and d,n∈N,
 f1=n(n−1)·1−0.5Iα(d+12,12)+(2r)d·Iβ(d+12,12)2d(1−rd), 
 f2=n(n−1)·0.5Iα(d+12,12)−(2r)d·Iβ(d+12,12)2d(1−rd), 
 g=1−(1−rd)1−(n−1)(1−r2)d/22n. 



For r and n fixed
(1)  
if 0<r<12, then
 gf1∼12(4−4r2)d/2→∞; 


(2)  
if r=12, then
 gf1=gf2∼n+1n−1·2d/2→∞; 


(3)  
if 12<r<1, then
 gf2∼2π·r(2r2−1)(n−1)1−r2·d+1·11−r2d/2→∞. 





Proof.  If 0<r<12, then g∼n(n−1)2(1−r2)d/2 and f1∼n(n−1)2d (see the proof of Theorem 2); hence,
 gf∼n(n−1)2(1−r2)d/2n(n−1)2d=12(4−4r2)d/2→∞,as4−4r2>2. 

If r=12, then g∼n(n+1)212d/2 and f1=f2∼n(n−1)2d+1 (see the proof of Theorem 2); hence,
 gf1=gf1∼n(n+1)212d/2n(n−1)2d+1=n+1n−1·2d/2→∞. 

If 12<r<1, then g∼nrd and f2∼n(n−1)2π·r(2r2−1)1−r2·d+1·1r1−r2d (see the proof of Theorem 2), hence
 gf2∼nrd2π·r(2r2−1)1−r2·d+1·1r1−r2dn(n−1)=2π·r(2r2−1)(n−1)1−r2·d+1·11−r2d/2→∞. 
 □

Now let us compare the estimates for the number of points that guarantee the linear and Fisher separabilities of random points in the spherical layer obtained in Corollary 2 and in [12], respectively. The estimate in Corollary 2 for the number of points guaranteeing the linear separability tends to ∞ faster than the estimate (5), guaranteeing the Fisher separability for all 0<r<1.

Statement 2. 
Let f1=N1(d,r,ϑ),f2=N2(d,r,ϑ),g=ϑ(1−r2)d/4,0<r<1,0<ϑ<1,d∈N. For r and ϑ fixed
(1)  
if 0<r<12, then
 f1g∼(21−r2)d/2→∞; 


(2)  
if r=12, then
 f1g=f2g∼2(d+2)/4→∞; 


(3)  
if 12<r<1, then f2g∼2π·r(2r2−1)1−r2·(d+1)1/4·1rd/2→∞.





Proof.  If 0<r<12 then f1g∼ϑ2d(1−r2)d/4ϑ=(21−r2)d/2.

If r=12, then f1=f2∼ϑ2d+1 and g=ϑ2d/4; hence, f1g=f2g∼ϑ2d+1ϑ2d/4=2(d+2)/4.

If 12<r<1, then f2∼ϑ2π·r(2r2−1)1−r2·d+1·1r1−r2d; hence,
 f2g∼ϑ2π·r(2r2−1)1−r2·(d+1)1/4·1r2(1−r2)d/4(1−r2)d/4ϑ 
 =2π·r(2r2−1)1−r2·(d+1)1/4·1rd/2.  □

4.4. A Note about Random Points Inside the Ball (r=0)
A reviewer of the original version of the article drew our attention to the fact that for the uniform distribution inside the ball (case r=0), better results are known. Specifically, let p¯xyF be the probability that i.i.d. points x, y inside the ball are not Fisher separable. Let Ixy be the indicator function of this event. Then
 p¯xyF=E[Ixy]=E[E[Ixy∣y]]=E[p¯y], 
where p¯y denotes the probability that x is not Fisher separable from a given point y. In [6] (also discussed in [15]), there is a proof that E[p¯y]=1/2d+1. In the notation of our paper, this implies that
 P1∘F(d,0,n)≥1−n2d+1,P∘F(d,0,n)≥1−n(n−1)2d+1>1−n22d+1, 
and P1∘F(d,0,n)>1−ϑ provided that n<ϑ·2d+1. This improves the estimate in Theorem 2 for the case r=0 twice. Note that the same estimate n<ϑ·2d+1 was derived for r=12 (see Theorem 2). The reviewer conjectured that estimate n<ϑ·2d derived in this paper could be improved twice for the whole range r∈0,12. The experimental results give support for this hypothesis (see Figure 4, Figure 5, Figure 6 and Figure 7).

5. Random Points Inside a Cube
Consider a set of points Mn={X1,…,Xn} choosing randomly, independently and according to the uniform distribution on the d-dimensional unit cube Qd.

Theorem 5. 
Let d,n∈N. Then
 (18) P1□(d,n)>1−n(d+1)cd,c=1.18858… 


Proof.  A random point Y is linearly separable from Mn={X1,…,Xn} if and only if Y∉conv(Mn). Denote this event by C. Thus, P1□(d,n)=P(C). Let us find the upper bound for the probability of the event C¯. This event means that the point Y belongs to the convex hull of Mn. Since the points in Mn have the uniform distribution, the probability of C¯ is
 P(C¯)=Volconv(Mn)Vol(Qd)=Volconv(Mn). 

In [20] it is proved that the upper bound for the maximal volume of the convex hull of k points placed in Qd is k(d+1)cd, where c=1.18858. Thus, Volconv(Y1,…,Yk)<k(d+1)cd so
 P(C¯)=Volconv(Mn) <n(d+1)cd. 
and
 P1□(d,n)=P(C)=1−P(C¯)>1−n(d+1)cd.  □

Corollary 3. 
Let 0<ϑ<1,
 (19) n<ϑcdd+1,c=1.18858… 



Then P1□(d,n)>1−ϑ.


Theorem 6. 
Let d,n∈N. Then
 (20) P□(d,n)>1−n(n−1)(d+1)cd,c=1.18858. 


Proof.  Denote by An the event that Mn is linearly separable and denote by Ci the event that Xi∉conv(Mn\{Xi}) (i=1,…,n). Thus, P□(d,n)=P(An). Clearly An=C1∩…∩Cn and P(An)=P(C1∩…∩Cn)=1−P(C¯1∪…∪C¯n)≥1−∑i=1nP(C¯i). Let us find the upper bound for the probability of the event C¯i. This event means that the point Xi belongs to the convex hull of the remaining points, i.e., Xi∈conv(Mn\{Xi}). In the proof of the previous theorem, it was shown that
 P(C¯i)≤(n−1)(d+1)cd,c=1.18858(i=1,…,n). 

Hence
 P(An)≥1−∑i=1nP(C¯i)≥1−n(n−1)(d+1)cd.  □

Corollary 4. 
[13] Let 0<ϑ<1,
 (21) n<ϑcdd+1,c=1.18858. 



Then P□(d,n)>1−ϑ.


We note that the estimate (21) for the number of points guaranteeing the linear separability tends to be ∞ faster than the estimate (13), guaranteeing the Fisher separability because
 ϑcdd+1ϑed/2883=3d+1ce1288d→∞,asd→∞, 
since c/e1288≈1.18446.

However better (and in fact asymptotically optimal) estimates for the Fisher separability in the unit cube are derived in [15]. Corollary 7 in [15] states that n points are Fisher separable with probability greater than 1−ϑ provided only that n<ϑeγd for γ=0.23319…. This can be written as n<ϑcd for c=e2γ=1.59421…. Thus,
 (22) P1□F(d,n)>1−nexp(2γd)=1−ncd, 
 (23) P□F(d,n)>1−n2cd. 

Theorem 6 and Corollary 4 in our paper state the same results with c=1.18858…, and for just linear separability instead of Fisher separability. However, [13,15] were submitted to the same conference, so these results were derived in parallel and independently.

The bounds (18) and (20) for the probabilities and corresponding frequencies are presented in Figure 8 and Figure 9.

6. Subsequent Work
In a recent paper [2], explicit and asymptotically optimal estimates of Fisher separation probabilities for spherically invariant distribution (e.g., the standard normal and the uniform distributions) were obtained. Theorem 14 in [2] generalizes the results presented here. Since [2] was submitted to the arxiv later, we did not compare the results of that article with our results.

7. Conclusions
In this paper we refined the estimates for the number of points and for the probability in stochastic separation theorems. We gave new bounds for linear separability, when the points are drawn randomly, independently and uniformly from a d-dimensional spherical layer or from the unit cube. These results refine some results obtained in [5,12,13,14] and allow us to better understand the applicability limits of the stochastic separation theorems for high-dimensional data mining and machine learning problems.

The strongest progress was in the estimation for the number of random points in a (1−r)-thick spherical layer Bd\rBd that are linear separable with high probability. If
 n≲ϑ2d/2,0≤r<12orn≲ϑ2(d+1)/2,r=12 
or
 n≲ϑ2π4·r(2r2−1)1−r24·d+14·1r1−r2d/2,12<r<1, 
then n i.i.d. random points inside the spherical layer Bd\rBd are linear separable with probability at least 1−ϑ (the asymptotic inequalities are for d→∞).

One of the main results of the experiment comparing linear and Fisher separabilities is as follows. The blessing of dimensionality when using linear discriminants can come noticeably earlier (for smaller values of d) than if we only use Fisher discriminants. This is achieved at the cost of constructing the usual linear discriminant in comparison with the Fisher one. 

Acknowledgments
The authors are grateful to anonymous reviewers for valuable comments.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Author Contributions
Conceptualization, S.S. and N.Z.; methodology, S.S. and N.Z.; software, S.S. and N.Z.; validation, S.S. and N.Z.; formal analysis, S.S. and N.Z.; investigation, S.S. and N.Z.; resources, S.S. and N.Z.; data curation, S.S. and N.Z.; writing—original draft preparation, S.S. and N.Z.; writing—review and editing, S.S. and N.Z.; visualization, S.S. and N.Z.; supervision, S.S. and N.Z.; project administration, S.S. and N.Z.; funding acquisition, S.S. and N.Z. All authors have read and agreed to the published version of the manuscript.

Funding
The work is supported by the Ministry of Science and Higher Education of the Russian Federation (agreement number 075-15-2020-808).

Conflicts of Interest
The authors declare no conflict of interest.

Figure 1 Illustration to the proof of Theorem 1.

Figure 2 Illustration to the proof of Theorem 1: case 1 (left); case 2 (right).

Figure 3 The graphs of the right-hand sides of the estimates (14), (15) for the probability P1∘(d,r,n) that a random point is linear and separable from a set of n=1000 (left) and n= 10,000 (right) random points in the layer Bd\rBd.

Figure 4 The graphs of the estimates for the probabilities P1∘(d,r,n) (P1∘F(d,r,n)) that a random point is linearly (and respectively, Fisher) separable from a set of n= 10,000 random points in the layer Bd\rBd. The solid lines correspond to the theoretical bounds (14) and (15) for the linear separability. The dash-dotted lines represent the theoretical bounds (2) and (6) for the Fisher separability. The crosses (circles) correspond to the empirical frequencies for linear (and respectively Fisher) separability obtained in 60 trials for each dimension d.

Figure 5 The graphs of the right-hand side of the estimate (3) for the probability P1∘F(d,r,n) that a random point is Fisher separable from a set of n=1000 (left) and n= 10,000 (right) random points in the layer Bd\rBd.

Figure 6 The graphs of the estimates for the probabilities P∘(d,r,n) (P∘F(d,r,n)) that a random set of n=1000 points in Bd\rBd is linearly (and respectively Fisher) separable. The solid lines correspond to the theoretical bounds (16) and (17) for the linear separability. The dash-dotted lines represent the theoretical bound (4) and (7) for the Fisher separability. The crosses (circles) correspond to the empirical frequencies for linear (and respectively, Fisher) separability obtained in 60 trials for each dimension d.

Figure 7 The graphs of the estimates for the probabilities P∘(d,r,n) (P∘F(d,r,n)) that a random set of n=10,000 points in Bd\rBd is linearly (and respectively, Fisher) separable. The notation is the same as in Figure 6.

Figure 8 The graphs of the estimate for the probabilities P1□(d,n) and P1□F(d,n) that a random point is linearly (Fisher) separable from a set of n = 10,000 random points inside the cube Qd. The solid red and blue lines correspond to the theoretical bounds (18) and (22) respectively. Red crosses (blue circles) correspond to the empirical frequencies for linear (and respectively, Fisher) separability obtained in 60 trials for each dimension d.

Figure 9 The graphs of the estimates (20) and (23) for the probabilities P□(d,n) and P□F(d,n) that a set of n = 10,000 random points inside the unit cube Qd is linear and Fisher separable, respectively. The notation is the same as in Figure 8.
==== Refs
References
1. Donoho D.L.   High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality. Invited Lecture at Mathematical Challenges of the 21st Century Proceedings of the AMS National Meeting Los Angeles, CA, USA 6–12 August 2000 Available online: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.329.3392  (accessed on 9 November 2020) 
2. Grechuk B.  Gorban A.N.  Tyukin I.Y.   General stochastic separation theorems with optimal bounds arXiv 2020 2010.05241 
3. Bárány I.  Füredi Z.   On the shape of the convex hull of random points Probab. Theory Relat. Fields 1988 77 231 240 10.1007/BF00334039 
4. Donoho D.  Tanner J.   Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing Philos. Trans. R. Soc. A 2009 367 4273 4293 10.1098/rsta.2009.0152 19805445 
5. Gorban A.N.  Tyukin I.Y.   Stochastic separation theorems Neural Netw. 2017 94 255 259 10.1016/j.neunet.2017.07.014 28806718 
6. Gorban A.N.  Golubkov A.  Grechuk B.  Mirkes E.M.  Tyukin I.Y.   Correction of AI systems by linear discriminants: Probabilistic foundations Inf. Sci. 2018 466 303 322 10.1016/j.ins.2018.07.040 
7. Gorban A.N.  Grechuk B.  Tyukin I.Y.   Augmented artificial intelligence: A conceptual framework arXiv 2018 1802.02172v3 
8. Albergante L.  Bac J.  Zinovyev A.   Estimating the effective dimension of large biological datasets using Fisher separability analysis Proceedings of the 2019 International Joint Conference on Neural Networks (IJCNN) Budapest, Hungary 14–19 July 2019 
9. Bac J.  Zinovyev A.   Lizard brain: Tackling locally low-dimensional yet globally complex organization of multi-dimensional datasets Front. Neurorobot. 2020 13 110 10.3389/fnbot.2019.00110 31998109 
10. Gorban A.N.  Makarov V.A.  Tyukin I.Y.   The unreasonable effectiveness of small neural ensembles in high-dimensional brain Phys. Life Rev. 2019 29 55 88 10.1016/j.plrev.2018.09.005 30366739 
11. Gorban A.N.  Makarov V.A.  Tyukin I.Y.   High-Dimensional Brain in a High-Dimensional World: Blessing of Dimensionality Entropy 2020 22 82 10.3390/e22010082 
12. Gorban A.N.  Burton R.  Romanenko I.  Tyukin I.Y.   One-trial correction of legacy AI systems and stochastic separation theorems Inf. Sci. 2019 484 237 254 10.1016/j.ins.2019.02.001 
13. Sidorov S.V.  Zolotykh N.Y.   On the Linear Separability of Random Points in the d -dimensional Spherical Layer and in the d -dimensional Cube Proceedings of the 2019 International Joint Conference on Neural Networks (IJCNN) Budapest, Hungary 14–19 July 2019 1 4 10.1109/IJCNN.2019.8852237 
14. Sidorov S.V.  Zolotykh N.Y.   Linear and Fisher Separability of Random Points in the d -dimensional Spherical Layer Proceedings of the 2020 International Joint Conference on Neural Networks (IJCNN) Glasgow, UK 19–24 July 2020 1 6 10.1109/IJCNN48605.2020.9206657 
15. Grechuk B.   Practical stochastic separation theorems for product distributions Proceedings of the 2019 International Joint Conference on Neural Networks (IJCNN) Budapest, Hungary 14–19 July 2019 1 8 10.1109/IJCNN.2019.8851817 
16. Elekes G.   A geometric inequality and the complexity of computing volume Discret. Comput. Geom. 1986 1 289 292 10.1007/BF02187701 
17. Paris R.B.   Incomplete beta functions NIST Handbook of Mathematical Functions Olver F.W.  Lozier D.W.  Boisvert R.F.  Clark C.W.   Cambridge University Press Cambridge, UK 2010 
18. Li S.   Concise Formulas for the Area and Volume of a Hyperspherical Cap Asian J. Math. Stat. 2011 4 66 70 10.3923/ajms.2011.66.70 
19. López J.L.  Sesma J.   Asymptotic expansion of the incomplete beta function for large values of the first parameter Integral Transform. Spec. Funct. 1999 8 233 236 10.1080/10652469908819230 
20. Dyer M.E.  Füredi Z.  McDiarmid C.   Random points in the n -cube DIMACS Ser. Discret. Math. Theor. Comput. Sci. 1990 1 33 38