Paper Group ANR 136
Bounded Optimal Exploration in MDP. Improved Multi-Class Cost-Sensitive Boosting via Estimation of the Minimum-Risk Class. Improved Particle Filters for Vehicle Localisation. Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases. Loss Bounds and Time Complexity for Speed Priors. New Liftable C …
Bounded Optimal Exploration in MDP
| Title | Bounded Optimal Exploration in MDP |
| Authors | Kenji Kawaguchi |
| Abstract | Within the framework of probably approximately correct Markov decision processes (PAC-MDP), much theoretical work has focused on methods to attain near optimality after a relatively long period of learning and exploration. However, practical concerns require the attainment of satisfactory behavior within a short period of time. In this paper, we relax the PAC-MDP conditions to reconcile theoretically driven exploration methods and practical needs. We propose simple algorithms for discrete and continuous state spaces, and illustrate the benefits of our proposed relaxation via theoretical analyses and numerical examples. Our algorithms also maintain anytime error bounds and average loss bounds. Our approach accommodates both Bayesian and non-Bayesian methods. |
| Tasks | |
| Published | 2016-04-05 |
| URL | http://arxiv.org/abs/1604.01350v1 |
| http://arxiv.org/pdf/1604.01350v1.pdf | |
| PWC | https://paperswithcode.com/paper/bounded-optimal-exploration-in-mdp |
| Repo | |
| Framework | |
Improved Multi-Class Cost-Sensitive Boosting via Estimation of the Minimum-Risk Class
| Title | Improved Multi-Class Cost-Sensitive Boosting via Estimation of the Minimum-Risk Class |
| Authors | Ron Appel, Xavier Burgos-Artizzu, Pietro Perona |
| Abstract | We present a simple unified framework for multi-class cost-sensitive boosting. The minimum-risk class is estimated directly, rather than via an approximation of the posterior distribution. Our method jointly optimizes binary weak learners and their corresponding output vectors, requiring classes to share features at each iteration. By training in a cost-sensitive manner, weak learners are invested in separating classes whose discrimination is important, at the expense of less relevant classification boundaries. Additional contributions are a family of loss functions along with proof that our algorithm is Boostable in the theoretical sense, as well as an efficient procedure for growing decision trees for use as weak learners. We evaluate our method on a variety of datasets: a collection of synthetic planar data, common UCI datasets, MNIST digits, SUN scenes, and CUB-200 birds. Results show state-of-the-art performance across all datasets against several strong baselines, including non-boosting multi-class approaches. |
| Tasks | |
| Published | 2016-07-12 |
| URL | http://arxiv.org/abs/1607.03547v2 |
| http://arxiv.org/pdf/1607.03547v2.pdf | |
| PWC | https://paperswithcode.com/paper/improved-multi-class-cost-sensitive-boosting |
| Repo | |
| Framework | |
Improved Particle Filters for Vehicle Localisation
| Title | Improved Particle Filters for Vehicle Localisation |
| Authors | Kira Kempinska, John Shawe-Taylor |
| Abstract | The ability to track a moving vehicle is of crucial importance in numerous applications. The task has often been approached by the importance sampling technique of particle filters due to its ability to model non-linear and non-Gaussian dynamics, of which a vehicle travelling on a road network is a good example. Particle filters perform poorly when observations are highly informative. In this paper, we address this problem by proposing particle filters that sample around the most recent observation. The proposal leads to an order of magnitude improvement in accuracy and efficiency over conventional particle filters, especially when observations are infrequent but low-noise. |
| Tasks | |
| Published | 2016-11-15 |
| URL | http://arxiv.org/abs/1611.04790v1 |
| http://arxiv.org/pdf/1611.04790v1.pdf | |
| PWC | https://paperswithcode.com/paper/improved-particle-filters-for-vehicle |
| Repo | |
| Framework | |
Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases
| Title | Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases |
| Authors | Zongyan Huang, Matthew England, James H. Davenport, Lawrence C. Paulson |
| Abstract | Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. However, it can be expensive, with worst case complexity doubly exponential in the size of the input. Hence it is important to formulate the problem in the best manner for the CAD algorithm. One possibility is to precondition the input polynomials using Groebner Basis (GB) theory. Previous experiments have shown that while this can often be very beneficial to the CAD algorithm, for some problems it can significantly worsen the CAD performance. In the present paper we investigate whether machine learning, specifically a support vector machine (SVM), may be used to identify those CAD problems which benefit from GB preconditioning. We run experiments with over 1000 problems (many times larger than previous studies) and find that the machine learned choice does better than the human-made heuristic. |
| Tasks | |
| Published | 2016-08-15 |
| URL | http://arxiv.org/abs/1608.04219v1 |
| http://arxiv.org/pdf/1608.04219v1.pdf | |
| PWC | https://paperswithcode.com/paper/using-machine-learning-to-decide-when-to |
| Repo | |
| Framework | |
Loss Bounds and Time Complexity for Speed Priors
| Title | Loss Bounds and Time Complexity for Speed Priors |
| Authors | Daniel Filan, Marcus Hutter, Jan Leike |
| Abstract | This paper establishes for the first time the predictive performance of speed priors and their computational complexity. A speed prior is essentially a probability distribution that puts low probability on strings that are not efficiently computable. We propose a variant to the original speed prior (Schmidhuber, 2002), and show that our prior can predict sequences drawn from probability measures that are estimable in polynomial time. Our speed prior is computable in doubly-exponential time, but not in polynomial time. On a polynomial time computable sequence our speed prior is computable in exponential time. We show better upper complexity bounds for Schmidhuber’s speed prior under the same conditions, and that it predicts deterministic sequences that are computable in polynomial time; however, we also show that it is not computable in polynomial time, and the question of its predictive properties for stochastic sequences remains open. |
| Tasks | |
| Published | 2016-04-12 |
| URL | http://arxiv.org/abs/1604.03343v1 |
| http://arxiv.org/pdf/1604.03343v1.pdf | |
| PWC | https://paperswithcode.com/paper/loss-bounds-and-time-complexity-for-speed |
| Repo | |
| Framework | |
New Liftable Classes for First-Order Probabilistic Inference
| Title | New Liftable Classes for First-Order Probabilistic Inference |
| Authors | Seyed Mehran Kazemi, Angelika Kimmig, Guy Van den Broeck, David Poole |
| Abstract | Statistical relational models provide compact encodings of probabilistic dependencies in relational domains, but result in highly intractable graphical models. The goal of lifted inference is to carry out probabilistic inference without needing to reason about each individual separately, by instead treating exchangeable, undistinguished objects as a whole. In this paper, we study the domain recursion inference rule, which, despite its central role in early theoretical results on domain-lifted inference, has later been believed redundant. We show that this rule is more powerful than expected, and in fact significantly extends the range of models for which lifted inference runs in time polynomial in the number of individuals in the domain. This includes an open problem called S4, the symmetric transitivity model, and a first-order logic encoding of the birthday paradox. We further identify new classes S2FO2 and S2RU of domain-liftable theories, which respectively subsume FO2 and recursively unary theories, the largest classes of domain-liftable theories known so far, and show that using domain recursion can achieve exponential speedup even in theories that cannot fully be lifted with the existing set of inference rules. |
| Tasks | |
| Published | 2016-10-26 |
| URL | http://arxiv.org/abs/1610.08445v1 |
| http://arxiv.org/pdf/1610.08445v1.pdf | |
| PWC | https://paperswithcode.com/paper/new-liftable-classes-for-first-order |
| Repo | |
| Framework | |
3D Menagerie: Modeling the 3D shape and pose of animals
| Title | 3D Menagerie: Modeling the 3D shape and pose of animals |
| Authors | Silvia Zuffi, Angjoo Kanazawa, David Jacobs, Michael J. Black |
| Abstract | There has been significant work on learning realistic, articulated, 3D models of the human body. In contrast, there are few such models of animals, despite many applications. The main challenge is that animals are much less cooperative than humans. The best human body models are learned from thousands of 3D scans of people in specific poses, which is infeasible with live animals. Consequently, we learn our model from a small set of 3D scans of toy figurines in arbitrary poses. We employ a novel part-based shape model to compute an initial registration to the scans. We then normalize their pose, learn a statistical shape model, and refine the registrations and the model together. In this way, we accurately align animal scans from different quadruped families with very different shapes and poses. With the registration to a common template we learn a shape space representing animals including lions, cats, dogs, horses, cows and hippos. Animal shapes can be sampled from the model, posed, animated, and fit to data. We demonstrate generalization by fitting it to images of real animals including species not seen in training. |
| Tasks | |
| Published | 2016-11-23 |
| URL | http://arxiv.org/abs/1611.07700v2 |
| http://arxiv.org/pdf/1611.07700v2.pdf | |
| PWC | https://paperswithcode.com/paper/3d-menagerie-modeling-the-3d-shape-and-pose |
| Repo | |
| Framework | |
Optimal Encoding and Decoding for Point Process Observations: an Approximate Closed-Form Filter
| Title | Optimal Encoding and Decoding for Point Process Observations: an Approximate Closed-Form Filter |
| Authors | Yuval Harel, Ron Meir, Manfred Opper |
| Abstract | The process of dynamic state estimation (filtering) based on point process observations is in general intractable. Numerical sampling techniques are often practically useful, but lead to limited conceptual insight about optimal encoding/decoding strategies, which are of significant relevance to Computational Neuroscience. We develop an analytically tractable Bayesian approximation to optimal filtering based on point process observations, which allows us to introduce distributional assumptions about sensor properties, that greatly facilitate the analysis of optimal encoding in situations deviating from common assumptions of uniform coding. Numerical comparison with particle filtering demonstrate the quality of the approximation. The analytic framework leads to insights which are difficult to obtain from numerical algorithms, and is consistent with biological observations about the distribution of sensory cells’ tuning curve centers. |
| Tasks | |
| Published | 2016-09-12 |
| URL | http://arxiv.org/abs/1609.03519v1 |
| http://arxiv.org/pdf/1609.03519v1.pdf | |
| PWC | https://paperswithcode.com/paper/optimal-encoding-and-decoding-for-point |
| Repo | |
| Framework | |
A Large-Scale Multilingual Disambiguation of Glosses
| Title | A Large-Scale Multilingual Disambiguation of Glosses |
| Authors | José Camacho Collados, Claudio Delli Bovi, Alessandro Raganato, Roberto Navigli |
| Abstract | Linking concepts and named entities to knowledge bases has become a crucial Natural Language Understanding task. In this respect, recent works have shown the key advantage of exploiting textual definitions in various Natural Language Processing applications. However, to date there are no reliable large-scale corpora of sense-annotated textual definitions available to the research community. In this paper we present a large-scale high-quality corpus of disambiguated glosses in multiple languages, comprising sense annotations of both concepts and named entities from a unified sense inventory. Our approach for the construction and disambiguation of the corpus builds upon the structure of a large multilingual semantic network and a state-of-the-art disambiguation system; first, we gather complementary information of equivalent definitions across different languages to provide context for disambiguation, and then we combine it with a semantic similarity-based refinement. As a result we obtain a multilingual corpus of textual definitions featuring over 38 million definitions in 263 languages, and we make it freely available at http://lcl.uniroma1.it/disambiguated-glosses. Experiments on Open Information Extraction and Sense Clustering show how two state-of-the-art approaches improve their performance by integrating our disambiguated corpus into their pipeline. |
| Tasks | Open Information Extraction, Semantic Similarity, Semantic Textual Similarity |
| Published | 2016-08-24 |
| URL | http://arxiv.org/abs/1608.06718v1 |
| http://arxiv.org/pdf/1608.06718v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-large-scale-multilingual-disambiguation-of |
| Repo | |
| Framework | |
Local Feature Detectors, Descriptors, and Image Representations: A Survey
| Title | Local Feature Detectors, Descriptors, and Image Representations: A Survey |
| Authors | Yusuke Uchida |
| Abstract | With the advances in both stable interest region detectors and robust and distinctive descriptors, local feature-based image or object retrieval has become a popular research topic. %All of the local feature-based image retrieval system involves two important processes: local feature extraction and image representation. The other key technology for image retrieval systems is image representation such as the bag-of-visual words (BoVW), Fisher vector, or Vector of Locally Aggregated Descriptors (VLAD) framework. In this paper, we review local features and image representations for image retrieval. Because many and many methods are proposed in this area, these methods are grouped into several classes and summarized. In addition, recent deep learning-based approaches for image retrieval are briefly reviewed. |
| Tasks | Image Retrieval |
| Published | 2016-07-28 |
| URL | http://arxiv.org/abs/1607.08368v1 |
| http://arxiv.org/pdf/1607.08368v1.pdf | |
| PWC | https://paperswithcode.com/paper/local-feature-detectors-descriptors-and-image |
| Repo | |
| Framework | |
Graph clustering, variational image segmentation methods and Hough transform scale detection for object measurement in images
| Title | Graph clustering, variational image segmentation methods and Hough transform scale detection for object measurement in images |
| Authors | Luca Calatroni, Yves van Gennip, Carola-Bibiane Schönlieb, Hannah Rowland, Arjuna Flenner |
| Abstract | We consider the problem of scale detection in images where a region of interest is present together with a measurement tool (e.g. a ruler). For the segmentation part, we focus on the graph based method by Flenner and Bertozzi which reinterprets classical continuous Ginzburg-Landau minimisation models in a totally discrete framework. To overcome the numerical difficulties due to the large size of the images considered we use matrix completion and splitting techniques. The scale on the measurement tool is detected via a Hough transform based algorithm. The method is then applied to some measurement tasks arising in real-world applications such as zoology, medicine and archaeology. |
| Tasks | Graph Clustering, Matrix Completion, Semantic Segmentation |
| Published | 2016-02-27 |
| URL | http://arxiv.org/abs/1602.08574v2 |
| http://arxiv.org/pdf/1602.08574v2.pdf | |
| PWC | https://paperswithcode.com/paper/graph-clustering-variational-image |
| Repo | |
| Framework | |
Weakly Supervised Scalable Audio Content Analysis
| Title | Weakly Supervised Scalable Audio Content Analysis |
| Authors | Anurag Kumar, Bhiksha Raj |
| Abstract | Audio Event Detection is an important task for content analysis of multimedia data. Most of the current works on detection of audio events is driven through supervised learning approaches. We propose a weakly supervised learning framework which can make use of the tremendous amount of web multimedia data with significantly reduced annotation effort and expense. Specifically, we use several multiple instance learning algorithms to show that audio event detection through weak labels is feasible. We also propose a novel scalable multiple instance learning algorithm and show that its competitive with other multiple instance learning algorithms for audio event detection tasks. |
| Tasks | Multiple Instance Learning |
| Published | 2016-06-12 |
| URL | http://arxiv.org/abs/1606.03664v1 |
| http://arxiv.org/pdf/1606.03664v1.pdf | |
| PWC | https://paperswithcode.com/paper/weakly-supervised-scalable-audio-content |
| Repo | |
| Framework | |
Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture
| Title | Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture |
| Authors | Lijie Chen, Jian Li |
| Abstract | The best arm identification problem (BEST-1-ARM) is the most basic pure exploration problem in stochastic multi-armed bandits. The problem has a long history and attracted significant attention for the last decade. However, we do not yet have a complete understanding of the optimal sample complexity of the problem: The state-of-the-art algorithms achieve a sample complexity of $O(\sum_{i=2}^{n} \Delta_{i}^{-2}(\ln\delta^{-1} + \ln\ln\Delta_i^{-1}))$ ($\Delta_{i}$ is the difference between the largest mean and the $i^{th}$ mean), while the best known lower bound is $\Omega(\sum_{i=2}^{n} \Delta_{i}^{-2}\ln\delta^{-1})$ for general instances and $\Omega(\Delta^{-2} \ln\ln \Delta^{-1})$ for the two-arm instances. We propose to study the instance-wise optimality for the BEST-1-ARM problem. Previous work has proved that it is impossible to have an instance optimal algorithm for the 2-arm problem. However, we conjecture that modulo the additive term $\Omega(\Delta_2^{-2} \ln\ln \Delta_2^{-1})$ (which is an upper bound and worst case lower bound for the 2-arm problem), there is an instance optimal algorithm for BEST-1-ARM. Moreover, we introduce a new quantity, called the gap entropy for a best-arm problem instance, and conjecture that it is the instance-wise lower bound. Hence, resolving this conjecture would provide a final answer to the old and basic problem. |
| Tasks | Multi-Armed Bandits |
| Published | 2016-05-27 |
| URL | http://arxiv.org/abs/1605.08481v1 |
| http://arxiv.org/pdf/1605.08481v1.pdf | |
| PWC | https://paperswithcode.com/paper/open-problem-best-arm-identification-almost |
| Repo | |
| Framework | |
Enabling My Robot To Play Pictionary : Recurrent Neural Networks For Sketch Recognition
| Title | Enabling My Robot To Play Pictionary : Recurrent Neural Networks For Sketch Recognition |
| Authors | Ravi Kiran Sarvadevabhatla, Jogendra Kundu, Babu R. Venkatesh |
| Abstract | Freehand sketching is an inherently sequential process. Yet, most approaches for hand-drawn sketch recognition either ignore this sequential aspect or exploit it in an ad-hoc manner. In our work, we propose a recurrent neural network architecture for sketch object recognition which exploits the long-term sequential and structural regularities in stroke data in a scalable manner. Specifically, we introduce a Gated Recurrent Unit based framework which leverages deep sketch features and weighted per-timestep loss to achieve state-of-the-art results on a large database of freehand object sketches across a large number of object categories. The inherently online nature of our framework is especially suited for on-the-fly recognition of objects as they are being drawn. Thus, our framework can enable interesting applications such as camera-equipped robots playing the popular party game Pictionary with human players and generating sparsified yet recognizable sketches of objects. |
| Tasks | Object Recognition, Sketch Recognition |
| Published | 2016-08-11 |
| URL | http://arxiv.org/abs/1608.03369v1 |
| http://arxiv.org/pdf/1608.03369v1.pdf | |
| PWC | https://paperswithcode.com/paper/enabling-my-robot-to-play-pictionary |
| Repo | |
| Framework | |
Exploring Differences in Interpretation of Words Essential in Medical Expert-Patient Communication
| Title | Exploring Differences in Interpretation of Words Essential in Medical Expert-Patient Communication |
| Authors | Javier Navarro, Christian Wagner, Uwe Aickelin, Lynsey Green, Robert Ashford |
| Abstract | In the context of cancer treatment and surgery, quality of life assessment is a crucial part of determining treatment success and viability. In order to assess it, patients completed questionnaires which employ words to capture aspects of patients well-being are the norm. As the results of these questionnaires are often used to assess patient progress and to determine future treatment options, it is important to establish that the words used are interpreted in the same way by both patients and medical professionals. In this paper, we capture and model patients perceptions and associated uncertainty about the words used to describe the level of their physical function used in the highly common (in Sarcoma Services) Toronto Extremity Salvage Score (TESS) questionnaire. The paper provides detail about the interval-valued data capture as well as the subsequent modelling of the data using fuzzy sets. Based on an initial sample of participants, we use Jaccard similarity on the resulting words models to show that there may be considerable differences in the interpretation of commonly used questionnaire terms, thus presenting a very real risk of miscommunication between patients and medical professionals as well as within the group of medical professionals. |
| Tasks | |
| Published | 2016-07-21 |
| URL | http://arxiv.org/abs/1607.06187v1 |
| http://arxiv.org/pdf/1607.06187v1.pdf | |
| PWC | https://paperswithcode.com/paper/exploring-differences-in-interpretation-of |
| Repo | |
| Framework | |
