Adaptive Filtering Software: Local Learning Package
Dmitriy Fradkin
Last update:
The basic idea of local learning is that, given a new example (a test case), k examples nearest to it from the training set are used to construct a classification model specifically for this example. While such approach is clearly slow, according to the literature it can lead to high accuracy.
This package consists of several stand-alone programs that can be combine together with classification tools (such as BBR software) to produce local classification models. These programs were used in our local learning experiments.
The code was written in C++, using STL. Compilation was tested with GCC 3.3.5. To compile code, move to the directory "afs/local/src" in the location where the contents of the MMS CD were copied, and type "make all".
This will produce four executable files in directory "afs/local/src": kNNcompute, kNNclassify, makeTests, InvertedModels. Their usage is described below.
First we describe the usage of individual programs available as part of the Local Learning Package. Then we describe some scripts that can be used to combine them together.
The purpose of this program is to pre-compute an ordered list of neighbors from the training set for each example in the test set. The program requires the name of the training set file, test set file, choice of similarity measure (L2 distance, cosine measure, L2 distance to projection) and the maximum number of neighbors to list. The output is a set of files (one for each test example) listing the ids of nearest vectors. The vectors in the training and test files should be specified in a sparse vector format, with the first field being the vector id.
Usage: kNNcompute[options] p, print : Print vectors (1) or not (0 - default) T, train : Train file name (required) t, test : test file name (required) m, maxN : maximum number of neighbors to record (default 0 - will use all training points) s, similarity : measure of similarity: Euclidean distance, cosine, project+distance (0 - default ,1,2) h, help : print this message
The purpose of this program is to perform kNN classification for a single example A for multiple values of k (specified in an input file), using the file of nearest neighbors (another parameter) produced by kNNcompute. Multiple topics can be handled at once, by using an appropriate qrel file.
The format of the qrel file is as follows. Only positive judgements are included. Each line contains information for a single document/topic pair:
topic_name doc_id 1
The file with values of k contains a single value of k in each line:
k_1 k_2 ... k_n
Usage: kNNclassify[options] k, knnfile : name of the file of neighbor ids (required) K, K : file with numbers of neighbors (required) Q, qrel : qrel training file (required) i, id : id of the current doc h, help : print this message
Given a file with training vectors, a file of nearest neghbor ids for some vector A, and the parameter k, this program will produce a file of vectors corresponding to the k nearest neighbors of A. If qrel file is specified, a separate file will be produced for each topic, with appropriate labels in the first field. Otherwise, a single file will be produced with vector ids in the first field of each line.
Usage: makeTests[options] T, train : Train file name (required) k, knnfile : knn file name (required) K, K : number of neighbors (required) Q, qrel : qrel training file h, help : print this message
This is stand-alone program for classification with Inverted Index of Logistic Models. It requires a file of models (in sparse vector format) and a file of test vectors (in sparse vector format). If an output file is specified, all results will be stored there; otherwise a separate file will be written for each test case. The output has the form:
model_id doc_id Pr(model|doc)Note that the dot product between model and document vectors undergo logistic transformation.
Usage: IndexModels modelFile testFile outputFile(optional)
Directory "local/sample-data" contains files:
Below we provide brief examples of the usage of programs and sample scripts. The scripts (which can be found in directory local/sample-scripts) themselves contain comments that describe their functioning.
Before using local learning it is necessary to prepare lists of neighbors (to save on multiple similarity computations). This can be done as follows:
> cd local/sample-data > mkdir nnlists > cd nnlists > ../../src/ > ../../src/kNNcompute -T ../Train.dat -t ../Test.dat -m 100 >& logFor each test document this produces an ordered list (closest first) of the 100 nearest neighbors from the training set. The output file format is:
"distance/similarity" "vector_id"The file name for vector with id A is A.knn
Now that the lists are ready, kNN or local learning can be done. Script localLearn-kNN.sh can be used to do kNN classification with multiple values of k and for many topics at once. For example, from sample-data directory:
> mkdir nnclassify > cd nnclassify > ../../sample-scripts/localLearn-kNN.sh >& logThe file of results (all-plain.res) has the following format:
topic1 doc1 true_label k1:pos:neg k2:pos:neg ... topic2 doc1 true_label k1:pos:neg k2:pos:neg ... ... topic1 doc2 true_label k1:pos:neg k2:pos:neg ... topic2 doc2 true_label k1:pos:neg k2:pos:neg ... ...In each triplet k1:pos:neg k is the neighborhood size, pos is the number of positive examples, and neg is the number of negative examples. To extract preditions for a particular $topic, with threshold $q:
grep "^${topic}\ " all-plain.res | awk -v thres=$q '{printf("%s ",$3); for(i=4;i<=NF;i++){split($(i),b,":"); v=(b[3]==0) ? 1 : (b[2]/b[3]>thres); printf("%d ",v);} printf("\n");}'
Local learning experiments can be done with the script localLearn-lemur.sh. For example, from sample-data directory, to run with k=20 and prior variance=10:
> mkdir nnlearn > cd nnlearn > ../../sample-scripts/localLearn-lemur.sh 20 10 > log-20-100To run with variance determined with cross-validation:
> mkdir nnlearn > cd nnlearn > ../../sample-scripts/localLearn-bbr.sh 20 0 > log-20-0These runs do take a lot of time!
The work was partially supported under funds provided by the KD-D group for a project at DIMACS on Monitoring Message Streams, funded through National Science Foundation grant EIA-0087022 to Rutgers University.
Software is free for non-commercial use.
Software is provided as is, without any guarantee or warranty. DIMACS or authors are not responsible for implications from the use of this software.
Questions, comments, bug reports welcome by email: dfradkin@cs.rutgers.edu