OpenRaiser/Intern-Atlas huggingface dataset:
Utilizing Navigation Paths to Generate Target Points for Enhanced End-to-End Autonomous Driving Planning
Venue: arXiv cs.RO 2024
Year: 2024

In recent years, end-to-end autonomous driving frameworks have been shown to not only enhance perception performance but also improve planning capabilities. However, most previous end-to-end autonomous driving frameworks have focused primarily on enhancing environmental perception while neglecting the learning of autonomous vehicle driving intent, which refers to the vehicle's intended direction of travel. In planning, the autonomous vehicle's direction is clear and well-defined, yet this crucial aspect has often been overlooked. This paper introduces NTT (Navigation to Target for Trajectory planning), a method within an end-to-end framework for autonomous driving. NTT generates the planned trajectory in two steps. First, it generates the future target point for the autonomous vehicle on the basis of the navigation path. Then, it produces the complete planned trajectory on the basis of this target point. On the one hand, generating the target point for the autonomous vehicle from the navigation path enables the vehicle to learn a clear driving intent. On the other hand, generating the trajectory on the basis of the target point allows for a flexible planned trajectory that can adapt to complex environmental changes, thereby enhancing the safety of the planning process. Our method achieved excellent planning performance on the widely used nuScenes dataset and its effectiveness was validated through ablation experiments.
PRIBOOT: A New Data-Driven Expert for Improved Driving Simulations
Venue: arXiv cs.RO 2024
Year: 2024

The development of Autonomous Driving (AD) systems in simulated environments like CARLA is crucial for advancing real-world automotive technologies. To drive innovation, CARLA introduced Leaderboard 2.0, significantly more challenging than its predecessor. However, current AD methods have struggled to achieve satisfactory outcomes due to a lack of sufficient ground truth data. Human driving logs provided by CARLA are insufficient, and previously successful expert agents like Autopilot and Roach, used for collecting datasets, have seen reduced effectiveness under these more demanding conditions. To overcome these data limitations, we introduce PRIBOOT, an expert agent that leverages limited human logs with privileged information. We have developed a novel BEV representation specifically tailored to meet the demands of this new benchmark and processed it as an RGB image to facilitate the application of transfer learning techniques, instead of using a set of masks. Additionally, we propose the Infraction Rate Score (IRS), a new evaluation metric designed to provide a more balanced assessment of driving performance over extended routes. PRIBOOT is the first model to achieve a Route Completion (RC) of 75% in Leaderboard 2.0, along with a Driving Score (DS) and IRS of 20% and 45%, respectively. With PRIBOOT, researchers can now generate extensive datasets, potentially solving the data availability issues that have hindered progress in this benchmark.
A Sticker is Worth a Thousand Words: Characterizing the Use of Stickers in WhatsApp Political Groups in Brazil
Venue: arXiv cs.SI 2024
Year: 2024

With the increasing use of smartphones, instant messaging platforms turned into important communication tools. According to WhatsApp, more than 100 billion messages are sent each day on the app. Communication on these platforms has allowed individuals to express themselves in other types of media, rather than simple text, including audio, videos, images, and stickers. Particularly, stickers are a new multimedia format that emerged with messaging apps, promoting new forms of interactions among users, especially in the Brazilian context, transcending their role as a mere form of humor to become a key element in political strategy. In this regard, we investigate how stickers are being used, unveiling unique characteristics that these media bring to WhatsApp chats and the political use of this new media format. To achieve that, we collected a large sample of messages from WhatsApp public political discussion groups in Brazil and analyzed the sticker messages shared in this context
DafnyBench: A Benchmark for Formal Software Verification
Venue: arXiv cs.SE 2024
Year: 2024

We introduce DafnyBench, the largest benchmark of its kind for training and evaluating machine learning systems for formal software verification. We test the ability of LLMs such as GPT-4 and Claude 3 to auto-generate enough hints for the Dafny formal verification engine to successfully verify over 750 programs with about 53,000 lines of code. The best model and prompting scheme achieved 68% success rate, and we quantify how this rate improves when retrying with error message feedback and how it deteriorates with the amount of required code and hints. We hope that DafnyBench will enable rapid improvements from this baseline as LLMs and verification techniques grow in quality.
Strategies for Pretraining Neural Operators
Venue: arXiv cs.LG 2024
Year: 2024

Pretraining for partial differential equation (PDE) modeling has recently shown promise in scaling neural operators across datasets to improve generalizability and performance. Despite these advances, our understanding of how pretraining affects neural operators is still limited; studies generally propose tailored architectures and datasets that make it challenging to compare or examine different pretraining frameworks. To address this, we compare various pretraining methods without optimizing architecture choices to characterize pretraining dynamics on different models and datasets as well as to understand its scaling and generalization behavior. We find that pretraining is highly dependent on model and dataset choices, but in general transfer learning or physics-based pretraining strategies work best. In addition, pretraining performance can be further improved by using data augmentations. Lastly, pretraining can be additionally beneficial when fine-tuning in scarce data regimes or when generalizing to downstream data similar to the pretraining distribution. Through providing insights into pretraining neural operators for physics prediction, we hope to motivate future work in developing and evaluating pretraining methods for PDEs.
Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups
Venue: arXiv cs.SC 2024
Year: 2024

We show that it is undecidable whether a system of linear equations over the Laurent polynomial ring $\mathbb{Z}[X^{\pm}]$ admit solutions where a specified subset of variables take value in the set of monomials $\{X^z \mid z \in \mathbb{Z}\}$. In particular, we construct a finitely presented $\mathbb{Z}[X^{\pm}]$-module, where it is undecidable whether a linear equation $X^{z_1} \boldsymbol{f}_1 + \cdots + X^{z_n} \boldsymbol{f}_n = \boldsymbol{f}_0$ has solutions $z_1, \ldots, z_n \in \mathbb{Z}$. This contrasts the decidability of the case $n = 1$, which can be deduced from Noskov's Lemma. We apply this result to settle a number of problems in computational group theory. We show that it is undecidable whether a system of equations has solutions in the wreath product $\mathbb{Z} \wr \mathbb{Z}$, providing a negative answer to an open problem of Kharlampovich, López and Miasnikov (2020). We show that there exists a finitely generated abelian-by-cyclic group in which the problem of solving a single quadratic equation is undecidable. We also construct a finitely generated abelian-by-cyclic group, different to that of Mishchenko and Treier (2017), in which the Knapsack Problem is undecidable. In contrast, we show that the problem of Coset Intersection is decidable in all finitely generated abelian-by-cyclic groups.
An origami Universal Turing Machine design
Venue: arXiv cs.CC 2024
Year: 2024

It has been known since 1996 that deciding whether a collection of creases on a piece of paper can be fully folded flat without causing self-intersection or adding new creases is an NP-Hard problem (Bern and Hayes). In their proof, a binary state was implemented as a pleat, with the state corresponding to the pleat layering order; states then interact via pleat intersections. Building on some of the machinery of their result, we will present a method for constructing an origami NAND logic gate, leading to a theoretical origami Universal Turing Machine.
On the Simulation Power of Surface Chemical Reaction Networks
Venue: arXiv cs.CC 2024
Year: 2024

The Chemical Reaction Network (CRN) is a well-studied model that describes the interaction of molecules in well-mixed solutions. In 2014, Qian and Winfree [22] proposed the abstract surface chemical reaction network model (sCRN), which takes the advantage of spatial separation by placing molecules on a structured surface, limiting the interaction between molecules. In this model, molecules can only react with their immediate neighbors. Many follow up works study the computational and pattern-construction power of sCRNs. In this work, our goal is to describe the power of sCRN by relating the model to other well-studied models in distributed computation. In this work, our main result is to show that, given the same initial configuration, sCRN, affinity strengthening tile automata, cellular automata, and amoebot can all simulate each other (up to unavoidable rotation and reflection of the pattern). One of our techniques is a coloring on-the-fly, which allows all molecules in sCRN to have a global orientation.
Newman's theorem via Carathéodory
Venue: arXiv cs.CC 2024
Year: 2024

We give a streamlined short proof of Newman's theorem in communication complexity by applying the classical and the approximate Carathéodory's theorems.
Predicting Cascading Failures with a Hyperparametric Diffusion Model
Venue: arXiv cs.SI 2024
Year: 2024

In this paper, we study cascading failures in power grids through the lens of information diffusion models. Similar to the spread of rumors or influence in an online social network, it has been observed that failures (outages) in a power grid can spread contagiously, driven by viral spread mechanisms. We employ a stochastic diffusion model that is Markovian (memoryless) and local (the activation of one node, i.e., transmission line, can only be caused by its neighbors). Our model integrates viral diffusion principles with physics-based concepts, by correlating the diffusion weights (contagion probabilities between transmission lines) with the hyperparametric Information Cascades (IC) model. We show that this diffusion model can be learned from traces of cascading failures, enabling accurate modeling and prediction of failure propagation. This approach facilitates actionable information through well-understood and efficient graph analysis methods and graph diffusion simulations. Furthermore, by leveraging the hyperparametric model, we can predict diffusion and mitigate the risks of cascading failures even in unseen grid configurations, whereas existing methods falter due to a lack of training data. Extensive experiments based on a benchmark power grid and simulations therein show that our approach effectively captures the failure diffusion phenomena and guides decisions to strengthen the grid, reducing the risk of large-scale cascading failures. Additionally, we characterize our model's sample complexity, improving upon the existing bound.
Adaptive Teaching with Shared Classifier for Knowledge Distillation
Venue: arXiv cs.CV 2024
Year: 2024

Knowledge distillation (KD) is a technique used to transfer knowledge from an overparameterized teacher network to a less-parameterized student network, thereby minimizing the incurred performance loss. KD methods can be categorized into offline and online approaches. Offline KD leverages a powerful pretrained teacher network, while online KD allows the teacher network to be adjusted dynamically to enhance the learning effectiveness of the student network. Recently, it has been discovered that sharing the classifier of the teacher network can significantly boost the performance of the student network with only a minimal increase in the number of network parameters. Building on these insights, we propose adaptive teaching with a shared classifier (ATSC). In ATSC, the pretrained teacher network self-adjusts to better align with the learning needs of the student network based on its capabilities, and the student network benefits from the shared classifier, enhancing its performance. Additionally, we extend ATSC to environments with multiple teachers. We conduct extensive experiments, demonstrating the effectiveness of the proposed KD method. Our approach achieves state-of-the-art results on the CIFAR-100 and ImageNet datasets in both single-teacher and multiteacher scenarios, with only a modest increase in the number of required model parameters. The source code is publicly available at https://github.com/random2314235/ATSC.
Validating Temporal Compliance Patterns: A Unified Approach with $MTL_f$ over various Data Models
Venue: arXiv cs.DB 2024
Year: 2024

Process mining extracts valuable insights from event data to help organizations improve their business processes, which is essential for their growth and success. By leveraging process mining techniques, organizations gain a comprehensive understanding of their processes' execution, enabling the discovery of process models, detection of deviations, identification of bottlenecks, and assessment of performance. Compliance checking, a specific area within conformance checking, ensures that the organizational activities adhere to prescribed process models and regulations. Linear Temporal Logic over finite traces ($LTL_{f}$ ) is commonly used for conformance checking, but it may not capture all temporal aspects accurately. This paper proposes Metric Temporal Logic over finite traces ($MTL_{f}$ ) to define explicit time-related constraints effectively in addition to the implicit time-ordering covered by $LTL_f$. Therefore, it provides a universal formal approach to capture compliance rules. Moreover, we define a minimal set of generic $MTL_f$ formulas and show that they are capable of capturing all the common patterns for compliance rules. As compliance validation is largely driven by the data model used to represent the event logs, we provide a mapping from $MTL_f$ to the common data models we found in the literature to encode event logs, namely, the relational and the graph models. A comprehensive study comparing various data models and an empirical evaluation across real-life event logs demonstrates the effectiveness of the proposed approach.
LLM-assisted Concept Discovery: Automatically Identifying and Explaining Neuron Functions
Venue: arXiv cs.CV 2024
Year: 2024

Providing textual concept-based explanations for neurons in deep neural networks (DNNs) is of importance in understanding how a DNN model works. Prior works have associated concepts with neurons based on examples of concepts or a pre-defined set of concepts, thus limiting possible explanations to what the user expects, especially in discovering new concepts. Furthermore, defining the set of concepts requires manual work from the user, either by directly specifying them or collecting examples. To overcome these, we propose to leverage multimodal large language models for automatic and open-ended concept discovery. We show that, without a restricted set of pre-defined concepts, our method gives rise to novel interpretable concepts that are more faithful to the model's behavior. To quantify this, we validate each concept by generating examples and counterexamples and evaluating the neuron's response on this new set of images. Collectively, our method can discover concepts and simultaneously validate them, providing a credible automated tool to explain deep neural networks.
Enhancing Path Selections with Interference Graphs in Multihop Relay Wireless Networks
Venue: arXiv cs.NI 2024
Year: 2024

The multihop relay wireless networks have gained traction due to the emergence of Reconfigurable Intelligent Surfaces (RISs) which can be used as relays in high frequency range wireless network, including THz or mmWave. To select paths in these networks, the transmission performance plays the key network in these networks. In this paper, we enhance and greatly simplify the path selection in multihop relay RIS enabled wireless networks with what we refer to as interference graphs. Interference graphs are created based on SNR model, conical and cylindrical beam shapes in the transmission and the related interference model. Once created, they can be simply and efficiently used to select valid paths, without overestimation of the effect of interference. The results show that decreased ordering of conflict selections in the graphs yields the best results, as compared to conservative approach that tolerates no interference.
PETSc/TAO Developments for GPU-Based Early Exascale Systems
Venue: arXiv cs.MS 2024
Year: 2024

The Portable Extensible Toolkit for Scientific Computation (PETSc) library provides scalable solvers for nonlinear time-dependent differential and algebraic equations and for numerical optimization via the Toolkit for Advanced Optimization (TAO). PETSc is used in dozens of scientific fields and is an important building block for many simulation codes. During the U.S. Department of Energy's Exascale Computing Project, the PETSc team has made substantial efforts to enable efficient utilization of the massive fine-grain parallelism present within exascale compute nodes and to enable performance portability across exascale architectures. We recap some of the challenges that designers of numerical libraries face in such an endeavor, and then discuss the many developments we have made, which include the addition of new GPU backends, features supporting efficient on-device matrix assembly, better support for asynchronicity and GPU kernel concurrency, and new communication infrastructure. We evaluate the performance of these developments on some pre-exascale systems as well the early exascale systems Frontier and Aurora, using compute kernel, communication layer, solver, and mini-application benchmark studies, and then close with a few observations drawn from our experiences on the tension between portable performance and other goals of numerical libraries.
Optimized Dual-Volumes for Tetrahedral Meshes
Venue: arXiv cs.GR 2024
Year: 2024

Constructing well-behaved Laplacian and mass matrices is essential for tetrahedral mesh processing. Unfortunately, the \emph{de facto} standard linear finite elements exhibit bias on tetrahedralized regular grids, motivating the development of finite-volume methods. In this paper, we place existing methods into a common construction, showing how their differences amount to the choice of simplex centers. These choices lead to satisfaction or breakdown of important properties: continuity with respect to vertex positions, positive semi-definiteness of the implied Dirichlet energy, positivity of the mass matrix, and unbiased-ness on regular grids. Based on this analysis, we propose a new method for constructing dual-volumes which explicitly satisfy all of these properties via convex optimization.
How to Distinguish AI-Generated Images from Authentic Photographs
Venue: arXiv cs.HC 2024
Year: 2024

The high level of photorealism in state-of-the-art diffusion models like Midjourney, Stable Diffusion, and Firefly makes it difficult for untrained humans to distinguish between real photographs and AI-generated images. To address this problem, we designed a guide to help readers develop a more critical eye toward identifying artifacts, inconsistencies, and implausibilities that often appear in AI-generated images. The guide is organized into five categories of artifacts and implausibilities: anatomical, stylistic, functional, violations of physics, and sociocultural. For this guide, we generated 138 images with diffusion models, curated 9 images from social media, and curated 42 real photographs. These images showcase the kinds of cues that prompt suspicion towards the possibility an image is AI-generated and why it is often difficult to draw conclusions about an image's provenance without any context beyond the pixels in an image. Human-perceptible artifacts are not always present in AI-generated images, but this guide reveals artifacts and implausibilities that often emerge. By drawing attention to these kinds of artifacts and implausibilities, we aim to better equip people to distinguish AI-generated images from real photographs in the future.
Matching with Nested and Bundled Pandora Boxes
Venue: arXiv cs.DS 2024
Year: 2024

We consider max-weighted matching with costs for learning the weights, modeled as a "Pandora's Box" on each endpoint of an edge. Each vertex has an initially-unknown value for being matched to a neighbor, and an algorithm must pay some cost to observe this value. The goal is to maximize the total matched value minus costs. Our model is inspired by two-sided settings, such as matching employees to employers. Importantly for such settings, we allow for negative values which cause existing approaches to fail. We first prove upper bounds for algorithms in two natural classes. Any algorithm that "bundles" the two Pandora boxes incident to an edge is an $o(1)$-approximation. Likewise, any "vertex-based" algorithm, which uses properties of the separate Pandora's boxes but does not consider the interaction of their value distributions, is an $o(1)$-approximation. Instead, we utilize Pandora's Nested-Box Problem, i.e. multiple stages of inspection. We give a self-contained, fully constructive optimal solution to the nested-boxes problem, which may have structural observations of interest compared to prior work. By interpreting each edge as a nested box, we leverage this solution to obtain a constant-factor approximation algorithm. Finally, we show any "edge-based" algorithm, which considers the interactions of values along an edge but not with the rest of the graph, is also an $o(1)$-approximation.
Batch-Instructed Gradient for Prompt Evolution:Systematic Prompt Optimization for Enhanced Text-to-Image Synthesis
Venue: arXiv cs.AI 2024
Year: 2024

Text-to-image models have shown remarkable progress in generating high-quality images from user-provided prompts. Despite this, the quality of these images varies due to the models' sensitivity to human language nuances. With advancements in large language models, there are new opportunities to enhance prompt design for image generation tasks. Existing research primarily focuses on optimizing prompts for direct interaction, while less attention is given to scenarios involving intermediary agents, like the Stable Diffusion model. This study proposes a Multi-Agent framework to optimize input prompts for text-to-image generation models. Central to this framework is a prompt generation mechanism that refines initial queries using dynamic instructions, which evolve through iterative performance feedback. High-quality prompts are then fed into a state-of-the-art text-to-image model. A professional prompts database serves as a benchmark to guide the instruction modifier towards generating high-caliber prompts. A scoring system evaluates the generated images, and an LLM generates new instructions based on calculated gradients. This iterative process is managed by the Upper Confidence Bound (UCB) algorithm and assessed using the Human Preference Score version 2 (HPS v2). Preliminary ablation studies highlight the effectiveness of various system components and suggest areas for future improvements.