Learning Sets with Separating Kernels

Introduction

In this paper we study the problem of learning from data the set where the data probability distribution is concentrated. Our study is more broadly motivated by questions in unsupervised learning, such as the problem of inferring geometric properties of probability distributions from random samples.

In recent years, there has been great progress in the theory and algorithms for supervised learning, i.e. function approximation problems from random noisy data . On the other hand, while there are a number of methods and studies in unsupervised learning, e.g. algorithms for clustering, dimensionality reduction, dictionary learning (see Chapter 14 of ), many interesting problems remain largely unexplored.

Our analysis starts with the observation that many studies in unsupervised learning hinge on at least one of the following two assumptions. The first is that the data are distributed according to a probability distribution which is absolutely continuous with respect to a reference measure, such as the Lebesgue measure. In this case it is possible to define a density and the corresponding density level sets. Studies in this scenario include to name a few. Such an assumption prevents considering the case where the data are represented in a high dimensional Euclidean space but are concentrated on a Lebesgue negligible subset, as a lower dimensional submanifold. This motivates the second assumption – sometimes called manifold assumption – postulating that the data lie on a low dimensional Riemannian manifold embedded in an Euclidean space. This latter idea has triggered a large number of different algorithmic and theoretical studies (see for example ). Though the manifold assumption has proved useful in some applications, there are many practical scenarios where it might not be satisfied. This observation has motivated considering more general situations such as manifold plus noise models , and models where the data are described by combinations of more than one manifold .

Here we consider a different point of view and work in a setting where the data are described by an abstract probability space and a similarity function induced by a reproducing kernel . In this framework, we consider the basic problem of estimating the set where the data distribution is concentrated (see Section 1.2 for a detailed discussion of related works). A special class of reproducing kernels, that we call separating kernels, plays a special role in our study. First, it allows to define a suitable metric on the probability space and makes the support of the distribution well defined; second, it leads to a new analytical characterization of the support in terms of the null space of the integral operator associated to the reproducing kernel.

This last result is the key towards a new computational approach to learn the support from data, since the integral operator can be approximated with high probability from random samples . Estimation of the null space of the integral operator can be unstable, and regularization techniques can be used to obtain stable estimators. In this paper we study a class of regularization techniques proposed to solve ill-posed problems and already studied in the context of supervised learning . Regularization is achieved by filtering out the small eigenvalues of the sample empirical matrix defined by the kernel. Different algorithms are defined by different filter functions and have different computational properties. Consistency and stability properties for a large class of spectral filters and of the corresponding algorithms are established in a unified framework. Numerical experiments show that the proposed algorithms are competitive, and often better, than other state of the art techniques.

The paper is divided into two parts. The first part includes Section 2, where we establish several mathematical results relating reproducing kernel Hilbert spaces of functions on a set $X$ and the geometry of the set $X$ itself. In particular, in this section we introduce the concept of separating kernel, which we further explore in Section 3. These results are of interest in their own right, and are at the heart of our approach. In the second part of the paper we discuss the problem of learning the support from data. More precisely, in Section 4 we illustrate some algorithms for learning the support of a distribution from random samples. In Section 5 we establish universal consistency for the proposed methods and discuss stability to random sampling. We conclude in Section 6 and 7 with some further discussions and some numerical experiments, respectively. A conference version of this paper appeared in . We now start by describing in some more detail our results and discussing some related works.

In this section we briefly describe the main ideas and results in the paper.

The setting we consider is described by a probability space $(X,\rho)$ and a measurable reproducing kernel $K$ on the set $X$ . The data are independent and identically distributed (i.i.d.) samples $x_{1},\dots,x_{n}$, each one drawn from $X$ with probability $\rho$. The reproducing kernel $K$ reflects some prior information on the problem and, as we discuss in the following, will also define the geometry of $X$. The goal is to use the sample points $x_{1},\dots,x_{n}$ to estimate the region where the probability measure $\rho$ is concentrated.

To fix some ideas, the space $X$ can be thought of as a high-dimensional Euclidean space and the distribution $\rho$ as being concentrated on a region $X_{\rho}$, which is a smaller – and potentially lower dimensional – subset of $X$ (e.g. a linear subspace or a manifold). In this example, the goal is to build from data an estimator $X_{n}$ which is, with high probability, close to $X_{\rho}$ with respect to a suitable metric.

We first note that a precise definition of $X_{\rho}$ requires some care. If $\rho$ is assumed to have a continuous density with respect to some fixed reference measure (for example, the Lebesgue measure in the Euclidean space), then the region $X_{\rho}$ can be easily defined to be the closure of the set of points where the density function is non-zero. Nevertheless, this assumption would prevent considering the situation where the data are concentrated on a “small”, possibly lower dimensional, subset of $X$. Note that, if the set $X$ were endowed with a topological structure and $\rho$ were defined on the corresponding Borel $\sigma$-algebra, it would be natural to define $X_{\rho}$ as the support of the measure $\rho$, i.e. the smallest closed subset of $X$ having measure one. However, since the set $X$ is only assumed to be a measurable space, no a priori given topology is available. Here we also remark that the definition of $X_{\rho}$ is not the only point where some further structure on $X$ would be useful. Indeed, when defining a learning error, a notion of distance between the set $X_{\rho}$ and its estimator $X_{n}$ is also needed and hence some metric structure on $X$ is required.

The idea is to use the properties of the reproducing kernel $K$ to induce a metric structure – and consequently a topology – on $X$. Indeed, under some mild technical assumptions on $K$, the function

defines a metric on $X$, thus making $X$ a topological space. Then, it is natural to define $X_{\rho}$ to be the support of $\rho$ with respect to such metric topology. Moreover, the Hausdorff distance $d_{H}$ induced by the metric $d_{K}$ provides a notion of distance between closed sets.

The problem we consider can now be restated as follows: we want to learn from data an estimator $X_{n}$ of $X_{\rho}$, such that $\lim_{n\to\infty}d_{H}(X_{n},X_{\rho})=0$ almost surely. While $X_{\rho}$ is now well defined, it is not clear how to build an estimator from data. A main result in the paper, given in Theorem 3, provides a new analytic characterization of $X_{\rho}$, which immediately suggests a new computational solution for the corresponding learning problem. To derive and state this result, we introduce a new notion of reproducing kernels, called separating kernels, that, roughly speaking, captures the sense in which the reproducing kernel and the probability distribution need to be related. We say that a reproducing kernel Hilbert space $\mathcal{H}$ (or equivalently its kernel) separates a subset $C\subset X$, if, for any $x\not\in C$, there exists $f\in\mathcal{H}$ such that

If $K$ separates all possible closed subsets in $X$, we say that it is completely separating. Figure 1 illustrates the notion of separating kernel in the simple example of the linear kernel in a Euclidean space.

Now, Theorem 3 states that, if either $K$ is completely separating, or at least separates $X_{\rho}$, then $X_{\rho}$ is the level set of a suitable distribution dependent continuous function $F_{\rho}$. More precisely, let ${\mathcal{H}}$ be the reproducing kernel Hilbert space associated to $K$ , $T:\mathcal{H}\to\mathcal{H}$ the integral operator with kernel $K$, and denote by $T^{\dagger}$ its pseudo-inverse. If we consider the function $F_{\rho}$ on $X$, defined by

and $K$ separates $X_{\rho}$, then we prove that

(where for simplicity we are assuming $K(x,x)=1$ for all $x\in X$).

The above result is crucial since the integral operator $T$ can be approximated with high probability from data (see and references therein). However, since the definition of $F_{\rho}$ involves the pseudo-inverse of $T$, the support estimation problem can be unstable and regularization techniques are needed to ensure stability. With this in mind, we propose and study a family of spectral regularization techniques which are classical in inverse problems and have been considered in supervised learning in . We define an estimator by

where $F_{n}(x)=(1/n){\mathbf{K}}_{{\mathbf{x}}}^{\top}\,g_{\lambda_{n}}({\mathbf{K}_{n}}/n){\mathbf{K}}_{{\mathbf{x}}}$, with ${\mathbf{(}{\mathbf{K}}_{n})}_{i,j}=K(x_{i},x_{j})$, ${\mathbf{K}}_{{\mathbf{x}}}$ is the column vector whose $i$-th entry is $K(x_{i},x)$, and ${\mathbf{K}}_{{\mathbf{x}}}^{\top}$ is its transpose. Here $g_{\lambda_{n}}({\mathbf{K}_{n}}/n)$ is a matrix defined via spectral calculus by a spectral filter function $g_{\lambda_{n}}$ that suppresses the contribution of the eigenvalues smaller than $\lambda_{n}$. Examples of spectral filters include Tikhonov regularization and truncated singular values decomposition , to name a few.

This class of methods can be studied within a unified framework, and the error analysis in the paper establishes strong universal consistency if $X_{\rho}$ is separated by $K$. More precisely, under the latter assumption, we show in Theorem 6 that,

provided that $X$ is compact and the sequences $(\tau_{n})_{n\geq 1},(\lambda_{n})_{n\geq 1}$ are chosen so that,

where $L_{\lambda_{n}}$ is the Lipschitz constant of the function $r_{\lambda_{n}}(\sigma)=\sigma g_{\lambda_{n}}(\sigma)$. The above result is universal in the sense that consistency can be shown without assuming regularity condition on $\rho$ or $X_{\rho}$.

The proof of the above result crucially depends on estimating the deviation between $F_{n}$ and $F_{\rho}$. Indeed, for the above choice of the sequence $\lambda_{n})_{n\geq 1}$ we show that

Under suitable distribution dependent assumptions, the above result can be further developed to obtain finite sample bounds quantifying stability to random sampling. Indeed, if the couple $(\rho,K)$ is such that $\sup_{x\in X}\left\lVert{T^{-s/2}T^{\dagger}TK_{x}}\right\rVert<+\infty$, with $0<s\leq 1$, and the eigenvalues of the (compact and positive) operator $T$ satisfy $\sigma_{j}\sim j^{-1/b}$ for some $0<b\leq 1$, then we prove in Theorem 7 that, for $n\geq 1$ and $\delta>0$, we have

with probability at least $1-2e^{-\delta}$, for $\lambda_{n}=n^{-1/(2s+b+1)}$ and a suitable constant $C_{s,b,\delta}$ which does not depend on $n$.

2 State of the art

where $B(x,\epsilon)$ is the ball of center $x$ and radius $\epsilon$, and $\epsilon_{n}$ slowly goes to zero when $n$ tends to infinity. Consistency and minimax converges rates are studied in with respect to the distance

where $C_{1}\triangle C_{2}=(C_{1}\setminus C_{2})\cup(C_{2}\setminus C_{1})$ and $\mu$ is a suitable known measure. If $\rho$ has a density $f$ with respect to some known measure $\mu$, a traditional approach is based on a non-parametric estimator $f_{n}$ of $f$, a so called plug-in estimator. A kernel based class of plug-in estimators is proposed in , namely

where $h_{n}$ is a regularization parameter and $c_{n}$ is a suitable threshold. Convergence rates with respect to $d_{\mu}$ are provided in . A related problem is level set estimation, where the goal is to detect the high density regions $\left\{x\in X\mid f(x)\geq c\right\}$. Consistency and optimal convergence rates for different plug-in estimators

Kernels, Integral Operators and Geometry in Spaces of Probabilities

In this section we establish the results that provide the foundations of our approach. The basic framework in this paper is described by a triple $(X,\rho,K)$, where

$X$ is a set (endowed with a $\sigma$-algebra $\mathcal{A}_{X}$);

$\rho$ is a probability measure defined on $X$;

$K$ is a (real) reproducing kernel on $X$, i.e. a real function on $X\times X$ of positive type.

We interpret $X$ as the data space and $\rho$ as the probability distribution generating the data. Roughly speaking, the kernel $K$ provides a natural similarity measure on $X$ and it defines its geometry.

We denote by $\mathcal{H}$ the reproducing kernel Hilbert space associated with the reproducing kernel $K$ (we refer to for an exhaustive review on the theory of reproducing kernel Hilbert spaces). The scalar product and norm in $\mathcal{H}$ are denoted by $\left\langle{\cdot},{\cdot}\right\rangle$ and $\left\lVert{\cdot}\right\rVert$, respectively. We recall that the elements of $\mathcal{H}$ are real functions on $X$, and the reproducing property $f(x)=\left\langle{f},{K_{x}}\right\rangle$ holds true for all $x\in X$ and $f\in\mathcal{H}$, where $K_{x}\in\mathcal{H}$ is defined by $K_{x}(y)=K(y,x)$.

In order to prove our results, we need some technical conditions on $K$.

The kernel $K$ has the following properties:

for all $x,y\in X$ with $x\neq y$ we have $K_{x}\neq K_{y}$;

the associated reproducing kernel Hilbert space $\mathcal{H}$ is separable;

the real function $K$ is measurable with respect to the product $\sigma$-algebra $\mathcal{A}_{X}\otimes\mathcal{A}_{X}$;

Assumptions 1.a), 1.b) and 1.c) are minimal requirements. In particular, Assumptions 1.a) and 1.b) are needed in order to define a separable metric structure on $X$, while Assumption 1.c) ensures that such metric topology is compatible with the $\sigma$-algebra $\mathcal{A}_{X}$ (see Proposition 1 below). In Proposition 2, the combination of 1.a), 1.b) and 1.c) will allow us to define the support $X_{\rho}$ of the probability measure $\rho$, as anticipated in Section 1.1. Assumption 1.d), instead, is a normalization requirement, and could be replaced by a suitable boundedness condition (in fact, even weaker integrability conditions could also be considered). We choose the normalization $K(x,x)=1$ $\forall x\in X$ since it makes equations more readable, and it is not restrictive in view of Proposition 13 in A.1.

We now show how the above assumptions allow us to define a metric on $X$ and to characterize the corresponding support of $\rho$ in terms of the integral operator with kernel $K$.

Our first result makes $X$ a separable metric space isometrically embedded in $\mathcal{H}$. This point of view is developed in . The relation between metric spaces isometrically embedded in Hilbert spaces and kernels of positive type was studied by Schoenberg around 1940. A recent discussion on this topic can be found in Chapter 2 § 3 of .

Under Assumption 1.a), the map $d_{K}:X\times X\to[0,+\infty[$ defined by

the map $x\mapsto K_{x}$ is an isometry from $X$ into $\mathcal{H}$;

the kernel $K$ is a continuous function on $X\times X$, and each $f\in\mathcal{H}$ is a continuous function.

If also Assumption 1.b) is satisfied, then

the metric space $(X,d_{K})$ is separable.

Finally, if also Assumption 1.c) holds true, then

the closed subsets of $X$ are measurable (with respect to $\mathcal{A}_{X}$);

if $Y$ is a topological space endowed with its Borel $\sigma$-algebra and $f:X\to Y$ is continuous, then $f$ is measurable; in particular, the functions in $\mathcal{H}$ are measurable.

Many of these properties are known in the literature, see for example and references therein. For the reader’s convenience, we give a self-contained short proof. Assumption 1.a) states that the map $x\mapsto K_{x}$ is injective. Since $d_{K}(x,y)=\left\lVert{K_{x}-K_{y}}\right\rVert$ by definition, $d_{K}$ is the metric on $X$ making $x\mapsto K_{x}$ an isometry, as claimed in item i). About ii), the kernel $K$ is continuous since $K(x,y)=\left\langle{K_{y}},{K_{x}}\right\rangle$ and the map $x\mapsto K_{x}$ is continuous by item i); furthermore, the elements of $\mathcal{H}$ are continuous by the reproducing property $f(x)=\left\langle{f},{K_{x}}\right\rangle$. If also Assumption 1.b) holds true, then the set ${\left\{K_{x}\mid x\in X\right\}}$ is separable in $\mathcal{H}$, and so is $X$ as the map $x\mapsto K_{x}$ is isometric from $X$ onto $\left\{K_{x}\mid x\in X\right\}$. Item iii) then follows. Suppose now that also Assumption 1.c) holds true. Then the map $d_{K}$ is a measurable map, so that the open balls of $X$ are measurable. Since $X$ is separable, any open set is a countable union of open balls, hence it is measurable. It follows that the closed subsets are measurable, too, hence item iv). Let $Y$ and $f$ be as in item v). If $A\subset Y$ is closed, then $f^{-1}(A)$ is closed in $X$, hence measurable by item iv). It follows that $f^{-1}(A)$ is measurable for all Borel sets $A\subset Y$, i.e. $f$ is measurable. Since the elements of $\mathcal{H}$ are continuous by ii), they are measurable, and item v) is proved. ∎

In the rest of the paper we will always consider $X$ as a topological metric space with metric $d_{K}$. Note that $d_{K}$ is the metric induced on $X$ by the norm of $\mathcal{H}$ through the embedding ${x\mapsto K_{x}}$. The next result shows that under our assumptions we can define the set $X_{\rho}$ as the smallest closed subset of $X$ having measure one.

Under Assumptions 1.a), 1.b) and 1.c), there exists a unique closed subset $X_{\rho}\subset X$ with $\rho(X_{\rho})=1$ satisfying the following property: if $C$ is a closed subset of $X$ and $\rho(C)=1$, then $C\supset X_{\rho}$.

Clearly, $X_{\rho}$ is closed and measurable by Proposition 1. Since $X$ is separable, there exists a sequence of closed subsets $(C_{j})_{j\geq 1}$ such that every closed subset $C=\cap C_{j_{k}}$, for some suitable subsequence. Hence, $X_{\rho}=\bigcap\limits_{j\mid\rho(C_{j})=1}C_{j}$ and, as a consequence, $\rho(X_{\rho})=1$. ∎

We add one remark. The set $X_{\rho}$ is called the support of the measure $\rho$ and clearly depends both on the probability distribution and on the topology induced by the kernel $K$ through the metric $d_{K}$ on $X$.

2 Separating Kernels

The following definition of separating kernel plays a central role in our approach.

We say that the reproducing kernel Hilbert space $\mathcal{H}$ separates a subset $C\subset X$, if, for all $x\not\in C$, there exists $f\in\mathcal{H}$ such that

In this case we also say that the corresponding reproducing kernel separates $C$.

We add some comments. First, in (2) the function $f$ depends on $x$ and $C$. Second, the reproducing property and (2) imply that $K_{x}\neq 0$ and $K_{x}\neq K_{y}$ for all $x\not\in C$ and $y\in C$ (compare with Assumption 1.a)). Finally, we stress that a different notion of separating property is given in .

Next, we provide an equivalent characterization of the separating property, which will be the key to a computational approach to support estimation. For any set $C$, let $P_{C}:\mathcal{H}\to\mathcal{H}$ be the orthogonal projection onto the closed subspace

i.e. the closure of the linear space generated by the family $\left\{K_{x}\mid x\in C\right\}$. Note that $P_{C}^{2}=P_{C}$, $P_{C}^{\top}=P_{C}$ and

The Hilbert space $\mathcal{H}_{C}$ is a closed subspace of the reproducing kernel Hilbert space $\mathcal{H}$, and it is itself a reproducing kernel Hilbert space of functions on $X$ with reproducing kernel $K_{C}(x,y)=\left\langle{P_{C}K_{y}},{P_{C}K_{x}}\right\rangle=\left\langle{P_{C}K_{y}},{K_{x}}\right\rangle$. Note that $K_{C}(x,y)=K(x,y)$ for all $x,y\in C$ by definition of $P_{C}$. Clearly, the function $F_{C}$ corresponds to the value of $K_{C}$ on the diagonal.

For any subset $C\subset X$, the following facts are equivalent:

for all $x\not\in C$, $K_{x}\notin\operatorname{ran}\,P_{C}$;

$\displaystyle{C=\left\{x\in X\mid F_{C}(x)=K(x,x)\right\}}$;

$\displaystyle{{\left\{K_{x}\mid x\in C\right\}=\left\{K_{x}\mid x\in X\right\}}\cap\operatorname{ran}\,P_{C}}$.

Under Assumption $\ref{A}.\ref{A3})$, if $C$ is separated by $\mathcal{H}$, then $C$ is closed with respect to the metric $d_{K}$.

We first prove that i) $\Rightarrow$ ii). Given $x\notin C$, by assumption there is $f\in\mathcal{H}$ such that $\left\langle{f},{K_{x}}\right\rangle=f(x)\neq 0$, i.e. $K_{x}\not\in\left\{f\right\}^{\perp}$, and $\left\langle{f},{K_{y}}\right\rangle=f(y)=0$ for all $y\in C$, i.e. $f\in\ker{P_{C}}=\operatorname{ran}\,P_{C}^{\perp}$. It follows that $\operatorname{ran}\,P_{C}\subset\left\{f\right\}^{\perp}$, and then $K_{x}\notin\operatorname{ran}\,P_{C}$. We prove ii) $\Rightarrow$ iii). If $x\in C$, then $K_{x}\in\operatorname{ran}\,P_{C}$ by definition of $P_{C}$, so that $F_{C}(x)=K(x,x)$. Hence $C\subset\left\{x\in X\mid F_{C}(x)=K(x,x)\right\}$. If $x\not\in C$, then by assumption $P_{C}K_{x}\neq K_{x}$, i.e. $(I-P_{C})K_{x}\neq 0$. By the equality

this implies $F_{C}(x)\neq K(x,x)$. Hence $C\supset\left\{x\in X\mid F_{C}(x)=K(x,x)\right\}$. We prove iii) $\Rightarrow$ i). If $x\not\in C$, define $f=(I-P_{C})K_{x}\in\ker{P_{C}}$, so that $f(y)=0$ for all $y\in C$. Furthermore, $f(x)=K(x,x)-F_{C}(x)\neq 0$. Thus, $f$ separates the set $C$. Finally, iv) is a restatement of ii) taking into account that $K_{x}\in\operatorname{ran}\,P_{C}$ for all $x\in C$ by construction. Under Assumption $\ref{A}.\ref{A3})$, the map $x\mapsto F_{C}(x)-K(x,x)=\left\langle{P_{C}K_{x}},{K_{x}}\right\rangle-K(x,x)$ is continuous by Proposition 1. By item iii), $C$ is the -level set of this function, hence $C$ is closed. ∎

Proposition 13 in A.1 shows that the reproducing kernel $K$ can be normalized under the mild assumption that $K(x,x)\neq 0$ for all $x\in X$, so that Assumption 1.d) can be satisfied up to a rescaling of $K$.

It may be the case that the set $X$ has its own metric $d_{X}$, and the $\sigma$-algebra $\mathcal{A}_{X}$ is the Borel $\sigma$-algebra associated with the topology induced by $d_{X}$. The following proposition shows that the metrics $d_{K}$ and $d_{X}$ induce the same topology on $X$, provided that $\mathcal{H}$ separates all the $d_{X}$-closed subsets and the corresponding kernel is continuous.

Let $X$ be a separable metric space with respect to a metric $d_{X}$, and $\mathcal{A}_{X}$ the corresponding Borel $\sigma$-algebra. Let $\mathcal{H}$ be a reproducing kernel Hilbert space on $X$ with kernel $K$. Assume that the kernel $K$ is a continuous function with respect to $d_{X}$ and that the space $\mathcal{H}$ separates every subset of $X$ which is closed with respect to $d_{X}$. Then

Assumptions $\ref{A}.\ref{A3})$, $\ref{A}.\ref{A1})$ and $\ref{A}.\ref{A2})$ hold true, and $K(x,x)>0$ for all $x\in X$;

a set is closed with respect to $d_{K}$ if and only if it is closed with respect to $d_{X}$.

The kernel is measurable and the space $\mathcal{H}$ is separable by Proposition $5.1$ and Corollary $5.2$ in . Since the points are closed sets for $d_{X}$ and the $d_{X}$-closed sets are separated by $\mathcal{H}$, then $K_{x}\neq 0$ (i.e. $K(x,x)>0$) for all $x\in X$ and $K_{x}\neq K_{y}$ if $x\neq y$ by the discussion following Definition 1. We show that $d_{X}$ and $d_{K}$ are equivalent metrics. Take a sequence $(x_{j})_{j\geq 1}$ such that for some $x\in X$ it holds that $\lim_{j\to\infty}d_{X}(x_{j},x)=0$. Since $K$ is continuous with respect to $d_{X}$, we have $\lim_{j\to\infty}d_{K}(x_{j},x)=0$. Hence, the $d_{K}$-closed sets are $d_{X}$-closed, too. Conversely, if the set $C$ is $d_{X}$-closed, since $\mathcal{H}$ separates $C$, Theorem 1 implies that $C=\left\{x\in X\mid K(x,x)-F_{C}(x)=0\right\}$, which is a $d_{K}$-closed set by $d_{K}$-continuity of the map $x\mapsto K(x,x)-F_{C}(x)$. ∎

Item ii) of the above proposition states that the metrics $d_{K}$ and $d_{X}$ are equivalent and implies that the set $X_{\rho}$ defined in Proposition 2 coincides with the support of $\rho$ with respect to the topology induced by $d_{X}$.

3 The Integral Operator Defined by the Kernel

We denote by $\mathcal{S}_{1}$ the Banach space of the trace class operators on $\mathcal{H}$, with trace class norm

where $\left\{e_{i}\right\}_{i\in I}$ is any orthonormal basis of $\mathcal{H}$. Furthermore, we let $\mathcal{S}_{2}$ be the separable Hilbert space of the Hilbert-Schmidt operators on $\mathcal{H}$, with Hilbert-Schmidt norm

Finally, if $A$ is any bounded operator on $\mathcal{H}$, we denote by $\left\lVert{A}\right\rVert_{\infty}$ its uniform operator norm. It is standard that $\left\lVert{A}\right\rVert_{\infty}\leq\left\lVert{A}\right\rVert_{\mathcal{S}_{2}}\leq\left\lVert{A}\right\rVert_{\mathcal{S}_{1}}$. Moreover, for all functions $f_{1},f_{2}\in\mathcal{H}$, the rank-one operator $f_{1}\otimes f_{2}$ on $\mathcal{H}$ defined by

is trace class, and $\left\lVert{f_{1}\otimes f_{2}}\right\rVert_{\mathcal{S}_{1}}=\left\lVert{f_{1}\otimes f_{2}}\right\rVert_{\mathcal{S}_{2}}=\left\lVert{f_{1}}\right\rVert\left\lVert{f_{2}}\right\rVert$.

We recall a few facts on integral operators with kernel $K$ (see for proofs and further discussions). Under Assumption 1, the $\mathcal{S}_{1}$-valued map $x\mapsto K_{x}\otimes K_{x}$ is Bochner-integrable with respect to $\rho$, and its integral

defines a positive trace class operator $T$ with $\left\lVert{T}\right\rVert_{\mathcal{S}_{1}}=\operatorname{tr}\left[T\right]=1$ (a short proof is given in Proposition 14 of the Appendix). Using the reproducing property of $\mathcal{H}$, it is straightforward to see that $T$ is simply the integral operator with kernel $K$ acting on $\mathcal{H}$, i.e.

The following is a key result in our approach.

Under Assumption 1, the null space of $T$ is

where $X_{\rho}$ is the support of $\rho$ as defined in Proposition 2.

Note that , for all $f\in\mathcal{H}$, the set

is closed since $f$ is continuous. We now prove Equation (5). Since $T$ is a positive operator, spectral theorem gives that $Tf=0$ if and only if $\left\langle{Tf},{f}\right\rangle=0$. The definition of $T$ and the reproducing property gives that

hence the condition $\left\langle{Tf},{f}\right\rangle=0$ is equivalent to the fact that $f(x)=0$ for $\rho$-almost every $x\in X$. Hence $f\in\ker{T}$ if and only if $\rho(C_{f})=1$, i.e. $C_{f}\supset X_{\rho}$, or equivalently $\left\langle{f},{K_{x}}\right\rangle=0$ $\forall x\in X_{\rho}$. Equation (5) then follows. ∎

In the following, we will use the abbreviated notation $P_{\rho}=P_{X_{\rho}}$. Note that the space $\mathcal{H}$ splits into the direct sum $\mathcal{H}=\mathcal{H}_{\rho}\oplus\mathcal{H}_{\rho}^{\perp}$, where

The reproducing kernel Hilbert space $\mathcal{H}_{\rho}$ (see Remark 2) has been considered before , and in particular in the context of semi-supervised manifold regularization , where $X_{\rho}$ is assumed to be an embedded manifold. The corresponding reproducing kernel is $K_{\rho}(x,y)=\left\langle{P_{\rho}K_{y}},{K_{x}}\right\rangle$ and $F_{X_{\rho}}(x)=K_{\rho}(x,x)$. See also the discussion in Section 6.

Under Assumption 1, we also introduce the integral operator $L_{K}:L^{2}(X,\rho)\to L^{2}(X,\rho)$,

which is a positive trace class operator, too. Note the difference between the operators $T$ and $L_{K}$: although their definitions are formally the same, the respective domains and images change.

Since $T$ and $L_{K}$ are positive trace class operators, by the Hilbert-Schmidt theorem each of them admits an orthonormal family of eigenvectors in $\mathcal{H}$ and $L^{2}(X,\rho)$, respectively, with a corresponding family of positive eigenvalues. The two spectral decompositions are strongly related, as we now briefly recall (see also Proposition 8 of and Theorem 2.11 of ).

Denote by $(\sigma_{j})_{j\in J}$ the (finite or countable) family of strictly positive eigenvalues of $L_{K}$, where each eigenvalue is repeated according to its (finite) multiplicity. For each $j\in J$ select a corresponding eigenvector $\phi_{j}\in L^{2}(X,\rho)$ in such a way that the sequence $(\phi_{j})_{j\in J}$ is orthonormal in $L^{2}(X,\rho)$. Hilbert-Schmidt theorem provides that

where the series converges in trace norm. In general, each element $\phi_{j}$ is an equivalence class of functions defined $\rho$-almost everywhere. In particular, the value of $\phi_{j}$ is not defined outside $X_{\rho}$. However, in each equivalence class we can choose a unique continuous function, denoted again by $\phi_{j}$, which is defined at every point of $X$ by means of the extension equation

With this choice, which will be implicitly assumed in the following, the family $(\sigma_{j})_{j\in J}$ coincides with the family of strictly positive eigenvalues of $T$ (with the same multiplicities), $(\sqrt{\sigma_{j}}\phi_{j})_{j\in J}$ is a orthonormal family in $\mathcal{H}$ of eigenfunctions of $T$, and

where the series converges in the Banach space $\mathcal{S}_{1}$ (hence in $\mathcal{S}_{2}$), see e.g. . As $\left\lVert{T}\right\rVert_{\mathcal{S}_{1}}=1$, the positive sequence $(\sigma_{j})_{j\in J}$ is summable and sums up to $1$. It is clear that the family $(\sqrt{\sigma_{j}}\phi_{j})_{j\in J}$ is an orthonormal basis of the Hilbert space $\mathcal{H}_{\rho}$. Conversely, let $(f_{j})_{j\in J}$ be an orthonormal basis of $\mathcal{H}_{\rho}$ of eigenvectors of $T$ with corresponding eigenvalues $(\sigma_{j})_{j\in J}$. Define

Then, it is not difficult to show that (6), (7) and (8) hold true.

4 An Analytic Characterization of the Support

Let Assumption 1 hold true. Collecting the previous results, if $\mathcal{H}$ separates $X_{\rho}$, then Theorem 1 gives that

The function $F_{\rho}=F_{X_{\rho}}$ is defined by (3) in terms of the projection $P_{\rho}$, which, in light of Theorem 2, can be characterized using the operator $T$. Indeed, from the definition of $F_{\rho}$ and (5) we have

where $T^{\dagger}$ is the pseudo-inverse of $T$ and $\theta$ is the Heaviside function $\theta(\sigma)=1{\hskip-2.5pt}\hbox{I}_{]0,+\infty[}(\sigma)$ (note that with our definition $\theta(0)=0)$. The above discussion is summarized in the following theorem.

If $\mathcal{H}$ satisfies Assumption 1 and separates the support $X_{\rho}$ of the measure $\rho$, then

As we discussed before, a natural question is whether there exist kernels capable to separate all possible closed subsets of $X$. In a learning scenario, this can be translated into a universality property, in the sense that it allows to describe any probability distribution and learn consistently its support . Note that in a supervised learning framework a similar role is played by the so called universal kernels . The following section answers positively to the previous question, introducing and studying the concept of completely separating kernels. Interestingly, there are universal kernels in the sense of which do not separate all closed subsets of $X$, as for example the Gaussian kernel.

Completely separating reproducing kernel Hilbert spaces

The property defining the class of kernels we are interested in is captured by the following definition.

A reproducing kernel Hilbert space $\mathcal{H}$ satisfying Assumption $\ref{A}.\ref{A3})$ is called completely separating if $\mathcal{H}$ separates all the subsets $C\subset X$ which are closed with respect to the metric $d_{K}$ defined by (1). In this case, we also say that the corresponding reproducing kernel is completely separating.

We end this section with Proposition 6, which gives a simple way to build completely separating kernels in high dimensional spaces from completely separating kernels in one dimension, the latter usually being easier to characterize.

We now state a sufficient condition on $K$ ensuring that $\mathcal{H}$ is completely separating.

for some $a,b,\gamma_{1},\gamma_{2}>0$. Then,

the translation invariant kernel $K(x,y)=K(x-y)$ is positive definite and continuous;

As an application, we show that the Abel kernel is completely separating.

with $\sigma>0$. Then $K$ is a positive definite kernel and the corresponding reproducing kernel Hilbert space $\mathcal{H}$ is completely separating for all $d\geq 1$.

A standard Fourier transform computation gives

where $\Gamma$ is Euler gamma function (Theorem 1.14 in ). The claim then follows from Theorem 4. ∎

2 Building Separating Kernels

The following result gives a way to construct completely separating reproducing kernel Hilbert spaces on high dimensional spaces.

If $X_{i}$, $i=1,2\ldots d$, are sets and $K^{(i)}$ are completely separating reproducing kernels on $X_{i}$ for all $i=1,2\ldots d$, then the product kernel

is completely separating on the set $X=X_{1}\times X_{2}\times\ldots\times X_{d}$.

Each set $X_{i}$ and $X$ are endowed with the metric $d_{K^{(i)}}$ and $d_{K}$ induced by the corresponding kernels, and $\mathcal{H}_{i}$ and $\mathcal{H}$ denote the reproducing kernel Hilbert spaces with kernels $K^{(i)}$ and $K$, respectively. A standard result gives that $\mathcal{H}=\mathcal{H}_{1}\otimes\ldots\otimes\mathcal{H}_{d}$ and $K_{x}=K^{(1)}_{x_{1}}\otimes\ldots\otimes K^{(d)}_{x_{d}}$ for all $x=(x_{1},\ldots,x_{d})\in X$ . We claim that the $d_{K}$-topology on $X$ is contained in the product topology of the $d_{K^{(i)}}$-topologies on $X_{i}$ (actually, it is not difficult to show that the two topologies coincide). Indeed, if $(x_{i,k})_{k\geq 1}$ are sequences in $X_{i}$ such that $\lim_{k\to\infty}d_{K^{(i)}}(x_{i,k},x_{i})=0$ for all $i=1,\ldots,d$, then

since $\lim_{k\to\infty}K^{(i)}(x_{i,k},x_{i,k})=\lim_{k\to\infty}K^{(i)}(x_{i,k},x_{i})=K^{(i)}(x_{i},x_{i})$. We now prove that $\mathcal{H}$ is completely separating. If $C\subset X$ is $d_{K}$-closed and $x=(x_{1},\ldots,x_{d})\in X\setminus C$, since $C$ is also closed in the product topology, for all $i=1,\ldots,d$ there exists an open neighborhood $U_{i}$ of $x_{i}$ in $X_{i}$ such that $U=U_{1}\times\ldots\times U_{d}\subset X\setminus C$. Since each $\mathcal{H}_{i}$ is completely separating, for all $i=1,\ldots,d$ there exists $f_{i}\in\mathcal{H}_{i}$ such that $f_{i}(x_{i})\neq 0$ and $f_{i}(y_{i})=0$ for all $y_{i}\in X_{i}\setminus U_{i}$. Then the product function $f=f_{1}\otimes\ldots\otimes f_{d}$ is in $\mathcal{H}$, and satisfies $f(x)\neq 0$ and $f(y)=0$ for all $y\in C$. ∎

is completely separating since each kernel in the product is positive definite and completely separating by Proposition 5.

A Spectral Approach to Learning the Support

In this section we study the set estimation problem in the context of learning theory. We fix a triple $(X,\rho,K)$ as in Section 2, and assume throughout that the reproducing kernel $K$ satisfies Assumption 1. We regard $X$ as a metric space with respect to $d_{K}$, and continue to denote by $X_{\rho}$ the support of $\rho$ defined in Proposition 2.

If $\mathcal{H}$ separates $X_{\rho}$, Theorem 3 shows that the support $X_{\rho}$ is the $1$-level set of a suitable function $F_{\rho}$ defined by the integral operator $T$, and therefore depending on $K$ and $\rho$. However, the probability distribution $\rho$ is unknown, as we only have a set of i.i.d. points $x_{1},\dots,x_{n}$ sampled from $\rho$ at our disposal. Our task is now to use our sample in order to estimate the set $X_{\rho}$.

The definition of $T$ given by (4) suggests that it can be estimated by the data dependent operator

The operator $T_{n}$ is positive and with finite rank; in particular, $T_{n}\in\mathcal{S}_{1}$ and $\left\lVert{T_{n}}\right\rVert_{\mathcal{S}_{1}}=\operatorname{tr}\left[T_{n}\right]=1$. We denote by $(\sigma^{(n)}_{j})_{j\in J_{n}}$ the strictly positive eigenvalues of $T_{n}$ (each one repeated according to its multiplicity) and by \big{(}\sqrt{\sigma^{(n)}_{j}}\phi^{(n)}_{j}\big{)}_{j\in J_{n}} the corresponding eigenvectors; note that in the present case the index set $J_{n}$ is finite. However, though $T_{n}$ converges to $T$ in all relevant topologies (see Lemma 1 and Remark 6 below), in general $T^{\dagger}_{n}T_{n}$ does not converge to $T^{\dagger}T$ since $T^{\dagger}$ may be unbounded, or, equivalently, since may be an accumulation point of the spectrum of $T$ when $\dim\mathcal{H}=\infty$. Hence, the problem of support estimation is ill-posed, and regularization techniques are needed to restore well-posedness and ensure a stable solution. In the following sections, we will show that spectral regularization can be used to learn the support efficiently from the data.

Note that, since the spectra of $T_{n}$ and $T$ are both contained in the interval $$, we can assume that the functions$g_{\lambda}$and$r_{\lambda}$are defined on$$. Moreover, as the operators$r_{\lambda}(T_{n})$and$r_{\lambda}(T)$approximate orthogonal projections, it is useful to have the bound$0\leq r_{\lambda}(T_{n}),r_{\lambda}(T)\leq{I}$satisfied for all$T_{n}$and$T$’s, and this can be achieved by choosing the function$r_{\lambda}$such that$0\leq r_{\lambda}(\sigma)\leq 1$for all$\sigma$.

As a consequence of the above discussion, the characterization of filter functions giving rise to stable algorithms is captured by the following assumption.

The family of functions $(r_{\lambda})_{\lambda>0}$, with $r_{\lambda}:\to$ for all $\lambda>0$, has the following properties:

for all $\sigma>0$, we have $\lim_{\lambda\to 0^{+}}r_{\lambda}(\sigma)=1$;

for all $\lambda>0$, there exists a positive constant $L_{\lambda}$ such that

By Assumption 2.a, there exists a function $g_{\lambda}:\to[0,+\infty[$ such that $r_{\lambda}(\sigma)=g_{\lambda}(\sigma)\sigma$. On the other hand, by Assumption 2.b) we have $\lim_{\lambda\to 0^{+}}r_{\lambda}(\sigma)=\theta(\sigma)$ for all $\sigma\in$. Assumption 2.c) is of technical nature, and will become clear in Section 5.2; here we note that in particular it implies that $r_{\lambda}$ is a continuous function for all $\lambda>0$.

A few examples of filter functions $r_{\lambda}$ satisfying Assumption 2 and of corresponding functions $g_{\lambda}$ are given in Table 1. It is easy to check that for each of them $L_{\lambda}=1/\lambda$. See for further examples.

For a chosen filter, the corresponding regularized empirical estimator of $F_{\rho}$ is defined by

where we allow the regularization parameter $\lambda_{n}$ to depend on the number of samples $n$. Note that the functions $F_{n}$ and $F_{\rho}$ are continuous on $X$ by continuity of the mapping $x\mapsto K_{x}$ (see i) of Proposition 1). In Section 5 we will show that, for an appropriate choice of the sequence $(\lambda_{n})_{n\geq 1}$, the estimator $F_{n}$ converges almost surely to $F_{\rho}$ uniformly on compact subsets of $X$. Unfortunately, this does not imply convergence of the $1$-level sets of $F_{n}$ to the $1$-level set of $F_{\rho}$ in any sense (as, for example, with respect to the Hausdorff distance). However, an estimator of $X_{\rho}$ can be obtained by setting

where $\tau_{n}>0$ is an off-set parameter that depends on the sample size $n$ (recall that $F_{n}$ takes values in $$). In Section 5 we show that, for a suitable choice of the sequence$(\tau_{n})_{n\geq 1}$, the closed set$X_{n}$ is indeed a consistent estimator of the support with respect to the Hausdorff distance.

In the following section we discuss some remarks about the computation of $F_{n}$.

2 Algorithmic and Computational Aspects

We show that the computation of $F_{n}$ (hence of $X_{n}$) reduces to a finite dimensional problem involving the empirical kernel matrix defined by the data. To this purpose, it is useful to introduce the sampling operator

which can be interpreted as the restriction operator which evaluates functions in $\mathcal{H}$ on the points of the training set. The transpose of $S_{n}$ is

and $S_{n}^{\top}$ can be interpreted as the out-of-sample extension operator . A simple computation shows that

Hence, considering the filter given in the form $r_{\lambda}(T_{n})=g_{\lambda}(T_{n})T_{n}$, we have

where the second equality follows from spectral calculus. Using the definition of the sampling operator, we can consider the $n$-dimensional vector ${\mathbf{K}}_{x}$ defined by

where ${\mathbf{K}}_{x}^{\ast}$ is the conjugate transpose of ${\mathbf{K}}_{x}$. More explicitly we have

The above equation shows that, while $\mathcal{H}$ could be infinite dimensional, the computation of the estimator reduces to a finite dimensional problem. Further, though the mathematical definition of the filter is done through spectral calculus, the computations might not require performing an eigen-decomposition. As an example, for Tikhonov regularization $g_{\lambda_{n}}(\sigma)=\frac{1}{\sigma+\lambda_{n}}$, so that $g_{\lambda_{n}}\left(\frac{\mathbf{K}_{n}}{n}\right)=(\frac{{\mathbf{K}}_{n}}{n}+\lambda_{n})^{-1}$ and the coefficient vector $\alpha(x)$ in (20) is given by

In the case of the Landweber filter, it is possible to prove that the coefficient vector can be evaluated iteratively by setting $\alpha^{0}(x)=0$, and

for $t=1,\dots,m_{\lambda_{n}}$. We refer to for the corresponding algorithm in a supervised framework; see also the discussion in Section 6.3.

We thus see that the estimator corresponding to Tikhonov regularization can be computed via Cholesky decomposition and has complexity of order $O(n^{3})$. For Landweber iteration the complexity is $O(n^{2}m)$, where $m$ is the number of iterations. Finally, the spectral cut-off, or truncated SVD, requires $O(n^{3})$ operations to compute the eigen-decompostion of the kernel matrix. Further discussions can be found in and references therein. We end remarking that, in order to test whether $N$ points belong or not to the support, we simply have to repeat the above computation replacing ${\mathbf{K}}_{x}$ by a $n\times N$ matrix ${\mathbf{K}}_{x,N}$, in which each column is a vector ${\mathbf{K}}_{x}$ corresponding to a point $x$ in the test set. Note that in this case the coefficients $\alpha(x)$ will also form a $n\times N$ matrix.

Error Analysis: Convergence and Stability

In this section we develop an errror analysis for the proposed class of estimators. First, we discuss convergence (consistency) and then stability with respect to random sampling in terms of finite sample bounds. We continue to suppose throughout this section that Assumption 1 holds true, and consider $X$ as a metric space with metric $d_{K}$.

We recall that the empirical data are a set of i.i.d. points $x_{1},\dots,x_{n}$, each one drawn from $X$ with probability $\rho$. Since we need to study asymptotic properties when the sample size $n$ goes to infinity, we introduce the following probability space

for some measurable map $\xi_{n}:X^{n}\to M$. The number $n$ is the cardinality of the sampled data. We then have the following facts.

$T_{n}$ is a $\mathcal{S}_{k}$-valued estimator for $k=1,2$;

if $X$ is locally compact, then $F_{n}$ is a $C(X)$-valued estimator, where $C(X)$ is the space of continuous functions on $X$ with the topology of uniform convergence on compact subsets.

The proof of the above proposition is rather technical, and we defer the interested reader to A.2 for more details.

In item ii) of Proposition 7, the assumption that $X$ is locally compact is needed to ensure that the topology of uniform convergence on compact subsets is a separable metric topology on $C(X)$, which in turn is essential to prove measurability of the random variable $F_{n}$ (see the proof of Proposition 16 in A.2). In many examples, the set $X$ has its own locally compact separable metric $d_{X}$. In this case, in order for $X$ to be locally compact metric space also for the metric $d_{K}$, it is enough that the kernel $K$ is a $d_{X}$-continuous function separating every subset of $X$ which is closed with respect to $d_{X}$, as the two topologies induced by $d_{X}$ and $d_{K}$ then coincide by item ii) of Proposition 3.

Concentration of measure results for random variables in Hilbert spaces can be used to prove that $T_{n}$ is an unbiased estimator of $T$, as stated in the following lemma.

with probability at least $1-2e^{-\delta}$. Furthermore

The result is known, but we report its short proof. For all $i\geq 1$ define the random variables $Z_{i}:\Omega\to\mathcal{S}_{2}$ as

Note that (23) and Theorem 2.19 in imply that

2 Consistency

We now choose a family of filter functions $(r_{\lambda})_{\lambda>0}$ and study the convergence of the associated estimators $F_{n}$ and $X_{n}$ introduced in Section 4.

which can be seen as the infinite sample analogue of $F_{n}$. Clearly, $G_{\lambda}$ is a continuous function. For all sets $C\subset X$, we then have the following splitting of the error into two parts, the sample error and the approximation error

In order to prove consistency, we need to show that the left hand side goes to as the sequence of regularization parameters $(\lambda_{n})_{n\geq 1}$ tends to . This will be done separately for the approximation and the sample errors in the next two propositions.

Under Assumption 2.b), if the sequence $(\lambda_{n})_{n\geq 1}$ is such that $\lim_{n\to\infty}\lambda_{n}=0$, then, for any compact subset $C\subset X$,

Assumption 2.b) and $\lim_{n\to\infty}\lambda_{n}=0$ imply that the sequence of non-negative functions $(r_{\lambda_{n}})_{n\geq 1}$ is bounded by $1$ and converges pointwisely to the Heaviside function $\theta$ on the interval $$. Spectral theorem ensures that, for all$x\in C$,