| Nome | Resumo |
| Michelle Kaori Hamada | Casamento aproximado entre strings e Semântica e similaridade de palavras - Parte I foram o tema da aula desta terça (02/07). Iniciamos realizando uma atividade em que consistia em indicar no contexto de similaridade entre palavras qual era a palavra mais próxima para cada uma, para Mario entre Marie, Maria e Maryo e para EDU entre DUDU, EIDU e EDUARDO. Deveríamos também explicar o que é Homógrafo, Homófono e um tesauro. Para realizar o casamento aproximado entre strings utilizamos algoritmos de string matching. Pode-se aplicar esses algoritmos em diversos contextos como de correção ortográfica (qual palavra é a mais próxima do desejado), biologia computacional (alinhar sequências de aminoácidos). Dentro dos algoritmos de string matching podemos aplicar a distância de Hamming, que calcula a quantidade de bits usado na mudança de uma transmissão para recepção, ele é muito utilizado para detectar erros nas transmissões binárias de comprimento fixo, ou seja, se aplicarmos hamming em PLN e PNL a distância é 2. Outra forma de medir a distância pode ser por meio da distância de Levenshtein que mede a quantidade de diferenças entre duas strings utilizando de operações como inserção, exclusão e substituição ele determina a quantidade mínima de edições para transformar uma string em outra, como exemplo a distância de Levenshtein para casa e data é 2, uma vez que é necessário pelo menos 2 edições para a conversão de casa para data, substituímos c por d e s por t. Explicando melhor como funciona a distância de Levenshtein, seja a e b duas strings e i e j o comprimento dessas duas strings, respectivamente. Se o comprimento de uma string for zero, então a distância será o comprimento da outra string, caso contrário realizamos o cálculo da distância de Levenshtein por meio do melhor valor que seria o menor valor calculado para o melhor caminho na comparação dentro do algoritmo. A desvantagem de Levenshtein é que a sua complexidade é muito alta mesmo para comparação entre duas strings que é o caso mais simples. Para calcular a distância podemos ter como peso +1 para inserção, +1 para eliminação e substituição +2 (ao se realizar uma substituição é preciso realizar pelo menos uma eliminação e uma inserção). Então para o exercício dado em aula para a similaridade entre palavras para Mario todas as palavras dadas seriam próximas, em todos os casos teríamos de diferença 2. Para a palavra EDU o mais semelhante seria o EIDU em que teríamos de realizar apenas uma eliminação, para DUDU seria necessário uma eliminação e uma substituição resultando em 3 enquanto que para eduardo seria necessário a inserção de quatro letras tendo então a distância valendo 4. A segunda parte da aula, seguindo o livro Speech and Language Processing de Dan Jurafsky and James H. Martin é o capítulo 6 é a parte de semântica e similaridade de palavras. Vimos cinco definições importantes, para entrarmos no contexto retomamos a aula 04 sobre Stemming (stem - parte de uma palavra; stemmer - o programa) e Lemmatization (lemma - forma básica da palavra; lemmatizer - o programa). Para compararmos Lemma e Wordform, enquanto um é a forma básica da palavra, ou seja, sem inflexão, o outro é uma palavra com inflexão. Um lemma pode pode ter significado diferente, ou seja, ser um homônimo. Homônimos são palavras que compartilham a mesma forma mas com significados diferentes (origens diferentes). Por exemplo, a palavra banco dependendo do contexto ele pode significar uma instituição financeira, ou uma ferramenta para armazenamento de dados ou um assento. Dentro de homônimos temos outras duas classificações: Homógrafos (mesma forma de escrita) e Homófonos (mesma fonética). Elas criam problemas para recuperação de informação (banco quebrado, seria a instituição ou o assento?), para tradução de textos (bat, em português pode significar morcego ou bastão e também para aplicações text-to-speech em que a pronúncia é diferente (bass de instrumento musical ou de peixe). Um dos conceitos é a polissemia que ocorre quando uma palavra apresenta vários significados relacionados (origens similares - Letra pode ser um elemento básico de um alfabeto, texto de uma canção ou a caligrafia de um determinado indivíduo) e são sistemáticos, funcionam como metonímia. Para determinar se uma palavra tem mais de um significado usamos o teste Zeugma, uma figura de linguagem, se a construção não faz sentido, provavelmente a palavra seja polissêmica. O conceito seguinte são os sinônimos que são as palavras que têm o mesmo significado em alguns ou todos os contextos. Para que duas palavra sejam sinônimas elas podem ser substituídas em todas as situações e têm o mesmo significado proposicional. Existem também os antônimos que são palavras que têm significados opostos em relação a uma característica (escuro - claro, quente - frio). O último conceito é o de hiponímia e hiperonímia, estas indicam relação hierárquica de significados entre palavras. Uma palavra é hiponímia de outra, quer dizer que o significado de uma é mais específico que da outra, enquanto que o inverso é o hiperonímia da outra, respectivamente, carro é uma hiponímia de automóvel e automóvel é hiperonímia de carro. Existe uma base de dados usada na área de linguística computacional organizado em base de relações usado para desambiguar o significado das palavras chamada Wordnet. Ele é um tesauro, um repositório/dicionário de ideias comuns. Para dizermos se duas palavras são similares elas mantêm uma relação de significado, isso é importante em diversos tipos de aplicações como recuperação de informação (busca por elementos similares), detecção de plágio (busca por regiões similares) ou de agrupamento de textos (busca por conjuntos de textos similares). Outra forma de estimar a similaridade entre palavras pode ser estimada medida de proximidade de significado. Duas das abordagens para identificar similaridade entre palavras são os algoritmos baseados em tesauros ou os baseados em distribuição de palavras. No primeiro, utiliza-se de path based similarity, onde duas palavras são similares se uma é hiponímia de outra ou se compartilham a mesma definição, ou seja, se ambas estão na mesma hierarquia ou bem próximas (distância do menor caminho entre eles). O problema dessa abordagem são que os vértices em hierarquias superiores são mais abstratos e as palavras conectadas por estes deveriam ser menos similares e de que também deveria ser possível representar o custo de cada aresta de forma independente. Para solucionar este problema pode-se utilizar um corpus para captar de uma forma melhor a distância entre dois conceitos ou duas palavras, existem interfaces para auxiliar nesse processo seja o NLTK ou iniciativas online. A segunda abordagem, necessita de um corpus grande no qual sejam evidenciados diferentes pares de palavras. Essa abordagem é útil pois diferente da métrica apresentada anteriormente ela não depende de um tesauro ou da completude das palavras, além de que no tesauro existem relações que não estão representadas (adjetivos e verbos), um dos motivos é devido a semântica que está em constante mudança. Em PLN, geralmente palavras que estão em contextos similares, tendem a ser semanticamente similares, isso é conhecido como distributional semantics ou vector semantics, em que o significado de uma palavra e calculada a partir da distribuição de palavras que estão ao redor dela, assim duas palavras são similares se ambas estão em contextos similares. Desse modo, as palavras passam a ser representadas como um vetor de números, e assim podemos comparar duas palavras ou também dois documentos, estes serão similares se os vetores são similares, formando assim a matriz: termo-documento. |
| Mauro Mascarenhas de Araujo | Aula de 01/07: "Casamento aproximado entre strings e Semântica e similaridade de palavras - Parte I". A aula iniciou-se com um teste, cuja primeira pergunta perguntava à qual palavra Mario era mais próximo: Marie, Maria e Maryo. Bom, neste caso, todas as alternativas são válidas, uma vez que, apenas um dos caracteres foi alterado. Já na segunda pergunta, a palavra dada era EDU, e as alternativas eram DUDU, EIDU e EDUARDO. Neste caso, a palavra que mais se qualificava era EIDU, uma vez que há apenas a inserção de apenas um caractere. Por fim, foram pedidas as definições de Homógrafo, Homófono e Tesauro. Homógrafo são palavras que têm a mesma escrita e mesma pronúncia, Homófono são palavras que têm a mesma pronúncia, mas escrita diferente e, Tesauro é uma lista com significados semelhantes, dentro de um domínio específico de conhecimentos (também chamado de dicionário de sinônimos). Já na parte teórica, começou-se com Casamento aproximado entre strings, onde, em um exmeplo de contexto de correção ortográfica, perguntou-se se "Graffe" estava mais próximo a Graf, Graft, Grail ou Giraffe. Neste caso, a resposta seria a última alternativa, Giraffe, uma vez que apenas uma letra foi removida. Também foi apresentado uma aplicação de alinhamento de sequências de aminoácidos, no contexto de biologia computacional. Um dos métodos para analisar a diferença entre duas palavras é a distância de Hamming que é a quantidade de bits usado na mudança de uma transmissão para a recepção, onde, embora seja utilizado para detectar erros nas transmissões binárias de comprimento fixo, pode ter seu conceito aplicado à strings. Logo após foi apresentada a implementação em Python da distância de Hamming para a análise de strings. Outro método apresentado foi a Distância de Levenshtein, que por definição já é usada para medir a quantidade de diferenças entre duas strings. Ela usa as operações de inclusão, inserção e substituição como ponderação para definir a distância entre duas strings. Esta distância define o número mínimo de edições para transformar uma string em outra. Em "casa" e "pata", por exemplo, a distância de Levenshtein é 2, pois, não há maneira de o fazer com menos de 2 edições, onde a conversão de casa para pata é obtida substituindo-se c por p, logo substituindo-se s por t. Logo a seguir foi apresentada a "função" para a realização do cálculo da distância de Levenshtein e sua respectiva implementação em Python. Em seguida foram mostradas as análises da distância de Levenshtein para as palavras "Mario" e "Marie", "Mario" e "Marie" e "Maria" e "Maryo" com pesos +1 para inserção e eliminação e +2 para substituição. Neste caso, todos deram iguais. Já no caso de "EDU" com "DUDU", "EDU" com "EIDU" e "EDU" com "EDUARDO", o segundo caso obteve a menor distância, enquanto o último, a maior. Por fim, foi apresentado um site que tem a ferramenta de cálculo da distância implementado. A seguir foram relembradas as diferenças entre "Stemming" (ação de reduzir em parte de uma palavra) e "Lemmatization" (a ação de reduzir em forma básica da palavra). Também foi mostrado que um mesmo Lemma pode apresentar significados diferentes, como a palavra "banco", que pode representar uma instituição financeira, um artefato ou ainda um assento, este é um caso de Homônimo, que são palavras que compartilham a mesma forma mas com significados diferentes (podem ser Homógrafos ou Homófonos), criando problemas na recuperação da informação, tradução de textos e em aplicações text-to-speak em PLN. Foi apresentado a definição de Polissemia, que é propriedade de uma palavra tem de apresentar vários significados, sendo sistemáticos, onde os exemplos foram "Letra" que pode ser o elemento básico de um alfabeto, texto de uma canção ou a caligrafia de um determinado indivíduo, e "vela" que pode ser de um barco, para iluminar ou de vigilante. Usando o teste de "Zeugma" é possível determinar se uma palavra tem mais de um significado. Também foi apresentado a definição de Sinônimos que são palavras que tem o mesmosignificado em alguns ou todos os contextos. Duas palavras são sinônimas se: Ambas podem ser substituídas em todas as situações.Ambas têm o mesmo significado proposicional. A definição de Antônimos que são palavras que tem significado oposto em relação a uma característica. Por fim, o significado de Hiponímia e Hiperonímia que indicam relação hierarquica de significados entre palavras. Uma palavra A é hiponímia de B, se o significado de A é mais específico que B (o inverso é a Hiperonímia). Foi apresentado o Wordnet, que é uma base de dados (1985) usada na área de linguística computacional, em inglês. Outra aplicação é a similaridade de palavras, onde são similares se ambas compartilham o mesmo significado, mantendo uma relação de significado, um exemplo é "Banco" e "Fundo", "Caderno" e "Caderneta". Ela é importante para recuperação de informação, detecção de plágio e agrupamentos de textos, por exemplo. Uma versão mais flexível de similaridade pode ser estimadada por uma medida de proximidade de significado: quase sinônimos, como em "Carro" e "Bicicleta". Um dos algoritmos que podem ser implementados são os baseados em tesauros, onde palavras são similares se uma é hiponímia de outra ou se compartilham a mesma definição. Outra possibilidade são os baseados em distribuição de palavras, que não precisam de um tesauro, mas de um corpus grande no qual sejam evidenciados diferentes pares de palavras, sendo mais flexíveis já que no tesauro algumas relações não estão representadas e a semântica das palavras mudam ao longo do tempo, além de que adjetivos e verbos são menos representados nos tesauros. Em PLN, palavras que estão em contextos similares, tendem a ser semanticamente similares, onde na literatura são conhecidas como distributional semantics e vector semantics. Em algoritmos baseados em distribuição, o significado de uma palavra é calculada a partir da distribuição de palavras que estão ao redor dela, sendo que as palavras são representadas como um vetor de números. Um exemplo dado foi um curpus cuja palavra tesgüino estava presente e, mesmo não sabendo o significado da palavra, foi possível identificar que tratava-se de uma bebida alcoólica. Por fim foi apresentada a matriz termo-documento, que compara as frequências de palavras em diferentes obras. Cem ela é possível comparar a proximidade entre obras, ao comparar as colunas da matriz, e comparar a proximidade de significados ao comparar as linhas. |
| Rodrigo Hiroaki Ideyama | Nome: Rodrigo Hiroaki Ideyama RA: 11042714 Resumo PLN 8 O tema da aula de número oito foi: Casamento aproximado entre Strings e Semântica e similaridade de palavras - Parte I. De início, o Jesús mostrou em diferentes contextos que verifica o matching entre Strings, no caso foi no contexto de biologia computacional e correção ortográfica. Para explicar melhor o casamento aproximado entre strings, ele explicou dois métodos de medição de similaridade entre as palavras: distância de Hamming e distância de Levenshtein. Distância de Hamming é a quantidade mínima de bits que diferem entre si quaisquer duas palavras do código. Ela é calculada quando uma palavra de código chega ao receptor e esta é comparada com todas as palavras presentes na tabela de descodificação. Por exemplo, se recebermos o código 01 e formos comparar com a codificação binária de dois bits, teremos as seguintes distâncias de Hamming: * 00\. Instrução: Estude pouco. Distância = 1 * 01\. Instrução = Estude bastante que ganhará carta de recomendação. Distância = 0 * 10\. Instrução = Não estude. Distância = 2 * 11\. Instrução = Estude pouco. Distância = 1 A instrução originalmente transmitida é aquela que tem a menor distância de Hamming da palavra recebida com erro, isto é, é mais semelhante com a palavra recebida. Então o decodificador (aluno) infere que a palavra originalmente transmitida é 01, pois apresentou menor distância de Hamming. Já a distância de Levenshtein, também conhecida como distância de edição, entre duas strings é dada pelo número mínimo de operações necessárias para transformar uma string em outra, sendo que essas operações podem ser a inserção, eliminação ou substituição de um caráter. Ao executar essa transformação em cada item da lista no termo informado, a palavra mais parecida é a que tem a menor distância de Levenshtein. Como exemplo, a atividade que o professor passou na aula, um dos exercícios pedia qual era a palavra mais próxima de EDU, tendo como alternativas DUDU, EIDU e EDUARDO. A distância de Levenshtein é calculada com base nos seguintes pesos: se for inserção, +1, eliminação, +1, e substituição, +2. Aplicando essas regras, temos os seguintes resultados: * DUDU. Distância de Levenshtein = 10 * EIDU. Distância de Levenshtein = 3 * EDUARDO. Distância de Levenshtein = 10 Logo, podemos concluir que o EIDU chega a ser a palavra mais próxima de EDU. No tópico seguinte, cinco definições importantes sobre significado de palavras, o Jesús, primeiramente, revisou sobre Stemming e Lemmatization. Técnicas mais importantes para a redução ou simplificação de palavras que esse processo pode ser chamado de normalização de palavras. O Stemming consiste em reduzir a palavra à sua raiz (sem levar em conta a classe gramatical), como exemplo, alun. Já o lemmatization, consiste aplicar umas técnicas para deflexionar as palavras (retira a conjunção verbal, caso seja um verbo, e altera os substantivos e os adjetivos para o singular masculino, de maneira a reduzir a palavra até sua forma dicionário), como exemplo, ser. Em seguida, ele citou qual é o capítulo da bibliografia que foi discutido na aula, sendo o livro Speech and language processing: An introduction to natural language processing, computational linguistics, and speech recognition da editora Pearson/Prentice Hall dos autores Daniel Jurafsky & James H. Martin e o capítulo seis como título vetor semântico. Após a revisão das técnicas, ele explicou as cinco definições, sendo elas: 1. Homônimos: são palavras que compartilham a mesma forma, porém com significados diferentes (origens diferentes). Ele pode ser dividido em dois tipos de categorias: * Homógrafos: mesma forma de escrita. Por exemplo: banco pode ser instituição financeira, ferramenta para armazenamento de dados e objeto para assento. * Homófonos: mesma forma de fala. Por exemplo: concerto que significa como tipo de atração musical e conserto, tarefa que procura fazer reparação de algo que quebrou ou inutilizável. Eles criam problemas em algumas aplicações de processamento de linguagem natural, como em recuperação de informação, em tradução de textos, em aplicações text-to-speech. 2. Polissemia (vários significados): é a propriedade de uma palavra tem de apresentar muitos significados. Uma palavra polissêmica tem significados relacionados (origens similares). Como exemplo, a palavra letra dada em aula, ela pode significar elemento básico de um alfabeto, texto de uma canção, caligrafia de um determinado indivíduo. Pode ser sistemática, por exemplo: eu amo Cacau Show ? eu amo ( os chocolates da) Cacau Show. 3. Sinônimos: palavras que têm o mesmo significado em alguns ou todos os contextos, devem respeitar as seguintes condições: ambas podem ser substituídas em todas as situações e ambas têm o mesmo significado proposicional. Como exemplo, reparação e restauração. 4. Antônimos: palavras que têm significado oposto em relação a uma característica. Por exemplo, rápido e lento no sentido de velocidade. 5. Hiponímia e hiperonímia: indicam relação hierárquica de significados entre palavras. Por exemplo: uma palavra A é hiponímia de B, se o significado de A é mais específico que B, carro é uma hiponímia de automóvel. De modo inverso, automóvel é uma hiperonímia de carro. Como próximo conteúdo, a fim de explicar o último exercício da atividade passada no início da aula, ele explicou sobre wordnet, repositório (tesauro) muito útil em processamento de linguagem natural. Wordnet é um grande banco de dados léxico em inglês que possui agrupamentos de sinônimos de substantivos, adjetivos, verbos e advérbios, muito utilizado para desambiguar o significado das palavras e está organizado em base de relações (hierárquicas). É um tesauro, isto é, um dicionário de ideias comuns. No tópico seguinte, o professor falou que similaridade de palavras é quando duas palavras compartilham o mesmo significado, tendo importância nas seguintes aplicações: recuperação de informação, detecção de plágio e agrupamento de textos. A fim de conseguir identificar essas similaridades, dois algoritmos podem ser utilizados para realizar a medição: 1. Algoritmos baseados em tesauro: duas palavras são similares se uma é hiponímia de outra ou se compartilham a mesma definição. 2. Algoritmos baseados em distribuição de palavras: não precisam de um tesauro, mas de um corpus grande no qual sejam evidenciados diferentes pares de palavras |
| Renato de Avila Lopes | Casamento aproximado entre strings String matching Graffe é mais próximo a Giraffe no contexto de correção ortográfica Pode ser usado para alinhar sequências de aminoácidos Distância de Hamming detecta erros nas transmissões binárias de comprimento fixo Quantidade de bits usados na mudança de uma transmissão para recepção Distância de Levenshtein mede a quantidade de diferenças entre duas strings Esta diferença define o número mínimo de edições para transformar uma string em outra Utiliza operações (inserção, exclusão e substituição) Casa e pata distância 2 (não há maneira de fazer com menos) Substitui-se c por p e s por t String com zero de comprimento, distância será o comprimento da outra string Algoritmo de Levenshtein é muito custoso computacionalmente Sua estrutura recursiva gera muita redundância Atividade utilizando distância de Levenshtein Pesos inserção 1 eliminação 1 substituição 2 Mario está a mesma distância de Marie, Maria e Maryo Foneticamente está mais próximo de Maryo EDU está mais próximo de EIDU com distância 1 DUDU tem distância 3 e EDUARDO 4 Levenshtein Demo http://www.let.rug.nl/kleiweg/lev/ Revisão Stemming reduzir em parte de uma palavra (stem) Stemmer artefato (programa) Lemmatisation reduzir a forma básica da palavra (Lemmas) Lemmatizer artefato (programa) Wordform é uma palavra com inflexão (Lemma não possui inflexão) Banks Bank Dormiu dormir Um determinado Lemma pode ter significados diferentes Homônimos compartilham a mesma forma com significados diferente (origens diferentes) Banco instituição financeira = artefato para armazenamento de dados = assento Homógrafos mesma forma de escrita Homófonos mesma forma de fala (Concerto / Conserto) Homônimos criam problemas em PLN em recuperação de informação, tradução de textos (bat morcego e bat bastão), em aplicações text-to-speech (pronúncia diferente bass instrumento bass peixe) Polissemia vários significados (relacionado - origens similares) Letra elemento básico de um alfabeto Texto de uma canção Caligrafia de um individuo Vela De um barco Para iluminar De vigilante Metonímia Polissemia sistemática Rádio Universidade Escola Hospital = Prédio ou Organização Autor / Trabalho de autor Como determinar se uma palavra tem mais de um significado Zeugma (figura de linguagem ou estilo) construirá uma universidade de mármore pedirá à universidade de João construirá uma universidade de mármore e de João (não faz sentido, não é coerente) Sinônimos tem o mesmo significado em alguns ou todos os contextos Podem ser substituídas em todas situações e tem o mesmo significado proposicional Antônimos significado oposto em relação a uma característica Hiponímia (sub) e Hiperonímia (super) Indicam hierarquia de significados entre palavras (significado mais específico) Carro é hiponímia de Automóvel Calçado é hiperonímia de Sandália Wordnet (wordnet.princeton.edu) é um tesauro (dicionário de ideias comuns) Muito útil em PLN Base de dados (1985) usada na área de linguística computacional Organizado hierarquicamente Desambiguação de significados das palavras Synset Synonym set conjunto de sinônimos (próximos) a uma palavra (hierarquia de hiporonomios) OpenWN-PT em português Semântica e similaridade de palavras Palavras similares compartilham o mesmo significado Mantêm uma relação de significado Banco é similar a fundo Caderno é similar a caderneta Similaridade de palavras pode ser útil em diferentes tipos de aplicações Recuperação de informação (elementos similares) Detecção de plágio (regiões similares) Agrupamento de textos (conjunto de textos similares) Versão mais flexível Pode ser estimada por uma medida de proximidade de significados quase sinônimos Carro é similar a bicicleta Palavras correlatas Carro está relacionado com Gasolina Algoritmos Baseado em tesauro (hiponímia) ou compartilham a mesma definição Path based similarity Duas palavras são similares se estão na mesma hierarquia (ou próximas) Distância do menor caminho Pathlen (c1, c2) = 1 + comprimento do caminho ente c1 e c2 na árvore de hiponímia simpath (c1, c2) = 1 / pathlen (c1, c2) wordlen (w1, w2) = max simpath (c1, c2) Problema Assumindo que cada aresta representa distância uniforme os vértices em hierarquias superiores são mais abstratos (deveriam ser menos abstratos) Deveria ser possível representar o custo de cada aresta de forma independente Contornando o problema Utilizar um corpus para captar da melhor forma a distância entre dois conceitos ou palavras SIM resnik (c1, c2) = - log P (LCS (c1, c2) ) SIM lin (c1, c2) = 2 log P (LCS (c1, c2) ) / log P (c1) + log P(c2) SIM jiangconrath (c1, c2) = 1 / log P (c1) + log P (c2) - 2 log P (LCS (c1, c2)) SIM eLesk (c1, c2) = ? overlap ( gloss ( r(c1) ), gloss ( ( q(c2) ) ) ) Interfaces NLTK oferece métodos para cálculo de similaridade baseado em wordnet Algoritmo de similaridade baseado em distribuição de palavras Corpus grande no qual sejam evidenciados diferentes pares de palavras Porque? Métricas anteriores dependem deum tesauro Dependem da completude das palavras (dicionário) e não são flexíveis Tesauro não representa algumas relações Adjetivos e verbos são menos representados Semântica muda / evolui ao longo do tempo Em PLN palavras que estão em contextos similares tendem a ser semanticamente similares (obras em uma biblioteca) Distributional semantics / Vector semantics Significado calculado a partir da distribuição de palavras ao seu redor Vetor de números a bottle of tesgüino is on the table Evebody likes tesguino Tesgüino makes you drunk We make tesgüino out of corn Pelo contexto podemos intuir que tesgüino é uma bebida alcoólica, mas certamente Tesgüino não estará presente em nenhum tesauro Matriz termo documento Dois documentos são similares se os vetores são similares Colunas: A dimensão do vetor é o tamanho do vocabulário N^|V| Linhas: A dimensão do vetor é o número de documentos N^|D| |
| Jair Edipo Jeronimo | Quando estamos realizando o casamento aproximado entre strings, um dos fatores que devemos levar em consideração é o contexto em que a palavra se encontra. Uma das formas de identificar erros nas transmissões de informação é utilizar a distância de Hamming, que mede a quantidade de bits usado na mudança de uma transmissão para a recepção. No caso, para strings, podemos utilizar a distância de Levenstein, que mede a quantidade de diferenças entre duas strings, levando em consideração operações como inserção, exclusão e substituição, para transformar uma string em outra. Esse método leva a uma árvore de distâncias, tal que o cálculo da distância entre duas palavras de tamanho n, pode utilizar mais de uma vez o cálculo de palavras de tamanho n-1. Existem definições que temos que levar em consideração sobre o significado das palavras. Para isso, temos que considerar também os métodos de stemming (parte de uma palavra), lemmatization (forma básica da palavra), lemma (palavra sem inflexão) e wordform (palavra com inflexão). Além disso, temos que um determinado lemma pode conter diversos significados diferentes, por exemplo, a palavra manga pode significar uma fruta ou uma parte da nossa roupa. Dessa forma, os significados das palavras têm como influência cinco definições importantes: homônimos, polissemia, sinônimos, antônimos e hiponímia e hiperonímia. Os homônimos são palavras que possuem a mesma forma escrita ou falada, porém podem ter diferentes significados (como no exemplo da manga). Este aspecto cria vários problemas para o processamento, pois pode levar a interpretações erradas. Já a polissemia, representa a propriedade de uma palavra que tem diversos significados que estão relacionados, por exemplo, a palavra letra que pode significar o texto de uma canção ou o elemento básico do alfabeto, sendo que ambos se referem a mesma coisa. Para verificar se uma palavra possui mais de um significado, podemos aplicar o teste Zeugma, que consiste em juntar a aplicação da palavra em dois contextos e verificar se a construção possui um sentido, caso não haja a palavra é polissêmica. Sinônimos são palavras que possuem o mesmo significado em pelo menos um contexto. Assim, duas palavras são sinônimas se tem o mesmo significado e podem ser substituídas uma pela outra em qualquer situação. Os antônimos são palavras que possuem o significado oposto em relação a uma característica, por exemplo, a palavra rápido é o antônimo da palavra lento. Por fim, temos o conceito de hiponímia e hiperonímia, que tratam uma relação hierárquica entre palavras, de forma que se uma palavra A possui o significado mais específico que B, então A é chamada de hiponímia de B e B é chamado de hiperonímia de A. Uma base muito usada na área de linguística computacional é a Wordnet, ela serve para desambiguar o significado das palavras. Além disso, é denominada como um tesauro, ou seja, um dicionário de ideias comuns. O Wordnet também contém uma funcionalidade chamada de synset que forma uma hierarquia de sinônimos para uma palavra. Outro conceito importante é a similaridade entre palavras, onde duas palavras são consideradas similares se ambas compartilham o mesmo significado. Este conceito é importante para diversos tipos de aplicação, como recuperação de informação, detecção de plágio, buscas por elementos ou regiões similares, entre outras. Existem algoritmos que servem para identificar a similaridade entre palavras, como por exemplo, os baseados em tesauros que relacionam duas palavras como similares, se uma é hiponímia de outra ou se compartilham a mesma definição. Há também algoritmos baseados em distribuição de palavras, que se baseiam em um corpus grande com evidências de diferentes pares de palavras, não precisando de um tesauro. Um algoritmo baseado em tesauro é o path based similarity, que avalia a similaridade de duas palavras, levando em consideração se elas estão na mesma hierarquia e na distância entre elas. O problema desta abordagem é que cada aresta representa uma distância uniforme, o que pode não ser tão real. Uma forma de contornar este problema é ter como base um corpus para identificar de maneira prática a distância entre as palavras. O NTKL, por exemplo, fornece métodos de cálculo de similaridade de palavras baseada em wordnet. Entretanto, o uso de tesauros dificulta a análise de palavras flexionadas, além de que adjetivos e verbos possuem menor representação. Por outro lado, temos que considerar também que a similaridade pode depender do contexto, sendo que a semântica muda e com isso afeta também na similaridade. Desse modo, existe um cálculo em que o significado de uma palavra é baseado na distribuição de palavras ao redor dela, as representando como um vetor de números. Assim, dois documentos são similares se os vetores de palavras são similares. |
| Guilherme Beo Arqueiro | Na aula 8 de PLN, vimos o casamento aproximado entre strings e a parte introdutória de semântica e similaridade de palavras. O string matching, ou casamento de strings, é a aproximação de duas palavras, que pode ser usada para identificar e corrigir erros, por exemplo. A distância de Hamming é um conceito utilizado na detecção de erros nas transmissões binárias de comprimento fixo, sendo essa distância a quantidade de bits usado na mudança de uma transmissão para a sua recepção. A distância de Levenshtein é outro conceito, utilizado para medir a quantidade de diferenças entre duas strings, usando operações de inserção, exclusão e substituição, a distância métrica define o número mínimo de edições para transformar uma string em outra. Um exemplo de distância de Levenshtein é casa e pata, que possuem uma distância 2, pois não há maneira de fazer a correção com menos de duas edições, já que é necessário substituir c por p e depois s por t. Sendo a e b duas strings, e i e j o comprimento de a e b, a distância de Levenshtein é dada por leva,b(i,j), sendo que se o comprimento de uma string for zero, a distância será igual ao comprimento da outra string. O algoritmo de Levenshtein pode gerar alguns subproblemas de overlapping. Essa distância pode ser calculada com pesos em tabelas, onde é adicionado 1 custo 1 para inserção, custo 1 para eliminação e custo 2 para substituição, na diagonal da tabela com as palavras analisadas. Após esse tópico, entramos no capítulo 6 do livro seguido na disciplina, e revisamos algumas definições sobre significado de palavras, como o stemming (redução a stems), o lemmatization (redução a lemmas), o lemma (forma básica da palavra) e o wordform (palavra com inflexão). Verificamos que um determinado lemma pode ter diferentes significados, ou seja, homônimos, que são palavras que compartilham a mesma forma, mas possuem significados diferentes (banco de instituição financeira e banco de assento, por exemplo). Os homônimos podem ser homógrafos, com a mesma forma de escrita, e homófonos, com a mesma forma de fala. Os homônimos criam alguns problemas em PLN, como a recuperação da informação, em tradução de textos e em aplicações text-to-speech. Vimos também a polissemia, em que uma palavra pode apresentar vários significados, e alguns tipos de polissemia são sistemáticos (metonímia). É possível determinar se uma palavra tem mais de um significado ao utilizar o teste Zeugma, que implica em aplicar a palavra a uma frase e, caso a construção não seja coerente, é provável que a palavra seja polissêmica. Vimos também exemplos de sinônimos, que são palavras que possuem o mesmo significado em alguns ou todos os contextos, e podem ser substituídas em todas as situações com o mesmo significado proposicional. Antônimos são palavras com significado oposto em relação a uma característica. Hiponímia é uma relação em que a palavra A tem um significado mais específico que B, e hiperonímia é o inverso, onde B tem o significado mais específico que A. Também estudamos mais detalhes do wordnet, um tesauro usado na área de linguística para desambiguar o significado das palavras. Também vimos a Synset, com um conjunto de sinônimos de uma palavra. Vimos a importância de estudar a similaridade entre palavras, como aplicações em recuperação de informação, detecção de plágio e agrupamento de textos, além de ser possível identificar palavras correlatas que sejam quase sinônimos. Estudamos algoritmos para identificar similaridade entre palavras, como os algoritmos baseados em distribuição de palavras que precisa de um corpus grande, e algoritmo de similaridade utilizando tesauro, denominado de path based similarity, onde duas palavras são similares se estão na mesma hierarquia, com a medida formalizada por pathlen(c1, c2) = 1 + comprimento do caminho na árvore hiponímia, além de simpath(c1,c2) = 1/pathlen(c1,c2). Podemos usar um corpus para captar da melhor forma a distância entre 2 conceitos ou 2 palavras, e vimos interfaces com métodos para calcular a similaridade de palavras baseada em wordnet, como NLTK. Em algoritmos baseados em distribuição de palavras, vimos distributional semantics, em que uma palavra é calculada a partir da distribuição de palavras ao seu redor, como o exemplo que vimos de tesgüino. Por último, vimos a matriz termo-documento, que são documentos similares caso os vetores sejam similares, utilizado para agrupamento hierárquico e para capturar o significado relacional das palavras. |
| Elsio Antunes Junior | 01/0719 - Casamento aproximado entre strings; A aula começa com uma atividade questionando, na primeira questão, sobre a distância entre a palavra "Mario" e outras três similares "Maryo", "Marie" e "Maria"; Igualmente, na segunda questão, comparando a palavra "EDU" a "EiDu", "Dudu" e "Eduardo"; Claramente pondo em discussão sobre quais critérios devemos adotar para avaliar a proximidade entre duas strings; Passeando pelos corredores da sala o professor visualizou várias respostas, algumas levando em consideração as modificações necessárias de cada caractere e algumas levando a proximidade de significado e até variabilidade nominal (já que se tratavam de nomes próprios), entendendo, portanto, que se tratava de uma consideração semântica; A atividade também falava de dois tipos de homônimos (homógrafos e homófonos) e do significado de "tesauro"; A aula entra, então, no contexto de correção ortográfica onde uma nova comparação de palavras é feito; Após a menção de sequências de aminoácidos no contexto de biologia computacional, começamos a falar sobre distância de Hamming; Uma evolução dos algoritmos de paridade para checar a integridade de fluxos binários, hammim compara duas strings de mesmo tamanho e conta um por um, quantos caracteres da mesma posição são diferentes; No exemplo, as strings "UFABC" e "UFRRJ" tem distância 3 pois apenas 2 dos 5 caracteres são iguais e estão na mesma posição; Passamos agora a analisar a abordagem da 'distância de Levenshtein', onde o que conta são o número de inserções de caracteres, o número de deleções e o número de substituições; Levenshtein, portanto, mede a quantidade de diferenças entre duas strings; Vamos definir lev_ab(i,j) uma função recursiva agindo sobre duas strings a e b cujos tamanhos são passados pelos parâmetros i e j, temos que, o critério de parada é quando i ou j é zero, quando o retorno da função é max(i, j); aplica- se recursivamente lev_ab() aos pares (i-1,j), (i,j-1) e (i-1,j-1), retornando o menor valor; Ao minimizar estas chamadas temos como resultado o valor máximo obtido pelo número mínimo de operações; No entanto, como ocorre em alguns algoritmos recursivos, expande-se um certo número de ramos repetidos, o que faz deste um algoritmo de complexidade exponencial; A solução é guardar os resultados parciais calculados, caracterizando o que se conhece por 'programação dinâmica', que reduz a complexidade à O(i*j); (na verdade, não é o fato de guardar os cálculos que torna um algoritmo recursivo programação dinâmica, mas o fato de podermos organizar estes dados em uma tabela); O professor finaliza a primeira parte da aula apresentando ferramentas online para testar o algoritmo e um artigo que fala sobre string matching, além das implementações em python disponibilizados com os slides da aula; Segue-se com a segunda parte da aula que fala sobre 'vector semantics'; Depois de um pequeno lembrete de conceitos de aulas anteriores como Stemming, Lemmatization, lemma e wordform, o professor começa dizendo que cinco definições linguísticas precisam ser entendidas para prosseguir; Homônimos, polissemia, sinônimo, antônimo e hiponímia/hiperonímia; Homômimos: mesma forma e significados diferentes (ex banco, banco e banco; ponto e ponto; rosa e rosa), incluindo homógrafos e homófonos; polissemia: vários significados (ex ponto, vela, letra, incluindo a metonímia: varios significados sistemáticos: a rádio, o rádio, a Marechal (avenida), o marechal) e uma técnica para diferenciá-los chamada Zeugma; Sinônimos e antônimos que são auto explicativos; Hiponímia e hiperonímia que indicam uma relação de hierarquia entre as palavras que será útil nos nossos próximos conceitos; A é hiponímia de B se A é mais específico que B; Por ex: carro é um automóvel, sandália é um calçado - ambos, carro e sandália são hiponímias em relação a suas hiperonímias; A aula continua falando agora sobre tesauros; Tesauros são dicionários de ideias comuns; bases de dados usadas para desambiguar o significado das palavras; O professor deu como exemplo o Wordnet de princeton; A aula finaliza mostrando como obter dados de similaridade das palavras usando o tesauro a partir de navegações nas árvores de hierarquia das palavras e uma outra forma baseada apenas em distribuição de palavras; nos foi apresentado o conceito de matriz termo-documento onde se pode verificar a similaridade entre documentos e também entre as palavras neles contida e a construção de um agrupamento hierárquico; E chega né? 700 palavras dessa vez. E olha que eu tentei resumir. |
| Igor Neres Trindade | Na aula de hoje, 01/07/2019, nos aprofundamos um pouco mais na classificação e processamento de textos, dando uma ênfase em semântica e seus conceitos para avaliar a similaridade entre palavras. Como referência bibiliog?afica, recomenda-se a leitura do capítulo 6 do livro Speech and Language Processing, de Dan Jurafsky. Começamos a aula com uma atividade que apresentava um conjunto de palavras e demandava a indicação da palavra mais próxima à uma palavra-base, sem apresentar um contexto específico. Muitos alunos, como apresentou o professor posteriormente, apresentaram respostas e justificativas similares, como a menor quantidade de diferença entre caracteres, ou mesmo a pronúncia similar. Enquanto isso é muito intuitivo para o homem, automatizar tal processo exige um pouco de trabalho. Nessa aula, estudamos algoritmos úteis para essa aplicação. A fim de avaliar o casamento aproximado entre strings, discutimos sobre a distância de Hamming e de Levenshtein. O primeiro, um pouco mais rudimentar e muito importante na detecção de erros em transmissões binárias de comprimento fixo, simplesmente compara duas strings caractere por caractere, desde que elas tenham o mesmo tamanho, retornando o número de caracteres diferentes. A distância de Levenshtein, por sua vez, pode comparar strings de tamanhos diferentes e o faz verificando todas as possibilidades de inserção, exclusão e substituição, cada operação dessa possuindo um custo. O algoritmo, dessa forma, escolhe recursivamente o conjunto de operações de menor custo que resulte em um casamento entre as palavras. Isso, entretanto, dependendo da implementação, pode ser muito custoso, com uma curva assintótica exponencial e pode ser melhorado através de programação dinâmica, o que, por lado, exige um armazenamento extra, mas deixa a implementação com O(n * m), sendo n e m os tamanhos das palavras analisadas. A aula, a partir disso, se desenrolou com conceito importantes da linguística. Ora, PLN trabalha com palavras, e elas podem se comportar de maneira diferente em contextos específicos. Vimos, em aulas anteriores, uma primeira estratégia, que é usar Lemmatizers. Lemmatizers obtém a visão do dicionário, a palavra sem inflexão e, diferente dos Stemmers, que obtém uma instância única da palavra, diferencia as classes gramaticais. Mas isso, por si só, não é suficiente: o substantivo banco, por exemplo, pode denotar uma instituição financeira, um artefato (como banco de dados) ou um assento (banco de madeira). Entender o porquê disso é fundamental. Dessa forma, começamos a classificar as palavras partindo de homônimo. Quando duas palavras compartilham a mesma forma, isto é, apresentam mesma grafia (homógrafo) ou mesma pronúncia (homófono), e possuem significados diferentes, dizemos que elas são homônimas. Um bom exemplo são os diferentes contextos da palavra banco. Diz-se, então que banco é uma palavra polissêmica, pois possui muitos significados relacionados. Além disso, muitas dessas ocorrências de polissemia são sistemáticas, apresentando uma relação de metonímia. Quando representamos o todo pela parte, atribuímos um novo significado à parte, como falar de uma fruta em referência à árvore. Vimos, ainda, outros conceitos como sinônimos, antônimos, hiponímia e hiperonímias. Esses dois últimos indicam uma relação hierárquica de significado: carro e caminhonete, são, por exemplo, hiponímias de automóvel. Agora que entendemos alguns conceitos, podemos usar tesauros! Tesauros são dicionários de ideias afins, usado para desambiguar o significado das palavras. Wordnet é um exemplo e está organizado em base de relações, essas que acabamos de estudar. Podemos usar essas relações para identificar similaridade de forma bem simples: duas palavras são similares se ambas estão bem próximas hierarquicamente (se uma é hiponímia de outra, por exemplo) e isso pode ser feito calculando a distância do menor caminho entre eles, em uma estrutura de árvore. Tal algoritmo é chamado de path based similarity. Há, também, algoritmos baseados em distribuição de palavras, que não precisam de tesauros. Se, por um lado, evitamos a dependência da completude do dicionário, que representam adjetivos e verbos em menor quantidade, por outro, necessitamos de um grande corpus. Nessa abordagem, analisamos o contexto em que as palavras estão, representando-as como vetores de números e usando matrizes termo-documento. Mas isso será abordado na próxima aula. |
| Luiz Gabriel Correia | Casamento aproximado entre strings e semântica e similaridade entre palavras. No contexto de correção de ortografia, "Graffe" está mais próximo intuitivamente de "Giraffe". Como medir a similaridade entre strings? Podemos usar a distância de Hamming, muito usada para detectar erro de transmissão. Basicamente é a quantidade de bits diferentes comparando duas cadeias distintas de mesmo tamanho. Distância de Levenshtein, proposta nos anos 1960, também compara a distância entre uma cadeia e outra, mas considerando qualquer uma de 3 operações: inserção, exclusão e substituição. Ex: a distância entre "casa" e "pata" é 2. O algoritmo que faz o calculo da distância é recursiva. Primeiro, se o tamanho de uma das cadeias é zero, então a distância é o tamanho da outra cadeia. Caso contrário, a distância é o mínimo da distância calculada em três cenários: no caso em que os dois elementos são iguais, diminuímos as duas cadeias em 1. Se forem diferentes, precisamos obter a distancia retirando o último carácter da primeira cadeia e retirando o último da segunda cadeia. A cada operação que reduz a cadeia associamos um custo. A deficiência deste algoritmo é que ele tem uma complexidade exponencial, já que muitos chamados são repetidos, desta forma, é uma versão ingênua. Usando memoização (programação dinâmica) com uma estrutura auxiliar para guardar os cálculos já feitos, podemos reduzir a complexidade para O(mn). Por esta distância EDU e EIDU tem distância 1. Não precisa calcular a matriz completa se especificarmos um número máximo de caracteres diferentes que queremos detectar, assim podemos acelerar ainda mais o cálculo. Como já vimos, lemma é a palavra sem flexões, na sua versão de dicionário. No entanto, o mesmo lemma pode ter diferentes significados. Palavras homógrafas são palavras diferentes com a mesma escrita, enquanto palavras homófonas são palavras diferentes com a mesma fala. Como determinar se uma palavra tem mais de um significado? Usando o teste Zeugma (figura de linguagem ou estilo). Se a construção não faz sentido coerente, usando todos os usos para aquela palavra, provavelmente a palavra seja polissêmica. Sinônimos são palavras com escrita diferente mas que tem o mesmo significado, ou seja, elas podemos ser substituídas um pela outra em TODOS as situações. Antônimos são duas palavras cuja o significado é o oposto. Hiponímia e Hiperonímia estabelecem relações de hierarquia de significado entre as palavras. Uma palavra é uma hiponímia de outra se tem um significado mais restrito. Uma palavra é uma hiperonímia de outra se te um significado mais abrangente. Tesauros é um repertório de palavras para auxiliar na desambiguação do significados do vocabulário de documentos. Um exemplo é o Wordnet. A diferentes iniciativas para vários idiomas. A deficiência deste tipo de dicionário é a dificuldade de se manter e atualizar. Duas palavras são similares se ambas compartilham o mesmo significado. É útil por exemplo para recuperar informação e detecção de plágio. A distância entre suas palavras também pode ser calculada com base na proximidade o significado ou contexto. Para isto, há algoritmos baseados em tesauros, que estabelecem que duas palavras são similares se uma é hiponímia da outra. Podemos calcular a distância através da distância dos caminhos na árvore de relações de hierarquia entre as palavras, a similaridade é o inverso da distância. Há também algoritmos baseados em distribuição de palavras em um grande corpus. A ideia é, palavras que estão em contextos similares tendem a ser semanticamente similares. Na literatura isto é conhecido como distributional semantics e vector semantics. Esta ideia é anterior ao contexto computacional. Matriz termo-frequência é uma estrutura simples mas eficiente para determinar semelhança entre documentos e termos. Construímos a matriz contando quantas vezes um termo aparece em um documento. O número de linhas é o tamanho do vocabulário e o número de colunas é o nome de obras. Podemos usar, por exemplo, distância euclidiana entre os dois vetores coluna. Analisando o vetor linha, podemos usar uma medida de distância entre dois vetores que representam palavras e estimar a proximidade semântica entre os dois termos. |
| Thiago Henrique Gomes Panini | Resumo 8 PLN A oitava aula de Processamento de Linguagem Natural foi iniciada com uma atividade, passada pelo professor Jesús, contemplando três questões a respeito do conteúdo a ser ministrado na aula. Nela, foi possível retirar alguns insights sobre similaridade entre palavras, significado de homógrafo, homófono e tesauro. Assim, tendo em mente uma introdução do tema da aula, iniciamos a discussão sobre similaridade de palavras e algumas aplicações práticos disso, como na biologia em cadeias de ácidos nucleicos. Um ponto essencial para a definição desse conceito é a distância entre as palavras que, apesar de parecer abstrato no início, se faz um conceito extremamente claro com as explicações que se sucederam. A medida de distância de Hamming foi introduzida como forma de realizar esse cálculo, mostrando então, como exemplo, as diferenças entre PLN e PNL, UFABC e UFRJ, UFABC e UFRRJ. O resultado para os respectivos exemplos foram 1, -1 e 3, indicando assim que esse algoritmo para o cálculo da distância não leva em consideração palavras trocadas e outras particularidades. Outro algoritmo que pode ser utilizado é a distância de Levenshtein em que, de uma forma mais robusta, consegue calcular uma espécie de diferença entre as palavras. O código responsável por definir o algoritmo de Levenshtein foi explicado pelo professor que, por sua vez, também pontuou sua principal desvantagem: custo computacional. Por definição, esse algoritmo trabalha com chamadas recursivas para realizar comparações de palavras e sucessivas alterações nas mesmas. Para evitar esse aumento do custo computacional, pode ser utilizada uma tática de programação dinâmica (memoização), utilizando alguma estrutura auxiliar, como matrizes e vetores, para aumentar a velocidade de execução do algoritmo. Para ilustrar essa aplicação, foi pontuado o exemplo do cálculo de Fibonacci utilizando matrizes como estruturas auxiliares, evitando assim a recursão excessiva. Em uma segunda etapa da aula, iniciou-se o debate sobre semântica e similaridade de palavras sob o macro tema de casamento aproximado entre strings. Ao invés de analisar palavras na ótica de troca de letras ou mudanças de posição, vamos agora aplicar os conhecimentos de PLN para aplicar questões de linguística de modo a identificar se realmente uma palavra é próxima a outra no universo semântico. O primeiro conceito para o entendimento dessa similaridade entre palavras é o Lemma, ou seja, significado das palavras sem inflexão. Em seguida, o conceito de Homônimos foi apresentado como uma forma de dificultar nossa vida em PLN. Exemplo: a frase banco quebrado indica a instituição ou o assento? Um outro conceito apresentado foi o de Polissemia, seguindo com os exemplos onde mais de um significado pode ser encontrado para a mesma palavra: letra, vela. Um teste a ser realizado a fim de identificar se uma palavra possui mais de um significado é o teste de Zeugma. Nele, dois contextos contendo a mesma utilização da palavra são comparados de modo a identificar se existe algum sentido nessa comparação. O exemplo utilizado em aula comparava a utilização da palavra universidade nas seguintes frases: ...construirá uma universidade de mármore e ...pedirá à universidade de João. Os tempos universidade de mármore e universidade de João podem não fazer sentido, indicando assim que o termo universidade foi utilizado e possui mais de um contexto. Em seguida, os conceitos de sinônimos e antônimos foram passados como parte do conteúdo teórico. Por fim, temos a Hiponímia e Hiperonímia que indicam relação hierárquica de significados entre a palavras. A definição de tesauro foi dada como sendo um dicionário de ideias comuns. Uma definição mais formal indica que o tesauro é um acervo ordenado de termos e conceitos relacionados entre si. Um dos tesauros mais comuns é o Wordnet. Por que é importante avaliar a similaridade? A resposta para essa pergunta pode ser dada em três tópicos diferentes. O primeiro deles, para recuperação de informação. O segundo, para detecção de plágio. O terceiro, para agrupamento de texto. A partir da criação de um agrupamento hierárquico, é possível assimilar conclusões sobre similaridades de palavras e a criação de um tesauros. |
| Marcelo de Souza Pena | Começamos a aula 8 com o teste. Foram três questões: a primeira para identificar dentre três opções qual palavra era mais similar à palavra da questão, a segunda pedia o significado de homógrafo e homófono e a terceira perguntando o que é tesauro. Para resolver a primeira contei quantas inserções/substituições de letras seriam necessárias para tornar as palavras iguais, na segunda a resposta estava no nome, palavras com grafia igual, mas significado e pronúncia diferentes e palavras com pronúncia igual, mas significado e grafia diferentes e tesauro, com ajuda do Google, descobri ser um dicionário de termos utilizados na indexação e classificação de documentos. Distância de Hemming é o algoritmo mais básico para medir similaridade entre palavras, considera apenas palavras de mesma dimensão e mede letra a letra quantas estão diferentes. Distância de Levenshtein é mais sofisticada, mede a quantidade de diferenças, sejam inserções, exclusões ou substituições, como a variação entre pata e casa que é 2, já que não há como fazer com menos de duas substituições. O cálculo é feito construindo uma matriz com os caminhos da comparação em que cada inserção ou remoção de letra acrescenta +1 ao valor da célula e cada substituição acrescenta +2. Uma variação do algoritmo calcula distâncias até um valor máximo, sem necessidade de calcular a matriz toda, tornando a execução mais rápida. Entrando no assunto semântica e similaridade de palavras, capítulo 6 - Vector Semantics do livro. Relembrando stem e lemma, parte de uma palavra vs forma básica da palavra. Dois lemmas podem ser iguais, mas com significados diferentes (homônimos) como banco, que pode ser um assento, uma instituição financeira ou mesmo um banco de dados. Cinco definições importantes sobre o significado de palavras: homônimos (palavras iguais com diferentes significados, como no exemplo do banco), polissemia (relações sistemáticas, palavras que podem ter mais de um significado, metonímia, como ler Machado, ir à universidade - dá pra testar polissemia colocando dois contextos juntos e vendo se a frase fica coerente, é chamado teste de Zeugma, se a frase não fizer sentido é porque a palavra provavelmente é polissêmica), sinônimos (palavras que tem o mesmo significado, independente do contexto), antônimos (palavras com significados opostos) e hiponímia e hiperonímia (como objetos e instâncias, de forma que carro é uma hiponímia de automóvel, que é uma hiperonímia de carro). Linguagem computacional. Tesauro é um dicionário de ideias comuns, como o Wordnet, com tonelitros de termos de forma hierárquica. Tesauros também são usados para verificação de plágio, com ajuda deles palavras similares são detectadas, além de recuperação de informação e agrupamento de textos. Existem iniciativas assim em outros idiomas, mas as línguas são vivas, estão sempre mudando, então é muito custoso mantê-los atualizados. A identificação de palavras similares pode ser feito com ajuda de um tesauro ou analisando a distribuição das palavras em um corpus bem grande. Algoritmos que usam tesauro podem construir árvores com as palavras sendo os nós e a similaridade é maior quando palavras estão na mesma hierarquia ou próximas, apesar de eles terem alguns problemas, alguns que podem ser contornados usando um corpus para analisar melhor a distância entre as palavras. Outra forma é utilizar um corpus grande uma vez que palavras utilizadas em contextos similares tendem a ser semanticamente similares, conseguindo mostrar relações que não estão presentes em tesauros, como a similaridade entre oculist e eye-doctor. Matriz termo-documento serve para detectar textos e termos similares, de forma que textos similares teriam uma frequência de palavras em proporção parecida. Também é possível agrupar hierarquicamente como em cladística e assim encontrar relações entre palavras. |
| Rodrigo Akiyama Abrantes | Resumo aula 8 de Processamento de Linguagem Natural Casamento aproximado entre strings A distância de hamming é utilizada para detectar erros nas transmissões binárias de comprimento fixo. Ela é a quantidade de bits utilizada na mudança de uma transmissão para a recepção. Para a análise da diferença entre termos, utilizando o algoritmo fornecido em aula, dado duas palavras de mesmo comprimento (ou seja, de mesmo número de caracteres), o algoritmo de hamming encontraria qual o número de caracteres que não correspondem em duas palavras. Por exemplo, UFABC e UFRRJ difeririam em 3 caracteres, apresentando uma distância de 3. Caso as duas palavras não tivessem o mesmo comprimento, o retorno seria -1, indicando erro ou entrada não válida. A distância de Levenshtein possui o mesmo propósito de medir a quantidade de diferenças entre duas strings, porém ela não possui a limitação de ambas terem de possuir o mesmo comprimento. Ela define o número mínimo de edições necessárias (sejam elas inserção, exclusão e substituição) para transformar uma string em outra. Se o comprimento de uma das strings for zero, então a distância será igual ao comprimento da outra string. A análise da implementação do algoritmo, porém, revela que esta abordagem não é muito eficaz quando se pensa no aspecto computacional já que esta utiliza recursão. Além disto, existe a possibilidade de se realizar diversas repetições de comparações, não sendo esta a abordagem mais eficiente. Um lemma é a forma básica da palavra, sem nenhuma inflexão (plural, conjugação, etc). Uma wordform é a palavra com inflexão (exemplo, bancos, cantoras, vidas). Um determinado lemma pode ter diferentes significados e este fato está relacionado quanto a classificação da palavra. Uma palavra homônima é aquela que compartilha da mesma forma de outra palavra, mas que possuem significados diferentes. Os tipos de homônimos são os homógrafos, que possuem a mesma escrita, e os homófonos, que possuem a mesma forma de fala. Esta classificação de palavras causam grandes problemas em PLN pois exigem que sejam realizadas análises de contexto para que se saiba qual forma da palavra foi utilizada e, portanto, qual é o seu real significado. Outra classificação é a polissemia, onde uma palavra apresenta vários significados relacionados. Para se testar se uma palavra possui mais de um significado é necessário realizar o teste Zeugma, inserindo a palavra em diferentes contextos. Se a construção tiver sentido coerente, ela será polissêmica. As palavras sinônimas são aquelas que possuem o mesmo significado em quase todos os contextos, podendo ocorrer substituições entre elas sem que se prejudique o entendimento da sentença. Antônimos são as palavras que possuem o significado oposto em relação a uma característica descrita por outra palavra. Palavras hiponímia e hiperonímia estabelecem uma relação de hierarquia de significado entre as palavras. Uma palavra A é hiponímia de B se o significado de A é mais específico que B. O wordnet é uma base de dados utilizada na área de linguística computacional e está em inglês, ele está organizado com base em relações hierárquicas das palavras e é utilizado para desambiguar o significado das palavras, funcionando como um tesauro. Para realizar a análise de similaridade de palavras, utilizam-se duas abordagens: a de algoritmos baseados em tesauro e a de algoritmos baseados em distribuição de palavras. Na primeira é calculado a distância na árvore hierarquica entre as palavras. Na segunda verifica-se as palavras imediatamente ao redor da palavra analisada. |
| Matheus Fama Machado de Sousa | Resumo aula 08 - Nesta aula, vimos um pouco sobre casamento de strings. Casamento de strings tem diversas aplicabilidades em diversas áreas como na correção ortográfica e identificação de sequências de aminoácidos. Conceitos importantes: Distância de Hamming: é a quantidade de bits usado na mudança de uma transmissão para a recepção. Utilizado para detectar erros nas transmissões binárias de comprimento fixo. Distância de Levenshtein : Usando-se de operações como inserção, exclusão e substituição, esta distância métrica define o número mínimo de edições para transformar uma string em outra. Por exemplo, a distância de Levenshtein entre casa e pata é 2. É usada para medir a quantidade de diferenças entre duas strings. Stemming (a ação de reduzir em stems) Stem: Parte de uma palavra Stemmer: O artefato (programa). Lemmatization (a ação de reduzir em Lemmas) Lemma: Forma básica da palavra Lemmatizer: O artefato (programa). Lemma: é a forma básica da palavra (sem inflexão). Wordform: é uma palavra com inflexão. Um determinado lemma pode ter significados diferentes. Exemplo: um banco pode manter investimentos dos correntistas ... Homônimos: São palavras que compartilham a mesma forma mas com significados diferentes (origens diferentes). Homônimos podem ser: Homógrafos, i.e., mesma forma de escrita (banco/banco) Homófonos, i.e., mesma forma de fala (Concerto/conserto). Homônimos criam problemas em PLN. Polissemia (muitos significados): É a propriedade de uma palavra tem de apresentar vários significados. Como determinar se uma palavra tem mais de um significado? Usando o teste Zeugma (figura de linguagem ou estilo) Se a construção não faz sentido (coerente), provavelmente a palavra é polissêmica. Sinônimos: Palavras que tem o mesmo significado em alguns ou todos os contextos. Ambas podem ser substituídas em todas as situações. Ambas têm o mesmo significado proposicional. Antônimos: Palavras que tem significado oposto em relação a uma característica. Hiponímia e Hiperonímia Indicam relação hierárquica de significados entre palavras. Uma palavra A é hiponímia de B, se o significado de A é mais específico que B Similaridade entre palavras Duas palavras são similares se ambas compartilham o mesmo significado. As palavras similares mantém uma relação de significado. A similaridade de palavras pode ser útil em diferentes tipos de aplicações, como por exemplo: Recuperação de Informação (IR) Busca por elementos similares Detecção de plágio Busca por regiões similares Agrupamento de textos Busca por conjuntos de textos similares A similaridade entre palavras pode ser estimada por uma medida de proximidade de significado: Quase sinônimos Carro é similar a Bicicleta. Duas abordagens para identificar similaridade entre palavras: (1) Algoritmos baseados em tesauro: Duas palavras são similares se uma é hiponímia de outra. Podemos discutir um problema dessa abordagem: Assumimos que cada aresta representa distância uniforme. simpath(nickel, money) == simpath(nickel, standard) Os vértices em hierarquias superiores são mais abstratos! (2) Algoritmos baseados em distribuição de palavras: Não precisam de um tesauro, mas de um corpus grande no qual sejam evidenciados diferentes pares de palavras. As métricas apresentadas são dependentes de um tesauro. Dependem da completude das palavras (dicionário), ie. não são flexíveis. No Tesauro algumas relações não estão representadas. Adjetivos e verbos são menos representados nos tesauros. O significado de uma palavra é calculada a partir da distribuição de palavras que estão ao redor dela. As palavras são representadas como um vetor de números. Matriz termo-documento: Dois documentos são similares se os vetores são similares. |
| Arthur Veloso Kamienski | String matching é a ação de casar strings relacionadas. A proximidade entre duas strings pode ser dada por diversos métodos distintos. Um desses métodos é a distância de Hamming, criado originalmente para identificar erros na transmissão de dados em formato binário, ao contar o número de bits distintos entre o que foi enviado e o que foi recebido. Esse método pode ser aplicado à palavras, sendo sua proximidade dada pelo número de letras que são distintas entre as duas. Um método mais robusto é a distância de Levenshtein, que leva em consideração operações de inserção, exclusão e substituição de caracteres. Assim, a distância é dada pelo número de operações necessárias para obter uma palavra a partir de outra, tendo a operação de substituição custo igual a dois (equivalente a uma remoção e uma inserção). Palavras homônimas (podendo ser dadas por palavras homógrafas, que tem grafia idêntica, ou homófonas, que são pronunciadas do mesmo modo), são palavras que, apesar de similares em sua grafia ou em sua pronúncia, têm significados distintos, devido a origens distintas. Essas palavras são problemáticas para PLN, principalmente quando tratamos de recuperação de informação, tradução de textos, e text-to-speech. Por outro lado, palavras também podem ser polissêmicas, tendo significados relacionados de origens similares. São exemplos as relações sistemáticas (metonímias), que relacionam uma palavra a uma outro sentido devido a sua relação com o sentido original. Uma maneira de se identificar uma palavra polissêmica podemos utilizar o teste de Zeugma, que analisa a coerência de uso de uma palavra em uma determinada frase. Se a palavra não for coerente, ela pode ser polissêmica. Palavras também podem ser sinônimos, ou seja, palavras distintas com um mesmo significado. Sinônimos podem ser identificados pois podem ser substituídos em todas as suas aplicações em frases, assim como por terem o mesmo significado proposicional. Antônimos são o inverso de sinônimos. Existem ainda hiponímias e hiperonímias, que indicam relações de hierarquia entre duas palavras, sendo a primeira indicando palavras com significado mais específico que outra, e a segunda para indicar palavras menos específicas que outra. Tesauros são dicionários de ideias comuns e podem ser utilizados para identificar sinônimos. Palavras similares são aquelas que compartilham o mesmo significado. A identificação de similaridade é importante para, por exemplo, a recuperação de informações, detecção de plágios e agrupamento de textos, ao se converter palavras para uma palavra comum com o mesmo significado. Palavras correlatas, no entanto, são palavras com significado similar, mas não idêntico, sendo consideradas "quase sinônimos". Para identificar palavras similares, podemos utilizar algoritmos baseados em tesauros, indicando que palavras são similares se pertencem à mesma hierarquia e calculando a distância entre elas pelo inverso do tamanho do caminho percorrido para chegar de uma a outra na sua arvore hierárquica. No entanto, vértices superiores na hierarquia são mais abstratos e deveriam ser mais distantes da palavras em questão. Outros algoritmos que podem ser utilizados são algoritmos baseados em distribuição de palavras. Esses algoritmos tem a vantagem de serem flexíveis com relação aos tesauros, pois não são estáticos e palavras podem mudar seu sentido com o passar do tempo. Algoritmos de distribuição de palavras são independentes de tesauros ao calcular o significado de palavras a partir da distribuição de palavras que ocorrem ao redor delas, e formar um vetor numérico de representação delas. |
| Amanda Cruz Francesconi | casamento aproximado entre strings string matching: qual a palavra mais próxima à palavra digitada? para determinar a similaridade é preciso definir um conceito de distancia: 1. distância de Hamming: compara elemento a elemento, bit a bit, indica quantidade de elementos diferentes entre as duas cadeias. O algoritmo é simples, com um laço que percorre o vetor/string e conta a cada vez que os caracteres são diferentes. Por exemplo: entre PLN e PNL o método retornaria 2. 2. Distância de Levenshtein, proposta nos anos 60 e utilizada em grande parte da computação. Utilizada operações de com inserção, exclusão e substituição para calcular quantas modificações teriam que ser feitas na palavra até chegar na palavra destino. Por exemplo a palavra "casa" e "pata" tem uma distância de 2, uma substituição de "c" por "p" e uma substituição de "s" por "t". Se um dos termos é nulo, a distância será o número de caracteres da palavra inserida. A deficiência desse algoritmo é o custo operacional exponencial pois a cada chamada da função ela se chama recursivamente mais 3 vezes. A solução para esse problema é utilizar a memoização, levando o algoritmo a funcionar em tempo MxN sendo M e N o tamanho das palavras inseridas. semantica e similaridade entre palavras SIGNIFICADO de palavras: 1. Homônimos: considerando o lemma (a versão do dicionário da palavra, versão sem inflexão) existem palavras de mesma forma porém com significados diferentes. Por exemplo "banco" que pode ser a instituiçaõ financeira, um artefato computacional (banco de dados) ou um objeto (assento). Os homônimos podem ser homógrafos ou homófonos. 2. Polissemia:muitos significados, geralmente tem origens similares. Como determinar se uma palavra tem mais de um significado? Uma das técnicas é o teste "Zeugma", criar uma frase combinando as duas entradas, se NÃO for coerente provavelmente a palavra seja polissêmica. 3. Sinônimos: palavras com o mesmo significado porém com grafia diferente. Exemplo: caderno e caderneta. 4. Antônimos: palavras que tem o significado oposto. Exemplo: claro e escuro. 5. Hipomímia e Hiperonímia: indica relação hierarquica de significado entre as palavras. Exemplo: carro é hiponímia de automóvel e automóvel é hiperonímia de carro. TESAUROS: dicionário de "ideias comuns", um tesauros conhecido é o wordnet, base de dados desde 1985, ao se inserir uma palavra ele mostra todos os contextos em que essa palavra foi encontrada, já mostrando sua hierarquia. Existem 2 em português. A deficiência, além de trabalhoso para ser construido, é que ele é especifico para certos contextos, não é dinânico. Porque é importante avaliar similaridade? Alguns exemplos são recuperação de informação, detecção de plágio (podem utilizar tesauros), agrupamento de textos entre outros. 1.Algoritmos baseados em tesauro: Duas palavras são similares se uma é hiponímia de outra ou "path based similarity", distância de menor caminho entre duas palavras utilizando um conceito de árvore. 2.Algoritmos baseados em distribuiçaõ de palavras: Utiliza um corpus grande. Matrix termo frequência: o número de linhas é o tamanho do vocabulário e o número de colunas é o número de obras, utilizando distância euclediana é possível descobrir a similaridade entre as obras. Assim como analisando por linhas é possível descobrir a similaridade entre dois termos do vocabulário. Com isso é possível construir um agrupamento hierárquico que poode, por sua vez, levar a criação de um tesauro. |
| Renan Baisso | Resumo aula 8 Dando prosseguimento aos estudos de processamento de linguagem natural, os itens abordados na aula foram (1) Casamento aproximado entre strings e (2) Semântica e similaridade de palavras, sendo que o último foi apenas introduzido. O casamento de strings consiste em um procedimento para medir distância entre palavras, por exemplo, em uma correção ortográfica dentre opções válidas, ou corretas, qual é a mais próxima de uma palavra que foi escrita errada, isto é, qual é a mais semelhante? Para responder tal questionamento, é necessário que seja estabelecido algum tipo de medida para verificar tal medida. O modelo mais simples de realizar esta medição entre strings, é o modelo de distância de Hamming, o mesmo utilizado para contexto binário, em que são medidos apenas quantos bits ou, no nosso caso, letras são distintas entre duas palavras, este modelo possui suas limitações, já que ambas as strings devem ter o mesmo tamanho. Ainda se tratando de casamentos de strings, existe também o modelo de Levenshtein que realiza a medida através de contagens de operações (substituição, adição ou eliminação) diferem duas palavras, isto é, quantas operações dentre as listadas são necessárias para que as palavras se tornem idênticas. Desta maneira, mesmo que, no casa de correções ortográficas, os objetos comparados sejam de tamanho diferente, o modelo pode ser aplicado, o que o torna mais robusto que o de Hamming. Além disso, o modelo de Levenshtein permite a definição de pesos para cada operação e em algumas implementações é possível parametrizar quantas diferenças são admissíveis. Recapitulando o que foi dito em aulas anteriores sobre stem e lemma, podemos sintetizar que um lemma pode ter mais de um significado semântico, como no caso de banco, que pode significar um assento, uma instituição financeira ou uma forma de armazenamento de dados. Partindo disso, pode-se determinar cinco definições importantes sobre os significados das palavras - 1) Homônimos que são palavras de mesmo som e com significado diferentes - 2) Polissemia que são palavras com mais de um significado ou significados semelhantes que pode ser verificado através do uso de zeugma - 3) Sinônimos que são palavras diferentes com um mesmo significado - 4) Antônimos que são palavras com significados opostos - 5) Hiponímia e Hiperonímia que são palavras que têm um relação de hierarquia com entre si através de contexto ou semelhança. Para verificar a similaridade entre palavras, podemos ter duas abordagens de algoritmos, um que se baseia em tesauros que são conjuntos de palavras relacionadas para um dado contexto. O funcionamento deste algoritmo é pelo cálculo de distância dentro da hierarquia do tesauro para determinar a semelhança, porém, nesta abordagem a manutenção de um tesauro é lenta e custosa, dado que para novos termos a evolução deve ser manual. Entretanto, utilizando uma abordagem de distribuição de palavras, que é conhecida na literatura por Distributional semantics ou Vector semantics, basta ter um corpus suficientemente grande para encontrar a relação das palavras para dados contextos, eliminando a necessidade de um tesauro. Para concluir, com base neste agregado de tópicos é possível construir uma estrutura matricial conhecida como Matriz: termo-documento, a qual pela análise entre colunas permite traçar a similaridade entre textos, já com a análise entre linhas a semelhança entre termos escritos em obras diferentes. |
| Marcela Akemi Yamashita | Parte 1: Casamento aproximado entre strings. String matching: graffe está mais proximo de? Girafe. Sequencias de aminoácidos podem ser alinhados para detectar erros nas transmissões binárias de comprimento fixo. Distancia de Hamming: quantidade de bits de transmissão para recepção. Distância de Levenshtein: quantidade de diferença entre duas strings, usando inserção, exclusão e substituição. Define o número minimo de edições para transformar uma string em outra. Ex: distancia entre casa e pata = 2. casa para pata é obtida substituindo c por p e s por t. Comprimento de uma string=0: distancia será o comprimento da outra string. Pode ser modelada como uma árvore de recursão(memoização). Algoritmo caro devido a sucessivas chamadas e repetições em diferentes recursões. Solução: matriz, atribuindo pesos para ações. A soma das ações tomadas define a diferença: Inserção:+1, Eliminação:+1, substituição:+2. Ferramenta online. Inviável para palavras grandes, custo m*n. Algoritmos alternativos que diminuem o custo. Parte 2: Semântica e similaridade de palavras. 5 definições de significado de palavras. Stemming x Lemmatization. Stem: parte de uma palavra. Lemma: forma básica (sem inflexão). Wordform: palavra com inflexão. Ex: Banks(wordform), bank(lemma). Lemma pode ter significados diferentes. Ex: banco (instituição financeira, artefato, assento). Homônimos: mesma forma, significados diferentes. Podem ser: homografos (mesma escrita: banco/banco). Homofonos(mesma pronuncia: concerto/conserto). Homônimos criam problemas em PLN: recuperação de informação, tradução de textos, aplicação texto-to-speech. Polissemia (muitos significados, porém relacionados). Ex: letra(elemento básico de um alfabeto, texto de uma canção, caligrafia de um determinado indivíduo). Relações sistemáticas(metonímia): prédio<->orgnanização. autor<->trabalho do autor, árvore<->fruto. Determinar se uma palavra possui mais de um significado: zeugma. Construção não coerente: provavelmente é polissêmica. Sinônimos: mesmo significado. Antônimos: significado oposto. Hiponímia: possui significado mais específico que outra (ex: carro e automóvel). Hiperonimia: possui significado mais abrangente que outra (ex: sandália e calçado). Wordnet: repositório (tesauro), base de dados (1985). Relações hierárquicas. Usado para desambiguar o significado das palavras. Synset: conjunto de sinônimos proximo. Hierarquia de hiperonomios. Similaridade entre palavras: semelhantes se compartilham mesmo significado. Ex: banco e fundo. Importancia: pode ser útil em recuperação de informação, detecção de plágio etc. Versão flexivel: similaridade estimada por medida de proximidade de significado: carro e bicicleta. Algoritmos: 1) baseado em tesauro: palavras são similares se uma é hiponímia de outra (carro e automovel), se compartilham mesma definição. Path based similarity. Distancia do menor caminho. Pathlen(c1, c2)= 1+comprimento do caminho entre c1 e c2 na árvore de hiponímia, sympath(c1,c2)=1/pathlen, wordsim(w1,w2)=max(simpath(c1,c2). 2) baseado em distribuição de palavras: não precisam de tesauro, mas de um corpus grande no qual sejam evidenciados diferentes pares de palavras. Palavras que estão em contextos similares tendem a ser semanticamente similares. Conhecido como distributional semantics, vector semantics. Significado calculado a partir da distribuição de palavras que estão ao redor dela. Palavras representadas como um vetor de números. Ex: oculist e eye-dictor. Matriz termo-documento: documentos são similares se os vetores são similares, dimensão do vetor: tamanho do vocabulário. Palavras são similares se os vetores são similares, dimensão do vetor: número de documentos. Agrupamento hierárquico. Capturar significado relacional. |
| Ruan Fernandes | A aula 08 do dia 01/07 abordou a primeira parte sobre Casamento aproximado de Strings; Semântica e Similaridade de Palavras I. String matching: a palavra é comparada/alinhada conforme o contexto. Distância de Hamming: quantidade de bits usado na mudança de uma transmissão para recepção. É usada para detectar erros nas transmissões binárias de comprimento fixo. Distância de Levenshtein: usa-se para medir a quantidade de diferenças entre duas strings; Fazendo uso de adição, exclusão e substituição, essa distância define o mínimo de edições para transformar uma string em outra. Como exemplo, foi mostrado casa -> pata; sua distância é 2 pois o mínimo de edições necessárias é substituindo-se o 'c' e o 'p'. Existem sites que podem fazer a demonstração desse método, como foi mostrado, retornando inclusive com a "tabela" que foi mostrada de exemplo nos slides anteriores. Cinco definições importantes sobre o significado de palavras: Lemma=forma básica de uma palavra; Wordform=uma palavra com inflexão (ex Bank/Banks, Sing/Sung); um Lemma pode ter significados diferentes, como no exemplo foi mostrado 'banco' como instituição financeira, como artefato e como assento. Homônimos=Palavras que compartilham a mesma forma, mas com significados diferentes (origem difere); podem ser homógrafos e homófonos (mesma escrita e mesma fala, respectivamente); porém, homônimos podem criar problemas em PLN: em recuperação de informação, tradução de textos ('bat': 'bastão' ou 'morcego'?), aplicações text-to-speech. Polissemia=uma palavra com vários significados (uma palavra polissêmica tem significados relacionados). Metonímia=trocar parte pelo todo (exemplo: 'li Machado de Assis' ao invés de 'li a obra X do autor Machado de Assis'). Para determinar se uma palavra tem mais de um significado, pode ser verificado usando zeugmas (figura de linguagem), de modo que se a construção não tem sentido, provavelmente a palavra é polissêmica; Sinônimos também podem ser usados, trocando palavras por outras com mesmo significado em alguns ou todos contextos; Antônimos: sentido oposto a uma característica; Hiponímia e Hiperonímia: A é hiponímia de B se A é mais específico que B; caso contrário, A é hiperonímia de B. Wordnet: repositório (tesauro). É uma base de dados usada na área de linguística computacional em inglês. Está organizado em base de relações hierárquicas. É usado para desambiguar o significado das palavras. Synset: conjunto de sinônimos a uma palavra. Existem diversas iniciativas de Wordnet em diversos idiomas. Similaridade entre palavras: duas palavras são consideradas similares se o significado for o mesmo para ambas. Avaliar a similaridade pode ser útil em situações como recuperação de informação, detecção de plágio, agrupamento de textos, etc. A similaridade entre palavras pode ser estimada por medida de proximidade de significado 'quase sinônimos': 'carro' e 'bicicleta'. Algoritmos: 1. Algoritmos baseados em tesauro: duas palavras são similares se uma é hiponímia de outra ('path based similarity', distância do menor caminho entre elas); 2. Algoritmos baseados em distribuição de palavras: não precisam de tesauro, mas sim de um corpus grande para que sejam evidenciados diferentes pares de palavras. O significado de uma palavra é calculado a partir da distribuição de palavras ao redor dela. Matriz termo-documento: dois documentos são similares se os vetores são similares. |
| Giselle Silva de Santana | Nesta oitava aula, do dia 01/07/2019, foram abordados os temas Casamento aproximado entre strings e Semântica e similaridade de palavrasParte I. O assunto está presente no capítulo seis do livro Speech and Language Processing de Jurafsky e Martin. Iniciou-se a aula com uma atividade com questões sobre os assuntos que seriam tratados na aula. Após a atividade, iniciou-se o assunto sobre Casamento aproximado entre strings, String matching é bastante relevante em contextos como correção ortográfica, determinando qual a string mais próxima da desejada, e na biologia computacional, com alinhamento de sequências. Existem técnicas para se determinar a proximidade entre palavras. A Distância de Hamming é utilizada para detectar erros nas transmissões binárias de comprimento fixo, sendo determinada pela quantidade de bits usados na mudança de uma transmissão para a recepção, por exemplo, a distância entre as palavras amor e amei é 2. Outro método é a Distância de Levenshtein(1968), que é usada para medir a quantidade de diferenças entre duas strings, usando-se de operações como inserção, exclusão e substituição, que definem o número mínimo de edições para transformar uma string em outra, como por exemplo, a distância entre casa e pata é 2, pois não há maneira de o fazer com menos de 2 edições. Caso o comprimento de uma string for zero, então a distância será igual ao comprimento da outra string. Aprofundando-se mais no assunto, foram apresentadas cinco definições importantes sobre significados de palavras. Primeiramente, vimos que um lemma é a forma básica de uma palavra (sem inflexão), enquanto que uma wordform é uma palavra com inflexão, exemplo: lemma: dormir e wordform: dormiu, sendo que um lemma pode ter diferentes significados, como por exemplo, banco pode se referir a uma instituição financeira, artefato ou assento, sendo neste caso chamados de homônimos, que possuem a mesma forma mas com significados diferentes. Os homônimos podem ser homógrafos, que possuem a mesma forma de escrita (banco/banco) ou homónofos, que possuem a mesma forma de fala (consenso/concenso). Os homônimos criam problemas em PLN em recuperação de informação, tradução de textos e aplicações text-to-speech. Outra definição foi a de Polissemia, que é o caso de uma palavra apresentar vários significados, com origens similares, sendo muitas vezes sistemáticas. Para se determinar se uma palavra tem mais de um significado, o teste Zeugma pode ser utilizado e consiste que se a construção da sentença não faz sentido (coerente), provavelmente a palavra seja polissêmica. Também foram apresentados os conceitos de sinônimos, que são palavras com mesmo significado em todos os contextos, antônimos, que são palavras com significado oposto, hiponímia e hiperonímia. Existem tesauros (repositórios), como o wordnet, que podem ser usados para desambiguar o significado das palavras. Por fim, falou- se sobre similaridade de palavras, que são muito úteis para recuperação de informação, detecção de plágio e agrupamento de textos. São duas abordagens principais: algoritmos baseados em tesauro ou baseados em distribuição de palavras, sendo o segundo tipo necessário pois o primeiro é muito dependente do tesauro, não sendo flexíveis e algumas relações não são representadas. |
| July Anne Pinheiro | Aula 8: Casamento aproximado entre strings: Semântica e similaridade de palavras - Parte I String matching É uma área da computação que pode ser utilizada no contexto de linguística para correção de textos, e até no âmbito de biologia computacional para análise de combinação genética. Distância de Hamming Algoritmos utilizado na detecção de erros nas transmissões binárias de comprimento fixo, ou seja, é a quantidade de bits utilizadas para a alteração de uma transmissão para uma recepção. Distância de Levenshtein (custosa, função exponencial) Algoritmo utilizado para medir a quantidade de diferenças entre duas strings, através da utilização de operações como: inserção, exclusão e substituição, o algoritmo define um número mínimo de edições para transformar uma string em outra. Definições importantes sobre significado de palavras Stem: Parte de uma palavra Lemma: Forma básica da palavra(sem inflexão) Wordform: é uma palavra com inflexão. 1) Homônimos: palavras que compartilham a mesma forma (escrita/fala) porém possuem distintos significados. 2) Polissemia: São palavras que apresentam diversos significados, porém esses significados são relacionados. 3) Sinônimos: Palavras que têm o mesmo significado em alguns ou todos os contextos. Obs: Palavras sinônimas podem ser substituídas em todas as suas aplicações, devido a elas possuírem o mesmo significado proposicional. 4) Antônimos: Palavras que têm significado oposto em relação a uma característica. 5) Hiponímia(Sub) e Hiperonímia(Super): Indicam relação hierárquica de significados entre palavras. Bases de Dados PLN Uma base de dados, dicionário de ideias comuns, são denominadas tesauros que são repertório alfabético de termos utilizados em indexação e na classificação de documentos. Wordnet: É um repositório(1985) utilizados na de linguística computacional, em inglês, para desambiguar o significado das palavras. A base de dados do Wordnet está organizado em base de relações (hierárquicas). Synset: Repositório com conjuntos de sinônimos (próximos) a uma palavra. Similaridade entre palavra Duas palavras são similares se ambas compartilham o mesmo significado. Tipos de Aplicações de análise de similaridade * Recuperação de Informação (IR) * Detecção de plágio * Agrupamento de textos Como identificar similaridade (1) Algoritmos baseados em tesauro: Precisa de um tesauro para análise de similaridade entre palavras. Para efetuar a análise é utilizado a ideia de distância do menor caminho entre eles, sendo utilizado as relação informada a seguir para cálculo da distância: Simpath = 1/Pathlen(c1 , c2 ), sendo Pathlen(c1 , c2 ) = 1 + comprimento do caminho entre c1 e c2 na árvore de hiponímia(relação de hierarquia entre palavras). (2) Algoritmos baseados em distribuição de palavras: Para que a análise seja efetuada, o significado de uma palavra é calculada a partir da distribuição de palavras que estão ao redor dela. As palavras são representadas como um vetor de números. Métodos é utilizados quando existe uma necessidade de flexibilidade nas palavras, ainda mais considerando que a semântica das palavras mudam de alguma forma com o passar do tempo, devido a isso não precisam do Tesauro. Matriz termo-documento São utilizadas para análise de documentos em relação a similaridade, caso 2 vetores de dimensão N sejam similares os documentos também serão. Importante ressaltar que esses vetores são relacionais e podem ser agrupados em níveis hierárquicos. |
| Bruno Menezes Gottardo Ladeia | Nesta aula 8 foram apresentados os conceitos de String matching e sobre semântica e similaridade de palavras (Vector Semantics). No que se refere ao casamento aproximado entre strings discorreu sobre as diferentes maneiras possíveis de se comparar cadeais de caracteres, existindo diferentes medidas de distâncias que podem ser utilizadas. Das mais famosas as duas que foram discutidas são: a distância de Hamming e a de Levenshtein. A de Hamming é uma medida muito simples, que só pode ser utilizada para calcular cadeias de mesmo tamanho. Ela compara os elementos posição a posição e conta a quantidade de pares de elementos que são díspares entre os elementos de análise. O total de elementos representa a distância de Hamming entre as duas strings sendo comparadas. Esta medida de distância é a mais básica (medida de distância clássica). Já a de Levenshtein é um pouco mais completa. A partir de duas strings ela conta a quantidade de operações necessárias (inserção, exclusão e substituição) para transformar a primeira string, na segunda (ou vice versa). O total de operações necessárias é igual a distância de Levenshtein (e.g. "casa" e "pata" possuem distância 2 entre si, pois, no caso da palavra "casa" basta substituir a letra 'c' por 'p' e a letra 's' pela letra 't'). Na sua forma mais básica as operações tudo possuem o mesmo peso. Caso uma das strings tenha tamanho 0, a distância será igual ao comprimento da outra string. Na sua forma recursiva mais básica a distância de Levenshtein possui complexidade de tempo diretamente proporcional ao tamanho das strings, tendo um desempenho muito ruim, visto que muitas operações são repetidas durante as chamadas recursivas. Para contornar este problema é possível fazer uso da Programação dinâmica e memoization para guardar um dicionário dos termos mais frequentes, a fim de diminuir o número de repetições. Na segunda parte foi revisto o conceito de 'significado' de palavras, havendo cinco definições importantes de interesse, que são: Homônimos, Polissemia, Sinônimos, Antônimos e Hiponímia e hiperonímia. Para fazer a análise do significado de palavras é preciso utilizar o seu lemma (palavra sem inflexão) e não seu wordform (palavra flexionada). No caso de homônimos, as palavras compartilham a mesma forma, porém possuem significados diferentes (origens diferentes), esta dualidade criam problemas para PLN. Polissemia é uma palavra que tem significados relacionados, podendo apresentar vários significados. Para determinar se uma palavra possui mais de um significado, use o teste de "Zeugma". Sinônimos são palavras com o mesmo significado em alguns, ou todos, os contextos. Antônimos é o oposto de sinônimos e a última estrutura representa estruturas hierárquicas, sendo hiponímia uma palavra de maior especificidade a outra palavra que estiver sendo comparada. (e.g. Carro hiponímia de automável). Para efeito comparativo de significado é utilizado um tesauro, um bastante conhecido é o wordnet de 1985. Deste último é possível construir algoritmos que calculam a similirade entre palavras ao considerar as medidas pathlen(c1, c2) = 1 + dis(c1,c2) e simpath(c1, c2) = 1/pathlen(c1, c2), para uma palavra será o max de sim para cada um dos caracteres. |
| Paula Keiko Miyashita | O casamento aproximado de strings determina a distância/diferença entre duas strings, no entanto este pode ser calculado de diferentes maneiras. A distância de Hamming assume que as strings têm o mesmo comprimento e as compara, por isso são utilizadas para detectar erros nas transmissões binárias. Se suas strings de tamanho diferente são comparadas, o retorno de erro é imediato, caso contrário o retorno é do número de caracteres diferentes entre as duas strings (considerando o valor e a posição dos caracteres). A distância de Levenshtein, por sua vez, é utilizada para medir a quantidade de diferenças entre duas strings. Essa medição considera três operações: inserção, exclusão e substituição. A cada operação é atribuído um peso e a soma dos pesos das operações necessárias para que uma string se iguale à outra é o valor da distância entre elas. Foi apontado um problema no cálculo da distância de Levenshtein, que é a chamada da função três vezes, para receber os custos de cada um dos termos. Em seguida se voltou para o termo lemma, que é a forma básica da palavra, e wordform é uma palavra com inflexão. O foco, no entanto, foi para lemmas que podem ter mais de um significado (ex: banco) e então foram introduzidos alguns conceitos importantes. O primeiro conceito foi de Homônimos, palavras com a mesma foram mas significado diferente (ex: banco), os homônimos podem ser separados em Homógrafos (de mesma escrita) ou homófonos (de mesmo som/fala). Os homônimos são desafios em PLN pois geram dúvida em situações como recuperação de informação, tradução de textos e aplicações text-to-speech. O segundo conceito foi o de polissemia: muitos significados relacionados (origens similares), muitos tipos de polissemia são sistemáticos (metonímias). Para determinar se uma palavra tem mais de um significado, pode-se utilizar o teste Zeugma, que junta duas frases que contém a palavra estudada e verifica seu sentido, se não fizer sentido há grande probabilidade da palavra ser polissêmica. O terceiro conceito foi de sinônimos, palavras com mesmo significados, que podem ser substituídas uma pela outra em todas as situações. O quarto conceito foi de Antônimos, palavras com significados opostos. Por fim, o quinto conceito foi de Hiponímia e Hiperonímia, que indica relação hierárquica entre palavras. Uma palavra A é hiponímia de B se o significado de A é mais específico que B. hiperonímia é o inverso. O tópico seguinte foi wordnet, um tesauro/repositório utilizado para desambiguar o significado das palavras. O wordnet pode ser utilizado para determinar a similaridade entre palavras, que por sua vez é útil em situações como a recuperação de informação, detecção de plágio e agrupamento de texto. O algoritmo que determina a similaridade baseado em tesauro verifica se há relação de hiponímia ou hiperonímia entre elas ou se compartilham da mesma definição, ou seja, verifica a distância mínima entre elas na rede. A similaridade também pode ser determinada por distribuição de palavra, parte-se do pressuposto que palavras em contextos similares tendem a ser semanticamente similares, utiliza-se uma matriz termo-documento para isso. |
| Joao Victor Fontinelle Consonni | A oitava aula de PLN começou com a aplicação de um teste de avaliação que cobriu parte dos conceitos que foram vistos ao longo da aula. O primeiro deles estava relacionado à distância de edição entre duas palavras, ou seja, ao número mínimo de operações necessárias para transformar uma string na outra. Neste contexto, vimos a Distância de Hamming, utilizada para detectar erros nas transmissões binárias de comprimento fixo. Por ser limitada a comparação de strings de mesmo tamanho, a Distância de Hamming é pouco abrangente. Como alternativa, vimos a Distância de Levenshtein, que utiliza operações de inserção, exclusão e substituição para medir a quantidade de diferenças de uma string para outra. O formalismo matemático, assim como a implementação do algoritmo para o calculo da Distância de Levenshtein foram apresentados, para então fazermos uma análise da complexidade de tempo e espaço do algoritmo, que cresce exponencialmente com o tamanho das strings de entrada. Na segunda parte da aula foram cobertos alguns conceitos teóricos relacionados à semântica. Vimos stem (parte de uma palavra), lemma (forma básica da palavra) e wordform (palavra com inflexão). Lemmas podem ter diferentes significados, ou seja, duas ou mais palavras pordem compartilhar a mesma forma entre si, mas com significados diferentes. Estes casos são definidos como homônimos. Homônimos podem ainda ser de dois tipos: homógrafos e homófonos. O primeiro refere-se a palavras com a mesma escrita, enquanto o segundo a palavras com a esma fonética. Em recuperação de informação, tradução de textos e aplicações text-to-speech, homônimos podem criar problemas. Outro conceito visto foi o de polissemia, que é a propriedade de uma palavra apresentar mais de um significado, mas com origens similares. Muitos tipos de polissemia são sistemáticos, como ocorre com metonímias. Para determinar se uma palavra possui mais do que um significado, é utilizado o teste de Zeugma, que consiste em construir uma frase a partir de duas frases distintas em que a palavra ocorre; se a construção não fizer sentido, a palavra provavelmente é polissêmica. Os conceitos de sinônimo e antônimo também foram apresentados, mas apenas brevemente, pois são mais comuns ao dia a dia. Por fim, vimos hiponímia e hiperonímia, que servem para indicar relação de hierarquia entre palavras, como carro que é uma hiponímia de automóvel, e calçado, que é uma hiperonímia de sandália. Para auxiliar na desambiguação de significados, existem bases de dados como o wordnet, que consiste em um tesauro para a lingua inglesa. Um tesauro é uma espécie de dicionário de ambiguidades, ou de 'ideias comuns'. Vimos também o conceito de similaridade, ou seja, palavras que compartilham significados comuns. Uma aplicação relacionada a isso foi a de detecção de plágio. Basicamente, a similaridade entre palavras pode ser estimada por uma medida de proximidade de significado. Para isso, pode-se utilizar algoritmos baseados em tasauros, nos quais duas palavras são similares se uma é hiponímia de outra (ou se compartilham a mesma definição). Outra abordagem consiste em algoritmos baseados em distribuição de palavras. Este último não requer um tesauro, apenas um corpus grande. |
| Ramon Neres Teixeira Jardim | Esta aula foi sobre similaridade de palavras. Muitas vezes é necessário definir o quão parecidas são duas palavras, como por exemplo, comparação de sequências de aminoácidos, ou correção ortográfica, substituindo uma dada palavra detectada como um erro ortográfico pela palavra mais parecida. Uma definição de distância entre duas palavras é a distância de Hamming, muito utilizada para detectar erros em transmissões binárias de comprimento fixo. A distância de Hamming é definida como a quantidade de bits diferentes entre duas cadeias binárias fazendo a comparação ordenadamente bit a bit e pode ser feita da mesma forma para strings. Esta medida de distância não é muito interessante pois não consegue calcular a distância entre strings de tamanhos diferentes. Outra definição para distância entre duas strings é a distância de Levenshtein, que mede a quantidade de diferenças entre duas strings utilizando de operações de inserção, exclusão e substituição, definindo a distância entre duas string como o menor número de edições em uma das strings para que fique igual a outra. Por exemplo, a distância entre "gesto" e "testo" é 1, pois pode-se transformar uma na outra com uma edição. Na segunda parte da aula, foram dadas cinco definições importantes sobre o significado de palavras. Nesta parte também foram relembrados os conceitos de Stem (parte de uma palavra) e Lemma (forma de dicionário da palavra) e também foi introduzido o conceito wordform, que é uma palavra com inflexão. A primeira definição foram os homônimos, que são palavras que são escritas da mesma forma, porém com significados diferentes. Um exemplo é a palavra branco, que pode tanto ser uma instituição financeira quanto um assento. Os homônimos são um problema para algoritmos de processamento de linguagem natural, por exemplo, ao fazer traduções de textos, o algoritmo ao encontrar um homônimo pode não saber como traduzi-lo. A segunda definição foi polissemia, uma mesma palavra com vários significados, como a palavra letra, que pode ser entendida como um elemento do alfabeto ou o texto de uma música ou a caligrafia de uma pessoa. Há muitos casos de polissemia que são sistemáticos, algo muito comum ao se referir à instituições ou suas instalações, por exemplo, universidade pode ser tanto a instituição universidade quanto o prédio da universidade. Uma forma de determinar se uma palavra é polissêmica é utilizar o teste de Zeugma, unificando duas ou mais frases contendo a palavra e verificando se a construção faz sentido. Em terceiro e quarto lugar foram definidos os conceitos de sinônimo e antônimo, que são mais conhecidos popularmente. Palavras sinônimas são palavras com o mesmo significada, como carro e automóvel. enquanto palavras antônimas são duas palavras com significados opostos, como claro e escuro. A quinta e última definição foi a de Hiponímia e Hiperonímia, que indicam uma relação hierárquica entre palavras, por exemplo, carro é hiponímia de automóvel e automóvel é hiperonímia de carro. Repositórios interessantes para aplicações acerca de similaridade de palavras são os tesauros, que são dicionários para desambiguar palavras com significados em comum, sendo o mais famoso o wordnet. |
| Yago Sorrilha | Casamento aproximado entre strings -Distância de Hamming é utilizada para detectar erros nas transmissões binárias de comprimento fixo. Ela é a quantidade de bits usado na mudança de uma transmissão para a recepção -Distância de Levenshtein é usada para medir a quantidade de diferenças entre duas strings. Usando-se operações como inserção, exclusão e substituição, esta distância define o número mínimo de edições para transformar uma string em outra. Sejam a e b duas strings e sejam i e j o comprimento de a e b, respectivamente, se o comprimento de uma string for zero, então a distância será igual ao comprimento da outra string. Semântica e similaridade de palavras - Parte I Cinco definições importantes sobre 'significado' de palavras 1) Homônimos são palavras que compartilham a mesma forma mas com significados diferentes (origens diferentes). Podem ser homógrafos que tem a mesma escrita e homófonos que tem a mesma fala. 2) Polissemia é a propriedade de uma palavra tem de apresentar vários significados, uma palavra polissêmica tem significados relacionados (origens similares). Relações sistemáticas (metonímia): muitos tipos de polissemia são sistemáticos. Ex.: autor - obra, prédio - instituição, árvore - fruto. Como determinar se uma palavra tem mais de um significado? Usando o teste "Zeugma" (figura de linguagem ou estilo). Teste: se a construção não faz sentido (não é coerente), provavelmente a palavra seja polissêmica. 3) Sinônimos são palavras que tem o mesmo significado mas são escritas de maneira diferente. Duas palavras são sinônimos se podem ser substituídas em todas as situações 4) Antônimos são palavras que tem significado contrário 5) Hiponímia e Hiperonímia indicam relação hierárquica de significados entre palavras. Uma palavra é hiponímia de outra se o significado da primeira é mais específico que a segunda. O modo inverso é a hiperonímia. Um tesauro é um dicionário de ideias comuns. É usado para desambiguar o significado das palavras. Similaridade: duas palavras são similares se ambas compartilham o mesmo significado. Ela pode ser útil em diferentes tipos de aplicações como: recuperação de informação, detecção de plágio e agrupamento de textos. Versão mais flexível: a similaridade entre palavras pode ser estimada por uma medida de proximidade de significado: "Quase sinônimos" Algoritmos Duas abordagens para identificar similaridade: 1) Algoritmos baseados em tesauro: duas palavras são similares se uma é hiponímia de outra ou se compartilham da mesma definição 2) Algoritmos baseados em distribuição de palavras: não precisam de um tesauro, mas de um corpus grande no qual sejam envidenciados diferentes pares de palavras Similaridade usando tesauro: denominado "path based similarity" Duas palavras são similares se ambas estão na mesma hierárquia ou bem próximas. Pensamento computacional: a distância do menor caminho entre eles. Similaridade baseada em distribuição de palavras: não dependem de tesauros Palavras que estão em contextos similares, tender a ser semanticamente similares Distributional semantics e Vector Semantics O significado de uma palavra é calculado a partir da distribuição das palavras que estão ao redor dela. Matriz termo-documento: dois documentos são similares se os vetores são similares (vetores da frequência das palavras do vocabulário do documento) |
| Lucas Kenzo Kurokawa | A aula começa com proximidade de string na correção ortográfica e na biologia computacional. Para calcularmos a distância de strings, uma das métricas possíveis seria a distância de Hamming, onde medimos a quantidade de bits usado para mudança de uma transmissão para recepção (detectar erros em transmissões binárias e de comprimento fixo). A métrica mais usada para medir quantidade de diferenças entre strings é a distância de Levenshtein, que conta quantas operações de inserção, exclusão ou substituição são necessárias para transformar uma string na outra. Caso uma string seja vazia, ou seja, de comprimento nulo, a distância será igual ao tamanho da outra string. Um problema desta métrica é que existem casos em que temos 2 candidatos derivados de operações diferentes, mas uma maneira de desempatar, seria o uso de pesos nas operações. Outro problema é o custo operacional do algoritmo que é exponencial dependendo do tamanho do problema e por ser recursivo, existe overlap de subproblemas. Uma palavra (lemma) pode ter vários significados diferentes dependendo do contexto em que está presente. Por exemplo: o lemma banco pode ser instituição financeira, artefato, objeto assento. Estas palavras que compartilham a mesma forma são denominadas homônimos, sendo subdivididos em homógrafos (mesma escrita) e homófonos (mesma fala). Estes causam diversos problemas em tarefas de processamento de linguagem natural (PLN). Em recuperação de informação, a frase banco quebrado sem contexto não sabemos se refere-se à instituição financeira ou ao assento. Em tradução de texto, tendo o homônimo bat em inglês, ao se traduzir para o português não sabemos se devemos traduzir para bastão ou morcego. Em conversão de texto para voz (text-to-speech), tendo a entrada escrita bass podemos pronunciá-lo como o peixe ou como o instrumento musical. Outra propriedade importante das palavras é a polissemia, que é os vários significados relacionados (origem similares) a uma mesma palavra. Por exemplo, a palavra letra pode significar dependendo do contexto um elemento básico de um alfabeto, o texto de uma canção ou a caligrafia de um indivíduo. Para determinar se a palavra possui polissemia, usamos o teste de Zeugma, que basicamente analisa se a construção não faz sentido (sem coerência), se não fizer, provavelmente a palavra é polissêmica. Além disso, existem também os sinônimos, que são as palavras com mesmo significado em alguns ou todos os contextos, ou seja, poderiam ser substituídas em todas as situações sem alteração na semântica. Exemplo: água e H2O. Existem também os antônimos, que seriam similares aos sinônimos, mas que tem significado oposto. Exemplo: rápido e lento. Por último, existem as hiponímias e hiperonímias, que são palavras de mesmo grupo, mas mais específicas. Exemplo: um carro é um automóvel (carro é hiponímia de automóvel e automóvel seria hiperonímia de carro). Ao fim, vimos também sobre wordnet (base de dados de relações de palavras) para avaliar similaridade de palavras, correlatas, para detecção de plágio, agrupamento de textos, etc. Para isso, usamos algoritmos com tesauros (baseado em hierarquia) ou distribuição de palavras (significado calculado olhando vizinhos, TF-IDF). |
| Eracton Ferreira Ramalho | A oitava aula do curso começou com uma lista de exercício que teríamos 15 minutos para resolvê-la. Logo, já posso introduzir os dois assuntos da aula: Casamento aproximado entre strings e também semântica e similaridade de palavras - Parte I. Inicialmente vimos o conceito de String matching, que é uma classe importante de algoritmos de strings que tentam encontrar uma ou várias strings dentro de textos maiores. Isso serviu para introduzir o pensamento de encontrar as palavras mais próximas entre algumas opções. O primeiro conceito mais importante aprofundado foi à distância de Hamming, onde pressupomos duas grandezas de mesmo tamanho para fazer a comparação. Utilizado para detectar erros nas transmissões binárias de comprimento fixo. A distância de Hamming é a quantidade de bits usados nas mudanças de uma transmissão para a recepção. Já a distância de Levenshtein é usada para medir a quantidade de diferenças entre duas strings. Usando-se de operações como inserção, exclusão e substituição, esta distância métrica define o número mínimo de edições para transformar uma string em outra. No caso dos exercícios introdutórios, dependendo o peso para cada uma dessas três operações sabemos o que custa menos, logo está mais próximo, de uma palavra para outra. Um ponto importante que é concluído olhando bem a formula que está no slide é que se o comprimento de uma string for zero, então a distância será igual ao comprimento da outra string. Se o tamanho for diferente, analisar sempre de trás pra frente e ir comparando. Este algoritmo tem um custo muito alto. Ele repete os chamados, por isso gasta muito processamento. Como resolver isso? Utilizando programação dinâmica (inserir uma estrutura de memória para o programa). Essa parte que vamos falar agora está no mesmo livro da bibliografia, no capitulo 6. Vamos retornar a aula 4 e recordar as diferenças de Stemming e lemmatization. Podemos colocar o Stemming como uma ação para reduzir e chegar em Stems. Stem: parte de uma palavra. Stemmer: o artefato (programa). Já olhando o lemmatization podemos vê-lo como uma ação de reduzir em Lemmas. O Lemma seria a forma básica da palavra e o Lemmatizer o artefato (programa). Definimos também outra palavra wordform como uma palavra com inflexão. Interessante ver que um lemma pode ter diferentes significados. No exemplo dado, banco pode significar três objetos distintos. Entrando neste assunto, definimos homônimos: são palavras que compartilham a mesma forma, mas significados distintos. Esses homônimos são um problema em PLN. Como saber se uma palavra tem mais de um significado? Usando o teste de Zeugma. O que são sinônimos? Palavras com mesmo significado. E o que são antônimos? Palavras com significado oposto. O que é um Homógrafo? É a mesma forma de escrita (banco/banco). Já os homófonos, são a mesma forma de fala (Concerto/conserto). E o que é um tesauro? Um repositório, muito útil em PLN. Resumindo o Wordnet, o que ele faz? Ele desambigua o significado das palavras e é uma base de dados usado em linguística computacional. |
| Leonardo Nascimento | Considerando o vocabulário inglês e a palavra graffe, cuja não existe no vocabulário, as palavras graf, graft, grail e giraffe são possíveis candidatas em um contexto de correção ortográfica. Intuitivamente se poderia dizer que giraffe é a melhor candidata, por requerer apenas uma pequena mudança, a inserção do caractere i. Todavia, essa escolha depende de qual medida de similaridade está sendo usada. A distância de Hamming é uma medida utilizada para detectar erros nas transmissões binárias de comprimento fixo, representando a quantidade de bits alterados entre a emissão e a recepção. Assim, é uma medida com pouca utilidade prática, uma vez que representa o número de posições nas quais duas cadeias de caracteres de mesmo comprimento diferem entre si. Para duas cadeias de caracteres quaisquer, a distância de Levenshtein representa o número mínimo de edições para transformar uma cadeia de caracteres em outra. Contudo, o cálculo da distância de Levenshtein feito de maneira ingênua é problemático porque o algoritmo tem complexidade exponencial, mas isso pode ser ajustado usando memoization. Um stem é parte de uma palavra, um lemma é a forma sem inflexão de uma palavra, e um wordform é a palavra com inflexão. É interessante notar que um determinado lemma pode ter significados diferentes. Considere o lemma banco, este pode representar uma instituição financeira, um artefato para armazenamento ou um assento. Palavras que compartilham a mesma forma com significados diferentes são homônimos, que podem ser tanto homógrafos quanto homófonos. Palavras que são homógrafos compartilham a mesma forma de escrita, enquanto homófonos a mesma forma de fala. Isso é um problema para tarefas de recuperação de informação, tradução de textos e aplicações speech-to-text, pois o significado não está claro. Quando uma palavra tem vários significados com origens similares, propriedade conhecida como polissemia, há um desafio grande para o processamento de linguagem natural, assim como quando existem metonímias. Para determinar se uma palavra tem mais de um significado pode ser feito o teste zeugma, e se a construção não fizer sentido, sabemos que provavelmente a palavra é polissêmica. Sinônimos, antônimos, hiponímias e hiperonímias também são grandes desafios, e um artefato muito útil nesses casos de processamento de linguagem natural é o tesauro, um dicionário de ideias comuns usado para desambiguar o significado das palavras. Um tesauro popular é a wordnet, uma base de dados usada na área de linguística computacional elaborada em 1985, organizada hierarquicamente por meio de conjuntos de sinônimos próximos a uma palavra conhecidos como synsets. Construída originalmente em inglês, agora a wordnet contempla diversos idiomas. Avaliar a similaridade é importante para recuperação de informação, detecção de plágio e agrupamento de textos. Duas abordagens são: algoritmos baseados em tesauro e algoritmos baseados em distribuição de palavras. Para algoritmos baseados em tesauro podemos verificar se duas palavras estão na mesma hierarquia, e a biblioteca NLTK oferece métodos para esse cálculo. Em algoritmos baseados em distribuição de palavras consideramos algumas relações que não estão representadas no tesauro, como a evolução da semântica. |
| Laura Cestavo Borges Dos Santos | String matcing se refere a um casamento aproximado entre strings e está dentro do contexto de correção ortográfica. Existem dois algoritmos principais com relação a string matching, para definir qual a palavra mais próxima: Distância de Hamming e Distância de Levenshtein. Distância de Hamming é utilizado para detectar erros em transmissões binárias de comprimento fixo e nada mais é que a quantidade de bits usado na mudança de uma transmissão para a recepção. É um algoritmo bem simples, porém só funciona com palavras de mesmo comprimento. A distância de Levenshtein é usada para medir a quantidade de diferenças entre duas strings. Usa-se operações de inserção, exclusão e substituição e esta distância métrica define o número mínimo de edições para transformar uma string em outra. A segunda parte da aula foi focada em semântica e similaridade de palavras, para começar foram apresentados alguns conceitos. Na aula 4, vimos que existem algoritmos de stemming, onde se reduz a palavra em stems (parte da palavra), e de lemmatization, que reduzem em lemmas ( forma básica das palavra). Basicamente Lemma é a forma básica da palavra e Wordform é uma palavra com inflexão, um exemplo seria dormir (Lemma) e dormiu (Wordform). Lemmas podem ter significados diferentes, como a palavra banco que dependendo do contexto significa assento ou a instituição financeira. Palavras que compartilham a mesma escrita mas com significados diferentes, como a palavra banco em diferentes contextos, são chamados de homônimos. Eles se dividem em duas categorias: homógrafos e homófonos, os primeiros dizem a respeito de palavras com a mesma escrita e o segunda a palavras com a mesma fala. Homônimos são tópicos que criam problemas em PLN. Alguns outros tópicos cobertos em aula foram polissemia, que é a propriedade de uma palavra tem de apresentas vários significados, e metonímias. Para identificar se uma palavra tem mais de um significado usa-se o teste Zeugma. Nesse teste checa-se se a construção não faz sentido e caso não, ela provavelmente é polissêmica. Outras definições vistas forma hiponímia e hiperonímia. Dada duas palavras A e B, A é hiponímia de B se o significado de A é mais específico que B e se for ao contrário é hiperonímia. Duas palavras são similares se ambas compartilham o mesmo significado e é importante avaliar isso. Existem dois algoritmos para isso: baseado em tesauro e baseado em distribuição de palavras, que não precisa de um tesauro mas de um grande corpus. Os tesauros usam a estratégia de Path Based Similarity e duas palavras são similares se ambas estão na mesma hierarquia (ou bem próximas). O problema é que há uma dependência de um tesauro e também da completude das palavras, ou seja, não é flexível. Verbos e adjetivos não entram em tesauros, por exemplo. Usa-se, então, a abordagem baseada em distribuição de palavras, onde o significado da palavra é calculada a partir da distribuição de palavras ao redor dela e as palavras são representadas como um vetor de números. |
| Felipe Rigo Yoshimura | Na aula 8 de PLN foi apresentado a primeira parte dos conceitos de casamento aproximado de strings, utilizando semântica e similaridade de palavras. O string matching pode ser utilizado para correção ortográfica e no contexto de biologia computacional. Uma das distâncias que podem ser utilizadas é a distância de Hamming, a qual detecta erros de transmissão binária para mensagens de comprimento fixo, ou seja, quantos bits mudam da transmissão para a recepção. Outra distância que pode ser utilizada é a de Levenshtein, ela mede a quantidade de alterações que são necessárias para transformar uma string na outra utilizando operações de inserção, exclusão e substituição. Cada operação pode ser o peso balanceado ou não. Se o comprimento de uma string for zero, então a distância e Levenshtein é o comprimento da outra. Esse algoritmo tem complexidade exponencial, porem pode ser resolvido com programação dinâmica. Algumas definições importantes: stemming é o processo de reduzir a palavra até um radical, ou seja uma poda; lemmatization já é a ação de reduzir as palavras para sua forma do dicionário; wordform é uma palavra com inflexão. Um lemma pode ter significados diferentes e homônimos são palavras que compartilham a mesma forma mas com significados diferentes. Eles podem ser homógrafos, que indica que tem a mesma escrita, ou homófonos para a mesma forma de fala. Homônimos criam alguns problemas como recuperação de informação, tradução de textos, aplicação text-to-speech. Uma palavra polissemia possui muitos significados relacionados, porém com origem similar. Algumas relações entre as palavras são sistemáticas, conhecidas como metonímia. Para determinar se uma palavra tem mais de um significado, pode-se utilizar o teste de "Zeugma" unindo frases que tenha a dúvida em uma só e vendo se faz sentido. Sinônimos tem o mesmo significado e antônimos o oposto. Hiponímia e Hiperonímia indicam uma relação de hierarquia entre as palavras de mais e menos específico respectivamente. Wordnet é um tesauro, dicionário de ideias comuns, muito útil em PLN possuindo um repositório com relações hierárquicas entre as palavras. Já o synset é um conjunto de sinônimos próximos entre as palavras. Algumas aplicações utilizando avaliação de similaridade entre as palavras são: Recuperação de informação, Detecção de plágio, agrupamento de textos. As duas abordagens para esse problema são baseadas em tesauro e na distribuição das palavras utilizando um corpus grande para evidenciar diferentes pares de palavras. Um exemplo de algortimo baseado em tesauro é o "path based similarity", o qual diz que duas palavras são similares se estão próximas ou na mesma hierarquia. Como o tesauro pode ficar desatualizado, tornando o algoritmo não flexível, uma outra opção é utilizar o algoritmo baseada em distribuição de palavras. Palavras que estão em contextos similares, tendem a ser semanticamente similares, também conhecido como Distribution semantics e Vector semantics. Utilizando a matriz termo- documento, pode-se comparar as colunas para identificar documentos parecidos e as linhas para achar palavras parecidas, e assim criar um agrupamento hierárquico conseguindo capturar significado relacional. ~ ~ ~ ~ |
| Denildo Veloso Braga | Aula 8: Casamento aproximado entre String. String matching: comparação de similaridade entre strings dado um parâmetro para comparação. Possíveis aplicações: reconhecimento de sequências de aminoácidos. Medidas de distância: distância de Hamming: assume que as strings têm o mesmo tamanho, usado para identificar erros nas transmissões binárias, retorna a quantidade de caracteres diferentes, é fácil de implementar. Distância de Levenshtein: proposta nos anos 70, mede a quantidade de diferença entre duas strings, considera três operações: inserção, exclusão e substituição, essas operações podem ter pesos diferentes, a versão mais simples considera o mesmo peso para cada operação, muito usado nos algoritmos atuais, se o comprimento de uma string for zero então a distância de edição é o tamanho da outra string, sua deficiência é que é muito ineficiente, sendo um algoritmo exponencial. Existe uma variação do algoritmo de Levenshtein que considera um limite de caracteres diferentes, essa versão é mais rápida pois não calcula toda a matriz de diferença entre as strings. Semântica e similaridade de palavras: 5 definições importantes sobre significado de palavras: stemms: trunca a palavra, lemmas: reduz para a versão básica presente do dicionário. Um determinado lemma pode ter significados diferentes, associados a contextos diferentes. Homônimos: homófono: palavras com mesma pronúncia, homógrafo: palavras com mesma grafia, em ambos os casos, o sentido é diferente. Polissemia: palavra com vários significados, geralmente, têm origens similares. Muitos tipos de polissemia são sistemáticos. Teste Zeugma: serve para identificar se uma palavra tem mais de um significado, se a construção não é coerente, provavelmente a palavra tem mais de um significado. Sinônimo: palavras são sinônimas se podem ser substituídas em todas as situações, uma base de sinônimos famosa é o Synset. Antônimos: palavras com significados diferentes. Hiponímia e hiperonímia: indica relação de hierarquia entre palavras. Tesauro: é um repositório de palavras com significados semelhantes, dentro de um domínio específico, serve para destacar as diferenças entre palavras semelhantes, Wordnet é um dos maiores tesauros atuais. Palavras são similares se compartilham o mesmo significado. Avaliar similaridade é importante para detecção de plágio, recuperação de informação e agrupamento de texto. Uma versão mais flexível é considerar palavras correlatas, que são quase sinônimos. Existem dois algoritmos para identificar similaridade entre palavras: um verifica se uma palavra é hiponímia da outra usando tesauro ou se compartilham a mesma definição e a outra abordagem considera pares de palavras dado a distribuição de palavras em um corpus grande. Essa última abordagem não depende de um tesauro, que é difícil de construir e de manter atualizado. Palavras que estão próximas, ou seja, em contexto similares, tendem a ter o mesmo significado, isso é conhecido como vector semantics ou distributional semantics. O significado de uma palavra é calculado com base na distribuição de palavras ao seu redor. Matriz termo-documento: associa a quantidade de vezes que termos aparecem em documentos. Dois documentos são similares se seus vetores de vocabulários são similares, duas palavras são similares se seus vetores são similares. |
| Rodolfo Azevedo Dos Santos | Casamento aproximado entre strings String matching: Contexto de biologia computacional: \- Alinhamento de sequências (para ver se uma sequência é similar a outra). Isso é feito através de algoritmos Distância de Hamming: Quando falamos de similaridade falamos de distância. Pressupõe que as palavras possuem o mesmo comprimento. Compara elemento a elemento e retorna a quantidade de elementos diferentes entre eles. A implementação é um laço for. É a medida mais básica de comparação. Ex: PLN e PNL = 2 (distância de Hamming). UFABC e UFRJ = -1 (pois os comprimentos são diferentes. Apenas compara se os comprimentos das duas cadeias são iguais). Distância de Levenshtein: Usado para medir a quantidade de diferenças entre duas strings. Utiliza operações de inserção, exclusão e substituição. Define o número mínimo de edição para transformar uma string em outra. Se uma das strings é nula (zero), a distância de edição é o maior tamanho (é a outra string): Esse é o caso base. Deficiência do algoritmo: Complexidade computacional exponencial, logo é muito caro. Isso ocorre porque repete os chamados. Para melhorá-lo utiliza-se programação dinâmica (memorização), que é a inclusão de uma estrutura de memória ao algoritmo. Sempre que há a pergunta sobre similaridade entre palavras é necessário estabelecer qual a medida de distância adotada. Semântica e similaridade de palavras (parte 1): Cinco definições importantes sobre o significado das palavras: Stemming: parte de uma palavra (truncada) Lemmatization: Leva a palavra para sua forma básica (forma sem flexão dicionário) Um determinado lemma pode ter significados diferes: Ex: Banco (pode ser instituição financeira, assento, artefato computacional) Mesma escrita, distância idêntica. 1) Homônimos: Homógrafos Mesma escrita Homófono: Mesma fala Homônimos criam problemas em PLN. Ex: Banco quebrado (instituição falida ou assento quebrado?) 2) Polissemia: Muitos significados relacionados a palavra. Como determinar computacionalmente se uma palavra tem mais de um significado? Teste de Zeugma (figura de linguagem) Se a construção não faz sentido (não é coerente) provavelmente a palavra é polissêmica. 3) Sinônimos: Palavras que tem mesmo significado porém escritas diferentes. São sinônimos se podem ser substituídos em todas situações. 4) Antônimos: Oposto 5) Hiponímia e Hipernonímia: Hipo (sub) e Hiper (super), relação de hierarquia entre as palavras Tesauro: Repositório (dicionário de ideias comuns) O mais comum é o Wordnet (em inglês). É utilizado desde 95 para desambiguar o resultado. Synset: Sinonym set Entrada: palavra Resultado: Todos sinônimos Em português existem dois tesauros. Deficiência: Muito esforço para construir, específico para cada contexto (não é dinâmico) Similaridade entre palavras: Similares se ambas compartilham mesmo significado. Importância: Recuperação de informação, detecção de plágio, agrupamento de texto. Algoritmos: 1) Baseados em tesauros 2) Baseados em distribuição de palavras: Não usam tesauros. Necessitam de corpus grande. Semântica evolui ao longo do tempo Computacionalmente: Distância entre palavras é o menor caminho entre elas. (pathlen). Matriz termo-documento: Termo (linha), documento (coluna). Junção das duas é a frequência. Documentos são similares se vetores são similares. Distância euclidiana entre dois vetores retorna a similaridade. |
| Carlos Eduardo Ramos | O tema da aula foi relacionado com o casamento aproximado entre stings, levando em conta a semântica e a similaridade das palavras. Em algumas partes do processamento de linguagem natural, queremos medir o quanto duas strings são semelhantes. Um exemplo seria a correção ortográfica, onde o corretor sugere ao usuário, ao digitar uma palavra errada, palavras candidatas que se pretendia digitar. O conceito de Distância de Hamming foi apresentado, onde distância de Hamming é a quantidade de bits usado na mudança de uma transmissão para a recepção. Outro conceito é o de distância de Levenshtein, que é usado para medir a quantidade de diferenças entre duas strings, considerando operações de inserção, exclusão e substituição de caracteres. Na distância de Levenshtein, podemos atribuir um peso específico a cada uma dessas operações, onde cada uma delas pode ter peso 1 O algoritmo para medir a distância de Levenshtein foi apresentado, bem como uma ferramenta online que faz a operação. Visto isso, os conceitos de stemming ( ação de reduzir palavras em stems - partindo a palavra) e Lemmatization (ação de reduzir a palavra em Lemmas, obtendo a forma básica seguindo uma heurística) foram revisados. Lemma é definido como a forma básica de uma palavra, sem realizar inflexões, e de acordo com um dicionário. Cada lemma pode ter vários significados, e isso pode dificultar a interpretação. Lemmas homônimos compartilham a mesma forma, mas a o lemma tem significado diferente. Dentre os lemmas homônimos, eles pode ser Homógrafos, com a mesma forma escrita; ou homófonos, com a mesma forma de fala (som). Wordforms é uma palavra com inflexão. O conceito de polissemia trata a propriedade das palavras terem vários significados relacionados, mas não exatamente iguais. Uma modalidade de polissemia é a metonímia, onde temos casos de palavras diferentes, mas que podem significar a mesma coisa. Exemplo: Prédio se referindo a uma Organização. O teste ZEUGMA pode determinar se há mais de um significado para uma palavra. Este teste verifica se a construção não faz sentido lógico, e se não houver sentido, provavelmente a oração possui uma palavra polissêmica. Nos sinônimos, diferentes palavras possuem significados iguais em alguns ou todos os contextos, ou seja, podemos substituir esses sinônimos sem perda de informação - o significado proposicional é o mesmo. Do contrário, com palavras de significado proporcional oposto, temos os antônimos. O repositório WordNet da Universidade de Princeton foi apresentado, onde Wordnet é uma base de dados usados na área de Linguística computacional, usado para tornar o significado das palavras não ambíguo. O wordnet é um dicionário de ideias comuns, um tesauro, que lista palavras com significados semelhantes. O wordnet pode ser usado para avaliar a similaridade de palavras. O wordnet é hierarquizado, e duas palavras são similares se ambas estão no mesmo nível de hierarquia ou bem próximas. Essa abordagem depende de um tesauro, e da completude das palavras. Outra abordagem é a baseada na distribuição de palavras, predizendo um significado pelo contexto. |
| Thiago Bruini Cardoso Silva | A oitava aula da disciplina foi centrada em dois temas principais: "Casamento aproximado entre strings" e "Semântica e similaridade de palavras". O primeiro assunto a ser explorado foi o casamento aproximado entre strings. Para se ter uma noção inicial da dificuldade encontrada nessa tarefa, foi realizada uma atividade em que deveríamos estabelecer um raciocínio para definir palavras mais próximas. Uma forma de definir, entre uma coleção de palavras Xi, qual é a mais próxima de outra palavras Y é por meio da distância de Hamming, que trata-se do número de bits de diferença que há entre duas strings. O problema dessa abordagem é a necessidade de que as duas strings a serem comparadas tenham tamanhos iguais. Um cálculo de distância mais sofisticado é a Distância de Levenshtein, sendo seu cálculo realizado pela contagem de operações de inserção, remoção e substituição que são necessárias para transformar a palavra Xi na palavra Y. "Casa" e "Gata" têm distância de Levenshtein igual a 2 por exemplo. Tivemos definido então que o cálculo de distância de edição entre duas palavras é realizado baseando-se na distância de Levenshtein. Para começar o estudo sobre semântica em PLN, foi necessário estabelecer 5 definições importantes considerando lemmas de palavras: 1 - Homônimos são palavras com forma igual, porém, significado semelhante. Caso essa forma seja somente na escrita, definimos como homógrafos. Caso essa forma seja referente à pronúncia, chamamos de homófonos. 2 - Polissemia é a propriedade presente em palavras que possuem muitos significados. "Banco", por exemplo, pode se referir ao assento ou à instituição financeira. 3 - Sinônimos refere-se a palavras diferentes que possuem um mesmo significado. "Caderno" e "caderneta" são sinônimos por exemplo. 4 - Antônimos são palavras opostas em relação a determinada característica. "Alto" e "baixo" são antônimos. 5 - Hiponímia e hiperonímia são relações de ordem entre palavras. "Carro" é mais específico do que "automóvel", portanto, "carro" é hiponímia de "automóvel" e "automóvel" é hiperonímia de "carro". A partir dessas definições, foi explorado o conceito de wordnet. A wordnet é um tesauro, dicionário de "ideias comuns", utilizada para desambiguar significado de palavras. Nele é possível encontrar relações entre palavras, como, por exemplo, seus sinônimos. Duas palavras são consideradas similares se compartilham o mesmo significado. Esse conceito é importante para trabalhos de detecção de plágio por exemplo, em que a troca de palavras por sinônimos não será eficiente para enganar um avaliador. A similaridade entre palavras não refere-se somente a sinônimos, mas a termos próximos. "Bicicleta" está próxima de "Carro" por exemplo. O primeiro algoritmo para cálculo de similaridade visto foi baseado em tesauros, onde é construída uma árvore de conceitos próximos e, quanto mais próximos dois termos, maior será a similaridade. O segundo algoritmo a tratar essa questão é baseado na distribuição de palavras. Palavras próximas em contextos similares são similares. As palavras passam então a ser representadas por vetores de números ao invés de N-gramas. |
| Eduardo Haberler Cardoso | A aula 8 de PLN, ministrada dia 03 de Julho, teve como tema central o casamento aproximado entre strings baseado na semântica e similaridade de palavras. No início da aula. como forma de contextualização dos problemas que são tratados com este tema, o professor passou alguns exemplos de palavras similares e levantou reflexões a respeito de quais palavras seriam mais similares, a resposta é depende do critério utilizado. Iniciamos considerando o critério de distância de Hamming, que tem papel relevante na detecção de erros nas transmissões binárias de comprimento fixo, basicamente é a diferença entre duas strings de mesmo tamanho. Neste caso, quaisquer operações de inserção, exclusão ou substituição possuem o mesmo peso. Em seguida vimos a distância de Levenshtein que é análoga à distância de Hamming, porém dispensa a necessidade das cadeias serem do mesmo tamanho. Neste caso, se uma cadeia for maior que a outra, a distância de Levenshtein será no mínimo a diferença entre as duas. Outra diferença é que a substituição, neste caso, possui peso 2 na contagem da distância. Por exemplo, as cadeias "mesa" e "mesas" possuem distância 1, já as cadeias "cerveja" e "cereal" possuem distância 7, pois são 3 substituições e uma inserção. Na segunda parte da aula, apresentou as 5 definições importantes sobre o significado de palavras, sendo elas: Homônimos: São palavras que são escritas (homógrafas) ou faladas (homófonas) da mesma forma mas possuem significados diferentes; Polissemia: palavras que podem significar várias coisas diferentes; Sinônimo: Palavras escritas e faladas de forma diferente, mas que possuem o mesmo significado; Antônimos: Palavras que possuem significados opostos; Por último foram apresentados os conceitos de hiponímia e hiperonímia, que são definidos em conjunto, pois um está relacionado ao outro. Uma palavra A é hiponímia da outra, B, se A é mais específico que B, i.e., B é uma macro categoria de A. Outra definição importante foi sobre o tesauro. Tesauro é um dicionário de "ideias comuns". Logo após, foi apresentada a definição de similaridade, que está relacionada ao significado das palavras. Portanto duas palavras são similares se possuem o mesmo significado, i.e., se são sinônimos ou hiponímias/hiperonímias entre si, que varia com o contexto de aplicação. Foi apresentado um algoritmo chamado path based similarity, que compara as palavras usando o tesauro. Uma vez que as palavras estiverem na mesma hierarquia ou estão próximas o suficiente, elas são consideradas similares. Para o cálculo de similaridade entre duas palavras,podemos utilizar o NLTK do python. Em seguida foi discutida uma abordagem que não leva em consideração o tesauro, apenas a similaridade baseada no contexto, partindo da premissa de que "palavras que estão em contextos similares, tendem a ser semanticamente similares". A partir desta abordagem, é possível discutirmos a matriz termo-documento que diz que "dois documentos são similares se os vetores são similares", onde os elementos dos vetores são os termos utilizados no documento. |
| Matheus Tulio Pereira da Cruz | Proximidade de palavras depende da medida que está em questão. String matching - casamento de palavras Distância de Hamming - é a quantidade de bits usados na mudança de uma transmissão para a recepção. Mas pode ser aplicada a cadeias de palavras, ou seja, ao invés de comparar bits, são comparados caracteres. Distância de Levenshtein - É usada para medir a quantidade de diferenças entre duas strings. Usando as operações como inserção , exclusão e substituição, está distância métrica define o número mínimo de edições para transformar uma string na outra. Para que o algoritmo de distância de Levenshtein seja eficiente é necessário que se use programação dinâmica (memoization), uma vez que ele realiza muitas chamada de comparação repetidas, então se tivesse gravado cada vez que um tipo de comparação fosse feita, não seria preciso rodar a função novamente, apenas acessar uma memória que tem o valor guardado. Quando se carece de conhecimento de alfabeto, ou dos vizinhos, a técnica de casamento aproximado entre strings é melhor do que a técnica de n-gramas que usa probabilidade. Stem: parte de uma palavra Lemma: é a forma básica da palavra. (A versão do dicionário, versão sem inflexão) Um lemma pode ter significados diferentes se aplicados em contextos diferentes. Homônimos : palavras que compartilham a mesma forma, mas com significados diferentes. Homógrafo Homófono Polissemia é a propriedade de uma palavra ter múltiplos significados. Muitos tipos de polissemia são sistemáticos. Comparações entre organizações <> prédios, autor <> trabalho do autor e árvore <> fruto. O teste de Zeugma determina se uma palavra tem mais de um significado. O teste construi uma frase juntando duas frases onde s palavra é usada e se a construção não faz sentido, então provavelmente a palavra seja polissêmica. Para o teste dar certo, é preciso ter uma base de dados grande. Sinônimos são palavras que possuem o mesmo significado mas são escritas diferentes. Antônimos são palavras que tem significado oposto em relação a uma característica. Hiponímia e Hiperonímia indicam relação hierárquica se significados entre palavras. Hipo está relacionado com sub e Hipe com super. Tesauro é um dicionário de ideias comuns. O Wordnet é o maior tesauro do mundo. Duas palavras são similares se possuem o mesmo significado. Avaliar similaridade é importante para recuperação de informação, detecção de plágio, busca por elementos similares, agrupamento de textos, entre outras coisas. A similaridade entre palavras pode ser estimada por uma medida de proximidade de significado: quase sinônimo. Duas abordagens são: - algoritmos baseados em tesauro - duas palavras são similares se as palavras estão na mesma hierarquia ou bem próximas. Pathlen(c1.c2) = 1 + comprimento do caminho entre c1 e c2 na árvores de hiponímia. - Algoritmos baseado em distribuição de palavras - não depende de um tesauro e os tesauros são pouco dinâmicos e podem ficar desatualizados. Palavras são similares se estão em contextos similares. O significado de uma palavra é baseado na distribuição de palavras ao redor dela. |
| Marcio Jose de Carvalho | O tema da aula 8 foi semântica e similaridade de palavras, iniciamos com exemplos de correção ortográfica e biologia computacional. Dois conceitos que vimos: Distância de hamming é conta de bits na mudança de transmissão para recepção; Distância de levenshtein mede a quantidade de diferenças entre duas strings, por inserção, exclusão ou substituição. Passamos para cinco definições importantes sobre o significado de palavras. Diferença de stemming e lemmatization. Stem é parte de uma palavras, e Lemma é a versão da palavra no dicionário. A versão com inflexão de uma lemma é chamada de wordform. O mesmo lemma pode ter significados diferentes, e isso nos leva aos conceitos que vamos definir. Homônimos são lemmas iguais com significados diferentes, pois tem origens diferentes. Homônimos causam problemas em pln, em particular em queries, tradução e conversão de texto para som, onde o lemma tem pronúncias diferentes para os diferentes significados. Polissemia é o mesmo lemma ter significados diferentes em contextos diferentes. Muitos casos de polissemia são sistemáticos, ou seja, os significados são diretamente relacionados, como universidade que pode ser a instituição ou o prédio, e pessoas que produzem algo, como escritores ou músicos, em que o nome pode ser usado para se referir à obra deles. Uma forma de testar polissemia é um teste de Zeugma, que é aplicar os diferentes significados a todos os contextos e verificar se essas construções fazem sentido coerente. Sinônimos e antônimos são conceitos relacionados. Tratam da relação de significado de palavras que tem forma diferente. Sinônimos são palavras que podem ser trocadas entre si, na maioria dos contextos, sem perda de coerência. Antônimos são palavras cuja substituição causa a negação do significado da outra. Hiponímia e hiperonímia se referente a classes de palavras e relações de hierarquia de significado. Hiponímia é uma palavra que é mais específica que outra, como carro e automóvel, ou maçã e fruta, sendo hiperonímia o inverso. Vimos o Wordnet, banco de dados de relações de similaridade entre palavras, da universidade Princeton, também pode ser considerado um tesauro. Algoritmos para relacionamento de palavras por similaridade apresentam várias aplicações, e geralmente são de dois tipos, baseados em tesauros ou corpora muito grandes. Algoritmos baseados em tesauro utilizam estruturas de grafos para mapear relacionamentos, como árvores em que conceitos mais abstratos ficam em alturas menores. A distância (caminho) entre duas palavras determina sua similaridade, porém é necessário se atentar para o nível de abstração do caminho. Assim, pode-se complementar essa abordagem com a atribuição de pesos baseado em similaridade de contextos, o que é obtido com análise de frequência em corpora curados. A abordagem por frequência de ocorrência em contextos similares é importante para capturar a qualidade dinâmica das linguagens naturais, algo que a estrutura rígida de um tesauro não permite. Por último, vimos o conceito de matriz termo-documento, para calcular similaridade de textos. |
| Brian Alves Andreossi | Aula 7 Casamento aproximado entre strings Semântica e Similaridade de palavras \- Exemplo: No contexto de correção ortográfica, a palavra mais próxima de graffe é giraffe Uma área que tem interesse neste tema de PLN é a biologia informática. Distância de Hamming \- Utilizado para detectar erros nas transmissões binárias de comprimento fixo. \- A distância de Hamming é a quantidade de bits usado na mudança de uma transmissão para uma recepção. Exemplo: hamming("PLN", "PNL") -> 2 hamming("UFABC", "UFRJ") -> -1 (quando a palavra não tem o mesmo comprimento, ela é considerada inválida) Distância de Levenshtein \- Usada para medir a quantidade de diferenças entre duas cadeias. \- Usando-se de operações como inserção, exclusão e substituição, esta distância métrica define o número mínimo de edições para torna-las a mesma palavra. Exemplo: levenshtein("casa", "pata") = 2 Este algoritmo é um exemplo clássico da aplicação da técnica de memoização (Análise de Algoritmos). Consegue transformar uma versão recursiva em uma versão matricial, geralmente mais barata Stemming vs Lemma Lema: versão não flexionada. Stem: corte puro da palavra. Homônimos Palavras que compartilham a mesma forma mas com significados diferentes (origens diferentes). São problemáticos em PLN, exemplo: "Banco quebrado" (a instituição ou o artefato)? Polissemia Propriedade de uma palavra de possuir diversos significados Relações Sistemáticas (metonímia) Muitos tipos de polissemias são sistemáticas Eu amo J.K.Rowling (Padrão Autor e seus trabalhos) Eu vou a escola (padrão prédio-organização). Como determinar se uma palavra tem mais de um significado? Teste Zeugma Se a junção de 2 amostras das frases contendo uma certa palavra e perder a coerência, provavelmente será polissêmica. Sinônimos Palavras com o mesmo significado porém com grafia diferente. Palavras que podem ser trocadas pelo seu par em todas as situações. Antônimos Palavras que tem conceito contrário. Hiponímia e Hiperonímia Relação de hierarquia entre as palavras \- Carro é hiponímia de Automóvel (Automovél é hiperonímia de carro) \- Sandálias é hiponímia de calçado Wordnet (Tesauro) Base de dados usada na área de linguística computacional. Usado para desambiguar o significado. Importância da avaliação de similaridade: \- Plágio \- Agrupamento de objetos. Formas de encontrar similaridade entre palavras 1\. Algoritmos baseados em tesauro: Duas palavras são similares se estão na mesma hierarquia É possível gerar árvores com as hierarquias, e calcular as distâncias e gerar a similaridade a partir disso. comprimento do caminho = arestas entre as palavras + 1 similaridade = 1/comprimento do caminho 2\. Baseado em distribuição de palavras É necessário pois as abordagens anteriores são dependentes de tesauros. Dependem da completude das palavras. Nem todas as relações estão mapeadas. Eventualmente, as palavras perdem e ganham significado. Chaves: Distributional semantics, vector semantics Duas palavras são similares se estão em contextos similares Matriz termo-documento Dois documentos são similares se os vetores são similares. Ou seja, se as palavras que os compõem tem frequência parecida. Essa matriz permite criar agrupamento hierárquico |
| Caique de Camargo | Aula do dia 01 de julho de 2019 com o tema "casamento aproximado entre Strings". Foram apresentados os conceitos de distância entre palavras, uma delas, chamada de Distância de Hamming que é a quantidade de bits utilizados na mudança da transmissão para a recepção. e a Distância de Levenshtein que é utilizado para medir a quantidade de diferença entre duas strings. Usando-se de operações como inserção, exclusão e substituição, esta distância métrica define o número mínimo de edições para transformar uma string em outra. Por exemplo, a distância de Levenshtein entre casa e pata é 2. Se o comprimento de uma string for zero, então a distância será igual ao comprimento da outra String. Lemma: é a forma básica da palavra (sem inflexão, e um determinado Lemma pode ter significados diferentes); Wordform: é uma palavra com inflexão. Existem cinco definições que são de extrema importância sobre o significado de palavras: 1) Homônimos: São palavras que compartilham a mesma forma mas com significados diferentes (origens diferentes); Homônimos podem ser homógrafos, i.e., mesma forma de escrita (banco/banco) ou homófonos, i.e., mesma forma de fala (Concerto/conserto). Homônimos criam muitos problemas em PLN, como em recuperação de informação, tradução e em aplicações text-to-speech; 2) Polissemia (muitos significados): é a propriedade de uma palavra tem de apresentar vários significados. Uma palavra polissêmica tem significados relacionados. E as metonímias. Para determinar se uma palavra tem mais de um significado é utilizado o teste de Zeuma, se a construção não faz sentido (coerente), provavelmente a palavra seja polissêmica. 3) Sinônimos: Palavras que tem o mesmo significado em alguns ou todos os contextos. Palavras são consideradas sinônimos se podem ser substituídas em todas as situações e se tem o mesmo significado proposicional. 4) Antônimos: Palavras que tem significado oposto em relação a uma característica. 5) Hiponímia e Hiperonímia: Uma palavra A é hiponímia de B se o significado de A é mais específico que o de B e o inverso é hiperonímia. Wordnet: é uma base de dados muito útil em PLN, se trata de um tesauro e é utilizado para desambiguar o significado de palavras. Um Synset é um conjunto de sinônimos próximos a uma palavra. Se duas ou mais palavras compartilham o mesmo significado são ditas similares e pode ser utilizados em diversos contextos de PLN, como recuperação de informação, detecção de plágio e agrupamento de textos. Existem duas abordagens para a identificação de similaridade entre palavras,a primeira com um algoritmo baseado em tesauros e outro baseado na distribuição de palavras, tendo um corpus grande e evidenciando diferentes pares de palavras. O NLTK oferece métodos para cálculo de similaridade de palavras baseada em wordnet. E também são utilizados matrizes termo-documentos para a detecção de similaridade entre documentos. |
| Pedro Ricardo Bronze | Similaridade de palavras. Iniciamos a aula com o quiz sobre distância de edição. Biologia molecular é uma das áreas principais na qual a computação e alinhamentos de bases nitrogenadas (ATCG). Na distância de Hamming o pressuposto é que o tamanho dos elementos é igual, e os caracteres diferentes são contados para se calcular a distância. Na medida Levenshtein mede-se a quantidade de diferenças entre duas strings, sendo que exclusão, inserção e substituição tem o mesmo peso cada. Um dos problemas desta distância é que ela tem complexidade exponencial, O(n^2). Uma forma de mitigar este problema é utilizar 'memoization', para armazenar na memória combinações consideradas em iterações anteriores. A medida de distância é fundamental quando consideramos calcular similaridade entre termos. Homônimos podem criar problemáticas para o PLN, em recuperação de informação, tradução de textos e aplicações text-to- speech. 2) Polissemia é a propriedade de uma palavra que apresenta vários significados. Em se tratando de polissemias sistemáticas temos exemplos de metonímia onde podemos analisar os diferentes significados. Um exemplo quando se escreve 'Rádio' podemos nos referir ao prédio da rádio ou à organização. O teste 'Zeugma' consiste em checar se a construção faz sentido, se não fizer provavelmente a palavra é polissêmica. 3) Sinônimos são palavras que podem ser utilizadas com o mesmo significado em todos os contextos, com mesmo significado proposicional. 4) Antônimos são palavras com sentidos opostos (claro/escuro, quente/frio) 5) Hiponímia e Hiperonímia indicam relação de hierarquia entre palavras, A é hiponímia de B se o significado de A é mais específico que B, sendo hipernímia o oposto. Tesauro é um dicionário de ideias comuns, um dos maiores é o Wordnet e temos outros em diferentes idiomas. Porque é importante o conceito de similaridade? Recuperação de informação, detecção de plágio textual e agrupamentos de textos. 1/Pathlen é uma das formas de medir similaridade, sendo pathlen = 1 + comprimento do caminho entre c1 e c2 na árvore de hiponímia. O significado de termos muda com o tempo em alguns casos e isso é uma coisa importante a se considerar, assim como as palavras correlatas também. Palavras que estão em contextos similares tendem a ser semanticamente similares. A distribuição de palavras que acompanham as palavras que estudamos nos auxiliam a entender o significado dela, principalmente útil quando uma palavra não está presente num tesauro utilizado. Através da Matriz termo-documento podemos podemos avaliar a similaridade de documentos se os vetores de contagem de palavras são similares entre si. E duas palavras são similares se os vetores de suas contagens por documento são similares entre si. Através disso podemos realizar agrupamento hierárquico de similares e inclusive de relações por exemplo 'rei' está para 'homem' como 'rainha' está para 'mulher'. |
| Fabio Figueiredo Rodrigues | A aula oito de Processamento de Linguagem Natural abordou os temas "Casamento aproximado entre strings" e "Semântica e similaridade de palavras". Inicialmente foi apresentado a Distância de Hamming, que é utilizado para detectar erros em transmissões de comprimento fixo. Portanto, este algoritmo, quando comparando duas strings de mesmo comprimento, retorna o número de posições nas quais os caracteres diferem entre si. Já a Distância de Levenshtein é usada para medir a quantidade de diferenças entre duas strings. Usando-se de operações como inserção (peso 1), exclusão (peso 1) e substituição (peso 1), esta distância métrica define o número mínimo de edições para transformar uma string em outra. Portanto, podemos utilizar esta técnica para medir a distância entre duas strings de tamanhos distintos. Retomando um pouco a aula 4 para partir para o segundo tema da aula, o Stemming consiste na ação de reduzir em stems (parte de uma palavra), enquanto o Lemmatization é a ação de reduzir em Lemmas (forma básica da palavra). Tendo isto, um determinado lemma pode ter significados diferentes, que é chamado de homônimos. Por exemplo, banco pode ser uma instituição de madeira, um artefato para armazenamento de dados ou assento. Os homônimos podem ser homógrafos (mesma forma de escrita) ou homófonos (mesma forma de fala). Caso uma palavra apresente significados relacionados, isto é chamado de polissemia. Por exemplo, vela: de um barco, para iluminar, de vigilante. Alguns tipos de polissemia são sitemáticos (metonímia), como na frase "Eu amo Shakespeare" que pode significar amar o autor (pessoa) ou então as obras do autor. Para determinar se uma palavra tem mais de um significado, podemos utilizar o teste "Zeugma", que caso a construção não seja coerente, provavelmente a palavra seja polissêmica. Temos também os sinônimos, que são palavras diferente que possuem o mesmo significado, como por exemplo, caderno e caderneta. Ambas podem ser substituídas em todas as situações e elas possuem o mesmo significado proposicional, portanto, são sinônimos. Os Antônimos são as palavras que tem significado oposto em relação a uma característica, como por exemplo, escuro e claro. Por fim, temos as Hiponímias e as Hiperonímias, que indicam relação hierárquica de significados entre palavras. Uma palavra A é hiponímia de B, se o significado de A é mais específico que B, e caso inverso, ela é hiperonímia. Dica: Wordnet é uma base de dados usada na área de linguística computacional, em inglês, que é utilizada para desambiguar o significado das palavras. Se duas palavras compartilham o mesmo significado, elas são ditas palavras similares, e para identificar isto, podemos utilizar duas abordagens: algoritmos baseados em tesauro (dicionário de ideias comuns) ou aqueles baseados em distribuição de palavras (corpus grande evidenciando diferentes pares de palavras). |
| Tiago Suzukayama | O tema desta aula foi o casamento aproximado entre strings. Num contexto de correção ortográfica, sabemos que "Graffe" é mais próximo de "Giraffe". A distância de Hamming é utilizada para detectar erros nas transmissões binárias de comprimento fixo. Ela também é a quantidade de bits usado na mudança de uma transmissão para a recepção. A distância de Levenshtein é usada para medir a quantidade de letras diferentes entre duas strings. Usando operações como inserção, exclusão e substituição, esta distância métrica define o número mínimo de edições para transformar uma string em outra. Como exemplo, as palavras "casa" e "pata" possuem distância de levenshtein de 2, pois não há forma de transformar uma em outra com menos de duas edições. De forma geral, se o comprimento de uma string for zero, então a distância será igual ao comprimento da outra string. Na distância de Levenshtein, inserção e eliminação possuem peso +1, e substituição possui peso +2. Revisando alguns conceitos da aula passada, vimos as diferenças entre stemming e lemmatization. O primeiro reduz parte da palavra, e o segundo reduz a palavra na sua forma básica. Já a diferenças entre Lemma e Wordform é que a primeira é a forma básica da palavra, sem inflexão, e a segunda é a palavra com inflexão. É importante saber cinco definições sobre "significado de palavras": 1) Homônimos - são palavras que compartilham a mesma forma mas com significados diferentes. Podem ser da mesma forma de escrita, ou homógrafos (banco/banco), ou da mesma forma de fala, ou homófonos (Concerto/conserto). Homônimos criam problemas em PLN, em recuperação de informação, tradução de textos e em aplicações text-to-speech. 2) Polissemia - é a propriedade de uma palavra que tem de apresentar vários significados, por exemplo, letra pode ser um elemento básico do alfabeto, um texto de uma canção ou a caligrafia de um indivíduo. Polissemias podem ser sistemáticas. 3) Sinônimos - palavras que tem o mesmo significado em alguns ou todos os contextos. São sinônimas se ambas podem ser substituídas em todas as situações, ou ambas têm o mesmo significado proposicional. 4) Antônimos - palavras que tem significado oposto em relação a uma característica. 5) Hiponímia e hiperonímia - indicam relação hierarquica de significados entre palavras. Wordnet é um base de dados usada para desambiguar o significado das palavras. Synset é um conjunto de sinônimos a uma palavra. Duas palavras são similares se ambas compartilham o mesmo significado. É importante avaliar sua similaridade para recuperação de informações, detecção de plágio e agrupamento de textos. A similaridade pode ser estimada por uma medida de proximidade de significado, por duas abordagens: algoritmos baseados em tesauros, ou algoritmos baseados em distribuição de palavras. |
| Augusto Goncalves da Silva | Similaridade de palavras diz respeito ao quão próximas são duas palavras, a ponto de poderem ser substituídas umas pelas outras. Distância de hamming indica a quantidade de elementos em posições iguais dentro de duas cadeia s de mesmo comprimento. Medida apenas pelo número de diferenças entre as cadeias. Distância de Levenshtein mostra a quantidade de diferenças entre os elementos dentro de uma cadeia, considerando possibilidades de erros, como inserção, exclusão e substituição. Medida a partir da quantidade de modificações que necessitam ser feitas para que as cadeias se tornem iguais. Porém, a execução desse algoritmo é custosa, devido a suas diversas chamadas recursivas. Considerando-se as distâncias básicas entre caracteres, sem levar em conta outras similaridades (como fonéticas), "Mario" é igualmente substituível por "Marie" e "Maryo". Existem diversos algoritmos para aproximação de palavras, dependendo de sua aplicação, cada um deles pode ser mais eficiente (em termos de execução e resultados). Para melhores resultados, algoritmos mais elaborados são necessários, que apliquem algumas definições linguísticas para calcular a similaridade entre palavras. Palavras Homônimas: possuem a mesma forma escrita (homógrafo) ou a mesma forma fonética (homófono). O pior problema dessas palavras é a diferença de significado entre elas, apesar de serem parecidas. Polissemia: palavras com uma grande quantidade de significados. O problema de palavras com polissemia é a identificação do significado correto (muitas vezes não literal). Como determinar se uma palavra tem mais de um significado? Podemos utilizar o teste de Zeugma, que diz que se a construção de uma frase juntando os dois contexto não faz sentido, então provavelmente a palavra é polissêmica. Sinônimos: são palavras com o mesmo significado, mas com escritas diferentes. São sinônimas as palavras que podem ser substituídas umas pelas outras em qualquer situação. Antônimos: palavras de significado contrário. Hiponímia e Hiperonímia: são palavras semelhantes quando considera-se suas "hierarquias", como combinar "prédio" e "construção" (o prédio é uma construção - prédio é uma hiponímia de construção, enquanto construção é uma hiperonímia de prédio). Podemos também dizer que palavras são similares se parecem-se em seus significados. Este conceito é frequentemente utilizado em detecção de textos com o mesmo conteúdo (possíveis plágios). Duas abordagens muito utilizadas: 1- baseada em tesauros: encontram similaridade em palavras que são sinônimas ou relacionadas com outras. Duas palavras são similares se estão na mesma hierarquia de generalidade, e seu grau é medido com a distância entre elas. 2- baseada em distribuição de palavras: considerando que palavras em contextos semelhantes possuem semântica semelhantes, as similaridades são medidas a partir das palavras ao redor. |
| Victor Arruda Ganciar | _Semântica e Similaridade de Palavras_ A distância de Hamming é a quantidade de bits usados na mudança de uma transmissão para a recepção e é utilizada para detectar erros nas transmissões binárias de comprimento fixo. A distância de Levenshtein é usada para medir a quantidade de diferenças entre duas strings. Usando operação como inserção, exclusão e substituição, esta distância métrica define o número mínimo de edições para transformar uma string em outra. Por exemplo, a distância entre as palavras pata e casa é de 2, pois são necessárias duas edições para uma palavra se transformar na outra, substituindo as letras c por p e t por s. Sejam a e b duas strings. Sejam i e j o comprimento de a e b, respectivamente. Se o comprimento de uma string for zero, então a distância será igual ao comprimento da outra string. _Significado de palavras_ Como visto nas aulas anteriores Stemming é a ação de reduzir em stems (ou parte de um palavra) e Stemmer é o programa que executa o algoritmo. Lemmatization é a ação de reduzir em Lemmas (ou forma básica da palavra, dicionário) e Lemmatizer é o programa que executa o algoritmo. Temos cinco definições importantes: 1. Homônimos: são palavras que compartilham a mesma forma mas possuem significados diferentes, como a palavra banco, que pode significar uma instituição financeira ou um assento. Ainda, homônimos podem ser homógrafos (possuem mesma forma de escrita) ou homófonos (possuem a mesma forma de fala). Homônimos criam problemas em recuperação de informação, tradução de textos e em aplicações text-to-speech. 2. Polissemia: é a propriedade que uma palavra tem em apresentar vários significados. Uma palavra polissêmica tem significados relacionados (origens similares), por exemplo as palavra letra e vela. Muitos tipos de polissemia são sistemáticos (metonímia), como as palavras rádio, escola e universidade. O teste de Zeugma é usado para determinar se uma palavra tem mais de um significado, para isso junta-se o complemento das duas palavras em uma mesma frase e verifica-se a coerência. 3. Sinônimos: são palavras que têm o mesmo significado em alguns ou todos os contextos, como as palavras carro e automóvel. Duas palavras são sinônimas se ambas podem ser substituídas em todas as situações. 4. Antônimos: são palavras que têm significado oposto em relação a uma característica, como as palavras escuro e claro. 5. Hiponímia e Hiperonímia: são palavras que indicam relação de hierarquia de significados, por exemplo carro é um hiponímia de automóvel e calçado é uma hiperonímia de sandália. |
| Lucas Zanoni de Oliveira | A aula do dia 01/07/2019 começou com um reforço sobre o conceito de String Matching utilizado para contextos de correção ortográfica e biologia computacional, por exemplo. O primeiro novo conceito apresentado foi o da Distância de Hamming que é utilizado para detectar erros de transmissões binárias de um comprimento fixo, onde uma quantidade de bits utilizado na mudança de uma transmissão para a devida recepção. Outro conceito foi o de Distância de Levenshtein que por sua vez é utilizado para a medição da quantidade de diferenças dentre duas palavras (strings), possuindo operações de inserção, exclusão e substituição. Um exemplo seria que a distância de Levenshtein para as palavras casa e pata é de 2, pois o mínimo de mudanças que teríamos que fazer para que elas sejam iguais, é de 2. Vale ressaltar que o algoritmo da última distância é altamente custoso visto que ele faz cálculos que anteriormente já tenham sido feitos. Posteriormente foi iniciado o capítulo 6 (Vector Semantics), onde foi resgatado o conceito de stem (parte de uma palavra) e lemma (forma básica de uma palavra), que por sua vez pode possuir diferentes significados (Ex: banco). Com isso, foi apresentado o termo wordform que diferentemente do lemma, trata-se de uma palavra com inflexão, por exemplo, dormiu e dormir. Ainda nessa linha, foram definidos como homônimos aquelas palavras que são iguais, porém possuem significados diferentes; polissemia a propriedade de uma palavra conter vários significados (Ex: vela), podendo ser sistemáticos (relação p?edio/organização) e sendo determinado a partir do teste Zeugma; sinônimos que se trata de palavras diferentes que possuem o mesmo significado (computador e PC); antônimos que não palavras com significados opostos (escuro e claro); hiponímia e hiperonímia que indicam a relação de hierarquia dentre os significados das palavras, onde uma palavra A que é hiponímia de B, quer dizer que o significado de A é mais específico que B, e hiperonímia é o inverso. Depois foi mostrado o Wordnet que é uma base de dados utilizada na área de linguística computacional, estando organizada de forma hierárquica e sendo usado para desambiguar o significado das palavras. Por outro lado, foi definido que duas palavras são similares quando possuem uma relação entre seus significados, sendo utilizado para aplicações como: recuperação de informação, detecção de plágio e agrupamento de textos. Já os algoritmos possuem duas abordagens que podem ser utilizadas para prover a identificação de similaridade de palavras, sendo aqueles baseados em tesauro e aqueles baseados em distribuição de palavras. |
| Felipe Dias Correia | A oitava aula é sobre o tema de Casamento aproximado entre strings Semântica como o primeiro tema, e foram utilizados exemplos de correções ortográficas para introduzir sobre o assunto. O primeiro assunto foi sobre a distância de Hamming, usam para detectar erros nas transmissões binárias de um comprimento fixo, e na teoria, é a quantidade de bits usado na mudança de uma transmissão para a recepção. O próximo assunto foi sobre a distância de Levenshtein, que usam para medir as diferenças entre duas strings, onde são presentes as operações de inserção, exclusão e substituição para definir a distância métrica do número minimo de edições para transformar uma string em outra string. O exemplo dado foi de "casa" e "pata", onde substitui o 'c' e o 's' por 'p' e 't' respectivamente. Outro tema abordado foram as cinco definições sobre 'significado' de palavras, com um breve resumo sobre Stemming e Lemmatization, Lemma e Wordform, e a explicação de Homônimos, que são palavras q compartilham a mesma forma, mas significados diferentes, como por exemplo, "Banco", que pode significar assento, instituição financeira ou artefato para armazenamento de dados. E também foi discutido sobre como homônimos podem ser problemáticos em PLN. O segundo assunto foi sobre Polissemia, onde uma palavra pode significar muitos significados, como "Letra", Vela, e também sobre Metonímia, onde é o caso de muitos tipos de polissemia, em que há exemplos onde o prédio esta relacionado a organização (Rádio, Universidade), e também de Autor para Trabalho do Autor (Eu amo J. K. Rowling). E apresentou técnicas para identificar o significado da palavra, usando o teste de Zeugma. Sobre o assunto de Sinônimos, onde as palavras tem o mesmo significado em alguns assuntos ou todos os contextos, como Caderno para caderneta, ou Computador para PC, e também sobre Antonimos, onde as palavras tem o significado oposto. Por último, foi sobre Hiponímia e Hiperonímia, onde indica a relação de hierarquia entre os significado das palavras, por exemplo Carro é uma hiponímia de Automóvel e Automóvel é hiperonímia de Carro. O próximo tema foi sobre Wordnet, apresentando o site em inglês que é usado para "desambiguar o significado" das palavras suas funções Synset por exemplo e sua versão em português. E no final, foi falado sobre similaridade entre palavra, onde duas palavras que são similares se ambas compartilham o mesmo signifcado, como exemplo, foi usado para instituição financeira, onde Banco é similar a Fundo e a importância de avaliar a similaridade destas palavras. |
| Lucas Ferraz Nicolau | O casamento aproximado de strings é a atividade de avaliar uma medida de distância entre palavras de modo a identificar o quanto são semelhantes. Esta ferramenta é de interesse em diversos contextos como correção ortográfica, onde devemos saber qual a palavra mais adequada para indicar como correção, e biologia computacional, onde podemos querer comparar alinhamento de sequências de sequências de bases nitrogenadas para identificar parentesco entre espécies. Uma primeira medida de distância entre palavras é a distância de Hamming que contabiliza a quantidade de elementos diferentes entre cadeias binárias de mesmo tamanho, ou seja, é a quantidade de bits utilizados na mudança de uma transmissão para a recepção. É uma medida simples de ser implementada, entretanto para a maioria das situações, não fornece informações suficientes. Uma medida mais sofisticada é de Levenshtein que compara strings considerando a quantidade mínima de operações que devem ser realizadas para transformar uma palavra em outra, utilizando para isso inserção, exclusão e substituição de caracteres de modo que cada operação tenha um peso estabelecido. Devido a natureza recursiva de um algoritmo para esta distância, ele terá execução em tempo exponencial caso não seja implementado com técnicas de programação dinâmica e, mesmos assim, pode vir a exigir muita memória para comparar palavras maiores. Além de considerar os conceitos de stem e lema, algumas outras definições importantes sobre significados de palavras que devemos ter em mente para comparação de palavras: homônimos são palavras que compartilham a mesma forma mas possuem significados diferentes, podendo ser homógrafos e homófonos; polissemia é a propriedade de uma palavra apresentar diferentes significados relacionados, muitas vezes por relações sistemáticas (metonímias), que podem ser identificadas pelo teste zeugma; sinônimos são palavras diferentes com o mesmo significado; antônimos são palavras com significado oposto; e hiponímia e hiperonímia são relações hierárquicas entre palavras, onde a primeira denomina um significado mais específico e, a segunda, um mais generalizado. Neste contexto, é interessante a existência de um tesauro, como Wordnet, que seja um repositório de palavras semelhantes as quais apresentam significados distintos. A similaridade entre palavras se trata da análise de quanto duas palavras compartilham o mesmo significado, interessante para aplicações como busca de informação, detecção de plágios e agrupamento de textos. Algoritmos para esta medida podem ser implementados utilizando tesauros, comparando diretamente com uma base, ou análise de distribuição de palavras, determinando o significado das palavras pelo contexto em que elas se apresentam como, por exemplo, o uso de uma matriz termo-documento. |
| Gustavo Murayama | Ao analisar a semântica e similaridade de palavras, é feito um casamento aproximado entre strings (string matching). O cálculo de similaridade pode ser feito através de alguns algoritmos, sendo um deles a Distância de Hamming, utilizado para detectar erros nas transmissões binárias de comprimento fixo. A distância é a quantidade de bits usados na mudança de uma transmissão para a recepção. A Distância de Levenshtein, por outro lado, define o número mínimo de edições para transformar uma string em outra. É usado para medir a quantidade de diferenças entre duas strings, usando operações como inserção, exclusão e substituição. Um exemplo, a distância da palavra casa e pata é 2, pois é substituído a letra c pela p (uma exclusão e uma inserção). Vale ressaltar que se o comprimento de uma string for 0, então a distância de Levenshtein é igual ao comprimento da outra string. Para o estudo do significado das palavras, cinco definições são importantes, além de alguns conceitos como stem, que é uma parte da palavra, lemma, que é a forma básica da palavra sem inflexão, e wordform, que é uma palavra com inflexão. Um lemma pode ter significados diferentes. Se as palavras compartilham a mesma forma, mas com significados diferentes, então é chamado de homônimos. A propriedade de uma palavra de apresentar vários significados se chama polissemia (uma palavra polissêmica tem significados relacionados) e muitos tipos são sistemáticos. Por exemplo, quando associamos o autor aos seus trabalho, dizemos Eu amo Stephen King ou Eu amo (as obras de) Stephen King. Para determinar se uma palavra tem mais de um significado, usamos o teste Zeugma: se a construção de uma frase não faz sentido (não for coerente), provavelmente a palavra seja polissêmica. Se duas palavras têm o mesmo significado em um ou mais contextos, é chamada de sinônima. Duas palavras são sinônimas se ambas podem ser substituídas em todas as situações e tem o mesmo significado proposicional. Antônimos se as palavras tem o significado oposto. Uma palavra A é hiponímia de B se o significado de A é mais específico que B, já o inverso é chamado de hiperonímia. Um tesauro (dicionário de ideias afins) é útil para PLN pois é usado para desambiguar o significado das palavras. Avaliar a similaridade de palavras é importante para recuperar informações (busca por elementos similares), detecção de plágio (busca por regiões similares) e agrupamento de textos (busca por conjuntos de textos similares). |
| Matheus Miranda Teles | Aula 7 - Casamento aproximado entre strings; Semântica e similaridade de palavras. Na correção ortográfica, consideramos que uma palavra está errada se esta difere de uma outra palavra, e para adivinhar a palavra que se encaixaria no contexto deve-se tomar uma medida para sabe qual o melhor encaixe para determinada situação. Uma medida é a distância de Levenshtein, que é usada para medir a quantidade de diferenças entre duas strings, usando de operações como inserção, exclusão e substituição. Esta distância define o número minimo de alterações para se transformar uma string em outra. Assim temos que a distancia de "casa" para "pata" é 2, pois trocando o "c" pelo "p" e o "s" pelo "t" saimos da primeira e chegamos na segunda. O algoritmo simples Chama recursivamente 3 casos para cada passo, fazendo com que ele não seja tão bem otimizado, porém um estrutura de cache já melhora o problema de (3^n) para (m*n) sendo n o tamanho da primeira palavra e m da segunda. Retomando a aula 4 temos que lemma é a forma básica da palavra, sem nenhuma inflexão, e wordform é uma palavra com inflexão, um determinado lemma pode ter significados diferentes, isso fazem das palavras homônimos pois compartilham a escrita mas não o significado. Em PLN homônimos são problemas pois interferem para recuperar informação, traduzir textos e aplicar text-to-speech. Outra tipo de um lemma é polissemia que são os que possuem muitos signifcados, como letra, que pode ser tanto o elemento básico de um alfabeto como o texto de uma canção. Então como sabemos se uma palavra possui mais de um significado? Usando o teste "Zeugma" que basta construir com uma mesma palavra, colocando seus dois complementos de frases distintas juntos, assim se não fizer sentido, provavelmente é polissêmica, existem também sinonimos que são quando duas palavras podem ser substituidas em todas as ocasiões, antônimos que são quando tem significados opostos e hipon~imia e hiperonímia, que indica relação de hierarquia das palavras. Existem tesauros com essas palavras, wordnet é uma base de palavras com hierarquias. Para a similaridade entre palavras temos que duas são similares se compartilham do mesmo significado e elas podem ser úteis para a recuperação de informações, detecção de plágio ou agrupamento de textos. Existe algoritmo para medir a similaridade entre palavras, então dado um tesauro, ele da as distâncias entre as palavras parecidas |
| Henrique Augusto Santos Batista | A distância de Hamming é utilizado para detectar erros nas transmissões binárias de comprimento fixo. A distância de Hamming é a quantidade de bits usado na mudança de uma transmissão para a recepção. A distância de Levenshtein é usada para medir a quantidade de diferenças entre duas strings. Usando-se de operações como inserção, exclusão e substituição, esta distância métrica define o número mínimo de edições para transformar uma string em outra por exemplo: a distância de Levenshtein entre casa e pata é 2 pois não há maneira de o fazer com menos de 2 edições a conversão de casa para pata é obtida substituindo-se c por p, logo substituindo-se s por t se o comprimento de uma string é 0 a distancia de Levenshtein é igual ao comprimento da outra string cinco definições sobre o significado de palavras Stemming -> a ação de reduzir em stems Stem é parte de uma palavra Stemmer é o artefato(programa) Lemmatization -> a ação de reduzir em Lemmas Lemma é a forma básica da palavra Lemmatizer é o artefato (programa) Lemma: é a forma básica da palavra (sem inflexão) Wordform: é uma palavra com inflexão. Exemplos: Bank Banks Sing Sung Dormir Dormiu Banco Bancos Um determinado lemma pode ter significados diferentes por exemplo: _Banco_ de investimentos _Bando_ de dados _Banco_ de madeira 1 ) Homônimos São palavras que compartilham a mesma forma mas com significados diferentes Banco: Instituição financeira. Banco: Artefato para armazenamento de dados. Banco: Assento. Homônimos podem ser homógrafos que são a mesma forma de escrita (banco/banco) e homófonos que são a mesma forma de fala (Concerto/conserto) 2 ) Polissemia É a propriedade de uma palavra tem de apresentar vários significados exemplo: Letra -> Elemento básico de um alfabeto, Letra -> Texto de uma canção, Letra-> Caligrafia de um determinado indivíduo. 3 ) Sinônimos Palavras que tem o mesmo significado em alguns ou todos os contextos. Caderno -> Caderneta Carro -> Automóvel Sofá -> Divá 4 ) Antônimos Palavras que tem significado oposto em relação a uma característica. escuro -> claro quente -> frio curto -> longo 5 ) Hiponímia e Hiperonímia Indicam relação hierárquica de significados entre palavras. Uma palavra A é hiponímia de B, se o significado de A é mais específico que B: Carro é uma hiponímia de Automóvel Sandália é uma hiponímia de Calçado De modo inverso: Automóvel é uma hiperonímia de Carro Calçado é uma hiperonímia de Sandália |
| Willian Teruya Kimura | No dia 01/07, foi apresentado o conteúdo referente a casamento aproximado entre strings e semântica e similaridade de palavras. Para iniciar a aula, foi questionado em um contexto de correção ortográfica qual seria uma palavra mais próxima dado uma string específica, e dado um exemplo de combinação de genes de DNA, verificando a similaridade dela, isso se chama string matching. Para verificar a combinação de strings, pode ser utilizado dois cálculos de distância: de Hamming (visto em aulas anteriores) e o de Leveschin. A distância de Leveschin é usado para averiguar as diferenças entre duas strings a partir de operações como inserção, exclusão e substituição, definindo o número mínimo de edições. Para se calcular, é utilizado o seguinte algoritmo: 1) Sejam a e b duas strings. 2) Sejam i e j o comprimento de a e b, respectivamente. 3) Se o comprimento de uma string for zero, então a distância será igual ao comprimento da outra string. Em seguida, foi verificado cinco definições importante acerca do significado das palavras, sendo elas: 1. Homônios, palavras que compartilham da mesma forma, porém podem assumir diferentes significados, podendo eles serem homógrafos (mesma grafia) ou homófonos (mesma forma de fala); 2. Polissemia, propriedade que uma palavra tem de apresentar vários significados, sendo muito deles sistemáticos (por exemplo: prédio <-> organização); 3. Sinônimos, palavras diferentes que possuem o mesmo significado dado alguns ou todos os contextos; 4. Antônimos, palavras que possuem o significado oposto em relação a uma característica, 5. Hipomínia e Hiperomínia, onde ama palavra A é hiponímia de B, se o significado de A é mais específico que B, e hipomínia caso contrário. Para ver de maneira mais adequada os distintos significados das palavras, foi mostrado o Wordnet, que é utilizado para reduzir a ambiguidade das palavras. Para existir similaridade entre palavras, deve se existir um compartilhamento do mesmo significado. É importante avaliar a similaridade devido a sua utilização para aplicações como: Recuperação de Informação, Detecção de Plágio ou Agrupamento de textos, tendo muitos outros exemplos. Para verificar tal similaridade, é possível utilizar dois algoritmos, sendo um deles baseados em tesauros, em que duas palavras são similares se uma é hipomínia de outra ou se compartilham da mesma definição, e o outro baseado em distribuição de palavras, em que se é necessário um corpus grande no qual sejam evidenciados diferentes pares de palavras. |
| Rafael Ribeiro Gomes da Silva | Na primeira parte da aula, entendemos o contexto do porquê é necessária a abordagem para análise de similaridade das palavras baseados em distribuições de palavras. Um dos maiores problemas em outros tipos de abordagem é a constante evolução do cenário mundial que pode acarretar em diferenças linguísticas no decorrer dos anos. Outro problema, é que os tesauros não são constantemente atualizados, o que pode gerar um déficit na informação. Na literatura, são abordadas duas frentes principais: distributional semantics e vector semantics. Para a distribuição de palavras, foram apresentadas quatro frases com uma palavra desconhecida e não localizada em um tesauro (tesauros funcionam como um dicionário listando as palavras e conclusões semelhantes em determinado contexto). Sendo possível inferir algo sobre a palavra, mesmo a desconhecendo completamente, apenas pelo contexto. Para o vetor de números, a ideia é computar a quantidade de palavras para encontrar similaridades entre obras através de termos escolhidos. Na segunda parte da aula, foram apresentadas as formas como podem ser calculadas a proximidade entre as palavras e a primeira abordagem foi a Distância de Hamming. Nessa abordagem, são calculadas as quantidades de operações necessárias para que a palavra seja transformada em outra palavra com algum significado. O maior problema é que sua assintoticidade é exponencial, pois são repetidas tuplas já definidas. Novamente foram discutidos os conceitos sobre stemming e lemmatization, deixando mais evidente a diferença entre uma parte da palavra e a forma básica sem inflexão. Uma grande dificuldade para a análise pura são das palavras homônimas, tanto foneticamente(homófonos), quanto léxicamente(homógrafos). São problemáticos devido a possível existência de diversos significados para as palavras, erros de tradução e problemas de pronúncia. A metonímia também engloba esses problemas, por conter relações sistemáticas. A forma de detecção de múltiplos significados, é através de zeugmas que analisam o sentido da frase. Outras formas para essa detecção seriam a análise de sinônimos e de antônimos. Houve a introdução sobre os conceitos de hiponímia e hiperonímia. Sendo eles, a relação entre as palavras dizendo se uma é mais específica que a outra. Por fim, entendemos a importância de se analisar a similaridade entre as palavras para análise do contexto, detecção de plágio, agrupamentos de textos entre outros. E que as duas abordagens para identificar a similaridade são: o algoritmo baseado em tesauros e na distribuição de palavras em um corpus grande. |
| Marcelo Schirbel Gomes | Aula 08 Casamento aproximado entre strings. Devemos ter uma medida de similaridade entre as palavras. Semântica e Similaridade Há muitos algoritmos em computação que se alinharam aos conhecimentos de biologia para verificarem se alinhamentos de DNA estão similares o suficientes para serem correlatos em parentesco histórico. Distância de Hamming É a quantidade de bits usado na mudança de uma transmissão para a recepção. Mas ele obriga que as distâncias entre as strings comparadas sejam iguais. E caso sejam de tamanhos distintos, o resultado é -1. Distância de Levenshtein Só podemos fazer adição, subtração e substituição. E transformamos uma string em outra. Mas é um algoritmo muito caro, pois tem uma função de custo exponencial. Stemming vs Lemma São formas de truncar e partir as palavras. No Stem cortamos puramente, no Lemma nós procuramos a forma básica de uma palavra com um dicionário. Um determinado Lemma pode ter significados diferentes. Por exemplo a palavra 'ponto'. Homonimos São palavras que, apesar de terem siginificados diferentes, são escritas da mesma forma. Homógrafo é algo que é escrito da mesma forma Homófono é a mesma fala. Mas são todos homônimos. Polissemia Muitos significados para uma mesma palavra. Como vela, banco, letra e etc. E por isso temos os sistemáticos, podendo obter o significado tanto de locais, ou de pessoas ou de elementos. E para determinar os múltiplos significados podemos usar o teste de Zeugma, ou seja, se a construção não faz sentido, provavelmente ela é polissêmica. Outro problema são os sinônimos e antônimos. Pois podemos trocar os sentidos e afetar o texto. Hiponímia, é quando A é mais específico do que B Hiperonímia é quando B é mais específico do que A. Isso pode auxiliar ao trocar as palavras. Tesauro É um dicionário de ideias comuns. É usado para desambiguar o significado de palavras. A similaridade de palavras pode ser util para buscar elementos similares, como informações, plãgio e agrupamento de objetos. Mas isso pode ser um problema quando as palavras são diferentes, mas permanecem sob um mesmo contexto. E pra isso usamos um tesauro, para fazer uma similariedade entre as palavras e traçar uma rota entre elas. E a rota de similariedade é dada por 1/(dist(a,b)) E a grande maioria dos algoritmos atuais se baseiam na abordagem de distribuição de palavras. Isso acontece para não ficarmos dependentes de tesauros. |
| Felipe de Campos Mesquita | Na aula 8 de processamento de linguagem natural começamos fazendo o teste/exercícios. A bibliografia da aula continua sendo o livro Speech and language processing: Na introduction to natural language processing, computational linguistics, and speech recognition de Daniel Jurafsky e James H Martin, capítulo 6. Dentre as três questões a primeira pedia para achar a palavra mais similar de uma palavra dada e justificar. Com este exercício podemos entender um pouco melhor como pode ser difícil julgar a similaridade de uma palavra. Há dúvidas a respeito de escolher uma no mesmo idioma, talvez a mais próxima lexicograficamente, ou escolher o gênero oposto. A segunda pergunta pedia as definições de homógrafo e homófono, que significam respectivamente, palavras que têm mesma grafia e sentidos diferentes, e que tem o mesmo som, mas grafia diferentes. A aula foi sobre casamento aproximado entre strings e semântica e similaridade de palavras (parte 1). O casamento aproximado entre strings (string matching em inglês) pode ser usado no contexto, por exemplo, de correção ortográfica, na biologia computacional para alinhamento de aminoácidos. A distância de Hamming visto em aula é utilizada para detectar erros nas transmissões binárias de comprimento fixo, a distância de Hamming é a quantidade de bits usado na mudança de uma transmissão para a recepção. Também vimos em aula a distância de Levenshtein que é usada para medir a quantidade de diferenças entre duas strings, usando de operações como inserção, exclusão e substituição, esta distância define o número mínimo de edições para transformar uma string em outra, o exemplo dado em aula foi o de casa e pata que é dois, pois não há maneira de fazer com menos de duas edições. Algumas definições importantes foram dadas durante a aula, entre elas, Stem, parte de uma palavra, Lemma, forma básica da palavra (sem inflexão), wordform, palavra com inflexão, homônimos são palavras que compartilham a mesma forma, mas com significados diferentes, por exemplo, banco assento e banco instituição financeira. Já a polissemia é a propriedade de uma palavra de apresentar vários significados. A respeito de similaridade entre palavras vimos na aula duas possíveis abordagens, a primeira é algoritmos baseados em tesauro (duas palavras são similares se uma é hiponímia de outra, carro é uma hiponímea de automóvel), e segunda abordagem é algoritmos baseados em distribuição de palavras. |
| Matheus de Araujo Vargas | Na aula de Processamento de Linguagem Natural do dia 1 de Julho do professor Jesus P. Mena foi explorado o conceito de String Matching, que é o "casamento" entre strings. Para verificar qual string é mais similar a uma outra string, algumas medidas de distância podem ser utilizadas. Foram apresentadas na aula as distâncias de Hamming e a distância de Levenshtein. A distância de Hamming é originalmente utilizada para detectar erros nas transmissões binárias de comprimento fixo. Para textos, a distância entre duas strings é medida pela quantidade de caracteres diferentes entre as duas strings que estão na mesma posição. Já a distância de Levenshtein, pode ser calculada entre string de tamanhos diferentes. Usando-se de operaçoes como inserção, exclusão e substituição, esta distância métrica define o número mínimo de edições para transformar uma string em outra. Por exemplo, a distância de Levenshtein entre casa e pata é 2, pois não há maneira de o fazer com menos de 2 edições. A conversão de casa para pata é obtida substituindo-se c por p, logo substituindo-se s por t. Foram apresentados também os conceitos de lemma, que é a forma básica da palavra (sem inflexão) e wordform, que é uma palavra com inflexão. Homônimos são palavras que compartilham a mesma forma, mas com significados diferentes (origens diferentes). Polissemia é a propriedade de uma palavra tem de apresentar vários significados. Sinônimos são palavras que tem o mesmo significado em alguns ou todos os contextos. Antônimos são palavras que tem significado oposto em relação a uma característica. Hiponímia e Hiperonímia indicam relação hierarquica de significados entre palavras. Uma palavra A é hiponímia de B, se o significado de A é mais específico que B. Caso contrário, A é hiperonímia de B. A similaridade de palavras pode ser útil em diferentes tipos de aplicações, como por exemplo: Recuperação de Informação (IR), busca por elementos similares, detecção de plágio, busca por regiões similares, agrupamento de textos e busca por conjuntos de textos similares. Duas abordagens para identificar similaridade entre palavras: 1) Algoritmos baseados em tesauro, em que duas palavras são similares se uma é hiponímia de outra. 2) Algoritmos baseados em distribuição de palavras, que não precisam de um tesauro, mas de um corpus grande no qual sejam evidenciados diferentes pares de palavras. |
| Guilherme Oliveira da Silva | Resumo Aula 8 Essa aula iniciou-se com o tópico de casamento de strings, uma forma de correção automática onde por meio da parte da palavra seja possível encontrar a palavra certa ou desejada, para isso precisa-se entender um pouco das distâncias. Duas delas que foram citadas a distância de hamming e a distância de levenshtein, o primeiro se utiliza da quantidade de bits para determinar a mudança na quantidade desses no momento da transmissão o segundo é usado para medir a diferença entre duas strings. Abordando esses conceitos juntamente com conceitos previamente estudados, stemming e lemmatization. Nos focando no lemma um novo conceito foi introduzido, wordfrom, que são as palavras flexionadas a partir de um lemma, dessa forma temos um conjunto de significados para cada lema. O primeiro citado é o homônimo, palavras que compartilham de uma mesma forma mas com significados diferentes, mas deve-se ter cuidado, esse tipo pode causar problemas ao PLN. O segundo é a polissemia uma propriedade que a palavra tem de assumir vários sons significados, dentro da polissemia temos a metonímia que envolvem as relações sistemáticas das palavras. O terceiro é são os sinônimos palavras que tem o mesmo significado em algum ou todos os conceitos. O quarto são os antônimos palavras que significam o oposto em relação a uma característica. E o quinto hiponímia e hiperonímia que indicam as relações hierárquicas. Depois de abordar esses conceitos entramos em wordnet, um repositório muito util em pln, uma base de dados criada em 1985 organizada de forma hierárquica, foi-se falado também um pouco das wordnet em português também, algumas iniciativas. Ao fim dessa breve explicação sobre wordnet entramos no conceito de similaridade de palavras conceito a partir de que se duas palavras tem o mesmo significado elas são similares, focou-se também na importância de avaliar essa similaridade e introduziu alguns algoritmos que fazem essa avaliação. Daqui para frente tratou-se de introduzir alguns tipos de algoritmos de avaliação similaridade alguns exemplos e problemas que podem surgir durante a programação, também mostrou-se como contorna-los. Falou-se da importância dos algoritmos de similaridade baseado na distribuição de palavras e o porque isso é importante. Falou-se um pouco de matriz, termo de documento, agrupamento hierárquico e a captura de significado relacional. |
| Matheus Dos Santos Pereira | Resumo da aula 08, sobre casamento aproximado entre String, semântica e similaridade de palavras parte 1. Podemos usar casamento aproximado entre Strings, para correção automática, no contexto de biologia computacional. A distância de Hamming pode ser utilizado para detectar erros nas transmissões binárias de comprimento fixo. A distância de Levenshtein é usada para medir a quantidade de diferenças entre duas Strings, utilizando de operações como inserção, exclusão e substituição, esta distância métrica define o número mínimo de edições para transformar uma String em outra, como por exemplo, a distância entre casa e pata é 2. Foi aplicado uma atividade sobre estes conceitos antes de apresentados para a sala, e foi apresentado os códigos em python, referente ao calculo das duas distancias. Definições importantes: Stem: Parte de uma palavra, Lemma: Forma básica da palavra, Wordform: é uma palavra com inflexão. Um Lemma pode ter significados diferentes, como por exemplo a palavra banco, que pode ser uma Instituição financeira, um Artefato para armazenamento de dados ou um Assento. Homógrafos: mesma forma de escrita (banco/banco) e Homófonos: mesma forma de fala (Concerto/conserto) Homônimos criam problemas em PLN, em recuperação de informação, em tradução de textos e em aplicações text-to-speech (a pronuncia é diferente). Polissemia é a propriedade de uma palavra tem de apresentar vários significados e muitos tipos de polissemia são sistemáticos (metonímia). Sinônimos Palavras que tem o mesmo significado em alguns ou todos os contextos, Antônimos Palavras que tem significado oposto em relação a uma característica. 5) Hiponímia e Hiperonímia: Indicam relação hierárquica de significados entre palavras, sendo o primeiro sub e o segundo super. Wordnet é um repositório (tesauro) muito útil em PLN, ele é uma base de dados (1985) usada na área de linguística computacional, em inglês, e está organizado em base de relações (hierárquicas), muito utilizado para desambiguar o significado das palavras. Duas palavras são similares se ambas compartilham o mesmo significado. As palavras similares mantem uma relação de significado. A similaridade de palavras pode ser útil em diferentes tipos de aplicações, como por exemplo: Recuperação de Informação (Busca por elementos similares), Detecção de plágio (Busca por regiões similares), Agrupamento de textos (Busca por conjuntos de textos similares), entre outros. |
| Thiago Felipe Floreste | O casamento de strings (strings matching) têm o objetivo de analisar a similaridade de duas cadeias de caractere s. Este é um conceito útil em diversos contextos. Pode ser usado, por exemplo, por corretores ortográficos , para sugerir a palavra mais provável a substituir uma outra palavra errada; no alinhamento de sequências de peptídeos e aminoácidos, útil para diversas aplicações biológicas, dentre outras várias situações.Uma forma de medir a similaridade de duas strings é através da Distância de Distância de Levenshtein, que é o número mínimo de edições (inserção, exclusão e substituição) necessárias para transformar uma cadeia de caracteres em outra.Por exemplo, a Distância de Levenshtein entre as palavras "casa" e "pata" é 2, pois este é número mínimo de transformações necessárias para transformar uma palavra na outra. A Distância de Levenshtein pode ser definida formalmente de maneira recursiva da seguinte maneira: Sejam s1 e s2, duas strings, sendo l1 o comprimento de s1 e l2 o comprimento de s2, O caso base da recursão ocorre quando min(l1, l2) = 0, nesse caso LEVs1,s2(l1, l2) = max(l1, l2), caso contrário, LEVs1,s2(l1, l2) = min { LEVs1,s2(l1, l2 - 1), LEVs1,s2(l1 - 1, l2), LEVs1,s2(l1 - 1, l2 - 1) }. A solução recursiva pode ser implementada de maneira quase direta computacionalmente, entretanto não é muito eficiente, pois tende a repetir os mesmos cálculos diversas vezes. Uma implementação com uso de programação linear tende a ser muito mais eficiente, neste caso. Outro tipo possível de análise é a da similaridade de palavras. Duas palavras são consideradas similares se compartilham o mesmo significado. Por exemplo, a palavra "caderno" é similar a palavra "caderneta". A análise de similaridade das palavras é utilizada, por exemplo,para recuperação de informações, análise de plágio e agrupamento de textos. É possível estimar a similaridade entre duas palavras com base no quão próximo são seus significados. Para isso existem duas abordagens principais: Algoritmos baseados em tesauro e Algoritmos baseados em distribuição de palavras. |
| Anderson Chaves Faria | Há diversas formas de se classificar a semelhança entre duas palavras. Na aula 8 fomos apresentados algumas dessas formas, seja por numero de variações da palavra, som, graficamente e até na interpretação delas. No método calculando a distância de hamming, nós contamos do início ao fim da string contando as diferenças, porém esse método só funciona se ambas tiverem comprimento igual, do contrário o retorno será -1, o que não nos ajuda muito. Já utilizando o método da distância de Levenshtein, nós médimos a quantidade de diferenças com base nas operações inserção, remoção e substituição, que acaba sendo um "atalho" com peso maior para uma remoção e inserção. A distância de Levenshtein nos retorna o mínimo número de edições para transformar uma palavra em outra. Infelizmente por ser calculada através de um algoritmo de backtracking muito custoso, em sua versão pura sem "memoization" o resultado pode levar muito tempo para ser processado dependendo do tamanho de cada uma das palavras. Depois tivemos uma recapitulação de alguns conceitos como stemming, lemmatization e suas diferenças, porém agora trazendo novas informações sobre significados, sobretudo na interpretação do lemma gerado. As principais diferenças de sentido podem ser atribuídas aos seguintes artefatos linguísticos: 1) Homônimos: Palavras com mesma forma, podendo ser divididos ainda entre homógrafos (mesma escrita) e homófonos (mesmo som) 2) Polissemia: muitos significados pruma mesma palavra (alguns sendo sistemáticos como a figura de linguagem metonímia). Contudo com uma base relativamente grande é possível fazer testes de Zeugma para descobrir se uma palavra é polissêmica. 3) Sinônimos: Palavras de mesmo significado 4) Antônimos: Palavras de significado contrário 5) Hierarquias de palavras (classes e instâncias) como hiponímias e hiperonímias. Por fim concluímos que similaridade de palavras está fortemente relacionado com a interpretação de cada uma e revisamos alguns algoritmos como matriz documento e alguns baseados em tesauros e agrupamentos hierárquicos para categorizar significados e ter aplicações bem interessantes como detecção de plágio, busca de elementos similares e agrupamentos de textos. |
| Lucas Monteiro de Oliveira | Resumo da aula 8 de Processamento de Linguagem Natural Título da aula: Casamento aproximado entre strings. Semântica e similaridade de palavras. A aula começou com uma discussão sobre similaridade e proximidade de strings em um contexto de correção ortográfica. Em seguida fomos apresentados à distância Hamming, que pode ser utilizada para detectar erros nas transmissões binárias. A distância de Hamming é definida pela quantidade de bits utilizadas na mudança de uma transmissão para uma recepção. Em seguidas vimos a distância de Levenshtein, que é utilizada na comparação de duas strings através da quantidade de passos necessários para se chegar de uma na outra. Os passos são definidos pelas operações de inserção, exclusão e substituição. O problema desta distância é que para que ela seja calculada, é necessário que uma tabela completa seja gerada, o que pode ser muito custoso. Na segunda parte da aula relembramos conceitos já vistos anteriormente como Stemming e Lemmatization, onde o primeiro consiste em simplesmente reduzir a palavra para um formato mais genérico, enquanto o segundo se propõe a reduzir a palavra de tal forma a se chegar no radical dela. Dada a definição de lemma foi abordado que estes podem ter mais de um significado, ou seja, homônimos, palavras que compartilham a mesma forma, mas possuem significados diferentes. Um outro conceito é o de palavras polissêmicas, que apesar de também possuírem significados diferentes para a mesma forma, possuem significados que são de certa forma relacionados. Uma forma de identificar as palavras polissêmicas é através do teste de Zeugma, uma figura de linguagem. Um outro cenário comum é o de sinônimos, ou seja, palavras que possuem um mesmo significado em alguns ou todos os contextos apesar de apresentarem formas diferentes. Antônimos são palavras com significados opostos, já hiponímia e hiperonímias são palavras que indicam algum tipo de relação hierárquica. Wordnet é um repositório tesauro que pode ser muito útil em diversas aplicações de PLN. |
| Iasmin de Haro Pracchias | Na aula do dia 01/07 vimos o conceito de similaridade entre palavras. O professor iniciou a aula com um exercício para que identificássemos o grau de similaridade entre algumas palavras. Após a finalização do exercícios vimos alguns métodos utilizados para identificar quão similares algumas palavras são de outras, como por exemplo o método da "distância de Hamming" que basicamente é utilizado para medir a quantidade de bits de diferença entre uma palavra e outra, também vimos o conceito de "distância de Levenshtein" que usa as operações de inserção, substituição, e exclusão para definir o numero de edições necessárias para transformar uma palavra em outra, ou seja, mede as diferenças entre as palavras em questão. O uso do método da "distância de Levenshtein" não é muito adequado, pois trata-se de um algoritmo que tem muitos processos relacionados o que toma um grande tempo de execução. Entrando no tópico de significados de palavras, o professor fez um pequeno overview sobre os métodos de Stemming e Lematization, que são respectivamente as ações de reduzir a palavras em stems (parte da palavra) e em lemmas (forma basica da palavra). Uma mesma palavra pode ter significados diferentes, vimos alguns exemplos deste tipo de caso. Palavras homônimas são palavras que possuem a mesma forma, mas significados diferentes, elas podem ser homógrafas (que são escritas da mesma forma) e homófonas (que são pronunciadas da mesma forma), homônimos podem causar problemas em PLN de variadas maneiras, como por exemplo em aplicações de tradução, uma vez que podemos ter palavras escritas da mesma forma mas que tem significados diferentes. Também vimos outro conceitos que pode causar problemas em PLN, como a Polissemia, que é a propriedade de uma palavra de ter vários significados, os conceitos sinônimos e antônimos com os quais já estamos mais familiarizados, e por fim os conceitos de hiponímia e hiperonímia, que indicam relações de hierarquia entre as palavras. |
| Paulo Alexander Simoes | Aula 8 : Casamento aproximado entre String Semântica e similaridade de palavra Quando falamos de semântica e similaridade de palavra nos remetemos a medir o grau de equivalência semântica entre dois textos, buscando descobrir quais textos são mais similares que outros. Um dos métodos utilizados para detecção, mesmo que este ainda utilize conceitos de erros é a distância de Hamming. Essa distância é dada pela quantidade de bits usado na mudança de uma transmissão para a recepção . Outro método é a distância de Levenshtein, este é utilizado para medir a quantidade de diferenças entre duas strings. Utilizando de operações como inserção, exclusão e substituição. esta distância métrica define o número mínimo de edições para transformar uma string em outra. Exemplo: a distância de Levenshtein entra "avião" e "gavião" é 1, onde é necessário apenas uma inserção de letra, o "g" no início da palavra. Revisando algumas definições de palavras, temos: Stemming x Lemmatization, o stemming é dado pela ação de reduzir em stems, stem é a parte uma palavra. Stemmer é quem realiza, o artefato(programa). Lemmatization (a ação de reduzir em Lemmas), Lemma é a forma básica da palavra, sem inflexão. Lemmatizer é o (artefato) programa. Wordform é a palavra com inflexões. Homônimos, são palavras que compartilham a mesma forma mas com significados diferentes, exemplo: leve(verbo:levar) e leve(adjetivo: referente ao peso). Polissemia: Propriedade que alguma palavra tem de apresentar vários significados. Relações sistemáticas (metonímia) muitos tipos de polissemia são sistemáticos. Sinônimos: Palavras diferentes que possuem o mesmo significado. Antônimos: Palavras que possuem significado oposto. Hiponímia e Hiperonímia: Hiponímia é quando uma palavra A tem um significado mais específico do que B, exemplo: Cerveja é hiponímia de bebida alcoólica. Similaridade entre palavras, ocorre quando ambas compartilham o mesmo significado. Como por exemplo: banco é similar a fundo Entender a similaridade é importante para recuperação de informação, detecção de plágio e agrupamento de textos. |
| Murilo Bolzan Dionisio | -Casamento aproximado entre strings: Devemos possuir uma medida de semelhança entre as palavras. Exemplo: No contexto de correção ortográfica, a palavra mais próxima de graffe é giraffe. A biologia informática é uma área com grande interesse nesse tema de PLN. -Distância de Hamming: Utilizado para detectar os erros nas transferências binárias de comprimento previamente fixados. A quantidade de bits necessários para a mudança de uma dessas transferências para uma recepção é chamada de distância de Hamming. Exemplo: Hamming ("PLN", "PNL") igual a 2; Hamming ("UFABC", "UFBA") igual a -1 (o algoritmo considera apenas palavras de tamanho iguais, se não a qualifica como inválida). Hamming ("UFABC", "UFABC") igual a 0. -Distância de Levenshtein: É usada para fazer a medição da quantidade de diferenças entre duas cadeias. Faz uso de operações como Inserção, Exclusão e Substituição, o número mínimo de edições para a tornar na mesma palavra é definida pela distância métrica. Exemplo: Levenshtein ("para", "casa") igual a 2; Levenshtein ("hora", "hoje") igual a 2. Este algoritmo é um exemplo clássico da aplicação da técnica de memorização (análise de algoritmos). Com ele é possível transformar uma versão recursiva em uma versão matriarcal de forma geralmente barata. -Stemming vs Lemma: Lema: um tipo de versão sem flexibilização. Stem: apenas um corte direto na palavra original. -Homógrafo vs Homófono: Homófono: duas palavras com a escrita diferente mas com a reprodução sonora igual. Homógrafo: quando duas palavras compartilham a mesma forma mas com significados diferentes (as origens normalmente são diferentes). -Polissemia: Propriedade de palavras que possuem diversos significados. -Sinônimos: Nome dado quando duas palavras diferentes possuem o mesmo significado. -Antônimos: Nome dado quando duas palavras diferentes possuem o significado oposto, como exemplo: cima e baixo, esquerda e direita, dentro e fora. -Wordnet: É uma base de dados usada em linguística computacional, onde é buscada quando se deseja desambiguar o significado de algo. |
| Jean Augusto de Araujo | Resumo da aula de Processamento de Linguagem Natural do dia 01/07: Casamento aproximado entre strings - Semântica e similaridade de palavras. A aula iniciou com uma introdução sobre o tema, e um exemplo de string matching no uso de correção ortográfica. Por exemplo, supondo que a palavra graffe foi escrita, ela deveria ser mais próxima de Graf, Graft, Grail ou Giraffe. Em paralelo, é mostrado uma sequência de aminoácidos (ACGT) e um possível alinhamento. Em ambos os casos, pode ser utilizada a distância de Hamming, já vista anteriormente, na para detectar erros nas transmissões binários, quando seu comprimento é fixo. Essa distância é a quantidade de bits de diferença na mudança de uma transmissão para recepção. Em sequência, a aula abordará principalmente a distância de Levenshtein. A distância de Levenshtein mede o número de diferenças entre dois textos, ou duas strings. O cálculo da distância é baseado em operações de inserção, exclusão e substituição para que a primeira string se aproxime da outra. Essas operações podem ter pesos diferentes. A distância de Levenshtein, dado o exemplo casa e pata é sempre 2. Substitui-se c por p e s por t, não sendo necessárias operações de inclusão ou exclusão. Pode ser representado em uma árvore. Foram apresentados algumas páginas da web com conteúdos úteis em relação ao tema, como simulador. Em sequência, foram apresentadas definições importantes. Stemming e Lemmatization. O Stemming é a ação de reduzir em stems, artefato, ou programa., realizado pelo Stemmer Já Lemmatization é a ação de reduzir em Lemmas, a palavra propriamente dia, em sua forma básica, realizado pelo Lemmatizer Também, apresentado a diferença entre Lemma, que é a forma mais básica da palavra e Wordform, que é a palavra com inflexão. Assim, um lemma pode assumir significados diferentes, como no caso de homônimos, sejam homógrafos ou homófonos. |
| Gabriel Peterlini Pinto | Nesta aula do dia 01/07 começamos a aula realizando um exercício para determinar a distância entre duas strings similares e qual é a melhor forma de determinar uma heurística para essa distância. Um dos métodos vistos foi a distância de Hamming, que é utilizada para detectar erros em transmissões binárias de comprimento fixo. A distancia de Hamming é a quantidade de bits usado na mudança de uma transmissão para a recepção, por exemplo, a distância de Hamming entre as palavras "PNL" e "PLN" é 2, ou seja, é a quantidade de caracteres diferentes entre ambas as strings. Outro método é a distância de Levenshtein, que é usada para medir a quantidade de diferenças entre duas strings através de operaçoes como inserção, exclusão e substituição, esta distância métrica define o número mínimo de edições para transformar uma string em outra. Por exemplo, a distância de Levenshtein entre casa e pata é 2, pois não há maneira de o fazer com menos de 2 edições. A conversão de casa para pata é obtida substituindo-se c por p, e depois substituindo-se s por t. Outro conceito visto durante o exercício no começo da aula foram de palavras homônimas que podem ser subdividas em palavras homógrafas e homófonas. Palavras homônimas são palavras que compartilham a mesma forma mas que possuem significados, por exemplo: "Banco": Instituição financeira, "Banco": Artefato para armazenamento de dados e "Banco": Assento. a subclassificação de homônimos em homográfos se dá as palavras que possuem a mesma forma de escrita, já os homônimos homófanos são as palavras que possuem a mesma forma de pronúncia. Homônimos podem causar problemas em PLN quando, por exemplo, tentamos traduzir palavras iguais com significados diferentes ou em aplicações de text-to-speech onde a pronúncia de palavras iguais são diferentes. |
| Jairo da Silva Freitas Junior | Esta aula iniciou com uma atividade sobre similaridade de strings que serviu como introdução para o primeiro assunto do encontro: casamento aproximado entre strings. O conceito por trás do String matching é mapear uma combinação de cadeias para alguma métrica de distância que modele bem a intuição do problema. A primeira estudada foi a distância de Hamming, que é a medida da quantidade de posições nas quais os caracteres de duas cadeias difere. Oura distância possível é a distância de Levenshtein, que mede a quantidade de diferença entre cadeias é medida pela quantidade de operações de inserções, exclusões e substituições. Esta abordagem, porém, é muito custosa computacionalmente devido a sobreposição de cadeias que podem ser geradas. Uma alternativa interessante e eficiente para string matching que mantém a ideia da distância de Levenshtein é baseada no artigo de Esko Ukkonen. Na segunda parte da aula introduziu-se os conceitos de homônimos (palavras com a mesma grafia e significados diferentes) e polissemia, esta última sobre a qual podemos analisar de forma ad hoc usando o teste Zeugma, iste é mesclando duas cadeias e avaliando se fazem sentido nest econtexto. Também vimos sinônimos, antônimos e hiponímia (quando uma palavra tem significado mais específico do que outra) e hiperonímia (o contrário). Um tesauro é um dicionário de ideias comuns e pode ser útil para desambiguar palavras, porém está em desuso devido a desatualização dos repositórios (ex: Wordnet e Synset) e ao aumento da capacidade de processamento de dados, que permite gerar desambiguações a partir da análise de grandes corpus (pela distribuição de palavras, usando, por exemplo, a técnica de matriz termo-documento). Uma aplicação de similaridade de strings é a detecção de plágio. Outra apresentada é a variação semântica das palavras no tempo. |
| Rafael Correia de Lima | Essa oitava aula de PLN foi dividida em duas partes: 1) Casamento Aproximado entre Strings e 2) introdução à Semântica e Similaridade de Palavras. Na primeira parte foram apresentadas técnicas para a medição de similaridade gráfica entre cadeias de caracteres. A primeira dessas técnicas apresentada foi a Distância de Hamming, que compara duas strings por seus caracteres de mesmo índice. No entanto, essa técnica funciona apenas para comparar cadeia que possuam a mesma quantidade de caracteres. A segunda técnica apresentada foi a Distância de Levenshtein. Ela é capaz de identificar a quantidade diferenças entre duas strings. A partir de uma das strings comparadas, contabiliza-se a quantidade de operações de inserção, exclusão ou substituição para obter-se a outra, cada qual com seu custo, e define-se como a distância entre as strings o menor número de operações possível. A forma ingênua do algoritmo de Levenshtein tem custo exponencial, mas existem versões adaptadas que fazem o uso de programação dinâmica para reduzir o tempo de execução. Na segunda parte da aula foram introduzidos alguns conceitos e definições importantes acerca da semântica de palavras. Foram revisadas as diferenças entre Stemming e Lemmatization, incluindo-se o conceito de wordform, sendo esse uma inflexão de um lemma. Foi ressaltada a possibilidade de que um lemma tenham mais de um significado, seja por motivo de homonímia, como por exemplo a palavra banco, (assento ou instituição financeira) ou por polissemia. Definiu-se também os sinônimos, antônimos e as relações de hiponímia e hiperonímia. A wordnet é um repositório que traz relações de hierarquia entre as palavras ali presentes, e pode ser usado por exemplo na busca de palavras com significado similar ou para a desambiguação de palavras. |
| Diego Pereira de Lima | Na aula de 01/07 do professor Jesús mena chalco, foi compartilhado técnicas de comparação de palavras como distância de levenshtein. Esta distância baseia-se na comparação de duas palavras e encontrar a variação de caracteres entre elas, dentre as regras: inserção, eliminação e substituição(contando por 2). Na segunda parte da aula foi abordado o contexto semântico e a comparação entre palavras. Entre as classificações dadas estão os homógrafo(possui a mesma escrita) e homofono, (possui o mesmo som). Também foi abordado o conceito de sinônimos (tem o mesmo significado), e seu oposto antônimos; e hiponimia e hiperonimia, os conceitos que refere se a hierarquia entre as palavras. Para como dicionário de ideias comuns que guardam uma hierarquia de forma automatizada entre estes conceitos abordados é o Wordnet. Um tesauro ou repositório de palavras e seus significados com uma hierarquia, como também a ferramenta o synset como repositorio de sinônimos. Abordado estes conceitos, foi iniciado de forma conceitual a explanação sobre os algoritnos de identificacao dd similaridade em palavras, aqueles baseados em tesauros ou na distribuição das palavras nos corpus. É possivel identificar similaridade entre palavras pelo tesauro a partir de uma árvore hierarquia, onde encontra- se a distância entre as palavras(pathlen (c1,c2)). Já a outra abordagem baseada na distribuição de palavras visa como sendo em sua forma gramatical no corpus ou sua presenças em contextos que podem ser alterados conforme a época que esta. No exercício dado em aula foi abordado tanto a primeira parte da aula com a distância de levenshtein para identificar a comparação entre as palavras sugeridas, quanto a segunda parte da aula para explicar sobre os conceitos de tesauro, homografo e homofono. |
| Luana Ferreira do Nascimento | Ao tentar detectar erros de gramática em algum documento, uma boa estratégia é que caso o programa identifique que uma palavra está errada ou fora de contexto, calcular quais palavras corretas estão mais próximas da palavra errada encontrada, para então sugerir a mudança para esta palavra descoberta. Stemming é a ação de reduzir stems a um radical. Já o lema vai tentar reduzir a palavra a sua forma primitiva singular e masculina no dicionário, sendo consideravelmente mais complexa de ser implementada. Cada lema pode ter diversos significados, que vão variar de acordo com o contexto de onde a palavra foi retirada, ainda que a distância de edição das palavras sejam a mesma. Palavras assim são chamadas de homônimos. Dentre estas palavras, temos os homófonos, que são palavras com a mesma fala e os homógrafos que são palavras com a mesma escrita. Palavras polissêmicas são palavras iguais que possuem significados similares porém diferentes. Uma dificuldade na interpretação de linguagens naturais através de máquinas é justamente saber diferenciar estas palavras, pois dependendo do contexto em que a palavra está inserida, ela pode indicar um tema de fala totalmente diferente em uma definição ou outra do termo utilizado. Após capturar as palavras-chave de um texto, podemos utilizar seus significados para tentar compilar o assunto abordado pelo texto, possibilitando sua classificação. Entretanto, muitas das palavras capturadas podem possuir múltiplos sentidos, podendo alterar a categoria do texto de acordo. Por exemplo podemos ter um texto com a utilização frequente da palavra banco. Este texto pode tanto estar se referindo aos bancos de sentar, quanto aos bancos instituições financeiras ou bancos no sentido de depósito de informações (como bancos de dados). |
| Gustavo Zanfelice Dib | União aproximada entre strings: Para isso precisamos de uma nova medida de semelhança entre duas palavras. Por exemplo: Para correção ortográfica, graffe seria girafe, no contexto de computação para biologia, PLN é utilizada para corrigir erros em cadeias de aminoácidos (entre outros usos). Distância de Hamming: Esse algoritmo é utilizado para detectar erros em transferências binárias de comprimentos pré-determinados. O número de bits para a mudança de uma transferência para uma recepção é denotado por distância de Hamming. Por exemplo: Hamming de "PLN" para "PNL" é 2, já a distância de ("UFABC", "UFBA") igual a -1. Isso acontece porque o algoritmo acredita que ambas as palavras possuem o mesmo tamanho. Vale-se destacar que palavras iguais possuem distância 0 pelo algoritmo. Distância de Levenshtein: Diferente de Hamming, esse algoritmo permite comparar palavras de tamanhos distintos e também é usado para medir a diferença entre duas palavras. Essa técnica considera as operações de inserção, exclusão e substituição para contar o número mínimo de alterações necessárias para igualar as duas palavras. Exemplos apresentados: Levenshtein de "para" para "casa" é 2 Levenshtein de "hora" para "hoje" é 2 Isso se deve porque substituição é considerada de custo 2. Por ser extremamente custoso se implementado de forma recursiva "crua" é muito comum utilizar técnicas de memoização (utilizando estruturas de dados auxiliares) Homógrafo vs Homófono: Palavras homófonas são palavras que possuem escritas distintas porém se pronuncia igualmente. Palavras homógrafas são palavras que se escrevem de forma idêntica porém o contexto pode alterar seu significado. (Revisão) Stemming vs Lemma Lema: Reduzir a uma palavra sem flexibilização. Stem: apenas um truncamento direto na palavra original. Polissemia: Palavras que possuem diferentes significados. |
| Estevao Crippa da Veiga | O casamento entre strings pode ser utilizado para fazer correções ortográficas e identificar erros em palavras ou frases. Dois exemplos de comparações que podem ser realizadas são: distância de Hamming e de Levenshtein. A distância de Hamming é utilizada para comparação de transmissões de comprimento fixo e iguais e equivale à quantidade de bits usada na mudança de uma transmissão para uma recepção. Já a distância de Levenshtein baseia-se na quantidade de operações realizadas entre a transmissão e a recepção, sendo inserção, exclusão e substituição as operações permitidas. Homônimo compartilham a mesma forma mas com significados diferentes. A polissemia consiste em uma mesma palavra com diferentes significados. Geralmente as polissemias são sistemáticas, portanto metonímias. Uma maneira de identificar a polissemia é o uso do teste de Zeugma. Já sinônimos são palavras diferentes que compartilham o mesmo significado. Definimos que duas palavras são sinônimas se ambas podem ser substituídas em todas as situações e ambas têm o mesmo significado proposicional. Antônimos são palavras que têm significado oposto em relação a uma característica. Já hiponímia e hiperonímia indicam relação de hierarquia de significados entre palavras, em que uma palavra A é hiponímia de B, se o significado de A é mais específico que B, assim como B é hiperonímia de A nesse mesmo contexto. Podemos definir também similaridade entre palavras, que consiste no compartilhamento do mesmo significado, e é utilizada para recuperação de informações, detecção de plágio, agrupamento de texto. Existem dois tipos de algoritmos muito utilizados para verificar similaridade: baseados em tesauros e baseados em distribuição de palavras. |
Observação:
Arquivo gerado por um programa.