00001 /* 00002 * Copyright 2007, 2008 Ernesto Coutinho Colla 00003 * 00004 * "BN Parallel Package" é um nome que identifica o conjunto de programas 00005 * que forma uma biblioteca de rotinas que foram desenvolvidas como parte da 00006 * dissertação de mestrado do autor em Ciências da Computação. 00007 * 00008 * O conjunto de programas foi integralmente desenvolvido pelo autor e está 00009 * disponível sob a licença GPL (GNU General Public License). O entendimento 00010 * integral dos termos da licença GPL é condição necessária para a utilização 00011 * parcial ou integral de qualquer parte deste conjunto de programas. 00012 * 00013 * This file is part of BN Parallel Package. 00014 * 00015 * BN Parallel Package is free software: you can redistribute it and/or modify 00016 * it under the terms of the GNU General Public License as published by 00017 * the Free Software Foundation, either version 3 of the License. 00018 * 00019 * BN Parallel Package is distributed in the hope that it will be useful, 00020 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00021 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00022 * GNU General Public License for more details. 00023 * 00024 * You should have received a copy of the GNU General Public License 00025 * along with BN Parallel Package. If not, see <http://www.gnu.org/licenses/>. 00026 */ 00027 00028 00029 /*! 00030 * @file BNVarElimination.h 00031 * @author Ernesto Colla (ernesto@gmail.com) 00032 * @version 0.0.1 00033 * @date Junho/2007 (2007-06-28) 00034 * @brief Biblioteca para fazer inferência em Redes Bayesianas (BN: \e Bayesian \e Network) utilizando o método de eliminação de variáveis. 00035 * 00036 */ 00037 00038 #ifndef DBGOUT 00039 #define DBGOUT stdout 00040 #endif 00041 00042 #ifndef BNVARELIMINATION_H 00043 #define BNVARELIMINATION_H 00044 00045 /* Includes */ 00046 #include <math.h> 00047 #include <pthread.h> 00048 00049 /* Bibliotecas específicas */ 00050 #include "BNMain.h" 00051 #include "graphtools.h" 00052 #include "threadtree.h" 00053 #include "singlelinkedlist.h" 00054 00055 /* Typedefs */ 00056 00057 /*! Estrutura de dados para definir uma operação de eliminação */ 00058 typedef struct struct_Elimination { 00059 int id; //!< \e id da operação de eliminação. Manipulado internamente pela biblioteca não deve ser alterado. 00060 int marginalize; //!< Flag para indicar se deve fazer a operação de marginalização: 1:marginaliza; 0:faz o produto mas não marginaliza. 00061 int nconst; //!< Parte constante da lista de potenciais da eliminação. Correspondem aos potenciais originais da Rede Bayesiana 00062 Variable* variable; //!< Variável que será eliminada na operação. 00063 SingleLinkedList* potentials; //!< Potenciais envolvidos na operação. 00064 Potential* result; //!< Potencial resultado da eliminação. 00065 pthread_mutex_t mutex; //!< Multex para garantir a sincronia das operações na eliminação 00066 } Elimination; 00067 00068 00069 // METHODS 00070 00071 void scale(int nvalues, double** refValues); 00072 00073 00074 /*! 00075 * @brief Constrói a árvore de eliminação de \e threads. A árvore de eliminação uma vez definida pode ser reutilizada para executar 00076 * diversas inferências. 00077 * @param[in] elmorder \e Array com os \e ids das variáveis na ordem que devem ser eliminadas. 00078 * @param[in] elmtree Grafo que representa a árvore de eliminação para resultante da fatoração simbólica. 00079 * @return \e ThreadTree construida a partir da ordem de eliminação e da árvore de eliminação. 00080 */ 00081 00082 // TODO: Atualizar documentação 00083 // ThreadTree* buildBNThreadTree(int nxq, int* xq, int nxe, int* xe, Potential** findings, BayesNet* bayesnet, Graph* moral, int* elmorder, Graph* elmtree); 00084 // ThreadTree* buildBNThreadTree(BayesNet* bayesnet, int* elmorder,Graph* elmtree); 00085 ThreadTree* buildBNThreadTree(int nxq, int* xq, int nxe, int* xe, Potential** findings,BayesNet* bayesnet, int* elmorder, Graph* moral, Graph* elmtree); 00086 00087 /*! 00088 * @brief Destrói a árvore de threads criada para executar a inferência. 00089 * @param[out] refThreadTree Referência para a \e ThreadTree a ser destruida. 00090 */ 00091 00092 void destroyBNThreadTree(ThreadTree** refThreadTree); 00093 00094 /*! 00095 * @brief Executa a inferência com a eliminação de variáveis da Rede Bayesiana explorando a possibilidade de executar a eliminação em paralelo. 00096 * @param[in] nxq Número de variáveis questionadas (\e Query \e Variables). 00097 * @param[in] xq \e Array com os \e ids das variáveis questionadas (\e Query \e Variables). 00098 * @param[in] nxe Número de variáveis que compõe a evidência (\e Evidence), ou seja, as variáveis observadas. O estado da variável esta 00099 * em outra estrutura denominada \e finding. 00100 * @param[in] xe \e Array com os \e ids das variáveis observadas. 00101 * @param[in] findings Potenciais que indicam os estados observados das variáveis. 00102 * @param[in] bayesnet BN da qual se deseja obter as variáveis requisitadas para a inferência. 00103 * @param[in] elmorder \e Array com os \e ids das variáveis na ordem que devem ser eliminadas. 00104 * @param[in] moral \e Moral \e Graph utilizado para a eliminação de variáveis e construido apenas com variáveis requisitadas. 00105 * @param[in] threadtree \e ThreadTree construida a partir da ordem de eliminação e da árvore de eliminação. 00106 * @return Potencial resultante do processo de eliminação de variáveis do grafo e portanto o resultado da inferência. 00107 */ 00108 00109 // Potential* doBNVariableElimination(int nxq, int* xq, int nxe, int* xe, Potential** findings, BayesNet* bayesnet, int* elmorder, Graph* moral, ThreadTree* threadtree); 00110 // Potential* doBNVariableElimination(Potential** findings, ThreadTree* threadtree); 00111 Potential* doBNVariableElimination(ThreadTree* threadtree); 00112 00113 /*! 00114 * @brief Executa linearmente a inferência com a eliminação de variáveis da Rede Bayesiana, ou seja, apenas uma variável é eliminada de cada vez 00115 * de forma serial, sem explorar a possibilidade de paralelização. 00116 * @param[in] nxq Número de variáveis questionadas (\e Query \e Variables). 00117 * @param[in] xq \e Array com os \e ids das variáveis questionadas (\e Query \e Variables). 00118 * @param[in] nxe Número de variáveis que compõe a evidência (\e Evidence), ou seja, as variáveis observadas. O estado da variável esta 00119 * em outra estrutura denominada \e finding. 00120 * @param[in] xe \e Array com os \e ids das variáveis observadas. 00121 * @param[in] findings Potenciais que indicam os estados observados das variáveis. 00122 * @param[in] bayesnet BN da qual se deseja obter as variáveis requisitadas para a inferência. 00123 * @param[in] elmorder \e Array com os \e ids das variáveis na ordem que devem ser eliminadas. 00124 * @param[in] moral \e Moral \e Graph utilizado para a eliminação de variáveis e construido apenas com variáveis requisitadas. 00125 * @return Potencial resultante do processo de eliminação de variáveis do grafo e portanto o resultado da inferência. 00126 */ 00127 00128 Potential* doBNLinearVariableElimination(int nxq, int* xq, int nxe, int* xe, Potential** findings, BayesNet* bayesnet, int* elmorder, Graph* moral); 00129 00130 /*! 00131 * @brief Função genérica invocada pela \e thread para executar uma operação de eliminação. 00132 * @param[out] arg Argumento genérico utilizada para passar literamente qualquer estrutura de dados necessária para executar a tarefa. 00133 */ 00134 00135 void *taskVariableElimination(void* arg); 00136 00137 /*! 00138 * @brief Executa a operação de eliminação de variável e armazena o resultado na própria estrutura de dados 00139 * @param[out] refElimination Referência para a estrutura que define uma operação de eliminação. O resultado será armazenado no 00140 * na própria estrutura. 00141 */ 00142 00143 void executeElimination(Elimination** refElimination); 00144 00145 /*! 00146 * @brief Normaliza um \e array de valores reais, ou seja, altera os valores de forma que a soma dos mesmos seja igual a 1. 00147 * @param[in] nvalues Número de elementos do \e array de números reais que será normalizado. 00148 * @param[out] refValues Referência para o \e array de números reais que será normalizado. 00149 */ 00150 00151 void normalize(int nvalues, double** refValues); 00152 00153 /*! 00154 * @brief Marginaliza as variáveis não requeridas de um potencial. 00155 * 00156 * Atenção: Apesar do valor de retorno da função de ser pouco intuitivo ela foi feita desta forma para evitar operações desnecessárias. 00157 * @param[in] moral \e Moral \e Graph utilizado para a eliminação de variáveis e construido apenas com variáveis requisitadas. 00158 * @param[in] source Potencial a ser marginalizado. 00159 * @return Potencial marginalizado ou NULL se não for feita nenhuma marginalização. 00160 */ 00161 00162 Potential* marginalizeNotRequired(Graph* moral, Potential* source); 00163 00164 #endif