OpenRaiser/Intern-Atlas huggingface dataset:
Double Exponential Lower Bound for Telephone Broadcast
Venue: arXiv cs.DS 2024
Year: 2024

Consider the Telephone Broadcast problem in which an input is a connected graph $G$ on $n$ vertices, a source vertex $s \in V(G)$, and a positive integer $t$. The objective is to decide whether there is a broadcast protocol from $s$ that ensures that all the vertices of $G$ get the message in at most $t$ rounds. We consider the broadcast protocol where, in a round, any node aware of the message can forward it to at most one of its neighbors. As the number of nodes aware of the message can at most double at each round, for a non-trivial instance we have $n \le 2^t$. Hence, the brute force algorithm that checks all the permutations of the vertices runs in time $2^{2^{\calO(t)}} \cdot n^{\calO(1)}$. As our first result, we prove this simple algorithm is the best possible in the following sense. Telephone Broadcast does not admit an algorithm running in time $2^{2^{o(t)}} \cdot n^{\calO(1)}$, unless the Ð fails. To the best of our knowledge, this is only the fourth example of \NP-Complete problem that admits a double exponential lower bound when parameterized by the solution size. It also resolves the question by Fomin, Fraigniaud, and Golovach [WG 2023]. In the same article, the authors asked whether the problem is \FPT\ when parameterized by the feedback vertex set number of the graph. We answer this question in the negative. Telephone Broadcast, when restricted to graphs of the feedback vertex number one, and hence treewidth of two, is \NP-\complete. We find this a relatively rare example of problems that admit a polynomial-time algorithm on trees but is \NP-\complete\ on graphs of treewidth two.
Application of Nash equilibrium for developing an optimal forest harvesting strategy in Toruń Forest District
Venue: arXiv cs.GT 2024
Year: 2024

This study investigates the application of Nash equilibrium strategies in optimizing forest harvesting decisions, focusing on multiple management objectives in forestry. Through simulation-based analysis, the research explores the evolution of various indicators during the game: 1) the mass of CO2 sequestration, 2) forest stands biodiversity, 3) the harvested wood volume, 4) native species fraction, and 5) protective functions. The results underscore the importance of considering diverse objectives and balancing competing interests in forestry decision processes. The forest stands designated for harvesting in the Toruń Forest District were defined as the initial strategy, and indicators for all objectives were calculated accordingly. A Nash equilibrium was identified through a game involving five players representing individual objectives with partially conflicting aims. The final strategy was obtained by modifying specific forest stands designated for harvesting, thereby maintaining the planned wood volume extraction while simultaneously reducing biodiversity loss by nearly 40%, preserving protective functions across over 600 hectares of forested areas, enhancing decadal carbon sequestration in the forest district by 100,000 tons, and additionally improving species suitability by nearly 10%. The findings suggest the potential for further research and refinement of Nash equilibrium-based optimization approaches to enhance the effectiveness and sustainability of forest management practices.
Time-optimal Point-to-point Motion Planning: A Two-stage Approach
Venue: arXiv cs.RO 2024
Year: 2024

This paper proposes a two-stage approach to formulate the time-optimal point-to-point motion planning problem, involving a first stage with a fixed time grid and a second stage with a variable time grid. The proposed approach brings benefits through its straightforward optimal control problem formulation with a fixed and low number of control steps for manageable computational complexity and the avoidance of interpolation errors associated with time scaling, especially when aiming to reach a distant goal. Additionally, an asynchronous nonlinear model predictive control (NMPC) update scheme is integrated with this two-stage approach to address delayed and fluctuating computation times, facilitating online replanning. The effectiveness of the proposed two-stage approach and NMPC implementation is demonstrated through numerical examples centered on autonomous navigation with collision avoidance.
gaHealth: An English-Irish Bilingual Corpus of Health Data
Venue: arXiv cs.CL 2024
Year: 2024

Machine Translation is a mature technology for many high-resource language pairs. However in the context of low-resource languages, there is a paucity of parallel data datasets available for developing translation models. Furthermore, the development of datasets for low-resource languages often focuses on simply creating the largest possible dataset for generic translation. The benefits and development of smaller in-domain datasets can easily be overlooked. To assess the merits of using in-domain data, a dataset for the specific domain of health was developed for the low-resource English to Irish language pair. Our study outlines the process used in developing the corpus and empirically demonstrates the benefits of using an in-domain dataset for the health domain. In the context of translating health-related data, models developed using the gaHealth corpus demonstrated a maximum BLEU score improvement of 22.2 points (40%) when compared with top performing models from the LoResMT2021 Shared Task. Furthermore, we define linguistic guidelines for developing gaHealth, the first bilingual corpus of health data for the Irish language, which we hope will be of use to other creators of low-resource data sets. gaHealth is now freely available online and is ready to be explored for further research.
Enhancing ASD detection accuracy: a combined approach of machine learning and deep learning models with natural language processing
Venue: arXiv cs.CL 2024
Year: 2024

Purpose: Our study explored the use of artificial intelligence (AI) to diagnose autism spectrum disorder (ASD). It focused on machine learning (ML) and deep learning (DL) to detect ASD from text inputs on social media, addressing challenges in traditional ASD diagnosis. Methods: We used natural language processing (NLP), ML, and DL models (including decision trees, XGB, KNN, RNN, LSTM, Bi-LSTM, BERT, and BERTweet) to analyze 404,627 tweets, classifying them based on ASD or non-ASD authors. A subset of 90,000 tweets was used for model training and testing. Results: Our AI models showed high accuracy, with an 88% success rate in identifying texts from individuals with ASD. Conclusion: The study demonstrates AI's potential in improving ASD diagnosis, especially in children, highlighting the importance of early detection.
Design of an Open-Source Architecture for Neural Machine Translation
Venue: arXiv cs.CL 2024
Year: 2024

adaptNMT is an open-source application that offers a streamlined approach to the development and deployment of Recurrent Neural Networks and Transformer models. This application is built upon the widely-adopted OpenNMT ecosystem, and is particularly useful for new entrants to the field, as it simplifies the setup of the development environment and creation of train, validation, and test splits. The application offers a graphing feature that illustrates the progress of model training, and employs SentencePiece for creating subword segmentation models. Furthermore, the application provides an intuitive user interface that facilitates hyperparameter customization. Notably, a single-click model development approach has been implemented, and models developed by adaptNMT can be evaluated using a range of metrics. To encourage eco-friendly research, adaptNMT incorporates a green report that flags the power consumption and kgCO${_2}$ emissions generated during model development. The application is freely available.
Multi-time-step coupling of peridynamics and classical continuum mechanics for dynamic brittle fracture
Venue: arXiv cs.CE 2024
Year: 2024

Peridynamics (PD), as a nonlocal theory, is well-suited for solving problems with discontinuities, such as cracks. However, the nonlocal effect of peridynamics makes it computationally expensive for dynamic fracture problems in large-scale engineering applications. As an alternative, this study proposes a multi-time-step (MTS) coupling model of PD and classical continuum mechanics (CCM) based on the Arlequin framework. Peridynamics is applied to the fracture domain of the structure, while continuum mechanics is applied to the rest of the structure. The MTS method enables the peridynamic model to be solved at a small time step and the continuum mechanical model is solved at a larger time step. Consequently, higher computational efficiency is achieved for the fracture domain of the structure while ensuring computational accuracy, and this coupling method can be easily applied to large-scale engineering fracture problems.
Integrity-protecting block cipher modes -- Untangling a tangled web
Venue: arXiv cs.CR 2024
Year: 2024

This paper re-examines the security of three related block cipher modes of operation designed to provide authenticated encryption. These modes, known as PES-PCBC, IOBC and EPBC, were all proposed in the mid-1990s. However, analyses of security of the latter two modes were published more recently. In each case one or more papers describing security issues with the schemes were eventually published, although a flaw in one of these analyses (of EPBC) was subsequently discovered - this means that until now EPBC had no known major issues. This paper establishes that, despite this, all three schemes possess defects which should prevent their use - especially as there are a number of efficient alternative schemes possessing proofs of security.
ZF Beamforming Tensor Compression for Massive MIMO Fronthaul
Venue: arXiv cs.IT 2024
Year: 2024

In the rapidly evolving landscape of 5G and beyond 5G (B5G) mobile cellular communications, efficient data compression and reconstruction strategies become paramount, especially in massive multiple-input multiple-output (MIMO) systems. A critical challenge in these systems is the capacity-limited fronthaul, particularly in the context of the Ethernet-based common public radio interface (eCPRI) connecting baseband units (BBUs) and remote radio units (RRUs). This capacity limitation hinders the effective handling of increased traffic and data flows. We propose a novel two-stage compression approach to address this bottleneck. The first stage employs sparse Tucker decomposition, targeting the weight tensor's low-rank components for compression. The second stage further compresses these components using complex givens decomposition and run-length encoding, substantially improving the compression ratio. Our approach specifically targets the Zero-Forcing (ZF) beamforming weights in BBUs. By reconstructing these weights in RRUs, we significantly alleviate the burden on eCPRI traffic, enabling a higher number of concurrent streams in the radio access network (RAN). Through comprehensive evaluations, we demonstrate the superior effectiveness of our method in Channel State Information (CSI) compression, paving the way for more efficient 5G/B5G fronthaul links.
Portable, heterogeneous ensemble workflows at scale using libEnsemble
Venue: arXiv cs.DC 2024
Year: 2024

libEnsemble is a Python-based toolkit for running dynamic ensembles, developed as part of the DOE Exascale Computing Project. The toolkit utilizes a unique generator--simulator--allocator paradigm, where generators produce input for simulators, simulators evaluate those inputs, and allocators decide whether and when a simulator or generator should be called. The generator steers the ensemble based on simulation results. Generators may, for example, apply methods for numerical optimization, machine learning, or statistical calibration. libEnsemble communicates between a manager and workers. We overview the unique characteristics of libEnsemble as well as current and potential interoperability with other packages in the workflow ecosystem. We highlight libEnsemble's dynamic resource features: libEnsemble can detect system resources, such as available nodes, cores, and GPUs, and assign these in a portable way. These features allow users to specify the number of processors and GPUs required for each simulation; and resources will be automatically assigned on a wide range of systems, including Frontier, Aurora, and Perlmutter. Such ensembles can include multiple simulation types, some using GPUs and others using only CPUs, sharing nodes for maximum efficiency. We also describe the benefits of libEnsemble's generator--simulator coupling, which easily exposes to the user the ability to cancel, and portably kill, running simulations based on models that are updated with intermediate simulation output. We demonstrate libEnsemble's capabilities, scalability, and scientific impact via a Gaussian process surrogate training problem for the longitudinal density profile at the exit of a plasma accelerator stage. The study uses gpCAM for the surrogate model and employs either Wake-T or WarpX simulations, highlighting efficient use of resources that can easily extend to exascale.
In the Search of Optimal Tree Networks: Hardness and Heuristics
Venue: arXiv cs.NI 2024
Year: 2024

Demand-aware communication networks are networks whose topology is optimized toward the traffic they need to serve. These networks have recently been enabled by novel optical communication technologies and are investigated intensively in the context of datacenters. In this work, we consider networks with one of the most common topologies~ -- a binary tree. We show that finding an optimal demand-aware binary tree network is NP-hard. Then, we propose optimization algorithms that generate efficient binary tree networks on real-life and synthetic workloads.
A machine learning workflow to address credit default prediction
Venue: arXiv cs.CE 2024
Year: 2024

Due to the recent increase in interest in Financial Technology (FinTech), applications like credit default prediction (CDP) are gaining significant industrial and academic attention. In this regard, CDP plays a crucial role in assessing the creditworthiness of individuals and businesses, enabling lenders to make informed decisions regarding loan approvals and risk management. In this paper, we propose a workflow-based approach to improve CDP, which refers to the task of assessing the probability that a borrower will default on his or her credit obligations. The workflow consists of multiple steps, each designed to leverage the strengths of different techniques featured in machine learning pipelines and, thus best solve the CDP task. We employ a comprehensive and systematic approach starting with data preprocessing using Weight of Evidence encoding, a technique that ensures in a single-shot data scaling by removing outliers, handling missing values, and making data uniform for models working with different data types. Next, we train several families of learning models, introducing ensemble techniques to build more robust models and hyperparameter optimization via multi-objective genetic algorithms to consider both predictive accuracy and financial aspects. Our research aims at contributing to the FinTech industry in providing a tool to move toward more accurate and reliable credit risk assessment, benefiting both lenders and borrowers.
Realizability of Rectangular Euler Diagrams
Venue: arXiv cs.CG 2024
Year: 2024

Euler diagrams are a tool for the graphical representation of set relations. Due to their simple way of visualizing elements in the sets by geometric containment, they are easily readable by an inexperienced reader. Euler diagrams where the sets are visualized as aligned rectangles are of special interest. In this work, we link the existence of such rectangular Euler diagrams to the order dimension of an associated order relation. For this, we consider Euler diagrams in one and two dimensions. In the one-dimensional case, this correspondence provides us with a polynomial-time algorithm to compute the Euler diagrams, while the two-dimensional case is linked to an NP-complete problem which we approach with an exponential-time algorithm.
ProbSAINT: Probabilistic Tabular Regression for Used Car Pricing
Venue: arXiv cs.LG 2024
Year: 2024

Used car pricing is a critical aspect of the automotive industry, influenced by many economic factors and market dynamics. With the recent surge in online marketplaces and increased demand for used cars, accurate pricing would benefit both buyers and sellers by ensuring fair transactions. However, the transition towards automated pricing algorithms using machine learning necessitates the comprehension of model uncertainties, specifically the ability to flag predictions that the model is unsure about. Although recent literature proposes the use of boosting algorithms or nearest neighbor-based approaches for swift and precise price predictions, encapsulating model uncertainties with such algorithms presents a complex challenge. We introduce ProbSAINT, a model that offers a principled approach for uncertainty quantification of its price predictions, along with accurate point predictions that are comparable to state-of-the-art boosting techniques. Furthermore, acknowledging that the business prefers pricing used cars based on the number of days the vehicle was listed for sale, we show how ProbSAINT can be used as a dynamic forecasting model for predicting price probabilities for different expected offer duration. Our experiments further indicate that ProbSAINT is especially accurate on instances where it is highly certain. This proves the applicability of its probabilistic predictions in real-world scenarios where trustworthiness is crucial.
A Modular Approach for Multimodal Summarization of TV Shows
Venue: arXiv cs.CL 2024
Year: 2024

In this paper we address the task of summarizing television shows, which touches key areas in AI research: complex reasoning, multiple modalities, and long narratives. We present a modular approach where separate components perform specialized sub-tasks which we argue affords greater flexibility compared to end-to-end methods. Our modules involve detecting scene boundaries, reordering scenes so as to minimize the number of cuts between different events, converting visual information to text, summarizing the dialogue in each scene, and fusing the scene summaries into a final summary for the entire episode. We also present a new metric, PRISMA (Precision and Recall EvaluatIon of Summary FActs), to measure both precision and recall of generated summaries, which we decompose into atomic facts. Tested on the recently released SummScreen3D dataset, our method produces higher quality summaries than comparison models, as measured with ROUGE and our new fact-based metric, and as assessed by human evaluators.
Feature Selection as Deep Sequential Generative Learning
Venue: arXiv cs.LG 2024
Year: 2024

Feature selection aims to identify the most pattern-discriminative feature subset. In prior literature, filter (e.g., backward elimination) and embedded (e.g., Lasso) methods have hyperparameters (e.g., top-K, score thresholding) and tie to specific models, thus, hard to generalize; wrapper methods search a feature subset in a huge discrete space and is computationally costly. To transform the way of feature selection, we regard a selected feature subset as a selection decision token sequence and reformulate feature selection as a deep sequential generative learning task that distills feature knowledge and generates decision sequences. Our method includes three steps: (1) We develop a deep variational transformer model over a joint of sequential reconstruction, variational, and performance evaluator losses. Our model can distill feature selection knowledge and learn a continuous embedding space to map feature selection decision sequences into embedding vectors associated with utility scores. (2) We leverage the trained feature subset utility evaluator as a gradient provider to guide the identification of the optimal feature subset embedding;(3) We decode the optimal feature subset embedding to autoregressively generate the best feature selection decision sequence with autostop. Extensive experimental results show this generative perspective is effective and generic, without large discrete search space and expert-specific hyperparameters.
KIWI: A Dataset of Knowledge-Intensive Writing Instructions for Answering Research Questions
Venue: arXiv cs.CL 2024
Year: 2024

Large language models (LLMs) adapted to follow user instructions are now widely deployed as conversational agents. In this work, we examine one increasingly common instruction-following task: providing writing assistance to compose a long-form answer. To evaluate the capabilities of current LLMs on this task, we construct KIWI, a dataset of knowledge-intensive writing instructions in the scientific domain. Given a research question, an initial model-generated answer and a set of relevant papers, an expert annotator iteratively issues instructions for the model to revise and improve its answer. We collect 1,260 interaction turns from 234 interaction sessions with three state-of-the-art LLMs. Each turn includes a user instruction, a model response, and a human evaluation of the model response. Through a detailed analysis of the collected responses, we find that all models struggle to incorporate new information into an existing answer, and to perform precise and unambiguous edits. Further, we find that models struggle to judge whether their outputs successfully followed user instructions, with accuracy at least 10 points short of human agreement. Our findings indicate that KIWI will be a valuable resource to measure progress and improve LLMs' instruction-following capabilities for knowledge intensive writing tasks.
Redefining cystoscopy with ai: bladder cancer diagnosis using an efficient hybrid cnn-transformer model
Venue: arXiv cs.CV 2024
Year: 2024

Bladder cancer ranks within the top 10 most diagnosed cancers worldwide and is among the most expensive cancers to treat due to the high recurrence rates which require lifetime follow-ups. The primary tool for diagnosis is cystoscopy, which heavily relies on doctors' expertise and interpretation. Therefore, annually, numerous cases are either undiagnosed or misdiagnosed and treated as urinary infections. To address this, we suggest a deep learning approach for bladder cancer detection and segmentation which combines CNNs with a lightweight positional-encoding-free transformer and dual attention gates that fuse self and spatial attention for feature enhancement. The architecture suggested in this paper is efficient making it suitable for medical scenarios that require real time inference. Experiments have proven that this model addresses the critical need for a balance between computational efficiency and diagnostic accuracy in cystoscopic imaging as despite its small size it rivals large models in performance.
FaaF: Facts as a Function for the evaluation of generated text
Venue: arXiv cs.CL 2024
Year: 2024

The demand for accurate and efficient verification of information in texts generated by large language models (LMs) is at an all-time high, but remains unresolved. Recent efforts have focused on extracting and verifying atomic facts from these texts via prompting LM evaluators. However, we demonstrate that this method of prompting is unreliable when faced with incomplete or inaccurate reference information. We introduce Facts as a Function (FaaF), a new approach to the fact verification task that leverages the function-calling capabilities of LMs. FaaF significantly enhances the ability of LMs to identify unsupported facts in texts, while also improving efficiency and significantly lowering costs compared to prompt-based methods. Additionally, we propose a framework for evaluating factual recall in Retrieval Augmented Generation (RAG) systems, which we employ to compare prompt-based and FaaF methods using various LMs under challenging conditions.