A set S of Boolean points is a specifying set for a threshold function f if the only threshold function consistent with f on S is f itself. The minimal cardinality of a specifying set for f is the specification number of f and it is never smaller than n+1 for a function with n relevant variables. In the present paper, we develop an inductive approach to describing the set of Boolean threshold functions with minimum specification number by means of operations that allow us to extend functions of n variables in this set to functions of n+1 variables.

Stochastic separation theorems play important role in high-dimensional data analysis and machine learning. It turns out that in high dimension 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 dimension. This and similar facts can be used for constructing correctors for artificial intelligent systems, for determining an intrinsic dimension 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. These results allow us to better outline the applicability limits of the stochastic separation theorems in applications.

The authors of [6] propose a method for correcting errors of artificial intelligence systems by separating erroneous cases with the Fisher linear discriminant. It turned out that if the dimension is large this approach works well even for an exponential (of the dimension) number of samples. In this paper, we specify the limits of applicability of this approach by estimating the number of points that are linearly separable with a probability close to 1 in two particular cases: when the points drawn randomly, independently and uniformly from a d-dimensional spherical layer and from the d-dimensional cube. Our bounds for these two cases improve some bounds obtained in [6].

An extremal point of a positive threshold Boolean function $f$ is either a maximal zero or a minimal one. It is known that if $f$ depends on all its variables, then the set of its extremal points completely specifies $f$ within the universe of threshold functions. However, in some cases, $f$ can be specified by a smaller set. The minimum number of points in such a set is the specification number of $f$. Hu (1965) showed that the specification number of a threshold function of $n$ variables is at least $n+1$. Anthony et al. (1995) proved that this bound is attained for nested functions and conjectured that for all other threshold functions the specification number is strictly greater than $n+1$. In the present paper, we resolve this conjecture negatively by exhibiting threshold Boolean functions of $n$ variables, which are non-nested and for which the specification number is $n+1$. On the other hand, we show that the set of extremal points satisfies the statement of the conjecture, i.e.~a positive threshold Boolean function depending on all its $n$ variables has $n+1$ extremal points if and only if it is nested. To prove this, we reveal an underlying structure of the set of extremal points.

It is known that a minimal teaching set of any threshold function on the two-dimensional rectangular grid consists of 3 or 4 points. We derive exact formulae for the numbers of functions corresponding to these values and further refine them in the case of a minimal teaching set of size 3. We also prove that the average cardinality of the minimal teaching sets of threshold functions is asymptotically $\nicefrac{7}{2}$. We further present corollaries of these results concerning some special arrangements of lines in the plane.