OpenRaiser/Intern-Atlas huggingface dataset:
Expansional Retrofitting for Word Vector Enrichment
Venue: arXiv cs.CL 2019
Year: 2019

Retrofitting techniques, which inject external resources into word representations, have compensated the weakness of distributed representations in semantic and relational knowledge between words. Implicitly retrofitting word vectors by expansional technique outperforms retrofitting in word similarity tasks with word vector generalization. In this paper, we propose unsupervised extrofitting: expansional retrofitting (extrofitting) without external semantic lexicons. We also propose deep extrofitting: in-depth stacking of extrofitting and further combinations of extrofitting with retrofitting. When experimenting with GloVe, we show that our methods outperform the previous methods on most of word similarity tasks while requiring only synonyms as an external resource. Lastly, we show the effect of word vector enrichment on text classification task, as a downstream task.
Rethinking Monocular Depth Estimation with Adversarial Training
Venue: arXiv cs.CV 2019
Year: 2019

Monocular depth estimation is an extensively studied computer vision problem with a vast variety of applications. Deep learning-based methods have demonstrated promise for both supervised and unsupervised depth estimation from monocular images. Most existing approaches treat depth estimation as a regression problem with a local pixel-wise loss function. In this work, we innovate beyond existing approaches by using adversarial training to learn a context-aware, non-local loss function. Such an approach penalizes the joint configuration of predicted depth values at the patch-level instead of the pixel-level, which allows networks to incorporate more global information. In this framework, the generator learns a mapping between RGB images and its corresponding depth map, while the discriminator learns to distinguish depth map and RGB pairs from ground truth. This conditional GAN depth estimation framework is stabilized using spectral normalization to prevent mode collapse when learning from diverse datasets. We test this approach using a diverse set of generators that include U-Net and joint CNN-CRF. We benchmark this approach on the NYUv2, Make3D and KITTI datasets, and observe that adversarial training reduces relative error by several fold, achieving state-of-the-art performance.
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
Venue: arXiv cs.LG 2019
Year: 2019

Communication-efficient SGD algorithms, which allow nodes to perform local updates and periodically synchronize local models, are highly effective in improving the speed and scalability of distributed SGD. However, a rigorous convergence analysis and comparative study of different communication-reduction strategies remains a largely open problem. This paper presents a unified framework called Cooperative SGD that subsumes existing communication-efficient SGD algorithms such as periodic-averaging, elastic-averaging and decentralized SGD. By analyzing Cooperative SGD, we provide novel convergence guarantees for existing algorithms. Moreover, this framework enables us to design new communication-efficient SGD algorithms that strike the best balance between reducing communication overhead and achieving fast error convergence with low error floor.
Qualitative vision-based navigation based on sloped funnel lane concept
Venue: arXiv cs.RO 2019
Year: 2019

Funnel lane concept is a qualitative visual navigation method which helps robots to autonomously navigate by using a recorded video. A visual path is extracted from the video by extracting some keyframes from the video. The robot uses this visual path for its navigation. Funnel lane unlike some other methods does not make use of traditional calculations of Jacobians, homographies, fundamental matrices, or the focus of expansion, and does not require any camera calibration. However, funnel lane has some shortcomings. One problem is that funnel lane gives no information about the radius of rotation, so in turnings, the robot turns by a constant radius of rotation along the path. This reduces the maneuverability and limits the robot from dealing with all turnings conditions. In addition, this problem makes the robot faces a serious problem in correcting its path when it deviates from the desired path. Another flaw is that in some situations the robot faces an ambiguity to understand whether a translation or a rotation should be followed in the visual path which leads the robot to deviate and to fail in following the desired path. This paper introduces the sloped funnel lane technique which does not have these shortcomings. The roll and pitch angles are added to the funnel lane, which help the robot to set its radius of rotation according to the turnings conditions it faces. Moreover, they help to reduce the ambiguity between translation and rotation. Therefore the robot can deal with different turnings conditions and the navigation method will be more robust and accurate. Experimental results on challenging scenarios on a real ground robot demonstrate the effectiveness of sloped funnel lane technique.
The First Order Truth behind Undecidability of Regular Path Queries Determinacy
Venue: arXiv cs.DB 2019
Year: 2019

In our paper [Głuch, Marcinkowski, Ostropolski-Nalewaja, LICS ACM, 2018] we have solved an old problem stated in [Calvanese, De Giacomo, Lenzerini, Vardi, SPDS ACM, 2000] showing that query determinacy is undecidable for Regular Path Queries. Here a strong generalisation of this result is shown, and -- we think -- a very unexpected one. We prove that no regularity is needed: determinacy remains undecidable even for finite unions of conjunctive path queries.
One (more) line on the most Ancient Algorithm in History
Venue: arXiv cs.DS 2019
Year: 2019

We give a new simple and short ("one-line") analysis for the runtime of the well-known Euclidean Algorithm. While very short simple, the obtained upper bound in near-optimal.
Functional Federated Learning in Erlang (ffl-erl)
Venue: arXiv cs.PL 2019
Year: 2019

The functional programming language Erlang is well-suited for concurrent and distributed applications. Numerical computing, however, is not seen as one of its strengths. The recent introduction of Federated Learning, a concept according to which client devices are leveraged for decentralized machine learning tasks, while a central server updates and distributes a global model, provided the motivation for exploring how well Erlang is suited to that problem. We present ffl-erl, a framework for Federated Learning, written in Erlang, and explore how well it performs in two scenarios: one in which the entire system has been written in Erlang, and another in which Erlang is relegated to coordinating client processes that rely on performing numerical computations in the programming language C. There is a concurrent as well as a distributed implementation of each case. Erlang incurs a performance penalty, but for certain use cases this may not be detrimental, considering the trade-off between conciseness of the language and speed of development (Erlang) versus performance (C). Thus, Erlang may be a viable alternative to C for some practical machine learning tasks.
Unknown Examples & Machine Learning Model Generalization
Venue: arXiv cs.LG 2019
Year: 2019

Over the past decades, researchers and ML practitioners have come up with better and better ways to build, understand and improve the quality of ML models, but mostly under the key assumption that the training data is distributed identically to the testing data. In many real-world applications, however, some potential training examples are unknown to the modeler, due to sample selection bias or, more generally, covariate shift, i.e., a distribution shift between the training and deployment stage. The resulting discrepancy between training and testing distributions leads to poor generalization performance of the ML model and hence biased predictions. We provide novel algorithms that estimate the number and properties of these unknown training examples---unknown unknowns. This information can then be used to correct the training set, prior to seeing any test data. The key idea is to combine species-estimation techniques with data-driven methods for estimating the feature values for the unknown unknowns. Experiments on a variety of ML models and datasets indicate that taking the unknown examples into account can yield a more robust ML model that generalizes better.
Deep Learning: Computational Aspects
Venue: arXiv cs.LG 2019
Year: 2019

In this article we review computational aspects of Deep Learning (DL). Deep learning uses network architectures consisting of hierarchical layers of latent variables to construct predictors for high-dimensional input-output models. Training a deep learning architecture is computationally intensive, and efficient linear algebra libraries is the key for training and inference. Stochastic gradient descent (SGD) optimization and batch sampling are used to learn from massive data sets.
Clausal Abstraction for DQBF (full version)
Venue: arXiv cs.LO 2019
Year: 2019

Dependency quantified Boolean formulas (DQBF) is a logic admitting existential quantification over Boolean functions, which allows us to elegantly state synthesis problems in verification such as the search for invariants, programs, or winning regions of games. In this paper, we lift the clausal abstraction algorithm for quantified Boolean formulas (QBF) to DQBF. Clausal abstraction for QBF is an abstraction refinement algorithm that operates on a sequence of abstractions that represent the different quantifier levels. For DQBF we need to generalize this principle to partial orders of abstractions. The two challenges to overcome are: (1) Clauses may contain literals with incomparable dependencies, which we address by the recently proposed proof rule called Fork Extension, and (2) existential variables may have spurious dependencies, which we prevent by tracking consistency requirements during the execution. Our implementation dCAQE solves significantly more formulas than the existing DQBF algorithms.
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
Venue: arXiv cs.CC 2019
Year: 2019

A fundamental graph problem is to recognize whether the vertex set of a graph $G$ can be bipartitioned into sets $A$ and $B$ such that $G[A]$ and $G[B]$ satisfy properties $Π_A$ and $Π_B$, respectively. This so-called $(Π_A,Π_B)$-Recognition problem generalizes amongst others the recognition of $3$-colorable, bipartite, split, and monopolar graphs. In this paper, we study whether certain fixed-parameter tractable $(Π_A,Π_B)$-Recognition problems admit polynomial kernels. In our study, we focus on the first level above triviality, where $Π_A$ is the set of $P_3$-free graphs (disjoint unions of cliques, or cluster graphs), the parameter is the number of clusters in the cluster graph $G[A]$, and $Π_B$ is characterized by a set $\mathcal{H}$ of connected forbidden induced subgraphs. We prove that, under the assumption that NP is not a subset of coNP/poly, \textsc{$(Π_A,Π_B)$-Recognition} admits a polynomial kernel if and only if $\mathcal{H}$ contains a graph with at most $2$ vertices. In both the kernelization and the lower bound results, we exploit the properties of a pushing process, which is an algorithmic technique used recently by Heggerness et al. and by Kanj et al. to obtain fixed-parameter algorithms for many cases of $(Π_A,Π_B)$-Recognition, as well as several other problems.
A Monotone Preservation Result for Boolean Queries Expressed as a Containment of Conjunctive Queries
Venue: arXiv cs.DB 2019
Year: 2019

When a relational database is queried, the result is normally a relation. Some queries, however, only require a yes/no answer; such queries are often called boolean queries. It is customary in database theory to express boolean queries by testing nonemptiness of query expressions. Another interesting way for expressing boolean queries are containment statements of the form $Q_1 \subseteq Q_2$ where $Q_1$ and $Q_2$ are query expressions. Here, for any input instance $I$, the boolean query result is $\mathit{true}$ if $Q_1(I)$ is a subset of $Q_2(I)$ and $\mathit{false}$ otherwise. In the present paper we will focus on nonemptiness and containment statements about conjunctive queries. The main goal is to investigate the monotone fragment of the containments of conjunctive queries. In particular, we show a preservation like result for this monotone fragment. That is, we show that, in expressive power, the monotone containments of conjunctive queries are exactly equal to conjunctive queries under nonemptiness.
NeuralCubes: Deep Representations for Visual Data Exploration
Venue: arXiv cs.DB 2019
Year: 2019

Visual exploration of large multidimensional datasets has seen tremendous progress in recent years, allowing users to express rich data queries that produce informative visual summaries, all in real time. Techniques based on data cubes are some of the most promising approaches. However, these techniques usually require a large memory footprint for large datasets. To tackle this problem, we present NeuralCubes: neural networks that predict results for aggregate queries, similar to data cubes. NeuralCubes learns a function that takes as input a given query, for instance, a geographic region and temporal interval, and outputs the result of the query. The learned function serves as a real-time, low-memory approximator for aggregation queries. NeuralCubes models are small enough to be sent to the client side (e.g. the web browser for a web-based application) for evaluation, enabling data exploration of large datasets without database/network connection. We demonstrate the effectiveness of NeuralCubes through extensive experiments on a variety of datasets and discuss how NeuralCubes opens up opportunities for new types of visualization and interaction.
Nash Equilibrium and Bisimulation Invariance
Venue: arXiv cs.LO 2019
Year: 2019

Game theory provides a well-established framework for the analysis of concurrent and multi-agent systems. The basic idea is that concurrent processes (agents) can be understood as corresponding to players in a game; plays represent the possible computation runs of the system; and strategies define the behaviour of agents. Typically, strategies are modelled as functions from sequences of system states to player actions. Analysing a system in such a setting involves computing the set of (Nash) equilibria in the concurrent game. However, we show that, with respect to the above model of strategies (arguably, the "standard" model in the computer science literature), bisimilarity does not preserve the existence of Nash equilibria. Thus, two concurrent games which are behaviourally equivalent from a semantic perspective, and which from a logical perspective satisfy the same temporal logic formulae, may nevertheless have fundamentally different properties (solutions) from a game theoretic perspective. Our aim in this paper is to explore the issues raised by this discovery. After illustrating the issue by way of a motivating example, we present three models of strategies with respect to which the existence of Nash equilibria is preserved under bisimilarity. We use some of these models of strategies to provide new semantic foundations for logics for strategic reasoning, and investigate restricted scenarios where bisimilarity can be shown to preserve the existence of Nash equilibria with respect to the conventional model of strategies in the computer science literature.
The dispersion time of random walks on finite graphs
Venue: arXiv cs.DM 2019
Year: 2019

We study two random processes on an $n$-vertex graph inspired by the internal diffusion limited aggregation (IDLA) model. In both processes $n$ particles start from an arbitrary but fixed origin. Each particle performs a simple random walk until first encountering an unoccupied vertex, and at which point the vertex becomes occupied and the random walk terminates. In one of the processes, called \textit{Sequential-IDLA}, only one particle moves until settling and only then does the next particle start whereas in the second process, called \textit{Parallel-IDLA}, all unsettled particles move simultaneously. Our main goal is to analyze the so-called dispersion time of these processes, which is the maximum number of steps performed by any of the $n$ particles. In order to compare the two processes, we develop a coupling which shows the dispersion time of the Parallel-IDLA stochastically dominates that of the Sequential-IDLA; however, the total number of steps performed by all particles has the same distribution in both processes. This coupling also gives us that dispersion time of Parallel-IDLA is bounded in expectation by dispersion time of the Sequential-IDLA up to a multiplicative $\log n$ factor. Moreover, we derive asymptotic upper and lower bound on the dispersion time for several graph classes, such as cliques, cycles, binary trees, $d$-dimensional grids, hypercubes and expanders. Most of our bounds are tight up to a multiplicative constant.
On Learning 3D Face Morphable Model from In-the-wild Images
Venue: arXiv cs.CV 2019
Year: 2019

As a classic statistical model of 3D facial shape and albedo, 3D Morphable Model (3DMM) is widely used in facial analysis, e.g., model fitting, image synthesis. Conventional 3DMM is learned from a set of 3D face scans with associated well-controlled 2D face images, and represented by two sets of PCA basis functions. Due to the type and amount of training data, as well as, the linear bases, the representation power of 3DMM can be limited. To address these problems, this paper proposes an innovative framework to learn a nonlinear 3DMM model from a large set of in-the-wild face images, without collecting 3D face scans. Specifically, given a face image as input, a network encoder estimates the projection, lighting, shape and albedo parameters. Two decoders serve as the nonlinear 3DMM to map from the shape and albedo parameters to the 3D shape and albedo, respectively. With the projection parameter, lighting, 3D shape, and albedo, a novel analytically-differentiable rendering layer is designed to reconstruct the original input face. The entire network is end-to-end trainable with only weak supervision. We demonstrate the superior representation power of our nonlinear 3DMM over its linear counterpart, and its contribution to face alignment, 3D reconstruction, and face editing.
Elastic bands across the path: A new framework and methods to lower bound DTW
Venue: arXiv cs.LG 2019
Year: 2019

There has been renewed recent interest in developing effective lower bounds for Dynamic Time Warping (DTW) distance between time series. These have many applications in time series indexing, clustering, forecasting, regression and classification. One of the key time series classification algorithms, the nearest neighbor algorithm with DTW distance (NN-DTW) is very expensive to compute, due to the quadratic complexity of DTW. Lower bound search can speed up NN-DTW substantially. An effective and tight lower bound quickly prunes off unpromising nearest neighbor candidates from the search space and minimises the number of the costly DTW computations. The speed up provided by lower bound search becomes increasingly critical as training set size increases. Different lower bounds provide different trade-offs between computation time and tightness. Most existing lower bounds interact with DTW warping window sizes. They are very tight and effective at smaller warping window sizes, but become looser as the warping window increases, thus reducing the pruning effectiveness for NN-DTW. In this work, we present a new class of lower bounds that are tighter than the popular Keogh lower bound, while requiring similar computation time. Our new lower bounds take advantage of the DTW boundary condition, monotonicity and continuity constraints to create a tighter lower bound. Of particular significance, they remain relatively tight even for large windows. A single parameter to these new lower bounds controls the speed-tightness trade-off. We demonstrate that these new lower bounds provide an exceptional balance between computation time and tightness for the NN-DTW time series classification task, resulting in greatly improved efficiency for NN-DTW lower bound search.
Super-Resolution for Hyperspectral and Multispectral Image Fusion Accounting for Seasonal Spectral Variability
Venue: arXiv cs.CV 2019
Year: 2019

Image fusion combines data from different heterogeneous sources to obtain more precise information about an underlying scene. Hyperspectral-multispectral (HS-MS) image fusion is currently attracting great interest in remote sensing since it allows the generation of high spatial resolution HS images, circumventing the main limitation of this imaging modality. Existing HS-MS fusion algorithms, however, neglect the spectral variability often existing between images acquired at different time instants. This time difference causes variations in spectral signatures of the underlying constituent materials due to different acquisition and seasonal conditions. This paper introduces a novel HS-MS image fusion strategy that combines an unmixing-based formulation with an explicit parametric model for typical spectral variability between the two images. Simulations with synthetic and real data show that the proposed strategy leads to a significant performance improvement under spectral variability and state-of-the-art performance otherwise.
Improved approximation algorithms for hitting 3-vertex paths
Venue: arXiv cs.DS 2019
Year: 2019

We study the problem of deleting a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. This problem is often called cluster vertex deletion in the literature and admits a straightforward 3-approximation algorithm since it is a special case of the vertex cover problem on a 3-uniform hypergraph. Recently, You, Wang, and Cao described an efficient 5/2-approximation algorithm for the unweighted version of the problem. Our main result is a 9/4-approximation algorithm for arbitrary weights, using the local ratio technique. We further conjecture that the problem admits a 2-approximation algorithm and give some support for the conjecture. This is in sharp contrast with the fact that the similar problem of deleting vertices to eliminate all triangles in a graph is known to be UGC-hard to approximate to within a ratio better than 3, as proved by Guruswami and Lee.
An improved upper bound on the integrality ratio for the $s$-$t$-path TSP
Venue: arXiv cs.DM 2019
Year: 2019

We give an improved analysis of the best-of-many Christofides algorithm with lonely edge deletion, which was proposed by Sebő and van Zuylen [2016]. This implies an improved upper bound on the integrality ratio of the standard LP relaxation for the $s$-$t$-path TSP.