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.

State retrenchment and administrative reform in Ireland: Probing comparative policy paradigms

Policy choices in response to crisis may carry consequences both for distributive outcomes and for the future policy capacity of the state itself. In this paper, we use conceptual heuristics to interpret policy practice. We examine the underlying policy paradigms shaping Irish government decisions in the aftermath of the European financial and economic crisis. We distinguish between two such paradigms- market-conforming and social equity - and apply them to three reform themes: reconfiguration of public budgets, the public service pay bargain, and the organizational profile of state competences. Our findings entail lessons for understanding the malleability of policy choice, and how state policy choices in response to crisis are framed and implemented.

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.

Expanded iron uta spectra - Probing the thermal stability limits in AGN clouds

The Fe unresolved transition arrays (UTAs) produce prominent features in the 15-17 Å wavelength range in the spectra of active galactic nuclei (AGNs). Here, we present new calculations of the energies and oscillator strengths of inner-shell lines from Fe XIV, Fe XV, and Fe XVI. These are crucial ions since they are dominant at inflection points in the gas thermal stability curve, and UTA excitation followed by autoionization is an important ionization mechanism for these species. We incorporate these, and data reported in previous papers, into the plasma simulation code Cloudy. This updated physics is subsequently employed to reconsider the thermally stable phases in absorbing media in AGNs. We show how the absorption profile of the Fe XIV UTA depends on density, due to the changing populations of levels within the ground configuration. © 2013. The American Astronomical Society. All rights reserved.

Photocatalytic activity indicator inks for the probing a wide range of surfaces

Three photocatalyst inks based on the redox dyes, Resazurin (Rz), Basic Blue 66 (BB66) and Acid Violet 7 (AV7), are used to assess the photocatalytic activities of a variety of different materials, such as commercial paint, tiles and glass and laboratory made samples of sol–gel coated glass and paint, which collectively exhibit a wide range of activities that cannot currently be probed by any one of the existing ISO tests. Unlike the ISO tests, the ink tests are fast (typically <10 min), simple to employ and inexpensive. Previous work indicates that the Rz ink test at least correlates linearly with other photocatalytic tests such as the photomineralisation of stearic acid. The average time to bleach 90% of the key RGB colour component of the ink, red for Rz and BB66 inks and green for AV7 ink, is determined, ttb(90), for eight samples of each of the different materials tested. Five laboratories conducted the tests and the results revealed an average repeatability and reproducibility of: ca. 11% and ca 21%, respectively, which compare well with those reported for the current ISO tests. Additional work on commercial self-cleaning glass using an Rz ink showed that the change in the red component of the RGB image of the ink correlated linearly with that of the change of absorbance at 608 nm, as measured using UV/vis spectroscopy, and the change in the a* component of the Lab colour analysis of the ink, as measured using diffuse reflectance spectroscopy. As a consequence, all three methods generate the same ttb(90). The advantages of the RGB digital image analysis method are discussed briefly.

Characterization of x-ray lens for use in probing high energy density states of matter

By using polycapillary lenses to focus laser-produced x-ray sources to high intensities, an improvement in signal-to-noise ratio can be achieved. Here the He-alpha line emission produced by driving a titanium backlighter target is focused by a polycapillary lens and the output characterized. The x-ray spot is measured to have a peak intensity of 4.5 x 10(7) photons, with a total photon count of 8.8 x 10(8) in 0.13 +/- 0.01 mm(2). This setup is equivalent to placing the backlighter target 3 mm from the sample with a 600 mu m diameter pinhole. The polycapillary lens enables the placement of the backlighter target at a much larger distance from the sample to be studied and therefore has the ability to greatly improve the signal-to-noise ratio on detectors. We demonstrate this with two simple diffraction experiments using pyrolytic graphite and polycrystalline aluminium.

Probing The effects of Experimental Conditions on the Character of Drug-Polymer Phase Diagrams Constructed Using Flory-Huggins Theory

Purpose: Amorphous drug-polymer solid dispersions have been found to result in improved drug dissolution rates when compared to their crystalline counterparts. However, when the drug exists in the amorphous form it will possess a higher Gibb’s free energy than its associated crystalline state and can recrystallize. Drug-polymer phase diagrams constructed through the application of the Flory Huggins (F-H) theory contain a wealth of information regarding thermodynamic and kinetic stability of the amorphous drug-polymer system. This study was aimed to evaluate the effects of various experimental conditions on the solubility and miscibility detections of drug-polymer binary system. Methods: Felodipine (FD)-Polyvinylpyrrolidone (PVP) K15 (PVPK15) and FD-Polyvinylpyrrolidone/vinyl acetate (PVP/VA64) were the selected systems for this research. Physical mixtures with different drug loadings were mixed and ball milled. These samples were then processed using Differential Scanning Calorimetry (DSC) and measurements of melting point (Tend) and glass transition (Tg) were detected using heating rates of 0.5, 1.0 and 5.0°C/min. Results: The melting point depression data was then used to calculate the F-H interaction parameter (χ) and extrapolated to lower temperatures to complete the liquid–solid transition curves. The theoretical binodal and spinodal curves were also constructed which were used to identify regions within the phase diagram. The effects of polymer selection, DSC heating rate, time above parent polymer Tg and polymer molecular weight were investigated by identifying amorphous drug miscibility limits at pharmaceutically relevant temperatures. Conclusion: The potential implications of these findings when applied to a non-ambient processing method such as Hot Melt Extrusion (HME) are also discussed.