OpenRaiser/Intern-Atlas huggingface dataset:
GraB: Finding Provably Better Data Permutations than Random Reshuffling
Venue: arXiv cs.LG 2023
Year: 2023

Random reshuffling, which randomly permutes the dataset each epoch, is widely adopted in model training because it yields faster convergence than with-replacement sampling. Recent studies indicate greedily chosen data orderings can further speed up convergence empirically, at the cost of using more computation and memory. However, greedy ordering lacks theoretical justification and has limited utility due to its non-trivial memory and computation overhead. In this paper, we first formulate an example-ordering framework named herding and answer affirmatively that SGD with herding converges at the rate $O(T^{-2/3})$ on smooth, non-convex objectives, faster than the $O(n^{1/3}T^{-2/3})$ obtained by random reshuffling, where $n$ denotes the number of data points and $T$ denotes the total number of iterations. To reduce the memory overhead, we leverage discrepancy minimization theory to propose an online Gradient Balancing algorithm (GraB) that enjoys the same rate as herding, while reducing the memory usage from $O(nd)$ to just $O(d)$ and computation from $O(n^2)$ to $O(n)$, where $d$ denotes the model dimension. We show empirically on applications including MNIST, CIFAR10, WikiText and GLUE that GraB can outperform random reshuffling in terms of both training and validation performance, and even outperform state-of-the-art greedy ordering while reducing memory usage over $100\times$.
Covariance Matrix Adaptation MAP-Annealing
Venue: arXiv cs.LG 2023
Year: 2023

Single-objective optimization algorithms search for the single highest-quality solution with respect to an objective. Quality diversity (QD) optimization algorithms, such as Covariance Matrix Adaptation MAP-Elites (CMA-ME), search for a collection of solutions that are both high-quality with respect to an objective and diverse with respect to specified measure functions. However, CMA-ME suffers from three major limitations highlighted by the QD community: prematurely abandoning the objective in favor of exploration, struggling to explore flat objectives, and having poor performance for low-resolution archives. We propose a new quality diversity algorithm, Covariance Matrix Adaptation MAP-Annealing (CMA-MAE), that addresses all three limitations. We provide theoretical justifications for the new algorithm with respect to each limitation. Our theory informs our experiments, which support the theory and show that CMA-MAE achieves state-of-the-art performance and robustness.
Self-mentoring: a new deep learning pipeline to train a self-supervised U-net for few-shot learning of bio-artificial capsule segmentation
Venue: arXiv cs.CV 2023
Year: 2023

Background: Accurate segmentation of microscopic structures such as bio-artificial capsules in microscopy imaging is a prerequisite to the computer-aided understanding of important biomechanical phenomenons. State-of-the-art segmentation performances are achieved by deep neural networks and related data-driven approaches. Training these networks from only a few annotated examples is challenging while producing manually annotated images that provide supervision is tedious. Method: Recently, self-supervision, i.e. designing a neural pipeline providing synthetic or indirect supervision, has proved to significantly increase generalization performances of models trained on few shots. The objective of this paper is to introduce one such neural pipeline in the context of micro-capsule image segmentation. Our method leverages the rather simple content of these images so that a trainee network can be mentored by a referee network which has been previously trained on synthetically generated pairs of corrupted/correct region masks. Results: Challenging experimental setups are investigated. They involve from only 3 to 10 annotated images along with moderately large amounts of unannotated images. In a bio-artificial capsule dataset, our approach consistently and drastically improves accuracy. We also show that the learnt referee network is transferable to another Glioblastoma cell dataset and that it can be efficiently coupled with data augmentation strategies. Conclusions: Experimental results show that very significant accuracy increments are obtained by the proposed pipeline, leading to the conclusion that the self-supervision mechanism introduced in this paper has the potential to replace human annotations.
AdaptivePaste: Code Adaptation through Learning Semantics-aware Variable Usage Representations
Venue: arXiv cs.SE 2023
Year: 2023

In software development, it is common for programmers to copy-paste or port code snippets and then adapt them to their use case. This scenario motivates the code adaptation task -- a variant of program repair which aims to adapt variable identifiers in a pasted snippet of code to the surrounding, preexisting source code. However, no existing approach has been shown to effectively address this task. In this paper, we introduce AdaptivePaste, a learning-based approach to source code adaptation, based on transformers and a dedicated dataflow-aware deobfuscation pre-training task to learn meaningful representations of variable usage patterns. We evaluate AdaptivePaste on a dataset of code snippets in Python. Results suggest that our model can learn to adapt source code with 79.8% accuracy. To evaluate how valuable is AdaptivePaste in practice, we perform a user study with 10 Python developers on a hundred real-world copy-paste instances. The results show that AdaptivePaste reduces the dwell time to nearly half the time it takes for manual code adaptation, and helps to avoid bugs. In addition, we utilize the participant feedback to identify potential avenues for improvement of AdaptivePaste.
POLTER: Policy Trajectory Ensemble Regularization for Unsupervised Reinforcement Learning
Venue: arXiv cs.LG 2023
Year: 2023

The goal of Unsupervised Reinforcement Learning (URL) is to find a reward-agnostic prior policy on a task domain, such that the sample-efficiency on supervised downstream tasks is improved. Although agents initialized with such a prior policy can achieve a significantly higher reward with fewer samples when finetuned on the downstream task, it is still an open question how an optimal pretrained prior policy can be achieved in practice. In this work, we present POLTER (Policy Trajectory Ensemble Regularization) - a general method to regularize the pretraining that can be applied to any URL algorithm and is especially useful on data- and knowledge-based URL algorithms. It utilizes an ensemble of policies that are discovered during pretraining and moves the policy of the URL algorithm closer to its optimal prior. Our method is based on a theoretical framework, and we analyze its practical effects on a white-box benchmark, allowing us to study POLTER with full control. In our main experiments, we evaluate POLTER on the Unsupervised Reinforcement Learning Benchmark (URLB), which consists of 12 tasks in 3 domains. We demonstrate the generality of our approach by improving the performance of a diverse set of data- and knowledge-based URL algorithms by 19% on average and up to 40% in the best case. Under a fair comparison with tuned baselines and tuned POLTER, we establish a new state-of-the-art for model-free methods on the URLB.
Graph-Based Methods for Discrete Choice
Venue: arXiv cs.LG 2023
Year: 2023

Choices made by individuals have widespread impacts--for instance, people choose between political candidates to vote for, between social media posts to share, and between brands to purchase--moreover, data on these choices are increasingly abundant. Discrete choice models are a key tool for learning individual preferences from such data. Additionally, social factors like conformity and contagion influence individual choice. Traditional methods for incorporating these factors into choice models do not account for the entire social network and require hand-crafted features. To overcome these limitations, we use graph learning to study choice in networked contexts. We identify three ways in which graph learning techniques can be used for discrete choice: learning chooser representations, regularizing choice model parameters, and directly constructing predictions from a network. We design methods in each category and test them on real-world choice datasets, including county-level 2016 US election results and Android app installation and usage data. We show that incorporating social network structure can improve the predictions of the standard econometric choice model, the multinomial logit. We provide evidence that app installations are influenced by social context, but we find no such effect on app usage among the same participants, which instead is habit-driven. In the election data, we highlight the additional insights a discrete choice framework provides over classification or regression, the typical approaches. On synthetic data, we demonstrate the sample complexity benefit of using social information in choice models.
Using Natural Language and Program Abstractions to Instill Human Inductive Biases in Machines
Venue: arXiv cs.AI 2023
Year: 2023

Strong inductive biases give humans the ability to quickly learn to perform a variety of tasks. Although meta-learning is a method to endow neural networks with useful inductive biases, agents trained by meta-learning may sometimes acquire very different strategies from humans. We show that co-training these agents on predicting representations from natural language task descriptions and programs induced to generate such tasks guides them toward more human-like inductive biases. Human-generated language descriptions and program induction models that add new learned primitives both contain abstract concepts that can compress description length. Co-training on these representations result in more human-like behavior in downstream meta-reinforcement learning agents than less abstract controls (synthetic language descriptions, program induction without learned primitives), suggesting that the abstraction supported by these representations is key.
Penguins Don't Fly: Reasoning about Generics through Instantiations and Exceptions
Venue: arXiv cs.CL 2023
Year: 2023

Generics express generalizations about the world (e.g., birds can fly) that are not universally true (e.g., newborn birds and penguins cannot fly). Commonsense knowledge bases, used extensively in NLP, encode some generic knowledge but rarely enumerate such exceptions and knowing when a generic statement holds or does not hold true is crucial for developing a comprehensive understanding of generics. We present a novel framework informed by linguistic theory to generate exemplars -- specific cases when a generic holds true or false. We generate ~19k exemplars for ~650 generics and show that our framework outperforms a strong GPT-3 baseline by 12.8 precision points. Our analysis highlights the importance of linguistic theory-based controllability for generating exemplars, the insufficiency of knowledge bases as a source of exemplars, and the challenges exemplars pose for the task of natural language inference.
Adaptive Spatiotemporal Dimension Reduction in Concurrent Multiscale Damage Analysis
Venue: arXiv cs.CE 2023
Year: 2023

Concurrent multiscale damage models are often used to quantify the impacts of manufacturing-induced micro porosity on the damage response of macroscopic metallic components. However, these models are challenged by major numerical issues including mesh dependency, convergence difficulty, and low accuracy in concentration regions. We make two contributions that collectively aim to address these difficulties. Firstly, we develop a novel adaptive assembly free impl-exp (AAF-IE) temporal integration scheme for nonlinear constitutive models. This scheme prevents the convergence issues that arise when implicit algorithms are employed to model softening. Our AAF-IE scheme autonomously adjusts step sizes to capture intricate history dependent deformations. It also dispenses with reassembling the stiffness matrices amid runtime for elasto-plasticity and damage models which, in turn, dramatically reduces memory footprints. Secondly, we propose an adaptive clustering-based domain decomposition strategy to dramatically reduce the spatial degrees of freedom by agglomerating close-by finite element nodes into a limited number of clusters. Our adaptive clustering scheme has static and dynamic stages that are carried out during offline and online analyses, respectively. The adaptive strategy determines the cluster density based on spatial discontinuity and controls adaptive clusters via field estimations. As demonstrated by numerical experiments the proposed adaptive method strikes a good balance between efficiency and accuracy for fracture simulations. In particular, we use our efficient concurrent multiscale model to quantify the significance of spatially varying microscopic porosity on a macrostructural softening behavior.
Constant Curvature Curve Tube Codes for Low-Latency Analog Error Correction
Venue: arXiv cs.IT 2023
Year: 2023

Recent research in ultra-reliable and low latency communications (URLLC) for future wireless systems has spurred interest in short block-length codes. In this context, we analyze arbitrary harmonic bandwidth (BW) expansions for a class of high-dimension constant curvature curve codes for analog error correction of independent continuous-alphabet uniform sources. In particular, we employ the circumradius function from knot theory to prescribe insulating tubes about the centerline of constant curvature curves. We then use tube packing density within a hypersphere to optimize the curve parameters. The resulting constant curvature curve tube (C3T) codes possess the smallest possible latency, i.e., block-length is unity under BW expansion mapping. Further, the codes perform within $5$ dB signal-to-distortion ratio of the optimal performance theoretically achievable at a signal-to-noise ratio (SNR) $< -5$ dB for BW expansion factor $n \leq 10$. Furthermore, we propose a neural-network-based method to decode C3T codes. We show that, at low SNR, the neural-network-based C3T decoder outperforms the maximum likelihood and minimum mean-squared error decoders for all $n$. The best possible digital codes require two to three orders of magnitude higher latency compared to C3T codes, thereby demonstrating the latter's utility for URLLC.
Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regret
Venue: arXiv cs.LG 2023
Year: 2023

We propose a new learning framework that captures the tiered structure of many real-world user-interaction applications, where the users can be divided into two groups based on their different tolerance on exploration risks and should be treated separately. In this setting, we simultaneously maintain two policies $π^{\text{O}}$ and $π^{\text{E}}$: $π^{\text{O}}$ ("O" for "online") interacts with more risk-tolerant users from the first tier and minimizes regret by balancing exploration and exploitation as usual, while $π^{\text{E}}$ ("E" for "exploit") exclusively focuses on exploitation for risk-averse users from the second tier utilizing the data collected so far. An important question is whether such a separation yields advantages over the standard online setting (i.e., $π^{\text{E}}=π^{\text{O}}$) for the risk-averse users. We individually consider the gap-independent vs.~gap-dependent settings. For the former, we prove that the separation is indeed not beneficial from a minimax perspective. For the latter, we show that if choosing Pessimistic Value Iteration as the exploitation algorithm to produce $π^{\text{E}}$, we can achieve a constant regret for risk-averse users independent of the number of episodes $K$, which is in sharp contrast to the $Ω(\log K)$ regret for any online RL algorithms in the same setting, while the regret of $π^{\text{O}}$ (almost) maintains its online regret optimality and does not need to compromise for the success of $π^{\text{E}}$.
Few-shot Reranking for Multi-hop QA via Language Model Prompting
Venue: arXiv cs.CL 2023
Year: 2023

We study few-shot reranking for multi-hop QA with open-domain questions. To alleviate the need for a large number of labeled question-document pairs for retriever training, we propose PromptRank, which relies on large language models prompting for multi-hop path reranking. PromptRank first constructs an instruction-based prompt that includes a candidate document path and then computes the relevance score between a given question and the path based on the conditional likelihood of the question given the path prompt according to a language model. PromptRank yields strong retrieval performance on HotpotQA with only 128 training examples compared to state-of-the-art methods trained on thousands of examples -- 73.6 recall@10 by PromptRank vs. 77.8 by PathRetriever and 77.5 by multi-hop dense retrieval. Code available at https://github.com/mukhal/PromptRank
Evaluating the Diversity, Equity and Inclusion of NLP Technology: A Case Study for Indian Languages
Venue: arXiv cs.CL 2023
Year: 2023

In order for NLP technology to be widely applicable, fair, and useful, it needs to serve a diverse set of speakers across the world's languages, be equitable, i.e., not unduly biased towards any particular language, and be inclusive of all users, particularly in low-resource settings where compute constraints are common. In this paper, we propose an evaluation paradigm that assesses NLP technologies across all three dimensions. While diversity and inclusion have received attention in recent literature, equity is currently unexplored. We propose to address this gap using the Gini coefficient, a well-established metric used for estimating societal wealth inequality. Using our paradigm, we highlight the distressed state of current technologies for Indian (IN) languages (a linguistically large and diverse set, with a varied speaker population), across all three dimensions. To improve upon these metrics, we demonstrate the importance of region-specific choices in model building and dataset creation, and more importantly, propose a novel, generalisable approach to optimal resource allocation during fine-tuning. Finally, we discuss steps to mitigate these biases and encourage the community to employ multi-faceted evaluation when building linguistically diverse and equitable technologies.
Optimizing Test-Time Query Representations for Dense Retrieval
Venue: arXiv cs.CL 2023
Year: 2023

Recent developments of dense retrieval rely on quality representations of queries and contexts from pre-trained query and context encoders. In this paper, we introduce TOUR (Test-Time Optimization of Query Representations), which further optimizes instance-level query representations guided by signals from test-time retrieval results. We leverage a cross-encoder re-ranker to provide fine-grained pseudo labels over retrieval results and iteratively optimize query representations with gradient descent. Our theoretical analysis reveals that TOUR can be viewed as a generalization of the classical Rocchio algorithm for pseudo relevance feedback, and we present two variants that leverage pseudo-labels as hard binary or soft continuous labels. We first apply TOUR on phrase retrieval with our proposed phrase re-ranker, and also evaluate its effectiveness on passage retrieval with an off-the-shelf re-ranker. TOUR greatly improves end-to-end open-domain question answering accuracy, as well as passage retrieval performance. TOUR also consistently improves direct re-ranking by up to 2.0% while running 1.3-2.4x faster with an efficient implementation.
Revisiting DocRED -- Addressing the False Negative Problem in Relation Extraction
Venue: arXiv cs.CL 2023
Year: 2023

The DocRED dataset is one of the most popular and widely used benchmarks for document-level relation extraction (RE). It adopts a recommend-revise annotation scheme so as to have a large-scale annotated dataset. However, we find that the annotation of DocRED is incomplete, i.e., false negative samples are prevalent. We analyze the causes and effects of the overwhelming false negative problem in the DocRED dataset. To address the shortcoming, we re-annotate 4,053 documents in the DocRED dataset by adding the missed relation triples back to the original DocRED. We name our revised DocRED dataset Re-DocRED. We conduct extensive experiments with state-of-the-art neural models on both datasets, and the experimental results show that the models trained and evaluated on our Re-DocRED achieve performance improvements of around 13 F1 points. Moreover, we conduct a comprehensive analysis to identify the potential areas for further improvement. Our dataset is publicly available at https://github.com/tonytan48/Re-DocRED.
New Explicit Good Linear Sum-Rank-Metric Codes
Venue: arXiv cs.IT 2023
Year: 2023

Sum-rank-metric codes have wide applications in universal error correction, multishot network coding, space-time coding and the construction of partial-MDS codes for repair in distributed storage. Fundamental properties of sum-rank-metric codes have been studied and some explicit or probabilistic constructions of good sum-rank-metric codes have been proposed. In this paper we give three simple constructions of explicit linear sum-rank-metric codes. In finite length regime, numerous larger linear sum-rank-metric codes with the same minimum sum-rank distances as the previous constructed codes can be derived from our constructions. For example several better linear sum-rank-metric codes over ${\bf F}_q$ with small block sizes and the matrix size $2 \times 2$ are constructed for $q=2, 3, 4$ by applying our construction to the presently known best linear codes. Asymptotically our constructed sum-rank-metric codes are close to the Gilbert-Varshamov-like bound on sum-rank-metric codes for some parameters. Finally we construct a linear MSRD code over an arbitrary finite field ${\bf F}_q$ with various square matrix sizes $n_1, n_2, \ldots, n_t$ satisfying $n_i \geq n_{i+1}^2+\cdots+n_t^2$ , $i=1, 2, \ldots, t-1$, for any given minimum sum-rank distance. There is no restriction on the block lengths $t$ and parameters $N=n_1+\cdots+n_t$ of these linear MSRD codes from the sizes of the fields ${\bf F}_q$. \end{abstract}
Tree Reconstruction using Topology Optimisation
Venue: arXiv cs.CV 2023
Year: 2023

Generating accurate digital tree models from scanned environments is invaluable for forestry, agriculture, and other outdoor industries in tasks such as identifying biomass, fall hazards and traversability, as well as digital applications such as animation and gaming. Existing methods for tree reconstruction rely on feature identification (trunk, crown, etc) to heuristically segment a forest into individual trees and generate a branch structure graph, limiting their application to sparse trees and uniform forests. However, the natural world is a messy place in which trees present with significant heterogeneity and are frequently encroached upon by the surrounding environment. We present a general method for extracting the branch structure of trees from point cloud data, which estimates the structure of trees by adapting the methods of structural topology optimisation to find the optimal material distribution to support wind-loading. We present the results of this optimisation over a wide variety of scans, and discuss the benefits and drawbacks of this novel approach to tree structure reconstruction. Despite the high variability of datasets containing trees, and the high rate of occlusions, our method generates detailed and accurate tree structures in most cases.