OpenRaiser/Intern-Atlas huggingface dataset:
Smaller parameters for vertex cover kernelization
Venue: arXiv cs.DS 2017
Year: 2017

We revisit the topic of polynomial kernels for Vertex Cover relative to structural parameters. Our starting point is a recent paper due to Fomin and Strømme [WG 2016] who gave a kernel with $\mathcal{O}(|X|^{12})$ vertices when $X$ is a vertex set such that each connected component of $G-X$ contains at most one cycle, i.e., $X$ is a modulator to a pseudoforest. We strongly generalize this result by using modulators to $d$-quasi-forests, i.e., graphs where each connected component has a feedback vertex set of size at most $d$, and obtain kernels with $\mathcal{O}(|X|^{3d+9})$ vertices. Our result relies on proving that minimal blocking sets in a $d$-quasi-forest have size at most $d+2$. This bound is tight and there is a related lower bound of $\mathcal{O}(|X|^{d+2-ε})$ on the bit size of kernels. In fact, we also get bounds for minimal blocking sets of more general graph classes: For $d$-quasi-bipartite graphs, where each connected component can be made bipartite by deleting at most $d$ vertices, we get the same tight bound of $d+2$ vertices. For graphs whose connected components each have a vertex cover of cost at most $d$ more than the best fractional vertex cover, which we call $d$-quasi-integral, we show that minimal blocking sets have size at most $2d+2$, which is also tight. Combined with existing randomized polynomial kernelizations this leads to randomized polynomial kernelizations for modulators to $d$-quasi-bipartite and $d$-quasi-integral graphs. There are lower bounds of $\mathcal{O}(|X|^{d+2-ε})$ and $\mathcal{O}(|X|^{2d+2-ε})$ for the bit size of such kernels.
On Designing a Generic Framework for Cloud-based Big Data Analytics
Venue: arXiv cs.CY 2017
Year: 2017

Big data analytics has gathered immense research attention lately because of its ability to harness useful information from heaps of data. Cloud computing has been adjudged as one of the best infrastructural solutions for implementation of big data analytics. This research paper proposes a five-layer model for cloud-based big data analytics that uses dew computing and edge computing concepts. Besides this, the paper also presents an approach for creation of custom big data stack by selecting technologies on the basis of identified data and computing models for the application
Stampery Blockchain Timestamping Architecture (BTA) - Version 6
Venue: arXiv cs.CR 2017
Year: 2017

A method for timestamping, anchoring and certification of a virtually unlimited amount of data in one or more blockchains, focusing on scalability and cost-effectiveness while ensuring existence, integrity and ownership by using cryptographic proofs that are independently verifiable by anyone in the world without disclosure of the original data and without the intervention of the certifying party.
ADaPTION: Toolbox and Benchmark for Training Convolutional Neural Networks with Reduced Numerical Precision Weights and Activation
Venue: arXiv cs.LG 2017
Year: 2017

Deep Neural Networks (DNNs) and Convolutional Neural Networks (CNNs) are useful for many practical tasks in machine learning. Synaptic weights, as well as neuron activation functions within the deep network are typically stored with high-precision formats, e.g. 32 bit floating point. However, since storage capacity is limited and each memory access consumes power, both storage capacity and memory access are two crucial factors in these networks. Here we present a method and present the ADaPTION toolbox to extend the popular deep learning library Caffe to support training of deep CNNs with reduced numerical precision of weights and activations using fixed point notation. ADaPTION includes tools to measure the dynamic range of weights and activations. Using the ADaPTION tools, we quantized several CNNs including VGG16 down to 16-bit weights and activations with only 0.8% drop in Top-1 accuracy. The quantization, especially of the activations, leads to increase of up to 50% of sparsity especially in early and intermediate layers, which we exploit to skip multiplications with zero, thus performing faster and computationally cheaper inference.
3D Shape Classification Using Collaborative Representation based Projections
Venue: arXiv cs.CV 2017
Year: 2017

A novel 3D shape classification scheme, based on collaborative representation learning, is investigated in this work. A data-driven feature-extraction procedure, taking the form of a simple projection operator, is in the core of our methodology. Provided a shape database, a graph encapsulating the structural relationships among all the available shapes, is first constructed and then employed in defining low-dimensional sparse projections. The recently introduced method of CRPs (collaborative representation based projections), which is based on L2-Graph, is the first variant that is included towards this end. A second algorithm, that particularizes the CRPs to shape descriptors that are inherently nonnegative, is also introduced as potential alternative. In both cases, the weights in the graph reflecting the database structure are calculated so as to approximate each shape as a sparse linear combination of the remaining dataset objects. By way of solving a generalized eigenanalysis problem, a linear matrix operator is designed that will act as the feature extractor. Two popular, inherently high dimensional descriptors, namely ShapeDNA and Global Point Signature (GPS), are employed in our experimentations with SHREC10, SHREC11 and SCHREC 15 datasets, where shape recognition is cast as a multi-class classification problem that is tackled by means of an SVM (support vector machine) acting within the reduced dimensional space of the crafted projections. The results are very promising and outperform state of the art methods, providing evidence about the highly discriminative nature of the introduced 3D shape representations.
Peg-in-Hole Revisited: A Generic Force Model for Haptic Assembly
Venue: arXiv cs.HC 2017
Year: 2017

The development of a generic and effective force model for semi-automatic or manual virtual assembly with haptic support is not a trivial task, especially when the assembly constraints involve complex features of arbitrary shape. The primary challenge lies in a proper formulation of the guidance forces and torques that effectively assist the user in the exploration of the virtual environment (VE), from repulsing collisions to attracting proper contact. The secondary difficulty is that of efficient implementation that maintains the standard 1 kHz haptic refresh rate. We propose a purely geometric model for an artificial energy field that favors spatial relations leading to proper assembly, differentiated to obtain forces and torques for general motions. The energy function is expressed in terms of a cross-correlation of shape-dependent affinity fields, precomputed offline separately for each object. We test the effectiveness of the method using familiar peg-in-hole examples. We show that the proposed technique unifies the two phases of free motion and precise insertion into a single interaction mode and provides a generic model to replace the ad hoc mating constraints or virtual fixtures, with no restrictive assumption on the types of the involved assembly features.
Haptic Assembly Using Skeletal Densities and Fourier Transforms
Venue: arXiv cs.HC 2017
Year: 2017

Haptic-assisted virtual assembly and prototyping has seen significant attention over the past two decades. However, in spite of the appealing prospects, its adoption has been slower than expected. We identify the main roadblocks as the inherent geometric complexities faced when assembling objects of arbitrary shape, and the computation time limitation imposed by the notorious 1 kHz haptic refresh rate. We addressed the first problem in a recent work by introducing a generic energy model for geometric guidance and constraints between features of arbitrary shape. In the present work, we address the second challenge by leveraging Fourier transforms to compute the constraint forces and torques. Our new concept of 'geometric energy' field is computed automatically from a cross-correlation of 'skeletal densities' in the frequency domain, and serves as a generalization of the manually specified virtual fixtures or heuristically identified mating constraints proposed in the literature. The formulation of the energy field as a convolution enables efficient computation using fast Fourier transforms (FFT) on the graphics processing unit (GPU). We show that our method is effective for low-clearance assembly of objects of arbitrary geometric and syntactic complexity.
Comparing Bug Finding Tools with Reviews and Tests
Venue: arXiv cs.SE 2017
Year: 2017

Bug finding tools can find defects in software source code us- ing an automated static analysis. This automation may be able to reduce the time spent for other testing and review activities. For this we need to have a clear understanding of how the defects found by bug finding tools relate to the defects found by other techniques. This paper describes a case study using several projects mainly from an industrial environment that were used to analyse the interrelationships. The main finding is that the bug finding tools predominantly find different defects than testing but a subset of defects found by reviews. However, the types that can be detected are analysed more thoroughly. Therefore, a combination is most advisable if the high number of false positives of the tools can be tolerated.
Energy-Delay-Distortion Problem
Venue: arXiv cs.IT 2017
Year: 2017

An energy-limited source trying to transmit multiple packets to a destination with possibly different sizes is considered. With limited energy, the source cannot potentially transmit all bits of all packets. In addition, there is a delay cost associated with each packet. Thus, the source has to choose, how many bits to transmit for each packet, and the order in which to transmit these bits, to minimize the cost of distortion (introduced by transmitting lower number of bits) and queueing plus transmission delay, across all packets. Assuming an exponential metric for distortion loss and linear delay cost, we show that the optimization problem is jointly convex. Hence, the problem can be exactly solved using convex solvers, however, because of the complicated expression derived from the KKT conditions, no closed form solution can be found even with the simplest cost function choice made in the paper, also the optimal order in which packets should be transmitted needs to be found via brute force. To facilitate a more structured solution, a discretized version of the problem is also considered, where time and energy are divided in discrete amounts. In any time slot (fixed length), bits belonging to any one packet can be transmitted, while any discrete number of energy quanta can be used in any slot corresponding to any one packet, such that the total energy constraint is satisfied. The discretized problem is a special case of a multi-partitioning problem, where each packet's utility is super-modular and the proposed greedy solution is shown to incur cost that is at most $2$-times of the optimal cost.
Application of Machine Learning for Channel based Message Authentication in Mission Critical Machine Type Communication
Venue: arXiv cs.NI 2017
Year: 2017

The design of robust wireless communication systems for industrial applications such as closed loop control processes has been considered manifold recently. Additionally, the ongoing advances in the area of connected mobility have similar or even higher requirements regarding system reliability and availability. Beside unfulfilled reliability requirements, the availability of a system can further be reduced, if it is under attack in the sense of violation of information security goals such as data authenticity or integrity. In order to guarantee the safe operation of an application, a system has at least to be able to detect these attacks. Though there are numerous techniques in the sense of conventional cryptography in order to achieve that goal, these are not always suited for the requirements of the applications mentioned due to resource inefficiency. In the present work, we show how the goal of message authenticity based on physical layer security (PHYSEC) can be achieved. The main idea for such techniques is to exploit user specific characteristics of the wireless channel, especially in spatial domain. Additionally, we show the performance of our machine learning based approach and compare it with other existing approaches.
A note on the complexity of Feedback Vertex Set parameterized by mim-width
Venue: arXiv cs.CC 2017
Year: 2017

We complement the recent algorithmic result that Feedback Vertex Set is XP-time solvable parameterized by the mim-width of a given branch decomposition of the input graph [3] by showing that the problem is W[1]-hard in this parameterization. The hardness holds even for linear mim-width, as well as for H-graphs, where the parameter is the number of edges in H. To obtain this result, we adapt a reduction due to Fomin, Golovach and Raymond [2], following the same line of reasoning but adding a new gadget.
CheXNet: Radiologist-Level Pneumonia Detection on Chest X-Rays with Deep Learning
Venue: arXiv cs.CV 2017
Year: 2017

We develop an algorithm that can detect pneumonia from chest X-rays at a level exceeding practicing radiologists. Our algorithm, CheXNet, is a 121-layer convolutional neural network trained on ChestX-ray14, currently the largest publicly available chest X-ray dataset, containing over 100,000 frontal-view X-ray images with 14 diseases. Four practicing academic radiologists annotate a test set, on which we compare the performance of CheXNet to that of radiologists. We find that CheXNet exceeds average radiologist performance on the F1 metric. We extend CheXNet to detect all 14 diseases in ChestX-ray14 and achieve state of the art results on all 14 diseases.
Private Information Retrieval from Storage Constrained Databases -- Coded Caching meets PIR
Venue: arXiv cs.IT 2017
Year: 2017

Private information retrieval (PIR) allows a user to retrieve a desired message out of $K$ possible messages from $N$ databases without revealing the identity of the desired message. Majority of existing works on PIR assume the presence of replicated databases, each storing all the $K$ messages. In this work, we consider the problem of PIR from storage constrained databases. Each database has a storage capacity of $μKL$ bits, where $K$ is the number of messages, $L$ is the size of each message in bits, and $μ\in [1/N, 1]$ is the normalized storage. In the storage constrained PIR problem, there are two key design questions: a) how to store content across each database under storage constraints; and b) construction of schemes that allow efficient PIR through storage constrained databases. The main contribution of this work is a general achievable scheme for PIR from storage constrained databases for any value of storage. In particular, for any $(N,K)$, with normalized storage $μ= t/N$, where the parameter $t$ can take integer values $t \in \{1, 2, \ldots, N\}$, we show that our proposed PIR scheme achieves a download cost of $\left(1+ \frac{1}{t}+ \frac{1}{t^{2}}+ \cdots + \frac{1}{t^{K-1}}\right)$. The extreme case when $μ=1$ (i.e., $t=N$) corresponds to the setting of replicated databases with full storage. For this extremal setting, our scheme recovers the information-theoretically optimal download cost characterized by Sun and Jafar as $\left(1+ \frac{1}{N}+ \cdots + \frac{1}{N^{K-1}}\right)$. For the other extreme, when $μ= 1/N$ (i.e., $t=1$), the proposed scheme achieves a download cost of $K$. The interesting aspect of the result is that for intermediate values of storage, i.e., $1/N < μ<1$, the proposed scheme can strictly outperform memory-sharing between extreme values of storage.
Deep-ESN: A Multiple Projection-encoding Hierarchical Reservoir Computing Framework
Venue: arXiv cs.LG 2017
Year: 2017

As an efficient recurrent neural network (RNN) model, reservoir computing (RC) models, such as Echo State Networks, have attracted widespread attention in the last decade. However, while they have had great success with time series data [1], [2], many time series have a multiscale structure, which a single-hidden-layer RC model may have difficulty capturing. In this paper, we propose a novel hierarchical reservoir computing framework we call Deep Echo State Networks (Deep-ESNs). The most distinctive feature of a Deep-ESN is its ability to deal with time series through hierarchical projections. Specifically, when an input time series is projected into the high-dimensional echo-state space of a reservoir, a subsequent encoding layer (e.g., a PCA, autoencoder, or a random projection) can project the echo-state representations into a lower-dimensional space. These low-dimensional representations can then be processed by another ESN. By using projection layers and encoding layers alternately in the hierarchical framework, a Deep-ESN can not only attenuate the effects of the collinearity problem in ESNs, but also fully take advantage of the temporal kernel property of ESNs to explore multiscale dynamics of time series. To fuse the multiscale representations obtained by each reservoir, we add connections from each encoding layer to the last output layer. Theoretical analyses prove that stability of a Deep-ESN is guaranteed by the echo state property (ESP), and the time complexity is equivalent to a conventional ESN. Experimental results on some artificial and real world time series demonstrate that Deep-ESNs can capture multiscale dynamics, and outperform both standard ESNs and previous hierarchical ESN-based models.
Practical Whole-System Provenance Capture
Venue: arXiv cs.CR 2017
Year: 2017

Data provenance describes how data came to be in its present form. It includes data sources and the transformations that have been applied to them. Data provenance has many uses, from forensics and security to aiding the reproducibility of scientific experiments. We present CamFlow, a whole-system provenance capture mechanism that integrates easily into a PaaS offering. While there have been several prior whole-system provenance systems that captured a comprehensive, systemic and ubiquitous record of a system's behavior, none have been widely adopted. They either A) impose too much overhead, B) are designed for long-outdated kernel releases and are hard to port to current systems, C) generate too much data, or D) are designed for a single system. CamFlow addresses these shortcoming by: 1) leveraging the latest kernel design advances to achieve efficiency; 2) using a self-contained, easily maintainable implementation relying on a Linux Security Module, NetFilter, and other existing kernel facilities; 3) providing a mechanism to tailor the captured provenance data to the needs of the application; and 4) making it easy to integrate provenance across distributed systems. The provenance we capture is streamed and consumed by tenant-built auditor applications. We illustrate the usability of our implementation by describing three such applications: demonstrating compliance with data regulations; performing fault/intrusion detection; and implementing data loss prevention. We also show how CamFlow can be leveraged to capture meaningful provenance without modifying existing applications.
Online Political Discourse in the Trump Era
Venue: arXiv cs.CY 2017
Year: 2017

We identify general trends in the (in)civility and complexity of political discussions occurring on Reddit between January 2007 and May 2017 -- a period spanning both terms of Barack Obama's presidency and the first 100 days of Donald Trump's presidency. We then investigate four factors that are frequently hypothesized as having contributed to the declining quality of American political discourse -- (1) the rising popularity of Donald Trump, (2) increasing polarization and negative partisanship, (3) the democratization of news media and the rise of fake news, and (4) merging of fringe groups into mainstream political discussions.
Programming Bots by Synthesizing Natural Language Expressions into API Invocations
Venue: arXiv cs.SE 2017
Year: 2017

At present, bots are still in their preliminary stages of development. Many are relatively simple, or developed ad-hoc for a very specific use-case. For this reason, they are typically programmed manually, or utilize machine-learning classifiers to interpret a fixed set of user utterances. In reality, real world conversations with humans require support for dynamically capturing users expressions. Moreover, bots will derive immeasurable value by programming them to invoke APIs for their results. Today, within the Web and Mobile development community, complex applications are being stringed together with a few lines of code -- all made possible by APIs. Yet, developers today are not as empowered to program bots in much the same way. To overcome this, we introduce BotBase, a bot programming platform that dynamically synthesizes natural language user expressions into API invocations. Our solution is two faceted: Firstly, we construct an API knowledge graph to encode and evolve APIs; secondly, leveraging the above we apply techniques in NLP, ML and Entity Recognition to perform the required synthesis from natural language user expressions into API calls.
On the Anti-Jamming Performance of the NR-DCSK System
Venue: arXiv cs.IT 2017
Year: 2017

This paper investigates the anti-jamming performance of the NR-DCSK system. We consider several practical jamming environments including broad-band jamming (BBJ), partial-time jamming (PTJ), tone jamming (TJ) consisting of both single-tone and multi-tone, and sweep jamming (SWJ). We first analytically derived the bit error rates of the considered system under the BBJ and the PTJ environments in closed-form expressions. Our derived results show that the system performances under these two jamming environments are enhanced as $P$ increases, where $P$ is the parameter of the NR-DCSK modulation scheme denoting the number of times a chaotic sample is repeated. In addition, our results demonstrate that for the PTJ, the optimal value of the jamming factor is close to zero when the jamming power is small, however, it increases and approaches one as the jamming power enlarges. We then investigate the performance of the considered system under the TJ and the SWJ environments via Monte-Carlo simulations. Our simulations show that single-tone jamming causes a more significant performance degradation than that provided by multi-tone jamming counterparts. Moreover, we point out that the system performance is significantly degraded when the starting frequency of the sweep jammer is close to the carrier frequency of the transmitted chaotic signals, the sweep bandwidth is small, and the sweep time is half of the transmitted bit duration.
Tracking Typological Traits of Uralic Languages in Distributed Language Representations
Venue: arXiv cs.CL 2017
Year: 2017

Although linguistic typology has a long history, computational approaches have only recently gained popularity. The use of distributed representations in computational linguistics has also become increasingly popular. A recent development is to learn distributed representations of language, such that typologically similar languages are spatially close to one another. Although empirical successes have been shown for such language representations, they have not been subjected to much typological probing. In this paper, we first look at whether this type of language representations are empirically useful for model transfer between Uralic languages in deep neural networks. We then investigate which typological features are encoded in these representations by attempting to predict features in the World Atlas of Language Structures, at various stages of fine-tuning of the representations. We focus on Uralic languages, and find that some typological traits can be automatically inferred with accuracies well above a strong baseline.