July 28, 2019

3065 words 15 mins read

Paper Group ANR 248

Multi-Level Discovery of Deep Options. LightNN: Filling the Gap between Conventional Deep Neural Networks and Binarized Networks. Making up for the deficit in a marathon run. Language Design as Information Renormalization. Unsupervised temporal context learning using convolutional neural networks for laparoscopic workflow analysis. Testing Piecewis …

Multi-Level Discovery of Deep Options


Title	Multi-Level Discovery of Deep Options
Authors	Roy Fox, Sanjay Krishnan, Ion Stoica, Ken Goldberg
Abstract	Augmenting an agent’s control with useful higher-level behaviors called options can greatly reduce the sample complexity of reinforcement learning, but manually designing options is infeasible in high-dimensional and abstract state spaces. While recent work has proposed several techniques for automated option discovery, they do not scale to multi-level hierarchies and to expressive representations such as deep networks. We present Discovery of Deep Options (DDO), a policy-gradient algorithm that discovers parametrized options from a set of demonstration trajectories, and can be used recursively to discover additional levels of the hierarchy. The scalability of our approach to multi-level hierarchies stems from the decoupling of low-level option discovery from high-level meta-control policy learning, facilitated by under-parametrization of the high level. We demonstrate that using the discovered options to augment the action space of Deep Q-Network agents can accelerate learning by guiding exploration in tasks where random actions are unlikely to reach valuable states. We show that DDO is effective in adding options that accelerate learning in 4 out of 5 Atari RAM environments chosen in our experiments. We also show that DDO can discover structure in robot-assisted surgical videos and kinematics that match expert annotation with 72% accuracy.
Tasks
Published	2017-03-24
URL	http://arxiv.org/abs/1703.08294v2
PDF	http://arxiv.org/pdf/1703.08294v2.pdf
PWC	https://paperswithcode.com/paper/multi-level-discovery-of-deep-options
Repo
Framework

LightNN: Filling the Gap between Conventional Deep Neural Networks and Binarized Networks


Title	LightNN: Filling the Gap between Conventional Deep Neural Networks and Binarized Networks
Authors	Ruizhou Ding, Zeye Liu, Rongye Shi, Diana Marculescu, R. D. Blanton
Abstract	Application-specific integrated circuit (ASIC) implementations for Deep Neural Networks (DNNs) have been adopted in many systems because of their higher classification speed. However, although they may be characterized by better accuracy, larger DNNs require significant energy and area, thereby limiting their wide adoption. The energy consumption of DNNs is driven by both memory accesses and computation. Binarized Neural Networks (BNNs), as a trade-off between accuracy and energy consumption, can achieve great energy reduction, and have good accuracy for large DNNs due to its regularization effect. However, BNNs show poor accuracy when a smaller DNN configuration is adopted. In this paper, we propose a new DNN model, LightNN, which replaces the multiplications to one shift or a constrained number of shifts and adds. For a fixed DNN configuration, LightNNs have better accuracy at a slight energy increase than BNNs, yet are more energy efficient with only slightly less accuracy than conventional DNNs. Therefore, LightNNs provide more options for hardware designers to make trade-offs between accuracy and energy. Moreover, for large DNN configurations, LightNNs have a regularization effect, making them better in accuracy than conventional DNNs. These conclusions are verified by experiment using the MNIST and CIFAR-10 datasets for different DNN configurations.
Tasks
Published	2017-12-02
URL	http://arxiv.org/abs/1802.02178v1
PDF	http://arxiv.org/pdf/1802.02178v1.pdf
PWC	https://paperswithcode.com/paper/lightnn-filling-the-gap-between-conventional
Repo
Framework

Making up for the deficit in a marathon run


Title	Making up for the deficit in a marathon run
Authors	Iztok Fister Jr., Dušan Fister, Suash Deb, Uroš Mlakar, Janez Brest, Iztok Fister
Abstract	To predict the final result of an athlete in a marathon run thoroughly is the eternal desire of each trainer. Usually, the achieved result is weaker than the predicted one due to the objective (e.g., environmental conditions) as well as subjective factors (e.g., athlete’s malaise). Therefore, making up for the deficit between predicted and achieved results is the main ingredient of the analysis performed by trainers after the competition. In the analysis, they search for parts of a marathon course where the athlete lost time. This paper proposes an automatic making up for the deficit by using a Differential Evolution algorithm. In this case study, the results that were obtained by a wearable sports-watch by an athlete in a real marathon are analyzed. The first experiments with Differential Evolution show the possibility of using this method in the future.
Tasks
Published	2017-05-09
URL	http://arxiv.org/abs/1705.03302v1
PDF	http://arxiv.org/pdf/1705.03302v1.pdf
PWC	https://paperswithcode.com/paper/making-up-for-the-deficit-in-a-marathon-run
Repo
Framework

Language Design as Information Renormalization


Title	Language Design as Information Renormalization
Authors	Angel J. Gallego, Roman Orus
Abstract	Here we consider some well-known facts in syntax from a physics perspective, allowing us to establish equivalences between both fields with many consequences. Mainly, we observe that the operation MERGE, put forward by N. Chomsky in 1995, can be interpreted as a physical information coarse-graining. Thus, MERGE in linguistics entails information renormalization in physics, according to different time scales. We make this point mathematically formal in terms of language models. In this setting, MERGE amounts to a probability tensor implementing a coarse-graining, akin to a probabilistic context-free grammar. The probability vectors of meaningful sentences are given by stochastic tensor networks (TN) built from diagonal tensors and which are mostly loop-free, such as Tree Tensor Networks and Matrix Product States, thus being computationally very efficient to manipulate. We show that this implies the polynomially-decaying (long-range) correlations experimentally observed in language, and also provides arguments in favour of certain types of neural networks for language processing. Moreover, we show how to obtain such language models from quantum states that can be efficiently prepared on a quantum computer, and use this to find bounds on the perplexity of the probability distribution of words in a sentence. Implications of our results are discussed across several ambits.
Tasks	Tensor Networks
Published	2017-08-04
URL	http://arxiv.org/abs/1708.01525v4
PDF	http://arxiv.org/pdf/1708.01525v4.pdf
PWC	https://paperswithcode.com/paper/language-design-and-renormalization
Repo
Framework

Unsupervised temporal context learning using convolutional neural networks for laparoscopic workflow analysis


Title	Unsupervised temporal context learning using convolutional neural networks for laparoscopic workflow analysis
Authors	Sebastian Bodenstedt, Martin Wagner, Darko Katić, Patrick Mietkowski, Benjamin Mayer, Hannes Kenngott, Beat Müller-Stich, Rüdiger Dillmann, Stefanie Speidel
Abstract	Computer-assisted surgery (CAS) aims to provide the surgeon with the right type of assistance at the right moment. Such assistance systems are especially relevant in laparoscopic surgery, where CAS can alleviate some of the drawbacks that surgeons incur. For many assistance functions, e.g. displaying the location of a tumor at the appropriate time or suggesting what instruments to prepare next, analyzing the surgical workflow is a prerequisite. Since laparoscopic interventions are performed via endoscope, the video signal is an obvious sensor modality to rely on for workflow analysis. Image-based workflow analysis tasks in laparoscopy, such as phase recognition, skill assessment, video indexing or automatic annotation, require a temporal distinction between video frames. Generally computer vision based methods that generalize from previously seen data are used. For training such methods, large amounts of annotated data are necessary. Annotating surgical data requires expert knowledge, therefore collecting a sufficient amount of data is difficult, time-consuming and not always feasible. In this paper, we address this problem by presenting an unsupervised method for training a convolutional neural network (CNN) to differentiate between laparoscopic video frames on a temporal basis. We extract video frames at regular intervals from 324 unlabeled laparoscopic interventions, resulting in a dataset of approximately 2.2 million images. From this dataset, we extract image pairs from the same video and train a CNN to determine their temporal order. To solve this problem, the CNN has to extract features that are relevant for comprehending laparoscopic workflow. Furthermore, we demonstrate that such a CNN can be adapted for surgical workflow segmentation. We performed image-based workflow segmentation on a publicly available dataset of 7 cholecystectomies and 9 colorectal interventions.
Tasks
Published	2017-02-13
URL	http://arxiv.org/abs/1702.03684v1
PDF	http://arxiv.org/pdf/1702.03684v1.pdf
PWC	https://paperswithcode.com/paper/unsupervised-temporal-context-learning-using
Repo
Framework

Testing Piecewise Functions


Title	Testing Piecewise Functions
Authors	Steve Hanneke, Liu Yang
Abstract	This work explores the query complexity of property testing for general piecewise functions on the real line, in the active and passive property testing settings. The results are proven under an abstract zero-measure crossings condition, which has as special cases piecewise constant functions and piecewise polynomial functions. We find that, in the active testing setting, the query complexity of testing general piecewise functions is independent of the number of pieces. We also identify the optimal dependence on the number of pieces in the query complexity of passive testing in the special case of piecewise constant functions.
Tasks
Published	2017-06-23
URL	http://arxiv.org/abs/1706.07669v2
PDF	http://arxiv.org/pdf/1706.07669v2.pdf
PWC	https://paperswithcode.com/paper/testing-piecewise-functions
Repo
Framework

Restoration of Pansharpened Images by Conditional Filtering in the PCA Domain


Title	Restoration of Pansharpened Images by Conditional Filtering in the PCA Domain
Authors	Joan Duran, Antoni Buades
Abstract	Pansharpening techniques aim at fusing low-resolution multispectral (MS) images and high-resolution panchromatic (PAN) images to produce high-resolution MS images. Despite significant progress in the field, spectral and spatial distortions might still compromise the quality of the results. We introduce a restoration strategy to mitigate artifacts of fused products. After applying the Principal Component Analysis (PCA) transform to a pansharpened image, the chromatic components are filtered conditionally to the geometry of PAN. The structural component is then replaced by the locally histogram-matched PAN for spatial enhancement. Experimental results illustrate the efficiency of the proposed restoration chain.
Tasks
Published	2017-10-02
URL	http://arxiv.org/abs/1710.00672v3
PDF	http://arxiv.org/pdf/1710.00672v3.pdf
PWC	https://paperswithcode.com/paper/restoration-of-pansharpened-images-by
Repo
Framework

Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection


Title	Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
Authors	Lijie Chen, Jian Li, Mingda Qiao
Abstract	In the Best-$k$-Arm problem, we are given $n$ stochastic bandit arms, each associated with an unknown reward distribution. We are required to identify the $k$ arms with the largest means by taking as few samples as possible. In this paper, we make progress towards a complete characterization of the instance-wise sample complexity bounds for the Best-$k$-Arm problem. On the lower bound side, we obtain a novel complexity term to measure the sample complexity that every Best-$k$-Arm instance requires. This is derived by an interesting and nontrivial reduction from the Best-$1$-Arm problem. We also provide an elimination-based algorithm that matches the instance-wise lower bound within doubly-logarithmic factors. The sample complexity of our algorithm strictly dominates the state-of-the-art for Best-$k$-Arm (module constant factors).
Tasks
Published	2017-02-13
URL	http://arxiv.org/abs/1702.03605v1
PDF	http://arxiv.org/pdf/1702.03605v1.pdf
PWC	https://paperswithcode.com/paper/nearly-instance-optimal-sample-complexity
Repo
Framework

Which Distribution Distances are Sublinearly Testable?


Title	Which Distribution Distances are Sublinearly Testable?
Authors	Constantinos Daskalakis, Gautam Kamath, John Wright
Abstract	Given samples from an unknown distribution $p$ and a description of a distribution $q$, are $p$ and $q$ close or far? This question of “identity testing” has received significant attention in the case of testing whether $p$ and $q$ are equal or far in total variation distance. However, in recent work, the following questions have been been critical to solving problems at the frontiers of distribution testing: -Alternative Distances: Can we test whether $p$ and $q$ are far in other distances, say Hellinger? -Tolerance: Can we test when $p$ and $q$ are close, rather than equal? And if so, close in which distances? Motivated by these questions, we characterize the complexity of distribution testing under a variety of distances, including total variation, $\ell_2$, Hellinger, Kullback-Leibler, and $\chi^2$. For each pair of distances $d_1$ and $d_2$, we study the complexity of testing if $p$ and $q$ are close in $d_1$ versus far in $d_2$, with a focus on identifying which problems allow strongly sublinear testers (i.e., those with complexity $O(n^{1 - \gamma})$ for some $\gamma > 0$ where $n$ is the size of the support of the distributions $p$ and $q$). We provide matching upper and lower bounds for each case. We also study these questions in the case where we only have samples from $q$ (equivalence testing), showing qualitative differences from identity testing in terms of when tolerance can be achieved. Our algorithms fall into the classical paradigm of $\chi^2$-statistics, but require crucial changes to handle the challenges introduced by each distance we consider. Finally, we survey other recent results in an attempt to serve as a reference for the complexity of various distribution testing problems.
Tasks
Published	2017-07-31
URL	http://arxiv.org/abs/1708.00002v2
PDF	http://arxiv.org/pdf/1708.00002v2.pdf
PWC	https://paperswithcode.com/paper/which-distribution-distances-are-sublinearly
Repo
Framework

Multimodal deep learning approach for joint EEG-EMG data compression and classification


Title	Multimodal deep learning approach for joint EEG-EMG data compression and classification
Authors	Ahmed Ben Said, Amr Mohamed, Tarek Elfouly, Khaled Harras, Z. Jane Wang
Abstract	In this paper, we present a joint compression and classification approach of EEG and EMG signals using a deep learning approach. Specifically, we build our system based on the deep autoencoder architecture which is designed not only to extract discriminant features in the multimodal data representation but also to reconstruct the data from the latent representation using encoder-decoder layers. Since autoencoder can be seen as a compression approach, we extend it to handle multimodal data at the encoder layer, reconstructed and retrieved at the decoder layer. We show through experimental results, that exploiting both multimodal data intercorellation and intracorellation 1) Significantly reduces signal distortion particularly for high compression levels 2) Achieves better accuracy in classifying EEG and EMG signals recorded and labeled according to the sentiments of the volunteer.
Tasks	EEG
Published	2017-03-27
URL	http://arxiv.org/abs/1703.08970v1
PDF	http://arxiv.org/pdf/1703.08970v1.pdf
PWC	https://paperswithcode.com/paper/multimodal-deep-learning-approach-for-joint
Repo
Framework

Segmenting Brain Tumors with Symmetry


Title	Segmenting Brain Tumors with Symmetry
Authors	Hejia Zhang, Xia Zhu, Theodore L. Willke
Abstract	We explore encoding brain symmetry into a neural network for a brain tumor segmentation task. A healthy human brain is symmetric at a high level of abstraction, and the high-level asymmetric parts are more likely to be tumor regions. Paying more attention to asymmetries has the potential to boost the performance in brain tumor segmentation. We propose a method to encode brain symmetry into existing neural networks and apply the method to a state-of-the-art neural network for medical imaging segmentation. We evaluate our symmetry-encoded network on the dataset from a brain tumor segmentation challenge and verify that the new model extracts information in the training images more efficiently than the original model.
Tasks	Brain Tumor Segmentation, Medical Image Segmentation
Published	2017-11-17
URL	http://arxiv.org/abs/1711.06636v1
PDF	http://arxiv.org/pdf/1711.06636v1.pdf
PWC	https://paperswithcode.com/paper/segmenting-brain-tumors-with-symmetry
Repo
Framework

An Effective Approach for Point Clouds Registration Based on the Hard and Soft Assignments


Title	An Effective Approach for Point Clouds Registration Based on the Hard and Soft Assignments
Authors	Congcong Jin, Jihua Zhu, Yaochen Li, Shaoyi Du, Zhongyu Li, Huimin Lu
Abstract	For the registration of partially overlapping point clouds, this paper proposes an effective approach based on both the hard and soft assignments. Given two initially posed clouds, it firstly establishes the forward correspondence for each point in the data shape and calculates the value of binary variable, which can indicate whether this point correspondence is located in the overlapping areas or not. Then, it establishes the bilateral correspondence and computes bidirectional distances for each point in the overlapping areas. Based on the ratio of bidirectional distances, the exponential function is selected and utilized to calculate the probability value, which can indicate the reliability of the point correspondence. Subsequently, both the values of hard and soft assignments are embedded into the proposed objective function for registration of partially overlapping point clouds and a novel variant of ICP algorithm is proposed to obtain the optimal rigid transformation. The proposed approach can achieve good registration of point clouds, even when their overlap percentage is low. Experimental results tested on public data sets illustrate its superiority over previous approaches on accuracy and robustness.
Tasks
Published	2017-06-01
URL	http://arxiv.org/abs/1706.00227v1
PDF	http://arxiv.org/pdf/1706.00227v1.pdf
PWC	https://paperswithcode.com/paper/an-effective-approach-for-point-clouds
Repo
Framework

Deep Learning applied to Road Traffic Speed forecasting


Title	Deep Learning applied to Road Traffic Speed forecasting
Authors	Thomas Epelbaum, Fabrice Gamboa, Jean-Michel Loubes, Jessica Martin
Abstract	In this paper, we propose deep learning architectures (FNN, CNN and LSTM) to forecast a regression model for time dependent data. These algorithm’s are designed to handle Floating Car Data (FCD) historic speeds to predict road traffic data. For this we aggregate the speeds into the network inputs in an innovative way. We compare the RMSE thus obtained with the results of a simpler physical model, and show that the latter achieves better RMSE accuracy. We also propose a new indicator, which evaluates the algorithms improvement when compared to a benchmark prediction. We conclude by questioning the interest of using deep learning methods for this specific regression task.
Tasks
Published	2017-10-02
URL	http://arxiv.org/abs/1710.08266v1
PDF	http://arxiv.org/pdf/1710.08266v1.pdf
PWC	https://paperswithcode.com/paper/deep-learning-applied-to-road-traffic-speed
Repo
Framework

From Community Detection to Community Profiling


Title	From Community Detection to Community Profiling
Authors	Hongyun Cai, Vincent W. Zheng, Fanwei Zhu, Kevin Chen-Chuan Chang, Zi Huang
Abstract	Most existing community-related studies focus on detection, which aim to find the community membership for each user from user friendship links. However, membership alone, without a complete profile of what a community is and how it interacts with other communities, has limited applications. This motivates us to consider systematically profiling the communities and thereby developing useful community-level applications. In this paper, we for the first time formalize the concept of community profiling. With rich user information on the network, such as user published content and user diffusion links, we characterize a community in terms of both its internal content profile and external diffusion profile. The difficulty of community profiling is often underestimated. We novelly identify three unique challenges and propose a joint Community Profiling and Detection (CPD) model to address them accordingly. We also contribute a scalable inference algorithm, which scales linearly with the data size and it is easily parallelizable. We evaluate CPD on large-scale real-world data sets, and show that it is significantly better than the state-of-the-art baselines in various tasks.
Tasks	Community Detection
Published	2017-01-17
URL	http://arxiv.org/abs/1701.04528v1
PDF	http://arxiv.org/pdf/1701.04528v1.pdf
PWC	https://paperswithcode.com/paper/from-community-detection-to-community
Repo
Framework

Global Convergence of the (1+1) Evolution Strategy


Title	Global Convergence of the (1+1) Evolution Strategy
Authors	Tobias Glasmachers
Abstract	We establish global convergence of the (1+1) evolution strategy, i.e., convergence to a critical point independent of the initial state. More precisely, we show the existence of a critical limit point, using a suitable extension of the notion of a critical point to measurable functions. At its core, the analysis is based on a novel progress guarantee for elitist, rank-based evolutionary algorithms. By applying it to the (1+1) evolution strategy we are able to provide an accurate characterization of whether global convergence is guaranteed with full probability, or whether premature convergence is possible. We illustrate our results on a number of example applications ranging from smooth (non-convex) cases over different types of saddle points and ridge functions to discontinuous and extremely rugged problems.
Tasks
Published	2017-06-09
URL	http://arxiv.org/abs/1706.02887v2
PDF	http://arxiv.org/pdf/1706.02887v2.pdf
PWC	https://paperswithcode.com/paper/global-convergence-of-the-11-evolution
Repo
Framework