OpenRaiser/Intern-Atlas huggingface dataset:
Minimum Weight Euclidean $(1+\varepsilon)$-Spanners
Venue: arXiv cs.CG 2023
Year: 2023

Given a set $S$ of $n$ points in the plane and a parameter $\varepsilon>0$, a Euclidean $(1+\varepsilon)$-spanner is a geometric graph $G=(S,E)$ that contains, for all $p,q\in S$, a $pq$-path of weight at most $(1+\varepsilon)\|pq\|$. We show that the minimum weight of a Euclidean $(1+\varepsilon)$-spanner for $n$ points in the unit square $[0,1]^2$ is $O(\varepsilon^{-3/2}\,\sqrt{n})$, and this bound is the best possible. The upper bound is based on a new spanner algorithm in the plane. It improves upon the baseline $O(\varepsilon^{-2}\sqrt{n})$, obtained by combining a tight bound for the weight of a Euclidean minimum spanning tree (MST) on $n$ points in $[0,1]^2$, and a tight bound for the lightness of Euclidean $(1+\varepsilon)$-spanners, which is the ratio of the spanner weight to the weight of the MST. Our result generalizes to Euclidean $d$-space for every constant dimension $d\in \mathbb{N}$: The minimum weight of a Euclidean $(1+\varepsilon)$-spanner for $n$ points in the unit cube $[0,1]^d$ is $O_d(\varepsilon^{(1-d^2)/d}n^{(d-1)/d})$, and this bound is the best possible. For the $n\times n$ section of the integer lattice in the plane, we show that the minimum weight of a Euclidean $(1+\varepsilon)$-spanner is between $Ω(\varepsilon^{-3/4}\cdot n^2)$ and $O(\varepsilon^{-1}\log(\varepsilon^{-1})\cdot n^2)$. These bounds become $Ω(\varepsilon^{-3/4}\cdot \sqrt{n})$ and $O(\varepsilon^{-1}\log(\varepsilon^{-1})\cdot \sqrt{n})$ when scaled to a grid of $n$ points in the unit square. In particular, this shows that the integer grid is \emph{not} an extremal configuration for minimum weight Euclidean $(1+\varepsilon)$-spanners.
Cross-domain Federated Object Detection
Venue: arXiv cs.CV 2023
Year: 2023

Detection models trained by one party (including server) may face severe performance degradation when distributed to other users (clients). Federated learning can enable multi-party collaborative learning without leaking client data. In this paper, we focus on a special cross-domain scenario in which the server has large-scale labeled data and multiple clients only have a small amount of labeled data; meanwhile, there exist differences in data distributions among the clients. In this case, traditional federated learning methods can't help a client learn both the global knowledge of all participants and its own unique knowledge. To make up for this limitation, we propose a cross-domain federated object detection framework, named FedOD. The proposed framework first performs the federated training to obtain a public global aggregated model through multi-teacher distillation, and sends the aggregated model back to each client for fine-tuning its personalized local model. After a few rounds of communication, on each client we can perform weighted ensemble inference on the public global model and the personalized local model. We establish a federated object detection dataset which has significant background differences and instance differences based on multiple public autonomous driving datasets, and then conduct extensive experiments on the dataset. The experimental results validate the effectiveness of the proposed method.
Minimization of Dynamical Systems over Monoids
Venue: arXiv cs.LO 2023
Year: 2023

Quantitative notions of bisimulation are well-known tools for the minimization of dynamical models such as Markov chains and ordinary differential equations (ODEs). In \emph{forward bisimulations}, each state in the quotient model represents an equivalence class and the dynamical evolution gives the overall sum of its members in the original model. Here we introduce generalized forward bisimulation (GFB) for dynamical systems over commutative monoids and develop a partition refinement algorithm to compute the coarsest one. When the monoid is $(\mathbb{R}, +)$, we recover probabilistic bisimulation for Markov chains and more recent forward bisimulations for nonlinear ODEs. Using $(\mathbb{R}, \cdot)$ we get nonlinear reductions for discrete-time dynamical systems and ODEs where each variable in the quotient model represents the product of original variables in the equivalence class. When the domain is a finite set such as the Booleans $\mathbb{B}$, we can apply GFB to Boolean networks (BN), a widely used dynamical model in computational biology. Using a prototype implementation of our minimization algorithm for GFB, we find disjunction- and conjunction-preserving reductions on 60 BN from two well-known repositories, and demonstrate the obtained analysis speed-ups. We also provide the biological interpretation of the reduction obtained for two selected BN, and we show how GFB enables the analysis of a large one that could not be analyzed otherwise. Using a randomized version of our algorithm we find product-preserving (therefore non-linear) reductions on 21 dynamical weighted networks from the literature that could not be handled by the exact algorithm.
Affordance Extraction with an External Knowledge Database for Text-Based Simulated Environments
Venue: arXiv cs.CL 2023
Year: 2023

Text-based simulated environments have proven to be a valid testbed for machine learning approaches. The process of affordance extraction can be used to generate possible actions for interaction within such an environment. In this paper the capabilities and challenges for utilizing external knowledge databases (in particular ConceptNet) in the process of affordance extraction are studied. An algorithm for automated affordance extraction is introduced and evaluated on the Interactive Fiction (IF) platforms TextWorld and Jericho. For this purpose, the collected affordances are translated into text commands for IF agents. To probe the quality of the automated evaluation process, an additional human baseline study is conducted. The paper illustrates that, despite some challenges, external databases can in principle be used for affordance extraction. The paper concludes with recommendations for further modification and improvement of the process.
Using Neural Networks for Novelty-based Test Selection to Accelerate Functional Coverage Closure
Venue: arXiv cs.SE 2023
Year: 2023

Novel test selectors used in simulation-based verification have been shown to significantly accelerate coverage closure regardless of the number of coverage holes. This paper presents a configurable and highly-automated framework for novel test selection based on neural networks. Three configurations of this framework are tested with a commercial signal processing unit. All three convincingly outperform random test selection with the largest saving of simulation being 49.37% to reach 99.5% coverage. The computational expense of the configurations is negligible compared to the simulation reduction. We compare the experimental results and discuss important characteristics related to the performance of the configurations.
Exponential Convergence of Sinkhorn Under Regularization Scheduling
Venue: arXiv cs.DS 2023
Year: 2023

In 2013, Cuturi [Cut13] introduced the Sinkhorn algorithm for matrix scaling as a method to compute solutions to regularized optimal transport problems. In this paper, aiming at a better convergence rate for a high accuracy solution, we work on understanding the Sinkhorn algorithm under regularization scheduling, and thus modify it with a mechanism that adaptively doubles the regularization parameter $η$ periodically. We prove that such modified version of Sinkhorn has an exponential convergence rate as iteration complexity depending on $\log(1/\varepsilon)$ instead of $\varepsilon^{-O(1)}$ from previous analyses [Cut13][ANWR17] in the optimal transport problems with integral supply and demand. Furthermore, with cost and capacity scaling procedures, the general optimal transport problem can be solved with a logarithmic dependence on $1/\varepsilon$ as well.
Cell-Free Massive MIMO for URLLC: A Finite-Blocklength Analysis
Venue: arXiv cs.IT 2023
Year: 2023

We present a general framework for the characterization of the packet error probability achievable in cell-free Massive multiple-input multiple output (MIMO) architectures deployed to support ultra-reliable low-latency (URLLC) traffic. The framework is general and encompasses both centralized and distributed cell-free architectures, arbitrary fading channels and channel estimation algorithms at both network and user-equipment (UE) sides, as well as arbitrary combining and precoding schemes. The framework is used to perform numerical experiments on specific scenarios, which illustrate the superiority of cell-free architectures compared to cellular architectures in supporting URLLC traffic in uplink and downlink. Also, these numerical experiments provide the following insights into the design of cell-free architectures for URLLC: i) minimum mean square error (MMSE) spatial processing must be used to achieve the URLLC targets; ii) for a given total number of antennas per coverage area, centralized cell-free solutions involving single-antenna access points (APs) offer the best performance in the uplink, thereby highlighting the importance of reducing the average distance between APs and UEs in the URLLC regime; iii) this observation applies also to the downlink, provided that the APs transmit precoded pilots to allow the UEs to estimate accurately the precoded channel.
Robot's Gendering Trouble: A Scoping Review of Gendering Humanoid Robots and its Effects on HRI
Venue: arXiv cs.RO 2023
Year: 2023

The discussion around the problematic practice of gendering humanoid robots has risen to the foreground in the last few years. To lay the basis for a thorough understanding of how robot's "gender" has been understood within the Human-Robot Interaction (HRI) community - i.e., how it has been manipulated, in which contexts, and which effects it has yield on people's perceptions and interactions with robots - we performed a scoping review of the literature. We identified 553 papers relevant for our review retrieved from 5 different databases. The final sample of reviewed papers included 35 papers written between 2005 and 2021, which involved a total of 3902 participants. In this article, we thoroughly summarize these papers by reporting information about their objectives and assumptions on gender (i.e., definitions and reasons to manipulate gender), their manipulation of robot's "gender" (i.e., gender cues and manipulation checks), their experimental designs (e.g., demographics of participants, employed robots), and their results (i.e., main and interaction effects). The review reveals that robot's "gender" does not affect crucial constructs for the HRI, such as likability and acceptance, but rather bears its strongest effect on stereotyping. We leverage our different epistemological backgrounds in Social Robotics and Gender Studies to provide a comprehensive interdisciplinary perspective on the results of the review and suggest ways to move forward in the field of HRI.
Memory Population in Continual Learning via Outlier Elimination
Venue: arXiv cs.LG 2023
Year: 2023

Catastrophic forgetting, the phenomenon of forgetting previously learned tasks when learning a new one, is a major hurdle in developing continual learning algorithms. A popular method to alleviate forgetting is to use a memory buffer, which stores a subset of previously learned task examples for use during training on new tasks. The de facto method of filling memory is by randomly selecting previous examples. However, this process could introduce outliers or noisy samples that could hurt the generalization of the model. This paper introduces Memory Outlier Elimination (MOE), a method for identifying and eliminating outliers in the memory buffer by choosing samples from label-homogeneous subpopulations. We show that a space with a high homogeneity is related to a feature space that is more representative of the class distribution. In practice, MOE removes a sample if it is surrounded by samples from different labels. We demonstrate the effectiveness of MOE on CIFAR-10, CIFAR-100, and CORe50, outperforming previous well-known memory population methods.
Incorporating functional summary information in Bayesian neural networks using a Dirichlet process likelihood approach
Venue: arXiv cs.LG 2023
Year: 2023

Bayesian neural networks (BNNs) can account for both aleatoric and epistemic uncertainty. However, in BNNs the priors are often specified over the weights which rarely reflects true prior knowledge in large and complex neural network architectures. We present a simple approach to incorporate prior knowledge in BNNs based on external summary information about the predicted classification probabilities for a given dataset. The available summary information is incorporated as augmented data and modeled with a Dirichlet process, and we derive the corresponding \emph{Summary Evidence Lower BOund}. The approach is founded on Bayesian principles, and all hyperparameters have a proper probabilistic interpretation. We show how the method can inform the model about task difficulty and class imbalance. Extensive experiments show that, with negligible computational overhead, our method parallels and in many cases outperforms popular alternatives in accuracy, uncertainty calibration, and robustness against corruptions with both balanced and imbalanced data.
Discourse-Aware Graph Networks for Textual Logical Reasoning
Venue: arXiv cs.CL 2023
Year: 2023

Textual logical reasoning, especially question-answering (QA) tasks with logical reasoning, requires awareness of particular logical structures. The passage-level logical relations represent entailment or contradiction between propositional units (e.g., a concluding sentence). However, such structures are unexplored as current QA systems focus on entity-based relations. In this work, we propose logic structural-constraint modeling to solve the logical reasoning QA and introduce discourse-aware graph networks (DAGNs). The networks first construct logic graphs leveraging in-line discourse connectives and generic logic theories, then learn logic representations by end-to-end evolving the logic relations with an edge-reasoning mechanism and updating the graph features. This pipeline is applied to a general encoder, whose fundamental features are joined with the high-level logic features for answer prediction. Experiments on three textual logical reasoning datasets demonstrate the reasonability of the logical structures built in DAGNs and the effectiveness of the learned logic features. Moreover, zero-shot transfer results show the features' generality to unseen logical texts.
Predicting Out-of-Domain Generalization with Neighborhood Invariance
Venue: arXiv cs.LG 2023
Year: 2023

Developing and deploying machine learning models safely depends on the ability to characterize and compare their abilities to generalize to new environments. Although recent work has proposed a variety of methods that can directly predict or theoretically bound the generalization capacity of a model, they rely on strong assumptions such as matching train/test distributions and access to model gradients. In order to characterize generalization when these assumptions are not satisfied, we propose neighborhood invariance, a measure of a classifier's output invariance in a local transformation neighborhood. Specifically, we sample a set of transformations and given an input test point, calculate the invariance as the largest fraction of transformed points classified into the same class. Crucially, our measure is simple to calculate, does not depend on the test point's true label, makes no assumptions about the data distribution or model, and can be applied even in out-of-domain (OOD) settings where existing methods cannot, requiring only selecting a set of appropriate data transformations. In experiments on robustness benchmarks in image classification, sentiment analysis, and natural language inference, we demonstrate a strong and robust correlation between our neighborhood invariance measure and actual OOD generalization on over 4,600 models evaluated on over 100 unique train/test domain pairs.
Width Helps and Hinders Splitting Flows
Venue: arXiv cs.DS 2023
Year: 2023

Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation $X$ on a directed graph $G$ into weighted source-to-sink paths whose superposition equals $X$. We show that, for acyclic graphs, considering the \emph{width} of the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class of \emph{width-stable} graphs, for which a popular heuristic is a \gwsimple-approximation ($|X|$ being the total flow of $X$), and strengthen its worst-case approximation ratio from $Ω(\sqrt{m})$ to $Ω(m / \log m)$ for sparse graphs, where $m$ is the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a $(\lceil \log \Vert X \Vert \rceil +1)$-approximation ($\Vert X \Vert$ being the maximum absolute value of $X$ on any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations ($\Vert X \Vert \leq 1$), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [ALENEX 2018], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version.
Robustness Analysis of Video-Language Models Against Visual and Language Perturbations
Venue: arXiv cs.CV 2023
Year: 2023

Joint visual and language modeling on large-scale datasets has recently shown good progress in multi-modal tasks when compared to single modal learning. However, robustness of these approaches against real-world perturbations has not been studied. In this work, we perform the first extensive robustness study of video-language models against various real-world perturbations. We focus on text-to-video retrieval and propose two large-scale benchmark datasets, MSRVTT-P and YouCook2-P, which utilize 90 different visual and 35 different text perturbations. The study reveals some interesting initial findings from the studied models: 1) models are generally more susceptible when only video is perturbed as opposed to when only text is perturbed, 2) models that are pre-trained are more robust than those trained from scratch, 3) models attend more to scene and objects rather than motion and action. We hope this study will serve as a benchmark and guide future research in robust video-language learning. The benchmark introduced in this study along with the code and datasets is available at https://bit.ly/3CNOly4.
A Comprehensive Review of Visual-Textual Sentiment Analysis from Social Media Networks
Venue: arXiv cs.CL 2023
Year: 2023

Social media networks have become a significant aspect of people's lives, serving as a platform for their ideas, opinions and emotions. Consequently, automated sentiment analysis (SA) is critical for recognising people's feelings in ways that other information sources cannot. The analysis of these feelings revealed various applications, including brand evaluations, YouTube film reviews and healthcare applications. As social media continues to develop, people post a massive amount of information in different forms, including text, photos, audio and video. Thus, traditional SA algorithms have become limited, as they do not consider the expressiveness of other modalities. By including such characteristics from various material sources, these multimodal data streams provide new opportunities for optimising the expected results beyond text-based SA. Our study focuses on the forefront field of multimodal SA, which examines visual and textual data posted on social media networks. Many people are more likely to utilise this information to express themselves on these platforms. To serve as a resource for academics in this rapidly growing field, we introduce a comprehensive overview of textual and visual SA, including data pre-processing, feature extraction techniques, sentiment benchmark datasets, and the efficacy of multiple classification methodologies suited to each field. We also provide a brief introduction of the most frequently utilised data fusion strategies and a summary of existing research on visual-textual SA. Finally, we highlight the most significant challenges and investigate several important sentiment applications.
Group Equality in Adaptive Submodular Maximization
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we study the classic submodular maximization problem subject to a group equality constraint under both non-adaptive and adaptive settings. It has been shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to under- or over-representation of some particular groups. This motivates us to study the submodular maximization problem with group equality, where we aim to select a group of items to maximize a (possibly non-monotone) submodular utility function subject to a group equality constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint and other fairness notations.
On Non-Linear operators for Geometric Deep Learning
Venue: arXiv cs.LG 2023
Year: 2023

This work studies operators mapping vector and scalar fields defined over a manifold $\mathcal{M}$, and which commute with its group of diffeomorphisms $\text{Diff}(\mathcal{M})$. We prove that in the case of scalar fields $L^p_ω(\mathcal{M,\mathbb{R}})$, those operators correspond to point-wise non-linearities, recovering and extending known results on $\mathbb{R}^d$. In the context of Neural Networks defined over $\mathcal{M}$, it indicates that point-wise non-linear operators are the only universal family that commutes with any group of symmetries, and justifies their systematic use in combination with dedicated linear operators commuting with specific symmetries. In the case of vector fields $L^p_ω(\mathcal{M},T\mathcal{M})$, we show that those operators are solely the scalar multiplication. It indicates that $\text{Diff}(\mathcal{M})$ is too rich and that there is no universal class of non-linear operators to motivate the design of Neural Networks over the symmetries of $\mathcal{M}$.