main_old.tex

\documentclass[12pt]{report}
\renewcommand{\baselinestretch}{1.5} 


% Define margins
\setlength{\topmargin}{-1.0cm}
\setlength{\oddsidemargin}{0.2cm}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{23.0cm}






% Numbering
\makeatletter

\newcommand\frontmatter{%
	\cleardoublepage
	%\@mainmatterfalse
	\pagenumbering{roman}}

\newcommand\mainmatter{%
	\cleardoublepage
	% \@mainmattertrue
	\pagenumbering{arabic}}

\newcommand\backmatter{%
	\if@openright
	\cleardoublepage
	\else
	\clearpage
	\fi
	% \@mainmatterfalse
}

\makeatother


% Define header and footer
%\usepackage{lastpage}
%\usepackage{fancyhdr}
%\pagestyle{fancy}
%\fancyhf{}
%\lhead{{\includegraphics[height=.8cm]{figures/nus.png}}}
%%\rhead{\textbf{\textit{Interpretable and Fair Machine Learning}} }
%\rfoot{\thepage}
%\renewcommand{\footrulewidth}{0.7pt}
%\renewcommand{\headrulewidth}{0.7pt}

% Abstract
\renewcommand\abstractname{\textsc{Abstract}}



% Packages
\usepackage{enumerate}
\usepackage{amsmath}
\usepackage{amsthm,amssymb}
\usepackage{dsfont}
\newtheorem{comment}{Comment}
\usepackage[utf8]{inputenc} 
\usepackage{graphicx}
\usepackage{multirow}
\usepackage{color}
\usepackage{comment}
\usepackage{microtype}
\usepackage{wrapfig}
\usepackage{hyperref}
\usepackage{url}
\usepackage{subfig}
\usepackage{booktabs}
\usepackage{caption}
\usepackage{enumitem,kantlipsum}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{blkarray}
\usepackage{adjustbox}
\usepackage{rotating}

%Hyperlink
\hypersetup{%
	colorlinks=true,% hyperlinks will be coloured
	linkcolor=blue,% hyperlink text will be green
%	linkbordercolor=red,% hyperlink border will be red
}


% Todo packages
\usepackage{xargs}
\usepackage[pdftex,dvipsnames]{xcolor}
\usepackage[colorinlistoftodos,prependcaption,textsize=tiny]{todonotes}
\newcommandx{\unsure}[2][1=]{\todo[linecolor=red,backgroundcolor=red!25,bordercolor=red,#1]{#2}}
\newcommandx{\change}[2][1=]{\todo[linecolor=blue,backgroundcolor=blue!25,bordercolor=blue,#1]{#2}}
\newcommandx{\info}[2][1=]{\todo[linecolor=OliveGreen,backgroundcolor=OliveGreen!25,bordercolor=OliveGreen,#1]{#2}}
\newcommandx{\improvement}[2][1=]{\todo[linecolor=Plum,backgroundcolor=Plum!25,bordercolor=Plum,#1]{#2}}
\newcommandx{\thiswillnotshow}[2][1=]{\todo[disable,#1]{#2}}



% Theorem
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{axiom}{Axiom}
\newtheorem{property}[theorem]{Property}
\newtheorem*{remark}{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{lemmarep}{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{example}{Example}[section]
\newtheorem{corollary}{Corollary}
\newtheorem{construction}[theorem]{Construction}
\usepackage{pgfplots}


% Tikz
\usepackage{tikz}
\usetikzlibrary{automata}
\usetikzlibrary{bayesnet,arrows}
\usetikzlibrary{shapes,fit,calc,positioning}
\tikzset{box/.style={draw, diamond, thick, text centered, minimum height=0.5cm, minimum width=1cm, text width=0.9cm}}
\tikzset{line/.style={draw, thick, -latex'}}


% References
\usepackage{cite}
\usepackage[nameinlink,capitalize]{cleveref}  % easy referencing




% Macros
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\blue}[1]{\textcolor{blue}{#1}}
\newcommand{\green}[1]{\textcolor{green}{#1}}


% Fairness 
%	Justicia
			\newcommand{\justicia}{\ensuremath{\mathsf{Justicia}}}
			\newcommand{\nonsensitive}{\ensuremath{\mathbf{X}}}
			\newcommand{\sensitive}{\ensuremath{\mathbf{A}}}
			\newcommand{\bool}{\ensuremath{B}}
			\newcommand{\boolset}{\ensuremath{\mathbf{B}}}
			\newcommand{\alg}{\mathcal{M}}
			\newcommand{\R}{\ensuremath{\raisebox{\depth}{\rotatebox{180}{R}}}}
			\newcommand{\justiciaenum}{\ensuremath{\mathsf{Justicia\_enum}}}
			\newcommand{\justicialearn}{\ensuremath{\mathsf{Justicia\_infer}}}
			\newcommand{\justiciacond}{\ensuremath{\mathsf{Justicia\_cond}}}
			\newcommand{\numnonsensitive}{\ensuremath{k}}
			\newcommand{\numsensitive}{\ensuremath{m}}
			\newcommand{\abs}[1]{\ensuremath{\mid #1 \mid}}
			
	
%	FVGM
			\newcommand{\fvgm}{\ensuremath{\mathsf{FVGM}}}
			\newcommand{\mediator}{\ensuremath{\mathbf{Z}}}
			\newcommand{\stochastic}{\ensuremath{\mathsf{S3P}}}
			\DeclareMathOperator*{\argmax}{arg\,max}
			\DeclareMathOperator*{\argmin}{arg\,min}
			\newcommand{\graph}{\ensuremath{G}}
			\newcommand{\factors}{\ensuremath{\theta}}
			\newcommand{\parent}{\ensuremath{\mathrm{Pa}}}
			\newcommand{\BN}{\ensuremath{\mathsf{BN}}}
			
%	FairXplainer
			\newcommand{\fairXplainer}{\ensuremath{\mathsf{FairXplainer}}}
			\newcommand{\function}{\ensuremath{g}}
			
			
%			color
			\definecolor{terminate}{gray}{0.8}
			\definecolor{collision}{rgb}{0.2,1,0.3}
			\definecolor{existential}{rgb}{0.9,0.9, 0.1}
			\definecolor{affirmative}{rgb}{0.2,1,0.3}
			

% Interpretability
%		Relaxed CNF
			\newcommand{\Rule}{\ensuremath{{\mathcal{R}}}}
			\newcommand{\clauseweight}[1]{\ensuremath{W \! \left( #1 \right)}}
%			\newcommand{\X}{{\mathbf{X}}}
			\newcommand{\MaxSAT}{\ensuremath{\textsc{MaxSAT}}}
			\newcommand{\noise}{\xi}
			\newcommand{\card}{\eta}
			\newcommand{\noclause}{k}
			\newcommand{\crr}{\ensuremath{\mathsf{CRR}}}
			\newcommand{\CNF}{\ensuremath{\mathsf{Card2CNF}}}
%			\newcommand{\B}{\mathbf{b}}
			\newcommand{\clause}{\ensuremath{\mathsf{clause}}}
			\newcommand{\MLIC}{\ensuremath{\mathsf{MLIC}}}
			\newcommand{\IMLI}{\ensuremath{\mathsf{IMLI}}}
			\newcommand{\ILP}{\ensuremath{\textsc{ILP}}}
			
			
%		Logic
			\newcommand{\propformula}{\phi}
			\newcommand{\propclause}{C}
			\newcommand{\literal}{V}
			\newcommand{\varquantifier}{Q}
			\newcommand{\varweight}{W}
			\newcommand{\ssatformula}{\Phi}
			
%		Bayesian Network
			\newcommand{\graphvertices}{\mathbf{V}}
			\newcommand{\graphvertex}{V}
			\newcommand{\graphedges}{\mathbf{E}}
			\newcommand{\graphedge}{E}
			\newcommand{\bncomplexity}{C}
			\newcommand{\bnnumdiscrete}{\mathsf{Card}}
			
%		Dataset
			\newcommand{\dataset}{\mathbf{D}}
			\newcommand{\datadistribution}{\mathcal{D}}
			
			
			
			
			
			
			
%	    IMLI
			\newcommand{\imli}{\ensuremath{\mathsf{IMLI}}}
			
		

			
			
			
			
\title{\textbf{Interpretability and Fairness in Machine Learning: A Formal Methods Approach}}
\author{
	by\\
	\textbf{Bishwamittra Ghosh}
	\vspace{-0.5em}\\
	(\small\textit{Ph.D Candidate, National University of Singapore})
	\vspace{1em}\\
	\textbf{A thesis submitted for the degree of} \\
	\textbf{Doctor of Philosophy}\\
	in\\
	\textbf{Computer Science}\\
	in the\\
	\textbf{Graduate Division}\\
	of the\\
	\textbf{National University of Singapore}\\
	\textbf{2023}
	\vspace{1em}\\


	Supervisor:
	\vspace{-0.5em}\\
	Assistant Professor Kuldeep S. Meel
	\vspace{1em}\\
	Examiners:
	\vspace{-0.5em}\\
	Assistant Professor Reza Shokri
	\vspace{-0.5em}\\
	Assistant Professor Harold Soh
}
\date{}		
			


\begin{document}
	\begin{titlepage}
%	\input{response.tex}
	\maketitle
%	\thispagestyle{empty}
	\end{titlepage}
	
	
	\frontmatter
	\pagebreak
	\hspace{0pt}
	\vfill
	\begin{center}
		To my parents
	\end{center}
	\vfill
	\hspace{0pt}
	\pagebreak
	
	
	\input{chapters/abstract.tex}
	\input{chapters/list_of_papers.tex}
	
	\pagebreak
	\begin{center}
		\huge Acknowledgment
	\end{center}
	\normalsize
	\pagebreak
	
	
	
	\tableofcontents
	\listofalgorithms
	\addcontentsline{toc}{chapter}{List of Algorithms}
	\listoffigures
	\addcontentsline{toc}{chapter}{List of Figures}
	\listoftables
	\addcontentsline{toc}{chapter}{List of Tables}
	
	
	
	\mainmatter
	\part{Prologue}
	\input{chapters/introduction.tex}
	\input{chapters/background.tex}
	\part{Interpretable Machine Learning}
	
	
	In this part of the thesis, we discuss  an incremental learning framework for interpretable classification rules in Chapter~\ref{chapter:imli}, and extend incremental learning to more expressible classification rules in Chapter~\ref{chapter:crr}. 
%	\input{chapters/interpretability_background.tex}
	
	

%% Interpretability
%%		IMLI
			\chapter{Efficient Learning of  Interpretable Classification Rules}
%				\input{chapters/interpretability/imli/abstract}
				\input{chapters/interpretability/imli/introduction}
				\input{chapters/interpretability/imli/related_work}
%				\input{chapters/interpretability/imli/preliminaries}
				\input{chapters/interpretability/imli/problem_formulation}
				\input{chapters/interpretability/imli/baseline}
				\input{chapters/interpretability/imli/incremental_learning}
				\input{chapters/interpretability/imli/iterative_learning}
				\input{chapters/interpretability/imli/experiment}
				\input{chapters/interpretability/imli/conclusion}
%%
%%
%%
%%		Relaxed CNF
			\chapter{Classification Rules in Relaxed Logical Form}
%				\input{chapters/interpretability/relaxed-cnf/abstract.tex}
				\input{chapters/interpretability/relaxed-cnf/introduction.tex}
%				\input{chapters/interpretability/relaxed-cnf/related_work.tex}
%				\input{chapters/interpretability/relaxed-cnf/preliminaries.tex}
				\input{chapters/interpretability/relaxed-cnf/problem_formulation.tex}
				\input{chapters/interpretability/relaxed-cnf/ilp_formulation.tex}
				\input{chapters/interpretability/relaxed-cnf/incremental_ilp.tex}
				\input{chapters/interpretability/relaxed-cnf/experiment.tex}
				\input{chapters/interpretability/relaxed-cnf/conclusion.tex}
%				
%			
%
%
%
\part{Fairness in Machine Learning}

In this part of the thesis, we discuss fairness verification for classifiers represented as Boolean formulas in Chapter~\ref{chapter:justicia} and linear classifiers in Chapter~\ref{chapter:fvgm}. Finally, we discuss the identification of the sources of unfairness in Chapter~\ref{chapter:fif}.
%	
%%	Fairness
%	\input{chapters/fairness_background.tex}	

%%		Justicia
			\chapter{A Stochastic SAT Approach to Formally Verify Fairness}
%				\input{chapters/fairness/justicia/abstract.tex}
				\input{chapters/fairness/justicia/introduction.tex}
%				\input{chapters/fairness/justicia/preliminaries.tex}
				\input{chapters/fairness/justicia/framework.tex}
				\input{chapters/fairness/justicia/practical.tex}
				\input{chapters/fairness/justicia/experiments.tex}
				\input{chapters/fairness/justicia/discussion.tex}
%				
%				
%%		FVGM
			\chapter{Algorithmic Fairness Verification with Graphical Models}
%				\input{chapters/fairness/fvgm/abstract}
				\input{chapters/fairness/fvgm/introduction}
%				\input{chapters/fairness/fvgm/background}
				\input{chapters/fairness/fvgm/framework}
				\input{chapters/fairness/fvgm/framework2}
				\input{chapters/fairness/fvgm/evaluations}
				\input{chapters/fairness/fvgm/applications}
				\input{chapters/fairness/fvgm/conclusion}
%				
%				
%%		FairXplainer
			\chapter{Computing Fairness Influence Functions with Global Sensitivity Analysis}				
%				\input{chapters/fairness/fif/abstract.tex}
				\input{chapters/fairness/fif/introduction.tex}
%				\input{chapters/fairness/fif/preliminaries.tex}
				\input{chapters/fairness/fif/framework.tex}
				\input{chapters/fairness/fif/fairxplainer.tex}
				\input{chapters/fairness/fif/experiments.tex}
				\input{chapters/fairness/fif/conclusion.tex}	
			
		\part{Epilogue}
	\backmatter
	\input{chapters/conclusion.tex}
	\bibliographystyle{siamurl}
	\addcontentsline{toc}{chapter}{Bibliography}
%	\bibliography{thesis}
	\bibliography{ref}
	
	\input{chapters/appendix.tex}
	

\end{document}