OpenRaiser/Intern-Atlas huggingface dataset:
Mining Root Cause Knowledge from Cloud Service Incident Investigations for AIOps
Venue: arXiv cs.IR 2022
Year: 2022

Root Cause Analysis (RCA) of any service-disrupting incident is one of the most critical as well as complex tasks in IT processes, especially for cloud industry leaders like Salesforce. Typically RCA investigation leverages data-sources like application error logs or service call traces. However a rich goldmine of root cause information is also hidden in the natural language documentation of the past incidents investigations by domain experts. This is generally termed as Problem Review Board (PRB) Data which constitute a core component of IT Incident Management. However, owing to the raw unstructured nature of PRBs, such root cause knowledge is not directly reusable by manual or automated pipelines for RCA of new incidents. This motivates us to leverage this widely-available data-source to build an Incident Causation Analysis (ICA) engine, using SoTA neural NLP techniques to extract targeted information and construct a structured Causal Knowledge Graph from PRB documents. ICA forms the backbone of a simple-yet-effective Retrieval based RCA for new incidents, through an Information Retrieval system to search and rank past incidents and detect likely root causes from them, given the incident symptom. In this work, we present ICA and the downstream Incident Search and Retrieval based RCA pipeline, built at Salesforce, over 2K documented cloud service incident investigations collected over a few years. We also establish the effectiveness of ICA and the downstream tasks through various quantitative benchmarks, qualitative analysis as well as domain expert's validation and real incident case studies after deployment.
Cryptography Is Not Enough: Relay Attacks on Authenticated GNSS Signals
Venue: arXiv cs.CR 2022
Year: 2022

Civilian-GNSS is vulnerable to signal spoofing attacks, and countermeasures based on cryptographic authentication are being proposed to protect against these attacks. Both Galileo and GPS are currently testing broadcast authentication techniques based on the delayed key disclosure to validate the integrity of navigation messages. These authentication mechanisms have proven secure against record now and replay later attacks, as navigation messages become invalid after keys are released. This work analyzes the security guarantees of cryptographically protected GNSS signals and shows the possibility of spoofing a receiver to an arbitrary location without breaking any cryptographic operation. In contrast to prior work, we demonstrate the ability of an attacker to receive signals close to the victim receiver and generate spoofing signals for a different target location without modifying the navigation message contents. Our strategy exploits the essential common reception and transmission time method used to estimate pseudorange in GNSS receivers, thereby rendering any cryptographic authentication useless. We evaluate our attack on a commercial receiver (ublox M9N) and a software-defined GNSS receiver (GNSS-SDR) using a combination of open-source tools, commercial GNSS signal generators, and software-defined radio hardware platforms. Our results show that it is possible to spoof a victim receiver to locations around 4000 km away from the true location without requiring any high-speed communication networks or modifying the message contents. Through this work, we further highlight the fundamental limitations in securing a broadcast signaling-based localization system even if all communications are cryptographically protected.
Low Complexity Suboptimal ML Detection for OFDM-IM Systems
Venue: arXiv cs.IT 2022
Year: 2022

Orthogonal frequency division multiplexing with index modulation (OFDM-IM) is a novel multicarrier scheme, which uses the k out of n subcarriers as active subcarriers to transmit data. For detecting the subcarrier activation pattern (SAP) at the receiver, maximum likelihood (ML) detection cannot be used because of its high computational complexity. Instead, the detector selecting the most likely active k subcarriers is used, which is called a k largest values (klv) detector. However, this method degrades the detection performance especially if the ratio of illegal SAPs to SAPs is high. In this letter, the suboptimal ML detector is proposed, which is a slight modification of the klv detector. However, the proposed detector has a similar detection performance compared to the ML detection, which is suitable for flexible implementation of OFDM-IM systems.
Parameterized safety verification of round-based shared-memory systems
Venue: arXiv cs.FL 2022
Year: 2022

We consider the parameterized verification problem for distributed algorithms where the goal is to develop techniques to prove the correctness of a given algorithm regardless of the number of participating processes. Motivated by an asynchronous binary consensus algorithm [J. Aspnes, Fast deterministic consensus in a noisy environment. Journal of Algorithms, 2002], we consider round-based distributed algorithms communicating with shared memory. A particular challenge in these systems is that 1) the number of processes is unbounded, and, more importantly, 2) there is a fresh set of registers at each round. A~verification algorithm thus needs to manage both sources of infinity. In this setting, we prove that the safety verification problem, which consists in deciding whether all possible executions avoid a given error state, is PSPACE-complete. For~negative instances of the safety verification problem, we~also provide exponential lower and upper bounds on the minimal number of processes needed for an error execution and on the minimal round on which the error state can be covered.
HyperNCA: Growing Developmental Networks with Neural Cellular Automata
Venue: arXiv cs.NE 2022
Year: 2022

In contrast to deep reinforcement learning agents, biological neural networks are grown through a self-organized developmental process. Here we propose a new hypernetwork approach to grow artificial neural networks based on neural cellular automata (NCA). Inspired by self-organising systems and information-theoretic approaches to developmental biology, we show that our HyperNCA method can grow neural networks capable of solving common reinforcement learning tasks. Finally, we explore how the same approach can be used to build developmental metamorphosis networks capable of transforming their weights to solve variations of the initial RL task.
A Structural Investigation of the Approximability of Polynomial-Time Problems
Venue: arXiv cs.DS 2022
Year: 2022

We initiate the systematic study of a recently introduced polynomial-time analogue of MaxSNP, which includes a large number of well-studied problems (including Nearest and Furthest Neighbor in the Hamming metric, Maximum Inner Product, optimization variants of $k$-XOR and Maximum $k$-Cover). Specifically, MaxSP$_k$ denotes the class of $O(m^k)$-time problems of the form $\max_{x_1,\dots, x_k} \#\{y:ϕ(x_1,\dots,x_k,y)\}$ where $ϕ$ is a quantifier-free first-order property and $m$ denotes the size of the relational structure. Assuming central hypotheses about clique detection in hypergraphs and MAX3SAT, we show that for any MaxSP$_k$ problem definable by a quantifier-free $m$-edge graph formula $ϕ$, the best possible approximation guarantee in faster-than-exhaustive-search time $O(m^{k-δ})$ falls into one of four categories: * optimizable to exactness in time $O(m^{k-δ})$, * an (inefficient) approximation scheme, i.e., a $(1+ε)$-approximation in time $O(m^{k-f(ε)})$, * a (fixed) constant-factor approximation in time $O(m^{k-δ})$, or * an $m^ε$-approximation in time $O(m^{k-f(ε)})$. We obtain an almost complete characterization of these regimes, for MaxSP$_k$ as well as for an analogously defined minimization class MinSP$_k$. As our main technical contribution, we rule out approximation schemes for a large class of problems admitting constant-factor approximations, under the Sparse MAX3SAT hypothesis posed by (Alman, Vassilevska Williams'20). As general trends for the problems we consider, we find: (1) Exact optimizability has a simple algebraic characterization, (2) only few maximization problems do not admit a constant-factor approximation; these do not even have a subpolynomial-factor approximation, and (3) constant-factor approximation of minimization problems is equivalent to deciding whether the optimum is equal to 0.
Sub-4.7 Scaling Exponent of Polar Codes
Venue: arXiv cs.IT 2022
Year: 2022

Polar code visibly approaches channel capacity in practice and is thereby a constituent code of the 5G standard. Compared to low-density parity-check code, however, the performance of short-length polar code has rooms for improvement that could hinder its adoption by a wider class of applications. As part of the program that addresses the performance issue at short length, it is crucial to understand how fast binary memoryless symmetric channels polarize. A number, called scaling exponent, was defined to measure the speed of polarization and several estimates of the scaling exponent were given in literature. As of 2022, the tightest overestimate is 4.714 made by Mondelli, Hassani, and Urbanke in 2015. We lower the overestimate to 4.63.
Using Collocated Vision and Tactile Sensors for Visual Servoing and Localization
Venue: arXiv cs.RO 2022
Year: 2022

Coordinating proximity and tactile imaging by collocating cameras with tactile sensors can 1) provide useful information before contact such as object pose estimates and visually servo a robot to a target with reduced occlusion and higher resolution compared to head-mounted or external depth cameras, 2) simplify the contact point and pose estimation problems and help tactile sensing avoid erroneous matches when a surface does not have significant texture or has repetitive texture with many possible matches, and 3) use tactile imaging to further refine contact point and object pose estimation. We demonstrate our results with objects that have more surface texture than most objects in standard manipulation datasets. We learn that optic flow needs to be integrated over a substantial amount of camera travel to be useful in predicting movement direction. Most importantly, we also learn that state of the art vision algorithms do not do a good job localizing tactile images on object models, unless a reasonable prior can be provided from collocated cameras.
The Causal News Corpus: Annotating Causal Relations in Event Sentences from News
Venue: arXiv cs.CL 2022
Year: 2022

Despite the importance of understanding causality, corpora addressing causal relations are limited. There is a discrepancy between existing annotation guidelines of event causality and conventional causality corpora that focus more on linguistics. Many guidelines restrict themselves to include only explicit relations or clause-based arguments. Therefore, we propose an annotation schema for event causality that addresses these concerns. We annotated 3,559 event sentences from protest event news with labels on whether it contains causal relations or not. Our corpus is known as the Causal News Corpus (CNC). A neural network built upon a state-of-the-art pre-trained language model performed well with 81.20% F1 score on test set, and 83.46% in 5-folds cross-validation. CNC is transferable across two external corpora: CausalTimeBank (CTB) and Penn Discourse Treebank (PDTB). Leveraging each of these external datasets for training, we achieved up to approximately 64% F1 on the CNC test set without additional fine-tuning. CNC also served as an effective training and pre-training dataset for the two external corpora. Lastly, we demonstrate the difficulty of our task to the layman in a crowd-sourced annotation exercise. Our annotated corpus is publicly available, providing a valuable resource for causal text mining researchers.
Masked Image Modeling Advances 3D Medical Image Analysis
Venue: arXiv cs.CV 2022
Year: 2022

Recently, masked image modeling (MIM) has gained considerable attention due to its capacity to learn from vast amounts of unlabeled data and has been demonstrated to be effective on a wide variety of vision tasks involving natural images. Meanwhile, the potential of self-supervised learning in modeling 3D medical images is anticipated to be immense due to the high quantities of unlabeled images, and the expense and difficulty of quality labels. However, MIM's applicability to medical images remains uncertain. In this paper, we demonstrate that masked image modeling approaches can also advance 3D medical images analysis in addition to natural images. We study how masked image modeling strategies leverage performance from the viewpoints of 3D medical image segmentation as a representative downstream task: i) when compared to naive contrastive learning, masked image modeling approaches accelerate the convergence of supervised training even faster (1.40$\times$) and ultimately produce a higher dice score; ii) predicting raw voxel values with a high masking ratio and a relatively smaller patch size is non-trivial self-supervised pretext-task for medical images modeling; iii) a lightweight decoder or projection head design for reconstruction is powerful for masked image modeling on 3D medical images which speeds up training and reduce cost; iv) finally, we also investigate the effectiveness of MIM methods under different practical scenarios where different image resolutions and labeled data ratios are applied.
Enable Deep Learning on Mobile Devices: Methods, Systems, and Applications
Venue: arXiv cs.LG 2022
Year: 2022

Deep neural networks (DNNs) have achieved unprecedented success in the field of artificial intelligence (AI), including computer vision, natural language processing and speech recognition. However, their superior performance comes at the considerable cost of computational complexity, which greatly hinders their applications in many resource-constrained devices, such as mobile phones and Internet of Things (IoT) devices. Therefore, methods and techniques that are able to lift the efficiency bottleneck while preserving the high accuracy of DNNs are in great demand in order to enable numerous edge AI applications. This paper provides an overview of efficient deep learning methods, systems and applications. We start from introducing popular model compression methods, including pruning, factorization, quantization as well as compact model design. To reduce the large design cost of these manual solutions, we discuss the AutoML framework for each of them, such as neural architecture search (NAS) and automated pruning and quantization. We then cover efficient on-device training to enable user customization based on the local data on mobile devices. Apart from general acceleration techniques, we also showcase several task-specific accelerations for point cloud, video and natural language processing by exploiting their spatial sparsity and temporal/token redundancy. Finally, to support all these algorithmic advancements, we introduce the efficient deep learning system design from both software and hardware perspectives.
PVNAS: 3D Neural Architecture Search with Point-Voxel Convolution
Venue: arXiv cs.CV 2022
Year: 2022

3D neural networks are widely used in real-world applications (e.g., AR/VR headsets, self-driving cars). They are required to be fast and accurate; however, limited hardware resources on edge devices make these requirements rather challenging. Previous work processes 3D data using either voxel-based or point-based neural networks, but both types of 3D models are not hardware-efficient due to the large memory footprint and random memory access. In this paper, we study 3D deep learning from the efficiency perspective. We first systematically analyze the bottlenecks of previous 3D methods. We then combine the best from point-based and voxel-based models together and propose a novel hardware-efficient 3D primitive, Point-Voxel Convolution (PVConv). We further enhance this primitive with the sparse convolution to make it more effective in processing large (outdoor) scenes. Based on our designed 3D primitive, we introduce 3D Neural Architecture Search (3D-NAS) to explore the best 3D network architecture given a resource constraint. We evaluate our proposed method on six representative benchmark datasets, achieving state-of-the-art performance with 1.8-23.7x measured speedup. Furthermore, our method has been deployed to the autonomous racing vehicle of MIT Driverless, achieving larger detection range, higher accuracy and lower latency.
Reachability in Bidirected Pushdown VASS
Venue: arXiv cs.FL 2022
Year: 2022

A pushdown vector addition system with states (PVASS) extends the model of vector addition systems with a pushdown store. A PVASS is said to be \emph{bidirected} if every transition (pushing/popping a symbol or modifying a counter) has an accompanying opposite transition that reverses the effect. Bidirectedness arises naturally in many models; it can also be seen as a overapproximation of reachability. We show that the reachability problem for \emph{bidirected} PVASS is decidable in Ackermann time and primitive recursive for any fixed dimension. For the special case of one-dimensional bidirected PVASS, we show reachability is in $\mathsf{PSPACE}$, and in fact in polynomial time if the stack is polynomially bounded. Our results are in contrast to the \emph{directed} setting, where decidability of reachability is a long-standing open problem already for one dimensional PVASS, and there is a $\mathsf{PSPACE}$-lower bound already for one-dimensional PVASS with bounded stack. The reachability relation in the bidirected (stateless) case is a congruence over $\mathbb{N}^d$. Our upper bounds exploit saturation techniques over congruences. In particular, we show novel elementary-time constructions of semilinear representations of congruences generated by finitely many vector pairs. In the case of one-dimensional PVASS, we employ a saturation procedure over bounded-size counters. We complement our upper bound with a $\mathsf{TOWER}$-hardness result for arbitrary dimension and $k$-$\mathsf{EXPSPACE}$ hardness in dimension $2k+6$ using a technique by Lazić and Totzke to implement iterative exponentiations.
Semi-Parametric Neural Image Synthesis
Venue: arXiv cs.CV 2022
Year: 2022

Novel architectures have recently improved generative image synthesis leading to excellent visual quality in various tasks. Much of this success is due to the scalability of these architectures and hence caused by a dramatic increase in model complexity and in the computational resources invested in training these models. Our work questions the underlying paradigm of compressing large training data into ever growing parametric representations. We rather present an orthogonal, semi-parametric approach. We complement comparably small diffusion or autoregressive models with a separate image database and a retrieval strategy. During training we retrieve a set of nearest neighbors from this external database for each training instance and condition the generative model on these informative samples. While the retrieval approach is providing the (local) content, the model is focusing on learning the composition of scenes based on this content. As demonstrated by our experiments, simply swapping the database for one with different contents transfers a trained model post-hoc to a novel domain. The evaluation shows competitive performance on tasks which the generative model has not been trained on, such as class-conditional synthesis, zero-shot stylization or text-to-image synthesis without requiring paired text-image data. With negligible memory and computational overhead for the external database and retrieval we can significantly reduce the parameter count of the generative model and still outperform the state-of-the-art.
A Mask-Based Adversarial Defense Scheme
Venue: arXiv cs.LG 2022
Year: 2022

Adversarial attacks hamper the functionality and accuracy of Deep Neural Networks (DNNs) by meddling with subtle perturbations to their inputs.In this work, we propose a new Mask-based Adversarial Defense scheme (MAD) for DNNs to mitigate the negative effect from adversarial attacks. To be precise, our method promotes the robustness of a DNN by randomly masking a portion of potential adversarial images, and as a result, the %classification result output of the DNN becomes more tolerant to minor input perturbations. Compared with existing adversarial defense techniques, our method does not need any additional denoising structure, nor any change to a DNN's design. We have tested this approach on a collection of DNN models for a variety of data sets, and the experimental results confirm that the proposed method can effectively improve the defense abilities of the DNNs against all of the tested adversarial attack methods. In certain scenarios, the DNN models trained with MAD have improved classification accuracy by as much as 20% to 90% compared to the original models that are given adversarial inputs.
Automating Neural Architecture Design without Search
Venue: arXiv cs.LG 2022
Year: 2022

Neural structure search (NAS), as the mainstream approach to automate deep neural architecture design, has achieved much success in recent years. However, the performance estimation component adhering to NAS is often prohibitively costly, which leads to the enormous computational demand. Though a large number of efforts have been dedicated to alleviating this pain point, no consensus has been made yet on which is optimal. In this paper, we study the automated architecture design from a new perspective that eliminates the need to sequentially evaluate each neural architecture generated during algorithm execution. Specifically, the proposed approach is built by learning the knowledge of high-level experts in designing state-of-the-art architectures, and then the new architecture is directly generated upon the knowledge learned. We implemented the proposed approach by using a graph neural network for link prediction and acquired the knowledge from NAS-Bench-101. Compared to existing peer competitors, we found a competitive network with minimal cost. In addition, we also utilized the learned knowledge from NAS-Bench-101 to automate architecture design in the DARTS search space, and achieved 97.82% accuracy on CIFAR10, and 76.51% top-1 accuracy on ImageNet consuming only $2\times10^{-4}$ GPU days. This also demonstrates the high transferability of the proposed approach, and can potentially lead to a new, more computationally efficient paradigm in this research direction.
Adaptive Online Value Function Approximation with Wavelets
Venue: arXiv cs.LG 2022
Year: 2022

Using function approximation to represent a value function is necessary for continuous and high-dimensional state spaces. Linear function approximation has desirable theoretical guarantees and often requires less compute and samples than neural networks, but most approaches suffer from an exponential growth in the number of functions as the dimensionality of the state space increases. In this work, we introduce the wavelet basis for reinforcement learning. Wavelets can effectively be used as a fixed basis and additionally provide the ability to adaptively refine the basis set as learning progresses, making it feasible to start with a minimal basis set. This adaptive method can either increase the granularity of the approximation at a point in state space, or add in interactions between different dimensions as necessary. We prove that wavelets are both necessary and sufficient if we wish to construct a function approximator that can be adaptively refined without loss of precision. We further demonstrate that a fixed wavelet basis set performs comparably against the high-performing Fourier basis on Mountain Car and Acrobot, and that the adaptive methods provide a convenient approach to addressing an oversized initial basis set, while demonstrating performance comparable to, or greater than, the fixed wavelet basis.