	Adaptive Filtering Tool Guide
	=============================

	I. Directory layout
	--------------------

Once you unzip the archive with "unzip filter.zip", you will have
the directory "filter" with subdirectories 
	"src": source code (*.cpp)
	"include": source code (*.hpp)
	"doc": documentation
	"data": sample data files

	II. Compiling
	-------------

To build the filtering tool, you need to know where the LEMUR tollkit
is installed on your machine.

Since the LEMUR main library file (liblemur.a) is not very usable (as
Andrei has noted, the LEMUR people have used a library-of-libraries
layout, which my linker cannot understand), you need to create a
subdirectory $(LEMUR)/lib-split, and unpack the file
$(LEMUR)/lib/liblemur.a into lib-split. This can be done e.g. with

cd /usr/local/lemur
mkdir lib-split
cd lib-split
ar xf ../lib/liblemur.a 

Go to the directory "filter/src".  Edit the file "Makefile" in that
directory, setting the appropriate value for the variable $(LEMUR)
(which should point to the directory where LEMUR kit is installed).

Now, run "make". This should compile all source files and build
the main application, "AdaptFilter".

At home, I compile and build with GCC 2.96 on a RedHat 7.1 Linux
platform. I don't foresee encountering any problems on other similar
platforms.

	III. Source code overview
	-------------------------

[This section is geared to potential code developers, and is of no
interest to end users.]

I tried to design the Adaptive Filtering tool so that it would use as
much of the LEMUR API as possible. It is designed so that it could be
easily used by somebody familiar with LEMUR, and, if desired, and
could later be integrated into LEMUR toolkit itself without
significant changes. The filtering code is structured in a manner
similar to that in which the retrieval code is structured in LEMUR.
LEMUR naming conventions etc. have been followed whenever possible.

LEMUR has abstract classes QueryRep and RetrievalMethod that abstract
the common functionality of retrieval methods, and an application
RetEval that can use any of the currently implemented concrete
retrieval methods. Similarly, my code has abstract FilterQueryRep and
FilterMethod, abstracting the common adaptive filtering functionality,
and the application AdaptFilter that can use any of the available
adaptive filtering methods. Currently (August 2002) only one filtering
method, RocchioFilterMethod is available.


	IV. Running the filtering program
	---------------------------------

A sample shell script "rocchio.sh", parameter file, and data files are
provided in the directory filter/data. The main file is "rocchio.sh";
read it to see how things work.


The filtering program expects to find the following input data:

1. The query database, pre-processed with LEMUR's ParseToFile and
BuildBasicIndex tools. It should list all queries you want to run
filtering with. (Why am I using ParseToFile and not ParseQuery?
Because the LEMUR sample script, test_basic_index.sh did so, and it
worked fine.)

2. The training set (TRAIN) database, pre-processed with LEMUR's
ParseToFile and BuildBasicIndex tools. This database will be
interpreted as the training set for the filtering run. This database
will be used by the filtering tool to obtain aggregate information
about training set.

3. The "main database", which must include all the documents from both
TRAIN and the test set (TEST), pre-processed with LEMUR's ParseToFile
and BuildBasicIndex tools.  This database may also include any other
documents (for example, the texts of query topics) but they will be
ignored.  This database will be used by the filtering tool to obtain
per-document information (TF, doc size) for each document when the
time comes to process it.

4. The TEST document order file, in the TREC format, which must list
the documents constituting TEST, in the order in which they will be
processed.  Note that if a document contained in the main database
neither appears in the TRAIN database nor is listed in the TEST
document order file, this document will be completely ignored for all
intents and purposes.

6. The QREL files for TRAIN. It should only contain the judgments that
will be used to train the filtering program.

6. The QREL files for TEST. It will be used as the "Oracle" when 
the filtering program wants to send a document to the experts for
their judgment.

7. The parameter file.

The query processor and the indexer use their own parameter files, and the
stopwords list.

Please refer to the file dat/rocchio.sh to see how the things work
together. It is a complete script that starts with the 3 SGML files
(for Queries, TRAIN, and TRAIN+TEST), pre-processes them, and then
runs the filtering tool producing the results file (list of documents
that have been sent to the Oracle during filtering). You may want
to edit the file first, modifying the following variables, if
necessary:
	$lemurbin : where the LEMUR standard executables are
	$mybin : where the filtering tool is
	$orig : where the input files are taken from 
	$run : the runtime directory. (The script rocchio.sh copies
	   input files from $orig to that directory, and runs all programs in it)

The program prints a lot of progress informartion to the standard
output (which is redirected to a log file in rocchio.sh), and produces
the main result file -- list of files to be sent to the Oracle -- in the 
file  res.filter_rocchio. Every line in the file is in the format

Q-id D-id J

where Q-id and D-id are the query id and the document id, while J
is the "judgment" which is always 1. One can change the format by
modifying the resultFormat parameter in the filter_param file:

resultFormat = 0; /* 0 = simple-format; 1 = TREC-format */

What input files are available?

(a) Set 
orig=orig-cacm-full

to use a small database (300 docs in TRAIN, ~2900 in TEST; short docs;
64 queries; very few judgments per query) that I have fashioned from
the CACM dataset that comes with Lemur.  A nice small set, you can
figure things with paper and pencil, but the docs are very short, and
the qrel file only has positive judgments.  No real negative feedback
here. The actual computational part of the run (training + test set
processing) takes about 21 sec on my home PC (a one-year-old run of
the mill consumer machine), or 160 sec (67U + 92S) on aplab (a 5-year
old Sun). The actual computational results (lists of selected docs)
are, of course, very similar on both machines. (You probably can achieve
virtually identical results on different platforms by synchronizing
the random number generators).

(b) [To come soon]
orig=orig-ap-small

A small database based on one training and one test file from the AP
collection. [This is not completed yet, since I am not sure about qrels].



	V. More on parameter files.
	---------------------------

There are several groups of parameters; dot (".") in the parameter
name serves for logical grouping. 

The filter_param script contains all, or almost parameters defined in
it; they are arranged by groups, with some comments. More details on
parameters semantics can be found in the comments next to the
parameters declarations in FilterParamManager.hpp,
RocchioFilterMethod.hpp, and AdaptFilter.cpp.  Look for the
"namespace" keyword in each file... there are several of those.

Many parameters are the same as for Lemur's retrieval program.  Some
parameters which do not exist in retrieval program, or whose meanings
are different; take a look at the comments in the param file. In particular,
note how setting cache.maxDocCacheSize and updateFreq affect performance.

All parameters for LAD control are listed and properly documented
in include/LADParamManager.hpp


	VI. Performance tuning
	-----------------------

1)  updateFreq = 1;
This parameter specifies how often (after how many judgments) the 
classifier will be updated. Changing it *will* change the results; 
longer interval between updates (say, updateFreq=5) may make
the classier worse (less adaptive), but will make the
program run faster (fewer re-scoring needed).

If you set updateFreq=-1, the classifier will be never re-trained
after its initial training on the TRAIN set; this, is exactly what's
referred as "batch filtering" by many people. 

2) cache.maxDocCacheSize = 10000;

[For compatibility with older versions, it is OK to use the old
parameter name, as in
maxDocCacheSize = 10000]

This parameter sets the size of the document cache. It does *not*
affect the results (the computations stay the same), but controls 
the implmentation details: namely, how many docs' TF data can be stored
in the RAM cache, in a pre-processed format.

After you've run the program:

% ../../filter/src/AdaptFilter filter_param > filter.log


Take a lok at the output file:

% grep -A1 'Doc Cache destructor' filter.log
Doc Cache destructor. Max size=10000, current size =3204 docs.
Since startup, inserted: 3204 docs; removed: 0 docs

This output shows the doc cache statistics over this run. In this runm
the doc cache was configured to store up to 10000 docs; only 3204 was
actually put in, so no cache flushing was necessary.

But if you ask for a smaller cache...

Doc Cache destructor. Max size=1000, current size =1000 docs.
Since startup, inserted: 161885 docs; removed: 160885 docs

This is a run with the same data, but the cache of only 1000 docs max
capacity. As a result, the cache was flushed in and out all the time
(161,888 insertions), so it was not particularly useful. (It still
*was* somewhat useful -- during the early parts of filtering run
for each query, before the number of labeled examples for that query
exceeded 1000).

3)     
cache.cacheAllDocs=0;

If this flag is set to 0 (default), a document is cached only at the
moment when it is known that it will be re-scored (that is, a TRAIN
doc after it has been pseudo-labeled, and a TEST doc after a
non-trivial judgment about it has been obtained from the Oracle). If
this flag is set to 1, all documents will be cached -- even those
which are only scared ones.

On large data sets (like AP or RCV1) you should use the default setting
(0), to avoid cluttering the doc cache. On a very small data set
(where you can afford to set cache.maxDocCacheSize > |TRAIN|+|TEST|),
setting cache.cacheAllDocs=1 will, of course, improve the performance
of a multi-query run greatly, since the entire corpus will be cached,
and all queries after the first one will be able to completely
avoid accessing the index files on the disk.

There is no harm in setting cache.maxDocCacheSize much higher than
needed; setting this parameter, per se, does not cause any additional
mwemory allocation; it simply controls when insertion into cache will
trigger removal of some existing elements from the cache.

4) 
cache.clearForEachQuery=1;

Currently, the default (1) will completely clear the cache between
queries; setting cache.clearForEachQuery=0 will let docs from previous
queries accummulate in the cache, so that when the cache overflows, it
some documents will be removed using a rather imperfect removal method
that we currently implement. Using the default (=1) makes performance
on a multi-query run more predictable, though, most likely, less 
fast, than with =0. You can experiment with this parameter to see
what works better in your circumstances.

5) 
cache.termCache=false;

Not supported yet. In the future, will be used to activate a second-level
cache, to optimize computing dot products during doc re-scoring.

6) 
queryBatch = 1;

This parameter specifies how many queries are processed "in parallel".
If you set, for example,
	queryBatch = 10;
it will mean that queries will be processed in batches of 10, and
the amount of TF data read from the disk will be reduced almost by
the factor of 10 compared to the default (queryBatch=1). In most
situations, it is advantageous to set queryBatch as high as possible
(up to the total number of queries you have), as long as you
don't run out of RAM space. You may monitor RAM usage by using 
programs such as "top".

When setting queryBatch, don't forget to increase
cache.maxDocCacheSize appropriately, so that it could hold the
combined S'+S for all queries in the batch at the same time. Consider
the following example (RCV1 corpus): |TRAIN|=80,000, |TEST|=720,000,
average number of true labeled examples in qrel per query |S|=400. If
your pseudo-feedback paramters are set up so that you select the
top 2% of |TRAIN| as P', and 5% of the remainder as N', then if
you are running just one query at a time, you'd want you 
cache.maxDocCacheSize to be no lower than

	2% * |TRAIN| + 5% * |TRAIN| + |S| = 5,600+400 = 6,000.

(In reality, you'd want to set it a bit higher, consider that different
queries may have different number of labeled examples in qrel). If
you are running queryBatch=n queries at a time, the minimum 
required cache size is

	 5% * |TRAIN| + n * (2% * |TRAIN| + |S|) = 4,000 + n*2,000.

(Note that you don't multiply |N'| by n, since the psudo-negative
sets are designed to be strongly overlapping). Thus, for queryBatch=10,
you would need at least cache.maxDocCacheSize=24,000. (Again, it
is a good idea to make it a bit higher; there is no harm in it).


	

	VII. Profiling using the Account class
	--------------------------------------

Do

% tail -40 filter.log

to see some profiling info: time in seconds spent in various
functional parts of the program. To see what various parts
correspond to, you may want to do 

% grep -n _ACC *.cpp 

and then look at the correpsonding parts of code. Typically,
a procedure may have code like this:

{
	Account acc(SOME_ACC);
	// the time spend here will be credited to SOME_ACC
	acc.reassign(OTHER_ACC);
	// the time spend here will be credited to OTHER_ACC
	{
		Account acc2(N2_ACC);
		// the time spend here will be credited to N2_ACC
	}
	// the time spend here will be credited to OTHER_ACC again
}

As you see, to start a timer, you create an Account object, or
reassign an existing one; the timer stops when it is reassigned, or
when the destructor runs (that is, when the end of block or a return
statement is reached). In the example above, all timers are
"exclusive": only one exclusive timer runs at a time, and when the
N2_ACC timer starts, the OTHER_ACC timer is suspended.

There are also a few non-exclusive timers, which have a second
argument in the constructor:
	Account totalAcc( TOTAL_ACC, false);
A non-exclusive timer will run all teh time until its
destructor kicks in, independently of all other
exclusive and non-exclusive timers.


	VIII. Tracing information
	-------------------------

As requested by David Lewis on Aug 25, 2002, the following tracing
information can be produced by the program. Note that producing this
information is *expensive*: it may make the program take twice as
much time as without tracing. This should not be surprising --
"reflection" about dot product usually will cost more than the
dot product itself!


Capability 1. Optionally trace the k highest (k specified in
configuration file) coefficients of the linear model, each
time the model is updated. Something like this:

MODT: Q=R101 LINEAR CLASSIFIER
MODT: Q=R101 THRESHOLD: 8.849
MODT: TOP  4  MODEL COEFFICIENTS:
MODT:       brazil 2.873
MODT:       coffee 2.380
MODT:       south 1.378
MODT:       argentin 0.944

A unique key ("MODT") is used at the beginning of each
line, so that these lines from the trace can be grepped out
separately from the others if desired.  

The following config file parameter controls the number of top 
terms printed:

trace.MODT.k = 0;

If the value is 0, only the header (with the new threshold value) is
printed with the "MODT" key; if negative, nothing is printed at all.


Capability 2. Optionally write a single trace line for each
document for which score >= m * threshold. 'm' is specified
in configuration file, and allows us to see, e.g. all documents
within 90% of the threshold.  The trace line would include:

  a1. query id (this is needed to distinguish output of different
  queries in  multi-topic  batches)


  a2. doc id

  b. document label (positive, negative, unknown). Note this
would require consulting oracle for some documents that
don't pass threshold.

  c. document score

  d. current linear classifier threshold

  e. top n values of (linear model coefficient * within
document weight)

The resulting trace info might look like this:

DOCT: R101 14103 Rel 14.948>12.775 brazil 1.58*2.38 coffee 1.04*2.59 market
2.39*1
DOCT: R101 16288 Non 10.601<11.112 coffee 1.04*4.30 intercontinental 3.88*1
transcontinental 1.04*1.40
DOCT: R101 28300 Unj 12.601>11.009 coffee 1.08*3.71 ocean 1.32*2.90 cargo 2.01*1

This allows quick impression of threshold, model weights,
feature selection, and within document weights as the
classifier evolves.


Capability 3: Roughly the same as Capability 2, but for the
labeled documents used during retraining of threshold.
Lines in this case should be sorted by score, should include
include the weight of the example, but don't need to include
the threshold.  Something like this:

THRT: 114103 Rel(1.0000) 14.948 brazil 1.58*2.38 coffee 1.04*2.59 market
2.39*1
THRT: 228300 Non(0.0038) 12.601 coffee 1.08*3.71 ocean 1.32*2.90 cargo
2.01*1
THRT:  16288 Rel(0.0038) 10.601 coffee 1.04*4.30 argent 3.88*1 brazil
1.04*1.40

Computational costs of tracing.

"MODT" is inexpensive: it only searches thru Q_up for the k highest
coefficients; so its cost can be disregarded compared ot the cost of
re-training the classifier, in whose context it is done.

"DOCT", when you consider it done on one individual document, is
actually quite a bit more expensive than the filtering procedure
performed on that document. (It is much more expensive to *reflect*
about a dot product that to simply compute the dot product! And I also
do not parallelize DOCT report preparation, as I do the actual dot
product computation). If trace.DOCT.m is >=1.0 -- then overall cost
using DOCT is still small, since only a few documents get the DOCT
treatment, and those documents are going to trigger much more
expensive classifier re-training anyway. If trace.DOCT.m is only a
little below 1.0 (e.g., trace.DOCT.m =0.9), then the cost of DOCT is
likely still small, since the total number of docs that get the DOCT
treatment is still comparable to the number of retrainings. However,
as you reduce trace.DOCT.m toward 0.0, the costs of doing DOCT will
become overwhelming -- much much higher than everything else in the
program!

"THRT" is only done on classifier re-training; so it is quite
affordable if you report only on a few highest-ranking docs (e.g.,
trace.THRT.n=5). But its cost is linear in n, so you'd better keep 
n reasonably low.

There is a "Tracing" line in the performance report at the end of the
log file, so you can see how much it actually cost you.


	IX. Output files
	----------------

(As of Jan-22-2003)

The application writes "contingency tables" for the training
set and the test set into two files, whose default names are
	trainTable = train-table;
	testTable = test-table;

You can specify the names of these files in the config file; or, more
usually, The shell script that invokes the AdpatFilter application
will rename those files, upon the termination of the AdaptFilter
run, so that they will have unique names.

Each file contains one line per topic, with the following syntax:

topic_id Rel_Ret Unj_Ret Nonrel_Ret Rel_NonRet  Unj_NonRet Nonrel_NonRet

For the test set contingency table, Rel_Ret, Unj_Ret, Nonrel_Ret are
the numbers of P/U/N documents in the test set that are "discovered"
(retrieved) by the classifier; Rel_NonRet, Unj_NonRet, Nonrel_NonRet
are the respective numbers not discovered by the classifier.
Therefore, the 6 numbers should sum to the total number of documents
in the test set.

For the training set contingency table, the numbers should be
interpreted in a similar way. A document is counted as "discovered" if
the classifier for the topic, *as it existed after the initial
training*, would select it. However, the document counts in each line
are not necessarily for the entire training set; rather, they are
document counts in the *initial labeled set* for the particular topic.
This would make a big difference in case of e.g. a Rocchio run on a
corpus whose labeling is interpretd in the TREC fashion (where the
initial labeled set only contains documents explicitly labeled in the
QREL file, plus the pseudo-labeled ones). However, there is no
difference in case of a kNN run on a corpus that's interpreted as
"fully judged" (as in our SIGIR'03 runs); there, the entire training
set serves as the "labeled set" for training.


Historic Note: prior to Feb-6-2003, the breakdown of documents in the
contingency tables into P/U/N followed the explicit labeling present
in the QREL file. Therefore, in case of a "fully judged" document with
a LYRL-style QREL file (like in SIGIR'03 runs), the "N" counts in a
test-table or train-table file were be always 0, and you had to
interpret the "U" counts as the "N" numbers for the purposes of the
efficiency calculations. This is not an issue now, as long as
test.fullyJudged and train.fullyJudged flags are properly set.



