OpenRaiser/Intern-Atlas huggingface dataset:
Locally Differentially Private Sparse Vector Aggregation
Venue: arXiv cs.CR 2022
Year: 2022

Vector mean estimation is a central primitive in federated analytics. In vector mean estimation, each user $i \in [n]$ holds a real-valued vector $v_i\in [-1, 1]^d$, and a server wants to estimate the mean of all $n$ vectors. Not only so, we would like to protect each individual user's privacy. In this paper, we consider the $k$-sparse version of the vector mean estimation problem, that is, suppose that each user's vector has at most $k$ non-zero coordinates in its $d$-dimensional vector, and moreover, $k \ll d$. In practice, since the universe size $d$ can be very large (e.g., the space of all possible URLs), we would like the per-user communication to be succinct, i.e., independent of or (poly-)logarithmic in the universe size. In this paper, we are the first to show matching upper- and lower-bounds for the $k$-sparse vector mean estimation problem under local differential privacy. Specifically, we construct new mechanisms that achieve asymptotically optimal error as well as succinct communication, either under user-level-LDP or event-level-LDP. We implement our algorithms and evaluate them on synthetic as well as real-world datasets. Our experiments show that we can often achieve one or two orders of magnitude reduction in error in comparison with prior works under typical choices of parameters, while incurring insignificant communication cost.
Structural Health Monitoring of a Foot Bridge in Virtual Reality Environment
Venue: arXiv cs.HC 2022
Year: 2022

Ageing civil infrastructure systems require imminent attention before any failure mechanism becomes critical. Structural Health Monitoring (SHM) is employed to track inputs and/or responses of structural systems for decision support. Inspections and structural health monitoring require field visits, and subsequently expert assessment of critical elements at site, which may be both time-consuming and costly. Also, fieldwork including visits and inspections may pose danger, require personal protective equipment and structure closures during the fieldwork. To address some of these issues, a Virtual Reality (VR) collaborative application is developed to bring the structure and SHM data from the field to the office such that many experts from different places can simultaneously virtually visit the bridge structure for final assessment. In this work, we present an SHM system in a VR environment that includes the technical and visual information necessary for the engineers to make decisions for a footbridge on the campus of the University of Central Florida. In this VR application, for the visualization stage, UAV (Unmanned Air Vehicle) photogrammetry and LiDAR (Light Detection and Ranging) methods are used to capture the bridge. For the technical assessment stage, Finite Element Analysis (FEA) and Operational Modal Analysis (OMA) from vibration data as part of SHM are analyzed. To better visualize the dynamic response of the structure, the operational behaviour from the FEA is reflected on the LiDAR point cloud model for immersive. The multi-user feature allowing teams to collaborate simultaneously is essential for decision-making activities. In conclusion, the proposed VR environment offers the potential to provide beneficial features with further automated and real-time improvements along with the SHM and FEA models.
How do influential and non-influential papers spread online?
Venue: arXiv cs.DL 2022
Year: 2022

Social media has become an important channel for publicizing academic research. Employing a dataset of about 10 million tweets of 584,264 scientific papers from 2012 to 2018, this study investigates the differential diffusion of influential and non-influential papers (divided by Average journal impact factor percentile). We find that non-influential papers shows a diffusion trend with multiple rounds, sparse, short-duration and small-scale bursts. In contrast, the bursts of influential journals are characterized by a small number of persistent, dense and large-scale bursts. Influential papers are generally disseminated to many loosely connected communities, while non-influential papers are diffused to several densely connected communities.
Membership Inference Attacks From First Principles
Venue: arXiv cs.CR 2022
Year: 2022

A membership inference attack allows an adversary to query a trained machine learning model to predict whether or not a particular example was contained in the model's training dataset. These attacks are currently evaluated using average-case "accuracy" metrics that fail to characterize whether the attack can confidently identify any members of the training set. We argue that attacks should instead be evaluated by computing their true-positive rate at low (e.g., <0.1%) false-positive rates, and find most prior attacks perform poorly when evaluated in this way. To address this we develop a Likelihood Ratio Attack (LiRA) that carefully combines multiple ideas from the literature. Our attack is 10x more powerful at low false-positive rates, and also strictly dominates prior attacks on existing metrics.
E$^2$(GO)MOTION: Motion Augmented Event Stream for Egocentric Action Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Event cameras are novel bio-inspired sensors, which asynchronously capture pixel-level intensity changes in the form of "events". Due to their sensing mechanism, event cameras have little to no motion blur, a very high temporal resolution and require significantly less power and memory than traditional frame-based cameras. These characteristics make them a perfect fit to several real-world applications such as egocentric action recognition on wearable devices, where fast camera motion and limited power challenge traditional vision sensors. However, the ever-growing field of event-based vision has, to date, overlooked the potential of event cameras in such applications. In this paper, we show that event data is a very valuable modality for egocentric action recognition. To do so, we introduce N-EPIC-Kitchens, the first event-based camera extension of the large-scale EPIC-Kitchens dataset. In this context, we propose two strategies: (i) directly processing event-camera data with traditional video-processing architectures (E$^2$(GO)) and (ii) using event-data to distill optical flow information (E$^2$(GO)MO). On our proposed benchmark, we show that event data provides a comparable performance to RGB and optical flow, yet without any additional flow computation at deploy time, and an improved performance of up to 4% with respect to RGB only information.
Some Basic Techniques allowing Petri Net Synthesis: Complexity and Algorithmic Issues
Venue: arXiv cs.FL 2022
Year: 2022

In Petri net synthesis we ask whether a given transition system $A$ can be implemented by a Petri net $N$. Depending on the level of accuracy, there are three ways how $N$ can implement $A$: an embedding, the least accurate implementation, preserves only the diversity of states of $A$; a language simulation already preserves exactly the language of $A$; a realization, the most accurate implementation, realizes the behavior of $A$ exactly. However, whatever the sought implementation, a corresponding net does not always exist. In this case, it was suggested to modify the input behavior -- of course as little as possible. Since transition systems consist of states, events and edges, these components appear as a natural choice for modifications. In this paper we show that the task of converting an unimplementable transition system into an implementable one by removing as few states or events or edges as possible is NP-complete -- regardless of what type of implementation we are aiming for; we also show that the corresponding parameterized problems are $W[2]$-hard, where the number of removed components is considered as the parameter; finally, we show there is no $c$-approximation algorithm (with a polynomial running time) for neither of these problems, for every constant $c\geq 1$.
Tighter Bounds for Reconstruction from $ε$-samples
Venue: arXiv cs.CG 2022
Year: 2022

We show that reconstructing a curve in $\mathbb{R}^d$ for $d\geq 2$ from a $0.66$-sample is always possible using an algorithm similar to the classical NN-Crust algorithm. Previously, this was only known to be possible for $0.47$-samples in $\mathbb{R}^2$ and $\frac{1}{3}$-samples in $\mathbb{R}^d$ for $d\geq 3$. In addition, we show that there is not always a unique way to reconstruct a curve from a $0.72$-sample; this was previously only known for $1$-samples. We also extend this non-uniqueness result to hypersurfaces in all higher dimensions.
Hybrid Self-Attention NEAT: A novel evolutionary approach to improve the NEAT algorithm
Venue: arXiv cs.NE 2022
Year: 2022

This article presents a "Hybrid Self-Attention NEAT" method to improve the original NeuroEvolution of Augmenting Topologies (NEAT) algorithm in high-dimensional inputs. Although the NEAT algorithm has shown a significant result in different challenging tasks, as input representations are high dimensional, it cannot create a well-tuned network. Our study addresses this limitation by using self-attention as an indirect encoding method to select the most important parts of the input. In addition, we improve its overall performance with the help of a hybrid method to evolve the final network weights. The main conclusion is that Hybrid Self- Attention NEAT can eliminate the restriction of the original NEAT. The results indicate that in comparison with evolutionary algorithms, our model can get comparable scores in Atari games with raw pixels input with a much lower number of parameters.
Symmetry Perception by Deep Networks: Inadequacy of Feed-Forward Architectures and Improvements with Recurrent Connections
Venue: arXiv cs.CV 2022
Year: 2022

Symmetry is omnipresent in nature and perceived by the visual system of many species, as it facilitates detecting ecologically important classes of objects in our environment. Symmetry perception requires abstraction of long-range spatial dependencies between image regions, and its underlying neural mechanisms remain elusive. In this paper, we evaluate Deep Neural Network (DNN) architectures on the task of learning symmetry perception from examples. We demonstrate that feed-forward DNNs that excel at modelling human performance on object recognition tasks, are unable to acquire a general notion of symmetry. This is the case even when the DNNs are architected to capture long-range spatial dependencies, such as through `dilated' convolutions and the recently introduced `transformers' design. By contrast, we find that recurrent architectures are capable of learning to perceive symmetry by decomposing the long-range spatial dependencies into a sequence of local operations, that are reusable for novel images. These results suggest that recurrent connections likely play an important role in symmetry perception in artificial systems, and possibly, biological ones too.
On the Ergodic Mutual Information of Keyhole MIMO Channels With Finite-Alphabet Inputs
Venue: arXiv cs.IT 2022
Year: 2022

This letter studies the ergodic mutual information (EMI) of keyhole multiple-input multiple-output channels having finite-alphabet input signals. The EMI is first investigated for single-stream transmission considering both cases with and without the channel state information at the transmitter. Then, the derived results are extended to the scenario of multi-stream transmission. Asymptotic analyses are performed in the regime of high signal-to-noise ratio (SNR). The high-SNR EMI is shown to converge to a constant with its rate of convergence determined by the diversity order. On this basis, the influence of the keyhole effect on the EMI is discussed. The analytical results are validated by numerical simulations.
Gaussian Process Constraint Learning for Scalable Chance-Constrained Motion Planning from Demonstrations
Venue: arXiv cs.RO 2022
Year: 2022

We propose a method for learning constraints represented as Gaussian processes (GPs) from locally-optimal demonstrations. Our approach uses the Karush-Kuhn-Tucker (KKT) optimality conditions to determine where on the demonstrations the constraint is tight, and a scaling of the constraint gradient at those states. We then train a GP representation of the constraint which is consistent with and which generalizes this information. We further show that the GP uncertainty can be used within a kinodynamic RRT to plan probabilistically-safe trajectories, and that we can exploit the GP structure within the planner to exactly achieve a specified safety probability. We demonstrate our method can learn complex, nonlinear constraints demonstrated on a 5D nonholonomic car, a 12D quadrotor, and a 3-link planar arm, all while requiring minimal prior information on the constraint. Our results suggest the learned GP constraint is accurate, outperforming previous constraint learning methods that require more a priori knowledge.
Deep Visual Constraints: Neural Implicit Models for Manipulation Planning from Visual Input
Venue: arXiv cs.RO 2022
Year: 2022

Manipulation planning is the problem of finding a sequence of robot configurations that involves interactions with objects in the scene, e.g., grasping and placing an object, or more general tool-use. To achieve such interactions, traditional approaches require hand-engineering of object representations and interaction constraints, which easily becomes tedious when complex objects/interactions are considered. Inspired by recent advances in 3D modeling, e.g. NeRF, we propose a method to represent objects as continuous functions upon which constraint features are defined and jointly trained. In particular, the proposed pixel-aligned representation is directly inferred from images with known camera geometry and naturally acts as a perception component in the whole manipulation pipeline, thereby enabling long-horizon planning only from visual input. Project page: https://sites.google.com/view/deep-visual-constraints
Intelligent Transportation Systems Using External Infrastructure: A Literature Survey
Venue: arXiv cs.RO 2022
Year: 2022

The main problems in transportation are accidents, increasingly slow traffic flow, and pollution. An intelligent transportation system (ITS) using external infrastructure can overcome these problems. For this reason, the number of such systems is increasing dramatically, and therefore requires an adequate overview. To the best of our knowledge, no current systematic review of existing ITS solutions exists. To fill this knowledge gap, our paper provides an overview of existing ITS that use external infrastructure worldwide. Accordingly, this paper addresses current questions and challenges. For this purpose, we performed a literature review of documents that describe existing ITS solutions from 2009 until today. We categorized the results according to technology levels and analyzed its hardware system setup and value-added contributions. In doing so, we made the ITS solutions comparable and highlighted past development alongside current trends. We analyzed more than 357 papers, including 52 test bed projects. In summary, current ITSs can deliver accurate information about individuals in traffic situations in real-time. However, further research into ITS should focus on more reliable perception of the traffic using modern sensors, plug-and-play mechanisms, and secure real-time distribution of the digital twins in a decentralized manner. By addressing these topics, the development of intelligent transportation systems will be able to take a step towards its comprehensive roll-out.
Self-attention Does Not Need $O(n^2)$ Memory
Venue: arXiv cs.LG 2022
Year: 2022

We present a very simple algorithm for attention that requires $O(1)$ memory with respect to sequence length and an extension to self-attention that requires $O(\log n)$ memory. This is in contrast with the frequently stated belief that self-attention requires $O(n^2)$ memory. While the time complexity is still $O(n^2)$, device memory rather than compute capability is often the limiting factor on modern accelerators. Thus, reducing the memory requirements of attention allows processing of longer sequences than might otherwise be feasible. We provide a practical implementation for accelerators that requires $O(\sqrt{n})$ memory, is numerically stable, and is within a few percent of the runtime of the standard implementation of attention. We also demonstrate how to differentiate the function while remaining memory-efficient. For sequence length 16384, the memory overhead of self-attention is reduced by 59X for inference and by 32X for differentiation.
Sample and Threshold Differential Privacy: Histograms and applications
Venue: arXiv cs.CR 2022
Year: 2022

Federated analytics seeks to compute accurate statistics from data distributed across users' devices while providing a suitable privacy guarantee and being practically feasible to implement and scale. In this paper, we show how a strong $(ε, δ)$-Differential Privacy (DP) guarantee can be achieved for the fundamental problem of histogram generation in a federated setting, via a highly practical sampling-based procedure that does not add noise to disclosed data. Given the ubiquity of sampling in practice, we thus obtain a DP guarantee almost for free, avoid over-estimating histogram counts, and allow easy reasoning about how privacy guarantees may obscure minorities and outliers. Using such histograms, related problems such as heavy hitters and quantiles can be answered with provable error and privacy guarantees. Experimental results show that our sample-and-threshold approach is accurate and scalable.
OstrichRL: A Musculoskeletal Ostrich Simulation to Study Bio-mechanical Locomotion
Venue: arXiv cs.RO 2022
Year: 2022

Muscle-actuated control is a research topic that spans multiple domains, including biomechanics, neuroscience, reinforcement learning, robotics, and graphics. This type of control is particularly challenging as bodies are often overactuated and dynamics are delayed and non-linear. It is however a very well tested and tuned actuation mechanism that has undergone millions of years of evolution with interesting properties exploiting passive forces and efficient energy storage of muscle-tendon units. To facilitate research on muscle-actuated simulation, we release a 3D musculoskeletal simulation of an ostrich based on the MuJoCo physics engine. The ostrich is one of the fastest bipeds on earth and therefore makes an excellent model for studying muscle-actuated bipedal locomotion. The model is based on CT scans and dissections used to collect actual muscle data, such as insertion sites, lengths, and pennation angles. Along with this model, we also provide a set of reinforcement learning tasks, including reference motion tracking, running, and neck control, used to infer muscle actuation patterns. The reference motion data is based on motion capture clips of various behaviors that we preprocessed and adapted to our model. This paper describes how the model was built and iteratively improved using the tasks. We also evaluate the accuracy of the muscle actuation patterns by comparing them to experimentally collected electromyographic data from locomoting birds. The results demonstrate the need for rich reward signals or regularization techniques to constrain muscle excitations and produce realistic movements. Overall, we believe that this work can provide a useful bridge between fields of research interested in muscle actuation.
Measuring Complexity of Learning Schemes Using Hessian-Schatten Total Variation
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we introduce the Hessian-Schatten total variation (HTV) -- a novel seminorm that quantifies the total "rugosity" of multivariate functions. Our motivation for defining HTV is to assess the complexity of supervised-learning schemes. We start by specifying the adequate matrix-valued Banach spaces that are equipped with suitable classes of mixed norms. We then show that the HTV is invariant to rotations, scalings, and translations. Additionally, its minimum value is achieved for linear mappings, which supports the common intuition that linear regression is the least complex learning model. Next, we present closed-form expressions of the HTV for two general classes of functions. The first one is the class of Sobolev functions with a certain degree of regularity, for which we show that the HTV coincides with the Hessian-Schatten seminorm that is sometimes used as a regularizer for image reconstruction. The second one is the class of continuous and piecewise-linear (CPWL) functions. In this case, we show that the HTV reflects the total change in slopes between linear regions that have a common facet. Hence, it can be viewed as a convex relaxation (l1-type) of the number of linear regions (l0-type) of CPWL mappings. Finally, we illustrate the use of our proposed seminorm.
On sketching approximations for symmetric Boolean CSPs
Venue: arXiv cs.DS 2022
Year: 2022

A Boolean maximum constraint satisfaction problem, Max-CSP($f$), is specified by a predicate $f:\{-1,1\}^k\to\{0,1\}$. An $n$-variable instance of Max-CSP($f$) consists of a list of constraints, each of which applies $f$ to $k$ distinct literals drawn from the $n$ variables. For $k=2$, Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios characterizing the $\sqrt n$-space streaming approximability of every predicate. For $k \geq 3$, Chou, Golovnev, Sudan, and Velusamy [CGSV21, arXiv:2102.12351] proved a general dichotomy theorem for $\sqrt n$-space sketching algorithms: For every $f$, there exists $α(f)\in (0,1]$ such that for every $ε>0$, Max-CSP($f$) is $(α(f)-ε)$-approximable by an $O(\log n)$-space linear sketching algorithm, but $(α(f)+ε)$-approximation sketching algorithms require $Ω(\sqrt{n})$ space. In this work, we give closed-form expressions for the sketching approximation ratios of multiple families of symmetric Boolean functions. Letting $α'_k = 2^{-(k-1)} (1-k^{-2})^{(k-1)/2}$, we show that for odd $k \geq 3$, $α(k$AND$) = α'_k$, and for even $k \geq 2$, $α(k$AND$) = 2α'_{k+1}$. We also resolve the ratio for the "at-least-$(k-1)$-$1$'s" function for all even $k$; the "exactly-$\frac{k+1}2$-$1$'s" function for odd $k \in \{3,\ldots,51\}$; and fifteen other functions. We stress here that for general $f$, according to [CGSV21], closed-form expressions for $α(f)$ need not have existed a priori. Separately, for all threshold functions, we give optimal "bias-based" approximation algorithms generalizing [CGV20] while simplifying [CGSV21]. Finally, we investigate the $\sqrt n$-space streaming lower bounds in [CGSV21], and show that they are incomplete for $3$AND.
Anomaly Crossing: New Horizons for Video Anomaly Detection as Cross-domain Few-shot Learning
Venue: arXiv cs.CV 2022
Year: 2022

Video anomaly detection aims to identify abnormal events that occurred in videos. Since anomalous events are relatively rare, it is not feasible to collect a balanced dataset and train a binary classifier to solve the task. Thus, most previous approaches learn only from normal videos using unsupervised or semi-supervised methods. Obviously, they are limited in capturing and utilizing discriminative abnormal characteristics, which leads to compromised anomaly detection performance. In this paper, to address this issue, we propose a new learning paradigm by making full use of both normal and abnormal videos for video anomaly detection. In particular, we formulate a new learning task: cross-domain few-shot anomaly detection, which can transfer knowledge learned from numerous videos in the source domain to help solve few-shot abnormality detection in the target domain. Concretely, we leverage self-supervised training on the target normal videos to reduce the domain gap and devise a meta context perception module to explore the video context of the event in the few-shot setting. Our experiments show that our method significantly outperforms baseline methods on DoTA and UCF-Crime datasets, and the new task contributes to a more practical training paradigm for anomaly detection.