%File: nlp-report.tex
\documentclass[letterpaper]{article}
\usepackage{aaai}
\usepackage{times}
\usepackage{helvet}
\usepackage{courier}
\pdfinfo{
/Title (Positive-only Semi-supervised Classification)
/Subject (CS 769: Project)
/Author (Chaitanya, Hidayath)}
 \begin{document}
% The file aaai.sty is the style file for AAAI Press 
% proceedings, working notes, and technical reports.
%
\title{Positive-only Semi-supervised Classification}
\author{Hidayath Ansari, Chaitanya Gokhale\\
University of Wisconsin-Madison
}
\maketitle
\begin{abstract}
\begin{quote}
%We discuss in this report, the task of binary classification on a test set,
%given a training set consisting of large number of unlabeled examples and a
%handful of examples belonging to one class. We will briefly explain all the
%approaches we have tried, the corresponding results and our future plans.

We discuss in this report, the task of binary classification on a test set,
given a training set consisting of large number of unlabeled examples and a
handful of examples belonging to one class. The task is part of the \textit{UCSD
Data Mining Contest 2008}.
\end{quote}
\end{abstract}

We are given 20 dimensional data from a real-world scientific experiment. The
training set consists of 68560 examples, of which only 60 are labeled positive
and rest all are unlabled. We are given a test set of 11427 unlabeled examples.
Our goal is to classify these into two classes, achieving highest F1 score. F1
score is given by
\begin{eqnarray*}F1 = \frac{2.P.R}{P+R}\end{eqnarray*}
where $P$ is Precision and $R$ is Recall.

In order to be able to guage our performance, we are given a quiz data set
consisting of 11427 examples, all unlabeled, for which we can submit our label
predictions once per day and obtain the F1 score.

\section{Initial Approaches}
First and foremost, we estimated the fraction of positve examples present in the
data, since this information would be useful irrespective the method we use for
classification.
We arrived at this estimate by finding the F1 score for the quiz
data, when all the examples are labeled as positives. We can rewrite equation for F1 score,
using the equations for Precision and Recall.
\begin{eqnarray*}
P = \frac{TP}{TP+FP} & R = \frac{TP}{TP+FN}\\
\frac{2}{F1} = & 2 + \frac{FP+FN}{TP}
\end{eqnarray*}
If we label all the examples as positives, then FN = 0, FP = total - TP.
As can be seen from the equation, by substituing these,
and the value of F1 score obtained, we can find TP. We found that there are
$\frac{1}{8}^{th}$ positive examples in the given data.

Next, we tried to use some of the most instinctive methods. As we discuss below,
some of them were just not worth trying while others performed miserably.\\

\noindent\textbf{Clustering:} We thought of clustering the given data to look
for any observable interesting patterns. However, at this scale we didn't have
the resources for an in-memory clustering algorithm. So we randomly sampled a
fraction ($\frac{1}{10}^{th}$) of the unlabled data and clustered it along with
the given positive data, using a variety of algorithms (hierarchical, spectral).
However, we couldn't find any patterns.

\noindent\textbf{SVD and visualization:} Considering the possibility that some
of the dimensions in the data might be adding noise rather than assist in
classification, we reduced the dimensions of the data, by taking SVD of the data.
We tried visualizing the data, taking the first 3 dimensions, however, no
discernible patterns could be seen.\\


\noindent\textbf{Bayesian Classifier:} 
The survey on Semi-supervised learning, \cite{Zhu05}, mentions Bayesian learning
 as one of the promising methods for our task. Unfortunately, that didn't seem 
to apply for our problem.

We estimated the feature-wise probability distribution for the data and assuming
independent features, we got the probability function for the complete data
vector. Thus, we computed $P(x)$ and $P(x|+)$, where x is any given example.
We can compute $P(-|x)$, as below:\\
$P(-|x) = \frac{P(x) - P(+).P(x | +)}{1 - P(+)}$

However, the number of positive examples is so small (60) in our case, that the
estimate obtained for the probability is highly unreliable. As a result, when
computing $P(-|x)$ we even ended up getting negative probablity values for some
of the examples!

\noindent\textbf{Co-training:} Starting with small number of labeled examples,
co-training can effectively classify the data. A separate classfier is
learned using each subset of features. The data points confidently classified by
one are used by the other for training, and vice-versa. This goes on
iteratively. However, for this to be effective, we need negative examples.
So, unless we have some reliable way of sampling negatives cotraining can't be
of any help. Also, there is an inherent assumption that, there are two subsets
of disjoint features in the data, s.t. each subset is sufficient to classify the data.


\section{Revised Plans of Attack}
SVM, Sampling negatives\\

\noindent\textbf{Nearest Neighbour}
% Copying from poster
%   NN can help detect a non-linear manifold structure in
%   the data. Most helpful so far. Several variants
%   - one-at-a-time
%   - batches
%     (Best results yet – in terms of F1 score)
%   - average distance
\begin{itemize}
 \item \textbf{Growing positive clusters:} On observing the data points added by the above nearest-neighbour approaches, we found that all these points are added as a result of being close to a subset of the given labeled positves. If in reality we have more than one disjoint clusters of positives, then with the above approaches, we might be completely missing one of the clusters. Hence, we first clustered the given positive examples (using hierarchical clustering) to form 5 clusters (the number was arrived at based on the inter-cluster distance distribution), and then let these positive clusters grow, using the batch-wise approach discussed above. The results obtained were worse than the batch-approach.

\item \textbf{Other approaches:} We tried few other ways of using nearest neighbour technique. One such variant is inspired from the k-NN classifier. The basic premise of this method was, if a data point has $p$ or more positive data points in its k-closest neighbours, then that data point can be labeled positive. We identified positives from the training data using p=2 and k=10 and added them to the given positves to form the 'seed' positives to be used for quiz set. Using the 'seed' positives, p=2 and k=20 we identified positive data points from the quiz set. Adding them to the seed, we continued the process for 4 more iterations. This approach performed worse than most other NN approaches.
\end{itemize}

\noindent\textbf{One-class SVM:}
One-class classifier \cite{Man01} learns a function that maximally covers the examples of a given class. We used the \texttt{LibSVM} implementaion of one-class SVM. Starting with the given positive examples, we tried to learn and iteratively improve our one-class classifier for the positive examples. In each iteration, we would add the unlabeled examples from training set, identified as positives by the one-class SVM, to our training set for the next iteration. We continued for about 8 iterations. We used this final classifier to label the quiz set examples. The performance was very much comparable to the nearest neighbour, but there wasn't any improvement over our current best.

\section{Results}
add few more from past plus the table from poster
\section{Future Plans}
disk-based clustering - cludo
\bibliographystyle{aaai}
\bibliography{ansari}

\end{document}
