OpenRaiser/Intern-Atlas huggingface dataset:
Initial nonrepetitive complexity of regular episturmian words and their Diophantine exponents
Venue: arXiv cs.FL 2024
Year: 2024

Regular episturmian words are episturmian words whose directive words have a regular and restricted form making them behave more like Sturmian words than general episturmian words. We present a method to evaluate the initial nonrepetitive complexity of regular episturmian words extending the work of Wojcik on Sturmian words. For this, we develop a theory of generalized Ostrowski numeration systems and show how to associate with each episturmian word a unique sequence of numbers written in this numeration system. The description of the initial nonrepetitive complexity allows us to obtain novel results on the Diophantine exponents of regular episturmian words. We prove that the Diophantine exponent of a regular episturmian word is finite if and only if its directive word has bounded partial quotients. Moreover, we prove that the Diophantine exponent of a regular episturmian word is strictly greater than $2$ if the sequence of partial quotients is eventually at least $3$. Given an infinite word $x$ over an integer alphabet, we may consider a real number $ξ_x$ having $x$ as a fractional part. The Diophantine exponent of $x$ is a lower bound for the irrationality exponent of $ξ_x$. Our results thus yield nontrivial lower bounds for the irrationality exponents of real numbers whose fractional parts are regular episturmian words. As a consequence, we identify a new uncountable class of transcendental numbers whose irrationality exponents are strictly greater than $2$. This class contains an uncountable subclass of Liouville numbers.
Intersection patterns in spaces with a forbidden homological minor
Venue: arXiv cs.CG 2024
Year: 2024

In this paper we study generalizations of classical results on intersection patterns of set systems in $\mathbb{R}^d$, such as the fractional Helly theorem or the $(p,q)$-theorem, in the setting of arbitrary triangulable spaces with a forbidden homological minor. Given a simplicial complex $K$ and an integer $b$, we say that a family $\mathcal{F}$ of subcomplexes of some simplicial complex $\mathcal{U}$ is a \emph{$(K,b)$-free cover} if (i) $K$ is a forbidden homological minor of $\mathcal{U}$, and (ii) the $j$th reduced Betti number $\tildeβ_j(\bigcap_{S\in {\mathcal{G}}}S,\mathbb{Z}_2)$ is strictly less than $b$ for all $0\leq j < \dim K$ and all nonempty subfamilies $\mathcal{G}\subseteq \mathcal{F}$. We show that for every $K$ and $b$, the fractional Helly number of a $(K,b)$-free cover is at most $μ(K)+1$, where $μ(K)$ is the maximum sum of the dimensions of two disjoint faces in~$K$. This implies that the assertion of the $(p,q)$-theorem holds for every $p \ge q > μ(K)$ and every $(K,b)$-free cover $\mathcal{F}$. For $b=1$ and a suitable $K$ this recovers the original $(p,q)$-theorem and its generalization to good covers. Interestingly, our results show that that the range of parameters $(p,q)$ for which the $(p,q)$-theorem holds is independent of $b$. Our proofs use Ramsey-type arguments combined with the notion of stair convexity of Bukh et al. to construct (forbidden) homological minors in cubical complexes.
A Link between Coding Theory and Cross-Validation with Applications
Venue: arXiv cs.LG 2024
Year: 2024

How many different binary classification problems a single learning algorithm can solve on a fixed data with exactly zero or at most a given number of cross-validation errors? While the number in the former case is known to be limited by the no-free-lunch theorem, we show that the exact answers are given by the theory of error detecting codes. As a case study, we focus on the AUC performance measure and leave-pair-out cross-validation (LPOCV), in which every possible pair of data with different class labels is held out at a time. We show that the maximal number of classification problems with fixed class proportion, for which a learning algorithm can achieve zero LPOCV error, equals the maximal number of code words in a constant weight code (CWC), with certain technical properties. We then generalize CWCs by introducing light CWCs, and prove an analogous result for nonzero LPOCV errors and light CWCs. Moreover, we prove both upper and lower bounds on the maximal numbers of code words in light CWCs. Finally, as an immediate practical application, we develop new LPOCV based randomization tests for learning algorithms that generalize the classical Wilcoxon-Mann-Whitney U test.
Approval-Based Committee Voting under Incomplete Information
Venue: arXiv cs.GT 2024
Year: 2024

We investigate approval-based committee voting with incomplete information about the approval preferences of voters. We consider several models of incompleteness where each voter partitions the set of candidates into approved, disapproved, and unknown candidates, possibly with ordinal preference constraints among candidates in the latter category. This captures scenarios where voters have not evaluated all candidates and/or it is unknown where voters draw the threshold between approved and disapproved candidates. We study the complexity of some fundamental computational problems for a number of classic approval-based committee voting rules including Proportional Approval Voting and Chamberlin-Courant. These problems include determining whether a given set of candidates is a possible or necessary winning committee and whether a given candidate is possibly or necessarily a member of the winning committee. We also consider proportional representation axioms and the problem of deciding whether a given committee is possibly or necessarily representative.
Scaling the weight parameters in Markov logic networks and relational logistic regression models
Venue: arXiv cs.AI 2024
Year: 2024

We consider Markov logic networks and relational logistic regression as two fundamental representation formalisms in statistical relational artificial intelligence that use weighted formulas in their specification. However, Markov logic networks are based on undirected graphs, while relational logistic regression is based on directed acyclic graphs. We show that when scaling the weight parameters with the domain size, the asymptotic behaviour of a relational logistic regression model is transparently controlled by the parameters, and we supply an algorithm to compute asymptotic probabilities. We also show using two examples that this is not true for Markov logic networks. We also discuss using several examples, mainly from the literature, how the application context can help the user to decide when such scaling is appropriate and when using the raw unscaled parameters might be preferable. We highlight random sampling as a particularly promising area of application for scaled models and expound possible avenues for further research.
Are Bias Mitigation Techniques for Deep Learning Effective?
Venue: arXiv cs.LG 2024
Year: 2024

A critical problem in deep learning is that systems learn inappropriate biases, resulting in their inability to perform well on minority groups. This has led to the creation of multiple algorithms that endeavor to mitigate bias. However, it is not clear how effective these methods are. This is because study protocols differ among papers, systems are tested on datasets that fail to test many forms of bias, and systems have access to hidden knowledge or are tuned specifically to the test set. To address this, we introduce an improved evaluation protocol, sensible metrics, and a new dataset, which enables us to ask and answer critical questions about bias mitigation algorithms. We evaluate seven state-of-the-art algorithms using the same network architecture and hyperparameter selection policy across three benchmark datasets. We introduce a new dataset called Biased MNIST that enables assessment of robustness to multiple bias sources. We use Biased MNIST and a visual question answering (VQA) benchmark to assess robustness to hidden biases. Rather than only tuning to the test set distribution, we study robustness across different tuning distributions, which is critical because for many applications the test distribution may not be known during development. We find that algorithms exploit hidden biases, are unable to scale to multiple forms of bias, and are highly sensitive to the choice of tuning set. Based on our findings, we implore the community to adopt more rigorous assessment of future bias mitigation methods. All data, code, and results are publicly available at: https://github.com/erobic/bias-mitigators.
On the Benefits of Traffic "Reprofiling'' -- The Single Hop Case
Venue: arXiv cs.NI 2024
Year: 2024

The need to guarantee hard delay bounds to traffic flows with deterministic traffic profiles, e.g., token buckets, arises in a number of network settings. Of interest are solutions that offer such guarantees while minimizing network bandwidth. The paper explores a basic building block towards realizing such solutions, namely, a single hop configuration. The main results are in the form of optimal solutions for meeting local deadlines under schedulers of varying complexity and therefore cost. The results demonstrate how judiciously modifying flows' traffic profiles, i.e., reprofiling them, can help simple schedulers reduce the bandwidth they require, often performing nearly as well as more complex ones.
RadarScenes: A Real-World Radar Point Cloud Data Set for Automotive Applications
Venue: arXiv cs.LG 2024
Year: 2024

A new automotive radar data set with measurements and point-wise annotations from more than four hours of driving is presented. Data provided by four series radar sensors mounted on one test vehicle were recorded and the individual detections of dynamic objects were manually grouped to clusters and labeled afterwards. The purpose of this data set is to enable the development of novel (machine learning-based) radar perception algorithms with the focus on moving road users. Images of the recorded sequences were captured using a documentary camera. For the evaluation of future object detection and classification algorithms, proposals for score calculation are made so that researchers can evaluate their algorithms on a common basis. Additional information as well as download instructions can be found on the website of the data set: www.radar-scenes.com.
Multimodal Fusion of EMG and Vision for Human Grasp Intent Inference in Prosthetic Hand Control
Venue: arXiv cs.RO 2024
Year: 2024

Objective: For transradial amputees, robotic prosthetic hands promise to regain the capability to perform daily living activities. Current control methods based on physiological signals such as electromyography (EMG) are prone to yielding poor inference outcomes due to motion artifacts, muscle fatigue, and many more. Vision sensors are a major source of information about the environment state and can play a vital role in inferring feasible and intended gestures. However, visual evidence is also susceptible to its own artifacts, most often due to object occlusion, lighting changes, etc. Multimodal evidence fusion using physiological and vision sensor measurements is a natural approach due to the complementary strengths of these modalities. Methods: In this paper, we present a Bayesian evidence fusion framework for grasp intent inference using eye-view video, eye-gaze, and EMG from the forearm processed by neural network models. We analyze individual and fused performance as a function of time as the hand approaches the object to grasp it. For this purpose, we have also developed novel data processing and augmentation techniques to train neural network components. Results: Our results indicate that, on average, fusion improves the instantaneous upcoming grasp type classification accuracy while in the reaching phase by 13.66% and 14.8%, relative to EMG (81.64% non-fused) and visual evidence (80.5% non-fused) individually, resulting in an overall fusion accuracy of 95.3%. Conclusion: Our experimental data analyses demonstrate that EMG and visual evidence show complementary strengths, and as a consequence, fusion of multimodal evidence can outperform each individual evidence modality at any given time.
Deformable Capsules for Object Detection
Venue: arXiv cs.CV 2024
Year: 2024

Capsule networks promise significant benefits over convolutional networks by storing stronger internal representations, and routing information based on the agreement between intermediate representations' projections. Despite this, their success has been limited to small-scale classification datasets due to their computationally expensive nature. Though memory efficient, convolutional capsules impose geometric constraints that fundamentally limit the ability of capsules to model the pose/deformation of objects. Further, they do not address the bigger memory concern of class-capsules scaling up to bigger tasks such as detection or large-scale classification. In this study, we introduce a new family of capsule networks, deformable capsules (\textit{DeformCaps}), to address a very important problem in computer vision: object detection. We propose two new algorithms associated with our \textit{DeformCaps}: a novel capsule structure (\textit{SplitCaps}), and a novel dynamic routing algorithm (\textit{SE-Routing}), which balance computational efficiency with the need for modeling a large number of objects and classes, which have never been achieved with capsule networks before. We demonstrate that the proposed methods efficiently scale up to create the first-ever capsule network for object detection in the literature. Our proposed architecture is a one-stage detection framework and it obtains results on MS COCO which are on par with state-of-the-art one-stage CNN-based methods, while producing fewer false positive detection, generalizing to unusual poses/viewpoints of objects.
One-shot learning for solution operators of partial differential equations
Venue: arXiv cs.LG 2024
Year: 2024

Learning and solving governing equations of a physical system, represented by partial differential equations (PDEs), from data is a central challenge in a variety of areas of science and engineering. Traditional numerical methods for solving PDEs can be computationally expensive for complex systems and require the complete PDEs of the physical system. On the other hand, current data-driven machine learning methods require a large amount of data to learn a surrogate model of the PDE solution operator, which could be impractical. Here, we propose the first solution operator learning method that only requires one PDE solution, i.e., one-shot learning. By leveraging the principle of locality of PDEs, we consider small local domains instead of the entire computational domain and define a local solution operator. The local solution operator is then trained using a neural network, and utilized to predict the solution of a new input function via mesh-based fixed-point iteration (FPI), meshfree local-solution-operator informed neural network (LOINN) or local-solution-operator informed neural network with correction (cLOINN). We test our method on diverse PDEs, including linear or nonlinear PDEs, PDEs defined on complex geometries, and PDE systems, demonstrating the effectiveness and generalization capabilities of our method across these varied scenarios.
Turning Federated Learning Systems Into Covert Channels
Venue: arXiv cs.CR 2024
Year: 2024

Federated learning (FL) goes beyond traditional, centralized machine learning by distributing model training among a large collection of edge clients. These clients cooperatively train a global, e.g., cloud-hosted, model without disclosing their local, private training data. The global model is then shared among all the participants which use it for local predictions. In this paper, we put forward a novel attacker model aiming at turning FL systems into covert channels to implement a stealth communication infrastructure. The main intuition is that, during federated training, a malicious sender can poison the global model by submitting purposely crafted examples. Although the effect of the model poisoning is negligible to other participants, and does not alter the overall model performance, it can be observed by a malicious receiver and used to transmit a single bit.
Wise-SrNet: A Novel Architecture for Enhancing Image Classification by Learning Spatial Resolution of Feature Maps
Venue: arXiv cs.CV 2024
Year: 2024

One of the main challenges since the advancement of convolutional neural networks is how to connect the extracted feature map to the final classification layer. VGG models used two sets of fully connected layers for the classification part of their architectures, which significantly increased the number of models' weights. ResNet and the next deep convolutional models used the Global Average Pooling (GAP) layer to compress the feature map and feed it to the classification layer. Although using the GAP layer reduces the computational cost, but also causes losing spatial resolution of the feature map, which results in decreasing learning efficiency. In this paper, we aim to tackle this problem by replacing the GAP layer with a new architecture called Wise-SrNet. It is inspired by the depthwise convolutional idea and is designed for processing spatial resolution while not increasing computational cost. We have evaluated our method using three different datasets: Intel Image Classification Challenge, MIT Indoors Scenes, and a part of the ImageNet dataset. We investigated the implementation of our architecture on several models of the Inception, ResNet, and DenseNet families. Applying our architecture has revealed a significant effect on increasing convergence speed and accuracy. Our Experiments on images with 224*224 resolution increased the Top-1 accuracy between 2% to 8% on different datasets and models. Running our models on 512*512 resolution images of the MIT Indoors Scenes dataset showed a notable result of improving the Top-1 accuracy within 3% to 26%. We will also demonstrate the GAP layer's disadvantage when the input images are large and the number of classes is not few. In this circumstance, our proposed architecture can do a great help in enhancing classification results. The code is shared at https://github.com/mr7495/image-classification-spatial.
Reconstructing shared dynamics with a deep neural network
Venue: arXiv cs.NE 2024
Year: 2024

Determining hidden shared patterns behind dynamic phenomena can be a game-changer in multiple areas of research. Here we present the principles and show a method to identify hidden shared dynamics from time series by a two-module, feedforward neural network architecture: the Mapper-Coach network. We reconstruct unobserved, continuous latent variable input, the time series generated by a chaotic logistic map, from the observed values of two simultaneously forced chaotic logistic maps. The network has been trained to predict one of the observed time series based on its own past and conditioned on the other observed time series by error-back propagation. It was shown, that after this prediction have been learned successfully, the activity of the bottleneck neuron, connecting the mapper and the coach module, correlated strongly with the latent shared input variable. The method has the potential to reveal hidden components of dynamical systems, where experimental intervention is not possible.
A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
Venue: arXiv cs.FL 2024
Year: 2024

We study the expressiveness and succinctness of history-deterministic pushdown automata (HD-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved based on the run constructed so far, but independently of the remainder of the input word. These are also known as good-for-games pushdown automata. We prove that HD-PDA recognise more languages than deterministic PDA (DPDA) but not all context-free languages (CFL). This class is orthogonal to unambiguous CFL. We further show that HD-PDA can be exponentially more succinct than DPDA, while PDA can be double-exponentially more succinct than HD-PDA. We also study HDness in visibly pushdown automata (VPA), which enjoy better closure properties than PDA, and for which we show that deciding HDness is ExpTime-complete. HD-VPA can be exponentially more succinct than deterministic VPA, while VPA can be exponentially more succinct than HD-VPA. Both of these lower bounds are tight. We then compare HD-PDA with PDA for which composition with games is well-behaved, i.e. good-for-games automata. We show that these two notions coincide, but only if we consider potentially infinitely branching games. Finally, we study the complexity of resolving nondeterminism in HD-PDA. Every HDPDA has a positional resolver, a function that resolves nondeterminism and that is only dependant on the current configuration. Pushdown transducers are sufficient to implement the resolvers of HD-VPA, but not those of HD-PDA. HD-PDA with finite-state resolvers are determinisable.
Identity Concealment Games: How I Learned to Stop Revealing and Love the Coincidences
Venue: arXiv cs.GT 2024
Year: 2024

In an adversarial environment, a hostile player performing a task may behave like a non-hostile one in order not to reveal its identity to an opponent. To model such a scenario, we define identity concealment games: zero-sum stochastic reachability games with a zero-sum objective of identity concealment. To measure the identity concealment of the player, we introduce the notion of an average player. The average player's policy represents the expected behavior of a non-hostile player. We show that there exists an equilibrium policy pair for every identity concealment game and give the optimality equations to synthesize an equilibrium policy pair. If the player's opponent follows a non-equilibrium policy, the player can hide its identity better. For this reason, we study how the hostile player may learn the opponent's policy. Since learning via exploration policies would quickly reveal the hostile player's identity to the opponent, we consider the problem of learning a near-optimal policy for the hostile player using the game runs collected under the average player's policy. Consequently, we propose an algorithm that provably learns a near-optimal policy and give an upper bound on the number of sample runs to be collected.
Reinforcement Learning With Sparse-Executing Actions via Sparsity Regularization
Venue: arXiv cs.LG 2024
Year: 2024

Reinforcement learning (RL) has demonstrated impressive performance in decision-making tasks like embodied control, autonomous driving and financial trading. In many decision-making tasks, the agents often encounter the problem of executing actions under limited budgets. However, classic RL methods typically overlook the challenges posed by such sparse-executing actions. They operate under the assumption that all actions can be taken for a unlimited number of times, both in the formulation of the problem and in the development of effective algorithms. To tackle the issue of limited action execution in RL, this paper first formalizes the problem as a Sparse Action Markov Decision Process (SA-MDP), in which specific actions in the action space can only be executed for a limited time. Then, we propose a policy optimization algorithm, Action Sparsity REgularization (ASRE), which adaptively handles each action with a distinct preference. ASRE operates through two steps: First, ASRE evaluates action sparsity by constrained action sampling. Following this, ASRE incorporates the sparsity evaluation into policy learning by way of an action distribution regularization. We provide theoretical identification that validates the convergence of ASRE to a regularized optimal value function. Experiments on tasks with known sparse-executing actions, where classical RL algorithms struggle to train policy efficiently, ASRE effectively constrains the action sampling and outperforms baselines. Moreover, we present that ASRE can generally improve the performance in Atari games, demonstrating its broad applicability.