OpenRaiser/Intern-Atlas huggingface dataset:
On the data processing theorem in the semi-deterministic setting
Venue: arXiv cs.IT 2013
Year: 2013

Data processing lower bounds on the expected distortion are derived in the finite-alphabet semi-deterministic setting, where the source produces a deterministic, individual sequence, but the channel model is probabilistic, and the decoder is subjected to various kinds of limitations, e.g., decoders implementable by finite-state machines, with or without counters, and with or without a restriction of common reconstruction with high probability. Some of our bounds are given in terms of the Lempel-Ziv complexity of the source sequence or the reproduction sequence. We also demonstrate how some analogous results can be obtained for classes of linear encoders and linear decoders in the continuous alphabet case.
Top-K Product Design Based on Collaborative Tagging Data
Venue: arXiv cs.SI 2013
Year: 2013

The widespread use and popularity of collaborative content sites (e.g., IMDB, Amazon, Yelp, etc.) has created rich resources for users to consult in order to make purchasing decisions on various products such as movies, e-commerce products, restaurants, etc. Products with desirable tags (e.g., modern, reliable, etc.) have higher chances of being selected by prospective customers. This creates an opportunity for product designers to design better products that are likely to attract desirable tags when published. In this paper, we investigate how to mine collaborative tagging data to decide the attribute values of new products and to return the top-k products that are likely to attract the maximum number of desirable tags when published. Given a training set of existing products with their features and user-submitted tags, we first build a Naive Bayes Classifier for each tag. We show that the problem of is NP-complete even if simple Naive Bayes Classifiers are used for tag prediction. We present a suite of algorithms for solving this problem: (a) an exact two tier algorithm(based on top-k querying techniques), which performs much better than the naive brute-force algorithm and works well for moderate problem instances, and (b) a set of approximation algorithms for larger problem instances: a novel polynomial-time approximation algorithm with provable error bound and a practical hill-climbing heuristic. We conduct detailed experiments on synthetic and real data crawled from the web to evaluate the efficiency and quality of our proposed algorithms, as well as show how product designers can benefit by leveraging collaborative tagging information.
Separating OR, SUM, and XOR Circuits
Venue: arXiv cs.CC 2013
Year: 2013

Given a boolean n by n matrix A we consider arithmetic circuits for computing the transformation x->Ax over different semirings. Namely, we study three circuit models: monotone OR-circuits, monotone SUM-circuits (addition of non-negative integers), and non-monotone XOR-circuits (addition modulo 2). Our focus is on \emph{separating} these models in terms of their circuit complexities. We give three results towards this goal: (1) We prove a direct sum type theorem on the monotone complexity of tensor product matrices. As a corollary, we obtain matrices that admit OR-circuits of size O(n), but require SUM-circuits of size Ω(n^{3/2}/\log^2n). (2) We construct so-called \emph{k-uniform} matrices that admit XOR-circuits of size O(n), but require OR-circuits of size Ω(n^2/\log^2n). (3) We consider the task of \emph{rewriting} a given OR-circuit as a XOR-circuit and prove that any subquadratic-time algorithm for this task violates the strong exponential time hypothesis.
Efficient repeat finding via suffix arrays
Venue: arXiv cs.DS 2013
Year: 2013

We solve the problem of finding interspersed maximal repeats using a suffix array construction. As it is well known, all the functionality of suffix trees can be handled by suffix arrays, gaining practicality. Our solution improves the suffix tree based approaches for the repeat finding problem, being particularly well suited for very large inputs. We prove the corrrectness and complexity of the algorithms.
On the Formulation of Performant SPARQL Queries
Venue: arXiv cs.DB 2013
Year: 2013

The combination of the flexibility of RDF and the expressiveness of SPARQL provides a powerful mechanism to model, integrate and query data. However, these properties also mean that it is nontrivial to write performant SPARQL queries. Indeed, it is quite easy to create queries that tax even the most optimised triple stores. Currently, application developers have little concrete guidance on how to write "good" queries. The goal of this paper is to begin to bridge this gap. It describes 5 heuristics that can be applied to create optimised queries. The heuristics are informed by formal results in the literature on the semantics and complexity of evaluating SPARQL queries, which ensures that queries following these rules can be optimised effectively by an underlying RDF store. Moreover, we empirically verify the efficacy of the heuristics using a set of openly available datasets and corresponding SPARQL queries developed by a large pharmacology data integration project. The experimental results show improvements in performance across 6 state-of-the-art RDF stores.
Petition Growth and Success Rates on the UK No. 10 Downing Street Website
Venue: arXiv cs.CY 2013
Year: 2013

Now that so much of collective action takes place online, web-generated data can further understanding of the mechanics of Internet-based mobilisation. This trace data offers social science researchers the potential for new forms of analysis, using real-time transactional data based on entire populations, rather than sample-based surveys of what people think they did or might do. This paper uses a `big data' approach to track the growth of over 8,000 petitions to the UK Government on the No. 10 Downing Street website for two years, analysing the rate of growth per day and testing the hypothesis that the distribution of daily change will be leptokurtic (rather than normal) as previous research on agenda setting would suggest. This hypothesis is confirmed, suggesting that Internet-based mobilisation is characterized by tipping points (or punctuated equilibria) and explaining some of the volatility in online collective action. We find also that most successful petitions grow quickly and that the number of signatures a petition receives on its first day is a significant factor in explaining the overall number of signatures a petition receives during its lifetime. These findings have implications for the strategies of those initiating petitions and the design of web sites with the aim of maximising citizen engagement with policy issues.
Security of Spectrum Learning in Cognitive Radios
Venue: arXiv cs.CR 2013
Year: 2013

Due to delay and energy constraints, a cognitive radio may not be able to perform spectrum sensing in all available channels. Therefore, a sensing policy is needed to decide which channels to sense. The channel selection problem is the problem of designing such a sensing policy to maximize throughput while avoiding interference to primary users. The channel selection problem can be formulated as a reinforcement learning problem. Channel selection schemes that employ reinforcement machine learning algorithms are vulnerable to belief manipulation attacks that contaminate the knowledge base of the learning algorithms. In this paper, we analyze the security of channel selection algorithms that are based on reinforcement learning and propose mitigation techniques that make these algorithms more robust against belief manipulation attacks.
Optimal Feedback Rate Sharing Strategy in Zero-Forcing MIMO Broadcast Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider a multiple-input multiple-output broadcast channel with limited feedback where all users share the feedback rates. Firstly, we find the optimal feedback rate sharing strategy using zero-forcing transmission scheme at the transmitter and random vector quantization at each user. We mathematically prove that equal sharing of sum feedback size among all users is the optimal strategy in the low signal-to-noise ratio (SNR) region, while allocating whole feedback size to a single user is the optimal strategy in the high SNR region. For the mid-SNR region, we propose a simple numerical method to find the optimal feedback rate sharing strategy based on our analysis and show that the equal allocation of sum feedback rate to a partial number of users is the optimal strategy. It is also shown that the proposed simple numerical method can be applicable to finding the optimal feedback rate sharing strategy when different path losses of the users are taken into account. We show that our proposed feedback rate sharing scheme can be extended to the system with stream control and is still useful for the systems with other techniques such as regularized zero-forcing and spherical cap codebook.
A cookbook of translating English to Xapi
Venue: arXiv cs.AI 2013
Year: 2013

The Xapagy cognitive architecture had been designed to perform narrative reasoning: to model and mimic the activities performed by humans when witnessing, reading, recalling, narrating and talking about stories. Xapagy communicates with the outside world using Xapi, a simplified, "pidgin" language which is strongly tied to the internal representation model (instances, scenes and verb instances) and reasoning techniques (shadows and headless shadows). While not fully a semantic equivalent of natural language, Xapi can represent a wide range of complex stories. We illustrate the representation technique used in Xapi through examples taken from folk physics, folk psychology as well as some more unusual literary examples. We argue that while the Xapi model represents a conceptual shift from the English representation, the mapping is logical and consistent, and a trained knowledge engineer can translate between English and Xapi at near-native speed.
Improved Performance of Unsupervised Method by Renovated K-Means
Venue: arXiv cs.LG 2013
Year: 2013

Clustering is a separation of data into groups of similar objects. Every group called cluster consists of objects that are similar to one another and dissimilar to objects of other groups. In this paper, the K-Means algorithm is implemented by three distance functions and to identify the optimal distance function for clustering methods. The proposed K-Means algorithm is compared with K-Means, Static Weighted K-Means (SWK-Means) and Dynamic Weighted K-Means (DWK-Means) algorithm by using Davis Bouldin index, Execution Time and Iteration count methods. Experimental results show that the proposed K-Means algorithm performed better on Iris and Wine dataset when compared with other three clustering methods.
A Cumulative Multi-Niching Genetic Algorithm for Multimodal Function Optimization
Venue: arXiv cs.NE 2013
Year: 2013

This paper presents a cumulative multi-niching genetic algorithm (CMN GA), designed to expedite optimization problems that have computationally-expensive multimodal objective functions. By never discarding individuals from the population, the CMN GA makes use of the information from every objective function evaluation as it explores the design space. A fitness-related population density control over the design space reduces unnecessary objective function evaluations. The algorithm's novel arrangement of genetic operations provides fast and robust convergence to multiple local optima. Benchmark tests alongside three other multi-niching algorithms show that the CMN GA has a greater convergence ability and provides an order-of-magnitude reduction in the number of objective function evaluations required to achieve a given level of convergence.
A local fingerprinting approach for audio copy detection
Venue: arXiv cs.MM 2013
Year: 2013

This study proposes an audio copy detection system that is robust to various attacks. These include the severe pitch shift and tempo change attacks which existing systems fail to detect. First, we propose a novel two dimensional representation for audio signals called the time-chroma image. This image is based on a modification of the concept of chroma in the music literature and is shown to achieve better performance in song identification. Then, we propose a novel fingerprinting algorithm that extracts local fingerprints from the time-chroma image. The proposed local fingerprinting algorithm is invariant to time/frequency scale changes in audio signals. It also outperforms existing methods like SIFT by a great extent. Finally, we introduce a song identification algorithm that uses the proposed fingerprints. The resulting copy detection system is shown to significantly outperform existing methods. Besides being able to detect whether a song (or a part of it) has been copied, the proposed system can accurately estimate the amount of pitch shift and/or tempo change that might have been applied to a song.
New Equations for Neutral Terms: A Sound and Complete Decision Procedure, Formalized
Venue: arXiv cs.PL 2013
Year: 2013

The definitional equality of an intensional type theory is its test of type compatibility. Today's systems rely on ordinary evaluation semantics to compare expressions in types, frustrating users with type errors arising when evaluation fails to identify two `obviously' equal terms. If only the machine could decide a richer theory! We propose a way to decide theories which supplement evaluation with `$ν$-rules', rearranging the neutral parts of normal forms, and report a successful initial experiment. We study a simple -calculus with primitive fold, map and append operations on lists and develop in Agda a sound and complete decision procedure for an equational theory enriched with monoid, functor and fusion laws.
Duality in STRIPS planning
Venue: arXiv cs.AI 2013
Year: 2013

We describe a duality mapping between STRIPS planning tasks. By exchanging the initial and goal conditions, taking their respective complements, and swapping for every action its precondition and delete list, one obtains for every STRIPS task its dual version, which has a solution if and only if the original does. This is proved by showing that the described transformation essentially turns progression (forward search) into regression (backward search) and vice versa. The duality sheds new light on STRIPS planning by allowing a transfer of ideas from one search approach to the other. It can be used to construct new algorithms from old ones, or (equivalently) to obtain new benchmarks from existing ones. Experiments show that the dual versions of IPC benchmarks are in general quite difficult for modern planners. This may be seen as a new challenge. On the other hand, the cases where the dual versions are easier to solve demonstrate that the duality can also be made useful in practice.
Information-Preserving Markov Aggregation
Venue: arXiv cs.IT 2013
Year: 2013

We present a sufficient condition for a non-injective function of a Markov chain to be a second-order Markov chain with the same entropy rate as the original chain. This permits an information-preserving state space reduction by merging states or, equivalently, lossless compression of a Markov source on a sample-by-sample basis. The cardinality of the reduced state space is bounded from below by the node degrees of the transition graph associated with the original Markov chain. We also present an algorithm listing all possible information-preserving state space reductions, for a given transition graph. We illustrate our results by applying the algorithm to a bi-gram letter model of an English text.
On Sink Mobility Trajectory in Clustering Routing Protocols in WSNs
Venue: arXiv cs.NI 2013
Year: 2013

Energy efficient routing protocols are consistently cited as efficient solutions for Wireless Sensor Networks (WSNs) routing. The area of WSNs is one of the emerging and fast growing fields which brought low cost, low power and multi-functional sensor nodes. In this paper, we examine some protocols related to homogeneous and heterogeneous networks. To evaluate the efficiency of different clustering schemes, we compare five clustering routing protocols; Low Energy Adaptive Clustering Hierarchy (LEACH), Threshold Sensitive Energy Efficient Sensor Network (TEEN), Distributed Energy Efficient Clustering (DEEC) and two variants of TEEN which are Clustering and Multi-Hop Protocol in Threshold Sensitive Energy Efficient Sensor Network (CAMPTEEN) and Hierarchical Threshold Sensitive Energy Efficient Sensor Network (H-TEEN). The contribution of this paper is to introduce sink mobility to increase the network life time of hierarchal routing protocols. Two scenarios are discussed to compare the performances of routing protocols; in first scenario static sink is implanted and in later one mobile sink is used. We perform analytical simulations in MATLAB by using different performance metrics such as, number of alive nodes, number of dead nodes and throughput.
A software for aging faces applied to ancient marble busts
Venue: arXiv cs.CV 2013
Year: 2013

The study and development of software able to show the effect of aging of faces is one of the tasks of face recognition technologies. Some software solutions are used for investigations, some others to show the effects of drugs on healthy appearance, however some other applications can be proposed for the analysis of visual arts. Here we use a freely available software, which is providing interesting results, for the comparison of ancient marble busts. An analysis of Augustus busts is proposed.
Analyzing Delay in Wireless Multi-hop Heterogeneous Body Area Networks
Venue: arXiv cs.NI 2013
Year: 2013

With increase in ageing population, health care market keeps growing. There is a need for monitoring of health issues. Wireless Body Area Network (WBAN) consists of wireless sensors attached on or inside human body for monitoring vital health related problems e.g, Electro Cardiogram (ECG), Electro Encephalogram (EEG), ElectronyStagmography (ENG) etc. Due to life threatening situations, timely sending of data is essential. For data to reach health care center, there must be a proper way of sending data through reliable connection and with minimum delay. In this paper transmission delay of different paths, through which data is sent from sensor to health care center over heterogeneous multi-hop wireless channel is analyzed. Data of medical related diseases is sent through three different paths. In all three paths, data from sensors first reaches ZigBee, which is the common link in all three paths. Wireless Local Area Network (WLAN), Worldwide Interoperability for Microwave Access (WiMAX), Universal Mobile Telecommunication System (UMTS) are connected with ZigBee. Each network (WLAN, WiMAX, UMTS) is setup according to environmental conditions, suitability of device and availability of structure for that device. Data from these networks is sent to IP-Cloud, which is further connected to health care center. Delay of data reaching each device is calculated and represented graphically. Main aim of this paper is to calculate delay of each link in each path over multi-hop wireless channel.
Reducing Uncertainty in Navigation and Exploration
Venue: arXiv cs.AI 2013
Year: 2013

A significant problem in designing mobile robot control systems involves coping with the uncertainty that arises in moving about in an unknown or partially unknown environment and relying on noisy or ambiguous sensor data to acquire knowledge about that environment. We describe a control system that chooses what activity to engage in next on the basis of expectations about how the information re- turned as a result of a given activity will improve 2 its knowledge about the spatial layout of its environment. Certain of the higher-level components of the control system are specified in terms of probabilistic decision models whose output is used to mediate the behavior of lower-level control components responsible for movement and sensing.
Occupancy Grids: A Stochastic Spatial Representation for Active Robot Perception
Venue: arXiv cs.RO 2013
Year: 2013

In this paper we provide an overview of a new framework for robot perception, real-world modelling, and navigation that uses a stochastic tesselated representation of spatial information called the Occupancy Grid. The Occupancy Grid is a multi-dimensional random field model that maintains probabilistic estimates of the occupancy state of each cell in a spatial lattice. Bayesian estimation mechanisms employing stochastic sensor models allow incremental updating of the Occupancy Grid using multi-view, multi-sensor data, composition of multiple maps, decision-making, and incorporation of robot and sensor position uncertainty. We present the underlying stochastic formulation of the Occupancy Grid framework, and discuss its application to a variety of robotic tusks. These include range-based mapping, multi-sensor integration, path-planning and obstacle avoidance, handling of robot position uncertainty, incorporation of pre-compiled maps, recovery of geometric representations, and other related problems. The experimental results show that the Occupancy Grid approach generates dense world models, is robust under sensor uncertainty and errors, and allows explicit handling of uncertainty. It supports the development of robust and agile sensor interpretation methods, incremental discovery procedures, and composition of information from multiple sources. Furthermore, the results illustrate that robotic tasks can be addressed through operations performed di- rectly on the Occupancy Grid, and that these operations have strong parallels to operations performed in the image processing domain.
Time, Chance, and Action
Venue: arXiv cs.AI 2013
Year: 2013

To operate intelligently in the world, an agent must reason about its actions. The consequences of an action are a function of both the state of the world and the action itself. Many aspects of the world are inherently stochastic, so a representation for reasoning about actions must be able to express chances of world states as well as indeterminacy in the effects of actions and other events. This paper presents a propositional temporal probability logic for representing and reasoning about actions. The logic can represent the probability that facts hold and events occur at various times. It can represent the probability that actions and other events affect the future. It can represent concurrent actions and conditions that hold or change during execution of an action. The model of probability relates probabilities over time. The logical language integrates both modal and probabilistic constructs and can thus represent and distinguish between possibility, probability, and truth. Several examples illustrating the use of the logic are given.
A Dynamic Approach to Probabilistic Inference
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we present a framework for dynamically constructing Bayesian networks. We introduce the notion of a background knowledge base of schemata, which is a collection of parameterized conditional probability statements. These schemata explicitly separate the general knowledge of properties an individual may have from the specific knowledge of particular individuals that may have these properties. Knowledge of individuals can be combined with this background knowledge to create Bayesian networks, which can then be used in any propagation scheme. We discuss the theory and assumptions necessary for the implementation of dynamic Bayesian networks, and indicate where our approach may be useful.