OpenRaiser/Intern-Atlas huggingface dataset:
Stronger adversaries grow cheaper forests: online node-weighted Steiner problems
Venue: arXiv cs.DS 2024
Year: 2024

We propose a $O(\log k \log n)$-competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous bound of $O(\log^2 k \log n)$ by Hajiaghayi et al. [2017]. In fact, our result extends to the more general prize-collecting setting, improving over previous works by a poly-logarithmic factor. Our key technical contribution is a randomized online algorithm for set cover and non-metric facility location in a new adversarial model which we call semi-adaptive adversaries. As a by-product of our techniques, we obtain the first deterministic $O(\log |C| \log |F|)$-competitive algorithm for non-metric facility location.
IMAN: An Adaptive Network for Robust NPC Mortality Prediction with Missing Modalities
Venue: arXiv cs.LG 2024
Year: 2024

Accurate prediction of mortality in nasopharyngeal carcinoma (NPC), a complex malignancy particularly challenging in advanced stages, is crucial for optimizing treatment strategies and improving patient outcomes. However, this predictive process is often compromised by the high-dimensional and heterogeneous nature of NPC-related data, coupled with the pervasive issue of incomplete multi-modal data, manifesting as missing radiological images or incomplete diagnostic reports. Traditional machine learning approaches suffer significant performance degradation when faced with such incomplete data, as they fail to effectively handle the high-dimensionality and intricate correlations across modalities. Even advanced multi-modal learning techniques like Transformers struggle to maintain robust performance in the presence of missing modalities, as they lack specialized mechanisms to adaptively integrate and align the diverse data types, while also capturing nuanced patterns and contextual relationships within the complex NPC data. To address these problem, we introduce IMAN: an adaptive network for robust NPC mortality prediction with missing modalities.
Aligning CodeLLMs with Direct Preference Optimization
Venue: arXiv cs.AI 2024
Year: 2024

The last year has witnessed the rapid progress of large language models (LLMs) across diverse domains. Among them, CodeLLMs have garnered particular attention because they can not only assist in completing various programming tasks but also represent the decision-making and logical reasoning capabilities of LLMs. However, current CodeLLMs mainly focus on pre-training and supervised fine-tuning scenarios, leaving the alignment stage, which is important for post-training LLMs, under-explored. This work first identifies that the commonly used PPO algorithm may be suboptimal for the alignment of CodeLLM because the involved reward rules are routinely coarse-grained and potentially flawed. We then advocate addressing this using the DPO algorithm. Based on only preference data pairs, DPO can render the model rank data automatically, giving rise to a fine-grained rewarding pattern more robust than human intervention. We also contribute a pipeline for collecting preference pairs for DPO on CodeLLMs. Studies show that our method significantly improves the performance of existing CodeLLMs on benchmarks such as MBPP and HumanEval.
STTATTS: Unified Speech-To-Text And Text-To-Speech Model
Venue: arXiv cs.CL 2024
Year: 2024

Speech recognition and speech synthesis models are typically trained separately, each with its own set of learning objectives, training data, and model parameters, resulting in two distinct large networks. We propose a parameter-efficient approach to learning ASR and TTS jointly via a multi-task learning objective and shared parameters. Our evaluation demonstrates that the performance of our multi-task model is comparable to that of individually trained models while significantly saving computational and memory costs ($\sim$50\% reduction in the total number of parameters required for the two tasks combined). We experiment with English as a resource-rich language, and Arabic as a relatively low-resource language due to shortage of TTS data. Our models are trained with publicly available data, and both the training code and model checkpoints are openly available for further research.
Approximate EFX and Exact tEFX Allocations for Indivisible Chores: Improved Algorithms
Venue: arXiv cs.GT 2024
Year: 2024

We explore the fair distribution of a set of $m$ indivisible chores among $n$ agents, where each agent's costs are evaluated using a monotone cost function. Our focus lies on two fairness criteria: envy-freeness up to any item (EFX) and a relaxed notion, namely envy-freeness up to the transfer of any item (tEFX). We demonstrate that a 2-approximate EFX allocation exists and is computable in polynomial time for three agents with subadditive cost functions, improving upon the previous $(2 + \sqrt{6})$ approximation for additive cost functions. This result requires extensive case analysis. Christoforidis et al. (IJCAI'24) independently claim the same approximation for additive cost functions; however, we provide a counter-example to their algorithm. We expand the number of agents to any number to get the same approximation guarantee with the assumption of partially identical ordering (IDO) for the cost functions. Additionally, we establish that a tEFX allocation is achievable for three agents if one has an additive 2-ratio bounded cost function, while the others may have general monotone cost functions. This is an improvement from the prior requirement of two agents with additive 2-ratio bounded cost functions. This allocation can also be extended to agent groups with identical valuations. Further, we show various analyses of EFX allocations for chores, such as the relaxations for additive $α$-ratio-bounded cost functions.
Learning dissipative Hamiltonian dynamics with reproducing kernel Hilbert spaces and random Fourier features
Venue: arXiv cs.LG 2024
Year: 2024

This paper presents a new method for learning dissipative Hamiltonian dynamics from a limited and noisy dataset. The method uses the Helmholtz decomposition to learn a vector field as the sum of a symplectic and a dissipative vector field. The two vector fields are learned using two reproducing kernel Hilbert spaces, defined by a symplectic and a curl-free kernel, where the kernels are specialized to enforce odd symmetry. Random Fourier features are used to approximate the kernels to reduce the dimension of the optimization problem. The performance of the method is validated in simulations for two dissipative Hamiltonian systems, and it is shown that the method improves predictive accuracy significantly compared to a method where a Gaussian separable kernel is used.
Recognizing Sumsets is NP-Complete
Venue: arXiv cs.DS 2024
Year: 2024

Sumsets are central objects in additive combinatorics. In 2007, Granville asked whether one can efficiently recognize whether a given set $S$ is a sumset, i.e. whether there is a set $A$ such that $A+A=S$. Granville suggested an algorithm that takes exponential time in the size of the given set, but can we do polynomial or even linear time? This basic computational question is indirectly asking a fundamental structural question: do the special characteristics of sumsets allow them to be efficiently recognizable? In this paper, we answer this question negatively by proving that the problem is NP-complete. Specifically, our results hold for integer sets and over any finite field. Assuming the Exponential Time Hypothesis, our lower bound becomes $2^{Ω(n^{1/4})}$.
Every Component Counts: Rethinking the Measure of Success for Medical Semantic Segmentation in Multi-Instance Segmentation Tasks
Venue: arXiv cs.CV 2024
Year: 2024

We present Connected-Component~(CC)-Metrics, a novel semantic segmentation evaluation protocol, targeted to align existing semantic segmentation metrics to a multi-instance detection scenario in which each connected component matters. We motivate this setup in the common medical scenario of semantic metastases segmentation in a full-body PET/CT. We show how existing semantic segmentation metrics suffer from a bias towards larger connected components contradicting the clinical assessment of scans in which tumor size and clinical relevance are uncorrelated. To rebalance existing segmentation metrics, we propose to evaluate them on a per-component basis thus giving each tumor the same weight irrespective of its size. To match predictions to ground-truth segments, we employ a proximity-based matching criterion, evaluating common metrics locally at the component of interest. Using this approach, we break free of biases introduced by large metastasis for overlap-based metrics such as Dice or Surface Dice. CC-Metrics also improves distance-based metrics such as Hausdorff Distances which are uninformative for small changes that do not influence the maximum or 95th percentile, and avoids pitfalls introduced by directly combining counting-based metrics with overlap-based metrics as it is done in Panoptic Quality.
Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
Venue: arXiv cs.DS 2024
Year: 2024

We give the first deterministic algorithm that makes sub-quadratic queries to find the global min-cut of a simple graph in the cut query model. Given an $n$-vertex graph $G$, our algorithm makes $\widetilde{O}(n^{5/3})$ queries to compute the global min-cut in $G$. As a key ingredient, we also show an algorithm for finding $s$-$t$ max-flows of size $\widetilde{O}(n)$ in $\widetilde{O}(n^{5/3})$ queries. We also show efficient cut-query implementations of versions of expander decomposition and isolating cuts, which may be of independent interest.
ChatSearch: a Dataset and a Generative Retrieval Model for General Conversational Image Retrieval
Venue: arXiv cs.CV 2024
Year: 2024

In this paper, we investigate the task of general conversational image retrieval on open-domain images. The objective is to search for images based on interactive conversations between humans and computers. To advance this task, we curate a dataset called ChatSearch. This dataset includes a multi-round multimodal conversational context query for each target image, thereby requiring the retrieval system to find the accurate image from database. Simultaneously, we propose a generative retrieval model named ChatSearcher, which is trained end-to-end to accept/produce interleaved image-text inputs/outputs. ChatSearcher exhibits strong capability in reasoning with multimodal context and can leverage world knowledge to yield visual retrieval results. It demonstrates superior performance on the ChatSearch dataset and also achieves competitive results on other image retrieval tasks and visual conversation tasks. We anticipate that this work will inspire further research on interactive multimodal retrieval systems. Our dataset will be available at https://github.com/joez17/ChatSearch.
Citywide Electric Vehicle Charging Demand Prediction Approach Considering Urban Region and Dynamic Influences
Venue: arXiv cs.LG 2024
Year: 2024

Electric vehicle charging demand prediction is important for vacant charging pile recommendation and charging infrastructure planning, thus facilitating vehicle electrification and green energy development. The performance of previous spatio-temporal studies is still far from satisfactory nowadays because urban region attributes and multivariate temporal influences are not adequately taken into account. To tackle these issues, we propose a learning approach for citywide electric vehicle charging demand prediction, named CityEVCP. To learn non-pairwise relationships in urban areas, we cluster service areas by the types and numbers of points of interest in the areas and develop attentive hypergraph networks accordingly. Graph attention mechanisms are employed for information propagation between neighboring areas. Additionally, we propose a variable selection network to adaptively learn dynamic auxiliary information and improve the Transformer encoder utilizing gated mechanisms for fluctuating charging time-series data. Experiments on a citywide electric vehicle charging dataset demonstrate the performances of our proposed approach compared with a broad range of competing baselines. Furthermore, we demonstrate the impact of dynamic influences on prediction results in different areas of the city and the effectiveness of our area clustering method.
A Little Help Goes a Long Way: Efficient LLM Training by Leveraging Small LMs
Venue: arXiv cs.LG 2024
Year: 2024

A primary challenge in large language model (LLM) development is their onerous pre-training cost. Typically, such pre-training involves optimizing a self-supervised objective (such as next-token prediction) over a large corpus. This paper explores a promising paradigm to improve LLM pre-training efficiency and quality by suitably leveraging a small language model (SLM). In particular, this paradigm relies on an SLM to both (1) provide soft labels as additional training supervision, and (2) select a small subset of valuable ("informative" and "hard") training examples. Put together, this enables an effective transfer of the SLM's predictive distribution to the LLM, while prioritizing specific regions of the training data distribution. Empirically, this leads to reduced LLM training time compared to standard training, while improving the overall quality. Theoretically, we develop a statistical framework to systematically study the utility of SLMs in enabling efficient training of high-quality LLMs. In particular, our framework characterizes how the SLM's seemingly low-quality supervision can enhance the training of a much more capable LLM. Furthermore, it also highlights the need for an adaptive utilization of such supervision, by striking a balance between the bias and variance introduced by the SLM-provided soft labels. We corroborate our theoretical framework by improving the pre-training of an LLM with 2.8B parameters by utilizing a smaller LM with 1.5B parameters on the Pile dataset.
An LLM Agent for Automatic Geospatial Data Analysis
Venue: arXiv cs.CY 2024
Year: 2024

Large language models (LLMs) are being used in data science code generation tasks, but they often struggle with complex sequential tasks, leading to logical errors. Their application to geospatial data processing is particularly challenging due to difficulties in incorporating complex data structures and spatial constraints, effectively utilizing diverse function calls, and the tendency to hallucinate less-used geospatial libraries. To tackle these problems, we introduce GeoAgent, a new interactive framework designed to help LLMs handle geospatial data processing more effectively. GeoAgent pioneers the integration of a code interpreter, static analysis, and Retrieval-Augmented Generation (RAG) techniques within a Monte Carlo Tree Search (MCTS) algorithm, offering a novel approach to geospatial data processing. In addition, we contribute a new benchmark specifically designed to evaluate the LLM-based approach in geospatial tasks. This benchmark leverages a variety of Python libraries and includes both single-turn and multi-turn tasks such as data acquisition, data analysis, and visualization. By offering a comprehensive evaluation among diverse geospatial contexts, this benchmark sets a new standard for developing LLM-based approaches in geospatial data analysis tasks. Our findings suggest that relying solely on knowledge of LLM is insufficient for accurate geospatial task programming, which requires coherent multi-step processes and multiple function calls. Compared to the baseline LLMs, the proposed GeoAgent has demonstrated superior performance, yielding notable improvements in function calls and task completion. In addition, these results offer valuable insights for the future development of LLM agents in automatic geospatial data analysis task programming.
Adapting MLOps for Diverse In-Network Intelligence in 6G Era: Challenges and Solutions
Venue: arXiv cs.NI 2024
Year: 2024

Seamless integration of artificial intelligence (AI) and machine learning (ML) techniques with wireless systems is a crucial step for 6G AInization. However, such integration faces challenges in terms of model functionality and lifecycle management. ML operations (MLOps) offer a systematic approach to tackle these challenges. Existing approaches toward implementing MLOps in a centralized platform often overlook the challenges posed by diverse learning paradigms and network heterogeneity. This article provides a new approach to MLOps targeting the intricacies of future wireless networks. Considering unique aspects of the future radio access network (RAN), we formulate three operational pipelines, namely reinforcement learning operations (RLOps), federated learning operations (FedOps), and generative AI operations (GenOps). These pipelines form the foundation for seamlessly integrating various learning/inference capabilities into networks. We outline the specific challenges and proposed solutions for each operation, facilitating large-scale deployment of AI-Native 6G networks.
From Imitation to Introspection: Probing Self-Consciousness in Language Models
Venue: arXiv cs.CL 2024
Year: 2024

Self-consciousness, the introspection of one's existence and thoughts, represents a high-level cognitive process. As language models advance at an unprecedented pace, a critical question arises: Are these models becoming self-conscious? Drawing upon insights from psychological and neural science, this work presents a practical definition of self-consciousness for language models and refines ten core concepts. Our work pioneers an investigation into self-consciousness in language models by, for the first time, leveraging causal structural games to establish the functional definitions of the ten core concepts. Based on our definitions, we conduct a comprehensive four-stage experiment: quantification (evaluation of ten leading models), representation (visualization of self-consciousness within the models), manipulation (modification of the models' representation), and acquisition (fine-tuning the models on core concepts). Our findings indicate that although models are in the early stages of developing self-consciousness, there is a discernible representation of certain concepts within their internal mechanisms. However, these representations of self-consciousness are hard to manipulate positively at the current stage, yet they can be acquired through targeted fine-tuning. Our datasets and code are at https://github.com/OpenCausaLab/SelfConsciousness.
From English-Centric to Effective Bilingual: LLMs with Custom Tokenizers for Underrepresented Languages
Venue: arXiv cs.CL 2024
Year: 2024

In this paper, we propose a model-agnostic cost-effective approach to developing bilingual base large language models (LLMs) to support English and any target language. The method includes vocabulary expansion, initialization of new embeddings, model training and evaluation. We performed our experiments with three languages, each using a non-Latin script - Ukrainian, Arabic, and Georgian. Our approach demonstrates improved language performance while reducing computational costs. It mitigates the disproportionate penalization of underrepresented languages, promoting fairness and minimizing adverse phenomena such as code-switching and broken grammar. Additionally, we introduce new metrics to evaluate language quality, revealing that vocabulary size significantly impacts the quality of generated text.
Intention Is All You Need
Venue: arXiv cs.HC 2024
Year: 2024

Among the many narratives of the transformative power of Generative AI is one that sees in the world a latent nation of programmers who need to wield nothing but intentions and natural language to render their ideas in software. In this paper, this outlook is problematised in two ways. First, it is observed that generative AI is not a neutral vehicle of intention. Multiple recent studies paint a picture of the "mechanised convergence" phenomenon, namely, that generative AI has a homogenising effect on intention. Second, it is observed that the formation of intention itself is immensely challenging. Constraints, materiality, and resistance can offer paths to design metaphors for intentional tools. Finally, existentialist approaches to intention are discussed and possible implications for programming are proposed in the form of a speculative, illustrative set of intentional programming practices.
DL-Polycube: Deep learning enhanced polycube method for high-quality hexahedral mesh generation and volumetric spline construction
Venue: arXiv cs.CG 2024
Year: 2024

In this paper, we present a novel algorithm that integrates deep learning with the polycube method (DL-Polycube) to generate high-quality hexahedral (hex) meshes, which are then used to construct volumetric splines for isogeometric analysis. Our DL-Polycube algorithm begins by establishing a connection between surface triangular meshes and polycube structures. We employ deep neural network to classify surface triangular meshes into their corresponding polycube structures. Following this, we combine the acquired polycube structural information with unsupervised learning to perform surface segmentation of triangular meshes. This step addresses the issue of segmentation not corresponding to a polycube while reducing manual intervention. Quality hex meshes are then generated from the polycube structures, with employing octree subdivision, parametric mapping and quality improvement techniques. The incorporation of deep learning for creating polycube structures, combined with unsupervised learning for segmentation of surface triangular meshes, substantially accelerates hex mesh generation. Finally, truncated hierarchical B-splines are constructed on the generated hex meshes. We extract trivariate Bézier elements from these splines and apply them directly in isogeometric analysis. We offer several examples to demonstrate the robustness of our DL-Polycube algorithm.
Matching Composition and Efficient Weight Reduction in Dynamic Matching
Venue: arXiv cs.DS 2024
Year: 2024

We consider the foundational problem of maintaining a $(1-\varepsilon)$-approximate maximum weight matching (MWM) in an $n$-node dynamic graph undergoing edge insertions and deletions. We provide a general reduction that reduces the problem on graphs with a weight range of $\mathrm{poly}(n)$ to $\mathrm{poly}(1/\varepsilon)$ at the cost of just an additive $\mathrm{poly}(1/\varepsilon)$ in update time. This improves upon the prior reduction of Gupta-Peng (FOCS 2013) which reduces the problem to a weight range of $\varepsilon^{-O(1/\varepsilon)}$ with a multiplicative cost of $O(\log n)$. When combined with a reduction of Bernstein-Dudeja-Langley (STOC 2021) this yields a reduction from dynamic $(1-\varepsilon)$-approximate MWM in bipartite graphs with a weight range of $\mathrm{poly}(n)$ to dynamic $(1-\varepsilon)$-approximate maximum cardinality matching in bipartite graphs at the cost of a multiplicative $\mathrm{poly}(1/\varepsilon)$ in update time, thereby resolving an open problem in [GP'13; BDL'21]. Additionally, we show that our approach is amenable to MWM problems in streaming, shared-memory work-depth, and massively parallel computation models. We also apply our techniques to obtain an efficient dynamic algorithm for rounding weighted fractional matchings in general graphs. Underlying our framework is a new structural result about MWM that we call the "matching composition lemma" and new dynamic matching subroutines that may be of independent interest.