\section{Introduction}

\noindent Nowadays computer security has become a necessity brought by the fast evolution of information technologies.
The expansion of the network architectures, such as cloud computing, revealed increasingly higher number of threats than before. According to 2021 Cyberthreat Defense Report \cite{Cyber}, the percentage of organizations compromised
by successful attacks rose by 5.5 \%, which seems to be the largest in the last 7 years. These attacks include malware, ransomware, Denial-of-Service (DoS) and Advanced Persistent Threats (APT).
Despite the fact that security research investments are on a positive trend, alleviation of these threats is not optimistic \cite{Cyber}. However, the constant progress and performance of the recent Intrusion Detection Systems (IDS) bring a  positive light on the subject.

One side of the modern IDSs approaches the intrusion detection as an anomaly detection problem. Detecting outliers in finite samples of data is an old statistical topic, alongside with the design of robust estimators that are resistant to corrupted data points \cite{Hub:04}. From this viewpoint, detecting a network intrusion reduces to learning a statistical estimator that is capable to distinguish between normal and abnormal traffic. However, there are two obvious issues to address. Related to first, one could find a plethora of results in the literature that confirm the efficiency of this statistical approach for usual attacks such as DoS, Probe, User to Root, Remote to User etc. However, in large networks, there is often the case when the attacker uses a stolen set of credentials to obtain data (or access) from (to) multiple nodes of the networks. In this case, while the traffic parameters may seem close to normal, the change in the graph connectivity pattern could reveal an abnormal behavior. In his malicious pursuit, the attacker will probably walk from node to node, through lateral movement, on paths that a normal user would never follow. Therefore, the underlying graph representation of the network traffic, where the nodes are the computers and the edges are the traffic sessions, becomes necessary. Secondly, the real network traffic is by nature not labeled.  Although the most challenging, unsupervised AD methods seems the most intuitive approach of an intrusion detection task.

In this paper we bring a preliminary evidence showing that the graph connectivity may be an important asset in some cases for unsupervised intrusion detection. We design a simple processing strategy of given flow data that enrich the feature vectors with additional graph embeddings. Our graph embedding method is based on computing egonets of each network node and extract their key features. After training on the extended features, the accuracy of several unsupervised AD algorithms shows slight improvements.

\subsection{Related work}
Several wide-range anomaly detection techniques that are often used in network IDSs are listed as follows: Statistical Profiling with Histograms \cite{Ilg:95,Yam:01}, Parametric and Non-parametric Statistical Modeling \cite{Gwa:05,Yeu:02}, (Deep or Shallow) Artificial Neural Networks and Autoencoders \cite{Gam:20,Cho:21,Ahm:21,Yin:17}, (One-Class) Support Vector Machines \cite{Gor:09,Per:06}, Reconstruction methods \cite{Vas:16,Shy:03,Kir:20}, Clustering methods \cite{Ahm:18,Yao:18}. However, generally most of these learning systems detect abnormal data flows or packets based on their features and characteristics. Besides the track imprinted in these features, many attacks manifest their tracks into anomalous underlying connection graph, and therefore graph anomaly detection techniques become an important tool for more insight \cite{Ako:15}.

Graph embedding is used in \cite{He:12}, where the flow data is viewed as an entropy time series, whose features are mapped as nodes in an undirected graph. Here, after computing weights on edges based on covariance between features, the authors devise an algorithm that assign an anomaly score on each flow. Spectral decomposition methods are applied in  \cite{Che:16} to intrusion detection problem. Their method keeps only statistical and spectral features of a given connectivity graph to detect traffic anomalies. In \cite{Cap:19} are used attack graphs to analyze the state evolution of multi-layered attacks in a vulnerable system. We mention that the vertices in these graphs are the attack states and actions, since they serve to modeling of the causality of vulnerability exploitation.

In \cite{Xia:20} the authors devise an IDS that, based on a double graph embedding, expand an original set of features into a new one containing graph embedding information. Their overall approach is vaguely similar to ours, however the embedding procedure and classification algorithms are not related. In the final, they used supervised learning algorithms to classify enhanced features of datasets CIDDS-001 and CIC-IDS2017.
\vspace{5pt}

\noindent \textit{Paper structure}. In the following Section we describe our graph embedding and feature expansion procedures. We evaluate the empirical performance of these embedding procedures, in Section~\ref{sec:experiments}, by comparison with the application of traditional anomaly detectors onto several well-known datasets. Lastly, we discuss and interpret our result in Section~\ref{sec:results}.

\section{Methodology}
\label{sec:methodology}

\noindent As presented in the introduction, the main steps of our method reduce to: $(i)$ embedding of the network flows into a directed graph; $(ii)$ extraction of several statistical node features from the graph and expand the original feature set. We use notation $X \in \mathbf{R}^{m \times N}$ for flow data, where $m$ is the number of features of a given flow and $N$ the number of flows.

\vspace{5pt}

\noindent First, given a set of fixed IPs within a network, mapping them  into integers set $[n]:=\{1, 2, \cdots, n\}$, where $n$ is the number of machines in the network, is straightforward. Now we further consider the graph $\mathcal{G} = \{V,E,W\}$, where the set of vertices $V = \{1,2, \cdots, n\}$, $E$ is the set of edges between nodes, corresponding to connections between pairs of IPs, and $W$ is a weight matrix. For instance, given a flow representation between two IPs let $(i,j) \equiv (\text{source}\_IP,\text{destination}\_IP)$, then  $(i,j) \in E$ if there exists a flow between IPs mappings $(i,j)$ and the value $w_{ij}$ on $i$th column and $j$th line in matrix $W$ defines some summable feature, for example the number of packets transmitted between source and destination.

\begin{figure}[t]
    \centering
    \includegraphics[width=7cm,height=5cm]{Graph_netalert.png}
    \caption{Subgraph enclosed by dashed line represents the egonet of node 1.}
    \label{fig:egonet}
\end{figure}

An \textit{egonet} of node $i$ is defined as the subgraph formed by all neighbors linked to node $i$ \cite{Ako:15}, as described by Figure \ref{fig:egonet}. Notice that egonets associated to different nodes may have different dimensions, depending on the degree of each node.

\noindent Mainly, our scheme consists of the following three steps:

\vspace{5pt}

\noindent I. \textbf{Flow-to-graph}. The first step performs the conversion of data from flow format into graph format, by retaining source, destination addresses $(i,j)$ and a particular attribute which represents the weight $w_{ij}$. This particular attribute may be any real-valued summable feature in the original data $X$. Since multiple flows may occur multiple times between the same pair of nodes, we get multiple weights $w_{ij}^t$, where $t$ is time counter. We sum over $t$ these weights in order to obtain a final weight: $w_{ij} = \sum_t w_{ij}^t$.

Based on the obtained graph features and weights, we form the directed graph associated with our data.

\vspace{5pt}

\noindent II. \textbf{Graph-to-features}.
Now on this resulted graph we perform the following operations:
\begin{enumerate}
    \item[1)] Extract all the egonets and stack them into $\mathcal{E}$, where each $\mathcal{E}_i \in \mathcal{E}$ is the egonet associated to node $i \in V$.
    \item[1')] Extract a  random-walk of size $\ell$  for each node. Denote $\mathcal{E}_i \in \mathcal{E}$ as the random-walk associated to node $i$ in $V$. Starting at node $i$, for at most $\ell$ iterations, a neighbor of the current node is randomly chosen  (w.r.t. a uniform probability distribution) and its associated edge is added to the subset $\mathcal{E}_i$. The new chosen node becomes the current node and a new iteration is performed. If either the node $i$ or the walk length $\ell$ are reached, the process terminates and outputs the walk.
    \item[2)] For any $i \in [n]$, extract $p$ features of the egonet/random walk instance $\mathcal{E}_i$. Denote $z_i \in \mathbf{R}^p$ the vector of these features.
    \item[3)] Output matrix $Z \in \mathbf{R}^{p \times n}$, as the array containing all egonet features.
\end{enumerate}
First we perfom only once a single step of the two alternatives $1)$ or $1')$. Notice that the random-walk $\mathcal{E}_i$ computed in scenario $1')$ is not limited to the egonet neighborhood
of node $i$. The statistical features computed in step $2)$, after step $1)$, include: dimension of egonet, the number of out-links, the number of in-links. In alternative scenario $1')$ they include the weight on the first leg of the walk or the weight transferred all the way from the first node to the last one of the walk. The full description of all features can be find in \cite{graphomaly}.

\vspace{5pt}

\noindent III. \textbf{Feature expansion}. Lastly, we expand the original data by adding the columns of $Z$ as prolongation of columns in $X$. Thus, for a given flow $x_t \in X$ from source $i$ to destination $j$, we form:
$$\hat{x}_t = \begin{bmatrix}x_t \\ z_i \\ z_j \end{bmatrix} \in \mathbf{R}^{m+2p}.$$
The matrix $\hat{X}$ containing columns $\hat{x}_t$ for $t \in [N]$ is the output of our scheme.

\noindent First, notice that the graph embedding at step II maps the flows from $X $ with size $m \times N$ into a final matrix $Z$ with size $p \times n$. By comparison, a column sample of $X$ corresponds to an edge/flow in the graph, while in $Z$ a column associates with a node. In the next section, we show the performance of AD tools in detecting  anomalous nodes.

Second, the step III is equivalent with inserting local topological information into flow features. Therefore the attacks that forces anomalous connections between machines are likely to be reflected into graph features $\{z_i,z_j\}$ and detected by an usual anomaly detection.

We further test the performance of several anomaly detections such as: One Class-SVM, Isolation Forests and Local Outlier Factor, onto the data output of the above processing procedure.

\begin{table*}[t]

\tabcolsep 5pt

\caption{Maximum balanced accuracy and running times when tuning parameters on 1\% of the available data.}
\label{table:grid-search-1p}
\small
\begin{center}
\begin{tabular}{c c l | c r | c r | c r | c r | c r | c }
Dataset&Method&($m$,$N$,outliers) &
\multicolumn{2}{c|}{OC-SVM} &
\multicolumn{2}{c|}{LOF} &
\multicolumn{2}{c|}{IForest} &
\multicolumn{1}{c}{Ensemble} \\
\hline
\multirow{3}{4em}{CIC-IDS2017}
& standard & (87, 4588, 5)
& 0.8751 & 0.81s
& 0.9751 & 0.01s
& 0.8751 & 0.07s
& \textbf{0.9152}   \\
& graph & (48, 382, 1)
& \textbf{0.9252} & 0.02s
& 0.9685 & 0.01s
& 0.4738 & 0.04s
& 0.8972  \\
& mixed & (183, 4588, 5)
& 0.8167 & 5.55s
& \textbf{0.9755} & 2.23s
& \textbf{0.9010} & 0.07s
& 0.8698  \\
\hline
\multirow{3}{4em}{UNSW-NB15}
&standard&(59, 4400, 321)
& 0.5831 & 2.43s
& \textbf{0.8663} & 0.46s
& \textbf{0.9584} & 0.70s
& \textbf{0.9511}   \\
&graph&(48, 42, 4)
& \textbf{0.7829} & 0.01s
& 0.7763 & 0.01s
&0.6053 & 0.03s
& 0.5   \\
&mixed&(155, 4400, 321)
& 0.5831 & 3.81s
& 0.8037 &9.73s
& 0.9216 & 0.14s
& 0.9123   \\
\end{tabular}
\end{center}
\end{table*}
\begin{table*}[t]

\tabcolsep 5pt

\caption{Balanced accuracy and running times
when training on 10\% of the data
from the UNSW-NB15 and CIC-IDS2017 datasets
with the parameters obtained in Table~\ref{table:grid-search-1p}
}
\label{tab:cic2017-unsw-training-10p}
\small
\begin{center}
\begin{tabular}{c c l | c c | c c | c c | c c | c c | c c}
Dataset & Method &($m$,$N$,outliers) &
\multicolumn{2}{c|}{OC-SVM} &
\multicolumn{2}{c|}{LOF} &
\multicolumn{2}{c|}{IForest} &
\multicolumn{1}{c}{Ensemble} \\
\hline
\multirow{3}{4em}{CIC-IDS2017}
& standard &(87, 45883, 928)
& 0.3724 & 242.30s
& \textbf{0.4811} & 529.12s
& 0.4132 & 0.35s
&  \textbf{0.4996}  \\

& graph & (48, 1999, 1)
& 0.4997   & 0.43s
& 0.4705 & 0.07s
& \textbf{0.4750} & 0.06s
& 0.4874  \\

& mixed &(183, 45883, 928)
& \textbf{0.5955} & 601.00s
& 0.4805 & 86.42s
& 0.4222 & 0.32s
& 0.4821   \\
\hline
\multirow{3}{4em}{UNSW-NB15}
& standard&(59, 44004, 5148)
& 0.6542 & 358.21s
& 0.5096 & 147.76s
& 0.7259 & 5.09s
& 0.5474  \\

& graph&(48, 46, 4)
& \textbf{0.7829} & 0.01s
& \textbf{0.6382} & 0.01s
& 0.3289 & 0.03s
& 0.5119  \\

& mixed & (155, 44004, 5148)
& 0.6619 & 579.19s
& 0.5775 & 750.70s
& \textbf{0.7926} & 0.82s
& \textbf{0.9103}   \\
\end{tabular}
\end{center}
\end{table*}

\section{Experiments}
\label{sec:experiments}

In this section we are interested in seeing numerical results of enhancing data
with graph specific features.
In our simulations we use
One-Class SVM~(OC-SVM)~\cite{Gor:09,Per:06},
Local Outlier Factor~(LOF)~\cite{Bre00},
Isolation-Forest~(IForest)~\cite{Liu:08},
and an ensemble~\cite{ensembles} that includes the above.
In the implementation of the latter we use voting methods~\cite{vote}.
In our tables and figures,
"standard" denotes the results on the plain data from the public datasets,
"graph" denotes the results on the data aggregated in the form of a graph,
and "mixed" the results on the plain data with the added graph features.

Even though we focus here on shallow machine learning methods,
which we prefer for their performance, speedy results, and known theoretical properties,
we also performed preliminary tests with autonecoder and variatonal autoencoder architectures
that have not yet shown promising results on the experimental setup presented here.

The experiments were performed using public datasets.
It contains different features of the flows which have been generated using the IBM QRadar appliance.
CIC-IDS2017\footnote{\url{https://www.unb.ca/cic/datasets/ids-2017.html}}
is created by the Canadian Institute of Cyber Security
simulating the benign behavior of 25 users
and replicating a series of attacks.
Flows extracted from this traffic contain 85 features.
UNSW-NB15 \footnote{\url{https://research.unsw.edu.au/projects/unsw-nb15-dataset}} is a dataset
which contains 49 features for the flows extracted using Bro-IDS and Argus tools.
Here, IXIA PerfectStorm tool was used to generate the underlying network traffic.

In order to run the experiments a dedicated station with 32 AMD Ryzen Threadripper PRO 3955WX CPUs was used.
Our implementation relied on the following software packages, among others:
pyod 0.9.6 \cite{pyod},
scikit-learn 1.0.2,
tensorflow 2.7.0,
graphomaly 0.1.

In line with our methodology,
we assume that we have access to a small initial dataset
depicting the normal state of the computers nodes inside the network
through their recorded traffic layer-3 traffic.
Thus,
in our experiments,
we only extract the first 1\% of samples from each dataset
and assume that this is known data with known labels on which we can initially train our models.
Even though we are only interested in the unsupervised setting,
the labels help us tune the parameters through grid-search techniques.
The datasets are laid out as time series,
meaning that the first selected samples reflect exactly the scenario described above.
We denote with $m$ the number of features and with $N$ the number of samples.

\begin{table}[t]

\tabcolsep 5pt

\caption{Types of Attacks detected on the UNSW-NB15 dataset with the ensembles from Table \ref{tab:cic2017-unsw-training-10p} (does not apply to the graph method)}
\label{tab:unsw-attacks}
\small
\begin{center}
\begin{tabular}{l |l |r |r }
Dataset &
Attack &
Detected &
Total \\
\hline
\multirow{9}{4em}{standard}
& Exploits
& 163
& 2088  \\

& DoS
& 79
& 1014  \\

& Fuzzers
& 29
& 516  \\

& Worms
& 0
& 7  \\

& Backdoor
& 11
& 138  \\

& Analysis
& 9
& 123  \\

& Shellcode
& 2
& 52  \\

& Reconnaissance
& 31
& 548  \\

& Generic
& 256
& 662  \\
\hline

\multirow{9}{4em}{mixed}
& Exploits
& 1933
& 2088  \\

& DoS
& 911
& 1014  \\

& Fuzzers
& 502
& 516  \\

& Worms
& 7
& 7  \\

& Backdoor
& 124
& 138  \\

& Analysis
& 109
& 123  \\

& Shellcode
& 47
& 52  \\

& Reconnaissance
& 506
& 548  \\

& Generic
& 644
& 662  \\

\end{tabular}
\end{center}
\end{table}
\section{Results}
\label{sec:results}

In Table~\ref{table:grid-search-1p}
we present the grid-search results on 1\% of the data
for both databases when using the standard, graph and mixed features.
The two columns underneath each method represent the balance accuracy~(BA) and the training execution time.
We can see that standard and mixed methods are giving similar BA results,
identical even for OC-SVM with UNSW-NB15,
but the standard ensemble performing better in both cases.
The execution times are lower for the graph methods,
where there is fewer data to process,
and longer for mixed methods where the graph features are added to the standard data.
The experiment objective is to obtain proper parameters to be used in future model training
on data where labels are not available.

Table~\ref{tab:cic2017-unsw-training-10p} uses the parameters obtained in Table~\ref{table:grid-search-1p}
to train the models on the next 10\% of available data from the time-series.
We see a clear degradation in the balanced accuracy compared to the tuned experiments:
the dataset is larger and new attacks are present and the model parameters are not optimal.
For CIC-IDS2017 all three approaches provide
similar results for the methods and the ensemble.
Instead,
on UNSW-NB15 we see an improvement offered by the graph-based approaches.
We assume that this is due to the richer summable attributes in UNSW-NB15
compared to CIC-IDS2017
where most of the attributes are either existing statistics (already summed) or flags information.
In terms of execution times,
we see a proportional increase corresponding to the ten-fold increase in analyzed data-points.

We further investigate the UNSW-NB15 results in Table~\ref{tab:unsw-attacks} where we compare the
standard and mixed ensembles for their capability of identifying specific types of attacks.
By identifying more attack samples,
the mixed method clearly outperforms the standard one in all scenarios.
Worm attacks are not even detected by the standard model.
\pdffig[\columnwidth]
    {fig-unsw}
    {Test results for the models from Table~\ref{table:grid-search-1p} on the UNSW-NB15 dataset.
    For graphical purposes, for each row the number of false positives (FP) are scaled in the $[0,1]$ interval.}
    {fig:unsw}
We now use the models form Table~\ref{table:grid-search-1p} as predictors
for the rest of the data samples from the UNSW-NB15 dataset.
Figure~\ref{fig:unsw} depicts the performance for different test dataset sizes:
10\%, 30\%, 50\%, 70\% and 100\%.
The True Positive Rates (TPR)
and
True Negative Rates (TNR) are analyzed
together with the number of False Positives (FP)
for all models, depicted on the columns,
and for all approaches, depicted on the rows.
For each row,
the number of false positives were scaled
such that the reader can see the relative differences
between each method.
As expected,
model performance degrades with time
as normal behaviour evolves and new types of attacks arrive.
We observe that OC-SVM is the most sensible to these changes,
while IForest seems more robust.
Ensembles tend to attenuate false positives and promote good TPR rates.

\section{Conclusions}
In this paper we studied the performance of unsupervised machine learning methods
when analyzing computer networks
by starting from a small dataset of known labeled packet samples
that we use to tune model parametrization
which we then use to investigate their performance for further unsupervised learning
on new incoming unlabeled data.
Data is augmented through graph feature extraction techniques,
such as egonets and random walks,
in order to improve the robustness of our models.

\bibliographystyle{unsrt}


\section{Introduction}
Due to an increasing ability to handle massive data with extraordinary model accuracy, machine learning (ML) algorithms have achieved remarkable success in many applications, such as computer vision \cite{KA2014VGG,SLJS2015GOOGLE,HZRS15Res,SVI2016INC} and natural language processing \cite{SVQ2014seq2,VSPU2017Attention,DCL2018BERT,YDY2019XLNET}.
However, empirical studies have also revealed that ML algorithms may incorporate bias from training data into model predictions.
Due to historical biases, vulnerable groups are often under-represented in available data \cite{JJSL2016, ZWY2017, SEC2019}.
As a consequence, without fairness considerations,  ML algorithms can be systematically biased against certain groups defined by protected attributes such as race and gender.

As algorithmic decision-making systems are now widely integrated in high-stakes decision-making processes, such as in healthcare \cite{MQ2017} and criminal prediction \cite{JJSL2016},
fair machine learning has grown rapidly over the last few years into a foundational area of trustworthy AI.
A main task in fair machine learning is to design efficient algorithms satisfying fairness constraints with a small sacrifice in model accuracy.
This field has made substantial progress in recent years, as many effective approaches have been proposed to mitigate algorithmic bias \cite{ZWKT2013,CKYMR2016,CFDV2017,XWYZW2019,LV2019,CJG2019,DETR2018,CMJW2019,JL2019,CHS2020,ZDC2022}.

An important fundamental benchmark for fair classification is provided by fair Bayes-optimal classifiers, which maximize accuracy subject to fairness  \cite{MW2018,ZDC2022}.
A representative class of classifiers is group-wise thresholding rules (GWTRs) over the feature-conditional probabilities of the target label, for each protected group (e.g., probability of repaying a loan given income).
Intuitively, being a GWTR is a minimal requirement for within-group fairness, as it ensures that the most qualified individuals are selected in every group.
 \cite{CSFG2017,MW2018,CCH02019,I2020,SC2021,ZDC2022} have studied fair Bayes-optimal classifiers  under various fairness constraints and proved that,
for many  fairness metrics, the optimal fair classifiers are GWTRs. Moreover, the associated thresholds can be learned efficiently \cite{MW2018,ZDC2022}.

Current literature on Bayes-optimality focuses mainly on the independence- and separation-based fairness measures (e.g., demographic parity, equality of opportunity, equalized odds; see Section \ref{fm} for definitions and a review).
However, sufficiency-based measures such as predictive parity are less commonly considered, possibly due to the complexity of their constraints.
Sufficiency-based measures are often applied to assess recidivism prediction instruments \cite{FBC2016,DMB2016,C2017fair}.
\cite{LSMH2019} shows that a particular sufficiency-based measure, group calibration,
is implicitly favored by unconstrained optimization:
calibration error is bounded by the excess risk over the unconstrained Bayes-optimal classifier.
For selective classification, \cite{LBRSP2021} finds that sufficiency-based representation learning leads to fairness.
Despite these findings, little is known about (1) what the optimal fair classifiers under sufficiency-based measures are, and (2) how to learn them efficiently.
In this paper, we aim to answer these two questions by focusing on predictive parity, which requires that the positive predictive value (probability of a successful outcome given a positive prediction) be equalized among protected groups.
For example, in credit lending, for example,  predictive parity requires that, for individuals who receive the loans, the repayment rates are the same in different protected groups.

We study fair Bayes-optimal classifiers under predictive parity.
Perhaps surprisingly, our theoretical results reveal that  the  \emph{optimal fair classifiers are often, but not always group-wise thresholding rules}, depending on the data distribution.
We identify a sufficient condition under which all fair Bayes-optimal classifier are GWTRs.
Without this condition,
we show that fair Bayes-optimal classifiers may not be a GWTR when the minority group is more qualified than the majority group.
In these cases, predictive parity may have limitations as a fairness measure, as it can lead to within-group unfairness for the minority group.
Our findings are a reminder that the improper use of fairness measures may result in severe unintended consequences.
Careful analysis before applying fairness measures is necessary.

We then develop an algorithm, FairBayes-DPP, aiming for predictive parity.
Our method is a three-stage plug-in method.
In the first step, we use standard learning algorithms to estimate the group-wise conditional probabilities of the labels.
In the second step, we check our sufficient condition. If the sufficient condition holds, in the third step
we apply
a plug-in method
for estimating the optimal thresholds under fairness for each protected group.

We summarize our contributions as follows.
\begin{itemize}
    \item We show that Bayes-optimal classifiers satisfying predictive parity may or may not be group-wise thresholding  rules (GWTRs), depending on the data distribution.

    \item We identify a sufficient condition under which all fair Bayes-optimal classifiers are GWTRs.
    We show that, when the sufficient condition is not satisfied, imposing predictive parity while maximizing accuracy may lead to within-group unfairness for the minority group.

    \item We propose the  FairBayes-DPP algorithm  for fair classification.
    We demonstrate that FairBayes-DPP  is computationally efficient, showing a solid performance in our experiments on a number of synthetic and standard empirical datasets.
\end{itemize}

\section{Related Literature}
\subsection{Fairness Measures}
\label{fm}

Various fairness metrics have been proposed to measure aspects of disparity in ML.
Group fairness \citep{CFM2009,DHPT2012,HPS2016} targets statistical parity across
 protected groups, while individual fairness \citep{JKMR2016,PKG2019,RBMF2020} aims to provide nondiscriminatory predictions
for similar individuals.
In general, group fairness measures can be categorized into three categories.

The first group consists of independence-based measures, which require independence between predictions and protected attributes; this includes demographic parity \cite{KC2012,ZWKT2013} and conditional statistical parity \cite{CSFG2017,I2020}. In  credit lending, independence means that the proportion of approved candidates is the same across different protected groups.
However, as discussed in \cite{HPS2016}, independence-based measures have limitations;
and applying them often leads to a substantial loss of accuracy.

The second group consists of separation-based measures,
which require conditional independence between predictions and protected attributes, given label information.
Typical examples in this group are equality of opportunity \cite{HPS2016,ZLM2018} and equalized odds \cite{HPS2016,ZVGGK2017}.
In  credit lending, separation-based measures require that the individuals  who will  pay back (or default on) their loan
have an equal probability of
getting the loan, despite their race or gender.
Compared to independence-based measures, separation-based measures take label information into account, allowing for perfect predictions that equal the label.
However, these measures can be hard to validate, as the label information is often unknown for some groups. For example, the repayment status is missing for individuals whose loan application is declined.

As a result, measuring predictive bias is more widely applicable.
This leads to the third class, sufficiency-based measures \cite{PMK2017,C2017fair,LSMH2019}, where the label is required to be conditionally independent of the protected attributes, given the prediction. In credit lending, this requires that among the approved applications, the proportion of individuals who pay back the loan is equal across different groups.
Unlike independence- and separation-based measures that are well studied with solid theoretical benchmarks and efficient algorithms, sufficiency-based measures are less commonly investigated.
A possible reason is that conditioning on the prediction
leads to a complex constraint, which is thus challenging to study and enforce algorithmically.

\subsection{Algorithms Aimed at Fairness}
Literature on algorithms for fairness has grown explosively over the past decade.
Existing algorithms for fairness can be categorized broadly into three categories.
The first category is pre-processing algorithms aiming to remove biases from the training data.
Examples include transformations \citep{FFMS2015,KJ2016,CFDV2017,JL2019}, fair representation learning \citep{ZWKT2013,CKYMR2016,DETR2018,CMJW2019} and fair data generation \citep{XYZ2018,SHC2019,XYfairplus,RKSR2021}.
The second group is
in-processing algorithms, which handle fairness constraints during the training process.
Two common strategies are penalized optimization \citep{GCAM2016,NH2018,CJG2019,CHS2020}  and adversarial training \citep{ZLM2018,CFC2018,XWYZW2019,LV2019}.
The former incorporates fairness measures as a regularization term into the optimization objective, while the latter tries to minimize
the predictive ability of the model with respect to
the protected attribute.

The third group is post-processing algorithms, aiming to remove disparities from the model output.
The most common post-processing algorithm is the thresholding method \citep{BJA2016,MW2018,I2020,SC2021,ZDC2022}, adjusting thresholds for every protected group to achieve fairness.  In this paper, we propose a post-processing algorithm, FairBayes-DPP, to estimate the fair Bayes-optimal classifier under predictive parity.

\section{Problem Formulation and Notations}\label{Pre_and _Not}
We consider
classification problems where two types of feature are observed: the usual feature $X\in\mathcal{X}$, and the  protected feature $A\in\mathcal{A}$.
For example, in loan applications, $X$ may refer to common features such as
 education level and income, and $A$ may correspond to the race or gender of a candidate.
As multiclass protected attributes are often encountered in practice, we allow $\mathcal{A}$ to have any number $K\ge1$ of classes, and let $\mathcal{A}=\{1,2,...,K\}$.
We denote by $Y$ the ground truth label.
In credit lending, $Y$  may correspond to the status of repayment or defaulting on a loan.
The output $\widehat{Y}$ of the classifier aims to predict $Y$ based on observed features $X,A$.
We consider randomized classifiers defined as follows:
\begin{definition}[Randomized classifier]
  A randomized classifier is a measurable function\footnote{We assume that, whenever needed, the sets considered are endowed with appropriate sigma-algebras, and all functions considered are measurable with respect to the appropriate sigma-algebras.}
  $f:\mathcal{X}\times\mathcal{A} \to [0,1]$, indicating the probability of predicting $\widehat{Y}=1$ when observing $X=x$ and $A=a$. We denote by $\widehat{Y}_f=\widehat{Y}_f(x)$ the prediction induced by the classifier $f$.
 \end{definition}
Group-wise thresholding rules (GWT rules/classifiers or GWTRs) over conditional probabilities are of special importance.
Consider an appropriate sigma-finite measure $\mu$ on $\mathcal{X}$ (such as the Lebesgue measure for measurable subsets of $\mathbb{R}^d$, $d\ge 1$, or the uniform measure for finite sets), and suppose that
for all $a\in\mathcal{A}$ and $y\in \mathcal{Y}$,
the features $X$ have a conditional distribution $P_{X|a,y}$
given $A=a,Y=y$
with a density $dP_{X|a,y}$
with respect to $\mu$.
For all\footnote{To be precise, this conditional density is defined for $\mu$-almost every $x\in\mathcal{X}$; however for simplicity we say for all $x\in\mathcal{X}$. We use this convention without further mentioning through the paper.}
$x\in\mathcal{X}$
and $a\in\mathcal{A}$, let $\eta_a(x)=P(Y=1|X=x,A=a)$.
 \begin{definition}[GWT rule/classifier]
  A classifier $f$ is a GWTR if there are constants $t_a$, $a\in\mathcal{A}$, and functions $\tau_a:\mathcal{X}\to[0,1]$, $a\in\mathcal{A}$,  such that for all $x\in\mathcal{X}$ and $a\in\mathcal{A}$
  \begin{equation}\label{gwtr}
      f(x,a)=I(\eta_a(x)>t_a)+\tau_a(x) I(\eta_a(x)=t_a),
  \end{equation}
 where $I(\cdot)$ is the indicator function.
 \end{definition}

Clearly, GWTRs choose individuals with the highest conditional probability in each group.
This property is a minimal requirement for within-group fairness.
For example, a GWT recruitment tool ensures that the most qualified candidates are approved in every protected group.

We consider predictive parity, which aims to ensure the same positive predictive value among protected groups:
  \begin{definition}[Predictive Parity]
  A classifier $f$ satisfies predictive parity if for all $a\in\mathcal{A}$,
   $$P(Y=1 |\widehat{Y}_f  = 1,A = a) =P(Y=1|\widehat{Y}_f  = 1).$$
  \end{definition}
We follow \cite{CHS2020, ZDC2022} to use the difference between positive predictive values to measure the degree of unfairness, defining the Difference in Predictive Parities (DPP) of a classifier $f$ as
$$\text{DPP}(f)=\sum_{a\in\mathcal{A}}|P(Y=1 |\widehat{Y}_f  = 1,A = a) -P(Y=1|\widehat{Y}_f  = 1)|.$$

\section{Fair Bayes-optimal Classifiers under Predictive Parity}
Since predictive parity is commonly considered in scenarios where false positives are particularly harmful \cite{LBRSP2021},
we study cost-sensitive  classification.
For
a cost parameter $c\in[0,1]$, the cost-sensitive 0-1 risk\footnote{When $c=1/2$, cost-sensitive risk reduces to the usual zero-one risk.} of the classifier $f$ is defined as
$$R_c(f)=c\cdot P(\widehat{Y}_f=1,Y=0)+(1-c)\cdot P(\widehat{Y}_f=0, Y=1).$$
An unconstrained Bayes-optimal classifier for the cost-sensitive risk is any minimizer $f^\star\in \text{argmin}_f R_c(f).$
A classical result is that all Bayes-optimal classifiers have the form
$f^\star(x,a)=I(\eta_a(x)>c)+\tau I(\eta_a(x)=c)$, where $\tau\in[0,1]$ is arbitrary \cite{C2001CS, MW2018}.
Taking  predictive parity into account, a fair Bayes-optimal  classifier is any  minimizer of the cost-sensitive risk among  fair classifiers:
\begin{equation}\label{bao}
    f_{PPV}^\star\in \underset{f: \text{DPP}(f)=0}{\text{argmin}} R_c(f).
\end{equation}

\subsection{GWT Fair Bayes-Optimal Classifiers under Predictive Parity}
We first  identify a sufficient condition under which  all fair Bayes-optimal classifier under predictive parity are GWTRs.

\begin{condition}[Sufficient condition for Bayes-optimal classifiers to be GWTRs]\label{suff-con}
\begin{equation*}
\underset{a\in\mathcal{A}}{\min}\,
P(Y=1|\,\eta_a(X)\geq c,A=a)
\geq\underset{a\in\mathcal{A}}{\max}\, P({Y=1}|A=a). \end{equation*}
\end{condition}
The sufficient condition \ref{suff-con} requires that the minimal group-wise positive predictive value
$P(Y=1|\,\eta_a(X)\geq c,A=a)$
of the unconstrained Bayes-optimal classifier  is lower bounded by the maximal proportion of positive labels $P({Y=1|A=a})$ among groups.
In other words, the  performances of different groups vary only moderately:
the average performance of the most qualified class of each group---the points with $x$ such that $\eta_a(x)\geq c$---should be better than the overall performance $P({Y=1|A=a})$ of any of the other groups.
Condition \ref{suff-con} holds if
$P({Y=1|A=a})\leq c$ for all $a\in\mathcal{A}$,
because $P(Y=1|\,\eta_a(X)\geq c,A=a)\geq c$.

This condition is particularly applicable in settings where $c$ is large, such as in credit lending, where false positives are more societally harmful than false negatives.
They are also relevant if $P({Y=1|A=a})$, $a\in\mathcal{A}$ are small,
such as in online advertising where the probability of clicks is small.
Under this condition, we present our main result.

\begin{theorem}[Main result]\label{thm-GWTR}
Consider the cost-sensitive $0$-$1$ risk with cost parameter $c$. If
Condition \ref{suff-con} holds,
then all fair Bayes-optimal classifiers under predictive parity are GWTRs.
Thus, for all $f_{PPV}^\star$ from \eqref{bao},
there are $(t_a)_{a=1}^{|\mathcal{A}|} \in [0,1]^{|\mathcal{A}|}$ and functions $\tau_a(x):\mathcal{X}\to[0,1]$, $a\in\mathcal{A}$,
such that \eqref{gwtr} holds.

\end{theorem}

Unlike for demographic parity or for equality of opportunity,
where the fairness constraint is linear with respect to the probability predictions of the classifier $f$ \cite{MW2018}, the DPP constraint is non-linear with respect to $f$.
As a consequence, previously used theoretical tools such as the Neyman-Pearson argument from hypothesis testing \cite{ZDC2022} are no longer valid in this case.
Instead, we prove the result using a novel constructive argument.
When Condition \ref{suff-con} is satisfied,
for any classifier satisfying predictive parity, which is not a GWTR, we construct a GWTR that satisfies predictive parity and achieves a smaller classification error.
As a result, under Condition \ref{suff-con}, all fair Bayes-optimal classifiers are GWTRs.

Overall, the proof of Theorem \ref{thm-GWTR} is quite involved, and requires a lot of careful casework and analysis.
The proof rests on three novel lemmas, Lemmas \ref{lem1}, \ref{lem2}, and \ref{lem3},  which establish some fundamental properties of the positive predictive value of group-wise thresholding rules; such as monotonicity properties with respect to the thresholding parameter.
These tools may be valuable in future work.

\subsection{Fair Bayes-optimal Classifiers under Predictive Parity do not Need to be Thresholding Rules}
Next, we consider the case when the sufficient condition \ref{suff-con} does not hold.
For simplicity, we consider a binary protected attribute $a\in\{0,1\}$ with
\begin{equation}\label{unsuff-con}
{P(Y=1|\,\eta_a(x)\geq c,A=1)}<P(Y=1|A=0). \end{equation}

Our result shows that, under condition \eqref{unsuff-con}, there exist class probabilities $p_a$, $a\in\mathcal{A}$, such that no Bayes-optimal classifier under predictive parity is a GWTR.
\begin{theorem}\label{thm-imGWT}
Suppose that condition \eqref{unsuff-con} holds.
Denote $t_1=\inf\{t: P(Y=1|\,\eta_1(X)\geq t,A=1)>P({Y=1|A=0})\}$. Suppose there exist $\delta_1,\delta_2>0$ such that $P(c+\delta_1<\eta_A(X)<t_1|A=1)=\delta_2>0$.
Then, for all $p_1>2/(2+\delta_1\delta_2)$, no fair Bayes-optimal classifier under predictive parity is a GWTR.

\end{theorem}

The condition involving the constants $\delta_1,\delta_2>0$ ensures that $\eta_1(X)$ has positive probability to be strictly larger than $c$, which is a technical condition needed in the proof.
Theorem \ref{thm-imGWT} shows that predictive parity may lead to within-group unfairness, whereby the most qualified individuals are predicted to be unqualified, for a better overall accuracy.
By definition, predictive parity requires that the qualifications of selected individuals are similar across the protected groups. Suppose there exists a highly qualified minority group in which most individuals are qualified.
Selecting the most qualified individuals in this group leads to a very high standard.
As a result, many qualified individuals in other majority groups may be predicted to be unqualified using this standard,
leading to accuracy loss.
Conversely, if we select less qualified individuals in the highly qualified group, the lower standard allows more qualified individuals from the other groups to be selected, and increases accuracy.

\section{FairBayes-DPP: Adaptive Thresholding for Fair Bayes-optimality}\label{sec-alg}
In this section, we propose the FairBayes-DPP algorithm (Algorithm \ref{alg:pre-par}) for fair Bayes-optimal classification under predictive parity.
As mentioned, the DPP constraint is non-linear with respect to the classifier $f$, and is also highly non-convex with respect to the model parameters, even if both the classifier $f$  and the risk function are convex with respect to these parameters.
In such cases,
incorporating fairness constraints as a penalty in the training objective may be hard due to potential harmful local minima.
Therefore, we consider a different approach, developing a new three-step plug-in method based on Theorem \ref{thm-GWTR}.
Suppose we observe data points $(x_i,a_i,y_i)_{i=1}^n$ drawn independently and identically from a distribution $\mathcal{D}$ over the domain
$\mathcal{X} \times \mathcal{A} \times \mathcal{Y}$.

\textbf{Step 1.}
In the first step, we apply standard machine learning algorithms to learn the feature- and group-conditional label probabilities $\eta$ based on the whole dataset.
Consider  a loss function $L(\cdot, \cdot)$ and the function class $\mathcal{F}=\{f_\theta: \theta\in\Theta \}$ parametrized by $\theta$.
The estimator of $\eta$ is obtained by minimizing the empirical risk, $\widehat\eta_a(x):=f_{\widehat\theta}(x,a)$, where
\begin{align}\label{ht}
    \widehat{\theta}&\in \underset{\theta\in\Theta}{\text{argmin}}\frac1{n}\sum_{i=1}^nL(y_{i},f_{\theta}(x_{i},a_i)).
\end{align}
Here we use the cross-entropy loss, as minimizing the empirical 0-1 risk is generally not tractable.
At the population level,
the minimizers of the risks induced by the 0-1 and cross-entropy losses are both the
true conditional probability function \citep{miller1993loss}.
\begin{algorithm}[tb]
   \caption{FairBayes-DPP}
   \label{alg:pre-par}
\begin{algorithmic}
   \STATE {\bfseries Input:}  Datasets $S=\cup_{a=1}^{|\mathcal{A}|}S_a$ with $S=\{x_{i},a_i,y_{i}\}_{i=1}^{n}$ and $S_a=\{x^{(a)}_{j},y^{(a)}_{j}\}_{j=1}^{n_a}$. Cost parameter $c\in[0,1]$.

   \STATE {\textbf{Step 1}:} Estimate $\eta_a(x)$ by $\widehat\eta = f_{\widehat\theta}$, with $\widehat\theta$ from \eqref{ht}

           \STATE {\textbf{Step 2}:} Check sufficient condition \ref{suff-con}.
   \STATE  Define, for all $t$,\qquad
 $\widehat{\text{PPV}}_{a}(t)=\frac{{\sum}_{j=1}^{n_a} I(y^{(a)}_j=1,\widehat{\eta}_{a}(x^{(a)}_j)\geq t)}{{\sum}_{j=1}^{n_a}I(\widehat{\eta}_{a}(x^{(a)}_j)\geq t)}$, \qquad $\widehat{P}(Y=1|A=a)=\frac{1}{n_a}\sum\limits_{i=1}^{n_a}y^{(a)}_j$.

  \IF{$\min_a\widehat{\text{PPV}}_{a}(c)< \max_a\widehat{P}(Y=1|A=a)$}
  \STATE {We recommend considering other fairness measures.}
  \ELSE
         \STATE {\textbf{Step 3}:} Find the optimal thresholds.
  Let {$t_{\min} = \min\{t:
 \widehat{\text{PPV}}_{1}(t)\ge \max_a\widehat{P}(Y=1|A=a)
  \}.$}
  \FOR{$t \in \mathcal{T}=[t_{\min}, \max_j\widehat\eta_1(x^{(1)}_{j})]$}

    \FOR{$a\in\mathcal{A} \setminus\{1\}$}
    \STATE Find $\widehat{t}_a(t)$ such that   {$\widehat{\text{PPV}}_{a}(\widehat{t}_a(t))\approx\widehat{\text{PPV}}_1(t).$}
    \ENDFOR
    \STATE Let $
\widehat{f}(x,a,t)
=\tilde{f}\left(x,a;\widehat t_1(t),\widehat t_2(t),...,\widehat t_{|\mathcal{A}|}(t)\right)
=I\left(\widehat\eta_{a}(x)\geq \widehat t_a(t)\right).$
\STATE Let $R_c(t)=\frac1n\sum_{i=1}^n c^{(1-y_i)}(1-c^{y_i})I(y_i\neq \widehat{f}(x_i,a_i,t)).
$
    \ENDFOR
    \STATE Find $\widehat{t}=\underset{t\in \mathcal{T}_n}{\text{argmin}}R_c(t).$

\STATE {\bfseries Output:}
$\widehat{f}_{PP}(x,a)=I(\widehat\eta_{a}(x)\geq\widehat{t}_a(\widehat{t}))$
    \ENDIF
    \end{algorithmic}
\end{algorithm}

\textbf{Step 2.}
In the second step, we check the empirical version of Condition \ref{suff-con} for the classifier derived in the first step.
To be more specific, we divide the data into $|\mathcal{A}|$ parts,
according to the value of $A$: for $a\in\mathcal{A}$,
$S_a=\{x^{(a)}_{j},y^{(a)}_{j}\}_{j=1}^{n_a}$, where $a^{(a)}_{j}=a$.
Let, for all $t$ for which it is defined, $$\widehat{\text{PPV}}_{a}(t)=\frac{{\sum}_{j=1}^{n_a} I(y^{(a)}_j=1,\widehat{\eta}_{a}(x^{(a)}_j)\geq t)}{{\sum}_{j=1}^{n_a}I(\widehat{\eta}_{a}(x^{(a)}_j)\geq t)} \qquad \text{ and } \qquad \widehat{P}(Y=1|A=a)=\frac{1}{n_a}\sum\limits_{i=1}^{n_a}y^{(a)}_j.$$
We only divide by nonzero quantities here and below.
To ensure that the quantities we divide by are nonzero, we restrict to  $t_a\in[0,\max_j(\widehat\eta_a(x^{(a)}_{j}))]$ when evaluating $\widehat{\text{PPV}}_{a}(t_a)$.
We check whether $\min_{a}\, \widehat{\text{PPV}}_{a}(c)\geq\max_a\, \widehat{P}(Y=1|A=a) $.\footnote{One could modify this to allow some slack; and perform a formal statistical hypothesis test of our sufficient condition.}
If this is not satisfied, we recommend considering other fairness measures, as predictive parity may not be appropriate in this case, see the discussion after Theorem \ref{thm-imGWT}.
 If it is satisfied,
 we then move to step 3 to adjust the thresholds of the classifier aiming for predictive parity.

\textbf{Step 3.} In the last step, we find the optimal thresholds under fairness.
Based on Theorem~\ref{thm-GWTR}, we consider the following  deterministic classifiers:
\begin{equation}\label{classifier1}
\tilde{f}(x,a;t_1,t_2,...,t_{|\mathcal{A}|})=I\left(\widehat\eta_{a}(x)\geq t_a\right),
\end{equation}
where $\widehat{\eta}$ is the estimate of $\eta$ from the first step, and $t_a$, $a\in\mathcal{A}$, are parameters to learn.

We use the following strategy to estimate $t_a$, $a\in\mathcal{A}$: First, we fix the threshold for the group with $a=1$, say $t$.
The positive predictive value for this group
can then be estimated by $\widehat{\text{PPV}}_{1}(t)$.
To achieve predictive parity, we need to find thresholds for the other groups such that the positive group-wise predictive values are the same\footnote{Since a sample mean $n^{-1}\sum_{i=1}^n Z_i$ of iid random variables $Z_i$ has a variability of order $O_P(n^{-1/2})$, even if the true predictive parities are equal, the empirical versions may differ by $O_P(n^{-1/2})$. However, in our case we simply find the values $t_a,t$ for which they are as close as possible.}, i.e., find $t_a$, $a=2,3,\ldots,|\mathcal{A}|$, such that
\begin{equation}\label{thresh-estimate}
\widehat{\text{PPV}}_{a}(t_a)
\approx
\widehat{\text{PPV}}_{1}(t)
, \ \ \ \text{ for } a = 2,3,...,|\mathcal{A}|.
\end{equation}
As proved in Lemma \ref{lem1}, the positive predictive value for each group in the population is non-decreasing with the respective threshold $t_a$.
As a consequence, we can search over
$t_a$, $a=2,3,\ldots,|\mathcal{A}|$,
efficiently  via, for instance, the bisection method.\footnote{The empirical PPV is only approximately monotonic, but this does not cause problems.}
Correspondingly, we consider the following range of $t$: $\mathcal{T}=[t_{\min},\max_j \eta_1(x^{(1)}_{j})]$ with
$$t_{\min} = \min\left\{t:
\widehat{\text{PPV}}_{1}(t)\ge \max_a\widehat{P}(Y=1|A=a)
\right\}.$$

We denote by $\widehat t_a(t)$, $a=2,3,\ldots,|\mathcal{A}|$, the estimated thresholds given by \eqref{thresh-estimate}, writing $\widehat t_1(t)=t$ for convenience.
We consider the classifier \eqref{classifier1} with these thresholds:
\begin{equation*
\widehat{f}(x,a,t)
=\tilde{f}\left(x,a;\widehat t_1(t),\widehat t_2(t),...,\widehat t_{|\mathcal{A}|}(t)\right)
=I\left(\widehat\eta_{a}(x)\geq \widehat t_a(t)\right).
\end{equation*}
Finally, we find $t$ that minimizes the cost-sensitive risk on the training data by searching over a grid $\mathcal{T}_n$ within $\mathcal{T}$:
$
\widehat{t}=\underset{t\in \mathcal{T}_n}{\text{argmin}}\left\{\frac1n\sum_{i=1}^n c^{(1-y_i)}(1-c^{y_i})I(y_i\neq \widehat{f}(x_i,a_i,t))\right\}.
$$
Our final estimator of the fair Bayes-optimal classifier is $\widehat{f}_{PP} = \widehat f_{\widehat t}$.
The FairBayes-DPP algorithm is related to the algorithms proposed for other fairness measures in  \cite{ZDC2022}, where a binary protected attribute is considered and closed-form optimal thresholds are derived.
In contrast, FairBayes-DPP can handle multi-class protected attributes and does not rely on closed-form thresholds.
Similar to the methods from \cite{ZDC2022}, our algorithm enforces fairness
only in the fast second step, where no gradient-based technique is applied.
Thus, it is computationally efficient and the non-convexity of fairness constraint is no longer problematic.
Our experimental results demonstrate that our method removes disparities and preserves accuracy.

\section{Experiments}

\begin{table
\caption{Classification accuracy and DPP of the true fair Bayes-optimal classifier and our estimator trained via logistic regression on a synthetic data example. See Section \ref{synth} for details.}
\label{table_synth}
\vspace{-0.2cm}
\begin{center}
\setlength{\tabcolsep}{5.7pt}
\renewcommand{\arraystretch}{0.95}
\begin{small}
\begin{sc}
\begin{tabular}{cc|cc|cc|cc}
\hline
\multicolumn{4}{c|}{Theoretical Value}  & \multicolumn{4}{c}{Logistic regression} \\\hline
\multicolumn{2}{c|}{Fair}  &\multicolumn{2}{c|}{Unconstrained}  &\multicolumn{2}{c|}{FairBayes-DPP}  &\multicolumn{2}{c}{Unconstrained}   \\\hline
  $p$ & ACC &DPP& ACC & DPP& $\widehat{\text{ACC}}$&$\widehat{\text{DPP}}$& $\widehat{\text{ACC}}$ \\\hline
0.2 & 0.814 & 0.000 & 0.814 & 0.049\,(0.036) & 0.813\,(0.005) & 0.046\,(0.037) & 0.813\,(0.005)\\
0.3 & 0.794 & 0.024 & 0.794 & 0.037\,(0.029) & 0.794\,(0.006) & 0.040\,(0.033) & 0.794\,(0.005)\\
0.4 & 0.781 & 0.050 & 0.781 & 0.035\,(0.029) & 0.781\,(0.006) & 0.054\,(0.029) & 0.782\,(0.005)\\
0.5 & 0.775 & 0.078 & 0.777 & 0.042\,(0.032) & 0.775\,(0.006) & 0.081\,(0.036) & 0.777\,(0.006)\\
0.6 & 0.778 & 0.113 & 0.781 & 0.038\,(0.031) & 0.778\,(0.006) & 0.113\,(0.037) & 0.781\,(0.006)\\\hline
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vspace{-0.4cm}
\end{table}
\subsection{Synthetic Data}
\label{synth}
We first study a synthetic dataset to compare our method with the true Bayes-optimal fair classifier derived analytically using the true data distribution.

\textbf{Statistical model.}
Let $X=(X_1,X_2)\in \mathbb{R}^2$ be a generic feature, $A\in\{0,1\}$ be the protected attribute and $Y\in\{0,1\}$ be the label.
We generate $A$ and $Y$ according to the probabilities $P(A=1)$, $P(Y=1|A=1)$ and $P(Y=1|A=0)$, specified below.
Conditional on $A=a$ and $Y=y$, $X$ is generated from a bivariate
Gaussian distribution $N((2a-1,2y-1)^\top,2^2I_2)$, where $I_p$ is the $p$-dimensional identity covariance matrix.
In this model,  $\eta_a(x)$ has a closed form, and we use it to find the true fair Bayes-optimal classifier numerically under the Condition \ref{suff-con}. More details about this synthetic model can be found in Section \ref{appendix-synth}.

 \textbf{Experimental setting.}
 We randomly sample $50,000$ training data points  and $5,000$ test data points.
 In the Gaussian case, the Bayes-optimal classifier is linear in $x$
and thus we employ logistic regression  to learn $\eta_1(\cdot)$ and $\eta_0(\cdot)$.
 We then
 search over a grid with spacings equal to $0.001$ over the range we identified in Section \ref{sec-alg}
for the empirically optimal thresholds under fairness.
 We denote  $\widehat{f}$ and $\widehat{f}_{PPV}$ the estimators of the unconstrained and fair Bayes-optimal classifiers, respectively.

We first evaluate the FairBayes-DPP algorithm under the  Condition \ref{suff-con}. We set the cost parameter $c=0.5$, while $P(A=1)=0.3$ and $P({Y=1|A=0})=0.2$.
It can be calculated that $P(Y=1|\,\eta_0(X)>0.5,A=0)\approx 0.613$, using \eqref{suff-gaussian} in the appendix.
To consider settings with varied levels of fairness in the population,
we vary $p=P({Y=1|A=1})$ from $0.2$ to $0.6$, with the DPP of unconstrained Bayes-optimal classifier grows from $0$ to $0.113$.

Table \ref{table_synth} presents the classification accuracy and DPP of the true fair Bayes-optimal classifier and FairBayes-DPP trained via logistic regression over 100 simulations\footnote{Here, the randomness of the experiment is due to the random generation of the synthetic data.}.
Our first observation is that, under predictive parity, the accuracy of the true unconstrained and fair Bayes-optimal classifiers is almost identical, indicating  that predictive parity under Condition \ref{suff-con} requires a very small loss of accuracy.
This finding is consistent with the results in \cite{LSMH2019} that sufficiency-based measures are favored by unconstrained learning.

Second, our FairBayes-DPP method  closely tracks the behavior of the fair Bayes-optimal classifier, controlling the accuracy metric ACC and unfairness metric DPP on the test data effectively.
When $|P({Y=1|A=1})-P({Y=1|A=0})|$ is small, FairBayes-DPP  performs similarly to the unconstrained classifier.
However, when the data is biased against protected groups and $|P({Y=1|A=1})-P({Y=1|A=0})|$ is large,
FairBayes-DPP  mitigates the disparity of the unconstrained classifier effectively, while preserving model accuracy. We further conduct extensive simulations to evaluate  the FairBayes-DPP algorithm with different model and training setups, as shown in the appendix. In particular, we also consider the  multi-class protected attribute case.

\subsection{Empirical Data Analysis}
{\bf Dataset.} We test FairBayes-DPP on two  benchmark  datasets for fair classification: ``Adult'' \cite{Dua2019} and ``COMPAS'' \cite{JJSL2016}.
For each dataset, we randomly sample (with replacement) 70\%, 50\% and 30\% as the training, validation and test set, respectively.
To further test the performance of our algorithm on a large-scale dataset, we conduct experiments on the CelebFaces Attributes (CelebA) Dataset \cite{CelebAdata}.

\begin{compactitem}
\item {\it Adult:} The target variable $Y$ is whether the income of an individual is more than \$50,000.  Age, marriage status, education level and other related variables are included in $X$, and the protected attribute $A$ refers to gender.

\item {\it COMPAS:} In the COMPAS dataset, the target is to predict recidivism. Here $Y$ indicates whether or not a criminal will reoffend, while $X$ includes  prior criminal records, age and an indicator of misdemeanor.
The protected attribute $A$  is the race of an individual,``white-vs-non-white''.

\item {\it CelebA:} CelebA dataset is a large-scale dataset with more than 200,000 face images,
each with 40 attributes (including protected attribute ``gender'' and other 39 different attributes for prediction tasks).
Our goal is to predict the face attributes $Y$ based on the images $X$ and remove bias with respect to gender  $A$ from the output.
\end{compactitem}

\begin{figure}[t]
    \centering
    \includegraphics[scale=0.36]{both}
        \vspace{-0.2cm}
    \caption{Accuracy and difference in predictive parity on the Adult and  COMPAS datasets.}
    \vspace{-0.3cm}
    \label{fig-ad_co}
\end{figure}

 \textbf{Experimental setting.}
 As algorithms for predictive parity are rarely considered in the literature, we use unconstrained learning as a baseline for our experiments.
 For the ``Adult'' and ``COMPAS'' datasets, we adopt the same training setting as in \cite{CHS2020, ZDC2022}. The conditional probabilities are learned via a three-layer fully connected neural network architecture with 32 hidden neurons per layer.
 For  ``CelebA'', we apply the training setting from \cite{WQK2020}. We learn the conditional probabilities by training a ResNet50 mode; \citep{HZRS15Res}, pretrained on ImageNet \cite{DDSLKL2009}. For all the datasets,
Over the course of training the model on
the training set, we select the one with best performance on the validation set.
In addition, we learn the optimal thresholds over the validation set to avoid overfitting.
All experiments use PyTorch. We refer
readers to the Appendix for more training details, including optimizer, learning rates, batch sizes and training epochs.
We repeat the experiment 100 times for the Adult and  COMPAS datasets and five times for the CelebA dataset.\footnote{For the Adult and  COMPAS datasets, the randomness of the experiment comes from the random selection of the training, validation and test data, as well as the
stochasticity of the batch selection in the optimization algorithm.
For the CelebA dataset, the randomness is caused by the stochasticity of the optimization method.}

Figure \ref{fig-ad_co} presents the average performances of FairBayes-DPP and unconstrained learning on the Adult and  COMPAS datasets.
Our method achieves almost the same accuracy as the unconstrained classifier, and has a smaller disparity.
To better compare our fair classifier with the unconstrained one, we  use the paired $t$-test to compare the DPP of the proposed algorithm ($\text{DPP}_{Fair}$) and of unconstrained learning ($\text{DPP}_{Base}$).
We consider the following one sided test:
$$\mathcal{H}_0: \text{DPP}_{fair}=\text{DPP}_{Base} \ \ \ \text{ v.s. }  \ \ \ \mathcal{H}_1:\text{DPP}_{fair}<\text{DPP}_{Base} .$$
The $p$-values of the tests are $3.90\times 10^{-4}$ for the Adult dataset and $3.09\times 10^{-8}$
for the COMPAS dataset.
In both cases, these results provide evidence
that our  FairBayes-DPP method  achieves a smaller disparity than unconstrained learning.

Finally, we test FairBayes-DPP  on the CelebA dataset,
Here, we only consider 27 attributes\footnote{Among the 39 attributes,  12 are heavily skewed  with $ \min(P(Y=1|M),P(Y=1|F))<0.01$ or $\max(P(Y=1|M),P(Y=1|F))>0.99$ (where $M$ represents Male and $F$ represents Female) in the training, validation or test set. They are:
 ``5 o'Clock Shadow'', ``Bald'', ``Double Chin'', ``Goatee'',  ``Gray Hair'', ``Heavy Makeup'', ``Mustache'', ``No Beard'', ``Rosy Cheeks'', ``Sideburns'', ``Wearing Lipstick'' and ``Wearing Necktie''.}
 with $0.01\leq P(Y=1|M),P(Y=1|F)\leq 0.99$ in the training, validation, and test sets; to ensure that the training, validation and test sample sizes are large enough for each subgroup.
We further identify one attribute, ``Young'', that violates  Condition \ref{suff-con}. We calculate the per-attribute accuracies and DPPs  on the test set. Table \ref{Table-celeba} presents the results of the first six attributes;  the  remaining results are in the appendix.
As we can see, even for the large-scale CelebA dataset with high dimensional image features, our algorithm mitigates the gender bias effectively, with almost no loss of accuracy.

\begin{table
    \caption{Per-attribute accuracy and DPP of the FairBayes-DPP algorithm and unconstrained optimization on the CelebA dataset.}
        \label{Table-celeba}
        \vspace{-0.2cm}
\begin{center}
\setlength{\tabcolsep}{4.8pt}
\renewcommand{\arraystretch}{0.98}
\begin{small}
\begin{sc}
    \begin{tabular}{l|cc|cc}\hline
 \multirow{2}[1]{*}{Attributes}           &      \multicolumn{2}{c|}{Per-attribute Accuracy}&      \multicolumn{2}{c}{Per-attribute DDP}\\\cline{2-5}
                      & FairBayes-DPP& Unconstrained & FairBayes-DPP& Unconstrained \\\hline
 Arched Eyebrows      & 0.838   & 0.838   & 0.028   & 0.105 \\
 Attractive           & 0.825   & 0.827   & 0.080   & 0.157 \\
 Bags Under Eyes      & 0.853   & 0.852   & 0.021   & 0.071 \\
 Bangs                & 0.959   & 0.958   & 0.012   & 0.081 \\
 Big Lips             & 0.706   & 0.718   & 0.026   & 0.123 \\
 Big Nose             & 0.845   & 0.845   & 0.076   & 0.130 \\\hline
  \end{tabular}
  \end{sc}
\end{small}
\end{center}
  \vspace{-0.5cm}
\end{table}

\section{Summary and Discussion}
In this paper, we investigated fair Bayes-optimal classifiers under predictive parity. We proved that when the overall performances of different protected groups vary only moderately, all fair Bayes-optimal classifiers under predictive parity are GWTRs. We further proposed a  post-processing algorithm to estimate the optimal GWTR. The derived post-processing algorithm removes the disparity in unconstrained classifiers effectively, while preserving a similar test accuracy.

However, when our sufficient condition is not satisfied, the fair Bayes-optimal classifier under predictive parity may lead to within-group unfairness for the minority group. In the current literature, many algorithms directly apply penalized/constrained optimization to impose fairness.
Our negative finding, however, is an important reminder  that careful analysis is required
before employing a fairness measure.
The improper use of a measure may result in severe unintended consequences.

\bibliographystyle{plain}


\section{Introduction}
\label{Intro}
Traditionally, neural architectures are manually designed by human experts: \textit{e}.\textit{g}. VGG, ResNet, and DenseNet.
Choosing proper neural architecture for a given dataset and task is important for getting high performance.
Recently, architectures selected by Neural Architecture Search (NAS) algorithms achieved state-of-the-art performances on various benchmark datasets.
Even though NAS methods show great performance on various tasks and datasets, their prohibitively high computational cost makes NAS methods hard to be applied practically.

To overcome this limitation, many recent works focused on reducing the computational costs of NAS while maintaining the advantage of NAS approaches.
Among them, several studies attempted to adapt given architectures for the given dataset and task rather than finding architectures within the vast search space.
Neural Architecture Transformer (NAT)~\cite{guo2019nat} is one of the representative works on network architecture adaptation.
The authors attempted to improve the given architecture so that the performance of the network is improved while maintaining or reducing the computational costs.
However, NAT still requires an architecture adaptation stage in addition to the conventional network weight training stage.
To make architecture adaptation effective and practical, we need to improve architecture during the network training stage.

Also, NAT has several other limitations.
First, the reproducibility of the algorithm is not verified since the authors reported only one result for each model.
Second, it can only transform the neural networks with identical cell architectures.
Recent NAS works focus on searching macroblock-based architectures that have various cell architectures.
However, those architectures cannot be transformed by NAT.

In this paper, we propose an architecture adaptation technique that doesn't require an additional architecture adaptation stage.
Since the proposed method improves architectures during the conventional train stage, it is \textit{proxyless} and can be easily combined with the existing deep neural network training process.
Especially, we examined the effectiveness of the proposed method not only for supervised learning but also self-supervised representation learning.

Our contributions are summarized as:
\begin{itemize}
    \item We propose a proxyless architecture adaptation algorithm that consecutively improves architecture and train the weights.
    \item We carried out extensive experiments on both supervised learning and self-supervised learning, and the results show consistent performance improvements.
    \item The proposed method overcomes the limitation of NAT such as poor reproducibility and limited types for the base architecture.
\end{itemize}

\begin{figure*}[t!]
\begin{center}
\centerline{\includegraphics[width=0.9\linewidth]{figures/DNAT_fig.pdf}}
\caption{An example of the network architecture adaptation by the proposed method. Until the training of the architecture parameters $\theta$ is finished, both $\omega$ and $\theta$ are trained. After the architecture train step, $\theta$ is fixed and only $\omega$ is trained until we get the final trained network.}
\vspace{-0.5cm}
\label{overall}
\end{center}
\end{figure*}

\section{Related Work}
\label{Related}
After the NAS is introduced by~\cite{zoph2016neural}, various kinds of NAS methods have been proposed; reinforcement learning (RL)-based methods~\cite{zoph2018learning, pham2018efficient, lee2020efficient}, evolutionary algorithm (EA)-based method~\cite{real2017large, real2018regularized}, gradient-based~\cite{liu2018darts, luo2018neural}, and others~\cite{brock2017smash}.
Recently, NAT~\cite{guo2019nat} proposed the architecture adaptation that optimizes given neural architecture and search space.
Unlike traditional NAS methods, NAT only changes the original operations into none or identity operations.
Although NAT showed impressive results in the paper, there are several limitations of the NAT as we claimed in Section 1.

The proposed method can be applied to not only supervised learning but also self-supervised representation learning.
Traditionally, self-supervised learning focuses on learning representations from unlabeled data and pre-defined handcrafted tasks\cite{noroozi2016unsupervised, komodakis2018unsupervised}.
Recently suggested contrastive learning enables learning representations without defining specific tasks.
Especially, SimCLR~\cite{chen2020simple} achieved remarkable performance on various benchmarks with the utilization of effective augmentations on contrastive loss.

\section{Methodology}
\label{Method}

The proposed method adapts the given neural architecture and improves the performance by using gradient-based optimization.
After the entire learning process, we directly get the trained network, and there is no need to train a new network from scratch.
There are two consecutive stages in the proposed method: the architecture train stage and the network train stage.
In the architecture train stage, both the architecture parameters and network parameters are trained.
After the architecture train stage, only network parameters are trained.
The overall processes of the proposed method for both supervised learning and self-supervised learning are shown in Figure~\ref{overall}.

\subsection{Differentiable architecture parameters}
To adapt the given neural architecture, we use differentiable architecture parameters and gradient-based learning.
The architecture parameters $\theta$ is defined in the network architecture graph.
Each edge in the network architecture graph contains original operation, identity operation, and none operation.
Computation of each edge is carried out based on the architecture parameters:
\begin{equation}
\label{arch_params}
    {o}_{e}(x)={\theta}_{e, none}\cdot Z + {\theta}_{e, id}\cdot x + {\theta}_{e, same}\cdot o(x),
\end{equation}
where $x$ means input, ${o}_{e}(x)$ means output of the edge, $Z$ means zero tensor, $o(x)$ means original operation of the edge, ${\theta}_{e, none}$ means the weight of the none operation of the edge, ${\theta}_{e, id}$ means the weight of the identity operation of the edge, and ${\theta}_{e, same}$ means the weight of the original operation of the edge.
We set initial ${\theta}_{none}$ and ${\theta}_{id}$ as zero, and ${\theta}_{same}$ as one.
Therefore, the initialized network works the same as the original architecture.

\subsection{Architecture train stage}
After the network is initialized, the architecture train stage begins to adapt the neural architecture for the given dataset and task.
In this stage, both the network weight parameters $\omega$ and the architecture parameters $\theta$ are trained alternately.
For every input mini-batches, $\omega$ is trained first, and $\theta$ is trained after the update of $\omega$.
Note that the proposed method doesn't require any separated dataset for architecture optimization, and the network can utilize a full dataset to train its weights $\omega$.
The architecture train stage is carried out for the pre-defined epochs.

When the architecture train stage is finished, architecture is transformed based on the trained $\theta$.
For each edge, the operation that has the highest weight in $\theta$ is selected to construct the final architecture.
In the example of Figure~\ref{overall}, two edges maintain the original operations, one edge changed its operation into identity, and one edge is removed because none operation is selected.

\subsection{Network train stage}
The architecture trained at the previous stage is fixed, and only $\omega$ of the network is trained in this stage.
This stage is the same as the traditional neural network training process, and it is continuously carried out after the architecture train stage.
At the end of this stage, we can get the trained network and use it to infer unseen input data or test the performance of the model.

\subsection{Supervised learning and self-supervised learning}
The proposed method can be applied to both supervised learning and self-supervised learning.
The objective of the proposed method can be formulated as:

\begin{equation}
    \min_{\theta} \mathcal{L}\big(w^*(\theta), \theta\big)
\label{eq:gradient_obj}
\end{equation}
\begin{equation}
    \text{s.t.}~~~w^*(\theta) = \argmin_{w} \mathcal{L}(w, \theta),
\label{eq:gradient_w_obj}
\end{equation}

where $\theta$ denotes the architecture parameter, $w$ is the weight of the network, $\mathcal{L}(\cdot)$ is the loss function.

In case of the supervised learning, we used the cross-entropy loss which uses data and labels to calculate the loss.
In self-supervised learning experiments, we utilized SimCLR~\cite{chen2020simple} objective which uses two different augmented views of images to calculate the loss.

\section{Experiments}
\label{Experiments}
We carried out extensive experiments to verify the performance and the reproducibility of comparison methods.
In the experiments, various models are trained on CIFAR-10 and Tiny Imagenet.

\subsection{Data and Experiment Setting}
\textbf{Supervised Learning.}  CIFAR-10 dataset consists of 50,000 train images and 10,000 test images with ten classes.
The size of images is $32\times32$, and images have RGB color channels.
Tiny Imagenet dataset has 100,000 train images and 10,000 test images with 200 classes.
The input size of Tiny Imagenet dataset is $64\times64$, and all images are RGB color images.

We experimented with various models on CIFAR-10 and Tiny Imagenet dataset.
These models include ResNet20, MobileNet V2, DARTS, and ProxylessNAS.
The former two models are manually designed, and the latter two models are NAS models.
To compare the performance of NAT and our algorithm, we trained the NAT controller on each dataset and then trained the transformed architecture inferred from the controller.
In the case of our algorithm, we test both cell-based transformation and full network transformation.
We used 0.025 learning rate, 600 epoch, and Stochastic Gradient Descent(SGD) optimizer as the same hyper-parameters to all models and methods.
Exceptionally, we applied 300 epochs to Mobilenet V2 and DARTS on Tiny Imagenet dataset, and utilized cut-out for NAS models such as DARTS and ProxylessNAS.

We tested five times with different random seeds for every experiment to get the right performance and verify the reproducibility of comparison algorithms.
Therefore, we report the average accuracy and standard deviation of each method and each model.
The total cost of NAT was calculated by adding GPU hours of the architecture transformation stage and network train stage, and the cost of our algorithms was computed by just measuring the cost of the whole training process.

\begin{table}[t]
\caption{Comparison of Average Accuracy, Standard Deviation and Total Cost between original, NAT and Ours on CIFAR-10.}
\label{tab_cifar10_result}
\vskip 0.05in
\begin{center}
\scalebox{0.8}{
\begin{tabular}{clccccc}
\toprule
& \multicolumn{1}{c}{}& \multicolumn{1}{c}{Avg Acc} & \multicolumn{1}{c}{Std} & \multicolumn{1}{c}{Total Cost}\\
Model & \multicolumn{1}{l}{Method} & \multicolumn{1}{c}{(\%)} & \multicolumn{1}{c}{(\%)}& \multicolumn{1}{c}{(GPU hours)}\\

\midrule
\multirow{4}{*}{Resnet20} & Original & 91.66 & 0.16 & 8\\
& NAT & 55.78 & 42.34 &  14\\
\cmidrule{2-5}
& Ours(Cell) & \textbf{93.29} & 0.11 & 11.2\\
& Ours(Full) & 93.12 & 0.12 & 8.7\\
\midrule
\multirow{4}{*}{\shortstack{Mobilenet \\ V2}}
& Original & 93.91 & 0.12 & 20.5\\
& NAT & 91.97 & 5.10 & 27.8 \\
\cmidrule{2-5}
& Ours(Cell) & \textbf{95.02} & 0.31 & 24.8\\
& Ours(Full) & 94.93 & 0.13 & 22.1\\
\midrule
\midrule
\multirow{4}{*}{DARTS} & Original & 96.75 & 0.11 & 38.3\\
& NAT & 96.95 & 0.09 & 47 \\
\cmidrule{2-5}
& Ours(Cell) & \textbf{96.97} & 0.15 & 45\\
& Ours(Full) & 96.82 & 0.13 & 41.1\\
\midrule
\multirow{3}{*}{\shortstack{Proxyless \\ NAS}} & Original & 94.19 & 1.08 & 15.3\\
& NAT & - & - & - \\
\cmidrule{2-5}
& Ours(Full) & \textbf{95.09} & 0.23 & 19.8\\
\bottomrule
\end{tabular}
}
\end{center}
\vskip -0.1in
\end{table}

\begin{table}[t]
\caption{Reproducibility of original, NAT and Ours with different random seeds on CIFAR-10.}
\label{tab_reproducibility}
\vskip 0.05in
\begin{center}
\scalebox{0.8}{
\begin{tabular}{clccccc}
\toprule
& \multicolumn{1}{c}{}& \multicolumn{5}{c}{Random Seed}\\
Model & \multicolumn{1}{l}{Method} & \multicolumn{1}{c}{(1)} & \multicolumn{1}{c}{(2)}& \multicolumn{1}{c}{(3)}& \multicolumn{1}{c}{(4)}& \multicolumn{1}{c}{(5)}\\

\midrule
\multirow{4}{*}{Resnet20} & Original & 91.74 & 91.74 & 91.65 & 91.76 & 91.39\\
& NAT & 10 & 75.14 & 91.05 & 10 & 92.68 \\
\cmidrule{2-7}
& Ours(Cell) & 93.21 & 93.34 & 93.4 & 93.15 & 93.37\\
& Ours(Full) & 93.07 & 93.26 & 93.22 & 93.06 & 92.97\\
\midrule
\multirow{4}{*}{\shortstack{Mobilenet \\ V2}}
& Original & 93.9 & 94.04 & 93.95 & 93.95 & 93.72\\
& NAT & 83.36 & 95.13 & 94.95 & 91.18 & 95.21 \\
\cmidrule{2-7}
& Ours(Cell) & 94.57 & 94.97 & 95.41 & 94.97 & 95.18\\
& Ours(Full) & 95.13 & 94.81 & 94.85 & 95 & 94.85\\
\bottomrule
\end{tabular}
}
\end{center}
\vskip -0.1in
\end{table}

\noindent\textbf{Self-Supervised Learning.} We conducted experiments with CIFAR-10 dataset to compare performances of original architectures and architectures adapted by the proposed method on self-supervised learning. Self-supervised learning requires deeper architecture than that used in supervised learning. Self-supervised learning is a kind of representation learning, which necessitates larger parameters to be converged. So we employed ResNet50 instead of ResNet20, and we adopted 24
cells instead of 9 cells to DARTS architecture. As a result, the size of the parameters was 24.6$\pm$0.1 for self-supervised learning and the dimensions of the channels were adjusted to match the parameters.
We used a temperature of 0.5, k of 200, epochs of 500, and 0.001 learning rate with Adam optimizer from SimCLR~\cite{chen2020simple} basic training settings. In all experiments, we maintained proxyless feature of the proposed method, which means we carried out the architecture search and learning the weights all at once.

\begin{figure}[t]
\begin{center}
\includegraphics[width=1.0\linewidth]{figures/normal_resnet_ours.pdf}
\vspace{-0.2cm}
\centerline{\small (a) Ours}
\includegraphics[width=1.0\linewidth]{figures/normal_resnet_nat.pdf}
\centerline{\small (b) NAT}
\vspace{-0.2cm}
\caption{Transformed ResNet20 cell architectures}
\vspace{-0.5cm}
\label{resnet}
\end{center}
\end{figure}

\begin{figure}[t]
\begin{center}
\includegraphics[width=1.0\linewidth]{figures/normal_mobilenet_ours.pdf}
\vspace{-0.2cm}
\centerline{\small (a) Ours}
\includegraphics[width=1.0\linewidth]{figures/normal_mobilenet_nat.pdf}
\centerline{\small (b) NAT}
\vspace{-0.2cm}
\caption{Transformed MobileNetV2 cell architectures}
\vspace{-0.5cm}
\label{mobilenet}
\end{center}
\end{figure}

\begin{figure}[t]
\begin{center}
\includegraphics[width=0.7\linewidth]{figures/normal_darts_ours.pdf}
\caption{DARTS normal cell transformed by our method. Reduction cell is the same as the original one.}
\label{darts}
\end{center}
\end{figure}

\subsection{Results on Supervised Learning}
The results of Table~\ref{tab_cifar10_result} have average accuracy, standard deviation, and total cost by various methods with different models on CIFAR-10 dataset.
We trained and inferred five times to get average accuracy and standard deviation.
As shown in Table~\ref{tab_cifar10_result}, the results of NAT is unstable in the case of manually designed models.
The results of our algorithms have better average accuracy and standard deviation than original and NAT in all cases.
Moreover, the total computational cost is lower than NAT.
Note that NAT cannot transform the architecture of ProxylessNAS, since it has various cell architectures in the network.
However, the proposed method successfully improves the performance of ProxylessNAS architecture.

Table~\ref{tab_reproducibility} shows the reproducibility of various methods with different random seeds on CIFAR-10 dataset.
Only one result is presented for each model in NAT paper. Therefore we experimented five times to get the right performance.
In the case of Resnet20 experiments, the results of seed 1 and 4 of NAT are caused by transforming identity edges into none operation.
Transformed Resnet20 architectures of seed 1 are presented in Figure~\ref{resnet}.
Changed edges are notated as red colors.
As shown in Figure~\ref{resnet}(b), NAT transformed all edges to node 5 into none operation.
Therefore, zero tensors are passed to the next layer.

Regarding the result of Mobilenet V2 experiments, the performance of NAT is degraded when it transforms convolution operation into identity operation.
Figure~\ref{mobilenet} shows the transformed Mobilenet V2 architectures of seed 1.
Additionally, we represent the transformed DARTS normal cell architecture of our algorithm in Figure~\ref{darts}.
There is no change in the edges of the reduction cell.

Table~\ref{tab_tiny_result} shows the results of various methods with different models on Tiny Imagenet dataset.
The results of this table describe that both our algorithms have better average accuracy and standard deviation than the original method upon all models.

\begin{table}[t]
\caption{Comparison Average Accuracy, Standard Deviation and Total Cost between original, NAT and Ours on Tiny Imagenet.}
\label{tab_tiny_result}
\vskip 0.05in
\begin{center}
\scalebox{0.8}{
\begin{tabular}{clccccc}
\toprule
& \multicolumn{1}{c}{}& \multicolumn{1}{c}{Avg Acc} & \multicolumn{1}{c}{Std} & \multicolumn{1}{c}{Total Cost}\\
Model & \multicolumn{1}{l}{Method} & \multicolumn{1}{c}{(\%)} & \multicolumn{1}{c}{(\%)}& \multicolumn{1}{c}{(GPU hours)}\\

\midrule
\multirow{3}{*}{Resnet20} & Original & 50.72 & 0.41 & 16.1\\
\cmidrule{2-5}
& Ours(Cell) & \textbf{52.86} & 0.49 & 22\\
& Ours(Full) & 52.7118 & 0.23 & 17.5\\
\midrule
\multirow{3}{*}{\shortstack{Mobilenet \\ V2}}
& Original & 51.57 & 0.76 & 20.3\\
\cmidrule{2-5}
& Ours(Cell) & \textbf{53.17} & 1.03 & 25.5\\
& Ours(Full) & 52.92 & 0.50 & 23.7\\
\midrule
\midrule
\multirow{3}{*}{DARTS} & Original & 59.25 & 0.44 & 39.2\\
\cmidrule{2-5}
& Ours(Cell) & 60.24 & 0.35 & 47\\
& Ours(Full) & \textbf{60.63} & 0.50 & 43.8\\
\bottomrule
\end{tabular}
}
\end{center}
\vskip -0.1in
\end{table}

\subsection{Results on Self-Supervised Learning}
The results reported in Table~\ref{tab_selfsup_result} is evaluated by k-nearest neighbor (KNN) during the representation learning.
Therefore, it may not be better than the performance of linear evaluation reported in~\cite{chen2020simple} but we evaluated all architectures fair conditions.
According to the results of Table~\ref{tab_selfsup_result}, the proposed method outperforms the basic architecture of ResNet50 and DARTS even with similar parameter sizes.

In ResNet50, three operations were changed from none to skip-connection compared to the original architecture. And in DARTS, skip-connection was changed to none in only two places in the reduce cell, resulting in little difference in the size of parameters compared to the cases of supervised learning.
This is due to the fact that self-supervised learning starves a lot of parameters than supervised learning.

\begin{table}[t]
\caption{Comparison Accuracy between original and Ours on Self-Supervised Learning.}
\label{tab_selfsup_result}
\vskip 0.05in
\begin{center}
\begin{tabular}{cclc}
\toprule
\multicolumn{1}{c}{}& \multicolumn{1}{c}{} & \multicolumn{1}{c}{} & \multicolumn{1}{c}{Accuracy}\\
DataSet & Model & \multicolumn{1}{l}{Method} & \multicolumn{1}{c}{(\%)}\\
\midrule
\multirow{5}{*}{CIFAR-10} & \multirow{2.5}{*}{Resnet50} & Original & 82.39\\
\cmidrule{3-4}
& & Ours & \textbf{86.8}\\
\cmidrule{2-4}
& \multirow{2.5}{*}{DARTS} & Original & 88.56\\
\cmidrule{3-4}
& & Ours & \textbf{89.04}\\
\bottomrule
\end{tabular}
\end{center}
\vskip -0.1in
\end{table}

\section{Conclusion}
\label{Conclusion}

We proposed a novel gradient-based neural architecture adaptation algorithm that is reproducible and effective for architecture improvement.
Thanks to the differentiable architecture parameters, our algorithm can train both the architecture and the network at once.
The results of the experiments demonstrate that the proposed algorithm has high reproducibility and stably improves the performance of various models on various datasets.
Moreover, the proposed method can be applied to both supervised learning and self-supervised learning and achieve performance improvement on both learning schemes.

{\small