Elementos da Teoria de Evidência de Dempster

Transcrição

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, carmo}@dc.ufscar.br
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, plausibilidade, 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
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-Shafer
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, parcialmente ignorados e mesmo incompletos. Como comentado em [Bonissone (1991), p.854],
a presença da incerteza em sistemas baseados em conhecimento pode se originar de
várias fontes: da confiabilidade parcial que se tem na informação, da imprecisão
inerente à linguagem de representação na qual a informação é expressa, da não
completeza da informação e da agregação/sumarização da informação que provêm
de 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 abordagens ad 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, qualquer
sistema robusto de inferência lógica poderia ser utilizado para a extração de conclusões válidas.
Entre as abordagens mais tradicionais existentes para a modelagem e tratamento de
incertezas, encontram-se:
w
w
w
w
w
w
w
w
regra de Bayes [Pearl (1982)]
regra de Bayes modificada [Duda (1976)]
fator de certeza [Gordon & Shortliffe (1975)], baseada em teoria da confirmação
teoria de Dempster-Shafer [Dempster (1967), Shafer (1976)]
teoria da possibilidade [Zadeh (1978)]
raciocínio default [Reiter (1980)]
teoria de endorsements [Cohen (1985)]
teoria de conjuntos aproximados [Pawlak (1982)]
 1 
Este trabalho apresenta e discute os principais elementos da Teoria 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 significado 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ções default. 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á na
habilidade deste método em modelar o afunilamento do conjunto de hipóteses, à
medida em que se acumulam evidências; este procedimento reflete o processo que
caracteriza 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 denominadas singletons, 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 se
algumas inferências gerais a respeito do que cada evidência implica puderem ser
feitas, a TDS permite que essas evidências possam ser combinadas de uma maneira
consistente e probabilística, para se estabelecer o que o conjunto de evidências
considerado 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 de domínio do problema ou
frame de discernimento, ou ainda quadro de discernimento e é 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 de reação orgânica, definida no exemplo como o conjunto
{alergia, intoxicação}, ou então
w para um diagnóstico de infecçã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óstico reaçã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.
{a,i,s,r}
{a,i,r}
{a,i,s}
{a,s}
{a,i}
{a}
{a,s,r}
{a,r}
{i,s}
{i}
{i,s,r}
{i,r}
{s}
{s,r}
{r}
Figura 1
Conjunto de todas as possíveis hipóteses obtidas do conjunto de hipóteses
primitivas Θ = a,i,s,r






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 é |Ω|.
 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 chamada atribuição de probabilidade básica (bpa - do
inglês basic probability assignment), ou função de massa.
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 subconjuntos de Θ, a bpa notada por m atribui 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 quantidade m(A) é a medida daquela parte da crença
total, que é atribuída exclusivamente à A, onde A é qualquer elemento de 2Θ e a crença total
sendo 1. Essa parte da crença m(A), não pode ser subdividida posteriomente entre os
subconjuntos de A e não inclui parte da crença atribuída a subconjuntos de A [Gordon &
Shortliffe (1984)]. Formalmente, se Θ é um domínio de problema, então m:2Θ → [0,1] é
chamada de atribuição básica de probabilidade (bpa) se satisfaz:
1. m(∅) = 0
2. m(A) ≥ 0, ∀ A∈2Θ
3.
∑m(A) = 1
A∈2
Θ
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 de crença não atribuída,
notada por m(Θ). Se m(A) = x e m nã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ótese A, 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 indicando 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. Assim m({a, r, i}) = 0.7,
m(Θ) = 0.3 e o valor de m 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ão m({sarampo}) = 0.6, m(Θ) = 0.4 e m é zero em qualquer outro conjunto.
A TDS permite que o peso de 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ção de crença, denotada bel, correspondente a uma determinada função de atribuição
de probabilidade m, atribui a todo subconjunto A de Θ, a soma das probabilidades básicas
atribuídas a todo subconjunto de A, por m. A quantia m(A) mede a crença que se atribui
exatamente a A e não o total de crença que se atribui a A. Para se obter a medida do total de
crença atribuído a A, deve-se adicionar à m(A) os valores m(B), para todo subconjunto próprio
B de A:
bel(A) = ∑m(X)
(I)
X⊆A
Uma função bel:2Θ → [0,1] é chamada de função de crença sobre Θ se ela for dada por
(I), relativa a alguma atribuição de probabilidade básica m:2Θ → [0,1].
Com certeza a função de crença com estrutura mais simples é aquela obtida fazendo
m(Θ) = 1 e m(A) = 0 para todo A ≠ Θ. Ela tem bel(Θ) = 1 e bel(A) = 0 para todo A ≠ Θ. Desde
que essa função de crença parece apropriada quando não se tem evidências, ela é chamada de
função de crença vacuosa. 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ão bel: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 positivo n, e toda coleção A1,..., An de subconjuntos de Θ,
 8 
bel(A1∪…∪An) ≥
∑bel(Ai)
−
i
∑bel(Ai∩Aj)
∑bel(Ai∩Aj∩Ak)
+
i<j
− … +
i<j<k
(−1)n+1bel(A1∩…∩An)
∑(−1)|I|+1bel(∩Ai)
=
I ⊆ {1,..., n}
i∈I
I≠∅
Para a prova deste teorema é importante primeiro provar os seguintes resultados:
∑(−1)|B|
Lema 1: Se A é um conjunto finito, então
B⊆A
1,
= 
0,
se A = ∅
caso contrário
Prova do Lema 1: O binômio de Newton garante que se x e a são números reais e n é um
n
n
n
inteiro positivo, então (x + a) = ∑   akxn−k, onde   representa o número possível de
k
k 
 
k=0
n
combinações de n elementos tomados k a k. Fazendo-se x = 1 e a = −1, tem-se
0 = (1−1)n =
n
n
n
n
=   (−1)0(1)n−0 −   (−1)1(1)n−1 +   (−1)2(1)n−2 + … +   (−1)n(1)0 =
0
1
2
 
 
 
n
n
n
n
n
=   −   +   − … + (−1)n 
0
1
2
     
n
w quando A = {a1,...,an},
∑(−1)
|B|
=
B⊆A
= (−1)|∅| +
∑(−1)
|{ai}|
∑(−1)
|{ai,aj}|
+
i
= (−1)0 +
+
i<j
∑(−1)
1
i
+
∑(−1)
|{ai,aj,ak}|
+ … + (−1)|A| =
i<j<k
∑(−1)
2
+
i<j
∑(−1)
3
+ … + (−1)n =
i<j<k
n
n
n
n
=   −   +   − … + (−1)n  = 0
0
1
2
     
n
w quando A = ∅,
∑ (−1)
|B|
= (−1)|A| = 1
B⊆A
 9 
Então, dada uma atribuição básica de probabilidade m, a função bel:2Θ → [0,1] definida
como bel(A) = ∑ m(X) é uma função de crença.
X⊆A
Prova do Teorema 1: Se a função de crença é dada por α, para alguma atribuição de
probabilidade básica m, 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) = m(∅) = 0
B⊆∅
2. bel(Θ) = ∑m(B) = 1
B⊆Θ
Para prova da condição (3), considere Ai,..., An uma família fixa de subconjuntos de
Θ e seja I(B) = {i | 1≤ i ≤n; B⊆Ai} para cada B⊆Θ:
∑(−1)|I|+1bel∩Ai
I ⊆ {1,..., n}
i∈I 
I≠∅
∑
(−1)|I|+1
∑ m(B) ,


I ⊆ {1,..., n} 
B⊆ ∩Ai


 i∈I 
I≠∅




=
pela definição de função de crença. Mas, fazendo-se ∩Ai = AI para simplicidade de notação,
 i∈I 


a seguinte igualdade é obtida com rearranjamento dos termos:
∑
(−1)|I|+1
m(B) = ∑ m(B) ∑ (−1)|I|+1 ,
∑



I ⊆ {1,..., n} 
B⊆ AI
B⊆Θ 
I ⊆ I(B)



I≠∅
I(B) ≠ ∅
I≠∅


Simplificando a última expressão, tem-se:
∑
m(B)
∑ (−1)|I|+1 = ∑ m(B)


B⊆Θ 
I ⊆ I(B)
B⊆Θ 



I(B) ≠ ∅
I≠∅
I(B) ≠ ∅



=
∑
m(B)

B⊆Θ 
I(B) ≠ ∅
1|∅| − 1|∅| +
∑ (−1)|I|+1 =



I ⊆ I(B)


I≠∅


1 +
(−1)|I|+1 = ∑ m(B)
∑



I ⊆ I(B)
B⊆Θ 


I(B) ≠ ∅
=
∑
m(B)

B⊆Θ 
I(B) ≠ ∅
1 +
(−1)|I| (−1)1 =
∑


I ⊆ I(B)


1 −
∑ (−1)|I|

I ⊆ I(B)


Utilizando o Lema 1 sabendo que I(B) ≠ ∅, tem-se que:
 10 
∑ (−1)|I| = 0
I ⊆ I(B)
donde
∑
m(B) 1 −
(−1)|I| = ∑ (m(B) (1 − 0)) =
∑



B⊆Θ 
I ⊆ I(B)
B⊆Θ


I(B) ≠ ∅
∑ m(B)
I(B) ≠ ∅
=
∑ m(B)
≤
∑ m(B)
B⊆Θ
B⊆Θ
B⊆Θ
I(B) ≠ ∅
B⊆Ai, algum i
B⊆Ai∪…∪An
=
bel(Ai∪…∪An)
__
Dado A⊆Θ, bel(A) + bel(A) ≤1, pois:
__
__
__
1 = bel(Θ) = bel(A∪A) ≥ bel(A) + bel(A) − bel(A∩A),
__
__
uma vez que A∩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
todo A⊆Θ.
É importante notar também que bel e m têm o mesmo valor em cada uma das hipóteses
primitivas e que bel é maior ou igual a m em conjuntos que contém mais do que um elemento,
ou seja, se A⊆Θ não for uma hipótese primitiva, então bel(A) é a soma dos valores de m para
todo subconjunto na subárvore que tem A 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: Se A é um conjunto finito e B⊆A, então
(−1)|A|,
|C|
(−1)
=
∑

 0,
C
se A = B
caso contrário
B⊆C⊆A
Prova do Lema 2: segue diretamente do Lema 1 e do fato que
 11 
∑ (−1)
|C|
=
C
∑ (−1)
|B∪D|
=
D⊆(A − B)
∑ (−1)
|B|
(−1)|D| = (−1)|B|
D⊆(A − B)
∑ (−1)
|D|
D⊆(A − B)
B⊆C⊆A
Tem-se duas situações
(i)
A = B, o que, pelo Lema 1 garante:
(−1)|B|
∑ (−1)
|D|
= (−1)|B|1 = (−1)|B| = (−1)|A|,
D⊆(A − B)
pois A − B = ∅.
(ii)
A ≠ B, o que, pelo Lema 1 garante:
(−1)|B|
∑ (−1)|D| = (−1)|B|0 = 0,
D⊆(A − B)
pois A − B ≠ ∅.
Lema 3: Seja Θ um conjunto finito e f e g funções em 2Θ. Então:
f(A) =
∑ g(B)
para todo A⊆Θ
B⊆A
se e somente se
g(A) =
∑ (−1)|A − B| f(B)
para todo A⊆Θ.
B⊆A
Prova do Lema 3: Segue do Lema 2. Se f(A) =
∑ g(B)
para todo A⊆Θ, então
B⊆A
∑ (−1)|A − B| f(B)
B⊆A
= (−1)|A| ∑ (−1)|B| f(B) = (−1)|A| ∑ (−1)|B| ∑ g(C)


B⊆A
B⊆A
C⊆B

Mas,
(−1)|A| ∑ (−1)|B| ∑ g(C) = (−1)|A| ∑ g(C) ∑ (−1)|B|



B
B⊆A
C⊆B
C⊆A



C⊆B⊆A


com simples rearranjo dos termos. Utilizando-se do Lema 2, tem-se
(−1)|A| ∑ g(C) ∑ (−1)|B| = (−1)|A| g(A) (−1)|A| = g(A) para todo A⊆Θ.

B
C⊆A


C⊆B⊆A


 12 
Por sua vez, se g(A) =
∑ (−1)|A − B| f(B)
para todo A⊆Θ, então:
B⊆A
∑ g(B)
B⊆A
=
∑ ∑ (−1)|B − C| f(C)
B⊆A C⊆B
=

∑ (−1)|C| f(C) ∑ (−1)|B|
C⊆B


B
C⊆B⊆A



=
(−1)|A| f(A) (−1)|A| = f(A) para todo A⊆Θ.
Teorema 2: Suponha bel:2Θ → [0,1] é a função de crença dada pela atribuição de probabilidade básica m:2Θ → [0,1]. Então, para todo A⊆Θ:
m(A) = ∑(−1)|A−B|bel(B)
B⊆A
Prova do Teorema 2: seja bel:2Θ → [0,1] é a função de crença dada pela atribuição de
probabilidade básica m:2Θ → [0,1]:
bel(A) = ∑ m(X), para todo A⊆Θ
X⊆A
Aplicando-se diretamente o Lema 3, tem-se:
m(A) = ∑(−1)|A−B|bel(B), para todo A⊆Θ
B⊆A
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 de elemento 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 seu núcleo (ou centro). No Exemplo 2, dado que m({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. Se C for o centro de uma função de
crença bel sobre Θ, então B⊆Θ satisfaz bel(B) = 1 se e somente se C⊆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,
dado A⊆Θ, pode ser de interesse representar a massa de probalidade total que pode ser movida
 13 
para os pontos de A. A essa quantia, dá-se o nome de número de comunalidade de A,
representada por Q(A), e à função que calcula o número de comunalidade para todo A⊆Θ,
dá-se o nome de função de comunalidade. Pela definição, tem-se então que a função de
comunalidade é uma função Q : 2Θ→[0,1] tal que:
Q(A) =
∑ m(B)
B⊆Θ
A⊆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: Sejam A = {s}, B = {a} e C = {s,a} como no Exemplo 2. Neste caso, a atribuição
de probabilidade básica em A e B poderia ser acrescida com o refinamento da atribuição básica
em C. Isso pode ser expresso pelas comunalidades de A e B, maiores que as respectivas
atribuições de probabalidade básica:
Q(A) = ∑ m(X) = m(A)+m(C) = 0.2+0.4 = 0.6 e
X⊆Θ
A⊆X
Q(B) = ∑ m(X) = m(B)+m(C) = 0.3+0.4 = 0.7
X⊆Θ
B⊆X
Facilmente percebe-se que Q(∅) = 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 sejam f e g funções em 2Θ. Então:
∑ (−1)|B|+1 g(B)
f(A) =
para todo A⊆Θ
B⊆A
se e somente se
g(A) =
∑ (−1)|B|+1 f(B)
B⊆A
 14 
para todo A⊆Θ.
∑ (−1)|B|+1 g(B)
Prova do Lema 4: Se f(A) =
vale para todo A⊆Θ, então
B⊆A
∑ (−1)|B|+1 f(B)
=
∑ (−1)|B|+1 ∑ (−1)|C|+1 g(C)
B⊆A
B⊆A
=

C⊆B
∑ (−1)|C| g(C) ∑ (−1)|B|
C⊆A
B


C⊆B⊆A



Utilizando o Lema 2, tem-se
∑ (−1)|C| g(C) ∑ (−1)|B|
C⊆A





B
C⊆B⊆A
A demonstração de que, se g(A) =
= g(A) para todo A⊆Θ.
∑ (−1)|B|+1 f(B)
vale para todo A⊆Θ, então
B⊆A
f(A) =
∑ (−1)|B|+1 g(B)
para todo A⊆Θ é trivial e segue o modelo acima.
B⊆A
Lema 5: Seja Θ e sejam f e g funções em 2Θ. Então:
f(A) =
∑__(−1)|B| g(B)
para todo A⊆Θ se e somente se g(A) =
B⊆A
__
∑ (−1)|B| f(B).
B⊆A
__
Prova do Lema 5: Seja h(A) = −f(A) para todo A⊆Θ.
Se f(A) =
∑__(−1)|B| g(B)
para todo A⊆Θ, então:
B⊆A
__
h(A) = −f(A) = − ∑ (−1)|B| g(B) = ∑ (−1)|B| (−1)1 g(B) = ∑ (−1)|B|+1 g(B)
__
___
B⊆(A)
Pelo
Lema
4,
g(A)
__
|B|
1
1
(−1)
(−1)
(−1)
f(B
) =
∑
B⊆A
Por sua vez, se g(A) =
B⊆A
=
B⊆A
∑ (−1)|B|+1 h(B)
=
B⊆A
__
|B|+1
(−1)
−(f(B
))
∑
B⊆A
__
|B|
(−1)
f(B
).
∑
B⊆A
__
∑ (−1)|B|+1 f(B), então ∑__(−1)|B| g(B)
B⊆A
B⊆A
 15 
__
= −h(A) = f(A).
=
Teorema 3: Seja Q : 2Θ→[0,1], uma função de comunalidade, então bel:2Θ → [0,1] dada
por bel(A) =
∑__(−1)|B| Q(B) é a função de crença associada a essa função de comunalidade.
B⊆A
Por sua vez, se bel:2Θ → [0,1] é uma função de crença, então
__
∑ (−1)|B| bel( B )
Q(A) =
B⊆A
é 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
∑__(−1)|B| Q(B) é a função de crença associada a essa
bel:2Θ → [0,1] dada por bel(A) =
B⊆A
função de comunalidade:
∑__(−1)|B| Q(B)
=
B⊆A
∑__(−1)|B| ∑ m(C)
B⊆A



C


B⊆C
=
|B|
∑ m(C) ∑ (−1)
__

C⊆Θ
B⊆C ∩ A

Pelo Lema 1,
|B|
∑ m(C) ∑ (−1)
__

C⊆Θ
B⊆C ∩ A

=
∑ m(C)
=
C
__
C∩A=∅
∑ m(A)
= bel(A),
para todo A⊆Θ
C⊆A
Pelo Lema 5, obtem-se diretamente:
Q(A) =
__
|B|
(−1)
bel(
B)
∑
B⊆A
Outra propriedade importante é dada pelo Teorema 4:
Teorema 4: Sejam C 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 se Q({θ})>0.
Prova do Teorema 4: Como Q({θ}) = ∑ m(B), Q({θ}) será positivo se e somente se for um
B⊆Θ
θ∈B
elemento focal, i.e., se e somente se estiver em C.
 16 
Uma vez que a função de comunalidade é não-incremental ( B⊆A implica Q(B)≥Q(A)),
segue da conclusão acima que Q(A) = 0 quando A inclui um ponto fora do centro C. Mais
ainda, da relação entre função de crença e função de comunalidade, tem-se:
bel(∅) = 0 =
∑ (−1)|B| Q(B)
∑ (−1)|A|+1 Q(A)
ou
B⊆Θ
= 1
A⊆Θ
A≠∅
Outra observação importante é que se Q(A) = Kq(A), onde K é uma constante positiva
e q : (2Θ−{∅}) → [0,∞), é possível determinar K:
K =  ∑ (−1)|A|+1 q(A)
 A⊆Θ
A≠∅

8
 −1, pois
∑ (−1)|A|+1 Kq(A) = 1


A⊆Θ

A≠∅

Plausibilidade de Uma Função de Crença
__
Dado A⊆Θ, o valor bel(A) pode não evidenciar totalmente o quanto se pode acreditar em A.
Uma descrição mais completa pode ser dada pelo grau de dúvida, denominado dou, definido
por:
__
dou(A) = bel( A )
__
O grau de dúvida é utilizado com menos frequência que a quantidade 1 − bel( A ),
denominada plausabilidade de A (ou probabilidade superior de A), 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 que bel(A) ≤ ℘l(A) para todo A⊆Θ. Pode-se também expressar
℘l(A) em termos da atribuição básica de probabilidade m como garante o teorema a seguir:
Teorema 5: Dada uma função de crença bel:2Θ → [0,1] e sua atribuição de probabilidade
básica m:2Θ → [0,1], a função ℘l:2Θ → [0,1] dada por
℘l(A) = ∑ m(B)
B∩A≠∅
é a função de plausibilidade.
Prova do Teorema 5: Para qualquer A⊆Θ, tem-se
 17 
__
℘l(A) = 1 − bel( A ) =
∑ m(B)
-
B⊆Θ
∑__m(B)
B⊆A
=
∑ m(B)
B∩A≠∅
Da definição de plausibilidade acima e da definição da função de comunalidade, dada
por Q(A) =
∑ m(B), tem-se que, para todo elemento particular θ de Θ,
B⊆Θ
A⊆B
℘l({θ}) = Q({θ})
9
Intervalos de Crença
Como visto na seção imediatamente anterior, a plausibilidade de uma dada hipótese A,
℘l(A), representa o quanto é possível acreditar em A. Se bel(A) representa a crença atual em
A, e sabendo-se que bel(A)≤℘l(A), é natural que a informação contida na crença em A seja
mais convenientemente expressa pelo intervalo [bel(A),℘l(A)] ao invés de bel(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 que bel(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 em A, sem incorrer em erros graves de suposição. Esse intervalo recebe apropriadamente o nome de intervalo de crença, representado por ℑ(A), e é tão mais amplo quanto mais
incerteza houver sobre a crença em A. 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: Sejam A = {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 em A quanto em B 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 em C, entretanto
está em seu máximo, não sendo possível nenhum acréscimo, representando uma certeza que
a probabilidade de C 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 as funções de crença bayesianas.
Uma função de crença bel é dita bayesiana se bel(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ásica m:2Θ → [0,1] tal que:
(i) m({θ}) = bel({θ}) para todo θ∈Θ
(ii) m(A) = 0 para para todo A⊆Θ que não seja conjunto unitário.
O próximo teorema prova várias equivalências envolvendo funções de crença bayesianas.
Teorema
6:
Seja
uma
função
de
crença
bel:2Θ → [0,1]
com
plausibilidade
℘l(A):2Θ → [0,1] e comunalidade Q:2Θ → [0,1]. As seguintes assertivas são todas equivalentes entre si:
(1) bel é bayesiana
(2) os elementos focais de bel são conjuntos unitários
(3) bel garante comunalidade zero para qualquer subconjunto contendo mais que um
elemento
(4) bel(A) = ℘l(A) para todo A⊆Θ
__
(5) bel(A)+bel(A) = 1 para todo A⊆Θ
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ção Q(A) =
∑ m(B), lembrando que se B possui mais que
B⊆Θ
A⊆B
um elemento, então m(B) = 0.
w (2) ≡ (4): Segue da comparação entre as relações bel(A) = ∑ m(B) e
B⊆A
℘l(A) = ∑ m(B) , lembrando que se B possui mais que um elemento, então
B∩A ≠ ∅
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ção bel:2Θ → [0,1] é uma função de crença bayesiana se existe uma
função ρ:Θ → [0,1] tal que:
∑ ρ(θ) = 1
e bel(A) = ∑ρ(θ)
θ ∈Θ
θ ∈A
Prova do Teorema 7: Tem-se
(i)
bel(∅) = ∑ρ(θ) = 0
θ ∈∅
(ii)
bel(Θ) = ∑ρ(θ) = 1
θ ∈Θ
(iii)
quando A∩B = ∅, A,B⊆Θ,
bel(A)+bel(B) = ∑ρ(θ)+∑ρ(θ) = ∑ρ(θ) = bel(A∪B)
θ ∈A
θ ∈B
θ ∈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ção m1⊕m2 é usada para indicar os efeitos combinados de duas atribuições de
probabilidade básica m1 e m2. A função de crença correspondente, notada por bel1⊕bel2, pode
ser calculada facilmente a partir de m1⊕m2.
Se m1 e m2 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) = χ∑ m1(X)×m2(Y), para todo A⊆Θ
(II)
X∩Y = A
A≠∅
onde χ é a constante de normalização, definida como
1
, e κ é a soma dos bpa’s de todas
1−κ
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: Se m1 e m2 são duas atribuições de probabilidades básicas em um domínio do
problema Θ, com
∑m1(Ai)m2(Bj) < 1
Ai∩Bi = ∅
então sua soma ortogonal m1⊕m2 definida por
m(∅) = 0
m1⊕m2(A) = χ∑ m1(X)×m2(Y), para todo não vazio A⊆Θ
X∩Y = A
A≠∅
onde χ é a constante de normalização, definida como
as ocorrências do conjunto ∅, é um bpa.
 21 
1
, e κ é a soma dos bpa’s de todas
1−κ
Prova do Teorema 8: É trivial a demonstração que m1⊕m2 satisfaz as duas primeiras
condições de uma atribuição de probabilidade básica. Fazendo-se m = m1⊕m2, para simplificação de notação, resta a prova que ∑ m(A) = 1. Mas,
A∈2
∑ m(A) = ∑ m(A) =
A∈2
Θ
Θ
m(∅) + ∑ m(A) = χ∑ m1(X)×m2(Y) =
A⊆Θ
X∩Y = A
A⊆Θ
A≠∅
=
1
1−κ
∑ m1(X)×m2(Y)
A≠∅
1
1−κ
=
X∩Y = A
∑ m1(X)×m2(Y)
X∩Y ≠ ∅
A≠∅
Tem-se, pela definição que κ = ∑ m1(X)×m2(Y). O que, por sua vez pode ser escrito como
X∩Y = ∅
κ = 1 − ∑ m1(X)×m2(Y)
X∩Y ≠ ∅
Voltando-se à equação anterior, obtém-se
1
1−κ
∑ m1(X)×m2(Y)
=
X∩Y ≠ ∅
=
∑ m1(X)×m2(Y) =
1 − 1 − ∑ m1(X)×m2(Y)
 X∩Y ≠ ∅

X∩Y
≠
∅


1
1
∑ m1(X)×m2(Y)
X∩Y ≠ ∅
∑ m1(X)×m2(Y) = 1
X∩Y ≠ ∅
Pode ser verificado trivialmente que o centro da função de crença bel1⊕bel2 dada por
m1⊕m2 é igual à intersecção dos centros de bel1 e bel2. Quando ∑m1(Ai)m2(Bj) < 1 não vale,
Ai∩Bi = ∅
diz-se que bel1⊕bel2 não existe, isto é, não é possível combinar bel1 e bel2 utilizando-se a
regra de combinação de Dempster. Também pode ser verificado que, se Q1 e Q2 são as
funções de comunalidade associadas a bel1 e bel2, então a combinação de Q1 e Q2,
representada por Q1⊕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
determinada m1 observação indique {alergia, intoxicação} (resumidamente {a,i}), com grau
 22 
0.5, enquanto que uma outra m2 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 por m1⊕m2 e é
representada na Tabela 1:
m2
Θ (0.4)
{i,r,s} (0.6)
{a,i} (0.5)
{i} (0.3)
{a,i}
(0.2)
m1
Θ (0.5)
{i,r,s}
Θ
(0.3)
(0.2)
Tabela 1
Rede de crenças para m1 e m2
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 calcular bel1⊕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, onde m4 = m1⊕m2 do exemplo anterior
 23 
m4
{i} (0.3)
{a,i} (0.2)
{i,r,s} (0.3)
{a} (0.8)
∅ (0,24)
{a} (0.16)
∅ (0,24)
Θ (0.2)
{i} (0.06)
{a,i} (0.04)
Θ (0.2)
{a}
(0.16)
m3
{i,r,s}
(0.06)
Θ
(0.04)
Tabela 2
Rede de Crenças para m3 e m4
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, χ =
1
, onde κ é a soma dos bpa’s de todas as ocorrências
1−κ
do conjunto ∅, cujas ocorrências se devem à combinação de hipóteses disjuntas. O valor
log(χ)1 é denominado peso de conflito entre bel1 e bel2 denotado con(bel1,bel2). Se bel1 e
bel2 não se conflitam em nada (como no exemplo 9, acima), então κ = 0 e con(bel1,bel2) = 0.
1.
Neste relatório, estamos considerandos logarítmos de base 10. Em verdade, o peso de conflito poderia ser definido para
qualquer base positiva maior que 1 (logaritmos naturais, por exemplo).
 24 
Por outro lado, se bel1 e bel2 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ção bel1⊕bel2 não é possível. O teorema
abaixo determina quando não é possível combinar bel1 e bel2 utilizando-se a regra de
combinação de Dempster:
Teorema 9: Sejam bel1 e bel2 funções de crença sobre o mesmo domínio Θ, e sejam Q1 e
Q2 as funções de comunalidade associadas, respectivamente, a bel1 e bel2. As seguintes
condições são equivalentes:
(1) bel1⊕bel2 não existe
(2) os centros de bel1 e bel2 são disjuntos
__
(3) existe um subconjunto A⊆Θ tal que bel1(A) = 1 e bel2(A) = 1
(4) Q1(A)Q2(A) = 0 para todo não-vazio A⊆Θ
Prova do Teorema 9:
w (1) ≡ (2) Sejam Ai e Bj os elementos focais de bel1 e bel2, respectivamente. Tem-se
que m1(Ai)m2(Bj) > 0 para todo i e j. E, portanto,
∑ m1(Ai)m2(Bj)
i,j
=
∑ m1(Ai)
i
×
∑ m2(Bj) = 1
j
Donde ∑ m1(Ai)m2(Bj) < 1 falha se e somente se Ai∩Bj = ∅ para todo i,j.
i,j
Ai∩Bj = ∅
Se C1 e C2 denotam os centros de bel1 e bel2, respectivamente, então:
C1∩C2 = ∪ Ai ∩ ∪ Bj = ∪(Ai∩Bj)
 


i,j
  j

 i
Dessa forma, Ai∩Bj = ∅ para todo i,j se e somente se C1∩C2 = ∅
__
__
w (2) ≡ (3) Tem-se que bel1(A) = bel2(A) = 1 se e somente se C1⊆A e C2⊆A, isto é,
C1∩C2 = ∅
w (2) ≡ (4) Uma função de crença garante comunalidade positiva não-nula para conjuntos unitários somente se estes estão contidos no centro dessa função. Então, se
C1∩C2 ≠ ∅, Q1(θ)Q2(θ) > 0 para qualquer θ∈C1∩C2. Caso C1∩C2 = ∅, todo nãovazio A⊆Θ, desde que não é subconjunto de C1 e C2 ao mesmo tempo, irá satisfazer
 25 
Q1(A) = 0 ou Q1(A) = 0. Portanto, Q1(A)Q2(A) = 0 para todo não-vazio A⊆Θ se e
somente se C1∩C2 = ∅
Este teorema pode ser estendido facilmente a várias funções de crença:
Teorema 10: Sejam bel1, bel2,..., beli,..., beln funções de crença sobre o mesmo domínio
Θ, e sejam Q1, 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 de bel1, bel2,..., beli,..., beln são disjuntos
(3) existem subconjuntos A1,A2,…,Ai,…,An⊆Θ tal que A1∩A2∩…∩Ai∩…∩An = ∅,
mas beli(Ai) = 1 para todo i∈{1,…,n}
(4) Q1(A)×Q2(A)×…×Qi(A)×…×Qn(A) = 0 para todo não-vazio A⊆Θ
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 
m1
{M} (0.9)
{T} (0.1)
{C} (0.8)
∅ (0,72)
∅ (0,08)
{T} (0.2)
∅ (0,18)
{T} (0.02)
m2
Tabela 3
Rede de crenças para m1 e m2
Neste caso, κ = 0.72+0.08+0.18 = 0.98 o que dá
χ=
1
1
=
= 5 e con(bel1,bel2) = log(5) ≅ 0.699
1−κ 0.2
Observe que, temos m1⊕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 superiores. 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:
 27 
Critério
Avaliação
Interpretação
As funções de crença permitem rápida compreensão, o que facilita o fornecimento de
informação ao usuário. Sua estrutura é, sob certos aspectos, semelhante ao de Fatores
de 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 Fatores
de Certeza por possuir uma rigorosa estrutura matemática. Quando expressa por
intervalos de crença, os resultados são ainda melhores.
Imprecisão
A 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, pois
pode 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ão
sejam muito conflitantes. Alguns autores sugerem alternativas nesse caso (por exemplo
[Walley (1996)] e [Wang (1994)]). Na maioria das situações, entretanto, a regra de
Dempster produz resultados altamente satisfatórios.
Consistência
O peso de conflito permite verificar se a combinação de duas ou mais crenças produzirá
resultados indesejáveis.
Declaração
Não há ainda procedimentos seguros que guiem o processo de declaração de crenças, o
que 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 precisar
de probabilidades condicionais e como uma evidência em geral foca apenas um pequeno
número do total das hipóteses, o cálculo pode ser bastante simplificado, pois a TDS não
precisa indicar crença nula. Outro problema ainda em questionamento é o de como as
crenç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 possibilidade)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ão
obedecem todas as regras obedecidas pelo acaso. (...) Possibilidades surgem quando
alguém descreve um experimento aleatório ou randômico, como o rolar de um dado
ou o atirar de uma moeda. O resultado de tal experimento varia randomicamente entre
experimentos fisicamente independentes.
2.
3.
O termo em inglês é chance, traduzido por possibilidade ou acaso. Nesse relatório foram utilizadas as duas traduções,
conforme o contexto.
Em inglês, belief.
 28 
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 graus
de crença. Mas se nós não conhecemos as possibilidades, então será uma extraordiná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 regra
de combinação de Dempster permite-nos construir descrições de raciocínio provável
que são mais modestos que descrições bayesianas, mas mais fidedigno à forma
humana 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 Intelligence, Pittsburgh, PA, 1982, p. 133-136.
[Reiter (1980)] Reiter, R. A Logic for Default Reasoning. Artificial Intelligence 13, 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-
gence 83, 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 DempsterShafer 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 Systems 1, 1978, pp 3-28.
 31 

Elementos da Teoria de Evidência de Dempster

Transcrição

Documentos relacionados

protocolo limpeza de pele – peles oleosas

Limpeza de Pele – Peles Acneicas

O Grupo Bel decide integrar o transporte ferroviário na sua

matéria completa - Communicação Assessoria Empresarial

A `Aqidah Vem Em Primeiro! - Nur Al

Adesão pelo Correio

Aqidah vem em primeiro! - Nur Al

Faça da ficha técnica

A potência subliminar

repolho Maddox