OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Data Layout Optimization with Worst-case Guarantees
Venue: arXiv cs.DB 2024
Year: 2024

Many data analytics systems store and process large datasets in partitions containing millions of rows. By mapping rows to partitions in an optimized way, it is possible to improve query performance by skipping over large numbers of irrelevant partitions during query processing. This mapping is referred to as a data layout. Recent works have shown that customizing the data layout to the anticipated query workload greatly improves query performance, but the performance benefits may disappear if the workload changes. Reorganizing data layouts to accommodate workload drift can resolve this issue, but reorganization costs could exceed query savings if not done carefully. In this paper, we present an algorithmic framework OReO that makes online reorganization decisions to balance the benefits of improved query performance with the costs of reorganization. Our framework extends results from Metrical Task Systems to provide a tight bound on the worst-case performance guarantee for online reorganization, without prior knowledge of the query workload. Through evaluation on real-world datasets and query workloads, our experiments demonstrate that online reorganization with OReO can lead to an up to 32% improvement in combined query and reorganization time compared to using a single, optimized data layout for the entire workload.
Axiomatization of approximate exclusion
Venue: arXiv cs.LO 2024
Year: 2024

We define and axiomatize approximate exclusion atoms in the team semantic setting. A team is a set of assignments, which can be seen as a mathematical model of a uni-relational database, and we say that an approximate exclusion atom is satisfied in a team if the corresponding usual exclusion atom is satisfied in a large enough subteam. We consider the implication problem for approximate exclusion atoms and show that it is axiomatizable for consequences with a degree of approximation that is not too large. We prove the completeness theorem for usual exclusion atoms, which is currently missing from the literature, and generalize it to approximate exclusion atoms. We also provide a polynomial time algorithm for the implication problems. The results also apply to exclusion dependencies in database theory.
6G Software Engineering: A Systematic Mapping Study
Venue: arXiv cs.SE 2024
Year: 2024

6G will revolutionize the software world allowing faster cellular communications and a massive number of connected devices. 6G will enable a shift towards a continuous edge-to-cloud architecture. Current cloud solutions, where all the data is transferred and computed in the cloud, are not sustainable in such a large network of devices. Current technologies, including development methods, software architectures, and orchestration and offloading systems, still need to be prepared to cope with such requirements. In this paper, we conduct a Systematic Mapping Study to investigate the current research status of 6G Software Engineering. Results show that 18 research papers have been proposed in software process, software architecture, orchestration and offloading methods. Of these, software architecture and software-defined networks are respectively areas and topics that have received the most attention in 6G Software Engineering. In addition, the main types of results of these papers are methods, architectures, platforms, frameworks and algorithms. For the five tools/frameworks proposed, they are new and not currently studied by other researchers. The authors of these findings are mainly from China, India and Saudi Arabia. The results will enable researchers and practitioners to further research and extend for 6G Software Engineering.
Concerns on Bias in Large Language Models when Creating Synthetic Personae
Venue: arXiv cs.HC 2024
Year: 2024

This position paper explores the benefits, drawbacks, and ethical considerations of incorporating synthetic personae in HCI research, particularly focusing on the customization challenges beyond the limitations of current Large Language Models (LLMs). These perspectives are derived from the initial results of a sub-study employing vignettes to showcase the existence of bias within black-box LLMs and explore methods for manipulating them. The study aims to establish a foundation for understanding the challenges associated with these models, emphasizing the necessity of thorough testing before utilizing them to create synthetic personae for HCI research.
Cryptocurrency Risk, Trust, and Acceptance in Thailand: A Comparative Study with Switzerland
Venue: arXiv cs.CE 2024
Year: 2024

The adoption of the Pao Tang digital wallet in Thailand, promoted under the Khon la Krueng (50-50 Co-Payment) Scheme, illustrates Thailand's receptiveness to digital financial instruments, amassing over 40 million users in just three years during the COVID-19 social distancing era. Nevertheless, acceptance of this platform does not confirm a broad understanding of cryptocurrencies and Web 3.0 technologies in the region. Through a mix of documentary research, online surveys and a targeted interview with the Pao Tang app's founder, this study evaluates the factors behind the Pao Tang platform's success and contrasts it with digital practices in Switzerland. Preliminary outcomes reveal a pronounced knowledge gap in Thailand regarding decentralized technologies. With regulatory frameworks for Web 3.0 and digital currencies still nascent, this research underscores the need for further exploration, serving as a blueprint for shaping strategies, policies, and awareness campaigns in both countries.
QFMTS: Generating Query-Focused Summaries over Multi-Table Inputs
Venue: arXiv cs.CL 2024
Year: 2024

Table summarization is a crucial task aimed at condensing information from tabular data into concise and comprehensible textual summaries. However, existing approaches often fall short of adequately meeting users' information and quality requirements and tend to overlook the complexities of real-world queries. In this paper, we propose a novel method to address these limitations by introducing query-focused multi-table summarization. Our approach, which comprises a table serialization module, a summarization controller, and a large language model (LLM), utilizes textual queries and multiple tables to generate query-dependent table summaries tailored to users' information needs. To facilitate research in this area, we present a comprehensive dataset specifically tailored for this task, consisting of 4909 query-summary pairs, each associated with multiple tables. Through extensive experiments using our curated dataset, we demonstrate the effectiveness of our proposed method compared to baseline approaches. Our findings offer insights into the challenges of complex table reasoning for precise summarization, contributing to the advancement of research in query-focused multi-table summarization.
Identifying every building's function in large-scale urban areas with multi-modality remote-sensing data
Venue: arXiv cs.CV 2024
Year: 2024

Buildings, as fundamental man-made structures in urban environments, serve as crucial indicators for understanding various city function zones. Rapid urbanization has raised an urgent need for efficiently surveying building footprints and functions. In this study, we proposed a semi-supervised framework to identify every building's function in large-scale urban areas with multi-modality remote-sensing data. In detail, optical images, building height, and nighttime-light data are collected to describe the morphological attributes of buildings. Then, the area of interest (AOI) and building masks from the volunteered geographic information (VGI) data are collected to form sparsely labeled samples. Furthermore, the multi-modality data and weak labels are utilized to train a segmentation model with a semi-supervised strategy. Finally, results are evaluated by 20,000 validation points and statistical survey reports from the government. The evaluations reveal that the produced function maps achieve an OA of 82% and Kappa of 71% among 1,616,796 buildings in Shanghai, China. This study has the potential to support large-scale urban management and sustainable urban development. All collected data and produced maps are open access at https://github.com/LiZhuoHong/BuildingMap.
Enhancing Deep Knowledge Tracing via Diffusion Models for Personalized Adaptive Learning
Venue: arXiv cs.CY 2024
Year: 2024

In contrast to pedagogies like evidence-based teaching, personalized adaptive learning (PAL) distinguishes itself by closely monitoring the progress of individual students and tailoring the learning path to their unique knowledge and requirements. A crucial technique for effective PAL implementation is knowledge tracing, which models students' evolving knowledge to predict their future performance. Based on these predictions, personalized recommendations for resources and learning paths can be made to meet individual needs. Recent advancements in deep learning have successfully enhanced knowledge tracking through Deep Knowledge Tracing (DKT). This paper introduces generative AI models to further enhance DKT. Generative AI models, rooted in deep learning, are trained to generate synthetic data, addressing data scarcity challenges in various applications across fields such as natural language processing (NLP) and computer vision (CV). This study aims to tackle data shortage issues in student learning records to enhance DKT performance for PAL. Specifically, it employs TabDDPM, a diffusion model, to generate synthetic educational records to augment training data for enhancing DKT. The proposed method's effectiveness is validated through extensive experiments on ASSISTments datasets. The experimental results demonstrate that the AI-generated data by TabDDPM significantly improves DKT performance, particularly in scenarios with small data for training and large data for testing.
Improving Automated Distractor Generation for Math Multiple-choice Questions with Overgenerate-and-rank
Venue: arXiv cs.CY 2024
Year: 2024

Multiple-choice questions (MCQs) are commonly used across all levels of math education since they can be deployed and graded at a large scale. A critical component of MCQs is the distractors, i.e., incorrect answers crafted to reflect student errors or misconceptions. Automatically generating them in math MCQs, e.g., with large language models, has been challenging. In this work, we propose a novel method to enhance the quality of generated distractors through overgenerate-and-rank, training a ranking model to predict how likely distractors are to be selected by real students. Experimental results on a real-world dataset and human evaluation with math teachers show that our ranking model increases alignment with human-authored distractors, although human-authored ones are still preferred over generated ones.
Custom Gradient Estimators are Straight-Through Estimators in Disguise
Venue: arXiv cs.LG 2024
Year: 2024

Quantization-aware training comes with a fundamental challenge: the derivative of quantization functions such as rounding are zero almost everywhere and nonexistent elsewhere. Various differentiable approximations of quantization functions have been proposed to address this issue. In this paper, we prove that when the learning rate is sufficiently small, a large class of weight gradient estimators is equivalent with the straight through estimator (STE). Specifically, after swapping in the STE and adjusting both the weight initialization and the learning rate in SGD, the model will train in almost exactly the same way as it did with the original gradient estimator. Moreover, we show that for adaptive learning rate algorithms like Adam, the same result can be seen without any modifications to the weight initialization and learning rate. We experimentally show that these results hold for both a small convolutional model trained on the MNIST dataset and for a ResNet50 model trained on ImageNet.
Broadcast Channel Synthesis from Shared Randomness
Venue: arXiv cs.IT 2024
Year: 2024

We study the problem of synthesising a two-user broadcast channel using a common message, where each output terminal shares an independent source of randomness with the input terminal. This generalises two problems studied in the literature (Cuff, IEEE Trans. Inform. Theory, 2013; Kurri et.al., IEEE Trans. Inform. Theory, 2021). We give an inner bound on the tradeoff region between the rates of communication and shared randomness, and a lower bound on the minimum communication rate. Although the bounds presented here are not tight in general, they are tight for some special cases, including the aforementioned problems.
"Community Guidelines Make this the Best Party on the Internet": An In-Depth Study of Online Platforms' Content Moderation Policies
Venue: arXiv cs.HC 2024
Year: 2024

Moderating user-generated content on online platforms is crucial for balancing user safety and freedom of speech. Particularly in the United States, platforms are not subject to legal constraints prescribing permissible content. Each platform has thus developed bespoke content moderation policies, but there is little work towards a comparative understanding of these policies across platforms and topics. This paper presents the first systematic study of these policies from the 43 largest online platforms hosting user-generated content, focusing on policies around copyright infringement, harmful speech, and misleading content. We build a custom web-scraper to obtain policy text and develop a unified annotation scheme to analyze the text for the presence of critical components. We find significant structural and compositional variation in policies across topics and platforms, with some variation attributable to disparate legal groundings. We lay the groundwork for future studies of ever-evolving content moderation policies and their impact on users.
Advancing Blockchain Scalability: A Linear Optimization Framework for Diversified Node Allocation in Shards
Venue: arXiv cs.DC 2024
Year: 2024

Blockchain technology, while revolutionary in enabling decentralized transactions, faces scalability challenges as the ledger must be replicated across all nodes of the chain, limiting throughput and efficiency. Sharding, which divides the chain into smaller segments, called shards, offers a solution by enabling parallel transaction processing. However, sharding introduces new complexities, notably how to allocate nodes to shards without compromising the network's security. This paper introduces a novel linear optimization framework for node allocation to shards that addresses decentralization constraints while minimizing resource consumption. In contrast to traditional methods that depend on random or trust-based assignments, our approach evaluates node characteristics, including ownership, hardware, and geographical distribution, and requires an explicit specification of decentralization targets with respect to these characteristics. By employing linear optimization, the framework identifies a resource-efficient node set meeting these targets. Adopted by the Internet Computer Protocol (ICP) community, this framework proves its utility in real-world blockchain applications. It provides a quantitative tool for node onboarding and offboarding decisions, balancing decentralization and resource considerations.
Harmonizing Program Induction with Rate-Distortion Theory
Venue: arXiv cs.HC 2024
Year: 2024

Many aspects of human learning have been proposed as a process of constructing mental programs: from acquiring symbolic number representations to intuitive theories about the world. In parallel, there is a long-tradition of using information processing to model human cognition through Rate Distortion Theory (RDT). Yet, it is still poorly understood how to apply RDT when mental representations take the form of programs. In this work, we adapt RDT by proposing a three way trade-off among rate (description length), distortion (error), and computational costs (search budget). We use simulations on a melody task to study the implications of this trade-off, and show that constructing a shared program library across tasks provides global benefits. However, this comes at the cost of sensitivity to curricula, which is also characteristic of human learners. Finally, we use methods from partial information decomposition to generate training curricula that induce more effective libraries and better generalization.
Benchmarking Educational Program Repair
Venue: arXiv cs.SE 2024
Year: 2024

The emergence of large language models (LLMs) has sparked enormous interest due to their potential application across a range of educational tasks. For example, recent work in programming education has used LLMs to generate learning resources, improve error messages, and provide feedback on code. However, one factor that limits progress within the field is that much of the research uses bespoke datasets and different evaluation metrics, making direct comparisons between results unreliable. Thus, there is a pressing need for standardization and benchmarks that facilitate the equitable comparison of competing approaches. One task where LLMs show great promise is program repair, which can be used to provide debugging support and next-step hints to students. In this article, we propose a novel educational program repair benchmark. We curate two high-quality publicly available programming datasets, present a unified evaluation procedure introducing a novel evaluation metric rouge@k for approximating the quality of repairs, and evaluate a set of five recent models to establish baseline performance.
Transfer-LMR: Heavy-Tail Driving Behavior Recognition in Diverse Traffic Scenarios
Venue: arXiv cs.CV 2024
Year: 2024

Recognizing driving behaviors is important for downstream tasks such as reasoning, planning, and navigation. Existing video recognition approaches work well for common behaviors (e.g. "drive straight", "brake", "turn left/right"). However, the performance is sub-par for underrepresented/rare behaviors typically found in tail of the behavior class distribution. To address this shortcoming, we propose Transfer-LMR, a modular training routine for improving the recognition performance across all driving behavior classes. We extensively evaluate our approach on METEOR and HDD datasets that contain rich yet heavy-tailed distribution of driving behaviors and span diverse traffic scenarios. The experimental results demonstrate the efficacy of our approach, especially for recognizing underrepresented/rare driving behaviors.
Mutual information and the encoding of contingency tables
Venue: arXiv cs.SI 2024
Year: 2024

Mutual information is commonly used as a measure of similarity between competing labelings of a given set of objects, for example to quantify performance in classification and community detection tasks. As argued recently, however, the mutual information as conventionally defined can return biased results because it neglects the information cost of the so-called contingency table, a crucial component of the similarity calculation. In principle the bias can be rectified by subtracting the appropriate information cost, leading to the modified measure known as the reduced mutual information, but in practice one can only ever compute an upper bound on this information cost, and the value of the reduced mutual information depends crucially on how good a bound is established. In this paper we describe an improved method for encoding contingency tables that gives a substantially better bound in typical use cases, and approaches the ideal value in the common case where the labelings are closely similar, as we demonstrate with extensive numerical results.
The Power of Absence: Thinking with Archival Theory in Algorithmic Design
Venue: arXiv cs.CY 2024
Year: 2024

This paper explores the value of archival theory as a means of grappling with bias in algorithmic design. Rather than seek to mitigate biases perpetuated by datasets and algorithmic systems, archival theory offers a reframing of bias itself. Drawing on a range of archival theory from the fields of history, literary and cultural studies, Black studies, and feminist STS, we propose absence-as power, presence, and productive-as a concept that might more securely anchor investigations into the causes of algorithmic bias, and that can prompt more capacious, creative, and joyful future work. This essay, in turn, can intervene into the technical as well as the social, historical, and political structures that serve as sources of bias.
EarthMatch: Iterative Coregistration for Fine-grained Localization of Astronaut Photography
Venue: arXiv cs.CV 2024
Year: 2024

Precise, pixel-wise geolocalization of astronaut photography is critical to unlocking the potential of this unique type of remotely sensed Earth data, particularly for its use in disaster management and climate change research. Recent works have established the Astronaut Photography Localization task, but have either proved too costly for mass deployment or generated too coarse a localization. Thus, we present EarthMatch, an iterative homography estimation method that produces fine-grained localization of astronaut photographs while maintaining an emphasis on speed. We refocus the astronaut photography benchmark, AIMS, on the geolocalization task itself, and prove our method's efficacy on this dataset. In addition, we offer a new, fair method for image matcher comparison, and an extensive evaluation of different matching models within our localization pipeline. Our method will enable fast and accurate localization of the 4.5 million and growing collection of astronaut photography of Earth. Webpage with code and data at https://earthloc-and-earthmatch.github.io
Variance Control for Black Box Variational Inference Using The James-Stein Estimator
Venue: arXiv cs.LG 2024
Year: 2024

Black Box Variational Inference is a promising framework in a succession of recent efforts to make Variational Inference more ``black box". However, in basic version it either fails to converge due to instability or requires some fine-tuning of the update steps prior to execution that hinder it from being completely general purpose. We propose a method for regulating its parameter updates by reframing stochastic gradient ascent as a multivariate estimation problem. We examine the properties of the James-Stein estimator as a replacement for the arithmetic mean of Monte Carlo estimates of the gradient of the evidence lower bound. The proposed method provides relatively weaker variance reduction than Rao-Blackwellization, but offers a tradeoff of being simpler and requiring no fine tuning on the part of the analyst. Performance on benchmark datasets also demonstrate a consistent performance at par or better than the Rao-Blackwellized approach in terms of model fit and time to convergence.