Categorización de Textos

Retomando la categorización de textos

2011-03-07T09:36:00.004-03:00

Hace bastante que no escribía en este blog... la verdad es que lo tenía algo de lado por mis muchas actividades; pero desde hoy lo retomaré: es una promesa.

Algunas observaciones que creo pertinentes para adentrarme nuevamente en el tema: estoy fascinado con la cantidad de publicaciones que están apareciendo respecto a la clasificación de textos. Es más, me llama profundamente la atención que están apareciendo empresas relacionadas exclusivamente con el tema. Tanto es así que hay empresas que "están llamando la atención de Gartner Inc. Al menos eso es lo que leí en este enlace, que aunque autoreferente, te muestra la existencia de empresas de Categorización de Texto, y no sólo departamentos o grupos dentro de otras empresas.

Otra cosa que me llamó la atención es la cantidad de patentes que esta empresa dice que tiene: 70 patentes. Esto me dice que estoy bastante desactualizado, por lo que tendré que ponernos al día :)

¿Dónde podría estar el error en mi modelo?

2008-12-02T15:20:00.002-03:00

Con una entrada similar a esta, pero en Inglés (Where did my (linear) model go wrong?), se hace un interesante análisis de lo que puede afectar la efectividad de un modelo de categorización de textos y por qué no se puede alcanzar una efectividad del 100%.

En definitiva, habla de 4 lugares desde dónde puede provenir el error:

Ruido en los datos en entrenamiento
Ruido en los datos de prueba
Representación insuficiente (no se han considerado las características correctas o suficientes)
Ejemplos insuficientes (los datos de entrenamiento no son suficientemente densos en algunas regiones)

Los motivos no son excluyentes entre sí.

Claro, después que lo leí, se "caía de maduro"... pero no siempre es fácil verlo.

Lectura interesante y recomendada.

Representación de documetos

2008-05-14T09:57:00.002-04:00

Cada vez se hace más frecuente que me pregunten respecto de cómo representar documentos, sobre todo, porque en la mayor parte de la documentación que encuentras aparece una sola: la representación vectorial.
Hoy, dado un correo que me envió, le explicaba a una futura colega cubana mi visión del tema, el que transcribo:

"Respecto a formas de representación, sin duda la vectorial es la más simple, aunque hay que tener un par de consideraciones.

"Quizás la más obvia sea la de la frecuencia, dado que puedes colocar la ocurrencia real (mala idea), una ocurrencia binaria (está o no está el término) o una ocurrencia ponderada (que es lejos la que más me gusta).

"También hay que tener presente qué vas a considerar para contar la frecuencia. Pueden ser palabras, frases, lemas o raíces, ó n-gramas.

"Y respecto a las palabras, tampoco las miremos en menos, dado que a que también podemos hacer algo con ellas: en vez de poner todas las palabras, podemos escoger palabras representativas (puro, cigarro, pipa... todos pueden ser representados con el término tabaco)... un poco, lo que hace k-nn.

"Si el tema que te interesa son las representaciones, pues la imaginación da para mucho. En este momento se me ocurre una que quise implementar y al final no le vi el aporte mayor en comparación a la complejidad de su manejo: mi diccionario era una lista de palabras identificadas con un correlativo. Cada documento era una lista de estructuras (o nodos), donde la estructura contenía el número de la palabra, su frecuencia ponderada y el puntero al siguiente nodo. La ENORME ventaja que tenía esta forma de organización es que era muy rápida de seguir y ahorraba el tremendo espacio vacío que usa la representación vectorial. El inconveniente, difícil de manejar y alto consumo de CPU."

Sé que en ese correo hubo muchas cosas que se me pasaron por alto. También que hay otras muchas formas de representación de documentos que no recuerdo o de plano no conozco, por lo que si puedes aportar con ideas, estas son bienvenidas. Al fin y al cabo, nos sirven a todos.

2008-05-09T15:24:00.004-04:00

La transferencia inductiva es aplicar el conocimiento aprendido en un conjunto de tares para mejorar la aplicación del conocimiento aprendido a nuevas tareas. La transferencia inductiva se está aplicacando en mejorar el rendimiento de la generalización en las tareas de clasificación usando los modelos aprendidos en algunas tareas relacionadas. En este artículo, mostramos un método para hacer transferencia inductiva para hacer la clasificación de texto más efectiva usando Wikipedia. Mapeamos los documentos de texto de diferentes tareas a un espacio de características usando Wikipedia, proveyendo así algún conocimiento oculto del contenido de los documentos. Se ha observado que cuando los clasificadores son construídos usando las características generadas desde Wikipedia, ellas son más efectivas en la transferencia de conocimiento. Una evaluación en las tareas diarias de clasificación en el corpus Reuters RCV1 muestra que nuestro método puede mejorar significativamente el rendimiento de la transferencia inductiva. Nuestro método superó exitósamente un obstaculo mayor observado en un trabajo reciente en una configuración similar.

Bajo esta presentación, encontré un artículo de HP que habla de esta transferencia inductiva.
La verdad es que recién estoy empezando a leer el artículo, pero debo reconocer que se ve muy interesante porque toca un tema del que soy absolutamente ignorante.
Cuando lo termine de leer publicaré mis comentarios y en lo posible una traducción o resumen.

Más gente... nuevos proyectos

2008-03-25T09:06:00.002-03:00

Siempre ando buscando acerca de de Categorización de Textos. En esta oportunidad encontré un post de Cesar Rodas, que habla de sus nuevos proyectos; en específico, GSoC - WP - Category Suggester - [Proposal].

En este post, Cesar habla de un desarrollo en PHP (en lo que evidentemente tiene mucha experiencia) que sugiere las categorías a un nuevo escrito mientras éste se redacta. Estaría basado en n-gramas y en post previos, desde los que aprendería las categorías.

Me llamó mucho la atención la aplicación práctica del proyecto por su originalidad, pero también llamó mi atención el uso de n-gramas, no porque sea una idea nueva, que no lo es; sino porque yo mismo tiendo a ni siquiera considerarlo pese a las enormes ventajas que tiene su uso.

Cesar hace una reseña de sus características, pero no está demás transcribirlas:

Son secuencias de n letras que se usan en vez de palabras.
Son independientes del idioma.
No precisan de algoritmos de lematización.
Son fáciles de "tokenizar" por su independencia del idioma.
Son insensibles a los errores de ortografía, lo que da una notable ventaja al aprender de las categorías que surgen de la creación misma de los post.

Normalmente me complico mucho con los algoritmos de lematización. El no tener que usarlos puede ser una enorme ventaja; aunque recuerdo haber hecho alguna vez, en los albores de mi estudio sobre categorización de textos, una experiencia con n-gramas y resultó ser más lento el aprendizaje... con el tiempo, me parece que el tiempo de aprendizaje es despreciable respecto al tiempo computacional que implica la sola lematización de los textos.

La idea es interesante, por lo que recomiendo su lectura. Vamos a seguir el trabajo a ver qué resulta.

Mindset: Yahoo aplica máquinas de aprendizaje a las búsqudas

2008-03-06T11:27:00.002-03:00

Bajo este título (en inglés), encontré en Digital Alchemy un interesante artículo de aplicaciones prácticas de categorización de textos, en este caso, impulsada por un gigante: Yahoo!.

La aplicación se llama Yahoo Mindset, está obviamente en pleno desarrollo y definitivamente esto promete... aunque quizás ampliando un poco más la cantidad de dimensiones del trabajo definitivamente sería un éxito; aunque no me cabe duda que lo harán.

Se trata de la utilización de máquinas de aprendizaje para definir si una página es comercial o escolástica... aunque me parece que la traducción literal no es la más afortunada, dado que en la página separa entre comercial e investigación.

La categorización tiene sólo dos posibilidades o categorías: pero usa una medida de cuán probable es que pertenezca a uno u otro grupo. De este modo ordena los resultados obtenidos de manera dinámica y pueden ser reordenada en tiempo real mediante una barra de desplazamiento.

Decir si es una aplicación de gran dificultad, es complicado. En primer lugar, todas las páginas deben ser categorizadas, lo que sabemos que implica una gran cantidad de recursos computacionales, lo que me hace pensar que el algoritmo utilizado debe ser algo así como árboles de decisión ó kNN; que todo debe estar preprocesado, que la búsqueda se realiza bajo los mismos conceptos que lo hace normalmente Yahoo y que la incorporación de máquinas de aprendizaje se limita a la ordenación de los resultados.

Puede, visto como lo expuse, que suene como que en realidad no es la gran cosa lo que ha hecho Yahoo Research, pero la verdad es que la incorporación de mejoras como esta puede hacer la diferencia en la navegación y búsqueda de información en el futuro.

Revisen esto!!!

2007-11-16T09:43:00.000-03:00

Sólo alcancé a leer la introducción, pero me parece que este trabajo está MUY bueno.
El autor es Ting Liu, autor del que aún no había escuchado nada, pero que de seguro muy pronto empezaré a escuchar más.

Administración de reclamos II

2007-11-15T14:22:00.000-03:00

Siguiendo con el análisis del documento que tratamos en el post anterior, veremos la explicación de la ponderación del vector de términos. No tengo nada que agregar, por lo que sólo resumiré lo que dice.

Ponderación del vector de términos

En esta fase, se construye un vector de términos por documento, que en este momento contiene la frecuencia "bruta" de aparición del término en el documento.

La ponderación normalmente es el producto de la frecuencia del término (tf) y el inverso de la frecuencia del documento (idf).

La frecuencia ponderada pretende medir la importancia del término para caracterizar el contenido de un documento.

En el documento, tf se obtiene por una transformación logarítmica de la frecuencia original del término, lo que reduce la importancia "bruta" de tf, que es importante para colecciones de documentos de largo variable.

donde i es el número del término, j es el número de documento, y n es la frecuencia del término.

El idf considera que si la aparición de un término en un documento es más raro, más discriminante es. Aunque, el peso de un término está inversamente relacionado con el número de documentos en los que el término aparece; es decir, la frecuencia documental del término.

donde n es el número total de documentos y dfi es el número de documentos donde el término está presente.

Finalmente, el peso o penderación del término i en el documento j está dado por

donde tfij es la frecuencia del término i en el documento j, e idfi es el inverso de la frecuencia de documento para el término i.

Reducción de la dimensionalidad

La matríz de términos por documento tiene gran dimension dado los muchos corpus distintos.
Más ún, la matriz es poco poblada (tiene muchos ceros) porque no todos los documentos tienen todos los términos del corpus.
En el texto, se usa "Indexación Semántica Latente por Descompsición Singular de Valores" (SDV por sus siglas en inglés) para reducir la dimensionalidad del espacio de características.
La Indexación Semántica Latente proyecta documentos desde un espacio de términos de grandes dimensiones a un ortonormal sub espacio semántico latente agrupando aquellos términos similares en varios (k) conceptos diferente. Toda esta información textual puede ser sumarizada en estos k conceptos.
Más aún, estos k conceptos (o variables SVD) son frecuentemente usados como variables explicativas en modelos tradicionales de clasificación de textos.
Esta reducción aproxima el peso de la matriz de términos por documento a una más pequeña de orde k, lo que la hace más manejable.
No se dice cómo calcular k, pero dice que se encuentran criterios en la literatura del tema.

Administración de reclamos

2007-11-12T16:40:00.000-03:00

Hace días que tengo en mi bandeja de entrada un correo con la referencia a un paper que no había tenido tiempo de leer.

De por sí, el título es sugerente: "Improving Customer Compliant Management by Automatic Email Classification Using Linguistic Style Features as Predictors".

La base de este paper es lo más interesante. Hasta ahora buscamos clasificar documentos de textos a partir de los términos que lo conforman; pero ellos hacen una clasificación simple: es o no es el correo un reclamo, a partir de una mezcla de la información del contenido sumado con la información que entrega el estilo lingüístico del correo.

Trabajo en una empresa que comercializa productos en acero, y les digo que el tema de la administración de los reclamos no es un tema para nada menor; y donde la administración oportuna de estos hace la diferencia entre los participantes de este mercado.

Ellos aseguran que al agregar el componente lingüístico al análisis de los correos, se mejora la predicción de si se trata o no de un reclamo, por lo que se puede dar un trato más apropiado a estos mensajes, disminuyendo el esfuerzo final de la empresa y aumentando la satisfacción del cliente. La mejora se puede notar en los tiempos, pero también en la efectividad de las respuestas al poder derivar las denuncias al personal apropiado sin necesidad de preparar al personal a quien corresponde responder consultas estar preparado en todos los ámbitos.

Entre las características que destacan, está que no usa la aproximación espacio-vector por el tamaño de la matriz resultante, sino Indexación Semántica Latente por medio de Descomposición Singular de Valores, esto es, la representación de los documentos por k conceptos representativos; donde la información del estilo lingüístico se introduce como un nuevo tipo de información textual.

Aproximación Espacio Vector

La idea de incorporar el estilo lingüístico no es lo único interesante de este paper. También se da una descripción de la aproximación espacio vector que es de lo más interesante.

Primero veremos qué es lo que propone y luego lo analizamos.

En esta representación, los documentos son convertidos en vectores de característica espacial basado en el peso de sus frecuencias a fin de seleccionar aquellos que entreguen más información a partir de su presencia en un diccionario.

Todo empieza con un preproceso, en el cual, se aplica una técnica de raw text cleaning. En esta, los caracteres especiales y la puntuación del texto se separa de las palabras.
En seguida, los errores ortográficos se corrigen comparando las palabras en el documento con el diccionario de referencia.

Luego viene el proceso de tokenización, en el que el documento se divide en tokens o palabras, donde los espacios sirven de separadores.
El resto del texto es dividido en palabras convertidas en minúsculas.
Las palabras son sumarizadas en informativas y no informativas. Las no informativas son los determinantes , conjunciones, auxiliares, preposiciones, pronombres, artículos, interjecciones, nombres propios, abreviaciones y números. Los informativos son los sustantivos , verbos, adjetivos y adverbios.

En seguida, viene el proceso de lematización, en el que las distintas variaciones de las palabras se llevan a una sola forma representativa llamada stem; lo que reduce el corpus del diccionario y aumenta la performance.
Todas las variaciones morfológicas se tratan de manera natural comparándolas con el diccionario de referencia. Si el término no es reconocido, el stemmer aplica alguna decisión estandar para entregar el stem correcto.

Lo siguiente es eplicar el term filtering, que sirve para reducir el número de términos irrelevantes: primero se sacan las palabras raras, del mismo modo que se sacan aquellas que aparecen menos de tres veces.
La misma regla se aplica en las palabras muy comunes como "a", "el", etc. Estas son conocidas como stopwords, y son palabras por su altea frecuencia no son discriminativas. Estas palabras están ligadas al idioma.

Al terminar el proceso, de todas formas se revisa el resultado manualmente.

Al final se consigue una matriz de grandes dimensiones de términos por documento, donde cada celda representa la frecuencia bruta de aparición del término en el documento.

Comentarios

Hay varias cosas que me llamaron la atención de la descripción del proceso.

Lo primero es la corrección de errores ortográficos. Si bien pareciera ser demasiado evidente que puede encontrarse este tipo de errores, hasta ahora no recuerdo haber leído de técnicas para la corrección de errores ortográficos. De hecho, si se piensa, puede ser bastante aventurado hacer este tipo de correcciones de manera automática tal y como lo propone el autor. Más aún, basado en un diccionario que no sabemos si es completo.
¿Me puse demasiado quisquilloso?. Veámoslo de la siguiente manera: si encuentro un reportaje donde habla de "wena Naty", existe la probabilidad que termine corregido "wena" por "vena" y "Naty" desechado por baja frecuencia o por ser un nombre propio.

De ahí surge mi segunda observación: dice que se excluyen los nombres propios. Me parece, de modo intuitivo y aún no tengo una comprobación experimental del hecho, que los nombres propios podrían entregar tanto o más información útil para la categorización de un texto que un sustantivo o un verbo.

La tercera observación va por el lado de la decisión estándar que tomaría el stemmer cuando no encuentra una palabra en el diccionario. Al respecto, creo que tomar una decisión no asistida puede ser contraproducente; aunque claro, no da ninguna pista de qué es una decisión estándar como para poder criticar con más fundamento.

Lo del term filtering y ese número de 3 como umbral para no considerar una palabra me parece que no corresponde. La experiencia indica que ese número no es arbitrario y es producto del tunning del procedimiento. Puede que ellos lo hayan conseguido así, pero no lo dicen.

Por último dice que el proceso se revisa manualmente, lo que me parece un acierto que no siempre hacemos. La importancia de esta revisión es fundamental, sobre todo en los primeros pasos del clasificador y mientras se consigue afinarlo adecuadamente.

Por ahora voy a dejar este post hasta aquí, y terminamos de analizar en el post siguiente.

Reconocimiento de texto y caracteres

2007-11-12T12:52:00.000-03:00

Siempre es llamativo cuando sale una nueva tecnología. En este caso, fue Xerox quien nos sorprendió con algo que quizás no tenía mucho de nuevo como idea, pero sí como implementación.

Leo en allamericanpatriot.com (no, no leo ese sitio de manera habitual, pero llegó el aviso por Google de la publicación de un artículo relacionado con categotización de textos) que Xerox habría desarrollado un software que es capaz de categorizar simultáneamente texto e imágen.

Los motivos para invertir tiempo en este tipo de desarrollos es obvio: el spam que recibimos es cada día más inteligente y el uso de imágenes es cada día más habitual como forma de evitar los filtros.

La parte simpática es que se trata de una aplicación que trabajaría on-line; por lo que las aplicaciones serían muchísimas: no sólo spam, también búsquedas en la web, organización de documentos, geografía, turismo... se me ocurren más, pero tampoco les voy a dar la tarea hecha: yo también estoy trabajando en algo.

La entrada no aporta mucha información de la implementación o la tecnología en sí, pero al menos da luces que hay gente trabajando en el tema.

Cómo trabajan los AntiSpam

2007-01-10T10:11:00.000-03:00

Encontré en CopiaTECH un interesante artículo de tres partes respecto de cómo trabajan los antispam. Para nuestros intereses, es muy importante porque los más modernos de éstos utilizan precisamente la tecnología de Categorización de Textos.

Creo que no está de más decir que me limitaré a traducir lo que dice el documento, aunque en ocasiones (las menos) lo he tenido que adaptar porque la redacción no me ha parecido precisamente clara.

Como no es el tema de mi blog, lo primero es definir spam: diremos que spam es cualquier correo electrónico no deseado y/o solicitado que recibamos.

La evolución de la tecnología anti-spam

A mediados de los 1990s, el método usado para disminuir el flujo de spam
estaba basada en las capacidades tecnológicas únicamente, tales como restringir el "reenvío de correo" (mail relay) de los servidores de correo, que originalmente no fue diseñada específicamente para resolver el problema de correo no deseado.

A finales de los 1990s, emergió la primera tecnología real anti-spam, como fue el filtro para correo masivo no solicitado de Netscape Messaging Server. Así, la mayor parte de los productos que formaban la infraestructura de mensajería no tenía estas capacidades y, para el 2000, estaba claro que los negocios tendrían que jugar un rol controlador de spam para proteger sus propios servidores en red.

También estaba claro que en ese momento las capacidades del software existente en la infraestructura y los productos asociados, como gateways antivirus para email, eran inadecuados y que los organismos estandarizadores de la industria no estaban preocupandose del tema. Esta situación, combinada con el hecho que los casos en la corte norteamericana relacionadas con spam, no tenían efecto aparente en los spammers (N. del T. spammer es quien genera spam), presentandose como un potencial oportunidad de negocio para las tecnologías anti-spam.

Precursores de la tecnología anti-spam

Virtualmente cualquier Simple Mail Transfer Protocos (SMTP) Message Transfer Agent (MTA) (N. del T.: SMTP es el protocolo usado en la transmisión de correo electrónico, mientras que MTA son las unidades encargadas de hacer esta transferencia... en lenguaje coloquial, podemos pensar que un SMTP MTA es un servicio/servidor dedicado a la transmisión de correo) tiene alguna habilidad nativa para controlar las comunicaciones con otros MTAs en Internet. Por ejemplo, Sendmail, el SMTP MTA más ampliamente usado en el mundo, tiene la habilidad de desabilitar el reenvío y limitar las redes desde las que puede aceptar mensajes.

Estas características, mencionadas arriba como precursoras y tecnología de primera generación, no fueron creadas especificamente para solucionar el problema del spam, ni tampoco constituyen una tecnología anti-spam en sí. Hasta hace pocos años, los productos de mensajería vendidos apuntaban a solucionar el problema implementando características rudimentarias como estas y otras como las "listas blancas" y "listas negras" dentro del conjunto básico de características anti-spam. Esta última aproximación aún es evidente en muchos productos que incluyen SMTP MTAs tales como IBM Lotus Domino, que no representa en realidad una tecnología anti-spam.

Las verdaderas tecnologías anti-spam, conocidas como tecnologías de segunda y tercera generación, son desarrollos relativamente recientes. Son tecnologías absolutamente nuevas y difieren completamente de los controles básicos de los MTAs. En particular, los algoritmos Bayesianos y los más recientes avances en análisis de texto, por ejemplo, usando Inteligencia Arficial, son un cambio radical de los pre-existentes mecanismos caracterizados o re-propuestos como tecnología anti-spam.

Tecnología Anti-spam - la primera generación

Es difícil distinguir claramente entre las características pre-existentes disponibles en la mayoría de los MTAs y las características de primera generación anti-spam porque estas últimas se siguieron usando (N. del T.: y se usan) aún cuando las nuevas herramientas estaban ampliamente desarrolladas para combatir el spam. Por ejemplo, las "Pruebas de Sobre y Cabecera", así como las "Pruebas DNS Simple", fueron motivados inicialmente por el combate al spam, pero no pueden distinguir directamente entre los mensajes spam y otros mensajes.

(Integrantes de la primera generación son:)

Controles básicos MTA: los controles MTA, que restringen la comunicación basada en redes y nombres de dominios, por ejemplo, para prevenir el "reenvío"; no son una tecnología anti-spam. Algunas de estas características son anteriores al problema del spam e inicialmente existieron con propósitos de seguridad.

Listas blancas y negras: las listas blancas y negras en un MTA son extensiones lógicas de los controles MTA básicos usados como una herramienta en bruto para controlar el spam. Aunque las listas blancas y negras son una característica anti-spam importante, ellas no son una tecnología nueva porque ellas son simplemente extensiones y no se apartan de los controles clásicos. Los productos antivirus y de seguridad en los MTAs tenían estas características antes de ser ser caracterizados como una característica anti-spam.

Búsqueda de palabras simples: Uno de los primeros métodos usados para combatir el spam fue la búsqueda simple de palabras. Esta funcionalidad existió antes de que el spam fuera un problema mayor en Internet, como parte de del filtrado de contenido y soluciones de comodidad y productos antivirus para e-mail. Esta aproximación suele ser usada para identificar un subconjunto de los mensajes que son spam, pero no es efectivo porque falla al reconocer variaciones de las palabras o variaciones en el contexto, y pueden resultar en muchos falsos positivos (correos legítimos identificados como spam). Los antivirus para servidores de correo y productos de seguridad tenían esta característica antes de ser usados como herramientas anti-spam. Evadir la búsqueda simple de palabras es trivial para los spammer usando variaciones de las palabras o cambiando las palabras por alguna alternativa.

Prueba del sobre y cabecera del mensaje: La prueba del sobre implica que el MTA revisa la información pasada a través del protocolo SMTP, por ejemplo el emisor y receptor del mensaje, se usa cuando se transfiere el mensaje y se rechaza si esta no es correcta o válida. La prueba de la cabecera entrega al MTA la habilidad de comprobar la información guardada dentro del mensaje, tal como el Para, De y Fecha y rechazar los mensajes si la cabecera está malformada o contiene información inválida. Mientras que estas características son obviamente muy usadas para eliminar el spam, ellas ahora sólo garantizan que el mensaje está correctamente construído y transmitido, y no si ellos fueron enviados por spammer o si el mensaje contiene spam; así, no son una tecnología anti-spam en rigor. También pueden ocurrir problemas en las cabeceras de los mensajes y en los sobres por razones no necesariamente relacionadas con el spam.

Prueba DNS simple: Mirando la información del emisor intercambiada durante el uso del protocolo SMTP y usando el sistema de dominio de nombres (DNS) de Internet, se puede validar la información intercambiada, por ejemplo verificar la existencia del dominio Internet del emisor o el nombre de la máquina que envía el mensaje (mirando el nombre asociado con la dirección Internet del emisor). La prueba DNS simple ayuda a prevenir el spoofing (cuando una máquina se enmascara como otra usando el mismo nombre). Aunque la prueba DNS simple es una herramienta significativa para combatir el spam, ella no es una tecnología anti-spam como tal porque sólo verifica la dirección y nombre de máquina de quien envía, no si quien envía en un spammer o si el mensaje contiene spam. La prueba DNS simple en una tecnología débil porque puede indicar un problema para una compleja variedad de razones legítimas y no necesariamente spam.

Tecnología anti-spam - la segunda generación

Las listas negras en tiempo real y las redes de firmas son la segunda generación de tecnologías anti-spam porque no son la reutilización simple o extensión de las características pre-existentes de los MTA con propósitos anti-spam. La segunda generación de tecnologías anti-spam existe específicamente con el propósito de detener el spam y está ampliamente mejorada respecto de los métodos anteriores.

Listas negras en tiempo real (RBLs): aunque son tecnicamente una prueba DNS cuando están basadas en direcciones Internet en vez de nombres de dominio; las RBLs fueron la primera real tecnología anti-spam. El concepto detrás del RBLs es simplemente mantener una lista de direcciones Internet que envían spam y las bloquea para transmisiones futuras. La tecnología tiene algunos (d)efectos que permiten burlarla, como cambiar la dirección IP o reenviar mensajes a través de un tercero previamente no identificado como spammer. Del mismo modo, los nombres de dominio pueden ser fácilmente adquiridos, enmascarados o hechos; así que los dominios desde los que spammer envían no pueden depender de los detectores de spam. Hay algunas RBLs externas que bloquean dominios o direcciones IP a partir de reclamos.

Redes de firmas: Son una significativa y relativamente nueva tecnología para combatir el spam. El concepto de redes de firmas es coleccionar e identificar mensajes spam generando una única "firma" que puede ser usada para identificar un mensaje dado. Dado que los mensajes spam son enviado de manera masiva (muchas copias del mismo mensaje) esta aproximación, si es soportada por un número suficiente de ejemplos de mensajes spam, puede detener un porcentaje significativo de correo no deseado. No obstante, el concepto es dependiente del tiempo empleado en la operación de la generación de la firma para comenzar a funcionar.

Tecnología anti-spam - la nueva generación

Identificar spam (por firmas) y spammers (con RBLs) está destinado a fallar. Los spammers pueden fácilmente burlar las RBLs y frecuentemente una buena red de firma toma tiempo en identificar mensajes de spam; además que nunca detectan el 100% de estos.

Filtros Bayesianos: Los filtros bayesianos, que es una aproximación estadística a la detección de spam basado en la probabilidad de spam de las palabras individuales. Usando como premisa la idea que el contenido comercial de los mensajes spam es el talón de Aquiles, el desarrollo de los filtros bayesianos cambió el foco de los esfuerzos anti-spam de redes y protocolos al contenido de los mensajes. Los filtros bayesianos simples , aunque efectivos en la mayoría del spam, pueden ser burlados fácilmente. Esta aproximación confía en el "entrenamiento" de los filtros procesando el spam conocido para generar un sistema basado en una calificación (score) de "palabras spam" que son usadas para evaluar los nuevos mensajes. Los spammers aprenden rápidamente a variar continuamente el contenido de los mensajes agregando palabras neutrales o variaciones de las palabras (como sustituyendo numeros por letras como el número "0" por la letra "O"). Con estas variaciones de las palabras neutrales y otros contenidos de mensajes y creando nuevas variaciones a las palabras, los filtros bayesianos pueden ser burlados consistentemente, y están siempre un paso atrás de los spam más recientes.

Inteligencia Artificial y máquinas de aprendizaje: Mientras las técnicas ya implementadas basadas en filtros bayesianos (por ejemplo, tomando en cuenta la proximidad de las palabras, tirando los tags HTML usados por los spammers a palabras riesgosas, etc.) continúan siendo ampliamente usadas, una aproximación más inteligente se hace necesaria. Alrededor del 2003, la necesidad de nuevas y especializadas tecnologías anti-spam era clara; y se veía venir un número de tecnologías de punta necesarias de desarrollar; tales como Corvigo, Proofpoint, y otras. Las aproximaciones de estas compañías fueron basadas en algoritmos de software originados en el campo de la inteligencia artificial, que es una rama de las ciencias de la computación. Fundamentalmente estas tecnologías realizan clasificación de texto usando tecnicas no-bayesianas. Así, ellas pueden adaptarse automáticamente a los cambios de las características del spam. Para hacer esto se han usado técnicas de máquinas de aprendizaje.

El futuro de la tecnología anti-spam

El spam existe en parte porque, cuando el SMTP fue originalmente creado, sólo gobiernos y universidades legitimadas, entidades universitarias e industriales, fueron conectadas a Internet. Ningún concepto de ilegitimidad o abuso de internet o del email había porque era un sistema cerrado. Con la comercialización de Internet en los 1990s, la situación cambió pero no así las tecnologías. Organizaciones de estandarización hoy trabajan especificando nuevas tecnologías que ayudarán a eliminar el spam forzando un alto grado de legitimidad en los emisores de mensajes. Esfuerzos anteriores en esta línea, se promovieron como tecnologías anti-spam, pero ellas intentaron legitimizar el correo electrónico comercial masivo, considerado por muchos como spam.

En contraste, los actuales esfuerzos basados en estandars para establecer una de autentificación de los emisores usando certificados digitales a los dominios de llaves para generar firmas digitales para los mensajes, pueden ser empleados por todas las empresas, en ves de sólo los emisores de correo masivo comercial. Los nuevos estándars, sin embargo, demoraran varios años en ser incorporados en una mayoría de los MTAs de Internet.

Signal Processing Approach

2007-01-08T15:31:00.000-03:00

Estaba revisando una presentación en SlideShare de la Universidad de Vigo, en España, bajo el nombre de A Signal Processing Approach to Distributional clustering of terms in Automatic Text Categorization.

Revisado el documento casi diapositiva a diapositiva, presento un resumen/recordatorio.

Lo primero es que define Categorización Automática de Textos como la categorización automática de documentos de texto en categorías predefinidas dado un conjunto de documentos de textos pre-categorizados. Esto es importante, pues entiendo se basa en aprendizaje por ejemplos, por lo que para que el método pueda implementarse, debe tener disponible un conjunto de entrenamiento / aprendizaje.

El método de Procesamiento de Señales propuesto, se enfoca en solucionar la problemática de la dimensionadlidad para el espacio de términos usados en la indexación. Para ello utiliza un Clustering Distribuido, definiendo esto como una efectiva y poderosa aproximación en la extracción de términos que ayuda a la reducción del espacio original:

Los términos son caracterizados por sus funciones de probabilidad de distribución sobre las diferentes categorías de documentos.

El clustering o agrupación es hecha siguiendo una medida de similaridad de las funciones anteriores.

El método de Clustering Distribuido tiene:

Medidas no basadas en información teórica
Pero sí basadas en una nueva interpretación del "Procesamiento de Señales", primero eliminado los términos que causan ruido y agrupando los restantes términos que sí aportan información siguiendo medidas de correlación o interdependencia.

Los resultados que se declararon fueron:

Re-confirmar los resultados obtenidos por otros algoritmos de Clustering Distribuido, que consiguen drásticas mejoras en la efectividad de la categorización, en especial con bajo número de características.
Y que los 20 conjuntos de grupos de noticias referenciados pueden ser indexados con una mínima pérdida de efectividad en la categorización con sólo 20 clusters.

Esto lo encontré interesante: la metodología para hacer el clustering:

Los documentos de textos son representados por la clásica indexación Bag of Words
El peso de cada palabra corresponde al número de veces que la palabra aparece en cada documento
Cada término es caracterizado por la probabilidad de la función de distribución en la variable discreta de la categoría.

Esta probabilidad de la función de distribución viene dada por una fórmula demasiado lenta de escribir en el blog, pero que se puede revisar en el documento original, pero básicamente está dada por:

"Las probabilidades son calculadas dividiendo el número de ocurrencias del término en todos los documentos a través de cada categoría, por el número total de ocurrencias del término en todos los documentos del conjunto de datos".

El término se asume como la señal de probabilidad, por lo que lo primero es eliminar las señales de ruido, esto es, las señales con una distribución muy plana, las que no entregan información de la variable para la categoría. Estas señales presentan una variaza baja.

Luego se agrupan señales similares; esto es, se basa en el grado de similaridad entre señales medidas por el coeficiente de correlación, el que está definido en el documento, y que tiene por hipótesis la equiprobabilidad de las categorías.

El algoritmo que en definitiva se utilizó, fue uno de clustering duro, esto es:

Se ordenó el vocabulario por varianza decreciente
Se eliminaron aquellos términos con varianza menor que un umbral dado (señales de ruido)
Se inizializaron M clusters aislados con los M términos
Cíclicamente se colocaron todos los términos en uno de los clusters, juntando aquellos correlacionados y creando nuevos clusters a partir de ellos.

Para permirir el juntar terminos pobremente correlacionados en el mismo cluster, se implementó:

Ventanas Dinámicas Expansión/Compresión

Las ventanas estáticas de dimensión M se expanden y comprimen en forma dinámica.

Clustering suave

Cualquier término puede ser compartido en más de un cluster.

Para la simulación del comportamiento, se usó 20 grupos de noticias con más de 20 mil documentos particionados en 20 grupos de noticias similares.

El filtro inicial incluyó: remover las stop words, luego las palabras no alfabéticas, y finalmente aquellas que aparecían en menos de 4 documentos o estaban menos de 4 veces en el conjunto de datos.

Luego de realizar la categorización, se graficaron los resultados Porcentaje de acierto v/s número de términos por cluster. Para ello, se utilizó el algoritmo Ingenuo de Bayes con funciones de selección Ganancia de Información, Chi cuadrado, Clustering duro y suave con ventanas estáticas, clustering duro y suave con ventanas dinámicas.

Según los autores, los restultados son notablemente mejores en clustering distribuido que con las funciones de selección clásicas, como Chi cuadrado y Ganancia de la información.

También concluyen que las curvas presentan un incremento inicial abrupto sobre los 20 clusters.

Por último, consigen asintomáticamente una efectividad de de alrededor del 79%.

Se declara que el cluster producido es bueno para 20 o más agrupaciones (igual al número de categorías definidas en la colección de 20 grupos de noticias); y que para el caso de los 20 clusters producidos, cada categoría está principalmente identificada por sólo uno y diferente cluster en una probabilidad del 0.9474 al 0.7552.

Sé que cada cual sacará sus comentarios del texto, pero en mi opinión, a pesar que se muestra como principal ventaja del método la alta efectividad con baja cantidad de términos; en mi opinión los resultados graficados no me son del todo convincentes, sobre todo por la falta de mayor información respecto al corpus de datos y cómo se seleccionaron los ejemplos de entrenamiento.

Pero sí creo que este documento tiene aspectos muy interesantes, y por eso mi comentario.

En primer lugar, cualquier estudio que se realice sobre categorización de textos es ya importante. En mi opinión, los elementos destacados del trabajo están en la eliminación de los términos generadores de ruido; y concuerdo con los autores que es una idea absolutamente correcta, funcional y necesaria.

También es plausible el haber hecho el estudio con clustering distribuido. La mayor parte de las herramientas comerciales que he visto no salen del Ingenuo de Bayes con raíces de palabras, que si bien es un avance, me parece que los sistemas multivaluares (que prueban más de una medida para la selección) nos permiten obtener mejores resultados y, con los computadores de ahora, con tiempos de respuesta aceptables.

Por último, en mi opinión la cantidad de ejemplos y el ambiente del que fueron extraídos es bastante imparcial, por lo que da crédito a los resultados obtenidos. Sería interesante ver cómo se comporta el mismo procedimiento en otros ambientes, como pueden ser con ejemplos de medicina.

Algoritmo de Porter enespañol

2006-03-08T23:36:00.000-03:00

Antes ya habíamos hablado del algoritmo de Porter, pero en [Panessi y
Bordignon, 2001] encontré una descripción mejor que la que habíamos dado
y por tanto paso a resumir.

El algoritmo de Porter permite hacer stemming, esto es extraer los
sufijos y prefijos comunes de palabras literalmente diferentes pero con
una raíz común que pueden ser consideradas como un sólo término.

Al realizar una búsqueda, el usuario puede perderse porque las palabras
están escritas de otra forma y con poca frecuencia en el documento.

Al aplicar stemming, se asegura que la forma de las palabras no penalice
la frecuencia de estas.

Los algoritmos de stemming, o lematización para quienes hablamos
español, más conocidos son: Lovins (1968), Porter (1980) y Paice (1990).
Todos eliminan "los finales" de las palabras en forma iterativa, y
requieren de una serie de pasos para llegar a la raíz, pero no requieren
"a priori" conocer todas las posibles terminaciones.

Originalmente todos fueron hechos para el inglés, y se diferencian en la
eficiencia del código y la elección de sufijos que identifican e
eliminan.

Estudios no definitivos, indican que los resultados conseguidos con
algoritmo de Lovins no concuerda con los resultados obtenidos con los
otros dos que se mencionaron.

La raíz de la lematización es un concepto distinto del de la lingüística
(orígen de las palabras) y no aporta al objetivo que persigue la
lematización.

No hay razón teórica para que los algoritmos de lematización no puedan
quitar también los prefijos (in, ante, anti, etc.), pero la mayor parte
de los métodos de stemmer sólo quitan sufijos.

La razón puede ser decidir cuándo es un prefijo y no parte de la raíz
(indispensable, introducción, etc.) o porque se puede quitar el
significado de la palabra.

El problema se extiende a cuando es un sufijo y no parte de la palabra.
Esto se resuelve fijando un mínimo de letras aceptables para la raíz y
con apoyo de una lista de palabras exentas de la aplicación de la regla.
Adicionalmente, hay reglas que indican cuándo un sufijo no debe
eliminarse.

Otro problema es el cambio de raíz en algunas palabras, por ejemplo, en
plural (repite, repetidos), donde en castellano el problema es mayor.

Los métodos de lematización son dependientes del idioma.

Tienen la ventaja que permiten la reducción de los índices, lo que
aumenta la velocidad de procesamiento.

El algoritmo de Porter tiene la ventaja de ir quitando sufijos por
etapas, en cambio Lovins requiere de la definición de todas las posibles
combinaciones de sufijos.

El algoritmo de Porter se publicó en 1980. Básicamente lee un archivo,
toma una serie de caracteres, y de esa serie, una palabra; luego valida
que todos los caracteres de la palabra sean letras y finalmente aplica
la lematización.

El lematizador hace pasar la palabra por varios conjuntos de reglas,
cada conjunto formado por "n" reglas y cada regla está constituida por:

1. un identificador de la regla
2. un sufijo a identificar
3. el texto por el que se reemplaza el sufijo
4. el tamaño del sufijo
5. el tamaño del texto de reemplazo
6. el tamaño minimo que debe tener la raíz resultante luego de aplicar
la regla (para no procesar palabras demasiado pequeñas).
7. Una función de validación (verifica si se debe aplicar la función una
vez encontrado el sufijo)

Cuando ya no queden más conjuntos de reglas por aplicar, se devuelve la
palabra resultante y se imprime.

Para traducir el algoritmo de Porter al español, se debe:

1. Ubicar los sufijos que ocurren frecuentemente en español.
2. Identificar los sufijos que ocurren juntos.
3. Establecer el orden en que ocurren

Para la selección de los grupos y orden de procesamiento, se deben tener
en cuenta:

1. Dos sufijos que ocurren juntos no pueden pertenecer al mismo
conjunto.
2. Las reglas que quiten sufijos más al final de cada palabra deben ser
procesados en un paso anterior a los que quitan otros.
3. Si un sufimo aparece siempre que ocurra otro, este sufijo es
condicional a la aparición del anterior.

Hay además reglas propias del castellano. Por ejemplo, el sufijo "nos",
que NO ES sufijo en palabras como campesinos, casinos, caminos, etc.;
pero sí en hacernos, ponernos, presentarnos, etc.

Para depurar el algoritmo hay que considerar 3 pasos:
1. Las palabras terminadas en "r", conceptualmente similares, suelen
quedar con distinta raíz, como en los verbos. Por ejemplo, caminar y
caminando. Primero se debe eliminar "ndo". Por lo que la eliminación de
las "r" es uno de los últimos pasos.

2. Similarmente, las palabras que terminan con vocales, por ejemplo, las
palabras terminación y terminal y/o terminó, se dejan para el final.

3. En último término, se aplica una tercer regla que elimina los tildes
de la raíz resultante. Por ejemplo, en diálogo y dialogó.

Proyecto de Ejemplo

2006-01-05T23:16:00.000-03:00

Antecedentes Generales

Con el fin de ilustrar el proceso de Categorización de Textos, es que se optó por una aplicación pura de categorización: la categorización de artículos de un periódico electrónico.

Durante ya bastante tiempo, se ha estado recolectando artículos, a una tasa de 30 artículos por día posible, consiguiendo un corpus que en este momento sobrepasa los 8500 artículos con alrededor de 25 categorías.

Estos artículos han sido extraídos desde www.latercera.cl, por un proceso automático y en forma absolutamente aleatoria.
Nos atrevemos a dar el nombre de la fuente porque se solicitó permiso para mencionarla, aunque no se cuenta con una autorización para publicar el corpus construido, pero sí para ser usado en nuestra investigación.

El formato en que se han ido almacenando es XML con la siguiente estructura:

<?xml version="1.0" encoding="UTF-8"?>
<articulos>
<articulo>
<fecha></fecha>
<titulo></titulo>
<link></link>
<texto>
</texto>
<canal></canal>
</articulo>
</articulos>

donde la fecha, es la fecha de publicación; el título, es el título del artículo; el link, es la dirección web desde donde se extrajo; el texto, es el desarrollo del artículo; y el canal, representa la categoría a la que pertenece.

Fases del Proyecto

Se dividirá el trabajo en 4 partes, la primera de ellas ya explicada, que es la recolección de los artículos desde el periódico de Internet.

La segunda etapa se trata del pre-procesamiento. En esta etapa, se eliminará por un lado todas aquellas cadenas de caracteres que son "basura", vale decir, caracteres que quedaron producto de la extracción misma desde la fuente. Por otro lado, se eliminará todas aquellas palabras que no aportan al contenido del artículo, sino a su redacción, tales como las preposiciones.

En una tercera etapa, se construirá los conjuntos de entrenamiento y prueba del clasificador. Esta etapa incluye la indexación de los documentos. La forma de indexar se detalla en un posteo posterior.

La cuarta etapa será entrenar los clasificadores. En esta etapa ya se debe tener determinado los métodos que se utilizarán para clasificar, aunque por su simplicidad y efectividad, el Ingenuo de Bayes y Support Vector Machine (SVM) estarán en la lista de los elegidos.

En una quinta etapa, se probarán los clasificadores construidos.

Durante la sexta y última etapa, se medirán los resultados obtenidos y se harán las comparaciones entre ellos.

Comitésde Clasificadores

2005-12-01T22:41:00.000-03:00

Los comités de clasificadores se basan en la idea que si, para una tarea
se requiere un experto, un grupo de expertos hará igual tarea mejor.

En categorización de texto, se aplican clasificadores para decidir si dj
pertenece a ci y se combina la salida apropiadamente.

* Requiere escoger k clasificadores

* Escoger la función de combinación

Los clasificadores del comité deben ser tan independientes como se
pueda, tanto en indexación como en el método inductivo. [Sebastiani,
2002]

Respecto de la función, la más simple es “por mayoría simple”:

Otra regla que se puede aplicar es por combinación lineal de pesos;
pesos que representan la efectividad relativa que se espera del
clasificador y que se validan en el conjunto de entrenamiento.

También se puede usar Selección Dinámica, donde los clasificadores se
eligen según sea el más efectivo para un documento dj similar. Su
decisión es la que adopta el comité.

Una alternativa intermedia es someterlo al juicio de todos los
clasificadores, pero la salida ponderarla según pesos para los
clasificadores según un documento dj similar al evaluado.

Se ha experimentado con varias combinaciones, normalmente de 3
clasificadores cada uno, pero han adolecido de una baja cantidad de
documentos a clasificar, por lo que los resultados son poco concluyentes

Clasificadores por SVM (Support Vector Machine)

2005-12-01T13:30:00.000-03:00

Las Máquinas con Soporte en Vector están presentes es Categorización de Textos desde el año 1998 [Sebastiani, 2002]. El método está basado en la Minimización Estructural del Riesgo [Yang, 1999] y está basado en un espacio vector donde el problema es encontrar una superficie que mejor separe los puntos que representan los datos en dos clases.

Para definir esta mejor separación, se introduce un margen entre las dos clases, y aunque se muestra el caso bi-dimensional separable linealmente en la figura, pero se puede generalizar para más dimensiones y no separable linealmente, lo que sería un hyperplano. La mejor separación, se refiere a que el margen entre la superficie que divide y los puntos se maximice.

En términos geométricos, puede ser visto como el intento de encontrar, a través de todas las superficies en el espacio |T|-dimensional, aquel que separa los negativos de los positivos, por el más amplio margen posible.

La fórmula muestra la superficie de decisión para SVM, donde x es un punto de dato arbitrario (a ser clasificado), mientras que el vector w y la constante b son aprendidas del conjunto de entrenamiento para los datos linealmente separables. Dado

que denota el conjunto de enternemiento, y donde yi tiene valor +1 si x es un ejemplo positivo y -1 si es uno negativo; el problema se limita a encontrar w y b que satisfagan:

lo que puede ser resuelto usando técnicas de programación.

Los algoritmos para resolver casos lineales se pueden extender para resolver casos no-lineales al introducir relajaciones a los márgenes de los hiperplanos o mapeando los vectores de datos originales a un espacio de dimensionalmente mayor donde no se pierdan las características de los
datos pero sí se puedan separar linealmente.

Es notable que la mejor decisión de superficie esté determinada sólo por un pequeño conjunto de ejemplos de entrenamiento, llamado soporte vector. Con sólo este conjunto de puntos, la decisión del hiperplano escogido para separar sigue siendo la misma.

Dos importantes ventajas para categorización de textos son:

La selección de términos frecuentemente no es necesaria, SVM tiende a ser bastante robusto al sobre ajuste y puede escalar a considerables dimensiones.
No requiere esfuerzo en sintonizarlo en un conjunto de validación.

Algo que estudiar

2005-11-25T22:25:00.000-03:00

Como se comentó en la presentación de este blog, lo aquí publicado no es más que lo que se ha ido recolectando respecto de Categorización de Textos.
Al respecto, se recomienda el excelente trabajo de Fabrizio Sebastiani, el que sin duda será muy educativo.

[Sebastiani, 2002] Fabrizio Sebastiani, 2002. Machine Learning in Automated Text Categorization, Consiglio Nazionale delle Ricerche, Italy. Revisado por última vez el 30 de agosto de 2005 en la URL www.math.unipd.it/~fabseb60/Publications/ACMCS02.pdf

Los siguientes papers tratan sobre Poesía y Hermes, dos aplicaciones libres basadas en Máquinas de Aprendizaje

[Gomez, Puertas, de Buenaga, Carrero, 2002] Gómez, José María y Puertas, Enrique y de Buenaga, Manuel y Carrero, Francisco, 2002. Text filtering at POESIA: a new Internet content filtering tool for educational environments. Última revisión en 30 de Agosto de 2005 en la dirección www.esi.uem.es/~jmgomez/papers/sepln02.pdf

[Gomez, Giraldez, de Buenaga, 2004] Gómez, José M. y Giráldez, Ignacio y de Buenaga, Manuel, 2004. Text Categorization for Internet Content Filtering. Última revisión en 30 de agosto de 2005 en la dirección http://tornado.dia.fi.upm.es/caepia/numeros/22/raepiaF09.pdf

La categorización de textos es considerada parte de la minería de textos. El siguiente documento da fé de ello.

[Hernandez, 2005] Hernandez Orallo, José, 2005. Web Mining, Universidad Politécnica de Valencia. Última revisión en 09 de Septiembre de 2005 en la dirección http://bbdd.escet.urjc.es/documentos/Master%20Ingenieria%20del%20Software%20DSIC%20Mineria%20de%20datos/dm4.pdf

Elsiguiente documento trata del problema del vocabulario en la comunicación.

[Furnas, Landauer, Gomez, Dumais, 1999] Furnas, G.W. y Landauer, T.K. y Gomez, L.M. y Dumais, S.T., 1999. The Vocabulary Problem in Human-System Communication: an Analysis and a Solution, Bell Communications Reseach. Última revisión en 13 de Septiembre de 2005 en la dirección http://www.google.cl/url?sa=t&ct=res&cd=3&url=http%3A//www.si.umich.edu/%7Efurnas/Papers/vocab.paper.pdf&ei=15UnQ6WxN7mI4QHz5rWCBw

[Yang, 1999] Yang, Yiming y Liu, Xin, 1999. A re-examination of text categorization methods. School of Computer Science, Carneie Mellon University. Última revisión en 25 de Noviembre en la dirección http://citeseer.ist.psu.edu/rd/0%2C361822%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/5062/http:zSzzSzwww.cs.cmu.eduzSz%7EyimingzSzpapers.yyzSzsigir99.pdf/yang99reexamination.pdf

[Joachims, 1997] Joachims, Thorsten, 1997 .Text Categorization with Support Vector Machines: Learning with Many Relevant Features. Última revisión en 25 de Noviembre de 2005 en la dirección http://citeseer.ist.psu.edu/rd/41909118%2C553162%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/26885/http:zSzzSzranger.uta.eduzSz%7EalpzSzixzSzreadingszSzSVMsforTextCategorization.pdf/joachims97text.pdf

[Medina Nieto M.A., 2001] EGRAI: Espacio Grupal con referencistas y Agentes como apoyo a la investigacion. Última revisión en 24 de Enero de 2006 en la dirección http://www.pue.udlap.mx/~tesis/msp/medina_n_ma/capitulo2.pdf

[Panessi y Bordignon, 2001] Procesamiento de Variantes Morfológicas en Búsquedas de Textos en Castellano . Walter Panessi y Fernando Raúl Alfredo Bordignon. Universidad Nacional de Luján, Departamento de Ciencias Básicas, División Estadística y Sistemas. Revisado por última vez en 08 de Marzo de 2006 en la direción http://www.tyr.unlu.edu.ar/TYR-publica/Varia-Morfo.pdf.

[Eyheramendy, Lewis y Madigan, 2001] On the Naive Bayes Model for Text Categorization. Susana Eyheramendy, David Lewis, David Madigan. Rutgers University. Revisado por última vez en 14 de Marzo de 2006 en la dirección http://www.stat.rutgers.edu/~madigan/PAPERS/susana3.pdf

Clasificadores basados en ejemplos

2005-11-25T09:08:00.001-03:00

Este tipo de clasificadores no construyen una representación explícita, pero confía en las etiquetas de los documentos de entrenamiento similares a los documentos de prueba. También se llaman lazy layer, porque posterga la decisión de cómo generalizar hasta que encuentra un nuevo caso.

Para decidir si dj pertenece a la categoría ci, mira si hay k documentos similares que pertenezcan a ci. Si la porción de coincidentes es alta, se toma la decisión. En otro caso, se decide que el documento no pertenece a la clase.

La similaridad se mide en relación a la distancia de los pesos. Se puede utilizar CSVi(dj) para determinar la distancia de los documentos y el método de los umbrales para convertir la decisión en una categorización binaria.

La construcción del clasificador involucra determinar k experimentalmente en el conjunto de prueba. Se ha propuesto 20 ó entre 30 y 45 documentos para una mayor efectividad. Al aumentar k no se afecta mayormente la performance.

Un caso de esta metodología es k-NN (k-Nearest Neighbors ─ los k vecinos más cercanos), que ha sido estudiada intensamente por más de cuatro décadas [Yang, 1999]. Ha sido aplicada a la categorización de textos desde las primeras investigaciones y está clasificado como uno de los métodos con mejor rendimiento para este tipo de aplicaciones. No divide el espacio de documentos linealmente, por lo que no sufre los problemas de los clasificadores lineales.

Su algoritmo es simple: dado un documento de prueba, busca los k vecim¡nos más cercanos entre los documentos de entrenamiento, y usa las categorías de estos k vecinos para determinar las categorías candidatas, construyendo un ranking de categorías dependiendo de la cantidad de documentos que compartan esta misma clasificación.

Normalmente los clasificadores basados en ejemplos usan pivote en el documento.

Este clasificador es absolutamente efectivo [Sebastiani, 2002], aunque tiene el inconveniente del tiempo que se requiere en el proceso.

Redes Neuronales - NNet

2005-11-25T09:08:00.000-03:00

Las redes neuronales también han sido utilizadas en la construcción de clasificadores.

Una red neuronal es una red donde la entrada son los términos y la salida la o las categorías de interés. Los pesos representan las relaciones de dependencia. Normalmente se representan como grafos, donde los nodos representan la suma de las entradas, las flechas representan las entradas y salidas de los nodos (como podría ser un término del documento), las que vienen modificadas por los pesos.

Un documento de test i, carga sus pesos de términos en las unidades de entrada de la red. La activación se propaga por la red y el valor de la salida determina la decisión de categorización.

Normalmente, se usa backpropagation,

donde las clasificaciones erróneas modifican los parámetros de la red para minimizar o eliminar el error.

La red neuronal más simple es el perceptrón, que es un clasificador lineal.

Otros clasificadores lineales de red neuronal implementan regresión logística.

Las redes neuronales no lineales son redes con una o más capas de unidades extra. En categorización de texto, normalmente representa interacciones de mayor orden entre los términos.

En general, no se notan diferencias al implementar redes neuronales lineales y no lineales.

Han sido intensamente usadas en Inteligencia Artificial [Yang, 1999] y se sabe han sido probadas con el corpus Reuter-21450, tanto con perceptrones como con Redes Neuronales de tres capas (con una capa escondida). En las experiencias se ha utilizado una red neuronal por categoría y han mostrado un alto costo computacional.

Un caso interesante de Clasificador Lineal - Rocchio

2005-11-21T23:43:00.000-03:00

El método de Rocchio:

Un caso interesante de clasificador lineal es aquel que utiliza el método de Rocchio. Básicamente, por que es fácil de implementar y, bajo ciertas condiciones, puede llegar a ser muy eficiente.

En este método, los clasificadores lineales utilizan un perfil explícito, esto es, un documento prototipo para la categoría con el cual se comparan. Son arreglos de pesos que representan un documento tipo basados en los pesos para cada atributo ci. Esta característica propicia que sea fácilmente interpretable por humanos.

El método calcula un clasificador
para la categoría ci,
donde

,

,

y

son los parámetros de importancia asignados a los ejemplos positivos y negativos.

Como se observa en las ecuaciones, básicamente calcula promedios de pesos, motivo por el que se justifica su eficiencia.

Pero al referirnos a la efectividad, tiene problemas con agrupaciones disjuntas de documentos

Como en el caso de la figura, el clasificador podría cometer grandes errores si el centroide no coincide con ningún documento.

Los clasificadores lineales pecan de este inconveniente precisamente porque dividen el espacio de documentos linealmente.

Mejoras al método de Rocchio

Una mejora que se puede intentar para el método de Rocchio, al crear el clasificador, es modificar el conjunto de valores negativos NEGAi. La propuesta apunta a escoger los valores que perteneceran al conjunto NEGAi, que ahora se llamará NPOSi (no positivos), y que contendrá aquellos documentos que son más cercanos a los positivos, si se quiere, los menos negativos.

Con esta modificación, la fórmula del modelo queda como:

donde el factor:

es más significante dado que son los más difíciles de separar de los positivos.

Una forma de encontrar los “cercanos positivos” es contrarrestando el centroide de los positivos, contra un documento base de los negativos. Los con menor "distancia" más altos son los elegidos.

Presentación de mi tema

2005-11-09T09:54:00.000-03:00

Hasta ahora no he escrito nada de mi aspecto personal, pero ahora me voy a tomar la licencia porque creo que es muy importante que aprenda a partir de mi experiencia.

Si estoy estudiando y publicando lo que he ido aprendiendo, es por que siento que necesito especializarme en algo, necesito algo en lo cual yo sea realmente un experto.

Quizás por lo mismo es que decidí integrarme al plan de Magister de la Universidad de Santiago de Chile, plan del que por estos días estoy haciendo ya su tesis... indudablemente, este es mi tema de tesis.

Ayer, ante el curso de Seminario de Tesis, más algunos invitados de la misma Universidad, presenté mis investigaciones orientadas a la tesis que realizo; pero en vez de ser una experiencia agradable, creo que fue más bien frustrante, aunque muy educativa.

Ahora expongo lo que siento fueron errores que no se pueden repetir una vez que me toque hacer la presentación de mi tesis, y que espero sirva al visitante de mi blog:

Incorporar elementos gráficos a la presentación: La mayor parte de los asistentes (muchos en relación a los que van normalmente a ese curso) no estaban interesados en mi tema. Noté que los escazos elementos gráficos que incorporé llamaron su atención y fueron muy didácticos a la hora de entender a lo que me refería.

No juzgar la intencionalidad de las preguntas: Si bien la mayor parte de las preguntas me parecieron sumamente atinadas, hubo otras no tan afortunadas. Erróneamente o no, sentí que fueron hechas con mala intención, lo que me desconcentró y no me permitió seguir mi exposición en condiciones óptimas.

No perder la paciencia: Relacionado con lo anterior, hubo un momento que ya no me interesaron las preguntas que me hizo este señor, por lo que de plano le respondí de mala manera para que no me preguntara más... craso error!!!. Además, debo intentar responder las preguntas y no caer en el debate con la audiencia.

Dejar las preguntas para el final: El tiempo que tenía para mi exposición era limitado, sin embargo dejé que me interrumpieran durante la exposición, lo que no me parece mal, pero dadas las circunstancias, hizo que me tomara más tiempo del que realmente disponía. Debo decir al principio de la presentación que las preguntas quedan para el final.

Colocar una diapositiva con el índice: La gente no tenía una visión global de hacia donde iba mi presentación, cosa que se podría haber solucionado con una diapositva con el índice al principio. En cierta ocasión, vi una presentación donde cada cierto tiempo se mostraba el índice con el próximo tema a tratar en otro color.

Introducir "violentamente" al oyente al tema: Los asistentes no sabían qué iban a escuchar, por lo que demoraron un rato en involucrarse en el tema. Una diapositiva con un gráfico que explicaba lo que hablábamos y que estaba a la mitad de la presentación, debió estar al principio.

Pulcritud de los términos: En más de alguna ocasión no utilicé el término exacto. No estoy seguro si fué una suspicacia o realmente enredé a alguien, pero me hicieron notar como un hecho grave el no haber utilizar el término exacto respecto de lo que me refería (datashow/proyector, metodología/clasificador, etc.).

Llevar la presentación en otro formato: Se perdió tiempo importante en tener que cambiar la presentación de formato para llevarlo a otra máquina. Eso distrajo la audiencia y la predispuso a la crítica.

Título de la exposición: El tema de la exposición debe ser tal que, con sólo leerlo, saber exactamente de qué se tratará la exposición, sin importar que quede algo largo o poco estético.

Separar tácitamente lo que es el marco teórico de lo que era mi proyecto en sí: Si bien eso se verá ayudado con la incorporación del índice, dejar en claro cuando terminamos de hablar de la teoría y cuando ya estamos hablando de lo que voy a hacer en mi proyecto.

Qué incluye y qué excluye el proyecto: En ningún momento me detuve y expliqué qué incluía y qué no mi proyecto. Creo que estaba claro si se revisa la totalidad de la presentación, pero la gente no estuvo siempre atenta, por lo que mucho de lo que nombré ni siquiera lo escucharon.

Acotar el objetivo del proyecto: Sumado a lo anterior, acotar suficientemente el objetivo ayuda a definir qué incluye y excluye el proyecto.

Definir el término del proyecto: En ningún momento hice mención clara de bajo cuales condiciones puedo dar por finalizado el trabajo.

Referirse a lo que es y no a lo que no es: En este blog también menciono "lo que no es categorización de textos". Mala idea. La presentación siempre debe ser constructiva y no destructiva respecto del conocimiento.

Presentación del orador y profesor guía: Algo que se me olvidó fue incluir mi nombre y el de mi profesor guía en la primera diapositiva. Eso me dará pié para presentar a mi profesor guía y a mi mismo.

Links: Quizás más de alguien me va a decir que "nadie va a mirar los links que incluí en la presentación como referencia". Pero yo quedé con la sensación que a mi presentación le faltó eso como motivación.

Módulo de tratamiento de textos: En mi presentación, en este blog, y en general en el proyecto que pretendo llevar a cabo con mi investigación; nunca aparece un módulo de tratamiento de textos, esto es: transformar documentos que llegan en distintos formatos (txt, xml, ps, pdf, doc, xsf, etc.) al formato que utilizará mi aplicación.

Corregir el esquema de la solución propuesta: Me di cuenta que cuando la expuse, le faltan y sobran características... en general, el dibujo es poco preciso y hasta incorrecto.

Sé que muchos esperan que publique la presentación que hice (JA!... vanidad... ni siquiera sé si alguien algún día leerá esto :), por lo que aquí se las adjunto.

Agradeceré, si es que estuviste en la presentación y hay algo que aportar, que lo incorpores como comentario.

Metodos en Linea

2005-11-03T12:21:00.000-03:00

Un clasificador en linea para una categoría ci, es un vector

que pertenece al mismo espacio |T| dimensional en que están los documentos.

Los métodos de aprendizaje para clasificadores lineales, se dividen en:

Batch: donde se analiza todo el conjunto de entrenamiento para construir el clasificador, como con el método de Rocchio

Lineales o incrementales: donde se construye el clasificador al analizar el primero de los documentos, y se afina este clasificador a partir del análisis de los documentos siguientes.

El método lineal o incremental es recomendable cuando no se tienen todos los documentos de ejemplo en el momento; o bien, cuando el clasificador va cambiando efectivamente al transcurrir el tiempo o se espera retroalimentación de parte del usuario.

Un método en línea simple, es el perceptrón, que es la red neuronal que está compuesta por un solo nodo.

En los perceptrones, inicialmente todos los pesos para el clasificador ci son iguales y positivos. Al analizar un ejemplo, si el la clasificación resulta positiva, se incrementa el peso wki del nodo en un valor A > 0; si por el contrario, la clasificación es negativa, se disminuye en un valor A <> 0.

El perceptrón es un caso de un algoritmo de algoritmo aditivo (los pesos se modifican a partir de sumas positivas o negativas), pero también los existen de tipo multiplicativo como Ganador inmediato positivo (Positive Winnow), que es similar al perceptrón, pero en vez de sumar o restar un A, dependiendo si la clasificación es positiva o negativa respectivamente; multiplica por una A > 1 para el caso positivo, y un 0 < A < 1, en caso contrario.

Hay una variante a este clasificador, que es Ganador Balanceado. En él, se usan dos pesos para cada término, uno positivo y uno negativo (Balanced Winnow), pero el factor multiplicado es el la diferencia entre ambos.

Los clasificadores en línea usan pivote tanto en la categoría como en el documento.

Métodos de Regresión

2005-10-27T23:22:00.000-03:00

Regresión se refiere a la aproximación del valor real de la función que determina la correcta clasificación del texto.

Uno de estos métodos es LLSF: Linear Least-Square Fit. En él, existen dos vectores asociados a los documentos:

- I(dj), de largo |T|, y que representa a los términos
- y O(dj), de largo |C|, y que representa a las categorías. Es de tipo binario para entrenamiento y no binario para prueba.

Este procedimiento trata de determinar O(dj) dado I(dj), y construir una matriz M con |C| filas y |T| columnas, tal que al hacer el producto cruz entre M e I(dj) se encuentre O(dj).

La matemática del método puede sonar complicada, pero no lo es: se calcula la matriz de los datos de entrenamiento calculando un “linear least-square fit” que minimice el error en la fórmula

, donde minM(x)=M para el que x es mínimo

representa la llamada norma de Frobenius para una matriz |C|x|T|,

I es la matriz |T|x|Tr|, donde las columnas son los vectores de entrada para los documentos de entrenamiento; y O es la matriz |C|x|Tr|, donde las columnas son la salida de los vectores de entrenamiento.

M normalmente se calcula haciendo una descomposición valor singular en el conjunto de entrenamiento, y esta entrada genérica representa el grado de asociación entre la categoría ci y el término tk.

LLSF es considerado uno de los más efectivos clasificadores de textos, pero tiene el serio problema del costo computacional.

Clasificadores por reglas de decisión

2005-10-27T23:05:00.000-03:00

Son clasificadores construidos a partir de métodos inductivos de reglas tipo condicional, donde los literales en la premisa denotan presencia o ausencia de una palabra clave; por ejemplo, si está la palabra fútbol, es probable que se trate de deportes.

En tal sentido, tienden a ser similares a los árboles de decisión, pero además tienden a generar clasificadores más compactos.

Inicialmente los documentos se expresan como un vector de términos n1,..., nx -> C, donde C indica si pertenece o no a la categoría.

A estas reglas, se les aplica un proceso de generalización donde la regla se modifica removiendo premisas o mezclándolas.

Finalmente se podan con un criterio similar al de los árboles de decisión.

Existe una amplia variedad de métodos, heurísticas y criterios empleados para la generalización y la poda.

Clasificadores simbólicos - Árboles de Decisión

2005-10-19T15:30:00.000-03:00

Si bien puede ser fácil de implementar los clasificadores probabilísticos, son difíciles de interpretar por lo humanos.

No es el caso de los Algoritmos Simbólicos, de los Aprendices Inductivos de Reglas y de los Árboles de Decisión; entre otros.

El caso de los Árboles de Decisión, DT de sus siglas en Inglés (Decision Tree), tienen la facilidad que son representables esquemáticamente como un grafo, donde sus nodos internos están etiquetados por términos, sus hojas con pesos y sus hojas con categorías.

Así, para encontrar la categoría de un documento, basándose en el vector que representa el documento, se navega recursivamente hasta una hoja.

Hay paquetes estándar de aprendizaje de árboles de decisión. Los más populares son ID3, C4.5 y C5.

Un método simple de aprendizaje para árboles de decisión es Dividir para Conquistar. En este método,
- Se revisan todos los ejemplos con igual etiqueta: los que pertenecen y los que no pertenecen a ci.
- Sino, se seleccionan aquellos términos que tengan igual término tk y se colocan en un subárbol separado.
- Se repite el proceso hasta que en la misma hoja queden todos los ejemplos de entrenamiento con igual categoría.

Para saber qué término escoger, normalmente se usan criterios como ganancia de la información o entropía.

Además, normalmente se usa posteriormente un proceso de poda para evitar el sobreajuste del árbol.

Los árboles de decisión han sido usados normalmente como el proceso principal en las herramientas de clasificación de texto; aunque también se les suele encontrar como punto de partida o como parte de un comité de clasificación en otras herramientas.

Clasificadores Probabilísticos - Ingenuo de Bayes

2005-10-19T13:03:00.000-03:00

El clasificador CVSi(dj), es quizás el clasificador más utilizado y el que más frecuentemente se encuentra en la literatura. Este clasificador expresa la probabilidad de que un documento, representado por el vector dj cualquiera, pertenezca a una clase ci dada. De forma matemática, se puede ver de la siguiente manera:

donde el espacio de eventos es el de los documentos, P(dj) es la probabilidad de escoger aleatoriamente un documento este esté representado por el vector d(j); y P(ci) es la probabilidad de que al tomar un documento cualquiera este pertenezca a la clase ci.

Estimar la probabilidad anterior no es fácil por lo complejo de dj; por lo que normalmente se asume que las variables que componen el documento vector son independientes; por lo que se puede representar la probabilidad anterior como:

Dada esta suposición, es lo que se conoce como Ingenuo de Bayes (Naive Bayes), y por su simplicidad y rendimiento, es ampliamente utilizado en Categorización de Textos.

De todas las aproximaciones del Ingenuo de Bayes, la más común es la Independencia Binaria, donde se usan valores binarios para la representación del documento en el vector; pero se pueden encontrar otras variaciones que apuntan a:
- Relajar la restricción que el vector documento tenga valores binarios
- Introducir normalización en el largo del documento
- Relajar la suposición de independencia

Construcción Inductiva de Clasificadores de Texto

2005-10-18T10:09:00.000-03:00

Como se vió, existen dos formas de clasificar texto: una manera dura, donde se toma una decisión booleana respecto a la pertenencia o no del texto a una determinada categoría; o una graduada, donde se estima una probabilidad de pertenencia.

De manera similar, hay dos formas de crear los clasificadores: una manera dura o automatizada, donde se deja la responsabilidad completa de la clasificación del texto al clasificador; y una parcialmente automatizada, donde el clasificador entrega una "proximidad a la clase".

En el caso de la clasificación dura, se define una función CVSi que determina si pertenece o no a la categoría (D->{V, F}). Esta función D, es en realidad una función que entrega un valor entre 0 y 1, y se define un valor umbral por sobre el cual la respuesta de D es considerada verdadera y falsa en otro caso.

El caso de la clasificación parcialmente automatizada es similar desde el punto de vista que también define una función CVSi que entrega un valor entre 0 y 1, pero que en este caso indica la proximidad a una clase; y así como funciona para clasificación con pivote en el documento, funciona para clasificación con pivote en la categoría.

Además, la función CVSi toma distintos significados dependiendo del método de aprendizaje utilizado. Así, para el Ingenuo de Bayes indica probabilidad; en cambio para Roccio, es una medida de proximidad en el espacio |T|-dimensional.

Determinación de Umbrales

Se distinguen dos caminos para la determinación de umbrales: analítica y experimental.

El caso de la determinación analítica, sólo es posible cuando hay un resultado teórico que indique cómo calcular el umbral que maximice el valor esperado para la función efectividad. Normalmente se utiliza con funciones cuya salida sea una probabilidad y cuya efectividad sea calculada por una medida de decisión teórica, como la utilidad .

Pero este análisis no siempre es posible. Para estos casos la determinación del umbral es en forma experimental, para lo que existen varias alternativas.

- Una manera es Scut, donde se prueban distintos umbrales y se escoge el que maximice la efectividad. Lo normal es que para esta forma de determinación se seleccionen distintos umbrales para distintas categorías.

- Una segunda alternativa es Pcut, donde se establece en aquel valor donde la generalidad del conjunto de validación es cercano a la generalidad del conjunto de prueba. Esta forma de determinar el umbral incorpora el principio que el porcentaje de documentos que pertenece a una determinada clase debiera mantenerse en el conjunto de entrenamiento que en el de prueba. Este método no se usa para clasificación con pivote en el documento.

- Una tercera forma, algo menos común, es el de umbral reparado, Rcut o umbral "k-per-doc"; donde una cantidad k de categorías es asignada a cada documento, aunque el umbral no está aplicado en el sentido anterior, pero se usa con pivote en el documento, y no permite una sintonía fina.

Reducción de la dimensionalidad

2005-10-06T21:29:00.000-04:00

Se denomina Reducción de la Dimensionalidad a disminuir el tamaño del vector que contiene los términos representativos de un documento.

La razón de querer disminuirlo es que los algoritmos más sofisticados de inducción tienen problemas para manejar vectores de gran tamaño, por eso se reduce |T|<<|T'|

Además, el reducir la dimensionalidad entrega la ventaja que disminuye el sobre ajuste, que es el fenómeno en el que el clasificador aprende las características contingentes y no sólo las constitutivas del documento.

Si bien hay muchas cifras respecto de cuánto debe ser esta reducción de dimensionalidad, llegando incluso algunos autores a proponer un 50%; la verdad es que una cifra así o superior puede llegar a ser perjudicial porque se puede llegar a eliminar términos con significado para el documento.

Respecto de los métodos de reducción, hay varios propuestos; la mayoría de ellos provienen del álgebra lineal o de la teoría de la información.

La Reducción de la Dimensionalidad puede ser vista desde dos puntos de vista:

- De modo Local: esto es, para cada categoría, es escoge |T'|<<|T| para la clasificación de la categoría (vale decir, cada categoría tendrá su propio conjunto de términos para ser evaluado). Normalmente, el valor de |T'| va de 0 a 50 términos... aunque intuitivamente se trata de cantidades empíricas.

- De modo Global: vale decir, el mismo conjunto de términos será utilizado para evaluar la clasificación en todas las categorías.

[Sebastiani 2002] nos dice que ambas formas han impactado en el resultado final, pero no se ha notado cambio cuando se trata de aprendizaje supervisado.

Respecto de cómo escoger los términos, también se ha encontrado dos formas:

- Reducción de Dimensionalidad por Selección: de los términos disponibles, se escogen los más representativos.

- Reducción de Dimensionalidad por Extracción: Los términos en T' no son los mismos que en T; por ejemplo, T' puede contener sólo palabras y T no sólo eso; pero son obtenidos por combinación o transformación de las originales.

Reducción de la dimensionalidad por Selección de Términos

También se le llama Reducción de Dimensionalidad por Espacio de Términos (TSR - Term Space Reduction).

La idea básica es que, dado un conjunto de términos T, seleccionar un subconjuto T', con |T|<<|T'|; con el que se indexan los documentos.

El TSR, ha mostrado mejorar la efectividad de la clasificación menor de un 5% dependiendo del clasificador, la agresividad de la reducción y la técnica TSR utilizada.

Dentro de las técnicas, una que debe llamar la atención es aquella llamada wrapper, que agrega y quita términos del conjunto T' inicial, para luego generar el clasificador. Una vez realizadas varias iteraciones, se selecciona aquel conjunto que presente mejores resultados. Si bien esta técnica parece ser buena, dado que a medida que aprende se afina, es prohibitiva en la mayoría de las aplicaciones de categorización de textos comunes dado el tamaño del espacio que requiere.

Frecuencia Documental

Esta es una sencilla técnica, aunque muy efectiva, donde se escogen aquellos términos que presentan mayor ocurrencia en los documentos.

Se ha demostrado (Sebastiani, 2002) que se puede disminuir la dimensionalidad del conjunto T hasta en un factor de 10 sin pérdida de información; y hasta en 100 con una pérdida de información despreciable.

Previo a la selección de los términos, y en un detalle no menor, se eliminan aquellos términos que, aportando a la redacción, no aportan información, como adverbios y preposiciones. El listado de estas palabras es almacenado en un conjunto denominado Stop Words.

A esta lista, hay quienes eliminan además aquellos términos que aparecen en un conjunto muy reducido de documentos, los que varían de 1 a 5.

Otras funciones de Teoría de Información

Nuevamente la Teoría de Información aporta a la categorización de textos; en este caso, a la reducción del espacio de términos.

Adjunto vemos un listado de las más conocidas sin perjuicio que se pueda encontrar alguna más.

Las probabilidades son interpretadas en un espacio de eventos para los documentos, y son estimadas contando las ocurrencias en el conjunto de entrenamiento.

Todas las funciones son especificadas localmente a una categoría específica ci, con el objeto de calcular el calor para el término tk en un sentido “global”independiente de la categoría.

Lo que intentan capturar es la intuición que los mejores términos para ci son aquellos distribuidos más diferentemente en el conjunto de ejemplos positivos y negativos para ci. De este modo, las interpretaciones para este principio varían a través de las diferentes funciones.

La mayoría de las funciones de la tabla han mejorado con frecuencia de documentos.

Colectivamente, los experimentos reportados indican que en cuanto a performance que el Coeficiente NGL, Tasa impar y Coeficiente GSS, son mejores que Xi Cuadrado y Ganancia de Información; y estos, a su vez, son mejores que el resto de los restantes presentes en la tabla.

Una observación interesante que nos muestra [Sebastiani, 2002], es que Xi cuadrado y ganancia de información, han podido, con distintos corpus, reducir la dimensionalidad en un factor de 100 sin pérdida de efectividad.

Reducción de la dimensionalidad por Reducción de Términos

El objetivo es similar a la por selección de términos, vale decir, a partir de T, generar un T' donde |T'|<<|T|.

La diferencia está en que busca el aumento de la efectividad en la existencia de palabras polisémicas, hominómicas y sinonímicas.

Se llama polisemia a la capacidad que tiene una sola palabra para expresar muy distintos significados. Al igual que la homonimia, en el caso de la polisemia se asignan varios significados a un solo significante. Pero, mientras la homonimia se produce por coincidencia de los significantes de diversos signos, la polisemia se debe a la extensión del significado de un solo significante. (Fuente: Wikipedia.org)

El método, cualquiera que este sea, se basa en:
- Un método de extracción de nuevos términos a partir de los viejos
- Un método de transformación de la representación original a la nueva basado en la nueva síntesis.

Don métodos se han probado en Categorización de Textos: Agrupación de Texto (Text Clustering) y Indexación Semántica Latente (Latent Semantic Indexing – LSI).

Agrupación de Textos

Trata de agrupar palabras con alto grado de semejanza (centroide o término representativo) para ser usado como término en la dimensión del espacio vector. Trata de hallar sinonimia.

El clustering puede ser no supervisado:
i)Buscar términos semejantes por alguna medida de similaridad
ii)Buscar co-ocurrencia o co-ausencia en los documentos de entrenamiento

o supervisado:

Se agrupan aquellos términos que tienden a estar presentes en la misma categoría o grupo de categorías.

El supervisado ha presentado mejores resultados con sólo un 2% de pérdida de la efectividad con una agresividad de 1000 y mejoras al bajar la agresividad.

Los resultados con no supervisados son pobres.

Indexación Semántica Latente

Originalmente fue desarrollado para Recuperación de la Información para resolver problema de uso de sinónimos, términos similares y palabras polisémicas en representación de documentos.

Comprime vectores de documentos en vectores de menor espacio dimensional, cuyas dimensiones son obtenidas como combinación de las dimensiones originales mirando sus patrones de co-ocurrencia.

Las dimensiones obtenidas no son intuitivamente interpretables, pero trabajan bien trayendo la estructura semántica latente del vocabulario usado en el corpus.

Representación de Documentos

2005-10-04T17:30:00.000-04:00

Existen varias aproximaciones a la representación de la información (Hearst and Hirsh 1996):

- Bag of Words: cada palabra constituye una posición de un vector y el valor corresponde con el nº de veces que ha aparecido.

- N-gramas o frases: permite tener en cuenta el orden de las palabras. Trata mejor frases negativas “... excepto ...”, “... pero no...”, que tomarían en otro caso las palabras que le siguen como relevantes.

- Representación relacional (primer orden): permite detectar patrones más complejos (si la palabra X está a la izquierda de la palabra Y en la misma frase...).

Sea cual sea la representación a utilizar, es necesario indexar el documento, vale decir, representaciones compactas de él. El tipo de indexación dependerá de cual represente mejor las unidades de texto (semántica léxica) y las reglas del lenguaje natural (semántivca composicional).

Normalmente se utiliza para la representación un vector de pesos de los términos,

donde cada posición representa una característica del documento y contiene el peso que en el documento específico se asigna a la característica. Este peso viene dado por un valor normalmente entre 0 y 1. T representa el conjunto de características que está presente al menos una vez en el documento.

Los términos normalmente son palabras, en cuyo caso estamos ante un bag of words, pero también podría ser algo más complejo como se vió arriba. Del mismo modo, el peso puede ser binario, el término está o no presente; o un valor entre 0 y 1, para representar, por ejemplo, el peso relativo de la palabra en el documento. Todo depende del algoritmo usado.

La verdad es que, por ejemplo en [Sebastiani 2002], hay numerosa literatura que habla de que representaciones más complejas que bag of words; como podrían ser frases, tanto sintácticas (de acuerdo a la gramática del idioma) como estadísticas (que no es gramatical, sólo una secuencia de palabras), no han demostrado ser más efectivas. Esto dado que las frases, si bien tienen mejores características semánticas, tienen menores características estadísticas que las palabras solas, por la existencia de sinónimos, entre otros problemas del lenguaje, y la menor frecuencia en los documentos. [Sebastiani et al.] también aclaran que una mezcla de frases y palabras sueltas da mejor resultado, aunque esto es objeto aún de estudio.

Cuando se trata de pesos no binarios, normalmente se calcula una frecuencia de aparición del término en el documento. La ecuación de abajo es el ejemplo más común de estas ecuaciones:

donde Card() representa la cantidad de veces que el término aparece en el documento.

Esta ecuación muestra que:
- a mayor ocurrencia del término en el documento, es más representativo del contenido
- mientras mayor sea la cantidad de documentos que contengan el término, éste es menos discriminador.
- al igual que muchas otras ecuaciones equivalentes, el orden de aparición del término ni la sintaxis de él, no reviste importancia.

Para que los pesos pertenezcan al rango entre 0 y 1, normalmente son normalizados por el coseno de normalización:

Existen otras técnicas de indexación, como probabilísticas o documentación estructurada, necesarias, por ejemplo, cuando Tr no está disponible y la cardinalidad del término no se puede calcular.

Antes de indexar, se eliminan las palabras neutras, aunque es controversial respecto de la procedencia (stemming), vale decir, agrupar palabras que comparten la misma raíz morfológica; dado que se han reportado casos donde ha sido perjudicial a la efectividad.

Dependiendo de la aplicación, se indexa todo el texto o sólo parte de él, como con los documentos estructurados.

La aproximación de indexación Darmstadt

El proyecto AIR (AIR/X) es uno de los más importantes esfuerzos en Categorización de Textos. Duró más de 10 años y desde 1985 es usado en clasificación de literatura científica, y cuenta del orden de O(105) documentos, agrupados en el orden de O(104) categorías.

La indexación utilizada en ese proyecto fue DIA (Darmstad Indexing Approach), que usa un vocabulario controlado pero ampliado con características o propiedades para los términos, documentos, categorías y relaciones entre estos. Por ejemplo:

- Propiedades de un término tk: por ejemplo, idf para tk

- Propiedades de una relación entre un término tk y un documento dj: por ejemplo, el tf para tk en dj; o la ubicación (título, resumen, etc.) de tk en dj.

- Propiedades para un documento dj: por ejemplo, el largo del documento.

- Propiedades de una categoría ci: por ejemplo, la generalidad para el conjunto de prueba de la categoría

Para cada posible relación documento-categoría, existe un “vector descriptor de relevancia” rd(dj, ci) que reúne las características de la relación. El tamaño de este vector es determinado por el número de propiedades consideradas y es independiente de la cantidad de términos, categorías o documentos.

La relación entre término y categoría se obtiene del conjunto de entrenamiento y se expresa como una probabilidad P(ci|tk) de que el documento pertenezca a la categoría ci (DIA association factor)

Esta indexación no ha sido usada para otras investigaciones, pero cobra y aumenta importancia en indexación de documentos estructurados y páginas web.

Los conjuntos de entrenamiento, prueba y validación

2005-10-03T23:12:00.000-04:00

Como ya se ha dicho, la categorización de texto basada en aprendizaje necesita ejemplos para deducir las reglas de clasificación.

Normalmente, se recolectan ejemplos de textos correctamente clasificados, normalmente tarea realizada por expertos humanos; los que se agrupan para servir de entrada al clasificador.

A estos ejemplos recolectados se les denomina generalmente el corpus inicial; y está definido como el conjunto O={d1,...,dn} contenidos en D preclasificados en C={c1,..., c|C|}, donde C es el conjunto de categorías existentes y D el conjunto de documentos.

A este conjunto inicial de documentos, o corpus inicial, se puede dividir de diferentes formas. Lo más normal es dividir en Entrenamiento y Prueba, donde el conjunto de entrenamiento sirve para educar al clasificador, y el de prueba para medir la efectividad conseguida. Estos conjuntos son disjuntos. Luego de probarlo, algún parámetro se moverá de modo de mejorar la efectividad del clasificador. Para ello se tiene reservado una parte del conjunto de entrenamiento no utilizado antes, que permite observar el resultado de este tunning o sintonización sobre los parámetros.

Otra manera es la Validación Cruzada. En esta variante, también conocida como k-fold cross validation; el conjunto de ejemplos conseguidos se divide en k conjuntos disjuntos, con los que iterativamente se van generando conjuntos de entrenamiento y prueba. Como el resultado será una serie de clasificadores menores, la efectidad final del clasificador está dada por el promedio de los clasificadores individuales. Al igual que el anterior, se reserva un conjunto para sintonización de los parámetros.

Se definirá Generalidad como el porcentaje de documentos del conjunto de entrenamiento que pertenecen a una categoría, de la forma como la define la siguiente fórmula:

Máquinas de aprendizaje y Conocimiento Ingenieril

2005-09-16T12:52:00.001-04:00

En la década de 1980, los clasificadores que existían eran producto de la construcción hecha por expertos en forma manual mediante el uso de reglas lógicas; del tipo si entonces . (DFN: Disjuntive Normal Form). A estos clasificadores se les calificó como de Conocimiento Ingenieril.

Ejemplo de esto es Contrue, un clasificador que se aplicó sobre un conjunto de entrenamiento de Reuter.

El inconveniente de esta forma de construir clasificadores es conseguir el conocimiento: se debe hacer manualmente por ingenieros con conocimientos y ayuda de expertos en el área y categoría, y si las categorías son actualizadas, el trabajo debe rehacerse, buscando nuevos expertos para las nuevas categorías.

Aunque se informó de un 90% de efectividad para Construe, [Sebastiani et al.] advierte que no hay otros sistemas probados con igual conjunto de datos, y no se sabe si fueron tomados aleatoriamente o escogidos.

Las Máquinas de Aprendizaje han sido las dominantes desde la década de 1990 en adelante. Acá, se construye un clasificador por un proceso inductivo que corre sobre documentos ya clasificados manualmente, de los que se deducen las características relevantes. Es un proceso de aprendizaje supervisado.

Las ventajas de Máquinas de Aprendizaje sobre Conocimiento Ingenieril, son claras: ahorro de esfuerzo en construir el clasificador; lo que permite ahorro en la actualización de categorías o si el clasificador se porta a otro ambiente.

Para el uso de Máquinas de Aprendizaje, la clave son los documentos ya clasificados: es más fácil clasificar un conjunto de documentos que construir y afinar un conjunto de reglas de clasificación.

2005-09-16T12:52:00.000-04:00

Las máquinas de aprendizaje como aproximación a la categorización de textos

En la década de 1980, los clasificadores que existían eran producto de la construcción hecha por expertos en forma manual mediante el uso de reglas lógicas; del tipo si entonces . (DFN: Disjuntive Normal Form)

Ejemplo de esto es Contrue, un clasificador que se aplicó sobre un conjunto de entrenamiento de Reuter.

El inconveniente de esta forma de construir clasificadores es conseguir el conocimiento: se debe hacer manualmente por ingenieros con conocimientos y ayuda de expertos en el área y categoría, y si las categorías son actualizadas, el trabajo debe rehacerse, buscando nuevos expertos para las nuevas categorías.

Aunque se informó de un 90% de efectividad para Construe, [Sebastiani et al.] advierte que no hay otros sistemas probados con igual conjunto de datos, y no se sabe si fueron tomados aleatoriamente o escogidos.

Las Máquinas de Aprendizaje han sido las dominantes desde la década de 1990 en adelante. Acá, se construye un clasificador por un proceso inductivo que corre sobre documentos ya clasificados manualmente, de los que se deducen las características relevantes. Es un proceso de aprendizaje supervisado.

Las ventajas de Máquinas de Aprendizaje sobre Conocimiento Ingenieril, son claras: ahorro de esfuerzo en construir el clasificador; lo que permite ahorro en la actualización de categorías o si el clasificador se porta a otro ambiente.

Para el uso de Máquinas de Aprendizaje, la clave son los documentos ya clasificados: es más fácil clasificar un conjunto de documentos que construir y afinar un conjunto de reglas de clasificación.

Aplicaciones de la categorización de textos

2005-09-16T12:04:00.000-04:00

La verdad es que la aplicabilidad de la Categorización de Textos es mucha. Aunque es difícil encontrarla en forma pura. La mayor parte de las veces se confunde o mezcla con otras como recuperación de textos o reconocimiento del habla.
[Sebastiani, 2002] habla de que los primeros trabajos se remontan al año 1961 con las investigaciones de Maron, y hace un resumen de las principales aplicaciones, las que se resumen a continuación:

Indexación automática para sistemas booleanos de recuperación de información

Los sistemas de Recuperación de la Información (Information Retrieval - IR) es el conjunto de sistemas encargados de revisar documentos y generar índices a partir de su contenido, normalmente, para facilitar la posterior navegación. Buscadores como Google, Yahoo, Altavista, entre otros; son ejemplos de sistemas que utilizan, entre otros, IR.

La Categorización de Textos en esta aplicación está basada en un conjunto controlado de términos y frases claves, llamado diccionario. Es lo más común en el ambiente de la categorización de textos y pretende asignar a cada documento palabras o frases que lo describen.

El diccionario es normalmente creado por un humano, lo que hace que esta aplicación sea cara.

Este vocabulario controlado son las categorías, y la indexación del texto es la aplicación de Categorización de Textos.

Para esta aplicación, probablemente usar el pivote en el documento sea la mejor opción.

Organización de Documentos

La aplicación anterior es un caso particular de esta, donde para la organización de documentos, las categorías son propias de la persona u organización que ordena los documentos.

Filtrado de Textos

El filtrado de textos es la actividad de, dado un flujo de documentos entrantes por vía asincrónica de un productor a un consumidor de información, por ejemplo un emisor de noticias, clasificarlos por intereses del lector.

Este es un caso de etiquetado simple, aunque adicionalmente podría realizar clasificación dentro de las categorías de interés.

Funcionan en el productor, por ejemplo, podría servir para despachar sólo las noticias que son de interés del usuario basado en un perfil para cada uno.

El perfil puede crearse inicialmente por el usuario y actualizarse con la clasificación que éste haga de lo recibido, lo que es conocido como adaptative filtering.

Cuando no hay un perfil inicial dado por el usuario, se llama routing si se le asigna una clasificación de interés; o batch filtering, si sólo se acepta o rechaza.

Des ambigüedad del sentido de la palabra

Dada la ocurrencia de una palabra ambigua en un texto, se trata de encontrar su sentido.

Es importante para procesamiento de lenguaje natural e indexación de documentos por sentido (no por Information Retrieval).

Es una aplicación de etiquetado simple y es usual que tenga pivote en el documento.

Ejemplos interesantes de uso, y que están contenidos dentro de los problemas de lingüística computacional; son la corrección ortográfica sensible al contexto, las sugerencias de redacción y la selección de palabras en las traducciones.

Categorización Jerárquica de páginas Web

El objetivo de esta categorización es facilitar la navegación por la Web al agrupar, por categorías jerárquicas, en los motores de búsqueda.

Hacerlo en forma automática tiene la obvia ventaja de la movilidad de las categorías.

Sus peculariedades son:
- La naturaleza hiper textual de los documentos, por lo que la clasificación varía respecto de lo interesante de las páginas referenciadas.
- La estructura jerárquica del conjunto de categorías, usado para descomponer la clasificación en problemas de clasificación más pequeños.

El problema del vocabulario y su ambigüedad

2005-09-15T13:29:00.000-04:00

El problema del vocabulario y la ambigüedad, dentro de la categorización de textos, requiere especial atención.

Se ha observado que las personas, sobre todo cuando se refieren a objetos que no están dentro de su ámbito de trabajo habitual, para referirse a un mismo objeto, usan una gran cantidad de términos distintos.

[Furnas, Landauer, Gomez, Dumais, 1999] acotan que si las personas llamaran las cosas de igual manera, esas palabras se podrían usar por los diseñadores para crear los sistemas. Se refieren a esto en el contexto del problema de los comandos de acceso (command naming) utilizado para obtener información de bibliotecas o realizar consultas a bases de datos.

[Furnas et al.] nos indican que si estas palabras, si son bien escogidas, puden cubrir buena parte de las alternativas que usan los usuarios. Para ello, se basan en simulaciones y experimentación directa de varias alternativas con índices ampliados probabilísticamente o listas de alias aumentan el éxito en un factor de 3 a 5.

En Categorización de Textos ocurre algo similar en el sentido que los documentos son escritos por personas; personas que usan multitud de términos para referirse a lo mismo... o igualmente complicado, usan el mismo término para referirse a cosas absolutamente diferentes.

En específico, el problema de los sinónimos (palabras que tienen igual significado, pero se escriben de forma distinta), quasi-sinonimia (sin ser exactamente sinónimos, bajo ciertas circunstancias describen lo mismo, por ejemplo: comunicado, declaración), antónimos (palabras que tienen significados contrarios) y homónimos (palabras que se escriben igual pero tienen significados distintos), polisemia (palabras con más de un significado, por ejemplo: bomba) y los lemas (raíz común a las palabras, por ejemplo: descubrir, descubrimiento); pueden resultar, más que un problema, una forma de mejorar la clasificación de los textos con la aplicación de índices o listas de alias, probablemente asociados a una probabilidad de pertenencia a la categoría.

Categorización Dura y Graduada

2005-09-12T23:23:00.000-04:00

Cuando se relaciona una categoría con un documento, lo normal es pensar en que el documento pertenece o no a una determinada categoría en términos absolutos (o visceversa), vale decir, se toma una decisión booleana respecto a la pertenencia de uno respecto del otro. A este tipo de categorizarción se le denomina normalmente Categorización Dura.

Pero no siempre es fácil decidir si entre documento y categoría existe relación. Cuando la decisión se toma basándose en una probabilidad de pertenencia, se habla de una categorización graduada.

La categorización graduada es especialmente útil cuando se trata de aplicaciones críticas, donde los documentos o las categorías, si hablamos de categorización con pivote en la categoría o el documento respectivamente; se ordenan de acuerdo a la probabilidad de pertenencia a la categoría, y posteriormente se deja la decisión final de la asignación a otra instancia, normalmente un humano. También se recure a este tipo de clasificación cuando el clasificador obtenido no es suficientemente bueno.

Sus aplicaciones, por ejemplo en la navegación de documento, son evidentes al permitir revisar aquellos documentos o categorías con más probabilidades de coincidencia con los requerimientos.

En la literatura se trata esta categorización como Document Ranking y Category Ranking.

Categorización con pivote en el documento o en la categoría

2005-09-12T23:00:00.000-04:00

Otro aspecto relevante a la hora de estudiar una solución de Categorización de Textos es "el pivote". Esto se refiere al objeto donde fijaremos nuestra atención para determinar la relación entre documentos y categorías.

Se distingue con pivote en el documento (DPC – Document Pivoted Categorization) como aquella categorización que pretende encontrar todas las categorías a las que pertenece un documento.

Como contrapartida, se distingue con pivote en la categoría (CPC – Category Pivoted Categorization) como aquella que pretende encontrar todos los documentos que pertenecen a determinada categoría.

La diferencia, que parece más de forma que de fondo, no es tal; y es importante si el conjunto de las categorías (C) o el de los documentos (D), no están completamente disponibles desde el principio. También es importante para escoger el método de construcción del clasificador.

La clasificación con pivote en el documento se suele recomendar cuando los documentos están disponibles en distintos momentos, como los correos electrónicos; y es la clasificación más común.

La clasificación con pivote en la categoría, en cambio, suele recomendarse cuando una nueva categoría puede ser agregada luego que existen documentos ya clasificados; o cuando estos documentos necesitan ser reclasificados con |C|+1 categorías.

Etiquetado simple, múltiple y binario

2005-09-08T23:10:00.000-04:00

Categorizar textos es "como asignarle etiquetas" al documento. Así, un documento en particular se puede relacionar con una o más categorías.

Cuando el proceso de categorización asigna al documento una sola categoría, se denomina etiquetado simple; y se habla de categorías no superpuestas.

Si por el contrario, el proceso de categorización admite asignar más de una categoría (o ninguna) al documento, se denomina etiquetado múltiple, y se habla de categorías superpuestas.

Cuando el proceso de categorización es simple, y además para cada categoría se decide si pertenece o no el documento (decisión booleana), se habla de etiquetado binario y es un caso muy importante de etiquetado dado que es más general que el etiquetado múltiple; de hecho, cualquier problema de etiquetado múltiple puede convertirse en binario, pero no visceversa. Esto porque si se asigna más de una categoría, habría que decidir cual es la más apropiada; o bien, si no se asigna ninguna categoría, se debiera decidir cual es la "menos inapropiada".

Es requisito de la categorización binaria que las categorías sean estocásticamente independientes, vale decir, la pertenencia del documento documento a determinada categoría no esté determinada por la pertenencia a otra.

La clasificación binaria es importante de estudiar, además, porque la mayor parte de las aplicaciones reales son binarias, dado que:

- las categorías son desigualmente pobladas,

- algunas categorías son más fáciles de caracterizar,

- resolviendo el problema binario se resuelve el problema multietiquetado

- y la literatura está más orientada al problema binario.

Caso claro es el filtrado de documentos.

Un clasificador binario, en lo formal, se puede definir como una función T -> {D,C}, donde T(di, ci) = {0,1}, donde 0 representa que no pertenece a la categoría y 1 que sí pertenece.

No tan nuevo

2005-09-08T22:30:00.000-04:00

La categorización de textos empezó hace ya muchos años. Ya en los años 1960 se empezaron a dar los primeros pasos en esta área.

Conocimiento Ingenieril
Por ese entonces, la forma de abordar la categorización de textos se basaba en conjuntos de reglas. Ahora conocemos eso como Conocimiento Ingenieril (o Knowledge Engenieering - KE); es una de las dos ramas que aún se explota.
Las reglas eran instrucciones condicionales, del tipo Si Entonces . En estos momentos aún se pueden encontrar software de este tipo, aunque algo más refinado, como es el caso de Spamassassin, que basa su descubrimiento de correo no deseado (spam) en una serie de condicionales como si es un correo HTML, si el remitente tiene números en su composición, si existe el dominio de origen, si contiene palabras clave, entre otras. A cada una de ellas le da una ponderación, y si pasa un determinado umbral, es declarado spam.

La idea, si lo pensamos, es bastante lógica; pero tiene una serie de inconvenientes.
El primero de ellos se refiere a la construcción de las condiciones. Para ello se requiere primero de un experto en el área de investigación. Así, por ejemplo, en el caso de Spamassassin, que se analizaba, son muchos los individuos que voluntariamente han aportado con su experiencia para la confección de las reglas. Pero el caso de este software no es la generalidad. En la mayor parte de las áreas de investigación, encontrar expertos en el dominio de la aplicación es difícil, y muchas veces convencerlos de que entreguen lo que consideran su know how es aún más difícil.
Un segundo inconveniente viene dado por la conformación de los equipos, no sólo se requiere del experto que entregue las reglas, sino que también requiere de quien interprete esas reglas y construya el clasificador en un lenguaje computacional, aunque por estos días esto podría ser algo más fácil.
El tercer inconveniente tiene que ver con la portabilidad de la solución. Como estos categorizadores son construidos para una problemática en particular, cambiarlos de dominio de aplicación puede llegar a ser imposible. Resulta más fácil reconstruir completamente la solución.
Una situación similar ocurre si una nueva categoría es incorporada. Normalmente el clasificador se debe reconstruir y los documentos reprocesados.
Por último, está el caso de la parametrización fina o tunning, la que también debe ser realizada por alguien con conocimientos del área. Por ejemplo, en el caso de Spamassassin, el puntaje que aporta cada regla a la evaluación final del correo, así como el umbral por sobre el cual este correo es considerado spam, son motivos de ajuste a la realidad de cada usuario. Las versiones recientemente revisadas, ajustan estos parámetros en forma dinámica indicándole a la aplicación si un determinado correo es o no indeseado, por lo que la misma aplicación modifica los umbrales basados en esta experiencia.
Pese a estos inconvenientes, no se puede descartar el construir en estos momentos un clasificador del tipo Conocimiento Ingenieril por que se ha observado la alta efectividad de estos una vez ajustados. En experimentos realizados, Reuter ha anunciado que su clasificador Construe, que tiene muchos años afinando sus reglas y parámetros, dice haber conseguido una efectividad que supera el 90%!!! [Sebastiani, 2002], pero no hay evidencia de cómo se hicieron estas mediciones, cómo se escogieron los ejemplos de entrenamiento y prueba, ni hay otros experimentos realizados con la misma fuente de datos [Sebastiani et al.].
No obstante esto, quienes, al igual que yo, utilizan Spamassassin, pueden dar fe de la alta efectividad de este analizador de correos.

Máquinas de Aprendizaje
La otra modalidad de Categorización de Textos son las máquinas de aprendizaje. Vienen haciendose populares desde la década de 1980, y por estos días son, sin lugar a duda, lo más estudiado.
En esta modalidad, ya no hay expertos que dicten reglas, sino más bien, hay un módulo que va aprendiendo de manera inductiva a partir de ejemplos preclasificados, cuando un documento de texto pertenece a determinada categoría. Es un ejemplo de aprendizaje supervisado.
Para hacer este estudio, se basa en la información intrínseca del documento, despreciando información externa como su origen, autor, formato, etc. Sebastiani et al. nos explica que esa información debiera considerarse, puesto que la información exógena aporta importante información respecto de la categoría a la cual debiera ser asignado y le da al clasificador aún más objetividad.
Una ventaja que aún no ha sido nombrada, sin duda muy importante, es que es más fácil clasificar documentos que construir y afinar reglas de clasificación; por lo que en general resulta más rápido construir y poner en funcionamiento clasificadores basados en Máquinas de Aprendizaje que en Conocimiento Ingenieril.
Hay registros, que se conversarán más adelante, respecto de la efectividad de estos clasificadores; los que se asemejan mucho a la efectividad alcanzada por clasificadores humanos.
Ejemplos de este tipo de clasificadores son Hermes y Poesía. El primero es un despachador de noticias y el segundo un supervisor de contenido accedido en Internet. Información sobre estos sistemas se puede encontrar en [Gomez, Puertas, de Buenaga, Carrero, 2002] y [Gomez, Giraldez, de Buenaga, 2004]

Porqué estudiar Categorización de Textos

2005-09-05T11:12:00.000-04:00

La categorización es una motivación natural en el ser humano. Basta ver los niños pequeños como definen lo que los redea a partir de la categorización, ya sea por colores texturas, etc.
Es de especial interés en la comunidad científica el poder caracterizar textos (Text Categorization Text Classification) por la cantidad de aplicaciones prácticas que se pueden encontrar, sin contar aquellas que están en plena investigación.

Quizás la más evidente es la organización de documentos en bibliotecas digitales, pero hay muchas otras aplicaciones. Entre las más destacables, IMHO, está el control de spam.

En estos momentos, aplicaciones como Spamassassin o McAffe WebShield Appliance controlan el spam (la última, tiene el inconveniente que sólo analiza el protocolo POP) basado en una serie de reglas, más o menos como lo hacían las primeras aplicaciones de categorización (Knowledge Engeneering); tema que se tratará más adelante; por lo que ahí hay mucho para hacer.

Hay otras aplicaciones, quizás no tan evidentes, como el controlar el acceso a Internet en las empresas para que los empleados no pierdan tiempo y recursos de la empresa en actividades que no contribuyen; o el control parental, para que los niños no accedan a páginas con violencia, pornografía u otras que no sean apropiadas, están ganando fuerza.

Como se ve, hay aplicaciones que justifican con creces la investigación en categorización de textos; pero hay una que no se puede dejar de lado y que se puede considerar como de las más importantes: la búsqueda de información.

El investigador pierde mucho tiempo buscando información. En la mayor parte de los buscadores, la información está indexada por palabras claves, por lo que la búsqueda se limita a mostrar un listado con aquellos links en los que se han encontrado estas palabras claves. Muchas veces es de ayuda la presentación ordenada por indicadores de cercanía, indicada en un pocentaje, o por cuan visitadas han sido esas páginas; pero no es suficiente. Se sabe de la existencia de trabajos para guiar las búsquedas mostrando enlaces a documentos relacionados.

Qué es categorizar textos???

2005-09-01T17:25:00.000-04:00

Definiremos en primer lugar lo que es un texto, como un documento que está compuesto de palabras.

Esta última definición es bastante importante dado que en este momento existen esfuerzos por categorizar documentos en general, sean estos videos, audios, imágenes, etc.; los que han tenido un éxito relativo por distintos problemas, pero básicamente por el problema de la representación: una pintura, por ejemplo, significará y tendrá una interpretación distinta dependiendo de quien la observe.

En el caso de los textos, si bien la problemática anterior también se puede dar, esta está más acotada por que las palabras cuentan con una definición establecida y común para todos.

Además, definiremos categorizar como distinguir las características propias de un objeto y que lo hacen distinto de otros objetos.

Definiremos pues, categorización de textos como relacionar un texto con categorías

En términos formales, existe una función T definida en (DxC) tal que T(di)=ci; donde D es el conjunto de los documentos disponibles, C es el conjunto de categorías disponibles, di es un documento cualquiera y ci es el vector de las categorías a las que pertenece el documento di.

El proceso de categorización de textos, lo que pretende es encontrar una función T' que se parezca lo más posible a la función T ya definida. Tal definición y coincidencia se llama efectividad

La categorización de textos se dice es parte de Recuperación de Información (Information Retrieval), y se preocupa de etiquetar, vale decir, asignar etiquetas que indican a qué categoría o categorías corresponde el documento. Aunque también encontrará que hay autores que clasifican la categorización de texto como un cruce entre Máquinas de Aaprendizaje (Machine Learning - ML) y Recuperación de la Información (Information Retrieval - IR). Más aún, hay quienes se refieren a esta área de estudio como una instancia de la Minería de Textos (Text Mining - TM) [Hernandez, 2005].

Con Recuperación de Información guarda bastante semejanza, de hecho, hay varias técnicas que es utilizan en IR que también son utilizadas en TC. Éstas técnicas son usadas en las tres fases del ciclo de vida del clasificador:

- Indexación al estilo Recuperación de la Información, para poder clasificar en la fase de operación.

- Técnicas al estilo Recuperación de la Información usado en la construcción inductiva del clasificador.

- Evaluación al estilo Recuperación de la Información, para medir la efectividad alcanzada por el clasificador.

Si parece que el concepto aún no está claro para los investigadores, [Sebastiani, 2002] relata que la expresión “Categorización Automática de Documentos” (ATC – Automatic Text Categorization), en la literatura aparece como:

- Asignación automática de documentos a conjuntos pre definidos de categorías.

- Identificación o descubrimiento automático de categorías.

- Identificación de las categorías y agrupamiento de los documentos bajo ellas; también llamado Agrupamiento de Textos (Text Clustering)

- Cualquier actividad de colocar items de texto en grupos, por lo que Categorización de Textos y Agrupamiento de Textos pasarían a ser sólo casos de Categorización Automática de Textos.

Inauguracion...

2005-08-31T16:20:00.000-04:00

Básicamente he construido este lugar para mantener lo que vaya recopilando hacerca de Categorización de Textos y uno que otro pensamiento que se me vaya ocurriendo en el camino. Si hay algo con lo que quieras aportar, es bienvenido, siempre y cuando mantengamos el clima de respeto y cooperación que exige la buena convivencia.