October 16, 2019

3067 words 15 mins read

Paper Group ANR 980

Interpretable Clustering via Optimal Trees. Unveiling the semantic structure of text documents using paragraph-aware Topic Models. Local Visual Microphones: Improved Sound Extraction from Silent Video. Learning to Predict Ego-Vehicle Poses for Sampling-Based Nonholonomic Motion Planning. Online learning over a finite action set with limited switchi …

Interpretable Clustering via Optimal Trees


Title	Interpretable Clustering via Optimal Trees
Authors	Dimitris Bertsimas, Agni Orfanoudaki, Holly Wiberg
Abstract	State-of-the-art clustering algorithms use heuristics to partition the feature space and provide little insight into the rationale for cluster membership, limiting their interpretability. In healthcare applications, the latter poses a barrier to the adoption of these methods since medical researchers are required to provide detailed explanations of their decisions in order to gain patient trust and limit liability. We present a new unsupervised learning algorithm that leverages Mixed Integer Optimization techniques to generate interpretable tree-based clustering models. Utilizing the flexible framework of Optimal Trees, our method approximates the globally optimal solution leading to high quality partitions of the feature space. Our algorithm, can incorporate various internal validation metrics, naturally determines the optimal number of clusters, and is able to account for mixed numeric and categorical data. It achieves comparable or superior performance on both synthetic and real world datasets when compared to K-Means while offering significantly higher interpretability.
Tasks
Published	2018-12-03
URL	http://arxiv.org/abs/1812.00539v1
PDF	http://arxiv.org/pdf/1812.00539v1.pdf
PWC	https://paperswithcode.com/paper/interpretable-clustering-via-optimal-trees
Repo
Framework

Unveiling the semantic structure of text documents using paragraph-aware Topic Models


Title	Unveiling the semantic structure of text documents using paragraph-aware Topic Models
Authors	Simón Roca-Sotelo, Jerónimo Arenas-García
Abstract	Classic Topic Models are built under the Bag Of Words assumption, in which word position is ignored for simplicity. Besides, symmetric priors are typically used in most applications. In order to easily learn topics with different properties among the same corpus, we propose a new line of work in which the paragraph structure is exploited. Our proposal is based on the following assumption: in many text document corpora there are formal constraints shared across all the collection, e.g. sections. When this assumption is satisfied, some paragraphs may be related to general concepts shared by all documents in the corpus, while others would contain the genuine description of documents. Assuming each paragraph can be semantically more general, specific, or hybrid, we look for ways to measure this, transferring this distinction to topics and being able to learn what we call specific and general topics. Experiments show that this is a proper methodology to highlight certain paragraphs in structured documents at the same time we learn interesting and more diverse topics.
Tasks	Topic Models
Published	2018-06-26
URL	http://arxiv.org/abs/1806.09827v1
PDF	http://arxiv.org/pdf/1806.09827v1.pdf
PWC	https://paperswithcode.com/paper/unveiling-the-semantic-structure-of-text
Repo
Framework

Local Visual Microphones: Improved Sound Extraction from Silent Video


Title	Local Visual Microphones: Improved Sound Extraction from Silent Video
Authors	Mohammad Amin Shabani, Laleh Samadfam, Mohammad Amin Sadeghi
Abstract	Sound waves cause small vibrations in nearby objects. A few techniques exist in the literature that can extract sound from video. In this paper we study local vibration patterns at different image locations. We show that different locations in the image vibrate differently. We carefully aggregate local vibrations and produce a sound quality that improves state-of-the-art. We show that local vibrations could have a time delay because sound waves take time to travel through the air. We use this phenomenon to estimate sound direction. We also present a novel algorithm that speeds up sound extraction by two to three orders of magnitude and reaches real-time performance in a 20KHz video.
Tasks
Published	2018-01-29
URL	http://arxiv.org/abs/1801.09436v1
PDF	http://arxiv.org/pdf/1801.09436v1.pdf
PWC	https://paperswithcode.com/paper/local-visual-microphones-improved-sound
Repo
Framework

Learning to Predict Ego-Vehicle Poses for Sampling-Based Nonholonomic Motion Planning


Title	Learning to Predict Ego-Vehicle Poses for Sampling-Based Nonholonomic Motion Planning
Authors	Holger Banzhaf, Paul Sanzenbacher, Ulrich Baumann, J. Marius Zöllner
Abstract	Sampling-based motion planning is an effective tool to compute safe trajectories for automated vehicles in complex environments. However, a fast convergence to the optimal solution can only be ensured with the use of problem-specific sampling distributions. Due to the large variety of driving situations within the context of automated driving, it is very challenging to manually design such distributions. This paper introduces therefore a data-driven approach utilizing a deep convolutional neural network (CNN): Given the current driving situation, future ego-vehicle poses can be directly generated from the output of the CNN allowing to guide the motion planner efficiently towards the optimal solution. A benchmark highlights that the CNN predicts future vehicle poses with a higher accuracy compared to uniform sampling and a state-of-the-art A-based approach. Combining this CNN-guided sampling with the motion planner Bidirectional RRT reduces the computation time by up to an order of magnitude and yields a faster convergence to a lower cost as well as a success rate of 100 % in the tested scenarios.
Tasks	Motion Planning
Published	2018-12-03
URL	http://arxiv.org/abs/1812.01127v2
PDF	http://arxiv.org/pdf/1812.01127v2.pdf
PWC	https://paperswithcode.com/paper/learning-to-predict-ego-vehicle-poses-for
Repo
Framework

Online learning over a finite action set with limited switching


Title	Online learning over a finite action set with limited switching
Authors	Jason Altschuler, Kunal Talwar
Abstract	This paper studies the value of switching actions in the Prediction From Experts (PFE) problem and Adversarial Multi-Armed Bandits (MAB) problem. First, we revisit the well-studied and practically motivated setting of PFE with switching costs. Many algorithms are known to achieve the minimax optimal order of $O(\sqrt{T \log n})$ in expectation for both regret and number of switches, where $T$ is the number of iterations and $n$ the number of actions. However, no high probability (h.p.) guarantees are known. Our main technical contribution is the first algorithms which with h.p. achieve this optimal order for both regret and switches. This settles an open problem of [Devroye et al., 2015], and directly implies the first h.p. guarantees for several problems of interest. Next, to investigate the value of switching actions at a more granular level, we introduce the setting of switching budgets, in which algorithms are limited to $S \leq T$ switches between actions. This entails a limited number of free switches, in contrast to the unlimited number of expensive switches in the switching cost setting. Using the above result and several reductions, we unify previous work and completely characterize the complexity of this switching budget setting up to small polylogarithmic factors: for both PFE and MAB, for all switching budgets $S \leq T$, and for both expectation and h.p. guarantees. For PFE, we show the optimal rate is $\tilde{\Theta}(\sqrt{T\log n})$ for $S = \Omega(\sqrt{T\log n})$, and $\min(\tilde{\Theta}(\tfrac{T\log n}{S}), T)$ for $S = O(\sqrt{T \log n})$. Interestingly, the bandit setting does not exhibit such a phase transition; instead we show the minimax rate decays steadily as $\min(\tilde{\Theta}(\tfrac{T\sqrt{n}}{\sqrt{S}}), T)$ for all ranges of $S \leq T$. These results recover and generalize the known minimax rates for the (arbitrary) switching cost setting.
Tasks	Multi-Armed Bandits
Published	2018-03-05
URL	http://arxiv.org/abs/1803.01548v2
PDF	http://arxiv.org/pdf/1803.01548v2.pdf
PWC	https://paperswithcode.com/paper/online-learning-over-a-finite-action-set-with
Repo
Framework

Improving Word Vector with Prior Knowledge in Semantic Dictionary


Title	Improving Word Vector with Prior Knowledge in Semantic Dictionary
Authors	Wei Li, Yunfang Wu, Xueqiang Lv
Abstract	Using low dimensional vector space to represent words has been very effective in many NLP tasks. However, it doesn’t work well when faced with the problem of rare and unseen words. In this paper, we propose to leverage the knowledge in semantic dictionary in combination with some morphological information to build an enhanced vector space. We get an improvement of 2.3% over the state-of-the-art Heidel Time system in temporal expression recognition, and obtain a large gain in other name entity recognition (NER) tasks. The semantic dictionary Hownet alone also shows promising results in computing lexical similarity.
Tasks
Published	2018-01-27
URL	http://arxiv.org/abs/1801.09031v1
PDF	http://arxiv.org/pdf/1801.09031v1.pdf
PWC	https://paperswithcode.com/paper/improving-word-vector-with-prior-knowledge-in
Repo
Framework

The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates


Title	The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates
Authors	Henry WJ Reeve, Joe Mellor, Gavin Brown
Abstract	In this paper we propose and explore the k-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates. We focus on a setting where the covariates are supported on a metric space of low intrinsic dimension, such as a manifold embedded within a high dimensional ambient feature space. The algorithm is conceptually simple and straightforward to implement. The k-Nearest Neighbour UCB algorithm does not require prior knowledge of the either the intrinsic dimension of the marginal distribution or the time horizon. We prove a regret bound for the k-Nearest Neighbour UCB algorithm which is minimax optimal up to logarithmic factors. In particular, the algorithm automatically takes advantage of both low intrinsic dimensionality of the marginal distribution over the covariates and low noise in the data, expressed as a margin condition. In addition, focusing on the case of bounded rewards, we give corresponding regret bounds for the k-Nearest Neighbour KL-UCB algorithm, which is an analogue of the KL-UCB algorithm adapted to the setting of multi-armed bandits with covariates. Finally, we present empirical results which demonstrate the ability of both the k-Nearest Neighbour UCB and k-Nearest Neighbour KL-UCB to take advantage of situations where the data is supported on an unknown sub-manifold of a high-dimensional feature space.
Tasks	Multi-Armed Bandits
Published	2018-03-01
URL	http://arxiv.org/abs/1803.00316v1
PDF	http://arxiv.org/pdf/1803.00316v1.pdf
PWC	https://paperswithcode.com/paper/the-k-nearest-neighbour-ucb-algorithm-for
Repo
Framework

The Temporal Singularity: time-accelerated simulated civilizations and their implications


Title	The Temporal Singularity: time-accelerated simulated civilizations and their implications
Authors	Giacomo Spigler
Abstract	Provided significant future progress in artificial intelligence and computing, it may ultimately be possible to create multiple Artificial General Intelligences (AGIs), and possibly entire societies living within simulated environments. In that case, it should be possible to improve the problem solving capabilities of the system by increasing the speed of the simulation. If a minimal simulation with sufficient capabilities is created, it might manage to increase its own speed by accelerating progress in science and technology, in a way similar to the Technological Singularity. This may ultimately lead to large simulated civilizations unfolding at extreme temporal speedups, achieving what from the outside would look like a Temporal Singularity. Here we discuss the feasibility of the minimal simulation and the potential advantages, dangers, and connection to the Fermi paradox of the Temporal Singularity. The medium-term importance of the topic derives from the amount of computational power required to start the process, which could be available within the next decades, making the Temporal Singularity theoretically possible before the end of the century.
Tasks
Published	2018-06-22
URL	http://arxiv.org/abs/1806.08561v1
PDF	http://arxiv.org/pdf/1806.08561v1.pdf
PWC	https://paperswithcode.com/paper/the-temporal-singularity-time-accelerated
Repo
Framework

Regional Multi-Armed Bandits


Title	Regional Multi-Armed Bandits
Authors	Zhiyang Wang, Ruida Zhou, Cong Shen
Abstract	We consider a variant of the classic multi-armed bandit problem where the expected reward of each arm is a function of an unknown parameter. The arms are divided into different groups, each of which has a common parameter. Therefore, when the player selects an arm at each time slot, information of other arms in the same group is also revealed. This regional bandit model naturally bridges the non-informative bandit setting where the player can only learn the chosen arm, and the global bandit model where sampling one arms reveals information of all arms. We propose an efficient algorithm, UCB-g, that solves the regional bandit problem by combining the Upper Confidence Bound (UCB) and greedy principles. Both parameter-dependent and parameter-free regret upper bounds are derived. We also establish a matching lower bound, which proves the order-optimality of UCB-g. Moreover, we propose SW-UCB-g, which is an extension of UCB-g for a non-stationary environment where the parameters slowly vary over time.
Tasks	Multi-Armed Bandits
Published	2018-02-22
URL	http://arxiv.org/abs/1802.07917v1
PDF	http://arxiv.org/pdf/1802.07917v1.pdf
PWC	https://paperswithcode.com/paper/regional-multi-armed-bandits
Repo
Framework

Online Learning with an Unknown Fairness Metric


Title	Online Learning with an Unknown Fairness Metric
Authors	Stephen Gillen, Christopher Jung, Michael Kearns, Aaron Roth
Abstract	We consider the problem of online learning in the linear contextual bandits setting, but in which there are also strong individual fairness constraints governed by an unknown similarity metric. These constraints demand that we select similar actions or individuals with approximately equal probability (arXiv:1104.3913), which may be at odds with optimizing reward, thus modeling settings where profit and social policy are in tension. We assume we learn about an unknown Mahalanobis similarity metric from only weak feedback that identifies fairness violations, but does not quantify their extent. This is intended to represent the interventions of a regulator who “knows unfairness when he sees it” but nevertheless cannot enunciate a quantitative fairness metric over individuals. Our main result is an algorithm in the adversarial context setting that has a number of fairness violations that depends only logarithmically on $T$, while obtaining an optimal $O(\sqrt{T})$ regret bound to the best fair policy.
Tasks	Multi-Armed Bandits
Published	2018-02-20
URL	http://arxiv.org/abs/1802.06936v2
PDF	http://arxiv.org/pdf/1802.06936v2.pdf
PWC	https://paperswithcode.com/paper/online-learning-with-an-unknown-fairness
Repo
Framework

Ensemble p-Laplacian Regularization for Remote Sensing Image Recognition


Title	Ensemble p-Laplacian Regularization for Remote Sensing Image Recognition
Authors	Xueqi Ma, Weifeng Liu, Dapeng Tao, Yicong Zhou
Abstract	Recently, manifold regularized semi-supervised learning (MRSSL) received considerable attention because it successfully exploits the geometry of the intrinsic data probability distribution including both labeled and unlabeled samples to leverage the performance of a learning model. As a natural nonlinear generalization of graph Laplacian, p-Laplacian has been proved having the rich theoretical foundations to better preserve the local structure. However, it is difficult to determine the fitting graph p-Lapalcian i.e. the parameter which is a critical factor for the performance of graph p-Laplacian. Therefore, we develop an ensemble p-Laplacian regularization (EpLapR) to fully approximate the intrinsic manifold of the data distribution. EpLapR incorporates multiple graphs into a regularization term in order to sufficiently explore the complementation of graph p-Laplacian. Specifically, we construct a fused graph by introducing an optimization approach to assign suitable weights on different p-value graphs. And then, we conduct semi-supervised learning framework on the fused graph. Extensive experiments on UC-Merced data set demonstrate the effectiveness and efficiency of the proposed method.
Tasks
Published	2018-06-21
URL	http://arxiv.org/abs/1806.08109v1
PDF	http://arxiv.org/pdf/1806.08109v1.pdf
PWC	https://paperswithcode.com/paper/ensemble-p-laplacian-regularization-for
Repo
Framework

Multi-Armed Bandits on Partially Revealed Unit Interval Graphs


Title	Multi-Armed Bandits on Partially Revealed Unit Interval Graphs
Authors	Xiao Xu, Sattar Vakili, Qing Zhao, Ananthram Swami
Abstract	A stochastic multi-armed bandit problem with side information on the similarity and dissimilarity across different arms is considered. The action space of the problem can be represented by a unit interval graph (UIG) where each node represents an arm and the presence (absence) of an edge between two nodes indicates similarity (dissimilarity) between their mean rewards. Two settings of complete and partial side information based on whether the UIG is fully revealed are studied and a general two-step learning structure consisting of an offline reduction of the action space and online aggregation of reward observations from similar arms is proposed to fully exploit the topological structure of the side information. In both cases, the computation efficiency and the order optimality of the proposed learning policies in terms of both the size of the action space and the time length are established.
Tasks	Multi-Armed Bandits
Published	2018-02-12
URL	https://arxiv.org/abs/1802.04339v3
PDF	https://arxiv.org/pdf/1802.04339v3.pdf
PWC	https://paperswithcode.com/paper/multi-armed-bandits-on-partially-revealed
Repo
Framework

RAPIDNN: In-Memory Deep Neural Network Acceleration Framework


Title	RAPIDNN: In-Memory Deep Neural Network Acceleration Framework
Authors	Mohsen Imani, Mohammad Samragh, Yeseong Kim, Saransh Gupta, Farinaz Koushanfar, Tajana Rosing
Abstract	Deep neural networks (DNN) have demonstrated effectiveness for various applications such as image processing, video segmentation, and speech recognition. Running state-of-the-art DNNs on current systems mostly relies on either generalpurpose processors, ASIC designs, or FPGA accelerators, all of which suffer from data movements due to the limited onchip memory and data transfer bandwidth. In this work, we propose a novel framework, called RAPIDNN, which processes all DNN operations within the memory to minimize the cost of data movement. To enable in-memory processing, RAPIDNN reinterprets a DNN model and maps it into a specialized accelerator, which is designed using non-volatile memory blocks that model four fundamental DNN operations, i.e., multiplication, addition, activation functions, and pooling. The framework extracts representative operands of a DNN model, e.g., weights and input values, using clustering methods to optimize the model for in-memory processing. Then, it maps the extracted operands and their precomputed results into the accelerator memory blocks. At runtime, the accelerator identifies computation results based on efficient in-memory search capability which also provides tunability of approximation to further improve computation efficiency. Our evaluation shows that RAPIDNN achieves 68.4x, 49.5x energy efficiency improvement and 48.1x, 10.9x speedup as compared to ISAAC and PipeLayer, the state-of-the-art DNN accelerators, while ensuring less than 0.3% of quality loss.
Tasks	Speech Recognition, Video Semantic Segmentation
Published	2018-06-15
URL	http://arxiv.org/abs/1806.05794v4
PDF	http://arxiv.org/pdf/1806.05794v4.pdf
PWC	https://paperswithcode.com/paper/rapidnn-in-memory-deep-neural-network
Repo
Framework

The problem with probabilistic DAG automata for semantic graphs


Title	The problem with probabilistic DAG automata for semantic graphs
Authors	Ieva Vasiljeva, Sorcha Gilroy, Adam Lopez
Abstract	Semantic representations in the form of directed acyclic graphs (DAGs) have been introduced in recent years, and to model them, we need probabilistic models of DAGs. One model that has attracted some attention is the DAG automaton, but it has not been studied as a probabilistic model. We show that some DAG automata cannot be made into useful probabilistic models by the nearly universal strategy of assigning weights to transitions. The problem affects single-rooted, multi-rooted, and unbounded-degree variants of DAG automata, and appears to be pervasive. It does not affect planar variants, but these are problematic for other reasons.
Tasks
Published	2018-10-29
URL	http://arxiv.org/abs/1810.12266v2
PDF	http://arxiv.org/pdf/1810.12266v2.pdf
PWC	https://paperswithcode.com/paper/the-problem-with-probabilistic-dag-automata
Repo
Framework

An Efficient Approach to Encoding Context for Spoken Language Understanding


Title	An Efficient Approach to Encoding Context for Spoken Language Understanding
Authors	Raghav Gupta, Abhinav Rastogi, Dilek Hakkani-Tur
Abstract	In task-oriented dialogue systems, spoken language understanding, or SLU, refers to the task of parsing natural language user utterances into semantic frames. Making use of context from prior dialogue history holds the key to more effective SLU. State of the art approaches to SLU use memory networks to encode context by processing multiple utterances from the dialogue at each turn, resulting in significant trade-offs between accuracy and computational efficiency. On the other hand, downstream components like the dialogue state tracker (DST) already keep track of the dialogue state, which can serve as a summary of the dialogue history. In this work, we propose an efficient approach to encoding context from prior utterances for SLU. More specifically, our architecture includes a separate recurrent neural network (RNN) based encoding module that accumulates dialogue context to guide the frame parsing sub-tasks and can be shared between SLU and DST. In our experiments, we demonstrate the effectiveness of our approach on dialogues from two domains.
Tasks	Spoken Language Understanding, Task-Oriented Dialogue Systems
Published	2018-07-01
URL	http://arxiv.org/abs/1807.00267v1
PDF	http://arxiv.org/pdf/1807.00267v1.pdf
PWC	https://paperswithcode.com/paper/an-efficient-approach-to-encoding-context-for
Repo
Framework