OpenRaiser/Intern-Atlas huggingface dataset:
Online neural connectivity estimation with ensemble stimulation
Venue: arXiv cs.LG 2020
Year: 2020

One of the primary goals of systems neuroscience is to relate the structure of neural circuits to their function, yet patterns of connectivity are difficult to establish when recording from large populations in behaving organisms. Many previous approaches have attempted to estimate functional connectivity between neurons using statistical modeling of observational data, but these approaches rely heavily on parametric assumptions and are purely correlational. Recently, however, holographic photostimulation techniques have made it possible to precisely target selected ensembles of neurons, offering the possibility of establishing direct causal links. Here, we propose a method based on noisy group testing that drastically increases the efficiency of this process in sparse networks. By stimulating small ensembles of neurons, we show that it is possible to recover binarized network connectivity with a number of tests that grows only logarithmically with population size under minimal statistical assumptions. Moreover, we prove that our approach, which reduces to an efficiently solvable convex optimization problem, can be related to Variational Bayesian inference on the binary connection weights, and we derive rigorous bounds on the posterior marginals. This allows us to extend our method to the streaming setting, where continuously updated posteriors allow for optional stopping, and we demonstrate the feasibility of inferring connectivity for networks of up to tens of thousands of neurons online. Finally, we show how our work can be theoretically linked to compressed sensing approaches, and compare results for connectivity inference in different settings.
Weakly Supervised 3D Object Detection from Point Clouds
Venue: arXiv cs.CV 2020
Year: 2020

A crucial task in scene understanding is 3D object detection, which aims to detect and localize the 3D bounding boxes of objects belonging to specific classes. Existing 3D object detectors heavily rely on annotated 3D bounding boxes during training, while these annotations could be expensive to obtain and only accessible in limited scenarios. Weakly supervised learning is a promising approach to reducing the annotation requirement, but existing weakly supervised object detectors are mostly for 2D detection rather than 3D. In this work, we propose VS3D, a framework for weakly supervised 3D object detection from point clouds without using any ground truth 3D bounding box for training. First, we introduce an unsupervised 3D proposal module that generates object proposals by leveraging normalized point cloud densities. Second, we present a cross-modal knowledge distillation strategy, where a convolutional neural network learns to predict the final results from the 3D object proposals by querying a teacher network pretrained on image datasets. Comprehensive experiments on the challenging KITTI dataset demonstrate the superior performance of our VS3D in diverse evaluation settings. The source code and pretrained models are publicly available at https://github.com/Zengyi-Qin/Weakly-Supervised-3D-Object-Detection.
Lane-Change Initiation and Planning Approach for Highly Automated Driving on Freeways
Venue: arXiv cs.RO 2020
Year: 2020

Quantifying and encoding occupants' preferences as an objective function for the tactical decision making of autonomous vehicles is a challenging task. This paper presents a low-complexity approach for lane-change initiation and planning to facilitate highly automated driving on freeways. Conditions under which human drivers find different manoeuvres desirable are learned from naturalistic driving data, eliminating the need for an engineered objective function and incorporation of expert knowledge in form of rules. Motion planning is formulated as a finite-horizon optimisation problem with safety constraints. It is shown that the decision model can replicate human drivers' discretionary lane-change decisions with up to 92% accuracy. Further proof of concept simulation of an overtaking manoeuvre is shown, whereby the actions of the simulated vehicle are logged while the dynamic environment evolves as per ground truth data recordings.
Toward Zero-Shot Unsupervised Image-to-Image Translation
Venue: arXiv cs.CV 2020
Year: 2020

Recent studies have shown remarkable success in unsupervised image-to-image translation. However, if there has no access to enough images in target classes, learning a mapping from source classes to the target classes always suffers from mode collapse, which limits the application of the existing methods. In this work, we propose a zero-shot unsupervised image-to-image translation framework to address this limitation, by associating categories with their side information like attributes. To generalize the translator to previous unseen classes, we introduce two strategies for exploiting the space spanned by the semantic attributes. Specifically, we propose to preserve semantic relations to the visual space and expand attribute space by utilizing attribute vectors of unseen classes, thus encourage the translator to explore the modes of unseen classes. Quantitative and qualitative results on different datasets demonstrate the effectiveness of our proposed approach. Moreover, we demonstrate that our framework can be applied to many tasks, such as zero-shot classification and fashion design.
Adoption and Effects of Software Engineering Best Practices in Machine Learning
Venue: arXiv cs.SE 2020
Year: 2020

The increasing reliance on applications with machine learning (ML) components calls for mature engineering techniques that ensure these are built in a robust and future-proof manner. We aim to empirically determine the state of the art in how teams develop, deploy and maintain software with ML components. We mined both academic and grey literature and identified 29 engineering best practices for ML applications. We conducted a survey among 313 practitioners to determine the degree of adoption for these practices and to validate their perceived effects. Using the survey responses, we quantified practice adoption, differentiated along demographic characteristics, such as geography or team size. We also tested correlations and investigated linear and non-linear relationships between practices and their perceived effect using various statistical models. Our findings indicate, for example, that larger teams tend to adopt more practices, and that traditional software engineering practices tend to have lower adoption than ML specific practices. Also, the statistical models can accurately predict perceived effects such as agility, software quality and traceability, from the degree of adoption for specific sets of practices. Combining practice adoption rates with practice importance, as revealed by statistical models, we identify practices that are important but have low adoption, as well as practices that are widely adopted but are less important for the effects we studied. Overall, our survey and the analysis of responses received provide a quantitative basis for assessment and step-wise improvement of practice adoption by ML teams.
At-Scale Sparse Deep Neural Network Inference with Efficient GPU Implementation
Venue: arXiv cs.DC 2020
Year: 2020

This paper presents GPU performance optimization and scaling results for inference models of the Sparse Deep Neural Network Challenge 2020. Demands for network quality have increased rapidly, pushing the size and thus the memory requirements of many neural networks beyond the capacity of available accelerators. Sparse deep neural networks (SpDNN) have shown promise for reining in the memory footprint of large neural networks. However, there is room for improvement in implementing SpDNN operations on GPUs. This work presents optimized sparse matrix multiplication kernels fused with the ReLU function. The optimized kernels reuse input feature maps from the shared memory and sparse weights from registers. For multi-GPU parallelism, our SpDNN implementation duplicates weights and statically partition the feature maps across GPUs. Results for the challenge benchmarks show that the proposed kernel design and multi-GPU parallelization achieve up to 180 tera-edges per second inference throughput. These results are up to 4.3x faster for a single GPU and an order of magnitude faster at full scale than those of the champion of the 2019 Sparse Deep Neural Network Graph Challenge for the same generation of NVIDIA V100 GPUs. Using the same implementation, we also show single-GPU throughput on NVIDIA A100 is 2.37$\times$ faster than V100.
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
Venue: arXiv cs.DS 2020
Year: 2020

The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time $2^{O(tw)}n^{O(1)}$, for Feedback Vertex Set and connected versions of the classical graph problems (such as Vertex Cover and Dominating Set). We show that Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Restricted Edge-Subset Feedback Edge Set, Node Multiway Cut, and Multiway Cut are unlikely to have such running times. More precisely, we match algorithms running in time $2^{O(tw \log tw)}n^{O(1)}$ with tight lower bounds under the Exponential-Time Hypothesis (ETH), ruling out $2^{o(tw \log tw)}n^{O(1)}$, where $n$ is the number of vertices and $tw$ is the treewidth of the input graph. Our algorithms extend to the weighted case, while our lower bounds also hold for the larger parameter pathwidth and do not require weights. We also show that, in contrast to Odd Cycle Transversal, there is no $2^{o(tw \log tw)}n^{O(1)}$-time algorithm for Even Cycle Transversal under the ETH.
Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
Venue: arXiv cs.DS 2020
Year: 2020

Graph sketching is a powerful technique introduced by the seminal work of Ahn, Guha and McGregor'12 on connectivity in dynamic graph streams that has enjoyed considerable attention in the literature since then, and has led to near optimal dynamic streaming algorithms for many fundamental problems such as connectivity, cut and spectral sparsifiers and matchings. Interestingly, however, the sketching and dynamic streaming complexity of approximating the shortest path metric of a graph is still far from well-understood. Besides a direct $k$-pass implementation of classical spanner constructions (recently improved to $\lfloor\frac k2\rfloor+1$-passes by Fernandez, Woodruff and Yasuda'20) the state of the art amounts to a $O(\log k)$-pass algorithm of Ahn, Guha and McGregor'12, and a $2$-pass algorithm of Kapralov and Woodruff'14. In particular, no single pass algorithm is known, and the optimal tradeoff between the number of passes, stretch and space complexity is open. In this paper we introduce several new graph sketching techniques for approximating the shortest path metric of the input graph. We give the first {\em single pass} sketching algorithm for constructing graph spanners: we show how to obtain a $\widetilde{O}(n^{\frac23})$-spanner using $\widetilde{O}(n)$ space, and in general a $\widetilde{O}(n^{\frac23(1-α)})$-spanner using $\widetilde{O}(n^{1+α})$ space for every $α\in [0, 1]$, a tradeoff that we think may be close optimal. We also give new spanner construction algorithms for any number of passes, simultaneously improving upon all prior work on this problem. Finally, we study the simultaneous communication model and propose the first protocols with low per player information.
A Novel Token-Based Replay Technique to Speed Up Conformance Checking and Process Enhancement
Venue: arXiv cs.SE 2020
Year: 2020

Token-based replay used to be the standard way to conduct conformance checking. With the uptake of more advanced techniques (e.g., alignment based), token-based replay got abandoned. However, despite decomposition approaches and heuristics to speed-up computation, the more advanced conformance checking techniques have limited scalability, especially when traces get longer and process models more complex. This paper presents an improved token-based replay approach that is much faster and scalable. Moreover, the approach provides more accurate diagnostics that avoid known problems (e.g., "token flooding") and help to pinpoint compliance problems. The novel token-based replay technique has been implemented in the PM4Py process mining library. We will show that the replay technique outperforms state-of-the-art techniques in terms of speed and/or diagnostics. %Moreover, a revision of an existing precision measure (ETConformance) will be proposed through integration with the token-based replayer.
Simple combinatorial auctions with budget constraints
Venue: arXiv cs.GT 2020
Year: 2020

We study the efficiency of simple combinatorial auctions for the allocation of a set of items to a set of agents, with private subadditive valuation functions and budget constraints. The class we consider includes all auctions that allocate each item independently to the agent that submits the highest bid for it, and requests a payment that depends on the bids of all agents only for this item. Two well-known examples of this class are the simultaneous first and second price auctions. We focus on the pure equilibria of the induced strategic games, and using the liquid welfare as our efficiency benchmark, we show an upper bound of 2 on the price of anarchy for any auction in this class, as well as a tight corresponding lower bound on the price of stability for all auctions whose payment rules are convex combinations of the bids. This implies a tight bound of 2 on the price of stability of the well-known simultaneous first and second price auctions, which are members of the class. Additionally, we show lower bounds for the whole class, for more complex auctions (like VCG), and for settings where the budgets are assumed to be common knowledge rather than private information.
Theory of Deep Convolutional Neural Networks II: Spherical Analysis
Venue: arXiv cs.LG 2020
Year: 2020

Deep learning based on deep neural networks of various structures and architectures has been powerful in many practical applications, but it lacks enough theoretical verifications. In this paper, we consider a family of deep convolutional neural networks applied to approximate functions on the unit sphere $\mathbb{S}^{d-1}$ of $\mathbb{R}^d$. Our analysis presents rates of uniform approximation when the approximated function lies in the Sobolev space $W^r_\infty (\mathbb{S}^{d-1})$ with $r>0$ or takes an additive ridge form. Our work verifies theoretically the modelling and approximation ability of deep convolutional neural networks followed by downsampling and one fully connected layer or two. The key idea of our spherical analysis is to use the inner product form of the reproducing kernels of the spaces of spherical harmonics and then to apply convolutional factorizations of filters to realize the generated linear features.
An Ensemble Scheme for Proactive Data Allocation in Distributed Datasets
Venue: arXiv cs.DC 2020
Year: 2020

The advent of the Internet of Things (IoT) gives the opportunity to numerous devices to interact with their environment, collect and process data. Data are transferred, in an upwards mode, to the Cloud through the Edge Computing (EC) infrastructure. A high number of EC nodes become the hosts of distributed datasets where various processing activities can be realized in close distance with end users. This approach can limit the latency in the provision of responses. In this paper, we focus on a model that proactively decides where the collected data should be stored in order to maximize the accuracy of datasets present at the EC infrastructure. We consider that the accuracy is defined by the solidity of datasets exposed as the statistical resemblance of data. We argue upon the similarity of the incoming data with the available datasets and select the most appropriate of them to store the new information. For alleviating processing nodes from the burden of a continuous, complicated statistical processing, we propose the use of synopses as the subject of the similarity process. The incoming data are matched against the available synopses based on an ensemble scheme, then, we select the appropriate host to store them and perform the update of the corresponding synopsis. We provide the description of the problem and the formulation of our solution. Our experimental evaluation targets to reveal the performance of the proposed approach.
Derivation of OTFS Modulation from First Principles
Venue: arXiv cs.IT 2020
Year: 2020

Orthogonal Time Frequency Space (OTFS) modulation has been recently proposed to be robust to channel induced Doppler shift in high mobility wireless communication systems. However, to the best of our knowledge, none of the prior works on OTFS have derived it from first principles. In this paper, using the ZAK representation of time-domain (TD) signals, we rigorously derive an orthonormal basis of approximately time and bandwidth limited signals which are also localized in the delay-Doppler (DD) domain. We then consider DD domain modulation based on this orthonormal basis, and derive OTFS modulation. To the best of our knowledge, this is the first paper to rigorously derive OTFS modulation from first principles. We show that irrespective of the amount of Doppler shift, the received DD domain basis signals are localized in a small interval of size roughly equal to the inverse time duration along the Doppler domain and of size roughly equal to the inverse bandwidth along the delay domain (time duration refers to the length of the time-interval where the TD transmit signal has been limited). With sufficiently large time duration and bandwidth, there is little interference between information symbols modulated on different basis signals, which allows for joint DD domain equalization of all information symbols. This explains the inherent robustness of DD domain modulation to channel induced Doppler shift when compared with Orthogonal Frequency Division Multiplexing (OFDM). The degree of localization of the DD domain basis signals is inversely related to the time duration of the transmit signal, which explains the trade-off between robustness to Doppler shift and latency.
On the Characterization of Saddle Point Equilibrium for Security Games with Additive Utility
Venue: arXiv cs.GT 2020
Year: 2020

In this work, we investigate a security game between an attacker and a defender, originally proposed in \cite{emadi2019security}. As is well known, the combinatorial nature of security games leads to a large cost matrix. Therefore, computing the value and optimal strategy for the players becomes computationally expensive. In this work, we analyze a special class of zero-sum games in which the payoff matrix has a special structure which results from the {\it additive property} of the utility function. Based on variational principles, we present structural properties of optimal attacker as well as defender's strategy. We propose a linear-time algorithm to compute the value based on the structural properties, which is an improvement from our previous result in \cite{emadi2019security}, especially in the context of large-scale zero-sum games.
Visual Reasoning Strategies for Effect Size Judgments and Decisions
Venue: arXiv cs.HC 2020
Year: 2020

Uncertainty visualizations often emphasize point estimates to support magnitude estimates or decisions through visual comparison. However, when design choices emphasize means, users may overlook uncertainty information and misinterpret visual distance as a proxy for effect size. We present findings from a mixed design experiment on Mechanical Turk which tests eight uncertainty visualization designs: 95% containment intervals, hypothetical outcome plots, densities, and quantile dotplots, each with and without means added. We find that adding means to uncertainty visualizations has small biasing effects on both magnitude estimation and decision-making, consistent with discounting uncertainty. We also see that visualization designs that support the least biased effect size estimation do not support the best decision-making, suggesting that a chart user's sense of effect size may not necessarily be identical when they use the same information for different tasks. In a qualitative analysis of users' strategy descriptions, we find that many users switch strategies and do not employ an optimal strategy when one exists. Uncertainty visualizations which are optimally designed in theory may not be the most effective in practice because of the ways that users satisfice with heuristics, suggesting opportunities to better understand visualization effectiveness by modeling sets of potential strategies.
Model Size Reduction Using Frequency Based Double Hashing for Recommender Systems
Venue: arXiv cs.SI 2020
Year: 2020

Deep Neural Networks (DNNs) with sparse input features have been widely used in recommender systems in industry. These models have large memory requirements and need a huge amount of training data. The large model size usually entails a cost, in the range of millions of dollars, for storage and communication with the inference services. In this paper, we propose a hybrid hashing method to combine frequency hashing and double hashing techniques for model size reduction, without compromising performance. We evaluate the proposed models on two product surfaces. In both cases, experiment results demonstrated that we can reduce the model size by around 90 % while keeping the performance on par with the original baselines.
BiTraP: Bi-directional Pedestrian Trajectory Prediction with Multi-modal Goal Estimation
Venue: arXiv cs.CV 2020
Year: 2020

Pedestrian trajectory prediction is an essential task in robotic applications such as autonomous driving and robot navigation. State-of-the-art trajectory predictors use a conditional variational autoencoder (CVAE) with recurrent neural networks (RNNs) to encode observed trajectories and decode multi-modal future trajectories. This process can suffer from accumulated errors over long prediction horizons (>=2 seconds). This paper presents BiTraP, a goal-conditioned bi-directional multi-modal trajectory prediction method based on the CVAE. BiTraP estimates the goal (end-point) of trajectories and introduces a novel bi-directional decoder to improve longer-term trajectory prediction accuracy. Extensive experiments show that BiTraP generalizes to both first-person view (FPV) and bird's-eye view (BEV) scenarios and outperforms state-of-the-art results by ~10-50%. We also show that different choices of non-parametric versus parametric target models in the CVAE directly influence the predicted multi-modal trajectory distributions. These results provide guidance on trajectory predictor design for robotic applications such as collision avoidance and navigation systems.