OpenRaiser/Intern-Atlas huggingface dataset:
Adversarial Attacks on Convolutional Neural Networks in Facial Recognition Domain
Venue: arXiv cs.LG 2021
Year: 2021

Numerous recent studies have demonstrated how Deep Neural Network (DNN) classifiers can be fooled by adversarial examples, in which an attacker adds perturbations to an original sample, causing the classifier to misclassify the sample. Adversarial attacks that render DNNs vulnerable in real life represent a serious threat in autonomous vehicles, malware filters, or biometric authentication systems. In this paper, we apply Fast Gradient Sign Method to introduce perturbations to a facial image dataset and then test the output on a different classifier that we trained ourselves, to analyze transferability of this method. Next, we craft a variety of different black-box attack algorithms on a facial image dataset assuming minimal adversarial knowledge, to further assess the robustness of DNNs in facial recognition. While experimenting with different image distortion techniques, we focus on modifying single optimal pixels by a large amount, or modifying all pixels by a smaller amount, or combining these two attack approaches. While our single-pixel attacks achieved about a 15% average decrease in classifier confidence level for the actual class, the all-pixel attacks were more successful and achieved up to an 84% average decrease in confidence, along with an 81.6% misclassification rate, in the case of the attack that we tested with the highest levels of perturbation. Even with these high levels of perturbation, the face images remained identifiable to a human. Understanding how these noised and perturbed images baffle the classification algorithms can yield valuable advances in the training of DNNs against defense-aware adversarial attacks, as well as adaptive noise reduction techniques. We hope our research may help to advance the study of adversarial attacks on DNNs and defensive mechanisms to counteract them, particularly in the facial recognition domain.
Efficient q-Integer Linear Decomposition of Multivariate Polynomials
Venue: arXiv cs.SC 2021
Year: 2021

We present two new algorithms for the computation of the q-integer linear decomposition of a multivariate polynomial. Such a decomposition is essential for the treatment of q-hypergeometric symbolic summation via creative telescoping and for describing the q-counterpart of Ore-Sato theory. Both of our algorithms require only basic integer and polynomial arithmetic and work for any unique factorization domain containing the ring of integers. Complete complexity analyses are conducted for both our algorithms and two previous algorithms in the case of multivariate integer polynomials, showing that our algorithms have better theoretical performances. A Maple implementation is also included which suggests that our algorithms are also much faster in practice than previous algorithms.
Adaptive strategy in differential evolution via explicit exploitation and exploration controls
Venue: arXiv cs.NE 2021
Year: 2021

Existing multi-strategy adaptive differential evolution (DE) commonly involves trials of multiple strategies and then rewards better-performing ones with more resources. However, the trials of an exploitative or explorative strategy may result in over-exploitation or over-exploration. To improve the performance, this paper proposes a new strategy adaptation method, named explicit adaptation scheme (Ea scheme), which separates multiple strategies and employs them on-demand. It is done by dividing the evolution process into several Selective-candidate with Similarity Selection (SCSS) generations and adaptive generations. In the SCSS generations, the exploitation and exploration needs are learnt by utilizing a balanced strategy. To meet these needs, in adaptive generations, two other strategies, exploitative or explorative is adaptively used. Experimental studies on benchmark functions demonstrate the effectiveness of Ea scheme when compared with its variants and other adaptation methods. Furthermore, performance comparisons with state-of-the-art evolutionary algorithms and swarm intelligence-based algorithms show that EaDE is very competitive.
Oral Billiards
Venue: arXiv cs.SD 2021
Year: 2021

We propose a physical model of speech to explain its precision and robustness. We begin by reducing the dynamics to the bare minimum of polygonal billiards. The symbolic stability of the billiard trajectories against variations in action and the oral cavity geometry forms the basis for precision and robustness in articulation. This stability survives forcing and dissipation to underpin reliable encoding of the trajectories into acoustic emissions. The kinematics of oral billiards and the cyclical nature of the forcing mechanism engender a grammar of the syllable independent of any language. The symbolic dynamics of oral billiards is rendered nearly maximally observable by their concomitant acoustic emissions. Speech recognition is the set of computations on the sub-maximally informative acoustic observables from which the symbolic dynamics of oral billiards may be inferred.
Linearly Constrained Gaussian Processes with Boundary Conditions
Venue: arXiv cs.LG 2021
Year: 2021

One goal in Bayesian machine learning is to encode prior knowledge into prior distributions, to model data efficiently. We consider prior knowledge from systems of linear partial differential equations together with their boundary conditions. We construct multi-output Gaussian process priors with realizations in the solution set of such systems, in particular only such solutions can be represented by Gaussian process regression. The construction is fully algorithmic via Gröbner bases and it does not employ any approximation. It builds these priors combining two parametrizations via a pullback: the first parametrizes the solutions for the system of differential equations and the second parametrizes all functions adhering to the boundary conditions.
Optimized spiking neurons classify images with high accuracy through temporal coding with two spikes
Venue: arXiv cs.NE 2021
Year: 2021

Spike-based neuromorphic hardware promises to reduce the energy consumption of image classification and other deep learning applications, particularly on mobile phones or other edge devices. However, direct training of deep spiking neural networks is difficult, and previous methods for converting trained artificial neural networks to spiking neurons were inefficient because the neurons had to emit too many spikes. We show that a substantially more efficient conversion arises when one optimizes the spiking neuron model for that purpose, so that it not only matters for information transmission how many spikes a neuron emits, but also when it emits those spikes. This advances the accuracy that can be achieved for image classification with spiking neurons, and the resulting networks need on average just two spikes per neuron for classifying an image. In addition, our new conversion method improves latency and throughput of the resulting spiking networks.
Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes
Venue: arXiv cs.LG 2021
Year: 2021

Stochastic Approximation (SA) is a popular approach for solving fixed-point equations where the information is corrupted by noise. In this paper, we consider an SA involving a contraction mapping with respect to an arbitrary norm, and show its finite-sample error bounds while using different stepsizes. The idea is to construct a smooth Lyapunov function using the generalized Moreau envelope, and show that the iterates of SA have negative drift with respect to that Lyapunov function. Our result is applicable in Reinforcement Learning (RL). In particular, we use it to establish the first-known convergence rate of the V-trace algorithm for off-policy TD-learning. Moreover, we also use it to study TD-learning in the on-policy setting, and recover the existing state-of-the-art results for $Q$-learning. Importantly, our construction results in only a logarithmic dependence of the convergence bound on the size of the state-space.
A Deep Conditioning Treatment of Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

We study the role of depth in training randomly initialized overparameterized neural networks. We give a general result showing that depth improves trainability of neural networks by improving the conditioning of certain kernel matrices of the input data. This result holds for arbitrary non-linear activation functions under a certain normalization. We provide versions of the result that hold for training just the top layer of the neural network, as well as for training all layers, via the neural tangent kernel. As applications of these general results, we provide a generalization of the results of Das et al. (2019) showing that learnability of deep random neural networks with a large class of non-linear activations degrades exponentially with depth. We also show how benign overfitting can occur in deep neural networks via the results of Bartlett et al. (2019b). We also give experimental evidence that normalized versions of ReLU are a viable alternative to more complex operations like Batch Normalization in training deep neural networks.
Optimal Causal Rate-Constrained Sampling for a Class of Continuous Markov Processes
Venue: arXiv cs.IT 2021
Year: 2021

Consider the following communication scenario. An encoder observes a stochastic process and causally decides when and what to transmit about it, under a constraint on the expected number of bits transmitted per second. A decoder uses the received codewords to causally estimate the process in real time. The encoder and the decoder are synchronized in time. For a class of continuous Markov processes satisfying regularity conditions, we find the optimal encoding and decoding policies that minimize the end-to-end estimation mean-square error under the rate constraint. We show that the optimal encoding policy transmits a $1$-bit codeword once the process innovation passes one of two thresholds. The optimal decoder noiselessly recovers the last sample from the 1-bit codewords and codeword-generating time stamps, and uses it to decide the running estimate of the current process, until the next codeword arrives. In particular, we show the optimal causal code for the Ornstein-Uhlenbeck process and calculate its distortion-rate function. Furthermore, we show that the optimal causal code also minimizes the mean-square cost of a continuous-time control system driven by a continuous Markov process and controlled by an additive control signal.
Comparison of Decentralization in DPoS and PoW Blockchains
Venue: arXiv cs.CR 2021
Year: 2021

Decentralization is a key indicator for the evaluation of public blockchains. In the past, there have been very few studies on measuring and comparing the actual level of decentralization between Proof-of-Work (PoW) blockchains and blockchains with other consensus protocols. This paper presents a new comparison study of the level of decentralization in Bitcoin and Steem, a prominent Delegated-Proof-of-Stake (DPoS) blockchain. Our study particularly focuses on analysing the power that decides the creators of blocks in the blockchain. In Bitcoin, miners with higher computational power generate more blocks. In contrast, blocks in Steem are equally generated by witnesses while witnesses are periodically elected by stakeholders with different voting power weighted by invested stake. We analyze the process of stake-weighted election of witnesses in DPoS and measure the actual stake invested by each stakeholder in Steem. We then compute the Shannon entropy of the distribution of computational power among miners in Bitcoin and the distribution of invested stake among stakeholders in Steem. Our analyses reveal that neither Bitcoin nor Steem is dominantly better than the other with respect to decentralization. Compared with Steem, Bitcoin tends to be more decentralized among top miners but less decentralized in general. Our study is designed to provide insights into the current state of the degree of decentralization in DPoS and PoW blockchains. We believe that the methodologies and findings in this paper can facilitate future studies of decentralization in other blockchain systems employing different consensus protocols.
AI-GAN: Attack-Inspired Generation of Adversarial Examples
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural networks (DNNs) are vulnerable to adversarial examples, which are crafted by adding imperceptible perturbations to inputs. Recently different attacks and strategies have been proposed, but how to generate adversarial examples perceptually realistic and more efficiently remains unsolved. This paper proposes a novel framework called Attack-Inspired GAN (AI-GAN), where a generator, a discriminator, and an attacker are trained jointly. Once trained, it can generate adversarial perturbations efficiently given input images and target classes. Through extensive experiments on several popular datasets \eg MNIST and CIFAR-10, AI-GAN achieves high attack success rates and reduces generation time significantly in various settings. Moreover, for the first time, AI-GAN successfully scales to complicated datasets \eg CIFAR-100 with around $90\%$ success rates among all classes.
Relating Apartness and Bisimulation
Venue: arXiv cs.LO 2021
Year: 2021

A bisimulation for a coalgebra of a functor on the category of sets can be described via a coalgebra in the category of relations, of a lifted functor. A final coalgebra then gives rise to the coinduction principle, which states that two bisimilar elements are equal. For polynomial functors, this leads to well-known descriptions. In the present paper we look at the dual notion of "apartness". Intuitively, two elements are apart if there is a positive way to distinguish them. Phrased differently: two elements are apart if and only if they are not bisimilar. Since apartness is an inductive notion, described by a least fixed point, we can give a proof system, to derive that two elements are apart. This proof system has derivation rules and two elements are apart if and only if there is a finite derivation (using the rules) of this fact. We study apartness versus bisimulation in two separate ways. First, for weak forms of bisimulation on labelled transition systems, where silent (tau) steps are included, we define an apartness notion that corresponds to weak bisimulation and another apartness that corresponds to branching bisimulation. The rules for apartness can be used to show that two states of a labelled transition system are not branching bismilar. To support the apartness view on labelled transition systems, we cast a number of well-known properties of branching bisimulation in terms of branching apartness and prove them. Next, we also study the more general categorical situation and show that indeed, apartness is the dual of bisimilarity in a precise categorical sense: apartness is an initial algebra and gives rise to an induction principle. In this analogy, we include the powerset functor, which gives a semantics to non-deterministic choice in process-theory.
Curvature of Feasible Sets in Offline and Online Optimization
Venue: arXiv cs.DS 2021
Year: 2021

It is known that the curvature of the feasible set in convex optimization allows for algorithms with better convergence rates, and there has been renewed interest in this topic both for offline as well as online problems. In this paper, leveraging results on geometry and convex analysis, we further our understanding of the role of curvature in optimization: - We first show the equivalence of two notions of curvature, namely strong convexity and gauge bodies, proving a conjecture of Abernethy et al. As a consequence, this show that the Frank-Wolfe-type method of Wang and Abernethy has accelerated convergence rate $O(\frac{1}{t^2})$ over strongly convex feasible sets without additional assumptions on the (convex) objective function. - In Online Linear Optimization, we identify two main properties that help explaining \emph{why/when} Follow the Leader (FTL) has only logarithmic regret over strongly convex sets. This allows one to directly recover a recent result of Huang et al., and to show that FTL has logarithmic regret over strongly convex sets whenever the gain vectors are non-negative. - We provide an efficient procedure for approximating convex bodies by strongly convex ones while smoothly trading off approximation error and curvature. This allows one to extend the improved algorithms over strongly convex sets to general convex sets. As a concrete application, we extend the results of Dekel et al. on Online Linear Optimization with Hints to general convex sets.
Inference for Batched Bandits
Venue: arXiv cs.LG 2021
Year: 2021

As bandit algorithms are increasingly utilized in scientific studies and industrial applications, there is an associated increasing need for reliable inference methods based on the resulting adaptively-collected data. In this work, we develop methods for inference on data collected in batches using a bandit algorithm. We first prove that the ordinary least squares estimator (OLS), which is asymptotically normal on independently sampled data, is not asymptotically normal on data collected using standard bandit algorithms when there is no unique optimal arm. This asymptotic non-normality result implies that the naive assumption that the OLS estimator is approximately normal can lead to Type-1 error inflation and confidence intervals with below-nominal coverage probabilities. Second, we introduce the Batched OLS estimator (BOLS) that we prove is (1) asymptotically normal on data collected from both multi-arm and contextual bandits and (2) robust to non-stationarity in the baseline reward.
A Spike in Performance: Training Hybrid-Spiking Neural Networks with Quantized Activation Functions
Venue: arXiv cs.LG 2021
Year: 2021

The machine learning community has become increasingly interested in the energy efficiency of neural networks. The Spiking Neural Network (SNN) is a promising approach to energy-efficient computing, since its activation levels are quantized into temporally sparse, one-bit values (i.e., "spike" events), which additionally converts the sum over weight-activity products into a simple addition of weights (one weight for each spike). However, the goal of maintaining state-of-the-art (SotA) accuracy when converting a non-spiking network into an SNN has remained an elusive challenge, primarily due to spikes having only a single bit of precision. Adopting tools from signal processing, we cast neural activation functions as quantizers with temporally-diffused error, and then train networks while smoothly interpolating between the non-spiking and spiking regimes. We apply this technique to the Legendre Memory Unit (LMU) to obtain the first known example of a hybrid SNN outperforming SotA recurrent architectures -- including the LSTM, GRU, and NRU -- in accuracy, while reducing activities to at most 3.74 bits on average with 1.26 significant bits multiplying each weight. We discuss how these methods can significantly improve the energy efficiency of neural networks.
An efficient algorithm for numerical homogenization of fluid filled porous solids: part-I
Venue: arXiv cs.CE 2021
Year: 2021

The concept of representative volume element or RVE is invoked to develop an algorithm for numerical homogenization of fluid filled porous solids. RVE based methods decouple analysis of a composite material into analyses at the local and global levels. The local level analysis models the microstructural details to determine effective properties by applying boundary conditions to the RVE and solving the resultant boundary value problem. The composite structure is then replaced by an equivalent homogeneous material having the calculated effective properties. We combine the features of two techniques: one is the definition of a displacement field for the fluid phase to allow for a definition of a continuous displacement field across the microstructure and the other is the $FE^2$ numerical homogenization that couples the macroscale with the RVE scale via gauss points.
Proficiency Constrained Multi-Agent Reinforcement Learning for Environment-Adaptive Multi UAV-UGV Teaming
Venue: arXiv cs.RO 2021
Year: 2021

A mixed aerial and ground robot team, which includes both unmanned ground vehicles (UGVs) and unmanned aerial vehicles (UAVs), is widely used for disaster rescue, social security, precision agriculture, and military missions. However, team capability and corresponding configuration vary since robots have different motion speeds, perceiving ranges, reaching areas, and resilient capabilities to the dynamic environment. Due to heterogeneous robots inside a team and the resilient capabilities of robots, it is challenging to perform a task with an optimal balance between reasonable task allocations and maximum utilization of robot capability. To address this challenge for effective mixed ground and aerial teaming, this paper developed a novel teaming method, proficiency aware multi-agent deep reinforcement learning (Mix-RL), to guide ground and aerial cooperation by considering the best alignments between robot capabilities, task requirements, and environment conditions. Mix-RL largely exploits robot capabilities while being aware of the adaption of robot capabilities to task requirements and environment conditions. Mix-RL's effectiveness in guiding mixed teaming was validated with the task "social security for criminal vehicle tracking".
Theories of real addition with and without a predicate for integers
Venue: arXiv cs.LO 2021
Year: 2021

We show that it is decidable whether or not a relation on the reals definable in the structure $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$ can be defined in the structure $\langle \mathbb{R}, +,<, 1 \rangle$. This result is achieved by obtaining a topological characterization of $\langle \mathbb{R}, +,<, 1 \rangle$-definable relations in the family of $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$-definable relations and then by following Muchnik's approach of showing that the characterization of the relation $X$ can be expressed in the logic of $\langle \mathbb{R}, +,<,1, X \rangle$. The above characterization allows us to prove that there is no intermediate structure between $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$ and $\langle \mathbb{R}, +,<, 1 \rangle$. We also show that a $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$-definable relation is $\langle \mathbb{R}, +,<, 1 \rangle$-definable if and only if its intersection with every $\langle \mathbb{R}, +,<, 1 \rangle$-definable line is $\langle \mathbb{R}, +,<, 1 \rangle$-definable. This gives a noneffective but simple characterization of $\langle \mathbb{R}, +,<, 1 \rangle$-definable relations.
Learning Coupled Policies for Simultaneous Machine Translation using Imitation Learning
Venue: arXiv cs.CL 2021
Year: 2021

We present a novel approach to efficiently learn a simultaneous translation model with coupled programmer-interpreter policies. First, wepresent an algorithmic oracle to produce oracle READ/WRITE actions for training bilingual sentence-pairs using the notion of word alignments. This oracle actions are designed to capture enough information from the partial input before writing the output. Next, we perform a coupled scheduled sampling to effectively mitigate the exposure bias when learning both policies jointly with imitation learning. Experiments on six language-pairs show our method outperforms strong baselines in terms of translation quality while keeping the translation delay low.