OpenRaiser/Intern-Atlas huggingface dataset:
Addressing Time Bias in Bipartite Graph Ranking for Important Node Identification
Venue: arXiv cs.SI 2019
Year: 2019

The goal of the ranking problem in networks is to rank nodes from best to worst, according to a chosen criterion. In this work, we focus on ranking the nodes according to their quality. The problem of ranking the nodes in bipartite networks is valuable for many real-world applications. For instance, high-quality products can be promoted on an online shop or highly reputed restaurants attract more people on venues review platforms. However, many classical ranking algorithms share a common drawback: they tend to rank older movies higher than newer movies, though some newer movies may have a high quality. This time bias originates from the fact that older nodes in a network tend to have more connections than newer ones. In the study, we develop a ranking method using a rebalance approach to diminish the time bias of the rankings in bipartite graphs.
Online Pricing with Reserve Price Constraint for Personal Data Markets
Venue: arXiv cs.CE 2019
Year: 2019

The society's insatiable appetites for personal data are driving the emergency of data markets, allowing data consumers to launch customized queries over the datasets collected by a data broker from data owners. In this paper, we study how the data broker can maximize her cumulative revenue by posting reasonable prices for sequential queries. We thus propose a contextual dynamic pricing mechanism with the reserve price constraint, which features the properties of ellipsoid for efficient online optimization, and can support linear and non-linear market value models with uncertainty. In particular, under low uncertainty, our pricing mechanism provides a worst-case regret logarithmic in the number of queries. We further extend to other similar application scenarios, including hospitality service, online advertising, and loan application, and extensively evaluate three pricing instances of noisy linear query, accommodation rental, and impression over MovieLens 20M dataset, Airbnb listings in U.S. major cities, and Avazu mobile ad click dataset, respectively. The analysis and evaluation results reveal that our proposed pricing mechanism incurs low practical regret, online latency, and memory overhead, and also demonstrate that the existence of reserve price can mitigate the cold-start problem in a posted price mechanism, and thus can reduce the cumulative regret.
A Generalization Theory based on Independent and Task-Identically Distributed Assumption
Venue: arXiv cs.LG 2019
Year: 2019

Existing generalization theories analyze the generalization performance mainly based on the model complexity and training process. The ignorance of the task properties, which results from the widely used IID assumption, makes these theories fail to interpret many generalization phenomena or guide practical learning tasks. In this paper, we propose a new Independent and Task-Identically Distributed (ITID) assumption, to consider the task properties into the data generating process. The derived generalization bound based on the ITID assumption identifies the significance of hypothesis invariance in guaranteeing generalization performance. Based on the new bound, we introduce a practical invariance enhancement algorithm from the perspective of modifying data distributions. Finally, we verify the algorithm and theorems in the context of image classification task on both toy and real-world datasets. The experimental results demonstrate the reasonableness of the ITID assumption and the effectiveness of new generalization theory in improving practical generalization performance.
Threshold-Based Graph Reconstruction Using Discrete Morse Theory
Venue: arXiv cs.CG 2019
Year: 2019

Discrete Morse theory has recently been applied in metric graph reconstruction from a given density function concentrated around an (unknown) underlying embedded graph. We propose a new noise model for the density function to reconstruct a connected graph both topologically and geometrically.
GitHub Typo Corpus: A Large-Scale Multilingual Dataset of Misspellings and Grammatical Errors
Venue: arXiv cs.CL 2019
Year: 2019

The lack of large-scale datasets has been a major hindrance to the development of NLP tasks such as spelling correction and grammatical error correction (GEC). As a complementary new resource for these tasks, we present the GitHub Typo Corpus, a large-scale, multilingual dataset of misspellings and grammatical errors along with their corrections harvested from GitHub, a large and popular platform for hosting and sharing git repositories. The dataset, which we have made publicly available, contains more than 350k edits and 65M characters in more than 15 languages, making it the largest dataset of misspellings to date. We also describe our process for filtering true typo edits based on learned classifiers on a small annotated subset, and demonstrate that typo edits can be identified with F1 ~ 0.9 using a very simple classifier with only three features. The detailed analyses of the dataset show that existing spelling correctors merely achieve an F-measure of approx. 0.5, suggesting that the dataset serves as a new, rich source of spelling errors that complement existing datasets.
Communication-Efficient Distributed Online Learning with Kernels
Venue: arXiv cs.LG 2019
Year: 2019

We propose an efficient distributed online learning protocol for low-latency real-time services. It extends a previously presented protocol to kernelized online learners that represent their models by a support vector expansion. While such learners often achieve higher predictive performance than their linear counterparts, communicating the support vector expansions becomes inefficient for large numbers of support vectors. The proposed extension allows for a larger class of online learning algorithms---including those alleviating the problem above through model compression. In addition, we characterize the quality of the proposed protocol by introducing a novel criterion that requires the communication to be bounded by the loss suffered.
Land Cover Change Detection via Semantic Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

This paper presents a change detection method that identifies land cover changes from aerial imagery, using semantic segmentation, a machine learning approach. We present a land cover classification training pipeline with Deeplab v3+, state-of-the-art semantic segmentation technology, including data preparation, model training for seven land cover types, and model exporting modules. In the land cover change detection system, the inputs are images retrieved from Google Earth at the same location but from different times. The system then predicts semantic segmentation results on these images using the trained model and calculates the land cover class percentage for each input image. We see an improvement in the accuracy of the land cover semantic segmentation model, with a mean IoU of 0.756 compared to 0.433, as reported in the DeepGlobe land cover classification challenge. The land cover change detection system that leverages the state-of-the-art semantic segmentation technology is proposed and can be used for deforestation analysis, land management, and urban planning.
Spatiotemporal deep learning model for citywide air pollution interpolation and prediction
Venue: arXiv cs.LG 2019
Year: 2019

Recently, air pollution is one of the most concerns for big cities. Predicting air quality for any regions and at any time is a critical requirement of urban citizens. However, air pollution prediction for the whole city is a challenging problem. The reason is, there are many spatiotemporal factors affecting air pollution throughout the city. Collecting as many of them could help us to forecast air pollution better. In this research, we present many spatiotemporal datasets collected over Seoul city in Korea, which is currently much suffered by air pollution problem as well. These datasets include air pollution data, meteorological data, traffic volume, average driving speed, and air pollution indexes of external areas which are known to impact Seoul's air pollution. To the best of our knowledge, traffic volume and average driving speed data are two new datasets in air pollution research. In addition, recent research in air pollution has tried to build models to interpolate and predict air pollution in the city. Nevertheless, they mostly focused on predicting air quality in discrete locations or used hand-crafted spatial and temporal features. In this paper, we propose the usage of Convolutional Long Short-Term Memory (ConvLSTM) model \cite{b16}, a combination of Convolutional Neural Networks and Long Short-Term Memory, which automatically manipulates both the spatial and temporal features of the data. Specially, we introduce how to transform the air pollution data into sequences of images which leverages the using of ConvLSTM model to interpolate and predict air quality for the entire city at the same time. We prove that our approach is suitable for spatiotemporal air pollution problems and also outperforms other related research.
Richer priors for infinitely wide multi-layer perceptrons
Venue: arXiv cs.LG 2019
Year: 2019

It is well-known that the distribution over functions induced through a zero-mean iid prior distribution over the parameters of a multi-layer perceptron (MLP) converges to a Gaussian process (GP), under mild conditions. We extend this result firstly to independent priors with general zero or non-zero means, and secondly to a family of partially exchangeable priors which generalise iid priors. We discuss how the second prior arises naturally when considering an equivalence class of functions in an MLP and through training processes such as stochastic gradient descent. The model resulting from partially exchangeable priors is a GP, with an additional level of inference in the sense that the prior and posterior predictive distributions require marginalisation over hyperparameters. We derive the kernels of the limiting GP in deep MLPs, and show empirically that these kernels avoid certain pathologies present in previously studied priors. We empirically evaluate our claims of convergence by measuring the maximum mean discrepancy between finite width models and limiting models. We compare the performance of our new limiting model to some previously discussed models on synthetic regression problems. We observe increasing ill-conditioning of the marginal likelihood and hyper-posterior as the depth of the model increases, drawing parallels with finite width networks which require notoriously involved optimisation tricks.
Mining Approximate Acyclic Schemes from Relations
Venue: arXiv cs.DB 2019
Year: 2019

Acyclic schemes have numerous applications in databases and in machine learning, such as improved design, more efficient storage, and increased performance for queries and machine learning algorithms. Multivalued dependencies (MVDs) are the building blocks of acyclic schemes. The discovery from data of both MVDs and acyclic schemes is more challenging than other forms of data dependencies, such as Functional Dependencies, because these dependencies do not hold on subsets of data, and because they are very sensitive to noise in the data; for example a single wrong or missing tuple may invalidate the schema. In this paper we present Maimon, a system for discovering approximate acyclic schemes and MVDs from data. We give a principled definition of approximation, by using notions from information theory, then describe the two components of Maimon: mining for approximate MVDs, then reconstructing acyclic schemes from approximate MVDs. We conduct an experimental evaluation of Maimon on 20 real-world datasets, and show that it can scale up to 1M rows, and up to 30 columns.
Neural Chinese Word Segmentation as Sequence to Sequence Translation
Venue: arXiv cs.CL 2019
Year: 2019

Recently, Chinese word segmentation (CWS) methods using neural networks have made impressive progress. Most of them regard the CWS as a sequence labeling problem which construct models based on local features rather than considering global information of input sequence. In this paper, we cast the CWS as a sequence translation problem and propose a novel sequence-to-sequence CWS model with an attention-based encoder-decoder framework. The model captures the global information from the input and directly outputs the segmented sequence. It can also tackle other NLP tasks with CWS jointly in an end-to-end mode. Experiments on Weibo, PKU and MSRA benchmark datasets show that our approach has achieved competitive performances compared with state-of-the-art methods. Meanwhile, we successfully applied our proposed model to jointly learning CWS and Chinese spelling correction, which demonstrates its applicability of multi-task fusion.
Empty Squares in Arbitrary Orientation Among Points
Venue: arXiv cs.CG 2019
Year: 2019

This paper studies empty squares in arbitrary orientation among a set $P$ of $n$ points in the plane. We prove that the number of empty squares with four contact pairs is between $Ω(n)$ and $O(n^2)$, and that these bounds are tight, provided $P$ is in a certain general position. A contact pair of a square is a pair of a point $p\in P$ and a side $\ell$ of the square with $p\in \ell$. The upper bound $O(n^2)$ also applies to the number of empty squares with four contact points, while we construct a point set among which there is no square of four contact points. These combinatorial results are based on new observations on the $L_\infty$ Voronoi diagram with the axes rotated and its close connection to empty squares in arbitrary orientation. We then present an algorithm that maintains a combinatorial structure of the $L_\infty$ Voronoi diagram of $P$, while the axes of the plane continuously rotates by $90$ degrees, and simultaneously reports all empty squares with four contact pairs among $P$ in an output-sensitive way within $O(s\log n)$ time and $O(n)$ space, where $s$ denotes the number of reported squares. Several new algorithmic results are also obtained: a largest empty square among $P$ and a square annulus of minimum width or minimum area that encloses $P$ over all orientations can be computed in worst-case $O(n^2 \log n)$ time.
Online Structured Sparsity-based Moving Object Detection from Satellite Videos
Venue: arXiv cs.CV 2019
Year: 2019

Inspired by the recent developments in computer vision, low-rank and structured sparse matrix decomposition can be potentially be used for extract moving objects in satellite videos. This set of approaches seeks for rank minimization on the background that typically requires batch-based optimization over a sequence of frames, which causes delays in processing and limits their applications. To remedy this delay, we propose an Online Low-rank and Structured Sparse Decomposition (O-LSD). O-LSD reformulates the batch-based low-rank matrix decomposition with the structured sparse penalty to its equivalent frame-wise separable counterpart, which then defines a stochastic optimization problem for online subspace basis estimation. In order to promote online processing, O-LSD conducts the foreground and background separation and the subspace basis update alternatingly for every frame in a video. We also show the convergence of O-LSD theoretically. Experimental results on two satellite videos demonstrate the performance of O-LSD in term of accuracy and time consumption is comparable with the batch-based approaches with significantly reduced delay in processing.
Class Teaching for Inverse Reinforcement Learners
Venue: arXiv cs.LG 2019
Year: 2019

In this paper we propose the first machine teaching algorithm for multiple inverse reinforcement learners. Specifically, our contributions are: (i) we formally introduce the problem of teaching a sequential task to a heterogeneous group of learners; (ii) we identify conditions under which it is possible to conduct such teaching using the same demonstration for all learners; and (iii) we propose and evaluate a simple algorithm that computes a demonstration(s) ensuring that all agents in a heterogeneous class learn a task description that is compatible with the target task. Our analysis shows that, contrary to other teaching problems, teaching a heterogeneous class with a single demonstration may not be possible as the differences between agents increase. We also showcase the advantages of our proposed machine teaching approach against several possible alternatives.
Safe Walking In VR using Augmented Virtuality
Venue: arXiv cs.HC 2019
Year: 2019

New technologies allow ordinary people to access Virtual Reality at affordable prices in their homes. One of the most important tasks when interacting with immersive Virtual Reality is to navigate the virtual environments (VEs). Arguably, the best methods to accomplish this use of direct control interfaces. Among those, natural walking (NW) makes for enjoyable user experience. However, common techniques to support direct control interfaces in VEs feature constraints that make it difficult to use those methods in cramped home environments. Indeed, NW requires unobstructed and open space. To approach this problem, we propose a new virtual locomotion technique, Combined Walking in Place (CWIP). CWIP allows people to take advantage of the available physical space and empowers them to use NW to navigate in the virtual world. For longer distances, we adopt Walking in Place (WIP) to enable them to move in the virtual world beyond the confines of a cramped real room. However, roaming in immersive alternate reality, while moving in the confines of a cluttered environment can lead people to stumble and fall. To approach these problems, we developed Augmented Virtual Reality (AVR), to inform users about real-world hazards, such as chairs, drawers, walls via proxies and signs placed in the virtual world. We propose thus CWIP-AVR as a way to safely explore VR in the cramped confines of your own home. To our knowledge, this is the first approach to combined different locomotion modalities in a safe manner. We evaluated it in a user study with 20 participants to validate their ability to navigate a virtual world while walking in a confined and cluttered real space. Our results show that CWIP-AVR allows people to navigate VR safely, switching between locomotion modes flexibly while maintaining a good immersion.
Efficient method for parallel computation of geodesic transformation on CPU
Venue: arXiv cs.PF 2019
Year: 2019

This paper introduces a fast Central Processing Unit (CPU) implementation of geodesic morphological operations using stream processing. In contrast to the current state-of-the-art, that focuses on achieving insensitivity to the filter sizes with efficient data structures, the proposed approach achieves efficient computation of long chains of elementary $3 \times 3$ filters using multicore and Single Instruction Multiple Data (SIMD) processing. In comparison to the related methods, up to $100$ times faster computation of common geodesic operators is achieved in this way, allowing for real-time processing (with over $30$ FPS) of up to $1500$ filters long chains, applied on $1024\times 1024$ images. In addition, the proposed approach outperformed GPGPU, and proved to be more efficient than the comparable streaming method for the computation of morphological erosions and dilations with window sizes up to $183\times 183$ in the case of using char and $27\times27$ when using double data types.
Rate-Splitting for Multigroup Multicast Beamforming in Multicarrier Systems
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we consider multigroup multicast transmissions with different types of service messages in an overloaded multicarrier system, where the number of transmitter antennas is insufficient to mitigate all inter-group interference. We show that employing a rate-splitting based multiuser beamforming approach enables a simultaneous delivery of the multiple service messages over the same time-frequency resources in a non-orthogonal fashion. Such an approach, taking into account transmission power constraints which are inevitable in practice, outperforms classic beamforming methods as well as current standardized multicast technologies, in terms of both spectrum efficiency and the flexibility of radio resource allocation.
VIABLE: Fast Adaptation via Backpropagating Learned Loss
Venue: arXiv cs.LG 2019
Year: 2019

In few-shot learning, typically, the loss function which is applied at test time is the one we are ultimately interested in minimising, such as the mean-squared-error loss for a regression problem. However, given that we have few samples at test time, we argue that the loss function that we are interested in minimising is not necessarily the loss function most suitable for computing gradients in a few-shot setting. We propose VIABLE, a generic meta-learning extension that builds on existing meta-gradient-based methods by learning a differentiable loss function, replacing the pre-defined inner-loop loss function in performing task-specific updates. We show that learning a loss function capable of leveraging relational information between samples reduces underfitting, and significantly improves performance and sample efficiency on a simple regression task. Furthermore, we show VIABLE is scalable by evaluating on the Mini-Imagenet dataset.
FirecREST: RESTful API on Cray XC systems
Venue: arXiv cs.DC 2019
Year: 2019

As science gateways are becoming an increasingly popular digital interface for scientific communities, it is also becoming increasingly important for High-Performance Computing centers to provide a modern Web-enabled APIs. With such interface, science gateways can easily integrate access to HPC center resources. This work presents the FirecREST API, a RESTful Web API infrastructure that allows scientific communities to access the various integrated resources and services available from the Cray XC systems at the Swiss National Supercomputing Centre. FirecREST requirements are derived from use cases described in this work.
An Iterative Polishing Framework based on Quality Aware Masked Language Model for Chinese Poetry Generation
Venue: arXiv cs.CL 2019
Year: 2019

Owing to its unique literal and aesthetical characteristics, automatic generation of Chinese poetry is still challenging in Artificial Intelligence, which can hardly be straightforwardly realized by end-to-end methods. In this paper, we propose a novel iterative polishing framework for highly qualified Chinese poetry generation. In the first stage, an encoder-decoder structure is utilized to generate a poem draft. Afterwards, our proposed Quality-Aware Masked Language Model (QAMLM) is employed to polish the draft towards higher quality in terms of linguistics and literalness. Based on a multi-task learning scheme, QA-MLM is able to determine whether polishing is needed based on the poem draft. Furthermore, QAMLM is able to localize improper characters of the poem draft and substitute with newly predicted ones accordingly. Benefited from the masked language model structure, QAMLM incorporates global context information into the polishing process, which can obtain more appropriate polishing results than the unidirectional sequential decoding. Moreover, the iterative polishing process will be terminated automatically when QA-MLM regards the processed poem as a qualified one. Both human and automatic evaluation have been conducted, and the results demonstrate that our approach is effective to improve the performance of encoder-decoder structure.