OpenRaiser/Intern-Atlas huggingface dataset:
When Hashing Met Matching: Efficient Spatio-Temporal Search for Ridesharing
Venue: arXiv cs.DS 2020
Year: 2020

Carpooling, or sharing a ride with other passengers, holds immense potential for urban transportation. Ridesharing platforms enable such sharing of rides using real-time data. Finding ride matches in real-time at urban scale is a difficult combinatorial optimization task and mostly heuristic approaches are applied. In this work, we mathematically model the problem as that of finding near-neighbors and devise a novel efficient spatio-temporal search algorithm based on the theory of locality sensitive hashing for Maximum Inner Product Search (MIPS). The proposed algorithm can find $k$ near-optimal potential matches for every ride from a pool of $n$ rides in time $O(n^{1 + ρ} (k + \log n) \log k)$ and space $O(n^{1 + ρ} \log k)$ for a small $ρ< 1$. Our algorithm can be extended in several useful and interesting ways increasing its practical appeal. Experiments with large NY yellow taxi trip datasets show that our algorithm consistently outperforms state-of-the-art heuristic methods thereby proving its practical applicability.
LensKit for Python: Next-Generation Software for Recommender System Experiments
Venue: arXiv cs.IR 2020
Year: 2020

LensKit is an open-source toolkit for building, researching, and learning about recommender systems. First released in 2010 as a Java framework, it has supported diverse published research, small-scale production deployments, and education in both MOOC and traditional classroom settings. In this paper, I present the next generation of the LensKit project, re-envisioning the original tool's objectives as flexible Python package for supporting recommender systems research and development. LensKit for Python (LKPY) enables researchers and students to build robust, flexible, and reproducible experiments that make use of the large and growing PyData and Scientific Python ecosystem, including scikit-learn, TensorFlow, and PyTorch. To that end, it provides classical collaborative filtering implementations, recommender system evaluation metrics, data preparation routines, and tools for efficiently batch running recommendation algorithms, all usable in any combination with each other or with other Python software. This paper describes the design goals, use cases, and capabilities of LKPY, contextualized in a reflection on the successes and failures of the original LensKit for Java software.
Flow length and size distributions in campus Internet traffic
Venue: arXiv cs.NI 2020
Year: 2020

The efficiency of flow-based networking mechanisms strongly depends on traffic characteristics and should thus be assessed using accurate flow models. For example, in the case of algorithms based on the distinction between elephant and mice flows, it is extremely important to ensure realistic flows' length and size distributions. Credible models or data are not available in literature. Numerous works contain only plots roughly presenting empirical distribution of selected flow parameters, without providing distribution mixture models or any reusable numerical data. This paper aims to fill that gap and provide reusable models of flow length and size derived from real traffic traces. Traces were collected at the Internet-facing interface of the university campus network and comprise four billion layer-4 flow (275 TB). These models can be used to assess a variety of flow-oriented solutions under the assumption of realistic conditions. Additionally, this paper provides a tutorial on constructing network flow models from traffic traces. The proposed methodology is universal and can be applied to traffic traces gathered in any network. We also provide an open source software framework to analyze flow traces and fit general mixture models to them.
Certifiably Globally Optimal Extrinsic Calibration from Per-Sensor Egomotion
Venue: arXiv cs.RO 2020
Year: 2020

We present a certifiably globally optimal algorithm for determining the extrinsic calibration between two sensors that are capable of producing independent egomotion estimates. This problem has been previously solved using a variety of techniques, including local optimization approaches that have no formal global optimality guarantees. We use a quadratic objective function to formulate calibration as a quadratically constrained quadratic program (QCQP). By leveraging recent advances in the optimization of QCQPs, we are able to use existing semidefinite program (SDP) solvers to obtain a certifiably global optimum via the Lagrangian dual problem. Our problem formulation can be globally optimized by existing general-purpose solvers in less than a second, regardless of the number of measurements available and the noise level. This enables a variety of robotic platforms to rapidly and robustly compute and certify a globally optimal set of calibration parameters without a prior estimate or operator intervention. We compare the performance of our approach with a local solver on extensive simulations and multiple real datasets. Finally, we present necessary observability conditions that connect our approach to recent theoretical results and analytically support the empirical performance of our system.
Jump to better conclusions: SCAN both left and right
Venue: arXiv cs.CL 2020
Year: 2020

Lake and Baroni (2018) recently introduced the SCAN data set, which consists of simple commands paired with action sequences and is intended to test the strong generalization abilities of recurrent sequence-to-sequence models. Their initial experiments suggested that such models may fail because they lack the ability to extract systematic rules. Here, we take a closer look at SCAN and show that it does not always capture the kind of generalization that it was designed for. To mitigate this we propose a complementary dataset, which requires mapping actions back to the original commands, called NACS. We show that models that do well on SCAN do not necessarily do well on NACS, and that NACS exhibits properties more closely aligned with realistic use-cases for sequence-to-sequence models.
Relevance in Structured Argumentation
Venue: arXiv cs.AI 2020
Year: 2020

We study properties related to relevance in non-monotonic consequence relations obtained by systems of structured argumentation. Relevance desiderata concern the robustness of a consequence relation under the addition of irrelevant information. For an account of what (ir)relevance amounts to we use syntactic and semantic considerations. Syntactic criteria have been proposed in the domain of relevance logic and were recently used in argumentation theory under the names of non-interference and crash-resistance. The basic idea is that the conclusions of a given argumentative theory should be robust under adding information that shares no propositional variables with the original database. Some semantic relevance criteria are known from non-monotonic logic. For instance, cautious monotony states that if we obtain certain conclusions from an argumentation theory, we may expect to still obtain the same conclusions if we add some of them to the given database. In this paper we investigate properties of structured argumentation systems that warrant relevance desiderata.
DASNet: Reducing Pixel-level Annotations for Instance and Semantic Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

Pixel-level annotation demands expensive human efforts and limits the performance of deep networks that usually benefits from more such training data. In this work we aim to achieve high quality instance and semantic segmentation results over a small set of pixel-level mask annotations and a large set of box annotations. The basic idea is exploring detection models to simplify the pixel-level supervised learning task and thus reduce the required amount of mask annotations. Our architecture, named DASNet, consists of three modules: detection, attention, and segmentation. The detection module detects all classes of objects, the attention module generates multi-scale class-specific features, and the segmentation module recovers the binary masks. Our method demonstrates substantially improved performance compared to existing semi-supervised approaches on PASCAL VOC 2012 dataset.
Simple Local Computation Algorithms for the General Lovasz Local Lemma
Venue: arXiv cs.DS 2020
Year: 2020

We consider the task of designing Local Computation Algorithms (LCA) for applications of the Lovász Local Lemma (LLL). LCA is a class of sublinear algorithms proposed by Rubinfeld et al.~\cite{Ronitt} that have received a lot of attention in recent years. The LLL is an existential, sufficient condition for a collection of sets to have non-empty intersection (in applications, often, each set comprises all objects having a certain property). The ground-breaking algorithm of Moser and Tardos~\cite{MT} made the LLL fully constructive, following earlier results by Beck~\cite{beck_lll} and Alon~\cite{alon_lll} giving algorithms under significantly stronger LLL-like conditions. LCAs under those stronger conditions were given in~\cite{Ronitt}, where it was asked if the Moser-Tardos algorithm can be used to design LCAs under the standard LLL condition. The main contribution of this paper is to answer this question affirmatively. In fact, our techniques yield LCAs for settings beyond the standard LLL condition.
Adversarial Defense via Data Dependent Activation Function and Total Variation Minimization
Venue: arXiv cs.LG 2020
Year: 2020

We improve the robustness of Deep Neural Net (DNN) to adversarial attacks by using an interpolating function as the output activation. This data-dependent activation remarkably improves both the generalization and robustness of DNN. In the CIFAR10 benchmark, we raise the robust accuracy of the adversarially trained ResNet20 from $\sim 46\%$ to $\sim 69\%$ under the state-of-the-art Iterative Fast Gradient Sign Method (IFGSM) based adversarial attack. When we combine this data-dependent activation with total variation minimization on adversarial images and training data augmentation, we achieve an improvement in robust accuracy by 38.9$\%$ for ResNet56 under the strongest IFGSM attack. Furthermore, We provide an intuitive explanation of our defense by analyzing the geometry of the feature space.
Domain Adaptation for Robot Predictive Maintenance Systems
Venue: arXiv cs.RO 2020
Year: 2020

Industrial robots play an increasingly important role in a growing number of fields. For example, robotics is used to increase productivity while reducing costs in various aspects of manufacturing. Since robots are often set up in production lines, the breakdown of a single robot has a negative impact on the entire process, in the worst case bringing the whole line to a halt until the issue is resolved, leading to substantial financial losses due to the unforeseen downtime. Therefore, predictive maintenance systems based on the internal signals of robots have gained attention as an essential component of robotics service offerings. The main shortcoming of existing predictive maintenance algorithms is that the extracted features typically differ significantly from the learnt model when the operation of the robot changes, incurring false alarms. In order to mitigate this problem, predictive maintenance algorithms require the model to be retrained with normal data of the new operation. In this paper, we propose a novel solution based on transfer learning to pass the knowledge of the trained model from one operation to another in order to prevent the need for retraining and to eliminate such false alarms. The deployment of the proposed unsupervised transfer learning algorithm on real-world datasets demonstrates that the algorithm can not only distinguish between operation and mechanical condition change, it further yields a sharper deviation from the trained model in case of a mechanical condition change and thus detects mechanical issues with higher confidence.
Envy-Free Classification
Venue: arXiv cs.LG 2020
Year: 2020

In classic fair division problems such as cake cutting and rent division, envy-freeness requires that each individual (weakly) prefer his allocation to anyone else's. On a conceptual level, we argue that envy-freeness also provides a compelling notion of fairness for classification tasks. Our technical focus is the generalizability of envy-free classification, i.e., understanding whether a classifier that is envy free on a sample would be almost envy free with respect to the underlying distribution with high probability. Our main result establishes that a small sample is sufficient to achieve such guarantees, when the classifier in question is a mixture of deterministic classifiers that belong to a family of low Natarajan dimension.
Transfinite Lyndon words
Venue: arXiv cs.FL 2020
Year: 2020

In this paper, we extend the notion of Lyndon word to transfinite words. We prove two main results. We first show that, given a transfinite word, there exists a unique factorization in Lyndon words that are densely non-increasing, a relaxation of the condition used in the case of finite words. In the annex, we prove that the factorization of a rational word has a special form and that it can be computed from a rational expression describing the word.
PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously
Venue: arXiv cs.CR 2020
Year: 2020

Today's blockchain designs suffer from a trilemma claiming that no blockchain system can simultaneously achieve decentralization, security, and performance scalability. For current blockchain systems, as more nodes join the network, the efficiency of the system (computation, communication, and storage) stays constant at best. A leading idea for enabling blockchains to scale efficiency is the notion of sharding: different subsets of nodes handle different portions of the blockchain, thereby reducing the load for each individual node. However, existing sharding proposals achieve efficiency scaling by compromising on trust - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of data. In this paper, we settle the trilemma by demonstrating a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: ``polynomially coded sharding'' scheme that achieves information-theoretic upper bounds on the efficiency of the storage, system throughput, as well as on trust, thus enabling a truly scalable system. We provide simulation results that numerically demonstrate the performance improvement over state of the arts, and the scalability of the PolyShard system. Finally, we discuss potential enhancements, and highlight practical considerations in building such a system.
MultiWOZ -- A Large-Scale Multi-Domain Wizard-of-Oz Dataset for Task-Oriented Dialogue Modelling
Venue: arXiv cs.CL 2020
Year: 2020

Even though machine learning has become the major scene in dialogue research community, the real breakthrough has been blocked by the scale of data available. To address this fundamental obstacle, we introduce the Multi-Domain Wizard-of-Oz dataset (MultiWOZ), a fully-labeled collection of human-human written conversations spanning over multiple domains and topics. At a size of $10$k dialogues, it is at least one order of magnitude larger than all previous annotated task-oriented corpora. The contribution of this work apart from the open-sourced dataset labelled with dialogue belief states and dialogue actions is two-fold: firstly, a detailed description of the data collection procedure along with a summary of data structure and analysis is provided. The proposed data-collection pipeline is entirely based on crowd-sourcing without the need of hiring professional annotators; secondly, a set of benchmark results of belief tracking, dialogue act and response generation is reported, which shows the usability of the data and sets a baseline for future studies.
Random Finite Set Theory and Centralized Control of Large Collaborative Swarms
Venue: arXiv cs.SY 2020
Year: 2020

Controlling large swarms of robotic agents presents many challenges including, but not limited to, computational complexity due to a large number of agents, uncertainty in the functionality of each agent in the swarm, and uncertainty in the swarm's configuration. This work generalizes the swarm state using Random Finite Set (RFS) theory and solves a centralized control problem with a Quasi-Newton optimization through the use of Model Predictive Control (MPC) to overcome the aforementioned challenges. This work uses the RFS formulation to control the distribution of agents assuming an unknown or unspecified number of agents. Computationally efficient solutions are also obtained via the MPC version of the Iterative Linear Quadratic Regulator (ILQR), a variant of Differential Dynamic Programming (DDP). Information divergence is used to define the distance between the swarm RFS and the desired swarm configuration through the use of the modified $L_2^2$ distance. Simulation results using MPC and ILQR show that the swarm intensity converges to the desired intensity. Additionally, the RFS control formulation is shown to be very flexible in terms of the number of agents in the swarm and configuration of the desired Gaussian mixtures. Lastly, the ILQR and the Gaussian Mixture Probability Hypothesis Density filter are used in conjunction to solve a spacecraft relative motion problem with imperfect information to show the viability of centralized RFS control for this real-world scenario.
Efficient Dialog Policy Learning via Positive Memory Retention
Venue: arXiv cs.AI 2020
Year: 2020

This paper is concerned with the training of recurrent neural networks as goal-oriented dialog agents using reinforcement learning. Training such agents with policy gradients typically requires a large amount of samples. However, the collection of the required data in form of conversations between chat-bots and human agents is time-consuming and expensive. To mitigate this problem, we describe an efficient policy gradient method using positive memory retention, which significantly increases the sample-efficiency. We show that our method is 10 times more sample-efficient than policy gradients in extensive experiments on a new synthetic number guessing game. Moreover, in a real-word visual object discovery game, the proposed method is twice as sample-efficient as policy gradients and shows state-of-the-art performance.
Towards Uniform Online Spherical Tessellations
Venue: arXiv cs.CG 2020
Year: 2020

The problem of uniformly placing N points onto a sphere finds applications in many areas. For example, points on the sphere correspond to unit quaternions as well as to the group of rotations SO(3) and the online version of generating uniform rotations (known as "incremental generation") plays a crucial role in a large number of engineering applications ranging from robotics and aeronautics to computer graphics. An online version of this problem was recently studied with respect to the gap ratio as a measure of uniformity. The first online algorithm of Chen et al. was upper-bounded by 5.99 and later improved to 3.69, which is achieved by considering a circumscribed dodecahedron followed by a recursive decomposition of each face. In this paper we provide a more efficient tessellation technique based on the regular icosahedron, which improves the upper-bound for the online version of this problem, decreasing it to approximately 2.84. Moreover, we show that the lower bound for the gap ratio of placing at least three points is the golden ratio, approx. 1.618, and for at least four points is no less than 1.726.
Probabilistic assessment of the impact of flexible loads under network tariffs in low voltage distribution networks
Venue: arXiv cs.SY 2020
Year: 2020

Given the historically static nature of low-voltage networks, distribution network companies do not possess tools for dealing with an increasingly variable demand due to the high penetration of distributed energy resources (DER). Within this context, this paper proposes a probabilistic framework for tariff design that minimises the impact of DER on network performance, stabilise network company revenue, and improves the equity of network costs allocation. To address the issue of the lack of customers' response, we also show how DER-specific tariffs can be complemented with an automated home energy management system (HEMS) that reduces peak demand while retaining the desired comfort level. The proposed framework comprises a nonparametric Bayesian model which statistically generates synthetic load and PV traces, a hot-water-use statistical model, a novel HEMS to schedule customers' controllable devices, and a probabilistic power-flow model. Test cases using both energy- and demand-based network tariffs show that flat tariffs with a peak demand component reduce the customers' cost, and alleviate network constraints. This demonstrates, first, the efficacy of the proposed tool for the development of tariffs that are beneficial for networks with a high DER penetration, and second, how customers' HEM systems can be part of the solution.
Fixed point combinators as fixed points of higher-order fixed point generators
Venue: arXiv cs.LO 2020
Year: 2020

Corrado Böhm once observed that if $Y$ is any fixed point combinator (fpc), then $Y(λyx.x(yx))$ is again fpc. He thus discovered the first "fpc generating scheme" -- a generic way to build new fpcs from old. Continuing this idea, define an $\textit{fpc generator}$ to be any sequence of terms $G_1,\dots,G_n$ such that \[ Y \in FPC \Rightarrow Y G_1 \cdots G_n \in FPC \] In this contribution, we take first steps in studying the structure of (weak) fpc generators. We isolate several robust classes of such generators, by examining their elementary properties like injectivity and (weak) constancy. We provide sufficient conditions for existence of fixed points of a given generator $(G_1,\cdots,G_n)$: an fpc $Y$ such that $Y = Y G_1 \cdots G_n$. We conjecture that weak constancy is a necessary condition for existence of such (higher-order) fixed points. This statement generalizes Statman's conjecture on non-existence of "double fpcs": fixed points of the generator $(G) = (λyx.x(yx))$ discovered by Böhm. Finally, we define and make a few observations about the monoid of (weak) fpc generators. This enables us to formulate new a conjecture about their structure.
Performance of Two-Hop Cooperative Cognitive Networks with an Energy Harvesting Relay
Venue: arXiv cs.IT 2020
Year: 2020

We consider an energy harvesting (EH) multi-antenna relay based cooperative cognitive radio network (CCRN), and investigate its outage and throughput performance with the peak-interference type of power control for both time-switching (TS) and power-splitting (PS) protocols. We assume that the relay uses maximum ratio combining and transmit antenna selection in the first and second hop respectively. Unlike other literature on this topic, we optimally combine the direct and relayed signals at the destination, and demonstrate that due to random nature of the channels and the power control used, there is considerable improvement in performance. We also analyze the performance of EH-CCRN with incremental relaying, and { analytically quantify the gain in throughput {over} EH-CCRN}. For the small number of antennas at the relay, throughput performance of EH-CCRN is actually inferior to one that uses the direct link without the relay, whereas that of the incremental scheme is always superior. We establish that there exist optimum values of EH parameters that result in maximum throughput with TS and PS EH protocols. We derive closed-form expressions for these in some special cases. Computer simulations are used to validate the derived expressions.