David,

There has not been all that much news about batch kNN. As an experiment,
I changed the implementation of the DP kernel, so that now it uses

vector<double>

rather than

hash_map<int, double>

as the accumulator, and that actually was useful. It increased the
filtering performance in our traditional NN classifier on the RCv1
corpus from 140 doc/min to 400 doc/min on an Apple computer that I
sometimes use for testing (a high-end consumer model, "iMac" with
something like 800 MHz CPU), or from 300 doc/min to **** on mms-01
(Andrei's Linux machine). 

I have not run all that extensive experiments; but, for example, batch
traditional kNN with k=60 and threshold=1.0 performs quite nicely on
the first 10,000 docs from the RCV1 test set; certainly much nicer
than batch Rocchio with the parameters that I happen to have in my
config file.  (Finding practically all P docs, fewer N, and way fewer
U). Of course, 10,000 docs is only a short stretch of the
720,000-documen TEST set that that TREC uses; and it would not
be surprising to see that adaptive Rocchio will ....

   ---	      ---	  ---

I will run a few more experiments, of course; but I suppose you should
not be surprised that what I am really interested in is not tinkering
with the batch kNN, but preparing for the more batch kNN work, which,
as I understand, you want to start in January.

So below is one observation concerning the future adaptive kNN work,
namely re-thresholding. 

As we know, setting the initial thresholding in kNN will be quite
expensive, but feasible: if the initial kNN doc pool is composed of
the 80,000 TRAIN documents, then, scoring them at the rate of *** 800
doc/min, we can perform the initial scoring in about 1.5 hours.
This is only, at most, an order of magnitude higher than what
it takes to train a 100 Rocchio classifiers (one per each of
the 100 queries).

How expensive will the threshold learning be? You do not specifically
discuss it in your specs, but it seems to me that it may actually be
cheaper than in Rocchio-like methods! In Rocchio, on every
re-training, we'd have, for each query, to fully re-score each of the
query's labeled set docs with the query's updated model. It's
likely that you already have this algorithm in mind, but still
I would like to mention it now.

With kNN, we can do the following. During the initial thresholding, we
will remember, for each document v in the doc pool its k closest
neighbors N_k(v)={w_1, ..., w_k}, and the distances to them. (Storing
this is affordable, in the sense that as long as k is smaller than the
average number of terms per document, this info takes less space than
our main inverted index).

When a new TEST document d is scored, we of course have to compute
sim(d,v) for this document d and each doc v in the doc pool. We should
not discard these scores immediately; instead, if a decision has been
made to add d to the doc pool, we should, for each v in the doc pool,
compare sim(d,v) against the stored similarities sim(v,w_1),
... sim(v,w_k) between v and its k neighbors {w_1, ..., w_k} in
N_k(v). If sim(d,v) is smaller than all these k values, then we now
that the k-neighborhood of v stays unchanged, and, therefore, the
score(v) with respect to the updated doc pool is the same as it was
w.r.t the old pool. On the other hand, if sim(d,v) is higher than some
of the sim(v,w_j), then we insert d into the k-neighborhood, replacing
the lowest scoring document w there, and re-compute the score of v
based on its new k-neighborhood.  If k is high, this re-computing can
in fact be made in an incremental way, that is (e.g., for traditional
kNN):

   Score(v,T, N_new) = Score(v,T, old) - l(w,T) + l(d,T),

etc. After all scores that need to be updated have been updated, we do
re-thresholding.

	--Vladimir


