May 7, 2019

2827 words 14 mins read

Paper Group ANR 50

Least Ambiguous Set-Valued Classifiers with Bounded Error Levels. An Evaluation of Information Sharing Parking Guidance Policies Using a Bayesian Approach. Challenges of Computational Processing of Code-Switching. Track Extraction with Hidden Reciprocal Chain Models. From Incremental Meaning to Semantic Unit (phrase by phrase). Improving Sparse Rep …

Least Ambiguous Set-Valued Classifiers with Bounded Error Levels


Title	Least Ambiguous Set-Valued Classifiers with Bounded Error Levels
Authors	Mauricio Sadinle, Jing Lei, Larry Wasserman
Abstract	In most classification tasks there are observations that are ambiguous and therefore difficult to correctly label. Set-valued classifiers output sets of plausible labels rather than a single label, thereby giving a more appropriate and informative treatment to the labeling of ambiguous instances. We introduce a framework for multiclass set-valued classification, where the classifiers guarantee user-defined levels of coverage or confidence (the probability that the true label is contained in the set) while minimizing the ambiguity (the expected size of the output). We first derive oracle classifiers assuming the true distribution to be known. We show that the oracle classifiers are obtained from level sets of the functions that define the conditional probability of each class. Then we develop estimators with good asymptotic and finite sample properties. The proposed estimators build on existing single-label classifiers. The optimal classifier can sometimes output the empty set, but we provide two solutions to fix this issue that are suitable for various practical needs.
Tasks
Published	2016-09-02
URL	http://arxiv.org/abs/1609.00451v2
PDF	http://arxiv.org/pdf/1609.00451v2.pdf
PWC	https://paperswithcode.com/paper/least-ambiguous-set-valued-classifiers-with
Repo
Framework


Title	An Evaluation of Information Sharing Parking Guidance Policies Using a Bayesian Approach
Authors	Xinyi Wu, Kartik Balkumar, Qi Luo, Robert Hampshire, Romesh Saigal
Abstract	Real-time parking occupancy information is critical for a parking management system to facilitate drivers to park more efficiently. Recent advances in connected and automated vehicle technologies enable sensor-equipped cars (probe cars) to detect and broadcast available parking spaces when driving through parking lots. In this paper, we evaluate the impact of market penetration of probe cars on the system performance, and investigate different parking guidance policies to improve the data acquisition process. We adopt a simulation-based approach to impose four policies on an off- street parking lot influencing the behavior of probe cars to park in assigned parking spaces. This in turn effects the scanning route and the parking space occupancy estimations. The last policy we propose is a near-optimal guidance strategy that maximizes the information gain of posteriors. The results suggest that an efficient information gathering policy can compensate for low penetration of connected and automated vehicles. We also highlight the policy trade-off that occur while attempting to maximize information gain through explorations and improve assignment accuracy through exploitations. Our results can assist urban policy makers in designing and managing smart parking systems.
Tasks
Published	2016-11-14
URL	http://arxiv.org/abs/1611.04845v1
PDF	http://arxiv.org/pdf/1611.04845v1.pdf
PWC	https://paperswithcode.com/paper/an-evaluation-of-information-sharing-parking
Repo
Framework

Challenges of Computational Processing of Code-Switching


Title	Challenges of Computational Processing of Code-Switching
Authors	Özlem Çetinoğlu, Sarah Schulz, Ngoc Thang Vu
Abstract	This paper addresses challenges of Natural Language Processing (NLP) on non-canonical multilingual data in which two or more languages are mixed. It refers to code-switching which has become more popular in our daily life and therefore obtains an increasing amount of attention from the research community. We report our experience that cov- ers not only core NLP tasks such as normalisation, language identification, language modelling, part-of-speech tagging and dependency parsing but also more downstream ones such as machine translation and automatic speech recognition. We highlight and discuss the key problems for each of the tasks with supporting examples from different language pairs and relevant previous work.
Tasks	Dependency Parsing, Language Identification, Language Modelling, Machine Translation, Part-Of-Speech Tagging, Speech Recognition
Published	2016-10-07
URL	http://arxiv.org/abs/1610.02213v1
PDF	http://arxiv.org/pdf/1610.02213v1.pdf
PWC	https://paperswithcode.com/paper/challenges-of-computational-processing-of
Repo
Framework

Track Extraction with Hidden Reciprocal Chain Models


Title	Track Extraction with Hidden Reciprocal Chain Models
Authors	George Stamatescu, Langford B White, Riley Bruce-Doust
Abstract	This paper develops Bayesian track extraction algorithms for targets modelled as hidden reciprocal chains (HRC). HRC are a class of finite-state random process models that generalise the familiar hidden Markov chains (HMC). HRC are able to model the “intention” of a target to proceed from a given origin to a destination, behaviour which cannot be properly captured by a HMC. While Bayesian estimation problems for HRC have previously been studied, this paper focusses principally on the problem of track extraction, of which the primary task is confirming target existence in a set of detections obtained from thresholding sensor measurements. Simulation examples are presented which show that the additional model information contained in a HRC improves detection performance when compared to HMC models.
Tasks
Published	2016-05-13
URL	http://arxiv.org/abs/1605.04046v1
PDF	http://arxiv.org/pdf/1605.04046v1.pdf
PWC	https://paperswithcode.com/paper/track-extraction-with-hidden-reciprocal-chain
Repo
Framework

From Incremental Meaning to Semantic Unit (phrase by phrase)


Title	From Incremental Meaning to Semantic Unit (phrase by phrase)
Authors	Andreas Scherbakov, Ekaterina Vylomova, Fei Liu, Timothy Baldwin
Abstract	This paper describes an experimental approach to Detection of Minimal Semantic Units and their Meaning (DiMSUM), explored within the framework of SemEval 2016 Task 10. The approach is primarily based on a combination of word embeddings and parserbased features, and employs unidirectional incremental computation of compositional embeddings for multiword expressions.
Tasks	Word Embeddings
Published	2016-04-17
URL	http://arxiv.org/abs/1604.04873v1
PDF	http://arxiv.org/pdf/1604.04873v1.pdf
PWC	https://paperswithcode.com/paper/from-incremental-meaning-to-semantic-unit
Repo
Framework

Improving Sparse Representation-Based Classification Using Local Principal Component Analysis


Title	Improving Sparse Representation-Based Classification Using Local Principal Component Analysis
Authors	Chelsea Weaver, Naoki Saito
Abstract	Sparse representation-based classification (SRC), proposed by Wright et al., seeks the sparsest decomposition of a test sample over the dictionary of training samples, with classification to the most-contributing class. Because it assumes test samples can be written as linear combinations of their same-class training samples, the success of SRC depends on the size and representativeness of the training set. Our proposed classification algorithm enlarges the training set by using local principal component analysis to approximate the basis vectors of the tangent hyperplane of the class manifold at each training sample. The dictionary in SRC is replaced by a local dictionary that adapts to the test sample and includes training samples and their corresponding tangent basis vectors. We use a synthetic data set and three face databases to demonstrate that this method can achieve higher classification accuracy than SRC in cases of sparse sampling, nonlinear class manifolds, and stringent dimension reduction.
Tasks	Dimensionality Reduction, Sparse Representation-based Classification
Published	2016-07-04
URL	http://arxiv.org/abs/1607.01059v6
PDF	http://arxiv.org/pdf/1607.01059v6.pdf
PWC	https://paperswithcode.com/paper/improving-sparse-representation-based
Repo
Framework


Title	What we write about when we write about causality: Features of causal statements across large-scale social discourse
Authors	Thomas C. McAndrew, Joshua C. Bongard, Christopher M. Danforth, Peter S. Dodds, Paul D. H. Hines, James P. Bagrow
Abstract	Identifying and communicating relationships between causes and effects is important for understanding our world, but is affected by language structure, cognitive and emotional biases, and the properties of the communication medium. Despite the increasing importance of social media, much remains unknown about causal statements made online. To study real-world causal attribution, we extract a large-scale corpus of causal statements made on the Twitter social network platform as well as a comparable random control corpus. We compare causal and control statements using statistical language and sentiment analysis tools. We find that causal statements have a number of significant lexical and grammatical differences compared with controls and tend to be more negative in sentiment than controls. Causal statements made online tend to focus on news and current events, medicine and health, or interpersonal relationships, as shown by topic models. By quantifying the features and potential biases of causality communication, this study improves our understanding of the accuracy of information and opinions found online.
Tasks	Sentiment Analysis, Topic Models
Published	2016-04-20
URL	http://arxiv.org/abs/1604.05781v2
PDF	http://arxiv.org/pdf/1604.05781v2.pdf
PWC	https://paperswithcode.com/paper/what-we-write-about-when-we-write-about
Repo
Framework

Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$


Title	Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$
Authors	Milan Banković
Abstract	In this paper, we investigate the possibility of improvement of the widely-used filtering algorithm for the linear constraints in constraint satisfaction problems in the presence of the alldifferent constraints. In many cases, the fact that the variables in a linear constraint are also constrained by some alldifferent constraints may help us to calculate stronger bounds of the variables, leading to a stronger constraint propagation. We propose an improved filtering algorithm that targets such cases. We provide a detailed description of the proposed algorithm and prove its correctness. We evaluate the approach on five different problems that involve combinations of the linear and the alldifferent constraints. We also compare our algorithm to other relevant approaches. The experimental results show a great potential of the proposed improvement.
Tasks
Published	2016-07-08
URL	http://arxiv.org/abs/1607.02466v2
PDF	http://arxiv.org/pdf/1607.02466v2.pdf
PWC	https://paperswithcode.com/paper/solving-finite-domain-linear-constraints-in
Repo
Framework

Robust Spectral Inference for Joint Stochastic Matrix Factorization


Title	Robust Spectral Inference for Joint Stochastic Matrix Factorization
Authors	Moontae Lee, David Bindel, David Mimno
Abstract	Spectral inference provides fast algorithms and provable optimality for latent topic analysis. But for real data these algorithms require additional ad-hoc heuristics, and even then often produce unusable results. We explain this poor performance by casting the problem of topic inference in the framework of Joint Stochastic Matrix Factorization (JSMF) and showing that previous methods violate the theoretical conditions necessary for a good solution to exist. We then propose a novel rectification method that learns high quality topics and their interactions even on small, noisy data. This method achieves results comparable to probabilistic techniques in several domains while maintaining scalability and provable optimality.
Tasks
Published	2016-11-01
URL	http://arxiv.org/abs/1611.00175v1
PDF	http://arxiv.org/pdf/1611.00175v1.pdf
PWC	https://paperswithcode.com/paper/robust-spectral-inference-for-joint
Repo
Framework

Distributed Dictionary Learning


Title	Distributed Dictionary Learning
Authors	Amir Daneshmand, Gesualdo Scutari, Francisco Facchinei
Abstract	The paper studies distributed Dictionary Learning (DL) problems where the learning task is distributed over a multi-agent network with time-varying (nonsymmetric) connectivity. This formulation is relevant, for instance, in big-data scenarios where massive amounts of data are collected/stored in different spatial locations and it is unfeasible to aggregate and/or process all the data in a fusion center, due to resource limitations, communication overhead or privacy considerations. We develop a general distributed algorithmic framework for the (nonconvex) DL problem and establish its asymptotic convergence. The new method hinges on Successive Convex Approximation (SCA) techniques coupled with i) a gradient tracking mechanism instrumental to locally estimate the missing global information; and ii) a consensus step, as a mechanism to distribute the computations among the agents. To the best of our knowledge, this is the first distributed algorithm with provable convergence for the DL problem and, more in general, bi-convex optimization problems over (time-varying) directed graphs.
Tasks	Dictionary Learning
Published	2016-12-21
URL	http://arxiv.org/abs/1612.07335v1
PDF	http://arxiv.org/pdf/1612.07335v1.pdf
PWC	https://paperswithcode.com/paper/distributed-dictionary-learning
Repo
Framework

Infinite-dimensional Log-Determinant divergences II: Alpha-Beta divergences


Title	Infinite-dimensional Log-Determinant divergences II: Alpha-Beta divergences
Authors	Minh Ha Quang
Abstract	This work presents a parametrized family of divergences, namely Alpha-Beta Log- Determinant (Log-Det) divergences, between positive definite unitized trace class operators on a Hilbert space. This is a generalization of the Alpha-Beta Log-Determinant divergences between symmetric, positive definite matrices to the infinite-dimensional setting. The family of Alpha-Beta Log-Det divergences is highly general and contains many divergences as special cases, including the recently formulated infinite dimensional affine-invariant Riemannian distance and the infinite-dimensional Alpha Log-Det divergences between positive definite unitized trace class operators. In particular, it includes a parametrized family of metrics between positive definite trace class operators, with the affine-invariant Riemannian distance and the square root of the symmetric Stein divergence being special cases. For the Alpha-Beta Log-Det divergences between covariance operators on a Reproducing Kernel Hilbert Space (RKHS), we obtain closed form formulas via the corresponding Gram matrices.
Tasks
Published	2016-10-13
URL	http://arxiv.org/abs/1610.08087v2
PDF	http://arxiv.org/pdf/1610.08087v2.pdf
PWC	https://paperswithcode.com/paper/infinite-dimensional-log-determinant
Repo
Framework

Provable Algorithms for Inference in Topic Models


Title	Provable Algorithms for Inference in Topic Models
Authors	Sanjeev Arora, Rong Ge, Frederic Koehler, Tengyu Ma, Ankur Moitra
Abstract	Recently, there has been considerable progress on designing algorithms with provable guarantees – typically using linear algebraic methods – for parameter learning in latent variable models. But designing provable algorithms for inference has proven to be more challenging. Here we take a first step towards provable inference in topic models. We leverage a property of topic models that enables us to construct simple linear estimators for the unknown topic proportions that have small variance, and consequently can work with short documents. Our estimators also correspond to finding an estimate around which the posterior is well-concentrated. We show lower bounds that for shorter documents it can be information theoretically impossible to find the hidden topics. Finally, we give empirical results that demonstrate that our algorithm works on realistic topic models. It yields good solutions on synthetic data and runs in time comparable to a {\em single} iteration of Gibbs sampling.
Tasks	Latent Variable Models, Topic Models
Published	2016-05-27
URL	http://arxiv.org/abs/1605.08491v1
PDF	http://arxiv.org/pdf/1605.08491v1.pdf
PWC	https://paperswithcode.com/paper/provable-algorithms-for-inference-in-topic
Repo
Framework

Position-Indexed Formulations for Kidney Exchange


Title	Position-Indexed Formulations for Kidney Exchange
Authors	John P. Dickerson, David F. Manlove, Benjamin Plaut, Tuomas Sandholm, James Trimble
Abstract	A kidney exchange is an organized barter market where patients in need of a kidney swap willing but incompatible donors. Determining an optimal set of exchanges is theoretically and empirically hard. Traditionally, exchanges took place in cycles, with each participating patient-donor pair both giving and receiving a kidney. The recent introduction of chains, where a donor without a paired patient triggers a sequence of donations without requiring a kidney in return, increased the efficacy of fielded kidney exchanges—while also dramatically raising the empirical computational hardness of clearing the market in practice. While chains can be quite long, unbounded-length chains are not desirable: planned donations can fail before transplant for a variety of reasons, and the failure of a single donation causes the rest of that chain to fail, so parallel shorter chains are better in practice. In this paper, we address the tractable clearing of kidney exchanges with short cycles and chains that are long but bounded. This corresponds to the practice at most modern fielded kidney exchanges. We introduce three new integer programming formulations, two of which are compact. Furthermore, one of these models has a linear programming relaxation that is exactly as tight as the previous tightest formulation (which was not compact) for instances in which each donor has a paired patient. On real data from the UNOS nationwide exchange in the United States and the NLDKSS nationwide exchange in the United Kingdom, as well as on generated realistic large-scale data, we show that our new models are competitive with all existing solvers—in many cases outperforming all other solvers by orders of magnitude.
Tasks
Published	2016-06-06
URL	http://arxiv.org/abs/1606.01623v2
PDF	http://arxiv.org/pdf/1606.01623v2.pdf
PWC	https://paperswithcode.com/paper/position-indexed-formulations-for-kidney
Repo
Framework

Joint Online Spoken Language Understanding and Language Modeling with Recurrent Neural Networks


Title	Joint Online Spoken Language Understanding and Language Modeling with Recurrent Neural Networks
Authors	Bing Liu, Ian Lane
Abstract	Speaker intent detection and semantic slot filling are two critical tasks in spoken language understanding (SLU) for dialogue systems. In this paper, we describe a recurrent neural network (RNN) model that jointly performs intent detection, slot filling, and language modeling. The neural network model keeps updating the intent estimation as word in the transcribed utterance arrives and uses it as contextual features in the joint model. Evaluation of the language model and online SLU model is made on the ATIS benchmarking data set. On language modeling task, our joint model achieves 11.8% relative reduction on perplexity comparing to the independent training language model. On SLU tasks, our joint model outperforms the independent task training model by 22.3% on intent detection error rate, with slight degradation on slot filling F1 score. The joint model also shows advantageous performance in the realistic ASR settings with noisy speech input.
Tasks	Intent Detection, Language Modelling, Slot Filling, Spoken Language Understanding
Published	2016-09-06
URL	http://arxiv.org/abs/1609.01462v1
PDF	http://arxiv.org/pdf/1609.01462v1.pdf
PWC	https://paperswithcode.com/paper/joint-online-spoken-language-understanding
Repo
Framework

Realtime Hierarchical Clustering based on Boundary and Surface Statistics


Title	Realtime Hierarchical Clustering based on Boundary and Surface Statistics
Authors	Dominik Alexander Klein, Dirk Schulz, Armin Bernd Cremers
Abstract	Visual grouping is a key mechanism in human scene perception. There, it belongs to the subconscious, early processing and is key prerequisite for other high level tasks such as recognition. In this paper, we introduce an efficient, realtime capable algorithm which likewise agglomerates a valuable hierarchical clustering of a scene, while using purely local appearance statistics. To speed up the processing, first we subdivide the image into meaningful, atomic segments using a fast Watershed transform. Starting from there, our rapid, agglomerative clustering algorithm prunes and maintains the connectivity graph between clusters to contain only such pairs, which directly touch in the image domain and are reciprocal nearest neighbors (RNN) wrt. a distance metric. The core of this approach is our novel cluster distance: it combines boundary and surface statistics both in terms of appearance as well as spatial linkage. This yields state-of-the-art performance, as we demonstrate in conclusive experiments conducted on BSDS500 and Pascal-Context datasets.
Tasks
Published	2016-09-22
URL	http://arxiv.org/abs/1609.06896v1
PDF	http://arxiv.org/pdf/1609.06896v1.pdf
PWC	https://paperswithcode.com/paper/realtime-hierarchical-clustering-based-on
Repo
Framework