title: Probabilistic Reasoning about Actions in Nonmonotonic Causal Theories

abstract: We present the language {m P}{cal C}+ for probabilistic reasoning about actions, which is a generalization of the action language {cal C}+ that allows to deal with probabilistic as well as nondeterministic effects of actions. We define a formal semantics of {m P}{cal C}+ in terms of probabilistic transitions between sets of states. Using a concept of a history and its belief state, we then show how several important problems in reasoning about actions can be concisely formulated in our formalism.


title: A New Algorithm for Maximum Likelihood Estimation in Gaussian Graphical Models for Marginal Independence

abstract: Graphical models with bi-directed edges (<->) represent marginal independence: the absence of an edge between two vertices indicates that the corresponding variables are marginally independent. In this paper, we consider maximum likelihood estimation in the case of continuous variables with a Gaussian joint distribution, sometimes termed a covariance graph model. We present a new fitting algorithm which exploits standard regression techniques and establish its convergence properties. Moreover, we contrast our procedure to existing estimation methods.


title: A Simple Insight into Iterative Belief Propagation's Success

abstract: In Non - ergodic belief networks the posterior belief OF many queries given evidence may become zero.The paper shows that WHEN belief propagation IS applied iteratively OVER arbitrary networks(the so called, iterative OR loopy belief propagation(IBP)) it IS identical TO an arc - consistency algorithm relative TO zero - belief queries(namely assessing zero posterior probabilities). This implies that zero - belief conclusions derived BY belief propagation converge AND are sound.More importantly it suggests that the inference power OF IBP IS AS strong AND AS weak, AS that OF arc - consistency.This allows the synthesis OF belief networks FOR which belief propagation IS useless ON one hand, AND focuses the investigation OF classes OF belief network FOR which belief propagation may be zero - complete.Finally, ALL the above conclusions apply also TO Generalized belief propagation algorithms that extend loopy belief propagation AND allow a crisper understanding OF their power.


title: A Robust Independence Test for Constraint-Based Learning of Causal Structure

abstract: Constraint-based (CB) learning is a formalism for learning a causal network with a database D by performing a series of conditional-independence tests to infer structural information. This paper considers a new test of independence that combines ideas from Bayesian learning, Bayesian network inference, and classical hypothesis testing to produce a more reliable and robust test. The new test can be calculated in the same asymptotic time and space required for the standard tests such as the chi-squared test, but it allows the specification of a prior distribution over parameters and can be used when the database is incomplete. We prove that the test is correct, and we demonstrate empirically that, when used with a CB causal discovery algorithm with noninformative priors, it recovers structural features more reliably and it produces networks with smaller KL-Divergence, especially as the number of nodes increases or the number of records decreases. Another benefit is the dramatic reduction in the probability that a CB algorithm will stall during the search, providing a remedy for an annoying problem plaguing CB learning when the database is small.


title: Loopy Belief Propagation as a Basis for Communication in Sensor Networks

abstract: Sensor networks are an exciting new kind of computer system. Consisting of a large number of tiny, cheap computational devices physically distributed in an environment, they gather and process data about the environment in real time. One of the central questions in sensor networks is what to do with the data, i.e., how to reason with it and how to communicate it. This paper argues that the lessons of the UAI community, in particular that one should produce and communicate beliefs rather than raw sensor values, are highly relevant to sensor networks. We contend that loopy belief propagation is particularly well suited to communicating beliefs in sensor networks, due to its compact implementation and distributed nature. We investigate the ability of loopy belief propagation to function under the stressful conditions likely to prevail in sensor networks. Our experiments show that it performs well and degrades gracefully. It converges to appropriate beliefs even in highly asynchronous settings where some nodes communicate far less frequently than others; it continues to function if some nodes fail to participate in the propagation process; and it can track changes in the environment that occur while beliefs are propagating. As a result, we believe that sensor networks present an important application opportunity for UAI.


title: On Information Regularization

abstract: We formulate a principle for classification with the knowledge of the marginal distribution over the data points (unlabeled data). The principle is cast in terms of Tikhonov style regularization where the regularization penalty articulates the way in which the marginal density should constrain otherwise unrestricted conditional distributions. Specifically, the regularization penalty penalizes any information introduced between the examples and labels beyond what is provided by the available labeled examples. The work extends Szummer and Jaakkola's information regularization (NIPS 2002) to multiple dimensions, providing a regularizer independent of the covering of the space used in the derivation. We show in addition how the information regularizer can be used as a measure of complexity of the classification task with unlabeled data and prove a relevant sample-complexity bound. We illustrate the regularization principle in practice by restricting the class of conditional distributions to be logistic regression models and constructing the regularization penalty from a finite set of unlabeled examples.


title: Probabilistic models for joint clustering and time-warping of multidimensional curves

abstract: In this paper we present a family of algorithms that can simultaneously align and cluster sets of multidimensional curves measured on a discrete time grid. Our approach is based on a generative mixture model that allows non-linear time warping of the observed curves relative to the mean curves within the clusters. We also allow for arbitrary discrete-valued translation of the time axis, random real-valued offsets of the measured curves, and additive measurement noise. The resulting model can be viewed as a dynamic Bayesian network with a special transition structure that allows effective inference and learning. The Expectation-Maximization (EM) algorithm can be used to simultaneously recover both the curve models for each cluster, and the most likely time warping, translation, offset, and cluster membership for each curve. We demonstrate how Bayesian estimation methods improve the results for smaller sample sizes by enforcing smoothness in the cluster mean curves. We evaluate the methodology on two real-world data sets, and show that the DBN models provide systematic improvements in predictive power over competing approaches.


title: Large-Sample Learning of Bayesian Networks is NP-Hard

abstract: In this paper, we provide new complexity results for algorithms that learn discrete-variable Bayesian networks from data. Our results apply whenever the learning algorithm uses a scoring criterion that favors the simplest model able to represent the generative distribution exactly. Our results therefore hold whenever the learning algorithm uses a consistent scoring criterion and is applied to a sufficiently large dataset. We show that identifying high-scoring structures is hard, even when we are given an independence oracle, an inference oracle, and/or an information oracle. Our negative results also apply to the learning of discrete-variable Bayesian networks in which each node has at most k parents, for all k > 3.


title: Using the structure of d-connecting paths as a qualitative measure of the strength of dependence

abstract: Pearls concept OF a d - connecting path IS one OF the foundations OF the modern theory OF graphical models : the absence OF a d - connecting path IN a DAG indicates that conditional independence will hold IN ANY distribution factorising according TO that graph. IN this paper we show that IN singly - connected Gaussian DAGs it IS possible TO USE the form OF a d - connection TO obtain qualitative information about the strength OF conditional dependence.More precisely, the squared partial correlations BETWEEN two given variables, conditioned ON different subsets may be partially ordered BY examining the relationship BETWEEN the d - connecting path AND the SET OF variables conditioned upon.


title: Reasoning about Bayesian Network Classifiers

abstract: Bayesian network classifiers are used in many fields, and one common class of classifiers are naive Bayes classifiers. In this paper, we introduce an approach for reasoning about Bayesian network classifiers in which we explicitly convert them into Ordered Decision Diagrams (ODDs), which are then used to reason about the properties of these classifiers. Specifically, we present an algorithm for converting any naive Bayes classifier into an ODD, and we show theoretically and experimentally that this algorithm can give us an ODD that is tractable in size even given an intractable number of instances. Since ODDs are tractable representations of classifiers, our algorithm allows us to efficiently test the equivalence of two naive Bayes classifiers and characterize discrepancies between them. We also show a number of additional results including a count of distinct classifiers that can be induced by changing some CPT in a naive Bayes classifier, and the range of allowable changes to a CPT which keeps the current classifier unchanged.


title: Monte Carlo Matrix Inversion Policy Evaluation

abstract: In 1950, Forsythe and Leibler (1950) introduced a statistical technique for finding the inverse of a matrix by characterizing the elements of the matrix inverse as expected values of a sequence of random walks. Barto and Duff (1994) subsequently showed relations between this technique and standard dynamic programming and temporal differencing methods. The advantage of the Monte Carlo matrix inversion (MCMI) approach is that it scales better with respect to state-space size than alternative techniques. In this paper, we introduce an algorithm for performing reinforcement learning policy evaluation using MCMI. We demonstrate that MCMI improves on runtime over a maximum likelihood model-based policy evaluation approach and on both runtime and accuracy over the temporal differencing (TD) policy evaluation approach. We further improve on MCMI policy evaluation by adding an importance sampling technique to our algorithm to reduce the variance of our estimator. Lastly, we illustrate techniques for scaling up MCMI to large state spaces in order to perform policy improvement.


title: Budgeted Learning of Naive-Bayes Classifiers

abstract: Frequently, acquiring training data has an associated cost. We consider the situation where the learner may purchase data during training, subject TO a budget. IN particular, we examine the CASE WHERE each feature label has an associated cost, AND the total cost OF ALL feature labels acquired during training must NOT exceed the budget.This paper compares methods FOR choosing which feature label TO purchase next, given the budget AND the CURRENT belief state OF naive Bayes model parameters.Whereas active learning has traditionally focused ON myopic(greedy) strategies FOR query selection, this paper presents a tractable method FOR incorporating knowledge OF the budget INTO the decision making process, which improves performance.


title: A Linear Belief Function Approach to Portfolio Evaluation

abstract: By elaborating on the notion of linear belief functions (Dempster 1990; Liu 1996), we propose an elementary approach to knowledge representation for expert systems using linear belief functions. We show how to use basic matrices to represent market information and financial knowledge, including complete ignorance, statistical observations, subjective speculations, distributional assumptions, linear relations, and empirical asset pricing models. We then appeal to Dempster's rule of combination to integrate the knowledge for assessing an overall belief of portfolio performance, and updating the belief by incorporating additional information. We use an example of three gold stocks to illustrate the approach.


title: Learning Riemannian Metrics

abstract: We propose a solution to the problem of estimating a Riemannian metric associated with a given differentiable manifold. The metric learning problem is based on minimizing the relative volume of a given set of points. We derive the details for a family of metrics on the multinomial simplex. The resulting metric has applications in text classification and bears some similarity to TFIDF representation of text documents.


title: Efficient Gradient Estimation for Motor Control Learning

abstract: The task of estimating the gradient of a function in the presence of noise is central to several forms of reinforcement learning, including policy search methods. We present two techniques for reducing gradient estimation errors in the presence of observable input noise applied to the control signal. The first method extends the idea of a reinforcement baseline by fitting a local linear model to the function whose gradient is being estimated; we show how to find the linear model that minimizes the variance of the gradient estimate, and how to estimate the model from data. The second method improves this further by discounting components of the gradient vector that have high variance. These methods are applied to the problem of motor control learning, where actuator noise has a significant influence on behavior. In particular, we apply the techniques to learn locally optimal controllers for a dart-throwing task using a simulated three-link arm; we demonstrate that proposed methods significantly improve the reward function gradient estimate and, consequently, the learning curve, over existing methods.


title: Approximate Decomposition: A Method for Bounding and Estimating Probabilistic and Deterministic Queries

abstract: In this paper, we introduce a method for approximating the solution to inference and optimization tasks in uncertain and deterministic reasoning. Such tasks are in general intractable for exact algorithms because of the large number of dependency relationships in their structure. Our method effectively maps such a dense problem to a sparser one which is in some sense "closest". Exact methods can be run on the sparser problem to derive bounds on the original answer, which can be quite sharp. We present empirical results demonstrating that our method works well on the tasks of belief inference and finding the probability of the most probable explanation in belief networks, and finding the cost of the solution that violates the smallest number of constraints in constraint satisfaction problems. On one large CPCS network, for example, we were able to calculate upper and lower bounds on the conditional probability of a variable, given evidence, that were almost identical in the average case.


title: 1 Billion Pages = 1 Million Dollars? Mining the Web to Play "Who Wants to be a Millionaire?"

abstract: We exploit the redundancy and volume of information on the web to build a computerized player for the ABC TV game show 'Who Wants To Be A Millionaire?' The player consists of a question-answering module and a decision-making module. The question-answering module utilizes question transformation techniques, natural language parsing, multiple information retrieval algorithms, and multiple search engines; results are combined in the spirit of ensemble learning using an adaptive weighting scheme. Empirically, the system correctly answers about 75% of questions from the Millionaire CD-ROM, 3rd edition - general-interest trivia questions often about popular culture and common knowledge. The decision-making module chooses from allowable actions in the game in order to maximize expected risk-adjusted winnings, where the estimated probability of answering correctly is a function of past performance and confidence in in correctly answering the current question. When given a six question head start (i.e., when starting from the $2,000 level), we find that the system performs about as well on average as humans starting at the beginning. Our system demonstrates the potential of simple but well-chosen techniques for mining answers from unstructured information such as the web.


title: Preference-based Graphic Models for Collaborative Filtering

abstract: Collaborative filtering is a very useful general technique for exploiting the preference patterns of a group of users to predict the utility of items to a particular user. Previous research has studied several probabilistic graphic models for collaborative filtering with promising results. However, while these models have succeeded in capturing the similarity among users and items in one way or the other, none of them has considered the fact that users with similar interests in items can have very different rating patterns; some users tend to assign a higher rating to all items than other users. In this paper, we propose and study of two new graphic models that address the distinction between user preferences and ratings. In one model, called the decoupled model, we introduce two different variables to decouple a users preferences FROM his ratings. IN the other, called the preference model, we model the orderings OF items preferred BY a USER, rather than the USERs numerical ratings of items. Empirical study over two datasets of movie ratings shows that appropriate modeling of the distinction between user preferences and ratings improves the performance substantially and consistently. Specifically, the proposed decoupled model outperforms all five existing approaches that we compare with significantly, but the preference model is not very successful. These results suggest that explicit modeling of the underlying user preferences is very important for collaborative filtering, but we can not afford ignoring the rating information completely.


title: LAYERWIDTH: Analysis of a New Metric for Directed Acyclic Graphs

abstract: We analyze a new property of directed acyclic graphs (DAGs), called layerwidth, arising from a class of DAGs proposed by Eiter and Lukasiewicz. This class of DAGs permits certain problems of structural model-based causality and explanation to be tractably solved. In this paper, we first address an open question raised by Eiter and Lukasiewicz - the computational complexity of deciding whether a given graph has a bounded layerwidth. After proving that this problem is NP-complete, we proceed by proving numerous important properties of layerwidth that are helpful in efficiently computing the optimal layerwidth. Finally, we compare this new DAG property to two other important DAG properties: treewidth and bandwidth.


title: Approximate Inference and Constrained Optimization

abstract: Loopy and generalized belief propagation are popular algorithms for approximate inference in Markov random fields and Bayesian networks. Fixed points of these algorithms correspond to extrema of the Bethe and Kikuchi free energy. However, belief propagation does not always converge, which explains the need for approaches that explicitly minimize the Kikuchi/Bethe free energy, such as CCCP and UPS. Here we describe a class of algorithms that solves this typically nonconvex constrained minimization of the Kikuchi free energy through a sequence of convex constrained minimizations of upper bounds on the Kikuchi free energy. Intuitively one would expect tighter bounds to lead to faster algorithms, which is indeed convincingly demonstrated in our simulations. Several ideas are applied to obtain tight convex bounds that yield dramatic speed-ups over CCCP.


title: Monte-Carlo optimizations for resource allocation problems in stochastic network systems

abstract: Real-world distributed systems and networks are often unreliable and subject to random failures of its components. Such a stochastic behavior affects adversely the complexity of optimization tasks performed routinely upon such systems, in particular, various resource allocation tasks. In this work we investigate and develop Monte Carlo solutions for a class of two-stage optimization problems in stochastic networks in which the expected value of resource allocations before and after stochastic failures needs to be optimized. The limitation of these problems is that their exact solutions are exponential in the number of unreliable network components: thus, exact methods do not scale-up well to large networks often seen in practice. We first prove that Monte Carlo optimization methods can overcome the exponential bottleneck of exact methods. Next we support our theoretical findings on resource allocation experiments and show a very good scale-up potential of the new methods to large stochastic networks.


title: Implementation and Comparison of Solution Methods for Decision Processes with Non-Markovian Rewards

abstract: This paper examines a number of solution methods for decision processes with non-Markovian rewards (NMRDPs). They all exploit a temporal logic specification of the reward function to automatically translate the NMRDP into an equivalent Markov decision process (MDP) amenable to well-known MDP solution methods. They differ however in the representation of the target MDP and the class of MDP solution methods to which they are suited. As a result, they adopt different temporal logics and different translations. Unfortunately, no implementation of these methods nor experimental let alone comparative results have ever been reported. This paper is the first step towards filling this gap. We describe an integrated system for solving NMRDPs which implements these methods and several variants under a common interface; we use it to compare the various approaches and identify the problem features favoring one over the other.


title: Sufficient Dimensionality Reduction with Irrelevant Statistics

abstract: The problem of finding a reduced dimensionality representation of categorical variables while preserving their most relevant characteristics is fundamental for the analysis of complex data. Specifically, given a co-occurrence matrix of two variables, one often seeks a compact representation of one variable which preserves information about the other variable. We have recently introduced ``Sufficient Dimensionality Reduction' [GT-2003], a method that extracts continuous reduced dimensional features whose measurements (i.e., expectation values) capture maximal mutual information among the variables. However, such measurements often capture information that is irrelevant for a given task. Widely known examples are illumination conditions, which are irrelevant as features for face recognition, writing style which is irrelevant as a feature for content classification, and intonation which is irrelevant as a feature for speech recognition. Such irrelevance cannot be deduced apriori, since it depends on the details of the task, and is thus inherently ill defined in the purely unsupervised case. Separating relevant from irrelevant features can be achieved using additional side data that contains such irrelevant structures. This approach was taken in [CT-2002], extending the information bottleneck method, which uses clustering to compress the data. Here we use this side-information framework to identify features whose measurements are maximally informative for the original data set, but carry as little information as possible on a side data set. In statistical terms this can be understood as extracting statistics which are maximally sufficient for the original dataset, while simultaneously maximally ancillary for the side dataset. We formulate this tradeoff as a constrained optimization problem and characterize its solutions. We then derive a gradient descent algorithm for this problem, which is based on the Generalized Iterative Scaling method for finding maximum entropy distributions. The method is demonstrated on synthetic data, as well as on real face recognition datasets, and is shown to outperform standard methods such as oriented PCA.


title: Decision Making with Partially Consonant Belief Functions

abstract: This paper studies decision making for Walley's partially consonant belief functions (pcb). In a pcb, the set of foci are partitioned. Within each partition, the foci are nested. The pcb class includes probability functions and possibility functions as extreme cases. Unlike earlier proposals for a decision theory with belief functions, we employ an axiomatic approach. We adopt an axiom system similar in spirit to von Neumann - Morgenstern's linear utility theory for a preference relation on pcb lotteries. We prove a representation theorem for this relation. Utility for a pcb lottery is a combination of linear utility for probabilistic lottery and binary utility for possibilistic lottery.


title: Phase Transition of Tractability in Constraint Satisfaction and Bayesian Network Inference

abstract: There has been great interest in identifying tractable subclasses of NP complete problems and designing efficient algorithms for these tractable classes. Constraint satisfaction and Bayesian network inference are two examples of such problems that are of great importance in AI and algorithms. In this paper we study, under the frameworks of random constraint satisfaction problems and random Bayesian networks, a typical tractable subclass characterized by the treewidth of the problems. We show that the property of having a bounded treewidth for CSPs and Bayesian network inference problem has a phase transition that occurs while the underlying structures of problems are still sparse. This implies that algorithms making use of treewidth based structural knowledge only work efficiently in a limited range of random instance.


title: Extending Factor Graphs so as to Unify Directed and Undirected Graphical Models

abstract: The two most popular types of graphical model are directed models (Bayesian networks) and undirected models (Markov random fields, or MRFs). Directed and undirected models offer complementary properties in model construction, expressing conditional independencies, expressing arbitrary factorizations of joint distributions, and formulating message-passing inference algorithms. We show that the strengths of these two representations can be combined in a single type of graphical model called a 'factor graph'. Every Bayesian network or MRF can be easily converted to a factor graph that expresses the same conditional independencies, expresses the same factorization of the joint distribution, and can be used for probabilistic inference through application of a single, simple message-passing algorithm. In contrast to chain graphs, where message-passing is implemented on a hypergraph, message-passing can be directly implemented on the factor graph. We describe a modified 'Bayes-ball' algorithm for establishing conditional independence in factor graphs, and we show that factor graphs form a strict superset of Bayesian networks and MRFs. In particular, we give an example of a commonly-used 'mixture of experts' model fragment, whose independencies cannot be represented in a Bayesian network or an MRF, but can be represented in a factor graph. We finish by giving examples of real-world problems that are not well suited to representation in Bayesian networks and MRFs, but are well-suited to representation in factor graphs.


title: Locally Weighted Naive Bayes

abstract: Despite its simplicity, the naive Bayes classifier has surprised machine learning researchers by exhibiting good performance on a variety of learning problems. Encouraged by these results, researchers have looked to overcome naive Bayes primary weakness - attribute independence - and improve the performance of the algorithm. This paper presents a locally weighted version of naive Bayes that relaxes the independence assumption by learning local models at prediction time. Experimental results show that locally weighted naive Bayes rarely degrades accuracy compared to standard naive Bayes and, in many cases, improves accuracy dramatically. The main advantage of this method compared to other techniques for enhancing naive Bayes is its conceptual and computational simplicity.


title: A Distance-Based Branch and Bound Feature Selection Algorithm

abstract: There is no known efficient method for selecting k Gaussian features from n which achieve the lowest Bayesian classification error. We show an example of how greedy algorithms faced with this task are led to give results that are not optimal. This motivates us to propose a more robust approach. We present a Branch and Bound algorithm for finding a subset of k independent Gaussian features which minimizes the naive Bayesian classification error. Our algorithm uses additive monotonic distance measures to produce bounds for the Bayesian classification error in order to exclude many feature subsets from evaluation, while still returning an optimal solution. We test our method on synthetic data as well as data obtained from gene expression profiling.


title: The sharpness-induced mode stopping and spectrum rarefication in waveguides with periodically corrugated walls

abstract: Starting from the rigorous excitation equation, the propagation of waves through a 2D waveguide with the periodically corrugated finite-length insert is examined in detail. The corrugation profile is chosen to obey the property that its amplitude is small as compared to the waveguide width, whereas the sharpness of the asperities is arbitrarily large. With the aid of the method of mode separation, which was developed earlier for inhomogeneous-in-bulk waveguide systems [Waves Random Media \textbf{10}, 395 (2000)], the corrugated segment of the waveguide is shown to serve as the effective scattering barrier whose width is coincident with the length of the insert and the average height is controlled by the sharpness of boundary asperities. Due to this barrier, the mode spectrum of the waveguide can be substantially rarefied and adjusted so as to reduce the number of extended modes to the value arbitrarily less than that in the absence of corrugation (up to zero), without changing considerably the waveguide average width.


title: On the Convergence of Bound Optimization Algorithms

abstract: Many practitioners who use the EM algorithm complain that it is sometimes slow. When does this happen, and what can be done about it? In this paper, we study the general class of bound optimization algorithms - including Expectation-Maximization, Iterative Scaling and CCCP - and their relationship to direct optimization algorithms such as gradient-based methods for parameter learning. We derive a general relationship between the updates performed by bound optimization methods and those of gradient and second-order methods and identify analytic conditions under which bound optimization algorithms exhibit quasi-Newton behavior, and conditions under which they possess poor, first-order convergence. Based on this analysis, we consider several specific algorithms, interpret and analyze their convergence properties and provide some recipes for preprocessing input to these algorithms to yield faster convergence behavior. We report empirical results supporting our analysis and showing that simple data preprocessing can result in dramatically improved performance of bound optimizers in practice.


title: Automated Analytic Asymptotic Evaluation of the Marginal Likelihood for Latent Models

abstract: We present and implement two algorithms for analytic asymptotic evaluation of the marginal likelihood of data given a Bayesian network with hidden nodes. As shown by previous work, this evaluation is particularly hard for latent Bayesian network models, namely networks that include hidden variables, where asymptotic approximation deviates from the standard BIC score. Our algorithms solve two central difficulties in asymptotic evaluation of marginal likelihood integrals, namely, evaluation of regular dimensionality drop for latent Bayesian network models and computation of non-standard approximation formulas for singular statistics for these models. The presented algorithms are implemented in Matlab and Maple and their usage is demonstrated for marginal likelihood approximations for Bayesian networks with hidden variables.


title: Probing interaction in the dark sector

abstract: A phenomenological attempt at alleviating the so-called coincidence problem is to allow the dark matter and dark energy to interact. By assuming a coupled quintessence scenario characterized by an interaction parameter $\epsilon$, we investigate the precision in the measurements of the expansion rate $H(z)$ required by future experiments in order to detect a possible deviation from the standard $\Lambda$CDM model ($\epsilon = 0$). We perform our analyses at two levels, namely: through Monte Carlo simulations based on $\epsilon$CDM models, in which $H(z)$ samples with different accuracies are generated and through an analytic method that calculates the error propagation of $\epsilon$ as a function of the error in $H(z)$. We show that our analytical approach traces simulations accurately and find that to detect an interaction {using $H(z)$ data only, these must reach an accuracy better than 1%.


title: Decentralized Sensor Fusion With Distributed Particle Filters

abstract: This paper presents a scalable Bayesian technique for decentralized state estimation from multiple platforms in dynamic environments. As has long been recognized, centralized architectures impose severe scaling limitations for distributed systems due to the enormous communication overheads. We propose a strictly decentralized approach in which only nearby platforms exchange information. They do so through an interactive communication protocol aimed at maximizing information flow. Our approach is evaluated in the context of a distributed surveillance scenario that arises in a robotic system for playing the game of laser tag. Our results, both from simulation and using physical robots, illustrate an unprecedented scaling capability to large teams of vehicles.


title: Learning Generative Models of Similarity Matrices

abstract: We describe a probabilistic (generative) view of affinity matrices along with inference algorithms for a subclass of problems associated with data clustering. This probabilistic view is helpful in understanding different models and algorithms that are based on affinity functions OF the data. IN particular, we show how(greedy) inference FOR a specific probabilistic model IS equivalent TO the spectral clustering algorithm.It also provides a framework FOR developing new algorithms AND extended models. AS one CASE, we present new generative data clustering models that allow us TO infer the underlying distance measure suitable for the clustering problem at hand. These models seem to perform well in a larger class of problems for which other clustering algorithms (including spectral clustering) usually fail. Experimental evaluation was performed in a variety point data sets, showing excellent performance.


title: Policy-contingent abstraction for robust robot control

abstract: This paper presents a scalable control algorithm that enables a deployed mobile robot system to make high-level decisions under full consideration of its probabilistic belief. Our approach is based on insights from the rich literature of hierarchical controllers and hierarchical MDPs. The resulting controller has been successfully deployed in a nursing facility near Pittsburgh, PA. To the best of our knowledge, this work is a unique instance of applying POMDPs to high-level robotic control problems.


title: An Axiomatic Approach to Robustness in Search Problems with Multiple Scenarios

abstract: This paper is devoted to the search of robust solutions in state space graphs when costs depend on scenarios. We first present axiomatic requirements for preference compatibility with the intuitive idea of robustness.This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of robust solutions, we propose a new sophistication of A* specially designed to determine the set of robust paths in a state space graph. The behavior of the algorithm is illustrated on a small example. Finally, an axiomatic justification of the refinement of robustness by an OWA criterion is provided.


title: Solving MAP Exactly using Systematic Search

abstract: MAP is the problem of finding a most probable instantiation of a set of variables in a Bayesian network given some evidence. Unlike computing posterior probabilities, or MPE (a special case of MAP), the time and space complexity of structural solutions for MAP are not only exponential in the network treewidth, but in a larger parameter known as the "constrained" treewidth. In practice, this means that computing MAP can be orders of magnitude more expensive than computing posterior probabilities or MPE. This paper introduces a new, simple upper bound on the probability of a MAP solution, which admits a tradeoff between the bound quality and the time needed to compute it. The bound is shown to be generally much tighter than those of other methods of comparable complexity. We use this proposed upper bound to develop a branch-and-bound search algorithm for solving MAP exactly. Experimental results demonstrate that the search algorithm is able to solve many problems that are far beyond the reach of any structure-based method for MAP. For example, we show that the proposed algorithm can compute MAP exactly and efficiently for some networks whose constrained treewidth is more than 40.


title: Learning Continuous Time Bayesian Networks

abstract: Continuous time Bayesian networks (CTBNs) describe structured stochastic processes with finitely many states that evolve over continuous time. A CTBN is a directed (possibly cyclic) dependency graph over a set of variables, each of which represents a finite state continuous time Markov process whose transition model is a function of its parents. We address the problem of learning parameters and structure of a CTBN from fully observed data. We define a conjugate prior for CTBNs, and show how it can be used both for Bayesian parameter estimation and as the basis of a Bayesian score for structure learning. Because acyclicity is not a constraint in CTBNs, we can show that the structure learning problem is significantly easier, both in theory and in practice, than structure learning for dynamic Bayesian networks (DBNs). Furthermore, as CTBNs can tailor the parameters and dependency structure to the different time granularities of the evolution of different variables, they can provide a better fit to continuous-time processes than DBNs with a fixed time granularity.


title: Marginalizing Out Future Passengers in Group Elevator Control

abstract: Group elevator scheduling is an NP-hard sequential decision-making problem with unbounded state spaces and substantial uncertainty. Decision-theoretic reasoning plays a surprisingly limited role in fielded systems. A new opportunity for probabilistic methods has opened with the recent discovery of a tractable solution for the expected waiting times of all passengers in the building, marginalized over all possible passenger itineraries. Though commercially competitive, this solution does not contemplate future passengers. Yet in up-peak traffic, the effects of future passengers arriving at the lobby and entering elevator cars can dominate all waiting times. We develop a probabilistic model of how these arrivals affect the behavior of elevator cars at the lobby, and demonstrate how this model can be used to very significantly reduce the average waiting time of all passengers.


title: On Local Optima in Learning Bayesian Networks

abstract: This paper proposes and evaluates the k-greedy equivalence search algorithm (KES) for learning Bayesian networks (BNs) from complete data. The main characteristic of KES is that it allows a trade-off between greediness and randomness, thus exploring different good local optima. When greediness is set at maximum, KES corresponds to the greedy equivalence search algorithm (GES). When greediness is kept at minimum, we prove that under mild assumptions KES asymptotically returns any inclusion optimal BN with nonzero probability. Experimental results for both synthetic and real data are reported showing that KES often finds a better local optima than GES. Moreover, we use KES to experimentally confirm that the number of different local optima is often huge.


title: Dealing with uncertainty in fuzzy inductive reasoning methodology

abstract: The aim of this research is to develop a reasoning under uncertainty strategy in the context of the Fuzzy Inductive Reasoning (FIR) methodology. FIR emerged from the General Systems Problem Solving developed by G. Klir. It is a data driven methodology based on systems behavior rather than on structural knowledge. It is a very useful tool for both the modeling and the prediction of those systems for which no previous structural knowledge is available. FIR reasoning is based on pattern rules synthesized from the available data. The size of the pattern rule base can be very large making the prediction process quite difficult. In order to reduce the size of the pattern rule base, it is possible to automatically extract classical Sugeno fuzzy rules starting from the set of pattern rules. The Sugeno rule base preserves pattern rules knowledge as much as possible. In this process some information is lost but robustness is considerably increased. In the forecasting process either the pattern rule base or the Sugeno fuzzy rule base can be used. The first option is desirable when the computational resources make it possible to deal with the overall pattern rule base or when the extracted fuzzy rules are not accurate enough due to uncertainty associated to the original data. In the second option, the prediction process is done by means of the classical Sugeno inference system. If the amount of uncertainty associated to the data is small, the predictions obtained using the Sugeno fuzzy rule base will be very accurate. In this paper a mixed pattern/fuzzy rules strategy is proposed to deal with uncertainty in such a way that the best of both perspectives is used. Areas in the data space with a higher level of uncertainty are identified by means of the so-called error models. The prediction process in these areas makes use of a mixed pattern/fuzzy rules scheme, whereas areas identified with a lower level of uncertainty only use the Sugeno fuzzy rule base. The proposed strategy is applied to a real biomedical system, i.e., the central nervous system control of the cardiovascular system.


title: Optimal Limited Contingency Planning

abstract: For a given problem, the optimal Markov policy can be considerred as a conditional or contingent plan containing a (potentially large) number of branches. Unfortunately, there are applications where it is desirable to strictly limit the number of decision points and branches in a plan. For example, it may be that plans must later undergo more detailed simulation to verify correctness and safety, or that they must be simple enough to be understood and analyzed by humans. As a result, it may be necessary to limit consideration to plans with only a small number of branches. This raises the question of how one goes about finding optimal plans containing only a limited number of branches. In this paper, we present an any-time algorithm for optimal k-contingency planning (OKP). It is the first optimal algorithm for limited contingency planning that is not an explicit enumeration of possible contingent plans. By modelling the problem as a Partially Observable Markov Decision Process, it implements the Bellman optimality principle and prunes the solution space. We present experimental results of applying this algorithm to some simple test cases.


title: Practically Perfect

abstract: The property of perfectness plays an important role in the theory of Bayesian networks. First, the existence of perfect distributions for arbitrary sets of variables and directed acyclic graphs implies that various methods for reading independence from the structure of the graph (e.g., Pearl, 1988; Lauritzen, Dawid, Larsen & Leimer, 1990) are complete. Second, the asymptotic reliability of various search methods is guaranteed under the assumption that the generating distribution is perfect (e.g., Spirtes, Glymour & Scheines, 2000; Chickering & Meek, 2002). We provide a lower-bound on the probability of sampling a non-perfect distribution when using a fixed number of bits to represent the parameters of the Bayesian network. This bound approaches zero exponentially fast as one increases the number of bits used to represent the parameters. This result implies that perfect distributions with fixed-length representations exist. We also provide a lower-bound on the number of bits needed to guarantee that a distribution sampled from a uniform Dirichlet distribution is perfect with probability greater than 1/2. This result is useful for constructing randomized reductions for hardness proofs.


title: Efficiently Inducing Features of Conditional Random Fields

abstract: Conditional Random Fields (CRFs) are undirected graphical models, a special case of which correspond to conditionally-trained finite state machines. A key advantage of these models is their great flexibility to include a wide array of overlapping, multi-granularity, non-independent features of the input. In face of this freedom, an important question that remains is, what features should be used? This paper presents a feature induction method for CRFs. Founded on the principle of constructing only those feature conjunctions that significantly increase log-likelihood, the approach is based on that of Della Pietra et al [1997], but altered to work with conditional rather than joint probabilities, and with additional modifications for providing tractability specifically for a sequence model. In comparison with traditional approaches, automated feature induction offers both improved accuracy and more than an order of magnitude reduction in feature count; it enables the use of richer, higher-order Markov models, and offers more freedom to liberally guess about which atomic features may be relevant to a task. The induction method applies to linear-chain CRFs, as well as to more arbitrary CRF structures, also known as Relational Markov Networks [Taskar & Koller, 2002]. We present experimental results on a named entity extraction task.


title: Systematic vs. Non-systematic Algorithms for Solving the MPE Task

abstract: The paper continues the study of partitioning based inference of heuristics for search in the context of solving the Most Probable Explanation task in Bayesian Networks. We compare two systematic Branch and Bound search algorithms, BBBT (for which the heuristic information is constructed during search and allows dynamic variable/value ordering) and its predecessor BBMB (for which the heuristic information is pre-compiled), against a number of popular local search algorithms for the MPE problem. We show empirically that, when viewed as approximation schemes, BBBT/BBMB are superior to all of these best known SLS algorithms, especially when the domain sizes increase beyond 2. This is in contrast with the performance of SLS vs. systematic search on CSP/SAT problems, where SLS often significantly outperforms systematic algorithms. As far as we know, BBBT/BBMB are currently the best performing algorithms for solving the MPE task.


title: Strong Faithfulness and Uniform Consistency in Causal Inference

abstract: A fundamental question in causal inference is whether it is possible to reliably infer manipulation effects from observational data. There are a variety of senses of asymptotic reliability in the statistical literature, among which the most commonly discussed frequentist notions are pointwise consistency and uniform consistency. Uniform consistency is in general preferred to pointwise consistency because the former allows us to control the worst case error bounds with a finite sample size. In the sense of pointwise consistency, several reliable causal inference algorithms have been established under the Markov and Faithfulness assumptions [Pearl 2000, Spirtes et al. 2001]. In the sense of uniform consistency, however, reliable causal inference is impossible under the two assumptions when time order is unknown and/or latent confounders are present [Robins et al. 2000]. In this paper we present two natural generalizations of the Faithfulness assumption in the context of structural equation models, under which we show that the typical algorithms in the literature (in some cases with modifications) are uniformly consistent even when the time order is unknown. We also discuss the situation where latent confounders may be present and the sense in which the Faithfulness assumption is a limiting case of the stronger assumptions.


title: An Importance Sampling Algorithm Based on Evidence Pre-propagation

abstract: Precision achieved by stochastic sampling algorithms for Bayesian networks typically deteriorates in face of extremely unlikely evidence. To address this problem, we propose the Evidence Pre-propagation Importance Sampling algorithm (EPIS-BN), an importance sampling algorithm that computes an approximate importance function by the heuristic methods: loopy belief Propagation and e-cutoff. We tested the performance of e-cutoff on three large real Bayesian networks: ANDES, CPCS, and PATHFINDER. We observed that on each of these networks the EPIS-BN algorithm gives us a considerable improvement over the current state of the art algorithm, the AIS-BN algorithm. In addition, it avoids the costly learning stage of the AIS-BN algorithm.


title: Collaborative Ensemble Learning: Combining Collaborative and Content-Based Information Filtering via Hierarchical Bayes

abstract: Collaborative filtering (CF) and content-based filtering (CBF) have widely been used in information filtering applications. Both approaches have their strengths and weaknesses which is why researchers have developed hybrid systems. This paper proposes a novel approach to unify CF and CBF in a probabilistic framework, named collaborative ensemble learning. It uses probabilistic SVMs to model each user's profile (as CBF does).At the prediction phase, it combines a society OF users profiles, represented by their respective SVM models, to predict an active users preferences(the CF idea).The combination scheme is embedded in a probabilistic framework and retains an intuitive explanation.Moreover, collaborative ensemble learning does not require a global training stage and thus can incrementally incorporate new data.We report results based on two data sets. For the Reuters-21578 text data set, we simulate user ratings under the assumption that each user is interested in only one category. In the second experiment, we use users' opinions on a set of 642 art images that were collected through a web-based survey. For both data sets, collaborative ensemble achieved excellent performance in terms of recommendation accuracy.


title: Exploiting Locality in Searching the Web

abstract: Published experiments on spidering the Web suggest that, given training data in the form of a (relatively small) subgraph of the Web containing a subset of a selected class of target pages, it is possible to conduct a directed search and find additional target pages significantly faster (with fewer page retrievals) than by performing a blind or uninformed random or systematic search, e.g., breadth-first search. If true, this claim motivates a number of practical applications. Unfortunately, these experiments were carried out in specialized domains or under conditions that are difficult to replicate. We present and apply an experimental framework designed to reexamine and resolve the basic claims of the earlier work, so that the supporting experiments can be replicated and built upon. We provide high-performance tools for building experimental spiders, make use of the ground truth and static nature of the WT10g TREC Web corpus, and rely on simple well understand machine learning techniques to conduct our experiments. In this paper, we describe the basic framework, motivate the experimental design, and report on our findings supporting and qualifying the conclusions of the earlier research.


title: Markov Random Walk Representations with Continuous Distributions

abstract: Representations based on random walks can exploit discrete data distributions for clustering and classification. We extend such representations from discrete to continuous distributions. Transition probabilities are now calculated using a diffusion equation with a diffusion coefficient that inversely depends on the data density. We relate this diffusion equation to a path integral and derive the corresponding path probability measure. The framework is useful for incorporating continuous data densities and prior knowledge.


title: Stochastic complexity of Bayesian networks

abstract: Bayesian networks are now being used in enormous fields, for example, diagnosis of a system, data mining, clustering and so on. In spite of their wide range of applications, the statistical properties have not yet been clarified, because the models are nonidentifiable and non-regular. In a Bayesian network, the set of its parameter for a smaller model is an analytic set with singularities in the space of large ones. Because of these singularities, the Fisher information matrices are not positive definite. In other words, the mathematical foundation for learning was not constructed. In recent years, however, we have developed a method to analyze non-regular models using algebraic geometry. This method revealed the relation between the models singularities and its statistical properties. In this paper, applying this method to Bayesian networks with latent variables, we clarify the order of the stochastic complexities.Our result claims that the upper bound of those is smaller than the dimension of the parameter space. This means that the Bayesian generalization error is also far smaller than that of regular model, and that Schwarzs model selection criterion BIC needs to be improved for Bayesian networks.


title: A Generalized Mean Field Algorithm for Variational Inference in Exponential Families

abstract: The mean field methods, which entail approximating intractable probability distributions variationally with distributions from a tractable family, enjoy high efficiency, guaranteed convergence, and provide lower bounds on the true likelihood. But due to requirement for model-specific derivation of the optimization equations and unclear inference quality in various models, it is not widely used as a generic approximate inference algorithm. In this paper, we discuss a generalized mean field theory on variational approximation to a broad class of intractable distributions using a rich set of tractable distributions via constrained optimization over distribution spaces. We present a class of generalized mean field (GMF) algorithms for approximate inference in complex exponential family models, which entails limiting the optimization over the class of cluster-factorizable distributions. GMF is a generic method requiring no model-specific derivations. It factors a complex model into a set of disjoint variable clusters, and uses a set of canonical fix-point equations to iteratively update the cluster distributions, and converge to locally optimal cluster marginals that preserve the original dependency structure within each cluster, hence, fully decomposed the overall inference problem. We empirically analyzed the effect of different tractable family (clusters of different granularity) on inference quality, and compared GMF with BP on several canonical models. Possible extension to higher-order MF approximation is also discussed.


title: Efficient Parametric Projection Pursuit Density Estimation

abstract: Product models of low dimensional experts are a powerful way to avoid the curse of dimensionality. We present the ``under-complete product of experts' (UPoE), where each expert models a one dimensional projection of the data. The UPoE is fully tractable and may be interpreted as a parametric probabilistic model for projection pursuit. Its ML learning rules are identical to the approximate learning rules proposed before for under-complete ICA. We also derive an efficient sequential learning algorithm and discuss its relationship to projection pursuit density estimation and feature induction algorithms for additive random field models.


title: Boltzmann Machine Learning with the Latent Maximum Entropy Principle

abstract: We present a new statistical learning paradigm for Boltzmann machines based on a new inference principle we have proposed: the latent maximum entropy principle (LME). LME is different both from Jaynes maximum entropy principle and from standard maximum likelihood estimation.We demonstrate the LME principle BY deriving new algorithms for Boltzmann machine parameter estimation, and show how robust and fast new variant of the EM algorithm can be developed.Our experiments show that estimation based on LME generally yields better results than maximum likelihood estimation, particularly when inferring hidden units from small amounts of data.


title: The Revisiting Problem in Mobile Robot Map Building: A Hierarchical Bayesian Approach

abstract: We present an application of hierarchical Bayesian estimation to robot map building. The revisiting problem occurs when a robot has to decide whether it is seeing a previously-built portion of a map, or is exploring new territory. This is a difficult decision problem, requiring the probability of being outside of the current known map. To estimate this probability, we model the structure of a "typical" environment as a hidden Markov model that generates sequences of views observed by a robot navigating through the environment. A Dirichlet prior over structural models is learned from previously explored environments. Whenever a robot explores a new environment, the posterior over the model is estimated by Dirichlet hyperparameters. Our approach is implemented and tested in the context of multi-robot map merging, a particularly difficult instance of the revisiting problem. Experiments with robot data show that the technique yields strong improvements over alternative methods.


title: Learning Measurement Models for Unobserved Variables

abstract: Observed associations in a database may be due in whole or part to variations in unrecorded (latent) variables. Identifying such variables and their causal relationships with one another is a principal goal in many scientific and practical domains. Previous work shows that, given a partition of observed variables such that members of a class share only a single latent common cause, standard search algorithms for causal Bayes nets can infer structural relations between latent variables. We introduce an algorithm for discovering such partitions when they exist. Uniquely among available procedures, the algorithm is (asymptotically) correct under standard assumptions in causal Bayes net search algorithms, requires no prior knowledge of the number of latent variables, and does not depend on the mathematical form of the relationships among the latent variables. We evaluate the algorithm on a variety of simulated data sets.


title: Learning Module Networks

abstract: Methods for learning Bayesian network structure can discover dependency structure between observed variables, and have been shown to be useful in many applications. However, in domains that involve a large number of variables, the space of possible network structures is enormous, making it difficult, for both computational and statistical reasons, to identify a good model. In this paper, we consider a solution to this problem, suitable for domains where many variables have similar behavior. Our method is based on a new class of models, which we call module networks. A module network explicitly represents the notion of a module - a set of variables that have the same parents in the network and share the same conditional probability distribution. We define the semantics of module networks, and describe an algorithm that learns a module network from data. The algorithm learns both the partitioning of the variables into modules and the dependency structure between the variables. We evaluate our algorithm on synthetic data, and on real data in the domains of gene expression and the stock market. Our results show that module networks generalize better than Bayesian networks, and that the learned module network structure reveals regularities that are obscured in learned Bayesian networks.


title: Efficient Inference in Large Discrete Domains

abstract: In this paper we examine the problem of inference in Bayesian Networks with discrete random variables that have very large or even unbounded domains. For example, in a domain where we are trying to identify a person, we may have variables that have as domains, the set of all names, the set of all postal codes, or the set of all credit card numbers. We cannot just have big tables of the conditional probabilities, but need compact representations. We provide an inference algorithm, based on variable elimination, for belief networks containing both large domain and normal discrete random variables. We use intensional (i.e., in terms of procedures) and extensional (in terms of listing the elements) representations of conditional probabilities and of the intermediate factors.


title: CLP(BN): Constraint Logic Programming for Probabilistic Knowledge

abstract: We present CLP(BN), a novel approach that aims at expressing Bayesian networks through the constraint logic programming framework. Arguably, an important limitation of traditional Bayesian networks is that they are propositional, and thus cannot represent relations between multiple similar objects in multiple contexts. Several researchers have thus proposed first-order languages to describe such networks. Namely, one very successful example of this approach are the Probabilistic Relational Models (PRMs), that combine Bayesian networks with relational database technology. The key difficulty that we had to address when designing CLP(cal{BN}) is that logic based representations use ground terms to denote objects. With probabilitic data, we need to be able to uniquely represent an object whose value we are not sure about. We use {sl Skolem functions} as unique new symbols that uniquely represent objects with unknown value. The semantics of CLP(cal{BN}) programs then naturally follow from the general framework of constraint logic programming, as applied to a specific domain where we have probabilistic data. This paper introduces and defines CLP(cal{BN}), and it describes an implementation and initial experiments. The paper also shows how CLP(cal{BN}) relates to Probabilistic Relational Models (PRMs), Ngo and Haddawys Probabilistic Logic Programs, AND Kersting AND De Raedts Bayesian Logic Programs.


title: Slow crack propagation through a disordered medium: Critical transition and dissipation

abstract: We show that the intermittent and self-similar fluctuations displayed by a slow crack during the propagation in a heterogeneous medium can be quantitatively described by an extension of a classical statistical model for fracture. The model yields the correct dynamical and morphological scaling, and allows to demonstrate that the scale invariance originates from the presence of a non-equilibrium, reversible, critical transition which in the presence of dissipation gives rise to self organized critical behaviour.


title: Quickly proving the Andr\'asfai-Erd\H{o}s-S\'os-Theorem

abstract: Given an integer $r\gs 2$, an important theorem first proved by B. Andr\'asfai, P. Erd\H{o}s, and V. T. S\'os states that any $K_{r+1}$--free graph on $n$ vertices whose minimum degree is greater than $(3r-4)n/(3r-1)$ is $r$--colourable, and determines the graphs that are extremal in this context. The purpose of this note is to give an alternative proof of this result using a different idea.


title: Polar subspaces and automatic maximality

abstract: This paper is about certain linear subspaces of Banach SN spaces (that is to say Banach spaces which have a symmetric nonexpansive linear map into their dual spaces). We apply our results to monotone linear subspaces of the product of a Banach space and its dual. In this paper, we establish several new results and also give improved proofs of some known ones in both the general and the special contexts.


title: The Bayesian process control with multiple assignable causes

abstract: We study an optimal process control problem with multiple assignable causes. The process is initially in-control but is subject to random transition to one of multiple out-of-control states due to assignable causes. The objective is to find an optimal stopping rule under partial observation that maximizes the total expected reward in infinite horizon. The problem is formulated as a partially observable Markov decision process (POMDP) with the belief space consisting of state probability vectors. New observations are obtained at fixed sampling interval to update the belief vector using Bayes' theorem. Under standard assumptions, we show that a conditional control limit policy is optimal and that there exists a convex, non-increasing control limit that partitions the belief space into two individually connected control regions: a stopping region and a continuation region. We further derive the analytical bounds for the control limit. An algorithm is devised based on structural results, which considerably reduces the computation. We also shed light on the selection of optimal fixed sampling interval.


title: Clusters of Black Holes as Point-Like Gamma-ray Sources

abstract: The possibility of identifying some of Galactic gamma-ray sources as clusters of primordial black holes is discussed. The known scenarios of supermassive black hole formation indicate the multiple formation of lower-mass black holes. Our analysis demonstrates that due to Hawking evaporation the cluster of black holes with masses about $10^{15}$ g could be observed as a gamma-ray source. The total mass of typical cluster is $\sim 10 M_\odot$. Detailed calculations have been performed on the basis of specific model of primordial black hole formation.


title: Pizza Race Problem

abstract: This paper deals with a problem in which two players share a previously sliced pizza and try to eat as much amount of pizza as they can. It takes time to eat each piece of pizza and both players eat pizza at the same rate. One is allowed to take a next piece only after the person has finished eating the piece on hand. Also, after the first piece is taken, one can only take a piece which is adjacent to already-taken piece. This paper shows that, in this real time setting, the starting player can always eat at least two-fifth of the total size of the pizza. However, this may not be the best possible amount the starting player can eat. It is a modified problem from an original one where two players takes piece alternatively instead.


title: Calculations of Potential Energy Surfaces Using Monte Carlo Configuration Interaction

abstract: We apply the method of Monte Carlo configuration interaction (MCCI) to calculate ground-state potential energy curves for a range of small molecules and compare the results with full configuration interaction. We show that the MCCI potential energy curve can be calculated to relatively good accuracy, as quantified using the non-parallelity error, using only a very small fraction of the FCI space. In most cases the potential curve is of better accuracy than its constituent single-point energies. We finally test the MCCI program on systems with basis sets beyond full configuration interaction: a lattice of fifty hydrogen atoms and ethylene. The results for ethylene agree fairly well with other computational work while for the lattice of fifty hydrogens we find that the fraction of the full configuration interaction space we were able to consider appears to be too small as, although some qualitative features are reproduced, the potential curve is less accurate.


title: Translocation and encapsulation of siRNA inside carbon nanotubes

abstract: We report spontaneous translocation of small interfering RNA (siRNA) inside carbon nanotubes (CNTs) of various diameters and chirality using all atom molecular dynamics (MD) simulations with explicit solvent. We use Umbrella sampling method to calculate the free energy landscape of the siRNA entry and translocation event. Free energy profiles shows that siRNA gains free energy while translocating inside CNT and barrier for siRNA exit from CNT ranges from 40 to 110 kcal/mol depending on CNT chirality and salt concentration. The translocation time \tau decreases with the increase of CNT diameter with a critical diameter of 24 \AA for the translocation. In contrast, double strand DNA (dsDNA) of the same sequence does not translocate inside CNT due to large free energy barrier for the translocation. This study helps in understanding the nucleic acid transport through nanopores at microscopic level and may help designing carbon nanotube based sensor for siRNA.


title: Parameter estimation in a memory-assisted noisy quantum interferometry

abstract: We demonstrate that memory in an $N$-qubit system subjected to decoherence, is a potential resource for the slow-down of the entanglement decay. We show that this effect can be used to retain the sub shot-noise sensitivity of the parameter estimation in quantum interferometry. We calculate quantum Fisher information, which sets the ultimate bound for the precision of the estimation. We also derive the sensitivity of such a noisy interferometer, when the phase is either estimated from the measurements of the population imbalance or from the one-body density.


title: On The Delays In Spiking Neural P Systems

abstract: In this work we extend and improve the results done in a previous work on simulating Spiking Neural P systems (SNP systems in short) with delays using SNP systems without delays. We simulate the former with the latter over sequential, iteration, join, and split routing. Our results provide constructions so that both systems halt at exactly the same time, start with only one spike, and produce the same number of spikes to the environment after halting.


title: Pattern Avoidance in Ordered Set Partitions

abstract: In this paper we consider the enumeration of ordered set partitions avoiding a permutation pattern of length 2 or 3. We provide an exact enumeration for avoiding the permutation 12. We also give exact enumeration for ordered partitions with 3 blocks and ordered partitions with n-1 blocks avoiding a permutation of length 3. We use enumeration schemes to recursively enumerate 123-avoiding ordered partitions with any block sizes. Finally, we give some asymptotic results for the growth rates of the number of ordered set partitions avoiding a single pattern; including a Stanley-Wilf type that exhibits existence of such growth rates.


title: Enhanced Image Analysis Using Cached Mobile Robots

abstract: In the field of Artificial intelligence Image processing plays a vital role in Decision making. Nowadays Mobile robots work as a Network sharing Centralized Database. All Image inputs are compared against this database and decision is made. In some cases the Centralized database is in other side of the globe and Mobile robots compare Input image through satellite link this sometime results in delays in decision making which may result in castrophe. This Research paper is about how to make image processing in mobile robots less time consuming and fast decision making. This research paper compares search techniques employed currently and optimum search method which we are going to state. Nowadays Mobile robots are extensively used in environments which are dangerous to human beings. In this dangerous situations quick Decision making makes the difference between Hit and Miss this can also results in Day to day tasks performed by Mobile robots Successful or Failure.


title: The accretion flow to the intermittent accreting ms pulsar, HETE J1900.1-2455, as observed by XMM-Newton and RXTE

abstract: We present a study of the accretion flow to the intermittent accreting millisecond pulsar, HETE J1900.1-2455, based on observations performed simultaneously by XMM-Newton and RXTE. The 0.33-50 keV spectrum is described by the sum of a hard Comptonized component originated in an optically thin {\tau}~1 corona, a soft kTin~0.2 keV component interpreted as accretion disc emission, and of disc reflection of the hard component. Two emission features are detected at energies of 0.98(1) and 6.58(7) keV, respectively. The latter is identified as K{\alpha} transition of Fe XXIII-XXV. A simultaneous detection in EPIC-pn, EPIC-MOS2, and RGS spectra favours an astrophysical origin also for the former, which has an energy compatible with Fe-L{\alpha} and helium-like Ne-K{\alpha} transitions. Broadness of the two features suggests a common origin, resulting from reflection in an accretion disc with inclination of (30+4{\deg}), and extending down to Rin=25(+16,-11) gravitational radii from the compact object. However, the strength of the feature at lower energy measured by EPIC-pn cannot be entirely reconciled with the amplitude of the Fe K{\alpha} line, hampering the possibility of describing it in terms of a broad-band reflection model, and preventing a firm identification. Pulsations at the 377.3 Hz spin frequency could not be detected, with an upper limit of 0.4% at 3-{\sigma} c.l. on the fractional amplitude. We interpret the inner disc radius estimated from spectral modelling and the lack of significant detection of coherent X-ray pulsations as an indication of a disc accretion flow truncated by some mechanism connected to the overall evolution of the accretion disc, rather than by the neutron star magnetic field. This is compatible with the extremely close similarity of spectral and temporal properties of this source with respect to other, non pulsing atoll sources in the hard state.


title: Quantum Noise-to-Sensibility Ratio

abstract: The quantum variables that can be accessed directly by experiments are described by observables. Therefore, physical parameters can only be evaluated indirectly, via estimations based on experimental measurement results. I show that the quantum sensitivity, or the quantum statistical uncertainty in single-parameter estimation, can be defined as the (minimal) ratio between noise and sensibility with a parameter of a well-calibrated observable. Among one of its applications, I show that, measuring a convenient quadrature in squeezed probe oscillators, it is possible to surpass the standard precision limit in phase-shift estimations, even in presence of moderate phase diffusion.


title: Weighted projected networks: mapping hypergraphs to networks

abstract: Many natural, technological, and social systems incorporate multiway interactions, yet are characterized and measured on the basis of weighted pairwise interactions. In this article, I propose a family of models in which pairwise interactions originate from multiway interactions, by starting from ensembles of hypergraphs and applying projections that generate ensembles of weighted projected networks. I calculate analytically the statistical properties of weighted projected networks, and suggest ways these could be used beyond theoretical studies. Weighted projected networks typically exhibit weight disorder along links even for very simple generating hypergraph ensembles. Also, as the size of a hypergraph changes, a signature of multiway interaction emerges on the link weights of weighted projected networks that distinguishes them from fundamentally weighted pairwise networks. This signature could be used to search for hidden multiway interactions in weighted network data. I find the percolation threshold and size of the largest component for hypergraphs of arbitrary uniform rank, translate the results into projected networks, and show that the transition is second order. This general approach to network formation has the potential to shed new light on our understanding of weighted networks.


title: Hasse theorem -- an elementary approach

abstract: We give an elementary proof to Hasse theorem.


title: Octonion and Split Octonion Representation of SO(8) Symmetry

abstract: The 8 $\times$ 8 matrix representation of SO(8) Symmetry has been defined by using the direct product of Pauli matrices and Gamma matrices. These 8 $\times$ 8 matrices are being used to describe the rotations in SO(8) symmetry. The comparison of 8$\times$8 matrices with octonions has also been shown. The transformations of SO(8) symmetry are represented with the help of Octonions and split Octonions spinors.


title: Polar codes for private and quantum communication over arbitrary channels

abstract: We construct new polar coding schemes for the transmission of quantum or private classical information over arbitrary quantum channels. In the former case, our coding scheme achieves the symmetric coherent information and in the latter the symmetric private information. Both schemes are built from a polar coding construction capable of transmitting classical information over a quantum channel [Wilde and Guha, IEEE Transactions on Information Theory, in press]. Appropriately merging two such classical-quantum schemes, one for transmitting "amplitude" information and the other for transmitting "phase," leads to the new private and quantum coding schemes, similar to the construction for Pauli and erasure channels in [Renes, Dupuis, and Renner, Physical Review Letters 109, 050504 (2012)]. The encoding is entirely similar to the classical case, and thus efficient. The decoding can also be performed by successive cancellation, as in the classical case, but no efficient successive cancellation scheme is yet known for arbitrary quantum channels. An efficient code construction is unfortunately still unknown. Generally, our two coding schemes require entanglement or secret-key assistance, respectively, but we extend two known conditions under which the needed assistance rate vanishes. Finally, although our results are formulated for qubit channels, we show how the scheme can be extended to multiple qubits. This then demonstrates a near-explicit coding method for realizing one of the most striking phenomena in quantum information theory: the superactivation effect, whereby two quantum channels which individually have zero quantum capacity can have a non-zero quantum capacity when used together.


title: Synthesis and Properties of Bismuth Ferrite Multiferroic Nanoflowers

abstract: The method of microwave assisted hydrothermal synthesis of bismuth ferrite multiferroic nanoflowers, their mechanism of growth, magnetic as well as dielectric properties are presented. The nanoflowers are composed of numerous petals formed by BiFeO3 (BFO) nanocrystals and some amount of amorphous phase. The growth of the nanoflowers begins from the central part of calyx composed of only few petals towards which subsequent petals are successively attached. The nanoflowers exhibit enhanced magnetization due to size effect and lack of spin compensation in the spin cycloid. The dielectric properties of the nanoflowers are influenced by water confined to crystal nanovoids resulting in a broad dielectric permittivity maximum at 200 K {\div} 300 K and also by Polomska transition above the temperature of 450 K.


title: Production of quantum degenerate strontium gases: Larger, better, faster, colder

abstract: We report on an improved scheme to generate Bose-Einstein condensates (BECs) and degenerate Fermi gases of strontium. This scheme allows us to create quantum gases with higher atom number, a shorter time of the experimental cycle, or deeper quantum degeneracy than before. We create a BEC of 84-Sr exceeding 10^7 atoms, which is a 30-fold improvement over previously reported experiments. We increase the atom number of 86-Sr BECs to 2.5x10^4 (a fivefold improvement), and refine the generation of attractively interacting 88-Sr BECs. We present a scheme to generate 84-Sr BECs with a cycle time of 2s, which, to the best of our knowledge, is the shortest cycle time of BEC experiments ever reported. We create deeply-degenerate 87-Sr Fermi gases with T/T_F as low as 0.10(1), where the number of populated nuclear spin states can be set to any value between one and ten. Furthermore, we report on a total of five different double-degenerate Bose-Bose and Bose-Fermi mixtures. These studies prepare an excellent starting point for applications of strontium quantum gases anticipated in the near future.


title: Improvement of eigenfunction estimates on manifolds of nonpositive curvature

abstract: Let $(M,g)$ be a compact, boundaryless manifold of dimension $n$ with the property that either (i) $n=2$ and $(M,g)$ has no conjugate points, or (ii) the sectional curvatures of $(M,g)$ are nonpositive. Let $\Delta$ be the positive Laplacian on $M$ determined by $g$. We study the $L^{2}\to{}L^{p}$ mapping properties of a spectral cluster of $\sqrt{\Delta}$ of width $1/\log\lambda$. Under the geometric assumptions above, \cite{berard77} B\'{e}rard obtained a logarithmic improvement for the remainder term of the eigenvalue counting function which directly leads to a $(\log\lambda)^{1/2}$ improvement for H\"ormander's estimate on the $L^{\infty}$ norms of eigenfunctions. In this paper we extend this improvement to the $L^p$ estimates for all $p>\frac{2(n+1)}{n-1}$.


title: Coupled three-form dark energy

abstract: Cosmology with a three-form field interacting with cold dark matter is considered. In particular, the mass of the dark matter particles is assumed to depend upon the amplitude of the three-form field invariant. In comparison to coupled scalar field quintessence, the new features include an effective pressure contribution to the field equations that manifests both in the background and perturbation level. The dynamics of the background is analyzed, and new scaling solutions are found. A simple example model leading to a de Sitter expansion without a potential is studied. The Newtonian limit of cosmological perturbations is derived, and it is deduced that the coupling can be very tightly constrained by the large-scale structure data. This is demonstrated with numerical solutions for a model with nontrivial coupling and a quadratic potential.


title: Anisotropic magnetization, resistivity and heat capacity of single crystalline R3Ni2-xSn7 (R = La, Ce, Pr and Nd)

abstract: We present a detailed study of R3Ni2-xSn7 (R = La, Ce, Pr and Nd) single crystals by measurements of crystal structure, stoichiometry, temperature dependent magnetic susceptibility, magnetization, electrical resistivity, magnetoresistance, and specific heat. This series forms with partial Ni occupancy with x varying from ~ 0.1 for R = La to ~0.7 for R = Nd. The electrical resistivity of this series follows metallic behavior at high temperatures. Determination of clear anisotropies as well as antiferromagnetic ordering temperatures for R3Ni2-xSn7 (R = Ce, Pr and Nd) have been made. For Pr3Ni1.56Sn7 and Nd3Ni1.34Sn7, multiple magnetic transitions take place upon cooling. Metamagnetic transitions in this family (R = Ce, Pr and Nd) were detected for applied magnetic fields below 70 kOe. An H-T phase diagram of Ce3Ni1.69Sn7 was assembled to shed light on its low field properties and to rule out possible quantum critical effects.


title: NNLL resummation for W-boson production at large pT

abstract: We present new results for W-boson production at large transverse momentum at the LHC and the Tevatron. The contribution of soft-gluon corrections is derived from NNLL resummation and added to the exact NLO result. Numerical results and their uncertainties for the approximate NNLO W-boson transverse momentum distributions are derived and compared to recent data from the LHC.


title: Minimal volume product near Hanner polytopes

abstract: Mahler's conjecture asks whether the cube is a minimizer for the volume product of a body and its polar in the class of symmetric convex bodies in a fixed dimension. It is known that every Hanner polytope has the same volume product as the cube or the cross-polytope. In this paper we prove that every Hanner polytope is a strict local minimizer for the volume product in the class of symmetric convex bodies endowed with the Banach-Mazur distance.


title: An Analytic Theory for the Orbits of Circumbinary Planets

abstract: Three transiting circumbinary planets (Kepler-16 b, Kepler-34 b, and Kepler-35 b) have recently been discovered from photometric data taken by the Kepler spacecraft. Their orbits are significantly non-Keplerian because of the large secondary-to-primary mass ratio and orbital eccentricity of the binaries, as well as the proximity of the planets to the binaries. We present an analytic theory, with the planet treated as a test particle, which shows that the planetary motion can be represented by the superposition of the circular motion of a guiding center, the forced oscillations due to the non-axisymmetric components of the binary's potential, the epicyclic motion, and the vertical motion. In this analytic theory, the periapse and ascending node of the planet precess at nearly equal rates in opposite directions. The largest forced oscillation term corresponds to a forced eccentricity (which is an explicit function of the parameters of the binary and of the guiding center radius of the planet), and the amplitude of the epicyclic motion (which is a free parameter of the theory) is the free eccentricity. Comparisons with direct numerical orbit integrations show that this analytic theory gives an accurate description of the planetary motion for all three Kepler systems. We find that all three Kepler circumbinary planets have nonzero free eccentricities.


title: A Learning Framework for Morphological Operators using Counter-Harmonic Mean

abstract: We present a novel framework for learning morphological operators using counter-harmonic mean. It combines concepts from morphology and convolutional neural networks. A thorough experimental validation analyzes basic morphological operators dilation and erosion, opening and closing, as well as the much more complex top-hat transform, for which we report a real-world application from the steel industry. Using online learning and stochastic gradient descent, our system learns both the structuring element and the composition of operators. It scales well to large datasets and online settings.


title: Information spreading with aging in heterogeneous populations

abstract: We study the critical properties of a model of information spreading based on the SIS epidemic model. Spreading rates decay with time, as ruled by two parameters, $\epsilon$ and $l$, that can be either constant or randomly distributed in the population. The spreading dynamics is developed on top of Erd\"os-Renyi networks. We present the mean-field analytical solution of the model in its simplest formulation, and Monte Carlo simulations are performed for the more heterogeneous cases. The outcomes show that the system undergoes a nonequilibrium phase transition whose critical point depends on the parameters $\epsilon$ and $l$. In addition, we conclude that the more heterogeneous the population, the more favored the information spreading over the network.


title: IS (Low Energy) SUSY STILL ALIVE?

abstract: Supersymmetry, a new symmetry that relates bosons and fermions in particle physics, still escapes observation. Search for supersymmetry is one of the main aims of the Large Hadron Collider. The other possible manifestation of supersymmetry is the Dark Matter in the Universe. The present lectures contain a brief introduction to supersymmetry in particle physics. The main notions of supersymmetry are introduced. The supersymmetric extension of the Standard Model -- the Minimal Supersymmetric Standard Model -- is considered in more detail. Phenomenological features of the Minimal Supersymmetric Standard Model as well as possible experimental signatures of supersymmetry at the Large Hadron Collider are described. The present limits on supersymmetric particles are presented and the allowed region of parameter space of the MSSM is shown.


title: Subtraction makes computing integers faster

abstract: We show some facts regarding the question whether, for any number $n$, the length of the shortest Addition Multiplications Chain (AMC) computing $n$ is polynomial in the length of the shortest division-free Straight Line Program (SLP) that computes $n$. If the answer to this question is "yes", then we can show a stronger upper bound for $\mathrm{PosSLP}$, the important problem which essentially captures the notion of efficient computation over the reals. If the answer is "no", then this would demonstrate how subtraction helps generating integers super-polynomially faster, given that addition and multiplication can be done in unit time. In this paper, we show that, for almost all numbers, AMCs and SLPs need same asymptotic length for computation. However, for one specific form of numbers, SLPs are strictly more powerful than AMCs by at least one step of computation.


title: Photoluminescence and High Temperature Persistent Photoconductivity Experiments in SnO2 Nanobelts

abstract: The Persistent Photoconductivity (PPC) effect was studied in individual tin oxide (SnO2) nanobelts as a function of temperature, in air, helium, and vacuum atmospheres, and low temperature Photoluminescence measurements were carried out to study the optical transitions and to determine of the acceptor/donors levels and their best representation inside the band gap. Under ultraviolet (UV) illumination and at temperatures in the range of 200 to 400K we observed a fast and strong enhancement of the photoconductivity, and the maximum value of the photocurrent induced increases as the temperature or the oxygen concentration decreases. By turning off the UV illumination the induced photocurrent decays with lifetimes up to several hours. The photoconductivity and the PPC results were explained by adsorption and desorption of molecular oxygen at the surface of the SnO2 nanobelts. Based on the temperature dependence of the PPC decay an activation energy of 230 meV was found, which corresponds to the energy necessary for thermal ionization of free holes from acceptor levels to the valence band, in agreement with the photoluminescence results presented. The molecular-oxygen recombination with holes is the origin of the PPC effect in metal oxide semiconductors, so that, the PPC effect is not related to the oxygen vacancies, as commonly presented in the literature.


title: The 3-ball is a local pessimum for packing

abstract: It was conjectured by Ulam that the ball has the lowest optimal packing fraction out of all convex, three-dimensional solids. Here we prove that any origin-symmetric convex solid of sufficiently small asphericity can be packed at a higher efficiency than balls. We also show that in dimensions 4, 5, 6, 7, 8, and 24 there are origin-symmetric convex bodies of arbitrarily small asphericity that cannot be packed using a lattice as efficiently as balls can be.


title: Optimal antibunching in passive photonic devices based on coupled nonlinear resonators

abstract: We propose the use of weakly nonlinear passive materials for prospective applications in integrated quantum photonics. It is shown that strong enhancement of native optical nonlinearities by electromagnetic field confinement in photonic crystal resonators can lead to single-photon generation only exploiting the quantum interference of two coupled modes and the effect of photon blockade under resonant coherent driving. For realistic system parameters in state of the art microcavities, the efficiency of such single-photon source is theoretically characterized by means of the second-order correlation function at zero time delay as the main figure of merit, where major sources of loss and decoherence are taken into account within a standard master equation treatment. These results could stimulate the realization of integrated quantum photonic devices based on non-resonant material media, fully integrable with current semiconductor technology and matching the relevant telecom band operational wavelengths, as an alternative to single-photon nonlinear devices based on cavity-QED with artificial atoms or single atomic-like emitters.


title: sl3-foam homology calculations

abstract: We exhibit a certain infinite family of three-stranded quasi-alternating pretzel knots which are counterexamples to Lobb's conjecture that the sl_3-knot concordance invariant s_3 (suitably normalised) should be equal to the Rasmussen invariant s_2. For this family, |s_3| < |s_2|. However, we also find other knots for which |s_3| > |s_2|. The main tool is an implementation of Morrison and Nieh's algorithm to calculate Khovanov's sl_3-foam link homology. Our C++-program is fast enough to calculate the integral homology of e.g. the (6,5)-torus knot in six minutes. Furthermore, we propose a potential improvement of the algorithm by gluing sub-tangles in a more flexible way.


title: Quasi-inverse endomorphisms

abstract: Greither and Pareigis have established a connection between Hopf Galois structures on a Galois extension $L/K$ with Galois group $G$, and the regular subgroups of the group of permutations on $G$, which are normalized by $G$. Byott has rephrased this connection in terms of certain equivalence classes of injective morphisms of $G$ into the holomorph of the groups $N$ with the same cardinality of $G$. Childs and Corradino have used this theory to construct such Hopf Galois structures, starting from fixed-point-free endomorphisms of $G$ that have abelian images. In this paper we show that a fixed-point-free endomorphism has an abelian image if and only if there is another endomorphism that is its inverse with respect to the circle operation in the near-ring of maps on $G$, and give a fairly explicit recipe for constructing all such endomorphisms.


title: Efficient moment-based inference of admixture parameters and sources of gene flow

abstract: The recent explosion in available genetic data has led to significant advances in understanding the demographic histories of and relationships among human populations. It is still a challenge, however, to infer reliable parameter values for complicated models involving many populations. Here we present MixMapper, an efficient, interactive method for constructing phylogenetic trees including admixture events using single nucleotide polymorphism (SNP) genotype data. MixMapper implements a novel two-phase approach to admixture inference using moment statistics, first building an unadmixed scaffold tree and then adding admixed populations by solving systems of equations that express allele frequency divergences in terms of mixture parameters. Importantly, all features of the model, including topology, sources of gene flow, branch lengths, and mixture proportions, are optimized automatically from the data and include estimates of statistical uncertainty. MixMapper also uses a new method to express branch lengths in easily interpretable drift units. We apply MixMapper to recently published data for HGDP individuals genotyped on a SNP array designed especially for use in population genetics studies, obtaining confident results for 30 populations, 20 of them admixed. Notably, we confirm a signal of ancient admixture in European populations---including previously undetected admixture in Sardinians and Basques---involving a proportion of 20--40% ancient northern Eurasian ancestry.


title: Local random quantum circuits are approximate polynomial-designs - numerical results

abstract: We numerically investigate the statement that local random quantum circuits acting on n qubits composed of polynomially many nearest neighbour two-qubit gates form an approximate unitary poly(n)-design [F.G.S.L. Brandao et al., arXiv:1208.0692]. Using a group theory formalism, spectral gaps that give a ratio of convergence to a given t-design are evaluated for a different number of qubits n (up to 20) and degrees t (t=2,3,4 and 5), improving previously known results for n=2 in the case of t=2 and 3. Their values lead to a conclusion that the previously used lower bound that bounds spectral gaps values may give very little information about the real situation and in most cases, only tells that a gap is closed. We compare our results to the another lower bounding technique, again showing that its results may not be tight.


title: On the horizon instability of an extreme Reissner-Nordstr\"om black hole

abstract: Aretakis has proved that a massless scalar field has an instability at the horizon of an extreme Reissner-Nordstr\"om black hole. We show that a similar instability occurs also for a massive scalar field and for coupled linearized gravitational and electromagnetic perturbations. We present numerical results for the late time behaviour of massless and massive scalar fields in the extreme RN background and show that instabilities are present for initial perturbations supported outside the horizon, e.g.\ an ingoing wavepacket. For a massless scalar we show that the numerical results for the late time behaviour are reproduced by an analytic calculation in the near-horizon geometry. We relate Aretakis' conserved quantities at the future horizon to the Newman-Penrose conserved quantities at future null infinity.