OpenRaiser/Intern-Atlas huggingface dataset:
The Graph Grammar Library - a generic framework for chemical graph rewrite systems
Venue: arXiv cs.MS 2013
Year: 2013

Graph rewrite systems are powerful tools to model and study complex problems in various fields of research. Their successful application to chemical reaction modelling on a molecular level was shown but no appropriate and simple system is available at the moment. The presented Graph Grammar Library (GGL) implements a generic Double Push Out approach for general graph rewrite systems. The framework focuses on a high level of modularity as well as high performance, using state-of-the-art algorithms and data structures, and comes with extensive documentation. The large GGL chemistry module enables extensive and detailed studies of chemical systems. It well meets the requirements and abilities envisioned by Yadav et al. (2004) for such chemical rewrite systems. Here, molecules are represented as undirected labeled graphs while chemical reactions are described by according graph grammar rules. Beside the graph transformation, the GGL offers advanced cheminformatics algorithms for instance to estimate energies ofmolecules or aromaticity perception. These features are illustrated using a set of reactions from polyketide chemistry a huge class of natural compounds of medical relevance. The graph grammar based simulation of chemical reactions offered by the GGL is a powerful tool for extensive cheminformatics studies on a molecular level. The GGL already provides rewrite rules for all enzymes listed in the KEGG LIGAND database is freely available at http://www.tbi.univie.ac.at/software/GGL/.
Report on the EuDML external cooperation model
Venue: arXiv cs.DL 2013
Year: 2013

One of the main tasks of the European Digital Mathematics Library project was to define a cooperation model with a variety of stakeholders that would allow building a reliable and durable global reference library, aiming to be eventually exhaustive. In this paper we present the EuDML external cooperation model and the business plan as the basis for its sustainability and further development.
Now that I Have a Good Theory of Uncertainty, What Else Do I Need?
Venue: arXiv cs.AI 2013
Year: 2013

Rather than discussing the isolated merits of a nominative theory of uncertainty, this paper focuses on a class of problems, referred to as Dynamic Classification Problem (DCP), which requires the integration of many theories, including a prescriptive theory of uncertainty. We start by analyzing the Dynamic Classification Problem and by defining its induced requirements on a supporting (plausible) reasoning system. We provide a summary of the underlying theory (based on the semantics of many-valed logics) and illustrate the constraints imposed upon it to ensure the modularity and computational performance required by the applications. We describe the technologies used for knowledge engineering (such as object-based simulator to exercise requirements, and development tools to build the Knowledge Base and functionally validate it). We emphasize the difference between development environment and run-time system, describe the rule cross-compiler, and the real-time inference engine with meta-reasoning capabilities. Finally, we illustrate how our proposed technology satisfies the pop's requirements and analyze some of the lessons reamed from its applications to situation assessment problems for Pilot's Associate and Submarine Commander Associate.
Uncertainty and Incompleteness
Venue: arXiv cs.AI 2013
Year: 2013

Two major difficulties in using default logics are their intractability and the problem of selecting among multiple extensions. We propose an approach to these problems based on integrating nommonotonic reasoning with plausible reasoning based on triangular norms. A previously proposed system for reasoning with uncertainty (RUM) performs uncertain monotonic inferences on an acyclic graph. We have extended RUM to allow nommonotonic inferences and cycles within nonmonotonic rules. By restricting the size and complexity of the nommonotonic cycles we can still perform efficient inferences. Uncertainty measures provide a basis for deciding among multiple defaults. Different algorithms and heuristics for finding the optimal defaults are discussed.
BaRT: A Bayesian Reasoning Tool for Knowledge Based Systems
Venue: arXiv cs.AI 2013
Year: 2013

As the technology for building knowledge based systems has matured, important lessons have been learned about the relationship between the architecture of a system and the nature of the problems it is intended to solve. We are implementing a knowledge engineering tool called BART that is designed with these lessons in mind. BART is a Bayesian reasoning tool that makes belief networks and other probabilistic techniques available to knowledge engineers building classificatory problem solvers. BART has already been used to develop a decision aid for classifying ship images, and it is currently being used to manage uncertainty in systems concerned with analyzing intelligence reports. This paper discusses how state-of-the-art probabilistic methods fit naturally into a knowledge based approach to classificatory problem solving, and describes the current capabilities of BART.
An Empirical Evaluation of a Randomized Algorithm for Probabilistic Inference
Venue: arXiv cs.AI 2013
Year: 2013

In recent years, researchers in decision analysis and artificial intelligence (Al) have used Bayesian belief networks to build models of expert opinion. Using standard methods drawn from the theory of computational complexity, workers in the field have shown that the problem of probabilistic inference in belief networks is difficult and almost certainly intractable. K N ET, a software environment for constructing knowledge-based systems within the axiomatic framework of decision theory, contains a randomized approximation scheme for probabilistic inference. The algorithm can, in many circumstances, perform efficient approximate inference in large and richly interconnected models of medical diagnosis. Unlike previously described stochastic algorithms for probabilistic inference, the randomized approximation scheme computes a priori bounds on running time by analyzing the structure and contents of the belief network. In this article, we describe a randomized algorithm for probabilistic inference and analyze its performance mathematically. Then, we devote the major portion of the paper to a discussion of the algorithm's empirical behavior. The results indicate that the generation of good trials (that is, trials whose distribution closely matches the true distribution), rather than the computation of numerous mediocre trials, dominates the performance of stochastic simulation. Key words: probabilistic inference, belief networks, stochastic simulation, computational complexity theory, randomized algorithms.
Interval Influence Diagrams
Venue: arXiv cs.AI 2013
Year: 2013

We describe a mechanism for performing probabilistic reasoning in influence diagrams using interval rather than point valued probabilities. We derive the procedures for node removal (corresponding to conditional expectation) and arc reversal (corresponding to Bayesian conditioning) in influence diagrams where lower bounds on probabilities are stored at each node. The resulting bounds for the transformed diagram are shown to be optimal within the class of constraints on probability distributions that can be expressed exclusively as lower bounds on the component probabilities of the diagram. Sequences of these operations can be performed to answer probabilistic queries with indeterminacies in the input and for performing sensitivity analysis on an influence diagram. The storage requirements and computational complexity of this approach are comparable to those for point-valued probabilistic inference mechanisms, making the approach attractive for performing sensitivity analysis and where probability information is not available. Limited empirical data on an implementation of the methodology are provided.
Weighing and Integrating Evidence for Stochastic Simulation in Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

Stochastic simulation approaches perform probabilistic inference in Bayesian networks by estimating the probability of an event based on the frequency that the event occurs in a set of simulation trials. This paper describes the evidence weighting mechanism, for augmenting the logic sampling stochastic simulation algorithm [Henrion, 1986]. Evidence weighting modifies the logic sampling algorithm by weighting each simulation trial by the likelihood of a network's evidence given the sampled state node values for that trial. We also describe an enhancement to the basic algorithm which uses the evidential integration technique [Chin and Cooper, 1987]. A comparison of the basic evidence weighting mechanism with the Markov blanket algorithm [Pearl, 1987], the logic sampling algorithm, and the evidence integration algorithm is presented. The comparison is aided by analyzing the performance of the algorithms in a simple example network.
Deciding Consistency of Databases Containing Defeasible and Strict Information
Venue: arXiv cs.AI 2013
Year: 2013

We propose a norm of consistency for a mixed set of defeasible and strict sentences, based on a probabilistic semantics. This norm establishes a clear distinction between knowledge bases depicting exceptions and those containing outright contradictions. We then define a notion of entailment based also on probabilistic considerations and provide a characterization of the relation between consistency and entailment. We derive necessary and sufficient conditions for consistency, and provide a simple decision procedure for testing consistency and deciding whether a sentence is entailed by a database. Finally, it is shown that if al1 sentences are Horn clauses, consistency and entailment can be tested in polynomial time.
When Should a Decision Maker Ignore the Advice of a Decision Aid?
Venue: arXiv cs.AI 2013
Year: 2013

This paper argues that the principal difference between decision aids and most other types of information systems is the greater reliance of decision aids on fallible algorithms--algorithms that sometimes generate incorrect advice. It is shown that interactive problem solving with a decision aid that is based on a fallible algorithm can easily result in aided performance which is poorer than unaided performance, even if the algorithm, by itself, performs significantly better than the unaided decision maker. This suggests that unless certain conditions are satisfied, using a decision aid as an aid is counterproductive. Some conditions under which a decision aid is best used as an aid are derived.
Model-based Influence Diagrams for Machine Vision
Venue: arXiv cs.CV 2013
Year: 2013

We show an approach to automated control of machine vision systems based on incremental creation and evaluation of a particular family of influence diagrams that represent hypotheses of imagery interpretation and possible subsequent processing decisions. In our approach, model-based machine vision techniques are integrated with hierarchical Bayesian inference to provide a framework for representing and matching instances of objects and relationships in imagery and for accruing probabilities to rank order conflicting scene interpretations. We extend a result of Tatman and Shachter to show that the sequence of processing decisions derived from evaluating the diagrams at each stage is the same as the sequence that would have been derived by evaluating the final influence diagram that contains all random variables created during the run of the vision system.
Defeasible Decisions: What the Proposal is and isn't
Venue: arXiv cs.AI 2013
Year: 2013

In two recent papers, I have proposed a description of decision analysis that differs from the Bayesian picture painted by Savage, Jeffrey and other classic authors. Response to this view has been either overly enthusiastic or unduly pessimistic. In this paper I try to place the idea in its proper place, which must be somewhere in between. Looking at decision analysis as defeasible reasoning produces a framework in which planning and decision theory can be integrated, but work on the details has barely begun. It also produces a framework in which the meta-decision regress can be stopped in a reasonable way, but it does not allow us to ignore meta-level decisions. The heuristics for producing arguments that I have presented are only supposed to be suggestive; but they are not open to the egregious errors about which some have worried. And though the idea is familiar to those who have studied heuristic search, it is somewhat richer because the control of dialectic is more interesting than the deepening of search.
Experiments Using Belief Functions and Weights of Evidence incorporating Statistical Data and Expert Opinions
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents some ideas and results of using uncertainty management methods in the presence of data in preference to other statistical and machine learning methods. A medical domain is used as a test-bed with data available from a large hospital database system which collects symptom and outcome information about patients. Data is often missing, of many variable types and sample sizes for particular outcomes is not large. Uncertainty management methods are useful for such domains and have the added advantage of allowing for expert modification of belief values originally obtained from data. Methodological considerations for using belief functions on statistical data are dealt with in some detail. Expert opinions are Incorporated at various levels of the project development and results are reported on an application to liver disease diagnosis. Recent results contrasting the use of weights of evidence and logistic regression on another medical domain are also presented.
A Scalable and Nearly Uniform Generator of SAT Witnesses
Venue: arXiv cs.LO 2013
Year: 2013

Functional verification constitutes one of the most challenging tasks in the development of modern hardware systems, and simulation-based verification techniques dominate the functional verification landscape. A dominant paradigm in simulation-based verification is directed random testing, where a model of the system is simulated with a set of random test stimuli that are uniformly or near-uniformly distributed over the space of all stimuli satisfying a given set of constraints. Uniform or near-uniform generation of solutions for large constraint sets is therefore a problem of theoretical and practical interest. For Boolean constraints, prior work offered heuristic approaches with no guarantee of performance, and theoretical approaches with proven guarantees, but poor performance in practice. We offer here a new approach with theoretical performance guarantees and demonstrate its practical utility on large constraint sets.
Online Power-Managing Strategy with Hard Real-Time Guarantees
Venue: arXiv cs.DS 2013
Year: 2013

We consider the problem of online dynamic power management that provides hard real-time guarantees. In this problem, each of the given jobs is associated with an arrival time, a deadline, and an execution time, and the objective is to decide a schedule of the jobs as well as a sequence of state transitions on the processors so as to minimize the total energy consumption. In this paper, we examine the problem complexity and provide online strategies to achieve energy-efficiency. First, we show that the competitive factor of any online algorithm for this problem is at least 2.06. Then we present an online algorithm which gives a 4-competitive schedule. When the execution times of the jobs are unit, we show that the competitive factor improves to 3.59. At the end, the algorithm is generalized to allow a trade-off between the number of processors we use and the energy-efficiency of the resulting schedule.
Self-organization and solution of shortest-path optimization problems with memristive networks
Venue: arXiv cs.ET 2013
Year: 2013

We show that memristive networks-namely networks of resistors with memory-can efficiently solve shortest-path optimization problems. Indeed, the presence of memory (time non-locality) promotes self organization of the network into the shortest possible path(s). We introduce a network entropy function to characterize the self-organized evolution, show the solution of the shortest-path problem and demonstrate the healing property of the solution path. Finally, we provide an algorithm to solve the traveling salesman problem. Similar considerations apply to networks of memcapacitors and meminductors, and networks with memory in various dimensions.
Intrinsic universality in tile self-assembly requires cooperation
Venue: arXiv cs.CC 2013
Year: 2013

We prove a negative result on the power of a model of algorithmic self-assembly for which it has been notoriously difficult to find general techniques and results. Specifically, we prove that Winfree's abstract Tile Assembly Model, when restricted to use noncooperative tile binding, is not intrinsically universal. This stands in stark contrast to the recent result that, via cooperative binding, the abstract Tile Assembly Model is indeed intrinsically universal. Noncooperative self-assembly, also known as "temperature 1", is where tiles bind to each other if they match on one or more sides, whereas cooperative binding requires binding on multiple sides. Our result shows that the change from single- to multi-sided binding qualitatively improves the kinds of dynamics and behavior that these models of nanoscale self-assembly are capable of. Our lower bound on simulation power holds in both two and three dimensions; the latter being quite surprising given that three-dimensional noncooperative tile assembly systems simulate Turing machines. On the positive side, we exhibit a three-dimensional noncooperative self-assembly tile set capable of simulating any two-dimensional noncooperative self-assembly system. Our negative result can be interpreted to mean that Turing universal algorithmic behavior in self-assembly does not imply the ability to simulate arbitrary algorithmic self-assembly processes.
Data Hiding in Binary Image using Block Parity
Venue: arXiv cs.CR 2013
Year: 2013

Secret data hiding in binary images is more difficult than other formats since binary images require only one bit representation to indicate black and white. This study proposes a new method for data hiding in binary images using optimized bit position to replace a secret bit. This method manipulates blocks, which are sub-divided. The parity bit for a specified block decides whether to change or not, to embed a secret bit. By finding the best position to insert a secret bit for each divided block, the image quality of the resulting stego-image can be improved, while maintaining low computational complexity.The experimental results show that the proposed method has an improvement with respect to a previous work.
Towards a Workload for Evolutionary Analytics
Venue: arXiv cs.DB 2013
Year: 2013

Emerging data analysis involves the ingestion and exploration of new data sets, application of complex functions, and frequent query revisions based on observing prior query answers. We call this new type of analysis evolutionary analytics and identify its properties. This type of analysis is not well represented by current benchmark workloads. In this paper, we present a workload and identify several metrics to test system support for evolutionary analytics. Along with our metrics, we present methodologies for running the workload that capture this analytical scenario.
Stochastic Analysis on RAID Reliability for Solid-State Drives
Venue: arXiv cs.PF 2013
Year: 2013

Solid-state drives (SSDs) have been widely deployed in desktops and data centers. However, SSDs suffer from bit errors, and the bit error rate is time dependent since it increases as an SSD wears down. Traditional storage systems mainly use parity-based RAID to provide reliability guarantees by striping redundancy across multiple devices, but the effectiveness of RAID in SSDs remains debatable as parity updates aggravate the wearing and bit error rates of SSDs. In particular, an open problem is that how different parity distributions over multiple devices, such as the even distribution suggested by conventional wisdom, or uneven distributions proposed in recent RAID schemes for SSDs, may influence the reliability of an SSD RAID array. To address this fundamental problem, we propose the first analytical model to quantify the reliability dynamics of an SSD RAID array. Specifically, we develop a "non-homogeneous" continuous time Markov chain model, and derive the transient reliability solution. We validate our model via trace-driven simulations and conduct numerical analysis to provide insights into the reliability dynamics of SSD RAID arrays under different parity distributions and subject to different bit error rates and array configurations. Designers can use our model to decide the appropriate parity distribution based on their reliability requirements.
Privacy-preserving Data Mining, Sharing and Publishing
Venue: arXiv cs.DB 2013
Year: 2013

The goal of the paper is to present different approaches to privacy-preserving data sharing and publishing in the context of e-health care systems. In particular, the literature review on technical issues in privacy assurance and current real-life high complexity implementation of medical system that assumes proper data sharing mechanisms are presented in the paper.
Client-Driven Content Extraction Associated with Table
Venue: arXiv cs.CV 2013
Year: 2013

The goal of the project is to extract content within table in document images based on learnt patterns. Real-world users i.e., clients first provide a set of key fields within the table which they think are important. These are first used to represent the graph where nodes are labelled with semantics including other features and edges are attributed with relations. Attributed relational graph (ARG) is then employed to mine similar graphs from a document image. Each mined graph will represent an item within the table, and hence a set of such graphs will compose a table. We have validated the concept by using a real-world industrial problem.
On growing connected beta-skeletons
Venue: arXiv cs.CG 2013
Year: 2013

A $β$-skeleton, $β\geq 1$, is a planar proximity undirected graph of an Euclidean points set, where nodes are connected by an edge if their lune-based neighbourhood contains no other points of the given set. Parameter $β$ determines the size and shape of the lune-based neighbourhood. A $β$-skeleton of a random planar set is usually a disconnected graph for $β>2$. With the increase of $β$, the number of edges in the $β$-skeleton of a random graph decreases. We show how to grow stable $β$-skeletons, which are connected for any given value of $β$ and characterise morphological transformations of the skeletons governed by $β$ and a degree of approximation. We speculate how the results obtained can be applied in biology and chemistry.