OpenRaiser/Intern-Atlas huggingface dataset:
Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
Venue: arXiv cs.LG 2022
Year: 2022

Modern machine learning systems such as deep neural networks are often highly over-parameterized so that they can fit the noisy training data exactly, yet they can still achieve small test errors in practice. In this paper, we study this "benign overfitting" phenomenon of the maximum margin classifier for linear classification problems. Specifically, we consider data generated from sub-Gaussian mixtures, and provide a tight risk bound for the maximum margin linear classifier in the over-parameterized setting. Our results precisely characterize the condition under which benign overfitting can occur in linear classification problems, and improve on previous work. They also have direct implications for over-parameterized logistic regression.
Can crowdsourcing rescue the social marketplace of ideas?
Venue: arXiv cs.SI 2022
Year: 2022

Facebook and Twitter recently announced community-based review platforms to address misinformation. We provide an overview of the potential affordances of such community-based approaches to content moderation based on past research and preliminary analysis of Twitter's Birdwatch data. While our analysis generally supports a community-based approach to content moderation, it also warns against potential pitfalls, particularly when the implementation of the new infrastructure focuses on crowd-based "validation" rather than "collaboration." We call for multidisciplinary research utilizing methods from complex systems studies, behavioural sociology, and computational social science to advance the research on crowd-based content moderation.
Deep Learning for Rheumatoid Arthritis: Joint Detection and Damage Scoring in X-rays
Venue: arXiv cs.CV 2022
Year: 2022

Recent advancements in computer vision promise to automate medical image analysis. Rheumatoid arthritis is an autoimmune disease that would profit from computer-based diagnosis, as there are no direct markers known, and doctors have to rely on manual inspection of X-ray images. In this work, we present a multi-task deep learning model that simultaneously learns to localize joints on X-ray images and diagnose two kinds of joint damage: narrowing and erosion. Additionally, we propose a modification of label smoothing, which combines classification and regression cues into a single loss and achieves 5% relative error reduction compared to standard loss functions. Our final model obtained 4th place in joint space narrowing and 5th place in joint erosion in the global RA2 DREAM challenge.
Pebble transducers with unary output
Venue: arXiv cs.FL 2022
Year: 2022

Bojańczyk recently initiated an intensive study of deterministic pebble transducers, which are two-way automata that can drop marks (named "pebbles") on their input word, and produce an output word. They describe functions from words to words. Two natural restrictions of this definition have been investigated: marble transducers by Douéneau-Tabot et al., and comparison-free pebble transducers (that we rename here "blind transducers") by Nguyên et al. Here, we study the decidability of membership problems between the classes of functions computed by pebble, marble and blind transducers that produce a unary output. First, we show that pebble and marble transducers have the same expressive power when the outputs are unary (which is false over non-unary outputs). Then, we characterize 1-pebble transducers with unary output that describe a function computable by a blind transducer, and show that the membership problem is decidable. These results can be interpreted in terms of automated simplification of programs.
Extracting total Amb programs from proofs
Venue: arXiv cs.LO 2022
Year: 2022

We present a logical system CFP (Concurrent Fixed Point Logic) from whose proofs one can extract nondeterministic and concurrent programs that are provably total and correct with respect to the proven formula. CFP is an intuitionistic first-order logic with inductive and coinductive definitions extended by two propositional operators, A || B (restriction, a strengthening of the implication B -> A) and $\ddownarrow(A)$ (total concurrency). The target of the extraction is a lambda calculus with constructors and recursion extended by a constructor Amb (for McCarthy's amb) which is interpreted operationally as globally angelic choice. The correctness of extracted programs is proven via an intermediate domain-theoretic denotational semantics. We demonstrate the usefulness of our system by extracting a concurrent program that translates infinite Gray code into the signed digit representation. A noteworthy feature of our system is that the proof rules for restriction and concurrency involve variants of the classical law of excluded middle that would not be interpretable computationally without Amb.
Analyzing Semantics of Aggregate Answer Set Programming Using Approximation Fixpoint Theory
Venue: arXiv cs.AI 2022
Year: 2022

Aggregates provide a concise way to express complex knowledge. The problem of selecting an appropriate formalisation of aggregates for answer set programming (ASP) remains unsettled. This paper revisits it from the viewpoint of Approximation Fixpoint Theory (AFT). We introduce an AFT formalisation equivalent with the Gelfond-Lifschitz reduct for basic ASP programs and we extend it to handle aggregates. We analyse how existing approaches relate to our framework. We hope this work sheds some new light on the issue of a proper formalisation of aggregates. This paper is under consideration for acceptance in TPLP.
Divide-and-conquer based Large-Scale Spectral Clustering
Venue: arXiv cs.LG 2022
Year: 2022

Spectral clustering is one of the most popular clustering methods. However, how to balance the efficiency and effectiveness of the large-scale spectral clustering with limited computing resources has not been properly solved for a long time. In this paper, we propose a divide-and-conquer based large-scale spectral clustering method to strike a good balance between efficiency and effectiveness. In the proposed method, a divide-and-conquer based landmark selection algorithm and a novel approximate similarity matrix approach are designed to construct a sparse similarity matrix within low computational complexities. Then clustering results can be computed quickly through a bipartite graph partition process. The proposed method achieves a lower computational complexity than most existing large-scale spectral clustering methods. Experimental results on ten large-scale datasets have demonstrated the efficiency and effectiveness of the proposed method. The MATLAB code of the proposed method and experimental datasets are available at https://github.com/Li-Hongmin/MyPaperWithCode.
Adversarial Example Detection for DNN Models: A Review and Experimental Comparison
Venue: arXiv cs.CV 2022
Year: 2022

Deep learning (DL) has shown great success in many human-related tasks, which has led to its adoption in many computer vision based applications, such as security surveillance systems, autonomous vehicles and healthcare. Such safety-critical applications have to draw their path to success deployment once they have the capability to overcome safety-critical challenges. Among these challenges are the defense against or/and the detection of the adversarial examples (AEs). Adversaries can carefully craft small, often imperceptible, noise called perturbations to be added to the clean image to generate the AE. The aim of AE is to fool the DL model which makes it a potential risk for DL applications. Many test-time evasion attacks and countermeasures,i.e., defense or detection methods, are proposed in the literature. Moreover, few reviews and surveys were published and theoretically showed the taxonomy of the threats and the countermeasure methods with little focus in AE detection methods. In this paper, we focus on image classification task and attempt to provide a survey for detection methods of test-time evasion attacks on neural network classifiers. A detailed discussion for such methods is provided with experimental results for eight state-of-the-art detectors under different scenarios on four datasets. We also provide potential challenges and future perspectives for this research direction.
AirCode: A Robust Object Encoding Method
Venue: arXiv cs.RO 2022
Year: 2022

Object encoding and identification are crucial for many robotic tasks such as autonomous exploration and semantic relocalization. Existing works heavily rely on the tracking of detected objects but have difficulty recalling revisited objects precisely. In this paper, we propose a novel object encoding method, which is named as AirCode, based on a graph of key-points. To be robust to the number of key-points detected, we propose a feature sparse encoding and object dense encoding method to ensure that each key-point can only affect a small part of the object descriptors, leading it to be robust to viewpoint changes, scaling, occlusion, and even object deformation. In the experiments, we show that it achieves superior performance for object identification than the state-of-the-art algorithms and is able to provide reliable semantic relocalization. It is a plug-and-play module and we expect that it will play an important role in various applications.
GRNN: Generative Regression Neural Network -- A Data Leakage Attack for Federated Learning
Venue: arXiv cs.LG 2022
Year: 2022

Data privacy has become an increasingly important issue in Machine Learning (ML), where many approaches have been developed to tackle this challenge, e.g. cryptography (Homomorphic Encryption (HE), Differential Privacy (DP), etc.) and collaborative training (Secure Multi-Party Computation (MPC), Distributed Learning and Federated Learning (FL)). These techniques have a particular focus on data encryption or secure local computation. They transfer the intermediate information to the third party to compute the final result. Gradient exchanging is commonly considered to be a secure way of training a robust model collaboratively in Deep Learning (DL). However, recent researches have demonstrated that sensitive information can be recovered from the shared gradient. Generative Adversarial Network (GAN), in particular, has shown to be effective in recovering such information. However, GAN based techniques require additional information, such as class labels which are generally unavailable for privacy-preserved learning. In this paper, we show that, in the FL system, image-based privacy data can be easily recovered in full from the shared gradient only via our proposed Generative Regression Neural Network (GRNN). We formulate the attack to be a regression problem and optimize two branches of the generative model by minimizing the distance between gradients. We evaluate our method on several image classification tasks. The results illustrate that our proposed GRNN outperforms state-of-the-art methods with better stability, stronger robustness, and higher accuracy. It also has no convergence requirement to the global FL model. Moreover, we demonstrate information leakage using face re-identification. Some defense strategies are also discussed in this work.
A rigged model of the breast for preoperative surgical planning
Venue: arXiv cs.CE 2022
Year: 2022

In breast surgical practice, drawing is part of the preoperative planning procedure and is essential for a successful operation. In this study, we design a pipeline to assist surgeons with patient-specific breast surgical drawings. We use a deformable torso model containing the surgical patterns to match any breast surface scan. To be compatible with surgical timing, we build an articulated model through a skinning process coupled with shape deformers to enhance a fast registration process. On one hand, the scalable bones of the skinning account for pose and morphological variations of the patients. On the other hand, pre-designed artistic blendshapes create a linear space for guaranteeing anatomical variations. Then, we apply meaningful constraints to the model to find a trade-off between precision and speed. The experiments were conducted on 7 patients, in 2 different poses (prone and supine) with a breast size ranging from 36A and 42C (US/UK bra sizing). The acquisitions were obtained using the depth camera Structure Sensor, and the breast scans were acquired in less than 1 minute. The result is a registration method converging within a few seconds (3 maximum), reaching a Mean Absolute Error of 2.3 mm for mesh registration and 8.0 mm for breast anatomical landmarks. Compared to the existing literature, our model can be personalized and does not require any database. Finally, our registered model can be used to transfer surgical reference patterns onto any patient in any position.
Measuring diachronic sense change: new models and Monte Carlo methods for Bayesian inference
Venue: arXiv cs.CL 2022
Year: 2022

In a bag-of-words model, the senses of a word with multiple meanings, e.g. "bank" (used either in a river-bank or an institution sense), are represented as probability distributions over context words, and sense prevalence is represented as a probability distribution over senses. Both of these may change with time. Modelling and measuring this kind of sense change is challenging due to the typically high-dimensional parameter space and sparse datasets. A recently published corpus of ancient Greek texts contains expert-annotated sense labels for selected target words. Automatic sense-annotation for the word "kosmos" (meaning decoration, order or world) has been used as a test case in recent work with related generative models and Monte Carlo methods. We adapt an existing generative sense change model to develop a simpler model for the main effects of sense and time, and give MCMC methods for Bayesian inference on all these models that are more efficient than existing methods. We carry out automatic sense-annotation of snippets containing "kosmos" using our model, and measure the time-evolution of its three senses and their prevalence. As far as we are aware, ours is the first analysis of this data, within the class of generative models we consider, that quantifies uncertainty and returns credible sets for evolving sense prevalence in good agreement with those given by expert annotation.
A Subatomic Proof System for Decision Trees
Venue: arXiv cs.LO 2022
Year: 2022

We design a proof system for propositional classical logic that integrates two languages for Boolean functions: standard conjunction-disjunction-negation and binary decision trees. We give two reasons to do so. The first is proof-theoretical naturalness: the system consists of all and only the inference rules generated by the single, simple, linear scheme of the recently introduced subatomic logic. Thanks to this regularity, cuts are eliminated via a natural construction. The second reason is that the system generates efficient proofs. Indeed, we show that a certain class of tautologies due to Statman, which cannot have better than exponential cut-free proofs in the sequent calculus, have polynomial cut-free proofs in our system. We achieve this by using the same construction that we use for cut elimination. In summary, by expanding the language of propositional logic, we make its proof theory more regular and generate more proofs, some of which are very efficient. That design is made possible by considering atoms as superpositions of their truth values, which are connected by self-dual, non-commutative connectives. A proof can then be projected via each atom into two proofs, one for each truth value, without a need for cuts. Those projections are semantically natural and are at the heart of the constructions in this paper. To accommodate self-dual non-commutativity, we compose proofs in deep inference.
Counting vertices of integral polytopes defined by facets
Venue: arXiv cs.CC 2022
Year: 2022

We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0/1 polytopes and half-integral polytopes.
Fourier Plane-Wave Series Expansion for Holographic MIMO Communications
Venue: arXiv cs.IT 2022
Year: 2022

Imagine a MIMO communication system that fully exploits the propagation characteristics offered by an electromagnetic channel and ultimately approaches the limits imposed by wireless communications. This is the concept of Holographic MIMO communications. Accurate and tractable channel modeling is critical to understanding its full potential. Classical stochastic models used by communications theorists are derived under the electromagnetic far-field assumption, i.e. planar wave approximation over the array. However, such assumption breaks down when electromagnetically large (compared to the wavelength) antenna arrays are considered. In this paper, we start from the first principles of wave propagation and provide a Fourier plane-wave series expansion of the channel response, which fully captures the essence of electromagnetic propagation in arbitrary scattering and is also valid in the (radiative) near-field. The expansion is based on the Fourier spectral representation and has an intuitive physical interpretation, as it statistically describes the angular coupling between source and receiver. When discretized uniformly, it leads to a low-rank semi-unitarily equivalent approximation of the electromagnetic channel in the angular domain. The developed channel model is used to compute the ergodic capacity of a point-to-point Holographic MIMO system with different degrees of channel state information.
Enabling 3D Object Detection with a Low-Resolution LiDAR
Venue: arXiv cs.CV 2022
Year: 2022

Light Detection And Ranging (LiDAR) has been widely used in autonomous vehicles for perception and localization. However, the cost of a high-resolution LiDAR is still prohibitively expensive, while its low-resolution counterpart is much more affordable. Therefore, using low-resolution LiDAR for autonomous driving is an economically viable solution, but the point cloud sparsity makes it extremely challenging. In this paper, we propose a two-stage neural network framework that enables 3D object detection using a low-resolution LiDAR. Taking input from a low-resolution LiDAR point cloud and a monocular camera image, a depth completion network is employed to produce dense point cloud that is subsequently processed by a voxel-based network for 3D object detection. Evaluated with KITTI dataset for 3D object detection in Bird-Eye View (BEV), the experimental result shows that the proposed approach performs significantly better than directly applying the 16-line LiDAR point cloud for object detection. For both easy and moderate cases, our 3D vehicle detection results are close to those using 64-line high-resolution LiDARs.
Pervasive AI for IoT applications: A Survey on Resource-efficient Distributed Artificial Intelligence
Venue: arXiv cs.DC 2022
Year: 2022

Artificial intelligence (AI) has witnessed a substantial breakthrough in a variety of Internet of Things (IoT) applications and services, spanning from recommendation systems to robotics control and military surveillance. This is driven by the easier access to sensory data and the enormous scale of pervasive/ubiquitous devices that generate zettabytes (ZB) of real-time data streams. Designing accurate models using such data streams, to predict future insights and revolutionize the decision-taking process, inaugurates pervasive systems as a worthy paradigm for a better quality-of-life. The confluence of pervasive computing and artificial intelligence, Pervasive AI, expanded the role of ubiquitous IoT systems from mainly data collection to executing distributed computations with a promising alternative to centralized learning, presenting various challenges. In this context, a wise cooperation and resource scheduling should be envisaged among IoT devices (e.g., smartphones, smart vehicles) and infrastructure (e.g. edge nodes, and base stations) to avoid communication and computation overheads and ensure maximum performance. In this paper, we conduct a comprehensive survey of the recent techniques developed to overcome these resource challenges in pervasive AI systems. Specifically, we first present an overview of the pervasive computing, its architecture, and its intersection with artificial intelligence. We then review the background, applications and performance metrics of AI, particularly Deep Learning (DL) and online learning, running in a ubiquitous system. Next, we provide a deep literature review of communication-efficient techniques, from both algorithmic and system perspectives, of distributed inference, training and online learning tasks across the combination of IoT devices, edge devices and cloud servers. Finally, we discuss our future vision and research challenges.
Public Communication can Facilitate Low-Risk Coordination under Surveillance
Venue: arXiv cs.DC 2022
Year: 2022

Consider a sub-population of rebels that wish to initiate a revolution. In order to avoid initializing a failed revolution, rebels would first strive to estimate their relative "power", which is often correlated with their fraction in the population. However, and especially in non-democratic countries, rebels refrain from disclosing themselves. This poses a significant challenge for rebels: estimating their fraction in the population while minimizing the risk of being identified as rebels. This paper introduces a distributed computing framework aiming to study this question. Our main takeaway message is that the communication pattern has a crucial role in achieving such a task. Specifically, we show that relying on the inherent noise in the communication, "public communication", characterized by the fact that each message announced by an individual can be viewed by all its neighbors, allows rebels to estimate their fraction in the population while keeping a negligible risk of each rebel being identified as such. The suggested estimation protocol, inspired by historical events, is extremely simple and can be executed covertly even under extreme conditions of surveillance. Conversely, we show that under peer-to-peer communication, protocols of similar simplicity are either inefficient or non-covert.
Two-layer neural networks with values in a Banach space
Venue: arXiv cs.LG 2022
Year: 2022

We study two-layer neural networks whose domain and range are Banach spaces with separable preduals. In addition, we assume that the image space is equipped with a partial order, i.e. it is a Riesz space. As the nonlinearity we choose the lattice operation of taking the positive part; in case of $\mathbb R^d$-valued neural networks this corresponds to the ReLU activation function. We prove inverse and direct approximation theorems with Monte-Carlo rates for a certain class of functions, extending existing results for the finite-dimensional case. In the second part of the paper, we study, from the regularisation theory viewpoint, the problem of finding optimal representations of such functions via signed measures on a latent space from a finite number of noisy observations. We discuss regularity conditions known as source conditions and obtain convergence rates in a Bregman distance for the representing measure in the regime when both the noise level goes to zero and the number of samples goes to infinity at appropriate rates.