OpenRaiser/Intern-Atlas huggingface dataset:
Simplicial Complex Entropy
Venue: arXiv cs.IT 2016
Year: 2016

We propose an entropy function for simplicial complices. Its value gives the expected cost of the optimal encoding of sequences of vertices of the complex, when any two vertices belonging to the same simplex are indistinguishable. We show that the proposed entropy function can be computed efficiently. By computing the entropy of several complices consisting of hundreds of simplices, we show that the proposed entropy function can be used in the analysis of the large sequences of simplicial complices that often appear in computational topology applications.
Debugging Machine Learning Tasks
Venue: arXiv cs.LG 2016
Year: 2016

Unlike traditional programs (such as operating systems or word processors) which have large amounts of code, machine learning tasks use programs with relatively small amounts of code (written in machine learning libraries), but voluminous amounts of data. Just like developers of traditional programs debug errors in their code, developers of machine learning tasks debug and fix errors in their data. However, algorithms and tools for debugging and fixing errors in data are less common, when compared to their counterparts for detecting and fixing errors in code. In this paper, we consider classification tasks where errors in training data lead to misclassifications in test points, and propose an automated method to find the root causes of such misclassifications. Our root cause analysis is based on Pearl's theory of causation, and uses Pearl's PS (Probability of Sufficiency) as a scoring metric. Our implementation, Psi, encodes the computation of PS as a probabilistic program, and uses recent work on probabilistic programs and transformations on probabilistic programs (along with gray-box models of machine learning algorithms) to efficiently compute PS. Psi is able to identify root causes of data errors in interesting data sets.
Mobile Icosapods
Venue: arXiv cs.RO 2016
Year: 2016

Pods are mechanical devices constituted of two rigid bodies, the base and the platform, connected by a number of other rigid bodies, called legs, that are anchored via spherical joints. It is possible to prove that the maximal number of legs of a mobile pod, when finite, is 20. In 1904, Borel designed a technique to construct examples of such 20-pods, but could not constrain the legs to have base and platform points with real coordinates. We show that Borel's construction yields all mobile 20-pods, and that it is possible to construct examples with all real coordinates.
CONDITOR1: Topic Maps and DITA labelling tool for textual documents with historical information
Venue: arXiv cs.DL 2016
Year: 2016

Conditor is a software tool which works with textual documents containing historical information. The purpose of this work two-fold: firstly to show the validity of the developed engine to correctly identify and label the entities of the universe of discourse with a labelled-combined XTM-DITA model. Secondly to explain the improvements achieved in the information retrieval process thanks to the use of a object-oriented database (JPOX) as well as its integration into the Lucene-type database search process to not only accomplish more accurate searches, but to also help the future development of a recommender system. We finish with a brief demo in a 3D-graph of the results of the aforementioned search.
Acceleration of Deep Neural Network Training with Resistive Cross-Point Devices
Venue: arXiv cs.LG 2016
Year: 2016

In recent years, deep neural networks (DNN) have demonstrated significant business impact in large scale analysis and classification tasks such as speech recognition, visual object detection, pattern extraction, etc. Training of large DNNs, however, is universally considered as time consuming and computationally intensive task that demands datacenter-scale computational resources recruited for many days. Here we propose a concept of resistive processing unit (RPU) devices that can potentially accelerate DNN training by orders of magnitude while using much less power. The proposed RPU device can store and update the weight values locally thus minimizing data movement during training and allowing to fully exploit the locality and the parallelism of the training algorithm. We identify the RPU device and system specifications for implementation of an accelerator chip for DNN training in a realistic CMOS-compatible technology. For large DNNs with about 1 billion weights this massively parallel RPU architecture can achieve acceleration factors of 30,000X compared to state-of-the-art microprocessors while providing power efficiency of 84,000 GigaOps/s/W. Problems that currently require days of training on a datacenter-size cluster with thousands of machines can be addressed within hours on a single RPU accelerator. A system consisted of a cluster of RPU accelerators will be able to tackle Big Data problems with trillions of parameters that is impossible to address today like, for example, natural speech recognition and translation between all world languages, real-time analytics on large streams of business and scientific data, integration and analysis of multimodal sensory data flows from massive number of IoT (Internet of Things) sensors.
DocLite: A Docker-Based Lightweight Cloud Benchmarking Tool
Venue: arXiv cs.DC 2016
Year: 2016

Existing benchmarking methods are time consuming processes as they typically benchmark the entire Virtual Machine (VM) in order to generate accurate performance data, making them less suitable for real-time analytics. The research in this paper is aimed to surmount the above challenge by presenting DocLite - Docker Container-based Lightweight benchmarking tool. DocLite explores lightweight cloud benchmarking methods for rapidly executing benchmarks in near real-time. DocLite is built on the Docker container technology, which allows a user-defined memory size and number of CPU cores of the VM to be benchmarked. The tool incorporates two benchmarking methods - the first referred to as the native method employs containers to benchmark a small portion of the VM and generate performance ranks, and the second uses historic benchmark data along with the native method as a hybrid to generate VM ranks. The proposed methods are evaluated on three use-cases and are observed to be up to 91 times faster than benchmarking the entire VM. In both methods, small containers provide the same quality of rankings as a large container. The native method generates ranks with over 90% and 86% accuracy for sequential and parallel execution of an application compared against benchmarking the whole VM. The hybrid method did not improve the quality of the rankings significantly.
Load Disaggregation Based on Aided Linear Integer Programming
Venue: arXiv cs.AI 2016
Year: 2016

Load disaggregation based on aided linear integer programming (ALIP) is proposed. We start with a conventional linear integer programming (IP) based disaggregation and enhance it in several ways. The enhancements include additional constraints, correction based on a state diagram, median filtering, and linear programming-based refinement. With the aid of these enhancements, the performance of IP-based disaggregation is significantly improved. The proposed ALIP system relies only on the instantaneous load samples instead of waveform signatures, and hence does not crucially depend on high sampling frequency. Experimental results show that the proposed ALIP system performs better than the conventional IP-based load disaggregation system.
Characterizing Honeypot-Captured Cyber Attacks: Statistical Framework and Case Study
Venue: arXiv cs.CR 2016
Year: 2016

Rigorously characterizing the statistical properties of cyber attacks is an important problem. In this paper, we propose the {\em first} statistical framework for rigorously analyzing honeypot-captured cyber attack data. The framework is built on the novel concept of {\em stochastic cyber attack process}, a new kind of mathematical objects for describing cyber attacks. To demonstrate use of the framework, we apply it to analyze a low-interaction honeypot dataset, while noting that the framework can be equally applied to analyze high-interaction honeypot data that contains richer information about the attacks. The case study finds, for the first time, that Long-Range Dependence (LRD) is exhibited by honeypot-captured cyber attacks. The case study confirms that by exploiting the statistical properties (LRD in this case), it is feasible to predict cyber attacks (at least in terms of attack rate) with good accuracy. This kind of prediction capability would provide sufficient early-warning time for defenders to adjust their defense configurations or resource allocations. The idea of "gray-box" (rather than "black-box") prediction is central to the utility of the statistical framework, and represents a significant step towards ultimately understanding (the degree of) the {\em predictability} of cyber attacks.
Parameterized Pattern Matching -- Succinctly
Venue: arXiv cs.DS 2016
Year: 2016

We consider the $Parameterized$ $Pattern$ $Matching$ problem, where a pattern $P$ matches some location in a text $\mathsf{T}$ iff there is a one-to-one correspondence between the alphabet symbols of the pattern to those of the text. More specifically, assume that the text $\mathsf{T}$ contains $n$ characters from a static alphabet $Σ_s$ and a parameterized alphabet $Σ_p$, where $Σ_s \cap Σ_p = \varnothing$ and $|Σ_s \cup Σ_p|=σ$. A pattern $P$ matches a substring $S$ of $\mathsf{T}$ iff the static characters match exactly, and there exists a one-to-one function that renames the parameterized characters in $S$ to that in $P$. Previous indexing solution [Baker, STOC 1993], known as $Parameterized$ $Suffix$ $Tree$, requires $Θ(n\log n)$ bits of space, and can find all $occ$ occurrences of $P$ in $\mathcal{O}(|P|\log σ+ occ)$ time. In this paper, we present the first succinct index that occupies $n \log σ+ \mathcal{O}(n)$ bits and answers queries in $\mathcal{O}((|P|+ occ\cdot \log n) \logσ\log \log σ)$ time. We also present a compact index that occupies $\mathcal{O}(n\logσ)$ bits and answers queries in $\mathcal{O}(|P|\log σ+ occ\cdot \log n)$ time. Furthermore, the techniques are extended to obtain the first succinct representation of the index of Shibuya for $Structural$ $Matching$ [SWAT, 2000], and of Idury and Schäffer for $Parameterized$ $Dictionary$ $Matching$ [CPM, 1994].
Source Localization on Graphs via l1 Recovery and Spectral Graph Theory
Venue: arXiv cs.LG 2016
Year: 2016

We cast the problem of source localization on graphs as the simultaneous problem of sparse recovery and diffusion kernel learning. An l1 regularization term enforces the sparsity constraint while we recover the sources of diffusion from a single snapshot of the diffusion process. The diffusion kernel is estimated by assuming the process to be as generic as the standard heat diffusion. We show with synthetic data that we can concomitantly learn the diffusion kernel and the sources, given an estimated initialization. We validate our model with cholera mortality and atmospheric tracer diffusion data, showing also that the accuracy of the solution depends on the construction of the graph from the data points.
Semantic Regularities in Document Representations
Venue: arXiv cs.CL 2016
Year: 2016

Recent work exhibited that distributed word representations are good at capturing linguistic regularities in language. This allows vector-oriented reasoning based on simple linear algebra between words. Since many different methods have been proposed for learning document representations, it is natural to ask whether there is also linear structure in these learned representations to allow similar reasoning at document level. To answer this question, we design a new document analogy task for testing the semantic regularities in document representations, and conduct empirical evaluations over several state-of-the-art document representation models. The results reveal that neural embedding based document representations work better on this analogy task than conventional methods, and we provide some preliminary explanations over these observations.
Multi-Subregion Based Correlation Filter Bank for Robust Face Recognition
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose an effective feature extraction algorithm, called Multi-Subregion based Correlation Filter Bank (MS-CFB), for robust face recognition. MS-CFB combines the benefits of global-based and local-based feature extraction algorithms, where multiple correlation filters correspond- ing to different face subregions are jointly designed to optimize the overall correlation outputs. Furthermore, we reduce the computational complexi- ty of MS-CFB by designing the correlation filter bank in the spatial domain and improve its generalization capability by capitalizing on the unconstrained form during the filter bank design process. MS-CFB not only takes the d- ifferences among face subregions into account, but also effectively exploits the discriminative information in face subregions. Experimental results on various public face databases demonstrate that the proposed algorithm pro- vides a better feature representation for classification and achieves higher recognition rates compared with several state-of-the-art algorithms.
BanditRepair: Speculative Exploration of Runtime Patches
Venue: arXiv cs.SE 2016
Year: 2016

We propose, BanditRepair, a system that systematically explores and assesses a set of possible runtime patches. The system is grounded on so-called bandit algorithms, that are online machine learning algorithms, designed for constantly balancing exploitation and exploration. BanditRepair's runtime patches are based on modifying the execution state for repairing null dereferences. BanditRepair constantly trades the ratio of automatically handled failures for searching for new runtime patches and vice versa. We evaluate the system with 16 null dereference field bugs, where BanditRepair identifies a total of 8460 different runtime patches, which are composed of 1 up to 8 decisions (execution modifications) taken in a row. We are the first to finely characterize the search space and the outcomes of runtime repair based on execution modification.
Exploring the Use of RPAs as 5G Points of Presence
Venue: arXiv cs.NI 2016
Year: 2016

This paper presents an early exploration and preliminary results on the use of Remotely Piloted Aircrafts (RPA) as 5G points of presence. The use of RPAs in the 5G arena would enable a cost-effective deployment of functions over mobile nodes that could be integrated on demand into the programmable and unified 5G infrastructure, enhancing the capacity of the network to flexibly adapt to the particular service requirements in a geographical area. As a first step, we evaluate the feasibility and the cost, in terms of energy consumption, of using virtualisation techniques over resource-constrained aerial vehicle platforms, as a fundamental software technology in the evolution towards 5G. We complement this evaluation presenting a proof-of-concept that considers the use of these platforms to enable real-time 5G communications in emergency cases.
Promoting Efficient Infrastructure Competition through Vectoring and Enlarged DSL Bandwidth
Venue: arXiv cs.NI 2016
Year: 2016

The most effective way to promote Next Generation Access coverage and ultra-broadband penetration is through infrastructure competition.
Probabilistic Reasoning via Deep Learning: Neural Association Models
Venue: arXiv cs.AI 2016
Year: 2016

In this paper, we propose a new deep learning approach, called neural association model (NAM), for probabilistic reasoning in artificial intelligence. We propose to use neural networks to model association between any two events in a domain. Neural networks take one event as input and compute a conditional probability of the other event to model how likely these two events are to be associated. The actual meaning of the conditional probabilities varies between applications and depends on how the models are trained. In this work, as two case studies, we have investigated two NAM structures, namely deep neural networks (DNN) and relation-modulated neural nets (RMNN), on several probabilistic reasoning tasks in AI, including recognizing textual entailment, triple classification in multi-relational knowledge bases and commonsense reasoning. Experimental results on several popular datasets derived from WordNet, FreeBase and ConceptNet have all demonstrated that both DNNs and RMNNs perform equally well and they can significantly outperform the conventional methods available for these reasoning tasks. Moreover, compared with DNNs, RMNNs are superior in knowledge transfer, where a pre-trained model can be quickly extended to an unseen relation after observing only a few training samples. To further prove the effectiveness of the proposed models, in this work, we have applied NAMs to solving challenging Winograd Schema (WS) problems. Experiments conducted on a set of WS problems prove that the proposed models have the potential for commonsense reasoning.
The Planar Tree Packing Theorem
Venue: arXiv cs.CG 2016
Year: 2016

Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. In the planar tree packing problem we are given two trees T1 and T2 on n vertices and have to find a planar graph on n vertices that is the edge-disjoint union of T1 and T2. A clear exception that must be made is the star which cannot be packed together with any other tree. But according to a conjecture of García et al. from 1997 this is the only exception, and all other pairs of trees admit a planar packing. Previous results addressed various special cases, such as a tree and a spider tree, a tree and a caterpillar, two trees of diameter four, two isomorphic trees, and trees of maximum degree three. Here we settle the conjecture in the affirmative and prove its general form, thus making it the planar tree packing theorem. The proof is constructive and provides a polynomial time algorithm to obtain a packing for two given nonstar trees.
Simulation Platform for Multi Agent Based Manufacturing Control System Based on The Hybrid Agent
Venue: arXiv cs.MA 2016
Year: 2016

Agent based distributed manufacturing control and scheduling systems are subsets of new manufacturing systems. Multi agent systems (MAS) not only drive design and engineering control solutions but also influence flexibility, agility, and re-configurability, which makes MASs a better centralized systems than its traditional counterparts. However, implementation of all MASs in the real factories are timely, also extremely costly. A simulation environment that would allow independent development and testing of the services and business processes of the related manufacturing hardware is needed. This paper presents the design and implementation of a userfriendly simulation platform for multi agent based manufacturing control systems by considering the shop floor level. The proposed simulation platform can simulate the software level of the factory by considering the hardware level of the mentioned factory. An example of the simulation platform is presented for a flexible manufacturing system, which is located in EMU CIM lab.
Mode-Seeking on Hypergraphs for Robust Geometric Model Fitting
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose a novel geometric model fitting method, called Mode-Seeking on Hypergraphs (MSH),to deal with multi-structure data even in the presence of severe outliers. The proposed method formulates geometric model fitting as a mode seeking problem on a hypergraph in which vertices represent model hypotheses and hyperedges denote data points. MSH intuitively detects model instances by a simple and effective mode seeking algorithm. In addition to the mode seeking algorithm, MSH includes a similarity measure between vertices on the hypergraph and a weight-aware sampling technique. The proposed method not only alleviates sensitivity to the data distribution, but also is scalable to large scale problems. Experimental results further demonstrate that the proposed method has significant superiority over the state-of-the-art fitting methods on both synthetic data and real images.
Chatty Maps: Constructing sound maps of urban areas from social media data
Venue: arXiv cs.SI 2016
Year: 2016

Urban sound has a huge influence over how we perceive places. Yet, city planning is concerned mainly with noise, simply because annoying sounds come to the attention of city officials in the form of complaints, while general urban sounds do not come to the attention as they cannot be easily captured at city scale. To capture both unpleasant and pleasant sounds, we applied a new methodology that relies on tagging information of geo-referenced pictures to the cities of London and Barcelona. To begin with, we compiled the first urban sound dictionary and compared it to the one produced by collating insights from the literature: ours was experimentally more valid (if correlated with official noise pollution levels) and offered a wider geographic coverage. From picture tags, we then studied the relationship between soundscapes and emotions. We learned that streets with music sounds were associated with strong emotions of joy or sadness, while those with human sounds were associated with joy or surprise. Finally, we studied the relationship between soundscapes and people's perceptions and, in so doing, we were able to map which areas are chaotic, monotonous, calm, and exciting.Those insights promise to inform the creation of restorative experiences in our increasingly urbanized world.
Loss Tomography in General Topology
Venue: arXiv cs.NI 2016
Year: 2016

Although there are a few works reported in the literature considering loss tomography in the general topology, there is few well established result since all of them rely either on simulations or on experiments that have many random factors affecting the outcome. To improve the situation, we address a number of issues in this paper that include a maximum likelihood estimator (MLE) for the general topology, the statistical properties of the MLE, the statistical properties of a frequently referred estimator called the moving variance and weighted average (MVWA), and a renewed MVWA that removes the restriction of knowing variance in advance from the MVWA. The statistical properties covers minimum-variance unbiasedness, efficiency, and variances of the estimates obtained by the estimators. Given the properties, we can evaluate the estimators without the need of simulations. To verify the properties, a simulation study is conducted that confirms the accuracy of the findings.