OpenRaiser/Intern-Atlas huggingface dataset:
FastQuery: Communication-efficient Embedding Table Query for Private LLM Inference
Venue: arXiv cs.CR 2024
Year: 2024

With the fast evolution of large language models (LLMs), privacy concerns with user queries arise as they may contain sensitive information. Private inference based on homomorphic encryption (HE) has been proposed to protect user query privacy. However, a private embedding table query has to be formulated as a HE-based matrix-vector multiplication problem and suffers from enormous computation and communication overhead. We observe the overhead mainly comes from the neglect of 1) the one-hot nature of user queries and 2) the robustness of the embedding table to low bit-width quantization noise. Hence, in this paper, we propose a private embedding table query optimization framework, dubbed FastQuery. FastQuery features a communication-aware embedding table quantization algorithm and a one-hot-aware dense packing algorithm to simultaneously reduce both the computation and communication costs. Compared to prior-art HE-based frameworks, e.g., Cheetah, Iron, and Bumblebee, FastQuery achieves more than $4.3\times$, $2.7\times$, $1.3\times$ latency reduction, respectively and more than $75.7\times$, $60.2\times$, $20.2\times$ communication reduction, respectively, on both LLAMA-7B and LLAMA-30B.
Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
Venue: arXiv cs.CC 2024
Year: 2024

We study the following generalization of the Hamiltonian cycle problem: Given integers $a,b$ and graph $G$, does there exist a closed walk in $G$ that visits every vertex at least $a$ times and at most $b$ times? Equivalently, does there exist a connected $[2a,2b]$ factor of $2b \cdot G$ with all degrees even? This problem is NP-hard for any constants $1 \leq a \leq b$. However, the graphs produced by known reductions have maximum degree growing linearly in $b$. The case $a = b = 1 $ -- i.e. Hamiltonicity -- remains NP-hard even in $3$-regular graphs; a natural question is whether this is true for other $a$, $b$. In this work, we study which $a, b$ permit polynomial time algorithms and which lead to NP-hardness in graphs with constrained degrees. We give tight characterizations for regular graphs and graphs of bounded max-degree, both directed and undirected.
LoGAH: Predicting 774-Million-Parameter Transformers using Graph HyperNetworks with 1/100 Parameters
Venue: arXiv cs.LG 2024
Year: 2024

A good initialization of deep learning models is essential since it can help them converge better and faster. However, pretraining large models is unaffordable for many researchers, which makes a desired prediction for initial parameters more necessary nowadays. Graph HyperNetworks (GHNs), one approach to predicting model parameters, have recently shown strong performance in initializing large vision models. Unfortunately, predicting parameters of very wide networks relies on copying small chunks of parameters multiple times and requires an extremely large number of parameters to support full prediction, which greatly hinders its adoption in practice. To address this limitation, we propose LoGAH (Low-rank GrAph Hypernetworks), a GHN with a low-rank parameter decoder that expands to significantly wider networks without requiring as excessive increase of parameters as in previous attempts. LoGAH allows us to predict the parameters of 774-million large neural networks in a memory-efficient manner. We show that vision and language models (i.e., ViT and GPT-2) initialized with LoGAH achieve better performance than those initialized randomly or using existing hypernetworks. Furthermore, we show promising transfer learning results w.r.t. training LoGAH on small datasets and using the predicted parameters to initialize for larger tasks. We provide the codes in https://github.com/Blackzxy/LoGAH .
Understanding Stakeholders' Perceptions and Needs Across the LLM Supply Chain
Venue: arXiv cs.HC 2024
Year: 2024

Explainability and transparency of AI systems are undeniably important, leading to several research studies and tools addressing them. Existing works fall short of accounting for the diverse stakeholders of the AI supply chain who may differ in their needs and consideration of the facets of explainability and transparency. In this paper, we argue for the need to revisit the inquiries of these vital constructs in the context of LLMs. To this end, we report on a qualitative study with 71 different stakeholders, where we explore the prevalent perceptions and needs around these concepts. This study not only confirms the importance of exploring the ``who'' in XAI and transparency for LLMs, but also reflects on best practices to do so while surfacing the often forgotten stakeholders and their information needs. Our insights suggest that researchers and practitioners should simultaneously clarify the ``who'' in considerations of explainability and transparency, the ``what'' in the information needs, and ``why'' they are needed to ensure responsible design and development across the LLM supply chain.
Large Language Models Enable Automated Formative Feedback in Human-Robot Interaction Tasks
Venue: arXiv cs.RO 2024
Year: 2024

We claim that LLMs can be paired with formal analysis methods to provide accessible, relevant feedback for HRI tasks. While logic specifications are useful for defining and assessing a task, these representations are not easily interpreted by non-experts. Luckily, LLMs are adept at generating easy-to-understand text that explains difficult concepts. By integrating task assessment outcomes and other contextual information into an LLM prompt, we can effectively synthesize a useful set of recommendations for the learner to improve their performance.
Game Derandomization
Venue: arXiv cs.CC 2024
Year: 2024

Using Kolmogorov Game Derandomization, upper bounds of the Kolmogorov complexity of deterministic winning players against deterministic environments can be proved. This paper gives improved upper bounds of the Kolmogorov complexity of such players. This paper also generalizes this result to probabilistic games. This applies to computable, lower computable, and uncomputable environments. We characterize the classic even-odds game and then generalize these results to time bounded players and also to all zero-sum repeated games. We characterize partial game derandomization. But first, we start with an illustrative example of game derandomization, taking place on the island of Crete.
Qsco: A Quantum Scoring Module for Open-set Supervised Anomaly Detection
Venue: arXiv cs.LG 2024
Year: 2024

Open set anomaly detection (OSAD) is a crucial task that aims to identify abnormal patterns or behaviors in data sets, especially when the anomalies observed during training do not represent all possible classes of anomalies. The recent advances in quantum computing in handling complex data structures and improving machine learning models herald a paradigm shift in anomaly detection methodologies. This study proposes a Quantum Scoring Module (Qsco), embedding quantum variational circuits into neural networks to enhance the model's processing capabilities in handling uncertainty and unlabeled data. Extensive experiments conducted across eight real-world anomaly detection datasets demonstrate our model's superior performance in detecting anomalies across varied settings and reveal that integrating quantum simulators does not result in prohibitive time complexities. Our study validates the feasibility of quantum-enhanced anomaly detection methods in practical applications.
Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically
Venue: arXiv cs.IT 2024
Year: 2024

Successive cancellation list (SCL) decoders of polar codes excel in practical performance but pose challenges for theoretical analysis. Existing works either limit their scope to erasure channels or address general channels without taking advantage of soft information. In this paper, we propose the "successive cancellation sampling" (SCS) decoder. SCS hires iid "agents" to sample codewords using posterior probabilities. This makes it fully parallel and amenable for some theoretical analysis. As an example, when comparing SCS with $a$ agents to any list decoder with list size $\ell$, we can prove that the error probability of the former is at most $\ell/ae$ more than that of the latter. In this paper, we also describe how to adjust the "temperature" of agents. Warmer agents are less likely to sample the same codewords and hence can further reduce error probability.
Isolate and then Identify: Rethinking Adaptive Group Testing
Venue: arXiv cs.IT 2024
Year: 2024

Group testing (GT) is the art of identifying binary signals and the marketplace for exchanging new ideas for related fields such as unique-element counting, compressed sensing, traitor tracing, and geno-typing. A GT scheme can be nonadaptive or adaptive; the latter is preferred when latency is ess of an issue. To construct adaptive GT schemes, a popular strategy is to spend the majority of tests in the first few rounds to gain as much information as possible, and uses later rounds to refine details. In this paper, we propose a transparent strategy called "isolate and then identify" (I@I). In the first few rounds, I@I divides the population into teams until every team contains at most one sick person. Then, in the last round, I@I identifies the sick person in each team. Performance-wise, I@I is the first GT scheme that achieves the optimal coefficient $1/$capacity$(Z)$ for the $k \log_2 (n/k)$ term in the number of tests when $Z$ is a generic channel corrupting the test outcomes. I@I follows a modular methodology whereby the isolating part and the identification part can be optimized separately.
Machine learning in business process management: A systematic literature review
Venue: arXiv cs.LG 2024
Year: 2024

Machine learning (ML) provides algorithms to create computer programs based on data without explicitly programming them. In business process management (BPM), ML applications are used to analyse and improve processes efficiently. Three frequent examples of using ML are providing decision support through predictions, discovering accurate process models, and improving resource allocation. This paper organises the body of knowledge on ML in BPM. We extract BPM tasks from different literature streams, summarise them under the phases of a process`s lifecycle, explain how ML helps perform these tasks and identify technical commonalities in ML implementations across tasks. This study is the first exhaustive review of how ML has been used in BPM. We hope that it can open the door for a new era of cumulative research by helping researchers to identify relevant preliminary work and then combine and further develop existing approaches in a focused fashion. Our paper helps managers and consultants to find ML applications that are relevant in the current project phase of a BPM initiative, like redesigning a business process. We also offer - as a synthesis of our review - a research agenda that spreads ten avenues for future research, including applying novel ML concepts like federated learning, addressing less regarded BPM lifecycle phases like process identification, and delivering ML applications with a focus on end-users.
Towards Sustainable IoT: Challenges, Solutions, and Future Directions for Device Longevity
Venue: arXiv cs.CR 2024
Year: 2024

In an era dominated by the Internet of Things, ensuring the longevity and sustainability of IoT devices has emerged as a pressing concern. This study explores the various complex difficulties which contributed to the early decommissioning of IoT devices and suggests methods to improve their lifespan management. By examining factors such as security vulnerabilities, user awareness gaps, and the influence of fashion-driven technology trends, the paper underscores the need for legislative interventions, consumer education, and industry accountability. Additionally, it explores innovative approaches to improving IoT longevity, including the integration of sustainability considerations into architectural design through requirements engineering methodologies. Furthermore, the paper discusses the potential of distributed ledger technology, or blockchain, to promote transparent and decentralized processes for device provisioning and tracking. This study promotes a sustainable IoT ecosystem by integrating technology innovation, legal change, and social awareness to reduce environmental impact and enhance resilience for the digital future
Segmentation of Maya hieroglyphs through fine-tuned foundation models
Venue: arXiv cs.CV 2024
Year: 2024

The study of Maya hieroglyphic writing unlocks the rich history of cultural and societal knowledge embedded within this ancient civilization's visual narrative. Artificial Intelligence (AI) offers a novel lens through which we can translate these inscriptions, with the potential to allow non-specialists access to reading these texts and to aid in the decipherment of those hieroglyphs which continue to elude comprehensive interpretation. Toward this, we leverage a foundational model to segment Maya hieroglyphs from an open-source digital library dedicated to Maya artifacts. Despite the initial promise of publicly available foundational segmentation models, their effectiveness in accurately segmenting Maya hieroglyphs was initially limited. Addressing this challenge, our study involved the meticulous curation of image and label pairs with the assistance of experts in Maya art and history, enabling the fine-tuning of these foundational models. This process significantly enhanced model performance, illustrating the potential of fine-tuning approaches and the value of our expanding dataset. We plan to open-source this dataset for encouraging future research, and eventually to help make the hieroglyphic texts legible to a broader community, particularly for Maya heritage community members.
3D View Optimization for Improving Image Aesthetics
Venue: arXiv cs.CV 2024
Year: 2024

Achieving aesthetically pleasing photography necessitates attention to multiple factors, including composition and capture conditions, which pose challenges to novices. Prior research has explored the enhancement of photo aesthetics post-capture through 2D manipulation techniques; however, these approaches offer limited search space for aesthetics. We introduce a pioneering method that employs 3D operations to simulate the conditions at the moment of capture retrospectively. Our approach extrapolates the input image and then reconstructs the 3D scene from the extrapolated image, followed by an optimization to identify camera parameters and image aspect ratios that yield the best 3D view with enhanced aesthetics. Comparative qualitative and quantitative assessments reveal that our method surpasses traditional 2D editing techniques with superior aesthetics.
Multi-Level Additive Modeling for Structured Non-IID Federated Learning
Venue: arXiv cs.LG 2024
Year: 2024

The primary challenge in Federated Learning (FL) is to model non-IID distributions across clients, whose fine-grained structure is important to improve knowledge sharing. For example, some knowledge is globally shared across all clients, some is only transferable within a subgroup of clients, and some are client-specific. To capture and exploit this structure, we train models organized in a multi-level structure, called ``Multi-level Additive Models (MAM)'', for better knowledge-sharing across heterogeneous clients and their personalization. In federated MAM (FeMAM), each client is assigned to at most one model per level and its personalized prediction sums up the outputs of models assigned to it across all levels. For the top level, FeMAM trains one global model shared by all clients as FedAvg. For every mid-level, it learns multiple models each assigned to a subgroup of clients, as clustered FL. Every bottom-level model is trained for one client only. In the training objective, each model aims to minimize the residual of the additive predictions by the other models assigned to each client. To approximate the arbitrary structure of non-IID across clients, FeMAM introduces more flexibility and adaptivity to FL by incrementally adding new models to the prediction of each client and reassigning another if necessary, automatically optimizing the knowledge-sharing structure. Extensive experiments show that FeMAM surpasses existing clustered FL and personalized FL methods in various non-IID settings. Our code is available at https://github.com/shutong043/FeMAM.
M$^3$CoT: A Novel Benchmark for Multi-Domain Multi-step Multi-modal Chain-of-Thought
Venue: arXiv cs.CV 2024
Year: 2024

Multi-modal Chain-of-Thought (MCoT) requires models to leverage knowledge from both textual and visual modalities for step-by-step reasoning, which gains increasing attention. Nevertheless, the current MCoT benchmark still faces some challenges: (1) absence of visual modal reasoning, (2) single-step visual modal reasoning, and (3) Domain missing, thereby hindering the development of MCoT. Motivated by this, we introduce a novel benchmark (M$^3$CoT) to address the above challenges, advancing the multi-domain, multi-step, and multi-modal CoT. Additionally, we conduct a thorough evaluation involving abundant MCoT approaches on Vision Large Language Models (VLLMs). In addition, we highlight that the current VLLMs still struggle to correctly reason in M$^3$CoT and there remains a large gap between existing VLLMs and human performance in M$^3$CoT, despite their superior results on previous MCoT benchmarks. To our knowledge, we take the first meaningful step toward the multi-domain, multi-step, and multi-modal scenario in MCoT. We hope that M$^3$CoT can serve as a valuable resource, providing a pioneering foundation in multi-domain, multi-step, multi-modal chain-of-thought research.
Vision-Based Approach for Food Weight Estimation from 2D Images
Venue: arXiv cs.CV 2024
Year: 2024

In response to the increasing demand for efficient and non-invasive methods to estimate food weight, this paper presents a vision-based approach utilizing 2D images. The study employs a dataset of 2380 images comprising fourteen different food types in various portions, orientations, and containers. The proposed methodology integrates deep learning and computer vision techniques, specifically employing Faster R-CNN for food detection and MobileNetV3 for weight estimation. The detection model achieved a mean average precision (mAP) of 83.41\%, an average Intersection over Union (IoU) of 91.82\%, and a classification accuracy of 100\%. For weight estimation, the model demonstrated a root mean squared error (RMSE) of 6.3204, a mean absolute percentage error (MAPE) of 0.0640\%, and an R-squared value of 98.65\%. The study underscores the potential applications of this technology in healthcare for nutrition counseling, fitness and wellness for dietary intake assessment, and smart food storage solutions to reduce waste. The results indicate that the combination of Faster R-CNN and MobileNetV3 provides a robust framework for accurate food weight estimation from 2D images, showcasing the synergy of computer vision and deep learning in practical applications.
User-Friendly Customized Generation with Multi-Modal Prompts
Venue: arXiv cs.CV 2024
Year: 2024

Text-to-image generation models have seen considerable advancement, catering to the increasing interest in personalized image creation. Current customization techniques often necessitate users to provide multiple images (typically 3-5) for each customized object, along with the classification of these objects and descriptive textual prompts for scenes. This paper questions whether the process can be made more user-friendly and the customization more intricate. We propose a method where users need only provide images along with text for each customization topic, and necessitates only a single image per visual concept. We introduce the concept of a ``multi-modal prompt'', a novel integration of text and images tailored to each customization concept, which simplifies user interaction and facilitates precise customization of both objects and scenes. Our proposed paradigm for customized text-to-image generation surpasses existing finetune-based methods in user-friendliness and the ability to customize complex objects with user-friendly inputs. Our code is available at $\href{https://github.com/zhongzero/Multi-Modal-Prompt}{https://github.com/zhongzero/Multi-Modal-Prompt}$.
Multi-State TD Target for Model-Free Reinforcement Learning
Venue: arXiv cs.LG 2024
Year: 2024

Temporal difference (TD) learning is a fundamental technique in reinforcement learning that updates value estimates for states or state-action pairs using a TD target. This target represents an improved estimate of the true value by incorporating both immediate rewards and the estimated value of subsequent states. Traditionally, TD learning relies on the value of a single subsequent state. We propose an enhanced multi-state TD (MSTD) target that utilizes the estimated values of multiple subsequent states. Building on this new MSTD concept, we develop complete actor-critic algorithms that include management of replay buffers in two modes, and integrate with deep deterministic policy optimization (DDPG) and soft actor-critic (SAC). Experimental results demonstrate that algorithms employing the MSTD target significantly improve learning performance compared to traditional methods.The code is provided on GitHub.
Mamba4KT:An Efficient and Effective Mamba-based Knowledge Tracing Model
Venue: arXiv cs.AI 2024
Year: 2024

Knowledge tracing (KT) enhances student learning by leveraging past performance to predict future performance. Current research utilizes models based on attention mechanisms and recurrent neural network structures to capture long-term dependencies and correlations between exercises, aiming to improve model accuracy. Due to the growing amount of data in smart education scenarios, this poses a challenge in terms of time and space consumption for knowledge tracing models. However, existing research often overlooks the efficiency of model training and inference and the constraints of training resources. Recognizing the significance of prioritizing model efficiency and resource usage in knowledge tracing, we introduce Mamba4KT. This novel model is the first to explore enhanced efficiency and resource utilization in knowledge tracing. We also examine the interpretability of the Mamba structure both sequence-level and exercise-level to enhance model interpretability. Experimental findings across three public datasets demonstrate that Mamba4KT achieves comparable prediction accuracy to state-of-the-art models while significantly improving training and inference efficiency and resource utilization. As educational data continues to grow, our work suggests a promising research direction for knowledge tracing that improves model prediction accuracy, model efficiency, resource utilization, and interpretability simultaneously.
GPU Based Differential Evolution: New Insights and Comparative Study
Venue: arXiv cs.NE 2024
Year: 2024

Differential Evolution (DE) is a highly successful population based global optimisation algorithm, commonly used for solving numerical optimisation problems. However, as the complexity of the objective function increases, the wall-clock run-time of the algorithm suffers as many fitness function evaluations must take place to effectively explore the search space. Due to the inherently parallel nature of the DE algorithm, graphics processing units (GPU) have been used to effectively accelerate both the fitness evaluation and DE algorithm. This work reviews the main architectural choices made in the literature for GPU based DE algorithms and introduces a new GPU based numerical optimisation benchmark to evaluate and compare GPU based DE algorithms.