OpenRaiser/Intern-Atlas huggingface dataset:
Tight Inapproximability for Graphical Games
Venue: arXiv cs.GT 2022
Year: 2022

We provide a complete characterization for the computational complexity of finding approximate equilibria in two-action graphical games. We consider the two most well-studied approximation notions: $\varepsilon$-Nash equilibria ($\varepsilon$-NE) and $\varepsilon$-well-supported Nash equilibria ($\varepsilon$-WSNE), where $\varepsilon \in [0,1]$. We prove that computing an $\varepsilon$-NE is PPAD-complete for any constant $\varepsilon < 1/2$, while a very simple algorithm (namely, letting all players mix uniformly between their two actions) yields a $1/2$-NE. On the other hand, we show that computing an $\varepsilon$-WSNE is PPAD-complete for any constant $\varepsilon < 1$, while a $1$-WSNE is trivial to achieve, because any strategy profile is a $1$-WSNE. All of our lower bounds immediately also apply to graphical games with more than two actions per player.
Learning by Distilling Context
Venue: arXiv cs.CL 2022
Year: 2022

Language models significantly benefit from context tokens, such as prompts or scratchpads. They perform better when prompted with informative instructions, and they acquire new reasoning capabilities by generating a scratch-pad before predicting the final answers. However, they do not \textit{internalize} these performance gains, which disappear when the context tokens are gone. Our work proposes to apply context distillation so that a language model can improve itself by internalizing these gains. Concretely, given a synthetic unlabeled input for the target task, we condition the model on ``[instructions] + [task-input]'' to predict ``[scratch-pad] + [final answer]''; then we fine-tune the same model to predict its own ``[final answer]'' conditioned on the ``[task-input]'', without seeing the ``[instructions]'' or using the ``[scratch-pad]''. We show that context distillation is a general method to train language models, and it can effectively internalize 3 types of training signals. First, it can internalize abstract task instructions and explanations, so we can iteratively update the model parameters with new instructions and overwrite old ones. Second, it can internalize step-by-step reasoning for complex tasks (e.g., 8-digit addition), and such a newly acquired capability proves to be useful for other downstream tasks. Finally, it can internalize concrete training examples, and it outperforms directly learning with gradient descent by 9\% on the SPIDER Text-to-SQL dataset; furthermore, combining context distillation operations can internalize more training examples than the context window size allows.
RF-Transformer: A Unified Backscatter Radio Hardware Abstraction
Venue: arXiv cs.NI 2022
Year: 2022

This paper presents RF-Transformer, a unified backscatter radio hardware abstraction that allows a low-power IoT device to directly communicate with heterogeneous wireless receivers at the minimum power consumption. Unlike existing backscatter systems that are tailored to a specific wireless communication protocol, RF-Transformer provides a programmable interface to the micro-controller, allowing IoT devices to synthesize different types of protocol-compliant backscatter signals sharing radically different PHY-layer designs. To show the efficacy of our design, we implement a PCB prototype of RF-Transformer on 2.4 GHz ISM band and showcase its capability on generating standard ZigBee, Bluetooth, LoRa, and Wi-Fi 802.11b/g/n/ac packets. Our extensive field studies show that RF-Transformer achieves 23.8 Mbps, 247.1 Kbps, 986.5 Kbps, and 27.3 Kbps throughput when generating standard Wi-Fi, ZigBee, Bluetooth, and LoRa signals while consuming 7.6-74.2 less power than their active counterparts. Our ASIC simulation based on the 65-nm CMOS process shows that the power gain of RF-Transformer can further grow to 92-678. We further integrate RF-Transformer with pressure sensors and present a case study on detecting foot traffic density in hallways. Our 7-day case studies demonstrate RFTransformer can reliably transmit sensor data to a commodity gateway by synthesizing LoRa packets on top of Wi-Fi signals. Our experimental results also verify the compatibility of RF-Transformer with commodity receivers. Code and hardware schematics can be found at: https://github.com/LeFsCC/RF-Transformer.
Assortment Optimization Under the Multivariate MNL Model
Venue: arXiv cs.DS 2022
Year: 2022

We study an assortment optimization problem under a multi-purchase choice model in which customers choose a bundle of up to one product from each of two product categories. Different bundles have different utilities and the bundle price is the summation of the prices of products in it. For the uncapacitated setting where any set of products can be offered, we prove that this problem is strongly NP-hard. We show that an adjusted-revenue-ordered assortment provides a 1/2-approximation. Furthermore, we develop an approximation framework based on a linear programming relaxation of the problem and obtain a 0.74-approximation algorithm. This approximation ratio almost matches the integrality gap of the linear program, which is proven to be at most 0.75. For the capacitated setting, we prove that there does not exist a constant-factor approximation algorithm assuming the Exponential Time Hypothesis. The same hardness result holds for settings with general bundle prices or more than two categories. Finally, we conduct numerical experiments on randomly generated problem instances. The average approximation ratios of our algorithms are over 99%.
Traffic Sign Classification Using Deep and Quantum Neural Networks
Venue: arXiv cs.CV 2022
Year: 2022

Quantum Neural Networks (QNNs) are an emerging technology that can be used in many applications including computer vision. In this paper, we presented a traffic sign classification system implemented using a hybrid quantum-classical convolutional neural network. Experiments on the German Traffic Sign Recognition Benchmark dataset indicate that currently QNN do not outperform classical DCNN (Deep Convolutuional Neural Networks), yet still provide an accuracy of over 90% and are a definitely promising solution for advanced computer vision.
Application-Driven AI Paradigm for Human Action Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Human action recognition in computer vision has been widely studied in recent years. However, most algorithms consider only certain action specially with even high computational cost. That is not suitable for practical applications with multiple actions to be identified with low computational cost. To meet various application scenarios, this paper presents a unified human action recognition framework composed of two modules, i.e., multi-form human detection and corresponding action classification. Among them, an open-source dataset is constructed to train a multi-form human detection model that distinguishes a human being's whole body, upper body or part body, and the followed action classification model is adopted to recognize such action as falling, sleeping or on-duty, etc. Some experimental results show that the unified framework is effective for various application scenarios. It is expected to be a new application-driven AI paradigm for human action recognition.
Effective Early Stopping of Point Cloud Neural Networks
Venue: arXiv cs.CV 2022
Year: 2022

Early stopping techniques can be utilized to decrease the time cost, however currently the ultimate goal of early stopping techniques is closely related to the accuracy upgrade or the ability of the neural network to generalize better on unseen data without being large or complex in structure and not directly with its efficiency. Time efficiency is a critical factor in neural networks, especially when dealing with the segmentation of 3D point cloud data, not only because a neural network itself is computationally expensive, but also because point clouds are large and noisy data, making learning processes even more costly. In this paper, we propose a new early stopping technique based on fundamental mathematics aiming to upgrade the trade-off between the learning efficiency and accuracy of neural networks dealing with 3D point clouds. Our results show that by employing our early stopping technique in four distinct and highly utilized neural networks in segmenting 3D point clouds, the training time efficiency of the models is greatly improved, with efficiency gain values reaching up to 94\%, while the models achieving in just a few epochs approximately similar segmentation accuracy metric values like the ones that are obtained in the training of the neural networks in 200 epochs. Also, our proposal outperforms four conventional early stopping approaches in segmentation accuracy, implying a promising innovative early stopping technique in point cloud segmentation.
Did You Get What You Paid For? Rethinking Annotation Cost of Deep Learning Based Computer Aided Detection in Chest Radiographs
Venue: arXiv cs.CV 2022
Year: 2022

As deep networks require large amounts of accurately labeled training data, a strategy to collect sufficiently large and accurate annotations is as important as innovations in recognition methods. This is especially true for building Computer Aided Detection (CAD) systems for chest X-rays where domain expertise of radiologists is required to annotate the presence and location of abnormalities on X-ray images. However, there lacks concrete evidence that provides guidance on how much resource to allocate for data annotation such that the resulting CAD system reaches desired performance. Without this knowledge, practitioners often fall back to the strategy of collecting as much detail as possible on as much data as possible which is cost inefficient. In this work, we investigate how the cost of data annotation ultimately impacts the CAD model performance on classification and segmentation of chest abnormalities in frontal-view X-ray images. We define the cost of annotation with respect to the following three dimensions: quantity, quality and granularity of labels. Throughout this study, we isolate the impact of each dimension on the resulting CAD model performance on detecting 10 chest abnormalities in X-rays. On a large scale training data with over 120K X-ray images with gold-standard annotations, we find that cost-efficient annotations provide great value when collected in large amounts and lead to competitive performance when compared to models trained with only gold-standard annotations. We also find that combining large amounts of cost efficient annotations with only small amounts of expensive labels leads to competitive CAD models at a much lower cost.
Wi-attack: Cross-technology Impersonation Attack against iBeacon Services
Venue: arXiv cs.CR 2022
Year: 2022

iBeacon protocol is widely deployed to provide location-based services. By receiving its BLE advertisements, nearby devices can estimate the proximity to the iBeacon or calculate indoor positions. However, the open nature of these advertisements brings vulnerability to impersonation attacks. Such attacks could lead to spam, unreliable positioning, and even security breaches. In this paper, we propose Wi-attack, revealing the feasibility of using WiFi devices to conduct impersonation attacks on iBeacon services. Different from impersonation attacks using BLE compatible hardware, Wi-attack is not restricted by broadcasting intervals and is able to impersonate multiple iBeacons at the same time. Effective attacks can be launched on iBeacon services without modifications to WiFi hardware or firmware. To enable direct communication from WiFi to BLE, we use the digital emulation technique of cross technology communication. To enhance the packet reception along with its stability, we add redundant packets to eliminate cyclic prefix error entirely. The emulation provides an iBeacon packet reception rate up to 66.2%. We conduct attacks on three iBeacon services scenarios, point deployment, multilateration, and fingerprint-based localization. The evaluation results show that Wi-attack can bring an average distance error of more than 20 meters on fingerprint-based localization using only 3 APs.
A Learnable Optimization and Regularization Approach to Massive MIMO CSI Feedback
Venue: arXiv cs.IT 2022
Year: 2022

Channel state information (CSI) plays a critical role in achieving the potential benefits of massive multiple input multiple output (MIMO) systems. In frequency division duplex (FDD) massive MIMO systems, the base station (BS) relies on sustained and accurate CSI feedback from the users. However, due to the large number of antennas and users being served in massive MIMO systems, feedback overhead can become a bottleneck. In this paper, we propose a model-driven deep learning method for CSI feedback, called learnable optimization and regularization algorithm (LORA). Instead of using l1-norm as the regularization term, a learnable regularization module is introduced in LORA to automatically adapt to the characteristics of CSI. We unfold the conventional iterative shrinkage-thresholding algorithm (ISTA) to a neural network and learn both the optimization process and regularization term by end-toend training. We show that LORA improves the CSI feedback accuracy and speed. Besides, a novel learnable quantization method and the corresponding training scheme are proposed, and it is shown that LORA can operate successfully at different bit rates, providing flexibility in terms of the CSI feedback overhead. Various realistic scenarios are considered to demonstrate the effectiveness and robustness of LORA through numerical simulations.
Deploying a sharded MongoDB cluster as a queued job on a shared HPC architecture
Venue: arXiv cs.DC 2022
Year: 2022

Data stores are the foundation on which data science, in all its variations, is built upon. They provide a queryable interface to structured and unstructured data. Data science often starts by leveraging these query features to perform initial data preparation. However, most data stores are designed to run continuously to service disparate user requests with little or no downtime. Many HPC architectures process user requests by job queue scheduler and maintain a shard filesystem to store a jobs persistent data. We deploy a MongoDB sharded cluster with a run script that is designed to run a data science workload concurrently. As our test piece, we run data ingest and data queries to measure the performance with different configurations on the Blue Waters supper computer.
Crocs: Cross-Technology Clock Synchronization for WiFi and ZigBee
Venue: arXiv cs.NI 2022
Year: 2022

Clock synchronization is a key function in embedded wireless systems and networks. This issue is equally important and more challenging in IoT systems nowadays, which often include heterogeneous wireless devices that follow different wireless standards. Conventional solutions to this problem employ gateway-based indirect synchronization, which suffers low accuracy. This paper for the first time studies the problem of cross-technology clock synchronization. Our proposal called Crocs synchronizes WiFi and ZigBee devices by direct cross-technology communication. Crocs decouples the synchronization signal from the transmission of a timestamp. By incorporating a barker-code based beacon for time alignment and cross-technology transmission of timestamps, Crocs achieves robust and accurate synchronization among WiFi and ZigBee devices, with the synchronization error lower than 1 millisecond. We further make attempts to implement different cross-technology communication methods in Crocs and provide insight findings with regard to the achievable accuracy and expected overhead.
Reliable Face Morphing Attack Detection in On-The-Fly Border Control Scenario with Variation in Image Resolution and Capture Distance
Venue: arXiv cs.CV 2022
Year: 2022

Face Recognition Systems (FRS) are vulnerable to various attacks performed directly and indirectly. Among these attacks, face morphing attacks are highly potential in deceiving automatic FRS and human observers and indicate a severe security threat, especially in the border control scenario. This work presents a face morphing attack detection, especially in the On-The-Fly (OTF) Automatic Border Control (ABC) scenario. We present a novel Differential-MAD (D-MAD) algorithm based on the spherical interpolation and hierarchical fusion of deep features computed from six different pre-trained deep Convolutional Neural Networks (CNNs). Extensive experiments are carried out on the newly generated face morphing dataset (SCFace-Morph) based on the publicly available SCFace dataset by considering the real-life scenario of Automatic Border Control (ABC) gates. Experimental protocols are designed to benchmark the proposed and state-of-the-art (SOTA) D-MAD techniques for different camera resolutions and capture distances. Obtained results have indicated the superior performance of the proposed D-MAD method compared to the existing methods.
TT-NF: Tensor Train Neural Fields
Venue: arXiv cs.LG 2022
Year: 2022

Learning neural fields has been an active topic in deep learning research, focusing, among other issues, on finding more compact and easy-to-fit representations. In this paper, we introduce a novel low-rank representation termed Tensor Train Neural Fields (TT-NF) for learning neural fields on dense regular grids and efficient methods for sampling from them. Our representation is a TT parameterization of the neural field, trained with backpropagation to minimize a non-convex objective. We analyze the effect of low-rank compression on the downstream task quality metrics in two settings. First, we demonstrate the efficiency of our method in a sandbox task of tensor denoising, which admits comparison with SVD-based schemes designed to minimize reconstruction error. Furthermore, we apply the proposed approach to Neural Radiance Fields, where the low-rank structure of the field corresponding to the best quality can be discovered only through learning.
Spike-based local synaptic plasticity: A survey of computational models and neuromorphic circuits
Venue: arXiv cs.NE 2022
Year: 2022

Understanding how biological neural networks carry out learning using spike-based local plasticity mechanisms can lead to the development of powerful, energy-efficient, and adaptive neuromorphic processing systems. A large number of spike-based learning models have recently been proposed following different approaches. However, it is difficult to assess if and how they could be mapped onto neuromorphic hardware, and to compare their features and ease of implementation. To this end, in this survey, we provide a comprehensive overview of representative brain-inspired synaptic plasticity models and mixed-signal CMOS neuromorphic circuits within a unified framework. We review historical, bottom-up, and top-down approaches to modeling synaptic plasticity, and we identify computational primitives that can support low-latency and low-power hardware implementations of spike-based learning rules. We provide a common definition of a locality principle based on pre- and post-synaptic neuron information, which we propose as a fundamental requirement for physical implementations of synaptic plasticity. Based on this principle, we compare the properties of these models within the same framework, and describe the mixed-signal electronic circuits that implement their computing primitives, pointing out how these building blocks enable efficient on-chip and online learning in neuromorphic processing systems.
The More Secure, The Less Equally Usable: Gender and Ethnicity (Un)fairness of Deep Face Recognition along Security Thresholds
Venue: arXiv cs.CV 2022
Year: 2022

Face biometrics are playing a key role in making modern smart city applications more secure and usable. Commonly, the recognition threshold of a face recognition system is adjusted based on the degree of security for the considered use case. The likelihood of a match can be for instance decreased by setting a high threshold in case of a payment transaction verification. Prior work in face recognition has unfortunately showed that error rates are usually higher for certain demographic groups. These disparities have hence brought into question the fairness of systems empowered with face biometrics. In this paper, we investigate the extent to which disparities among demographic groups change under different security levels. Our analysis includes ten face recognition models, three security thresholds, and six demographic groups based on gender and ethnicity. Experiments show that the higher the security of the system is, the higher the disparities in usability among demographic groups are. Compelling unfairness issues hence exist and urge countermeasures in real-world high-stakes environments requiring severe security levels.
Explaining Hierarchical Features in Dynamic Point Cloud Processing
Venue: arXiv cs.MM 2022
Year: 2022

This paper aims at bringing some light and understanding to the field of deep learning for dynamic point cloud processing. Specifically, we focus on the hierarchical features learning aspect, with the ultimate goal of understanding which features are learned at the different stages of the process and what their meaning is. Last, we bring clarity on how hierarchical components of the network affect the learned features and their importance for a successful learning model. This study is conducted for point cloud prediction tasks, useful for predicting coding applications.
Neural Unbalanced Optimal Transport via Cycle-Consistent Semi-Couplings
Venue: arXiv cs.LG 2022
Year: 2022

Comparing unpaired samples of a distribution or population taken at different points in time is a fundamental task in many application domains where measuring populations is destructive and cannot be done repeatedly on the same sample, such as in single-cell biology. Optimal transport (OT) can solve this challenge by learning an optimal coupling of samples across distributions from unpaired data. However, the usual formulation of OT assumes conservation of mass, which is violated in unbalanced scenarios in which the population size changes (e.g., cell proliferation or death) between measurements. In this work, we introduce NubOT, a neural unbalanced OT formulation that relies on the formalism of semi-couplings to account for creation and destruction of mass. To estimate such semi-couplings and generalize out-of-sample, we derive an efficient parameterization based on neural optimal transport maps and propose a novel algorithmic scheme through a cycle-consistent training procedure. We apply our method to the challenging task of forecasting heterogeneous responses of multiple cancer cell lines to various drugs, where we observe that by accurately modeling cell proliferation and death, our method yields notable improvements over previous neural optimal transport methods.