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.

Towards a general framework for information fusion

Depending on the representation setting, different combination rules have been proposed for fusing information from distinct sources. Moreover in each setting, different sets of axioms that combination rules should satisfy have been advocated, thus justifying the existence of alternative rules (usually motivated by situations where the behavior of other rules was found unsatisfactory). These sets of axioms are usually purely considered in their own settings, without in-depth analysis of common properties essential for all the settings. This paper introduces core properties that, once properly instantiated, are meaningful in different representation settings ranging from logic to imprecise probabilities. The following representation settings are especially considered: classical set representation, possibility theory, and evidence theory, the latter encompassing the two other ones as special cases. This unified discussion of combination rules across different settings is expected to provide a fresh look on some old but basic issues in information fusion.

Evidential Fusion for Gender Profiling

Gender profiling is a fundamental task that helps CCTV systems to
provide better service for intelligent surveillance. Since subjects being detected
by CCTVs are not always cooperative, a few profiling algorithms are proposed
to deal with situations when faces of subjects are not available, among which
the most common approach is to analyze subjects’ body shape information. In
addition, there are some drawbacks for normal profiling algorithms considered
in real applications. First, the profiling result is always uncertain. Second, for a
time-lasting gender profiling algorithm, the result is not stable. The degree of
certainty usually varies, sometimes even to the extent that a male is classified
as a female, and vice versa. These facets are studied in a recent paper [16] using
Dempster-Shafer theory. In particular, Denoeux’s cautious rule is applied for
fusion mass functions through time lines. However, this paper points out that if
severe mis-classification is happened at the beginning of the time line, the result
of applying Denoeux’s rule could be disastrous. To remedy this weakness,
in this paper, we propose two generalizations to the DS approach proposed in
[16] that incorporates time-window and time-attenuation, respectively, in applying
Denoeux’s rule along with time lines, for which the DS approach is a special
case. Experiments show that these two generalizations do provide better results
than their predecessor when mis-classifications happen.

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.

Fusion of Static and Temporal Information for Threat Evaluation in Sensor Networks

In many CCTV and sensor network based intelligent surveillance systems, a number of attributes or criteria are used to individually evaluate the degree of potential threat of a suspect. The outcomes for these attributes are in general from analytical algorithms where data are often pervaded with uncertainty and incompleteness. As a result, such individual threat evaluations are often inconsistent, and individual evaluations can change as time elapses. Therefore, integrating heterogeneous threat evaluations with temporal influence to obtain a better overall evaluation is a challenging issue. So far, this issue has rarely be considered by existing event reasoning frameworks under uncertainty in sensor network based surveillance. In this paper, we first propose a weighted aggregation operator based on a set of principles that constraints the fusion of individual threat evaluations. Then, we propose a method to integrate the temporal influence on threat evaluation changes. Finally, we demonstrate the usefulness of our system with a decision support event modeling framework using an airport security surveillance scenario.

Relationships between EEA1 binding partners and their role in endosome fusion

Homotypic fusion between early endosomes requires the phosphatidylinositol 3-phosphate (PI3P)-binding protein, Early Endosomal Autoantigen 1 (EEA1). We have investigated the role of other proteins that interact with EEA1 in the fusion of early endosomes derived from Baby Hamster Kidney (BHK) cells. We confirm a requirement for syntaxin 13, but additionally show that the assay is equally sensitive to reagents specifically targeted against syntaxin 6. Binding of EEA1 to immobilised GST-syntaxin 6 and 13 was directly compared; only syntaxin 6 formed a stable complex with EEA1. Early endosome fusion requires the release of intravesicular calcium, and calmodulin plays a vital role in the fusion pathway, as judged by sensitivity to antagonists. We demonstrate that both EEA1 and syntaxin 13 interact with calmodulin. In the case of EEA1, binding to calmodulin requires an IQ domain, which is adjacent to a C-terminal FYVE domain that specifically binds to PI3P. We have assessed the influence of protein binding partners on EEA1 interaction with PI3P and find that both calmodulin and rab5-GTP are antagonistic to PI3P binding, whilst syntaxins 6 and 13 have no effect. These studies reveal a complex network of interactions between the proteins required for endosome fusion.

Regulation of endosome fusion

Homotypic fusion between early endosomes can be reconstituted in vitro. By using wortmannin and LY294002, inhibitors of phosphatidylinositol (Pl) 3-kinase, a requirement for this activity has been established in order for fusion to proceed efficiently. It has been shown that Pl 3-kinase activity is required downstream of rab5 activation, although a large excess of activated rab5 can overcome wortmannin inhibition. A series of experiments have also been performed which indicate a role for early endosomal autoantigen 1 (EEA1) in determining fusion efficiency. EEA1 dissociates from membranes following wortmannin treatment. It is proposed that the requirement of endosome fusion for Pl 3-kinase activity is to promote the association of EEA1 with endosomes.

Involvement of the endosomal autoantigen EEA1 in homotypic fusion of early endosomes

In mammalian cells, fusion between early endocytic vesicles has been shown to require the ubiquitous intracellular fusion factors N-ethylmaleimide-sensitive factor (NSF) and alpha-SNAP, as well as a factor specific for early endosomes, the small GTPase Rab5 [1-3]. We have previously demonstrated an additional requirement for phosphatidylinositol 3-kinase (PI 3-kinase) activity [4]. The membrane association of early endosomal antigen 1 (EEA1), a specific marker of early endosomes [5,6], has recently been shown to be similarly dependent on PI 3-kinase activity [7], and we therefore postulated that it might be involved in endosome fusion. Here, we present evidence that EEA1 has an important role in determining the efficiency of endosome fusion in vitro. Both the carboxy-terminal domain of EEA1 (residues 1098-1411) and specific antibodies against EEA1 inhibited endosome fusion when included in an in vitro assay. Furthermore, depletion of EEA1, both from the membrane fraction used in the assay by washing with salt and from the cytosol using an EEA1-specific antibody, resulted in inhibition of endosome fusion. The involvement of EEA1 in endosome fusion accounts for the sensitivity of the endosome fusion assay to inhibitors of PI 3-kinase.

Inhibition of endosome fusion by wortmannin persists in the presence of activated Rab5

Rab5-dependent endosome fusion is sensitive to the phosphoinositide 3-kinase inhibitor, wortmannin. It has been proposed that phosphoinositide 3-kinase activity may be required for activation of rab5 by influencing its nucleotide cycle such as to promote its active GTP state. In this report we demonstrate that endosome fusion remains sensitive to wortmannin despite preloading of endosomes with stimulatory levels of a GTPase-defective mutant rab5(Q79L) or of a xanthosine triphosphate-binding mutant, rab5(D136N), in the presence of the nonhydrolysable analogue XTPgammaS. These results suggest that activation of rab5 cannot be the principal function of the wortmannin-sensitive factor on the endosome fusion pathway. This result is extrapolated to all GTPases by demonstrating that endosome fusion remains wortmannin sensitive despite prior incubation with the nonhydrolysable nucleotide analogue GTPgammaS. Consistent with these results, direct measurement of clathrin-coated vesicle-stimulated nucleotide dissociation from exogenous rab5 was insensitive to the presence of wortmannin. A large excess of rab5(Q79L), beyond levels required for maximal stimulation of the fusion assay, afforded protection against wortmannin inhibition, and partial protection was also observed with an excess of wild-type rab5 independent of GTPgammaS.