Tengo un montón de juegos. Algunos conjuntos contienen valores malos. Sé qué conjuntos los tienen, pero no qué valores son malos.

Question

Mi empresa envía correos electrónicos en nombre de muchas otras empresas. Hotmail nos avisa cuando empezamos a enviar mensajes de spam, pero sólo dice "algunos de los correos de este gigantesco lote de mensajes tenían cosas de spam", y no específicamente qué correos eran de spam. Esos lotes de correos electrónicos contienen cosas de muchos clientes diferentes que tenemos, y tengo que acotar qué clientes están enviando los mensajes de spam.

Así que, teniendo en cuenta un montón de conjuntos de correos electrónicos que enviamos, y que Hotmail nos da un "sí" o un "no" en cada conjunto, y teniendo en cuenta que los correos electrónicos y los clientes son 1:1 por lo que es fácil saber qué cliente envió cualquier correo electrónico en los conjuntos, ¿cómo puedo saber qué clientes son probablemente los spammers?

(P.D. - No soy el más brillante de los magos de las matemáticas, así que por favor explique su respuesta en términos sencillos).

Answer 1

Si tienes acceso al lote malo, ¿por qué no lo divides por cliente? A continuación, reenvíe cada lote particionado a una dirección de correo electrónico de su empresa para ver qué lote está marcado. Como cada correo electrónico del lote dividido pertenece a un cliente, sabrá quién es el spammer.

Answer 2

Esta es una forma de modelar el problema. Suponga que tiene clientes numerados $i=1,2,\ldots,M$ y cada cliente tiene una probabilidad asociada $p_i$ que es la probabilidad de que no arruinar un lote de mensajes con spam si están incluidos en el lote.

Lo más sencillo sería decir $p_i=0$ para los spammers, es decir, que siempre estropean el lote. Entonces se podría decir que los probables spammers eran clientes que nunca participaron en un buen lote de mensajes.

De forma más elaborada, se podría decir que cada spammer tiene la misma probabilidad de pasar $p_i=\sigma$ y cada uno de los que no son spamers pasa con probabilidad $p_i=\nu$ .

Entonces, para un conjunto determinado de clientes $C$ en un lote, la probabilidad de un buen lote de mensajes es $$ G_C = \prod_{i\in C} p_i $$ y la probabilidad de un lote malo de mensajes es $1-G_C$ .

Dado un conjunto de lotes con conjuntos de clientes $C_1,C_2,\ldots$ la probabilidad de recuperar el etiquetado bueno/malo realizado es $$ P = \prod_{C_j~\mathrm{good}} G_{C_j} \prod_{C_j~\mathrm{bad}} (1-G_{C_j}) $$

Podemos buscar la condición de máxima probabilidad maximizando $\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} $$ a una aproximación de primer orden suponiendo $G_C$ se acerca a cero para los lotes malos. Entonces $$ \frac{\partial L}{\partial p_i} \simeq \sum_{\mathrm{good}}\frac{1}{p_i}-\sum_{\mathrm{bad}}\frac{G_{c_j}}{p_i} $$ y podemos buscar la mejor clasificación de spammer/no-spammer comenzando con un etiquetado arbitrario (digamos todos los no-spammer, por ejemplo), y luego reclasificando los clientes con la mayor derivada negativa como spammers, y/o aquellos con la mayor derivada positiva como no-spammers, y luego repitiendo según sea necesario hasta converger a un máximo (local).

Algunas variaciones de este enfoque serían considerar las probabilidades mensaje por mensaje para tener en cuenta los diferentes volúmenes, o utilizar algo como el Algoritmo EM para tratar de determinar también $\sigma$ y $\nu$ . Pero ya que me has pedido términos de lenguaje llano, creo que debo parar aquí.