[Algoritmo] [PLN#7] Entenda como funciona o algoritmo de Pos-Tagging



Análise morfológica 

Este tipo de análise é necessário para que o tamanho do dicionário não fique muito extenso, uma vez que é mais simples o armazenamento do radical da palavra  e seus afixos. Estes são os componentes que formam uma palavra juntamente como radical, como prefixos e sufixos. Um exemplo de prefixo é des na palavra desesperança e de sufixo é mos na palavra calamos.

O tratamento computacional deste tipo de análise é relativamente simples. Baseia-se em regras que analisam as palavras e as classificam segundo tabelas de afixos. Por emplo, a entrada zinho de uma tabela de sufixo está associada a um diminutivo de um substantivo, portanto, a palavra bonezinho é o diminutivo da palavra boné que é seu radical. Desta forma, são reconhecida as palavras que não estão na sua forma padrão, já adequando-as para a fase posterior de análise sintática. 

Jurafsky e Martin chamam o sistema que realiza a passagem da palavra escrita para a forma classificada de Conversor de Estados Finitos (Finit-state Transducer - FST). Este tipo de sistema é o que passa uma palavra de sua forma como é normalmente escrita para uma forma etiquetada, ou seja, com identificação de seu radical e afixo.


Análise sintática

No contexto do processamento da linguagem, as gramáticas utilizadas na análise sintática têm sido chamada de Modelos de Linguagem (Language Models - LM). Esta definição está associada ao amplo universo de frases possíveis de serem modeladas para representação de determinado domínio de análise. No seguimento, serão abordadas algumas técnicas utilizadas no identificação e etiquetagem dos elementos sintáticos e na organização da construção sintática. 


Etiquetagem 

O primeiro processamento que é efetuado na análise sintática é a identificação das classes das palavras (também conhecidas como classes morfológicas, etiquetas lexicais ou partes de fala). Para proceder esta classificação, são implementados parser que identificam nas frases as classes das palavras que as compõem. Esta classificação de palavras também é conhecida como etiquetagem (tagging). Por exemplo, frase Eu tropecei na pedra, poderia ser etiquetada da seguinte forma: Eu / PPE tropecei/ VP na PAF pedra /SSF. Onde PPE - Pronome pessoal, VP - Verbo no Passado, PAF - Preposição + artigo feminino, SSF - Substantivo Singular Feminino.

Basicamente, a etiquetagem dos atuais parsers sintáticos que vem sendo implementados constituem-se de três tipos: os que usam regras, os que utilizam estatísticas e híbridos que utilizam as duas anteriores.  A primeira, utiliza regras, também chamada de lexicalista, uma vez que ela se preocupa em seguir regras de dicionário e de gramáticas para verificação da consistência da linguagem.
A segunda abordagem chama-se probabilística, uma vez que utiliza cadeias de Markov para descobrir qual é a sequência mais provável de palavras. Dentro deste contexto, a técnica que tem sido mais utilizada em parsers sintáticos probabilísticos é chamada de n-gramas, que consiste me estabelecer uma estatística a cada n palavras. Normalmente é implementado n = 3, sendo que são analisadas 2 palavras para previsão da terceira. Desta forma, é estabelecida uma esta estatística de construção de frases permitindo a descoberta de qual é palavra de combinação mais provável permitindo a verificação e correção da construção frasal. 

A última abordagem é chamada de funcionalista e reúne tanto características referentes ao uso de regras, quanto ao uso de probabilidades. Uma das técnicas mais utilizadas é conhecida como Transformation-Based Learning (TBL), ou Aprendizado Baseado em Transformação, que faz a indução de regras a partir de exemplos de palavras apresentadas. Baseando-se em regras básicas, procura-se inferir a categoria de construção das frases dadas para o aprendizados. Sobre este aprendizado, são construídas estatísticas que podem dar origem  a novas regras de construção de frases não previstas no modelo básico.

A etiquetagem das palavras, contudo, não basta para análise sintática. Por vezes ocorre situações ambíguas onde é necessário recorrer-se a mais um nível, uma vez que , dependendo onde se encontra a palavra na frase, ela pode ter a função de advérbio ou de substantivo (ex : Branco), de verbo ou conjunção (ex: como), e  assim por diante. O próximo passo, portanto, é a análise da construção gramatical da frase para a definição da categoria sintática. 

Construção gramatical

Após a etiquetagem, passa-se à verificação da construção gramatical da frase. Para tanto, a linguagem é modelada por gramáticas livres de contexto, que divida as frases em árvores de sintagmas nominal e verbal e, a partir daí, verifica que a classe enquadra-se em cada sintagma. Nesse sentido, há duas correntes de desenvolvimento: a construção de árvores de parser e de parsers probabilísticos. 

Árvores de parser

Árvores de utilizam técnicas de busca em árvore para determinar a correção da construção frasal, realizando a comparação entre a frase e a estrutura da árvore. Uma técnica bastante difundida que busca realizando a comparação entre a frase e a estrutura da árvore. Uma técnica bastante difundida que busca resolver os problemas de busca em árvore é o algoritmo de Earley, que baseia-se na transição de estados para estabelecer qual é a classe mais provável de ser seguirá à classe atual. Este algoritmo possui 3 operadores: predictor, scanner e completor. O primeiro estabelece as transições de estado possíveis, o segundo realiza a comparação entre as transições possíveis e a palavra em análise, e o terceiro módulo realiza o registro final da classe na frase etiquetada. O maior problema deste tipo de parser é a incapacidade de resolver casos de ambiguidade.

Algoritmo de Earley

O algoritmo de Earley realiza uma busca top-down numa gramática estruturada em árvore. Ele começa com a varredura de um vetor chamado mapa (chart), contendo tantos elementos quantos forem as palavras da frase em análise. Cada uma destas entradas do vetor contém uma lista de estados gerados pelo paring até aquela palavra. A lista de estados gerados é composta de uma subárvore que representa uma regra gramatical, de informação sobre o preenchimento da subárvore (regras satisfeitas) e da posição na subárvore de acordo com a palavra do mapa (vetor).

Neste contexto, o operador predictor e que cria a subárvore a partir da regra gramatical. Ele aloca as folhas na árvore para estados não-terminais da gramática. O operador scanner verifica qual das ramificações geradas é compatível coma palavra em análise, gera uma nova folha e marca no mapa o atual estado da busca. Por fim, o operador completer é necessário quando uma regra terminou de ser avaliada e deve-se realizar o retrocesso (backtracking) para concluir a avaliação das demais ramificações da árvore. 


O parsing probabilístico

O parsing probabilístico utiliza uma gramática cujas entradas possuem ponderações estatísticas (pesos). Estas ponderações estão colocadas com base na observação da probabilidade de ocorrência das regras gramaticais no corpus (base de palavras). Através destes pesos é possível a resolução de ambiguidades, sendo indicadas as frases de maior probabilidade.

Assim, a probabilidade de uma regra R não terminal ( a → b ou a) ocorrer numa frase F é a divisão do número de ocorrências de R na aaliação de F pelo número de repetições de símbolo avaliado(a):

E a probabilidade de uma árvore de parser A para o cálculo da melhor F é o produto de todas as regras envolvidas na construção de A:


A partir destas equações é possível saber se as regras usadas para a construção de uma árvore é mais adequada que outra. Isto resolve grande parte dos problemas de ambiguidade nos casos de palavras que podem pertencer a mais de uma classe. 
Um dos algoritmos empregados para a execução deste tipo de parsing é o Earley probabilístico, que segue o mesmo algoritmo analisando na seção anterior, acrescido dos valores de probabilidades das regras, o que permite a desambiguação. 
O maior problema do parser probabilistico é a colocação de pesos iguais a construções frasais diferentes, embora com as mesmas palavras (ex: eu tropecei na pedra poderia ter iigual peso de tropecei na pedra eu). A solução para este caso na utilização de indicadores lexicais (lexical heads), que permite ao algoritmo de busca identificar diferentes ramificações dos sintagmas.

Os indicadores lexicais são palavras que ficam junto das raízes de uma determinada subárvore de parsing. Isso serve para indicar a palavra principal de uma parte da frase (o sujeito num  sintagma nominal, por exemplo) e alterar o peso de construções frasais que poderiam ter pesos iguais. 

Análise Semântica

apesar do extenso processamento realizado nas análise morfológica e sintática, apenas com estas não é possível distinguir certas categorias de palavras e muito menos precisar o objetivo da frase. Para tanto, não acrescentadas nas árvores de parser os chamados anexos semânticos (semantic attachments). Este tipo de análise semântica tradicional pode ser construído ainda em tempo de análise sintática, à medida que a árvore de parser vai sendo completada.

O anexo semântico apresentado na árvore é uma composição de uma rede semântica onde é definido o verbo tropeçar. A definição que este verbo necessita de um agente (aquele que tropeça) e um paciente (algo em que o agente tropeça).
Por outro lado, há poucas formas de análise semântica: gramáticas semânticas (semantic grammar), gramáticas baseadas em caso (case-based grammars) e outros métodos para casos específicos. 


Gramáticas Semânticas

As gramáticass tradicionais são utilização apneas para definir regras de sintaxe. Por outro lado, podem ser defiicdas regras associadas a frases-padrão, onde variam as palavras envolvidas. É uma forma viável quando existe uma hierarquia de diferentes contextos e necessita-se diferencia-los através de padrões. Infelizmente, para cada frase analisada, é necessária uma regra distinta dificultando sua utilização em diferentes domínios do conhecimento.

A construção de gramática semânticas baseia-se na colocação de variáveis que serão preenchidas de acordo com a afirmação ou questionamento do usuário ao sistema. Um exemplo de regras de uma gramática semântica.




Poderia ser:

Questão → quem tropeçou ONDE
Resp_Quest → QUEM tropeçou ONDE
QUEM → eu
ONDE → PREPOSIÇÃO LUGAR
PREPOSIÇÃO → na
LUGAR → pedra

Caso fosse questionado quem tropecou na pedra?, a resposta seria eu trpeçou na pedra, pela associação da expressão na pedra com variável ONDE e o pronome eu com a variável QUEM.


Agradecimentos a Daniel Nehmer Muller e seu trabalho que pode ser encontrado aqui.


Exemplo prático utilizando o Stanford parser

Como já foi dito anteriormente  o POS-tagging é um algoritmo bastante genérico e pode ser utilizado em muitas partes do Processamento de Linguagem Natural. Este algoritmo utiliza as regras linguísticas para classificar as partes de uma sentença. Como resultado final o algoritmo constrói uma árvore onde cada palavra é classificada com uma TAG. 

As tags utilizadas variam de acordo com a língua utilizada. Na língua inglesa veja algumas possíveis tags:

CC Coordinating conjunction
CD Cardinal number
DT Determiner
EX Existential there
FW Foreign word
IN Preposition or subordinating conjunction
JJ Adjective
JJR Adjective, comparative
JJS Adjective, superlative
LS List item marker
MD Modal
NN Noun, singular or mass
NNS Noun, plural
NNP Proper noun, singular
NNPS Proper noun, plural
PDT Predeterminer
POS Possessive ending
PRP Personal pronoun
PRP$ Possessive pronoun
RB Adverb
RBR Adverb, comparative
RBS Adverb, superlative
RP Particle
SYM Symbol
TO to
UH Interjection
VB Verb, base form
VBD Verb, past tense
VBG Verb, gerund or present participle
VBN Verb, past participle
VBP Verb, non­3rd person singular present
VBZ Verb, 3rd person singular present


Existem algumas ferramentas construídas capazes de realizar esta tarefa. Neste artigo iremos destacar uma delas que é o  Stanford Parser. O Stanford Parser já foi testado diversas vezes e muitos trabalhos já utilizaram esta ferramenta para construção de outras aplicações de PLN. Ele é implementado em Java e atualmente está disponível para diversas línguas, dentre elas o Inglês, chinês, alemão, entre outras.

Veja um exemplo de como utilizar o Stanford Parser para realizar o POS-tagging: 

package Modules.TextMiner;

import Model.Text;
import Model.Phrase;
import edu.stanford.nlp.simple.Document;
import edu.stanford.nlp.simple.Sentence;
import edu.stanford.nlp.trees.Tree;
import java.util.ArrayList;
import java.util.List;


public class PosTagger {
    
    private Text text;

        public PosTagger(String textToConvert){
        text = parseText(textToConvert);
    }

    public PosTagger() {
    }
    
    public Text parseText(String textToConvert) {
        Text text = new Text();
        Phrase phrase = new Phrase();
        Document doc = new Document(textToConvert);
        for (Sentence sent : doc.sentences()) {
            Tree t = sent.parse();
            phrase.setOriginalPhrase(t);
            text.addPhrase(phrase);
        }
        return text;

    }



    private ArrayList<Tree> extractNouns(Tree node) {
        
        ArrayList<Tree> nounList = new ArrayList<>();
        
        for (Tree subtree : node) {
            if (subtree.label().value().equals("NN")) {
                nounList.add(subtree);
            }
        }
        
        return nounList;
    }
    
    private ArrayList<Tree> extractVerbs(Tree node) {
        
        ArrayList<Tree> verbsList = new ArrayList<>();
        
        for (Tree subtree : node) {
            if (subtree.label().value().equals("VB")) {
                verbsList.add(subtree);
            }
        }
        
        return verbsList;
    }

    public Text getText() {
        return text;
    }

    public void setText(Text text) {
        this.text = text;
    }
}



Outros algoritmos e outras classes referenciadas neste código pode ser encontrada no nosso github.

Clique na imagem abaixo para acessar



[Algoritmo] [PLN#7] Entenda como funciona o algoritmo de Pos-Tagging [Algoritmo] [PLN#7] Entenda como funciona o algoritmo de Pos-Tagging Reviewed by Vinicius dos Santos on 14:58:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!