OpenRaiser/Intern-Atlas huggingface dataset:
Random-Order Interval Selection
Venue: arXiv cs.DS 2025
Year: 2025

In the problem of online unweighted interval selection, the objective is to maximize the number of non-conflicting intervals accepted by the algorithm. In the conventional online model of irrevocable decisions, there is an Omega(n) lower bound on the competitive ratio, even for randomized algorithms [Bachmann et al. 2013]. In a line of work that allows for revocable acceptances, [Faigle and Nawijn 1995] gave a greedy 1-competitive (i.e. optimal) algorithm in the real-time model, where intervals arrive in order of non-decreasing starting times. The natural extension of their algorithm in the adversarial (any-order) model is 2k-competitive [Borodin and Karavasilis 2023], when there are at most k different interval lengths, and that is optimal for all deterministic, and memoryless randomized algorithms. We study this problem in the random-order model, where the adversary chooses the instance, but the online sequence is a uniformly random permutation of the items. We consider the same algorithm that is optimal in the cases of the real-time and any-order models, and give an upper bound of 2.5 on the competitive ratio under random-order arrivals. We also initiate a study of utilizing random-order arrivals to extract random bits with the goal of derandomizing algorithms. Besides producing simple algorithms, simulating random bits through random arrivals enhances our understanding of the comparative strength of the two models. Our main extraction process returns a bit with a worst-case bias of 2 - sqrt(2) = 0.585 and operates under the mild assumption that there exist at least two distinct items in the input. We motivate the applicability of this process by using it to simulate a number of barely random algorithms for interval selection (single-length arbitrary weights, and C-benevolent instances), the general knapsack problem, string guessing, minimum makespan, and job throughput scheduling.
Learning Ordinality in Semantic Segmentation
Venue: arXiv cs.CV 2025
Year: 2025

Semantic segmentation consists of predicting a semantic label for each image pixel. While existing deep learning approaches achieve high accuracy, they often overlook the ordinal relationships between classes, which can provide critical domain knowledge (e.g., the pupil lies within the iris, and lane markings are part of the road). This paper introduces novel methods for spatial ordinal segmentation that explicitly incorporate these inter-class dependencies. By treating each pixel as part of a structured image space rather than as an independent observation, we propose two regularization terms and a new metric to enforce ordinal consistency between neighboring pixels. Two loss regularization terms and one metric are proposed for structural ordinal segmentation, which penalizes predictions of non-ordinal adjacent classes. Five biomedical datasets and multiple configurations of autonomous driving datasets demonstrate the efficacy of the proposed methods. Our approach achieves improvements in ordinal metrics and enhances generalization, with up to a 15.7% relative increase in the Dice coefficient. Importantly, these benefits come without additional inference time costs. This work highlights the significance of spatial ordinal relationships in semantic segmentation and provides a foundation for further exploration in structured image representations.
AI-Assisted Generation of Difficult Math Questions
Venue: arXiv cs.AI 2025
Year: 2025

Current LLM training positions mathematical reasoning as a core capability. With publicly available sources fully tapped, there is unmet demand for diverse and challenging math questions. Relying solely on human experts is both time-consuming and costly, while LLM-generated questions often lack the requisite diversity and difficulty. We present a design framework that combines the strengths of LLMs with a human-in-the-loop approach to generate a diverse array of challenging math questions. We leverage LLM metacognition skills [Didolkar et al., 2024] of a strong LLM to extract core "skills" from existing math datasets. These skills serve as the basis for generating novel and difficult questions by prompting the LLM with random pairs of core skills. The use of two different skills within each question makes finding such questions an "out of distribution" task for both LLMs and humans. Our pipeline employs LLMs to iteratively generate and refine questions and solutions through multiturn prompting. Human annotators then verify and further refine the questions, with their efficiency enhanced via further LLM interactions. Applying this pipeline on skills extracted from the MATH dataset [Hendrycks et al., 2021] resulted in MATH$^2$ - a dataset of higher-quality math questions, as evidenced by: (a) Lower performance of all models on MATH$^2$ than on MATH (b) Higher performance on MATH when using MATH$^2$ questions as in-context examples. Although focused on mathematics, our methodology seems applicable to other domains requiring structured reasoning, and potentially as a component of scalable oversight. Also of interest is a striking relationship observed between models' performance on the new dataset: the success rate on MATH$^2$ is the square on MATH, suggesting that successfully solving the question in MATH$^2$ requires a nontrivial combination of two distinct math skills.
Cross-Institutional Dental EHR Entity Extraction via Generative AI and Synthetic Notes
Venue: arXiv cs.CL 2025
Year: 2025

This research addresses the issue of missing structured data in dental records by extracting diagnostic information from unstructured text. The updated periodontology classification system's complexity has increased incomplete or missing structured diagnoses. To tackle this, we use advanced AI and NLP methods, leveraging GPT-4 to generate synthetic notes for fine-tuning a RoBERTa model. This significantly enhances the model's ability to understand medical and dental language. We evaluated the model using 120 randomly selected clinical notes from two datasets, demonstrating its improved diagnostic extraction accuracy. The results showed high accuracy in diagnosing periodontal status, stage, and grade, with Site 1 scoring 0.99 and Site 2 scoring 0.98. In the subtype category, Site 2 achieved perfect scores, outperforming Site 1. This method enhances extraction accuracy and broadens its use across dental contexts. The study underscores AI and NLP's transformative impact on healthcare delivery and management. Integrating AI and NLP technologies enhances documentation and simplifies administrative tasks by precisely extracting complex clinical information. This approach effectively addresses challenges in dental diagnostics. Using synthetic training data from LLMs optimizes the training process, improving accuracy and efficiency in identifying periodontal diagnoses from clinical notes. This innovative method holds promise for broader healthcare applications, potentially improving patient care quality.
Private Collaborative Edge Inference via Over-the-Air Computation
Venue: arXiv cs.LG 2025
Year: 2025

We consider collaborative inference at the wireless edge, where each client's model is trained independently on its local dataset. Clients are queried in parallel to make an accurate decision collaboratively. In addition to maximizing the inference accuracy, we also want to ensure the privacy of local models. To this end, we leverage the superposition property of the multiple access channel to implement bandwidth-efficient multi-user inference methods. We propose different methods for ensemble and multi-view classification that exploit over-the-air computation (OAC). We show that these schemes perform better than their orthogonal counterparts with statistically significant differences while using fewer resources and providing privacy guarantees. We also provide experimental results verifying the benefits of the proposed OAC approach to multi-user inference, and perform an ablation study to demonstrate the effectiveness of our design choices. We share the source code of the framework publicly on Github to facilitate further research and reproducibility.
A Cooperation Control Framework Based on Admittance Control and Time-varying Passive Velocity Field Control for Human-Robot Co-carrying Tasks
Venue: arXiv cs.RO 2025
Year: 2025

Human-robot co-carrying tasks reveal their potential in both industrial and everyday applications by leveraging the strengths of both parties. Effective control of robots in these tasks requires managing the energy level in the closed-loop systems to prevent potential dangers while also minimizing motion errors to complete the shared tasks. The collaborative tasks pose numerous challenges due to varied human intentions in adapting to workspace characteristics, leading to human-robot conflicts. In this paper, we develop a cooperation control framework for human-robot co-carrying tasks constructed by utilizing reference generator and low-level controller to aim to achieve safe interaction and synchronized human-robot movement. Firstly, the human motion predictions are corrected in the event of prediction errors based on the conflicts measured by the interaction forces through admittance control, thereby mitigating conflict levels. Low-level controller using an energy-compensation passive velocity field control approach allows encoding the corrected motion to produce control torques for the robot. In this manner, the closed-loop robotic system is passive when the energy level exceeds the predetermined threshold, and otherwise. Furthermore, the proposed control approach ensures that the system's kinetic energy is compensated within a finite time interval. The passivity, stability, convergence rate of energy, and power flow regulation are analyzed from theoretical viewpoints. Human-in-the-loop experiments involving 18 participants have demonstrated that the proposed method significantly enhances task performance and reduces human workload, as evidenced by both objective metrics and subjective evaluations, with improvements confirmed by statistical tests (p < 0.05) relative to baseline methods.
Regime-Aware Time Weighting for Physics-Informed Neural Networks
Venue: arXiv cs.LG 2025
Year: 2025

We introduce a novel method to handle the time dimension when Physics-Informed Neural Networks (PINNs) are used to solve time-dependent differential equations; our proposal focuses on how time sampling and weighting strategies affect solution quality. While previous methods proposed heuristic time-weighting schemes, our approach is grounded in theoretical insights derived from the Lyapunov exponents, which quantify the sensitivity of solutions to perturbations over time. This principled methodology automatically adjusts weights based on the stability regime of the system -- whether chaotic, periodic, or stable. Numerical experiments on challenging benchmarks, including the chaotic Lorenz system and the Burgers' equation, demonstrate the effectiveness and robustness of the proposed method. Compared to existing techniques, our approach offers improved convergence and accuracy without requiring additional hyperparameter tuning. The findings underline the importance of incorporating causality and dynamical system behavior into PINN training strategies, providing a robust framework for solving time-dependent problems with enhanced reliability.
Need of AI in Modern Education: in the Eyes of Explainable AI (xAI)
Venue: arXiv cs.AI 2025
Year: 2025

Modern Education is not \textit{Modern} without AI. However, AI's complex nature makes understanding and fixing problems challenging. Research worldwide shows that a parent's income greatly influences a child's education. This led us to explore how AI, especially complex models, makes important decisions using Explainable AI tools. Our research uncovered many complexities linked to parental income and offered reasonable explanations for these decisions. However, we also found biases in AI that go against what we want from AI in education: clear transparency and equal access for everyone. These biases can impact families and children's schooling, highlighting the need for better AI solutions that offer fair opportunities to all. This chapter tries to shed light on the complex ways AI operates, especially concerning biases. These are the foundational steps towards better educational policies, which include using AI in ways that are more reliable, accountable, and beneficial for everyone involved.
ReLiK: Retrieve and LinK, Fast and Accurate Entity Linking and Relation Extraction on an Academic Budget
Venue: arXiv cs.CL 2025
Year: 2025

Entity Linking (EL) and Relation Extraction (RE) are fundamental tasks in Natural Language Processing, serving as critical components in a wide range of applications. In this paper, we propose ReLiK, a Retriever-Reader architecture for both EL and RE, where, given an input text, the Retriever module undertakes the identification of candidate entities or relations that could potentially appear within the text. Subsequently, the Reader module is tasked to discern the pertinent retrieved entities or relations and establish their alignment with the corresponding textual spans. Notably, we put forward an innovative input representation that incorporates the candidate entities or relations alongside the text, making it possible to link entities or extract relations in a single forward pass and to fully leverage pre-trained language models contextualization capabilities, in contrast with previous Retriever-Reader-based methods, which require a forward pass for each candidate. Our formulation of EL and RE achieves state-of-the-art performance in both in-domain and out-of-domain benchmarks while using academic budget training and with up to 40x inference speed compared to competitors. Finally, we show how our architecture can be used seamlessly for Information Extraction (cIE), i.e. EL + RE, and setting a new state of the art by employing a shared Reader that simultaneously extracts entities and relations.
Semantical Analysis of Intuitionistic Modal Logics between CK and IK
Venue: arXiv cs.LO 2025
Year: 2025

The intuitionistic modal logics considered between Constructive K (CK) and Intuitionistic K (IK) differ in their treatment of the possibility (diamond) connective. It was recently rediscovered that some logics between CK and IK also disagree on their diamond-free fragments, with only some remaining conservative over the standard axiomatisation of intuitionistic modal logic with necessity (box) alone. We show that relational Kripke semantics for CK can be extended with frame conditions for all axioms in the standard axiomatisation of IK, as well as other axioms previously studied. This allows us to answer open questions about the (non-)conservativity of such logics over intuitionistic modal logic without diamond. Our results are formalised using the Coq Proof Assistant.
MESA: Effective Matching Redundancy Reduction by Semantic Area Segmentation
Venue: arXiv cs.CV 2025
Year: 2025

We propose MESA and DMESA as novel feature matching methods, which utilize Segment Anything Model (SAM) to effectively mitigate matching redundancy. The key insight of our methods is to establish implicit-semantic area matching prior to point matching, based on advanced image understanding of SAM. Then, informative area matches with consistent internal semantic are able to undergo dense feature comparison, facilitating precise inside-area point matching. Specifically, MESA adopts a sparse matching framework and first obtains candidate areas from SAM results through a novel Area Graph (AG). Then, area matching among the candidates is formulated as graph energy minimization and solved by graphical models derived from AG. To address the efficiency issue of MESA, we further propose DMESA as its dense counterpart, applying a dense matching framework. After candidate areas are identified by AG, DMESA establishes area matches through generating dense matching distributions. The distributions are produced from off-the-shelf patch matching utilizing the Gaussian Mixture Model and refined via the Expectation Maximization. With less repetitive computation, DMESA showcases a speed improvement of nearly five times compared to MESA, while maintaining competitive accuracy. Our methods are extensively evaluated on five datasets encompassing indoor and outdoor scenes. The results illustrate consistent performance improvements from our methods for five distinct point matching baselines across all datasets. Furthermore, our methods exhibit promise generalization and improved robustness against image resolution variations. The code is publicly available at https://github.com/Easonyesheng/A2PM-MESA.
Joint Antenna Position and Beamforming Optimization with Self-Interference Mitigation in MA-ISAC System
Venue: arXiv cs.IT 2025
Year: 2025

Movable antennas (MAs) have demonstrated significant potential in enhancing the performance of integrated sensing and communication (ISAC) systems. However, the application in the integrated and cost-effective full-duplex (FD) monostatic systems remains underexplored. To address this research gap, we develop an MA-ISAC model within a monostatic framework, where the self-interference channel is modeled in the near field and characterized by antenna position vectors. This model allows us to investigate the use of MAs with the goal of maximizing the weighted sum of communication capacity and sensing mutual information. The resulting optimization problem is non-convex making it challenging to solve optimally. To overcome this, we employ fractional programming (FP) to propose an alternating optimization (AO) algorithm that jointly optimizes the beamforming and antenna positions for both transceivers. Specifically, closed-form solutions for the transmit and receive beamforming matrices are derived using the Karush-Kuhn-Tucker (KKT) conditions, and a novel coarse-to-fine grained search (CFGS) approach is employed to determine the high-quality sub-optimal antenna positions. Numerical results demonstrate that with strong self-interference cancellation (SIC) capabilities, MAs significantly enhance the overall performance and reliability of the ISAC system when utilizing our proposed algorithm, compared to conventional fixed-position antenna designs.
Convergence Analysis of Natural Gradient Descent for Over-parameterized Physics-Informed Neural Networks
Venue: arXiv cs.LG 2025
Year: 2025

In the context of over-parameterization, there is a line of work demonstrating that randomly initialized (stochastic) gradient descent (GD) converges to a globally optimal solution at a linear convergence rate for the quadratic loss function. However, the learning rate of GD for training two-layer neural networks exhibits poor dependence on the sample size and the Gram matrix, leading to a slow training process. In this paper, we show that for training two-layer $\text{ReLU}^3$ Physics-Informed Neural Networks (PINNs), the learning rate can be improved from $\mathcal{O}(λ_0)$ to $\mathcal{O}(1/\|\bm{H}^{\infty}\|_2)$, implying that GD actually enjoys a faster convergence rate. Despite such improvements, the convergence rate is still tied to the least eigenvalue of the Gram matrix, leading to slow convergence. We then develop the positive definiteness of Gram matrices with general smooth activation functions and provide the convergence analysis of natural gradient descent (NGD) in training two-layer PINNs, demonstrating that the learning rate can be $\mathcal{O}(1)$ and at this rate, the convergence rate is independent of the Gram matrix. In particular, for smooth activation functions, the convergence rate of NGD is quadratic. Numerical experiments are conducted to verify our theoretical results.
Towards Certified Unlearning for Deep Neural Networks
Venue: arXiv cs.LG 2025
Year: 2025

In the field of machine unlearning, certified unlearning has been extensively studied in convex machine learning models due to its high efficiency and strong theoretical guarantees. However, its application to deep neural networks (DNNs), known for their highly nonconvex nature, still poses challenges. To bridge the gap between certified unlearning and DNNs, we propose several simple techniques to extend certified unlearning methods to nonconvex objectives. To reduce the time complexity, we develop an efficient computation method by inverse Hessian approximation without compromising certification guarantees. In addition, we extend our discussion of certification to nonconvergence training and sequential unlearning, considering that real-world users can send unlearning requests at different time points. Extensive experiments on three real-world datasets demonstrate the efficacy of our method and the advantages of certified unlearning in DNNs.
Leveraging Encoder-only Large Language Models for Mobile App Review Feature Extraction
Venue: arXiv cs.CL 2025
Year: 2025

Mobile app review analysis presents unique challenges due to the low quality, subjective bias, and noisy content of user-generated documents. Extracting features from these reviews is essential for tasks such as feature prioritization and sentiment analysis, but it remains a challenging task. Meanwhile, encoder-only models based on the Transformer architecture have shown promising results for classification and information extraction tasks for multiple software engineering processes. This study explores the hypothesis that encoder-only large language models can enhance feature extraction from mobile app reviews. By leveraging crowdsourced annotations from an industrial context, we redefine feature extraction as a supervised token classification task. Our approach includes extending the pre-training of these models with a large corpus of user reviews to improve contextual understanding and employing instance selection techniques to optimize model fine-tuning. Empirical evaluations demonstrate that this method improves the precision and recall of extracted features and enhances performance efficiency. Key contributions include a novel approach to feature extraction, annotated datasets, extended pre-trained models, and an instance selection mechanism for cost-effective fine-tuning. This research provides practical methods and empirical evidence in applying large language models to natural language processing tasks within mobile app reviews, offering improved performance in feature extraction.