OpenRaiser/Intern-Atlas huggingface dataset:
Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties
Venue: arXiv cs.GT 2017
Year: 2017

We study social choice rules under the utilitarian distortion framework, with an additional metric assumption on the agents' costs over the alternatives. In this approach, these costs are given by an underlying metric on the set of all agents plus alternatives. Social choice rules have access to only the ordinal preferences of agents but not the latent cardinal costs that induce them. Distortion is then defined as the ratio between the social cost (typically the sum of agent costs) of the alternative chosen by the mechanism at hand, and that of the optimal alternative chosen by an omniscient algorithm. The worst-case distortion of a social choice rule is, therefore, a measure of how close it always gets to the optimal alternative without any knowledge of the underlying costs. Under this model, it has been conjectured that Ranked Pairs, the well-known weighted-tournament rule, achieves a distortion of at most 3 [Anshelevich et al. 2015]. We disprove this conjecture by constructing a sequence of instances which shows that the worst-case distortion of Ranked Pairs is at least 5. Our lower bound on the worst case distortion of Ranked Pairs matches a previously known upper bound for the Copeland rule, proving that in the worst case, the simpler Copeland rule is at least as good as Ranked Pairs. And as long as we are limited to (weighted or unweighted) tournament rules, we demonstrate that randomization cannot help achieve an expected worst-case distortion of less than 3. Using the concept of approximate majorization within the distortion framework, we prove that Copeland and Randomized Dictatorship achieve low constant factor fairness-ratios (5 and 3 respectively), which is a considerable generalization of similar results for the sum of costs and single largest cost objectives. In addition to all of the above, we outline several interesting directions for further research in this space.
The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant
Venue: arXiv cs.CC 2017
Year: 2017

The problems of Permutation Routing via Matching and Token Swapping are reconfiguration problems on graphs. This paper is concerned with the complexity of those problems and a colored variant. For a given graph where each vertex has a unique token on it, those problems require to find a shortest way to modify a token placement into another by swapping tokens on adjacent vertices. While all pairs of tokens on a matching can be exchanged at once in Permutation Routing via Matching, Token Swapping allows only one pair of tokens can be swapped. In the colored version, vertices and tokens are colored and the goal is to relocate tokens so that each vertex has a token of the same color. We investigate the time complexity of several restricted cases of those problems and show when those problems become tractable and remain intractable.
Clipper: A Low-Latency Online Prediction Serving System
Venue: arXiv cs.DC 2017
Year: 2017

Machine learning is being deployed in a growing number of applications which demand real-time, accurate, and robust predictions under heavy query load. However, most machine learning frameworks and systems only address model training and not deployment. In this paper, we introduce Clipper, a general-purpose low-latency prediction serving system. Interposing between end-user applications and a wide range of machine learning frameworks, Clipper introduces a modular architecture to simplify model deployment across frameworks and applications. Furthermore, by introducing caching, batching, and adaptive model selection techniques, Clipper reduces prediction latency and improves prediction throughput, accuracy, and robustness without modifying the underlying machine learning frameworks. We evaluate Clipper on four common machine learning benchmark datasets and demonstrate its ability to meet the latency, accuracy, and throughput demands of online serving applications. Finally, we compare Clipper to the TensorFlow Serving system and demonstrate that we are able to achieve comparable throughput and latency while enabling model composition and online learning to improve accuracy and render more robust predictions.
Non-Redundant Spectral Dimensionality Reduction
Venue: arXiv cs.LG 2017
Year: 2017

Spectral dimensionality reduction algorithms are widely used in numerous domains, including for recognition, segmentation, tracking and visualization. However, despite their popularity, these algorithms suffer from a major limitation known as the "repeated Eigen-directions" phenomenon. That is, many of the embedding coordinates they produce typically capture the same direction along the data manifold. This leads to redundant and inefficient representations that do not reveal the true intrinsic dimensionality of the data. In this paper, we propose a general method for avoiding redundancy in spectral algorithms. Our approach relies on replacing the orthogonality constraints underlying those methods by unpredictability constraints. Specifically, we require that each embedding coordinate be unpredictable (in the statistical sense) from all previous ones. We prove that these constraints necessarily prevent redundancy, and provide a simple technique to incorporate them into existing methods. As we illustrate on challenging high-dimensional scenarios, our approach produces significantly more informative and compact representations, which improve visualization and classification tasks.
On kernel design for regularized LTI system identification
Venue: arXiv cs.SY 2017
Year: 2017

There are two key issues for the kernel-based regularization method: one is how to design a suitable kernel to embed in the kernel the prior knowledge of the LTI system to be identified, and the other one is how to tune the kernel such that the resulting regularized impulse response estimator can achieve a good bias-variance tradeoff. In this paper, we focus on the issue of kernel design. Depending on the type of the prior knowledge, we propose two methods to design kernels: one is from a machine learning perspective and the other one is from a system theory perspective. We also provide analysis results for both methods, which not only enhances our understanding for the existing kernels but also directs the design of new kernels.
Hybrid Learning of Optical Flow and Next Frame Prediction to Boost Optical Flow in the Wild
Venue: arXiv cs.CV 2017
Year: 2017

CNN-based optical flow estimation has attracted attention recently, mainly due to its impressively high frame rates. These networks perform well on synthetic datasets, but they are still far behind the classical methods in real-world videos. This is because there is no ground truth optical flow for training these networks on real data. In this paper, we boost CNN-based optical flow estimation in real scenes with the help of the freely available self-supervised task of next-frame prediction. To this end, we train the network in a hybrid way, providing it with a mixture of synthetic and real videos. With the help of a sample-variant multi-tasking architecture, the network is trained on different tasks depending on the availability of ground-truth. We also experiment with the prediction of "next-flow" instead of estimation of the current flow, which is intuitively closer to the task of next-frame prediction and yields favorable results. We demonstrate the improvement in optical flow estimation on the real-world KITTI benchmark. Additionally, we test the optical flow indirectly in an action classification scenario. As a side product of this work, we report significant improvements over state-of-the-art in the task of next-frame prediction.
Crossing Number for Graphs With Bounded Pathwidth
Venue: arXiv cs.CG 2017
Year: 2017

The crossing number is the smallest number of pairwise edge-crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios. Furthermore, up to now, general crossing number computations have never been successfully tackled using bounded width of graph decompositions, like treewidth or pathwidth. In this paper, we for the first time show that crossing number is tractable (even in linear time) for maximal graphs of bounded pathwidth~3. The technique also shows that the crossing number and the rectilinear (a.k.a. straight-line) crossing number are identical for this graph class, and that we require only an $O(n)\times O(n)$-grid to achieve such a drawing. Our techniques can further be extended to devise a 2-approximation for general graphs with pathwidth 3, and a $4w^3$-approximation for maximal graphs of pathwidth $w$. This is a constant approximation for bounded pathwidth graphs.
3D fully convolutional networks for subcortical segmentation in MRI: A large-scale study
Venue: arXiv cs.CV 2017
Year: 2017

This study investigates a 3D and fully convolutional neural network (CNN) for subcortical brain structure segmentation in MRI. 3D CNN architectures have been generally avoided due to their computational and memory requirements during inference. We address the problem via small kernels, allowing deeper architectures. We further model both local and global context by embedding intermediate-layer outputs in the final prediction, which encourages consistency between features extracted at different scales and embeds fine-grained information directly in the segmentation process. Our model is efficiently trained end-to-end on a graphics processing unit (GPU), in a single stage, exploiting the dense inference capabilities of fully CNNs. We performed comprehensive experiments over two publicly available datasets. First, we demonstrate a state-of-the-art performance on the ISBR dataset. Then, we report a {\em large-scale} multi-site evaluation over 1112 unregistered subject datasets acquired from 17 different sites (ABIDE dataset), with ages ranging from 7 to 64 years, showing that our method is robust to various acquisition protocols, demographics and clinical factors. Our method yielded segmentations that are highly consistent with a standard atlas-based approach, while running in a fraction of the time needed by atlas-based methods and avoiding registration/normalization steps. This makes it convenient for massive multi-site neuroanatomical imaging studies. To the best of our knowledge, our work is the first to study subcortical structure segmentation on such large-scale and heterogeneous data.
Deep Active Learning for Dialogue Generation
Venue: arXiv cs.CL 2017
Year: 2017

We propose an online, end-to-end, neural generative conversational model for open-domain dialogue. It is trained using a unique combination of offline two-phase supervised learning and online human-in-the-loop active learning. While most existing research proposes offline supervision or hand-crafted reward functions for online reinforcement, we devise a novel interactive learning mechanism based on hamming-diverse beam search for response generation and one-character user-feedback at each step. Experiments show that our model inherently promotes the generation of semantically relevant and interesting responses, and can be used to train agents with customized personas, moods and conversational styles.
Towards a cognitive MAC layer: Predicting the MAC-level performance in Dynamic WSN using Machine learning
Venue: arXiv cs.NI 2017
Year: 2017

Predictable network performance is key in many low-power wireless sensor network applications. In this paper, we use machine learning as an effective technique for real-time characterization of the communication performance as observed by the MAC layer. Our approach is data-driven and consists of three steps: extensive experiments for data collection, offline modeling and trace-driven performance evaluation. From our experiments and analysis, we find that a neural networks prediction model shows best performance.
Massive MIMO with Imperfect Channel Covariance Information
Venue: arXiv cs.IT 2017
Year: 2017

This work investigates the impact of imperfect statistical information in the uplink of massive MIMO systems. In particular, we first show why covariance information is needed and then propose two schemes for covariance matrix estimation. A lower bound on the spectral efficiency (SE) of any combining scheme is derived, under imperfect covariance knowledge, and a closed-form expression is computed for maximum-ratio combin- ing. We show that having covariance information is not critical, but that it is relatively easy to acquire it and to achieve SE close to the ideal case of having perfect statistical information.
IEDC: An Integrated Approach for Overlapping and Non-overlapping Community Detection
Venue: arXiv cs.SI 2017
Year: 2017

Community detection is a task of fundamental importance in social network analysis that can be used in a variety of knowledge-based domains. While there exist many works on community detection based on connectivity structures, they suffer from either considering the overlapping or non-overlapping communities. In this work, we propose a novel approach for general community detection through an integrated framework to extract the overlapping and non-overlapping community structures without assuming prior structural connectivity on networks. Our general framework is based on a primary node based criterion which consists of the internal association degree along with the external association degree. The evaluation of the proposed method is investigated through the extensive simulation experiments and several benchmark real network datasets. The experimental results show that the proposed method outperforms the earlier state-of-the-art algorithms based on the well-known evaluation criteria.
A Simple and Approximately Optimal Mechanism for a Buyer with Complements
Venue: arXiv cs.GT 2017
Year: 2017

We consider a revenue-maximizing seller with $m$ heterogeneous items and a single buyer whose valuation $v$ for the items may exhibit both substitutes (i.e., for some $S, T$, $v(S \cup T) < v(S) + v(T)$) and complements (i.e., for some $S, T$, $v(S \cup T) > v(S) + v(T)$). We show that the mechanism first proposed by Babaioff et al. [2014] - the better of selling the items separately and bundling them together - guarantees a $Θ(d)$ fraction of the optimal revenue, where $d$ is a measure on the degree of complementarity. Note that this is the first approximately optimal mechanism for a buyer whose valuation exhibits any kind of complementarity, and extends the work of Rubinstein and Weinberg [2015], which proved that the same simple mechanisms achieve a constant factor approximation when buyer valuations are subadditive, the most general class of complement-free valuations. Our proof is enabled by the recent duality framework developed in Cai et al. [2016], which we use to obtain a bound on the optimal revenue in this setting. Our main technical contributions are specialized to handle the intricacies of settings with complements, and include an algorithm for partitioning edges in a hypergraph. Even nailing down the right model and notion of "degree of complementarity" to obtain meaningful results is of interest, as the natural extensions of previous definitions provably fail.
Encapsulating models and approximate inference programs in probabilistic modules
Venue: arXiv cs.AI 2017
Year: 2017

This paper introduces the probabilistic module interface, which allows encapsulation of complex probabilistic models with latent variables alongside custom stochastic approximate inference machinery, and provides a platform-agnostic abstraction barrier separating the model internals from the host probabilistic inference system. The interface can be seen as a stochastic generalization of a standard simulation and density interface for probabilistic primitives. We show that sound approximate inference algorithms can be constructed for networks of probabilistic modules, and we demonstrate that the interface can be implemented using learned stochastic inference networks and MCMC and SMC approximate inference programs.
Privacy-Protecting Energy Management Unit through Model-Distribution Predictive Control
Venue: arXiv cs.IT 2017
Year: 2017

The roll-out of smart meters in electricity networks introduces risks for consumer privacy due to increased measurement frequency and granularity. Through various Non-Intrusive Load Monitoring techniques, consumer behavior may be inferred from their metering data. In this paper, we propose an energy management method that reduces energy cost and protects privacy through the minimization of information leakage. The method is based on a Model Predictive Controller that utilizes energy storage and local generation, and that predicts the effects of its actions on the statistics of the actual energy consumption of a consumer and that seen by the grid. Computationally, the method requires solving a Mixed-Integer Quadratic Program of manageable size whenever new meter readings are available. We simulate the controller on generated residential load profiles with different privacy costs in a two-tier time-of-use energy pricing environment. Results show that information leakage is effectively reduced at the expense of increased energy cost. The results also show that with the proposed controller the consumer load profile seen by the grid resembles a mixture between that obtained with Non-Intrusive Load Leveling and Lazy Stepping.
Neuromorphic Deep Learning Machines
Venue: arXiv cs.NE 2017
Year: 2017

An ongoing challenge in neuromorphic computing is to devise general and computationally efficient models of inference and learning which are compatible with the spatial and temporal constraints of the brain. One increasingly popular and successful approach is to take inspiration from inference and learning algorithms used in deep neural networks. However, the workhorse of deep learning, the gradient descent Back Propagation (BP) rule, often relies on the immediate availability of network-wide information stored with high-precision memory, and precise operations that are difficult to realize in neuromorphic hardware. Remarkably, recent work showed that exact backpropagated weights are not essential for learning deep representations. Random BP replaces feedback weights with random ones and encourages the network to adjust its feed-forward weights to learn pseudo-inverses of the (random) feedback weights. Building on these results, we demonstrate an event-driven random BP (eRBP) rule that uses an error-modulated synaptic plasticity for learning deep representations in neuromorphic computing hardware. The rule requires only one addition and two comparisons for each synaptic weight using a two-compartment leaky Integrate & Fire (I&F) neuron, making it very suitable for implementation in digital or mixed-signal neuromorphic hardware. Our results show that using eRBP, deep representations are rapidly learned, achieving nearly identical classification accuracies compared to artificial neural network simulations on GPUs, while being robust to neural and synaptic state quantizations during learning.
Canonical Duality Theory for Topology Optimization
Venue: arXiv cs.DM 2017
Year: 2017

This paper presents a canonical duality approach for solving a general topology optimization problem of nonlinear elastic structures. By using finite element method, this most challenging problem can be formulated as a mixed integer nonlinear programming problem (MINLP), i.e. for a given deformation, the first-level optimization is a typical linear constrained 0-1 programming problem, while for a given structure, the second-level optimization is a general nonlinear continuous minimization problem in computational nonlinear elasticity. It is discovered that for linear elastic structures, first-level optimization is a typical Knapsack problem, which is considered to be NP-complete in computer science. However, by using canonical duality theory, this well-known problem can be solved analytically to obtain exact integer solution. A perturbed canonical dual algorithm (CDT) is proposed and illustrated by benchmark problems in topology optimization. Numerical results show that the proposed CDT method produces desired optimal structure without any gray elements. The checkerboard issue in traditional methods is much reduced.
Improper Signaling in Two-Path Relay Channels
Venue: arXiv cs.IT 2017
Year: 2017

Inter-relay interference (IRI) challenges the operation of two-path relaying systems. Furthermore, the unavailability of the channel state information (CSI) at the source and the limited detection capabilities at the relays prevent neither eliminating the interference nor adopting joint detection at the relays nodes. Improper signaling is a powerful signaling scheme that has the capability to reduce the interference impact at the receiver side and improves the achievable rate performance. Therefore, improper signaling is adopted at both relays, which have access to the global CSI. Then, improper signal characteristics are designed to maximize the total end-to-end achievable rate at the relays. To this end, both the power and the circularity coefficient, a measure of the impropriety degree of the signal, are optimized at the relays. Although the optimization problem is not convex, optimal power allocation for both relays for a fixed circularity coefficient is obtained. Moreover, the circularity coefficient is tuned to maximize the rate for a given power allocation. Finally, a joint solution of the optimization problem is proposed using a coordinate descent method based on alternate optimization. The simulation results show that employing improper signaling improves the achievable rate at medium and high IRI.
Computability of Perpetual Exploration in Highly Dynamic Rings
Venue: arXiv cs.DC 2017
Year: 2017

We consider systems made of autonomous mobile robots evolving in highly dynamic discrete environment i.e., graphs where edges may appear and disappear unpredictably without any recurrence, stability, nor periodicity assumption. Robots are uniform (they execute the same algorithm), they are anonymous (they are devoid of any observable ID), they have no means allowing them to communicate together, they share no common sense of direction, and they have no global knowledge related to the size of the environment. However, each of them is endowed with persistent memory and is able to detect whether it stands alone at its current location. A highly dynamic environment is modeled by a graph such that its topology keeps continuously changing over time. In this paper, we consider only dynamic graphs in which nodes are anonymous, each of them is infinitely often reachable from any other one, and such that its underlying graph (i.e., the static graph made of the same set of nodes and that includes all edges that are present at least once over time) forms a ring of arbitrary size. In this context, we consider the fundamental problem of perpetual exploration: each node is required to be infinitely often visited by a robot. This paper analyzes the computability of this problem in (fully) synchronous settings, i.e., we study the deterministic solvability of the problem with respect to the number of robots. We provide three algorithms and two impossibility results that characterize, for any ring size, the necessary and sufficient number of robots to perform perpetual exploration of highly dynamic rings.