July 27, 2019

2782 words 14 mins read

Paper Group ANR 675

Distributed methods for synchronization of orthogonal matrices over graphs. Scalable Dense Monocular Surface Reconstruction. DGCNN: Disordered Graph Convolutional Neural Network Based on the Gaussian Mixture Model. An entity-driven recursive neural network model for chinese discourse coherence modeling. Machine Learning and the Future of Realism. M …

Distributed methods for synchronization of orthogonal matrices over graphs


Title	Distributed methods for synchronization of orthogonal matrices over graphs
Authors	Johan Thunberg, Florian Bernard, Jorge Goncalves
Abstract	This paper addresses the problem of synchronizing orthogonal matrices over directed graphs. For synchronized transformations (or matrices), composite transformations over loops equal the identity. We formulate the synchronization problem as a least-squares optimization problem with nonlinear constraints. The synchronization problem appears as one of the key components in applications ranging from 3D-localization to image registration. The main contributions of this work can be summarized as the introduction of two novel algorithms; one for symmetric graphs and one for graphs that are possibly asymmetric. Under general conditions, the former has guaranteed convergence to the solution of a spectral relaxation to the synchronization problem. The latter is stable for small step sizes when the graph is quasi-strongly connected. The proposed methods are verified in numerical simulations.
Tasks	Image Registration
Published	2017-01-25
URL	http://arxiv.org/abs/1701.07248v3
PDF	http://arxiv.org/pdf/1701.07248v3.pdf
PWC	https://paperswithcode.com/paper/distributed-methods-for-synchronization-of
Repo
Framework

Scalable Dense Monocular Surface Reconstruction


Title	Scalable Dense Monocular Surface Reconstruction
Authors	Mohammad Dawud Ansari, Vladislav Golyanik, Didier Stricker
Abstract	This paper reports on a novel template-free monocular non-rigid surface reconstruction approach. Existing techniques using motion and deformation cues rely on multiple prior assumptions, are often computationally expensive and do not perform equally well across the variety of data sets. In contrast, the proposed Scalable Monocular Surface Reconstruction (SMSR) combines strengths of several algorithms, i.e., it is scalable with the number of points, can handle sparse and dense settings as well as different types of motions and deformations. We estimate camera pose by singular value thresholding and proximal gradient. Our formulation adopts alternating direction method of multipliers which converges in linear time for large point track matrices. In the proposed SMSR, trajectory space constraints are integrated by smoothing of the measurement matrix. In the extensive experiments, SMSR is demonstrated to consistently achieve state-of-the-art accuracy on a wide variety of data sets.
Tasks
Published	2017-10-17
URL	http://arxiv.org/abs/1710.06130v1
PDF	http://arxiv.org/pdf/1710.06130v1.pdf
PWC	https://paperswithcode.com/paper/scalable-dense-monocular-surface
Repo
Framework

DGCNN: Disordered Graph Convolutional Neural Network Based on the Gaussian Mixture Model


Title	DGCNN: Disordered Graph Convolutional Neural Network Based on the Gaussian Mixture Model
Authors	Bo Wu, Yang Liu, Bo Lang, Lei Huang
Abstract	Convolutional neural networks (CNNs) can be applied to graph similarity matching, in which case they are called graph CNNs. Graph CNNs are attracting increasing attention due to their effectiveness and efficiency. However, the existing convolution approaches focus only on regular data forms and require the transfer of the graph or key node neighborhoods of the graph into the same fixed form. During this transfer process, structural information of the graph can be lost, and some redundant information can be incorporated. To overcome this problem, we propose the disordered graph convolutional neural network (DGCNN) based on the mixed Gaussian model, which extends the CNN by adding a preprocessing layer called the disordered graph convolutional layer (DGCL). The DGCL uses a mixed Gaussian function to realize the mapping between the convolution kernel and the nodes in the neighborhood of the graph. The output of the DGCL is the input of the CNN. We further implement a backward-propagation optimization process of the convolutional layer by which we incorporate the feature-learning model of the irregular node neighborhood structure into the network. Thereafter, the optimization of the convolution kernel becomes part of the neural network learning process. The DGCNN can accept arbitrary scaled and disordered neighborhood graph structures as the receptive fields of CNNs, which reduces information loss during graph transformation. Finally, we perform experiments on multiple standard graph datasets. The results show that the proposed method outperforms the state-of-the-art methods in graph classification and retrieval.
Tasks	Graph Classification, Graph Similarity
Published	2017-12-10
URL	http://arxiv.org/abs/1712.03563v1
PDF	http://arxiv.org/pdf/1712.03563v1.pdf
PWC	https://paperswithcode.com/paper/dgcnn-disordered-graph-convolutional-neural
Repo
Framework

An entity-driven recursive neural network model for chinese discourse coherence modeling


Title	An entity-driven recursive neural network model for chinese discourse coherence modeling
Authors	Fan Xu, Shujing Du, Maoxi Li, Mingwen Wang
Abstract	Chinese discourse coherence modeling remains a challenge taskin Natural Language Processing field.Existing approaches mostlyfocus on the need for feature engineering, whichadoptthe sophisticated features to capture the logic or syntactic or semantic relationships acrosssentences within a text.In this paper, we present an entity-drivenrecursive deep modelfor the Chinese discourse coherence evaluation based on current English discourse coherenceneural network model. Specifically, to overcome the shortage of identifying the entity(nouns) overlap across sentences in the currentmodel, Our combined modelsuccessfully investigatesthe entities information into the recursive neural network freamework.Evaluation results on both sentence ordering and machine translation coherence rating task show the effectiveness of the proposed model, which significantly outperforms the existing strong baseline.
Tasks	Feature Engineering, Machine Translation, Sentence Ordering
Published	2017-04-14
URL	http://arxiv.org/abs/1704.04336v1
PDF	http://arxiv.org/pdf/1704.04336v1.pdf
PWC	https://paperswithcode.com/paper/an-entity-driven-recursive-neural-network
Repo
Framework

Machine Learning and the Future of Realism


Title	Machine Learning and the Future of Realism
Authors	Giles Hooker, Cliff Hooker
Abstract	The preceding three decades have seen the emergence, rise, and proliferation of machine learning (ML). From half-recognised beginnings in perceptrons, neural nets, and decision trees, algorithms that extract correlations (that is, patterns) from a set of data points have broken free from their origin in computational cognition to embrace all forms of problem solving, from voice recognition to medical diagnosis to automated scientific research and driverless cars, and it is now widely opined that the real industrial revolution lies less in mobile phone and similar than in the maturation and universal application of ML. Among the consequences just might be the triumph of anti-realism over realism.
Tasks	Medical Diagnosis
Published	2017-04-15
URL	http://arxiv.org/abs/1704.04688v1
PDF	http://arxiv.org/pdf/1704.04688v1.pdf
PWC	https://paperswithcode.com/paper/machine-learning-and-the-future-of-realism
Repo
Framework

Men Are from Mars, Women Are from Venus: Evaluation and Modelling of Verbal Associations


Title	Men Are from Mars, Women Are from Venus: Evaluation and Modelling of Verbal Associations
Authors	Ekaterina Vylomova, Andrei Shcherbakov, Yuriy Philippovich, Galina Cherkasova
Abstract	We present a quantitative analysis of human word association pairs and study the types of relations presented in the associations. We put our main focus on the correlation between response types and respondent characteristics such as occupation and gender by contrasting syntagmatic and paradigmatic associations. Finally, we propose a personalised distributed word association model and show the importance of incorporating demographic factors into the models commonly used in natural language processing.
Tasks
Published	2017-07-26
URL	http://arxiv.org/abs/1707.08458v1
PDF	http://arxiv.org/pdf/1707.08458v1.pdf
PWC	https://paperswithcode.com/paper/men-are-from-mars-women-are-from-venus
Repo
Framework

Stochastic Primal-Dual Proximal ExtraGradient Descent for Compositely Regularized Optimization


Title	Stochastic Primal-Dual Proximal ExtraGradient Descent for Compositely Regularized Optimization
Authors	Tianyi Lin, Linbo Qiao, Teng Zhang, Jiashi Feng, Bofeng Zhang
Abstract	We consider a wide range of regularized stochastic minimization problems with two regularization terms, one of which is composed with a linear function. This optimization model abstracts a number of important applications in artificial intelligence and machine learning, such as fused Lasso, fused logistic regression, and a class of graph-guided regularized minimization. The computational challenges of this model are in two folds. On one hand, the closed-form solution of the proximal mapping associated with the composed regularization term or the expected objective function is not available. On the other hand, the calculation of the full gradient of the expectation in the objective is very expensive when the number of input data samples is considerably large. To address these issues, we propose a stochastic variant of extra-gradient type methods, namely \textsf{Stochastic Primal-Dual Proximal ExtraGradient descent (SPDPEG)}, and analyze its convergence property for both convex and strongly convex objectives. For general convex objectives, the uniformly average iterates generated by \textsf{SPDPEG} converge in expectation with $O(1/\sqrt{t})$ rate. While for strongly convex objectives, the uniformly and non-uniformly average iterates generated by \textsf{SPDPEG} converge with $O(\log(t)/t)$ and $O(1/t)$ rates, respectively. The order of the rate of the proposed algorithm is known to match the best convergence rate for first-order stochastic algorithms. Experiments on fused logistic regression and graph-guided regularized logistic regression problems show that the proposed algorithm performs very efficiently and consistently outperforms other competing algorithms.
Tasks
Published	2017-08-20
URL	http://arxiv.org/abs/1708.05978v4
PDF	http://arxiv.org/pdf/1708.05978v4.pdf
PWC	https://paperswithcode.com/paper/stochastic-primal-dual-proximal-extragradient
Repo
Framework

Difficulty-level Modeling of Ontology-based Factual Questions


Title	Difficulty-level Modeling of Ontology-based Factual Questions
Authors	Vinu E. V, P Sreenivasa Kumar
Abstract	Semantics based knowledge representations such as ontologies are found to be very useful in automatically generating meaningful factual questions. Determining the difficulty level of these system generated questions is helpful to effectively utilize them in various educational and professional applications. The existing approaches for finding the difficulty level of factual questions are very simple and are limited to a few basic principles. We propose a new methodology for this problem by considering an educational theory called Item Response Theory (IRT). In the IRT, knowledge proficiency of end users (learners) are considered for assigning difficulty levels, because of the assumptions that a given question is perceived differently by learners of various proficiencies. We have done a detailed study on the features (factors) of a question statement which could possibly determine its difficulty level for three learner categories (experts, intermediates and beginners). We formulate ontology based metrics for the same. We then train three logistic regression models to predict the difficulty level corresponding to the three learner categories.
Tasks
Published	2017-09-03
URL	http://arxiv.org/abs/1709.00670v1
PDF	http://arxiv.org/pdf/1709.00670v1.pdf
PWC	https://paperswithcode.com/paper/difficulty-level-modeling-of-ontology-based
Repo
Framework

Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation


Title	Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation
Authors	Yin Tat Lee, Santosh S. Vempala
Abstract	We give the first rigorous proof of the convergence of Riemannian Hamiltonian Monte Carlo, a general (and practical) method for sampling Gibbs distributions. Our analysis shows that the rate of convergence is bounded in terms of natural smoothness parameters of an associated Riemannian manifold. We then apply the method with the manifold defined by the log barrier function to the problems of (1) uniformly sampling a polytope and (2) computing its volume, the latter by extending Gaussian cooling to the manifold setting. In both cases, the total number of steps needed is O^{*}(mn^{\frac{2}{3}}), improving the state of the art. A key ingredient of our analysis is a proof of an analog of the KLS conjecture for Gibbs distributions over manifolds.
Tasks
Published	2017-10-17
URL	http://arxiv.org/abs/1710.06261v1
PDF	http://arxiv.org/pdf/1710.06261v1.pdf
PWC	https://paperswithcode.com/paper/convergence-rate-of-riemannian-hamiltonian
Repo
Framework

Data-driven Natural Language Generation: Paving the Road to Success


Title	Data-driven Natural Language Generation: Paving the Road to Success
Authors	Jekaterina Novikova, Ondřej Dušek, Verena Rieser
Abstract	We argue that there are currently two major bottlenecks to the commercial use of statistical machine learning approaches for natural language generation (NLG): (a) The lack of reliable automatic evaluation metrics for NLG, and (b) The scarcity of high quality in-domain corpora. We address the first problem by thoroughly analysing current evaluation metrics and motivating the need for a new, more reliable metric. The second problem is addressed by presenting a novel framework for developing and evaluating a high quality corpus for NLG training.
Tasks	Text Generation
Published	2017-06-28
URL	http://arxiv.org/abs/1706.09433v1
PDF	http://arxiv.org/pdf/1706.09433v1.pdf
PWC	https://paperswithcode.com/paper/data-driven-natural-language-generation
Repo
Framework

Relative Error Tensor Low Rank Approximation


Title	Relative Error Tensor Low Rank Approximation
Authors	Zhao Song, David P. Woodruff, Peilin Zhong
Abstract	We consider relative error low rank approximation of $tensors$ with respect to the Frobenius norm: given an order-$q$ tensor $A \in \mathbb{R}^{\prod_{i=1}^q n_i}$, output a rank-$k$ tensor $B$ for which $\A-B_F^2 \leq (1+\epsilon)$OPT, where OPT $= \inf_{\textrm{rank-}k~A’} \A-A’_F^2$. Despite the success on obtaining relative error low rank approximations for matrices, no such results were known for tensors. One structural issue is that there may be no rank-$k$ tensor $A_k$ achieving the above infinum. Another, computational issue, is that an efficient relative error low rank approximation algorithm for tensors would allow one to compute the rank of a tensor, which is NP-hard. We bypass these issues via (1) bicriteria and (2) parameterized complexity solutions: (1) We give an algorithm which outputs a rank $k’ = O((k/\epsilon)^{q-1})$ tensor $B$ for which $\A-B_F^2 \leq (1+\epsilon)$OPT in $nnz(A) + n \cdot \textrm{poly}(k/\epsilon)$ time in the real RAM model. Here $nnz(A)$ is the number of non-zero entries in $A$. (2) We give an algorithm for any $\delta >0$ which outputs a rank $k$ tensor $B$ for which $\A-B_F^2 \leq (1+\epsilon)$OPT and runs in $ ( nnz(A) + n \cdot \textrm{poly}(k/\epsilon) + \exp(k^2/\epsilon) ) \cdot n^\delta$ time in the unit cost RAM model. For outputting a rank-$k$ tensor, or even a bicriteria solution with rank-$Ck$ for a certain constant $C > 1$, we show a $2^{\Omega(k^{1-o(1)})}$ time lower bound under the Exponential Time Hypothesis. Our results give the first relative error low rank approximations for tensors for a large number of robust error measures for which nothing was known, as well as column row and tube subset selection. We also obtain new results for matrices, such as $nnz(A)$-time CUR decompositions, improving previous $nnz(A)\log n$-time algorithms, which may be of independent interest.
Tasks
Published	2017-04-26
URL	http://arxiv.org/abs/1704.08246v2
PDF	http://arxiv.org/pdf/1704.08246v2.pdf
PWC	https://paperswithcode.com/paper/relative-error-tensor-low-rank-approximation
Repo
Framework

Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients


Title	Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients
Authors	Lukas Balles, Philipp Hennig
Abstract	The ADAM optimizer is exceedingly popular in the deep learning community. Often it works very well, sometimes it doesn’t. Why? We interpret ADAM as a combination of two aspects: for each weight, the update direction is determined by the sign of stochastic gradients, whereas the update magnitude is determined by an estimate of their relative variance. We disentangle these two aspects and analyze them in isolation, gaining insight into the mechanisms underlying ADAM. This analysis also extends recent results on adverse effects of ADAM on generalization, isolating the sign aspect as the problematic one. Transferring the variance adaptation to SGD gives rise to a novel method, completing the practitioner’s toolbox for problems where ADAM fails.
Tasks
Published	2017-05-22
URL	http://arxiv.org/abs/1705.07774v3
PDF	http://arxiv.org/pdf/1705.07774v3.pdf
PWC	https://paperswithcode.com/paper/dissecting-adam-the-sign-magnitude-and
Repo
Framework

Deepest Neural Networks


Title	Deepest Neural Networks
Authors	Raul Rojas
Abstract	This paper shows that a long chain of perceptrons (that is, a multilayer perceptron, or MLP, with many hidden layers of width one) can be a universal classifier. The classification procedure is not necessarily computationally efficient, but the technique throws some light on the kind of computations possible with narrow and deep MLPs.
Tasks
Published	2017-07-09
URL	http://arxiv.org/abs/1707.02617v1
PDF	http://arxiv.org/pdf/1707.02617v1.pdf
PWC	https://paperswithcode.com/paper/deepest-neural-networks
Repo
Framework

A Learning and Masking Approach to Secure Learning


Title	A Learning and Masking Approach to Secure Learning
Authors	Linh Nguyen, Sky Wang, Arunesh Sinha
Abstract	Deep Neural Networks (DNNs) have been shown to be vulnerable against adversarial examples, which are data points cleverly constructed to fool the classifier. Such attacks can be devastating in practice, especially as DNNs are being applied to ever increasing critical tasks like image recognition in autonomous driving. In this paper, we introduce a new perspective on the problem. We do so by first defining robustness of a classifier to adversarial exploitation. Next, we show that the problem of adversarial example generation can be posed as learning problem. We also categorize attacks in literature into high and low perturbation attacks; well-known attacks like fast-gradient sign method (FGSM) and our attack produce higher perturbation adversarial examples while the more potent but computationally inefficient Carlini-Wagner (CW) attack is low perturbation. Next, we show that the dual approach of the attack learning problem can be used as a defensive technique that is effective against high perturbation attacks. Finally, we show that a classifier masking method achieved by adding noise to the a neural network’s logit output protects against low distortion attacks such as the CW attack. We also show that both our learning and masking defense can work simultaneously to protect against multiple attacks. We demonstrate the efficacy of our techniques by experimenting with the MNIST and CIFAR-10 datasets.
Tasks	Autonomous Driving
Published	2017-09-13
URL	http://arxiv.org/abs/1709.04447v4
PDF	http://arxiv.org/pdf/1709.04447v4.pdf
PWC	https://paperswithcode.com/paper/a-learning-and-masking-approach-to-secure
Repo
Framework

Learning to Hallucinate Face Images via Component Generation and Enhancement


Title	Learning to Hallucinate Face Images via Component Generation and Enhancement
Authors	Yibing Song, Jiawei Zhang, Shengfeng He, Linchao Bao, Qingxiong Yang
Abstract	We propose a two-stage method for face hallucination. First, we generate facial components of the input image using CNNs. These components represent the basic facial structures. Second, we synthesize fine-grained facial structures from high resolution training images. The details of these structures are transferred into facial components for enhancement. Therefore, we generate facial components to approximate ground truth global appearance in the first stage and enhance them through recovering details in the second stage. The experiments demonstrate that our method performs favorably against state-of-the-art methods
Tasks	Face Hallucination
Published	2017-08-01
URL	http://arxiv.org/abs/1708.00223v1
PDF	http://arxiv.org/pdf/1708.00223v1.pdf
PWC	https://paperswithcode.com/paper/learning-to-hallucinate-face-images-via
Repo
Framework