OpenRaiser/Intern-Atlas huggingface dataset:
Why Exposure Bias Matters: An Imitation Learning Perspective of Error Accumulation in Language Generation
Venue: arXiv cs.CL 2023
Year: 2023

Current language generation models suffer from issues such as repetition, incoherence, and hallucinations. An often-repeated hypothesis is that this brittleness of generation models is caused by the training and the generation procedure mismatch, also referred to as exposure bias. In this paper, we verify this hypothesis by analyzing exposure bias from an imitation learning perspective. We show that exposure bias leads to an accumulation of errors, analyze why perplexity fails to capture this accumulation, and empirically show that this accumulation results in poor generation quality. Source code to reproduce these experiments is available at https://github.com/kushalarora/quantifying_exposure_bias
CIRS: Bursting Filter Bubbles by Counterfactual Interactive Recommender System
Venue: arXiv cs.IR 2023
Year: 2023

While personalization increases the utility of recommender systems, it also brings the issue of filter bubbles. E.g., if the system keeps exposing and recommending the items that the user is interested in, it may also make the user feel bored and less satisfied. Existing work studies filter bubbles in static recommendation, where the effect of overexposure is hard to capture. In contrast, we believe it is more meaningful to study the issue in interactive recommendation and optimize long-term user satisfaction. Nevertheless, it is unrealistic to train the model online due to the high cost. As such, we have to leverage offline training data and disentangle the causal effect on user satisfaction. To achieve this goal, we propose a counterfactual interactive recommender system (CIRS) that augments offline reinforcement learning (offline RL) with causal inference. The basic idea is to first learn a causal user model on historical data to capture the overexposure effect of items on user satisfaction. It then uses the learned causal user model to help the planning of the RL policy. To conduct evaluation offline, we innovatively create an authentic RL environment (KuaiEnv) based on a real-world fully observed user rating dataset. The experiments show the effectiveness of CIRS in bursting filter bubbles and achieving long-term success in interactive recommendation. The implementation of CIRS is available via https://github.com/chongminggao/CIRS-codes.
Sampling Lovász Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time
Venue: arXiv cs.DS 2023
Year: 2023

We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. Suppose that the CSP has $n$ variables with domain size at most q, each constraint contains at most k variables, shares variables with at most $Δ$ constraints, and is violated with probability at most $p$ by a uniform random assignment. The algorithm returns an almost uniform satisfying assignment in expected $\mathrm{poly}(q,k,Δ)\cdot\tilde{O}(n)$ time, as long as a local lemma condition is satisfied: \[ k\cdot p\cdot q^2\cdot Δ^5\le C_0\quad\text{for a suitably small absolute constant }C_0. \] Previously, under similar local lemma conditions, sampling algorithms with running time polynomial in both $n$ and $Δ$ were only known for the almost atomic case, where each constraint is violated by a small number of forbidden local configurations. The key term $Δ^5$ in our local lemma condition also improves the previously best known $Δ^7$ for general CSPs [JPV21b] and $Δ^{5.714}$ for atomic CSPs, including the special case of $k$-CNF [JPV21a, HSW21]. Our sampling approach departs from previous fast algorithms for sampling LLL, which were based on Markov chains. A crucial step of our algorithm is a recursive marginal sampler that is of independent interests. Within a local lemma regime, this marginal sampler can draw a random value for a variable according to its marginal distribution, at a cost independent of the size of the CSP.
Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization
Venue: arXiv cs.LG 2023
Year: 2023

In this paper we provide an algorithmic framework based on Langevin diffusion (LD) and its corresponding discretizations that allow us to simultaneously obtain: i) An algorithm for sampling from the exponential mechanism, whose privacy analysis does not depend on convexity and which can be stopped at anytime without compromising privacy, and ii) tight uniform stability guarantees for the exponential mechanism. As a direct consequence, we obtain optimal excess empirical and population risk guarantees for (strongly) convex losses under both pure and approximate differential privacy (DP). The framework allows us to design a DP uniform sampler from the Rashomon set. Rashomon sets are widely used in interpretable and robust machine learning, understanding variable importance, and characterizing fairness.
Partitioning axis-parallel lines in 3D
Venue: arXiv cs.CG 2023
Year: 2023

Let $L$ be a set of $n$ axis-parallel lines in $\mathbb{R}^3$. We are are interested in partitions of $\mathbb{R}^3$ by a set $H$ of three planes such that each open cell in the arrangement $\mathcal{A}(H)$ is intersected by as few lines from $L$ as possible. We study such partitions in three settings, depending on the type of splitting planes that we allow. We obtain the following results. $\bullet$ There are sets $L$ of $n$ axis-parallel lines such that, for any set $H$ of three splitting planes, there is an open cell in $\mathcal{A}(H)$ that intersects at least~$\lfloor n/3 \rfloor-1 \approx \frac{1}{3}n$ lines. $\bullet$ If we require the splitting planes to be axis-parallel, then there are sets $L$ of $n$ axis-parallel lines such that, for any set $H$ of three splitting planes, there is an open cell in $\mathcal{A}(H)$ that intersects at least $\frac{3}{2}\lfloor n/4 \rfloor -1 \approx \left( \frac{1}{3}+\frac{1}{24}\right) n$ lines. Furthermore, for any set $L$ of $n$ axis-parallel lines, there exists a set $H$ of three axis-parallel splitting planes such that each open cell in $\mathcal{A}(H)$ intersects at most $\frac{7}{18} n = \left( \frac{1}{3}+\frac{1}{18}\right) n$ lines. $\bullet$ For any set $L$ of $n$ axis-parallel lines, there exists a set $H$ of three axis-parallel and mutually orthogonal splitting planes, such that each open cell in $\mathcal{A}(H)$ intersects at most $\lceil \frac{5}{12} n \rceil \approx \left( \frac{1}{3}+\frac{1}{12}\right) n$ lines.
Generalized Triangular Dynamical System: An Algebraic System for Constructing Cryptographic Permutations over Finite Fields
Venue: arXiv cs.CR 2023
Year: 2023

In recent years a new class of symmetric-key primitives over $\mathbb{F}_p$ that are essential to Multi-Party Computation and Zero-Knowledge Proofs based protocols have emerged. Towards improving the efficiency of such primitives, a number of new block ciphers and hash functions over $\mathbb{F}_p$ were proposed. These new primitives also showed that following alternative design strategies to the classical Substitution-Permutation Network (SPN) and Feistel Networks leads to more efficient cipher and hash function designs over $\mathbb{F}_p$ specifically for large odd primes $p$. In view of these efforts, in this work we build an \emph{algebraic framework} that allows the systematic exploration of viable and efficient design strategies for constructing symmetric-key (iterative) permutations over $\mathbb{F}_p$. We first identify iterative polynomial dynamical systems over finite fields as the central building block of almost all block cipher design strategies. We propose a generalized triangular polynomial dynamical system (GTDS), and based on the GTDS we provide a generic definition of an iterative (keyed) permutation over $\mathbb{F}_p^n$. Our GTDS-based generic definition is able to describe the three most well-known design strategies, namely SPNs, Feistel networks and Lai--Massey. Consequently, the block ciphers that are constructed following these design strategies can also be instantiated from our generic definition. Moreover, we find that the recently proposed \texttt{Griffin} design, which neither follows the Feistel nor the SPN design, can be described using the generic GTDS-based definition. We also show that a new generalized Lai--Massey construction can be instantiated from the GTDS-based definition. We further provide generic analysis of the GTDS including an upper bound on the differential uniformity and the correlation.
Path and trajectory planning of a tethered UAV-UGV marsupial robotic system
Venue: arXiv cs.RO 2023
Year: 2023

This letter addresses the problem of trajectory planning in a marsupial robotic system consisting of an unmanned aerial vehicle (UAV) linked to an unmanned ground vehicle (UGV) through a non-taut tether with controllable length. To the best of our knowledge, this is the first method that addresses the trajectory planning of a marsupial UGV-UAV with a non-taut tether. The objective is to determine a synchronized collision-free trajectory for the three marsupial system agents: UAV, UGV, and tether. First, we present a path planning solution based on optimal Rapidly-exploring Random Trees (RRT*) with novel sampling and steering techniques to speed-up the computation. This algorithm is able to obtain collision-free paths for the UAV and the UGV, taking into account the 3D environment and the tether. Then, the letter presents a trajectory planner based on non-linear least squares. The optimizer takes into account aspects not considered in the path planning, like temporal constraints of the motion imposed by limits on the velocities and accelerations of the robots, or raising the tether's clearance. Simulated and field test results demonstrate that the approach generates obstacle-free, smooth, and feasible trajectories for the marsupial system.
RL4ReAl: Reinforcement Learning for Register Allocation
Venue: arXiv cs.LG 2023
Year: 2023

We aim to automate decades of research and experience in register allocation, leveraging machine learning. We tackle this problem by embedding a multi-agent reinforcement learning algorithm within LLVM, training it with the state of the art techniques. We formalize the constraints that precisely define the problem for a given instruction-set architecture, while ensuring that the generated code preserves semantic correctness. We also develop a gRPC based framework providing a modular and efficient compiler interface for training and inference. Our approach is architecture independent: we show experimental results targeting Intel x86 and ARM AArch64. Our results match or out-perform the heavily tuned, production-grade register allocators of LLVM.
A Set Membership Approach to Discovering Feature Relevance and Explaining Neural Classifier Decisions
Venue: arXiv cs.LG 2023
Year: 2023

Neural classifiers are non linear systems providing decisions on the classes of patterns, for a given problem they have learned. The output computed by a classifier for each pattern constitutes an approximation of the output of some unknown function, mapping pattern data to their respective classes. The lack of knowledge of such a function along with the complexity of neural classifiers, especially when these are deep learning architectures, do not permit to obtain information on how specific predictions have been made. Hence, these powerful learning systems are considered as black boxes and in critical applications their use tends to be considered inappropriate. Gaining insight on such a black box operation constitutes a one way approach in interpreting operation of neural classifiers and assessing the validity of their decisions. In this paper we tackle this problem introducing a novel methodology for discovering which features are considered relevant by a trained neural classifier and how they affect the classifier's output, thus obtaining an explanation on its decision. Although, feature relevance has received much attention in the machine learning literature here we reconsider it in terms of nonlinear parameter estimation targeted by a set membership approach which is based on interval analysis. Hence, the proposed methodology builds on sound mathematical approaches and the results obtained constitute a reliable estimation of the classifier's decision premises.
This Sample seems to be good enough! Assessing Coverage and Temporal Reliability of Twitter's Academic API
Venue: arXiv cs.SI 2023
Year: 2023

Because of its willingness to share data with academia and industry, Twitter has been the primary social media platform for scientific research as well as for consulting businesses and governments in the last decade. In recent years, a series of publications have studied and criticized Twitter's APIs and Twitter has partially adapted its existing data streams. The newest Twitter API for Academic Research allows to "access Twitter's real-time and historical public data with additional features and functionality that support collecting more precise, complete, and unbiased datasets." The main new feature of this API is the possibility of accessing the full archive of all historic Tweets. In this article, we will take a closer look at the Academic API and will try to answer two questions. First, are the datasets collected with the Academic API complete? Secondly, since Twitter's Academic API delivers historic Tweets as represented on Twitter at the time of data collection, we need to understand how much data is lost over time due to Tweet and account removal from the platform. Our work shows evidence that Twitter's Academic API can indeed create (almost) complete samples of Twitter data based on a wide variety of search terms. We also provide evidence that Twitter's data endpoint v2 delivers better samples than the previously used endpoint v1.1. Furthermore, collecting Tweets with the Academic API at the time of studying a phenomenon rather than creating local archives of stored Tweets, allows for a straightforward way of following Twitter's developer agreement. Finally, we will also discuss technical artifacts and implications of the Academic API. We hope that our work can add another layer of understanding of Twitter data collections leading to more reliable studies of human behavior via social media data.
PDNPulse: Sensing PCB Anomaly with the Intrinsic Power Delivery Network
Venue: arXiv cs.CR 2023
Year: 2023

The ubiquitous presence of printed circuit boards (PCBs) in modern electronic systems and embedded devices makes their integrity a top security concern. To take advantage of the economies of scale, today's PCB design and manufacturing are often performed by suppliers around the globe, exposing them to many security vulnerabilities along the segmented PCB supply chain. Moreover, the increasing complexity of the PCB designs also leaves ample room for numerous sneaky board-level attacks to be implemented throughout each stage of a PCB's lifetime, threatening many electronic devices. In this paper, we propose PDNPulse, a power delivery network (PDN) based PCB anomaly detection framework that can identify a wide spectrum of board-level malicious modifications. PDNPulse leverages the fact that the PDN's characteristics are inevitably affected by modifications to the PCB, no matter how minuscule. By detecting changes to the PDN impedance profile and using the Frechet distance-based anomaly detection algorithms, PDNPulse can robustly and successfully discern malicious modifications across the system. Using PDNPulse, we conduct extensive experiments on seven commercial-off-the-shelf PCBs, covering different design scales, different threat models, and seven different anomaly types. The results confirm that PDNPulse creates an effective security asymmetry between attack and defense.
PVI-DSO: Leveraging Planar Regularities for Direct Sparse Visual-Inertial Odometry
Venue: arXiv cs.RO 2023
Year: 2023

The monocular visual-inertial odometry (VIO) based on the direct method can leverage all available pixels in the image to simultaneously estimate the camera motion and reconstruct the denser map of the scene in real time. However, the direct method is sensitive to photometric changes, which can be compensated by introducing geometric information in the environment. In this paper, we propose a monocular direct sparse visual-inertial odometry, which exploits the planar regularities (PVI-DSO). Our system detects the planar regularities from the 3D mesh built on the estimated map points. To improve the pose estimation accuracy with the geometric information, a tightly coupled coplanar constraint expression is used to express photometric error in the direct method. Additionally, to improve the optimization efficiency, we elaborately derive the analytical Jacobian of the linearization form for the coplanar constraint. Finally, the inertial measurement error, coplanar point photometric error, non-coplanar photometric error, and prior error are added into the optimizer, which simultaneously improves the pose estimation accuracy and mesh itself. We verified the performance of the whole system on simulation and real-world datasets. Extensive experiments have demonstrated that our system outperforms the state-of-the-art counterparts.
Detail-recovery Image Deraining via Dual Sample-augmented Contrastive Learning
Venue: arXiv cs.CV 2023
Year: 2023

The intricacy of rainy image contents often leads cutting-edge deraining models to image degradation including remnant rain, wrongly-removed details, and distorted appearance. Such degradation is further exacerbated when applying the models trained on synthetic data to real-world rainy images. We observe two types of domain gaps between synthetic and real-world rainy images: one exists in rain streak patterns; the other is the pixel-level appearance of rain-free images. To bridge the two domain gaps, we propose a semi-supervised detail-recovery image deraining network (Semi-DRDNet) with dual sample-augmented contrastive learning. Semi-DRDNet consists of three sub-networks:i) for removing rain streaks without remnants, we present a squeeze-and-excitation based rain residual network; ii) for encouraging the lost details to return, we construct a structure detail context aggregation based detail repair network; to our knowledge, this is the first time; and iii) for building efficient contrastive constraints for both rain streaks and clean backgrounds, we exploit a novel dual sample-augmented contrastive regularization network.Semi-DRDNet operates smoothly on both synthetic and real-world rainy data in terms of deraining robustness and detail accuracy. Comparisons on four datasets including our established Real200 show clear improvements of Semi-DRDNet over fifteen state-of-the-art methods. Code and dataset are available at https://github.com/syy-whu/DRD-Net.
SPIDER-WEB generates coding algorithms with superior error tolerance and real-time information retrieval capacity
Venue: arXiv cs.ET 2023
Year: 2023

DNA has been considered a promising medium for storing digital information. As an essential step in the DNA-based data storage workflow, coding algorithms are responsible to implement functions including bit-to-base transcoding, error correction, etc. In previous studies, these functions are normally realized by introducing multiple algorithms. Here, we report a graph-based architecture, named SPIDER-WEB, providing an all-in-one coding solution by generating customized algorithms automatically. SPIDERWEB is able to correct a maximum of 4% edit errors in the DNA sequences including substitution and insertion/deletion (indel), with only 5.5% redundant symbols. Since no DNA sequence pretreatment is required for the correcting and decoding processes, SPIDER-WEB offers the function of real-time information retrieval, which is 305.08 times faster than the speed of single-molecule sequencing techniques. Our retrieval process can improve 2 orders of magnitude faster compared to the conventional one under megabyte-level data and can be scalable to fit exabyte-level data. Therefore, SPIDER-WEB holds the potential to improve the practicability in large-scale data storage applications.
Towards Automatic Construction of Filipino WordNet: Word Sense Induction and Synset Induction Using Sentence Embeddings
Venue: arXiv cs.CL 2023
Year: 2023

Wordnets are indispensable tools for various natural language processing applications. Unfortunately, wordnets get outdated, and producing or updating wordnets can be slow and costly in terms of time and resources. This problem intensifies for low-resource languages. This study proposes a method for word sense induction and synset induction using only two linguistic resources, namely, an unlabeled corpus and a sentence embeddings-based language model. The resulting sense inventory and synonym sets can be used in automatically creating a wordnet. We applied this method on a corpus of Filipino text. The sense inventory and synsets were evaluated by matching them with the sense inventory of the machine translated Princeton WordNet, as well as comparing the synsets to the Filipino WordNet. This study empirically shows that the 30% of the induced word senses are valid and 40% of the induced synsets are valid in which 20% are novel synsets.
PALBERT: Teaching ALBERT to Ponder
Venue: arXiv cs.LG 2023
Year: 2023

Currently, pre-trained models can be considered the default choice for a wide range of NLP tasks. Despite their SoTA results, there is practical evidence that these models may require a different number of computing layers for different input sequences, since evaluating all layers leads to overconfidence in wrong predictions (namely overthinking). This problem can potentially be solved by implementing adaptive computation time approaches, which were first designed to improve inference speed. Recently proposed PonderNet may be a promising solution for performing an early exit by treating the exit layer's index as a latent variable. However, the originally proposed exit criterion, relying on sampling from trained posterior distribution on the probability of exiting from the $i$-th layer, introduces major variance in exit layer indices, significantly reducing the resulting model's performance. In this paper, we propose improving PonderNet with a novel deterministic Q-exit criterion and a revisited model architecture. We adapted the proposed mechanism to ALBERT and RoBERTa and compared it with recent methods for performing an early exit. We observed that the proposed changes can be considered significant improvements on the original PonderNet architecture and outperform PABEE on a wide range of GLUE tasks. In addition, we also performed an in-depth ablation study of the proposed architecture to further understand Lambda layers and their performance.
Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
Venue: arXiv cs.IT 2023
Year: 2023

We study the robust matrix completion problem for the low-rank Hankel matrix, which detects the sparse corruptions caused by extreme outliers while we try to recover the original Hankel matrix from the partial observation. In this paper, we explore the convenient Hankel structure and propose a novel non-convex algorithm, coined Hankel Structured Gradient Descent (HSGD), for large-scale robust Hankel matrix completion problems. HSGD is highly computing- and sample-efficient compared to the state-of-the-arts. The recovery guarantee with a linear convergence rate has been established for HSGD under some mild assumptions. The empirical advantages of HSGD are verified on both synthetic datasets and real-world nuclear magnetic resonance signals.