esteban ruiz dirección: dr. gabriel infantelópez
TRANSCRIPT
![Page 1: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/1.jpg)
El algoritmo ADIOS
Esteban Ruiz
Dirección: Dr. Gabriel InfanteLópez
![Page 2: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/2.jpg)
Contenido
● ¿Qué es? ● Ventajas● Ideas generales● Conceptos útiles● El procedimiento MEX, caminos generalizados● Esquema del algoritmo● Dificultades e implementación. Aplicaciones
![Page 3: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/3.jpg)
¿Qué es?El problema:
Inferir reglas subyacentes en corpus no anotados.
ADIOS: Automatic Distillation of StructureZ. Solan, D. Horn, E. Ruppin, S. Edelman (TAU)
![Page 4: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/4.jpg)
Ventajas y característicasVentajas y características● No supervisado● Corpus no estructurado● Combina probabilidades y reglas
Desventajas
● Infiere sólo gramáticas limitadas
![Page 5: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/5.jpg)
Ideas generales del algoritmoCorpus, léxico, símbolos especiales
Cargar el corpus en un pseudografo
LéxicoDos
símbolos especiales:
begin
end
begin
![Page 6: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/6.jpg)
Ideas generales del algoritmoEn cada camino:
Detección de patrones y reescritura del grafo
Detección de patrones más complejos:
clases de equivalencia y caminos generalizados
![Page 7: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/7.jpg)
Conceptos útiles
Definición de PR y P
L
IDEM p/ PL
![Page 8: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/8.jpg)
Más conceptos útiles● Matriz M
● DR y D
L (Relaciones de decrecimiento)
● Prueba de significación
![Page 9: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/9.jpg)
El procedimiento MEX (simplificado)
![Page 10: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/10.jpg)
Esquema del algoritmo:Inicializacion:Repetir hasta el
fin del archivo:
● Leer el archivo hasta encontrar el final de una secuencia
● Cargar los símbolos encontrados como un nuevo camino en el pseudografo
Destilación de patronesCon cada camino:
● Ejecutar MEX en ese camino
● Si se obtuvo un patrón reescribir (rewire) el grafo
![Page 11: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/11.jpg)
Esquema del algoritmo:Gen: primer pasoCon cada camino:
● Por cada posición posible de una ventana de largo L:
– Considerar todos los huecos posibles en esa ventana y ejecutar MEX para cada caso
● Seleccionar el mejor patrón encontrado y reescribir el grafo (nueva clase de equiv)
![Page 12: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/12.jpg)
Esquema del algoritmo:Gen: bootstrapCon cada camino:
● Con cada posición de una ventana de largo L
– Construir el camino generalizado
– Reducir el camino generalizado
– Realizar MEX sobre elcamino generalizado reducido
● Si se detectó un patrón:
– ¿nueva clase de equiv?
– Reescribir el grafo
![Page 13: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/13.jpg)
Dificultades
● Calculo de la binomial● Especificación del
algoritmo● Definición de camino
generalizado● Adioslite● Prueba de significación
![Page 14: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/14.jpg)
Software utilizado
● cvs● eclipse● JDK 6● Librerias de apache y
Jgraph● ArgoUML
![Page 15: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/15.jpg)
Diseño
![Page 16: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/16.jpg)
Diseño
![Page 17: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/17.jpg)
Experiencias de la implementación
● Algo de documentación● Testing● Problemas con la
especificación● Resultados del diseño OO
![Page 18: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/18.jpg)
BibliografíaZ. Solan, D. Horn, E. Ruppin and S. Edelman, Unsupervised learning of
natural languages. Editado por James L. McClelland, Carnegie Mellon University, Pittsburgh, PA, y aprobado June 14, 2005.
D. S. Moore, Estadística aplicada básica, Antoni Bosch editor, 1995.
M. Triola, Estadística elemental, Addison Wesley Longman, 7ma. ed., 2000.
D. K. Hildebrand, L. Ott, Estadística aplicada a la administración y a la economía, Addison Wesley Longman, 3ra. ed, 1998.
J. Makkonen, H. AhonenMyka and Marko Salmenkivi, Applying Semantic Classes in Event Detection and Tracking.
J. Weeds, D. Weir and D. McCarthy, Characterising Measures of Lexical Distributional Similarity.
![Page 19: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/19.jpg)
BibliografíaJ. Brookshear, Lenguajes formales, autómatas y complejidad. Addison
Wesley Iberoamericana.
L. A. Ballesteros, Resolving ambiguity for crosslanguage information retrieval: A dictionary approach, Univ. of Massachusetts, 2001.
N. K. Bosa, P. Liang, Neural Network Fundamentals with Graphs, Algorithms, and Applications.
P. G. Hoel, S. C. Port, C. J. Stone, Introduction to Stochastic Proceses, Waveland Press, 1987.
C. M. Grinstead, J. L. Snell, Introduction to Probability, AMS, second revised edition, 1997.
G. Infante Lopez, Two level grammars for natural language parsing, Soluciones Gráficas, 2005.
![Page 20: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/20.jpg)
Agradecimientos y preguntas
![Page 21: Esteban Ruiz Dirección: Dr. Gabriel InfanteLópez](https://reader030.vdocumento.com/reader030/viewer/2022012518/6192054596162a49595a1d58/html5/thumbnails/21.jpg)
ADIOS