OpenRaiser/Intern-Atlas huggingface dataset:
SA-LSPL:Sequence-Aware Long- and Short- Term Preference Learning for next POI recommendation
Venue: arXiv cs.CY 2024
Year: 2024

The next Point of Interest (POI) recommendation aims to recommend the next POI for users at a specific time. As users' check-in records can be viewed as a long sequence, methods based on Recurrent Neural Networks (RNNs) have recently shown good applicability to this task. However, existing methods often struggle to fully explore the spatio-temporal correlations and dependencies at the sequence level, and don't take full consideration for various factors influencing users' preferences. To address these issues, we propose a novel approach called Sequence-Aware Long- and Short-Term Preference Learning (SA-LSPL) for next-POI recommendation. We combine various information features to effectively model users' long-term preferences. Specifically, our proposed model uses a multi-modal embedding module to embed diverse check-in details, taking into account both user's personalized preferences and social influences comprehensively. Additionally, we consider explicit spatio-temporal correlations at the sequence level and implicit sequence dependencies. Furthermore, SA-LSPL learns the spatio-temporal correlations of consecutive and non-consecutive visits in the current check-in sequence, as well as transition dependencies between categories, providing a comprehensive capture of user's short-term preferences. Extensive experiments on two real-world datasets demonstrate the superiority of SA-LSPL over state-of-the-art baseline methods.
CoDa: Constrained Generation based Data Augmentation for Low-Resource NLP
Venue: arXiv cs.CL 2024
Year: 2024

We present CoDa (Constrained Generation based Data Augmentation), a controllable, effective, and training-free data augmentation technique for low-resource (data-scarce) NLP. Our approach is based on prompting off-the-shelf instruction-following Large Language Models (LLMs) for generating text that satisfies a set of constraints. Precisely, we extract a set of simple constraints from every instance in the low-resource dataset and verbalize them to prompt an LLM to generate novel and diverse training instances. Our findings reveal that synthetic data that follows simple constraints in the downstream dataset act as highly effective augmentations, and CoDa can achieve this without intricate decoding-time constrained generation techniques or fine-tuning with complex algorithms that eventually make the model biased toward the small number of training instances. Additionally, CoDa is the first framework that provides users explicit control over the augmentation generation process, thereby also allowing easy adaptation to several domains. We demonstrate the effectiveness of CoDa across 11 datasets spanning 3 tasks and 3 low-resource settings. CoDa outperforms all our baselines, qualitatively and quantitatively, with improvements of 0.12%-7.19%. Code is available here: https://github.com/Sreyan88/CoDa
Circular-arc graphs and the Helly property
Venue: arXiv cs.DS 2024
Year: 2024

In this paper we investigate some problems related to the Helly properties of circular-arc graphs, which are defined as intersection graphs of arcs of a fixed circle. As such, circular-arc graphs are among the simplest classes of intersection graphs whose models might not satisfy the Helly property. In particular, some cliques of a circular-arc graph might be Helly in some but not all arc intersection models of the graph. Our first result is an alternative proof of a theorem by Lin and Szwarcfiter which asserts that for every circular-arc graph $G$ either every normalized model of $G$ satisfies the Helly property or no normalized model of $G$ satisfies this property. Further, we study the Helly properties of a single clique of a circular-arc graph $G$. We divide the cliques of $G$ into three types: a clique $C$ of $G$ is always-Helly/always-non-Helly/ambiguous if $C$ is Helly in every/no/(some but not all) normalized model of $G$. We provide a combinatorial description for the cliques of each type, and based on it, we devise a polynomial time algorithm which determines the type of a given clique. Finally, we study the Helly Cliques problem, in which we are given an $n$-vertex circular-arc graph $G$ and some of its cliques $C_1, \ldots, C_k$ and we ask if there is an arc intersection model of $G$ in which all the cliques $C_1, \ldots, C_k$ satisfy the Helly property. We show that: (1) the Helly Cliques problem admits a $2^{O(k\log{k})}n^{O(1)}$-time algorithm (that is, it is FPT when parametrized by the number of cliques given in the input), (2) assuming Exponential Time Hypothesis (ETH), the Helly Cliques problem cannot be solved in time $2^{o(k)}n^{O(1)}$, (3) the Helly Cliques problem admits a polynomial kernel of size $O(k^6)$. All our results use a data structure, called a PQM-tree, which maintains all normalized models of a circular-arc graph $G$.
Keep your memory dump shut: Unveiling data leaks in password managers
Venue: arXiv cs.CR 2024
Year: 2024

Password management has long been a persistently challenging task. This led to the introduction of password management software, which has been around for at least 25 years in various forms, including desktop and browser-based applications. This work assesses the ability of two dozen password managers, 12 desktop applications, and 12 browser-plugins, to effectively protect the confidentiality of secret credentials in six representative scenarios. Our analysis focuses on the period during which a Password Manager (PM) resides in the RAM. Despite the sensitive nature of these applications, our results show that across all scenarios, only three desktop PM applications and two browser plugins do not store plaintext passwords in the system memory. Oddly enough, at the time of writing, only two vendors recognized the exploit as a vulnerability, reserving CVE-2023-23349, while the rest chose to disregard or underrate the issue.
Towards a Semantic Characterisation of Global Type Well-formedness
Venue: arXiv cs.LO 2024
Year: 2024

We address the question of characterising the well-formedness properties of multiparty session types semantically, i.e., as properties of the semantic model used to interpret types. Choosing Prime Event Structures (PESs) as our semantic model, we present semantic counterparts for the two properties that underpin global type well-formedness, namely projectability and boundedness, in this model. As a first step towards a characterisation of the class of PESs corresponding to well-formed global types, we identify some simple structural properties satisfied by such PESs.
Planning and Editing What You Retrieve for Enhanced Tool Learning
Venue: arXiv cs.CL 2024
Year: 2024

Recent advancements in integrating external tools with Large Language Models (LLMs) have opened new frontiers, with applications in mathematical reasoning, code generators, and smart assistants. However, existing methods, relying on simple one-time retrieval strategies, fall short on effectively and accurately shortlisting relevant tools. This paper introduces a novel PLUTO (Planning, Learning, and Understanding for TOols) approach, encompassing `Plan-and-Retrieve (P&R)` and `Edit-and-Ground (E&G)` paradigms. The P&R paradigm consists of a neural retrieval module for shortlisting relevant tools and an LLM-based query planner that decomposes complex queries into actionable tasks, enhancing the effectiveness of tool utilization. The E&G paradigm utilizes LLMs to enrich tool descriptions based on user scenarios, bridging the gap between user queries and tool functionalities. Experiment results demonstrate that these paradigms significantly improve the recall and NDCG in tool retrieval tasks, significantly surpassing current state-of-the-art models.
Eclipse Attack Detection on a Blockchain Network as a Non-Parametric Change Detection Problem
Venue: arXiv cs.CR 2024
Year: 2024

This paper introduces a novel non-parametric change detection algorithm to identify eclipse attacks on a blockchain network; the non-parametric algorithm relies only on the empirical mean and variance of the dataset, making it highly adaptable. An eclipse attack occurs when malicious actors isolate blockchain users, disrupting their ability to reach consensus with the broader network, thereby distorting their local copy of the ledger. To detect an eclipse attack, we monitor changes in the Fréchet mean and variance of the evolving blockchain communication network connecting blockchain users. First, we leverage the Johnson-Lindenstrauss lemma to project large-dimensional networks into a lower-dimensional space, preserving essential statistical properties. Subsequently, we employ a non-parametric change detection procedure, leading to a test statistic that converges weakly to a Brownian bridge process in the absence of an eclipse attack. This enables us to quantify the false alarm rate of the detector. Our detector can be implemented as a smart contract on the blockchain, offering a tamper-proof and reliable solution. Finally, we use numerical examples to compare the proposed eclipse attack detector with a detector based on the random forest model.
Deep Extrinsic Manifold Representation for Vision Tasks
Venue: arXiv cs.CV 2024
Year: 2024

Non-Euclidean data is frequently encountered across different fields, yet there is limited literature that addresses the fundamental challenge of training neural networks with manifold representations as outputs. We introduce the trick named Deep Extrinsic Manifold Representation (DEMR) for visual tasks in this context. DEMR incorporates extrinsic manifold embedding into deep neural networks, which helps generate manifold representations. The DEMR approach does not directly optimize the complex geodesic loss. Instead, it focuses on optimizing the computation graph within the embedded Euclidean space, allowing for adaptability to various architectural requirements. We provide empirical evidence supporting the proposed concept on two types of manifolds, $SE(3)$ and its associated quotient manifolds. This evidence offers theoretical assurances regarding feasibility, asymptotic properties, and generalization capability. The experimental results show that DEMR effectively adapts to point cloud alignment, producing outputs in $ SE(3) $, as well as in illumination subspace learning with outputs on the Grassmann manifold.
A Theory for Length Generalization in Learning to Reason
Venue: arXiv cs.AI 2024
Year: 2024

Length generalization (LG) is a challenging problem in learning to reason. It refers to the phenomenon that when trained on reasoning problems of smaller lengths or sizes, the resulting model struggles with problems of larger sizes or lengths. Although LG has been studied by many researchers, the challenge remains. This paper proposes a theoretical study of LG for problems whose reasoning processes can be modeled as DAGs (directed acyclic graphs). The paper first identifies and proves the conditions under which LG can be achieved in learning to reason. It then designs problem representations based on the theory to learn to solve challenging reasoning problems like parity, addition, and multiplication, using a Transformer to achieve perfect LG.
Leveraging Corpus Metadata to Detect Template-based Translation: An Exploratory Case Study of the Egyptian Arabic Wikipedia Edition
Venue: arXiv cs.CL 2024
Year: 2024

Wikipedia articles (content pages) are commonly used corpora in Natural Language Processing (NLP) research, especially in low-resource languages other than English. Yet, a few research studies have studied the three Arabic Wikipedia editions, Arabic Wikipedia (AR), Egyptian Arabic Wikipedia (ARZ), and Moroccan Arabic Wikipedia (ARY), and documented issues in the Egyptian Arabic Wikipedia edition regarding the massive automatic creation of its articles using template-based translation from English to Arabic without human involvement, overwhelming the Egyptian Arabic Wikipedia with articles that do not only have low-quality content but also with articles that do not represent the Egyptian people, their culture, and their dialect. In this paper, we aim to mitigate the problem of template translation that occurred in the Egyptian Arabic Wikipedia by identifying these template-translated articles and their characteristics through exploratory analysis and building automatic detection systems. We first explore the content of the three Arabic Wikipedia editions in terms of density, quality, and human contributions and utilize the resulting insights to build multivariate machine learning classifiers leveraging articles' metadata to detect the template-translated articles automatically. We then publicly deploy and host the best-performing classifier, XGBoost, as an online application called EGYPTIAN WIKIPEDIA SCANNER and release the extracted, filtered, and labeled datasets to the research community to benefit from our datasets and the online, web-based detection system.
LAESI: Leaf Area Estimation with Synthetic Imagery
Venue: arXiv cs.CV 2024
Year: 2024

We introduce LAESI, a Synthetic Leaf Dataset of 100,000 synthetic leaf images on millimeter paper, each with semantic masks and surface area labels. This dataset provides a resource for leaf morphology analysis primarily aimed at beech and oak leaves. We evaluate the applicability of the dataset by training machine learning models for leaf surface area prediction and semantic segmentation, using real images for validation. Our validation shows that these models can be trained to predict leaf surface area with a relative error not greater than an average human annotator. LAESI also provides an efficient framework based on 3D procedural models and generative AI for the large-scale, controllable generation of data with potential further applications in agriculture and biology. We evaluate the inclusion of generative AI in our procedural data generation pipeline and show how data filtering based on annotation consistency results in datasets which allow training the highest performing vision models.
On $(θ, Θ)$-cyclic codes and their applications in constructing QECCs
Venue: arXiv cs.IT 2024
Year: 2024

Let $\mathbb F_q$ be a finite field, where $q$ is an odd prime power. Let $R=\mathbb{F}_q+u\mathbb{F}_q+v\mathbb{F}_q+uv\mathbb F_q$ with $u^2=u,v^2=v,uv=vu$. In this paper, we study the algebraic structure of $(θ, Θ)$-cyclic codes of block length $(r,s )$ over $\mathbb{F}_qR.$ Specifically, we analyze the structure of these codes as left $R[x:Θ]$-submodules of $\mathfrak{R}_{r,s} = \frac{\mathbb{F}_q[x:θ]}{\langle x^r-1\rangle} \times \frac{R[x:Θ]}{\langle x^s-1\rangle}$. Our investigation involves determining generator polynomials and minimal generating sets for this family of codes. Further, we discuss the algebraic structure of separable codes. A relationship between the generator polynomials of $(θ, Θ)$-cyclic codes over $\mathbb F_qR$ and their duals is established. Moreover, we calculate the generator polynomials of dual of $(θ, Θ)$-cyclic codes. As an application of our study, we provide a construction of quantum error-correcting codes (QECCs) from $(θ, Θ)$-cyclic codes of block length $(r,s)$ over $\mathbb{F}_qR$. We support our theoretical results with illustrative examples.
RL-MUL 2.0: Multiplier Design Optimization with Parallel Deep Reinforcement Learning and Space Reduction
Venue: arXiv cs.AR 2024
Year: 2024

Multiplication is a fundamental operation in many applications, and multipliers are widely adopted in various circuits. However, optimizing multipliers is challenging due to the extensive design space. In this paper, we propose a multiplier design optimization framework based on reinforcement learning. We utilize matrix and tensor representations for the compressor tree of a multiplier, enabling seamless integration of convolutional neural networks as the agent network. The agent optimizes the multiplier structure using a Pareto-driven reward customized to balance area and delay. Furthermore, we enhance the original framework with parallel reinforcement learning and design space pruning techniques and extend its capability to optimize fused multiply-accumulate (MAC) designs. Experiments conducted on different bit widths of multipliers demonstrate that multipliers produced by our approach outperform all baseline designs in terms of area, power, and delay. The performance gain is further validated by comparing the area, power, and delay of processing element arrays using multipliers from our approach and baseline approaches.
DeeDSR: Towards Real-World Image Super-Resolution via Degradation-Aware Stable Diffusion
Venue: arXiv cs.CV 2024
Year: 2024

Diffusion models, known for their powerful generative capabilities, play a crucial role in addressing real-world super-resolution challenges. However, these models often focus on improving local textures while neglecting the impacts of global degradation, which can significantly reduce semantic fidelity and lead to inaccurate reconstructions and suboptimal super-resolution performance. To address this issue, we introduce a novel two-stage, degradation-aware framework that enhances the diffusion model's ability to recognize content and degradation in low-resolution images. In the first stage, we employ unsupervised contrastive learning to obtain representations of image degradations. In the second stage, we integrate a degradation-aware module into a simplified ControlNet, enabling flexible adaptation to various degradations based on the learned representations. Furthermore, we decompose the degradation-aware features into global semantics and local details branches, which are then injected into the diffusion denoising module to modulate the target generation. Our method effectively recovers semantically precise and photorealistic details, particularly under significant degradation conditions, demonstrating state-of-the-art performance across various benchmarks. Codes will be released at https://github.com/bichunyang419/DeeDSR.
Statistical Analysis by Semiparametric Additive Regression and LSTM-FCN Based Hierarchical Classification for Computer Vision Quantification of Parkinsonian Bradykinesia
Venue: arXiv cs.CV 2024
Year: 2024

Bradykinesia, characterized by involuntary slowing or decrement of movement, is a fundamental symptom of Parkinson's Disease (PD) and is vital for its clinical diagnosis. Despite various methodologies explored to quantify bradykinesia, computer vision-based approaches have shown promising results. However, these methods often fall short in adequately addressing key bradykinesia characteristics in repetitive limb movements: "occasional arrest" and "decrement in amplitude." This research advances vision-based quantification of bradykinesia by introducing nuanced numerical analysis to capture decrement in amplitudes and employing a simple deep learning technique, LSTM-FCN, for precise classification of occasional arrests. Our approach structures the classification process hierarchically, tailoring it to the unique dynamics of bradykinesia in PD. Statistical analysis of the extracted features, including those representing arrest and fatigue, has demonstrated their statistical significance in most cases. This finding underscores the importance of considering "occasional arrest" and "decrement in amplitude" in bradykinesia quantification of limb movement. Our enhanced diagnostic tool has been rigorously tested on an extensive dataset comprising 1396 motion videos from 310 PD patients, achieving an accuracy of 80.3%. The results confirm the robustness and reliability of our method.
Meta Learning in Bandits within Shared Affine Subspaces
Venue: arXiv cs.LG 2024
Year: 2024

We study the problem of meta-learning several contextual stochastic bandits tasks by leveraging their concentration around a low-dimensional affine subspace, which we learn via online principal component analysis to reduce the expected regret over the encountered bandits. We propose and theoretically analyze two strategies that solve the problem: One based on the principle of optimism in the face of uncertainty and the other via Thompson sampling. Our framework is generic and includes previously proposed approaches as special cases. Besides, the empirical results show that our methods significantly reduce the regret on several bandit tasks.
Sponge: Inference Serving with Dynamic SLOs Using In-Place Vertical Scaling
Venue: arXiv cs.DC 2024
Year: 2024

Mobile and IoT applications increasingly adopt deep learning inference to provide intelligence. Inference requests are typically sent to a cloud infrastructure over a wireless network that is highly variable, leading to the challenge of dynamic Service Level Objectives (SLOs) at the request level. This paper presents Sponge, a novel deep learning inference serving system that maximizes resource efficiency while guaranteeing dynamic SLOs. Sponge achieves its goal by applying in-place vertical scaling, dynamic batching, and request reordering. Specifically, we introduce an Integer Programming formulation to capture the resource allocation problem, providing a mathematical model of the relationship between latency, batch size, and resources. We demonstrate the potential of Sponge through a prototype implementation and preliminary experiments and discuss future works.
Neural Radiance Field-based Visual Rendering: A Comprehensive Review
Venue: arXiv cs.CV 2024
Year: 2024

In recent years, Neural Radiance Fields (NeRF) has made remarkable progress in the field of computer vision and graphics, providing strong technical support for solving key tasks including 3D scene understanding, new perspective synthesis, human body reconstruction, robotics, and so on, the attention of academics to this research result is growing. As a revolutionary neural implicit field representation, NeRF has caused a continuous research boom in the academic community. Therefore, the purpose of this review is to provide an in-depth analysis of the research literature on NeRF within the past two years, to provide a comprehensive academic perspective for budding researchers. In this paper, the core architecture of NeRF is first elaborated in detail, followed by a discussion of various improvement strategies for NeRF, and case studies of NeRF in diverse application scenarios, demonstrating its practical utility in different domains. In terms of datasets and evaluation metrics, This paper details the key resources needed for NeRF model training. Finally, this paper provides a prospective discussion on the future development trends and potential challenges of NeRF, aiming to provide research inspiration for researchers in the field and to promote the further development of related technologies.
Opera Graeca Adnotata: Building a 34M+ Token Multilayer Corpus for Ancient Greek
Venue: arXiv cs.CL 2024
Year: 2024

In this article, the beta version 0.1.0 of Opera Graeca Adnotata (OGA), the largest open-access multilayer corpus for Ancient Greek (AG) is presented. OGA consists of 1,687 literary works and 34M+ tokens coming from the PerseusDL and OpenGreekAndLatin GitHub repositories, which host AG texts ranging from about 800 BCE to about 250 CE. The texts have been enriched with seven annotation layers: (i) tokenization layer; (ii) sentence segmentation layer; (iii) lemmatization layer; (iv) morphological layer; (v) dependency layer; (vi) dependency function layer; (vii) Canonical Text Services (CTS) citation layer. The creation of each layer is described by highlighting the main technical and annotation-related issues encountered. Tokenization, sentence segmentation, and CTS citation are performed by rule-based algorithms, while morphosyntactic annotation is the output of the COMBO parser trained on the data of the Ancient Greek Dependency Treebank. For the sake of scalability and reusability, the corpus is released in the standoff formats PAULA XML and its offspring LAULA XML.