OpenRaiser/Intern-Atlas huggingface dataset:
Modèle flou d'expression des préférences basé sur les CP-Nets
Venue: arXiv cs.AI 2013
Year: 2013

This article addresses the problem of expressing preferences in flexible queries while basing on a combination of the fuzzy logic theory and Conditional Preference Networks or CP-Nets.
Secure End-to-End Communication with Optimal Throughput in Unreliable Networks
Venue: arXiv cs.NI 2013
Year: 2013

We demonstrate the feasibility of end-to-end communication in highly unreliable networks. Modeling a network as a graph with vertices representing nodes and edges representing the links between them, we consider two forms of unreliability: unpredictable edge-failures, and deliberate deviation from protocol specifications by corrupt nodes. We present a robust routing protocol for end-to-end communication that is simultaneously resilient to both forms of unreliability. In particular, we prove rigorously that our protocol is SECURE against the actions of the corrupt nodes, achieves correctness (Receiver gets ALL of the messages from Sender, in order and without modification), and enjoys provably optimal throughput performance, as measured using competitive analysis. Furthermore, our protocol does not incur any asymptotic memory overhead as compared to other protocols that are unable to handle malicious interference of corrupt nodes. In particular, our protocol requires O(n^2) memory per processor, where n is the size of the network. This represents an O(n^2) improvement over all existing protocols that have been designed for this network model.
Evolutionary Design of Digital Circuits Using Genetic Programming
Venue: arXiv cs.NE 2013
Year: 2013

For simple digital circuits, conventional method of designing circuits can easily be applied. But for complex digital circuits, the conventional method of designing circuits is not fruitfully applicable because it is time-consuming. On the contrary, Genetic Programming is used mostly for automatic program generation. The modern approach for designing Arithmetic circuits, commonly digital circuits, is based on Graphs. This graph-based evolutionary design of arithmetic circuits is a method of optimized designing of arithmetic circuits. In this paper, a new technique for evolutionary design of digital circuits is proposed using Genetic Programming (GP) with Subtree Mutation in place of Graph-based design. The results obtained using this technique demonstrates the potential capability of genetic programming in digital circuit design with limited computer algorithms. The proposed technique, helps to simplify and speed up the process of designing digital circuits, discovers a variation in the field of digital circuit design where optimized digital circuits can be successfully and effectively designed.
Simulating the Smart Grid
Venue: arXiv cs.SY 2013
Year: 2013

Major challenges for the transition of power systems do not only tackle power electronics but also communication technology, power market economy and user acceptance studies. Simulation is an important research method therein, as it helps to avoid costly failures. A common smart grid simulation platform is still missing. We introduce a conceptual model of agents in multiple flow networks. Flow networks extend the depth of established power flow analysis through use of networks of information flow and financial transactions. We use this model as a basis for comparing different power system simulators. Furthermore, a quantitative comparison of simulators is done to facilitate the decision for a suitable tool in comprehensive smart grid simulation.
FooPar: A Functional Object Oriented Parallel Framework in Scala
Venue: arXiv cs.DC 2013
Year: 2013

We present FooPar, an extension for highly efficient Parallel Computing in the multi-paradigm programming language Scala. Scala offers concise and clean syntax and integrates functional programming features. Our framework FooPar combines these features with parallel computing techniques. FooPar is designed modular and supports easy access to different communication backends for distributed memory architectures as well as high performance math libraries. In this article we use it to parallelize matrix matrix multiplication and show its scalability by a isoefficiency analysis. In addition, results based on a empirical analysis on two supercomputers are given. We achieve close-to-optimal performance wrt. theoretical peak performance. Based on this result we conclude that FooPar allows to fully access Scala's design features without suffering from performance drops when compared to implementations purely based on C and MPI.
The H-index can be easily manipulated
Venue: arXiv cs.CC 2013
Year: 2013

We prove two complexity results about the H-index concerned with the Google scholar merge operation on one's scientific articles. The results show that, although it is hard to merge one's articles in an optimal way, it is easy to merge them in such a way that one's H-index increases. This suggests the need for an alternative scientific performance measure that is resistant to this type of manipulation.
Active Consensus over Sensor Networks via Randomized Communication
Venue: arXiv cs.NI 2013
Year: 2013

Distributed consensus has been widely studied for sensor network applications. Whereas the asymptotic convergence rate has been extensively explored in prior work, other important and practical issues, including energy efficiency and link reliability, have received relatively little attention. In this paper, we present a distributed consensus approach that can achieve a good balance between convergence rate and energy efficiency. The approach selects a subset of links that significantly contribute to the formation of consensus at each iteration, thus adapting the network's topology dynamically to the changes of the sensor states. A global optimization problem is formulated for optimal link selection, which is subsequently factorized into sub-problems that can be solved locally, and practically via approximation. An algorithm is derived to solve the approximation efficiently, using quadratic programming (QP) relaxation and random sampling. Simulations on networks of different types demonstrate that the proposed method reduces the communication energy costs without significantly impacting the convergence rate and that the approach is robust to link failures.
Stability and performance of stochastic predictive control
Venue: arXiv cs.SY 2013
Year: 2013

This article is concerned with stability and performance of controlled stochastic processes under receding horizon policies. We carry out a systematic study of methods to guarantee stability under receding horizon policies via appropriate selections of cost functions in the underlying finite-horizon optimal control problem. We also obtain quantitative bounds on the performance of the system under receding horizon policies as measured by the long-run expected average cost. The results are illustrated with the help of several simple examples.
On the predictability of the number of convex vertices
Venue: arXiv cs.CG 2013
Year: 2013

Convex hulls are a fundamental geometric tool used in a number of algorithms. As a side-effect of exhaustive tests for an algorithm for which a convex hull computation was the first step, interesting experimental results were found and are the sunject of this paper. They establish that the number of convex vertices of natural datasets can be predicted, if not precisely at least within a defined range. Namely it was found that the number of convex vertices of a dataset of N points lies in the range 2.35 N^0.091 <= h <= 19.19 N^0.091. This range obviously does not describe neither natural nor artificial worst-cases but corresponds to the distributions of natural data. This can be used for instance to define a starting size for pre-allocated arrays or to evaluate output-sensitive algorithms. A further consequence of these results is that the random models of data used to test convex hull algorithms should be bounded by rectangles and not as they usually are by circles if they want to represent accurately natural datasets
Modifiable Combining Functions
Venue: arXiv cs.AI 2013
Year: 2013

Modifiable combining functions are a synthesis of two common approaches to combining evidence. They offer many of the advantages of these approaches and avoid some disadvantages. Because they facilitate the acquisition, representation, explanation, and modification of knowledge about combinations of evidence, they are proposed as a tool for knowledge engineers who build systems that reason under uncertainty, not as a normative theory of evidence.
Belief in Belief Functions: An Examination of Shafer's Canonical Examples
Venue: arXiv cs.AI 2013
Year: 2013

In the canonical examples underlying Shafer-Dempster theory, beliefs over the hypotheses of interest are derived from a probability model for a set of auxiliary hypotheses. Beliefs are derived via a compatibility relation connecting the auxiliary hypotheses to subsets of the primary hypotheses. A belief function differs from a Bayesian probability model in that one does not condition on those parts of the evidence for which no probabilities are specified. The significance of this difference in conditioning assumptions is illustrated with two examples giving rise to identical belief functions but different Bayesian probability distributions.
The Recovery of Causal Poly-Trees from Statistical Data
Venue: arXiv cs.AI 2013
Year: 2013

Poly-trees are singly connected causal networks in which variables may arise from multiple causes. This paper develops a method of recovering ply-trees from empirically measured probability distributions of pairs of variables. The method guarantees that, if the measured distributions are generated by a causal process structured as a ply-tree then the topological structure of such tree can be recovered precisely and, in addition, the causal directionality of the branches can be determined up to the maximum extent possible. The method also pinpoints the minimum (if any) external semantics required to determine the causal relationships among the variables considered.
Theory-Based Inductive Learning: An Integration of Symbolic and Quantitative Methods
Venue: arXiv cs.AI 2013
Year: 2013

The objective of this paper is to propose a method that will generate a causal explanation of observed events in an uncertain world and then make decisions based on that explanation. Feedback can cause the explanation and decisions to be modified. I call the method Theory-Based Inductive Learning (T-BIL). T-BIL integrates deductive learning, based on a technique called Explanation-Based Generalization (EBG) from the field of machine learning, with inductive learning methods from Bayesian decision theory. T-BIL takes as inputs (1) a decision problem involving a sequence of related decisions over time, (2) a training example of a solution to the decision problem in one period, and (3) the domain theory relevant to the decision problem. T-BIL uses these inputs to construct a probabilistic explanation of why the training example is an instance of a solution to one stage of the sequential decision problem. This explanation is then generalized to cover a more general class of instances and is used as the basis for making the next-stage decisions. As the outcomes of each decision are observed, the explanation is revised, which in turn affects the subsequent decisions. A detailed example is presented that uses T-BIL to solve a very general stochastic adaptive control problem for an autonomous mobile robot.
A Measure-Free Approach to Conditioning
Venue: arXiv cs.AI 2013
Year: 2013

In an earlier paper, a new theory of measurefree "conditional" objects was presented. In this paper, emphasis is placed upon the motivation of the theory. The central part of this motivation is established through an example involving a knowledge-based system. In order to evaluate combination of evidence for this system, using observed data, auxiliary at tribute and diagnosis variables, and inference rules connecting them, one must first choose an appropriate algebraic logic description pair (ALDP): a formal language or syntax followed by a compatible logic or semantic evaluation (or model). Three common choices- for this highly non-unique choice - are briefly discussed, the logics being Classical Logic, Fuzzy Logic, and Probability Logic. In all three,the key operator representing implication for the inference rules is interpreted as the often-used disjunction of a negation (b => a) = (b'v a), for any events a,b. However, another reasonable interpretation of the implication operator is through the familiar form of probabilistic conditioning. But, it can be shown - quite surprisingly - that the ALDP corresponding to Probability Logic cannot be used as a rigorous basis for this interpretation! To fill this gap, a new ALDP is constructed consisting of "conditional objects", extending ordinary Probability Logic, and compatible with the desired conditional probability interpretation of inference rules. It is shown also that this choice of ALDP leads to feasible computations for the combination of evidence evaluation in the example. In addition, a number of basic properties of conditional objects and the resulting Conditional Probability Logic are given, including a characterization property and a developed calculus of relations.
On the key exchange with nonlinear polynomial maps of stable degree
Venue: arXiv cs.CR 2013
Year: 2013

We say that the sequence $g_n$, $n\ge 3$, $n \rightarrow \infty$ of polynomial transformation bijective maps of free module $K^n$ over commutative ring $K$ is a sequence of stable degree if the order of $g_n$ is growing with $n$ and the degree of each nonidentical polynomial map of kind ${g_n}^k$ is an independent constant $c$. A transformation $b=τ {g_n}^k τ^{-1}$, where $τ$ is affine bijection, $n$ is large and $k$ is relatively small, can be used as a base of group theoretical Diffie-Hellman key exchange algorithm for the Cremona group $C(K^n)$ of all regular automorphisms of $K^n$. The specific feature of this method is that the order of the base may be unknown for the adversary because of the complexity of its computation. The exchange can be implemented by tools of Computer Algebra (symbolic computations). The adversary can not use the degree of righthandside in $b^x=d$ to evaluate unknown $x$ in this form for the discrete logarithm problem. In the paper we introduce the explicit constructions of sequences of elements of stable degree for cases $c=3$ for each commutative ring $K$ containing at least 3 regular elements and discuss the implementation of related key exchange and public key algorithms.
Are Friends Overrated? A Study for the Social News Aggregator Digg.com
Venue: arXiv cs.SI 2013
Year: 2013

The key feature of online social networks (OSN) is the ability of users to become active, make friends and interact via comments, videos or messages with those around them. This social interaction is typically perceived as critical to the proper functioning of these platforms; therefore, a significant share of OSN research in the recent past has investigated the characteristics and importance of these social links, studying the networks' friendship relations through their topological properties, the structure of the resulting communities and identifying the role and importance of individual members within these networks. In this paper, we present results from a multi-year study of the online social network Digg.com, indicating that the importance of friends and the friend network in the propagation of information is less than originally perceived. While we do note that users form and maintain a social structure along which information is exchanged, the importance of these links and their contribution is very low: Users with even a nearly identical overlap in interests react on average only with a probability of 2% to information propagated and received from friends. Furthermore, in only about 50% of stories that became popular from the entire body of 10 million news we find evidence that the social ties among users were a critical ingredient to the successful spread. Our findings indicate the presence of previously unconsidered factors, the temporal alignment between user activities and the existence of additional logical relationships beyond the topology of the social graph, that are able to drive and steer the dynamics of such OSNs.
Application of Evidential Reasoning to Helicopter Flight Path Control
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a methodology for research and development of the inferencing and knowledge representation aspects of an Expert System approach for performing reasoning under uncertainty in support of a real time vehicle guidance and navigation system. Such a system could be of major benefit for non-terrain following low altitude flight systems operating in foreign hostile environments such as might be experienced by NOE helicopter or similar mission craft. An innovative extension of the evidential reasoning methodology, termed the Sum-and-Lattice-Points Method, has been developed. The research and development effort presented in this paper consists of a formal mathematical development of the Sum-and-Lattice-Points Method, its formulation and representation in a parallel environment, prototype software development of the method within an expert system, and initial testing of the system within the confines of the vehicle guidance system.
Predicting The Performance of Minimax and Product in Game-Tree
Venue: arXiv cs.AI 2013
Year: 2013

The discovery that the minimax decision rule performs poorly in some games has sparked interest in possible alternatives to minimax. Until recently, the only games in which minimax was known to perform poorly were games which were mainly of theoretical interest. However, this paper reports results showing poor performance of minimax in a more common game called kalah. For the kalah games tested, a non-minimax decision rule called the product rule performs significantly better than minimax. This paper also discusses a possible way to predict whether or not minimax will perform well in a game when compared to product. A parameter called the rate of heuristic flaw (rhf) has been found to correlate positively with the. performance of product against minimax. Both analytical and experimental results are given that appear to support the predictive power of rhf.
Planning, Scheduling, and Uncertainty in the Sequence of Future Events
Venue: arXiv cs.AI 2013
Year: 2013

Scheduling in the factory setting is compounded by computational complexity and temporal uncertainty. Together, these two factors guarantee that the process of constructing an optimal schedule will be costly and the chances of executing that schedule will be slight. Temporal uncertainty in the task execution time can be offset by several methods: eliminate uncertainty by careful engineering, restore certainty whenever it is lost, reduce the uncertainty by using more accurate sensors, and quantify and circumscribe the remaining uncertainty. Unfortunately, these methods focus exclusively on the sources of uncertainty and fail to apply knowledge of the tasks which are to be scheduled. A complete solution must adapt the schedule of activities to be performed according to the evolving state of the production world. The example of vision-directed assembly is presented to illustrate that the principle of least commitment, in the creation of a plan, in the representation of a schedule, and in the execution of a schedule, enables a robot to operate intelligently and efficiently, even in the presence of considerable uncertainty in the sequence of future events.
Knowledge and Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

One purpose -- quite a few thinkers would say the main purpose -- of seeking knowledge about the world is to enhance our ability to make good decisions. An item of knowledge that can make no conceivable difference with regard to anything we might do would strike many as frivolous. Whether or not we want to be philosophical pragmatists in this strong sense with regard to everything we might want to enquire about, it seems a perfectly appropriate attitude to adopt toward artificial knowledge systems. If is granted that we are ultimately concerned with decisions, then some constraints are imposed on our measures of uncertainty at the level of decision making. If our measure of uncertainty is real-valued, then it isn't hard to show that it must satisfy the classical probability axioms. For example, if an act has a real-valued utility U(E) if the event E obtains, and the same real-valued utility if the denial of E obtains, so that U(E) = U(-E), then the expected utility of that act must be U(E), and that must be the same as the uncertainty-weighted average of the returns of the act, p-U(E) + q-U('E), where p and q represent the uncertainty of E and-E respectively. But then we must have p + q = 1.
Approximate Deduction in Single Evidential Bodies
Venue: arXiv cs.AI 2013
Year: 2013

Results on approximate deduction in the context of the calculus of evidence of Dempster-Shafer and the theory of interval probabilities are reported. Approximate conditional knowledge about the truth of conditional propositions was assumed available and expressed as sets of possible values (actually numeric intervals) of conditional probabilities. Under different interpretations of this conditional knowledge, several formulas were produced to integrate unconditioned estimates (assumed given as sets of possible values of unconditioned probabilities) with conditional estimates. These formulas are discussed together with the computational characteristics of the methods derived from them. Of particular importance is one such evidence integration formulation, produced under a belief oriented interpretation, which incorporates both modus ponens and modus tollens inferential mechanisms, allows integration of conditioned and unconditioned knowledge without resorting to iterative or sequential approximations, and produces elementary mass distributions as outputs using similar distributions as inputs.
A General Purpose Inference Engine for Evidential Reasoning Research
Venue: arXiv cs.AI 2013
Year: 2013

The purpose of this paper is to report on the most recent developments in our ongoing investigation of the representation and manipulation of uncertainty in automated reasoning systems. In our earlier studies (Tong and Shapiro, 1985) we described a series of experiments with RUBRIC (Tong et al., 1985), a system for full-text document retrieval, that generated some interesting insights into the effects of choosing among a class of scalar valued uncertainty calculi. [n order to extend these results we have begun a new series of experiments with a larger class of representations and calculi, and to help perform these experiments we have developed a general purpose inference engine.
Experimentally Comparing Uncertain Inference Systems to Probability
Venue: arXiv cs.AI 2013
Year: 2013

This paper examines the biases and performance of several uncertain inference systems: Mycin, a variant of Mycin. and a simplified version of probability using conditional independence assumptions. We present axiomatic arguments for using Minimum Cross Entropy inference as the best way to do uncertain inference. For Mycin and its variant we found special situations where its performance was very good, but also situations where performance was worse than random guessing, or where data was interpreted as having the opposite of its true import We have found that all three of these systems usually gave accurate results, and that the conditional independence assumptions gave the most robust results. We illustrate how the Importance of biases may be quantitatively assessed and ranked. Considerations of robustness might be a critical factor is selecting UlS's for a given application.