OpenRaiser/Intern-Atlas huggingface dataset:
Common Information and Secret Key Capacity
Venue: arXiv cs.IT 2013
Year: 2013

We study the generation of a secret key of maximum rate by a pair of terminals observing correlated sources and with the means to communicate over a noiseless public com- munication channel. Our main result establishes a structural equivalence between the generation of a maximum rate secret key and the generation of a common randomness that renders the observations of the two terminals conditionally independent. The minimum rate of such common randomness, termed interactive common information, is related to Wyner's notion of common information, and serves to characterize the minimum rate of interactive public communication required to generate an optimum rate secret key. This characterization yields a single-letter expression for the aforementioned communication rate when the number of rounds of interaction are bounded. An application of our results shows that interaction does not reduce this rate for binary symmetric sources. Further, we provide an example for which interaction does reduce the minimum rate of communication. Also, certain invariance properties of common information quantities are established that may be of independent interest.
Overview of Visualization Tools for Web Browser History Data
Venue: arXiv cs.HC 2013
Year: 2013

Nowadays, the Web has become one of the most widespread platforms for information change and retrieval. As it becomes easier to publish documents, as the number of users, and thus publishers, increases and as the number of documents grows, searching for information is turning into a cumbersome and time-consuming operation. Because of the loose interconnection between documents, people have difficulty remembering where they have been and returning to previously visited pages. Navigation through the web faces problems of locating oneself with respect to space and time. The idea of graphical assistance navigation is to help users to find their paths in hyperspace by adapting the style of link presentation to the goals, knowledge and other characteristics of an individual user. We first introduce the concepts related to web navigation; we then present an overview of different graphical navigation tools and techniques. We conclude by presenting a comparative table of these tools based on some pertinent criteria.
Resilience of Dynamic Overlays through Local Interactions
Venue: arXiv cs.DC 2013
Year: 2013

This paper presents a self-organizing protocol for dynamic (unstructured P2P) overlay networks, which allows to react to the variability of node arrivals and departures. Through local interactions, the protocol avoids that the departure of nodes causes a partitioning of the overlay. We show that it is sufficient to have knowledge about 1st and 2nd neighbours, plus a simple interaction P2P protocol, to make unstructured networks resilient to node faults. A simulation assessment over different kinds of overlay networks demonstrates the viability of the proposal.
Genetic Soundtracks: Creative Matching of Audio to Video
Venue: arXiv cs.MM 2013
Year: 2013

The matching of the soundtrack in a movie or a video can have an enormous influence in the message being conveyed and its impact, in the sense of involvement and engagement, and ultimately in their aesthetic and entertainment qualities. Art is often associated with creativity, implying the presence of inspiration, originality and appropriateness. Evolutionary systems provides us with the novelty, showing us new and subtly different solutions in every generation, possibly stimulating the creativity of the human using the system. In this paper, we present Genetic Soundtracks, an evolutionary approach to the creative matching of audio to a video. It analyzes both media to extract features based on their content, and adopts genetic algorithms, with the purpose of truncating, combining and adjusting audio clips, to align and match them with the video scenes.
Convex hull: Incremental variations on the Akl-Toussaint heuristics Simple, optimal and space-saving convex hull algorithms
Venue: arXiv cs.CG 2013
Year: 2013

Convex hulls are a fundamental geometric tool used in a number of algorithms. A famous paper by Akl and Toussaint in 1978 described a way to reduce the number of points involved in the computation, which is since known as the Akl-Toussaint heuristics. This paper first studies what this heurstics really represents in terms of reduction of points and demonstrates that the optimum selection is reached using an octogon as the remaining number of points is in O(sqrt(N)) rather than the usual O(N). Then it focuses on optimising the overall computational efficiency in a convex hull computation. Although the heuristics is usually used as a first step in computations one can obtain the convex hull directly from the heuristics's basis. First a simple incremental implementation is described, and if the number of characteristic points of the Akl-Toussaint heuristics p is taken as a parametre the convex hull is then computed in a O(N(p+h/p)) average complexity or O(Nh) asymptotic complexity. Given the relative constant factor of 1/p however experimental results show that this algorithm should be considered linear in average. Worst-case complexity is in O(N^2) and space complexity is O(h) but could be O(1) if the required output is the array of convex vertices's indexes. Then a remark on why the basic incremental method should be preferred for average cases is made. Finally an optimal linear algorithm both in average and worst-case and using a minimal space complexity in O(sqrt(N)) in average (or O(1) if in-place computation is allowed) is presented.
Image Classification by Feature Dimension Reduction and Graph based Ranking
Venue: arXiv cs.CV 2013
Year: 2013

Dimensionality reduction (DR) of image features plays an important role in image retrieval and classification tasks. Recently, two types of methods have been proposed to improve the both the accuracy and efficiency for the dimensionality reduction problem. One uses Non-negative matrix factorization (NMF) to describe the image distribution on the space of base matrix. Another one for dimension reduction trains a subspace projection matrix to project original data space into some low-dimensional subspaces which have deep architecture, so that the low-dimensional codes would be learned. At the same time, the graph based similarity learning algorithm which tries to exploit contextual information for improving the effectiveness of image rankings is also proposed for image class and retrieval problem. In this paper, after above two methods mentioned are utilized to reduce the high-dimensional features of images respectively, we learn the graph based similarity for the image classification problem. This paper compares the proposed approach with other approaches on an image database.
Stochastic Simulation of Bayesian Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

This paper examines Bayesian belief network inference using simulation as a method for computing the posterior probabilities of network variables. Specifically, it examines the use of a method described by Henrion, called logic sampling, and a method described by Pearl, called stochastic simulation. We first review the conditions under which logic sampling is computationally infeasible. Such cases motivated the development of the Pearl's stochastic simulation algorithm. We have found that this stochastic simulation algorithm, when applied to certain networks, leads to much slower than expected convergence to the true posterior probabilities. This behavior is a result of the tendency for local areas in the network to become fixed through many simulation cycles. The time required to obtain significant convergence can be made arbitrarily long by strengthening the probabilistic dependency between nodes. We propose the use of several forms of graph modification, such as graph pruning, arc reversal, and node reduction, in order to convert some networks into formats that are computationally more efficient for simulation.
Temporal Reasoning About Uncertain Worlds
Venue: arXiv cs.AI 2013
Year: 2013

We present a program that manages a database of temporally scoped beliefs. The basic functionality of the system includes maintaining a network of constraints among time points, supporting a variety of fetches, mediating the application of causal rules, monitoring intervals of time for the addition of new facts, and managing data dependencies that keep the database consistent. At this level the system operates independent of any measure of belief or belief calculus. We provide an example of how an application program mi9ght use this functionality to implement a belief calculus.
Coefficients of Relations for Probabilistic Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

Definitions and notations with historical references are given for some numerical coefficients commonly used to quantify relations among collections of objects for the purpose of expressing approximate knowledge and probabilistic reasoning.
Satisfaction of Assumptions is a Weak Predictor of Performance
Venue: arXiv cs.AI 2013
Year: 2013

This paper demonstrates a methodology for examining the accuracy of uncertain inference systems (UIS), after their parameters have been optimized, and does so for several common UIS's. This methodology may be used to test the accuracy when either the prior assumptions or updating formulae are not exactly satisfied. Surprisingly, these UIS's were revealed to be no more accurate on the average than a simple linear regression. Moreover, even on prior distributions which were deliberately biased so as give very good accuracy, they were less accurate than the simple probabilistic model which assumes marginal independence between inputs. This demonstrates that the importance of updating formulae can outweigh that of prior assumptions. Thus, when UIS's are judged by their final accuracy after optimization, we get completely different results than when they are judged by whether or not their prior assumptions are perfectly satisfied.
Comparisons of Reasoning Mechanisms for Computer Vision
Venue: arXiv cs.CV 2013
Year: 2013

An evidential reasoning mechanism based on the Dempster-Shafer theory of evidence is introduced. Its performance in real-world image analysis is compared with other mechanisms based on the Bayesian formalism and a simple weight combination method.
The Role of Calculi in Uncertain Inference Systems
Venue: arXiv cs.AI 2013
Year: 2013

Much of the controversy about methods for automated decision making has focused on specific calculi for combining beliefs or propagating uncertainty. We broaden the debate by (1) exploring the constellation of secondary tasks surrounding any primary decision problem, and (2) identifying knowledge engineering concerns that present additional representational tradeoffs. We argue on pragmatic grounds that the attempt to support all of these tasks within a single calculus is misguided. In the process, we note several uncertain reasoning objectives that conflict with the Bayesian ideal of complete specification of probabilities and utilities. In response, we advocate treating the uncertainty calculus as an object language for reasoning mechanisms that support the secondary tasks. Arguments against Bayesian decision theory are weakened when the calculus is relegated to this role. Architectures for uncertainty handling that take statements in the calculus as objects to be reasoned about offer the prospect of retaining normative status with respect to decision making while supporting the other tasks in uncertain reasoning.
Evidential Reasoning in Image Understanding
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, we present some results of evidential reasoning in understanding multispectral images of remote sensing systems. The Dempster-Shafer approach of combination of evidences is pursued to yield contextual classification results, which are compared with previous results of the Bayesian context free classification, contextual classifications of dynamic programming and stochastic relaxation approaches.
Integrating Logical and Probabilistic Reasoning for Decision Making
Venue: arXiv cs.AI 2013
Year: 2013

We describe a representation and a set of inference methods that combine logic programming techniques with probabilistic network representations for uncertainty (influence diagrams). The techniques emphasize the dynamic construction and solution of probabilistic and decision-theoretic models for complex and uncertain domains. Given a query, a logical proof is produced if possible; if not, an influence diagram based on the query and the knowledge of the decision domain is produced and subsequently solved. A uniform declarative, first-order, knowledge representation is combined with a set of integrated inference procedures for logical, probabilistic, and decision-theoretic reasoning.
Compiling Fuzzy Logic Control Rules to Hardware Implementations
Venue: arXiv cs.AI 2013
Year: 2013

A major aspect of human reasoning involves the use of approximations. Particularly in situations where the decision-making process is under stringent time constraints, decisions are based largely on approximate, qualitative assessments of the situations. Our work is concerned with the application of approximate reasoning to real-time control. Because of the stringent processing speed requirements in such applications, hardware implementations of fuzzy logic inferencing are being pursued. We describe a programming environment for translating fuzzy control rules into hardware realizations. Two methods of hardware realizations are possible. The First is based on a special purpose chip for fuzzy inferencing. The second is based on a simple memory chip. The ability to directly translate a set of decision rules into hardware implementations is expected to make fuzzy control an increasingly practical approach to the control of complex systems.
An Algorithm for Computing Probabilistic Propositions
Venue: arXiv cs.AI 2013
Year: 2013

A method for computing probabilistic propositions is presented. It assumes the availability of a single external routine for computing the probability of one instantiated variable, given a conjunction of other instantiated variables. In particular, the method allows belief network algorithms to calculate general probabilistic propositions over nodes in the network. Although in the worst case the time complexity of the method is exponential in the size of a query, it is polynomial in the size of a number of common types of queries.
Optimal DNA shotgun sequencing: Noisy reads are as good as noiseless reads
Venue: arXiv cs.IT 2013
Year: 2013

We establish the fundamental limits of DNA shotgun sequencing under noisy reads. We show a surprising result: for the i.i.d. DNA model, noisy reads are as good as noiseless reads, provided that the noise level is below a certain threshold which can be surprisingly high. As an example, for a uniformly distributed DNA sequence and a symmetric substitution noisy read channel, the threshold is as high as 19%.
On MITL and alternating timed automata
Venue: arXiv cs.FL 2013
Year: 2013

One clock alternating timed automata OCATA have been recently introduced as natural extension of (one clock) timed automata to express the semantics of MTL (Ouaknine, Worrell 2005). We consider the application of OCATA to problem of model-checking MITL formulas (a syntactic fragment of MTL) against timed automata. We introduce a new semantics for OCATA where, intuitively, clock valuations are intervals instead of single real values. Thanks to this new semantics, we show that we can bound the number of clock copies that are necessary to allow an OCATA to recognise the models of an MITL formula. Equipped with this technique, we propose a new algorithm to translate an MITL formula into a timed automaton, and we sketch several ideas to define new model checking algorithms for MITL.
Un modèle booléen pour l'énumération des siphons et des pièges minimaux dans les réseaux de Petri
Venue: arXiv cs.CE 2013
Year: 2013

Petri-nets are a simple formalism for modeling concurrent computation. Recently, they have emerged as a powerful tool for the modeling and analysis of biochemical reaction networks, bridging the gap between purely qualitative and quantitative models. These networks can be large and complex, which makes their study difficult and computationally challenging. In this paper, we focus on two structural properties of Petri-nets, siphons and traps, that bring us information about the persistence of some molecular species. We present two methods for enumerating all minimal siphons and traps of a Petri-net by iterating the resolution of a boolean model interpreted as either a SAT or a CLP(B) program. We compare the performance of these methods with a state-of-the-art dedicated algorithm of the Petri-net community. We show that the SAT and CLP(B) programs are both faster. We analyze why these programs perform so well on the models of the repository of biological models biomodels.net, and propose some hard instances for the problem of minimal siphons enumeration.
Shortest Repetition-Free Words Accepted by Automata
Venue: arXiv cs.FL 2013
Year: 2013

We consider the following problem: given that a finite automaton $M$ of $N$ states accepts at least one $k$-power-free (resp., overlap-free) word, what is the length of the shortest such word accepted? We give upper and lower bounds which, unfortunately, are widely separated.
Cloud Computing: a Prologue
Venue: arXiv cs.DC 2013
Year: 2013

An emerging internet based super computing model is represented by cloud computing. Cloud computing is the convergence and evolution of several concepts from virtualization, distributed storage, grid, and automation management to enable a more flexible approach for deploying and scaling applications. However, cloud computing moves the application software and databases to the large data centers, where the management of the data and services may not be fully trustworthy. The concept of cloud computing on the basis of the various definitions available in the industry and the characteristics of cloud computing are being analyzed in this paper. The paper also describes the main cloud service providers and their products followed by primary cloud computing operating systems.
Towards The Inductive Acquisition of Temporal Knowledge
Venue: arXiv cs.AI 2013
Year: 2013

The ability to predict the future in a given domain can be acquired by discovering empirically from experience certain temporal patterns that tend to repeat unerringly. Previous works in time series analysis allow one to make quantitative predictions on the likely values of certain linear variables. Since certain types of knowledge are better expressed in symbolic forms, making qualitative predictions based on symbolic representations require a different approach. A domain independent methodology called TIM (Time based Inductive Machine) for discovering potentially uncertain temporal patterns from real time observations using the technique of inductive inference is described here.
Deriving And Combining Continuous Possibility Functions in the Framework of Evidential Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

To develop an approach to utilizing continuous statistical information within the Dempster- Shafer framework, we combine methods proposed by Strat and by Shafero We first derive continuous possibility and mass functions from probability-density functions. Then we propose a rule for combining such evidence that is simpler and more efficiently computed than Dempster's rule. We discuss the relationship between Dempster's rule and our proposed rule for combining evidence over continuous frames.
An Application of Non-Monotonic Probabilistic Reasoning to Air Force Threat Correlation
Venue: arXiv cs.AI 2013
Year: 2013

Current approaches to expert systems' reasoning under uncertainty fail to capture the iterative revision process characteristic of intelligent human reasoning. This paper reports on a system, called the Non-monotonic Probabilist, or NMP (Cohen, et al., 1985). When its inferences result in substantial conflict, NMP examines and revises the assumptions underlying the inferences until conflict is reduced to acceptable levels. NMP has been implemented in a demonstration computer-based system, described below, which supports threat correlation and in-flight route replanning by Air Force pilots.
Computing Reference Classes
Venue: arXiv cs.AI 2013
Year: 2013

For any system with limited statistical knowledge, the combination of evidence and the interpretation of sampling information require the determination of the right reference class (or of an adequate one). The present note (1) discusses the use of reference classes in evidential reasoning, and (2) discusses implementations of Kyburg's rules for reference classes. This paper contributes the first frank discussion of how much of Kyburg's system is needed to be powerful, how much can be computed effectively, and how much is philosophical fat.
Distributed Revision of Belief Commitment in Multi-Hypothesis Interpretations
Venue: arXiv cs.AI 2013
Year: 2013

This paper extends the applications of belief-networks to include the revision of belief commitments, i.e., the categorical acceptance of a subset of hypotheses which, together, constitute the most satisfactory explanation of the evidence at hand. A coherent model of non-monotonic reasoning is established and distributed algorithms for belief revision are presented. We show that, in singly connected networks, the most satisfactory explanation can be found in linear time by a message-passing algorithm similar to the one used in belief updating. In multiply-connected networks, the problem may be exponentially hard but, if the network is sparse, topological considerations can be used to render the interpretation task tractable. In general, finding the most probable combination of hypotheses is no more complex than computing the degree of belief for any individual hypothesis. Applications to medical diagnosis are illustrated.
A Causal Bayesian Model for the Diagnosis of Appendicitis
Venue: arXiv cs.AI 2013
Year: 2013

The causal Bayesian approach is based on the assumption that effects (e.g., symptoms) that are not conditionally independent with respect to some causal agent (e.g., a disease) are conditionally independent with respect to some intermediate state caused by the agent, (e.g., a pathological condition). This paper describes the development of a causal Bayesian model for the diagnosis of appendicitis. The paper begins with a description of the standard Bayesian approach to reasoning about uncertainty and the major critiques it faces. The paper then lays the theoretical groundwork for the causal extension of the Bayesian approach, and details specific improvements we have developed. The paper then goes on to describe our knowledge engineering and implementation and the results of a test of the system. The paper concludes with a discussion of how the causal Bayesian approach deals with the criticisms of the standard Bayesian model and why it is superior to alternative approaches to reasoning about uncertainty popular in the Al community.
A Backwards View for Assessment
Venue: arXiv cs.AI 2013
Year: 2013

Much artificial intelligence research focuses on the problem of deducing the validity of unobservable propositions or hypotheses from observable evidence.! Many of the knowledge representation techniques designed for this problem encode the relationship between evidence and hypothesis in a directed manner. Moreover, the direction in which evidence is stored is typically from evidence to hypothesis.
DAVID: Influence Diagram Processing System for the Macintosh
Venue: arXiv cs.AI 2013
Year: 2013

Influence diagrams are a directed graph representation for uncertainties as probabilities. The graph distinguishes between those variables which are under the control of a decision maker (decisions, shown as rectangles) and those which are not (chances, shown as ovals), as well as explicitly denoting a goal for solution (value, shown as a rounded rectangle.