OpenRaiser/Intern-Atlas huggingface dataset:
Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity
Venue: arXiv cs.GT 2023
Year: 2023

We investigate verification and existence problems for prominent stability concepts in hedonic games with friends, enemies, and optionally with neutrals [8, 16]. We resolve several (long-standing) open questions [4, 16, 20, 23] and show that for friend-oriented preferences, under the friends and enemies model, it is coNP-complete to verify whether a given agent partition is (strictly) core stable, while under the friends, enemies, and neutrals model, it is NP-complete to determine whether an individual stable partition exists. We further look into natural restricted cases from the literature, such as when the friends and enemies relationships are symmetric, when the initial coalitions have bounded size, when the vertex degree in the friendship graph (resp. the union of friendship and enemy graph) is bounded, or when such graph is acyclic or close to being acyclic. We obtain a complete (parameterized) complexity picture regarding these cases.
Representative Subset Selection for Efficient Fine-Tuning in Self-Supervised Speech Recognition
Venue: arXiv cs.LG 2023
Year: 2023

Self-supervised speech recognition models require considerable labeled training data for learning high-fidelity representations for Automatic Speech Recognition (ASR) which is computationally demanding and time-consuming. We consider the task of identifying an optimal subset of data for efficient fine-tuning in self-supervised speech models for ASR. We discover that the dataset pruning strategies used in vision tasks for sampling the most informative examples do not perform better than random subset selection on fine-tuning self-supervised ASR. We then present the COWERAGE algorithm for representative subset selection in self-supervised ASR. COWERAGE is based on our finding that ensuring the coverage of examples based on training Word Error Rate (WER) in the early training epochs leads to better generalization performance. Extensive experiments with the wav2vec 2.0 and HuBERT model on TIMIT, Librispeech, and LJSpeech datasets show the effectiveness of COWERAGE and its transferability across models, with up to 17% relative WER improvement over existing dataset pruning methods and random sampling. We also demonstrate that the coverage of training instances in terms of WER values ensures the inclusion of phonemically diverse examples, leading to better test accuracy in self-supervised speech recognition models.
Exact approaches for the Connected Vertex Cover problem
Venue: arXiv cs.DS 2023
Year: 2023

Given a graph $G$, the Connected Vertex Cover problem (CVC) asks to find a minimum cardinality vertex cover of $G$ that induces a connected subgraph. In this paper we describe some approaches to solve the CVC problem exactly. First, we give compact mixed-integer extended formulations for CVC: these are the first formulations proposed for this problem, and can be easily adapted to variations of the problem such as Tree Cover. Second, we describe a simple branch and bound algorithm for the CVC problem. Finally, we implement our algorithm and compare its performance against our best formulation: contrary to what usually happens for the classical Vertex Cover problem, our formulation outperforms the branch and bound algorithm.
WOODS: Benchmarks for Out-of-Distribution Generalization in Time Series
Venue: arXiv cs.LG 2023
Year: 2023

Machine learning models often fail to generalize well under distributional shifts. Understanding and overcoming these failures have led to a research field of Out-of-Distribution (OOD) generalization. Despite being extensively studied for static computer vision tasks, OOD generalization has been underexplored for time series tasks. To shine light on this gap, we present WOODS: eight challenging open-source time series benchmarks covering a diverse range of data modalities, such as videos, brain recordings, and sensor signals. We revise the existing OOD generalization algorithms for time series tasks and evaluate them using our systematic framework. Our experiments show a large room for improvement for empirical risk minimization and OOD generalization algorithms on our datasets, thus underscoring the new challenges posed by time series tasks. Code and documentation are available at https://woods-benchmarks.github.io .
VGSE: Visually-Grounded Semantic Embeddings for Zero-Shot Learning
Venue: arXiv cs.CV 2023
Year: 2023

Human-annotated attributes serve as powerful semantic embeddings in zero-shot learning. However, their annotation process is labor-intensive and needs expert supervision. Current unsupervised semantic embeddings, i.e., word embeddings, enable knowledge transfer between classes. However, word embeddings do not always reflect visual similarities and result in inferior zero-shot performance. We propose to discover semantic embeddings containing discriminative visual properties for zero-shot learning, without requiring any human annotation. Our model visually divides a set of images from seen classes into clusters of local image regions according to their visual similarity, and further imposes their class discrimination and semantic relatedness. To associate these clusters with previously unseen classes, we use external knowledge, e.g., word embeddings and propose a novel class relation discovery module. Through quantitative and qualitative evaluation, we demonstrate that our model discovers semantic embeddings that model the visual properties of both seen and unseen classes. Furthermore, we demonstrate on three benchmarks that our visually-grounded semantic embeddings further improve performance over word embeddings across various ZSL models by a large margin.
Performance of Deep Learning models with transfer learning for multiple-step-ahead forecasts in monthly time series
Venue: arXiv cs.LG 2023
Year: 2023

Deep Learning and transfer learning models are being used to generate time series forecasts; however, there is scarce evidence about their performance prediction that it is more evident for monthly time series. The purpose of this paper is to compare Deep Learning models with transfer learning and without transfer learning and other traditional methods used for monthly forecasts to answer three questions about the suitability of Deep Learning and Transfer Learning to generate predictions of time series. Time series of M4 and M3 competitions were used for the experiments. The results suggest that deep learning models based on TCN, LSTM, and CNN with transfer learning tend to surpass the performance prediction of other traditional methods. On the other hand, TCN and LSTM, trained directly on the target time series, got similar or better performance than traditional methods for some forecast horizons.
Random vector functional link network: recent developments, applications, and future directions
Venue: arXiv cs.NE 2023
Year: 2023

Neural networks have been successfully employed in various domains such as classification, regression and clustering, etc. Generally, the back propagation (BP) based iterative approaches are used to train the neural networks, however, it results in the issues of local minima, sensitivity to learning rate and slow convergence. To overcome these issues, randomization based neural networks such as random vector functional link (RVFL) network have been proposed. RVFL model has several characteristics such as fast training speed, direct links, simple architecture, and universal approximation capability, that make it a viable randomized neural network. This article presents the first comprehensive review of the evolution of RVFL model, which can serve as the extensive summary for the beginners as well as practitioners. We discuss the shallow RVFLs, ensemble RVFLs, deep RVFLs and ensemble deep RVFL models. The variations, improvements and applications of RVFL models are discussed in detail. Moreover, we discuss the different hyperparameter optimization techniques followed in the literature to improve the generalization performance of the RVFL model. Finally, we give potential future research directions/opportunities that can inspire the researchers to improve the RVFL's architecture and learning algorithm further.
Evolution is Driven by Natural Autoencoding: Reframing Species, Interaction Codes, Cooperation, and Sexual Reproduction
Venue: arXiv cs.NE 2023
Year: 2023

The continuity of life and its evolution, we proposed, emerge from an interactive group process manifested in networks of interaction. We term this process \textit{survival-of-the-fitted}. Here, we reason that survival of the fitted results from a natural computational process we term \textit{natural autoencoding}. Natural autoencoding works by retaining repeating biological interactions while non-repeatable interactions disappear. (1) We define a species by its \textit{species interaction code}, which consists of a compact description of the repeating interactions of species organisms with their external and internal environments. Species interaction codes are descriptions recorded in the biological infrastructure that enables repeating interactions. Encoding and decoding are interwoven. (2) Evolution proceeds by natural autoencoding of sustained changes in species interaction codes. DNA is only one element in natural autoencoding. (3) Natural autoencoding accounts for the paradox of genome randomization in sexual reproduction -- recombined genomes are analogous to the diversified inputs required for artificial autoencoding. The increase in entropy generated by genome randomization compensates for the decrease in entropy generated by organized life. (4) Natural autoencoding and artificial autoencoding algorithms manifest defined similarities and differences. Recognition of the importance of fittedness could well serve the future of a humanly livable biosphere.
Predicting the generalization gap in neural networks using topological data analysis
Venue: arXiv cs.LG 2023
Year: 2023

Understanding how neural networks generalize on unseen data is crucial for designing more robust and reliable models. In this paper, we study the generalization gap of neural networks using methods from topological data analysis. For this purpose, we compute homological persistence diagrams of weighted graphs constructed from neuron activation correlations after a training phase, aiming to capture patterns that are linked to the generalization capacity of the network. We compare the usefulness of different numerical summaries from persistence diagrams and show that a combination of some of them can accurately predict and partially explain the generalization gap without the need of a test set. Evaluation on two computer vision recognition tasks (CIFAR10 and SVHN) shows competitive generalization gap prediction when compared against state-of-the-art methods.
Modules in Robinson Spaces
Venue: arXiv cs.DM 2023
Year: 2023

A Robinson space is a dissimilarity space $(X,d)$ (i.e., a set $X$ of size $n$ and a dissimilarity $d$ on $X$) for which there exists a total order $<$ on $X$ such that $x<y<z$ implies that $d(x,z)\ge \max\{ d(x,y), d(y,z)\}$. Recognizing if a dissimilarity space is Robinson has numerous applications in seriation and classification. An mmodule of $(X,d)$ (generalizing the notion of a module in graph theory) is a subset $M$ of $X$ which is not distinguishable from the outside of $M$, i.e., the distance from any point of $X\setminus M$ to all points of $M$ is the same. If $p$ is any point of $X$, then $\{ p\}$ and the maximal by inclusion mmodules of $(X,d)$ not containing $p$ define a partition of $X$, called the copoint partition. In this paper, we investigate the structure of mmodules in Robinson spaces and use it and the copoint partition to design a simple and practical divide-and-conquer algorithm for recognition of Robinson spaces in optimal $O(n^2)$ time.
Bilaterally Slimmable Transformer for Elastic and Efficient Visual Question Answering
Venue: arXiv cs.CV 2023
Year: 2023

Recent advances in Transformer architectures [1] have brought remarkable improvements to visual question answering (VQA). Nevertheless, Transformer-based VQA models are usually deep and wide to guarantee good performance, so they can only run on powerful GPU servers and cannot run on capacity-restricted platforms such as mobile phones. Therefore, it is desirable to learn an elastic VQA model that supports adaptive pruning at runtime to meet the efficiency constraints of different platforms. To this end, we present the bilaterally slimmable Transformer (BST), a general framework that can be seamlessly integrated into arbitrary Transformer-based VQA models to train a single model once and obtain various slimmed submodels of different widths and depths. To verify the effectiveness and generality of this method, we integrate the proposed BST framework with three typical Transformer-based VQA approaches, namely MCAN [2], UNITER [3], and CLIP-ViL [4], and conduct extensive experiments on two commonly-used benchmark datasets. In particular, one slimmed MCAN-BST submodel achieves comparable accuracy on VQA-v2, while being 0.38x smaller in model size and having 0.27x fewer FLOPs than the reference MCAN model. The smallest MCAN-BST submodel only has 9M parameters and 0.16G FLOPs during inference, making it possible to deploy it on a mobile device with less than 60 ms latency.
Online Bipartite Matching via Smoothness
Venue: arXiv cs.GT 2023
Year: 2023

The online bipartite matching problem has offline buyers desiring to be matched to online items. The analysis of online bipartite matching of Eden et al. (2021) is a smoothness proof (Syrgkanis and Tardos, 2013). Moreover, it can be interpreted as combining a $λ= 1-1/e$ value covering (which holds for single-dimensional agents and randomized auctions) and $μ= 1$ revenue covering (Hartline et al., 2014). Note that value covering is a fact about single-dimensional agents and has nothing to do with the underlying feasibility setting. Thus, the essential new result from Eden et al. (2021) is that online bipartite matching is $μ=1$ revenue covered. A number of old and new observations follow from this perspective.
SERA: Safe and Efficient Reactive Obstacle Avoidance for Collaborative Robotic Planning in Unstructured Environments
Venue: arXiv cs.RO 2023
Year: 2023

Safe and efficient collaboration among multiple robots in unstructured environments is increasingly critical in the era of Industry 4.0. However, achieving robust and autonomous collaboration among humans and other robots requires modern robotic systems to have effective proximity perception and reactive obstacle avoidance. In this paper, we propose a novel methodology for reactive whole-body obstacle avoidance that ensures conflict-free robot-robot interactions even in dynamic environment. Unlike existing approaches based on Jacobian-type, sampling based or geometric techniques, our methodology leverages the latest deep learning advances and topological manifold learning, enabling it to be readily generalized to other problem settings with high computing efficiency and fast graph traversal techniques. Our approach allows a robotic arm to proactively avoid obstacles of arbitrary 3D shapes without direct contact, a significant improvement over traditional industrial cobot settings. To validate our approach, we implement it on a robotic platform consisting of dual 6-DoF robotic arms with optimized proximity sensor placement, capable of working collaboratively with varying levels of interference. Specifically, one arm performs reactive whole-body obstacle avoidance while achieving its pre-determined objective, while the other arm emulates the presence of a human collaborator with independent and potentially adversarial movements. Our methodology provides a robust and effective solution for safe human-robot collaboration in non-stationary environments.
A Runtime Environment for Contract Automata
Venue: arXiv cs.SE 2023
Year: 2023

Contract automata have been introduced for specifying applications through behavioural contracts and for synthesising their orchestrations as finite state automata. This paper addresses the realisation of applications from contract automata specifications. We present CARE, a new runtime environment to coordinate services implementing contracts that guarantees the adherence of the implementation to its contract. We discuss how CARE can be adopted to realise contract-based applications, its formal guarantees, and we identify the responsibilities of the involved business actors. Experiments show the benefits of adopting CARE with respect to manual implementations.
A distribution-dependent Mumford-Shah model for unsupervised hyperspectral image segmentation
Venue: arXiv cs.CV 2023
Year: 2023

Hyperspectral images provide a rich representation of the underlying spectrum for each pixel, allowing for a pixel-wise classification/segmentation into different classes. As the acquisition of labeled training data is very time-consuming, unsupervised methods become crucial in hyperspectral image analysis. The spectral variability and noise in hyperspectral data make this task very challenging and define special requirements for such methods. Here, we present a novel unsupervised hyperspectral segmentation framework. It starts with a denoising and dimensionality reduction step by the well-established Minimum Noise Fraction (MNF) transform. Then, the Mumford-Shah (MS) segmentation functional is applied to segment the data. We equipped the MS functional with a novel robust distribution-dependent indicator function designed to handle the characteristic challenges of hyperspectral data. To optimize our objective function with respect to the parameters for which no closed form solution is available, we propose an efficient fixed point iteration scheme. Numerical experiments on four public benchmark datasets show that our method produces competitive results, which outperform three state-of-the-art methods substantially on three of these datasets.
UnShadowNet: Illumination Critic Guided Contrastive Learning For Shadow Removal
Venue: arXiv cs.CV 2023
Year: 2023

Shadows are frequently encountered natural phenomena that significantly hinder the performance of computer vision perception systems in practical settings, e.g., autonomous driving. A solution to this would be to eliminate shadow regions from the images before the processing of the perception system. Yet, training such a solution requires pairs of aligned shadowed and non-shadowed images which are difficult to obtain. We introduce a novel weakly supervised shadow removal framework UnShadowNet trained using contrastive learning. It is composed of a DeShadower network responsible for the removal of the extracted shadow under the guidance of an Illumination network which is trained adversarially by the illumination critic and a Refinement network to further remove artefacts. We show that UnShadowNet can be easily extended to a fully-supervised set-up to exploit the ground-truth when available. UnShadowNet outperforms existing state-of-the-art approaches on three publicly available shadow datasets (ISTD, adjusted ISTD, SRD) in both the weakly and fully supervised setups.
On $d$-stable locally checkable problems parameterized by mim-width
Venue: arXiv cs.DM 2023
Year: 2023

In this paper we continue the study of locally checkable problems under the framework introduced by Bonomo-Braberman and Gonzalez in 2020, by focusing on graphs of bounded mim-width. We study which restrictions on a locally checkable problem are necessary in order to be able to solve it efficiently on graphs of bounded mim-width. To this end, we introduce the concept of $d$-stability of a check function. The related locally checkable problems contain large classes of problems, among which we can mention, for example, LCVP problems. We give an algorithm showing that these problems are XP when parameterized by the mim-width of a given binary decomposition tree of the input graph, that is, that they can be solved in polynomial time given a binary decomposition tree of bounded mim-width. We explore the relation between $d$-stable locally checkable problems and the recently introduced DN logic (Bergougnoux, Dreier and Jaffke, 2022), and show that both frameworks model the same family of problems. We include a list of concrete examples of $d$-stable locally checkable problems whose complexity on graphs of bounded mim-width was open so far.
CycDA: Unsupervised Cycle Domain Adaptation from Image to Video
Venue: arXiv cs.CV 2023
Year: 2023

Although action recognition has achieved impressive results over recent years, both collection and annotation of video training data are still time-consuming and cost intensive. Therefore, image-to-video adaptation has been proposed to exploit labeling-free web image source for adapting on unlabeled target videos. This poses two major challenges: (1) spatial domain shift between web images and video frames; (2) modality gap between image and video data. To address these challenges, we propose Cycle Domain Adaptation (CycDA), a cycle-based approach for unsupervised image-to-video domain adaptation by leveraging the joint spatial information in images and videos on the one hand and, on the other hand, training an independent spatio-temporal model to bridge the modality gap. We alternate between the spatial and spatio-temporal learning with knowledge transfer between the two in each cycle. We evaluate our approach on benchmark datasets for image-to-video as well as for mixed-source domain adaptation achieving state-of-the-art results and demonstrating the benefits of our cyclic adaptation. Code is available at \url{https://github.com/wlin-at/CycDA}.
IGRF-RFE: A Hybrid Feature Selection Method for MLP-based Network Intrusion Detection on UNSW-NB15 Dataset
Venue: arXiv cs.LG 2023
Year: 2023

The effectiveness of machine learning models is significantly affected by the size of the dataset and the quality of features as redundant and irrelevant features can radically degrade the performance. This paper proposes IGRF-RFE: a hybrid feature selection method tasked for multi-class network anomalies using a Multilayer perceptron (MLP) network. IGRF-RFE can be considered as a feature reduction technique based on both the filter feature selection method and the wrapper feature selection method. In our proposed method, we use the filter feature selection method, which is the combination of Information Gain and Random Forest Importance, to reduce the feature subset search space. Then, we apply recursive feature elimination(RFE) as a wrapper feature selection method to further eliminate redundant features recursively on the reduced feature subsets. Our experimental results obtained based on the UNSW-NB15 dataset confirm that our proposed method can improve the accuracy of anomaly detection while reducing the feature dimension. The results show that the feature dimension is reduced from 42 to 23 while the multi-classification accuracy of MLP is improved from 82.25% to 84.24%.
CADG: A Model Based on Cross Attention for Domain Generalization
Venue: arXiv cs.CV 2023
Year: 2023

In Domain Generalization (DG) tasks, models are trained by using only training data from the source domains to achieve generalization on an unseen target domain, this will suffer from the distribution shift problem. So it's important to learn a classifier to focus on the common representation which can be used to classify on multi-domains, so that this classifier can achieve a high performance on an unseen target domain as well. With the success of cross attention in various cross-modal tasks, we find that cross attention is a powerful mechanism to align the features come from different distributions. So we design a model named CADG (cross attention for domain generalization), wherein cross attention plays a important role, to address distribution shift problem. Such design makes the classifier can be adopted on multi-domains, so the classifier will generalize well on an unseen domain. Experiments show that our proposed method achieves state-of-the-art performance on a variety of domain generalization benchmarks compared with other single model and can even achieve a better performance than some ensemble-based methods.