OpenRaiser/Intern-Atlas huggingface dataset:
MicroHD: An Accuracy-Driven Optimization of Hyperdimensional Computing Algorithms for TinyML systems
Venue: arXiv cs.PF 2024
Year: 2024

Hyperdimensional computing (HDC) is emerging as a promising AI approach that can effectively target TinyML applications thanks to its lightweight computing and memory requirements. Previous works on HDC showed that limiting the standard 10k dimensions of the hyperdimensional space to much lower values is possible, reducing even more HDC resource requirements. Similarly, other studies demonstrated that binary values can be used as elements of the generated hypervectors, leading to significant efficiency gains at the cost of some degree of accuracy degradation. Nevertheless, current optimization attempts do not concurrently co-optimize HDC hyper-parameters, and accuracy degradation is not directly controlled, resulting in sub-optimal HDC models providing several applications with unacceptable output qualities. In this work, we propose MicroHD, a novel accuracy-driven HDC optimization approach that iteratively tunes HDC hyper-parameters, reducing memory and computing requirements while ensuring user-defined accuracy levels. The proposed method can be applied to HDC implementations using different encoding functions, demonstrates good scalability for larger HDC workloads, and achieves compression and efficiency gains up to 200x when compared to baseline implementations for accuracy degradations lower than 1%.
PerOS: Personalized Self-Adapting Operating Systems in the Cloud
Venue: arXiv cs.HC 2024
Year: 2024

Operating systems (OSes) are foundational to computer systems, managing hardware resources and ensuring secure environments for diverse applications. However, despite their enduring importance, the fundamental design objectives of OSes have seen minimal evolution over decades. Traditionally prioritizing aspects like speed, memory efficiency, security, and scalability, these objectives often overlook the crucial aspect of intelligence as well as personalized user experience. The lack of intelligence becomes increasingly critical amid technological revolutions, such as the remarkable advancements in machine learning (ML). Today's personal devices, evolving into intimate companions for users, pose unique challenges for traditional OSes like Linux and iOS, especially with the emergence of specialized hardware featuring heterogeneous components. Furthermore, the rise of large language models (LLMs) in ML has introduced transformative capabilities, reshaping user interactions and software development paradigms. While existing literature predominantly focuses on leveraging ML methods for system optimization or accelerating ML workloads, there is a significant gap in addressing personalized user experiences at the OS level. To tackle this challenge, this work proposes PerOS, a personalized OS ingrained with LLM capabilities. PerOS aims to provide tailored user experiences while safeguarding privacy and personal data through declarative interfaces, self-adaptive kernels, and secure data management in a scalable cloud-centric architecture; therein lies the main research question of this work: How can we develop intelligent, secure, and scalable OSes that deliver personalized experiences to thousands of users?
ERIOS: Co-construction of a Dynamic Temporal Visualization Tool in the Electronic Health Record
Venue: arXiv cs.HC 2024
Year: 2024

ERIOS, is a collaborative project between Dedalus, a health software company, Montpellier University Hospital Center (CHU), and the University of Montpellier. This initiative aims to incorporate research and development (R\&D) directly within the hospital, focusing on co-creating components of the Electronic Health Record (EHR) alongside end-users. The project was initiated with two initial use cases, which led to the development of components for dynamic temporal visualization, now integrated into specific dashboards. The application of academic recommendations regarding user engagement methodology and human-computer interactions significantly enhanced our ability to meet user needs.
Budget-aware Query Tuning: An AutoML Perspective
Venue: arXiv cs.DB 2024
Year: 2024

Modern database systems rely on cost-based query optimizers to come up with good execution plans for input queries. Such query optimizers rely on cost models to estimate the costs of candidate query execution plans. A cost model represents a function from a set of cost units to query execution cost, where each cost unit specifies the unit cost of executing a certain type of query processing operation (such as table scan or join). These cost units are traditionally viewed as constants, whose values only depend on the platform configuration where the database system runs on top of but are invariant for queries processed by the database system. In this paper, we challenge this classic view by thinking of these cost units as variables instead. We show that, by varying the cost-unit values one can obtain query plans that significantly outperform the default query plans returned by the query optimizer when viewing the cost units as constants. We term this cost-unit tuning process "query tuning" (QT) and show that it is similar to the well-known hyper-parameter optimization (HPO) problem in AutoML. As a result, any state-of-the-art HPO technologies can be applied to QT. We study the QT problem in the context of anytime tuning, which is desirable in practice by constraining the total time spent on QT within a given budget -- we call this problem budget-aware query tuning. We further extend our study from tuning a single query to tuning a workload with multiple queries, and we call this generalized problem budget-aware workload tuning (WT), which aims for minimizing the execution time of the entire workload. WT is more challenging as one needs to further prioritize individual query tuning within the given time budget. We propose solutions to both QT and WT and experimental evaluation using both benchmark and real workloads demonstrates the efficacy of our proposed solutions.
Does Faithfulness Conflict with Plausibility? An Empirical Study in Explainable AI across NLP Tasks
Venue: arXiv cs.AI 2024
Year: 2024

Explainability algorithms aimed at interpreting decision-making AI systems usually consider balancing two critical dimensions: 1) \textit{faithfulness}, where explanations accurately reflect the model's inference process. 2) \textit{plausibility}, where explanations are consistent with domain experts. However, the question arises: do faithfulness and plausibility inherently conflict? In this study, through a comprehensive quantitative comparison between the explanations from the selected explainability methods and expert-level interpretations across three NLP tasks: sentiment analysis, intent detection, and topic labeling, we demonstrate that traditional perturbation-based methods Shapley value and LIME could attain greater faithfulness and plausibility. Our findings suggest that rather than optimizing for one dimension at the expense of the other, we could seek to optimize explainability algorithms with dual objectives to achieve high levels of accuracy and user accessibility in their explanations.
Precision game engineering through reshaping strategic payoffs
Venue: arXiv cs.GT 2024
Year: 2024

Nash equilibrium is a key concept in game theory fundamental for elucidating the equilibrium state of strategic interactions, finding applications in diverse fields such as economics, political science, and biology. However, the Nash equilibrium may not always align with the optimal or desired outcomes within a system. This article introduces a novel game engineering framework that tweaks strategic payoffs within a game to achieve a desired Nash equilibrium while averting undesired ones. Leveraging mixed-integer linear programming, this framework identifies intricate combinations of players and strategies and optimal perturbations to their payoffs that enable the shift from undesirable Nash equilibria to more favorable ones. We demonstrate the effectiveness and scalability of our approach on games of varying complexity, ranging from simple prototype games such as the Prisoner's Dilemma and Snowdrift games with two or more players to complex game configurations with as high as $10^6$ entries in the payoff matrix. These studies showcase the capability of this framework in efficiently identifying the alternative ways of reshaping strategic payoffs to secure desired Nash equilibria and preclude the undesired equilibrium states. Our game engineering framework offers a versatile toolkit for precision strategic decision-making with far-reaching implications across diverse domains.
Individual Text Corpora Predict Openness, Interests, Knowledge and Level of Education
Venue: arXiv cs.CL 2024
Year: 2024

Here we examine whether the personality dimension of openness to experience can be predicted from the individual google search history. By web scraping, individual text corpora (ICs) were generated from 214 participants with a mean number of 5 million word tokens. We trained word2vec models and used the similarities of each IC to label words, which were derived from a lexical approach of personality. These IC-label-word similarities were utilized as predictive features in neural models. For training and validation, we relied on 179 participants and held out a test sample of 35 participants. A grid search with varying number of predictive features, hidden units and boost factor was performed. As model selection criterion, we used R2 in the validation samples penalized by the absolute R2 difference between training and validation. The selected neural model explained 35% of the openness variance in the test sample, while an ensemble model with the same architecture often provided slightly more stable predictions for intellectual interests, knowledge in humanities and level of education. Finally, a learning curve analysis suggested that around 500 training participants are required for generalizable predictions. We discuss ICs as a complement or replacement of survey-based psychodiagnostics.
Word Ladders: A Mobile Application for Semantic Data Collection
Venue: arXiv cs.CL 2024
Year: 2024

Word Ladders is a free mobile application for Android and iOS, developed for collecting linguistic data, specifically lists of words related to each other through semantic relations of categorical inclusion, within the Abstraction project (ERC-2021-STG-101039777). We hereby provide an overview of Word Ladders, explaining its game logic, motivation and expected results and applications to nlp tasks as well as to the investigation of cognitive scientific open questions
Tools and Tasks in Sensemaking: A Visual Accessibility Perspective
Venue: arXiv cs.HC 2024
Year: 2024

Our previous interview study explores the needs and uses of diagrammatic information by the Blind and Low Vision (BLV) community, resulting in a framework called the Ladder of Diagram Access. The framework outlines five levels of information access when interacting with a diagram. In this paper, we connect this framework to include the global activity of sensemaking and discuss its (in)accessibility to the BLV demographic. We also discuss the integration of this framework into the sensemaking process and explore the current sensemaking practices and strategies employed by the BLV community, the challenges they face at different levels of the ladder, and potential solutions to enhance inclusivity towards a data-driven workforce.
Combined Static Analysis and Machine Learning Prediction for Application Debloating
Venue: arXiv cs.CR 2024
Year: 2024

Software debloating can effectively thwart certain code reuse attacks by reducing attack surfaces to break gadget chains. Approaches based on static analysis enable a reduced set of functions reachable at a callsite for execution by leveraging static properties of the callgraph. This achieves low runtime overhead, but the function set is conservatively computed, negatively affecting reduction. In contrast, approaches based on machine learning (ML) have much better precision and can sharply reduce function sets, leading to significant improvement in attack surface. Nevertheless, mispredictions occur in ML-based approaches. These cause overheads, and worse, there is no clear way to distinguish between mispredictions and actual attacks. In this work, we contend that a software debloating approach that incorporates ML-based predictions at runtime is realistic in a whole application setting, and that it can achieve significant attack surface reductions beyond the state of the art. We develop a framework, Predictive Debloat with Static Guarantees (PDSG). PDSG is fully sound and works on application source code. At runtime it predicts the dynamic callee set emanating from a callsite, and to resolve mispredictions, it employs a lightweight audit based on static invariants of call chains. We deduce the invariants offline and assert that they hold at runtime when there is a misprediction. To the best of our knowledge, it achieves the highest gadget reductions among similar techniques on SPEC CPU 2017, reducing 82.5% of the total gadgets on average. It triggers misprediction checks on only 3.8% of the total predictions invoked at runtime, and it leverages Datalog to verify dynamic call sequences conform to the static call relations. It has an overhead of 8.9%, which makes the scheme attractive for practical deployments.
No-Regret Learning for Stackelberg Equilibrium Computation in Newsvendor Pricing Games
Venue: arXiv cs.CE 2024
Year: 2024

We introduce the application of online learning in a Stackelberg game pertaining to a system with two learning agents in a dyadic exchange network, consisting of a supplier and retailer, specifically where the parameters of the demand function are unknown. In this game, the supplier is the first-moving leader, and must determine the optimal wholesale price of the product. Subsequently, the retailer who is the follower, must determine both the optimal procurement amount and selling price of the product. In the perfect information setting, this is known as the classical price-setting Newsvendor problem, and we prove the existence of a unique Stackelberg equilibrium when extending this to a two-player pricing game. In the framework of online learning, the parameters of the reward function for both the follower and leader must be learned, under the assumption that the follower will best respond with optimism under uncertainty. A novel algorithm based on contextual linear bandits with a measurable uncertainty set is used to provide a confidence bound on the parameters of the stochastic demand. Consequently, optimal finite time regret bounds on the Stackelberg regret, along with convergence guarantees to an approximate Stackelberg equilibrium, are provided.
Information Security and Privacy in the Digital World: Some Selected Topics
Venue: arXiv cs.CR 2024
Year: 2024

In the era of generative artificial intelligence and the Internet of Things, while there is explosive growth in the volume of data and the associated need for processing, analysis, and storage, several new challenges are faced in identifying spurious and fake information and protecting the privacy of sensitive data. This has led to an increasing demand for more robust and resilient schemes for authentication, integrity protection, encryption, non-repudiation, and privacy-preservation of data. The chapters in this book present some of the state-of-the-art research works in the field of cryptography and security in computing and communications.
DSFNet: Learning Disentangled Scenario Factorization for Multi-Scenario Route Ranking
Venue: arXiv cs.IR 2024
Year: 2024

Multi-scenario route ranking (MSRR) is crucial in many industrial mapping systems. However, the industrial community mainly adopts interactive interfaces to encourage users to select pre-defined scenarios, which may hinder the downstream ranking performance. In addition, in the academic community, the multi-scenario ranking works only come from other fields, and there are no works specifically focusing on route data due to lacking a publicly available MSRR dataset. Moreover, all the existing multi-scenario works still fail to address the three specific challenges of MSRR simultaneously, i.e. explosion of scenario number, high entanglement, and high-capacity demand. Different from the prior, to address MSRR, our key idea is to factorize the complicated scenario in route ranking into several disentangled factor scenario patterns. Accordingly, we propose a novel method, Disentangled Scenario Factorization Network (DSFNet), which flexibly composes scenario-dependent parameters based on a high-capacity multi-factor-scenario-branch structure. Then, a novel regularization is proposed to induce the disentanglement of factor scenarios. Furthermore, two extra novel techniques, i.e. scenario-aware batch normalization and scenario-aware feature filtering, are developed to improve the network awareness of scenario representation. Additionally, to facilitate MSRR research in the academic community, we propose MSDR, the first large-scale publicly available annotated industrial Multi-Scenario Driving Route dataset. Comprehensive experimental results demonstrate the superiority of our DSFNet, which has been successfully deployed in AMap to serve the major online traffic.
Environment-Aware Codebook for RIS-Assisted MU-MISO Communications: Implementation and Performance Analysis
Venue: arXiv cs.IT 2024
Year: 2024

Reconfigurable intelligent surface (RIS) provides a new electromagnetic response control solution, which can reshape the characteristics of wireless channels. In this paper, we propose a novel environment-aware codebook protocol for RIS-assisted multi-user multiple-input single-output (MU-MISO) systems. Specifically, we first introduce a channel training protocol which consists of off-line and on-line stages. Secondly, we propose an environment-aware codebook generation scheme, which utilizes the statistical channel state information and alternating optimization method to generate codewords offline. Then, in the on-line stage, we use these pre-designed codewords to configure the RIS, and the optimal codeword resulting in the highest sum rate is adopted for assisting in the downlink data transmission. Thirdly, we analyze the theoretical performance of the proposed protocol considering the channel estimation errors. Finally, numerical simulations are provided to verify our theoretical analysis and the performance of the proposed scheme.
Engineering A Workload-balanced Push-Relabel Algorithm for Massive Graphs on GPUs
Venue: arXiv cs.DC 2024
Year: 2024

The push-relabel algorithm is an efficient algorithm that solves the maximum flow/ minimum cut problems of its affinity to parallelization. As the size of graphs grows exponentially, researchers have used Graphics Processing Units (GPUs) to accelerate the computation of the push-relabel algorithm further. However, prior works need to handle the significant memory consumption to represent a massive residual graph. In addition, the nature of their algorithms has inherently imbalanced workload distribution on GPUs. This paper first identifies the two challenges with the memory and computational models. Based on the analysis of these models, we propose a workload-balanced push-relabel algorithm (WBPR) with two enhanced compressed sparse representations (CSR) and a vertex-centric approach. The enhanced CSR significantly reduces memory consumption, while the vertex-centric approach alleviates the workload imbalance and improves the utilization of the GPU. In the experiment, our approach reduces the memory consumption from O(V^2) to O(V + E). Moreover, we can achieve up to 7.31x and 2.29x runtime speedup compared to the state-of-the-art on real-world graphs in maximum flow and bipartite matching tasks, respectively. Our code will be open-sourced for further research on accelerating the push-relabel algorithm.
Instruction-Driven Game Engines on Large Language Models
Venue: arXiv cs.AI 2024
Year: 2024

The Instruction-Driven Game Engine (IDGE) project aims to democratize game development by enabling a large language model (LLM) to follow free-form game rules and autonomously generate game-play processes. The IDGE allows users to create games by issuing simple natural language instructions, which significantly lowers the barrier for game development. We approach the learning process for IDGEs as a Next State Prediction task, wherein the model autoregressively predicts in-game states given player actions. It is a challenging task because the computation of in-game states must be precise; otherwise, slight errors could disrupt the game-play. To address this, we train the IDGE in a curriculum manner that progressively increases the model's exposure to complex scenarios. Our initial progress lies in developing an IDGE for Poker, a universally cherished card game. The engine we've designed not only supports a wide range of poker variants but also allows for high customization of rules through natural language inputs. Furthermore, it also favors rapid prototyping of new games from minimal samples, proposing an innovative paradigm in game development that relies on minimal prompt and data engineering. This work lays the groundwork for future advancements in instruction-driven game creation, potentially transforming how games are designed and played.
Harmonizing Light and Darkness: A Symphony of Prior-guided Data Synthesis and Adaptive Focus for Nighttime Flare Removal
Venue: arXiv cs.CV 2024
Year: 2024

Intense light sources often produce flares in captured images at night, which deteriorates the visual quality and negatively affects downstream applications. In order to train an effective flare removal network, a reliable dataset is essential. The mainstream flare removal datasets are semi-synthetic to reduce human labour, but these datasets do not cover typical scenarios involving multiple scattering flares. To tackle this issue, we synthesize a prior-guided dataset named Flare7K*, which contains multi-flare images where the brightness of flares adheres to the laws of illumination. Besides, flares tend to occupy localized regions of the image but existing networks perform flare removal on the entire image and sometimes modify clean areas incorrectly. Therefore, we propose a plug-and-play Adaptive Focus Module (AFM) that can adaptively mask the clean background areas and assist models in focusing on the regions severely affected by flares. Extensive experiments demonstrate that our data synthesis method can better simulate real-world scenes and several models equipped with AFM achieve state-of-the-art performance on the real-world test dataset.
A Context-Sensitive, Outlier-Based Static Analysis to Find Kernel Race Conditions
Venue: arXiv cs.SE 2024
Year: 2024

Race conditions are a class of bugs in software where concurrent accesses to shared resources are not protected from each other. Consequences of race conditions include privilege escalation, denial of service, and memory corruption which can potentially lead to arbitrary code execution. However, in large code bases the exact rules as to which fields should be accessed under which locks are not always clear. We propose a novel static technique that infers rules for how field accesses should be locked, and then checks the code against these rules. Traditional static analysers for detecting race conditions are based on lockset analysis. Instead, we propose an outlier-based technique enhanced with a context-sensitive mechanism that scales well. We have implemented this analysis in LLIF, and evaluated it to find incorrectly protected field accesses in Linux v5.14.11. We thoroughly evaluate its ability to find race conditions, and study the causes for false positive reports. In addition, we reported a subset of the issues and submitted patches. The maintainers confirmed 24 bugs.