22

Geração de classificadores Generalização de exemplos

Embed Size (px)

Citation preview

Page 1: Geração de classificadores Generalização de exemplos
Page 2: Geração de classificadores Generalização de exemplos

Geração de classificadores

Page 3: Geração de classificadores Generalização de exemplos

Generalização de exemplos

Page 4: Geração de classificadores Generalização de exemplos

Generalização de exemplos

Page 5: Geração de classificadores Generalização de exemplos

Generalização de exemplos

Page 6: Geração de classificadores 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

Page 7: Geração de classificadores Generalização de exemplos

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

Page 8: Geração de classificadores Generalização de exemplos

Gramática

• Reconhecimento

• Geração

• Árvore sintática

Page 9: Geração de classificadores Generalização de exemplos

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

Page 10: Geração de classificadores Generalização de exemplos

Gramática regular

• S ::= a S | u S | g S | c S | a | u | g | c

• Ex: uaggcuacgccagcau

Page 11: Geração de classificadores Generalização de exemplos

Gramática livre de contexto

• S ::= a S u | u S a | c S g | g S c |

Page 12: Geração de classificadores Generalização de exemplos

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

Page 13: Geração de classificadores Generalização de exemplos

Gramática livre de contexto

• S ::= a S u | u S a | c S g | g S c | SS

Page 14: Geração de classificadores Generalização de exemplos

SCFG e estrutura secundária(slide de Ariane Machado Lima)

Page 15: Geração de classificadores Generalização de exemplos

Gramática sensível ao contexto

Page 16: Geração de classificadores Generalização de exemplos

Gramática sensível ao contexto

• A ::= a z B | a m B• zB ::= zul• mB ::= marelo

Page 17: Geração de classificadores Generalização de exemplos

Classes gramaticais

• Diferentes complexidades

• Regular já é interessante:– gramática de seqüência clonada– HMM

Page 18: Geração de classificadores Generalização de exemplos

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]• ...

Page 19: Geração de classificadores Generalização de exemplos

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

Page 20: Geração de classificadores Generalização de exemplos

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

Page 21: Geração de classificadores Generalização de exemplos

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

Page 22: Geração de classificadores Generalização de exemplos

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