[1]Utpal Roy

[1]Department of Physics, Indian Institute of Technology, Patna, 801106,
Bihar, India

2]Department of Physics, Indian Institute of Science Education and Research,
Kolkata, 741246, West Bengal, India

# Matter Wave Isotope Separation in a Ring Trap

Sriganapathy Raghav  Suranjana Ghosh  Barun Halder<EMAIL_ADDRESS>*  [

###### Abstract

We devise a novel mechanism of isotope separation from a mixture of Bose-
Einstein condensate in the presence of interspecies interaction. Fractional
revivals of this miscible system are studied inside a ring waveguide for
spatially resolving the isotopes of $Rb$. The characteristic time scale is
influenced by the ring radius and the strength of interspecies interaction. We
identify the physical parameters for which the autocorrelation function
displays the signature of distinguishability. A study of the separability
function further suggests favourable time instances for separating the
isotopes with greater yields. The precise ranges of ring radius and
interspecies interaction strength are revealed. We illustrate condensate
densities at proposed time instances, which confirms our results and also
validates our method.

##  1 Introduction

The natural abundances of isotopes are mostly in the form of mixtures. Often,
a particular isotope is required in pure form and thus, isotope separation has
been an enduring problem in science. Separation of stable isotopes involves
methods such as diffusion or centrifugation [1], ion-exchange chromatography
[2], light-induced drift isotope separation (LIDIS) [3, 4] _etc._ , which rely
on the difference in the isotopic mass, isotopic charge and isotopic shift in
atomic or molecular spectral lines, respectively. The isotopes of the alkali
metals can be separated from an isotopic mixture of Bose-Einstein condensate
(BEC), where phase separation is exploited by tuning the interspecies Feshbach
resonance [5, 6, 7]. One could note that the regime of separation for the
ground state of the two species lies at the greater values of the interspecies
interaction [8, 6, 9]. This is because, at higher values of interspecies
interaction, the energy of the inhomogeneous state is lower than that of the
homogeneous state, which favours the spatial separation of the isotopes. The
isotope separation is also predicted for a BEC mixture under the Thomas-Fermi
limit [10, 11, 12]. Experimental observation of spatial separation is also
achieved, but by neglecting the role of mass-imbalance between the isotopes
[5]. The miscible-immiscible transition is shown in the absence of an external
trap, where the transition is governed by the strength of the interspecies
interaction in comparison to the intraspecies interaction [10].

On the other hand, the phase boundary of such transition is also shown to
alter by changing the trap frequency [13, 14, 15]. The external trap, being
the most favourable physical quantity to control the dynamics of a BEC, drives
a quick emergence of various technological applications [16, 17, 18]. A large
amount of literature exists towards the theoretical and experimental studies
of efficient trap engineering in BEC [19, 20, 21, 22, 23, 24, 25]. A ring-
shaped waveguide is one of the most useful traps in $2$D, which is formed by
overlaying a blue-detuned laser in the middle of harmonic confinement [26,
27], where the radius of the ring can be efficiently controlled. BEC inside
such a ring waveguide manifests a number of interesting physics. The
phenomenon of fractional revivals (FR) is recently reported in this system
[28] and is a very well-studied effect in diverse quantum systems in their
time evolutions [29, 30, 31, 32, 33, 34, 35, 36, 37].

In this work, we present a novel technique of isotope separation from the
isotopic mixture of trapped Bose-Einstein condensates. The underlying model
involves the dynamics of an isotopic mixture of a binary BEC inside the ring
trap. The inclusion of interspecies interaction makes the FR-physics more
rigorous and interesting due to the emergence of two time-scales, which are
influenced by each other. We provide a systematic study of the time-evolution
and identify the region of experimental parameters, the trap parameters and
the interspecies interaction strength, for which the isotopes of Rubidium,
${}^{85}Rb$ and ${}^{87}Rb$, will get spatially resolved. Employing FR of
mixed BEC in a ring waveguide to spatially separate its isotopes will be the
first-of-its-kind technique.

The paper is organized as follows. The next section deals with the model of
interacting BEC mixture in a ring trap, along with the numerical technique to
be adopted. Section III includes a detailed analysis of the combined dynamics
through a modified FR phenomenon, where the influence of interspecies
interaction on the individual time scales becomes apparent. A range of
interspecies interactions is proposed in Sec.IV, which later suggests physical
situations for isotope separation through autocorrelation function. In Sec.V,
we quantify the degree of isotope separation at different time instances and
identify the favourable situations for greater isotopic yields in experiments.
A precise parameter domain is also revealed for ring radius and interspecies
interaction. Visualization of condensate densities at the identified instances
clearly manifests the spatial separation of the isotopes, which validates our
model for practical applications. The paper concludes in Sec.VI with a summary
and possible implications.

##  2 Basic Formulation of the System and the Method

We describe the method for the isotopic mixture of ${}^{85}Rb$ and ${}^{87}Rb$
BECs, having atomic masses $m_{1}$ and $m_{2}$, number of atoms $N_{1}$ and
$N_{2}$, respectively. Both the components have their respective intra-species
scattering lengths, $a_{11}$ and $a_{22}$, whereas inter-species coupling is
governed by the scattering length $a_{12}$ and is tuned to the desired values
through the inter-species Feshbach resonance [38, 39, 40, 41, 42]. The
dynamics of a two-component BEC in a ring trap is described by the three-
dimensional (3D) mean-field Gross Pitaevskii Equation (GPE), which is made
dimensionless by scaling the position, time, and energy by $a_{\perp}$,
$1/\omega_{\perp}$ and ${\hbar\omega_{\perp}}$, respectively. Here,
$a_{\perp}=a_{1,\perp}=\sqrt{\hbar/2m_{1}\omega_{\perp}}$ is the harmonic
oscillator length in the transverse direction when the ring trap is created in
the $x$-$y$ plane. $\omega_{\perp}$ is taken as $\omega_{1,z}$, the trap
frequency as experienced by ${}^{85}Rb$ in $z$-direction. All the physical
quantities are chosen as per the experiment [5, 39]: $N_{1}=N_{2}=10^{3}$;
$m_{1}=85\;$a.u., $m_{2}=87\;$a.u., $\omega_{\perp}=2\pi\times 130\;$Hz,
$a_{\perp}=0.675\mu$m; $a_{11}=a_{22}=2.698\times 10^{-9}\;$m; and the radial
frequencies, $\omega_{r}=\omega_{1,r}=\omega_{2,r}$ [5]. The GPE is written
after dimensional reduction to quasi-2D as follows [43, 44, 45].

$i\frac{\partial\psi_{i}}{\partial t}=[\mathcal{L}+\mathcal{N}]\psi_{i},$ (1)

where $\psi_{i}\equiv\psi_{i}(x,y,t)$ and
$\mathcal{L}=-{\frac{m_{1}}{2m_{i}}\nabla_{x,y}}^{2}$ with
$\nabla_{x,y}^{2}=\frac{\partial^{2}}{\partial
x^{2}}+\frac{\partial^{2}}{\partial y^{2}}$. The second term,
$\mathcal{N}=\sum_{j=1}^{2}g_{ij}|\psi_{j}|^{2}+V_{i}(x,y)$, contains the
tunable quantities, such as the couplings,
$g_{ij}=\frac{\sqrt{2\pi\lambda}(m_{1}+m_{2})a_{ij}N_{j}}{m_{2}a_{\perp}}$ and
the ring trap,

$V_{i}(x,y)=\frac{1}{4}\rho_{i}\omega^{2}(x^{2}+y^{2})+V_{0}e^{-\frac{2(x^{2}+y^{2})}{\sigma^{2}}},$
(2)

which is a combination of a 2D harmonic potential and a Gaussian potential.
Here $\rho_{i}=m_{i}/m_{1}$, $\omega=\omega_{r}/\omega_{\perp}$. $\sigma$ and
$V_{0}$ are the waist and amplitude of the Gaussian spike, respectively. The
oscillations along the radial direction are suppressed by placing the
condensate in the exact minimum ($r_{0}$) of the potential [46].

Numerical Method: We adopt the Split Step Fourier Method (SSFM) [47, 48, 49]
for numerically solving the system, where both the parts of the dynamical
equation (Eq.1) are treated separately. The first term is evolved in the
momentum space, and the second term, involving the nonlinearity and the trap,
is evolved in the coordinate space [47]. The $x$\- and $y$-coordinates are
equally divided into $512$ grids with a step size of $0.1841$. The step size
for time is $0.0915$ with a total of $16384$ grids up to the second revival
time.

Figure 1: (a) The density of the BEC mixture of ${}^{85}Rb$ and ${}^{87}Rb$
with interspecies interaction strength $a_{12}=1.0\;a_{11}$, at the quarter
revival time, $t=T_{R}/4$. The densities of the two isotopes are shown
separately in (b) and (c). The autocorrelation functions of the two
interacting species are shown in (d). The ring radius is taken as
$r_{0}=12a_{\perp}$. $x$ and $y$ are in the units of $a_{\perp}=0.675\;\mu$m
and, $t$ is in the units of $1/\omega_{\perp}=1.224\;$ms.

##  3 Dynamics of the Condensate Mixture

We consider that the condensates of the two isotopes initially coexist in the
form of a binary peak with waist, $d_{0}=0.75\;a_{\perp}$, and at the
diametrically opposite points of the ring with coordinates, $(\pm r_{0},0)$.
The mixed cloud disperses along the ring waveguide in clockwise and anti-
clockwise directions. They will start interfering at $(0,\pm r_{0})$, and also
continue to spread further.

It is important to note that a single component BEC (not the system under
study) in a ring trap, after some specific time interval, revives in its
initial position and shape. The time when the condensate replicates the
initial configuration is termed the revival time, $T_{R}$. This revival
phenomenon has been thoroughly examined recently, where the exact revival time
is given by $T_{R}=\pi r_{0}^{2}$ [28]. Moreover, at some specific fractions
of this revival time ($t=T_{R}\times p/q$), several mini replicas of the
initial condensate are formed, and this phenomenon is known as fractional
revivals (FR), where $p$ and $q$ are mutually prime integers and decide the
number of splits [28]. According to the model, at time $\frac{T_{R}}{4}$
($p=1$, $q=4$), a single initial cloud will split into two, and a dual initial
cloud will split into four daughter condensates. Moreover, two components of a
binary BEC with no interspecies interaction will independently show FR and
follow the above model, which is not the case for an isotopic mixture of BECs
where interspecies interactions are considered.

To display the resultant cloud of the isotopic mixture in the presence of
interspecies interactions, we choose a FR time as $T_{R}/4$ and the condensate
is delineated in Fig. 1(a). It is apparent that the condensates of both the
isotopes are mixed in a nontrivial manner due to their coexistence. This
becomes further clarified when the condensate densities of ${}^{85}Rb$ and
${}^{87}Rb$ are shown separately in Fig.1(b) and 1(c), respectively. These
densities look identical and not distinct, resulting in a miscible cloud, as
shown in Fig. 1(a). To separate two constituent clouds of the interacting
isotopes, we need to unwind the physics of miscibility and then try to devise
a way. The well-known autocorrelation (AC) function helps us in the first
stage. AC is the modulus square of the inner product of the initial and the
temporally evolved wavefunctions, having mathematical definition as

$|A(t)|^{2}={|\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}\psi^{*}(x,y,0)\psi(x,y,t)dxdy|^{2}}.$
(3)

For a dispersing cloud, the AC function decays with time to manifest,
gradually decreasing fidelity with the initial structure. However, the
existence of significantly dominant peaks have different physics and are also
observed in Fig.1(d) for the mixed cloud in Fig. 1(a). Periodic AC peaks with
nearly one magnitude are the signature of revivals, whereas there are other
periodic peaks of lower magnitudes, which are known as FR instances. Overall,
the AC time-series provides us with comparable characteristic time scales for
both the isotopic condensates in the presence of interspecies interactions,
due to which the components remain indistinguishable.

Therefore, Fig.1(a) to Fig.1(d) suggest designing a physical situation when AC
peaks will get separated in time during some FR instances to distinguish and
measure two isotopic condensates from their mixture. The key physical
parameters to control the dynamics are the radius of the ring trap ($r_{0}$),
interspecies interaction ($a_{12}$) and time. It is clear from Fig.1 that the
interspecies interaction, $a_{12}=1.0\;a_{11}$, and ring radius,
$r_{0}=12a_{\perp}$, do not help in isotope separation during the whole
temporal dynamics. Below, we will explore the influence of interspecies
interaction on the individual revival dynamics of the isotopes.

###  3.1 Revival Dynamics of the Mixture without and with Interspecies
Interactions

For a two-component BEC, we have two-time scales, one for each component.
First, we will discuss about the expression for revival times of the two
species at zero interspecies interaction. It is known that an initial Gaussian
wave packet of two isotopes with width $w_{i,1}=w_{i,2}=w_{i}$, centred at
$(r_{0},0)$, propagates along the ring and interferes with itself at
$(-r_{0},0)$. The resulting interference maxima of the two species are
proportional to the oscillating terms in their density [43] and are given by

$\displaystyle
I_{max,1}\propto\cos{\Bigg{(}\frac{2Dtd}{w_{i}^{2}w_{t,1}^{2}}\Bigg{)}},$
$\displaystyle
I_{max,2}\propto\cos{\Bigg{(}\frac{2m_{1}Dtd}{m_{2}w_{i}^{2}w_{t,2}^{2}}\Bigg{)}},$
(4)

where $I_{max,1}$ and $I_{max,2}$ are the interference maxima of ${}^{85}Rb$
and ${}^{87}Rb$, respectively. The condensates are initially separated by
distance $D$ at position $d$ and with width $w_{i}$. $w_{t,1}$ and $w_{t,2}$
are their widths at a later time $t$. These widths are related by

$\displaystyle w_{t,1}=\sqrt{w_{i}^{2}+\Bigg{(}\frac{2t}{w_{i}}\Bigg{)}^{2}},$
$\displaystyle
w_{t,2}=\sqrt{w_{i}^{2}+\Bigg{(}\frac{2m_{1}t}{m_{2}w_{i}}\Bigg{)}^{2}},$ (5)

respectively. The difference in the interference maxima is brought out due to
the difference in the revival times of the isotopes. Hence, we have different
effective fringe separations for the two species:

$\Delta d^{\prime}_{1}=\frac{4\pi t}{D},\;\;\Delta d^{\prime}_{2}=\frac{4\pi
m_{1}t}{m_{2}D}.$

At revival times, the fringe separation becomes $2\pi r_{0}\times p$ due to
the circular geometry of the ring, where $p$ denotes the winding number. Since
the initial separation $D$ between the wave packets is $2\pi r_{0}$, the
revival time for ${}^{85}Rb$ and ${}^{87}Rb$ are obtained as,

$\displaystyle T_{R,1}=\pi r_{0}^{2}\times p,$ $\displaystyle
T_{R,2}=\frac{m_{2}}{m_{1}}\pi r_{0}^{2}\times p.$ (6)

The difference of the revival times of ${}^{85}Rb$ and ${}^{87}Rb$ in the
absence of interspecies interaction becomes

$\Delta T_{R}=\Bigg{(}\frac{m_{2}}{m_{1}}-1\Bigg{)}\pi r_{0}^{2}.$ (7)

It is clear from the above equation that the difference in the revival time
scales for two noninteracting isotopes is merely due to the mass-imbalance of
the two species. The solid line with squares in Fig. 2 shows $\Delta T_{R}$
with the radius of the ring in the absence of interspecies interaction. This
variation is quite straightforward from the above analytical expression.
However, the presence of interspecies interaction makes the variation quite
nontrivial, and it doesn’t follow Eq.7. In this case, $\Delta T_{R}$ is
plotted after numerically solving the dynamical equation and by finding the
revival times for an interacting mixture, as depicted by the dotted lines with
circles and triangles in Fig. 2 for two nonzero interactions,
$a_{12}=0.5a_{11}$ and $a_{12}=1.0a_{11}$, respectively. The difference in the
time scales of the mixed constituents is not significant enough without
offering us quite a favourable situation for separating the isotopes. This
also explains why we didn’t have separation for $a_{12}=1.0\;a_{11}$ in fig.1.
The important points from Fig. 2 are i) the nonuniform time scale variation
with the ring radius and ii) the possibility of influencing the time scale
variation with respect to the different interspecies interaction strengths.

Figure 2: Difference in the revival times of the two isotopes $\Delta T_{R}$,
for various radii are shown. The solid line with squares is in the absence of
interspecies interaction, whereas the dotted line with circles and triangles
is in the presence of interspecies interaction $a_{12}=0.5a_{11}$ and
$a_{12}=1.0a_{11}$, respectively. Here, radius $r_{0}$, revival time $T_{R}$,
and interspecies interaction $a_{12}$ are in the units of $a_{\perp}$,
$1/\omega_{\perp}$, and ${a_{11}}$, respectively.

##  4 Identifying Appropriate Interspecies Interaction for Isotope Separation

We have seen that a mixture of isotopes with interspecies interaction doesn’t
follow Eq.[6] and both the isotopes have their revival times altered due to
interaction strength for a given external trap. We evaluate the revival times
of both the species for a wide range of interaction strengths with constant
ring radii and depict them in Fig.(3). A merging of the time scales is
observed at higher interspecies interactions. This behaviour is also seen for
other fractional and revival times of the two species at greater interspecies
interaction. We have shown the merging of timescales for ring radii
$r_{0}=10a_{\perp}$, $r_{0}=12a_{\perp}$ and, $r_{0}=14a_{\perp}$, in the
Fig.3(a), 3(b) and 3(c), respectively.

Figure 3: Variation of revival time for ${}^{85}Rb$ (line with squares) and
${}^{87}Rb$ (line with triangles) with interspecies interaction $a_{12}$, for
fixed ring radii, (a) $r_{0}=10a_{\perp}$, (b) $r_{0}=12a_{\perp}$ and (c)
$r_{0}=14a_{\perp}$. Here, $r_{0}$, $T_{R}$, and $a_{12}$ are in the units of
$a_{\perp}$, $1/\omega_{\perp}$, and ${a_{11}}$, respectively.

The interesting point to gain here is the wide difference in the time scales
of the interacting species for a significant range of interspecies
interaction. Moreover, the greater the radius, the greater the difference in
the revival times at $a_{12}=0$ as shown in Fig.2. This difference in the time
scales is definitely the situation where the mixed condensate cloud should
manifest a separation. The separation of isotopes is not possible for
interspecies interaction strength $a_{12}\gtrsim 0.5a_{11}$, due to
insignificant differences in the revival times of the two species. Therefore,
for separating isotopes, one needs to choose $1)$ an interspecies interaction
strength for which the revival times of the two species are fairly separated
and $2)$ a ring radius for which the difference in the revival times, in the
absence of the interspecies interaction strength, is considerably large.

Figure 4: Autocorrelation function of two initial condensates of a coupled BEC
with interspecies interaction $a_{12}=0.3\;a_{11}$. Fractional revival
instances are indicated by pair notations. The inset shows the autocorrelation
function of the two species at $a_{12}=1.0\;a_{11}$ for comparison. The ring
radius is taken as $r_{0}=12a_{\perp}$ and $t$ is in the unit of
$1/\omega_{\perp}=1.224$ms.

To examine whether such a situation is indeed favourable for separating the
BEC of two miscible isotopes, we choose a set of preferred parameters:
$r_{0}=12a_{\perp}$ and interspecies interaction strength, $a_{12}=0.3a_{11}$.
We repeat the AC function plot with these parameters in Fig. 4 for ${}^{85}Rb$
(solid line) and ${}^{87}Rb$ (dotted line) interacting condensates, where
every peak corresponds to a fractional revival time, and we compare it with
the previous AC function (Fig.1(d)) plot, given in the inset of Fig. 4. AC
peaks are seen to separate, unlike in the previous case. The FR times of both
the species are indicated by the notation, $(t_{1},t_{2})$, such that
$(\frac{3}{4},\frac{3}{4})$ corresponds to $\frac{3}{4}^{th}$ revivals of
both, ${}^{85}Rb$ and ${}^{87}Rb$. The spacing of the peaks increases with
time, thereby making it possible to identify time instances where the
difference in the AC functions of the two species is maximum. As discussed
earlier, the greater the difference in the two AC functions, the lesser the
spatial overlap between two isotopes. Two condensate wavefunctions will become
distinguished or separately measured when the pair of peaks are separated from
each other. In other words, the maximum of one AC peak should coincide with
the minimum of the other AC peak. This, being a dynamical system, such typical
situation has to be maintained for separation. The pair of peaks $(1,1)$ is
one such instance. Hence, our methodology is indeed helpful in choosing the
optimal values of $r_{0}$ and $a_{12}$ for which the isotope separation is
possible.

##  5 Separability of the Isotopes

From the autocorrelation functions of the two species, one could notice the
separation of the isotopes. However, it requires careful analysis of how much
they are separated and at what times for efficient implementation of the
isotope separation scheme. To obtain the degree of separation, we define a
quantity called ’Separability ($S$)’ between the two isotopes in the mixed
BEC:

Figure 5: Variation of the isotope Separability with Time. The prominent
separability peaks are indicated, such as $S_{\frac{1}{2}}$ denotes the time
near the $1/2$-th fractional revival of ${}^{87}Rb$. The interspecies
interaction is taken as $a_{12}=0.3a_{11}$ and the ring radius is
$r_{0}=12a_{\perp}$. $t$ is in the unit of $1/\omega_{\perp}=1.224\;$ms.

$\displaystyle\begin{aligned} &S=1-\Delta,\\\
&\Delta=\frac{[\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}|\psi_{1}(x,y)|^{2}|\psi_{2}(x,y)|^{2}dxdy]^{2}}{\int_{-\infty}^{\infty}|\psi_{1}(x,y)|^{4}dxdy\int_{-\infty}^{\infty}|\psi_{2}(x,y)|^{4}dxdy}.\end{aligned}$
(8)

The term, $\Delta$, is given by the square of the inner product of the
probability densities of ${}^{85}Rb$ and ${}^{87}Rb$, weighted by the product
of $4^{th}$ order moment of the inner product. The numerator helps in
amplifying the tiny variations in the overlap of the wavefunctions of two
species. The separability takes the value from $0$ to $1$, where $0$ implies
zero separation and $1$ corresponds to a $100\%$ separation. We choose the
parameters of Fig. 4 for calculating $S$ and presented in Fig. 5. A
separability peak close to $1$ will be the desired situation. For times up to
$1000$ in the unit of $\frac{1}{\omega_{\perp}}$, we could find four prominent
peaks, $S_{\frac{1}{2}}$, $S_{1}$, $S_{\frac{3}{2}}$ and $S_{2}$, occurring
closer to $\frac{1}{2}$, $1$, $\frac{3}{2}$ and $2$ of the revival time of
${}^{87}Rb$. At these times, the separation of the isotopes is maximum, i.e.,
$S\approx 1$, compared to the other times.

The times corresponding to $S_{\frac{1}{2}}$, $S_{1}$, $S_{\frac{3}{2}}$ and
$S_{2}$ are $0.286s,\;$$0.575s,\;$$0.855s$ and, $1.138s$, respectively. At
these times, the condensate densities of the two species have $>95\%$
separation. The exact values of the percentage of separation of the two
isotopes for the above Separability peaks are given in Table.1.

Peak |  $S_{\frac{1}{2}}$ |  $S_{1}$ |  $S_{\frac{3}{2}}$ |  $S_{2}$
---|---|---|---|---
Time (s) | 0.286 | 0.575 | 0.855 | 1.138
Separability | 95.7$\%$ | 98.9$\%$ | 98.7$\%$ | 94.5$\%$
Table 1: Percentage of separation of the two isotopes for the four
Separability peaks and their corresponding times from Fig. 5. The interspecies
interaction is taken as $a_{12}=0.3a_{11}$ and the ring radius is
$r_{0}=12a_{\perp}$.

In addition, a more favourable instance will be relying on the following
factors too: $1)$ at higher evolution time, one could observe an overall decay
of the autocorrelation function (Fig.4) due to dispersion and hence, sooner is
better for isotope separation; $2)$ a broader temporal width of the
separability peak is preferable, as it will provide better time window in
which the isotopes remains separated in the experiment.

Parameter Contours for Maximal Isotope Separation: In our work, the
separability of the isotopes is tuned by two physical parameters, the radius
of the ring $r_{0}$ and the interspecies interaction $a_{12}$. The
separability peaks in Fig. 5 offers the times for maximal isotope separations,
designated by $S_{\frac{1}{2}}$, $S_{1}$, $S_{\frac{3}{2}}$ and $S_{2}$ and
having $>95\%$ isotope yields. The exact values of the percentage of
separation are given in Table.1. These, along with the above points ($1$ and
$2$), suggest one of the most favourable instances as $S_{1}$ with a wider
separability peak and $98.9\%$ yield. We identify the parameter contours,
comprising of $r_{0}$ and $a_{12}$, for the instance, $S_{1}$, and depict it
in Fig. 6.

Figure 6: The preferred parameter regions for isotope separation in
experiments, following the Separability, $S_{1}$, as an example. The
interspecies interaction $a_{12}$ and ring radius $r_{0}$ can be chosen as per
the need, where the white dotted line indicates the maximum separability. We
also draw the regions for various percentage yields, $90\%,\;95\%$ and $98\%$,
by dashed contours. The ring radius is in the unit of $a_{\perp}=0.675\;\mu$m,
and the interspecies interaction is in the unit of $a_{11}=2.698\times
10^{-9}\;$m.

The diagram highlights the regions above $90{\%}$ separability. Though the
whole highlighted region provides a wide parameter range for isotope
separation, one can further improve it by choosing greater yields, as shown by
different contours. The white dotted line in the middle indicates the maximum
separability value for both parameters. It is interesting to note that the
maximum separability line lies within the window $0.2a_{11}>a_{12}>0.4a_{11}$
of interspecies interaction strength. We also draw the regions for various
percentage yields, $90\%,\;95\%$ and $98\%$, by dashed contours. For a desired
separation line, the favourable values for the radius and interspecies
interaction can be chosen in the experiments.

Condensate Densities Upon Isotope Separation: One can visualize the individual
condensate of the isotopes for any set of parameters, described in the
parameter contour plot in Fig. 6 to verify their spatial separation. Here, we
will choose one of the values, such as the interspecies interaction is
$a_{12}=0.3a_{11}$ and the ring trap radius is taken as $r_{0}=12a_{\perp}$ in
Fig. 7. Condensate densities of both the isotopes, ${}^{85}Rb$ and
${}^{87}Rb$, separately plotted at times, $0.286\;$s, $0.575\;$s, $0.855\;$s,
and $1.138\;$s, corresponding to $S_{\frac{1}{2}}$, $S_{1}$, $S_{\frac{3}{2}}$
and $S_{2}$, respectively. These instances, near multiples of half revival, do
not further split the initially considered dual clouds and, hence, show nice
separation in the preferred parameter window. At $S_{\frac{1}{2}}$, the
isotopes are separated with respect to their common centre of mass and remain
separated for a shorter time interval, as reflected from the narrow width of
the separability peak for $S_{\frac{1}{2}}$ in Fig. 5. It is fascinating to
observe that each of the other pairs of plots for ${}^{85}Rb$ and ${}^{87}Rb$
condensates in Fig. 7 manifests orthogonal positioning with respect to each
other, implying a clear isotope separation inside the ring trap.

Figure 7: Condensate densities of both the isotopes, ${}^{85}Rb$ and
${}^{87}Rb$, separately plotted at times, $0.286\;$s, $0.575\;$s, $0.855\;$s,
and $1.138\;$s, corresponding to $S_{\frac{1}{2}}$, $S_{1}$, $S_{\frac{3}{2}}$
and $S_{2}$, respectively. Spatial coordinates are in the units of
$a_{\perp}=0.675\;\mu$m,. The interspecies interaction is taken as
$a_{12}=0.3a_{11}$, the ring radius is $r_{0}=12a_{\perp}$ and time is in the
unit of $1/\omega_{\perp}=1.224\;$ms.

##  6 Conclusion

We have reported a method to separate isotopes from a mixed-binary BEC of $Rb$
isotopes, which is made to evolve along a ring waveguide. The difference in
the fractional revival time scales of the two interacting isotopes is employed
in spatially separating them. We have quantified the degree of spatial
separation of isotopes by a quantity called Separability. The plot of
separability and time gives us specific times when there is a maximum
separation of isotopes. The times corresponding to $S_{\frac{1}{2}}$, $S_{1}$,
$S_{\frac{3}{2}}$ and $S_{2}$ are identified, where the condensate densities
of the two species have $>95\%$ separation. The percentage of separation is
addressed up to $\sim 99\%$, which is higher than the previously reported
isotope separation methods [4, 50] by using the LIDIS technique [4, 51, 52,
53]. The physically supported parameter contours offered a wide range of trap
and cross-interaction values under the present scheme. The domain of
interspecies interaction strength is unique ($a_{12}<a_{11}$) in the context
of high fidelity spatial separation of isotopes in comparison to the past
works [8, 6, 9].

## References

  *   * De Groot [2009] De Groot, P.A.: Chapter 20 - Isotope separation methods, Handbook of stable isotope analytical techniques, 1025–1032 (2009)
  * Hosoe et al. [1988] Hosoe, M., Oi, T., Kawada, K., Kakihana, H.: Separation of rubidium isotopes by ion-exchange chromatography. Journal of Chromatography A 435, 253–255 (1988)
  * Streater et al. [1987] Streater, A., Mooibroek, J., Woerdman, J.: Light-induced drift in rubidium: spectral dependence and isotope separation. Optics communications 64(2), 137–143 (1987)
  * Streater et al. [1988] Streater, A., Mooibroek, J., Woerdman, J.: Enhanced efficiency in separation of rb isotopes by light-induced drift with the use of a diode laser with relaxation sidebands. Applied physics letters 52(8), 602–604 (1988)
  * Papp et al. [2008] Papp, S., Pino, J., Wieman, C.: Tunable miscibility in a dual-species bose-einstein condensate. Physical review letters 101(4), 040402 (2008)
  * Wen et al. [2020] Wen, L., Guo, H., Wang, Y.-J., Hu, A.-Y., Saito, H., Dai, C.-Q., Zhang, X.-F.: Effects of atom numbers on the miscibility-immiscibility transition of a binary bose-einstein condensate. Physical Review A 101(3), 033610 (2020)
  * Kumar et al. [2017] Kumar, R.K., Tomio, L., Malomed, B.A., Gammal, A.: Vortex lattices in binary bose-einstein condensates with dipole-dipole interactions. Physical Review A 96(6), 063624 (2017)
  * Wen et al. [2012] Wen, L., Liu, W.-M., Cai, Y., Zhang, J., Hu, J.: Controlling phase separation of a two-component bose-einstein condensate by confinement. Physical Review A 85(4), 043602 (2012)
  * Cikojević et al. [2018] Cikojević, V., Markić, L.V., Boronat, J.: Harmonically trapped bose–bose mixtures: a quantum monte carlo study. New Journal of Physics 20(8), 085002 (2018)
  * Ao and Chui [1998] Ao, P., Chui, S.: Binary bose-einstein condensate mixtures in weakly and strongly segregated phases. Physical Review A 58(6), 4836 (1998)
  * Riboli and Modugno [2002] Riboli, F., Modugno, M.: Topology of the ground state of two interacting bose-einstein condensates. Physical Review A 65(6), 063614 (2002)
  * Jezek and Capuzzi [2002] Jezek, D., Capuzzi, P.: Interaction-driven effects on two-component bose-einstein condensates. Physical Review A 66(1), 015602 (2002)
  * Navarro et al. [2009] Navarro, R., Carretero-González, R., Kevrekidis, P.: Phase separation and dynamics of two-component bose-einstein condensates. Physical Review A 80(2), 023613 (2009)
  * Merhasin et al. [2005] Merhasin, I.M., Malomed, B.A., Driben, R.: Transition to miscibility in a binary bose–einstein condensate induced by linear coupling. Journal of Physics B: Atomic, Molecular and Optical Physics 38(7), 877 (2005)
  * Sabbatini et al. [2011] Sabbatini, J., Zurek, W.H., Davis, M.J.: Phase separation and pattern formation in a binary bose-einstein condensate. Physical review letters 107(23), 230402 (2011)
  * Bloch et al. [2012] Bloch, I., Dalibard, J., Nascimbene, S.: Quantum simulations with ultracold quantum gases. Nature Physics 8(4), 267–276 (2012)
  * Ryu and Boshier [2015] Ryu, C., Boshier, M.G.: Integrated coherent matter wave circuits. New Journal of Physics 17(9), 092002 (2015)
  * Gajdacz et al. [2014] Gajdacz, M., Opatrnỳ, T., Das, K.K.: An atomtronics transistor for quantum gates. Physics Letters A 378(28-29), 1919–1924 (2014)
  * Lesanovsky and von Klitzing [2007] Lesanovsky, I., Klitzing, W.: Time-averaged adiabatic potentials: versatile matter-wave guides and atom traps. Physical Review Letters 99(8), 083001 (2007)
  * Henderson et al. [2009] Henderson, K., Ryu, C., MacCormick, C., Boshier, M.: Experimental demonstration of painting arbitrary and dynamic potentials for bose-einstein condensates. New Journal of Physics 11(4), 043030 (2009)
  * Nath and Roy [2014] Nath, A., Roy, U.: Bose–einstein condensate in a bichromatic optical lattice: an exact analytical model. Laser Physics Letters 11(11), 115501 (2014)
  * Raghav et al. [2022] Raghav, S., Halder, B., Basu, P., Roy, U.: Tunneling and revival of anderson localization in a bose-einstein condensate. Physical Review A 106(6), 063304 (2022)
  * Nath et al. [2020] Nath, A., Bera, J., Ghosh, S., Roy, U.: Exact analytical model for bose-einstein condensate at negative temperature. Scientific Reports 10(1), 9016 (2020)
  * Halder et al. [2021] Halder, B., Ghosh, S., Basu, P., Bera, J., Malomed, B., Roy, U.: Exact solutions for solitary waves in a bose-einstein condensate under the action of a four-color optical lattice. Symmetry 14(1), 49 (2021)
  * Basu et al. [2022] Basu, P., Halder, B., Raghav, S., Roy, U.: Nonlinear excitations in ultracold atoms trapped in triple optical lattices. Condensed Matter 7(3), 52 (2022)
  * Ryu et al. [2007] Ryu, C., Andersen, M., Clade, P., Natarajan, V., Helmerson, K., Phillips, W.D.: Observation of persistent flow of a bose-einstein condensate in a toroidal trap. Physical Review Letters 99(26), 260401 (2007)
  * Naik and Raman [2005] Naik, D., Raman, C.: Optically plugged quadrupole trap for bose-einstein condensates. Physical Review A 71(3), 033617 (2005)
  * Bera et al. [2020] Bera, J., Ghosh, S., Salasnich, L., Roy, U.: Matter-wave fractional revivals in a ring waveguide. Physical Review A 102(6), 063323 (2020)
  * Averbukh and Perelman [1989] Averbukh, I.S., Perelman, N.: Fractional revivals: Universality in the long-term evolution of quantum wave packets beyond the correspondence principle dynamics. Physics Letters A 139(9), 449–453 (1989)
  * Robinett [2004] Robinett, R.W.: Quantum wave packet revivals. Physics reports 392(1-2), 1–119 (2004)
  * Parker and Stroud Jr [1986] Parker, J., Stroud Jr, C.: Coherence and decay of rydberg wave packets. Physical review letters 56(7), 716 (1986)
  * Banerji and Ghosh [2006] Banerji, J., Ghosh, S.: The role of ro-vibrational coupling in the revival dynamics of diatomic molecular wave packets. Journal of Physics B: Atomic, Molecular and Optical Physics 39(5), 1113 (2006)
  * Ghosh et al. [2006] Ghosh, S., Chiruvelli, A., Banerji, J., Panigrahi, P.: Mesoscopic superposition and sub-planck-scale structure in molecular wave packets. Physical Review A 73(1), 013411 (2006)
  * Ghosh et al. [2009] Ghosh, S., Roy, U., Genes, C., Vitali, D.: Sub-planck-scale structures in a vibrating molecule in the presence of decoherence. Physical Review A 79(5), 052104 (2009)
  * Roy et al. [2009] Roy, U., Ghosh, S., Panigrahi, P.K., Vitali, D.: Sub-planck-scale structures in the pöschl-teller potential and their sensitivity to perturbations. Physical Review A 80(5), 052115 (2009)
  * Ghosh [2012] Ghosh, S.: Coherent control of mesoscopic superpositions in a diatomic molecule. International Journal of Quantum Information 10(02), 1250014 (2012)
  * Ghosh and Roy [2014] Ghosh, S., Roy, U.: Enhanced quantum sensitivity in a vibrating diatomic molecule due to a rotational amendment. Physical Review A 90(2), 022113 (2014)
  * Burke Jr et al. [1998] Burke Jr, J.P., Bohn, J.L., Esry, B., Greene, C.H.: Prospects for mixed-isotope bose-einstein condensates in rubidium. Physical review letters 80(10), 2097 (1998)
  * Papp and Wieman [2006] Papp, S.B., Wieman, C.E.: Observation of heteronuclear feshbach molecules from a ${}^{85}{R}b$–${}^{87}{R}b$ gas. Physical Review Letters 97(18), 180404 (2006)
  * Dong et al. [2016] Dong, S., Cui, Y., Shen, C., Wu, Y., Tey, M.K., You, L., Gao, B.: Observation of broad p-wave feshbach resonances in ultracold rb 85- rb 87 mixtures. Physical Review A 94(6), 062702 (2016)
  * Fukuhara et al. [2009] Fukuhara, T., Sugawa, S., Takasu, Y., Takahashi, Y.: All-optical formation of quantum degenerate mixtures. Physical Review A 79(2), 021601 (2009)
  * Tanzi et al. [2018] Tanzi, L., Cabrera, C., Sanz, J., Cheiney, P., Tomza, M., Tarruell, L.: Feshbach resonances in potassium bose-bose mixtures. Physical Review A 98(6), 062712 (2018)
  * Pethick and Smith [2008] Pethick, C.J., Smith, H.: Bose–einstein condensation in dilute gases (2008)
  * Adhikari [2001] Adhikari, S.K.: Coupled bose-einstein condensate: Collapse for attractive interaction. Physical Review A 63(4), 043611 (2001)
  * Salasnich et al. [2014] Salasnich, L., Cardoso, W.B., Malomed, B.A.: Localized modes in quasi-two-dimensional bose-einstein condensates with spin-orbit and rabi couplings. Physical Review A 90(3), 033629 (2014)
  * Zhang et al. [2017] Zhang, X.-F., Kato, M., Han, W., Zhang, S.-G., Saito, H.: Spin-orbit-coupled bose-einstein condensates held under a toroidal trap. Physical Review A 95(3), 033620 (2017)
  * Weideman and Herbst [1986] Weideman, J., Herbst, B.: Split-step methods for the solution of the nonlinear schrödinger equation. SIAM Journal on Numerical Analysis 23(3), 485–507 (1986)
  * Taha and Xu [2005] Taha, T.R., Xu, X.: Parallel split-step fourier methods for the coupled nonlinear schrödinger type equations. The Journal of Supercomputing 32(1), 5–23 (2005)
  * Wang [2007] Wang, H.: A time-splitting spectral method for coupled gross–pitaevskii equations with applications to rotating bose–einstein condensates. Journal of computational and applied mathematics 205(1), 88–104 (2007)
  * Okamoto et al. [2008] Okamoto, M., Nakamura, T., Sato, S.: Observation of light-induced drift effect of rubidium by using two diode lasers for pumping and re-pumping. Materials transactions 49(11), 2632–2635 (2008)
  * Hradecny et al. [1992] Hradecny, C., Slovak, J., Tethal, T., Yermolayev, I., Shalagin, A.: Radioactive isotope and isomer separation using the light-induced drift effect. International journal of radiation applications and Instrumentation. Part A. Applied radiation and isotopes 43(10), 1259–1264 (1992)
  * Hradecny et al. [1994] Hradecny, C., Tethal, T., Yermolayev, I., Zemlyanoi, S., Zuzaan, P.: Isotope separation of 22na and 24na by using the light-induced drift effect. Applied radiation and isotopes 45(2), 257–260 (1994)
  * Yuki et al. [2017] Yuki, K., Kobayashi, T., Matsuoka, L.: Numerical analysis of highly efficient laser-based method of radioactive cs isotope separation utilizing light-induced drift in d1 and d2 transitions in rare gases. Journal of Nuclear Science and Technology 54(11), 1240–1250 (2017)


# FROCC: Fast Random projection-based One-Class Classification

Arindam Bhattacharya  Sumanth Varambally  Amitabha Bagchi  Srikanta Bedathur

###### Abstract

We present Fast Random projection-based One-Class Classification (FROCC), an
extremely efficient method for one-class classification. Our method is based
on a simple idea of transforming the training data by projecting it onto a set
of random unit vectors that are chosen uniformly and independently from the
unit sphere, and bounding the regions based on separation of the data. FROCC
can be naturally extended with kernels. We provide a new theoretical framework
to prove that that FROCC generalizes well in the sense that it is stable and
has low bias for some parameter settings. FROCC achieves up to 3.1 percent
points better AUC ROC, with 1.2–67.8$\times$ speedup in training and test
times over a range of state-of-the-art benchmarks including the SVM and the
deep learning based models for the OCC task.

##  1 Introduction

One-class classification (OCC) has attracted a lot of attention over the years
under various names such as novelty detection [30], anomaly or outlier
detection [34, 29], concept learning [15], and so on. Unlike the classical
binary (or multi-class) classification problem, the problem addressed in OCC
is much simpler: to simply identify all instances of a class by using only a
(small) set of examples from that class. Therefore it is applicable in
settings where only “normal” data is known at training time, and the model is
expected to accurately describe this normal data. After training, any data
which deviates from this normality is treated as an anomaly or a novel item.
Real-world applications include intrusion detection [11, 5], medical diagnoses
[14], fraud detection [37], etc., where the requirement is to offer not only
high precision, but also the ability to scale training and testing time as the
volume of (training) data increases.

Primary approaches to OCC include one-class variants of support vector
machines (SVM) [30], probabilistic density estimators describing the support
of normal class [6, 27], and recently, deep-learning based methods such as
auto-encoders (AE) and Generative Adversarial Networks (GAN) which try to
learn the distribution of normal data samples during training [29, 24, 28].
However, almost all of these methods are either extremely slow to train or
require significant hyper-parameter tuning or both.

We present an alternative approach based on the idea of using a collection of
random projections onto a number of randomly chosen 1-dimensional subspaces
(vectors) resulting in a simple yet surprisingly powerful one-class
classifier. Random projections down to a single dimension or to a small number
of dimensions have been used in the past to speed up approximate nearest
neighbor search [17, 2, 13] and other problems that rely on the distance-
preserving property guaranteed by the Johnson-Lindenstrauss Lemma but our
problem space is different. We use random projections in an entirely novel
fashion based on the following key insight: for the one-class classification
problem, the preservation of distances is _not_ important, we only require the
class boundary to be preserved. The preservation of distances is a stronger
property which implies that the class boundary is preserved, but the converse
need not hold. We don’t need to preserve distances. All we need to do is
“view” the training data from a “direction” that shows that the outlier is
separated from the data.

Formalizing this intuition, we develop an algorithm for one-class
classification called FROCC (Fast Random projection-based One-Class
Classification) that essentially applies a simplified envelope method to
random projections of training data to provide very strong classifier. FROCC
also comes with a theoretically provable generalization property: the method
is stable and has low bias.

At a high level, FROCC works as follows: given only positively labelled data
points, we select a set of random vectors from the unit sphere, and project
all the training data points onto these random vectors. We compactly represent
all the training data projections along each vector using one (or more)
intervals, based on the separation parameter $\varepsilon$. If a test data
point’s projection with the random vector is within the interval spanned by
all the training data projections, we say it is part of the normal class,
otherwise it is an outlier. The parameter $\varepsilon$ breaks the single
interval used to represent the random vector projection into _dense_ clusters
with a density lower-bound $\frac{1}{\varepsilon}$, resulting in a collection
of intervals along each vector.

The simplicity of the proposed model provides us with a massive advantage in
terms of computational cost – during both training and testing – over all the
existing methods ranging from SVMs to deep neural network models. We achieve
1–16$\times$ speedup for non-deep baselines like One Class SVM (OCSVM) [30]
and Isolation forests. For state-of-the-art deep learning based approaches
like Deep-SVDD and Auto Encoder we achieve a speedup to the tune of 45$\times$
– 68$\times$. At the same time, the average area under the ROC curve is 0.3 —
3.1 percent points _better than_ the state-of-the-art baseline methods on six
of the eleven benchmark datasets we used in our empirical study.

Like SVM our methods can be seamlessly extended to use kernels. These
extensions can take advantage of kernels that may be suitable for certain data
distributions, without changing the overall one-class decision framework of
FROCC.

Multi-modal Gaussian Data
---
ROC = 0.816 | ROC = 0.824 | ROC = 0.968 | ROC = 0.836
|  |  |
Moon Data
ROC = 0.734 | ROC = 0.783 | ROC = 0.823 | ROC = 0.911
|  |  |
(a) $\varepsilon=1,K=linear$ |  (b) $\varepsilon=1,K=rbf$ |  (c) $\varepsilon=0.1,K=linear$ |  (d) $\varepsilon=0.1,K=rbf$

Figure 1: Classification boundaries for different variants of FROCC. Blue-
colored points are the “normal” class.

To understand the power of our method consider the one-class decision
boundaries for various methods on two toy datasets visualized in Figure 1. We
see that FROCC with $\varepsilon=0.1$ computes a very desirable decision
boundary for Multi-modal Gaussian data, a case which is known to be difficult
for SVM to handle. In this case incorporating a standard Gaussian RBF kernel
doesn’t improve the ROC for FROCC. In the case of the Moon-shaped data,
however, this kernel is able to direct FROCC to better decision boundaries
which reflect in better ROC scores.

Through a range of experiments we show that the in most cases FROCC is able to
achieve high scores in ROC as well as Precision@n measures with 2–3 orders of
improvement in speed.

##### Our contributions.

  * •

We define a powerful and efficient random-projection based one class
classifier: FROCC.

  * •

We show theoretically that FROCC is a stable classification algorithm.

  * •

We perform an extensive experimental evaluation on several data sets that
shows that our methods outperform traditional methods in both quality of
results and speed, and that our methods are comparable in quality to recent
neural methods while outperforming them in terms of speed by three orders of
magnitude.

##### Organization.

We discuss related literature in Sec. 2. Formal definitions of our methods are
presented in Sec. 3. In Section 4 we provide analysis of stability of our
methods. The experiments setup and results of an extensive experimental
comparison with several baselines are discussed in Sec. 5. We make some
concluding remarks in Sec. 6.

##  2 Related Work

##### One Class Classification.

One class classification has been studied extensively so we don’t attempt to
survey the literature in full detail, referring the reader instead to the
survey of traditional methods by [16]. A more recent development is the
application of deep learning-based methods to this problem. A partial survey
of these methods is available in [28].

Unlike deep learning-based methods our work takes a more traditional geometric
view of the one class problem in a manner similar to [34] and [30] but we do
not rely on optimization as a subroutine like their methods do. This gives us
an efficiency benefit over these methods in addition to the improvement we get
in terms of quality of results. An additional efficiency advantage our FROCC
methods have is that we do not need to preprocess to re-center the data like
these two methods do.

Our methods operate in the paradigm where the training data consists of a
fully labeled set of examples only from the normal class. We do not use even a
small number of examples from the negative class as done in, e.g., [3].
Neither does our method use both labeled and unlabelled data as in the PAC
model [35]. Our methods are randomized in nature which put them in the same
category as probabilistic methods that attempts to fit a distribution on the
positive data. One examples of such a method is learning using Parzen window
density estimation [6]. We consider one such method as a baseline: [10] apply
Minimum Co-variance Determinant Estimator [27] to find the region whose co-
variance matrix has the lowest determinant, effectively creating an elliptical
envelope around the positive data.

We also compare our algorithms to deep learning-based methods. Specifically we
compare our methods to the Auto-encoder-based one class classification method
proposed by [29].

Another baseline we compare against is the deep learning extension of Support
Vector Data Description (SVDD) proposed by [28], where a neural network learns
a transformation from input space to a useful space. In both cases our results
are comparable and often better in terms of ROC while achieving a high
speedup.

##### Random Projection-based Algorithms.

Random projection methods have been productive in nearest-neighbor contexts
due to the fact that it is possible to preserve distances between a set of
points if the number of random dimensions chosen is large enough, the so-
called Johnson-Lindenstrauss property, c.f., e.g. locality sensitive hashing
[12, 2]. Our methods do not look to preserve distances, only the boundary,
and, besides, we are not necessarily looking for dimensionality reduction,
which is key goal of the cited methods. A smaller number of projection
dimensions may preserve distances between the training points but it does not
make the task of discriminating outliers any easier. It may be possible that
for the classifier to have good accuracy the dimensionality of the projection
space be higher than the data space. As such our problem space is different
from that of the space of problems that look for dimensionality reduction
through random projection. [17] uses projections to a collection of randomly
chosen vectors to take a simpler approach than locality sensitive hashing but
his problem of interest is also approximate nearest neighbor search. Some
research has also focused on using random projections to learn mixtures of
Gaussians, starting with the work of [7] but again this is a different problem
space.

The closest work to ours in flavor is that of [36] who attempts to find
$k$-half-spaces whose intersection fully contains a given positively labelled
data set. The key difference here is that our methods work with the
intersections of hyper-rectangles that are unbounded in one dimension and not
half-spaces. While the solution in [36] can be a general convex body in the
projection space, ours is specifically limited to cuboids. As such it is not
possible to refine Vempala’s method by taking a parameter $\varepsilon$ and
subdividing intervals (c.f. Section 3), nor is it clear how it could be
regularized for use in real-world applications.

##  3 Fast Random-Projection based OCC

######  Definition 1 (FROCC ($S,m,\varepsilon,K$)).

Assume that we are given a set of training points
$S=\\{\bm{x}_{1},\ldots,\bm{x}_{n}\\}\subseteq\mathbb{R}^{d}$. Then, given an
integer parameter $m>0$, a real parameter $\varepsilon\in(0,1]$ and a kernel
function $K(\cdot,\cdot)$, the $\varepsilon$-separated Fast Random-projection
based One-Class Classifier FROCC $(S,m,\varepsilon,K)$, comprises, for each
$i$, $1\leq i\leq m$,

  1. 1.

A classifying direction $\bm{w}_{i}$ that is a unit vector chosen uniformly at
random from $\bm{1}_{d}$, the set of all unit vectors of $\mathbb{R}^{d}$,
independent of all other classifying directions, and

  2. 2.

a set of intervals $R_{i}$ defined as follows: Let
$S^{\prime}_{i}=\\{K(\bm{w}_{i},\bm{x}_{j}):1\leq j\leq n\\}$ and
$S_{i}=\\{y_{1},\ldots,y_{n}\\}$ is a shifted and scaled version of
$S^{\prime}_{i}$ such that $y_{i}\in(0,1),1\leq i\leq n$. Assume
$y_{1}\leq\cdots\leq y_{n}$. Then each interval of $R_{i}$ has the property
that it is of the form $[y_{j},y_{j+k}]$ for some $j\geq 1,k\geq 0$ such that

    1. (a)

for all $t$ such that $0\leq t<k$, $y_{j+t+1}-y_{j+t}<\varepsilon$,

    2. (b)

$y_{j}-y_{j-1}>\varepsilon$ whenever $j-1>0$, and

    3. (c)

$y_{j+k+1}-y_{j+k}>\varepsilon$ whenever $j+k+1\leq n$.

Given a query point $\bm{y}\in\mathbb{R}^{d}$, FROCC $(S,m,\varepsilon,K)$
returns YES if for every $i$, $1\leq i\leq m$, $K(\bm{w}_{i},\bm{y})$ lies
within some interval of $R_{i}$.

In the simplest setting the kernel function $K(\cdot,\cdot)$ will be just the
usual dot product associated with $\mathbb{R}^{d}$.

Figure 2: The test point $q$ is correctly classified as an outlier by
$\bm{w_{2}}$ using FROCC since the projection lies outside the discriminating
boundaries given by $e$ and $f$. However, $\bm{w_{1}}$ classifies $q$
incorrectly for $\varepsilon>\varepsilon_{d}$, since the discriminating
boundary (blue region) is formed by the intervals $[a,d]$. If we chose
$\varepsilon\leq\varepsilon_{d}$, $\bm{w_{1}}$ correctly classifies $q$, since
the discriminating boundaries (green regions) are given by the intervals
$[a,b]$ and $[c,d]$.

We show a small example in Figure 2. The green points are training points. Two
classifying directions $\bm{w}_{1}$ and $\bm{w}_{2}$ are displayed. The test
point $\bm{q}$ has the property that $\langle\bm{q},\bm{w}_{1}\rangle$ lies in
$[a,d]$ but since $\langle\bm{q},\bm{w}_{2}\rangle$ does not lie in $[e,f]$,
$\bm{q}$ is said to be outside the class. Noting that the projections along
$\bm{w}_{1}$ of the two clusters of the training set are well separated, a
choice of $\varepsilon<\varepsilon_{d}$ leads to splitting of the interval
$[a,d]$ into $[a,b]$ and $[c,d]$, thus correctly classifying $q$ to be an
outlier.

In simple terms the intervals of $R_{i}$ have the property that the points of
$S_{i}$ are densely scattered within each interval and there are wide gaps
between the intervals that are empty of points of $S_{i}$. The density of the
intervals is lower bounded by $1/\varepsilon$ and the width between successive
intervals is lower bounded by $\varepsilon$. If we now look at Figure 2 we
note that since the interval $[b,c]$ has length more than $\varepsilon$,
$R_{1}$ becomes $[a,b]\cup[c,d]$ and so the projection of $\bm{q}$ along
$\bm{w}_{1}$ is also classified as being outside the class.

##### Computing FROCC.

Algorithm 1 outlines the training procedure of FROCC. The function $f$ in Line
1 is any valid kernel, which defaults to inner product
$\langle\cdot,\cdot\rangle$. Algorithm 2 shows how the interval tree is
created for each classification direction. Unlike many optimization based
learning methods, such as neural networks, our algorithm needs a single pass
through the data.

1

Data: $S=\\{\bm{x}_{1},\ldots,\bm{x}_{n}\\}\subseteq\mathbb{R}^{d}$: training
set

input : m, $\varepsilon$

output : $[R_{i}]_{i=1}^{m}$: list of m interval trees

2 Initialize $result\leftarrow$ _empty list_

3 for  _$i\leftarrow 1$ to $m$_ do

4 $\ell_{i}\leftarrow inf$

5 $u_{i}\leftarrow 0$

6 $\bm{w}_{i}\thicksim Uniform(\bm{1}_{d})$ // sample a d-dimensional unit
vector uniformly

7 Initialize projectionList $\leftarrow$ _empty list_

8 for  _$j\leftarrow 1$ to $n$_ do

9 $projection\leftarrow f(x_{j},w_{i})$

10 projectionList.append(projection)

11

12 end for

13 sort(projectionList)

14 $R_{i}\leftarrow$ _IntervalTree(projectionList, $\varepsilon$)_

15 result.append($R_{i}$)

16 end for

Algorithm 1 FROCC Training

1

input : projectionList, $\varepsilon$

output : R: interval tree

2 Initialize $R\leftarrow$ _empty interval tree_

3 Initialize $start\leftarrow projectionList[1]$, $end\leftarrow
projectionList[1]$

4 margin = $(\max(projectionList)-\min(projectionList))\cdot\varepsilon$

5 for  _$i\leftarrow 2$ to $n$_ do

6 if  _$projectionList[i] <end+margin$_ then

7 $end\leftarrow projectionList[i]$

8

9 else

10 // point is outside margin

11 R.insert([start, end])

12 $start\leftarrow projectionList[i]$

13 $end\leftarrow projectionList[i]$

14

15 end if

16

17 end for

18if  _$start\neq end$_ then

19 // handle last interval

20 R.insert([start, end])

21 end if

Algorithm 2 IntervalTree subroutine for $\varepsilon\in(0,1)$

The standard method for choosing uniformly random vectors in $\mathbb{R}^{d}$
is to sample from a spherical $d$-dimensional Gaussian centered at the origin
and then normalizing it so that its length is 1. Folklore and a quick
calculation suggests that independently picking $d$ random variables with
distribution $N(0,1)$ is good enough for this purpose. The spherical symmetry
of the Gaussian distribution ensures that the random vector is uniformly
picked from all possible directions.

##### Time complexity.

The time taken to compute the boundaries of the $FROCC$ is $O(mnd)$ for
$\varepsilon=1$ (assuming the kernel is dot product, which takes $O(d)$). For
$\varepsilon<1$ additional factor of $\theta(mn\log n)$ is required to create
$\varepsilon$-separated intervals along each classifying direction.

##  4 Theoretical Analysis

In this section we state and prove certain properties of FROCC which states
that FROCC is a stable classifier whose performance can be reliably tweaked by
modifying the number of classification dimensions $m$ and separation parameter
$\varepsilon$. In particular, we show that:

  1. 1.

Bias of FROCC decreases exponentially with the size of the training set if the
training set is drawn from a spatially divisible distribution,

  2. 2.

Precision and model size of FROCC increase monotonically with $m$ and decrease
monotonically with $\varepsilon$, and

  3. 3.

Probability of FROCC making an error decays exponentially with $m$.

###  4.1 Stability of FROCC

Following the analysis of [4] we prove that FROCC generalizes in a certain
sense. Specifically we will show that under some mild assumptions the bias of
FROCC with $\varepsilon=1$ goes to 0 at an exponential rate as the size of the
training set increases. We first show a general theorem which should be viewed
as a variant of Theorem 17 of [4] which is more suited to our situation since
we address a one-class situation and our algorithm is randomized. Our Theorem
4 is of general interest and may have applications beyond the analysis of
FROCC.

####  4.1.1 Terminology and notation

Let $\mathcal{S}$ denote the set of all finite labelled point sets of
$\mathbb{R}^{d}$ where each point is labelled either 0 or 1. We assume we have
a training set $S\in\mathcal{S}$ chosen randomly as follows: We are given an
unknown distribution $D$ over $\mathbb{R}^{d}\times\\{0,1\\}$ and $S$
comprises $k$ samples with label 1 drawn i.i.d. from $D$. For a point
$z=(x,y)\in\mathbb{R}^{d}\times\\{0,1\\}$ we use $dat(z)$ to denote $x$ and
$lab(z)$ to denote $y$.

Let $\mathcal{R}$ be the set of all finite strings on some finite alphabet,
and let us call the elements of $\mathcal{R}$ decision strings. Further, let
$\mathcal{F}$ be the set of all classification functions from $\mathbb{R}^{d}$
to $\\{0,1\\}$. Then we say a classification map
$\Phi:\mathcal{S}\times\mathcal{R}\rightarrow\mathcal{F}$ maps a training set
and a decision string to a classification algorithm

With this setup we say that a randomized classification algorithm $A$ takes a
training $S\in\mathcal{S}$ as input, picks a random decision string
$r\in\mathcal{R}$ and returns the classification function $\Phi(S,r)$ which we
denote $A(S,r)$. $A(S,r)$ is a randomly chosen element of $\mathcal{F}$ which
we call a classifier. Given an $r$, $A(S,r)$ is fixed but we will use $A_{S}$
to denote the randomized classifier which has been given its training set $S$
but is yet to pick a random decision string. Now, given a
$z\in\mathbb{R}^{d}$, the loss function of a randomized classifier $A_{S}$ is
given by

$V(A_{S},z)=\mbox{E}_{r}\left\\{\mathrm{1}_{A(S,r)(dat(z))\neq
lab(z)}\right\\},$

where the expectation is over the randomness of the decision string $r$. In
other words the loss is equal to $\mbox{Pr}_{r}\left\\{A(S,r)(dat(z))\neq
lab(z)\right\\}$.

We define the risk of $A_{S}$ as

$R(A_{S})=\mbox{E}_{S,z}\left\\{V(A_{S},z)\right\\},$

where the expectation is over the random choice of $S$ and of the point $z$.
Note that $V(\cdot,\cdot)$ already contains an expectation on the randomness
associated with the decision string which is inherent in $A_{S}$

The empirical risk of $A_{S}$ is defined

$R_{e}(A_{S})=\frac{1}{|S|}\sum_{z\in S}V(A_{S},z).$

We introduce notation for two modifications of the training set $S$. For
$1\leq i\leq|S|$ we say that $S^{\setminus i}=S\setminus\\{z_{i}\\}$ and
$S^{i}=S^{\setminus i}\cup\\{z_{i}^{\prime}\\}$ where $z_{i}^{\prime}$ is
chosen from $D$ independently of all previous choices. We now define a notion
of stability.

The following notion of stability is a modification of the definition of
stability for classification algorithms given by [4].

######  Definition 2 (0-1 uniform classification stability).

Suppose we have a randomized classification algorithm $A$ and a loss function
$V(\cdot,\cdot)$ whose co-domain is $[0,1]$. Then $A$ is said to have 0-1
uniform classification stability $(\beta,\eta)$ if for all
$S\subseteq\mathbb{R}^{d}$, for every $i$ such that $1\leq i\leq|S|$, and for
every $z\in\mathbb{R}^{d}\times\\{0,1\\}$

$|V(A_{S},z)-V(A_{S^{\setminus i}},z)|\leq\beta$

with probability at least $1-\eta$.

If $\beta$ is $O(1/|S|)$ and $\eta$ is $O(e^{-c|S|})$ for some constant $c>0$,
we say that $A$ is 0-1 uniform classification stable.

We prove that a 0-1 uniform classification stable algorithm has low bias and
converges exponentially fast in the size of $S$ to its expected behavior. This
is a general result that may be applicable to a large class of randomized
classification algorithm. We also prove that FROCC is 0-1 uniform
classification stable under mild conditions on the unknown distribution.

We also introduce a condition that the unknown distribution $D$ has to satisfy
in order for us to show the desired stability property.

######  Definition 3 (Spatial divisibility).

Suppose that $\mu:\mathbb{R}^{d}\rightarrow[0,1]$ is a probability density
function. For any set $T$ containing $d$ points
$x_{i},\ldots,x_{d}\in\mathbb{R}^{d}$ let $H_{T+}$ and $H_{T-}$ be the two
half-spaces defined by the hyper-plane containing all the points of $T$. We
say that $\mu$ is spatially divisible if for any set $d+1$ randomly chosen
points $X=\\{X_{1},\ldots,X_{d}\\}$ and $Y$ chosen independently according to
density $\mu$ and any $A,B\subset\mathbb{R}^{d}$ such that $\mu(A),\mu(B)>0$,

$\displaystyle\mbox{Pr}\left\\{Y\in H_{X+}|X_{i}\in A,Y\in B\right\\}$
$\displaystyle>0,\mathrm{and~{}}$ $\displaystyle\mbox{Pr}\left\\{Y\in
H_{X-}|X_{i}\in A,Y\in B\right\\}$ $\displaystyle>0.$

Note that the set $X$ defines a hyper-plane in $d$ dimensions with probability
1 for any distribution defined on a non-empty volume of $\mathbb{R}^{d}$. Most
standard distributions have the spatial divisibility property. For example, it
is easy to see that a multi-variate Gaussian distribution has this property.
If we pick a point uniformly at random from within a convex $d$-polytope then
too the spatial divisibility property is satisfied. To see this we note that
the only way it could not be satisfied is if the points $X_{i}$ and $Y$ are
picked from the surface of the $d$-polytope which is an event of probability
0.

####  4.1.2 Results

With the definition of stability given above we can prove the following
theorem which shows that the deviation of the empirical risk from the expected
risk tends to 0 exponentially as $|S|$ increases for a class of randomized
algorithms that includes FROCC.

######  Theorem 4.

Suppose we have a randomized classification algorithm $A$ which has 0-1
uniform classification stability $(\beta,\eta)$ with $0<\beta,\eta<1$, and
suppose this algorithm is trained on a set $S$ drawn i.i.d. from a hidden
distribution in such a way that the random choices made by $A$ are independent
of $S$, then, for any $\varepsilon>0$,

$\mbox{Pr}\left\\{|R(A,S)-R_{e}(A,S)|>\varepsilon\right\\}\leq
2\exp\left\\{-\frac{2\varepsilon^{2}}{|S|\beta^{2}}\right\\}+2|S|\eta.$ (1)

Moreover if $A$ is 0-1 uniform classification stable then the RHS of (1) tends
to 0 at a rate exponential in $|S|$.

###### Proof.

As in [4] we will use McDiarmid’s inequality [22] to bound the deviation of
the empirical risk from the risk. For completeness we state the result:

######  Lemma 5 ([22]).

Given a set of $m$ independent random variables $Y_{i},1\leq i\leq m$ and a
function $f$ such that $|f(x_{1},\ldots,x_{m})-f(y_{1},\ldots,y_{m})|<c_{i}$
whenever $x_{j}=y_{j},1\leq j\leq m,j\neq i$, and $x_{i}\neq y_{i}$, then

$\mbox{Pr}\left\\{|\mbox{E}\left\\{f(Y_{1},\ldots,Y_{m})\right\\}-f(Y_{1},\ldots,Y_{m})|>\varepsilon\right\\}\leq
e^{\left(-\frac{2\varepsilon^{2}}{\sum_{i=1}^{m}c_{i}^{2}}\right)}.$

To use Lemma 5 we have to show that $R_{e}(A,S)$ is a $2\beta$-Lipschitz
function. However, this property is only true with a certain probability in
our case. In particular we will show that for all $i$, $1\leq i\leq|S|$,
$|R_{e}(A,S)-R_{e}(A,S^{i})|\leq 2\beta$ with probability at least
$1-2|S|\eta$. To see this we note that for any $i$ and any $z_{j}\in S$
(including $j=i$).

$\displaystyle|V(A_{S},z_{j})-V(A_{S^{i}},z_{j})|=$
$\displaystyle|V(A_{S},z_{j})-V(A_{S^{\setminus i}},z_{j})$
$\displaystyle+V(A_{S^{\setminus i}},z_{j})-V(A_{S^{i}},z_{j})|.$

Using the definition of $(\beta,\eta)$ 0-1 uniform classification stability
and the triangle inequality, we get that the RHS is bounded by $2\beta$ with
probability at least $1-2\eta$. If $A_{j}$ is the event that the RHS above is
bounded by $2\beta$ then we want to bound the probability of the event that
this is true for all $j$, $1\leq j\leq|S|$, i.e., the event
$F=\cap_{j=1}^{|S|}A_{j}$. Since
$\mbox{Pr}\left\\{\overline{A_{j}}\right\\}\leq 2\eta$, we can say that
$\mbox{Pr}\left\\{F\right\\}$ is at least $1-2|S|\eta$.

Now, let $E$ be the event that $|R(A,S)-R_{e}(A,S)|>\varepsilon$ and $F$
defined above be the event that $R_{e}(A,S)$, which is a function of the
vector of $|S|$ elements chosen independently to form $S$ is
$2\beta$-Lipschitz. We know that

$\mbox{Pr}\left\\{E\right\\}=\mbox{Pr}\left\\{E\cap
F\right\\}+\mbox{Pr}\left\\{E\cap\overline{F}\right\\},$

and so we can say that

$\mbox{Pr}\left\\{E\right\\}\leq\mbox{Pr}\left\\{E|F\right\\}\mbox{Pr}\left\\{F\right\\}+\mbox{Pr}\left\\{\overline{F}\right\\}.$
(2)

We have already argued that the second term on the RHS is upper bounded by
$2|S|\eta$ so we turn to the first term. To apply Lemma 5 to the first term we
note that $E$ depends on the random selection of $S$ which are selected
independently of each other and, by assumption, independent of the random
choices made by $A$. Therefore the random collection $\\{V(A_{S},z):z\in S\\}$
is independent even when conditioned on $F$ which is determined purely by the
random choices of $A$ and is true for every choice of set $S$. Once this is
noted then we can use McDiarmid’s inequality to bound the first term of
Equation (2). We ignore $\mbox{Pr}\left\\{F\right\\}$ by upper bounding it by
1. ∎

We now show that Theorem 4 applies to FROCC with $\varepsilon=1$ if the
unknown distribution $D$ is spatially divisible.

######  Proposition 6.

If the unknown distribution $D$ is spatially divisible then FROCC with
$\varepsilon=1$ is 0-1 uniform classification stable.

###### Proof.

For any $i$, $1\leq i\leq n$, where $n=|S|$, we note that when $\varepsilon=1$
the entire interval spanned by the projections in any direction is said to
contain inliers, and so if $x_{i}$ lies strictly within the convex hull of $S$
then the removal of $i$ from $S$ does not affect the classifier. This is
because the boundaries in any direction are determined by the points that are
part of the convex hull. Let us denote this set $\mbox{conv}(S)$. Therefore,
since $V(\cdot,\cdot)$ takes value at most 1, we deduce the following upper
bound

$|V(A_{S},z)-V(A_{S^{\setminus
i}},z)|\leq\mbox{Pr}\left\\{x_{i}\in\mbox{conv}(S)\right\\}.$

To bound the probability that a point $x_{i}$ lies in the convex hull of $S$
we use an argument that Efron [9] attributes to Rényi and Sulanke [25, 26].
Given a region $B\subset\mathbb{R}^{d}$ let us denote by $D(B)$ the
probability that a point drawn from the unknown distribution $D$ places a
point in $B$. Now given any $d$ points, say $x_{1},\ldots,x_{d}\in S$, we
divide $\mathbb{R}^{d}$ into two regions $A_{X+}$ that lies on one side of the
hyper-plane defined by $x_{1},\ldots,x_{d}$ and $A_{X-}$ that lies on the
other side. Then the probability that $x_{1},\ldots,x_{d}$ all lie in
$\mbox{conv}(S)$ is equal to the probability that all the remaining points of
$S$ are either in $A_{X+}$ or in $A_{X-}$, i.e.,

$\mbox{Pr}\left\\{x_{1},\ldots,x_{d}\in\mbox{conv}(S)\right\\}=D(A_{X+})^{(n-d)}+D(A_{X-})^{(n-d)}.$

From this, using the union bound we can say that

$\mbox{Pr}\left\\{x_{i}\in\mbox{conv}(S)\right\\}\leq\sum_{Y\in\mathcal{P}(S\setminus\\{x_{i}\\},d)}D(A_{Y+})^{(n-d)}+D(A_{Y-})^{(n-d)},$

where $\mathcal{P}(A,d)$ is the set of all subsets of $A$ of size $d$. This
can further be bounded as

$LHS\leq
2\binom{n-1}{d}\max_{Y\in\mathcal{P}(S\setminus\\{x_{i}\\},d)}\max\\{D(A_{Y+})^{(n-d)},D(A_{Y-})^{(n-d)}\\}.$

Since we have assumed that $D(A_{Y\pm})<1$ for all $Y\subset S$ such that
$|Y|=d$ and $x_{i}\notin Y$, using the fact that $\binom{n}{k}\leq(en/k)^{k}$,
we can say that there is an $\alpha$ such that $0<\alpha<1$ and a constant
$C>0$ such that

$|V(A_{S},z)-V(A_{S^{\setminus i}},z)|\leq C\cdot(n-1)^{d}\alpha^{n}$

almost surely. Since the RHS goes to 0 exponentially fast in $n$ with
probability 1, we can say that FROCC is 0-1 uniform classification stable when
$\varepsilon=1$. ∎

From Theorem 4 and Proposition 6 we get

######  Theorem 7.

For a training set $S$ chosen i.i.d. from a spatially divisible unknown
distribution, if $\varepsilon$ is set to 1 then $R_{e}(FROCC,S)$ converges in
probability to $R(FROCC,S)$ exponentially fast in $|S|$.

We feel that it should be possible to use the framework provided by Theorem 4
to show that FROCC is stable even when $\varepsilon$ lies in $(0,1)$, however
this problem remains open.

###  4.2 Monotonicity properties of FROCC

We now show that the precision and the model size of FROCC is monotonic in the
two parameters $m$ and $\varepsilon$ but in opposite directions. The precision
and model size increase as $m$ increases and decrease as $\varepsilon$
increases. This result is formalized as Proposition 8 below and follows by a
coupling argument.

We first introduce some terms. On the $\sigma$-algebra induced by the Borel
sets of $\cup_{i\geq 1}\mathbb{R}^{i}$ we define the probability measure
$\mbox{P}_{m,\varepsilon}(\cdot)$ induced by FROCC with parameters
$\varepsilon,m>0$. Note that $\varepsilon,m>0$, FROCC is a random collection
of $m$-dimensional cubes in $\mathbb{R}^{m}$. These cubes are induced by
taking the products of intervals in each of the $m$ dimensions. Each dimension
has between 1 and $|S|$ intervals when trained on $S$. We define the model
size of FROCC to be the sum of the number of intervals, i.e., if there are
$k_{i}$ intervals along dimension $i$, $1\leq i\leq m$, the model size is
$\sum_{i=1}^{m}2k_{i}$. We will use the letter $M_{m,\varepsilon}$ to denote
the model size of FROCC with parameters $m,\varepsilon$. Note that this is a
random variable.

######  Proposition 8.

Given FROCC trained on a finite set $S\subset\mathbb{R}^{d}$, for
$\varepsilon,\varepsilon^{\prime}>0$, $m,m^{\prime}>0$ and any
$x\in\mathbb{R}^{d}$ we have that

  1. 1.

whenever $\varepsilon<\varepsilon^{\prime}$

    1. (a)

$\mbox{P}_{m,\varepsilon}(x\mbox{ is classifed
YES})\leq\mbox{P}_{m,\varepsilon^{\prime}}(x\mbox{ is classifed YES})$,

    2. (b)

$\mbox{E}_{m,\varepsilon}(M_{m,\varepsilon})\geq\mbox{E}_{m,\varepsilon^{\prime}}(M_{m,\varepsilon^{\prime}})$,
and,

  2. 2.

whenever $m<m^{\prime}$

    1. (a)

$\mbox{P}_{m,\varepsilon}(x\mbox{ is classifed
YES})\leq\mbox{P}_{m^{\prime},\varepsilon}(x\mbox{ is classifed YES})$,

    2. (b)

$\mbox{E}_{m,\varepsilon}(M_{m,\varepsilon})\geq\mbox{E}_{m^{\prime},\varepsilon}(M_{m^{\prime},\varepsilon})$.

###### Proof.

For 1(a) and 1(b) we couple the probability distributions
$\mbox{P}_{m,\varepsilon}(\cdot)$ and
$\mbox{P}_{m,\varepsilon^{\prime}}(\cdot)$ by choosing $m$ random unit
vectors, $\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{m}$, and then constructing
one instance of FROCC with separation $\varepsilon$ and one instance of FROCC
with separation $\varepsilon^{\prime}$ using the same $m$ random unit vectors.

Now, consider some vector $\boldsymbol{w}_{i}$ and let the $x_{j}^{i},1\leq
i\leq|S|$ be the projections of the training points on $\boldsymbol{w}_{i}$.
Let the intervals formed by $\varepsilon$ separated FROCC be
$\\{[a_{ij},b_{ij}]:1\leq j\leq k_{i}\\}$ and those of $\varepsilon^{\prime}$
separated FROCC be $\\{[a^{\prime}_{ij},b^{\prime}_{ij}]:1\leq j\leq
k^{\prime}_{i}\\}$. We know that $a^{\prime}_{i1}=a_{i1}=\min x_{j}^{i}$.
Clearly each $[a_{ij},b_{ij}]$ is contained within some
$[a^{\prime}_{ij^{\prime}},b^{\prime}_{ij^{\prime}}]$ since the distance
between subsequent points within $[a_{ij},b_{ij}]$ is at most $\varepsilon$
which is strictly less than $\varepsilon^{\prime}$. This proves 1(a) and also
implies that $k_{i}^{\prime}\leq k_{i}$ which proves 1(b).

For 2(a) and 2(b) we couple the probability distributions
$\mbox{P}_{m,\varepsilon}(\cdot)$ and
$\mbox{P}_{m^{\prime},\varepsilon}(\cdot)$ by choosing $m$ random unit
vectors, $\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{m}$, and then constructing
two instances of FROCC. Then we choose an additional $m^{\prime}-m$ vectors
$\boldsymbol{w}_{m+1},\ldots,\boldsymbol{w}_{m^{\prime}}$ and compute
intervals corresponding to these and add them to the second instance of FROCC.
2(b) follows immediately. For 2(a) we note that any $x\in\mathbb{R}^{d}$
classified as YES by the second model must also be classified as YES by the
first model since it is classified as YES along the first $m$ dimensions of
the second model which are common to both models. ∎

From Proposition 8 it follows that expected model size and false positive
probability vary inversely, i.e., the larger the model size the smaller the
false positive probability and vice versa.

Proposition 8 is also consistent with the following upper bound that is easy
to prove

######  Fact 9.

For FROCC constructed on training set
$S=\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{n}\\}$,

$2m\leq M_{m,\varepsilon}\leq
m\cdot\max\left\\{2,\frac{\delta_{\max}}{\varepsilon}\right\\}$

with probability 1, where $\delta_{\max}=\max_{1\leq i,j\leq
n}\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\|_{2}$.

The first inequality is trivial. The second follows by observing that along
any dimension the gaps between intervals must be at least $\varepsilon$ and
the length of the interval between the maximum and minimum projection is at
mode $\delta_{\max}$.

###  4.3 FROCC’s error decays exponentially with $m$

######  Definition 10.

Given a finite set of points
$S=\\{\bm{x}_{1},\ldots,\bm{x}_{n}\\}\subseteq\mathbb{R}^{d}$ and any
$\bm{w}\in\bm{1}_{d}$, we say that
$\ell_{\bm{w}}=\min_{j=1}^{n}\langle\bm{x}_{j},\bm{w}\rangle,$ and
$u_{\bm{w}}=\max_{j=1}^{n}\langle\bm{x}_{j},\bm{w}\rangle$. Now, given a point
$\bm{y}\subset\mathbb{R}^{d}$ and $\bm{w}\in\bm{1}_{d}$, we say that the
distance of $\bm{y}$ from $S$ along the direction $\bm{w}$ is defined as

$\alpha(\bm{y},S,\bm{w})=\left\\{\begin{array}[]{ll}\ell_{\bm{w}}-\langle\bm{y},\bm{w}\rangle&\mbox{if
}\langle\bm{y},\bm{w}\rangle<\ell_{\bm{w}}\\\ 0&\mbox{if
}\ell_{\bm{w}}\leq\langle\bm{y},\bm{w}\rangle\leq u_{\bm{w}}\\\
\langle\bm{y},\bm{w}\rangle-u_{\bm{w}}&\mbox{o.w.}\end{array}\right.$

Further we say that $\bm{w}\in\bm{1}_{d}$ is a discriminator of $\bm{y}$ from
$S$ if $\alpha(\bm{y},S)>0$. Finally we denote by $C(\bm{y},S)$ the subset of
unit vectors of $\bm{1}_{d}$ that discriminate $\bm{y}$ from $S$.

FROCC has the property that the probability of misclassifying a point outside
the class decreases exponentially with parameter $m$. We state this formally.
Given $A\subset\bm{1}_{d}$ we denote the measure of $A$ by $\mu(A)$.

######  Proposition 11.

Given a set $S$ and a point $\bm{y}$ with a set $C(\bm{y},S)$ of non-empty
measure such that for any $\bm{w}\in C(\bm{y},S)$,
$\langle\bm{y},\bm{w}\rangle\notin[\min_{j=1}^{n}\langle\bm{x}_{j},\bm{w}\rangle,\max_{j=1}^{n}\langle\bm{x}_{j},\bm{w}\rangle]$,
the probability that FROCC projection dimension $m$ returns a Yes answer is

$\mbox{Pr}\left\\{\bm{y},S,m\right\\}=\left(1-\frac{\mu(C(\bm{y},S))}{\mu(\bm{1}_{d})}\right)^{m}.$

Hence for the classifier to given an erroneous Yes answer on $\bm{y}$ with
probability at most $\delta$ we need

$m\geq\frac{\mu(\bm{1}_{d})}{\mu(C(\bm{y},S))}\log\frac{1}{\delta}$ (3)

projection dimensions.

(a) m=1

(b) m=2

(c) m=8

Figure 3: Probability contours of $\mbox{Pr}\left\\{\bm{y},S,m\right\\}$ for
different values of $m$. The region boundary gets more distinct with
increasing $m$.

The proof of (3) is just a simple calculation. Figure 3 presents the result of
Proposition 11 visually.

##  5 Experiments and Results

We conducted a comprehensive set of experiments to evaluate the performance of
FROCC on synthetic and real world benchmark datasets and compare them with
various existing state of the art baselines. In this section we first present
the details of the datasets, baselines, and metrics we used in our empirical
evaluation, and then present the results of comparison.

###  5.1 Methods Compared

We compare FROCC with the following state of the art algorithms for OCC:

  1. (i)

OC-SVM: One class SVM based on the formulation of Schölkopf et al [30],

  2. (ii)

Isolation Forest: Isolation forest algorithm [21],

  3. (iii)

AE: An auto encoder based anomaly detection algorithm based on Aggarwal [1],

  4. (iv)

Deep SVDD: A deep neural-network based formulation of Ruff et al [28]. We used
the implementation and the optimal model parameters provided by the
authors111https://github.com/lukasruff/Deep-SVDD-PyTorch.

We implemented FROCC using Python 3.8 with numpy library. The IntervalTree
subroutine (Algorithm 2) was optimized by quantizing the interval into
discrete bins of sizes based on $\varepsilon$. This allows for a vectorized
implementation of the subroutine. All experiments were conducted on a server
with Intel Xeon (2.60GHz), and NVIDIA GeForce GTX 1080 Ti GPU. It is
noteworthy that unlike deep learning based methods (i.e., AE and Deep SVDD),
FROCC does not require GPU during training as well as testing.

For OCSVM and FROCC, for each dataset we chose the best performing (in ROC)
kernel among the following:  (a) linear (dot product),  (b) radial basis
function (RBF),  (c) polynomial (degree=3) and,  (d) sigmoid .

###  5.2 Datasets

We evaluate FROCC and the baseline methods on a set of well-known benchmark
datasets summarized in Table 1. The set of benchmarks we have chosen covers a
large spectrum of data characteristics such as the number of samples (from a
few hundreds to millions) as well as the number of features (from a handful to
tens of thousands). Thus it broadly covers the range of scenarios where OCC
task appears.

To adapt the multi-class datasets for evaluation in OCC setting, we perform
the processing similar to Ruff et al [28]: Given a dataset with multiple
labels, we assign one class the _positive_ label and all others the _negative_
label. Specifically, we select the positive classes for i. MNIST: randomly
from 0, 1 and 4, ii. CIFAR 10: airplane, automobile and deer and iii. CIFAR
100: beaver, motorcycle and fox. We then split the _positive_ class instances
into _train_ and _test_ sets. Using labelled data allows us to evaluate the
performance using true labels. We _do not_ use any labels for training. We
double the test set size by adding equal number of instances from the
_negative_ ly labeled instances. We train the OCC on the _train_ set which
consists of only _positive_ examples. Metrics are calculated on _test_ set
which consists of equal number of _positive_ and _negative_ examples.

ID | Name | Features | Training Samples |  | Test Samples
---
(Equal +/– Split)
A1 | Diabetes [8] | 8 | 268 | 508
A2⋆ | MAGIC Telescope [8] | 10 | 12332 | 20870
A3⋆ | MiniBooNE [8] | 50 | 18250 | 30650
A4 | Cardiotocography [8] | 35 | 147 | 294
B1⋆ | SATLog-Vehicle [31] | 100 | 24623 | 36864
B2⋆ | Kitsune Network Attack [23] | 115 | 3018972 | 3006490
B3 | MNIST [20] | 784 | 3457 | 5390
B4 | CIFAR-10 [18] | 3072 | 3000 | 5896
B5 | CIFAR-100 [18] | 3072 | 300 | 594
B6 | GTSRB [32] | 3072 | 284 | 562
B7 | Omniglot [19] | 33075 | 250 | 400

Table 1: Dataset statistics. The datasets are divided in to two groups: Group
A (A1:A4) has datasets with fewer than 100 features and Group B (B1:B7)
contains datasets with greater than 100 features. ⋆ marks the datasets with
more than $10,000$ training samples.

###  5.3 Metrics

Classification Performance: For measuring the classification performance, we
use the following two commonly used metrics:

  * •

ROC AUC to measure the classification performance of all methods, and

  * •

Adjusted Precision@n, that is, fraction of true outliers among the top n
points in the test set, normalized across datasets [33].

Computational Scalability: For measuring the computational performance of all
the methods, we use the speedup of their training and testing time over the
fastest baseline method for the dataset. In other words, for an algorithm $A$
its speedup is calculated as the ratio of training (or testing) time of the
fastest _baseline_ method to the training (or testing) time of $A$. We found
Isolation forests to be the fastest across all scenarios, thus making it the
default choice for computing the speedup metric over. All measurements are
reported as an average over 5 runs for each method.

###  5.4 Results and Observations

ID | OC-SVM | IsoForest | Deep SVDD | Auto Encoder | FROCC
---|---|---|---|---|---
A1 | 53.35 $\pm$ 0.95 | 63.48 $\pm$ 0.46 | 73.24 $\pm$ 0.65 | 62.43 $\pm$ 0.26 | _73.18 $\pm$ 0.26_
A2⋆ | 68.12 $\pm$ 0.85 | 77.09 $\pm$ 0.84 | 61.39 $\pm$ 0.87 | _75.96 $\pm$ 0.44_ | 72.30 $\pm$ 0.33
A3⋆ | 54.22 $\pm$ 0.45 | 81.21 $\pm$ 0.14 | _78.21 $\pm$ 0.10_ | 56.27 $\pm$ 0.22 | 69.32 $\pm$ 0.30
A4 | 57.93 $\pm$ 0.73 | 85.10 $\pm$ 0.33 | 56.95 $\pm$ 0.53 | 59.43 $\pm$ 0.60 | _83.57 $\pm$ 0.44_
B1⋆ | 73.51 $\pm$ 0.41 | _83.19 $\pm$ 0.44_ | 68.36 $\pm$ 0.64 | 76.42 $\pm$ 0.76 | 85.14 $\pm$ 0.74
B2⋆ | 86.01 $\pm$ 0.60 | 80.05 $\pm$ 0.43 | _84.73 $\pm$ 0.37_ | 79.23 $\pm$ 0.34 | 86.64 $\pm$ 0.51
B3 | 98.99 $\pm$ 0.11 | 98.86 $\pm$ 0.31 | 97.04 $\pm$ 0.08 | _99.38 $\pm$ 0.13_ | 99.61 $\pm$ 0.35
B4 | 52.21 $\pm$ 0.39 | 51.47 $\pm$ 0.59 | _59.32 $\pm$ 0.62_ | 56.73 $\pm$ 0.47 | 61.93 $\pm$ 0.64
B5 | 49.62 $\pm$ 0.12 | 54.13 $\pm$ 0.17 | _67.81 $\pm$ 0.39_ | 55.73 $\pm$ 0.53 | 71.04 $\pm$ 0.37
B6 | 63.55 $\pm$ 0.12 | 61.23 $\pm$ 0.35 | 71.88 $\pm$ 0.36 | 66.73 $\pm$ 0.44 | _67.12 $\pm$ 0.60_
B7 | _90.21 $\pm$ 0.63_ | 70.83 $\pm$ 0.35 | 72.70 $\pm$ 0.07 | 62.38 $\pm$ 0.12 | 92.46 $\pm$ 0.21

Table 2: Area under the ROC curve. ID corresponds to the dataset ID in Table
1. Bold values represent the best scores and _italics_ represent the second
best scores.

ID | OC-SVM | IsoForest | Deep SVDD | Auto Encoder | FROCC
---|---|---|---|---|---
A1 | 59.72 $\pm$ 0.95 | 61.64 $\pm$ 0.05 | _72.74 $\pm$ 0.13_ | 63.54 $\pm$ 0.14 | 72.83 $\pm$ 0.27
A2⋆ | 78.17 $\pm$ 0.15 | 87.09 $\pm$ 0.35 | 72.23 $\pm$ 0.47 | 78.19 $\pm$ 0.32 | _84.31 $\pm$ 0.50_
A3⋆ | 61.05 $\pm$ 0.56 | 79.77 $\pm$ 0.73 | _78.32 $\pm$ 0.43_ | 66.17 $\pm$ 0.48 | 71.91 $\pm$ 0.36
A4 | 63.21 $\pm$ 0.94 | _82.83 $\pm$ 0.18_ | 60.03 $\pm$ 0.35 | 57.73 $\pm$ 0.54 | 85.91 $\pm$ 0.33
B1⋆ | 74.22 $\pm$ 0.44 | _81.94 $\pm$ 0.62_ | 68.36 $\pm$ 0.68 | 76.42 $\pm$ 0.60 | 89.21 $\pm$ 0.35
B2⋆ | 81.35 $\pm$ 0.60 | 87.24 $\pm$ 0.65 | 81.21 $\pm$ 0.63 | 72.94 $\pm$ 0.56 | _83.21 $\pm$ 0.65_
B3 | 92.34 $\pm$ 0.47 | 91.65 $\pm$ 0.65 | _93.25 $\pm$ 0.45_ | 74.32 $\pm$ 0.37 | 99.80 $\pm$ 0.58
B4 | 50.02 $\pm$ 0.75 | 51.42 $\pm$ 0.86 | _57.32 $\pm$ 0.09_ | 51.63 $\pm$ 0.18 | 57.92 $\pm$ 0.41
B5 | 50.08 $\pm$ 0.32 | 50.13 $\pm$ 0.43 | _55.21 $\pm$ 0.64_ | 53.40 $\pm$ 0.77 | 55.62 $\pm$ 0.38
B6 | 61.63 $\pm$ 0.01 | 59.13 $\pm$ 0.11 | 69.38 $\pm$ 0.30 | _64.71 $\pm$ 0.16_ | 62.46 $\pm$ 0.36
B7 | 88.32 $\pm$ 0.10 | 72.83 $\pm$ 0.26 | _82.70 $\pm$ 0.51_ | 65.90 $\pm$ 0.47 | 79.34 $\pm$ 0.40

Table 3: Adjusted $Precision@n$. For each dataset, $n$ is the number of
positive examples in the test set of that dataset. ID corresponds to the
dataset ID in Table 1. Bold values represent the best scores and _italics_
represent the second best scores.

ID | OC-SVM | Deep SVDD | Auto Encoder | FROCC
---|---|---|---|---
Train | Test | Train | Test | Train | Test | Train | Test
A1 | 0.055 | 0.862 | 0.034 | 0.038 | 0.089 | 0.090 | 1.111(2) | 1.111
A2⋆ | 0.057 | 0.847 | 0.032 | 0.038 | 0.085 | 0.088 | 1.333(3) | 1.075
A3⋆ | 0.100 | 0.840 | 0.031 | 0.039 | 0.082 | 0.087 | 1.282(3) | 1.075
A4 | 0.064 | 0.870 | 0.038 | 0.038 | 0.091 | 0.091 | 1.190(2) | 1.099
B1⋆ | 0.074 | 0.855 | 0.032 | 0.038 | 0.087 | 0.089 | 1.075(1) | 1.087
B2⋆ | 0.043 | 0.524 | 0.028 | 0.038 | 0.062 | 0.078 | 1.786(1) | 1.176
B3 | 0.099 | 0.794 | 0.043 | 0.039 | 0.050 | 0.080 | 1.299(1) | 1.149
B4 | 0.099 | 0.820 | 0.040 | 0.039 | 0.069 | 0.083 | 1.389(1) | 1.099
B5 | 0.100 | 0.826 | 0.039 | 0.039 | 0.074 | 0.085 | 1.370(1) | 1.087
B6 | 0.098 | 0.833 | 0.039 | 0.039 | 0.079 | 0.086 | 1.351(2) | 1.087
B7 | 0.100 | 0.806 | 0.035 | 0.039 | 0.061 | 0.082 | 1.449(1) | 1.111

Table 4: Training and test speedups for baselines and FROCC. It is calculated
as $speedup(M)=\frac{time(IF)}{time(M)}$, where $time(IF)$ is the time for
Isolation Forest, the fastest baseline. Higher is better. A number greater
than 1 indicates the method is faster than the fastest baseline. Superscript
shows the rank of the methods based on ROC-AUC scores for FROCC.

Table 2 compares the ROC scores of the baselines on the datasets. From the
table we note that FROCC outperforms the baselines in six of the eleven
datasets. Further, we note that for high dimensional datasets –i.e., datasets
with _$\geq$ 100 features_ (B1-B7), FROCC outperforms the baselines in six out
of seven datasets while ranking second in the remaining one. This demonstrates
the superiority of FROCC for high dimensional data which are known to be
challenging for most OCC methods. Table 3 summarizes the _Adjusted
Precision@n_ (for a given dataset, $n$ is the number of positive examples in
test data). Here too we observe that FROCC outperforms the baselines in six
datasets. In high dimensional datasets, it is superior in four out of seven
datasets, and is the second best in one. And even in datasets where the
performance of FROCC is not the highest, it does not drop as low as
traditional shallow baselines, which in two occasions fail to learn
altogether.

Next, we turn our attention to the computational performance of all the
methods summarized in Table 4, where we present the training and testing
speedups. These results particularly highlight the scalability of FROCC over
all other baselines, including the traditionally efficient shallow methods
such as Isolation forest. Against deep learning based methods such as Deep
SVDD and Auto Encoder, FROCC shows nearly _1-2 orders_ magnitude speedup.
Overall, we notice that FROCC achieves up to $68\times$ speedup while beating
the baselines, and up to $35\times$ speedup while ranking second or third.

###  5.5 Discussion of Results

Here we discuss the results from two broad perspectives:

##### ROC and Speed trade-offs:

The speedups show that FROCC is the fastest method. From Table 2, we see that
in six datasets, FROCC outperforms the baseline as well. Of the cases it
doesn’t outperform the baselines, it ranks second thrice out of five and in
each of the these cases (datasets A1, A4 and B7) it is 35, 29 and 1.19 times
faster than the best performing method respectively. Thus, depending on the
application, the speed vs ROC trade-off may make FROCC the method of choice
even when it doesn’t outperform other algorithms.

##### Scalability:

While we are faster than baselines in all datasets, large datasets like
MiniBooNE (A3), SATLog-Vehicle (B1) and especially Kitsune network attack (B2)
datasets – where FROCC is 68 times faster than the second best method – can be
render the best performing deep baselines infeasible, leaving scalable methods
like IsolationForest and FROCC as the only option. Given that FROCC
consistently ranks among top three (1: 6 times, 2: 3 times, 3: 2 times),
whereas IsolationForest’s rank varies inconsistently and go up to 5 (out of
5), FROCC is the algorithm of choice when scalability is a concern.

###  5.6 Parameter Sensitivity

In previous section we mentioned that the parameters were chosen based on grid
search. In this section we present a study of sensitivity of FROCC to the
parameters.

##### Sensitivity to dimensions.

From the analysis in Section 4, we know that the performance of FROCC improves
with increasing number of classification dimensions. Figure 4 shows this
variation for a few selected datasets.

Figure 4: Variation of area under the ROC with Dimensions for MNIST, SATLOG
Vehicle, Omniglot and Kitsune network attack dataset. We observe that the
metric improves monotonically, confirming the theoretical claim.

##### Sensitivity to $\varepsilon$.

The separation parameter $\varepsilon$ is a dataset specific parameter and
relates to the minimum distance of separation between positive examples and
potential negative examples. In practice this comes out to be around the order
of 0.1 or 0.01, as shown in Figure 5

Figure 5: Variation of area under the ROC with $\varepsilon$ for MNIST and
MAGIC Telescope dataset.

##  6 Conclusion

In this paper, we presented a surprisingly simple and highly effective one-
class classification strategy based on projecting data onto randomly selected
vectors from the unit sphere. By representing these projections as a
collections of intervals we developed FROCC. Our experiments over real and
synthetic datasets reveal that despite its extreme simplicity –and the
resulting computational efficiency– FROCC is not just _better_ than the
traditional methods for one-class classification but also better than the
highly sophisticated (and expensive) models that use deep neural networks.

As part of our future work, we plan to explore extending the FROCC algorithms
to the classification task under highly imbalanced data, and to application
settings where high-performance OCC are crucial.

## References

  * Aggarwal [2015] Aggarwal CC (2015) Outlier analysis. In: Data mining, Springer, pp 237–263
  * Ailon and Chazelle [2006] Ailon N, Chazelle B (2006) Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. In: ACM STOC, pp 557–563
  * Borisyak et al [2019] Borisyak M, Ryzhikov A, Ustyuzhanin A, Derkach D, Ratnikov F, Mineeva O (2019) $(1+\varepsilon)$-class classification: an anomaly detection method for highly imbalanced or incomplete data sets, arXiv:1906.06096
  * Bousquet and Elisseeff [2002] Bousquet O, Elisseeff A (2002) Stability and generalization. J Mach Learn Res 2:499–526
  * Chandola et al [2009] Chandola V, Banerjee A, Kumar V (2009) Anomaly detection: A survey. ACM computing surveys (CSUR) 41(3):1–58
  * Cohen et al [2008] Cohen G, Sax H, Geissbuhler A, et al (2008) Novelty detection using one-class parzen density estimator. an application to surveillance of nosocomial infections. In: MIE, pp 21–26
  * Dasgupta [1999] Dasgupta S (1999) Learning mixtures of Gaussians. In: Proc. IEEE FOCS, pp 634–644
  * Dua and Graff [2017] Dua D, Graff C (2017) UCI machine learning repository. URL http://archive.ics.uci.edu/ml
  * Efron [1965] Efron B (1965) The convex hull of a random set of points. Biometrika 52(3-4):331–343
  * Fauconnier and Haesbroeck [2009] Fauconnier C, Haesbroeck G (2009) Outliers detection with the minimum covariance determinant estimator in practice. Statistical Methodology 6(4):363–379
  * Garcia-Teodoro et al [2009] Garcia-Teodoro P, Díaz-Verdejo JE, Maciá-Fernández G, Vázquez E (2009) Anomaly-based network intrusion detection: Techniques, systems and challenges. Computers & Security 28(1-2):18–28
  * Indyk and Motwani [1998] Indyk P, Motwani R (1998) Approximate nearest neighbors: Towards removing the curse of dimensionality. In: Proc. ACM STOC, pp 604–613
  * Indyk and Naor [2007] Indyk P, Naor A (2007) Nearest-neighbor-preserving embeddings. ACM Transactions on Algorithms (TALG) 3(3):31–es
  * Irigoien et al [2014] Irigoien I, Sierra B, Arenas C (2014) Towards application of one-class classification methods to medical data. In: TheScientificWorldJournal
  * Japkowicz et al [1995] Japkowicz N, Myers C, Gluck MA (1995) A novelty detection approach to classification. In: IJCAI, pp 518–523
  * Khan and Madden [2009] Khan SS, Madden MG (2009) A survey of recent trends in one class classification. In: Irish conference on artificial intelligence and cognitive science, Springer, pp 188–197
  * Kleinberg [1997] Kleinberg JM (1997) Two algorithms for nearest-neighbor search in high dimensions. In: Proc. 29th Annu. ACM STOC, pp 599–608
  * Krizhevsky [2009] Krizhevsky A (2009) Learning multiple layers of features from tiny images
  * Lake et al [2015] Lake BM, Salakhutdinov R, Tenenbaum JB (2015) Human-level concept learning through probabilistic program induction. Science 350(6266):1332–1338
  * LeCun and Cortes [2005] LeCun Y, Cortes C (2005) The mnist database of handwritten digits
  * Liu et al [2008] Liu FT, Ting KM, Zhou ZH (2008) Isolation forest. In: 2008 Eighth IEEE International Conference on Data Mining, IEEE, pp 413–422
  * McDiarmid [1989] McDiarmid C (1989) On the method of bounded differences. In: Siemons J (ed) Surv. Comb., Cambridge University Press, London Mathematical Society Lecture Note Series
  * Mirsky et al [2018] Mirsky Y, Doitshman T, Elovici Y, Shabtai A (2018) Kitsune: an ensemble of autoencoders for online network intrusion detection. Network and Distributed System Security Symposium (NDSS)
  * Perera and Patel [2018] Perera P, Patel VM (2018) Learning deep features for one-class classification. IEEE Transactions on Image Processing 28:5450–5463
  * Rényi and Sulanke [1963] Rényi A, Sulanke R (1963) Uber die convexe hulle von is zufallig gewahlten punkten i. Z Wahr Verw Geb 2:75–84
  * Rényi and Sulanke [1964] Rényi A, Sulanke R (1964) Uber die convexe hulle von is zufallig gewahlten punkten ii. Z Wahr Verw Geb 3:138–147
  * Rousseeuw and Driessen [1999] Rousseeuw PJ, Driessen KV (1999) A fast algorithm for the minimum covariance determinant estimator. Technometrics 41(3):212–223, 10.1080/00401706.1999.10485670
  * Ruff et al [2018] Ruff L, Vandermeulen R, Goernitz N, Deecke L, Siddiqui SA, Binder A, Müller E, Kloft M (2018) Deep one-class classification. In: International conference on machine learning, pp 4393–4402
  * Sakurada and Yairi [2014] Sakurada M, Yairi T (2014) Anomaly detection using autoencoders with nonlinear dimensionality reduction. In: Proceedings of the MLSDA 2014 2Nd Workshop on Machine Learning for Sensory Data Analysis, ACM, MLSDA’14, p 4:4–4:11
  * Schölkopf et al [2000] Schölkopf B, Williamson R, Smola A, Shawe-Taylor J, Piatt J (2000) Support vector method for novelty detection. In: Advances in Neural Information Processing Systems, pp 582–588
  * Siebert [1987] Siebert JP (1987) Vehicle recognition using rule based methods
  * Stallkamp et al [2012] Stallkamp J, Schlipsing M, Salmen J, Igel C (2012) Man vs. computer: Benchmarking machine learning algorithms for traffic sign recognition. Neural Networks
  * Swersky et al [2016] Swersky L, Marques HO, Sander J, Campello RJ, Zimek A (2016) On the evaluation of outlier detection and one-class classification methods. In: 2016 IEEE international conference on data science and advanced analytics (DSAA), IEEE, pp 1–10
  * Tax and Duin [2004] Tax DM, Duin RP (2004) Support Vector Data Description. Machine Learning 54(1):45–66
  * Valiant [1984] Valiant L (1984) Theory of the learnable. Commun ACM 27(11):1134–1142
  * Vempala [2010] Vempala SS (2010) A random-sampling-based algorithm for learning intersections of halfspaces. J ACM 57(6):32:1–32:14
  * Zheng et al [2018] Zheng P, Yuan S, Wu X, Li JY, Lu A (2018) One-class adversarial nets for fraud detection. In: AAAI