OpenRaiser/Intern-Atlas huggingface dataset:
Identifying a Training-Set Attack's Target Using Renormalized Influence Estimation
Venue: arXiv cs.LG 2022
Year: 2022

Targeted training-set attacks inject malicious instances into the training set to cause a trained model to mislabel one or more specific test instances. This work proposes the task of target identification, which determines whether a specific test instance is the target of a training-set attack. Target identification can be combined with adversarial-instance identification to find (and remove) the attack instances, mitigating the attack with minimal impact on other predictions. Rather than focusing on a single attack method or data modality, we build on influence estimation, which quantifies each training instance's contribution to a model's prediction. We show that existing influence estimators' poor practical performance often derives from their over-reliance on training instances and iterations with large losses. Our renormalized influence estimators fix this weakness; they far outperform the original estimators at identifying influential groups of training examples in both adversarial and non-adversarial settings, even finding up to 100% of adversarial training instances with no clean-data false positives. Target identification then simplifies to detecting test instances with anomalous influence values. We demonstrate our method's effectiveness on backdoor and poisoning attacks across various data domains, including text, vision, and speech, as well as against a gray-box, adaptive attacker that specifically optimizes the adversarial instances to evade our method. Our source code is available at https://github.com/ZaydH/target_identification.
Dissipative Hamiltonian Neural Networks: Learning Dissipative and Conservative Dynamics Separately
Venue: arXiv cs.LG 2022
Year: 2022

Understanding natural symmetries is key to making sense of our complex and ever-changing world. Recent work has shown that neural networks can learn such symmetries directly from data using Hamiltonian Neural Networks (HNNs). But HNNs struggle when trained on datasets where energy is not conserved. In this paper, we ask whether it is possible to identify and decompose conservative and dissipative dynamics simultaneously. We propose Dissipative Hamiltonian Neural Networks (D-HNNs), which parameterize both a Hamiltonian and a Rayleigh dissipation function. Taken together, they represent an implicit Helmholtz decomposition which can separate dissipative effects such as friction from symmetries such as conservation of energy. We train our model to decompose a damped mass-spring system into its friction and inertial terms and then show that this decomposition can be used to predict dynamics for unseen friction coefficients. Then we apply our model to real world data including a large, noisy ocean current dataset where decomposing the velocity field yields useful scientific insights.
Tree Representation, Growth Rate of Blockchain and Reward Allocation in Ethereum with Multiple Mining Pools
Venue: arXiv cs.CR 2022
Year: 2022

It is interesting but difficult and challenging to study Ethereum with multiple mining pools. One of the main difficulties comes from not only how to represent such a general tree with multiple block branches (or sub-chains) related to the multiple mining pools, but also how to analyze a multi-dimensional stochastic system due to the mining competition among the multiple mining pools. In this paper, we first set up a mathematical representation for the tree with multiple block branches. Then we provide a block classification of Ethereum: Regular blocks (in the main chain), orphan blocks, uncle blocks, stale blocks, and nephew blocks, and give some key probabilities of generating the different types of blocks by applying the law of large numbers. Based on this, we further discuss the growth rate of blockchain, and the reward allocation among the multiple mining pools through applying the renewal reward theorem. Finally, we use some simulation experiments to verify our theoretical results, and show that the approximate computation approaches developed, such as the key probabilities, the long-term growth rate of blockchain, and the long-term reward allocation (rate) among the multiple mining pools, can have a faster convergence. Therefore, we provide a powerful tool for observing and understanding the influence of the selfish mining attacks on the performance of Ethereum with multiple mining pools. We believe that the methodology and results developed in this paper will shed light on the study of Ethereum with multiple mining pools, such that a series of promising research can be inspired potentially.
Stochastic Coded Federated Learning with Convergence and Privacy Guarantees
Venue: arXiv cs.LG 2022
Year: 2022

Federated learning (FL) has attracted much attention as a privacy-preserving distributed machine learning framework, where many clients collaboratively train a machine learning model by exchanging model updates with a parameter server instead of sharing their raw data. Nevertheless, FL training suffers from slow convergence and unstable performance due to stragglers caused by the heterogeneous computational resources of clients and fluctuating communication rates. This paper proposes a coded FL framework to mitigate the straggler issue, namely stochastic coded federated learning (SCFL). In this framework, each client generates a privacy-preserving coded dataset by adding additive noise to the random linear combination of its local data. The server collects the coded datasets from all the clients to construct a composite dataset, which helps to compensate for the straggling effect. In the training process, the server as well as clients perform mini-batch stochastic gradient descent (SGD), and the server adds a make-up term in model aggregation to obtain unbiased gradient estimates. We characterize the privacy guarantee by the mutual information differential privacy (MI-DP) and analyze the convergence performance in federated learning. Besides, we demonstrate a privacy-performance tradeoff of the proposed SCFL method by analyzing the influence of the privacy constraint on the convergence rate. Finally, numerical experiments corroborate our analysis and show the benefits of SCFL in achieving fast convergence while preserving data privacy.
RecShard: Statistical Feature-Based Memory Optimization for Industry-Scale Neural Recommendation
Venue: arXiv cs.LG 2022
Year: 2022

We propose RecShard, a fine-grained embedding table (EMB) partitioning and placement technique for deep learning recommendation models (DLRMs). RecShard is designed based on two key observations. First, not all EMBs are equal, nor all rows within an EMB are equal in terms of access patterns. EMBs exhibit distinct memory characteristics, providing performance optimization opportunities for intelligent EMB partitioning and placement across a tiered memory hierarchy. Second, in modern DLRMs, EMBs function as hash tables. As a result, EMBs display interesting phenomena, such as the birthday paradox, leaving EMBs severely under-utilized. RecShard determines an optimal EMB sharding strategy for a set of EMBs based on training data distributions and model characteristics, along with the bandwidth characteristics of the underlying tiered memory hierarchy. In doing so, RecShard achieves over 6 times higher EMB training throughput on average for capacity constrained DLRMs. The throughput increase comes from improved EMB load balance by over 12 times and from the reduced access to the slower memory by over 87 times.
TGFuse: An Infrared and Visible Image Fusion Approach Based on Transformer and Generative Adversarial Network
Venue: arXiv cs.CV 2022
Year: 2022

The end-to-end image fusion framework has achieved promising performance, with dedicated convolutional networks aggregating the multi-modal local appearance. However, long-range dependencies are directly neglected in existing CNN fusion approaches, impeding balancing the entire image-level perception for complex scenario fusion. In this paper, therefore, we propose an infrared and visible image fusion algorithm based on a lightweight transformer module and adversarial learning. Inspired by the global interaction power, we use the transformer technique to learn the effective global fusion relations. In particular, shallow features extracted by CNN are interacted in the proposed transformer fusion module to refine the fusion relationship within the spatial scope and across channels simultaneously. Besides, adversarial learning is designed in the training process to improve the output discrimination via imposing competitive consistency from the inputs, reflecting the specific characteristics in infrared and visible images. The experimental performance demonstrates the effectiveness of the proposed modules, with superior improvement against the state-of-the-art, generalising a novel paradigm via transformer and adversarial learning in the fusion task.
Unsupervised Image Fusion Method based on Feature Mutual Mapping
Venue: arXiv cs.CV 2022
Year: 2022

Deep learning-based image fusion approaches have obtained wide attention in recent years, achieving promising performance in terms of visual perception. However, the fusion module in the current deep learning-based methods suffers from two limitations, \textit{i.e.}, manually designed fusion function, and input-independent network learning. In this paper, we propose an unsupervised adaptive image fusion method to address the above issues. We propose a feature mutual mapping fusion module and dual-branch multi-scale autoencoder. More specifically, we construct a global map to measure the connections of pixels between the input source images. % The found mapping relationship guides the image fusion. Besides, we design a dual-branch multi-scale network through sampling transformation to extract discriminative image features. We further enrich feature representations of different scales through feature aggregation in the decoding process. Finally, we propose a modified loss function to train the network with efficient convergence property. Through sufficient training on infrared and visible image data sets, our method also shows excellent generalized performance in multi-focus and medical image fusion. Our method achieves superior performance in both visual perception and objective evaluation. Experiments prove that the performance of our proposed method on a variety of image fusion tasks surpasses other state-of-the-art methods, proving the effectiveness and versatility of our approach.
Data-driven Mutation Analysis for Cyber-Physical Systems
Venue: arXiv cs.SE 2022
Year: 2022

Cyber-physical systems (CPSs) typically consist of a wide set of integrated, heterogeneous components; consequently, most of their critical failures relate to the interoperability of such components.Unfortunately, most CPS test automation techniques are preliminary and industry still heavily relies on manual testing. With potentially incomplete, manually-generated test suites, it is of paramount importance to assess their quality. Though mutation analysis has demonstrated to be an effective means to assess test suite quality in some specific contexts, we lack approaches for CPSs. Indeed, existing approaches do not target interoperability problems and cannot be executed in the presence of black-box or simulated components, a typical situation with CPSs. In this paper, we introduce data-driven mutation analysis, an approach that consists in assessing test suite quality by verifying if it detects interoperability faults simulated by mutating the data exchanged by software components. To this end, we describe a data-driven mutation analysis technique (DaMAT) that automatically alters the data exchanged through data buffers. Our technique is driven by fault models in tabular form where engineers specify how to mutate data items by selecting and configuring a set of mutation operators. We have evaluated DaMAT with CPSs in the space domain; specifically, the test suites for the software systems of a microsatellite and nanosatellites launched on orbit last year. Our results show that the approach effectively detects test suite shortcomings, is not affected by equivalent and redundant mutants, and entails acceptable costs.
Probabilistic Total Store Ordering
Venue: arXiv cs.PL 2022
Year: 2022

We present $\textit{Probabilistic Total Store Ordering (PTSO)}$ -- a probabilistic extension of the classical TSO semantics. For a given (finite-state) program, the operational semantics of PTSO induces an infinite-state Markov chain. We resolve the inherent non-determinism due to process schedulings and memory updates according to given probability distributions. We provide a comprehensive set of results showing the decidability of several properties for PTSO, namely (i) Almost-Sure (Repeated) Reachability: whether a run, starting from a given initial configuration, almost surely visits (resp. almost surely repeatedly visits) a given set of target configurations. (ii) Almost-Never (Repeated) Reachability: whether a run from the initial configuration, almost never visits (resp. almost never repeatedly visits) the target. (iii) Approximate Quantitative (Repeated) Reachability: to approximate, up to an arbitrary degree of precision, the measure of runs that start from the initial configuration and (repeatedly) visit the target. (iv) Expected Average Cost: to approximate, up to an arbitrary degree of precision, the expected average cost of a run from the initial configuration to the target. We derive our results through a nontrivial combination of results from the classical theory of (infinite-state) Markov chains, the theories of decisive and eager Markov chains, specific techniques from combinatorics, as well as, decidability and complexity results for the classical (non-probabilistic) TSO semantics. As far as we know, this is the first work that considers probabilistic verification of programs running on weak memory models.
On Uniform Boundedness Properties of SGD and its Momentum Variants
Venue: arXiv cs.LG 2022
Year: 2022

A theoretical, and potentially also practical, problem with stochastic gradient descent is that trajectories may escape to infinity. In this note, we investigate uniform boundedness properties of iterates and function values along the trajectories of the stochastic gradient descent algorithm and its important momentum variant. Under smoothness and $R$-dissipativity of the loss function, we show that broad families of step-sizes, including the widely used step-decay and cosine with (or without) restart step-sizes, result in uniformly bounded iterates and function values. Several important applications that satisfy these assumptions, including phase retrieval problems, Gaussian mixture models, and some neural network classifiers, are discussed in detail. We further extend the uniform boundedness of SGD and its momentum variant under the generalized dissipativity for the functions whose tails grow slower than quadratic functions. This includes some interesting applications, for example, Bayesian logistic regression and logistic regression with $\ell_1$ regularization.
HoneyTop90: A 90-line MATLAB code for topology optimization using honeycomb tessellation
Venue: arXiv cs.CE 2022
Year: 2022

This paper provides a simple, compact and efficient 90-line pedagogical MATLAB code for topology optimization using hexagonal elements (honeycomb tessellation). Hexagonal elements provide nonsingular connectivity between two juxtaposed elements and, thus, subdue checkerboard patterns and point connections inherently from the optimized designs. A novel approach to generate honeycomb tessellation is proposed. The element connectivity matrix and corresponding nodal coordinates array are determined in 5 (7) and 4 (6) lines, respectively. Two additional lines for the meshgrid generation are required for an even number of elements in the vertical direction. The code takes a fraction of a second to generate meshgrid information for the millions of hexagonal elements. Wachspress shape functions are employed for the finite element analysis, and compliance minimization is performed using the optimality criteria method. The provided Matlab code and its extensions are explained in detail. Options to run the optimization with and without filtering techniques are provided. Steps to include different boundary conditions, multiple load cases, active and passive regions, and a Heaviside projection filter are also discussed. The code is provided in Appendix~A, and it can also be downloaded along with supplementary materials from \url{https://github.com/PrabhatIn/HoneyTop90}.
On the Translation of Automata to Linear Temporal Logic
Venue: arXiv cs.FL 2022
Year: 2022

While the complexity of translating future linear temporal logic (LTL) into automata on infinite words is well-understood, the size increase involved in turning automata back to LTL is not. In particular, there is no known elementary bound on the complexity of translating deterministic $ω$-regular automata to LTL. Our first contribution consists of tight bounds for LTL over a unary alphabet: alternating, nondeterministic and deterministic automata can be exactly exponentially, quadratically and linearly more succinct, respectively, than any equivalent LTL formula. Our main contribution consists of a translation of general counter-free deterministic $ω$-regular automata into LTL formulas of double exponential temporal-nesting depth and triple exponential length, using an intermediate Krohn-Rhodes cascade decomposition of the automaton. To our knowledge, this is the first elementary bound on this translation. Furthermore, our translation preserves the acceptance condition of the automaton in the sense that it turns a looping, weak, Büchi, coBüchi or Muller automaton into a formula that belongs to the matching class of the syntactic future hierarchy. In particular, it can be used to translate an LTL formula recognising a safety language to a formula belonging to the safety fragment of LTL (over both finite and infinite words).
Comparison research on binary relations based on transitive degrees and cluster degrees
Venue: arXiv cs.AI 2022
Year: 2022

Interval-valued information systems are generalized models of single-valued information systems. By rough set approach, interval-valued information systems have been extensively studied. Authors could establish many binary relations from the same interval-valued information system. In this paper, we do some researches on comparing these binary relations so as to provide numerical scales for choosing suitable relations in dealing with interval-valued information systems. Firstly, based on similarity degrees, we compare the most common three binary relations induced from the same interval-valued information system. Secondly, we propose the concepts of transitive degree and cluster degree, and investigate their properties. Finally, we provide some methods to compare binary relations by means of the transitive degree and the cluster degree. Furthermore, we use these methods to analyze the most common three relations induced from Face Recognition Dataset, and obtain that $RF_{B} ^λ$ is a good choice when we deal with an interval-valued information system by means of rough set approach.
ML4CO-KIDA: Knowledge Inheritance in Dataset Aggregation
Venue: arXiv cs.AI 2022
Year: 2022

The Machine Learning for Combinatorial Optimization (ML4CO) NeurIPS 2021 competition aims to improve state-of-the-art combinatorial optimization solvers by replacing key heuristic components with machine learning models. On the dual task, we design models to make branching decisions to promote the dual bound increase faster. We propose a knowledge inheritance method to generalize knowledge of different models from the dataset aggregation process, named KIDA. Our improvement overcomes some defects of the baseline graph-neural-networks-based methods. Further, we won the $1$\textsuperscript{st} Place on the dual task. We hope this report can provide useful experience for developers and researchers. The code is available at https://github.com/megvii-research/NeurIPS2021-ML4CO-KIDA.
BLDNet: A Semi-supervised Change Detection Building Damage Framework using Graph Convolutional Networks and Urban Domain Knowledge
Venue: arXiv cs.CV 2022
Year: 2022

Change detection is instrumental to localize damage and understand destruction in disaster informatics. While convolutional neural networks are at the core of recent change detection solutions, we present in this work, BLDNet, a novel graph formulation for building damage change detection and enable learning relationships and representations from both local patterns and non-stationary neighborhoods. More specifically, we use graph convolutional networks to efficiently learn these features in a semi-supervised framework with few annotated data. Additionally, BLDNet formulation allows for the injection of additional contextual building meta-features. We train and benchmark on the xBD dataset to validate the effectiveness of our approach. We also demonstrate on urban data from the 2020 Beirut Port Explosion that performance is improved by incorporating domain knowledge building meta-features.
Stochastic dendrites enable online learning in mixed-signal neuromorphic processing systems
Venue: arXiv cs.ET 2022
Year: 2022

The stringent memory and power constraints required in edge-computing sensory-processing applications have made event-driven neuromorphic systems a promising technology. On-chip online learning provides such systems the ability to learn the statistics of the incoming data and to adapt to their changes. Implementing online learning on event driven-neuromorphic systems requires (i) a spike-based learning algorithm that calculates the weight updates using only local information from streaming data, (ii) mapping these weight updates onto limited bit precision memory and (iii) doing so in a robust manner that does not lead to unnecessary updates as the system is reaching its optimal output. Recent neuroscience studies have shown how dendritic compartments of cortical neurons can solve these problems in biological neural networks. Inspired by these studies we propose spike-based learning circuits to implement stochastic dendritic online learning. The circuits are embedded in a prototype spiking neural network fabricated using a 180nm process. Following an algorithm-circuits co-design approach we present circuits and behavioral simulation results that demonstrate the learning rule features. We validate the proposed method using behavioral simulations of a single-layer network with 4-bit precision weights applied to the MNIST benchmark and demonstrating results that reach accuracy levels above 85%.
Transformer-Based Video Front-Ends for Audio-Visual Speech Recognition for Single and Multi-Person Video
Venue: arXiv cs.CV 2022
Year: 2022

Audio-visual automatic speech recognition (AV-ASR) extends speech recognition by introducing the video modality as an additional source of information. In this work, the information contained in the motion of the speaker's mouth is used to augment the audio features. The video modality is traditionally processed with a 3D convolutional neural network (e.g. 3D version of VGG). Recently, image transformer networks arXiv:2010.11929 demonstrated the ability to extract rich visual features for image classification tasks. Here, we propose to replace the 3D convolution with a video transformer to extract visual features. We train our baselines and the proposed model on a large scale corpus of YouTube videos. The performance of our approach is evaluated on a labeled subset of YouTube videos as well as on the LRS3-TED public corpus. Our best video-only model obtains 31.4% WER on YTDEV18 and 17.0% on LRS3-TED, a 10% and 15% relative improvements over our convolutional baseline. We achieve the state of the art performance of the audio-visual recognition on the LRS3-TED after fine-tuning our model (1.6% WER). In addition, in a series of experiments on multi-person AV-ASR, we obtained an average relative reduction of 2% over our convolutional video frontend.