{'fraction_non_alphanumeric': 0.04373539371393142, 'fraction_numerical': 0.008823389135307865, 'mean_word_length': 4.083151515151515, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning Low-Density Separators

We define a novel, basic, unsupervised learning problem - learning the lowest density homogeneous hyperplane separator of an unknown probability distribution. This task is relevant to several problems in machine learning, such as semi-supervised learning and clustering stability. We investigate the question of existence of a universally consistent algorithm for this problem. We propose two natural learning paradigms and prove that, on input unlabeled random samples generated by any member of a rich family of distributions, they are guaranteed to converge to the optimal separator for that distribution. We complement this result by showing that no learning algorithm for our task can achieve uniform learning rates (that are independent of the data generating distribution).


Introduction
While the theory of machine learning has achieved extensive understanding of many aspects of supervised learning, our theoretical understanding of unsupervised learning leaves a lot to be desired. In spite of the obvious practical importance of various unsupervised learning tasks, the state of our current knowledge does not provide anything that comes close to the rigorous mathematical performance guarantees that classification prediction theory enjoys.
In this paper we make a small step in that direction by analyzing one specific unsupervised learning task -the detection of low-density linear separators for data distributions over Euclidean spaces. We consider the following task: for an unknown data distribution over R n , find the homogeneous hyperplane of lowest density that cuts through that distribution. We assume that the underlying data distribution has a continuous density function and that the data available to the learner are finite i.i.d. samples of that distribution.
Our model can be viewed as a restricted instance of the fundamental issue of inferring information about a probability distribution from the random samples it generates. Tasks of that nature range from the ambitious problem of density estimation [8], through estimation of level sets [4], [13], [1], densest region detection [3], and, of course, clustering. All of these tasks are notoriously difficult with respect to both the sample complexity and the computational complexity aspects (unless one presumes strong restrictions about the nature of the underlying data distribution). Our task seems more modest than these. Although we are not aware of any previous work on this problem (from the point of view of statistical machine learning, at least), we believe that it is a rather basic problem that is relevant to various practical learning scenarios.
One important domain to which the detection of low-density linear data separators is relevant is semi-supervised learning [7]. Semi-supervised learning is motivated by the fact that in many real world classification problems, unlabeled samples are much cheaper and easier to obtain than labeled examples. Consequently, there is great incentive to develop tools by which such unlabeled samples can be utilized to improve the quality of sample based classifiers. Naturally, the utility of unlabeled data to classification depends on assuming some relationship between the unlabeled data distribution and the class membership of data points (see [5] for a rigorous discussion of this point). A common postulate of that type is that the boundary between data classes passes through low-density regions of the data distribution. The Transductive Support Vector Machines paradigm (TSVM) [9] is an example of an algorithm that implicitly uses such a low density boundary assumption. Roughly speaking, TSVM searches for a hyperplane that has small error on the labeled data and at the same time has wide margin with respect to the unlabeled data sample.
Another area in which low-density boundaries play a significant role is the analysis of clustering stability. Recent work on the analysis of clustering stability found close relationship between the stability of a clustering and the data density along the cluster boundaries -roughly speaking, the lower these densities the more stable the clustering ( [6], [12]).
A low-density-cut algorithm for a family F of probability distributions takes as an input a finite sample generated by some distribution f ∈ F and has to output a hyperplane through the origin with low density w.r.t. f . In particular, we consider the family of all distributions over R n that have continuous density functions. We investigate two notions of success for low-density-cut algorithmsuniform convergence (over a family of probability distributions) and consistency. For uniform convergence we prove a general negative result, showing that no algorithm can guarantee any fixed convergence rates (in terms of sample sizes). This negative result holds even in the simplest case where the data domain is the one-dimensional unit interval. For consistency (e.g., allowing the learning/convergence rates to depend on the data-generating distribution), we prove the success of two natural algorithmic paradigms; Soft-Margin algorithms that choose a margin parameter (depending on the sample size) and output the separator with lowest empirical weight in the margins around it, and Hard-Margin algorithms that choose the separator with widest sample-free margins.
The paper is organized as follows: Section 2 provides the formal definition of our learning task as well as the success criteria that we investigate. In Section 3 we present two natural learning paradigms for the problem over the real line and prove their universal consistency over a rich class of probability distributions. Section 4 extends these results to show the learnability of lowest-density homogeneous linear cuts for probability distributions over R d for arbitrary dimension, d. In Section 5 we show that the previous universal consistency results cannot be improved to obtain uniform learning rates (by any finite-sample based algorithm). We conclude the paper with a discussion of directions for further research.

Preliminaries
We consider probability distributions over R d . For concreteness, let the domain of the distribution be the d-dimensional unit ball.
A linear cut learning algorithm is an algorithm that takes as input a finite set of domain points, a sample S ⊆ R d , and outputs a homogenous hyperplane, L(S) (determined by a weight vector, w ∈ R d , such that ||w|| 2 = 1).
We investigate algorithms that aim to detect hyperplanes with low density with respect to the samplegenerating probability distribution.
Let f : R d → R + 0 be a d-dimensional density function. We assume that f is continuous. For any homogeneous hyperplane h(w) = {x ∈ R d : w T x = 0} defined by a unit weight vector w ∈ R d , we consider the (d − 1)-dimensional integral of the density over h, Note that w → f (w) is a continuous mapping defined on the (d−1)-sphere S d−1 = {w ∈ R d : w 2 = 1}. Note that, for any such weight vector w, f (w) = f (−w). For the 1-dimensional case, these hyperplanes are replaced by points, x on the real line, and f (x) = f (x) -the density at the point x. Definition 1. A linear cut learning algorithm is a function that maps samples to homogeneous hyperplanes. Namely, (The intention is that L finds the lowest density linear separator of the sample generating distribution.) Definition 2. Let µ be a probability distribution and f its density function. For a weight vector w we define the half-spaces h For any weight vectors w and w ′ , In theses cases we omit any explicit reference to D. All of our results hold as well when D is taken to be the probability mass of the symmetric difference between L(S) and w * and when D is taken Definition 3. Let F denote a family of probability distributions over R d . We assume that all members of F have density functions, and identify a distribution with its density function. Let D denote a distance function over hyperplanes. For a linear cut learning algorithm, L, as above, 1. We say that L, is consistent for F w.r.t a distance measure D, if, for any probability distribution f in F , if f attains a unique minimum density hyperplane then where w * is the minimum density hyperplane for f .

2.
We say that L is uniformly convergent for F (w.r.t a distance measure, D), if, for every ǫ, δ > 0, there exists a m(ǫ, δ) such that for any probability distribution f ∈ F, if f has a unique minimizer w * then, for all m ≥ m(ǫ, δ) we have

The One Dimensional Problem
Let F 1 be the family of all probability distributions over the unit interval [0, 1] that have continuous density function. We consider two natural algorithms for lowest density cut over this family. The first is a simple bucketing algorithm. We explain it in detail and show its consistency in section 3.1. The second algorithm is the hard-margin algorithm which outputs the mid-point of the largest gap between two consecutive points the sample. In section 3.2 we show hard-margin algorithm is consistent and in section 3.1 that the bucketing algorithm is consistent. In section 5 we show there are no algorithms that are uniformly convergent for F 1 .

The Bucketing Algorithm
The algorithm is parameterized by a function k : N → N. For a sample of size m, the algorithm splits the interval [0, 1] into k(m) equal length subintervals (buckets). Given an input sample S, it counts the number of sample points lying in each bucket and outputs the mid-point of the bucket with fewest sample points. In case of ties, it picks the rightmost bucket. We denote this algorithm by B k . As it turns out, there exists a choice of k(m) which makes the algorithm B k consistent for F 1 . Proof. Fix f ∈ F 1 , assume f has a unique minimizer x * . Fix ǫ, δ > 0. Let U = (x * − ǫ/2, x * + ǫ/2) be an neighbourhood of the unique minimizer x * . The set [0, 1] \ U is compact and hence there exists The assumptions on growth of k(m) imply that there exists m 0 such that for all m ≥ m 0 Fix any m ≥ m 0 . Divide [0, 1] into k(m) buckets each of length 1/k(m). For any bucket I, I ∩ U = ∅, .
For a bucket I, we denote by |I ∩ S| the number of sample points in the bucket I. From the well known Vapnik-Chervonenkis bounds [2], we have that with probability at least 1 − δ over i.i.d. draws of sample S of size m, for any bucket I, Fix any sample S satisfying the inequality (7) . For any bucket I, I ∩ U = ∅, ≤ |I ∩ S| m by (7) Since |J ∩ S| > |I ∩ S|, the algorithm B k must not output the mid-point of any bucket I for which I ∩ U = ∅. Henceforth, the algorithm's output, B k (S), is the mid-point of an bucket I which intersects U . Thus the estimate B k (S) differs from x * by at most the sum of the radius of the neighbourhood U and the radius of the bucket. Since the length of a bucket is 1/k < |V |/2 and V ⊂ U , the sum of the radii is Combining all the above, we have that for any ǫ, δ > 0 there exists m 0 such that for any m ≥ m 0 , with probability at least 1 − δ over the draw of an i.i.d. sample S of size m, |B k (S) − x * | < ǫ. This is the same as saying that B k is consistent for f . ⊓ ⊔ Note that in the above proof we cannot replace the condition since Vapnik-Chervonenkis bounds do not allow us to detect O(1/ √ m)-difference between probability masses of two buckets.
The following theorems shows that if there are too many buckets the bucketing algorithm is not consistent anymore. To prove the theorem we need a proposition of the following lemma dealing with the classical coupon collector problem.
Lemma 1 (The Coupon Collector Problem [11]). Let the random variable X denote the number of trials for collecting each of the n types of coupons. Then for any constant c ∈ R, and m = n ln n + cn, Proof (of Theorem 2). Consider the following density f on [0, 1], which attains unique minimum at x * = 1/4. From the assumption on the growth of k(m) for all sufficiently large m, k(m) > 4 and k(m) > 8m/ ln m. Consider the all buckets lying in the interval [ 1 2 , 1] and denote them by b 1 , b 2 , . . . , b n . Since the bucket size is less than 1/4, they cover the interval [ 3 4 , 1]. Hence their length total length is at least 1/4 and hence there are n ≥ k(m)/4 > 2m/ ln m such buckets. We will show that for m large enough, with probability at least 1/2, at least one of the buckets b 1 , b 2 , . . . , b n receives no sample point. Since probability masses of b 1 , b 2 , . . . , b n are the same, we can think of these buckets as coupon types we are collecting and the sample points as coupons. By Lemma 1, it suffices to verify, that the number of trials, m, is at most 1 2 n ln n. Indeed, we have

The Hard-Margin Algorithm
Let the hard-margin algorithm be the function that outputs the mid-point of the largest interval between the adjacent sample points. More formally, given a sample S of size m, the algorithm sorts the sample S ∪ {0, 1} so that x 0 = 0 ≤ x 1 ≤ x 2 ≤ · · · ≤ x m ≤ 1 = x m+1 and outputs the midpoint ( Henceforth, the notion largest gap refers to the length of the largest interval between the adjacent points of a sample.
Theorem 3. The hard-margin algorithm is consistent for the family F 1 .
To prove the theorem we need the following property of the distribution of the largest gap between two adjacent elements of m points forming an i.i.d. sample from the uniform distribution on [0, 1]. The statement of which we present an (up to our knowledge) new proof has been originally proven by Lévy [10].  We first show that there exists ζ > 0 such that m ≥ (1 + ζ)b ln b for all sufficiently large m. Indeed, For any ζ < ǫ/3 and sufficiently large m the last expression is greater than m.
The existence of such ζ and Lemma 1 guarantee that for all sufficiently large m, for of each bucketing B i , with probability 1 − o(1), each bucket is hit by a sample point. We now apply union bound and get that, for all sufficiently large m, with probability 1 − (3/ǫ)o(1) = 1 − o(1), for each bucketing B i , each bucket is hit by at least one sample point. Consider any sample S such that for each bucketing, each bucket is hit by at least one point of S. Then, the largest gap in S can not be bigger than the bucket size plus the difference of offsets between two adjacent bucketings, since otherwise the largest gap would demonstrate an empty bucket in at least one of the bucketings. In other, words the largest gap, K m , is at most for any ǫ < 1.

⊓ ⊔
Proof (of the Theorem). Consider any two disjoint intervals U, V ⊆ [0, 1] such that for any x ∈ U and any y ∈ V , f (x) f (y) < p < 1 for some p ∈ (0, 1). We claim that with probability 1 − o(1), the largest gap in U is bigger than the largest gap in V .
If we draw an i.i.d. sample m points from µ, according to the law of large numbers for an arbitrarily small χ > 0, the ratio between the number of points m U in the interval U and the number of points m V in the interval V with probability 1 − o(1) satisfies For a fixed χ, choose a constant ǫ > 0 such that 1−ǫ 1+ǫ > p + χ. From Lemma 2 we show that with probability 1−o(1) the largest gap between adjacent sample points falling into U is at least (1 − ǫ)|U | ln mU mU . Similarly, with probability 1 − o(1) the largest gap between adjacent sample points falling into V is at most (1 + ǫ)|V | ln mV mV . From (8) it follows that the ratio of gap sizes with probability 1 − o(1) is at least for a constant γ > 0 such that 1 + γ ≤ 1−ǫ 1+ǫ 1 p+χ . Hence for sufficiently large m with probability 1 − o(1), the largest gap in U is strictly bigger than the largest gap in V . Now, we can choose intervals is an arbitrarily small neighbourhood containing x * . We can pick an even smaller neighbourhood U containing x * such that for all x ∈ U and all y ∈ V 1 ∪ V 2 , f (x) f (y) < p < 1 for some p ∈ (0, 1). Then with probability 1 − o(1), the largest gap in U is bigger than largest gap in V 1 and the largest gap in V 2 .
⊓ ⊔ In this section we consider the problem of learning the minimum density homogeneous (i.e. passing through origin) linear cut in distributions over R d . Namely, assuming that some unknown probability distribution generates i.i.d. finite sample of points in R d . We wish to process these samples to find the (d − 1)-dimensional hyperplane, through the origin of R d , that has the lowest probability density with respect to the sample-generating distribution. In other words, we wish to find how to cut the space R d through the origin in the "sparsest direction".
Formally, let F d be the family of all probability distributions over the R d that have a continuous density function. We wish to show that there exists a linear cut learning algorithm that is consistent for F d . Note by Theorem 5, no algorithm achieves uniform convergence for F d (even for d = 1).
Define the soft-margin algorithm with parameter γ : N → R + as follows. Given a sample S of size m, it counts for every hyperplane, the number of sample points lying within distance γ := γ(m) and outputs the hyperplane with the lowest such count. In case of the ties, it breaks them arbitrarily. We denote this algorithm by H γ . Formally, for any weight vector w ∈ S d−1 (the unit sphere in R d ) we consider the "γ-strip" h(w, γ) = {x ∈ R d : |w T x| ≤ γ} and count the number of sample points lying in it. We output the weight vector w for which the number of sample points in h(w, γ) is the smallest; we break ties arbitrarily.
To fully specify the algorithm, it remains to specify the function γ(m). As it turns out, there is a choice of the function γ(m) which makes the algorithm consistent.
Proof. The structure of the proof is similar to the proof of Theorem 1. However, we will need more technical tools. First let's fix f . For any weight vector w ∈ S d−1 and any γ > 0, we define f γ (w) as the d-dimensional integral converges uniformly to f . In other words, for every ζ > 0 there exists m 0 such that for any m ≥ 0 and any w ∈ S d−1 , Fix f and ǫ, δ > 0. Let U = {w ∈ S d−1 : |w T w * | > 1 − ǫ} be the "ǫ-double-neighbourhood" of the antipodal pair {w * , −w * }. The set S d−1 \ U is compact and hence α := min f (S d−1 \ U ) exists. Since w * , −w * are the only minimizers of f , α > f (w * ) and hence η := α − f (w * ) is positive.
The assumptions on γ(m) imply that there exists m 0 such that for all m ≥ m 0 , In this paper have presented a novel unsupervised learning problem that is modest enough to allow learning algorithm with asymptotic learning guarantees, while being relevant to several central challenging learning tasks. Our analysis can be viewed as providing justification to some common semi-supervised learning paradigms, such as the maximization of margins over the unlabeled sample or the search for empirically-sparse separating hyperplanes. As far as we know, our results provide the first performance guarantees for these paradigms.
From a more general perspective, the paper demonstrates some type of meaningful information about a data generating probability distribution that can be reliably learned from finite random samples of that distribution, in a fully non-parametric model -without postulating any prior assumptions about the structure of the data distribution. As such, the search for a low-density data separating hyperplane can be viewed as a basic tool for the initial analysis of unknown data. Analysis that can be carried out in situations where the learner has no prior knowledge about the data in question and can only access it via unsupervised random sampling.
Our analysis raises some intriguing open questions. First, note that while we prove the universal consistency of the 'hard-margin' algorithm for Real data distributions, we do not have a similar result for higher dimensional data. Since searching for empirical maximal margins is a common heuristic, it is interesting to resolve the question of consistency of such algorithms.
Another natural research direction that this work calls for is the extension of our results to more complex separators. In clustering, for example, it is common to search for clusters that are separated by sparse data regions. however, such between-cluster boundaries are often not linear. Can one provide any reliable algorithm for the detection of sparse boundaries from finite random samples when these boundaries belong to a richer family of functions?
Our research has focused on the information complexity of the task. However, to evaluate the practical usefulness of our proposed algorithms, one should also carry a computational complexity analysis of the low-density separation task. We conjecture that the problem of finding the homogeneous hyperplane with largest margins, or lowest density around it (with respect to a finite high dimensional set of points) is NP-hard (when the Euclidean dimension is considered as part of the input, rather than as a fixed constant parameter). however, even if this conjecture is true, it will be interesting to find efficient approximation algorithms for these problems.