July 27, 2019

2776 words 14 mins read

Paper Group ANR 584

Hamiltonian Maker-Breaker games on small graphs. Local Radon Descriptors for Image Search. Predicting Floor-Level for 911 Calls with Neural Networks and Smartphone Sensor Data. A Framework for Easing the Development of Applications Embedding Answer Set Programming. A New Method for Removing the Moire’ Pattern from Images. Automatic Localization of …

Hamiltonian Maker-Breaker games on small graphs


Title	Hamiltonian Maker-Breaker games on small graphs
Authors	Miloš Stojaković, Nikola Trkulja
Abstract	We look at the unbiased Maker-Breaker Hamiltonicity game played on the edge set of a complete graph $K_n$, where Maker’s goal is to claim a Hamiltonian cycle. First, we prove that, independent of who starts, Maker can win the game for $n = 8$ and $n = 9$. Then we use an inductive argument to show that, independent of who starts, Maker can win the game if and only if $n \geq 8$. This, in particular, resolves in the affirmative the long-standing conjecture of Papaioannou. We also study two standard positional games related to Hamiltonicity game. For Hamiltonian Path game, we show that Maker can claim a Hamiltonian path if and only if $n \geq 5$, independent of who starts. Next, we look at Fixed Hamiltonian Path game, where the goal of Maker is to claim a Hamiltonian path between two predetermined vertices. We prove that if Maker starts the game, he wins if and only if $n \geq 7$, and if Breaker starts, Maker wins if and only if $n \geq 8$. Using this result, we are able to improve the previously best upper bound on the smallest number of edges a graph on $n$ vertices can have, knowing that Maker can win the Maker-Breaker Hamiltonicity game played on its edges. To resolve the outcomes of the mentioned games on small (finite) boards, we devise algorithms for efficiently searching game trees and then obtain our results with the help of a computer.
Tasks
Published	2017-08-25
URL	http://arxiv.org/abs/1708.07579v3
PDF	http://arxiv.org/pdf/1708.07579v3.pdf
PWC	https://paperswithcode.com/paper/hamiltonian-maker-breaker-games-on-small
Repo
Framework

Local Radon Descriptors for Image Search


Title	Local Radon Descriptors for Image Search
Authors	Morteza Babaie, H. R. Tizhoosh, Amin Khatami, M. E. Shiri
Abstract	Radon transform and its inverse operation are important techniques in medical imaging tasks. Recently, there has been renewed interest in Radon transform for applications such as content-based medical image retrieval. However, all studies so far have used Radon transform as a global or quasi-global image descriptor by extracting projections of the whole image or large sub-images. This paper attempts to show that the dense sampling to generate the histogram of local Radon projections has a much higher discrimination capability than the global one. In this paper, we introduce Local Radon Descriptor (LRD) and apply it to the IRMA dataset, which contains 14,410 x-ray images as well as to the INRIA Holidays dataset with 1,990 images. Our results show significant improvement in retrieval performance by using LRD versus its global version. We also demonstrate that LRD can deliver results comparable to well-established descriptors like LBP and HOG.
Tasks	Image Retrieval, Medical Image Retrieval
Published	2017-10-11
URL	http://arxiv.org/abs/1710.04097v1
PDF	http://arxiv.org/pdf/1710.04097v1.pdf
PWC	https://paperswithcode.com/paper/local-radon-descriptors-for-image-search
Repo
Framework

Predicting Floor-Level for 911 Calls with Neural Networks and Smartphone Sensor Data


Title	Predicting Floor-Level for 911 Calls with Neural Networks and Smartphone Sensor Data
Authors	William Falcon, Henning Schulzrinne
Abstract	In cities with tall buildings, emergency responders need an accurate floor level location to find 911 callers quickly. We introduce a system to estimate a victim’s floor level via their mobile device’s sensor data in a two-step process. First, we train a neural network to determine when a smartphone enters or exits a building via GPS signal changes. Second, we use a barometer equipped smartphone to measure the change in barometric pressure from the entrance of the building to the victim’s indoor location. Unlike impractical previous approaches, our system is the first that does not require the use of beacons, prior knowledge of the building infrastructure, or knowledge of user behavior. We demonstrate real-world feasibility through 63 experiments across five different tall buildings throughout New York City where our system predicted the correct floor level with 100% accuracy.
Tasks
Published	2017-10-29
URL	http://arxiv.org/abs/1710.11122v4
PDF	http://arxiv.org/pdf/1710.11122v4.pdf
PWC	https://paperswithcode.com/paper/predicting-floor-level-for-911-calls-with
Repo
Framework

A Framework for Easing the Development of Applications Embedding Answer Set Programming


Title	A Framework for Easing the Development of Applications Embedding Answer Set Programming
Authors	Francesco Calimeri, Davide Fuscà, Stefano Germano, Simona Perri, Jessica Zangari
Abstract	Answer Set Programming (ASP) is a well-established declarative problem solving paradigm which became widely used in AI and recognized as a powerful tool for knowledge representation and reasoning (KRR), especially for its high expressiveness and the ability to deal also with incomplete knowledge. Recently, thanks to the availability of a number of robust and efficient implementations, ASP has been increasingly employed in a number of different domains, and used for the development of industrial-level and enterprise applications. This made clear the need for proper development tools and interoperability mechanisms for easing interaction and integration with external systems in the widest range of real-world scenarios, including mobile applications and educational contexts. In this work we present a framework for integrating the KRR capabilities of ASP into generic applications. We show the use of the framework by illustrating proper specializations for some relevant ASP systems over different platforms, including the mobile setting; furthermore, the potential of the framework for educational purposes is illustrated by means of the development of several ASP-based applications.
Tasks
Published	2017-07-21
URL	http://arxiv.org/abs/1707.06959v1
PDF	http://arxiv.org/pdf/1707.06959v1.pdf
PWC	https://paperswithcode.com/paper/a-framework-for-easing-the-development-of
Repo
Framework

A New Method for Removing the Moire’ Pattern from Images


Title	A New Method for Removing the Moire’ Pattern from Images
Authors	Seyede Mahya Hazavei, Hamid Reza Shahdoosti
Abstract	During the last decades, denoising methods have attracted much attention of researchers. The conventional method for removing the Moire’ pattern from images is using notch filters in the Frequency-domain. In this paper a new method is proposed that can achieve a better performance in comparison with the traditional method. Median filter is used in some part of spectrum of noisy images to reduce the noise. At the second part of this paper, to demonstrate the robustness of the proposed method, it is implemented for some noisy images that have moire’ pattern. Experiments on noisy images with different characteristics show that the proposed method increases the PSNR values compared with previous methods.
Tasks	Denoising
Published	2017-01-31
URL	http://arxiv.org/abs/1701.09037v1
PDF	http://arxiv.org/pdf/1701.09037v1.pdf
PWC	https://paperswithcode.com/paper/a-new-method-for-removing-the-moire-pattern
Repo
Framework

Automatic Localization of Deep Stimulation Electrodes Using Trajectory-based Segmentation Approach


Title	Automatic Localization of Deep Stimulation Electrodes Using Trajectory-based Segmentation Approach
Authors	Roger Gomez Nieto, Andres Marino Alvarez Meza, Julian David Echeverry Correa, Alvaro Angel Orozco Gutierrez
Abstract	Parkinson’s disease (PD) is a degenerative condition of the nervous system, which manifests itself primarily as muscle stiffness, hypokinesia, bradykinesia, and tremor. In patients suffering from advanced stages of PD, Deep Brain Stimulation neurosurgery (DBS) is the best alternative to medical treatment, especially when they become tolerant to the drugs. This surgery produces a neuronal activity, a result from electrical stimulation, whose quantification is known as Volume of Tissue Activated (VTA). To locate correctly the VTA in the cerebral volume space, one should be aware exactly the location of the tip of the DBS electrodes, as well as their spatial projection. In this paper, we automatically locate DBS electrodes using a threshold-based medical imaging segmentation methodology, determining the optimal value of this threshold adaptively. The proposed methodology allows the localization of DBS electrodes in Computed Tomography (CT) images, with high noise tolerance, using automatic threshold detection methods.
Tasks	Computed Tomography (CT), Medical Image Segmentation
Published	2017-06-13
URL	http://arxiv.org/abs/1706.04254v1
PDF	http://arxiv.org/pdf/1706.04254v1.pdf
PWC	https://paperswithcode.com/paper/automatic-localization-of-deep-stimulation
Repo
Framework

Fairness in Criminal Justice Risk Assessments: The State of the Art


Title	Fairness in Criminal Justice Risk Assessments: The State of the Art
Authors	Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, Aaron Roth
Abstract	Objectives: Discussions of fairness in criminal justice risk assessments typically lack conceptual precision. Rhetoric too often substitutes for careful analysis. In this paper, we seek to clarify the tradeoffs between different kinds of fairness and between fairness and accuracy. Methods: We draw on the existing literatures in criminology, computer science and statistics to provide an integrated examination of fairness and accuracy in criminal justice risk assessments. We also provide an empirical illustration using data from arraignments. Results: We show that there are at least six kinds of fairness, some of which are incompatible with one another and with accuracy. Conclusions: Except in trivial cases, it is impossible to maximize accuracy and fairness at the same time, and impossible simultaneously to satisfy all kinds of fairness. In practice, a major complication is different base rates across different legally protected groups. There is a need to consider challenging tradeoffs.
Tasks
Published	2017-03-27
URL	http://arxiv.org/abs/1703.09207v2
PDF	http://arxiv.org/pdf/1703.09207v2.pdf
PWC	https://paperswithcode.com/paper/fairness-in-criminal-justice-risk-assessments
Repo
Framework

Semantic Sentiment Analysis of Twitter Data


Title	Semantic Sentiment Analysis of Twitter Data
Authors	Preslav Nakov
Abstract	Internet and the proliferation of smart mobile devices have changed the way information is created, shared, and spreads, e.g., microblogs such as Twitter, weblogs such as LiveJournal, social networks such as Facebook, and instant messengers such as Skype and WhatsApp are now commonly used to share thoughts and opinions about anything in the surrounding world. This has resulted in the proliferation of social media content, thus creating new opportunities to study public opinion at a scale that was never possible before. Naturally, this abundance of data has quickly attracted business and research interest from various fields including marketing, political science, and social studies, among many others, which are interested in questions like these: Do people like the new Apple Watch? Do Americans support ObamaCare? How do Scottish feel about the Brexit? Answering these questions requires studying the sentiment of opinions people express in social media, which has given rise to the fast growth of the field of sentiment analysis in social media, with Twitter being especially popular for research due to its scale, representativeness, variety of topics discussed, as well as ease of public access to its messages. Here we present an overview of work on sentiment analysis on Twitter.
Tasks	Sentiment Analysis
Published	2017-10-04
URL	http://arxiv.org/abs/1710.01492v1
PDF	http://arxiv.org/pdf/1710.01492v1.pdf
PWC	https://paperswithcode.com/paper/semantic-sentiment-analysis-of-twitter-data
Repo
Framework

A Neural Attention Model for Categorizing Patient Safety Events


Title	A Neural Attention Model for Categorizing Patient Safety Events
Authors	Arman Cohan, Allan Fong, Nazli Goharian, Raj Ratwani
Abstract	Medical errors are leading causes of death in the US and as such, prevention of these errors is paramount to promoting health care. Patient Safety Event reports are narratives describing potential adverse events to the patients and are important in identifying and preventing medical errors. We present a neural network architecture for identifying the type of safety events which is the first step in understanding these narratives. Our proposed model is based on a soft neural attention model to improve the effectiveness of encoding long sequences. Empirical results on two large-scale real-world datasets of patient safety reports demonstrate the effectiveness of our method with significant improvements over existing methods.
Tasks
Published	2017-02-23
URL	http://arxiv.org/abs/1702.07092v1
PDF	http://arxiv.org/pdf/1702.07092v1.pdf
PWC	https://paperswithcode.com/paper/a-neural-attention-model-for-categorizing
Repo
Framework

Virtual vs. Real: Trading Off Simulations and Physical Experiments in Reinforcement Learning with Bayesian Optimization


Title	Virtual vs. Real: Trading Off Simulations and Physical Experiments in Reinforcement Learning with Bayesian Optimization
Authors	Alonso Marco, Felix Berkenkamp, Philipp Hennig, Angela P. Schoellig, Andreas Krause, Stefan Schaal, Sebastian Trimpe
Abstract	In practice, the parameters of control policies are often tuned manually. This is time-consuming and frustrating. Reinforcement learning is a promising alternative that aims to automate this process, yet often requires too many experiments to be practical. In this paper, we propose a solution to this problem by exploiting prior knowledge from simulations, which are readily available for most robotic platforms. Specifically, we extend Entropy Search, a Bayesian optimization algorithm that maximizes information gain from each experiment, to the case of multiple information sources. The result is a principled way to automatically combine cheap, but inaccurate information from simulations with expensive and accurate physical experiments in a cost-effective manner. We apply the resulting method to a cart-pole system, which confirms that the algorithm can find good control policies with fewer experiments than standard Bayesian optimization on the physical system only.
Tasks
Published	2017-03-03
URL	http://arxiv.org/abs/1703.01250v1
PDF	http://arxiv.org/pdf/1703.01250v1.pdf
PWC	https://paperswithcode.com/paper/virtual-vs-real-trading-off-simulations-and
Repo
Framework

Potential-Function Proofs for First-Order Methods


Title	Potential-Function Proofs for First-Order Methods
Authors	Nikhil Bansal, Anupam Gupta
Abstract	This note discusses proofs for convergence of first-order methods based on simple potential-function arguments. We cover methods like gradient descent (for both smooth and non-smooth settings), mirror descent, and some accelerated variants.
Tasks
Published	2017-12-13
URL	https://arxiv.org/abs/1712.04581v3
PDF	https://arxiv.org/pdf/1712.04581v3.pdf
PWC	https://paperswithcode.com/paper/potential-function-proofs-for-first-order
Repo
Framework

Identifying On-time Reward Delivery Projects with Estimating Delivery Duration on Kickstarter


Title	Identifying On-time Reward Delivery Projects with Estimating Delivery Duration on Kickstarter
Authors	Thanh Tran, Kyumin Lee, Nguyen Vo, Hongkyu Choi
Abstract	In Crowdfunding platforms, people turn their prototype ideas into real products by raising money from the crowd, or invest in someone else’s projects. In reward-based crowdfunding platforms such as Kickstarter and Indiegogo, selecting accurate reward delivery duration becomes crucial for creators, backers, and platform providers to keep the trust between the creators and the backers, and the trust between the platform providers and users. According to Kickstarter, 35% backers did not receive rewards on time. Unfortunately, little is known about on-time and late reward delivery projects, and there is no prior work to estimate reward delivery duration. To fill the gap, in this paper, we (i) extract novel features that reveal latent difficulty levels of project rewards; (ii) build predictive models to identify whether a creator will deliver all rewards in a project on time or not; and (iii) build a regression model to estimate accurate reward delivery duration (i.e., how long it will take to produce and deliver all the rewards). Experimental results show that our models achieve good performance – 82.5% accuracy, 78.1 RMSE, and 0.108 NRMSE at the first 5% of the longest reward delivery duration.
Tasks
Published	2017-10-12
URL	http://arxiv.org/abs/1710.04743v1
PDF	http://arxiv.org/pdf/1710.04743v1.pdf
PWC	https://paperswithcode.com/paper/identifying-on-time-reward-delivery-projects
Repo
Framework

Sharp Convergence Rates for Forward Regression in High-Dimensional Sparse Linear Models


Title	Sharp Convergence Rates for Forward Regression in High-Dimensional Sparse Linear Models
Authors	Damian Kozbur
Abstract	Forward regression is a statistical model selection and estimation procedure which inductively selects covariates that add predictive power into a working statistical regression model. Once a model is selected, unknown regression parameters are estimated by least squares. This paper analyzes forward regression in high-dimensional sparse linear models. Probabilistic bounds for prediction error norm and number of selected covariates are proved. The analysis in this paper gives sharp rates and does not require beta-min or irrepresentability conditions.
Tasks	Model Selection
Published	2017-02-03
URL	http://arxiv.org/abs/1702.01000v3
PDF	http://arxiv.org/pdf/1702.01000v3.pdf
PWC	https://paperswithcode.com/paper/sharp-convergence-rates-for-forward
Repo
Framework

Generalized Probabilistic Bisection for Stochastic Root-Finding


Title	Generalized Probabilistic Bisection for Stochastic Root-Finding
Authors	Sergio Rodriguez, Michael Ludkovski
Abstract	We consider numerical schemes for root finding of noisy responses through generalizing the Probabilistic Bisection Algorithm (PBA) to the more practical context where the sampling distribution is unknown and location-dependent. As in standard PBA, we rely on a knowledge state for the approximate posterior of the root location. To implement the corresponding Bayesian updating, we also carry out inference of oracle accuracy, namely learning the probability of correct response. To this end we utilize batched querying in combination with a variety of frequentist and Bayesian estimators based on majority vote, as well as the underlying functional responses, if available. For guiding sampling selection we investigate both Information Directed sampling, as well as Quantile sampling. Our numerical experiments show that these strategies perform quite differently; in particular we demonstrate the efficiency of randomized quantile sampling which is reminiscent of Thompson sampling. Our work is motivated by the root-finding sub-routine in pricing of Bermudan financial derivatives, illustrated in the last section of the paper.
Tasks
Published	2017-11-02
URL	http://arxiv.org/abs/1711.00843v1
PDF	http://arxiv.org/pdf/1711.00843v1.pdf
PWC	https://paperswithcode.com/paper/generalized-probabilistic-bisection-for
Repo
Framework

Learning Word Embeddings for Hyponymy with Entailment-Based Distributional Semantics


Title	Learning Word Embeddings for Hyponymy with Entailment-Based Distributional Semantics
Authors	James Henderson
Abstract	Lexical entailment, such as hyponymy, is a fundamental issue in the semantics of natural language. This paper proposes distributional semantic models which efficiently learn word embeddings for entailment, using a recently-proposed framework for modelling entailment in a vector-space. These models postulate a latent vector for a pseudo-phrase containing two neighbouring word vectors. We investigate both modelling words as the evidence they contribute about this phrase vector, or as the posterior distribution of a one-word phrase vector, and find that the posterior vectors perform better. The resulting word embeddings outperform the best previous results on predicting hyponymy between words, in unsupervised and semi-supervised experiments.
Tasks	Learning Word Embeddings, Word Embeddings
Published	2017-10-06
URL	http://arxiv.org/abs/1710.02437v1
PDF	http://arxiv.org/pdf/1710.02437v1.pdf
PWC	https://paperswithcode.com/paper/learning-word-embeddings-for-hyponymy-with
Repo
Framework