OpenRaiser/Intern-Atlas huggingface dataset:
The Bottom-Left Algorithm for the Strip Packing Problem
Venue: arXiv cs.DS 2024
Year: 2024

The bottom-left algorithm is a simple heuristic for the Strip Packing Problem. It places the rectangles in the given order at the lowest free position in the strip, using the left most position in case of ties. Despite its simplicity, the exact approximation ratio of the bottom-left algorithm remains unknown. We will improve the more-than-40-year-old value for the lower bound from $5/4$ to $4/3 - \varepsilon$. Additionally, we will show that this lower bound holds even in the special case of squares, where the previously known lower bound was $12/11 -\varepsilon$. These lower bounds apply regardless of the ordering of the rectangles. When squares are arranged in the worst possible order, we establish a constant upper bound and a $10/3-\varepsilon$ lower bound for the approximation ratio of the bottom-left algorithm. This bound also applies to some online setting and yields an almost tight result there. Finally, we show that the approximation ratio of a local search algorithm based on permuting rectangles in the ordering of the bottom-left algorithm is at least~$2$ and that such an algorithm may need an exponential number of improvement steps to reach a local optimum.
Speech as Interactive Design Material (SIDM): How to design and evaluate task-tailored synthetic voices?
Venue: arXiv cs.HC 2024
Year: 2024

The aim of this workshop is two-fold. First, it aims to establish a research community focused on design and evaluation of synthetic speech (TTS) interfaces that are tailored not only to goal oriented tasks (e.g., food ordering, online shopping) but also personal growth and resilience promoting applications (e.g., coaching, mindful reflection, and tutoring). Second, through discussion and collaborative efforts, to establish a set of practices and standards that will help to improve ecological validity of TTS evaluation. In particular, the workshop will explore the topics such as: interaction design of voice-based conversational interfaces; the interplay between prosodic aspects (e.g., pitch variance, loudness, jitter) of TTS and its impact on voice perception. This workshop will serve as a platform on which to build a community that is better equipped to tackle the dynamic field of interactive TTS interfaces, which remains understudied, yet increasingly pertinent to everyday lives of users.
Understanding the Dataset Practitioners Behind Large Language Model Development
Venue: arXiv cs.CL 2024
Year: 2024

As large language models (LLMs) become more advanced and impactful, it is increasingly important to scrutinize the data that they rely upon and produce. What is it to be a dataset practitioner doing this work? We approach this in two parts: first, we define the role of "dataset practitioners" by performing a retrospective analysis on the responsibilities of teams contributing to LLM development at a technology company, Google. Then, we conduct semi-structured interviews with a cross-section of these practitioners (N=10). We find that although data quality is a top priority, there is little consensus around what data quality is and how to evaluate it. Consequently, practitioners either rely on their own intuition or write custom code to evaluate their data. We discuss potential reasons for this phenomenon and opportunities for alignment.
ESG Sentiment Analysis: comparing human and language model performance including GPT
Venue: arXiv cs.CL 2024
Year: 2024

In this paper we explore the challenges of measuring sentiment in relation to Environmental, Social and Governance (ESG) social media. ESG has grown in importance in recent years with a surge in interest from the financial sector and the performance of many businesses has become based in part on their ESG related reputations. The use of sentiment analysis to measure ESG related reputation has developed and with it interest in the use of machines to do so. The era of digital media has created an explosion of new media sources, driven by the growth of social media platforms. This growing data environment has become an excellent source for behavioural insight studies across many disciplines that includes politics, healthcare and market research. Our study seeks to compare human performance with the cutting edge in machine performance in the measurement of ESG related sentiment. To this end researchers classify the sentiment of 150 tweets and a reliability measure is made. A gold standard data set is then established based on the consensus of 3 researchers and this data set is then used to measure the performance of different machine approaches: one based on the VADER dictionary approach to sentiment classification and then multiple language model approaches, including Llama2, T5, Mistral, Mixtral, FINBERT, GPT3.5 and GPT4.
Enhancing Continuous Domain Adaptation with Multi-Path Transfer Curriculum
Venue: arXiv cs.LG 2024
Year: 2024

Addressing the large distribution gap between training and testing data has long been a challenge in machine learning, giving rise to fields such as transfer learning and domain adaptation. Recently, Continuous Domain Adaptation (CDA) has emerged as an effective technique, closing this gap by utilizing a series of intermediate domains. This paper contributes a novel CDA method, W-MPOT, which rigorously addresses the domain ordering and error accumulation problems overlooked by previous studies. Specifically, we construct a transfer curriculum over the source and intermediate domains based on Wasserstein distance, motivated by theoretical analysis of CDA. Then we transfer the source model to the target domain through multiple valid paths in the curriculum using a modified version of continuous optimal transport. A bidirectional path consistency constraint is introduced to mitigate the impact of accumulated mapping errors during continuous transfer. We extensively evaluate W-MPOT on multiple datasets, achieving up to 54.1\% accuracy improvement on multi-session Alzheimer MR image classification and 94.7\% MSE reduction on battery capacity estimation.
Automated Floodwater Depth Estimation Using Large Multimodal Model for Rapid Flood Mapping
Venue: arXiv cs.CV 2024
Year: 2024

Information on the depth of floodwater is crucial for rapid mapping of areas affected by floods. However, previous approaches for estimating floodwater depth, including field surveys, remote sensing, and machine learning techniques, can be time-consuming and resource-intensive. This paper presents an automated and fast approach for estimating floodwater depth from on-site flood photos. A pre-trained large multimodal model, GPT-4 Vision, was used specifically for estimating floodwater. The input data were flooding photos that contained referenced objects, such as street signs, cars, people, and buildings. Using the heights of the common objects as references, the model returned the floodwater depth as the output. Results show that the proposed approach can rapidly provide a consistent and reliable estimation of floodwater depth from flood photos. Such rapid estimation is transformative in flood inundation mapping and assessing the severity of the flood in near-real time, which is essential for effective flood response strategies.
Towards Empirical Interpretation of Internal Circuits and Properties in Grokked Transformers on Modular Polynomials
Venue: arXiv cs.LG 2024
Year: 2024

Grokking has been actively explored to reveal the mystery of delayed generalization and identifying interpretable representations and algorithms inside the grokked models is a suggestive hint to understanding its mechanism. Grokking on modular addition has been known to implement Fourier representation and its calculation circuits with trigonometric identities in Transformers. Considering the periodicity in modular arithmetic, the natural question is to what extent these explanations and interpretations hold for the grokking on other modular operations beyond addition. For a closer look, we first hypothesize that any modular operations can be characterized with distinctive Fourier representation or internal circuits, grokked models obtain common features transferable among similar operations, and mixing datasets with similar operations promotes grokking. Then, we extensively examine them by learning Transformers on complex modular arithmetic tasks, including polynomials. Our Fourier analysis and novel progress measure for modular arithmetic, Fourier Frequency Density and Fourier Coefficient Ratio, characterize distinctive internal representations of grokked models per modular operation; for instance, polynomials often result in the superposition of the Fourier components seen in elementary arithmetic, but clear patterns do not emerge in challenging non-factorizable polynomials. In contrast, our ablation study on the pre-grokked models reveals that the transferability among the models grokked with each operation can be only limited to specific combinations, such as from elementary arithmetic to linear expressions. Moreover, some multi-task mixtures may lead to co-grokking -- where grokking simultaneously happens for all the tasks -- and accelerate generalization, while others may not find optimal solutions. We provide empirical steps towards the interpretability of internal circuits.
Towards Bridging the Gap between Near and Far-Field Characterizations of the Wireless Channel
Venue: arXiv cs.IT 2024
Year: 2024

The "near-field" propagation modeling of wireless channels is necessary to support sixth-generation (6G) technologies, such as intelligent reflecting surface (IRS), that are enabled by large aperture antennas and higher frequency carriers. As the conventional far-field model proves inadequate in this context, there is a pressing need to explore and bridge the gap between near and far-field propagation models. Although far-field models are simple and provide computationally efficient solutions for many practical applications, near-field models provide the most accurate representation of wireless channels. This paper builds upon the foundations of electromagnetic wave propagation theory to derive near and far-field models as approximations of the Green's function (Maxwell's equations). We characterize the near and far-field models both theoretically and with the help of simulations in a line-of-sight (LOS)-only scenario. In particular, for two key applications in multiantenna systems, namely, beamforming and multiple-access, we showcase the advantages of using the near-field model over the far-field, and present a novel scheduling scheme for multiple-access in the near-field regime. Our findings offer insights into the challenge of incorporating near-field models in practical wireless systems, fostering enhanced performance in future communication technologies.
On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective
Venue: arXiv cs.LG 2024
Year: 2024

In this paper, we provide lower bounds for Differentially Private (DP) Online Learning algorithms. Our result shows that, for a broad class of $(\varepsilon,δ)$-DP online algorithms, for number of rounds $T$ such that $\log T\leq O(1 / δ)$, the expected number of mistakes incurred by the algorithm grows as $Ω(\log \frac{T}δ)$. This matches the upper bound obtained by Golowich and Livni (2021) and is in contrast to non-private online learning where the number of mistakes is independent of $T$. To the best of our knowledge, our work is the first result towards settling lower bounds for DP-Online learning and partially addresses the open question in Sanyal and Ramponi (2022).
A Survey on Data Selection for Language Models
Venue: arXiv cs.CL 2024
Year: 2024

A major factor in the recent success of large language models is the use of enormous and ever-growing text datasets for unsupervised pre-training. However, naively training a model on all available data may not be optimal (or feasible), as the quality of available text data can vary. Filtering out data can also decrease the carbon footprint and financial costs of training models by reducing the amount of training required. Data selection methods aim to determine which candidate data points to include in the training dataset and how to appropriately sample from the selected data points. The promise of improved data selection methods has caused the volume of research in the area to rapidly expand. However, because deep learning is mostly driven by empirical evidence and experimentation on large-scale data is expensive, few organizations have the resources for extensive data selection research. Consequently, knowledge of effective data selection practices has become concentrated within a few organizations, many of which do not openly share their findings and methodologies. To narrow this gap in knowledge, we present a comprehensive review of existing literature on data selection methods and related research areas, providing a taxonomy of existing approaches. By describing the current landscape of research, this work aims to accelerate progress in data selection by establishing an entry point for new and established researchers. Additionally, throughout this review we draw attention to noticeable holes in the literature and conclude the paper by proposing promising avenues for future research.
Computation Rate Maximization for Wireless Powered Edge Computing With Multi-User Cooperation
Venue: arXiv cs.IT 2024
Year: 2024

The combination of mobile edge computing (MEC) and radio frequency-based wireless power transfer (WPT) presents a promising technique for providing sustainable energy supply and computing services at the network edge. This study considers a wireless-powered mobile edge computing system that includes a hybrid access point (HAP) equipped with a computing unit and multiple Internet of Things (IoT) devices. In particular, we propose a novel muti-user cooperation scheme to improve computation performance, where collaborative clusters are dynamically formed. Each collaborative cluster comprises a source device (SD) and an auxiliary device (AD), where the SD can partition the computation task into various segments for local processing, offloading to the HAP, and remote execution by the AD with the assistance of the HAP. Specifically, we aims to maximize the weighted sum computation rate (WSCR) of all the IoT devices in the network. This involves jointly optimizing collaboration, time and data allocation among multiple IoT devices and the HAP, while considering the energy causality property and the minimum data processing requirement of each device. Initially, an optimization algorithm based on the interior-point method is designed for time and data allocation. Subsequently, a priority-based iterative algorithm is developed to search for a near-optimal solution to the multi-user collaboration scheme. Finally, a deep learning-based approach is devised to further accelerate the algorithm's operation, building upon the initial two algorithms. Simulation results show that the performance of the proposed algorithms is comparable to that of the exhaustive search method, and the deep learning-based algorithm significantly reduces the execution time of the algorithm.
Bike3S: A Tool for Bike Sharing Systems Simulation
Venue: arXiv cs.MA 2024
Year: 2024

Vehicle sharing systems are becoming increasingly popular. The effectiveness of such systems depends, among other factors, on different strategic and operational management decisions and policies, like the dimension of the fleet or the distribution of vehicles. It is of foremost importance to be able to anticipate and evaluate the potential effects of such strategies before they can be successfully deployed. In this paper we present Bike3S, a simulator for a station-based bike sharing system. The simulator performs semi-realistic simulations of the operation of a bike sharing system and allows for evaluating and testing different management decisions and strategies. In particular, the simulator has been designed to test different station capacities, station distributions, and balancing strategies. The simulator carries out microscopic agent-based simulations, where users of different types can be defined that act according to their individual goals and objectives which influences the overall dynamics of the whole system.
NFT1000: A Cross-Modal Dataset for Non-Fungible Token Retrieval
Venue: arXiv cs.IR 2024
Year: 2024

With the rise of "Metaverse" and "Web 3.0", Non-Fungible Token (NFT) has emerged as a kind of pivotal digital asset, garnering significant attention. By the end of March 2024, more than 1.7 billion NFTs have been minted across various blockchain platforms. To effectively locate a desired NFT, conducting searches within a vast array of NFTs is essential. The challenge in NFT retrieval is heightened due to the high degree of similarity among different NFTs, regarding regional and semantic aspects. In this paper, we will introduce a benchmark dataset named "NFT Top1000 Visual-Text Dataset" (NFT1000), containing 7.56 million image-text pairs, and being collected from 1000 most famous PFP1 NFT collections2 by sales volume on the Ethereum blockchain. Based on this dataset and leveraging the CLIP series of pre-trained models as our foundation, we propose the dynamic masking fine-tuning scheme. This innovative approach results in a 7.4\% improvement in the top1 accuracy rate, while utilizing merely 13\% of the total training data (0.79 million vs. 6.1 million). We also propose a robust metric Comprehensive Variance Index (CVI) to assess the similarity and retrieval difficulty of visual-text pairs data. The dataset will be released as an open-source resource. For more details, please refer to: https://github.com/ShuxunoO/NFT-Net.git.
Can we predict QPP? An approach based on multivariate outliers
Venue: arXiv cs.IR 2024
Year: 2024

Query performance prediction (QPP) aims to forecast the effectiveness of a search engine across a range of queries and documents. While state-of-the-art predictors offer a certain level of precision, their accuracy is not flawless. Prior research has recognized the challenges inherent in QPP but often lacks a thorough qualitative analysis. In this paper, we delve into QPP by examining the factors that influence the predictability of query performance accuracy. We propose the working hypothesis that while some queries are readily predictable, others present significant challenges. By focusing on outliers, we aim to identify the queries that are particularly challenging to predict. To this end, we employ multivariate outlier detection method. Our results demonstrate the effectiveness of this approach in identifying queries on which QPP do not perform well, yielding less reliable predictions. Moreover, we provide evidence that excluding these hard-to-predict queries from the analysis significantly enhances the overall accuracy of QPP.
m2mKD: Module-to-Module Knowledge Distillation for Modular Transformers
Venue: arXiv cs.LG 2024
Year: 2024

Modular neural architectures are gaining attention for their powerful generalization and efficient adaptation to new domains. However, training these models poses challenges due to optimization difficulties arising from intrinsic sparse connectivity. Leveraging knowledge from monolithic models through techniques like knowledge distillation can facilitate training and enable integration of diverse knowledge. Nevertheless, conventional knowledge distillation approaches are not tailored to modular models and struggle with unique architectures and enormous parameter counts. Motivated by these challenges, we propose module-to-module knowledge distillation (m2mKD) for transferring knowledge between modules. m2mKD combines teacher modules of a pretrained monolithic model and student modules of a modular model with a shared meta model respectively to encourage the student module to mimic the behaviour of the teacher module. We evaluate m2mKD on two modular neural architectures: Neural Attentive Circuits (NACs) and Vision Mixture-of-Experts (V-MoE). Applying m2mKD to NACs yields significant improvements in IID accuracy on Tiny-ImageNet (up to 5.6%) and OOD robustness on Tiny-ImageNet-R (up to 4.2%). Additionally, the V-MoE-Base model trained with m2mKD achieves 3.5% higher accuracy than end-to-end training on ImageNet-1k. Code is available at https://github.com/kamanphoebe/m2mKD.
LangGPT: Rethinking Structured Reusable Prompt Design Framework for LLMs from the Programming Language
Venue: arXiv cs.SE 2024
Year: 2024

LLMs have demonstrated commendable performance across diverse domains. Nevertheless, formulating high-quality prompts to instruct LLMs proficiently poses a challenge for non-AI experts. Existing research in prompt engineering suggests somewhat scattered optimization principles and designs empirically dependent prompt optimizers. Unfortunately, these endeavors lack a structured design template, incurring high learning costs and resulting in low reusability. In addition, it is not conducive to the iterative updating of prompts. Inspired by structured reusable programming languages, we propose LangGPT, a dual-layer prompt design framework as the programming language for LLMs. LangGPT has an easy-to-learn normative structure and provides an extended structure for migration and reuse. Experiments illustrate that LangGPT significantly enhances the performance of LLMs. Moreover, the case study shows that LangGPT leads LLMs to generate higher-quality responses. Furthermore, we analyzed the ease of use and reusability of LangGPT through a user survey in our online community.
Incremental Concept Formation over Visual Images Without Catastrophic Forgetting
Venue: arXiv cs.LG 2024
Year: 2024

Deep neural networks have excelled in machine learning, particularly in vision tasks, however, they often suffer from catastrophic forgetting when learning new tasks sequentially. In this work, we introduce Cobweb4V, an alternative to traditional neural network approaches. Cobweb4V is a novel visual classification method that builds on Cobweb, a human like learning system that is inspired by the way humans incrementally learn new concepts over time. In this research, we conduct a comprehensive evaluation, showcasing Cobweb4Vs proficiency in learning visual concepts, requiring less data to achieve effective learning outcomes compared to traditional methods, maintaining stable performance over time, and achieving commendable asymptotic behavior, without catastrophic forgetting effects. These characteristics align with learning strategies in human cognition, positioning Cobweb4V as a promising alternative to neural network approaches.