The Area of the Convex Hull of Sampled Curves:
a Robust Functional Statistical Depth Measure

Guillaume Staerman Pavlo Mozharovskyi Stephan Clémençon

LTCI, Télécom Paris, Institut Polytechnique de Paris

###### Abstract

With the ubiquity of sensors in the IoT era, statistical observations are
becoming increasingly available in the form of massive (multivariate) time-
series. Formulated as unsupervised anomaly detection tasks, an abundance of
applications like aviation safety management, the health monitoring of complex
infrastructures or fraud detection can now rely on such functional data,
acquired and stored with an ever finer granularity. The concept of statistical
depth, which reflects centrality of an arbitrary observation w.r.t. a
statistical population may play a crucial role in this regard, anomalies
corresponding to observations with ’small’ depth. Supported by sound
theoretical and computational developments in the recent decades, it has
proven to be extremely useful, in particular in functional spaces. However,
most approaches documented in the literature consist in evaluating
independently the centrality of each point forming the time series and
consequently exhibit a certain insensitivity to possible shape changes. In
this paper, we propose a novel notion of functional depth based on the area of
the convex hull of sampled curves, capturing gradual departures from
centrality, even beyond the envelope of the data, in a natural fashion. We
discuss practical relevance of commonly imposed axioms on functional depths
and investigate which of them are satisfied by the notion of depth we promote
here. Estimation and computational issues are also addressed and various
numerical experiments provide empirical evidence of the relevance of the
approach proposed.

##  1 Introduction

Technological advances in data acquisition, management and warehousing (e.g.
IoT, distributed platforms) enable massive data processing and are leading to
a wide variety of new applications in the digitalized (service) industry. The
need to design more and more automated systems fed by ever more informative
streams of data manifests in many areas of human activity (e.g transportation,
energy, health, commerce, finance/insurance). Monitoring the behavior/health
of complex systems offers a broad spectrum of machine-learning implementation
as classification or anomaly detection. With the increasing industrial
digitalization, data are more and more often collected in quasi-real time and
naturally take the form of temporal series or functions. The case of
functional data is thus of crucial interest in practice, refer to e.g. Ramsay
and Silverman, (2002, 2005) for an excellent account of Functional Data
Analysis (FDA in abbreviated form) and of its applications. A functional
dataset is typically a set of $n\geq 1$ curves partially observed at different
time points $T_{1}=t_{1}<\ldots<t_{p}=T_{2}$ which can be seen as $n$
(partially observed) realizations of a stochastic process
$X=(X_{t})_{t\in[T_{1},T_{2}]}$. Hence, the first step of FDA generally
consists in reconstruct the functional objects from these observations, by
means of interpolation, smoothing or projection techniques. Whereas, with the
design of many successful algorithms such as (deep) neural networks, SVM’s or
boosting procedures, the practice of statistical learning has rapidly
generalized these last few years, the automatic analysis of functional data to
achieve complex (e.g. unsupervised) tasks such as anomaly detection is still a
challenge, due to the huge variety of possible patterns that may carry the
relevant information for discrimination purposes. It is far from
straightforward to generalize directly methods originally introduced in the
finite-dimensional case to the functional setup, unless preliminary filtering
or dimensionality reduction techniques are used, see e.g Rossi and Villa,
(2006); Staerman et al., (2019). Such techniques essentially consist in
projecting the observation, supposed to take their values in a certain Hilbert
space, onto a subspace of finite dimensionality, generally defined by
truncating their expansion in a Hilbertian basis of reference or by means of a
flexible dictionary of functions/’atoms’. Next, one can apply any state-of-
the-art algorithm tailored to the finite dimension case, based on the
parsimonious representations thus obtained, cf Ferraty and Vieu, (2006);
Ramsay and Silverman, (2002). The basis functions can be either chosen among a
pre-selected dictionary (e.g. Fourier, wavelets, cosine packets, etc.)
presumably capable of capturing the information carried by the curves or built
empirically using Functional Principal Component Analysis, retaining the most
informative part of the (Kahrunen-Loève) decomposition only, see Ramsay and
Silverman, (2005). Of course, the major drawback of such FDA approaches lies
in the fact that they are dramatically conditioned by the finite-dimensional
representation method chosen, the subsequent analysis of the data may be fully
jeopardized if the latter makes disappear some patterns relevant for the task
considered.

Originally introduced by J. Tukey to extend the notion of median/quantile to
multivariate random variables (see Tukey, 1975a ), a data depth is a function
defined on the feature space and valued in $[0,1]$ used to determine the
’representativeness’ of a point with respect to a statistical population and
that should fulfill a variety of desirable properties (ideally just like the
quantile function in the univariate situation). Given a training set, a data
depth function provides a score that measures the centrality of any element
w.r.t. a dataset and then defines, notably, an ordering of all the elements of
the dataset. In particular, it finds a very natural application in
(unsupervised) anomaly detection, see e.g Cuevas et al., (2007); Long and
Huang, (2016); Mosler and Mozharovskyi, (2017) in supervised situations and
Hubert et al., (2015); Nagy et al., (2017) in the unsupervised context: an
observation is considered all the more ’abnormal’, as its depth is small. This
concept has been extended to the functional data framework by integrating
univariate depth functions on the whole interval of time $[T_{1},T_{2}]$, see
e.g. Claeskens et al., (2014); Fraiman and Muniz, (2001); Hubert et al.,
(2015). Alternatively, various depth functions fully tailored to the
functional setup have been introduced in the statistical literature, refer to
e.g Chakraborty and Chaudhuri, (2014); Dutta et al., (2011); Lopez-Pintado and
Romo, (2009, 2011). However, most of them fail to fulfill certain desirable
properties or face significant computational difficulties. It is the major
purpose of this paper to introduce a novel robust functional statistical depth
measure dedicated to the analysis of functional data. Based on the area of the
convex hull of collections of sampled curves, it is easy to compute and to
interpret both at the same time. Given a curve $x$ lying in a certain
functional space $\mathcal{F}$ (e.g. the Kolmogorov space
$\mathcal{C}([0,1])$, the space of real valued continuous functions on
$[0,1]$), the general idea is to quantify its contribution, on average, to the
area of the convex hull (ACH in short) of random curves in $\mathcal{F}$ with
the same probability law. Precisely, this function, referred to as the ACH
depth throughout the article, is defined by the ratio of the ACH of the sample
to that of the sample augmented by the curve $x$. We prove here that it
fulfills various properties desirable for depth functions. In particular,
given its form, it exhibits sensitivity (i.e. the depth score of new/test
curves that are further and further away from the training set of curves
decreases smoothly), which property, quite desirable intuitively, is actually
not satisfied by most statistical (functional) depth documented in the
literature. For instance, the statistical Tukey depth assigns a score of $0$
to any element lying outside the convex hull of the training data, see Tukey,
1975b ; Dutta et al., (2011). In addition, the statistical depth we promote
here is robust to outliers: adding outliers to the training set of curves has
little or no effect on the returned score and ordering on a test set. For this
reason, this functional depth is very well suited for unsupervised anomaly
detection. In the functional setup, this task is extremely challenging.
Indeed, the richness of functional spaces leads to a huge diversity in the
nature of possibly observed differences between curves. As dicussed in Hubert
et al., (2015), three main types of anomaly can be distinguished: shift,
magnitude or shape anomalies. Anomalies can be either isolated/transient or
persistent depending of their duration ; some of them being more difficult to
detect (shape anomalies). Since the functional statistical depth measure we
propose is related to a whole batch of curves and do not reflect the
individual properties of a single curve, it enables the detection of a wide
variety of anomaly shapes, as illustrated by the numerical experiments
displayed in Section 4.

The paper is organized as follows. In Section 2, basic concepts pertaining to
the statistical depth theory, both for the multivariate framework and for the
functional case, are briefly recalled for clarity’s sake. In Section 3 the
functional statistical depth based on the area of the convex hull of a batch
of curves is introduced at length and its theoretical properties are
investigated, together with computational aspects. Section 4 presents
numerical results in order to provide strong empirical evidence of the
relevance of the novel depth function proposed, for the purpose of
unsupervised functional anomaly detection especially. Eventually, concluding
remarks are collected in Section 5.

##  2 Background and Preliminaries

For clarity, we start with recalling the concept of statistical depth in the
multivariate and functional framework. We next list the desirable properties
it should fulfill and also briefly review recent advances in this field. Here
and throughout, the Dirac mass at any point $a$ is denoted by $\delta_{a}$,
the convex hull of any subset $A$ of $\mathbb{R}^{d}$ by $conv(A)$.

###  2.1 Data Depth in a Multivariate Space

By data depth, one usually means a nonparametric statistical function that
determines the centrality of any element $x\in\mathbb{R}^{d}$ with respect to
a statistical population. Given a dataset, a depth function provides a center-
outward ordering of the data points. Since it permits to define a ranking of
the (multivariate) observations and local averages derived from it, a data
depth can be used for various tasks, including classification (Lange et al.,
(2014)), clustering (Jörnsten, (2004)), anomaly detection (Serfling, (2006))
or rank tests (Oja, (1983)). In order to give a precise definition, some
notations are needed. Let $X$ be a random variable, defined on a certain
probability space $(\Omega,\mathcal{A},\mathbb{P})$, taking its values in
$\mathcal{X}\subset\mathbb{R}^{d}$ with probability distribution $P$. Denote
by $\mathcal{P}(\mathcal{X})$ the set of all probability distributions on
$\mathcal{X}$. A data depth is a function

$D:$ | $\mathbb{R}^{d}\times\mathcal{P}(\mathcal{X})$ | $\longrightarrow$ | $[0,1]$
---|---|---|---
| $(x,\;P)$ | $\longmapsto$ | $D(x,\;P)$

measurable with respect to its first argument $x$. It is interpreted as
follows: the closer the quantity $D(x,P)$ to $1$, the deeper (i.e. the more
’central’) the observation $x$ with respect to the distribution $P$ is
considered. As mentioned above, it naturally defines a predorder on the set
$\mathcal{X}$. In particular, medians of the multivariate distribution $P$
corresponds to maximizers of the depth function $D$ and quantile regions are
defined as depth sublevel sets. A crucial example is the half-space depth
$D_{T}$ (also called location depth sometimes) introduced in the seminal
contribution Tukey, 1975b . It is defined as

$D_{T}(x,\;P)=\inf\\{P(H):\;H\text{ closed half-space, }x\in H\\},$

for any $x\in\mathbb{R}^{d}$ and probability distribution on $\mathbb{R}^{d}$.
As the distribution $P$ is generally unknown, a statistical version can be
built from independent copies $X_{1},\;\ldots,\;X_{n}$ of the generic random
vector $X$ by means of the plug-in principle, i.e. by replacing $P$ by an
empirical counterpart $\widehat{P}_{n}$, typically the raw empirical
distribution $(1/n)\sum_{i=1}^{n}\delta_{X_{i}}$ (or a smooth/penalized
version of the latter), yielding the empirical depth

$\widehat{D}_{n}(x)=D(x,\;\widehat{P}_{n}).$ (1)

Empirical medians and quantile regions are then naturally defined as medians
and quantile regions of the empirical depth (1). Of course, the relevance of a
depth function regarding the measurement of centrality in a multivariate space
is guaranteed in the sole case where certain desirable properties are
satisfied. We refer to Zuo and Serfling, (2000) for an account of the
statistical theory of multivariate data depth and many examples.

###  2.2 Statistical Functional Depth

In this paper, we consider the situation where the r.v. $X$ takes its values
in a space of infinite dimension. Precisely, focus is on the case where the
feature space is the vector space $\mathcal{C}([0,1])$ of real-valued
continuous functions on $[0,1]$:

$\begin{array}[]{ccccc}X&:&(\Omega,\;\mathcal{A},\;\mathbb{P})&\longrightarrow&\mathcal{C}([0,1])\\\
&&\omega&\longmapsto&X(\omega)=(X_{t}(\omega))_{t\in[0,1]}.\end{array}$

Recall that, when equipped with the $\sup$ norm $||.||_{\infty}$,
$\mathcal{C}([0,1])$ is a separable Banach space. We denote by
$\mathcal{P}(\mathcal{C}([0,1]))$ the set of all probability laws on
$\mathcal{C}([0,1])$ and by $P_{t}$ the $1$-dimensional marginal of the law
$P$ of the stochastic process $X$ at time point $t\in[0,1]$.

Depths in a functional framework have been first considered in Fraiman and
Muniz, (2001), where it is proposed to define functional depths as simple
integrals over time of a univariate depth function $D$, namely
$(x,P)\in\mathcal{C}([0,1])\mapsto\int_{0}^{1}D(x_{t},P_{t})dt$. Due to the
averaging effect, local changes for the curve $x$ only induce slight
modifications of the depth value, which makes anomaly detection approaches
based on such ‘poorly sensitive’ functional depths ill-suited in general.
Recently, alternative functional depths have been introduced, see Lopez-
Pintado and Romo, (2009, 2011) for depths based on the geometry of the set of
curves, Chakraborty and Chaudhuri, (2014) for a notion of depth based on the
$L_{2}$ distance or Dutta et al., (2011) for a functional version of the Tukey
depth. As discussed in Nieto-Reyes and Battey, (2016) and Gijbels and Nagy,
(2018), the axiomatic framework introduced in Zuo and Serfling, (2000) for
multivariate depth is no longer adapted to the richness of the topological
structure of functional spaces. Indeed, the vast majority of the functional
depths documented in the literature do not fulfill versions of the most
natural and elementary properties required for a depth function in a
multivariate setup, cf Gijbels and Nagy, (2018). However, there is still no
consensus about the set of desirable properties that a functional depth should
satisfy, beyond the form of sensitivity mentioned above. Those that appear to
be the most relevant in our opinion are listed below. By $P_{X}$ is meant the
law of a functional r.v. taking its values in $\mathcal{C}([0,1])$.

  * •

(Non-degeneracy) For all non atomic distribution $P$ in
$\mathcal{P}(\mathcal{C}([0,1]))$, we have

$\underset{x\in\mathcal{C}([0,1])}{\inf}D(x,P)<\underset{x\in\mathcal{C}([0,1])}{\sup}D(x,P).$

  * •

(Affine invariance) The depth $D$ is said to be (scalar) affine invariant if
for any $x$ in $\mathcal{C}([0,1])$ and all $a$, $b$ in $\mathbb{R}$, we have

$D(x,P_{X})=D(ax+b,P_{aX+b}).$

  * •

(Maximality at the center) For any point-symmetric and non atomic distribution
$P$ with $\theta\in\mathcal{C}([0,1])$ as center of symmetry, we have

$D(\theta,P)=\underset{x\in\mathcal{C}([0,1])}{\sup}D(x,P).$

  * •

(Vanishing at $\infty$) For any non atomic distribution $P$ in
$\mathcal{P}(\mathcal{C}([0,1]))$,

$D(z,P_{X})\underset{||z||_{\infty}\longrightarrow\infty}{\;\;\;\;\;\longrightarrow}\underset{x\in\mathcal{C}([0,1])}{\inf}D(x,P).$

  * •

(Decreasing w.r.t. the deepest point) For any $P$ in
$\mathcal{P}(\mathcal{C}([0,1]))$ such that
$D(z,P)=\underset{x\in\mathcal{C}([0,1])}{\sup}D(x,P)$, $D(x,P)<D(y,P)<D(z,P)$
holds for any $x,y\in\mathcal{C}([0,1])$ such that $\min\\{d(y,z),d(y,x)\\}>0$
and $\max\\{d(y,z),d(y,x)\\}<d(x,z)$.

  * •

(Continuity in $x$) For any non atomic distribution
$P\in\mathcal{P}(\mathcal{C}([0,1]))$, the function $x\mapsto D(x,P)$ is
continuous w.r.t. the $\sup$ norm.

  * •

((Uniform-) continuity in $P$) For all $x$ in $\mathcal{C}([0,1])$, the
mapping $P\in\mathcal{P}(\mathcal{C}([0,1]))\mapsto D(x,\;P)$ is (uniformly-)
continuous w.r.t. the Lévy-Prohorov metric.

Before introducing the ACH depth and investigating its properties, a few
remarks are in order. Though it obviously appears as mandatory to make the
other properties meaningful, non-degeneracy, is actually not fulfilled by all
the functional depths proposed, see e.g Lopez-Pintado and Romo, (2009, 2011);
Dutta et al., (2011). The ’Maximality at center’ and ’Decreasing w.r.t. the
deepest point’ properties permit to preserve the original center-outward
ordering goal of data depth in the functional framework. Many definition of
the concept of ”symmetry” in a functional space are detailed in the
Supplementary material for the sake of place. The ’Continuity in $x$’ property
extends a property fulfilled by cumulative distribution functions of
multivariate continuous distributions. From a statistical perspective, the
’Continuity in $P$’ property is essential, insofar as $P$ must be replaced in
practice by an estimator, cf Eq. (1), built from finite-dimensional
observations, i.e. a finite number of sampled curves.

##  3 The Area of the Convex Hull of (Sampled) Curves

It is the purpose of this section to present at length the statistical depth
function we propose for path-valued random variables. As shall be seen below,
its definition is based on very simple geometrical ideas and various desirable
properties can be easily checked from it. Statistical and computational issues
are also discussed at length. By $\mathcal{K}_{2}$ is meant the collection of
all compact subsets of $\mathbb{R}^{2}$ and $\lambda$ denotes Lebesgue measure
on the plane $\mathbb{R}^{2}$. Consider an i.i.d. sample
$X_{1},\;\ldots,\;X_{n}$ drawn from $P$ in $\mathcal{P}(\mathcal{C}([0,1]))$.
The graph of any function $x$ in $\mathcal{C}([0,1])$ is denoted by

$graph(x)=\\{(t,y):y=x(t),t\in[0,1]\\},$

while we denote by $graph(\\{x_{1},\ldots,x_{n}\\})$ the set

$\bigcup_{i=1}^{n}graph(\\{x_{i}\\})$

defined by a collection of $n\geq 1$ functions $\\{x_{1},\ldots,x_{n}\\}$ in
$\mathcal{C}([0,1])$. We now give a precise definition of the statistical
depth measure we propose for random variables valued in $\mathcal{C}([0,1])$.

###### Definition 3.1

Let $J\geq 1$ be a fixed integer. The ACH depth of degree $J$ is the function
$D_{J}:\mathcal{C}([0,1])\times\mathcal{P}(\mathcal{C}([0,1]))\rightarrow[0,1]$
defined by: $\forall x\in\mathcal{C}([0,1])$,

$D_{J}(x,\;P)=\mathbb{E}\left[\frac{\lambda\left(conv\left(graph\left(\\{X_{1},\ldots,X_{J}\\}\right)\right)\right)}{\lambda\left(conv\left(graph\left(\\{X_{1},\ldots,X_{J}\\}\cup\\{x\\}\right)\right)\right)}\right],$

where $X_{1},\;\ldots,\;X_{J}$ are i.i.d. r.v.’s drawn from $P$. Its average
version $\bar{D}_{J}$ is defined by: $\forall x\in\mathcal{C}([0,1])$,

$\bar{D}_{J}(x,\;P)=\frac{1}{J}\sum_{j=1}^{J}D_{j}(x,\;P).$

The choice of $J$ leads to various views of distribution $P$, the average
variant permitting to combine all of them (up to degree $J$). When $n\geq J$,
an unbiased statistical estimation of $D_{J}(.,\;P)$ can be obtained by
computing the symmetric $U$-statistic of degree $J$, see Lee, (1990): $\forall
x\in\mathcal{C}([0,1])$,

$D_{J,n}(x)=\\\ \frac{1}{\binom{n}{J}}\sum_{1\leq i_{1}<\ldots<i_{J}\leq
n}\frac{\lambda\left(conv\left(graph\left(\\{X_{i_{1}},\ldots,X_{i_{J}}\\}\right)\right)\right)}{\lambda\left(conv\left(graph\left(\\{X_{i_{1}},\ldots,X_{i_{J}},x\\}\right)\right)\right)}.$
(2)

Considering the empirical average version given by

$\forall
x\in\mathcal{C}([0,1]),\;\;\bar{D}_{J,n}(x)=\frac{1}{J}\sum_{j=1}^{J}D_{j,n}(x)$

brings some ’stability’. However, the computational cost rapidly increasing
with $J$, small values of $J$ are preferred in practice. Moreover, as we
illustrate in Section 4.1, J equal two already yields satisfactory results.

Approximation from sampled curves. In general, one does not observes the batch
of continuous curves $\\{X_{1},\;\ldots,\;X_{n}\\}$ on the whole time interval
$[0,1]$ but at discrete time points only, the number $p\geq 1$ of time points
and the time points $0\leq t_{1}<t_{2}<\ldots<t_{p}\leq 1$ themselves possibly
varying depending on the curve considered. In such a case, the estimators
above are computed from continuous curves reconstructed from the sampled
curves available by means of interpolation procedures or approximation schemes
based on appropriate basis. In practice, linear interpolation is used for this
purpose with theoretical guarantees (refer to Theorem 3.2 below) facilitating
significantly the computation of the empirical ACH depth, see subsection 4.3.

###  3.1 Main Properties of the ACH Depth

In this subsection, we study theoretical properties of the population version
of the functional depths introduced above and next establish the consistency
of their statistical versions. The following result reveals that, among the
properties listed in the previous subsection, five are fulfilled by the
(average) ACH depth function.

###### Proposition 3.1

For all $J\geq 1$, the depth function $D_{J}$ (respectively, $\bar{D}_{J}$)
fulfills the following properties: ’non-degeneracy’, ’affine invariance’,
’vanishing at infinity’, ’continuity in $x$’ and ’continuity in $P$’. In
addition, the following properties are not satisfied: ’maximality at center’
and ’decreasing w.r.t. the deepest point’.

Refer to the Appendix section for the technical proof. In a functional space,
not satisfying maximality at center is not an issue. For instance, though the
constant trajectory $y(t)\equiv 0$ is a center of symmetry for the Brownian
motion, it is clearly not representative of this distribution. In contrast,
scalar-affine invariance is relevant, insofar as it allows z-normalization of
the functional data and continuity in $P$ is essential to derive the
consistency of $D_{J,n}$ (respectively, of $\bar{D}_{J,n}$), as stated below.

###### Theorem 3.1

Let $J\geq 1$ and $X_{1},\;\ldots,\;X_{n}$ be $n\geq J$ independent copies of
a generic r.v. $X$ with distribution $P\in\mathcal{P}(\mathcal{C}([0,1]))$. As
$n\to\infty$, we have, for any $x\in\mathcal{C}([0,1])$, with probability one,

$\left|D_{J,n}(x)-D_{J}(x,\;P)\right|\rightarrow 0$

and

$\left|\bar{D}_{J,n}(x)-\bar{D}_{J}(x,\;P)\right|\rightarrow 0.$

###  3.2 On Statistical/Computational Issues

As mentioned above, only sampled curves are available in practice. Each random
curve $X_{i}$ being observed at fixed time points
$0=t^{(i)}_{1}<t^{(i)}_{2}<\ldots<t^{(i)}_{p_{i}}=1$ (potentially different
for each $X_{i}$) with $p_{i}\geq 1$, we denoted by
$X^{\prime}_{1},\;\ldots,\;X^{\prime}_{n}$ the continuous curves reconstructed
from the sampled curves
$(X_{i}(t^{(i)}_{1}),\;\ldots,\;X_{i}(t^{(i)}_{p_{i}}))$, $1\leq i\leq n$, by
linear interpolation. From a practical perspective, one considers the
estimator $D^{\prime}_{J,n}(x)$ of $D_{J}(x,\;P)$ given by the approximation
of $D_{J,n}(x)$ obtained when replacing the $X_{i}$’s by the
$X^{\prime}_{i}$’s in (2). The (computationally feasible) estimator
$\bar{D}^{\prime}_{J,n}(x)$ of $\bar{D}_{J}(x,\;P)$ is constructed in a
similar manner. The result stated below shows that this approximation stage
preserves almost-sure consistency.

###### Theorem 3.2

Let $J\leq n$. Suppose that, as $n\rightarrow\infty$,

$\delta=\max_{1\leq i\leq n}\max_{2\leq k\leq
p_{i}}\left\\{t^{(i)}_{k+1}-t^{(i)}_{k}\right\\}\rightarrow 0.$

As $n\to\infty$, we have, for any $x\in\mathcal{C}([0,1])$, with probability
one,

$\left|D^{\prime}_{J,n}(x)-D_{J}(x,\;P)\right|\rightarrow 0$

and

$\left|\bar{D}^{\prime}_{J,n}(x)-\bar{D}_{J}(x,\;P)\right|\rightarrow 0.$

Refer to the Appendix section for the technical proof. Given the batch of
continuous and piecewise linear curves
$X^{\prime}_{1},\;\ldots,\;X^{\prime}_{n}$, although the computation cost of
the area of their convex hull is of order $O(p\log p)$ with $p=\max_{i}p_{i}$,
that of the U-statistic $D^{\prime}_{J,n}(x)$ (and a fortiori that of
$\bar{D}^{\prime}_{J,n}(x)$) becomes very expensive as soon as $\binom{n}{J}$
is large. As pointed out in Lopez-Pintado and Romo, (2009), even if the choice
$J=2$ for statistics of this type, may lead to a computationally tractable
procedure, while offering a reasonable representation of the distribution,
varying $J$ permits to capture much more information in general. For this
reason, we propose to compute an incomplete version of the $U$-statistic
$D^{\prime}_{J,n}(x)$ using a basic Monte-Carlo approximation scheme with
$K\geq 1$ replications: rather than averaging over all $\binom{n}{J}$ subsets
of $\\{1,\;\ldots,\;n\\}$ with cardinality $J$ to compute
$D^{\prime}_{J,n}(x)$, one averages over $K\geq 1$ subsets drawn with
replacement, forming an incomplete $U$-statistic, see Enqvist, (1978). The
same approximation procedure can be applied (in a randomized manner) to each
of the $U$-statistics involved in the average $\bar{D}^{\prime}_{J,n}(x)$, as
described in the Supplementary Material.

##  4 Numerical Experiments

From a practical perspective, this section explores certain properties of the
functional depth proposed using simulated data. It also describes its
performance compared with the state-of-the-art methods on (real) benchmark
datasets. As a first go, we focus on the impact of the choice of the tuning
parameter $K$, which rules the trade-off between approximation accuracy and
computational burden and parameter $J$. Precisely, it is investigated through
the stability of the ranking induced by the corresponding depths. We next
investigate the robustness of the ACH depth (ACHD in its abbreviated form),
together with its ability to detect abnormal observations of various types.
Finally, the ACH depth is benchmarked against alternative depths standing as
natural competitors in the functional setup using real datasets. A simulation-
based study of the variance of the ACH depth is postponed to the Supplementary
Material.

Figure 1: Boxplots of the approximations of $D_{J,n}(x_{0})$ (top) and
$D_{J,n}(x_{3})$ (bottom) over different size of $K$. The black crosses
correspond to the exact depth measure $D_{J,n}$ for each $J$ respectively.

For the sake of simplicity, the two same simulated datasets, represented in
Figure 3, are used throughout the section. The dataset $(a)$ corresponds to
sample path segments of the _geometric Brownian motion_ with mean $2$ and
variance $0.5$, a stochastic process widely used in statistical modeling. The
dataset $(b)$ consists of smooth curves given by $x(t)=a\cos(2\pi
t)+b\sin(2\pi t)$, $t\in[0,1]$, where $a$ and $b$ are independently and
uniformly distributed on $[0,0.05]$, as proposed by Claeskens et al., (2014).
Four curves $\\{x_{i}:\;i\in\\{0,1,2,3\\}\\}$ have been incorporated to each
dataset: a deep curve and three atypical curves (anomalies), with expected
depth-induced ranking $D_{J}(x_{3})<D_{J}(x_{2})\approx
D_{J}(x_{1})<D_{J}(x_{0})$.

###  4.1 Choosing Tuning Parameters $K$ and $J$

Figure 2: Rank-Rank plot for different values of J (2, 3 and 4). The first
line represents the rank over the dataset (a) while the second line represents
the dataset (b).

Parameter $K$ reflects the trade-off between statistical performance and
computational time. In order to investigate its impact on the stability of the
method, we compute depths of the deepest and most atypical curves ($x_{0}$ and
$x_{3}$) for dataset (b), taking $J=2,3,4$. Figure 1 presents boxplots of the
approximated ACHD (together with the exact values of ACHD) over $100$
repetitions. Note that, as expected, depth values grow with $J$. The variance
of the depth decreases taking sufficiently small values for $K=5n$ and almost
disappearing for $K\geq 20n$, while decreasing pattern remains the same for
different values of $K$. For these reasons, we keep $K=5n$ in what follows.

The choice of $J$ is less obvious, and clearly when describing an observation
in a functional space a substantial part of information is lost anyway.
Nevertheless, one observes that computational burden increases exponentially
with $J$ and thus smaller values are preferable. Figure 2 shows the rank-rank
plots of datasets (a) and (b) for small values of $J=2,3,4$ and indicates,
that depth-induced ranking does not change much with $J$. Thus, for saving
computational time, we use value $J=2$ in all subsequent experiments.

Figure 3: Datasets (a) (left) and (b) (right) containing 100 paths with four
selected observations. The colors are the same for the four selected
observations of both datasets (a) and (b).

###  4.2 Robustness

$d_{\tau}(\sigma_{0},\sigma_{\alpha})(\times 10^{-2})$
---
|  $\boldsymbol{\alpha}$ |  0 |  5 |  10 |  15 |  25 |  30
ACHD |  Location |  0 |  0.6 |  1.3 |  2.2 |  4.3 |  5.2
Isolated |  0 |  0.3 |  1.3 |  0.9 |  1.6 |  2.4
Shape |  0 |  0.9 |  2 |  2.6 |  4.2 |  4.7
FSDO |  Location |  0 |  3.6 |  7.3 |  10 |  16 |  20
Isolated |  0 |  0.8 |  3.6 |  3.2 |  7.2 |  9.4
Shape |  0 |  1.6 |  2.9 |  4.2 |  6.6 |  7.4
FT |  Location |  0 |  5.1 |  9.5 |  13 |  20 |  23
Isolated |  0 |  0.7 |  2.7 |  2.7 |  5.9 |  7.2
Shape |  0 |  1.7 |  2.9 |  4.3 |  6.6 |  7.7
FIF |  Location |  0 |  7 |  8.2 |  7.3 |  7.3 |  8.9
Isolated |  0 |  9.3 |  12 |  11 |  10 |  12
Shape |  0 |  7.4 |  7.9 |  10 |  14 |  14
Table 1: Kendall’s tau distances between the rank returned with normal data
($\sigma_{0}$) and contamined data ($\sigma_{\alpha}$, over different portion
of contamination $\alpha$ with location, isolated and shape anomalies) for
ACHD and three state-of-the-art methods. Bold numbers indicate best stability
of the rank over the contaminated datasets.

Under robustness of a statistical estimator on understands its ability not to
be “disturbed” by atypical observations. We explore robustness of ACHD in the
following simulation study: between the original dataset and the same dataset
contaminated with anomalies, we measure (averaged over $10$ random
repetitions) Kendall’s $\tau$ distance of two depth-induced rankings $\sigma$
and $\sigma^{\prime}$, respectively, of the original data:

$d_{\tau}(\sigma,\sigma^{\prime})=\frac{n(n-1)}{2}\sum_{i<j}\mathbbm{1}_{\\{(\sigma(i)-\sigma(j))(\sigma^{\prime}(i)-\sigma^{\prime}(j))<0\\}}\,.$

In their overview work, Hubert et al., (2015) introduce taxonomy for atypical
observations, focusing on _Location_ , _Isolated_ , and _Shape_ anomalies.
Here, we add _Location_ anomalies to dataset (a) and _Isolated_ and _Shape_
anomalies to dataset (b); other types of anomalies for both datasets can be
found in the Supplementary Material. The abnormal functions are constructed as
follows. _Location_ anomalies for dataset (a) are $\tilde{x}(t)=x(t)+ax(t)$
with $a$ drawn uniformly on $[0,1]$. _Isolated_ anomalies for dataset (b) are
constructed by adding a peak at $t_{0}$ (drawn uniformly on $[0,1]$) of
amplitude $b$ (drawn uniformly on $[0.03,0.06]$) such that
$\tilde{y}(t_{0})=y(t_{0})+b$ and $\tilde{y}(t)=y(t)$ for any $t\neq t_{0}$.
_Shape_ anomalies for dataset (b) are $\tilde{z}(t)=z(t)+0.01\times\cos(2\pi
tf)+0.01\times\sin(2\pi tf)$ with $f$ drawn uniformly from $\\{1,2,...,10\\}$.
By varying the percentage of abnormal observations $\alpha$, we compare ACHD
to several of the most know in the literature depth approaches: the
_functional Stahel-Donoho depth_ (FSDO) (Hubert et al.,, 2015) and the
_functional Tukey depth_ (FT) (Claeskens et al.,, 2014), and also to the
_functional isolation forest_ (FIF) algorithm (Staerman et al.,, 2019) which
proves satisfactory anomaly detection; see Table 3. One can observe that ACHD
consistently preserves depth-induced ranking despite inserted abnormal
observation, even if their fraction $\alpha$ reaches $30\%$. FSDO behaves
competitively giving slightly better results than ACHD for shape anomalies.

###  4.3 Applications to Anomaly Detection

Figure 4: Number of anomalies detected over a grid of parameters for three
types of anomalies (location, isolated, and shape) for ACHD and three further
state-of-the-art methods.

Further, we explore the ability of ACHD to detect atypical observations. For
this, we conduct an experiment in settings similar to those in Section 4.2,
while changing degree of abnormality gradually for $15$ (out of $100$ curves)
in dataset (a). Thus, we alter $a$ in $[0,3]$ for _location anomalies_ , $b$
in $[0,10]$ for _isolated anomalies_ , and $e$ in $[1,2]$ for _shape
anomalies_ to amplify the ”spikes” of oscillations such that
$\tilde{z}(t)=ez(t)$. (For an illustration of abnormal curves the reader is
referred to the Supplementary Material.) Figure 4 illustrates number of
anomalies detected by ACHD, FSDO, FT, and FIF for different parameters of
abnormality. While it is difficult to find the general winner, ACHD behaves
favorably in all the considered cases and clearly outperforms the two other
depths when the data is contaminated with _isolated anomalies_.

We conclude this section with a _real-world data benchmark_ based on three
datasets: Octane (Esbensen,, 2001), Wine (Larsen et al.,, 2006), and EOG (Chen
et al.,, 2015). The Wine dataset consists of 397 measurements of proton
nuclear magnetic resonance (NMR) spectra of 40 different wine samples, the
Octane dataset are 39 near infrared (NIR) spectra of gasoline samples with 226
measurements, while the EOG dataset represents the electrical potential
between electrodes placed at points close to the eyes with 1250 measurements.
(Graphs of the three datasets can be found in the Supplementary Material.) As
pointed out by Hubert et al., (2015), it is difficult to detect anomalies in
the first two datasets, while they are easily seen during the human eye
inspection. For the EOG dataset, we assign smaller of the two classes to be
abnormal. To the existing state-of-the-art methods, we add here _Isolation
Forest_ (IF) (Liu et al.,, 2008) and the _One-Class SVM_ (OC) (Schölkopf et
al.,, 2001)—multivariate methods applied after a proper dimension reduction
(to the dimension 10) using _Functional Principal Component Analysis_
(FPCA).(Ramsay and Silverman,, 2002). Portions of detected anomalies (by all
the considered methods), indicated in Table 2, hint on very competitive
performance of ACHD in the addressed benchmark.

| ACHD | FSDO | FT | FIF | IF | OC
---|---|---|---|---|---|---
Octane | 1 | 0.5 | 0.33 | 1 | 0.5 | 0.5
Wine | 1 | 0 | 0 | 1 | 0 | 1
EOG | 0.73 | 0.55 | 0.48 | 0.43 | 0.63 | 0.6
Table 2: Portion of detected anomalies of benchmark methods for the Octane,
Wine, and EOG datasets.

##  5 Conclusion

In this paper, we have introduced a novel functional depth function on the
space $\mathcal{C}([0,1])$ of real valued continuous curves on $[0,1]$ that
presents various advantages. Regarding interpretability first, the depth
computed at a query curve $x$ in $\mathcal{C}([0,1])$ takes the form of an
expected ratio, quantifying the relative increase of the area of the convex
hull of i.i.d. random curves when adding $x$ to the batch. We have shown that
this depth satisfies several desirable properties and have explained how to
solve approximation issues, concerning the sampled character of observations
in practice and scalability namely. Numerical experiments on both synthetic
and real data have highlighted a number of crucial benefits: reduced variance
of its statistical versions, robustness with respect to the choice of tuning
parameters and to the presence of outliers in the training sample, capacity of
detecting (possibly slight) anomalies of various types, surpassing competitors
such as depths of integral type, for isolated anomalies in particular. The
open-source implementation of the method, along with all reproducing scripts,
can be accessed at https://github.com/GuillaumeStaermanML/ACHD.

Acknowlegments

The authors thank Stanislav Nagy for his helpful remarks. The authors thank
Stanislav Nagy for some helpful remarks. This work has been funded by BPI
France in the context of the PSPC Project Expresso (2017-2021).

## References

  * Arcones, (2003) Arcones, M. (2003).  On the asymptotic accuracy of the bootstrap under arbitrary resampling size.  Ann. Inst. Statist. Math., 55:563–583.
  * Chakraborty and Chaudhuri, (2014) Chakraborty and Chaudhuri (2014).  The spatial distribution in infinite dimensional spaces and related quantiles and depths.  The annals of statistics.
  * Chen et al., (2015) Chen, Y., Keogh, E., Hu, B., Begum, N., Bagnall, A., Mueen, A., and Batista, G. (2015).  The ucr time series classification archive.
  * Claeskens et al., (2014) Claeskens, G., Hubert, M., Slaets, L., and Vakili, K. (2014).  Multivariate functional halfspace depth.  Journal of American Statistical Association, 109(505):411–423.
  * Cuevas et al., (2007) Cuevas, A., Febrero, M., and Fraiman, R. (2007).  Robust estimation and classification for functional data via projection-based depth notions.  Computational Statistics, 22(3):481–496.
  * Dudley, (1984) Dudley (1984).  A course on empirical processes.  In springer, editor, Ecole d’Eté de probabilités de Saint-Flour XII. Lecture Notes in Math. Cambridge University press, New York.
  * Dudley, (2002) Dudley, R. M. (2002).  Real Analysis and Probability.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition.
  * Dutta et al., (2011) Dutta, Ghosh, and Chaudhuri (2011).  Some intriguing properties of tukey’s half-space depth.  Bernouilli.
  * Enqvist, (1978) Enqvist, E. (1978).  On sampling from sets of random variables with application to incomplete $U$-statistics.  PhD thesis, Lund University.
  * Esbensen, (2001) Esbensen, K. (2001).  Multivariate data analysis-in practice.  Camo Software.
  * Ferraty and Vieu, (2006) Ferraty, F. and Vieu, P. (2006).  Nonparametric Functional Data Analysis.  Springer-Verlag, New York.
  * Fraiman and Muniz, (2001) Fraiman, R. and Muniz, G. (2001).  Trimmed means for functional data.  Test, 10(2):419–440.
  * Gijbels and Nagy, (2018) Gijbels, I. and Nagy, S. (2018).  On a general definition of depth for functional data.  Statistical Science.
  * Hubert et al., (2015) Hubert, M., Rousseeuw, P. J., and Segaert, P. (2015).  Multivariate functional outlier detection.  Statistical Methods & Applications, 24(2):177–202.
  * Jörnsten, (2004) Jörnsten, R. (2004).  Clustering and classification based on the l1 data depth.  Journal of Multivariate Analysis, 90(1):67 – 89.
  * Lange et al., (2014) Lange, T., Mosler, K., and Mozharovskyi, P. (2014).  Fast nonparametric classification based on data depth.  Statistical Papers, 55(1):49–69.
  * Larsen et al., (2006) Larsen, F., Berg, F., and Engelsen, S. (2006).  An exploratory chemometric study of 1 h nmr spectra of table wine.  Journal of Chemometrics, 20:198 – 208.
  * Lee, (1990) Lee, A. J. (1990).  ${U}$-statistics: Theory and practice.  Marcel Dekker, Inc., New York.
  * Liu et al., (2008) Liu, F. T., Ting, K. M., and Zhou, Z. (2008).  Isolation forest.  In 2008 Eighth IEEE International Conference on Data Mining, pages 413–422.
  * Long and Huang, (2016) Long and Huang (2016).  A study of functional depths.  preprint.
  * Lopez-Pintado and Romo, (2009) Lopez-Pintado, S. and Romo, J. (2009).  On the concept of depth for functional data.  Journal of the American Statistical Association.
  * Lopez-Pintado and Romo, (2011) Lopez-Pintado, S. and Romo, J. (2011).  A half-region depth for functional data.  Computational Statistics and Data Analysis.
  * Mosler and Mozharovskyi, (2017) Mosler, K. and Mozharovskyi, P. (2017).  Fast dd-classification of functional data.  Statistical Papers, 58(4):1055–1089.
  * Nagy et al., (2016) Nagy, S., Gijbels, I., and Hlubinka, D. (2016).  Weak convergence of discretely observed functional data with applications.  Journal of Multivariate Analysis, 146:46 – 62.
  * Nagy et al., (2017) Nagy, S., Gijbels, I., and Hlubinka, D. (2017).  Depth-based recognition of shape outlying functions.  Journal of Computational and Graphical Statistics, 26(4):883–893.
  * Nieto-Reyes and Battey, (2016) Nieto-Reyes, A. and Battey, H. (2016).  A topologically valid definition of depth for functional data.  Statistical Science.
  * Oja, (1983) Oja (1983).  Descriptive statistics for multivariate distributions.  Statistics and Probability Letters.
  * Ramsay and Silverman, (2002) Ramsay, J. O. and Silverman, B. W. (2002).  Applied Functional Data Analysis: Methods and Case Studies.  Springer-Verlag, New York.
  * Ramsay and Silverman, (2005) Ramsay, J. O. and Silverman, B. W. (2005).  Functional Data Analysis.  Springer-Verlag, New York.
  * Rossi and Villa, (2006) Rossi, F. and Villa, N. (2006).  Support vector machine for functional data classification.  Neurocomputing, 69(7):730 – 742.
  * Schneider, (2013) Schneider, R. (2013).  Convex Bodies: The Brunn-Minkowski Theory.  Cambridge University Press, Cambridge.
  * Schneider and Weil, (2008) Schneider, R. and Weil, W. (2008).  Stochastic and Integral Geometry.  Springer-Verlag, Berlin Heidelberg.
  * Schölkopf et al., (2001) Schölkopf, B., Platt, J., Shawe-Taylor, J., Smola, A., and Williamson, R. (2001).  Estimating the support of a high-dimensional distribution.  Neural Computation, 13(7):1443–1471.
  * Serfling, (2006) Serfling, R. (2006).  Depth functions in nonparametric multivariate inference.  DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 72.
  * Staerman et al., (2019) Staerman, G., Mozharovskyi, P., Clémençon, S., and d’Alché Buc, F. (2019).  Functional isolation forest.  In Proceedings of The 11th Asian Conference on Machine Learning.
  * (36) Tukey (1975a).  Mathematics and the picturing of data.  In Proceedings of the International Congress of Mathematicians.
  * (37) Tukey, J. W. (1975b).  Mathematics and the picturing of data.  In James, R., editor, Proceedings of the International Congress of Mathematicians, volume 2, pages 523–531. Canadian Mathematical Congress.
  * Zuo and Serfling, (2000) Zuo, B. and Serfling, R. (2000).  General notions of statistical depth function.  The Annals of Statistics, 28(2):461–482.

Supplementary Material to the Article
The Area of the Convex Hull of Sampled Curves:
a Robust Functional Statistical Depth Measure

First, Section A collects technical proofs omitted in the body of the article.
Then, Section B provides the exact algorithm for approximate computation of
the proposed depth notion. Finally, Section C collects further experimental
results mentioned in the article.

##  A Technical proofs

This part presents the proofs of Proposition 3.1, Theorems 3.1 and 3.2 as well
as the counter examples for the non-satisfied properties. Most of the proofs
are done for both $D_{J}$ and $\overline{D}_{J}$.

###  A.1 Proof of Proposition 3.1

####  A.1.1 Affine-invariance

Let $a,b\in\mathbb{R}$, it is clear that

$\displaystyle conv\left(graph\left(\\{aX_{1}+b,...,aX_{n}+b\\}\right)\right)$
$\displaystyle=a\times
conv\left(graph\left(\\{X_{1},...,X_{n}\\}\right)\right)+b$

where $a\times
conv\left(graph\left(\\{X_{1},...,X_{n}\\}\right)\right)+b=\\{(t,ax+b):(t,x)\in
conv\left(graph\left(\\{X_{1},...,X_{n}\\}\right)\right)\\}$. Following this,
and by properties of Lebesgue measure, we have

$\displaystyle\frac{\lambda_{2}\left(a\times
conv\left(graph\left(\\{X_{1},...,X_{n}\\}\right)\right)+b\right)}{\lambda_{2}\left(a\times
conv\left(graph\left(\\{X_{1},...,X_{n},z\\}\right)\right)+b\right)}$
$\displaystyle=\frac{\lambda_{2}\left(a\times
conv\left(graph\left(\\{X_{1},...,X_{n}\\}\right)\right)\right)}{\lambda_{2}\left(a\times
conv\left(graph\left(\\{X_{1},...,X_{n},z\\}\right)\right)\right)}$
$\displaystyle=\frac{a\times\lambda_{2}\left(conv\left(graph\left(\\{X_{1},...,X_{n}\\}\right)\right)\right)}{a\times\lambda_{2}\left(conv\left(graph\left(\\{X_{1},...,X_{n},z\\}\right)\right)\right)}$
$\displaystyle=\frac{\lambda_{2}\left(conv\left(graph\left(\\{X_{1},...,X_{n}\\}\right)\right)\right)}{\lambda_{2}\left(conv\left(graph\left(\\{X_{1},...,X_{n},z\\}\right)\right)\right)}$

The case of $\mathbf{a},\mathbf{b}\in\mathcal{X}$:
Now, we just take a counter example to prove that it is not true if $b$
belongs to $\mathcal{X}$, the case where $a\in\mathcal{X}$ is trivial. For the
sake of simplicity, let $I=[0,1]$ and $J=2$. If we take $x\equiv 0,x_{1}\equiv
1,x_{2}\equiv 2$ and $X$ a random variable with distribution $P$ such that
$\mathbb{P}(X\equiv x_{1})=\frac{1}{2}$ and $\mathbb{P}(X\equiv
x_{2})=\frac{1}{2}$. Let $X_{1},X_{2}$ be samples from $P$ and $b$ be
continuous function
$t\mapsto(10t-4)\mathbbm{1}_{([0.4,0.5])}+(-10t+6)\mathbbm{1}_{([0.5,0.6])}$.
It is easy to see that $D_{J}(x|P)=\frac{1}{8}\neq D_{J}(x+b|P_{X+b})$ since

$\displaystyle D_{J}(x+b|P_{X+b})$
$\displaystyle=\frac{1}{2}\times\left(\frac{1}{2}\times\frac{0.5}{1.5}+\frac{1}{2}\times\frac{0.5}{2.5}\right)^{j=1}+\frac{1}{2}\times\left(\frac{1}{4}\times\frac{0.5}{1.5}+\frac{1}{4}\times\frac{0.5}{2.5}+\frac{1}{2}\times\frac{1.5}{2.5}\right)^{j=2}$
$\displaystyle=\frac{8}{60}+\frac{9}{60}$ $\displaystyle=\frac{17}{60}.$

Note that even if we set $j>1$ to avoid the fact that the convex hull of
constant function have null Lebesgue measure, $D_{J}(x|P)$ and
$D_{J}(x+b|P_{X+b})$ remain different, see Fig. 5.

Figure 5: Plots of the functions used in the case of
$\mathbf{a},\mathbf{b}\in\mathcal{X}$. The three red lines come from
$x_{1},x_{2},x$. The cyan curves correspond to $x_{1}+b$ and $x_{2}+b$ and
blue curve to $x+b$.

####  A.1.2 Vanishing at infinity

Let $J$ be fixed and $x_{n}$ a sequence of function such that $||x_{n}||$
tends to infinity when $n$ grows, for every $j\in\\{1,...,J\\}$ we define :

$\displaystyle\Phi_{x_{n}}:$ $\displaystyle\quad\mathcal{X}^{\otimes
j}\;\;\;\;\;\;\longrightarrow[0,1]$
$\displaystyle(x_{1},...,x_{j})\longmapsto\frac{\lambda_{2}\left(conv\left(graph(\\{x_{1},...,x_{j}\\})\right)\right)}{\lambda_{2}\left(conv\left(graph(\\{x_{1},...,x_{j},x_{n}\\})\right)\right)}$

As a continuous function on compact set, $x_{1},...,x_{j}$ are bounded, then
$\Phi_{x_{n}}\underset{||x_{n}||_{\infty}\rightarrow\infty}{\longrightarrow}0$.
The result follows from dominated convergence theorem since $\Phi_{x_{n}}$ is
bounded by 1.

####  A.1.3 Continuity in $x$

Let $x_{1},...,x_{j}$, $j\in\\{1,...,J\\}$ be fixed curves in $\mathcal{C}(I)$
with at least two different curves, i.e, there exists a $t\in I$ and
$l,k\in{1,...,j}$ such that $x_{k}(t)\neq x_{l}(t)$. If $j=1$, we need that
$x_{1}$ is not a constant function. From Lemma A.6.1, we know that the
function

$f:x\longmapsto Band(x_{1},...,x_{j},x)$

is continuous.

Let $\mathcal{K}_{2}$ be the set of all compact set in $\mathbb{R}^{2}$ and
$\mathcal{K}^{C}_{2}$ the set of all convex bodies (compact, convex set with
non-empty interior). We equip both spaces with the Hausdorff distance. We know
that :

$\displaystyle conv:$
$\displaystyle\,\mathcal{K}_{2}\longrightarrow\mathcal{K}_{2}$
$\displaystyle\,K_{2}\longmapsto conv(K_{2})$

and

$\displaystyle\psi:$
$\displaystyle\,\mathcal{K}^{C}_{2}\longrightarrow\mathcal{K}^{C}_{2}$
$\displaystyle\,K^{c}_{2}\longmapsto\lambda_{2}(K^{c}_{2})$

are continuous with respect to the Hausdorff distance. See for example,
Theorems 12.3.5 and 12.3.6 in Schneider and Weil, (2008) for $g$ and Theorem
1.8.16 in Schneider, (2013) for $\psi$. Then $\Phi:=\psi\circ conv\circ f$ :
$x\,\mapsto\lambda_{2}\left(conv\left(graph\\{x_{1},...,x_{j},x\\})\right)\right)$
is continuous.
It is straightforward to show that

$\phi:x\longmapsto\frac{\lambda_{2}\left(conv\left(graph(\\{x_{1},...,x_{j}\\})\right)\right)}{\lambda_{2}\left(conv\left(graph(\\{x_{1},...,x_{j},x\\})\right)\right)}$

is continuous. Now, we just have to prove that

$\;x\longmapsto\mathbb{E}\left[\frac{\lambda_{2}\left(conv\left(graph(\\{x_{1},...,x_{j}\\})\right)\right)}{\lambda_{2}\left(conv\left(graph(\\{x_{1},...,x_{j},x\\})\right)\right)}\right]$

is continuous which is true by dominated convergence theorem. We conclude the
proof with the continuity of the sum of continuous functions.

###  A.2 Continuity in $P$

$\left(\mathcal{C}([0,1]),||.||_{\infty}\right)$ is a polish space and implies
that the set of all probability measures on this space with the Lévy-Prohorov
metric $\rho_{LP}$ is still polish. By the portmanteau theorem (e.g., see
Theorem 11.3.3 in Dudley, (2002)) it follows that
$\rho_{LP}(Q_{n},Q)\rightarrow 0$ is equivalent to
$Q_{n}\overset{d}{\rightarrow}Q$ for $Q,Q_{n}$ respectively a measure and a
sequence of measures on $\mathcal{C}([0,1])$. It implies that

$\int fdQ_{n}\longrightarrow\int fdQ$

for every $f$ bounded continuous real function on
$\left(\mathcal{C}([0,1]),||.||_{\infty}\right)$.

Let $j$ be fixed natural number and define the following function

$\displaystyle\Phi_{x}:$ $\displaystyle\quad\quad\mathcal{X}^{\otimes
j}\;\;\longrightarrow[0,1]$
$\displaystyle(x_{1},...,x_{j})\longmapsto\frac{\lambda_{2}\left(conv\left(graph(\\{x_{1},...,x_{j}\\})\right)\right)}{\lambda_{2}\left(conv\left(graph(\\{x_{1},...,x_{j},x\\})\right)\right)}$

If we equip $\mathcal{C}([0,1])^{\otimes j}$ with the infinite norm
$|||.|||_{\infty,j}$ defined by

$|||f|||_{\infty,j}=max(||f_{1}||_{\infty},...,||f_{j}||_{\infty}),$

following the same argument from the proof A.1.3, $\Phi_{x}$ is bounded and
continuous.
Now, let $J\leq n$ be fixed and $P_{n}$ be a sequence of measures on
$\mathcal{C}([0,1])$ such that $\rho_{LP}(Q_{n},Q)\rightarrow 0$. we have :

$\displaystyle\underset{n\rightarrow\infty}{\lim}\sum_{j=1}^{J}D_{j}(x|Q_{n})$
$\displaystyle=\sum_{j=1}^{J}\underset{n\rightarrow\infty}{\lim}\int_{\mathcal{C}([0,1])^{\otimes
j}}\Phi_{x}dQ^{\otimes j}_{n}$
$\displaystyle=\sum_{j=1}^{J}\int_{\mathcal{C}([0,1])^{\otimes
j}}\Phi_{x}dQ^{\otimes j}$ $\displaystyle=\sum_{j=1}^{J}D_{j}(x|Q)$

Then the results holds for $\sum_{j=1}^{J}D_{j}$ (and trivially for $D_{J}$).

###  A.3 Proof of the Theorem 3.1

For every $1\leq j\leq J$,the term $|D_{j,n}(x|P_{n})-D_{j}(x|P)|$ goes to
zero almost-surely by U-statistics consistency (see e.g. hoeffding1961strong).
Then

$\mathbb{P}\left(\forall
j:\bigg{|}D_{j,n}(x|P_{n})-D_{j}(x|P)\bigg{|}\rightarrow 0\right)=1$

which is equivalent to

$\mathbb{P}\left(\sum_{j=1}^{J}\bigg{|}D_{j,n}(x|P_{n})-D_{j}(x|P)\bigg{|}\rightarrow
0\right)=1\,.$

By triangle inequality, for any $x\in\mathcal{C}([0,1])$,

$\displaystyle\bigg{|}\sum_{j=1}^{J}D_{j,n}(x|P_{n})-D_{j}(x|P)\bigg{|}$
$\displaystyle\leq\sum_{j=1}^{J}\bigg{|}D_{j,n}(x|P_{n})-D_{j}(x|P)\bigg{|}$
$\displaystyle\leq\sum_{j=1}^{J}\bigg{|}D_{j,n}(x|P_{n})-D_{j}(x|P)\bigg{|}$

which leads to the result.

###  A.4 Proof of the Theorem 3.2

The result follows from the continuity in $P$ and Theorem 3 in Nagy et al.,
(2016).

###  A.5 Counter-examples for the not-satisfied properties

####  A.5.1 Maximality at the center

We restrict ourselves for simplicity to $J=2$ and $I=[0,1]$. Let $X\sim P$ be
a distribution such that $P(X\equiv y_{1})=P(X\equiv y_{2})=\frac{1}{2}$ with

$\displaystyle y_{1}$
$\displaystyle=(-2t+1)\mathbbm{1}_{[0,0.25]}+(2t)\mathbbm{1}_{[0.25,0.5]}+(-2t+2)\mathbbm{1}_{[0.5,0.75]}+(2t-1)\mathbbm{1}_{[0.75,1]}\,,$
$\displaystyle y_{2}=-y_{1}\,.$

The distribution is clearly centrally and halfspace symmetric around
$\theta\equiv 0$ but we have

$D_{J}(\theta,P)<D_{J}(y_{1},P)=D_{J}(y_{2},P)\,.$

Since

$\displaystyle D_{J}(0,P)$
$\displaystyle=\frac{1}{2}\times\left(\frac{1}{2}\times\frac{3}{8}+\frac{1}{2}\times\frac{3}{8}\right)^{j=1}+\frac{1}{2}\times\left(\frac{1}{2}+\frac{1}{4}\times\frac{3}{8}+\frac{1}{4}\times\frac{3}{8}\right)^{j=2}$
$\displaystyle=\frac{17}{32}\approx 0.53$

and

$\displaystyle D_{J}(y_{1},P)$
$\displaystyle=\frac{1}{2}\times\left(\frac{1}{2}\times+\frac{1}{2}\times\frac{3}{16}\right)^{j=1}+\frac{1}{2}\times\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{4}\times\frac{3}{16}\right)^{j=2}$
$\displaystyle=\frac{70}{128}\approx 0.546$

Figure 6: Plot of the functions used in the counter example of the maximality
at the center property. $y_{1}$ (blue curve) and $y_{2}$ (cyan curve)
correspond to the distribution and $\theta\equiv 0$ corresponds to the red
curve.

####  A.5.2 Decreasing w.r.t. the deepest point

We restrict ourselves $I$ to $[0,1]$ and $J=2$ for the sake of comprehension
but the example still works on every $I$. Let $P$ be the distribution such
that

$P(X\equiv 0)=P(X\equiv 1)=P(X\equiv-1)=\frac{1}{3}.$

It is clear from this distribution that
$0\in\underset{x\in\mathcal{X}}{\text{sup }}D(x,P)$ and , if we write $z\equiv
0$, $D_{J}(z,P)=\frac{1}{4}$. We define $y\equiv 1.5$ and
$x(t)=4t\mathbbm{1}_{[0,0.5]}(t)+(-4t+4)\mathbbm{1}_{[0.5,1]}(t)$. We have
$d(x,z)=2$, $d(x,y)=0.5$ and $d(y,z)=1.5$. If we compute the depth of $x$ and
$y$ we have :

$D_{J}(y,P)=\frac{1}{2}\times\frac{2}{9}\times\left(\frac{4}{5}+\frac{2}{5}+\frac{2}{3}\right)=\frac{23}{135}$

and

$D_{J}(x,P)=\frac{1}{2}\times\frac{2}{9}\times\left(\frac{4}{5}+\frac{1}{2}+\frac{8}{9}\right)=\frac{197}{810}\,.$

The result follows. Notice that the result remains true if $conv$ is replaced
by the $band$ function.

Figure 7: Plots of the functions used in the counter example of the decreasing
property. The three red lines come from the distribution, the thicker red
curve corresponds to the maximal depth. The cyan curve corresponds to $x$ and
the blue curve to $y$.

###  A.6 Technical requirements

###### Lemma A.6.1

Let $x_{1},...,x_{j}$, $j\in\\{1,...,J\\}$ be fixed curves in
$\mathcal{C}([0,T])$. The function

$\displaystyle\mathcal{C}([0,T])\longrightarrow\mathcal{K}_{2}$ $\displaystyle
x\mapsto Band(x_{1},...,x_{j},x)$

is continuous if we equip $\mathcal{K}_{2}$ with the Hausdorff distance
$d_{H}$.

Proof. Let $x_{0}\in\mathcal{C}([0,T])$ and $j$ be fixed in $\\{1,...,J\\}$.
We want to prove

$\forall\epsilon>0,\exists\delta:\forall
x\in\mathcal{C}([0,T]):||x-x_{0}||_{\infty}<\delta\Rightarrow
d_{H}(Band(x_{1},...,x_{j},x),Band(x_{1},...,x_{j},x_{0}))\leq\epsilon$

Let $\epsilon>0$, and write $B_{x}:=Band(x_{1},...,x_{j},x)$ and
$B_{x_{0}}:=Band(x_{1},...,x_{j},x_{0})$ for the simplicity of notation. We
have :

$d_{H}(B_{x},B(x_{0}))=max\left(\underset{z\in B_{x}}{\text{sup
}}d(z,B_{x_{0}}),\underset{z\in B_{x_{0}}}{\text{sup }}d(z,B_{x})\right)$

with $d$ being the distance induced by $||.||_{\infty}$.
It is easy to see that for any $z\in B_{x}$, $\underset{y\in
B_{x_{0}}}{\text{inf }}||z-y||_{\infty}$ is minimized by the function
$y^{*}(t)=z(t)\mathds{1}_{(z(t)\in
B_{x_{0}})}+max(x_{1}(t),...,x_{j}(t),x(t))\mathds{1}_{(z(t)\notin
B_{x_{0}})}$.

Following this, we have :

$\displaystyle d(z,B_{x_{0}})$ $\displaystyle=||z-y^{*}||_{\infty}$
$\displaystyle=\max(\underset{t:z(t)\notin B_{x_{0}},z(t)>B_{x_{0}}}{\text{sup
}}|z(t)-max(x_{1}(t),...,x_{j}(t),x(t))|,$
$\displaystyle\underset{t:z(t)\notin B_{x_{0}},z(t)<B_{x_{0}}}{\text{sup
}}|z(t)-min(x_{1}(t),...,x_{j}(t),x(t))|)$

$z\in B_{x}$ implies that $\forall t,\quad
min\left(x(t),\underset{i=1,...,j}{\text{min }}X_{i}(t)\right)\leq z(t)\leq
max\left(x(t),\underset{i=1,...,j}{\text{max }}X_{i}(t)\right)$ . If
$z(t)>B_{x_{0}}$ too, $max(\underset{i=1,...,j}{\text{max
}}X_{i}(t),x_{0}(t))<z(t)\leq x(t)$ and

$\underset{t:z(t)\notin B_{x_{0}},z(t)>B_{x_{0}}}{\text{sup
}}|z(t)-max(x_{1}(t),...,x_{j}(t),x(t))|=\underset{t:z(t)\notin
B_{x_{0}},z(t)>B_{x_{0}}}{\text{sup }}|z(t)-x(t)|.$

With the same argument we have :

$\underset{t:z(t)\notin B_{x_{0}},z(t)<B_{x_{0}}}{\text{sup
}}|z(t)-max(x_{1}(t),...,x_{j}(t),x(t))|=\underset{t:z(t)\notin
B_{x_{0}},z(t)<B_{x_{0}}}{\text{sup }}|z(t)-x(t)|.$

It follows that for every $z\in B_{x}$ ,
$d(z,B_{x_{0}})\leq||x-x_{0}||_{\infty}\leq\epsilon$ (simply by taking
$\delta=\epsilon$). We then have

$\underset{z\in B_{x}}{\text{sup }}d(z,B_{x_{0}})\leq\epsilon\,.$

We can prove that

$\underset{z\in B_{x_{0}}}{\text{sup }}d(z,B_{x})\leq\epsilon$

with the same argument which lead us to the final result.

##  B Monte-Carlo approximation of the average version of the empirical ACH
depth.

The procedure given in Section 3.2 can be summarize by the Algorithm B.

Input:
$\tilde{\mathcal{S}}_{n}=\\{X_{1}^{\prime},\ldots,X_{n}^{\prime}\\}$-dataset,
the observed curve $x^{\prime}$, $K$, $1\leq J\leq n$ and the vector of
weights $\mathbf{w}=(w_{j})_{1\leq j\leq J}$ such that
$\mathbf{w}_{j}=\frac{\binom{j}{n}}{\sum_{m=1}^{J}\binom{m}{n}}$.

  1. 1.

For $k=1,\ldots,K$ do:

     * (i)

Select $l\in\\{1,\ldots,J\\}$ according to $\mathbf{w}$.

     * (ii)

Select randomly and uniformly $(i_{1},\ldots,i_{l})\in\\{1,\ldots,n\\}$.

     * (iii)

$s(x^{\prime})\leftarrow
s(x^{\prime})+\frac{\lambda_{2}\left(conv\left(graph\left(\\{X_{i_{1}}^{\prime},\ldots,X_{i_{l}}^{\prime}\\}\right)\right)\right)}{\lambda_{2}\left(conv\left(graph\left(\\{X_{i_{1}}^{\prime},\ldots,X_{i_{l}}^{\prime},x^{\prime}\\}\right)\right)\right)}$.

  2. 2.

Return:
$\quad\overline{D}_{J,n}(x^{\prime}|\mathcal{S}_{n}^{\prime})=\frac{1}{K}s(x^{\prime})$.

##  C Additional Experiences

###  C.1 Asymptotic variance of the exact and approximate versions

To obtain further insights about the stability of the proposed depth notion,
we explore its asymptotic variance. For this, we compute (exact and
approximate) ACHD of $x_{i},\,i=1,2,3,4$ for different sample sizes. The
boxplots over $100$ repeated simulation for data sets (a) and (b) are
indicated in Fig. 8 and 9. One observes not only stable decrease of the
variance of ACHD with the sample size, but also the similarity between exact
and approximate versions, which hints on stability and precision of the exact
algorithm even when exploring a small portion of combinations (e.g., when
$n=500$ only $2\%$ of all pairs are explored for $K=5n$).

$x_{0}$ | $x_{1}$
---|---
|
$x_{2}$ | $x_{3}$
|
Figure 8: Boxplot (over $100$ repetitions) of the depth score for the observations $\mathbf{x}_{0},\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3}$ for the two following settings on the data set (a): the green boxplots represent the exact computation while the orange boxplots represent the approximation both with $J=2$. $x_{0}$ | $x_{1}$
---|---
|
$x_{2}$ | $x_{3}$
|
Figure 9: Boxplot (over $100$ repetitions) of the depth score for the
observations $\mathbf{x}_{0},\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3}$ for
the two following settings on the data set (b): the green boxplots represent
the exact computation while the orange boxplots represent the approximation
both with $J=2$. Figure 10: Number of anomalies detected over a grid of
parameters for two types of anomalies, location and isolated anomalies for
ACHD and three others state-of-art methods.

The dataset Octane, Wine, and EOG used in the Section 4.4 are represented in
Figure 11.

|  |
---|---|---
Figure 11: The data sets Octane, Wine, and EOG used in Section 4.5.

###  C.2 Robustness

Additional results on the robustness experiment are given in Table 3 for the
location anomalies with the dataset (b) and the isolated anomalies for the
data set (a).

$d_{\tau}(\sigma_{0},\sigma_{\alpha})(\times 10^{-2})$
---
|  $\boldsymbol{\alpha}$ |  0 |  5 |  10 |  15 |  25 |  30
ACHD |  Location |  0 |  0.7 |  1.5 |  2.3 |  4.2 |  5.1
Isolated |  0 |  1.3 |  1.8 |  1.6 |  2.4 |  3.2
FSDO |  Location |  0 |  1.5 |  3.1 |  5.1 |  8.8 |  11
Isolated |  0 |  0.9 |  1 |  1.1 |  1.5 |  1.6
FT |  Location |  0 |  0.6 |  1.5 |  3 |  6.4 |  8
Isolated |  0 |  1.3 |  0.8 |  0.9 |  1.1 |  1.5
FIF |  Location |  0 |  14 |  15 |  15 |  16 |  15
Isolated |  0 |  6.9 |  7.3 |  7 |  8.2 |  8.1
Table 3: Kendall’s tau distances between the rank returned with normal data
and contaminated data (over different size of contamination with location and
isolated anomalies) for the area of the convex hull depth measure and three
others state-of-art methods.

###  C.3 Anomaly detection

Additional experiments with location anomalies from the data set (b) and
isolated anomalies from data set (a) are given in Figure 10.