July 27, 2019

3137 words 15 mins read

Paper Group ANR 616

Sketching the order of events. Leveraging multiple datasets for deep leaf counting. A Bayesian Perspective on Generalization and Stochastic Gradient Descent. Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking. Flow Fields: Dense Correspondence Fields for Highly Accurate Large Displacement Optical Flow Estimation. Online Learni …

Sketching the order of events


Title	Sketching the order of events
Authors	Terry Lyons, Harald Oberhauser
Abstract	We introduce features for massive data streams. These stream features can be thought of as “ordered moments” and generalize stream sketches from “moments of order one” to “ordered moments of arbitrary order”. In analogy to classic moments, they have theoretical guarantees such as universality that are important for learning algorithms.
Tasks
Published	2017-08-31
URL	http://arxiv.org/abs/1708.09708v1
PDF	http://arxiv.org/pdf/1708.09708v1.pdf
PWC	https://paperswithcode.com/paper/sketching-the-order-of-events
Repo
Framework

Leveraging multiple datasets for deep leaf counting


Title	Leveraging multiple datasets for deep leaf counting
Authors	Andrei Dobrescu, Mario Valerio Giuffrida, Sotirios A Tsaftaris
Abstract	The number of leaves a plant has is one of the key traits (phenotypes) describing its development and growth. Here, we propose an automated, deep learning based approach for counting leaves in model rosette plants. While state-of-the-art results on leaf counting with deep learning methods have recently been reported, they obtain the count as a result of leaf segmentation and thus require per-leaf (instance) segmentation to train the models (a rather strong annotation). Instead, our method treats leaf counting as a direct regression problem and thus only requires as annotation the total leaf count per plant. We argue that combining different datasets when training a deep neural network is beneficial and improves the results of the proposed approach. We evaluate our method on the CVPPP 2017 Leaf Counting Challenge dataset, which contains images of Arabidopsis and tobacco plants. Experimental results show that the proposed method significantly outperforms the winner of the previous CVPPP challenge, improving the results by a minimum of ~50% on each of the test datasets, and can achieve this performance without knowing the experimental origin of the data (i.e. in the wild setting of the challenge). We also compare the counting accuracy of our model with that of per leaf segmentation algorithms, achieving a 20% decrease in mean absolute difference in count (DiC).
Tasks	Instance Segmentation, Semantic Segmentation
Published	2017-09-05
URL	http://arxiv.org/abs/1709.01472v1
PDF	http://arxiv.org/pdf/1709.01472v1.pdf
PWC	https://paperswithcode.com/paper/leveraging-multiple-datasets-for-deep-leaf
Repo
Framework

A Bayesian Perspective on Generalization and Stochastic Gradient Descent


Title	A Bayesian Perspective on Generalization and Stochastic Gradient Descent
Authors	Samuel L. Smith, Quoc V. Le
Abstract	We consider two questions at the heart of machine learning; how can we predict if a minimum will generalize to the test set, and why does stochastic gradient descent find minima that generalize well? Our work responds to Zhang et al. (2016), who showed deep neural networks can easily memorize randomly labeled training data, despite generalizing well on real labels of the same inputs. We show that the same phenomenon occurs in small linear models. These observations are explained by the Bayesian evidence, which penalizes sharp minima but is invariant to model parameterization. We also demonstrate that, when one holds the learning rate fixed, there is an optimum batch size which maximizes the test set accuracy. We propose that the noise introduced by small mini-batches drives the parameters towards minima whose evidence is large. Interpreting stochastic gradient descent as a stochastic differential equation, we identify the “noise scale” $g = \epsilon (\frac{N}{B} - 1) \approx \epsilon N/B$, where $\epsilon$ is the learning rate, $N$ the training set size and $B$ the batch size. Consequently the optimum batch size is proportional to both the learning rate and the size of the training set, $B_{opt} \propto \epsilon N$. We verify these predictions empirically.
Tasks
Published	2017-10-17
URL	http://arxiv.org/abs/1710.06451v3
PDF	http://arxiv.org/pdf/1710.06451v3.pdf
PWC	https://paperswithcode.com/paper/a-bayesian-perspective-on-generalization-and
Repo
Framework

Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking


Title	Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
Authors	Yuxin Chen, Jianqing Fan, Cong Ma, Kaizheng Wang
Abstract	This paper is concerned with the problem of top-$K$ ranking from pairwise comparisons. Given a collection of $n$ items and a few pairwise comparisons across them, one wishes to identify the set of $K$ items that receive the highest ranks. To tackle this problem, we adopt the logistic parametric model — the Bradley-Terry-Luce model, where each item is assigned a latent preference score, and where the outcome of each pairwise comparison depends solely on the relative scores of the two items involved. Recent works have made significant progress towards characterizing the performance (e.g. the mean square error for estimating the scores) of several classical methods, including the spectral method and the maximum likelihood estimator (MLE). However, where they stand regarding top-$K$ ranking remains unsettled. We demonstrate that under a natural random sampling model, the spectral method alone, or the regularized MLE alone, is minimax optimal in terms of the sample complexity — the number of paired comparisons needed to ensure exact top-$K$ identification, for the fixed dynamic range regime. This is accomplished via optimal control of the entrywise error of the score estimates. We complement our theoretical studies by numerical experiments, confirming that both methods yield low entrywise errors for estimating the underlying scores. Our theory is established via a novel leave-one-out trick, which proves effective for analyzing both iterative and non-iterative procedures. Along the way, we derive an elementary eigenvector perturbation bound for probability transition matrices, which parallels the Davis-Kahan $\sin\Theta$ theorem for symmetric matrices. This also allows us to close the gap between the $\ell_2$ error upper bound for the spectral method and the minimax lower limit.
Tasks
Published	2017-07-31
URL	http://arxiv.org/abs/1707.09971v3
PDF	http://arxiv.org/pdf/1707.09971v3.pdf
PWC	https://paperswithcode.com/paper/spectral-method-and-regularized-mle-are-both
Repo
Framework

Flow Fields: Dense Correspondence Fields for Highly Accurate Large Displacement Optical Flow Estimation


Title	Flow Fields: Dense Correspondence Fields for Highly Accurate Large Displacement Optical Flow Estimation
Authors	Christian Bailer, Bertram Taetz, Didier Stricker
Abstract	Modern large displacement optical flow algorithms usually use an initialization by either sparse descriptor matching techniques or dense approximate nearest neighbor fields. While the latter have the advantage of being dense, they have the major disadvantage of being very outlier-prone as they are not designed to find the optical flow, but the visually most similar correspondence. In this article we present a dense correspondence field approach that is much less outlier-prone and thus much better suited for optical flow estimation than approximate nearest neighbor fields. Our approach does not require explicit regularization, smoothing (like median filtering) or a new data term. Instead we solely rely on patch matching techniques and a novel multi-scale matching strategy. We also present enhancements for outlier filtering. We show that our approach is better suited for large displacement optical flow estimation than modern descriptor matching techniques. We do so by initializing EpicFlow with our approach instead of their originally used state-of-the-art descriptor matching technique. We significantly outperform the original EpicFlow on MPI-Sintel, KITTI 2012, KITTI 2015 and Middlebury. In this extended article of our former conference publication we further improve our approach in matching accuracy as well as runtime and present more experiments and insights.
Tasks	Optical Flow Estimation
Published	2017-03-07
URL	http://arxiv.org/abs/1703.02563v2
PDF	http://arxiv.org/pdf/1703.02563v2.pdf
PWC	https://paperswithcode.com/paper/flow-fields-dense-correspondence-fields-for
Repo
Framework

Online Learning of Optimal Bidding Strategy in Repeated Multi-Commodity Auctions


Title	Online Learning of Optimal Bidding Strategy in Repeated Multi-Commodity Auctions
Authors	Sevi Baltaoglu, Lang Tong, Qing Zhao
Abstract	We study the online learning problem of a bidder who participates in repeated auctions. With the goal of maximizing his T-period payoff, the bidder determines the optimal allocation of his budget among his bids for $K$ goods at each period. As a bidding strategy, we propose a polynomial-time algorithm, inspired by the dynamic programming approach to the knapsack problem. The proposed algorithm, referred to as dynamic programming on discrete set (DPDS), achieves a regret order of $O(\sqrt{T\log{T}})$. By showing that the regret is lower bounded by $\Omega(\sqrt{T})$ for any strategy, we conclude that DPDS is order optimal up to a $\sqrt{\log{T}}$ term. We evaluate the performance of DPDS empirically in the context of virtual trading in wholesale electricity markets by using historical data from the New York market. Empirical results show that DPDS consistently outperforms benchmark heuristic methods that are derived from machine learning and online learning approaches.
Tasks
Published	2017-03-07
URL	http://arxiv.org/abs/1703.02567v5
PDF	http://arxiv.org/pdf/1703.02567v5.pdf
PWC	https://paperswithcode.com/paper/online-learning-of-optimal-bidding-strategy
Repo
Framework

Co-saliency Detection for RGBD Images Based on Multi-constraint Feature Matching and Cross Label Propagation


Title	Co-saliency Detection for RGBD Images Based on Multi-constraint Feature Matching and Cross Label Propagation
Authors	Runmin Cong, Jianjun Lei, Huazhu Fu, Qingming Huang, Xiaochun Cao, Chunping Hou
Abstract	Co-saliency detection aims at extracting the common salient regions from an image group containing two or more relevant images. It is a newly emerging topic in computer vision community. Different from the most existing co-saliency methods focusing on RGB images, this paper proposes a novel co-saliency detection model for RGBD images, which utilizes the depth information to enhance identification of co-saliency. First, the intra saliency map for each image is generated by the single image saliency model, while the inter saliency map is calculated based on the multi-constraint feature matching, which represents the constraint relationship among multiple images. Then, the optimization scheme, namely Cross Label Propagation (CLP), is used to refine the intra and inter saliency maps in a cross way. Finally, all the original and optimized saliency maps are integrated to generate the final co-saliency result. The proposed method introduces the depth information and multi-constraint feature matching to improve the performance of co-saliency detection. Moreover, the proposed method can effectively exploit any existing single image saliency model to work well in co-saliency scenarios. Experiments on two RGBD co-saliency datasets demonstrate the effectiveness of our proposed model.
Tasks	Co-Saliency Detection, Saliency Detection
Published	2017-10-14
URL	http://arxiv.org/abs/1710.05172v1
PDF	http://arxiv.org/pdf/1710.05172v1.pdf
PWC	https://paperswithcode.com/paper/co-saliency-detection-for-rgbd-images-based
Repo
Framework

CoNLL-SIGMORPHON 2017 Shared Task: Universal Morphological Reinflection in 52 Languages


Title	CoNLL-SIGMORPHON 2017 Shared Task: Universal Morphological Reinflection in 52 Languages
Authors	Ryan Cotterell, Christo Kirov, John Sylak-Glassman, Géraldine Walther, Ekaterina Vylomova, Patrick Xia, Manaal Faruqui, Sandra Kübler, David Yarowsky, Jason Eisner, Mans Hulden
Abstract	The CoNLL-SIGMORPHON 2017 shared task on supervised morphological generation required systems to be trained and tested in each of 52 typologically diverse languages. In sub-task 1, submitted systems were asked to predict a specific inflected form of a given lemma. In sub-task 2, systems were given a lemma and some of its specific inflected forms, and asked to complete the inflectional paradigm by predicting all of the remaining inflected forms. Both sub-tasks included high, medium, and low-resource conditions. Sub-task 1 received 24 system submissions, while sub-task 2 received 3 system submissions. Following the success of neural sequence-to-sequence models in the SIGMORPHON 2016 shared task, all but one of the submissions included a neural component. The results show that high performance can be achieved with small training datasets, so long as models have appropriate inductive bias or make use of additional unlabeled data or synthetic data. However, different biasing and data augmentation resulted in disjoint sets of inflected forms being predicted correctly, suggesting that there is room for future improvement.
Tasks	Data Augmentation
Published	2017-06-27
URL	http://arxiv.org/abs/1706.09031v2
PDF	http://arxiv.org/pdf/1706.09031v2.pdf
PWC	https://paperswithcode.com/paper/conll-sigmorphon-2017-shared-task-universal
Repo
Framework

Racing Thompson: an Efficient Algorithm for Thompson Sampling with Non-conjugate Priors


Title	Racing Thompson: an Efficient Algorithm for Thompson Sampling with Non-conjugate Priors
Authors	Yichi Zhou, Jun Zhu, Jingwei Zhuo
Abstract	Thompson sampling has impressive empirical performance for many multi-armed bandit problems. But current algorithms for Thompson sampling only work for the case of conjugate priors since these algorithms require to infer the posterior, which is often computationally intractable when the prior is not conjugate. In this paper, we propose a novel algorithm for Thompson sampling which only requires to draw samples from a tractable distribution, so our algorithm is efficient even when the prior is non-conjugate. To do this, we reformulate Thompson sampling as an optimization problem via the Gumbel-Max trick. After that we construct a set of random variables and our goal is to identify the one with highest mean. Finally, we solve it with techniques in best arm identification.
Tasks
Published	2017-08-16
URL	http://arxiv.org/abs/1708.04781v1
PDF	http://arxiv.org/pdf/1708.04781v1.pdf
PWC	https://paperswithcode.com/paper/racing-thompson-an-efficient-algorithm-for
Repo
Framework

Accelerated Parallel Non-conjugate Sampling for Bayesian Non-parametric Models


Title	Accelerated Parallel Non-conjugate Sampling for Bayesian Non-parametric Models
Authors	Michael Minyi Zhang, Sinead A. Williamson, Fernando Perez-Cruz
Abstract	Inference of latent feature models in the Bayesian nonparametric setting is generally difficult, especially in high dimensional settings, because it usually requires proposing features from some prior distribution. In special cases, where the integration is tractable, we could sample new feature assignments according to a predictive likelihood. However, this still may not be efficient in high dimensions. We present a novel method to accelerate the mixing of latent variable model inference by proposing feature locations from the data, as opposed to the prior. First, we introduce our accelerated feature proposal mechanism that we will show is a valid Bayesian inference algorithm and next we propose an approximate inference strategy to perform accelerated inference in parallel. This sampling method is efficient for proper mixing of the Markov chain Monte Carlo sampler, computationally attractive, and is theoretically guaranteed to converge to the posterior distribution as its limiting distribution.
Tasks	Bayesian Inference
Published	2017-05-19
URL	https://arxiv.org/abs/1705.07178v4
PDF	https://arxiv.org/pdf/1705.07178v4.pdf
PWC	https://paperswithcode.com/paper/accelerated-inference-for-latent-variable
Repo
Framework

Deep Self-Taught Learning for Weakly Supervised Object Localization


Title	Deep Self-Taught Learning for Weakly Supervised Object Localization
Authors	Zequn Jie, Yunchao Wei, Xiaojie Jin, Jiashi Feng, Wei Liu
Abstract	Most existing weakly supervised localization (WSL) approaches learn detectors by finding positive bounding boxes based on features learned with image-level supervision. However, those features do not contain spatial location related information and usually provide poor-quality positive samples for training a detector. To overcome this issue, we propose a deep self-taught learning approach, which makes the detector learn the object-level features reliable for acquiring tight positive samples and afterwards re-train itself based on them. Consequently, the detector progressively improves its detection ability and localizes more informative positive samples. To implement such self-taught learning, we propose a seed sample acquisition method via image-to-object transferring and dense subgraph discovery to find reliable positive samples for initializing the detector. An online supportive sample harvesting scheme is further proposed to dynamically select the most confident tight positive samples and train the detector in a mutual boosting way. To prevent the detector from being trapped in poor optima due to overfitting, we propose a new relative improvement of predicted CNN scores for guiding the self-taught learning process. Extensive experiments on PASCAL 2007 and 2012 show that our approach outperforms the state-of-the-arts, strongly validating its effectiveness.
Tasks	Object Localization, Weakly Supervised Object Detection, Weakly-Supervised Object Localization
Published	2017-04-18
URL	http://arxiv.org/abs/1704.05188v2
PDF	http://arxiv.org/pdf/1704.05188v2.pdf
PWC	https://paperswithcode.com/paper/deep-self-taught-learning-for-weakly
Repo
Framework

Neural Rating Regression with Abstractive Tips Generation for Recommendation


Title	Neural Rating Regression with Abstractive Tips Generation for Recommendation
Authors	Piji Li, Zihao Wang, Zhaochun Ren, Lidong Bing, Wai Lam
Abstract	Recently, some E-commerce sites launch a new interaction box called Tips on their mobile apps. Users can express their experience and feelings or provide suggestions using short texts typically several words or one sentence. In essence, writing some tips and giving a numerical rating are two facets of a user’s product assessment action, expressing the user experience and feelings. Jointly modeling these two facets is helpful for designing a better recommendation system. While some existing models integrate text information such as item specifications or user reviews into user and item latent factors for improving the rating prediction, no existing works consider tips for improving recommendation quality. We propose a deep learning based framework named NRT which can simultaneously predict precise ratings and generate abstractive tips with good linguistic quality simulating user experience and feelings. For abstractive tips generation, gated recurrent neural networks are employed to “translate” user and item latent representations into a concise sentence. Extensive experiments on benchmark datasets from different domains show that NRT achieves significant improvements over the state-of-the-art methods. Moreover, the generated tips can vividly predict the user experience and feelings.
Tasks
Published	2017-08-01
URL	http://arxiv.org/abs/1708.00154v1
PDF	http://arxiv.org/pdf/1708.00154v1.pdf
PWC	https://paperswithcode.com/paper/neural-rating-regression-with-abstractive
Repo
Framework

p-FP: Extraction, Classification, and Prediction of Website Fingerprints with Deep Learning


Title	p-FP: Extraction, Classification, and Prediction of Website Fingerprints with Deep Learning
Authors	Se Eun Oh, Saikrishna Sunkam, Nicholas Hopper
Abstract	Recent advances in learning Deep Neural Network (DNN) architectures have received a great deal of attention due to their ability to outperform state-of-the-art classifiers across a wide range of applications, with little or no feature engineering. In this paper, we broadly study the applicability of deep learning to website fingerprinting. We show that unsupervised DNNs can be used to extract low-dimensional feature vectors that improve the performance of state-of-the-art website fingerprinting attacks. When used as classifiers, we show that they can match or exceed performance of existing attacks across a range of application scenarios, including fingerprinting Tor website traces, fingerprinting search engine queries over Tor, defeating fingerprinting defenses, and fingerprinting TLS-encrypted websites. Finally, we show that DNNs can be used to predict the fingerprintability of a website based on its contents, achieving 99% accuracy on a data set of 4500 website downloads.
Tasks	Feature Engineering
Published	2017-11-10
URL	http://arxiv.org/abs/1711.03656v2
PDF	http://arxiv.org/pdf/1711.03656v2.pdf
PWC	https://paperswithcode.com/paper/p-fp-extraction-classification-and-prediction
Repo
Framework

Deep Learning for Secure Mobile Edge Computing


Title	Deep Learning for Secure Mobile Edge Computing
Authors	Yuanfang Chen, Yan Zhang, Sabita Maharjan
Abstract	Mobile edge computing (MEC) is a promising approach for enabling cloud-computing capabilities at the edge of cellular networks. Nonetheless, security is becoming an increasingly important issue in MEC-based applications. In this paper, we propose a deep-learning-based model to detect security threats. The model uses unsupervised learning to automate the detection process, and uses location information as an important feature to improve the performance of detection. Our proposed model can be used to detect malicious applications at the edge of a cellular network, which is a serious security threat. Extensive experiments are carried out with 10 different datasets, the results of which illustrate that our deep-learning-based model achieves an average gain of 6% accuracy compared with state-of-the-art machine learning algorithms.
Tasks
Published	2017-09-23
URL	http://arxiv.org/abs/1709.08025v1
PDF	http://arxiv.org/pdf/1709.08025v1.pdf
PWC	https://paperswithcode.com/paper/deep-learning-for-secure-mobile-edge
Repo
Framework

Double/Debiased/Neyman Machine Learning of Treatment Effects


Title	Double/Debiased/Neyman Machine Learning of Treatment Effects
Authors	Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey
Abstract	Chernozhukov, Chetverikov, Demirer, Duflo, Hansen, and Newey (2016) provide a generic double/de-biased machine learning (DML) approach for obtaining valid inferential statements about focal parameters, using Neyman-orthogonal scores and cross-fitting, in settings where nuisance parameters are estimated using a new generation of nonparametric fitting methods for high-dimensional data, called machine learning methods. In this note, we illustrate the application of this method in the context of estimating average treatment effects (ATE) and average treatment effects on the treated (ATTE) using observational data. A more general discussion and references to the existing literature are available in Chernozhukov, Chetverikov, Demirer, Duflo, Hansen, and Newey (2016).
Tasks
Published	2017-01-30
URL	http://arxiv.org/abs/1701.08687v1
PDF	http://arxiv.org/pdf/1701.08687v1.pdf
PWC	https://paperswithcode.com/paper/doubledebiasedneyman-machine-learning-of
Repo
Framework