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

SISTEMAS DEINFORMAÇÃO

22

22SISTEMAS DE

INFORMAÇÃO2

2SISTEMAS DEINFORMAÇÃO

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

SISTEMAS DEINFORMAÇÃO

33

33SISTEMAS DE

INFORMAÇÃO3

3SISTEMAS DEINFORMAÇÃO

33

3

Gramáticas

SISTEMAS DEINFORMAÇÃO

44

44SISTEMAS DE

INFORMAÇÃO4

4SISTEMAS DEINFORMAÇÃO

44

4

Gramáticas

símbolos terminaissímbolos não-terminais

símbolo inicial

conjunto de produções

SISTEMAS DEINFORMAÇÃO

55

55SISTEMAS DE

INFORMAÇÃO5

5SISTEMAS DEINFORMAÇÃO

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)*

SISTEMAS DEINFORMAÇÃO

66

66SISTEMAS DE

INFORMAÇÃO6

6SISTEMAS DEINFORMAÇÃO

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)*)

SISTEMAS DEINFORMAÇÃO

77

77SISTEMAS DE

INFORMAÇÃO7

7SISTEMAS DEINFORMAÇÃO

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: αρβ => αγβ

SISTEMAS DEINFORMAÇÃO

88

88SISTEMAS DE

INFORMAÇÃO8

8SISTEMAS DEINFORMAÇÃO

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 }

SISTEMAS DEINFORMAÇÃO

99

99SISTEMAS DE

INFORMAÇÃO9

9SISTEMAS DEINFORMAÇÃO

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 → ε

}

SISTEMAS DEINFORMAÇÃO

1010

1010SISTEMAS DE

INFORMAÇÃO10

10SISTEMAS DEINFORMAÇÃO

1010

10

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 → ε

}

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}

SISTEMAS DEINFORMAÇÃO

1111

1111SISTEMAS DE

INFORMAÇÃO11

11SISTEMAS DEINFORMAÇÃO

1111

11

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 → ε

}

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}

SISTEMAS DEINFORMAÇÃO

1212

1212SISTEMAS DE

INFORMAÇÃO12

12SISTEMAS DEINFORMAÇÃO

1212

12

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 → ε

}

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}

SISTEMAS DEINFORMAÇÃO

1313

1313SISTEMAS DE

INFORMAÇÃO13

13SISTEMAS DEINFORMAÇÃO

1313

13

Gramáticas - Simplificação

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

S → 0S33

S → A

A → 12

A → ε

}

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

S → 0S33 | A

A → 12 | ε

}

SISTEMAS DEINFORMAÇÃO

2121

2121SISTEMAS DE

INFORMAÇÃO21

21SISTEMAS DEINFORMAÇÃO

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

SISTEMAS DEINFORMAÇÃO

2222

2222SISTEMAS DE

INFORMAÇÃO22

22SISTEMAS DEINFORMAÇÃO

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

SISTEMAS DEINFORMAÇÃO

2323

2323SISTEMAS DE

INFORMAÇÃO23

23SISTEMAS DEINFORMAÇÃO

2323

23

Hierarquia de Chomsky

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Σ)*

Hierarquia de Chomsky

24

Fonte: Adaptado de Searls (2002)

Fonte: Adaptado de Matsuno (2006)

25SISTEMAS DEINFORMAÇÃO

2525

2525SISTEMAS DE

INFORMAÇÃO25

25SISTEMAS DEINFORMAÇÃO

2525

25

Árvore sintática ou

Árvore de derivação

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

26SISTEMAS DEINFORMAÇÃO

2626

2626SISTEMAS DE

INFORMAÇÃO26

26SISTEMAS DEINFORMAÇÃO

2626

26

Mais exemplos de árvores sintáticas

27SISTEMAS DEINFORMAÇÃO

2727

2727SISTEMAS DE

INFORMAÇÃO27

27SISTEMAS DEINFORMAÇÃO

2727

27

Mais exemplos de árvores sintáticas

28SISTEMAS DEINFORMAÇÃO

2828

2828SISTEMAS DE

INFORMAÇÃO28

28SISTEMAS DEINFORMAÇÃO

2828

28

Mais exemplos de árvores sintáticas

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

29SISTEMAS DEINFORMAÇÃO

2929

2929SISTEMAS DE

INFORMAÇÃO29

29SISTEMAS DEINFORMAÇÃO

2929

29

Ambiguidade

30SISTEMAS DEINFORMAÇÃO

3030

3030SISTEMAS DE

INFORMAÇÃO30

30SISTEMAS DEINFORMAÇÃO

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

SISTEMAS DEINFORMAÇÃO

3131

3131SISTEMAS DE

INFORMAÇÃO31

31SISTEMAS DEINFORMAÇÃO

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)

SISTEMAS DEINFORMAÇÃO

3232

3232SISTEMAS DE

INFORMAÇÃO32

32SISTEMAS DEINFORMAÇÃO

3232

32

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) Considera a ambiguidade da linguagem!

SISTEMAS DEINFORMAÇÃO

3333

3333SISTEMAS DE

INFORMAÇÃO33

33SISTEMAS DEINFORMAÇÃO

3333

33

Gramáticas Estocásticas

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

SISTEMAS DEINFORMAÇÃO

3434

3434SISTEMAS DE

INFORMAÇÃO34

34SISTEMAS DEINFORMAÇÃO

3434

34

Gramática

• Reconhecimento

• Geração

• Árvore sintática

SISTEMAS DEINFORMAÇÃO

3535

3535SISTEMAS DE

INFORMAÇÃO35

35SISTEMAS DEINFORMAÇÃO

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)

SISTEMAS DEINFORMAÇÃO

3636

3636SISTEMAS DE

INFORMAÇÃO36

36SISTEMAS DEINFORMAÇÃO

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

SISTEMAS DEINFORMAÇÃO

3737

3737SISTEMAS DE

INFORMAÇÃO37

37SISTEMAS DEINFORMAÇÃO

3737

37

Várias aplicações

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

• Processamento de linguagem natural

• Imagens

• Outras...

SISTEMAS DEINFORMAÇÃO

3838

3838SISTEMAS DE

INFORMAÇÃO38

38SISTEMAS DEINFORMAÇÃO

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

SISTEMAS DEINFORMAÇÃO

3939

3939SISTEMAS DE

INFORMAÇÃO39

39SISTEMAS DEINFORMAÇÃO

3939

39

Estrutura secundária e gramáticas

| | ||| |

||

||

SISTEMAS DEINFORMAÇÃO

4040

4040SISTEMAS DE

INFORMAÇÃO40

40SISTEMAS DEINFORMAÇÃO

4040

40

Imagens: representação por quadtrees

SISTEMAS DEINFORMAÇÃO

4141

4141SISTEMAS DE

INFORMAÇÃO41

41SISTEMAS DEINFORMAÇÃO

4141

41

Imagens: representação por quadtrees

SISTEMAS DEINFORMAÇÃO

4242

4242SISTEMAS DE

INFORMAÇÃO42

42SISTEMAS DEINFORMAÇÃO

4242

42

Imagens: representação por quadtrees

SISTEMAS DEINFORMAÇÃO

4343

4343SISTEMAS DE

INFORMAÇÃO43

43SISTEMAS DEINFORMAÇÃO

4343

43

Imagens: representação por quadtrees

SISTEMAS DEINFORMAÇÃO

4444

4444SISTEMAS DE

INFORMAÇÃO44

44SISTEMAS DEINFORMAÇÃO

4444

44

Imagens: representação por quadtrees

SISTEMAS DEINFORMAÇÃO

4545

4545SISTEMAS DE

INFORMAÇÃO45

45SISTEMAS DEINFORMAÇÃO

4545

45

Imagens: representação por quadtrees

SISTEMAS DEINFORMAÇÃO

4646

4646SISTEMAS DE

INFORMAÇÃO46

46SISTEMAS DEINFORMAÇÃO

4646

46

Imagens: representação por quadtrees

SISTEMAS DEINFORMAÇÃO

4747

4747SISTEMAS DE

INFORMAÇÃO47

47SISTEMAS DEINFORMAÇÃO

4747

47

Imagens: representação por quadtrees

SISTEMAS DEINFORMAÇÃO

4848

4848SISTEMAS DE

INFORMAÇÃO48

48SISTEMAS DEINFORMAÇÃO

4848

48

Imagens: representação por quadtrees

SISTEMAS DEINFORMAÇÃO

4949

4949SISTEMAS DE

INFORMAÇÃO49

49SISTEMAS DEINFORMAÇÃO

4949

49

Grafos AND-OR

SISTEMAS DEINFORMAÇÃO

5151

5151SISTEMAS DE

INFORMAÇÃO51

51SISTEMAS DEINFORMAÇÃO

5151

51

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

SISTEMAS DEINFORMAÇÃO

5252

5252SISTEMAS DE

INFORMAÇÃO52

52SISTEMAS DEINFORMAÇÃO

5252

52

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

SISTEMAS DEINFORMAÇÃO

5353

5353SISTEMAS DE

INFORMAÇÃO53

53SISTEMAS DEINFORMAÇÃO

5353

53

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

SISTEMAS DEINFORMAÇÃO

5454

5454SISTEMAS DE

INFORMAÇÃO54

54SISTEMAS DEINFORMAÇÃO

5454

54

Revisão de gramáticas em imagens

SISTEMAS DEINFORMAÇÃO

5555

5555SISTEMAS DE

INFORMAÇÃO55

55SISTEMAS DEINFORMAÇÃO

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

SISTEMAS DEINFORMAÇÃO

5656

5656SISTEMAS DE

INFORMAÇÃO56

56SISTEMAS DEINFORMAÇÃO

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

SISTEMAS DEINFORMAÇÃO

5757

5757SISTEMAS DE

INFORMAÇÃO57

57SISTEMAS DEINFORMAÇÃO

5757

57

GrammarLab

• A gramática pode ser desenhada manualmente ou aprendida

SISTEMAS DEINFORMAÇÃO

5858

5858SISTEMAS DE

INFORMAÇÃO58

58SISTEMAS DEINFORMAÇÃO

5858

58

GrammarLab

• A gramática pode ser desenhada manualmente ou aprendida

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

SISTEMAS DEINFORMAÇÃO

5959

5959SISTEMAS DE

INFORMAÇÃO59

59SISTEMAS DEINFORMAÇÃO

5959

59

GrammarLab

• A gramática pode ser desenhada manualmente ou aprendida

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

SISTEMAS DEINFORMAÇÃO

6060

6060SISTEMAS DE

INFORMAÇÃO60

60SISTEMAS DEINFORMAÇÃO

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

SISTEMAS DEINFORMAÇÃO

6161

6161SISTEMAS DE

INFORMAÇÃO61

61SISTEMAS DEINFORMAÇÃO

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

SISTEMAS DEINFORMAÇÃO

6262

6262SISTEMAS DE

INFORMAÇÃO62

62SISTEMAS DEINFORMAÇÃO

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