OpenRaiser/Intern-Atlas huggingface dataset:
Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
Venue: arXiv cs.DS 2024
Year: 2024

Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text $T$ of length $n$, a pattern $P$ of length $m$, and a threshold $k$, the task is to identify the fragments of $T$ that are at distance at most $k$ to $P$. We consider the two most common distances: Hamming distance (the number of character substitutions) in Pattern Matching with Mismatches and edit distance (the minimum number of character insertions, deletions, and substitutions) in Pattern Matching with Edits. We revisit the complexity of these two problems in the quantum setting. Our recent work [STOC'24] shows that $\hat{O}(\sqrt{nk})$ quantum queries are sufficient to solve (the decision version of) Pattern Matching with Edits. However, the quantum time complexity of the underlying solution does not provide any improvement over classical computation. On the other hand, the state-of-the-art algorithm for Pattern Matching with Mismatches [Jin and Nogler; SODA'23] achieves query complexity $\hat{O}(\sqrt{nk^{3/2}})$ and time complexity $\tilde{O}(\sqrt{nk^2})$, falling short of an unconditional lower bound of $Ω(\sqrt{nk})$ queries. In this work, we present quantum algorithms with a time complexity of $\tilde{O}(\sqrt{nk}+\sqrt{n/m}\cdot k^2)$ for Pattern Matching with Mismatches and $\hat{O}(\sqrt{nk}+\sqrt{n/m}\cdot k^{3.5})$ for Pattern Matching with Edits; both solutions use $\hat{O}(\sqrt{nk})$ queries. The running times are near-optimal for $k\ll m^{1/3}$ and $k\ll m^{1/6}$, respectively, and offer advantage over classical algorithms for $k\ll (mn)^{1/4}$ and $k\ll (mn)^{1/7}$, respectively. Our solutions can also report the starting positions of approximate occurrences of $P$ in $T$ (represented as collections of arithmetic progressions); in this case, the unconditional lower bound and the complexities of our algorithms increase by a $Θ(\sqrt{n/m})$ factor.
An Improved Approach for Cardiac MRI Segmentation based on 3D UNet Combined with Papillary Muscle Exclusion
Venue: arXiv cs.CV 2024
Year: 2024

Left ventricular ejection fraction (LVEF) is the most important clinical parameter of cardiovascular function. The accuracy in estimating this parameter is highly dependent upon the precise segmentation of the left ventricle (LV) structure at the end diastole and systole phases. Therefore, it is crucial to develop robust algorithms for the precise segmentation of the heart structure during different phases. Methodology: In this work, an improved 3D UNet model is introduced to segment the myocardium and LV, while excluding papillary muscles, as per the recommendation of the Society for Cardiovascular Magnetic Resonance. For the practical testing of the proposed framework, a total of 8,400 cardiac MRI images were collected and analysed from the military hospital in Tunis (HMPIT), as well as the popular ACDC public dataset. As performance metrics, we used the Dice coefficient and the F1 score for validation/testing of the LV and the myocardium segmentation. Results: The data was split into 70%, 10%, and 20% for training, validation, and testing, respectively. It is worth noting that the proposed segmentation model was tested across three axis views: basal, medio basal and apical at two different cardiac phases: end diastole and end systole instances. The experimental results showed a Dice index of 0.965 and 0.945, and an F1 score of 0.801 and 0.799, at the end diastolic and systolic phases, respectively. Additionally, clinical evaluation outcomes revealed a significant difference in the LVEF and other clinical parameters when the papillary muscles were included or excluded.
Unary counting quantifiers do not increase the expressive power of Presburger aritmetic: an alternative shorter proof
Venue: arXiv cs.LO 2024
Year: 2024

This work was presented in June 5-7, 2017 at the conference "Journées sur les Arithmétiques Faibles -- Weak Arithmetics Days" held in Saint-Pertersburg of which no proceeding was ever published. It was not a new result but showed that a different approach is possible. The paper presented at ICALP 2024 addresses, among other problems, the complexity issues which were ignored in my 2017 talk.
Evaluating Model Performance with Hard-Swish Activation Function Adjustments
Venue: arXiv cs.CV 2024
Year: 2024

In the field of pattern recognition, achieving high accuracy is essential. While training a model to recognize different complex images, it is vital to fine-tune the model to achieve the highest accuracy possible. One strategy for fine-tuning a model involves changing its activation function. Most pre-trained models use ReLU as their default activation function, but switching to a different activation function like Hard-Swish could be beneficial. This study evaluates the performance of models using ReLU, Swish and Hard-Swish activation functions across diverse image datasets. Our results show a 2.06% increase in accuracy for models on the CIFAR-10 dataset and a 0.30% increase in accuracy for models on the ATLAS dataset. Modifying the activation functions in architecture of pre-trained models lead to improved overall accuracy.
FltLM: An Intergrated Long-Context Large Language Model for Effective Context Filtering and Understanding
Venue: arXiv cs.CL 2024
Year: 2024

The development of Long-Context Large Language Models (LLMs) has markedly advanced natural language processing by facilitating the process of textual data across long documents and multiple corpora. However, Long-Context LLMs still face two critical challenges: The lost in the middle phenomenon, where crucial middle-context information is likely to be missed, and the distraction issue that the models lose focus due to overly extended contexts. To address these challenges, we propose the Context Filtering Language Model (FltLM), a novel integrated Long-Context LLM which enhances the ability of the model on multi-document question-answering (QA) tasks. Specifically, FltLM innovatively incorporates a context filter with a soft mask mechanism, identifying and dynamically excluding irrelevant content to concentrate on pertinent information for better comprehension and reasoning. Our approach not only mitigates these two challenges, but also enables the model to operate conveniently in a single forward pass. Experimental results demonstrate that FltLM significantly outperforms supervised fine-tuning and retrieval-based methods in complex QA scenarios, suggesting a promising solution for more accurate and reliable long-context natural language understanding applications.
Generative Model for Less-Resourced Language with 1 billion parameters
Venue: arXiv cs.CL 2024
Year: 2024

Large language models (LLMs) are a basic infrastructure for modern natural language processing. Many commercial and open-source LLMs exist for English, e.g., ChatGPT, Llama, Falcon, and Mistral. As these models are trained on mostly English texts, their fluency and knowledge of low-resource languages and societies are superficial. We present the development of large generative language models for a less-resourced language. GaMS 1B - Generative Model for Slovene with 1 billion parameters was created by continuing pretraining of the existing English OPT model. We developed a new tokenizer adapted to Slovene, Croatian, and English languages and used embedding initialization methods FOCUS and WECHSEL to transfer the embeddings from the English OPT model. We evaluate our models on several classification datasets from the Slovene suite of benchmarks and generative sentence simplification task SENTA. We only used a few-shot in-context learning of our models, which are not yet instruction-tuned. For classification tasks, in this mode, the generative models lag behind the existing Slovene BERT-type models fine-tuned for specific tasks. On a sentence simplification task, the GaMS models achieve comparable or better performance than the GPT-3.5-Turbo model.
Combining Planning and Diffusion for Mobility with Unknown Dynamics
Venue: arXiv cs.RO 2024
Year: 2024

Manipulation of large objects over long horizons (such as carts in a warehouse) is an essential skill for deployable robotic systems. Large objects require mobile manipulation which involves simultaneous manipulation, navigation, and movement with the object in tow. In many real-world situations, object dynamics are incredibly complex, such as the interaction of an office chair (with a rotating base and five caster wheels) and the ground. We present a hierarchical algorithm for long-horizon robot manipulation problems in which the dynamics are partially unknown. We observe that diffusion-based behavior cloning is highly effective for short-horizon problems with unknown dynamics, so we decompose the problem into an abstract high-level, obstacle-aware motion-planning problem that produces a waypoint sequence. We use a short-horizon, relative-motion diffusion policy to achieve the waypoints in sequence. We train mobile manipulation policies on a Spot robot that has to push and pull an office chair. Our hierarchical manipulation policy performs consistently better, especially when the horizon increases, compared to a diffusion policy trained on long-horizon demonstrations or motion planning assuming a rigidly-attached object (success rate of 8 (versus 0 and 5 respectively) out of 10 runs). Importantly, our learned policy generalizes to new layouts, grasps, chairs, and flooring that induces more friction, without any further training, showing promise for other complex mobile manipulation problems. Project Page: https://yravan.github.io/plannerorderedpolicy/
AutoFeedback: An LLM-based Framework for Efficient and Accurate API Request Generation
Venue: arXiv cs.SE 2024
Year: 2024

Large Language Models (LLMs) leverage external tools primarily through generating the API request to enhance task completion efficiency. The accuracy of API request generation significantly determines the capability of LLMs to accomplish tasks. Due to the inherent hallucinations within the LLM, it is difficult to efficiently and accurately generate the correct API request. Current research uses prompt-based feedback to facilitate the LLM-based API request generation. However, existing methods lack factual information and are insufficiently detailed. To address these issues, we propose AutoFeedback, an LLM-based framework for efficient and accurate API request generation, with a Static Scanning Component (SSC) and a Dynamic Analysis Component (DAC). SSC incorporates errors detected in the API requests as pseudo-facts into the feedback, enriching the factual information. DAC retrieves information from API documentation, enhancing the level of detail in feedback. Based on this two components, Autofeedback implementes two feedback loops during the process of generating API requests by the LLM. Extensive experiments demonstrate that it significantly improves accuracy of API request generation and reduces the interaction cost. AutoFeedback achieves an accuracy of 100.00\% on a real-world API dataset and reduces the cost of interaction with GPT-3.5 Turbo by 23.44\%, and GPT-4 Turbo by 11.85\%.
Constrained TLBO algorithm for lightweight cable-stiffened scissor-like deployable structures
Venue: arXiv cs.CE 2024
Year: 2024

Present works discusses the efficient structural analysis and weight optimization of the cable-stiffened deployable structures. The stiffening effect of cables is incorporated through a matrix analysis based iterative strategy to identify the active and passive cables. The structural form can be easily deployed to cartesian as well as polar coordinates through the arrangement of duplet members. The large span utility of cable stiffened bar members can pose challenges to the deployability due to increased weight. A novel teaching-learning based optimization (TLBO) algorithm is utilized to optimize the overall weight of the structure through efficient section designs with proper constraint on the yield criteria. The penalty function approach is adopted to identify the unfeasible designs. A number of example cases are analysed and comparison is presented with the existing literature to show the suitability of the proposed approach. Finally, a new form of three-dimensional deployable structure is proposed. It is seen that such deployable structure can be accurately analysed using the iterative matrix analysis approach and efficiently optimized using the present algorithm.
Self-Boosting Large Language Models with Synthetic Preference Data
Venue: arXiv cs.CL 2024
Year: 2024

Through alignment with human preferences, Large Language Models (LLMs) have advanced significantly in generating honest, harmless, and helpful responses. However, collecting high-quality preference data is a resource-intensive and creativity-demanding process, especially for the continual improvement of LLMs. We introduce SynPO, a self-boosting paradigm that leverages synthetic preference data for model alignment. SynPO employs an iterative mechanism wherein a self-prompt generator creates diverse prompts, and a response improver refines model responses progressively. This approach trains LLMs to autonomously learn the generative rewards for their own outputs and eliminates the need for large-scale annotation of prompts and human preferences. After four SynPO iterations, Llama3-8B and Mistral-7B show significant enhancements in instruction-following abilities, achieving over 22.1% win rate improvements on AlpacaEval 2.0 and ArenaHard. Simultaneously, SynPO improves the general performance of LLMs on various tasks, validated by a 3.2 to 5.0 average score increase on the well-recognized Open LLM leaderboard.
DLGNet: Hyperedge Classification through Directed Line Graphs for Chemical Reactions
Venue: arXiv cs.LG 2024
Year: 2024

Graphs and hypergraphs provide powerful abstractions for modeling interactions among a set of entities of interest and have been attracting a growing interest in the literature thanks to many successful applications in several fields. In particular, they are rapidly expanding in domains such as chemistry and biology, especially in the areas of drug discovery and molecule generation. One of the areas witnessing the fasted growth is the chemical reactions field, where chemical reactions can be naturally encoded as directed hyperedges of a hypergraph. In this paper, we address the chemical reaction classification problem by introducing the notation of a Directed Line Graph (DGL) associated with a given directed hypergraph. On top of it, we build the Directed Line Graph Network (DLGNet), the first spectral-based Graph Neural Network (GNN) expressly designed to operate on a hypergraph via its DLG transformation. The foundation of DLGNet is a novel Hermitian matrix, the Directed Line Graph Laplacian, which compactly encodes the directionality of the interactions taking place within the directed hyperedges of the hypergraph thanks to the DLG representation. The Directed Line Graph Laplacian enjoys many desirable properties, including admitting an eigenvalue decomposition and being positive semidefinite, which make it well-suited for its adoption within a spectral-based GNN. Through extensive experiments on chemical reaction datasets, we show that DGLNet significantly outperforms the existing approaches, achieving on a collection of real-world datasets an average relative-percentage-difference improvement of 33.01%, with a maximum improvement of 37.71%.
Mechanism Design for Exchange Markets
Venue: arXiv cs.GT 2024
Year: 2024

Exchange markets are a significant type of market economy, in which each agent holds a budget and certain (divisible) resources available for trading. Most research on equilibrium in exchange economies is based on an environment of completely free competition. However, the orderly operation of markets also relies on effective economic regulatory mechanisms. This paper initiates the study of the mechanism design problem in exchange markets, exploring the potential to establish truthful market rules and mechanisms. This task poses a significant challenge as unlike auctioneers in auction design, the mechanism designer in exchange markets lacks centralized authority to fully control the allocation of resources. In this paper, the mechanism design problem is formalized as a two-stage game. In stage 1, agents submit their private information to the manager, who then formulates market trading rules based on the submitted information. In stage 2, agents are free to engage in transactions within these rules, ultimately reaching an equilibrium. We generalize the concept of liquid welfare from classical budget-feasible auctions and use market liquid welfare as a measure to evaluate the performance of the designed mechanism. Moreover, an extra concept called profitability is introduced to assess whether the market is money-making (profitable) or money-losing (unprofitable). Our goal is to design a truthful mechanism that achieves an (approximate) optimal welfare while minimizing unprofitability as much as possible. Two mechanisms for the problem are proposed. The first one guarantees truthfulness and profitability while approaching an approximation ratio of 1/2 in large markets. The second one is also truthful and achieves 1/2 approximation in general markets but incurs bounded unprofitability. Our aim is for both mechanisms to provide valuable insights into the truthful market design problem.
Clean Evaluations on Contaminated Visual Language Models
Venue: arXiv cs.CV 2024
Year: 2024

How to evaluate large language models (LLMs) cleanly has been established as an important research era to genuinely report the performance of possibly contaminated LLMs. Yet, how to cleanly evaluate the visual language models (VLMs) is an under-studied problem. We propose a novel approach to achieve such goals through data augmentation methods on the visual input information. We then craft a new visual clean evaluation benchmark with thousands of data instances. Through extensive experiments, we found that the traditional visual data augmentation methods are useful, but they are at risk of being used as a part of the training data as a workaround. We further propose using BGR augmentation to switch the colour channel of the visual information. We found that it is a simple yet effective method for reducing the effect of data contamination and fortunately, it is also harmful to be used as a data augmentation method during training. It means that it is hard to integrate such data augmentation into training by malicious trainers and it could be a promising technique to cleanly evaluate visual LLMs. Our code, data, and model weights will be released upon publication.
InAttention: Linear Context Scaling for Transformers
Venue: arXiv cs.LG 2024
Year: 2024

VRAM requirements for transformer models scale quadratically with context length due to the self-attention mechanism. In this paper we modify the decoder-only transformer, replacing self-attention with InAttention, which scales linearly with context length during inference by having tokens attend only to initial states. Benchmarking shows that InAttention significantly reduces VRAM usage during inference, enabling handling of long sequences on consumer GPUs. We corroborate that fine-tuning extends context length efficiently, improving performance on long sequences without high training costs. InAttention offers a scalable solution for long-range dependencies in transformer models, paving the way for further optimization.
ReIFE: Re-evaluating Instruction-Following Evaluation
Venue: arXiv cs.CL 2024
Year: 2024

The automatic evaluation of instruction following typically involves using large language models (LLMs) to assess response quality. However, there is a lack of comprehensive evaluation of these LLM-based evaluators across two dimensions: the base LLMs and the evaluation protocols. Therefore, we present a thorough meta-evaluation of instruction following, including 25 base LLMs and 15 recently proposed evaluation protocols, on 4 human-annotated datasets, assessing the evaluation accuracy of the LLM-evaluators. Our evaluation allows us to identify the best-performing base LLMs and evaluation protocols with a high degree of robustness. Moreover, our large-scale evaluation reveals: (1) Base LLM performance ranking remains largely consistent across evaluation protocols, with less capable LLMs showing greater improvement from protocol enhancements; (2) Robust evaluation of evaluation protocols requires many base LLMs with varying capability levels, as protocol effectiveness can depend on the base LLM used; (3) Evaluation results on different datasets are not always consistent, so a rigorous evaluation requires multiple datasets with distinctive features. We release our meta-evaluation suite ReIFE, which provides the codebase and evaluation result collection for more than 500 LLM-evaluator configurations, to support future research in instruction-following evaluation.
FlowBotHD: History-Aware Diffuser Handling Ambiguities in Articulated Objects Manipulation
Venue: arXiv cs.RO 2024
Year: 2024

We introduce a novel approach for manipulating articulated objects which are visually ambiguous, such doors which are symmetric or which are heavily occluded. These ambiguities can cause uncertainty over different possible articulation modes: for instance, when the articulation direction (e.g. push, pull, slide) or location (e.g. left side, right side) of a fully closed door are uncertain, or when distinguishing features like the plane of the door are occluded due to the viewing angle. To tackle these challenges, we propose a history-aware diffusion network that can model multi-modal distributions over articulation modes for articulated objects; our method further uses observation history to distinguish between modes and make stable predictions under occlusions. Experiments and analysis demonstrate that our method achieves state-of-art performance on articulated object manipulation and dramatically improves performance for articulated objects containing visual ambiguities. Our project website is available at https://flowbothd.github.io/.
Transforming disaster risk reduction with AI and big data: Legal and interdisciplinary perspectives
Venue: arXiv cs.CY 2024
Year: 2024

Managing complex disaster risks requires interdisciplinary efforts. Breaking down silos between law, social sciences, and natural sciences is critical for all processes of disaster risk reduction. This enables adaptive systems for the rapid evolution of AI technology, which has significantly impacted the intersection of law and natural environments. Exploring how AI influences legal frameworks and environmental management, while also examining how legal and environmental considerations can confine AI within the socioeconomic domain, is essential. From a co-production review perspective, drawing on insights from lawyers, social scientists, and environmental scientists, principles for responsible data mining are proposed based on safety, transparency, fairness, accountability, and contestability. This discussion offers a blueprint for interdisciplinary collaboration to create adaptive law systems based on AI integration of knowledge from environmental and social sciences. Discrepancies in the use of language between environmental scientists and decision-makers in terms of usefulness and accuracy hamper how AI can be used based on the principles of legal considerations for a safe, trustworthy, and contestable disaster management framework. When social networks are useful for mitigating disaster risks based on AI, the legal implications related to privacy and liability of the outcomes of disaster management must be considered. Fair and accountable principles emphasise environmental considerations and foster socioeconomic discussions related to public engagement. AI also has an important role to play in education, bringing together the next generations of law, social sciences, and natural sciences to work on interdisciplinary solutions in harmony.