Natural Languages

Facultade de Informática da Coruña
Computer Science Engineering
2009-2010

Esta páxina en galego

Esta páxina en español

Outline:

• Faculty
• Rooms and Timeline
• Programmme
• Bibliography
• Student time
• Practical works
• Evaluation
• Links of interest

REMARK: there exists a official page of the course in the web site of the Faculty.

IMPORTANT REMARK: Information provided in this pages does not substitute the official information published in official media.

Faculty

• Miguel A. Alonso Pardo
• Jesús Vilares Ferro

Rooms and Timeline

• Theory: the first half of the term, Room 2.6, Monday 16:30-18:30 and Friday 15:30-17:30
• Practical works: the second half of the term, Lab. 1.3, Friday 15:30-17:30

Programme

1.  Introduction
1. Levels of analysis
2. Ambiguity
2.  Linguistic Resources
1. Tag-sets
2. Dictionaries
3. Tagged texts
4. Tree-banks
3. Lexical Analysis
1. Text segmentation
2. Flexive and derivative morphology
3. Modelizing large dictionaries
4. Numbered acyclic deterministic finite-state automata
5. Finite-state transducers and two-level morphology
4. Tagging
1. Hidden Markov Models
2. Efficient execution of Hidden Markov Models
3. Smoothing techniques
4. Dealing with unknown words
5. Transformation-based and error-driven tag learning
5. Context-free parsing
1. Parsing schemata
2. Bottom-up parsing
3. Earley's parser
4. Push-down automata and dynamic programming
5. Generalized LR parsers
6. Shared forest
7. Probabilistic parsing
6. Parsing of mildly context-sensitive languages
1. Tree adjoining grammars
2. Parsing tree adjoining grammars
3. Automata for parsing tree adjoining grammars
4. Derivation trees
5. Probabilistic Representación compartida de los árboles de derivación
7. Semantic analysis
   
1. Feature structures and unification-based formalisms
   
2. Lexical relations: WordNet and EuroWordNet
   
8. Information Retrieval (IR)
   
1. Basic concepts
   
2. Retrieval models: boolean, vector and probabilistic
   
3. Indexing and retrieval
   
4. Evaluation of IR systems
   
5. Wen IR. A case in point: Google
   
6. Applications of natural language processing to IR: linguistic variation
   
9. Information Extraction (IE)
   
1. Basic concepts
   
2. Arquitecture of an IE system
   
3. IE tasks
   
4. Evaluation of IE systema
   
5. Examples of IE sytems: FASTUS and others
   
10. Question Answering (QA)
    
1. Basic conceptos
   
2. QA vs. IR/IE
   
3. Arquitecture of a QA syetem
   
4. Question processing
   
5. Retrieving and selectinf documents/passages
   
6. Answer extraction
   
7. Evaluaction of QA systems
   
11. Machine Translation (MT)
    
1. Basic concepts and open issues
   
2. "Classic" approaches
   
3. Statistical approaches
   
4. Applications in multilingual IR

Basic Bibliography

• Daniel Jurafsky y James H. Martin, Speech and Language Processing. Second Edition, Pearson Education, Upper Saddle River, New Jersey, 2009.
• Christopher D. Manning and Hinrich Schütze, Foundations of Statistical Natural Language Processing, The MIT Press, Cambridge (Massachusetts) and London (England), 1999.
• ChristopherD. Manning, Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval, Cambridge University Press, Cambridge, 2008.

Additional Bibliography:

In shelves I28 of the librtary you can found a lot of books on Natural Language Processing. We strongly recommend to visit that part of the library.

• Ricardo Baeza-Yates and Berthier Ribeiro-Neto, Modern Information Retrieval, Addison Wesley and ACM Press, Harlow, England, 1999.
• Marie-Francine Moens, Information Extraction: Algorithms and Prospects in a Retrieval Context, Springer, Dordrecht, 2006.
• Klaas Sikkel, Parsing Schemata - A Framework for Specification and Analysis of Parsing Algorithms, Texts in Theoretical Computer Science - An EATCS Series. Springer-Verlag, Berlin/Heidelberg/New York, 1997 (a former version of this book is available at ftp://ftp.cs.utwente.nl/pub/doc/Parlevink/PhD/Sikkel/).
• Robert Dale, Hermann Moisi and Harold Somers (editores), Handbook of Natural Language Processing, Marcel Dekker, Inc., New York and Basel, 2000.
• James Allen, Natural Language Understanding, The Benjamin/Cummings Publishing Company, Inc., Redwood City, CA, USA, second edition, 1995.

Slides:

• Lecture about unification-based grammars
• Example
• Lecture about semantic representation and analysis
• Example
• Lecture about shallow parsing
  
• On-line demos:
• Freeling 2.1 demo (including Spanish and Galician)
• Cognitive Computation Group (CCG) demo (Univ. of Illinois at Urbana-Champaign)
• Memory-Based Shallow Parsing (MBSP) demo, Computational Linguistics and Psycholinguistics (CLiPS) Research Centre, University of Antwerp
  
• Lecture about lexical semantics
• Lecture about information retrieval
• Tutorial about the probabilistic model: notes, slides
• Example of index generation
• Lecture about information extraction
• FASTUS system: web, local (protected)
• Lecture about question answering
• On-line QA systems:
• START (general purpose)
• EAGLi (genomics)
  
• Lecture about machine translation

Lecture notes:

• Análisis léxico:
• preprocesamiento.pdf (artículo conjunto del Prof. Jorge Graña, Fco. Mario Barcala y Jesús Vilares sobre la segmentación y el preprocesamiento)
• diccionario.pdf (material preparado por el Prof. Jorge Graña sobre la implemenatción eficiente de grandes diccionarios)
• Etiquetación:
• HMM.pdf (material preparado por el Prof. Jorge Graña sobre los modelos de Markov ocultos)
• brill.pdf (material preparado por el Prof. Jorge Graña sobre aprendizaje de etiquetas basado en transformaciones y dirigido por el error)
• Análisis sintáctico de gramáticas independientes del contexto:
• parsing_schemata.pdf (material preparado por el Prof. Miguel A. Alonso sobre los esquemas de análisis sintáctico)
• cfg_parsing.pdf (material preparado por el Prof. Miguel A. Alonso sobre los algoritmos CYK y Earley)
• PDA.pdf (material preparado por el Prof. Miguel A. Alonso sobre la interpretación en programación dinámica de los autómatas a pila no deterministas)
• PCFG.pdf (material preparado por el Prof. Jorge Graña para introducir el análisis sintáctico probabilístico)
• Análisis sintáctico de gramáticas suavemente dependientes del contexto:
• TAG.pdf (material preparado por el Prof. Miguel A. Alonso sobre las gramáticas de adjunción de árboles)
• parsing_TAG.pdf (material preparado por el Prof. Miguel A. Alonso sobre el análisis sintáctico de las gramáticas de adjunción de árboles)
• LIA.pdf (material preparado por el Prof. Miguel A. Alonso sobre los autómatas lineales de índices)
• Análisis semántico:
• feature_structures.pdf   (material sobre estructuras de rasgos extraído del capítulo 7 del libro de Sikkel)
• parsing_unification.pdf (material sobre análisis sintáctico de gramáticas de unificación extraído del capítulo 8 del libro de Sikkel)
• wordnet.pdf (cinco artículos sobre WordNet)
• Recuperación y extracción de información:
• ir.pdf   (Introducción a la recuperación de informació:n realizada por el Prof. jesús Vilares)
• ir_pobabilistico.pdf   (Introducción a los modelos probabilísticos de recuperación de informació:n realizada por el Prof. jesús Vilares)
• slides_IR.pdf   (transparencias del capítulo 15 del libro de Manning & Schütze)
• pagerank.pdf (artículo de Page, Brin, Motwani & Winograd sobre el algoritmo PageRank usado por Google)
• ie.pdf (tutorial de Appelt & Israel en IJCAI'99 sobre extracción de información)
• agrep.pdf (technical Report de Wu y Manber sobre pattern matchning con errores)

Student time

See the web page of the Faculty

Practical works

Last year (2008-09) final lab work

Evaluation

• Evaluation:

  Final mark of the course is based on pratical works. Written examination is an option.

Links

• LIBNAFDA, A library for efficient management of very large dictionaries based on numbered acyclic deterministic finite-state automata.
• http://coleweb.dc.fi.udc.es/cole/sites_cl.html, COLE Group page with links to NLP sites
• http://coleweb.dc.fi.udc.es/cole/sites_ir.html, COLE GRoup page with links to IR and IE sites
• El Mundo según Google, Documentos TV program scheduled Tuesday, 30 September 2007, by La 2