OpenRaiser/Intern-Atlas huggingface dataset:
Sidestepping the Triangulation Problem in Bayesian Net Computations
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a new approach for computing posterior probabilities in Bayesian nets, which sidesteps the triangulation problem. The current state of art is the clique tree propagation approach. When the underlying graph of a Bayesian net is triangulated, this approach arranges its cliques into a tree and computes posterior probabilities by appropriately passing around messages in that tree. The computation in each clique is simply direct marginalization. When the underlying graph is not triangulated, one has to first triangulated it by adding edges. Referred to as the triangulation problem, the problem of finding an optimal or even a ?good? triangulation proves to be difficult. In this paper, we propose to first decompose a Bayesian net into smaller components by making use of Tarjan's algorithm for decomposing an undirected graph at all its minimal complete separators. Then, the components are arranged into a tree and posterior probabilities are computed by appropriately passing around messages in that tree. The computation in each component is carried out by repeating the whole procedure from the beginning. Thus the triangulation problem is sidestepped.
Fractional Order Hybrid Systems and Their Stability
Venue: arXiv cs.SY 2013
Year: 2013

This paper deals with hybrid systems (HS) with fractional order dynamics and their stability. The stability of two particular types of fractional order hybrid systems (FOHS), i.e., switching and reset control systems, is studied. Common Lyapunov method, as well as its frequency domain equivalence, are generalized for the former systems and, for the latter, H$_β$-condition is used --frequency domain equivalence of Lyapunov-like method for reset control systems. The applicability and efficiency of the proposed methods are shown by some illustrative examples.
On the stretch factor of the Theta-4 graph
Venue: arXiv cs.CG 2013
Year: 2013

In this paper we show that the θ-graph with 4 cones has constant stretch factor, i.e., there is a path between any pair of vertices in this graph whose length is at most a constant times the Euclidean distance between that pair of vertices. This is the last θ-graph for which it was not known whether its stretch factor was bounded.
Sample Distortion for Compressed Imaging
Venue: arXiv cs.CV 2013
Year: 2013

We propose the notion of a sample distortion (SD) function for independent and identically distributed (i.i.d) compressive distributions to fundamentally quantify the achievable reconstruction performance of compressed sensing for certain encoder-decoder pairs at a given sampling ratio. Two lower bounds on the achievable performance and the intrinsic convexity property is derived. A zeroing procedure is then introduced to improve non convex SD functions. The SD framework is then applied to analyse compressed imaging with a multi-resolution statistical image model using both the generalized Gaussian distribution and the two-state Gaussian mixture distribution. We subsequently focus on the Gaussian encoder-Bayesian optimal approximate message passing (AMP) decoder pair, whose theoretical SD function is provided by the rigorous analysis of the AMP algorithm. Given the image statistics, analytic bandwise sample allocation for bandwise independent model is derived as a reverse water-filling scheme. Som and Schniter's turbo message passing approach is further deployed to integrate the bandwise sampling with the exploitation of the hidden Markov tree structure of wavelet coefficients. Natural image simulations confirm that with oracle image statistics, the SD function associated with the optimized sample allocation can accurately predict the possible compressed sensing gains. Finally, a general sample allocation profile based on average image statistics not only illustrates preferable performance but also makes the scheme practical.
Parameters Optimization for Improving ASR Performance in Adverse Real World Noisy Environmental Conditions
Venue: arXiv cs.CL 2013
Year: 2013

From the existing research it has been observed that many techniques and methodologies are available for performing every step of Automatic Speech Recognition (ASR) system, but the performance (Minimization of Word Error Recognition-WER and Maximization of Word Accuracy Rate- WAR) of the methodology is not dependent on the only technique applied in that method. The research work indicates that, performance mainly depends on the category of the noise, the level of the noise and the variable size of the window, frame, frame overlap etc is considered in the existing methods. The main aim of the work presented in this paper is to use variable size of parameters like window size, frame size and frame overlap percentage to observe the performance of algorithms for various categories of noise with different levels and also train the system for all size of parameters and category of real world noisy environment to improve the performance of the speech recognition system. This paper presents the results of Signal-to-Noise Ratio (SNR) and Accuracy test by applying variable size of parameters. It is observed that, it is really very hard to evaluate test results and decide parameter size for ASR performance improvement for its resultant optimization. Hence, this study further suggests the feasible and optimum parameter size using Fuzzy Inference System (FIS) for enhancing resultant accuracy in adverse real world noisy environmental conditions. This work will be helpful to give discriminative training of ubiquitous ASR system for better Human Computer Interaction (HCI).
Genetic Algorithm with Ensemble Learning for Detecting Community Structure in Complex Networks
Venue: arXiv cs.SI 2013
Year: 2013

Community detection in complex networks is a topic of considerable recent interest within the scientific community. For dealing with the problem that genetic algorithm are hardly applied to community detection, we propose a genetic algorithm with ensemble learning (GAEL) for detecting community structure in complex networks. GAEL replaces its traditional crossover operator with a multi-individual crossover operator based on ensemble learning. Therefore, GAEL can avoid the problems that are brought by traditional crossover operator which is only able to mix string blocks of different individuals, but not able to recombine clustering contexts of different individuals into new better ones. In addition, the local search strategy, which makes mutated node be placed into the community where most of its neighbors are, is used in mutation operator. At last, a Markov random walk based method is used to initialize population in this paper, and it can provide us a population of accurate and diverse clustering solutions. Those diverse and accurate individuals are suitable for ensemble learning based multi-individual crossover operator. The proposed GAEL is tested on both computer-generated and real-world networks, and compared with current representative algorithms for community detection in complex networks. Experimental results demonstrate that GAEL is highly effective at discovering community structure.
Combining Multiple-Valued Logics in Modular Expert Systems
Venue: arXiv cs.AI 2013
Year: 2013

The way experts manage uncertainty usually changes depending on the task they are performing. This fact has lead us to consider the problem of communicating modules (task implementations) in a large and structured knowledge based system when modules have different uncertainty calculi. In this paper, the analysis of the communication problem is made assuming that (i) each uncertainty calculus is an inference mechanism defining an entailment relation, and therefore the communication is considered to be inference-preserving, and (ii) we restrict ourselves to the case which the different uncertainty calculi are given by a class of truth functional Multiple-valued Logics.
Some Properties of Plausible Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a plausible reasoning system to illustrate some broad issues in knowledge representation: dualities between different reasoning forms, the difficulty of unifying complementary reasoning styles, and the approximate nature of plausible reasoning. These issues have a common underlying theme: there should be an underlying belief calculus of which the many different reasoning forms are special cases, sometimes approximate. The system presented allows reasoning about defaults, likelihood, necessity and possibility in a manner similar to the earlier work of Adams. The system is based on the belief calculus of subjective Bayesian probability which itself is based on a few simple assumptions about how belief should be manipulated. Approximations, semantics, consistency and consequence results are presented for the system. While this puts these often discussed plausible reasoning forms on a probabilistic footing, useful application to practical problems remains an issue.
Probability Estimation in Face of Irrelevant Information
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we consider one aspect of the problem of applying decision theory to the design of agents that learn how to make decisions under uncertainty. This aspect concerns how an agent can estimate probabilities for the possible states of the world, given that it only makes limited observations before committing to a decision. We show that the naive application of statistical tools can be improved upon if the agent can determine which of his observations are truly relevant to the estimation problem at hand. We give a framework in which such determinations can be made, and define an estimation procedure to use them. Our framework also suggests several extensions, which show how additional knowledge can be used to improve tile estimation procedure still further.
Evidential Reasoning in a Categorial Perspective: Conjunction and Disjunction of Belief Functions
Venue: arXiv cs.AI 2013
Year: 2013

The categorial approach to evidential reasoning can be seen as a combination of the probability kinematics approach of Richard Jeffrey (1965) and the maximum (cross-) entropy inference approach of E. T. Jaynes (1957). As a consequence of that viewpoint, it is well known that category theory provides natural definitions for logical connectives. In particular, disjunction and conjunction are modelled by general categorial constructions known as products and coproducts. In this paper, I focus mainly on Dempster-Shafer theory of belief functions for which I introduce a category I call Dempster?s category. I prove the existence of and give explicit formulas for conjunction and disjunction in the subcategory of separable belief functions. In Dempster?s category, the new defined conjunction can be seen as the most cautious conjunction of beliefs, and thus no assumption about distinctness (of the sources) of beliefs is needed as opposed to Dempster?s rule of combination, which calls for distinctness (of the sources) of beliefs.
Truth as Utility: A Conceptual Synthesis
Venue: arXiv cs.AI 2013
Year: 2013

This paper introduces conceptual relations that synthesize utilitarian and logical concepts, extending the logics of preference of Rescher. We define first, in the context of a possible worlds model, constraint-dependent measures that quantify the relative quality of alternative solutions of reasoning problems or the relative desirability of various policies in control, decision, and planning problems. We show that these measures may be interpreted as truth values in a multi valued logic and propose mechanisms for the representation of complex constraints as combinations of simpler restrictions. These extended logical operations permit also the combination and aggregation of goal-specific quality measures into global measures of utility. We identify also relations that represent differential preferences between alternative solutions and relate them to the previously defined desirability measures. Extending conventional modal logic formulations, we introduce structures for the representation of ignorance about the utility of alternative solutions. Finally, we examine relations between these concepts and similarity based semantic models of fuzzy logic.
Completing Knowledge by Competing Hierarchies
Venue: arXiv cs.AI 2013
Year: 2013

A control strategy for expert systems is presented which is based on Shafer's Belief theory and the combination rule of Dempster. In contrast to well known strategies it is not sequentially and hypotheses-driven, but parallel and self organizing, determined by the concept of information gain. The information gain, calculated as the maximal difference between the actual evidence distribution in the knowledge base and the potential evidence determines each consultation step. Hierarchically structured knowledge is an important representation form and experts even use several hierarchies in parallel for constituting their knowledge. Hence the control strategy is applied to a layered set of distinct hierarchies. Depending on the actual data one of these hierarchies is chosen by the control strategy for the next step in the reasoning process. Provided the actual data are well matched to the structure of one hierarchy, this hierarchy remains selected for a longer consultation time. If no good match can be achieved, a switch from the actual hierarchy to a competing one will result, very similar to the phenomenon of restructuring in problem solving tasks. Up to now the control strategy is restricted to multi hierarchical knowledge bases with disjunct hierarchies. It is implemented in the expert system IBIG (inference by information gain), being presently applied to acquired speech disorders (aphasia).
Compatibility of Quantitative and Qualitative Representations of Belief
Venue: arXiv cs.AI 2013
Year: 2013

The compatibility of quantitative and qualitative representations of beliefs was studied extensively in probability theory. It is only recently that this important topic is considered in the context of belief functions. In this paper, the compatibility of various quantitative belief measures and qualitative belief structures is investigated. Four classes of belief measures considered are: the probability function, the monotonic belief function, Shafer's belief function, and Smets' generalized belief function. The analysis of their individual compatibility with different belief structures not only provides a sound b<msis for these quantitative measures, but also alleviates some of the difficulties in the acquisition and interpretation of numeric belief numbers. It is shown that the structure of qualitative probability is compatible with monotonic belief functions. Moreover, a belief structure slightly weaker than that of qualitative belief is compatible with Smets' generalized belief functions.
Adaptive-Gain Second Order Sliding Mode Observer Design for Switching Power Converters
Venue: arXiv cs.SY 2013
Year: 2013

In this paper, a novel adaptive-gain Second Order Sliding Mode (SOSM) observer is proposed for multicell converters by considering it as a class of hybrid systems. The aim is to reduce the number of voltage sensors by estimating the capacitor voltages only from the measurement of load current. The proposed observer is proven to be robust in the presence of perturbations with \emph{unknown} boundary. However, the states of the system are only partially observable in the sense of observability rank condition. Due to its switching behavior, a recent concept of $Z(T_N)$ observability is used to analysis its hybrid observability, since its observability depends upon the switching control signals. Under certain condition of the switching sequences, the voltage across each capacitor becomes observable. Simulation results and comparisons with Luenberger switched observer highlight the effectiveness and robustness of the proposed observer with respect to output measurement noise and system uncertainties (load variations).
A Behavioural Foundation for Natural Computing and a Programmability Test
Venue: arXiv cs.IT 2013
Year: 2013

What does it mean to claim that a physical or natural system computes? One answer, endorsed here, is that computing is about programming a system to behave in different ways. This paper offers an account of what it means for a physical system to compute based on this notion. It proposes a behavioural characterisation of computing in terms of a measure of programmability, which reflects a system's ability to react to external stimuli. The proposed measure of programmability is useful for classifying computers in terms of the apparent algorithmic complexity of their evolution in time. I make some specific proposals in this connection and discuss this approach in the context of other behavioural approaches, notably Turing's test of machine intelligence. I also anticipate possible objections and consider the applicability of these proposals to the task of relating abstract computation to nature-like computation.
Fault Tolerance in Distributed Systems using Fused State Machines
Venue: arXiv cs.DC 2013
Year: 2013

Replication is a standard technique for fault tolerance in distributed systems modeled as deterministic finite state machines (DFSMs or machines). To correct f crash or f/2 Byzantine faults among n different machines, replication requires nf additional backup machines. We present a solution called fusion that requires just f additional backup machines. First, we build a framework for fault tolerance in DFSMs based on the notion of Hamming distances. We introduce the concept of an (f,m)-fusion, which is a set of m backup machines that can correct f crash faults or f/2 Byzantine faults among a given set of machines. Second, we present an algorithm to generate an (f,f)-fusion for a given set of machines. We ensure that our backups are efficient in terms of the size of their state and event sets. Our evaluation of fusion on the widely used MCNC'91 benchmarks for DFSMs show that the average state space savings in fusion (over replication) is 38% (range 0-99%). To demonstrate the practical use of fusion, we describe its potential application to the MapReduce framework. Using a simple case study, we compare replication and fusion as applied to this framework. While a pure replication-based solution requires 1.8 million map tasks, our fusion-based solution requires only 1.4 million map tasks with minimal overhead during normal operation or recovery. Hence, fusion results in considerable savings in state space and other resources such as the power needed to run the backup tasks.
How Do We Find Early Adopters Who Will Guide a Resource Constrained Network Towards a Desired Distribution of Behaviors?
Venue: arXiv cs.SI 2013
Year: 2013

We identify influential early adopters that achieve a target behavior distribution for a resource constrained social network with multiple costly behaviors. This problem is important for applications ranging from collective behavior change to corporate viral marketing campaigns. In this paper, we propose a model of diffusion of multiple behaviors when individual participants have resource constraints. Individuals adopt the set of behaviors that maximize their utility subject to available resources. We show that the problem of influence maximization for multiple behaviors is NP-complete. Thus we propose heuristics, which are based on node degree and expected immediate adoption, to select early adopters. We evaluate the effectiveness under three metrics: unique number of participants, total number of active behaviors and network resource utilization. We also propose heuristics to distribute the behaviors amongst the early adopters to achieve a target distribution in the population. We test our approach on synthetic and real-world topologies with excellent results. Our heuristics produce 15-51\% increase in resource utilization over the naïve approach.
Ant Colony Optimization with a New Random Walk Model for Community Detection in Complex Networks
Venue: arXiv cs.SI 2013
Year: 2013

Detecting communities from complex networks has recently triggered great interest. Aiming at this problem, a new ant colony optimization strategy building on the Markov random walks theory, which is named as MACO, is proposed in this paper. The framework of ant colony optimization is taken as the basic framework in this algorithm. In each iteration, a Markov random walk model is employed as heuristic rule; all of the ants local solutions are aggregated to a global one through an idea of clustering ensemble, which then will be used to update a pheromone matrix. The strategy relies on the progressive strengthening of within-community links and the weakening of between-community links. Gradually this converges to a solution where the underlying community structure of the complex network will become clearly visible. The proposed MACO has been evaluated both on synthetic benchmarks and on some real-world networks, and compared with some present competing algorithms. Experimental result has shown that MACO is highly effective for discovering communities.
Fast Complex Network Clustering Algorithm Using Agents
Venue: arXiv cs.SI 2013
Year: 2013

Recently, the sizes of networks are always very huge, and they take on distributed nature. Aiming at this kind of network clustering problem, in the sight of local view, this paper proposes a fast network clustering algorithm in which each node is regarded as an agent, and each agent tries to maximize its local function in order to optimize network modularity defined by function Q, rather than optimize function Q from the global view as traditional methods. Both the efficiency and effectiveness of this algorithm are tested against computer-generated and real-world networks. Experimental result shows that this algorithm not only has the ability of clustering large-scale networks, but also can attain very good clustering quality compared with the existing algorithms. Furthermore, the parameters of this algorithm are analyzed.
A Diffusion Process on Riemannian Manifold for Visual Tracking
Venue: arXiv cs.CV 2013
Year: 2013

Robust visual tracking for long video sequences is a research area that has many important applications. The main challenges include how the target image can be modeled and how this model can be updated. In this paper, we model the target using a covariance descriptor, as this descriptor is robust to problems such as pixel-pixel misalignment, pose and illumination changes, that commonly occur in visual tracking. We model the changes in the template using a generative process. We introduce a new dynamical model for the template update using a random walk on the Riemannian manifold where the covariance descriptors lie in. This is done using log-transformed space of the manifold to free the constraints imposed inherently by positive semidefinite matrices. Modeling template variations and poses kinetics together in the state space enables us to jointly quantify the uncertainties relating to the kinematic states and the template in a principled way. Finally, the sequential inference of the posterior distribution of the kinematic states and the template is done using a particle filter. Our results shows that this principled approach can be robust to changes in illumination, poses and spatial affine transformation. In the experiments, our method outperformed the current state-of-the-art algorithm - the incremental Principal Component Analysis method, particularly when a target underwent fast poses changes and also maintained a comparable performance in stable target tracking cases.