May 5, 2019

3008 words 15 mins read

Paper Group ANR 542

Data Recombination for Neural Semantic Parsing. Blankets Joint Posterior score for learning Markov network structures. An Interactive Medical Image Segmentation Framework Using Iterative Refinement. Building Deep Networks on Grassmann Manifolds. Finite-Sample Analysis of Fixed-k Nearest Neighbor Density Functional Estimators. The End of Optimism? A …

Data Recombination for Neural Semantic Parsing


Title	Data Recombination for Neural Semantic Parsing
Authors	Robin Jia, Percy Liang
Abstract	Modeling crisp logical regularities is crucial in semantic parsing, making it difficult for neural models with no task-specific prior knowledge to achieve good results. In this paper, we introduce data recombination, a novel framework for injecting such prior knowledge into a model. From the training data, we induce a high-precision synchronous context-free grammar, which captures important conditional independence properties commonly found in semantic parsing. We then train a sequence-to-sequence recurrent network (RNN) model with a novel attention-based copying mechanism on datapoints sampled from this grammar, thereby teaching the model about these structural properties. Data recombination improves the accuracy of our RNN model on three semantic parsing datasets, leading to new state-of-the-art performance on the standard GeoQuery dataset for models with comparable supervision.
Tasks	Semantic Parsing
Published	2016-06-11
URL	http://arxiv.org/abs/1606.03622v1
PDF	http://arxiv.org/pdf/1606.03622v1.pdf
PWC	https://paperswithcode.com/paper/data-recombination-for-neural-semantic
Repo
Framework

Blankets Joint Posterior score for learning Markov network structures


Title	Blankets Joint Posterior score for learning Markov network structures
Authors	Federico Schlüter, Yanela Strappa, Diego H. Milone, Facundo Bromberg
Abstract	Markov networks are extensively used to model complex sequential, spatial, and relational interactions in a wide range of fields. By learning the structure of independences of a domain, more accurate joint probability distributions can be obtained for inference tasks or, more directly, for interpreting the most significant relations among the variables. Recently, several researchers have investigated techniques for automatically learning the structure from data by obtaining the probabilistic maximum-a-posteriori structure given the available data. However, all the approximations proposed decompose the posterior of the whole structure into local sub-problems, by assuming that the posteriors of the Markov blankets of all the variables are mutually independent. In this work, we propose a scoring function for relaxing such assumption. The Blankets Joint Posterior score computes the joint posterior of structures as a joint distribution of the collection of its Markov blankets. Essentially, the whole posterior is obtained by computing the posterior of the blanket of each variable as a conditional distribution that takes into account information from other blankets in the network. We show in our experimental results that the proposed approximation can improve the sample complexity of state-of-the-art scores when learning complex networks, where the independence assumption between blanket variables is clearly incorrect.
Tasks
Published	2016-08-08
URL	http://arxiv.org/abs/1608.02315v2
PDF	http://arxiv.org/pdf/1608.02315v2.pdf
PWC	https://paperswithcode.com/paper/blankets-joint-posterior-score-for-learning
Repo
Framework


Title	An Interactive Medical Image Segmentation Framework Using Iterative Refinement
Authors	Pratik Kalshetti, Manas Bundele, Parag Rahangdale, Dinesh Jangra, Chiranjoy Chattopadhyay, Gaurav Harit, Abhay Elhence
Abstract	Image segmentation is often performed on medical images for identifying diseases in clinical evaluation. Hence it has become one of the major research areas. Conventional image segmentation techniques are unable to provide satisfactory segmentation results for medical images as they contain irregularities. They need to be pre-processed before segmentation. In order to obtain the most suitable method for medical image segmentation, we propose a two stage algorithm. The first stage automatically generates a binary marker image of the region of interest using mathematical morphology. This marker serves as the mask image for the second stage which uses GrabCut on the input image thus resulting in an efficient segmented result. The obtained result can be further refined by user interaction which can be done using the Graphical User Interface (GUI). Experimental results show that the proposed method is accurate and provides satisfactory segmentation results with minimum user interaction on medical as well as natural images.
Tasks	Medical Image Segmentation, Semantic Segmentation
Published	2016-06-05
URL	http://arxiv.org/abs/1606.01453v1
PDF	http://arxiv.org/pdf/1606.01453v1.pdf
PWC	https://paperswithcode.com/paper/an-interactive-medical-image-segmentation
Repo
Framework

Building Deep Networks on Grassmann Manifolds


Title	Building Deep Networks on Grassmann Manifolds
Authors	Zhiwu Huang, Jiqing Wu, Luc Van Gool
Abstract	Learning representations on Grassmann manifolds is popular in quite a few visual recognition tasks. In order to enable deep learning on Grassmann manifolds, this paper proposes a deep network architecture by generalizing the Euclidean network paradigm to Grassmann manifolds. In particular, we design full rank mapping layers to transform input Grassmannian data to more desirable ones, exploit re-orthonormalization layers to normalize the resulting matrices, study projection pooling layers to reduce the model complexity in the Grassmannian context, and devise projection mapping layers to respect Grassmannian geometry and meanwhile achieve Euclidean forms for regular output layers. To train the Grassmann networks, we exploit a stochastic gradient descent setting on manifolds of the connection weights, and study a matrix generalization of backpropagation to update the structured data. The evaluations on three visual recognition tasks show that our Grassmann networks have clear advantages over existing Grassmann learning methods, and achieve results comparable with state-of-the-art approaches.
Tasks
Published	2016-11-17
URL	http://arxiv.org/abs/1611.05742v3
PDF	http://arxiv.org/pdf/1611.05742v3.pdf
PWC	https://paperswithcode.com/paper/building-deep-networks-on-grassmann-manifolds
Repo
Framework

Finite-Sample Analysis of Fixed-k Nearest Neighbor Density Functional Estimators


Title	Finite-Sample Analysis of Fixed-k Nearest Neighbor Density Functional Estimators
Authors	Shashank Singh, Barnabás Póczos
Abstract	We provide finite-sample analysis of a general framework for using k-nearest neighbor statistics to estimate functionals of a nonparametric continuous probability density, including entropies and divergences. Rather than plugging a consistent density estimate (which requires $k \to \infty$ as the sample size $n \to \infty$) into the functional of interest, the estimators we consider fix k and perform a bias correction. This is more efficient computationally, and, as we show in certain cases, statistically, leading to faster convergence rates. Our framework unifies several previous estimators, for most of which ours are the first finite sample guarantees.
Tasks
Published	2016-06-05
URL	http://arxiv.org/abs/1606.01554v1
PDF	http://arxiv.org/pdf/1606.01554v1.pdf
PWC	https://paperswithcode.com/paper/finite-sample-analysis-of-fixed-k-nearest
Repo
Framework

The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits


Title	The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
Authors	Tor Lattimore, Csaba Szepesvari
Abstract	Stochastic linear bandits are a natural and simple generalisation of finite-armed bandits with numerous practical applications. Current approaches focus on generalising existing techniques for finite-armed bandits, notably the optimism principle and Thompson sampling. While prior work has mostly been in the worst-case setting, we analyse the asymptotic instance-dependent regret and show matching upper and lower bounds on what is achievable. Surprisingly, our results show that no algorithm based on optimism or Thompson sampling will ever achieve the optimal rate, and indeed, can be arbitrarily far from optimal, even in very simple cases. This is a disturbing result because these techniques are standard tools that are widely used for sequential optimisation. For example, for generalised linear bandits and reinforcement learning.
Tasks
Published	2016-10-14
URL	http://arxiv.org/abs/1610.04491v1
PDF	http://arxiv.org/pdf/1610.04491v1.pdf
PWC	https://paperswithcode.com/paper/the-end-of-optimism-an-asymptotic-analysis-of
Repo
Framework

Generalized Fourier-Bessel operator and almost-periodic interpolation and approximation


Title	Generalized Fourier-Bessel operator and almost-periodic interpolation and approximation
Authors	Jean-Paul Gauthier, Dario Prandi
Abstract	We consider functions $f$ of two real variables, given as trigonometric functions over a finite set $F$ of frequencies. This set is assumed to be closed under rotations in the frequency plane of angle $\frac{2k\pi}{M}$ for some integer $M$. Firstly, we address the problem of evaluating these functions over a similar finite set $E$ in the space plane and, secondly, we address the problems of interpolating or approximating a function $g$ of two variables by such an $f$ over the grid $E.$ In particular, for this aim, we establish an abstract factorization theorem for the evaluation function, which is a key point for an efficient numerical solution to these problems. This result is based on the very special structure of the group $SE(2,N)$, subgroup of the group $SE(2)$ of motions of the plane corresponding to discrete rotations, which is a maximally almost periodic group. Although the motivation of this paper comes from our previous works on biomimetic image reconstruction and pattern recognition, where these questions appear naturally, this topic is related with several classical problems: the FFT in polar coordinates, the Non Uniform FFT, the evaluation of general trigonometric polynomials, and so on.
Tasks	Image Reconstruction
Published	2016-11-23
URL	http://arxiv.org/abs/1612.00056v1
PDF	http://arxiv.org/pdf/1612.00056v1.pdf
PWC	https://paperswithcode.com/paper/generalized-fourier-bessel-operator-and
Repo
Framework

Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising


Title	Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising
Authors	Jia Zhang, Zheng Wang, Qian Li, Jialin Zhang, Yanyan Lan, Qiang Li, Xiaoming Sun
Abstract	In this work, we study the guaranteed delivery model which is widely used in online display advertising. In the guaranteed delivery scenario, ad exposures (which are also called impressions in some works) to users are guaranteed by contracts signed in advance between advertisers and publishers. A crucial problem for the advertising platform is how to fully utilize the valuable user traffic to generate as much as possible revenue. Different from previous works which usually minimize the penalty of unsatisfied contracts and some other cost (e.g. representativeness), we propose the novel consumption minimization model, in which the primary objective is to minimize the user traffic consumed to satisfy all contracts. Under this model, we develop a near optimal method to deliver ads for users. The main advantage of our method lies in that it consumes nearly as least as possible user traffic to satisfy all contracts, therefore more contracts can be accepted to produce more revenue. It also enables the publishers to estimate how much user traffic is redundant or short so that they can sell or buy this part of traffic in bulk in the exchange market. Furthermore, it is robust with regard to priori knowledge of user type distribution. Finally, the simulation shows that our method outperforms the traditional state-of-the-art methods.
Tasks
Published	2016-11-23
URL	http://arxiv.org/abs/1611.07599v1
PDF	http://arxiv.org/pdf/1611.07599v1.pdf
PWC	https://paperswithcode.com/paper/efficient-delivery-policy-to-minimize-user
Repo
Framework

Deep Action- and Context-Aware Sequence Learning for Activity Recognition and Anticipation


Title	Deep Action- and Context-Aware Sequence Learning for Activity Recognition and Anticipation
Authors	Mohammad Sadegh Aliakbarian, Fatemehsadat Saleh, Basura Fernando, Mathieu Salzmann, Lars Petersson, Lars Andersson
Abstract	Action recognition and anticipation are key to the success of many computer vision applications. Existing methods can roughly be grouped into those that extract global, context-aware representations of the entire image or sequence, and those that aim at focusing on the regions where the action occurs. While the former may suffer from the fact that context is not always reliable, the latter completely ignore this source of information, which can nonetheless be helpful in many situations. In this paper, we aim at making the best of both worlds by developing an approach that leverages both context-aware and action-aware features. At the core of our method lies a novel multi-stage recurrent architecture that allows us to effectively combine these two sources of information throughout a video. This architecture first exploits the global, context-aware features, and merges the resulting representation with the localized, action-aware ones. Our experiments on standard datasets evidence the benefits of our approach over methods that use each information type separately. We outperform the state-of-the-art methods that, as us, rely only on RGB frames as input for both action recognition and anticipation.
Tasks	Activity Recognition, Temporal Action Localization
Published	2016-11-17
URL	http://arxiv.org/abs/1611.05520v2
PDF	http://arxiv.org/pdf/1611.05520v2.pdf
PWC	https://paperswithcode.com/paper/deep-action-and-context-aware-sequence
Repo
Framework

Maximum entropy models capture melodic styles


Title	Maximum entropy models capture melodic styles
Authors	Jason Sakellariou, Francesca Tria, Vittorio Loreto, François Pachet
Abstract	We introduce a Maximum Entropy model able to capture the statistics of melodies in music. The model can be used to generate new melodies that emulate the style of the musical corpus which was used to train it. Instead of using the $n-$body interactions of $(n-1)-$order Markov models, traditionally used in automatic music generation, we use a $k-$nearest neighbour model with pairwise interactions only. In that way, we keep the number of parameters low and avoid over-fitting problems typical of Markov models. We show that long-range musical phrases don’t need to be explicitly enforced using high-order Markov interactions, but can instead emerge from multiple, competing, pairwise interactions. We validate our Maximum Entropy model by contrasting how much the generated sequences capture the style of the original corpus without plagiarizing it. To this end we use a data-compression approach to discriminate the levels of borrowing and innovation featured by the artificial sequences. The results show that our modelling scheme outperforms both fixed-order and variable-order Markov models. This shows that, despite being based only on pairwise interactions, this Maximum Entropy scheme opens the possibility to generate musically sensible alterations of the original phrases, providing a way to generate innovation.
Tasks	Music Generation
Published	2016-10-11
URL	http://arxiv.org/abs/1610.03414v1
PDF	http://arxiv.org/pdf/1610.03414v1.pdf
PWC	https://paperswithcode.com/paper/maximum-entropy-models-capture-melodic-styles
Repo
Framework

Classifying Syntactic Regularities for Hundreds of Languages


Title	Classifying Syntactic Regularities for Hundreds of Languages
Authors	Reed Coke, Ben King, Dragomir Radev
Abstract	This paper presents a comparison of classification methods for linguistic typology for the purpose of expanding an extensive, but sparse language resource: the World Atlas of Language Structures (WALS) (Dryer and Haspelmath, 2013). We experimented with a variety of regression and nearest-neighbor methods for use in classification over a set of 325 languages and six syntactic rules drawn from WALS. To classify each rule, we consider the typological features of the other five rules; linguistic features extracted from a word-aligned Bible in each language; and genealogical features (genus and family) of each language. In general, we find that propagating the majority label among all languages of the same genus achieves the best accuracy in label pre- diction. Following this, a logistic regression model that combines typological and linguistic features offers the next best performance. Interestingly, this model actually outperforms the majority labels among all languages of the same family.
Tasks
Published	2016-03-25
URL	http://arxiv.org/abs/1603.08016v2
PDF	http://arxiv.org/pdf/1603.08016v2.pdf
PWC	https://paperswithcode.com/paper/classifying-syntactic-regularities-for
Repo
Framework

Conservative Contextual Linear Bandits


Title	Conservative Contextual Linear Bandits
Authors	Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi-Yadkori, Benjamin Van Roy
Abstract	Safety is a desirable property that can immensely increase the applicability of learning algorithms in real-world decision-making problems. It is much easier for a company to deploy an algorithm that is safe, i.e., guaranteed to perform at least as well as a baseline. In this paper, we study the issue of safety in contextual linear bandits that have application in many different fields including personalized ad recommendation in online marketing. We formulate a notion of safety for this class of algorithms. We develop a safe contextual linear bandit algorithm, called conservative linear UCB (CLUCB), that simultaneously minimizes its regret and satisfies the safety constraint, i.e., maintains its performance above a fixed percentage of the performance of a baseline strategy, uniformly over time. We prove an upper-bound on the regret of CLUCB and show that it can be decomposed into two terms: 1) an upper-bound for the regret of the standard linear UCB algorithm that grows with the time horizon and 2) a constant (does not grow with the time horizon) term that accounts for the loss of being conservative in order to satisfy the safety constraint. We empirically show that our algorithm is safe and validate our theoretical analysis.
Tasks	Decision Making
Published	2016-11-19
URL	http://arxiv.org/abs/1611.06426v2
PDF	http://arxiv.org/pdf/1611.06426v2.pdf
PWC	https://paperswithcode.com/paper/conservative-contextual-linear-bandits
Repo
Framework

Chinese Restaurant Process for cognate clustering: A threshold free approach


Title	Chinese Restaurant Process for cognate clustering: A threshold free approach
Authors	Taraka Rama
Abstract	In this paper, we introduce a threshold free approach, motivated from Chinese Restaurant Process, for the purpose of cognate clustering. We show that our approach yields similar results to a linguistically motivated cognate clustering system known as LexStat. Our Chinese Restaurant Process system is fast and does not require any threshold and can be applied to any language family of the world.
Tasks
Published	2016-10-19
URL	http://arxiv.org/abs/1610.06053v1
PDF	http://arxiv.org/pdf/1610.06053v1.pdf
PWC	https://paperswithcode.com/paper/chinese-restaurant-process-for-cognate
Repo
Framework

Object Detection Free Instance Segmentation With Labeling Transformations


Title	Object Detection Free Instance Segmentation With Labeling Transformations
Authors	Long Jin, Zeyu Chen, Zhuowen Tu
Abstract	Instance segmentation has attracted recent attention in computer vision and existing methods in this domain mostly have an object detection stage. In this paper, we study the intrinsic challenge of the instance segmentation problem, the presence of a quotient space (swapping the labels of different instances leads to the same result), and propose new methods that are object proposal- and object detection- free. We propose three alternative methods, namely pixel-based affinity mapping, superpixel-based affinity learning, and boundary-based component segmentation, all focusing on performing labeling transformations to cope with the quotient space problem. By adopting fully convolutional neural networks (FCN) like models, our framework attains competitive results on both the PASCAL dataset (object-centric) and the Gland dataset (texture-centric), which the existing methods are not able to do. Our work also has the advantages in its transparency, simplicity, and being all segmentation based.
Tasks	Instance Segmentation, Object Detection, Semantic Segmentation
Published	2016-11-28
URL	http://arxiv.org/abs/1611.08991v2
PDF	http://arxiv.org/pdf/1611.08991v2.pdf
PWC	https://paperswithcode.com/paper/object-detection-free-instance-segmentation
Repo
Framework

Efficient Activity Detection in Untrimmed Video with Max-Subgraph Search


Title	Efficient Activity Detection in Untrimmed Video with Max-Subgraph Search
Authors	Chao-Yeh Chen, Kristen Grauman
Abstract	We propose an efficient approach for activity detection in video that unifies activity categorization with space-time localization. The main idea is to pose activity detection as a maximum-weight connected subgraph problem. Offline, we learn a binary classifier for an activity category using positive video exemplars that are “trimmed” in time to the activity of interest. Then, given a novel \emph{untrimmed} video sequence, we decompose it into a 3D array of space-time nodes, which are weighted based on the extent to which their component features support the learned activity model. To perform detection, we then directly localize instances of the activity by solving for the maximum-weight connected subgraph in the test video’s space-time graph. We show that this detection strategy permits an efficient branch-and-cut solution for the best-scoring—and possibly non-cubically shaped—portion of the video for a given activity classifier. The upshot is a fast method that can search a broader space of space-time region candidates than was previously practical, which we find often leads to more accurate detection. We demonstrate the proposed algorithm on four datasets, and we show its speed and accuracy advantages over multiple existing search strategies.
Tasks	Action Detection, Activity Detection
Published	2016-07-11
URL	http://arxiv.org/abs/1607.02815v1
PDF	http://arxiv.org/pdf/1607.02815v1.pdf
PWC	https://paperswithcode.com/paper/efficient-activity-detection-in-untrimmed
Repo
Framework