
\documentclass[12pt]{report}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Standard AMS packages
\usepackage{amssymb, amsmath, amsthm}
% *** MATH PACKAGES ***
%
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{booktabs}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{cite}
\usepackage{multirow}
\usepackage{array}
\usepackage{xcolor}
\usepackage{enumitem}
\usepackage{multirow}
\usepackage{booktabs}

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}

\newcommand{\dataset}{{\cal D}}
\newcommand{\fracpartial}[2]{\frac{\partial #1}{\partial  #2}}

\DeclareMathOperator{\argmax}{arg\,max} 

% *** PDF, URL AND HYPERLINK PACKAGES ***
\usepackage{url}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  For mathematical diagrams
\usepackage{xypic}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% For inserting graphic files
\usepackage{graphicx} %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Hyper-references
\usepackage[pdftex, plainpages=false]{hyperref}   %To be use with PDF-TEX

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Graduate college required margins
\usepackage[left=1.5in, top=1.3in, right=1.3in, bottom=1.2in]{geometry}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% line spacing
\usepackage{setspace}
    %\singlespacing
    %\onehalfspacing
    \doublespacing


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Personal Environments and Commands
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}{Example}
\numberwithin{equation}{chapter}
\numberwithin{figure}{chapter}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% My commands
\newcommand{\reals}{\mathbb{R}}   %Real numbers' symbol
\newcommand{\hyperbolic}{\mathbb{H}}  %Hyperbolic symbol
\newcommand{\complex}{\mathbb{C}} %Complex numbers' symbol
\newcommand{\integers}{\mathbb{Z}}   %Integer numbers' symbol
\newcommand{\presentation}[2]{\langle \, #1  \, | \, #2 \,  \rangle}
\newcommand{\GammaH}{Cayley (G, X\cup \widetilde{\mathcal{H}}) }
\newcommand{\Hs}{\{ H_i \}_{i=1}^m}
\usepackage{caption}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% THESIS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{General supervised learning framework for open world classification}
\author{Sai Krishna Theja Bhavaraju}
\date{December 2020}

\pagenumbering{roman}
{%% PAGE NUMBERING ROMAN

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TITLE PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\singlespacing

\newpage
\thispagestyle{empty}
\begin{center}
{ %\large
UNIVERSITY OF OKLAHOMA
\par
\vspace{0.16in}
GRADUATE COLLEGE
\par
\vspace{1.2in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
GENERAL SUPERVISED LEARNING FRAMEWORK 
\par
\vspace{0.17in}
FOR OPEN WORLD CLASSIFICATION
\par
\vspace{1.2in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
A DISSERTATION
\par
\vspace{0.17in}
SUBMITTED TO THE GRADUATE FACULTY
\par
\vspace{0.17in}
in partial fulfillment of the requirements for the
\par
\vspace{0.17in}
Degree of
\par
\vspace{0.17in}
DOCTOR OF PHILOSOPHY
\par
\vfill
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
By
\par
\vspace{0.17in}
SAI KRISHNA THEJA BHAVARAJU
\par
%\vspace{0.05in}
Norman, Oklahoma
\par
%\vspace{0.05in}
2020
}
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% SIGNATURE PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\thispagestyle{empty}
\begin{center}
{%\large
GENERAL SUPERVISED LEARNING FRAMEWORK 
\par
%\vspace{0.17in}
FOR OPEN WORLD CLASSIFICATION
\par
\vspace{0.9in}
A DISSERTATION APPROVED FOR THE
\par
%\vspace{0.17in}
SCHOOL OF INDUSTRIAL AND SYSTEMS ENGINEERING
\par
\vspace{0.9in}
BY THE COMMITTEE CONSISTING OF
\par
\vfill
\begin{flushright}
\begin{tabular}{cr}

\  \  \  \  \  \  \  & Dr. Charles Nicholson, Chair\\
 \\ &  \\
  \\ &  \\

  & Dr. Christan Grant \\
\\ & \\
 \\ &  \\

 & Dr. Andres Gonzalez \\
\\   & \\
 \\ &  \\

 & Dr. Shivakumar Raman \\
 \\ &  \\
  \\ &  \\

   & Dr. Theodore Trafalis \\
\end{tabular}
\end{flushright}
}
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% COPYRIGHT PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\thispagestyle{empty}
\   \
\par
\vfill
\begin{center}
\copyright \    Copyright by SAI KRISHNA THEJA BHAVARAJU \   2020

All rights reserved.
\end{center}
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ACKNOWLEDGEMENTS PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter*{Acknowledgements}

Firstly, I would like to express my sincere gratitude to my advisor Dr. Charles Nicholson for the continuous support, for his patience, motivation, and immense knowledge. His guidance helped me in all the time of research and writing of this thesis. I could not have imagined having a better advisor and mentor for my Ph.D study. Besides my advisor, I would like to thank the rest of my thesis committee: Dr. Christan Grant, Dr. Andres Gonzalez, Dr. Shivakumar Raman, and Dr. Theodore Trafalis for their insightful suggestions and encouragement. I would like to specially thank Dr. Saptarshi Mandal for all the intellectual discussions and brain storming sessions we had. Last but not the least, I would like to thank my family: my parents for supporting me and keeping me motivated throughout my journey. This would not have been possible without their moral support. Also, I thank my friends and my roommates for their continued help and encouragement.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TABLE OF CONTENTS PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\singlespacing
\tableofcontents
%\listoffigures
\listoftables
}
\newpage

} %% END PAGE NUMBERING ROMAN


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pagenumbering{arabic}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% INTRODUCTION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Introduction}
\section{Understanding the open world classification problem}
In traditional supervised learning for classification, models are trained based on data sets that contain examples of all classes to be identified.  That is, in so called \emph{closed world} problems, all classes are known in advance. Once the model is trained, it can used to predict or otherwise discriminate between these same classes in new data.  However, there are problems where this condition does not hold.  That is, in \emph{open world} problems, the training data is incomplete and the new data for which the model has been developed may contain classes which the model was not trained on.  This problem has its origins in the field of computer vision for recognition in which a target image class or set of classes should be recognized among known and unknown image classes.  Indeed, much of the research on open world problems is concentrated within the domain of computer vision and referred to as open set recognition (OSR) or open world recognition (OWR). In \cite{scheirer2012}, one of the earliest works in OSR, the authors formally defined terms such as  open space and openness that correspond to the problem of open set recognition, and also show how this problem setting is different from general data modeling task.  In \cite{bendale2015towards}, the authors extend the concept of OSR to OWR and identify the necessary tasks for an effective system, i.e., the system should be able to detect unknown classes, label unknown points, and update the model.
The open world supervised learning scenario is not limited to computer vision, but applies to numerous domains associated with traditional classification problems,  i.e., open world classification is applicable to any classification problem without a guarantee on the exhaustiveness of the training classes.  Indeed, it is plausible that one not know a priori if a multi-class problem is open or closed.  Given this broad spectrum for application, the open world condition applies to problems with vastly different data types, sources, and characteristics which includes image, text, sensor data,  or more traditional structured data types.  

The present work addresses this with a general framework that tackles this broad perspective.   For open world classification (OWC), ideally a model is trained on a finite set of known classes and when applied to new data, it is able to accurately address four tasks: (i) label all known classes, (ii) identify the instances associated with the new, unknown classes, (iii) create new, distinct classes for these instances, and (iv) update itself without losing predictive performance power on the known classes and be able to consistently classify the unknown classes in new data. These tasks are similar to those from \cite{bendale2015towards}, however, unlike their work, here we are only interested in an approach which accomplishes these goals automatically and without human intervention.  Furthermore, OWC should not be limited to only specific machine learning (ML) techniques, since depending on the domain and data type, modelers often use different type of classifiers for the problem at hand.  The present study addresses these goals with a framework that applies irrespective of the type of data or nature of the classifier.

\section{Contributions of this work}
The present work develops a general framework that tackles the problem of open world classification (OWC), by addressing the following four tasks: (i) label all known classes, (ii) identify the instances associated with the new, unknown classes, (iii) create new, distinct classes for these instances, and (iv) update itself without losing predictive performance power on the known classes and be able to consistently classify the unknown classes in new data. However, the first task is not the focus of this paper and the remaining three tasks can be broadly classified into two categories namely, identification and categorization. While the task of identification involves identifying data instances associated with the new or unknown classes, categorization deals with the discovery of the unknown classes and also categorizing the identified instances into their respective classes, without human intervention. The contributions of this paper can be attributed to these two tasks and are as follows:

\paragraph{Identification of unknown data}
Most of the works in the literature address the open world problem in the domain of computer vision. Furthermore, the solutions proposed to this problem are very algorithmic specific and are tied to a specific machine learning algorithm, which restricts other researchers from using classifiers of their interest. To address this issue, we approach this problem with a two stage process by separating the training phase from the identification phase. In Chapter \ref{iden}, we developed an algorithm that identifies the data instances from open world data that belong to unknown classes. This algorithm can be used in conjunction with any classifier and also the type of the data.

\paragraph{Categorization of unknown data}
Most of the works in the literature, propose solutions to the identification task as a complete solution to the open world problem. One the other hand, identifying the data belonging to unknown classes as the only solution, it is important to discover the number of new classes and also to categorize the instances accordingly. Furthermore, the tasks of class discovery and categorization should not include any human intervention. In Chapter \ref{categ}, we developed an algorithm that discovers the unknown classes and also categorize the instances into their respective classes, without any human intervention.

\chapter{Literature review}
\section{Introduction}
In the previous chapter, four tasks corresponding to OWC have been stated, of which the first task is not the focus of this paper, assuming a high quality classifier already exists. However, the remaining three tasks can be broadly classified into two categories namely, identification and categorization. While identification deals with identifying instances associated with the new or unknown classes, categorization involves categorizing these instances into new, distinct classes. Furthermore, the task of updating the model with an additional capability of classifying the new classes, is also considered a part of the categorization phase. The works available in the literature are grouped into these two categories and presented in this section.
\section{Identification of unknown classes}
As specified in the previous section, OSR based works, constitute major portion of literature related to this task and we make an effort to present some of the noticeable works in this section.

Open set recognition as defined in \cite{scheirer2012} provides a mathematical foundation and basic definitions for open world problems.  Furthermore, in the same work, the authors modify a support vector machine to design a 1-vs-set machine to address OSR. \cite{scheirer2014probability} extended this to deal with multiple target classes and formulated a Weibull-Calibrated SVM in conjunction with a  technique based on compact abating probability to identify the data instances belonging to unknown classes.  Similarly, \cite{jain2014multi,scherreik2016open} have modified a traditional SVM classifier to adapt to the open world setting. Alternatively, there are works \cite{mensink2013distance,bendale2015towards,ristin2014incremental} in the literature based on the Nearest Class Mean (NCM) classifier to solve the problem of open set recognition. Similarly, \cite{junior2017nearest} developed an open set classifier that is an extension to the nearest neighbor classifier for OSR. \cite{agrawal1993mining}

Apart from considering the traditional ML models for OSR, there are works that address this problem from a deep learning perspective. One of the early works corresponding to this progression is done by \cite{bendale2016towards}, where the authors replaced the SoftMax layer of a neural network with an OpenMax layer to adapt to the problem of open set recognition. Similarly, \cite{shu2017doc,kardan2017mitigating} developed methods to handle OSR by making algorithmic modifications to the output layer of a deep neural network. On the other hand,  \cite{hassen2018learning} tried to solve the problem of open set recognition by developing a neural network based representation of the data samples. \cite{oza2019c2ae} introduced a modified version of an autoencoder to solve for OSR. In their next work, Multi task learning based CNN for OSR was developed by \cite{oza2019deep}.
Applications of OSR in various fields such as malware detection, face recognition, text classification etc., were done by \cite{rieck2011automatic,gunther2017toward,cevikalp2013face,fei2016breaking,prakhya2017open,shu2017doc}. While most of the deep learning based works discussed so far are discriminative approaches, there are works in the literature that address this problem in a generative perspective as well. Similar to the OpenMax classifier discussed previously, \cite{ge2017generative} developed a generative openmax classifier to identify data points from unknown classes. Conversely, \cite{neal2018open} proposed a new data augmentation technique called counterfactual image generation (OSRCI) in conjunction with generated adversarial network (GAN) to address the problem of OSR. Other works in the field of OSR include \cite{cevikalp2016best,zhang2016sparse,vignotto2018extreme,rozsa2017adversarial,cardoso2017weightless,yoshihashi2019classification,rudd2017extreme,jo2018open}.
A more detailed survey about the various works in this field is provided by \cite{geng2020recent}. 


\section{Categorization of unknown classes}
All the works in the domain of open set recognition that have been discussed so far mainly focuses on just the identification of the data instances coming from unknown classes; they do not provide any solutions as to how the identified data can be organized into their respective classes. However, we have identified few works that try to solve this problem. In \cite{bendale2015towards}, the authors tried to categorize the data instances by human intervention, where the identified data instances were manually labelled and used to further update the model. In \cite{shu2018unseen}, the authors developed a neural network based model called Pairwise Classification Network (PCN) to identify if two images belong to the same class  or a different class, along with another deep learning model called Open Classification Network (OCN) for open image classification. The predictions made by PCN are used as a distance function for hierarchical clustering to cluster the data points. In \cite{geng2018collective}, on the other hand, tried to solve this problem from a generative modeling perspective where they implement modified Hierarchical Dirichlet Process (HDP) to model both the training and test data, and also to come up with an estimate as to how many clusters are possibly present in the test data. They claim that this estimate can be further used as a prior to clustering algorithms such as K-means, etc. Considering these works, the solution provided by \cite{bendale2015towards} does not satisfy our need completely, as we would want a technique that automatically identifies the clusters in the data without any human intervention. On the other hand, \cite{shu2018unseen} and \cite{geng2018collective} also provide an estimation as opposed to accurate value about the possible number of clusters in the data. On the whole, we can understand that the categorization of the identified data instances is still an unsolved problem, and there is a need for a solution that can automatically and accurately organize the identified instances.
\section{Other related work}
We briefly mention areas within supervised learning that have some conceptual similarities to open world classification, yet are distinct from and pose entirely different challenges than open world problems.  \emph{Semi-supervised learning} train models on relatively small subsets of labeled data and a large set of unlabeled data \cite{chapelle2009semi}.  \emph{Few shots learning} \cite{snell2017prototypical,ravi2016optimization, garcia2017few,lake2013one,bertinetto2016learning,fu2013learning}, \emph{one shot learning} \cite{vinyals2016matching,fei2006one}, and \emph{zero shot learning}  \cite{palatucci2009zero,lampert2009learning,fu2018recent} are extreme forms of semi-supervised learning.  In the latter case, while models are trained to make predictions on data that belong to classes not seen during training, the algorithm is provided semantic or attribute information regarding the unseen classes \cite{geng2020recent}. \emph{Domain adaption} machine learning is designed for scenarios in which the training data and the test data have different data distributions \cite{daume2006domain,ben2007analysis, daume2009frustratingly,patel2015visual,yamada2014domain}. In \emph{concept drift} problems \cite{widmer1996learning,vzliobaite2010learning,gama2014survey}, the data distribution changes dynamically over time and the ML model must update itself.  However, in all of these domains, all classes are known in advance of model training.  This includes the number of classes that may be encountered as well examples of all classes and/or information about all classes. In the open world classification problem we address, we assume no information about the quantity or quality of any unknown classes in the test data.    
\section{Gaps and research objectives}
While there are much fewer works that try to provide solution to the problem of open world classification, there are certain drawbacks associated with them. 
\begin{itemize}
	\item Most of the works discussed above are applied especially to the domain of computer vision.
	\item All the works make algorithmic changes to the existing machine learning models to come with a classifier that can handle the open world problem.
	\item To the best of our knowledge, there are no signs of works that can be applied to any given type of data.
	\item There are no techniques available in the literature that can accurately categorize the data instances into their categories.
\end{itemize}

Taking the above mentioned drawbacks into consideration, the following research objectives have been formulated, and will be addressed in the present work.
\begin{itemize}
	\item \textit{ Research objective 1: To develop a methodology that can handle the open world problem for any type of data.}
	
	\item \textit{ Research objective 2: To come up with a technique that can automatically categorize the data instances from unknown classes without human intervention}
\end{itemize}
\chapter{Identification of data that belong to unknown classes} \label{iden}
\section{Background and methodology}
Let $\mathcal{K}$ denote the set of all known classes and $\mathcal{U}$ denote the set of unknown classes. Let $\mathcal{T}$ denote the training data containing instances of $k=|\mathcal{K}|$ known classes and $\mathcal{O}$ denote the open world test data which may contain up to $k + u$ classes, where $u = |\mathcal{U}|$. Let $n_\text{T}$ denote the number of observations in $\mathcal{T}$ and $n_\text{O}$ denote the number of observations in $\mathcal{O}$.  For a given observation $i$, let $c_i \in \mathcal{K} \cup \mathcal{U}$ denote the true class. Both $\mathcal{T}$ and $\mathcal{O}$ have the same number of features, $m$. Let $\mathcal{C}$ be any classifier, trained on $\mathcal{T}$, which maps the $m$-dimensional training or test data to $k$ probability values, $0 \le p_j \le 1 \ \forall j \in \mathcal{K}$.  Additionally, $\sum_{j \in \mathcal{K}}p_j = 1$. If $X$ denotes the input data, then $\mathcal{C}: X\to\mathbb{R}^k$, whereas the predicted class  is given by $\hat{c} = \argmax_{j \in \mathcal{K}} p_j$.   

% \begin{table}[ht]
% 	\centering
% 	\caption{Notation}
% 	\begin{tabular}[t]{lcc}
% 		\toprule
% 		Notation&information\\
% 		\midrule
% 		$\mathcal{K}$&set of all known classes\\
% 		$\mathcal{U}$&set of unknown classes\\
% 		$\mathcal{T}$&Training data containing instances of $k=|\mathcal{K}|$ known classes\\
% 		$\mathcal{O}$&open world test data which may contain up to $k + u$ classes, where $u = |\mathcal{U}|$\\
% 		$n_\text{T}$&number of observations in $\mathcal{T}$\\
% 		$n_\text{O}$&number of observations in $\mathcal{O}$\\
% 		$c_i$&For a given observation $i$, $c_i \in \mathcal{K} \cup \mathcal{U}$ denotes the true class\\
% 		$\mathcal{C}$&classifier, trained on $\mathcal{T}$, which maps the $m$-dimensional training or test data to $k$ probability values, $0 \le p_j \le 1 \ \forall j \in \mathcal{K}$\\
% 		\bottomrule
% 	\end{tabular}
% 	\label{tab:example2}
% \end{table}%

There are basically two key issues to be addressed in the context of open world problem, of which the first motive is to identify the data instances belonging to the unknown classes (identification) and the second motive is to categorize these identified data points into their respective categories (categorization). 

The task of identifying unknown classes is necessary when a trained classifier is applied to the open world test data.  Hence, it   sufficient to have an identification method that occurs during the application phase.  As mentioned in the previous section, a lot of works in the field of open world problem have been limited to computer vision and are mostly algorithmic modifications to existing machine learning models. Furthermore, these works try to integrate the task of identification with the actual model training, making it a single process.

However, to provide a general approach to identify instances in $\mathcal{O}$ associated with classes in $\mathcal{U}$, we separate model training or algorithm specifications from the identification task.  This is accomplished by performing anomaly detection on the $k$-dimensional probability space generated by $\mathcal{C}(\mathcal{T})$ and $\mathcal{C}(\mathcal{O})$. The identification task is now independent of the type of probabilistic classifier and makes no assumptions on the original input data.

The probability distribution generated by $\mathcal{C}(\mathcal{T})$ is a function of the quality of the classifier and the separability of the classes in the training data.  However, the $k$-dimensional probability space is independent of the type of data associated with any problem domain.  For perfect probabilistic classifiers, not only is the predicted class correct for any observation $i$, i.e., $\hat{c}_i = c_i$, but also  each $p_j$ is a $k$-dimensional binary vector.  If such a classifier were applied to an observation associated with class $j \notin \mathcal{K}$, the $k$-dimensional space would be inadequate to represent the entity.  Nonetheless, the observation would be mapped as to the space.  The projection of such a point would likely be a non-binary vector of probabilities.  For less than perfect classifiers, we operate under the hypothesis that the $k$-dimensional probability distribution for a known class is detectably distinct from that of the distribution for an unknown class.   

There are a variety of metrics to measure dissimiliarity between probability distributions including Kullback–Leibler (KL) divergence \cite{kullback1951information} and Jensen-Shannon distance (JSD) \cite{lin1991divergence}. For two probability distributions $P$ and $Q$ on the same probability space $X$, the KL divergence $D_\text{KL}$ is computed as
\begin{equation*} \label{KL}
D_\text{KL} \left( P \middle\| Q \right) =  \sum_{x \in X} P(x) \log \frac{P(x)}{Q(x)} 
\end{equation*}

\noindent The JSD is a symmetric dissimilarity measurement based on the asymmetric KL divergence.   The JSD between two probability distributions $P$ and $Q$ is 
\begin{equation*} \label{JSD}
D_\text{JSD} \left( P \middle\| Q \right) =   \sqrt{\frac{1}{2}D_\text{KL} \left( P \middle\| M \right) +    \frac{1}{2}D_\text{KL} \left( Q \middle\| M \right)}
\end{equation*}
\noindent where $M = \frac{1}{2} \left(P + Q\right)$.

\section{Algorithm for anomaly detection using Jensen-Shannon distance}
The algorithm for identification of unknown classes based on JSD follows.  First, the predicted probabilities from the trained classifier are determined.  Specifically,  $\mathbf{P}_{\text{train}}$ is an $n \times k$ probability matrix generated from the application of $\mathcal{C}$ on $\mathcal{T}$. For each class $j \in \mathcal{K}$, compute the centroid, $\tilde{c}_j$, for the set of observations $C_j = \{i \in \mathbf{P}_\text{train} :  c_i = j \}$ of the predicted probability distributions from $\mathbf{P}_{\text{train}}$.  Next, compute the $D_{\text{JSD}}$ between every observation $i \in C_j$ and each $\tilde{c}_j$ and determine the corresponding mean, $\mu_j$, and standard deviation, $\sigma_j$, of the dissimilarity values between each point and each centroid. 

Generate the prediction probabilities for every data point in $O$ using $\mathcal{C}$ and store in $\mathbf{P}_{\text{test}}$. The JSD for every point $i  \in \mathbf{P}_{\text{test}}$ to the previously determined centroids is computed, $D_{\text{JSD}}(i,\tilde{c}_j) \ \forall j \in \mathcal{K}$.  These values are then mean-centered and scaled using $\mu_j$ and $\sigma_j$.

For each class $j \in \mathcal{K}$, if the value of the test point $i$ from $\tilde{c}_j$ is greater than critical value ($\mathcal{\tau}$), the data point is identified as anomaly and is stored in $\mathcal{F}$. The value of $\mathcal{\tau}$ is determined using Chebyshev's inequality \cite{saw1984chebyshev} based on a confidence parameter ($\alpha$). Since we are unaware of the underlying distribution from which the distances are generated, using Chebyshev's inequality will provide generalization to the method as it can be used for any data set irrespective of its underlying distribution.

\begin{algorithm} 
	\caption{Identify outsiders (Jensen-Shannon Distance)}
	\label{alg:JSD}
	\textbf{Input: }
	
	\hspace*{\algorithmicindent} training data $\mathcal{T}$ with $n$ observations
	
	\hspace*{\algorithmicindent} open world data $\mathcal{O}$
	
	\hspace*{\algorithmicindent} probabilistic classifier $\mathcal{C}$
	
	\hspace*{\algorithmicindent} confidence parameter $\alpha$
	
	\textbf{Output:} 
	
	\hspace*{\algorithmicindent} $\mathcal{F}$: flagged data
	
	\begin{algorithmic}[1] 
		
		
		\State $\mathbf{P}_{\text{train}} \gets \mathcal{C}\left(\mathcal{T}\right)$ 
	%	\State $P_{train}$ = $find\_prediction\_probability(\textit{$\mathcal{C}$,$T$})$
		\State Compute centroids $\tilde{c}_j \ \forall j \in \mathcal{K}$ from $\mathbf{P}_{train}$ 
		\State Compute $D_{\text{JSD}}(i,\tilde{c}_j) \ \forall i \in \mathbf{P}_{train}$ and $\mu_j, \sigma_j \ \forall j \in \mathcal{K}$
		\State $\mathbf{P}_{\text{test}} \gets \mathcal{C}\left(\mathcal{O}\right)$ 
		\State For each $j \in \mathcal{K}$, compute $D_{\text{JSD}}(i,\tilde{c}_j) \ \forall i \in \mathbf{P}_{test}$ and mean-center and scale using $\mu_j$ and $\sigma_j$
		\State Determine $\tau$ using Chebyshev's inequality for a confidence parameter $\alpha$ 
		\State For each $i  \in \mathbf{P}_{\text{test}}$, if the scaled value of $D_{\text{JSD}}(i,\tilde{c}_j) \geq \  \tau, \  \forall j \in \mathcal{K}$, identify $i$ as an anomaly and store it in $\mathcal{F}$.
	\end{algorithmic}
\end{algorithm}

\chapter{Categorization of data that belong to unknown classes} \label{categ}

\section{Background and methodology}
Once data instances are identified as not belonging to the set of known classes, the next step is to categorize the instances into new classes. This is the most critical part of the analysis since incorrect categorization of instances can mislead the model while making predictions. 

The prediction probabilities associated with the data instances are the key drivers for this analysis as they offer generalization to the methodology. When classifier $\mathcal{C}$ is applied to observations belonging classes in $\mathcal{U}$, the resulting $k$-dimensional space is generally inadequate. The distribution of prediction probabilities corresponding to observations that belong to class $j \in \mathcal{K}$ are ideally skewed towards class $j$ in such a way to as exceed some confidence threshold. This is impossible for classes in $\mathcal{U}$.  The error distribution for an observation belonging to class $i \in \mathcal{U}$ may either be non-informative or contain inherent patterns since the open world classifier is incomplete with respect to classes in $\mathcal{U}$. We hypothesize that the error is informative and additionally there is a distinguishable \emph{residual signature} for different unknown classes. 

\section{Algorithm for detecting unknown classes using association rule mining (ARM)}
ARM is a rule-based machine learning method to discover interesting relations between variables in a large databases \cite{agrawal1993mining} and is considered great tool for decision making in various fields such as, market basket analysis \cite{chen2005market,russell2000analysis}, medical diagnosis \cite{gamberger1999high,nahar2013association}, Bioinformatics \cite{gupta2006mining,leung2010discovering,park2009prediction}, Multimedia \cite{zaiane2000mining,shyu2001generalized}, computer network security \cite{treinen2006framework,mabu2010intrusion}, census data \cite{malerba2003mining}, remote sensing data \cite{ding2002association,rajasekar2009application}. 

The algorithm for categorization of identified data instances based on ARM is provided in Algorithm \ref{alg:ARM}.  The required inputs for this algorithm include the sets $\mathcal{T}$, $\mathcal{F}$, $\mathcal{O}$, and the classifier $\mathcal{C}$. Furthermore, $\omega$, $\eta$, $\beta$, and $\gamma$ are user-defined parameters that are described below.

This is an iterative algorithm where the unknown classes are discovered based on the residual signatures that exist within the flagged instances. Furthermore, for every unknown class discovered, all the instances associated with that particular unknown class are identified and removed from the flagged set $\mathcal{F}$. This process is continued until the stopping criteria is satisfied. The stopping condition for this algorithm is when there are less than $\omega$ fraction of data points left in $\mathcal{F}$.

The first step in the methodology is to find the prediction probabilities of all the identified data instances. Specifically,  $\mathbf{P}_{\text{identified}}$ is an $m \times k$ probability matrix generated from the application of $\mathcal{C}$ on $\mathcal{F}$, where $|\mathcal{F}|= m$. An example is depicted in Table \ref{tab:example1}. In this table, index 1 is associated with the first flagged observation for which classes $c_1$ and $c_2$  have the H highest probabilities across the residual signature. Similarly, the highest $H$ probabilities for every data point in $\mathbf{P}_{\text{identified}}$ are determined and  the corresponding training class labels are stored as items in a set $\mathcal{I}$. Table \ref{tab:example2} depicts an example set $\mathcal{I}$ for $H$=2 from the data shown in Table \ref{tab:example1}. Apply the Apriori algorithm \cite{agrawal1994fast} on $\mathcal{I}$ to generate frequent itemsets of length $H$ based on a user-defined value of support ($S$) and confidence ($C$). Support and confidence are ARM-specific parameter values. Determine the itemset $s$ from $\mathcal{I}$, with the highest support value and identify all the instances from $\mathcal{F}$ with $s$ as their highest $H$ probabilities and store them in $\mathcal{B}$. If the number of data points in $\mathcal{B}$ is at least $\eta$ percentage of $\mathcal{F}$, proceed forward. Update $\mathcal{F}$  by removing $\mathcal{B}$ from $\mathcal{F}$. Next step is to label all the instances in $\mathcal{B}$ with a new class $k+i$. Initially $i$ is to set to be equal to 0 and is incremented by 1 for every unknown class discovered. Update $\mathcal{T}$ by appending  $\mathcal{B}$ to $\mathcal{T}$. Retrain the classifier $\mathcal{C}$ on $\mathcal{T}$. Make predictions on $\mathcal{F}$ using $\mathcal{C}$ and determine all the instances that are predicted as $k+i$ with a prediction confidence (prediction probability) value of at least $\gamma$ and store them in $\mathcal{P}$. Update $\mathcal{F}$ and $\mathcal{T}$ by removing $\mathcal{P}$ from $\mathcal{F}$ and appending $\mathcal{P}$ to $\mathcal{T}$. This process is repeated until the number of data points in $\mathcal{P}$ is less than $\beta$ $|\mathcal{F}|$.  The output of this algorithm is an updated classifier ($\mathcal{C}$) that is capable of classifying both the known and the identified unknown classes. 

\begin{algorithm} 
	\caption{Residual signature based categorization of identified instances}
	\label{alg:ARM}
	\textbf{Input: }
	
	\hspace*{\algorithmicindent} training data $\mathcal{T}$ with $n$ observations
	
	\hspace*{\algorithmicindent} identified data $\mathcal{F}$ with $m$ observations
	
	\hspace*{\algorithmicindent} open world data $\mathcal{O}$
	
	\hspace*{\algorithmicindent} probabilistic classifier $\mathcal{C}$
	
	\hspace*{\algorithmicindent} maximum probability parameter $H$
	
	\hspace*{\algorithmicindent} $\omega$, $\eta$, and $\beta$: termination parameters
	
    \hspace*{\algorithmicindent} $\gamma$: prediction probability parameter
	
	\textbf{Output:} 
	
	\hspace*{\algorithmicindent} Updated probabilistic classifier $\mathcal{C}$ 
	\begin{algorithmic}[1] 
		\State $L  \gets |\mathcal{F}| $
		\State $i \gets 0$
		\While{$|\mathcal{F}|$ $\geq$ $\omega$($L$)}
		\State $\mathbf{P}_{\text{identified}} \gets \mathcal{C}\left(\mathcal{F}\right)$ 
		\State create $\mathcal{I}$ from $\mathbf{P}_{\text{identified}}$ based on $H$
		%\State Generate frequent itemsets from items in $\mathcal{I}$ and store them in $\mathcal{V}$ for a corresponding value of $S$ and $C$
		\State $\mathcal{B}$ $\leftarrow$ instances in $\mathcal{F}$ associated with the itemset with the highest support value.
% 		\State Determine the itemset $s$ from $\mathcal{I}$ with the highest support value and identify all the instances from $\mathcal{F}$ associated with itemset $s$ and store them in $\mathcal{B}$
		\If{$|\mathcal{B}| < \eta|\mathcal{F}|$} 
		
			\Return $\mathcal{C}$
		\EndIf

		
		%\State Create $\mathcal{R}$ by labeling instances in $\mathcal{B}$ with a new class $k+1$
		\State $i \leftarrow i +1$
		\State $\mathcal{F} \leftarrow \mathcal{F} \setminus \mathcal{B}$
		\State create new label $k+i$ for all observations in $\mathcal{B}$
		\State $\mathcal{T} \leftarrow \mathcal{T} \cup \mathcal{B}$
		\State retrain classifier $\mathcal{C}$ on $\mathcal{T}$
		
		\Repeat
		      %  \State $\mathcal{C}(\mathcal{F})$
		      \State $\mathcal{P}$ $\leftarrow$ instances in $\mathcal{F}$ that are predicted as $k+i$ with a prediction probability of at least $\gamma$ 
		%\State $z=0$

		\State $\mathcal{T} \gets \mathcal{T} \cup \mathcal{P}$
		\State retrain classifier $\mathcal{C}$ on $\mathcal{T}$
		\State $\mathcal{F} \gets \mathcal{F} \setminus \mathcal{P}$
		\Until{$|\mathcal{P}| < \beta |\mathcal{F}|$}
		\EndWhile
		
\State \Return $\mathcal{C}$
	\end{algorithmic}
\end{algorithm}

\begin{table}[ht]
	\centering
	\caption{$\mathbf{P}_{\text{identified}}$}
	\begin{tabular}[t]{lccccc}
		\toprule
		index&$c_1$&$c_2$&$c_3$&$\ldots$&$c_k$\\
		\midrule
		1 &\textbf{0.40}&\textbf{0.50}&0.08&&\\
		2&\textbf{0.70}&0.07&\textbf{0.20}&&\\
		3&\textbf{0.60}&0.09&\textbf{0.30}&&\\
		$\vdots$&&&&$\ddots$&\\
		$m$&&&&&\\
		\bottomrule
	\end{tabular}
	\label{tab:example1}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{$\mathcal{I}$ for $H$=2}
	\begin{tabular}[t]{lcc}
		\toprule
		index&itemset\\
		\midrule
		1 & $\{c_1, c_2\}$ \\
		2&$\{c_1, c_3\}$ \\
		$\vdots$&\\
		m& $\{c_1, c_3\}$ \\
		\bottomrule
	\end{tabular}
	\label{tab:example2}
\end{table}%


% \begin{table}[ht]
% 	\centering
% 	\caption{$\mathcal{I}$ for $H$=2}
% 	\begin{tabular}[t]{cccc}
% 		\toprule
% 		itemset&Support\\
% 		\midrule
% 		 $\{c_1, c_3\}$&0.25 \\
% 		$\{c_1, c_2\}$&0.15 \\
% 		$\{c_2, c_3\}$&0.12 \\
% 		$\vdots$&$\vdots$\\
% 		\bottomrule
% 	\end{tabular}
% 	\label{tab:example3}
% \end{table}%

\chapter{Experiments and results}
\section{Introduction}
To analyze the performance of the proposed methodology, four different experiments with the number of unknown classes ranging from 0 to 3 are conducted. A wide variety of data types from different domains are considered. Table \ref{tab:experiments} lists all the experiments conducted and the associated data sets.

\begin{table}[ht]
	\centering
	\caption{Data description}
	\begin{tabular}[t]{clcccc}
		\toprule
		Experiment & Data & $|\mathcal{K}|$ & $|\mathcal{U}|$&$n_\text{T}$&$n_\text{O}$ \\
		\midrule
		1&Code commit messages & 5&0&1418&1351\\
		2&Traditional numeric data & 6&1&5416&2690\\
		3&Human activity recognition & 6&2&2898&2839\\
		4&Hand written digits & 10&3&22504&6000\\
		\bottomrule
	\end{tabular}
	\label{tab:experiments}
\end{table}%

Certain factors are same across all experiments. Random Forest is used as the classifier and Table \ref{tab:performance} lists the accuracy, precision, recall and f1-score for the performance of the classifier. on the training data, prior to implementing the proposed framework. The level of confidence for the Chebyshev's inequality ($\alpha$) is considered to be 0.1 and the distance metric used is Jensen-Shannon Distance.

\begin{table}[ht]
	\centering
	\caption{Performance of $\mathcal{C}$ in every experiment}
	\begin{tabular}[t]{lcccc}
		\toprule
		Performance metric&1&2&3&4 \\
		\midrule
		Accuracy&0.98&0.95&0.94&0.97\\
		Precision&0.98&0.95&0.94&0.97\\
		Recall&0.98&0.95&0.94&0.97\\
		F_{1}-$\text{score}$ &0.98&0.95&0.94&0.97\\
		\bottomrule
	\end{tabular}
	\label{tab:performance}
\end{table}%

\section{Data}
\subsection{Code commit messages}
CCM data for experiment 1 is derived from different open source projects available on GitHub such as messages that belong to different categories such as bug fixing, design improvement, adding new features, improving non functional requirements and no category. The dataset contains 5 different classes with a total of 3377 instances. 
 
 \subsection{Traditional numeric data}
TND  \cite{johnson2016integrating} used for experiment 2 is derived from Geo-spatial data having six different classes corresponding to the land cover such as  impervious, farm, forest, grass, orchard and water. The features present in the dataset are the maximum NDVI (normalized difference vegetation index) values derived from the time-series of satellite images. Each observation in the dataset is represented using 29 attributes and there are a total of 10546 observations.

\subsection{Human activity recognition data}
HAR is a sensor data \cite{anguita2013public} corresponding to different human activities such as walking, walking upstairs, walking downstairs, sitting, standing and laying. This dataset contains 10299 observations and 561 features.

\subsection{Hand written digits data}
This dataset \cite{lecun2010mnist} contains images corresponding to the hand written digits 0 to 9. There are a total of 60000 observations each represented by a 784 dimensional feature vector. 

\section{Analysis on text data} \label{text}

As the first step in the process, Algorithm \ref{alg:JSD} is applied on the open world data containing 1351 instances, out of which 52 have been identified, which is less than 4\% of the total number of observations in $\mathcal{O}$. Based on the Chebyshev's inequality, there is a chance for 10\% of the known data to be identified as belonging to unknown classes. Furthermore, presence of an unknown class would result in higher percentage of identified instances. However, in this scenario, we do not see a strong evidence to suspect the presence of an unknown class. Thus, we can terminate the algorithm here and not proceed forward to the second stage of the methodology.

% \begin{table}[ht]
% 	\centering
% 	\caption{Text data: Performance of $\mathcal{C}$ on $\mathcal{T}$}
% 	\begin{tabular}[t]{lc}
% 		\toprule
% 		Performance metric&$\mathcal{C}$ \\
% 		\midrule
% 		$Accuracy$&0.98\\
% 		$Precision$&0.98\\
% 		$Recall$&0.98\\
% 		$F1-score$&0.98\\
% 		\hline
% 	\end{tabular}
% 	\label{tab:perftrain3}
% \end{table}%

\begin{table}[ht]
	\centering
	\caption{Classwise data distribution of $\mathcal{O}$ and $\mathcal{F}$ for Text data}
	\begin{tabular}[t]{cccc}
		\toprule
		Class& class information &$|\mathcal{O}|$&  $|\mathcal{F}|$\\
		\midrule
		$1$&bug fixing&417&19\\
		$2$&no category&117&1\\
		$3$&design improvement&181&8\\
		$4$&adding new features&229&5\\
		$5$&non functional requirements&407&19\\
		\bottomrule
	\end{tabular}
	\label{tab: dist3}
\end{table}%


% \begin{table}[ht]
% 	\centering
% 	\caption{Class wise data distribution of $\mathcal{F}$ for text data}
% 	\begin{tabular}[t]{lcc}
% 		\toprule
% 		&Number of instances\\
% 		\midrule
% 		$0$&19\\
% 		$1$&1\\
% 		$2$&8\\
% 		$3$&5\\
% 		$4$&19\\
% 		\hline
% 	\end{tabular}
% 	\label{tab: flaggeddist3}
% \end{table}%

\section{Analysis on Crowd sourcing data} \label{crowd}
The training data considered for this experiment contains classes \textit{1, 2, 3, 4} and \textit{5} and the open world data contains a new class \textit{0} along with the known classes. From Table \ref{tab: dist2}, it is evident that 1150 out of 2690 instances have been identified by Algorithm \ref{alg:JSD}. Furthermore, about 88\% of the identified data instances belong to the unknown class. As we have a large number of instances identified in the first step, we proceed forward to the categorization stage of the framework. Algorithm \ref{alg:ARM} is applied on $\mathcal{F}$ using the parameter setting provided in Table \ref{tab: param2} and it successfully discovered the unknown class. This evident from Table \ref{tab:newclassifier2}, as we see that about 88\% of the data instances belonging to class \textit{0} are classified correctly and the majority of the remaining instances are misclassified as class \textit{1}, as class \textit{0} (farm) is more similar to class \textit{1} (forest). The overall accuracy of the classifier increases from 50\% to 90\% and the information regarding other performance metrics is provided in Table \ref{tab:comp2}. This experiment demonstrates the successful working of the proposed methodology for the case when a single unknown class is present in the open world data. 


\begin{table}[ht]
	\centering
	\caption{Classwise data distribution of $\mathcal{O}$ and $\mathcal{F}$ for TND}
	\begin{tabular}[t]{ccccc}
		\toprule
		Class& class information &$|\mathcal{O}|$&  $|\mathcal{F}|$&Percentage (\%)\\
		\midrule
		$0$&Farm&1224&1014&88.17\\
		$1$&Forest&1230&91&7.90\\
		$2$&Grass&126&15&1.73\\
		$3$&Impervious&70&20&1.30\\
		$4$&Orchard&8&4&0.52\\
		$5$&Water&32&6&0.34\\
		\bottomrule
	\end{tabular}
	\label{tab: dist2}
\end{table}%




% \begin{table}[ht]
% 	\centering
% 	\caption{Crowd sourcing data: Performance of $\mathcal{C}$ on $\mathcal{T}$}
% 	\begin{tabular}[t]{lc}
% 		\toprule
% 		Performance metric&$\mathcal{C}$ \\
% 		\midrule
% 		$Accuracy$&0.95\\
% 		$Precision$&0.95\\
% 		$Recall$&0.95\\
% 		$F1-score$&0.95\\
% 		\hline
% 	\end{tabular}
% 	\label{tab:perftrain2}
% \end{table}%

\begin{table}[ht]
	\centering
	\caption{Parameter settings for experiments 2,3 and 4}
	\begin{tabular}[t]{crrrrrrr}
		\toprule
		&\multicolumn{4}{c}{Experiments}\\ \cmidrule{2-5}
		Parameter&1&2&3&4\\
		\midrule 
		Chebyshev's parameter ($\mathcal{\tau}$)&3.16&3.16&3.16&3.16\\
		Maximum probability limit ($H$)&2&3&3&4\\
		Support ($S$)&0.1&0.1&0.1&0.1\\
		Confidence ($C$)&0.1&0.1&0.1&0.1\\
		Termination parameter ($\omega$)&0.25&0.25&0.25&0.25\\
		Termination parameter ($\beta$)&0.1&0.1&0.1&0.1\\
		Termination parameter ($\eta$)&0.1&0.1&0.1&0.1\\
		Prediction confidence ($\gamma$)& 0.6&0.6&0.6&0.4\\
		\bottomrule 
	\end{tabular}
	\label{tab: param2}
\end{table}%



% \begin{table}[ht]
% 	\centering
% 	\caption{Classwise data distribution of $\mathcal{F}$ for Crowd sourcing data}
% 	\begin{tabular}[t]{lcc}
% 		\toprule
% 		&Number of instances& Percentage (\%)\\
% 		\midrule
% 		$0$&1014&88.17\\
% 		$1$&91&7.9\\
% 		$2$&15&1.73\\
% 		$3$&20&1.3\\
% 		$4$&4&0.52\\
% 		$5$&6&0.34\\
% 		\hline
% 	\end{tabular}
% 	\label{tab: flaggeddist2}
% \end{table}%


\begin{table}[ht]
	\centering
	\caption{Confusion matrix for performance of $\mathcal{C}$ on $\mathcal{O}$ for crowd sourcing data}
\begin{tabular}[t]{ccccccc}
		\toprule
		&\multicolumn{6}{c}{Predicted class}\\ \cmidrule{2-7}
		True class&0&1&2&3&4&5\\
		\midrule
		$0$&0&1087&11&123&0&3\\
		$1$& 0&1126&0&4&0&0\\
		$2$&0&6&57&7&0&0\\
		$3$&0&13&1&112&0&0\\
		$4$&0&7&0&0&1&0\\
		$5$&0&4&0&3&0&25\\
		\bottomrule
	\end{tabular}
	\label{tab:oldclassifier2}
\end{table}%


\begin{table}[ht]
	\centering
	\caption{Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for TND}
	\begin{tabular}[t]{ccccccc}
		\toprule
		&\multicolumn{6}{c}{Predicted class}\\ \cmidrule{2-7}
		True class&0&1&2&3&4&5\\
		\midrule
		$0$&1082&109&1&29&0&3\\
		$1$&72&1054&0&4&0&0\\
		$2$&13&1&53&3&0&0\\
		$3$&19&1&0&106&0&0\\
		$4$&3&4&0&0&1&0\\
		$5$&2&2&0&3&0&25\\
		\bottomrule
	\end{tabular}
	\label{tab:newclassifier2}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for TND}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.51&0.90\\
		Precision&0.27&0.90\\
		Recall&0.51&0.90\\
		F_{1}-$\text{score}$&0.35&0.90\\
		\bottomrule
	\end{tabular}
	\label{tab:comp2}
\end{table}%
% \begin{table}[ht]
% 	\centering
% 	\caption{Initial and Final distribution of $F$ for Crowd sourcing data}
% 	\begin{tabular}[t]{lcc}
% 		\toprule
% 		&Initial& Final\\
% 		\midrule
% 		$0$&1014&43\\
% 		$1$&91&20\\
% 		$2$&15&3\\
% 		$3$&20&2\\
% 		$4$&4&2\\
% 		$5$&6&4\\
% 		\hline
% 	\end{tabular}
% 	\label{tab: firstandlast}
% \end{table}%



% \begin{table}[ht]
% 	\centering
% 	\caption{Confusion matrix for performance of $\mathcal{C}$ on $\mathcal{O}$ for crowd sourcing data}
% 	\begin{tabular}[t]{lccccccc}
% 		\toprule
% 		\multicolumn{8}{c}{Predicted}\\
% 		&&0&1&2&3&4&5\\
% 		\midrule
% 		\multirow{8}{*}{True}&$0$&0&1087&11&123&0&3\\
% 		&$1$& 0&1126&0&4&0&0\\
% 		&$2$&0&6&57&7&0&0\\
% 		&$3$&0&13&1&112&0&0\\
% 		&$4$&0&7&0&0&1&0\\
% 		&$5$&0&4&0&3&0&25\\
% 		\hline
% 	\end{tabular}
% 	\label{tab:oldclassifier2}
% \end{table}%


\begin{table}[ht]
	\centering
	\caption{Confusion matrix for performance of $\mathcal{C}_{new}$ on $\mathcal{O}$ for crowd sourcing data}
	\begin{tabular}[t]{lccccccc}
		\toprule
		\multicolumn{8}{c}{Predicted}\\
		&&0&1&2&3&4&5\\
		\midrule
		\multirow{8}{*}{True}&$0$&1082&109&1&29&0&3\\
		&$1$&72&1054&0&4&0&0\\
		&$2$&13&1&53&3&0&0\\
		&$3$&19&1&0&106&0&0\\
		&$4$&3&4&0&0&1&0\\
		&$5$&2&2&0&3&0&25\\
		\hline
	\end{tabular}
	\label{tab:newclassifier2}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for TND}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.51&0.90\\
		Precision&0.27&0.90\\
		Recall&0.51&0.90\\
		F_{1}-$\text{score}$&0.35&0.90\\
		\bottomrule
	\end{tabular}
	\label{tab:comp2}
\end{table}%


\section{Analysis on HAR data} \label{HAR}

The open world data contains data from all the classes out of which  classes \textit{2} and \textit{6} were randomly selected to be considered as the unknown classes and the remaining as the known classes. The distribution of the data before and after the identification stage is displayed in Table \ref{tab: flaggeddist4}. We see that 1990 out of 2839 instances present in $\mathcal{O}$ are flagged, out of which about 96\% of the them belong to the unknown classes. We proceed forward and apply Algorithm \ref{alg:ARM} based on the parameters specified in Table \ref{tab: param2}. This algorithm successfully discovered the two unknown classes and assign the identified instances into two new classes. We further evaluate the quality of the categorization by providing a confusion matrix which is displayed in Table \ref{tab:newclassifier4}. Based on the results from this table it is evident that nearly 90\% of observations belonging to class \textit{2} are classified correctly and the majority of the remaining instances are misclassified as class \textit{3} as class \textit{2} (walking upstairs) exhibit more similarity to class \textit{3} (walking downstairs) compared to other classes. Similarly, 97.5\% of observations belonging to class \textit{6} are classified correctly and the major portion of the remaining instances are misclassified as class \textit{4} as class \textit{6} (laying) is more similar to class \textit{4} (sitting). The overall accuracy of the classifier increases from 24\% to 93\% and the information regarding other performance metrics is provided in Table \ref{tab:comp2}. This experiment demonstrates the successful working of the proposed on data containing two unknown classes.



\begin{table}[ht]
	\centering
	\caption{Classwise data distribution of $\mathcal{F}$ for HAR data}
	\begin{tabular}[t]{ccccc}
		\toprule
         Class& Class information&$|\mathcal{O}|$&  $|\mathcal{F}|$&Percentage (\%)\\
		\midrule
		$1$&Walking&196&27&1.35\\
		$2$&Walking upstairs&917&748&37.58\\
		$3$&Walking downstairs&149&10&0.50\\
		$4$&Sitting&175&13&0.65\\
		$5$&Standing&211&30&1.50\\
		$6$&Laying&1191&1162&58.39\\
		\bottomrule
	\end{tabular}
	\label{tab: flaggeddist4}
\end{table}%


% \begin{table}[ht]
% 	\centering
% 	\caption{Parameters setting for Algorithm \ref{alg:ARM} - HAR data}
% 	\begin{tabular}[t]{lcc}
% 		\toprule
% 		Parameter&Value\\
% 		\midrule 
% 		Maximum probability limit ($H$)&3\\
% 		Support ($S$)&0.1\\
% 		Confidence ($C$)&0.1\\
% 		Termination parameter ($\omega$)&0.25\\
% 		Termination parameter ($\beta$)&0.1\\
% 		Prediction confidence ($\gamma$) &0.6\\
% 		Number of iterations ($k$)&3\\
% 		\bottomrule 
% 	\end{tabular}
% 	\label{tab: param2}
% \end{table}%

\begin{table}[ht]
	\centering
	\caption{Confusion matrix for performance of $\mathcal{C}$ on $O$ for HAR data}
	\begin{tabular}[t]{ccccccc}
		\toprule
		&\multicolumn{6}{c}{Predicted class}\\ \cmidrule{2-7}
		True class&1&2&3&4&5&6\\
		\midrule
		$1$&194&0&1&1&0&0\\
		$2$&209&0&605&0&103&0\\
		$3$&8&0&140&0&1&0\\
		$4$&0&0&0&163&12&0\\
		$5$&0&0&7&9&195&0\\
		$6$&1049&0&3&99&40&0\\
		\bottomrule
	\end{tabular}
	\label{tab:oldclassifier4}
\end{table}%
\begin{table}[ht]
	\centering
    \caption{Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for HAR data}
	\begin{tabular}[t]{ccccccc}
		\toprule
		&\multicolumn{6}{c}{Predicted class}\\ \cmidrule{2-7}
		True class&1&2&3&4&5&6\\
		\midrule
		$1$&167&21&0&0&0&8\\
		$2$&2&822&92&0&1&0\\
		$3$&7&9&133&0&0&0\\
		$4$&0&0&0&162&13&0\\
		$5$&0&7&0&10&194&0\\
		$6$&0&1&0&34&2&1154\\
		\bottomrule
	\end{tabular}
	\label{tab:newclassifier4}
\end{table}%

% \begin{table}[!t]
% 	\centering
% 	\caption{Confusion matrix for performance of $\mathcal{C}_{new}$ on $\mathcal{O}$ for HAR data}
% 	\begin{tabular}[t]{lccccccc}
% 		\toprule
% 		\multicolumn{8}{c}{Predicted}\\
% 		&&1&2&3&4&5&6\\
% 		\midrule
% 		\multirow{8}{*}{True}&
% 		$1$&167&21&0&0&0&8\\
% 		&$2$&2&822&92&0&1&0\\
% 		&$3$&7&9&133&0&0&0\\
% 		&$4$&0&0&0&162&13&0\\
% 		&$5$&0&7&0&10&194&0\\
% 		&$6$&0&1&0&34&2&1154\\
% 		\bottomrule
% 	\end{tabular}
% 	\label{tab:newclassifier4}
% \end{table}%

\begin{table}[ht]
	\centering
	\caption{Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for HAR data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.24&0.93\\
		Precision&0.09&0.94\\
		Recall&0.24&0.93\\
		F_{1}-$\text{score}$&0.12&0.93\\
		\bottomrule
	\end{tabular}
	\label{tab:comp4}
\end{table}%

% \begin{table}[!t]
% 	\centering
% 	\caption{Initial and Final distribution of $F$ for HAR data}
% 	\begin{tabular}[t]{lcc}
% 		\toprule
% 		&Initial&Final\\
% 		\midrule
% 		$1$&27&1\\
% 		$2$&748&7\\
% 		$3$&10&1\\
% 		$4$&13&13\\
% 		$5$&30&23\\
% 		$6$&1162&8\\
% 		\bottomrule
% 	\end{tabular}
% 	\label{tab: firstandlast4}
% \end{table}%


\section{Analysis on MNIST data} \label{digit}
The open world data contains observations belonging to all the digits \textit{0} to \textit{9}, out which digits \textit{1,5} and \textit{8} are considered as the unknown classes and the remaining digits as known classes. The distribution of the open world data and the flagged data is displayed in Table \ref{tab: dist}. From the table, it is evident that about 86\% of the instances in $\mathcal{O}$ are flagged as belonging unknown classes. Furthermore, more than 80\% of the identified instances in $\mathcal{F}$ belong to the unknown classes. Since the criteria to proceed forward is met, we apply Algorithm \ref{alg:ARM} on $\mathcal{F}$ using the parameters specified in Table \ref{tab: param2}. From the results, all the three unknown classes are discovered and the quality of the categorization is displayed in Table \ref{tab:newclassifier}. About 79\% of observations belonging to class \textit{1}, 8\% of the observations belonging to class \textit{5} and 73\% of the observations belonging to class \textit{8} are classified correctly. The performance of the latest classifier on class $\textit{5}$ is poor compared to other unknown classes due to the lack of a common pattern across majority of the observations belonging to class \textit{5}. Furthermore, only few instances possess a similarity pattern and are identified by the Algorithm \ref{alg:ARM}. Hence, the classifier has insufficient observations to learn from and resulted in performing poorly on that particular class. However, it is interesting to note that, for class \textit{1}, the majority of the misclassified instances are predicted as class \textit{7}, and the reason is that digit \textit{1} possess similar pixel arrangement with digit \textit{7} and this similarity resulted in the misclassification. Similarly, digits \textit{5} and \textit{8} are more similar to digit \textit{3} and the results explain the same as the majority of the instances that belong to digits \textit{5} and \textit{8} are misclassified as digit \textit{3}. Furthermore, the results from this experiment support our hypothesize that the error is informative and that the \emph{residual signature} helps in distinguishing the unknown classes. The final performance of the classifier increases from 48\% to 75\% and other performance metrics are displayed in Table \ref{tab:comp}.


\begin{table}[!t]
	\centering
	\caption{Classwise data distribution of $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{cccc}
		\toprule
		Class&  $|\mathcal{O}|$&  $|\mathcal{F}|$&Percentage (\%)\\
		\midrule
		$0$&435&59&1.71\\
		$1$&1109&1104&32.09\\
		$2$&396&78&2.26\\
		$3$&433&81&2.35\\
		$4$&425&98&2.84\\
		$5$&892&790&22.96\\
		$6$&422&76&2.20\\
		$7$&454&79&2.29\\
		$8$&999&988&28.72\\
		$9$&435&87&2.52\\
		\bottomrule
	\end{tabular}
	\label{tab: dist}
\end{table}%


\begin{table}[ht]
	\centering
	\caption{Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy &0.48&0.75\\
		Precision&0.28&0.73\\
		Recall&0.48&0.75\\
		F_{1}-$\text{score}$&0.34&0.72\\
		\bottomrule
	\end{tabular}
	\label{tab:comp}
\end{table}%



\begin{table}[ht]
	\centering
	\caption{Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{ccccccccccc}
		\toprule
		&\multicolumn{8}{c}{Predicted class}\\ \cmidrule{2-11}
		True class&0&1&2&3&4&5&6&7&8&9\\
		\midrule
		$0$&410&0&1&0&1&0&0&0&23&0\\
		$1$&0&873&10&2&4&6&4&1&207&2\\
		$2$&0&6&363&2&3&0&0&2&20&0\\
		$3$&0&2&5&400&1&6&0&5&12&2\\
		$4$&3&2&1&0&394&14&2&2&0&7\\
		$5$&13&6&9&387&34&70&28&7&284&54\\
		$6$&1&0&0&0&3&0&403&0&15&0\\
		$7$&0&9&6&1&2&22&0&410&0&4\\
		$8$&5&24&39&67&17&31&10&6&735&65\\
		$9$&0&1&1&5&7&28&0&3&3&387\\
		\bottomrule
	\end{tabular}
	\label{tab:newclassifier}
\end{table}%

% \begin{table}[ht]
% 	\centering
% 	\caption{Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
% 	\begin{tabular}[t]{ccccccccccc}
% 		\toprule
% 		&\multicolumn{8}{c}{Predicted class}\\ \cmidrule{2-11}
% 		True class&0&1&2&3&4&5&6&7&8&9\\
% 		\midrule
% 		$0$&431&0&3&0&0&0&1&0&0&0\\
% 		$1$&0&0&359&244&17&0&86&389&0&14\\
% 		$2$&1&0&387&1&3&0&1&3&0&0\\
% 		$3$&0&0&11&415&0&0&0&3&0&4\\
% 		$4$&3&0&2&0&406&0&1&2&0&11\\
% 		$5$&43&0&32&573&51&0&68&11&0&114\\
% 		$6$&1&0&1&0&3&0&417&0&0&0\\
% 		$7$&0&0&6&0&0&0&0&439&0&0\\
% 		$8$&23&0&286&455&26&0&43&6&0&160\\
% 		$9$&0&0&1&7&5&0&1&4&0&417\\
% 		\bottomrule
% 	\end{tabular}
% 	\label{tab:newclassifier}
% \end{table}%


% \begin{table}[ht]
% 	\centering
% 	\caption{Class wise data distribution of $F$ for MNIST data}
% 	\begin{tabular}[t]{lcc}
% 		\toprule
% 		&Number of instances& Percentage (\%)\\
% 		\hline
% 		$0$&192&2.07\\
% 		$1$&82&0.88\\
% 		$2$&268&2.89\\
% 		$3$&315&3.39\\
% 		$4$&232&2.50\\
% 		$5$&298&3.21\\
% 		$6$&3823&41.25\\
% 		$7$&4057&43.77\\
% 		\hline
% 	\end{tabular}
% 	\label{tab: flaggeddist}
% \end{table}%

\chapter{Sensitivity analysis}
\section{Introduction}
Given the presence of different parameters that govern the functioning of the methodology, it is imperative to analyze the impact of change in these parameter values on the performance of the methodology. The following are the parameters that we considered for the sensitivity analysis.
\begin{itemize}
	\item Number of known classes ($|\mathcal{K}|$)
	\item Chebyshev’s parameter ($\mathcal{\tau}$)
	\item Maximum probability parameter ($H$)
	\item Quality of the classifier
	\end{itemize}
To maintain consistency, we conduct all the analyses on the MNIST data as it is one of the standard data sets available.

\section{Sensitivity analysis: Number of known classes} \label{known}
\paragraph{Purpose}
The goal of this analysis is to analyze the impact of number of known classes on the overall performance of the methodology. 

\paragraph{Hypothesis}
As the number of known classes increases, the dimensionality of the probabilistic space increases and provides more detail for categorization.

\paragraph{Experimental setup}
Three experiments, by varying the number of known classes at 2,5 and 8 are conducted. Furthermore, data corresponding to digits \textit{8} and \textit{9} are considered as the unknown classes for all the experiments. Figures 1 and 2 are the images corresponding to digits 8 and 9 respectively. Also, random forest (RF) is the classifier used for all the experiments conducted. The parameter settings associated with Algorithm \ref{alg:JSD} and Algorithm \ref{alg:ARM} and the details about each experiment is provided in Table \ref{tab:s1p}.

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis 1: Experimental setup}
		\begin{tabular}[t]{crrrrrr}
		\toprule
		&\multicolumn{3}{c}{Experiments}\\ \cmidrule{2-4}
		Parameter&1&2&3\\
		\midrule 
		Number of unknown classes&2&2&2\\
		Number of known classes&2&5&8\\
		Classifier&RF&RF&RF\\
		Chebyshev's parameter ($\mathcal{\tau}$)&3.16&3.16&3.16\\
		Maximum probability limit ($H$)&1&3&4\\
% 		Support ($S$)&0.1&0.1&0.1\\
% 		Confidence ($C$)&0.1&0.1&0.1\\
		Termination parameter ($\omega$)&0.25&0.25&0.25\\
		Termination parameter ($\beta$)&0.1&0.1&0.1\\
		Termination parameter ($\eta$)&0.1&0.1&0.1\\
		Prediction confidence ($\gamma$) &0.6&0.6&0.4\\
		\bottomrule 
	\end{tabular}
	\label{tab:s1p}
\end{table}%
\subsection{Experiment-1}
The training data considered for this experiment contains classes \textit{0} and \textit{1} and the open world data contains two new classes \textit{8} and \textit{9} along with the known classes.  
% For all the experiments in this analysis, we consider $\mathcal{O}$ to contain 50\% of the data that belongs to known classes and 50\% of the data that belongs to unknown classes. 

\begin{table}[!t]
	\centering
	\caption{Sensitivity analysis-1 (Experiment-1): Classwise data distribution of $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{ccc}
		\toprule
		Class&  $|\mathcal{O}|$&  $|\mathcal{F}|$\\
		\midrule
		$0$&937&49\\
		$1$&1063&38\\
		$8$&1005&982\\
		$9$&995&972\\
		\bottomrule
	\end{tabular}
	\label{tab:s1e1}
\end{table}%

The first step is the identification stage where we apply Algorithm \ref{alg:JSD} on $\mathcal{O}$ to identify the data instances belonging to the unknown classes. The results of the identification stage indicate that about 50\% of the instances in $\mathcal{O}$ are identified (flagged) as potentially not belonging to the known classes. From Table \ref{tab:s1e1}, we further evaluate the quality of the identified instances by analyzing the distribution of the flagged instances in $\mathcal{F}$, and we see that about 96\% of the flagged instances belong to the unknown classes. Since we have more than 10\% of the instances as flagged, we move forward to the next step which is the categorization of flagged instances. Algorithm \ref{alg:ARM} is applied on $\mathcal{F}$ and the results from Table \ref{tab:s1e1cf} indicate that Algorithm \ref{alg:ARM} discovered a single unknown class as opposed to two unknown classes. Furthermore, we also see that about 98\% of the instances belonging to class \textit{8} are correctly classified whereas instances that belong to \textit{9} are completely misclassified. Table \ref{tab:s1e1c} provides a comparison of performance between the old and new classifier and we see improvement in the overall performance of the classifier.

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-1 (Experiment-1):Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.49&0.73\\
		Precision&0.25&0.61\\
		Recall&0.49&0.73\\
		F_{1}-$\text{score}$&0.33&0.65\\
		\bottomrule
	\end{tabular}
	\label{tab:s1e1c}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-1 (Experiment-1):Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{crrrrr}
		\toprule
		&\multicolumn{4}{c}{Predicted class}\\
		\cmidrule{2-5}
		True class&0&1&8&9\\
		\midrule
		$0$&928&0&9&0\\
		$1$&0&1024&39&0\\
		$8$&7&9&989&0\\
		$9$&14&4&977&0\\
		\bottomrule
	\end{tabular}
	\label{tab:s1e1cf}
\end{table}%


\subsection{Experiment -2}
In the second experiment, we increase the number of training classes to 5, but the number of unknown classes remain the same. The training data $\mathcal{T}$ includes images corresponding to digits \textit{0,1,2,3} and \textit{4} and $\mathcal{O}$ contains data that belong to digits \textit{0,1,2,3,4,8} and \textit{9}. The same procedure similar to the first experiment is followed and the results corresponding to the identification phase are displayed in Table \ref{tab:s1e2}. From the table, we see that about 46\% of instances that are identified belong to the unknown classes. From Table \ref{tab:s1e1}, we further evaluate the quality of the identified instances by analyzing the distribution of the flagged instances in $\mathcal{F}$, and we see that about 88\% of the flagged instances belong to the unknown classes. Since we have more than 10\% of the instances as flagged, we move forward to the next step which is the categorization of flagged instances. Algorithm \ref{alg:ARM} is applied on $\mathcal{F}$ and the results from Table \ref{tab:s1e1cf} indicate that Algorithm \ref{alg:ARM} discovered both the unknown classes successfully. However, we see that 64\% of class \textit{8} are correctly classified, while the remaining 36\% of them are spread across the other classes, of which majority of them are wrongly classified as class \textit{9}. Similarly, for class \textit{9}, 73\% of them are correctly classified and the majority of them misclassified as class \textit{4}.  The overall performance of the final classifier is provided in Table \ref{tab:s1e1c} and we see a considerable improvement in the performance.

\begin{table}[!t]
	\centering
	\caption{Sensitivity analysis-1 (Experiment-2): Classwise data distribution of $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{ccc}
		\toprule
		Class&  $|\mathcal{O}|$&  $|\mathcal{F}|$\\
		\midrule
		$0$&403&51\\
		$1$&430&40\\
		$2$&387&55\\
		$3$&399&55\\
		$4$&381&62\\
		$8$&1005&989\\
		$9$&995&595\\
		\bottomrule
	\end{tabular}
	\label{tab:s1e2}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-1 (Experiment-2): Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.49&0.81\\
		Precision&0.30&0.83\\
		Recall&0.0.49&0.81\\
	F_{1}-$\text{score}$&0.0.36&0.81\\
		\bottomrule
	\end{tabular}
	\label{tab:s1e2c}
\end{table}%


\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-1 (Experiment-2): Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{crrrrrrrr}
		\toprule
		&\multicolumn{7}{c}{Predicted class}\\ 
		\cmidrule{2-8}
		True class&0&1&2&3&4&8&9\\
		\midrule
		$1$&0&421&2&2&2&3&0\\
		$2$&3&0&346&0&5&33&0\\
		$3$&0&0&2&351&0&36&10\\
		$4$&1&1&1&0&360&0&18\\
		$8$&6&36&22&27&21&641&252\\
		$9$&9&7&10&17&218&3&731\\
		\bottomrule
	\end{tabular}
	\label{tab:s1e2cf}
\end{table}%

% The parameter setting used for this experiment, corresponding to Algorithm \ref{alg:ARM} is displayed in Table \ref{tab:s1p}.
% The initial and final model performance on $\mathcal{O}$ is provided in Table \ref{tab:s1e2c} and there is a considerable improvement in the performance of the final classifier. 
% Detailed information about the categorization task of the methodology is provided in Table \ref{tab:s1e2cf}. From this table, we see that the methodology correctly identified the two unknown classes and also group the data instances more accurately compared to the first experiment. The reason for the improvement is the inclusion of more number of known classes in the training data.

\subsection{Experiment-3}\label{mnist}
In the final experiment, we increase the number of training classes to 8 and the number of unknown classes remain the same. The training data $\mathcal{T}$ includes images corresponding to digits \textit{0,1,2,3,4,5,6,7} and $\mathcal{O}$ contains data that belong to all the digits \textit{0} to \textit{9}. The result of the identification phase is displayed in Table \ref{tab:s1e3} and we can see that 
more than 50\% of instances that are identified belong to the unknown classes. From Table \ref{tab:s1e1}, we further evaluate the quality of the identified instances by analyzing the distribution of the flagged instances in $\mathcal{F}$, and we see that about 84\% of the flagged instances belong to the unknown classes. Since we have more than 10\% of the instances as flagged, we move forward to the next step which is the categorization of flagged instances. Algorithm \ref{alg:ARM} is applied on $\mathcal{F}$ and the results from Table \ref{tab:s1e1cf} indicate that Algorithm \ref{alg:ARM} discovered both the unknown classes successfully. However, we see that 74\% of class \textit{8} are correctly classified, while the remaining 26\% of them are spread across the other classes, of which majority of them are wrongly classified as class \textit{3}. Similarly, for class \textit{9}, 79\% of them are correctly classified and the majority of the remaining instances are misclassified as class \textit{4}.  The overall performance of the final classifier is provided in Table \ref{tab:s1e1c} and we see a considerable improvement in the performance.

\begin{table}[!t]
	\centering
	\caption{Sensitivity analysis-1 (Experiment-3): Classwise data distribution of $\mathcal{O}$ and $\mathcal{F}$ for MNIST data}
	\begin{tabular}[t]{ccc}
		\toprule
		Class&  $|\mathcal{O}|$&  $|\mathcal{F}|$\\
		\midrule
		$0$&247&41\\
		$1$&283&20\\
		$2$&236&65\\
		$3$&268&63\\
		$4$&239&54\\
		$5$&230&70\\
		$6$&231&45\\
		$7$&266&45\\
		$8$&1005&1001\\
		$9$&995&963\\
		\hline
	\end{tabular}
	\label{tab:s1e3}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-1 (Experiment-3): Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
		\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.48&0.86\\
		Precision&0.30&0.88\\
		Recall&0.48&0.86\\
		F_{1}-$\text{score}$&0.     36&0.87\\
		\bottomrule
	\end{tabular}
	\label{tab:s1e3c}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-1 (Experiment-3): Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{crrrrrrrrrr}
		\toprule
		&\multicolumn{8}{c}{Predicted class}\\ \cmidrule{2-11}
		True class&0&1&2&3&4&5&6&7&8&9\\
		\midrule
		$1$&0&280&1&1&1&0&0&0&0&0\\
		$2$&3&2&221&1&3&0&2&2&2&0\\
		$3$&0&0&4&243&0&0&1&6&8&6\\
		$4$&0&1&0&0&227&0&0&1&0&10\\
		$5$&2&1&0&2&0&212&3&0&2&8\\
		$6$&3&0&0&0&0&1&227&0&0&0\\
		$7$&1&1&7&0&2&1&0&251&0&3\\
		$8$&3&21&37&89&14&29&7&5&743&57\\
		$9$&9&3&13&12&121&5&0&27&18&787\\
		\bottomrule
	\end{tabular}
	\label{tab:s1e3cf}
\end{table}%

\paragraph{Conclusion}
The main motive of analysis is to determine the effect of the number of training classes on the proposed framework. In this regard, we carried out different experiments with varying the number of training classes ranging from 2 to 8. Results strongly suggest that as the number of known classes increases, the ability to identify and discriminate the unknown classes also improves. However, it is interesting to note from Table \ref{tab:s1t} that, in all the experiments conducted, the performance of the methodology corresponding to the identification task remains consistent. The only difference in the performance is noticed with the categorization task. In the first experiment, there are insufficient number of known classes to capture the similarity patterns existing in the data and both the unknown classes exhibited similarity to the same known class. Increase in the number of training classes, resulted in a unique similarity pattern to each unknown class and resulted in better categorization in the second and third experiments. However, we see some discrepancy in the prediction distribution for the unknown classes and the overall misclassification rate associated with the categorization of the unknown classes decreases as seen in Table \ref{tab:s1t}. Furthermore, from the same table, we see that the overall performance of the final classifier also increases as the number of known classes increases.

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis 1: Combined results of all experiments}
		\begin{tabular}[t]{crrrrrr}
		\toprule
		&\multicolumn{3}{c}{Experiments}\\ \cmidrule{2-4}
		Parameter&1&2&3\\
		\midrule 
		Percentage of data identified&50&46&50\\
		Number of unknown classes discovered&1&2&2\\
		Percentage misclassified for class \textit{8}&2&36&26\\
		Percentage misclassified for class \textit{9}&100&27&21\\
		Final F_{1}-$\text{score}$ &0.65&0.81&0.87\\
		\bottomrule 
	\end{tabular}
	\label{tab:s1t}
\end{table}%

\section{Sensitivity analysis: Chebyshev’s parameter}
\paragraph{Purpose}
One of the critical parameters associated with the framework is the Chebyshev’s parameter ($\tau$) and it governs the way the methodology works and plays a major role in the identification phase. It is imperative to choose an appropriate value as any fallacious results that occur in this stage will subsequently lead to undesirable results in the second stage and ultimately lead to overall failure of the framework.  Hence, it is imperative to assign a proper value to $\tau$ to achieve desired results.

\paragraph{Hypothesis}
The higher the value of $\tau$, the fewer will be the number of instances flagged. On the other hand, a very low value of $\tau$ might cause more instances from the known classes be flagged which is again not desirable. The methodology fails for extreme values of the Chebyshev's parameter $\tau$.
\paragraph{Experimental setup}
To maintain consistency, all the experiments are conducted on the MNIST data, where the training data $\mathcal{O}$ includes data corresponding to digits \textit{0} to \textit{7} and the open world data $\mathcal{O}$ contains data that belongs to all the digits \textit{0} to \textit{9}. The only varying parameter for this analysis is $\tau$ and is set to 1.4, 2.0 and 4.47 for the first, second and third experiment respectively. The details about the other parameters associated with the methodology is provided in Table \ref{tab:s2p}.

% \begin{table}[!t]
% 	\centering
% 	\caption{Sensitivity analysis-1}
% 	\begin{tabular}[t]{lcc}
% 		\toprule
% 		Experiment&$\mathcal{\alpha}$&$\mathcal{\tau}$\\
% 		\midrule
% 		Experiment-1&0.5&1.414\\
% 		Experiment-2&0.75&2\\
% 		Experiment-3&0.95&4.47\\
% 		\bottomrule
% 	\end{tabular}
% 	\label{tab:s2e}
% \end{table}%


\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis 2: Experimental setup}
		\begin{tabular}[t]{crrrrrr}
		\toprule
		&\multicolumn{3}{c}{Experiments}\\ \cmidrule{2-4}
		Parameter&1&2&3\\
		\midrule 
		Classifier&RF&RF&RF\\
		Chebyshev's parameter ($\mathcal{\tau}$)&1.414&2&4.47\\
		Maximum probability limit ($H$)&4&4&4\\
% 		Support ($S$)&0.1&0.1&0.1\\
% 		Confidence ($C$)&0.1&0.1&0.1\\
		Termination parameter ($\omega$)&0.25&0.25&0.25\\
		Termination parameter ($\beta$)&0.1&0.1&0.1\\
		Termination parameter ($\eta$)&0.1&0.1&0.1&\\
		Prediction confidence ($\gamma$) &0.4&0.4&0.4\\
		\bottomrule 
	\end{tabular}
	\label{tab:s2p}
\end{table}%


%2614

\subsection{Experiment-1}
The first step is the identification stage where we apply Algorithm \ref{alg:JSD} on $\mathcal{O}$, using the Chebyshev's parameter ($\mathcal{\tau}$) that is set to a value of 1.414. The results of the identification stage indicate that about 65\% of the instances in $\mathcal{O}$ are identified (flagged) as belonging to the unknown classes. From Table \ref{tab:s2e1}, we analyze the distribution of the flagged instances in $\mathcal{F}$, and we see that about 76\% of them belong to the unknown classes. Since we have more than 10\% of the instances as flagged, we move forward to the next step which is the categorization of flagged instances. Algorithm \ref{alg:ARM} is applied on $\mathcal{F}$ and the results from Table \ref{tab:s2e1cf} indicate that Algorithm \ref{alg:ARM} successfully discovered both the unknown classes. Furthermore, we also see that about 53\% of the instances belonging to class \textit{8} are correctly classified while the remaining are spread across the other classes, of which majority of them are wrongly classified as class \textit{3}. Similarly, for class \textit{9}, 84\% of them are correctly classified and the majority of the remaining instances are misclassified as class \textit{4}.  The overall accuracy of the classifier increases from 48\% to 82\% and the information regarding other performance metrics is provided in Table \ref{tab:s2e1c}.

\begin{table}[!t]
	\centering
	\caption{Sensitivity analysis-2 (Experiment-1): Classwise data distribution of $\mathcal{O}$ and $\mathcal{F}$ for MNIST data}
	\begin{tabular}[t]{ccc}
		\toprule
		Class&  $|\mathcal{O}|$&  $|\mathcal{F}|$\\
		\midrule
		$0$&247&68\\
		$1$&283&34\\
		$2$&236&93\\
		$3$&268&99\\
		$4$&239&82\\
		$5$&230&108\\
		$6$&231&69\\
		$7$&266&66\\
		$8$&1005&1002\\
		$9$&995&994\\
		\bottomrule
	\end{tabular}
	\label{tab:s2e1}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-2 (Experiment-1):Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{crrrrrrrrrr}
		\toprule
		&\multicolumn{8}{c}{Predicted class}\\ \cmidrule{2-11}
		True class&0&1&2&3&4&5&6&7&8&9\\
		\midrule
		$0$&246&0&0&0&0&0&1&0&0&0\\
		$1$&0&280&1&1&1&0&0&0&0&0\\
		$2$&1&2&223&1&5&0&1&1&2&0\\
		$3$&0&0&5&243&0&1&1&6&10&2\\
		$4$&0&1&0&0&224&0&0&1&1&12\\
		$5$&2&1&0&2&0&211&3&0&4&7\\
		$6$&3&0&0&0&0&0&228&0&0&0\\
		$7$&1&1&7&0&1&1&0&249&0&6\\
		$8$&6&54&67&138&16&79&14&5&530&96\\
		$9$&7&4&15&12&74&5&0&24&16&838\\
		\hline
	\end{tabular}
	\label{tab:s2e1cf}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{ Sensitivity analysis-2 (Experiment-1): Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.48&0.82\\
		Precision&0.30&0.84\\
		Recall&0.48&0.82\\
		F_{1}-$\text{score}$&0.36&0.81\\
		\bottomrule
	\end{tabular}
	\label{tab:s2e1c}
\end{table}%

%2502
\subsection{Experiment -2}
The first step is the identification stage where we apply Algorithm \ref{alg:JSD} on $\mathcal{O}$, using the Chebyshev's parameter ($\mathcal{\tau}$) that is set to a value of 2. The results of the identification stage indicate that about 62\% of the instances in $\mathcal{O}$ are identified (flagged) as belonging to the unknown classes. From Table \ref{tab:s2e2}, we analyze the distribution of the flagged instances in $\mathcal{F}$, and we see that about 80\% of them belong to the unknown classes. Since we have more than 10\% of the instances as flagged, we move forward to the next step which is the categorization of flagged instances. Algorithm \ref{alg:ARM} is applied on $\mathcal{F}$ and the results from Table \ref{tab:s2e2cf} indicate that Algorithm \ref{alg:ARM} successfully discovered both the unknown classes. Furthermore, we also see that about 53\% of the instances belonging to class \textit{8} are correctly classified while the remaining are spread across the other classes, of which majority of them are wrongly classified as class \textit{3}. Similarly, for class \textit{9}, 84\% of them are correctly classified and the majority of the remaining instances are misclassified as class \textit{4}. The overall accuracy of the classifier increases from 48\% to 82\% and the information regarding other performance metrics is provided in Table \ref{tab:s2e2c}.

\begin{table}[!t]
	\centering
	\caption{Sensitivity analysis-2 (Experiment-2): Classwise data distribution of $\mathcal{O}$ and $\mathcal{F}$ for MNIST data}
\begin{tabular}[t]{cccc}
		\toprule
		Class&  $|\mathcal{O}|$&  $|\mathcal{F}|$\\
		\midrule
		$0$&247&51\\
		$1$&283&29\\
		$2$&236&76\\
		$3$&268&87\\
		$4$&239&66\\
		$5$&230&90\\
		$6$&231&55\\
		$7$&266&55\\
		$8$&1005&1002\\
		$9$&995&991\\
		\bottomrule
	\end{tabular}
	\label{tab:s2e2}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-2 (Experiment-2): Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{crrrrrrrrrr}
		\toprule
		&\multicolumn{8}{c}{Predicted class}\\ \cmidrule{2-11}
		True class&0&1&2&3&4&5&6&7&8&9\\
		\midrule
		$0$&246&0&0&0&0&0&1&0&0&0\\
		$1$&0&280&2&1&0&0&0&0&0&0\\
		$2$&1&2&223&1&5&0&1&1&2&0\\
		$3$&0&0&5&243&0&1&1&6&10&2\\
		$4$&0&1&0&0&224&0&0&1&1&12\\
		$5$&2&1&0&2&0&211&3&0&4&7\\
		$6$&3&0&0&0&0&0&228&0&0&0\\
		$7$&1&1&7&0&1&1&0&249&0&6\\
		$8$&6&54&67&138&16&79&14&5&530&96\\
		$9$&7&4&15&12&74&5&0&24&16&838\\
		\bottomrule
	\end{tabular}
	\label{tab:s2e2cf}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{ Sensitivity analysis-2 (Experiment-2): Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.48&0.82\\
		Precision&0.30&0.84\\
		Recall&0.48&0.82\\
	F_{1}-$\text{score}$&0.36&0.81\\
		\bottomrule
	\end{tabular}
	\label{tab:s2e2c}
\end{table}%

%2352
\subsection{Experiment -3}
Algorithm \ref{alg:JSD} is applied on $\mathcal{O}$, using the Chebyshev's parameter ($\mathcal{\tau}$) that is set to a value of 4.47. The results of the identification stage indicate that about 59\% of the instances in $\mathcal{O}$ are identified (flagged) as belonging to the unknown classes. From Table \ref{tab:s2e3}, we analyze the distribution of the flagged instances in $\mathcal{F}$, and we see that about 84\% of them belong to the unknown classes. Since we have more than 10\% of the instances as flagged, we move forward to the next step which is the categorization of flagged instances. Algorithm \ref{alg:ARM} is applied on $\mathcal{F}$ and the results from Table \ref{tab:s2e2cf} indicate that Algorithm \ref{alg:ARM} successfully discovered both the unknown classes. Furthermore, we also see that about 53\% of the instances belonging to class \textit{8} are correctly classified while the remaining are spread across the other classes, of which majority of them are wrongly classified as class \textit{3}. Similarly, for class \textit{9}, 85\% of them are correctly classified and the majority of the remaining instances are misclassified as class \textit{4}. The overall accuracy of the classifier increases from 48\% to 82\% and the information regarding other performance metrics is provided in Table \ref{tab:s2e3c}.

\begin{table}[!t]
	\centering
	\caption{Sensitivity analysis-2 (Experiment-3): Classwise data distribution of $\mathcal{O}$ and $\mathcal{F}$ for MNIST data}
	\begin{tabular}[t]{ccc}
		\toprule
		Class&  $|\mathcal{O}|$&  $|\mathcal{F}|$\\
		\midrule
		$0$&247&42\\
		$1$&283&20\\
		$2$&236&57\\
		$3$&268&60\\
		$4$&239&54\\
		$5$&230&66\\
		$6$&231&42\\
		$7$&266&42\\
		$8$&1005&1002\\
		$9$&995&967\\
		\bottomrule
	\end{tabular}
	\label{tab:s2e3}
\end{table}%


\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-2 (Experiment-3): Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{crrrrrrrrrr}
		\toprule
		&\multicolumn{8}{c}{Predicted class}\\ \cmidrule{2-11}
		True class&0&1&2&3&4&5&6&7&8&9\\
		\midrule
		$0$&246&0&0&0&0&0&1&0&0&0\\
		$1$&0&281&1&1&0&0&0&0&0&0\\
		$2$&2&2&224&0&3&0&0&2&3&0\\
		$3$&0&0&6&244&1&2&0&5&9&1\\
		$4$&0&1&0&0&225&0&0&1&1&11\\
		$5$&2&1&0&2&0&215&3&0&1&6\\
		$6$&3&0&0&0&0&0&228&0&0&0\\
		$7$&1&1&7&1&1&0&0&250&0&5\\
		$8$&5&66&67&128&22&73&11&6&530&97\\
		$9$&8&5&14&14&90&6&0&21&16&821\\
		\bottomrule
	\end{tabular}
	\label{tab:s2e3cf}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-2 (Experiment-3): Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.48&0.82\\
		Precision&0.30&0.84\\
		Recall&0.48&0.82\\
		F_{1}-$\text{score}$&0.36&0.81\\
		\bottomrule
	\end{tabular}
	\label{tab:s2e3c}
\end{table}%


\paragraph{Conclusion}
The main motive of this analysis to determine the effect of Chebyshev’s parameter ($\mathcal{\tau}$) on the performance of the methodology. We hypothesized that the number of instances flagged decreases as the value of $\mathcal{\tau}$ increases and the results from Table \ref{tab:s2t} support our hypothesis. Furthermore, it is interesting to note that decrease in the number of flagged instances can be mainly attributed to the instances from the known classes while there is a negligible decrease for the unknown classes. However, from Table \ref{tab:s2t}, we can see that the overall performance of the final classifier in all the three experiments remains consistent. This implies that even when there is difference in the percentage of flagged instances, the overall performance of the framework across all experiments remains consistent. This characteristic of the methodology is desirable as the results show that the framework is robust to the false positives, i.e., the instances that actually belong to the known classes but are identified by the methodology as potentially belonging to the unknown classes.


\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis 2: Combined results of all experiments}
		\begin{tabular}[t]{crrrrrr}
		\toprule
		&\multicolumn{3}{c}{Experiments}\\ \cmidrule{2-4}
		Parameter&1&2&3\\
		\midrule 
		Chebyshev's parameter ($\mathcal{\tau}$)&1.414&2&4.47\\
		Percentage of data identified&65&62&59\\
		Percentage of instances in $\mathcal{F}$ that belong to unknown classes &50&50&49\\ 
		Number of unknown classes discovered&2&2&2\\
		Percentage correctly classified for class \textit{8}&53&53&53\\
		Percentage correctly classified for class \textit{9}&84&84&85\\
		Final F_{1}-$\text{score}$ &0.81&0.81&0.81\\
		\bottomrule 
	\end{tabular}
	\label{tab:s2t}
\end{table}%

\section{Sensitivity analysis: Maximum probability parameter (H)}
\paragraph{Purpose}
Maximum probability parameter (H) is one of the parameters that can have considerable effect on the performance of the framework. This parameter governs the categorization step of the methodology and  decides the size of the itemsets that are generated by Algorithm \ref{alg:ARM}. In this analysis, we determined the performance of the framework by conducting experiments for different values of H. 

\paragraph{Hypothesis}
A very low value of H does not provide enough information to capture the residual patterns existing within the data. On the other hand, a very high value of H will result in a common residual signature across all the unknown classes and makes it difficult to distinguish one another.

\paragraph{Experimental setup}
To maintain consistency, in all the experiments the training data $\mathcal{T}$ includes the classes \textit{0} to \textit{7} and the open world data $\mathcal{O}$ contains data that belongs to all the digits \textit{0} to \textit{9}. Three experiments with different values of H, 1, 4 and 7 are conducted. The details about the parameter settings associated with other parameters are provided in Table \ref{tab:s3p}. Since the parameter H is a part of Algorithm \ref{alg:ARM}, we apply Algorithm \ref{alg:JSD} on $\mathcal{O}$ to determine the set of flagged instances $\mathcal{F}$ and use the same flagged set for all the experiments conducted in this analysis. Th results of identification stage is provided in Table \ref{tab:s3i}. From the results, we see that 
about 59\% of the instances in $\mathcal{O}$ are identified (flagged) as belonging to the unknown classes. Furthermore, 83\% of the flagged instances belong to the unknown classes.
%2929
\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis 3: Experimental setup}
		\begin{tabular}[t]{crrrrrr}
		\toprule
		&\multicolumn{3}{c}{Experiments}\\ \cmidrule{2-4}
		Parameter&1&2&3\\
		\midrule 
		Classifier&RF&RF&RF\\
		Chebyshev's parameter ($\mathcal{\tau}$)&3.16&3.16&3.16\\
		Maximum probability limit ($H$)&1&4&7\\
% 		Support ($S$)&0.1&0.1&0.1\\
% 		Confidence ($C$)&0.1&0.1&0.1\\
		Termination parameter ($\omega$)&0.25&0.25&0.25\\
		Termination parameter ($\beta$)&0.1&0.1&0.1\\
		Termination parameter ($\eta$)&0.1&0.1&0.1\\
		Prediction confidence ($\gamma$) &0.4&0.4&0.4\\
		\bottomrule 
	\end{tabular}
	\label{tab:s3p}
\end{table}%

% \begin{table}[!t]
% 	\centering
% 	\caption{Sensitivity analysis-1}
% 	\begin{tabular}[t]{lc}
% 		\toprule
% 		Experiment&Value of H\\
% 		\midrule
% 		Experiment-1&1\\
% 		Experiment-2&4\\
% 		Experiment-3&7\\
% 		\bottomrule
% 	\end{tabular}
% 	\label{tab:s4e}
% \end{table}%



\begin{table}[!t]
	\centering
	\caption{Sensitivity analysis 3: Classwise data distribution of $\mathcal{O}$ and $\mathcal{F}$ for MNIST data}
	\begin{tabular}[t]{ccc}
		\toprule
		Class&  $|\mathcal{O}|$&  $|\mathcal{F}|$\\
		\midrule
		$0$&368&63\\
		$1$&415&33\\
		$2$&360&96\\
		$3$&409&100\\
		$4$&361&73\\
		$5$&335&105\\
		$6$&362&69\\
		$7$&390&75\\
		$8$&1490&1486\\
		$9$&1510&1443\\
		\bottomrule
	\end{tabular}
	\label{tab:s3i}
\end{table}%



\subsection{Experiment-1}
For this experiment, the value of H is set equal to 1. Algorithm \ref{alg:ARM} is applied on the data and the results for the categorization phase are provided in Table \ref{tab:s3e1cf}. From this table, we see that 3 unknown classes are identified, while the actual number of unknown classes present is 2. Furthermore, 37\% of the instances belonging to class \textit{8} are classified correctly,  39\% of them are misclassified as class \textit{9} and 13\% of them are misclassified as belonging to the third unknown class. On the other hand, 93\% of the instances belonging to class \textit{9} are correctly classified and the remaining are misclassified as other classes, of which only 10 instances are classified as belonging to the \textit{new} class. However, from Table \ref{tab:s4e1c}, we see an improvement in the overall performance of the final classifier compared to the initial classifier.

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-3 (Experiment-1): Confusion matrix for performance of $\mathcal{C}_{new}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{crrrrrrrrrrr}
		\toprule
		&\multicolumn{8}{c}{Predicted class}\\ \cmidrule{2-12}
		True class&0&1&2&3&4&5&6&7&8&9&new\\
		\midrule
		$0$&365&1&0&0&0&0&2&0&0&0&0\\
		$1$&0&441&1&1&0&0&0&0&1&1&0\\
		$2$&3&2&339&0&0&0&1&5&2&7&1\\
		$3$&0&0&3&310&0&0&1&5&85&2&3\\
		$4$&0&2&0&0&289&0&0&1&1&68&0\\
		$5$&2&2&0&1&0&230&5&0&2&4&89\\
		$6$&3&1&0&0&0&1&355&0&0&0&2\\
		$7$&1&1&6&0&0&0&0&375&1&6&0\\
		$8$&6&58&65&4&1&5&13&4&552&581&201\\
		$9$&10&5&7&4&6&0&0&39&29&1400&10\\
		\hline
	\end{tabular}
	\label{tab:s3e1cf}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-3 (Experiment-1): Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.48&0.77\\
		Precision&0.30&0.83\\
		Recall&0.0.48&0.77\\
		F_{1}-$\text{score}$&0.0.36&0.77\\
		\bottomrule
	\end{tabular}
	\label{tab:s4e1c}
\end{table}%


Since the value of H was considered to be 1, only itemsets with size 1 are returned and the categorization of the instances happen based on these itemsets. The results corresponding to the performance of the final classifier is provided in table. From table conf, we can see that, for this particular value of H, 3 new classes were identified by the framework as opposed to 2 unknown classes. This can be considered as the failure of the framework and is due to the very low value being set to the parameter H.


\subsection{Experiment-2}
For this experiment, the value of H is set equal to 4. Algorithm \ref{alg:ARM} is applied on the data and the results for the categorization phase are provided in Table \ref{tab:s3e2cf}. From this table, we see that exactly two unknown classes are discovered. Furthermore, 66\% of the instances belonging to class \textit{8} are classified correctly and majority of the remaining instances are misclassified as belonging to class \textit{3} and class \textit{9}. On the other hand, 86\% of the instances belonging to class \textit{9} are correctly classified and majority of the remaining instances are misclassified as class \textit{4}. The overall accuracy of the classifier increases from 48\% to 86\% and the information regarding other performance metrics is provided in Table \ref{tab:s4e2c}.



\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-3 (Experiment-2):Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{crrrrrrrrrr}
		\toprule
		&\multicolumn{8}{c}{Predicted class}\\ \cmidrule{2-11}
		True class&0&1&2&3&4&5&6&7&8&9\\
		\midrule
		$0$&365&0&0&1&0&0&2&0&0&0\\
		$1$&0&412&2&1&1&0&0&0&1&0\\
		$2$&3&2&341&0&2&0&1&4&7&0\\
		$3$&0&0&5&369&0&2&1&7&16&9\\
		$4$&0&2&0&0&342&0&2&1&4&10\\
		$5$&2&1&0&4&0&303&6&0&5&14\\
		$6$&2&1&0&0&0&2&357&0&0&0\\
		$7$&0&1&9&0&3&0&0&372&1&4\\
		$8$&9&58&72&134&20&74&17&4&986&116\\
		$9$&15&6&16&18&93&6&1&31&18&1306\\
		\bottomrule
	\end{tabular}
	\label{tab:s3e2cf}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{ Sensitivity analysis-3 (Experiment-2): Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.48&0.86\\
		Precision&0.30&0.87\\
		Recall&0.48&0.86\\
	F_{1}-$\text{score}$&0.36&0.86\\
		\bottomrule
	\end{tabular}
	\label{tab:s4e2c}
\end{table}%
\subsection{Experiment-3} \label{S3E3}
For this experiment, the value of H is set equal to 7. Algorithm \ref{alg:ARM} is applied on the data and the results for the categorization phase are provided in Table \ref{tab:s3e2cf}. From this table, we see that exactly two unknown classes are discovered. However, only 13\% of the instances belonging to class \textit{8} are correctly classified correctly and 77\% of the instances are misclassified as belonging to class \textit{9}. On the other hand, 90\% of the instances belonging to class \textit{9} are correctly classified and majority of the remaining instances are misclassified as class \textit{4} and class \textit{7}. The overall accuracy of the classifier increases from 48\% to 70\% and the information regarding other performance metrics is provided in Table \ref{tab:s4e3c}.

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-3 (Experiment-3): Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{crrrrrrrrrr}
		\toprule
		&\multicolumn{8}{c}{Predicted class}\\ \cmidrule{2-11}
		True class&0&1&2&3&4&5&6&7&8&9\\
		\midrule
		$0$&333&0&1&1&0&0&0&0&0&33\\
		$1$&0&399&2&0&0&0&0&0&14&0\\
		$2$&3&2&304&0&1&0&1&1&26&22\\
		$3$&0&0&2&368&0&3&1&3&13&19\\
		$4$&0&0&0&0&307&0&0&0&26&28\\
		$5$&2&2&1&2&2&287&2&0&14&23\\
		$6$&2&1&0&0&0&2&357&0&0&0\\
		$7$&0&1&6&0&0&0&0&349&17&17\\
		$8$&3&21&28&50&4&21&7&0&202&1154\\
		$9$&1&4&1&17&24&5&0&28&73&1357\\
		\bottomrule
	\end{tabular}
	\label{tab:s4e3cf}
\end{table}%


\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-3 (Experiment-3): Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.48&0.70\\
		Precision&0.30&0.71\\
		Recall&0.48&0.71\\
		F_{1}-$\text{score}$&0.36&0.69\\
		\bottomrule
	\end{tabular}
	\label{tab:s4e3c}
\end{table}%

\paragraph{Conclusion}
Based on the experiments conducted, we see that a very low value or a very high value of parameter H resulted in the failure of the methodology. Furthermore, a very low value of H implies that we trying to categorize the flagged instances based on a single similarity pattern. As a result, very little information is used to categorize the instances as we are considering the similarity of identified instances with just one of the training classes. On the other hand, when the value of H is set to a high value, more information than required is used for categorization. This information is no more informative as we are considering the similarity of the flagged instances with  all the training classes. This induces noise into the process and the itemsets generated are associated to instances from multiple unknown classes as opposed to a particular unknown class. This eventually leads to incorrect categorization of the models and is evident from the results displayed in Table \ref{tab:s3t}. Furthermore, we see a poor performance from the classifiers when H is set to extreme values.  Hence, a moderate value of H is required to obtain desired results, and as a rule of thumb, we recommend this value to be equal to $|\mathcal{K}|$/2.

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis 3: Combined results of all experiments}
		\begin{tabular}[t]{crrrrrr}
		\toprule
		&\multicolumn{3}{c}{Experiments}\\ \cmidrule{2-4}
		Parameter&1&2&3\\
		\midrule 
		Maximum probability limit ($H$)&1&4&7\\
		Number of unknown classes discovered&3&2&2\\
		Percentage correctly classified for class \textit{8}&37&66&13\\
		Percentage correctly classified for class \textit{9}&93&86&90\\
		F_{1}-$\text{score}$ &0.77&0.86&0.69\\
		\bottomrule 
	\end{tabular}
	\label{tab:s3t}
\end{table}%

\section{Sensitivity analysis: Quality of classifier}\label{quality}
\paragraph{Purpose}
This analysis does not correspond to any parameter associated with the methodology but relates to one of the characteristics of the classifier itself. For the purpose of analysis, we examine the effect of quality of the classifier on the overall performance of the framework. This is an important analysis to conduct as we encounter classifiers with varied performance depending on the problem. 

\paragraph{Hypothesis}
A high quality classifier has better understanding of the patterns that exist within the training data and makes predictions on the known classes that are confident and accurate. The same classifier supplied with instances belonging to unknown classes makes predictions that are inaccurate and not confident. This discrepancy in predictions helps us to identify the unknown classes. On the other hand, a low quality classifier is inaccurate and not confident in making predictions on both the known classes as well as the unknown classes. This similarity in the performance, makes it difficult to distinguish between known and unknown classes. Hence, the performance of the framework improves with the increase in the quality of the classifier.

\paragraph{Experimental setup}
To maintain consistency, all the experiments are conducted on the MNIST data, where the training data $\mathcal{O}$ includes data corresponding to digits \textit{0} to \textit{7} and the open world data $\mathcal{O}$ contains data that belongs to all the digits \textit{0} to \textit{9}. Three experiments by varying the quality of the classifier are conducted. The details about the experimental settings are provided in Table \ref{tab:s5p}.

% \begin{table}[!t]
% 	\centering
% 	\caption{Sensitivity analysis-1}
% 	\begin{tabular}[t]{lc}
% 		\toprule
% 		Experiment&Quality of the classifier\\
% 		\midrule
% 		Experiment-1&High\\
% 		Experiment-2&Medium\\
% 		Experiment-3&Low\\
% 		\bottomrule
% 	\end{tabular}
% 	\label{tab:s5e}
% \end{table}%

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis 4: Experimental setup}
		\begin{tabular}[t]{center}
		\toprule
		&\multicolumn{3}{c}{Experiments}\\ \cmidrule{2-4}
		Parameter&1&2&3\\
		\midrule 
		Classifier&RF&RF&RF\\
		Quality (Accuracy \%)&High&Moderate &Low\\
		Chebyshev's parameter ($\mathcal{\tau}$)&3.16&3.16&3.16\\
		Maximum probability limit ($H$)&4&4&4\\
% 		Support ($S$)&0.1&0.1&0.1\\
% 		Confidence ($C$)&0.1&0.1&0.1\\
		Termination parameter ($\omega$)&0.25&0.25&0.25\\
		Termination parameter ($\beta$)&0.1&0.1&0.1\\
			Termination parameter ($\eta$)&0.1&0.1&0.1&\\
		Prediction confidence ($\gamma$) &0.4&0.4&0.4\\
		\bottomrule 
	\end{tabular}
	\label{tab:s5p}
\end{table}%
\subsubsection{Experiment -1}\label{q1}
In the first experiment, we consider the classifier with a very high accuracy of 99\%.  The first step is the identification stage where we apply Algorithm \ref{alg:JSD} on $\mathcal{O}$, using the Chebyshev's parameter ($\mathcal{\tau}$) that is set to a value of 3.16. The results of the identification stage indicate that about 59\% of the instances in $\mathcal{O}$ are identified (flagged) as belonging to the unknown classes. From Table \ref{tab:s5e1}, we analyze the distribution of the flagged instances in $\mathcal{F}$, and we see that about 83\% of them belong to the unknown classes. Since we have more than 10\% of the instances as flagged, we move forward to the next step, which is the categorization of flagged instances. Algorithm \ref{alg:ARM} is applied on $\mathcal{F}$ and the results from Table \ref{tab:s5e1cf} indicate that Algorithm \ref{alg:ARM} successfully discovered both the unknown classes. Furthermore, we also see that about 74\% of the instances belonging to class \textit{8} are correctly classified while the remaining are spread across the other classes, of which majority of them are wrongly classified as class \textit{3}. Similarly, for class \textit{9}, 79\% of them are correctly classified and the majority of the remaining instances are misclassified as class \textit{4}.  The overall accuracy of the classifier increases from 48\% to 86\% and the information regarding other performance metrics is provided in Table \ref{tab:s5e1c}.

\begin{table}[!t]
	\centering
	\caption{Sensitivity analysis-4 (Experiment-1): Classwise data distribution of $\mathcal{O}$ and $\mathcal{F}$ for MNIST data}
	\begin{tabular}[t]{ccc}
		\toprule
		Class&  $|\mathcal{O}|$&  $|\mathcal{F}|$\\
		\midrule
		$0$&247&41\\
		$1$&283&20\\
		$2$&236&65\\
		$3$&268&63\\
		$4$&239&54\\
		$5$&230&70\\
		$6$&231&42\\
		$7$&266&45\\
		$8$&1005&1001\\
		$9$&995&963\\
		\bottomrule
	\end{tabular}
	\label{tab:s5e1}
\end{table}%



\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-4 (Experiment-1):Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
    \begin{tabular}[t]{crrrrrrrrrr}
		\toprule
		&\multicolumn{8}{c}{Predicted class}\\ \cmidrule{2-11}
		True class&0&1&2&3&4&5&6&7&8&9\\
		\midrule
		$0$&246&0&0&0&0&0&1&0&0&0\\
		$1$&0&280&1&1&1&0&0&0&0&0\\
		$2$&3&2&221&1&3&0&2&2&2&0\\
		$3$&0&0&4&243&0&0&1&6&8&6\\
		$4$&0&1&0&0&227&0&0&1&0&10\\
		$5$&2&1&0&2&0&212&3&0&2&8\\
		$6$&3&0&0&0&0&1&227&0&0&0\\
		$7$&1&1&7&0&2&1&0&251&0&3\\
		$8$&3&21&37&89&14&29&7&5&743&57\\
		$9$&9&3&13&12&121&5&0&27&18&787\\
		\bottomrule
	\end{tabular}
	\label{tab:s5e1cf}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis-4 (Experiment-1): Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for MNIST data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial& Final\\
		\midrule
		Accuracy&0.48&0.86\\
		Precision&0.30&0.88\\
		Recall&0.48&0.86\\
		F_{1}-$\text{score}$&0.36&0.87\\
		\bottomrule
	\end{tabular}
	\label{tab:s5e1c}
\end{table}%

\subsubsection{Experiment -2}\label{q2}
In this experiment, we consider a classifier with a lower performance (Accuracy: 70\%) compared to the classifier in the previous experiment. We apply Algorithm \ref{alg:JSD} on $\mathcal{O}$, using the Chebyshev's parameter ($\mathcal{\tau}$) that is set to a value of 3.16. The result of the identification stage is that none of the instances are flagged as belonging to the unknown classes. Since we do not have any data to proceed further, we terminate the algorithm here.

% \begin{table}[!t]
% 	\centering
% 	\caption{Sensitivity analysis-4 (Experiment-2): Class wise data distribution of $\mathcal{O}$ and $\mathcal{F}$ for MNIST data}
% 	\begin{tabular}[t]{lccc}
% 		\toprule
% 		Class&  $\mathcal{O}$&  $\mathcal{F}$\\
% 		\hline
% 		$0$&247&31\\
% 		$1$&283&22\\
% 		$2$&236&50\\
% 		$3$&268&14\\
% 		$4$&239&33\\
% 		$5$&230&12\\
% 		$6$&231&29\\
% 		$7$&266&37\\
% 		$8$&1005&96\\
% 		$9$&995&137\\
% 		\hline
% 	\end{tabular}
% 	\label{tab:s3e2}
% \end{table}%

% \begin{table}[ht]
% 	\centering
% 	\caption{Sensitivity analysis-4 (Experiment-2): Performance of $\mathcal{C}$ and $\mathcal{C}_{new}$ on $\mathcal{O}$ for MNIST data}
% 	\begin{tabular}[t]{lcc}
% 		\toprule
% 		Performance metric&$\mathcal{C}$ & $\mathcal{C}_{new}$\\
% 		\midrule
% 		$Accuracy$&0.39&0.39\\
% 		$Precision$&0.24&0.25\\
% 		$Recall$&0.0.40&0.39\\
% 		$F1-score$&0.0.30&0.30\\
% 		\bottomrule
% 	\end{tabular}
% 	\label{tab:s3e2c}
% \end{table}%

% \begin{table}[ht]
% 	\centering
% 	\caption{Sensitivity analysis-4 (Experiment-2): Confusion matrix for performance of $\mathcal{C}_{new}$ on $\mathcal{O}$ for MNIST data}
% 	\begin{tabular}[t]{lccccccccccc}
% 		\toprule
% 		\multicolumn{8}{c}{Predicted}\\
% 		&&0&1&2&3&4&5&6&7&8&9\\
% 		\hline
% 		\multirow{8}{*}{True}&$0$&240&0&2&2&0&0&1&0&0&0\\
% 		&$1$&0&279&2&2&0&0&0&0&0&0\\
% 		&$2$&10&30&153&8&6&0&12&17&0&0\\
% 		&$3$&4&14&10&221&6&0&12&17&0&0\\
% 		&$4$&0&7&1&8&205&0&8&10&0&0\\
% 		&$5$&20&19&2&79&38&47&15&10&0&0\\
% 		&$6$&17&6&11&10&3&0&182&2&0&0\\
% 		&$7$&5&9&6&3&5&0&0&238&0&0\\
% 		&$8$&8&271&140&243&143&4&157&39&0&0\\
% 		&$9$&9&39&14&79&703&0&9&142&0&0\\
% 		\hline
% 	\end{tabular}
% 	\label{tab:s3e2cf}
% \end{table}%


% From the results, we can see that out of all instances identified, 50\% of them belongs to unknown classes. After the categorization phase, the results of the classifier can be seen in table. From the table we can see there is no improvement in the performance of the latest classifier compared to the initial classifier. Furthermore, from the tables, we can see that there are no instances from O that are classified into classes 8 or 9. One of the possible reasons for the failure could be the lower percentage of unknown data being identified and as a result, enough information was not provided to the model to learn the new classes. 

\subsection{Experiment-3} \label{q3}
For this experiment, we consider a classifier with a relatively low performance (Accuracy: 51\%) compared to the previous two experiments.  Similar to the previous experiment, none of the instances were identified for a critical value of 3.16 after the identification stage. 

\paragraph{Conclusion}
The results from this analysis support our hypothesis that the quality of the classifier plays a crucial on the performance of the framework. The framework performed successfully when used in conjunction with a high quality classifier as supported by the results from Experiment \ref{q1}. For Experiments \ref{q2} and \ref{q3}, we see that the framework terminated in the first stage of the process itself as Algorithm \ref{alg:JSD} failed to identify instances that belong to the unknown classes.
\begin{table}[ht]
	\centering
	\caption{Sensitivity analysis 4: Combined results of all experiments}
		\begin{tabular}[t]{crrrrrr}
		\toprule
		&\multicolumn{3}{c}{Experiments}\\ \cmidrule{2-4}
		Parameter&1&2&3\\
		\midrule 
		Quality (Accuracy \%)&High&Moderate &Low\\
		Percentage of identified instances&59&0&0\\
		Number of unknown classes discovered&2&-&-\\
		F_{1}-$\text{score}$ &0.86&-&-\\
		\bottomrule 
	\end{tabular}
	\label{tab:s3t}
\end{table}%

% \section{Sensitivity analysis: Percentage of unknown class in O}

% In the previous experiments, we have conducted sensitivity analyses on the parameters associated with the framework. This analysis, on the other hand, is performed to determine the sensitivity of the methodology towards the percentage of unknown data in the open world dataset O. Based on the results we have from various experiments, it is understood that, this technique does not only capture the unknown classes but also data from the known classes. Hence, it is important to examine if the proportion of unknown data in O affects the performance of the framework.

% \begin{table}[!t]
% 	\centering
% 	\caption{Sensitivity analysis-4}
% 	\begin{tabular}[t]{lc}
% 		\toprule
% 		Experiment&Percentage of unknown classes\\
% 		\midrule
% 		Experiment-1&<25\%\\
% 		Experiment-2&=50\%\\
% 		Experiment-3&=100\%\\
% 		\bottomrule
% 	\end{tabular}
% 	\label{tab:s5e}
% \end{table}%


% \begin{table}[ht]
% 	\centering
% 	\caption{Parameters setting for Algorithm \ref{alg:ARM} - HAR data}
% 	\begin{tabular}[t]{lcc}
% 		\toprule
% 		Parameter&Value\\
% 		\midrule 
% 		Maximum probability limit ($H$)&4\\
% 		Support ($S$)&0.1\\
% 		Confidence ($C$)&0.1\\
% 		Termination parameter ($\omega$)&0.25\\
% 		Termination parameter ($\beta$)&0.1\\
% 		Prediction confidence ($\gamma$) &0.4\\
% 		Number of iterations ($k$)&3\\
% 		\bottomrule 
% 	\end{tabular}
% 	\label{tab:s4p}
% \end{table}%
% To maintain consistency, all the experiments are conducted on the MNIST data, where the training data T includes the classes 0 to 7 and the open world data O contains all the digits 0 to 9. Please note that in every experiment the unknown classes remain the same (8,9), but the proportion of data belonging to the unknown classes varies from experiment to experiment. Furthermore, all the other parameters that are involved in the entire framework remain constant and their values are displayed in table PARAM2. 

% \subsubsection{Experiment-1}
% For this experiment, an open world dataset that contains less than 25\% of unknown data is used. The class wise distribution of O along with the distribution of the flagged instances after the identification phase of the methodology is available in Table dist. 

% From the table, we can see that we have just 20\% of data belonging to unknown classes and almost all of them have been captured in the first step. Furthermore, there are approximately 50\% of instances that belongs to unknown classes and 50\% to the known classes. The results corresponding to the second stage (categorization) is available in table.

% \begin{table}[!t]
% 	\centering
% 	\caption{Experiment 3: Class wise data distribution of $\mathcal{O}$ and $\mathcal{F}$ for MNIST data}
% 	\begin{tabular}[t]{lccc}
% 		\toprule
% 		Class&  $\mathcal{O}$&  $\mathcal{F}$\\
% 		\hline
% 		$0$&493&63\\
% 		$1$&553&33\\
% 		$2$&496&96\\
% 		$3$&409&100\\
% 		$4$&361&73\\
% 		$5$&335&105\\
% 		$6$&362&69\\
% 		$7$&390&75\\
% 		$8$&1490&1486\\
% 		$9$&1510&1443\\
% 		\hline
% 	\end{tabular}
% 	\label{tab:s5e1}
% \end{table}%

% From the results, we can see an improvement in the performance of the final model compared to the initial classifier. Also, it is evident from the table, that majority of the data instances that belong to unknown classes have been grouped accurately.

% This experiment was conducted the same way as the previous experiment. The only change being the percentage of unknown data in O. For this experiment, we considered equal percentages of known and unknown data. The distribution of the data before and after the identification phase is provided in Table. 
% In this experiment, we considered an open world data set that contains data that belongs to only unknown classes. The distribution of data before and after identification is provided in Table.

% Table provides the performance of initial and final classifier on O. The values are zero for the initial classifier as the open world data does not contain any instances from the known classes.

\chapter{Case study - Social media analytics for community resilience}
\section{Introduction}

Social media platforms such as Facebook and Twitter have become prevalent communication tools in modern society. These platforms provide a mechanism for collecting dynamic data on human behavior and sentiment. Such data has proven useful to study a variety of activity including crime prediction \cite{Wang-2012}, disease outbreak \cite{Ritterman-2009}, stock market prices \cite{Si-2013}, and political election results \cite{Tumasjan-2010}, among other things.

Recent studies consider the use of social media during natural disasters \cite{Riccardi-2016}, studying mainly either the mood of the population or the various reactions of the public during a specific incident. Furthermore, most of the works that utilize social media data to support emergency management mainly rely on Twitter data for analysis \cite{reuter2018iscram}. One of the first works in social media data analysis during disasters was in 2008 after the wildfires in South Carolina  \cite{Sutton-2008}. Since then, many case studies have been related to the Haiti earthquakes \cite{Muralidharan-2011,caragea-2011} Hurricane Irene \cite{mandel2012demographic,Freberg-2013}, or Hurricane Sandy \cite{dong2013social,caragea-2014, Kryvasheyeu-2015, Jamali-2019}. A summary of the ongoing research in the area of emergency management using Twitter as a source of data is provided in \cite{martinez2018twitter}.  Most of the related analysis, especially those occurring in the United States, rely heavily on data collected from Twitter.

Twitter is a micro-blogging service in which, collectively,  users broadcast hundreds of millions of brief messages daily \cite{twitter}. One major characteristic of Twitter is that the messaging service is conducted in real-time and the day and time that the message is sent is recorded. Twitter messages, known as tweets, can also be labeled with keywords using the hashtag symbol (\#) to allow messages to be categorized. The twitter feed (i.e.,  on-going stream of tweets sent to users) can be filtered based on these  labels. Additionally, if the user creating a tweet has permitted location identification services from Twitter, the data include automatic geo-location coordinates embedded within the tweet.  The real-time nature of this social media platform,  the ability   to search for specific keyword labels, and the ability to filter by date, time, and location facilitates data collection regarding how the engaged population react to major events.

In research related to the use of social media during natural disasters, several studies measure user sentiment. For example,  \cite{nagy-2012} and \cite{caragea-2014} classify the tweet text as expressing Positive, Neutral or Negative emotions (also referred to as the sentiment polarity). \cite{mandel2012demographic} conducted a demographic analysis of the sentiment using the tweets corresponding to Hurricane Irene. A binary (positive or negative) or three-way (positive, negative, neutral) classification of sentiment are common levels of granularity used in sentiment analysis \cite{Go-2009, Agarwal-2011, Cruz-2013, Li-2013, Neppalli-2017, dong2013social}. On the other hand, \cite{schulz2013fine} performed a fine-grained sentiment analysis on the disaster-related tweets. The tweets were classified into 7 categories which include anger, disgust, fear, happiness, sadness, and surprise.  \cite{Ragini-2018} proposed a big data framework to analyze the user sentiment by applying various text mining and machine learning techniques on disaster related tweets.  Apart from sentiment analysis on natural hazard related tweets, researchers have analyzed tweet sentiment during other types of emergencies such as the 2013 Boston Marathon bombing \cite{lee2015sentiment}, the 2017 Las Vegas shooting \cite{singh2018analyzing}, the Syrian refugee crisis \cite{ozturk2018sentiment} and the Ebola disease outbreak \cite{lu2015visualizing}.

Works that use social media to tackle various disaster related tasks have proliferated in the recent times \cite{riccardi2016power,imran2013practical,cheong2011social,kumar2011tweettracker}. In research related to the use of social media during natural disasters, several studies measure user sentiment. For example,  \cite{nagy-2012} and \cite{caragea-2014} classify the tweet text as expressing Positive, Neutral or Negative emotions (also referred to as the sentiment polarity). \cite{mandel2012demographic} conducted a demographic analysis of the sentiment using the tweets corresponding to Hurricane Irene. A binary (positive or negative) or three-way (positive, negative, neutral) classification of sentiment are common levels of granularity used in sentiment analysis \cite{Go-2009, Agarwal-2011, Cruz-2013, Li-2013, Neppalli-2017, dong2013social}. On the other hand, \cite{schulz2013fine} performed a fine-grained sentiment analysis on the disaster-related tweets. The tweets were classified into 7 categories which include anger, disgust, fear, happiness, sadness, and surprise.  \cite{Ragini-2018} proposed a big data framework to analyze the user sentiment by applying various text mining and machine learning techniques on disaster related tweets.  Apart from sentiment analysis on natural hazard related tweets, researchers have analyzed tweet sentiment during other types of emergencies such as the 2013 Boston Marathon bombing \cite{lee2015sentiment}, the 2017 Las Vegas shooting \cite{singh2018analyzing}, the Syrian refugee crisis \cite{ozturk2018sentiment} and the Ebola disease outbreak \cite{lu2015visualizing}. With an intention to provide valuable crisis response information to the humanitarian organizations, \cite{alam2018crisismmd} have released a dataset that contains tweets belonging to various actionable categories. \cite{huang2015geographic} used machine learning models to classify disaster related tweets into various categories of disaster management phases like mitigation, preparedness, emergency response and recovery. \cite{caragea2011classifying} classified tweets during Haiti disaster into multiple informative categories. \cite{verma2011natural} classified disaster related tweets that come under the category of situational awareness. A hybrid model combining both machine learning and rule based methods was proposed by \cite{ragini2018mining} to classify disaster related tweets which can help the emergency responders identify people who are at risk. \cite{caragea2016identifying} used Convolutional Neural Networks to classify informative tweets from non-informative tweets. A summarization of research in the field of crisis management using twitter as the main source of information is provided by \cite{luna2018social,martinez2018twitter}.

These works explain the importance of social media analytics in effective disaster management and ameliorating the community resilience. The basic idea is to extract useful information from disaster related tweets by classifying them into various informative categories. One of the key aspects associated with developing the classification models for tweet classification is the preparation of training data. Literature suggests works that deal with different classification types such as informative vs non-informative, sentiment analysis, multi-class classification involving multiple informative classes, etc. Furthermore, in each of the these tasks, the decision about the type of classification or the categories for tweet classification are decided by the researcher and the training data is prepared accordingly. After the data preparation phase, machine learning models are trained to classify the tweets into different categories, to use them at the time of hazards that occur in the future. 
Since, the choice of tweet categories is manual and limited, it is possible for the classifiers to encounter tweets from categories that are not present in the training data. This opens up the need to address the problem of open world classification in social media analytics for disaster management. In Section \ref{twitter}, we demonstrate the occurrence OWC on Twitter analysis and also the performance of the proposed framework on a sample real world dataset.

\section{Application of the proposed framework on disaster related Twitter data} \label{twitter}
We apply the proposed framework on Crisis MMD dataset \cite{crisismmd2018icwsm}, which comprises of human-annotated tweets collected during different major disasters. The dataset under consideration contains 10,347 tweets corresponding to different humanitarian categories such as affected individuals, infrastructure and utility damage, injured or dead people and, rescue volunteering or donation effort.

For the experiment, ``rescue volunteering or donation effort" class is considered to be the unknown class while the other classes are the known classes. In order to be consistent with the testing and the sensitivity analysis, we use random forest for the classification using the Tf-idf based word representation. The distribution of the open world data and the identified instances is displayed in Table \ref{tab:twitter1}. From this table, we see that about 30\% of the instances in $\mathcal{O}$ are flagged as belonging to the unknown class. Furthermore, 77\% of the flagged instances belong to the unknown class. Since, we have more than 10\% of the instances as flagged in the first stage,we proceed to the second stage based on the parameter settings displayed in Table \ref{tab: twitterp}. The results indicate that the algorithm automatically terminated after discovering the presence of a single unknown class in the open world data. Furthermore, Table \ref{tab:twitter2} depicts that 82\% of the instances that belong to class \textit{3} are classified correctly and the majority of the remaining instances are misclassified as class \textit{1}. Before applying our framework, the distribution of the predictions made by the initial classifier on the open world data is provided in Table \ref{tab:twitter5}. This table shows, that majority of the instances in $\mathcal{O}$ that belong to the unknown class are misclassified as class \textit{1}. This shows that class \textit{3} possess semantic similarity with class \textit{1} in the vector space, resulting in the misclassification as class \textit{1}, before and after the application of the framework. From Tables \ref{tab:twitter2} and \ref{tab:twitter4},we see that in presence of of an unknown class, the performance of the classifier on the known classes is not degraded much, but the framework automatically discovered the single unknown class and correctly classified 1630 instances out of 1977 instances totally present. This case study demonstrates the possibility of open world problems in social media analytics and also the applicability of the proposed framework to such real world applications.

\begin{table}[!t]
	\centering
	\caption{Class wise data distribution of $\mathcal{O}$ and $\mathcal{F}$ for Twitter data}
	\begin{tabular}[t]{lcccc}
		\toprule
		Class&class information&$|\mathcal{O}|$&$|\mathcal{F}|$\\
		\hline
		$0$&affected individuals&193&83\\
		$1$&infrastructure and utility damage&479&57\\
		$2$&injured or dead people&196&53\\
		$3$&rescue volunteering or donation effort&1977&641\\
		\bottomrule
	\end{tabular}
	\label{tab:twitter1}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Parameters setting for Algorithm \ref{alg:ARM} - Twitter data}
	\begin{tabular}[t]{lcc}
		\toprule
		Parameter&Value\\
		\midrule 
		Maximum probability limit ($H$)&3\\
% 		Support ($S$)&0.1\\
% 		Confidence ($C$)&0.1\\
		Termination parameter ($\omega$)&0.25\\
		Termination parameter ($\beta$)&0.1\\
		Prediction confidence ($\gamma$) &0.6\\
		\bottomrule 
	\end{tabular}
	\label{tab: twitterp}
\end{table}%

\begin{table}[ht]
	\centering
    \caption{Confusion matrix for the initial performance of $\mathcal{C}$ on $\mathcal{O}$ for Twitter data}
	\begin{tabular}[t]{crrrr}
		\toprule
		&\multicolumn{4}{c}{Predicted class}\\ \cmidrule{2-5}
		True class&0&1&2&3\\
		\midrule
		$0$&49&128&16&0\\
		$1$&7&467&5&0\\
		$2$&3&36&157&0\\
		$3$&252&1631&94&0\\
		\bottomrule
	\end{tabular}
	\label{tab:twitter5}
\end{table}%


\begin{table}[ht]
	\centering
	\caption{Confusion matrix for the final performance of $\mathcal{C}$ on $\mathcal{O}$ for Twitter data}
	\begin{tabular}[t]{crrrr}
		\toprule
		&\multicolumn{4}{c}{Predicted class}\\ \cmidrule{2-5}
		True class&0&1&2&3\\
		\midrule
		$0$&23&50&9&111\\
		$1$&4&383&2&90\\
		$2$&0&20&150&26\\
		$3$&19&321&7&1630\\
		\bottomrule
	\end{tabular}
	\label{tab:twitter2}
\end{table}%

% \begin{table}[ht]
% 	\centering
% 	\caption{Confusion matrix for performance of $\mathcal{C}_{new}$ on $\mathcal{O}$ for Twitter data}
% 	\begin{tabular}[t]{lccccc}
% 		\toprule
% 		\multicolumn{3}{c}{Predicted}\\
% 		&&0&1&2&3\\
% 		\midrule
% 		\multirow{4}{*}{True}&
% 		$0$&23&50&9&111\\
% 		&$1$&4&383&2&90\\
% 		&$2$&0&20&150&26\\
% 		&$3$&19&321&7&1630\\
% 		\hline
% 	\end{tabular}
% 	\label{tab:twitter2}
% \end{table}%


\begin{table}[ht]
	\centering
	\caption{Initial and final performance of $\mathcal{C}$ on $\mathcal{O}$ for Twitter data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial & Final\\
		\midrule
		Accuracy&0.24&0.77\\
		Precision&0.08&0.79\\
		Recall&0.24&0.77\\
		F_{1}-$\text{score}$&0.11&0.76\\
		\bottomrule
	\end{tabular}
	\label{tab:twitter3}
\end{table}%

\begin{table}[ht]
	\centering
	\caption{Initial and final performance of $\mathcal{C}$ on known classes for Twitter data}
	\begin{tabular}[t]{lcc}
		\toprule
		Performance metric&Initial & Final\\
		\midrule
		Accuracy&0.82&0.69\\
		Precision&0.83&0.85\\
		Recall&0.82&0.69\\
		F_{1}-$\text{score}$&0.79&0.72\\
		\bottomrule
	\end{tabular}
	\label{tab:twitter4}
\end{table}%

\chapter{Summary}
\section{Conclusion}
To date, the problem of open world classification has been addressed primarily in the domain of computer vision. Most of the works that are available in the literature try to solve this problem especially for the image data. The main goal of this work is to be able to generalize the problem of open world classification without confining it to a particular domain or the data being worked upon. To the best of our knowledge, there is no work in the literature that solves the problem of open world classification, irrespective of the nature of the data and also the classifier in use. We address this issue by developing a framework that is based on the projection of data on to a  probabilistic space as opposed to working with the original feature space. Hence, this projection provides the method to generalize to any type of data. Also, the idea of projecting the data onto a probabilistic space makes the methodology independent of the classifier, as it is possible to generate the probabilistic space using any classifier. Furthermore, most of the techniques available in the literature that address this issue are either data specific or algorithmic specific. Considering this issue, we propose a methodology that acts like an accessory to any classifier to solve the problem of open world classification.

It is evident from the literature review that most of the works in this field try to build models that focus mainly on the identification phase. This is just a partial solution and is complete only when the identified data points are organized into their respective classes. While there are a few works in the literature that address the problem of discovering the unknown classes, their solutions are not accurate as they just provide an estimate as to how many unknown classes can be present in the open world data. To address this issue, in this paper, we propose a novel way of categorizing the data instances belonging to unknown classes based on the idea of residual signature. Each unknown class can possess a unique signature in the probabilistic space and this idea is leveraged to group the data. The experiments prove the successful working of the proposed methodology for different number of unknown classes and also for different types of data. The case study presented in this paper demonstrates the applicability of the proposed framework to social media analytics to improve community resilience.

\section{Limitations}
Ideally, we would expect Algorithm \ref{alg:JSD} to flag only those instances that belong to the unknown classes. However, we see some of the observations from the known classes also being flagged by the algorithm.
From the results in Section \ref{quality}, we see that the framework does not perform as expected when used in conjunction with a low quality classifier. Another limitation is with regards to Algorithm \ref{alg:ARM} where the performance of the framework is relatively poor when there are fewer number of known classes present in the data. This is specifically true when the number of unknown classes is greater than the number of known classes. Furthermore, when few instances are associated with a particular itemset during the categorization phase, causes imbalance in the dataset which makes the task of training the machine learning model difficult.

In Algorithm \ref{alg:ARM}, the class labels can be replaced with the actual probability values to generate the itemsets. Techniques such as \cite{snell2017prototypical,ravi2016optimization, garcia2017few,lake2013one,bertinetto2016learning,fu2013learning}, \emph{one shot learning} \cite{vinyals2016matching,fei2006one} can be applied when dealing with imbalanced data sets. 

\section{Future work}
This framework is based on the assumption that the open world data is already available at once, which is basically referred to as the offline setting. One of the future works could be based on adapting this framework to the online setting, where a single or relatively small number of instances are provided to the framework at a given instance of time.

% The limitations of the proposed work are as follows:
% \begin{itemize}
%     \item From Section \ref{quality}, we learnt that the framework does not perform as expected when used in conjunction with a classifier of low quality.
    
%     \item From Section \ref{known}, it is understood that the performance is relatively poor when dealing with fewer number of known classes. This is especially true when we have more number of unknown classes than the known classes.
    
%     \item From Section \ref{mnist}, the performance of the classifier is poor when fewer number of instances are associated with an itemset. It is difficult to train classical machine learning models on imbalanced dataset. Hence techniques such as \emph{one shot learning} \cite{vinyals2016matching,fei2006one}, \emph{Few shots learning} \cite{snell2017prototypical,ravi2016optimization, garcia2017few,lake2013one,bertinetto2016learning,fu2013learning}, and \emph{zero shot learning}  \cite{palatucci2009zero,lampert2009learning,fu2018recent} can be used to improve the performance of the framework.
    
% \end{itemize}


\bibliographystyle{unsrt}
\bibliography{sample}
\end{document}

