Tema 06 - Moodle USP: e-Disciplinas

SISTEMAS DEINFORMAÇÃO

11

11SISTEMAS DE

INFORMAÇÃO1

1SISTEMAS DEINFORMAÇÃO

11

1

Professora:Ariane Machado Lima

Tema 06

Métodos sintáticos


22

22SISTEMAS DE

INFORMAÇÃO2


22

2

Avisos

Próxima aula: PROVA

Atividade de validação cruzada para 10/10

Trabalho final: para 06/12– Trabalho escrito ou – APRESENTAÇÕES DIA 06/12


33

33SISTEMAS DE

INFORMAÇÃO3


33

3

Gramáticas


44

44SISTEMAS DE

INFORMAÇÃO4


44

4

Gramáticas

símbolos terminaissímbolos não-terminais

símbolo inicial

conjunto de produções


55

55SISTEMAS DE

INFORMAÇÃO5


55

5

Gramáticas

Definição: uma gramática G é uma quádrupla (V, Σ, S, P), onde

V é o conjunto de símbolos não-terminais (variáveis) Σ é o conjunto de símbolos terminais S é o símbolo inicial P é o conjunto de produções da forma

(Σ U V)* V (Σ U V)* → (Σ U V)*


66

66SISTEMAS DE

INFORMAÇÃO6


66

6

Gramáticas

Uma forma sentencial de uma gramática G é qualquer cadeia obtida pela aplicação recorrente das seguintes regras:

S (símbolo inicial de G) é uma forma sentencial Sejam αρβ uma forma sentencial de G e ρ → γ uma

produção de G. Então αγβ é também uma forma sentencial de G .

(α,β,γ Є (Σ U V)* e ρ Є (Σ U V)* V (Σ U V)*)


77

77SISTEMAS DE

INFORMAÇÃO7


77

7

Gramáticas

Uma forma sentencial de uma gramática G é qualquer cadeia obtida pela aplicação recorrente das seguintes regras:

S (símbolo inicial de G) é uma forma sentencial Sejam αρβ uma forma sentencial de G e ρ → γ uma

produção de G. Então αγβ é também uma forma sentencial de G .

(α,β,γ Є (Σ U V)* e ρ Є (Σ U V)* V (Σ U V)*)

Derivação direta: αρβ => αγβ


88

88SISTEMAS DE

INFORMAÇÃO8


88

8

Gramáticas

Derivação: aplicação de zero ou mais derivações diretas

α =>* μ isto é, α => β => … => μ

Uma cadeia w (w Є Σ*) é uma sentença de G se

S =>* w (S sendo o símbolo inicial) Linguagem gerada por G:

L(G) = { w Є Σ* | S =>* w }


99

99SISTEMAS DE

INFORMAÇÃO9


99

9

Gramáticas - Exemplos

G = (V, Σ, S, P), onde V = {S, A} Σ = {0,1,2,3} S = S P = {

S → 0S33

S → A

A → 12

A → ε

}


1010

1010SISTEMAS DE

INFORMAÇÃO10


1010

10



S → 0S33

S → A

A → 12

A → ε

}

Ex de formas sentenciais:

S, 0S33, 00S3333, 00A3333 0S33 => 00S3333 0S33 =>* 00A3333 0S33 =>* 0S33 Ex de sentenças:

00123333, 12, ε L(G) = {0m1n2n32m | m≥0 e n

=0 ou n=1}


1111

1111SISTEMAS DE

INFORMAÇÃO11


1111

11



S → 0S33

S → A

A → 12

A → ε

}



00123333, 12, ε L(G) = {0m1n2n32m | m≥0 e n

=0 ou n=1}


1212

1212SISTEMAS DE

INFORMAÇÃO12


1212

12



S → 0S33

S → A

A → 12

A → ε

}



00123333, 12, ε L(G) = {0m1n2n32m | m≥0 e n

=0 ou n=1}


1313

1313SISTEMAS DE

INFORMAÇÃO13


1313

13

Gramáticas - Simplificação


S → 0S33

S → A

A → 12

A → ε

}


S → 0S33 | A

A → 12 | ε

}


2121

2121SISTEMAS DE

INFORMAÇÃO21


2121

21

Gramáticas

Gramáticas são dispositivos generativos (geram cadeias)

Dada uma cadeia w, reconhecer se w Є L(G) é um processo chamado análise sintática

Dependendo do formato das produção, a análise sintática pode ser mais ou menos complexa


2222

2222SISTEMAS DE

INFORMAÇÃO22


2222

22

Hierarquia de Chomsky

Hierarquia das linguagens em classes de acordo com a sua complexidade relativa (Noam Chomsky, 1956)

Cada classe de linguagem pode ser gerada por um tipo de gramática (formato das produções)

Cada tipo de gramática tem uma complexidade de análise sintática diferente

Na prática: dada uma linguagem, saber qual o dispositivo mais eficiente para análise sintática


2323

2323SISTEMAS DE

INFORMAÇÃO23


2323

23


Linguagens regulares (tipo 3)

Linguagens livres de contexto (tipo 2)

Linguagens sensíveis ao contexto (tipo 1)

Linguagens irrestritas (tipo 0)

α →β

α Є V

β Є Σε, β Є V, β Є (VΣou

ΣV)

α Є V

β Є (VUΣ)*

α Є (VUΣ)*V(VUΣ)*β Є (VUΣ)*|α| <= | β |

α Є (VUΣ)*V(VUΣ)*β Є (VUΣ)*


24

Fonte: Adaptado de Searls (2002)

Fonte: Adaptado de Matsuno (2006)


2525

2525SISTEMAS DE

INFORMAÇÃO25


2525

25

Árvore sintática ou

Árvore de derivação

Árvore sintática ou árvore de derivação


2626

2626SISTEMAS DE

INFORMAÇÃO26


2626

26

Mais exemplos de árvores sintáticas


2727

2727SISTEMAS DE

INFORMAÇÃO27


2727

27



2828

2828SISTEMAS DE

INFORMAÇÃO28


2828

28


Duas árvores sintáticas distintas para a mesma cadeia!!!!


2929

2929SISTEMAS DE

INFORMAÇÃO29


2929

29

Ambiguidade


3030

3030SISTEMAS DE

INFORMAÇÃO30


3030

30

Ambiguidade

Algumas gramáticas ambíguas podem ser convertidas em não-ambíguas

Algumas linguagens são inerentemente ambíguas (só podem ser descritas por gramáticas ambíguas)

Eu vi o menino com uma luneta


3131

3131SISTEMAS DE

INFORMAÇÃO31


3131

31

Gramáticas Estocásticas

P(x, t | G) = produto das probabilidades das produções usadas na derivação t de x, para uma dada gramática G

P(x | G) = ∑i P(x, t

i | G)


3232

3232SISTEMAS DE

INFORMAÇÃO32


3232

32


P(x, t | G) = produto das probabilidades das produções usadas na derivação t de x, para uma dada gramática G

P(x | G) = ∑i P(x, t

i | G) Considera a ambiguidade da linguagem!


3333

3333SISTEMAS DE

INFORMAÇÃO33


3333

33


Definição: uma gramática estocática G é uma quíntupla (V, Σ, S, P, ρ), onde

V é o conjunto de símbolos não-terminais (variáveis) Σ é o conjunto de símbolos terminais S é o símbolo inicial P é o conjunto de produções da forma

(Σ U V)* V (Σ U V)* → (Σ U V)* ρ é o conjunto de distribuições de probabilidades sobre

as produções de mesmo lado esquerdo

∑i ρ(α → βi) = 1


3434

3434SISTEMAS DE

INFORMAÇÃO34


3434

34

Gramática

• Reconhecimento

• Geração

• Árvore sintática


3535

3535SISTEMAS DE

INFORMAÇÃO35


3535

35

Análise sintática

• Analisadores sintáticos: programas que, dados uma gramática G e uma sequência s, solta:• Se a sequência s é ou não reconhecida pela

gramática G (não estocático)• Qual a probabilidade da sequência s dada G

(estocástico)• Qual(is) a(s) árvore(s) sintática(s) de s dada G

(uma, só a mais provável ou todas)


3636

3636SISTEMAS DE

INFORMAÇÃO36


3636

36

Gramáticas para Reconhecimento de Padrões Sintáticos e Estruturais

• Uma classe pode ser vista como uma linguagem (conjunto de cadeias)

• Cada classe Ci é representada por uma gramática Gi

• Cada gramática atribui a uma cadeia x uma probabilidade P(x|Gi): verossimilhança

• No caso binário (pertence ou não pertence à linguagem) compara-se a um modelo nulo


3737

3737SISTEMAS DE

INFORMAÇÃO37


3737

37

Várias aplicações

• Bioinformática (análise de sequências)

• Processamento de linguagem natural

• Imagens

• Outras...


3838

3838SISTEMAS DE

INFORMAÇÃO38


3838

38

Estrutura secundária de RNAs

Busca por padrões de sequência E estruturais

GRAMÁTICAS REGULARES NÃO RESOLVEM…

Não conseguem modelar pareamentos entre bases


3939

3939SISTEMAS DE

INFORMAÇÃO39


3939

39

Estrutura secundária e gramáticas

| | ||| |

||

||


4040

4040SISTEMAS DE

INFORMAÇÃO40


4040

40

Imagens: representação por quadtrees


4141

4141SISTEMAS DE

INFORMAÇÃO41


4141

41



4242

4242SISTEMAS DE

INFORMAÇÃO42


4242

42



4343

4343SISTEMAS DE

INFORMAÇÃO43


4343

43



4444

4444SISTEMAS DE

INFORMAÇÃO44


4444

44



4545

4545SISTEMAS DE

INFORMAÇÃO45


4545

45



4646

4646SISTEMAS DE

INFORMAÇÃO46


4646

46



4747

4747SISTEMAS DE

INFORMAÇÃO47


4747

47



4848

4848SISTEMAS DE

INFORMAÇÃO48


4848

48



4949

4949SISTEMAS DE

INFORMAÇÃO49


4949

49

Grafos AND-OR


5151

5151SISTEMAS DE

INFORMAÇÃO51


5151

51

Mais exemplos de gramáticas -Detecção de estenoses


5252

5252SISTEMAS DE

INFORMAÇÃO52


5252

52



5353

5353SISTEMAS DE

INFORMAÇÃO53


5353

53



5454

5454SISTEMAS DE

INFORMAÇÃO54


5454

54

Revisão de gramáticas em imagens


5555

5555SISTEMAS DE

INFORMAÇÃO55


5555

55

Gramáticas para Reconhecimento de Padrões Sintáticos e Estruturais

• Uma classe pode ser vista como uma linguagem (conjunto de cadeias)

• Cada classe Ci é representada por uma gramática Gi

• Cada gramática atribui a uma cadeia x uma probabilidade P(x|Gi): verossimilhança

• No caso binário (pertence ou não pertence à linguagem) compara-se a um modelo nulo


5656

5656SISTEMAS DE

INFORMAÇÃO56


5656

56

Gramáticas para Reconhecimento de Padrões Sintáticos

• A gramática pode ser desenhada manualmente ou aprendida

• Modelo nulo N: depende da aplicação– Pode ser uma distribuição uniforme

• Cálculo de um score: • S(x) = P(x|G) / P(x|N) ou• S(x) = logP(x|G) - log P(x|N)

Razão da verossimilhança oulog-likelihood ratio


5757

5757SISTEMAS DE

INFORMAÇÃO57


5757

57

GrammarLab



5858

5858SISTEMAS DE

INFORMAÇÃO58


5858

58

GrammarLab


Aprendizado gramatical (supervisionado): - Aprendizado das produções - Aprendizado das probabilidadesPassos distintos ou conjugados


5959

5959SISTEMAS DE

INFORMAÇÃO59


5959

59

GrammarLab


Amostra de treinamento: - só positiva - positiva e negativa


6060

6060SISTEMAS DE

INFORMAÇÃO60


6060

60

Classificação

• No caso determinístico, se a sequência é reconhecida ou não – Não paramétrico

• No caso estocástico - classificação bayesiana:• comparação com um modelo nulo• Paramétrico:

• Distribuição multinomial sobre as produções com o mesmo lado esquerdo

• Distribuição de Dirichlet sobre as priori´s


6161

6161SISTEMAS DE

INFORMAÇÃO61


6161

61

Referências• RAMOS, M. V. M.; NETO, J. J.; VEJA, I. S. Linguagens Formais:

Teoria, Modelagem e Implementação. Ed. Bookman, 2009.• SIPSER, M. Introdução à Teoria da Computação. Ed. Thomson,

2007• DUDA, R.; HART, P.; STORK, D. Pattern Classification and

Scene Analysis. Ed. John Wiley, 2001. Cap 8.6 e 8.7• DURBIN, R.; EDDY, S. R.; KROGH, A. Biological Sequence

Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 2002. Cap 9


6262

6262SISTEMAS DE

INFORMAÇÃO62


6262

62

Próximas atividades Validação cruzada para os classificadores:

Naive Bayes (aula de redes bayesianas) Redes Neurais (aula de RN) SVM (aula de SVM) Random Forests (aula de árvores de decisão)

Ideia: para cada um dos 3, teste de vários parâmetros (específicos de cada um deles), utilizando:

- todas a características- apenas com os componentes principais selecionados - apenas com as características selecionadas pelo selecionador 1- apenas com as características selecionadas pelo selecionador 2 Em cada um, calcular os valores médios de revocação

(sensibilidade), precisão e erro total. Apresentar os resultados em uma tabela (métricas nas colunas,

com/sem seleção de características nas linhas) e discuti-los

Documents

Tema 06 - Moodle USP: e-Disciplinas