OpenRaiser/Intern-Atlas huggingface dataset:
Qualitative Decision Theory with Sugeno Integrals
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents an axiomatic framework for qualitative decision under uncertainty in a finite setting. The corresponding utility is expressed by a sup-min expression, called Sugeno (or fuzzy) integral. Technically speaking, Sugeno integral is a median, which is indeed a qualitative counterpart to the averaging operation underlying expected utility. The axiomatic justification of Sugeno integral-based utility is expressed in terms of preference between acts as in Savage decision theory. Pessimistic and optimistic qualitative utilities, based on necessity and possibility measures, previously introduced by two of the authors, can be retrieved in this setting by adding appropriate axioms.
Learning the Structure of Dynamic Probabilistic Networks
Venue: arXiv cs.AI 2013
Year: 2013

Dynamic probabilistic networks are a compact representation of complex stochastic processes. In this paper we examine how to learn the structure of a DPN from data. We extend structure scoring rules for standard probabilistic networks to the dynamic case, and show how to search for structure when some of the variables are hidden. Finally, we examine two applications where such a technology might be useful: predicting and classifying dynamic behaviors, and learning causal orderings in biological processes. We provide empirical results that demonstrate the applicability of our methods in both domains.
Solving POMDPs by Searching in Policy Space
Venue: arXiv cs.AI 2013
Year: 2013

Most algorithms for solving POMDPs iteratively improve a value function that implicitly represents a policy and are said to search in value function space. This paper presents an approach to solving POMDPs that represents a policy explicitly as a finite-state controller and iteratively improves the controller by search in policy space. Two related algorithms illustrate this approach. The first is a policy iteration algorithm that can outperform value iteration in solving infinitehorizon POMDPs. It provides the foundation for a new heuristic search algorithm that promises further speedup by focusing computational effort on regions of the problem space that are reachable, or likely to be reached, from a start state.
Magic Inference Rules for Probabilistic Deduction under Taxonomic Knowledge
Venue: arXiv cs.AI 2013
Year: 2013

We present locally complete inference rules for probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events. Crucially, in contrast to similar inference rules in the literature, our inference rules are locally complete for conjunctive events and under additional taxonomic knowledge. We discover that our inference rules are extremely complex and that it is at first glance not clear at all where the deduced tightest bounds come from. Moreover, analyzing the global completeness of our inference rules, we find examples of globally very incomplete probabilistic deductions. More generally, we even show that all systems of inference rules for taxonomic and probabilistic knowledge-bases over conjunctive events are globally incomplete. We conclude that probabilistic deduction by the iterative application of inference rules on interval restrictions for conditional probabilities, even though considered very promising in the literature so far, seems very limited in its field of application.
Constructing Situation Specific Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

This paper describes a process for constructing situation-specific belief networks from a knowledge base of network fragments. A situation-specific network is a minimal query complete network constructed from a knowledge base in response to a query for the probability distribution on a set of target variables given evidence and context variables. We present definitions of query completeness and situation-specific networks. We describe conditions on the knowledge base that guarantee query completeness. The relationship of our work to earlier work on KBMC is also discussed.
Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams)
Venue: arXiv cs.AI 2013
Year: 2013

One of the benefits of belief networks and influence diagrams is that so much knowledge is captured in the graphical structure. In particular, statements of conditional irrelevance (or independence) can be verified in time linear in the size of the graph. To resolve a particular inference query or decision problem, only some of the possible states and probability distributions must be specified, the "requisite information." This paper presents a new, simple, and efficient "Bayes-ball" algorithm which is well-suited to both new students of belief networks and state of the art implementations. The Bayes-ball algorithm determines irrelevant sets and requisite information more efficiently than existing methods, and is linear in the size of the graph for belief networks and influence diagrams.
Probabilistic Inference in Influence Diagrams
Venue: arXiv cs.AI 2013
Year: 2013

This paper is about reducing influence diagram (ID) evaluation into Bayesian network (BN) inference problems. Such reduction is interesting because it enables one to readily use one's favorite BN inference algorithm to efficiently evaluate IDs. Two such reduction methods have been proposed previously (Cooper 1988, Shachter and Peot 1992). This paper proposes a new method. The BN inference problems induced by the mew method are much easier to solve than those induced by the two previous methods.
Variable-Length Coding with Feedback: Finite-Length Codewords and Periodic Decoding
Venue: arXiv cs.IT 2013
Year: 2013

Theoretical analysis has long indicated that feedback improves the error exponent but not the capacity of single-user memoryless channels. Recently Polyanskiy et al. studied the benefit of variable-length feedback with termination (VLFT) codes in the non-asymptotic regime. In that work, achievability is based on an infinite length random code and decoding is attempted at every symbol. The coding rate backoff from capacity due to channel dispersion is greatly reduced with feedback, allowing capacity to be approached with surprisingly small expected latency. This paper is mainly concerned with VLFT codes based on finite-length codes and decoding attempts only at certain specified decoding times. The penalties of using a finite block-length $N$ and a sequence of specified decoding times are studied. This paper shows that properly scaling $N$ with the expected latency can achieve the same performance up to constant terms as with $N = \infty$. The penalty introduced by periodic decoding times is a linear term of the interval between decoding times and hence the performance approaches capacity as the expected latency grows if the interval between decoding times grows sub-linearly with the expected latency.
A Verified Approach for Checking Real-Time Specification Patterns
Venue: arXiv cs.LO 2013
Year: 2013

We propose a verified approach to the formal verification of timed properties using model-checking techniques. We focus on properties expressed using real-time specification patterns, which can be viewed as a subset of timed temporal logics that includes properties commonly found during the analysis of reactive systems. Our model-checking approach is based on the use of observers in order to transform the verification of timed patterns into the verification of simpler LTL formulas. While the use of observers for model-checking is quite common, our contribution is original in several ways. First, we define a formal framework to verify that our observers are correct and non-intrusive. Second, we define different classes of observers for each pattern and use a pragmatic approach in order to select the most efficient candidate in practice. This approach is implemented in an integrated verification tool chain for the Fiacre language.
Real-Time Specification Patterns and Tools
Venue: arXiv cs.SE 2013
Year: 2013

An issue limiting the adoption of model checking technologies by the industry is the ability, for non-experts, to express their requirements using the property languages supported by verification tools. This has motivated the definition of dedicated assertion languages for expressing temporal properties at a higher level. However, only a limited number of these formalisms support the definition of timing constraints. In this paper, we propose a set of specification patterns that can be used to express real-time requirements commonly found in the design of reactive systems. We also provide an integrated model checking tool chain for the verification of timed requirements on TTS, an extension of Timed Petri Nets with data variables and priorities.
Rank regularization and Bayesian inference for tensor completion and extrapolation
Venue: arXiv cs.IT 2013
Year: 2013

A novel regularizer of the PARAFAC decomposition factors capturing the tensor's rank is proposed in this paper, as the key enabler for completion of three-way data arrays with missing entries. Set in a Bayesian framework, the tensor completion method incorporates prior information to enhance its smoothing and prediction capabilities. This probabilistic approach can naturally accommodate general models for the data distribution, lending itself to various fitting criteria that yield optimum estimates in the maximum-a-posteriori sense. In particular, two algorithms are devised for Gaussian- and Poisson-distributed data, that minimize the rank-regularized least-squares error and Kullback-Leibler divergence, respectively. The proposed technique is able to recover the "ground-truth'' tensor rank when tested on synthetic data, and to complete brain imaging and yeast gene expression datasets with 50% and 15% of missing entries respectively, resulting in recovery errors at -10dB and -15dB.
Multi-scale Discriminant Saliency with Wavelet-based Hidden Markov Tree Modelling
Venue: arXiv cs.CV 2013
Year: 2013

The bottom-up saliency, an early stage of humans' visual attention, can be considered as a binary classification problem between centre and surround classes. Discriminant power of features for the classification is measured as mutual information between distributions of image features and corresponding classes . As the estimated discrepancy very much depends on considered scale level, multi-scale structure and discriminant power are integrated by employing discrete wavelet features and Hidden Markov Tree (HMT). With wavelet coefficients and Hidden Markov Tree parameters, quad-tree like label structures are constructed and utilized in maximum a posterior probability (MAP) of hidden class variables at corresponding dyadic sub-squares. Then, a saliency value for each square block at each scale level is computed with discriminant power principle. Finally, across multiple scales is integrated the final saliency map by an information maximization rule. Both standard quantitative tools such as NSS, LCC, AUC and qualitative assessments are used for evaluating the proposed multi-scale discriminant saliency (MDIS) method against the well-know information based approach AIM on its released image collection with eye-tracking data. Simulation results are presented and analysed to verify the validity of MDIS as well as point out its limitation for further research direction.
Efficient Support for Mode-Directed Tabling in the YapTab Tabling System
Venue: arXiv cs.PL 2013
Year: 2013

Mode-directed tabling is an extension to the tabling technique that supports the definition of mode operators for specifying how answers are inserted into the table space. In this paper, we focus our discussion on the efficient support for mode directed-tabling in the YapTab tabling system. We discuss 7 different mode operators and explain how we have extended and optimized YapTab's table space organization to support them. Initial experimental results show that our implementation compares favorably with the B-Prolog and XSB state-of-the-art Prolog tabling systems.
On Comparing Alternative Splitting Strategies for Or-Parallel Prolog Execution on Multicores
Venue: arXiv cs.PL 2013
Year: 2013

Many or-parallel Prolog models exploiting implicit parallelism have been proposed in the past. Arguably, one of the most successful models is environment copying for shared memory architectures. With the increasing availability and popularity of multicore architectures, it makes sense to recover the body of knowledge there is in this area and re-engineer prior computational models to evaluate their performance on newer architectures. In this work, we focus on the implementation of splitting strategies for or-parallel Prolog execution on multicores and, for that, we develop a framework, on top of the YapOr system, that integrates and supports five alternative splitting strategies. Our implementation shares the underlying execution environment and most of the data structures used to implement or-parallelism in YapOr. In particular, we took advantage of YapOr's infrastructure for incremental copying and scheduling support, which we used with minimal modifications. We thus argue that all these common support features allow us to make a first and fair comparison between these five alternative splitting strategies and, therefore, better understand their advantages and weaknesses.
Optimal Locally Repairable Codes and Connections to Matroid Theory
Venue: arXiv cs.IT 2013
Year: 2013

Petabyte-scale distributed storage systems are currently transitioning to erasure codes to achieve higher storage efficiency. Classical codes like Reed-Solomon are highly sub-optimal for distributed environments due to their high overhead in single-failure events. Locally Repairable Codes (LRCs) form a new family of codes that are repair efficient. In particular, LRCs minimize the number of nodes participating in single node repairs during which they generate small network traffic. Two large-scale distributed storage systems have already implemented different types of LRCs: Windows Azure Storage and the Hadoop Distributed File System RAID used by Facebook. The fundamental bounds for LRCs, namely the best possible distance for a given code locality, were recently discovered, but few explicit constructions exist. In this work, we present an explicit and optimal LRCs that are simple to construct. Our construction is based on grouping Reed-Solomon (RS) coded symbols to obtain RS coded symbols over a larger finite field. We then partition these RS symbols in small groups, and re-encode them using a simple local code that offers low repair locality. For the analysis of the optimality of the code, we derive a new result on the matroid represented by the code generator matrix.
The Complexity of Robot Games on the Integer Line
Venue: arXiv cs.LO 2013
Year: 2013

In robot games on Z, two players add integers to a counter. Each player has a finite set from which he picks the integer to add, and the objective of the first player is to let the counter reach 0. We present an exponential-time algorithm for deciding the winner of a robot game given the initial counter value, and prove a matching lower bound.
A Survey on Array Storage, Query Languages, and Systems
Venue: arXiv cs.DB 2013
Year: 2013

Since scientific investigation is one of the most important providers of massive amounts of ordered data, there is a renewed interest in array data processing in the context of Big Data. To the best of our knowledge, a unified resource that summarizes and analyzes array processing research over its long existence is currently missing. In this survey, we provide a guide for past, present, and future research in array processing. The survey is organized along three main topics. Array storage discusses all the aspects related to array partitioning into chunks. The identification of a reduced set of array operators to form the foundation for an array query language is analyzed across multiple such proposals. Lastly, we survey real systems for array processing. The result is a thorough survey on array data storage and processing that should be consulted by anyone interested in this research topic, independent of experience level. The survey is not complete though. We greatly appreciate pointers towards any work we might have forgotten to mention.
Informational Divergence Approximations to Product Distributions
Venue: arXiv cs.IT 2013
Year: 2013

The minimum rate needed to accurately approximate a product distribution based on an unnormalized informational divergence is shown to be a mutual information. This result subsumes results of Wyner on common information and Han-Verdú on resolvability. The result also extends to cases where the source distribution is unknown but the entropy is known.
A Study of Influential Factors in the Adoption and Diffusion of B2C E-Commerce
Venue: arXiv cs.CY 2013
Year: 2013

This paper looks at the present standing of ecommerce in Saudi Arabia, as well as the challenges and strengths of Business to Customers (B2C) electronic commerce. Many studies have been conducted around the world in order to gain a better understanding of the demands, needs and effectiveness of online commerce. A study was undertaken to review the literature identifying the factors influencing the adoption and diffusion of B2C e-commerce. It found four distinct categories: businesses, customers, environmental and governmental support, which must all be considered when creating an e-commerce infrastructure. A concept matrix was used to provide a comparison of important factors in different parts of the world. The study found that e-commerce in Saudi Arabia was lacking in Governmental support as well as relevant involvement by both customers and retailers.
Graph Layouts via Layered Separators
Venue: arXiv cs.CG 2013
Year: 2013

A k-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets such that no two edges that are in the same set are nested with respect to the vertex ordering. A k-track layout of a graph consists of a vertex k-colouring, and a total order of each vertex colour class, such that between each pair of colour classes no two edges cross. The queue-number (track-number) of a graph G, is the minimum k such that G has a k-queue (k-track) layout. This paper proves that every n-vertex planar graph has track number and queue number at most O(log n). This improves the result of Di Battista, Frati and Pach [Foundations of Computer Science, (FOCS '10), pp. 365--374] who proved the first sub-polynomial bounds on the queue number and track number of planar graphs. Specifically, they obtained O(log^2 n) queue number and O(log^8 n) track number bounds for planar graphs. The result also implies that every planar graph has a 3D crossing-free grid drawing in O(n log n) volume. The proof uses a non-standard type of graph separators.
On the dynamic compressibility of sets
Venue: arXiv cs.CC 2013
Year: 2013

We define a new notion of compressibility of a set of numbers through the dynamics of a polynomial function. We provide approaches to solve the problem by reducing it to the multi-criteria traveling salesman problem through a series of transformations. We then establish computational complexity results by giving some NP-completeness proofs. We also discuss about a notion of $ε$ K-compressibility of a set, with regard to lossy compression and deduce the necessary condition for the given set to be $ε$ K-compressible. Finally, we conclude by providing a list of open problems solutions to which could extend the applicability the our technique.
Phishing Dynamic Evolving Neural Fuzzy Framework for Online Detection Zero-day Phishing Email
Venue: arXiv cs.CR 2013
Year: 2013

Phishing is a kind of attack in which criminals use spoofed emails and fraudulent web sites to trick financial organization and customers. Criminals try to lure online users by convincing them to reveal the username, passwords, credit card number and updating account information or fill billing information.
ThermInfo: Collecting, Retrieving, and Estimating Reliable Thermochemical Data
Venue: arXiv cs.CE 2013
Year: 2013

Standard enthalpies of formation are used for assessing the efficiency and safety of chemical processes in the chemical industry. However, the number of compounds for which the enthalpies of formation are available is many orders of magnitude smaller than the number of known compounds. Thermochemical data prediction methods are therefore clearly needed. Several commercial and free chemical databases are currently available, the NIST WebBook being the most used free source. To overcome this problem a cheminformatics system was designed and built with two main objectives in mind: collecting and retrieving critically evaluated thermochemical values, and estimating new data. In its present version, by using cheminformatics techniques, ThermInfo allows the retrieval of the value of a thermochemical property, such as a gas-phase standard enthalpy of formation, by inputting, for example, the molecular structure or the name of a compound. The same inputs can also be used to estimate data (presently restricted to non-polycyclic hydrocarbons) by using the Extended Laidler Bond Additivity (ELBA) method. The information system is publicly available at http://www.therminfo.com or http://therminfo.lasige.di.fc.ul.pt. ThermInfo's strength lies in the data quality, availability (free access), search capabilities, and, in particular, prediction ability, based on a user-friendly interface that accepts inputs in several formats.
Benchmarking community detection methods on social media data
Venue: arXiv cs.SI 2013
Year: 2013

Benchmarking the performance of community detection methods on empirical social network data has been identified as critical for improving these methods. In particular, while most current research focuses on detecting communities in data that has been digitally extracted from large social media and telecommunications services, most evaluation of this research is based on small, hand-curated datasets. We argue that these two types of networks differ so significantly that by evaluating algorithms solely on the former, we know little about how well they perform on the latter. To address this problem, we consider the difficulties that arise in constructing benchmarks based on digitally extracted network data, and propose a task-based strategy which we feel addresses these difficulties. To demonstrate that our scheme is effective, we use it to carry out a substantial benchmark based on Facebook data. The benchmark reveals that some of the most popular algorithms fail to detect fine-grained community structure.
Internal models for nonlinear output agreement and optimal flow control
Venue: arXiv cs.SY 2013
Year: 2013

This paper studies the problem of output agreement in networks of nonlinear dynamical systems under time-varying disturbances. Necessary and sufficient conditions for output agreement are derived for the class of incrementally passive systems. Following this, it is shown that the optimal distribution problem in dynamic inventory systems with time-varying supply and demand can be cast as a special version of the output agreement problem. We show in particular that the time-varying optimal distribution problem can be solved by applying an internal model controller to the dual variables of a certain convex network optimization problem.
Beyond Markov Chains, Towards Adaptive Memristor Network-based Music Generation
Venue: arXiv cs.ET 2013
Year: 2013

We undertook a study of the use of a memristor network for music generation, making use of the memristor's memory to go beyond the Markov hypothesis. Seed transition matrices are created and populated using memristor equations, and which are shown to generate musical melodies and change in style over time as a result of feedback into the transition matrix. The spiking properties of simple memristor networks are demonstrated and discussed with reference to applications of music making. The limitations of simulating composing memristor networks in von Neumann hardware is discussed and a hardware solution based on physical memristor properties is presented.