OpenRaiser/Intern-Atlas huggingface dataset:
Learning Low Degree Hypergraphs
Venue: arXiv cs.DS 2024
Year: 2024

We study the problem of learning a hypergraph via edge detecting queries. In this problem, a learner queries subsets of vertices of a hidden hypergraph and observes whether these subsets contain an edge or not. In general, learning a hypergraph with $m$ edges of maximum size $d$ requires $Ω((2m/d)^{d/2})$ queries. In this paper, we aim to identify families of hypergraphs that can be learned without suffering from a query complexity that grows exponentially in the size of the edges. We show that hypermatchings and low-degree near-uniform hypergraphs with $n$ vertices are learnable with poly$(n)$ queries. For learning hypermatchings (hypergraphs of maximum degree $ 1$), we give an $O(\log^3 n)$-round algorithm with $O(n \log^5 n)$ queries. We complement this upper bound by showing that there are no algorithms with poly$(n)$ queries that learn hypermatchings in $o(\log \log n)$ adaptive rounds. For hypergraphs with maximum degree $Δ$ and edge size ratio $ρ$, we give a non-adaptive algorithm with $O((2n)^{ρΔ+1}\log^2 n)$ queries. To the best of our knowledge, these are the first algorithms with poly$(n, m)$ query complexity for learning non-trivial families of hypergraphs that have a super-constant number of edges of super-constant size.
On Grid Codes
Venue: arXiv cs.IT 2024
Year: 2024

Generating functions for the size of a $r$-sphere, with respect to the Manhattan distance in an $n$-dimensional grid, are used to provide explicit formulas for the minimum and maximum size of an $r$-ball centered at a point of the grid. This allows us to offer versions of the Hamming and Gilbert-Varshamov bounds for codes in these grids. Relations between the Hamming, Manhattan, and Lee distances defined in an abelian group $G$ are studied. A formula for the minimum Hamming distance of codes that are cyclic subgroups of $G$ is presented. Furthermore, several lower bounds for the minimum Manhattan distance of these codes based on their minimum Hamming and Lee distances are established. Examples illustrating the main results are presented, including several SageMath implementations.
Rethinking the Zigzag Flattening for Image Reading
Venue: arXiv cs.CV 2024
Year: 2024

Sequence ordering of word vector matters a lot to text reading, which has been proven in natural language processing (NLP). However, the rule of different sequence ordering in computer vision (CV) was not well explored, e.g., why the ``zigzag" flattening (ZF) is commonly utilized as a default option to get the image patches ordering in vision networks. Notably, when decomposing multi-scale images, the ZF could not maintain the invariance of feature point positions. To this end, we investigate the Hilbert fractal flattening (HF) as another method for sequence ordering in CV and contrast it against ZF. The HF has proven to be superior to other curves in maintaining spatial locality, when performing multi-scale transformations of dimensional space. And it can be easily plugged into most deep neural networks (DNNs). Extensive experiments demonstrate that it can yield consistent and significant performance boosts for a variety of architectures. Finally, we hope that our studies spark further research about the flattening strategy of image reading.
A Laboratory Experiment on Using Different Financial-Incentivization Schemes in Software-Engineering Experimentation
Venue: arXiv cs.SE 2024
Year: 2024

In software-engineering research, many empirical studies are conducted with open-source or industry developers. However, in contrast to other research communities like economics or psychology, only few experiments use financial incentives (i.e., paying money) as a strategy to motivate participants' behavior and reward their performance. The most recent version of the SIGSOFT Empirical Standards mentions payouts only for increasing participation in surveys, but not for mimicking real-world motivations and behavior in experiments. Within this article, we report a controlled experiment in which we tackled this gap by studying how different financial incentivization schemes impact developers. For this purpose, we first conducted a survey on financial incentives used in the real-world, based on which we designed three incentivization schemes: (1) a performance-dependent scheme that employees prefer, (2) a scheme that is performance-independent, and (3) a scheme that mimics open-source development. Then, using a between-subject experimental design, we explored how these three schemes impact participants' performance. Our findings indicate that the different schemes can impact participants' performance in software-engineering experiments. Due to the small sample sizes, our results are not statistically significant, but we can still observe clear tendencies. Our contributions help understand the impact of financial incentives on participants in experiments as well as real-world scenarios, guiding researchers in designing experiments and organizations in compensating developers.
On the complexity of Chow and Hurwitz forms
Venue: arXiv cs.CC 2024
Year: 2024

We consider the bit complexity of computing Chow forms and their generalization to multiprojective spaces. We develop a deterministic algorithm using resultants and obtain a single exponential complexity upper bound. Earlier computational results for Chow forms were in the arithmetic complexity model, and our result represents the first bit complexity bound. We also extend our algorithm to Hurwitz forms in projective space, and explore connections between multiprojective Hurwitz forms and matroid theory. The motivation for our work comes from incidence geometry where intriguing computational algebra problems remain open.
A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs
Venue: arXiv cs.DS 2024
Year: 2024

The Steiner tree problem aims to determine a minimum edge-weighted tree that spans a given set of terminal vertices from a given graph. In the past decade, a considerable number of algorithms have been developed to solve this computationally challenging problem. However, existing algorithms typically encounter difficulties for solving large instances, i.e., graphs with a high number of vertices and terminals. In this paper, we present a novel partition-and-merge algorithm to effectively solve this problem in large graphs. The algorithm breaks the input network into small subgraphs and then merges the subgraphs in a bottom-up manner. In the merging procedure, partial Steiner trees in the subgraphs are also created and optimized by efficient local optimization. When the merging procedure ends, the algorithm terminates and reports the final solution for the input graph. We evaluated the algorithm on a wide range of benchmark instances, showing that the algorithm outperforms the best-known algorithms on large instances and competes favorably with them on small or medium-sized instances.
Privacy-preserving machine learning with tensor networks
Venue: arXiv cs.CR 2024
Year: 2024

Tensor networks, widely used for providing efficient representations of low-energy states of local quantum many-body systems, have been recently proposed as machine learning architectures which could present advantages with respect to traditional ones. In this work we show that tensor network architectures have especially prospective properties for privacy-preserving machine learning, which is important in tasks such as the processing of medical records. First, we describe a new privacy vulnerability that is present in feedforward neural networks, illustrating it in synthetic and real-world datasets. Then, we develop well-defined conditions to guarantee robustness to such vulnerability, which involve the characterization of models equivalent under gauge symmetry. We rigorously prove that such conditions are satisfied by tensor-network architectures. In doing so, we define a novel canonical form for matrix product states, which has a high degree of regularity and fixes the residual gauge that is left in the canonical forms based on singular value decompositions. We supplement the analytical findings with practical examples where matrix product states are trained on datasets of medical records, which show large reductions on the probability of an attacker extracting information about the training dataset from the model's parameters. Given the growing expertise in training tensor-network architectures, these results imply that one may not have to be forced to make a choice between accuracy in prediction and ensuring the privacy of the information processed.
Understanding Adversarial Robustness from Feature Maps of Convolutional Layers
Venue: arXiv cs.CV 2024
Year: 2024

The adversarial robustness of a neural network mainly relies on two factors: model capacity and anti-perturbation ability. In this paper, we study the anti-perturbation ability of the network from the feature maps of convolutional layers. Our theoretical analysis discovers that larger convolutional feature maps before average pooling can contribute to better resistance to perturbations, but the conclusion is not true for max pooling. It brings new inspiration to the design of robust neural networks and urges us to apply these findings to improve existing architectures. The proposed modifications are very simple and only require upsampling the inputs or slightly modifying the stride configurations of downsampling operators. We verify our approaches on several benchmark neural network architectures, including AlexNet, VGG, RestNet18, and PreActResNet18. Non-trivial improvements in terms of both natural accuracy and adversarial robustness can be achieved under various attack and defense mechanisms. The code is available at \url{https://github.com/MTandHJ/rcm}.
Alpha-NML Universal Predictors
Venue: arXiv cs.IT 2024
Year: 2024

Inspired by the connection between classical regret measures employed in universal prediction and Rényi divergence, we introduce a new class of universal predictors that depend on a real parameter $α\geq 1$. This class interpolates two well-known predictors, the mixture estimators, that include the Laplace and the Krichevsky-Trofimov predictors, and the Normalized Maximum Likelihood (NML) estimator. We point out some advantages of this new class of predictors and study its benefits from two complementary viewpoints: (1) we prove its optimality when the maximal Rényi divergence is considered as a regret measure, which can be interpreted operationally as a middle ground between the standard average and worst-case regret measures; (2) we discuss how it can be employed when NML is not a viable option, as an alternative to other predictors such as Luckiness NML. Finally, we apply the $α$-NML predictor to the class of discrete memoryless sources (DMS), where we derive simple formulas to compute the predictor and analyze its asymptotic performance in terms of worst-case regret.
Motion-aware Dynamic Graph Neural Network for Video Compressive Sensing
Venue: arXiv cs.CV 2024
Year: 2024

Video snapshot compressive imaging (SCI) utilizes a 2D detector to capture sequential video frames and compress them into a single measurement. Various reconstruction methods have been developed to recover the high-speed video frames from the snapshot measurement. However, most existing reconstruction methods are incapable of efficiently capturing long-range spatial and temporal dependencies, which are critical for video processing. In this paper, we propose a flexible and robust approach based on the graph neural network (GNN) to efficiently model non-local interactions between pixels in space and time regardless of the distance. Specifically, we develop a motion-aware dynamic GNN for better video representation, i.e., represent each node as the aggregation of relative neighbors under the guidance of frame-by-frame motions, which consists of motion-aware dynamic sampling, cross-scale node sampling, global knowledge integration, and graph aggregation. Extensive results on both simulation and real data demonstrate both the effectiveness and efficiency of the proposed approach, and the visualization illustrates the intrinsic dynamic sampling operations of our proposed model for boosting the video SCI reconstruction results. The code and model will be released.
Capability-based Frameworks for Industrial Robot Skills: a Survey
Venue: arXiv cs.RO 2024
Year: 2024

The research community is puzzled with words like skill, action, atomic unit and others when describing robots' capabilities. However, for giving the possibility to integrate capabilities in industrial scenarios, a standardization of these descriptions is necessary. This work uses a structured review approach to identify commonalities and differences in the research community of robots' skill frameworks. Through this method, 210 papers were analyzed and three main results were obtained. First, the vast majority of authors agree on a taxonomy based on task, skill and primitive. Second, the most investigated robots' capabilities are pick and place. Third, industrial oriented applications focus more on simple robots' capabilities with fixed parameters while ensuring safety aspects. Therefore, this work emphasizes that a taxonomy based on task, skill and primitives should be used by future works to align with existing literature. Moreover, further research is needed in the industrial domain for parametric robots' capabilities while ensuring safety.
Active Self-Semi-Supervised Learning for Few Labeled Samples
Venue: arXiv cs.CV 2024
Year: 2024

Training deep models with limited annotations poses a significant challenge when applied to diverse practical domains. Employing semi-supervised learning alongside the self-supervised model offers the potential to enhance label efficiency. However, this approach faces a bottleneck in reducing the need for labels. We observed that the semi-supervised model disrupts valuable information from self-supervised learning when only limited labels are available. To address this issue, this paper proposes a simple yet effective framework, active self-semi-supervised learning (AS3L). AS3L bootstraps semi-supervised models with prior pseudo-labels (PPL). These PPLs are obtained by label propagation over self-supervised features. Based on the observations the accuracy of PPL is not only affected by the quality of features but also by the selection of the labeled samples. We develop active learning and label propagation strategies to obtain accurate PPL. Consequently, our framework can significantly improve the performance of models in the case of limited annotations while demonstrating fast convergence. On the image classification tasks across four datasets, our method outperforms the baseline by an average of 5.4\%. Additionally, it achieves the same accuracy as the baseline method in about 1/3 of the training time.
Approaching Massive MIMO Performance with Reconfigurable Intelligent Surfaces: We Do Not Need Many Antennas
Venue: arXiv cs.IT 2024
Year: 2024

This paper considers an antenna structure where a (non-large) array of radiating elements is placed at short distance in front of a reconfigurable intelligent surface (RIS), herein nicknamed reconfigurable intelligent base station (RIBS). We firstly derive a closed-form expression for the channel between the array of radiating elements and the RIS that captures the near-field effects, and give some considerations on the channel hardening and favorable propagation in this scenario. Focusing on both active and passive RIS, we describe channel estimation and downlink signal processing techniques suitable for the RIBS structure. Additionally, we formulate and solve an optimization problem aimed at maximizing the fairness among the users with respect to the downlink power coefficients and RIS configuration both in the cases of active and passive RIBS. Numerical results show that the proposed structure is effective and capable of outperforming conventional non-RIS aided MIMO systems, especially in the case of active RIBS. The proposed antenna structure is thus shown to be able to approach massive MIMO performance levels in a cost-effective way with reduced hardware resources.
Point-Unet: A Context-aware Point-based Neural Network for Volumetric Segmentation
Venue: arXiv cs.CV 2024
Year: 2024

Medical image analysis using deep learning has recently been prevalent, showing great performance for various downstream tasks including medical image segmentation and its sibling, volumetric image segmentation. Particularly, a typical volumetric segmentation network strongly relies on a voxel grid representation which treats volumetric data as a stack of individual voxel `slices', which allows learning to segment a voxel grid to be as straightforward as extending existing image-based segmentation networks to the 3D domain. However, using a voxel grid representation requires a large memory footprint, expensive test-time and limiting the scalability of the solutions. In this paper, we propose Point-Unet, a novel method that incorporates the efficiency of deep learning with 3D point clouds into volumetric segmentation. Our key idea is to first predict the regions of interest in the volume by learning an attentional probability map, which is then used for sampling the volume into a sparse point cloud that is subsequently segmented using a point-based neural network. We have conducted the experiments on the medical volumetric segmentation task with both a small-scale dataset Pancreas and large-scale datasets BraTS18, BraTS19, and BraTS20 challenges. A comprehensive benchmark on different metrics has shown that our context-aware Point-Unet robustly outperforms the SOTA voxel-based networks at both accuracies, memory usage during training, and time consumption during testing. Our code is available at https://github.com/VinAIResearch/Point-Unet.
The Sandbox Environment for Generalizable Agent Research (SEGAR)
Venue: arXiv cs.LG 2024
Year: 2024

A broad challenge of research on generalization for sequential decision-making tasks in interactive environments is designing benchmarks that clearly landmark progress. While there has been notable headway, current benchmarks either do not provide suitable exposure nor intuitive control of the underlying factors, are not easy-to-implement, customizable, or extensible, or are computationally expensive to run. We built the Sandbox Environment for Generalizable Agent Research (SEGAR) with all of these things in mind. SEGAR improves the ease and accountability of generalization research in RL, as generalization objectives can be easy designed by specifying task distributions, which in turns allows the researcher to measure the nature of the generalization objective. We present an overview of SEGAR and how it contributes to these goals, as well as experiments that demonstrate a few types of research questions SEGAR can help answer.
Strategy Complexity of Reachability in Countable Stochastic 2-Player Games
Venue: arXiv cs.GT 2024
Year: 2024

We study countably infinite stochastic 2-player games with reachability objectives. Our results provide a complete picture of the memory requirements of $\varepsilon$-optimal (resp. optimal) strategies. These results depend on the size of the players' action sets and on whether one requires strategies that are uniform (i.e., independent of the start state). Our main result is that $\varepsilon$-optimal (resp. optimal) Maximizer strategies require infinite memory if Minimizer is allowed infinite action sets. This lower bound holds even under very strong restrictions. Even in the special case of infinitely branching turn-based reachability games, even if all states allow an almost surely winning Maximizer strategy, strategies with a step counter plus finite private memory are still useless. Regarding uniformity, we show that for Maximizer there need not exist positional (i.e., memoryless) uniformly $\varepsilon$-optimal strategies even in the special case of finite action sets or in finitely branching turn-based games. On the other hand, in games with finite action sets, there always exists a uniformly $\varepsilon$-optimal Maximizer strategy that uses just one bit of public memory.
Unifying cubical and multimodal type theory
Venue: arXiv cs.LO 2024
Year: 2024

In this paper we combine the principled approach to modalities from multimodal type theory (MTT) with the computationally well-behaved realization of identity types from cubical type theory (CTT). The result -- cubical modal type theory (Cubical MTT) -- has the desirable features of both systems. In fact, the whole is more than the sum of its parts: Cubical MTT validates desirable extensionality principles for modalities that MTT only supported through ad hoc means. We investigate the semantics of Cubical MTT and provide an axiomatic approach to producing models of Cubical MTT based on the internal language of topoi and use it to construct presheaf models. Finally, we demonstrate the practicality and utility of this axiomatic approach to models by constructing a model of (cubical) guarded recursion in a cubical version of the topos of trees. We then use this model to justify an axiomatization of Löb induction and thereby use Cubical MTT to smoothly reason about guarded recursion.
Modeling Attrition in Recommender Systems with Departing Bandits
Venue: arXiv cs.LG 2024
Year: 2024

Traditionally, when recommender systems are formalized as multi-armed bandits, the policy of the recommender system influences the rewards accrued, but not the length of interaction. However, in real-world systems, dissatisfied users may depart (and never come back). In this work, we propose a novel multi-armed bandit setup that captures such policy-dependent horizons. Our setup consists of a finite set of user types, and multiple arms with Bernoulli payoffs. Each (user type, arm) tuple corresponds to an (unknown) reward probability. Each user's type is initially unknown and can only be inferred through their response to recommendations. Moreover, if a user is dissatisfied with their recommendation, they might depart the system. We first address the case where all users share the same type, demonstrating that a recent UCB-based algorithm is optimal. We then move forward to the more challenging case, where users are divided among two types. While naive approaches cannot handle this setting, we provide an efficient learning algorithm that achieves $\tilde{O}(\sqrt{T})$ regret, where $T$ is the number of users.
Does Audio Deepfake Detection Generalize?
Venue: arXiv cs.SD 2024
Year: 2024

Current text-to-speech algorithms produce realistic fakes of human voices, making deepfake detection a much-needed area of research. While researchers have presented various techniques for detecting audio spoofs, it is often unclear exactly why these architectures are successful: Preprocessing steps, hyperparameter settings, and the degree of fine-tuning are not consistent across related work. Which factors contribute to success, and which are accidental? In this work, we address this problem: We systematize audio spoofing detection by re-implementing and uniformly evaluating architectures from related work. We identify overarching features for successful audio deepfake detection, such as using cqtspec or logspec features instead of melspec features, which improves performance by 37% EER on average, all other factors constant. Additionally, we evaluate generalization capabilities: We collect and publish a new dataset consisting of 37.9 hours of found audio recordings of celebrities and politicians, of which 17.2 hours are deepfakes. We find that related work performs poorly on such real-world data (performance degradation of up to one thousand percent). This may suggest that the community has tailored its solutions too closely to the prevailing ASVSpoof benchmark and that deepfakes are much harder to detect outside the lab than previously thought.