Privacy-Preserving Image Classification in the Local Setting

Differential privacy (DP) ensures that an adversary should not be able to reliably infer any individual sample from the computation of a dataset, even with unbounded computational power and access to every other samples. Given two data database $A,A^{\prime}$, it is said that $A,A^{\prime}$ are neighbors if they differs on at most one row. The formal definition of a $(\epsilon,\delta)$-differential private mechanism over $A$ is defined below:

Definition 1 ($\epsilon,\delta$)-differential privacy(?; ?): A randomized mechanism $\mathcal{F}$ is $(\epsilon,\delta)$-differentially private if for every two neighboring database $A,A^{\prime}$ and for any $\mathcal{O}\subseteq Range(\mathcal{F})$,

$$Pr[\mathcal{F}(A)\in\mathcal{O}]\leq e^{\epsilon}Pr[\mathcal{F}(A^{\prime})\in\mathcal{O}]+\delta$$

(1)

where $Pr[\cdot]$ denotes the probability of an event, $Range(\mathcal{F})$ denotes the set of all possible outputs of the algorithm $\mathcal{F}$. The smaller $\epsilon,\delta$ are, the closer $Pr[\mathcal{F}(A)\in\mathcal{O}]$ and $Pr[\mathcal{F}(A^{\prime})\in\mathcal{O}]$ are, and the stronger privacy protection gains. When $\delta=0$, the mechanism $\mathcal{F}$ is $\epsilon$-differentially private, which is a stronger privacy guarantee than $\epsilon,\delta$-differential privacy with $\delta>0$.

Similar to DP, a stronger setting of local privacy is investigated by Duchi et al. (?), namely Local Differential Privacy. It considers a scenario that a data curator needs to collect data from data owners, and infer the statistical information from these data. The data owner is assumed to trust no one, and would perturb the data before sharing with data curator. The formal definition is given below:

Definition 2 $\epsilon$-Local Differential Privacy(?; ?): A randomized mechanism $\mathcal{G}$ satisfies $\epsilon$-Local Differential Privacy ($\epsilon$-LDP) if for any input $v_{1}$ and $v_{2}$ and for any $\mathcal{S}\subseteq Range(\mathcal{G})$:

$$Pr[\mathcal{G}(v_{1})\in\mathcal{S}]\leq e^{\epsilon}Pr[\mathcal{G}(v_{2})\in\mathcal{S}]$$

(2)

Comparing to DP, LDP provides a stronger privacy model, while entails more noise.

Randomized Response(?) is a decades-old technique which is designed to collect the statistical information regarding sensitive survey questions. The original technique is used for frequency estimation of a particular input. For social research, the interviewee is asked to provide an answer regarding the sensitive question, such as marijuana usage. To protect the privacy, the interviewee is asked to spin a spinner unobserved by the interviewer. Rather than answering the sensitive question directly, the interviewee only tells yes or no according to whether the spinner points to the true answer. Suppose that the interviewer wants to estimate the population of using marijuana and asks the interviewee if he has ever used the marijuana. And the probability that the spinner points to yes is $p$, then the spinner points to no is with probability $1-p$. Thus an unbiased maximum likelihood estimates of the true population proportion is given by $\frac{p-1}{2p-1}+\frac{n_{1}}{(2p-1)n}$, where $n$ is the number of participating interviewees and $n_{1}$ is the amount of reporting yes. It(?) shows that this mechanism satisfies $(ln\frac{p}{1-p})$-LDP.

Randomized response could also be generalized to multiple choices, where the domain of the choices is $[d],d>2$. Suppose the randomized method is $\mathcal{G},\forall v,s\in[d]$, the perturbation is defined below:

$$Pr[\mathcal{G}(v)=s]=\begin{cases}p=\frac{e^{\epsilon}}{d-1+e^{\epsilon}}\text{, if }v=s\\ q=\frac{1-p}{d-1}=\frac{1}{d-1+e^{\epsilon}}\text{, if }v\neq s\end{cases}$$

(3)

In terms of maintaining the original statistical information, even though (?) proves that randomized response is universally optimal for mutual information and $f$-divergences optimization, there’s no clear guide about how to employ this mechanism in particular machine learning algorithm.

Principal Component Analysis is a well known tool for unsupervised learning which finds the subspace that preserves the most variance of the original data, however, it is not effective in the supervised learning since the labeling information is ignored in the computation. Discriminant Component Analysis (DCA)(?), basically a supervised PCA, is proposed recently as a complement for supervised learning, where the signal subspace components of DCA are associated with the discriminant power regarding the classification effectiveness while the noise subspace components of DCA are tightly coupled with the recoverability. Since the rank of the signal subspace is limited by the number of classes, DCA is capable to support classification using a small number of components.

Consider a $K$-class data set consisting of $N$ samples $X=[x_{1},x_{2},\dots,x_{n}]^{T}$, in which $x_{i}\in{\mathbb{R}}^{m}$. Each sample $x_{i}$ associates with a class label $y_{i}$ where $y_{i}\in\{C_{1},C_{2},\dots,C_{k}\}$. Let $\mu$ denotes the centroid of the total mass, $\mu_{k}$ denotes the centroid of the samples in class $C_{k}$, and $N_{k}$ denotes the number of samples in class $C_{k}$. The signal matrix is represented by the between-class scatter matrix:

$$S_{B}=\sum^{K}_{k=1}N_{k}(\mu_{k}-\mu)(\mu_{k}-\mu)^{T}$$

(5)

The noise matrix is characterized by the following within-class scatter matrix:

$$S_{W}=\sum^{K}_{k=1}\sum_{i:y_{i}=C_{k}}(x_{i}-\mu_{k})(x_{i}-\mu_{k})^{T}$$

(6)

The total scatter matrix $\bar{S}$ can be written as follows:

$$\bar{S}=S_{B}+S_{W}$$

(7)

In DCA, two ridge parameters $\rho$ and $\rho^{\prime}$ are incorporated in the noise matrix $S_{W}$ and the signal matrix $S_{B}$ as follows:

$$S_{B}^{\prime}=S_{B}+\rho^{\prime}\mathbb{I}$$

(8)

$$S_{W}^{\prime}=S_{W}+\rho\mathbb{I}$$

(9)

where $\mathbb{I}$ is the identity matrix. Therefore, the regulated scatter matrix is denoted as:

$$\bar{S}^{\prime}=S_{B}^{\prime}+S_{W}^{\prime}=\bar{S}+(\rho+\rho^{\prime})\mathbb{I}$$

(10)

DCA performs spectral decomposition of the pre-whitened scatter matrix, $D_{DCA}$:

$$D_{DCA}=(S_{W}^{\prime})^{-1}\bar{S}^{\prime}=U\Lambda U^{T}$$

(11)

where $\Lambda$ holds the the monotonically decreasing eigenvalues, and U holds the associated eigenvectors. To form a projection matrix, it chooses $k$ eigenvectors with the largest eigenvalues to form a projection matrix $W_{dca}\in{\mathbb{R}}^{m\times k}$, in which each column is an eigenvector. And the raw data is transformed by multiplying the projection matrix:

$$X_{proj}=X\times W_{dca}$$

(12)

As Fig.1 shows, in this paper, we consider the following problem: Given $n$ Data Owners, each Data Owner $O_{i}$ holds a set of images that are represented as a $m$-dimensional feature vectors. For ease of analysis, here it is assume that only one image is possessed by $O_{i}$ and it is denoted as $x_{i}=\{x_{i1},x_{i2},\dots,x_{im}\},x_{ij}\in[d]$. Each image $x_{i}$ associates with a label $y_{i}$, for instance, the images held by each data owner is about the handwritten digit, and $y_{i}$ indicates the corresponding digit of $x_{i}$; the untrustworthy Data User would like to fit an image classifier with $x_{i},y_{i},i\in\{1,2,\dots,n\}$ as input while satisfying $\epsilon_{j}$-LDP for the $j$th feature of $x_{i}$. It should be noted that the images held by each data owner are perturbed independently, so there are no difference to perturb a set of images or a single image at $O_{i}$. With respect to image classification, the effectiveness of both Naive Bayes and KNN classifiers have been demonstrated through previous work(?; ?), which are studied in this work.

For the threat model, the adversary is intended to learn individual image $x_{i}$, who could be either the untrustworthy data user, a participating data owner or an outside attacker. It assumes that adversaries might have arbitrary background knowledge and there might be a collusion among them. The goal is maintain the data utility in terms of image classification while protecting the data privacy.

In this paper, we mainly investigate to use Randomized Response to satisfy $\epsilon_{ij}$-LDP for $x_{ij}$, which is perturbed independently. Given a $x_{i},y_{i}$, we assume that the class label $y_{i}\in\{C_{1},C_{2},\dots,C_{k}\}$ and $x_{i}^{\prime}$ is the vector after perturbation. Firstly, we show how to build the Naive Bayes classifier by leveraging the aggregation result of the perturbed input.

In our problem, for each training data $x_{i}$, $x_{ij}$ is independently perturbed by randomized response at $O_{i}$ and $x_{i}^{\prime}$ is sent to the Data User. And the frequency of each appeared value $v$ is served as the building block of the classifier training, more specifically, the frequency of value $v$ in the $j$th feature that belongs to $C_{k}$ should be counted, in which is denoted as $c_{j}(v)$. However, due to the noise injected by randomized response, the observation doesn’t reflect the true proportion of value $v$. Thus given the number of observation of $v$ in the $j$th feature, denoted as $\sum_{j}v$, $c_{j}(v)$ is estimated as(?):

	$\displaystyle\hat{c_{j}(v)}$	$\displaystyle=\frac{\sum_{j}v-nq_{j}}{p_{j}-q_{j}}$		(13)
		$\displaystyle=\frac{\sum_{j}v-n(1-p_{j})/(d-1)}{p_{j}-(1-p_{j})/(d-1)}$		(14)

where $p_{j}=Pr[x_{ij}^{\prime}=v]$, if $x_{ij}=v$, which refers to Equ.3, and $n$ is the number of observations that in $C_{k}$. It can be further shown that $\hat{c_{j}(v)}$ is an unbiased estimator. Assuming $f_{v,j}$ is the true proportion that value $v$ occurs in $j$th feature, $E[\hat{c_{j}(v)}]$ would be:

	$\displaystyle E[\hat{c_{j}(v)}]$	$\displaystyle=E[\frac{\sum_{j}v-nq_{j}}{p_{j}-q_{j}}]$		(15)
		$\displaystyle=\frac{nf_{v,j}p_{j}+n(1-f_{v,j})q_{j}-nq_{j}}{p_{j}-q_{j}}$		(16)
		$\displaystyle=nf_{v,j}$		(17)

And $Var[\hat{c_{j}(v)}]$ is given as below:

	$\displaystyle Var[\hat{c_{j}(v)}]$	$\displaystyle=\frac{nq_{j}(1-q_{j})}{(p_{j}-q_{j})^{2}}+\frac{nf_{v,j}(1-p_{j}-q_{j})}{p_{j}-q_{j}}$		(18)
		$\displaystyle=n(\frac{d-2+e^{\epsilon_{j}}}{(e^{\epsilon_{j}}-1)^{2}}+\frac{f_{v,j}(d-2)}{e^{\epsilon_{j}}-1})$		(19)

where $Var[\hat{c_{j}(v)}]$ is in $O(\frac{nd}{e^{\epsilon}})$. Furthermore, $\hat{\mu_{j}}$ is the estimated mean of feature $j$ given the frequency estimation of each appeared value:

$$\hat{\mu_{j}}=\frac{\sum_{v}v\hat{c_{j}(v)}}{n}$$

(20)

Correspondingly, $E[\hat{\mu_{j}}]$ and $Var[\hat{\mu_{j}}]$ are computed as follow:

	$\displaystyle E[\hat{\mu_{j}}]$	$\displaystyle=E[\frac{\sum_{v}v\hat{c_{j}(v)}}{n}]$		(21)
		$\displaystyle=\frac{E[\sum_{v}v\hat{c_{j}(v)]}}{n}$		(22)
		$\displaystyle=\frac{\sum_{v}vE[\hat{c_{j}(v)]}}{n}$		(23)
		$\displaystyle=\sum_{v}vf_{v,j}$		(24)

	$\displaystyle Var[\hat{\mu_{j}}]$	$\displaystyle=Var[\frac{\sum_{v}v\hat{c_{j}(v)}}{n}]$		(25)
		$\displaystyle=\frac{Var[\sum_{v}v\hat{c_{j}(v)]}}{n^{2}}$		(26)
		$\displaystyle=\frac{\sum_{v}v^{2}Var[\hat{c_{j}(v)]}}{n^{2}}$		(27)

It can be seen that $\hat{\mu_{j}}$ is an unbiased estimator and $Var[\hat{\mu_{j}}]$ is in $O(\frac{d}{ne^{\epsilon}})$. And the Mean-Squared-Error (MSE) of $\hat{\mu_{j}}$ is equal to $Var[\hat{\mu_{j}}]$. In practical, the unbiased estimator for the sum of counts is adopted, which is $\sum_{v}\hat{c_{j}(v)}$ and it results in the same order of MSE.

A different mean estimator is given by replacing the denominator $n$ with the corrected sum of frequencies, where $\hat{\mu_{j}^{rr}}$:

$$\hat{\mu_{j}^{rr}}=\frac{\sum_{v}v\hat{c_{j}(v)}}{\sum_{v}\hat{c_{j}(v)}}$$

(28)

Correspondingly, by using multivariate Taylor expansions, $E[\hat{\mu_{j}^{rr}}]$ and $Var[\hat{\mu_{j}^{rr}}]$ are computed as follow:

	$\displaystyle E[X]=E[\sum_{v}v\hat{c_{j}(v)}]=\sum_{v}E[v\hat{c_{j}(v)}]=\sum_{v}vE[\hat{c_{j}(v)}]\leq nd^{2}$		(29)
	$\displaystyle var[X]=var[\sum_{v}v\hat{c_{j}(v)}]=\sum_{v}var[v\hat{c_{j}(v)}]=\sum_{v}v^{2}var[\hat{c_{j}(v)}]$		(30)
	$\displaystyle E[Y]=E[\sum_{v}\hat{c_{j}(v)}]=\sum_{v}E[\hat{c_{j}(v)}]=n$		(31)
	$\displaystyle var[Y]=var[\sum_{v}\hat{c_{j}(v)}]=\sum_{v}var[\hat{c_{j}(v)}]=nd(\frac{d-2+e^{\epsilon_{j}}}{(e^{\epsilon_{j}}-1)^{2}})$		(32)

	$\displaystyle E[\frac{X}{Y}]\approx\frac{E[X]}{E[Y]}-\frac{cov[X,Y]}{E[Y]^{2}}+\frac{E[X]}{E[Y]^{3}}var[Y]$		(33)
	$\displaystyle\approx\frac{E[X]E[Y]^{2}}{E[Y]^{3}}-\frac{cov[X,Y]E[Y]}{E[Y]^{3}}+\frac{E[X]var[Y]}{E[Y]^{3}}$		(34)
	$\displaystyle\approx\frac{E[X]E[Y]^{2}-cov[X,Y]E[Y]+E[X]var[Y]}{E[Y]^{3}}$		(35)
	$\displaystyle\leq\frac{n^{3}d^{2}-ncov[X,Y]+n^{2}d^{3}\frac{d-2+e^{\epsilon_{j}}}{(e^{\epsilon_{j}}-1)^{2}}}{n^{3}}$		(36)
	$\displaystyle var[\frac{X}{Y}]\approx\frac{var[X]}{E[Y]^{2}}-\frac{2E[X]}{E[Y]^{3}}cov[X,Y]+\frac{E[X]^{2}}{E[Y]^{4}}var[Y]$		(37)
	$\displaystyle\approx\frac{var[X]E[Y]^{2}}{E[Y]^{4}}-\frac{2E[X]E[Y]cov[X,Y]}{E[Y]^{4}}+\frac{E[X]^{2}var[Y]}{E[Y]^{4}}$		(38)
	$\displaystyle\approx\frac{var[X]E[Y]^{2}-2E[X]E[Y]cov[X,Y]+E[X]^{2}var[Y]}{E[Y]^{4}}$		(39)
	$\displaystyle cov[X,Y]=E[XY]-E[X]E[Y]$		(40)
	$\displaystyle MSE[\frac{X}{Y}]=Var[\frac{X}{Y}]+(E[\frac{X}{Y}]-\frac{X}{Y})^{2}$		(41)

The Nearest Centroid Classifier (NCC) is a classification model that assigns to testing data the label of the class of training data whose mean is closest to the observation in terms of certain distance metrics. Given training data $x_{i},y_{i},i\in\{1,2,\dots,n\}$, the per-class centroid is computed as follows:

$$\mu_{k}=\frac{1}{N_{k}}\sum_{i:y_{i}=C_{k}}x_{i}$$

(42)

where $N_{k}$ is the number of training data that belonging to class $C_{k}$. For a testing data $x_{t}$, the predicted class is given by,

$$\hat{y_{t}}=\operatorname*{argmin}_{k}\ell_{p}(x_{t},\mu_{k})$$

(43)

where $\ell(\cdot)$ is the $p$-norm distance between $x_{t}$ and $\mu_{k}$. To build the NCC from the perturbed data, the estimated centroid is adopted:

$$\hat{\mu_{k}}=\frac{\sum_{v\in C_{k}}v\hat{c_{j}(v)}}{N_{k}}$$

(44)

Suppose there are $N$ images $\{E_{i}\}^{N}_{i=1}$, each image has the same size $h\times w$, the patch size is $k_{h}\times k_{w}$, the number of filters in the $r$th convolution layer is $L_{r}$. $E_{i}$ is denoted as $[e_{i1},e_{i2},\dots,e_{i\widetilde{h}\widetilde{w}}]$, and $e_{ij}\in{\mathbb{R}}^{k_{h}\times k_{w}}$ denotes the $j$th vectorized patch in $E_{i}$, where $\widetilde{h}=(h-k_{h}+2z)/t+1,\widetilde{w}=(w-k_{w}+2z)/t+1$, and $t$ is the size of stride, $z$ is the the size of zero padding. Additionally, assuming there are $K$ classes, each image $E_{i}$ associates with a class label $y_{i}$ where $y_{i}\in\{C_{1},C_{2},\dots,C_{k}\}$, and each class $C_{k}$ contains $N_{k}$ images. For the first convolution layer, the overall patch mean $\mu$ and within class patch mean $\mu_{k}$ is calculated as below:

	$\displaystyle\mu$	$\displaystyle=\frac{\sum_{i=1}^{N}\sum_{j=1}^{\widetilde{h}\widetilde{w}}e_{ij}}{N}$		(45)
	$\displaystyle\mu_{k}$	$\displaystyle=\frac{\sum_{i\in C_{k}}^{N}\sum_{j=1}^{\widetilde{h}\widetilde{w}}e_{ij}}{N_{k}}$		(46)

Then the between-class scatter matrix $S_{B}$, the within class scatter matrix $S_{W}$ and regularized scatter matrix are calculated as below:

	$\displaystyle S_{B}$	$\displaystyle=\sum^{K}_{k=1}N_{k}(\mu_{k}-\mu)(\mu_{k}-\mu)^{T}$		(47)
	$\displaystyle S_{W}$	$\displaystyle=\sum^{K}_{k=1}\sum_{i\in C_{k}}(E_{i}-\mu_{k})(E_{i}-\mu_{k})^{T}$		(48)
	$\displaystyle\bar{S}^{\prime}$	$\displaystyle=S_{B}^{\prime}+S_{W}^{\prime}=S_{B}+\rho^{\prime}\mathbb{I}+S_{W}+\rho\mathbb{I}$		(49)

Once getting $S_{W}$ and $\bar{S}^{\prime}$, DCA is performed over the patches and compute a set of discriminant components as the orthonormal filters, where:

$$(S_{W}^{\prime})^{-1}\bar{S}^{\prime}=U\Lambda U^{T}$$

(50)

where $U$ holds the associated eigenvectors. The leading eigenvectors capture the main discriminant power of the mean-removed training patches. Then the first $L_{1}$ eigenvectors are taken as the orthonormal filters, where the $l$th filter is represented as $W^{l}_{1}\in{\mathbb{R}}^{k_{h}\times k_{w}}$, in the first convolution layer.

Similar to CNN, multiple convolution layers could be stacked following the first layer, as Fig. 2 shows. Given a second convolution layer as example, it repeats the similar procedure as in the first one. Given the $l_{1}$th filter in the first layer, for image $E_{i}$:

$$E_{i}^{l_{1}}=E_{i}*W^{l_{1}}_{1},i=1,2,\dots,N,l_{1}=1,2,\dots,L_{1}$$

(51)

where $*$ denotes the 2D convolution. It could use zero padding on $E_{i}^{l_{1}}$ to make it has the same size as $E_{i}$. After that, the patch mean of $E_{i}^{l_{1}}$ is removed, then it performs DCA over the concatenated patches and computes the filters for the second convolution layer. Once DCA is finished, the first $L_{2}$ eigenvectors are taken as the filters, the $l$th filter in the second layer is represented as $W^{l}_{2},W^{l}_{2}\in{\mathbb{R}}^{k_{h}\times k_{w}}$. For each $E_{i}^{l_{1}}$, there are $L_{2}$ filters to be convolved, as Fig. 2 shows.

After second convolution layer, there are $L_{1}\times L_{2}$ output in total, and they are converted to binary representation using the Heaviside step function $H(\cdot)$:

$$H(x)=\begin{cases}0,x\leq 0\\ 1,x>0\end{cases}$$

(52)

where $x=E_{i}^{l_{1}}*W^{l_{2}}_{2},l_{1}=1,2,\dots,L_{1},l_{2}=1,2,\dots,L_{2}$.

Once the output of the second convolution layer is converted to binary, for $E_{i}^{l_{1}}$, it obtains $\{H(E_{i}^{l_{1}}*W^{l_{2}}_{2})\}_{l_{2}=1}^{L_{2}}$, which is a vector of $L_{2}$ binary bits. Since $E_{i}^{l_{1}}$ has the same size as $E_{i}$ with zero padding, for each pixel, the vector of $L_{2}$ binary bits is viewed as a decimal number of $L_{2}$ digits. It “maps” the output back into a single integer:

$$T_{i}^{l_{1}}=\sum^{L_{2}}_{l_{2}=1}2^{l_{2}-1}H(E_{i}^{l_{1}}*W^{l_{2}}_{2})$$

(53)

The output of the binary quantization layer are $L_{1}$ “images” with each “pixel” of $L_{2}$ digits. To further reduce the size of the representation, for $T_{i}^{l_{1}}$, a max pooling layer is applied after the binary quantization layer.

The randomized response is applied to the output of the pooling layer, and the domain size $d$ is determined by $L_{2}$, where $d=2^{L_{2}}$. As we mentioned early, in DCA, the rank of the signal space is limited by the number of classes. More specially, $L_{r}\leq K$, where $L_{r}$ is the number of filters in $r$th convolution layer and $K$ is the number of classes. By employing DCA in the design, the domain of the final output is scalable, moreover, DCA also guarantees a high utility with a small number of components.

We first measure the classification accuracy with three image representations, the raw pixel, DCAConv and HOG, where a Bag of Visual Words (BOVW) model is associated with the HOG descriptor. More specifically, HOG descriptor provides a fixed length of the image representation, while each feature is contrast-normalized to improve the accuracy. Once the descriptor is generated, a K-Means clustering is performed over the whole descriptors and the center of each cluster is used as the visual dictionary’s vocabularies. Finally, the frequency histogram is made from the visual vocabularies and is served as BOVW. Unlike DCAConv, the domain size of the BOVW is fixed once the number of clusters is determined and there is no significant difference observed after tuning the number of clusters. In the experiment, the domain size of the BOVW is determined by the maximum frequency observed among all features, e.g. MNIST has a domain size of 40, Fashion-MNIST has a size of 39 and YaleB has a size of 44, otherwise, the probability of answering honestly would be uneven among all features. For DCACov, there are two convolution layers and various number of $L_{2}$ filters is tested. To make a fair comparison, the raw pixel is downscaled to have the same size as the DCAConv output domain. For example, the raw pixel value is downscaled to [0,15] using a MinMaxScaler³³3http://scikit-learn.org/stable/modules/generated/
sklearn.preprocessing.MinMaxScaler.html to match the DCAConv with 4 $L_{2}$ filters. For the information loss caused by the downscaling, we don’t observe a significant degrading in terms of the classification accuracy. Fig. 4 displays the accuracy regarding Naive Bayes and KNN classifiers, the horizontal specifies the $\epsilon$ for each individual feature, and the vertical axis shows the classification accuracy.

From the figure, it could be seen that, both classifiers perform slightly better than random guessing when $\epsilon\leq 0.01$, and the accuracy increases as $\epsilon\geq 0.1$. When $\epsilon$ grows to $1.0$, for DCAConv and raw pixel, both classifiers provide reasonably good accuracy, however, the BOVW still suffers from a low accuracy as the domain size is much larger than the other two representations. Tab. 1 provides the KNN accuracy of DCAConv when $\epsilon\geq 0.1$, where the last column gives the ground truth as no randomized response applied. As analyzed in Section III, the probability of being the true $\ell_{2}$ distance is bigger than $\frac{1}{2}$ as $\epsilon\geq ln(d+1)$, and it confirms that the accuracy approximates to the ground truth given that $\epsilon$, e.g. for all 3 datasets, the accuracy is within $5\%$ of the ground truth as $\epsilon\geq 2.83$. The comparison between Naive Bayes and KNN classifiers shows that Naive Bayes achieves higher accuracy when $\epsilon\leq 1.0$, where it may due to that the noise is eliminated by the frequency estimator, but the KNN still suffers to a low probability to preserve the true proximity of the data points given the same $\epsilon$. However, as $\epsilon$ increases, the perturbation becomes less, and the KNN starts to dominate classification accuracy.

Finally, for the texture dataset, the downscaled pixel feature provides a compatible accuracy with DCAConv. However, for the more complicated data, like facial data, the pixel fails to provide a good discriminant capacity in the KNN algorithm; under the same $\epsilon$, BOVW performs worse than the other two representations due to the large domain size.

We evaluate DCAConv under an extreme case, where the output is set to binary, and compare the utility of the representation to a variant of CNN. As we mention early, the reason that it is hard to apply randomized response to CNN is that the data flow is continuous. However, there are studies to replace the weights and activation with discrete values for the purpose of improving the power-efficiency. Binarized Neural Network (BNN)(?) is one of such research work, which modifies the convolution layer and activation function, to transform the data flow from float number to $\{+1,-1\}$. For the implementation of BNN, we take the suggested values for parameters like the number of hidden units in the fully connected layer, but with the same convolution layer setting as DCAConv, like the same number of filters. Once the training of BNN is finished, we take the activated binarized output before the fully connected layer and perturb it using randomized response. The classification result is shown in Fig 6, where the vertical axis specifies the classification accuracy. With the binary representation, the probability of preserving the true proximity quickly dominates as $\epsilon\geq 1.1$, and the performance of the perturbed data almost reaches the ground truth. Similarly, Tab. 2 provides the Naive Bayes and KNN accuracy of DCAConv when $\epsilon\geq 0.1$, where the domain size $d=2$, it can be seen that the classification accuracy of KNN almost matches the ground truth regarding all 3 datasets when $\epsilon\geq 1.5$. However, unlike KNN, there is not a clear threshold of $\epsilon$ for Naive Bayes classifier to provide a utility guarantee.