OpenRaiser/Intern-Atlas huggingface dataset:
Swim till You Sink: Computing the Limit of a Game
Venue: arXiv cs.GT 2024
Year: 2024

During 2023, two interesting results were proven about the limit behavior of game dynamics: First, it was shown that there is a game for which no dynamics converges to the Nash equilibria. Second, it was shown that the sink equilibria of a game adequately capture the limit behavior of natural game dynamics. These two results have created a need and opportunity to articulate a principled computational theory of the meaning of the game that is based on game dynamics. Given any game in normal form, and any prior distribution of play, we study the problem of computing the asymptotic behavior of a class of natural dynamics called the noisy replicator dynamics as a limit distribution over the sink equilibria of the game. When the prior distribution has pure strategy support, we prove this distribution can be computed efficiently, in near-linear time to the size of the best-response graph. When the distribution can be sampled -- for example, if it is the uniform distribution over all mixed strategy profiles -- we show through experiments that the limit distribution of reasonably large games can be estimated quite accurately through sampling and simulation.
An Interpretable Deep Learning Approach for Morphological Script Type Analysis
Venue: arXiv cs.CV 2024
Year: 2024

Defining script types and establishing classification criteria for medieval handwriting is a central aspect of palaeographical analysis. However, existing typologies often encounter methodological challenges, such as descriptive limitations and subjective criteria. We propose an interpretable deep learning-based approach to morphological script type analysis, which enables systematic and objective analysis and contributes to bridging the gap between qualitative observations and quantitative measurements. More precisely, we adapt a deep instance segmentation method to learn comparable character prototypes, representative of letter morphology, and provide qualitative and quantitative tools for their comparison and analysis. We demonstrate our approach by applying it to the Textualis Formata script type and its two subtypes formalized by A. Derolez: Northern and Southern Textualis
BUT Systems and Analyses for the ASVspoof 5 Challenge
Venue: arXiv cs.SD 2024
Year: 2024

This paper describes the BUT submitted systems for the ASVspoof 5 challenge, along with analyses. For the conventional deepfake detection task, we use ResNet18 and self-supervised models for the closed and open conditions, respectively. In addition, we analyze and visualize different combinations of speaker information and spoofing information as label schemes for training. For spoofing-robust automatic speaker verification (SASV), we introduce effective priors and propose using logistic regression to jointly train affine transformations of the countermeasure scores and the automatic speaker verification scores in such a way that the SASV LLR is optimized.
Tight entropy bound based on p-quasinorms
Venue: arXiv cs.IT 2024
Year: 2024

In the present paper we prove a family of tight upper and lower bounds for the Shannon entropy and von Neumann entropy based on the p-norms. This allows us to have an entropy estimate, a criterion for the finiteness of it and a bound on the difference of entropy, additionally, we did some numerical tests that show the efficiency of our approximations.
Range-based Multi-Robot Integrity Monitoring Against Cyberattacks and Faults: An Anchor-Free Approach
Venue: arXiv cs.RO 2024
Year: 2024

Coordination of multi-robot systems (MRSs) relies on efficient sensing and reliable communication among the robots. However, the sensors and communication channels of these robots are often vulnerable to cyberattacks and faults, which can disrupt their individual behavior and the overall objective of the MRS. In this work, we present a multi-robot integrity monitoring framework that utilizes inter-robot range measurements to (i) detect the presence of cyberattacks or faults affecting the MRS, (ii) identify the affected robot(s), and (iii) reconstruct the resulting localization error of these robot(s). The proposed iterative algorithm leverages sequential convex programming and alternating direction of multipliers method to enable real-time and distributed implementation. Our approach is validated using numerical simulations and demonstrated using PX4-SiTL in Gazebo on an MRS, where certain agents deviate from their desired position due to a GNSS spoofing attack. Furthermore, we demonstrate the scalability and interoperability of our algorithm through mixed-reality experiments by forming a heterogeneous MRS comprising real Crazyflie UAVs and virtual PX4-SiTL UAVs working in tandem.
Multi-User SR-LDPC Codes
Venue: arXiv cs.IT 2024
Year: 2024

This article introduces a novel non-orthogonal multiple access (NOMA) scheme for coordinated uplink channels. The scheme builds on the recently proposed sparse-regression low-density parity-check (SR-LDPC) code, and extends the underlying notions to scenarios with many concurrent users. The resulting scheme, called Multi-User SR-LDPC (MU-SR-LDPC) coding, consists of each user transmitting its own SR-LDPC codeword using a unique sensing matrix in conjunction with a characteristic outer LDPC code. To recover the sent information, the decoder jointly processes the received signals using a low-complexity and highly-parallelizable AMP-BP algorithm. At finite blocklengths (FBL), MU-SR-LDPC codes are shown to achieve a target BER at a higher spectral efficiency than baseline orthogonal multiple access (OMA) and non-orthogonal multiple access (NOMA) schemes with similar computational complexity. Furthermore, MU-SR-LDPC codes are shown to match the performance of maximum a posteriori (MAP) decoding in certain regimes. For certain blocklengths and a sufficiently high number of users, MU-SR-LDPC codes may achieve a higher spectral efficiency than the approximate FBL capacity of the effective single-user Gaussian channel seen by each user in a comparable OMA scheme. Results are supported by numerical simulations.
A Full DAG Score-Based Algorithm for Learning Causal Bayesian Networks with Latent Confounders
Venue: arXiv cs.LG 2024
Year: 2024

Causal Bayesian networks (CBN) are popular graphical probabilistic models that encode causal relations among variables. Learning their graphical structure from observational data has received a lot of attention in the literature. When there exists no latent (unobserved) confounder, i.e., no unobserved direct common cause of some observed variables, learning algorithms can be divided essentially into two classes: constraint-based and score-based approaches. The latter are often thought to be more robust than the former and to produce better results. However, to the best of our knowledge, when variables are discrete, no score-based algorithm is capable of dealing with latent confounders. This paper introduces the first fully score-based structure learning algorithm searching the space of DAGs (directed acyclic graphs) that is capable of identifying the presence of some latent confounders. It is justified mathematically and experiments highlight its effectiveness.
Optimization of Multi-Agent Flying Sidekick Traveling Salesman Problem over Road Networks
Venue: arXiv cs.RO 2024
Year: 2024

The mixed truck-drone delivery systems have attracted increasing attention for last-mile logistics, but real-world complexities demand a shift from single-agent, fully connected graph models to multi-agent systems operating on actual road networks. We introduce the multi-agent flying sidekick traveling salesman problem (MA-FSTSP) on road networks, extending the single truck-drone model to multiple trucks, each carrying multiple drones while considering full road networks for truck restrictions and flexible drone routes. We propose a mixed-integer linear programming model and an efficient three-phase heuristic algorithm for this NP-hard problem. Our approach decomposes MA-FSTSP into manageable subproblems of one truck with multiple drones. Then, it computes the routes for trucks without drones in subproblems, which are used in the final phase as heuristics to help optimize drone and truck routes simultaneously. Extensive numerical experiments on Manhattan and Boston road networks demonstrate our algorithm's superior effectiveness and efficiency, significantly outperforming both column generation and variable neighborhood search baselines in solution quality and computation time. Notably, our approach scales to more than 300 customers within a 5-minute time limit, showcasing its potential for large-scale, real-world logistics applications.
Active Learning of Molecular Data for Task-Specific Objectives
Venue: arXiv cs.LG 2024
Year: 2024

Active learning (AL) has shown promise for being a particularly data-efficient machine learning approach. Yet, its performance depends on the application and it is not clear when AL practitioners can expect computational savings. Here, we carry out a systematic AL performance assessment for three diverse molecular datasets and two common scientific tasks: compiling compact, informative datasets and targeted molecular searches. We implemented AL with Gaussian processes (GP) and used the many-body tensor as molecular representation. For the first task, we tested different data acquisition strategies, batch sizes and GP noise settings. AL was insensitive to the acquisition batch size and we observed the best AL performance for the acquisition strategy that combines uncertainty reduction with clustering to promote diversity. However, for optimal GP noise settings, AL did not outperform randomized selection of data points. Conversely, for targeted searches, AL outperformed random sampling and achieved data savings up to 64%. Our analysis provides insight into this task-specific performance difference in terms of target distributions and data collection strategies. We established that the performance of AL depends on the relative distribution of the target molecules in comparison to the total dataset distribution, with the largest computational savings achieved when their overlap is minimal.
Proposal of an Electronic Auditing System Applied to the Brazilian Electronic Voting Machine
Venue: arXiv cs.CR 2024
Year: 2024

A new system, called SELA -- Auditing Electronic System, has been developed to be applied to the Brazilian Electronic Voting Machine. The SELA was designed to use open hardware and software, making it widely known by society. The security of the auditing process is guaranteed by the application of a Fingerprint Algorithm, a Hash Function. This system is robust and requires minimal modifications to the Electronic Voting Machine. In this paper, SELA is described, and its use during the election process is analyzed. A comparison between SELA and the use of thermal printers as a secondary voting record system is also presented. The authors recommend a pilot implementation of SELA for the 2002 Brazilian Elections.
Newton-Raphson Flow for Aggressive Quadrotor Tracking Control
Venue: arXiv cs.RO 2024
Year: 2024

We apply the Newton-Raphson flow tracking controller to aggressive quadrotor flight and demonstrate that it achieves good tracking performance over a suite of benchmark trajectories, beating the native trajectory tracking controller in the popular PX4 Autopilot. The Newton-Raphson flow tracking controller is a recently proposed integrator-type controller that aims to drive to zero the error between a future predicted system output and the reference trajectory. This controller is computationally lightweight, requiring only an imprecise predictor, and achieves guaranteed asymptotic error bounds under certain conditions. We show that these theoretical advantages are realizable on a quadrotor hardware platform. Our experiments are conducted on a Holybrox x500v2 quadrotor using a Pixhawk 6x flight controller and a Rasbperry Pi 4 companion computer which receives location information from an OptiTrack motion capture system and sends input commands through the ROS2 API for the PX4 software stack.
Assisting Novice Developers Learning in Flutter Through Cognitive-Driven Development
Venue: arXiv cs.SE 2024
Year: 2024

Cognitive-Driven Development (CDD) is a coding design technique that helps developers focus on designing code within cognitive limits. The imposed limit tends to enhance code readability and maintainability. While early works on CDD focused mostly on Java, its applicability extends beyond specific programming languages. In this study, we explored the use of CDD in two new dimensions: focusing on Flutter programming and targeting novice developers unfamiliar with both Flutter and CDD. Our goal was to understand to what extent CDD helps novice developers learn a new programming technology. We conducted an in-person Flutter training camp with 24 participants. After receiving CDD training, six remaining students were tasked with developing a software management application guided by CDD practices. Our findings indicate that CDD helped participants keep code complexity low, measured using Intrinsic Complexity Points (ICP), a CDD metric. Notably, stricter ICP limits led to a 20\% reduction in code size, improving code quality and readability. This report could be valuable for professors and instructors seeking effective methodologies for teaching design practices that reduce code and cognitive complexity.
Revisiting Min-Max Optimization Problem in Adversarial Training
Venue: arXiv cs.CV 2024
Year: 2024

The rise of computer vision applications in the real world puts the security of the deep neural networks at risk. Recent works demonstrate that convolutional neural networks are susceptible to adversarial examples - where the input images look similar to the natural images but are classified incorrectly by the model. To provide a rebuttal to this problem, we propose a new method to build robust deep neural networks against adversarial attacks by reformulating the saddle point optimization problem in \cite{madry2017towards}. Our proposed method offers significant resistance and a concrete security guarantee against multiple adversaries. The goal of this paper is to act as a stepping stone for a new variation of deep learning models which would lead towards fully robust deep learning models.
Approximately covering vertices by order-$5$ or longer paths
Venue: arXiv cs.DS 2024
Year: 2024

This paper studies $MPC^{5+}_v$, which is to cover as many vertices as possible in a given graph $G=(V,E)$ by vertex-disjoint $5^+$-paths (i.e., paths each with at least five vertices). $MPC^{5+}_v$ is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of $\frac {19}7\approx 2.714$ and runs in $O(|V|^6)$ time. In this paper, we present a new approximation algorithm for $MPC^{5+}_v$ which achieves a ratio of $2.511$ and runs in $O(|V|^{2.5} |E|^2)$ time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion.
Irregularity Inspection using Neural Radiance Field
Venue: arXiv cs.CV 2024
Year: 2024

With the increasing growth of industrialization, more and more industries are relying on machine automation for production. However, defect detection in large-scale production machinery is becoming increasingly important. Due to their large size and height, it is often challenging for professionals to conduct defect inspections on such large machinery. For example, the inspection of aging and misalignment of components on tall machinery like towers requires companies to assign dedicated personnel. Employees need to climb the towers and either visually inspect or take photos to detect safety hazards in these large machines. Direct visual inspection is limited by its low level of automation, lack of precision, and safety concerns associated with personnel climbing the towers. Therefore, in this paper, we propose a system based on neural network modeling (NeRF) of 3D twin models. By comparing two digital models, this system enables defect detection at the 3D interface of an object.
Koopman AutoEncoder via Singular Value Decomposition for Data-Driven Long-Term Prediction
Venue: arXiv cs.LG 2024
Year: 2024

The Koopman autoencoder, a data-driven technique, has gained traction for modeling nonlinear dynamics using deep learning methods in recent years. Given the linear characteristics inherent to the Koopman operator, controlling its eigenvalues offers an opportunity to enhance long-term prediction performance, a critical task for forecasting future trends in time-series datasets with long-term behaviors. However, controlling eigenvalues is challenging due to high computational complexity and difficulties in managing them during the training process. To tackle this issue, we propose leveraging the singular value decomposition (SVD) of the Koopman matrix to adjust the singular values for better long-term prediction. Experimental results demonstrate that, during training, the loss term for singular values effectively brings the eigenvalues close to the unit circle, and the proposed approach outperforms existing baseline methods for long-term prediction tasks.
TWLV-I: Analysis and Insights from Holistic Evaluation on Video Foundation Models
Venue: arXiv cs.CV 2024
Year: 2024

In this work, we discuss evaluating video foundation models in a fair and robust manner. Unlike language or image foundation models, many video foundation models are evaluated with differing parameters (such as sampling rate, number of frames, pretraining steps, etc.), making fair and robust comparisons challenging. Therefore, we present a carefully designed evaluation framework for measuring two core capabilities of video comprehension: appearance and motion understanding. Our findings reveal that existing video foundation models, whether text-supervised like UMT or InternVideo2, or self-supervised like V-JEPA, exhibit limitations in at least one of these capabilities. As an alternative, we introduce TWLV-I, a new video foundation model that constructs robust visual representations for both motion- and appearance-based videos. Based on the average top-1 accuracy of linear probing on five action recognition benchmarks, pretrained only on publicly accessible datasets, our model shows a 4.6%p improvement compared to V-JEPA (ViT-L) and a 7.7%p improvement compared to UMT (ViT-L). Even when compared to much larger models, our model demonstrates a 7.2%p improvement compared to DFN (ViT-H), a 2.7%p improvement compared to V-JEPA (ViT-H) and a 2.8%p improvement compared to InternVideo2 (ViT-g). We provide embedding vectors obtained by TWLV-I from videos of several commonly used video benchmarks, along with evaluation source code that can directly utilize these embeddings. The code is available at https://github.com/twelvelabs-io/video-embeddings-evaluation-framework.
HITS: High-coverage LLM-based Unit Test Generation via Method Slicing
Venue: arXiv cs.SE 2024
Year: 2024

Large language models (LLMs) have behaved well in generating unit tests for Java projects. However, the performance for covering the complex focal methods within the projects is poor. Complex methods comprise many conditions and loops, requiring the test cases to be various enough to cover all lines and branches. However, existing test generation methods with LLMs provide the whole method-to-test to the LLM without assistance on input analysis. The LLM has difficulty inferring the test inputs to cover all conditions, resulting in missing lines and branches. To tackle the problem, we propose decomposing the focal methods into slices and asking the LLM to generate test cases slice by slice. Our method simplifies the analysis scope, making it easier for the LLM to cover more lines and branches in each slice. We build a dataset comprising complex focal methods collected from the projects used by existing state-of-the-art approaches. Our experiment results show that our method significantly outperforms current test case generation methods with LLMs and the typical SBST method Evosuite regarding both line and branch coverage scores.
BURExtract-Llama: An LLM for Clinical Concept Extraction in Breast Ultrasound Reports
Venue: arXiv cs.CL 2024
Year: 2024

Breast ultrasound is essential for detecting and diagnosing abnormalities, with radiology reports summarizing key findings like lesion characteristics and malignancy assessments. Extracting this critical information is challenging due to the unstructured nature of these reports, with varied linguistic styles and inconsistent formatting. While proprietary LLMs like GPT-4 are effective, they are costly and raise privacy concerns when handling protected health information. This study presents a pipeline for developing an in-house LLM to extract clinical information from radiology reports. We first use GPT-4 to create a small labeled dataset, then fine-tune a Llama3-8B model on it. Evaluated on clinician-annotated reports, our model achieves an average F1 score of 84.6%, which is on par with GPT-4. Our findings demonstrate the feasibility of developing an in-house LLM that not only matches GPT-4's performance but also offers cost reductions and enhanced data privacy.
Technical Report: Coopetition in Heterogeneous Cross-Silo Federated Learning
Venue: arXiv cs.GT 2024
Year: 2024

In cross-silo federated learning (FL), companies collaboratively train a shared global model without sharing heterogeneous data. Prior related work focused on algorithm development to tackle data heterogeneity. However, the dual problem of coopetition, i.e., FL collaboration and market competition, remains under-explored. This paper studies the FL coopetition using a dynamic two-period game model. In period 1, an incumbent company trains a local model and provides model-based services at a chosen price to users. In period 2, an entrant company enters, and both companies decide whether to engage in FL collaboration and then compete in selling model-based services at different prices to users. Analyzing the two-period game is challenging due to data heterogeneity, and that the incumbent's period one pricing has a temporal impact on coopetition in period 2, resulting in a non-concave problem. To address this issue, we decompose the problem into several concave sub-problems and develop an algorithm that achieves a global optimum. Numerical results on three public datasets show two interesting insights. First, FL training brings model performance gain as well as competition loss, and collaboration occurs only when the performance gain outweighs the loss. Second, data heterogeneity can incentivize the incumbent to limit market penetration in period 1 and promote price competition in period 2.
One-step Structure Prediction and Screening for Protein-Ligand Complexes using Multi-Task Geometric Deep Learning
Venue: arXiv cs.AI 2024
Year: 2024

Understanding the structure of the protein-ligand complex is crucial to drug development. Existing virtual structure measurement and screening methods are dominated by docking and its derived methods combined with deep learning. However, the sampling and scoring methodology have largely restricted the accuracy and efficiency. Here, we show that these two fundamental tasks can be accurately tackled with a single model, namely LigPose, based on multi-task geometric deep learning. By representing the ligand and the protein pair as a graph, LigPose directly optimizes the three-dimensional structure of the complex, with the learning of binding strength and atomic interactions as auxiliary tasks, enabling its one-step prediction ability without docking tools. Extensive experiments show LigPose achieved state-of-the-art performance on major tasks in drug research. Its considerable improvements indicate a promising paradigm of AI-based pipeline for drug development.