OpenRaiser/Intern-Atlas huggingface dataset:
Signal-Dependent Performance Analysis of Orthogonal Matching Pursuit for Exact Sparse Recovery
Venue: arXiv cs.IT 2020
Year: 2020

Exact recovery of $K$-sparse signals $x \in \mathbb{R}^{n}$ from linear measurements $y=Ax$, where $A\in \mathbb{R}^{m\times n}$ is a sensing matrix, arises from many applications. The orthogonal matching pursuit (OMP) algorithm is widely used for reconstructing $x$. A fundamental question in the performance analysis of OMP is the characterizations of the probability of exact recovery of $x$ for random matrix $A$ and the minimal $m$ to guarantee a target recovery performance. In many practical applications, in addition to sparsity, $x$ also has some additional properties. This paper shows that these properties can be used to refine the answer to the above question. In this paper, we first show that the prior information of the nonzero entries of $x$ can be used to provide an upper bound on $\|x\|_1^2/\|x\|_2^2$. Then, we use this upper bound to develop a lower bound on the probability of exact recovery of $x$ using OMP in $K$ iterations. Furthermore, we develop a lower bound on the number of measurements $m$ to guarantee that the exact recovery probability using $K$ iterations of OMP is no smaller than a given target probability. Finally, we show that when $K=O(\sqrt{\ln n})$, as both $n$ and $K$ go to infinity, for any $0<ζ\leq 1/\sqrtπ$, $m=2K\ln (n/ζ)$ measurements are sufficient to ensure that the probability of exact recovering any $K$-sparse $x$ is no lower than $1-ζ$ with $K$ iterations of OMP. For $K$-sparse $α$-strongly decaying signals and for $K$-sparse $x$ whose nonzero entries independently and identically follow the Gaussian distribution, the number of measurements sufficient for exact recovery with probability no lower than $1-ζ$ reduces further to $m=(\sqrt{K}+4\sqrt{\frac{α+1}{α-1}\ln(n/ζ)})^2$ and asymptotically $m\approx 1.9K\ln (n/ζ)$, respectively.
Learning to Reason in Round-based Games: Multi-task Sequence Generation for Purchasing Decision Making in First-person Shooters
Venue: arXiv cs.AI 2020
Year: 2020

Sequential reasoning is a complex human ability, with extensive previous research focusing on gaming AI in a single continuous game, round-based decision makings extending to a sequence of games remain less explored. Counter-Strike: Global Offensive (CS:GO), as a round-based game with abundant expert demonstrations, provides an excellent environment for multi-player round-based sequential reasoning. In this work, we propose a Sequence Reasoner with Round Attribute Encoder and Multi-Task Decoder to interpret the strategies behind the round-based purchasing decisions. We adopt few-shot learning to sample multiple rounds in a match, and modified model agnostic meta-learning algorithm Reptile for the meta-learning loop. We formulate each round as a multi-task sequence generation problem. Our state representations combine action encoder, team encoder, player features, round attribute encoder, and economy encoders to help our agent learn to reason under this specific multi-player round-based scenario. A complete ablation study and comparison with the greedy approach certify the effectiveness of our model. Our research will open doors for interpretable AI for understanding episodic and long-term purchasing strategies beyond the gaming community.
ASAP-Net: Attention and Structure Aware Point Cloud Sequence Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

Recent works of point clouds show that mulit-frame spatio-temporal modeling outperforms single-frame versions by utilizing cross-frame information. In this paper, we further improve spatio-temporal point cloud feature learning with a flexible module called ASAP considering both attention and structure information across frames, which we find as two important factors for successful segmentation in dynamic point clouds. Firstly, our ASAP module contains a novel attentive temporal embedding layer to fuse the relatively informative local features across frames in a recurrent fashion. Secondly, an efficient spatio-temporal correlation method is proposed to exploit more local structure for embedding, meanwhile enforcing temporal consistency and reducing computation complexity. Finally, we show the generalization ability of the proposed ASAP module with different backbone networks for point cloud sequence segmentation. Our ASAP-Net (backbone plus ASAP module) outperforms baselines and previous methods on both Synthia and SemanticKITTI datasets (+3.4 to +15.2 mIoU points with different backbones). Code is availabe at https://github.com/intrepidChw/ASAP-Net
PyMGRIT: A Python Package for the parallel-in-time method MGRIT
Venue: arXiv cs.MS 2020
Year: 2020

In this paper, we introduce the Python framework PyMGRIT, which implements the multigrid-reduction-in-time (MGRIT) algorithm for solving the (non-)linear systems arising from the discretization of time-dependent problems. The MGRIT algorithm is a reduction-based iterative method that allows parallel-in-time simulations, i. e., calculating multiple time steps simultaneously in a simulation, by using a time-grid hierarchy. The PyMGRIT framework features many different variants of the MGRIT algorithm, ranging from different multigrid cycle types and relaxation schemes, as well as various coarsening strategies, including time-only and space-time coarsening, to using different time integrators on different levels in the multigrid hierachy. PyMGRIT allows serial runs for prototyping and testing of new approaches, as well as parallel runs using the Message Passing Interface (MPI). Here, we describe the implementation of the MGRIT algorithm in PyMGRIT and present the usage from both user and developer point of views. Three examples illustrate different aspects of the package, including pure time parallelism as well as space-time parallelism by coupling PyMGRIT with PETSc or Firedrake, which enable spatial parallelism through MPI.
Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations
Venue: arXiv cs.DS 2020
Year: 2020

Given a vertex-weighted graph, the maximum weight independent set problem asks for a pair-wise non-adjacent set of vertices such that the sum of their weights is maximum. The branch-and-reduce paradigm is the de facto standard approach to solve the problem to optimality in practice. In this paradigm, data reduction rules are applied to decrease the problem size. These data reduction rules ensure that given an optimum solution on the new (smaller) input, one can quickly construct an optimum solution on the original input. We introduce new generalized data reduction and transformation rules for the problem. A key feature of our work is that some transformation rules can increase the size of the input. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later throughout the algorithm. In experiments, our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than heuristic solvers DynWVC and HILS on many instances. While the increasing transformations are only efficient enough for preprocessing at this time, we see this as a critical initial step towards a new branch-and-transform paradigm.
Who Watches the Watchmen? A Review of Subjective Approaches for Sybil-resistance in Proof of Personhood Protocols
Venue: arXiv cs.CR 2020
Year: 2020

Most current self-sovereign identity systems may be categorized as strictly objective, consisting of cryptographically signed statements issued by trusted third party attestors. This failure to provide an input for subjectivity accounts for a central challenge: the inability to address the question of "Who verifies the verifier?". Instead, these protocols outsource their legitimacy to mechanisms beyond their internal structure, relying on traditional centralized institutions such as national ID issuers and KYC providers to verify the claims they hold. This reliance has been employed to safeguard applications from a vulnerability previously thought to be impossible to address in distributed systems: the Sybil attack problem, which describes the abuse of an online system by creating many illegitimate virtual personas. Inspired by the progress in cryptocurrencies and blockchain technology, there has recently been a surge in networked protocols that make use of subjective inputs such as voting, vouching, and interpreting, to arrive at a decentralized and sybil-resistant consensus for identity. In this article, we will outline the approaches of these new and natively digital sources of authentication -- their attributes, methodologies strengths, and weaknesses -- and sketch out possible directions for future developments.
Soft Sequence Heaps
Venue: arXiv cs.DS 2020
Year: 2020

Chazelle [JACM00] introduced the soft heap as a building block for efficient minimum spanning tree algorithms, and recently Kaplan et al. [SOSA2019] showed how soft heaps can be applied to achieve simpler algorithms for various selection problems. A soft heap trades-off accuracy for efficiency, by allowing $εN$ of the items in a heap to be corrupted after a total of $N$ insertions, where a corrupted item is an item with artificially increased key and $0 < ε\leq 1/2$ is a fixed error parameter. Chazelle's soft heaps are based on binomial trees and support insertions in amortized $O(\lg(1/ε))$ time and extract-min operations in amortized $O(1)$ time. In this paper we explore the design space of soft heaps. The main contribution of this paper is an alternative soft heap implementation based on merging sorted sequences, with time bounds matching those of Chazelle's soft heaps. We also discuss a variation of the soft heap by Kaplan et al. [SICOMP2013], where we avoid performing insertions lazily. It is based on ternary trees instead of binary trees and matches the time bounds of Kaplan et al., i.e. amortized $O(1)$ insertions and amortized $O(\lg(1/ε))$ extract-min. Both our data structures only introduce corruptions after extract-min operations which return the set of items corrupted by the operation.
DAWN: Vehicle Detection in Adverse Weather Nature Dataset
Venue: arXiv cs.CV 2020
Year: 2020

Recently, self-driving vehicles have been introduced with several automated features including lane-keep assistance, queuing assistance in traffic-jam, parking assistance and crash avoidance. These self-driving vehicles and intelligent visual traffic surveillance systems mainly depend on cameras and sensors fusion systems. Adverse weather conditions such as heavy fog, rain, snow, and sandstorms are considered dangerous restrictions of the functionality of cameras impacting seriously the performance of adopted computer vision algorithms for scene understanding (i.e., vehicle detection, tracking, and recognition in traffic scenes). For example, reflection coming from rain flow and ice over roads could cause massive detection errors which will affect the performance of intelligent visual traffic systems. Additionally, scene understanding and vehicle detection algorithms are mostly evaluated using datasets contain certain types of synthetic images plus a few real-world images. Thus, it is uncertain how these algorithms would perform on unclear images acquired in the wild and how the progress of these algorithms is standardized in the field. To this end, we present a new dataset (benchmark) consisting of real-world images collected under various adverse weather conditions called DAWN. This dataset emphasizes a diverse traffic environment (urban, highway and freeway) as well as a rich variety of traffic flow. The DAWN dataset comprises a collection of 1000 images from real-traffic environments, which are divided into four sets of weather conditions: fog, snow, rain and sandstorms. The dataset is annotated with object bounding boxes for autonomous driving and video surveillance scenarios. This data helps interpreting effects caused by the adverse weather conditions on the performance of vehicle detection systems.
Analysing gamification elements in educational environments using an existing Gamification taxonomy
Venue: arXiv cs.HC 2020
Year: 2020

Gamification has been widely employed in the educational domain over the past eight years when the term became a trend. However, the literature states that gamification still lacks formal definitions to support the design and analysis of gamified strategies. This paper analysed the game elements employed in gamified learning environments through a previously proposed and evaluated taxonomy while detailing and expanding this taxonomy. In the current paper, we describe our taxonomy in-depth as well as expand it. Our new structured results demonstrate an extension of the proposed taxonomy which results from this process, is divided into five dimensions, related to the learner and the learning environment. Our main contribution is the detailed taxonomy that can be used to design and evaluate gamification design in learning environments.
The Effects of Object Shape, Fidelity, Color, and Luminance on Depth Perception in Handheld Mobile Augmented Reality
Venue: arXiv cs.HC 2020
Year: 2020

Depth perception of objects can greatly affect a user's experience of an augmented reality (AR) application. Many AR applications require depth matching of real and virtual objects and have the possibility to be influenced by depth cues. Color and luminance are depth cues that have been traditionally studied in two-dimensional (2D) objects. However, there is little research investigating how the properties of three-dimensional (3D) virtual objects interact with color and luminance to affect depth perception, despite the substantial use of 3D objects in visual applications. In this paper, we present the results of a paired comparison experiment that investigates the effects of object shape, fidelity, color, and luminance on depth perception of 3D objects in handheld mobile AR. The results of our study indicate that bright colors are perceived as nearer than dark colors for a high-fidelity, simple 3D object, regardless of hue. Additionally, bright red is perceived as nearer than any other color. These effects were not observed for a low-fidelity version of the simple object or for a more-complex 3D object. High-fidelity objects had more perceptual differences than low-fidelity objects, indicating that fidelity interacts with color and luminance to affect depth perception. These findings reveal how the properties of 3D models influence the effects of color and luminance on depth perception in handheld mobile AR and can help developers select colors for their applications.
Co-training for On-board Deep Object Detection
Venue: arXiv cs.CV 2020
Year: 2020

Providing ground truth supervision to train visual models has been a bottleneck over the years, exacerbated by domain shifts which degenerate the performance of such models. This was the case when visual tasks relied on handcrafted features and shallow machine learning and, despite its unprecedented performance gains, the problem remains open within the deep learning paradigm due to its data-hungry nature. Best performing deep vision-based object detectors are trained in a supervised manner by relying on human-labeled bounding boxes which localize class instances (i.e.objects) within the training images.Thus, object detection is one of such tasks for which human labeling is a major bottleneck. In this paper, we assess co-training as a semi-supervised learning method for self-labeling objects in unlabeled images, so reducing the human-labeling effort for developing deep object detectors. Our study pays special attention to a scenario involving domain shift; in particular, when we have automatically generated virtual-world images with object bounding boxes and we have real-world images which are unlabeled. Moreover, we are particularly interested in using co-training for deep object detection in the context of driver assistance systems and/or self-driving vehicles. Thus, using well-established datasets and protocols for object detection in these application contexts, we will show how co-training is a paradigm worth to pursue for alleviating object labeling, working both alone and together with task-agnostic domain adaptation.
Continual Class Incremental Learning for CT Thoracic Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

Deep learning organ segmentation approaches require large amounts of annotated training data, which is limited in supply due to reasons of confidentiality and the time required for expert manual annotation. Therefore, being able to train models incrementally without having access to previously used data is desirable. A common form of sequential training is fine tuning (FT). In this setting, a model learns a new task effectively, but loses performance on previously learned tasks. The Learning without Forgetting (LwF) approach addresses this issue via replaying its own prediction for past tasks during model training. In this work, we evaluate FT and LwF for class incremental learning in multi-organ segmentation using the publicly available AAPM dataset. We show that LwF can successfully retain knowledge on previous segmentations, however, its ability to learn a new class decreases with the addition of each class. To address this problem we propose an adversarial continual learning segmentation approach (ACLSeg), which disentangles feature space into task-specific and task-invariant features. This enables preservation of performance on past tasks and effective acquisition of new knowledge.
PLACE: Proximity Learning of Articulation and Contact in 3D Environments
Venue: arXiv cs.CV 2020
Year: 2020

High fidelity digital 3D environments have been proposed in recent years, however, it remains extremely challenging to automatically equip such environment with realistic human bodies. Existing work utilizes images, depth or semantic maps to represent the scene, and parametric human models to represent 3D bodies. While being straightforward, their generated human-scene interactions are often lack of naturalness and physical plausibility. Our key observation is that humans interact with the world through body-scene contact. To synthesize realistic human-scene interactions, it is essential to effectively represent the physical contact and proximity between the body and the world. To that end, we propose a novel interaction generation method, named PLACE (Proximity Learning of Articulation and Contact in 3D Environments), which explicitly models the proximity between the human body and the 3D scene around it. Specifically, given a set of basis points on a scene mesh, we leverage a conditional variational autoencoder to synthesize the minimum distances from the basis points to the human body surface. The generated proximal relationship exhibits which region of the scene is in contact with the person. Furthermore, based on such synthesized proximity, we are able to effectively obtain expressive 3D human bodies that interact with the 3D scene naturally. Our perceptual study shows that PLACE significantly improves the state-of-the-art method, approaching the realism of real human-scene interaction. We believe our method makes an important step towards the fully automatic synthesis of realistic 3D human bodies in 3D scenes. The code and model are available for research at https://sanweiliti.github.io/PLACE/PLACE.html.
Graph Drawing via Gradient Descent, $(GD)^2$
Venue: arXiv cs.DS 2020
Year: 2020

Readability criteria, such as distance or neighborhood preservation, are often used to optimize node-link representations of graphs to enable the comprehension of the underlying data. With few exceptions, graph drawing algorithms typically optimize one such criterion, usually at the expense of others. We propose a layout approach, Graph Drawing via Gradient Descent, $(GD)^2$, that can handle multiple readability criteria. $(GD)^2$ can optimize any criterion that can be described by a smooth function. If the criterion cannot be captured by a smooth function, a non-smooth function for the criterion is combined with another smooth function, or auto-differentiation tools are used for the optimization. Our approach is flexible and can be used to optimize several criteria that have already been considered earlier (e.g., obtaining ideal edge lengths, stress, neighborhood preservation) as well as other criteria which have not yet been explicitly optimized in such fashion (e.g., vertex resolution, angular resolution, aspect ratio). We provide quantitative and qualitative evidence of the effectiveness of $(GD)^2$ with experimental data and a functional prototype: \url{http://hdc.cs.arizona.edu/~mwli/graph-drawing/}.
A Differentially Private Game Theoretic Approach for Deceiving Cyber Adversaries
Venue: arXiv cs.CR 2020
Year: 2020

Cyber deception is one of the key approaches used to mislead attackers by hiding or providing inaccurate system information. There are two main factors limiting the real-world application of existing cyber deception approaches. The first limitation is that the number of systems in a network is assumed to be fixed. However, in the real world, the number of systems may be dynamically changed. The second limitation is that attackers' strategies are simplified in the literature. However, in the real world, attackers may be more powerful than theory suggests. To overcome these two limitations, we propose a novel differentially private game theoretic approach to cyber deception. In this proposed approach, a defender adopts differential privacy mechanisms to strategically change the number of systems and obfuscate the configurations of systems, while an attacker adopts a Bayesian inference approach to infer the real configurations of systems. By using the differential privacy technique, the proposed approach can 1) reduce the impacts on network security resulting from changes in the number of systems and 2) resist attacks regardless of attackers' reasoning power. The experimental results demonstrate the effectiveness of the proposed approach.
FLCD: A Flexible Low Complexity Design of Coded Distributed Computing
Venue: arXiv cs.IT 2020
Year: 2020

We propose a flexible low complexity design (FLCD) of coded distributed computing (CDC) with empirical evaluation on Amazon Elastic Compute Cloud (Amazon EC2). CDC can expedite MapReduce like computation by trading increased map computations to reduce communication load and shuffle time. A main novelty of FLCD is to utilize the design freedom in defining map and reduce functions to develop asymptotic homogeneous systems to support varying intermediate values (IV) sizes under a general MapReduce framework. Compared to existing designs with constant IV sizes, FLCD offers greater flexibility in adapting to network parameters and significantly reduces the implementation complexity by requiring fewer input files and shuffle groups. The FLCD scheme is the first proposed low-complexity CDC design that can operate on a network with an arbitrary number of nodes and computation load. We perform empirical evaluations of the FLCD by executing the TeraSort algorithm on an Amazon EC2 cluster. This is the first time that theoretical predictions of the CDC shuffle time are validated by empirical evaluations. The evaluations demonstrate a 2.0 to 4.24x speedup compared to conventional uncoded MapReduce, a 12% to 52% reduction in total time, and a wider range of operating network parameters compared to existing CDC schemes.