On the Complexity of Strong and Epistemic Credal Networks

Credal networks are graph-based statistical models whose parameters take values on a set, instead of being sharply specified as in traditional statistical models (e.g., Bayesian networks). The result of inferences with such models depends on the irrelevance/independence concept adopted. In this paper, we study the computational complexity of inferences under the concepts of epistemic irrelevance and strong independence. We strengthen complexity results by showing that inferences with strong independence are NP-hard even in credal trees with ternary variables, which indicates that tractable algorithms, including the existing one for epistemic trees, cannot be used for strong independence. We prove that the polynomial time of inferences in credal trees under epistemic irrelevance is not likely to extend to more general models, because the problem becomes NP-hard even in simple polytrees. These results draw a definite line between networks with efficient inferences and those where inferences are hard, and close several open questions regarding the computational complexity of such models.

Solving Decision Problems with Limited Information

We present a new algorithm for exactly solving decision-making problems represented as an influence diagram. We do not require the usual assumptions of no forgetting and regularity, which allows us to solve problems with limited information. The algorithm, which implements a sophisticated variable elimination procedure, is empirically shown to outperform a state-of-the-art algorithm in randomly generated problems of up to 150 variables and 10^64 strategies.

Updating Credal Networks is Approximable in Polynomial Time

Credal networks relax the precise probability requirement of Bayesian networks, enabling a richer representation of uncertainty in the form of closed convex sets of probability measures. The increase in expressiveness comes at the expense of higher computational costs. In this paper, we present a new variable elimination algorithm for exactly computing posterior inferences in extensively specified credal networks, which is empirically shown to outperform a state-of-the-art algorithm. The algorithm is then turned into a provably good approximation scheme, that is, a procedure that for any input is guaranteed to return a solution not worse than the optimum by a given factor. Remarkably, we show that when the networks have bounded treewidth and bounded number of states per variable the approximation algorithm runs in time polynomial in the input size and in the inverse of the error factor, thus being the first known fully polynomial-time approximation scheme for inference in credal networks.

Solving Limited Memory Influence Diagrams

We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and 10^64 solutions. We show that these problems are NP-hard even if the underlying graph structure of the problem has low treewidth and the variables take on a bounded number of states, and that they admit no provably good approximation if variables can take on an arbitrary number of states.

Algorithms for Hidden Markov Models With Imprecisely Specified Parameters

Hidden Markov models (HMMs) are widely used models for sequential data. As with other probabilistic graphical models, they require the specification of precise probability values, which can be too restrictive for some domains, especially when data are scarce or costly to acquire. We present a generalized version of HMMs, whose quantification can be done by sets of, instead of single, probability distributions. Our models have the ability to suspend judgment when there is not enough statistical evidence, and can serve as a sensitivity analysis tool for standard non-stationary HMMs. Efficient inference algorithms are developed to address standard HMM usage such as the computation of likelihoods and most probable explanations. Experiments with real data show that the use of imprecise probabilities leads to more reliable inferences without compromising efficiency.

Solving Limited Memory Influence Diagrams

We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and 10^64 solutions. We show that the problem is NP-hard even if the underlying graph structure of the problem has small treewidth and the variables take on a bounded number of states, but that a fully polynomial time approximation scheme exists for these cases. Moreover, we show that the bound on the number of states is a necessary condition for any efficient approximation scheme.

The Complexity of Approximately Solving Influence Diagrams

Influence diagrams allow for intuitive and yet precise description of complex situations involving decision making under uncertainty. Unfortunately, most of the problems described by influence diagrams are hard to solve. In this paper we discuss the complexity of approximately solving influence diagrams. We do not assume no-forgetting or regularity, which makes the class of problems we address very broad. Remarkably, we show that when both the treewidth and the cardinality of the variables are bounded the problem admits a fully polynomial-time approximation scheme.

Anytime Marginal MAP Inference

This paper presents a new anytime algorithm for the marginal MAP problem in graphical models of bounded treewidth. We show asymptotic convergence and theoretical error bounds for any fixed step. Experiments show that it compares well to a state-of-the-art systematic search algorithm.

Hidden Markov Models With Set-Valued Parameters

Hidden Markov models (HMMs) are widely used probabilistic models of sequential data. As with other probabilistic models, they require the specification of local conditional probability distributions, whose assessment can be too difficult and error-prone, especially when data are scarce or costly to acquire. The imprecise HMM (iHMM) generalizes HMMs by allowing the quantification to be done by sets of, instead of single, probability distributions. iHMMs have the ability to suspend judgment when there is not enough statistical evidence, and can serve as a sensitivity analysis tool for standard non-stationary HMMs. In this paper, we consider iHMMs under the strong independence interpretation, for which we develop efficient inference algorithms to address standard HMM usage such as the computation of likelihoods and most probable explanations, as well as performing filtering and predictive inference. Experiments with real data show that iHMMs produce more reliable inferences without compromising the computational efficiency.

Numerical modelling of radionuclide migration in near-surface systems

Em todo o mundo são usados, hoje em dia, modelos numéricos hidrogeoquímicos para simular fenómenos naturais e fenómenos decorrentes de actividades antrópicas. Estes modelos ajudam-nos a compreender o ambiente envolvente, a sua variabilidade espacial e evolução temporal. No presente trabalho apresenta-se o desenvolvimento de modelos numéricos hidrogeoquímicos aplicados no contexto do repositório geológico profundo para resíduos nucleares de elevada actividade. A avaliação da performance de um repositório geológico profundo inclui o estudo da evolução geoquímica do repositório, bem como a análise dos cenários de mau funcionamento do repositório, e respectivas consequências ambientais. Se se escaparem acidentalmente radionuclídeos de um repositório, estes poderão atravessar as barreiras de engenharia e barreiras naturais que constituem o repositório, atingindo eventualmente, os ecosistemas superficiais. Neste caso, os sedimentos subsuperficiais constituem a última barreira natural antes dos ecosistemas superficiais. No presente trabalho foram desenvolvidos modelos numéricos que integram processos biogeoquímicos, geoquímicos, hidrodinâmicos e de transporte de solutos, para entender e quantificar a influência destes processos na mobilidade de radionuclídeos em sistemas subsuperficiais. Os resultados alcançados reflectem a robustez dos instrumentos numéricos utilizados para desenvolver simulações descritivas e predictivas de processos hidrogeoquímicos que influenciam a mobilidade de radionuclídeos. A simulação (descritiva) de uma experiência laboratorial revela que a actividade microbiana induz a diminuição do potencial redox da água subterrânea que, por sua vez, favorece a retenção de radionuclídeos sensíveis ao potencial redox, como o urânio. As simulações predictivas indicam que processos de co-precipitação com minerais de elementos maioritários, precipitação de fases puras, intercâmbio catiónico e adsorção à superfície de minerais favorecem a retenção de U, Cs, Sr e Ra na fase sólida de uma argila glaciar e uma moreia rica em calcite. A etiquetagem dos radionuclídeos nas simulações numéricas permitiu concluir que a diluição isotópica joga um papel importante no potencial impacte dos radionuclídeos nos sistemas subsuperficiais. A partir dos resultados das simulações numéricas é possivel calcular coeficientes de distribuição efectivos. Esta metodologia proporciona a simulação de ensaios de traçadores de longa duração que não seriam exequíveis à escala da vida humana. A partir destas simulações podem ser obtidos coeficientes de retardamento que são úteis no contexto da avaliação da performance de repositórios geológicos profundos.

Governance structures and performance management systems in universities: a comparative study between the UK and Portugal

À semelhança do que aconteceu em muitas instituições públicas, as universidades têm enfrentado pressões crescentes para mudar, tendo de repensar as suas formas de governança e de gestão, dando mais ênfase à implementação de sistemas de gestão do desempenho (SGD). Apesar de existirem vários estudos sobre o desempenho, estes têm ignorado o uso dado à informação recolhida. Além disso, e apesar de terem ocorrido várias reformas na governança destas instituições, existem ainda poucos estudos que relacionam a governança e o desempenho. Assim, esta pesquisa visa explorar a forma como as universidades medem, reportam e gerem o desempenho e como as estruturas de governança se relacionam com estas práticas. Para alcançar o objetivo proposto, um estudo comparativo entre universidades britânicas e portuguesas foi realizado. Os dados foram recolhidos através da utilização de uma metodologia qualitativa, sendo os métodos utilizados a análise documental e entrevistas semi-estruturadas a membros dos órgãos de governo e gestão de cada instituição. A análise dos dados mostrou a inexistência de um sistema completamente integrado de gestão de desempenho (SGD) em ambas as instituições, essencialmente devido à falta de práticas de gestão de desempenho. De facto, apesar de alguns dos entrevistados terem reportado o "uso positivo" de dados sobre o desempenho, alguns relataram o "não uso" desses dados, principalmente em relação ao desempenho individual, e outros o "mau uso" dessa informação, tendo sido reportadas práticas de gaming e deturpação dos resultados. Como forma de ultrapassar alguns destes problemas, verificou-se a co-existência de duas estruturas de governança: uma 'formal', da qual fazem parte todos os órgão de governo, com um valor mais 'simbólico'; e uma estrutura 'paralela', constituída por órgãos mais ágeis, que gerem a universidade no dia a dia. Verificou-se terem sido vários os fatores a afetarem, negativa e positivamente, os SGD em ambas as instituições, tendo sido rotulados de "inibidores" e "determinantes", respetivamente. A pesquisa mostrou que, apesar de as estruturas de governança serem importantes para a implementação e funcionamento de um SGD, há outros fatores que precisam de ser levados em consideração, nomeadamente, o nível de comunicação e o nível de envolvimento dos atores no processo. Estes dois fatores são considerados relevantes para a integração bem sucedida de práticas de medição, reporte e gestão de desempenho. Esta integração, juntamente com outras mudanças que ocorreram em termos de governança, contribuirá certamente para que se passe de um sistema em que se governa o desempenho para um sistema em que se governa para o desempenho.

Wireless networks congestion control

Congestion control in wireless networks is an important and open issue. Previous research has proven the poor performance of the Transport Control Protocol (TCP) in such networks. The factors that contribute to the poor performance of TCP in wireless environments concern its unsuitability to identify/detect and react properly to network events, its TCP window based ow control algorithm that is not suitable for the wireless channel, and the congestion collapse due to mobility. New rate based mechanisms have been proposed to mitigate TCP performance in wired and wireless networks. However, these mechanisms also present poor performance, as they lack of suitable bandwidth estimation techniques for multi-hop wireless networks. It is thus important to improve congestion control performance in wireless networks, incorporating components that are suitable for wireless environments. A congestion control scheme which provides an e - cient and fair sharing of the underlying network capacity and available bandwidth among multiple competing applications is crucial to the definition of new e cient and fair congestion control schemes on wireless multi-hop networks. The Thesis is divided in three parts. First, we present a performance evaluation study of several congestion control protocols against TCP, in wireless mesh and ad-hoc networks. The obtained results show that rate based congestion control protocols need an eficient and accurate underlying available bandwidth estimation technique. The second part of the Thesis presents a new link capacity and available bandwidth estimation mechanism denoted as rt-Winf (real time wireless inference). The estimation is performed in real-time and without the need to intrusively inject packets in the network. Simulation results show that rt-Winf obtains the available bandwidth and capacity estimation with accuracy and without introducing overhead trafic in the network. The third part of the Thesis proposes the development of new congestion control mechanisms to address the congestion control problems of wireless networks. These congestion control mechanisms use cross layer information, obtained by rt-Winf, to accurately and eficiently estimate the available bandwidth and the path capacity over a wireless network path. Evaluation of these new proposed mechanisms, through ns-2 simulations, shows that the cooperation between rt-Winf and the congestion control algorithms is able to significantly increase congestion control eficiency and network performance.

Avaliação ecológica do efeito combinado de contaminantes ambientais

The assessment of ecological status of lotic freshwater bodies, based on stringent criteria of classification, has been defined by the Water Framework Directive (WFD), as a result of the implementation and optimization of methodologies that integrate physico-chemical, biological, and hydromorphological parameters. It is recognized that the application of this methodology is not easy, because it requires deep technical and scientific knowledge; it is time consuming in its application involving high financial costs. Thus, the main objective of this study was the development of cheaper and faster complementary methodologies that may contribute to the technical application of the classification criteria defined by the WFD, achieving the same final results of evaluation. In order to achieve this main goal, the river Mau, a small mountain river subjected to different stressors (eg, metals, pesticides), was established as the main sampling area. This thesis reviewed the historical development of various biotic indexes and its application in assessing water quality, especially highlighting the new paradigm defined by the WFD, and the corresponding actions developed for optimization and intercalibration of methodologies, evaluating the final state of water bodies. The ecological spatiotemporal characterization of the river Mau focused on the application of the WFD methodology, using at this stage only macroinvertebrates collected during four seasons. Results were compared with historical data of the last three years and they demonstrated that the river is in good condition. However, the ecological quality decreased at certain locations indicating that organisms were subjected to some type of disturbance. As the ecological quality can be conditioned by pulses of contamination from the sediments, in environmental adverse conditions, assays were performed with elutriates, obtained from sediments collected near the mining complex Braçal-Palhal. Results showed that this method was effective achieving the state of contamination, which may be important in prioritizing/scoring of critical areas within river ecosystems potentially impacted, using the WFD methodology. However, this methodology requires the collection of sediment which can promote the modification and / or loss of contaminants. To solve this potential problem, we developed a new methodology to obtain similar results. For this, we used a benthic microalga, belonging to the Portuguese flora, sensitive to organic pollution and metals. This methodology was optimized for application in situ, by immobilization of diatom in calcium alginate beads. The results showedthat their sensitivity and normal growth rate are similar to data obtained when used free cells of diatom. This new methodology allowed the achievement of a very quick response on the degree of contamination of a site, providing a complementary methodology to WFD.

Coping, fatores psicossociais e capacidade para o trabalho

O coping desempenha um importante papel na saúde individual e rendimento organizacional. Tal como o coping é um tema de interesse recente e promissor na área da psicologia da saúde ocupacional, também os fatores psicossociais do trabalho têm ganho um crescente interesse no domínio da saúde ocupacio-nal. No entanto, pouco se sabe acerca das configurações de coping mais salu-togénicas no mundo do trabalho, e menos ainda acerca da participação dos fatores psicossociais na definição das mesmas. Esta última perspetiva assume os fatores psicossociais não como causas de stresse, mas enquanto recursos de coping. Com o presente estudo, desejávamos saber se as pessoas com melhor saúde no trabalho usam estratégias de coping diferentes daquelas com menor saúde, bem como se a escolha dessas estratégias é influenciada pelos fatores psicossociais do trabalho. Pretendia-se ainda caracterizar o coping dos trabalhadores mais saudáveis e produtivos, e perceber que fatores psicosso-ciais contribuem para o mesmo. Foram estudados 2960 profissionais de traba-lhos mentais, sendo 31% (n=909) profissionais de saúde e 69% (n=2051) pro-fissionais de outras áreas. Além das variáveis sociodemográficas, avaliou-se o coping (Brief COPE), os fatores psicossociais do trabalho (COPSOQ) e o índi-ce de capacidade para o trabalho (ICT), enquanto indicador de saúde ocupa-cional. Desenhou-se um estudo transversal e quantitativo, com níveis de análi-se descritivo, exploratório, correlacional e preditivo. Os resultados confirmaram as hipóteses de estudo e permitem concluir genericamente que (1) o coping diferencia e determina a saúde no trabalho, (2) os fatores psicossociais do trabalho influenciam o coping, ainda que modestamente, e (3) o coping dos profissionais de saúde é estruturalmente diferente do coping dos não profissio-nais de saúde. Os resultados possibilitam ainda estabelecer perfis de bom e de mau coping no trabalho e concorrem para definir estratégias de intervenção psicológica para o desenvolvimento do reportório de coping dos profissionais de trabalhos mentais, bem como estratégias de gestão (de recursos humanos) para a melhoria do ambiente psicossocial do trabalho. Por fim, os resultados estimulam algumas considerações teóricas e metodológicas que sugerem direções futuras para o estudo dos efeitos da relação do coping com o ambien-te psicossocial do trabalho na saúde e bem-estar individual, no rendimento organizacional e na qualidade de vida no trabalho. Julgamos, por fim, que os resultados obtidos podem contribuir para aprimorar os mecanismos de coping dos profissionais e para ajustar o ambiente psicossocial do trabalho.

Estudo da degradação do tempo de vida das fibras óticas e o seu impacte no desempenho das redes de comunicações

Este trabalho focou-se no estudo do impacte das condições ambientais, de instalação e de utilização na degradação da fibra ótica, que frequentemente resultam na redução do desempenho das fibras óticas. Entre este fatores, foram estudados os efeitos de ambientes agressivos para o revestimento da fibra, nomeadamente no tempo de vida e resistência. Foi também estudado o efeito da propagação de sinais óticos de elevadas potências em curvaturas apertadas e a sua influência na degradação do desempenho da fibra ótica. Ainda neste âmbito, foi também estudado o desempenho de fibras óticas insensíveis a curvtura e fibras dopadas com Érbio, sendo analisada a dinâmica do efeito rastilho nestas fibras. Como parte integrante das redes óticas, os conetores óticos são de extrema importância na sua estrutura. O seu desempenho será refletido na qualidade do serviço da rede, e por isso é determinante estudar os fatores que contribuem para a sua degradação e mau funcionamento. Assim, este trabalho apresenta um estudo do comportamento de conetores óticos perante situações de mau manuseamento (como são limpeza insuficiente e degradação física da face final). Em adição foi também dado ênfase à reutilização de fibra danificada pelo efeito rastilho no desenvolvimento de sensores, passíveis de serem utilizados na monitorização de índice de refração, pressão hidrostática, tensão ou alta temperatura. Este procedimento surge como uma solução de baixo custo para o desenvolvimento de sensores em fibra ótica a partir de fibra danificada e inutilizável para as suas habituais aplicações em transmissão e/ou reflexão de sinais óticos.