\chapter{Algorithm Recognition}
\label{chap:ch3}
\vk{fixme: unsupervised learning}
In this chapter, we will discuss about Algorithm Recognition in supervised and \ra{few-short} setting using IR2Vec. 
In section~\ref{sec:algo:intro}, we give a brief introduction to Algorithm Recognition, a summary of the previous work, and our proposal to solve the problem. 
In section~\ref{sec:algo:sup}, we give a brief overview of supervised learning for Algorithm Recognition, the dataset used, our Model Architecture, and results. 
In section~\ref{sec:algo:unsup}, we give a brief overview of few-shot learning for Algorithm Recognition, few-shot classification, dataset used, our Model Architecture, and results. 
In Section~\ref{sec:algo:conclusion}, we will conclude this chapter.


\section{Introduction}\label{sec:algo:intro}
Algorithm recognition is a problem in which we want to detect similar programs that solve the same problem. In the programming language to prove that two programs are same or not is an undecidable problem and cannot be solved deterministically. The benefits of algorithm recognition could be better maintenance of the codes, tagging the similar programs, code suggestion. etc.   A tool can be derived from this solution and can ease the problem faced by the software developer in the daily routine. With the advent of machine learning based approximation strategies, several attempts have been made to fruitfully address this problem.

% Classifying programs based on the problem statement or detecting if two programs solve the same purpose is undecidable as there is no algorithm exist to emulate this on a Turing Machine. With that said, it cannot be solved on a modern computer. However, it is rather important -- classification of programs based on functionality helps in better maintainance of codes, helps in better code suggestion, etc. With the advent of machine learning based approximation strategies, several attempts have been made to fruitfully address this problem.

Applying deep learning to classify programs was first carried out by Peng et al.~\cite{Peng:2015}, and then used by various others~\cite{tbcnn-aaai16,ncc,Chen:2019} to demonstrate the goodness of their representation to classify programs. 
However, most of these approaches~\cite{Peng:2015,tbcnn-aaai16,Chen:2019} are trained to solve the specific task of classifying programs (whose representations cannot generalize across other tasks).

In this work, we have used the IR2Vec to get the program representations. We will apply these representations in supervised as well as \ra{few-shot} setting. In  upcoming sections, we will discuss in about the work done for each setting respectively.

\section{Supervised Learning}\label{sec:algo:sup}
    Supervised Learning is the field of machine learning in which the model is trained against the set of known label or tags. The model for a given data point can't predict any thing that is not part of the set of classes that is exposed during training. There are some fixed numbers of label for a machine learning task.
% \vk{Add more here..}

% \subsection{Background}
In case of the image classification, there is a dataset of images with the corresponding labels. A classifier would be trained on the images from training set to predict the label of the image. Given the true label and the predicted label, a loss is computed to update gradient.
% \vk{Related work}

% \subsection{Methodology}
On a similar note, we try to classify programs so as to recognize algorithms. Here, given a program, the objective is to classify it to one of the known classes that it would belong. Fig~\ref{fig:supervised-background} summarizes this flow. 

\begin{figure}[t]
    \centering
    \includegraphics[scale=0.4]{figures/chapter-3/supervised_introduction.png}
    \caption{Algorithm Recognition in Supervised Way}
     \label{fig:supervised-background}
\end{figure}

% we want to predict to give algorithm class the program belong to.

% We developed an classifier in TensorFlow\cite{tensorflow_USENIX2016} which can classify the program respectively. 
\subsection{DataSet}
% We have selected the POJ-104 dataset\ref{tbcnn-aaai16} for our experiments. It has 104 type of different program which acts like class or label and each class has approximately ~500 programs. We have splitted this dataset into 3:1:1(training:testing:validation).

% ==================================================
We make use of the POJ-104 dataset introduced by Mou et al.~\cite{tbcnn-aaai16} for program classification. This dataset is obtained from Pedagogical Programming Open Judge (POJ/OJ) system, where the students submit the solutions to programming questions and the Open Judge system automatically evaluates those codes. 
Each programming question has an associated ID and many valid submissions across each ID. 
Each ID corresponding to a programming question forms a class, and all the submissions against the ID forms the data points of that class for classification problem. There are 104 such classes of C and C++ codes.

We follow the same data splitting strategy of earlier works by selecting 500 samples from each class randomly and splitting them in 3:1:1 ratio for training, testing and validation.
% ==================================================

% \subsection{Embedding Generation}

\subsection{Model}
% We used IR2Vec to generate the embedding for the input programs. For each program, we get a 300 dimension vector and its corresponding label. Such a vector is used as the input to the model.

% The first input layer expects a 300-dimension vector which is followed by simple three layered Multi-Level Precptron(MLP) with a softmax layer for output. The Categorical cross entropy Loss is used as the loss function and Adam as the optimizer. The whole training run for 100 epochs.

% ===================================================== (Can use directly)
For this classification task, we construct a simple three layered neural network which takes the vectors representing the programs of different classes as input and predicts the class as output. The neural network for this task consists of two stacked dense layers of 300 units each. Batch normalization~\cite{pmlr-v37-ioffe15-batchnorm} with ReLU as the activation function is used, with a dropout of 25\% as regularizer between each layer. The final layer is a softmax layer with the units equal to the number of classes of the programs. Adam optimizer with learning rate of 0.001 and categorical cross entropy is used as the loss function. Given an input vector, the network is trained to predict a class out of 104 classes of the input programs. 
% ===================================================

\subsection{Results}

We achieve an accuracy of 96.2\% with \textit{Flow-Aware} encodings of IR2Vec. 
The results are compared with various methods that had used the same dataset for classifying the programs. We outperform the state-of-the-art methods on using a simpler neural network, whereas other methods use RNNs and LSTMs to achieve the results.
We obtain superior results by taking a very less training time of about \textit{one minute} per epoch when compared to the time taken by inst2vec of 1-2 hours per epoch on a P100 GPU, as claimed by the authors. 

As said earlier, the comparison is between TBCNN~\cite{tbcnn-aaai16}, inst2vec~\cite{ncc} and IR2Vec-Symbolic and IR2Vec-Flow-Aware.

% \begin{center}
\begin{table}[h]
\centering
  \caption{POJ-104 classification results}
%   \vspace*{-\baselineskip}
  \label{tab:pc_accuracy}   % \small
    \begin{tabular}{ccccc}
    \toprule
     & \textbf{TBCNN} & \textbf{inst2vec} & \textbf{IR2Vec-Flow-Aware}\\
        \hline
        \textbf{Accuracy} & 94\% & \textit{94.83\%\protect\footnotemark}  & \textbf{96.2\%} \\
    \bottomrule
    \end{tabular}
% \vspace*{-\baselineskip}
\end{table}
% \end{center}
 \footnotetext{This value is quoted by the authors in their paper.}


% \subsection{Visual Technique}
In Fig.~\ref{fig:clusters}, we visualize how the datapoints get clustered on training.
As the input vector is of 300 dimensions, we reduce it's dimension to 2 dimensions using t-SNE~\cite{tsne}. Points which are similar to each other meant to be closer to each other. The effectiveness of the encoding different instance to time during training is shown in this figure.

\begin{figure}[h]
    % \centering
\begin{subfigure}[b]{0.3\textwidth}
%   \centering
  \includegraphics[width=\textwidth]{figures/untrained.png}  
  \caption{Untrained}
  \label{fig:0e}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.3\textwidth}
%   \centering
  \includegraphics[width=\textwidth]{figures/5e_tsne.png}  
  \caption{After 5 Epochs}
  \label{fig:5e}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.3\textwidth}
%   \centering
  \includegraphics[width=\textwidth]{figures/full_tsne.png}  
  \caption{After 100 Epochs}
  \label{fig:100e}
\end{subfigure}
    \caption{Comparison of cluster at different instant}
    \vspace*{-\baselineskip}
    \label{fig:clusters}
\end{figure}

\begin{itemize}
    \item In Fig.~\ref{fig:0e}, we show the untrained data. It can be seen that points of similar labels are grouped together to some extent, though the clusters are not formed distinctly.
    % \vspace*{-0.4cm}

% It is a well accepted fact that the weights of the penultimate layer of the neural network represe the representation of 
% After training the classification model with the training data points for 5 epochs, we obtain the 

    \item In Fig.~\ref{fig:5e}, we show the plot formed by the learned output vectors that were taken from the last layer of the classification model after 5 epochs of the training for the same test data points. As it can be seen, on a minimalistic training, they quickly form better clusters.
    %   \vspace*{-0.4cm}
    \item At the end of training, after 100 epochs, the points form more distinct clusters as shown in Fig.~\ref{fig:100e}.
\end{itemize}

% Unsupervised Learning started
\vk{We are not using unsupervised learning!}
\section{Few Shot Learning}\label{sec:algo:unsup}
\subsection{Background}
We want to generalize the model for the unseen classes. The unseen classes are the data point types which were not present during the training. The unsupervised learning can't help to solve the problem as it would not generalize.

Unsupervised learning is the type of machine learning technique, where the model is trained on the dataset that is unlabelled. The clustering algorithms (like KNN, K-means, hierarchical clustering) are the prominent examples of this category. 
These algorithms focus on minimizing the intra-cluster distance and maximizing the inter-cluster distances. Similar data points stay near a similar point and far from the non-similar ones.

As shown in Fig~\ref{fig:unsupervised-background}, the set of unlabelled programs are passed a  machine learning model. The model tries to form clusters of similar programs during the training. After training is done, we perform inference on the model, where we try to assign a given unseen program to the \textit{best-suited} cluster. At the time of inference, the unknown program is assigned to one of the existing cluster only.  
% This is a schematic diagram of the flow for better understanding.

\vk{Not correct?}
\ra{We will use Few Shot Classification methodology to solve this problem. Few Shot Classification is the way to learn the patterns to create separate clusters, even for the unseen classes using the few shot methodology.} We will discuss in detail in Sec.~\ref{sec:algo:unsup:fsc}. 

% Few shot learning is a way of learning where there is a limited availability of data. It can either be supervised or unsupervised. In this experiment, we use an unsupervised few shot learning technique for  

\begin{figure}[t]
    \centering
    \includegraphics[scale=0.4]{figures/chapter-3/unsupervised.png}
    \caption{Algorithm Recognition in Unsupervised Way\vk{Fixme}}
     \label{fig:unsupervised-background}
\end{figure}

\subsection{Few Shot Classification}\label{sec:algo:unsup:fsc}
\vk{Few shot learning is not unsupervised}
	    In Few Shot Classification, model learn to generalize for unseen classes during training. The training phase has two sets - support set and a Query set. The training happens in task. Each task consists of N classes and K datapoints in the support set and N classes in the support set \vk{incorrect?}. Each task has a mutually exclusive set i.e. all the N classes are not part of another task.(fig~\ref{fig:unsupervised-fewshot})
% 	Training
\vk{Task -- not sure if it is a standard term}
    A task is given to the model and support set is passed to the model. Now to see how much the model learns after first task, we run it on the query set for which we knew the label. The datapoint belonging to same class should lie near to each other. In the example as per Fig.\ref{fig:unsupervised-background}, there is a cat class in the support set and query set of task1. On training, the datapoint of cat class from query set should try to lie near the cat cluster of the support set. The other datapoints in the query set should also have same behaviour.
	
% 	The Loss function is formulated in terms of the distance metric\vk{Not necessarily; a notion of distance can be learnt}. If the query set is far apart during training then more is the loss and that needs to backpropagate for the better learning of the next task or batch.

A previous work Prototypical Networks~\cite{protonet:NIPS2017} which perform few-short classification to generalize the model for unseen classes.

\begin{figure}[t]
    \centering
    \includegraphics[scale=0.4]{figures/chapter-3/unsupervised_few_shot.png}
    \caption{Few shot Learning Example}
     \label{fig:unsupervised-fewshot}
\end{figure}


\begin{figure}[t]
    \centering
    \includegraphics[scale=0.5]{figures/chapter-3/prototypes.png}
    \caption{Prototypes}
     \label{fig:unsupervised-prototypes}
\end{figure}

\subsection{Prototypical Networks}
Prototypical Networks~\cite{protonet:NIPS2017} is a way for few-shot classification algorithm. They have proposed a loss function known as Prototypical Loss and use it to train the network. They map the input embedding to a new latent space where similar points are nearer. $S_{k}$ is the support set for class \textit{k}, where $f_{\phi}$ is the neural network which learns to map the input to latent space, where $\phi$ is the learnable parameter of the neural network.

\subsubsection{Prototype}
During the training phase, the support set is passed to the model. Each class forms an aggregate point from other participating points and known as the prototype (Fig.~\ref{fig:unsupervised-prototypes}). In equation~\ref{eq:1}, prototype($c_{k}$) is been calculated for each class respectively. \vk{More here}

 
\begin{equation} \label{eq:1}
c_{k} = \frac{1}{|S_{k}|}  \sum_{(x_{i},y_{i}) \epsilon S_{k}}  f_{ \phi }(x_{i})
\end{equation}

\subsubsection{Loss Function}\label{sec:algo:proto:loss}
During the training phase, datapoint from each class of the Query set to evaluated against all the calculated prototypes. The loss function is calculated using the probability distribution of a prototype($c_{k}$) given a point \textbf{x} . Using the square euclidean metric to calculate the distance between them. Less is the distance, higher is the probability that the point x belongs to the respective prototype. Loss function is negative log-probability of $p_{\phi}$ from Eq.~\ref{eq:2} %\vk{Equation}

\begin{equation}\label{eq:2}
p_{ \phi }(y = k | x) =  \frac{exp(-d(f_{\phi}(x), c_{k}))}{\sum_{k^{'} }exp(-d(f_{\phi}(x), c_{k^{'}}))} 
\end{equation}

\subsection{Algorithm Recognition for unseen programs}
Inspiring from the work mentioned above, we want to apply the same technique to the programs. We make the required changes to the Prototypical Networks~\cite{protonet:NIPS2017} to work for the programs recognition in few-shot setting.  

\subsection{Dataset}
We have selected the POJ-104 dataset~\cite{tbcnn-aaai16} for our experiments. It has 104 type of different program which acts like class or label and each class has approximately ~500 programs. We have split this dataset into Train: Test: Val →  1-80 classes (80): 81-94 classes (14): 95-104 classes (10).

\subsection{Model Architecture}
The implementation was done using PyTorch in python. The first input layer expects a 300-dimension vector which is followed by a simple three-layered Multi-Level Perceptron(MLP) with a softmax layer for output. The negative log-probability of the Eq.~~\ref{eq:2} is used as the loss function and Adam optimizer. The whole training runs for 100 epochs.

\subsection{Results}
We have calculate the accuracy for four configuration. The \textit{\textbf{N way}} is the number of the classes used in each task and \textit{\textbf{K shot}} is the number datapoint  of each class are being used. See the Tab.~\ref{tab:unsupervised-acc}.
\begin{table}[h]
\begin{tabular}{lllll}
\hline
\multirow{2}{*}{\textbf{POJ Experiment}} & \multicolumn{2}{l}{\textbf{5 ways}} & \multicolumn{2}{l}{\textbf{10 ways}} \\
 & \textbf{1 Shot} & \textbf{5 Shot} & \textbf{1 Shot} & \textbf{5 Shot} \\
\hline
Test Accuracy \% & 78.47 & 89.66 & 80.9 & 91.27 \\
\hline
\end{tabular}
\centering
\caption{Compare the accuracy percentage.}
\label{tab:unsupervised-acc}
\end{table}

% \vk{Conclusion}


\section{Conclusion}\label{sec:algo:conclusion}
We successfully generates the vector presentation using IR2Vec for the POJ/OJ Dataset. Using this representation and the without any complex model architecture, we are able to get better results than the previous work for the supervised learning setting. On the other hand for few-shot learning, we are  able to cluster the unseen classes which were not the part of the training dataset.
This work would be extended to classify or identify the binaries files.