Elementos da Teoria de Evidência de Dempster-Shafer

Elementos da Teoria de Evidência de Dempster-Shafer

Joaquim Quinteiro Uchôa;

Sônia Maria Panontim&

Maria do Carmo Nicoletti

Universidade Federal de São Carlos (UFSCar)

Departamento de Computação (DC)

C. P. 676 - 13.565-905 - São Carlos (SP) - Brasil

e-mail: joaquim, sonia, [email protected]

Resumo: O problema de raciocinar com incerteza é reconhecido como uma área de grande

importância em Inteligência Artificial. Esse relatório apresenta a Teoria de Evidências de

Dempster-Shafer (TDS), seus conceitos básicos e fundamentos. São abordados com detalhes

a atribuição básica de probabilidade, função de crença, função de comunalidade, plausibili-

dade, intervalo de crença, regra de combinação de Dempster e peso do conflito. Além disso

a TDS é avaliada como medida de incerteza, de acordo com critérios propostos por Walley

em [Walley (1995)].

Palavras-chaves: função de crença, plausibilidade, intervalo de crença, incerteza, evidência,

teoria de Bayes, probabilidade, sistemas baseados em conhecimento, peso de conflito, regra

de combinação de Dempster.

“Todas as verdades esperam em todas as coisas,

elas nem apressam sua própria descoberta, nem resistem à ela,

elas não necessitam do fórceps do obstetra,

as insignificantes são tão grandes para mim como qualquer outra,

(o que é menor ou maior que um toque?) “

Walt Whitman, Canto de Mim Mesmo n. 30,1881.

ÍNDICE

Elementos da Teoria de Evidência de Dempster-Shafer 1

Introdução 1

Critérios para a avaliação de medidas de incerteza 2

Considerações sobre a Teoria de Evidência de Dempster-Sha-

fer 3

O Domínio do Problema na TDS: Um Exemplo Simplificado 4

Conceitos Básicos 5

Função de Crença 8

Número e Função de Comunalidade 13

Plausibilidade de Uma Função de Crença 17

Intervalos de Crença 18

Funções de Crença Bayseanas 18

Combinação da Função de Crença 20

Peso de Conflito 24

Avaliando a TDS com os critérios de Walley 27

Conclusões 28

Bibliografia 29


1 Introdução

Assim como acontece com qualquer software, sistemas baseados em conhecimento devem

ser capazes de representar, manipular e comunicar dados. É fato que tais sistemas devem estar

preparados para modelar e tratar dados considerados imperfeitos; muitas vezes o que se

convenciona chamar de dados imperfeitos abrange dados imprecisos, inconsistentes, parcial-

mente ignorados e mesmo incompletos. Como comentado em [Bonissone (1991), p.854],

a presença da incerteza em sistemas baseados em conhecimento pode se originar devárias fontes: da confiabilidade parcial que se tem na informação, da imprecisãoinerente à linguagem de representação na qual a informação é expressa, da nãocompleteza da informação e da agregação/sumarização da informação que provêmde múltiplas fontes.

Existem vários modelos formais disponíveis para o tratamento de incertezas; apesar

disso, muitas vezes o tratamento da incerteza em sistemas baseados em conhecimento tem

sido feito através de abordagensad hoc, baseadas em representações e combinações de regras

que não estão subsidiadas por uma teoria bem fundamentada e tampouco têm o respaldo de

uma semântica bem definida.

Deve ser lembrado também que problemas relacionados com incertezas acontecem em

todo sistema baseado em conhecimento. Durante o projeto de bases de conhecimento, por

exemplo, deve se ter sempre em mente que o conhecimento com o qual se trabalha raramente

está completo ou é exato e que maneiras de lidar com essa situação devem ser implementadas.

Assim, bases de conhecimento se constituem numa das principais fontes de informações

incertas em sistemas baseados em conhecimento. Como comentado em [Ng (1990), p.30]:

se toda informação pudesse ser representada de maneira completa e precisa, qualquersistema robusto de inferência lógica poderia ser utilizado para a extração de conclu-sões válidas.

Entre as abordagens mais tradicionais existentes para a modelagem e tratamento de

incertezas, encontram-se:

w regra de Bayes [Pearl (1982)]

w regra de Bayes modificada [Duda (1976)]

w fator de certeza [Gordon & Shortliffe (1975)], baseada em teoria da confirmação

w teoria de Dempster-Shafer [Dempster (1967), Shafer (1976)]

w teoria da possibilidade [Zadeh (1978)]

w raciocíniodefault[Reiter (1980)]

w teoria deendorsements[Cohen (1985)]

w teoria de conjuntos aproximados [Pawlak (1982)]


1

Este trabalho apresenta e discute os principais elementos daTeoria de Evidência de

Dempster-Shafer(TDS), quando da representação de conhecimento incerto. Com esse

objetivo, na Seção 2 são apresentados critérios a serem considerados para a avaliação de

medidas de incerteza. A Seção 3 comenta sobre a Teoria Dempster-Shafer e suas vantagens

em relação aos outros métodos de tratamento de incerteza. Na Seção 4, é definido o domínio

do problema da TDS, usando um exemplo simplificado. Na Seção 5, são fornecidos os

conceitos básicos da TDS e alguns exemplos são discutidos para uma melhor compreensão

por parte do leitor. Na Seção 6, é apresentada e discutida a função de crença. Comunalidade,

plausibilidade e intervalos de crença são discutidos respectivamente nas Seções 7, 8 e 9. A

Seção 10 fala sobre funções de crença bayseanas, mostrando como alguns conceitos da Teoria

de Bayes podem ser expressos pela TDS. A seção 11 descreve o processo pelo qual funções

de crença podem ser combinadas, usando a regra de Dempster. A Seção 12 discute o conflito

entre funções de crença e quando estas podem ser combinadas e na Seção 13 a TDS é

analisada considerando os critérios discriminados na Seção 2. A Seção 14 discute o signifi-

cado de alguns termos comuns à várias terorias, inclusive à TDS, compara alguns aspectos

da TDS versus Teoria de Bayes e adianta o próximo passo do trabalho sendo desenvolvido.

2 Critérios para a avaliação de medidas de incerteza

Walley em [Wal1ey (1996), p.3-4] discute a necessidade do estabelecimento de critérios para

a avaliação das medidas de incerteza e propõe seis critérios, básicos:

(1) Interpretação: a medida deve ter uma interpretação clara que seja suficientemente

precisa para:

w poder ser usada

w que se possa entender as conclusões do sistema e usar tais conclusões para deflagrar

as ações correspondentes

w que se possa estabelecer regras para a combinação de tais medidas e para a sua

atualização

Esse critério é essencial para “dar significado” à medida e justificar as conclusões

do sistema.

(2) Imprecisão:a medida deve ser capaz de modelar ignorância parcial ou incompleta,

informação limitada ou conflitante, bem como declarações imprecisas de incerteza.

É importante lembrar que ignorância parcial e informações conflitantes são comuns

em domínios reais.

(3) Cálculo: devem existir regras para:

w combinar medidas de incerteza

w atualizá-las, após a evidência de novas informações

w usá-las, para calcular outras incertezas


2

w derivar conclusões e tomar decisões

A satisfação desse critério é fundamental para que conclusões possam ser derivadas

de valores incertos.

(4) Consistência:por um lado, o sistema de tratamento de incertezas deve fornecer

métodos que permitam a verificação da consistência de todas as declarações de

incerteza e de todas as suposiçõesdefault. Por outro lado, as regras de cálculo devem

garantir que as conclusões sejam consistentes com todas as declarações e suposições

defaults.

(5) Declaração (Input): o sistema deve cuidar para que o usuário não tenha problemas

quando do fornecimento de todos os valores de incerteza necessários como entrada

do sistema. Além disso, um sistema para o tratamento de incertezas deve viabilizar

a combinação de avaliações qualitativas com valores quantitativos de incerteza.

(6) Computação: deve ser computacionalmente factível para o sistema derivar

inferências e conclusões a partir das declarações iniciais.

Walley classifica a seguir esses seis critérios em teóricos (1, 2, 3 e 4) e práticos (5 e 6).

Os critérios teóricos são aqueles que, para serem verificados necessitam ser subsidiados por

uma teoria adequada de incerteza que viabilize tal verificação, independentemente do domínio

da aplicação. Já os critérios práticos são aqueles que, dependendo da aplicação, podem ou

não ser satisfeitos. São dependentes do tipo de modelo utilizado, do número de entradas

necessárias, da restrição de tempo, do poder computacional e da habilidade do usuário. Na

Seção 12 a TDS é avaliada com relação a esses 6 critérios.

3 Considerações sobre a Teoria de Evidência de

Dempster-Shafer

A Teoria de Dempster-Shafer se originou com o trabalho de Dempster sobre probabilidades

inferior e superior [Dempster (1967), Dempster (1967a)] e teve continuidade com os trabalhos

de Shafer [Shafer (1976)], que refinou e estendeu as idéias de Dempster.

O investimento no modelo Dempster-Shafer para o tratamento de incertezas em sistemas

baseados em conhecimento foi motivado principalmente por problemas encontrados na

modelagem da incerteza usando métodos puramente probabilísticos, e também pela falta de

embasamento matemático do modelo fator de certeza do MYCIN. Como comentado em

[Gordon & Shortliffe (1984), p.272]:

a vantagem da Teoria de Dempster-Shafer sobre as abordagens anteriores está nahabilidade deste método em modelar oafunilamentodo conjunto de hipóteses, àmedida em que se acumulam evidências; este procedimento reflete o processo quecaracteriza o raciocínio usado em diagnóstico e o raciocínio especializado em geral.


3

Uma vez que a TDS atribui valores de crença a subconjuntos e a cada elemento do

conjunto de hipóteses, essa teoria tem condições de refletir mais precisamente o processo de

acúmulo de evidências. Além disso a TDS permite que funções de crença possam ser

combinadas, produzindo novas funções de crença num procedimento que independe da ordem

na qual as evidências surgem, mas que, entretanto, exige que as hipóteses primitivas sendo

consideradas sejam mutuamente exclusivas e exaustivas. A partir destas hipóteses primitivas

(também denominadassingletons, ou unidades, por serem conjuntos unitários), é possível

construir hipóteses mais elaboradas que não são mutuamente exclusivas ou exaustivas.

Apesar da TDS ter muito em comum com o modelo de Fator de Certeza, é, ao contrário

deste modelo, bem fundamentada matematicamente. A regra de combinação de fatores de

certeza bem como a regra de combinação da Teoria de Bayes são, na realidade, especializações

da regra de combinação da TDS. Como comentado em [Stein (1993), p. 26],

se tivermos observado várias evidências independentes (dados observados) e sealgumas inferências gerais a respeito do que cada evidência implica puderem serfeitas, a TDS permite que essas evidências possam ser combinadas de uma maneiraconsistente e probabilística, para se estabelecer o que o conjunto de evidênciasconsiderado como um todo, implica.

A partir de uma única única coleção de evidências, usando a TDS, vários conjuntos

alternativos de hipóteses podem ser derivados. A cada um desses conjuntos está associado

um intervalo de confiança chamado de intervalo de crença. A TDS permite que, quando da

determinação da validade de uma determinada hipótese, possam ser consideradas todas as

informações disponíveis.

4 O Domínio do Problema na TDS: Um Exemplo Simplificado

Suponha que um paciente apresente manchas vermelhas pelo corpo e que isso seja sintoma

de qualquer dos seguintes problemas: alergia a, intoxicação i, sarampo s, rubéola r.

Óbvio que existem muitos outros possíveis problemas, mas para efeito de simplicidade, vamos

supor que existam apenas esses quatro.

Na TDS o conjunto das hipóteses primitivas é chamado dedomíniodo problemaou

framedediscernimento,ou aindaquadrodediscernimentoe é notado porΘ . Nesse exemplo

1 ,Θ = alergia a, intoxicação i, sarampo s, rubéola r

. A TDS assume para qualquer

domínio de problemaΘ que:

(1) Θ é exaustivo, no sentido de ser completo (conter toda possível hipótese primitiva);

(2) as hipóteses primitivas (singletons) emΘ são mutuamente exclusivas.

Suponha agora que um outro sintoma (evidência) considerado pelo médico aponte:


4

w para um diagnóstico dereação orgânica, definida no exemplo como o conjunto

alergia, intoxicação, ou então

w para um diagnóstico deinfecção, definida no exemplo como o conjunto sarampo,rubéola.

Se o médico, por exemplo, observar uma evidência que confirma com um determinado

grau o diagnósticoreação orgânica, ele irá atribuir uma quantidade de crença ao conjunto

alergia, intoxicação proporcional ao grau observado de confirmação da evidência.

Uma nova evidência pode, por exemplo, excluir sarampo do diagnóstico. Uma evidência

que “desconfirma” sarampo pode ser tratada como uma evidência que confirme o resto do

conjunto de hipóteses, ou seja, que confirma o conjunto rubéola, alergia, intoxicação. Como

já visto, um subconjunto de hipóteses deΘ pode ser visto como uma nova hipótese, formada

pela disjunção de seus elementos, uma vez que como se sabe, hipóteses primitivas são

mutuamente exclusivas. O conjuntoΘ das hipóteses primitivas dá origem a 2|Θ| possíveis

hipóteses, como mostra a Figura 1 para o exemplo anterior ondeΘ = a,i,s,r. Em um

determinado domínio apenas alguns subconjuntos de 2Θ serão de interesse.

O papel do domínio do problemaΘ na TDS se assemelha ao do espaço amostral (Ω) na

teoria de probabilidade; a diferença entretanto é que na TDS, o número de possíveis hipóteses

é 2|Θ|, enquanto que na Teoria de Probabilidade é |Ω|.

a,i,s,r

a,i,r

a,s i,sa,r

a,s,r

i,r

i,s,r

s,r

a ri s

a,i,s

a,i

Figura 1

Conjunto de todas as possíveis hipóteses obtidas do conjunto de hipótesesprimitivasΘ =

a,i,s,r


5

5 Conceitos Básicos

Para indicar a crença em uma hipótese, dada uma evidência, a TDS associa à essa crença, um

número no intervalo [0, 1]. A relevância de cada evidência para cada um dos elementos de

2Θ é representada por uma função chamadaatribuição de probabilidade básica(bpa - do

inglêsbasic probability assignment),ou funçãodemassa.

A bpa é uma generalização da função de densidade da probabilidade sendo que essa

última associaria um número do intervalo [0, 1] a toda hipótese primitiva deΘ, de maneira

que a soma desses números totalizasse 1. Usando 2Θ, o conjunto de todos possíveis subcon-

juntos deΘ, a bpa notada pormatribui um número do intervalo [0, 1] a todo subconjunto de

Θ, de maneira que a soma dessas atribuições seja 1. (Por definição, o número 0 deve ser

atribuído ao conjunto vazio, uma vez que o conjunto vazio corresponde à hipótese falsa. É

falso porqueΘ é exaustivo). Essa função representa a quantidade total de crença na evidência

que aponta exatamente para um determinado conjunto de hipóteses e, como é probabilidade,

varia entre 0 e 1.

Assim sendo,m permite a atribuição de uma quantidade de crença a cada elemento do

reticulado da Figura 1 e não apenas aos elementos a, i, s e r, como acontece com a

função de densidade da probabilidade. A quantidadem(A) é a medida daquela parte da crença

total, que é atribuída exclusivamente àA, ondeA é qualquer elemento de 2Θ e a crença total

sendo 1. Essa parte da crençam(A), não pode ser subdividida posteriomente entre os

subconjuntos deA e não inclui parte da crença atribuída a subconjuntos deA [Gordon &

Shortliffe (1984)]. Formalmente, seΘ é umdomínio de problema, entãom:2Θ → [0,1] é

chamada deatribuição básica de probabilidade(bpa) se satisfaz:

1. m(∅) = 0

2. m(A) ≥ 0, ∀ A∈2Θ

3. ∑m(A)

A∈2Θ

= 1

Como convenção, a probabilidade básica que “sobra”, após as probabilidades básicas

terem sido atribuídas aos subconjuntos próprios deΘ é chamada decrençanãoatribuída,

notada porm(Θ). Sem(A) = xemnão atribui crença a qualquer outro subconjunto deΘ, então

m(Θ) = 1−x . O resto da crença é pois atribuído aΘ, e não à negação da hipóteseA, como

seria no modelo de Bayes.

A TDS vê a observação de evidência contra uma hipótese apenas como evidência que

suporta a negação da hipótese. Assim, no exemplo, evidência que desconfirma a hipótese

sarampo é equivalente a evidência que confirma a hipótese alergia, intoxicação, rubéola

(qualquer hipótese menos sarampo).


6

Exemplo 2: Para o exemplo anterior, uma possível atribuição de probabilidade básica poderia

ser:

m(s ) = 0.2

m(a ) = 0.3

m(r ) = 0.1

m(s, a) = 0.4

m(A) = 0, para∀ A∈2Θ, A≠s, A≠a, A≠r, A≠s,a

Exemplo 3 [Stein (1993), p.26-27]:considere uma situação de previsão no mercado de ações

ondeΘ = NMG, −5%,−1%, 0%, 1%, 5%, PMG, onde cada elemento é uma hipótese indi-

cando uma mudança no preço de ações nas próximas 24 horas e os termos NMG e PMG

indicam mudanças negativas e positivas muito grande, respectivamente. Considere, agora o

conjunto H1 = 1%, 5%, PMG

que contém as hipóteses que refletem um movimento de

valorização no mercado financeiro. Suponha que uma determinada regra de análise financeira

suporte em 60% o conjunto de hipóteses H1, dada uma determinada evidência. A função m

então é calculada como:

H1 = 1%, 5%, PMG

m(H1) = 0.6

Θ m(Θ) = 1−0.6= 0.4

Note que Θ contém o conjunto H1, assim como o seu complemento

H1___

= NMG, −5%,−1%, 0%

. Usando a TDS, é errado atribuir o valor 0.4 apenas a H1

___, uma

vez que não existe evidência que o restante 0.4 de probabilidade de fato contradiz H1. Sabe-se

apenas que a evidência existente suporta H1 com uma confiança de 0.6. Essencialmente, o

que se está dizendo com isso é que se está 60% confiante que a evidência observada indica

uma valorização expressa em H1. Por outro lado, sabe-se com 40% de confiança que a

evidência observada, não diz nada. Atribui-se então, os 40% restante de probabilidade ao

domínio do problema, o qual contém ambos: H1 e H1___

. Mais tarde, com o aparecimento de

novas evidências, esses 40% podem ser reduzidos ainda mais.

Exemplo 4: Suponha que não exista evidência com relação a qualquer diagnóstico em um

paciente com manchas vermelhas (ver Exemplo 1). A função de atribuição de probabilidade

atribui 1 aΘ = sarampo, alergia, intoxicação, rubéola

e 0 a qualquer outro subconjunto de

Θ. O modelo de Bayes tenta representar a ignorância através de uma função que atribui 0.25

a cada hipótese primitiva, assumindo nenhuma informação a priori. É importante notar que

tal atribuição implica mais informação do que realmente existe.


7

Exemplo 5: Suponha uma evidência que desconfirma o diagnóstico de sarampo, com um grau

0.7. Isso é equivalente a confirmar o não-sarampo com grau 0.7. Assimm(a, r, i ) = 0.7,

m(Θ) = 0.3 e o valor dem para qualquer outro subconjunto deΘ é 0.

Exemplo 6: Suponha uma evidência que confirma o diagnóstico de sarampo, com um grau

0.6. Entãom(sarampo) = 0.6,m(Θ) = 0.4 emé zero em qualquer outro conjunto.

A TDS permite que opesode várias “pequenas evidências” possa ser relevante, mesmo

que nenhuma delas, sozinha, seja relevante - as próximas seções discutem isso.

6 Função de Crença

A funçãodecrença, denotadabel, correspondente a uma determinada função de atribuição

de probabilidadem, atribui a todo subconjuntoA de Θ, a soma das probabilidades básicas

atribuídas a todo subconjunto deA, por m. A quantiam(A) mede a crença que se atribui

exatamente aA e não o total de crença que se atribui aA. Para se obter a medida do total de

crença atribuído a A, deve-se adicionar àm(A) os valoresm(B), para todo subconjunto próprio

B de A:

bel(A) = ∑m(X)X⊆A

(I)

Uma funçãobel:2Θ → [0,1] é chamada defunção de crençasobreΘ se ela for dada por

(I), relativa a alguma atribuição de probabilidade básicam:2Θ → [0,1].

Com certeza a função de crença com estrutura mais simples é aquela obtida fazendo

m(Θ) = 1 em(A) = 0 para todoA ≠ Θ. Ela tembel(Θ) = 1 ebel(A) = 0 para todoA ≠ Θ. Desde

que essa função de crença parece apropriada quando não se tem evidências, ela é chamada de

funçãodecrençavacuosa. A classe de funções de crença pode ser caracterizada sem referencia

à atribuição de probabilidade básica:

Teorema 1: SeΘ é o domínio do problema, entãobel:2Θ → [0,1] é uma função de crença se

e somente se satisfaz às seguintes condições:

(1) bel(∅) = 0 (a crença na hipótese nula é 0)

(2) bel(Θ) = 1 (a crença no domínio do problema é 1)

(3) Para todo inteiro positivon, e toda coleçãoA1,...,An de subconjuntos deΘ,


8

bel(A1∪…∪An) ≥ ∑bel

i

(Ai) − ∑bel

i<j

(Ai∩Aj) + ∑bel(i<j<k

Ai∩Aj∩Ak) − … +

(−1)n+1bel(A1∩…∩An) = ∑(−1)|I|+1

I ⊆ 1,..., nI≠∅

bel(∩Ai

i∈I

)

Para a prova deste teorema é importante primeiro provar os seguintes resultados:

Lema 1: Se A é um conjunto finito, então∑(−1)|B|

B⊆A

=

1,0,

seA = ∅caso contrário

Prova do Lema 1:O binômio de Newtongarante que sex e a são números reais en é um

inteiro positivo, então(x + a)n = ∑k = 0

nnk

akxn−k, ondenk

representa o número possível de

combinações den elementos tomadosk ak. Fazendo-sex = 1 e a = −1, tem-se

0 = (1−1)n =

= n0

(−1)0(1)n−0 − n1

(−1)1(1)n−1 + n2

(−1)2(1)n−2 + … + nn

(−1)n(1)0 =

= n0

− n1

+ n2

− … + (−1)nnn

w quandoA = a1,...,an,

∑(−1)|B|

B⊆A

=

= (−1)|∅| + ∑(−1)|ai|

i

+ ∑(−1)|ai,aj|

i<j

+ ∑(−1)|ai,aj,ak|

i<j<k

+ … + (−1)|A| =

= (−1)0 + ∑(−1)1

i

+ ∑(−1)2

i<j

+ ∑(−1)3

i<j<k

+ … + (−1)n =

= n0

− n1

+ n2

− … + (−1)nnn

= 0

w quandoA = ∅,

∑B⊆A

(−1)|B| = (−1)|A| = 1


9

Então, dada uma atribuição básica de probabilidadem, a funçãobel:2Θ → [0,1] definida

comobel(A) = ∑X⊆A

m(X) é uma função de crença.

Prova do Teorema 1:Se a função de crença é dada porα, para alguma atribuição de

probabilidade básicam, então as condições (1) e (2) do Teorema 1 seguem da definição da

atribuição de probabilidade básica, ou seja,

1. bel(∅) = ∑m(B)B⊆∅

= m(∅) = 0

2. bel(Θ) = ∑m(B)B⊆Θ

= 1

Para prova da condição (3), considereAi,...,An uma família fixa de subconjuntos de

Θ e sejaI(B) = i | 1≤ i ≤n; B⊆Ai para cadaB⊆Θ:

∑(−1)|I|+1

I ⊆ 1,..., nI≠∅

bel∩Ai

i∈I

= ∑I ⊆ 1,..., n

I≠∅

(−1)|I|+1 ∑B⊆

∩Ai

i∈I

m(B)

,

pela definição de função de crença. Mas, fazendo-se∩Ai

i∈I

= AI para simplicidade de notação,

a seguinte igualdade é obtida com rearranjamento dos termos:

∑I ⊆ 1,..., n

I≠∅

(−1)|I|+1 ∑B⊆ AI

m(B)

= ∑B⊆Θ

I(B) ≠ ∅

m(B) ∑I ⊆ I(B)

I≠∅

(−1)|I|+1

,

Simplificando a última expressão, tem-se:

∑B⊆Θ

I(B) ≠ ∅

m(B) ∑I ⊆ I(B)

I≠∅

(−1)|I|+1

= ∑B⊆Θ

I(B) ≠ ∅

m(B)

1|∅| − 1|∅| + ∑I ⊆ I(B)

I≠∅

(−1)|I|+1

=

= ∑B⊆Θ

I(B) ≠ ∅

m(B)

1 + ∑I ⊆ I(B)

(−1)|I|+1

= ∑B⊆Θ

I(B) ≠ ∅

m(B)

1 + ∑I ⊆ I(B)

(−1)|I| (−1)1

=

= ∑B⊆Θ

I(B) ≠ ∅

m(B)

1 − ∑I ⊆ I(B)

(−1)|I|

Utilizando o Lema 1 sabendo queI(B) ≠ ∅, tem-se que:


10

∑I ⊆ I(B)

(−1)|I| = 0

donde

∑B⊆Θ

I(B) ≠ ∅

m(B)

1 − ∑I ⊆ I(B)

(−1)|I|

= ∑B⊆Θ

I(B) ≠ ∅

(m(B) (1 − 0)) =

∑B⊆Θ

I(B) ≠ ∅

m(B) = ∑B⊆Θ

B⊆Ai, algumi

m(B) ≤ ∑B⊆Θ

B⊆Ai∪…∪An

m(B) = bel(Ai∪…∪An)

DadoA⊆Θ, bel(A) + bel(A__

) ≤1, pois:

1 = bel(Θ) = bel(A∪A__

) ≥ bel(A) + bel(A__

) − bel(A∩A__

),

uma vez queA∩A__

= ∅, bel(A∩A__

) = 0.

Logo, dada uma funçãoφ:2Θ → [0,1], comφ(∅) = 0 eφ(Θ) = 1, uma condição neces-

sária (mas não suficiente) para queφ seja uma função de crença é queφ(A)+φ(A__

) ≤ 1 para

todoA⊆Θ.

É importante notar também quebelem têm o mesmo valor em cada uma das hipóteses

primitivas e quebelé maior ou igual amem conjuntos que contém mais do que um elemento,

ou seja, seA⊆Θ não for uma hipótese primitiva, entãobel(A) é a soma dos valores dempara

todo subconjunto na subárvore que temA por raíz. Considerando o Exemplo 1 (Secão 4, p.

4), tem-se

bel(s) = m(s) e

bel(a, s) = m(a, s) + m(a) + m(s) ≥ m(a, s).

Dada uma função de crença bel, é possível encontrar sua atribuição de probabilidade

básica, como garante o teorema 2. Antes de sua apresentação, entretanto, dois lemas são

necessários:

Lema 2: SeA é um conjunto finito eB⊆A, então

∑C

B⊆C⊆A

(−1)|C| = (−1)|A|,

0,seA = Bcaso contrário

Prova do Lema 2:segue diretamente do Lema 1 e do fato que


11

∑C

B⊆C⊆A

(−1)|C| = ∑D⊆(A − B)

(−1)|B∪D| = ∑D⊆(A − B)

(−1)|B|(−1)|D| = (−1)|B| ∑D⊆(A − B)

(−1)|D|

Tem-se duas situações

(i) A = B, o que, pelo Lema 1 garante:

(−1)|B| ∑D⊆(A − B)

(−1)|D| = (−1)|B|1 = (−1)|B| = (−1)|A|,

poisA − B = ∅.

(ii) A ≠ B, o que, pelo Lema 1 garante:

(−1)|B| ∑D⊆(A − B)

(−1)|D| = (−1)|B|0 = 0,

poisA − B ≠ ∅.

Lema 3: SejaΘ um conjunto finito ef eg funções em 2Θ. Então:

f(A) = ∑B⊆A

g(B) para todoA⊆Θ

se e somente se

g(A) = ∑B⊆A

(−1)|A − B| f(B) para todoA⊆Θ.

Prova do Lema 3:Segue do Lema 2. Sef(A) = ∑B⊆A

g(B) para todoA⊆Θ, então

∑B⊆A

(−1)|A − B| f(B) = (−1)|A| ∑B⊆A

(−1)|B| f(B) = (−1)|A| ∑B⊆A

(−1)|B| ∑C⊆B

g(C)

Mas,

(−1)|A| ∑B⊆A

(−1)|B| ∑C⊆B

g(C)

= (−1)|A| ∑C⊆A

g(C) ∑B

C⊆B⊆A

(−1)|B|

com simples rearranjo dos termos. Utilizando-se do Lema 2, tem-se

(−1)|A| ∑C⊆A

g(C) ∑B

C⊆B⊆A

(−1)|B|

= (−1)|A| g(A) (−1)|A| = g(A) para todoA⊆Θ.


12

Por sua vez, seg(A) = ∑B⊆A

(−1)|A − B| f(B) para todoA⊆Θ, então:

∑B⊆A

g(B) = ∑B⊆A

∑

C⊆B

(−1)|B − C| f(C)

= ∑C⊆B

(−1)|C| f(C) ∑B

C⊆B⊆A

(−1)|B|

=

(−1)|A| f(A) (−1)|A| = f(A) para todoA⊆Θ.

Teorema 2: Suponhabel:2Θ → [0,1] é a função de crença dada pela atribuição de prob-

abilidade básicam:2Θ → [0,1]. Então, para todoA⊆Θ:

m(A) = ∑(−1)|A−B|

B⊆A

bel(B)

Prova do Teorema 2:sejabel:2Θ → [0,1] é a função de crença dada pela atribuição de

probabilidade básicam:2Θ → [0,1]:

bel(A) = ∑X⊆A

m(X), para todoA⊆Θ

Aplicando-se diretamente o Lema 3, tem-se:

m(A) = ∑(−1)|A−B|

B⊆A

bel(B), para todoA⊆Θ

Na TDS, o principal interesse são aqueles subconjuntos deΘ que têm atribuição de

probabilidade básica não nula. Cada um desses subconjuntos é chamado deelemento focal

da função de crença bel sobre 2Θ. A união de todos os elementos focais, para uma função de

crença, é chamada seunúcleo (ou centro). No Exemplo 2, dado quem(s ) = 0.2,

m(a ) = 0.3, m(r ) = 0.1, m(s, a) = 0.4, o núcleo da função de crença é s, a, r. Além

disso,bel(s, a) = m(s ) + m(a ) + m(s, a) = 0.9. SeC for o centro de uma função de

crençabelsobreΘ, entãoB⊆Θ satisfazbel(B) = 1 se e somente seC⊆B.

7 Número e Função de Comunalidade

A noção intuitiva de função de crença pode ser mais facilmente apreendida se o conjuntoΘ

for representado geometricamente. Se os elementos deΘ forem considerados como pontos,

dadoA⊆Θ, pode ser de interesse representar a massa de probalidade total que pode ser movida


13

para os pontos deA. A essa quantia, dá-se o nome denúmerode comunalidadede A,

representada porQ(A), e à função que calcula o número de comunalidade para todoA⊆Θ,

dá-se o nome defunçãode comunalidade. Pela definição, tem-se então que a função de

comunalidade é uma funçãoQ : 2Θ→[0,1] tal que:

Q(A) = ∑B⊆ΘA⊆B

m(B)

Ou seja, a comunalidade de A é a soma das atribuições de todos os conjuntos que contém

A. Representa, dessa forma, a quantidade de crença que pode ser refinada até A.

Exemplo 7: SejamA = s, B = a e C = s,a como no Exemplo 2. Neste caso, a atribuição

de probabilidade básica emAeBpoderia ser acrescida com o refinamento da atribuição básica

em C. Isso pode ser expresso pelas comunalidades deA e B, maiores que as respectivas

atribuições de probabalidade básica:

Q(A) = ∑X⊆ΘA⊆X

m(X) = m(A)+m(C) = 0.2+0.4= 0.6 e

Q(B) = ∑X⊆ΘB⊆X

m(X) = m(B)+m(C) = 0.3+0.4= 0.7

Facilmente percebe-se queQ(∅) = 1. Além disso, função de crença pode ser expressa

através da função de comunalidade, e vice-versa, como garante o Teorema 3. Antes de sua

demonstração, entretanto, dois lemas são necessários:

Lema 4: SejaΘ e sejamf eg funções em 2Θ. Então:

f(A) = ∑B⊆A

(−1)|B|+1 g(B) para todoA⊆Θ

se e somente se

g(A) = ∑B⊆A

(−1)|B|+1 f(B) para todoA⊆Θ.


14

Prova do Lema 4: Se f(A) = ∑B⊆A

(−1)|B|+1 g(B) vale para todoA⊆Θ, então

∑B⊆A

(−1)|B|+1 f(B) = ∑B⊆A

(−1)|B|+1 ∑C⊆B

(−1)|C|+1 g(C)

= ∑C⊆A

(−1)|C| g(C) ∑B

C⊆B⊆A

(−1)|B|

Utilizando o Lema 2, tem-se

∑C⊆A

(−1)|C| g(C) ∑B

C⊆B⊆A

(−1)|B|

= g(A) para todoA⊆Θ.

A demonstração de que, seg(A) = ∑B⊆A

(−1)|B|+1 f(B) vale para todoA⊆Θ, então

f(A) = ∑B⊆A

(−1)|B|+1 g(B) para todoA⊆Θ é trivial e segue o modelo acima.

Lema 5: SejaΘ e sejamf eg funções em 2Θ. Então:

f(A) = ∑B⊆A

__(−1)|B| g(B) para todoA⊆Θ se e somente seg(A) = ∑

B⊆A

(−1)|B| f(B__

).

Prova do Lema 5:Sejah(A) = −f(A__

) para todoA⊆Θ.

Sef(A) = ∑B⊆A

__(−1)|B| g(B) para todoA⊆Θ, então:

h(A) = −f(A__

) = − ∑B⊆(A

__)

___(−1)|B| g(B) = ∑

B⊆A

(−1)|B| (−1)1 g(B) = ∑B⊆A

(−1)|B|+1 g(B)

Pelo Lema 4, g(A) = ∑B⊆A

(−1)|B|+1 h(B) = ∑B⊆A

(−1)|B|+1 −(f(B__

)) =

∑B⊆A

(−1)|B| (−1)1 (−1)1 f(B__

) = ∑B⊆A

(−1)|B| f(B__

).

Por sua vez, seg(A) = ∑B⊆A

(−1)|B|+1 f(B__

), então∑B⊆A

__(−1)|B| g(B) = −h(A

__) = f(A).


15

Teorema 3: SejaQ : 2Θ→[0,1], uma função de comunalidade, entãobel:2Θ → [0,1] dada

porbel(A) = ∑B⊆A

__(−1)|B| Q(B) é a função de crença associada a essa função de comunalidade.

Por sua vez, sebel:2Θ → [0,1] é uma função de crença, entãoQ(A) = ∑B⊆A

(−1)|B| bel( B__

)

é a função de comunalidade associada a essa função de crença.

Prova do Teorema 3: Seja Q : 2Θ→[0,1], uma função de comunalidade, então

bel:2Θ → [0,1] dada porbel(A) = ∑B⊆A

__(−1)|B| Q(B) é a função de crença associada a essa

função de comunalidade:

∑B⊆A

__(−1)|B| Q(B) = ∑

B⊆A__

(−1)|B| ∑C

B⊆C

m(C)

= ∑C⊆Θ

m(C) ∑B⊆C ∩ A

__(−1)|B|

Pelo Lema 1,

∑C⊆Θ

m(C) ∑B⊆C ∩ A

__(−1)|B|

= ∑C

C ∩ A__

= ∅

m(C) = ∑C⊆A

m(A) = bel(A), para todoA⊆Θ

Pelo Lema 5, obtem-se diretamente:

Q(A) = ∑B⊆A

(−1)|B| bel( B__

)

Outra propriedade importante é dada pelo Teorema 4:

Teorema 4: SejamC o centro de uma função de crença sobreΘ e Q sua função de

comunalidade. Então um elementoθ∈Θ está em C se e somente seQ( θ )>0.

Prova do Teorema 4: ComoQ( θ ) = ∑B⊆Θθ∈B

m(B), Q( θ ) será positivo se e somente se for um

elemento focal, i.e., se e somente se estiver emC.


16

Uma vez que a função de comunalidade é não-incremental (B⊆A implicaQ(B)≥Q(A)),

segue da conclusão acima queQ(A) = 0 quandoA inclui um ponto fora do centroC. Mais

ainda, da relação entre função de crença e função de comunalidade, tem-se:

bel(∅) = 0 = ∑B⊆Θ

(−1)|B| Q(B) ou ∑A⊆ΘA ≠ ∅

(−1)|A|+1 Q(A) = 1

Outra observação importante é que seQ(A) = Kq(A), ondeK é uma constante positiva

eq : (2Θ− ∅ ) → [0,∞), é possível determinarK:

K =

∑A⊆ΘA ≠ ∅

(−1)|A|+1 q(A)

−1, pois ∑A⊆ΘA ≠ ∅

(−1)|A|+1 Kq(A) = 1

8 Plausibilidade de Uma Função de Crença

DadoA⊆Θ, o valorbel(A) pode não evidenciar totalmente o quanto se pode acreditar emA__

.

Uma descrição mais completa pode ser dada pelograudedúvida, denominadodou, definido

por:

dou(A) = bel( A__

)

O grau de dúvida é utilizado com menos frequência que a quantidade 1− bel( A__

),

denominadaplausabilidadede A (ouprobabilidadesuperiordeA), notada por℘l(A), que

fornece a quantidade máxima de crença que pode ser atribuída àA. Desde que

bel(A) + bel( A__

) ≤ 1, tem-se quebel(A) ≤ ℘l(A) para todoA⊆Θ. Pode-se também expressar

℘l(A) em termos da atribuição básica de probabilidadem como garante o teorema a seguir:

Teorema 5: Dada uma função de crençabel:2Θ → [0,1] e sua atribuição de probabilidade

básicam:2Θ → [0,1], a função℘l:2Θ → [0,1] dada por

℘l(A) = ∑B∩A≠∅

m(B)

é a função de plausibilidade.

Prova do Teorema 5: Para qualquerA⊆Θ, tem-se


17

℘l(A) = 1 − bel( A__

) = ∑B⊆Θ

m(B) - ∑B⊆A

__m(B) = ∑

B∩A≠∅

m(B)

Da definição de plausibilidade acima e da definição da função de comunalidade, dada

por Q(A) = ∑B⊆ΘA⊆B

m(B), tem-se que, para todo elemento particularθ deΘ,

℘l( θ ) = Q( θ )

9 Intervalos de Crença

Como visto na seção imediatamente anterior, a plausibilidade de uma dada hipóteseA,

℘l(A), representa o quanto é possível acreditar emA. Se bel(A) representa a crença atual em

A, e sabendo-se quebel(A)≤℘l(A), é natural que a informação contida na crença emA seja

mais convenientemente expressa pelo intervalo [bel(A),℘l(A)] ao invés debel(A) apenas.

Como será visto na Seção 10, com as funções de crença bayesianas (utilizadas pela teoria

de probabilidade clássica) ocorre quebel(A) = ℘l(A), resultando que o intervalo

[bel(A),℘l(A)] é degenerado, ou seja, possui um único ponto. Em geral, entretanto, isso não

ocorre na TDS. É desejável, portanto, que sistemas baseados na TDS ao fornecerem

informações de crença em uma dada hipótese ou evidência forneçam não somente o grau de

crença, mas o intervalo [bel(A),℘l(A)] que expressa a faixa de valores no qual é possível

acreditar emA, sem incorrer em erros graves de suposição. Esse intervalo recebe apropriada-

mente o nome deintervalodecrença, representado porℑ(A), e é tão mais amplo quanto mais

incerteza houver sobre a crença emA. Isso pode ser visualizado com clareza na função de

crença vacuosa (ver Seção 6, p. 8), onde todas as hipóteses primitivas possuem [0,1] como

intervalo de crença.

Exemplo 8: SejamA = s, B = a e C = s,a como no Exemplo 2, ondeΘ = a,i,s,r. Neste

caso, os intervalos de crença dessas hipóteses são:

ℑ(A) = [bel(A),℘l(A)] = [bel(A),1−bel(A)] = bel( s ),1−bel( a,i,r )] =

[0.2,1−(0.3+0.1)] = [0.2,0.6]

ℑ(B) = [bel(B),℘l(B)] = [bel(B),1−bel(B)] = bel( a ),1−bel( s,i,r )] =

[0.3,1−(0.2+0.1)] = [0.3,0.7]

ℑ(C) = [bel(C),℘l(C)] = [bel(C),1−bel(C)] = bel( s,a ),1−bel( i,r )] =

[(0.2+0.3+0.4),1−(0.1)] = [0.9,0.9]


18

A crença tanto emA quanto emB pode ser aumentada em 0.4 pontos, o que em ambas

representam um aumento maior que o dobro do grau de crença. A crença emC, entretanto

está em seu máximo, não sendo possível nenhum acréscimo, representando uma certeza que

a probabilidade deC ocorrer é 0.9.

10 Funções de Crença Bayseanas

Na literatura podem ser encontradas várias referências (ver por exemplo [Shafer (1976)] ou

[Shafer (1986)]) que abordam o relacionamento entre a TDS e a Teoria de Bayes. É fato que

o conceito de função de crença é suficientemente amplo, a ponto de permitir que os conceitos

da Teoria Bayesiana possam ser focalizados sob a perspectiva da TDS. Mais ainda, as

probabilidades bayesianas podem ser enquadradas como casos específicos das funções de

crença. São asfunçõesdecrençabayesianas.

Uma função de crençabel é dita bayesiana sebel(A∪B) = bel(A)+bel(B) para todo

A,B⊆Θ e A∩B = ∅. Em síntese, uma função de crença bayesiana usa a atribuição de

probabilidade básicam:2Θ → [0,1] tal que:

(i) m( θ ) = bel( θ ) para todoθ∈Θ

(ii) m(A) = 0 para para todoA⊆Θ que não seja conjunto unitário.

O próximo teorema prova várias equivalências envolvendo funções de crença bayesia-

nas.

Teorema 6: Seja uma função de crençabel:2Θ → [0,1] com plausibilidade

℘l(A):2Θ → [0,1] e comunalidadeQ:2Θ → [0,1]. As seguintes assertivas são todas equiva-

lentes entre si:

(1) bel é bayesiana

(2) os elementos focais debel são conjuntos unitários

(3) bel garante comunalidade zero para qualquer subconjunto contendo mais que um

elemento

(4) bel(A) = ℘l(A) para todoA⊆Θ

(5) bel(A)+bel(A__

) = 1 para todoA⊆Θ

Prova do Teorema 6:


19

w (1) ≡ (2): Segue diretamente do fato que a atribuição de probabilidade básica é nula

para conjuntos não unitários.

w (2) ≡ (3): Segue da relaçãoQ(A) = ∑B⊆ΘA⊆B

m(B), lembrando que se B possui mais que

um elemento, entãom(B) = 0.

w (2) ≡ (4): Segue da comparação entre as relaçõesbel(A) = ∑B⊆A

m(B) e

℘l(A) = ∑B∩A ≠ ∅

m(B) , lembrando que se B possui mais que um elemento, então

m(B) = 0.

w (4) ≡ (5): Segue da relação℘l(A) = 1−bel(A)

Uma outra propriedade importante das funções de crença bayesianas é que:

Teorema 7: Uma funçãobel:2Θ → [0,1] é uma função de crença bayesiana se existe uma

funçãoρ:Θ → [0,1] tal que:

∑θ ∈Θ

ρ(θ) = 1 ebel(A) = ∑ρθ ∈A

(θ)

Prova do Teorema 7: Tem-se

(i) bel(∅) = ∑ρθ ∈∅

(θ) = 0

(ii) bel(Θ) = ∑ρθ ∈Θ

(θ) = 1

(iii) quandoA∩B = ∅, A,B⊆Θ,

bel(A)+bel(B) = ∑ρθ ∈A

(θ)+∑ρθ ∈B

(θ) = ∑ρθ ∈A∪B

(θ) = bel(A∪B)

Pode ser verficado de forma trivial que a funçãoρ:Θ → [0,1] satisfazρ(θ) = m( θ ).

11 Combinação da Função de Crença

Como comentado em [Stein (1993)], o processo de acúmulo de evidências em diagnóstico

médico requer um método que combine o suporte a uma hipótese, ou à sua negação, com base

no acúmulo de múltiplas observações. Para propagar a crença a TDS combina diferentes


20

funções de crença, calculando sua soma ortogonal utilizando a regra de combinação de

Dempster.

A notaçãom1⊕m2 é usada para indicar os efeitos combinados de duas atribuições de

probabilidade básicam1 em2. A função de crença correspondente, notada porbel1⊕bel2, pode

ser calculada facilmente a partir dem1⊕m2.

Sem1 em2 são duas atribuições de probabilidades básicas em um domínio do problema

Θ, então sua soma ortogonal é definida por

m(∅) = 0

m1⊕m2(A) = χ∑X∩Y = A

A ≠ ∅

m1(X)×m2(Y), para todoA⊆Θ (II)

ondeχ é a constante de normalização, definida como1

1−κ, e κ é a soma dos bpa’s de todas

as ocorrências do conjunto∅. O conjunto vazio ocorre quando se tenta combinar hipóteses

disjuntas - indicativa que existem evidências que suportam hipóteses que estão em conflito,

uma com a outra.

A comutatividade da multiplicação garante que (II) produz o mesmo valor e independe,

assim, da ordem na qual as funções são combinadas - isso é muito importante uma vez que a

agregação de evidências deve ser independente da ordem na qual ela acontece. A prova que

m1⊕m2 é uma atribuição básica de probabilidade, sendo possível portanto o cálculo de

bel1⊕bel2 é verificada pelo teorema abaixo:

Teorema 8: Sem1 e m2 são duas atribuições de probabilidades básicas em um domínio do

problemaΘ, com

∑m

Ai∩Bi = ∅1(Ai)m2(Bj) < 1

então sua soma ortogonalm1⊕m2 definida por

m(∅) = 0

m1⊕m2(A) = χ∑X∩Y = A

A ≠ ∅

m1(X)×m2(Y), para todo não vazioA⊆Θ

ondeχ é a constante de normalização, definida como1

1−κ, e κ é a soma dos bpa’s de todas

as ocorrências do conjunto∅, é um bpa.


21

Prova do Teorema 8: É trivial a demonstração quem1⊕m2 satisfaz as duas primeiras

condições de uma atribuição de probabilidade básica. Fazendo-sem = m1⊕m2, para simplifi-

cação de notação, resta a prova que∑A∈2

Θ

m(A) = 1. Mas,

∑A∈2

Θ

m(A) = ∑A⊆Θ

m(A) = m(∅) + ∑A⊆ΘA ≠ ∅

m(A) = χ∑X∩Y = A

A ≠ ∅

m1(X)×m2(Y) =

=1

1−κ ∑X∩Y= A

A ≠ ∅

m1(X)×m2(Y) =1

1−κ ∑X∩Y ≠ ∅

m1(X)×m2(Y)

Tem-se, pela definição queκ = ∑X∩Y = ∅

m1(X)×m2(Y). O que, por sua vez pode ser escrito como

κ = 1 − ∑X∩Y ≠ ∅

m1(X)×m2(Y)

Voltando-se à equação anterior, obtém-se

11−κ ∑

X∩Y≠ ∅

m1(X)×m2(Y) =1

1 −

1 − ∑X∩Y ≠ ∅

m1(X)×m2(Y)

∑X∩Y ≠ ∅

m1(X)×m2(Y) =

=1

∑X∩Y ≠ ∅

m1(X)×m2(Y)∑

X∩Y ≠ ∅

m1(X)×m2(Y) = 1

Pode ser verificado trivialmente que o centro da função de crençabel1⊕bel2 dada por

m1⊕m2 é igual à intersecção dos centros debel1 ebel2. Quando∑m

Ai∩Bi = ∅1(Ai)m2(Bj) < 1 não vale,

diz-se quebel1⊕bel2 não existe, isto é, não é possível combinarbel1 e bel2 utilizando-se a

regra de combinação de Dempster. Também pode ser verificado que, seQ1 e Q2 são as

funções de comunalidade associadas abel1 e bel2, então a combinação deQ1 e Q2,

representada porQ1⊕Q2, é dada por Q1⊕Q2(A) = χQ1(A)Q2(A) para qualquer não vazio

A⊆Θ.

Exemplo 9: Considere novamente o frame de discernimentoΘ = alergia, intoxicação,

rubéola, sarampo (resumidamenteΘ = a,i,s,r) e suponha que, para um certo paciente, uma

determinadam1 observação indique alergia, intoxicação (resumidamente a,i), com grau


22

0.5, enquanto que uma outram2 desconfirmando alergia com grau 0.6 (i. e., confirma a

hipótese i, r, s). A rede de crença, baseada em ambas observações, é dada porm1⊕m2 e é

representada na Tabela 1:

Tabela 1

Rede de crenças param1 em2

Então,

m1⊕m2 (i) = 0.30

m1⊕m2 (i, r, s) = 0.30

m1⊕m2 (a, i) = 0.20

m1⊕m2 ( Θ) = 0.20

m1⊕m2 = 0 para quaisquer outros subconjuntos deΘ

Obs.: Note que nesse exemploχ = 1 uma vez queκ = 0

A partir da Tabela 1 pode-se então calcularbel1⊕bel2 , para todos os elementos de 2Θ.

Por exemplo,

bel1⊕bel2(a, i) = m1⊕m2(a, i) + m1⊕m2(a) + m1⊕m2(i) = 0.2 + 0 + 0.3 = 0.5

Exemplo 10: Suponha agora que para o mesmo paciente do exemplo anterior, uma terceira

evidência confirma o diagnóstico de alergia com grau 0.8. Pela TDS deve-se agora calcular

m3⊕m4, ondem4 = m1⊕m2 do exemplo anterior

m2

m1

i,r,s (0.6) Θ (0.4)

a,i (0.5)

Θ (0.5)

i (0.3) a,i (0.2)

i,r,s (0.3) Θ (0.2)


23

Tabela 2

Rede de Crenças param3 em4

Como neste exemplo o conjunto∅ foi obtido duas vezes com valor de crença 0.24,

κ = 0.24 + 0.24 = 0.48 e 1 -κ = 0.52

Então,

m3⊕m4(a) = (0.16 + 0.16) / 0.52 = 0.615

m3⊕m4(i) = 0.06 / 0.52 = 0.115

m3⊕m4(i, r, s) = 0.06 / 0.52 = 0.115

m3⊕m4(a, i) = 0.04 / 0.52 = 0.077

m3⊕m4( Θ ) = 0.04 / 0.52 = 0.077

m3⊕m4= 0 para quaisquer outros subconjuntos deΘ

Obs.: Note que nesse exemplo∑ m3⊕m4 = 1, como requer a definição de um bpa.

Na proxima seção serão abordados alguns problemas que podem surgir ao combinar

funções de crença, bem como evidenciar situação em que essa combinação é possível.

12 Peso de Conflito

Como definido anteriormente,χ = 11−κ

, ondeκ é a soma dos bpa’s de todas as ocorrências

do conjunto∅, cujas ocorrências se devem à combinação de hipóteses disjuntas. O valor

log(χ)1 é denominadopesode conflito entrebel1 e bel2 denotadocon(bel1,bel2). Sebel1 e

bel2 não se conflitam em nada (como no exemplo 9, acima), entãoκ = 0 econ(bel1,bel2) = 0.

m4

m3

i,r,s (0.3)a,i (0.2)

a,i (0.04)

i (0.3)

i (0.06)

Θ (0.2)

a (0.8)

Θ (0.2)

a (0.16) a (0.16)

i,r,s (0.06) Θ (0.04)

∅ (0,24) ∅ (0,24)


24

1. Neste relatório, estamos considerandos logarítmos de base 10. Em verdade, o peso de conflito poderia ser definido paraqualquer base positiva maior que 1 (logaritmos naturais, por exemplo).

Por outro lado, sebel1 ebel2 não possuem nenhuma evidência em comum, ou seja a união de

todas as intersecções de suas evidências é o conjunto vazio (hipótese nula), entãoκ = 1 e

con(bel1,bel2) = ∞. Em tais condições, a combinaçãobel1⊕bel2 não é possível. O teorema

abaixo determina quando não é possível combinarbel1 e bel2 utilizando-se a regra de

combinação de Dempster:

Teorema 9: Sejambel1 e bel2 funções de crença sobre o mesmo domínioΘ, e sejamQ1 e

Q2 as funções de comunalidade associadas, respectivamente, abel1 e bel2. As seguintes

condições são equivalentes:

(1) bel1⊕bel2 não existe

(2) os centros debel1 ebel2 são disjuntos

(3) existe um subconjuntoA⊆Θ tal quebel1(A) = 1 ebel2(A__

) = 1

(4) Q1(A)Q2(A) = 0 para todo não-vazioA⊆Θ

Prova do Teorema 9:

w (1) ≡ (2) SejamAi e Bj os elementos focais debel1 e bel2, respectivamente. Tem-se

quem1(Ai)m2(Bj) > 0 para todoi e j. E, portanto,

∑i,j

m1(Ai)m2(Bj) = ∑i

m1(Ai) × ∑j

m2(Bj) = 1

Donde∑i,j

Ai∩Bj = ∅

m1(Ai)m2(Bj) < 1 falha se e somente seAi∩Bj = ∅ para todoi,j.

SeC1 eC2 denotam os centros debel1 ebel2, respectivamente, então:

C1∩C2 = ∪

i

Ai

∩ ∪j

Bj

= ∪(Ai∩Bj)i,j

Dessa forma,Ai∩Bj = ∅ para todoi,j se e somente seC1∩C2 = ∅

w (2) ≡ (3) Tem-se quebel1(A) = bel2(A__

) = 1 se e somente seC1⊆A e C2⊆A__

, isto é,

C1∩C2 = ∅

w (2) ≡ (4) Uma função de crença garante comunalidade positiva não-nula para con-juntos unitários somente se estes estão contidos no centro dessa função. Então, seC1∩C2 ≠ ∅, Q1(θ)Q2(θ) > 0 para qualquerθ∈C1∩C2. CasoC1∩C2 = ∅, todo não-

vazioA⊆Θ, desde que não é subconjunto deC1 eC2 ao mesmo tempo, irá satisfazer


25

Q1(A) = 0 ou Q1(A) = 0. Portanto,Q1(A)Q2(A) = 0 para todo não-vazioA⊆Θ se e

somente seC1∩C2 = ∅

Este teorema pode ser estendido facilmente a várias funções de crença:

Teorema 10: Sejambel1, bel2,..., beli,..., beln funções de crença sobre o mesmo domínio

Θ, e sejamQ1, Q2,..., Qi,..., Qn as funções de comunalidade associadas, respectivamente, a

bel1, bel2,..., beli,..., beln. As seguintes condições são equivalentes:

(1) bel1⊕bel2⊕…⊕beli⊕…⊕beln não existe

(2) os centros debel1, bel2,..., beli,..., beln são disjuntos

(3) existem subconjuntosA1,A2,…,Ai,…,An⊆Θ tal queA1∩A2∩…∩Ai∩…∩An = ∅,

masbeli(Ai) = 1 para todoi∈1,…,n

(4) Q1(A)×Q2(A)×…×Qi(A)×…×Qn(A) = 0 para todo não-vazioA⊆Θ

A demonstração deste teorema segue o modelo anterior, e é deixado como exercício.

Em alguns casos, mesmo sendo possível a combinação de duas funções de crença

utilizando-se da regra de Dempster, o resultado pode não ser o esperado, sendo até mesmo

contrário à intuição. Nesses casos, entretanto, o peso do conflito fornece dados fundamentais

sobre a combinação dessas crenças. Pode ser verificado que quando o peso de conflito é

superior a 0.6, por exemplo, os resultados são altamente indesejáveis.

Exemplo 11: Suponha que dois doutores examinem um paciente e concordam que ele sofre

ou de meningite (M), ou de concussão (C) ou de tumor cerebral (T). Ou seja,Θ = M,C,T.

No entanto discordam quanto ao diagnóstico. Para o primeiro médico as atribuições de

probabilidades básicas deveriam ser:

m1( M ) = 0.9 e m1( T ) = 0.1

enquanto para os segundo seriam:

m1( C ) = 0.8 e m1( T ) = 0.2

A rede de crenças que combina essas duas atribuições é dada pela Tabela 3:


26

Tabela 3

Rede de crenças param1 em2

Neste caso,κ = 0.72+0.08+0.18= 0.98 o que dá

χ = 11−κ

= 10.2

= 5 econ(bel1,bel2) = log(5) ≅ 0.699

Observe que, temosm1⊕m2(T) = 1, o que não é um resultado esperado pela intuição.

De uma forma geral, não é desejável a combinação de duas funções de crença quando

κ for muito maior que a metade, pois indica que as duas crenças estão mais em conflito do

que concordância. Impondo um valor limite paraκ é possível determinar um máximo para o

peso de conflito. Por exemplo, se for imposto queκ < 0.75, tem-se que não é possível

combinar corretamente quando o peso de conflito for maior que 0.6. Um valor mais restritivo

ainda, tal comoκ < 0.7 acarreta a impossibilidade de se combinar corretamente quando o peso

de conflito for maior que 0.5.

Alguns autores sugerem novas formas de combinação que não a regra de Dempster. Por

exemplo, Walley em [Walley (1996)] sugere que sejam combinadas por extensão natural. No

entanto seu artigo não deixa suficientemente claro o funcionamento da extensão natural, em

parte por usar notação e resultados advindos dos trabalhos de probabilidades inferiores e

superiores, que não fazem parte das pesquisas que motivaram este relatório. Wang em [Wang

(1994)] sugere uma nova abordagem para a TDS, utilizando frequências inferiores e supe-

riores. Como sua abordagem utiliza conceitos avançados da TDS, foge aos objetivos deste

trabalho.

13 Avaliando a TDS com os critérios de Walley

Como adiantado anteriormente, é possível a análise da TDS de acordo com os critérios

de Walley [Walley (1996)], discutidos na Seção 2. Comentários sobre a TDS, focalizados sob

os seis critérios estão na Tabela 4:

m1

m2

T (0.1)

T (0.02)

M (0.9)

C (0.8)

T (0.2)

∅ (0,72)

∅ (0,18)

∅ (0,08)


27

Critério Avaliação

Interpretação

As funções de crença permitem rápida compreensão, o que facilita o fornecimento deinformação ao usuário. Sua estrutura é, sob certos aspectos, semelhante ao de Fatoresde Certeza, o que tem inclusive levado a sugestões de utilização da TDS no MYCIN(ver, por exemplo [Gordon-Shortliffe (1984)] ). A TDS teria vantagens sobre os Fatoresde Certeza por possuir uma rigorosa estrutura matemática. Quando expressa porintervalos de crença, os resultados são ainda melhores.

ImprecisãoA TDS permite a representação de ignorância (parcial ou total) e conflito. No entanto,cuidado especial deve ser dado à combinação de crenças altamente conflitantes, poispode levar a resultados contra-intuitivos.

Cálculo

A regra de Dempster permite a combinação de funções de crença, desde que essas nãosejam muito conflitantes. Alguns autores sugerem alternativas nesse caso (por exemplo[Walley (1996)] e [Wang (1994)]). Na maioria das situações, entretanto, a regra deDempster produz resultados altamente satisfatórios.

ConsistênciaO peso de conflito permite verificar se a combinação de duas ou mais crenças produziráresultados indesejáveis.

DeclaraçãoNão há ainda procedimentos seguros que guiem o processo de declaração de crenças, oque pode introduzir agravantes ao sistema.

Computação

Como a TDS utiliza um grande número de hipóteses (maior que na Teoria de Bayes),o cálculo computacional pode ser extremamente penoso. No entanto, por não precisarde probabilidades condicionais e como uma evidência em geral foca apenas um pequenonúmero do total das hipóteses, o cálculo pode ser bastante simplificado, pois a TDS nãoprecisa indicar crença nula. Outro problema ainda em questionamento é o de como ascrenças devem ser propagadas.

Tabela 4

Avaliação da TDS de acordo com os critérios de Walley em[Walley (1996)]

14 Conclusões

Uma questão pertinentes à TDS é o significado que ela dá aos termos “acaso” (ou possibili-

dade)2 e “crença3”. Para muitos matemáticos e para a maioria das pessoas, as duas idéias são

abordadas com o nome de “probabilidade”. A TDS rejeita essa unificação, conforme Shafer

em [Shafer (1976), p. 9]:

muito dos graus numéricos de crença estudados aqui não são possibidades e nãoobedecem todas as regras obedecidas pelo acaso. (...) Possibilidades surgem quandoalguém descreve um experimento aleatório ou randômico, como o rolar de um dadoou o atirar de uma moeda. O resultado de tal experimento varia randomicamente entreexperimentos fisicamente independentes.


28

2. O termo em inglês é chance, traduzido por possibilidade ou acaso. Nesse relatório foram utilizadas as duas traduções,conforme o contexto.

3. Em inglês,belief.

Dessa forma, os graus de possibilidade governando um experimento aleatório pode ou

não coincidir com os nossos graus de crença sobre o resultado desse experimento. Como

afirma Shafer em [Shafer (1976), p.16]:

Se conhecemos as possibilidades, então podemos seguramente adotá-las como grausde crença. Mas se nós não conhecemos as possibilidades, então será uma extraordi-nária coincidência nossos graus de crença serem iguais a ela.

Além disso, a TDS permite expressar ignorância parcial e total de forma extremamente

adequada, ao contrário da Teoria de Bayes que expressa ignorância parcial atribuindo-se

crença à negação da hipótese e ignorância total dividindo-se o total da crença entre as hipóteses

presentes (eventualmente, atribuindo mais crença do que realmente possuem).Outra diferença

importante entre a TDS e a Teoria de Bayes é modo como novas evidências são adicionadas

ao sistema. Na Teoria de Bayes, a ordem com que as evidências são apresentadas pode influir

no resultado, além de que cada nova evidência é expressa como certeza. Na TDS, as funções

são combinadas utilizando-se da regra de Dempter, conforme exposto na Seção 10. Essa regra

garante que o resultado da combinação não depende da ordem da apresentação das evidências

e nem necessita que estas expressem certeza. Dessa forma, como afirma Shafer em [Shafer

(1976), p. 27]:

Desde que não se requira que expressemos nossa evidência como uma certeza, a regrade combinação de Dempster permite-nos construir descrições de raciocínio provávelque são mais modestos que descrições bayesianas, mas mais fidedigno à formahumana de pensar.

Além disso, cabe relembrar que, quando da implementação de sistemas que utilizam a

TDS, é importante que sejam dadas devidas atenções para o intervalo de crença, bem como

analisar o peso de conflito ao se combinar funções de crença. Isto garantirá maior segurança

nas decisões, bem como fornecerá maior informação sobre as hipóteses e evidências em

análise.

Esse trabalho terá continuidade com a análise da Teoria de Conjuntos Aproximados

[Pawlak (1982), Uchôa & Nicoletti (1997)], que é muitas vezes utilizada para a representação

de incerteza, sob a perspectiva da TDS (ver [Yager et alii (1994)]).

15 Bibliografia

[Bonissone (1991)] Bonissone, P. Plausible reasoning. In: Shapiro, S. C. ; Eckroth, D. &

Valassi, G. A. (eds.)Encyclopedia of Artificial Intelligence.New York, John Wiley

& Sons, 1991. p. 854-863.

[Dempster (1967)] Dempster, A. P. Upper and Lower Probabilities Induced by a Multivalued

Mapping.Annals Mathematics Statistics, 38, 1967, p. 325-339.


29

[Dempster (1967a)] Dempster, A. P. Upper and Lower Probability Inferences Based on a

Sample from a Finite Univariate Population.Biometrika, 54, 1967, pp. 515-528.

[Duda et alii (1976)] Duda, R. O.; Hart, P. E. & Nilsson, N. J. . Subjective bayesian methods

for rule-based inference systems. In:AFIPS Conference Proceedings, N.Y., June

1976, p. 1075-1082.

[Gordon & Shortliffe (1984)] Gordon, J. & Shortliffe, E. H. The Dempster-Shafer Theory

of Evidence. In:Rule-based expert systems.New York, Addison-Wesley, 1984.p.

272-292.

[Ng & Abramsom (1990)] Ng, K.C. & Abramsom, B. Uncertainty management in expert

systems.IEEE Expert, April 1990, p. 29-47.

[Pawlak (1982)] Pawlak, Z. Rough sets.International Journal of Computer and Information

Sciences, 11(5), 1982, p. 341-356.

[Pearl (1982)] Pearl, J. Reverend Bayes on inference engines: a distributed hierarchical

approach. In:Proceedings of the Second National Conference on Artificial Intelli-

gence, Pittsburgh, PA, 1982, p. 133-136.

[Reiter (1980)] Reiter, R. A Logic for Default Reasoning.Artificial Intelligence13, 1980,

pp. 81-132.

[Shafer (1976)] Shafer, G.A mathemathical theory of evidence. Princeton, Princeton

University Press, 1976.

[Shafer (1986)] Shafer. G. Probability Judgement in Artificial Inteligence. In: Kanal, L. N. &

Lemmer, J. F. (eds.).Uncertainty in Artificial Inteligence. North-Holland, Elsevier

Science Publishers, 1986. p. 127-135.

[Shortliffe & Buchanan (1975)] Shortliffe, E. H. & Buchanan, B. G. A Model of Inexact

Reasoning in Medicine.Math. Biosci., 23, 1975, p. 351-379.

[Stein (1993)] Stein, R. The Dempster-Shafer Theory of Evidential Reasoning.AI Expert,

August 1993, p. 26-31.

[Uchôa & Nicoletti (1997)] Uchôa, J. Q. & Nicoletti, M.C.Elementos da teoria de conjuntos

aproximados.Relatório Técnico do Departamento de Computação 001/97. São

Carlos, DC-UFSCar, 1997.


30

[Walley (1996)] Walley, P. Measures of uncertainty in expert systems.Artificial Inteli-

gence83, 1996, p. 1-58.

[Wang (1994)] Wang. P.A defect in Dempster-Shafer theory. Technical Report N. 85 of

CRCC. Indiana, Indiana University, 1994.

[Yager et alii (1994)] Yager, R. R.; Fedrizi, M. & Kacprzyk, J.Advances in the Dempster-

Shafer theory of evidence.New York, John Wiley & Sons, 1994.

[Zadeh (1978)] Zadeh, L. A. Fuzzy Sets as a Basis for a Theory of Possibility. In:Fuzzy

Sets and Systems1, 1978, pp 3-28.


31

Documents

Elementos da Teoria de Evidência de Dempster-Shafer