BNVarElimination.h

Vá para a documentação deste arquivo.
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

Gerado em Fri Feb 15 19:50:41 2008 para IME-Dissertação por  doxygen 1.5.1