OpenRaiser/Intern-Atlas huggingface dataset:
A Unifying Framework for Manipulation Problems
Venue: arXiv cs.MA 2018
Year: 2018

Manipulation models for electoral systems are a core research theme in social choice theory; they include bribery (unweighted, weighted, swap, shift, ...), control (by adding or deleting voters or candidates), lobbying in referenda and others. We develop a unifying framework for manipulation models with few types of people, one of the most commonly studied scenarios. A critical insight of our framework is to separate the descriptive complexity of the voting rule R from the number of types of people. This allows us to finally settle the computational complexity of R-Swap Bribery, one of the most fundamental manipulation problems. In particular, we prove that R-Swap Bribery is fixed-parameter tractable when R is Dodgson's rule and Young's rule, when parameterized by the number of candidates. This way, we resolve a long-standing open question from 2007 which was explicitly asked by Faliszewski et al. [JAIR 40, 2011]. Our algorithms reveal that the true hardness of bribery problems often stems from the complexity of the voting rules. On one hand, we give a fixed-parameter algorithm parameterized by number of types of people for complex voting rules. Thus, we reveal that R-Swap Bribery with Dodgson's rule is much harder than with Condorcet's rule, which can be expressed by a conjunction of linear inequalities, while Dodson's rule requires quantifier alternation and a bounded number of disjunctions of linear systems. On the other hand, we give an algorithm for quantifier-free voting rules which is parameterized only by the number of conjunctions of the voting rule and runs in time polynomial in the number of types of people. This way, our framework explains why Shift Bribery is polynomial-time solvable for the plurality voting rule, making explicit that the rule is simple in that it can be expressed with a single linear inequality, and that the number of voter types is polynomial.
Helping Crisis Responders Find the Informative Needle in the Tweet Haystack
Venue: arXiv cs.CL 2018
Year: 2018

Crisis responders are increasingly using social media, data and other digital sources of information to build a situational understanding of a crisis situation in order to design an effective response. However with the increased availability of such data, the challenge of identifying relevant information from it also increases. This paper presents a successful automatic approach to handling this problem. Messages are filtered for informativeness based on a definition of the concept drawn from prior research and crisis response experts. Informative messages are tagged for actionable data -- for example, people in need, threats to rescue efforts, changes in environment, and so on. In all, eight categories of actionability are identified. The two components -- informativeness and actionability classification -- are packaged together as an openly-available tool called Emina (Emergent Informativeness and Actionability).
Denoising Arterial Spin Labeling Cerebral Blood Flow Images Using Deep Learning
Venue: arXiv cs.CV 2018
Year: 2018

Arterial spin labeling perfusion MRI is a noninvasive technique for measuring quantitative cerebral blood flow (CBF), but the measurement is subject to a low signal-to-noise-ratio(SNR). Various post-processing methods have been proposed to denoise ASL MRI but only provide moderate improvement. Deep learning (DL) is an emerging technique that can learn the most representative signal from data without prior modeling which can be highly complex and analytically indescribable. The purpose of this study was to assess whether the record breaking performance of DL can be translated into ASL MRI denoising. We used convolutional neural network (CNN) to build the DL ASL denosing model (DL-ASL) to inherently consider the inter-voxel correlations. To better guide DL-ASL training, we incorporated prior knowledge about ASL MRI: the structural similarity between ASL CBF map and grey matter probability map. A relatively large sample data were used to train the model which was subsequently applied to a new set of data for testing. Experimental results showed that DL-ASL achieved state-of-the-art denoising performance for ASL MRI as compared to current routine methods in terms of higher SNR, keeping CBF quantification quality while shorten the acquisition time by 75%, and automatic partial volume correction.
Contrasting Web Robot and Human Behaviors with Network Models
Venue: arXiv cs.SI 2018
Year: 2018

The web graph is a commonly-used network representation of the hyperlink structure of a website. A network of similar structure to the web graph, which we call the session graph has properties that reflect the browsing habits of the agents in the web server logs. In this paper, we apply session graphs to compare the activity of humans against web robots or crawlers. Understanding these properties will enable us to improve models of HTTP traffic, which can be used to predict and generate realistic traffic for testing and improving web server efficiency, as well as devising new caching algorithms. We apply large-scale network properties, such as the connectivity and degree distribution of human and Web robot session graphs in order to identify characteristics of the traffic which would be useful for modeling web traffic and improving cache performance. We find that the empirical degree distributions of session graphs for human and robot requests on one Web server are best fit by different theoretical distributions, indicating at a difference in the processes which generate the traffic.
Object-based reasoning in VQA
Venue: arXiv cs.CV 2018
Year: 2018

Visual Question Answering (VQA) is a novel problem domain where multi-modal inputs must be processed in order to solve the task given in the form of a natural language. As the solutions inherently require to combine visual and natural language processing with abstract reasoning, the problem is considered as AI-complete. Recent advances indicate that using high-level, abstract facts extracted from the inputs might facilitate reasoning. Following that direction we decided to develop a solution combining state-of-the-art object detection and reasoning modules. The results, achieved on the well-balanced CLEVR dataset, confirm the promises and show significant, few percent improvements of accuracy on the complex "counting" task.
On Psychoacoustically Weighted Cost Functions Towards Resource-Efficient Deep Neural Networks for Speech Denoising
Venue: arXiv cs.SD 2018
Year: 2018

We present a psychoacoustically enhanced cost function to balance network complexity and perceptual performance of deep neural networks for speech denoising. While training the network, we utilize perceptual weights added to the ordinary mean-squared error to emphasize contribution from frequency bins which are most audible while ignoring error from inaudible bins. To generate the weights, we employ psychoacoustic models to compute the global masking threshold from the clean speech spectra. We then evaluate the speech denoising performance of our perceptually guided neural network by using both objective and perceptual sound quality metrics, testing on various network structures ranging from shallow and narrow ones to deep and wide ones. The experimental results showcase our method as a valid approach for infusing perceptual significance to deep neural network operations. In particular, the more perceptually sensible enhancement in performance seen by simple neural network topologies proves that the proposed method can lead to resource-efficient speech denoising implementations in small devices without degrading the perceived signal fidelity.
Discrete Autoencoders for Sequence Models
Venue: arXiv cs.LG 2018
Year: 2018

Recurrent models for sequences have been recently successful at many tasks, especially for language modeling and machine translation. Nevertheless, it remains challenging to extract good representations from these models. For instance, even though language has a clear hierarchical structure going from characters through words to sentences, it is not apparent in current language models. We propose to improve the representation in sequence models by augmenting current approaches with an autoencoder that is forced to compress the sequence through an intermediate discrete latent space. In order to propagate gradients though this discrete representation we introduce an improved semantic hashing technique. We show that this technique performs well on a newly proposed quantitative efficiency measure. We also analyze latent codes produced by the model showing how they correspond to words and phrases. Finally, we present an application of the autoencoder-augmented model to generating diverse translations.
The Intriguing Properties of Model Explanations
Venue: arXiv cs.LG 2018
Year: 2018

Linear approximations to the decision boundary of a complex model have become one of the most popular tools for interpreting predictions. In this paper, we study such linear explanations produced either post-hoc by a few recent methods or generated along with predictions with contextual explanation networks (CENs). We focus on two questions: (i) whether linear explanations are always consistent or can be misleading, and (ii) when integrated into the prediction process, whether and how explanations affect the performance of the model. Our analysis sheds more light on certain properties of explanations produced by different methods and suggests that learning models that explain and predict jointly is often advantageous.
Open3D: A Modern Library for 3D Data Processing
Venue: arXiv cs.CV 2018
Year: 2018

Open3D is an open-source library that supports rapid development of software that deals with 3D data. The Open3D frontend exposes a set of carefully selected data structures and algorithms in both C++ and Python. The backend is highly optimized and is set up for parallelization. Open3D was developed from a clean slate with a small and carefully considered set of dependencies. It can be set up on different platforms and compiled from source with minimal effort. The code is clean, consistently styled, and maintained via a clear code review mechanism. Open3D has been used in a number of published research projects and is actively deployed in the cloud. We welcome contributions from the open-source community.
Optical Network Models and their Application to Software-Defined Network Management
Venue: arXiv cs.NI 2018
Year: 2018

Software-defined networking is finding its way into optical networks. Here, it promises a simplification and unification of network management for optical networks allowing automation of operational tasks despite the highly diverse and vendor-specific commercial systems and the complexity and analog nature of optical transmission. A fundamental component for software-defined optical networking are common abstractions and interfaces. Currently, a number of models for optical networks are available. They all claim to provide open and vendor agnostic management of optical equipment. In this work, we survey and compare the most important models and propose an intent interface for creating virtual topologies that is integrated in the existing model ecosystem.
Towards Efficient Dynamic Virtual Network Embedding Strategy for Cloud IoT Networks
Venue: arXiv cs.NI 2018
Year: 2018

Network Virtualization is one of the most promising technologies for future networking and considered as a critical IT resource that connects distributed, virtualized Cloud Computing services and different components such as storage, servers and application. Network Virtualization allows multiple virtual networks to coexist on same shared physical infrastructure simultaneously. One of the crucial keys in Network Virtualization is Virtual Network Embedding, which provides a method to allocate physical substrate resources to virtual network requests. In this paper, we investigate Virtual Network Embedding strategies and related issues for resource allocation of an Internet Provider(InP) to efficiently embed virtual networks that are requested by Virtual Network Operators(VNOs) who share the same infrastructure provided by the InP. In order to achieve that goal, we design a heuristic Virtual Network Embedding algorithm that simultaneously embeds virtual nodes and virtual links of each virtual network request onto physic infrastructure. Through extensive simulations, we demonstrate that our proposed scheme improves significantly the performance of Virtual Network Embedding by enhancing the long-term average revenue as well as acceptance ratio and resource utilization of virtual network requests compared to prior algorithms.
Field normalization of scientometric indicators
Venue: arXiv cs.DL 2018
Year: 2018

When scientometric indicators are used to compare research units active in different scientific fields, there often is a need to make corrections for differences between fields, for instance differences in publication, collaboration, and citation practices. Field-normalized indicators aim to make such corrections. The design of these indicators is a significant challenge. We discuss the main issues in the design of field-normalized indicators, and we present an overview of different approaches that have been developed for dealing with the problem of field normalization. We also discuss how field-normalized indicators can be evaluated, and we consider the sensitivity of scientometric analyses to the choice of a field normalization approach.
Revisiting Fast Practical Byzantine Fault Tolerance: Thelma, Velma, and Zelma
Venue: arXiv cs.DC 2018
Year: 2018

In a previous note (arXiv:1712.01367 [cs.DC]) , we observed a safety violation in Zyzzyva and a liveness violation in FaB. In this manuscript, we sketch fixes to both. The same view-change core is applied in the two schemes, and additionally, applied to combine them and create a single, enhanced scheme that has the benefits of both approaches.
Performance of Media-based Modulation in Multi-user Networks
Venue: arXiv cs.IT 2018
Year: 2018

High spectral efficiency and low power consumption are the most challenging requirements of 5G networks since the number of devices are increased drastically. Media-based modulation (MBM) is a promising scheme in order to achieve these requirements. In this paper, the spectral efficiency of MBM scheme in single- and multi-user networks is studied. To find the spectral efficiency, information theoretical methods are used and tight lower- and upper-bounds are derived for the achievable rate. The performance of the system is studied for both correlated and uncorrelated constellation diagrams. It is shown that the entries of the constellation diagram for the sum rate region of multi-user case are always correlated. The characteristic of covariance matrix is derived and its impact on performance assessed.
Trajectory-based Radical Analysis Network for Online Handwritten Chinese Character Recognition
Venue: arXiv cs.CV 2018
Year: 2018

Recently, great progress has been made for online handwritten Chinese character recognition due to the emergence of deep learning techniques. However, previous research mostly treated each Chinese character as one class without explicitly considering its inherent structure, namely the radical components with complicated geometry. In this study, we propose a novel trajectory-based radical analysis network (TRAN) to firstly identify radicals and analyze two-dimensional structures among radicals simultaneously, then recognize Chinese characters by generating captions of them based on the analysis of their internal radicals. The proposed TRAN employs recurrent neural networks (RNNs) as both an encoder and a decoder. The RNN encoder makes full use of online information by directly transforming handwriting trajectory into high-level features. The RNN decoder aims at generating the caption by detecting radicals and spatial structures through an attention model. The manner of treating a Chinese character as a two-dimensional composition of radicals can reduce the size of vocabulary and enable TRAN to possess the capability of recognizing unseen Chinese character classes, only if the corresponding radicals have been seen. Evaluated on CASIA-OLHWDB database, the proposed approach significantly outperforms the state-of-the-art whole-character modeling approach with a relative character error rate (CER) reduction of 10%. Meanwhile, for the case of recognition of 500 unseen Chinese characters, TRAN can achieve a character accuracy of about 60% while the traditional whole-character method has no capability to handle them.
Spherical CNNs
Venue: arXiv cs.LG 2018
Year: 2018

Convolutional Neural Networks (CNNs) have become the method of choice for learning problems involving 2D planar images. However, a number of problems of recent interest have created a demand for models that can analyze spherical images. Examples include omnidirectional vision for drones, robots, and autonomous cars, molecular regression problems, and global weather and climate modelling. A naive application of convolutional networks to a planar projection of the spherical signal is destined to fail, because the space-varying distortions introduced by such a projection will make translational weight sharing ineffective. In this paper we introduce the building blocks for constructing spherical CNNs. We propose a definition for the spherical cross-correlation that is both expressive and rotation-equivariant. The spherical correlation satisfies a generalized Fourier theorem, which allows us to compute it efficiently using a generalized (non-commutative) Fast Fourier Transform (FFT) algorithm. We demonstrate the computational efficiency, numerical accuracy, and effectiveness of spherical CNNs applied to 3D model recognition and atomization energy regression.
Analysis of the Continued Logarithm Algorithm
Venue: arXiv cs.DM 2018
Year: 2018

The Continued Logarithm Algorithm - CL for short- introduced by Gosper in 1978 computes the gcd of two integers; it seems very efficient, as it only performs shifts and subtractions. Shallit has studied its worst-case complexity in 2016 and showed it to be linear. We here perform the average-case analysis of the algorithm: we study its main parameters (number of iterations, total number of shifts) and obtain precise asymptotics for their mean values. Our 'dynamical' analysis involves the dynamical system underlying the algorithm, that produces continued fraction expansions whose quotients are powers of 2. Even though this CL system has already been studied by Chan (around 2005), the presence of powers of 2 in the quotients ingrains into the central parameters a dyadic flavour that cannot be grasped solely by studying the CL system. We thus introduce a dyadic component and deal with a two-component system. With this new mixed system at hand, we then provide a complete average-case analysis of the CL algorithm, with explicit constants.
EMME: a formal tool for ECMAScript Memory Model Evaluation
Venue: arXiv cs.LO 2018
Year: 2018

Nearly all web-based interfaces are written in JavaScript. Given its prevalence, the support for high performance JavaScript code is crucial. The ECMA Technical Committee 39 (TC39) has recently extended the ECMAScript language (i.e., JavaScript) to support shared memory accesses between different threads. The extension is given in terms of a natural language memory model specification. In this paper we describe a formal approach for validating both the memory model and its implementations in various JavaScript engines. We first introduce a formal version of the memory model and report results on checking the model for consistency and other properties. We then introduce our tool, EMME, built on top of the Alloy analyzer, which leverages the model to generate all possible valid executions of a given JavaScript program. Finally, we report results using EMME together with small test programs to analyze industrial JavaScript engines. We show that EMME can find bugs as well as missed opportunities for optimization.
Sometimes You Want to Go Where Everybody Knows your Name
Venue: arXiv cs.LG 2018
Year: 2018

We introduce a new metric for measuring how well a model personalizes to a user's specific preferences. We define personalization as a weighting between performance on user specific data and performance on a more general global dataset that represents many different users. This global term serves as a form of regularization that forces us to not overfit to individual users who have small amounts of data. In order to protect user privacy, we add the constraint that we may not centralize or share user data. We also contribute a simple experiment in which we simulate classifying sentiment for users with very distinct vocabularies. This experiment functions as an example of the tension between doing well globally on all users, and doing well on any specific individual user. It also provides a concrete example of how to employ our new metric to help reason about and resolve this tension. We hope this work can help frame and ground future work into personalization.
Enhanced Max-Min SINR for Uplink Cell-Free Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we consider the max-min signal-to-interference plus noise ratio (SINR) problem for the uplink transmission of a cell-free Massive multiple-input multiple-output (MIMO) system. Assuming that the central processing unit (CPU) and the users exploit only the knowledge of the channel statistics, we first derive a closed-form expression for uplink rate. In particular, we enhance (or maximize) user fairness by solving the max-min optimization problem for user rate, by power allocation and choice of receiver coefficients, where the minimum uplink rate of the users is maximized with available transmit power at the particular user. Based on the derived closed-form expression for the uplink rate, we formulate the original user max-min problem to design the optimal receiver coefficients and user power allocations. However, this max-min SINR problem is not jointly convex in terms of design variables and therefore we decompose this original problem into two sub-problems, namely, receiver coefficient design and user power allocation. By iteratively solving these sub-problems, we develop an iterative algorithm to obtain the optimal receiver coefficient and user power allocations. In particular, the receiver coefficients design for a fixed user power allocation is formulated as generalized eigenvalue problem whereas a geometric programming (GP) approach is utilized to solve the power allocation problem for a given set of receiver coefficients. Numerical results confirm a three-fold increase in system rate over existing schemes in the literature.
The Multi Vehicle Stereo Event Camera Dataset: An Event Camera Dataset for 3D Perception
Venue: arXiv cs.RO 2018
Year: 2018

Event based cameras are a new passive sensing modality with a number of benefits over traditional cameras, including extremely low latency, asynchronous data acquisition, high dynamic range and very low power consumption. There has been a lot of recent interest and development in applying algorithms to use the events to perform a variety of 3D perception tasks, such as feature tracking, visual odometry, and stereo depth estimation. However, there currently lacks the wealth of labeled data that exists for traditional cameras to be used for both testing and development. In this paper, we present a large dataset with a synchronized stereo pair event based camera system, carried on a handheld rig, flown by a hexacopter, driven on top of a car and mounted on a motorcycle, in a variety of different illumination levels and environments. From each camera, we provide the event stream, grayscale images and IMU readings. In addition, we utilize a combination of IMU, a rigidly mounted lidar system, indoor and outdoor motion capture and GPS to provide accurate pose and depth images for each camera at up to 100Hz. For comparison, we also provide synchronized grayscale images and IMU readings from a frame based stereo camera system.