Teora de la comunicacin 75.19 Implementacin de Redes bayesianas mediante una aplicacin para la deteccin y el filtrado de SPAM Esteban Calabria 78711 16 de agosto del 2006Teora de la comunicacin 75.19 Esteban Calabria - 78711 2Prefacio ElpresentetrabajoserealizutilizandocomobaseelpapertituladoClassification methods in the detection of new malicious emails escrito por Dong-Her Shih, Hsiu-Sen Chiang, C. David Y en el ao 2004. Teora de la comunicacin 75.19 Esteban Calabria - 78711 3Indice 1.Introduccin ______________________________________________ 5 1.2. Estructura del trabajo ____________________________________ 7 1.3. Definicin de conceptos __________________________________ 8 1.3.2 Problema de la Clasificacin ___________________________ 8 1.3.4 Clasificacin por plantilla o template. ____________________ 9 1.3.5 Clasificacin por el vecino ms cercano o nearest- neighbour _ 10 1.3.6 Clasificacin por funciones linealmente discriminantes______ 11 1.3.7 Clasificacin por mtodos estadsticos ___________________ 13 1.3.7.1 Teora sobre la decisin bayesiana_____________________ 13 1.3.7.2. Medida de confianza_______________________________ 18 1.3.8. Redes Bayesianas___________________________________ 21 1.3.9. El clasificador Nave Bayes ___________________________ 22 1.3.9.1El clasificador Nave Bayes : un ejemplo practico ________ 23 1.3.9.1.1 Ejemplo de robos de auto __________________________ 23 1.3.9.1.2 Conjunto de Datos________________________________ 24 1.3.9.1.3 Desarrollo _____________________________________ 24 2. Aprendizaje Activo _______________________________________ 27 2.1 Clasificacin mediante aprendizaje activo supervisado _________ 29 3. Deteccion de SPAM mediante aprendizaje activo supervisado ___ 32 3.1 El problema de la deteccion de mails maliciosos y su importancia 32 3.2 Tecnicas previas utilizadas _______________________________ 33 3.3 Clasificacion SPAM mediante Redes Bayesianas______________ 34 3.4 Aprendizaje activo aplicado a la Deteccion de mails maliciosos __ 37 3.5 Criterio de seleccin para el filtrador de spam ________________ 38 4. Aplicaciones de computadora ______________________________ 43 4.1. Aplicacion Ejemplo Clasificadores Bayesianos_______________ 43 4.2.Aplicacion Ejemplo Aprendizaje Activo_____________________ 46 4.3 Cliente de mails con deteccion de Spam_____________________ 47 Teora de la comunicacin 75.19 Esteban Calabria - 78711 44.5 .Servidor POP3 prueba para el envio de mails ________________ 48 5. Conclusiones y Trabajos futuros ____________________________ 49 5.1 Trabajos Futuros _______________________________________ 49 5.Bibliografia______________________________________________ 52 Teora de la comunicacin 75.19 Esteban Calabria - 78711 5Abstract En el presente trabajo desarrollamos la temtica del aprendizaje activo supervisado para resolver el problema de la clasificacin utilizando mtodos de decisin basados en estadstica y la teora de decisin bayesiana como el clasificador Nave Bayes. Mostraremos las ventajas que nos ofrece en comparacin con el aprendizaje pasivo y una posible aplicacin para el filtrado de Spam, el correo electrnico masivo no solicitado generalmente con fines publicitarios, que dada la importancia y difusin del uso del email resulta un tema de bastante aplicacin y relevancia hoy en da 1.Introduccin Generalmente las personas aprenden de forma natural adquiriendo interactivamente el conocimiento mediante las acciones y experimentos que hacen con el entorno que los rodea. No obstante mucho del aprendizaje por computadora toma al que aprende, en este caso un algoritmo, como un receptor pasivo de datos a procesar. Esto ignora el hecho de que en muchas situaciones la herramienta ms poderosa para adquirir el conocimiento es la habilidad para actuar e influenciar el mundo que se est tratando de conocer. En varios mbitos se sugiere que aquellos que se involucran activamente en el proceso de aprendizaje pueden capturar mejor la informacin y ser capaces de utilizarla en distintos contextos. [http://en.wikipedia.org/wiki/Active_learning]. Es por ello que ya hace algn tiempo muchas de las investigaciones que estudian la forma en que se adquiere el conocimiento se hayan volcado al estudio del aprendizaje activo, un concepto que va ms all de los sistemas informticos. La idea sugiere que el sujeto que aprende se involucre activamente dentro del proceso de aprendizaje. En particular muchos autores[Cohn, Ghahramani, Jordan. 1996] muestran cmo aprovechar, en muchas tareas de aprendizaje, que la experiencia o datos sean ganados interactivamente y estudian la forma de aplicar el aprendizaje activo para sacar provecho de esta habilidad eficientemente en el mbito de la informtica y los sistemas inteligentes. En sus trabajos citan ejemplos donde se aplica aprendizaje activo: un robot que selecciona lugares para colocar sensores que detectan desechos radioactivos, un algoritmo que adquiere nociones de cinemtica arrojando un cuerpo desde distintas alturas elegidas por l e incluso aplicaciones Teora de la comunicacin 75.19 Esteban Calabria - 78711 6que preguntan a un humano experto que clasifique una palabra no reconocida del lenguaje natural para entender un problema. Formalmente, el aprendizaje activo estudia el fenmeno donde el que aprende selecciona acciones y hace preguntas que determinan que datos son agregados al conjunto de datos que conforman su conocimientos o experiencia, en base a los cuales tomar futuras decisiones[Cohn, Ghahramani, Jordan. 1996].Durante el transcurso del presente trabajo nos referiremos a dicho conjunto utilizando el trmino conjunto de datos de entrenamiento y estudiaremos el aprendizaje activo aplicado a los sistemas informticos dentro del marco del aprendizaje supervisado y para resolver problemas de clasificacin, es decir, aquellos en que hay que decidir a cual grupo o clase pertenece un objeto dada cierta informacin sobre l. El algoritmo de aprendizaje que diseemos tendr control sobre el dominio de entrada y decidir que parte del mismo recibir como informacin. En este trabajo llamaremos el que aprende para designar al algoritmo o programa de computadora que se desea entrenar con cierta informacin a la que, a su vez, nos referiremos como instancias o datos,representados por un conjunto finito de observaciones o caractersticas relacionadas con el problema que se est tratando de resolver.Se mostrar un ejemplo donde entrenaremos un algoritmo que en un control vial decida si detener un auto o no en funcin de cuan propenso es que el auto sea robado observando sus caractersticas. Para ello se dispone un conjunto de datos de entrenamiento con instancias adquiridas en controles anteriores donde se sabe para cada auto su color, el tipo de auto, su origen y si se trat de un auto robado o no. Se puede demostrar que cuando las acciones y preguntas son seleccionadas correctamente, los requerimientos de datos para algunos problemas decrecen drsticamente y algunos problemas de aprendizaje np-completos se convierten en polinmicos en tiempo computacional. En la prctica el aprendizaje activo ofrece sus mayores recompensas donde los datos son caros o dificiles de obtener o cuando el entorno es complejo o peligroso: en ciertos proyectos industriales obtener algo puede llevar das y costar miles de dlares,un mtodo que lo encuentre puede ofrecer una enorme fuente para ahorrar tiempo y dinero. Como se ver ms adelante el aprendizaje activo incluye implcitamente el concepto de el costo de adquirir la informacin. Teora de la comunicacin 75.19 Esteban Calabria - 78711 7Aqu propondremos como aplicar el aprendizaje activo para el filtrado de mails y decidir si uno nuevo es Spam o no. Un aspecto importante en el aprendizaje es el de obtener un modelo que represente el dominio de conocimiento y que sea accesible para el usuario. En particular, resulta importante obtener la informacin de dependencia entre las variables involucradas en el fenmeno, en los sistemas donde se desea predecir el comportamiento de algunas variables desconocidas basados en otras conocidas como en nuestro caso. Por ello proponemos un modelo para la deteccin de SPAM apoyndonos y adaptando el realizado en otros trabajos [Shih, Chiang & Yen. 2004] donde se propone una resolucin mediante aprendizaje pasivo.1.2. Estructura del trabajo El presente trabajo comienza definiendo elproblema de la clasificacin y exploraremos sintticamente las distintas soluciones que se han planteado dentro del marco de los sistemas inteligentes. De todas ellas profundizaremos en los mtodos estadsticos y, pasando por la teora de decisin bayesiana, desembocaremos en la aplicacin del clasificador Naive Bayes. Una vez sentadas las bases tericas entraremos de lleno dentro de la teora del aprendizaje activo tanto supervisado como no supervisado, sus aplicaciones y los distintos criterios de seleccin para obtener el conjunto de datos de entrenamiento. En la siguiente seccin introduciremos la problemtica de la deteccin del spam, su importancia y el papel que desempea en la informtica hoy en da. Luego de explicar las soluciones y heursticas clsicas utilizadas para filtrar los mails indeseados veremos cuales son las estrategias de aprendizaje pasivo utilizadas por la mayora de los productos comerciales. Una vez expuesto como funcionara conceptualmente una aplicacin que discrimine los distintos tipos de mails, partiremos de ah para proponer una solucin mediante el aprendizaje activo y veremos las ventajas que proporciona, como por ejemplo permitir personalizar el filtrador de mails indeseados para las necesidades y caractersticas particulares de los mails que recibe cada usuario. Acompaaremos el desarrollo terico concluyendo con una serie de aplicaciones informticas que proponen una aplicacin prctica de los conceptos desarrollados durante todo el trabajo. Teora de la comunicacin 75.19 Esteban Calabria - 78711 8Por ltimo plantearemos diversos temas que surgieron durante el desarrollo del trabajo, propondremos posibles estudios para sertratados en futuros trabajos (o por otros autores) y plantearemos las conclusiones. 1.3. Definicin de conceptos 1.3.2 Problema de la Clasificacin La clasificacin es el problema de decidir a cual grupo o clase pertenece un objeto dada cierta informacin sobre l. Dicha informacion es algo sobre el objeto que puede ser observado y cuantificado, como el color o la longitud. Las caractersticas que se observan son generalmente elegidas para distinguir bien la clase. Por ejemplo para decidir si un objeto pertenece a la clase frutillas o cerezas una observacin de la dureza de la superficie probablemente resulte ser mucho ms efectiva que una observacion del color. [Kramm, 2004]. Para resolver los problemas de clasificacin existen distintas tcnicas de sistemas inteligentes tales como algoritmos de induccin (ID3), redes neuronales. Independientemente de la que se use, dichas tcnicas se vuelven ms eficientes a medida que van adquiriendo experiencia. Aqu utilizaremos redes bayesianas y el clasificador Nave Bayes. Veamos un ejemplo [Kramm, 2004] sobre el cual basaremos gran parte de los desarrollos tericos que realizaremos posteriormente. Supongamos que un restaurant, con reputacin de tener platos muy deliciosos y postres muy caros, ofrece un premio de un postre gratis si el cliente puede identificar correctamente el especial del da. El juego se desarrolla de esta manera: el cliente entra al lobby del restaurant y declara su intencin de tratar de ganar el postre gratis. Luego paga su comida por adelantado, que debe ser el plato especial del da no identificado, ytrata de adivinar cual es. El mozo anota la opcin en la orden y se retira. El cliente luego se sienta y descubre si su respuesta fue correcta o no cuando se le sive la cena. Supongamos que este juego se desarrolla generalmente en el restaurant favorito del cliente, donde es un comensal habitual y que el cliente ha participado varias veces en este juego por lo que posee cierta informacin de cuales han sido los platos especiales del da en el pasado. Teora de la comunicacin 75.19 Esteban Calabria - 78711 9 Claramente el dueo del restaurant no dejar observar cual es el plato especial del dia antes de que se tome una decisin. Sin embargo hay algunas observaciones que se pueden realizar. En particular, como mencionamos, interesa observar cuan seguido se ofreci cada plato especial del dia en situaciones anteriores. Tambin se puede apelar al sentido del olfato y obtener informacin de el aroma que predomina en el lugar con la esperanza de que contenga indicios que permitan identificar el especial del da. A continuacin veremos que tcnicas se utilizan para clasificar y cuales de ellas son factibles de aplicar al problema planteado.1.3.4 Clasificacin por plantilla o template. Comencemos por la ms simple: la clasificacion por plantilla. Tambin conocida como template classification [Kramm, 2004] en la bibliografa en ingls. Consiste en establecer rangos discriminativos de clasificacin y para cada instancia nueva ver dentro de que clasificacin cae. Supongamos que se deben clasificar los huevos de gallina recin puestos, segn su tamao, en las siguientes categoras: pequea, mediana, grande y extra grande. Podriamos hacer un molde en madera (plantilla) que contenga orificios que representen el tamao mnimo del dimetro del huevo permitido para una clase. Se deben tener tantos orificios como clases distintas, cuatro en este caso, ya que cada uno corresponde a una clase. Para identificar a que clase pertenece un huevo nuevo probamos por turnos si el huevo pasa o no por el orificio de nuestro molde de madera, desde el ms chico al ms grande, hasta encontrar el primero por el que pasa y de esa forma encontramos su clasificacin. La clasificacin por plantilla y template se suele utilizar auxiliarmente para discretizar valores de naturaleza continua ya que muchas de las tcnicas planteadas para sistemas inteligentes funcionan con variables de naturaleza discreta. Teora de la comunicacin 75.19 Esteban Calabria - 78711 101.3.5 Clasificacin por el vecino ms cercano o nearest- neighbour Alternativamente se puede optar por otra forma de clasificacin y, en su lugar, comparar un objeto a clasificar contra un conjunto de objetos conocidos ya clasificados, con el objetivo de identificar el ms cercano. La clase del objeto desconocido entonces ser asignada basndose en la clase de su vecino ms cercano. Aplicndolo al ejemplo anterior, se podra medir el dimetro de cada huevo y clasificarlos. Esta medida luego se podra utilizar para comparar un huevo recin puesto contra cada huevo conocido (ya clasificado) y clasificar el nuevo basndose en la categora del huevo conocido cuyo dimetro sea ms cercano. Formalmente, una clasificacin por vecino ms cercano (NN o nearest-neighbour) es una tcnica de clasificacin y discriminacin no paramtrica donde un objeto a testear es comparado por su similitud, midiendo sus mltiples variables, con la de los items dentro de un conjunto de datos de entrenamiento. La clase del item que es ms similar puede ser usada como un indicador de la clase del objeto a testear. Para determinar la similitud o distancia entre un objeto y otro se suele utilizar la distancia euclideana. Una extensines el caso donde se consideran k vecinos ms cercanos (k-NN), que es utilizada en muchos campos incluyendo el reconocimiento de patrones. Por ejemplo aplicaciones que incluyen tareas como reconocimiento de voz, interpretacin de diagnosticos medicos, de imgenes satelitales, etc. El conjunto de dato de entrenamiento es usado para clasificar cada miembro del conjunto destino. Partimos de la base que la estructura de los datos es la siguiente: hay una clasificacin (categrica) o variable de inters (comprador, no comprador, por ejemplo) y un nmero de variables adicionales predictoras (edad, salario, ubicacin,). En trminos generales el algoritmo se da como sigue: Para cada instancia del conjunto de datos a clasificar (casos) encontrar los k elementos ms cercanos (vecinos ms cercanos) del set de datos de entrenamiento. Se calcula la distancia euclideana para saber cuan cercano es Teora de la comunicacin 75.19 Esteban Calabria - 78711 11cada miembro del conjunto de datos de entrenamiento contra la instancia que se est examinando. Para los k vecinos ms cercanos ver a que clase o categora pertenece la mayora de ellos. Asignar esa categora a la instancia que est siendo examinada. Repetir este procedimiento para los elementos restantes (casos) dentro del conjunto de datos a clasificar. Claro que el tiempo computacional de este algoritmo crece a medida que k crece, pero la ventaja es que cuanto mayor sea el set de datos de entrenamiento menos vulnerable es el algoritmo ante ruido en los datos de entrenamiento. En la prctica k est en el rango de los miles de registros. 1.3.6 Clasificacin por funciones linealmente discriminantes Otra forma de clasificar es utilizando funciones linealmente discriminantes que se pueden escribir como: ( )0tg x w x w = + Donde w es el vector peso y 0wes el peso del umbral. Los valores de w y 0w son determinados por una funcin de criterio. Una posible funcin de criterio puede ser minimizar el error de aprendizaje. Las funciones linealmente discriminantes son poderosas en los casos donde las clases son linealmente separables. Por ejemplo si quisieramos clasificar huevos en dos categoras, grandes y pequeos basandonos en un dimetro mnimo observado. Podemos disear una funcin discriminante que devuelva menos de 0 si el huevo es clasificado como pequeo y mayor a 0 si el huevo es grande. Los valores de w y 0wpueden ser escogidos usando distintas tcnicas como la del gradiente decreciente (gradient descent) [Kramm, 2004]. Otra alternativa para realizar clasificaciones linealmente discriminantes es utilizando una red neuronal[Martnez.1997] como puede ser el caso de un Teora de la comunicacin 75.19 Esteban Calabria - 78711 12perceptrn. La ventaja de las redes neuronales es que nos proveen una forma de desarrollar funciones discriminantes no lineales para clasificar, dndonos el poder de disear regiones de decisin arbitrarias. A continuacin se muestra como quedara una clasificacin linealmente discriminante aplicado al problema de la determinacin de patologas del lenguaje hablado [http://www.eng.ox.ac.uk/samp/speech_path.html] donde H yson parmetros a observar. La dificultad de aplicar tcnicas no lineales al problema de la clasificacin viene de elegir la funcin no lineal apropiada. Es por ello que se suele usar una alternativa estadistca, fundada alrededor del teorema de Bayes, para resolver el problema de clasificacin. Segn esta teora se especifica como fusionar informacin obtenida en observaciones independientes para tomar decisiones que maximicen la ganancia de informacin esperada. Teora de la comunicacin 75.19 Esteban Calabria - 78711 13 1.3.7 Clasificacin por mtodos estadsticos 1.3.7.1 Teora sobre la decisin bayesiana Como se mencion anteriormente, retomemos el caso de restaurante que ofrece un premio de un postre gratis si se identifica correctamente cual es el especial del da. Supongamos tambin que el restaurant sirve comida italiana y que los especiales pueden ser tallarines a la bolognesa(clase uno, denotada como1w )o linguini con salsa de ostras(clase 2, denotada como2w ). Un participante frecuente del juego de adivinar el especial del dia ha observado que dos de cada tres veces el especial es linguini. De esta observacin de ocurrencias pasadas se acerca al restaurant asumiendo una probabilidad a prioride P (2w ) =13 y que el especial del da es spaguetti y una probabilidad a priori P(1w ) =23que el especial es linguini. Como no hay posibilidad de otro plato especial estas probabilidades suman uno. Si no hubiera otra informacion se podra tomar la decisin basndose directamente en estas probabilidades a priori. Decidiramos: 1w si( ) ( )1 2P w P w > 2w si ( ) ( )1 2P w P w < Por supuesto basndonos solamente en las prioridades a priori elegir siempre linguini es predeciblemente errneo un tercio de las veces. Para mejorar las chances de identificar correctamente el especial del da deberemos tomar ventaja de la informacin que nos puede proporcionar el entorno. En este caso, aprovecharemos el sentido del olfato ydesarrollaremos un raiting que mida el aroma a frutos del mar en el ambiente. Teora de la comunicacin 75.19 Esteban Calabria - 78711 14Este sistema asocia un aroma con un nmero entre 0 y 1 que refleja la intensidad de aroma a frutos del mar presente en el restaurante, donde 0 significa la ausencia de aromas de frutos del mar y 1 la presencia muy intensa del mismo. A travs del tiempo, con este raiting que denotaremos x se va desarrollado una densidad deprobabilidad condicional que mide la intensidad del aroma a frutos del mar, dada la presencia de un plato especial del dia, que expresaremos como: ( )/iP x w Donde i = 1 significa spaghetti e i = 2 significa linguini. Existen aqudos distribuciones distintas ( ) /iP x w . Una cuando el especial del da es spaguetti y otra diferente cuando el especial es linguini. Unas distribuciones hipotticas se muestran a continuacin: Probabilidad condicional hipottica segn intensidad aroma frutos del mar Estas distribuciones son independientes una de otra a pesar de que se muestran en el mismo grfico por una cuestin de conveniencia. Con las observaciones que tenemos, las probabilidades a priori y las probabilidades condicionales para cada plato, al ingresar al restaurant utlizamos el olfato y clasificamos el aroma a frutos del mar segn el raiting que propusimos. Teora de la comunicacin 75.19 Esteban Calabria - 78711 15Ahora se puede tomar la decision basndonos en el raiting x de intensidad de aroma a frutos del mar: Si( ) ( )1 2/ / P w x P w x > entonces elegimos 1wSino elegimos2w Estas probabilidades son calculadas a partir de las distribuciones( ) P x ,( )iP wy ( ) ,iP x wutilizando el teorema de bayes como se mostrar a continuacin. La probabilidad conjunta del raiting de intensidad x de aromas a frutos del mar y cada claseiw esta dada por: ( ) ( ) ( ), /i iP x w P w x P x = que alternativamente puede ser escrita como: ( ) ( ) ( ), /i i iP x w P x w P w = Igualando la parte derecha de las ecuaciones anteriores podemos obtener la frmula de Bayes: ( )( ) ( )( )//i iiP x w P wP w xP x=

El denominador de la ecuacin anterior, que es la suma de las prioridades condicionales ponderadas, se puede calcular en funcion de las distribuciones observadas previamente de la siguiente manera: ( )21( / ). ( )i iiP X P x w P w==(2.5) Teora de la comunicacin 75.19 Esteban Calabria - 78711 16 Probabilidad condicional ponderada con( )iP w Finalmente para decidir sobre la clase 1 2 evaluaramos la siguiente inecuacin que es una comparacin de las probabilidades a posteriori:

( ) ( )?1 2/ / P w x P w x > A su vez se puede rescribir en trmino de las probabilidades observadas: ( ) P xHipotetica Teora de la comunicacin 75.19 Esteban Calabria - 78711 17 Probabilidades a posteriori de( ) /iP w xpara i = 1 (spaghetti) and i = 2 (linguini). ( ) ( )( )( ) ( )( )?1 1 2 2/ / P x w P w P x w P wP x P x>(2.7) Claramente los denominadores se cancelan eliminando la necesidad de calcular la probabilidad P(x) Esto simplifica la ecuacin anterior a la clsica regla de decisin Bayesiana:

( ) ( ) ( ) ( )?1 1 2 2/ / P x w P w P x w P w > (2.8) Siesta desigualdad es en efecto verdadera entonces se decide la clase1w en caso contrario se decide la clase 2w . Dada una observacin x y una clase de decisin j, la probabilidad de cometer un error es: ( ) ( )/ , / ,iP error x j P w x i j = (2.9) Teora de la comunicacin 75.19 Esteban Calabria - 78711 18Podemos minimizar la probabilidad de error eligiendo1wsi( ) ( )1 2/ / P w x P w x >o 2wen caso contrario. La probabilidad de error est dada por: ( ) ( ) ( )( ) , / P error P error x dx P error x P x dx = = (2.10) Si aseguramos que para cada x que( ) / P error x es minimizada entonces la ( ) P errortambin es minimizada. La condicin de decisin( ) ( ) ( ) ( )?1 1 2 2/ / P x w P w P x w P w >puede ser reescrita y ser generalizada al caso de tener N clases: ( ) { }arg max ( / )i i iD P x w P w = (2.11) Donde D es el ndice de la clase ganadora. 1.3.7.2. Medida de confianza Adems de poder tomar una decisin que conduzca a una clasificacin, a veces es deseable proveer una medida en cuan segura es la decisin, es decir, cuanta confianza se le puede atribuir a la decisin que tomamos. Cuando tomamos una decisin probabilstica, la medida de la confianza debe reflejar cuan correcta es la hiptesis dado el modelo. Por lo que un nivel alto de confianza implicara que el modelo sobre el que se construy la decisin era muy adecuado para tomar las observaciones persistentes. Teora de la comunicacin 75.19 Esteban Calabria - 78711 19Por el contrario una medida de confianza baja implica que ms de un modelo pueden explicar las observaciones que realizamos y justamente puede ser la mejor pero de un conjunto de mltiples hiptesis rivales. La medida de confianza puede ser tambin pensada para determinar cuanto riesgo uno esta dispuesto a tomar ante la posibilidad de estar equivocado ante la decisin que se tome. Por ejemplo, en el escenario del restaurante, supngase que un da en particular no se tiene ganas de comer linguini. Si se esta razonablemente segurode que el especial del da fuera justamente spaghetti con salsa boloesa uno estara de acuerdo con jugar y en caso contrario se preferira no jugar al juego y elegir cualquier otro plato. Si una medida de confianza fuera includa en la toma de decisiones, entonces se podra utilizar para decidir si conviene o no jugar al juego. Otra alternativa seria, supngase que se esta corto de dinero y se decide que solo vale la pena jugar si se obtiene el postre gratis. En ese caso, uno puede usar la medida de confianza para medir cuan seguro se esta de que se va a adivinar correctamente y de si se esta seguro de poder ganar el postre. Sino es mejor decidir cocinar nuestra propia cena. Una medida de confianza obvia es la probabilidad de estar en lo cierto:

( ) ( )/ 1 / P correcto x P error x = (2.12) Que se puede rescribir como: ( )( / ) max /iiP correcto x P w x =( (2.13) Y mostrado para nuestro ejemplo hipottico como: Teora de la comunicacin 75.19 Esteban Calabria - 78711 20 ( ) ( ) 1 / max /iiConfianza P error x P w x = =( Teora de la comunicacin 75.19 Esteban Calabria - 78711 21 1.3.8. Redes Bayesianas Una red bayesiana es un grafo acclico dirigido en el que cada nodo representa una variable y cada arco una dependencia probabilstica, en la cual se especifica la probabilidad condicional de cada variable dados sus padres, la variable a la que apunta el arco es dependiente (causa-efecto) de la que est en el origen de ste. [Fernndez. 2004] La topologa o estructura de la red nos da informacin sobre las dependencias probabilsticas entre las variables pero tambin sobre las independencias condicionales de una variable (o conjunto de variables) dada otra u otras variables, dichas independencias, simplifican la representacin del conocimiento (menos parmetros) y el razonamiento (propagacin de las probabilidades). El obtener una red Bayesiana a partir de datos, es un proceso de aprendizaje que se divide en dos etapas: el aprendizaje estructural y el aprendizaje paramtrico. El aprendizaje estructural consiste en obtener la estructura de la red bayesiana, es decir, las relaciones de dependencia e independencia entre las variables involucradas. El aprendizaje paramtrico tiene como finalidad obtener las probabilidades a priori y condicionales requeridas a partir de una estructura dada. Estas redes [Fernndez. 2004] son utilizadas en diversas reas de aplicacin como por ejemplo en medicina, cienciaLas mismas proveen una forma compacta de representar el conocimiento y mtodos flexibles de razonamiento - basados en las teoras probabilsticas - capaces de predecir el valor de variables no observadas y explicar las observadas. Entre las caractersticas que poseen las redes bayesianas, se puede destacar que permiten aprender sobre relaciones de dependencia y causalidad, permiten combinar conocimiento con datos y pueden manejar bases de datosincompletas. Existen diversos clasificadores como ser el Nave Bayes, TAN y KDB. Estas se diferencian en el tipo de grafo que generan correspondiendo un Arbol, Red y Poliarbolpara cada clasificador respectivamente. Teora de la comunicacin 75.19 Esteban Calabria - 78711 22 No obstante aqu solamente el clasificador Naive Bayes estudiaremos el primero. 1.3.9. El clasificador Nave Bayes El paradigma clasificatorio en el que se utiliza el teorema de Bayes en conjuncin con la hiptesis de independencia condicional de las variables predictoras dada la clase que se conoce bajo diversos nombres que incluye los de idiota Bayes, nave Bayes simple Bayes y Bayes independiente. A continuacin mostramos un grafo correspondiente a este modelo. Se puede apreciar claramente que, como no existen arcos entre las variables predictoras, entonces se puede visualizar grficamente la hiptesis de que son consideradas como variables independendientes: Grafo correspondiente al modelo Naive Bayes A pesar una larga tradicin en la comunidad de reconocimiento de patrones el clasificador Nave Bayes aparece por primera vez en la literatura del aprendizaje automtico a finales de los ochenta con el objetivo de comparar su capacidad predictiva con la de mtodos ms sofisticados. De manera gradual los investigadores de esta comunidad de aprendizaje automtico se han dado cuenta de su potencialidad y robustez en problemas de clasificacin supervisada. Teora de la comunicacin 75.19 Esteban Calabria - 78711 23A pesar de diseo inocente y las aparentemente sobre simplificadas asumpciones de independencia, el clasificador generalmente se comporta mucho mejor en situaciones complejas del mundo real de lo que se esperara. Recientemente han surgido anlisis detallados sobre el problema de la clasificacin bayesiana que demuestran la existencia de fundamentos tericos para explicar la aparente sobrestimada eficacia del clasificador Naive Bayes[http://en.wikipedia.org/wiki/Naive_Bayesian_classifier] Veremos a continuacin un resultado terico que nos servir para entender mejor las caractersticas del clasificador nave Bayes. 1.3.9.1El clasificador Nave Bayes : un ejemplo practico El clasificador Nave Bayes selecciona la clase Vnb dados los atributos a1, a2,, an. Esto resulta en: ( )arg max ( / )jnb v V j i jV P v P a v= Generalmente estimamos( / )i jP a vusando el metodo de las m-estimaciones( / )ni jn mpP a vn m+=+ Donde: n = numero de casos donde v = vj nc = numero de casos donde v = vj y a = ai p = probabilidad a priori estimada para( / )i jP a vm = parmetro m del mtodo 1.3.9.1.1 Ejemplo de robos de auto Veremos a continuacion una aplicacion concreta del clasificador Nave Bayesaplicado al robo de automotores [Meisner. 2003]. Dados ciertos atributos del auto que son Color, Tipo, Origen se quiere saber la susceptibilidad de que estos sean robados. Este ejemplo puede resultar til a la hora de detener autos que transitan por una ruta. Debido a la imposibilidad de Teora de la comunicacin 75.19 Esteban Calabria - 78711 24detener todos los autos que pasan, el control vial debe decidir a cuales pedirle los papeles para evitar entorpecer el transito. Para ello se cuenta con datos histricos que se tomaron en controles viales realizados en situaciones previas. Nuestras variables predictoras serian el Color, el Tipo y el Origen. Y nuestra variable clase, la que contiene el conocimiento al cual esperamos arribar, es la que nos indica si el vehculo fue robado o no Este caso que se plantea es a modo de ejemplo, con un ser de datos tal como se muestra a continuacin bastante reducido. En un caso real sera conveniente contar conun set de datos y atributos mayor. 1.3.9.1.2 Conjunto de Datos Muestra ColorTipoOrigenRobado 1RojoDeportivoNacionalSi 2RojoDeportivoNacionalNo 3RojoDeportivoNacionalSi 4AmarilloDeportivoNacionalNo 5AmarilloDeportivoImportadoSi 6AmarilloFamiliarImportadoNo 7AmarilloFamiliarImportadoSi 8AmarilloFamiliarNacionalNo 9RojoFamiliarImportadoNo 10RojoDeportivoImportadoSi 1.3.9.1.3 Desarrollo Durante el control vial se presenta un vehculo que es Rojo, Familiar y Nacional. Entonces hay que decidir si detenemos al conductor y le pedimos sus papeles o lo dejamos pasar directamente. Como se puede observar no existe un ejemplo que se trate de un auto de dichas caractersticas dentro del set de datos histricos que se posee. Debemos calcular las siguientes probabilidades: Teora de la comunicacin 75.19 Esteban Calabria - 78711 25 Probabilidades que hay que calcular para el ejemplo dado P(Rojo/Si) P(Familiar/Si) P(Nacional/Si) P(Rojo/No)P(Nacional/No) P(Familiar/No) Calculo de probabilidades 3 3*0.5( / ) 0.565 32 3*0.5( / ) 0.435 31 3*0.5( / ) 0.315 33 3*0.5( / ) 0.565 32 3*0.5( / ) 0.435 33 3*0.5( / ) 0.565 3P Rojo SIP Rojo NoP Familiar SiP Familiar NoP Domestico SiP Domestico No+= =++= =++= =++= =++= =++= =+ Como segn nuestro set de datos tenemos que P (Si)=0.5 y P (No)=0.5 entonces Teora de la comunicacin 75.19 Esteban Calabria - 78711 26 P(Si)*P(Rojo/Si)*P(Familiar/Si)*P(Nacional/Si) = 0.5*0.56*0.31*0.43 P(Si)*P(Rojo/Si)*P(Familiar/Si)*P(Nacional/Si) = 0.037 Y para v = No tenemos P(No)*P(Rojo/No)*P(Familiar/No)*P(Nacional/No)=0.5*0.43*0.56*0.56 P(No)*P(Rojo/No)*P(Familiar/No)*P(Nacional/No)=0= 0.069 Entonces como 0.069 > 0.037, entonces nuestro ejemplo es clasificado como No. Teora de la comunicacin 75.19 Esteban Calabria - 78711 272. Aprendizaje Activo Volvamos a nuestro escenario del restaurante: esta claro que una vez que obtenemos buenas estimaciones de cuan seguido se espera encontrar cada especial del da: Probabilidades a priori de( )iP w Y cuan intenso es el aroma a frutos del mar del lugar cuando se sirve cada especial del da: Probabilidades condicionales( ) /iP x w Es posible aplicar la teora de decisin de Bayes para ayudarnos a clasificar el prximo especial del da. Siempre y cuando el raiting de intensidad de aroma a frutos del mar sea predecible, se pueden tomar decisiones ms acertadas que simplemente basarnos en( )iP w

Entonces ganar el postre gratis depende mucho de tener buenas probabilidadescondicionales ( ) /iP x w y una forma de descubrirlas es ir al restaurante y jugar el juego todos los das. Eventualmente podremos llegar a tener informacin para armar las distribuciones( ) /iP x w suficientemente buenas para ganar un postre gratuito la mayora de las veces que decidamos jugar. Pero este entrenamiento requerira un montn de dinero y un fuerte deseo de comer comida italiana todos los das por tal vez varios aos. Aparece entonces la problemtica de analizar el costo asociado a descubrir la relacin entre la intensidad de aroma a frutos del mar y el especial del da. Los mtodos de aprendizaje activo son aquellos que permiten al que aprende interactuar con el entorno. Esto contrasta con el aprendizaje pasivo donde se aprende exclusivamente observando el entorno. Por ejemplo, supongamos que un robot debe ser entrenado para navegar del punto A al B de una habitacin en particular. La habitacin define el entorno. El robot puede aprender pasivamente Teora de la comunicacin 75.19 Esteban Calabria - 78711 28observando como los humanos van del punto A al B, o, se le puede permitir al robot aprender activamente explorando el cuarto. La ventaja de la metodologa activa es que el que aprende identifica sus propias debilidades y desconocimiento y busca la informacin que maximice su beneficio y comprensin Los mtodos de aprendizaje activo permiten al que aprende tener control sobre que datos nuevos son adquiridos mediante dos mtodos de adquisicin: generativos y selectivos. En los mtodos generativos el que aprende busca generar nuevos datos de entrenamientos que, cuando sean clasificados por un orculo, se espera que tengan un impacto positivo sobre el sistema que aprende. Utilizaremos durante este trabajo trmino orculo para referirnos a quien le va a entregar la correcta clasificacin de los datos de entrenamiento. En la prctica ste puede tratarse de un humano experto en el dominio del problema a resolver. Este mtodo resulta atractivo cuando el costo de adquirir datos nuevos es alto y cuando el orculo puede juzgar y decidir la clasificacin basndose en el ejemplo sintetizado.Por ejemplo en el escenario del restaurante, un mtodo generativo puede llegar a requerir que cocinemos nuestro propio linguini o spaghetti con el objetivo de generar un aroma mediante el cual podamos identificar la comida. Claramente, el mtodo generativo no es el ms adecuadopara este escenario. En los mtodos selectivos, el que aprende elige de un conjunto de datos existentes aquellos que van a tener un impacto positivo sobre el sistema. Los mtodos selectivos son aplicables en casos donde un conjunto grande de datos esta disponible. Si estos datos ya se encuentran clasificados de antemano, el mtodo selectivo se puede usar para reducir el tamao del conjunto de datos de entrenamiento. En cambio si los datos estn sin clasificar, y el costo de hacerlo es elevado, el mtodo selectivo puede disminuir la cantidad de instancias a clasificar. A continuacin veremos un algoritmo genrico para el aprendizaje activo utilizando un mtodo selectivo Teora de la comunicacin 75.19 Esteban Calabria - 78711 29Dado un conjunto candidatos de datos de entrenamiento U 1. Seleccionar in conjunto de entrenamiento inicial U0 de U y definir i = 0. 2. Si Uino esta clasificado, clasificar el conjunto Ui. 3. Entrenar el modelo utilizando el conjunto Ui. 4. Determinar si se cumpli la opcin de corte. 5. Obtener un nuevo set de datos de entrenamiento utilizando alguna heurstica : a partir de generando observaciones no hechas hasta el momento a partir de observaciones existentes que no aportan certeza 6 Unir los datoscon Ui creando el prximo conjunto de entrenamiento Ui+1. 7. Incrementar iy volver al paso 2 Algoritmo de aprendizaje activo generalizado El mtodo selectivoes adecuado para el caso de nuestro restaurante: pasamos por el restaurante, capturamos el aroma del entorno y decidimos si es necesario pedir el plato del da para poder asociarlo con el aroma presente. Pueden darse varias situaciones. Podemos, en funcin del aroma, estar seguros que el plato especial del da se trata de linguini y decidir si queremos comer ah o no. Otro da, en cambio, llegar a la conclusin de que el aroma es difcil de clasificar y elegir comer en ese restaurante para saber cual es el plato especial del da y, por consiguiente, ganar ms informacin al respecto. A continuacin veremos algunas aplicaciones comunes del aprendizaje activo: 2.1 Clasificacin mediante aprendizaje activo supervisado En muchas tareas de aprendizaje supervisado, clasificar instancias para crear un conjunto de datos de aprendizaje puede consumir mucho tiempo y ser una tarea costosa. Por lo tanto encontrar formas de minimizar el nmero de instancias a clasificar resulta beneficioso [Tong. 2001]. Teora de la comunicacin 75.19 Esteban Calabria - 78711 30 Usualmente el conjunto de datos es elegido de un conjunto al azar de instancias sobre un muestreo. No obstante en muchos casos, tal como estuvimos viendo, se puede aplicar aprendizaje activo y el que aprende puede (activamente) elegir los ejemplos o instancias para entrenarse con la esperanza de que esta flexibilidad reduzca la necesidad de clasificar un conjunto grande de datos Lewis y Gale en 1994 introdujeron el mtodo Pool-based active learning. Aqu el que aprende tiene acceso a un conjunto (pool) de datos sin clasificar y pregunta sobre la correcta clasificacin de un grupo de instancias del conjunto. En muchos dominios este es un mtodo razonable ya que hay disponible una gran cantidad de datos sin clasificar. El principal objetivo del aprendizaje activo es elegir un buen subgrupo del conjunto para clasificar. Ejemplos de situaciones donde se puede utilizar este mtodo son: Bsqueda de pginas web. Una compaa busca recopilar informacin de un tipo particular de pginas, por ejemplo aquellas que contengan una lista de publicaciones. Contrata una cantidad de empleados para que clasifiquen a mano algunas pginas para crear un set de datos de entrenamiento para un clasificador automtico que eventualmente se utilizara para clasificar y extraer pginas del resto de la web. Como los expertos humanos son un recurso limitado la compaa busca reducir el nmero de pginas que los empleados tienen que clasificar. En lugar de clasificar pginas elegidas al azar de la web, la computadora utiliza aprendizaje activo para requerir que se clasifiquen las pginas web que juzga que aportan ms informacin para el proceso de aprendizaje. Filtrado de Mail. Un usuario desea crear un sistema personalizado que filtre automticamente el spam. En la fase de aprendizaje esta aplicacin tiene acceso a los mails pasados que ha recibido el usuario. Usando aprendizaje activo la aplicacin interactivamente le muestra los mails pasados y le pregunta al usuario si el mail mostrado es spam o no. Basndose en lo que el usuario decidi, muestra otro mail Teora de la comunicacin 75.19 Esteban Calabria - 78711 31y vuelve a pedir al usuario que diga de qu clase de mail se trata y as sucesivamente.La ventaja es que este filtro de spam estar personalizado para un usuario especfico y resultara ms especfico que uno genrico para sus necesidades y la clase de mails que reciba. Este es el caso que estudiaremos en el presente trabajo Clasificacin de datos relevantes. El usuario desea ordenar tems de un sitio web o base de datos o incluso el contenido de su propio disco rgido (artculos, imgenes, etc.) que poseen un inters especial para l. Como en los casos anteriores la computadora le muestra un tem y le pregunta al usuario cuales son de su inters o cuales no. Basndose en las respuestas del usuario la aplicacin logra identificar los tems que pueden llegar a ser de potencial inters para el usuario Los primeros dos ejemplos requieren induccin: el objetivo es crear un clasificador que funcione bien en situaciones futuras y desconocidas. El tercer ejemplo, en cambio, mide su performance sobre las restantes instancias que el usuario no clasific en lugar de un conjunto de datos completamente independiente. Teora de la comunicacin 75.19 Esteban Calabria - 78711 323. Deteccion de SPAM mediante aprendizaje activo supervisado 3.1 El problema de la deteccion de mails maliciosos y su importancia En los ltimos aos el nmero de usuarios de Internet alrededor del mundo ha crecido drsticamente a medida que Internet se expande. Junto con este crecimiento y la utilizacin de este medio de cominicacin ha surgido la utilizacin del email como medio de difusion publicitaro para hacer llegar en masa avisos publicitarios a potenciales interesados. Estos mails no solicitados fueron creciendo exponencialmente a medida que pasa el tiempo llegando a ser un problema y recibieron la categorizacion de mails basura o SPAM. Se pueden encontrar en los sitios de internet relacionados con el tema [http://www.cyberguard.com/] mucha informacion cuantificada de cmo fue creciendo el SPAM a traves del tiempo Como asi tambien el alto porcentaje de [http://www.chebucto.ns.ca/] mails que resultan ser spam en contraposicion a todos al total de mails que son enviados diariamente Teora de la comunicacin 75.19 Esteban Calabria - 78711 33 Ademas de ser molesto y saturar la casilla de un usuario con mensajes no deseados, el Spam puede ser una forma de introducir programas maliciosos y virus en una computadora resultando un serio problema de serguridad. Por todo lo antes mencionado en los ultimos aos ha cobrado importancia encontrar mtodos que analicen los mails, detecten el spam y lo eliminen antes de llegar a la casilladestino. Muchos de los programas comerciales y populares que cumplen este fin mezclan la teoria de decisin bayesiana vista anteriormente con determinadas heuristicas utilizando grandes bases de datos de mail ya clasificados la que utilizan para entrenar la red bayesiana. En otras palabras utilizan un aprendizaje pasivo y supervisado. 3.2 Tecnicas previas utilizadas Sin embago el problema de detectar spam existi desde que el uso del mail se ha popularizado en forma global y no siempre se utilizaron stas tcnicas de sistemas inteligentes. Al principio la forma deteccin de spam ms rudimentarias. Mtodos como bloquear la direccion de mail de la persona que envia el spam o utilizar heursticas que discriminen un mail segn su contenido resultaban muy tiles. Por ejemplo, el contenido en exceso de ciertos smbolos como el $ y la presencia de determinadas Teora de la comunicacin 75.19 Esteban Calabria - 78711 34palabras como ser oferta, gratis, descuento, etc podian dejar en evidencia las caractersticas maliciosas del mail en cuestin. A medida que la presencia del SPAM se hizo ms acentuada, dichos metodos empezaron a perder eficacia. Estos se empezaron a redactar de tal forma de poder saltear las heuristicas ms comunes evitando utilizar palabras que delaten su naturaleza. Veamos a continuacion en detalle las tcnicas utilizadas para combatir el SPAM. Bloqueo de Direcciones: Consiste en bloquear la direccin del remitente de un mail que contiene SPAM para no recibir ms sus mails. Hoy en dia existen programas para el envio de mails masivos que enmascaran la direccion del remitente. Incluso hay virus maliciosos que infectan una computadora y la convierten en un enviador constante de SPAM. Heuristica. El uso de heuristicas para determinar si un mail es spam o no es una tcnica que se suele utilizar hoy en dia. Pero a medida que pasa el tiempo la forma de redactar los mails span va evolucionando de forma que esas Heuristicas no se cumplan. Es por ello que a medida que pasa el tiempo la forma que tienen los mails spam va mutando. Libreta de direcciones de Permitidos. Consiste en solo permitir mails de un determinado grupo de personas 3.3 Clasificacion SPAM mediante Redes Bayesianas Estudiaremos como aplicar el clasificador Naive Bayes para la deteccion de mails maliciosos. Este clasificador determina el parecido del mail que estamos estudiando con un spam en dadas las caracteristicas del formato que tiene el mail [Shih, Chiang & Yen. 2004] Si deseramos utilizar una red bayesiana para clasificar un mail como spam o no, el primer paso seria definir las observaciones que nos den indicios de su naturaleza para armar las distribuciones marginales( / ) P Spam Observacion .Teora de la comunicacin 75.19 Esteban Calabria - 78711 35Como en el caso del restaurante decidimos que el aroma presente en el ambiente nos podia ser util para decidir cual ser el plato especial del da, en este caso decidiremos que elementos tomaremos como relevantes del mail como por ejemplo su longitud, la cantidad de destinatarios, etc. Por lo tanto este clasificador clasifica el mail basandose sus caracteristicas. Por ejemplo si un mail contuviera un numero significatico de caracteristicas maliciosas tenderia a ser clasificado como spam. La respuesta a que observar del mail es muy importante y puede variar mucho la eficacia del filtrador de spam. Hay autores que incluso desarrollan tcnicas para analizar exhaustivamente el contenido del texto hace al cuerpo del mail: A continuacin se muestran algunas caracteristicas que en la prctica resultan bastante efectivas: Caracteristicas a observar de un mail CaracteristicaValores Posibles x1Mail content typeText/plain, text/html, other x2Mail sizePequeo, Mediano, Grande x3Mime FormatYes, No x4AttachmentYes, No x5N Atachments1,2,3,4,5,5+ x6Tamao atachmentPequeo, Mediano, Grande x7Tipo Atachmentexe, doc, pdf, scr x8Script LanguageVBScript, JavaScript,. . . x9SubjectRe, Fw, Fwd,. . . x10Carbon CopyCC, BCC, Undisclosed-Recipient,. . . x11RecipientSingle- Recipient,Multi-Recipient La solucin supervisada y con aprendizaje pasivo seria conseguir una base de datos con mails ya clasificados, entrenar nuetra red bayesiana. Para este problema resulta tan efectivo para los fines practicos utilizar el clasificador Nave Bayes como el TAN o el KDB por lo que se opta el primero por simpleza. Teora de la comunicacin 75.19 Esteban Calabria - 78711 36De esa forma podemos obtener: ( ) P Spam y las distribuciones ( / )iP Spam X y tal como vimos anteriormente dado un mail nuevo determinaramos si es spam si se cumple la siguiente desigualdad ( ) ( / ) ( ) ( / )i iP spam P x spam P nospam P x nospam > En caso contrario el mail puede ser recibido tranquilamente en la Bandeja de entradas. La pregunta que es interesante responder es cuantos mails necesitamos o seria conveniente tener para entrenar nuestra red bayesiana. Una forma de hacerlo es [Shih, Chiang & Yen. 2004] estimando el radio de poblacin: 2/ 22(1 ) z p pne= Donde: e es el error,n es la cantidad de muestras,p es la proporcion de la poblaciones el nivel de confianza Con una confianza del 0.95 y un error de 0.01 variando p entre valores razonables la cantidad de mails necesarios puede variar entre 300 y 2000 mails. No nos interesa aqu calcular el valor exacto sino proporcionar un rango numrico que Teora de la comunicacin 75.19 Esteban Calabria - 78711 37indique a grandes rasgos la cantidad de mails que para entrenar nuestra red bayesiana en forma pasiva y supervisada 3.4 Aprendizaje activo aplicado a la Deteccion de mails maliciosos Como dijimos antes una de las aplicaciones del aprendizaje activo es el filtrado de emails. Si bien un filtro de spam entrenado de la forma explicada antes resulta efectivo, podemos aprovechar el hecho de que en la prctica las caracteristicas del spam recibidos por dos personas distintas pueden diferir mucho. Tal vez una persona aficionada a hacer inversiones reciba mucho spam de bancos ofreciendole tarjetas, prestamos con intereses bajos, etc. Incluso lo que a cierto individulo le puede resultar como un mail indeseable a otra persona realmente puede llegar a resultarle interesante. El usuario puede llegar a estar interesado en decir que clase mails quiere recibir y que mails descartar. El mismo tiene el poder definir lo que para l es un mail SPAM o no. Aprovechando estas caracteristicas podemos utilizar aprendizaje activo para realizar un filtro de spam customizado para una determinada persona y que le resulte ms efectivo. En la fase de aprendizaje esta aplicacin tiene acceso a los mails pasados que ha recibido el usuario. Usando aprendizaje activo la aplicacin interactivamente le muestra los mails pasados y le pregunta al usuario si el mail mostrado es spam o no. Basandose en lo que el usuario escribio, muestra otro mail y vuelve a pedir al usuario que diga de que clase de mail se trata ya si sucesivamente. La ventaja es que este filto de spam estara personalizado para una usuario especfico y resultara ms especfico que uno generico. Este es el caso que estudiaremos en el presente trabajo. Claro que no seria prctico y resultara altamente tedioso que una persona tenga que clasificar como spam o no de 300 a 2000 mails que recibio en el pasado. Adems no podemos asegurar que el usuario haya guardado un historial de sus mails recibidos anteriormente. Es aqu donde interviene encontrar un criterio de seleccin adecuado. Teora de la comunicacin 75.19 Esteban Calabria - 78711 38La idea es que el filtrador de spam se pueda utilizar desde un principio sin tener datos histricos cargados. Si bien la presencia de un conjunto de mails ya clasificados podra resultar til, ahorrara tiempo y consultas al usuario consideraremos aqu que no es condicion necesaria. Podemos prescindir de la etapa de entrenamiento pues el ste sera constante. 3.5 Criterio de seleccin para el filtrador de spam Para el criterio de seleccin de nuestro filtrador de spam propondremos utilizaremos el principio de la regin de incertidumbre. Supongamos un mail con determinadas caractersticas u observaciones jxque pueden estar presentes o no en un mail, por ejemplo un jxen particular puede corresponder a si el mail contiene imagenes o no. Consideremos tambinlos posibles valorespara la clasificacin iwque son 1wsi el mail es spam y 2wen caso contrario. Como vimos anteriormente para decidir si el mail es spam o no nos basariamos en: ( )arg max ( / )i i j ijP w P x w ` ) El resultado de ( )( / )i j ijP w P x wpara cualquier iw ser un valor que esta entre 0 y 1 ya que es una multiplicatorias de trminos todos menores que 1. En la prctica lo ms probable es que sean valores muy pequeos como se vio en el ejemplo del clasificador de Naive Bayes desarrollado anteriormente. Vemos que: ( )( / )i j ii jP w P x w| | |\ . Hay que notar que el resultado de la sumatoria anterior no necesariamente cierra a uno. De hecho probablemente sea tambien un nmero muy pequeo.Teora de la comunicacin 75.19 Esteban Calabria - 78711 39 . Para calcular el grado de incertidumbre de nuestra decisin computamos: ( )( )arg max ( / )1( / )i i j iji j ii jP w P x wIncertidumbreP w P x w ` )= | | |\ . : Donde 0 1 Incertidumbre < < Donde 1 denota la mnima incertidumbre posible. En algun punto de la aplicacin el usuarioprimero el usuario definira una mnima incertidumbre entrede modo que analizamos: ?MinimaIncertidumbre Incertidumbre > Si se cumple esa desigualdad entonces decimos que el filtrador encontr una clasificacin. En caso contrario no estamos lo suficientemente seguros de la clasificacin de un determinado mail y por lo tanto decidimos preguntrsela al usuario. Cuanto mayor sea la incertidumbre menor ser el porcentaje de falsos positivos pero mayor ser las clasificaciones que el filtrador deje en manos del usuario. Hay que analizar un caso en particular. Si vemos ( )( / )i j ii jP w P x w| | |\ . Teora de la comunicacin 75.19 Esteban Calabria - 78711 40Hay casos dado el conjunto de datos que manejamos, se de que( / )j iP x w =0 para algunosjxde tal forma que el calculo de la sumatoria anterior de tambien 0. Esta sumatoria corresponde al denominador del clculo de la incertidumbre y no se puede dividir por 0 habr que considerar que hacemos en ese caso. Esta situacin ser muy comun al principio cuando no disponemos de informacin previa, es decir, nuestro conjunto de datos de entrenamiento est vacio. Por lo tanto si para el caso del mail que entra se da que para algun jxde unmail a clasificar se cumple que: ( / ) 0j iP x w = Significa que probablemente nunca nos topamos un mail en el pasado que encontremos parecido a ste. Entonces en este caso particular le preguntariamos al usuario (orculo) sobre su clasificacin sin pasar por el clculo de la incertidumbre para luegoagregarlo al conjunto de datos de entrenamiento ya que nos aporta informacin donde antes tenamos incertidumbre. Con este nuevo mail incorporado la( / )j iP x w ya no va a hacer 0. Hay que tener en cuenta que todo esto dependiender como calculamos( / )j iP x w . En el ejemplo del clasificador Naive bayes que vimos [Meisner. 2003] el autor utiliza un mtodo que llama de las m-estimaciones para calcular ( / )j iP x w . En este caso el filtrador propuesto calcula( / )j iP x w en funcin de su conjunto de datos de entrenamiento D con una simple relacin entre donde se cuentan cantidad de mails de la claseiwcon la observacinjxy lo divide por en nmero de mails de la claseiw , es decir, si consideramos el operador # ( ) como la cantidad de mails que cumplen diramos: ( )( )# ,( / )#j ij iix wP x ww= Teora de la comunicacin 75.19 Esteban Calabria - 78711 41 La desventaja de calcular las probabilidades de esa manera es que se piede un poco eficacia en estudiar como se desenvolvera el clasificador en ciertas situaciones completamente nuevas, es decir, hay casos donde el clasificador despondera directamente que no sabe de que clase se puede tratar. De otra forma arriesgara una clasificacin estimando una( / )j iP x wmediante algn mtodo (como el de las m-estimaciones). No obstane para un filtrador de spam que funciona por aprendizaje activo resulta aceptable suponer el caso donde el clasificador responde que no sabe. Por otro lado, tambin podemos incluir en el proceso la medida de cuanto variaran las clasificaciones anteriores ante la incorporacin de este nuevo mail. Para cada mail i de nuestro conjunto de datos de entrenamiento D podemos calcular: ( ){ }( ) { }arg max ( / ) ' ' arg max ( / )i ii i i i iP x w P w P x w P w V = Donde P(iw ) y( / ) 'iP x w son las distribuciones que se usaron en el momento de clasificar el mail en en cuestion y iV Vi cuanto vario dicha clasificacin. Si el mail nuevo mejora las clasificaciones anteriores, es decir, las aleja de la regin de incertidumbre puede considerarse como una instancia til para sumarse al conjunto de datos de entrenamiento. Si en cambio empeora la clasificacin, ya sea alternando una clasificacn anterior o acercandola e incluso haciendola caer dentro de nuestra zona de incertidumbre, ese mail agregara ruido y no aportara nada a la convergencia del clasificador. Podemos medir la variacin total de la siguiente manera Total iDV V = Teora de la comunicacin 75.19 Esteban Calabria - 78711 42Por claridad no incluiremos esta variacin en el algoritmo que mostraremos a continuacin. El resumen del algoritmo que emplearemos ante un mail nuevo es el que se muestra a continuacin: Observar las caractersticas iwdel mail recibido Si ( / ) 0j iP x w = algun jxde unmail a clasificar entonces preguntar al usuario su clasificacin e incorporar el mail a nuestro conjunto D de entrenamiento. Sino clasificar el Mail con un clasificador nave Bayes contra el conjunto D Si?MinimaIncertidumbre Incertidumbre