OpenRaiser/Intern-Atlas huggingface dataset:
langcc: A Next-Generation Compiler Compiler
Venue: arXiv cs.PL 2022
Year: 2022

Traditionally, parsing has been a laborious and error-prone component of compiler development, and most parsers for full industrial programming languages are still written by hand. The author [Zim22] shows that automatic parser generation can be practical, via a number of new innovations upon the standard LR paradigm of Knuth et al. With this methodology, we can automatically generate efficient parsers for virtually all languages that are intuitively "easy to parse". This includes Golang 1.17.8 and Python 3.9.12, for which our generated parsers are, respectively, 1.2x and 4.3x faster than the standard parsers. This document is a companion technical report which describes the software implementation of that work, which is available open-source at https://github.com/jzimmerman/langcc.
Advertising Media and Target Audience Optimization via High-dimensional Bandits
Venue: arXiv cs.LG 2022
Year: 2022

We present a data-driven algorithm that advertisers can use to automate their digital ad-campaigns at online publishers. The algorithm enables the advertiser to search across available target audiences and ad-media to find the best possible combination for its campaign via online experimentation. The problem of finding the best audience-ad combination is complicated by a number of distinctive challenges, including (a) a need for active exploration to resolve prior uncertainty and to speed the search for profitable combinations, (b) many combinations to choose from, giving rise to high-dimensional search formulations, and (c) very low success probabilities, typically just a fraction of one percent. Our algorithm (designated LRDL, an acronym for Logistic Regression with Debiased Lasso) addresses these challenges by combining four elements: a multiarmed bandit framework for active exploration; a Lasso penalty function to handle high dimensionality; an inbuilt debiasing kernel that handles the regularization bias induced by the Lasso; and a semi-parametric regression model for outcomes that promotes cross-learning across arms. The algorithm is implemented as a Thompson Sampler, and to the best of our knowledge, it is the first that can practically address all of the challenges above. Simulations with real and synthetic data show the method is effective and document its superior performance against several benchmarks from the recent high-dimensional bandit literature.
Sample-based Uncertainty Quantification with a Single Deterministic Neural Network
Venue: arXiv cs.LG 2022
Year: 2022

Development of an accurate, flexible, and numerically efficient uncertainty quantification (UQ) method is one of fundamental challenges in machine learning. Previously, a UQ method called DISCO Nets has been proposed (Bouchacourt et al., 2016), which trains a neural network by minimizing the energy score. In this method, a random noise vector in $\mathbb{R}^{10\text{--}100}$ is concatenated with the original input vector in order to produce a diverse ensemble forecast despite using a single neural network. While this method has shown promising performance on a hand pose estimation task in computer vision, it remained unexplored whether this method works as nicely for regression on tabular data, and how it competes with more recent advanced UQ methods such as NGBoost. In this paper, we propose an improved neural architecture of DISCO Nets that admits faster and more stable training while only using a compact noise vector of dimension $\sim \mathcal{O}(1)$. We benchmark this approach on miscellaneous real-world tabular datasets and confirm that it is competitive with or even superior to standard UQ baselines. Moreover we observe that it exhibits better point forecast performance than a neural network of the same size trained with the conventional mean squared error. As another advantage of the proposed method, we show that local feature importance computation methods such as SHAP can be easily applied to any subregion of the predictive distribution. A new elementary proof for the validity of using the energy score to learn predictive distributions is also provided.
Computed Decision Weights and a New Learning Algorithm for Neural Classifiers
Venue: arXiv cs.LG 2022
Year: 2022

In this paper we consider the possibility of computing rather than training the decision layer weights of a neural classifier. Such a possibility arises in two way, from making an appropriate choice of loss function and by solving a problem of constrained optimization. The latter formulation leads to a promising new learning process for pre-decision weights with both simplicity and efficacy.
A Nearly Tight Lower Bound for the $d$-Dimensional Cow-Path Problem
Venue: arXiv cs.DS 2022
Year: 2022

In the $d$-dimensional cow-path problem, a cow living in $\mathbb{R}^d$ must locate a $(d - 1)$-dimensional hyperplane $H$ whose location is unknown. The only way that the cow can find $H$ is to roam $\mathbb{R}^d$ until it intersects $\mathcal{H}$. If the cow travels a total distance $s$ to locate a hyperplane $H$ whose distance from the origin was $r \ge 1$, then the cow is said to achieve competitive ratio $s / r$. It is a classic result that, in $\mathbb{R}^2$, the optimal (deterministic) competitive ratio is $9$. In $\mathbb{R}^3$, the optimal competitive ratio is known to be at most $\approx 13.811$. But in higher dimensions, the asymptotic relationship between $d$ and the optimal competitive ratio remains an open question. The best upper and lower bounds, due to Antoniadis et al., are $O(d^{3/2})$ and $Ω(d)$, leaving a gap of roughly $\sqrt{d}$. In this note, we achieve a stronger lower bound of $\tildeΩ(d^{3/2})$.
NeuCEPT: Locally Discover Neural Networks' Mechanism via Critical Neurons Identification with Precision Guarantee
Venue: arXiv cs.LG 2022
Year: 2022

Despite recent studies on understanding deep neural networks (DNNs), there exists numerous questions on how DNNs generate their predictions. Especially, given similar predictions on different input samples, are the underlying mechanisms generating those predictions the same? In this work, we propose NeuCEPT, a method to locally discover critical neurons that play a major role in the model's predictions and identify model's mechanisms in generating those predictions. We first formulate a critical neurons identification problem as maximizing a sequence of mutual-information objectives and provide a theoretical framework to efficiently solve for critical neurons while keeping the precision under control. NeuCEPT next heuristically learns different model's mechanisms in an unsupervised manner. Our experimental results show that neurons identified by NeuCEPT not only have strong influence on the model's predictions but also hold meaningful information about model's mechanisms.
Infrared: A Meta Bug Detector
Venue: arXiv cs.SE 2022
Year: 2022

The recent breakthroughs in deep learning methods have sparked a wave of interest in learning-based bug detectors. Compared to the traditional static analysis tools, these bug detectors are directly learned from data, thus, easier to create. On the other hand, they are difficult to train, requiring a large amount of data which is not readily available. In this paper, we propose a new approach, called meta bug detection, which offers three crucial advantages over existing learning-based bug detectors: bug-type generic (i.e., capable of catching the types of bugs that are totally unobserved during training), self-explainable (i.e., capable of explaining its own prediction without any external interpretability methods) and sample efficient (i.e., requiring substantially less training data than standard bug detectors). Our extensive evaluation shows our meta bug detector (MBD) is effective in catching a variety of bugs including null pointer dereference, array index out-of-bound, file handle leak, and even data races in concurrent programs; in the process MBD also significantly outperforms several noteworthy baselines including Facebook Infer, a prominent static analysis tool, and FICS, the latest anomaly detection method.
Perception-Distortion Trade-off in the SR Space Spanned by Flow Models
Venue: arXiv cs.CV 2022
Year: 2022

Flow-based generative super-resolution (SR) models learn to produce a diverse set of feasible SR solutions, called the SR space. Diversity of SR solutions increases with the temperature ($τ$) of latent variables, which introduces random variations of texture among sample solutions, resulting in visual artifacts and low fidelity. In this paper, we present a simple but effective image ensembling/fusion approach to obtain a single SR image eliminating random artifacts and improving fidelity without significantly compromising perceptual quality. We achieve this by benefiting from a diverse set of feasible photo-realistic solutions in the SR space spanned by flow models. We propose different image ensembling and fusion strategies which offer multiple paths to move sample solutions in the SR space to more desired destinations in the perception-distortion plane in a controllable manner depending on the fidelity vs. perceptual quality requirements of the task at hand. Experimental results demonstrate that our image ensembling/fusion strategy achieves more promising perception-distortion trade-off compared to sample SR images produced by flow models and adversarially trained models in terms of both quantitative metrics and visual quality.
Data-driven Loop Closure Detection in Bathymetric Point Clouds for Underwater SLAM
Venue: arXiv cs.RO 2022
Year: 2022

Simultaneous localization and mapping (SLAM) frameworks for autonomous navigation rely on robust data association to identify loop closures for back-end trajectory optimization. In the case of autonomous underwater vehicles (AUVs) equipped with multibeam echosounders (MBES), data association is particularly challenging due to the scarcity of identifiable landmarks in the seabed, the large drift in dead-reckoning navigation estimates to which AUVs are prone and the low resolution characteristic of MBES data. Deep learning solutions to loop closure detection have shown excellent performance on data from more structured environments. However, their transfer to the seabed domain is not immediate and efforts to port them are hindered by the lack of bathymetric datasets. Thus, in this paper we propose a neural network architecture aimed to showcase the potential of adapting such techniques to correspondence matching in bathymetric data. We train our framework on real bathymetry from an AUV mission and evaluate its performance on the tasks of loop closure detection and coarse point cloud alignment. Finally, we show its potential against a more traditional method and release both its implementation and the dataset used.
Resource Allocation of STAR-RIS Assisted Full-Duplex Systems
Venue: arXiv cs.IT 2022
Year: 2022

Well-designed simultaneously transmitting and reflecting RIS (STAR-RIS), which extends the half-space coverage to full-space coverage, incurs wireless communication environments to be smart and reconfigurable. In this paper, we survey how STAR-RIS affects the performance of full-duplex communication systems with the presence of full-duplex users, wherein the base station (BS) and the uplink users are subject to maximum transmission power constraints. Firstly, the weighted sum-rate (WSR) is derived as a system performance metric. Then, we formulate the resource allocation design into an equivalent weighted minimum mean-square-error form and then transform it into several convex sub-problems to maximize the WSR as an optimization problem which jointly optimizes the beamforming and the combining vectors at the BS, the transmit powers of the uplink users, and phase shifts of STAR-RIS. Although the WSR optimization is non-convex, an efficient iterative alternating procedure is proposed to achieve a sub-optimal solution for the optimization problem. Secondly, the STAR-RIS's phase shifts are optimized via the successive convex approximation technique. Finally, numerical results are provided to explain how STAR-RIS improves the performance metric with the presence of full-duplex users.
Membership Inference Attacks and Generalization: A Causal Perspective
Venue: arXiv cs.LG 2022
Year: 2022

Membership inference (MI) attacks highlight a privacy weakness in present stochastic training methods for neural networks. It is not well understood, however, why they arise. Are they a natural consequence of imperfect generalization only? Which underlying causes should we address during training to mitigate these attacks? Towards answering such questions, we propose the first approach to explain MI attacks and their connection to generalization based on principled causal reasoning. We offer causal graphs that quantitatively explain the observed MI attack performance achieved for $6$ attack variants. We refute several prior non-quantitative hypotheses that over-simplify or over-estimate the influence of underlying causes, thereby failing to capture the complex interplay between several factors. Our causal models also show a new connection between generalization and MI attacks via their shared causal factors. Our causal models have high predictive power ($0.90$), i.e., their analytical predictions match with observations in unseen experiments often, which makes analysis via them a pragmatic alternative.
Creating Structure in Web Archives With Collections: Different Concepts From Web Archivists
Venue: arXiv cs.DL 2022
Year: 2022

As web archives' holdings grow, archivists subdivide them into collections so they are easier to understand and manage. In this work, we review the collection structures of eight web archive platforms: : Archive-It, Conifer, the Croatian Web Archive (HAW), the Internet Archive's user account web archives, Library of Congress (LC), PANDORA, Trove, and the UK Web Archive (UKWA). We note a plethora of different approaches to web archive collection structures. Some web archive collections support sub-collections and some permit embargoes. Curatorial decisions may be attributed to a single organization or many. Archived web pages are known by many names: mementos, copies, captures, or snapshots. Some platforms restrict a memento to a single collection and others allow mementos to cross collections. Knowledge of collection structures has implications for many different applications and users. Visitors will need to understand how to navigate collections. Future archivists will need to understand what options are available for designing collections. Platform designers need it to know what possibilities exist. The developers of tools that consume collections need to understand collection structures so they can meet the needs of their users.
Probabilistic Population Protocol Models
Venue: arXiv cs.DC 2022
Year: 2022

Population protocols are a relatively novel computational model in which very resource-limited anonymous agents interact in pairs with the goal of computing predicates. We consider the probabilistic version of this model, which naturally allows to consider the setup in which a small probability of an incorrect output is tolerated. The main focus of this thesis is the question of confident leader election, which is an extension of the regular leader election problem with an extra requirement for the eventual leader to detect its uniqueness. Having a confident leader allows the population protocols to determine the convergence of its computations. This behaviour of the model is highly beneficial and was shown to be feasible when the original model is extended in various ways. We show that it takes a linear in terms of the population size number of interactions for a probabilistic population protocol to have a non-zero fraction of agents in all reachable states, starting from a configuration with all agents in the same state. This leads us to a conclusion that confident leader election is out of reach even with the probabilistic version of the model.
Uncertainty Aware Multitask Pyramid Vision Transformer For UAV-Based Object Re-Identification
Venue: arXiv cs.CV 2022
Year: 2022

Object Re-IDentification (ReID), one of the most significant problems in biometrics and surveillance systems, has been extensively studied by image processing and computer vision communities in the past decades. Learning a robust and discriminative feature representation is a crucial challenge for object ReID. The problem is even more challenging in ReID based on Unmanned Aerial Vehicle (UAV) as the images are characterized by continuously varying camera parameters (e.g., view angle, altitude, etc.) of a flying drone. To address this challenge, multiscale feature representation has been considered to characterize images captured from UAV flying at different altitudes. In this work, we propose a multitask learning approach, which employs a new multiscale architecture without convolution, Pyramid Vision Transformer (PVT), as the backbone for UAV-based object ReID. By uncertainty modeling of intraclass variations, our proposed model can be jointly optimized using both uncertainty-aware object ID and camera ID information. Experimental results are reported on PRAI and VRAI, two ReID data sets from aerial surveillance, to verify the effectiveness of our proposed approach
Density-aware NeRF Ensembles: Quantifying Predictive Uncertainty in Neural Radiance Fields
Venue: arXiv cs.CV 2022
Year: 2022

We show that ensembling effectively quantifies model uncertainty in Neural Radiance Fields (NeRFs) if a density-aware epistemic uncertainty term is considered. The naive ensembles investigated in prior work simply average rendered RGB images to quantify the model uncertainty caused by conflicting explanations of the observed scene. In contrast, we additionally consider the termination probabilities along individual rays to identify epistemic model uncertainty due to a lack of knowledge about the parts of a scene unobserved during training. We achieve new state-of-the-art performance across established uncertainty quantification benchmarks for NeRFs, outperforming methods that require complex changes to the NeRF architecture and training regime. We furthermore demonstrate that NeRF uncertainty can be utilised for next-best view selection and model refinement.
Distributed Execution Indexing
Venue: arXiv cs.DC 2022
Year: 2022

This work-in-progress report presents both the design and partial evaluation of distributed execution indexing, a technique for microservice applications that precisely identifies dynamic instances of inter-service remote procedure calls (RPCs). Such an indexing scheme is critical for request-level fault injection techniques, which aim to automatically find failure-handling bugs in microservice applications.Distributed execution indexes enable granular specification of request-level faults, while also establishing a correspondence between inter-service RPCs across multiple executions, as is required to perform a systematic search of the fault space.In this paper, we formally define the general concept of a distributed execution index, which can be parameterized on different ways of identifying an RPC in a single service. We identify an instantiation that maintains precision in the presence of a variety of program structure complexities such as loops, function indirection, and concurrency with scheduling nondeterminism. We demonstrate that this particular instantiation addresses gaps in the state-of-the-art in request-level fault injection and show that they are all special cases of distributed execution indexing. We discuss the implementation challenges and provide an implementation of distributed execution indexing as an extension of \Filibuster{}, a resilience testing tool for microservice applications for the Java programming language, which supports fault injection for gRPC and HTTP.
An Optimal Level-synchronous Shared-memory Parallel BFS Algorithm with Optimal parallel Prefix-sum Algorithm and its Implications for Energy Consumption
Venue: arXiv cs.DC 2022
Year: 2022

We present a work-efficient parallel level-synchronous Breadth First Search (BFS) algorithm for shared-memory architectures which achieves the theoretical lower bound on parallel running time. The optimality holds regardless of the shape of the graph. We also demonstrate the implication of this optimality for the energy consumption of the program empirically. The key idea is never to use more processing cores than necessary to complete the work in any computation step efficiently. We keep the rest of the cores idle to save energy and to reduce other resource contentions (e.g., bandwidth, shared caches, etc). Our BFS does not use locks and atomic instructions and is easily extendible to shared-memory coprocessors.
S$^3$R: Self-supervised Spectral Regression for Hyperspectral Histopathology Image Classification
Venue: arXiv cs.CV 2022
Year: 2022

Benefited from the rich and detailed spectral information in hyperspectral images (HSI), HSI offers great potential for a wide variety of medical applications such as computational pathology. But, the lack of adequate annotated data and the high spatiospectral dimensions of HSIs usually make classification networks prone to overfit. Thus, learning a general representation which can be transferred to the downstream tasks is imperative. To our knowledge, no appropriate self-supervised pre-training method has been designed for histopathology HSIs. In this paper, we introduce an efficient and effective Self-supervised Spectral Regression (S$^3$R) method, which exploits the low rank characteristic in the spectral domain of HSI. More concretely, we propose to learn a set of linear coefficients that can be used to represent one band by the remaining bands via masking out these bands. Then, the band is restored by using the learned coefficients to reweight the remaining bands. Two pre-text tasks are designed: (1)S$^3$R-CR, which regresses the linear coefficients, so that the pre-trained model understands the inherent structures of HSIs and the pathological characteristics of different morphologies; (2)S$^3$R-BR, which regresses the missing band, making the model to learn the holistic semantics of HSIs. Compared to prior arts i.e., contrastive learning methods, which focuses on natural images, S$^3$R converges at least 3 times faster, and achieves significant improvements up to 14% in accuracy when transferring to HSI classification tasks.
Scale Attention for Learning Deep Face Representation: A Study Against Visual Scale Variation
Venue: arXiv cs.CV 2022
Year: 2022

Human face images usually appear with wide range of visual scales. The existing face representations pursue the bandwidth of handling scale variation via multi-scale scheme that assembles a finite series of predefined scales. Such multi-shot scheme brings inference burden, and the predefined scales inevitably have gap from real data. Instead, learning scale parameters from data, and using them for one-shot feature inference, is a decent solution. To this end, we reform the conv layer by resorting to the scale-space theory, and achieve two-fold facilities: 1) the conv layer learns a set of scales from real data distribution, each of which is fulfilled by a conv kernel; 2) the layer automatically highlights the feature at the proper channel and location corresponding to the input pattern scale and its presence. Then, we accomplish the hierarchical scale attention by stacking the reformed layers, building a novel style named SCale AttentioN Conv Neural Network (\textbf{SCAN-CNN}). We apply SCAN-CNN to the face recognition task and push the frontier of SOTA performance. The accuracy gain is more evident when the face images are blurry. Meanwhile, as a single-shot scheme, the inference is more efficient than multi-shot fusion. A set of tools are made to ensure the fast training of SCAN-CNN and zero increase of inference cost compared with the plain CNN.