OpenRaiser/Intern-Atlas huggingface dataset:
Constraint Propagation on GPU: A Case Study for the Bin Packing Constraint
Venue: arXiv cs.OH 2024
Year: 2024

The Bin Packing Problem is one of the most important problems in discrete optimization, as it captures the requirements of many real-world problems. Because of its importance, it has been approached with the main theoretical and practical tools. Resolution approaches based on Linear Programming are the most effective, while Constraint Programming proves valuable when the Bin Packing Problem is a component of a larger problem. This work focuses on the Bin Packing constraint and explores how GPUs can be used to enhance its propagation algorithm. Two approaches are motivated and discussed, one based on knapsack reasoning and one using alternative lower bounds. The implementations are evaluated in comparison with state-of-the-art approaches on different benchmarks from the literature. The results indicate that the GPU-accelerated lower bounds offers a desirable alternative to tackle large instances.
MIKE: A New Benchmark for Fine-grained Multimodal Entity Knowledge Editing
Venue: arXiv cs.CL 2024
Year: 2024

Multimodal knowledge editing represents a critical advancement in enhancing the capabilities of Multimodal Large Language Models (MLLMs). Despite its potential, current benchmarks predominantly focus on coarse-grained knowledge, leaving the intricacies of fine-grained (FG) multimodal entity knowledge largely unexplored. This gap presents a notable challenge, as FG entity recognition is pivotal for the practical deployment and effectiveness of MLLMs in diverse real-world scenarios. To bridge this gap, we introduce MIKE, a comprehensive benchmark and dataset specifically designed for the FG multimodal entity knowledge editing. MIKE encompasses a suite of tasks tailored to assess different perspectives, including Vanilla Name Answering, Entity-Level Caption, and Complex-Scenario Recognition. In addition, a new form of knowledge editing, Multi-step Editing, is introduced to evaluate the editing efficiency. Through our extensive evaluations, we demonstrate that the current state-of-the-art methods face significant challenges in tackling our proposed benchmark, underscoring the complexity of FG knowledge editing in MLLMs. Our findings spotlight the urgent need for novel approaches in this domain, setting a clear agenda for future research and development efforts within the community.
CHATATC: Large Language Model-Driven Conversational Agents for Supporting Strategic Air Traffic Flow Management
Venue: arXiv cs.CL 2024
Year: 2024

Generative artificial intelligence (AI) and large language models (LLMs) have gained rapid popularity through publicly available tools such as ChatGPT. The adoption of LLMs for personal and professional use is fueled by the natural interactions between human users and computer applications such as ChatGPT, along with powerful summarization and text generation capabilities. Given the widespread use of such generative AI tools, in this work we investigate how these tools can be deployed in a non-safety critical, strategic traffic flow management setting. Specifically, we train an LLM, CHATATC, based on a large historical data set of Ground Delay Program (GDP) issuances, spanning 2000-2023 and consisting of over 80,000 GDP implementations, revisions, and cancellations. We test the query and response capabilities of CHATATC, documenting successes (e.g., providing correct GDP rates, durations, and reason) and shortcomings (e.g,. superlative questions). We also detail the design of a graphical user interface for future users to interact and collaborate with the CHATATC conversational agent.
NL2Formula: Generating Spreadsheet Formulas from Natural Language Queries
Venue: arXiv cs.CL 2024
Year: 2024

Writing formulas on spreadsheets, such as Microsoft Excel and Google Sheets, is a widespread practice among users performing data analysis. However, crafting formulas on spreadsheets remains a tedious and error-prone task for many end-users, particularly when dealing with complex operations. To alleviate the burden associated with writing spreadsheet formulas, this paper introduces a novel benchmark task called NL2Formula, with the aim to generate executable formulas that are grounded on a spreadsheet table, given a Natural Language (NL) query as input. To accomplish this, we construct a comprehensive dataset consisting of 70,799 paired NL queries and corresponding spreadsheet formulas, covering 21,670 tables and 37 types of formula functions. We realize the NL2Formula task by providing a sequence-to-sequence baseline implementation called fCoder. Experimental results validate the effectiveness of fCoder, demonstrating its superior performance compared to the baseline models. Furthermore, we also compare fCoder with an initial GPT-3.5 model (i.e., text-davinci-003). Lastly, through in-depth error analysis, we identify potential challenges in the NL2Formula task and advocate for further investigation.
CloudNine: Analyzing Meteorological Observation Impact on Weather Prediction Using Explainable Graph Neural Networks
Venue: arXiv cs.LG 2024
Year: 2024

The impact of meteorological observations on weather forecasting varies with sensor type, location, time, and other environmental factors. Thus, quantitative analysis of observation impacts is crucial for effective and efficient development of weather forecasting systems. However, the existing impact analysis methods are difficult to be widely applied due to their high dependencies on specific forecasting systems. Also, they cannot provide observation impacts at multiple spatio-temporal scales, only global impacts of observation types. To address these issues, we present a novel system called ``CloudNine,'' which allows analysis of individual observations' impacts on specific predictions based on explainable graph neural networks (XGNNs). Combining an XGNN-based atmospheric state estimation model with a numerical weather prediction model, we provide a web application to search for observations in the 3D space of the Earth system and to visualize the impact of individual observations on predictions in specific spatial regions and time periods.
Evaluation of a semi-autonomous attentive listening system with takeover prompting
Venue: arXiv cs.CL 2024
Year: 2024

The handling of communication breakdowns and loss of engagement is an important aspect of spoken dialogue systems, particularly for chatting systems such as attentive listening, where the user is mostly speaking. We presume that a human is best equipped to handle this task and rescue the flow of conversation. To this end, we propose a semi-autonomous system, where a remote operator can take control of an autonomous attentive listening system in real-time. In order to make human intervention easy and consistent, we introduce automatic detection of low interest and engagement to provide explicit takeover prompts to the remote operator. We implement this semi-autonomous system which detects takeover points for the operator and compare it to fully tele-operated and fully autonomous attentive listening systems. We find that the semi-autonomous system is generally perceived more positively than the autonomous system. The results suggest that identifying points of conversation when the user starts to lose interest may help us improve a fully autonomous dialogue system.
APTQ: Attention-aware Post-Training Mixed-Precision Quantization for Large Language Models
Venue: arXiv cs.LG 2024
Year: 2024

Large Language Models (LLMs) have greatly advanced the natural language processing paradigm. However, the high computational load and huge model sizes pose a grand challenge for deployment on edge devices. To this end, we propose APTQ (Attention-aware Post-Training Mixed-Precision Quantization) for LLMs, which considers not only the second-order information of each layer's weights, but also, for the first time, the nonlinear effect of attention outputs on the entire model. We leverage the Hessian trace as a sensitivity metric for mixed-precision quantization, ensuring an informed precision reduction that retains model performance. Experiments show APTQ surpasses previous quantization methods, achieving an average of 4 bit width a 5.22 perplexity nearly equivalent to full precision in the C4 dataset. In addition, APTQ attains state-of-the-art zero-shot accuracy of 68.24\% and 70.48\% at an average bitwidth of 3.8 in LLaMa-7B and LLaMa-13B, respectively, demonstrating its effectiveness to produce high-quality quantized LLMs.
Effects of term weighting approach with and without stop words removing on Arabic text classification
Venue: arXiv cs.CL 2024
Year: 2024

Classifying text is a method for categorizing documents into pre-established groups. Text documents must be prepared and represented in a way that is appropriate for the algorithms used for data mining prior to classification. As a result, a number of term weighting strategies have been created in the literature to enhance text categorization algorithms' functionality. This study compares the effects of Binary and Term frequency weighting feature methodologies on the text's classification method when stop words are eliminated once and when they are not. In recognition of assessing the effects of prior weighting of features approaches on classification results in terms of accuracy, recall, precision, and F-measure values, we used an Arabic data set made up of 322 documents divided into six main topics (agriculture, economy, health, politics, science, and sport), each of which contains 50 documents, with the exception of the health category, which contains 61 documents. The results demonstrate that for all metrics, the term frequency feature weighting approach with stop word removal outperforms the binary approach, while for accuracy, recall, and F-Measure, the binary approach outperforms the TF approach without stop word removal. However, for precision, the two approaches produce results that are very similar. Additionally, it is clear from the data that, using the same phrase weighting approach, stop word removing increases classification accuracy.
Driving Generative Agents With Their Personality
Venue: arXiv cs.CL 2024
Year: 2024

This research explores the potential of Large Language Models (LLMs) to utilize psychometric values, specifically personality information, within the context of video game character development. Affective Computing (AC) systems quantify a Non-Player character's (NPC) psyche, and an LLM can take advantage of the system's information by using the values for prompt generation. The research shows an LLM can consistently represent a given personality profile, thereby enhancing the human-like characteristics of game characters. Repurposing a human examination, the International Personality Item Pool (IPIP) questionnaire, to evaluate an LLM shows that the model can accurately generate content concerning the personality provided. Results show that the improvement of LLM, such as the latest GPT-4 model, can consistently utilize and interpret a personality to represent behavior.
BIONIB: Blockchain-based IoT using Novelty Index in Bridge Health Monitoring
Venue: arXiv cs.CR 2024
Year: 2024

Bridge health monitoring becomes crucial with the deployment of IoT sensors. The challenge lies in securely storing vast amounts of data and extracting useful information to promptly identify unhealthy bridge conditions. To address this challenge, we propose BIONIB, wherein real-time IoT data is stored on the blockchain for monitoring bridges. One of the emerging blockchains, EOSIO is used because of its exceptional scaling capabilities for monitoring the health of bridges. The approach involves collecting data from IoT sensors and using an unsupervised machine learning-based technique called the Novelty Index (NI) to observe meaningful patterns in the data. Smart contracts of EOSIO are used in implementation because of their efficiency, security, and programmability, making them well-suited for handling complex transactions and automating processes within decentralized applications. BIONIB provides secure storage benefits of blockchain, as well as useful predictions based on the NI. Performance analysis uses real-time data collected from IoT sensors at the bridge in healthy and unhealthy states. The data is collected with extensive experimentation with different loads, climatic conditions, and the health of the bridge. The performance of BIONIB under varying numbers of sensors and various numbers of participating blockchain nodes is observed. We observe a tradeoff between throughput, latency, and computational resources. Storage efficiency can be increased by manifolds with a slight increase in latency caused by NI calculation. As latency is not a significant concern in bridge health applications, the results demonstrate that BIONIB has high throughput, parallel processing, and high security while efficiently scaled.
Path Planning based on 2D Object Bounding-box
Venue: arXiv cs.RO 2024
Year: 2024

The implementation of Autonomous Driving (AD) technologies within urban environments presents significant challenges. These challenges necessitate the development of advanced perception systems and motion planning algorithms capable of managing situations of considerable complexity. Although the end-to-end AD method utilizing LiDAR sensors has achieved significant success in this scenario, we argue that its drawbacks may hinder its practical application. Instead, we propose the vision-centric AD as a promising alternative offering a streamlined model without compromising performance. In this study, we present a path planning method that utilizes 2D bounding boxes of objects, developed through imitation learning in urban driving scenarios. This is achieved by integrating high-definition (HD) map data with images captured by surrounding cameras. Subsequent perception tasks involve bounding-box detection and tracking, while the planning phase employs both local embeddings via Graph Neural Network (GNN) and global embeddings via Transformer for temporal-spatial feature aggregation, ultimately producing optimal path planning information. We evaluated our model on the nuPlan planning task and observed that it performs competitively in comparison to existing vision-centric methods.
MultiLS: A Multi-task Lexical Simplification Framework
Venue: arXiv cs.CL 2024
Year: 2024

Lexical Simplification (LS) automatically replaces difficult to read words for easier alternatives while preserving a sentence's original meaning. LS is a precursor to Text Simplification with the aim of improving text accessibility to various target demographics, including children, second language learners, individuals with reading disabilities or low literacy. Several datasets exist for LS. These LS datasets specialize on one or two sub-tasks within the LS pipeline. However, as of this moment, no single LS dataset has been developed that covers all LS sub-tasks. We present MultiLS, the first LS framework that allows for the creation of a multi-task LS dataset. We also present MultiLS-PT, the first dataset to be created using the MultiLS framework. We demonstrate the potential of MultiLS-PT by carrying out all LS sub-tasks of (1). lexical complexity prediction (LCP), (2). substitute generation, and (3). substitute ranking for Portuguese. Model performances are reported, ranging from transformer-based models to more recent large language models (LLMs).
Energy-Efficient Active Element Selection in RIS-aided Massive MIMO Systems
Venue: arXiv cs.IT 2024
Year: 2024

This chapter delves into the critical aspects of optimizing energy efficiency (EE) in active reconfigurable intelligent surface (RIS)-assisted massive MIMO (M-MIMO) wireless communication systems. We develop a comprehensive and unified theoretical framework to analyze the boundaries of EE within M-MIMO systems integrated with active RIS while adhering to practical constraints. Our research focuses on a formulated EE optimization problem aiming to maximize the EE for active RIS-assisted M-MIMO communication systems. Our goal is to strategically find the number of active RIS elements for outperforming the EE attainable by an entirely passive RIS. Besides, the proposed novel solution has been tailored to the innovative problem. The formulation and solution design consider analytical optimization techniques, such as lagrangian dual transform (LDT) and fractional programming (FP) optimization, facilitating the effective implementation of RIS-aided M-MIMO applications in real-world settings. In particular, our results show that the proposed algorithm can provide up to 120% higher EE than the entirely passive RIS. Besides, we found that the active RIS can operate with less than half of the reflecting elements for the entirely passive RIS. Finally, in view of active RIS achieving the complete utilization of amplification power available, it should be equipped with a reasonable number of reflecting elements above N = 49.
Divide-or-Conquer? Which Part Should You Distill Your LLM?
Venue: arXiv cs.CL 2024
Year: 2024

Recent methods have demonstrated that Large Language Models (LLMs) can solve reasoning tasks better when they are encouraged to solve subtasks of the main task first. In this paper we devise a similar strategy that breaks down reasoning tasks into a problem decomposition phase and a problem solving phase and show that the strategy is able to outperform a single stage solution. Further, we hypothesize that the decomposition should be easier to distill into a smaller model compared to the problem solving because the latter requires large amounts of domain knowledge while the former only requires learning general problem solving strategies. We propose methods to distill these two capabilities and evaluate their impact on reasoning outcomes and inference cost. We find that we can distill the problem decomposition phase and at the same time achieve good generalization across tasks, datasets, and models. However, it is harder to distill the problem solving capability without losing performance and the resulting distilled model struggles with generalization. These results indicate that by using smaller, distilled problem decomposition models in combination with problem solving LLMs we can achieve reasoning with cost-efficient inference and local adaptation.
Ar-Spider: Text-to-SQL in Arabic
Venue: arXiv cs.CL 2024
Year: 2024

In Natural Language Processing (NLP), one of the most important tasks is text-to-SQL semantic parsing, which focuses on enabling users to interact with the database in a more natural manner. In recent years, text-to-SQL has made significant progress, but most were English-centric. In this paper, we introduce Ar-Spider 1, the first Arabic cross-domain text-to-SQL dataset. Due to the unique nature of the language, two major challenges have been encountered, namely schema linguistic and SQL structural challenges. In order to handle these issues and conduct the experiments, we adopt two baseline models LGESQL [4] and S2SQL [12], both of which are tested with two cross-lingual models to alleviate the effects of schema linguistic and SQL structure linking challenges. The baselines demonstrate decent single-language performance on our Arabic text-to-SQL dataset, Ar-Spider, achieving 62.48% for S2SQL and 65.57% for LGESQL, only 8.79% below the highest results achieved by the baselines when trained in English dataset. To achieve better performance on Arabic text-to-SQL, we propose the context similarity relationship (CSR) approach, which results in a significant increase in the overall performance of about 1.52% for S2SQL and 1.06% for LGESQL and closes the gap between Arabic and English languages to 7.73%.
Towards Probabilistically-Sound Beam Search with Masked Language Models
Venue: arXiv cs.LG 2024
Year: 2024

Beam search with masked language models (MLMs) is challenging in part because joint probability distributions over sequences are not readily available, unlike for autoregressive models. However, estimating such distributions has important domain-specific applications such as ancient text restoration and protein engineering. Here we present probabilistically-sound methods for beam search with MLMs. First, we clarify the conditions under which it is theoretically sound to perform text infilling with MLMs using standard beam search. When these conditions fail, we provide a probabilistically-sound inference time modification with no additional computational complexity and demonstrate that it is superior to the aforementioned beam search in the expected conditions. We then present empirical results comparing several infilling approaches with MLMs across several domains. Notably, our method probes the inductive biases of MLMs and explores the surprising contextual sensitivity of mask tokens for text infilling.
Multi Agent Influence Diagrams for DeFi Governance
Venue: arXiv cs.GT 2024
Year: 2024

Decentralized Finance (DeFi) governance models have become increasingly complex due to the involvement of numerous independent agents, each with their own incentives and strategies. To effectively analyze these systems, we propose using Multi Agent Influence Diagrams (MAIDs) as a powerful tool for modeling and studying the strategic interactions within DeFi governance. MAIDs allow for a comprehensive representation of the decision-making processes of various agents, capturing the influence of their actions on one another and on the overall governance outcomes. In this paper, we study a simple governance game that approximates real governance protocols and compute the Nash equilibria using MAIDs. We further outline the structure of a MAID in MakerDAO.
Cost-Adaptive Recourse Recommendation by Adaptive Preference Elicitation
Venue: arXiv cs.LG 2024
Year: 2024

Algorithmic recourse recommends a cost-efficient action to a subject to reverse an unfavorable machine learning classification decision. Most existing methods in the literature generate recourse under the assumption of complete knowledge about the cost function. In real-world practice, subjects could have distinct preferences, leading to incomplete information about the underlying cost function of the subject. This paper proposes a two-step approach integrating preference learning into the recourse generation problem. In the first step, we design a question-answering framework to refine the confidence set of the Mahalanobis matrix cost of the subject sequentially. Then, we generate recourse by utilizing two methods: gradient-based and graph-based cost-adaptive recourse that ensures validity while considering the whole confidence set of the cost matrix. The numerical evaluation demonstrates the benefits of our approach over state-of-the-art baselines in delivering cost-efficient recourse recommendations.
Tight Inapproximability of Target Set Reconfiguration
Venue: arXiv cs.DS 2024
Year: 2024

Given a graph $G$ with a vertex threshold function $τ$, consider a dynamic process in which any inactive vertex $v$ becomes activated whenever at least $τ(v)$ of its neighbors are activated. A vertex set $S$ is called a target set if all vertices of $G$ would be activated when initially activating vertices of $S$. In the Minmax Target Set Reconfiguration problem, for a graph $G$ and its two target sets $X$ and $Y$, we wish to transform $X$ into $Y$ by repeatedly adding or removing a single vertex, using only target sets of $G$, so as to minimize the maximum size of any intermediate target set. We prove that it is NP-hard to approximate Minmax Target Set Reconfiguration within a factor of $2-o\left(\frac{1}{\operatorname{polylog} n}\right)$, where $n$ is the number of vertices. Our result establishes a tight lower bound on approximability of Minmax Target Set Reconfiguration, which admits a $2$-factor approximation algorithm. The proof is based on a gap-preserving reduction from Target Set Selection to Minmax Target Set Reconfiguration, where NP-hardness of approximation for the former problem is proven by Chen (SIAM J. Discrete Math., 2009) and Charikar, Naamad, and Wirth (APPROX/RANDOM 2016).