New Complexity Results for MAP in Bayesian Networks

This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. It is demonstrated that the problem remains hard even in networks with very simple topology, such as binary polytrees and simple trees (including the Naive Bayes structure), which extends previous complexity results. Furthermore, a Fully Polynomial Time Approximation Scheme for MAP in networks with bounded treewidth and bounded number of states per variable is developed. Approximation schemes were thought to be impossible, but here it is shown otherwise under the assumptions just mentioned, which are adopted in most applications.

NP-hardness of MAP in Ternary Tree Bayesian Networks

This paper strengthens the NP-hardness result for the (partial) maximum a posteriori (MAP) problem in Bayesian networks with topology of trees (every variable has at most one parent) and variable cardinality at most three. MAP is the problem of querying the most probable state configuration of some (not necessarily all) of the network variables given evidence. It is demonstrated that the problem remains hard even in such simplistic networks.

Propositional and Relational Bayesian Networks Associated with Imprecise and Qualitative Probabilistic Assessments

This paper investigates a representation language with flexibility inspired by probabilistic logic and compactness inspired by relational Bayesian networks. The goal is to handle propositional and first-order constructs together with precise, imprecise, indeterminate and qualitative probabilistic assessments. The paper shows how this can be achieved through the theory of credal networks. New exact and approximate inference algorithms based on multilinear programming and iterated/loopy propagation of interval probabilities are presented; their superior performance, compared to existing ones, is shown empirically.

The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages

We study the computational complexity of finding maximum a posteriori configurations in Bayesian networks whose probabilities are specified by logical formulas. This approach leads to a fine grained study in which local information such as context-sensitive independence and determinism can be considered. It also allows us to characterize more precisely the jump from tractability to NP-hardness and beyond, and to consider the complexity introduced by evidence alone.

Proposing the deep dynamic Bayesian network as a future computer based medical system

The development of new learning models has been of great importance throughout recent years, with a focus on creating advances in the area of deep learning. Deep learning was first noted in 2006, and has since become a major area of research in a number of disciplines. This paper will delve into the area of deep learning to present its current limitations and provide a new idea for a fully integrated deep and dynamic probabilistic system. The new model will be applicable to a vast number of areas initially focusing on applications into medical image analysis with an overall goal of utilising this approach for prediction purposes in computer based medical systems.

Statistical Monitoring of Dynamic Multivariate Processes: Part II: Identifying Fault Magnitude and Signature

This paper builds on work presented in the first paper, Part 1 [1] and is of equal significance. The paper proposes a novel compensation method to preserve the integrity of step-fault signatures prevalent in various processes that can be masked during the removal of both auto- and cross correlation. Using industrial data, the paper demonstrates the benefit of the proposed method, which is applicable to chemical, electrical, and mechanical process monitoring. This paper, (and Part 1 [1]), has led to further work supported by EPSRC grant GR/S84354/01 involving kernel PCA methods.

Microarray-based classifiers and prognosis models identify subgroups with distinct clinical outcomes and high risk of AML transformation of myelodysplastic syndrome

The diagnosis of myelodysplastic syndrome (MDS) currently relies primarily on the morphologic assessment of the patient's bone marrow and peripheral blood cells. Moreover, prognostic scoring systems rely on observer-dependent assessments of blast percentage and dysplasia. Gene expression profiling could enhance current diagnostic and prognostic systems by providing a set of standardized, objective gene signatures. Within the Microarray Innovations in LEukemia study, a diagnostic classification model was investigated to distinguish the distinct subclasses of pediatric and adult leukemia, as well as MDS. Overall, the accuracy of the diagnostic classification model for subtyping leukemia was approximately 93%, but this was not reflected for the MDS samples giving only approximately 50% accuracy. Discordant samples of MDS were classified either into acute myeloid leukemia (AML) or

Care and Management of Ancient Stone Monuments During Environmental Change

Ancient stone monuments (ASMs), such as standing stones and rock art panels, are powerful and iconic expressions of Britain’s rich prehistoric past that have major economic and tourism value. However, ASMs are under pressure due to increasing anthropogenic exposure and changing climatic conditions, which accelerate their rates of disrepair. Although scientific data exists on the integrity of stone monuments, most applies to “built” systems; therefore, additional work specific to ASMs in the countryside is needed to develop better-informed safeguarding strategies. Here, we use Neolithic and Bronze Age rock art panels across Northern England as a case study for delineating ASM management actions required to enhance monument preservation. The state of the rock art is described first, including factors that led to current conditions. Rock art management approaches then are described within the context of future environments, which models suggest to be more dynamic and locally variable. Finally, a Condition Assessment and Risk Evaluation (CARE) scheme is proposed to help prioritise interventions; an example of which is provided based on stone deterioration at Petra in Jordon. We conclude that more focused scientific and behavioural data, specific to deterioration mechanisms, are required for an ASM CARE scheme to be successful.

Generalized loopy 2U: A new algorithm for approximate inference in credal networks

Credal networks generalize Bayesian networks by relaxing the requirement of precision of probabilities. Credal networks are considerably more expressive than Bayesian networks, but this makes belief updating NP-hard even on polytrees. We develop a new efficient algorithm for approximate belief updating in credal networks. The algorithm is based on an important representation result we prove for general credal networks: that any credal network can be equivalently reformulated as a credal network with binary variables; moreover, the transformation, which is considerably more complex than in the Bayesian case, can be implemented in polynomial time. The equivalent binary credal network is then updated by L2U, a loopy approximate algorithm for binary credal networks. Overall, we generalize L2U to non-binary credal networks, obtaining a scalable algorithm for the general case, which is approximate only because of its loopy nature. The accuracy of the inferences with respect to other state-of-the-art algorithms is evaluated by extensive numerical tests.

Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks

Motivated by the need for designing efficient and robust fully-distributed computation in highly dynamic networks such as Peer-to-Peer (P2P) networks, we study distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy {\em churn} (i.e., nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a {\em constant} degree graph with {\em high expansion} even under {\em continuous high adversarial} churn. Our protocol can tolerate a churn rate of up to $O(n/\poly\log(n))$ per round (where $n$ is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only $O(\poly\log(n))$ overhead for topology maintenance: only polylogarithmic (in $n$) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.

Towards a knowledge-based approach for effective decision-making in railway safety

Purpose – This paper aims to contribute towards understanding how safety knowledge can be elicited from railway experts for the purposes of supporting effective decision-making. Design/methodology/approach – A consortium of safety experts from across the British railway industry is formed. Collaborative modelling of the knowledge domain is used as an approach to the elicitation of safety knowledge from experts. From this, a series of knowledge models is derived to inform decision-making. This is achieved by using Bayesian networks as a knowledge modelling scheme, underpinning a Safety Prognosis tool to serve meaningful prognostics information and visualise such information to predict safety violations. Findings – Collaborative modelling of safety-critical knowledge is a valid approach to knowledge elicitation and its sharing across the railway industry. This approach overcomes some of the key limitations of existing approaches to knowledge elicitation. Such models become an effective tool for prediction of safety cases by using railway data. This is demonstrated using passenger–train interaction safety data. Practical implications – This study contributes to practice in two main directions: by documenting an effective approach to knowledge elicitation and knowledge sharing, while also helping the transport industry to understand safety. Social implications – By supporting the railway industry in their efforts to understand safety, this research has the potential to benefit railway passengers, staff and communities in general, which is a priority for the transport sector. Originality/value – This research applies a knowledge elicitation approach to understanding safety based on collaborative modelling, which is a novel approach in the context of transport.