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.

New Results for the MAP Problem 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. First, 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). Such proofs extend previous complexity results for the problem. Inapproximability results are also derived in the case of trees if the number of states per variable is not bounded. Although the problem is shown to be hard and inapproximable even in very simple scenarios, a new exact algorithm is described that is empirically fast in networks of bounded treewidth and bounded number of states per variable. The same algorithm is used as basis of a Fully Polynomial Time Approximation Scheme for MAP under such assumptions. Approximation schemes were generally thought to be impossible for this problem, but we show otherwise for classes of networks that are important in practice. The algorithms are extensively tested using some well-known networks as well as random generated cases to show their effectiveness.

Improving parameter learning of Bayesian nets from incomplete data

This paper addresses the estimation of parameters of a Bayesian network from incomplete data. The task is usually tackled by running the Expectation-Maximization (EM) algorithm several times in order to obtain a high log-likelihood estimate. We argue that choosing the maximum log-likelihood estimate (as well as the maximum penalized log-likelihood and the maximum a posteriori estimate) has severe drawbacks, being affected both by overfitting and model uncertainty. Two ideas are discussed to overcome these issues: a maximum entropy approach and a Bayesian model averaging approach. Both ideas can be easily applied on top of EM, while the entropy idea can be also implemented in a more sophisticated way, through a dedicated non-linear solver. A vast set of experiments shows that these ideas produce significantly better estimates and inferences than the traditional and widely used maximum (penalized) log-likelihood and maximum a posteriori estimates. In particular, if EM is adopted as optimization engine, the model averaging approach is the best performing one; its performance is matched by the entropy approach when implemented using the non-linear solver. The results suggest that the applicability of these ideas is immediate (they are easy to implement and to integrate in currently available inference engines) and that they constitute a better way to learn Bayesian network parameters.

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.

The Inferential Complexity of Bayesian and Credal Networks

This paper presents new results on the complexity of graph-theoretical models that represent probabilities (Bayesian networks) and that represent interval and set valued probabilities (credal networks). We define a new class of networks with bounded width, and introduce a new decision problem for Bayesian networks, the maximin a posteriori. We present new links between the Bayesian and credal networks, and present new results both for Bayesian networks (most probable explanation with observations, maximin a posteriori) and for credal networks (bounds on probabilities a posteriori, most probable explanation with and without observations, maximum a posteriori).

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.

A New Android Malware Detection Method Using Bayesian Classification

Mobile malware has been growing in scale and complexity as smartphone usage continues to rise. Android has surpassed other mobile platforms as the most popular whilst also witnessing a dramatic increase in malware targeting the platform. A worrying trend that is emerging is the increasing sophistication of Android malware to evade detection by traditional signature-based scanners. As such, Android app marketplaces remain at risk of hosting malicious apps that could evade detection before being downloaded by unsuspecting users. Hence, in this paper we present an effective approach to alleviate this problem based on Bayesian classification models obtained from static code analysis. The models are built from a collection of code and app characteristics that provide indicators of potential malicious activities. The models are evaluated with real malware samples in the wild and results of experiments are presented to demonstrate the effectiveness of the proposed approach.

Impact of Residual Transmit RF Impairments on Training-Based MIMO Systems

Radio-frequency (RF) impairments, which intimately exist in wireless communication systems, can severely limit the performance of multiple-input-multiple-output (MIMO) systems. Although we can resort to compensation schemes to mitigate some of these impairments, a certain amount of residual impairments always persists. In this paper, we consider a training-based point-to-point MIMO system with residual transmit RF impairments (RTRI) using spatial multiplexing transmission. Specifically, we derive a new linear channel estimator for the proposed model, and show that RTRI create an estimation error floor in the high signal-to-noise ratio (SNR) regime. Moreover, we derive closed-form expressions for the signal-to-noise-plus-interference ratio (SINR) distributions, along with analytical expressions for the ergodic achievable rates of zero-forcing, maximum ratio combining, and minimum mean-squared error receivers, respectively. In addition, we optimize the ergodic achievable rates with respect to the training sequence length and demonstrate that finite dimensional systems with RTRI generally require more training at high SNRs than those with ideal hardware. Finally, we extend our analysis to large-scale MIMO configurations, and derive deterministic equivalents of the ergodic achievable rates. It is shown that, by deploying large receive antenna arrays, the extra training requirements due to RTRI can be eliminated. In fact, with a sufficiently large number of receive antennas, systems with RTRI may even need less training than systems with ideal hardware.

Minimal residual disease detection in childhood acute lymphoblastic leukaemia patients at multiple time-points reveals high levels of concordance between molecular and immunophenotypic approaches

In this single centre study of childhood acute lymphoblastic leukaemia (ALL) patients treated on the Medical Research Council UKALL 97/99 protocols, it was determined that minimal residual disease (MRD) detected by real time quantitative polymerase chain reaction (RQ-PCR) and 3-colour flow cytometry (FC) displayed high levels of qualitative concordance when evaluated at multiple time-points during treatment (93.38%), and a combined use of both approaches allowed a multi time-point evaluation of MRD kinetics for 90% (53/59) of the initial cohort. At diagnosis, MRD markers with sensitivity of at least 0.01% were identified by RQ-PCR detection of fusion gene transcripts, IGH/TRG rearrangements, and FC. Using a combined RQ-PCR and FC approach, the evaluation of 367 follow-up BM samples revealed that the detection of MRD >1% at Day 15 (P = 0.04), >0.01% at the end of induction (P = 0.02), >0.01% at the end of consolidation (P = 0.01), >0.01% prior to the first delayed intensification (P = 0.01), and >0.1% prior to the second delayed intensification and continued maintenance (P = 0.001) were all associated with relapse and, based on early time-points (end of induction and consolidation) a significant log-rank trend (P = 0.0091) was noted between survival curves for patients stratified into high, intermediate and low-risk MRD groups.

Wilms' tumor gene 1 (WT1) expression in childhood acute lymphoblastic leukemia:a wide range of WT1 expression levels, its impact on prognosis and minimal residual disease monitoring

Wilms' tumor gene 1 (WT1) is overexpressed in the majority (70-90%) of acute leukemias and has been identified as an independent adverse prognostic factor, a convenient minimal residual disease (MRD) marker and potential therapeutic target in acute leukemia. We examined WT1 expression patterns in childhood acute lymphoblastic leukemia (ALL), where its clinical implication remains unclear. Using a real-time quantitative PCR designed according to Europe Against Cancer Program recommendations, we evaluated WT1 expression in 125 consecutively enrolled patients with childhood ALL (106 BCP-ALL, 19 T-ALL) and compared it with physiologic WT1 expression in normal and regenerating bone marrow (BM). In childhood B-cell precursor (BCP)-ALL, we detected a wide range of WT1 levels (5 logs) with a median WT1 expression close to that of normal BM. WT1 expression in childhood T-ALL was significantly higher than in BCP-ALL (P<0.001). Patients with MLL-AF4 translocation showed high WT1 overexpression (P<0.01) compared to patients with other or no chromosomal aberrations. Older children (> or =10 years) expressed higher WT1 levels than children under 10 years of age (P<0.001), while there was no difference in WT1 expression in patients with peripheral blood leukocyte count (WBC) > or =50 x 10(9)/l and lower. Analysis of relapsed cases (14/125) indicated that an abnormal increase or decrease in WT1 expression was associated with a significantly increased risk of relapse (P=0.0006), and this prognostic impact of WT1 was independent of other main risk factors (P=0.0012). In summary, our study suggests that WT1 expression in childhood ALL is very variable and much lower than in AML or adult ALL. WT1, thus, will not be a useful marker for MRD detection in childhood ALL, however, it does represent a potential independent risk factor in childhood ALL. Interestingly, a proportion of childhood ALL patients express WT1 at levels below the normal physiological BM WT1 expression, and this reduced WT1 expression appears to be associated with a higher risk of relapse.

Chimaerism following allogeneic bone marrow transplantation:detection of residual host cells using the polymerase chain reaction

Chimaerism was assessed in five recipients following sex mismatched allogeneic bone marrow transplantation. Techniques included karyotyping of bone marrow cells, dot blot DNA analysis of blood and bone marrow suspensions, and in vitro amplification of DNA by the polymerase chain reaction (PCR) using blood and bone marrow suspensions and stored bone marrow slides. Results of karyotypic analysis suggested complete chimaerism in four patients, while in one patient mixed chimaerism was detected. Mixed chimaerism was also detected, however, in a second patient using PCR and confirmed by dot blot analysis on all tissues examined. PCR is a sensitive tool for investigation of chimaerism following bone marrow transplantation. Since this technique does not require radioactivity, it is an attractive method for use in a clinical laboratory. This technique represents a further development in the use of DNA methodologies in the assessment of haematological disease.

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.