1 faculdades coc trabalho de conclusão de curso

Transcrição

FACULDADES COC
TRABALHO DE CONCLUSÃO DE CURSO
BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO
SISTEMA INTELIGENTE PARA GERAÇÃO DE PSEUDOPALAVRAS
Henrique Vieira Lopes
Marcel Ferreira Nascimento
Orientador: Prof. Lúcio André Castro Jorge
RIBEIRÃO PRETO
2011
1
HENRIQUE VIEIRA LOPES
MARCEL FERREIRA NASCIMENTO
SISTEMA INTELIGENTE PARA GERAÇÃO DE PSEUDOPALAVRAS
Trabalho
de
conclusão
de
curso
apresentado ao Centro Universitário
UNISEB de Ribeirão Preto, como parte
dos requisitos para obtenção do grau de
Bacharel em Ciência da Computação.
Orientador: Prof. Lúcio André Castro
Jorge
RIBEIRÃO PRETO
2011
2
3
TRABALHO DE CONCLUSÃO DE CURSO
Aluno: Henrique Vieira Lopes
Código: 5875
Aluno: Marcel Ferreira Nascimento
Código: 6133
Curso: Ciência da Computação
Semestre/Ano: 8º/2011
Tema: Sistema para geração de pseudopalavras usando método de aprendizado
inteligente.
Objetivos pretendidos: Estudar a viabilidade de se construir um sistema de
aprendizado inteligente que reconheça o padrão existente na ordem das letras em
palavras contidas em um banco de dados para a criação de pseudopalavras.
___/___/______
_____________________________
Lúcio André Castro Jorge
Professor Orientador
___/___/______
_____________________________
Henrique Vieira Lopes
Aluno
___/___/______
_____________________________
Marcel Ferreira Nascimento
Aluno
___/___/______
_____________________________
Paulo Cesar de Carvalho Dias
Coordenador do Curso
4
___/___/______
_____________________________
Prof. Reginaldo Arthus
Vice-Reitor
5
FORMULÁRIO DE AVALIAÇÃO – FATCC
Tema: Sistema para geração de pseudopalavras usando método de aprendizado
inteligente.
Data da apresentação: _____/_____/________
Horário: ____________
Local: _________________________________
Comissão Julgadora:
1) Professor Orientador: _________________________________________________
2) Professor da Área: ____________________________________________________
3) Professor Convidado: _________________________________________________
6
Fatores de Avaliação
Pontuação (0.0 a 2.0)
1. Atualidade e relevância do tema proposto.
2. Linguagem técnica utilizada em relação ao tema e
aos objetivos, e competência linguística.
3. Aspectos metodológicos e formais da editoração
do trabalho escrito - sequência lógica e coerência
interna.
4. Revisão Bibliográfica realizada em relação ao
tema pesquisado.
5. Apresentação oral – segurança e coerência em
relação ao trabalho escrito.
Média: ____________ (_________________________________________________)
Assinaturas dos membros da Comissão Julgadora:
1) _____/_____/________ ________________________________________________
2) _____/_____/________ ________________________________________________
3) _____/_____/________ ________________________________________________
7
A nossos pais pela paciência e apoio.
8
AGRADECIMENTOS
Ao nosso orientador, Prof. Lúcio André Castro Jorge pela dedicação e contribuição,
para a concretização deste trabalho.
Ao mestre Ricardo Basso Garcia que contribuiu com a sugestão do nosso tema de TCC.
Ao Prof. Jean Jacques Groote por nos ajudar a determinar os seguimentos de pesquisa e
desenvolvimento do nosso trabalho.
Ao Prof. Wagner Aparecido Cavali por contribuir com seu conhecimento estatístico
para compreendermos melhor os algoritmos utilizados.
A todos os professores que nos lecionaram aulas durante o curso proporcionando todo
conhecimento necessário para nossa formação acadêmica e profissional.
9
A imaginação é mais importante que o
conhecimento - Albert Einstein
10
RESUMO
Este trabalho buscou contribuir para a análise feita por psicólogos, pedagogos e
fonoaudiólogos no diagnóstico de consciência fonológica com o estudo das técnicas
mais utilizadas no reconhecimento de padrão para desenvolvimento de um programa
que utilize uma delas para reconhecer o padrão existente na ordem das letras em
palavras de um banco de dados. A partir do padrão reconhecido, criar uma lista de
pseudopalavras. Uma vez que criado, foram documentados todos os testes efetuados e
também criado outro programa que faz o mesmo procedimento, mas construído de uma
forma mais simples para compararmos os resultados.
Entre os dois resultados, a rede de bayes apresentou-se melhor, devido a seu
poderoso mecanismo de reconhecimento de padrão, porém as palavras geradas tendiam
a um padrão, já o outro algoritmo, mesmo com uma taxa de acerto inferior gerou
palavras uma variabilidade de letras maior.
11
SUMÁRIO
SUMÁRIO .......................................................................................................................... 12
INTRODUÇÃO .................................................................................................................... 20
CAPITULO 1. RECONHECIMENTO DE PADRÕES ................................................................. 24
1.1 CONSIDERAÇÕES INICIAIS ................................................................................................ 24
1.2 INTRODUÇÃO AO RECONHECIMENTO DE PADRÕES ................................................................. 24
1.3 TÉCNICAS DE RECONHECIMENTO DE PADRÕES ....................................................................... 25
1.3.1 TÉCNICA POR CASAMENTO DE MODELOS .................................................................................. 26
1.3.2 CLASSIFICAÇÃO EM ÁRVORE ................................................................................................... 26
1.3.3 TÉCNICA SINTÁTICA .............................................................................................................. 26
1.3.4 TÉCNICA FUZZY ................................................................................................................... 27
1.3.5 TÉCNICA CONEXIONISTA ........................................................................................................ 28
1.3.6 ALGORITMOS GENÉTICOS ...................................................................................................... 28
1.3.7 TÉCNICAS ESTATÍSTICAS......................................................................................................... 29
1.4 CONSIDERAÇÕES FINAIS .................................................................................................. 30
CAPITULO 2. REDES BAYESIANAS ..................................................................................... 31
2.1 CONSIDERAÇÕES INICIAIS................................................................................................. 31
2.2 TEORIA DA PROBABILIDADE .............................................................................................. 31
2.2.1 NOTAÇÃO PROPOSICIONAL .................................................................................................... 31
2.2.2 ESPAÇO AMOSTRAL, EVENTOS E VARIÁVEIS ALEATÓRIAS. ............................................................. 32
2.2.3 DISTRIBUIÇÃO DE PROBABILIDADE CONJUNTA ........................................................................... 33
2.2.4 PROBABILIDADE A PRIORI ...................................................................................................... 33
2.2.5 PROBABILIDADE CONDICIONAL ............................................................................................... 33
2.2.6 AXIOMAS DA PROBABILIDADE................................................................................................. 34
2.2.7 INDEPENDÊNCIA .................................................................................................................. 34
2.3 REDES BAYESIANAS ........................................................................................................ 35
2.3.1 RACIOCÍNIO PROBABILÍSTICO.................................................................................................. 35
2.3.2 TEOREMA DE BAYES ............................................................................................................. 35
2.3.3 DEFINIÇÃO DE REDES BAYESIANAS ........................................................................................... 36
12
2.3.4 CONSTRUÇÃO DE REDES BAYESIANAS ....................................................................................... 37
2.4 INFERÊNCIA BAYESIANA ................................................................................................... 38
2.4.1 MÉTODOS EXATOS ............................................................................................................... 38
2.4.2 MÉTODOS APROXIMADOS ..................................................................................................... 41
2.5 APRENDIZADO BAYESIANO .............................................................................................. 43
2.5.1 ALGORITMO K2 ................................................................................................................... 43
2.5.2 ALGORITMO EM ................................................................................................................. 44
CAPITULO 3. IMPLEMENTAÇÃO. ...................................................................................... 46
3.1 CONSIDERAÇÕES INICIAIS................................................................................................. 46
3.2 BASE DE PALAVRAS ........................................................................................................ 46
3.3 REDE DE BAYES ............................................................................................................. 48
3.3.1 WEKA ................................................................................................................................ 48
3.3.2 DEFINIÇÃO DE ATRIBUTOS ..................................................................................................... 48
3.3.3 PROJETO ............................................................................................................................ 50
3.4 ALGORITMO DE MÉDIA PONDERADA ................................................................................... 51
3.4.1 DEFINIÇÃO DE ATRIBUTOS ..................................................................................................... 51
3.4.2 CALCULO DE MÉDIAS PONDERADAS ......................................................................................... 51
3.4.3 ESTRUTURA ........................................................................................................................ 51
3.4.4 PROJETO ............................................................................................................................ 52
3.4.5 CONSIDERAÇÕES FINAIS ........................................................................................................ 55
CAPITULO 4. RESULTADO, TESTES E DISCUSSÃO. .............................................................. 57
4.1 CONSIDERAÇÕES INICIAIS ................................................................................................ 57
4.2 REDE DE BAYES ............................................................................................................. 57
4.2.1 TESTES DE TREINAMENTO DA REDE DE BAYES COM A BASE DE PALAVRAS COMPLETA ....................... 57
4.2.2 TESTES DE TREINAMENTO DA REDE DE BAYES APENAS COM PALAVRAS DISTINTAS ........................... 58
4.2.3 RESULTADO DA GERAÇÃO DE PSEUDOPALAVRAS ........................................................................ 59
4.2.4 DISCUSSÃO ......................................................................................................................... 61
4.3 ALGORITMO DE MÉDIA PONDERADA................................................................................... 62
4.3.1 RESULTADOS E TESTES .......................................................................................................... 62
4.3.2 DISCUSSÃO ......................................................................................................................... 67
13
CAPITULO 5. CONCLUSÃO E TRABALHOS FUTUROS. ......................................................... 68
CAPITULO 6. REFERÊNCIAS .............................................................................................. 69
14
LISTA DE QUADROS
Quadro 1 - Exemplo de proposições .............................................................................. 31
Quadro 2 - Proposições compostas................................................................................. 32
Quadro 3 - Tabela verdade ............................................................................................. 32
Quadro 4 - Exemplo de eventos no espaço amostral ...................................................... 32
Quadro 5 - Exemplo de distribuição de probabilidade (DEVORE, 2006) ..................... 33
Quadro 6 - Probabilidade a priori (RUSSEL & NORVIG, 2004) .................................. 33
15
LISTA DE TABELAS
Tabela 1 – Representação da probabilidade de acerto após o treinamento da Rede de
Bayes .............................................................................................................................. 57
Tabela 2 - Representação da probabilidade de acerto após o treinamento da Rede de
Bayes com palavras distintas .......................................................................................... 58
Tabela 3 - Pseudopalavras geradas pela rede ................................................................. 60
Tabela 6 - Teste para geração de pseudopalavras com 4 letras ...................................... 62
16
LISTA DE ILUSTRAÇÕES
Figura 1 – Intersecção (DEVORE, 2006) ....................................................................... 34
Figura 2 - Rede Bayesiana - (RUSSEL & NORVIG, 2004). ......................................... 37
Figura 3 - Algoritmo Enumeração - (RUSSEL & NORVIG, 2004). ............................. 40
Figura 4 - Representação gráfica do processo de construção da base de palavras. ........ 47
Figura 5 - Representação gráfica do processo de geração de pseudopalavras através da
rede de bayes. ................................................................................................................. 50
Figura 6 - Exemplo da estrutura de dados arvore utilizada pelo algoritmo de média
ponderada........................................................................................................................ 52
Figura 7 - Representação gráfica do processo de geração de pseudopalavras através do
algoritmo de média ponderada. ...................................................................................... 53
17
LISTA DE ALGORITMOS
Algoritmo 1 - Enumeração - (VALENTIM , 2007). ...................................................... 39
Algoritmo 2 - Eliminação de Variáveis - (VALENTIM , 2007). ................................... 41
Algoritmo 3 - Ponderação de Amostragem - (VALENTIM , 2007). ............................. 42
Algoritmo 4 - Amostragem de Gibbs - (VALENTIM, 2007) ........................................ 43
Algoritmo 5 - Algoritmo K2 - (COOPER & HERSKOVITS, 1992) ............................. 44
18
LISTA DE EQUAÇÕES
Equação 1 - Probabilidade condicional .......................................................................... 34
Equação 2 - Independência ............................................................................................. 35
Equação 3 - Regra de bayes ............................................................................................ 35
Equação 4 - Somatório dos termos da distribuição conjunta de probabilidade .............. 38
Equação 5 - Cálculos iniciais de média ponderada ........................................................ 54
Equação 6 - Cálculo da probabilidade do novo nó ......................................................... 54
Equação 7 - Recalculo do valor do nó ............................................................................ 54
19
INTRODUÇÃO
Em grande parte as crianças possuem problemas quanto à aprendizagem da
leitura e escrita no ensino fundamental. Com o interesse de resolver esse problema,
psicólogos, pedagogos e fonoaudiólogos buscam investigar a capacidade com que as
crianças desenvolvem a interpretação sobre os símbolos já que a linguagem escrita é a
representação visual da linguagem oral. Este estudo avalia a capacidade de
reconhecimento de palavras após a criança passar pelo processo de informação
fonológico e ortográfico, que lhes ensina as relações entre grafemas e fonemas na qual
uma silaba corresponde a pequenos segmentos sonoros, dando assim a noção de que a
combinação entre as letras do alfabeto produz um som e a combinação desses sons
produz uma palavra (BARREIRA; MALUF, 2003; GINDRI; KESKE-SOARES;
MOTA, 2007).
O reconhecimento de palavras é feito por duas rotas distintas, rota fonológica e a
rota lexical. A rota fonológica utiliza o conhecimento das regras de conversão entre
grafema e fonema para que a construção da pronúncia da palavra possa ser efetuada,
para avaliar esse processo de decodificação é recomendada a leitura de pseudopalavras,
pois determina a capacidade do leitor identificar palavras que ele não conhece. A rota
lexical depende do reconhecimento de uma palavra previamente adquirida, memorizada
no sistema de reconhecimento visual de palavras, recuperação do significado e da
pronúncia por meio de endereçamento direto ao léxico. A avaliação desse processo de
reconhecimento é feito através da leitura de palavras reais isoladas, pois desta forma não
há sugestões psicolinguísticas, pictóricas ou contextuais (CUNHA; CAPELLINI, 2010).
Uma pseudopalavras é uma sequência de fonemas ou grafemas que não determinam
uma palavra da língua (SALLES; PARENTE, 2006).
A avaliação da deficiência de reconhecimento de palavras pode ser realizada
pelo processo de leitura em voz alta, conforme descrito na pesquisa de Marco Pezzani
França (FRANÇA, 2007). França conta que, diante de palavras reais, a pronúncia é
recuperada pela rota lexical, pois após serem reconhecidas no léxico visual de entrada, a
pronúncia é recuperada do léxico fonêmico de saída. No caso da leitura de
pseudopalavras, a identidade dos grafemas é transmitida do sistema de análise visual
para o sistema de conversão grafema-fonema, onde os elementos fonêmicos podem ser
recuperados e agrupados para produzir a pronúncia, utilizando assim a rota fonológica.
França
(2007)
completa
que
palavras
mais
familiares
tendem
a
serem
20
reconhecidas/produzidas mais rapidamente ou mais corretamente e isto caracteriza o uso
da rota lexical na leitura em voz alta, ao passo que, palavras pouco familiares são
reconhecidas/produzidas
mais
lentamente,
de
forma
silabada
ou
com
omissões/substituições de fonemas, o que caracteriza o uso da rota fonológica.
Este trabalho propõe a geração automática de pseudopalavras para auxiliar
psicólogos, terapeutas, pedagogos, professores e pesquisadores no teste de avaliação da
capacidade de reconhecimento de palavras e assim melhorar o diagnóstico de
deficiências no processo de alfabetização. Este é o primeiro estudo em nosso
conhecimento direcionado a geração de pseudopalavras, porém se assemelha com
trabalhos em reconhecimento de padrões linguísticos.
Laila Beatriz Soares Melo (MELO, 2007) utiliza técnicas probabilísticas de
aprendizado de máquina para buscar semelhanças em um texto e categoriza-lo
automaticamente.
Ricardo Basso Garcia (GARCIA, 2006) replicou uma experiência utilizando
redes neurais artificiais que extrai o conhecimento sintático-semântico para formar
sentenças linguísticas.
José Mauro da Silva (SILVA, 2007) em seu mestrado, desenvolveu a extração
de conhecimento de objetos textuais por meio de reconhecimento de padrões, mais
especificamente com técnicas de processamento de linguagem natural e Naive-bayes
(técnica probabilística de mineração de dados).
Em todos estes trabalhos o reconhecimento de padrões é estudado através de um
recurso da inteligência artificial chamado de aprendizagem de máquina. Na
aprendizagem de máquina o reconhecimento de padrão se divide em duas áreas:
reconhecimento de padrão supervisionado, na qual consiste de um professor que
interfere no processo de correção de erros buscando o padrão desejado. A outra área é o
reconhecimento de padrão não supervisionado que consiste na aprendizagem sem
professor ou qualquer outra estrutura que interfira na classificação dos dados
(HAYKIN, 2001).
Dentre as principais técnicas de aprendizagem de maquina que existem podemos
citar redes neurais artificiais, árvores de decisão, mapas auto-organizáveis, redes
bayesianas e modelos de markov. Escolhemos a rede de bayesiana por admitir o
aprendizado a partir da experiência e combinar o melhor da inteligência artificial
clássica e das redes neurais. A rede bayesiana é definida como uma rede probabilística
que utiliza a regra de bayes para calcular suas hipóteses ponderadas por suas
21
probabilidades, onde a hipótese determina a distribuição de probabilidade. A cada
hipótese existe uma probabilidade a priori correspondente. Cada nó da rede possui um
rótulo com a hipótese e uma tabela com as probabilidades, e o padrão reconhecido pela
rede é encontrado de acordo com o percurso feito na mesma, depois de uma série de
treinamentos que permitiu que ela se adaptasse ao número expressivo de dados
correspondentes a uma determinada sequencia de hipóteses (STUART; PETER, 2004).
Com o apoio das redes bayesianas, aplicado na extração do padrão de
relacionamento entre letras de uma palavra, este trabalho propõe extrair de uma
linguagem o padrão de formação das palavras (grafemas) e posteriormente utilizar este
para criar possíveis pseudopalavras. Para isso precisamos de uma base de palavras que
represente a linguagem a quem deve pertencer a pseudopalavra.
A partir da base de palavras, nosso sistema utilizará as técnicas citadas de
reconhecimento de padrão com o objetivo de identificar um padrão estatístico de
combinações de letras, estes padrões serão recombinados para gerar uma nova
pseudopalavra.
Para efeito de comparação de resultados, também foi desenvolvido um programa
que faça a geração de pseudopalavras através de um simples cálculo de média
ponderada, utilizando a mesma base de palavra e os mesmos atributos. Com esta
comparação foi analisado a eficiência de um programa simples versus um sistema
inteligente.
Os produtos deste trabalho serão uma contribuição científica, através de um
trabalho de conclusão de curso, e uma ferramenta que auxilie o diagnóstico de testes da
consciência fonológica na investigação dos processos cognitivos no conhecimento
linguístico.
Como base para o desenvolvimento do sistema proposto neste trabalho, no
capitulo 1 é apresentada uma revisão teórica referente aos conhecimentos necessários
para desenvolvimento do projeto, como conceitos e técnicas de aprendizado de máquina
que é a base para o reconhecimento de padrão dos grafemas, que será realizado no
processamento das palavras.
No capítulo 2 foi aprofundado o estudo de uma técnica probabilística de
reconhecimento de padrão. A Rede de Bayes é um dos ramos de aprendizado de
máquinas e será utilizada na extração e representação do conhecimento referente à
formação das palavras.
22
O capítulo 3 relata a definição da base de palavras e dos atributos necessários
para representação do relacionamento entre as letras, bem como o desenvolvimento dos
sistemas de geração de pseudopalavras a partir dos conceitos citados nos capítulos
anteriores.
O capítulo 4 apresenta testes realizados com a ferramenta desenvolvida, os
resultados, mostrando a probabilidade de acerto e a discussão sobre os resultados
obtidos.
No último capítulo serão apresentadas as conclusões e trabalhos futuros.
23
CAPÍTULO 1 RECONHECIMENTO DE PADRÕES
1.1 CONSIDERAÇÕES INICIAIS
O fato de algumas palavras pertencerem a mesma linguagem implica que elas
possuem um padrão que às define como participante desta, devemos então reconhecer
este padrão para conseguir reproduzi-lo e posteriormente gerar novas palavras.
Neste capítulo, é o início do estudo ao reconhecimento de padrão e algumas de
suas técnicas com o objetivo de aprendê-las para posteriormente aprofundar em uma
específica.
1.1.1 INTRODUÇÃO AO RECONHECIMENTO DE PADRÕES
Reconhecimento de padrões é a área de pesquisa que tem por objetivo a
classificação de objetos em categorias ou classes (THEODORIDIS, 1999). Ele é
formalmente definido como o processo pelo qual um padrão/sinal recebido é atribuído a
uma classe dentre um número predeterminado de classes (HAYKIN, 2001).
Os seres humanos são bons no reconhecimento de padrões, através de um
processo de aprendizagem analisamos o mundo a nossa volta e sem esforço podemos
reconhecer a fonte dos dados (HAYKIN, 2001). A experiência humana de
reconhecimento de padrões se refere a um processo perceptivo em que os padrões
(sensorial, conceitual ou lógico) são analisados e classificados como sendo familiar,
quer no sentido de ter sido uma experiência prévia ou, sendo semelhante ou associado a
uma experiência anterior (HEDE, 1994).
Apesar da naturalidade e simplicidade que o ser humano reconhece padrões, sua
implementação em meios computacionais pode requerer processos bastante complexos
(SILVA, 2007), este trabalho e outras técnicas que permitem aos computadores fazerem
coisas que parecem inteligentes quando feitas por pessoas é estudado em inteligência
artificial (HEDE, 1994).
Embora não seja certamente possível descrever o método o qual o cérebro
humano aprende com experiências passadas para realizar o reconhecimento de padrões,
fica evidente que o aprendizado é um componente indispensável nesta tarefa, tanto para
máquinas quanto para humanos. Em alguns casos o aprendizado é feito com a ajuda de
um professor, ou seja, um agente externo fornece amostras de treinamento já
classificadas, tais amostras tornam-se representantes das classes a que pertencem, elas
24
então podem ser processadas de forma adequada para que as informações específicas de
sua classificação possam ser extraídas através delas.
Este processo denomina-se
reconhecimento de padrões supervisionado. Se as amostras fornecidas para
aprendizagem não foram previamente classificadas, temos um caso de reconhecimento
de padrões não supervisionado. Nesses casos, a aprendizagem se dá pela descoberta dos
grupos naturais inerentes ao conjunto de treinamento, ou seja, os padrões são associados
a uma classe que é aprendida de acordo com a semelhança dos padrões de treinamento
(PAL S.; PAL A., 2001).
Aplicações de reconhecimento de padrões incluem reconhecimento de
caracteres, diagnóstico médico, problemas bancários, análise de sinais e imagens
biomédicas, reconhecimento e compreensão de línguas, identificação de faces humanas
e
impressões
digitais,
confiabilidade,
automação
industrial,
socioeconômica,
arqueologia, controle de qualidade e outras (STEINER, 1995).
1.2
TÉCNICAS DE RECONHECIMENTO DE PADRÕES
A
maioria
das
abordagens
concebidas
para
resolver
problemas
de
reconhecimento de padrão utiliza um conjunto de medidas que definem a característica
de um padrão. Assim a escolha cuidadosa dessas medidas é importante, pois o ideal é
utilizar todas as medições de um determinado padrão, em contra partida muitas
características tornam o classificador confuso e podem ser redundantes. Duas grandes
abordagens são utilizadas tradicionalmente para ajudar nesta tarefa. A primeira é a
seleção de recursos que visa selecionar um subconjunto das medidas que com o objetivo
de otimizar a separação das classes e ao mesmo tempo aumentar a homogeneidade
dentro da própria classe. Outra abordagem é chamada de extração de características, que
visa reduzir o número de medidas disponíveis através de uma transformação sobre o
vetor original de medidas que otimize algum critério de separação entre as classes (PAL
S.; PAL A., 2001).
Diversas técnicas vêm surgindo ao longo dos anos, graças ao grande interesse e
avanços na área de reconhecimento de padrões a fim de fornecer técnicas
progressivamente melhores, dentre elas podemos citar como as mais importantes o
casamento de modelos, classificação em arvore, sintática, Fuzzy, conexionista,
algoritmos genéticos e, estatísticas (JAIN; DUIN; MAO, 2000) (PAL S.; PAL A.,
2001).
25
1.2.1 TÉCNICA POR CASAMENTO DE MODELOS
É uma das abordagens mais antigas e simples para reconhecimento de padrões.
Casamento é uma operação genérica de reconhecimento de padrão que é utilizado para
determinar a similaridade entre duas entidades do mesmo tipo. Nesta técnica, um padrão
a ser reconhecido é comparado com um modelo armazenado, muitas vezes aprendido a
partir do conjunto de treinamento (JAIN; DUIN; MAO, 2000). Por exemplo, no caso de
imagens o modelo é uma forma 2D a qual é levado em consideração suas variações
como translação, rotação e mudanças na escala, a medida de similaridade entre os
modelos é que definirá o reconhecimento do padrão.
A maior desvantagem desta técnica está no alto custo computacional, mais a
disponibilidade de processadores mais rápidos a tornou mais viável.
1.2.2 CLASSIFICAÇÃO EM ÁRVORE
O modelo de classificação em árvore fornece uma descrição hierárquica da base
de conhecimento onde a raiz é o topo e cada exemplo é passado para baixo da árvore.
Em cada nó são tomadas decisões até chegar a um nó terminal, este nó é responsável
pelo rótulo de classificação do padrão. O aspecto mais crucial de classificação baseado
em árvores é a construção automática de árvores a partir de um conjunto de exemplos.
Dentre a grande diversidade de algoritmos existentes as principais diferenças são
as regras usadas para decidir e na estratégia de poda (a remoção de sub-árvores
redundantes). Para ambas as atividades são utilizados critérios de otimização como
ganho de informação ou entropia.
Por ser de fácil compreensão este modelo tem sido popular em áreas como
biologia e as ciências médicas (PAL S.; PAL A., 2001).
1.2.3 TÉCNICA SINTÁTICA
Esta abordagem faz uma analogia entre a estrutura hierárquica de padrões e a
sintaxe das linguagens. Os padrões são especificados como construção de sub-padrões
em várias formas de composição assim como frases e sentenças são constituídas pela
concatenação de palavras e as palavras por sua vez são constituídas concatenando
caracteres.
A vantagem desta abordagem é que sub-padrões mais simples, chamados de
“primitivo padrão”, são muito mais fáceis de reconhecer que os próprios padrões. A
descrição estrutural dos padrões em termos de um conjunto de padrões primitivos e as
operações de sua composição é denominada linguagem. As regras que ditam a
26
composição entre sub-padrões é denominada gramática e normalmente podem ser
expressas por meio de lógica e operações matemáticas.
Um sistema de reconhecimento de padrão sintático pode ser considerado
constituído de três partes principais: o pré-processamento, a descrição do padrão e
análise da sintaxe. Basicamente, o processo de pré-processamento consiste em
aproximar o padrão de entrada a um modelo aceitável, por exemplo, em uma imagem
em preto-e-branco pode ser codificada em uma matriz ou uma expansão em série de
Fourrier. Então cada padrão pré-processado é tratado para extrair primitivas em relação
a ele no processo de descrição do padrão. A decisão sobre se o padrão apresentado está
sintaticamente correto, ou seja, pertente à classe de padrões descrita pela gramática é a
tarefa do analisador de sintaxe (FU, 1977).
1.2.4 TÉCNICA FUZZY
Esta técnica de reconhecimento de padrões tem o objetivo de aprimorar o
agrupamento dos dados, levando em consideração a incerteza de classificação de um
atributo. O objetivo do agrupamento é a partição de um conjunto de dados em grupos
homogéneos, onde o elemento de um grupo compartilha atributos semelhantes entre o
próprio grupo e não compartilham atributos semelhantes com elementos de outro grupo
(PAL S.; PAL A., 2001).
Nos agrupamentos tradicionais é utilizada a lógica booleana, onde um elemento
tem a obrigatoriedade de pertencer a um grupo e sua unidade de participação é um. A
lógica Fuzzy é uma generalização do agrupamento tradicional onde a participação de
um elemento em um grupo é medida usando valores de pertinência, entre 0 e 1, onde 0
representa que é completamente incompatível com um atributo, 1 representa que é
completamente compatível com um atributo e valores entre 0 e 1 representam que é
parcialmente compatível com um atributo, com grau de participação de acordo com este
valor (SANDRI; CORREA, 1999).
Em outras palavras a lógica Fuzzy dá uma noção de incorporação, no sentido de
que a melhor solução para um problema booleano pode ser encontrada através da
visualização do espaço, submetendo-a a diferentes restrições, permitindo assim uma
liberdade maior para o algoritmo evitar erros que são forçados pelas imposições da
teoria clássica dos conjuntos.
A técnica Fuzzy para o reconhecimento de padrões pode ser aplicada na
identificação de um padrão desconhecido, em características linguísticas, associado a
27
árvores de decisão, gramáticas de estrutura frasal, e assim por diante, que levam a
formas difusas de métodos clássicos de classificação supervisionada (PAL S.; PAL A.,
2001).
1.2.5 TÉCNICA CONEXIONISTA
O ser humano realiza o reconhecimento de padrões através de um processo de
aprendizagem, e assim acontece com a técnica conexionista ou redes neurais. Uma rede
neural realiza o reconhecimento de padrões passando inicialmente por uma sessão de
treinamento, o aprendizado supervisionado. Mais tarde apresenta-se à rede um novo
padrão que pertence à mesma população de padrões do treinamento, a rede consegue
então identificar o novo padrão apresentado, com base no conhecimento extraído da
fase de treinamento.
Genericamente podemos dividir as máquinas de reconhecimento de padrões que
utilizam redes neurais em:

Uma rede não supervisionada para extração de características
(transformação de um ponto X em um ponto intermediário Y para reduzir
a dimensionalidade) e uma rede supervisionada para classificação (o
mapeamento do ponto intermediário Y em uma das classes);

Uma rede única de múltiplas camadas alimentada adiante, utilizando
aprendizagem supervisionada. Neste modelo a extração de características
é feita por unidades ocultas dentro da rede (HAYKIN, 2001).
Uma rede neural pode ser vista como grafos ponderados, onde os nós são os
neurônios e as arestas a interconexão entre eles (PAL S.; PAL A., 2001). Cada neurônio
é composto por um vetor de entrada, para cada entrada há um peso correspondente e a
soma das entradas ponderadas pelos pesos correspondentes é chamada de saída linear, a
esta saída é aplicada uma função de ativação e o resultado desta operação é o sinal de
ativação que passa pelas arestas (RESENDE, 2003).
O reconhecimento de padrão conexionista tem uma resistência natural ao ruído,
tolerância a imagens distorcidas, capacidade superior em reconhecer imagens
parcialmente degradadas e possibilita processamento paralelo (PAL S.; PAL A., 2001).
1.2.6 ALGORITMOS GENÉTICOS
Os algoritmos genéticos são estratégias evolucionárias inspiradas no principio de
que o mais apito sobrevive, direcionado a evolução, seleção natural, e algumas leis
28
genéticas. Eles são capazes de oferecer uma solução próxima do ideal com uma boa
performance pois ele não fica preso num mínimo local.
A técnica assume um conjunto de soluções ligadas umas nas outras, chamadas
de cromossomos. Nestas soluções são aplicadas várias iterações, chamadas de gerações,
cada geração possui uma função que indique os elementos mais aptos para a solução,
que são chamados de cromossomos parentes e são então selecionados para a
reprodução. O processo de reprodução tem operações como seleção/reprodução,
crossover e mutação, que definem o novo conjunto de elementos, teoricamente mais
aptos. Essas operações são repetidas até que o conjunto de dados seja estabilizado, então
a última solução será a mais próxima da realidade (PAL S.; PAL A., 2001).
1.2.7 TÉCNICAS ESTATÍSTICAS
No início do desenvolvimento de reconhecimento de padrões os seus praticantes
logo perceberam que as estatísticas e a teoria das probabilidades eram as ferramentas
ideais que precisavam. A estatística ajudou a modelar a variabilidade dos padrões no
espaço, através de distribuições multiderivadas. Também foi utilizado o método clássico
de discriminação linear para maximizar a relação entre a variância dos grupos e para
dentro do grupo, outras técnicas também foram construídas usando outros métodos,
como mínimos quadráticos e programação linear (PAL S.; PAL A., 2001).
A teoria em geral consiste em que, a partir de um modelo reconhecido, o mesmo
é transformado em um vetor de características e posteriormente gera-se um padrão na
base. De posse dessa base treinada, realiza-se uma operação matemática que compara
um novo elemento com o padrão da base.
As técnicas estatísticas tradicionais são regressão logística e árvores de classificação e
regressão. A ideia básica da regressão logística é estabelecer uma relação linear entre as
variáveis explicativas e a variável resposta, utilizando máxima verossimilhança. As
árvores de classificação e regressão são métodos de regressão não paramétricos, que
tem por objetivo estabelecer uma relação entre um vetor de variáveis preditoras e uma
única variável de respostas, o vetor é ajustado por sucessivas divisões binárias do
conjunto de dados de forma a deixar o subconjunto cada vez mais heterogêneo. Os
componentes básicos de uma árvore de regressão são os nós e as regras de divisão
(FERREIRA;SOARES;CRUZ, 2001).
Os melhores modelos para reconhecimento de padrão provêm da teoria de bayes,
que se aplica a todos os métodos quadráticos, lineares ou parciais. A técnica bayes
29
consiste em avaliar hipóteses estatísticas com a teoria de probabilidade à posteriori, ela
consegue mostrar soluções ótimas minimizando custo e probabilidade de erro
(FUKUNAGA, 1990).
1.3
CONSIDERAÇÕES FINAIS
Neste capítulo foi estudado o que é reconhecimento de padrão e as diversas técnicas
que podem ser aplicadas, chamando mais a atenção para as técnicas probabilísticas, pois
podem representar a frequência das combinações de letras em uma palavra e assim
extrair as maiores.
No próximo capítulo será apresentado um estudo mais detalhado sobre uma técnica
específica das técnicas probabilísticas de reconhecimento de padrões.
30
CAPÍTULO 2 REDES BAYESIANAS
2.1
CONSIDERAÇÕES INICIAIS
Com o estudo realizado no capítulo anterior que, evidenciou a necessidade de
reconhecimento de padrões entre as letras para desenvolvermos novas pseudopalavras
neste capítulo será apresentado primeiramente uma revisão sobre a teoria das
probabilidades e posteriormente um estudo detalhado referente as Redes Bayesianas.
2.2
TEORIA DA PROBABILIDADE
2.2.1 NOTAÇÃO PROPOSICIONAL
A proposição é representada por meio de palavras ou uma sequência de símbolos
que afirma algo como verdadeiro. Essas afirmações são feitas com base em notação
lógica, na qual se resulta em valores atômicos: verdadeiro V, falso F (ALENCAR
FILHO, 2002).
Exemplos de proposições:
p = A Terra é redonda.
q = O mar é azul.
r = O número pi é racional.
s = Henrique é estudante.
Quadro 1 - Exemplo de proposições
Estas são proposições simples quando combinadas se tornam proposições
compostas A sua compreensão se dá por meio de operações lógicas efetuadas em
cadeia. Toda proposição composta depende unicamente das proposições simples que
pertencem a ela, sendo assim o resultado das partes resulta no todo (ALENCAR
FILHO, 2002).
As proposições compostas são construídas por conectivos como NÂO (~, ¬), E
(^) , OU (v), SE (→), SE SOMENTE SE (↔) .
Exemplos de proposições compostas:
31
s = (p ^ q)
s = (~p ^ q) v (p ^ ~r)
s = (~p ^ q) → (p ^ ~r)
s = (q ↔ ~r)
Quadro 2 - Proposições compostas
A partir das proposições compostas podemos criar a tabela verdade. Para sua
construção é utilizado o teorema, na qual n é o número de proposições simples, 2 n é o
número de linhas e as colunas são todas as proposições (ALENCAR FILHO, 2002).
Exemplo de tabela verdade:
p
q
(p ^ q)
V
F
F
V
V
V
F
F
F
F
V
F
Quadro 3 - Tabela verdade
2.2.2 ESPAÇO AMOSTRAL, EVENTOS E VARIÁVEIS ALEATÓRIAS.
O espaço amostral é representado pela letra S, que significa o conjunto de todos
os resultados possíveis para um determinado experimento. Já os eventos são os
subconjuntos do espaço amostral. Um evento atômico consiste em uma especificação
completa dos estados observáveis do experimento aleatório. Por exemplo:
Ao fazer o lançamento de uma moeda os eventos obtidos são:
Evento 1: CCKC
Evento 2: KKKC
Evento 3: CCKC
Quadro 4 - Exemplo de eventos no espaço amostral
Os possíveis resultados de um espaço amostral são associados a rótulos,
chamados de variável aleatória (DEVORE, 2006). As mesmas podem ser classificadas
em 3 tipos: Variáveis aleatórias booleanas (assumem valores do tipo verdadeiro ou
32
falso), variáveis aleatórias discretas (assumem valores enumeráveis) e variáveis
contínuas (assumem valores reais como os números entre 0 a 1)
(RUSSEL &
NORVIG, 2004)
2.2.3 DISTRIBUIÇÃO DE PROBABILIDADE CONJUNTA
A distribuição de probabilidade conjunta determina as probabilidades associadas
aos possíveis valores de qualquer variável X. A distribuição denota como a variável X
foi distribuída de tal forma para que probabilidade total seja igual a um. Por exemplo:
Suponha que queremos saber qual tipo computador será mais vendido no inicio
do ano, laptop ou desktop.
X = 1 se o cliente comprar um laptop
0 se o cliente comprar um desktop
Se 20% dos compradores escolheram laptop, a distribuição fica dessa forma:
P(0) = P(X = 0) = P (próximo cliente comprar laptop) = 0,8
P(1) = P(X = 1) = P (próximo cliente comprar desktop) = 0,2
Quadro 5 - Exemplo de distribuição de probabilidade (DEVORE, 2006)
2.2.4 PROBABILIDADE A PRIORI
Também conhecia como probabilidade incondicional é a suposição de uma
informação pré-estabelecida na ausência de informações. Por exemplo:
Os possíveis valores para o lançamento de um dado.
P(Dado) = <1, 2, 3, 4, 5, 6>
Também pode representar um intervalo de variáveis contínuas. Por exemplo:
P(X = x) = U [18, 26](x)
Sendo U o intervalo das possíveis temperaturas em graus Celsius.
Quadro 6 - Probabilidade a priori (RUSSEL & NORVIG, 2004)
2.2.5 PROBABILIDADE CONDICIONAL
A probabilidade condicional é a relação entre duas probabilidades a priori. O
quanto uma probabilidade é capaz de influenciar a ocorrência de outra sendo a
probabilidade de A dado que ocorreu B é definida pela equação:
33
P(A | B) = P (A ∩ B)
P(B)
Equação 1 - Probabilidade condicional
E pelo diagrama de Venn.
Figura 1 – Intersecção (DEVORE, 2006)
2.2.6 AXIOMAS DA PROBABILIDADE
P(A) representa a probabilidade de ocorrência do evento A. Para que essa
probabilidade seja consistente devem-se satisfazer os axiomas abaixo:
Axioma 1
0 <= P(A) <= 1
Axioma 2
P(S) = 1
Axioma 3
Se A1, A2, A3,... , An for um conjunto mutuamente exclusivo, a junção de todas essas
probabilidades resulta em 1.
Quadro 7 - Axiomas de probabilidade
2.2.7 INDEPENDÊNCIA
A independência ocorre quando a ocorrência de uma probabilidade não interfere
no valor da outra. Por exemplo: a ocorrência do evento B dada à probabilidade de A, o
valor de P(A | B) é igual ao valor de A, pois B não interfere no valor da probabilidade
condicional.
A proposição que define a independência de A e B é dada por:
34
Equação 2 - Independência
P (A ∩ B) = P(A) . P(B)
A independência condicional também pode ocorrer de maneira múltipla. Basta
que exista uma série de eventos (A1, A2, ...., An) que ocorram sequencialmente na qual
o evento A1 não interfira na probabilidade do evento A2 e assim sucessivamente
(DEVORE, 2006).
2.3
REDES BAYESIANAS
2.3.1 RACIOCÍNIO PROBABILÍSTICO
A aleatoriedade e julgamento incerto faz parte do mundo real. Por isso
precisamos de paradigmas que suportem a represenção de medidas quantitativas de
declarações incertas e métodos para combinação das medidas de raciocínio para tomada
de decisões.
A teoria das probabilidades é o método em vigor para lidar com a incerteza,
tanto que vem sendo estudado muito recentemente (KJAE RULFF; MADSEN, 2008).
Esse raciocínio é utilizado de tal forma que permite o relacionamento de independências
condicionais denotado que o valor de X interfere no valor de Y.
2.3.2 TEOREMA DE BAYES
Este teorema foi descrito baseado no conceito de independência probabilística,
sendo assim principal requisito para muitos sistemas de IA que usam inferência
probabilística.
A equação da regra de bayes é dada por:
Equação 3 - Regra de bayes
P(A | B) = P(B | A) P(A)
P(B)
Para que o teorema seja aplicado precisa-se de três probabilidades condicionais e
duas incondicionais.
Exemplo:
35
Possui durante 50% do tempo rigidez no pescoço quem tem
meningite.
Probabilidade de um paciente possuir meningite é 1 / 50000.
Probabilidade de qualquer um possuir rigidez no pescoço é 1 / 20.
P(s | m) = 0,5
P(m) = 1 / 50000
P(s) = 1 / 20
P(m | s) = P(s | m) P(m) = P(0,5 | 1/50000) = 0,0002
P(s)
P(1/20)
Quadro 8 - Aplicação da regra de bayes
O uso da regra de bayes é aplicado em cada relação da rede bayesiana de acordo
com a arquitetura que foi criada a rede (RUSSEL & NORVIG, 2004) .
2.3.3 DEFINIÇÃO DE REDES BAYESIANAS
Uma rede bayesiana é um grafo orientado que possui a distribuição de probabilidade
conjunta total de um espaço amostral.

Um conjunto de variáveis aleatórias que constitui os nós da rede, que possam ser
tanto discretas quanto contínuas.

Um conjunto de elos dirigidos entre os nós para representar a ligação de uma
variável aleatória com outra. O nó pai aponta com uma flecha para o nó filho.

Cada nó Xi possui uma distribuição de probabilidade condicional P(Xi |
Pais(Xi)) que representa o efeito dos pais sobre o nó.

Não deve possuir ciclos. Por isso é a rede bayesiana é um grafo acíclico.
36
Exemplo de rede Bayesiana:
Figura 2 - Rede Bayesiana - (RUSSEL & NORVIG, 2004).
Toda variável aleatória, Xi é condicionalmente independente de qualquer
subconjunto de nós que não são seus descendentes, conhecidos os nós pais de Xi
(representados por pa(Xi)). Assim, considerando-se X1, X2,..., Xn como os nós de uma
rede bayesiana e tomando-se uma tabela condicional correspondente a cada nó
(RUSSEL & NORVIG, 2004).
2.3.4 CONSTRUÇÃO DE REDES BAYESIANAS
Para a construção de redes bayesianas é preciso ordenar as variáveis aleatórias.
Assim na distribuição conjunta de probabilidade P(X1, X2, ..., X3), o valor de X1 é
considerado como valor raiz (PEARL, 1986a).
Passos para criar uma rede bayesiana:
1. Escolha o conjunto de variáveis relevantes Xi que descrevam o domínio.
2. Defina uma ordenação para as variáveis.
3. Enquanto restarem variáveis no conjunto:
a) Selecione uma variável Xi e adicione um nó para ela à rede.
b) Defina os pais de Xi (pa(Xi)) com algum conjunto mínimo de nós que já estão
na rede, tal que a propriedade de independência condicional seja satisfeita.
c) Defina a tabela de probabilidades condicionais de Xi.
Quadro 9 - Construção da rede de bayes (RUSSEL & NORVIG, 2004).
O bom funcionamento da rede bayesiana é extremamente dependente da sua
estrutura, tanto que os passos anteriores garantem a produção de uma rede acíclica.
A rede precisa garantir a sua distribuição de variáveis de acordo com as funções causais,
37
na qual a ordem que os nós são acessados determina a causa e efeito. Todos os valores
das variáveis devem ser exaustivos (KJAE RULFF; MADSEN, 2008).
2.4
INFERÊNCIA BAYESIANA
O processo de consulta em um sistema de redes bayesianas é computar a
distribuição da probabilidade condicional para um conjunto de variáveis de consulta,
dado os valores de um conjunto de variáveis de evidência. Isso é chamado inferência
bayesiana e permite responder a uma série de “consultas” sobre um domínio de dados.
Por exemplo, na área médica, a principal tarefa consiste em obter um diagnóstico para
um determinado paciente apresentando certos sintomas (evidências). Esta tarefa consiste
em atualizar as probabilidades das variáveis em função das evidências (VALENTIM ,
2007).
Há três tipos distintos de algoritmos de inferência: exatos, aproximados e
simbólicos. Abordaremos nesta monografia apenas os exatos e aproximados. Um
algoritmo de inferência denomina-se exato se as probabilidades dos nós são calculadas
somente com erros de arredondamento e as limitações de cálculo dos computadores. Os
algoritmos por aproximação utilizam distintas técnicas de simulação para obter valores
aproximados das probabilidades. Em geral, estes algoritmos são utilizados em casos em
que os algoritmos exatos não são aplicáveis ou quando custo computacional é muito alto
(CASTILHO & GUTIERREZ, 1997).
2.4.1 MÉTODOS EXATOS
2.4.1.1 ALGORITMO DE ENUMERAÇÃO
Qualquer probabilidade condicional pode ser calculada pelo somatório de termos
da distribuição conjunta total dada pela formula abaixo:
Equação 4 - Somatório dos termos da distribuição conjunta de probabilidade
P( X | e)    P( X , e, y)
y
A equação permite responder a qualquer consulta P(X|e) a partir da distribuição
conjunta total da rede bayesiana que será utilizada no Algoritmo 1 e a Figura 3. Porém,
não é interessante ter quer construir explicitamente uma distribuição conjunta total, pois
38
uma consulta teria complexidade de tempo O(n 2 n ) e complexidade de espaço O( 2 n )
para uma rede com n nós booleanos (RUSSEL & NORVIG, 2004). A ideia básica do
algoritmo de enumeração é avaliar a sem ter que montar explicitamente a tabela de
probabilidade conjunta total. Apenas, percorrem-se os nós da rede propagando as
evidências e extraindo as probabilidades para que sejam feitos os somatórios e
multiplicações necessárias.
Sabendo que qualquer proposição a é equivalente à disjunção de todos os
eventos atômicos em que a é válida, denota-se tal conjunto por e(a). Sabendo também
que os eventos atômicos são mutuamente exclusivos (VALENTIM , 2007).
“A probabilidade de uma proposição é igual à soma das probabilidades dos
eventos atômicos em que ela é válida” (RUSSEL & NORVIG, 2004).
Algoritmo 1 - Enumeração - (VALENTIM , 2007).
39
Figura 3 - Algoritmo Enumeração - (RUSSEL & NORVIG, 2004).
2.4.1.2 ALGORITMO DE ELIMINAÇÃO DE VARIÁVEIS
O algoritmo de eliminação de variáveis é um melhoramento do algoritmo
anterior. A ideia é efetuar os cálculos apenas uma vez e guardar os resultados para uso
posterior. Essa é uma forma de programação dinâmica desenvolvida no Algoritmo 2.
(RUSSEL & NORVIG, 2004).
Dada uma rede bayesiana sobre um conjunto de variáveis, um conjunto de
evidência E com seus respectivos valores observados em e, e uma variável de consulta
Xq, a computação de P(Xq|e) envolve apenas um subconjunto de distribuições de
probabilidade associadas à rede. Se a distribuição de probabilidades P(Xi|pa(Xi)) é
necessária para o cálculo da consulta, então diz que Xi é uma variável de requisito. O
conjunto de variáveis de requisito é denotado por XR. Variáveis de consulta Xq
pertencem necessariamente a XR, mas nem todas as variáveis E pertencem a XR
(VALENTIM , 2007).
40
Algoritmo 2 - Eliminação de Variáveis - (VALENTIM , 2007).
2.4.2 MÉTODOS APROXIMADOS
Estes algoritmos também são conhecidos como algoritmos de amostragem
estocástica. A ideia principal deste método aproximado é usar o modelo da rede
bayesiana para simular a influência da evidência sobre o resto das variáveis (JENSEN,
2001). Neste algoritmo as tabelas de probabilidade condicional da rede, gera-se um
conjunto de amostras selecionadas aleatoriamente, então se realiza inferência, isto é,
aproximam-se probabilidades de variáveis de “consulta” pela frequência de suas
aparições na amostra. A exatidão dos resultados vai depender do tamanho das amostras
(do número de iterações que geram as amostras) e, diferentemente dos métodos exatos,
a estrutura da rede não é relevante no cálculo da inferência, sendo essa uma de suas
vantagens principais (VALENTIM, 2007).
2.4.2.1 AMOSTRAGEM ENCAMINHADA
A função básica de qualquer algoritmo de amostragem é a geração de amostras a
partir de probabilidade conhecida. Por exemplo, uma moeda imparcial pode ser
considerada uma variável aleatória Moeda com valores <cara,coroa> e uma distribuição
a priori P(Moeda) = <0,5,0,5>. A amostragem a partir dessa distribuição é exatamente
igual ao lançamento da moda: com probabilidade 0,5 ela retornará cara, e com
probabilidade 0,5 retornará coroa. Dada uma fonte de números aleatórios no intervalo
[0,1], é uma questão simples a amostragem de qualquer distribuição sobre uma única
variável (RUSSEL & NORVIG, 2004).
O processo de amostragem aleatória para redes bayesianas gera eventos a partir
de uma rede que não tem nenhuma evidência associada a ela. A ideia é fazer a
41
amostragem uma variável de cada vez, em ordem topológica. A distribuição de
probabilidade a partir da qual se obtêm uma amostra do valor está condicionada aos
valores já atribuídos aos pais da variável (VALENTIM , 2007).
2.4.2.2 PONDERAÇÃO DE PROBABILIDADE
É o método de simulação estocástico mais implementado para inferência em
redes bayesianas como demonstrado no Algoritmo 3, em parte por causa da sua fácil
implementação e rápido tempo de convergência comparado com o algoritmo
amostragem encaminhada. O algoritmo fixa os valores para as variáveis de evidência E
e efetua a amostragem apenas das amostragens restantes X e Y. Garantindo que cada
evento gerado será consistente com a evidência. Porém, nem todos os eventos são
iguais. Antes de efetuar as contas na distribuição para a variável de consulta, cada
evento é ponderado pela probabilidade de que o evento concorde com a evidência,
medida pelo produto das probabilidades condicionais para cada variável de evidência,
dados os seus pais. Intuitivamente, eventos em que a evidência real parece improvável
devem receber menor peso (VALENTIM , 2007).
Algoritmo 3 - Ponderação de Amostragem - (VALENTIM , 2007).
42
2.4.2.3
AMOSTRAGEM DE GIBBS
A amostragem de Gibbs denomina-se de um nó é condicionalmente
independente de todos os outros nós de uma rede dados seus pais, filhos e pais de seus
filhos. Essa afirmação é equivalente à especificação de que um nó é independente de
seus não-descendentes, dados seus pais. Em matemática, física ou estatística a
amostragem de Gibbs é um método usado para gerar uma sequência de amostras da
distribuição de probabilidade conjunta das variáveis aleatórias. O propósito dessa
sequência é aproximar a distribuição conjunta ou computar uma integral (CASELLA &
GEORGE, 1992).
A principal característica desse comparado aos outros algoritmos de amostragem
é de que geram cada evento a partir do nada, já a amostragem de Gibbs gera cada evento
fazendo uma mudança aleatória no evento precedente. Portanto, deve-se pensar que a
rede se encontra em um determinado estado atual especificando um valor para uma das
variáveis não de evidência x. Então, o algoritmo vagueia ao acaso pelo espaço de
atribuições completas possíveis, invertendo uma variável de cada vez, mas mantendo
fixas as variáveis de evidência como demonstrado no Algoritmo 4 (VALENTIM, 2007).
Algoritmo 4 - Amostragem de Gibbs - (VALENTIM, 2007)
2.5
APRENDIZADO BAYESIANO
2.5.1 ALGORITMO K2
O algoritmo K2 avalia as possíveis topologias de uma rede bayesiana calculando
a probabilidade dessa topologia gerar uma base de dados. O algoritmo começa
assumindo que um nó não tem antecessores e incrementa o número de antecessores
43
adicionando o antecessor que resulta no maior aumento de probabilidade da estrutura
gerar a base de dados como demonstrado no Algoritmo 5. Na adição de mais um
antecessor ao nó não aumenta mais a probabilidade, dessa forma o nó para de receber
antecessores e o algoritmo faz o mesmo para o nó seguinte. Este algoritmo requer uma
ordenação das variáveis e faz uso de um método de pontuação bayesiana para alcançar
seu objetivo, que é encontrar a estrutura de rede bayesiana S mais provável, dado um
conjunto de dados D. Logo, o que este algoritmo busca é o maior valor possível para a
probabilidade P(S|D). Admitindo que R é uma rede Bayesiana que tem estrutura gráfica
S e probabilidades condicionais associadas à estrutura Θ, determinaram uma fórmula
para calcular a probabilidade P(S|D) supondo que nenhum conjunto de probabilidades
condicionais Θ é preferido para uma estrutura S antes de se analisar a base de dados
(COOPER & HERSKOVITS, 1992).
Algoritmo 5 - Algoritmo K2 - (COOPER & HERSKOVITS, 1992)
2.5.2 ALGORITMO EM
É o algoritmo que faz estimação por máxima verossimilhança de acordo com
determinado conjuntos de dados (distribuição conjunta de probabilidade).
44
A função de máxima verossimilhança pode ser definida densidade conjunta de n
variáveis aleatórias, digamos F x1,...,xn(x1, . . . , xn; θ), considerada como função de
θ. Em particular, se X1, . . . ,Xn é uma amostra aleatória da densidade f(x; θ), então a
função de verossimilhança é f(x1; θ)f(x2; θ) . . . f(xn; θ).
O algoritmo EM estrutural é utilizado para aprender estrutura e parâmetros a partir
de dados incompletos. Este algoritmo, em cada iteração e com uma estrutura dada
inicialmente, completa os dados faltosos mediante uma aproximação. A partir desses
dados completados, realiza uma busca por estruturas, avaliando cada estrutura candidata
com métricas aproximadas. Essa estrutura encontrada será utilizada na próxima iteração
do algoritmo. Após várias iterações, o algoritmo desenvolve uma melhor estrutura para
os dados originais (LUNA ,2011) .
2.6
CONSIDERAÇÕES FINAIS
Com o estudo realizado neste capítulo foi compreendido que existe uma alta
complexidade nas Redes Bayesianas, porém concluímos que seu modelo simples já será
suficiente para a extração do padrão existente entre as letras de uma palavra.
45
CAPÍTULO 3 IMPLEMENTAÇÃO
3.1
Com base nos estudos realizados podemos definir que é tecnicamente possível a
construção de pseudopalavras, utilizando rede de bayes. O próximo passo é criar uma
base de palavras confiável e desenvolver um programa que faça a leitura letra a letra das
palavras e gere pseudopalavras, utilizando as técnicas estudadas.
Para efeito de comparação também será desenvolvido um programa simples que
utiliza média ponderada para calcular a relação entre os atributos e gerar
randomicamente uma pseudopalavra.
3.2
BASE DE PALAVRAS
Para a realização do desenvolvimento e teste dos métodos estudados é necessário
utilizar uma base de palavras que represente satisfatoriamente uma língua conhecida.
Escolhemos a língua portuguesa por ser a linguagem em que somos alfabetizados e
assim podemos distinguir facilmente uma palavra existente, gramaticalmente válida ou
gramaticalmente inválida.
Para representar a língua portuguesa escolhemos os livros “A Mão e a Luva”,
“Casa Velha”, “Contos Fluminenses”, “Dom Casmurro”, “Esaú e Jacó”, “Helena”,
“Histórias da Meia Noite”, “Histórias Sem Data”, “Iaiá Garcia”, “Memorial de Aires”,
“O Alienista”, “O Guarani”, “Páginas Recolhidas”, “Papeis Avulsos”, “Quincas Borba”,
“Relíquias de Casa Velha” e “Ressurreição” do autor Machado de Assis, “A
Moreninha” de Joaquim Manuel de Macedo, “Iracema” de José de Alencar e “O
Cortiço” de Aluízio de Azevedo. Totalizando 20 livros da literatura clássica portuguesa.
46
Figura 4 - Representação gráfica do processo de construção da base de palavras.
Conforme apresentado na Figura 4 , esses livros foram importados na integra
para um banco de dados PostgreSql versão 8.4, onde cada palavra foi inserida em uma
tupla. Após a importação o banco de dados tinha 1,5 milhões de tuplas e
consequentemente 1,5 milhões de possíveis palavras. Sobre essas palavras foi aplicado
o 1º Filtro que excluía as palavras com menos de quatro caracteres, pois a maioria
dessas palavras representam artigos, pronomes e preposições. Após foi realizado o
processo 2º Filtro, que excluiu as palavras que continham caracteres inválidos (-, @, <,
>, ‟, ª, º, ñ, „, ´, û), números e as em que todos os caracteres eram letras maiúsculas.
Após a aplicação desses filtros foi realizado o processo RemoveAcentuação, que
substituiu caracteres com acentuação (á, é, í, ó, ú, à, è, ì, ò, ù, ã, õ, â, ê, î, ô, ä, ë, ï, ö, ü,
ç) por caracteres correspondentes sem acentuação (a, e, i, o, u, a, e, i, o, u, a, o, a, e, i, o,
a, e, i, o, u, c) e em seguida o 3º Filtro que fez a remoção de pontuação e caracteres
auxiliares (. , ,, ..., “, ”, *, !, ?, ;, (, ), :).
A aplicação de todo esse processo inviabiliza a geração de pseudopalavras com
menos de quatro caracteres, acentuação ou hifens, porém, dá mais confiabilidade de que
a base representa relações de letras de palavras existentes e não nomes, complementos
gramaticais ou palavras de organização e estrutura dos livros. Após este processo
restaram 500 mil palavras, das quais 38 mil são distintas.
47
3.3
REDE DE BAYES
3.3.1 WEKA
O
Weka
(Waikato
Environment
for
Knowledge
Analysis;
http://www.cs.waikato.ac.nz/ml/weka) é um projeto desenvolvido e mantido pela
universidade de Waikato, localizada na Nova Zelândia, e licenciado pela GPL (General
Public License). Este projeto visa reunir implementações de algoritmos de diversas
técnicas de mineração de dados e na área da inteligência artificial dedicada ao
aprendizado de máquina. Disponibilizado por meio de uma API em Java ou uma
aplicação para testes e experimentos, ele possui ferramentas que possibilitam o préprocessamento, classificação, regressão, clustering e associação de dados.
No nosso projeto, utilizamos a aplicação para auxílio na seleção de atributos e a
API para a implementação do gerador de pseudopalavras. Em ambos os casos foi
utilizado um classificador do tipo BayesNet, que representa a Rede de Bayes. Os dados
a serem classificados são passados ao classificador por meio de uma Instances. A
Instances é um grupo de Instance. Uma Instance é a representação lógica de uma
informação, esta representação é obtida através de valores que devem ser informados
que representam esta informação, esses valores são chamados de atributos.
Os dados de entrada são passados a Instance por um arquivo de texto no formato
ARFF. Este é um formato de arquivo próprio da Weka, onde o símbolo % representa
comentários, e a primeira linha sem comentários deve ser @relation que representa o
nome da relação de atributos, posteriormente devem ser definidos os atributos com o
comando @attribute e por fim deve ser inserido em cada linha valores para todos os
atributos, em ordem de definição e separados por vírgula (WITTEN; EIBE; HALL,
2011).
3.3.2 DEFINIÇÃO DE ATRIBUTOS
Os atributos são os representadores do padrão que devemos extrair de algum
dado, no nosso caso, os atributos devem representar a relação entre as letras em uma
palavra.
Para a identificação dos melhores atributos fizemos um brainstorm e
posteriormente utilizamos a Weka para testes. No brainstorm identificamos que não
seria possível a utilização de sílabas para representação da relação entre as letras, uma
vez que sílabas são geradas foneticamente e nosso trabalho não contempla sons. Outra
restrição importante identificada é que não poderíamos definir como atributo uma letra
48
ser consoante ou vogal, pois, esta classificação não é relevante para a maioria das
línguas e nosso trabalho perderia seu sentido genérico.
Após o brainstorm, o primeiro teste foi realizado com cada letra do alfabeto
sendo um atributo, neste teste inseríamos o valor 1 no atributo relacionado a letra atual,
1 no atributo selecionado para a próxima letra e 0 nos demais atributos. O problema
encontrado foi que não tínhamos um atributo que representava a classificação.
O segundo teste foi realizado com base no primeiro, porém adicionando a
classificação. Foi marcado como 1 o atributo relacionado a letra atual, a próxima letra
no atributo de classificação e 0 para os demais atributos. Neste teste os resultados da
Weka foram insignificantes e percebemos que esses atributos ainda não representavam a
relação entre as letras, sendo necessário incluir como atributo a vizinhança da letra.
Para o terceiro teste utilizamos então a letra atual no atributo de classificação, e
marcamos como 1 os atributos das letras que representavam a letra anterior e a próxima.
O teste realizado na Weka mais uma vez não teve o êxito de classificação esperado, e
após uma longa discussão com nosso orientador identificamos esses atributos não
expressavam a posição das letras nas palavras e que a inclusão dos demais atributos com
o valor 0 influenciava no cálculo das probabilidades da rede, gerando um resultado
insatisfatório.
Com as considerações do terceiro teste, no quarto teste não utilizamos cada letra
como atributo com valores booleanos (0 e 1), utilizamos então um atributo que
representa a letra anterior e um atributo que representa a letra posterior, em ambos os
atributos os valores utilizados eram os próprios caracteres. Criamos um atributo
numérico e seu valor era a posição da letra na palavra e mantivemos o atributo de
classificação com seu valor sendo o caractere da letra a ser classificada. Este teste teve
um resultado relevante na Weka e utiliza todas as características que expressa a relação
entre as letras de uma palavra, sendo elas:

Sua vizinhança;

A posição da letra em uma palavra, considerando ela ser a primeira ou a
última letra;

A própria letra.
Após estes testes definimos que os atributos necessários para expressar a relação
entre as letras são:
49

Um atributo nominal que representa a letra anterior, sendo „?‟ caso a letra
a ser classificada for a primeira letra da palavra;

Um atributo numérico que representa a posição da letra a ser classificada
em relação à palavra;

Um atributo nominal que representa a próxima letra, sendo „?‟ caso a
letra a ser classificada for a primeira letra da palavra;

Um atributo nominal de classificação que representa a letra atual.
Onde, um atributo numérico é um número maior que zero, e um atributo nominal
é uma letra do alfabeto (a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,x,w,y,z).
Neste trabalho percebemos que a definição dos atributos para extrair o padrão
nos dados é a tarefa mais importante na utilização de algoritmos de classificação em
inteligência artificial.
3.3.3 PROJETO
Para a implementação da estrutura de aprendizagem de Rede de Bayes utilizamos
a linguagem Java e a plataforma de desenvolvimento NetBeans com a API da Weka.
Conforme a estrutura apresentada no diagrama Figura 5, o projeto inicia por um gerador
de arquivo texto que lê as palavras cadastradas no banco de dados, separa os atributos e
gera um arquivo na estrutura de um arquivo ARFF da Weka.
Figura 5 - Representação gráfica do processo de geração de pseudopalavras através da rede de
bayes.
Após a geração deste arquivo ARFF, o mesmo é lido e instanciado como uma
variável do tipo „weka.Instances‟, esta variável representa em memória o conjunto de
50
palavras lidas e os atributos que definem cada relação de letras. É instanciado também
uma variável weka.classifiers do tipo BayesNet que faz os cálculos de probabilidades da
rede de bayes para nossa aplicação. Para construir a rede de treinamento é chamado o
método buildClassifier da variável BayesNet passando como parâmetro a Instance.) e as
Instances que representa a relação entre as letras, para realizar o treinamento da rede.
Com a rede treinada é possível realizar a classificação de atributos e analisar seu
resultado. A combinação de várias classificações é que geram uma pseudopalavra. A
classificação é realizada pelo método classifyInstance da variável classifier passando
como parâmetro a weka.Instance a ser classificada, o valor retornado desse método é
um double que representa a posição do atributo no array de atributos da variável
weka.Instance classificada.
3.4 ALGORITMO DE MÉDIA PONDERADA
Para comparar os resultados obtidos pela rede bayesiana criamos um algoritmo de
média pondera para geração de pseudopalavras. Pois se existe um algoritmo mais
simples que resolve o mesmo problema com menor taxa de erro, é mais conveniente que
um algoritmo complexo que faça a mesma coisa.
3.4.1 DEFINIÇÃO DE ATRIBUTOS
Os atributos definidos para este calculo, são os mesmo definidos para a rede de
bayes, tanto que nosso objetivo é comparar o resultado dos dois algoritmos. Para
representação desses atributos, foi criada uma classe chamada de relação para organizar
essas informações dentro do programa. Neste algoritmo foi utilizado o calculo de
médias ponderadas para alimentar esses valores.
3.4.2 CALCULO DE MÉDIAS PONDERADA
O calculo de média ponderada foi elaborado de tal forma para permitir que a
frequência que os eventos ocorrem, pondere a distribuição de probabilidades entre as
variáveis aleatórias do espaço amostral.
3.4.3 ESTRUTURA
O algoritmo de média ponderada foi construído utilizando como base uma
estrutura de dados arvore para armazenar as probabilidades como demonstrado na
Figura 6. Cada nó possui uma distribuição de probabilidade entre seus nós filhos dado
pelo calculo de média ponderada, cuja somatória é igual a 1. Com relação ao algoritmo
51
anterior e o seus parâmetros, a forma com que se encontram os atributos nessa estrutura
são: Nó pai representa a letra anterior (o nó raiz não possui nó pai, por isso o
consideramos nulo), nós filhos representam os próximos nós (os “nós folhas” não
possuem próximo nó, por isso os consideramos nulos), o nó em si, representa a letra e a
relação entre os nós, representa a probabilidade. A raiz inicial representa o ponto de
partida da execução do algoritmo que não representa uma letra.
Figura 6 - Exemplo da estrutura de dados arvore utilizada pelo algoritmo de média ponderada
3.4.4 PROJETO
O projeto foi dividido em três partes. Cálculo de média ponderada: busca uma
lista de palavras em um banco de dados, a cada palavra lida, letra a letra é analisada
criando os níveis da árvore e relações probabilísticas entre nós no filhos. A extração de
atributos que retira as informações da árvore e insere em um banco de dados. E a
criação das pseudopalavras que são geradas a partir das relações mais fortes existentes
entre os filhos dos nós na arvore.
52
Figura 7 - Representação gráfica do processo de geração de pseudopalavras através do algoritmo
de média ponderada.
3.4.4.1 CÁLCULO DE MÉDIA PONDERADA
Este algoritmo faz uma vasta leitura na base de palavras criando uma lista, para
cada palavra lida, que é dividida em suas respectivas letras, na qual cada letra será
representada por meio de um nó em uma árvore a ordenação pelos níveis e as
probabilidades correspondem à probabilidade da letra lida em relação à próxima letra
(filho do nó).
Quando uma letra é inserida na arvore pela primeira vez ela se torna o primeiro
nó filho da raiz (como já havia descrito a raiz não representa uma letra e sim um ponto
genérico para criação a relação de primeira letra e o início da palavra). A probabilidade
deste nó é 1 , pois é a única variável da nossa distribuição de probabilidade para este nó.
Na inserção de uma segunda letra no mesmo nível da arvore que foi inserida a anterior,
cria-se um novo nó na arvore e dividindo a probabilidade de um único nó em 2, sendo
assim cada uma das relações ficou com probabilidade igual a ½.
Na inserção da terceira letra também no mesmo nível, é efetuado um cálculo
para distribuir de maneira ponderada as probabilidades entre os nós da arvore:
53
Equação 5 - Cálculos iniciais de média ponderada
vt = valor atual da probabilidade do nó.
pnn = probabilidade de um novo nó ser inserido na distribuição de probabilidade que é dado por:
q = quantidade de vezes que uma letra foi inserida para um determinado nó.
Neste caso, este calcula para todos os filhos do nó em questão. E o novo nó
recebe a probabilidade através deste calculo:
Equação 6 - Cálculo da probabilidade do novo nó
Quando uma nova letra for inserida na arvore já existir, a distribuição de
probabilidade recalcula as probabilidades da distribuição com o cálculo de média
ponderada descrita acima e reforma a relação já existente. Mas para calcular a
probabilidade de um novo nó é efetuado o seguinte calculo:
Equação 7 - Recalculo do valor do nó
3.4.4.2 EXTRAÇÃO DE ATRIBUTOS
Para extração de atributos foi desenvolvido um algoritmo que percorre toda a
árvore e para cada nó acessado instanciou-se um objeto da classe “relação letra” que é
composta dos seguintes atributos: letra anterior, letra, posição, letra posterior,
probabilidade correspondente à próxima letra. Assim para cada instância foi criado uma
tupla no banco de dados cuja tabela possuía os mesmos atributos da classe.
54
3.4.4.3 GERADOR DE PSEUDOPALAVRAS
O gerador de pseudopalavras foi desenvolvido para utilizar o padrão extraído do
calculo de média ponderada, que representa entre as probabilidades, as fortes relações
que possuem entre as letras das palavras lidas. Essas palavras utilizadas para o calculo
de probabilidades representam um padrão linguístico, ou seja, a variabilidade existente
entre as palavras, tipo, tamanho e sua complexidade. Devido a esse fato as formações
das pseudopalavras vão seguir esse padrão de forma reduzida nas relações menores
(“silábicas”).
Dado o padrão apreendido, as pseudopalavras serão geradas através de 2
parâmetros: A primeira letra e o tamanho da palavra. Porém esses parâmetros devem
estar de acordo com a estrutura da árvore, e no caso a quantidade de letras para a
pseudopalavra deve estar de acordo com a altura da mesma e a primeira letra deve estar
entre as primeiras letras das palavras inseridas na arvore.
Para gerar as pseudopalavras o algoritmo desenvolvido busca as tuplas no banco
de dados correspondente a classificação da letra. No caso da primeira letra informada
pelo parâmetro, o algoritmo a busca no banco de dados e depois todas as relações
existem entre as possíveis próximas letras de acordo com as relações que existiam na
arvore. Essas relações inseridas em uma lista na qual é ordenada de acordo com as suas
probabilidades. Na primeira metade da lista estão as relações mais fortes entre as
próximas letras. Sendo assim é escolhida a próxima letra de maneira aleatória e
concatenada a letra anterior, que no caso é a primeira letra. Depois é refeito a busca
novamente, até que a próxima letra esteja no ultimo nível da arvore, ou seja, no banco
de dados é o atributo próximo possui valor nulo. No final desse processo geramos uma
pseudopalavra.
3.4.5 CONSIDERAÇÕES FINAIS
Neste capítulo criada uma base de palavras confiáveis com base em livros
clássicos da literatura portuguesa e defido os atributos necessários para expressar a
relação entre as letras de uma palavra. Desenvolvemos dois programas diferentes para a
geração de pseudopalavras, o primeiro utilizando a Rede de Bayes da Weka e o segundo
utilizando um algoritmo de média ponderada.
No próximo capítulo serão apresentados e discutidos os testes para a geração de
pseudopalavras nos dois programas, ambos utilizando a mesma base de palavra e os
mesmos atributos.
55
56
CAPÍTULO 4 RESULTADO, TESTES E DISCUSSÃO.
4.1
A partir dos programas gerados no capítulo anterior, realizamos vários testes de
geração de pseudopalavras e os mais relevantes serão apresentados neste capítulo. Para
possibilitar a comparação do resultado dos programas, será utilizada a mesma base de
palavras e os atributos definidos no capítulo do anterior.
4.2
REDE DE BAYES
4.2.1 TESTES DE TREINAMENTO DA REDE DE BAYES COM A BASE DE
PALAVRAS COMPLETA
A primeira parte do programa gerador de pseudopalavras através da Rede de
Bayes é o treinamento da rede que foi executada com a API da Weka. Após o
treinamento, a Weka disponibiliza a probabilidade de acerto de uma classificação. Esta
taxa representa a inter-relação dos atributos com a classificação e com este dado
podemos estimar quantas palavras são necessárias para melhor gerar pseudopalavras.
Para realizar este teste foram construídos sete arquivos do tipo ARFF com os
atributos definidos, onde o primeiro usava 1.000 palavras, o segundo 10.000 palavras, o
terceiro 25.000 palavras, o quarto 50.000 palavras, o quinto 100.000 palavras, o sexto
250.000 palavras e o sétimo 500000 palavras. Todas retiradas do banco de palavras.
Tabela 1 – Representação da probabilidade de acerto após o treinamento da Rede de Bayes
Quantidade de Palavras representadas
Taxa de Acerto (%)
Numero de Instâncias
1.000
34,90
6.349
10.000
34,16
62.898
25.000
33,94
158.428
50.000
33,97
319.317
100.000
32,02
634.860
250.000
32,71
1.581.088
500.000
32,34
31.666.025
pelo ARFF
57
Na Tabela 1 podemos ver a relação entre a quantidade de palavras lidas, a taxa
de acerto e o número de instâncias geradas. Podemos observar que a probabilidade de
acerto diminui muito lentamente conforme aumentamos o número de palavras, e
podemos dizer que é praticamente estável, uma vez que a maior variação foi de -2,88%
entre 1.000 e 100.000 palavras.
A baixa taxa de acerto, em média 33,43%, representa que a Rede de Bayes não
conseguiu achar um padrão estatístico de relação entre as letras, utilizando os atributos
informados. Levando em consideração os testes realizados para seleção dos atributos,
definimos que estes são os que melhor representam a relação entre as letras e que a
baixa taxa de acerto representa que não foi utilizado um padrão estatístico na construção
das palavras.
Vale ressaltar que para o processamento de 250.000 e 500.000 palavras foi
necessário aumentar a memória do Java para 1,2Gb e 2,0Gb de memória RAM
respectivamente, ocupando em média 60% do consumo de CPU.
4.2.2 TESTES DE TREINAMENTO DA REDE DE BAYES APENAS COM
PALAVRAS DISTINTAS
Neste teste será definido se a alta quantidade de palavras repetidas,
aproximadamente 93% da base de palavras, influenciou ou não no resultado do teste
anterior.
Para realizar este teste foram construídos quatro arquivos do tipo ARFF com os
atributos definidos anteriormente, onde o primeiro usava 1.000 palavras, o segundo
10.000 palavras, o terceiro 20.000 palavras e o quarto 35.000 palavras. Todas retiradas
do banco de palavras, porém sem repetição das mesmas.
Tabela 2 - Representação da probabilidade de acerto após o treinamento da Rede de Bayes com
palavras distintas
Quantidade
de
Palavras
distintas
Taxa de Acerto (%)
Numero de Instâncias
1.000
31,93
8.257
10.000
32,60
82.096
20.000
32,51
163.999
35.000
32,37
286.947
representadas pelo ARFF
58
Na Tabela 2 podemos ver que a taxa de acerto permanece relativamente estável
em uma amplitude de 1.000 a 35.000 palavras, tendo variação máxima de 0.67%. Com
esses valores estáveis e semelhantes ao teste anterior, onde foram utilizadas palavras
repetidas, demonstra que estas não afetam negativamente o desempenho da Rede de
Bayes na classificação dos atributos e na geração de pseudopalavras.
4.2.3 RESULTADO DA GERAÇÃO DE PSEUDOPALAVRAS
Uma vez que a taxa de acerto da Rede de Bayes se manteve estável usando
palavras repetidas ou distintas e em pouca ou muita quantidade, foram escolhidas para a
geração de pseudopalavras o arquivo ARFF, do primeiro teste, contendo 50.000
palavras, por representar uma taxa média de acerto da base.
A partir deste arquivo ARFF a Rede de Bayes do programa foi novamente
treinada e solicitada a ela que gerasse uma pseudopalavra começando com o caracter „a‟
e com 6 letras. O programa gera uma linha com atributos para a classificação como
„a,2,?,?‟ onde o primeiro atributo representa a letra anterior, o segundo atributo
representa a posição do caractere a ser buscado na palavra, o terceiro atributo representa
o próximo caractere e o quarto é a letra que estamos procurando, sendo o caractere „?‟
um coringa para a Rede de Bayes, informando que não sabemos o valor deste atributo.
O programa gerou então a letra „r‟ que seria segunda letra da futura pseudopalavra, de
acordo com o cálculo de probabilidades da Rede de Bayes onde se conhecia o caractere
anterior e a posição na palavra. O programa repete este processo para as próximas
posições da futura pseudopalavra alterando os atributos conforme necessário e após
gerar os 6 caracteres a pseudopalavra gerada foi: araras.
A pseudopalavra gerada, araras, na verdade é uma palavra existente, para
identificar se foi apenas coincidência utilizamos o programa para gerar vinte e seis
pseudopalavras, cada uma começando com uma letra diferente do alfabeto, contendo
seis caracteres. O resultado foi a seguinte lista:
59
Tabela 3 - Pseudopalavras geradas pela rede
Pseudopalavras geradas pela rede
Araras
Hasaso
Oraras
Vasaso
Braras
Issaso
Praras
Xcoras
Casaso
Juraso
Quraso
Wzaras
Dosaso
Kzaras
Rasaso
Yzaras
Essaso
Lvaras
Sssaso
Zasaso
Fraras
Masas
Traras
Graras
Ntoras
Uraras
Do total de possíveis pseudopalavras geradas, foram obtidas 17 pseudopalavras
válidas, 8 pseudopalavras inválidas e 1 palavra real (considerando a gramática
brasileira, da qual foram retirados os livros que formaram a base de palavras), o que
representa 65,38% de acerto.
Apesar do alto índice de acerto todas as pseudopalavras continham as
terminações „ras‟ e „aso‟. Essa convergência para repetição de terminação aconteceu
pois a partir do segundo caractere gerado, ou seja, do terceiro caractere da
pseudopalavra a Rede de Bayes fez a geração sem utilizar o atributo que representa o
próximo caractere, pois na geração da letra atual a rede não tinha ainda qual seria a
próxima letra. Para corrigir este efeito o programa foi alterado para que após a primeira
geração completa da futura pseudopalavra o mesmo passe novamente pela
pseudopalavra tentando classificar novamente seus atributos, pois nesta nova
classificação o programa já pode utilizar o atributo referente a próxima letra. O
resultado desta geração foi a seguinte lista:
Arares
Haseso
Orares
Viseso
Brares
Isseso
Prares
Xcres
Ciseso
Jureso
Qureso
Wzeses
Deseso
Kzeres
Reseso
Yzeses
Esseso
Lvares
Ssseso
Zeseso
Frares
Meseso
Trares
Grares
Nteses
Urares
60
Após esta possível correção, foram geradas 19 pseudopalavras válidas, e 7
pseudopalavras inválidas. Com este teste de correção a taxa de acerto subiu para
73,07% porém as terminações convergiram para somente outras três sequências de
caracteres („eso‟, „res‟ e „ses‟).
Uma terceira forma de gerar pseudopalavras foi testada, onde foi solicitado ao
programa que gerasse vinte e seis pseudopalavras com seis caracteres, com a letra „d‟ na
terceira posição, a letra „a‟ na última posição e cada primeira letra era uma letra do
alfabeto. O resultado foi a seguinte lista:
Andoua
Hadoua
Ondoua
Vadoua
Bedoua
Indoua
Padoua
Xadoua
Cadoua
Jadoua
Qudoua
Wndoua
Dedoua
Kndoua
Radoua
Yndoua
Endoua
Ladoua
Sadoua
Zadoua
Fidoua
Madoua
Tadoua
Gudoua
Nadoua
Undoua
Neste teste foram geradas 22 pseudopalavras válidas, e 4 palavras inválidas,
elevando a taxa de acerto para 84,62%. As pseudopalavras geradas convergiram para
uma terminação, porém isto já era esperado, uma vez que o teste determinava a
vizinhança.
4.2.4 DISCUSSÃO
Com estes resultados observamos que a parte gerada automaticamente pela rede
sempre converge para um padrão, mas é possível aumentar a taxa de acerto se
informamos mais valores para os atributos, pois estes estarão 100% corretos, uma vez
que são determinados pelo usuário. Estatisticamente, se queremos uma pseudopalavra
com seis caracteres, que comece pela letra „a‟ e temos 33,97% de acerto em cada letra
gerada pela rede temos:
(100%+33,97%+33,97%+33,97%+33,97%+33,97%) / 6 = 44,97% de acerto.
Mas, se queremos uma pseudopalavra que tenha seis caracteres e contenha o
caractere „a‟ na primeira posição, „c‟ na segunda posição, „e‟ na terceira posição e temos
a mesma taxa de acerto em cada letra gerada pela rede temos:
(100%+33,79%+100%+33,79%+100%) / 6 = 61,32% de acerto.
61
Apesar do alto índice de acerto foi identificado um problema em que, por ser um
classificador, se utilizarmos sempre a mesma base de palavras e os mesmos valores para
os atributos, a Rede de Bayes irá gerar sempre as mesmas palavras, pois ela tende a
selecionar o melhor padrão.
4.3 ALGORITMO DE MÉDIA PONDERADA
Para efetuarmos os testes deste algoritmo utilizamos todas as letras do alfabeto
efetuando quatro vezes a geração com o mesmo tamanho de pseudopalavra desejada. Os
tamanhos da pseudopalavra variou entre 4 e 7.
O resultado esperado para estes testes é de que as pseudopalavras sejam
satisfatoriamente pronunciáveis, ou seja, devem estar de acordo com o teste que será
aplicado pelo profissional da área.
4.3.1 RESULTADOS E TESTES
Nas tabelas encontram-se pseudopalavras em vermelho (incorretas) e preto
(corretas), mas também existem palavras em azul na qual não identificamos como um
erro e sim um elemento que não faz parte do conjunto desejado.
Tabela 6 - Teste para geração de pseudopalavras com 4 letras
Teste para geração de pseudopalavras com 4 letras
Primeiro
Segundo
Terceiro
Quarto
auqu
abud
afli
adga
bife
bime
bufi
biro
crum
crri
cren
cudo
dalp
dcia
dagr
danu
evur
evut
eviv
efle
frlo
frrd
frfa
funi
gace
gaim
glit
gita
hird
hitt
huro
husi
igrf
ilen
iton
ilha
62
jedr
jeve
jebr
jauf
kliv
kagi
klti
kltu
lulu
lusg
lhin
lhoq
mupa
mudi
mizi
mimu
nuss
nubl
nigu
nube
oflc
osci
opte
opsn
pizo
pita
puli
pupi
qulg
qufo
qule
qupu
ruol
ruad
ruxb
ruva
siga
saua
scld
sixo
tivi
tuag
tuoa
taio
utit
utoc
uscl
usca
vaba
vuje
vace
vuci
woad
wico
wolu
wimn
xibs
xuri
xiai
xixi
yocb
yoes
yovr
yole
zube
zuti
zubj
zulc
Neste teste observamos que quantidade de pseudopalavras aceitas é de 50,96%.
Existem vários fatores que responsáveis por esse resultado. Um deles é o fato de que a
combinação entre as letras é feita de maneira quase aleatória, a quantidade de letra pode
“cortar” algumas possíveis palavras e o treinamento com palavras com tamanho menor
que 4 foi filtrado na criação da base de dados.
Primeiro
Segundo
Terceiro
Quarto
atosu
avano
azipo
azoqu
bavog
batil
bixeg
busqu
63
cupto
cunuz
citen
clinu
dasme
dalvo
dualu
dages
etomi
efond
etans
etime
flmbo
fuzbi
fropr
flpot
gaive
gltav
gioca
gavec
huciu
humiu
hipra
huled
igasa
ibist
ilias
igiou
jabos
jedue
jerit
japur
kadea
katos
kabot
klegi
lhuro
lunga
lavon
lurma
mirol
mujav
mipus
muvod
nuzil
nitad
nuzbr
nuere
odequ
opaco
oitao
opuei
pigor
pluld
puquv
pumoe
qutan
qusga
qupas
quemo
raisu
rurui
rabla
runte
scago
sanab
sitad
scler
tacin
tizei
tatur
tusat
usamo
usnag
utoif
utmec
valba
vauro
vasal
vulge
wirpa
wosqu
wilat
wozui
xuero
xumbu
xumus
xioua
yoaog
yogit
yoera
yotic
zubot
ziqub
zuleq
ziboc
O teste com cinco letras com 57,69%, mostrou características muito semelhantes
em relação ao erro de “corte” das pseudopalavras geradas com quatro letras como por
exemplo: ziboc, sitad, kabot, odequ, azoqu e etc. Porém mostrou uma quantidade de
acertos mais significativos.
64
Primeiro
Segundo
Terceiro
Quarto
adeuco
adeleu
aqupia
adanos
buzote
bicnan
buenas
bastra
clutar
cilham
ciquas
clubar
dcavad
dcucos
dafimo
dalvai
eleran
euesad
elfeca
evirit
fuprar
fufota
frmada
flvess
gabelh
giosoa
gadoso
glauel
hioteo
huspei
hiamet
hipons
itonav
igapar
ialolo
iavilt
jelalh
jemist
jaurou
jeuzar
klfina
kaveni
kapius
kagolo
lancas
lavast
luedon
laseso
minavi
mimouc
mupost
muavas
nifrai
nuxbia
ninait
niosav
ofugac
oscele
odutem
oflsos
pircos
plpose
pltale
pliter
quoupi
qublid
qudist
qubras
rangur
rusuco
rapado
runino
scopes
sanzor
sirque
sabave
tanege
tuplim
tupamo
tifest
ussaca
utubav
umetur
usfeni
vugome
vabame
valziz
vuduic
wonfou
wotada
wozate
wovera
xufeda
xubuno
xuzand
xibera
65
yonuxo
yoebur
yovevi
yoesos
zuaoze
zimead
zismut
zixait
Este teste mostrou uma maior quantidade de pseudopalavras aceitáveis igual á
65,38%. Porém continua com os mesmos problemas dos testes anteriores, inclusive com
a geração de sequências de consoantes que ocorreu devido à aleatoriedade.
Primeiro
Segundo
Terceiro
Quarto
azituli
aqustis
ateociu
azaranc
bijernd
bubiava
badidos
balocas
crlgado
cimnhon
cuzasic
clecolo
dcacaro
dufaime
daqueir
dabamba
elirila
etesici
eumbato
elmados
fuoseac
frotasa
fucassi
frgorad
gandare
giquiar
gilienh
gahubiu
hucanda
hutrcam
hunsare
higuiza
iliubra
ianenou
ilmeins
ibivaso
jeovisi
jebmour
jealada
jezonto
kavisad
kludisi
karblog
klamequ
lhisoce
lacasad
latanac
lhoidas
miocoui
mueojou
mutouni
muavuda
nusndol
nivembo
nusconi
niratan
ofrgala
oigages
oibailt
oimevou
puqulul
pizerer
pissame
plomiad
qutenid
quredou
quleame
qusibeu
raninga
raprava
raveira
raiandi
simoase
sacilia
scldave
scisoui
tielida
taguran
talasst
tulscid
66
umirria
utofima
usemeta
usnavar
vugesad
vamadou
vuefaso
vuxadin
wimbess
wicoxed
wonquco
wiminos
xuzimot
xuprati
xunzeri
xiquice
yoepara
yoldaiu
yosplav
yoarvou
ziodota
zidudia
ziquava
zinaver
Com 62,05% de acerto demonstram resultados semelhantes aos testes anteriores,
demonstrando que a taxa de acerto não aumenta quando a palavra fica maior.
4.3.2 DISCUSSÃO
Com este último teste, percebemos que um dos principais problemas, ocorridos
em todos os testes, é o ponto de parada na formação da pseudopalavras, criando
palavras com terminações de consoantes como: wimbess, kavisad, latanac e etc. Outro
fator importante, que já havia citado antes, é que uma pseudopalavra que comesse com a
letra “A” e possua 20 letras só é possível se a base de dados possuir pelo menos uma
palavra que comesse com “A” e possua 20 letras, tanto que este algoritmo é baseado nos
dados que foram lidos, por isso, neste ultimo teste que deveria ter apenas palavras com
7 letras, apresentou algumas palavras com menos, pois o caminho na árvore, pelo qual o
algoritmo percorreu, termina antes da quantidade de letras terminar.
4.4 CONSIDERAÇÕES FINAIS
Neste capitulo fizemos os testes com a rede de bayes e o algoritmo de média
ponderada apurando os resultados. Na análise de resultados dos dois algoritmos
observamos os erros e acertos. Todas pseudopalavras geradas no teste foram exibidas,
tanto as corretas como as incorretas, com a sua justificativa.
No próximo capitulo concluiremos nosso trabalho com a comparação dos dois
algoritmos e seus resultados.
67
CAPÍTULO 5 CONCLUSÃO E TRABALHOS FUTUROS.
Conforme discutido no capitulo anterior, a rede de bayes apresentou uma alta taxa
de acerto, porém devido a seu mecanismo de identificação de padrão, as palavras
tendem a convergir para terminações semelhantes. Também foi encontrada uma
limitação na rede de bayes, em que devido a esse mesmo mecanismo, se caso seja usado
uma base palavras estática a quantidade de pseudopalavras diferentes, que ela irá gerar,
será limitada a variação da letra inicial.
O algoritmo de média ponderada mostrou uma variabilidade de formação de
palavras maior, porém 2 problemas resultaram em uma baixa taxa de acerto: o ponto de
parada na construção de uma pseudopalavra, na qual muitas ficaram com terminações
de consoantes que não existiam nas palavras da base. Outro problema foi que as
ramificações criadas na árvore limitam a geração de algumas pseudopalavras,
dependendo do percurso feito pelo algoritmo na estrutura de dados.
Concluímos que a melhor opção entre as soluções para geração de pseudopalavras é
a rede de bayes devido a sua maior taxa de acerto comparada ao algoritmo de média
ponderada. E indicamos, para trabalhos futuros, a correção da sua baixa taxa de
diversidade na geração de peseudopalavras através de uma base de palavras alimentada
continuamente pela auto extração de palavras da web. Acreditamos que a web seja a
melhor fonte de palavras, pois a quantidade de textos digitais disponíveis crescem de
forma rápida devido ao grande número de usuários e suas interações com redes sociais,
sites informativos e chats.
68
CAPÍTULO 6 REFERÊNCIAS
BARRERA, Sylvia Domingos; MALUF, Maria Regina. Consciência metalingüística e
alfabetização: um estudo com crianças da primeira série do ensino fundamental. Psicol.
Reflex. Crit., Porto Alegre, v. 16, n. 3, 2003 .
CUNHA,
Vera
Lúcia
Orlandi;
CAPELLINI,
Simone
Aparecida.
Análise
psicolinguística e cognitivo-linguística das provas de habilidades metalinguísticas e
leitura realizadas em escolares de 2ª a 5ª série. Rev. CEFAC, São Paulo, v. 12, n. 5,
2010.
FRANÇA, Marcio Pezzini. Estudo do reconhecimento de palavras e pseudopalavras em
estudantes da 2ª e 3ª séries do ensino fundamental: tempo de reação e lapsos na leitura
em voz alta. 2007.
GARCIA, Ricardo Basso. Conhecimento sintatico-semantico e processamento de
sentenças em rede neural recorrente simples. 2006.
GINDRI, Gigiane; KESKE-SOARES, Márcia; MOTA, Helena Bolli. Memória de
trabalho, consciência fonológica e hipótese de escrita. Pró-Fono R. Atual. Cient.,
Barueri, v. 19, n. 3, 2007.
HAYKIN, Simon - Redes neurais : princípios e prática / Simon Haykin; trad. Paulo
Martins Engel. - 2. ed. – Porto Alegre : Bookman, 2001.
MELO, Laila Beatriz Soares. Reconhecimento de padrões textuais para categorização
automática de documentos. 2007.
SILVA, José Mauro da. SINAPSE: Uma Metodologia para Extração de Conhecimentos
em Objetos Textuais Baseada em Conceito para o Português do Brasil. 2007. 140f.
Dissertação (Mestrado em Ciência da Computação) – Programa de Pós-Graduação do
Instituto de Informática, Universidade Federal de Goiás, Goiânia, 2007.
SALLES, Jerusa Fumagalli de; PARENTE, Maria Alice de Mattos Pimenta. Funções
neuropsicológicas em crianças com dificuldades de leitura e escrita. Psic.: Teor. e Pesq.,
Brasília, v. 22, n. 2, Aug. 2006 .
STUART, Russel; PETER, Norving - Inteligência Artificial. Tradução: Publicare
Consultoria 2 ed. Rio de Janeiro – RJ: Elsevier, 2004.
PAL, Sankar k; PAL, Amita. Pattern Recognition: From Classical to Modern
Approaches. World Scientifica Publishing Co. Pre. Ltd. 2001
TEODORIDIS, Sergios - Pattern Recognition. Academic Press, USA, 1 ed, 1999
69
STEINER,
Maria
Teresinha
Arns.
UMA
METODOLOGIA
PARA
O
RECONHECIMENTO DE PADRÕES MULTIVARIADOS COM RESPOSTA
DICOTÔMICA. Dezembro 1997.
HEDE, Ma. PATTERN RECOGNITION USING NEURAL NETWORKS. Setembro
1994.
FU, King Sun. Syntactic Pattern Recognition, Applications. USA, 1977.
JAIN, Anil k.; DUIN, Robert P.W; MAO, Jianchang. Statistical Pattern Recognition: A
Review. Janeiro 2000. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND
MACHINE INTELLIGENCE, VOL. 22, NO. 1
FUKUNAGUA, Keinosuke. Introduction to Statistical Pattern Recognition. Academic
Press, INC USA. 2 Ed. 1990.
FERREIRA, Carlos A.; SOARES, José F.; CRUZ, Frederico R.B. Reconhecimento de
Padrões em Estatística: Uma Abordagem Comparativa. Abril de 2001
RESENTE, Solange Oliveira. Sistemas inteligentes: Fundamentos e aplicações. 2005
SANDRI, Sandra; CORREA, Cláudio. Lógica Nebulosa. Julho de 1999. ITA, São José
dos Campos - SP; V Escola de Redes neurais, Promoção: Conselho Nacional de Redes
neurais pp. c073-c090
ALENCAR FILHO, Edgard de, 1913 - Iniciação à lógica matemática – São Paulo - SP:
Nobel 2002.
DEVORE, Jay L. - Probabilidade e estatística : Para engenharia e ciências. Tradução :
Joaquim Pinheiro Nunes da Silva. São Paulo – SP : Pioneira Thomson Learning, 2006.
KJAERULFF, Uffe B. ; MADSEN, Anders L. - Bayesian Networks and Inﬂuence
Diagrams - A Guide to Construction and Analysis. 2008 Springer Science Business
Media, LLC, New York, NY (USA).
PEARL, J. - Reasoning in Intelligent Systems. Ed.Morgan Kaufman, 1986.
CASTILHO E. , GUTIERREZ J. - Expert Systems and Probabilistic Network Models.
Ed. Springer, 1997.
DECHTER R.. Bucket elimination: A unifying framework for probabilistic inference.
In M. I. Jordan, editor, Learning in Graphical Models, p.75–104. MIT Press, 1999.
CASELLA G., GEROGE E. I.. Explaining the Gibbs sampler. Am. Stat. 46: p.167–174,
1992.
GEMAN S., GEMAN D.. Stochastic relaxation, Gibbs distribution and Bayesian
restoration of images. IEE Transactions on Pattern Analysis and Machine Intelligence 6:
p.721–741, 1984.
70
JENSEN F.V.. Bayesian Networks and Decision Graphs. Ed. Springer, 2001.
SILVA, W. T. da., LADEIRA, M. Mineração de dados em redes Bayesianas. In:
CONGRESSO DA SOCIEDADE BRASILEIRA DE COMPUTAÇÃO, 22., 2002,
Florianópolis. Anais. Florianópolis: UFSC, 2002.
COOPER G. F., HERSKOVITS E.. A Bayesian method for the induction of
probabilistic networks from data. Machine Learning, v9, p. 309-347, 1992.
VALENTIM, FELIPE LEAL. Estudo e implementação de algoritmos de inferência e
aprendizado em redes bayesianas, Lavras 2007.
LUNA, José Eduardo Ochoa. Algoritmos EM para Aprendizagem de Redes Bayesianas
a partir de Dados Incompletos.
TAN, Ah-Hwee. (1999). “Text mining: the state of the art and the challenges”. p. 65-70,
Beijing, April 1999.
LEAL, Miguel das Neves. Text Mining. 2003.
SCHEIDT, Rafael de Faria. Aplicação de Bibliometria em Trabalhos Científicos
Utilizando Mineração de Textos, 2007.
LOPES, Maria Célia Santos. Mineração de dados textuais utilizando técnicas de
Clustering para o idioma português. 2004.
ARANHA, Christian; Passos, Emmanuel. A Tecnologia de Mineração de Textos. 2006.
FONSECA, raphaela baptista. Uma estratégia de apoio à seleção de algoritmos de
clusterização de dados. 2008.
CORDEIRO, João Paulo da Costa. Extração de Elementos Relevantes em
Textos/Paginas da Word Wide Web.
PAZZIM, Debora_Machado_Pazzim. Clusterização de Textos Utilizando o Algoritmo
de K-Means. 2007.
KOLOSSOSKI, George. SEGMENTAÇÃO DE IMAGENS E
ALGORITMO K-
MEANS.
WITTEN, Ian. H; EIBE, Frank; HALL, Mark A. – Data Mining: Practical Machine
Learning Tools and Techniques, 3rd ed. 2001.
71

1 faculdades coc trabalho de conclusão de curso

Transcrição

Documentos relacionados

Discursiva

Maior substring em comum

historia ii - mod 47

Em uma pizzaria, cada tulipa de chopp custa R$ 0,80 e uma pizza

inferência bayesiana

Campeonato Nacional de Pizzaiolos TROFEU FARINHA

Contadores, somadores e acumuladores

Exercício extra 1

lyrices z

O PEDAÇO QUE FALTA A letra da música: Faltando um Pedaço de