January 30, 2020

3225 words 16 mins read

Paper Group ANR 440

Learning to Prune: Speeding up Repeated Computations. Time-sync Video Tag Extraction Using Semantic Association Graph. Hyper-Graph-Network Decoders for Block Codes. Interpretability Beyond Classification Output: Semantic Bottleneck Networks. Investigating Antigram Behaviour using Distributional Semantics. Carpe Diem, Seize the Samples Uncertain “At …

Learning to Prune: Speeding up Repeated Computations


Title	Learning to Prune: Speeding up Repeated Computations
Authors	Daniel Alabi, Adam Tauman Kalai, Katrina Ligett, Cameron Musco, Christos Tzamos, Ellen Vitercik
Abstract	It is common to encounter situations where one must solve a sequence of similar computational problems. Running a standard algorithm with worst-case runtime guarantees on each instance will fail to take advantage of valuable structure shared across the problem instances. For example, when a commuter drives from work to home, there are typically only a handful of routes that will ever be the shortest path. A naive algorithm that does not exploit this common structure may spend most of its time checking roads that will never be in the shortest path. More generally, we can often ignore large swaths of the search space that will likely never contain an optimal solution. We present an algorithm that learns to maximally prune the search space on repeated computations, thereby reducing runtime while provably outputting the correct solution each period with high probability. Our algorithm employs a simple explore-exploit technique resembling those used in online algorithms, though our setting is quite different. We prove that, with respect to our model of pruning search spaces, our approach is optimal up to constant factors. Finally, we illustrate the applicability of our model and algorithm to three classic problems: shortest-path routing, string search, and linear programming. We present experiments confirming that our simple algorithm is effective at significantly reducing the runtime of solving repeated computations.
Tasks
Published	2019-04-26
URL	http://arxiv.org/abs/1904.11875v1
PDF	http://arxiv.org/pdf/1904.11875v1.pdf
PWC	https://paperswithcode.com/paper/learning-to-prune-speeding-up-repeated
Repo
Framework

Time-sync Video Tag Extraction Using Semantic Association Graph


Title	Time-sync Video Tag Extraction Using Semantic Association Graph
Authors	Wenmian Yang, Kun Wang, Na Ruan, Wenyuan Gao, Weijia Jia, Wei Zhao, Nan Liu, Yunyong Zhang
Abstract	Time-sync comments reveal a new way of extracting the online video tags. However, such time-sync comments have lots of noises due to users’ diverse comments, introducing great challenges for accurate and fast video tag extractions. In this paper, we propose an unsupervised video tag extraction algorithm named Semantic Weight-Inverse Document Frequency (SW-IDF). Specifically, we first generate corresponding semantic association graph (SAG) using semantic similarities and timestamps of the time-sync comments. Second, we propose two graph cluster algorithms, i.e., dialogue-based algorithm and topic center-based algorithm, to deal with the videos with different density of comments. Third, we design a graph iteration algorithm to assign the weight to each comment based on the degrees of the clustered subgraphs, which can differentiate the meaningful comments from the noises. Finally, we gain the weight of each word by combining Semantic Weight (SW) and Inverse Document Frequency (IDF). In this way, the video tags are extracted automatically in an unsupervised way. Extensive experiments have shown that SW-IDF (dialogue-based algorithm) achieves 0.4210 F1-score and 0.4932 MAP (Mean Average Precision) in high-density comments, 0.4267 F1-score and 0.3623 MAP in low-density comments; while SW-IDF (topic center-based algorithm) achieves 0.4444 F1-score and 0.5122 MAP in high-density comments, 0.4207 F1-score and 0.3522 MAP in low-density comments. It has a better performance than the state-of-the-art unsupervised algorithms in both F1-score and MAP.
Tasks
Published	2019-05-03
URL	https://arxiv.org/abs/1905.01053v1
PDF	https://arxiv.org/pdf/1905.01053v1.pdf
PWC	https://paperswithcode.com/paper/time-sync-video-tag-extraction-using-semantic
Repo
Framework

Hyper-Graph-Network Decoders for Block Codes


Title	Hyper-Graph-Network Decoders for Block Codes
Authors	Eliya Nachmani, Lior Wolf
Abstract	Neural decoders were shown to outperform classical message passing techniques for short BCH codes. In this work, we extend these results to much larger families of algebraic block codes, by performing message passing with graph neural networks. The parameters of the sub-network at each variable-node in the Tanner graph are obtained from a hypernetwork that receives the absolute values of the current message as input. To add stability, we employ a simplified version of the arctanh activation that is based on a high order Taylor approximation of this activation function. Our results show that for a large number of algebraic block codes, from diverse families of codes (BCH, LDPC, Polar), the decoding obtained with our method outperforms the vanilla belief propagation method as well as other learning techniques from the literature.
Tasks
Published	2019-09-05
URL	https://arxiv.org/abs/1909.09036v2
PDF	https://arxiv.org/pdf/1909.09036v2.pdf
PWC	https://paperswithcode.com/paper/hyper-graph-network-decoders-for-block-codes
Repo
Framework

Interpretability Beyond Classification Output: Semantic Bottleneck Networks


Title	Interpretability Beyond Classification Output: Semantic Bottleneck Networks
Authors	Max Losch, Mario Fritz, Bernt Schiele
Abstract	Today’s deep learning systems deliver high performance based on end-to-end training. While they deliver strong performance, these systems are hard to interpret. To address this issue, we propose Semantic Bottleneck Networks (SBN): deep networks with semantically interpretable intermediate layers that all downstream results are based on. As a consequence, the analysis on what the final prediction is based on is transparent to the engineer and failure cases and modes can be analyzed and avoided by high-level reasoning. We present a case study on street scene segmentation to demonstrate the feasibility and power of SBN. In particular, we start from a well performing classic deep network which we adapt to house a SB-Layer containing task related semantic concepts (such as object-parts and materials). Importantly, we can recover state of the art performance despite a drastic dimensionality reduction from 1000s (non-semantic feature) to 10s (semantic concept) channels. Additionally we show how the activations of the SB-Layer can be used for both the interpretation of failure cases of the network as well as for confidence prediction of the resulting output. For the first time, e.g., we show interpretable segmentation results for most predictions at over 99% accuracy.
Tasks	Dimensionality Reduction, Scene Segmentation
Published	2019-07-25
URL	https://arxiv.org/abs/1907.10882v2
PDF	https://arxiv.org/pdf/1907.10882v2.pdf
PWC	https://paperswithcode.com/paper/interpretability-beyond-classification-output
Repo
Framework

Investigating Antigram Behaviour using Distributional Semantics


Title	Investigating Antigram Behaviour using Distributional Semantics
Authors	Saptarshi Sengupta
Abstract	Language is an extremely interesting subject to study, each day presenting new challenges and new topics for research. Words in particular have several unique characteristics which when explored, prove to be astonishing. Anagrams and Antigrams are such words possessing these amazing properties. The presented work is an exploration into generating anagrams from a given word and determining whether there exists antigram relationships between the pairs of generated anagrams in light of the Word2Vec distributional semantic similarity model. The experiments conducted, showed promising results for detecting antigrams.
Tasks	Semantic Similarity, Semantic Textual Similarity
Published	2019-01-15
URL	http://arxiv.org/abs/1901.05066v1
PDF	http://arxiv.org/pdf/1901.05066v1.pdf
PWC	https://paperswithcode.com/paper/investigating-antigram-behaviour-using
Repo
Framework

Carpe Diem, Seize the Samples Uncertain “At the Moment” for Adaptive Batch Selection


Title	Carpe Diem, Seize the Samples Uncertain “At the Moment” for Adaptive Batch Selection
Authors	Hwanjun Song, Minseok Kim, Sundong Kim, Jae-Gil Lee
Abstract	The performance of deep neural networks is significantly affected by how well mini-batches are constructed. In this paper, we propose a novel adaptive batch selection algorithm called Recency Bias that exploits the uncertain samples predicted inconsistently in recent iterations. The historical label predictions of each sample are used to evaluate its predictive uncertainty within a sliding window. By taking advantage of this design, Recency Bias not only accelerates the training step but also achieves a more accurate network. We demonstrate the superiority of Recency Bias by extensive evaluation on two independent tasks. Compared with existing batch selection methods, the results showed that Recency Bias reduced the test error by up to 20.5% in a fixed wall-clock training time. At the same time, it improved the training time by up to 59.3% to reach the same test error.
Tasks
Published	2019-11-19
URL	https://arxiv.org/abs/1911.08050v1
PDF	https://arxiv.org/pdf/1911.08050v1.pdf
PWC	https://paperswithcode.com/paper/carpe-diem-seize-the-samples-uncertain-at-the-1
Repo
Framework


Title	The CASE Dataset of Candidate Spaces for Advert Implantation
Authors	Soumyabrata Dev, Murhaf Hossari, Matthew Nicholson, Killian McCabe, Atul Nautiyal, Clare Conran, Jian Tang, Wei Xu, François Pitié
Abstract	With the advent of faster internet services and growth of multimedia content, we observe a massive growth in the number of online videos. The users generate these video contents at an unprecedented rate, owing to the use of smart-phones and other hand-held video capturing devices. This creates immense potential for the advertising and marketing agencies to create personalized content for the users. In this paper, we attempt to assist the video editors to generate augmented video content, by proposing candidate spaces in video frames. We propose and release a large-scale dataset of outdoor scenes, along with manually annotated maps for candidate spaces. We also benchmark several deep-learning based semantic segmentation algorithms on this proposed dataset.
Tasks	Semantic Segmentation
Published	2019-03-21
URL	http://arxiv.org/abs/1903.08943v2
PDF	http://arxiv.org/pdf/1903.08943v2.pdf
PWC	https://paperswithcode.com/paper/the-case-dataset-of-candidate-spaces-for
Repo
Framework

End-to-end learning of energy-based representations for irregularly-sampled signals and images


Title	End-to-end learning of energy-based representations for irregularly-sampled signals and images
Authors	Ronan Fablet, Lucas Drumetz, François Rousseau
Abstract	For numerous domains, including for instance earth observation, medical imaging, astrophysics,…, available image and signal datasets often involve irregular space-time sampling patterns and large missing data rates. These sampling properties may be critical to apply state-of-the-art learning-based (e.g., auto-encoders, CNNs,…), fully benefit from the available large-scale observations and reach breakthroughs in the reconstruction and identification of processes of interest. In this paper, we address the end-to-end learning of representations of signals, images and image sequences from irregularly-sampled data, i.e. when the training data involved missing data. From an analogy to Bayesian formulation, we consider energy-based representations. Two energy forms are investigated: one derived from auto-encoders and one relating to Gibbs priors. The learning stage of these energy-based representations (or priors) involve a joint interpolation issue, which amounts to solving an energy minimization problem under observation constraints. Using a neural-network-based implementation of the considered energy forms, we can state an end-to-end learning scheme from irregularly-sampled data. We demonstrate the relevance of the proposed representations for different case-studies: namely, multivariate time series, 2D images and image sequences.
Tasks	Time Series
Published	2019-10-01
URL	https://arxiv.org/abs/1910.00556v1
PDF	https://arxiv.org/pdf/1910.00556v1.pdf
PWC	https://paperswithcode.com/paper/end-to-end-learning-of-energy-based-1
Repo
Framework

Imitation-Regularized Offline Learning


Title	Imitation-Regularized Offline Learning
Authors	Yifei Ma, Yu-Xiang Wang, Balakrishnan, Narayanaswamy
Abstract	We study the problem of offline learning in automated decision systems under the contextual bandits model. We are given logged historical data consisting of contexts, (randomized) actions, and (nonnegative) rewards. A common goal is to evaluate what would happen if different actions were taken in the same contexts, so as to optimize the action policies accordingly. The typical approach to this problem, inverse probability weighted estimation (IPWE) [Bottou et al., 2013], requires logged action probabilities, which may be missing in practice due to engineering complications. Even when available, small action probabilities cause large uncertainty in IPWE, rendering the corresponding results insignificant. To solve both problems, we show how one can use policy improvement (PIL) objectives, regularized by policy imitation (IML). We motivate and analyze PIL as an extension to Clipped-IPWE, by showing that both are lower-bound surrogates to the vanilla IPWE. We also formally connect IML to IPWE variance estimation [Swaminathan and Joachims 2015] and natural policy gradients. Without probability logging, our PIL-IML interpretations justify and improve, by reward-weighting, the state-of-art cross-entropy (CE) loss that predicts the action items among all action candidates available in the same contexts. With probability logging, our main theoretical contribution connects IML-underfitting to the existence of either confounding variables or model misspecification. We show the value and accuracy of our insights by simulations based on Simpson’s paradox, standard UCI multiclass-to-bandit conversions and on the Criteo counterfactual analysis challenge dataset.
Tasks	Multi-Armed Bandits
Published	2019-01-15
URL	http://arxiv.org/abs/1901.04723v1
PDF	http://arxiv.org/pdf/1901.04723v1.pdf
PWC	https://paperswithcode.com/paper/imitation-regularized-offline-learning
Repo
Framework

Semantic query-by-example speech search using visual grounding


Title	Semantic query-by-example speech search using visual grounding
Authors	Herman Kamper, Aristotelis Anastassiou, Karen Livescu
Abstract	A number of recent studies have started to investigate how speech systems can be trained on untranscribed speech by leveraging accompanying images at training time. Examples of tasks include keyword prediction and within- and across-mode retrieval. Here we consider how such models can be used for query-by-example (QbE) search, the task of retrieving utterances relevant to a given spoken query. We are particularly interested in semantic QbE, where the task is not only to retrieve utterances containing exact instances of the query, but also utterances whose meaning is relevant to the query. We follow a segmental QbE approach where variable-duration speech segments (queries, search utterances) are mapped to fixed-dimensional embedding vectors. We show that a QbE system using an embedding function trained on visually grounded speech data outperforms a purely acoustic QbE system in terms of both exact and semantic retrieval performance.
Tasks
Published	2019-04-15
URL	http://arxiv.org/abs/1904.07078v1
PDF	http://arxiv.org/pdf/1904.07078v1.pdf
PWC	https://paperswithcode.com/paper/semantic-query-by-example-speech-search-using
Repo
Framework

Characterization of Glue Variables in CDCL SAT Solving


Title	Characterization of Glue Variables in CDCL SAT Solving
Authors	Md Solimul Chowdhury, Martin Müller, Jia-Huai You
Abstract	A state-of-the-art criterion to evaluate the importance of a given learned clause is called Literal Block Distance (LBD) score. It measures the number of distinct decision levels in a given learned clause. The lower the LBD score of a learned clause, the better is its quality. The learned clauses with LBD score of 2, called glue clauses, are known to possess high pruning power which are never deleted from the clause databases of the modern CDCL SAT solvers. In this work, we relate glue clauses to decision variables. We call the variables that appeared in at least one glue clause up to the current search state Glue Variables. We first show experimentally, by running the state-of-the-art CDCL SAT solver MapleLCMDist on benchmarks from SAT Competition-2017 and 2018, that branching decisions with glue variables are categorically more inference and conflict efficient than nonglue variables. Based on this observation, we develop a structure aware CDCL variable bumping scheme, which bumps the activity score of a glue variable based on its appearance count in the glue clauses that are learned so far by the search. Empirical evaluation shows effectiveness of the new method over the main track instances from SAT Competition 2017 and 2018.
Tasks
Published	2019-04-25
URL	http://arxiv.org/abs/1904.11106v1
PDF	http://arxiv.org/pdf/1904.11106v1.pdf
PWC	https://paperswithcode.com/paper/characterization-of-glue-variables-in-cdcl
Repo
Framework

Dynamical Anatomy of NARMA10 Benchmark Task


Title	Dynamical Anatomy of NARMA10 Benchmark Task
Authors	Tomoyuki Kubota, Kohei Nakajima, Hirokazu Takahashi
Abstract	The emulation task of a nonlinear autoregressive moving average model, i.e., the NARMA10 task, has been widely used as a benchmark task for recurrent neural networks, especially in reservoir computing. However, the type and quantity of computational capabilities required to emulate the NARMA10 model remain unclear, and, to date, the NARMA10 task has been utilized blindly. Therefore, in this study, we have investigated the properties of the NARMA10 model from a dynamical system perspective. We revealed its bifurcation structure and basin of attraction, as well as the system’s Lyapunov spectra. Furthermore, we have analyzed the computational capabilities required to emulate the NARMA10 model by decomposing it into multiple combinations of orthogonal nonlinear polynomials using Legendre polynomials, and we directly evaluated its information processing capacity together with its dependences on some system parameters. The result demonstrates that the NARMA10 model contains an unstable region in the phase space that makes the system diverge according to the selection of the input range and initial conditions. Furthermore, the information processing capacity of the model varies according to the input range. These properties prevent safe application of this model and fair comparisons among experiments, which are unfavorable for a benchmark task. As a result, we propose a benchmark model that can clearly evaluate equivalent computational capacity using NARMA10. Compared to the original NARMA10 model, the proposed model is highly stable and robust against the input range settings.
Tasks
Published	2019-06-11
URL	https://arxiv.org/abs/1906.04608v3
PDF	https://arxiv.org/pdf/1906.04608v3.pdf
PWC	https://paperswithcode.com/paper/dynamical-anatomy-of-narma10-benchmark-task
Repo
Framework

Dilated Spatial Generative Adversarial Networks for Ergodic Image Generation


Title	Dilated Spatial Generative Adversarial Networks for Ergodic Image Generation
Authors	Cyprien Ruffino, Romain Hérault, Eric Laloy, Gilles Gasso
Abstract	Generative models have recently received renewed attention as a result of adversarial learning. Generative adversarial networks consist of samples generation model and a discrimination model able to distinguish between genuine and synthetic samples. In combination with convolutional (for the discriminator) and de-convolutional (for the generator) layers, they are particularly suitable for image generation, especially of natural scenes. However, the presence of fully connected layers adds global dependencies in the generated images. This may lead to high and global variations in the generated sample for small local variations in the input noise. In this work we propose to use architec-tures based on fully convolutional networks (including among others dilated layers), architectures specifically designed to generate globally ergodic images, that is images without global dependencies. Conducted experiments reveal that these architectures are well suited for generating natural textures such as geologic structures .
Tasks	Image Generation
Published	2019-05-15
URL	https://arxiv.org/abs/1905.08613v1
PDF	https://arxiv.org/pdf/1905.08613v1.pdf
PWC	https://paperswithcode.com/paper/190508613
Repo
Framework

Trend to Equilibrium for the Kinetic Fokker-Planck Equation via the Neural Network Approach


Title	Trend to Equilibrium for the Kinetic Fokker-Planck Equation via the Neural Network Approach
Authors	Hyung Ju Hwang, Jin Woo Jang, Hyeontae Jo, Jae Yong Lee
Abstract	The issue of the relaxation to equilibrium has been at the core of the kinetic theory of rarefied gas dynamics. In the paper, we introduce the Deep Neural Network (DNN) approximated solutions to the kinetic Fokker-Planck equation in a bounded interval and study the large-time asymptotic behavior of the solutions and other physically relevant macroscopic quantities. We impose the varied types of boundary conditions including the inflow-type and the reflection-type boundaries as well as the varied diffusion and friction coefficients and study the boundary effects on the asymptotic behaviors. These include the predictions on the large-time behaviors of the pointwise values of the particle distribution and the macroscopic physical quantities including the total kinetic energy, the entropy, and the free energy. We also provide the theoretical supports for the pointwise convergence of the neural network solutions to the \textit{a priori} analytic solutions. We use the library \textit{PyTorch}, the activation function \textit{tanh} between layers, and the \textit{Adam} optimizer for the Deep Learning algorithm.
Tasks
Published	2019-11-22
URL	https://arxiv.org/abs/1911.09843v1
PDF	https://arxiv.org/pdf/1911.09843v1.pdf
PWC	https://paperswithcode.com/paper/trend-to-equilibrium-for-the-kinetic-fokker
Repo
Framework

Bounded Fuzzy Possibilistic Method


Title	Bounded Fuzzy Possibilistic Method
Authors	Hossein Yazdani
Abstract	This paper introduces Bounded Fuzzy Possibilistic Method (BFPM) by addressing several issues that previous clustering/classification methods have not considered. In fuzzy clustering, object’s membership values should sum to 1. Hence, any object may obtain full membership in at most one cluster. Possibilistic clustering methods remove this restriction. However, BFPM differs from previous fuzzy and possibilistic clustering approaches by allowing the membership function to take larger values with respect to all clusters. Furthermore, in BFPM, a data object can have full membership in multiple clusters or even in all clusters. BFPM relaxes the boundary conditions (restrictions) in membership assignment. The proposed methodology satisfies the necessity of obtaining full memberships and overcomes the issues with conventional methods on dealing with overlapping. Analysing the objects’ movements from their own cluster to another (mutation) is also proposed in this paper. BFPM has been applied in different domains in geometry, set theory, anomaly detection, risk management, diagnosis diseases, and other disciplines. Validity and comparison indexes have been also used to evaluate the accuracy of BFPM. BFPM has been evaluated in terms of accuracy, fuzzification constant (different norms), objects’ movement analysis, and covering diversity. The promising results prove the importance of considering the proposed methodology in learning methods to track the behaviour of data objects, in addition to obtain accurate results.
Tasks	Anomaly Detection
Published	2019-02-08
URL	http://arxiv.org/abs/1902.03127v1
PDF	http://arxiv.org/pdf/1902.03127v1.pdf
PWC	https://paperswithcode.com/paper/bounded-fuzzy-possibilistic-method
Repo
Framework