OpenRaiser/Intern-Atlas huggingface dataset:
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
Venue: arXiv cs.LG 2020
Year: 2020

We consider networks, trained via stochastic gradient descent to minimize $\ell_2$ loss, with the training labels perturbed by independent noise at each iteration. We characterize the behavior of the training dynamics near any parameter vector that achieves zero training error, in terms of an implicit regularization term corresponding to the sum over the data points, of the squared $\ell_2$ norm of the gradient of the model with respect to the parameter vector, evaluated at each data point. This holds for networks of any connectivity, width, depth, and choice of activation function. We interpret this implicit regularization term for three simple settings: matrix sensing, two layer ReLU networks trained on one-dimensional data, and two layer networks with sigmoid activations trained on a single datapoint. For these settings, we show why this new and general implicit regularization effect drives the networks towards "simple" models.
Understanding the Stability of Medical Concept Embeddings
Venue: arXiv cs.CL 2020
Year: 2020

Frequency is one of the major factors for training quality word embeddings. Several work has recently discussed the stability of word embeddings in general domain and suggested factors influencing the stability. In this work, we conduct a detailed analysis on the stability of concept embeddings in medical domain, particularly the relation with concept frequency. The analysis reveals the surprising high stability of low-frequency concepts: low-frequency (<100) concepts have the same high stability as high-frequency (>1000) concepts. To develop a deeper understanding of this finding, we propose a new factor, the noisiness of context words, which influences the stability of medical concept embeddings, regardless of frequency. We evaluate the proposed factor by showing the linear correlation with the stability of medical concept embeddings. The correlations are clear and consistent with various groups of medical concepts. Based on the linear relations, we make suggestions on ways to adjust the noisiness of context words for the improvement of stability. Finally, we demonstrate that the proposed factor extends to the word embedding stability in general domain.
Enabling Secure Wireless Communications via Intelligent Reflecting Surfaces
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we propose to utilize intelligent reflecting surfaces (IRSs) for enhancing the physical layer security of wireless communications systems. In particular, an IRS-assisted secure wireless system is considered, where a multi-antenna transmitter communicates with a single-antenna receiver in the presence of an eavesdropper. To maximize the secrecy rate, both the beamformer at the transmitter and the IRS phase shifts are jointly optimized. Based on the block coordinate descent (BCD) and minorization maximization (MM) techniques, two efficient algorithms are developed to solve the resulting non-convex optimization problem for small- and large-scale IRSs, respectively. Simulation results show that IRSs can significantly improve physical layer security if the proposed algorithms are employed. Furthermore, we reveal that deploying large-scale IRSs is more efficient than enlarging the antenna array size of the transmitter for both boosting the secrecy rate and enhancing the energy efficiency.
Learning relevant features for statistical inference
Venue: arXiv cs.LG 2020
Year: 2020

Given two views of data, we consider the problem of finding the features of one view which can be most faithfully inferred from the other. We find that these are also the most correlated variables in the sense of deep canonical correlation analysis (DCCA). Moreover, we show that these variables can be used to construct a non-parametric representation of the implied joint probability distribution, which can be thought of as a classical version of the Schmidt decomposition of quantum states. This representation can be used to compute the expectations of functions over one view of data conditioned on the other, such as Bayesian estimators and their standard deviations. We test the approach using inference on occluded MNIST images, and show that our representation contains multiple modes. Surprisingly, when applied to supervised learning (one dataset consists of labels), this approach automatically provides regularization and faster convergence compared to the cross-entropy objective. We also explore using this approach to discover salient independent variables of a single dataset.
Optimizing Search API Queries for Twitter Topic Classifiers Using a Maximum Set Coverage Approach
Venue: arXiv cs.IR 2020
Year: 2020

Twitter has grown to become an important platform to access immediate information about major events and dynamic topics. As one example, recent work has shown that classifiers trained to detect topical content on Twitter can generalize well beyond the training data. Since access to Twitter data is hidden behind a limited search API, it is impossible (for most users) to apply these classifiers directly to the Twitter unfiltered data streams ("firehose"). Rather, applications must first decide what content to retrieve through the search API before filtering that content with topical classifiers. Thus, it is critically important to query the Twitter API relative to the intended topical classifier in a way that minimizes the amount of negatively classified data retrieved. In this paper, we propose a sequence of query optimization methods that generalize notions of the maximum coverage problem to find the subset of query terms within the API limits that cover most of the topically relevant tweets without sacrificing precision. We evaluate the proposed methods on a large dataset of Twitter data collected during 2013 and 2014 labeled using manually curated hashtags for eight topics. Among many insights, our analysis shows that the best of the proposed methods can significantly outperform the firehose on precision and F1-score while achieving high recall within strict API limitations.
Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms
Venue: arXiv cs.LG 2020
Year: 2020

Recursive stochastic algorithms have gained significant attention in the recent past due to data driven applications. Examples include stochastic gradient descent for solving large-scale optimization problems and empirical dynamic programming algorithms for solving Markov decision problems. These recursive stochastic algorithms approximate certain contraction operators and can be viewed within the framework of iterated random operators. Accordingly, we consider iterated random operators over a Polish space that simulate iterated contraction operator over that Polish space. Assume that the iterated random operators are indexed by certain batch sizes such that as batch sizes grow to infinity, each realization of the random operator converges (in some sense) to the contraction operator it is simulating. We show that starting from the same initial condition, the distribution of the random sequence generated by the iterated random operators converges weakly to the trajectory generated by the contraction operator. We further show that under certain conditions, the time average of the random sequence converges to the spatial mean of the invariant distribution. We then apply these results to logistic regression, empirical value iteration, and empirical Q value iteration for finite state finite action MDPs to illustrate the general theory develop here.
Fusion-supervised Deep Cross-modal Hashing
Venue: arXiv cs.IR 2020
Year: 2020

Deep hashing has recently received attention in cross-modal retrieval for its impressive advantages. However, existing hashing methods for cross-modal retrieval cannot fully capture the heterogeneous multi-modal correlation and exploit the semantic information. In this paper, we propose a novel \emph{Fusion-supervised Deep Cross-modal Hashing} (FDCH) approach. Firstly, FDCH learns unified binary codes through a fusion hash network with paired samples as input, which effectively enhances the modeling of the correlation of heterogeneous multi-modal data. Then, these high-quality unified hash codes further supervise the training of the modality-specific hash networks for encoding out-of-sample queries. Meanwhile, both pair-wise similarity information and classification information are embedded in the hash networks under one stream framework, which simultaneously preserves cross-modal similarity and keeps semantic consistency. Experimental results on two benchmark datasets demonstrate the state-of-the-art performance of FDCH.
A multi-start local search algorithm for the Hamiltonian completion problem on undirected graphs
Venue: arXiv cs.DM 2020
Year: 2020

This paper proposes a local search algorithm for a specific combinatorial optimisation problem in graph theory: the Hamiltonian Completion Problem (HCP) on undirected graphs. In this problem, the objective is to add as few edges as possible to a given undirected graph in order to obtain a Hamiltonian graph. This problem has mainly been studied in the context of various specific kinds of undirected graphs (e.g. trees, unicyclic graphs and series-parallel graphs). The proposed algorithm, however, concentrates on solving HCP for general undirected graphs. It can be considered to belong to the category of matheuristics, because it integrates an exact linear time solution for trees into a local search algorithm for general graphs. This integration makes use of the close relation between HCP and the minimum path partition problem, which makes the algorithm equally useful for solving the latter problem. Furthermore, a benchmark set of problem instances is constructed for demonstrating the quality of the proposed algorithm. A comparison with state-of-the-art solvers indicates that the proposed algorithm is able to achieve high-quality results.
Achieving Max-Min Throughput in LoRa Networks
Venue: arXiv cs.IT 2020
Year: 2020

With growing popularity, LoRa networks are pivotally enabling Long Range connectivity to low-cost and power-constrained user equipments (UEs). Due to its wide coverage area, a critical issue is to effectively allocate wireless resources to support potentially massive UEs in the cell while resolving the prominent near-far fairness problem for cell-edge UEs, which is challenging to address due to the lack of tractable analytical model for the LoRa network and its practical requirement for low-complexity and low-overhead design. To achieve massive connectivity with fairness, we investigate the problem of maximizing the minimum throughput of all UEs in the LoRa network, by jointly designing high-level policies of spreading factor (SF) allocation, power control, and duty cycle adjustment based only on average channel statistics and spatial UE distribution. By leveraging on the Poisson rain model along with tailored modifications to our considered LoRa network, we are able to account for channel fading, aggregate interference and accurate packet overlapping, and still obtain a tractable and yet accurate closed-form formula for the packet success probability and hence throughput. We further propose an iterative balancing (IB) method to allocate the SFs in the cell such that the overall max-min throughput can be achieved within the considered time period and cell area. Numerical results show that the proposed scheme with optimized design greatly alleviates the near-far fairness issue, and significantly improves the cell-edge throughput.
Tracelets and Tracelet Analysis Of Compositional Rewriting Systems
Venue: arXiv cs.LO 2020
Year: 2020

Taking advantage of a recently discovered associativity property of rule compositions, we extend the classical concurrency theory for rewriting systems over adhesive categories. We introduce the notion of tracelets, which are defined as minimal derivation traces that universally encode sequential compositions of rewriting rules. Tracelets are compositional, capture the causality of equivalence classes of traditional derivation traces, and intrinsically suggest a clean mathematical framework for the definition of various notions of abstractions of traces. We illustrate these features by introducing a first prototype for a framework of tracelet analysis, which as a key application permits to formulate a first-of-its-kind algorithm for the static generation of minimal derivation traces with prescribed terminal events.
On the incomputability of computable dimension
Venue: arXiv cs.LO 2020
Year: 2020

Using an iterative tree construction we show that for simple computable subsets of the Cantor space Hausdorff, constructive and computable dimensions might be incomputable.
Overlap Algebras: a Constructive Look at Complete Boolean Algebras
Venue: arXiv cs.LO 2020
Year: 2020

The notion of a complete Boolean algebra, although completely legitimate in constructive mathematics, fails to capture some natural structures such as the lattice of subsets of a given set. Sambin's notion of an overlap algebra, although classically equivalent to that of a complete Boolean algebra, has powersets and other natural structures as instances. In this paper we study the category of overlap algebras as an extension of the category of sets and relations, and we establish some basic facts about mono-epi-isomorphisms and (co)limits; here a morphism is a symmetrizable function (with classical logic this is just a function which preserves joins). Then we specialize to the case of morphisms which preserve also finite meets: classically, this is the usual category of complete Boolean algebras. Finally, we connect overlap algebras with locales, and their morphisms with open maps between locales, thus obtaining constructive versions of some results about Boolean locales.
Driving with Style: Inverse Reinforcement Learning in General-Purpose Planning for Automated Driving
Venue: arXiv cs.RO 2020
Year: 2020

Behavior and motion planning play an important role in automated driving. Traditionally, behavior planners instruct local motion planners with predefined behaviors. Due to the high scene complexity in urban environments, unpredictable situations may occur in which behavior planners fail to match predefined behavior templates. Recently, general-purpose planners have been introduced, combining behavior and local motion planning. These general-purpose planners allow behavior-aware motion planning given a single reward function. However, two challenges arise: First, this function has to map a complex feature space into rewards. Second, the reward function has to be manually tuned by an expert. Manually tuning this reward function becomes a tedious task. In this paper, we propose an approach that relies on human driving demonstrations to automatically tune reward functions. This study offers important insights into the driving style optimization of general-purpose planners with maximum entropy inverse reinforcement learning. We evaluate our approach based on the expected value difference between learned and demonstrated policies. Furthermore, we compare the similarity of human driven trajectories with optimal policies of our planner under learned and expert-tuned reward functions. Our experiments show that we are able to learn reward functions exceeding the level of manual expert tuning without prior domain knowledge.
On Linear Learning with Manycore Processors
Venue: arXiv cs.PF 2020
Year: 2020

A new generation of manycore processors is on the rise that offers dozens and more cores on a chip and, in a sense, fuses host processor and accelerator. In this paper we target the efficient training of generalized linear models on these machines. We propose a novel approach for achieving parallelism which we call Heterogeneous Tasks on Homogeneous Cores (HTHC). It divides the problem into multiple fundamentally different tasks, which themselves are parallelized. For evaluation, we design a detailed, architecture-cognizant implementation of our scheme on a recent 72-core Knights Landing processor that is adaptive to the cache, memory, and core structure. Our library efficiently supports dense and sparse datasets as well as 4-bit quantized data for further possible gains in performance. We show benchmarks for Lasso and SVM with different data sets against straightforward parallel implementations and prior software. In particular, for Lasso on dense data, we improve the state-of-the-art by an order of magnitude.
An Adaptive Performance-oriented Scheduler for Static and Dynamic Heterogeneity
Venue: arXiv cs.DC 2020
Year: 2020

With the emergence of heterogeneous hardware paving the way for the post-Moore era, it is of high importance to adapt the runtime scheduling to the platform's heterogeneity. To enhance adaptive and responsive scheduling, we introduce a Performance Trace Table (PTT) into XiTAO, a framework for elastic scheduling of mixed-mode parallelism. The PTT is an extensible and dynamic lightweight manifest of the per-core latency that can be used to guide the scheduling of both critical and non-critical tasks. By understanding the per-task latency, the PTT can infer task performance, intra-application interference as well as inter-application interference. We run random Direct Acyclic Graphs (DAGs) of different workload categories as a benchmark on NVIDIA Jetson TX2 chip, achieving up to 3.25x speedup over a standard work-stealing scheduler. To exemplify scheduling adaption to interference, we run DAGs with high parallelism and analyze the scheduler's response to interference from a background process on an Intel Haswell (2650v3) multicore workstation. We also showcase the XiTAO's scheduling performance by porting the VGG-16 image classification framework based on Convolutional Neural Networks (CNN).
The Complexity of Subgame Perfect Equilibria in Quantitative Reachability Games
Venue: arXiv cs.GT 2020
Year: 2020

We study multiplayer quantitative reachability games played on a finite directed graph, where the objective of each player is to reach his target set of vertices as quickly as possible. Instead of the well-known notion of Nash equilibrium (NE), we focus on the notion of subgame perfect equilibrium (SPE), a refinement of NE well-suited in the framework of games played on graphs. It is known that there always exists an SPE in quantitative reachability games and that the constrained existence problem is decidable. We here prove that this problem is PSPACE-complete. To obtain this result, we propose a new algorithm that iteratively builds a set of constraints characterizing the set of SPE outcomes in quantitative reachability games. This set of constraints is obtained by iterating an operator that reinforces the constraints up to obtaining a fixpoint. With this fixpoint, the set of SPE outcomes can be represented by a finite graph of size at most exponential. A careful inspection of the computation allows us to establish PSPACE membership.
A globally exponentially stable position observer for interior permanent magnet synchronous motors
Venue: arXiv cs.SY 2020
Year: 2020

The design of a position observer for the interior permanent magnet synchronous motor is a challenging problem that, in spite of many research efforts, remained open for a long time. In this paper we present the first globally exponentially convergent solution to it, assuming that the saliency is not too large. As expected in all observer tasks, a persistency of excitation condition is imposed. Conditions on the operation of the motor, under which it is verified, are given. In particular, it is shown that at rotor standstill---when the system is not observable---it is possible to inject a probing signal to enforce the persistent excitation condition. {The high performance of the proposed observer, in standstill and high speed regions, is verified by extensive series of test-runs on an experimental setup.
Improving Visual Relation Detection using Depth Maps
Venue: arXiv cs.CV 2020
Year: 2020

Visual relation detection methods rely on object information extracted from RGB images such as 2D bounding boxes, feature maps, and predicted class probabilities. We argue that depth maps can additionally provide valuable information on object relations, e.g. helping to detect not only spatial relations, such as standing behind, but also non-spatial relations, such as holding. In this work, we study the effect of using different object features with a focus on depth maps. To enable this study, we release a new synthetic dataset of depth maps, VG-Depth, as an extension to Visual Genome (VG). We also note that given the highly imbalanced distribution of relations in VG, typical evaluation metrics for visual relation detection cannot reveal improvements of under-represented relations. To address this problem, we propose using an additional metric, calling it Macro Recall@K, and demonstrate its remarkable performance on VG. Finally, our experiments confirm that by effective utilization of depth maps within a simple, yet competitive framework, the performance of visual relation detection can be improved by a margin of up to 8%.
When Attackers Meet AI: Learning-empowered Attacks in Cooperative Spectrum Sensing
Venue: arXiv cs.NI 2020
Year: 2020

Defense strategies have been well studied to combat Byzantine attacks that aim to disrupt cooperative spectrum sensing by sending falsified versions of spectrum sensing data to a fusion center. However, existing studies usually assume network or attackers as passive entities, e.g., assuming the prior knowledge of attacks is known or fixed. In practice, attackers can actively adopt arbitrary behaviors and avoid pre-assumed patterns or assumptions used by defense strategies. In this paper, we revisit this security vulnerability as an adversarial machine learning problem and propose a novel learning-empowered attack framework named Learning-Evaluation-Beating (LEB) to mislead the fusion center. Based on the black-box nature of the fusion center in cooperative spectrum sensing, our new perspective is to make the adversarial use of machine learning to construct a surrogate model of the fusion center's decision model. We propose a generic algorithm to create malicious sensing data using this surrogate model. Our real-world experiments show that the LEB attack is effective to beat a wide range of existing defense strategies with an up to 82% of success ratio. Given the gap between the proposed LEB attack and existing defenses, we introduce a non-invasive method named as influence-limiting defense, which can coexist with existing defenses to defend against LEB attack or other similar attacks. We show that this defense is highly effective and reduces the overall disruption ratio of LEB attack by up to 80%.
Stochastic quantization approach to modeling of constrained Ito processes in discrete time
Venue: arXiv cs.SY 2020
Year: 2020

Stochastic quantization in physics has been considered to provide a path integral representation of a probability distribution for Ito processes. It has been indicated that the stochastic quantization can involve a potential term, if the Ito process is limited to Langevin equation. In this paper, in order to apply the stochastic quantization to engineering problems, we propose a novel method to incorporate a potential term into stochastic quantization of the general Ito process. This method indicates that weighted distribution gives rise to the potential term for the discrete-time path integral and preserves the role of the path integral as the probability distribution, without making any assumptions on the drift term. A second order approximation on the stochastic fluctuations for the path integral gives difference equations which represent the time evolution of expectation value and covariance matrix for the stochastic processes. The difference equations explicitly derive Extended Kalman Filter and models on the constrained Ito processes by the identification of the potential function with a penalty or barrier function. The numerical simulations of the constrained stochastic systems show that the potential term can constrain the nonlinear dynamics towards a minimum or a decreasing direction of the potential function.