OpenRaiser/Intern-Atlas huggingface dataset:
A Comparison of LiDAR-based SLAM Systems for Control of Unmanned Aerial Vehicles
Venue: arXiv cs.RO 2021
Year: 2021

This paper investigates the use of LiDAR SLAM as a pose feedback for autonomous flight. Cartographer, LOAM and HDL graph SLAM are first introduced on a conceptual level and later tested for this role. They are first compared offline on a series of datasets to see if they are capable of producing high-quality pose estimates in agile and long-range flight scenarios. The second stage of testing consists of integrating the SLAM algorithms into a cascade PID UAV control system and comparing the control system performance on step excitation signals and helical trajectories. The comparison is based on step response characteristics and several time integral performancecriteria as well as the RMS error between planned and executed trajectory.
Fairness in Biometrics: a figure of merit to assess biometric verification systems
Venue: arXiv cs.CV 2021
Year: 2021

Machine learning-based (ML) systems are being largely deployed since the last decade in a myriad of scenarios impacting several instances in our daily lives. With this vast sort of applications, aspects of fairness start to rise in the spotlight due to the social impact that this can get in minorities. In this work aspects of fairness in biometrics are addressed. First, we introduce the first figure of merit that is able to evaluate and compare fairness aspects between multiple biometric verification systems, the so-called Fairness Discrepancy Rate (FDR). A use case with two synthetic biometric systems is introduced and demonstrates the potential of this figure of merit in extreme cases of fair and unfair behavior. Second, a use case using face biometrics is presented where several systems are evaluated compared with this new figure of merit using three public datasets exploring gender and race demographics.
Offline Reinforcement Learning from Human Feedback in Real-World Sequence-to-Sequence Tasks
Venue: arXiv cs.CL 2021
Year: 2021

Large volumes of interaction logs can be collected from NLP systems that are deployed in the real world. How can this wealth of information be leveraged? Using such interaction logs in an offline reinforcement learning (RL) setting is a promising approach. However, due to the nature of NLP tasks and the constraints of production systems, a series of challenges arise. We present a concise overview of these challenges and discuss possible solutions.
Re-Assessing the "Classify and Count" Quantification Method
Venue: arXiv cs.LG 2021
Year: 2021

Learning to quantify (a.k.a.\ quantification) is a task concerned with training unbiased estimators of class prevalence via supervised learning. This task originated with the observation that "Classify and Count" (CC), the trivial method of obtaining class prevalence estimates, is often a biased estimator, and thus delivers suboptimal quantification accuracy; following this observation, several methods for learning to quantify have been proposed that have been shown to outperform CC. In this work we contend that previous works have failed to use properly optimised versions of CC. We thus reassess the real merits of CC (and its variants), and argue that, while still inferior to some cutting-edge methods, they deliver near-state-of-the-art accuracy once (a) hyperparameter optimisation is performed, and (b) this optimisation is performed by using a true quantification loss instead of a standard classification-based loss. Experiments on three publicly available binary sentiment classification datasets support these conclusions.
Fast, Exact and Scalable Dynamic Ridesharing
Venue: arXiv cs.DS 2021
Year: 2021

We study the problem of servicing a set of ride requests by dispatching a set of shared vehicles, which is faced by ridesharing companies such as Uber and Lyft. Solving this problem at a large scale might be crucial in the future for effectively using large fleets of autonomous vehicles. Since finding a solution for the entire set of requests that minimizes the total driving time is NP-complete, most practical approaches process the requests one by one. Each request is inserted into any vehicle's route such that the increase in driving time is minimized. Although this variant is solvable in polynomial time, it still takes considerable time in current implementations, even when inexact filtering heuristics are used. In this work, we present a novel algorithm for finding best insertions, based on (customizable) contraction hierarchies with local buckets. Our algorithm finds provably exact solutions, is still 30 times faster than a state-of-the-art algorithm currently used in industry and academia, and scales much better. When used within iterative transport simulations, our algorithm decreases the simulation time for largescale scenarios with many requests from days to hours.
Deep-Dup: An Adversarial Weight Duplication Attack Framework to Crush Deep Neural Network in Multi-Tenant FPGA
Venue: arXiv cs.CR 2021
Year: 2021

The wide deployment of Deep Neural Networks (DNN) in high-performance cloud computing platforms brought to light multi-tenant cloud field-programmable gate arrays (FPGA) as a popular choice of accelerator to boost performance due to its hardware reprogramming flexibility. Such a multi-tenant FPGA setup for DNN acceleration potentially exposes DNN interference tasks under severe threat from malicious users. This work, to the best of our knowledge, is the first to explore DNN model vulnerabilities in multi-tenant FPGAs. We propose a novel adversarial attack framework: Deep-Dup, in which the adversarial tenant can inject adversarial faults to the DNN model in the victim tenant of FPGA. Specifically, she can aggressively overload the shared power distribution system of FPGA with malicious power-plundering circuits, achieving adversarial weight duplication (AWD) hardware attack that duplicates certain DNN weight packages during data transmission between off-chip memory and on-chip buffer, to hijack the DNN function of the victim tenant. Further, to identify the most vulnerable DNN weight packages for a given malicious objective, we propose a generic vulnerable weight package searching algorithm, called Progressive Differential Evolution Search (P-DES), which is, for the first time, adaptive to both deep learning white-box and black-box attack models. The proposed Deep-Dup is experimentally validated in a developed multi-tenant FPGA prototype, for two popular deep learning applications, i.e., Object Detection and Image Classification. Successful attacks are demonstrated in six popular DNN architectures (e.g., YOLOv2, ResNet-50, MobileNet, etc.)
Iterated multiplication in $VTC^0$
Venue: arXiv cs.LO 2021
Year: 2021

We show that $VTC^0$, the basic theory of bounded arithmetic corresponding to the complexity class $\mathrm{TC}^0$, proves the $IMUL$ axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the $\mathrm{TC}^0$ iterated multiplication algorithm by Hesse, Allender, and Barrington. As a consequence, $VTC^0$ can also prove the integer division axiom, and (by our previous results) the RSUV-translation of induction and minimization for sharply bounded formulas. Similar consequences hold for the related theories $Δ^b_1$-$CR$ and $C^0_2$. As a side result, we also prove that there is a well-behaved $Δ_0$ definition of modular powering in $IΔ_0+WPHP(Δ_0)$.
IMU-Assisted Learning of Single-View Rolling Shutter Correction
Venue: arXiv cs.CV 2021
Year: 2021

Rolling shutter distortion is highly undesirable for photography and computer vision algorithms (e.g., visual SLAM) because pixels can be potentially captured at different times and poses. In this paper, we propose a deep neural network to predict depth and row-wise pose from a single image for rolling shutter correction. Our contribution in this work is to incorporate inertial measurement unit (IMU) data into the pose refinement process, which, compared to the state-of-the-art, greatly enhances the pose prediction. The improved accuracy and robustness make it possible for numerous vision algorithms to use imagery captured by rolling shutter cameras and produce highly accurate results. We also extend a dataset to have real rolling shutter images, IMU data, depth maps, camera poses, and corresponding global shutter images for rolling shutter correction training. We demonstrate the efficacy of the proposed method by evaluating the performance of Direct Sparse Odometry (DSO) algorithm on rolling shutter imagery corrected using the proposed approach. Results show marked improvements of the DSO algorithm over using uncorrected imagery, validating the proposed approach.
Transforming Fading Channel from Fast to Slow: IRS-Assisted High-Mobility Communication
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we study a new intelligent refracting surface (IRS)-assisted high-mobility communication with the IRS deployed in a high-speed moving vehicle to assist its passenger's communication with a static base station (BS) on the roadside. The vehicle's high Doppler frequency results in a fast fading channel between the BS and the passenger/user, which renders channel estimation for the IRS with a large number of refracting elements a more challenging task as compared to the conventional case with low-mobility users only. In order to mitigate the Doppler effect and reap the full IRS passive beamforming gain with low training overhead, we propose a new and efficient transmission protocol to execute channel estimation and IRS refraction design for data transmission. Specifically, by exploiting the quasi-static channel between the IRS and user both moving at the same high speed, we first estimate the cascaded BS-IRS-user channel with the Doppler effect compensated. Then, we estimate the instantaneous BS-user fast fading channel (without IRS refraction) and tune the IRS refraction over time accordingly to align the cascaded channel with the BS-user direct channel, thus maximizing the IRS's passive beamforming gain as well as converting their combined channel from fast to slow fading. Simulation results show the effectiveness of the proposed channel estimation scheme and passive beamforming design as compared to various benchmark schemes.
A fast learning algorithm for One-Class Slab Support Vector Machines
Venue: arXiv cs.LG 2021
Year: 2021

One Class Slab Support Vector Machines (OCSSVM) have turned out to be better in terms of accuracy in certain classes of classification problems than the traditional SVMs and One Class SVMs or even other One class classifiers. This paper proposes fast training method for One Class Slab SVMs using an updated Sequential Minimal Optimization (SMO) which divides the multi variable optimization problem to smaller sub problems of size two that can then be solved analytically. The results indicate that this training method scales better to large sets of training data than other Quadratic Programming (QP) solvers.
Sensitivity Oracles for All-Pairs Mincuts
Venue: arXiv cs.DS 2021
Year: 2021

Let $G=(V,E)$ be an undirected unweighted graph on $n$ vertices and $m$ edges. We address the problem of sensitivity oracle for all-pairs mincuts in $G$ defined as follows. Build a compact data structure that, on receiving any pair of vertices $s,t\in V$ and failure (or insertion) of any edge as query, can efficiently report the mincut between $s$ and $t$ after the failure (or the insertion). To the best of our knowledge, there exists no data structure for this problem which takes $o(mn)$ space and a non-trivial query time. We present the following results. - Our first data structure occupies ${\cal O}(n^2)$ space and guarantees ${\cal O}(1)$ query time to report the value of resulting $(s,t)$-mincut upon failure (or insertion) of any edge. Moreover, the set of vertices defining a resulting $(s,t)$-mincut after the update can be reported in ${\cal O}(n)$ time which is worst-case optimal. - Our second data structure optimizes space at the expense of increased query time. It takes ${\cal O}(m)$ space -- which is also the space taken by $G$. The query time is ${\cal O}(\min(m,n c_{s,t}))$ where $c_{s,t}$ is the value of the mincut between $s$ and $t$ in $G$. This query time is faster by a factor of $Ω(\min(m^{1/3},\sqrt{n}))$ compared to the best known deterministic algorithm to compute a $(s,t)$-mincut from scratch. - If we are only interested in knowing if failure (or insertion) of an edge changes the value of $(s,t)$-mincut, we can distribute our ${\cal O}(n^2)$ space data structure evenly among $n$ vertices. For any failed (or inserted) edge we only require the data structures stored at its endpoints to determine if the value of $(s,t)$-mincut has changed for any $s,t \in V$.
Digital Nudging with Recommender Systems: Survey and Future Directions
Venue: arXiv cs.HC 2021
Year: 2021

Recommender systems are nowadays a pervasive part of our online user experience, where they either serve as information filters or provide us with suggestions for additionally relevant content. These systems thereby influence which information is easily accessible to us and thus affect our decision-making processes though the automated selection and ranking of the presented content. Automated recommendations can therefore be seen as digital nudges, because they determine different aspects of the choice architecture for users. In this work, we examine the relationship between digital nudging and recommender systems, topics that so far were mostly investigated in isolation. Through a systematic literature search, we first identified 87 nudging mechanisms, which we categorize in a novel taxonomy. A subsequent analysis then shows that only a small part of these nudging mechanisms was previously investigated in the context of recommender systems. This indicates that there is a huge potential to develop future recommender systems that leverage the power of digital nudging in order to influence the decision-making of users. In this work, we therefore outline potential ways of integrating nudging mechanisms into recommender systems.
Settling the Robust Learnability of Mixtures of Gaussians
Venue: arXiv cs.DS 2021
Year: 2021

This work represents a natural coalescence of two important lines of work: learning mixtures of Gaussians and algorithmic robust statistics. In particular we give the first provably robust algorithm for learning mixtures of any constant number of Gaussians. We require only mild assumptions on the mixing weights (bounded fractionality) and that the total variation distance between components is bounded away from zero. At the heart of our algorithm is a new method for proving dimension-independent polynomial identifiability through applying a carefully chosen sequence of differential operations to certain generating functions that not only encode the parameters we would like to learn but also the system of polynomial equations we would like to solve. We show how the symbolic identities we derive can be directly used to analyze a natural sum-of-squares relaxation.
Identifying Mislabeled Images in Supervised Learning Utilizing Autoencoder
Venue: arXiv cs.CV 2021
Year: 2021

Supervised learning is based on the assumption that the ground truth in the training data is accurate. However, this may not be guaranteed in real-world settings. Inaccurate training data will result in some unexpected predictions. In image classification, incorrect labels may cause the classification model to be inaccurate as well. In this paper, I am going to apply unsupervised techniques to the training data before training the classification network. A convolutional autoencoder is applied to encode and reconstruct images. The encoder will project the image data on to latent space. In the latent space, image features are preserved in a lower dimension. The assumption is that data samples with similar features are likely to have the same label. Noised samples can be classified in the latent space by the Density-Base Scan (DBSCAN) clustering algorithm. These incorrectly labeled data are visualized as outliers in the latent space. Therefore, the outliers identified by the DBSCAN algorithm can be classified as incorrectly labeled samples. After the outliers are detected, all the outliers are treated as mislabeled data samples and removed from the dataset. Thus the training data can be directly used in training the supervised learning network. The algorithm can detect and remove above 67\% of mislabeled data in the experimental dataset.
Exploiting User Mobility for WiFi RTT Positioning: A Geometric Approach
Venue: arXiv cs.NI 2021
Year: 2021

Recently, round-trip time (RTT) measured by a fine-timing measurement protocol has received great attention in the area of WiFi positioning. It provides an acceptable ranging accuracy in favorable environments when a line-of-sight (LOS) path exists. Otherwise, a signal is detoured along with non-LOS paths, making the resultant ranging results different from the ground-truth, called an RTT bias, which is the main reason for poor positioning performance. To address it, we aim at leveraging the user mobility trajectory detected by a smartphone's inertial measurement units, called pedestrian dead reckoning (PDR). Specifically, PDR provides the geographic relation among adjacent locations, guiding the resultant positioning estimates' sequence not to deviate from the user trajectory. To this end, we describe their relations as multiple geometric equations, enabling us to render a novel positioning algorithm with acceptable accuracy. Depending on the mobility pattern being linear or arbitrary, we develop different algorithms divided into two phases. First, we can jointly estimate an RTT bias of each AP and the user's step length by leveraging the geometric relation mentioned above. It enables us to construct a user's relative trajectory defined on the concerned AP's local coordinate system. Second, we align every AP's relative trajectory into a single one, called trajectory alignment, equivalent to transformation to the global coordinate system. As a result, we can estimate the sequence of the user's absolute locations from the aligned trajectory. Various field experiments extensively verify the proposed algorithm's effectiveness that the average positioning error is approximately 0.369 (m) and 1.705 (m) in LOS and NLOS environments, respectively.
How Likely Are Large Elections Tied?
Venue: arXiv cs.GT 2021
Year: 2021

Understanding the likelihood for an election to be tied is a classical topic in many disciplines including social choice, game theory, political science, and public choice. Despite a large body of literature and the common belief that ties are rare, little is known about how rare ties are in large elections except for a few simple positional scoring rules under the i.i.d. uniform distribution over the votes, known as the Impartial Culture (IC) in social choice. In particular, little progress was made after Marchant explicitly posed the likelihood of k-way ties under IC as an open question in 2001. We give an asymptotic answer to the open question for a wide range of commonly studied voting rules under a model that is much more general and realistic than i.i.d. models (especially IC) -- the smoothed social choice framework by Xia that was inspired by the celebrated smoothed complexity analysis by Spielman and Teng. We prove dichotomy theorems on the smoothed likelihood of ties under positional scoring rules, edge-order-based rules, and some multi-round score-based elimination rules, which include commonly studied voting rules such as plurality, Borda, veto, maximin, Copeland, ranked pairs, Schulze, STV, and Coombs as special cases. We also complement the theoretical results by experiments on synthetic data and real-world rank data on Preflib. Our main technical tool is an improved dichotomous characterization on the smoothed likelihood for a Poisson multinomial variable to be in a polyhedron, which is proved by exploring the interplay between the V-representation and the matrix representation of polyhedra and might be of independent interest.
Multi-Modal Learning of Keypoint Predictive Models for Visual Object Manipulation
Venue: arXiv cs.RO 2021
Year: 2021

Humans have impressive generalization capabilities when it comes to manipulating objects and tools in completely novel environments. These capabilities are, at least partially, a result of humans having internal models of their bodies and any grasped object. How to learn such body schemas for robots remains an open problem. In this work, we develop an self-supervised approach that can extend a robot's kinematic model when grasping an object from visual latent representations. Our framework comprises two components: (1) we present a multi-modal keypoint detector: an autoencoder architecture trained by fusing proprioception and vision to predict visual key points on an object; (2) we show how we can use our learned keypoint detector to learn an extension of the kinematic chain by regressing virtual joints from the predicted visual keypoints. Our evaluation shows that our approach learns to consistently predict visual keypoints on objects in the manipulator's hand, and thus can easily facilitate learning an extended kinematic chain to include the object grasped in various configurations, from a few seconds of visual data. Finally we show that this extended kinematic chain lends itself for object manipulation tasks such as placing a grasped object and present experiments in simulation and on hardware.
The algebra of binary trees is affine complete
Venue: arXiv cs.FL 2021
Year: 2021

A function on an algebra is congruence preserving if, for any congruence, it maps pairs of congruent elements onto pairs of congruent elements. We show that on the algebra of binary trees whose leaves are labeled by letters of an alphabet containing at least three letters, a function is congruence preserving if and only if it is polynomial.
Gaussian Processes with Skewed Laplace Spectral Mixture Kernels for Long-term Forecasting
Venue: arXiv cs.AI 2021
Year: 2021

Long-term forecasting involves predicting a horizon that is far ahead of the last observation. It is a problem of high practical relevance, for instance for companies in order to decide upon expensive long-term investments. Despite the recent progress and success of Gaussian processes (GPs) based on spectral mixture kernels, long-term forecasting remains a challenging problem for these kernels because they decay exponentially at large horizons. This is mainly due to their use of a mixture of Gaussians to model spectral densities. Characteristics of the signal important for long-term forecasting can be unravelled by investigating the distribution of the Fourier coefficients of (the training part of) the signal, which is non-smooth, heavy-tailed, sparse, and skewed. The heavy tail and skewness characteristics of such distributions in the spectral domain allow to capture long-range covariance of the signal in the time domain. Motivated by these observations, we propose to model spectral densities using a skewed Laplace spectral mixture (SLSM) due to the skewness of its peaks, sparsity, non-smoothness, and heavy tail characteristics. By applying the inverse Fourier Transform to this spectral density we obtain a new GP kernel for long-term forecasting. In addition, we adapt the lottery ticket method, originally developed to prune weights of a neural network, to GPs in order to automatically select the number of kernel components. Results of extensive experiments, including a multivariate time series, show the beneficial effect of the proposed SLSM kernel for long-term extrapolation and robustness to the choice of the number of mixture components.