OpenRaiser/Intern-Atlas huggingface dataset:
Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
Venue: arXiv cs.LG 2014
Year: 2014

We extend the work of Narasimhan and Bilmes [30] for minimizing set functions representable as a dierence between submodular functions. Similar to [30], our new algorithms are guaranteed to monotonically reduce the objective function at every step. We empirically and theoretically show that the per-iteration cost of our algorithms is much less than [30], and our algorithms can be used to efficiently minimize a dierence between submodular functions under various combinatorial constraints, a problem not previously addressed. We provide computational bounds and a hardness result on the multiplicative inapproximability of minimizing the dierence between submodular functions. We show, however, that it is possible to give worst-case additive bounds by providing a polynomial time computable lower-bound on the minima. Finally we show how a number of machine learning problems can be modeled as minimizing the dierence between submodular functions. We experimentally show the validity of our algorithms by testing them on the problem of feature selection with submodular cost features.
Predicting the behavior of interacting humans by fusing data from multiple sources
Venue: arXiv cs.AI 2014
Year: 2014

Multi-fidelity methods combine inexpensive low-fidelity simulations with costly but highfidelity simulations to produce an accurate model of a system of interest at minimal cost. They have proven useful in modeling physical systems and have been applied to engineering problems such as wing-design optimization. During human-in-the-loop experimentation, it has become increasingly common to use online platforms, like Mechanical Turk, to run low-fidelity experiments to gather human performance data in an efficient manner. One concern with these experiments is that the results obtained from the online environment generalize poorly to the actual domain of interest. To address this limitation, we extend traditional multi-fidelity approaches to allow us to combine fewer data points from high-fidelity human-in-the-loop experiments with plentiful but less accurate data from low-fidelity experiments to produce accurate models of how humans interact. We present both model-based and model-free methods, and summarize the predictive performance of each method under dierent conditions.
Warped Mixtures for Nonparametric Cluster Shapes
Venue: arXiv cs.LG 2014
Year: 2014

A mixture of Gaussians fit to a single curved or heavy-tailed cluster will report that the data contains many clusters. To produce more appropriate clusterings, we introduce a model which warps a latent mixture of Gaussians to produce nonparametric cluster shapes. The possibly low-dimensional latent mixture model allows us to summarize the properties of the high-dimensional clusters (or density manifolds) describing the data. The number of manifolds, as well as the shape and dimension of each manifold is automatically inferred. We derive a simple inference scheme for this model which analytically integrates out both the mixture parameters and the warping function. We show that our model is effective for density estimation, performs better than infinite Gaussian mixture models at recovering the true number of clusters, and produces interpretable summaries of high-dimensional datasets.
Probabilistic inverse reinforcement learning in unknown environments
Venue: arXiv cs.LG 2014
Year: 2014

We consider the problem of learning by demonstration from agents acting in unknown stochastic Markov environments or games. Our aim is to estimate agent preferences in order to construct improved policies for the same task that the agents are trying to solve. To do so, we extend previous probabilistic approaches for inverse reinforcement learning in known MDPs to the case of unknown dynamics or opponents. We do this by deriving two simplified probabilistic models of the demonstrator's policy and utility. For tractability, we use maximum a posteriori estimation rather than full Bayesian inference. Under a flat prior, this results in a convex optimisation problem. We find that the resulting algorithms are highly competitive against a variety of other methods for inverse reinforcement learning that do have knowledge of the dynamics.
On the BDD/FC Conjecture
Venue: arXiv cs.DB 2014
Year: 2014

Bounded Derivation Depth property (BDD) and Finite Controllability (FC) are two properties of sets of datalog rules and tuple generating dependencies (known as Datalog +/- programs), which recently attracted some attention. We conjecture that the first of these properties implies the second, and support this conjecture by some evidence proving, among other results, that it holds true for all theories over binary signature.
Exponentiated Gradient Exploration for Active Learning
Venue: arXiv cs.LG 2014
Year: 2014

Active learning strategies respond to the costly labelling task in a supervised classification by selecting the most useful unlabelled examples in training a predictive model. Many conventional active learning algorithms focus on refining the decision boundary, rather than exploring new regions that can be more informative. In this setting, we propose a sequential algorithm named EG-Active that can improve any Active learning algorithm by an optimal random exploration. Experimental results show a statistically significant and appreciable improvement in the performance of our new approach over the existing active feedback methods.
Hadoop in Low-Power Processors
Venue: arXiv cs.DC 2014
Year: 2014

In our previous work we introduced a so-called Amdahl blade microserver that combines a low-power Atom processor, with a GPU and an SSD to provide a balanced and energy-efficient system. Our preliminary results suggested that the sequential I/O of Amdahl blades can be ten times higher than that a cluster of conventional servers with comparable power consumption. In this paper we investigate the performance and energy efficiency of Amdahl blades running Hadoop. Our results show that Amdahl blades are 7.7 times and 3.4 times as energy-efficient as the Open Cloud Consortium cluster for a data-intensive and a compute-intensive application, respectively. The Hadoop Distributed Filesystem has relatively poor performance on Amdahl blades because both disk and network I/O are CPU-heavy operations on Atom processors. We demonstrate three effective techniques to reduce CPU consumption and improve performance. However, even with these improvements, the Atom processor is still the system's bottleneck. We revisit Amdahl's law, and estimate that Amdahl blades need four Atom cores to be well balanced for Hadoop tasks.
Sensors for healthcare: Would you want them in your home?
Venue: arXiv cs.HC 2014
Year: 2014

This paper describes some of the challenges set within SPHERE, a large-scale Interdisciplinary Research Collaboration that aims to develop sensor systems to monitor people's health and wellbeing in the home. In particular we discuss the dual task facing the User- Centered Design research group, to ensure the development of inclusive and desirable domestic healthcare technology. On the one hand, we seek to gain a rich understanding of the many envisaged users of the SPHERE system. On the other hand, for the user experience requirements to be translated into tangible outputs, it is crucial that we effectively communicate these findings to the broader team of SPHERE engineers and computer scientists.
Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
Venue: arXiv cs.DM 2014
Year: 2014

A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that outputs a certificate, along with its answer (be it positive or negative), where the certificate can be used to easily justify the given answer. While the recognition of circular-arc graphs has been known to be polynomial since the 1980s, no polynomial-time certifying recognition algorithm is known to date, despite such algorithms being found for many subclasses of circular-arc graphs. This is largely due to the fact that a forbidden structure characterization of circular-arc graphs is not known, even though the problem has been intensely studied since the seminal work of Klee in the 1960s. In this contribution, we settle this problem. We present the first forbidden structure characterization of circular-arc graphs. Our obstruction has the form of mutually avoiding walks in the graph. It naturally extends a similar obstruction that characterizes interval graphs. As a consequence, we give the first polynomial-time certifying algorithm for the recognition of circular-arc graphs.
Supporting SPARQL Update Queries in RDF-XML Integration
Venue: arXiv cs.DB 2014
Year: 2014

The Web of Data encourages organizations and companies to publish their data according to the Linked Data practices and offer SPARQL endpoints. On the other hand, the dominant standard for information exchange is XML. The SPARQL2XQuery Framework focuses on the automatic translation of SPARQL queries in XQuery expressions in order to access XML data across the Web. In this paper, we outline our ongoing work on supporting update queries in the RDF-XML integration scenario.
Cluster based RBF Kernel for Support Vector Machines
Venue: arXiv cs.LG 2014
Year: 2014

In the classical Gaussian SVM classification we use the feature space projection transforming points to normal distributions with fixed covariance matrices (identity in the standard RBF and the covariance of the whole dataset in Mahalanobis RBF). In this paper we add additional information to Gaussian SVM by considering local geometry-dependent feature space projection. We emphasize that our approach is in fact an algorithm for a construction of the new Gaussian-type kernel. We show that better (compared to standard RBF and Mahalanobis RBF) classification results are obtained in the simple case when the space is preliminary divided by k-means into two sets and points are represented as normal distributions with a covariances calculated according to the dataset partitioning. We call the constructed method C$_k$RBF, where $k$ stands for the amount of clusters used in k-means. We show empirically on nine datasets from UCI repository that C$_2$RBF increases the stability of the grid search (measured as the probability of finding good parameters).
Efficient Data Compression with Error Bound Guarantee in Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

We present a data compression and dimensionality reduction scheme for data fusion and aggregation applications to prevent data congestion and reduce energy consumption at network connecting points such as cluster heads and gateways. Our in-network approach can be easily tuned to analyze the data temporal or spatial correlation using an unsupervised neural network scheme, namely the autoencoders. In particular, our algorithm extracts intrinsic data features from previously collected historical samples to transform the raw data into a low dimensional representation. Moreover, the proposed framework provides an error bound guarantee mechanism. We evaluate the proposed solution using real-world data sets and compare it with traditional methods for temporal and spatial data compression. The experimental validation reveals that our approach outperforms several existing wireless sensor network's data compression methods in terms of compression efficiency and signal reconstruction.
A Lightweight Approach for Improving the Lookup Performance in Kademlia-type Systems
Venue: arXiv cs.NI 2014
Year: 2014

Discovery of nodes and content in large-scale distributed systems is generally based on Kademlia, today. Understanding Kademlia-type systems to improve their performance is essential for maintaining a high service quality for an increased number of participants, particularly when those systems are adopted by latency-sensitive applications. This paper contributes to the understanding of Kademlia by studying the impact of \emph{diversifying} neighbours' identifiers within each routing table bucket on the lookup performance. We propose a new, yet backward-compatible, neighbour selection scheme that attempts to maximize the aforementioned diversity. The scheme does not cause additional overhead except negligible computations for comparing the diversity of identifiers. We present a theoretical model for the actual impact of the new scheme on the lookup's hop count and validate it against simulations of three exemplary Kademlia-type systems. We also measure the performance gain enabled by a partial deployment for the scheme in the real KAD system. The results confirm the superiority of the systems that incorporate our scheme.
Cutting Last Wires for Mobile Communications by Microwave Power Transfer
Venue: arXiv cs.IT 2014
Year: 2014

The advancements in microwave power transfer (MPT) over past decades have enabled wireless power transfer over long distances. The latest breakthroughs in wireless communication, namely massive MIMO, small cells and millimeter-wave communication, make wireless networks suitable platforms for implementing MPT. This can lead to the elimination of the "last wires" connecting mobile devices to the grid for recharging, thereby tackling a long-standing ICT grand challenge. Furthermore, the seamless integration between MPT and wireless communication opens a new area called wirelessly powered communications (WPC) where many new research directions arise e.g., simultaneous information-and-power transfer, WPC network architectures, and techniques for safe and efficient WPC. This article provides an introduction to WPC by describing the key features of WPC, shedding light on a set of frequently asked questions, and identifying the key design issues and discussing possible solutions.
Distributed Power Splitting for SWIPT in Relay Interference Channels using Game Theory
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider simultaneous wireless information and power transfer (SWIPT) in relay interference channels, where multiple source-destination pairs communicate through their dedicated energy harvesting relays. Each relay needs to split its received signal from sources into two streams: one for information forwarding and the other for energy harvesting. We develop a distributed power splitting framework using game theory to derive a profile of power splitting ratios for all relays that can achieve a good network-wide performance. Specifically, non-cooperative games are respectively formulated for pure amplify-and-forward (AF) and decode-and-forward (DF) networks, in which each link is modeled as a strategic player who aims to maximize its own achievable rate. The existence and uniqueness for the Nash equilibriums (NEs) of the formulated games are analyzed and a distributed algorithm with provable convergence to achieve the NEs is also developed. Subsequently, the developed framework is extended to the more general network setting with mixed AF and DF relays. All the theoretical analyses are validated by extensive numerical results. Simulation results show that the proposed game-theoretical approach can achieve a near-optimal network-wide performance on average, especially for the scenarios with relatively low and moderate interference.
Cortical Processing with Thermodynamic-RAM
Venue: arXiv cs.NE 2014
Year: 2014

AHaH computing forms a theoretical framework from which a biologically-inspired type of computing architecture can be built where, unlike von Neumann systems, memory and processor are physically combined. In this paper we report on an incremental step beyond the theoretical framework of AHaH computing toward the development of a memristor-based physical neural processing unit (NPU), which we call Thermodynamic-RAM (kT-RAM). While the power consumption and speed dominance of such an NPU over von Neumann architectures for machine learning applications is well appreciated, Thermodynamic-RAM offers several advantages over other hardware approaches to adaptation and learning. Benefits include general-purpose use, a simple yet flexible instruction set and easy integration into existing digital platforms. We present a high level design of kT-RAM and a formal definition of its instruction set. We report the completion of a kT-RAM emulator and the successful port of all previous machine learning benchmark applications including unsupervised clustering, supervised and unsupervised classification, complex signal prediction, unsupervised robotic actuation and combinatorial optimization. Lastly, we extend a previous MNIST hand written digits benchmark application, to show that an extra step of reading the synaptic states of AHaH nodes during the train phase (healing) alone results in plasticity that improves the classifier's performance, bumping our best F1 score up to 99.5%.
Gradient Distribution Priors for Biomedical Image Processing
Venue: arXiv cs.CV 2014
Year: 2014

Ill-posed inverse problems are commonplace in biomedical image processing. Their solution typically requires imposing prior knowledge about the latent ground truth. While this regularizes the problem to an extent where it can be solved, it also biases the result toward the expected. With inappropriate priors harming more than they use, it remains unclear what prior to use for a given practical problem. Priors are hence mostly chosen in an {\em ad hoc} or empirical fashion. We argue here that the gradient distribution of natural-scene images may provide a versatile and well-founded prior for biomedical images. We provide motivation for this choice from different points of view, and we fully validate the resulting prior for use on biomedical images by showing its stability and correlation with image quality. We then provide a set of simple parametric models for the resulting prior, leading to straightforward (quasi-)convex optimization problems for which we provide efficient solver algorithms. We illustrate the use of the present models and solvers in a variety of common image-processing tasks, including contrast enhancement, noise level estimation, denoising, blind deconvolution, zooming/up-sampling, and dehazing. In all cases we show that the present method leads to results that are comparable to or better than the state of the art; always using the same, simple prior. We conclude by discussing the limitations and possible interpretations of the prior.
Snapshot for Time: The One-Shot Case
Venue: arXiv cs.DC 2014
Year: 2014

We show that for one-shot problems - problems where a processor executes a single operation-execution - timing constraints can be captured by conditions on the relation between original outputs and supplementary snapshots. In addition to the dictionary definition of the word snapshot, in distributed computing snapshots also stand for a task that imposes relation among sets which are output of processors. Hence, constrains relating the timing between operation-executions of processors can be captured by the sets relation representing a task. This allows to bring to bear techniques developed for tasks, to one-shot objects. In particular, for the one-shot case the question of linearizability is moot. Nevertheless, current proof techniques of object implementation require the prover to provide linearization-points even in the one shot case. Transforming the object into a task relieves the prover of an implementation from the burden of finding the "linearization-points," since if the task is solvable, linearization points are guaranteed to exist. We exhibit this advantage with a new algorithm to implement MWMR register in a SWMR system.
On the Role of Identity in Surveillance
Venue: arXiv cs.CY 2014
Year: 2014

Surveillance is a process that observes behaviour, recognises properties and identifies individuals. It has become a commonplace phenomenon in our everyday life. Many surveillance practices depend on the use of advanced technologies to collect, store and process data. We propose (i) an abstract definition of surveillance; and (ii) an abstract definition of identity, designed to capture the common structure of many disparate surveillance situations. We argue that the notion of identity is fundamental to surveillance. Rather than having a single identity, individuals have many identities, real and virtual, that are used in different aspects of their lives. Most aspects of life are subject to some form of surveillance, and observations and identities can be aggregated. The notion of identity needs to be theorised. Our analysis is very general and, at the same time, sufficiently precise to be the basis of mathematical models.
A Note on the Bellare-Rivest Protocol for Translucent Cryptography
Venue: arXiv cs.CR 2014
Year: 2014

We remark that the Bellare-Rivest protocol for translucent cryptography [J. Cryptology (1999) 12: 117-139] can not truly enable the government to decrypt partial encrypted communications.
When MIMO Control Meets MIMO Communication: A Majorization Condition for Networked Stabilizability
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, we initiate the study of networked stabilization via a MIMO communication scheme between the controller and the plant. Specifically, the communication system is modeled as a MIMO transceiver, which consists of three parts: an encoder, a MIMO channel, and a decoder. In the spirit of MIMO communication, the number of SISO subchannels in the transceiver is often greater than the number of data streams to be transmitted. Moreover, the subchannel capacities are assumed to be fixed a priori. In this case, the encoder/decoder pair gives an additional design freedom on top of the controller, leading to a stabilization problem via coding/control co-design. It turns out that how to take the best advantage of the coding mechanism is quite crucial. From a demand/supply perspective, the design of the coding mechanism boils down to reshaping the demands for communication resource from different control inputs to match the given supplies. We study the problem for the case of AWGN subchannels and fading subchannels, respectively. In both cases, we arrive at a unified necessary and sufficient condition on the capacities of the subchannels under which the coding/control co-design problem is solvable. The condition is given in terms of a majorization type relation. As we go along, systematic procedures are also put forward to implement the coding/control co-design. A numerical example is presented to illustrate our results.
An Effective Black Hole Attack Detection Mechanism using Permutation Based Acknowledgement in MANET
Venue: arXiv cs.NI 2014
Year: 2014

With the evolution of wireless technology and use of mobile devices, Mobile Ad-hoc Network has become popular among researchers to explore. A mobile ad-hoc network (MANET) is a self-configuring network of mobile routers (and associated hosts) connected by wireless links. The routers and hosts are free to move randomly and organize themselves arbitrarily. It allows mobile nodes to communicate directly without any centralized coordinator. Such network scenarios cannot rely on centralized and organized connectivity, and can be conceived as applications of Mobile Ad-Hoc Networks. Thus, MANET is vulnerable due to its dynamic network topology, as any node become untrusted at any time. The Black hole attack is one kind of security risk in which malicious node advertises itself to have a shortest path for any destination, to forge data or for DOS attack. In this paper, to detect such nodes effectively, we propose a Permutation based Acknowledgement for most widely used reactive protocol ad-hoc on demand distance vector routing AODV. This mechanism is enhancement of Adaptive Acknowledgement (AACK) and TWO-ACK, here we have tried to show the efficiency increment by decreasing number of messages routed in the network.