Paper Group ANR 405
Data Filtering for Cluster Analysis by $\ell_0$-Norm Regularization. Multi-Source Neural Translation. Online Learning Schemes for Power Allocation in Energy Harvesting Communications. A Factorized Model for Transitive Verbs in Compositional Distributional Semantics. Unimodal Thompson Sampling for Graph-Structured Arms. Depth-Width Tradeoffs in Appr …
Data Filtering for Cluster Analysis by $\ell_0$-Norm Regularization
| Title | Data Filtering for Cluster Analysis by $\ell_0$-Norm Regularization |
| Authors | Andrea Cristofari |
| Abstract | A data filtering method for cluster analysis is proposed, based on minimizing a least squares function with a weighted $\ell_0$-norm penalty. To overcome the discontinuity of the objective function, smooth non-convex functions are employed to approximate the $\ell_0$-norm. The convergence of the global minimum points of the approximating problems towards global minimum points of the original problem is stated. The proposed method also exploits a suitable technique to choose the penalty parameter. Numerical results on synthetic and real data sets are finally provided, showing how some existing clustering methods can take advantages from the proposed filtering strategy. |
| Tasks | |
| Published | 2016-07-29 |
| URL | http://arxiv.org/abs/1607.08756v3 |
| http://arxiv.org/pdf/1607.08756v3.pdf | |
| PWC | https://paperswithcode.com/paper/data-filtering-for-cluster-analysis-by-ell_0 |
| Repo | |
| Framework | |
Multi-Source Neural Translation
| Title | Multi-Source Neural Translation |
| Authors | Barret Zoph, Kevin Knight |
| Abstract | We build a multi-source machine translation model and train it to maximize the probability of a target English string given French and German sources. Using the neural encoder-decoder framework, we explore several combination methods and report up to +4.8 Bleu increases on top of a very strong attention-based neural translation model. |
| Tasks | Machine Translation |
| Published | 2016-01-05 |
| URL | http://arxiv.org/abs/1601.00710v1 |
| http://arxiv.org/pdf/1601.00710v1.pdf | |
| PWC | https://paperswithcode.com/paper/multi-source-neural-translation |
| Repo | |
| Framework | |
Online Learning Schemes for Power Allocation in Energy Harvesting Communications
| Title | Online Learning Schemes for Power Allocation in Energy Harvesting Communications |
| Authors | Pranav Sakulkar, Bhaskar Krishnamachari |
| Abstract | We consider the problem of power allocation over a time-varying channel with unknown distribution in energy harvesting communication systems. In this problem, the transmitter has to choose the transmit power based on the amount of stored energy in its battery with the goal of maximizing the average rate obtained over time. We model this problem as a Markov decision process (MDP) with the transmitter as the agent, the battery status as the state, the transmit power as the action and the rate obtained as the reward. The average reward maximization problem over the MDP can be solved by a linear program (LP) that uses the transition probabilities for the state-action pairs and their reward values to choose a power allocation policy. Since the rewards associated the state-action pairs are unknown, we propose two online learning algorithms: UCLP and Epoch-UCLP that learn these rewards and adapt their policies along the way. The UCLP algorithm solves the LP at each step to decide its current policy using the upper confidence bounds on the rewards, while the Epoch-UCLP algorithm divides the time into epochs, solves the LP only at the beginning of the epochs and follows the obtained policy in that epoch. We prove that the reward losses or regrets incurred by both these algorithms are upper bounded by constants. Epoch-UCLP incurs a higher regret compared to UCLP, but reduces the computational requirements substantially. We also show that the presented algorithms work for online learning in cost minimization problems like the packet scheduling with power-delay tradeoff with minor changes. |
| Tasks | |
| Published | 2016-07-08 |
| URL | http://arxiv.org/abs/1607.02552v2 |
| http://arxiv.org/pdf/1607.02552v2.pdf | |
| PWC | https://paperswithcode.com/paper/online-learning-schemes-for-power-allocation |
| Repo | |
| Framework | |
A Factorized Model for Transitive Verbs in Compositional Distributional Semantics
| Title | A Factorized Model for Transitive Verbs in Compositional Distributional Semantics |
| Authors | Lilach Edelstein, Roi Reichart |
| Abstract | We present a factorized compositional distributional semantics model for the representation of transitive verb constructions. Our model first produces (subject, verb) and (verb, object) vector representations based on the similarity of the nouns in the construction to each of the nouns in the vocabulary and the tendency of these nouns to take the subject and object roles of the verb. These vectors are then combined into a final (subject,verb,object) representation through simple vector operations. On two established tasks for the transitive verb construction our model outperforms recent previous work. |
| Tasks | |
| Published | 2016-09-25 |
| URL | http://arxiv.org/abs/1609.07756v1 |
| http://arxiv.org/pdf/1609.07756v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-factorized-model-for-transitive-verbs-in |
| Repo | |
| Framework | |
Unimodal Thompson Sampling for Graph-Structured Arms
| Title | Unimodal Thompson Sampling for Graph-Structured Arms |
| Authors | Stefano Paladino, Francesco Trovò, Marcello Restelli, Nicola Gatti |
| Abstract | We study, to the best of our knowledge, the first Bayesian algorithm for unimodal Multi-Armed Bandit (MAB) problems with graph structure. In this setting, each arm corresponds to a node of a graph and each edge provides a relationship, unknown to the learner, between two nodes in terms of expected reward. Furthermore, for any node of the graph there is a path leading to the unique node providing the maximum expected reward, along which the expected reward is monotonically increasing. Previous results on this setting describe the behavior of frequentist MAB algorithms. In our paper, we design a Thompson Sampling-based algorithm whose asymptotic pseudo-regret matches the lower bound for the considered setting. We show that -as it happens in a wide number of scenarios- Bayesian MAB algorithms dramatically outperform frequentist ones. In particular, we provide a thorough experimental evaluation of the performance of our and state-of-the-art algorithms as the properties of the graph vary. |
| Tasks | |
| Published | 2016-11-17 |
| URL | http://arxiv.org/abs/1611.05724v2 |
| http://arxiv.org/pdf/1611.05724v2.pdf | |
| PWC | https://paperswithcode.com/paper/unimodal-thompson-sampling-for-graph |
| Repo | |
| Framework | |
Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
| Title | Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks |
| Authors | Itay Safran, Ohad Shamir |
| Abstract | We provide several new depth-based separation results for feed-forward neural networks, proving that various types of simple and natural functions can be better approximated using deeper networks than shallower ones, even if the shallower networks are much larger. This includes indicators of balls and ellipses; non-linear functions which are radial with respect to the $L_1$ norm; and smooth non-linear functions. We also show that these gaps can be observed experimentally: Increasing the depth indeed allows better learning than increasing width, when training neural networks to learn an indicator of a unit ball. |
| Tasks | |
| Published | 2016-10-31 |
| URL | http://arxiv.org/abs/1610.09887v2 |
| http://arxiv.org/pdf/1610.09887v2.pdf | |
| PWC | https://paperswithcode.com/paper/depth-width-tradeoffs-in-approximating |
| Repo | |
| Framework | |
Fully Convolutional Networks for Dense Semantic Labelling of High-Resolution Aerial Imagery
| Title | Fully Convolutional Networks for Dense Semantic Labelling of High-Resolution Aerial Imagery |
| Authors | Jamie Sherrah |
| Abstract | The trend towards higher resolution remote sensing imagery facilitates a transition from land-use classification to object-level scene understanding. Rather than relying purely on spectral content, appearance-based image features come into play. In this work, deep convolutional neural networks (CNNs) are applied to semantic labelling of high-resolution remote sensing data. Recent advances in fully convolutional networks (FCNs) are adapted to overhead data and shown to be as effective as in other domains. A full-resolution labelling is inferred using a deep FCN with no downsampling, obviating the need for deconvolution or interpolation. To make better use of image features, a pre-trained CNN is fine-tuned on remote sensing data in a hybrid network context, resulting in superior results compared to a network trained from scratch. The proposed approach is applied to the problem of labelling high-resolution aerial imagery, where fine boundary detail is important. The dense labelling yields state-of-the-art accuracy for the ISPRS Vaihingen and Potsdam benchmark data sets. |
| Tasks | Scene Understanding |
| Published | 2016-06-08 |
| URL | http://arxiv.org/abs/1606.02585v1 |
| http://arxiv.org/pdf/1606.02585v1.pdf | |
| PWC | https://paperswithcode.com/paper/fully-convolutional-networks-for-dense |
| Repo | |
| Framework | |
Robust Fusion of Multi-Band Images with Different Spatial and Spectral Resolutions for Change Detection
| Title | Robust Fusion of Multi-Band Images with Different Spatial and Spectral Resolutions for Change Detection |
| Authors | Vinicius Ferraris, Nicolas Dobigeon, Qi Wei, Marie Chabert |
| Abstract | Archetypal scenarios for change detection generally consider two images acquired through sensors of the same modality. However, in some specific cases such as emergency situations, the only images available may be those acquired through different kinds of sensors. More precisely, this paper addresses the problem of detecting changes between two multi-band optical images characterized by different spatial and spectral resolutions. This sensor dissimilarity introduces additional issues in the context of operational change detection. To alleviate these issues, classical change detection methods are applied after independent preprocessing steps (e.g., resampling) used to get the same spatial and spectral resolutions for the pair of observed images. Nevertheless, these preprocessing steps tend to throw away relevant information. Conversely, in this paper, we propose a method that more effectively uses the available information by modeling the two observed images as spatial and spectral versions of two (unobserved) latent images characterized by the same high spatial and high spectral resolutions. As they cover the same scene, these latent images are expected to be globally similar except for possible changes in sparse spatial locations. Thus, the change detection task is envisioned through a robust multi-band image fusion method which enforces the differences between the estimated latent images to be spatially sparse. This robust fusion problem is formulated as an inverse problem which is iteratively solved using an efficient block-coordinate descent algorithm. The proposed method is applied to real panchormatic/multispectral and hyperspectral images with simulated realistic changes. A comparison with state-of-the-art change detection methods evidences the accuracy of the proposed strategy. |
| Tasks | |
| Published | 2016-09-20 |
| URL | http://arxiv.org/abs/1609.06076v1 |
| http://arxiv.org/pdf/1609.06076v1.pdf | |
| PWC | https://paperswithcode.com/paper/robust-fusion-of-multi-band-images-with |
| Repo | |
| Framework | |
A Corpus and Evaluation Framework for Deeper Understanding of Commonsense Stories
| Title | A Corpus and Evaluation Framework for Deeper Understanding of Commonsense Stories |
| Authors | Nasrin Mostafazadeh, Nathanael Chambers, Xiaodong He, Devi Parikh, Dhruv Batra, Lucy Vanderwende, Pushmeet Kohli, James Allen |
| Abstract | Representation and learning of commonsense knowledge is one of the foundational problems in the quest to enable deep language understanding. This issue is particularly challenging for understanding casual and correlational relationships between events. While this topic has received a lot of interest in the NLP community, research has been hindered by the lack of a proper evaluation framework. This paper attempts to address this problem with a new framework for evaluating story understanding and script learning: the ‘Story Cloze Test’. This test requires a system to choose the correct ending to a four-sentence story. We created a new corpus of ~50k five-sentence commonsense stories, ROCStories, to enable this evaluation. This corpus is unique in two ways: (1) it captures a rich set of causal and temporal commonsense relations between daily events, and (2) it is a high quality collection of everyday life stories that can also be used for story generation. Experimental evaluation shows that a host of baselines and state-of-the-art models based on shallow language understanding struggle to achieve a high score on the Story Cloze Test. We discuss these implications for script and story learning, and offer suggestions for deeper language understanding. |
| Tasks | |
| Published | 2016-04-06 |
| URL | http://arxiv.org/abs/1604.01696v1 |
| http://arxiv.org/pdf/1604.01696v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-corpus-and-evaluation-framework-for-deeper |
| Repo | |
| Framework | |
Robust Local Scaling using Conditional Quantiles of Graph Similarities
| Title | Robust Local Scaling using Conditional Quantiles of Graph Similarities |
| Authors | Jayaraman J. Thiagarajan, Prasanna Sattigeri, Karthikeyan Natesan Ramamurthy, Bhavya Kailkhura |
| Abstract | Spectral analysis of neighborhood graphs is one of the most widely used techniques for exploratory data analysis, with applications ranging from machine learning to social sciences. In such applications, it is typical to first encode relationships between the data samples using an appropriate similarity function. Popular neighborhood construction techniques such as k-nearest neighbor (k-NN) graphs are known to be very sensitive to the choice of parameters, and more importantly susceptible to noise and varying densities. In this paper, we propose the use of quantile analysis to obtain local scale estimates for neighborhood graph construction. To this end, we build an auto-encoding neural network approach for inferring conditional quantiles of a similarity function, which are subsequently used to obtain robust estimates of the local scales. In addition to being highly resilient to noise or outlying data, the proposed approach does not require extensive parameter tuning unlike several existing methods. Using applications in spectral clustering and single-example label propagation, we show that the proposed neighborhood graphs outperform existing locally scaled graph construction approaches. |
| Tasks | graph construction |
| Published | 2016-12-14 |
| URL | http://arxiv.org/abs/1612.04875v1 |
| http://arxiv.org/pdf/1612.04875v1.pdf | |
| PWC | https://paperswithcode.com/paper/robust-local-scaling-using-conditional |
| Repo | |
| Framework | |
Testing Bayesian Networks
| Title | Testing Bayesian Networks |
| Authors | Clement Canonne, Ilias Diakonikolas, Daniel Kane, Alistair Stewart |
| Abstract | This work initiates a systematic investigation of testing high-dimensional structured distributions by focusing on testing Bayesian networks – the prototypical family of directed graphical models. A Bayesian network is defined by a directed acyclic graph, where we associate a random variable with each node. The value at any particular node is conditionally independent of all the other non-descendant nodes once its parents are fixed. Specifically, we study the properties of identity testing and closeness testing of Bayesian networks. Our main contribution is the first non-trivial efficient testing algorithms for these problems and corresponding information-theoretic lower bounds. For a wide range of parameter settings, our testing algorithms have sample complexity sublinear in the dimension and are sample-optimal, up to constant factors. |
| Tasks | |
| Published | 2016-12-09 |
| URL | https://arxiv.org/abs/1612.03156v2 |
| https://arxiv.org/pdf/1612.03156v2.pdf | |
| PWC | https://paperswithcode.com/paper/testing-bayesian-networks |
| Repo | |
| Framework | |
3D Object Proposals using Stereo Imagery for Accurate Object Class Detection
| Title | 3D Object Proposals using Stereo Imagery for Accurate Object Class Detection |
| Authors | Xiaozhi Chen, Kaustav Kundu, Yukun Zhu, Huimin Ma, Sanja Fidler, Raquel Urtasun |
| Abstract | The goal of this paper is to perform 3D object detection in the context of autonomous driving. Our method first aims at generating a set of high-quality 3D object proposals by exploiting stereo imagery. We formulate the problem as minimizing an energy function that encodes object size priors, placement of objects on the ground plane as well as several depth informed features that reason about free space, point cloud densities and distance to the ground. We then exploit a CNN on top of these proposals to perform object detection. In particular, we employ a convolutional neural net (CNN) that exploits context and depth information to jointly regress to 3D bounding box coordinates and object pose. Our experiments show significant performance gains over existing RGB and RGB-D object proposal methods on the challenging KITTI benchmark. When combined with the CNN, our approach outperforms all existing results in object detection and orientation estimation tasks for all three KITTI object classes. Furthermore, we experiment also with the setting where LIDAR information is available, and show that using both LIDAR and stereo leads to the best result. |
| Tasks | 3D Object Detection, Autonomous Driving, Object Detection |
| Published | 2016-08-27 |
| URL | http://arxiv.org/abs/1608.07711v2 |
| http://arxiv.org/pdf/1608.07711v2.pdf | |
| PWC | https://paperswithcode.com/paper/3d-object-proposals-using-stereo-imagery-for |
| Repo | |
| Framework | |
Simple Bayesian Algorithms for Best Arm Identification
| Title | Simple Bayesian Algorithms for Best Arm Identification |
| Authors | Daniel Russo |
| Abstract | This paper considers the optimal adaptive allocation of measurement effort for identifying the best among a finite set of options or designs. An experimenter sequentially chooses designs to measure and observes noisy signals of their quality with the goal of confidently identifying the best design after a small number of measurements. This paper proposes three simple and intuitive Bayesian algorithms for adaptively allocating measurement effort, and formalizes a sense in which these seemingly naive rules are the best possible. One proposal is top-two probability sampling, which computes the two designs with the highest posterior probability of being optimal, and then randomizes to select among these two. One is a variant of top-two sampling which considers not only the probability a design is optimal, but the expected amount by which its quality exceeds that of other designs. The final algorithm is a modified version of Thompson sampling that is tailored for identifying the best design. We prove that these simple algorithms satisfy a sharp optimality property. In a frequentist setting where the true quality of the designs is fixed, one hopes the posterior definitively identifies the optimal design, in the sense that that the posterior probability assigned to the event that some other design is optimal converges to zero as measurements are collected. We show that under the proposed algorithms this convergence occurs at an exponential rate, and the corresponding exponent is the best possible among all allocation |
| Tasks | |
| Published | 2016-02-26 |
| URL | http://arxiv.org/abs/1602.08448v4 |
| http://arxiv.org/pdf/1602.08448v4.pdf | |
| PWC | https://paperswithcode.com/paper/simple-bayesian-algorithms-for-best-arm |
| Repo | |
| Framework | |
A High Speed Multi-label Classifier based on Extreme Learning Machines
| Title | A High Speed Multi-label Classifier based on Extreme Learning Machines |
| Authors | Meng Joo Er, Rajasekar Venkatesan, Ning Wang |
| Abstract | In this paper a high speed neural network classifier based on extreme learning machines for multi-label classification problem is proposed and dis-cussed. Multi-label classification is a superset of traditional binary and multi-class classification problems. The proposed work extends the extreme learning machine technique to adapt to the multi-label problems. As opposed to the single-label problem, both the number of labels the sample belongs to, and each of those target labels are to be identified for multi-label classification resulting in in-creased complexity. The proposed high speed multi-label classifier is applied to six benchmark datasets comprising of different application areas such as multi-media, text and biology. The training time and testing time of the classifier are compared with those of the state-of-the-arts methods. Experimental studies show that for all the six datasets, our proposed technique have faster execution speed and better performance, thereby outperforming all the existing multi-label clas-sification methods. |
| Tasks | Multi-Label Classification |
| Published | 2016-08-31 |
| URL | http://arxiv.org/abs/1608.08898v1 |
| http://arxiv.org/pdf/1608.08898v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-high-speed-multi-label-classifier-based-on |
| Repo | |
| Framework | |
Consistency and Trust in Peer Data Exchange Systems
| Title | Consistency and Trust in Peer Data Exchange Systems |
| Authors | Leopoldo Bertossi, Loreto Bravo |
| Abstract | We propose and investigate a semantics for “peer data exchange systems” where different peers are related by data exchange constraints and trust relationships. These two elements plus the data at the peers’ sites and their local integrity constraints are made compatible via a semantics that characterizes sets of “solution instances” for the peers. They are the intended -possibly virtual- instances for a peer that are obtained through a data repair semantics that we introduce and investigate. The semantically correct answers from a peer to a query, the so-called “peer consistent answers”, are defined as those answers that are invariant under all its different solution instances. We show that solution instances can be specified as the models of logic programs with a stable model semantics. The repair semantics is based on null values as used in SQL databases, and is also of independent interest for repairs of single databases with respect to integrity constraints. |
| Tasks | |
| Published | 2016-06-06 |
| URL | http://arxiv.org/abs/1606.01930v1 |
| http://arxiv.org/pdf/1606.01930v1.pdf | |
| PWC | https://paperswithcode.com/paper/consistency-and-trust-in-peer-data-exchange |
| Repo | |
| Framework | |
