OpenRaiser/Intern-Atlas huggingface dataset:
On the non-efficient PAC learnability of conjunctive queries
Venue: arXiv cs.DB 2023
Year: 2023

This note serves three purposes: (i) we provide a self-contained exposition of the fact that conjunctive queries are not efficiently learnable in the Probably-Approximately-Correct (PAC) model, paying clear attention to the complicating fact that this concept class lacks the polynomial-size fitting property, a property that is tacitly assumed in much of the computational learning theory literature; (ii) we establish a strong negative PAC learnability result that applies to many restricted classes of conjunctive queries (CQs), including acyclic CQs for a wide range of notions of "acyclicity"; (iii) we show that CQs (and UCQs) are efficiently PAC learnable with membership queries.
Multiple Shooting Approach for Finding Approximately Shortest Paths for Autonomous Robots in Unknown Environments in 2D
Venue: arXiv cs.RO 2023
Year: 2023

An autonomous robot with a limited vision range finds a path to the goal in an unknown environment in 2D avoiding polygonal obstacles. In the process of discovering the environmental map, the robot has to return to some positions marked previously, the regions where the robot traverses to return are defined as sequences of bundles of line segments. This paper presents a novel algorithm for finding approximately shortest paths along the sequences of bundles of line segments based on the method of multiple shooting. Three factors of the approach including bundle partition, collinear condition, and update of shooting points are presented. We then show that if the collinear condition holds, the exactly shortest paths of the problems are determined, otherwise, the sequence of paths obtained by the update of the method converges to the shortest path. The algorithm is implemented in Python and some numerical examples show that the running time of path-planning for autonomous robots using our method is faster than that using the rubber band technique of Li and Klette in Euclidean Shortest Paths, Springer, 53-89 (2011).
Interaction Modeling with Multiplex Attention
Venue: arXiv cs.LG 2023
Year: 2023

Modeling multi-agent systems requires understanding how agents interact. Such systems are often difficult to model because they can involve a variety of types of interactions that layer together to drive rich social behavioral dynamics. Here we introduce a method for accurately modeling multi-agent systems. We present Interaction Modeling with Multiplex Attention (IMMA), a forward prediction model that uses a multiplex latent graph to represent multiple independent types of interactions and attention to account for relations of different strengths. We also introduce Progressive Layer Training, a training strategy for this architecture. We show that our approach outperforms state-of-the-art models in trajectory forecasting and relation inference, spanning three multi-agent scenarios: social navigation, cooperative task achievement, and team sports. We further demonstrate that our approach can improve zero-shot generalization and allows us to probe how different interactions impact agent behavior.
Homomorphically Full Oriented Graphs
Venue: arXiv cs.DM 2023
Year: 2023

Homomorphically full graphs are those for which every homomorphic image is isomorphic to a subgraph. We extend the definition of homomorphically full to oriented graphs in two different ways. For the first of these, we show that homomorphically full oriented graphs arise as quasi-transitive orientations of homomorphically full graphs. This in turn yields an efficient recognition and construction algorithms for these homomorphically full oriented graphs. For the second one, we show that the related recognition problem is GI-hard, and that the problem of deciding if a graph admits a homomorphically full orientation is NP-complete. In doing so we show the problem of deciding if two given oriented cliques are isomorphic is GI-complete.
Graph Embeddings via Tensor Products and Approximately Orthonormal Codes
Venue: arXiv cs.SI 2023
Year: 2023

We propose a dynamic graph representation method, showcasing its rich representational capacity and establishing some of its theoretical properties. Our representation falls under the bind-and-sum approach in hyperdimensional computing (HDC), and we show that the tensor product is the most general binding operation that respects the superposition principle employed in HDC. We also establish some precise results characterizing the behavior of our method, including a memory vs. size analysis of how our representation's size must scale with the number of edges in order to retain accurate graph operations. True to its HDC roots, we also compare our graph representation to another typical HDC representation, the Hadamard-Rademacher scheme, showing that these two graph representations have the same memory-capacity scaling. We establish a link to adjacency matrices, showing that our method is a pseudo-orthogonal generalization of adjacency matrices. In light of this, we briefly discuss its applications toward a dynamic compressed representation of large sparse graphs.
Large-Scale Traffic Congestion Prediction based on Multimodal Fusion and Representation Mapping
Venue: arXiv cs.LG 2023
Year: 2023

With the progress of the urbanisation process, the urban transportation system is extremely critical to the development of cities and the quality of life of the citizens. Among them, it is one of the most important tasks to judge traffic congestion by analysing the congestion factors. Recently, various traditional and machine-learning-based models have been introduced for predicting traffic congestion. However, these models are either poorly aggregated for massive congestion factors or fail to make accurate predictions for every precise location in large-scale space. To alleviate these problems, a novel end-to-end framework based on convolutional neural networks is proposed in this paper. With learning representations, the framework proposes a novel multimodal fusion module and a novel representation mapping module to achieve traffic congestion predictions on arbitrary query locations on a large-scale map, combined with various global reference information. The proposed framework achieves significant results and efficient inference on real-world large-scale datasets.
The Alberta Plan for AI Research
Venue: arXiv cs.AI 2023
Year: 2023

Herein we describe our approach to artificial intelligence research, which we call the Alberta Plan. The Alberta Plan is pursued within our research groups in Alberta and by others who are like minded throughout the world. We welcome all who would join us in this pursuit.
Ordinal analysis of lexical patterns
Venue: arXiv cs.CL 2023
Year: 2023

Words are fundamental linguistic units that connect thoughts and things through meaning. However, words do not appear independently in a text sequence. The existence of syntactic rules induces correlations among neighboring words. Using an ordinal pattern approach, we present an analysis of lexical statistical connections for 11 major languages. We find that the diverse manners that languages utilize to express word relations give rise to unique pattern structural distributions. Furthermore, fluctuations of these pattern distributions for a given language can allow us to determine both the historical period when the text was written and its author. Taken together, our results emphasize the relevance of ordinal time series analysis in linguistic typology, historical linguistics and stylometry.
The Kolmogorov Birthday Paradox
Venue: arXiv cs.CC 2023
Year: 2023

We prove a Kolmogorov complexity variant of the birthday paradox. Sufficiently sized random subsets of strings are guaranteed to have two members x and y with low K(x/y). To prove this, we first show that the minimum conditional Kolmogorov complexity between members of finite sets is very low if they are not exotic. Exotic sets have high mutual information with the halting sequence.
Deep model with built-in cross-attention alignment for acoustic echo cancellation
Venue: arXiv cs.SD 2023
Year: 2023

With recent research advances, deep learning models have become an attractive choice for acoustic echo cancellation (AEC) in real-time teleconferencing applications. Since acoustic echo is one of the major sources of poor audio quality, a wide variety of deep models have been proposed. However, an important but often omitted requirement for good echo cancellation quality is the synchronization of the microphone and far end signals. Typically implemented using classical algorithms based on cross-correlation, the alignment module is a separate functional block with known design limitations. In our work we propose a deep learning architecture with built-in self-attention based alignment, which is able to handle unaligned inputs, improving echo cancellation performance while simplifying the communication pipeline. Moreover, we show that our approach achieves significant improvements for difficult delay estimation cases on real recordings from AEC Challenge data set.
A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
Venue: arXiv cs.DS 2023
Year: 2023

The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. We present a generalized framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. This raises several generalized variants of the shortest path problem. We introduce the problem of finding a path with the tightest lower-bound on the optimal cost. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy.
Motion Robust High-Speed Light-Weighted Object Detection With Event Camera
Venue: arXiv cs.CV 2023
Year: 2023

In this work, we propose a motion robust and high-speed detection pipeline which better leverages the event data. First, we design an event stream representation called temporal active focus (TAF), which efficiently utilizes the spatial-temporal asynchronous event stream, constructing event tensors robust to object motions. Then, we propose a module called the bifurcated folding module (BFM), which encodes the rich temporal information in the TAF tensor at the input layer of the detector. Following this, we design a high-speed lightweight detector called agile event detector (AED) plus a simple but effective data augmentation method, to enhance the detection accuracy and reduce the model's parameter. Experiments on two typical real-scene event camera object detection datasets show that our method is competitive in terms of accuracy, efficiency, and the number of parameters. By classifying objects into multiple motion levels based on the optical flow density metric, we further illustrated the robustness of our method for objects with different velocities relative to the camera. The codes and trained models are available at https://github.com/HarmoniaLeo/FRLW-EvD .
On the existence of strong proof complexity generators
Venue: arXiv cs.CC 2023
Year: 2023

Cook and Reckhow 1979 pointed out that NP is not closed under complementation iff there is no propositional proof system that admits polynomial size proofs of all tautologies. Theory of proof complexity generators aims at constructing sets of tautologies hard for strong and possibly for all proof systems. We focus at a conjecture from K.2004 in foundations of the theory that there is a proof complexity generator hard for all proof systems. This can be equivalently formulated (for p-time generators) without a reference to proof complexity notions as follows: * There exist a p-time function $g$ stretching each input by one bit such that its range intersects all infinite NP sets. We consider several facets of this conjecture, including its links to bounded arithmetic (witnessing and independence results), to time-bounded Kolmogorov complexity, to feasible disjunction property of propositional proof systems and to complexity of proof search. We argue that a specific gadget generator from K.2009 is a good candidate for $g$. We define a new hardness property of generators, the $\bigvee$-hardness, and shows that one specific gadget generator is the $\bigvee$-hardest (w.r.t. any sufficiently strong proof system). We define the class of feasibly infinite NP sets and show, assuming a hypothesis from circuit complexity, that the conjecture holds for all feasibly infinite NP sets.
Time Series Clustering with an EM algorithm for Mixtures of Linear Gaussian State Space Models
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we consider the task of clustering a set of individual time series while modeling each cluster, that is, model-based time series clustering. The task requires a parametric model with sufficient flexibility to describe the dynamics in various time series. To address this problem, we propose a novel model-based time series clustering method with mixtures of linear Gaussian state space models, which have high flexibility. The proposed method uses a new expectation-maximization algorithm for the mixture model to estimate the model parameters, and determines the number of clusters using the Bayesian information criterion. Experiments on a simulated dataset demonstrate the effectiveness of the method in clustering, parameter estimation, and model selection. The method is applied to real datasets commonly used to evaluate time series clustering methods. Results showed that the proposed method produces clustering results that are as accurate or more accurate than those obtained using previous methods.
Citation advantage of COVID-19 related publications
Venue: arXiv cs.DL 2023
Year: 2023

With the global spread of the COVID-19 pandemic, scientists from various disciplines responded quickly to this historical public health emergency. The sudden boom of COVID-19 related papers in a short period of time may bring unexpected influence to some commonly used bibliometric indicators. By a large-scale investigation using Science Citation Index Expanded and Social Sciences Citation Index, this brief communication confirms the citation advantage of COVID-19 related papers empirically through the lens of Essential Science Indicators' highly cited paper. More than 8% of COVID-19 related papers published during 2020 and 2021 were selected as Essential Science Indicators highly cited papers, which was much higher than the set global benchmark value of 1%. The citation advantage of COVID-19 related papers for different Web of Science categories/countries/journal impact factor quartiles were also demonstrated. The distortions of COVID-19 related papers' citation advantage to some bibliometric indicators such as journal impact factor were discussed at the end of this brief communication.
Apptainer Without Setuid
Venue: arXiv cs.DC 2023
Year: 2023

Apptainer (formerly known as Singularity) since its beginning implemented many of its container features with the assistance of a setuid-root program. It still supports that mode, but as of version 1.1.0 it no longer uses setuid by default. This is feasible because it now can mount squashfs filesystems, ext3 filesystems, and overlay filesystems using unprivileged user namespaces and FUSE. It also now enables unprivileged users to build containers, even without requiring system administrators to configure /etc/subuid and /etc/subgid unlike other "rootless" container systems. As a result, all the unprivileged functions can be used nested inside of another container, even if the container runtime prevents any elevated privileges. As of version 1.2.0 Apptainer also supports completely unprivileged encryption of Singularity Image Format (SIF) container files. Performance with a particularly challenging HEP benchmark using the FUSE-based mounts both with and without encryption is essentially identical to the previous methods that required elevated privileges to use the Linux kernel-based counterparts.
A Globally Convergent Gradient-based Bilevel Hyperparameter Optimization Method
Venue: arXiv cs.LG 2023
Year: 2023

Hyperparameter optimization in machine learning is often achieved using naive techniques that only lead to an approximate set of hyperparameters. Although techniques such as Bayesian optimization perform an intelligent search on a given domain of hyperparameters, it does not guarantee an optimal solution. A major drawback of most of these approaches is an exponential increase of their search domain with number of hyperparameters, increasing the computational cost and making the approaches slow. The hyperparameter optimization problem is inherently a bilevel optimization task, and some studies have attempted bilevel solution methodologies for solving this problem. However, these studies assume a unique set of model weights that minimize the training loss, which is generally violated by deep learning architectures. This paper discusses a gradient-based bilevel method addressing these drawbacks for solving the hyperparameter optimization problem. The proposed method can handle continuous hyperparameters for which we have chosen the regularization hyperparameter in our experiments. The method guarantees convergence to the set of optimal hyperparameters that this study has theoretically proven. The idea is based on approximating the lower-level optimal value function using Gaussian process regression. As a result, the bilevel problem is reduced to a single level constrained optimization task that is solved using the augmented Lagrangian method. We have performed an extensive computational study on the MNIST and CIFAR-10 datasets on multi-layer perceptron and LeNet architectures that confirms the efficiency of the proposed method. A comparative study against grid search, random search, Bayesian optimization, and HyberBand method on various hyperparameter problems shows that the proposed algorithm converges with lower computation and leads to models that generalize better on the testing set.
A Comparison of Reinforcement Learning Frameworks for Software Testing Tasks
Venue: arXiv cs.SE 2023
Year: 2023

Software testing activities scrutinize the artifacts and the behavior of a software product to find possible defects and ensure that the product meets its expected requirements. Recently, Deep Reinforcement Learning (DRL) has been successfully employed in complex testing tasks such as game testing, regression testing, and test case prioritization to automate the process and provide continuous adaptation. Practitioners can employ DRL by implementing from scratch a DRL algorithm or using a DRL framework. DRL frameworks offer well-maintained implemented state-of-the-art DRL algorithms to facilitate and speed up the development of DRL applications. Developers have widely used these frameworks to solve problems in various domains including software testing. However, to the best of our knowledge, there is no study that empirically evaluates the effectiveness and performance of implemented algorithms in DRL frameworks. Moreover, some guidelines are lacking from the literature that would help practitioners choose one DRL framework over another. In this paper, we empirically investigate the applications of carefully selected DRL algorithms on two important software testing tasks: test case prioritization in the context of Continuous Integration (CI) and game testing. For the game testing task, we conduct experiments on a simple game and use DRL algorithms to explore the game to detect bugs. Results show that some of the selected DRL frameworks such as Tensorforce outperform recent approaches in the literature. To prioritize test cases, we run experiments on a CI environment where DRL algorithms from different frameworks are used to rank the test cases. Our results show that the performance difference between implemented algorithms in some cases is considerable, motivating further investigation.
Decentralized Nonlinear Control of Redundant Upper Limb Exoskeleton with Natural Adaptation Law
Venue: arXiv cs.RO 2023
Year: 2023

The aim of this work is to utilize an adaptive decentralized control method called virtual decomposition control (VDC) to control the orientation and position of the end-effector of a 7 degrees of freedom (DoF) right-hand upper-limb exoskeleton. The prevailing adaptive VDC approach requires tuning of 13n adaptation gains along with 26n upper and lower parameter bounds, where n is the number of rigid bodies. Therefore, utilizing the VDC scheme to control high DoF robots like the 7-DoF upper-limb exoskeleton can be an arduous task. In this paper, a new adaptation function, so-called natural adaptation law (NAL), is employed to eliminate these burdens from VDC, which results in reducing all 13n gains to one and removing dependency on upper and lower bounds. In doing so, VDC-based dynamic equations are restructured, and inertial parameter vectors are made compatible with NAL. Then, the NAL adaptation function is exploited to design a new adaptive VDC scheme. This novel adaptive VDC approach ensures physical consistency conditions for estimated parameters with no need for upper and lower bounds. Finally, the asymptotic stability of the algorithm is proved with the virtual stability concept and the accompanying function. The experimental results are utilized to demonstrate the excellent performance of the proposed new adaptive VDC scheme.
Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix
Venue: arXiv cs.SI 2023
Year: 2023

Community detection is a fundamental problem in network science. In this paper, we consider community detection in hypergraphs drawn from the $hypergraph$ $stochastic$ $block$ $model$ (HSBM), with a focus on exact community recovery. We study the performance of polynomial-time algorithms which operate on the $similarity$ $matrix$ $W$, where $W_{ij}$ reports the number of hyperedges containing both $i$ and $j$. Under this information model, while the precise information-theoretic limit is unknown, Kim, Bandeira, and Goemans derived a sharp threshold up to which the natural min-bisection estimator on $W$ succeeds. As min-bisection is NP-hard in the worst case, they additionally proposed a semidefinite programming (SDP) relaxation and conjectured that it achieves the same recovery threshold as the min-bisection estimator. In this paper, we confirm this conjecture. We also design a simple and highly efficient spectral algorithm with nearly linear runtime and show that it achieves the min-bisection threshold. Moreover, the spectral algorithm also succeeds in denser regimes and is considerably more efficient than previous approaches, establishing it as the method of choice. Our analysis of the spectral algorithm crucially relies on strong $entrywise$ bounds on the eigenvectors of $W$. Our bounds are inspired by the work of Abbe, Fan, Wang, and Zhong, who developed entrywise bounds for eigenvectors of symmetric matrices with independent entries. Despite the complex dependency structure in similarity matrices, we prove similar entrywise guarantees.
Rectilinear Planarity of Partial 2-Trees
Venue: arXiv cs.DS 2023
Year: 2023

A graph is rectilinear planar if it admits a planar orthogonal drawing without bends. While testing rectilinear planarity is NP-hard in general (Garg and Tamassia, 2001), it is a long-standing open problem to establish a tight upper bound on its complexity for partial 2-trees, i.e., graphs whose biconnected components are series-parallel. We describe a new O(n^2)-time algorithm to test rectilinear planarity of partial 2-trees, which improves over the current best bound of O(n^3 \log n) (Di Giacomo et al., 2022). Moreover, for partial 2-trees where no two parallel-components in a biconnected component share a pole, we are able to achieve optimal O(n)-time complexity. Our algorithms are based on an extensive study and a deeper understanding of the notion of orthogonal spirality, introduced several years ago (Di Battista et al, 1998) to describe how much an orthogonal drawing of a subgraph is rolled-up in an orthogonal drawing of the graph.