{'fraction_non_alphanumeric': 0.04831911175079675, 'fraction_numerical': 0.014547136835612214, 'mean_word_length': 3.911638475132542, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Adaptive Semisupervised Inference

Semisupervised methods inevitably invoke some assumption that links the marginal distribution of the features to the regression function of the label. Most commonly, the cluster or manifold assumptions are used which imply that the regression function is smooth over high-density clusters or manifolds supporting the data. A generalization of these assumptions is that the regression function is smooth with respect to some density sensitive distance. This motivates the use of a density based metric for semisupervised learning. We analyze this setting and make the following contributions - (a) we propose a semi-supervised learner that uses a density-sensitive kernel and show that it provides better performance than any supervised learner if the density support set has a small condition number and (b) we show that it is possible to adapt to the degree of semi-supervisedness using data-dependent choice of a parameter that controls sensitivity of the distance metric to the density. This ensures that the semisupervised learner never performs worse than a supervised learner even if the assumptions fail to hold.


Introduction
Semisupervised methods inevitably invoke some assumption that links the marginal distribution p(x) of the features X to the regression function f (x) = E[Y |X = x] of the label Y . The most common assumption is the cluster assumption in which it is assumed that f is very smooth wherever p exhibits clusters [Lafferty and Wasserman, 2007, Rigollet, 2007, Seeger, 2000, Singh et al., 2008a. In the special case where the clusters are manifolds, this is called the manifold assumption [Belkin and Niyogi, 2004, Lafferty and Wasserman, 2007, Niyogi, 2008.
A generalization of the cluster and manifold assumptions is that the regression function is smooth with respect to some density-sensitive distance. Several recent papers propose using a density based metric or diffusion distance for semisupervised learning [Bousquet et al., 2004, Coifman and Lafon, 2006, Sajama and Orlitsky, 2005.
In this paper, we analyze semisupervised inference under this generalized assumption.
Singh, Nowak and Zhu [2008a], Lafferty and Wasserman [2007] and Nadler et al [2009] have showed that the degree to which unlabeled data improves performance is very sensitive to the cluster and manifold assumptions. In this paper, we introduce adaptive semisupervised inference. We define a parameter α that controls the sensitivity of the distance metric to the density, and hence the strength of the semisupervised assumption. When α = 0 there is no semisupervised assumption, that is, there is no link between f and p. When α = ∞ there is a very strong semisupervised assumption. We use the data to estimate α and hence we adapt to the appropriate assumption linking f and p.
This paper makes the following contributions -(a) we propose a semi-supervised learner that uses a densitysensitive kernel and show that it provides better performance than any supervised learner if the density support set has a small condition number and (b) we show that it is possible to adapt to the degree of semi-supervisedness using data-dependent choice of a parameter that controls sensitivity of the distance metric to the density. This ensures that the semisupervised learner never performs worse than a supervised learner even if the assumptions fail to hold. Preliminary simulations, to be reported in future work, confirmed that our proposed estimator adapts well to alpha and has good risk when the semisupervised smoothness holds and when it fails.
Related Work. There are a number of papers that discuss conditions under which semisupervised methods can succeed or that discuss metrics that are useful for semisupervised methods. These include Bousquet et al. [2004], Singh et al. [2008b, Nadler et al. [2009], Sajama andOrlitsky [2005] and references therein. However, to the best of our knowledge, there are no papers that explicitly study adaptive methods that allow the data to choose the strength of the semisupervised assumption.
Outline. This paper is organized as follows. In Section 2 we define a set of joint distributions P XY (α) indexed by α. In Section 3, we define a density sensitive estimator f α of f , assuming that (f, p) ∈ P XY (α). We find finite sample bounds on the error of f α and we investigate the dependence of this error on α. In Section 4, we show that cross-validation can be used to adapt to α. We conclude in Section 5.

Definitions
We consider the collection of joint distributions P XY (α) = P X × P Y |X indexed by a density-sensitivity parameter α as follows. X, Y are random variables, X is supported on a compact domain X ⊂ R d , and Y is realvalued. The marginal density p(x) ∈ [λ 0 , Λ 0 ] is bounded over its support {x : p(x) > 0}, where 0 < λ 0 , Λ 0 < ∞. Also, let the conditional density be p(y|x) with variance bounded by σ 2 , and conditional label mean or regression function be f (x) = E[Y |X = x], with |f (x)| ≤ M . We say that (p, f ) ∈ P XY (α) if these functions satisfy the properties described below.
Before stating the properties of f and p, we define a distance metric with density sensitivity α.
Density-sensitive distance: We consider the following distance with density sensitivity α ∈ [0, ∞) between two points x 1 , x 2 ∈ X that is a modification of the definition in Sajama and Orlitsky [2005]: where Γ(x 1 , x 2 ) is the set of all continuous finite curves from x 1 to x 2 with unit speed everywhere and L(γ) is the length of curve γ (i.e. γ(L(γ)) = x 2 ). Notice that large α makes points connected by high density paths closer, and α = 0 corresponds to Euclidean distance.
Our first assumption is that the regression function f is smooth with respect to the density sensitive distance: A1) Semisupervised smoothness: The regression func- is β-smooth with respect to the density-sensitive distance D α , i.e. there exists constants C 1 , β > 0 such that for all In particular if α = 0 and β = 1, this corresponds to Lipschitz smoothness.
Our second assumption is that the density function p is smooth with respect to Euclidean distance over the support set. Recall that the support of p is S = {x : p(x) > 0}.
A2) Density smoothness: The density function p(x) is Hölder η-smooth with respect to Euclidean distance if it has η derivatives and there exists a constant C 2 > 0 such that for all where η is the largest integer such that η < η, and T η x2 is the Taylor polynomial of degree η around the point x 2 .
The condition number of a set S with boundary ∂S is the largest real number τ > 0 such that, if d(x, ∂S) ≤ τ then x has a unique projection onto the boundary of S. Here, d(x, ∂S) = inf z∈∂S ||x − z||. When τ is large, S cannot be too thin, the boundaries of S cannot be too curved and S cannot get too close to being self-intersecting. If S consists of more than one connected component, then τ large also means that the connected components cannot be too close to each other. Let τ 0 denote the smallest condition number of the support sets S of all p ∈ P X . We shall see that semisupervised inference outperforms supervised inference when τ 0 is small. Additionally, we assume that S has at most K < ∞ connected components.
In the supervised setting, we assume access to n labeled data L = {X i , Y i } n i=1 drawn i.i.d. from P XY (α), and in the semi-supervised setting, we assume access to m ad- As usual, we write a n = O(b n ) if |a n /b n | is bounded for all large n. Similarly, a n = Ω(b n ) if |a n /b n | is bounded away from 0 for all large n. We write a n b n if a n = O(a n ) and a n = Ω(b n ).

Density-Sensitive Inference
Let K(x) be a symmetric non-negative function and let K h (x) = K( x /h). Let 2 be the kernel density estimator of p with bandwidth h m , based on the unlabeled data. Define the support set estimate S = {x : p m (x) > 0} and the empirical boundary region where δ m = 2c 2 √ d (log 2 m)/m 1 d for some constant c 2 > 0. Now define a plug-in estimate of the D α distance as follows: We consider the following semisupervised learner which uses a kernel that is sensitive to the density. In the following definitions we take, for simplicity, K(x) = I(||x|| ≤ 1).

Performance upper bound for semisupervised estimator
The following theorem characterizes the performance of the density sensitive semisupervised kernel estimator.
Theorem 1. Assume λ 0 > 1+c 0 for some constant c 0 > 0 1 and let m = c 1 (log m) −1/2 for constant c 1 > 0 and The proof of Theorem 1 is given in section 6. The first term is negligible when the amount of unlabeled data m is large. The second term is the bias and third term is variance. If the bandwidth and α log m is large enough, then the density-sensitive semisupervised kernel estimator is able to achieve an integrated MSE rate of O(n −1 ) for all joint distributions in P XY (α) supported on sets with condition number τ 0 > 3δ m .

Performance lower bound for any supervised estimator
We now establish a lower bound on the performance of any supervised estimator.
where the inf is over all supervised estimators.
Coupled with Theorem 1, the results state that if the condition number of the support set is small 3δ m < τ 0 ≤ c 5 n − 1 d−1 and α is large enough, then the densitysensitive semi-supervised estimator outperforms any supervised learning algorithm in terms of integrated MSE rate.
A complete proof of Theorem 2 is given in the appendix. Here we provide some intuition regarding the proof strategy. We construct a set of joint distributions over X and Y that depends on n, and apply Assouad's Lemma. Intuitively, we need to take advantage of the decreasing condition number τ 0 . This is because if τ 0 were to be kept fixed, as n increases the semi-supervised assumption would reduce to familiar Euclidean smoothness.
So, we construct the distributions as follows. We split the unit cube in R d into two rectangle sets with a small gap in between, and let the marginal density p be uniform over these sets. Then we add a series of "bumps" between the two rectangles, as shown schematically in Figure 1. Over one of the sets we set f ≡ M , and over the other we set f ≡ −M . The number of bumps increases with n, implying that the condition number must decrease. The sets are designed specifically so that the condition number can be lower bounded easily as a function of n. In essence, as n increases these boundaries become space-filling, so that there is a region where the regression function could be M or −M , and it is not possible to tell which with only labeled data. 3 Figure 1: A two-dimensional cross-section of the support of a marginal density p used in the proof of Theorem 2.

Adaptive Semisupervised Inference
In section 3.1, we established a bound on the integrated mean square error of the density-sensitive semisupervised kernel estimator. The bound is achieved by using an estimate D α of the density-sensitive distance. However, this requires knowing the density-sensitive parameter α, along with other parameters.
It is critical to choose α (and h) appropriately, otherwise we might incur a large error if the semisupervised assumption does not hold or holds with a different density sensitivity value α. The following result shows that we can adapt to the correct degree of semisupervisedness α if cross-validation is used to select the appropriate α and h. This implies that the estimator gracefully degrades to a supervised learner if the semisupervised assumption (sensitivity of regression function to marginal density) does not hold (α = 0).
where f * is the true regression function. Let H be a finite set of bandwidths and let A be a finite set of values for α. Divide the data into training data T and validation data V . For notational simplicity, let both sets have size n. Let F = { f T α,h } α∈A,h∈H denote the semisupervised kernel estimators trained on data T using α ∈ A and h ∈ H.
See appendix for proof. In practice, both H and A may be taken to be of size n a for some a > 0. Then we can approximate the optimal h and α with sufficient accuracy to achieve the optimal rate. Setting δ = 1/(4M 2 n), we then see that the penalty for adaptation is log(|A||H|/δ) nt + δM = O(log n/n) and hence introduces only a logarithmic term.

Discussion
Semisupervised methods are very powerful but, like all methods, they only work under certain conditions. We have shown that, when the support of the distribution is somewhat irregular (i.e., the boundary of the support of the density has a small condition number), then semi-supervised methods can attain better performance. Specifically, we demonstrated that a semi-supervised kernel estimator that uses a density-sensitive distance can outperform any supervised estimator in such cases.
We introduced a family of estimators indexed by a parameter α. This parameter controls the strength of the semi-supervised assumption. We showed that the behavior of the semi-supervised method depends critically on α.
Finally, we showed that cross-validation can be used to automatically adapt to α so that α does not need to be known. Hence, our method takes advantage of the unlabeled data when the semi-supervised assumption holds, but does not add extra bias when the assumption fails. Preliminary simulations confirm that our proposed estimator adapts well to alpha and has good risk when the semi-supervised smoothness holds and when it fails. We will report these results in future work.
The analysis in this paper can be extended in several ways. First, it is possible to use other density sensitive metrics such as the diffusion distance [Lee and Wasserman, 2008]. Second, it is possible to relax the assumption that the density p is strictly bounded away from 0 on its support. Finally, other estimators besides kernel estimators can be used. We will report on these extensions elsewhere.

Proof of Theorem 1
Here we prove Theorem 1 stated in section 3.1 (repeated below for convenience), using some results given in the appendix. Theorem 4. Assume λ 0 > 1+c 0 for some constant c 0 > 0 3 and let m = c 1 (log m) −1/2 for constant c 1 > 0 and Proof. Let G m be the indicator of the event when the unlabeled sample is such that sup We can write 3 This assumption is more restrictive than necessary, and a more general statement can be by introducing a rescaling factor in the definition of the density-sensitive distance.
where S * m as defined in Proposition 2. For the boundary region we have where Leb denotes the Lebesgue measure. Since the radius of curvature of ∂S is at least τ 0 , and τ 0 > 3δ m , we have by Proposition 3, Following the derivation in Chapter 5 of Gyorfi et al. [2002], we have where the d S * m distance is the length of the shortest path between two points restricted to S * m , as defined in the appendix. Clearly S * m has condition number at least τ 0 − 3δ m > 0. If S * m has exactly one connected component, then Proposition 4 combined with the assumption that Since S * m can have at most K connected components, we can repeat the same argument for each component and conclude that

Appendix
Results used in proof of Theorem 1 In order to prove Theorem 1, we characterize how the plug-in densitysensitive distance estimate D α behaves. For this, we start with a result about the density estimator.
Theorem 5. If m ≥ m 0 , where m 0 ≡ m 0 (λ 0 , Λ 0 ) is a constant, then for all marginal densities p of distributions in P XY (α), we have with probability > 1 − 1/m, Proof. Follows from Theorem 1 in Singh et al. [2008a] by noting that since the density estimate will be 0 a.s. outside the boundary region, and we have p ≥ λ 0 on S, for sufficiently large m (i.e. small m ), we must have S\R ∂S ⊆ S ⊆ S ∪ R ∂S .
The following two propositions now characterize how the plug-in density-sensitive distance estimate D α behaves.
Then for any (x 1 , x 2 ) ∈ Ψ, Proof. Note that by the triangle inequality, R ∂S ⊆ R ∂S , so S\ R ∂S ⊆ S\R ∂S since τ 0 > 2δ m for m large enough. We see that if (x 1 , x 2 ) ∈ Ψ, then x and y must be in the same connected component of S\ R ∂S , and, furthermore, all points along any path in Γ(x 1 , x 2 ) must also be in the same connected component. For Similarly,

Given a set
Proposition 2. With the notation of Proposition 1, for all Then for any (x 1 , x 2 ) ∈ Ψ, Proof. Since for any x 1 and x 2 , since, by the triangle inequality, S * m ⊆ S\ R ∂S . Applying Proposition 1, the result follows.
To prove Theorem 1, we also need the following two results.
Proposition 3. Let X be a compact subset of R d , and T > 0. Then for any τ ∈ (0, T ), for all sets S ⊆ X with condition number at least τ , Vol(∂S) ≤ c 3 /τ for some c 3 independent of τ , where Vol is the d − 1-dimensional volume.
Proof. Let {z i } N i=1 be a minimal Euclidean τ /2covering of ∂S, and B i = {x : x − z i 2 ≤ τ /2}. Let T i be the tangent plane to ∂S at z i . Then using the argument made in the proof of Lemma 4 in Genovese et al. [2010], for some constants C 1 and C 2 independent of τ . Since X is compact, for some constant C depending only on X and T , where N denotes the covering number (note that even though ∂S is a d − 1 dimensional set, we can't claim N (∂S, · 2 , τ ) = O(τ −(d−1) ), since ∂S can become space-filling as τ → 0). So and the result follows with c 3 = C 2 C.
Proposition 4. Let X be a compact subset of R d , and T > 0. Then for any τ ∈ (0, T ), for all compact, connected sets S ⊆ X with condition number at least τ , sup Proof. First consider the quantity Since ∂S is closed, there must exist u * , v * ∈ ∂S such that sup u,v∈∂S By Proposition 6.3 in Niyogi et al. [2008] (or see Lemma 3 in Genovese et al. [2010]), if x, y ∈ ∂S such that x − y 2 = a ≤ τ /2, then d ∂S (x, y) ≤ τ − τ 1 − (2a)/τ . In particular, if x − y 2 ≤ τ /2, then d ∂S (x, y) ≤ τ . So any Euclidean τ /2-covering of ∂S is also a τ -covering 8 in the d ∂S metric. Then we have for some constant C depending only on X and T (note that, as in the proof of 3, even though ∂S is a d − 1 dimensional set, we can't claim N (∂S, · 2 , τ ) = O(τ −(d−1) ), since ∂S can become space-filling as τ → 0).
which must exist since S is compact. Let u ‡ , v ‡ ∈ ∂S be the (not necessarily unique) projections of u † and v † onto ∂S. Clearly the line segment connecting u † and u ‡ is fully contained in S, and the same applies to v † and v ‡ . So Theorem 6. Let Ω = {0, 1} q , the collection of binary vectors of length q ≥ 1. Let P Ω = {P ω , ω ∈ Ω} be the corresponding collection of 2 q probability measures associated with each vector. Also let P ω ∧ P ω denote the affinity between two distributions (i.e. P ω ∧ P ω = 1 − sup A |P ω (A) − P ω (A)|, where the supremum is over all measurable sets), and ρ(·, ·) denotes the Hamming distance between two binary vectors. For any semidistance d We now prove Theorem 2.
is the Dirac delta (we could also use a conditional distribution that is absolutely continuous with respect to Lebesgue measure; the result would be the same). Finally, let P ω denote the measure on R d+1 defined by p ω (x) and p ω (y|x), and P ω n the corresponding product measure.
Then, using the previous concentration result, and taking union bound over all f ∈ F, we have with probability > 1 − δ, Now consider Taking expectation with respect to validation dataset, Now taking expectation with respect to training dataset, Since this holds for all f ∈ F, we get: The result follows since F = { f T α,h } α∈A,h∈H and |F| = |A||H|.