OpenRaiser/Intern-Atlas huggingface dataset:
Entropy and Graph Based Modelling of Document Coherence using Discourse Entities: An Application
Venue: arXiv cs.IR 2015
Year: 2015

We present two novel models of document coherence and their application to information retrieval (IR). Both models approximate document coherence using discourse entities, e.g. the subject or object of a sentence. Our first model views text as a Markov process generating sequences of discourse entities (entity n-grams); we use the entropy of these entity n-grams to approximate the rate at which new information appears in text, reasoning that as more new words appear, the topic increasingly drifts and text coherence decreases. Our second model extends the work of Guinaudeau & Strube [28] that represents text as a graph of discourse entities, linked by different relations, such as their distance or adjacency in text. We use several graph topology metrics to approximate different aspects of the discourse flow that can indicate coherence, such as the average clustering or betweenness of discourse entities in text. Experiments with several instantiations of these models show that: (i) our models perform on a par with two other well-known models of text coherence even without any parameter tuning, and (ii) reranking retrieval results according to their coherence scores gives notable performance gains, confirming a relation between document coherence and relevance. This work contributes two novel models of document coherence, the application of which to IR complements recent work in the integration of document cohesiveness or comprehensibility to ranking [5, 56].
Exploring Privacy Preservation in Outsourced K-Nearest Neighbors with Multiple Data Owners
Venue: arXiv cs.CR 2015
Year: 2015

The k-nearest neighbors (k-NN) algorithm is a popular and effective classification algorithm. Due to its large storage and computational requirements, it is suitable for cloud outsourcing. However, k-NN is often run on sensitive data such as medical records, user images, or personal information. It is important to protect the privacy of data in an outsourced k-NN system. Prior works have all assumed the data owners (who submit data to the outsourced k-NN system) are a single trusted party. However, we observe that in many practical scenarios, there may be multiple mutually distrusting data owners. In this work, we present the first framing and exploration of privacy preservation in an outsourced k-NN system with multiple data owners. We consider the various threat models introduced by this modification. We discover that under a particularly practical threat model that covers numerous scenarios, there exists a set of adaptive attacks that breach the data privacy of any exact k-NN system. The vulnerability is a result of the mathematical properties of k-NN and its output. Thus, we propose a privacy-preserving alternative system supporting kernel density estimation using a Gaussian kernel, a classification algorithm from the same family as k-NN. In many applications, this similar algorithm serves as a good substitute for k-NN. We additionally investigate solutions for other threat models, often through extensions on prior single data owner systems.
Distributed Mini-Batch SDCA
Venue: arXiv cs.LG 2015
Year: 2015

We present an improved analysis of mini-batched stochastic dual coordinate ascent for regularized empirical loss minimization (i.e. SVM and SVM-type objectives). Our analysis allows for flexible sampling schemes, including where data is distribute across machines, and combines a dependence on the smoothness of the loss and/or the data spread (measured through the spectral norm).
Action recognition in still images by latent superpixel classification
Venue: arXiv cs.CV 2015
Year: 2015

Action recognition from still images is an important task of computer vision applications such as image annotation, robotic navigation, video surveillance and several others. Existing approaches mainly rely on either bag-of-feature representations or articulated body-part models. However, the relationship between the action and the image segments is still substantially unexplored. For this reason, in this paper we propose to approach action recognition by leveraging an intermediate layer of "superpixels" whose latent classes can act as attributes of the action. In the proposed approach, the action class is predicted by a structural model(learnt by Latent Structural SVM) based on measurements from the image superpixels and their latent classes. Experimental results over the challenging Stanford 40 Actions dataset report a significant average accuracy of 74.06% for the positive class and 88.50% for the negative class, giving evidence to the performance of the proposed approach.
Reconstruction of Graph Signals through Percolation from Seeding Nodes
Venue: arXiv cs.SI 2015
Year: 2015

New schemes to recover signals defined in the nodes of a graph are proposed. Our focus is on reconstructing bandlimited graph signals, which are signals that admit a sparse representation in a frequency domain related to the structure of the graph. Most existing formulations focus on estimating an unknown graph signal by observing its value on a subset of nodes. By contrast, in this paper, we study the problem of reconstructing a known graph signal using as input a graph signal that is non-zero only for a small subset of nodes (seeding nodes). The sparse signal is then percolated (interpolated) across the graph using a graph filter. Graph filters are a generalization of classical time-invariant systems and represent linear transformations that can be implemented distributedly across the nodes of the graph. Three setups are investigated. In the first one, a single simultaneous injection takes place on several nodes in the graph. In the second one, successive value injections take place on a single node. The third one is a generalization where multiple nodes inject multiple signal values. For noiseless settings, conditions under which perfect reconstruction is feasible are given, and the corresponding schemes to recover the desired signal are specified. Scenarios leading to imperfect reconstruction, either due to insufficient or noisy signal value injections, are also analyzed. Moreover, connections with classical interpolation in the time domain are discussed. The last part of the paper presents numerical experiments that illustrate the results developed through synthetic graph signals and two real-world signal reconstruction problems: influencing opinions in a social network and inducing a desired brain state in humans.
VMF-SNE: Embedding for Spherical Data
Venue: arXiv cs.LG 2015
Year: 2015

T-SNE is a well-known approach to embedding high-dimensional data and has been widely used in data visualization. The basic assumption of t-SNE is that the data are non-constrained in the Euclidean space and the local proximity can be modelled by Gaussian distributions. This assumption does not hold for a wide range of data types in practical applications, for instance spherical data for which the local proximity is better modelled by the von Mises-Fisher (vMF) distribution instead of the Gaussian. This paper presents a vMF-SNE embedding algorithm to embed spherical data. An iterative process is derived to produce an efficient embedding. The results on a simulation data set demonstrated that vMF-SNE produces better embeddings than t-SNE for spherical data.
Defensive Resource Allocation in Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

In this work, we are interested on the analysis of competing marketing campaigns between an incumbent who dominates the market and a challenger who wants to enter the market. We are interested in (a) the simultaneous decision of how many resources to allocate to their potential customers to advertise their products for both marketing campaigns, and (b) the optimal allocation on the situation in which the incumbent knows the entrance of the challenger and thus can predict its response. Applying results from game theory, we characterize these optimal strategic resource allocations for the voter model of social networks.
A Model for Foraging Ants, Controlled by Spiking Neural Networks and Double Pheromones
Venue: arXiv cs.NE 2015
Year: 2015

A model of an Ant System where ants are controlled by a spiking neural circuit and a second order pheromone mechanism in a foraging task is presented. A neural circuit is trained for individual ants and subsequently the ants are exposed to a virtual environment where a swarm of ants performed a resource foraging task. The model comprises an associative and unsupervised learning strategy for the neural circuit of the ant. The neural circuit adapts to the environment by means of classical conditioning. The initially unknown environment includes different types of stimuli representing food and obstacles which, when they come in direct contact with the ant, elicit a reflex response in the motor neural system of the ant: moving towards or away from the source of the stimulus. The ants are released on a landscape with multiple food sources where one ant alone would have difficulty harvesting the landscape to maximum efficiency. The introduction of a double pheromone mechanism yields better results than traditional ant colony optimization strategies. Traditional ant systems include mainly a positive reinforcement pheromone. This approach uses a second pheromone that acts as a marker for forbidden paths (negative feedback). This blockade is not permanent and is controlled by the evaporation rate of the pheromones. The combined action of both pheromones acts as a collective stigmergic memory of the swarm, which reduces the search space of the problem. This paper explores how the adaptation and learning abilities observed in biologically inspired cognitive architectures is synergistically enhanced by swarm optimization strategies. The model portraits two forms of artificial intelligent behaviour: at the individual level the spiking neural network is the main controller and at the collective level the pheromone distribution is a map towards the solution emerged by the colony.
Investigating SRAM PUFs in large CPUs and GPUs
Venue: arXiv cs.CR 2015
Year: 2015

Physically unclonable functions (PUFs) provide data that can be used for cryptographic purposes: on the one hand randomness for the initialization of random-number generators; on the other hand individual fingerprints for unique identification of specific hardware components. However, today's off-the-shelf personal computers advertise randomness and individual fingerprints only in the form of additional or dedicated hardware. This paper introduces a new set of tools to investigate whether intrinsic PUFs can be found in PC components that are not advertised as containing PUFs. In particular, this paper investigates AMD64 CPU registers as potential PUF sources in the operating-system kernel, the bootloader, and the system BIOS; investigates the CPU cache in the early boot stages; and investigates shared memory on Nvidia GPUs. This investigation found non-random non-fingerprinting behavior in several components but revealed usable PUFs in Nvidia GPUs.
Importing SMT and Connection proofs as expansion trees
Venue: arXiv cs.LO 2015
Year: 2015

Different automated theorem provers reason in various deductive systems and, thus, produce proof objects which are in general not compatible. To understand and analyze these objects, one needs to study the corresponding proof theory, and then study the language used to represent proofs, on a prover by prover basis. In this work we present an implementation that takes SMT and Connection proof objects from two different provers and imports them both as expansion trees. By representing the proofs in the same framework, all the algorithms and tools available for expansion trees (compression, visualization, sequent calculus proof construction, proof checking, etc.) can be employed uniformly. The expansion proofs can also be used as a validation tool for the proof objects produced.
Mixing HOL and Coq in Dedukti (Extended Abstract)
Venue: arXiv cs.LO 2015
Year: 2015

We use Dedukti as a logical framework for interoperability. We use automated tools to translate different developments made in HOL and in Coq to Dedukti, and we combine them to prove new results. We illustrate our approach with a concrete example where we instantiate a sorting algorithm written in Coq with the natural numbers of HOL.
Almost Instantaneous Fix-to-Variable Length Codes
Venue: arXiv cs.IT 2015
Year: 2015

We propose almost instantaneous fixed-to-variable-length (AIFV) codes such that two (resp. $K-1$) code trees are used if code symbols are binary (resp. $K$-ary for $K \geq 3$), and source symbols are assigned to incomplete internal nodes in addition to leaves. Although the AIFV codes are not instantaneous codes, they are devised such that the decoding delay is at most two bits (resp. one code symbol) in the case of binary (resp. $K$-ary) code alphabet. The AIFV code can attain better average compression rate than the Huffman code at the expenses of a little decoding delay and a little large memory size to store multiple code trees. We also show for the binary and ternary AIFV codes that the optimal AIFV code can be obtained by solving 0-1 integer programming problems.
Auditable Versioned Data Storage Outsourcing
Venue: arXiv cs.CR 2015
Year: 2015

Auditability is crucial for data outsourcing, facilitating accountability and identifying data loss or corruption incidents in a timely manner, reducing in turn the risks from such losses. In recent years, in synch with the growing trend of outsourcing, a lot of progress has been made in designing probabilistic (for efficiency) provable data possession (PDP) schemes. However, even the recent and advanced PDP solutions that do deal with dynamic data, do so in a limited manner, and for only the latest version of the data. A naive solution treating different versions in isolation would work, but leads to tremendous overheads, and is undesirable. In this paper, we present algorithms to achieve full persistence (all intermediate configurations are preserved and are modifiable) for an optimized skip list (known as FlexList) so that versioned data can be audited. The proposed scheme provides deduplication at the level of logical, variable sized blocks, such that only the altered parts of the different versions are kept, while the persistent data-structure facilitates access (read) of any arbitrary version with the same storage and process efficiency that state-of-the-art dynamic PDP solutions provide for only the current version, while commit (write) operations incur around 5% additional time. Furthermore, the time overhead for auditing arbitrary versions in addition to the latest version is imperceptible even on a low-end server...
SnowWatch: Snow Monitoring through Acquisition and Analysis of User-Generated Content
Venue: arXiv cs.CV 2015
Year: 2015

We present a system for complementing snow phenomena monitoring with virtual measurements extracted from public visual content. The proposed system integrates an automatic acquisition and analysis of photographs and webcam images depicting Alpine mountains. In particular, the technical demonstration consists in a web portal that interfaces the whole system with the population. It acts as an entertaining photo-sharing social web site, acquiring at the same time visual content necessary for environmental monitoring.
A Minimal Architecture for General Cognition
Venue: arXiv cs.AI 2015
Year: 2015

A minimalistic cognitive architecture called MANIC is presented. The MANIC architecture requires only three function approximating models, and one state machine. Even with so few major components, it is theoretically sufficient to achieve functional equivalence with all other cognitive architectures, and can be practically trained. Instead of seeking to transfer architectural inspiration from biology into artificial intelligence, MANIC seeks to minimize novelty and follow the most well-established constructs that have evolved within various sub-fields of data science. From this perspective, MANIC offers an alternate approach to a long-standing objective of artificial intelligence. This paper provides a theoretical analysis of the MANIC architecture.
Asymptotic Orthogonality Analysis of Time-Domain Sparse Massive MIMO Channels
Venue: arXiv cs.IT 2015
Year: 2015

The theoretical analysis of downlink massive MIMO usually assumes the ideal Gaussian channel matrix with asymp- totic orthogonality of channel vectors associated with different users, since it can provide the favorable propagation condition. Meanwhile, recent experiments have shown that massive MIMO channels between a certain user and massive base station antennas appear the spatial common sparsity (SCS) in both the time domain and angle domain. This motivates us to investigate whether realistic sparse massive MIMO channels could provide the favorable propagation condition, and reveal the capacity gap between massive MIMO systems over realistic sparse channels and that under the ideal Gaussian channel matrix assumption. This paper theoretically proves that channel vectors associated with different users in massive MIMO over realistic sparse channels satisfy the asymptotic orthogonality, which indicates that the favorable propagation condition can also be provided. Moreover, the simulation results confirm the theoretical analysis.
Understanding the Timed Distributed Trace of a Partially Synchronous System at Runtime
Venue: arXiv cs.DC 2015
Year: 2015

It has gained broad attention to understand the timed distributed trace of a cyber-physical system at runtime, which is often achieved by verifying properties over the observed trace of system execution. However, this verification is facing severe challenges. First, in realistic settings, the computing entities only have imperfectly synchronized clocks. A proper timing model is essential to the interpretation of the trace of system execution. Second, the specification should be able to express properties with real-time constraints despite the asynchrony, and the semantics should be interpreted over the currently-observed and continuously-growing trace. To address these challenges, we propose PARO - the partially synchronous system observation framework, which i) adopts the partially synchronous model of time, and introduces the lattice and the timed automata theories to model the trace of system execution; ii) adopts a tailored subset of TCTL to specify temporal properties, and defines the 3-valued semantics to interpret the properties over the currently-observed finite trace; iii) constructs the timed automaton corresponding to the trace at runtime, and reduces the satisfaction of the 3-valued semantics over finite traces to that of the classical boolean semantics over infinite traces. PARO is implemented over MIPA - the open-source middleware we developed. Performance measurements show the cost-effectiveness of PARO in different settings of key environmental factors.
Separated by an Un-common Language: Towards Judgment Language Informed Vector Space Modeling
Venue: arXiv cs.CL 2015
Year: 2015

A common evaluation practice in the vector space models (VSMs) literature is to measure the models' ability to predict human judgments about lexical semantic relations between word pairs. Most existing evaluation sets, however, consist of scores collected for English word pairs only, ignoring the potential impact of the judgment language in which word pairs are presented on the human scores. In this paper we translate two prominent evaluation sets, wordsim353 (association) and SimLex999 (similarity), from English to Italian, German and Russian and collect scores for each dataset from crowdworkers fluent in its language. Our analysis reveals that human judgments are strongly impacted by the judgment language. Moreover, we show that the predictions of monolingual VSMs do not necessarily best correlate with human judgments made with the language used for model training, suggesting that models and humans are affected differently by the language they use when making semantic judgments. Finally, we show that in a large number of setups, multilingual VSM combination results in improved correlations with human judgments, suggesting that multilingualism may partially compensate for the judgment language effect on human judgments.
Extending SROIQ with Constraint Networks and Grounded Circumscription
Venue: arXiv cs.LO 2015
Year: 2015

Developments in semantic web technologies have promoted ontological encoding of knowledge from diverse domains. However, modelling many practical domains requires more expressiveness than what the standard description logics (most prominently SROIQ) support. In this paper, we extend the expressive DL SROIQ with constraint networks (resulting in the logic SROIQc) and grounded circumscription (resulting in the logic GC-SROIQ). Applications of constraint modelling include embedding ontologies with temporal or spatial information, while those of grounded circumscription include defeasible inference and closed world reasoning. We describe the syntax and semantics of the logic formed by including constraint modelling constructs in SROIQ, and provide a sound, complete and terminating tableau algorithm for it. We further provide an intuitive algorithm for Grounded Circumscription in SROIQc, which adheres to the general framework of grounded circumscription, and which can be applied to a whole range of expressive logics for which no such specific algorithm presently exists.
Capacity and Rate Regions of A Class of Broadcast Interference Channels
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, a class of broadcast interference channels (BIC) is investigated, where one of the two broadcast receivers is subject to interference coming from a point-to-point transmission. For a general discrete memoryless broadcast interference channel (DM-BIC), an achievable scheme based on message splitting, superposition and binning is proposed and a concise representation of the corresponding achievable rate region R is obtained. Two partial-order broadcast conditions interference-oblivious less noisy and interference-cognizant less noisy are defined, thereby extending the usual less noisy condition for a regular broadcast channel by taking interference into account. Under these conditions, a reduced form of R is shown to be equivalent to a rate region based on a simpler scheme, where the broadcast transmitter uses only superposition. Furthermore, if interference is strong for the interference-oblivious less noisy DM-BIC, the capacity region is given by the aforementioned two equivalent rate regions. For a Gaussian broadcast interference channel (GBIC), channel parameters are categorized into three regimes. For the first two regimes, which are closely related to the two partial-order broadcast conditions, achievable rate regions are derived by specializing the corresponding achievable schemes of DM-BICs with Gaussian input distributions. The entropy power inequality (EPI) based outer bounds are obtained by combining bounding techniques for a Gaussian broadcast channel (GBC) and a Gaussian interference channel (GIC). These inner and outer bounds lead to either exact or approximate characterizations of capacity regions and sum capacity under various conditions. For the remaining complementing regime, inner and outer bounds are also provided.