OpenRaiser/Intern-Atlas huggingface dataset:
Truly Tight-in-$Δ$ Bounds for Bipartite Maximal Matching and Variants
Venue: arXiv cs.DC 2020
Year: 2020

In a recent breakthrough result, Balliu et al. [FOCS'19] proved a deterministic $Ω(\min(Δ,\log n /\log \log n))$-round and a randomized $Ω(\min(Δ,\log \log n/\log \log \log n))$-round lower bound for the complexity of the bipartite maximal matching problem on $n$-node graphs in the LOCAL model of distributed computing. Both lower bounds are asymptotically tight as a function of the maximum degree $Δ$. We provide truly tight bounds in $Δ$ for the complexity of bipartite maximal matching and many natural variants, up to and including the additive constant. As a by-product, our results yield a considerably simplified version of the proof by Balliu et al. We show that our results can be obtained via bounded automatic round elimination, a version of the recent automatic round elimination technique by Brandt [PODC'19] that is particularly suited for automatization from a practical perspective. In this context, our work can be seen as another step towards the automatization of lower bounds in the LOCAL model.
Knapsack Pruning with Inner Distillation
Venue: arXiv cs.LG 2020
Year: 2020

Neural network pruning reduces the computational cost of an over-parameterized network to improve its efficiency. Popular methods vary from $\ell_1$-norm sparsification to Neural Architecture Search (NAS). In this work, we propose a novel pruning method that optimizes the final accuracy of the pruned network and distills knowledge from the over-parameterized parent network's inner layers. To enable this approach, we formulate the network pruning as a Knapsack Problem which optimizes the trade-off between the importance of neurons and their associated computational cost. Then we prune the network channels while maintaining the high-level structure of the network. The pruned network is fine-tuned under the supervision of the parent network using its inner network knowledge, a technique we refer to as the Inner Knowledge Distillation. Our method leads to state-of-the-art pruning results on ImageNet, CIFAR-10 and CIFAR-100 using ResNet backbones. To prune complex network structures such as convolutions with skip-links and depth-wise convolutions, we propose a block grouping approach to cope with these structures. Through this we produce compact architectures with the same FLOPs as EfficientNet-B0 and MobileNetV3 but with higher accuracy, by $1\%$ and $0.3\%$ respectively on ImageNet, and faster runtime on GPU.
Compressing BERT: Studying the Effects of Weight Pruning on Transfer Learning
Venue: arXiv cs.CL 2020
Year: 2020

Pre-trained universal feature extractors, such as BERT for natural language processing and VGG for computer vision, have become effective methods for improving deep learning models without requiring more labeled data. While effective, feature extractors like BERT may be prohibitively large for some deployment scenarios. We explore weight pruning for BERT and ask: how does compression during pre-training affect transfer learning? We find that pruning affects transfer learning in three broad regimes. Low levels of pruning (30-40%) do not affect pre-training loss or transfer to downstream tasks at all. Medium levels of pruning increase the pre-training loss and prevent useful pre-training information from being transferred to downstream tasks. High levels of pruning additionally prevent models from fitting downstream datasets, leading to further degradation. Finally, we observe that fine-tuning BERT on a specific task does not improve its prunability. We conclude that BERT can be pruned once during pre-training rather than separately for each task without affecting performance.
Simultaneous games with purchase of randomly supplied perfect information: Oracle Games
Venue: arXiv cs.GT 2020
Year: 2020

We study the role of costly information in non-cooperative two-player games when an extrinsic third party information broker is introduced asymmetrically, allowing one player to obtain information about the other player's action. This broker or "oracle" is defined by a probability of response, supplying correct information randomly; the informed player can pay more for a higher probability of response. We determine the necessary and sufficient conditions for strategy profiles to be equilibria, in terms of how both players change their strategies in response to the existence of the oracle, as determined by its cost of information function. For mixed strategy equilibria, there is a continuous change as information becomes cheaper, with clear transitions occuring at critical {\it nodes} at which pure strategies become dominated (or undominated). These nodes separate distinct responses to the information for sale, alternating between regions where the paying player increases the amount of information purchased, and regions where the other player moves away from riskier strategies, in favor of safer bets that minimize losses. We derive conditions for these responses by defining a value of information.
An improved nonlinear FastEuler AHRS estimation based on the SVDCKF algorithm
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we present a Singular Value Decomposition Cubature Kalman Filter(SVDCKF) fusion algorithm based on the improved nonlinear FastEuler Attitude and Heading Reference and System(AHRS) estimation model for small-UAV attitude. The contributions of this work are the derivation of the low-cost IMU/MAG integrated AHRS model combined with the quaternion attitude determination, and use the FastEuler to correct the gyroscope attitude update, which can increase the real-time solution. In addition, the SVDCKF algorithm is fused the various raw sensors data in order to improve the filter accuracy compared with the CKF. The simulation and experiment results demonstrate the proposed algorithm has the more excellent attitude solution accuracy compared with the CKF in the low and high dynamic flight conditions.
Balancing Efficiency and Flexibility for DNN Acceleration via Temporal GPU-Systolic Array Integration
Venue: arXiv cs.DC 2020
Year: 2020

The research interest in specialized hardware accelerators for deep neural networks (DNN) spikes recently owing to their superior performance and efficiency. However, today's DNN accelerators primarily focus on accelerating specific "kernels" such as convolution and matrix multiplication, which are vital but only part of an end-to-end DNN-enabled application. Meaningful speedups over the entire application often require supporting computations that are, while massively parallel, ill-suited to DNN accelerators. Integrating a general-purpose processor such as a CPU or a GPU incurs significant data movement overhead and leads to resource under-utilization on the DNN accelerators. We propose Simultaneous Multi-mode Architecture (SMA), a novel architecture design and execution model that offers general-purpose programmability on DNN accelerators in order to accelerate end-to-end applications. The key to SMA is the temporal integration of the systolic execution model with the GPU-like SIMD execution model. The SMA exploits the common components shared between the systolic-array accelerator and the GPU, and provides lightweight reconfiguration capability to switch between the two modes in-situ. The SMA achieves up to 63% performance improvement while consuming 23% less energy than the baseline Volta architecture with TensorCore.
Fawkes: Protecting Privacy against Unauthorized Deep Learning Models
Venue: arXiv cs.CR 2020
Year: 2020

Today's proliferation of powerful facial recognition systems poses a real threat to personal privacy. As Clearview.ai demonstrated, anyone can canvas the Internet for data and train highly accurate facial recognition models of individuals without their knowledge. We need tools to protect ourselves from potential misuses of unauthorized facial recognition systems. Unfortunately, no practical or effective solutions exist. In this paper, we propose Fawkes, a system that helps individuals inoculate their images against unauthorized facial recognition models. Fawkes achieves this by helping users add imperceptible pixel-level changes (we call them "cloaks") to their own photos before releasing them. When used to train facial recognition models, these "cloaked" images produce functional models that consistently cause normal images of the user to be misidentified. We experimentally demonstrate that Fawkes provides 95+% protection against user recognition regardless of how trackers train their models. Even when clean, uncloaked images are "leaked" to the tracker and used for training, Fawkes can still maintain an 80+% protection success rate. We achieve 100% success in experiments against today's state-of-the-art facial recognition services. Finally, we show that Fawkes is robust against a variety of countermeasures that try to detect or disrupt image cloaks.
Designing spontaneous behavioral switching via chaotic itinerancy
Venue: arXiv cs.RO 2020
Year: 2020

Chaotic itinerancy is a frequently observed phenomenon in high-dimensional and nonlinear dynamical systems, and it is characterized by the random transitions among multiple quasi-attractors. Several studies have revealed that chaotic itinerancy has been observed in brain activity, and it is considered to play a critical role in the spontaneous, stable behavior generation of animals. Thus, chaotic itinerancy is a topic of great interest, particularly for neurorobotics researchers who wish to understand and implement autonomous behavioral controls for agents. However, it is generally difficult to gain control over high-dimensional nonlinear dynamical systems. Hence, the implementation of chaotic itinerancy has mainly been accomplished heuristically. In this study, we propose a novel way of implementing chaotic itinerancy reproducibly and at will in a generic high-dimensional chaotic system. In particular, we demonstrate that our method enables us to easily design both the trajectories of quasi-attractors and the transition rules among them simply by adjusting the limited number of system parameters and by utilizing the intrinsic high-dimensional chaos. Finally, we quantitatively discuss the validity and scope of application through the results of several numerical experiments.
Deep Learning of Movement Intent and Reaction Time for EEG-informed Adaptation of Rehabilitation Robots
Venue: arXiv cs.RO 2020
Year: 2020

Mounting evidence suggests that adaptation is a crucial mechanism for rehabilitation robots in promoting motor learning. Yet, it is commonly based on robot-derived movement kinematics, which is a rather subjective measurement of performance, especially in the presence of a sensorimotor impairment. Here, we propose a deep convolutional neural network (CNN) that uses electroencephalography (EEG) as an objective measurement of two kinematics components that are typically used to assess motor learning and thereby adaptation: i) the intent to initiate a goal-directed movement, and ii) the reaction time (RT) of that movement. We evaluated our CNN on data acquired from an in-house experiment where 13 subjects moved a rehabilitation robotic arm in four directions on a plane, in response to visual stimuli. Our CNN achieved average test accuracies of 80.08% and 79.82% in a binary classification of the intent (intent vs. no intent) and RT (slow vs. fast), respectively. Our results demonstrate how individual movement components implicated in distinct types of motor learning can be predicted from synchronized EEG data acquired before the start of the movement. Our approach can, therefore, inform robotic adaptation in real-time and has the potential to further improve one's ability to perform the rehabilitation task.
Residual-Sparse Fuzzy $C$-Means Clustering Incorporating Morphological Reconstruction and Wavelet frames
Venue: arXiv cs.CV 2020
Year: 2020

Instead of directly utilizing an observed image including some outliers, noise or intensity inhomogeneity, the use of its ideal value (e.g. noise-free image) has a favorable impact on clustering. Hence, the accurate estimation of the residual (e.g. unknown noise) between the observed image and its ideal value is an important task. To do so, we propose an $\ell_0$ regularization-based Fuzzy $C$-Means (FCM) algorithm incorporating a morphological reconstruction operation and a tight wavelet frame transform. To achieve a sound trade-off between detail preservation and noise suppression, morphological reconstruction is used to filter an observed image. By combining the observed and filtered images, a weighted sum image is generated. Since a tight wavelet frame system has sparse representations of an image, it is employed to decompose the weighted sum image, thus forming its corresponding feature set. Taking it as data for clustering, we present an improved FCM algorithm by imposing an $\ell_0$ regularization term on the residual between the feature set and its ideal value, which implies that the favorable estimation of the residual is obtained and the ideal value participates in clustering. Spatial information is also introduced into clustering since it is naturally encountered in image segmentation. Furthermore, it makes the estimation of the residual more reliable. To further enhance the segmentation effects of the improved FCM algorithm, we also employ the morphological reconstruction to smoothen the labels generated by clustering. Finally, based on the prototypes and smoothed labels, the segmented image is reconstructed by using a tight wavelet frame reconstruction operation. Experimental results reported for synthetic, medical, and color images show that the proposed algorithm is effective and efficient, and outperforms other algorithms.
Cooperative LIDAR Object Detection via Feature Sharing in Deep Networks
Venue: arXiv cs.CV 2020
Year: 2020

The recent advancements in communication and computational systems has led to significant improvement of situational awareness in connected and autonomous vehicles. Computationally efficient neural networks and high speed wireless vehicular networks have been some of the main contributors to this improvement. However, scalability and reliability issues caused by inherent limitations of sensory and communication systems are still challenging problems. In this paper, we aim to mitigate the effects of these limitations by introducing the concept of feature sharing for cooperative object detection (FS-COD). In our proposed approach, a better understanding of the environment is achieved by sharing partially processed data between cooperative vehicles while maintaining a balance between computation and communication load. This approach is different from current methods of map sharing, or sharing of raw data which are not scalable. The performance of the proposed approach is verified through experiments on Volony dataset. It is shown that the proposed approach has significant performance superiority over the conventional single-vehicle object detection approaches.
A Recurrent Neural Network Based Patch Recommender for Linux Kernel Bugs
Venue: arXiv cs.SE 2020
Year: 2020

Software bugs in a production environment have an undesirable impact on quality of service, unplanned system downtime, and disruption in good customer experience, resulting in loss of revenue and reputation. Existing approaches to automated software bug repair focuses on known bug templates detected using static code analysis tools and test suites, and in automatic generation of patch code for these bugs. We describe the typical bug fixing process employed in the Linux kernel, and motivate the need for a new automated tool flow to fix bugs. We present an initial design of such an automated tool that uses Recurrent Neural Network (RNN) based Natural Language Processing to generate patch recommendations from user generated bug reports. At the 50th percentile of the test bugs, the correct patch occurs within the top 11.5 patch recommendations output by the model. Further, we present a Linux kernel developer's assessment of the quality of patches recommended for new unresolved kernel bugs.
Caveats in Eliciting Mobile App Requirements
Venue: arXiv cs.SE 2020
Year: 2020

Factors such as app stores or platform choices heavily affect functional and non-functional mobile app requirements. We surveyed 45 companies and interviewed ten experts to explore how factors that impact mobile app requirements are understood by requirements engineers in the mobile app industry. We observed a lack of knowledge in several areas. For instance, we observed that all practitioners were aware of data privacy concerns, however, they did not know that certain third-party libraries, usage aggregators, or advertising libraries also occasionally leak sensitive user data. Similarly, certain functional requirements may not be implementable in the absence of a third-party library that is either banned from an app store for policy violations or lacks features, for instance, missing desired features in ARKit library for iOS made practitioners turn to Android. We conclude that requirements engineers should have adequate technical experience with mobile app development as well as sufficient knowledge in areas such as privacy, security and law, in order to make informed decisions during requirements elicitation.
Processing topical queries on images of historical newspaper pages
Venue: arXiv cs.IR 2020
Year: 2020

Historical newspapers are a source of research for the human and social sciences. However, these image collections are difficult to read by machine due to the low quality of the print, the lack of standardization of the pages in addition to the low quality photograph of some files. This paper presents the processing model of a topic navigation system in historical newspaper page images. The general procedure consists of four modules which are: segmentation of text sub-images and text extraction, preprocessing and representation, induced topic extraction and representation, and document viewing and retrieval interface. The algorithmic and technological approaches of each module are described and the initial test results about a collection covering a range of 28 years are presented.
Adaptive Sampling Distributed Stochastic Variance Reduced Gradient for Heterogeneous Distributed Datasets
Venue: arXiv cs.LG 2020
Year: 2020

We study distributed optimization algorithms for minimizing the average of \emph{heterogeneous} functions distributed across several machines with a focus on communication efficiency. In such settings, naively using the classical stochastic gradient descent (SGD) or its variants (e.g., SVRG) with a uniform sampling of machines typically yields poor performance. It often leads to the dependence of convergence rate on maximum Lipschitz constant of gradients across the devices. In this paper, we propose a novel \emph{adaptive} sampling of machines specially catered to these settings. Our method relies on an adaptive estimate of local Lipschitz constants base on the information of past gradients. We show that the new way improves the dependence of convergence rate from maximum Lipschitz constant to \emph{average} Lipschitz constant across machines, thereby, significantly accelerating the convergence. Our experiments demonstrate that our method indeed speeds up the convergence of the standard SVRG algorithm in heterogeneous environments.
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
Venue: arXiv cs.CC 2020
Year: 2020

The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be the maximum $k$-party NOF randomized communication complexity of $\mathcal{G}$. We show: (1) The Generalized Inner Product function $GIP^k_n$ cannot be computed in $FORMULA[s]\circ \mathcal{G}$ on more than $1/2+\varepsilon$ fraction of inputs for $$ s = o \! \left ( \frac{n^2}{ \left(k \cdot 4^k \cdot {R}^{(k)}(\mathcal{G}) \cdot \log (n/\varepsilon) \cdot \log(1/\varepsilon) \right)^{2}} \right).$$ As a corollary, we get an average-case lower bound for $GIP^k_n$ against $FORMULA[n^{1.99}]\circ PTF^{k-1}$. (2) There is a PRG of seed length $n/2 + O\left(\sqrt{s} \cdot R^{(2)}(\mathcal{G}) \cdot\log(s/\varepsilon) \cdot \log (1/\varepsilon) \right)$ that $\varepsilon$-fools $FORMULA[s] \circ \mathcal{G}$. For $FORMULA[s] \circ LTF$, we get the better seed length $O\left(n^{1/2}\cdot s^{1/4}\cdot \log(n)\cdot \log(n/\varepsilon)\right)$. This gives the first non-trivial PRG (with seed length $o(n)$) for intersections of $n$ half-spaces in the regime where $\varepsilon \leq 1/n$. (3) There is a randomized $2^{n-t}$-time $\#$SAT algorithm for $FORMULA[s] \circ \mathcal{G}$, where $$t=Ω\left(\frac{n}{\sqrt{s}\cdot\log^2(s)\cdot R^{(2)}(\mathcal{G})}\right)^{1/2}.$$ In particular, this implies a nontrivial #SAT algorithm for $FORMULA[n^{1.99}]\circ LTF$. (4) The Minimum Circuit Size Problem is not in $FORMULA[n^{1.99}]\circ XOR$. On the algorithmic side, we show that $FORMULA[n^{1.99}] \circ XOR$ can be PAC-learned in time $2^{O(n/\log n)}$.
Fast and Regularized Reconstruction of Building Façades from Street-View Images using Binary Integer Programming
Venue: arXiv cs.CV 2020
Year: 2020

Regularized arrangement of primitives on building façades to aligned locations and consistent sizes is important towards structured reconstruction of urban environment. Mixed integer linear programing was used to solve the problem, however, it is extreamly time consuming even for state-of-the-art commercial solvers. Aiming to alleviate this issue, we cast the problem into binary integer programming, which omits the requirements for real value parameters and is more efficient to be solved . Firstly, the bounding boxes of the primitives are detected using the YOLOv3 architecture in real-time. Secondly, the coordinates of the upper left corners and the sizes of the bounding boxes are automatically clustered in a binary integer programming optimization, which jointly considers the geometric fitness, regularity and additional constraints; this step does not require \emph{a priori} knowledge, such as the number of clusters or pre-defined grammars. Finally, the regularized bounding boxes can be directly used to guide the façade reconstruction in an interactive envinronment. Experimental evaluations have revealed that the accuracies for the extraction of primitives are above 0.82, which is sufficient for the following 3D reconstruction. The proposed approach only takes about $ 10\% $ to $ 20\% $ of the runtime than previous approach and reduces the diversity of the bounding boxes to about $20\%$ to $50\%$.
Learning to Walk in the Real World with Minimal Human Effort
Venue: arXiv cs.RO 2020
Year: 2020

Reliable and stable locomotion has been one of the most fundamental challenges for legged robots. Deep reinforcement learning (deep RL) has emerged as a promising method for developing such control policies autonomously. In this paper, we develop a system for learning legged locomotion policies with deep RL in the real world with minimal human effort. The key difficulties for on-robot learning systems are automatic data collection and safety. We overcome these two challenges by developing a multi-task learning procedure and a safety-constrained RL framework. We tested our system on the task of learning to walk on three different terrains: flat ground, a soft mattress, and a doormat with crevices. Our system can automatically and efficiently learn locomotion skills on a Minitaur robot with little human intervention. The supplemental video can be found at: \url{https://youtu.be/cwyiq6dCgOc}.