Paper Group ANR 137
POMDP-lite for Robust Robot Planning under Uncertainty. Deepr: A Convolutional Net for Medical Records. Extending Weakly-Sticky Datalog+/-: Query-Answering Tractability and Optimizations. Exact Structure Learning of Bayesian Networks by Optimal Path Extension. Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach. …
POMDP-lite for Robust Robot Planning under Uncertainty
| Title | POMDP-lite for Robust Robot Planning under Uncertainty |
| Authors | Min Chen, Emilio Frazzoli, David Hsu, Wee Sun Lee |
| Abstract | The partially observable Markov decision process (POMDP) provides a principled general model for planning under uncertainty. However, solving a general POMDP is computationally intractable in the worst case. This paper introduces POMDP-lite, a subclass of POMDPs in which the hidden state variables are constant or only change deterministically. We show that a POMDP-lite is equivalent to a set of fully observable Markov decision processes indexed by a hidden parameter and is useful for modeling a variety of interesting robotic tasks. We develop a simple model-based Bayesian reinforcement learning algorithm to solve POMDP-lite models. The algorithm performs well on large-scale POMDP-lite models with up to $10^{20}$ states and outperforms the state-of-the-art general-purpose POMDP algorithms. We further show that the algorithm is near-Bayesian-optimal under suitable conditions. |
| Tasks | |
| Published | 2016-02-16 |
| URL | http://arxiv.org/abs/1602.04875v3 |
| http://arxiv.org/pdf/1602.04875v3.pdf | |
| PWC | https://paperswithcode.com/paper/pomdp-lite-for-robust-robot-planning-under |
| Repo | |
| Framework | |
Deepr: A Convolutional Net for Medical Records
| Title | Deepr: A Convolutional Net for Medical Records |
| Authors | Phuoc Nguyen, Truyen Tran, Nilmini Wickramasinghe, Svetha Venkatesh |
| Abstract | Feature engineering remains a major bottleneck when creating predictive systems from electronic medical records. At present, an important missing element is detecting predictive regular clinical motifs from irregular episodic records. We present Deepr (short for Deep record), a new end-to-end deep learning system that learns to extract features from medical records and predicts future risk automatically. Deepr transforms a record into a sequence of discrete elements separated by coded time gaps and hospital transfers. On top of the sequence is a convolutional neural net that detects and combines predictive local clinical motifs to stratify the risk. Deepr permits transparent inspection and visualization of its inner working. We validate Deepr on hospital data to predict unplanned readmission after discharge. Deepr achieves superior accuracy compared to traditional techniques, detects meaningful clinical motifs, and uncovers the underlying structure of the disease and intervention space. |
| Tasks | Feature Engineering |
| Published | 2016-07-26 |
| URL | http://arxiv.org/abs/1607.07519v1 |
| http://arxiv.org/pdf/1607.07519v1.pdf | |
| PWC | https://paperswithcode.com/paper/deepr-a-convolutional-net-for-medical-records |
| Repo | |
| Framework | |
Extending Weakly-Sticky Datalog+/-: Query-Answering Tractability and Optimizations
| Title | Extending Weakly-Sticky Datalog+/-: Query-Answering Tractability and Optimizations |
| Authors | Mostafa Milani, Leopoldo Bertossi |
| Abstract | Weakly-sticky (WS) Datalog+/- is an expressive member of the family of Datalog+/- programs that is based on the syntactic notions of stickiness and weak-acyclicity. Query answering over the WS programs has been investigated, but there is still much work to do on the design and implementation of practical query answering (QA) algorithms and their optimizations. Here, we study sticky and WS programs from the point of view of the behavior of the chase procedure, extending the stickiness property of the chase to that of generalized stickiness of the chase (gsch-property). With this property we specify the semantic class of GSCh programs, which includes sticky and WS programs, and other syntactic subclasses that we identify. In particular, we introduce joint-weakly-sticky (JWS) programs, that include WS programs. We also propose a bottom-up QA algorithm for a range of subclasses of GSCh. The algorithm runs in polynomial time (in data) for JWS programs. Unlike the WS class, JWS is closed under a general magic-sets rewriting procedure for the optimization of programs with existential rules. We apply the magic-sets rewriting in combination with the proposed QA algorithm for the optimization of QA over JWS programs. |
| Tasks | |
| Published | 2016-07-10 |
| URL | http://arxiv.org/abs/1607.02682v1 |
| http://arxiv.org/pdf/1607.02682v1.pdf | |
| PWC | https://paperswithcode.com/paper/extending-weakly-sticky-datalog-query |
| Repo | |
| Framework | |
Exact Structure Learning of Bayesian Networks by Optimal Path Extension
| Title | Exact Structure Learning of Bayesian Networks by Optimal Path Extension |
| Authors | Subhadeep Karan, Jaroslaw Zola |
| Abstract | Bayesian networks are probabilistic graphical models often used in big data analytics. The problem of exact structure learning is to find a network structure that is optimal under certain scoring criteria. The problem is known to be NP-hard and the existing methods are both computationally and memory intensive. In this paper, we introduce a new approach for exact structure learning. Our strategy is to leverage relationship between a partial network structure and the remaining variables to constraint the number of ways in which the partial network can be optimally extended. Via experimental results, we show that the method provides up to three times improvement in runtime, and orders of magnitude reduction in memory consumption over the current best algorithms. |
| Tasks | |
| Published | 2016-08-09 |
| URL | http://arxiv.org/abs/1608.02682v3 |
| http://arxiv.org/pdf/1608.02682v3.pdf | |
| PWC | https://paperswithcode.com/paper/exact-structure-learning-of-bayesian-networks |
| Repo | |
| Framework | |
Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach
| Title | Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach |
| Authors | Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, Sujay Sanghavi |
| Abstract | We consider the non-square matrix sensing problem, under restricted isometry property (RIP) assumptions. We focus on the non-convex formulation, where any rank-$r$ matrix $X \in \mathbb{R}^{m \times n}$ is represented as $UV^\top$, where $U \in \mathbb{R}^{m \times r}$ and $V \in \mathbb{R}^{n \times r}$. In this paper, we complement recent findings on the non-convex geometry of the analogous PSD setting [5], and show that matrix factorization does not introduce any spurious local minima, under RIP. |
| Tasks | |
| Published | 2016-09-12 |
| URL | http://arxiv.org/abs/1609.03240v2 |
| http://arxiv.org/pdf/1609.03240v2.pdf | |
| PWC | https://paperswithcode.com/paper/non-square-matrix-sensing-without-spurious |
| Repo | |
| Framework | |
Online Sparse Linear Regression
| Title | Online Sparse Linear Regression |
| Authors | Dean Foster, Satyen Kale, Howard Karloff |
| Abstract | We consider the online sparse linear regression problem, which is the problem of sequentially making predictions observing only a limited number of features in each round, to minimize regret with respect to the best sparse linear regressor, where prediction accuracy is measured by square loss. We give an inefficient algorithm that obtains regret bounded by $\tilde{O}(\sqrt{T})$ after $T$ prediction rounds. We complement this result by showing that no algorithm running in polynomial time per iteration can achieve regret bounded by $O(T^{1-\delta})$ for any constant $\delta > 0$ unless $\text{NP} \subseteq \text{BPP}$. This computational hardness result resolves an open problem presented in COLT 2014 (Kale, 2014) and also posed by Zolghadr et al. (2013). This hardness result holds even if the algorithm is allowed to access more features than the best sparse linear regressor up to a logarithmic factor in the dimension. |
| Tasks | |
| Published | 2016-03-07 |
| URL | http://arxiv.org/abs/1603.02250v1 |
| http://arxiv.org/pdf/1603.02250v1.pdf | |
| PWC | https://paperswithcode.com/paper/online-sparse-linear-regression |
| Repo | |
| Framework | |
Semantic Noise Modeling for Better Representation Learning
| Title | Semantic Noise Modeling for Better Representation Learning |
| Authors | Hyo-Eun Kim, Sangheum Hwang, Kyunghyun Cho |
| Abstract | Latent representation learned from multi-layered neural networks via hierarchical feature abstraction enables recent success of deep learning. Under the deep learning framework, generalization performance highly depends on the learned latent representation which is obtained from an appropriate training scenario with a task-specific objective on a designed network model. In this work, we propose a novel latent space modeling method to learn better latent representation. We designed a neural network model based on the assumption that good base representation can be attained by maximizing the total correlation between the input, latent, and output variables. From the base model, we introduce a semantic noise modeling method which enables class-conditional perturbation on latent space to enhance the representational power of learned latent feature. During training, latent vector representation can be stochastically perturbed by a modeled class-conditional additive noise while maintaining its original semantic feature. It implicitly brings the effect of semantic augmentation on the latent space. The proposed model can be easily learned by back-propagation with common gradient-based optimization algorithms. Experimental results show that the proposed method helps to achieve performance benefits against various previous approaches. We also provide the empirical analyses for the proposed class-conditional perturbation process including t-SNE visualization. |
| Tasks | Representation Learning |
| Published | 2016-11-04 |
| URL | http://arxiv.org/abs/1611.01268v1 |
| http://arxiv.org/pdf/1611.01268v1.pdf | |
| PWC | https://paperswithcode.com/paper/semantic-noise-modeling-for-better |
| Repo | |
| Framework | |
OCR of historical printings with an application to building diachronic corpora: A case study using the RIDGES herbal corpus
| Title | OCR of historical printings with an application to building diachronic corpora: A case study using the RIDGES herbal corpus |
| Authors | U. Springmann, A. Lüdeling |
| Abstract | This article describes the results of a case study that applies Neural Network-based Optical Character Recognition (OCR) to scanned images of books printed between 1487 and 1870 by training the OCR engine OCRopus [@breuel2013high] on the RIDGES herbal text corpus [@OdebrechtEtAlSubmitted]. Training specific OCR models was possible because the necessary ground truth is available as error-corrected diplomatic transcriptions. The OCR results have been evaluated for accuracy against the ground truth of unseen test sets. Character and word accuracies (percentage of correctly recognized items) for the resulting machine-readable texts of individual documents range from 94% to more than 99% (character level) and from 76% to 97% (word level). This includes the earliest printed books, which were thought to be inaccessible by OCR methods until recently. Furthermore, OCR models trained on one part of the corpus consisting of books with different printing dates and different typesets (mixed models) have been tested for their predictive power on the books from the other part containing yet other fonts, mostly yielding character accuracies well above 90%. It therefore seems possible to construct generalized models trained on a range of fonts that can be applied to a wide variety of historical printings still giving good results. A moderate postcorrection effort of some pages will then enable the training of individual models with even better accuracies. Using this method, diachronic corpora including early printings can be constructed much faster and cheaper than by manual transcription. The OCR methods reported here open up the possibility of transforming our printed textual cultural heritage into electronic text by largely automatic means, which is a prerequisite for the mass conversion of scanned books. |
| Tasks | Optical Character Recognition |
| Published | 2016-08-06 |
| URL | http://arxiv.org/abs/1608.02153v2 |
| http://arxiv.org/pdf/1608.02153v2.pdf | |
| PWC | https://paperswithcode.com/paper/ocr-of-historical-printings-with-an |
| Repo | |
| Framework | |
Adaptive coherence estimator (ACE) for explosive hazard detection using wideband electromagnetic induction (WEMI)
| Title | Adaptive coherence estimator (ACE) for explosive hazard detection using wideband electromagnetic induction (WEMI) |
| Authors | Brendan Alvey, Alina Zare, Matthew Cook, Dominic K. Ho |
| Abstract | The adaptive coherence estimator (ACE) estimates the squared cosine of the angle between a known target vector and a sample vector in a whitened coordinate space. The space is whitened according to an estimation of the background statistics, which directly effects the performance of the statistic as a target detector. In this paper, the ACE detection statistic is used to detect buried explosive hazards with data from a Wideband Electromagnetic Induction (WEMI) sensor. Target signatures are based on a dictionary defined using a Discrete Spectrum of Relaxation Frequencies (DSRF) model. Results are summarized as a receiver operator curve (ROC) and compared to other leading methods. |
| Tasks | |
| Published | 2016-03-19 |
| URL | http://arxiv.org/abs/1603.06140v3 |
| http://arxiv.org/pdf/1603.06140v3.pdf | |
| PWC | https://paperswithcode.com/paper/adaptive-coherence-estimator-ace-for |
| Repo | |
| Framework | |
A Category Space Approach to Supervised Dimensionality Reduction
| Title | A Category Space Approach to Supervised Dimensionality Reduction |
| Authors | Anthony O. Smith, Anand Rangarajan |
| Abstract | Supervised dimensionality reduction has emerged as an important theme in the last decade. Despite the plethora of models and formulations, there is a lack of a simple model which aims to project the set of patterns into a space defined by the classes (or categories). To this end, we set up a model in which each class is represented as a 1D subspace of the vector space formed by the features. Assuming the set of classes does not exceed the cardinality of the features, the model results in multi-class supervised learning in which the features of each class are projected into the class subspace. Class discrimination is automatically guaranteed via the imposition of orthogonality of the 1D class sub-spaces. The resulting optimization problem - formulated as the minimization of a sum of quadratic functions on a Stiefel manifold - while being non-convex (due to the constraints), nevertheless has a structure for which we can identify when we have reached a global minimum. After formulating a version with standard inner products, we extend the formulation to reproducing kernel Hilbert spaces in a straightforward manner. The optimization approach also extends in a similar fashion to the kernel version. Results and comparisons with the multi-class Fisher linear (and kernel) discriminants and principal component analysis (linear and kernel) showcase the relative merits of this approach to dimensionality reduction. |
| Tasks | Dimensionality Reduction |
| Published | 2016-10-27 |
| URL | http://arxiv.org/abs/1610.08838v1 |
| http://arxiv.org/pdf/1610.08838v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-category-space-approach-to-supervised |
| Repo | |
| Framework | |
Internet of Things Applications: Animal Monitoring with Unmanned Aerial Vehicle
| Title | Internet of Things Applications: Animal Monitoring with Unmanned Aerial Vehicle |
| Authors | Jun Xu, Gurkan Solmaz, Rouhollah Rahmatizadeh, Damla Turgut, Ladislau Boloni |
| Abstract | In animal monitoring applications, both animal detection and their movement prediction are major tasks. While a variety of animal monitoring strategies exist, most of them rely on mounting devices. However, in real world, it is difficult to find these animals and install mounting devices. In this paper, we propose an animal monitoring application by utilizing wireless sensor networks (WSNs) and unmanned aerial vehicle (UAV). The objective of the application is to detect locations of endangered species in large-scale wildlife areas and monitor movement of animals without any attached devices. In this application, sensors deployed throughout the observation area are responsible for gathering animal information. The UAV flies above the observation area and collects the information from sensors. To achieve the information efficiently, we propose a path planning approach for the UAV based on a Markov decision process (MDP) model. The UAV receives a certain amount of reward from an area if some animals are detected at that location. We solve the MDP using Q-learning such that the UAV prefers going to those areas that animals are detected before. Meanwhile, the UAV explores other areas as well to cover the entire network and detects changes in the animal positions. We first define the mathematical model underlying the animal monitoring problem in terms of the value of information (VoI) and rewards. We propose a network model including clusters of sensor nodes and a single UAV that acts as a mobile sink and visits the clusters. Then, one MDP-based path planning approach is designed to maximize the VoI while reducing message delays. The effectiveness of the proposed approach is evaluated using two real-world movement datasets of zebras and leopard. Simulation results show that our approach outperforms greedy, random heuristics and the path planning based on the traveling salesman problem. |
| Tasks | Q-Learning |
| Published | 2016-10-17 |
| URL | http://arxiv.org/abs/1610.05287v2 |
| http://arxiv.org/pdf/1610.05287v2.pdf | |
| PWC | https://paperswithcode.com/paper/internet-of-things-applications-animal |
| Repo | |
| Framework | |
Digital Image Forensics vs. Image Composition: An Indirect Arms Race
| Title | Digital Image Forensics vs. Image Composition: An Indirect Arms Race |
| Authors | Victor Schetinger, Massimo Iuliani, Alessandro Piva, Manuel M. Oliveira |
| Abstract | The field of image composition is constantly trying to improve the ways in which an image can be altered and enhanced. While this is usually done in the name of aesthetics and practicality, it also provides tools that can be used to maliciously alter images. In this sense, the field of digital image forensics has to be prepared to deal with the influx of new technology, in a constant arms-race. In this paper, the current state of this arms-race is analyzed, surveying the state-of-the-art and providing means to compare both sides. A novel scale to classify image forensics assessments is proposed, and experiments are performed to test composition techniques in regards to different forensics traces. We show that even though research in forensics seems unaware of the advanced forms of image composition, it possesses the basic tools to detect it. |
| Tasks | |
| Published | 2016-01-13 |
| URL | http://arxiv.org/abs/1601.03239v1 |
| http://arxiv.org/pdf/1601.03239v1.pdf | |
| PWC | https://paperswithcode.com/paper/digital-image-forensics-vs-image-composition |
| Repo | |
| Framework | |
Internal Guidance for Satallax
| Title | Internal Guidance for Satallax |
| Authors | Michael Färber, Chad Brown |
| Abstract | We propose a new internal guidance method for automated theorem provers based on the given-clause algorithm. Our method influences the choice of unprocessed clauses using positive and negative examples from previous proofs. To this end, we present an efficient scheme for Naive Bayesian classification by generalising label occurrences to types with monoid structure. This makes it possible to extend existing fast classifiers, which consider only positive examples, with negative ones. We implement the method in the higher-order logic prover Satallax, where we modify the delay with which propositions are processed. We evaluated our method on a simply-typed higher-order logic version of the Flyspeck project, where it solves 26% more problems than Satallax without internal guidance. |
| Tasks | |
| Published | 2016-05-30 |
| URL | http://arxiv.org/abs/1605.09293v1 |
| http://arxiv.org/pdf/1605.09293v1.pdf | |
| PWC | https://paperswithcode.com/paper/internal-guidance-for-satallax |
| Repo | |
| Framework | |
The embedding dimension of Laplacian eigenfunction maps
| Title | The embedding dimension of Laplacian eigenfunction maps |
| Authors | Jonathan Bates |
| Abstract | Any closed, connected Riemannian manifold $M$ can be smoothly embedded by its Laplacian eigenfunction maps into $\mathbb{R}^m$ for some $m$. We call the smallest such $m$ the maximal embedding dimension of $M$. We show that the maximal embedding dimension of $M$ is bounded from above by a constant depending only on the dimension of $M$, a lower bound for injectivity radius, a lower bound for Ricci curvature, and a volume bound. We interpret this result for the case of surfaces isometrically immersed in $\mathbb{R}^3$, showing that the maximal embedding dimension only depends on bounds for the Gaussian curvature, mean curvature, and surface area. Furthermore, we consider the relevance of these results for shape registration. |
| Tasks | |
| Published | 2016-05-04 |
| URL | http://arxiv.org/abs/1605.01643v1 |
| http://arxiv.org/pdf/1605.01643v1.pdf | |
| PWC | https://paperswithcode.com/paper/the-embedding-dimension-of-laplacian |
| Repo | |
| Framework | |
A ranking approach to global optimization
| Title | A ranking approach to global optimization |
| Authors | Cédric Malherbe, Nicolas Vayatis |
| Abstract | We consider the problem of maximizing an unknown function over a compact and convex set using as few observations as possible. We observe that the optimization of the function essentially relies on learning the induced bipartite ranking rule of f. Based on this idea, we relate global optimization to bipartite ranking which allows to address problems with high dimensional input space, as well as cases of functions with weak regularity properties. The paper introduces novel meta-algorithms for global optimization which rely on the choice of any bipartite ranking method. Theoretical properties are provided as well as convergence guarantees and equivalences between various optimization methods are obtained as a by-product. Eventually, numerical evidence is given to show that the main algorithm of the paper which adapts empirically to the underlying ranking structure essentially outperforms existing state-of-the-art global optimization algorithms in typical benchmarks. |
| Tasks | |
| Published | 2016-03-14 |
| URL | http://arxiv.org/abs/1603.04381v2 |
| http://arxiv.org/pdf/1603.04381v2.pdf | |
| PWC | https://paperswithcode.com/paper/a-ranking-approach-to-global-optimization |
| Repo | |
| Framework | |
