OpenRaiser/Intern-Atlas huggingface dataset:
A Study of Joint Effect on Denoising Techniques and Visual Cues to Improve Speech Intelligibility in Cochlear Implant Simulation
Venue: arXiv cs.SD 2020
Year: 2020

Speech perception is key to verbal communication. For people with hearing loss, the capability to recognize speech is restricted, particularly in a noisy environment or the situations without visual cues, such as lip-reading unavailable via phone call. This study aimed to understand the improvement of vocoded speech intelligibility in cochlear implant (CI) simulation through two potential methods: Speech Enhancement (SE) and Audiovisual Integration. A fully convolutional neural network (FCN) using an intelligibility-oriented objective function was recently proposed and proven to effectively facilitate the speech intelligibility as an advanced denoising SE approach. Furthermore, audiovisual integration is reported to supply better speech comprehension compared to audio-only information. An experiment was designed to test speech intelligibility using tone-vocoded speech in CI simulation with a group of normal-hearing listeners. Experimental results confirmed the effectiveness of the FCN-based denoising SE and audiovisual integration on vocoded speech. Also, it positively recommended that these two methods could become a blended feature in a CI processor to improve the speech intelligibility for CI users under noisy conditions.
The Approximation Ratio of the 2-Opt Heuristic for the Metric Traveling Salesman Problem
Venue: arXiv cs.DM 2020
Year: 2020

The 2-Opt heuristic is one of the simplest algorithms for finding good solutions to the metric Traveling Salesman Problem. It is the key ingredient to the well-known Lin-Kernighan algorithm and often used in practice. So far, only upper and lower bounds on the approximation ratio of the 2-Opt heuristic for the metric TSP were known. We prove that for the metric TSP with $n$ cities, the approximation ratio of the 2-Opt heuristic is $\sqrt{n/2}$ and that this bound is tight.
At Stability's Edge: How to Adjust Hyperparameters to Preserve Minima Selection in Asynchronous Training of Neural Networks?
Venue: arXiv cs.LG 2020
Year: 2020

Background: Recent developments have made it possible to accelerate neural networks training significantly using large batch sizes and data parallelism. Training in an asynchronous fashion, where delay occurs, can make training even more scalable. However, asynchronous training has its pitfalls, mainly a degradation in generalization, even after convergence of the algorithm. This gap remains not well understood, as theoretical analysis so far mainly focused on the convergence rate of asynchronous methods. Contributions: We examine asynchronous training from the perspective of dynamical stability. We find that the degree of delay interacts with the learning rate, to change the set of minima accessible by an asynchronous stochastic gradient descent algorithm. We derive closed-form rules on how the learning rate could be changed, while keeping the accessible set the same. Specifically, for high delay values, we find that the learning rate should be kept inversely proportional to the delay. We then extend this analysis to include momentum. We find momentum should be either turned off, or modified to improve training stability. We provide empirical experiments to validate our theoretical findings.
Realtime Simulation of Thin-Shell Deformable Materials using CNN-Based Mesh Embedding
Venue: arXiv cs.GR 2020
Year: 2020

We address the problem of accelerating thin-shell deformable object simulations by dimension reduction. We present a new algorithm to embed a high-dimensional configuration space of deformable objects in a low-dimensional feature space, where the configurations of objects and feature points have approximate one-to-one mapping. Our key technique is a graph-based convolutional neural network (CNN) defined on meshes with arbitrary topologies and a new mesh embedding approach based on physics-inspired loss term. We have applied our approach to accelerate high-resolution thin shell simulations corresponding to cloth-like materials, where the configuration space has tens of thousands of degrees of freedom. We show that our physics-inspired embedding approach leads to higher accuracy compared with prior mesh embedding methods. Finally, we show that the temporal evolution of the mesh in the feature space can also be learned using a recurrent neural network (RNN) leading to fully learnable physics simulators. After training our learned simulator runs $500-10000\times$ faster and the accuracy is high enough for robot manipulation tasks.
Margin-Based Generalization Lower Bounds for Boosted Classifiers
Venue: arXiv cs.LG 2020
Year: 2020

Boosting is one of the most successful ideas in machine learning. The most well-accepted explanations for the low generalization error of boosting algorithms such as AdaBoost stem from margin theory. The study of margins in the context of boosting algorithms was initiated by Schapire, Freund, Bartlett and Lee (1998) and has inspired numerous boosting algorithms and generalization bounds. To date, the strongest known generalization (upper bound) is the $k$th margin bound of Gao and Zhou (2013). Despite the numerous generalization upper bounds that have been proved over the last two decades, nothing is known about the tightness of these bounds. In this paper, we give the first margin-based lower bounds on the generalization error of boosted classifiers. Our lower bounds nearly match the $k$th margin bound and thus almost settle the generalization performance of boosted classifiers in terms of margins.
Meta R-CNN : Towards General Solver for Instance-level Few-shot Learning
Venue: arXiv cs.CV 2020
Year: 2020

Resembling the rapid learning capability of human, few-shot learning empowers vision systems to understand new concepts by training with few samples. Leading approaches derived from meta-learning on images with a single visual object. Obfuscated by a complex background and multiple objects in one image, they are hard to promote the research of few-shot object detection/segmentation. In this work, we present a flexible and general methodology to achieve these tasks. Our work extends Faster /Mask R-CNN by proposing meta-learning over RoI (Region-of-Interest) features instead of a full image feature. This simple spirit disentangles multi-object information merged with the background, without bells and whistles, enabling Faster /Mask R-CNN turn into a meta-learner to achieve the tasks. Specifically, we introduce a Predictor-head Remodeling Network (PRN) that shares its main backbone with Faster /Mask R-CNN. PRN receives images containing few-shot objects with their bounding boxes or masks to infer their class attentive vectors. The vectors take channel-wise soft-attention on RoI features, remodeling those R-CNN predictor heads to detect or segment the objects that are consistent with the classes these vectors represent. In our experiments, Meta R-CNN yields the state of the art in few-shot object detection and improves few-shot object segmentation by Mask R-CNN.
Understanding and Stabilizing GANs' Training Dynamics with Control Theory
Venue: arXiv cs.LG 2020
Year: 2020

Generative adversarial networks (GANs) are effective in generating realistic images but the training is often unstable. There are existing efforts that model the training dynamics of GANs in the parameter space but the analysis cannot directly motivate practically effective stabilizing methods. To this end, we present a conceptually novel perspective from control theory to directly model the dynamics of GANs in the function space and provide simple yet effective methods to stabilize GANs' training. We first analyze the training dynamic of a prototypical Dirac GAN and adopt the widely-used closed-loop control (CLC) to improve its stability. We then extend CLC to stabilize the training dynamic of normal GANs, where CLC is implemented as a squared $L2$ regularizer on the output of the discriminator. Empirical results show that our method can effectively stabilize the training and obtain state-of-the-art performance on data generation tasks.
Learning to Align Multi-Camera Domains using Part-Aware Clustering for Unsupervised Video Person Re-Identification
Venue: arXiv cs.CV 2020
Year: 2020

Most video person re-identification (re-ID) methods are mainly based on supervised learning, which requires cross-camera ID labeling. Since the cost of labeling increases dramatically as the number of cameras increases, it is difficult to apply the re-identification algorithm to a large camera network. In this paper, we address the scalability issue by presenting deep representation learning without ID information across multiple cameras. Technically, we train neural networks to generate both ID-discriminative and camera-invariant features. To achieve the ID discrimination ability of the embedding features, we maximize feature distances between different person IDs within a camera by using a metric learning approach. At the same time, considering each camera as a different domain, we apply adversarial learning across multiple camera domains for generating camera-invariant features. We also propose a part-aware adaptation module, which effectively performs multi-camera domain invariant feature learning in different spatial regions. We carry out comprehensive experiments on three public re-ID datasets (i.e., PRID-2011, iLIDS-VID, and MARS). Our method outperforms state-of-the-art methods by a large margin of about 20\% in terms of rank-1 accuracy on the large-scale MARS dataset.
ATOL: Measure Vectorization for Automatic Topologically-Oriented Learning
Venue: arXiv cs.CG 2020
Year: 2020

Robust topological information commonly comes in the form of a set of persistence diagrams, finite measures that are in nature uneasy to affix to generic machine learning frameworks. We introduce a fast, learnt, unsupervised vectorization method for measures in Euclidean spaces and use it for reflecting underlying changes in topological behaviour in machine learning contexts. The algorithm is simple and efficiently discriminates important space regions where meaningful differences to the mean measure arise. It is proven to be able to separate clusters of persistence diagrams. We showcase the strength and robustness of our approach on a number of applications, from emulous and modern graph collections where the method reaches state-of-the-art performance to a geometric synthetic dynamical orbits problem. The proposed methodology comes with a single high level tuning parameter: the total measure encoding budget. We provide a completely open access software.
Citations Driven by Social Connections? A Multi-Layer Representation of Coauthorship Networks
Venue: arXiv cs.SI 2020
Year: 2020

To what extent is the citation rate of new papers influenced by the past social relations of their authors? To answer this question, we present a data-driven analysis of nine different physics journals. Our analysis is based on a two-layer network representation constructed from two large-scale data sets, INSPIREHEP and APS. The social layer contains authors as nodes and coauthorship relations as links. This allows us to quantify the social relations of each author, prior to the publication of a new paper. The publication layer contains papers as nodes and citations between papers as links. This layer allows us to quantify scientific attention as measured by the change of the citation rate over time. We particularly study how this change depends on the social relations of their authors, prior to publication. We find that on average the maximum value of the citation rate is reached sooner for authors who either published more papers, or who had more coauthors in previous papers. We also find that for these authors the decay in the citation rate is faster, meaning that their papers are forgotten sooner.
Towards a Framework for Observational Causality From Time Series: When Shannon Meets Turing
Venue: arXiv cs.IT 2020
Year: 2020

We propose a novel tensor-based formalism for inferring causal structures from time series. An information theoretical analysis of transfer entropy, shows that transfer entropy results from transmission of information over a set of communication channels. Tensors are the mathematical equivalents of these multi-channel causal channels. A multi-channel causal channel is a generalization of a discrete memoryless channel. Investigation of a system comprising three variables shows that in our formalism, bivariate analysis suffices to differentiate between direct and indirect relations. For this to be true, we have to combine the output of multi-channel causal channels with the output of single-channel causal channels. We can understand this result when we consider the role of noise. Subsequent transmission of information over noisy channels can never result in less noisy transmission overall. This implies that a Data Processing Inequality exists for transfer entropy.
Style Transfer by Rigid Alignment in Neural Net Feature Space
Venue: arXiv cs.CV 2020
Year: 2020

Arbitrary style transfer is an important problem in computer vision that aims to transfer style patterns from an arbitrary style image to a given content image. However, current methods either rely on slow iterative optimization or fast pre-determined feature transformation, but at the cost of compromised visual quality of the styled image; especially, distorted content structure. In this work, we present an effective and efficient approach for arbitrary style transfer that seamlessly transfers style patterns as well as keep content structure intact in the styled image. We achieve this by aligning style features to content features using rigid alignment; thus modifying style features, unlike the existing methods that do the opposite. We demonstrate the effectiveness of the proposed approach by generating high-quality stylized images and compare the results with the current state-of-the-art techniques for arbitrary style transfer.
LoGAN: Latent Graph Co-Attention Network for Weakly-Supervised Video Moment Retrieval
Venue: arXiv cs.CV 2020
Year: 2020

The goal of weakly-supervised video moment retrieval is to localize the video segment most relevant to the given natural language query without access to temporal annotations during training. Prior strongly- and weakly-supervised approaches often leverage co-attention mechanisms to learn visual-semantic representations for localization. However, while such approaches tend to focus on identifying relationships between elements of the video and language modalities, there is less emphasis on modeling relational context between video frames given the semantic context of the query. Consequently, the above-mentioned visual-semantic representations, built upon local frame features, do not contain much contextual information. To address this limitation, we propose a Latent Graph Co-Attention Network (LoGAN) that exploits fine-grained frame-by-word interactions to reason about correspondences between all possible pairs of frames, given the semantic context of the query. Comprehensive experiments across two datasets, DiDeMo and Charades-Sta, demonstrate the effectiveness of our proposed latent co-attention model where it outperforms current state-of-the-art (SOTA) weakly-supervised approaches by a significant margin. Notably, it even achieves a 11% improvement to Recall@1 accuracy over strongly-supervised SOTA methods on DiDeMo.
Complexity of Stability
Venue: arXiv cs.CC 2020
Year: 2020

Graph parameters such as the clique number, the chromatic number, and the independence number are central in many areas, ranging from computer networks to linguistics to computational neuroscience to social networks. In particular, the chromatic number of a graph (i.e., the smallest number of colors needed to color all vertices such that no two adjacent vertices are of the same color) can be applied in solving practical tasks as diverse as pattern matching, scheduling jobs to machines, allocating registers in compiler optimization, and even solving Sudoku puzzles. Typically, however, the underlying graphs are subject to (often minor) changes. To make these applications of graph parameters robust, it is important to know which graphs are stable for them in the sense that adding or deleting single edges or vertices does not change them. We initiate the study of stability of graphs for such parameters in terms of their computational complexity. We show that, for various central graph parameters, the problem of determining whether or not a given graph is stable is complete for Θ_2^p, a well-known complexity class in the second level of the polynomial hierarchy, which is also known as "parallel access to NP."
Graph search via star sampling with and without replacement
Venue: arXiv cs.NI 2020
Year: 2020

Star sampling (SS) is a random sampling procedure on a graph wherein each sample consists of a randomly selected vertex (the star center) and its (one-hop) neighbors (the star points). We consider the use of SS to find any member of a target set of vertices in a graph, where the figure of merit (cost) is either the expected number of samples (unit cost) or the expected number of star centers plus star points (linear cost) until a vertex in the target set is encountered, either as a star center or as a star point. We analyze these two performance measures on three related star sampling paradigms: SS with replacement (SSR), SS without center replacement (SSC), and SS without star replacement (SSS). Exact and approximate expressions are derived for the expected unit and linear costs of SSR, SSC, and SSS on Erdős-Rényi (ER) random graphs. The approximations are seen to be accurate. SSC/SSS are notably better than SSR under unit cost for low-density ER graphs, while SSS is notably better than SSR/SSC under linear cost for low- to moderate-density ER graphs. Simulations on twelve "real-world" graphs shows the cost approximations to be of variable quality: the SSR and SSC approximations are uniformly accurate, while the SSS approximation, derived for an ER graph, is of variable accuracy.
Estimating the Percolation Centrality of Large Networks through Pseudo-dimension Theory
Venue: arXiv cs.DS 2020
Year: 2020

In this work we investigate the problem of estimating the percolation centrality of every vertex in a graph. This centrality measure quantifies the importance of each vertex in a graph going through a contagious process. It is an open problem whether the percolation centrality can be computed in $\mathcal{O}(n^{3-c})$ time, for any constant $c>0$. In this paper we present a $\mathcal{O}(m \log^2 n)$ randomized approximation algorithm for the percolation centrality for every vertex of $G$, generalizing techniques developed by Riondato, Upfal e Kornaropoulos (this complexity is reduced to $\mathcal{O}((m+n) \log n)$ for unweighted graphs). The estimation obtained by the algorithm is within $ε$ of the exact value with probability $1-δ$, for {\it fixed} constants $0 < ε,δ\leq 1$. In fact, we show in our experimental analysis that in the case of real world complex networks, the output produced by our algorithm is significantly closer to the exact values than its guarantee in terms of theoretical worst case analysis.
Training Generative Networks with general Optimal Transport distances
Venue: arXiv cs.LG 2020
Year: 2020

We propose a new algorithm that uses an auxiliary neural network to express the potential of the optimal transport map between two data distributions. In the sequel, we use the aforementioned map to train generative networks. Unlike WGANs, where the Euclidean distance is ${\it implicitly}$ used, this new method allows to ${\it explicitly}$ use ${\it any}$ transportation cost function that can be chosen to match the problem at hand. For example, it allows to use the squared distance as a transportation cost function, giving rise to the Wasserstein-2 metric for probability distributions, which results in fast and stable gradient descends. It also allows to use image centered distances, like the structure similarity index, with notable differences in the results.
Better Document-Level Machine Translation with Bayes' Rule
Venue: arXiv cs.CL 2020
Year: 2020

We show that Bayes' rule provides an effective mechanism for creating document translation models that can be learned from only parallel sentences and monolingual documents---a compelling benefit as parallel documents are not always available. In our formulation, the posterior probability of a candidate translation is the product of the unconditional (prior) probability of the candidate output document and the "reverse translation probability" of translating the candidate output back into the source language. Our proposed model uses a powerful autoregressive language model as the prior on target language documents, but it assumes that each sentence is translated independently from the target to the source language. Crucially, at test time, when a source document is observed, the document language model prior induces dependencies between the translations of the source sentences in the posterior. The model's independence assumption not only enables efficient use of available data, but it additionally admits a practical left-to-right beam-search algorithm for carrying out inference. Experiments show that our model benefits from using cross-sentence context in the language model, and it outperforms existing document translation approaches.
Re-balancing Variational Autoencoder Loss for Molecule Sequence Generation
Venue: arXiv cs.LG 2020
Year: 2020

Molecule generation is to design new molecules with specific chemical properties and further to optimize the desired chemical properties. Following previous work, we encode molecules into continuous vectors in the latent space and then decode the vectors into molecules under the variational autoencoder (VAE) framework. We investigate the posterior collapse problem of current RNN-based VAEs for molecule sequence generation. For the first time, we find that underestimated reconstruction loss leads to posterior collapse, and provide both theoretical and experimental evidence. We propose an effective and efficient solution to fix the problem and avoid posterior collapse. Without bells and whistles, our method achieves SOTA reconstruction accuracy and competitive validity on the ZINC 250K dataset. When generating 10,000 unique valid SMILES from random prior sampling, it costs JT-VAE1450s while our method only needs 9s. Our implementation is at https://github.com/chaoyan1037/Re-balanced-VAE.
A Deep Factorization of Style and Structure in Fonts
Venue: arXiv cs.LG 2020
Year: 2020

We propose a deep factorization model for typographic analysis that disentangles content from style. Specifically, a variational inference procedure factors each training glyph into the combination of a character-specific content embedding and a latent font-specific style variable. The underlying generative model combines these factors through an asymmetric transpose convolutional process to generate the image of the glyph itself. When trained on corpora of fonts, our model learns a manifold over font styles that can be used to analyze or reconstruct new, unseen fonts. On the task of reconstructing missing glyphs from an unknown font given only a small number of observations, our model outperforms both a strong nearest neighbors baseline and a state-of-the-art discriminative model from prior work.