OpenRaiser/Intern-Atlas huggingface dataset:
Efficient, Noise-Tolerant, and Private Learning via Boosting
Venue: arXiv cs.LG 2020
Year: 2020

We introduce a simple framework for designing private boosting algorithms. We give natural conditions under which these algorithms are differentially private, efficient, and noise-tolerant PAC learners. To demonstrate our framework, we use it to construct noise-tolerant and private PAC learners for large-margin halfspaces whose sample complexity does not depend on the dimension. We give two sample complexity bounds for our large-margin halfspace learner. One bound is based only on differential privacy, and uses this guarantee as an asset for ensuring generalization. This first bound illustrates a general methodology for obtaining PAC learners from privacy, which may be of independent interest. The second bound uses standard techniques from the theory of large-margin classification (the fat-shattering dimension) to match the best known sample complexity for differentially private learning of large-margin halfspaces, while additionally tolerating random label noise.
Arabic Diacritic Recovery Using a Feature-Rich biLSTM Model
Venue: arXiv cs.CL 2020
Year: 2020

Diacritics (short vowels) are typically omitted when writing Arabic text, and readers have to reintroduce them to correctly pronounce words. There are two types of Arabic diacritics: the first are core-word diacritics (CW), which specify the lexical selection, and the second are case endings (CE), which typically appear at the end of the word stem and generally specify their syntactic roles. Recovering CEs is relatively harder than recovering core-word diacritics due to inter-word dependencies, which are often distant. In this paper, we use a feature-rich recurrent neural network model that uses a variety of linguistic and surface-level features to recover both core word diacritics and case endings. Our model surpasses all previous state-of-the-art systems with a CW error rate (CWER) of 2.86\% and a CE error rate (CEER) of 3.7% for Modern Standard Arabic (MSA) and CWER of 2.2% and CEER of 2.5% for Classical Arabic (CA). When combining diacritized word cores with case endings, the resultant word error rate is 6.0% and 4.3% for MSA and CA respectively. This highlights the effectiveness of feature engineering for such deep neural models.
Deep-Geometric 6 DoF Localization from a Single Image in Topo-metric Maps
Venue: arXiv cs.CV 2020
Year: 2020

We describe a Deep-Geometric Localizer that is able to estimate the full 6 Degree of Freedom (DoF) global pose of the camera from a single image in a previously mapped environment. Our map is a topo-metric one, with discrete topological nodes whose 6 DoF poses are known. Each topo-node in our map also comprises of a set of points, whose 2D features and 3D locations are stored as part of the mapping process. For the mapping phase, we utilise a stereo camera and a regular stereo visual SLAM pipeline. During the localization phase, we take a single camera image, localize it to a topological node using Deep Learning, and use a geometric algorithm (PnP) on the matched 2D features (and their 3D positions in the topo map) to determine the full 6 DoF globally consistent pose of the camera. Our method divorces the mapping and the localization algorithms and sensors (stereo and mono), and allows accurate 6 DoF pose estimation in a previously mapped environment using a single camera. With potential VR/AR and localization applications in single camera devices such as mobile phones and drones, our hybrid algorithm compares favourably with the fully Deep-Learning based Pose-Net that regresses pose from a single image in simulated as well as real environments.
ALPINE: Active Link Prediction using Network Embedding
Venue: arXiv cs.LG 2020
Year: 2020

Many real-world problems can be formalized as predicting links in a partially observed network. Examples include Facebook friendship suggestions, consumer-product recommendations, and the identification of hidden interactions between actors in a crime network. Several link prediction algorithms, notably those recently introduced using network embedding, are capable of doing this by just relying on the observed part of the network. Often, the link status of a node pair can be queried, which can be used as additional information by the link prediction algorithm. Unfortunately, such queries can be expensive or time-consuming, mandating the careful consideration of which node pairs to query. In this paper we estimate the improvement in link prediction accuracy after querying any particular node pair, to use in an active learning setup. Specifically, we propose ALPINE (Active Link Prediction usIng Network Embedding), the first method to achieve this for link prediction based on network embedding. To this end, we generalized the notion of V-optimality from experimental design to this setting, as well as more basic active learning heuristics originally developed in standard classification settings. Empirical results on real data show that ALPINE is scalable, and boosts link prediction accuracy with far fewer queries.
Local Aggregation in Preference Games
Venue: arXiv cs.GT 2020
Year: 2020

In this work we introduce a new model of decision-making by agents in a social network. Agents have innate preferences over the strategies but, because of the social interactions, the decision of the agents are not only affected by their innate preferences but also by the decision taken by their social neighbors. We assume that the strategies of the agents are embedded in an {approximate} metric space. Furthermore, departing from the previous literature, we assume that, due to the lack of information, each agent locally represents the trend of the network through an aggregate value, which can be interpreted as the output of an aggregation function. We answer some fundamental questions related to the existence and efficiency of pure Nash equilibria.
Tackling Existence Probabilities of Objects with Motion Planning for Automated Urban Driving
Venue: arXiv cs.RO 2020
Year: 2020

Motion planners take uncertain information about the environment as an input. The environment information is often quite noisy and has a tendency to contain false positive object detection. State-of-the-art motion planners consider all objects alike, thus producing overcautious behavior. In this paper we present a planning approach that considers alternative maneuvers in a combined fashion and plans a motion that is formed by the probabilities of those alternatives. The proposed planner can smoothly react to objects with low existence probability while remaining collision-free in case their existence substantiates. In this way, it tolerates the faults arising from perception and prediction, thus reducing their impact on operational reliability.
A Double Exponential Lower Bound for the Distinct Vectors Problem
Venue: arXiv cs.CC 2020
Year: 2020

In the (binary) Distinct Vectors problem we are given a binary matrix A with pairwise different rows and want to select at most k columns such that, restricting the matrix to these columns, all rows are still pairwise different. A result by Froese et al. [JCSS] implies a 2^2^(O(k)) * poly(|A|)-time brute-force algorithm for Distinct Vectors. We show that this running time bound is essentially optimal by showing that there is a constant c such that the existence of an algorithm solving Distinct Vectors with running time 2^(O(2^(ck))) * poly(|A|) would contradict the Exponential Time Hypothesis.
Cooperative Service Caching and Workload Scheduling in Mobile Edge Computing
Venue: arXiv cs.NI 2020
Year: 2020

Mobile edge computing is beneficial to reduce service response time and core network traffic by pushing cloud functionalities to network edge. Equipped with storage and computation capacities, edge nodes can cache services of resource-intensive and delay-sensitive mobile applications and process the corresponding computation tasks without outsourcing to central clouds. However, the heterogeneity of edge resource capacities and inconsistence of edge storage and computation capacities make it difficult to jointly fully utilize the storage and computation capacities when there is no cooperation among edge nodes. To address this issue, we consider cooperation among edge nodes and investigate cooperative service caching and workload scheduling in mobile edge computing. This problem can be formulated as a mixed integer nonlinear programming problem, which has non-polynomial computation complexity. To overcome the challenges of subproblem coupling, computation-communication tradeoff, and edge node heterogeneity, we develop an iterative algorithm called ICE. This algorithm is designed based on Gibbs sampling, which has provably near-optimal results, and the idea of water filling, which has polynomial computation complexity. Simulations are conducted and the results demonstrate that our algorithm can jointly reduce the service response time and the outsourcing traffic compared with the benchmark algorithms.
Schema-Guided Dialogue State Tracking Task at DSTC8
Venue: arXiv cs.CL 2020
Year: 2020

This paper gives an overview of the Schema-Guided Dialogue State Tracking task of the 8th Dialogue System Technology Challenge. The goal of this task is to develop dialogue state tracking models suitable for large-scale virtual assistants, with a focus on data-efficient joint modeling across domains and zero-shot generalization to new APIs. This task provided a new dataset consisting of over 16000 dialogues in the training set spanning 16 domains to highlight these challenges, and a baseline model capable of zero-shot generalization to new APIs. Twenty-five teams participated, developing a range of neural network models, exceeding the performance of the baseline model by a very high margin. The submissions incorporated a variety of pre-trained encoders and data augmentation techniques. This paper describes the task definition, dataset and evaluation methodology. We also summarize the approach and results of the submitted systems to highlight the overall trends in the state-of-the-art.
Multi-Objective Optimization for Size and Resilience of Spiking Neural Networks
Venue: arXiv cs.NE 2020
Year: 2020

Inspired by the connectivity mechanisms in the brain, neuromorphic computing architectures model Spiking Neural Networks (SNNs) in silicon. As such, neuromorphic architectures are designed and developed with the goal of having small, low power chips that can perform control and machine learning tasks. However, the power consumption of the developed hardware can greatly depend on the size of the network that is being evaluated on the chip. Furthermore, the accuracy of a trained SNN that is evaluated on chip can change due to voltage and current variations in the hardware that perturb the learned weights of the network. While efforts are made on the hardware side to minimize those perturbations, a software based strategy to make the deployed networks more resilient can help further alleviate that issue. In this work, we study Spiking Neural Networks in two neuromorphic architecture implementations with the goal of decreasing their size, while at the same time increasing their resiliency to hardware faults. We leverage an evolutionary algorithm to train the SNNs and propose a multiobjective fitness function to optimize the size and resiliency of the SNN. We demonstrate that this strategy leads to well-performing, small-sized networks that are more resilient to hardware faults.
Spatially Variant Laplacian Pyramids for Multi-Frame Exposure Fusion
Venue: arXiv cs.MM 2020
Year: 2020

Laplacian Pyramid Blending is a commonly used method for several seamless image blending tasks. While the method works well for images with comparable intensity levels, it is often unable to produce artifact free images for applications which handle images with large intensity variation such as exposure fusion. This paper proposes a spatially varying Laplacian Pyramid Blending to blend images with large intensity differences. The proposed method dynamically alters the blending levels during the final stage of Pyramid Reconstruction based on the amount of local intensity variation. The proposed algorithm out performs state-of-the-art methods for image blending both qualitatively as well as quantitatively on publicly available High Dynamic Range (HDR) imaging dataset. Qualitative improvements are demonstrated in terms of details, halos and dark halos. For quantitative comparison, the no-reference perceptual metric MEF-SSIM was used.
The Limits of LoRaWAN in Event-Triggered Wireless Networked Control Systems
Venue: arXiv cs.NI 2020
Year: 2020

Wireless sensors and actuators offer benefits to large industrial control systems. The absence of wires for communication reduces the deployment cost, maintenance effort, and provides greater flexibility for sensor and actuator location and system architecture. These benefits come at a cost of a high probability of communication delay or message loss due to the unreliability of radio-based communication. This unreliability poses a challenge to contemporary control systems that are designed with the assumption of instantaneous and reliable communication. Wireless sensors and actuators create a paradigm shift in engineering energy-efficient control schemes coupled with robust communication schemes that can maintain system stability in the face of unreliable communication. This paper investigates the feasibility of using the low-power wide-area communication protocol LoRaWAN with an event-triggered control scheme through modelling in Matlab. We show that LoRaWAN is capable of meeting the maximum delay and message loss requirements of an event-triggered controller for certain classes of applications. We also expose the limitation in the use of LoRaWAN when message size or communication range requirements increase or the underlying physical system is exposed to significant external disturbances.
The Privacy Funnel from the viewpoint of Local Differential Privacy
Venue: arXiv cs.CR 2020
Year: 2020

We consider a database $\vec{X} = (X_1,\cdots,X_n)$ containing the data of $n$ users. The data aggregator wants to publicise the database, but wishes to sanitise the dataset to hide sensitive data $S_i$ correlated to $X_i$. This setting is considered in the Privacy Funnel, which uses mutual information as a leakage metric. The downsides to this approach are that mutual information does not give worst-case guarantees, and that finding optimal sanitisation protocols can be computationally prohibitive. We tackle these problems by using differential privacy metrics, and by considering local protocols which operate on one entry at a time. We show that under both the Local Differential Privacy and Local Information Privacy leakage metrics, one can efficiently obtain optimal protocols; however, Local Information Privacy is both more closely aligned to the privacy requirements of the Privacy Funnel scenario, and more efficiently computable. We also consider the scenario where each user has multiple attributes (i.e. $X_i = (X^1_i,\cdots,X^m_i)$), for which we define \emph{Side-channel Resistant Local Information Privacy}, and we give efficient methods to find protocols satisfying this criterion while still offering good utility. Exploratory experiments confirm the validity of these methods.
Generalizing meanings from partners to populations: Hierarchical inference supports convention formation on networks
Venue: arXiv cs.CL 2020
Year: 2020

A key property of linguistic conventions is that they hold over an entire community of speakers, allowing us to communicate efficiently even with people we have never met before. At the same time, much of our language use is partner-specific: we know that words may be understood differently by different people based on our shared history. This poses a challenge for accounts of convention formation. Exactly how do agents make the inferential leap to community-wide expectations while maintaining partner-specific knowledge? We propose a hierarchical Bayesian model to explain how speakers and listeners solve this inductive problem. To evaluate our model's predictions, we conducted an experiment where participants played an extended natural-language communication game with different partners in a small community. We examine several measures of generalization and find key signatures of both partner-specificity and community convergence that distinguish our model from alternatives. These results suggest that partner-specificity is not only compatible with the formation of community-wide conventions, but may facilitate it when coupled with a powerful inductive mechanism.
Separating Variables in Bivariate Polynomial Ideals
Venue: arXiv cs.SC 2020
Year: 2020

We present an algorithm which for any given ideal $I\subseteq\mathbb{K} [x,y]$ finds all elements of $I$ that have the form $f(x) - g(y)$, i.e., all elements in which no monomial is a multiple of $xy$.
Accelerating Psychometric Screening Tests With Bayesian Active Differential Selection
Venue: arXiv cs.LG 2020
Year: 2020

Classical methods for psychometric function estimation either require excessive measurements or produce only a low-resolution approximation of the target psychometric function. In this paper, we propose a novel solution for rapid screening for a change in the psychometric function estimation of a given patient. We use Bayesian active model selection to perform an automated pure-tone audiogram test with the goal of quickly finding if the current audiogram will be different from a previous audiogram. We validate our approach using audiometric data from the National Institute for Occupational Safety and Health NIOSH. Initial results show that with a few tones we can detect if the patient's audiometric function has changed between the two test sessions with high confidence.
Dropout Prediction over Weeks in MOOCs via Interpretable Multi-Layer Representation Learning
Venue: arXiv cs.LG 2020
Year: 2020

Massive Open Online Courses (MOOCs) have become popular platforms for online learning. While MOOCs enable students to study at their own pace, this flexibility makes it easy for students to drop out of class. In this paper, our goal is to predict if a learner is going to drop out within the next week, given clickstream data for the current week. To this end, we present a multi-layer representation learning solution based on branch and bound (BB) algorithm, which learns from low-level clickstreams in an unsupervised manner, produces interpretable results, and avoids manual feature engineering. In experiments on Coursera data, we show that our model learns a representation that allows a simple model to perform similarly well to more complex, task-specific models, and how the BB algorithm enables interpretable results. In our analysis of the observed limitations, we discuss promising future directions.
BABO: Background Activation Black-Out for Efficient Object Detection
Venue: arXiv cs.CV 2020
Year: 2020

Recent advances in deep learning have enabled complex real-world use cases comprised of multiple vision tasks and detection tasks are being shifted to the edge side as a pre-processing step of the entire workload. Since running a deep model on resource-constraint devices is challenging, techniques for efficient inference methods are demanded. In this paper, we present an objectness-aware object detection method to reduce computational cost by sparsifying activation values on background regions where target objects don't exist. Sparsified activation can be exploited to increase inference speed by software or hardware accelerated sparse convolution techniques. To accomplish this goal, we incorporate a light-weight objectness mask generation (OMG) network in front of an object detection (OD) network so that it can zero out unnecessary background areas of an input image before being fed into the OD network. In experiments, by switching background activation values to zero, the average number of zero values increases further from 36% to 68% on MobileNetV2-SSDLite even with ReLU activation while maintaining accuracy on MS-COCO. This result indicates that the total MAC including both OMG and OD networks can be reduced to 62% of the original OD model when only non-zero multiply-accumulate operations are considered. Moreover, we show a similar tendency in heavy networks (VGG and RetinaNet) and an additional dataset (PASCAL VOC).
Solving Raven's Progressive Matrices with Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

Raven's Progressive Matrices (RPM) have been widely used for Intelligence Quotient (IQ) test of humans. In this paper, we aim to solve RPM with neural networks in both supervised and unsupervised manners. First, we investigate strategies to reduce over-fitting in supervised learning. We suggest the use of a neural network with deep layers and pre-training on large-scale datasets to improve model generalization. Experiments on the RAVEN dataset show that the overall accuracy of our supervised approach surpasses human-level performance. Second, as an intelligent agent requires to automatically learn new skills to solve new problems, we propose the first unsupervised method, Multilabel Classification with Pseudo Target (MCPT), for RPM problems. Based on the design of the pseudo target, MCPT converts the unsupervised learning problem to a supervised task. Experiments show that MCPT doubles the testing accuracy of random guessing e.g. 28.50% vs. 12.5%. Finally, we discuss the problem of solving RPM with unsupervised and explainable strategies in the future.
Concept Whitening for Interpretable Image Recognition
Venue: arXiv cs.LG 2020
Year: 2020

What does a neural network encode about a concept as we traverse through the layers? Interpretability in machine learning is undoubtedly important, but the calculations of neural networks are very challenging to understand. Attempts to see inside their hidden layers can either be misleading, unusable, or rely on the latent space to possess properties that it may not have. In this work, rather than attempting to analyze a neural network posthoc, we introduce a mechanism, called concept whitening (CW), to alter a given layer of the network to allow us to better understand the computation leading up to that layer. When a concept whitening module is added to a CNN, the axes of the latent space are aligned with known concepts of interest. By experiment, we show that CW can provide us a much clearer understanding for how the network gradually learns concepts over layers. CW is an alternative to a batch normalization layer in that it normalizes, and also decorrelates (whitens) the latent space. CW can be used in any layer of the network without hurting predictive performance.