# I have a bunch of sets. Some sets contain bad values. I know which sets have them, but not which values are bad.

My company sends email on behalf of many other companies. Hotmail tells us when we start sending spammy messages, but they only say "some of the emails this giant batch of messages had spammy stuff", and not specifically which emails were spammy. Those batches of emails contain stuff from lots of different clients we have, and I need to narrow down which clients are sending the spammy messages.

So, given a bunch of sets of emails we sent, and Hotmail giving us a "yay" or "nay" on each set, and given that emails and clients are 1:1 so it's easy to which client sent any given email in the sets, how can I tell which clients are probably the spammers?

(P.S.- I'm not the brightest math whiz in the box, so please explain your answer in layman's terms).

-
There might be ways to do this if we could assume that everything a spammer sends out is spam, and nothing a non-spammer sends out is spam. But if some clients send out a lot of non-spam and just the occasional spam, I think it will be very difficult. –  Robert Israel Apr 5 '13 at 22:03
If there were just one spammer, this would be the well-known puzzle with rats and 1000 bottles of wine. That should give you something to search for. A generalization with more poisoned bottles/spammers was discussed here: math.stackexchange.com/questions/639/… –  Samuel Apr 5 '13 at 22:14
We do get back more information than "there is some non-zero level of spam in this batch"- Hotmail tells us that a given batch is exceptionally spammy, or rather spammy in a particular way we care about- they are sending to spamtrap email addresses. –  spiffytech Apr 6 '13 at 4:31

## 2 Answers

If you have access to the bad batch, why not partition it by client? Then forward each partitioned batch to an email address your company owns to see which batch is flagged. Since every email in the partitioned batch belongs to one client, you'll know who the spammer is.

-

Here's a way you could model the problem. Suppose you have clients numbered $i=1,2,\ldots,M$, and each client has an associated probability $p_i$ which is the probability that they don't ruin a batch of messages with spam if they are included in the batch.

The simplest thing to do would be to say $p_i=0$ for spammers, i.e. they always spoil the batch. Then you could say the likely spammers were clients who never participated in a good batch of messages.

More elaborate, you could say that each spammer has the same probability of passing $p_i=\sigma$ and each non-spammer passes with probability $p_i=\nu$.

Then for a given set of clients $C$ in a batch, the probability of a good batch of messages is $$G_C = \prod_{i\in C} p_i$$ and the probability of a bad batch of messages is $1-G_C$.

Given a set of batches with client sets $C_1,C_2,\ldots$, the likelihood of getting the realized good/bad labelling back is $$P = \prod_{C_j~\mathrm{good}} G_{C_j} \prod_{C_j~\mathrm{bad}} (1-G_{C_j})$$

We can look for the maximum likelihood condition by maximizing $\log P$ \begin{align} L &= \log P = \sum_{C_j~\mathrm{good}} \log G_{C_j} + \sum_{C_j~\mathrm{bad}} \log (1-G_{C_j}) \\ & \simeq \sum_{C_j~\mathrm{good}}\sum_{i\in C_j} \log p_i - \sum_{C_j~\mathrm{bad}}\prod_{i\in C_j}p_i \end{align} to a first order approximation assuming $G_C$ is close to zero for bad batches. Then $$\frac{\partial L}{\partial p_i} \simeq \sum_{\mathrm{good}}\frac{1}{p_i}-\sum_{\mathrm{bad}}\frac{G_{c_j}}{p_i}$$ and we can look the best spammer/non-spammer classification by starting with and arbitrary labelling (say all non-spammer, e.g.), then reclassifying the clients with largest negative derivative as spammers, and/or those with largest positive derivative as non-spammers, then repeat as necessary until you converge to a (local) maximum.

Some variations of this approach would be to consider the probabilities on a message-by-message basis to account for different volumes, or to use something like the EM algorithm to also try to determine $\sigma$ and $\nu$. But since you asked for layman's terms I think I should stop here.

-
Can you please explain what the capital pi in your equations means? –  spiffytech Apr 22 '13 at 21:38
It means the product. To find the probability of a group of independent events all occurring at the same time (e.g. all messages in a batch are bad) we multiply together the probabilities of each event. –  Zander Apr 25 '13 at 1:34