OpenRaiser/Intern-Atlas huggingface dataset:
An Online Mechanism for Ridesharing in Autonomous Mobility-on-Demand Systems
Venue: arXiv cs.AI 2017
Year: 2017

With proper management, Autonomous Mobility-on-Demand (AMoD) systems have great potential to satisfy the transport demands of urban populations by providing safe, convenient, and affordable ridesharing services. Meanwhile, such systems can substantially decrease private car ownership and use, and thus significantly reduce traffic congestion, energy consumption, and carbon emissions. To achieve this objective, an AMoD system requires private information about the demand from passengers. However, due to self-interestedness, passengers are unlikely to cooperate with the service providers in this regard. Therefore, an online mechanism is desirable if it incentivizes passengers to truthfully report their actual demand. For the purpose of promoting ridesharing, we hereby introduce a posted-price, integrated online ridesharing mechanism (IORS) that satisfies desirable properties such as ex-post incentive compatibility, individual rationality, and budget-balance. Numerical results indicate the competitiveness of IORS compared with two benchmarks, namely the optimal assignment and an offline, auction-based mechanism.
Distributed TensorFlow with MPI
Venue: arXiv cs.DC 2017
Year: 2017

Machine Learning and Data Mining (MLDM) algorithms are becoming increasingly important in analyzing large volume of data generated by simulations, experiments and mobile devices. With increasing data volume, distributed memory systems (such as tightly connected supercomputers or cloud computing systems) are becoming important in designing in-memory and massively parallel MLDM algorithms. Yet, the majority of open source MLDM software is limited to sequential execution with a few supporting multi-core/many-core execution. In this paper, we extend recently proposed Google TensorFlow for execution on large scale clusters using Message Passing Interface (MPI). Our approach requires minimal changes to the TensorFlow runtime -- making the proposed implementation generic and readily usable to increasingly large users of TensorFlow. We evaluate our implementation using an InfiniBand cluster and several well knowndatasets. Our evaluation indicates the efficiency of our proposed implementation.
Scheduling meets n-fold Integer Programming
Venue: arXiv cs.DS 2017
Year: 2017

Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NP-hard cases, but relatively little is known about exact solutions when some part of the input is a fixed parameter. In 2014, Mnich and Wiese initiated a systematic study in this direction. In this paper we continue this study and show that several additional cases of fundamental scheduling problems are fixed parameter tractable for some natural parameters. Our main tool is n-fold integer programming, a recent variable dimension technique which we believe to be highly relevant for the parameterized complexity community. This paper serves to showcase and highlight this technique. Specifically, we show the following four scheduling problems to be fixed-parameter tractable, where p max is the maximum processing time of a job and w max is the maximum weight of a job: - Makespan minimization on uniformly related machines $(Q||C_{max} )$ parameterized by $p_{max}$, - Makespan minimization on unrelated machines $(R||C_{max} )$ parameterized by $p_{max}$ and the number of kinds of machines, - Sum of weighted completion times minimization on unrelated machines $(R|| \sum w_i C_i )$ parameterized by $p_{max} + w_{max}$ and the number of kinds of machines, - The same problem, $(R|| \sum w_i C_i),$ parameterized by the number of distinct job times and the number of machines.
Exploring Context with Deep Structured models for Semantic Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

State-of-the-art semantic image segmentation methods are mostly based on training deep convolutional neural networks (CNNs). In this work, we proffer to improve semantic segmentation with the use of contextual information. In particular, we explore `patch-patch' context and `patch-background' context in deep CNNs. We formulate deep structured models by combining CNNs and Conditional Random Fields (CRFs) for learning the patch-patch context between image regions. Specifically, we formulate CNN-based pairwise potential functions to capture semantic correlations between neighboring patches. Efficient piecewise training of the proposed deep structured model is then applied in order to avoid repeated expensive CRF inference during the course of back propagation. For capturing the patch-background context, we show that a network design with traditional multi-scale image inputs and sliding pyramid pooling is very effective for improving performance. We perform comprehensive evaluation of the proposed method. We achieve new state-of-the-art performance on a number of challenging semantic segmentation datasets including $NYUDv2$, $PASCAL$-$VOC2012$, $Cityscapes$, $PASCAL$-$Context$, $SUN$-$RGBD$, $SIFT$-$flow$, and $KITTI$ datasets. Particularly, we report an intersection-over-union score of $77.8$ on the $PASCAL$-$VOC2012$ dataset.
Security, Privacy, and Access Control in Information-Centric Networking: A Survey
Venue: arXiv cs.NI 2017
Year: 2017

Information-Centric Networking (ICN) is a new networking paradigm, which replaces the widely used host-centric networking paradigm in communication networks (e.g., Internet, mobile ad hoc networks) with an information-centric paradigm, which prioritizes the delivery of named content, oblivious of the contents origin. Content and client security are more intrinsic in the ICN paradigm versus the current host centric paradigm where they have been instrumented as an after thought. By design, the ICN paradigm inherently supports several security and privacy features, such as provenance and identity privacy, which are still not effectively available in the host-centric paradigm. However, given its nascency, the ICN paradigm has several open security and privacy concerns, some that existed in the old paradigm, and some new and unique. In this article, we survey the existing literature in security and privacy research sub-space in ICN. More specifically, we explore three broad areas: security threats, privacy risks, and access control enforcement mechanisms. We present the underlying principle of the existing works, discuss the drawbacks of the proposed approaches, and explore potential future research directions. In the broad area of security, we review attack scenarios, such as denial of service, cache pollution, and content poisoning. In the broad area of privacy, we discuss user privacy and anonymity, name and signature privacy, and content privacy. ICN's feature of ubiquitous caching introduces a major challenge for access control enforcement that requires special attention. In this broad area, we review existing access control mechanisms including encryption-based, attribute-based, session-based, and proxy re-encryption-based access control schemes. We conclude the survey with lessons learned and scope for future work.
KLMAT: A Kernel Least Mean Absolute Third Algorithm
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, a kernel least mean absolute third (KLMAT) algorithm is developed for adaptive prediction. Combining the benefits of the kernel method and the least mean absolute third (LMAT) algorithm, the proposed KLMAT algorithm performs robustly against noise with different probability densities. To further enhance the convergence rate of the KLMAT algorithm, a variable step-size version (VSS-KLMAT algorithm) is proposed based on a Lorentzian function. Moreover, the stability and convergence property of the proposed algorithms are analyzed. Simulation results in the context of time series prediction demonstrate that the effectiveness of proposed algorithms.
From virtual demonstration to real-world manipulation using LSTM and MDN
Venue: arXiv cs.RO 2017
Year: 2017

Robots assisting the disabled or elderly must perform complex manipulation tasks and must adapt to the home environment and preferences of their user. Learning from demonstration is a promising choice, that would allow the non-technical user to teach the robot different tasks. However, collecting demonstrations in the home environment of a disabled user is time consuming, disruptive to the comfort of the user, and presents safety challenges. It would be desirable to perform the demonstrations in a virtual environment. In this paper we describe a solution to the challenging problem of behavior transfer from virtual demonstration to a physical robot. The virtual demonstrations are used to train a deep neural network based controller, which is using a Long Short Term Memory (LSTM) recurrent neural network to generate trajectories. The training process uses a Mixture Density Network (MDN) to calculate an error signal suitable for the multimodal nature of demonstrations. The controller learned in the virtual environment is transferred to a physical robot (a Rethink Robotics Baxter). An off-the-shelf vision component is used to substitute for geometric knowledge available in the simulation and an inverse kinematics module is used to allow the Baxter to enact the trajectory. Our experimental studies validate the three contributions of the paper: (1) the controller learned from virtual demonstrations can be used to successfully perform the manipulation tasks on a physical robot, (2) the LSTM+MDN architectural choice outperforms other choices, such as the use of feedforward networks and mean-squared error based training signals and (3) allowing imperfect demonstrations in the training set also allows the controller to learn how to correct its manipulation mistakes.
Pufferfish Privacy Mechanisms for Correlated Data
Venue: arXiv cs.LG 2017
Year: 2017

Many modern databases include personal and sensitive correlated data, such as private information on users connected together in a social network, and measurements of physical activity of single subjects across time. However, differential privacy, the current gold standard in data privacy, does not adequately address privacy issues in this kind of data. This work looks at a recent generalization of differential privacy, called Pufferfish, that can be used to address privacy in correlated data. The main challenge in applying Pufferfish is a lack of suitable mechanisms. We provide the first mechanism -- the Wasserstein Mechanism -- which applies to any general Pufferfish framework. Since this mechanism may be computationally inefficient, we provide an additional mechanism that applies to some practical cases such as physical activity measurements across time, and is computationally efficient. Our experimental evaluations indicate that this mechanism provides privacy and utility for synthetic as well as real data in two separate domains.
Investigation of event-based memory surfaces for high-speed tracking, unsupervised feature extraction and object recognition
Venue: arXiv cs.NE 2017
Year: 2017

In this paper we compare event-based decaying and time based-decaying memory surfaces for high-speed eventbased tracking, feature extraction, and object classification using an event-based camera. The high-speed recognition task involves detecting and classifying model airplanes that are dropped free-hand close to the camera lens so as to generate a challenging dataset exhibiting significant variance in target velocity. This variance motivated the investigation of event-based decaying memory surfaces in comparison to time-based decaying memory surfaces to capture the temporal aspect of the event-based data. These surfaces are then used to perform unsupervised feature extraction, tracking and recognition. In order to generate the memory surfaces, event binning, linearly decaying kernels, and exponentially decaying kernels were investigated with exponentially decaying kernels found to perform best. Event-based decaying memory surfaces were found to outperform time-based decaying memory surfaces in recognition especially when invariance to target velocity was made a requirement. A range of network and receptive field sizes were investigated. The system achieves 98.75% recognition accuracy within 156 milliseconds of an airplane entering the field of view, using only twenty-five event-based feature extracting neurons in series with a linear classifier. By comparing the linear classifier results to an ELM classifier, we find that a small number of event-based feature extractors can effectively project the complex spatio-temporal event patterns of the dataset to an almost linearly separable representation in feature space.
Time-optimal Coordination of Mobile Robots along Specified Paths
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, we address the problem of time-optimal coordination of mobile robots under kinodynamic constraints along specified paths. We propose a novel approach based on time discretization that leads to a mixed-integer linear programming (MILP) formulation. This problem can be solved using general-purpose MILP solvers in a reasonable time, resulting in a resolution-optimal solution. Moreover, unlike previous work found in the literature, our formulation allows an exact linear modeling (up to the discretization resolution) of second-order dynamic constraints. Extensive simulations are performed to demonstrate the effectiveness of our approach.
Optimal Throughput for Covert Communication Over a Classical-Quantum Channel
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the problem of communication over a memoryless classical-quantum wiretap channel subject to the constraint that the eavesdropper on the channel should not be able to learn whether the legitimate parties are using the channel to communicate or not. Specifically, the relative entropy between the output quantum states at the eavesdropper when a codeword is transmitted and when no input is provided must be sufficiently small. Extending earlier works, this paper proves the "square-root law" for a broad class of classical-quantum channels: the maximum amount of information that can be reliably and covertly transmitted over $n$ uses of such a channel scales like $\sqrt{n}$. The scaling constant is also determined.
Modeling and Optimal Operation of Distributed Battery Storage in Low Voltage Grids
Venue: arXiv cs.SY 2017
Year: 2017

Due to high power in-feed from photovoltaics, it can be expected that more battery systems will be installed in the distribution grid in near future to mitigate voltage violations and thermal line and transformer overloading. In this paper, we present a two-stage centralized model predictive control scheme for distributed battery storage that consists of a scheduling entity and a real-time control entity. To guarantee secure grid operation, we solve a robust multi-period optimal power flow (OPF) for the scheduling stage that minimizes battery degradation and maximizes photovoltaic utilization subject to grid constraints. The real-time controller solves a real-time OPF taking into account storage allocation profiles from the scheduler, a detailed battery model, and real-time measurements. To reduce the computational complexity of the controllers, we present a linearized OPF that approximates the nonlinear AC-OPF into a linear programming problem. Through a case study, we show, for two different battery technologies, that we can substantially reduce battery degradation when we incorporate a battery degradation model. A further finding is that we can reduce battery losses by 30% by using the detailed battery model in the real-time control stage.
Risk-Averse $ω$-regular Markov Decision Process Control
Venue: arXiv cs.SY 2017
Year: 2017

Many control problems in environments that can be modeled as Markov decision processes (MDPs) concern infinite-time horizon specifications. The classical aim in this context is to compute a control policy that maximizes the probability of satisfying the specification. In many scenarios, there is however a non-zero probability of failure in every step of the system's execution. For infinite-time horizon specifications, this implies that the specification is violated with probability 1 in the long run no matter what policy is chosen, which prevents previous policy computation methods from being useful in these scenarios. In this paper, we introduce a new optimization criterion for MDP policies that captures the task of working towards the satisfaction of some infinite-time horizon $ω$-regular specification. The new criterion is applicable to MDPs in which the violation of the specification cannot be avoided in the long run. We give an algorithm to compute policies that are optimal in this criterion and show that it captures the ideas of optimism and risk-averseness in MDP control: while the computed policies are optimistic in that a MDP run enters a failure state relatively late, they are risk-averse by always maximizing the probability to reach their respective next goal state. We give results on two robot control scenarios to validate the usability of risk-averse MDP policies.
On the Powerball Method for Optimization
Venue: arXiv cs.SY 2017
Year: 2017

We propose a new method to accelerate the convergence of optimization algorithms. This method simply adds a power coefficient $γ\in[0,1)$ to the gradient during optimization. We call this the Powerball method and analyze the convergence rate for the Powerball method for strongly convex functions. While theoretically the Powerball method is guaranteed to have a linear convergence rate in the same order of the gradient method, we show that empirically it significantly outperforms the gradient descent and Newton's method, especially during the initial iterations. We demonstrate that the Powerball method provides a $10$-fold speedup of the convergence of both gradient descent and L-BFGS on multiple real datasets.
Conditional Similarity Networks
Venue: arXiv cs.CV 2017
Year: 2017

What makes images similar? To measure the similarity between images, they are typically embedded in a feature-vector space, in which their distance preserve the relative dissimilarity. However, when learning such similarity embeddings the simplifying assumption is commonly made that images are only compared to one unique measure of similarity. A main reason for this is that contradicting notions of similarities cannot be captured in a single space. To address this shortcoming, we propose Conditional Similarity Networks (CSNs) that learn embeddings differentiated into semantically distinct subspaces that capture the different notions of similarities. CSNs jointly learn a disentangled embedding where features for different similarities are encoded in separate dimensions as well as masks that select and reweight relevant dimensions to induce a subspace that encodes a specific similarity notion. We show that our approach learns interpretable image representations with visually relevant semantic subspaces. Further, when evaluating on triplet questions from multiple similarity notions our model even outperforms the accuracy obtained by training individual specialized networks for each notion separately.
How NOT To Evaluate Your Dialogue System: An Empirical Study of Unsupervised Evaluation Metrics for Dialogue Response Generation
Venue: arXiv cs.CL 2017
Year: 2017

We investigate evaluation metrics for dialogue response generation systems where supervised labels, such as task completion, are not available. Recent works in response generation have adopted metrics from machine translation to compare a model's generated response to a single target response. We show that these metrics correlate very weakly with human judgements in the non-technical Twitter domain, and not at all in the technical Ubuntu domain. We provide quantitative and qualitative results highlighting specific weaknesses in existing metrics, and provide recommendations for future development of better automatic evaluation metrics for dialogue systems.
Submodular Variational Inference for Network Reconstruction
Venue: arXiv cs.LG 2017
Year: 2017

In real-world and online social networks, individuals receive and transmit information in real time. Cascading information transmissions (e.g. phone calls, text messages, social media posts) may be understood as a realization of a diffusion process operating on the network, and its branching path can be represented by a directed tree. The process only traverses and thus reveals a limited portion of the edges. The network reconstruction/inference problem is to infer the unrevealed connections. Most existing approaches derive a likelihood and attempt to find the network topology maximizing the likelihood, a problem that is highly intractable. In this paper, we focus on the network reconstruction problem for a broad class of real-world diffusion processes, exemplified by a network diffusion scheme called respondent-driven sampling (RDS). We prove that under realistic and general models of network diffusion, the posterior distribution of an observed RDS realization is a Bayesian log-submodular model.We then propose VINE (Variational Inference for Network rEconstruction), a novel, accurate, and computationally efficient variational inference algorithm, for the network reconstruction problem under this model. Crucially, we do not assume any particular probabilistic model for the underlying network. VINE recovers any connected graph with high accuracy as shown by our experimental results on real-life networks.
A Comparison of NOOP to Structural Domain-Theoretic Models of OOP
Venue: arXiv cs.PL 2017
Year: 2017

Mainstream object-oriented programming languages such as Java, C#, C++ and Scala are all almost entirely nominally-typed. NOOP is a recently developed domain-theoretic model of OOP that was designed to include full nominal information found in nominally-typed OOP. This paper compares NOOP to the most widely known domain-theoretic models of OOP, namely, the models developed by Cardelli and Cook, which were structurally-typed models. Leveraging the development of NOOP, the comparison presented in this paper provides a clear and precise mathematical account for the relation between nominal and structural OO type systems.
SMASH: Physics-guided Reconstruction of Collisions from Videos
Venue: arXiv cs.GR 2017
Year: 2017

Collision sequences are commonly used in games and entertainment to add drama and excitement. Authoring even two body collisions in the real world can be difficult, as one has to get timing and the object trajectories to be correctly synchronized. After tedious trial-and-error iterations, when objects can actually be made to collide, then they are difficult to capture in 3D. In contrast, synthetically generating plausible collisions is difficult as it requires adjusting different collision parameters (e.g., object mass ratio, coefficient of restitution, etc.) and appropriate initial parameters. We present SMASH to directly read off appropriate collision parameters directly from raw input video recordings. Technically we enable this by utilizing laws of rigid body collision to regularize the problem of lifting 2D trajectories to a physically valid 3D reconstruction of the collision. The reconstructed sequences can then be modified and combined to easily author novel and plausible collisions. We evaluate our system on a range of synthetic scenes and demonstrate the effectiveness of our method by accurately reconstructing several complex real world collision events.