April 2, 2020

# Paper Group ANR 308

word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data. Simulation of Skin Stretching around the Forehead Wrinkles in Rhytidectomy. Artificial Intelligence Assistance Significantly Improves Gleason Grading of Prostate Biopsies by Pathologists. Gradient Boosting Neural Networks: GrowNet. Satisfiability and Que …

#### word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data

Title word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data
Authors Martin Grohe
Abstract Vector representations of graphs and relational structures, whether hand-crafted feature vectors or learned representations, enable us to apply standard data analysis and machine learning techniques to the structures. A wide range of methods for generating such embeddings have been studied in the machine learning and knowledge representation literature. However, vector embeddings have received relatively little attention from a theoretical point of view. Starting with a survey of embedding techniques that have been used in practice, in this paper we propose two theoretical approaches that we see as central for understanding the foundations of vector embeddings. We draw connections between the various approaches and suggest directions for future research.
Published 2020-03-27
URL https://arxiv.org/abs/2003.12590v1
PDF https://arxiv.org/pdf/2003.12590v1.pdf
PWC https://paperswithcode.com/paper/word2vec-node2vec-graph2vec-x2vec-towards-a
Repo
Framework

#### Simulation of Skin Stretching around the Forehead Wrinkles in Rhytidectomy

Title Simulation of Skin Stretching around the Forehead Wrinkles in Rhytidectomy
Authors Ping Zhou, Shuo Huang, Qiang Chen, Siyuan He, Guochao Cai
Abstract Objective: Skin stretching around the forehead wrinkles is an important method in rhytidectomy. Proper parameters are required to evaluate the surgical effect. In this paper, a simulation method was proposed to obtain the parameters. Methods: Three-dimensional point cloud data with a resolution of 50 {\mu}m were employed. First, a smooth supporting contour under the wrinkled forehead was generated via b-spline interpolation and extrapolation to constrain the deformation of the wrinkled zone. Then, based on the vector formed intrinsic finite element (VFIFE) algorithm, the simulation was implemented in Matlab for the deformation of wrinkled forehead skin in the stretching process. Finally, the stress distribution and the residual wrinkles of forehead skin were employed to evaluate the surgical effect. Results: Although the residual wrinkles are similar when forehead wrinkles are finitely stretched, their stress distribution changes greatly. This indicates that the stress distribution in the skin is effective to evaluate the surgical effect, and the forehead wrinkles are easily to be overstretched, which may lead to potential skin injuries. Conclusion: The simulation method can predict stress distribution and residual wrinkles after forehead wrinkle stretching surgery, which can be potentially used to control the surgical process and further reduce risks of skin injury.
Published 2020-01-01
URL https://arxiv.org/abs/2001.00149v1
PDF https://arxiv.org/pdf/2001.00149v1.pdf
PWC https://paperswithcode.com/paper/simulation-of-skin-stretching-around-the
Repo
Framework

#### Artificial Intelligence Assistance Significantly Improves Gleason Grading of Prostate Biopsies by Pathologists

Title Artificial Intelligence Assistance Significantly Improves Gleason Grading of Prostate Biopsies by Pathologists
Authors Wouter Bulten, Maschenka Balkenhol, Jean-Joël Awoumou Belinga, Américo Brilhante, Aslı Çakır, Xavier Farré, Katerina Geronatsiou, Vincent Molinié, Guilherme Pereira, Paromita Roy, Günter Saile, Paulo Salles, Ewout Schaafsma, Joëlle Tschui, Anne-Marie Vos, Hester van Boven, Robert Vink, Jeroen van der Laak, Christina Hulsbergen-van de Kaa, Geert Litjens
Abstract While the Gleason score is the most important prognostic marker for prostate cancer patients, it suffers from significant observer variability. Artificial Intelligence (AI) systems, based on deep learning, have proven to achieve pathologist-level performance at Gleason grading. However, the performance of such systems can degrade in the presence of artifacts, foreign tissue, or other anomalies. Pathologists integrating their expertise with feedback from an AI system could result in a synergy that outperforms both the individual pathologist and the system. Despite the hype around AI assistance, existing literature on this topic within the pathology domain is limited. We investigated the value of AI assistance for grading prostate biopsies. A panel of fourteen observers graded 160 biopsies with and without AI assistance. Using AI, the agreement of the panel with an expert reference standard significantly increased (quadratically weighted Cohen’s kappa, 0.799 vs 0.872; p=0.018). Our results show the added value of AI systems for Gleason grading, but more importantly, show the benefits of pathologist-AI synergy.
Published 2020-02-11
URL https://arxiv.org/abs/2002.04500v1
PDF https://arxiv.org/pdf/2002.04500v1.pdf
PWC https://paperswithcode.com/paper/artificial-intelligence-assistance
Repo
Framework

#### Gradient Boosting Neural Networks: GrowNet

Title Gradient Boosting Neural Networks: GrowNet
Authors Sarkhan Badirli, Xuanqing Liu, Zhengming Xing, Avradeep Bhowmik, Sathiya S. Keerthi
Abstract A novel gradient boosting framework is proposed where shallow neural networks are employed as “weak learners”. General loss functions are considered under this unified framework with specific examples presented for classification, regression and learning to rank. A fully corrective step is incorporated to remedy the pitfall of greedy function approximation of classic gradient boosting decision tree. The proposed model rendered state-of-the-art results in all three tasks on multiple datasets. An ablation study is performed to shed light on the effect of each model components and model hyperparameters.
Published 2020-02-19
URL https://arxiv.org/abs/2002.07971v1
PDF https://arxiv.org/pdf/2002.07971v1.pdf
Repo
Framework

#### Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints

Title Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints
Authors Franz Baader, Bartosz Bednarczyk, Sebastian Rudolph
Abstract We introduce and investigate the expressive description logic (DL) ALCSCC++, in which the global and local cardinality constraints introduced in previous papers can be mixed. On the one hand, we prove that this does not increase the complexity of satisfiability checking and other standard inference problems. On the other hand, the satisfiability problem becomes undecidable if inverse roles are added to the languages. In addition, even without inverse roles, conjunctive query entailment in this DL turns out to be undecidable. We prove that decidability of querying can be regained if global and local constraints are not mixed and the global constraints are appropriately restricted. The latter result is based on a locally-acyclic model construction, and it reduces query entailment to ABox consistency in the restricted setting, i.e., to ABox consistency w.r.t. restricted cardinality constraints in ALCSCC, for which we can show an ExpTime upper bound.
Published 2020-02-14
URL https://arxiv.org/abs/2002.06072v1
PDF https://arxiv.org/pdf/2002.06072v1.pdf
Repo
Framework

#### Common Information Components Analysis

Title Common Information Components Analysis
Authors Michael Gastpar, Erixhen Sula
Abstract We give an information-theoretic interpretation of Canonical Correlation Analysis (CCA) via (relaxed) Wyner’s common information. CCA permits to extract from two high-dimensional data sets low-dimensional descriptions (features) that capture the commonalities between the data sets, using a framework of correlations and linear transforms. Our interpretation first extracts the common information up to a pre-selected resolution level, and then projects this back onto each of the data sets. In the case of Gaussian statistics, this procedure precisely reduces to CCA, where the resolution level specifies the number of CCA components that are extracted. This also suggests a novel algorithm, Common Information Components Analysis (CICA), with several desirable features, including a natural extension to beyond just two data sets.
Published 2020-02-03
URL https://arxiv.org/abs/2002.00779v3
PDF https://arxiv.org/pdf/2002.00779v3.pdf
PWC https://paperswithcode.com/paper/common-information-components-analysis
Repo
Framework

#### Natural Language QA Approaches using Reasoning with External Knowledge

Title Natural Language QA Approaches using Reasoning with External Knowledge
Authors Chitta Baral, Pratyay Banerjee, Kuntal Kumar Pal, Arindam Mitra
Abstract Question answering (QA) in natural language (NL) has been an important aspect of AI from its early days. Winograd’s councilmen'' example in his 1972 paper and McCarthy's Mr. Hug example of 1976 highlights the role of external knowledge in NL understanding. While Machine Learning has been the go-to approach in NL processing as well as NL question answering (NLQA) for the last 30 years, recently there has been an increasingly emphasized thread on NLQA where external knowledge plays an important role. The challenges inspired by Winograd's councilmen example, and recent developments such as the Rebooting AI book, various NLQA datasets, research on knowledge acquisition in the NLQA context, and their use in various NLQA models have brought the issue of NLQA using reasoning’’ with external knowledge to the forefront. In this paper, we present a survey of the recent work on them. We believe our survey will help establish a bridge between multiple fields of AI, especially between (a) the traditional fields of knowledge representation and reasoning and (b) the field of NL understanding and NLQA.
Published 2020-03-06
URL https://arxiv.org/abs/2003.03446v1
PDF https://arxiv.org/pdf/2003.03446v1.pdf
PWC https://paperswithcode.com/paper/natural-language-qa-approaches-using
Repo
Framework

#### Clustering Binary Data by Application of Combinatorial Optimization Heuristics

Title Clustering Binary Data by Application of Combinatorial Optimization Heuristics
Authors Javier Trejos-Zelaya, Luis Eduardo Amaya-Briceño, Alejandra Jiménez-Romero, Alex Murillo-Fernández, Eduardo Piza-Volio, Mario Villalobos-Arias
Abstract We study clustering methods for binary data, first defining aggregation criteria that measure the compactness of clusters. Five new and original methods are introduced, using neighborhoods and population behavior combinatorial optimization metaheuristics: first ones are simulated annealing, threshold accepting and tabu search, and the others are a genetic algorithm and ant colony optimization. The methods are implemented, performing the proper calibration of parameters in the case of heuristics, to ensure good results. From a set of 16 data tables generated by a quasi-Monte Carlo experiment, a comparison is performed for one of the aggregations using L1 dissimilarity, with hierarchical clustering, and a version of k-means: partitioning around medoids or PAM. Simulated annealing perform very well, especially compared to classical methods.
Published 2020-01-06
URL https://arxiv.org/abs/2001.01809v1
PDF https://arxiv.org/pdf/2001.01809v1.pdf
PWC https://paperswithcode.com/paper/clustering-binary-data-by-application-of
Repo
Framework

#### A New Unified Deep Learning Approach with Decomposition-Reconstruction-Ensemble Framework for Time Series Forecasting

Title A New Unified Deep Learning Approach with Decomposition-Reconstruction-Ensemble Framework for Time Series Forecasting
Authors Guowei Zhang, Tao Ren, Yifan Yang
Abstract A new variational mode decomposition (VMD) based deep learning approach is proposed in this paper for time series forecasting problem. Firstly, VMD is adopted to decompose the original time series into several sub-signals. Then, a convolutional neural network (CNN) is applied to learn the reconstruction patterns on the decomposed sub-signals to obtain several reconstructed sub-signals. Finally, a long short term memory (LSTM) network is employed to forecast the time series with the decomposed sub-signals and the reconstructed sub-signals as inputs. The proposed VMD-CNN-LSTM approach is originated from the decomposition-reconstruction-ensemble framework, and innovated by embedding the reconstruction, single forecasting, and ensemble steps in a unified deep learning approach. To verify the forecasting performance of the proposed approach, four typical time series datasets are introduced for empirical analysis. The empirical results demonstrate that the proposed approach outperforms consistently the benchmark approaches in terms of forecasting accuracy, and also indicate that the reconstructed sub-signals obtained by CNN is of importance for further improving the forecasting performance.
Tasks Time Series, Time Series Forecasting
Published 2020-02-22
URL https://arxiv.org/abs/2002.09695v1
PDF https://arxiv.org/pdf/2002.09695v1.pdf
PWC https://paperswithcode.com/paper/a-new-unified-deep-learning-approach-with
Repo
Framework

#### Bandit optimisation of functions in the Matérn kernel RKHS

Title Bandit optimisation of functions in the Matérn kernel RKHS
Authors David Janz, David R. Burt, Javier González
Abstract We consider the problem of optimising functions in the reproducing kernel Hilbert space (RKHS) of a Mat'ern kernel with smoothness parameter $\nu$ over the domain $[0,1]^d$ under noisy bandit feedback. Our contribution, the $\pi$-GP-UCB algorithm, is the first practical approach with guaranteed sublinear regret for all $\nu>1$ and $d \geq 1$. Empirical validation suggests better performance and drastically improved computational scalablity compared with its predecessor, Improved GP-UCB.
Published 2020-01-28
URL https://arxiv.org/abs/2001.10396v2
PDF https://arxiv.org/pdf/2001.10396v2.pdf
PWC https://paperswithcode.com/paper/bandit-optimisation-of-functions-in-the
Repo
Framework

#### Learning fine-grained search space pruning and heuristics for combinatorial optimization

Title Learning fine-grained search space pruning and heuristics for combinatorial optimization
Authors Juho Lauri, Sourav Dutta, Marco Grassia, Deepak Ajwani
Abstract Combinatorial optimization problems arise in a wide range of applications from diverse domains. Many of these problems are NP-hard and designing efficient heuristics for them requires considerable time and experimentation. On the other hand, the number of optimization problems in the industry continues to grow. In recent years, machine learning techniques have been explored to address this gap. We propose a framework for leveraging machine learning techniques to scale-up exact combinatorial optimization algorithms. In contrast to the existing approaches based on deep-learning, reinforcement learning and restricted Boltzmann machines that attempt to directly learn the output of the optimization problem from its input (with limited success), our framework learns the relatively simpler task of pruning the elements in order to reduce the size of the problem instances. In addition, our framework uses only interpretable learning models based on intuitive features and thus the learning process provides deeper insights into the optimization problem and the instance class, that can be used for designing better heuristics. For the classical maximum clique enumeration problem, we show that our framework can prune a large fraction of the input graph (around 99 % of nodes in case of sparse graphs) and still detect almost all of the maximum cliques. This results in several fold speedups of state-of-the-art algorithms. Furthermore, the model used in our framework highlights that the chi-squared value of neighborhood degree has a statistically significant correlation with the presence of a node in a maximum clique, particularly in dense graphs which constitute a significant challenge for modern solvers. We leverage this insight to design a novel heuristic for this problem outperforming the state-of-the-art. Our heuristic is also of independent interest for maximum clique detection and enumeration.
Published 2020-01-05
URL https://arxiv.org/abs/2001.01230v1
PDF https://arxiv.org/pdf/2001.01230v1.pdf
PWC https://paperswithcode.com/paper/learning-fine-grained-search-space-pruning
Repo
Framework

#### A Probability Density Theory for Spin-Glass Systems

Title A Probability Density Theory for Spin-Glass Systems
Authors Gavin S. Hartnett, Masoud Mohseni
Abstract Spin-glass systems are universal models for representing many-body phenomena in statistical physics and computer science. High quality solutions of NP-hard combinatorial optimization problems can be encoded into low energy states of spin-glass systems. In general, evaluating the relevant physical and computational properties of such models is difficult due to critical slowing down near a phase transition. Ideally, one could use recent advances in deep learning for characterizing the low-energy properties of these complex systems. Unfortunately, many of the most promising machine learning approaches are only valid for distributions over continuous variables and thus cannot be directly applied to discrete spin-glass models. To this end, we develop a continuous probability density theory for spin-glass systems with arbitrary dimensions, interactions, and local fields. We show how our formulation geometrically encodes key physical and computational properties of the spin-glass in an instance-wise fashion without the need for quenched disorder averaging. We show that our approach is beyond the mean-field theory and identify a transition from a convex to non-convex energy landscape as the temperature is lowered past a critical temperature. We apply our formalism to a number of spin-glass models including the Sherrington-Kirkpatrick (SK) model, spins on random Erd\H{o}s-R'enyi graphs, and random restricted Boltzmann machines.
Published 2020-01-03
URL https://arxiv.org/abs/2001.00927v2
PDF https://arxiv.org/pdf/2001.00927v2.pdf
PWC https://paperswithcode.com/paper/a-probability-density-theory-for-spin-glass
Repo
Framework

#### Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization

Title Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization
Authors Quoc Tran-Dinh, Nhan H. Pham, Lam M. Nguyen
Abstract We develop two new stochastic Gauss-Newton algorithms for solving a class of stochastic nonconvex compositional optimization problems frequently arising in practice. We consider both the expectation and finite-sum settings under standard assumptions. We use both classical stochastic and SARAH estimators for approximating function values and Jacobians. In the expectation case, we establish $\mathcal{O}(\varepsilon^{-2})$ iteration complexity to achieve a stationary point in expectation and estimate the total number of stochastic oracle calls for both function values and its Jacobian, where $\varepsilon$ is a desired accuracy. In the finite sum case, we also estimate the same iteration complexity and the total oracle calls with high probability. To our best knowledge, this is the first time such global stochastic oracle complexity is established for stochastic Gauss-Newton methods. We illustrate our theoretical results via numerical examples on both synthetic and real datasets.
Published 2020-02-17
URL https://arxiv.org/abs/2002.07290v1
PDF https://arxiv.org/pdf/2002.07290v1.pdf
PWC https://paperswithcode.com/paper/stochastic-gauss-newton-algorithms-for
Repo
Framework

#### Total3DUnderstanding: Joint Layout, Object Pose and Mesh Reconstruction for Indoor Scenes from a Single Image

Title Total3DUnderstanding: Joint Layout, Object Pose and Mesh Reconstruction for Indoor Scenes from a Single Image
Authors Yinyu Nie, Xiaoguang Han, Shihui Guo, Yujian Zheng, Jian Chang, Jian Jun Zhang
Abstract Semantic reconstruction of indoor scenes refers to both scene understanding and object reconstruction. Existing works either address one part of this problem or focus on independent objects. In this paper, we bridge the gap between understanding and reconstruction, and propose an end-to-end solution to jointly reconstruct room layout, object bounding boxes and meshes from a single image. Instead of separately resolving scene understanding and object reconstruction, our method builds upon a holistic scene context and proposes a coarse-to-fine hierarchy with three components: 1. room layout with camera pose; 2. 3D object bounding boxes; 3. object meshes. We argue that understanding the context of each component can assist the task of parsing the others, which enables joint understanding and reconstruction. The experiments on the SUN RGB-D and Pix3D datasets demonstrate that our method consistently outperforms existing methods in indoor layout estimation, 3D object detection and mesh reconstruction.
Tasks 3D Object Detection, Object Detection, Object Reconstruction, Scene Understanding
Published 2020-02-27
URL https://arxiv.org/abs/2002.12212v1
PDF https://arxiv.org/pdf/2002.12212v1.pdf
PWC https://paperswithcode.com/paper/total3dunderstanding-joint-layout-object-pose
Repo
Framework

#### Compressive Learning of Generative Networks

Title Compressive Learning of Generative Networks
Authors Vincent Schellekens, Laurent Jacques
Abstract Generative networks implicitly approximate complex densities from their sampling with impressive accuracy. However, because of the enormous scale of modern datasets, this training process is often computationally expensive. We cast generative network training into the recent framework of compressive learning: we reduce the computational burden of large-scale datasets by first harshly compressing them in a single pass as a single sketch vector. We then propose a cost function, which approximates the Maximum Mean Discrepancy metric, but requires only this sketch, which makes it time- and memory-efficient to optimize.