OpenRaiser/Intern-Atlas huggingface dataset:
Optimizing Near Field Computation in the MLFMA Algorithm with Data Redundancy and Performance Modeling on a Single GPU
Venue: arXiv cs.DC 2024
Year: 2024

The Multilevel Fast Multipole Algorithm (MLFMA) has known applications in scientific modeling in the fields of telecommunications, physics, mechanics, and chemistry. Accelerating calculation of far-field using GPUs and GPU clusters for large-scale problems has been studied for more than a decade. The acceleration of the Near Field Computation (P2P operator) however was less of a concern because it does not face the challenges of distributed processing which does far field. This article proposes a modification of the P2P algorithm and uses performance models to determine its optimality criteria. By modeling the speedup, we found that making threads independence by creating redundancy in the data makes the algorithm for lower dense (higher frequency) problems nearly 13 times faster than non-redundant mode.
Towards Provable Log Density Policy Gradient
Venue: arXiv cs.LG 2024
Year: 2024

Policy gradient methods are a vital ingredient behind the success of modern reinforcement learning. Modern policy gradient methods, although successful, introduce a residual error in gradient estimation. In this work, we argue that this residual term is significant and correcting for it could potentially improve sample-complexity of reinforcement learning methods. To that end, we propose log density gradient to estimate the policy gradient, which corrects for this residual error term. Log density gradient method computes policy gradient by utilising the state-action discounted distributional formulation. We first present the equations needed to exactly find the log density gradient for a tabular Markov Decision Processes (MDPs). For more complex environments, we propose a temporal difference (TD) method that approximates log density gradient by utilizing backward on-policy samples. Since backward sampling from a Markov chain is highly restrictive we also propose a min-max optimization that can approximate log density gradient using just on-policy samples. We also prove uniqueness, and convergence under linear function approximation, for this min-max optimization. Finally, we show that the sample complexity of our min-max optimization to be of the order of $m^{-1/2}$, where $m$ is the number of on-policy samples. We also demonstrate a proof-of-concept for our log density gradient method on gridworld environment, and observe that our method is able to improve upon the classical policy gradient method by a clear margin, thus indicating a promising novel direction to develop reinforcement learning algorithms that require fewer samples.
Recent Advances, Applications, and Open Challenges in Machine Learning for Health: Reflections from Research Roundtables at ML4H 2023 Symposium
Venue: arXiv cs.LG 2024
Year: 2024

The third ML4H symposium was held in person on December 10, 2023, in New Orleans, Louisiana, USA. The symposium included research roundtable sessions to foster discussions between participants and senior researchers on timely and relevant topics for the \ac{ML4H} community. Encouraged by the successful virtual roundtables in the previous year, we organized eleven in-person roundtables and four virtual roundtables at ML4H 2022. The organization of the research roundtables at the conference involved 17 Senior Chairs and 19 Junior Chairs across 11 tables. Each roundtable session included invited senior chairs (with substantial experience in the field), junior chairs (responsible for facilitating the discussion), and attendees from diverse backgrounds with interest in the session's topic. Herein we detail the organization process and compile takeaways from these roundtable discussions, including recent advances, applications, and open challenges for each topic. We conclude with a summary and lessons learned across all roundtables. This document serves as a comprehensive review paper, summarizing the recent advancements in machine learning for healthcare as contributed by foremost researchers in the field.
Relational to RDF Data Migration by Query Co-Evaluation
Venue: arXiv cs.DB 2024
Year: 2024

In this paper we define a new algorithm to convert an input relational database to an output set of RDF triples. The algorithm can be used to e.g. load CSV data into a financial OWL ontology such as FIBO. The algorithm takes as input a set of relational conjunctive (select-from-where) queries, one for each input table, from the three column (subject, predicate, object) output RDF schema to the input table's relational schema. The algorithm's output is the only set of RDF triples for which a unique round-trip of the input data under the relational queries exists. The output may contain blank nodes, is unique up to unique isomorphism, and can be obtained using elementary formal methods (equational theorem proving and term model construction specifically). We also describe how (generalized) homomorphisms between graphs can be used to write such relational conjunctive (select-from-where) queries, which, due to the lack of structure in the three-column RDF schema, tend to be large in practice. We demonstrate examples of both the algorithm and mapping language on the FIBO financial ontology.
AIO2: Online Correction of Object Labels for Deep Learning with Incomplete Annotation in Remote Sensing Image Segmentation
Venue: arXiv cs.CV 2024
Year: 2024

While the volume of remote sensing data is increasing daily, deep learning in Earth Observation faces lack of accurate annotations for supervised optimization. Crowdsourcing projects such as OpenStreetMap distribute the annotation load to their community. However, such annotation inevitably generates noise due to insufficient control of the label quality, lack of annotators, frequent changes of the Earth's surface as a result of natural disasters and urban development, among many other factors. We present Adaptively trIggered Online Object-wise correction (AIO2) to address annotation noise induced by incomplete label sets. AIO2 features an Adaptive Correction Trigger (ACT) module that avoids label correction when the model training under- or overfits, and an Online Object-wise Correction (O2C) methodology that employs spatial information for automated label modification. AIO2 utilizes a mean teacher model to enhance training robustness with noisy labels to both stabilize the training accuracy curve for fitting in ACT and provide pseudo labels for correction in O2C. Moreover, O2C is implemented online without the need to store updated labels every training epoch. We validate our approach on two building footprint segmentation datasets with different spatial resolutions. Experimental results with varying degrees of building label noise demonstrate the robustness of AIO2. Source code will be available at https://github.com/zhu-xlab/AIO2.git.
Neural Network Assisted Lifting Steps For Improved Fully Scalable Lossy Image Compression in JPEG 2000
Venue: arXiv cs.CV 2024
Year: 2024

This work proposes to augment the lifting steps of the conventional wavelet transform with additional neural network assisted lifting steps. These additional steps reduce residual redundancy (notably aliasing information) amongst the wavelet subbands, and also improve the visual quality of reconstructed images at reduced resolutions. The proposed approach involves two steps, a high-to-low step followed by a low-to-high step. The high-to-low step suppresses aliasing in the low-pass band by using the detail bands at the same resolution, while the low-to-high step aims to further remove redundancy from detail bands, so as to achieve higher energy compaction. The proposed two lifting steps are trained in an end-to-end fashion; we employ a backward annealing approach to overcome the non-differentiability of the quantization and cost functions during back-propagation. Importantly, the networks employed in this paper are compact and with limited non-linearities, allowing a fully scalable system; one pair of trained network parameters are applied for all levels of decomposition and for all bit-rates of interest. By employing the proposed approach within the JPEG 2000 image coding standard, our method can achieve up to 17.4% average BD bit-rate saving over a wide range of bit-rates, while retaining quality and resolution scalability features of JPEG 2000.
Atropos-k is PSPACE-complete
Venue: arXiv cs.CC 2024
Year: 2024

Burke and Teng introduced a two-player combinatorial game Atropos based on Sperner's lemma, and showed that deciding whether one has a winning strategy for Atropos is PSPACE-complete. In the original Atropos game, the players must color a node adjacent to the last colored node. Burke and Teng also mentioned a variant Atropos-k in which each move is at most of distance k of the previous move, and asked a question on determining the computational complexity of this variant. In this paper, we answer this question by showing that for any fixed integer k (k>=2), Atropos-k is PSPACE-complete by reduction from True Quantified Boolean Formula (TQBF).
Sensor-based Multi-agent Coverage Control with Spatial Separation in Unstructured Environments
Venue: arXiv cs.RO 2024
Year: 2024

Multi-robot systems have increasingly become instrumental in tackling search and coverage problems. However, the challenge of optimizing task efficiency without compromising task success still persists, particularly in expansive, unstructured environments with dense obstacles. This paper presents an innovative, decentralized Voronoi-based approach for search and coverage to reactively navigate these complexities while maintaining safety. This approach leverages the active sensing capabilities of multi-robot systems to supplement GIS (Geographic Information System), offering a more comprehensive and real-time understanding of the environment. Based on point cloud data, which is inherently non-convex and unstructured, this method efficiently generates collision-free Voronoi regions using only local sensing information through spatial decomposition and spherical mirroring techniques. Then, deadlock-aware guided map integrated with a gradient-optimized, centroid Voronoi-based coverage control policy, is constructed to improve efficiency by avoiding exhaustive searches and local sensing pitfalls. The effectiveness of our algorithm has been validated through extensive numerical simulations in high-fidelity environments, demonstrating significant improvements in both task success rate, coverage ratio, and task execution time compared with others.
Towards Self-Contained Answers: Entity-Based Answer Rewriting in Conversational Search
Venue: arXiv cs.IR 2024
Year: 2024

Conversational information-seeking (CIS) is an emerging paradigm for knowledge acquisition and exploratory search. Traditional web search interfaces enable easy exploration of entities, but this is limited in conversational settings due to the limited-bandwidth interface. This paper explore ways to rewrite answers in CIS, so that users can understand them without having to resort to external services or sources. Specifically, we focus on salient entities -- entities that are central to understanding the answer. As our first contribution, we create a dataset of conversations annotated with entities for saliency. Our analysis of the collected data reveals that the majority of answers contain salient entities. As our second contribution, we propose two answer rewriting strategies aimed at improving the overall user experience in CIS. One approach expands answers with inline definitions of salient entities, making the answer self-contained. The other approach complements answers with follow-up questions, offering users the possibility to learn more about specific entities. Results of a crowdsourcing-based study indicate that rewritten answers are clearly preferred over the original ones. We also find that inline definitions tend to be favored over follow-up questions, but this choice is highly subjective, thereby providing a promising future direction for personalization.
NeuSpeech: Decode Neural signal as Speech
Venue: arXiv cs.CL 2024
Year: 2024

Decoding language from brain dynamics is an important open direction in the realm of brain-computer interface (BCI), especially considering the rapid growth of large language models. Compared to invasive-based signals which require electrode implantation surgery, non-invasive neural signals (e.g. EEG, MEG) have attracted increasing attention considering their safety and generality. However, the exploration is not adequate in three aspects: 1) previous methods mainly focus on EEG but none of the previous works address this problem on MEG with better signal quality; 2) prior works have predominantly used $``teacher-forcing"$ during generative decoding, which is impractical; 3) prior works are mostly $``BART-based"$ not fully auto-regressive, which performs better in other sequence tasks. In this paper, we explore the brain-to-text translation of MEG signals in a speech-decoding formation. Here we are the first to investigate a cross-attention-based ``whisper" model for generating text directly from MEG signals without teacher forcing. Our model achieves impressive BLEU-1 scores of 60.30 and 52.89 without pretraining $\&$ teacher-forcing on two major datasets ($\textit{GWilliams}$ and $\textit{Schoffelen}$). This paper conducts a comprehensive review to understand how speech decoding formation performs on the neural decoding tasks, including pretraining initialization, training $\&$ evaluation set splitting, augmentation, and scaling law. Code is available at https://github.com/NeuSpeech/NeuSpeech1$.
AI Language Models Could Both Help and Harm Equity in Marine Policymaking: The Case Study of the BBNJ Question-Answering Bot
Venue: arXiv cs.CY 2024
Year: 2024

AI Large Language Models (LLMs) like ChatGPT are set to reshape some aspects of policymaking processes. Policy practitioners are already using ChatGPT for help with a variety of tasks: from drafting statements, submissions, and presentations, to conducting background research. We are cautiously hopeful that LLMs could be used to promote a marginally more balanced footing among decision makers in policy negotiations by assisting with certain tedious work, particularly benefiting developing countries who face capacity constraints that put them at a disadvantage in negotiations. However, the risks are particularly concerning for environmental and marine policy uses, due to the urgency of crises like climate change, high uncertainty, and trans-boundary impact. To explore the realistic potentials, limitations, and equity risks for LLMs in marine policymaking, we present a case study of an AI chatbot for the recently adopted Biodiversity Beyond National Jurisdiction Agreement (BBNJ), and critique its answers to key policy questions. Our case study demonstrates the dangers of LLMs in marine policymaking via their potential bias towards generating text that favors the perspectives of mainly Western economic centers of power, while neglecting developing countries' viewpoints. We describe several ways these biases can enter the system, including: (1) biases in the underlying foundational language models; (2) biases arising from the chatbot's connection to UN negotiation documents, and (3) biases arising from the application design. We urge caution in the use of generative AI in ocean policy processes and call for more research on its equity and fairness implications. Our work also underscores the need for developing countries' policymakers to develop the technical capacity to engage with AI on their own terms.
CatCode: A Comprehensive Evaluation Framework for LLMs On the Mixture of Code and Text
Venue: arXiv cs.AI 2024
Year: 2024

Large language models (LLMs) such as ChatGPT are increasingly proficient in understanding and generating a mixture of code and text. Evaluation based on such $\textit{mixture}$ can lead to a more comprehensive understanding of the models' abilities in solving coding problems. However, in this context, current evaluation methods are either limited in task coverage or lack standardization. To address this issue, we propose using category theory as a framework for evaluation. Specifically, morphisms within a code category can represent code debugging and transformation, functors between two categories represent code translation, and functors between a code category and a natural language category represent code generation, explanation, and reproduction. We present an automatic evaluation framework called $\textbf{CatCode}$ ($\textbf{Cat}$egory $\textbf{Code}$) that can comprehensively assess the coding abilities of LLMs, including ChatGPT, Text-Davinci, and CodeGeeX.
K-stars LDP: A Novel Framework for (p, q)-clique Enumeration under Local Differential Privacy
Venue: arXiv cs.CR 2024
Year: 2024

(p,q)-clique enumeration on a bipartite graph is critical for calculating clustering coefficient and detecting densest subgraph. It is necessary to carry out subgraph enumeration while protecting users' privacy from any potential attacker as the count of subgraph may contain sensitive information. Most recent studies focus on the privacy protection algorithms based on edge LDP (Local Differential Privacy). However, these algorithms suffer a large estimation error due to the great amount of required noise. In this paper, we propose a novel idea of k-stars LDP and a novel k-stars LDP algorithm for (p, q)-clique enumeration with a small estimation error, where a k-stars is a star-shaped graph with k nodes connecting to one node. The effectiveness of edge LDP relies on its capacity to obfuscate the existence of an edge between the user and his one-hop neighbors. This is based on the premise that a user should be aware of the existence of his one-hop neighbors. Similarly, we can apply this premise to k-stars as well, where an edge is a specific genre of 1-stars. Based on this fact, we first propose the k-stars neighboring list to enable our algorithm to obfuscate the existence of k-stars with Warner' s RR. Then, we propose the absolute value correction technique and the k-stars sampling technique to further reduce the estimation error. Finally, with the two-round user-collector interaction mechanism, we propose our k-stars LDP algorithm to count the number of (p, q)-clique while successfully protecting users' privacy. Both the theoretical analysis and experiments have showed the superiority of our algorithm over the algorithms based on edge LDP.
DECOR: Enhancing Logic Locking Against Machine Learning-Based Attacks
Venue: arXiv cs.CR 2024
Year: 2024

Logic locking (LL) has gained attention as a promising intellectual property protection measure for integrated circuits. However, recent attacks, facilitated by machine learning (ML), have shown the potential to predict the correct key in multiple LL schemes by exploiting the correlation of the correct key value with the circuit structure. This paper presents a generic LL enhancement method based on a randomized algorithm that can significantly decrease the correlation between locked circuit netlist and correct key values in an LL scheme. Numerical results show that the proposed method can efficiently degrade the accuracy of state-of-the-art ML-based attacks down to around 50%, resulting in negligible advantage versus random guessing.
Towards Fair and Efficient Learning-based Congestion Control
Venue: arXiv cs.NI 2024
Year: 2024

Recent years have witnessed a plethora of learning-based solutions for congestion control (CC) that demonstrate better performance over traditional TCP schemes. However, they fail to provide consistently good convergence properties, including {\em fairness}, {\em fast convergence} and {\em stability}, due to the mismatch between their objective functions and these properties. Despite being intuitive, integrating these properties into existing learning-based CC is challenging, because: 1) their training environments are designed for the performance optimization of single flow but incapable of cooperative multi-flow optimization, and 2) there is no directly measurable metric to represent these properties into the training objective function. We present Astraea, a new learning-based congestion control that ensures fast convergence to fairness with stability. At the heart of Astraea is a multi-agent deep reinforcement learning framework that explicitly optimizes these convergence properties during the training process by enabling the learning of interactive policy between multiple competing flows, while maintaining high performance. We further build a faithful multi-flow environment that emulates the competing behaviors of concurrent flows, explicitly expressing convergence properties to enable their optimization during training. We have fully implemented Astraea and our comprehensive experiments show that Astraea can quickly converge to fairness point and exhibit better stability than its counterparts. For example, \sys achieves near-optimal bandwidth sharing (i.e., fairness) when multiple flows compete for the same bottleneck, delivers up to 8.4$\times$ faster convergence speed and 2.8$\times$ smaller throughput deviation, while achieving comparable or even better performance over prior solutions.
Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
Venue: arXiv cs.DS 2024
Year: 2024

We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph's vulnerability to vertex removal in terms of connectivity. Vertex integrity is the smallest number $ι$ such that there is a set $S$ of $ι' \le ι$ vertices such that every connected component of $G-S$ contains at most $ι-ι'$ vertices. It is known that the vertex integrity lies between the well-studied parameters vertex cover number and tree-depth. Alon and Yuster [ESA 2007] designed algorithms for graphs with small vertex cover number using fast matrix multiplications. We demonstrate that fast matrix multiplication can also be effectively used when parameterizing by vertex integrity $ι$ by developing efficient algorithms for problems including an $O(ι^{ω-1}n)$-time algorithm for computing the girth of a graph, randomized $O(ι^{ω- 1}n)$-time algorithms for Maximum Matching and for finding any induced four-vertex subgraph except for a clique or an independent set, and an $O(ι^{(ω-1)/2}n^2) \subseteq O(ι^{0.687} n^2)$-time algorithm for All-Pairs Shortest Paths. These algorithms can be faster than previous algorithms parameterized by tree-depth, for which fast matrix multiplication is not known to be effective.
An Improved Traditional Chinese Evaluation Suite for Foundation Model
Venue: arXiv cs.CL 2024
Year: 2024

We present TMMLU+, a new benchmark designed for Traditional Chinese language understanding. TMMLU+ is a multi-choice question-answering dataset with 66 subjects from elementary to professional level. It is six times larger and boasts a more balanced subject distribution than its predecessor, Taiwan Massive Multitask Language Understanding (TMMLU). We also benchmark closed-source models and 26 open-weight Chinese large language models (LLMs) of parameters ranging from 1.8B to 72B on the proposed TMMLU+. Our findings reveal that (1.) Traditional Chinese models still trail behind their Simplified Chinese counterparts, highlighting a need for more focused advancements in LLMs catering to Traditional Chinese. (2.) Current LLMs still fall short of human performance in average scores, indicating a potential need for future research to delve deeper into social science and humanities subjects. (3.) Among all the tokenization compression metrics examined, we identify that only the fertility score uniquely demonstrates strong correlations with our benchmark results. We foresee that TMMLU+ will pinpoint areas for future model improvement, thereby narrowing the gap between machine and human linguistic capabilities and supporting researchers in developing Traditional Chinese LLMs. Our dataset, along with the benchmark source code, is accessible at huggingface.co/datasets/ikala/tmmluplus.