Babel.ZIP II

Em texto anterior, mencionei o seguinte problema proposto por Knight e Marcu (2000): dada uma frase como esta,

El universo (que otros llaman la Biblioteca) se compone de un número indefinido, y tal vez infinito, de galerías hexagonales, con vastos pozos de ventilación en el medio, cercados por barandas bajísimas

pretende-se construir um algoritmo capaz de comprimi-la, isto é, substituí-la por uma frase tão curta quanto possível que satisfaça as seguintes propriedades:

• Preserve a informação essencial contida na frase original
• Elimine tudo o que seja acessório
• Seja gramatical
• Tenha o mesmo sentido da frase original
  

(Repare-se que esta definição do problema é vaga e omite aspectos importantes como quanto queremos comprimir ou qual é o contexto que determina o que é essencial e o que é acessório; mas por ora vamos prosseguir, sem complicar em demasia.)

Uma frase aceitável dentro destes parâmetros seria algo como

El universo se compone de un número indefinido de galerías hexagonales cercados por barandas.

Esta frase tem a particularidade de poder ser obtida a partir da frase original apenas removendo algumas palavras, sobrando aquelas que se encontram a negrito:

El universo (que otros llaman la Biblioteca) se compone de un número indefinido, y tal vez infinito, de galerías hexagonales, con vastos pozos de ventilación en el medio, cercados por barandas bajísimas.

Se restringirmos o nosso universo de procura àquelas frases que podem ser obtidas por este processo (isto é, removendo palavras da frase original), evitamos passos tradicionalmente difíceis em linguística computacional, como representação semântica e síntese de texto. Mesmo assim, o espaço de procura (isto é, o número de possíveis compressões) é exponencial: cada palavra na frase original pode ou não ser seleccionada (isto é, colocada a negrito); havendo N palavras, resultam 2^N possíveis compressões, de entre as quais queremos seleccionar uma.

O algoritmo proposto por Knight e Marcu (2000) é inspirado no noisy channel model, um modelo originalmente proposto por Claude Shannon (1948) para modelizar comunicação na presença de ruído, e adoptado em tradução automática estatística desde os tempos da Guerra Fria (a história deste modelo fica para um post futuro). Segundo este modelo, há um emissor que transmite uma frase comprimida c. O ruído no canal corrompe esta frase adicionando palavras irrelevantes; como resultado, o receptor observa uma frase "longa" l que corresponde à nossa frase original. O objectivo é estimar c a partir de l. A probabilidade da compressão c dada a frase original l é proporcional a

P(l | c) P(c)

O primeiro termo, P(l | c), representa o modelo do canal. O segundo termo, P(c), representa o modelo do emissor. Tipicamente, a extracção da informação essencial é assegurada pelo primeiro modelo; a gramaticalidade é assegurada pelo segundo modelo. Para fazer face ao espaço de procura exponencial, Knight e Marcu (2000) utilizam um processador sintáctico e assumem (no modelo de P(l | c)) que l é obtido a partir de c através da adição de constituintes sintácticos, de acordo com um modelo probabilístico. Os parâmetros deste modelo e da gramática estocástica associado ao modelo do emissor P(c) são estimados generativamente usando corpora paralelo de frases e respectivas compressões. Através de algoritmos de programação dinâmica, é possível descodificar (ou seja, obter a compressão c que maximiza P(c | l)) de forma eficiente.

Este tipo de problemas em que o espaço de procura é exponencial mas tem um certo tipo de estrutura tem sido objecto de grande atenção em aprendizagem automática, sob o nome de structured prediction. Em determinadas situações, compensa estimar os parâmetros do modelo de forma discriminativa (em vez de generativa), o que resulta quase sempre num problema de optimização mais complicado. Este assunto (generative versus discriminative training) será objecto de um post futuro. Nesta linha, novos modelos para compressão de frases foram propostos por McDonald (2006), Clarke e Lapata (2008) e outros.

E isto é útil? E o que tem que ver com sumarização de documentos, afinal o tema que foi puxado em Babel.ZIP I? Bem... Isso é o que espero descobrir em breve. Estou a trabalhar num projecto de laboratório que visa combinar extracção das frases mais salientes de um documento com compressão de frases; o objectivo é, dado um documento, construir um sumário que, em vez de apenas extrair frases inteiras do documento, extrai e comprime ao mesmo tempo. Isso será feito num único passo, usando técnicas de structured prediction, programação linear inteira, etc.

More to come!

---

Knight, K. and Marcu, D. (2000). Statistics-based summarization - step one: Sentence compression. In AAAI/IAAI, pages 703-710.

Claude E. Shannon (1948). A Mathematical Theory of Communication, Bell System Technical Journal, Vol. 27, pp. 379–423, 623–656, 1948.

R. McDonald (2006). Discriminative Sentence Compression with Soft Syntactic Constraints.

European Association for Computational Linguistics (EACL).

Clarke, J. and Lapata, M. (2008). Global inference for sentence compression: An integer linear programming approach. Journal of Artificial Intelligence Research, 31:399-429.