Paper Group ANR 1364
Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition. Applying Partial-ACO to Large-scale Vehicle Fleet Optimisation. pISTA-SENSE-ResNet for Parallel MRI Reconstruction. Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View. Infusing Learned Priors …
Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition
| Title | Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition |
| Authors | Matthew England, Dorian Florescu |
| Abstract | There has been recent interest in the use of machine learning (ML) approaches within mathematical software to make choices that impact on the computing performance without affecting the mathematical correctness of the result. We address the problem of selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm in Symbolic Computation. Prior work to apply ML on this problem implemented a Support Vector Machine (SVM) to select between three existing human-made heuristics, which did better than anyone heuristic alone. The present work extends to have ML select the variable ordering directly, and to try a wider variety of ML techniques. We experimented with the NLSAT dataset and the Regular Chains Library CAD function for Maple 2018. For each problem, the variable ordering leading to the shortest computing time was selected as the target class for ML. Features were generated from the polynomial input and used to train the following ML models: k-nearest neighbours (KNN) classifier, multi-layer perceptron (MLP), decision tree (DT) and SVM, as implemented in the Python scikit-learn package. We also compared these with the two leading human constructed heuristics for the problem: Brown’s heuristic and sotd. On this dataset all of the ML approaches outperformed the human made heuristics, some by a large margin. |
| Tasks | |
| Published | 2019-04-24 |
| URL | https://arxiv.org/abs/1904.11061v2 |
| https://arxiv.org/pdf/1904.11061v2.pdf | |
| PWC | https://paperswithcode.com/paper/comparing-machine-learning-models-to-choose |
| Repo | |
| Framework | |
Applying Partial-ACO to Large-scale Vehicle Fleet Optimisation
| Title | Applying Partial-ACO to Large-scale Vehicle Fleet Optimisation |
| Authors | Darren M. Chitty, Elizabeth Wanner, Rakhi Parmar, Peter R. Lewis |
| Abstract | Optimisation of fleets of commercial vehicles with regards scheduling tasks from various locations to vehicles can result in considerably lower fleet traversal times. This has significant benefits including reduced expenses for the company and more importantly, a reduction in the degree of road use and hence vehicular emissions. Exact optimisation methods fail to scale to real commercial problem instances, thus meta-heuristics are more suitable. Ant Colony Optimisation (ACO) generally provides good solutions on small to medium problem sizes. However, commercial fleet optimisation problems are typically large and complex, in which ACO fails to scale well. Partial-ACO is a new ACO variant designed to scale to larger problem instances. Therefore this paper investigates the application of Partial-ACO on the problem of fleet optimisation, demonstrating the capacity of Partial-ACO to successfully scale to larger problems. Indeed, for real-world fleet optimisation problems supplied by a Birmingham based company with up to 298 jobs and 32 vehicles, Partial-ACO can improve upon their fleet traversal times by over 44%. Moreover, Partial-ACO demonstrates its ability to scale with considerably improved results over standard ACO and competitive results against a Genetic Algorithm. |
| Tasks | |
| Published | 2019-04-16 |
| URL | http://arxiv.org/abs/1904.07636v1 |
| http://arxiv.org/pdf/1904.07636v1.pdf | |
| PWC | https://paperswithcode.com/paper/applying-partial-aco-to-large-scale-vehicle |
| Repo | |
| Framework | |
pISTA-SENSE-ResNet for Parallel MRI Reconstruction
| Title | pISTA-SENSE-ResNet for Parallel MRI Reconstruction |
| Authors | Tieyuan Lu, Xinlin Zhang, Yihui Huang, Yonggui Yang, Gang Guo, Lijun Bao, Feng Huang, Di Guo, Xiaobo Qu |
| Abstract | Magnetic resonance imaging has been widely applied in clinical diagnosis, however, is limited by its long data acquisition time. Although imaging can be accelerated by sparse sampling and parallel imaging, achieving promising reconstruction images with a fast reconstruction speed remains a challenge. Recently, deep learning approaches have attracted a lot of attention for its encouraging reconstruction results but without a proper interpretability. In this letter, to enable high-quality image reconstruction for the parallel magnetic resonance imaging, we design the network structure from the perspective of sparse iterative reconstruction and enhance it with the residual structure. The experimental results of a public knee dataset show that compared with the optimization-based method and the latest deep learning parallel imaging methods, the proposed network has less error in reconstruction and is more stable under different acceleration factors. |
| Tasks | Image Reconstruction |
| Published | 2019-09-24 |
| URL | https://arxiv.org/abs/1910.00650v1 |
| https://arxiv.org/pdf/1910.00650v1.pdf | |
| PWC | https://paperswithcode.com/paper/pista-sense-resnet-for-parallel-mri |
| Repo | |
| Framework | |
Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View
| Title | Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View |
| Authors | Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, Xu Sun |
| Abstract | Graph Neural Networks (GNNs) have achieved promising performance on a wide range of graph-based tasks. Despite their success, one severe limitation of GNNs is the over-smoothing issue (indistinguishable representations of nodes in different classes). In this work, we present a systematic and quantitative study on the over-smoothing issue of GNNs. First, we introduce two quantitative metrics, MAD and MADGap, to measure the smoothness and over-smoothness of the graph nodes representations, respectively. Then, we verify that smoothing is the nature of GNNs and the critical factor leading to over-smoothness is the low information-to-noise ratio of the message received by the nodes, which is partially determined by the graph topology. Finally, we propose two methods to alleviate the over-smoothing issue from the topological view: (1) MADReg which adds a MADGap-based regularizer to the training objective;(2) AdaGraph which optimizes the graph topology based on the model predictions. Extensive experiments on 7 widely-used graph datasets with 10 typical GNN models show that the two proposed methods are effective for relieving the over-smoothing issue, thus improving the performance of various GNN models. |
| Tasks | Node Classification |
| Published | 2019-09-07 |
| URL | https://arxiv.org/abs/1909.03211v2 |
| https://arxiv.org/pdf/1909.03211v2.pdf | |
| PWC | https://paperswithcode.com/paper/measuring-and-relieving-the-over-smoothing |
| Repo | |
| Framework | |
Infusing Learned Priors into Model-Based Multispectral Imaging
| Title | Infusing Learned Priors into Model-Based Multispectral Imaging |
| Authors | Jiaming Liu, Yu Sun, Ulugbek S. Kamilov |
| Abstract | We introduce a new algorithm for regularized reconstruction of multispectral (MS) images from noisy linear measurements. Unlike traditional approaches, the proposed algorithm regularizes the recovery problem by using a prior specified \emph{only} through a learned denoising function. More specifically, we propose a new accelerated gradient method (AGM) variant of regularization by denoising (RED) for model-based MS image reconstruction. The key ingredient of our approach is the three-dimensional (3D) deep neural net (DNN) denoiser that can fully leverage spationspectral correlations within MS images. Our results suggest the generalizability of our MS-RED algorithm, where a single trained DNN can be used to solve several different MS imaging problems. |
| Tasks | Denoising, Image Reconstruction |
| Published | 2019-09-20 |
| URL | https://arxiv.org/abs/1909.09313v1 |
| https://arxiv.org/pdf/1909.09313v1.pdf | |
| PWC | https://paperswithcode.com/paper/infusing-learned-priors-into-model-based |
| Repo | |
| Framework | |
Deep learning networks for selection of persistent scatterer pixels in multi-temporal SAR interferometric processing
| Title | Deep learning networks for selection of persistent scatterer pixels in multi-temporal SAR interferometric processing |
| Authors | Ashutosh Tiwari, Avadh Bihari Narayan, Onkar Dikshit |
| Abstract | In multi-temporal SAR interferometry (MT-InSAR), persistent scatterer (PS) pixels are used to estimate geophysical parameters, essentially deformation. Conventionally, PS pixels are selected on the basis of the estimated noise present in the spatially uncorrelated phase component along with look-angle error in a temporal interferometric stack. In this study, two deep learning architectures, namely convolutional neural network for interferometric semantic segmentation (CNN-ISS) and convolutional long short term memory network for interferometric semantic segmentation (CLSTM-ISS), based on learning spatial and spatio-temporal behaviour respectively, were proposed for selection of PS pixels. These networks were trained to relate the interferometric phase history to its classification into phase stable (PS) and phase unstable (non-PS) measurement pixels using ~10,000 real world interferometric images of different study sites containing man-made objects, forests, vegetation, uncropped land, water bodies, and areas affected by lengthening, foreshortening, layover and shadowing. The networks were trained using training labels obtained from the Stanford method for Persistent Scatterer Interferometry (StaMPS) algorithm. However, pixel selection results, when compared to a combination of R-index and a classified image of the test dataset, reveal that CLSTM-ISS estimates improved the classification of PS and non-PS pixels compared to those of StaMPS and CNN-ISS. The predicted results show that CLSTM-ISS reached an accuracy of 93.50%, higher than that of CNN-ISS (89.21%). CLSTM-ISS also improved the density of reliable PS pixels compared to StaMPS and CNN-ISS and outperformed StaMPS and other conventional MT-InSAR methods in terms of computational efficiency. |
| Tasks | Semantic Segmentation |
| Published | 2019-09-04 |
| URL | https://arxiv.org/abs/1909.01868v3 |
| https://arxiv.org/pdf/1909.01868v3.pdf | |
| PWC | https://paperswithcode.com/paper/deep-learning-networks-for-selection-of |
| Repo | |
| Framework | |
Grammar-based Neural Text-to-SQL Generation
| Title | Grammar-based Neural Text-to-SQL Generation |
| Authors | Kevin Lin, Ben Bogin, Mark Neumann, Jonathan Berant, Matt Gardner |
| Abstract | The sequence-to-sequence paradigm employed by neural text-to-SQL models typically performs token-level decoding and does not consider generating SQL hierarchically from a grammar. Grammar-based decoding has shown significant improvements for other semantic parsing tasks, but SQL and other general programming languages have complexities not present in logical formalisms that make writing hierarchical grammars difficult. We introduce techniques to handle these complexities, showing how to construct a schema-dependent grammar with minimal over-generation. We analyze these techniques on ATIS and Spider, two challenging text-to-SQL datasets, demonstrating that they yield 14–18% relative reductions in error. |
| Tasks | Semantic Parsing, Text-To-Sql |
| Published | 2019-05-30 |
| URL | https://arxiv.org/abs/1905.13326v1 |
| https://arxiv.org/pdf/1905.13326v1.pdf | |
| PWC | https://paperswithcode.com/paper/grammar-based-neural-text-to-sql-generation |
| Repo | |
| Framework | |
Gravity as a Reference for Estimating a Person’s Height from Video
| Title | Gravity as a Reference for Estimating a Person’s Height from Video |
| Authors | Didier Bieler, Semih Günel, Pascal Fua, Helge Rhodin |
| Abstract | Estimating the metric height of a person from monocular imagery without additional assumptions is ill-posed. Existing solutions either require manual calibration of ground plane and camera geometry, special cameras, or reference objects of known size. We focus on motion cues and exploit gravity on earth as an omnipresent reference ‘object’ to translate acceleration, and subsequently height, measured in image-pixels to values in meters. We require videos of motion as input, where gravity is the only external force. This limitation is different to those of existing solutions that recover a person’s height and, therefore, our method opens up new application fields. We show theoretically and empirically that a simple motion trajectory analysis suffices to translate from pixel measurements to the person’s metric height, reaching a MAE of up to 3.9 cm on jumping motions, and that this works without camera and ground plane calibration. |
| Tasks | Calibration |
| Published | 2019-09-05 |
| URL | https://arxiv.org/abs/1909.02211v2 |
| https://arxiv.org/pdf/1909.02211v2.pdf | |
| PWC | https://paperswithcode.com/paper/gravity-as-a-reference-for-estimating-a |
| Repo | |
| Framework | |
Distributed and Consistent Multi-Image Feature Matching via QuickMatch
| Title | Distributed and Consistent Multi-Image Feature Matching via QuickMatch |
| Authors | Zachary Serlin, Guang Yang, Brandon Sookraj, Calin Belta, Roberto Tron |
| Abstract | In this work we consider the multi-image object matching problem, extend a centralized solution of the problem to a distributed solution, and present an experimental application of the centralized solution. Multi-image feature matching is a keystone of many applications, including simultaneous localization and mapping, homography, object detection, and structure from motion. We first review the QuickMatch algorithm for multi-image feature matching. We then present a scheme for distributing sets of features across computational units (agents) that largely preserves feature match quality and minimizes communication between agents (avoiding, in particular, the need of flooding all data to all agents). Finally, we show how QuickMatch performs on an object matching test with low quality images. The centralized QuickMatch algorithm is compared to other standard matching algorithms, while the Distributed QuickMatch algorithm is compared to the centralized algorithm in terms of preservation of match consistency. The presented experiment shows that QuickMatch matches features across a large number of images and features in larger numbers and more accurately than standard techniques. |
| Tasks | |
| Published | 2019-10-29 |
| URL | https://arxiv.org/abs/1910.13317v1 |
| https://arxiv.org/pdf/1910.13317v1.pdf | |
| PWC | https://paperswithcode.com/paper/distributed-and-consistent-multi-image |
| Repo | |
| Framework | |
Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
| Title | Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems |
| Authors | Qiuwei Li, Zhihui Zhu, Gongguo Tang, Michael B. Wakin |
| Abstract | The (global) Lipschitz smoothness condition is crucial in establishing the convergence theory for most optimization methods. Unfortunately, most machine learning and signal processing problems are not Lipschitz smooth. This motivates us to generalize the concept of Lipschitz smoothness condition to the relative smoothness condition, which is satisfied by any finite-order polynomial objective function. Further, this work develops new Bregman-divergence based algorithms that are guaranteed to converge to a second-order stationary point for any relatively smooth problem. In addition, the proposed optimization methods cover both the proximal alternating minimization and the proximal alternating linearized minimization when we specialize the Bregman divergence to the Euclidian distance. Therefore, this work not only develops guaranteed optimization methods for non-Lipschitz smooth problems but also solves an open problem of showing the second-order convergence guarantees for these alternating minimization methods. |
| Tasks | |
| Published | 2019-04-22 |
| URL | http://arxiv.org/abs/1904.09712v1 |
| http://arxiv.org/pdf/1904.09712v1.pdf | |
| PWC | https://paperswithcode.com/paper/provable-bregman-divergence-based-methods-for |
| Repo | |
| Framework | |
ConCare: Personalized Clinical Feature Embedding via Capturing the Healthcare Context
| Title | ConCare: Personalized Clinical Feature Embedding via Capturing the Healthcare Context |
| Authors | Liantao Ma, Chaohe Zhang, Yasha Wang, Wenjie Ruan, Jiantao Wang, Wen Tang, Xinyu Ma, Xin Gao, Junyi Gao |
| Abstract | Predicting the patient’s clinical outcome from the historical electronic medical records (EMR) is a fundamental research problem in medical informatics. Most deep learning-based solutions for EMR analysis concentrate on learning the clinical visit embedding and exploring the relations between visits. Although those works have shown superior performances in healthcare prediction, they fail to explore the personal characteristics during the clinical visits thoroughly. Moreover, existing works usually assume that the more recent record weights more in the prediction, but this assumption is not suitable for all conditions. In this paper, we propose ConCare to handle the irregular EMR data and extract feature interrelationship to perform individualized healthcare prediction. Our solution can embed the feature sequences separately by modeling the time-aware distribution. ConCare further improves the multi-head self-attention via the cross-head decorrelation, so that the inter-dependencies among dynamic features and static baseline information can be effectively captured to form the personal health context. Experimental results on two real-world EMR datasets demonstrate the effectiveness of ConCare. The medical findings extracted by ConCare are also empirically confirmed by human experts and medical literature. |
| Tasks | |
| Published | 2019-11-27 |
| URL | https://arxiv.org/abs/1911.12216v1 |
| https://arxiv.org/pdf/1911.12216v1.pdf | |
| PWC | https://paperswithcode.com/paper/concare-personalized-clinical-feature |
| Repo | |
| Framework | |
Do Image Classifiers Generalize Across Time?
| Title | Do Image Classifiers Generalize Across Time? |
| Authors | Vaishaal Shankar, Achal Dave, Rebecca Roelofs, Deva Ramanan, Benjamin Recht, Ludwig Schmidt |
| Abstract | We study the robustness of image classifiers to temporal perturbations derived from videos. As part of this study, we construct two datasets, ImageNet-Vid-Robust and YTBB-Robust , containing a total 57,897 images grouped into 3,139 sets of perceptually similar images. Our datasets were derived from ImageNet-Vid and Youtube-BB respectively and thoroughly re-annotated by human experts for image similarity. We evaluate a diverse array of classifiers pre-trained on ImageNet and show a median classification accuracy drop of 16 and 10 on our two datasets. Additionally, we evaluate three detection models and show that natural perturbations induce both classification as well as localization errors, leading to a median drop in detection mAP of 14 points. Our analysis demonstrates that perturbations occurring naturally in videos pose a substantial and realistic challenge to deploying convolutional neural networks in environments that require both reliable and low-latency predictions |
| Tasks | Object Detection, Video Object Detection |
| Published | 2019-06-05 |
| URL | https://arxiv.org/abs/1906.02168v3 |
| https://arxiv.org/pdf/1906.02168v3.pdf | |
| PWC | https://paperswithcode.com/paper/a-systematic-framework-for-natural |
| Repo | |
| Framework | |
Quantity doesn’t buy quality syntax with neural language models
| Title | Quantity doesn’t buy quality syntax with neural language models |
| Authors | Marten van Schijndel, Aaron Mueller, Tal Linzen |
| Abstract | Recurrent neural networks can learn to predict upcoming words remarkably well on average; in syntactically complex contexts, however, they often assign unexpectedly high probabilities to ungrammatical words. We investigate to what extent these shortcomings can be mitigated by increasing the size of the network and the corpus on which it is trained. We find that gains from increasing network size are minimal beyond a certain point. Likewise, expanding the training corpus yields diminishing returns; we estimate that the training corpus would need to be unrealistically large for the models to match human performance. A comparison to GPT and BERT, Transformer-based models trained on billions of words, reveals that these models perform even more poorly than our LSTMs in some constructions. Our results make the case for more data efficient architectures. |
| Tasks | |
| Published | 2019-08-31 |
| URL | https://arxiv.org/abs/1909.00111v1 |
| https://arxiv.org/pdf/1909.00111v1.pdf | |
| PWC | https://paperswithcode.com/paper/quantity-doesnt-buy-quality-syntax-with |
| Repo | |
| Framework | |
Generating Local Search Neighborhood with Synthesized Logic Programs
| Title | Generating Local Search Neighborhood with Synthesized Logic Programs |
| Authors | Mateusz Ślażyński, Salvador Abreu, Grzegorz J. Nalepa |
| Abstract | Local Search meta-heuristics have been proven a viable approach to solve difficult optimization problems. Their performance depends strongly on the search space landscape, as defined by a cost function and the selected neighborhood operators. In this paper we present a logic programming based framework, named Noodle, designed to generate bespoke Local Search neighborhoods tailored to specific discrete optimization problems. The proposed system consists of a domain specific language, which is inspired by logic programming, as well as a genetic programming solver, based on the grammar evolution algorithm. We complement the description with a preliminary experimental evaluation, where we synthesize efficient neighborhood operators for the traveling salesman problem, some of which reproduce well-known results. |
| Tasks | |
| Published | 2019-09-18 |
| URL | https://arxiv.org/abs/1909.08242v1 |
| https://arxiv.org/pdf/1909.08242v1.pdf | |
| PWC | https://paperswithcode.com/paper/generating-local-search-neighborhood-with |
| Repo | |
| Framework | |
Deep Ensembles: A Loss Landscape Perspective
| Title | Deep Ensembles: A Loss Landscape Perspective |
| Authors | Stanislav Fort, Huiyi Hu, Balaji Lakshminarayanan |
| Abstract | Deep ensembles have been empirically shown to be a promising approach for improving accuracy, uncertainty and out-of-distribution robustness of deep learning models. While deep ensembles were theoretically motivated by the bootstrap, non-bootstrap ensembles trained with just random initialization also perform well in practice, which suggests that there could be other explanations for why deep ensembles work well. Bayesian neural networks, which learn distributions over the parameters of the network, are theoretically well-motivated by Bayesian principles, but do not perform as well as deep ensembles in practice, particularly under dataset shift. One possible explanation for this gap between theory and practice is that popular scalable approximate Bayesian methods tend to focus on a single mode, whereas deep ensembles tend to explore diverse modes in function space. We investigate this hypothesis by building on recent work on understanding the loss landscape of neural networks and adding our own exploration to measure the similarity of functions in the space of predictions. Our results show that random initializations explore entirely different modes, while functions along an optimization trajectory or sampled from the subspace thereof cluster within a single mode predictions-wise, while often deviating significantly in the weight space. We demonstrate that while low-loss connectors between modes exist, they are not connected in the space of predictions. Developing the concept of the diversity–accuracy plane, we show that the decorrelation power of random initializations is unmatched by popular subspace sampling methods. |
| Tasks | |
| Published | 2019-12-05 |
| URL | https://arxiv.org/abs/1912.02757v1 |
| https://arxiv.org/pdf/1912.02757v1.pdf | |
| PWC | https://paperswithcode.com/paper/deep-ensembles-a-loss-landscape-perspective-1 |
| Repo | |
| Framework | |
