July 27, 2019

2722 words 13 mins read

Paper Group ANR 664

Runtime Analysis of the $(1+(λ,λ))$ Genetic Algorithm on Random Satisfiable 3-CNF Formulas. Identifying Nonlinear 1-Step Causal Influences in Presence of Latent Variables. Fast Causal Inference with Non-Random Missingness by Test-Wise Deletion. Compressive Sensing via Convolutional Factor Analysis. Parallelizing Linear Recurrent Neural Nets Over Se …

Runtime Analysis of the $(1+(λ,λ))$ Genetic Algorithm on Random Satisfiable 3-CNF Formulas


Title	Runtime Analysis of the $(1+(λ,λ))$ Genetic Algorithm on Random Satisfiable 3-CNF Formulas
Authors	Maxim Buzdalov, Benjamin Doerr
Abstract	The $(1+(\lambda,\lambda))$ genetic algorithm, first proposed at GECCO 2013, showed a surprisingly good performance on so me optimization problems. The theoretical analysis so far was restricted to the OneMax test function, where this GA profited from the perfect fitness-distance correlation. In this work, we conduct a rigorous runtime analysis of this GA on random 3-SAT instances in the planted solution model having at least logarithmic average degree, which are known to have a weaker fitness distance correlation. We prove that this GA with fixed not too large population size again obtains runtimes better than $\Theta(n \log n)$, which is a lower bound for most evolutionary algorithms on pseudo-Boolean problems with unique optimum. However, the self-adjusting version of the GA risks reaching population sizes at which the intermediate selection of the GA, due to the weaker fitness-distance correlation, is not able to distinguish a profitable offspring from others. We show that this problem can be overcome by equipping the self-adjusting GA with an upper limit for the population size. Apart from sparse instances, this limit can be chosen in a way that the asymptotic performance does not worsen compared to the idealistic OneMax case. Overall, this work shows that the $(1+(\lambda,\lambda))$ GA can provably have a good performance on combinatorial search and optimization problems also in the presence of a weaker fitness-distance correlation.
Tasks
Published	2017-04-14
URL	http://arxiv.org/abs/1704.04366v1
PDF	http://arxiv.org/pdf/1704.04366v1.pdf
PWC	https://paperswithcode.com/paper/runtime-analysis-of-the-1-genetic-algorithm
Repo
Framework

Identifying Nonlinear 1-Step Causal Influences in Presence of Latent Variables


Title	Identifying Nonlinear 1-Step Causal Influences in Presence of Latent Variables
Authors	Saber Salehkaleybar, Jalal Etesami, Negar Kiyavash
Abstract	We propose an approach for learning the causal structure in stochastic dynamical systems with a $1$-step functional dependency in the presence of latent variables. We propose an information-theoretic approach that allows us to recover the causal relations among the observed variables as long as the latent variables evolve without exogenous noise. We further propose an efficient learning method based on linear regression for the special sub-case when the dynamics are restricted to be linear. We validate the performance of our approach via numerical simulations.
Tasks
Published	2017-01-23
URL	http://arxiv.org/abs/1701.06605v1
PDF	http://arxiv.org/pdf/1701.06605v1.pdf
PWC	https://paperswithcode.com/paper/identifying-nonlinear-1-step-causal
Repo
Framework

Fast Causal Inference with Non-Random Missingness by Test-Wise Deletion


Title	Fast Causal Inference with Non-Random Missingness by Test-Wise Deletion
Authors	Eric V. Strobl, Shyam Visweswaran, Peter L. Spirtes
Abstract	Many real datasets contain values missing not at random (MNAR). In this scenario, investigators often perform list-wise deletion, or delete samples with any missing values, before applying causal discovery algorithms. List-wise deletion is a sound and general strategy when paired with algorithms such as FCI and RFCI, but the deletion procedure also eliminates otherwise good samples that contain only a few missing values. In this report, we show that we can more efficiently utilize the observed values with test-wise deletion while still maintaining algorithmic soundness. Here, test-wise deletion refers to the process of list-wise deleting samples only among the variables required for each conditional independence (CI) test used in constraint-based searches. Test-wise deletion therefore often saves more samples than list-wise deletion for each CI test, especially when we have a sparse underlying graph. Our theoretical results show that test-wise deletion is sound under the justifiable assumption that none of the missingness mechanisms causally affect each other in the underlying causal graph. We also find that FCI and RFCI with test-wise deletion outperform their list-wise deletion and imputation counterparts on average when MNAR holds in both synthetic and real data.
Tasks	Causal Discovery, Causal Inference, Imputation
Published	2017-05-25
URL	http://arxiv.org/abs/1705.09031v1
PDF	http://arxiv.org/pdf/1705.09031v1.pdf
PWC	https://paperswithcode.com/paper/fast-causal-inference-with-non-random
Repo
Framework

Compressive Sensing via Convolutional Factor Analysis


Title	Compressive Sensing via Convolutional Factor Analysis
Authors	Xin Yuan, Yunchen Pu, Lawrence Carin
Abstract	We solve the compressive sensing problem via convolutional factor analysis, where the convolutional dictionaries are learned {\em in situ} from the compressed measurements. An alternating direction method of multipliers (ADMM) paradigm for compressive sensing inversion based on convolutional factor analysis is developed. The proposed algorithm provides reconstructed images as well as features, which can be directly used for recognition ($e.g.$, classification) tasks. When a deep (multilayer) model is constructed, a stochastic unpooling process is employed to build a generative model. During reconstruction and testing, we project the upper layer dictionary to the data level and only a single layer deconvolution is required. We demonstrate that using $\sim30%$ (relative to pixel numbers) compressed measurements, the proposed model achieves the classification accuracy comparable to the original data on MNIST. We also observe that when the compressed measurements are very limited ($e.g.$, $<10%$), the upper layer dictionary can provide better reconstruction results than the bottom layer.
Tasks	Compressive Sensing
Published	2017-01-11
URL	http://arxiv.org/abs/1701.03006v1
PDF	http://arxiv.org/pdf/1701.03006v1.pdf
PWC	https://paperswithcode.com/paper/compressive-sensing-via-convolutional-factor
Repo
Framework

Parallelizing Linear Recurrent Neural Nets Over Sequence Length


Title	Parallelizing Linear Recurrent Neural Nets Over Sequence Length
Authors	Eric Martin, Chris Cundy
Abstract	Recurrent neural networks (RNNs) are widely used to model sequential data but their non-linear dependencies between sequence elements prevent parallelizing training over sequence length. We show the training of RNNs with only linear sequential dependencies can be parallelized over the sequence length using the parallel scan algorithm, leading to rapid training on long sequences even with small minibatch size. We develop a parallel linear recurrence CUDA kernel and show that it can be applied to immediately speed up training and inference of several state of the art RNN architectures by up to 9x. We abstract recent work on linear RNNs into a new framework of linear surrogate RNNs and develop a linear surrogate model for the long short-term memory unit, the GILR-LSTM, that utilizes parallel linear recurrence. We extend sequence learning to new extremely long sequence regimes that were previously out of reach by successfully training a GILR-LSTM on a synthetic sequence classification task with a one million timestep dependency.
Tasks
Published	2017-09-12
URL	http://arxiv.org/abs/1709.04057v2
PDF	http://arxiv.org/pdf/1709.04057v2.pdf
PWC	https://paperswithcode.com/paper/parallelizing-linear-recurrent-neural-nets
Repo
Framework

Vehicle classification based on convolutional networks applied to FM-CW radar signals


Title	Vehicle classification based on convolutional networks applied to FM-CW radar signals
Authors	Samuele Capobianco, Luca Facheris, Fabrizio Cuccoli, Simone Marinai
Abstract	This paper investigates the processing of Frequency Modulated-Continuos Wave (FM-CW) radar signals for vehicle classification. In the last years deep learning has gained interest in several scientific fields and signal processing is not one exception. In this work we address the recognition of the vehicle category using a Convolutional Neural Network (CNN) applied to range Doppler signature. The developed system first transforms the 1-dimensional signal into a 3-dimensional signal that is subsequently used as input to the CNN. When using the trained model to predict the vehicle category we obtain good performance.
Tasks
Published	2017-10-09
URL	http://arxiv.org/abs/1710.05718v3
PDF	http://arxiv.org/pdf/1710.05718v3.pdf
PWC	https://paperswithcode.com/paper/vehicle-classification-based-on-convolutional
Repo
Framework

Freehand Ultrasound Image Simulation with Spatially-Conditioned Generative Adversarial Networks


Title	Freehand Ultrasound Image Simulation with Spatially-Conditioned Generative Adversarial Networks
Authors	Yipeng Hu, Eli Gibson, Li-Lin Lee, Weidi Xie, Dean C. Barratt, Tom Vercauteren, J. Alison Noble
Abstract	Sonography synthesis has a wide range of applications, including medical procedure simulation, clinical training and multimodality image registration. In this paper, we propose a machine learning approach to simulate ultrasound images at given 3D spatial locations (relative to the patient anatomy), based on conditional generative adversarial networks (GANs). In particular, we introduce a novel neural network architecture that can sample anatomically accurate images conditionally on spatial position of the (real or mock) freehand ultrasound probe. To ensure an effective and efficient spatial information assimilation, the proposed spatially-conditioned GANs take calibrated pixel coordinates in global physical space as conditioning input, and utilise residual network units and shortcuts of conditioning data in the GANs’ discriminator and generator, respectively. Using optically tracked B-mode ultrasound images, acquired by an experienced sonographer on a fetus phantom, we demonstrate the feasibility of the proposed method by two sets of quantitative results: distances were calculated between corresponding anatomical landmarks identified in the held-out ultrasound images and the simulated data at the same locations unseen to the networks; a usability study was carried out to distinguish the simulated data from the real images. In summary, we present what we believe are state-of-the-art visually realistic ultrasound images, simulated by the proposed GAN architecture that is stable to train and capable of generating plausibly diverse image samples.
Tasks	Image Registration
Published	2017-07-17
URL	http://arxiv.org/abs/1707.05392v1
PDF	http://arxiv.org/pdf/1707.05392v1.pdf
PWC	https://paperswithcode.com/paper/freehand-ultrasound-image-simulation-with
Repo
Framework

Pose-Aware Person Recognition


Title	Pose-Aware Person Recognition
Authors	Vijay Kumar, Anoop Namboodiri, Manohar Paluri, C V Jawahar
Abstract	Person recognition methods that use multiple body regions have shown significant improvements over traditional face-based recognition. One of the primary challenges in full-body person recognition is the extreme variation in pose and view point. In this work, (i) we present an approach that tackles pose variations utilizing multiple models that are trained on specific poses, and combined using pose-aware weights during testing. (ii) For learning a person representation, we propose a network that jointly optimizes a single loss over multiple body regions. (iii) Finally, we introduce new benchmarks to evaluate person recognition in diverse scenarios and show significant improvements over previously proposed approaches on all the benchmarks including the photo album setting of PIPA.
Tasks	Person Recognition
Published	2017-05-29
URL	http://arxiv.org/abs/1705.10120v1
PDF	http://arxiv.org/pdf/1705.10120v1.pdf
PWC	https://paperswithcode.com/paper/pose-aware-person-recognition
Repo
Framework

Recognizing Explicit and Implicit Hate Speech Using a Weakly Supervised Two-path Bootstrapping Approach


Title	Recognizing Explicit and Implicit Hate Speech Using a Weakly Supervised Two-path Bootstrapping Approach
Authors	Lei Gao, Alexis Kuppersmith, Ruihong Huang
Abstract	In the wake of a polarizing election, social media is laden with hateful content. To address various limitations of supervised hate speech classification methods including corpus bias and huge cost of annotation, we propose a weakly supervised two-path bootstrapping approach for an online hate speech detection model leveraging large-scale unlabeled data. This system significantly outperforms hate speech detection systems that are trained in a supervised manner using manually annotated data. Applying this model on a large quantity of tweets collected before, after, and on election day reveals motivations and patterns of inflammatory language.
Tasks	Hate Speech Detection
Published	2017-10-20
URL	http://arxiv.org/abs/1710.07394v2
PDF	http://arxiv.org/pdf/1710.07394v2.pdf
PWC	https://paperswithcode.com/paper/recognizing-explicit-and-implicit-hate-speech
Repo
Framework

Factoring Shape, Pose, and Layout from the 2D Image of a 3D Scene


Title	Factoring Shape, Pose, and Layout from the 2D Image of a 3D Scene
Authors	Shubham Tulsiani, Saurabh Gupta, David Fouhey, Alexei A. Efros, Jitendra Malik
Abstract	The goal of this paper is to take a single 2D image of a scene and recover the 3D structure in terms of a small set of factors: a layout representing the enclosing surfaces as well as a set of objects represented in terms of shape and pose. We propose a convolutional neural network-based approach to predict this representation and benchmark it on a large dataset of indoor scenes. Our experiments evaluate a number of practical design questions, demonstrate that we can infer this representation, and quantitatively and qualitatively demonstrate its merits compared to alternate representations.
Tasks
Published	2017-12-05
URL	http://arxiv.org/abs/1712.01812v2
PDF	http://arxiv.org/pdf/1712.01812v2.pdf
PWC	https://paperswithcode.com/paper/factoring-shape-pose-and-layout-from-the-2d
Repo
Framework

Iteratively Linearized Reweighted Alternating Direction Method of Multipliers for a Class of Nonconvex Problems


Title	Iteratively Linearized Reweighted Alternating Direction Method of Multipliers for a Class of Nonconvex Problems
Authors	Tao Sun, Hao Jiang, Lizhi Cheng, Wei Zhu
Abstract	In this paper, we consider solving a class of nonconvex and nonsmooth problems frequently appearing in signal processing and machine learning research. The traditional alternating direction method of multipliers encounters troubles in both mathematics and computations in solving the nonconvex and nonsmooth subproblem. In view of this, we propose a reweighted alternating direction method of multipliers. In this algorithm, all subproblems are convex and easy to solve. We also provide several guarantees for the convergence and prove that the algorithm globally converges to a critical point of an auxiliary function with the help of the Kurdyka-{\L}ojasiewicz property. Several numerical results are presented to demonstrate the efficiency of the proposed algorithm.
Tasks
Published	2017-09-01
URL	http://arxiv.org/abs/1709.00483v5
PDF	http://arxiv.org/pdf/1709.00483v5.pdf
PWC	https://paperswithcode.com/paper/iteratively-linearized-reweighted-alternating
Repo
Framework

Isointense Infant Brain Segmentation with a Hyper-dense Connected Convolutional Neural Network


Title	Isointense Infant Brain Segmentation with a Hyper-dense Connected Convolutional Neural Network
Authors	Jose Dolz, Ismail Ben Ayed, Jing Yuan, Christian Desrosiers
Abstract	Neonatal brain segmentation in magnetic resonance (MR) is a challenging problem due to poor image quality and low contrast between white and gray matter regions. Most existing approaches for this problem are based on multi-atlas label fusion strategies, which are time-consuming and sensitive to registration errors. As alternative to these methods, we propose a hyper-densely connected 3D convolutional neural network that employs MR-T1 and T2 images as input, which are processed independently in two separated paths. An important difference with previous densely connected networks is the use of direct connections between layers from the same and different paths. Adopting such dense connectivity helps the learning process by including deep supervision and improving gradient flow. We evaluated our approach on data from the MICCAI Grand Challenge on 6-month infant Brain MRI Segmentation (iSEG), obtaining very competitive results. Among 21 teams, our approach ranked first or second in most metrics, translating into a state-of-the-art performance.
Tasks	Brain Segmentation, Infant Brain Mri Segmentation
Published	2017-10-16
URL	http://arxiv.org/abs/1710.05956v4
PDF	http://arxiv.org/pdf/1710.05956v4.pdf
PWC	https://paperswithcode.com/paper/isointense-infant-brain-segmentation-with-a
Repo
Framework

Isointense infant brain MRI segmentation with a dilated convolutional neural network


Title	Isointense infant brain MRI segmentation with a dilated convolutional neural network
Authors	Pim Moeskops, Josien P. W. Pluim
Abstract	Quantitative analysis of brain MRI at the age of 6 months is difficult because of the limited contrast between white matter and gray matter. In this study, we use a dilated triplanar convolutional neural network in combination with a non-dilated 3D convolutional neural network for the segmentation of white matter, gray matter and cerebrospinal fluid in infant brain MR images, as provided by the MICCAI grand challenge on 6-month infant brain MRI segmentation.
Tasks	Infant Brain Mri Segmentation
Published	2017-08-09
URL	http://arxiv.org/abs/1708.02757v1
PDF	http://arxiv.org/pdf/1708.02757v1.pdf
PWC	https://paperswithcode.com/paper/isointense-infant-brain-mri-segmentation-with
Repo
Framework

An Expectation-Maximization Algorithm for the Fractal Inverse Problem


Title	An Expectation-Maximization Algorithm for the Fractal Inverse Problem
Authors	Peter Bloem, Steven de Rooij
Abstract	We present an Expectation-Maximization algorithm for the fractal inverse problem: the problem of fitting a fractal model to data. In our setting the fractals are Iterated Function Systems (IFS), with similitudes as the family of transformations. The data is a point cloud in ${\mathbb R}^H$ with arbitrary dimension $H$. Each IFS defines a probability distribution on ${\mathbb R}^H$, so that the fractal inverse problem can be cast as a problem of parameter estimation. We show that the algorithm reconstructs well-known fractals from data, with the model converging to high precision parameters. We also show the utility of the model as an approximation for datasources outside the IFS model class.
Tasks
Published	2017-06-09
URL	http://arxiv.org/abs/1706.03149v2
PDF	http://arxiv.org/pdf/1706.03149v2.pdf
PWC	https://paperswithcode.com/paper/an-expectation-maximization-algorithm-for-the
Repo
Framework

Anomaly Detection for a Water Treatment System Using Unsupervised Machine Learning


Title	Anomaly Detection for a Water Treatment System Using Unsupervised Machine Learning
Authors	Jun Inoue, Yoriyuki Yamagata, Yuqi Chen, Christopher M. Poskitt, Jun Sun
Abstract	In this paper, we propose and evaluate the application of unsupervised machine learning to anomaly detection for a Cyber-Physical System (CPS). We compare two methods: Deep Neural Networks (DNN) adapted to time series data generated by a CPS, and one-class Support Vector Machines (SVM). These methods are evaluated against data from the Secure Water Treatment (SWaT) testbed, a scaled-down but fully operational raw water purification plant. For both methods, we first train detectors using a log generated by SWaT operating under normal conditions. Then, we evaluate the performance of both methods using a log generated by SWaT operating under 36 different attack scenarios. We find that our DNN generates fewer false positives than our one-class SVM while our SVM detects slightly more anomalies. Overall, our DNN has a slightly better F measure than our SVM. We discuss the characteristics of the DNN and one-class SVM used in this experiment, and compare the advantages and disadvantages of the two methods.
Tasks	Anomaly Detection, Time Series
Published	2017-09-15
URL	http://arxiv.org/abs/1709.05342v2
PDF	http://arxiv.org/pdf/1709.05342v2.pdf
PWC	https://paperswithcode.com/paper/anomaly-detection-for-a-water-treatment
Repo
Framework