OpenRaiser/Intern-Atlas huggingface dataset:
Polar Encoding: A Simple Baseline Approach for Classification with Missing Values
Venue: arXiv cs.LG 2024
Year: 2024

We propose polar encoding, a representation of categorical and numerical $[0,1]$-valued attributes with missing values to be used in a classification context. We argue that this is a good baseline approach, because it can be used with any classification algorithm, preserves missingness information, is very simple to apply and offers good performance. In particular, unlike the existing missing-indicator approach, it does not require imputation, ensures that missing values are equidistant from non-missing values, and lets decision tree algorithms choose how to split missing values, thereby providing a practical realisation of the "missingness incorporated in attributes" (MIA) proposal. Furthermore, we show that categorical and $[0,1]$-valued attributes can be viewed as special cases of a single attribute type, corresponding to the classical concept of barycentric coordinates, and that this offers a natural interpretation of polar encoding as a fuzzified form of one-hot encoding. With an experiment based on twenty real-life datasets with missing values, we show that, in terms of the resulting classification performance, polar encoding performs better than the state-of-the-art strategies "multiple imputation by chained equations" (MICE) and "multiple imputation with denoising autoencoders" (MIDAS) and -- depending on the classifier -- about as well or better than mean/mode imputation with missing-indicators.
Faster parameterized algorithms for modification problems to minor-closed classes
Venue: arXiv cs.DS 2024
Year: 2024

Let ${\cal G}$ be a minor-closed graph class and let $G$ be an $n$-vertex graph. We say that $G$ is a $k$-apex of ${\cal G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to ${\cal G}$. Our first result is an algorithm that decides whether $G$ is a $k$-apex of ${\cal G}$ in time $2^{{\sf poly}(k)}\cdot n^2$, where ${\sf poly}$ is a polynomial function depending on ${\cal G}$. This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020], whose running time was $2^{{\sf poly}(k)}\cdot n^3$. The elimination distance of $G$ to ${\cal G}$, denoted by ${\sf ed}_{\cal G}(G)$, is the minimum number of rounds required to reduce each connected component of $G$ to a graph in ${\cal G}$ by removing one vertex from each connected component in each round. Bulian and Dawar [Algorithmica 2017] provided an FPT-algorithm, with parameter $k$, to decide whether ${\sf ed}_{\cal G}(G)\leq k$. However, its dependence on $k$ is not explicit. We extend the techniques used in the first algorithm to decide whether ${\sf ed}_{\cal G}(G)\leq k$ in time $2^{2^{2^{{\sf poly}(k)}}}\cdot n^2$. This is the first algorithm for this problem with an explicit parametric dependence in $k$. In the special case where ${\cal G}$ excludes some apex-graph as a minor, we give two alternative algorithms, running in time $2^{2^{{\cal O}(k^2\log k)}}\cdot n^2$ and $2^{{\sf poly}(k)}\cdot n^3$ respectively, where $c$ and ${\sf poly}$ depend on ${\cal G}$. As a stepping stone for these algorithms, we provide an algorithm that decides whether ${\sf ed}_{\cal G}(G)\leq k$ in time $2^{{\cal O}({\sf tw}\cdot k+{\sf tw}\log{\sf tw})}\cdot n$, where ${\sf tw}$ is the treewidth of $G$. Finally, we provide explicit upper bounds on the size of the graphs in the minor-obstruction set of the class of graphs ${\cal E}_k({\cal G})=\{G\mid{\sf ed}_{\cal G}(G)\leq k\}$.
Coverage and Rate of Joint Communication and Parameter Estimation in Wireless Networks
Venue: arXiv cs.IT 2024
Year: 2024

From an information theoretic perspective, joint communication and sensing (JCAS) represents a natural generalization of communication network functionality. However, it requires the re-evaluation of network performance from a multi-objective perspective. We develop a novel mathematical framework for characterizing the sensing and communication coverage probability and ergodic rate in JCAS networks. We employ a formulation of sensing parameter estimation based on mutual information to extend the notions of coverage probability and ergodic rate to the radar setting. We define sensing coverage probability as the probability that the rate of information extracted about the parameters of interest associated with a typical radar target exceeds some threshold, and sensing ergodic rate as the spatial average of the aforementioned rate of information. Using this framework, we analyze the downlink sensing and communication coverage and rate of a mmWave JCAS network employing a shared waveform, directional beamforming, and monostatic sensing. Leveraging tools from stochastic geometry, we derive upper and lower bounds for these quantities. We also develop several general technical results including: i) a generic method for obtaining closed form upper and lower bounds on the Laplace Transform of a shot noise process, ii) a new analog of H{ö}lder's Inequality to the setting of harmonic means, and iii) a relation between the Laplace and Mellin Transforms of a non-negative random variable. We use the derived bounds to numerically investigate the performance of JCAS networks under varying base station and blockage density. Among several insights, our numerical analysis indicates that network densification improves sensing SINR performance -- in contrast to communications.
State-of-the-art generalisation research in NLP: A taxonomy and review
Venue: arXiv cs.CL 2024
Year: 2024

The ability to generalise well is one of the primary desiderata of natural language processing (NLP). Yet, what 'good generalisation' entails and how it should be evaluated is not well understood, nor are there any evaluation standards for generalisation. In this paper, we lay the groundwork to address both of these issues. We present a taxonomy for characterising and understanding generalisation research in NLP. Our taxonomy is based on an extensive literature review of generalisation research, and contains five axes along which studies can differ: their main motivation, the type of generalisation they investigate, the type of data shift they consider, the source of this data shift, and the locus of the shift within the modelling pipeline. We use our taxonomy to classify over 400 papers that test generalisation, for a total of more than 600 individual experiments. Considering the results of this review, we present an in-depth analysis that maps out the current state of generalisation research in NLP, and we make recommendations for which areas might deserve attention in the future. Along with this paper, we release a webpage where the results of our review can be dynamically explored, and which we intend to update as new NLP generalisation studies are published. With this work, we aim to take steps towards making state-of-the-art generalisation testing the new status quo in NLP.
GBSVM: Granular-ball Support Vector Machine
Venue: arXiv cs.LG 2024
Year: 2024

GBSVM (Granular-ball Support Vector Machine) is a significant attempt to construct a classifier using the coarse-to-fine granularity of a granular-ball as input, rather than a single data point. It is the first classifier whose input contains no points. However, the existing model has some errors, and its dual model has not been derived. As a result, the current algorithm cannot be implemented or applied. To address these problems, this paper has fixed the errors of the original model of the existing GBSVM, and derived its dual model. Furthermore, a particle swarm optimization algorithm is designed to solve the dual model. The sequential minimal optimization algorithm is also carefully designed to solve the dual model. The solution is faster and more stable than the particle swarm optimization based version. The experimental results on the UCI benchmark datasets demonstrate that GBSVM has good robustness and efficiency. All codes have been released in the open source library at http://www.cquptshuyinxia.com/GBSVM.html or https://github.com/syxiaa/GBSVM.
A Learning-based Framework for Topology-Preserving Segmentation using Quasiconformal Mappings
Venue: arXiv cs.CV 2024
Year: 2024

We propose the Topology-Preserving Segmentation Network, a deformation-based model that can extract objects in an image while maintaining their topological properties. This network generates segmentation masks that have the same topology as the template mask, even when trained with limited data. The network consists of two components: the Deformation Estimation Network, which produces a deformation map that warps the template mask to enclose the region of interest, and the Beltrami Adjustment Module, which ensures the bijectivity of the deformation map by truncating the associated Beltrami coefficient based on Quasiconformal theories. The proposed network can also be trained in an unsupervised manner, eliminating the need for labeled training data. This is achieved by incorporating an unsupervised segmentation loss. Our experimental results on various image datasets show that TPSN achieves better segmentation accuracy than state-of-the-art models with correct topology. Furthermore, we demonstrate TPSN's ability to handle multiple object segmentation.
Enumeration of spatial manipulators by using the concept of Adjacency Matrix
Venue: arXiv cs.RO 2024
Year: 2024

This study is on the enumeration of spatial robotic manipulators, which is an essential basis for a companion study on dimensional synthesis, both of which together present a wider utility in manipulator synthesis. The enumeration of manipulators is done by using adjacency matrix concept. In this paper, a novel way of applying adjacency matrix to spatial manipulators with four types of joints, namely revolute, prismatic, cylindrical and spherical joints, is presented. The limitations of the applicability of the concept to 3D manipulators are discussed. 1-DOF (Degree Of Freedom) manipulators of four links and 2-DOF, 3-DOF and 4-DOF manipulators of three links, four links and five links, are enumerated based on a set of conventions and some assumptions. Finally, 96 1-DOF manipulators of four links, 641 2-DOF manipulators of 5 links, 4 2-DOF manipulators of three links, 8 3-DOF manipulators of four links and 15 4-DOF manipulators of five links are presented.
On the complexity of symmetric vs. functional PCSPs
Venue: arXiv cs.CC 2024
Year: 2024

The complexity of the promise constraint satisfaction problem $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is largely unknown, even for symmetric $\mathbf{A}$ and $\mathbf{B}$, except for the case when $\mathbf{A}$ and $\mathbf{B}$ are Boolean. First, we establish a dichotomy for $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ where $\mathbf{A}, \mathbf{B}$ are symmetric, $\mathbf{B}$ is functional (i.e. any $r-1$ elements of an $r$-ary tuple uniquely determines the last one), and $(\mathbf{A},\mathbf{B})$ satisfies technical conditions we introduce called dependency and additivity. This result implies a dichotomy for $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ with $\mathbf{A},\mathbf{B}$ symmetric and $\mathbf{B}$ functional if (i) $\mathbf{A}$ is Boolean, or (ii) $\mathbf{A}$ is a hypergraph of a small uniformity, or (iii) $\mathbf{A}$ has a relation $R^{\mathbf{A}}$ of arity at least 3 such that the hypergraph diameter of $(A, R^{\mathbf{A}})$ is at most 1. Second, we show that for $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, where $\mathbf{A}$ and $\mathbf{B}$ contain a single relation, $\mathbf{A}$ satisfies a technical condition called balancedness, and $\mathbf{B}$ is arbitrary, the combined basic linear programming relaxation (BLP) and the affine integer programming relaxation (AIP) is no more powerful than the (in general strictly weaker) AIP relaxation. Balanced $\mathbf{A}$ include symmetric $\mathbf{A}$ or, more generally, $\mathbf{A}$ preserved by a transitive permutation group.
Dynamic Latent Separation for Deep Learning
Venue: arXiv cs.LG 2024
Year: 2024

A core problem in machine learning is to learn expressive latent variables for model prediction on complex data that involves multiple sub-components in a flexible and interpretable fashion. Here, we develop an approach that improves expressiveness, provides partial interpretation, and is not restricted to specific applications. The key idea is to dynamically distance data samples in the latent space and thus enhance the output diversity. Our dynamic latent separation method, inspired by atomic physics, relies on the jointly learned structures of each data sample, which also reveal the importance of each sub-component for distinguishing data samples. This approach, atom modeling, requires no supervision of the latent space and allows us to learn extra partially interpretable representations besides the original goal of a model. We empirically demonstrate that the algorithm also enhances the performance of small to larger-scale models in various classification and generation problems.
Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem
Venue: arXiv cs.AI 2024
Year: 2024

The 0-1 Multidimensional Knapsack Problem (MKP) is a classical NP-hard combinatorial optimization problem with many engineering applications. In this paper, we propose a novel algorithm combining evolutionary computation with the exact algorithm to solve the 0-1 MKP. It maintains a set of solutions and utilizes the information from the population to extract good partial assignments. To find high-quality solutions, an exact algorithm is applied to explore the promising search space specified by the good partial assignments. The new solutions are used to update the population. Thus, the good partial assignments evolve towards a better direction with the improvement of the population. Extensive experimentation with commonly used benchmark sets shows that our algorithm outperforms the state-of-the-art heuristic algorithms, TPTEA and DQPSO, as well as the commercial solver CPlex. It finds better solutions than the existing algorithms and provides new lower bounds for 10 large and hard instances.
Motion Planning on Visual Manifolds
Venue: arXiv cs.RO 2024
Year: 2024

In this thesis, we propose an alternative characterization of the notion of Configuration Space, which we call Visual Configuration Space (VCS). This new characterization allows an embodied agent (e.g., a robot) to discover its own body structure and plan obstacle-free motions in its peripersonal space using a set of its own images in random poses. Here, we do not assume any knowledge of geometry of the agent, obstacles or the environment. We demonstrate the usefulness of VCS in (a) building and working with geometry-free models for robot motion planning, (b) explaining how a human baby might learn to reach objects in its peripersonal space through motor babbling, and (c) automatically generating natural looking head motion animations for digital avatars in virtual environments. This work is based on the formalism of manifolds and manifold learning using the agent's images and hence we call it Motion Planning on Visual Manifolds.
SpyHammer: Understanding and Exploiting RowHammer under Fine-Grained Temperature Variations
Venue: arXiv cs.CR 2024
Year: 2024

RowHammer is a DRAM vulnerability that can cause bit errors in a victim DRAM row solely by accessing its neighboring DRAM rows at a high-enough rate. Recent studies demonstrate that new DRAM devices are becoming increasingly vulnerable to RowHammer, and many works demonstrate system-level attacks for privilege escalation or information leakage. In this work, we perform the first rigorous fine-grained characterization and analysis of the correlation between RowHammer and temperature. We show that RowHammer is very sensitive to temperature variations, even if the variations are very small (e.g., $\pm 1$ °C). We leverage two key observations from our analysis to spy on DRAM temperature: 1) RowHammer-induced bit error rate consistently increases (or decreases) as the temperature increases, and 2) some DRAM cells that are vulnerable to RowHammer exhibit bit errors only at a particular temperature. Based on these observations, we propose a new RowHammer attack, called SpyHammer, that spies on the temperature of DRAM on critical systems such as industrial production lines, vehicles, and medical systems. SpyHammer is the first practical attack that can spy on DRAM temperature. Our evaluation in a controlled environment shows that SpyHammer can infer the temperature of the victim DRAM modules with an error of less than $\pm 2.5$ °C at the 90th percentile of all tested temperatures, for 12 real DRAM modules (120 DRAM chips) from four main manufacturers.
Accelerating the Delivery of Data Services over Uncertain Mobile Crowdsensing Networks
Venue: arXiv cs.DC 2024
Year: 2024

The challenge of exchanging and processing of big data over mobile crowdsensing (MCS) networks calls for designing seamless data service provisioning mechanisms to enable utilization of resources of mobile devices/users for crowdsensing tasks. Although conventional onsite spot trading of resources based on real-time network conditions can facilitate data sharing, it often suffers from prohibitively long service provisioning delays and unavoidable trading failures due to requiring timely analysis of dynamic network environment. These limitations motivate us to investigate an integrated forward and spot trading mechanism (iFAST), which entails a novel hybrid data trading protocol with time efficiency, over uncertain MCS ecosystems. In iFAST, the sellers (i.e., mobile devices who can contribute data) can provide long-term or temporary sensing services to the buyers (i.e., sensing tasks). Specifically, it enables signing long-term contracts in advance of future transactions through a forward trading mode, via analyzing historical statistics of the network/market, for which the notion of overbooking is introduced and promoted. iFAST further encourages the buyers with unsatisfying service quality to recruit temporary sellers through a spot trading mode, considering the current network/market conditions. We analyze the fundamental blocks of iFAST and provide a case study to demonstrate its performance. Inspirations for future research directions of next-generation sensing and communication are summarized.
Human-Aware Physical Human-Robot Collaborative Transportation and Manipulation with Multiple Aerial Robots
Venue: arXiv cs.RO 2024
Year: 2024

Human-robot interaction will play an essential role in various industries and daily tasks, enabling robots to effectively collaborate with humans and reduce their physical workload. Most of the existing approaches for physical human-robot interaction focus on collaboration between a human and a single ground or aerial robot. In recent years, very little progress has been made in this research area when considering multiple aerial robots, which offer increased versatility and mobility. This paper proposes a novel approach for physical human-robot collaborative transportation and manipulation of a cable-suspended payload with multiple aerial robots. The proposed method enables smooth and intuitive interaction between the transported objects and a human worker. In the same time, we consider distance constraints during the operations by exploiting the internal redundancy of the multi-robot transportation system. The key elements of our approach are (a) a collaborative payload external wrench estimator that does not rely on any force sensor; (b) a 6D admittance controller for human-aerial-robot collaborative transportation and manipulation; (c) a human-aware force distribution that exploits the internal system redundancy to guarantee the execution of additional tasks such inter-human-robot separation without affecting the payload trajectory tracking or quality of interaction. We validate the approach through extensive simulation and real-world experiments. These include scenarios where the robot team assists the human in transporting and manipulating a load, or where the human helps the robot team navigate the environment. We experimentally demonstrate for the first time, to the best of our knowledge, that our approach enables a quadrotor team to physically collaborate with a human in manipulating a payload in all 6 DoF in collaborative human-robot transportation and manipulation tasks.
Graph Neural Network Surrogate for Seismic Reliability Analysis of Highway Bridge Systems
Venue: arXiv cs.LG 2024
Year: 2024

Rapid reliability assessment of transportation networks can enhance preparedness, risk mitigation, and response management procedures related to these systems. Network reliability analysis commonly considers network-level performance and does not consider the more detailed node-level responses due to computational cost. In this paper, we propose a rapid seismic reliability assessment approach for bridge networks based on graph neural networks, where node-level connectivities, between points of interest and other nodes, are evaluated under probabilistic seismic scenarios. Via numerical experiments on transportation systems in California, we demonstrate the accuracy, computational efficiency, and robustness of the proposed approach compared to the Monte Carlo approach.
ScionFL: Efficient and Robust Secure Quantized Aggregation
Venue: arXiv cs.CR 2024
Year: 2024

Secure aggregation is commonly used in federated learning (FL) to alleviate privacy concerns related to the central aggregator seeing all parameter updates in the clear. Unfortunately, most existing secure aggregation schemes ignore two critical orthogonal research directions that aim to (i) significantly reduce client-server communication and (ii) mitigate the impact of malicious clients. However, both of these additional properties are essential to facilitate cross-device FL with thousands or even millions of (mobile) participants. In this paper, we unite both research directions by introducing ScionFL, the first secure aggregation framework for FL that operates efficiently on quantized inputs and simultaneously provides robustness against malicious clients. Our framework leverages (novel) multi-party computation (MPC) techniques and supports multiple linear (1-bit) quantization schemes, including ones that utilize the randomized Hadamard transform and Kashin's representation. Our theoretical results are supported by extensive evaluations. We show that with no overhead for clients and moderate overhead for the server compared to transferring and processing quantized updates in plaintext, we obtain comparable accuracy for standard FL benchmarks. Moreover, we demonstrate the robustness of our framework against state-of-the-art poisoning attacks.