VISITAS:

lunes, 31 de octubre de 2011

Tokenización (4)

Nos vamos a centrar en los aspectos técnicos que surgen en una de las etapas de la segmentación de un texto: la tokenización.
Los lenguajes creados artificialmente, como por ejemplo, los lenguajes de programación, se definen de forma muy estricta para eliminar las ambigüedades tanto léxicas como estructurales. Esto no ocurre en los lenguajes naturales, en los cuales, un mismo carácter puede servir para propósitos diferentes y en los cuales la sintaxis no se define estrictamente.
Para el caso de la tokenización, podemos distinguir entre lenguajes delimitados por espacios (y otros signos de puntuación perfectamente definidos) y lenguajes no segmentados.
En los lenguajes delimitados por espacios, el carácter espacio hace de separador entre palabras, aunque también se definen otros caracteres separadores de palabras, como los símbolos de puntuación, el tabulador, el salto de línea, etc.
En los lenguajes no segmentados las palabras se escriben una a continuación de otras sin indicación explícita de los límites de las palabras. La tokenización en estos lenguajes requiere información léxica y morfológica adicional.
En cualquiera de estos tipos de lenguajes existen tres categorías para la estructura de las palabras:
  • palabras aisladas, donde una palabra no se divide en otras unidades
  • palabras aglutinantes, donde una palabra se divide en otras unidades más pequeñas llamadas morfemas delimitadas claramente
  • palabras inflexivas, donde una palabra se divide en otras unidades más pequeñas que no están claramente determinadas
Los distintos idiomas pueden mostrar una clara tendencia hacia una de estas categorías: Por ejemplo, el chino es predominantemente aislado, el japonés es aglutinativo y el latín es inflexivo. Pero la mayoría de los idiomas exhiben las tres categorías.
Tokenización en lenguajes delimitados por espacios
Aunque en estas lenguas la tokenización es más sencilla, existen muchos asuntos que resolver. La mayoría de estas ambigüedades vienen de los signos de puntuación, donde el mismo signo puede servir para diferentes funciones. Por ejemplo, el punto puede servir para separar decimales en un número, para marcar el final de una abreviatura o para finalizar una frase. Incluso, en una abreviatura al final de una sentencia, el punto hace de fin de abreviatura y de fin de sentencia. El tokenizador (dependiente del idioma) tiene que ser capaz de determinar cuándo un punto es parte de un token y cuando separa dos tokens. Para ello, el tokenizador tiene que ser capaz de reconocer abreviaturas.
Otra situación que debe tratar el tokenizador es: $40 y 40 dólares. Ambas deberían formar el mismo único token: 40-dólares.
Las comillas dobles y simples son otro caso de ambigüedad en la tokenización. En muchos casos, las comillas indican un texto entrecomillado y lo único que hay que resolver es si se abren o se cierran las comillas. Pero a veces, también se utilizan las comillas en inglés por ejemplo para doesn't, I'm, you're, etc. En estos casos, la tokenización está ligada al análisis sintáctico. Además, en estos casos de comillas como contracción de dos palabras, la tokenización tiene que expandir las palabras eliminando el apóstrofe (I'm ---> I am). Pero siempre, dependiente del idioma.
En algunos idiomas, como el español, existen contracciones de palabras que no utilizan comillas, como por ejemplo "del", que es la contracción de "de el", y que deben expandirse en los dos tokens componentes.
Otro caso es el guión, que se suele utilizar para unir varias palabras en un token: end-of-line, o para unir varios tokens: language-dependent. Además, el guión se usa a veces para partir una palabra en dos líneas. Estos guiones hay que eliminarlos durante la tokenización, y la dificultad aquí estriba en distinguir estos casos de los guiones utilizados para unir tokens.
Las palabras múltiples son casos de varias palabras que siempre van juntas y que expresan un único significado. Por ejemplo, en inglés "in spite of" es equivalente a "despite" y ambos deberían ser tratados como un único token. Otros caso es "de facto".
Existen también las expresiones numéricas, fechas, horas, moneda, porcentajes, etc que deben ser tratados como un único token.
Tokenización en lenguajes no segmentados
Ejemplos de estos lenguajes son el chino y el japonés.
El tratamiento en estos casos es totalmente dependiente del idioma y no vamos a tratarlo aquí.
En general, la solución siempre se basa en reconocer las palabras a través de un diccionario.



viernes, 28 de octubre de 2011

Desafíos en el pre-procesado del texto (3)

El preprocesado de texto consiste en obtener un corpus de documentos de texto en uno o más idiomas y tokenizar dichos textos (caracteres, palabras y sentencias).
Tipos de sistemas de escritura
Los sistemas escritos pueden ser logográficos, silábicos o alfabéticos.
Los sistemas logográficos utilizan un símbolo para representar cada palabra.
Los sistemas silábicos utilizan un símbolo para representar cada sílaba.
Los sistemas alfabéticos utilizan un símbolo para cada sonido.
Los idiomas modernos suelen ser una mezcla de estos tipos de escritura. Por ejemplo, el español utiliza símbolos logográficos como los números (0-9), moneda (€) y otros símbolos (%), aunque se trata de un idioma fundamentalmente alfabético (a-z),
Juegos de caracteres
Hace unos años, interpretar un fichero de texto era algo trivial, ya que todos los textos estaban codificados según el conjunto de caracteres ASCII de 7 bits (128 caracteres) que incluye únicamente el alfabeto latino (caracteres esenciales en el inglés escrito). El problema con este juego de caracteres es que no incluye por ejemplo las tildes. Así que en español había que codificar por ejemplo una é como 'e. En idiomas como el ruso, el árabe o el chino la situación era todavía más complicada.
Con la aparición de los juegos de caracteres de 8 bits (256 caracteres) se ampliaron las posibilidades. No es un juego de caracteres único, sino varios, para los distintos alfabetos y para algunos sistemas silábicos. Por ejemplo, la serie ISO-8859 son más de 10 juegos de caracteres que contienen definiciones para la mayoría de las lenguas europeas (incluyendo el griego). El problema es que como sólo se dispone de 256 posibles caracteres, los distintos juegos de caracteres de 8 bits se solapan. Además, lenguas como el chino o el japonés tienen más de 256 caracteres distintos y no se pueden codificar con 8 bits.
Aparecen después los juegos de caracteres de 16 bits que pueden representar hasta 65.536 caracteres distintos. Pero hay que agrupar cada carácter en 2 bytes, lo cual puede dificultar el procesado de ficheros de texto que incluyan caracteres de varias lenguas, algunos utilizando 8 bits y otros utilizando 16 bits.
El estándar Unicode elimina muchos de estos problemas, especificando un juego de caracteres universal que incluye más de 100.000 caracteres distintos procedentes de más de 75 lenguas diferentes (que abarcan la gran mayoría de los sistemas escritos en uso hoy día). Unicode se suele implementar con la codificación UTF-8 de longitud variable (aunque pueden existir otras implementaciones de Unicode), en el cual, cada carácter se representa por un número variable de bytes, de 1 a 4. En UTF-8 los 128 caracteres ASCII se codifican con 1 byte (con lo cual los textos ASCII no necesitan ser modificados para Unicode), la mayoría de los caracteres incluidos en ISO-8859 (1920 caracteres) necesitan 2 bytes, y todos los demás caracteres (incluidos el japonés,el chino o el coreanos) necesitan 3 bytes y muy raramente 4 bytes (se utilizan 4 bytes para símbolos matemáticos por ejemplo). El estándar Unicode y su implementación UTF-8 permite codificar todos los caracteres sin solapes.
UTF-8 garantiza el principio de no superposición, es decir, según el comienzo de cada byte, se puede saber a qué carácter pertenece:
  • Caracteres representados con un byte: 0xxxxxxx
  • Caracteres representados con dos bytes: 110xxxxx 10xxxxxx
  • Caracteres representados con tres bytes: 1110xxxx 10xxxxxx 10xxxxxx
  • Caracteres representados con cuatro bytes: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Nota: El ocho de UTF-8 no implica codificación con 8 bits.

Identificación de la codificación y su impacto en la tokenización
A pesar del creciente uso de Unicode, existen muchos documentos de texto codificados en ISO-8859 y sus diferentes juegos de caracteres. De esta forma, el separador de sentencias por ejemplo, cambia según la codificación que se esté usando. Por ejemplo, textos en español e inglés se suelen codificar utilizando ISO-8859-1 (Latin 1) con 8 bits; el carácter © corresponde con el valor 169 en Latin 1; si intentamos interpretar este valor como UTF-8 nos encontramos con que no tiene nada que ver.
La tokenización por tanto, está ligada a un idioma concreto y a una codificación específica.
Normalmente, la cabecera de un documento de texto contiene información sobre la codificación de caracteres que se utiliza, pero esto no siempre es así y en algunos casos habrá que detectar la codificación automáticamente.
Un algoritmo de detección de codificación de caracteres debe conocer los distintos sistemas de codificación para saber que rangos de bytes tiene que buscar los caracteres válidos, así como qué rangos de bytes serán improbables esa codificación. El algoritmo analiza entonces los bytes del fichero y compara los bytes encontrados con los rangos esperados en codificaciones conocidads, decidiendo así la codificación que mejor se adapta a los datos.
Por ejemplo, el ISO-8859-5 (utilizado para caracteres rusos) codifica las letras mayúsculas en el rango 0xB0-0xCF y las letras minúsculas en el rango 0xD0-0xEF. Sin embargo, el juego KOI8-R (también utilizado para codificar los caracteres rusos) codifica las mayúsculas en el rango 0xE0-0xEF y las minúsculas en el rango 0xC0-0xDF. En Unicode, los caracteres rusos necesitan 2 bytes, con las letras mayúsculas en el rango 0x0410-0x042F, y las letras minúsculas en el rango 0x0430-0x045F. Un algoritmo de detección de codificación de caracteres para el idioma ruso debería examinar los bytes que tiene el fichero para determinar en qué rango aparecen la mayoría de los caracteres. Por ejemplo, el byte 0x04 es un carácter de control extraño en ISO-8859-5 y KOI8-R, pero debería ser más de un 50% de las ocurrencias en un fichero Unicode ruso. Igualmente, un fichero ISO-8859-5 debería contener muchos bytes en el rango 0xB0-0xBF, pero pocos en el rango 0xF0-0xFF, mientras que un fichero en KOI8-R debería contener pocos bytes en el rango 0xB0-0xBF y muchos bytes en el rango 0xF0-0xFF. A partir de la distribución de los bytes que tiene el fichero es posible determinar la codificación de caracteres para textos en ruso.
Sin embargo, debido a que existe un solape entre los juegos de caracteres existentes, puede haber situaciones en que es imposible detectar la codificación. Por ejemplo, la mayoría de los juegos de caracteres reservan los primeros 128 caracteres para los caracteres ASCII, y si un documento contiene sólo esos primeros 128 caracteres, entonces no se puede determinar si se trata de uno de los juegos ISO-8859 o incluso UTF-8.
Dependencia del idioma
Además de la variedad en los tipos de símbolos utilizados en los sistemas escritos, existen muchas convenciones ortográficas para marcar los límites entre las unidades lingüísticas tales como sílabas, palabras o sentencias. Por ejemplo, en idiomas como el español se utilizan unos determinados signos de puntuación para separar sentencias y el espacio y otros signos de puntuación para separar palabras. Sin embargo, en otros idiomas, la separación entre palabras no está tan claramente definida e incluso no hay separadores de sentencias.
Detección del idioma
Para realizar correctamente la segmentación del texto es necesario aplicar las características especiales de cada idioma. Por eso, un paso muy importante en las primeras etapas es la identificación del idioma de un texto o una sección de un texto (ya que un documento podría ser multi-idioma),
En lenguas que utilizan un alfabeto único, como el griego o el hebreo, el idioma se determina directamente a partir de la identificación de la codificación de caracteres. En otros casos, la codificación puede utilizarse para determinar un conjunto pequeño de idiomas posibles de un documento (idiomas que comparten el mismo juego de caracteres). Además, la distribución de los bytes utilizada para detectar la codificación puede aprovecharse para identificar caracteres que son predominantes en alguno de los idiomas posibles. Esto es relativamente sencillo en idiomas que utilizan el mismo juego de caracteres, como el sueco y el noruego, pero que no utilizan exactamente los mismos caracteres. En el caso de usar el mismo juego y los mismos caracteres, como en el caso de la mayoría de las lenguas europeas, se pueden utilizar las frecuencias de los caracteres (cada idioma utiliza los caracteres con unas frecuencias distintas), entrenando el sistema con las distribuciones de frecuencias de los caracteres en los distintos idiomas.
Ahora surge el problema cuando no conocemos ni la codificación de caracteres ni el idioma del texto ¿Qué hacemos entonces? Pues ahora mismo no tengo respuesta clara a este problema. Espero resolverlo en el futuro y lo escribiré en este blog.
Dependencia del corpus
No todos los corpus de documentos contienen textos gramaticalmente y ortográficamente perfectos (como sería el caso de documentos literarios o periodísticos). En algunos casos tenemos e-mails, foros, blogs, etc, donde son frecuentes las palabras mal escritas, utilización aleatoria de símbolos y caracteres de puntuación, utilización variopinta de los espacios, etc, etc. Esto afecta principalmente a la tokenización y a la detección de sentencias.
Por lo tanto, la mayoría de los algoritmos de segmentación utilizados en NLP son dependientes del idioma y dependientes del corpus.

Pre-procesado del texto (2)

Los lenguajes naturales presentan muchas ambigüedades. Gran parte del procesamiento del lenguaje natural (NLP) consiste en resolver estas ambigüedades.
La primera etapa en todo sistema NLP es el preprocesamiento del texto a partir de la información de entrada, la cual básicamente será una secuencia de bits.
Para procesar un texto, es necesario en primer lugar definir claramente los caracteres, las palabras y las sentencias. Dependiendo del idioma, esta tarea puede ser más o menos sencilla.
Los caracteres son la unidad mínima del lenguaje escrito, las palabras constan de uno o más caracteres, y las sentencias constan de una o más palabras.
El pre-procesado del texto se divide en dos etapas:
  • Conseguir un documento de texto
  • Segmentación del texto
Obtener un documento de texto
Este proceso puede suponer varios pasos, dependiendo del documento original.
En primer lugar, para que el documento pueda almacenarse como texto, sus caracteres tienen que representarse con una codificación. Segundo, hay que identificar el idioma del documento, para determinar los algoritmos específicos de un idioma (este proceso puede estar relacionado a la codificación de los caracteres). En tercer lugar, hay que seccionar el texto, es decir, identificar el contenido textual quitando lo que no es texto, como imágenes, links, tablas, etc.
La salida de esta etapa es un corpus de documentos de texto, organizados por idioma.

Segmentar el texto
Este proceso convierte un corpus de textos en sus componentes: palabras y sentencias.
La segmentación en palabras despieza la secuencia de caracteres de un texto localizando los límites entre palabras, o sea, los puntos donde termina una palabra y comienza la siguiente.
Las palabras así identificadas se denominan tokens y al proceso de segmentar palabras se le denomina tokenización. Después de conseguir los tokens, hay que normalizar, que consiste en convertir las diversas formas de escribir un token en una forma canónica. Por ejemplo, los tokens "Sr" "señor" y "Señor" son equivalentes y tienen que normalizarse a una forma única.
La segmentación en sentencias detecta los límites entre sentencias, o sea, la última palabra de una sentencia y la primera palabra de la siguiente sentencia. Este proceso suele consistir en detectar unos determinados signos de puntuación como ".", ":", "!", "?", dependiendo del idioma.
En la práctica, la segmentación de palabras y sentencias no se pueden ejecutar como dos procesos independientes. Por ejemplo, las abreviaturas en muchos idiomas terminan en "." al igual que el final de una sentencia. Si por ejemplo, una abreviatura coincide con el final de una sentencia, entonces el "." marca tanto el final de la abreviatura como el final de la sentencia.


jueves, 27 de octubre de 2011

Etapas clásicas en el procesamiento de un texto (1)

Volvemos a retomar el tema del procesamiento del lenguaje natural.
Desde el texto plano hasta el significado del mismo, se pasa por una serie de etapas:
  • Análisis sintáctico
  • Tokenización
  • Léxico
  • Sintaxis
  • Análisis semántico
  • Análisis pragmático
Las primeras etapas realizan un análisis que proporciona un orden y una estructura que es tratable por un sistema informático. En el análisis semántico se analiza el significado literal de cada término. Y en la última etapa se considera el contexto para ajustar el significado total de cada sentencia.
La etapa de tokenización consiste en obtener los caracteres, las palabras y las sentencias. Esta etapa puede llegar a ser muy compleja en lenguas como el alemán o el chino, donde el espacio no delimita todos los tokens. El análisis léxico etiqueta cada token con su morfología (persona, género, número, tiempo, etc). El análisis sintáctico etiqueta la función de cada palabra dentro de la sentencia.
Las etapas de tokenización, léxico y sintaxis están muy estudiadas y se han conseguido resultados muy buenos. Sin embargo las otras dos etapas son muy complejas para un sistema automático.
Es importante señalar que en la práctica (o sea, en los sistemas que procesan el lenguaje natural), estas etapas no están completamente separadas, sino que comparten funciones. Por ejemplo, la tokenización en idiomas como el alemán podría depender de otros análisis posteriores para poder realizarse correctamente. Pero en cualquier caso, pedagógicamente estas son las etapas por las que hay que pasar para analizar el lenguaje natural.
Iremos viendo estas distintas etapas en profundidad más adelante.