Re: mailreaver "--undo" ambiguity

TL;DR below: undo ain't simple and is not even feasible for some.
Special sauce for winnow needed. Acting more sophisticated than the
Bayesians and you're t ^H roast.

--------------

Couple of things:

1) --undo is only really doable for the bayesian classifiers =
Markovian/OSB/OSBF/Winnow
(hypespace is 'doable', but no code exists for this operation yet, and
when it would, it's still an approximation given timeline scenarios
like this one: train A, train B, train C, oops!-->undo B  which would
require removal of the B data from the CSS database but thanks to
optimizations, it /may/ already have been re-used in part or whole by
the subsequent train.C activity. Untangling that is not exactly simple
(at leas not for me). The short end is that proper 'undo' for HS is a
tough cookie. NN (Neural Net) 'undo' is out as well; can't say for
SVM/SKS/... but my bet is undo is a no-no there as well.

Which is a roundabout way of saying that crm114 does not store a true
transaction log (that would take extra time and storage, which only
slows us down [quite a bit] in regular operating conditions).
Ergo: caveat emptor.


2) what you're asking ('autodetect' class when requesting an 'undo'
operation) is doable when there's a reavercache living underground and
your message is located in said cache, like Bill said. HOWEVER,
there's the semantics regarding 'undo' itself.
There's three possible ways to define 'undo':
a) undo the training of message M == make it appear as if the given
message M was not trained that last time into the given class. [Bit
fuzzy wording, but you can train a message M multiple times [*]]
b) undo the training of message M == rollback the trainings up to and
including the last training of message M so as to make it appear as if
message M (and any follow-up trainings) never happened. [Usage can
restrict undo in this definition to limit rollback to one message at a
time only: This is quite similar to UNDO in  word-processor or other
user systems: undo ~ rollback.  This differs from definition (a) as
there 'undo' is not /exactly/ a rollback given earlier mentioned
timeline scenario: undo.B means untrain.B, while C remains trained,
while a /rollback/ semantic would implicitly rollback C as well.]
c) undo the training of message M == make it appear as if the given
message M was not trained into the given class but was trained into
the opposite class instead.

Intuitively, definition (a) makes the most sense.
Both a) and b) implementations would remove the message M from the
reavercache (maybe moving it to the unknown dir as Bill suggested, but
do we want to have any recollection of that message anywhere in the
system after the undo? It depends on /why/ you wanted that 'undo' to
happen...)

a) can be extended to act like c) by adding a subsequent --train
instruction for that message into the opposite class.

a) + b) will get rid of the message; c) will swap it over to the other
side, hence c) is never really getting rid of it.

Nothing wicked there, it's just that 'undo' is used as a word for
different actions in different systems, so picking your definition is
important.


3) Second caveat is closely related to the [*] up there and applies to
all of a), b) and c), i.e. to any which way you want to do your
'undo':

You can implicitly and explicitly train a message M multiple times.
'implicitly' thanks to circumstances-du-jour and the training
algorithm (SSTTT / THTTR / whateveryacallit) inside mailtrainer: you
can set up mailreaver (default, even) to repetitively train a message
M into a given class C until it's subsequent classification score
surpasses a given threshold. ('Thick Threshold' training). mailtrainer
adds a bit to that basic approach to prevent infinite training loops
by clipping the training count to an upper limit.)
The implicit training rounds count depends on all training history (==
all previous trainings, as those all influenced the CSS and thus
impact the current training round) /and/ on the fact if message M was
trained alone or in a bulk mailtrainer run (something about the +0.5
counting in there and the way unequally sized bulk training lists are
processed exactly in mailtrainer -- out of scope for this email).
Anyway, glossing over a lot of crufty detail, you may guestimate
between 1(0?) to 5 training rounds happening per --train M.
That's the /implicit/ rounds.

Then there's nobody stopping you from multiple invocations of
mailreaver/mailtrainer for the same message M, i.e. you invoking
mailtreaver with --train for message M. That'll be you strengthening
the training of M /explicitly/.

crm114 keeps track (in a way) of the number of times you trained a
/class/. It does /not/ keep track of the number of times you trained a
/message/.

And that's the real kicker!


Given two messages A and B, both trained. As you may recall, messages
are cut up and munched and turned into 'feature' sequences, where the
thing that's recognized, classified and trained is /features/. Say
message A and B have a feature F in common. message A may have a
feature G that's unique for that message, but /we do not know that/.
Training is, for undo purposes, identical to counting feature
occurrences, (And I'll ignore <unique> for now, as this is enough for
a solid, throbbing headache already, I'm sure. ;-) )
Anyway, when training is just counting +1 for each time the crm14
goblin sees a feature F pass by, undo would be counting -1 for each
feature F in our to-be-undone message M, right?
Well, trouble is.... nobody can tell you /afterwards/, how many times
that message was trained /implicitly/ or /explicitly/; all we know is
it got trained. Period. Maybe once, maybe more times.
So 'undo' (i.e. <refute>) /can/, in a way, 'remove' /one single round/
of training of message M, but it cannot know if that is exactly what
happened before. 'One round of training' is /not/ 'one training'.

Your original --train M may have taken two rounds, so the message M is
still lurking in the class at half strength after one <refute>.
And the **** is we don't know how many rounds of <refute> we need for
a complete undo. Besides, do we want to 'undo'-style (a) that last
explicit --train M run only, or do we want to undo /all/ explicit
--train M runs that happened until now?
And no matter which of these we pick, how many rounds of <refute>
would it take exactly?
We do not know.

We do not keep track of the number of training rounds per training,
nor how many times a given message was trained /explicitly/. So 'undo'
remains guesswork.




Conclusion:

Given a live reavercache, finding out if your message is in the cache
and hence in which class it is sitting is easy (foregoing the
situation where the caller trained a message into both classes at some
time -- which may be considered a user error, but it can happen,
resulting in an ambiguous situation regarding which class to 'untrain'
from)

However, we'll never be able to properly 'undo' a training or 'all
training' of any given trained message in that cache as we don't know
how many rounds it took to train the bugger, and we need that info
when we want to get close to an effective 'undo' either way.

Given all that, and assuming we solve that conundrum, there's still
(1), which says undo/refute is only technically doable for the
bayesians (markovian/OSB/OSBF/Winnow), /maybe/ doable for HS given
special conditions, a no-no for NN at least, and a 'Bill knows, me
doesn't' for the others so 'undo' is highly dependent on classifier
(and options) used as well.



That ain't gonna be a simple patch for mailreaver/mailtrainer, folks. ;-)



The above is the elaboration / explanation of this little note:

> Note that you won't get a 'perfect' undo (unless a series of
> particular conditions are met). Hence, in actual practice, it's an
> /approximation/ of an undo.

As an approximation, undo won't be close, even.



PS: if you want a 'real' undo, the way out is a full 'replay', i.e.
start with empty fresh CSS and replay all trainings, except the one(s)
you wish to undo, /in the same order/ as you did them before, into the
relevant/affected class(es).



PPS: For those who can handle a little extra: if my latest intel is
correct, mailreaver/mailtrainer is /not/ fit to handle WINNOW as it
mandates symmetric training and vanilla mailtrainer doesn't do that.
Train into class spam for winnow means you must train into class spam
and <refute> train into class <good> /every round/. Things go
pearshaped very quickly when you don't.
'undo'-ing a winnow-training round is a little wicked as it must be
symmetrical as well, but flip that <refute> to the other side. That
doesn't happen today, IIRC.





On Fri, Jun 26, 2009 at 9:22 PM, Bill Yerazunis<[email protected]> wrote:
>
>   From: Paul Fox <[email protected]>




-- 
Met vriendelijke groeten / Best regards,

Ger Hobbelt

--------------------------------------------------
web:    http://www.hobbelt.com/
        http://www.hebbut.net/
mail:   [email protected]
mobile: +31-6-11 120 978
--------------------------------------------------

------------------------------------------------------------------------------