# Low-PAPR Joint Channel Estimation and Data Detection in ZP-OTFS System

Omid Abbassi Aghda, Mohammad Javad Omidi, Hamid Saeedi-Sourck O. A. Aghda and
M.J. Omidi are with the Dept. of Electrical and Computer Engineering, Isfahan
University of Technology, Isfahan 84156-83111, Iran (e-mail<EMAIL_ADDRESS>o.abasi@ec.iut.ac.ir). M.J. Omidi is also with the Dept. of Electronics and
Communication Engineering, KCST, Doha 35003, Kuwait. H. Saeedi-Sourck is with
the Dept. of Electrical Engineering, Yazd University, Yazd 89158-18411, Iran.
(e-mail: saeedi@yazd.ac.ir).

###### Abstract

Orthogonal Time Frequency Space (OTFS) systems face significant challenges in
channel estimation due to high pilot overhead and peak-to-average power ratio
(PAPR). To address these issues, we propose a two-step channel estimation
method for Zero-Pad OTFS (ZP-OTFS), a modified OTFS system characterized by
multiple zero rows along the delay axis. This method strategically inserts
pilot sequences into the zero bins of the ZP-OTFS system, effectively
mitigating overhead and PAPR. Comprehensive simulation results validate the
effectiveness of our proposed method, demonstrating its superior performance
over traditional embedded pilot estimation in high Signal-to-Noise Ratio (SNR)
scenarios. Specifically, our method achieves a lower normalized mean square
error (NMSE) and better bit error rates (BER) at high SNRs.

###### Index Terms:

Channel estimation, delay-Doppler domain, OTFS, PAPR, sparse recovery.

##  I Introduction

Reliable communication in high-mobility environments is crucial for the 6th
generation of wireless telecommunication systems. Orthogonal frequency
division multiplexing (OFDM) struggles in these environments due to high
Doppler shift, leading to significant inter-carrier interference. Orthogonal
time frequency space (OTFS), a new modulation technique, addresses this by
multiplexing information symbols into the delay-Doppler (DD) domain, allowing
full channel diversity exploitation. The DD domain represents the channel’s
delay and Doppler characteristics, while the time-frequency (TF) domain
represents the signal’s time and frequency components. However, data detection
and channel estimation in OTFS remain challenging [1].

Data detection in OTFS systems can be computationally demanding, particularly
when using conventional methods such as zero-forcing (ZF) and minimum mean
square error (MMSE). To address this challenge, a low-complexity linear MMSE
(LMMSE) detection method was proposed [2]. This method takes advantage of the
structure of the DD channel matrix to reduce detection complexity.
Additionally, the message passing (MP) algorithm has been used for data
detection [3], offering significantly lower computational complexity compared
to MMSE and ZF detectors. The lower computational complexity of the MP
detector is due to its ability to leverage the sparsity of the DD channel
matrix. However, despite its lower complexity compared to MMSE and ZF
detectors, the MP algorithm still has high complexity. The practicality of the
MP detector may also be limited by its dependence on frame size, the number of
channel taps in the DD domain, and the constellation size of the quadrature
amplitude modulation (QAM) symbols [3]. In conclusion, further research is
needed to develop data detection methods with even lower computational
complexity for OTFS systems. To further reduce detection complexity, the
authors in [4] proposed a delay-time (DT) maximal ratio combining (MRC)
detector for use in OTFS systems. The MRC detector has significantly less
computational complexity compared to MP and LMMSE detectors since its
complexity only depends on the frame size and the maximum delay-spread of the
channel. Furthermore, the MRC detector improves the signal-to-noise ratio
(SNR) of the received signal, resulting in a lower bit error rate (BER).
However, in order to use the MRC detector, a modified version of OTFS known as
zero-pad OTFS (ZP-OTFS) must be employed. ZP-OTFS was specifically designed
for this purpose and involves setting multiple rows along the delay axis to
zero. While this zero-padding technique enables the use of the MRC detector,
it also introduces high system overhead, which is a significant disadvantage
of ZP-OTFS. Overall, the MRC detector offers benefits such as lower complexity
and improved SNR, but its use requires ZP-OTFS, which introduces high system
overhead.

Accurate estimation of the channel state information (CSI) is vital for
wireless communication systems, as the detector’s performance heavily depends
on it. The embedded pilot (EP) method, proposed in [5], is a way to estimate
CSI in OTFS. Due to its use of the sparse nature of the DD channel
representation and its threshold-based detection of channel taps, it has a low
estimation error and low computational cost, respectively. However, the EP
scheme has two drawbacks: it suffers from a high peak-to-average power ratio
(PAPR) due to the high power of the pilot impulse, and it has high pilot
overhead caused by the need to separate the single pilot from information
symbols in the DD domain with guard symbols to prevent interference at the
receiver. To address this overhead and take advantage of the sparse
representation of the wireless channel in the DD domain, a channel estimation
method based on a sparse recovery algorithm was explored in [6]. While this
method outperforms EP channel estimation, it requires more total power
dedicated to pilot sequences, which could be challenging and impose high
impractical PAPR to the system. In contrast, [7] proposes a channel estimation
method, referred to as the pilot with cyclic prefix (PCP) method, that
significantly reduces PAPR compared to methods in [5] and [6]. However, it
consistently incurs higher overhead. This trade-off between PAPR, overhead,
and channel estimation accuracy highlights the complexity of designing
efficient channel estimation methods for OTFS systems. The authors in [8]
present a method with less overhead than others for integer Doppler shifts.
For fractional shifts, the overhead matches that of our approach. However, its
performance cannot reach the EP scheme due to its equalization in the TF
domain. In the pursuit of increasing spectral efficiency, a superimposed DD
domain channel estimation method was proposed in [9]. This method assumes no
pilot overhead for the system and superimposes pilots and data in each DD bin.
An iterative method is used at the receiver for joint channel estimation and
data detection to cancel out pilot interference. However, this method is only
applicable for the doubly-under-spread channel, as it assumes that the
receiver has prior knowledge of the delay and Doppler of each channel
coefficient and that the covariance matrix of CSI is known at the receiver.
It’s important to note that all these methods utilize the DD representation of
the signal for channel estimation.

This paper proposes a pilot design with a two-step channel estimation
algorithm for ZP-OTFS systems. The proposed design addresses the disadvantages
of using ZP-OTFS by inserting Zadoff-Chu pilot sequences in zero bins. Such
design enables us to use the MRC detector, offering the benefits of lower
computational complexity and improved SNR. The proposed method also utilizes
the time domain received sequences to estimate the CSI which leads to reduced
estimation complexity. To combat high PAPR and reduce overhead, our proposed
method spreads pilot symbols in the zero bins of ZP-OTFS system. Additionally,
we use a sparse recovery algorithm to estimate CSI in two steps using time
domain samples while consuming less total power compared to the method in [6].
This approach of using time domain samples for CSI estimation gives us an
advantage over other estimation methods as we do not have to transform the
received signal into DD domain to estimate CSI. In contrast to [9], our
proposed method estimates the delay and Doppler of each tap using a sparse
recovery algorithm and assumes that the covariance matrix of CSI is unknown at
the receiver. Notably, we applied the proposed method in[9] in two steps on
time domain received samples instead of applying it iteratively on DD domain
received samples. Overall we propose a joint channel estimation and data
detection method for the ZP-OTFS system that offers several key advantages.
Notably, our proposed method does not impose high PAPR and maintains almost a
constant PAPR for different numbers of subcarriers. Additionally, our method
increases spectral efficiency, improves power efficiency, and utilizes the
superiority of the MRC detector over other detection methods. Our method also
estimates CSI using time domain samples, eliminating the need to transform the
received signal into the DD domain.

The paper is structured as follows: Section II outlines the system design of
the proposed method, while Section III describes the joint channel estimation
and data detection process. In Section IV, simulation results of the proposed
method are presented and compared with the EP method. Finally, Section V
concludes the paper.

Notation: Boldface upper case ($\mathbf{A}$) for matrices, boldface lower case
($\mathbf{a}$) for vectors, regular lower case ($a$) for scalars, $(.)^{H}$
for Hermitian operator, $\text{{vec}}(\mathbf{A})$ vectorizes the matrix
$\mathbf{A}$ by stacking its columns under each other,
$\text{{vec}}^{-1}(\mathbf{a})$ unvectorize the vector $\mathbf{a}$, $\otimes$
for Kronecker product, $\mathbf{F}_{N}$ for $N$-point discrete Fourier
transform (DFT) matrix, $\lfloor.\rfloor$ and $\left[.\right]_{M}$ are floor
and modulo-$M$ operator.

##  II System Design

In the ZP-OTFS transceiver, the DD domain is divided into $M$ and $N$ bins
along the delay and Doppler axes, respectively. The $l^{th}$ delay bin
($l=0,1,...,M-1$) corresponds to a delay of $\tau=\frac{l}{M\Delta f}$, while
the $k^{th}$ Doppler bin ($k=0,1,...,N-1$) corresponds to a Doppler shift of
$\nu=\frac{k}{NT_{s}}$, where $\Delta f$ is the sub-carrier spacing. The
available bandwidth is $B=M\Delta f$, while $T=NT_{s}$ is the frame duration,
where $T_{s}$ is the ZP-OTFS sub-symbol duration, and $T_{s}\Delta f=1$.

###  II-A The Transmitter

The signal transmitted in the DD domain is depicted in Fig. 1a, where both
information and pilot symbols are arranged. The transmitted signal in the DD
domain can be represented by the matrix
$\mathbf{X}=\mathbf{X}_{d}+\mathbf{X}_{p}\in\mathbb{C}^{M\times N}$, where
$\mathbf{X}_{d}$ and $\mathbf{X}_{p}$ consist of information symbols and pilot
sequences, respectively. In ZP-OTFS system, the value of $l_{ZP}$ (number of
rows which must be zero in ZP-OTFS system along delay axis) must be at least
equal to $l_{max}$ , where $l_{max}$ is the maximum delay spread of the
channel. In our approach, we consider the value $l_{ZP}=l_{max}+1$.
Consequently, the overhead of our proposed method is $(l_{max}+1)N$, which is
much less than the EP scheme [5]. The choice of $l_{ZP}$ ensures that, in the
receiver, one last row of the received DD domain matrix becomes free of
interference from data information effect. This allows us to estimate the
channel in the first step by looking at the last row, which is free of data
interference. Therefore, the first $M-l_{ZP}$ rows of the data matrix
$\mathbf{X}_{d}$ carry information symbols and the others are zero, while in
order to utilize all the available DD resources the last $l_{ZP}$ rows of the
pilot matrix $\mathbf{X}_{p}$ are pilot symbols, generated from a Zadoff-Chu
sequence. This arrangement ensures that the pilot sequences and information
symbols in the matrix $\mathbf{X}$ do not overlap. Information and pilot
symbols are chosen in a way so that the average power of the transmitted
signal becomes one. As a result, the average power of the signal is equal to
one, given that $E\\{|X[l,k]|^{2}\\}=1$, where $X[l,k]$ are the elements of
the matrix $\mathbf{X}$.

\begin{overpic}[width=195.12767pt,tics=10]{fig/transmitter.eps}
\put(0.3,20.8){ \scalebox{0.8}{$\frac{1}{M\Delta f}$}} \put(11.2,7.0){
\scalebox{0.8}{$\frac{1}{NT_{s}}$}} \put(39.0,91.0){ \scalebox{0.8}{$0$}}
\put(39.0,86.5){ \scalebox{0.8}{$1$}} \put(38.3,63.0){
\scalebox{0.8}{\rotatebox{0.0}{$M$}}} \put(41.8,63.0){
\scalebox{0.8}{\rotatebox{0.0}{$-$}}} \put(44.4,62.8){
\scalebox{0.8}{\rotatebox{0.0}{$1$}}} \put(83.4,91.0){ \scalebox{0.8}{$0$}}
\put(83.4,86.5){ \scalebox{0.8}{$1$}} \put(83.1,63.0){
\scalebox{0.8}{\rotatebox{0.0}{$M$}}} \put(86.6,63.0){
\scalebox{0.8}{\rotatebox{0.0}{$-$}}} \put(89.2,63.0){
\scalebox{0.8}{\rotatebox{0.0}{$1$}}} \put(-1.45,68.5){
\scalebox{0.8}{$l_{ZP}$}} \put(38.7,79.7){
\scalebox{0.8}{$\mathbf{XF}_{N}^{H}$}} \put(11.0,96.5){
\scalebox{0.8}{$\mathbf{X}=\mathbf{X}_{d}+\mathbf{X}_{p}$}} \put(56.0,96.5){
\scalebox{0.8}{$\mathbf{\tilde{X}}=\mathbf{\tilde{X}}_{d}+\mathbf{\tilde{X}}_{p}$}}
\put(7.1,58.5){ \scalebox{0.8}{$0$}} \put(12.56,58.5){ \scalebox{0.8}{$1$}}
\put(31.2,58.5){ \scalebox{0.8}{\rotatebox{0.0}{$N$}}} \put(34.2,58.5){
\scalebox{0.8}{\rotatebox{0.0}{$-$}}} \put(36.9,58.5){
\scalebox{0.8}{\rotatebox{0.0}{$1$}}} \put(51.9,58.5){ \scalebox{0.8}{$0$}}
\put(57.5,58.5){ \scalebox{0.8}{$1$}} \put(76.0,58.5){
\scalebox{0.8}{\rotatebox{0.0}{$N$}}} \put(79.0,58.5){
\scalebox{0.8}{\rotatebox{0.0}{$-$}}} \put(81.0,58.5){
\scalebox{0.8}{\rotatebox{0.0}{$1$}}} \put(19.0,56.0){
\scalebox{0.8}{\rotatebox{0.0}{(a)}}} \put(64.5,56.0){
\scalebox{0.8}{\rotatebox{0.0}{(b)}}} \put(46.0,37.0){
\scalebox{0.8}{\rotatebox{0.0}{(c)}}} \put(23.0,1.0){
\scalebox{0.8}{\rotatebox{0.0}{(d)}}} \put(74.9,1.0){
\scalebox{0.8}{\rotatebox{0.0}{(e)}}} \put(3.0,55.5){
\scalebox{0.8}{\rotatebox{0.0}{$l$}}} \put(41.0,95.6){
\scalebox{0.8}{\rotatebox{0.0}{$k$}}} \put(48.0,55.5){
\scalebox{0.8}{\rotatebox{0.0}{$l$}}} \put(86.0,95.6){
\scalebox{0.8}{\rotatebox{0.0}{$n$}}} \put(68.5,22.0){
\scalebox{0.8}{\rotatebox{0.0}{$\mathbf{h}=$}}} \put(-1.6,47.2){
\scalebox{0.8}{\rotatebox{0.0}{$\mathbf{s}=\mathbf{s}_{d}+\mathbf{s}_{p}$}}}
\put(47.7,46.65){
$\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptscriptstyle\bullet$}}}}}$}
\put(49.25,46.65){
$\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptscriptstyle\bullet$}}}}}$}
\put(51.1,46.65){
$\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptscriptstyle\bullet$}}}}}$}
\put(16.0,51.0){ \scalebox{0.8}{$0$}} \put(21.0,51.0){ \scalebox{0.8}{$1$}}
\put(77.0,51.0){ \scalebox{0.8}{$M$}} \put(80.2,51.0){ \scalebox{0.8}{$N$}}
\put(40.5,51.0){ \scalebox{0.8}{$M$}} \put(44.0,51.0){ \scalebox{0.8}{$-$}}
\put(46.5,51.0){ \scalebox{0.8}{$1$}} \put(83.2,51.0){ \scalebox{0.8}{$-$}}
\put(85.9,51.0){ \scalebox{0.8}{$1$}} \put(18.0,41.0){ \scalebox{0.8}{OTFS
sub-symbol}} \put(20.5,25.8){ \scalebox{0.8}{$h\left(\tau,\nu\right)$}}
\put(25.5,5.0){ \scalebox{0.8}{$\tau$}} \put(45.5,20.0){
\scalebox{0.8}{$\nu$}} \put(0.0,8.0){ \scalebox{0.8}{gain}} \put(57.5,40.0){
\scalebox{0.8}{$\tau=\frac{0}{M\Delta f}$}} \put(57.5,34.3){
\scalebox{0.8}{$\tau=\frac{1}{M\Delta f}$}} \put(57.5,28.5){
\scalebox{0.8}{$\tau=\frac{2}{M\Delta f}$}} \put(81.5,38.0){
\scalebox{0.8}{$\nu=\frac{0}{NT_{s}}$}} \put(81.5,29.8){
\scalebox{0.8}{$\nu=\frac{1}{NT_{s}}$}} \put(81.5,22.0){
\scalebox{0.8}{$\nu=\frac{2}{NT_{s}}$}} \put(81.5,14.7){
\scalebox{0.8}{$\nu=\frac{-2}{NT_{s}}$}} \put(81.5,7.0){
\scalebox{0.8}{$\nu=\frac{-1}{NT_{s}}$}} \put(82.5,79.5){
\scalebox{0.8}{vec($\mathbf{\tilde{X}}$)}} \end{overpic} Figure 1: transmitter
system design and channel representation: (a) the DD signal $\mathbf{X}$, (b)
the DT signal $\mathbf{\tilde{X}}$, (c) the time signal $\mathbf{s}$, (d) the
DD channel $h\left(\tau,\nu\right)$, (e) the channel vector $\mathbf{h}$. : DD
data, : DD pilot, : DT data, : DT pilot

The DT representation of the transmitted signal, depicted in Fig. 1b, is
defined as $\tilde{\mathbf{X}}=\mathbf{XF}_{N}^{H}$. As shown in Fig. 1c, the
time-domain signal $\mathbf{s}$ can be obtained as the inverse discrete Zak
transform (IDZT) of the DD-domain signal $\mathbf{X}$, equivalent to
vectorizing the $\mathbf{\tilde{X}}$ matrix as [4]

$\mathbf{s}=\mathbf{s}_{d}+\mathbf{s}_{p}=\text{IDZT}(\mathbf{X})=\textbf{vec}(\mathbf{XF}_{N}^{H})=(\mathbf{F}_{N}^{H}\otimes\mathbf{I}_{M})\mathbf{x},$
(1)

where $\mathbf{s}\in\mathbb{C}^{MN\times 1}$ and
$\mathbf{x}=\textbf{vec}(\mathbf{X})\in\mathbb{C}^{MN\times 1}$. Similar to
the DD representation of the signal, the last $l_{ZP}$ rows along the delay
axis consist of pilot sequences, since we applied the inverse DFT (IDFT) along
the Doppler axis of the DD domain (along rows of the $\mathbf{X}$) to form the
DT representation of the signal. Additionally,
$\mathbf{s}_{d}=\text{IDZT}(\mathbf{X}_{d})$ and
$\mathbf{s}_{p}=\text{IDZT}(\mathbf{X}_{p})$ represent time-domain data and
pilot vectors, respectively, since IDZT is a linear transformation. As shown
in Fig. 1c, pilot symbols can be distinguished from data symbols. In every $M$
samples of the time domain signal, which are defined as OTFS sub-symbols, last
$l_{ZP}$ samples are pilot symbols. Since $l_{ZP}=l_{max}+1$, in the receiver,
every last sample of the OTFS sub-symbol is free of interference and is used
to estimate the channel in the first step. To avoid inter-frame interference,
a cyclic prefix (CP) is added to the beginning of $\mathbf{s}$.

###  II-B Channel Effect

The DD domain channel representation is shown in Fig. 1d, along with the
mathematical expression of the DD channel given by
$h\left(\tau,\nu\right)=\sum_{i=1}^{Q}h_{i}\delta\left(\tau-\tau_{i},\nu-\nu_{i}\right)$.
Here, $\left\\{h_{i}\right\\}_{i=1}^{Q}$ represents the channel coefficients
and $Q=\left(l_{max}+1\right)\left(2k_{max}+1\right)$, where $l_{max}$ and
$k_{max}$ denote the maximum delay and Doppler spread of the channel,
respectively, corresponding to $\tau_{max}=\frac{l_{max}}{M\Delta f}$ and
$\nu_{max}=\frac{k_{max}}{NT}$. The sparsity order of the DD channel is given
by the ratio of non-zero channel coefficients $P$ to $Q$. The value of $P$
represents the number of dominant reflectors, and in the receiver we estimate
their delay, Doppler, and value, represented by $\tau_{i}$, $\nu_{i}$, and
$h_{i}$, respectively [10]. After removing the CP, the input-output relation
is described by

$\mathbf{r}=\mathbf{H}\mathbf{s}+\mathbf{w}=\mathbf{H}\mathbf{s}_{d}+\mathbf{H}\mathbf{s}_{p}+\mathbf{w}$
(2)

where $\mathbf{w}\in\mathbb{C}^{MN\times 1}$ is the noise vector,
$\mathbf{r}\in\mathbb{C}^{MN\times 1}$ is the time domain received signal, and
$\mathbf{H}\in\mathbb{C}^{MN\times MN}$ is the time domain channel matrix
[11]. The channel matrix $\mathbf{H}$ is formulated as

$\mathbf{H}=\sum_{i=1}^{Q}h_{i}\mathbf{\Pi}^{l_{i}}\mathbf{\Delta}^{k_{i}},$
(3)

where $\mathbf{\Pi}\in\mathbb{C}^{MN\times MN}$ is the standard permutation
matrix,
$\mathbf{\Delta}=\text{{diag}}(z^{0},z^{1},...,z^{MN-1})\in\mathbb{C}^{MN\times
MN}$ is the diagonal Doppler matrix, and $z=e^{j2\pi/\left(MN\right)}$ [1]. By
substituting (3) into (2), we obtain (4) as

$\mathbf{r}\\!\\!=\\!\\!\left[\mathbf{\Psi}_{1},\mathbf{\Psi}_{2},\cdots,\mathbf{\Psi}_{Q}\right]\mathbf{h}+\mathbf{w}\\!\\!=\\!\\!\mathbf{\Psi}\mathbf{h}+\mathbf{w}\\!\\!=\\!\\!\mathbf{\Psi}_{d}\mathbf{h}+\mathbf{\Psi}_{p}\mathbf{h}+\mathbf{w},$
(4)

where
$\mathbf{\Psi}_{i}=\mathbf{\Pi}^{l_{i}}\mathbf{\Delta}^{k_{i}}\mathbf{s}\in\mathbb{C}^{MN\times
1}$, $\mathbf{h}\in\mathbb{C}^{Q\times 1}$ represents the channel vector, and
$\mathbf{\Psi}=\mathbf{\Psi}d+\mathbf{\Psi}p\in\mathbb{C}^{MN\times Q}$ is the
time domain signal matrix. Equation (4) represents the input-output relation
of the channel in the time domain. Fig. 1e shows how to form $\mathbf{h}$
using $h\left(\tau,\nu\right)$, where the $i^{th}$ element of $\mathbf{h}$
corresponds to $h_{i}$, and its delay and Doppler are
$l_{i}=\left[i-1\right]_{l_{max}+1}$ and $k_{i}$ as

$k_{i}=\begin{cases}\lfloor\frac{i-1}{l_{max}+1}\rfloor,&\\!\\!\\!\\!\text{if}\\!\
\lfloor\frac{i-1}{l_{max}+1}\rfloor\\!<=k_{max},\\\
\lfloor\frac{i-1}{l_{max}+1}\rfloor-(2k_{max}+1),&\\!\\!\\!\\!\text{if}\
\\!\lfloor\frac{i-1}{l_{max}+1}\rfloor\\!>k_{max}.\end{cases}$ (5)

In [9], the authors proposed a reformulation in (4) in the DD domain. They
assumed that the vector $\mathbf{h}$ is not sparse and considered that the
delay and Doppler of each tap is known in the receiver, allowing it to only
estimate the channel gain $h_{i}$. However, their method was not able to
estimate the taps’ delay and Doppler. Our proposed reformulation in (4) allows
us to estimate the CSI using time domain sequences, eliminating the need to
transform the received signal into the DD domain. Additionally, our approach
takes into account the $\mathbf{h}$’s sparsity, so we do not need to know the
taps’ delay and Doppler. Finally, the paper proposes estimating the channel
vector $\mathbf{h}$ using the orthogonal matching pursuit (OMP) algorithm,
which can be applied to (4). In our research we have utilized OMP algorithm
since its low complexity makes it computationally efficient, while its good
performance ensures accurate results [12].

###  II-C Receiver

As depicted in Fig. 2a, the received signal can be represented in the time
domain as $\mathbf{r}=\mathbf{r}_{d}+\mathbf{r}_{p}$, where $\mathbf{r}_{d}$
and $\mathbf{r}_{p}$ are the channel-effected data and pilot, respectively. To
obtain the corresponding DD domain representation of the time domain signal,
we apply an $N$-point DFT to $\mathbf{\tilde{Y}}$ along the time axis,
yielding $\mathbf{Y}=\mathbf{\tilde{Y}}\mathbf{F}_{N}$, where
$\mathbf{\tilde{Y}}=\text{vec}^{-1}\left(\mathbf{r}\right)$ is the DT
representation of the received signal. This approach is known as the discrete
Zak transform (DZT).

In the receiver, we use time domain channel-affected pilot symbols in
$\mathbf{r}$ to estimate the channel vector $\mathbf{h}$, rather than its DD
representation. We then employ an MRC detector to detect the information
symbols, thanks to our pilot design which enables the use of an MRC detector
in the receiver. To ensure accurate channel estimation, we use the entire time
domain received signal in the next step, comprising both channel-affected data
and pilot, to estimate the channel vector.

\begin{overpic}[width=195.12767pt,tics=10]{fig/receiver.eps} \put(12.0,48.0){
\scalebox{0.8}{$\mathbf{r}$ (2nd step)}} \put(33.0,48.0){
\scalebox{0.8}{$\mathbf{r^{\prime}}_{p}$(1st step)}} \put(56.0,25.0){
\scalebox{0.9}{$\mathbf{r}$}} \put(17.0,39.5){ \scalebox{0.8}{OMP on}}
\put(36.5,39.5){ \scalebox{0.8}{OMP on}} \put(18.3,35.9){ \scalebox{0.8}{Eq.
\eqref{eq:iterative_received_signal_sparse_recovery}}}
\put(39.0,35.9){\scalebox{0.8}{Eq. \eqref{eq:time_coarse_estimation_formula}}}
\put(22.0,25.2){\scalebox{0.8}{Apply Eq.
\eqref{eq:data_without_pilot_time_receiver} on $\mathbf{r}$}}
\put(26.0,14.7){\scalebox{0.8}{MRC detector}}
\put(45.0,31.1){\scalebox{0.8}{$\mathbf{\hat{h}}$}}
\put(25.9,31.1){\scalebox{0.8}{$\mathbf{\hat{h}}$}}
\put(57.3,15.0){\scalebox{0.8}{$\mathbf{\hat{h}}$}}
\put(38.0,19.0){\scalebox{0.8}{$\mathbf{r}_{d}$}}
\put(41.0,11.0){\scalebox{0.8}{DD}} \put(39.0,8.0){\scalebox{0.8}{output}}
\put(26.0,11.0){\scalebox{0.8}{DT}} \put(24.0,8.0){\scalebox{0.8}{output}}
\put(10.0,16.0){\rotatebox{90.0}{\scalebox{0.8}{$\textbf{vec}\left(\mathbf{\hat{\tilde{X}}}_{d}\right)$}}}
\put(13.5,6.0){
\scalebox{0.7}{\rotatebox{0.0}{$\mathbf{\hat{\tilde{X}}}_{d}$}}}
\put(44.0,1.0){ \scalebox{0.7}{\rotatebox{0.0}{$\mathbf{\hat{X}}_{d}$}}}
\put(65.8,46.4){ \scalebox{0.7}{$0$}} \put(72.0,46.4){ \scalebox{0.7}{$1$}}
\put(82.0,46.4){ \scalebox{0.7}{\rotatebox{0.0}{$N$}}} \put(84.4,46.4){
\scalebox{0.7}{\rotatebox{0.0}{$-$}}} \put(86.7,46.4){
\scalebox{0.7}{\rotatebox{0.0}{$1$}}} \par\par\par\put(8.5,73.0){
\scalebox{0.7}{$0$}} \put(16.0,73.0){ \scalebox{0.7}{$1$}} \put(37.5,73.0){
\scalebox{0.7}{\rotatebox{0.0}{$M$}}} \put(40.5,73.0){
\scalebox{0.7}{\rotatebox{0.0}{$-$}}} \put(43.0,73.0){
\scalebox{0.7}{\rotatebox{0.0}{$1$}}} \par\par\put(55.0,51.5){
\scalebox{0.7}{\rotatebox{0.0}{$\mathbf{r^{\prime}}_{p}=$}}}
\par\put(0.0,68.5){ \scalebox{0.7}{\rotatebox{0.0}{$\mathbf{r}=$}}}
\par\par\put(80.0,73.0){ \scalebox{0.7}{\rotatebox{0.0}{$M$}}}
\put(83.0,73.0){ \scalebox{0.7}{\rotatebox{0.0}{$N$}}} \put(85.5,73.0){
\scalebox{0.7}{\rotatebox{0.0}{$-$}}} \put(87.7,73.0){
\scalebox{0.7}{\rotatebox{0.0}{$1$}}} \put(44.7,68.3){
$\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptscriptstyle\bullet$}}}}}$}
\put(46.3,68.3){
$\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptscriptstyle\bullet$}}}}}$}
\put(47.9,68.3){
$\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptscriptstyle\bullet$}}}}}$}
\put(76.0,51.3){
$\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptscriptstyle\bullet$}}}}}$}
\put(77.6,51.3){
$\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptscriptstyle\bullet$}}}}}$}
\put(79.2,51.3){
$\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.7}{$\scriptscriptstyle\bullet$}}}}}$}
\put(93.0,68.5){\scalebox{0.8}{(a)}} \put(93.0,51.5){\scalebox{0.8}{(b)}}
\put(30.0,0.0){\scalebox{0.8}{(c)}}
\put(57.0,25.0){\scalebox{1.0}{\rotatebox{180.0}{{\rotatebox{0.0}{$\begin{cases}&\\\
&\\\ &\\\ &\\\ &\\\ &\\\ &\end{cases}$}}}}} \put(67.0,25.0){
\scalebox{0.7}{Joint channel estimation}} \put(64.0,21.0){ \scalebox{0.7}{and
data detection algorithm}} \par\end{overpic} Figure 2:  receiver system
design: (a) the time vector $\mathbf{r}$, (b) channel-affected pilot vector
without data interference $\mathbf{r^{\prime}}_{p}$ , (c) proposed algorithm.
: channel-affected pilot symbols without data interference : channel-affected
pilot symbols with data interference, : channel-affected data symbols with
pilot interference

##  III Joint Channel Estimation and Data Detection

This paper uses a two-step method for channel estimation and data detection.
The first step involves obtaining a preliminary estimate of the channel,
followed by interference cancellation and the implementation of the MRC
detector for data detection. In the second step, both the detected data and
pilot sequences are jointly used as pilots to refine the channel estimation,
resulting in a more accurate channel representation.

Our method builds upon the approach in [9], but with several key differences.
Our pilot design allows for a more accurate channel estimation in the first
step, resulting in improved performance compared to [9]. While the method in
[9] requires multiple iterations to accurately estimate the channel, our
approach achieves a high level of accuracy in just two steps. Additionally,
our pilot design enables the use of a MRC detector, which detects data in the
DT domain. Since we estimate the channel using time-domain sequences, there is
no need to transform the received data into the DD domain.

###  III-A First Step

We estimate the CSI using channel-affected pilot entries in $\mathbf{r}$ that
are free from data interference. These entries form a new vector
$\mathbf{r^{\prime}}_{p}\in\mathbb{C}^{N\times 1}$, shown in Fig. 2b. We
rewrite (4) as

$\mathbf{r^{\prime}}_{p}=\mathbf{\Psi^{\prime}}_{p}\mathbf{h}+\mathbf{w^{\prime}},$
(6)

where $\mathbf{w}^{\prime}\in\mathbb{C}^{N\times 1}$ represents the noise
vector for $\mathbf{r^{\prime}}_{p}$ entries, and
$\mathbf{\Psi^{\prime}}_{p}\in\mathbb{C}^{N\times Q}$ is the time-domain pilot
matrix of the first step. It is important to note that the matrix
$\mathbf{\Psi^{\prime}}_{p}$ only consists of the rows of $\mathbf{\Psi}$ that
contribute to forming $\mathbf{r^{\prime}}_{p}$. Now, performing OMP on (6)
yields the estimated channel vector $\mathbf{\hat{h}}$ [12]. Afterward, to
detect data, we cancel out the channel-affected pilot symbols of the received
signal $\mathbf{r}$

$\mathbf{r}_{d}=\mathbf{r}-\mathbf{\Psi}_{p}\mathbf{\hat{h}}=\mathbf{\Psi}_{d}\mathbf{h}+\mathbf{\Psi}_{p}\left(\mathbf{h}-\mathbf{\hat{h}}\right)+\mathbf{w},$
(7)

where $\mathbf{r}_{d}\in\mathbb{C}^{MN\times 1}$ denotes the received channel-
affected data vector with the influence of channel-affected pilot symbols
eliminated. In our proposed pilot scheme, the last entries of each OTFS sub-
symbol are initially occupied by pilot symbols. However, these pilot symbols
are subsequently eliminated. Following their removal, we employ the MRC
detector to detect the information symbols from the vector $\mathbf{r}_{d}$.
This approach allows us to effectively utilize the MRC detector in the
presence of pilot symbols. At this stage, the DT output representation of the
detected data is denoted by $\mathbf{\hat{\tilde{X}}}_{d}$. Since the MRC
detector produces DT output, we utilize this DT output of the detected symbol
in the next step, as illustrated in Fig. 2c. The term
$\mathbf{\Psi}_{p}\left(\mathbf{h}-\mathbf{\hat{h}}\right)$ in (7) indicates
the amount of interference that remains due to the imperfect channel
estimation. To minimize this interference, we need a second step to obtain a
more accurate estimate of the channel vector, which will improve the detection
performance. The first step and the second step of our proposed method are
shown in Fig. 2c. This figure indicates that we use $\mathbf{r^{\prime}}_{p}$
in the first step to estimate the channel vector $\mathbf{\hat{h}}$ and after
removing the channel-affected pilot symbols, the MRC detector uses
$\mathbf{\hat{h}}$ and $\mathbf{r}_{d}$ to detect information symbols named
$\mathbf{\hat{\tilde{X}}}_{d}$ in the DT domain.

###  III-B Second Step

In this step, the time domain pilot sequences $\mathbf{s}_{p}$ and detected
data
$\mathbf{\hat{s}}_{d}=\textbf{vec}\left(\mathbf{\hat{\tilde{X}}}_{d}\right)$
from the first step are jointly used as pilot to accurately estimate the
channel and reduce detection errors, shown in Fig. 2c. To achieve this, we
rewrite (4) as

$\mathbf{r}\\!=\\!\left(\\!\mathbf{\Psi}_{p}\\!+\mathbf{\hat{\Psi}}_{d}\\!\right)\mathbf{h}\\!+\\!\left(\\!\mathbf{\Psi}_{d}\\!-\\!\mathbf{\hat{\Psi}}_{d}\\!\right)\mathbf{h}\\!+\\!\mathbf{\hat{w}}\\!=\\!\left(\\!\mathbf{\Psi}_{p}\\!+\\!\mathbf{\hat{\Psi}}_{d}\\!\right)\mathbf{h}\\!+\\!\mathbf{\bar{w}},$
(8)

where the term $\mathbf{\hat{\Psi}}=\mathbf{\Psi}_{p}+\mathbf{\hat{\Psi}}_{d}$
is considered as the joint pilot and $\mathbf{\hat{\Psi}}_{d}$ are time domain
detected data matrix that is formed using $\mathbf{\hat{s}}_{d}$ according to
(4). Unlike the first step, this approach uses all the entries of $\mathbf{r}$
to estimate the channel, including those with data interference. The channel
vector is then estimated using the OMP algorithm on (8).

As shown in Fig. 2c, to detect data, similar to previous step, we remove the
channel-affected pilot from the received signal using (7), and employ the MRC
detector to detect the DD representation of the data matrix
$\mathbf{\hat{X}}_{d}$. As the channel vector is estimated more accurately
than in the first step, the MRC detector results in better performance in the
second step.

##  IV Simulation Results

In this section, we evaluate the performance of our proposed channel
estimation method. The system operates at a carrier frequency of $f_{c}=4$ GHz
and a subcarrier spacing of $\Delta f=15$ kHz, with a maximum speed of the
fading channel set to $v=500$ km/h. Our method demonstrates a contribution by
achieving lower overhead and PAPR compared to the EP scheme, and lower
overhead with similar PAPR compared to the PCP scheme. This competitive
performance validates the effectiveness of our method and its potential for
practical implementation in future wireless communication systems. We use the
EVA channel model and Jakes’ formula to generate DD channel parameters [1],
assuming integer delay and Doppler for each tap. Our pilot design could
potentially be extended to work with fractional channel parameters in future
researches. The value of single pilot tone in the EP scheme is
$\sqrt{(4k_{\text{max}}+1)(2l_{\text{max}}+1)}$, while our method considers
less pilot overhead, resulting in lower dedicated pilot power. Parameters $M$
and $N$ are set to 64 for simulating BER and normalized mean square error
(NMSE) curves while 4-QAM alphabet is used.

Fig. 3a compares the NMSE versus SNR for our method and the EP scheme. The
first step of our method underperforms EP, but the second step outperforms EP
at high SNRs due to less error in the first step. However, it underperforms at
low SNRs due to suboptimal channel estimation. A crossover point occurs at an
SNR of about 11 dB, indicating a performance transition . This crossover will
impact the BER curve.

Fig. 3b displays the BER versus SNR, with the second step’s BER matching the
EP and known CSI. Despite the first step’s NMSE not reaching EP, its BER is
comparable. The crossover in the BER curves of the second step and EP is due
to the crossover in NMSE of channel estimation, emphasizing the impact of
channel estimation quality on BER.

Fig. 4a illustrates the complementary cumulative distribution function (CCDF)
for the PAPR of the transmitted signal for different values of $M$ and $N$.
The PAPR of the proposed method is significantly lower than that of the EP
signal. This can be attributed to the fact that in the EP scheme, only one
high power single pulse in the DD domain is utilized. Consequently, as $M$ and
$N$ increase, leading to an increase in the channel parameters $l_{max}$ and
$k_{max}$ respectively, more power is allocated to a single pilot in the EP
scheme, resulting in a high PAPR. In contrast, our proposed system distributes
pilots across the DD domain, which results in a low PAPR. Interestingly, this
low PAPR changes only slightly with an increase in $M$ and $N$. It is also
worth noting that the PCP method exhibits a similar PAPR to our proposed
system.

Fig. 4b illustrates the number of overhead bins for the proposed method, the
PCP method, and the EP scheme for different values of $M$ and $N$. As $N$
increases, the overhead of the system also increases. In the EP and PCP
methods, this is due to the additional guard used to prevent interference from
data symbols to the pilot symbols, which results in increased overhead.
However, our proposed method circumvents this issue by estimating the channel
in two steps. This approach not only decreases the overhead, making it more
efficient than both the EP scheme and the PCP method, but also makes our
proposed method particularly effective for systems where low overhead is
crucial.

(a)  (b)

Figure 3: (a) The NMSE of the proposed method (first step and second step)
with EP, (b) The BER of the proposed method with EP and known CSI.

(a)  (b)

Figure 4: (a) CCDF versus PAPR of the transmitted signal, (b) Number of pilot
overhead versus $M$ for different $N$.

##  V conclusion

In this paper, a two-step joint channel estimation and data detection scheme
for ZP-OTFS systems based on sparse recovery algorithms was proposed. In the
first step, the OMP algorithm was used for channel estimation, and in the
second step, data detection was performed using the MRC detector. The proposed
method offered significant improvements in both spectral and power efficiency
while imposing a low PAPR on the transmitter without affecting the system
performance.

## References

  * [1] Y. Hong, T. Thaj, and E. Viterbo, _Delay-Doppler Communications: Principles and Applications_. Academic Press, 2022.
  * [2] S. Tiwari, S. Sekhar Das, and V. Rangamgari, “Low complexity LMMSE receiver for OTFS,” _IEEE communication letter_ , vol. 23, no. 12, pp. 2205–2209.
  * [3] P. Raviteja, K. T. Phan, Y. Hong, and E. Viterbo, “Interference cancellation and iterative detection for orthogonal time frequency space modulation,” _IEEE Transactions on Wireless Communications_ , vol. 17, no. 10, pp. 6501–6515, 2018.
  * [4] T. Thaj and E. Viterbo, “Low complexity iterative rake decision feedback equalizer for zero-padded OTFS systems,” _IEEE Transactions on Vehicular Technology_ , vol. 69, no. 12, pp. 15 606–15 622, 2020.
  * [5] P. Raviteja, K. T. Phan, and Y. Hong, “Embedded pilot-aided channel estimation for OTFS in delay-Doppler channels,” _IEEE Transactions on Vehicular Technology_ , vol. 68, no. 5, pp. 4906–4917, 2019.
  * [6] L. Zhao, W. Gao, and W. Guo, “Sparse bayesian learning of delay-Doppler channel for OTFS system,” _IEEE Communication Letters_ , vol. 24, no. 12, pp. 2766–2769, 2020.
  * [7] P. S. Sanoopkumar and A. Farhang, “A practical pilot for channel estimation of OTFS,” 2022. [Online]. Available: https://www.techrxiv.org/articles/preprint/A_Practical_Pilot_for_Channel_Estimation_of_OTFS/21594162
  * [8] H. Zhang, X. Huang, and J. A. Zhang, “Low-overhead OTFS transmission with frequency or time domain channel estimation,” _IEEE Transactions on Vehicular Technology_ , pp. 1–14, 2023.
  * [9] H. B. Mishra, P. Singh, A. K. Prasad, and R. Budhiraja, “OTFS channel estimation and data detection designs with superimposed pilots,” _IEEE Transactions on Wireless Communications_ , vol. 21, no. 4, pp. 2258–2274, 2021\.
  * [10] S. Srivastava, R. K. Singh, A. K. Jagannatham, and L. Hanzo, “Bayesian learning aided simultaneous row and group sparse channel estimation in orthogonal time frequency space modulated mimo systems,” _IEEE Transactions on Communications_ , vol. 70, no. 1, pp. 635–648, 2022.
  * [11] P. Raviteja, Y. Hong, E. Viterbo, and E. Biglieri, “Practical pulse-shaping waveforms for reduced-cyclic-prefix OTFS,” _IEEE Transactions on Vehicular Technology_ , vol. 68, no. 1, pp. 957–961, 2019.
  * [12] E. Crespo Marques, N. Maciel, L. Naviner, H. Cai, and J. Yang, “A review of sparse recovery algorithms,” _IEEE Access_ , vol. 7, pp. 1300–1322, 2019\.


11institutetext: Department of Computing Sciences
Umeå University 90740, Sweden
11email<EMAIL_ADDRESS>
# Concept Drift Detection using Ensemble of Integrally Private Models

Ayush K. Varshney  11 0000-0002-8073-6784 Vicenç Torra  11 0000-0002-0368-8037

###### Abstract

Deep neural networks (DNNs) are one of the most widely used machine learning
algorithm. DNNs requires the training data to be available beforehand with
true labels. This is not feasible for many real-world problems where data
arrives in the streaming form and acquisition of true labels are scarce and
expensive. In the literature, not much focus has been given to the privacy
prospect of the streaming data, where data may change its distribution
frequently. These concept drifts must be detected privately in order to avoid
any disclosure risk from DNNs. Existing privacy models use concept drift
detection schemes such ADWIN, KSWIN to detect the drifts. In this paper, we
focus on the notion of integrally private DNNs to detect concept drifts.
Integrally private DNNs are the models which recur frequently from different
datasets. Based on this, we introduce an ensemble methodology which we call
’Integrally Private Drift Detection’ (IPDD) method to detect concept drift
from private models. Our IPDD method does not require labels to detect drift
but assumes true labels are available once the drift has been detected. We
have experimented with binary and multi-class synthetic and real-world data.
Our experimental results show that our methodology can privately detect
concept drift, has comparable utility (even better in some cases) with ADWIN
and outperforms utility from different levels of differentially private
models. The source code for the paper is available here. 111Accepted for
publication in MLCS co-located with ECML-PKDD 2023.

###### Keywords:

Data privacy Integral privacy Concept Drift Private drift Deep neural networks
Streaming data.

##  1 Introduction

In recent years, the interest in deep learning models has witnessed a steady
increase, despite encountering various challenges such as explainability,
privacy, and data dependency. To address these issues, significant
advancements have been made, including approaches to enhance explainability
[1], privacy-preserving techniques [2], adopting a data-centric perspective to
facilitate model training with high-quality data, and more. However, limited
attention has been given in the context of streaming data, which refers to the
continuous arrival of data in real-world scenarios, often accompanied by the
problem of concept drift. Concept drift implies that the statistical
properties of the data may change over time, necessitating the model to adapt
to these changes to ensure reliable predictions. Noisy data at one point of
time may become useful data over time. These changes in data distributions can
be due to various hidden factors. Handling of such drifts is a must and has
been employed in many applications such as spam detection [3], demand
prediction [4]. Learned models must have the ability to detect concept drifts
and incorporate them by retraining on the new data. Three types of concept
drifts have been shown in Fig. 1. Abrupt drifts are sudden changes in the data
distribution. E.g. complete lockdown in many countries due to COVID-19
pandemic. Gradual drifts are the drifts which changes the distribution over
time. E.g. in fraud detection system, fraudsters adapt according to the
improving security policies in place. Incremental concept drift are the drifts
where old concepts vanishes completely with time. E.g. after lifting COVID-19
lockdown, people may be hesitant to return to their normal behaviour.

Figure 1: Types of drifts in the data

In the literature of concept drift detection, there has been several
algorithms which can detect concept drifts such as Adaptive windowing (ADWIN)
[5] and its variant, and Kolmogorov-Smirnov Windowing (KSWIN). These are the
two prominent drift detection methods used in the streaming settings. To
detect drifts, these techniques were originally proposed assuming the
availability of true labels which is unrealistic in most real-world
assumptions. ADWIN employs two windows, one fixed size and one variable size,
which slide over the incoming data stream. The fixed size window keeps the
most recent points and the variable size window keeps the earlier points. If
the statistics of the two windows differs significantly then ADWIN indicates
that the drift has been detected.

In case of DNNs, training requires huge amount of data and acquisition of
ground truth to detect drift can be very costly. A recently proposed
uncertainty drift detection scheme [6] detects drift during inference without
the availability of true labels. It computes values for prediction uncertainty
using dropout in the DNNs and uses entropy of these uncertainty values to
detect drifts. Another approach to get prediction uncertainty is through the
ensemble of DNN models. Different DNNs produce different probabilities during
predictions and the overall uncertainty in their predictions can be used to
detect the drift. In the literature, almost none of the approaches focus on
the privacy perspective of drift detection.

Privacy is a crucial factor to take into account in concept drift detection as
data is often sensitive. There exists many privacy models such as k-anonymity
[7], differential privacy (DP) [8], integral privacy [9] and others for static
environment but their counter-parts for online learning are rather limited.
For online learning, k-anonymity [10] tries to protect against identity
disclosure by guaranteeing k-anonymity for addition, deletion, and updating
the records but may fail to protect attribute disclosure; differential privacy
(DP) perturbs the data or the model in order to generate privacy-preserving
outputs against the disclosure of sensitive information. Even though DP
provides theoretically sound privacy-preserving models, it has a number of
practical drawbacks. For instance, when aiming for high privacy (small
$\epsilon$), the amount of noise added can become very high. Moreover, there
is a finite privacy budget for multiple searches, and high sensitivity queries
demand a bigger amount of noise. DP may struggle with the privacy budget when
the data distribution changes frequently. You may end up loosing utility or
privacy or both in the long run. Also, the addition of a lot of noise to the
output can make machine learning models less useful. Most of the privacy
approaches in the online learning literature focuses on either storing the
data or predicting the output privately. None or very few approaches in
literature focuses on detecting drifts privately.

In our approach, we have considered Integral Privacy as an alternative to DP
to generate high utility, privacy-preserving machine learning models.
Integrally-private models provide sound defence against membership inference
attacks and model comparison attacks. A membership inference attack is about
getting access to the records used in the training process. On similar lines,
a model comparison attack gives intruder access to the complete training set
or to a huge portion of the training set through intersectional analysis. A
machine learning model is integrally private [9] if it can be generated by
multiple disjoint datasets. For an intruder whose aim is to do membership
inference attacks or model comparison attacks, integrally-private models
create ambiguity as the models are generated by multiple disjoint datasets. It
has been proven in [11] that under some conditions it is possible to obtain,
with probability close to one, the same parameter updates for a model with
multiple minimatchs. They also find that a small fraction of a dataset can
also lead to good results. One of the first works which shows the framework
for model comparison attack and the defence by integral privacy for decision
trees was given in [12]. The authors generate the complete model space and
return the integrally private decision tree models which have approximately
same model parameters. Generating complete (or approximately complete) model
space can be a very computationally intensive task for a dataset with only few
thousand instances.

For DNNs, generating model space and comparing models to find integrally
private models can be tricky. This is due to the fact that for a given layer
of two different models, equivalent neurons can be placed in different
positions. Also, due to huge number of learning parameters in DNNs, there can
be very few recurring models. In order to overcome these challenges for DNNs,
a relaxed variant of integral privacy, $\Delta$-Integral privacy, was proposed
in [13]. $\Delta$-Integral privacy ($\Delta$-IP) considers models which are at
most $\Delta$ distance apart, and then recommends the mean of these models (in
the $\Delta$ range) as the integrally private model. The $\Delta$-IP algorithm
can recommend up to X number of integrally private models which can be used as
an ensemble of private models to detect concept drifts in streaming data. In
this paper, we propose a methodology for drift detection through an ensemble
of $\Delta$-integrally private models. We compute an ensemble of $\Delta$-IP
models and use them to compute a measure of prediction uncertainty. This
prediction uncertainty of $\Delta$-IP models on the incoming datastream is
used to detect concept drift. Our methodology only requires true labels to
recompute the $\Delta$-IP models once a drift has been detected. We also
present the probabilistic analysis for the recurring models. Our theoretical
analysis is inspired from the work in [11] which focuses on forging a
minibatch. In our case, the analysis focus on learning similar parameters
after complete training.

Our experimental setup shows results for ANN (one hidden layer with 10
neurons) and DNN of 3 hidden layers (10-20-10 hidden layer architecture). We
evaluate our proposed methodology for 3 real-world dataset and 4 synthetic
dataset. We have also compared our results with different levels of privacy in
DP models. We show that our approach outperforms the DP alternatives. We find
that ensemble of integrally private models can successfully detect concept
drifts while maintaining the utility of non-private models.

The rest of the paper is organized as follows. Section 2 describes the
background for the proposed drift detection methodology. Section 3 describes
our proposed work. Section 4 gives the experimental analysis. The paper
finishes with some conclusions and future work.

##  2 Background

In this section we describe the major concepts that are needed in this work.

###  2.1 Uncertainty in Neural Networks

Understanding the uncertainty of a model is essential to understand the
model’s confidence. In DNNs, class probabilities can not be the proxy for
model’s confidence. For unseen data, DNNs may give high probability even when
the predictions are wrong. This can be the case in concept drifts i.e, the
prediction may be uncertain but the system can give high class probability.
Ensemble methods find the uncertainty using predictions from the family of
DNNs. Here you train multiple DNNs with different initializations. In this way
you generate a set of confidence parameters from multiple DNNs, and the
variance of the output can be interpreted as the model uncertainty. In our
work, we estimate the model uncertainty using an ensemble of private models.
With drift in estimated uncertainty as an indicator for concept drift, we can
employ drift detection schemes such as ADWIN, KSWIN to detect concept drift.

###  2.2 Model Comparison Attack and $\Delta$-Integral privacy

Integral privacy [9] is a privacy model which provides defense against model
comparison attacks and membership inference attacks. In a model Comparison
Attack [12, 13], an intruder aims to get access to the sensitive information
or do membership inference analysis by comparing the model parameters. A model
comparison attack assumes that the intruder has access to the global model $M$
trained using algorithm $A$ on the training set $X$ a subset of the population
$\mathcal{D}$, and some background information $S^{*}(\subseteq\mathcal{D})$.
The intruder wants to get the maximum (or total) number of records used in the
training process. I.e. the intruder wants to maximize access to $X$. The
intruder draws a number of samples $S_{1},S_{2},...,S_{n}$ from $\mathcal{D}$
and compares the model generated by each $S_{i}$ with the global model $M$.
Then, the intruder selects the $S_{i}$ corresponding to the most similar model
to $M$ and hence guesses the records used in the training. In case that there
are multiple models similar to $M$, the intruder can do intersectional
analysis for membership inference. That is, find common data records which
lead to the model $M$. In case of DNNs, model comparison can be tricky as
highlighted before in [13]. The comparison between models is done by comparing
each layer and neurons in respective layers.

In order to defend against such attacks, integral privacy requires you to
chose a model which recurs from different disjoint datasets. Disjoint datasets
are needed to avoid intersectional analysis. In this way an intruder cannot
identify the training set because multiple training sets lead to the same
model. As explained in Section 1, due to the huge number of parameters in DNNs
there are very few recurring models. $\Delta$-IP relaxes the equivalence
relation between neurons. It allows the two models to be considered as equal
if neurons in each layer of the respective model are at most $\Delta$ distance
apart. Formally, $\Delta$-IP can be defined as follows.

$\Delta$-Integral Privacy Let $\mathcal{D}$ be the population,
$S^{*}\subset\mathcal{D}$ be the background knowledge, and
$M\subset\mathcal{M}$ be the model generated by an algorithm $A$ on an unknown
dataset $X\subset D$. Then, let $Gen^{*}(M,S,\Delta)$ represent the set of all
generators consistent with background knowledge $S^{*}$ and model $M$ or
models at most $\Delta$ different. Then, k-anonymity $\Delta$-IP holds when
$Gen^{*}(M,S,\Delta)$ has atleast k-elements and

$\bigcap_{S\in Gen^{*}(G,S^{*},\Delta)}S=\emptyset$ (1)

##  3 Proposed Methodology

Figure 2: Flowchart drift detection using ensemble of $\Delta$-Integrally
Private Models

In this section, we provide the details of our proposed methodology which we
call Integrally private drift detection (IPDD) scheme. Our proposed IPDD
methodology detects drifts with unlabeled data but assumes that true labels
are available on request. Our approach is based on the detection of concept
drifts from the measure of uncertainty in prediction by ensemble of private
models. Previous works [14] [6] show that prediction uncertainty from DNN is
correlated with prediction error. We argue on similar lines and use drift in
prediction uncertainty as a proxy for detecting concept drift. We use Shanon
entropy to evaluate the uncertainty over different $c$ class labels.

Algorithm 1 Algorithm to generate k $\Delta$-Integrally private DNNs for
training data $D$. The algorithm return an ensemble of k private models

Inputs: $D$ \- Training data

Output: returns k integrally private models

Algorithm:

$N$ \- Size of subsamples

$\Delta$ \- Privacy parameter

S = Generate_subsample($D$, $N$)

$\triangleright$ Generate n disjoint subsamples of size $N$

ModelList = [[]]

while $S_{i}\leftarrow S$ do $\triangleright$ For all samples in $S$

$M_{i}\leftarrow$ Train DNN on $S_{i}$

present $\leftarrow$ False

if $M_{i}$ is utmost $\Delta$ distance apart from models in ModelList then

Put $M_{i}$ in the same bucket

present $\leftarrow$ True

end if

if present is False then

Append $M_{i}$ in ModelList $\triangleright$ Create a new bucket with $M_{i}$

end if

end while

Returns mean of top k recurring models from ModelList

Algorithm 2 Drift detection using $\Delta$-Integrally private models

Inputs: $\mathcal{D}$ \- Dataset

Algorithm:

training_data = Initial_data($\mathcal{D}$)

$\triangleright$ Initial Data to train private DNNs

Private_Models = Algorithm_1(training_data)

while $\mathcal{D}$ has elements do $\triangleright$ While stream has incoming
data

Receive incoming data $x_{t}$

pred, uncertainty $\leftarrow$ Private_Models.predict($x_{t}$)

Add uncertainty to ADWIN

if ADWIN detects drift then

Request true labels $y_{t}$ for $x_{t}$

Update training_data with $x_{t},y_{t}$

Private_Models = Algorithm_1(training_data)

end if

end while

Then any change detection algorithm such as ADWIN can be employed to detect
drifts using this uncertainty measure. We chose ADWIN as it works well with
real-valued inputs. The flowchart of the methodology is shown in Fig. 2. First
$k$ integrally private models are computed from the initial available training
data. With incoming data instances, we predict the output and input the
prediction uncertainty from each of the k private models to ADWIN. If drift
has been detected, true labels are requested and the training data must be
updated with new instances. Here, our methodology does not require true labels
to detect concept drift. New private models are computed from the updated
training data. If the training data exceeds the threshold, records are removed
on a first-come, first-served basis. In case there is no drift, then the
prediction for new instances continues.

Algorithm 1 describes the computation for k private models. First, samples
(i.e., sets of records) are generated from the training data in such a way
that pairs of samples have empty intersection (i.e., they do not share any
record). Models for these samples are computed using the same initialization.
Models within $\Delta$ distance apart are kept in the same bucket. Buckets are
sorted in descending order according to the number of models in each bucket.
The algorithm then returns the mean of the top k recurring set of models as an
ensemble of k integrally private models.

Algorithm 2 describes how to detect drifts privately. First, it uses initial
available data as training data and computes private models using Algorithm 1
on the training data. Predictions on new incoming instances are used to
compute the uncertainty measure and to see if the drift is detected using
ADWIN. If the drift is detected, true labels must be requested, then training
data must be updated and the private models are recomputed on a new training
data. This process continues as long as the new data is available for
prediction.

###  3.1 Theoretical Analysis

In this section, we present the probabilistic analysis for the recurrence of
DNNs. DNNs are trained using mean samplers such as SGD, Adam etc. This
analysis is inspired by the forgeability analysis done in [11]. The analysis
in [11] computes the probability of forging a single minibatch while we focus
on probabilistic analysis of learning the same model parameters after learning
from different training data. Let us consider a set of disjoint datasamples,
$D_{1},D_{2},...,D_{m}$, i.i.d. (independent and identically distributed)
sampled from a given $N$-dimensional dataset $\mathcal{D}$ with some
distribution. Here, each of the $D_{i}$ is composed of $b$ minibatches
$\hat{x}={x_{1},x_{2},...,x_{b}}$. $M_{1},M_{2},...,M_{m}$ be the DNN models
we want to train which have the same initialization. The update rule looks
like $g(w,\hat{x})=\frac{1}{b}\sum_{i=1}^{b}g(w,x_{i})$. The update rule
$g(w,x)$ can be seen as a random variable with mean $\mu$ and $\sigma^{2}$
($=\sum_{i=1}^{N}\sigma_{i}^{2}$, where $\sigma_{i}^{2}$ is the covariance of
the $i^{th}$ component of a random variable $x$ sampled with distribution
$\mathcal{D}$) as the trace of the covariance matrix. The mean sampler for the
batch $\hat{x},\;g(w,\hat{x})$ is still $\mu$
($\frac{1}{b}\sum_{i=1}^{b}g(w,x_{i})=\frac{1}{b}*b\mu$) but individual
variance will get the $\frac{1}{b}$ i.e. now the trace of the covariance
matrix is $\frac{1}{b}\sigma^{2}$.

Since the data samples are i.i.d sampled from $\mathcal{D}$ and each $x_{i}$
is i.i.d sampled from data samples, then $x_{i}$ follows the same distribution
of $\mathcal{D}$. Then by Markov’s inequality we can say that,

$\displaystyle
P(|g(w,\hat{x})-\mu|_{2}\geq\Delta)=P(|g(w,\hat{x})-\mu|_{2}^{2}\geq\Delta^{2})\leq\frac{E(|g(w,\hat{x})-\mu|_{2}^{2})}{\Delta^{2}}$
(2)

Figure 3: Two models $M_{j},M_{k}$ at most $\Delta^{2}$ distance apart from
$\mu$ with probability defined in Eq. (5)

Here the first equality is true by the property of monotonicity of squares and
the second is Markov’s inequality. Note that $E(|g(w,\hat{x})-\mu|_{2}^{2})$
is just the trace of the covariance matrix $(\frac{1}{b}\sigma^{2})$. Then, we
can write:

$\displaystyle
P(|g(w,\hat{x})-\mu|_{2}^{2}\geq\Delta^{2})\leq\frac{\sigma^{2}}{b\Delta^{2}}$
$\displaystyle\Rightarrow P(|g(w,\hat{x})-\mu|_{2}^{2}\leq\Delta^{2})\geq
1-\frac{\sigma^{2}}{b\Delta^{2}}$ (3)

Let us consider two models $M_{j}\text{ and }M_{k},$ training on data samples
$D_{j}\text{ and }D_{k}$ with $\hat{x_{j}},\hat{x_{k}}$. From Eq. (5), we can
say
$P(|g(w,\hat{x}_{j})-\mu|_{2}^{2}\leq\Delta^{2})\geq(1-\frac{\sigma^{2}}{b\Delta^{2}})$
and
$P(g(w,\hat{x}_{k})-\mu|_{2}^{2}\leq\Delta^{2})\geq(1-\frac{\sigma^{2}}{b\Delta^{2}})$
at $i^{th}$ epoch

As demonstrated in Fig. 3, if $g(w,\hat{x}_{j}),g(w,\hat{x}_{k})$ are in the
$\Delta^{2}$ ball of $\mu$ with probability defined in Eq. (5) then with
probability $\geq(1-\frac{\sigma^{2}}{b\Delta^{2}})^{2}$ we can say both
models are utmost $2\Delta^{2}$ distant. I.e.
$P(|g(w,\hat{x}_{j})-g(w,\hat{x}_{k})|\leq
2\Delta^{2})\geq(1-\frac{\sigma^{2}}{b\Delta^{2}})^{2}$. Then, the probability
that out of $m$ models there exists two models which are in the $\Delta^{2}$
ball of $\mu$ would be:

$\displaystyle P(|g(w,\hat{x_{j}})-g(w,\hat{x_{k}})|_{2}^{2}\leq
2\Delta^{2})\geq\sum_{r=2}^{m}\binom{m}{r}\left(1-\frac{\sigma^{2}}{b\Delta^{2}}\right)^{r}\left(\frac{\sigma^{2}}{b\Delta^{2}}\right)^{m-r}$
(4)

This is equivalent to having at least $2$ models out of $m$ in the
$2\Delta^{2}$ ball of $\mu$. The probability that $m$ models are in the
$2\Delta^{2}$ ball of $\mu$ would be:

$\displaystyle P(|g(w,\hat{x_{j}})-g(w,\hat{x_{k}})|_{2}^{2}\leq
2\Delta^{2})\geq\left(1-\frac{\sigma^{2}}{b\Delta^{2}}\right)^{m}$ (5)

Equation (6) and (7) represents the probability of weights updating in the
$2\Delta^{2}$ ball of $\mu$ for a single epoch. For $T$ iterations, the
probability that there exists a model having weight updates in the
$2\Delta^{2}$ ball of $\mu$ is at least
$(\sum_{r=2}^{m}\binom{m}{r}(\frac{\sigma^{2}}{b\Delta^{2}})^{m-r}(1-\frac{\sigma^{2}}{b\Delta^{2}})^{r})^{T}$.
After T epochs, the probability of $m$ models to be in the $2\Delta^{2}$ ball
of $\mu$ will be at least $((1-\frac{\sigma^{2}}{b\Delta^{2}})^{m})^{T}$.

So, for samples sampled i.i.d. from some dataset, we can conclude that the
lower bound for the probability that there exists recurrent models within
$2\Delta^{2}$ ball is at least
$(\sum_{r=2}^{m}\binom{m}{r}(\frac{\sigma^{2}}{b\Delta^{2}})^{m-r}(1-\frac{\sigma^{2}}{b\Delta^{2}})^{r})^{T}$.
In addition, the probability that all the m models are in the $2\Delta^{2}$
ball of $\mu$ is at least $((1-\frac{\sigma^{2}}{b\Delta^{2}})^{m})^{T}$. From
this discussion, we have the following theorems.

###### Theorem 3.1

If $D_{1},D_{2},...,D_{m}$ are i.i.d samples from the dataset $\mathcal{D}$
with some distribution and $b$ is the number of minibatches used for training
in each of $T$ epochs. Then under similar training environment i.e. same
initialization, learning rate, etc. with probability greater than
$(\sum_{r=2}^{m}\binom{m}{r}(\frac{\sigma^{2}}{b\Delta^{2}})^{m-r}(1-\frac{\sigma^{2}}{b\Delta^{2}})^{r})^{T}$,
the model will recur.

###### Theorem 3.2

With the above mentioned properties, a model satisfies k-anonymous integral
privacy with probability atleast
$(\sum_{r=k}^{m}\binom{m}{r}(\frac{\sigma^{2}}{b\Delta^{2}})^{m-r}(1-\frac{\sigma^{2}}{b\Delta^{2}})^{r})^{T}$

Proof: See Eq. (6) for proof. k-Anonymity integral privacy is equivalent to
having at least $k$ models out of $m$ in the $\Delta$ ball of $\mu$.

Remark on the choice of $\Delta,m$: In order to generate higher k-Anonymity
integrally private models, from theorem 2 we can say that increasing the
number of i.i.d samples $(m),\;b\;(\text{Number of batches used in each
epochs})\text{ and }\Delta$ (the distance value) increases the probability of
getting recurrent models.

Role of initialization: The probabilistic analysis presented here gives you
the lower bound that the model will recur from the samples having similar
distribution. The probability can further improve when models are initialized
with the same weight as the learning from similar dataset would result in the
similar learning for the models.

##  4 Experiments

In this section, we present the experimental results for our proposed
methodology. We will show that our methodology performs well with Categorical,
Real, and Integer data with arbitrary number of classes. We perform our
experiments on 3 real-world datasets namely Cover type (CovType), Electricity,
and Susy dataset [15]. We also run our experiments on artificially generated
Sine data and Insects data with abrupt, gradual and incremental drifts [16].
Table 1 shows the number of instances and other details of these datasets.

Dataset | # instances | # attribute | Data type | # classes
---|---|---|---|---
CovType | 581012 | 54 |  Categorical Integer | 7
Electricity | 45312 | 8 |  Real Integer | 2
Susy | 5000000 | 18 | Real | 2
Sine | 200000 | 4 | Real | 2
Insects_ab | 52848 | 33 | Real | 6
Insects_grad | 24150 | 33 | Real | 6
Insects_incre | 57018 | 33 | Real | 6
Table 1: Details of the used Datasets

For our experiments, we have randomly considered a NN with a single hidden
layer (10 neurons) architecture (We will call this architecture ANN) and a
three hidden layer NN architecture with 10-20-10 number of neurons (we will
call it DNN). For our experimental purpose we have chosen $\Delta=0.01$ and
ADWIN parameter, $\delta=0.001$. For all the datasets, we have initially
trained ANN and DNN over 10% of the dataset, and then stream is evaluated with
2% of the dataset at each time instance.

We compare our results (Integrally private drift detection, IPDD) with No re-
training (No_retrain), ADWIN with unlimited label availability (ADWIN_unlim),
and ADWIN with limited labels (ADWIN_lim). We have used three levels of
differentially private models: high privacy ($\epsilon=0.1$) under limited
label availability (DP_01), moderate privacy ($\epsilon=0.5$) under limited
label availability (DP_05) and low privacy ($\epsilon=1.0$) under limited
label availability (DP_10). All the results have been computed for ANN as well
as DNN. The No_retraining model approach does not check for drifts, it trains
the model with initial data once and only does the prediction for the rest of
the data stream. For ADWIN_unlim we assume it has access to all the true
labels of the incoming data stream and it detects drifts using the true labels
only. The ADWIN_lim can have true labels upon request but detect the drifts
using uncertainty through the ADWIN model. Similar settings were assumed for
DP_01, DP_05, DP_10 and IPDD.

We can observe that our methodology IPDD has better or comparable accuracy
score for both ANN and DNN. Table LABEL:tab:acc_score provides the accuracy of
the learned models. IPDD performs better than its counterparts for CovType and
Electricity datasets, it has comparable accuracy score for Insects_ab and
comparable results with ADWIN_unlim method. Table LABEL:tab:mcc_score provides
the results for Mathews correlation coefficient (mcc) in the range $[-1,1]$
(higher the better). MCC is a reliable statistical rate which assigns high
value to a classifier if it performs good in all four confusion matrix
categories. In comparison with differentially private models, IPDD performs
much better than all three levels of differential privacy for all datasets
except Insects_grad and Insects_incre. For ANN, IPDD performs performs better
for CovType dataset and has comparable mcc rate with the rest. In case of
DNNs, IPDD performs better than its counterparts for Electricity, Susy and
Insects_ab datasets; and performs comparable results for the rest of the
datasets. Table LABEL:tab:auc_score shows the score for the area under the
curve (auc score). Auc score is the probability that a model ranks a random
positive instance higher than a random negative instance. Table
LABEL:tab:auc_score highlights that auc score for IPDD’s ANN and DNN performs
better than its counterparts in case of all the datasets except Insect_grad
and Insect_incre dataset.

Figure 4: Drift detected by different $\epsilon$-differentially private models

We observed that with the addition of noise DP models may struggle to detect
drifts. Table LABEL:tab:drift_detected shows the number of drifts detected by
each method. It highlights that DP models at times may detect very few drifts
because of the noise. On the other hand, IPDD detects comparable drifts to
ADWIN_unlim and ADWIN_lim for both ANN and DNN. Table LABEL:tab:drift_detected
also highlights that proposed IPDD does not detect unnecessary drifts i.e.
IPDD does not necessary detect any drift when there is none (counterparts of
IPDD does not detect any drift). As expected when the noise for DP models
decreases, more drifts were detected by DP models as shown in Fig. 4.

In most of the cases, differentially private models does not perform as good
as IPDD models even when the $\epsilon$ is very high (very low privacy). This
is shown in Fig. 5. It compares the accuracy score between DNN model of DP and
IPDD for all the datasets. Fig. 5(a), 5(b), 5(c), 5(d), 5(e), and 5(f)
highlights that even though the accuracy score improves for DP models, IPDD
still performs better than DP. Only in case of Fig. 5(g) the DP model has
slightly better accuracy score than IPDD even in case of high privacy.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

Figure 5:  Comparison of the accuracy score between differential privacy and
integral privacy: (a) CovType (b) Electricity (c) Susy (d) Sine (e) Insect_ab
(f) Insect_grad (g) Insect_incr.

(a)

(b)

Figure 6: K-anonymity integral privacy against (a) increasing $\Delta$ (b)
increasing the number of i.i.d samples

(a)

(b)

(c)

Figure 7:  Number of integral private models in an ensemble against (a)
increasing the number of i.i.d samples (b) increasing the number of different
initialization. (c) k-anonymity against different initialization

Section 3.1 shows the probabilistic analysis on the lower bound of the
recurrence of Integrally private models. As discussed in the remarks of
Section 3.1, the higher the value of $\Delta$ the higher the number
k-anonymity in integrally private models. For models with same initialization
trained on 100 i.i.d samples ($D_{1},D_{2},...,D_{100}$) from Sine dataset,
the k in k-anonymity Integral privacy has been plotted against increasing
$\Delta$ in Fig. 6(a). As can be seen increasing the $\Delta$ value leads to
the higher value of k in k-anonymity Integral privacy. Similarly, we can see
in Fig. 6(b) that for a fixed $\Delta=0.01$, increasing the number of i.i.d
samples leads to a higher value of k in k-Anonymity integral privacy. It is
important to highlight the distinction between k-anonymity and ensemble of k
models chosen with k-anonymity Integral privacy. Simply, in k-Anonymity
integral privacy, there exists a bucket which has at least k models while we
require an ensemble of k such buckets.

We observe in Fig. 7(a) that for a fixed $\Delta=0.01$, increasing the number
of i.i.d samples also leads to the higher k in k-Anonymity integral privacy.
In cases where all the models are clustered to only one IP model, generating
an ensemble of such models can be tricky. An easier way to avoid this problem
is to generate an ensemble of k-anonymity models using different
initializations. The reason for this could be attributed to the comparable
learning process when using similar training data. For 100 i.i.d samples of
Sine data, in Fig. 7(b), x-axis shows the number of different initialization
and y-axis shows the number of different IP models in an ensemble. It is
important to note here that for 100 samples if the number of IP models
increases in an ensemble, k-anonymity of each IP model will decrease as
depicted in Fig. 7(c).

###  4.1 Limitations of our approach:

The analysis of our method as well as our experiment permits us to state the
following.

  1. 1.

Generating k-anonymous integrally private models requires training on large
number of samples which is a time consuming process. The proposed IPDD
methodology has running time as the cost of privacy.

  2. 2.

As shown in Section 3.1, the generation of integrally private models is a
probabilistic approach and depends on the samples selected. That is, different
runs can provide different results.

##  5 Conclusion and Future work

In this paper we have presented a private drift detection methodology called
’Integral Privacy Drift Detection’ (IPDD). Our methodology detects drifts
using an ensemble of k-anonymity integrally private models. Simply, we
generate an ensemble of k models which are recurring from multiple disjoint
datasets. Our methodology does not require the ground truth to detect concept
drift but assumes they are available for retraining. We find that our
methodology can successfully detect concept drifts while maintaining the
utility of non-private models. It is useful in generating models which have
comparable (better in some cases) accuracy score, mcc score and auc score
against ADWIN with unlimited label availability and limited label
availability. In comparison with its differentially private counterpart, IPDD
perfoms significantly better in most of the cases.

As shown above different parameters can lead to different levels of privacy.
It can also affect the number of drifts detected and the utilty of the model.
Fine-tuning of these parameters for each application is an interesting
direction for future work. Furthermore, extension of our work for non-i.i.d.
samples would be an interesting future direction.

Acknowledgement:  This work was partially supported by the Wallenberg Al,
Autonomous Systems and Software Program (WASP) funded by the Knut and Alice
Wallenberg Foundation. The computations were enabled by the supercomputing
resource Berzelius provided by National Supercomputer Centre at Linköping
University and the Knut and Alice Wallenberg foundation.

## References

  * [1] Patrick Schwab and Walter Karlen  “Cxplain: Causal explanations for model interpretation under uncertainty”  In _Advances in Neural Information Processing Systems_ 32, 2019
  * [2] Reza Shokri and Vitaly Shmatikov  “Privacy-preserving deep learning”  In _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , 2015, pp. 1310–1321
  * [3] Joao Gama, Pedro Medas, Gladys Castillo and Pedro Rodrigues  “Learning with drift detection”  In _Advances in Artificial Intelligence–SBIA 2004: 17th Brazilian Symposium on Artificial Intelligence, Sao Luis, Maranhao, Brazil, September 29-Ocotber 1, 2004. Proceedings 17_ , 2004, pp. 286–295  Springer
  * [4] Indrė Žliobaitė, Mykola Pechenizkiy and Joao Gama  “An overview of concept drift applications”  In _Big data analysis: new algorithms for a new society_ Springer, 2016, pp. 91–114
  * [5] Albert Bifet and Ricard Gavalda  “Learning from time-changing data with adaptive windowing”  In _Proceedings of the 2007 SIAM international conference on data mining_ , 2007, pp. 443–448  SIAM
  * [6] Lucas Baier, Tim Schlör, Jakob Schöffer and Niklas Kühl  “Detecting concept drift with neural network model uncertainty”  In _arXiv preprint arXiv:2107.01873_ , 2021
  * [7] Pierangela Samarati  “Protecting respondents identities in microdata release”  In _IEEE transactions on Knowledge and Data Engineering_ 13.6 IEEE, 2001, pp. 1010–1027
  * [8] Cynthia Dwork  “Differential Privacy”  In _Automata, Languages and Programming_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 1–12
  * [9] Vicenç Torra, Guillermo Navarro-Arribas and Edgar Galván  “Explaining recurrent machine learning models: integral privacy revisited”  In _International Conference on Privacy in Statistical Databases_ , 2020, pp. 62–73  Springer
  * [10] Julián Salas and Vicenç Torra  “A general algorithm for k-anonymity on dynamic databases”  In _Data privacy management, cryptocurrencies and blockchain technology_ Springer, 2018, pp. 407–414
  * [11] Anvith Thudi, Hengrui Jia, Ilia Shumailov and Nicolas Papernot  “On the necessity of auditable algorithmic definitions for machine unlearning”  In _31st USENIX Security Symposium (USENIX Security 22)_ , 2022, pp. 4007–4022
  * [12] Navoda Senavirathne and Vicenç Torra  “Integrally private model selection for decision trees”  In _computers & security_ 83 Elsevier, 2019, pp. 167–181
  * [13] Ayush K Varshney and Vicenç Torra  “Integrally Private Model Selection for Deep Neural Networks”  In _DEXA 2023, DOI: https://doi.org/10.21203/rs.3.rs-2944008/v1_ , 2023
  * [14] Alex Kendall and Yarin Gal  “What uncertainties do we need in bayesian deep learning for computer vision?”  In _Advances in neural information processing systems_ 30, 2017
  * [15] Dheeru Dua and Casey Graff  “UCI Machine Learning Repository”, 2017  URL: http://archive.ics.uci.edu/ml
  * [16] Vinicius MA Souza, Denis M Reis, Andre G Maletzke and Gustavo EAPA Batista  “Challenges in benchmarking stream learning algorithms with real-world data”  In _Data Mining and Knowledge Discovery_ 34 Springer, 2020, pp. 1805–1858