OpenRaiser/Intern-Atlas huggingface dataset:
C-3PO: Click-sequence-aware DeeP Neural Network (DNN)-based Pop-uPs RecOmmendation
Venue: arXiv cs.CY 2018
Year: 2018

With the emergence of mobile and wearable devices, push notification becomes a powerful tool to connect and maintain the relationship with App users, but sending inappropriate or too many messages at the wrong time may result in the App being removed by the users. In order to maintain the retention rate and the delivery rate of advertisement, we adopt Deep Neural Network (DNN) to develop a pop-up recommendation system "Click sequence-aware deeP neural network (DNN)-based Pop-uPs recOmmendation (C-3PO)" enabled by collaborative filtering-based hybrid user behavioral analysis. We further verified the system with real data collected from the product Security Master, Clean Master and CM Browser, supported by Leopard Mobile Inc. (Cheetah Mobile Taiwan Agency). In this way, we can know precisely about users' preference and frequency to click on the push notification/pop-ups, decrease the troublesome to users efficiently, and meanwhile increase the click through rate of push notifications/pop-ups.
The 2018 DAVIS Challenge on Video Object Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

We present the 2018 DAVIS Challenge on Video Object Segmentation, a public competition specifically designed for the task of video object segmentation. It builds upon the DAVIS 2017 dataset, which was presented in the previous edition of the DAVIS Challenge, and added 100 videos with multiple objects per sequence to the original DAVIS 2016 dataset. Motivated by the analysis of the results of the 2017 edition, the main track of the competition will be the same than in the previous edition (segmentation given the full mask of the objects in the first frame -- semi-supervised scenario). This edition, however, also adds an interactive segmentation teaser track, where the participants will interact with a web service simulating the input of a human that provides scribbles to iteratively improve the result.
Evolutionary Generative Adversarial Networks
Venue: arXiv cs.LG 2018
Year: 2018

Generative adversarial networks (GAN) have been effective for learning generative models for real-world data. However, existing GANs (GAN and its variants) tend to suffer from training problems such as instability and mode collapse. In this paper, we propose a novel GAN framework called evolutionary generative adversarial networks (E-GAN) for stable GAN training and improved generative performance. Unlike existing GANs, which employ a pre-defined adversarial objective function alternately training a generator and a discriminator, we utilize different adversarial training objectives as mutation operations and evolve a population of generators to adapt to the environment (i.e., the discriminator). We also utilize an evaluation mechanism to measure the quality and diversity of generated samples, such that only well-performing generator(s) are preserved and used for further training. In this way, E-GAN overcomes the limitations of an individual adversarial training objective and always preserves the best offspring, contributing to progress in and the success of GANs. Experiments on several datasets demonstrate that E-GAN achieves convincing generative performance and reduces the training problems inherent in existing GANs.
Raw Multi-Channel Audio Source Separation using Multi-Resolution Convolutional Auto-Encoders
Venue: arXiv cs.SD 2018
Year: 2018

Supervised multi-channel audio source separation requires extracting useful spectral, temporal, and spatial features from the mixed signals. The success of many existing systems is therefore largely dependent on the choice of features used for training. In this work, we introduce a novel multi-channel, multi-resolution convolutional auto-encoder neural network that works on raw time-domain signals to determine appropriate multi-resolution features for separating the singing-voice from stereo music. Our experimental results show that the proposed method can achieve multi-channel audio source separation without the need for hand-crafted features or any pre- or post-processing.
Reinforcement Learning to Rank in E-Commerce Search Engine: Formalization, Analysis, and Application
Venue: arXiv cs.LG 2018
Year: 2018

In e-commerce platforms such as Amazon and TaoBao, ranking items in a search session is a typical multi-step decision-making problem. Learning to rank (LTR) methods have been widely applied to ranking problems. However, such methods often consider different ranking steps in a session to be independent, which conversely may be highly correlated to each other. For better utilizing the correlation between different ranking steps, in this paper, we propose to use reinforcement learning (RL) to learn an optimal ranking policy which maximizes the expected accumulative rewards in a search session. Firstly, we formally define the concept of search session Markov decision process (SSMDP) to formulate the multi-step ranking problem. Secondly, we analyze the property of SSMDP and theoretically prove the necessity of maximizing accumulative rewards. Lastly, we propose a novel policy gradient algorithm for learning an optimal ranking policy, which is able to deal with the problem of high reward variance and unbalanced reward distribution of an SSMDP. Experiments are conducted in simulation and TaoBao search engine. The results demonstrate that our algorithm performs much better than online LTR methods, with more than 40% and 30% growth of total transaction amount in the simulation and the real application, respectively.
A fast implementation of near neighbors queries for Fréchet distance (GIS Cup)
Venue: arXiv cs.CG 2018
Year: 2018

This paper describes an implementation of fast near-neighbours queries (also known as range searching) with respect to the Fréchet distance. The algorithm is designed to be efficient on practical data such as GPS trajectories. Our approach is to use a quadtree data structure to enumerate all curves in the database that have similar start and endpoints as the query curve. On these curves we run positive and negative filters to narrow the set of potential results. Only for those trajectories where these heuristics fail, we compute the Fréchet distance exactly, by running a novel recursive variant of the classic free-space diagram algorithm. Our implementation won the ACM SIGSPATIAL GIS Cup 2017.
Nash equilibria in routing games with edge priorities
Venue: arXiv cs.GT 2018
Year: 2018

In this paper we present a new competitive packet routing model with edge priorities. We consider players that route selfishly through a network over time and try to reach their destinations as fast as possible. If the number of players who want to enter an edge at the same time exceeds the inflow capacity of this edge, edge priorities with respect to the preceding edge solve these conflicts. Our edge priorities are well-motivated by applications in traffic. For this class of games, we show the existence of equilibrium solutions for single-source-single-sink games and we analyze structural properties of these solutions. We present an algorithm that computes Nash equilibria and we prove bounds both on the Price of Stability and on the Price of Anarchy. Moreover, we introduce the new concept of a Price of Mistrust. Finally, we also study the relations to earliest arrival flows.
Enhancing Cooperative Coevolution for Large Scale Optimization by Adaptively Constructing Surrogate Models
Venue: arXiv cs.NE 2018
Year: 2018

It has been shown that cooperative coevolution (CC) can effectively deal with large scale optimization problems (LSOPs) through a divide-and-conquer strategy. However, its performance is severely restricted by the current context-vector-based sub-solution evaluation method since this method needs to access the original high dimensional simulation model when evaluating each sub-solution and thus requires many computation resources. To alleviate this issue, this study proposes an adaptive surrogate model assisted CC framework. This framework adaptively constructs surrogate models for different sub-problems by fully considering their characteristics. For the single dimensional sub-problems obtained through decomposition, accurate enough surrogate models can be obtained and used to find out the optimal solutions of the corresponding sub-problems directly. As for the nonseparable sub-problems, the surrogate models are employed to evaluate the corresponding sub-solutions, and the original simulation model is only adopted to reevaluate some good sub-solutions selected by surrogate models. By these means, the computation cost could be greatly reduced without significantly sacrificing evaluation quality. Empirical studies on IEEE CEC 2010 benchmark functions show that the concrete algorithm based on this framework is able to find much better solutions than the conventional CC algorithms and a non-CC algorithm even with much fewer computation resources.
Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering
Venue: arXiv cs.DS 2018
Year: 2018

We study $k$-means clustering in a semi-supervised setting. Given an oracle that returns whether two given points belong to the same cluster in a fixed optimal clustering, we investigate the following question: how many oracle queries are sufficient to efficiently recover a clustering that, with probability at least $(1 - δ)$, simultaneously has a cost of at most $(1 + ε)$ times the optimal cost and an accuracy of at least $(1 - ε)$? We show how to achieve such a clustering on $n$ points with $O{((k^2 \log n) \cdot m{(Q, ε^4, δ/ (k\log n))})}$ oracle queries, when the $k$ clusters can be learned with an $ε'$ error and a failure probability $δ'$ using $m(Q, ε',δ')$ labeled samples in the supervised setting, where $Q$ is the set of candidate cluster centers. We show that $m(Q, ε', δ')$ is small both for $k$-means instances in Euclidean space and for those in finite metric spaces. We further show that, for the Euclidean $k$-means instances, we can avoid the dependency on $n$ in the query complexity at the expense of an increased dependency on $k$: specifically, we give a slightly more involved algorithm that uses $O(k^4/(ε^2 δ) + (k^{9}/ε^4) \log(1/δ) + k \cdot m(\mathbb{R}^r, ε^4/k, δ))$ oracle queries. We also show that the number of queries needed for $(1 - ε)$-accuracy in Euclidean $k$-means must linearly depend on the dimension of the underlying Euclidean space, and for finite metric space $k$-means, we show that it must at least be logarithmic in the number of candidate centers. This shows that our query complexities capture the right dependencies on the respective parameters.
Multimodal Registration of Retinal Images Using Domain-Specific Landmarks and Vessel Enhancement
Venue: arXiv cs.CV 2018
Year: 2018

The analysis of different image modalities is frequently performed in ophthalmology as it provides complementary information for the diagnosis and follow-up of relevant diseases, like hypertension or diabetes. This work presents a hybrid method for the multimodal registration of color fundus retinography and fluorescein angiography. The proposed method combines a feature-based approach, using domain-specific landmarks, with an intensity-based approach that employs a domain-adapted similarity metric. The methodology is tested on a dataset of 59 image pairs containing both healthy and pathological cases. The results show a satisfactory performance of the proposed combined approach in this multimodal scenario, improving the registration accuracy achieved by the feature-based and the intensity-based approaches.
PRESISTANT: Learning based assistant for data pre-processing
Venue: arXiv cs.LG 2018
Year: 2018

Data pre-processing is one of the most time consuming and relevant steps in a data analysis process (e.g., classification task). A given data pre-processing operator (e.g., transformation) can have positive, negative or zero impact on the final result of the analysis. Expert users have the required knowledge to find the right pre-processing operators. However, when it comes to non-experts, they are overwhelmed by the amount of pre-processing operators and it is challenging for them to find operators that would positively impact their analysis (e.g., increase the predictive accuracy of a classifier). Existing solutions either assume that users have expert knowledge, or they recommend pre-processing operators that are only "syntactically" applicable to a dataset, without taking into account their impact on the final analysis. In this work, we aim at providing assistance to non-expert users by recommending data pre-processing operators that are ranked according to their impact on the final analysis. We developed a tool PRESISTANT, that uses Random Forests to learn the impact of pre-processing operators on the performance (e.g., predictive accuracy) of 5 different classification algorithms, such as J48, Naive Bayes, PART, Logistic Regression, and Nearest Neighbor. Extensive evaluations on the recommendations provided by our tool, show that PRESISTANT can effectively help non-experts in order to achieve improved results in their analytical tasks.
Chest X-Ray Analysis of Tuberculosis by Deep Learning with Segmentation and Augmentation
Venue: arXiv cs.LG 2018
Year: 2018

The results of chest X-ray (CXR) analysis of 2D images to get the statistically reliable predictions (availability of tuberculosis) by computer-aided diagnosis (CADx) on the basis of deep learning are presented. They demonstrate the efficiency of lung segmentation, lossless and lossy data augmentation for CADx of tuberculosis by deep convolutional neural network (CNN) applied to the small and not well-balanced dataset even. CNN demonstrates ability to train (despite overfitting) on the pre-processed dataset obtained after lung segmentation in contrast to the original not-segmented dataset. Lossless data augmentation of the segmented dataset leads to the lowest validation loss (without overfitting) and nearly the same accuracy (within the limits of standard deviation) in comparison to the original and other pre-processed datasets after lossy data augmentation. The additional limited lossy data augmentation results in the lower validation loss, but with a decrease of the validation accuracy. In conclusion, besides the more complex deep CNNs and bigger datasets, the better progress of CADx for the small and not well-balanced datasets even could be obtained by better segmentation, data augmentation, dataset stratification, and exclusion of non-evident outliers.
Understanding and Improving Multi-Sense Word Embeddings via Extended Robust Principal Component Analysis
Venue: arXiv cs.CL 2018
Year: 2018

Unsupervised learned representations of polysemous words generate a large of pseudo multi senses since unsupervised methods are overly sensitive to contextual variations. In this paper, we address the pseudo multi-sense detection for word embeddings by dimensionality reduction of sense pairs. We propose a novel principal analysis method, termed Ex-RPCA, designed to detect both pseudo multi senses and real multi senses. With Ex-RPCA, we empirically show that pseudo multi senses are generated systematically in unsupervised method. Moreover, the multi-sense word embeddings can by improved by a simple linear transformation based on Ex-RPCA. Our improved word embedding outperform the original one by 5.6 points on Stanford contextual word similarity (SCWS) dataset. We hope our simple yet effective approach will help the linguistic analysis of multi-sense word embeddings in the future.
AntShield: On-Device Detection of Personal Information Exposure
Venue: arXiv cs.NI 2018
Year: 2018

Mobile devices have access to personal, potentially sensitive data, and there is a growing number of applications that transmit this personally identifiable information (PII) over the network. In this paper, we present the AntShield system that performs on-device packet-level monitoring and detects the transmission of such sensitive information accurately and in real-time. A key insight is to distinguish PII that is predefined and is easily available on the device from PII that is unknown a priori but can be automatically detected by classifiers. Our system not only combines, for the first time, the advantages of on-device monitoring with the power of learning unknown PII, but also outperforms either of the two approaches alone. We demonstrate the real-time performance of our prototype as well as the classification performance using a dataset that we collect and analyze from scratch (including new findings in terms of leaks and patterns). AntShield is a first step towards enabling distributed learning of private information exposure.
An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling
Venue: arXiv cs.LG 2018
Year: 2018

For most deep learning practitioners, sequence modeling is synonymous with recurrent networks. Yet recent results indicate that convolutional architectures can outperform recurrent networks on tasks such as audio synthesis and machine translation. Given a new sequence modeling task or dataset, which architecture should one use? We conduct a systematic evaluation of generic convolutional and recurrent architectures for sequence modeling. The models are evaluated across a broad range of standard tasks that are commonly used to benchmark recurrent networks. Our results indicate that a simple convolutional architecture outperforms canonical recurrent networks such as LSTMs across a diverse range of tasks and datasets, while demonstrating longer effective memory. We conclude that the common association between sequence modeling and recurrent networks should be reconsidered, and convolutional networks should be regarded as a natural starting point for sequence modeling tasks. To assist related work, we have made code available at http://github.com/locuslab/TCN .
Highly Cited Papers of Ukrainian Scientists Written in Collaboration: A Bibliometric Analysis (2011-2015)
Venue: arXiv cs.DL 2018
Year: 2018

The paper presents the results of the study of international and national cooperation of Ukrainian scientists from different scientific fields using citation analysis data from Scopus in the period of 2011-2015. The results show that during the period under study, the number of documents of highly cited Ukrainian scientists that have received enough citations to be included to the top 1%, 5% and 10% most cited documents in the world, evidenced an increase and were significantly different in different subjects areas. Papers written by a group of co-authors predominate among highly cited documents of Ukrainian scientists. Consequently, international cooperation plays an important role in Ukrainian scientists research results visibility and impact. At the same time, up to 16%-27% highly cited articles of Ukrainian scientists have been written without partnering with foreign colleagues, that means a significant part of important scientific results in Ukraine are carried out by oneself. Therefore, for generating an optimal policy of science development in Ukraine it is important to provide a balanced view of the expectations of the results of the international cooperation of Ukrainian scientists and achieving a required balance between the inter-country and international collaboration.
Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices
Venue: arXiv cs.DM 2018
Year: 2018

The switch Markov chain has been extensively studied as the most natural Markov Chain Monte Carlo approach for sampling graphs with prescribed degree sequences. We use comparison arguments with other, less natural but simpler to analyze, Markov chains, to show that the switch chain mixes rapidly in two different settings. We first study the classic problem of uniformly sampling simple undirected, as well as bipartite, graphs with a given degree sequence. We apply an embedding argument, involving a Markov chain defined by Jerrum and Sinclair (TCS, 1990) for sampling graphs that almost have a given degree sequence, to show rapid mixing for degree sequences satisfying strong stability, a notion closely related to $P$-stability. This results in a much shorter proof that unifies the currently known rapid mixing results of the switch chain and extends them up to sharp characterizations of $P$-stability. In particular, our work resolves an open problem posed by Greenhill (SODA, 2015). Secondly, in order to illustrate the power of our approach, we study the problem of uniformly sampling graphs for which, in addition to the degree sequence, a joint degree distribution is given. Although the problem was formalized over a decade ago, and despite its practical significance in generating synthetic network topologies, small progress has been made on the random sampling of such graphs. The case of a single degree class reduces to sampling of regular graphs, but beyond this almost nothing is known. We fully resolve the case of two degree classes, by showing that the switch Markov chain is always rapidly mixing. Again, we first analyze an auxiliary chain for strongly stable instances on an augmented state space and then use an embedding argument.
Classification based Grasp Detection using Spatial Transformer Network
Venue: arXiv cs.CV 2018
Year: 2018

Robotic grasp detection task is still challenging, particularly for novel objects. With the recent advance of deep learning, there have been several works on detecting robotic grasp using neural networks. Typically, regression based grasp detection methods have outperformed classification based detection methods in computation complexity with excellent accuracy. However, classification based robotic grasp detection still seems to have merits such as intermediate step observability and straightforward back propagation routine for end-to-end training. In this work, we propose a novel classification based robotic grasp detection method with multiple-stage spatial transformer networks (STN). Our proposed method was able to achieve state-of-the-art performance in accuracy with real- time computation. Additionally, unlike other regression based grasp detection methods, our proposed method allows partial observation for intermediate results such as grasp location and orientation for a number of grasp configuration candidates.
Two-Dimensional Block Trees
Venue: arXiv cs.DS 2018
Year: 2018

The Block Tree (BT) is a novel compact data structure designed to compress sequence collections. It obtains compression ratios close to Lempel-Ziv and supports efficient direct access to any substring. The BT divides the text recursively into fixed-size blocks and those appearing earlier are represented with pointers. On repetitive collections, a few blocks can represent all the others, and thus the BT reduces the size by orders of magnitude. In this paper we extend the BT to two dimensions, to exploit repetitiveness in collections of images, graphs, and maps. This two-dimensional Block Tree divides the image regularly into subimages and replaces some of them by pointers to other occurrences thereof. We develop a specific variant aimed at compressing the adjacency matrices of Web graphs, obtaining space reductions of up to 50\% compared with the $k^2$-tree, which is the best alternative supporting direct and reverse navigation in the graph.
Concatenated Power Mean Word Embeddings as Universal Cross-Lingual Sentence Representations
Venue: arXiv cs.CL 2018
Year: 2018

Average word embeddings are a common baseline for more sophisticated sentence embedding techniques. However, they typically fall short of the performances of more complex models such as InferSent. Here, we generalize the concept of average word embeddings to power mean word embeddings. We show that the concatenation of different types of power mean word embeddings considerably closes the gap to state-of-the-art methods monolingually and substantially outperforms these more complex techniques cross-lingually. In addition, our proposed method outperforms different recently proposed baselines such as SIF and Sent2Vec by a solid margin, thus constituting a much harder-to-beat monolingual baseline. Our data and code are publicly available.