OpenRaiser/Intern-Atlas huggingface dataset:
Mode matching in GANs through latent space learning and inversion
Venue: arXiv cs.CV 2019
Year: 2019

Generative adversarial networks (GANs) have shown remarkable success in generation of unstructured data, such as, natural images. However, discovery and separation of modes in the generated space, essential for several tasks beyond naive data generation, is still a challenge. In this paper, we address the problem of imposing desired modal properties on the generated space using a latent distribution, engineered in accordance with the modal properties of the true data distribution. This is achieved by training a latent space inversion network in tandem with the generative network using a divergence loss. The latent space is made to follow a continuous multimodal distribution generated by reparameterization of a pair of continuous and discrete random variables. In addition, the modal priors of the latent distribution are learned to match with the true data distribution using minimal-supervision with negligible increment in number of learnable parameters. We validate our method on multiple tasks such as mode separation, conditional generation, and attribute discovery on multiple real world image datasets and demonstrate its efficacy over other state-of-the-art methods.
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
Venue: arXiv cs.DS 2019
Year: 2019

A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph $G$ has a $b$-coloring with $k$ colors. The $b$-chromatic number of a graph $G$, denoted by $χ_b(G)$, is the maximum number $k$ such that $G$ admits a $b$-coloring with $k$ colors. We consider the complexity of the b-Coloring problem, whenever the value of $k$ is close to one of two upper bounds on $χ_b(G)$: The maximum degree $Δ(G)$ plus one, and the $m$-degree, denoted by $m(G)$, which is defined as the maximum number $i$ such that $G$ has $i$ vertices of degree at least $i-1$. We obtain a dichotomy result stating that for fixed $k \in \{Δ(G) + 1 - p, m(G) - p\}$, the problem is polynomial-time solvable whenever $p \in \{0, 1\}$ and, even when $k = 3$, it is NP-complete whenever $p \ge 2$. We furthermore consider parameterizations of the b-Coloring problem that involve the maximum degree $Δ(G)$ of the input graph $G$ and give two FPT-algorithms. First, we show that deciding whether a graph $G$ has a $b$-coloring with $m(G)$ colors is FPT parameterized by $Δ(G)$. Second, we show that b-Coloring is FPT parameterized by $Δ(G) + \ell_k(G)$, where $\ell_k(G)$ denotes the number of vertices of degree at least $k$.
Densely Connected Attention Propagation for Reading Comprehension
Venue: arXiv cs.CL 2019
Year: 2019

We propose DecaProp (Densely Connected Attention Propagation), a new densely connected neural architecture for reading comprehension (RC). There are two distinct characteristics of our model. Firstly, our model densely connects all pairwise layers of the network, modeling relationships between passage and query across all hierarchical levels. Secondly, the dense connectors in our network are learned via attention instead of standard residual skip-connectors. To this end, we propose novel Bidirectional Attention Connectors (BAC) for efficiently forging connections throughout the network. We conduct extensive experiments on four challenging RC benchmarks. Our proposed approach achieves state-of-the-art results on all four, outperforming existing baselines by up to $2.6\%-14.2\%$ in absolute F1 score.
Skeleton-Based Action Recognition with Synchronous Local and Non-local Spatio-temporal Learning and Frequency Attention
Venue: arXiv cs.CV 2019
Year: 2019

Benefiting from its succinctness and robustness, skeleton-based action recognition has recently attracted much attention. Most existing methods utilize local networks (e.g., recurrent, convolutional, and graph convolutional networks) to extract spatio-temporal dynamics hierarchically. As a consequence, the local and non-local dependencies, which contain more details and semantics respectively, are asynchronously captured in different level of layers. Moreover, existing methods are limited to the spatio-temporal domain and ignore information in the frequency domain. To better extract synchronous detailed and semantic information from multi-domains, we propose a residual frequency attention (rFA) block to focus on discriminative patterns in the frequency domain, and a synchronous local and non-local (SLnL) block to simultaneously capture the details and semantics in the spatio-temporal domain. Besides, a soft-margin focal loss (SMFL) is proposed to optimize the learning whole process, which automatically conducts data selection and encourages intrinsic margins in classifiers. Our approach significantly outperforms other state-of-the-art methods on several large-scale datasets.
The Method of Multimodal MRI Brain Image Segmentation Based on Differential Geometric Features
Venue: arXiv cs.CV 2019
Year: 2019

Accurate segmentation of brain tissue in magnetic resonance images (MRI) is a diffcult task due to different types of brain abnormalities. Using information and features from multimodal MRI including T1, T1-weighted inversion recovery (T1-IR) and T2-FLAIR and differential geometric features including the Jacobian determinant(JD) and the curl vector(CV) derived from T1 modality can result in a more accurate analysis of brain images. In this paper, we use the differential geometric information including JD and CV as image characteristics to measure the differences between different MRI images, which represent local size changes and local rotations of the brain image, and we can use them as one CNN channel with other three modalities (T1-weighted, T1-IR and T2-FLAIR) to get more accurate results of brain segmentation. We test this method on two datasets including IBSR dataset and MRBrainS datasets based on the deep voxelwise residual network, namely VoxResNet, and obtain excellent improvement over single modality or three modalities and increases average DSC(Cerebrospinal Fluid (CSF), Gray Matter (GM) and White Matter (WM)) by about 1.5% on the well-known MRBrainS18 dataset and about 2.5% on the IBSR dataset. Moreover, we discuss that one modality combined with its JD or CV information can replace the segmentation effect of three modalities, which can provide medical conveniences for doctor to diagnose because only to extract T1-modality MRI image of patients. Finally, we also compare the segmentation performance of our method in two networks, VoxResNet and U-Net network. The results show VoxResNet has a better performance than U-Net network with our method in brain MRI segmentation. We believe the proposed method can advance the performance in brain segmentation and clinical diagnosis.
On SDN-Enabled Online and Dynamic Bandwidth Allocation for Stream Analytics
Venue: arXiv cs.NI 2019
Year: 2019

Data communication in cloud-based distributed stream data analytics often involves a collection of parallel and pipelined TCP flows. As the standard TCP congestion control mechanism is designed for achieving "fairness" among competing flows and is agnostic to the application layer contexts, the bandwidth allocation among a set of TCP flows traversing bottleneck links often leads to sub-optimal application-layer performance measures, e.g., stream processing throughput or average tuple complete latency. Motivated by this and enabled by the rapid development of the Software-Defined Networking (SDN) techniques, in this paper, we re-investigate the design space of the bandwidth allocation problem and propose a cross-layer framework which utilizes the additional information obtained from the application layer and provides on-the-fly and dynamic bandwidth adjustment algorithms for helping the stream analytics applications achieving better performance during the runtime. We implement a prototype cross-layer bandwidth allocation framework based on a popular open-source distributed stream processing platform, Apache Storm, together with the OpenDaylight controller, and carry out extensive experiments with real-world analytical workloads on top of a local cluster consisting of 10 workstations interconnected by a SDN-enabled switch. The experiment results clearly validate the effectiveness and efficiency of our proposed framework and algorithms.
Adapting multi-armed bandits policies to contextual bandits scenarios
Venue: arXiv cs.LG 2019
Year: 2019

This work explores adaptations of successful multi-armed bandits policies to the online contextual bandits scenario with binary rewards using binary classification algorithms such as logistic regression as black-box oracles. Some of these adaptations are achieved through bootstrapping or approximate bootstrapping, while others rely on other forms of randomness, resulting in more scalable approaches than previous works, and the ability to work with any type of classification algorithm. In particular, the Adaptive-Greedy algorithm shows a lot of promise, in many cases achieving better performance than upper confidence bound and Thompson sampling strategies, at the expense of more hyperparameters to tune.
Fast Matrix Factorization with Non-Uniform Weights on Missing Data
Venue: arXiv cs.IR 2019
Year: 2019

Matrix factorization (MF) has been widely used to discover the low-rank structure and to predict the missing entries of data matrix. In many real-world learning systems, the data matrix can be very high-dimensional but sparse. This poses an imbalanced learning problem, since the scale of missing entries is usually much larger than that of observed entries, but they cannot be ignored due to the valuable negative signal. For efficiency concern, existing work typically applies a uniform weight on missing entries to allow a fast learning algorithm. However, this simplification will decrease modeling fidelity, resulting in suboptimal performance for downstream applications. In this work, we weight the missing data non-uniformly, and more generically, we allow any weighting strategy on the missing data. To address the efficiency challenge, we propose a fast learning method, for which the time complexity is determined by the number of observed entries in the data matrix, rather than the matrix size. The key idea is two-fold: 1) we apply truncated SVD on the weight matrix to get a more compact representation of the weights, and 2) we learn MF parameters with element-wise alternating least squares (eALS) and memorize the key intermediate variables to avoid repeating computations that are unnecessary. We conduct extensive experiments on two recommendation benchmarks, demonstrating the correctness, efficiency, and effectiveness of our fast eALS method.
Learning Groupwise Multivariate Scoring Functions Using Deep Neural Networks
Venue: arXiv cs.IR 2019
Year: 2019

While in a classification or a regression setting a label or a value is assigned to each individual document, in a ranking setting we determine the relevance ordering of the entire input document list. This difference leads to the notion of relative relevance between documents in ranking. The majority of the existing learning-to-rank algorithms model such relativity at the loss level using pairwise or listwise loss functions. However, they are restricted to univariate scoring functions, i.e., the relevance score of a document is computed based on the document itself, regardless of other documents in the list. To overcome this limitation, we propose a new framework for multivariate scoring functions, in which the relevance score of a document is determined jointly by multiple documents in the list. We refer to this framework as GSFs -- groupwise scoring functions. We learn GSFs with a deep neural network architecture, and demonstrate that several representative learning-to-rank algorithms can be modeled as special cases in our framework. We conduct evaluation using click logs from one of the largest commercial email search engines, as well as a public benchmark dataset. In both cases, GSFs lead to significant performance improvements, especially in the presence of sparse textual features.
Agent Embeddings: A Latent Representation for Pole-Balancing Networks
Venue: arXiv cs.LG 2019
Year: 2019

We show that it is possible to reduce a high-dimensional object like a neural network agent into a low-dimensional vector representation with semantic meaning that we call agent embeddings, akin to word or face embeddings. This can be done by collecting examples of existing networks, vectorizing their weights, and then learning a generative model over the weight space in a supervised fashion. We investigate a pole-balancing task, Cart-Pole, as a case study and show that multiple new pole-balancing networks can be generated from their agent embeddings without direct access to training data from the Cart-Pole simulator. In general, the learned embedding space is helpful for mapping out the space of solutions for a given task. We observe in the case of Cart-Pole the surprising finding that good agents make different decisions despite learning similar representations, whereas bad agents make similar (bad) decisions while learning dissimilar representations. Linearly interpolating between the latent embeddings for a good agent and a bad agent yields an agent embedding that generates a network with intermediate performance, where the performance can be tuned according to the coefficient of interpolation. Linear extrapolation in the latent space also results in performance boosts, up to a point.
Approximate Curve-Restricted Simplification of Polygonal Curves
Venue: arXiv cs.CG 2019
Year: 2019

The goal in the min-\# curve simplification problem is to reduce the number of the vertices of a polygonal curve without changing its shape significantly. We study curve-restricted min-\# simplification of polygonal curves, in which the vertices of the simplified curve can be placed on any point of the input curve, provided that they respect the order along that curve. For local directed Hausdorff distance from the input to the simplified curve in $\mathbb{R}^2$, we present an approximation algorithm that computes a curve whose number of links is at most twice the minimum possible.
Joint Probability Distribution of Prediction Errors of ARIMA
Venue: arXiv cs.SY 2019
Year: 2019

Producing probabilistic guarantee for several steps of a predicted signal follow a temporal logic defined behavior has its rising importance in monitoring. In this paper, we derive a method to compute the joint probability distribution of prediction errors of multiple steps based on Autoregressive Integrated Moving Average(ARIMA) model. We cover scenarios in stationary process and intrinsically stationary process for univariate and multivariate.
Deep-learning the Latent Space of Light Transport
Venue: arXiv cs.GR 2019
Year: 2019

We suggest a method to directly deep-learn light transport, i. e., the mapping from a 3D geometry-illumination-material configuration to a shaded 2D image. While many previous learning methods have employed 2D convolutional neural networks applied to images, we show for the first time that light transport can be learned directly in 3D. The benefit of 3D over 2D is, that the former can also correctly capture illumination effects related to occluded and/or semi-transparent geometry. To learn 3D light transport, we represent the 3D scene as an unstructured 3D point cloud, which is later, during rendering, projected to the 2D output image. Thus, we suggest a two-stage operator comprising of a 3D network that first transforms the point cloud into a latent representation, which is later on projected to the 2D output image using a dedicated 3D-2D network in a second step. We will show that our approach results in improved quality in terms of temporal coherence while retaining most of the computational efficiency of common 2D methods. As a consequence, the proposed two stage-operator serves as a valuable extension to modern deferred shading approaches.
Finite degree clones are undecidable
Venue: arXiv cs.LO 2019
Year: 2019

A clone of functions on a finite domain determines and is determined by its system of invariant relations (=predicates). When a clone is determined by a finite number of relations, we say that the clone is of finite degree. For each Minsky Machine $\mathcal{M}$ we associate a finitely generated clone $\mathcal{C}$ such that $\mathcal{C}$ has finite degree if and only if $\mathcal{M}$ halts, thus proving that deciding whether a given clone has finite degree is impossible.
Exploring RNN-Transducer for Chinese Speech Recognition
Venue: arXiv cs.CL 2019
Year: 2019

End-to-end approaches have drawn much attention recently for significantly simplifying the construction of an automatic speech recognition (ASR) system. RNN transducer (RNN-T) is one of the popular end-to-end methods. Previous studies have shown that RNN-T is difficult to train and a very complex training process is needed for a reasonable performance. In this paper, we explore RNN-T for a Chinese large vocabulary continuous speech recognition (LVCSR) task and aim to simplify the training process while maintaining performance. First, a new strategy of learning rate decay is proposed to accelerate the model convergence. Second, we find that adding convolutional layers at the beginning of the network and using ordered data can discard the pre-training process of the encoder without loss of performance. Besides, we design experiments to find a balance among the usage of GPU memory, training circle and model performance. Finally, we achieve 16.9% character error rate (CER) on our test set which is 2% absolute improvement from a strong BLSTM CE system with language model trained on the same text corpus.
Parametric Shortest Paths in Planar Graphs
Venue: arXiv cs.CC 2019
Year: 2019

We construct a family of planar graphs $\{G_n\}_{n\geq 4}$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $λ$ such that, as $λ$ varies in $(-\infty,+\infty)$, the piece-wise linear cost of the shortest path from $s$ to $t$ has $n^{Ω(\log n)}$ pieces. This shows that lower bounds obtained earlier by Carstensen (1983) and Mulmuley \& Shah (2001) for general graphs also hold for planar graphs, thereby refuting a conjecture of Nikolova (2009). Gusfield (1980) and Dean (2009) showed that the number of pieces for every $n$-vertex graph with linear edge weights is $n^{\log n + O(1)}$. We generalize this result in two ways. (i) If the edge weights vary as a polynomial of degree at most $d$, then the number of pieces is $n^{\log n + (α(n)+O(1))^d}$, where $α(n)$ is the slow growing inverse Ackermann function. (ii) If the edge weights are linear forms of three parameters, then the number of pieces, appropriately defined for $\mathbb{R}^3$, is $n^{(\log n)^2+O(\log n)}$.
On the Fundamental Limits of Fog-RAN Cache-aided Networks with Downlink and Sidelink Communications
Venue: arXiv cs.IT 2019
Year: 2019

Maddah-Ali and Niesen (MAN) in 2014 showed that coded caching in single bottleneck-link broadcast networks allows serving an arbitrarily large number of cache-equipped users with a total link load (bits per unit time) that does not scale with the number of users. Since then, the general topic of coded caching has generated enormous interest both from the information theoretic and (network) coding theoretic viewpoint, and from the viewpoint of applications. Building on the MAN work, this paper considers a particular network topology referred to as cache-aided Fog Radio Access Network (Fog-RAN), that includes a Macro-cell Base Station (MBS) co-located with the content server, several cache-equipped Small-cell Base Stations (SBSs), and many users without caches. Some users are served directly by the MBS broadcast downlink, while other users are served by the SBSs. The SBSs can also exchange data via rounds of direct communication via a side channel, referred to as "sidelink". For this novel Fog-RAN model, the fundamental tradeoff among (a) the amount of cache memory at the SBSs, (b) the load on the downlink (from MBS to directly served users and SBSs), and (c) the aggregate load on the sidelink is studied, under the standard worst-case demand scenario. Several existing results are recovered as special cases of this network model and byproduct results of independent interest are given. Finally, the role of topology-aware versus topology-agnostic caching is discussed.
Extractive Summary as Discrete Latent Variables
Venue: arXiv cs.CL 2019
Year: 2019

In this paper, we compare various methods to compress a text using a neural model. We find that extracting tokens as latent variables significantly outperforms the state-of-the-art discrete latent variable models such as VQ-VAE. Furthermore, we compare various extractive compression schemes. There are two best-performing methods that perform equally. One method is to simply choose the tokens with the highest tf-idf scores. Another is to train a bidirectional language model similar to ELMo and choose the tokens with the highest loss. If we consider any subsequence of a text to be a text in a broader sense, we conclude that language is a strong compression code of itself. Our finding justifies the high quality of generation achieved with hierarchical method, as their latent variables are nothing but natural language summary. We also conclude that there is a hierarchy in language such that an entire text can be predicted much more easily based on a sequence of a small number of keywords, which can be easily found by classical methods as tf-idf. We speculate that this extraction process may be useful for unsupervised hierarchical text generation.
Bounded ACh Unification
Venue: arXiv cs.LO 2019
Year: 2019

We consider the problem of the unification modulo an equational theory ACh, which consists of a function symbol $h$ that is homomorphic over an associative-commutative operator $+$. Since the unification modulo ACh theory is undecidable, we define a variant of the problem called \textit{bounded ACh unification}. In this bounded version of ACh unification, we essentially bound the number of times $h$ can be applied to a term recursively, and only allow solutions that satisfy this bound. There is no bound on the number of occurrences of $h$ in a term, and the $+$ symbol can be applied an unlimited number of times. We give inference rules for solving the bounded version of the problem and prove that the rules are sound, complete, and terminating. We have implemented the algorithm in Maude and give experimental results. We argue that this algorithm is useful in cryptographic protocol analysis.
Sample complexity of partition identification using multi-armed bandits
Venue: arXiv cs.LG 2019
Year: 2019

Given a vector of probability distributions, or arms, each of which can be sampled independently, we consider the problem of identifying the partition to which this vector belongs from a finitely partitioned universe of such vector of distributions. We study this as a pure exploration problem in multi armed bandit settings and develop sample complexity bounds on the total mean number of samples required for identifying the correct partition with high probability. This framework subsumes well studied problems such as finding the best arm or the best few arms. We consider distributions belonging to the single parameter exponential family and primarily consider partitions where the vector of means of arms lie either in a given set or its complement. The sets considered correspond to distributions where there exists a mean above a specified threshold, where the set is a half space and where either the set or its complement is a polytope, or more generally, a convex set. In these settings, we characterize the lower bounds on mean number of samples for each arm highlighting their dependence on the problem geometry. Further, inspired by the lower bounds, we propose algorithms that can match these bounds asymptotically with decreasing probability of error. Applications of this framework may be diverse. We briefly discuss one associated with finance.