Author: Fabio Gagliardi Cozman
 |
O formato de intercâmbio para redes Bayesianas |
Introdução
O objetivo deste site é resumir e distribuir informações sobre um esforço para padronizar formatos para representação de redes bayesianas e outros modelos gráficos relacionados.
O objetivo do esforço atual é especificar um formato baseado em XML que seja muito simples de entender e que ainda possa representar gráficos acíclicos dirigidos com relações probabilísticas, variáveis de decisão e valores de utilidade. O formato atual é conhecido como XMLBIF versão 0.3.
Background histórico
O formato atual é Vários membros da comunidade UAI sentiram que um formato comum para redes Bayesianas aumentaria significativamente a troca de conhecimento e resultados experimentais na comunidade. Com o espírito de promover esse intercâmbio, várias tentativas foram feitas na criação de um formato padronizado. Um painel foi organizado na conferência de UAI de 1996, e formatos como o BNIF e o BIF foram então propostos; eventualmente, um um grupo foi formado para debater questões relacionadas a um possível padrão. À medida que essas discussões prosseguiram, tornou-se evidente que a definição de um único formato abrangente provavelmente seria uma tarefa muito difícil no estágio atual do conhecimento.
Durante a conferência de UAI de 1998, foi formado um novo painel para avaliar a estratégia a seguir em direção a um formato padrão. O painel sugeriu que seria uma boa ideia baseá-lo em XML (A Linguagem de Marcação Extensível), pois o XML agora está recebendo o suporte da indústria como um mecanismo para a especificação de dados. A idéia é que o XML pode fornecer uma camada inicial de padronização. Mesmo que diferentes formatos sejam propostos por diferentes grupos, o fato de que eles são baseados em XML torna a tradução muito mais simples. E o fato de que os analisadores compatíveis com XML estão livremente disponíveis torna o processo inteiro mais suave.
Após a discussão em painel, várias reuniões entre membros da comunidade UAI sugeriram que poderia ser dado outro passo no caminho da padronização. Seria uma boa ideia tentar definir um formato padrão muito simples em XML. Esse padrão teria que ser simples para que as pessoas pudessem entendê-lo rapidamente e construir analisadores para ele sem muito trabalho. O padrão seria benéfico para familiarizar as pessoas com XML e para indicar como proceder em esforços de padronização futuros.
As discussões levaram ao atual esforço de padronização. Um formato muito simples foi definido durante conversas entre Fabio Cozman e membros do projeto GeNie notavelmente Marek Druzdzel e Daniel Garcia. Este formato é descrito abaixo e atualmente é conhecido como XMLBIF (XML-based BayesNets Interchange Format) versão 0.3.
O formato XMLBIF está sendo implementado nos sistemas JavaBayes e GeNie; houve sinais de que as implementações nos sistemas Netica e Hugin estão em andamento.
O grupo de trabalho XMLBIF
Muitas pessoas contribuíram para o formato XMLBIF. O formato foi projetado principalmente por Fabio Cozman, com importantes contribuições de Marek Druzdzel e Daniel Garcia. Akihiro Shinmori contribuiu com sua experiência em questões XML. Brent Boerlage, Frank Jensen e Bruce D'Ambrosio apoiaram a idéia e contribuíram para a discussão.
Qualquer um pode se juntar ao grupo e contribuir.
O formato XMLBIF
O objetivo do formato XMLBIF atual é representar gráficos acíclicos dirigidos que podem ser associados a medidas de probabilidade condicional para variáveis discretas, com a possibilidade de que as variáveis de decisão e de utilidade estejam presentes no gráfico.
O formato enfatiza a internacionalização, adotando as diretrizes do XML para a especificação do documento (a Documentação XML explica isso no comprimento, isso equivale à adoção do Unicode como padrão para representação de personagens, documentos sensíveis a maiúsculas e marcas para indicar codificações de documento).
XML é muito semelhante ao HTML e a maioria das estruturas usadas em HTML aparecem em XML.
Todo arquivo em XMLBIF deve conter uma tag XML inicial que exiba informações básicas sobre o documento:
<?xml version="1.0"?>
O atributo da versão é obrigatório. Outros atributos, que se seguem ao atributo da versão, são opcionais. Por exemplo:
<?xml version="1.0" encoding="US-ASCII"?>Outras tags XML podem vir após essa tag inicial. A Especificação XML detalha as possíveis tags. Essencialmente, o documento XML pode conter várias indicações sobre a gramática que devem ser aplicadas pelo analisador XML. A possibilidade mais interessante é incorporar toda a especificação do documento na parte superior do documento através de uma etiqueta DOCTYPE. Aqui está a especificação XML completa da XMLBIF versão 0.3 (isto é chamado de Definição de Tipo de Documento ou DTD):
<!DOCTYPE BIF [ <!ELEMENT BIF ( NETWORK )*> <!ATTLIST BIF VERSION CDATA #REQUIRED> <!ELEMENT NETWORK ( NAME, ( PROPERTY | VARIABLE | DEFINITION )* )> <!ELEMENT NAME (#PCDATA)> <!ELEMENT VARIABLE ( NAME, ( OUTCOME | PROPERTY )* ) > <!ATTLIST VARIABLE TYPE (nature|decision|utility) "nature"> <!ELEMENT OUTCOME (#PCDATA)> <!ELEMENT DEFINITION ( FOR | GIVEN | TABLE | PROPERTY )* > <!ELEMENT FOR (#PCDATA)> <!ELEMENT GIVEN (#PCDATA)> <!ELEMENT TABLE (#PCDATA)> <!ELEMENT PROPERTY (#PCDATA)> ]>Esta tag contém toda a Definição de Tipo de Documento (DTD) para XMLBIF versão 0.3, e pode ser incluído em qualquer XMLBIF documento da versão 0.3. A DTD mostra todas as tags usadas pela XMLBIF versão 0.3. As redes representadas em um arquivo deve ser anexado por tags BIF; a etiqueta BIF de abertura deve conter a versão do formato. Por exemplo:<BIF VERSION="0.3"> Network aqui Another network here </BIF>Cada rede é anexada por tags de rede. Uma rede é definida através de uma tag NAME e uma seqüência de marcas PROPERTY, VARIABLE e DEFINITION nota que nenhuma ordem é imposta nas marcas PROPRIEDADE, VARIÁVEL e DEFINIÇÃO).<BIF VERSION="0.3"> <NETWORK> <NAME>Dog-Problem</NAME> <PROPERTY>date Sunday, 19 July, 1998</PROPERTY> <PROPERTY>author John</PROPERTY> variáveis e probabilidades vão aqui </NETWORK> </BIF>Uma propriedade é apenas uma string de texto arbitrário a ser associado a um bloco. Exemplos de propriedades:
<PROPERTY>size 12</PROPERTY> <PROPERTY>comment Trial number ten</PROPERTY>Qualquer texto é válido na string dentro das tags de abertura e fechamento do PROPRIEDADE. A idéia é armazenar informações específicas para um determinado sistema ou rede nas propriedades. Qualquer número dos atributos da propriedade podem aparecer em um bloco. As propriedades podem ser associadas para uma REDE, uma VARIÁVEL ou uma DEFINIÇÃO.As variáveis são definidas pelos nomes, tipos e propriedades:
<VARIABLE TYPE="nature"> <NAME>light-on</NAME> <OUTCOME>true</OUTCOME> <OUTCOME>false</OUTCOME> <PROPERTY>position = (73, 165)</PROPERTY> </VARIABLE>Atualmente, o conteúdo de um atributo TYPE deve ser a palavra-chave ``nature'' ou ``decision'' ou ``utility''.As densidades de probabilidade condicionais são especificadas da etiqueta DEFINITION. Um exemplo é:
<DEFINITION> <FOR>hear-bark</FOR> <GIVEN>dog-out</GIVEN> <TABLE>0.7 0.3 0.99 0.01 </TABLE> </DEFINITION>Não existe uma ordem obrigatória de blocos de variáveis e de probabilidades.
A tag TABLE é específica para o bloco DEFINITION (nota que uma definição pode ser uma distribuição de probabilidade, um conjunto de valores de decisão ou um conjunto de valores de utilidade, dependendo nos atributos TYPE da referida variável). Os blocos DEFINITION são usados para definir a topologia de rede atual, especificando tabelas de probabilidade condicional.
Um exemplo de um bloco de probabilidade padrão é:
<DEFINITION> <FOR>GasGauge</FOR> <GIVEN>BatteryPower</GIVEN> <GIVEN>GasInTank</GIVEN> <TABLE>1.0 0.0 0.0 1.0 0.2 0.8 0.0 1.0 </TABLE> </DEFINITION>para um GasGauge variável que é definido com TYPE igual a ``nature''. O corpo da tag TABLE é uma seqüência de números reais não negativos, na ordem de contagem de as variáveis declaradas, tomando as variáveis GIVEN primeiro e depois as variáveis FOR (se todas as variáveis fossem binárias, dirijamos binário contando com o dígito menos significativo na direita). Se existem várias declarações de tabela, somente a última é válida.Aqui está a rede bayesiana problemática para cães, com base na discussão em Charniak, E., Bayesian Networks Sem Obstruções, AI Magazine, 1991.
<?xml version="1.0" encoding="US-ASCII"?> <!-- Bayesian network in XMLBIF v0.3 (BayesNet Interchange Format) Produzido por JavaBayes (http://www.cs.cmu.edu/~javabayes/ Saída criada qua 12 de agosto 21:16:40 GMT+01:00 1998 --> <!-- DTD for the XMLBIF 0.3 format --> <!DOCTYPE BIF [ <!ELEMENT BIF ( NETWORK )*> <!ATTLIST BIF VERSION CDATA #REQUIRED> <!ELEMENT NETWORK ( NAME, ( PROPERTY | VARIABLE | DEFINITION )* )> <!ELEMENT NAME (#PCDATA)> <!ELEMENT VARIABLE ( NAME, ( OUTCOME | PROPERTY )* ) > <!ATTLIST VARIABLE TYPE (nature|decision|utility) "nature"> <!ELEMENT OUTCOME (#PCDATA)> <!ELEMENT DEFINITION ( FOR | GIVEN | TABLE | PROPERTY )* > <!ELEMENT FOR (#PCDATA)> <!ELEMENT GIVEN (#PCDATA)> <!ELEMENT TABLE (#PCDATA)> <!ELEMENT PROPERTY (#PCDATA)> ]> <BIF VERSION="0.3"> <NETWORK> <NAME>Dog-Problem</NAME> <!-- Variables --> <VARIABLE TYPE="nature"> <NAME>light-on</NAME> <OUTCOME>true</OUTCOME> <OUTCOME>false</OUTCOME> <PROPERTY>position = (73, 165)</PROPERTY> </VARIABLE> <VARIABLE TYPE="nature"> <NAME>bowel-problem</NAME> <OUTCOME>true</OUTCOME> <OUTCOME>false</OUTCOME> <PROPERTY>position = (190, 69)</PROPERTY> </VARIABLE> <VARIABLE TYPE="nature"> <NAME>dog-out</NAME> <OUTCOME>true</OUTCOME> <OUTCOME>false</OUTCOME> <PROPERTY>position = (155, 165)</PROPERTY> </VARIABLE> <VARIABLE TYPE="nature"> <NAME>hear-bark</NAME> <OUTCOME>true</OUTCOME> <OUTCOME>false</OUTCOME> <PROPERTY>position = (154, 241)</PROPERTY> </VARIABLE> <VARIABLE TYPE="nature"> <NAME>family-out</NAME> <OUTCOME>true</OUTCOME> <OUTCOME>false</OUTCOME> <PROPERTY>position = (112, 69)</PROPERTY> </VARIABLE> <!-- Probability distributions --> <DEFINITION> <FOR>light-on</FOR> <GIVEN>family-out</GIVEN> <TABLE>0.6 0.4 0.05 0.95 </TABLE> </DEFINITION> <DEFINITION> <FOR>bowel-problem</FOR> <TABLE>0.01 0.99 </TABLE> </DEFINITION> <DEFINITION> <FOR>dog-out</FOR> <GIVEN>bowel-problem</GIVEN> <GIVEN>family-out</GIVEN> <TABLE>0.99 0.01 0.97 0.03 0.9 0.1 0.3 0.7 </TABLE> </DEFINITION> <DEFINITION> <FOR>hear-bark</FOR> <GIVEN>dog-out</GIVEN> <TABLE>0.7 0.3 0.01 0.99 </TABLE> </DEFINITION> <DEFINITION> <FOR>family-out</FOR> <TABLE>0.15 0.85 </TABLE> </DEFINITION> </NETWORK> </BIF>Fora do XML
É importante notar que existem alguns fatos sobre o formato que não pode ser explicitado através de XML. Por exemplo, se uma DEFINITION contiver várias etiquetas TABLE, somente a última é válida. Outro exemplo é que XMLBIF versão 0.3 aceita números reais que são representados em notação científica conforme especificado nas definições da linguagem ANSI C ou Java.A versão 0.3 do XMLBIF foi projetado para usar as facilidades XML; assim sendo aceita caracteres Unicode. Mas como implementações atuais de analisadores deve, em muitos casos, contar com sistemas que não possuem um bom suporte Unicode, sugerimos que apenas caracteres ASCII são usados na versão XMLBIF 0.3 arquivos por enquanto. Além disso, identificadores (o nome da rede, nomes de variáveis e nomes de resultados) podem ser expressos em qualquer Unicode personagem; no entanto, temos alguns problemas com esse nível de liberdade. Primeiro, há dificuldades em escrever analisadores personalizados que podem suportar toda a gama de Unicode. Em segundo lugar, há perguntas relacionadas à manipulação de expressões matemáticas envolvendo variáveis com nomes arbitrariamente complexos. Por estas razões, nós exigir que os identificadores na versão XMLBIF 0.3 satisfaçam um pouco restritivos condições: qualquer identificador deve ser uma seqüência de letras e dígitos, e a seqüência deve começar com uma carta. Uma carta é qualquer personagem nas seqüências [a-z] e [A-Z] além do sublinhado _. Um dígito é qualquer personagem na sequência [0-9]. É possível que, no futuro, um conjunto de condições menos restritivas será dado para identificadores, similares ao Java identificadores de linguagem.
O aspecto mais importante do formato atual que não é capturado por XML é a semântica dos conteúdos de uma etiqueta TABLE. Todas as distribuições e valores de utilidade são especificados como arrays de números reais; XMLBIF versão 0.3 não requer Esses números não são negativos nem somam um máximo. Tal As condições de consistência devem ser verificadas pelo analisador se desejado. O ponto importante é como as tabelas são organizadas:
As probabilidades de uma variável binária podem ser especificadas de forma simples:
0.15, 0.85
Consideremos um exemplo mais complicado. O condicional p(d|f,b) (a probabilidade de d dado f e b, onde todas variáveis são binárias) é definida como
0.99, 0.01, 0.90, 0.1, 0.97, 0.03, 0.3, 0.70
A lógica é simples: prossiga como se estivesse preenchendo uma tabela, onde os índices da mesa variam da direita para a esquerda, com as variáveis condicionais primeiro (no exemplo acima, é como a contagem binária porque todas as variáveis têm apenas dois valores).Um exemplo mais complicado seria uma função p(A|B,C) onde A tem 3 valores, B tem 2 valores e C tem 4 valores. A função é representado como:
p(A1|B1 C1) p(A2|B1 C1) p(A3|B1 C1)
p(A1|B1 C2) p(A2|B1 C2) p(A3|B1 C2)
p(A1|B1 C3) p(A2|B1 C3) p(A3|B1 C3)
p(A1|B1 C4) p(A2|B1 C4) p(A3|B1 C4)
p(A1|B2 C1) p(A2|B2 C1) p(A3|B2 C1)
p(A1|B2 C2) p(A2|B2 C2) p(A3|B2 C2)
p(A1|B2 C3) p(A2|B2 C3) p(A3|B2 C3)
p(A1|B2 C4) p(A2|B2 C4) p(A3|B2 C4)