OpenRaiser/Intern-Atlas huggingface dataset:
Rational Closure in SHIQ
Venue: arXiv cs.AI 2014
Year: 2014

We define a notion of rational closure for the logic SHIQ, which does not enjoys the finite model property, building on the notion of rational closure introduced by Lehmann and Magidor in [23]. We provide a semantic characterization of rational closure in SHIQ in terms of a preferential semantics, based on a finite rank characterization of minimal models. We show that the rational closure of a TBox can be computed in EXPTIME using entailment in SHIQ.
Image Tag Completion by Low-rank Factorization with Dual Reconstruction Structure Preserved
Venue: arXiv cs.CV 2014
Year: 2014

A novel tag completion algorithm is proposed in this paper, which is designed with the following features: 1) Low-rank and error s-parsity: the incomplete initial tagging matrix D is decomposed into the complete tagging matrix A and a sparse error matrix E. However, instead of minimizing its nuclear norm, A is further factor-ized into a basis matrix U and a sparse coefficient matrix V, i.e. D=UV+E. This low-rank formulation encapsulating sparse coding enables our algorithm to recover latent structures from noisy initial data and avoid performing too much denoising; 2) Local reconstruction structure consistency: to steer the completion of D, the local linear reconstruction structures in feature space and tag space are obtained and preserved by U and V respectively. Such a scheme could alleviate the negative effect of distances measured by low-level features and incomplete tags. Thus, we can seek a balance between exploiting as much information and not being mislead to suboptimal performance. Experiments conducted on Corel5k dataset and the newly issued Flickr30Concepts dataset demonstrate the effectiveness and efficiency of the proposed method.
Coherence for Skew-Monoidal Categories
Venue: arXiv cs.LO 2014
Year: 2014

I motivate a variation (due to K. Szlachányi) of monoidal categories called skew-monoidal categories where the unital and associativity laws are not required to be isomorphisms, only natural transformations. Coherence has to be formulated differently than in the well-known monoidal case. In my (to my knowledge new) version, it becomes a statement of uniqueness of normalizing rewrites. I present a proof of this coherence theorem and also formalize it fully in the dependently typed programming language Agda.
Patch-based Hybrid Modelling of Spatially Distributed Systems by Using Stochastic HYPE - ZebraNet as an Example
Venue: arXiv cs.PF 2014
Year: 2014

Individual-based hybrid modelling of spatially distributed systems is usually expensive. Here, we consider a hybrid system in which mobile agents spread over the space and interact with each other when in close proximity. An individual-based model for this system needs to capture the spatial attributes of every agent and monitor the interaction between each pair of them. As a result, the cost of simulating this model grows exponentially as the number of agents increases. For this reason, a patch-based model with more abstraction but better scalability is advantageous. In a patch-based model, instead of representing each agent separately, we model the agents in a patch as an aggregation. This property significantly enhances the scalability of the model. In this paper, we convert an individual-based model for a spatially distributed network system for wild-life monitoring, ZebraNet, to a patch-based stochastic HYPE model with accurate performance evaluation. We show the ease and expressiveness of stochastic HYPE for patch-based modelling of hybrid systems. Moreover, a mean-field analytical model is proposed as the fluid flow approximation of the stochastic HYPE model, which can be used to investigate the average behaviour of the modelled system over an infinite number of simulation runs of the stochastic HYPE model.
Optimizing Budget Allocation in Graphs
Venue: arXiv cs.DS 2014
Year: 2014

In the classical facility location problem we consider a graph $G$ with fixed weights on the edges of $G$. The goal is then to find an optimal positioning for a set of facilities on the graph with respect to some objective function. We introduce a new framework for facility location problems, where the weights on the graph edges are not fixed, but rather should be assigned. The goal is to find a valid assignment for which the resulting weighted graph optimizes the facility location objective function. We present algorithms for finding the optimal {\em budget allocation} for the center point problem and for the median point problem on trees. Our algorithms run in linear time, both for the case where a candidate vertex is given as part of the input, and for the case where finding a vertex that optimizes the solution is part of the problem. We also present a hardness result for the general graph case of the center point problem, followed by an $O(\log^2(n))$ approximation algorithm on graphs - with general metric spaces.
Logic Programming and Logarithmic Space
Venue: arXiv cs.LO 2014
Year: 2014

We present an algebraic view on logic programming, related to proof theory and more specifically linear logic and geometry of interaction. Within this construction, a characterization of logspace (deterministic and non-deterministic) computation is given via a synctactic restriction, using an encoding of words that derives from proof theory. We show that the acceptance of a word by an observation (the counterpart of a program in the encoding) can be decided within logarithmic space, by reducing this problem to the acyclicity of a graph. We show moreover that observations are as expressive as two-ways multi-heads finite automata, a kind of pointer machines that is a standard model of logarithmic space computation.
Automatic Test Data Generation and Model Checking with CHR
Venue: arXiv cs.SE 2014
Year: 2014

We present an example for application of Constraint Handling Rules to automated test data generation and model checking in verification of mission critical software for satellite control.
Synthetic Data and Artificial Neural Networks for Natural Scene Text Recognition
Venue: arXiv cs.CV 2014
Year: 2014

In this work we present a framework for the recognition of natural scene text. Our framework does not require any human-labelled data, and performs word recognition on the whole image holistically, departing from the character based recognition systems of the past. The deep neural network models at the centre of this framework are trained solely on data produced by a synthetic text generation engine -- synthetic data that is highly realistic and sufficient to replace real data, giving us infinite amounts of training data. This excess of data exposes new possibilities for word recognition models, and here we consider three models, each one "reading" words in a different way: via 90k-way dictionary encoding, character sequence encoding, and bag-of-N-grams encoding. In the scenarios of language based and completely unconstrained text recognition we greatly improve upon state-of-the-art performance on standard datasets, using our fast, simple machinery and requiring zero data-acquisition costs.
A Hybrid Latent Variable Neural Network Model for Item Recommendation
Venue: arXiv cs.LG 2014
Year: 2014

Collaborative filtering is used to recommend items to a user without requiring a knowledge of the item itself and tends to outperform other techniques. However, collaborative filtering suffers from the cold-start problem, which occurs when an item has not yet been rated or a user has not rated any items. Incorporating additional information, such as item or user descriptions, into collaborative filtering can address the cold-start problem. In this paper, we present a neural network model with latent input variables (latent neural network or LNN) as a hybrid collaborative filtering technique that addresses the cold-start problem. LNN outperforms a broad selection of content-based filters (which make recommendations based on item descriptions) and other hybrid approaches while maintaining the accuracy of state-of-the-art collaborative filtering techniques.
A Fast, Minimal Memory, Consistent Hash Algorithm
Venue: arXiv cs.DS 2014
Year: 2014

We present jump consistent hash, a fast, minimal memory, consistent hash algorithm that can be expressed in about 5 lines of code. In comparison to the algorithm of Karger et al., jump consistent hash requires no storage, is faster, and does a better job of evenly dividing the key space among the buckets and of evenly dividing the workload when the number of buckets changes. Its main limitation is that the buckets must be numbered sequentially, which makes it more suitable for data storage applications than for distributed web caching.
Sampling the suffix array with minimizers
Venue: arXiv cs.DS 2014
Year: 2014

Sampling (evenly) the suffixes from the suffix array is an old idea trading the pattern search time for reduced index space. A few years ago Claude et al. showed an alphabet sampling scheme allowing for more efficient pattern searches compared to the sparse suffix array, for long enough patterns. A drawback of their approach is the requirement that sought patterns need to contain at least one character from the chosen subalphabet. In this work we propose an alternative suffix sampling approach with only a minimum pattern length as a requirement, which seems more convenient in practice. Experiments show that our algorithm achieves competitive time-space tradeoffs on most standard benchmark data.
Inferring the geographic focus of online documents from social media sharing patterns
Venue: arXiv cs.SI 2014
Year: 2014

Determining the geographic focus of digital media is an essential first step for modern geographic information retrieval. However, publicly-visible location annotations are remarkably sparse in online data. In this work, we demonstrate a method which infers the geographic focus of an online document by examining the locations of Twitter users who share links to the document. We apply our geotagging technique to multiple datasets built from different content: manually-annotated news articles, GDELT, YouTube, Flickr, Twitter, and Tumblr.
ExpertBayes: Automatically refining manually built Bayesian networks
Venue: arXiv cs.AI 2014
Year: 2014

Bayesian network structures are usually built using only the data and starting from an empty network or from a naive Bayes structure. Very often, in some domains, like medicine, a prior structure knowledge is already known. This structure can be automatically or manually refined in search for better performance models. In this work, we take Bayesian networks built by specialists and show that minor perturbations to this original network can yield better classifiers with a very small computational cost, while maintaining most of the intended meaning of the original model.
Leveraging Personalization To Facilitate Privacy
Venue: arXiv cs.SI 2014
Year: 2014

Online social networks have enabled new methods and modalities of collaboration and sharing. These advances bring privacy concerns: online social data is more accessible and persistent and simultaneously less contextualized than traditional social interactions. To allay these concerns, many web services allow users to configure their privacy settings based on a set of multiple-choice questions. We suggest a new paradigm for privacy options. Instead of suggesting the same defaults to each user, services can leverage knowledge of users' traits to recommend a machine-learned prediction of their privacy preferences for Facebook. As a case study, we build and evaluate MyPrivacy, a publicly available web application that suggests personalized privacy settings. An evaluation with 199 users shows that users find the suggestions to be appropriate and private; furthermore, they express intent to implement the recommendations made by MyPrivacy. This supports the proposal to put personalization to work in online communities to promote privacy and security.
Controlled Natural Language Generation from a Multilingual FrameNet-based Grammar
Venue: arXiv cs.CL 2014
Year: 2014

This paper presents a currently bilingual but potentially multilingual FrameNet-based grammar library implemented in Grammatical Framework. The contribution of this paper is two-fold. First, it offers a methodological approach to automatically generate the grammar based on semantico-syntactic valence patterns extracted from FrameNet-annotated corpora. Second, it provides a proof of concept for two use cases illustrating how the acquired multilingual grammar can be exploited in different CNL applications in the domains of arts and tourism.
Why do linear SVMs trained on HOG features perform so well?
Venue: arXiv cs.CV 2014
Year: 2014

Linear Support Vector Machines trained on HOG features are now a de facto standard across many visual perception tasks. Their popularisation can largely be attributed to the step-change in performance they brought to pedestrian detection, and their subsequent successes in deformable parts models. This paper explores the interactions that make the HOG-SVM symbiosis perform so well. By connecting the feature extraction and learning processes rather than treating them as disparate plugins, we show that HOG features can be viewed as doing two things: (i) inducing capacity in, and (ii) adding prior to a linear SVM trained on pixels. From this perspective, preserving second-order statistics and locality of interactions are key to good performance. We demonstrate surprising accuracy on expression recognition and pedestrian detection tasks, by assuming only the importance of preserving such local second-order interactions.
Optimization of Free Space Optical Wireless Network for Cellular Backhauling
Venue: arXiv cs.NI 2014
Year: 2014

With densification of nodes in cellular networks, free space optic (FSO) connections are becoming an appealing low cost and high rate alternative to copper and fiber as the backhaul solution for wireless communication systems. To ensure a reliable cellular backhaul, provisions for redundant, disjoint paths between the nodes must be made in the design phase. This paper aims at finding a cost-effective solution to upgrade the cellular backhaul with pre-deployed optical fibers using FSO links and mirror components. Since the quality of the FSO links depends on several factors, such as transmission distance, power, and weather conditions, we adopt an elaborate formulation to calculate link reliability. We present a novel integer linear programming model to approach optimal FSO backhaul design, guaranteeing $K$-disjoint paths connecting each node pair. Next, we derive a column generation method to a path-oriented mathematical formulation. Applying the method in a sequential manner enables high computational scalability. We use realistic scenarios to demonstrate our approaches efficiently provide optimal or near-optimal solutions, and thereby allow for accurately dealing with the trade-off between cost and reliability.
Load Hiding of Household's Power Demand
Venue: arXiv cs.OH 2014
Year: 2014

With the development and introduction of smart metering, the energy information for costumers will change from infrequent manual meter readings to fine-grained energy consumption data. On the one hand these fine-grained measurements will lead to an improvement in costumers' energy habits, but on the other hand the fined-grained data produces information about a household and also households' inhabitants, which are the basis for many future privacy issues. To ensure household privacy and smart meter information owned by the household inhabitants, load hiding techniques were introduced to obfuscate the load demand visible at the household energy meter. In this work, a state-of-the-art battery-based load hiding (BLH) technique, which uses a controllable battery to disguise the power consumption and a novel load hiding technique called load-based load hiding (LLH) are presented. An LLH system uses an controllable household appliance to obfuscate the household's power demand. We evaluate and compare both load hiding techniques on real household data and show that both techniques can strengthen household privacy but only LLH can increase appliance level privacy.
Learning with Cross-Kernels and Ideal PCA
Venue: arXiv cs.LG 2014
Year: 2014

We describe how cross-kernel matrices, that is, kernel matrices between the data and a custom chosen set of `feature spanning points' can be used for learning. The main potential of cross-kernels lies in the fact that (a) only one side of the matrix scales with the number of data points, and (b) cross-kernels, as opposed to the usual kernel matrices, can be used to certify for the data manifold. Our theoretical framework, which is based on a duality involving the feature space and vanishing ideals, indicates that cross-kernels have the potential to be used for any kind of kernel learning. We present a novel algorithm, Ideal PCA (IPCA), which cross-kernelizes PCA. We demonstrate on real and synthetic data that IPCA allows to (a) obtain PCA-like features faster and (b) to extract novel and empirically validated features certifying for the data manifold.
A New Result on the Random Residue Sequence Algorithm
Venue: arXiv cs.CR 2014
Year: 2014

Random residue sequences (RR) may be used in many random number applications including those related to multiple access in communications. This paper investigates variations on an algorithm to generate RR sequences that was proposed earlier by the author. This makes it possible to obtain many more random sequences than was possible to do by the previous algorithm. Experimental results are presented on a variety of sequences of length 16 and 24. To obtain a variety of RR sequences of a specific length can have obvious applications in cryptography.
Low-cost Augmented Reality prototype for controlling network devices
Venue: arXiv cs.HC 2014
Year: 2014

With the evolution of mobile devices, and smart-phones in particular, comes the ability to create new experiences that enhance the way we see, interact, and manipulate objects, within the world that surrounds us. It is now possible to blend data from our senses and our devices in numerous ways that simply were not possible before using Augmented Reality technology. In a near future, when all of the office devices as well as your personal electronic gadgets are on a common wireless network, operating them using a universal remote controller would be possible. This paper presents an off-the-shelf, low-cost prototype that leverages the Augmented Reality technology to deliver a novel and interactive way of operating office network devices around using a mobile device. We believe this type of system may provide benefits to controlling multiple integrated devices and visualizing interconnectivity or utilizing visual elements to pass information from one device to another, or may be especially beneficial to control devices when interacting with them physically may be difficult or pose danger or harm.
Distributed Resource Allocation for Relay-Aided Device-to-Device Communication: A Message Passing Approach
Venue: arXiv cs.NI 2014
Year: 2014

Device-to-device (D2D) communication underlaying cellular wireless networks is a promising concept to improve user experience and resource utilization by allowing direct transmission between two cellular devices. In this paper, performance of network-assisted D2D communication is investigated where D2D traffic is carried through relay nodes. Considering a multi-user and multi-relay network, we propose a distributed solution for resource allocation with a view to maximizing network sum-rate. An optimization problem is formulated for radio resource allocation at the relays. The objective is to maximize end-to-end rate as well as satisfy the data rate requirements for cellular and D2D user equipments under total power constraint. Due to intractability of the resource allocation problem, we propose a solution approach using message passing technique where each user equipment sends and receives information messages to/from the relay node in an iterative manner with the goal of achieving an optimal allocation. Therefore, the computational effort is distributed among all the user equipments and the corresponding relay node. The convergence and optimality of the proposed scheme are proved and a possible distributed implementation of the scheme in practical LTE-Advanced networks is outlined. The numerical results show that there is a distance threshold beyond which relay-aided D2D communication significantly improves network performance with a small increase in end-to-end delay when compared to direct communication between D2D peers.
Optimal Gaussian Filter for Effective Noise Filtering
Venue: arXiv cs.OH 2014
Year: 2014

In this paper we show that the knowledge of noise statistics contaminating a signal can be effectively used to choose an optimal Gaussian filter to eliminate noise. Very specifically, we show that the additive white Gaussian noise (AWGN) contaminating a signal can be filtered best by using a Gaussian filter of specific characteristics. The design of the Gaussian filter bears relationship with the noise statistics and also some basic information about the signal. We first derive a relationship between the properties of the Gaussian filter, noise statistics and the signal and later show through experiments that this relationship can be used effectively to identify the optimal Gaussian filter that can effectively filter noise.
Analog input layer for optical reservoir computers
Venue: arXiv cs.ET 2014
Year: 2014

Reservoir computing is an information processing technique, derived from the theory of neural networks, which is easy to implement in hardware. Several reservoir computer hardware implementations have been realized recently with performance comparable to digital implementations, which demonstrated the potential of reservoir computing for ultrahigh bandwidth signal processing tasks. In all these implementations however the signal pre-processing necessary to efficiently address the reservoir was performed digitally. Here we show how this digital pre-processing can be replaced by an analog input layer. We study both numerically and experimentally to what extent the pre-processing can be replaced by a modulation of the input signal by either a single sine-wave or by a sum of two sine functions, since harmonic oscillations are particularly easy to generate in hardware. We find that the modulation by a single sine gives performance worse than state of the art. On the other hand, on many -but not all- tasks, the modulation by two sines gives performances comparable to the state of the art. The present work thus represents an important step towards fully autonomous, ultrahigh bandwidth analog reservoir computers.
An Evolutionary Approach to Coalition Formation
Venue: arXiv cs.GT 2014
Year: 2014

In Cooperative Games with Externalities when the members of a set S \subset N of agents wish to deviate they need to calculate their worth. This worth depends on what the non-members (outsiders) N \setminus S will do, which in turn depends on which coalition structure the outsiders will form. Since this coalition formation problem is NP-hard, various approaches have been adopted. In this paper using an evolutionary game theoretic approach we provide a set of equations that can help agents in S reason about the coalition structures the outsiders may form in terms of minimum distances on an n-s dimensional space, where n=|N|, s=|S|.