La modificación del prototipo es completa y apenas ocupa memoria ram en comparación con la anterior implementación. Por desgracia no todo van a ser buenas noticias...
Actualmente mi portatil sigue indexando 10 documentos del clef (unos 1300 documentos en total) y lleva 10 horas... (estimo que tardará 2 o 3 más). Llevo muchos días intentando optimizar cada fragmento de código y no he conseguido tiempos de ejecución razonables hasta ahora. En el último modelo tuve que aplicar una modificación "mia" para limar un poco el tiempo de ejecución y el algoritmo simplemente no tiene en cuenta ninguna coocurrencia que se de con una probabilidad menor de 0.05
El problema que tengo es que utilizo TODOS los terminos del índice como nuevo espacio vectorial por lo que la matriz de ocurrencias tiene que almacenar relaciones entre muchísimos términos. Esto puede arreglarse utilizando SVD posteriormente o solo almacenando relaciones entre ciertas palabras (nombres, verbos, ...) o entre ciertas partes de la frase (con análisis sintactico).
En varios artículos de DS se habla incluso de decidir "a mano" los términos conceptuales (en torno a 1000) lo cual en el caso de adoptarse en mi prototipo daría unos tiempos mucho más razonables.
La cuestión es que si en dos días más no consigo mejoras sustanciales me veré obligado a hacer algún cambio en la elección de los conceptos... El no haber avanzado apenas en 2 semanas me agobia...
PD: El SVD tiene otro problema añadido y es que si parto de la matriz de coocurrencias completa (para quitar el ruido) tendría que dar al algoritmo la matriz de 25000 x 25000 y, al menos la implementación de numpy no es capaz de procesarla sin utilizar muchísima memoria...
martes, 18 de noviembre de 2008
miércoles, 5 de noviembre de 2008
Prototipo V1.0
Hace mucho tiempo que no edito el blog pero no por ello he estado sin trabajar este mes. Llevo todo este tiempo trabajando en el diseño e implementación de mi primer prototipo en Python.
El prototipo es un sistema de recuperación de información que implementa un modelo básico de semántica distribuida. Está en pruebas y da unos resultados bastante buenos con la salvedad de que utiliza una cantidad desmesurada de memoria RAM y que las consultas son algo lentas (no así el indexado). Es un problema que estoy tratanto de arreglar actualmente y con el que estaré hasta la semana que viene cuando debería de dar por finalizado el primer prototipo.
El problema que tengo es que las pruebas las estoy realizando en mi ordenador y no se qué cantidad de datos podría utilizar para las pruebas. Actualmente utilizo de 1 a 15 documentos del clef lo cual pueden ser de 500 a 3000 documentos aproximadamente. Aún mejorando sustancialmente la necesidad de memoria no creo que pueda llegar a procesar los 300 documentos del clef del 95.
La semana que viene enviaré un mail a Dani para que definamos las pruebas para las comparaciones en un futuro.
Las tres siguientes iteraciones serán la posibilidad de un coeficiente de hibridación respecto del modelo vectorial, la incorporación del SVD (ya he realizado algunas pequeñas pruebas) para eliminar ruido en la matriz de coocurrencias y la aplicación de análisis sintactico para obtener solo las coocurrencias más relevantes.
El prototipo es un sistema de recuperación de información que implementa un modelo básico de semántica distribuida. Está en pruebas y da unos resultados bastante buenos con la salvedad de que utiliza una cantidad desmesurada de memoria RAM y que las consultas son algo lentas (no así el indexado). Es un problema que estoy tratanto de arreglar actualmente y con el que estaré hasta la semana que viene cuando debería de dar por finalizado el primer prototipo.
El problema que tengo es que las pruebas las estoy realizando en mi ordenador y no se qué cantidad de datos podría utilizar para las pruebas. Actualmente utilizo de 1 a 15 documentos del clef lo cual pueden ser de 500 a 3000 documentos aproximadamente. Aún mejorando sustancialmente la necesidad de memoria no creo que pueda llegar a procesar los 300 documentos del clef del 95.
La semana que viene enviaré un mail a Dani para que definamos las pruebas para las comparaciones en un futuro.
Las tres siguientes iteraciones serán la posibilidad de un coeficiente de hibridación respecto del modelo vectorial, la incorporación del SVD (ya he realizado algunas pequeñas pruebas) para eliminar ruido en la matriz de coocurrencias y la aplicación de análisis sintactico para obtener solo las coocurrencias más relevantes.
jueves, 9 de octubre de 2008
Semántica Distribuida
El modelo de recuperación de información basada en la semántica distribuida es un tipo específico de modelo vectorial en el cual se tiene en cuenta el contenido semántico de las unidades de información representando este significado mediante vectores multidimensionales.
Este tipo de vectores pueden hayarse a partir de la matriz de co-ocurrencias entre términos en la colección utilizada. A partir de la representación multidimensional de los documentos y peticiones se pueden hacer comparaciones entre ellos utilizando medidas de proximidad geométrica entre dichos vectores.
El modelo trata de obtener, para cada uno de los términos lingüisticos observados, su significado y para ello se parte de la siguiente premisa:
Se asume que existe una correlación entre el significado de una palabra y sus características dentro de cierto contexto dentro de un lenguaje.
Explicandolo de una manera más sencilla se puede decir que el significado de una palabra dentro de un contexto determinado (un párrafo, una frase, un texto completo) puede determinarse observando qué palabras aparecen más comunmente en dicho contexto. Por ejemplo a partir del término perro podría obtenerse un conjunto de palabras tales como {mascota, amigo, hombre, animal, domestico} que ciertamente podría constituir una representación del concepto de perro.
Representación de documentos
En el modelo vectorial genérico cada documento es representado por un vector representando el peso de cada uno de los términos existentes en el índice respecto del documento (ver sección....). El modelo basado en semántica distribuida sin embargo asume que existe una correlación entre la distribución de caracteristicas de una palabra y su significado.
El modelo parte de una matriz de co-ocurrencias entre cada una de las unidades lingüisticas del texto y un conjunto de N términos de definición. Cada elemento nij de la matriz de co-ocurrencias se define como la frecuencia de aparición del término i-ésimo del texto junto con un término j-ésimo de definición.
De esta forma puede definirse el contenido semántico de la unidad lingistica i-ésima por el vector (ni1, ni2, ... nin) mientras que un documento completo se define como la suma de todos los productos entre la definición de cada uno de los términos del índice (ci) y su peso:
dn = sumatorio(Wni Ci)
Cálculo de similitudes
Una vez que se han convertido tanto los documentos como las consultas al nuevo espacio semántico pueden aplicarse cualquiera de las técnicas estudiadas anteriormente para el modelo vectorial (ver sección ...)
Este tipo de vectores pueden hayarse a partir de la matriz de co-ocurrencias entre términos en la colección utilizada. A partir de la representación multidimensional de los documentos y peticiones se pueden hacer comparaciones entre ellos utilizando medidas de proximidad geométrica entre dichos vectores.
El modelo trata de obtener, para cada uno de los términos lingüisticos observados, su significado y para ello se parte de la siguiente premisa:
Se asume que existe una correlación entre el significado de una palabra y sus características dentro de cierto contexto dentro de un lenguaje.
Explicandolo de una manera más sencilla se puede decir que el significado de una palabra dentro de un contexto determinado (un párrafo, una frase, un texto completo) puede determinarse observando qué palabras aparecen más comunmente en dicho contexto. Por ejemplo a partir del término perro podría obtenerse un conjunto de palabras tales como {mascota, amigo, hombre, animal, domestico} que ciertamente podría constituir una representación del concepto de perro.
Representación de documentos
En el modelo vectorial genérico cada documento es representado por un vector representando el peso de cada uno de los términos existentes en el índice respecto del documento (ver sección....). El modelo basado en semántica distribuida sin embargo asume que existe una correlación entre la distribución de caracteristicas de una palabra y su significado.
El modelo parte de una matriz de co-ocurrencias entre cada una de las unidades lingüisticas del texto y un conjunto de N términos de definición. Cada elemento nij de la matriz de co-ocurrencias se define como la frecuencia de aparición del término i-ésimo del texto junto con un término j-ésimo de definición.
De esta forma puede definirse el contenido semántico de la unidad lingistica i-ésima por el vector (ni1, ni2, ... nin) mientras que un documento completo se define como la suma de todos los productos entre la definición de cada uno de los términos del índice (ci) y su peso:
dn = sumatorio(Wni Ci)
Cálculo de similitudes
Una vez que se han convertido tanto los documentos como las consultas al nuevo espacio semántico pueden aplicarse cualquiera de las técnicas estudiadas anteriormente para el modelo vectorial (ver sección ...)
martes, 30 de septiembre de 2008
SVD en la semántica latente
En el anterior artículo se explicaba por encima el funcionamiento de la semántica latente pero uno de los puntos clave apenas se citó. La técnica conocida como "Singular value decomposition" analiza la matriz de pesos original (termino-documento) obteniendo a continuación tres matrices distintas que interpretadas correctamente proporcionan el modelo de semántica latente. Explicada de una manera más sencilla podría decirse que a partir de esta técnica podemos observar las relaciones entre distintos elementos del sistema excluyendo buena parte del "ruido" existente en dichas relaciones.
Este tipo de análisis no se va a analizar en detalle dado que no es el objeto de este proyecto pero si se van a analizar las matrices obtenidas y las posibilidades que nos ofrecen.
* Se van a escribir las matrices poniendo entre paréntesis sus dimensiones debido a las limitaciones del editor.
Partiendo de la matriz original X(txo) que relaciona términos con documentos se descompone en un conjunto de factores ortogonales , en los estudios se utiliza un valor entre 50 y 100. A partir de estos elementos se puede aproximar la matriz original X mediante combinaciones lineales. La descomposición de la matriz original es la siguiente:
X(txo) = T0(txr) S0(rxr) O0'(rxo)
T0 y O0 tienen columnas ortogonales mientras que S0 es la diagonal. En el caso de observar solamente los k valores independientes más significativos la ecuación cambia convirtiendose en el modelo reducido que es el que se utiliza en la técnica de la semántica latente.
X(txr) "parecido" X^(txo) T(txk) S(kxk) O'(kxo)
Comparación de dos términos
Se puede obtener de una manera sencilla la matriz de relaciones entre cada par de términos utilizando la ecuación siguiente:
TS²T'
Comparación de dos documentos
Para obtener la relación existente entre cada par de documentos ha de aplicarse la siguiente ecuación:
DS²D'
Comparación entre término y documento
La matriz que almacena la comparación entre cada par término-documento se puede obtener aplicando:
TSD'
Este tipo de análisis no se va a analizar en detalle dado que no es el objeto de este proyecto pero si se van a analizar las matrices obtenidas y las posibilidades que nos ofrecen.
* Se van a escribir las matrices poniendo entre paréntesis sus dimensiones debido a las limitaciones del editor.
Partiendo de la matriz original X(txo) que relaciona términos con documentos se descompone en un conjunto de factores ortogonales , en los estudios se utiliza un valor entre 50 y 100. A partir de estos elementos se puede aproximar la matriz original X mediante combinaciones lineales. La descomposición de la matriz original es la siguiente:
X(txo) = T0(txr) S0(rxr) O0'(rxo)
T0 y O0 tienen columnas ortogonales mientras que S0 es la diagonal. En el caso de observar solamente los k valores independientes más significativos la ecuación cambia convirtiendose en el modelo reducido que es el que se utiliza en la técnica de la semántica latente.
X(txr) "parecido" X^(txo) T(txk) S(kxk) O'(kxo)
Comparación de dos términos
Se puede obtener de una manera sencilla la matriz de relaciones entre cada par de términos utilizando la ecuación siguiente:
TS²T'
Comparación de dos documentos
Para obtener la relación existente entre cada par de documentos ha de aplicarse la siguiente ecuación:
DS²D'
Comparación entre término y documento
La matriz que almacena la comparación entre cada par término-documento se puede obtener aplicando:
TSD'
viernes, 26 de septiembre de 2008
Semántica Latente
Acabo de hacer la primera lectura a los artículos sobre semántica latente y he de decir que me parece una técnica que parte de unas ideas muy interesantes.
Si he entendido bien los artículos, el modelo de semántica latente parte del hecho de que una query y un documento sin términos comunes podrían estar hablando de lo mismo (dado que puede tener términos sinónimos) mientras que si tuvieran términos comunes podrían hablar de cosas completamente distintas (polisemia).
Partiendo de estos problemas esta técnica se resume de forma muy esquematizada como sigue:
1. Partimos de una representación similar a la del modelo vectorial de tal manera que tenemos un vector de pesos (un peso por cada término del índice) para cada documento.
2. Se aplica un método estadístico conocido como "singular-value-decomposition" descomponiendo la matriz original en 3 matrices de una forma muy específica. Esta descomposición permite observar la relevancia de cada término de manera independiente del resto de los términos.
3. Algunos de los componenetes de las matrices anteriores tienen valores muy pequeños y pueden ignorarse. Una vez aplicada una reducción de los términos tendremos una versión reducida de las matrices anteriores.
4. Al considerar únicamente los componentes más importantes de forma independiente estamos teniendo en cuenta las asociaciones más fuertes dentro de la estructura estudiada. El utilizar sólo las relaciones más fuertes posibilita la eliminación, al menos en parte, del "ruido" producido por la polisemia y la sinonimia.
5. A partir del modelo reducido se puede aproximar mediante combinación lineal el resto de valores de la matriz termino-documento. Las filas de la matriz aproximada de término-documento son utilizadas para el cálculo de similitud entre documentos ya sea por el método del coseno o por cualquier método similar.
Nota: a partir de la descomposición SVD se pueden observar relaciones independientes entre términos y / o documentos mediante cálculos matriciales sencillos
Si he entendido bien los artículos, el modelo de semántica latente parte del hecho de que una query y un documento sin términos comunes podrían estar hablando de lo mismo (dado que puede tener términos sinónimos) mientras que si tuvieran términos comunes podrían hablar de cosas completamente distintas (polisemia).
Partiendo de estos problemas esta técnica se resume de forma muy esquematizada como sigue:
1. Partimos de una representación similar a la del modelo vectorial de tal manera que tenemos un vector de pesos (un peso por cada término del índice) para cada documento.
2. Se aplica un método estadístico conocido como "singular-value-decomposition" descomponiendo la matriz original en 3 matrices de una forma muy específica. Esta descomposición permite observar la relevancia de cada término de manera independiente del resto de los términos.
3. Algunos de los componenetes de las matrices anteriores tienen valores muy pequeños y pueden ignorarse. Una vez aplicada una reducción de los términos tendremos una versión reducida de las matrices anteriores.
4. Al considerar únicamente los componentes más importantes de forma independiente estamos teniendo en cuenta las asociaciones más fuertes dentro de la estructura estudiada. El utilizar sólo las relaciones más fuertes posibilita la eliminación, al menos en parte, del "ruido" producido por la polisemia y la sinonimia.
5. A partir del modelo reducido se puede aproximar mediante combinación lineal el resto de valores de la matriz termino-documento. Las filas de la matriz aproximada de término-documento son utilizadas para el cálculo de similitud entre documentos ya sea por el método del coseno o por cualquier método similar.
Nota: a partir de la descomposición SVD se pueden observar relaciones independientes entre términos y / o documentos mediante cálculos matriciales sencillos
jueves, 25 de septiembre de 2008
Organización del pfc
Estoy teniendo algunos dilemas últimamente en cómo organizar bien la parte de Antecedentes (estado del arte) para que resulte intuitivo y fácil de leer.
La idea que manejo ahora y que me parece la más correcta es la siguiente:
1. Conceptos previos
1.1. Objetivos de la recuperación de información
1.2. Análisis de información
1.3. Complejidad
2. Resumen historico
2.1. Inicios
2.2. Sistemas automáticos para bibliotecas
2.3. World Wide Web
2.4. Nuevas investigaciones
3. Modelos de recuperación de información
3.1. Modelo booleano
3.2. Modelo Booleano extendido
3.3. Modelo probabilístico
3.4. Modelo vectorial
3.5. Modelos basados en lógica borrosa
3.6. Modelos lógicos
3.7. Modelo basados en la interactividad
3.8. Modelos basados en la Inteligencia Artificial
3.9. Modelos basados en semántica latente
3.10. Modelos basados en semántica distribuida
4. Técnicas de procesamiento
4.1. Escaneado de sentencias clave
4.2. Proceso de eliminación sintáctica
4.3. Selección de frases preposicionales
4.4. Lematización
4.5. Detección de sinónimos
4.6. Diccionarios de frases
4.7. Metodos de expansión jerárquicos
4.8. Elaboración automática del proceso de selección
De esta forma describo por una parte los modelos y por otra las técnicas específicas (que pueden usar varios modelos) referenciandolos correctamente según corresponda...
La idea que manejo ahora y que me parece la más correcta es la siguiente:
1. Conceptos previos
1.1. Objetivos de la recuperación de información
1.2. Análisis de información
1.3. Complejidad
2. Resumen historico
2.1. Inicios
2.2. Sistemas automáticos para bibliotecas
2.3. World Wide Web
2.4. Nuevas investigaciones
3. Modelos de recuperación de información
3.1. Modelo booleano
3.2. Modelo Booleano extendido
3.3. Modelo probabilístico
3.4. Modelo vectorial
3.5. Modelos basados en lógica borrosa
3.6. Modelos lógicos
3.7. Modelo basados en la interactividad
3.8. Modelos basados en la Inteligencia Artificial
3.9. Modelos basados en semántica latente
3.10. Modelos basados en semántica distribuida
4. Técnicas de procesamiento
4.1. Escaneado de sentencias clave
4.2. Proceso de eliminación sintáctica
4.3. Selección de frases preposicionales
4.4. Lematización
4.5. Detección de sinónimos
4.6. Diccionarios de frases
4.7. Metodos de expansión jerárquicos
4.8. Elaboración automática del proceso de selección
De esta forma describo por una parte los modelos y por otra las técnicas específicas (que pueden usar varios modelos) referenciandolos correctamente según corresponda...
jueves, 18 de septiembre de 2008
Resurgimiento
Después de un curso bastante intenso he retomado estos días el proyecto fuertemente. Por fin he comenzado a redactar parte de los antecedentes de la documentación (lo que se suele llamar estado del arte) y a recordar todo lo aprendido hace casi un año.
De momento no he tenido problemas graves y todo sigue su ritmo por lo cual este mensaje solo será un formalidad para indicar que sigo trabajando en ello. A lo largo de la semana que viene publicare la jerarquía del documento y cuando Dani vuelva de sus vacaciones le enviaré el borrador que tenga en ese momento.
De momento no he tenido problemas graves y todo sigue su ritmo por lo cual este mensaje solo será un formalidad para indicar que sigo trabajando en ello. A lo largo de la semana que viene publicare la jerarquía del documento y cuando Dani vuelva de sus vacaciones le enviaré el borrador que tenga en ese momento.
Suscribirse a:
Entradas (Atom)