Paper Group ANR 1567
Fast Re-Optimization via Structural Diversity. The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property. Unsupervised predictive coding models may explain visual brain representation. Differentiated Backprojection Domain Deep Learning for Conebeam Artifact Removal. LiDAR Iris for Loop-Closure Detection. Tackling Mul …
Fast Re-Optimization via Structural Diversity
| Title | Fast Re-Optimization via Structural Diversity |
| Authors | Benjamin Doerr, Carola Doerr, Frank Neumann |
| Abstract | When a problem instance is perturbed by a small modification, one would hope to find a good solution for the new instance by building on a known good solution for the previous one. Via a rigorous mathematical analysis, we show that evolutionary algorithms, despite usually being robust problem solvers, can have unexpected difficulties to solve such re-optimization problems. When started with a random Hamming neighbor of the optimum, the (1+1) evolutionary algorithm takes $\Omega(n^2)$ time to optimize the LeadingOnes benchmark function, which is the same asymptotic optimization time when started in a randomly chosen solution. There is hence no significant advantage from re-optimizing a structurally good solution. We then propose a way to overcome such difficulties. As our mathematical analysis reveals, the reason for this undesired behavior is that during the optimization structurally good solutions can easily be replaced by structurally worse solutions of equal or better fitness. We propose a simple diversity mechanism that prevents this behavior, thereby reducing the re-optimization time for LeadingOnes to $O(\gamma\delta n)$, where $\gamma$ is the population size used by the diversity mechanism and $\delta \le \gamma$ the Hamming distance of the new optimum from the previous solution. We show similarly fast re-optimization times for the optimization of linear functions with changing constraints and for the minimum spanning tree problem. |
| Tasks | |
| Published | 2019-02-01 |
| URL | http://arxiv.org/abs/1902.00304v2 |
| http://arxiv.org/pdf/1902.00304v2.pdf | |
| PWC | https://paperswithcode.com/paper/fast-re-optimization-via-structural-diversity |
| Repo | |
| Framework | |
The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
| Title | The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property |
| Authors | David Gamarnik, Ilias Zadik |
| Abstract | In this paper we study the computational-statistical gap of the planted clique problem, where a clique of size $k$ is planted in an Erdos Renyi graph $G(n,\frac{1}{2})$ resulting in a graph $G\left(n,\frac{1}{2},k\right)$. The goal is to recover the planted clique vertices by observing $G\left(n,\frac{1}{2},k\right)$ . It is known that the clique can be recovered as long as $k \geq \left(2+\epsilon\right)\log n $ for any $\epsilon>0$, but no polynomial-time algorithm is known for this task unless $k=\Omega\left(\sqrt{n} \right)$. Following a statistical-physics inspired point of view as an attempt to understand this computational-statistical gap, we study the landscape of the “sufficiently dense” subgraphs of $G$ and their overlap with the planted clique. Using the first moment method, we study the densest subgraph problems for subgraphs with fixed, but arbitrary, overlap size with the planted clique, and provide evidence of a phase transition for the presence of Overlap Gap Property (OGP) at $k=\Theta\left(\sqrt{n}\right)$. OGP is a concept introduced originally in spin glass theory and known to suggest algorithmic hardness when it appears. We establish the presence of OGP when $k$ is a small positive power of $n$ by using a conditional second moment method. As our main technical tool, we establish the first, to the best of our knowledge, concentration results for the $K$-densest subgraph problem for the Erdos-Renyi model $G\left(n,\frac{1}{2}\right)$ when $K=n^{0.5-\epsilon}$ for arbitrary $\epsilon>0$. Finally, to study the OGP we employ a certain form of overparametrization, which is conceptually aligned with a large body of recent work in learning theory and optimization. |
| Tasks | |
| Published | 2019-04-15 |
| URL | https://arxiv.org/abs/1904.07174v2 |
| https://arxiv.org/pdf/1904.07174v2.pdf | |
| PWC | https://paperswithcode.com/paper/the-landscape-of-the-planted-clique-problem |
| Repo | |
| Framework | |
Unsupervised predictive coding models may explain visual brain representation
| Title | Unsupervised predictive coding models may explain visual brain representation |
| Authors | Marcio Fonseca |
| Abstract | Deep predictive coding networks are neuroscience-inspired unsupervised learning models that learn to predict future sensory states. We build upon the PredNet implementation by Lotter, Kreiman, and Cox (2016) to investigate if predictive coding representations are useful to predict brain activity in the visual cortex. We use representational similarity analysis (RSA) to compare PredNet representations to functional magnetic resonance imaging (fMRI) and magnetoencephalography (MEG) data from the Algonauts Project. In contrast to previous findings in the literature (Khaligh-Razavi &Kriegeskorte, 2014), we report empirical data suggesting that unsupervised models trained to predict frames of videos may outperform supervised image classification baselines. Our best submission achieves an average noise normalized score of 16.67% and 27.67% on the fMRI and MEG tracks of the Algonauts Challenge. |
| Tasks | Image Classification |
| Published | 2019-06-30 |
| URL | https://arxiv.org/abs/1907.00441v1 |
| https://arxiv.org/pdf/1907.00441v1.pdf | |
| PWC | https://paperswithcode.com/paper/unsupervised-predictive-coding-models-may |
| Repo | |
| Framework | |
Differentiated Backprojection Domain Deep Learning for Conebeam Artifact Removal
| Title | Differentiated Backprojection Domain Deep Learning for Conebeam Artifact Removal |
| Authors | Yoseob Han, Junyoung Kim, Jong Chul Ye |
| Abstract | Conebeam CT using a circular trajectory is quite often used for various applications due to its relative simple geometry. For conebeam geometry, Feldkamp, Davis and Kress algorithm is regarded as the standard reconstruction method, but this algorithm suffers from so-called conebeam artifacts as the cone angle increases. Various model-based iterative reconstruction methods have been developed to reduce the cone-beam artifacts, but these algorithms usually require multiple applications of computational expensive forward and backprojections. In this paper, we develop a novel deep learning approach for accurate conebeam artifact removal. In particular, our deep network, designed on the differentiated backprojection domain, performs a data-driven inversion of an ill-posed deconvolution problem associated with the Hilbert transform. The reconstruction results along the coronal and sagittal directions are then combined using a spectral blending technique to minimize the spectral leakage. Experimental results show that our method outperforms the existing iterative methods despite significantly reduced runtime complexity. |
| Tasks | |
| Published | 2019-06-17 |
| URL | https://arxiv.org/abs/1906.06854v1 |
| https://arxiv.org/pdf/1906.06854v1.pdf | |
| PWC | https://paperswithcode.com/paper/differentiated-backprojection-domain-deep |
| Repo | |
| Framework | |
LiDAR Iris for Loop-Closure Detection
| Title | LiDAR Iris for Loop-Closure Detection |
| Authors | Ying Wang, Zezhou Sun, Jian Yang, Hui Kong |
| Abstract | In this paper, a global descriptor for a LiDAR point cloud, called LiDAR Iris, is proposed for fast and accurate loop-closure detection. A binary signature image can be obtained for each point cloud after a couple of LoG-Gabor filtering and thresholding operations on the LiDAR-Iris image representation. Given two point clouds, the similarity of them can be calculated as the hamming-distance of two corresponding binary signature images extracted from the two point clouds, respectively. Our LiDAR-Iris method can achieve a pose-invariant loop-closure detection with the Fourier transform of the LiDAR-Iris representation if assuming a 3D (x,y,yaw) pose space, although our method can generally be applied to a 6D pose space by re-aligning point cloud with an additional IMU sensor. Experimental results on five road-scene sequences demonstrate its excellent performance in loop-closure detection. |
| Tasks | Loop Closure Detection |
| Published | 2019-12-09 |
| URL | https://arxiv.org/abs/1912.03825v2 |
| https://arxiv.org/pdf/1912.03825v2.pdf | |
| PWC | https://paperswithcode.com/paper/lidar-iris-for-loop-closure-detection |
| Repo | |
| Framework | |
Tackling Multiple Ordinal Regression Problems: Sparse and Deep Multi-Task Learning Approaches
| Title | Tackling Multiple Ordinal Regression Problems: Sparse and Deep Multi-Task Learning Approaches |
| Authors | Lu Wang, Dongxiao Zhu |
| Abstract | Many real-world datasets are labeled with natural orders, i.e., ordinal labels. Ordinal regression is a method to predict ordinal labels that finds a wide range of applications in data-rich science domains, such as medical, social and economic sciences. Most existing approaches work well for a single ordinal regression task. However, they ignore the task relatedness when there are multiple related tasks. Multi-task learning (MTL) provides a framework to encode task relatedness, to bridge data from all tasks, and to simultaneously learn multiple related tasks to improve the generalization performance. Even though MTL methods have been extensively studied, there is barely existing work investigating MTL for data with ordinal labels. We tackle multiple ordinal regression problems via sparse and deep multi-task approaches, i.e., two regularized multi-task ordinal regression (RMTOR) models for small datasets and two deep neural networks based multi-task ordinal regression (DMTOR) models for large-scale datasets. The performance of the proposed multi-task ordinal regression models (MTOR) is demonstrated on three real-world medical datasets for multi-stage disease diagnosis. Our experimental results indicate that our proposed MTOR models markedly improve the prediction performance comparing with single-task learning (STL) ordinal regression models. |
| Tasks | Multi-Task Learning |
| Published | 2019-07-29 |
| URL | https://arxiv.org/abs/1907.12508v1 |
| https://arxiv.org/pdf/1907.12508v1.pdf | |
| PWC | https://paperswithcode.com/paper/tackling-multiple-ordinal-regression-problems |
| Repo | |
| Framework | |
Learning Local Feature Descriptor with Motion Attribute for Vision-based Localization
| Title | Learning Local Feature Descriptor with Motion Attribute for Vision-based Localization |
| Authors | Yafei Song, Di Zhu, Jia Li, Yonghong Tian, Mingyang Li |
| Abstract | In recent years, camera-based localization has been widely used for robotic applications, and most proposed algorithms rely on local features extracted from recorded images. For better performance, the features used for open-loop localization are required to be short-term globally static, and the ones used for re-localization or loop closure detection need to be long-term static. Therefore, the motion attribute of a local feature point could be exploited to improve localization performance, e.g., the feature points extracted from moving persons or vehicles can be excluded from these systems due to their unsteadiness. In this paper, we design a fully convolutional network (FCN), named MD-Net, to perform motion attribute estimation and feature description simultaneously. MD-Net has a shared backbone network to extract features from the input image and two network branches to complete each sub-task. With MD-Net, we can obtain the motion attribute while avoiding increasing much more computation. Experimental results demonstrate that the proposed method can learn distinct local feature descriptor along with motion attribute only using an FCN, by outperforming competing methods by a wide margin. We also show that the proposed algorithm can be integrated into a vision-based localization algorithm to improve estimation accuracy significantly. |
| Tasks | Loop Closure Detection |
| Published | 2019-08-03 |
| URL | https://arxiv.org/abs/1908.01180v2 |
| https://arxiv.org/pdf/1908.01180v2.pdf | |
| PWC | https://paperswithcode.com/paper/learning-local-feature-descriptor-with-motion |
| Repo | |
| Framework | |
Incorporating physical constraints in a deep probabilistic machine learning framework for coarse-graining dynamical systems
| Title | Incorporating physical constraints in a deep probabilistic machine learning framework for coarse-graining dynamical systems |
| Authors | Sebastian Kaltenbach, Phaedon-Stelios Koutsourelakis |
| Abstract | Data-based discovery of effective, coarse-grained (CG) models of high-dimensional dynamical systems presents a unique challenge in computational physics and particularly in the context of multiscale problems. The present paper offers a data-based, probablistic perspective that enables the quantification of predictive uncertainties. One of the outstanding problems has been the introduction of physical constraints in the probabilistic machine learning objectives. The primary utility of such constraints stems from the undisputed physical laws such as conservation of mass, energy etc that they represent. Furthermore and apart from leading to physically realistic predictions, they can significantly reduce the requisite amount of training data which for high-dimensional, multiscale systems are expensive to obtain (Small Data regime). We formulate the coarse-graining process by employing a probabilistic state-space model and account for the aforementioned equality constraints as virtual observables in the associated densities. We demonstrate how probabilistic inference tools can be employed to identify the coarse-grained variables in combination with deep neural nets and their evolution model without ever needing to define a fine-to-coarse (restriction) projection and without needing time-derivatives of state variables. Furthermore, it is capable of reconstructing the evolution of the full, fine-scale system and therefore the observables of interest need not be selected a priori. We demonstrate the efficacy of the proposed framework by applying it to systems of interacting particles and an image-series of a nonlinear pendulum. |
| Tasks | |
| Published | 2019-12-30 |
| URL | https://arxiv.org/abs/1912.12976v3 |
| https://arxiv.org/pdf/1912.12976v3.pdf | |
| PWC | https://paperswithcode.com/paper/incorporating-physical-constraints-in-a-deep |
| Repo | |
| Framework | |
Joint haze image synthesis and dehazing with mmd-vae losses
| Title | Joint haze image synthesis and dehazing with mmd-vae losses |
| Authors | Zongliang Li, Chi Zhang, Gaofeng Meng, Yuehu Liu |
| Abstract | Fog and haze are weathers with low visibility which are adversarial to the driving safety of intelligent vehicles equipped with optical sensors like cameras and LiDARs. Therefore image dehazing for perception enhancement and haze image synthesis for testing perception abilities are equivalently important in the development of such autonomous driving systems. From the view of image translation, these two problems are essentially dual with each other, which have the potentiality to be solved jointly. In this paper, we propose an unsupervised Image-to-Image Translation framework based on Variational Autoencoders (VAE) and Generative Adversarial Nets (GAN) to handle haze image synthesis and haze removal simultaneously. Since the KL divergence in the VAE objectives could not guarantee the optimal mapping under imbalanced and unpaired training samples with limited size, Maximum mean discrepancy (MMD) based VAE is utilized to ensure the translating consistency in both directions. The comprehensive analysis on both synthesis and dehazing performance of our method demonstrate the feasibility and practicability of the proposed method. |
| Tasks | Autonomous Driving, Image Dehazing, Image Generation, Image-to-Image Translation, Unsupervised Image-To-Image Translation |
| Published | 2019-05-15 |
| URL | https://arxiv.org/abs/1905.05947v1 |
| https://arxiv.org/pdf/1905.05947v1.pdf | |
| PWC | https://paperswithcode.com/paper/joint-haze-image-synthesis-and-dehazing-with |
| Repo | |
| Framework | |
Semi-supervised estimation of event temporal length for cell event detection
| Title | Semi-supervised estimation of event temporal length for cell event detection |
| Authors | Ha Tran Hong Phan, Ashnil Kumar, David Feng, Michael Fulham, Jinman Kim |
| Abstract | Cell event detection in cell videos is essential for monitoring of cellular behavior over extended time periods. Deep learning methods have shown great success in the detection of cell events for their ability to capture more discriminative features of cellular processes compared to traditional methods. In particular, convolutional long short-term memory (LSTM) models, which exploits the changes in cell events observable in video sequences, is the state-of-the-art for mitosis detection in cell videos. However, their limitations are the determination of the input sequence length, which is often performed empirically, and the need for a large annotated training dataset which is expensive to prepare. We propose a novel semi-supervised method of optimal length detection for mitosis detection with two key contributions: (i) an unsupervised step for learning the spatial and temporal locations of cells in their normal stage and approximating the distribution of temporal lengths of cell events and, (ii) a step of inferring, from that distribution, an optimal input sequence length and a minimal number of annotated frames for training a LSTM model for each particular video. We evaluated our method in detecting mitosis in densely packed stem cells in a phase-contrast microscopy videos. Our experimental data prove that increasing the input sequence length of LSTM can lead to a decrease in performance. Our results also show that by approximating the optimal input sequence length of the tested video, a model trained with only 18 annotated frames achieved F1-scores of 0.880-0.907, which are 10% higher than those of other published methods with a full set of 110 training annotated frames. |
| Tasks | Mitosis Detection |
| Published | 2019-09-22 |
| URL | https://arxiv.org/abs/1909.09946v1 |
| https://arxiv.org/pdf/1909.09946v1.pdf | |
| PWC | https://paperswithcode.com/paper/190909946 |
| Repo | |
| Framework | |
SeqLPD: Sequence Matching Enhanced Loop-Closure Detection Based on Large-Scale Point Cloud Description for Self-Driving Vehicles
| Title | SeqLPD: Sequence Matching Enhanced Loop-Closure Detection Based on Large-Scale Point Cloud Description for Self-Driving Vehicles |
| Authors | Zhe Liu, Chuanzhe Suo, Shunbo Zhou, Huanshu Wei, Yingtian Liu, Hesheng Wang, Yun-Hui Liu |
| Abstract | Place recognition and loop-closure detection are main challenges in the localization, mapping and navigation tasks of self-driving vehicles. In this paper, we solve the loop-closure detection problem by incorporating the deep-learning based point cloud description method and the coarse-to-fine sequence matching strategy. More specifically, we propose a deep neural network to extract a global descriptor from the original large-scale 3D point cloud, then based on which, a typical place analysis approach is presented to investigate the feature space distribution of the global descriptors and select several super keyframes. Finally, a coarse-to-fine strategy, which includes a super keyframe based coarse matching stage and a local sequence matching stage, is presented to ensure the loop-closure detection accuracy and real-time performance simultaneously. Thanks to the sequence matching operation, the proposed approach obtains an improvement against the existing deep-learning based methods. Experiment results on a self-driving vehicle validate the effectiveness of the proposed loop-closure detection algorithm. |
| Tasks | Loop Closure Detection |
| Published | 2019-04-30 |
| URL | https://arxiv.org/abs/1904.13030v2 |
| https://arxiv.org/pdf/1904.13030v2.pdf | |
| PWC | https://paperswithcode.com/paper/seqlpd-sequence-matching-enhanced-loop |
| Repo | |
| Framework | |
Learning to See the Wood for the Trees: Deep Laser Localization in Urban and Natural Environments on a CPU
| Title | Learning to See the Wood for the Trees: Deep Laser Localization in Urban and Natural Environments on a CPU |
| Authors | Georgi Tinchev, Adrian Penate-Sanchez, Maurice Fallon |
| Abstract | Localization in challenging, natural environments such as forests or woodlands is an important capability for many applications from guiding a robot navigating along a forest trail to monitoring vegetation growth with handheld sensors. In this work we explore laser-based localization in both urban and natural environments, which is suitable for online applications. We propose a deep learning approach capable of learning meaningful descriptors directly from 3D point clouds by comparing triplets (anchor, positive and negative examples). The approach learns a feature space representation for a set of segmented point clouds that are matched between a current and previous observations. Our learning method is tailored towards loop closure detection resulting in a small model which can be deployed using only a CPU. The proposed learning method would allow the full pipeline to run on robots with limited computational payload such as drones, quadrupeds or UGVs. |
| Tasks | Loop Closure Detection |
| Published | 2019-02-26 |
| URL | http://arxiv.org/abs/1902.10194v1 |
| http://arxiv.org/pdf/1902.10194v1.pdf | |
| PWC | https://paperswithcode.com/paper/learning-to-see-the-wood-for-the-trees-deep |
| Repo | |
| Framework | |
Diffusion $K$-means clustering on manifolds: provable exact recovery via semidefinite relaxations
| Title | Diffusion $K$-means clustering on manifolds: provable exact recovery via semidefinite relaxations |
| Authors | Xiaohui Chen, Yun Yang |
| Abstract | We introduce the {\it diffusion $K$-means} clustering method on Riemannian submanifolds, which maximizes the within-cluster connectedness based on the diffusion distance. The diffusion $K$-means constructs a random walk on the similarity graph with vertices as data points randomly sampled on the manifolds and edges as similarities given by a kernel that captures the local geometry of manifolds. The diffusion $K$-means is a multi-scale clustering tool that is suitable for data with non-linear and non-Euclidean geometric features in mixed dimensions. Given the number of clusters, we propose a polynomial-time convex relaxation algorithm via the semidefinite programming (SDP) to solve the diffusion $K$-means. In addition, we also propose a nuclear norm regularized SDP that is adaptive to the number of clusters. In both cases, we show that exact recovery of the SDPs for diffusion $K$-means can be achieved under suitable between-cluster separability and within-cluster connectedness of the submanifolds, which together quantify the hardness of the manifold clustering problem. We further propose the {\it localized diffusion $K$-means} by using the local adaptive bandwidth estimated from the nearest neighbors. We show that exact recovery of the localized diffusion $K$-means is fully adaptive to the local probability density and geometric structures of the underlying submanifolds. |
| Tasks | |
| Published | 2019-03-11 |
| URL | https://arxiv.org/abs/1903.04416v4 |
| https://arxiv.org/pdf/1903.04416v4.pdf | |
| PWC | https://paperswithcode.com/paper/diffusion-k-means-clustering-on-manifolds |
| Repo | |
| Framework | |
Forecasting, Causality, and Impulse Response with Neural Vector Autoregressions
| Title | Forecasting, Causality, and Impulse Response with Neural Vector Autoregressions |
| Authors | Kurt Izak Cabanilla, Kevin Thomas Go |
| Abstract | Incorporating nonlinearity is paramount to predicting the future states of a dynamical system, its response to shocks, and its underlying causal network. However, most existing methods for causality detection and impulse response, such as Vector Autoregression (VAR), assume linearity and are thus unable to capture the complexity. Here, we introduce a vector autoencoder nonlinear autoregression neural network (VANAR) capable of both automatic time series feature extraction for its inputs and functional form estimation. We evaluate VANAR in three ways: first in terms of pure forecast accuracy, second in terms of detecting the correct causality between variables, and lastly in terms of impulse response where we model trajectories given external shocks. These tests were performed on a simulated nonlinear chaotic system and an empirical system using Philippine macroeconomic data. Results show that VANAR significantly outperforms VAR in the forecast and causality tests. VANAR has consistently superior accuracy even over state of the art models such as SARIMA and TBATS. For the impulse response test, both models fail to predict the shocked trajectories of the nonlinear chaotic system. VANAR was robust in its ability to model a wide variety of dynamics, from chaotic, high noise, and low data environments to macroeconomic systems. |
| Tasks | Time Series |
| Published | 2019-03-22 |
| URL | https://arxiv.org/abs/1903.09395v3 |
| https://arxiv.org/pdf/1903.09395v3.pdf | |
| PWC | https://paperswithcode.com/paper/impulse-response-and-granger-causality-in |
| Repo | |
| Framework | |
Methodology for the Automated Metadata-Based Classification of Incriminating Digital Forensic Artefacts
| Title | Methodology for the Automated Metadata-Based Classification of Incriminating Digital Forensic Artefacts |
| Authors | Xiaoyu Du, Mark Scanlon |
| Abstract | The ever increasing volume of data in digital forensic investigation is one of the most discussed challenges in the field. Usually, most of the file artefacts on seized devices are not pertinent to the investigation. Manually retrieving suspicious files relevant to the investigation is akin to finding a needle in a haystack. In this paper, a methodology for the automatic prioritisation of suspicious file artefacts (i.e., file artefacts that are pertinent to the investigation) is proposed to reduce the manual analysis effort required. This methodology is designed to work in a human-in-the-loop fashion. In other words, it predicts/recommends that an artefact is likely to be suspicious rather than giving the final analysis result. A supervised machine learning approach is employed, which leverages the recorded results of previously processed cases. The process of features extraction, dataset generation, training and evaluation are presented in this paper. In addition, a toolkit for data extraction from disk images is outlined, which enables this method to be integrated with the conventional investigation process and work in an automated fashion. |
| Tasks | |
| Published | 2019-07-02 |
| URL | https://arxiv.org/abs/1907.01421v1 |
| https://arxiv.org/pdf/1907.01421v1.pdf | |
| PWC | https://paperswithcode.com/paper/methodology-for-the-automated-metadata-based |
| Repo | |
| Framework | |
