OpenRaiser/Intern-Atlas huggingface dataset:
Existential Calculi of Relations with Transitive Closure: Complexity and Edge Saturations
Venue: arXiv cs.LO 2023
Year: 2023

We study the decidability and complexity of equational theories of the existential calculus of relations with transitive closure (ECoR*) and its fragments, where ECoR* is the positive calculus of relations with transitive closure extended with complements of term variables and constants. We give characterizations of these equational theories by using edge saturations and we show that the equational theory is 1) coNP-complete for ECoR* without transitive closure; 2) in coNEXP for ECoR* without intersection and PSPACE-complete for two smaller fragments; 3) $Π_{1}^{0}$-complete for ECoR*. The second result gives PSPACE-upper bounds for some extensions of Kleene algebra, including Kleene algebra with top w.r.t. binary relations.
Deep Audio-Visual Singing Voice Transcription based on Self-Supervised Learning Models
Venue: arXiv cs.SD 2023
Year: 2023

Singing voice transcription converts recorded singing audio to musical notation. Sound contamination (such as accompaniment) and lack of annotated data make singing voice transcription an extremely difficult task. We take two approaches to tackle the above challenges: 1) introducing multimodal learning for singing voice transcription together with a new multimodal singing dataset, N20EMv2, enhancing noise robustness by utilizing video information (lip movements to predict the onset/offset of notes), and 2) adapting self-supervised learning models from the speech domain to the singing voice transcription task, significantly reducing annotated data requirements while preserving pretrained features. We build a self-supervised learning based audio-only singing voice transcription system, which not only outperforms current state-of-the-art technologies as a strong baseline, but also generalizes well to out-of-domain singing data. We then develop a self-supervised learning based video-only singing voice transcription system that detects note onsets and offsets with an accuracy of about 80\%. Finally, based on the powerful acoustic and visual representations extracted by the above two systems as well as the feature fusion design, we create an audio-visual singing voice transcription system that improves the noise robustness significantly under different acoustic environments compared to the audio-only systems.
Unlocking Context Constraints of LLMs: Enhancing Context Efficiency of LLMs with Self-Information-Based Content Filtering
Venue: arXiv cs.CL 2023
Year: 2023

Large language models (LLMs) have received significant attention by achieving remarkable performance across various tasks. However, their fixed context length poses challenges when processing long documents or maintaining extended conversations. This paper proposes a method called \textit{Selective Context} that employs self-information to filter out less informative content, thereby enhancing the efficiency of the fixed context length. We demonstrate the effectiveness of our approach on tasks of summarisation and question answering across different data sources, including academic papers, news articles, and conversation transcripts.
Pseudorandom Finite Models
Venue: arXiv cs.LO 2023
Year: 2023

We study pseudorandomness and pseudorandom generators from the perspective of logical definability. Building on results from ordinary derandomization and finite model theory, we show that it is possible to deterministically construct, in polynomial time, graphs and relational structures that are statistically indistinguishable from random structures by any sentence of first order or least fixed point logics. This raises the question of whether such constructions can be implemented via logical transductions from simpler structures with less entropy. In other words, can logical formulas be pseudorandom generators? We provide a complete classification of when this is possible for first order logic, fixed point logic, and fixed point logic with parity, and provide partial results and conjectures for first order logic with parity.
SQLi Detection with ML: A data-source perspective
Venue: arXiv cs.CR 2023
Year: 2023

Almost 50 years after the invention of SQL, injection attacks are still top-tier vulnerabilities of today's ICT systems. Consequently, SQLi detection is still an active area of research, where the most recent works incorporate machine learning techniques into the proposed solutions. In this work, we highlight the shortcomings of the previous ML-based results focusing on four aspects: the evaluation methods, the optimization of the model parameters, the distribution of utilized datasets, and the feature selection. Since no single work explored all of these aspects satisfactorily, we fill this gap and provide an in-depth and comprehensive empirical analysis. Moreover, we cross-validate the trained models by using data from other distributions. This aspect of ML models (trained for SQLi detection) was never studied. Yet, the sensitivity of the model's performance to this is crucial for any real-life deployment. Finally, we validate our findings on a real-world industrial SQLi dataset.
Anserini Gets Dense Retrieval: Integration of Lucene's HNSW Indexes
Venue: arXiv cs.IR 2023
Year: 2023

Anserini is a Lucene-based toolkit for reproducible information retrieval research in Java that has been gaining traction in the community. It provides retrieval capabilities for both "traditional" bag-of-words retrieval models such as BM25 as well as retrieval using learned sparse representations such as SPLADE. With Pyserini, which provides a Python interface to Anserini, users gain access to both sparse and dense retrieval models, as Pyserini implements bindings to the Faiss vector search library alongside Lucene inverted indexes in a uniform, consistent interface. Nevertheless, hybrid fusion techniques that integrate sparse and dense retrieval models need to stitch together results from two completely different "software stacks", which creates unnecessary complexities and inefficiencies. However, the introduction of HNSW indexes for dense vector search in Lucene promises the integration of both dense and sparse retrieval within a single software framework. We explore exactly this integration in the context of Anserini. Experiments on the MS MARCO passage and BEIR datasets show that our Anserini HNSW integration supports (reasonably) effective and (reasonably) efficient approximate nearest neighbor search for dense retrieval models, using only Lucene.
The African Stopwords project: curating stopwords for African languages
Venue: arXiv cs.CL 2023
Year: 2023

Stopwords are fundamental in Natural Language Processing (NLP) techniques for information retrieval. One of the common tasks in preprocessing of text data is the removal of stopwords. Currently, while high-resource languages like English benefit from the availability of several stopwords, low-resource languages, such as those found in the African continent, have none that are standardized and available for use in NLP packages. Stopwords in the context of African languages are understudied and can reveal information about the crossover between languages. The \textit{African Stopwords} project aims to study and curate stopwords for African languages. In this paper, we present our current progress on ten African languages as well as future plans for the project.
Periodicity Analysis of the Logistic Map over Ring $\mathbb{Z}_{3^n}$
Venue: arXiv cs.IT 2023
Year: 2023

Periodicity analysis of sequences generated by a deterministic system is a long-standing challenge in both theoretical research and engineering applications. To overcome the inevitable degradation of the Logistic map on a finite-precision circuit, its numerical domain is commonly converted from a real number field to a ring or a finite field. This paper studies the period of sequences generated by iterating the Logistic map over ring $\mathbb{Z}_{3^n}$ from the perspective of its associate functional network, where every number in the ring is considered as a node, and the existing mapping relation between any two nodes is regarded as a directed edge. The complete explicit form of the period of the sequences starting from any initial value is given theoretically and verified experimentally. Moreover, conditions on the control parameter and initial value are derived, ensuring the corresponding sequences to achieve the maximum period over the ring. The results can be used as ground truth for dynamical analysis and cryptographical applications of the Logistic map over various domains.
Overview of the TREC 2022 NeuCLIR Track
Venue: arXiv cs.IR 2023
Year: 2023

This is the first year of the TREC Neural CLIR (NeuCLIR) track, which aims to study the impact of neural approaches to cross-language information retrieval. The main task in this year's track was ad hoc ranked retrieval of Chinese, Persian, or Russian newswire documents using queries expressed in English. Topics were developed using standard TREC processes, except that topics developed by an annotator for one language were assessed by a different annotator when evaluating that topic on a different language. There were 172 total runs submitted by twelve teams.
Recognizing and generating unswitchable graphs
Venue: arXiv cs.DS 2023
Year: 2023

In this paper, we show that unswitchable graphs are a proper subclass of split graphs, and exploit this fact to propose efficient algorithms for their recognition and generation.
Codes Correcting a Single Long Duplication Error
Venue: arXiv cs.IT 2023
Year: 2023

We consider the problem of constructing a code capable of correcting a single long tandem duplication error of variable length. As the main contribution of this paper, we present a $q$-ary efficiently encodable code of length $n+1$ and redundancy $1$ that can correct a single duplication of length at least $K=4\cdot\lceil \log_q n\rceil +1$. The complexity of encoding is $O(\frac{n^2}{\log n})$ and the complexity of decoding is $O(n)$. We also present a $q$-ary non-efficient code of length $n+1$ correcting single long duplication of length at least $K = \lceil \log_q n\rceil +ϕ(n)$, where $ϕ(n)\rightarrow{\infty}$ as $n\rightarrow{\infty}$. This code has redundancy less than $1$ for sufficiently large $n$. Moreover, we show that in the class of codes correcting a single long duplication with redundancy $1$, the value $K$ in our constructions is order-optimal.
Autonomous Intelligent Cyber-defense Agent: Introduction and Overview
Venue: arXiv cs.CR 2023
Year: 2023

This chapter introduces the concept of Autonomous Intelligent Cyber-defense Agents (AICAs), and briefly explains the importance of this field and the motivation for its emergence. AICA is a software agent that resides on a system, and is responsible for defending the system from cyber compromises and enabling the response and recovery of the system, usually autonomously. The autonomy of the agent is a necessity because of the growing scarcity of human cyber-experts who could defend systems, either remotely or onsite, and because sophisticated malware could degrade or spoof the communications of a system that uses a remote monitoring center. An AICA Reference Architecture has been proposed and defines five main functions: (1) sensing and world state identification, (2) planning and action selection, (3) collaboration and negotiation, (4) action execution and (5) learning and knowledge improvement. The chapter reviews the details of AICA's environment, functions and operations. As AICA is intended to make changes within its environment, there is a risk that an agent's action could harm a friendly computer. This risk must be balanced against the losses that could occur if the agent does not act. The chapter discusses means by which this risk can be managed and how AICA's design features could help build trust among its users.
PEFT-Ref: A Modular Reference Architecture and Typology for Parameter-Efficient Finetuning Techniques
Venue: arXiv cs.CL 2023
Year: 2023

Recent parameter-efficient finetuning (PEFT) techniques aim to improve over the considerable cost of fully finetuning large pretrained language models (PLM). As different PEFT techniques proliferate, it is becoming difficult to compare them, in particular in terms of (i) the structure and functionality they add to the PLM, (ii) the different types and degrees of efficiency improvements achieved, (iii) performance at different downstream tasks, and (iv) how differences in structure and functionality relate to efficiency and task performance. To facilitate such comparisons, this paper presents a reference architecture which standardises aspects shared by different PEFT techniques, while isolating differences to specific locations and interactions with the standard components. Through this process of standardising and isolating differences, a modular view of PEFT techniques emerges, supporting not only direct comparison of different techniques and their efficiency and task performance, but also systematic exploration of reusability and composability of the different types of finetuned modules. We demonstrate how the reference architecture can be applied to understand properties and relative advantages of PEFT techniques, hence to inform selection of techniques for specific tasks, and design choices for new PEFT techniques.
ChatGPT (Feb 13 Version) is a Chinese Room
Venue: arXiv cs.CL 2023
Year: 2023

ChatGPT has gained both positive and negative publicity after reports suggesting that it is able to pass various professional and licensing examinations. This suggests that ChatGPT may pass Turing Test in the near future. However, a computer program that passing Turing Test can either mean that it is a Chinese Room or artificially conscious. Hence, the question of whether the current state of ChatGPT is more of a Chinese Room or approaching artificial consciousness remains. Here, I demonstrate that the current version of ChatGPT (Feb 13 version) is a Chinese Room. Despite potential evidence of cognitive connections, ChatGPT exhibits critical errors in causal reasoning. At the same time, I demonstrate that ChatGPT can generate all possible categorical responses to the same question and response with erroneous examples; thus, questioning its utility as a learning tool. I also show that ChatGPT is capable of artificial hallucination, which is defined as generating confidently wrong replies. It is likely that errors in causal reasoning leads to hallucinations. More critically, ChatGPT generates false references to mimic real publications. Therefore, its utility is cautioned.
TIGTEC : Token Importance Guided TExt Counterfactuals
Venue: arXiv cs.LG 2023
Year: 2023

Counterfactual examples explain a prediction by highlighting changes of instance that flip the outcome of a classifier. This paper proposes TIGTEC, an efficient and modular method for generating sparse, plausible and diverse counterfactual explanations for textual data. TIGTEC is a text editing heuristic that targets and modifies words with high contribution using local feature importance. A new attention-based local feature importance is proposed. Counterfactual candidates are generated and assessed with a cost function integrating semantic distance, while the solution space is efficiently explored in a beam search fashion. The conducted experiments show the relevance of TIGTEC in terms of success rate, sparsity, diversity and plausibility. This method can be used in both model-specific or model-agnostic way, which makes it very convenient for generating counterfactual explanations.
Two Decreasing Measures for Simply Typed Lambda-Terms (Extended Version)
Venue: arXiv cs.LO 2023
Year: 2023

This paper defines two decreasing measures for terms of the simply typed lambda-calculus, called the W-measure and the Tm-measure. A decreasing measure is a function that maps each typable lambda-term to an element of a well-founded ordering, in such a way that contracting any beta-redex decreases the value of the function, entailing strong normalization. Both measures are defined constructively, relying on an auxiliary calculus, a non-erasing variant of the lambda-calculus. In this system, dubbed the m-calculus, each beta-step creates a "wrapper" containing a copy of the argument that cannot be erased and cannot interact with the context in any other way. Both measures rely crucially on the observation, known to Turing and Prawitz, that contracting a redex cannot create redexes of higher degree, where the degree of a redex is defined as the height of the type of its lambda-abstraction. The W-measure maps each lambda-term to a natural number, and it is obtained by evaluating the term in the m-calculus and counting the number of remaining wrappers. The Tm-measure maps each lambda-term to a structure of nested multisets, where the nesting depth is proportional to the maximum redex degree.
Semantic Compression With Large Language Models
Venue: arXiv cs.AI 2023
Year: 2023

The rise of large language models (LLMs) is revolutionizing information retrieval, question answering, summarization, and code generation tasks. However, in addition to confidently presenting factually inaccurate information at times (known as "hallucinations"), LLMs are also inherently limited by the number of input and output tokens that can be processed at once, making them potentially less effective on tasks that require processing a large set or continuous stream of information. A common approach to reducing the size of data is through lossless or lossy compression. Yet, in some cases it may not be strictly necessary to perfectly recover every detail from the original data, as long as a requisite level of semantic precision or intent is conveyed. This paper presents three contributions to research on LLMs. First, we present the results from experiments exploring the viability of approximate compression using LLMs, focusing specifically on GPT-3.5 and GPT-4 via ChatGPT interfaces. Second, we investigate and quantify the capability of LLMs to compress text and code, as well as to recall and manipulate compressed representations of prompts. Third, we present two novel metrics -- Exact Reconstructive Effectiveness (ERE) and Semantic Reconstruction Effectiveness (SRE) -- that quantify the level of preserved intent between text compressed and decompressed by the LLMs we studied. Our initial results indicate that GPT-4 can effectively compress and reconstruct text while preserving the semantic essence of the original text, providing a path to leverage $\sim$5$\times$ more tokens than present limits allow.
SEA: A Spatially Explicit Architecture for Multi-Agent Reinforcement Learning
Venue: arXiv cs.MA 2023
Year: 2023

Spatial information is essential in various fields. How to explicitly model according to the spatial location of agents is also very important for the multi-agent problem, especially when the number of agents is changing and the scale is enormous. Inspired by the point cloud task in computer vision, we propose a spatial information extraction structure for multi-agent reinforcement learning in this paper. Agents can effectively share the neighborhood and global information through a spatially encoder-decoder structure. Our method follows the centralized training with decentralized execution (CTDE) paradigm. In addition, our structure can be applied to various existing mainstream reinforcement learning algorithms with minor modifications and can deal with the problem with a variable number of agents. The experiments in several multi-agent scenarios show that the existing methods can get convincing results by adding our spatially explicit architecture.
Opinion Control under Adversarial Network Perturbation: A Stackelberg Game Approach
Venue: arXiv cs.CY 2023
Year: 2023

The emerging social network platforms enable users to share their own opinions, as well as to exchange opinions with others. However, adversarial network perturbation, where malicious users intentionally spread their extreme opinions, rumors, and misinformation to others, is ubiquitous in social networks. Such adversarial network perturbation greatly influences the opinion formation of the public and threatens our societies. Thus, it is critical to study and control the influence of adversarial network perturbation. Although tremendous efforts have been made in both academia and industry to guide and control the public opinion dynamics, most of these works assume that the network is static, and ignore such adversarial network perturbation. In this work, based on the well-accepted Friedkin-Johnsen opinion dynamics model, we model the adversarial network perturbation and analyze its impact on the networks' opinion. Then, from the adversary's perspective, we analyze its optimal network perturbation, which maximally changes the network's opinion. Next, from the network defender's perspective, we formulate a Stackelberg game and aim to control the network's opinion even under such adversarial network perturbation. We devise a projected subgradient algorithm to solve the formulated Stackelberg game. Extensive simulations on real social networks validate our analysis of the adversarial network perturbation's influence and the effectiveness of the proposed opinion control algorithm.
Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction
Venue: arXiv cs.DS 2023
Year: 2023

Streaming graphs are drawing increasing attention in both academic and industrial communities as many graphs in real applications evolve over time. Continuous subgraph matching (shorted as CSM) aims to report the incremental matches of a query graph in such streaming graphs. It involves two major steps, i.e., candidate maintenance and incremental match generation, to answer CSM. Throughout the course of continuous subgraph matching, incremental match generation backtracking over the search space dominates the total cost. However, most previous approaches focus on developing techniques for efficient candidate maintenance, while incremental match generation receives less attention despite its importance in CSM. Aiming to minimize the overall cost, we propose two techniques to reduce backtrackings in this paper. We present a cost-effective index CaLiG that yields tighter candidate maintenance, shrinking the search space of backtracking. In addition, we develop a novel incremental matching paradigm KSS that decomposes the query vertices into conditional kernel vertices and shell vertices. With the matches of kernel vertices, the incremental matches can be produced immediately by joining the candidates of shell vertices without any backtrackings. Benefiting from reduced backtrackings, the elapsed time of CSM decreases significantly. Extensive experiments over real graphs show that our method runs faster than the state-of-the-art algorithm orders of magnitude.
Using Intent Estimation and Decision Theory to Support Lifting Motions with a Quasi-Passive Hip Exoskeleton
Venue: arXiv cs.RO 2023
Year: 2023

This paper compares three controllers for quasi-passive exoskeletons. The Utility Maximizing Controller (UMC) uses intent estimation to recognize user motions and decision theory to activate the support mechanism. The intent estimation algorithm requires demonstrations for each motion to be recognized. Depending on what motion is recognized, different control signals are sent to the exoskeleton. The Extended UMC (E-UMC) adds a calibration step and a velocity module to trigger the UMC. As a benchmark, and to compare the behavior of the controllers irrespective of the hardware, a Passive Exoskeleton Controller (PEC) is developed as well. The controllers were implemented on a hip exoskeleton and evaluated in a user study consisting of two phases. First, demonstrations of three motions were recorded: squat, stoop left and stoop right. Afterwards, the controllers were evaluated. The E-UMC combines benefits from the UMC and the PEC, confirming the need for the two extensions. The E-UMC discriminates between the three motions and does not generate false positives for previously unseen motions such as stair walking. The proposed methods can also be applied to support other motions.