May 5, 2019

3186 words 15 mins read

Paper Group ANR 506

Probably Approximately Correct Greedy Maximization. Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models. It’s about time: Online Macrotask Sequencing in Expert Crowdsourcing. Capturing divergence in dependency trees to improve syntactic projection. Gesture-based Bootstrapping for Egocentric Hand Segmentation. The Multi-fi …

Probably Approximately Correct Greedy Maximization


Title	Probably Approximately Correct Greedy Maximization
Authors	Yash Satsangi, Shimon Whiteson, Frans A. Oliehoek
Abstract	Submodular function maximization finds application in a variety of real-world decision-making problems. However, most existing methods, based on greedy maximization, assume it is computationally feasible to evaluate F, the function being maximized. Unfortunately, in many realistic settings F is too expensive to evaluate exactly even once. We present probably approximately correct greedy maximization, which requires access only to cheap anytime confidence bounds on F and uses them to prune elements. We show that, with high probability, our method returns an approximately optimal set. We propose novel, cheap confidence bounds for conditional entropy, which appears in many common choices of F and for which it is difficult to find unbiased or bounded estimates. Finally, results on a real-world dataset from a multi-camera tracking system in a shopping mall demonstrate that our approach performs comparably to existing methods, but at a fraction of the computational cost.
Tasks	Decision Making
Published	2016-02-25
URL	http://arxiv.org/abs/1602.07860v1
PDF	http://arxiv.org/pdf/1602.07860v1.pdf
PWC	https://paperswithcode.com/paper/probably-approximately-correct-greedy
Repo
Framework

Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models


Title	Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models
Authors	Ankur Moitra
Abstract	In this paper we introduce a new approach for approximately counting in bounded degree systems with higher-order constraints. Our main result is an algorithm to approximately count the number of solutions to a CNF formula $\Phi$ when the width is logarithmic in the maximum degree. This closes an exponential gap between the known upper and lower bounds. Moreover our algorithm extends straightforwardly to approximate sampling, which shows that under Lov'asz Local Lemma-like conditions it is not only possible to find a satisfying assignment, it is also possible to generate one approximately uniformly at random from the set of all satisfying assignments. Our approach is a significant departure from earlier techniques in approximate counting, and is based on a framework to bootstrap an oracle for computing marginal probabilities on individual variables. Finally, we give an application of our results to show that it is algorithmically possible to sample from the posterior distribution in an interesting class of graphical models.
Tasks
Published	2016-10-14
URL	http://arxiv.org/abs/1610.04317v2
PDF	http://arxiv.org/pdf/1610.04317v2.pdf
PWC	https://paperswithcode.com/paper/approximate-counting-the-lovasz-local-lemma
Repo
Framework

It’s about time: Online Macrotask Sequencing in Expert Crowdsourcing


Title	It’s about time: Online Macrotask Sequencing in Expert Crowdsourcing
Authors	Heinz Schmitz, Ioanna Lykourentzou
Abstract	We introduce the problem of Task Assignment and Sequencing (TAS), which adds the timeline perspective to expert crowdsourcing optimization. Expert crowdsourcing involves macrotasks, like document writing, product design, or web development, which take more time than typical binary microtasks, require expert skills, assume varying degrees of knowledge over a topic, and require crowd workers to build on each other’s contributions. Current works usually assume offline optimization models, which consider worker and task arrivals known and do not take into account the element of time. Realistically however, time is critical: tasks have deadlines, expert workers are available only at specific time slots, and worker/task arrivals are not known a-priori. Our work is the first to address the problem of optimal task sequencing for online, heterogeneous, time-constrained macrotasks. We propose tas-online, an online algorithm that aims to complete as many tasks as possible within budget, required quality and a given timeline, without future input information regarding job release dates or worker availabilities. Results, comparing tas-online to four typical benchmarks, show that it achieves more completed jobs, lower flow times and higher job quality. This work has practical implications for improving the Quality of Service of current crowdsourcing platforms, allowing them to offer cost, quality and time improvements for expert tasks.
Tasks
Published	2016-01-15
URL	http://arxiv.org/abs/1601.04038v1
PDF	http://arxiv.org/pdf/1601.04038v1.pdf
PWC	https://paperswithcode.com/paper/its-about-time-online-macrotask-sequencing-in
Repo
Framework

Capturing divergence in dependency trees to improve syntactic projection


Title	Capturing divergence in dependency trees to improve syntactic projection
Authors	Ryan Georgi, Fei Xia, William D. Lewis
Abstract	Obtaining syntactic parses is a crucial part of many NLP pipelines. However, most of the world’s languages do not have large amounts of syntactically annotated corpora available for building parsers. Syntactic projection techniques attempt to address this issue by using parallel corpora consisting of resource-poor and resource-rich language pairs, taking advantage of a parser for the resource-rich language and word alignment between the languages to project the parses onto the data for the resource-poor language. These projection methods can suffer, however, when the two languages are divergent. In this paper, we investigate the possibility of using small, parallel, annotated corpora to automatically detect divergent structural patterns between two languages. These patterns can then be used to improve structural projection algorithms, allowing for better performing NLP tools for resource-poor languages, in particular those that may not have large amounts of annotated data necessary for traditional, fully-supervised methods. While this detection process is not exhaustive, we demonstrate that common patterns of divergence can be identified automatically without prior knowledge of a given language pair, and the patterns can be used to improve performance of projection algorithms.
Tasks	Word Alignment
Published	2016-05-14
URL	http://arxiv.org/abs/1605.04475v1
PDF	http://arxiv.org/pdf/1605.04475v1.pdf
PWC	https://paperswithcode.com/paper/capturing-divergence-in-dependency-trees-to
Repo
Framework

Gesture-based Bootstrapping for Egocentric Hand Segmentation


Title	Gesture-based Bootstrapping for Egocentric Hand Segmentation
Authors	Yubo Zhang, Vishnu Naresh Boddeti, Kris M. Kitani
Abstract	Accurately identifying hands in images is a key sub-task for human activity understanding with wearable first-person point-of-view cameras. Traditional hand segmentation approaches rely on a large corpus of manually labeled data to generate robust hand detectors. However, these approaches still face challenges as the appearance of the hand varies greatly across users, tasks, environments or illumination conditions. A key observation in the case of many wearable applications and interfaces is that, it is only necessary to accurately detect the user’s hands in a specific situational context. Based on this observation, we introduce an interactive approach to learn a person-specific hand segmentation model that does not require any manually labeled training data. Our approach proceeds in two steps, an interactive bootstrapping step for identifying moving hand regions, followed by learning a personalized user specific hand appearance model. Concretely, our approach uses two convolutional neural networks: (1) a gesture network that uses pre-defined motion information to detect the hand region; and (2) an appearance network that learns a person specific model of the hand region based on the output of the gesture network. During training, to make the appearance network robust to errors in the gesture network, the loss function of the former network incorporates the confidence of the gesture network while learning. Experiments demonstrate the robustness of our approach with an F1 score over 0.8 on all challenging datasets across a wide range of illumination and hand appearance variations, improving over a baseline approach by over 10%.
Tasks	Hand Segmentation
Published	2016-12-09
URL	http://arxiv.org/abs/1612.02889v2
PDF	http://arxiv.org/pdf/1612.02889v2.pdf
PWC	https://paperswithcode.com/paper/gesture-based-bootstrapping-for-egocentric
Repo
Framework

The Multi-fidelity Multi-armed Bandit


Title	The Multi-fidelity Multi-armed Bandit
Authors	Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, Barnabás Póczos
Abstract	We study a variant of the classical stochastic $K$-armed bandit where observing the outcome of each arm is expensive, but cheap approximations to this outcome are available. For example, in online advertising the performance of an ad can be approximated by displaying it for shorter time periods or to narrower audiences. We formalise this task as a multi-fidelity bandit, where, at each time step, the forecaster may choose to play an arm at any one of $M$ fidelities. The highest fidelity (desired outcome) expends cost $\lambda^{(m)}$. The $m^{\text{th}}$ fidelity (an approximation) expends $\lambda^{(m)} < \lambda^{(M)}$ and returns a biased estimate of the highest fidelity. We develop MF-UCB, a novel upper confidence bound procedure for this setting and prove that it naturally adapts to the sequence of available approximations and costs thus attaining better regret than naive strategies which ignore the approximations. For instance, in the above online advertising example, MF-UCB would use the lower fidelities to quickly eliminate suboptimal ads and reserve the larger expensive experiments on a small set of promising candidates. We complement this result with a lower bound and show that MF-UCB is nearly optimal under certain conditions.
Tasks
Published	2016-10-30
URL	http://arxiv.org/abs/1610.09726v1
PDF	http://arxiv.org/pdf/1610.09726v1.pdf
PWC	https://paperswithcode.com/paper/the-multi-fidelity-multi-armed-bandit
Repo
Framework

A Neural Knowledge Language Model


Title	A Neural Knowledge Language Model
Authors	Sungjin Ahn, Heeyoul Choi, Tanel Pärnamaa, Yoshua Bengio
Abstract	Current language models have a significant limitation in the ability to encode and decode factual knowledge. This is mainly because they acquire such knowledge from statistical co-occurrences although most of the knowledge words are rarely observed. In this paper, we propose a Neural Knowledge Language Model (NKLM) which combines symbolic knowledge provided by the knowledge graph with the RNN language model. By predicting whether the word to generate has an underlying fact or not, the model can generate such knowledge-related words by copying from the description of the predicted fact. In experiments, we show that the NKLM significantly improves the performance while generating a much smaller number of unknown words.
Tasks	Language Modelling
Published	2016-08-01
URL	http://arxiv.org/abs/1608.00318v2
PDF	http://arxiv.org/pdf/1608.00318v2.pdf
PWC	https://paperswithcode.com/paper/a-neural-knowledge-language-model
Repo
Framework

SyGuS-Comp 2016: Results and Analysis


Title	SyGuS-Comp 2016: Results and Analysis
Authors	Rajeev Alur, Dana Fisman, Rishabh Singh, Armando Solar-Lezama
Abstract	Syntax-Guided Synthesis (SyGuS) is the computational problem of finding an implementation f that meets both a semantic constraint given by a logical formula $\varphi$ in a background theory T, and a syntactic constraint given by a grammar G, which specifies the allowed set of candidate implementations. Such a synthesis problem can be formally defined in SyGuS-IF, a language that is built on top of SMT-LIB. The Syntax-Guided Synthesis Competition (SyGuS-Comp) is an effort to facilitate, bring together and accelerate research and development of efficient solvers for SyGuS by providing a platform for evaluating different synthesis techniques on a comprehensive set of benchmarks. In this year’s competition we added a new track devoted to programming by examples. This track consisted of two categories, one using the theory of bit-vectors and one using the theory of strings. This paper presents and analyses the results of SyGuS-Comp’16.
Tasks
Published	2016-11-23
URL	http://arxiv.org/abs/1611.07627v1
PDF	http://arxiv.org/pdf/1611.07627v1.pdf
PWC	https://paperswithcode.com/paper/sygus-comp-2016-results-and-analysis
Repo
Framework

Can we trust the bootstrap in high-dimension?


Title	Can we trust the bootstrap in high-dimension?
Authors	Noureddine El Karoui, Elizabeth Purdom
Abstract	We consider the performance of the bootstrap in high-dimensions for the setting of linear regression, where $p<n$ but $p/n$ is not close to zero. We consider ordinary least-squares as well as robust regression methods and adopt a minimalist performance requirement: can the bootstrap give us good confidence intervals for a single coordinate of $\beta$? (where $\beta$ is the true regression vector). We show through a mix of numerical and theoretical work that the bootstrap is fraught with problems. Both of the most commonly used methods of bootstrapping for regression – residual bootstrap and pairs bootstrap – give very poor inference on $\beta$ as the ratio $p/n$ grows. We find that the residuals bootstrap tend to give anti-conservative estimates (inflated Type I error), while the pairs bootstrap gives very conservative estimates (severe loss of power) as the ratio $p/n$ grows. We also show that the jackknife resampling technique for estimating the variance of $\hat{\beta}$ severely overestimates the variance in high dimensions. We contribute alternative bootstrap procedures based on our theoretical results that mitigate these problems. However, the corrections depend on assumptions regarding the underlying data-generation model, suggesting that in high-dimensions it may be difficult to have universal, robust bootstrapping techniques.
Tasks
Published	2016-08-02
URL	http://arxiv.org/abs/1608.00696v1
PDF	http://arxiv.org/pdf/1608.00696v1.pdf
PWC	https://paperswithcode.com/paper/can-we-trust-the-bootstrap-in-high-dimension
Repo
Framework

Measuring Book Impact Based on the Multi-granularity Online Review Mining


Title	Measuring Book Impact Based on the Multi-granularity Online Review Mining
Authors	Qingqing Zhou, Chengzhi Zhang, Star X. Zhao, Bikun Chen
Abstract	As with articles and journals, the customary methods for measuring books’ academic impact mainly involve citations, which is easy but limited to interrogating traditional citation databases and scholarly book reviews, Researchers have attempted to use other metrics, such as Google Books, libcitation, and publisher prestige. However, these approaches lack content-level information and cannot determine the citation intentions of users. Meanwhile, the abundant online review resources concerning academic books can be used to mine deeper information and content utilizing altmetric perspectives. In this study, we measure the impacts of academic books by multi-granularity mining online reviews, and we identify factors that affect a book’s impact. First, online reviews of a sample of academic books on Amazon.cn are crawled and processed. Then, multi-granularity review mining is conducted to identify review sentiment polarities and aspects’ sentiment values. Lastly, the numbers of positive reviews and negative reviews, aspect sentiment values, star values, and information regarding helpfulness are integrated via the entropy method, and lead to the calculation of the final book impact scores. The results of a correlation analysis of book impact scores obtained via our method versus traditional book citations show that, although there are substantial differences between subject areas, online book reviews tend to reflect the academic impact. Thus, we infer that online reviews represent a promising source for mining book impact within the altmetric perspective and at the multi-granularity content level. Moreover, our proposed method might also be a means by which to measure other books besides academic publications.
Tasks
Published	2016-03-26
URL	http://arxiv.org/abs/1603.08091v1
PDF	http://arxiv.org/pdf/1603.08091v1.pdf
PWC	https://paperswithcode.com/paper/measuring-book-impact-based-on-the-multi
Repo
Framework

Proceedings of the First International Workshop on Argumentation in Logic Programming and Non-Monotonic Reasoning (Arg-LPNMR 2016)


Title	Proceedings of the First International Workshop on Argumentation in Logic Programming and Non-Monotonic Reasoning (Arg-LPNMR 2016)
Authors	Sarah Alice Gaggl, Juan Carlos Nieves, Hannes Strass
Abstract	This volume contains the papers presented at Arg-LPNMR 2016: First International Workshop on Argumentation in Logic Programming and Nonmonotonic Reasoning held on July 8-10, 2016 in New York City, NY.
Tasks
Published	2016-11-08
URL	http://arxiv.org/abs/1611.02439v1
PDF	http://arxiv.org/pdf/1611.02439v1.pdf
PWC	https://paperswithcode.com/paper/proceedings-of-the-first-international-1
Repo
Framework

Adversary Resistant Deep Neural Networks with an Application to Malware Detection


Title	Adversary Resistant Deep Neural Networks with an Application to Malware Detection
Authors	Qinglong Wang, Wenbo Guo, Kaixuan Zhang, Alexander G. Ororbia II, Xinyu Xing, C. Lee Giles, Xue Liu
Abstract	Beyond its highly publicized victories in Go, there have been numerous successful applications of deep learning in information retrieval, computer vision and speech recognition. In cybersecurity, an increasing number of companies have become excited about the potential of deep learning, and have started to use it for various security incidents, the most popular being malware detection. These companies assert that deep learning (DL) could help turn the tide in the battle against malware infections. However, deep neural networks (DNNs) are vulnerable to adversarial samples, a flaw that plagues most if not all statistical learning models. Recent research has demonstrated that those with malicious intent can easily circumvent deep learning-powered malware detection by exploiting this flaw. In order to address this problem, previous work has developed various defense mechanisms that either augmenting training data or enhance model’s complexity. However, after a thorough analysis of the fundamental flaw in DNNs, we discover that the effectiveness of current defenses is limited and, more importantly, cannot provide theoretical guarantees as to their robustness against adversarial sampled-based attacks. As such, we propose a new adversary resistant technique that obstructs attackers from constructing impactful adversarial samples by randomly nullifying features within samples. In this work, we evaluate our proposed technique against a real world dataset with 14,679 malware variants and 17,399 benign programs. We theoretically validate the robustness of our technique, and empirically show that our technique significantly boosts DNN robustness to adversarial samples while maintaining high accuracy in classification. To demonstrate the general applicability of our proposed method, we also conduct experiments using the MNIST and CIFAR-10 datasets, generally used in image recognition research.
Tasks	Information Retrieval, Malware Detection, Speech Recognition
Published	2016-10-05
URL	http://arxiv.org/abs/1610.01239v4
PDF	http://arxiv.org/pdf/1610.01239v4.pdf
PWC	https://paperswithcode.com/paper/adversary-resistant-deep-neural-networks-with
Repo
Framework

Learning Personalized Optimal Control for Repeatedly Operated Systems


Title	Learning Personalized Optimal Control for Repeatedly Operated Systems
Authors	Theja Tulabandhula
Abstract	We consider the problem of online learning of optimal control for repeatedly operated systems in the presence of parametric uncertainty. During each round of operation, environment selects system parameters according to a fixed but unknown probability distribution. These parameters govern the dynamics of a plant. An agent chooses a control input to the plant and is then revealed the cost of the choice. In this setting, we design an agent that personalizes the control input to this plant taking into account the stochasticity involved. We demonstrate the effectiveness of our approach on a simulated system.
Tasks
Published	2016-09-18
URL	http://arxiv.org/abs/1609.05536v1
PDF	http://arxiv.org/pdf/1609.05536v1.pdf
PWC	https://paperswithcode.com/paper/learning-personalized-optimal-control-for
Repo
Framework

Annealing Gaussian into ReLU: a New Sampling Strategy for Leaky-ReLU RBM


Title	Annealing Gaussian into ReLU: a New Sampling Strategy for Leaky-ReLU RBM
Authors	Chun-Liang Li, Siamak Ravanbakhsh, Barnabas Poczos
Abstract	Restricted Boltzmann Machine (RBM) is a bipartite graphical model that is used as the building block in energy-based deep generative models. Due to numerical stability and quantifiability of the likelihood, RBM is commonly used with Bernoulli units. Here, we consider an alternative member of exponential family RBM with leaky rectified linear units – called leaky RBM. We first study the joint and marginal distributions of leaky RBM under different leakiness, which provides us important insights by connecting the leaky RBM model and truncated Gaussian distributions. The connection leads us to a simple yet efficient method for sampling from this model, where the basic idea is to anneal the leakiness rather than the energy; – i.e., start from a fully Gaussian/Linear unit and gradually decrease the leakiness over iterations. This serves as an alternative to the annealing of the temperature parameter and enables numerical estimation of the likelihood that are more efficient and more accurate than the commonly used annealed importance sampling (AIS). We further demonstrate that the proposed sampling algorithm enjoys faster mixing property than contrastive divergence algorithm, which benefits the training without any additional computational cost.
Tasks
Published	2016-11-11
URL	http://arxiv.org/abs/1611.03879v1
PDF	http://arxiv.org/pdf/1611.03879v1.pdf
PWC	https://paperswithcode.com/paper/annealing-gaussian-into-relu-a-new-sampling
Repo
Framework

Optimal Learning for Stochastic Optimization with Nonlinear Parametric Belief Models


Title	Optimal Learning for Stochastic Optimization with Nonlinear Parametric Belief Models
Authors	Xinyu He, Warren B. Powell
Abstract	We consider the problem of estimating the expected value of information (the knowledge gradient) for Bayesian learning problems where the belief model is nonlinear in the parameters. Our goal is to maximize some metric, while simultaneously learning the unknown parameters of the nonlinear belief model, by guiding a sequential experimentation process which is expensive. We overcome the problem of computing the expected value of an experiment, which is computationally intractable, by using a sampled approximation, which helps to guide experiments but does not provide an accurate estimate of the unknown parameters. We then introduce a resampling process which allows the sampled model to adapt to new information, exploiting past experiments. We show theoretically that the method converges asymptotically to the true parameters, while simultaneously maximizing our metric. We show empirically that the process exhibits rapid convergence, yielding good results with a very small number of experiments.
Tasks	Stochastic Optimization
Published	2016-11-22
URL	http://arxiv.org/abs/1611.07161v1
PDF	http://arxiv.org/pdf/1611.07161v1.pdf
PWC	https://paperswithcode.com/paper/optimal-learning-for-stochastic-optimization
Repo
Framework