OpenRaiser/Intern-Atlas huggingface dataset:
On Hard and Soft Decision Decoding of BCH Codes
Venue: arXiv cs.IT 2022
Year: 2022

The binary primitive BCH codes are cyclic and are constructed by choosing a subset of the cyclotomic cosets. Which subset is chosen determines the dimension, the minimum distance and the weight distribution of the BCH code. We construct possible BCH codes and determine their coderate, true minimum distance and the non-equivalent codes. A particular choice of cyclotomic cosets gives BCH codes which are, extended by one bit, equivalent to Reed-Muller codes, which is a known result from the sixties. We show that BCH codes have possibly better parameters than Reed-Muller codes, which are related in recent publications to polar codes. We study the decoding performance of these different BCH codes using information set decoding based on minimal weight codewords of the dual code. We show that information set decoding is possible even in case of a channel without reliability information since the decoding algorithm inherently calculates reliability information. Different BCH codes of the same rate are compared and different decoding performances and complexity are observed. Some examples of hard decision decoding of BCH codes have the same decoding performance as maximum likelihood decoding. All presented decoding methods can possibly be extended to include reliability information of a Gaussian channel for soft decision decoding. We show simulation results for soft decision list information set decoding and compare the performance to other methods.
Moufang Patterns and Geometry of Information
Venue: arXiv cs.IT 2022
Year: 2022

Technology of data collection and information transmission is based on various mathematical models of encoding. The words "Geometry of information" refer to such models, whereas the words "Moufang patterns" refer to various sophisticated symmetries appearing naturally in such models. In this paper we show that the symmetries of spaces of probability distributions, endowed with their canonical Riemannian metric of information geometry, have the structure of a commutative Moufang loop. We also show that the F-manifold structure on the space of probability distribution can be described in terms of differential 3-webs and Malcev algebras. We then present a new construction of (noncommutative) Moufang loops associated to almost-symplectic structures over finite fields, and use then to construct a new class of code loops with associated quantum error-correcting codes and networks of perfect tensors.
USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems
Venue: arXiv cs.LG 2022
Year: 2022

Real-world decision-making systems are often subject to uncertainties that have to be resolved through observational data. Therefore, we are frequently confronted with combinatorial optimization problems of which the objective function is unknown and thus has to be debunked using empirical evidence. In contrast to the common practice that relies on a learning-and-optimization strategy, we consider the regression between combinatorial spaces, aiming to infer high-quality optimization solutions from samples of input-solution pairs -- without the need to learn the objective function. Our main deliverable is a universal solver that is able to handle abstract undetermined stochastic combinatorial optimization problems. For learning foundations, we present learning-error analysis under the PAC-Bayesian framework using a new margin-based analysis. In empirical studies, we demonstrate our design using proof-of-concept experiments, and compare it with other methods that are potentially applicable. Overall, we obtain highly encouraging experimental results for several classic combinatorial problems on both synthetic and real-world datasets.
Globally Convergent Multilevel Training of Deep Residual Networks
Venue: arXiv cs.LG 2022
Year: 2022

We propose a globally convergent multilevel training method for deep residual networks (ResNets). The devised method can be seen as a novel variant of the recursive multilevel trust-region (RMTR) method, which operates in hybrid (stochastic-deterministic) settings by adaptively adjusting mini-batch sizes during the training. The multilevel hierarchy and the transfer operators are constructed by exploiting a dynamical system's viewpoint, which interprets forward propagation through the ResNet as a forward Euler discretization of an initial value problem. In contrast to traditional training approaches, our novel RMTR method also incorporates curvature information on all levels of the multilevel hierarchy by means of the limited-memory SR1 method. The overall performance and the convergence properties of our multilevel training method are numerically investigated using examples from the field of classification and regression.
A Comparative Study of Deep Learning Classification Methods on a Small Environmental Microorganism Image Dataset (EMDS-6): from Convolutional Neural Networks to Visual Transformers
Venue: arXiv cs.CV 2022
Year: 2022

In recent years, deep learning has made brilliant achievements in Environmental Microorganism (EM) image classification. However, image classification of small EM datasets has still not obtained good research results. Therefore, researchers need to spend a lot of time searching for models with good classification performance and suitable for the current equipment working environment. To provide reliable references for researchers, we conduct a series of comparison experiments on 21 deep learning models. The experiment includes direct classification, imbalanced training, and hyperparameter tuning experiments. During the experiments, we find complementarities among the 21 models, which is the basis for feature fusion related experiments. We also find that the data augmentation method of geometric deformation is difficult to improve the performance of VTs (ViT, DeiT, BotNet and T2T-ViT) series models. In terms of model performance, Xception has the best classification performance, the ViT model consumes the least time for training, and the ShuffleNet-V2 model has the least number of parameters.
A Topological Perspective on Causal Inference
Venue: arXiv cs.AI 2022
Year: 2022

This paper presents a topological learning-theoretic perspective on causal inference by introducing a series of topologies defined on general spaces of structural causal models (SCMs). As an illustration of the framework we prove a topological causal hierarchy theorem, showing that substantive assumption-free causal inference is possible only in a meager set of SCMs. Thanks to a known correspondence between open sets in the weak topology and statistically verifiable hypotheses, our results show that inductive assumptions sufficient to license valid causal inferences are statistically unverifiable in principle. Similar to no-free-lunch theorems for statistical inference, the present results clarify the inevitability of substantial assumptions for causal inference. An additional benefit of our topological approach is that it easily accommodates SCMs with infinitely many variables. We finally suggest that the framework may be helpful for the positive project of exploring and assessing alternative causal-inductive assumptions.
Perfectly Matched Sets in Graphs: Parameterized and Exact Computation
Venue: arXiv cs.DM 2022
Year: 2022

In an undirected graph $G=(V,E)$, we say $(A,B)$ is a pair of perfectly matched sets if $A$ and $B$ are disjoint subsets of $V$ and every vertex in $A$ (resp. $B$) has exactly one neighbor in $B$ (resp. $A$). The size of a pair of perfectly matched sets $(A,B)$ is $|A|=|B|$. The PERFECTLY MATCHED SETS problem is to decide whether a given graph $G$ has a pair of perfectly matched sets of size $k$. We show that PMS is $W[1]$-hard when parameterized by solution size $k$ even when restricted to split graphs and bipartite graphs. We observe that PMS is FPT when parameterized by clique-width, and give FPT algorithms with respect to the parameters distance to cluster, distance to co-cluster and treewidth. Complementing FPT results, we show that PMS does not admit a polynomial kernel when parameterized by vertex cover number unless $NP\subseteq coNP/poly$. We also provide an exact exponential algorithm running in time $O^*(1.966^n)$. Finally, considering graphs with structural assumptions, we show that PMS remains $NP$-hard on planar graphs.
Attribution of Predictive Uncertainties in Classification Models
Venue: arXiv cs.LG 2022
Year: 2022

Predictive uncertainties in classification tasks are often a consequence of model inadequacy or insufficient training data. In popular applications, such as image processing, we are often required to scrutinise these uncertainties by meaningfully attributing them to input features. This helps to improve interpretability assessments. However, there exist few effective frameworks for this purpose. Vanilla forms of popular methods for the provision of saliency masks, such as SHAP or integrated gradients, adapt poorly to target measures of uncertainty. Thus, state-of-the-art tools instead proceed by creating counterfactual or adversarial feature vectors, and assign attributions by direct comparison to original images. In this paper, we present a novel framework that combines path integrals, counterfactual explanations and generative models, in order to procure attributions that contain few observable artefacts or noise. We evidence that this outperforms existing alternatives through quantitative evaluations with popular benchmarking methods and data sets of varying complexity.
Causal Inference Struggles with Agency on Online Platforms
Venue: arXiv cs.LG 2022
Year: 2022

Online platforms regularly conduct randomized experiments to understand how changes to the platform causally affect various outcomes of interest. However, experimentation on online platforms has been criticized for having, among other issues, a lack of meaningful oversight and user consent. As platforms give users greater agency, it becomes possible to conduct observational studies in which users self-select into the treatment of interest as an alternative to experiments in which the platform controls whether the user receives treatment or not. In this paper, we conduct four large-scale within-study comparisons on Twitter aimed at assessing the effectiveness of observational studies derived from user self-selection on online platforms. In a within-study comparison, treatment effects from an observational study are assessed based on how effectively they replicate results from a randomized experiment with the same target population. We test the naive difference in group means estimator, exact matching, regression adjustment, and inverse probability of treatment weighting while controlling for plausible confounding variables. In all cases, all observational estimates perform poorly at recovering the ground-truth estimate from the analogous randomized experiments. In all cases except one, the observational estimates have the opposite sign of the randomized estimate. Our results suggest that observational studies derived from user self-selection are a poor alternative to randomized experimentation on online platforms. In discussing our results, we postulate a "Catch-22" that suggests that the success of causal inference in these settings may be at odds with the original motivations for providing users with greater agency.
User Association in Dense mmWave Networks as Restless Bandits
Venue: arXiv cs.IT 2022
Year: 2022

We study the problem of user association, i.e., determining which base station (BS) a user should associate with, in a dense millimeter wave (mmWave) network. In our system model, in each time slot, a user arrives with some probability in a region with a relatively small geographical area served by a dense mmWave network. Our goal is to devise an association policy under which, in each time slot in which a user arrives, it is assigned to exactly one BS so as to minimize the weighted average amount of time that users spend in the system. The above problem is a restless multi-armed bandit problem and is provably hard to solve. We prove that the problem is Whittle indexable, and based on this result, propose an association policy under which an arriving user is associated with the BS having the smallest Whittle index. Using simulations, we show that our proposed policy outperforms several user association policies proposed in prior work.
From Predictions to Decisions: The Importance of Joint Predictive Distributions
Venue: arXiv cs.LG 2022
Year: 2022

A fundamental challenge for any intelligent system is prediction: given some inputs, can you predict corresponding outcomes? Most work on supervised learning has focused on producing accurate marginal predictions for each input. However, we show that for a broad class of decision problems, accurate joint predictions are required to deliver good performance. In particular, we establish several results pertaining to combinatorial decision problems, sequential predictions, and multi-armed bandits to elucidate the essential role of joint predictive distributions. Our treatment of multi-armed bandits introduces an approximate Thompson sampling algorithm and analytic techniques that lead to a new kind of regret bound.
Revisiting Residue Codes for Modern Memories
Venue: arXiv cs.AR 2022
Year: 2022

Residue codes have been traditionally used for compute error correction rather than storage error correction. In this paper, we use these codes for storage error correction with surprising results. We find that adapting residue codes to modern memory systems offers a level of error correction comparable to traditional schemes such as Reed-Solomon with fewer bits of storage. For instance, our adaptation of residue code -- MUSE ECC -- can offer ChipKill protection using approximately 30% fewer bits. We show that the storage gains can be used to hold metadata needed for emerging security functionality such as memory tagging or to provide better detection capabilities against Rowhammer attacks. Our evaluation shows that memory tagging in a MUSE-enabled system shows a 12% reduction in memory bandwidth utilization while providing the same level of error correction as a traditional ECC baseline without a noticeable loss of performance. Thus, our work demonstrates a new, flexible primitive for co-designing reliability with security and performance.
Stein Variational Gradient Descent with Multiple Kernel
Venue: arXiv cs.LG 2022
Year: 2022

Stein variational gradient descent (SVGD) and its variants have shown promising successes in approximate inference for complex distributions. In practice, we notice that the kernel used in SVGD-based methods has a decisive effect on the empirical performance. Radial basis function (RBF) kernel with median heuristics is a common choice in previous approaches, but unfortunately this has proven to be sub-optimal. Inspired by the paradigm of Multiple Kernel Learning (MKL), our solution to this flaw is using a combination of multiple kernels to approximate the optimal kernel, rather than a single one which may limit the performance and flexibility. Specifically, we first extend Kernelized Stein Discrepancy (KSD) to its multiple kernels view called Multiple Kernelized Stein Discrepancy (MKSD) and then leverage MKSD to construct a general algorithm Multiple Kernel SVGD (MK-SVGD). Further, MKSVGD can automatically assign a weight to each kernel without any other parameters, which means that our method not only gets rid of optimal kernel dependence but also maintains computational efficiency. Experiments on various tasks and models demonstrate that our proposed method consistently matches or outperforms the competing methods.
Relay-Assisted Cooperative Federated Learning
Venue: arXiv cs.IT 2022
Year: 2022

Federated learning (FL) has recently emerged as a promising technology to enable artificial intelligence (AI) at the network edge, where distributed mobile devices collaboratively train a shared AI model under the coordination of an edge server. To significantly improve the communication efficiency of FL, over-the-air computation allows a large number of mobile devices to concurrently upload their local models by exploiting the superposition property of wireless multi-access channels. Due to wireless channel fading, the model aggregation error at the edge server is dominated by the weakest channel among all devices, causing severe straggler issues. In this paper, we propose a relay-assisted cooperative FL scheme to effectively address the straggler issue. In particular, we deploy multiple half-duplex relays to cooperatively assist the devices in uploading the local model updates to the edge server. The nature of the over-the-air computation poses system objectives and constraints that are distinct from those in traditional relay communication systems. Moreover, the strong coupling between the design variables renders the optimization of such a system challenging. To tackle the issue, we propose an alternating-optimization-based algorithm to optimize the transceiver and relay operation with low complexity. Then, we analyze the model aggregation error in a single-relay case and show that our relay-assisted scheme achieves a smaller error than the one without relays provided that the relay transmit power and the relay channel gains are sufficiently large. The analysis provides critical insights on relay deployment in the implementation of cooperative FL. Extensive numerical results show that our design achieves faster convergence compared with state-of-the-art schemes.
Responsible and Regulatory Conform Machine Learning for Medicine: A Survey of Challenges and Solutions
Venue: arXiv cs.LG 2022
Year: 2022

Machine learning is expected to fuel significant improvements in medical care. To ensure that fundamental principles such as beneficence, respect for human autonomy, prevention of harm, justice, privacy, and transparency are respected, medical machine learning systems must be developed responsibly. Many high-level declarations of ethical principles have been put forth for this purpose, but there is a severe lack of technical guidelines explicating the practical consequences for medical machine learning. Similarly, there is currently considerable uncertainty regarding the exact regulatory requirements placed upon medical machine learning systems. This survey provides an overview of the technical and procedural challenges involved in creating medical machine learning systems responsibly and in conformity with existing regulations, as well as possible solutions to address these challenges. First, a brief review of existing regulations affecting medical machine learning is provided, showing that properties such as safety, robustness, reliability, privacy, security, transparency, explainability, and nondiscrimination are all demanded already by existing law and regulations - albeit, in many cases, to an uncertain degree. Next, the key technical obstacles to achieving these desirable properties are discussed, as well as important techniques to overcome these obstacles in the medical context. We notice that distribution shift, spurious correlations, model underspecification, uncertainty quantification, and data scarcity represent severe challenges in the medical context. Promising solution approaches include the use of large and representative datasets and federated learning as a means to that end, the careful exploitation of domain knowledge, the use of inherently transparent models, comprehensive out-of-distribution model testing and verification, as well as algorithmic impact assessments.
Few Shots Are All You Need: A Progressive Few Shot Learning Approach for Low Resource Handwritten Text Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Handwritten text recognition in low resource scenarios, such as manuscripts with rare alphabets, is a challenging problem. The main difficulty comes from the very few annotated data and the limited linguistic information (e.g. dictionaries and language models). Thus, we propose a few-shot learning-based handwriting recognition approach that significantly reduces the human labor annotation process, requiring only few images of each alphabet symbol. The method consists in detecting all the symbols of a given alphabet in a textline image and decoding the obtained similarity scores to the final sequence of transcribed symbols. Our model is first pretrained on synthetic line images generated from any alphabet, even though different from the target domain. A second training step is then applied to diminish the gap between the source and target data. Since this retraining would require annotation of thousands of handwritten symbols together with their bounding boxes, we propose to avoid such human effort through an unsupervised progressive learning approach that automatically assigns pseudo-labels to the non-annotated data. The evaluation on different manuscript datasets show that our model can lead to competitive results with a significant reduction in human effort. The code will be publicly available in this repository: \url{https://github.com/dali92002/HTRbyMatching}
User-Centric Perspective in Random Access Cell-Free Aided by Spatial Separability
Venue: arXiv cs.IT 2022
Year: 2022

In a cell-free massive multiple-input multiple-output (CF-mMIMO) network, multiple access points (APs) actively cooperate to serve users' equipment (UEs). We consider how the random access (RA) problem can be addressed by such a network under the occurrence of pilot collisions. To find a solution, we embrace the user-centric perspective, which basically dictates that only a preferred set of APs needs to serve a UE. Due to the success of the strongest-user collision resolution (SUCRe) protocol for cellular (Ce) mMIMO, we extend it by considering the new setting. Besides, we establish that the user-centric perspective naturally equips a CF network with robust fundamentals for resolving collisions. We refer to this foundation as spatial separability, which enables multiple colliding UEs to access the network simultaneously. We then propose two novel RA protocols for CF-mMIMO: i) the baseline cell-free (BCF) that resolves collisions with the concept of spatial separability alone, and ii) the cell-free SUCRe (CF-SUCRe) that combines SUCRe and spatial separability principle to resolve collisions. We evaluate our proposed RA protocols against the Ce-SUCRe. Respectively, the BCF and CF-SUCRe can support 7x and 4x more UEs' access on average compared to the Ce-SUCRe with an average energy efficiency gain based on total power consumed (TPC) by the network per access attempt of 52x and 340x. Among our procedures, even with a higher overhead, the CF-SUCRe is superior to BCF regarding TPC per access attempt. This is because the combination of methods for collision resolution allows many APs to be disconnected from the RA process without sacrificing much the performance. Finally, our numerical results presented in this work can be reproduced using the code package available on: github.com/victorcroisfelt/cf-ra-spatial-separability.