OpenRaiser/Intern-Atlas huggingface dataset:
Universal Transceivers: Opportunities and Future Directions for the Internet of Everything (IoE)
Venue: arXiv cs.NI 2021
Year: 2021

The Internet of Everything (IoE) is a recently introduced information and communication technology (ICT) framework promising for extending the human connectivity to the entire universe, which itself can be regarded as a natural IoE, an interconnected network of everything we perceive. The countless number of opportunities that can be enabled by IoE through a blend of heterogeneous ICT technologies across different scales and environments and a seamless interface with the natural IoE impose several fundamental challenges, such as interoperability, ubiquitous connectivity, energy efficiency, and miniaturization. The key to address these challenges is to advance our communication technology to match the multi-scale, multi-modal, and dynamic features of the natural IoE. To this end, we introduce a new communication device concept, namely the universal IoE transceiver, that encompasses transceiver architectures that are characterized by multi-modality in communication (with modalities such as molecular, RF/THz, optical and acoustic) and in energy harvesting (with modalities such as mechanical, solar, biochemical), modularity, tunability, and scalability. Focusing on these fundamental traits, we provide an overview of the opportunities that can be opened up by micro/nanoscale universal transceiver architectures towards realizing the IoE applications. We also discuss the most pressing challenges in implementing such transceivers and briefly review the open research directions. Our discussion is particularly focused on the opportunities and challenges pertaining to the IoE physical layer, which can enable the efficient and effective design of higher-level techniques. We believe that such universal transceivers can pave the way for seamless connection and communication with the universe at a deeper level and pioneer the construction of the forthcoming IoE landscape.
Shapley-Based Core-Selecting Payment Rules
Venue: arXiv cs.GT 2021
Year: 2021

In this research note, we lay some groundwork for analyzing the manipulability of core-selecting payment rules in combinatorial auctions. In particular, we focus on payment rules based on the bidders' Shapley values. We define a sensitivity metric, and provide analytical results for this metric in LLG, for six different payment vectors used as reference points for minimum-revenue core-selecting payment rules. We furthermore show how this sensitivity affects the derivative of the resulting payment rules.
Solving the subset sum problem with a nonideal biological computer
Venue: arXiv cs.ET 2021
Year: 2021

We consider the solution of the subset sum problem based on a parallel computer consisting of self-propelled biological agents moving in a nanostructured network that encodes the NP-complete task in its geometry. We develop an approximate analytical method to analyze the effects of small errors in the nonideal junctions composing the computing network by using a Gaussian confidence interval approximation of the multinomial distribution. We concretely evaluate the probability distribution for error-induced paths and determine the minimal number of agents required to obtain a proper solution. We finally validate our theoretical results with exact numerical simulations of the subset sum problem for different set sizes and error probabilities.
Model Checking C++ Programs
Venue: arXiv cs.SE 2021
Year: 2021

In the last three decades, memory safety issues in system programming languages such as C or C++ have been one of the significant sources of security vulnerabilities. However, there exist only a few attempts with limited success to cope with the complexity of C++ program verification. Here we describe and evaluate a novel verification approach based on bounded model checking (BMC) and satisfiability modulo theories (SMT) to verify C++ programs formally. Our verification approach analyzes bounded C++ programs by encoding into SMT various sophisticated features that the C++ programming language offers, such as templates, inheritance, polymorphism, exception handling, and the Standard C++ Libraries. We formalize these features within our formal verification framework using a decidable fragment of first-order logic and then show how state-of-the-art SMT solvers can efficiently handle that. We implemented our verification approach on top of ESBMC. We compare ESBMC to LLBMC and DIVINE, which are state-of-the-art verifiers to check C++ programs directly from the LLVM bitcode. Experimental results show that ESBMC can handle a wide range of C++ programs, presenting a higher number of correct verification results. At the same time, it reduces the verification time if compared to LLBMC and DIVINE tools. Additionally, ESBMC has been applied to a commercial C++ application in the telecommunication domain and successfully detected arithmetic overflow errors, potentially leading to security vulnerabilities.
Live Synthesis
Venue: arXiv cs.LO 2021
Year: 2021

Synthesis automatically constructs an implementation that satisfies a given logical specification. In this paper, we study the live synthesis problem, where the synthesized implementation replaces an already running system. In addition to satisfying its own specification, the synthesized implementation must guarantee a sound transition from the previous implementation. This version of the synthesis problem is highly relevant in always-on applications, where updates happen while the system is running. To specify the correct handover between the old and new implementation, we introduce an extension of linear-time temporal logic (LTL) called LiveLTL. A LiveLTL specification defines separate requirements on the two implementations and ensures that the new implementation satisfies, in addition to its own requirements, any obligations left unfinished by the old implementation. For specifications in LiveLTL, we show that the live synthesis problem can be solved within the same complexity bound as standard reactive synthesis, i.e., in 2EXPTIME. Our experiments show the necessity of live synthesis for LiveLTL specifications created from benchmarks of SYNTCOMP and robot control.
CHISEL: Compression-Aware High-Accuracy Embedded Indoor Localization with Deep Learning
Venue: arXiv cs.LG 2021
Year: 2021

GPS technology has revolutionized the way we localize and navigate outdoors. However, the poor reception of GPS signals in buildings makes it unsuitable for indoor localization. WiFi fingerprinting-based indoor localization is one of the most promising ways to meet this demand. Unfortunately, most work in the domain fails to resolve challenges associated with deployability on resource-limited embedded devices. In this work, we propose a compression-aware and high-accuracy deep learning framework called CHISEL that outperforms the best-known works in the area while maintaining localization robustness on embedded devices.
A Systems Theory of Transfer Learning
Venue: arXiv cs.LG 2021
Year: 2021

Existing frameworks for transfer learning are incomplete from a systems theoretic perspective. They place emphasis on notions of domain and task, and neglect notions of structure and behavior. In doing so, they limit the extent to which formalism can be carried through into the elaboration of their frameworks. Herein, we use Mesarovician systems theory to define transfer learning as a relation on sets and subsequently characterize the general nature of transfer learning as a mathematical construct. We interpret existing frameworks in terms of ours and go beyond existing frameworks to define notions of transferability, transfer roughness, and transfer distance. Importantly, despite its formalism, our framework avoids the detailed mathematics of learning theory or machine learning solution methods without excluding their consideration. As such, we provide a formal, general systems framework for modeling transfer learning that offers a rigorous foundation for system design and analysis.
HandVoxNet++: 3D Hand Shape and Pose Estimation using Voxel-Based Neural Networks
Venue: arXiv cs.CV 2021
Year: 2021

3D hand shape and pose estimation from a single depth map is a new and challenging computer vision problem with many applications. Existing methods addressing it directly regress hand meshes via 2D convolutional neural networks, which leads to artefacts due to perspective distortions in the images. To address the limitations of the existing methods, we develop HandVoxNet++, i.e., a voxel-based deep network with 3D and graph convolutions trained in a fully supervised manner. The input to our network is a 3D voxelized-depth-map-based on the truncated signed distance function (TSDF). HandVoxNet++ relies on two hand shape representations. The first one is the 3D voxelized grid of hand shape, which does not preserve the mesh topology and which is the most accurate representation. The second representation is the hand surface that preserves the mesh topology. We combine the advantages of both representations by aligning the hand surface to the voxelized hand shape either with a new neural Graph-Convolutions-based Mesh Registration (GCN-MeshReg) or classical segment-wise Non-Rigid Gravitational Approach (NRGA++) which does not rely on training data. In extensive evaluations on three public benchmarks, i.e., SynHand5M, depth-based HANDS19 challenge and HO-3D, the proposed HandVoxNet++ achieves state-of-the-art performance. In this journal extension of our previous approach presented at CVPR 2020, we gain 41.09% and 13.7% higher shape alignment accuracy on SynHand5M and HANDS19 datasets, respectively. Our method is ranked first on the HANDS19 challenge dataset (Task 1: Depth-Based 3D Hand Pose Estimation) at the moment of the submission of our results to the portal in August 2020.
Data Uncertainty Guided Noise-aware Preprocessing Of Fingerprints
Venue: arXiv cs.CV 2021
Year: 2021

The effectiveness of fingerprint-based authentication systems on good quality fingerprints is established long back. However, the performance of standard fingerprint matching systems on noisy and poor quality fingerprints is far from satisfactory. Towards this, we propose a data uncertainty-based framework which enables the state-of-the-art fingerprint preprocessing models to quantify noise present in the input image and identify fingerprint regions with background noise and poor ridge clarity. Quantification of noise helps the model two folds: firstly, it makes the objective function adaptive to the noise in a particular input fingerprint and consequently, helps to achieve robust performance on noisy and distorted fingerprint regions. Secondly, it provides a noise variance map which indicates noisy pixels in the input fingerprint image. The predicted noise variance map enables the end-users to understand erroneous predictions due to noise present in the input image. Extensive experimental evaluation on 13 publicly available fingerprint databases, across different architectural choices and two fingerprint processing tasks demonstrate effectiveness of the proposed framework.
Designing Machine Learning Pipeline Toolkit for AutoML Surrogate Modeling Optimization
Venue: arXiv cs.LG 2021
Year: 2021

The pipeline optimization problem in machine learning requires simultaneous optimization of pipeline structures and parameter adaptation of their elements. Having an elegant way to express these structures can help lessen the complexity in the management and analysis of their performances together with the different choices of optimization strategies. With these issues in mind, we created the AutoMLPipeline (AMLP) toolkit which facilitates the creation and evaluation of complex machine learning pipeline structures using simple expressions. We use AMLP to find optimal pipeline signatures, datamine them, and use these datamined features to speed-up learning and prediction. We formulated a two-stage pipeline optimization with surrogate modeling in AMLP which outperforms other AutoML approaches with a 4-hour time budget in less than 5 minutes of AMLP computation time.
Row-sensing Templates: A Generic 3D Sensor-based Approach to Robot Localization with Respect to Orchard Row Centerlines
Venue: arXiv cs.RO 2021
Year: 2021

Accurate robot localization relative to orchard row centerlines is essential for autonomous guidance where satellite signals are often obstructed by foliage. Existing sensor-based approaches rely on various features extracted from images and point clouds. However, any selected features are not available consistently, because the visual and geometrical characteristics of orchard rows change drastically when tree types, growth stages, canopy management practices, seasons, and weather conditions change. In this work, we introduce a novel localization method that doesn't rely on features; instead, it relies on the concept of a row-sensing template, which is the expected observation of a 3D sensor traveling in an orchard row, when the sensor is anywhere on the centerline and perfectly aligned with it. First, the template is built using a few measurements, provided that the sensor's true pose with respect to the centerline is available. Then, during navigation, the best pose estimate (and its confidence) is estimated by maximizing the match between the template and the sensed point cloud using particle-filtering. The method can adapt to various orchards and conditions by re-building the template. Experiments were performed in a vineyard, and in an orchard in different seasons. Results showed that the lateral mean absolute error (MAE) was less than 3.6% of the row width, and the heading MAE was less than 1.72 degrees. Localization was robust, as errors didn't increase when less than 75% of measurement points were missing. The results indicate that template-based localization can provide a generic approach for accurate and robust localization in real-world orchards.
Fair Decision Rules for Binary Classification
Venue: arXiv cs.LG 2021
Year: 2021

In recent years, machine learning has begun automating decision making in fields as varied as college admissions, credit lending, and criminal sentencing. The socially sensitive nature of some of these applications together with increasing regulatory constraints has necessitated the need for algorithms that are both fair and interpretable. In this paper we consider the problem of building Boolean rule sets in disjunctive normal form (DNF), an interpretable model for binary classification, subject to fairness constraints. We formulate the problem as an integer program that maximizes classification accuracy with explicit constraints on two different measures of classification parity: equality of opportunity and equalized odds. Column generation framework, with a novel formulation, is used to efficiently search over exponentially many possible rules. When combined with faster heuristics, our method can deal with large data-sets. Compared to other fair and interpretable classifiers, our method is able to find rule sets that meet stricter notions of fairness with a modest trade-off in accuracy.
Pool of Experts: Realtime Querying Specialized Knowledge in Massive Neural Networks
Venue: arXiv cs.DB 2021
Year: 2021

In spite of the great success of deep learning technologies, training and delivery of a practically serviceable model is still a highly time-consuming process. Furthermore, a resulting model is usually too generic and heavyweight, and hence essentially goes through another expensive model compression phase to fit in a resource-limited device like embedded systems. Inspired by the fact that a machine learning task specifically requested by mobile users is often much simpler than it is supported by a massive generic model, this paper proposes a framework, called Pool of Experts (PoE), that instantly builds a lightweight and task-specific model without any training process. For a realtime model querying service, PoE first extracts a pool of primitive components, called experts, from a well-trained and sufficiently generic network by exploiting a novel conditional knowledge distillation method, and then performs our train-free knowledge consolidation to quickly combine necessary experts into a lightweight network for a target task. Thanks to this train-free property, in our thorough empirical study, PoE can build a fairly accurate yet compact model in a realtime manner, whereas it takes a few minutes per query for the other training methods to achieve a similar level of the accuracy.
CInC Flow: Characterizable Invertible 3x3 Convolution
Venue: arXiv cs.LG 2021
Year: 2021

Normalizing flows are an essential alternative to GANs for generative modelling, which can be optimized directly on the maximum likelihood of the dataset. They also allow computation of the exact latent vector corresponding to an image since they are composed of invertible transformations. However, the requirement of invertibility of the transformation prevents standard and expressive neural network models such as CNNs from being directly used. Emergent convolutions were proposed to construct an invertible 3$\times$3 CNN layer using a pair of masked CNN layers, making them inefficient. We study conditions such that 3$\times$3 CNNs are invertible, allowing them to construct expressive normalizing flows. We derive necessary and sufficient conditions on a padded CNN for it to be invertible. Our conditions for invertibility are simple, can easily be maintained during the training process. Since we require only a single CNN layer for every effective invertible CNN layer, our approach is more efficient than emerging convolutions. We also proposed a coupling method, Quad-coupling. We benchmark our approach and show similar performance results to emergent convolutions while improving the model's efficiency.
Impact of Channel Aging on Zero-Forcing Precoding in Cell-Free Massive MIMO Systems
Venue: arXiv cs.IT 2021
Year: 2021

In the context of cell-free massive multi-input multi-output (mMIMO), zero-forcing precoding (ZFP) requires the exchange of instantaneous channel state information and precoded data symbols via a fronthaul network. It causes considerable propagation and processing delays, which degrade performance. This letter analyzes the impact of channel aging on the performance of ZFP in cell-free mMIMO. The aging effects of not only user mobility but also phase noise are considered. Numerical results in terms of per-user spectral efficiency are illustrated.
Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we propose a novel pooling layer for graph neural networks based on maximizing the mutual information between the pooled graph and the input graph. Since the maximum mutual information is difficult to compute, we employ the Shannon capacity of a graph as an inductive bias to our pooling method. More precisely, we show that the input graph to the pooling layer can be viewed as a representation of a noisy communication channel. For such a channel, sending the symbols belonging to an independent set of the graph yields a reliable and error-free transmission of information. We show that reaching the maximum mutual information is equivalent to finding a maximum weight independent set of the graph where the weights convey entropy contents. Through this communication theoretic standpoint, we provide a distinct perspective for posing the problem of graph pooling as maximizing the information transmission rate across a noisy communication channel, implemented by a graph neural network. We evaluate our method, referred to as Maximum Entropy Weighted Independent Set Pooling (MEWISPool), on graph classification tasks and the combinatorial optimization problem of the maximum independent set. Empirical results demonstrate that our method achieves the state-of-the-art and competitive results on graph classification tasks and the maximum independent set problem in several benchmark datasets.
When Are Learned Models Better Than Hash Functions?
Venue: arXiv cs.DB 2021
Year: 2021

In this work, we aim to study when learned models are better hash functions, particular for hash-maps. We use lightweight piece-wise linear models to replace the hash functions as they have small inference times and are sufficiently general to capture complex distributions. We analyze the learned models in terms of: the model inference time and the number of collisions. Surprisingly, we found that learned models are not much slower to compute than hash functions if optimized correctly. However, it turns out that learned models can only reduce the number of collisions (i.e., the number of times different keys have the same hash value) if the model is able to over-fit to the data; otherwise, it can not be better than an ordinary hash function. Hence, how much better a learned model is in avoiding collisions highly depends on the data and the ability of the model to over-fit. To evaluate the effectiveness of learned models, we used them as hash functions in the bucket chaining and Cuckoo hash tables. For bucket chaining hash table, we found that learned models can achieve 30% smaller sizes and 10% lower probe latency. For Cuckoo hash tables, in some datasets, learned models can increase the ratio of keys stored in their primary locations by around 10%. In summary, we found that learned models can indeed outperform hash functions but only for certain data distributions and with a limited margin.
Byzantine-robust Federated Learning through Spatial-temporal Analysis of Local Model Updates
Venue: arXiv cs.LG 2021
Year: 2021

Federated Learning (FL) enables multiple distributed clients (e.g., mobile devices) to collaboratively train a centralized model while keeping the training data locally on the client. Compared to traditional centralized machine learning, FL offers many favorable features such as offloading operations which would usually be performed by a central server and reducing risks of serious privacy leakage. However, Byzantine clients that send incorrect or disruptive updates due to system failures or adversarial attacks may disturb the joint learning process, consequently degrading the performance of the resulting model. In this paper, we propose to mitigate these failures and attacks from a spatial-temporal perspective. Specifically, we use a clustering-based method to detect and exclude incorrect updates by leveraging their geometric properties in the parameter space. Moreover, to further handle malicious clients with time-varying behaviors, we propose to adaptively adjust the learning rate according to momentum-based update speculation. Extensive experiments on 4 public datasets demonstrate that our algorithm achieves enhanced robustness comparing to existing methods under both cross-silo and cross-device FL settings with faulty/malicious clients.
Erasures repair for decreasing monomial-Cartesian and augmented Reed-Muller codes of high rate
Venue: arXiv cs.IT 2021
Year: 2021

In this work, we present linear exact repair schemes for one or two erasures in decreasing monomial-Cartesian codes DM-CC, a family of codes which provides a framework for polar codes. In the case of two erasures, the positions of the erasures should satisfy a certain restriction. We present families of augmented Reed-Muller (ARM) and augmented Cartesian codes (ACar) which are families of evaluation codes obtained by strategically adding vectors to Reed-Muller and Cartesian codes, respectively. We develop repair schemes for one or two erasures for these families of augmented codes. Unlike the repair scheme for two erasures of DM-CC, the repair scheme for two erasures for the augmented codes has no restrictions on the positions of the erasures. When the dimension and base field are fixed, we give examples where ARM and ACar codes provide a lower bandwidth (resp., bitwidth) in comparison with Reed-Solomon (resp., Hermitian) codes. When the length and base field are fixed, we give examples where ACar codes provide a lower bandwidth in comparison with ARM. Finally, we analyze the asymptotic behavior when the augmented codes achieve the maximum rate.