====== Trabajo Práctico 2 - Etiquetado de Secuencias ======

[[materias:pln:2017|(volver a la página principal)]]

En este trabajo práctico implementaremos varios modelos de etiquetado de
secuencias y realizaremos algunos experimentos con ellos.

  * Repositorio: https://github.com/PLN-FaMAF/PLN-2017/tree/master/tagging.
  * Fecha de entrega: 18/05 a las 23:59.


===== Instrucciones =====

El código base para el proyecto se encuentra en el [[https://github.com/PLN-FaMAF/PLN-2017/tree/master/tagging|repositorio de la materia]].
La entrega del proyecto es a través de github. Por lo tanto, deben **hacer un "fork" del repositorio** dentro de sus cuentas de github.

Además del código fuente, **deben elaborar un README** con una breve explicación de lo que hicieron en cada ejercicio. El README puede estar en texto plano (txt), markdown (md) o restrucured text (rst), y debe estar incluído dentro de la carpeta ''tagging''.

Criterios de Evaluación:

  * Estilo de codificación (chequeado con flake8 y a ojo).
  * Diseño del código: uso de clases, herencia, etc.
  * Uso y aprobación de tests (provistos y definidos por uds.).
  * Uso apropiado de git (commits granulares, logs informativos).
  * Resultados.
  * README.


===== Ejercicio 1: Corpus AnCora: Estadísticas de etiquetas POS =====

Programar un script ''stats.py'' que muestre la siguiente información del corpus:

  * Estadísticas básicas:
    * Cantidad de oraciones.
    * Cantidad de ocurrencias de palabras.
    * Cantidad de palabras (vocabulario).
    * Cantidad de etiquetas (vocabulario de tags).
  * Etiquetas más frecuentes: Una tabla con las 10 etiquetas más frecuentes y la siguiente información para cada una:
    * Cantidad de veces que aparece (frecuencia), y porcentaje del total.
    * Cinco palabras más frecuentes con esa etiqueta.
    * En el README, agregar a mano una breve descripción del significado de la etiqueta.
  * Niveles de ambigüedad de las palabras: Una figura similar a la Figura 5.10 de Jurafsky & Martin (2008). Para cada nivel de ambigüedad (de 1 a 9) mostrar:
    * Cantidad de palabras y porcentaje del total.
    * Cinco palabras más frecuentes.
  * Incluir todas las estadísticas en el README.

Uso del script:

  $ python tagging/scripts/stats.py

Documentación:

  * [[http://clic.ub.edu/corpus/|Corpus AnCora]]
  * [[https://web.archive.org/web/20160325024315/http://nlp.lsi.upc.edu/freeling/doc/tagsets/tagset-es.html|Etiquetas EAGLES]]
  * [[https://nlp.stanford.edu/software/spanish-faq.shtml#tagset|Stanford CoreNLP simplified tagset]]


===== Ejercicio 2: Baseline Tagger =====

  * Programar un etiquetador baseline, que elija para cada palabra su etiqueta más frecuente observada en entrenamiento.
  * Para las palabras desconocidas, devolver la etiqueta 'nc0s000'.

Interfaz de ''BaselineTagger'' en  ''baseline.py'':

<code python>
class BaselineTagger:

    def __init__(self, n, tagged_sents):
        """
        tagged_sents -- training sentences, each one being a list of pairs.
        """

    def tag(self, sent):
        """Tag a sentence.

        sent -- the sentence.
        """

    def tag_word(self, w):
        """Tag a word.

        w -- the word.
        """

    def unknown(self, w):
        """Check if a word is unknown for the model.

        w -- the word.
        """
</code>

Tests:

  $ nosetests tagging/tests/test_baseline.py 


===== Ejercicio 3: Entrenamiento y Evaluación de Taggers =====

  * Programar un script ''train.py'' que permita entrenar un etiquetador baseline.
  * Programar un script ''eval.py'' que permita evaluar un modelo de tagging. Calcular:
    * //Accuracy//, esto es, el porcentaje de etiquetas correctas.
    * //Accuracy// sobre las palabras conocidas y sobre las palabras desconocidas.
    * Matriz de confusión, como se explica en la sección 5.7.1 (//Error Analysis//) de Jurafsky & Martin.
  * Entrenar y evaluar el modelo baseline del ejercicio anterior. Reportar los resultados en el README.
  * **Bonus**: Graficar la matriz de confusión como un mapa de calor (ver documentación abajo).

Ejemplo de uso de los scripts:

  $ python tagging/scripts/train.py -o baseline
  $ python tagging/scripts/eval.py -i baseline

Documentación:

  * http://scikit-learn.org/stable/auto_examples/model_selection/plot_confusion_matrix.html

===== Ejercicio 4: Hidden Markov Models y Algoritmo de Viterbi =====

  * Implementar un Hidden Markov Model cuyos parámetros son las probabilidades de transición entre estados (las etiquetas) y de emisión de símbolos (las palabras).
  * Implementar el algoritmo de Viterbi que calcula el etiquetado más probable de una oración.

Interfaz de ''HMM'' y ''ViterbiTagger'' en  ''hmm.py'':

<code python>
class HMM:

    def __init__(self, n, tagset, trans, out):
        """
        n -- n-gram size.
        tagset -- set of tags.
        trans -- transition probabilities dictionary.
        out -- output probabilities dictionary.
        """

    def tagset(self):
        """Returns the set of tags.
        """

    def trans_prob(self, tag, prev_tags):
        """Probability of a tag.

        tag -- the tag.
        prev_tags -- tuple with the previous n-1 tags (optional only if n = 1).
        """

    def out_prob(self, word, tag):
        """Probability of a word given a tag.

        word -- the word.
        tag -- the tag.
        """

    def tag_prob(self, y):
        """
        Probability of a tagging.
        Warning: subject to underflow problems.

        y -- tagging.
        """

    def prob(self, x, y):
        """
        Joint probability of a sentence and its tagging.
        Warning: subject to underflow problems.

        x -- sentence.
        y -- tagging.
        """

    def tag_log_prob(self, y):
        """
        Log-probability of a tagging.

        y -- tagging.
        """

    def log_prob(self, x, y):
        """
        Joint log-probability of a sentence and its tagging.

        x -- sentence.
        y -- tagging.
        """

    def tag(self, sent):
        """Returns the most probable tagging for a sentence.

        sent -- the sentence.
        """


class ViterbiTagger:

    def __init__(self, hmm):
        """
        hmm -- the HMM.
        """

    def tag(self, sent):
        """Returns the most probable tagging for a sentence.

        sent -- the sentence.
        """
</code>

Tests:

  $ nosetests tagging/tests/test_hmm.py 
  $ nosetests tagging/tests/test_viterbi_tagger.py 

Documentación:

  * [[http://www.cs.columbia.edu/~mcollins/hmms-spring2013.pdf]]


===== Ejercicio 5: HMM POS Tagger =====

  * Implementar en una clase ''MLHMM'' un Hidden Markov Model cuyos parámetros se estiman usando Maximum Likelihood sobre un corpus de oraciones etiquetado.
  * La clase debe tener **la misma interfaz que ''HMM''** con las modificaciones y agregados especificadas abajo.
  * Agregar al script de entrenamiento (train.py) una opción de línea de comandos que permita utilizar la MLHMM con distintos valores de ''n''.
  * Entrenar y evaluar para varios valores de ''n'' (1, 2, 3 y 4). Reportar los resultados en el README. Reportar también tiempo de evaluación.

Interfaz de ''MLHMM'' en ''hmm.py'':

<code python>
class MLHMM:

    def __init__(self, n, tagged_sents, addone=True):
        """
        n -- order of the model.
        tagged_sents -- training sentences, each one being a list of pairs.
        addone -- whether to use addone smoothing (default: True).
        """

    def tcount(self, tokens):
        """Count for an n-gram or (n-1)-gram of tags.

        tokens -- the n-gram or (n-1)-gram tuple of tags.
        """

    def unknown(self, w):
        """Check if a word is unknown for the model.

        w -- the word.
        """

    """
       Todos los métodos de HMM.
    """
</code>

Tests:

  $ nosetests tagging/tests/test_ml_hmm.py 

Documentación:

  * [[http://www.cs.columbia.edu/~mcollins/hmms-spring2013.pdf]]

===== Ejercicio 6: Features para Etiquetado de Secuencias =====

  * Implementar en ''features.py'' los siguientes features básicos:
    * ''word_lower'': la palabra actual en minúsculas.
    * ''word_istitle'': la palabra actual empieza en mayúsculas.
    * ''word_isupper'': la palabra actual está en mayúsculas.
    * ''word_isdigit'': la palabra actual es un número.
  * También implementar los siguientes features paramétricos:
    * ''NPrevTags(n)'': la tupla de los últimos ''n'' tags.
    * ''PrevWord(f)'': Dado un feature ''f'', aplicarlo sobre la palabra anterior en lugar de la actual.

Interfaz de los features paramétricos en ''features.py'':

<code python>
class NPrevTags(Feature):

    def __init__(self, n):
        """Feature: n previous tags tuple.

        n -- number of previous tags to consider.
        """

    def _evaluate(self, h):
        """n previous tags tuple.

        h -- a history.
        """


class PrevWord(Feature):

    def __init__(self, f):
        """Feature: the feature f applied to the previous word.

        f -- the feature.
        """

    def _evaluate(self, h):
        """Apply the feature to the previous word in the history.

        h -- the history.
        """
</code>

Tests:

  $ nosetests tagging/tests/test_features.py 

Documentación:

  * [[http://nbviewer.ipython.org/url/cs.famaf.unc.edu.ar/~francolq/Etiquetado%20de%20Secuencias%20con%20Feature%20Forge.ipynb|Etiquetado de Secuencias con Feature Forge]]


===== Ejercicio 7: Maximum Entropy Markov Models =====

  * Implementar un MEMM con el siguiente //pipeline// de scikit-learn:
    * Vectorizador (''featureforge.vectorizer.Vectorizer'') con los features definidos en el ejercicio anterior.
    * Clasificador de máxima entropía (''sklearn.linear_model.LogisticRegression'').
  * Implementar un algoritmo de tagging en el método ''tag'' usando //beam inference// con un //beam// de tamaño 1.
  * Agregar al script de entrenamiento (train.py) una opción de línea de comandos que permita utilizar el MEMM con distintos valores de ''n''.
  * Entrenar y evaluar para varios valores de ''n'' (1, 2, 3 y 4).
  * Probar también los siguientes clasificadores:
    * ''sklearn.naive_bayes.MultinomialNB''
    * ''sklearn.svm.LinearSVC''
  * Reportar los resultados en el README. Reportar también tiempo de evaluación.
  * **Bonus**: Inventar y agregar features que mejoren la calidad del tagger.

Interfaz de ''MEMM'' en ''memm.py'':

<code python>
class MEMM:

    def __init__(self, n, tagged_sents):
        """
        n -- order of the model.
        tagged_sents -- list of sentences, each one being a list of pairs.
        """

    def sents_histories(self, tagged_sents):
        """
        Iterator over the histories of a corpus.

        tagged_sents -- the corpus (a list of sentences)
        """

    def sent_histories(self, tagged_sent):
        """
        Iterator over the histories of a tagged sentence.

        tagged_sent -- the tagged sentence (a list of pairs (word, tag)).
        """

    def sents_tags(self, tagged_sents):
        """
        Iterator over the tags of a corpus.

        tagged_sents -- the corpus (a list of sentences)
        """

    def sent_tags(self, tagged_sent):
        """
        Iterator over the tags of a tagged sentence.

        tagged_sent -- the tagged sentence (a list of pairs (word, tag)).
        """

    def tag(self, sent):
        """Tag a sentence.

        sent -- the sentence.
        """

    def tag_history(self, h):
        """Tag a history.

        h -- the history.
        """

    def unknown(self, w):
        """Check if a word is unknown for the model.

        w -- the word.
        """
</code>

Tests:

  $ nosetests tagging/tests/test_memm.py 

Documentación:

  * Introducción a scikit-learn para clasificación de textos:
    * http://scikit-learn.org/stable/tutorial/text_analytics/working_with_text_data.html
    * [[http://nbviewer.ipython.org/url/cs.famaf.unc.edu.ar/~francolq/Clasificaci%C3%B3n%20de%20Texto%20con%20scikit-learn.ipynb#|Mi versión del mismo tutorial]]
  * Beam inference:
    * [[https://class.coursera.org/nlp/lecture/133|video lecture]] (ir al minuto 07:10)
    * [[https://d396qusza40orc.cloudfront.net/nlp/slides/04-02-Maximum_Entropy_Sequence_Models-v2.pdf|slides]]


===== Ejercicio 8 (punto bonus): Algoritmo de Viterbi para MEMMs (con Beam)  =====

Implementar el algoritmo de Viterbi para obtener la secuencia de tags de máxima probabilidad de acuerdo a un MEMM:

  * Para obtener las probabilidades de los tags, usar el método ''predict_proba'' si el clasificador lo tiene (e.g. ''LogisticRegression'' y ''MultinomialNB''). Si no, usar la exponenciación (base 2) del método ''decision_function'' (e.g. ''LinearSVC'').
  * Beam: En cada paso del Viterbi, guardar sólo los ''k'' taggings más probables, a donde ''k'' es un parámetro de la clase.
  * Evaluar para varios clasificadores (''LogisticRegression'' y ''LinearSVC''), para varios valores de ''n'' (1, 2, 3 y 4), y para varios valores de ''k'' (1, 2 y 3). Reportar los resultados en el README. Reportar también tiempo de evaluación.