OpenRaiser/Intern-Atlas huggingface dataset:
Deep Learning for Multi-User Proactive Beam Handoff: A 6G Application
Venue: arXiv cs.NI 2023
Year: 2023

This paper demonstrates the use of deep learning and time series data generated from user equipment (UE) beam measurements and positions collected by the base station (BS) to enable handoffs between beams that belong to the same or different BSs. We propose the use of long short-term memory (LSTM) recurrent neural networks with three different approaches and vary the number of lookbacks of the beam measurements to study the performance of the prediction used for the proactive beam handoff. Simulations show that while UE positions can improve the prediction performance, it is only up to a certain point. At a sufficiently large number of lookbacks, the UE positions become irrelevant to the prediction accuracy since the LSTMs are able to learn the optimal beam based on implicitly defined positions from the time-defined trajectories.
Convolutional Learning on Multigraphs
Venue: arXiv cs.LG 2023
Year: 2023

Graph convolutional learning has led to many exciting discoveries in diverse areas. However, in some applications, traditional graphs are insufficient to capture the structure and intricacies of the data. In such scenarios, multigraphs arise naturally as discrete structures in which complex dynamics can be embedded. In this paper, we develop convolutional information processing on multigraphs and introduce convolutional multigraph neural networks (MGNNs). To capture the complex dynamics of information diffusion within and across each of the multigraph's classes of edges, we formalize a convolutional signal processing model, defining the notions of signals, filtering, and frequency representations on multigraphs. Leveraging this model, we develop a multigraph learning architecture, including a sampling procedure to reduce computational complexity. The introduced architecture is applied towards optimal wireless resource allocation and a hate speech localization task, offering improved performance over traditional graph neural networks.
Differentially private partitioned variational inference
Venue: arXiv cs.LG 2023
Year: 2023

Learning a privacy-preserving model from sensitive data which are distributed across multiple devices is an increasingly important problem. The problem is often formulated in the federated learning context, with the aim of learning a single global model while keeping the data distributed. Moreover, Bayesian learning is a popular approach for modelling, since it naturally supports reliable uncertainty estimates. However, Bayesian learning is generally intractable even with centralised non-private data and so approximation techniques such as variational inference are a necessity. Variational inference has recently been extended to the non-private federated learning setting via the partitioned variational inference algorithm. For privacy protection, the current gold standard is called differential privacy. Differential privacy guarantees privacy in a strong, mathematically clearly defined sense. In this paper, we present differentially private partitioned variational inference, the first general framework for learning a variational approximation to a Bayesian posterior distribution in the federated learning setting while minimising the number of communication rounds and providing differential privacy guarantees for data subjects. We propose three alternative implementations in the general framework, one based on perturbing local optimisation runs done by individual parties, and two based on perturbing updates to the global model (one using a version of federated averaging, the second one adding virtual parties to the protocol), and compare their properties both theoretically and empirically.
Hebbian Deep Learning Without Feedback
Venue: arXiv cs.NE 2023
Year: 2023

Recent approximations to backpropagation (BP) have mitigated many of BP's computational inefficiencies and incompatibilities with biology, but important limitations still remain. Moreover, the approximations significantly decrease accuracy in benchmarks, suggesting that an entirely different approach may be more fruitful. Here, grounded on recent theory for Hebbian learning in soft winner-take-all networks, we present multilayer SoftHebb, i.e. an algorithm that trains deep neural networks, without any feedback, target, or error signals. As a result, it achieves efficiency by avoiding weight transport, non-local plasticity, time-locking of layer updates, iterative equilibria, and (self-) supervisory or other feedback signals -- which were necessary in other approaches. Its increased efficiency and biological compatibility do not trade off accuracy compared to state-of-the-art bio-plausible learning, but rather improve it. With up to five hidden layers and an added linear classifier, accuracies on MNIST, CIFAR-10, STL-10, and ImageNet, respectively reach 99.4%, 80.3%, 76.2%, and 27.3%. In conclusion, SoftHebb shows with a radically different approach from BP that Deep Learning over few layers may be plausible in the brain and increases the accuracy of bio-plausible machine learning. Code is available at https://github.com/NeuromorphicComputing/SoftHebb.
Two Bicomplex and One Multicomplex Least Mean Square algorithms
Venue: arXiv cs.LG 2023
Year: 2023

We study and introduce new gradient operators in the complex and bicomplex settings, inspired from the well-known Least Mean Square (LMS) algorithm invented in 1960 by Widrow and Hoff for Adaptive Linear Neuron (ADALINE). These gradient operators will be used to formulate new learning rules for the Bicomplex Least Mean Square (BLMS) algorithms and we will also formulate these learning rules will for the case of multicomplex LMS algorithms (MLMS). This approach extends both the classical real and complex LMS algorithms.
Moral Mimicry: Large Language Models Produce Moral Rationalizations Tailored to Political Identity
Venue: arXiv cs.CL 2023
Year: 2023

Large Language Models (LLMs) have demonstrated impressive capabilities in generating fluent text, as well as tendencies to reproduce undesirable social biases. This study investigates whether LLMs reproduce the moral biases associated with political groups in the United States, an instance of a broader capability herein termed moral mimicry. This hypothesis is explored in the GPT-3/3.5 and OPT families of Transformer-based LLMs. Using tools from Moral Foundations Theory, it is shown that these LLMs are indeed moral mimics. When prompted with a liberal or conservative political identity, the models generate text reflecting corresponding moral biases. This study also explores the relationship between moral mimicry and model size, and similarity between human and LLM moral word use.
A Deep Learning Approach to Analyzing Continuous-Time Systems
Venue: arXiv cs.LG 2023
Year: 2023

Scientists often use observational time series data to study complex natural processes, but regression analyses often assume simplistic dynamics. Recent advances in deep learning have yielded startling improvements to the performance of models of complex processes, but deep learning is generally not used for scientific analysis. Here we show that deep learning can be used to analyze complex processes, providing flexible function approximation while preserving interpretability. Our approach relaxes standard simplifying assumptions (e.g., linearity, stationarity, and homoscedasticity) that are implausible for many natural systems and may critically affect the interpretation of data. We evaluate our model on incremental human language processing, a domain with complex continuous dynamics. We demonstrate substantial improvements on behavioral and neuroimaging data, and we show that our model enables discovery of novel patterns in exploratory analyses, controls for diverse confounds in confirmatory analyses, and opens up research questions that are otherwise hard to study.
On Representing Linear Programs by Graph Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

Learning to optimize is a rapidly growing area that aims to solve optimization problems or improve existing optimization algorithms using machine learning (ML). In particular, the graph neural network (GNN) is considered a suitable ML model for optimization problems whose variables and constraints are permutation--invariant, for example, the linear program (LP). While the literature has reported encouraging numerical results, this paper establishes the theoretical foundation of applying GNNs to solving LPs. Given any size limit of LPs, we construct a GNN that maps different LPs to different outputs. We show that properly built GNNs can reliably predict feasibility, boundedness, and an optimal solution for each LP in a broad class. Our proofs are based upon the recently--discovered connections between the Weisfeiler--Lehman isomorphism test and the GNN. To validate our results, we train a simple GNN and present its accuracy in mapping LPs to their feasibilities and solutions.
Random graph matching at Otter's threshold via counting chandeliers
Venue: arXiv cs.DS 2023
Year: 2023

We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdős-Rényi graphs $\mathcal{G}(n,q)$ whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that $nq\to\infty$ and the edge correlation coefficient $ρ$ satisfies $ρ^2>α\approx 0.338$, where $α$ is Otter's tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is information-theoretically necessary. This is the first polynomial-time graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs. In comparison, previous methods either require $ρ=1-o(1)$ or are restricted to sparse graphs. The crux of the algorithm is a carefully curated family of rooted trees called chandeliers, which allows effective extraction of the graph correlation from the counts of the same tree while suppressing the undesirable correlation between those of different trees.
Matching Queues with Abandonments in Quantum Switches: Stability and Throughput Analysis
Venue: arXiv cs.PF 2023
Year: 2023

Inspired by quantum switches, we consider a discrete-time multi-way matching system with two classes of arrivals: requests for entangled pair of qubits between two nodes, and qubits from each node that can be used to serve the requests. An important feature of this model is that qubits decohere and so abandon over time. In contrast to classical server-based queueing models, the combination of queueing, server-less multi-way matching, and (potentially correlated) abandonments make the analysis a challenging problem. The primary focus of this paper is to study a simple system consisting of two types of requests and three types of qubits operating under a Max-Weight policy. In this setting, we characterize the stability region under the Max-Weight policy by adopting a two-time scale fluid limit to get a handle on the abandonments. In particular, we show that Max-Weight is throughput optimal and that it can achieve throughputs larger than the ones that can be achieved by non-idling policies when the requests are infinitely backlogged. Moreover, despite the use of the Max-Weight policy, we show that there can be a counter-intuitive behavior in the system: the longest requests queue can have a positive drift for some time even if the overall system is stable.
Generalized Parametric Contrastive Learning
Venue: arXiv cs.CV 2023
Year: 2023

In this paper, we propose the Generalized Parametric Contrastive Learning (GPaCo/PaCo) which works well on both imbalanced and balanced data. Based on theoretical analysis, we observe that supervised contrastive loss tends to bias high-frequency classes and thus increases the difficulty of imbalanced learning. We introduce a set of parametric class-wise learnable centers to rebalance from an optimization perspective. Further, we analyze our GPaCo/PaCo loss under a balanced setting. Our analysis demonstrates that GPaCo/PaCo can adaptively enhance the intensity of pushing samples of the same class close as more samples are pulled together with their corresponding centers and benefit hard example learning. Experiments on long-tailed benchmarks manifest the new state-of-the-art for long-tailed recognition. On full ImageNet, models from CNNs to vision transformers trained with GPaCo loss show better generalization performance and stronger robustness compared with MAE models. Moreover, GPaCo can be applied to the semantic segmentation task and obvious improvements are observed on the 4 most popular benchmarks. Our code is available at https://github.com/dvlab-research/Parametric-Contrastive-Learning.
The Interplay of AI and Digital Twin: Bridging the Gap between Data-Driven and Model-Driven Approaches
Venue: arXiv cs.AI 2023
Year: 2023

The evolution of network virtualization and native artificial intelligence (AI) paradigms have conceptualized the vision of future wireless networks as a comprehensive entity operating in whole over a digital platform, with smart interaction with the physical domain, paving the way for the blooming of the Digital Twin (DT) concept. The recent interest in the DT networks is fueled by the emergence of novel wireless technologies and use-cases, that exacerbate the level of complexity to orchestrate the network and to manage its resources. Driven by AI, the key principle of the DT is to create a virtual twin for the physical entities and network dynamics, where the virtual twin will be leveraged to generate synthetic data and offer an on-demand platform for AI model training. Despite the common understanding that AI is the seed for DT, we anticipate that the DT and AI will be enablers for each other, in a way that overcome their limitations and complement each other benefits. In this article, we dig into the fundamentals of DT, where we reveal the role of DT in unifying model-driven and data-driven approaches, and explore the opportunities offered by DT in order to achieve the optimistic vision of 6G networks. We further unfold the essential role of the theoretical underpinnings in unlocking further opportunities by AI, and hence, we unveil their pivotal impact on the realization of reliable, efficient, and low-latency DT.
Obstructions to faster diameter computation: Asteroidal sets
Venue: arXiv cs.DS 2023
Year: 2023

An extremity is a vertex such that the removal of its closed neighbourhood does not increase the number of connected components. Let $Ext_α$ be the class of all connected graphs whose quotient graph obtained from modular decomposition contains no more than $α$ pairwise nonadjacent extremities. Our main contributions are as follows. First, we prove that the diameter of every $m$-edge graph in $Ext_α$ can be computed in deterministic ${\cal O}(α^3 m^{3/2})$ time. We then improve the runtime to linear for all graphs with bounded clique-number. Furthermore, we can compute an additive $+1$-approximation of all vertex eccentricities in deterministic ${\cal O}(α^2 m)$ time. This is in sharp contrast with general $m$-edge graphs for which, under the Strong Exponential Time Hypothesis (SETH), one cannot compute the diameter in ${\cal O}(m^{2-ε})$ time for any $ε> 0$. As important special cases of our main result, we derive an ${\cal O}(m^{3/2})$-time algorithm for exact diameter computation within dominating pair graphs of diameter at least six, and an ${\cal O}(k^3m^{3/2})$-time algorithm for this problem on graphs of asteroidal number at most $k$. We end up presenting an improved algorithm for chordal graphs of bounded asteroidal number, and a partial extension of our results to the larger class of all graphs with a dominating target of bounded cardinality. Our time upper bounds in the paper are shown to be essentially optimal under plausible complexity assumptions.
MARLUI: Multi-Agent Reinforcement Learning for Adaptive UIs
Venue: arXiv cs.HC 2023
Year: 2023

Adaptive user interfaces (UIs) automatically change an interface to better support users' tasks. Recently, machine learning techniques have enabled the transition to more powerful and complex adaptive UIs. However, a core challenge for adaptive user interfaces is the reliance on high-quality user data that has to be collected offline for each task. We formulate UI adaptation as a multi-agent reinforcement learning problem to overcome this challenge. In our formulation, a user agent mimics a real user and learns to interact with a UI. Simultaneously, an interface agent learns UI adaptations to maximize the user agent's performance. The interface agent learns the task structure from the user agent's behavior and, based on that, can support the user agent in completing its task. Our method produces adaptation policies that are learned in simulation only and, therefore, does not need real user data. Our experiments show that learned policies generalize to real users and achieve on par performance with data-driven supervised learning baselines.
A Digital Twin Description Framework and its Mapping to Asset Administration Shell
Venue: arXiv cs.OH 2023
Year: 2023

The pace of reporting on Digital Twin (DT) projects continues to accelerate both in industry and academia. However, these experience reports often leave out essential characteristics of the DT, such as the scope of the system-under-study, the insights and actions enabled, and the time-scale of processing. A lack of these details could therefore hamper both understanding of these DTs and development of DT tools and techniques. Our previous work developed a DT description framework with fourteen characteristics as a checklist for experience report authors to better describe the capabilities of their DT projects. This report provides an extended example of reporting to highlight the utility of this description framework, focusing on the DT of an industrial drilling machine. Furthermore, we provide a mapping from our description framework to the Asset Administration Shell (AAS) which is an emerging standard for Industry 4.0 system integration. This mapping aids practitioners in understanding how our description framework relates to AAS, potentially aiding in description or implementation activities.
Developing A Visual-Interactive Interface for Electronic Health Record Labeling: An Explainable Machine Learning Approach
Venue: arXiv cs.LG 2023
Year: 2023

Labeling a large number of electronic health records is expensive and time consuming, and having a labeling assistant tool can significantly reduce medical experts' workload. Nevertheless, to gain the experts' trust, the tool must be able to explain the reasons behind its outputs. Motivated by this, we introduce Explainable Labeling Assistant (XLabel) a new visual-interactive tool for data labeling. At a high level, XLabel uses Explainable Boosting Machine (EBM) to classify the labels of each data point and visualizes heatmaps of EBM's explanations. As a case study, we use XLabel to help medical experts label electronic health records with four common non-communicable diseases (NCDs). Our experiments show that 1) XLabel helps reduce the number of labeling actions, 2) EBM as an explainable classifier is as accurate as other well-known machine learning models outperforms a rule-based model used by NCD experts, and 3) even when more than 40% of the records were intentionally mislabeled, EBM could recall the correct labels of more than 90% of these records.
Uniform Exact Reconstruction of Sparse Signals and Low-rank Matrices from Phase-Only Measurements
Venue: arXiv cs.IT 2023
Year: 2023

In phase-only compressive sensing (PO-CS), our goal is to recover low-complexity signals (e.g., sparse signals, low-rank matrices) from the phase of complex linear measurements. While perfect recovery of signal direction in PO-CS was observed quite early, the exact reconstruction guarantee for a fixed, real signal was recently done by Jacques and Feuillen [IEEE Trans. Inf. Theory, 67 (2021), pp. 4150-4161]. However, two questions remain open: the uniform recovery guarantee and exact recovery of complex signal. In this paper, we almost completely address these two open questions. We prove that, all complex sparse signals or low-rank matrices can be uniformly, exactly recovered from a near optimal number of complex Gaussian measurement phases. By recasting PO-CS as a linear compressive sensing problem, the exact recovery follows from restricted isometry property (RIP). Our approach to uniform recovery guarantee is based on covering arguments that involve a delicate control of the (original linear) measurements with overly small magnitude. To work with complex signal, a different sign-product embedding property and a careful rescaling of the sensing matrix are employed. In addition, we show an extension that the uniform recovery is stable under moderate bounded noise. We also propose to add Gaussian dither before capturing the phases to achieve full reconstruction with norm information. Experimental results are reported to corroborate and demonstrate our theoretical results.
Survey on Fairness Notions and Related Tensions
Venue: arXiv cs.CY 2023
Year: 2023

Automated decision systems are increasingly used to take consequential decisions in problems such as job hiring and loan granting with the hope of replacing subjective human decisions with objective machine learning (ML) algorithms. However, ML-based decision systems are prone to bias, which results in yet unfair decisions. Several notions of fairness have been defined in the literature to capture the different subtleties of this ethical and social concept (e.g., statistical parity, equal opportunity, etc.). Fairness requirements to be satisfied while learning models created several types of tensions among the different notions of fairness and other desirable properties such as privacy and classification accuracy. This paper surveys the commonly used fairness notions and discusses the tensions among them with privacy and accuracy. Different methods to address the fairness-accuracy trade-off (classified into four approaches, namely, pre-processing, in-processing, post-processing, and hybrid) are reviewed. The survey is consolidated with experimental analysis carried out on fairness benchmark datasets to illustrate the relationship between fairness measures and accuracy in real-world scenarios.
Quantum-Inspired Perfect Matching under Vertex-Color Constraints
Venue: arXiv cs.CC 2023
Year: 2023

We propose and study the graph-theoretical problem EXISTS-PMVC: the existence of perfect matching under vertex-color constraints on graphs with bi-colored edges. EXISTS-PMVC is of special interest because of its motivation from quantum-state identification and quantum-experiment design, as well as its rich expressiveness, i.e., EXISTS-PMVC naturally subsumes important constrained matching problems, such as exact perfect matching. We give complexity and algorithmic results for EXISTS-PMVC under two types of vertex color constraints: (1) decision-diagram constraints (EXISTS-PMVC-DD) and (2) symmetric constraints (EXISTS-PMVC-Sym). For EXISTS-PMVC-DD, we reveal its NP-hardness by a graph-gadget technique. We prove that EXISTS-PMVC-Sym with a bounded number of colors (EXISTS-PMVC-Sym-Bounded) is polynomially equivalent with Exact Perfect Matching (XPM), which implies that EXISTS-PMVC-Sym-Bounded is in RNC on general graphs and PTIME on planar graphs. Directly applying algorithms for XPM to solve EXISTS-PMVC-Sym-Bounded is, however, impractical. We propose algorithms that natively handle EXISTS-PMVC-Sym-Bounded with considerably better complexity. Our novel results for EXISTS-PMVC provide insights into both constrained matching and scalable quantum experiment design.