# Differentially Private Projected Histograms of Multi-Attribute Data for
Classification

Dong Su${}^{~{}\\#}$, Jianneng Cao${}^{~{}\star}$, Ninghui Li${}^{~{}\\#}$
# Purdue University ⋆ Institute for Infocomm Research
{su17<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we tackle the problem of constructing a differentially private
synopsis for the classification analyses. Several the state-of-the-art methods
follow the structure of existing classification algorithms and are all
iterative, which is suboptimal due to the locally optimal choices and the
over-divided privacy budget among many sequentially composed steps. Instead,
we propose a new approach, PrivPfC, a new differentially private method for
releasing data for classification. The key idea is to privately select an
optimal partition of the underlying dataset using the given privacy budget in
one step. Given one dataset and the privacy budget, PrivPfC constructs a pool
of candidate grids where the number of cells of each grid is under a data-
aware and privacy-budget-aware threshold. After that, PrivPfC selects an
optimal grid via the exponential mechanism by using a novel quality function
which minimizes the expected number of misclassified records on which a
histogram classifier is constructed using the published grid. Finally, PrivPfC
injects noise into each cell of the selected grid and releases the noisy grid
as the private synopsis of the data. If the size of the candidate grid pool is
larger than the processing capability threshold set by the data curator, we
add a step in the beginning of PrivPfC to prune the set of attributes
privately. We introduce a modified $\chi^{2}$ quality function with low
sensitivity and use it to evaluate an attribute’s relevance to the
classification label variable. Through extensive experiments on real datasets,
we demonstrate PrivPfC’s superiority over the state-of-the-art methods.

##  1 Introduction

We study the problem of publishing histograms of datasets while satisfying
differential privacy. A histogram is an important tool for summarizing data,
and can serve as the basis for many data analysis tasks. Publishing noisy
histograms for one-dimensional or two-dimensional datasets have been studied
extensively in recent years [21, 41, 8, 26, 4, 40, 39, 9, 33, 32]. However, as
noticed in [39, 33], these approaches do not work well when the number of
attributes/dimensions goes above a few. Many datasets that are of interest
have multiple attributes. In this paper, we focus on multi-attribute datasets
that have dozens of attributes, some of categorical and some are numerical.

For such a multi-attribute dataset, it is infeasible to publish a histogram
with all the attributes, therefore it is necessary to select a subset of the
attributes that are “interesting” for some intended data analysis tasks, and
to determine how to discretize the attributes. These selections partition the
domain into a number of cells. We call the result a “grid”. We consider a
common optimization objective, where the dataset includes a label attribute
and our goal is to ensure that classifiers that are accurate for the original
dataset can be learnt from the published noisy histograms. Classification is
an important tool for data analysis, and differentially private algorithms for
learning classifiers have been considered an important problem, with many
recent attempts [3, 6, 17, 30, 7, 24, 23, 39, 46, 45].

In this paper we propose the PrivPfC (Private Publication for Classification)
approach for publishing projected histograms. The key novelty is to privately
select a high-quality grid in a single step, while adapting to the privacy
budget $\epsilon$. We construct a set of candidate grids where the number of
cells is under a certain threshold (determined by the dataset size and the
privacy budget), and then use the exponential mechanism to select one grid
using a novel quality function that minimizes expected number of misclassified
records when a histogram classifier is constructed using the published
histogram. By construction, our quality function considers the impact of
injected Laplace noise to the histogram on the classification accuracy.

For high dimensional datasets, the size of the set of candidate grids might be
larger than the processing capacity of the data curator. We add a feature
selection step in the beginning to prune the set of attributes. This step
first privately selects a small number of attributes which are most relevant
to the class attribute by employing the exponential mechanism. We introduce a
modified $\chi^{2}$ correlation function that has low sensitivity while
evaluating an attribute’s relevance to the classification label variable. This
feature selection step enables our PrivPfC framework to scale to higher
dimensional datasets.

Our proposed PrivPfC outputs a histogram that can be used to generate
synthetic data for multiple data analysis tasks, while being optimized for
data classification. We show the effectiveness of PrivPfC by comparing it with
several other approaches that output a classifier in a differentially private
fashion.

For evaluation, we use two common classification algorithms, the decision tree
and the SVM, because these have been used in the literature on learning
classifiers while satisfying the differential privacy. Extensive experiments
on real datasets show that PrivPfC consistently and significantly outperforms
other state-of-the-art methods.

The contributions of this paper are summarized as follows:

  1. 1.

We propose PrivPfC, a novel framework for publishing data for classification
under differential privacy. As part of PrivPfC, we introduce a new quality
function that enables the selection of a good “grid” for publishing noisy
histograms. We also introduce a way to enable private selection of most
relevant features for classification, and to enable PrivPfC to scale to
higher-dimension datasets.

  2. 2.

Through extensive experiments on real datasets, we have compared PrivPfC
against several other state-of-the-art methods for data publishing as well as
private classification, demonstrating that PrivPfC improves the state-of-the-
art.

The rest of the paper is organized as follows. In Section 2, we review the
related work. Our PrivPfC approach is presented in Section 3. We report
experimental results in Section 4. Section 5 concludes our work.

##  2 Related Work

The notion of differential privacy was developed in a series of papers [11,
14, 3, 13, 12]. There are several primitives for satisfying
$\epsilon$-differential privacy. In this paper we use two of them. The first
primitive is the _Laplacian mechanism_ [13]. It adds noise sampled from a
Laplace distribution to a statistic $f$ to be released. The scale of the
Laplace distribution is proportional to $\mathsf{GS}_{f}$, the _global
sensitivity_ or the $L_{1}$ sensitivity of $f$. Another primitive is to sample
the output of the data analysis mechanism according to an exponential
distribution; this is generally referred to as the _exponential mechanism_
[28]. The mechanism relies on a _quality_ function
$q:\mathcal{D}\times\mathcal{R}\rightarrow\mathbb{R}$ that assigns a real
valued score to one output $r\in\mathcal{R}$ when the input dataset is $D$,
where higher scores indicate more desirable outputs. Given the quality
function $q$, its global sensitivity $\mathsf{GS}_{q}$ is defined as:

$\mathsf{GS}_{q}=\max_{r}\max_{D\simeq D^{\prime}}|q(D,r)-q(D^{\prime},r)|.$

The following method satisfies $\epsilon$-differential privacy:

$\mathsf{Pr}\left[r\mbox{ is selected}\right]\propto
e^{\left(\frac{\epsilon}{2\,\mathsf{GS}_{q}}q(D,r)\right)}.$

There has been a large body of works on differentially private histogram
construction for answering range queries or marginal queries [13, 40, 21, 9,
42, 33, 27, 34, 45].

Differentially Private Classification. Differentially private classification
has received growing attention in the research community [3, 6, 17, 30, 7, 24,
23, 39, 46, 45]. Blum et al. [3] suggested a solution for constructing the
private version of the ID3 [35] decision tree classifier. When the ID3
algorithm needs to get the number of tuples with a specific feature value, it
queries the SuLQ interface to get the corresponding noise count. Friedman and
Schuster [17] improved this approach by redesigning the classic ID3 classifier
construction algorithm to consider the feature quality function with low
sensitivity and using exponential mechanism to evaluate all the attributes
simultaneously. Chaudhuri et al. [6, 7] proposed a differentially private
logistic regression algorithm and later generalized this idea to address the
private empirical risk minimization which can be applied to a wider range of
classification problems, such as SVM classification. Zhang et al. [46]
proposed PrivGene, a general private model fitting framework based on genetic
algorithms, that can be applied to the SVM classification and the logistic
regression.

Besides the above interactive methods for constructing differentially private
classifiers, several works proposed solutions to publish data for
classification analysis tasks. Mohammed et al. [30] proposed the DiffGen
algorithm which first partitions the data domain by iteratively selecting
attributes and ways to discretize the attributes, and then injects Laplace
noise into each cell of all the leaf partitions. Vinterbo [39] proposed
another data publishing algorithm, called Private Projected Histogram (PPH).
PPH first decides how many attributes are to be selected, then incrementally
selects attributes via the exponential mechanism to maximize the
discernibility of the selected attributes. For each categorical attribute, the
full domain is used. For numerical attribute, it uses the formula proposed in
Lei [26] to decide how many bins to discretize them. In this method, the
number of attributes and how attributes are partitioned are independent of the
privacy budget. Furthermore, all selected attributes are treated equally.
Zhang et al. [45] presented PrivBayes which constructs a private a Bayesian
network through iteratively selecting sets of attributes that have maximum
mutual information via the exponential mechanism. It then injects Laplace
noise to perturb each conditional distribution of the network. We will further
analyze the above approaches and compare our proposed method with them in the
later sections.

##  3 PrivPfC Framework

In this section we present the PrivPfC framework of privately publishing data
for classification analysis.

###  3.1 Preliminaries

Figure 1: Taxonomy hierarchies of Relationship attribute and Education-num
attribute

We consider a dataset with a set of predictor variables and one binary
response variable. The predictor variables can be numerical or categorical.
Following [2, 22, 18, 30], for each predictor variable $A_{i}$, we assume the
existence of a _taxonomy hierarchy_ (also called a _generalization hierarchy_
in the literature) $T_{i}$. Figure 1 shows the taxonomy hierarchies of
_Relationship_ , a categorical variable, and _Education-num_ , a numerical
variable. In the hierarchy, the root node represents the whole domain of the
variable, and a parent node is a generalization (or a cover) of its children.
Child nodes under the same parent node are semantically related; they are
closer to each other than to nodes under a different parent node.

Each _level_ of a predictor variable’s taxonomy hierarchy forms a partition of
its domain. On the basis of the taxonomy hierarchy and its levels, we
introduce the notion of a grid.

######  Definition 1 (Grid)

Let $\mathsf{A}=\\{A_{1},\ldots,A_{d}\\}$ be the set of predictor variables in
a dataset and $\\{T_{1},\ldots,T_{d}\\}$ be their taxonomy hierarchies
respectively. Let $h_{i}$ be the height of $T_{i}$, $1\leq i\leq d$. Then, a
_grid_ $g$ is given by $\langle\ell_{1},\ldots,\ell_{d}\rangle$, where
$1\leq\ell_{i}\leq h_{i}$ and $1\leq i\leq d$. A grid defines a partition of
the data domain into _cells_ where each attribute $A_{i}$ is partitioned into
the values at level $\ell_{i}$. The number of cells of a grid is
$\Pi_{i=1}^{d}|T_{i}[l_{i}]|$, where $|T_{i}[l_{i}]|$ is the number of nodes
in the level $l_{i}$ of the hierarchy $T_{i}$. And the number of all possible
grids is $\Pi_{i=1}^{d}h_{i}$.

######  Definition 2 (Histogram)

Given a dataset $D$ and a grid $g$, a histogram $\mathsf{H}(D,g)$ partitions
$D$ into cells according to $g$, and outputs the numbers of positive instances
and negative instances in each cell.

By injecting Laplace noise into the positive counts and negative counts of
each cell in the histogram $\mathsf{H}(D,g)$, we get the noisy version of it,
$\tilde{\mathsf{H}}(D,g)$.

###  3.2 Histogram Publishing for Classification

Given a dataset $D$, the taxonomy hierarchies of its predictor variables, a
total privacy budget $\epsilon$, and the number of tuples in the dataset $N$
(a rough estimate suffices), we generate a candidate pool of all grids whose
number of cells are below a threshold, which is determined by $\epsilon$ and
$N$. We compute the quality score for each grid, which measures the usefulness
for classification of each grid in the pool. We then apply the exponential
mechanism [28] to privately select a grid, and finally publish a noisy
histogram using $g$.

A key technical challenge is to come up with a low-sensitivity quality
function that can measure the desirability of choosing a particular grid $g$.
We publish $\tilde{\mathsf{H}}(D,g)$, a noisy histogram of $D$ using $g$ to
partition the data domain, and desire that classifiers learned from
$\tilde{\mathsf{H}}(D,g)$ are close to classifiers learned from $D$.
Furthermore, we desire this to hold regardless of which particular
classification algorithm is used. We propose to define the quality function to
minimize the misclassification error (when measured using the dataset $D$) for
the classifier defined by the histogram $\tilde{\mathsf{H}}(D,g)$, i.e., for
each cell in the grid defined by $g$, it predicts the majority class according
to $\tilde{\mathsf{H}}(D,g)$. This classifier is in the same spirit as
histogram classifiers [10, 31], and we use
$\mathit{HC}^{\tilde{\mathsf{H}}(D,g)}$ to denote it.

Suppose that a grid is able to separate positive and negative data points very
well, then, even after adding the noises, this separation feature is still
preserved and can be used to learn classifiers. When no noise is added, the
finest partition is desired. However, with noise, we want to ensure that the
noises do not overwhelm the true counts. Since when a grid $g$ is fixed, the
noisy histogram includes random noises, the misclassification error is a
random variable, and we use the expected value of this error as the quality
function.

######  Definition 3 (Quality of grid)

Given a dataset $D$ and a grid $g$, the grid quality is measured by the
expected misclassification error of the histogram classifier
$\mathit{HC}^{\tilde{\mathsf{H}}(D,g)}$:

$\mathrm{qual}_{D}(g)=\mathbb{E}[err(\mathit{HC}^{\tilde{\mathsf{H}}(D,g)},D)].$

The following Lemma shows how to compute $\mathrm{qual}_{D}(g)$.

######  Lemma 1 (Quality of grid)

Given a dataset $D$ and a grid $g$, $\epsilon$ for the parameter of adding
Laplacian noise to the counts, we have

$\displaystyle\mathrm{qual}_{D}(g)$ $\displaystyle=\sum_{c\in
g}\left[\min(n_{c}^{+},n_{c}^{-})\left(1-\frac{e^{-\epsilon
x_{c}}}{2}\left(1+\frac{\epsilon x_{c}}{2}\right)\right)\right.$
$\displaystyle+\left.\max(n_{c}^{+},n_{c}^{-})\left(\frac{e^{-\epsilon
x_{c}}}{2}\left(1+\frac{\epsilon x_{c}}{2}\right)\right)\right],$ (1)

where $c$ ranges over all cells in the grid, $n_{c}^{+}$ is the number of
positive data points in $c$, $n_{c}^{-}$ is the number of negative data points
in $c$, and $x_{c}=|n_{c}^{+}-n_{c}^{-}|$.

To prove Lemma 1, we note that $\mathrm{qual}_{D}(g)$ can be further
decomposed into the sum of expected misclassification error at each perturbed
cell of the histogram after majority voting, and thus

$\displaystyle\mathrm{qual}_{D}(g)$ $\displaystyle=\sum_{c\in
g}\mathbb{E}[err(\tilde{c},D)]$

Where $\tilde{c}$ denotes the application of the histogram classifier
$\mathit{HC}^{\tilde{\mathsf{H}}(D,g)}$ to the cell $c$.

For cell $c$, if the added Laplace noises do not change the majority class
label, then the number of misclassified input tuples is
$\min(n_{c}^{+},n_{c}^{-})$; otherwise, it is $\max(n_{c}^{+},n_{c}^{-})$.
Thus,

$\displaystyle\mathbb{E}[err(\tilde{c},D)]=\min(n_{c}^{+},n_{c}^{-})\cdot
p_{c}+\max(n_{c}^{+},n_{c}^{-})\cdot(1-p_{c}),$ (2)

where $p_{c}$ is the probability that the majority class label in $c$ does not
change after injecting Laplace noises.

Let $Z_{1}$ and $Z_{2}$ be the Laplace noises added to the majority class and
the minority class of cell $c$, respectively, then

$p_{c}=\mathsf{Pr}\left[Z_{2}-Z_{1}\leq|n_{c}^{+}-n_{c}^{-}|\right].$ (3)

######  Lemma 2 ([25])

Let $Z_{1}$ and $Z_{2}$ be two i.i.d. random variables that follow the Laplace
distribution with mean 0 and scale $\frac{1}{\epsilon}$. Then the density of
their difference $Y=Z_{1}-Z_{2}$ is

$\displaystyle
f_{Y}(y)=\frac{\epsilon}{4}e^{-\epsilon|y|}(1+\epsilon|y|)\quad\quad-\infty<y<\infty,$

and the corresponding cumulative distribution function is

$\displaystyle F_{Y}(y)=\begin{dcases}1-\frac{e^{-\epsilon
y}}{2}\left(1+\frac{\epsilon y}{2}\right),&\mathrm{if~{}}y\geq 0,\\\
\frac{e^{\epsilon y}}{2}\left(1-\frac{\epsilon
y}{2}\right),&\mathrm{otherwise}.\end{dcases}$ (4)

From Equations (3) and (4), we have

$p_{c}=1-\frac{e^{-\epsilon|n_{c}^{+}-n_{c}^{-}|}}{2}\left(1+\frac{\epsilon|n_{c}^{+}-n_{c}^{-}|}{2}\right).$
(5)

Plugging Equation (5) into Equation (2) provides Lemma 1.

The lemma below bounds the sensitivity of our quality function.

###### Lemma 3

For any $\epsilon>0$, the global sensitivity of the quality function 1 is
$B(\epsilon)$, where

$\displaystyle B(\epsilon)$
$\displaystyle=x\cdot\left(\frac{e^{-\epsilon(x-1)}}{2}\left(1+\frac{\epsilon(x-1)}{2}\right)-\frac{e^{-\epsilon
x}}{2}\left(1+\frac{\epsilon x}{2}\right)\right)$
$\displaystyle+\left(1-\frac{e^{-\epsilon(x-1)}}{2}\left(1+\frac{\epsilon(x-1)}{2}\right)\right),$

and

$\displaystyle x=\frac{\epsilon
e^{\epsilon}+\sqrt{2-\left(4-\epsilon^{2}\right)e^{\epsilon}+2e^{2\epsilon}}}{-\epsilon+\epsilon
e^{\epsilon}}.$

Algorithm 1 PrivPfC: Privately Publishing Data for Classification

Input:  dataset $D$, the set of predictor variables $\mathcal{F}$ and their
taxonomy hierarchies, total privacy budget $\epsilon$, maximum grid pool size
$B$, median of the first branching factors of hierarchies $b$.

1:function $\mathsf{main}$($D,\mathcal{F},N,\epsilon$, $B$, $b$)

2: $T\leftarrow\delta\cdot N\cdot\epsilon/2$

3: $\mathsf{H}\leftarrow\mbox{Enumerate}(\mathcal{F},T)$

4: if $|\mathsf{H}|\geq B$ then

5: $k\leftarrow\left\lceil\frac{2\log{T}}{\log{b}}\right\rceil$

6: $\epsilon_{fs}\leftarrow 0.3\epsilon$, $\epsilon_{sh}\leftarrow
0.3\epsilon$, $\epsilon_{ph}\leftarrow 0.4\epsilon$

7: $X\leftarrow\mathsf{selectFeature}(D,\mathcal{F},k,\epsilon_{fs})$

8: $\mathsf{H}_{X}\leftarrow\mbox{Enumerate}(X,T)$

9:
$\hat{I}\leftarrow\mbox{PrivateHistogramPublishing}(D,\mathsf{H}_{X},\epsilon_{sh},\epsilon_{ph})$

10: else

11: $\epsilon_{sh}\leftarrow\frac{3}{7}\epsilon$,
$\epsilon_{ph}\leftarrow\frac{4}{7}\epsilon$

12:
$\hat{I}\leftarrow\mbox{PrivateHistogramPublishing}(D,\mathsf{H},\epsilon_{sh},\epsilon_{ph})$

13: end if

14: return $\hat{I}$

15:end function

16:

17:function
$\mathsf{PrivateHistogramPublishing}$($D,\mathsf{H},\epsilon_{sh},\epsilon_{ph}$)

18: $h\leftarrow\mathsf{selectHist}(D,\mathsf{H},\epsilon_{sh})$

19: $\hat{I}\leftarrow\mathsf{perturbHist}(D,h,\epsilon_{ph})$

20: return $\hat{I}$

21:end function

22:

23:function $\mathsf{selectHist}$($D,\mathsf{H},\epsilon_{sh}$)

24: for $i=1\to|\mathsf{H}|$ do

25: $q_{i}\leftarrow\mathrm{qual}(\mathsf{H}_{i})$

26: $p_{i}\leftarrow e^{-(q_{i}\epsilon_{sh})/2}$

27: end for

28: $h\leftarrow$ sample $i\in[1..|\mathsf{H}|]$ according to $p_{i}$

29: return $h$

30:end function

31:

32:function $\mathsf{perturbHist}$($D,h,\epsilon_{ph}$)

33: Initialize $I$ to empty

34: for each cell $c\in h$ do

35: $\hat{n}_{c}^{+}\leftarrow n_{c}^{+}+\mathrm{Lap}(1/\epsilon_{ph})$

36: $\hat{n}_{c}^{-}\leftarrow n_{c}^{-}+\mathrm{Lap}(1/\epsilon_{ph})$

37: Add $(\hat{n}_{c}^{+},\hat{n}_{c}^{-})$ to $I$

38: end for

39: Round all counts of $I$ to their nearest non-negative integers.

40: return $I$

41:end function

42:

43:

44:function $\mathsf{selectFeature}$($D,\mathcal{F},k,\epsilon_{fs}$)

45: Initialize $X$ to empty

46: Let $R$ be the response variable in $D$

47: for each $A_{i}\in\mathcal{F}$ do

48: $cor_{i}\leftarrow\mathsf{Cor}\left(A_{i},R,D\right)$

49: $p_{i}\leftarrow e^{\frac{\epsilon_{fs}\cdot cor_{i}}{4k}}$

50: end for

51: for $i=1\to k$ do

52: $f\leftarrow$sample $A_{i}\in\mathcal{F}$ according to $p_{i}$

53: Add $f$ to $X$

54: Remove $f$ from $\mathcal{F}$

55: end for

56: return $X$

57:end function

###  3.3 Correlation-based Feature Selection

Our basic solution privately selects a grid from the candidate pool to release
synthetic data. As the number of predictor variables increases, the candidate
pool size grows exponentially, giving arise to a scalability issue.
Fortunately, usually in a real dataset some predictor variables are not useful
for predicting the class labels. Such irrelevant variables can thus be
excluded from the classification to improve the scalability of our solution.

Feature selection [19] is the process of selecting a subset of important
features (predictor variables) to build a classification model. Various
feature selection methods have been proposed including wrapper method,
embedded methods, stepwise regression [15]. However, they require building a
large number of classification models, one for a subset of features one wants
to evaluate. It is unclear how to adapt these methods to satisfy differential
privacy. We propose a simple but effective approach, which selects predictor
variables based on a correlation analysis between predictor variables and the
class (i.e., target variable). We adapt the $\chi^{2}$ correlation test [20]
to have a low sensitivity.

Given a dataset $D$ with $N$ tuples, the $\chi^{2}$ correlation test [20]
evaluates whether categorical variables $A$ and $B$ are correlated. Suppose
that variable $A$ has $m$ distinct values, $a_{1},\ldots,a_{m}$, and $B$ has
$n$ distinct values, $b_{1},\ldots,b_{n}$. The $\chi^{2}$ correlation between
$A$ and $B$ (a.k.a Pearson $\chi^{2}$ statistic) is defined as

$\chi^{2}(A,B)=\sum_{i=1}^{m}\sum_{j=1}^{n}\frac{(o_{ij}-e_{ij})^{2}}{e_{ij}},$
(6)

where $o_{ij}$ is the observed number of tuples with $A=a_{i}$ and $B=b_{j}$
in dataset $D$, and the expected count $e_{ij}$ is computed by assuming $A$
and $B$ are independent

$e_{ij}=\frac{\mathrm{count}(A=a_{i})\times\mathrm{count}(B=b_{j})}{N},$ (7)

where $\mathrm{count}(A=a_{i})$ returns the number of tuples in dataset $D$
with $A=a_{i}$.

Clearly, if $A$ and $B$ are independent, then $\chi^{2}(A,B)=0$. The bigger
the $\chi^{2}$ value is, the stronger the correlation of variables $A$ and $B$
is. $\chi^{2}(A,B)$, however, has a large global sensitivity, because the
$e_{ij}$’s in Equation (6) can be very small. Our analysis (omitted for space
limitation) shows that it is at least $\frac{N^{2}+1}{2N}$.

We adapt $\chi^{2}$ correlation test to define the correlation
$\mathsf{Cor}(A,R)$ between a predictor variable $A$ with $m$ distinct values
and the binary response variable $R$ as:

$\mathsf{Cor}\left(A,R\right)=\sum_{i=1}^{m}\sum_{j=1}^{2}\left|o_{ij}-e_{ij}\right|,$
(8)

where $o_{ij}$ is the observed number of tuples with $A=a_{i}$ and $R=r_{j}$
in $D$, and the expected count $e_{ij}$ is computed by assuming $A$ and $R$
are independent as in Equation (7).

###### Lemma 4

Let $A$ and $R$ be a categorical variable and binary response variable in a
dataset $D$, respectively. Then, the global sensitivity of Function
$\mathsf{Cor}\left(A,R,D\right)$ is 2.

The proof is in the Appendix Section.

###  3.4 The Algorithm

We now present the full algorithm (Algorithm 1) for our framework of releasing
private data for classification tasks.

Line 2 sets the threshold of the maximum number of cells in a grid, to prevent
the average counts from being dominated by the injected noises. That is,

$E\left[\left|\mathsf{Lap}\left(\frac{1}{\epsilon}\right)\right|\right]\leq\frac{1}{5}\cdot\frac{N}{T},$
(9)

which means that the average noise magnitude is no more than the 20% of the
average cell count.

When feature selection is deemed necessary, we allocate 30% of the privacy
budget to privately select $k$ predictor variables that are strongly
correlated with the response variable. These selected variables are then used
to release private synthetic data.

The number of attributes to be selected, $k$, is based on $T$, the maximum
grid size. We want to have enough attributes so that relevant attributes are
included. At the same time, we do not want $k$ so large so that there are too
many candidate grids with size below $T$. Let $b$ be the median of the first
branching factors of hierarchies of all attributes. We set $k$ to be
$\frac{2\log(T)}{\log(b)}$.

###### Theorem 1

Algorithm 1 satisfies $\epsilon$-differential privacy.

Theorem 1 shows that Algorithm PrivPfC satisfies $\epsilon$-differential
privacy. The proof of Theorem 1 is thus straightforward by considering the
sequential composability of differential privacy as discussed in Section 2.

##  4 Experiment

Dataset | # Dim | # Numerical | # Categorical | # Records | Classification Task
---|---|---|---|---|---
Adult | 15 | 6 | 8 | 45,222 | Determine whether a person makes over 50K a year.
Bank | 21 | 10 | 10 | 41,188 | Determine whether the client subscribed a term deposit.
US | 47 | 15 | 31 | 39,186 | Determine whether a person makes over 50K a year.
BR | 43 | 14 | 28 | 57,333 | Determine whether a person makes over 300 per month.
Table 1: Dataset characteristics | Methods | Description
---|---|---
Non-Interactive | PrivPfC | Our proposed method.
PrivPfC-SelNF | Our proposed method with noise free feature selection and histogram selection.
PrivPfC-FSNF | Our proposed method with noise free feature selection.
DiffGen [30] | Private data release for classification via recursive partitioning.
DiffGen-NF | Noise free DiffGen.
PrivBayes [45] | Private Data Release via Bayes network.
PrivBayes-NF | Noise free PrivBayes.
PPH [39] | Private data release for classification by projection and perturbation.
Interactive | DiffPC-4.5 [17] | Privately construct C4.5 decision tree classifier.
PrivGene [46] | Private model fitting based on genetic algorithms.
PrivateERM [7] | Private classifier construction based on empirical risk minimization.
Table 2: Summary of differentially private classification methods
---
|
(a) Adult | (b) Bank
|
(c) US | (d) BR
Figure 2: Comparison of PrivPfC, DiffGen, PrivBayes, PPH and DiffPC-4.5 by
decision tree classification. x-axis: privacy budget $\epsilon$ in log-scale.
y-axis: misclassification rate in log-scale.
---
|
(a) Adult | (b) Bank
|
(c) US | (d) BR
Figure 3: Comparison of PrivPfC, DiffGen, PrivBayes, PPH, PrivGene and
PrivateERM by SVM classification. x-axis: privacy budget $\epsilon$ in log-
scale. y-axis: misclassification rate in log-scale.

###  4.1 Experimental Settings

Datasets. We use 4 real datasets for our experiments. The first one is the
Adult dataset from the UCI machine learning repository [1]. It contains 6
numerical attributes and 8 categorical attributes, and is widely used for
evaluating the performance of classification algorithms. After removing
missing values, the dataset contains 45,222 tuples. The second dataset is the
Bank marketing dataset from the same repository. It contains 10 numerical
attributes and 10 categorical attributes on 41,188 individuals. The third is
the US dataset from the _Integrated Public Use Microdata Series_ (IPUMS) [36].
It has 39,186 the United States census records in 2010, with 15 numerical
attributes and 31 categorical ones. The last is the BR dataset (also from
IMPUS), which contains 57,333 Brazil census records in 2010 and has 14
numerical attributes and 28 categorical ones. The classification tasks for the
Adult, US and BR datasets are to predict whether an individual has an income
above a certain threshold. The one for the Bank dataset is to predict whether
a client will subscribe a term deposit. Table 1 summarizes the characteristics
of the datasets.

Taxonomy Hierarchies. For the Adult dataset, we use the same taxonomy
hierarchies as DiffGen [30]. For the remaining 3 datasets, we do the
following. For numerical attributes, we partition each domain into equal size
bins and build hierarchies over them. For categorical attributes, we build
taxonomy hierarchies by considering the semantic meanings of the attribute
values.

Competing Methods. We compare PrivPfC with 6 state-of-the-art methods in terms
of misclassification rate. These include 3 non-interactive methods, DiffGen
[30], PrivBayes [45] and Private Projected Histogram (PPH) [39], which
privately release synthetic datasets for classification analyses, and 3
interactive methods, PrivGene [46], DiffPC-4.5 [17], and PrivateERM [7], which
includes one method for decision tree, and two methods for SVM.

_DiffGen._ [30] consists of two steps, partition and perturbation. The
partition step first generalizes all attribute’s values into the topmost nodes
in their taxonomy hierarchies and then iteratively selects one attribute at a
time for specialization, using the exponential mechanism. The quality of each
candidate specialization is based on the same heuristics as used by the
decision tree algorithms, such as information gain and majority class. As
suggested in [30], we use the majority class to measure the candidate quality,
and set the number of specialization steps to be 10 for the Adult dataset and
the bank dataset. For the US and BR datasets, we set the number to be 6 and 8
respectively, as beyond these numbers, the DiffGen implementation runs into
memory problems. The perturbation step injects Laplace noise into each cell of
the partition and outputs all the cells with their noisy counts as the noisy
synopsis of the data.

_PrivBayes._ [45] determines the structure of a Bayesian network by first
randomly select an attribute as the first node, and then iteratively select
one attribute and up to $k$ nodes as the attribute’s parent nodes, which have
the maximum mutual information. After the structure is determined, PrivBayes
perturbs the marginals needed for computing the conditional distributions. The
performance of the PrivBayes algorithm depends on $k$. We set $k=3$ for the
Adult dataset and the Bank dataset, which is the same as the one used in [45].
For the US and BR datasets, which were not used in [45], setting $k=3$ runs
out of memory in our experiments because of the larger dimensionality; we set
$k=2$ for them.

_PPH._ [39] starts with a feature selection procedure to select a set of $k$
features that have the maximal discernibility. Then, it uses the selected
features to build a histogram. For each categorical attribute, the full domain
is used. For numerical attribute, it uses the formula proposed in Lei [26] to
decide how many bins to discretize them.

_PrivGene_ [46] is a general-purpose private model fitting framework based on
genetic algorithms, which can be applied to SVM classification. _DiffPC-4.5_
[17] is an interactive private algorithm for building a C4.5 decision tree
classifier differential-privately. _PrivateERM_ [7] is an interactive private
algorithm for constructing SVM classifier by injecting noise into the risk
function first and then optimizing the perturbed risk function.

The source codes of the DiffGen, PrivBayes, PPH, DiffPC-4.5, PrivGene were
downloaded from [29], [43], [38], [16] and [44], respectively. The source code
of PrivateERM was shared by the authors of PrivBayes [45].

Evaluation Methodology. We consider two baselines – _Majority_ and
_NoiseFree_. _Majority_ is the misclassification rate by majority voting on
the class attribute, which predicts each test case with the majority class
label in the train dataset. _NoiseFree_ is the misclassification rate of a
decision tree or SVM classifier built on the true data. We expect that a good
algorithm to perform better than _Majority_ , and gets close to _NoiseFree_ as
$\epsilon$ increases.

The evaluation is based on two classification models: the CART decision tree
classifier and the SVM classifier with radial basis kernel. Interactive
approaches DiffPC-4.5 and PrivateERM build private classifiers directly. And
we use parameters suggested by the corresponding papers. The non-interactive
approaches PrivPfC, PPH, DiffGen, and PrivBayes generate private synthetic
datasets. To evaluate their performance in terms of decision tree model, we
use the rpart [37] library to build decision trees on their generated
synthetic datasets. For the evaluation in terms of SVM model, we use the
LibSVM package [5] to build SVM classifiers on the synthetic datasets. We use
the same set of parameters of rpart and LibSVM respectively in evaluating the
above non-interactive approaches.

For all the experiments, we vary $\epsilon$ from 0.05 to 1.0. Similar to the
experiment settings of [17, 30, 39], under each privacy budget, we execute
10-fold stratified cross-validation to evaluate the misclassification rate of
the above methods. For each train-test pair, we run the target method 10
times. We report the average measurements over the 10 runs and the 10-fold
crossvalidations. We set the maximum grid pool size to be 200,000. The
implementation and experiments of PrivPfC were done in Python 2.7 and all
experiments were conducted on an Intel Core i7-3770 3.40GHz PC with 16GB
memory.

###  4.2 Comparison against Competitors

Comparison on Decision Tree. Five approaches are involved: PrivPfC, DiffGen,
PrivBayes, PPH and DiffPC-4.5. Figure 2 reports their average
misclassification rates and the corresponding standard deviations. Clearly,
PrivPfC has the best performance, followed by DiffGen, PPH, DiffPC-4.5.
PrivBayes is the poorest in most cases. The performance of PrivPfC is also the
most robust, as can be seen from the fact that the standard deviation of its
misclassification rates is the lowest.

Comparison on SVM. We compare 6 approaches: PrivPfC, DiffGen, PrivBayes, PPH,
PrivGene, and PrivateERM. Figure 3 reports the experimental results. Once
again, PrivPfC has the best performance, followed by DiffGen, PrivGene, PPH,
PrivateERM and PrivBayes.

Effectiveness of Private Feature Selection. In Figure 4, we evaluate our
private feature selection method on the US dataset under privacy budget 0.1.
We create a variant of PrivPfC, called PrivPfC-FSNF, in which the feature
selection step of PrivPfC is noise-free and all the privacy budget is used in
remaining steps. PPH is included in the comparison since it also has a private
feature selection step. We create variants for each of the rest competitors,
by adding our proposed feature selection method as preprocessing step which
uses 30% of the total privacy budget.

From Figure 4, we can see that our PrivPfC algorithm has close performance to
its counterpart (PrivPfC-FSNF). This justifies that fact that the set of
attributes PrivPfC selects for grid partition is almost as good as those
selected by PrivPfC-FSNF and the effectiveness of PrivPfC mainly comes from
the private histogram selection. We can also see that although PrivBayes,
DiffPC-4.5 and PrivateERM’s performances are improved significantly by doing
our private feature selection step, they are still outperformed by PrivPfC.

|
---|---
(a) Decision Tree | (b) SVM
Figure 4: Effectiveness of Private Feature Selection on US dataset with
$\epsilon=0.1$. y-axis: misclassification rate.

###  4.3 Analyses of Sources of Errors

---
|
(a) Adult | (b) Bank
|
(c) US | (d) BR
Figure 5: Analyses of PrivPfC, DiffGen and PrivBayes by decision tree
classification. x-axis: privacy budget $\epsilon$ in log-scale. y-axis:
misclassification rate in log-scale.
---
|
(a) Adult | (b) Bank
|
(c) US | (d) BR
Figure 6: Analyses of PrivPfC, DiffGen and PrivBayes by SVM classification.
x-axis: privacy budget $\epsilon$ in log-scale. y-axis: misclassification rate
in log-scale.

PrivPfC distributes the privacy budget among three steps, feature selection,
grid selection and perturbation, in a 30%-30%-40% way. When feature selection
is not needed, the privacy budget is divided between grid selection and
perturbation in a ratio of 3:4. While these ratios are somewhat arbitrary, we
have experimentally evaluated other ratios, allocating between 20% and 60% to
each step. We have found that the differences among different budget
allocations are minor, so long as the last step receives at least 30% of the
privacy budget. Even with the worst allocation, which gives 20% to the last
step, PrivPfC still clearly outperforms competing methods. We also consider a
variant of PrivPfC, called PrivPfC-SelNF, in which the feature selection step
and histogram selection step are noise free and all the privacy budget is used
in the histogram perturbation step. PrivPfC-SelNF is not private; it shows the
best one can hope to achieve by optimizing the division among steps.

We have seen that PrivPfC outperforms the other non-interactive methods such
as DiffGen and PrivBayes. The key difference in PrivPfC is that we choose the
grid $g$ holistically, instead of arriving at the final grid through a series
of decisions. For example, DiffGen iteratively chooses the attributes and ways
to partition them, and PrivBayes iteratively builds a Bayesian network. There
are two reasons why such an iterative approach does not perform well. The
first is that the decisions made in each iteration may be sub-optimal because
of the perturbation necessary for satisfying differential privacy. The second
is that even if the decision made in each iteration is locally optimal, the
combination of them is not globally optimal. To see to what extent the latter
factor affects accuracy, we consider noise free variants of them respectively,
DiffGen-NF and PrivBayes-NF. In these variants the decisions in each iteration
as well as the publishing of counts in the end are performed without any
perturbation. They represent DiffGen and PrivBayes when the privacy budget
$\epsilon$ goes to $\infty$.

Figure 5 and Figure 6 report the experimental results of comparing these
methods, using Decision Tree and SVM, respectively. We first observe that
while PrivPfC-SelNF indeed outperforms PrivPfC, the difference is very small,
especially for larger $\epsilon$ values in the range. In fact, on Adult, US,
and BR datasets, the difference is barely noticeable when $\epsilon\geq 0.1$.
This suggests that little improvement can be gained to further optimize the
division of privacy budget or dataset among determining grid $g$ and
publishing noisy histogram.

We also observe that the non-private noise-free version of PrivBayes still
performs poorly; in fact, it performs significantly worse than the private
PrivPfC. This suggests that the iterative Bayes network construction approach
is not suitable for the purpose of building accurate classifiers. This is
perhaps due in large part to the fact that it is not designed originally to
optimize for classification.

The non-private DiffGen-NF performs similarly to PrivPfC and PrivPfC-SelNF on
the Adult and US datasets. On the Bank dataset, it is outperformed by PrivPfC
and PrivPfC-SelNF when $\epsilon\geq 0.15$. On the BR dataset, DiffGen-NF
performs significantly worse than PrivPfC and PrivPfC-SelNF. This suggests
that the inherent iterative structure of DiffGen is suboptimal, even without
considering the effect of perturbation.

##  5 Conclusion

In this paper, we have introduced PrivPfC, a novel framework for publishing
data for classification under differential privacy. As a core part of PrivPfC,
we have introduced a novel quality function that enables the selection of a
good “grid” for publishing noisy histograms. We have also introduced a new
techinque for privately selecting of most relevant features for
classification, which enables PrivPfC to scale to higher-dimension datasets.
We have conducted extensive experiments on four real datasets, and the results
show that our approach greatly outperforms several other state-of-the-art
methods for private data publishing as well as private classification.

## References

  * [1] A. Asuncion and D. Newman.  UCI machine learning repository, 2010.
  * [2] R. J. Bayardo and R. Agrawal.  Data privacy through optimal $k$-anonymization.  In ICDE, pages 217–228, 2005.
  * [3] A. Blum, C. Dwork, F. McSherry, and K. Nissim.  Practical privacy: the sulq framework.  In PODS, pages 128–138, 2005.
  * [4] T.-H. H. Chan, E. Shi, and D. Song.  Private and continual release of statistics.  ACM Trans. Inf. Syst. Secur., 14(3):26:1–26:24, Nov. 2011.
  * [5] C.-C. Chang and C.-J. Lin.  LIBSVM: A library for support vector machines.  ACM Transactions on Intelligent Systems and Technology, 2:27:1–27:27, 2011.  Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
  * [6] K. Chaudhuri and C. Monteleoni.  Privacy-preserving logistic regression.  In NIPS, pages 289–296, 2008.
  * [7] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate.  Differentially private empirical risk minimization.  The Journal of Machine Learning Research, 12:1069–1109, 2011.
  * [8] G. Cormode, C. Procopiuc, D. Srivastava, and T. T. L. Tran.  Differentially private summaries for sparse data.  ICDT ’12, pages 299–311, 2012.
  * [9] G. Cormode, M. Procopiuc, E. Shen, D. Srivastava, and T. Yu.  Differentially private spatial decompositions.  In ICDE, pages 258–269, 2012.
  * [10] L. Devroye, L. Györfi, and G. Lugosi.  A probabilistic theory of pattern recognition.  Applications of mathematics. Springer, New York, Berlin, Heidelberg, 1996\.
  * [11] I. Dinur and K. Nissim.  Revealing information while preserving privacy.  In PODS, pages 202–210, 2003.
  * [12] C. Dwork.  Differential privacy.  In ICALP, pages 1–12, 2006.
  * [13] C. Dwork, F. McSherry, K. Nissim, and A. Smith.  Calibrating noise to sensitivity in private data analysis.  In TCC, pages 265–284, 2006.
  * [14] C. Dwork and K. Nissim.  Privacy-preserving datamining on vertically partitioned databases.  In CRYPTO, pages 528–544, 2004.
  * [15] M. A. Efroymson.  Multiple regression analysis.  Wiley, 1960.
  * [16] A. Friedman.  Data mining with differential privacy.  Available at http://www.cs.technion.ac.il/ arikf/publications/publications.html.
  * [17] A. Friedman and A. Schuster.  Data mining with differential privacy.  In KDD, pages 493–502, 2010.
  * [18] B. C. M. Fung, K. Wang, and P. S. Yu.  Top-down specialization for information and privacy preservation.  In ICDE, pages 205–216, 2005.
  * [19] I. Guyon and A. Elisseeff.  An introduction to variable and feature selection.  The Journal of Machine Learning Research, 3:1157–1182, 2003.
  * [20] J. Han, M. Kamber, and J. Pei.  Data Mining: Concepts and Techniques.  Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 3rd edition, 2011\.
  * [21] M. Hay, V. Rastogi, G. Miklau, and D. Suciu.  Boosting the accuracy of differentially private histograms through consistency.  PVLDB, 3(1):1021–1032, 2010.
  * [22] V. S. Iyengar.  Transforming data to satisfy privacy constraints.  In KDD, pages 279–288, 2002.
  * [23] G. Jagannathan, K. Pillaipakkamnatt, and R. N. Wright.  A practical differentially private random decision tree classifier.  Transactions on Data Privacy, 5:273–295, 2012.
  * [24] X. Jiang, Z. Ji, S. Wang, N. Mohammed, S. Cheng, and L. Ohno-Machado.  Differential-private data publishing through component analysis.  Transactions on data privacy, 6(1):19, 2013.
  * [25] S. Kotz, T. Kozubowski, and K. Podgorski.  The Laplace Distribution and Generalizations: A Revisit With Applications to Communications, Exonomics, Engineering, and Finance.  Number 183. Springer, 2001.
  * [26] J. Lei.  Differentially private m-estimators.  In NIPS, pages 361–369, 2011.
  * [27] C. Li, M. Hay, G. Miklau, and Y. Wang.  A data-and workload-aware algorithm for range queries under differential privacy.  PVLDB, 7(5), 2014.
  * [28] F. McSherry and K. Talwar.  Mechanism design via differential privacy.  In FOCS, pages 94–103, 2007.
  * [29] N. Mohammed.  Differentially private data release for data mining.  Available at http://dmas.lab.mcgill.ca/fung/pub/MCFY11kdd.htm.
  * [30] N. Mohammed, R. Chen, B. C. M. Fung, and P. S. Yu.  Differentially private data release for data mining.  In KDD, pages 493–501, 2011.
  * [31] R. Nowak.  Ece 901, lecture 5: Plug-in rules and the histogram classifier.  Available at http://nowak.ece.wisc.edu/SLT07/lecture5.pdf.
  * [32] W. Qardaji, W. Yang, and N. Li.  Differentially private grids for geospatial data.  ICDE ’13, pages 757–768, 2013.
  * [33] W. Qardaji, W. Yang, and N. Li.  Understanding hierarchical methods for differentially private histograms.  PVLDB, 6(14):1954–1965, 2013.
  * [34] W. Qardaji, W. Yang, and N. Li.  Priview: Practical differentially private release of marginal contingency tables.  SIGMOD ’14, pages 1435–1446, 2014.
  * [35] J. R. Quinlan.  Induction of decision trees.  Mach. Learn., 1(1):81–106, Mar. 1986.
  * [36] S. Ruggles, J. T. Alexander, K. Genadek, R. Goeken, M. B. Schroeder, and M. Sobek.  Integrated public use microdata series: Version 5.0 [machine-readable database], 2010.
  * [37] T. Therneau, B. Atkinson, and B. Ripley.  rpart: Recursive partitioning and regression trees, 2014.
  * [38] S. A. Vinterbo.  Differentially private projected histograms.  Available at http://ptg.ucsd.edu/~staal/R/pph.html.
  * [39] S. A. Vinterbo.  Differentially private projected histograms: Construction and use for prediction.  ECML PKDD’12, pages 19–34, 2012.
  * [40] X. Xiao, G. Wang, and J. Gehrke.  Differential privacy via wavelet transforms.  IEEE Trans. Knowl. Data Eng., 23(8):1200–1214, 2011.
  * [41] Y. Xiao, L. Xiong, and C. Yuan.  Differential private data release through multidimensional partitioning.  In VLDB SDM Workshop, 2010.
  * [42] J. Xu, Z. Zhang, X. Xiao, Y. Yang, and G. Yu.  Differentially private histogram publication.  In ICDE, pages 32–43, 2012.
  * [43] J. Zhang.  Privbayes: Private data release via bayesian networks.  Available at http://sourceforge.net/projects/privbayes/.
  * [44] J. Zhang.  Privgene: Differentially private model fitting using genetic algorithms.  Available at http://sourceforge.net/projects/privgene/.
  * [45] J. Zhang, G. Cormode, C. M. Procopiuc, D. Srivastava, and X. Xiao.  Privbayes: Private data release via bayesian networks.  In SIGMOD ’14, pages 1423–1434, 2014.
  * [46] J. Zhang, X. Xiao, Y. Yang, Z. Zhang, and M. Winslett.  Privgene: Differentially private model fitting using genetic algorithms.  In SIGMOD ’13, pages 665–676, 2013.

##  6 Appendix

Proof of Lemma 4. Without loss of generality, we assume the cell $o_{11}$ is
changed by 1. We use $\mathbf{c}_{i}$ to denote the number of tuples with
$R=r_{i}$, $i=1,2$.

$\displaystyle\Delta=|\mathrm{corr}(f,D^{\prime})-\mathrm{corr}(f,D)|$
$\displaystyle=\Bigg{|}\left(o_{11}+1-\frac{(o_{11}+o_{12}+1)(\mathbf{c}_{1}+1)}{\mathbf{c}_{1}+\mathbf{c}_{2}+1}\right)-\left(o_{11}-\frac{(o_{11}+o_{12})\mathbf{c}_{1}}{\mathbf{c}_{1}+\mathbf{c}_{2}}\right)$
$\displaystyle+\sum_{i=2}^{m}\left(o_{i1}-\frac{(o_{i1}+o_{i2})(\mathbf{c}_{1}+1)}{\mathbf{c}_{1}+\mathbf{c}_{2}+1}\right)-\left(o_{i1}-\frac{(o_{i1}+o_{i2})\mathbf{c}_{1}}{\mathbf{c}_{1}+\mathbf{c}_{2}}\right)\Bigg{|}$
$\displaystyle\leq\left|1-\frac{(o_{11}+o_{12}+1)(\mathbf{c}_{1}+1)}{\mathbf{c}_{1}+\mathbf{c}_{2}+1}+\frac{(o_{11}+o_{12})\mathbf{c}_{1}}{\mathbf{c}_{1}+\mathbf{c}_{2}}\right|$
$\displaystyle+\sum_{i=2}^{m}\left|-\frac{(o_{i1}+o_{i2})(\mathbf{c}_{1}+1)}{\mathbf{c}_{1}+\mathbf{c}_{2}+1}+\frac{(o_{i1}+o_{i2})\mathbf{c}_{1}}{\mathbf{c}_{1}+\mathbf{c}_{2}}\right|$
$\displaystyle=\frac{(\mathbf{c}_{1}+\mathbf{c}_{2})(\mathbf{c}_{1}+\mathbf{c}_{2}+1)-(o_{11}+o_{12})\mathbf{c}_{2}-(\mathbf{c}_{1}+1)(\mathbf{c}_{1}+\mathbf{c}_{2})}{(\mathbf{c}_{1}+\mathbf{c}_{2})(\mathbf{c}_{1}+\mathbf{c}_{2}+1)}$
$\displaystyle+\frac{\mathbf{c}_{2}((\mathbf{c}_{1}-o_{11})+(\mathbf{c}_{2}-o_{12}))}{(\mathbf{c}_{1}+\mathbf{c}_{2})(\mathbf{c}_{1}+\mathbf{c}_{2}+1)}$
$\displaystyle=\frac{2\mathbf{c}_{2}((\mathbf{c}_{1}-o_{11})+(\mathbf{c}_{2}-o_{12}))}{(\mathbf{c}_{1}+\mathbf{c}_{2})(\mathbf{c}_{1}+\mathbf{c}_{2}+1)}$
$\displaystyle\leq 2.$

$\Box$


# Multilingual and Fully Non-Autoregressive ASR with Large Language Model
Fusion: A Comprehensive Study

###### Abstract

In the era of large models, the autoregressive nature of decoding often
results in latency serving as a significant bottleneck. We propose a non-
autoregressive LM-fused ASR system that effectively leverages the
parallelization capabilities of accelerator hardware. Our approach combines
the Universal Speech Model (USM) and the PaLM 2 language model in per-segment
scoring mode, achieving an average relative WER improvement across all
languages of 10.8% on FLEURS and 3.6% on YouTube captioning. Furthermore, our
comprehensive ablation study analyzes key parameters such as LLM size, context
length, vocabulary size, fusion methodology. For instance, we explore the
impact of LLM size ranging from 128M to 340B parameters on ASR performance.
This study provides valuable insights into the factors influencing the
effectiveness of practical large-scale LM-fused speech recognition systems.

Index Terms—  large language model, multilingual speech recognition

##  1 Introduction

Large-scale models have showcased impressive results across applications,
especially in multilingual speech models [1, 2, 3, 4, 5] and multilingual
large language models (LLMs) [6, 7, 8]. The next evolution is the fusion of
these large multilingual models to enhance accuracy. However, their size
brings latency issues, notably in autoregressive decoding, as seen with
shallow fusion [9].

Applications like voice assistants and live captioning face challenges from
these models’ latency. Recognizing this concern, our study presents a non-
autoregressive LM-fused ASR system. This approach streams utterances at
8-second intervals using the Universal Speech Model (USM) [10] and the PaLM 2
language model [11]. Both the USM and PaLM 2 process each 8-second chunk with
full audio context, leading to enhanced accuracy, and they are also able
process it quickly to by parallelizing across the sequence for smooth user
experience. In particular, hypotheses are generated non-autoregressively by
attaching a CTC decoder to the USM, and the hypotheses are scored non-
autoregressively by the LM by passing in the entire hypothesis sequence in
teacher forcing mode [12].

Our methodology yields an average double-digit gain of 10.8% on relative word
error rate (WER) on the public multilingual FLEURS testset. On a challenging
internal YouTube captioning testset, we observe an average gain of 3.6%,
across all available languages. Our study further delves into factors like LM
size (up to 340B), vocabulary, context length, segmentation, n-best list size,
and scoring method. For instance, we find that though LLMs display emergent
behaviors with increasing size [13], their impact on WER is more muted—but
larger models can reduce the sensitivity to fusion weight.

##  2 Related work

Leveraging large language models to enhance ASR systems has emerged as a
natural and promising direction, leading to significant advancements in recent
research. Several studies have focused on integrating LLMs with ASR models,
exploiting their vast linguistic knowledge and contextual understanding. [14]
combined T5 [15] and PaLM 1 [16] with a Conformer RNN-T model, enhancing ASR
performance for English and code-switched data. Our work builds on this by
using LLMs for large-scale ASR models with a non-autoregressive CTC head.

[9] improved recognition of rare words in short voice queries using shallow
fusion. In contrast, our focus lies in long-form tasks like YouTube
captioning, where LLMs’ contextual understanding is crucial. Given the
limitations of shallow fusion for long tasks and mismatched vocabularies, we
explore scoring as a more efficient fusion technique.

[17] integrated a Listen Attend Spell Once model [18] with BERT [19] using
n-best scoring. We expand upon this idea by deploying larger-scale,
multilingual models. Other research, such as [20], has explored various fusion
methods between LLMs and ASR systems. Their surprising finding was the
comparable performance of simple shallow fusion to deeper techniques.
Similarly, [21] used two fusion methods with LLaMa LLM and found minimal
difference in WER outcomes, supporting the conclusions of [20].

Building on these findings, our study emphasizes scoring as the fusion method,
aiming for a practical and scalable ASR+LLM solution suitable for real-world
applications.

##  3 Method

###  3.1 Speech Model

We employ the Universal Speech Model (USM) [10], a 2 billion parameter
Conformer [22], with 32 layers and a model dimension of 1536, for ASR
hypotheses. The vocabulary comprises 16384 wordpieces, and a CTC decoder
ensures non-autoregressive, parallel inference. For training the USM, a
multitask approach is used. It’s trained on over 12 million hours of unlabeled
audio and 28 billion sentences of text data, along with 110 thousand hours of
supervised and 100 thousand hours of semi-supervised audio. All datasets are
multilingual. The USM features chunk-wise bi-directional attention, enabling
accurate long-form audio modeling with 30 second segment during training.
Unlike traditional audio-based chunking, this approach maintains continuous
state throughout, allowing for streaming results every 8 seconds, enhancing
user experience.

###  3.2 Language Model

We utilize the PaLM 2 language model [11] to score the ASR hypotheses. Trained
on varied data sources like web documents and books, it uses a 256k wordpiece
vocabulary. PaLM 2 surpasses its predecessor, PaLM 1 [16], via enhanced
training, architecture improvements, and extended context length, showcasing
superior performance in natural language tasks. We assess its capability in
ASR scoring using the pre-trained variant and apply prefix LM scoring mode
[23], prompting the model with a fixed prefix (top hypotheses from previous
segments) and scoring several suffix hypotheses (different hypotheses for
current segment).

###  3.3 Long-form Inference

To process long-form audio without memory constraints, we employ a streaming
framework, processing the audio frame by frame. Using the USM’s chunk-wise
attention, we encode 8-second chunks as soon as the audio is available and
relay them to the CTC decoder. These CTC probabilities form a confusion
network lattice encoding possible wordpieces. Given the independence of each
encoded frame, the wordpiece distributions are also independent of one
another. Consequently, the lattice holds hypotheses that exponentially grow
with length, making it challenging to score all of them with an LLM.

Fig. 1: Results on all languages. Text indicates relative WER change. Top:
Youtube Captions testset. Bottom: FLEURS testset.

###  3.4 LM Scoring

To handle the exponential growth, we break the lattice into 8-second segments,
scoring only current segment hypotheses. To maintain context, we use the
concatenated top hypothesis from the previous two segments as the LM prefix.
This iterative process updates every 8 seconds, ensuring the prefix is always
the top hypotheses from the last two segments. To derive suffixes for the LM,
we pick the best N hypotheses from the lattice and batch them as suffix
sequences for scoring. The combined LM and ASR scores given the audio x and
the hypothesis y are then represented by

$\log p_{final}(\textbf{y}|\textbf{x})=\log
p_{asr}(\textbf{y}|\textbf{x})+\lambda\cdot\log p_{lm}(\textbf{y}),$ (1)

with the leading hypothesis chosen as the final transcript. Per-segment
scoring is parallelizable, non-autoregressive, and updates in streaming mode
every 8 seconds as one speaks.

##  4 Evaluation

Throughout our evaluations, we will use the following setup unless otherwise
mentioned.

  * •

US English locale

  * •

1 billion parameter variant of PaLM 2

  * •

LM scoring weight of 0.3 (optimized according to the settings list here)

  * •

Context length of 2 prior segments

  * •

N-best list size of 16

  * •

Youtube Captions testset, described in next section.

###  4.1 Testsets

YouTube videos span diverse categories, making them suitable for our LM
scoring study. We evaluate on the commonly used YouTube captioning testset,
YT_LONG, encompassing video-on-demand content in multiple languages [24, 25,
26, 27, 14]. For US English, it includes 77 videos totaling 22.2 hours, with a
median utterance length of 14.8 minutes. Other languages average 61 videos and
17 hours. We also analyze results on the FLEURS testset [28], containing
600-900 utterances per language, with US English having 647. The total
duration across languages is 283 hours.

###  4.2 Results on All Languages

Results for all languages are presented in Figure 1. We tested LM scoring
weight $\lambda$ at four values: {0.15, 0.30, 0.45, 0.60}. On Youtube (Figure
1 (top)), PaLM 2 integration reduces WER by 4.1% for en_us, averaging 3.6%
across 15 languages. The FLEURS testset (Figure 1 (bottom)) shows a more
pronounced improvement: 9.7% for en_us and 10.8% on average. No language
showed regression.

###  4.3 Dependence on LM Size

Large language models demonstrate emergent abilities with increased size,
data, and compute [13, 29]. This study examines ASR hypothesis scoring using
different PaLM 2 scale variants. Results in Table 1 indicate that while WER
improves with larger models (E2-E6), the gains might not offset the growing
inference costs. Additionally, optimal LM scoring weight increases with model
size, shifting from 0.25 for a 128M LM to 0.45 for a 340B LM (Figure 2).
Larger models show decreased WER sensitivity to LM weight changes. This
suggests that smaller models require cautious weighting, while larger models,
with their improved accuracy, can afford more weight without risking incorrect
hypothesis selection.

Table 1: Dependence on PaLM 2 model size. LM size | WER | relative
---|---|---
B1: No LM | 14.48 | -
E2: 128M | 13.98 | -3.4%
E3: 500M | 13.94 | -3.7%
E4: 1B | 13.88 | -4.1%
E5: 8B | 13.83 | -4.5%
E6: 340B | 13.76 | -5.0%

###  4.4 Dependence on Context Length

By adjusting the number of segments from previous history to utilize as a
prompt, we can coarsely control the LM’s context length. Figure 3 indicates
that concatenating 4 context segments, or 32 seconds of decoded text, is
optimal. Including more than 4 segments slightly reduces performance, possibly
due to the LM scoring weight being optimized at 2 segments. The results
suggest that using about 32 seconds or approximately 50 words of context
improves ASR. However, adding more context after this offers limited benefit,
differing from many NLP tasks where longer contexts are essential.

###  4.5 Dependence on Vocabulary Size

Fig. 2: Dependence of various PaLM 2 models on the LM scoring weight. Fig. 3:
Dependence on number of context segments.

PaLM 2 has a vocabulary of 256k tokens, optimized for natural language
generation. A benefit of per-segment scoring is that it allows handling of
mismatched vocabularies between ASR and LLM models through re-tokenization. In
the 1-billion-parameter PaLM 2, embedding and softmax layers take up about one
third of its parameters. We tested a reduced 32k token vocabulary for PaLM 2
to decrease computational cost. Results in Table 2 show minimal performance
degradation with the smaller vocabulary. Thus, using a smaller vocabulary can
save computation while retaining strong performance.

Table 2: Dependence on LM vocabulary size. LM vocabulary size | WER
---|---
B2: 256k | 13.88
E7: 32k | 13.89

###  4.6 Dependence on Segmentation

Segmentation determines the frequency of lattice scoring with the LLM,
influencing user experience and transcription quality [27, 30, 31]. We
evaluated fixed segmentation lengths and a voice activity detector (VAD)
segmenter [32]. While VAD avoids cutting words, it yields inconsistent segment
lengths potentially affecting user experience when used in a per-segment
streaming scenario. The median length of VAD segments is around 5 seconds.

Results in 3 show fixed-length (B3) surpasses VAD (E8), opposing findings in
[30]. This is due to differences in the model; [30] uses RNN-T which discards
most hypotheses upon segmentation, while our CTC model doesn’t retain decoder
states, making it more robust to premature segmentation. 4 shows WER stability
beyond 3 seconds. This is evidence that, in contrast to RNN-T, CTC remains
unaffected by word truncation, thanks to its non-dependent confusion network
structure.

Table 3: Dependence on segmenter. Segmentation | WER
---|---
B3: Fixed 8 sec | 13.88
E8: VAD | 13.98
Fig. 4: Dependence on the segment length.

###  4.7 Dependence on Number of Hypotheses

The number of paths in a lattice increases with segment length, but
computational bounds limit the number of hypotheses scored. Figure 5 presents
a study on the n-best list size, which denotes the scored hypotheses per
segment. Performance improves as the list expands, plateauing at about 1024.
This growth suggests the lattice’s high density, allowing the LLM to continue
improving the transcription quality up to computational constraints.

Fig. 5: Dependence on n-best list size.

###  4.8 Comparison to Shallow Fusion

Our exploration has mainly considered per-segment LM scoring. An alternative
is per-frame scoring or shallow fusion, which is computationally heavier due
to its autoregressive decoding and frequent LM invocation.

In per-frame scoring, the LM acts on each frame, usually pre-pruning,
amplifying computational load. When applied post-pruning, per-frame scoring
requires forward propagations of $N_{frames}\times N_{hyps}$, while per-
segment scoring demands $N_{tokens}\times N_{hyps}$ propagations. This makes
per-frame about $N_{frames}/N_{tokens}$ times costlier. On our YouTube
testset, this ratio is 4. We apply a blank pruning strategy where frames with
a blank probability above 0.9 are skipped. This largely diminishes the factor-
of-4 cost difference.

Performance comparisons in Table 4 show per-frame scoring (E9) at 13.70 (-5.4%
relative to no LM) outperforms per-segment scoring (B4) at 13.88 (-4.1%
relative). Shallow fusion shines in non-latency-critical scenarios with
matched vocabularies. For per-frame scoring, we retrained the ASR model with
PaLM 2’s vocabulary.

Table 4: Comparison between per-segment to per-frame scoring (i.e. shallow fusion). Vocabulary size | WER
---|---
B4: Per-segment scoring (scoring) | 13.88
E9: Per-frame scoring (shallow fusion) | 13.70

##  5 Conclusion

We developed a deployable ASR system using large-scale multilingual models,
emphasizing practicality. By adopting a non-autoregressive system with CTC and
per-segment LM scoring, we enhanced performance across languages for YouTube
captions and FLEURS. Our study also provided insights into system parameters’
effects on ASR efficacy.

## References

  * [1] V. Pratap _et al._ , “Massively multilingual asr: 50 languages, 1 model, 1 billion parameters,” _Proc. Interspeech 2020_ , pp. 4751–4755, 2020.
  * [2] B. Li _et al._ , “Scaling end-to-end models for large-scale multilingual asr,” in _Proc. ASRU_. IEEE, 2021, pp. 1011–1018.
  * [3] Y. Zhang _et al._ , “Bigssl: Exploring the frontier of large-scale semi-supervised learning for automatic speech recognition,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 16, no. 6, pp. 1519–1532, 2022.
  * [4] A. Radford _et al._ , “Robust speech recognition via large-scale weak supervision,” in _International Conference on Machine Learning_. PMLR, 2023, pp. 28 492–28 518.
  * [5] W. Chen _et al._ , “Improving massively multilingual asr with auxiliary ctc objectives,” in _Proc. ICASSP_. IEEE, 2023, pp. 1–5.
  * [6] M. Shoeybi _et al._ , “Megatron-lm: Training multi-billion parameter language models using model parallelism,” _arXiv preprint arXiv:1909.08053_ , 2019.
  * [7] T. Brown _et al._ , “Language models are few-shot learners,” _Advances in neural information processing systems_ , vol. 33, pp. 1877–1901, 2020.
  * [8] H. Touvron _et al._ , “Llama: Open and efficient foundation language models,” _arXiv preprint arXiv:2302.13971_ , 2023.
  * [9] K. Hu _et al._ , “Massively multilingual shallow fusion with large language models,” in _Proc. ICASSP_. IEEE, 2023, pp. 1–5.
  * [10] Y. Zhang _et al._ , “Google usm: Scaling automatic speech recognition beyond 100 languages,” _arXiv preprint arXiv:2303.01037_ , 2023.
  * [11] R. Anil _et al._ , “Palm 2 technical report,” _arXiv preprint arXiv:2305.10403_ , 2023.
  * [12] J. Salazar, D. Liang, T. Q. Nguyen, and K. Kirchhoff, “Masked language model scoring,” in _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , 2020, pp. 2699–2712.
  * [13] J. Wei _et al._ , “Emergent abilities of large language models,” _arXiv preprint arXiv:2206.07682_ , 2022.
  * [14] T. Chen _et al._ , “Large-scale language model rescoring on long-form data,” in _Proc. ICASSP_. IEEE, 2023, pp. 1–5.
  * [15] C. Raffel _et al._ , “Exploring the limits of transfer learning with a unified text-to-text transformer,” _J. Mach. Learn. Res._ , vol. 21, no. 1, jun 2020.
  * [16] A. Chowdhery _et al._ , “Palm: Scaling language modeling with pathways,” _arXiv preprint arXiv:2204.02311_ , 2022.
  * [17] F.-H. Yu, K.-Y. Chen, and K.-H. Lu, “Non-autoregressive asr modeling using pre-trained language models for chinese speech recognition,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 30, pp. 1474–1482, 2022.
  * [18] Y. Bai _et al._ , “Fast end-to-end speech recognition via non-autoregressive models and cross-modal knowledge transferring from bert,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 29, pp. 1897–1911, 2021.
  * [19] J. Devlin, M. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding,” _CoRR_ , vol. abs/1810.04805, 2018. [Online]. Available: http://arxiv.org/abs/1810.04805
  * [20] A. Kannan _et al._ , “An analysis of incorporating an external language model into a sequence-to-sequence model,” in _Proc. ICASSP_. IEEE, 2018, pp. 1–5828.
  * [21] Y. Li, Y. Wu, J. Li, and S. Liu, “Prompting large language models for zero-shot domain adaptation in speech recognition,” _arXiv preprint arXiv:2306.16007_ , 2023.
  * [22] A. Gulati _et al._ , “Conformer: Convolution-augmented transformer for speech recognition,” in _Proc. Interspeech_ , 2020, pp. 5036–5040.
  * [23] T. Wang _et al._ , “What language model architecture and pretraining objective works best for zero-shot generalization?” in _International Conference on Machine Learning_. PMLR, 2022, pp. 22 964–22 984.
  * [24] H. Soltau, H. Liao, and H. Sak, “Reducing the Computational Complexity for Whole Word Models,” in _Proc. ASRU_. IEEE, 2017, pp. 63–68.
  * [25] C.-C. Chiu, W. Han, Y. Zhang _et al._ , “A comparison of end-to-end models for long-form speech recognition,” in _Proc. ASRU_. IEEE, 2019, pp. 889–896.
  * [26] C.-C. Chiu _et al._ , “Rnn-t models fail to generalize to out-of-domain audio: Causes and solutions,” in _Proc. SLT_. IEEE, 2021, pp. 873–880.
  * [27] W. R. Huang _et al._ , “E2e segmenter: Joint segmenting and decoding for long-form asr,” _Proc. Interspeech 2022_ , pp. 4995–4999, 2022.
  * [28] A. Conneau _et al._ , “Fleurs: Few-shot learning evaluation of universal representations of speech,” in _Proc. SLT_. IEEE, 2023, pp. 798–805.
  * [29] S. Bubeck _et al._ , “Sparks of artificial general intelligence: Early experiments with gpt-4,” _arXiv preprint arXiv:2303.12712_ , 2023.
  * [30] W. R. Huang _et al._ , “E2e segmentation in a two-pass cascaded encoder asr model,” in _Proc. ICASSP_. IEEE, 2023, pp. 1–5.
  * [31] W. R. Huang, H. Zhang, S. Kumar, S.-y. Chang, and T. N. Sainath, “Semantic segmentation with bidirectional language models improves long-form asr,” _arXiv preprint arXiv:2305.18419_ , 2023.
  * [32] R. Zazo Candil, T. N. Sainath, G. Simko, and C. Parada, “Feature learning with raw-waveform cldnns for voice activity detection,” _Proc. Interspeech 2016_ , pp. 3668–3672, 2016.


Batch labeling workflow using cVIL for labeling 4,000 images according to hair
color: (1) selecting a range of images with low uncertainty for black hair
from the class density plot (A) yields a preview of images with the highest
uncertainty in the selection (C). (2) The anticipated target class (“black”)
is selected from the class distribution view (B), which shows the proportion
of instances already labeled individually (_instance_ labels) or through a
range selection (_batch_ labels). (3) The user confirms the target class (if
all persons have black hair) by labeling all images in (C) in a batch manner
(D) – or updates the selection (if not all persons have black hair; A).

# cVIL: Class-Centric Visual Interactive Labeling

Matthias Matt10009-0001-6195-3169, Matthias Zeppelzauer20000-0003-0413-4746,
Manuela Waldner10000-0003-1387-5132
1TU Wien, Institute of Visual Computing & Human-Centered Technology, Austria
2St. Pölten University of Applied Sciences, Austria

###### Abstract

We present cVIL, a class-centric approach to visual interactive labeling,
which facilitates human annotation of large and complex image data sets. cVIL
uses different property measures to support instance labeling for labeling
difficult instances and batch labeling to quickly label easy instances.
Simulated experiments reveal that cVIL with batch labeling can outperform
traditional labeling approaches based on active learning. In a user study,
cVIL led to better accuracy and higher user preference compared to a
traditional instance-based visual interactive labeling approach based on 2D
scatterplots.

<ccs2012> <concept>
<concept_id>10003120.10003145.10003147.10010365</concept_id>
<concept_desc>Human-centered computing Visual analytics</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003120.10003123.10010860.10010858</concept_id>
<concept_desc>Human-centered computing User interface design</concept_desc>
<concept_significance>300</concept_significance> </concept> </ccs2012>

[500]Human-centered computing Visual analytics [300]Human-centered computing
User interface design

##  1 Introduction

Reducing costs for human annotation of unlabeled, unstructured data, such as
image collections, has been widely studied. One standard methodology
originating from the domain of machine learning is active learning (AL), where
the model steers the labeling process [Set09]. One prominent AL strategy is
uncertainty-based selection where the most ambiguous instance is selected for
labeling [FZL12].

Using AL, the user’s role is, however, limited to labeling those instances
that are autonomously selected by the system, which can easily get tedious and
frustrating to users [ACKK14]. A successful approach for integrating user
initiative in the labeling process is visual interactive labeling (VIL). VIL
has been found superior to AL at least for simple labeling tasks [BHZ∗18]. VIL
systems typically show parts or all data in a visualization, where the user
can interactively select instances for labeling. For example, Seifert and
Granitzer [SG10] show the model confidence for all instances and classes in a
radial visualization. VIL has been extended by guidance mechanisms [GCT22] and
semi-automatic labeling approaches based on clustering [CBB∗19, BT20]. Some
systems also allow interactively selecting a threshold based on confidence
[BGTF21] to label samples or other predefined metrics to grow clusters based
on distance [SKK20] or purify clusters based on outlier scores [BT20]. To
combine the strengths of VIL and AL, Bernard et al. [BZSA18] have introduced a
process model, which allows both the model and user to select instances for
labeling.

Typically, VIL approaches, as described above, are _instance-centric_ , i.e.,
they show the class assignment of all data instances to be labeled in some
spatial representation like a 2D scatterplot. We refer to such systems as
iVIL. When working with large amounts of data, it is impractical to interact
with the data directly [CTBA∗11]. Consequently, the visualization in a
scatterplot can limit the system’s scalability with respect to the amount of
data to be visualized and labeled – especially if the data distribution in the
projection space is complex and classes strongly overlap in the projection
[NA18]. Furthermore, the preceding dimensionality reduction may introduce
(non-linear) distortions. Figure 1 illustrates the limitation of scatterplots:
It shows t-SNE [vdMH08] projections of two subsets of the CelebA [LLWT15]
dataset (which we call CelebHair and CelebGlasses), where the classes refer to
a person’s hair color (upper plot) and whether or not they wear glasses (lower
plot). Each dataset comprises 1,000 images per class. The images are
represented by DINO embeddings [CTM∗21]. Color encodes the ground truth class
for illustration. It is easy to see that labeling this data (imagine all
points would be gray because no labels exist yet) becomes a complex and
tedious task. Selecting individual instances is time-consuming, and selecting
multiple instances of one class at once is difficult, due to the large class
overlaps.

Figure 1: t-SNE projection of high dimensional embeddings found by
representation learning, used for the iVIL approach in our user study.

To address the above challenges, we propose a _class-centric_ VIL approach,
named cVIL. The main contributions are:

  * •

A new visual interactive labeling approach, which combines principles of AL
(the computation of well-understandable properties) and VIL (leaving the
initiative for selecting items to be labeled to the user; Section 2.1).

  * •

A labeling interface that scales independently of the number of data instances
(Section 2.2) and allows for efficient instance and batch labeling (Section
2.3).

  * •

Results from simulations that demonstrate better efficiency compared to AL
(Section 3) and from a user study that show higher labeling accuracy and user
preference compared to iVIL (Section 4).

##  2 Class-Centric Visual Interactive Labeling

cVIL provides a visual overview of class-centric property measure values
[BHS∗21] from which users can select instances or batches of instances for
labeling. By showing distributions of property measures across instances at a
class level rather than features per instance, cVIL disentangles the visual
representation from the number of instances and helps users to interactively
train a classifier guided by property measures. This can speed up the labeling
process considerably.

###  2.1 Measures

By observing participants during an instance-centric visual labeling process,
Bernard et al. [BHZ∗18] found that participants use specific strategies while
labeling. These strategies were later formalized into the concept of _property
measures_ [BHS∗21]. For cVIL, we experimented with three representative and
complimentary property measures, which either use the model output, data
distribution, or both to calculate the final result:

Min-Margin: This property measure is based on class probability, defining Min-
Margin as the difference between the largest and second-largest class
probability value. To get a measure of uncertainty, the resulting value is
subtracted from 1. For example, given a class assignment $(0.1,0.1,0.5,0.3)$
for a single instance, the uncertainty of this instance based on Min-Margin is
given by $1-(0.5-0.3)=0.8$.

Eccentricity: We define sample eccentricity as the Euclidean distance to the
overall median of the data. Before calculating the distance, each dimension is
first scaled by the inverse of its respective variance. The variance is
computed over the entire input data. This measure is completely data-centric
(i.e. model-independent) in contrast to the others and enables the
identification of outliers in the data distribution.

Disagreement: The average Jensen-Shannon distance between a data point’s class
probability distribution and that of all its neighbors defines its
disagreement in relation to its neighborhood. The neighborhood of a sample is
defined by the $k$-nearest neighbors based on Euclidean distance. While the
neighbors of a sample are selected from the data space, the resulting property
measure value is calculated based on the class probability distribution of the
neighbors, making it a hybrid approach. A value of $k=20$ was chosen for all
evaluations. This measure highlights instances in particularly inhomogeneous
regions wrt. class assignments in the feature space.

###  2.2 Visual Encoding

The property measures output one scalar value per unlabeled data instance,
whereby each data instance is assigned to the predicted class based on the
probability output of the model for this instance. The visual encoding,
therefore, only needs to convey a univariate distribution per class. To ensure
scalability with the number of data instances, we chose an area plot based on
kernel density estimation (KDE) of the values, as shown in Figure cVIL: Class-
Centric Visual Interactive Labeling (A). The x-axis represents the values of
the respective property measure (e.g., Min-Margin), and the y-axis is the
estimated density of instances corresponding to this value. The x-axes of the
plots are not shared because only the relative position within each class
partition is relevant for labeling.

###  2.3 Interaction Design

The KDE class distribution plots allow users to preview images by hovering or
selecting images within a certain property measure range (see Figure cVIL:
Class-Centric Visual Interactive Labeling). In the preview panel, images with
the largest property measure values in the selection will then be displayed,
which tend to represent the most uncertain images within the selection – and,
therefore, the most important ones for the learning and labeling process. The
number of image previews is limited to the size of the panel. Hovering over
the KDE class distribution plot updates the preview images so that images with
equal or lower property measure values are shown. This way, the user can
quickly validate model predictions, making cVIL also suitable for _Quality
Assurance for Machine Learning_ (QA4ML) [ZTdJ∗21] tasks.

After making a selection in the KDE plot and selecting a target class, users
have two options for how they can assign the label of the selected target
class to the images: using _instance labeling_ , users click on individual
images from the preview to label them with the selected class. This is the
most useful interaction after a cold start and when selecting images after
making an outlier selection (i.e., selecting images with a high uncertainty
score for a particular class) to identify and label particularly difficult
instances.

The second option is _batch labeling_ , which can be used to quickly confirm
class predictions for instances that are rather certain. Low property measure
values are a good indicator for such instances. If users think that all
instances within the selected range do belong to the selected target class,
they just press a button to label all instances from the current selection in
the KDE plot at once, as illustrated in Figure cVIL: Class-Centric Visual
Interactive Labeling. Note that this may lead to the labeling of more images
than are currently visible in the preview panel and, therefore, may produce
wrong labels for out-of-class examples. To prevent this, users can validate
the selection range with the hover preview to make sure the images are
correct. In our user study (Section 4), we did not observe that batch labeling
led to a critical number of incorrect labels. After model retraining, which
took an average of three seconds in our user study, all KDE plots are updated
with the new property measure values. Due to the relatively short re-training
time, users can easily update the model while labeling.

##  3 Quantitative Experiments: cVIL vs. AL

Firstly, we compared the property measures in terms of their runtime. When
benchmarking our implementation of the three property measures with an M1
MacBook Pro, we found that – for an embedding size of 1,024 dimensions and up
to more than 16,000 samples – the property measures for all instances can be
calculated in less than a second. In particular, the results for Disagreement
took close to one second to calculate, while Eccentricity took less than 100ms
and Min-Margin only around 1ms.

To assess the performance of the selected property measures and the potential
of cVIL, we compared the theoretical performance of cVIL (accuracy per
simulated labeling step) to AL. For evaluation we use MNIST [LCB10], STL10
[CNL11], as well as CelebHair and CelebGlasses. For MNIST, the raw pixels are
used as training data. For the more complex datasets, we use DINO [CTM∗21] for
representation learning for the simulations as well as the user study. The
backbone model of DINO is a vision transformer, which was pre-trained on
ImageNet [DDS∗09].

We simulate instance labeling by selecting samples with the highest property
measure value in each class partition and assigning them their correct ground
truth label. An equal number of samples are selected from each class to get a
total of ten samples per iteration. For example, for STL10, one sample with
the highest property measure value per class is selected. We simulate optimal
batch labeling by selecting instances with the lowest property measure value
up to the first incorrectly predicted instance for labeling. Therefore, the
number of samples in a batch selection can vary, depending on the accuracy of
the model and property measures.

The classifier is a multi-layer perceptron with two hidden layers consisting
of 50 and 20 neurons. Batch labels are given a lower sample weight during
training, which is realized by assigning them lower costs in the loss function
before back-propagation. The number of batch labels that are used for each
class during training is determined by the number of samples $C_{min}$ in the
class with the fewest instance labels. In the evaluations, $10\cdot C_{min}$
instances were then randomly sampled from the batch labels of each class. The
weights of samples labeled through batch labeling were set to 0.1.

Based on the evaluation results with MNIST and STL10 datasets, shown in Figure
2, we observed that Disagreement and Eccentricity are less effective for
instance labeling. Min-Margin leads to faster model improvement and is en par
with AL simulations that also use Min-Margin. This indicates that class
partitioning with instance labeling is comparable in performance to AL. For
STL10, Eccentricity shows slightly better results than Disagreement, while the
opposite is true for MNIST. For CelebHair and CelebGlasses, Eccentricity has a
considerably lower accuracy, while all other methods – including AL – perform
similarly. To summarize, instance labeling using cVIL performs best with Min-
Margin and yields comparable performance to Min-Margin-based AL.

For batch labeling, we observe that Disagreement and Eccentricity slightly
outperform Min-Margin for MNIST and both strategies outperform AL. For
CelebHair and CelebGlasses, all methods perform similarly well. For STL10,
which is the most complex dataset, cVIL clearly outperforms AL with all three
property measures, with peak performance for Eccentricity. To sum up, batch
labeling can easily compete with AL and outperforms it, in particular for
complex data, even when using the same measure (Min-Margin). Surprisingly, a
purely data-driven strategy (Eccentricity) outperforms all others. Our
experiments show that cVIL with batch labeling has clear potential to
outperform traditional AL.

Figure 2: cVIL with Min-Margin is en par with AL for instance labeling (left).
For batch labeling, cVIL outperforms AL independently of the property measure
(right).

##  4 User Study: cVIL vs. iVIL

In the user study, we compare our class-centric VIL interface (cVIL) to a
simple instance-centric VIL interface (iVIL). For the iVIL baseline interface,
the KDE plots from Figure cVIL: Class-Centric Visual Interactive Labeling (A)
are replaced with a t-SNE [vdMH08] projection of the DINO feature vectors
[CTM∗21], as shown in Figure 1. The colors shown in the interface represent
the _predicted_ labels associated with the data instances. Users can either
label individually selected instances or perform batch labeling using a lasso
selection in the scatter plot. Our hypothesis is that cVIL is more effective
at labeling than iVIL while being less demanding and more preferable to use.

###  4.1 Study Design

Participants: The user study was conducted with 16 participants (11 male, 4
female, 1 non-binary). All of them had a background in computer science, with
4 being post-graduate, 6 graduate, and 6 undergraduate level. Moreover, 11 of
the participants had prior experience with machine learning. All participants
were between 22 and 40 years old with a median age of 26.

Task: During the study, the participants were given labeling tasks. The system
was not initialized, which meant that participants had to first label samples
based on a random selection to train the model at which point the full
interface became available. The task was considered complete only when
participants believed that all the data points had their correct label –
either assigned manually by the user or predicted by the model. The
participants had to decide when this stage was reached and were instructed to
export the labels at that point. The entire study, including setup and
introduction, was estimated to take approximately one hour to complete.

Data: We asked users to label the CelebGlasses and CelebHair data sets (see
Figure 1). To reduce the complexity of the CelebHair dataset, a subset with
only black and gray hair was used. To reduce the amount of time required for
labeling, the number of samples was limited to 1,000 per class. For the user
study, only Min-Margin was available to the participants due to its simplicity
and good overall performance. This further reduced the task complexity by only
presenting users with a single measure to focus on.

Independent and dependent variables: The study used a within-subjects design,
with the interface (cVIL vs. iVIL) as the independent variable. We also varied
the dataset assigned to the two interfaces, as well as the order of appearance
of the interfaces. The overall accuracy of both manual and predicted labels,
labeling time, cognitive demand, and preference were the dependent variables
being observed.

Procedure: Participants were provided with a tutorial sheet that explained the
system’s components and how to interact with them prior to attempting the
task. They solved the tasks on an external monitor and had access to a mouse
and keyboard. The study was conducted on an M1 MacBook Pro. After solving each
task, the participants completed a NASA TLX questionnaire to evaluate the
perceived cognitive demand of the tasks. Upon completing the study,
participants were asked to express their likes and dislikes about each
interface and indicate their preference.

###  4.2 Results

Of the 16 participants, 15 successfully finished the study. One user
accidentally selected an incorrect target class for a batch labeling action
using cVIL, which led to a dramatic reduction in accuracy. We excluded this
participant from further analysis (see Section 5 for our learnings from this
case).

All remaining participants performed better using cVIL compared to iVIL. The
median accuracy of the exported labels compared to the ground truth was 96.05%
for iVIL, whereas it was 98.4% for cVIL, as can be seen in Figure 4, which is
a statistically significant difference ($t(14)=5.784$, $p<.001$).

Figure 3:  Final accuracy.

Figure 4:  Completion time.

When comparing the final accuracy (measured against the ground truth) in
dependence on the number of instance labels, we observe that cVIL achieves
considerably better accuracy with fewer labels, as can be seen in Figure 6.
The solid lines represent a robust linear regression estimation of the results
for each framework. cVIL achieves around the same accuracy with 100 labels as
iVIL with 600. Notably, these results were achieved solely through instance
labeling, as can be seen in Figure 6. Interestingly, the accuracy is not
significantly affected by the number of generated batch labels in both
conditions (except for one outlier in iVIL). Participants batch-labeled an
average of 600 samples in cVIL and 315 in iVIL, but this difference in the
number of labels is not statistically significant ($t(14)=1.570$, $p=0.14$).

We also measured the time it took to finish the labeling task by looking at
the difference between the first and the last labeling action or model
retraining. Participants generally needed less time to finish the labeling
tasks in cVIL as can be seen in Figure 4. The median labeling time for iVIL
was around 18:30 minutes compared to 16 minutes for cVIL, however, this
difference is not statistically significant ($t(14)=-1.947$, $p=0.07$).

Figure 5:  Final accuracy by number of instance labels.

Figure 6:  Final accuracy by number of batch labels.

To analyze task load, we aggregated the scores from the NASA TLX questionnaire
as described by Rubio et al. [RDMP04], where we weighted Frustration highest,
followed by Mental Demand, Effort, Performance, and finally Temporal Demand.
We could detect no difference between cVIL and the baseline (Wilcoxon Signed-
Rank test: $z=-0.879;p=0.39$).

In the final questionnaire, however, 13 out of 16 participants stated that
they preferred cVIL over the iVIL baseline implementation. The main reason for
this was that participants found the system easier to use as it helped them to
better spot false positives and outliers, evaluate current model performance,
and re-label incorrect predictions. Having information about uncertainty made
it easier to label and gave a better indication of the model’s accuracy.
Participants reported that the class partitioning made it easier to focus on
one particular class, and participants only needed to identify false positives
when deciding if a class label was correct, rather than having to consider the
possibility of having true and false negatives as in an instance-based
approach. However, participants disliked that there was too little change in
the visual representations after the model updates. Four participants reported
that the iVIL baseline was also easier to understand and navigate as well as
more engaging and fun to use. However, six other participants felt it was more
tedious and ambiguous since images were harder to find.

##  5 Discussion and Conclusions

In our study, users could label 2,000 photos in a reasonable time and with
high accuracy with both interfaces. All users could achieve higher performance
using cVIL, and most participants preferred it over the instance-based
baseline. This confirms that class-centric VIL is promising when data is
getting more complex – even though the data used for our user study was still
relatively small. We conclude that scatterplots provide a less reliable way to
judge model performance when class distributions strongly overlap compared to
our class-centric property measure distribution plots. We found that cVIL can
address these limitations and provide effective feedback with large and
complex datasets while still being fully interactive.

Our study showed several directions for improvements of cVIL. In our study, we
had to exclude one user because of an incorrect target class selection for
batch labeling, which had drastic consequences on model accuracy. This could
have happened with both interfaces and could be easily prevented for cVIL by
warning the user if the selected target class does not correspond to the class
density plot from which the selection was made. Generally, batch labeling
using Min-Margin as the property measure (and also lasso selections in the
baseline) did not notably contribute to model accuracy. In our simulations,
data-based property measures produced more promising results for batch
labeling. In the future, the usage of different property measures for instance
and batch labeling should be investigated and empirically evaluated. Both our
simulations and the user study show that cVIL is a promising approach in cases
where data complexity becomes high and sample sizes are large, as is typically
the case in real-world scenarios. Therefore, focusing on one class at a time
and enabling the user to switch between instance and batch labeling depending
on the state of the learning process shows to be of central importance.

A number of open topics remain for future investigation, such as the choice of
the most suitable property measure, investigating different batch labeling
strategies (including methodology from semi-supervised learning), and
systematically evaluating the impact of data set size, features, and class
properties on instance- and class-centric VIL performance.

## Acknowledgements

We thank Professor Takeo Igarashi for valuable discussions and all
participants of the user study for their time.

This research was funded in whole or in part by the Austrian Science Fund
(FWF) 10.55776/P36453. For open access purposes, the author has applied a CC
BY public copyright license to any author accepted manuscript version arising
from this submission.

## References

  * [ACKK14] Amershi S., Cakmak M., Knox W. B., Kulesza T.:  Power to the people: The role of humans in interactive machine learning.  _Ai Magazine 35_ , 4 (2014), 105–120.
  * [BGTF21] Benato B. C., Gomes J. F., Telea A. C., Falcão A. X.:  Semi-automatic data annotation guided by feature space projection.  _Pattern Recognition 109_ (2021), 107612.
  * [BHS∗21] Bernard J., Hutter M., Sedlmair M., Zeppelzauer M., Munzner T.:  A taxonomy of property measures to unify active learning and human-centered approaches to data labeling.  _ACM Trans. Interact. Intell. Syst. 11_ (2021), 20:1–20:42.
  * [BHZ∗18] Bernard J., Hutter M., Zeppelzauer M., Fellner D. W., Sedlmair M.:  Comparing visual-interactive labeling with active learning: An experimental study.  _IEEE Transactions on Visualization and Computer Graphics 24_ (2018), 298–308.
  * [BT20] Beil D., Theissler A.:  Cluster-clean-label: an interactive machine learning approach for labeling high-dimensional data.  _Proceedings of the 13th International Symposium on Visual Information Communication and Interaction_ (2020).
  * [BZSA18] Bernard J., Zeppelzauer M., Sedlmair M., Aigner W.:  Vial: a unified process for visual interactive labeling.  _The Visual Computer 34_ (2018), 1189–1207.
  * [CBB∗19] Chegini M., Bernard J., Berger P., Sourin A., Andrews K., Schreck T.:  Interactive labelling of a multivariate dataset for supervised machine learning using linked visualisations, clustering, and active learning.  _Vis. Informatics 3_ (2019), 9–17.
  * [CNL11] Coates A., Ng A., Lee H.:  An analysis of single-layer networks in unsupervised feature learning.  In _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ (2011), JMLR Workshop and Conference Proceedings, pp. 215–223.
  * [CTBA∗11] Chen M., Trefethen A. E., Bañares-Alcántara R., Jirotka M., Coecke B., Ertl T., Schmidt A.:  From data analysis and visualization to causality discovery.  _Computer 44_ (2011), 84–87.
  * [CTM∗21] Caron M., Touvron H., Misra I., J’egou H., Mairal J., Bojanowski P., Joulin A.:  Emerging properties in self-supervised vision transformers.  _2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ (2021), 9630–9640.
  * [DDS∗09] Deng J., Dong W., Socher R., Li L.-J., Li K., Fei-Fei L.:  Imagenet: A large-scale hierarchical image database.  _2009 IEEE Conference on Computer Vision and Pattern Recognition_ (2009), 248–255.
  * [FZL12] Fu Y., Zhu X., Li B.:  A survey on instance selection for active learning.  _Knowledge and Information Systems 35_ (2012), 249–283.
  * [GCT22] Grimmeisen B., Chegini M., Theissler A.:  Visgil: machine learning-based visual guidance for interactive labeling.  _The Visual Computer 39_ (2022), 5097 – 5119.
  * [LCB10] LeCun Y., Cortes C., Burges C.:  MNIST handwritten digit database.  _ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist 2_ (2010).
  * [LLWT15] Liu Z., Luo P., Wang X., Tang X.:  Deep learning face attributes in the wild.  In _ICCV_ (2015), IEEE Computer Society, pp. 3730–3738.
  * [NA18] Nonato L. G., Aupetit M.:  Multidimensional projection for visual analytics: Linking techniques with distortions, tasks, and layout enrichment.  _IEEE Transactions on Visualization and Computer Graphics 25_ , 8 (2018), 2650–2673.
  * [RDMP04] Rubio S., Diaz E. M. C., Martin J., Puente J. M.:  Evaluation of subjective mental workload: A comparison of swat, nasa-tlx, and workload profile methods.  _Applied Psychology 53_ (2004), 61–86.
  * [Set09] Settles B.:  _Active learning literature survey_.  Tech. rep., University of Wisconsin-Madison Department of Computer Sciences, 2009.
  * [SG10] Seifert C., Granitzer M.:  User-based active learning.  _2010 IEEE International Conference on Data Mining Workshops_ (2010), 418–425.
  * [SKK20] Schröder S.-M., Kiko R., Koch R.:  Morphocluster: Efficient annotation of plankton images by clustering.  _Sensors 20_ , 11 (2020), 3060.
  * [vdMH08] van der Maaten L., Hinton G. E.:  Visualizing data using t-sne.  _Journal of Machine Learning Research 9_ (2008), 2579–2605.
  * [ZTdJ∗21] Zhang Y., Tennekes M., de Jong T., Curier L., Coecke B., Chen M.:  Simulation-based optimization of user interfaces for quality-assuring machine learning model predictions.  _ACM Transactions on Interactive Intelligent Systems_ (2021).