Upload
ana-livia-borja-bicalho
View
217
Download
2
Embed Size (px)
Citation preview
Geração de classificadores
Generalização de exemplos
Generalização de exemplos
Generalização de exemplos
Representação das famílias
• Precisamos de uma descrição para as famílias• Podemos representar o DNA e o RNA por
seqüências de a, c, g, t ou u• Em linguagens formais:
– Um conjunto de seqüências formam uma linguagem
– linguagens são descritas por gramáticas
Uma gramática
• Frase ::= sujeito predicado• sujeito ::= artigo nome• artigo ::= a | o • nome ::= cão | moça | dia• predicado ::= verbo adjetivo• verbo ::= está | estava• adjectivo ::= feliz | triste
Gramática
• Reconhecimento
• Geração
• Árvore sintática
Classes gramaticais (cont.)
• Regulares:– A a | a B
• Livres de Contexto:– A a B C f d
• Sensíveis ao Contexto:– a A D a B C f d
Gramática regular
• S ::= a S | u S | g S | c S | a | u | g | c
• Ex: uaggcuacgccagcau
Gramática livre de contexto
• S ::= a S u | u S a | c S g | g S c |
Gramática livre de contexto
• S ::= a S u | u S a | c S g | g S c | A• A ::= A a | A u | A c | g A | a | u | c | g
Gramática livre de contexto
• S ::= a S u | u S a | c S g | g S c | SS
SCFG e estrutura secundária(slide de Ariane Machado Lima)
Gramática sensível ao contexto
Gramática sensível ao contexto
• A ::= a z B | a m B• zB ::= zul• mB ::= marelo
Classes gramaticais
• Diferentes complexidades
• Regular já é interessante:– gramática de seqüência clonada– HMM
Gramáticas estocásticas
• S ::= Prom SeqCod [1]• Prom ::= TATA Seq [0.6]• ...• SeqCod ::= Cod SeqCod [0.998]• SeqCod ::= Stop [0.002]• Cod ::= Lys [0.03]• Cod ::= Asp [0.035]• ...
Resultados: Data searching
• NLL- score: – Negative Log Likelihood
-log (P(Seq | gramática))– Dependente do tamanho da seqüência de teste
• mais precisamente do número de produções utilizados
• em GRE numero de produções igual ao tamanho– Precisa de normalização
Z- score• Tenha uma amostra positiva e uma negativa• Para cada tamanho de seq negativa (número de produções),
calcule o NLL médio negativo• Pontos não cobertos -> interpolação• Para cada seq da amostra (+ e -), calcule seu Z-score:
(NLL(X) – NLLmed,neg,tam=x )Ztam=x (X)= ------------------------------------
DesvioPadrão(NLLneg,tam=x)
• Plote esses valores em um gráfico Z x nr seq• Encontre um limiar que separe as amostras + e -
– 3,8 é o mais utilizado
Gramáticas regulares vs. HMM
• gramáticas regulares e HMM tem poder semelhante de expressão
• dada uma HMM podemos desenhar uma gramática regular estocástica que gera a mesma distribuição de probabilidades
Inferência gramatical – gramáticas regulares
• gramáticas podem ter sua arquitetura inferida automaticamente a partir de um conjunto de sequências– árvore de prefixos– generalizações por junção de nós
• probabilidades podem ser inferidas conjuntamente ou em separado