May 6, 2019

2949 words 14 mins read

Paper Group ANR 425

Étude de Problèmes d’Optimisation Combinatoire à Multiples Composantes Interdépendantes. Density Matching Reward Learning. Application of the Signature Method to Pattern Recognition in the CEQUEL Clinical Trial. Predicting with Distributions. Multiplicative LSTM for sequence modelling. Robust Influence Maximization. Bayesian Nonparametric Modeling …

Étude de Problèmes d’Optimisation Combinatoire à Multiples Composantes Interdépendantes


Title	Étude de Problèmes d’Optimisation Combinatoire à Multiples Composantes Interdépendantes
Authors	Mohamed El Yafrani, Belaïd Ahiod
Abstract	This extended abstract presents an overview on NP-hard optimization problems with multiple interdependent components. These problems occur in many real-world applications: industrial applications, engineering, and logistics. The fact that these problems are composed of many sub-problems that are NP-hard makes them even more challenging to solve using exact algorithms. This is mainly due to the high complexity of this class of algorithms and the hardness of the problems themselves. The main source of difficulty of these problems is the presence of internal dependencies between sub-problems. This aspect of interdependence of components is presented, and some outlines on solving approaches are briefly introduced from a (meta)heuristics and evolutionary computation perspective.
Tasks
Published	2016-06-22
URL	http://arxiv.org/abs/1606.06797v1
PDF	http://arxiv.org/pdf/1606.06797v1.pdf
PWC	https://paperswithcode.com/paper/etude-de-problemes-doptimisation-combinatoire
Repo
Framework

Density Matching Reward Learning


Title	Density Matching Reward Learning
Authors	Sungjoon Choi, Kyungjae Lee, Andy Park, Songhwai Oh
Abstract	In this paper, we focus on the problem of inferring the underlying reward function of an expert given demonstrations, which is often referred to as inverse reinforcement learning (IRL). In particular, we propose a model-free density-based IRL algorithm, named density matching reward learning (DMRL), which does not require model dynamics. The performance of DMRL is analyzed theoretically and the sample complexity is derived. Furthermore, the proposed DMRL is extended to handle nonlinear IRL problems by assuming that the reward function is in the reproducing kernel Hilbert space (RKHS) and kernel DMRL (KDMRL) is proposed. The parameters for KDMRL can be computed analytically, which greatly reduces the computation time. The performance of KDMRL is extensively evaluated in two sets of experiments: grid world and track driving experiments. In grid world experiments, the proposed KDMRL method is compared with both model-based and model-free IRL methods and shows superior performance on a nonlinear reward setting and competitive performance on a linear reward setting in terms of expected value differences. Then we move on to more realistic experiments of learning different driving styles for autonomous navigation in complex and dynamic tracks using KDMRL and receding horizon control.
Tasks	Autonomous Navigation
Published	2016-08-12
URL	http://arxiv.org/abs/1608.03694v1
PDF	http://arxiv.org/pdf/1608.03694v1.pdf
PWC	https://paperswithcode.com/paper/density-matching-reward-learning
Repo
Framework

Application of the Signature Method to Pattern Recognition in the CEQUEL Clinical Trial


Title	Application of the Signature Method to Pattern Recognition in the CEQUEL Clinical Trial
Authors	A. B. Kormilitzin, K. E. A. Saunders, P. J. Harrison, J. R. Geddes, T. J. Lyons
Abstract	The classification procedure of streaming data usually requires various ad hoc methods or particular heuristic models. We explore a novel non-parametric and systematic approach to analysis of heterogeneous sequential data. We demonstrate an application of this method to classification of the delays in responding to the prompts, from subjects with bipolar disorder collected during a clinical trial, using both synthetic and real examples. We show how this method can provide a natural and systematic way to extract characteristic features from sequential data.
Tasks
Published	2016-06-07
URL	http://arxiv.org/abs/1606.02074v1
PDF	http://arxiv.org/pdf/1606.02074v1.pdf
PWC	https://paperswithcode.com/paper/application-of-the-signature-method-to
Repo
Framework

Predicting with Distributions


Title	Predicting with Distributions
Authors	Michael Kearns, Zhiwei Steven Wu
Abstract	We consider a new learning model in which a joint distribution over vector pairs $(x,y)$ is determined by an unknown function $c(x)$ that maps input vectors $x$ not to individual outputs, but to entire {\em distributions/} over output vectors $y$. Our main results take the form of rather general reductions from our model to algorithms for PAC learning the function class and the distribution class separately, and show that virtually every such combination yields an efficient algorithm in our model. Our methods include a randomized reduction to classification noise and an application of Le Cam’s method to obtain robust learning algorithms.
Tasks
Published	2016-06-03
URL	http://arxiv.org/abs/1606.01275v3
PDF	http://arxiv.org/pdf/1606.01275v3.pdf
PWC	https://paperswithcode.com/paper/predicting-with-distributions
Repo
Framework

Multiplicative LSTM for sequence modelling


Title	Multiplicative LSTM for sequence modelling
Authors	Ben Krause, Liang Lu, Iain Murray, Steve Renals
Abstract	We introduce multiplicative LSTM (mLSTM), a recurrent neural network architecture for sequence modelling that combines the long short-term memory (LSTM) and multiplicative recurrent neural network architectures. mLSTM is characterised by its ability to have different recurrent transition functions for each possible input, which we argue makes it more expressive for autoregressive density estimation. We demonstrate empirically that mLSTM outperforms standard LSTM and its deep variants for a range of character level language modelling tasks. In this version of the paper, we regularise mLSTM to achieve 1.27 bits/char on text8 and 1.24 bits/char on Hutter Prize. We also apply a purely byte-level mLSTM on the WikiText-2 dataset to achieve a character level entropy of 1.26 bits/char, corresponding to a word level perplexity of 88.8, which is comparable to word level LSTMs regularised in similar ways on the same task.
Tasks	Density Estimation, Language Modelling
Published	2016-09-26
URL	http://arxiv.org/abs/1609.07959v3
PDF	http://arxiv.org/pdf/1609.07959v3.pdf
PWC	https://paperswithcode.com/paper/multiplicative-lstm-for-sequence-modelling
Repo
Framework

Robust Influence Maximization


Title	Robust Influence Maximization
Authors	Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, Xuren Zhou
Abstract	In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem — the task of finding $k$ seed nodes in a social network to maximize the influence spread. We propose the problem of robust influence maximization, which maximizes the worst-case ratio between the influence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We design an algorithm that solves this problem with a solution-dependent bound. We further study uniform sampling and adaptive sampling methods to effectively reduce the uncertainty on parameters and improve the robustness of the influence maximization task. Our empirical results show that parameter uncertainty may greatly affect influence maximization performance and prior studies that learned influence probabilities could lead to poor performance in robust influence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an effective way to improve the robustness of influence maximization.
Tasks
Published	2016-01-25
URL	http://arxiv.org/abs/1601.06551v2
PDF	http://arxiv.org/pdf/1601.06551v2.pdf
PWC	https://paperswithcode.com/paper/robust-influence-maximization
Repo
Framework

Bayesian Nonparametric Modeling of Heterogeneous Groups of Censored Data


Title	Bayesian Nonparametric Modeling of Heterogeneous Groups of Censored Data
Authors	Alexandre Piché, Russell Steele, Ian Shrier, Stephanie Long
Abstract	Datasets containing large samples of time-to-event data arising from several small heterogeneous groups are commonly encountered in statistics. This presents problems as they cannot be pooled directly due to their heterogeneity or analyzed individually because of their small sample size. Bayesian nonparametric modelling approaches can be used to model such datasets given their ability to flexibly share information across groups. In this paper, we will compare three popular Bayesian nonparametric methods for modelling the survival functions of heterogeneous groups. Specifically, we will first compare the modelling accuracy of the Dirichlet process, the hierarchical Dirichlet process, and the nested Dirichlet process on simulated datasets of different sizes, where group survival curves differ in shape or in expectation. We, then, will compare the models on a real-world injury dataset.
Tasks
Published	2016-10-24
URL	http://arxiv.org/abs/1610.07262v2
PDF	http://arxiv.org/pdf/1610.07262v2.pdf
PWC	https://paperswithcode.com/paper/bayesian-nonparametric-modeling-of
Repo
Framework

Occlusion-Model Guided Anti-Occlusion Depth Estimation in Light Field


Title	Occlusion-Model Guided Anti-Occlusion Depth Estimation in Light Field
Authors	Hao Zhu, Qing Wang, Jingyi Yu
Abstract	Occlusion is one of the most challenging problems in depth estimation. Previous work has modeled the single-occluder occlusion in light field and get good results, however it is still difficult to obtain accurate depth for multi-occluder occlusion. In this paper, we explore the multi-occluder occlusion model in light field, and derive the occluder-consistency between the spatial and angular space which is used as a guidance to select the un-occluded views for each candidate occlusion point. Then an anti-occlusion energy function is built to regularize depth map. The experimental results on public light field datasets have demonstrated the advantages of the proposed algorithm compared with other state-of-the-art light field depth estimation algorithms, especially in multi-occluder areas.
Tasks	Depth Estimation
Published	2016-08-15
URL	http://arxiv.org/abs/1608.04187v2
PDF	http://arxiv.org/pdf/1608.04187v2.pdf
PWC	https://paperswithcode.com/paper/occlusion-model-guided-anti-occlusion-depth
Repo
Framework

External Lexical Information for Multilingual Part-of-Speech Tagging


Title	External Lexical Information for Multilingual Part-of-Speech Tagging
Authors	Benoît Sagot
Abstract	Morphosyntactic lexicons and word vector representations have both proven useful for improving the accuracy of statistical part-of-speech taggers. Here we compare the performances of four systems on datasets covering 16 languages, two of these systems being feature-based (MEMMs and CRFs) and two of them being neural-based (bi-LSTMs). We show that, on average, all four approaches perform similarly and reach state-of-the-art results. Yet better performances are obtained with our feature-based models on lexically richer datasets (e.g. for morphologically rich languages), whereas neural-based results are higher on datasets with less lexical variability (e.g. for English). These conclusions hold in particular for the MEMM models relying on our system MElt, which benefited from newly designed features. This shows that, under certain conditions, feature-based approaches enriched with morphosyntactic lexicons are competitive with respect to neural methods.
Tasks	Part-Of-Speech Tagging
Published	2016-06-12
URL	http://arxiv.org/abs/1606.03676v2
PDF	http://arxiv.org/pdf/1606.03676v2.pdf
PWC	https://paperswithcode.com/paper/external-lexical-information-for-multilingual
Repo
Framework

Stochastic Learning of Multi-Instance Dictionary for Earth Mover’s Distance based Histogram Comparison


Title	Stochastic Learning of Multi-Instance Dictionary for Earth Mover’s Distance based Histogram Comparison
Authors	Jihong Fan, Ru-Ze Liang
Abstract	Dictionary plays an important role in multi-instance data representation. It maps bags of instances to histograms. Earth mover’s distance (EMD) is the most effective histogram distance metric for the application of multi-instance retrieval. However, up to now, there is no existing multi-instance dictionary learning methods designed for EMD based histogram comparison. To fill this gap, we develop the first EMD-optimal dictionary learning method using stochastic optimization method. In the stochastic learning framework, we have one triplet of bags, including one basic bag, one positive bag, and one negative bag. These bags are mapped to histograms using a multi-instance dictionary. We argue that the EMD between the basic histogram and the positive histogram should be smaller than that between the basic histogram and the negative histogram. Base on this condition, we design a hinge loss. By minimizing this hinge loss and some regularization terms of the dictionary, we update the dictionary instances. The experiments over multi-instance retrieval applications shows its effectiveness when compared to other dictionary learning methods over the problems of medical image retrieval and natural language relation classification.
Tasks	Dictionary Learning, Image Retrieval, Medical Image Retrieval, Relation Classification, Stochastic Optimization
Published	2016-09-03
URL	http://arxiv.org/abs/1609.00817v1
PDF	http://arxiv.org/pdf/1609.00817v1.pdf
PWC	https://paperswithcode.com/paper/stochastic-learning-of-multi-instance
Repo
Framework

Is the Bellman residual a bad proxy?


Title	Is the Bellman residual a bad proxy?
Authors	Matthieu Geist, Bilal Piot, Olivier Pietquin
Abstract	This paper aims at theoretically and empirically comparing two standard optimization criteria for Reinforcement Learning: i) maximization of the mean value and ii) minimization of the Bellman residual. For that purpose, we place ourselves in the framework of policy search algorithms, that are usually designed to maximize the mean value, and derive a method that minimizes the residual $\T_* v_\pi - v_\pi_{1,\nu}$ over policies. A theoretical analysis shows how good this proxy is to policy optimization, and notably that it is better than its value-based counterpart. We also propose experiments on randomly generated generic Markov decision processes, specifically designed for studying the influence of the involved concentrability coefficient. They show that the Bellman residual is generally a bad proxy to policy optimization and that directly maximizing the mean value is much better, despite the current lack of deep theoretical analysis. This might seem obvious, as directly addressing the problem of interest is usually better, but given the prevalence of (projected) Bellman residual minimization in value-based reinforcement learning, we believe that this question is worth to be considered.
Tasks
Published	2016-06-24
URL	http://arxiv.org/abs/1606.07636v3
PDF	http://arxiv.org/pdf/1606.07636v3.pdf
PWC	https://paperswithcode.com/paper/is-the-bellman-residual-a-bad-proxy
Repo
Framework

LiDAR Ground Filtering Algorithm for Urban Areas Using Scan Line Based Segmentation


Title	LiDAR Ground Filtering Algorithm for Urban Areas Using Scan Line Based Segmentation
Authors	Lei Wang, Yongun Zhang
Abstract	This paper addresses the task of separating ground points from airborne LiDAR point cloud data in urban areas. A novel ground filtering method using scan line segmentation is proposed here, which we call SLSGF. It utilizes the scan line information in LiDAR data to segment the LiDAR data. The similarity measurements are designed to make it possible to segment complex roof structures into a single segment as much as possible so the topological relationships between the roof and the ground are simpler, which will benefit the labeling process. In the labeling process, the initial ground segments are detected and a coarse to fine labeling scheme is applied. Data from ISPRS 2011 are used to test the accuracy of SLSGF; and our analytical and experimental results show that this method is computationally-efficient and noise-insensitive, thereby making a denoising process unnecessary before filtering.
Tasks	Denoising
Published	2016-03-02
URL	http://arxiv.org/abs/1603.00912v1
PDF	http://arxiv.org/pdf/1603.00912v1.pdf
PWC	https://paperswithcode.com/paper/lidar-ground-filtering-algorithm-for-urban
Repo
Framework

A note on privacy preserving iteratively reweighted least squares


Title	A note on privacy preserving iteratively reweighted least squares
Authors	Mijung Park, Max Welling
Abstract	Iteratively reweighted least squares (IRLS) is a widely-used method in machine learning to estimate the parameters in the generalised linear models. In particular, IRLS for L1 minimisation under the linear model provides a closed-form solution in each step, which is a simple multiplication between the inverse of the weighted second moment matrix and the weighted first moment vector. When dealing with privacy sensitive data, however, developing a privacy preserving IRLS algorithm faces two challenges. First, due to the inversion of the second moment matrix, the usual sensitivity analysis in differential privacy incorporating a single datapoint perturbation gets complicated and often requires unrealistic assumptions. Second, due to its iterative nature, a significant cumulative privacy loss occurs. However, adding a high level of noise to compensate for the privacy loss hinders from getting accurate estimates. Here, we develop a practical algorithm that overcomes these challenges and outputs privatised and accurate IRLS solutions. In our method, we analyse the sensitivity of each moments separately and treat the matrix inversion and multiplication as a post-processing step, which simplifies the sensitivity analysis. Furthermore, we apply the {\it{concentrated differential privacy}} formalism, a more relaxed version of differential privacy, which requires adding a significantly less amount of noise for the same level of privacy guarantee, compared to the conventional and advanced compositions of differentially private mechanisms.
Tasks
Published	2016-05-24
URL	http://arxiv.org/abs/1605.07511v1
PDF	http://arxiv.org/pdf/1605.07511v1.pdf
PWC	https://paperswithcode.com/paper/a-note-on-privacy-preserving-iteratively
Repo
Framework

Large scale biomedical texts classification: a kNN and an ESA-based approaches


Title	Large scale biomedical texts classification: a kNN and an ESA-based approaches
Authors	Khadim Dramé, Fleur Mougin, Gayo Diallo
Abstract	With the large and increasing volume of textual data, automated methods for identifying significant topics to classify textual documents have received a growing interest. While many efforts have been made in this direction, it still remains a real challenge. Moreover, the issue is even more complex as full texts are not always freely available. Then, using only partial information to annotate these documents is promising but remains a very ambitious issue. MethodsWe propose two classification methods: a k-nearest neighbours (kNN)-based approach and an explicit semantic analysis (ESA)-based approach. Although the kNN-based approach is widely used in text classification, it needs to be improved to perform well in this specific classification problem which deals with partial information. Compared to existing kNN-based methods, our method uses classical Machine Learning (ML) algorithms for ranking the labels. Additional features are also investigated in order to improve the classifiers’ performance. In addition, the combination of several learning algorithms with various techniques for fixing the number of relevant topics is performed. On the other hand, ESA seems promising for this classification task as it yielded interesting results in related issues, such as semantic relatedness computation between texts and text classification. Unlike existing works, which use ESA for enriching the bag-of-words approach with additional knowledge-based features, our ESA-based method builds a standalone classifier. Furthermore, we investigate if the results of this method could be useful as a complementary feature of our kNN-based approach.ResultsExperimental evaluations performed on large standard annotated datasets, provided by the BioASQ organizers, show that the kNN-based method with the Random Forest learning algorithm achieves good performances compared with the current state-of-the-art methods, reaching a competitive f-measure of 0.55% while the ESA-based approach surprisingly yielded reserved results.ConclusionsWe have proposed simple classification methods suitable to annotate textual documents using only partial information. They are therefore adequate for large multi-label classification and particularly in the biomedical domain. Thus, our work contributes to the extraction of relevant information from unstructured documents in order to facilitate their automated processing. Consequently, it could be used for various purposes, including document indexing, information retrieval, etc.
Tasks	Information Retrieval, Multi-Label Classification, Text Classification
Published	2016-06-09
URL	http://arxiv.org/abs/1606.02976v1
PDF	http://arxiv.org/pdf/1606.02976v1.pdf
PWC	https://paperswithcode.com/paper/large-scale-biomedical-texts-classification-a
Repo
Framework

Differentially Private Gaussian Processes


Title	Differentially Private Gaussian Processes
Authors	Michael Thomas Smith, Max Zwiessele, Neil D. Lawrence
Abstract	A major challenge for machine learning is increasing the availability of data while respecting the privacy of individuals. Here we combine the provable privacy guarantees of the differential privacy framework with the flexibility of Gaussian processes (GPs). We propose a method using GPs to provide differentially private (DP) regression. We then improve this method by crafting the DP noise covariance structure to efficiently protect the training data, while minimising the scale of the added noise. We find that this cloaking method achieves the greatest accuracy, while still providing privacy guarantees, and offers practical DP for regression over multi-dimensional inputs. Together these methods provide a starter toolkit for combining differential privacy and GPs.
Tasks	Gaussian Processes
Published	2016-06-02
URL	http://arxiv.org/abs/1606.00720v3
PDF	http://arxiv.org/pdf/1606.00720v3.pdf
PWC	https://paperswithcode.com/paper/differentially-private-gaussian-processes
Repo
Framework