pwc-archive/papers-with-abstracts huggingface dataset:
Learning from Data to Speed-up Sorted Table Search Procedures: Methodology and Practical Guidelines
Authors: Domenico Amato, Giosué Lo Bosco, Raffaele Giancarlo
Date: 2020-07-20 00:00:00
Tasks: CPU, GPU, Table Search

Sorted Table Search Procedures are the quintessential query-answering tool, with widespread usage that now includes also Web Applications, e.g, Search Engines (Google Chrome) and ad Bidding Systems (AppNexus). Speeding them up, at very little cost in space, is still a quite significant achievement. Here we study to what extend Machine Learning Techniques can contribute to obtain such a speed-up via a systematic experimental comparison of known efficient implementations of Sorted Table Search procedures, with different Data Layouts, and their Learned counterparts developed here. We characterize the scenarios in which those latter can be profitably used with respect to the former, accounting for both CPU and GPU computing. Our approach contributes also to the study of Learned Data Structures, a recent proposal to improve the time/space performance of fundamental Data Structures, e.g., B-trees, Hash Tables, Bloom Filters. Indeed, we also formalize an Algorithmic Paradigm of Learned Dichotomic Sorted Table Search procedures that naturally complements the Learned one proposed here and that characterizes most of the known Sorted Table Search Procedures as having a "learning phase" that approximates Simple Linear Regression.
Unsupervised Domain Adaptation in the Absence of Source Data
Authors: Roshni Sahoo, Divya Shanmugam, John Guttag
Date: 2020-07-20 00:00:00
Tasks: Domain Adaptation, Unsupervised Domain Adaptation

Current unsupervised domain adaptation methods can address many types of distribution shift, but they assume data from the source domain is freely available. As the use of pre-trained models becomes more prevalent, it is reasonable to assume that source data is unavailable. We propose an unsupervised method for adapting a source classifier to a target domain that varies from the source domain along natural axes, such as brightness and contrast. Our method only requires access to unlabeled target instances and the source classifier. We validate our method in scenarios where the distribution shift involves brightness, contrast, and rotation and show that it outperforms fine-tuning baselines in scenarios with limited labeled data.
Integrating Network Embedding and Community Outlier Detection via Multiclass Graph Description
Authors: Sambaran Bandyopadhyay, Saley Vishal Vivek, M. N. Murty
Date: 2020-07-20 00:00:00
Tasks: Community Detection, Graph Embedding, Network Embedding, Outlier Detection

Network (or graph) embedding is the task to map the nodes of a graph to a lower dimensional vector space, such that it preserves the graph properties and facilitates the downstream network mining tasks. Real world networks often come with (community) outlier nodes, which behave differently from the regular nodes of the community. These outlier nodes can affect the embedding of the regular nodes, if not handled carefully. In this paper, we propose a novel unsupervised graph embedding approach (called DMGD) which integrates outlier and community detection with node embedding. We extend the idea of deep support vector data description to the framework of graph embedding when there are multiple communities present in the given network, and an outlier is characterized relative to its community. We also show the theoretical bounds on the number of outliers detected by DMGD. Our formulation boils down to an interesting minimax game between the outliers, community assignments and the node embedding function. We also propose an efficient algorithm to solve this optimization framework. Experimental results on both synthetic and real world networks show the merit of our approach compared to state-of-the-arts.
Regret Analysis of a Markov Policy Gradient Algorithm for Multi-arm Bandits
Authors: Denis Denisov, Neil Walton
Date: 2020-07-20 00:00:00

We consider a policy gradient algorithm applied to a finite-arm bandit problem with Bernoulli rewards. We allow learning rates to depend on the current state of the algorithm, rather than use a deterministic time-decreasing learning rate. The state of the algorithm forms a Markov chain on the probability simplex. We apply Foster-Lyapunov techniques to analyse the stability of this Markov chain. We prove that if learning rates are well chosen then the policy gradient algorithm is a transient Markov chain and the state of the chain converges on the optimal arm with logarithmic or poly-logarithmic regret.
Nengo and low-power AI hardware for robust, embedded neurorobotics
Authors: Travis DeWolf, Pawel Jaworski, Chris Eliasmith
Date: 2020-07-20 00:00:00
Tasks: MuJoCo

In this paper we demonstrate how the Nengo neural modeling and simulation libraries enable users to quickly develop robotic perception and action neural networks for simulation on neuromorphic hardware using familiar tools, such as Keras and Python. We identify four primary challenges in building robust, embedded neurorobotic systems: 1) developing infrastructure for interfacing with the environment and sensors; 2) processing task specific sensory signals; 3) generating robust, explainable control signals; and 4) compiling neural networks to run on target hardware. Nengo helps to address these challenges by: 1) providing the NengoInterfaces library, which defines a simple but powerful API for users to interact with simulations and hardware; 2) providing the NengoDL library, which lets users use the Keras and TensorFlow API to develop Nengo models; 3) implementing the Neural Engineering Framework, which provides white-box methods for implementing known functions and circuits; and 4) providing multiple backend libraries, such as NengoLoihi, that enable users to compile the same model to different hardware. We present two examples using Nengo to develop neural networks that run on CPUs, GPUs, and Intel's neuromorphic chip, Loihi, to demonstrate this workflow. The first example is an end-to-end spiking neural network that controls a rover simulated in Mujoco. The network integrates a deep convolutional network that processes visual input from mounted cameras to track a target, and a control system implementing steering and drive functions to guide the rover to the target. The second example augments a force-based operational space controller with neural adaptive control to improve performance during a reaching task using a real-world Kinova Jaco2 robotic arm. Code and details are provided with the intent of enabling other researchers to build their own neurorobotic systems.
Learning latent representations across multiple data domains using Lifelong VAEGAN
Authors: Fei Ye, Adrian G. Bors
Date: 2020-07-20 00:00:00
Proceeding: ECCV 2020 8
Tasks: Lifelong learning, Representation Learning

The problem of catastrophic forgetting occurs in deep learning models trained on multiple databases in a sequential manner. Recently, generative replay mechanisms (GRM), have been proposed to reproduce previously learned knowledge aiming to reduce the forgetting. However, such approaches lack an appropriate inference model and therefore can not provide latent representations of data. In this paper, we propose a novel lifelong learning approach, namely the Lifelong VAEGAN (L-VAEGAN), which not only induces a powerful generative replay network but also learns meaningful latent representations, benefiting representation learning. L-VAEGAN can allow to automatically embed the information associated with different domains into several clusters in the latent space, while also capturing semantically meaningful shared latent variables, across different data domains. The proposed model supports many downstream tasks that traditional generative replay methods can not, including interpolation and inference across different data domains.
Solving the functional Eigen-Problem using Neural Networks
Authors: Ido Ben-Shaul, Leah Bar, Nir Sochen
Date: 2020-07-20 00:00:00

In this work, we explore the ability of NN (Neural Networks) to serve as a tool for finding eigen-pairs of ordinary differential equations. The question we aime to address is whether, given a self-adjoint operator, we can learn what are the eigenfunctions, and their matching eigenvalues. The topic of solving the eigen-problem is widely discussed in Image Processing, as many image processing algorithms can be thought of as such operators. We suggest an alternative to numeric methods of finding eigenpairs, which may potentially be more robust and have the ability to solve more complex problems. In this work, we focus on simple problems for which the analytical solution is known. This way, we are able to make initial steps in discovering the capabilities and shortcomings of DNN (Deep Neural Networks) in the given setting.
Can we cover navigational perception needs of the visually impaired by panoptic segmentation?
Authors: Wei Mao, Jiaming Zhang, Kailun Yang, Rainer Stiefelhagen
Date: 2020-07-20 00:00:00
Tasks: Deep Learning, Instance Segmentation, Panoptic Segmentation, Segmentation, Semantic Segmentation

Navigational perception for visually impaired people has been substantially promoted by both classic and deep learning based segmentation methods. In classic visual recognition methods, the segmentation models are mostly object-dependent, which means a specific algorithm has to be devised for the object of interest. In contrast, deep learning based models such as instance segmentation and semantic segmentation allow to individually recognize part of the entire scene, namely things or stuff, for blind individuals. However, both of them can not provide a holistic understanding of the surroundings for the visually impaired. Panoptic segmentation is a newly proposed visual model with the aim of unifying semantic segmentation and instance segmentation. Motivated by that, we propose to utilize panoptic segmentation as an approach to navigating visually impaired people by offering both things and stuff awareness in the proximity of the visually impaired. We demonstrate that panoptic segmentation is able to equip the visually impaired with a holistic real-world scene perception through a wearable assistive system.
A Comprehensive Evaluation of Multi-task Learning and Multi-task Pre-training on EHR Time-series Data
Authors: Matthew B. A. McDermott, Bret Nestor, Evan Kim, Wancong Zhang, Anna Goldenberg, Peter Szolovits, Marzyeh Ghassemi
Date: 2020-07-20 00:00:00
Tasks: Few-Shot Learning, Multi-Task Learning, Time Series, Time Series Analysis

Multi-task learning (MTL) is a machine learning technique aiming to improve model performance by leveraging information across many tasks. It has been used extensively on various data modalities, including electronic health record (EHR) data. However, despite significant use on EHR data, there has been little systematic investigation of the utility of MTL across the diverse set of possible tasks and training schemes of interest in healthcare. In this work, we examine MTL across a battery of tasks on EHR time-series data. We find that while MTL does suffer from common negative transfer, we can realize significant gains via MTL pre-training combined with single-task fine-tuning. We demonstrate that these gains can be achieved in a task-independent manner and offer not only minor improvements under traditional learning, but also notable gains in a few-shot learning context, thereby suggesting this could be a scalable vehicle to offer improved performance in important healthcare contexts.
Time Series Source Separation with Slow Flows
Authors: Edouard Pineau, Sébastien Razakarivony, Thomas Bonald
Date: 2020-07-20 00:00:00
Tasks: blind source separation, Time Series, Time Series Analysis

In this paper, we show that slow feature analysis (SFA), a common time series decomposition method, naturally fits into the flow-based models (FBM) framework, a type of invertible neural latent variable models. Building upon recent advances on blind source separation, we show that such a fit makes the time series decomposition identifiable.
Mixed Moments for the Product of Ginibre Matrices
Authors: Nick Halmagyi, Shailesh Lal
Date: 2020-07-20 00:00:00

We study the ensemble of a product of n complex Gaussian i.i.d. matrices. We find this ensemble is Gaussian with a variance matrix which is averaged over a multi-Wishart ensemble. We compute the mixed moments and find that at large $N$, they are given by an enumeration of non-crossing pairings weighted by Fuss-Catalan numbers.
NPCFace: Negative-Positive Collaborative Training for Large-scale Face Recognition
Authors: Dan Zeng, Hailin Shi, Hang Du, Jun Wang, Zhen Lei, Tao Mei
Date: 2020-07-20 00:00:00
Tasks: Face Recognition

The training scheme of deep face recognition has greatly evolved in the past years, yet it encounters new challenges in the large-scale data situation where massive and diverse hard cases occur. Especially in the range of low false accept rate (FAR), there are various hard cases in both positives (intra-class) and negatives (inter-class). In this paper, we study how to make better use of these hard samples for improving the training. The literature approaches this by margin-based formulation in either positive logit or negative logits. However, the correlation between hard positive and hard negative is overlooked, and so is the relation between the margins in positive and negative logits. We find such correlation is significant, especially in the large-scale dataset, and one can take advantage from it to boost the training via relating the positive and negative margins for each training sample. To this end, we propose an explicit collaboration between positive and negative margins sample-wisely. Given a batch of hard samples, a novel Negative-Positive Collaboration loss, named NPCFace, is formulated, which emphasizes the training on both negative and positive hard cases via the collaborative-margin mechanism in the softmax logits, and also brings better interpretation of negative-positive hardness correlation. Besides, the emphasis is implemented with an improved formulation to achieve stable convergence and flexible parameter setting. We validate the effectiveness of our approach on various benchmarks of large-scale face recognition, and obtain advantageous results especially in the low FAR range.
Discrete Point Flow Networks for Efficient Point Cloud Generation
Authors: Roman Klokov, Edmond Boyer, Jakob Verbeek
Date: 2020-07-20 00:00:00
Proceeding: ECCV 2020 8
Tasks: 3D Shape Representation, Point Cloud Generation

Generative models have proven effective at modeling 3D shapes and their statistical variations. In this paper we investigate their application to point clouds, a 3D shape representation widely used in computer vision for which, however, only few generative models have yet been proposed. We introduce a latent variable model that builds on normalizing flows with affine coupling layers to generate 3D point clouds of an arbitrary size given a latent shape representation. To evaluate its benefits for shape modeling we apply this model for generation, autoencoding, and single-view shape reconstruction tasks. We improve over recent GAN-based models in terms of most metrics that assess generation and autoencoding. Compared to recent work based on continuous flows, our model offers a significant speedup in both training and inference times for similar or better performance. For single-view shape reconstruction we also obtain results on par with state-of-the-art voxel, point cloud, and mesh-based methods.
Competing Bandits: The Perils of Exploration Under Competition
Authors: Guy Aridor, Yishay Mansour, Aleksandrs Slivkins, Zhiwei Steven Wu
Date: 2020-07-20 00:00:00
Tasks: Multi-Armed Bandits

Most online platforms strive to learn from interactions with users, and many engage in exploration: making potentially suboptimal choices for the sake of acquiring new information. We study the interplay between exploration and competition: how such platforms balance the exploration for learning and the competition for users. Here users play three distinct roles: they are customers that generate revenue, they are sources of data for learning, and they are self-interested agents which choose among the competing platforms. We consider a stylized duopoly model in which two firms face the same multi-armed bandit problem. Users arrive one by one and choose between the two firms, so that each firm makes progress on its bandit problem only if it is chosen. Through a mix of theoretical results and numerical simulations, we study whether and to what extent competition incentivizes the adoption of better bandit algorithms, and whether it leads to welfare increases for users. We find that stark competition induces firms to commit to a "greedy" bandit algorithm that leads to low welfare. However, weakening competition by providing firms with some "free" users incentivizes better exploration strategies and increases welfare. We investigate two channels for weakening the competition: relaxing the rationality of users and giving one firm a first-mover advantage. Our findings are closely related to the "competition vs. innovation" relationship, and elucidate the first-mover advantage in the digital economy.
On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications
Authors: Sayan Bandyapadhyay, Fedor V. Fomin, Kirill Simonov
Date: 2020-07-20 00:00:00
Tasks: Clustering, Constrained Clustering

Fair clustering is a constrained variant of clustering where the goal is to partition a set of colored points, such that the fraction of points of any color in every cluster is more or less equal to the fraction of points of this color in the dataset. This variant was recently introduced by Chierichetti et al. [NeurIPS, 2017] in a seminal work and became widely popular in the clustering literature. In this paper, we propose a new construction of coresets for fair clustering based on random sampling. The new construction allows us to obtain the first coreset for fair clustering in general metric spaces. For Euclidean spaces, we obtain the first coreset whose size does not depend exponentially on the dimension. Our coreset results solve open questions proposed by Schmidt et al. [WAOA, 2019] and Huang et al. [NeurIPS, 2019]. The new coreset construction helps to design several new approximation and streaming algorithms. In particular, we obtain the first true constant-approximation algorithm for metric fair clustering, whose running time is fixed-parameter tractable (FPT). In the Euclidean case, we derive the first $(1+\epsilon)$-approximation algorithm for fair clustering whose time complexity is near-linear and does not depend exponentially on the dimension of the space. Besides, our coreset construction scheme is fairly general and gives rise to coresets for a wide range of constrained clustering problems. This leads to improved constant-approximations for these problems in general metrics and near-linear time $(1+\epsilon)$-approximations in the Euclidean metric.
DiffRNN: Differential Verification of Recurrent Neural Networks
Authors: Sara Mohammadinejad, Brandon Paulsen, Chao Wang, Jyotirmoy V. Deshmukh
Date: 2020-07-20 00:00:00
Tasks: speech-recognition, Speech Recognition

Recurrent neural networks (RNNs) such as Long Short Term Memory (LSTM) networks have become popular in a variety of applications such as image processing, data classification, speech recognition, and as controllers in autonomous systems. In practical settings, there is often a need to deploy such RNNs on resource-constrained platforms such as mobile phones or embedded devices. As the memory footprint and energy consumption of such components become a bottleneck, there is interest in compressing and optimizing such networks using a range of heuristic techniques. However, these techniques do not guarantee the safety of the optimized network, e.g., against adversarial inputs, or equivalence of the optimized and original networks. To address this problem, we propose DIFFRNN, the first differential verification method for RNNs to certify the equivalence of two structurally similar neural networks. Existing work on differential verification for ReLUbased feed-forward neural networks does not apply to RNNs where nonlinear activation functions such as Sigmoid and Tanh cannot be avoided. RNNs also pose unique challenges such as handling sequential inputs, complex feedback structures, and interactions between the gates and states. In DIFFRNN, we overcome these challenges by bounding nonlinear activation functions with linear constraints and then solving constrained optimization problems to compute tight bounding boxes on nonlinear surfaces in a high-dimensional space. The soundness of these bounding boxes is then proved using the dReal SMT solver. We demonstrate the practical efficacy of our technique on a variety of benchmarks and show that DIFFRNN outperforms state-of-the-art RNN verification tools such as POPQORN.
Monte Carlo Dropout Ensembles for Robust Illumination Estimation
Authors: Firas Laakom, Jenni Raitoharju, Alexandros Iosifidis, Jarno Nikkanen, Moncef Gabbouj
Date: 2020-07-20 00:00:00
Tasks: Color Constancy, Deep Learning

Computational color constancy is a preprocessing step used in many camera systems. The main aim is to discount the effect of the illumination on the colors in the scene and restore the original colors of the objects. Recently, several deep learning-based approaches have been proposed to solve this problem and they often led to state-of-the-art performance in terms of average errors. However, for extreme samples, these methods fail and lead to high errors. In this paper, we address this limitation by proposing to aggregate different deep learning methods according to their output uncertainty. We estimate the relative uncertainty of each approach using Monte Carlo dropout and the final illumination estimate is obtained as the sum of the different model estimates weighted by the log-inverse of their corresponding uncertainties. The proposed framework leads to state-of-the-art performance on INTEL-TAU dataset.
ThriftyNets : Convolutional Neural Networks with Tiny Parameter Budget
Authors: Guillaume Coiffier, Ghouthi Boukli Hacene, Vincent Gripon
Date: 2020-07-20 00:00:00

Typical deep convolutional architectures present an increasing number of feature maps as we go deeper in the network, whereas spatial resolution of inputs is decreased through downsampling operations. This means that most of the parameters lay in the final layers, while a large portion of the computations are performed by a small fraction of the total parameters in the first layers. In an effort to use every parameter of a network at its maximum, we propose a new convolutional neural network architecture, called ThriftyNet. In ThriftyNet, only one convolutional layer is defined and used recursively, leading to a maximal parameter factorization. In complement, normalization, non-linearities, downsamplings and shortcut ensure sufficient expressivity of the model. ThriftyNet achieves competitive performance on a tiny parameters budget, exceeding 91% accuracy on CIFAR-10 with less than 40K parameters in total, and 74.3% on CIFAR-100 with less than 600K parameters.