OpenRaiser/Intern-Atlas huggingface dataset:
Theory III: Dynamics and Generalization in Deep Networks
Venue: arXiv cs.LG 2020
Year: 2020

The key to generalization is controlling the complexity of the network. However, there is no obvious control of complexity -- such as an explicit regularization term -- in the training of deep networks for classification. We will show that a classical form of norm control -- but kind of hidden -- is present in deep networks trained with gradient descent techniques on exponential-type losses. In particular, gradient descent induces a dynamics of the normalized weights which converge for $t \to \infty$ to an equilibrium which corresponds to a minimum norm (or maximum margin) solution. For sufficiently large but finite $ρ$ -- and thus finite $t$ -- the dynamics converges to one of several margin maximizers, with the margin monotonically increasing towards a limit stationary point of the flow. In the usual case of stochastic gradient descent, most of the stationary points are likely to be convex minima corresponding to a constrained minimizer -- the network with normalized weights-- which corresponds to vanishing regularization. The solution has zero generalization gap, for fixed architecture, asymptotically for $N \to \infty$, where $N$ is the number of training examples. Our approach extends some of the original results of Srebro from linear networks to deep networks and provides a new perspective on the implicit bias of gradient descent. We believe that the elusive complexity control we describe is responsible for the puzzling empirical finding of good predictive performance by deep networks, despite overparametrization.
Stable Roommates with Narcissistic, Single-Peaked, and Single-Crossing Preferences
Venue: arXiv cs.GT 2020
Year: 2020

The classical Stable Roommates problem is to decide whether there exists a matching of an even number of agents such that no two agents which are not matched to each other would prefer to be with each other rather than with their respectively assigned partners. We investigate Stable Roommates with complete (i.e., every agent can be matched with any other agent) or incomplete preferences, with ties (i.e., two agents are considered of equal value to some agent) or without ties. It is known that in general allowing ties makes the problem NP-complete. We provide algorithms for Stable Roommates that are, compared to those in the literature, more efficient when the input preferences are complete and have some structural property, such as being narcissistic, single-peaked, and single-crossing. However, when the preferences are incomplete and have ties, we show that being single-peaked and single-crossing does not reduce the computational complexity--Stable Roommates remains NP-complete.
The practice of self-citations: a longitudinal study
Venue: arXiv cs.DL 2020
Year: 2020

In this article, we discuss the outcomes of an experiment where we analysed whether and to what extent the introduction, in 2012, of the new research assessment exercise in Italy (a.k.a. Italian Scientific Habilitation) affected self-citation behaviours in the Italian research community. The Italian Scientific Habilitation attests to the scientific maturity of researchers and in Italy, as in many other countries, is a requirement for accessing to a professorship. To this end, we obtained from ScienceDirect 35,673 articles published from 1957 and 2016 by the participants to the 2012 Italian Scientific Habilitation, that resulted in the extraction of 1,379,050 citations retrieved through Semantic Publishing technologies. Our analysis showed an overall increment in author self-citations (i.e. where the citing article and the cited article share at least one author) in several of the 24 academic disciplines considered. However, we depicted a stronger causal relation between such increment and the rules introduced by the 2012 Italian Scientific Habilitation in 10 out of 24 disciplines analysed.
No-regret Exploration in Contextual Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

We consider the recently proposed reinforcement learning (RL) framework of Contextual Markov Decision Processes (CMDP), where the agent interacts with a (potentially adversarial) sequence of episodic tabular MDPs. In addition, a context vector determining the MDP parameters is available to the agent at the start of each episode, thereby allowing it to learn a context-dependent near-optimal policy. In this paper, we propose a no-regret online RL algorithm in the setting where the MDP parameters are obtained from the context using generalized linear mappings (GLMs). We propose and analyze optimistic and randomized exploration methods which make (time and space) efficient online updates. The GLM based model subsumes previous work in this area and also improves previous known bounds in the special case where the contextual mapping is linear. In addition, we demonstrate a generic template to derive confidence sets using an online learning oracle and give a lower bound for the setting.
On-Line Balancing of Random Inputs
Venue: arXiv cs.DS 2020
Year: 2020

We consider an online vector balancing game where vectors $v_t$, chosen uniformly at random in $\{-1,+1\}^n$, arrive over time and a sign $x_t \in \{-1,+1\}$ must be picked immediately upon the arrival of $v_t$. The goal is to minimize the $L^\infty$ norm of the signed sum $\sum_t x_t v_t$. We give an online strategy for picking the signs $x_t$ that has value $O(n^{1/2})$ with high probability. Up to constants, this is the best possible even when the vectors are given in advance.
Domain adaptation for holistic skin detection
Venue: arXiv cs.CV 2020
Year: 2020

Human skin detection in images is a widely studied topic of Computer Vision for which it is commonly accepted that analysis of pixel color or local patches may suffice. This is because skin regions appear to be relatively uniform and many argue that there is a small chromatic variation among different samples. However, we found that there are strong biases in the datasets commonly used to train or tune skin detection methods. Furthermore, the lack of contextual information may hinder the performance of local approaches. In this paper we present a comprehensive evaluation of holistic and local Convolutional Neural Network (CNN) approaches on in-domain and cross-domain experiments and compare with state-of-the-art pixel-based approaches. We also propose a combination of inductive transfer learning and unsupervised domain adaptation methods, which are evaluated on different domains under several amounts of labelled data availability. We show a clear superiority of CNN over pixel-based approaches even without labelled training samples on the target domain. Furthermore, we provide experimental support for the counter-intuitive superiority of holistic over local approaches for human skin detection.
Online Observability of Boolean Control Networks
Venue: arXiv cs.SY 2020
Year: 2020

Observabililty is an important topic of Boolean control networks (BCNs). In this paper, we propose a new type of observability named online observability to present the sufficient and necessary condition of determining the initial states of BCNs, when their initial states cannot be reset. And we design an algorithm to decide whether a BCN has the online observability. Moreover, we prove that a BCN is identifiable iff it satisfies controllability and the online observability, which reveals the essence of identification problem of BCNs.
Software-defined Design Space Exploration for an Efficient DNN Accelerator Architecture
Venue: arXiv cs.DC 2020
Year: 2020

Deep neural networks (DNNs) have been shown to outperform conventional machine learning algorithms across a wide range of applications, e.g., image recognition, object detection, robotics, and natural language processing. However, the high computational complexity of DNNs often necessitates extremely fast and efficient hardware. The problem gets worse as the size of neural networks grows exponentially. As a result, customized hardware accelerators have been developed to accelerate DNN processing without sacrificing model accuracy. However, previous accelerator design studies have not fully considered the characteristics of the target applications, which may lead to sub-optimal architecture designs. On the other hand, new DNN models have been developed for better accuracy, but their compatibility with the underlying hardware accelerator is often overlooked. In this article, we propose an application-driven framework for architectural design space exploration of DNN accelerators. This framework is based on a hardware analytical model of individual DNN operations. It models the accelerator design task as a multi-dimensional optimization problem. We demonstrate that it can be efficaciously used in application-driven accelerator architecture design. Given a target DNN, the framework can generate efficient accelerator design solutions with optimized performance and area. Furthermore, we explore the opportunity to use the framework for accelerator configuration optimization under simultaneous diverse DNN applications. The framework is also capable of improving neural network models to best fit the underlying hardware resources.
Lemotif: An Affective Visual Journal Using Deep Neural Networks
Venue: arXiv cs.HC 2020
Year: 2020

We present Lemotif, an integrated natural language processing and image generation system that uses machine learning to (1) parse a text-based input journal entry describing the user's day for salient themes and emotions and (2) visualize the detected themes and emotions in creative and appealing image motifs. Synthesizing approaches from artificial intelligence and psychology, Lemotif acts as an affective visual journal, encouraging users to regularly write and reflect on their daily experiences through visual reinforcement. By making patterns in emotions and their sources more apparent, Lemotif aims to help users better understand their emotional lives, identify opportunities for action, and track the effectiveness of behavioral changes over time. We verify via human studies that prospective users prefer motifs generated by Lemotif over corresponding baselines, find the motifs representative of their journal entries, and think they would be more likely to journal regularly using a Lemotif-based app.
Truly Proximal Policy Optimization
Venue: arXiv cs.LG 2020
Year: 2020

Proximal policy optimization (PPO) is one of the most successful deep reinforcement-learning methods, achieving state-of-the-art performance across a wide range of challenging tasks. However, its optimization behavior is still far from being fully understood. In this paper, we show that PPO could neither strictly restrict the likelihood ratio as it attempts to do nor enforce a well-defined trust region constraint, which means that it may still suffer from the risk of performance instability. To address this issue, we present an enhanced PPO method, named Truly PPO. Two critical improvements are made in our method: 1) it adopts a new clipping function to support a rollback behavior to restrict the difference between the new policy and the old one; 2) the triggering condition for clipping is replaced with a trust region-based one, such that optimizing the resulted surrogate objective function provides guaranteed monotonic improvement of the ultimate policy performance. It seems, by adhering more truly to making the algorithm proximal - confining the policy within the trust region, the new algorithm improves the original PPO on both sample efficiency and performance.
Feasible Region: an Actuation-Aware Extension of the Support Region
Venue: arXiv cs.RO 2020
Year: 2020

In legged locomotion the projection of the robot Center of Mass (CoM) being inside the convex hull of the contact points is a commonly accepted sufficient condition to achieve static balancing. However, some of these configurations cannot be realized because the joint torques required to sustain them would be above their limits (actuation limits). In this manuscript we rule out such configurations and define the Feasible Region, a revisited support region that guarantees both global static stability in the sense of tipover and slippage avoidance and of existence of a set of joint-torques that are able to sustain the robot body weight. We show that the feasible region can be employed for the selection of feasible footholds and CoM trajectories to achieve static locomotion on rough terrains, also in presence of load intensive tasks. Key results of our approach include the efficiency in the computation of the feasible region thanks to an Iterative Projection algorithm. This allowed us to carry out successful experiments on the HyQ robot, that was able to negotiate obstacles of moderate dimensions while carrying an extra 10 kg payload.
Accurate 3D Face Reconstruction with Weakly-Supervised Learning: From Single Image to Image Set
Venue: arXiv cs.CV 2020
Year: 2020

Recently, deep learning based 3D face reconstruction methods have shown promising results in both quality and efficiency.However, training deep neural networks typically requires a large volume of data, whereas face images with ground-truth 3D face shapes are scarce. In this paper, we propose a novel deep 3D face reconstruction approach that 1) leverages a robust, hybrid loss function for weakly-supervised learning which takes into account both low-level and perception-level information for supervision, and 2) performs multi-image face reconstruction by exploiting complementary information from different images for shape aggregation. Our method is fast, accurate, and robust to occlusion and large pose. We provide comprehensive experiments on three datasets, systematically comparing our method with fifteen recent methods and demonstrating its state-of-the-art performance.
Equivariant Entity-Relationship Networks
Venue: arXiv cs.LG 2020
Year: 2020

The relational model is a ubiquitous representation of big-data, in part due to its extensive use in databases. In this paper, we propose the Equivariant Entity-Relationship Network (EERN), which is a Multilayer Perceptron equivariant to the symmetry transformations of the Entity-Relationship model. To this end, we identify the most expressive family of linear maps that are exactly equivariant to entity relationship symmetries, and further show that they subsume recently introduced equivariant maps for sets, exchangeable tensors, and graphs. The proposed feed-forward layer has linear complexity in the data and can be used for both inductive and transductive reasoning about relational databases, including database embedding, and the prediction of missing records. This provides a principled theoretical foundation for the application of deep learning to one of the most abundant forms of data. Empirically, EERN outperforms different variants of coupled matrix tensor factorization in both synthetic and real-data experiments.
Generative Adversarial Minority Oversampling
Venue: arXiv cs.CV 2020
Year: 2020

Class imbalance is a long-standing problem relevant to a number of real-world applications of deep learning. Oversampling techniques, which are effective for handling class imbalance in classical learning systems, can not be directly applied to end-to-end deep learning systems. We propose a three-player adversarial game between a convex generator, a multi-class classifier network, and a real/fake discriminator to perform oversampling in deep learning systems. The convex generator generates new samples from the minority classes as convex combinations of existing instances, aiming to fool both the discriminator as well as the classifier into misclassifying the generated samples. Consequently, the artificial samples are generated at critical locations near the peripheries of the classes. This, in turn, adjusts the classifier induced boundaries in a way which is more likely to reduce misclassification from the minority classes. Extensive experiments on multiple class imbalanced image datasets establish the efficacy of our proposal.
A Conceptual Bio-Inspired Framework for the Evolution of Artificial General Intelligence
Venue: arXiv cs.NE 2020
Year: 2020

In this work, a conceptual bio-inspired parallel and distributed learning framework for the emergence of general intelligence is proposed, where agents evolve through environmental rewards and learn throughout their lifetime without supervision, i.e., self-learning through embodiment. The chosen control mechanism for agents is a biologically plausible neuron model based on spiking neural networks. Network topologies become more complex through evolution, i.e., the topology is not fixed, while the synaptic weights of the networks cannot be inherited, i.e., newborn brains are not trained and have no innate knowledge of the environment. What is subject to the evolutionary process is the network topology, the type of neurons, and the type of learning. This process ensures that controllers that are passed through the generations have the intrinsic ability to learn and adapt during their lifetime in mutable environments. We envision that the described approach may lead to the emergence of the simplest form of artificial general intelligence.
Second- and Third-Order Asymptotics of the Continuous-Time Poisson Channel
Venue: arXiv cs.IT 2020
Year: 2020

The paper derives the optimal second-order coding rate for the continuous-time Poisson channel. We also obtain bounds on the third-order coding rate. This is the first instance of a second-order result for a continuous-time channel. The converse proof hinges on a novel construction of an output distribution induced by Wyner's discretized channel and the construction of an appropriate $ε$-net of the input probability simplex. While the achievability proof follows the general program to prove the third-order term for non-singular discrete memoryless channels put forth by Polyanskiy, several non-standard techniques -- such as new definitions and bounds on the probabilities of typical sets using logarithmic Sobolev inequalities -- are employed to handle the continuous nature of the channel.
Micro-Batch Training with Batch-Channel Normalization and Weight Standardization
Venue: arXiv cs.CV 2020
Year: 2020

Batch Normalization (BN) has become an out-of-box technique to improve deep network training. However, its effectiveness is limited for micro-batch training, i.e., each GPU typically has only 1-2 images for training, which is inevitable for many computer vision tasks, e.g., object detection and semantic segmentation, constrained by memory consumption. To address this issue, we propose Weight Standardization (WS) and Batch-Channel Normalization (BCN) to bring two success factors of BN into micro-batch training: 1) the smoothing effects on the loss landscape and 2) the ability to avoid harmful elimination singularities along the training trajectory. WS standardizes the weights in convolutional layers to smooth the loss landscape by reducing the Lipschitz constants of the loss and the gradients; BCN combines batch and channel normalizations and leverages estimated statistics of the activations in convolutional layers to keep networks away from elimination singularities. We validate WS and BCN on comprehensive computer vision tasks, including image classification, object detection, instance segmentation, video recognition and semantic segmentation. All experimental results consistently show that WS and BCN improve micro-batch training significantly. Moreover, using WS and BCN with micro-batch training is even able to match or outperform the performances of BN with large-batch training.
Computing the Homology of Semialgebraic Sets. II: General formulas
Venue: arXiv cs.CG 2020
Year: 2020

We describe and analyze a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of semialgebraic sets given by Boolean formulas. The algorithm works in weak exponential time. This means that outside a subset of data having exponentially small measure, the cost of the algorithm is single exponential in the size of the data. This extends the previous work of the authors in arXiv:1807.06435 to arbitrary semialgebraic sets. All previous algorithms proposed for this problem have doubly exponential complexity.
A Silver Standard Corpus of Human Phenotype-Gene Relations
Venue: arXiv cs.CL 2020
Year: 2020

Human phenotype-gene relations are fundamental to fully understand the origin of some phenotypic abnormalities and their associated diseases. Biomedical literature is the most comprehensive source of these relations, however, we need Relation Extraction tools to automatically recognize them. Most of these tools require an annotated corpus and to the best of our knowledge, there is no corpus available annotated with human phenotype-gene relations. This paper presents the Phenotype-Gene Relations (PGR) corpus, a silver standard corpus of human phenotype and gene annotations and their relations. The corpus consists of 1712 abstracts, 5676 human phenotype annotations, 13835 gene annotations, and 4283 relations. We generated this corpus using Named-Entity Recognition tools, whose results were partially evaluated by eight curators, obtaining a precision of 87.01%. By using the corpus we were able to obtain promising results with two state-of-the-art deep learning tools, namely 78.05% of precision. The PGR corpus was made publicly available to the research community.
SuSi: Supervised Self-Organizing Maps for Regression and Classification in Python
Venue: arXiv cs.LG 2020
Year: 2020

In many research fields, the sizes of the existing datasets vary widely. Hence, there is a need for machine learning techniques which are well-suited for these different datasets. One possible technique is the self-organizing map (SOM), a type of artificial neural network which is, so far, weakly represented in the field of machine learning. The SOM's unique characteristic is the neighborhood relationship of the output neurons. This relationship improves the ability of generalization on small datasets. SOMs are mostly applied in unsupervised learning and few studies focus on using SOMs as supervised learning approach. Furthermore, no appropriate SOM package is available with respect to machine learning standards and in the widely used programming language Python. In this paper, we introduce the freely available Supervised Self-organizing maps (SuSi) Python package which performs supervised regression and classification. The implementation of SuSi is described with respect to the underlying mathematics. Then, we present first evaluations of the SOM for regression and classification datasets from two different domains of geospatial image analysis. Despite the early stage of its development, the SuSi framework performs well and is characterized by only small performance differences between the training and the test datasets. A comparison of the SuSi framework with existing Python and R packages demonstrates the importance of the SuSi framework. In future work, the SuSi framework will be extended, optimized and upgraded e.g. with tools to better understand and visualize the input data as well as the handling of missing and incomplete data.