May 7, 2019

2881 words 14 mins read

Paper Group ANR 43

Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis. Markov Random Field Model-Based Salt and Pepper Noise Removal. Bitwise Neural Networks. Uniform Transformation of Non-Separable Probability Distributions. Synthesis of Shared Control Protocols with Provable Safety and Performance Guarantees. A Survey of S …

Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis


Title	Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
Authors	Bo Jiang, Tianyi Lin, Shiqian Ma, Shuzhong Zhang
Abstract	Nonconvex and nonsmooth optimization problems are frequently encountered in much of statistics, business, science and engineering, but they are not yet widely recognized as a technology in the sense of scalability. A reason for this relatively low degree of popularity is the lack of a well developed system of theory and algorithms to support the applications, as is the case for its convex counterpart. This paper aims to take one step in the direction of disciplined nonconvex and nonsmooth optimization. In particular, we consider in this paper some constrained nonconvex optimization models in block decision variables, with or without coupled affine constraints. In the case of without coupled constraints, we show a sublinear rate of convergence to an $\epsilon$-stationary solution in the form of variational inequality for a generalized conditional gradient method, where the convergence rate is shown to be dependent on the H"olderian continuity of the gradient of the smooth part of the objective. For the model with coupled affine constraints, we introduce corresponding $\epsilon$-stationarity conditions, and apply two proximal-type variants of the ADMM to solve such a model, assuming the proximal ADMM updates can be implemented for all the block variables except for the last block, for which either a gradient step or a majorization-minimization step is implemented. We show an iteration complexity bound of $O(1/\epsilon^2)$ to reach an $\epsilon$-stationary solution for both algorithms. Moreover, we show that the same iteration complexity of a proximal BCD method follows immediately. Numerical results are provided to illustrate the efficacy of the proposed algorithms for tensor robust PCA.
Tasks
Published	2016-05-09
URL	http://arxiv.org/abs/1605.02408v5
PDF	http://arxiv.org/pdf/1605.02408v5.pdf
PWC	https://paperswithcode.com/paper/structured-nonconvex-and-nonsmooth
Repo
Framework

Markov Random Field Model-Based Salt and Pepper Noise Removal


Title	Markov Random Field Model-Based Salt and Pepper Noise Removal
Authors	Ahmadreza Baghaie
Abstract	Problem of impulse noise reduction is a very well studied problem in image processing community and many different approaches have been proposed to tackle this problem. In the current work, the problem of fixed value impulse noise (salt and pepper) removal from images is investigated by use of a Markov Random Field (MRF) models with smoothness priors. After the formulation of the problem as an inpainting problem, graph cuts with $\alpha$-expansion moves are considered for minimization of the energy functional. As for comparisons, several other minimization techniques that are widely used for MRF models’ optimization are considered and the results are compared using Peak-Signal-to-Noise-Ratio (PSNR) and Structural Similarity Index (SSIM) as metrics. The investigations show the superiority of graph cuts with $\alpha$-expansion moves over the other techniques both in terms of PSNR and also computational times.
Tasks	Salt-And-Pepper Noise Removal
Published	2016-09-20
URL	http://arxiv.org/abs/1609.06341v1
PDF	http://arxiv.org/pdf/1609.06341v1.pdf
PWC	https://paperswithcode.com/paper/markov-random-field-model-based-salt-and
Repo
Framework

Bitwise Neural Networks


Title	Bitwise Neural Networks
Authors	Minje Kim, Paris Smaragdis
Abstract	Based on the assumption that there exists a neural network that efficiently represents a set of Boolean functions between all binary inputs and outputs, we propose a process for developing and deploying neural networks whose weight parameters, bias terms, input, and intermediate hidden layer output signals, are all binary-valued, and require only basic bit logic for the feedforward pass. The proposed Bitwise Neural Network (BNN) is especially suitable for resource-constrained environments, since it replaces either floating or fixed-point arithmetic with significantly more efficient bitwise operations. Hence, the BNN requires for less spatial complexity, less memory bandwidth, and less power consumption in hardware. In order to design such networks, we propose to add a few training schemes, such as weight compression and noisy backpropagation, which result in a bitwise network that performs almost as well as its corresponding real-valued network. We test the proposed network on the MNIST dataset, represented using binary features, and show that BNNs result in competitive performance while offering dramatic computational savings.
Tasks
Published	2016-01-22
URL	http://arxiv.org/abs/1601.06071v1
PDF	http://arxiv.org/pdf/1601.06071v1.pdf
PWC	https://paperswithcode.com/paper/bitwise-neural-networks
Repo
Framework

Uniform Transformation of Non-Separable Probability Distributions


Title	Uniform Transformation of Non-Separable Probability Distributions
Authors	Eric Kee
Abstract	A theoretical framework is developed to describe the transformation that distributes probability density functions uniformly over space. In one dimension, the cumulative distribution can be used, but does not generalize to higher dimensions, or non-separable distributions. A potential function is shown to link probability density functions to their transformation, and to generalize the cumulative. A numerical method is developed to compute the potential, and examples are shown in two dimensions.
Tasks
Published	2016-08-16
URL	http://arxiv.org/abs/1609.01982v1
PDF	http://arxiv.org/pdf/1609.01982v1.pdf
PWC	https://paperswithcode.com/paper/uniform-transformation-of-non-separable
Repo
Framework

Synthesis of Shared Control Protocols with Provable Safety and Performance Guarantees


Title	Synthesis of Shared Control Protocols with Provable Safety and Performance Guarantees
Authors	Nils Jansen, Murat Cubuktepe, Ufuk Topcu
Abstract	We formalize synthesis of shared control protocols with correctness guarantees for temporal logic specifications. More specifically, we introduce a modeling formalism in which both a human and an autonomy protocol can issue commands to a robot towards performing a certain task. These commands are blended into a joint input to the robot. The autonomy protocol is synthesized using an abstraction of possible human commands accounting for randomness in decisions caused by factors such as fatigue or incomprehensibility of the problem at hand. The synthesis is designed to ensure that the resulting robot behavior satisfies given safety and performance specifications, e.g., in temporal logic. Our solution is based on nonlinear programming and we address the inherent scalability issue by presenting alternative methods. We assess the feasibility and the scalability of the approach by an experimental evaluation.
Tasks
Published	2016-10-26
URL	http://arxiv.org/abs/1610.08500v1
PDF	http://arxiv.org/pdf/1610.08500v1.pdf
PWC	https://paperswithcode.com/paper/synthesis-of-shared-control-protocols-with
Repo
Framework

A Survey of Semantic Segmentation


Title	A Survey of Semantic Segmentation
Authors	Martin Thoma
Abstract	This survey gives an overview over different techniques used for pixel-level semantic segmentation. Metrics and datasets for the evaluation of segmentation algorithms and traditional approaches for segmentation such as unsupervised methods, Decision Forests and SVMs are described and pointers to the relevant papers are given. Recently published approaches with convolutional neural networks are mentioned and typical problematic situations for segmentation algorithms are examined. A taxonomy of segmentation algorithms is given.
Tasks	Semantic Segmentation
Published	2016-02-21
URL	http://arxiv.org/abs/1602.06541v2
PDF	http://arxiv.org/pdf/1602.06541v2.pdf
PWC	https://paperswithcode.com/paper/a-survey-of-semantic-segmentation
Repo
Framework

Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem


Title	Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
Authors	Alexandra Carpentier, Andrea Locatelli
Abstract	We consider the problem of \textit{best arm identification} with a \textit{fixed budget $T$}, in the $K$-armed stochastic bandit setting, with arms distribution defined on $[0,1]$. We prove that any bandit strategy, for at least one bandit problem characterized by a complexity $H$, will misidentify the best arm with probability lower bounded by $$\exp\Big(-\frac{T}{\log(K)H}\Big),$$ where $H$ is the sum for all sub-optimal arms of the inverse of the squared gaps. Our result disproves formally the general belief - coming from results in the fixed confidence setting - that there must exist an algorithm for this problem whose probability of error is upper bounded by $\exp(-T/H)$. This also proves that some existing strategies based on the Successive Rejection of the arms are optimal - closing therefore the current gap between upper and lower bounds for the fixed budget best arm identification problem.
Tasks
Published	2016-05-29
URL	http://arxiv.org/abs/1605.09004v1
PDF	http://arxiv.org/pdf/1605.09004v1.pdf
PWC	https://paperswithcode.com/paper/tight-lower-bounds-for-the-fixed-budget-best
Repo
Framework

Video Captioning with Transferred Semantic Attributes


Title	Video Captioning with Transferred Semantic Attributes
Authors	Yingwei Pan, Ting Yao, Houqiang Li, Tao Mei
Abstract	Automatically generating natural language descriptions of videos plays a fundamental challenge for computer vision community. Most recent progress in this problem has been achieved through employing 2-D and/or 3-D Convolutional Neural Networks (CNN) to encode video content and Recurrent Neural Networks (RNN) to decode a sentence. In this paper, we present Long Short-Term Memory with Transferred Semantic Attributes (LSTM-TSA)—a novel deep architecture that incorporates the transferred semantic attributes learnt from images and videos into the CNN plus RNN framework, by training them in an end-to-end manner. The design of LSTM-TSA is highly inspired by the facts that 1) semantic attributes play a significant contribution to captioning, and 2) images and videos carry complementary semantics and thus can reinforce each other for captioning. To boost video captioning, we propose a novel transfer unit to model the mutually correlated attributes learnt from images and videos. Extensive experiments are conducted on three public datasets, i.e., MSVD, M-VAD and MPII-MD. Our proposed LSTM-TSA achieves to-date the best published performance in sentence generation on MSVD: 52.8% and 74.0% in terms of BLEU@4 and CIDEr-D. Superior results when compared to state-of-the-art methods are also reported on M-VAD and MPII-MD.
Tasks	Video Captioning
Published	2016-11-23
URL	http://arxiv.org/abs/1611.07675v1
PDF	http://arxiv.org/pdf/1611.07675v1.pdf
PWC	https://paperswithcode.com/paper/video-captioning-with-transferred-semantic
Repo
Framework

Multimodal Memory Modelling for Video Captioning


Title	Multimodal Memory Modelling for Video Captioning
Authors	Junbo Wang, Wei Wang, Yan Huang, Liang Wang, Tieniu Tan
Abstract	Video captioning which automatically translates video clips into natural language sentences is a very important task in computer vision. By virtue of recent deep learning technologies, e.g., convolutional neural networks (CNNs) and recurrent neural networks (RNNs), video captioning has made great progress. However, learning an effective mapping from visual sequence space to language space is still a challenging problem. In this paper, we propose a Multimodal Memory Model (M3) to describe videos, which builds a visual and textual shared memory to model the long-term visual-textual dependency and further guide global visual attention on described targets. Specifically, the proposed M3 attaches an external memory to store and retrieve both visual and textual contents by interacting with video and sentence with multiple read and write operations. First, text representation in the Long Short-Term Memory (LSTM) based text decoder is written into the memory, and the memory contents will be read out to guide an attention to select related visual targets. Then, the selected visual information is written into the memory, which will be further read out to the text decoder. To evaluate the proposed model, we perform experiments on two publicly benchmark datasets: MSVD and MSR-VTT. The experimental results demonstrate that our method outperforms the state-of-theart methods in terms of BLEU and METEOR.
Tasks	Video Captioning
Published	2016-11-17
URL	http://arxiv.org/abs/1611.05592v1
PDF	http://arxiv.org/pdf/1611.05592v1.pdf
PWC	https://paperswithcode.com/paper/multimodal-memory-modelling-for-video
Repo
Framework

Exploring the coevolution of predator and prey morphology and behavior


Title	Exploring the coevolution of predator and prey morphology and behavior
Authors	Randal S. Olson, Arend Hintze, Fred C. Dyer, Jason H. Moore, Christoph Adami
Abstract	A common idiom in biology education states, “Eyes in the front, the animal hunts. Eyes on the side, the animal hides.” In this paper, we explore one possible explanation for why predators tend to have forward-facing, high-acuity visual systems. We do so using an agent-based computational model of evolution, where predators and prey interact and adapt their behavior and morphology to one another over successive generations of evolution. In this model, we observe a coevolutionary cycle between prey swarming behavior and the predator’s visual system, where the predator and prey continually adapt their visual system and behavior, respectively, over evolutionary time in reaction to one another due to the well-known “predator confusion effect.” Furthermore, we provide evidence that the predator visual system is what drives this coevolutionary cycle, and suggest that the cycle could be closed if the predator evolves a hybrid visual system capable of narrow, high-acuity vision for tracking prey as well as broad, coarse vision for prey discovery. Thus, the conflicting demands imposed on a predator’s visual system by the predator confusion effect could have led to the evolution of complex eyes in many predators.
Tasks
Published	2016-02-29
URL	http://arxiv.org/abs/1602.08802v1
PDF	http://arxiv.org/pdf/1602.08802v1.pdf
PWC	https://paperswithcode.com/paper/exploring-the-coevolution-of-predator-and
Repo
Framework

Optimal Rates For Regularization Of Statistical Inverse Learning Problems


Title	Optimal Rates For Regularization Of Statistical Inverse Learning Problems
Authors	Gilles Blanchard, Nicole Mücke
Abstract	We consider a statistical inverse learning problem, where we observe the image of a function $f$ through a linear operator $A$ at i.i.d. random design points $X_i$, superposed with an additive noise. The distribution of the design points is unknown and can be very general. We analyze simultaneously the direct (estimation of $Af$) and the inverse (estimation of $f$) learning problems. In this general framework, we obtain strong and weak minimax optimal rates of convergence (as the number of observations $n$ grows large) for a large class of spectral regularization methods over regularity classes defined through appropriate source conditions. This improves on or completes previous results obtained in related settings. The optimality of the obtained rates is shown not only in the exponent in $n$ but also in the explicit dependency of the constant factor in the variance of the noise and the radius of the source condition set.
Tasks
Published	2016-04-14
URL	http://arxiv.org/abs/1604.04054v1
PDF	http://arxiv.org/pdf/1604.04054v1.pdf
PWC	https://paperswithcode.com/paper/optimal-rates-for-regularization-of
Repo
Framework

Design of Data-Driven Mathematical Laws for Optimal Statistical Classification Systems


Title	Design of Data-Driven Mathematical Laws for Optimal Statistical Classification Systems
Authors	Denise M. Reeves
Abstract	This article will devise data-driven, mathematical laws that generate optimal, statistical classification systems which achieve minimum error rates for data distributions with unchanging statistics. Thereby, I will design learning machines that minimize the expected risk or probability of misclassification. I will devise a system of fundamental equations of binary classification for a classification system in statistical equilibrium. I will use this system of equations to formulate the problem of learning unknown, linear and quadratic discriminant functions from data as a locus problem, thereby formulating geometric locus methods within a statistical framework. Solving locus problems involves finding equations of curves or surfaces defined by given properties and finding graphs or loci of given equations. I will devise three systems of data-driven, locus equations that generate optimal, statistical classification systems. Each class of learning machines satisfies fundamental statistical laws for a classification system in statistical equilibrium. Thereby, I will formulate three classes of learning machines that are scalable modules for optimal, statistical pattern recognition systems, all of which are capable of performing a wide variety of statistical pattern recognition tasks, where any given M-class statistical pattern recognition system exhibits optimal generalization performance for an M-class feature space.
Tasks
Published	2016-12-12
URL	http://arxiv.org/abs/1612.03902v9
PDF	http://arxiv.org/pdf/1612.03902v9.pdf
PWC	https://paperswithcode.com/paper/design-of-data-driven-mathematical-laws-for
Repo
Framework

Zipf’s law is a consequence of coherent language production


Title	Zipf’s law is a consequence of coherent language production
Authors	Jake Ryland Williams, James P. Bagrow, Andrew J. Reagan, Sharon E. Alajajian, Christopher M. Danforth, Peter Sheridan Dodds
Abstract	The task of text segmentation may be undertaken at many levels in text analysis—paragraphs, sentences, words, or even letters. Here, we focus on a relatively fine scale of segmentation, hypothesizing it to be in accord with a stochastic model of language generation, as the smallest scale where independent units of meaning are produced. Our goals in this letter include the development of methods for the segmentation of these minimal independent units, which produce feature-representations of texts that align with the independence assumption of the bag-of-terms model, commonly used for prediction and classification in computational text analysis. We also propose the measurement of texts’ association (with respect to realized segmentations) to the model of language generation. We find (1) that our segmentations of phrases exhibit much better associations to the generation model than words and (2), that texts which are well fit are generally topically homogeneous. Because our generative model produces Zipf’s law, our study further suggests that Zipf’s law may be a consequence of homogeneity in language production.
Tasks	Text Generation
Published	2016-01-29
URL	http://arxiv.org/abs/1601.07969v2
PDF	http://arxiv.org/pdf/1601.07969v2.pdf
PWC	https://paperswithcode.com/paper/zipfs-law-is-a-consequence-of-coherent
Repo
Framework

Regression with n$\to$1 by Expert Knowledge Elicitation


Title	Regression with n$\to$1 by Expert Knowledge Elicitation
Authors	Marta Soare, Muhammad Ammad-ud-din, Samuel Kaski
Abstract	We consider regression under the “extremely small $n$ large $p$” condition, where the number of samples $n$ is so small compared to the dimensionality $p$ that predictors cannot be estimated without prior knowledge. This setup occurs in personalized medicine, for instance, when predicting treatment outcomes for an individual patient based on noisy high-dimensional genomics data. A remaining source of information is expert knowledge, which has received relatively little attention in recent years. We formulate the inference problem of asking expert feedback on features on a budget, propose an elicitation strategy for a simple “small $n$” setting, and derive conditions under which the elicitation strategy is optimal. Experiments on simulated experts, both on synthetic and genomics data, demonstrate that the proposed strategy can drastically improve prediction accuracy.
Tasks
Published	2016-05-20
URL	http://arxiv.org/abs/1605.06477v3
PDF	http://arxiv.org/pdf/1605.06477v3.pdf
PWC	https://paperswithcode.com/paper/regression-with-nto1-by-expert-knowledge
Repo
Framework

Scale-invariance of ruggedness measures in fractal fitness landscapes


Title	Scale-invariance of ruggedness measures in fractal fitness landscapes
Authors	Hendrik Richter
Abstract	The paper deals with using chaos to direct trajectories to targets and analyzes ruggedness and fractality of the resulting fitness landscapes. The targeting problem is formulated as a dynamic fitness landscape and four different chaotic maps generating such a landscape are studied. By using a computational approach, we analyze properties of the landscapes and quantify their fractal and rugged characteristics. In particular, it is shown that ruggedness measures such as correlation length and information content are scale-invariant and self-similar.
Tasks
Published	2016-12-21
URL	http://arxiv.org/abs/1612.07029v2
PDF	http://arxiv.org/pdf/1612.07029v2.pdf
PWC	https://paperswithcode.com/paper/scale-invariance-of-ruggedness-measures-in
Repo
Framework