OpenRaiser/Intern-Atlas huggingface dataset:
Ghost-dil-NetVLAD: A Lightweight Neural Network for Visual Place Recognition
Venue: arXiv cs.CV 2024
Year: 2024

Visual place recognition (VPR) is a challenging task with the unbalance between enormous computational cost and high recognition performance. Thanks to the practical feature extraction ability of the lightweight convolution neural networks (CNNs) and the train-ability of the vector of locally aggregated descriptors (VLAD) layer, we propose a lightweight weakly supervised end-to-end neural network consisting of a front-ended perception model called GhostCNN and a learnable VLAD layer as a back-end. GhostCNN is based on Ghost modules that are lightweight CNN-based architectures. They can generate redundant feature maps using linear operations instead of the traditional convolution process, making a good trade-off between computation resources and recognition accuracy. To enhance our proposed lightweight model further, we add dilated convolutions to the Ghost module to get features containing more spatial semantic information, improving accuracy. Finally, rich experiments conducted on a commonly used public benchmark and our private dataset validate that the proposed neural network reduces the FLOPs and parameters of VGG16-NetVLAD by 99.04% and 80.16%, respectively. Besides, both models achieve similar accuracy.
Simple and near-optimal algorithms for hidden stratification and multi-group learning
Venue: arXiv cs.LG 2024
Year: 2024

Multi-group agnostic learning is a formal learning criterion that is concerned with the conditional risks of predictors within subgroups of a population. The criterion addresses recent practical concerns such as subgroup fairness and hidden stratification. This paper studies the structure of solutions to the multi-group learning problem, and provides simple and near-optimal algorithms for the learning problem.
Fight Perturbations with Perturbations: Defending Adversarial Attacks via Neuron Influence
Venue: arXiv cs.CV 2024
Year: 2024

The vulnerabilities of deep learning models towards adversarial attacks have attracted increasing attention, especially when models are deployed in security-critical domains. Numerous defense methods, including reactive and proactive ones, have been proposed for model robustness improvement. Reactive defenses, such as conducting transformations to remove perturbations, usually fail to handle large perturbations. The proactive defenses that involve retraining, suffer from the attack dependency and high computation cost. In this paper, we consider defense methods from the general effect of adversarial attacks that take on neurons inside the model. We introduce the concept of neuron influence, which can quantitatively measure neurons' contribution to correct classification. Then, we observe that almost all attacks fool the model by suppressing neurons with larger influence and enhancing those with smaller influence. Based on this, we propose \emph{Neuron-level Inverse Perturbation} (NIP), a novel defense against general adversarial attacks. It calculates neuron influence from benign examples and then modifies input examples by generating inverse perturbations that can in turn strengthen neurons with larger influence and weaken those with smaller influence.
Towards a conjecture on a special class of matrices over commutative rings of characteristic 2
Venue: arXiv cs.CR 2024
Year: 2024

In this paper, we prove the conjecture posed by Keller and Rosemarin at Eurocrypt 2021 on the nullity of a matrix polynomial of a block matrix with Hadamard type blocks over commutative rings of characteristic 2. Therefore, it confirms the conjectural optimal bound on the dimension of invariant subspace of the Starkad cipher using the HADES design strategy. Moreover, we reveal the algebraic structure formed by Hadamard matrices over commutative rings from the perspectives of group algebra and polynomial algebra. An interesting relation between block-Hadamard matrices and Hadamard-block matrices is obtained as well.
Can Social Ontological Knowledge Representations be Measured Using Machine Learning?
Venue: arXiv cs.CL 2024
Year: 2024

Personal Social Ontology (PSO), it is proposed, is how an individual perceives the ontological properties of terms. For example, an absolute fatalist would arguably use terms that remove any form of agency from a person. Such fatalism has the impact of ontologically defining acts such as winning, victory and success in a manner that is contrary to how a non-fatalist would ontologically define them. While both the said fatalist and non-fatalist would agree on the dictionary definition of these terms, they would differ on specifically how they can be brought about. This difference between the two individuals can be induced from their usage of these terms, i.e., the co-occurrence of these terms with other terms. As such a quantification of this such co-occurrence offers an avenue to characterise the social ontological views of the speaker. In this paper we ask, what specific term co-occurrence should be measured in order to obtain a valid and reliable psychometric measure of a persons social ontology? We consider the social psychology and social neuroscience literature to arrive at a list of social concepts that can be considered principal features of personal social ontology, and then propose an NLP pipeline to capture the articulation of these terms in language.
Robust Sparse Recovery with Sparse Bernoulli matrices via Expanders
Venue: arXiv cs.IT 2024
Year: 2024

Sparse binary matrices are of great interest in the field of sparse recovery, nonnegative compressed sensing, statistics in networks, and theoretical computer science. This class of matrices makes it possible to perform signal recovery with lower storage costs and faster decoding algorithms. In particular, Bernoulli$(p)$ matrices formed by independent identically distributed (i.i.d.) Bernoulli$(p)$ random variables are of practical relevance in the context of noise-blind recovery in nonnegative compressed sensing. In this work, we investigate the robust nullspace property of Bernoulli$(p)$ matrices. Previous results in the literature establish that such matrices can accurately recover $n$-dimensional $s$-sparse vectors with $m=O\left(\frac{s}{c(p)}\log\frac{en}{s}\right)$ measurements, where $c(p) \le p$ is a constant dependent only on the parameter $p$. These results suggest that in the sparse regime, as $p$ approaches zero, the (sparse) Bernoulli$(p)$ matrix requires significantly more measurements than the minimal necessary, as achieved by standard isotropic subgaussian designs. However, we show that this is not the case. Our main result characterizes, for a wide range of sparsity levels $s$, the smallest $p$ for which sparse recovery can be achieved with the minimal number of measurements. We also provide matching lower bounds to establish the optimality of our results and explore connections with the theory of invertibility of discrete random matrices and integer compressed sensing.
Unlocking the Secrets of Software Configuration Landscapes-Ruggedness, Accessibility, Escapability, and Transferability
Venue: arXiv cs.SE 2024
Year: 2024

Modern software systems are often highly configurable to tailor varied requirements from diverse stakeholders. Understanding the mapping between configurations and the desired performance attributes plays a fundamental role in advancing the controllability and tuning of the underlying system, yet has long been a dark hole of knowledge due to their black-box nature and the enormous combinatorial configuration space. In this paper, using $86$M evaluated configurations from three real-world systems on $32$ running workloads, we conducted one of its kind fitness landscape analysis (FLA) for configurable software systems. With comprehensive FLA methods, we for the first time show that: $i)$ the software configuration landscapes are fairly rugged, with numerous scattered local optima; $ii)$ nevertheless, the top local optima are highly accessible, featuring significantly larger basins of attraction; $iii)$ most inferior local optima are escapable with simple perturbations; $iv)$ landscapes of the same system with different workloads share structural similarities, which can be exploited to expedite heuristic search. Our results also provide valuable insights on the design of tailored meta-heuristics for configuration tuning; our FLA framework along with the collected data, build solid foundation for future research in this direction.
Mirror Learning: A Unifying Framework of Policy Optimisation
Venue: arXiv cs.LG 2024
Year: 2024

Modern deep reinforcement learning (RL) algorithms are motivated by either the generalised policy iteration (GPI) or trust-region learning (TRL) frameworks. However, algorithms that strictly respect these theoretical frameworks have proven unscalable. Surprisingly, the only known scalable algorithms violate the GPI/TRL assumptions, e.g. due to required regularisation or other heuristics. The current explanation of their empirical success is essentially "by analogy": they are deemed approximate adaptations of theoretically sound methods. Unfortunately, studies have shown that in practice these algorithms differ greatly from their conceptual ancestors. In contrast, in this paper we introduce a novel theoretical framework, named Mirror Learning, which provides theoretical guarantees to a large class of algorithms, including TRPO and PPO. While the latter two exploit the flexibility of our framework, GPI and TRL fit in merely as pathologically restrictive corner cases thereof. This suggests that the empirical performance of state-of-the-art methods is a direct consequence of their theoretical properties, rather than of aforementioned approximate analogies. Mirror learning sets us free to boldly explore novel, theoretically sound RL algorithms, a thus far uncharted wonderland.
Savile Row Manual
Venue: arXiv cs.AI 2024
Year: 2024

We describe the constraint modelling tool Savile Row, its input language and its main features. Savile Row translates a solver-independent constraint modelling language to the input languages for various solvers including constraint, SAT, and SMT solvers. After a brief introduction, the manual describes the Essence Prime language, which is the input language of Savile Row. Then we describe the functions of the tool, its main features and options and how to install and use it.
Uniform Approximation with Quadratic Neural Networks
Venue: arXiv cs.LG 2024
Year: 2024

In this work, we examine the approximation capabilities of deep neural networks utilizing the Rectified Quadratic Unit (ReQU) activation function, defined as \(\max(0,x)^2\), for approximating Hölder-regular functions with respect to the uniform norm. We constructively prove that deep neural networks with ReQU activation can approximate any function within the \(R\)-ball of \(r\)-Hölder-regular functions (\(\mathcal{H}^{r, R}([-1,1]^d)\)) up to any accuracy \(ε\) with at most \(\mathcal{O}\left(ε^{-d /2r}\right)\) neurons and fixed number of layers. This result highlights that the effectiveness of the approximation depends significantly on the smoothness of the target function and the characteristics of the ReQU activation function. Our proof is based on approximating local Taylor expansions with deep ReQU neural networks, demonstrating their ability to capture the behavior of Hölder-regular functions effectively. Furthermore, the results can be straightforwardly generalized to any Rectified Power Unit (RePU) activation function of the form \(\max(0,x)^p\) for \(p \geq 2\), indicating the broader applicability of our findings within this family of activations.
Bridging the Language Gap: An Empirical Study of Bindings for Open Source Machine Learning Libraries Across Software Package Ecosystems
Venue: arXiv cs.SE 2024
Year: 2024

Open source machine learning (ML) libraries enable developers to integrate advanced ML functionality into their own applications. However, popular ML libraries, such as TensorFlow, are not available natively in all programming languages and software package ecosystems. Hence, developers who wish to use an ML library which is not available in their programming language or ecosystem of choice, may need to resort to using a so-called binding library (or binding). Bindings provide support across programming languages and package ecosystems for reusing a host library. For example, the Keras .NET binding provides support for the Keras library in the NuGet (.NET) ecosystem even though the Keras library was written in Python. In this paper, we collect 2,436 cross-ecosystem bindings for 546 ML libraries across 13 software package ecosystems by using an approach called BindFind, which can automatically identify bindings and link them to their host libraries. Furthermore, we conduct an in-depth study of 133 cross-ecosystem bindings and their development for 40 popular open source ML libraries. Our findings reveal that the majority of ML library bindings are maintained by the community, with npm being the most popular ecosystem for these bindings. Our study also indicates that most bindings cover only a limited range of the host library's releases, often experience considerable delays in supporting new releases, and have widespread technical lag. Our findings highlight key factors to consider for developers integrating bindings for ML libraries and open avenues for researchers to further investigate bindings in software package ecosystems.
Addressing Maximization Bias in Reinforcement Learning with Two-Sample Testing
Venue: arXiv cs.LG 2024
Year: 2024

Value-based reinforcement-learning algorithms have shown strong results in games, robotics, and other real-world applications. Overestimation bias is a known threat to those algorithms and can sometimes lead to dramatic performance decreases or even complete algorithmic failure. We frame the bias problem statistically and consider it an instance of estimating the maximum expected value (MEV) of a set of random variables. We propose the $T$-Estimator (TE) based on two-sample testing for the mean, that flexibly interpolates between over- and underestimation by adjusting the significance level of the underlying hypothesis tests. We also introduce a generalization, termed $K$-Estimator (KE), that obeys the same bias and variance bounds as the TE and relies on a nearly arbitrary kernel function. We introduce modifications of $Q$-Learning and the Bootstrapped Deep $Q$-Network (BDQN) using the TE and the KE, and prove convergence in the tabular setting. Furthermore, we propose an adaptive variant of the TE-based BDQN that dynamically adjusts the significance level to minimize the absolute estimation bias. All proposed estimators and algorithms are thoroughly tested and validated on diverse tasks and environments, illustrating the bias control and performance potential of the TE and KE.
DIVA-DAF: A Deep Learning Framework for Historical Document Image Analysis
Venue: arXiv cs.CV 2024
Year: 2024

Deep learning methods have shown strong performance in solving tasks for historical document image analysis. However, despite current libraries and frameworks, programming an experiment or a set of experiments and executing them can be time-consuming. This is why we propose an open-source deep learning framework, DIVA-DAF, which is based on PyTorch Lightning and specifically designed for historical document analysis. Pre-implemented tasks such as segmentation and classification can be easily used or customized. It is also easy to create one's own tasks with the benefit of powerful modules for loading data, even large data sets, and different forms of ground truth. The applications conducted have demonstrated time savings for the programming of a document analysis task, as well as for different scenarios such as pre-training or changing the architecture. Thanks to its data module, the framework also allows to reduce the time of model training significantly.
Learning from One and Only One Shot
Venue: arXiv cs.CV 2024
Year: 2024

Humans can generalize from only a few examples and from little pretraining on similar tasks. Yet, machine learning (ML) typically requires large data to learn or pre-learn to transfer. Motivated by nativism and artificial general intelligence, we directly model human-innate priors in abstract visual tasks such as character and doodle recognition. This yields a white-box model that learns general-appearance similarity by mimicking how humans naturally ``distort'' an object at first sight. Using just nearest-neighbor classification on this cognitively-inspired similarity space, we achieve human-level recognition with only $1$--$10$ examples per class and no pretraining. This differs from few-shot learning that uses massive pretraining. In the tiny-data regime of MNIST, EMNIST, Omniglot, and QuickDraw benchmarks, we outperform both modern neural networks and classical ML. For unsupervised learning, by learning the non-Euclidean, general-appearance similarity space in a $k$-means style, we achieve multifarious visual realizations of abstract concepts by generating human-intuitive archetypes as cluster centroids.
A Survey of PPG's Application in Authentication
Venue: arXiv cs.CR 2024
Year: 2024

Biometric authentication prospered because of its convenient use and security. Early generations of biometric mechanisms suffer from spoofing attacks. Recently, unobservable physiological signals (e.g., Electroencephalogram, Photoplethysmogram, Electrocardiogram) as biometrics offer a potential remedy to this problem. In particular, Photoplethysmogram (PPG) measures the change in blood flow of the human body by an optical method. Clinically, researchers commonly use PPG signals to obtain patients' blood oxygen saturation, heart rate, and other information to assist in diagnosing heart-related diseases. Since PPG signals contain a wealth of individual cardiac information, researchers have begun to explore their potential in cyber security applications. The unique advantages (simple acquisition, difficult to steal, and live detection) of the PPG signal allow it to improve the security and usability of the authentication in various aspects. However, the research on PPG-based authentication is still in its infancy. The lack of systematization hinders new research in this field. We conduct a comprehensive study of PPG-based authentication and discuss these applications' limitations before pointing out future research directions.
Representations learnt by SGD and Adaptive learning rules: Conditions that vary sparsity and selectivity in neural networks
Venue: arXiv cs.LG 2024
Year: 2024

From the point of view of the human brain, continual learning can perform various tasks without mutual interference. An effective way to reduce mutual interference can be found in sparsity and selectivity of neurons. According to Aljundi et al. and Hadsell et al., imposing sparsity at the representational level is advantageous for continual learning because sparse neuronal activations encourage less overlap between parameters, resulting in less interference. Similarly, highly selective neural networks are likely to induce less interference since particular response in neurons will reduce the chance of overlap with other parameters. Considering that the human brain performs continual learning over the lifespan, finding conditions where sparsity and selectivity naturally arises may provide insight for understanding how the brain functions. This paper investigates various conditions that naturally increase sparsity and selectivity in a neural network. This paper tested different optimizers with Hoyer's sparsity metric and CCMAS selectivity metric in MNIST classification task. It is essential to note that investigations on the natural occurrence of sparsity and selectivity concerning various conditions have not been acknowledged in any sector of neuroscience nor machine learning until this day. This paper found that particular conditions increase sparsity and selectivity such as applying a large learning rate and lowering a batch size. In addition to the relationship between the condition, sparsity, and selectivity, the following will be discussed based on empirical analysis: 1. The relationship between sparsity and selectivity and 2. The relationship between test accuracy, sparsity, and selectivity.
AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data
Venue: arXiv cs.DB 2024
Year: 2024

We propose AIM, a new algorithm for differentially private synthetic data generation. AIM is a workload-adaptive algorithm within the paradigm of algorithms that first selects a set of queries, then privately measures those queries, and finally generates synthetic data from the noisy measurements. It uses a set of innovative features to iteratively select the most useful measurements, reflecting both their relevance to the workload and their value in approximating the input data. We also provide analytic expressions to bound per-query error with high probability which can be used to construct confidence intervals and inform users about the accuracy of generated data. We show empirically that AIM consistently outperforms a wide variety of existing mechanisms across a variety of experimental settings.
G$ \mathbf{^2} $VD Planner: Efficient Motion Planning With Grid-based Generalized Voronoi Diagrams
Venue: arXiv cs.RO 2024
Year: 2024

In this paper, an efficient motion planning approach with grid-based generalized Voronoi diagrams (G$ \mathbf{^2} $VD) is newly proposed for mobile robots. Different from existing approaches, the novelty of this work is twofold: 1) a new state lattice-based path searching approach is proposed, in which the search space is reduced to a novel Voronoi corridor to further improve the search efficiency; 2) an efficient quadratic programming-based path smoothing approach is presented, wherein the clearance to obstacles is considered to improve the path clearance of hard-constrained path smoothing approaches. We validate the efficiency and smoothness of our approach in various challenging simulation scenarios and outdoor environments. It is shown that the computational efficiency is improved by 17.1% in the path searching stage, and path smoothing with the proposed approach is 6.6 times faster than an advanced sparse-banded structure-based path smoothing approach and 53.3 times faster than the popular timed-elastic-band planner. A video showing outdoor navigation on our campus is available at https://youtu.be/iMXGthgvp58.