Máquinas de aprendizaje y Conocimiento Ingenieril

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.

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

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

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

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

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

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

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

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???

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.