2019 年的期刊文章 · 第 29 页

共 1232 篇,按发表时间排,新的在前,每页 40 篇。这一页是 2019 到 2019。

按期刊、按主题看 →

第 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 页

JMLR Optimization & Learning Theory · 发表于 2019

Learning to Match via Inverse Optimal Transport

Ruilin Li, Xiaojing Ye, Haomin Zhou, Hongyuan Zha

摘要

We propose a unified data-driven framework based on inverse optimal transport that can learn adaptive, nonlinear interaction cost function from noisy and incomplete empirical matching matrix and predict new matching in various matching contexts. We emphasize that the discrete optimal transport plays the role of a variational principle which gives rise to an optimization based framework for modeling the observed empirical matching data. Our formulation leads to a non-convex optimization problem which can be solved efficiently by an alternating optimization method. A key novel aspect of our formulation is the incorporation of marginal relaxation via regularized Wasserstein distance, significantly improving the robustness of the method in the face of noisy or missing empirical matching data. Our model falls into the category of prescriptive models, which not only predict potential future matching, but is also able to explain what leads to empirical matching and quantifies the impact of changes in matching factors. The proposed approach has wide applicability including predicting matching in online dating, labor market, college application and crowdsourcing. We back up our claims with numerical experiments on both synthetic data and real world data sets.

JMLR Latent Variables & Mixtures · 发表于 2019

Learning by Unsupervised Nonlinear Diffusion

Mauro Maggioni, James M. Murphy

摘要

This paper proposes and analyzes a novel clustering algorithm, called learning by unsupervised nonlinear diffusion (LUND), that combines graph-based diffusion geometry with techniques based on density and mode estimation. LUND is suitable for data generated from mixtures of distributions with densities that are both multimodal and supported near nonlinear sets. A crucial aspect of this algorithm is the use of time of a data-adapted diffusion process, and associated diffusion distances, as a scale parameter that is different from the local spatial scale parameter used in many clustering algorithms. We prove estimates for the behavior of diffusion distances with respect to this time parameter under a flexible nonparametric data model, identifying a range of times in which the mesoscopic equilibria of the underlying process are revealed, corresponding to a gap between within-cluster and between-cluster diffusion distances. These structures may be missed by the top eigenvectors of the graph Laplacian, commonly used in spectral clustering. This analysis is leveraged to prove sufficient conditions guaranteeing the accuracy of LUND. We implement LUND and confirm its theoretical properties on illustrative data sets, demonstrating its theoretical and empirical advantages over both spectral and density-based clustering.

JMLR Networks & Graphs · 发表于 2019

Learning Unfaithful $K$-separable Gaussian Graphical Models

De Wen Soh, Sekhar Tatikonda

摘要

The global Markov property for Gaussian graphical models ensures graph separation implies conditional independence. Specifically if a node set $S$ graph separates nodes $u$ and $v$ then $X_u$ is conditionally independent of $X_v$ given $X_S$. The opposite direction need not be true, that is, $X_u \perp X_v \mid X_S$ need not imply $S$ is a node separator of $u$ and $v$. When it does, the relation $X_u \perp X_v \mid X_S$ is called faithful. In this paper we provide a characterization of faithful relations and then provide an algorithm to test faithfulness based only on knowledge of other conditional relations of the form $X_i \perp X_j \mid X_S$. We study two classes of separable Gaussian graphical models, namely, weakly $K$-separable and strongly $K$-separable Gaussian graphical models. Using the above test for faithfulness, we introduce algorithms to learn the topologies of weakly $K$-separable and strongly $K$-separable Gaussian graphical models with $\Omega(K\log p)$ sample complexity. For strongly $K$-separable Gaussian graphical models, we additionally provide a method with error bounds for learning the off-diagonal precision matrix entries.

JMLR Machine Learning Networks & Graphs · 发表于 2019

Learning Representations of Persistence Barcodes

Christoph D. Hofer, Roland Kwitt, Marc Niethammer

摘要

We consider the problem of supervised learning with summary representations of topological features in data. In particular, we focus on persistent homology, the prevalent tool used in topological data analysis. As the summary representations, referred to as barcodes or persistence diagrams, come in the unusual format of multi sets, equipped with computationally expensive metrics, they can not readily be processed with conventional learning techniques. While different approaches to address this problem have been proposed, either in the context of kernel-based learning, or via carefully designed vectorization techniques, it remains an open problem how to leverage advances in representation learning via deep neural networks. Appropriately handling topological summaries as input to neural networks would address the disadvantage of previous strategies which handle this type of data in a task-agnostic manner. In particular, we propose an approach that is designed to learn a task-specific representation of barcodes. In other words, we aim to learn a representation that adapts to the learning problem while, at the same time, preserving theoretical properties (such as stability). This is done by projecting barcodes into a finite dimensional vector space using a collection of parametrized functionals, so called structure elements, for which we provide a generic construction scheme. A theoretical analysis of this approach reveals sufficient conditions to preserve stability, and also shows that different choices of structure elements lead to great differences with respect to their suitability for numerical optimization. When implemented as a neural network input layer, our approach demonstrates compelling performance on various types of problems, including graph classification and eigenvalue prediction, the classification of 2D/3D object shapes and recognizing activities from EEG signals.

JMLR High-Dimensional Latent Variables & Mixtures · 发表于 2019

Learning Overcomplete, Low Coherence Dictionaries with Linear Inference

Jesse A. Livezey, Alejandro F. Bujan, Friedrich T. Sommer

摘要

Finding overcomplete latent representations of data has applications in data analysis, signal processing, machine learning, theoretical neuroscience and many other fields. In an overcomplete representation, the number of latent features exceeds the data dimensionality, which is useful when the data is undersampled by the measurements (compressed sensing or information bottlenecks in neural systems) or composed from multiple complete sets of linear features, each spanning the data space. Independent Components Analysis (ICA) is a linear technique for learning sparse latent representations, which typically has a lower computational cost than sparse coding, a linear generative model which requires an iterative, nonlinear inference step. While well suited for finding complete representations, we show that overcompleteness poses a challenge to existing ICA algorithms. Specifically, the coherence control used in existing ICA and other dictionary learning algorithms, necessary to prevent the formation of duplicate dictionary features, is ill-suited in the overcomplete case. We show that in the overcomplete case, several existing ICA algorithms have undesirable global minima that maximize coherence. We provide a theoretical explanation of these failures and, based on the theory, propose improved coherence control costs for overcomplete ICA algorithms. Further, by comparing ICA algorithms to the computationally more expensive sparse coding on synthetic data, we show that the limited applicability of overcomplete, linear inference can be extended with the proposed cost functions. Finally, when trained on natural images, we show that the coherence control biases the exploration of the data manifold, sometimes yielding suboptimal, coherent solutions. All told, this study contributes new insights into and methods for coherence control for linear ICA, some of which are applicable to many other nonlinear models.

JMLR Other · 发表于 2019

Learning Optimized Risk Scores

Berk Ustun, Cynthia Rudin

摘要

Risk scores are simple classification models that let users make quick risk predictions by adding and subtracting a few small numbers. These models are widely used in medicine and criminal justice, but are difficult to learn from data because they need to be calibrated, sparse, use small integer coefficients, and obey application-specific constraints. In this paper, we introduce a machine learning method to learn risk scores. We formulate the risk score problem as a mixed integer nonlinear program, and present a cutting plane algorithm to recover its optimal solution. We improve our algorithm with specialized techniques that generate feasible solutions, narrow the optimality gap, and reduce data-related computation. Our algorithm can train risk scores in a way that scales linearly in the number of samples in a dataset, and that allows practitioners to address application-specific constraints without parameter tuning or post-processing. We benchmark the performance of different methods to learn risk scores on publicly available datasets, comparing risk scores produced by our method to risk scores built using methods that are used in practice. We also discuss the practical benefits of our method through a real-world application where we build a customized risk score for ICU seizure prediction in collaboration with the Massachusetts General Hospital.

JMLR Latent Variables & Mixtures High-Dimensional · 发表于 2019

Learning Attribute Patterns in High-Dimensional Structured Latent Attribute Models

Yuqi Gu, Gongjun Xu

摘要

Structured latent attribute models (SLAMs) are a special family of discrete latent variable models widely used in social and biological sciences. This paper considers the problem of learning significant attribute patterns from a SLAM with potentially high-dimensional configurations of the latent attributes. We address the theoretical identifiability issue, propose a penalized likelihood method for the selection of the attribute patterns, and further establish the selection consistency in such an overfitted SLAM with a diverging number of latent patterns. The good performance of the proposed methodology is illustrated by simulation studies and two real datasets in educational assessments.

JMLR Optimization & Learning Theory · 发表于 2019

Learnability of Solutions to Conjunctive Queries

Hubie Chen, Matthew Valeriote

摘要

The problem of learning the solution space of an unknown formula has been studied in multiple embodiments in computational learning theory. In this article, we study a family of such learning problems; this family contains, for each relational structure, the problem of learning the solution space of an unknown conjunctive query evaluated on the structure. A progression of results aimed to classify the learnability of each of the problems in this family, and thus far a culmination thereof was a positive learnability result generalizing all previous ones. This article completes the classification program towards which this progression of results strived, by presenting a negative learnability result that complements the mentioned positive learnability result. In addition, a further negative learnability result is exhibited, which indicates a dichotomy within the problems to which the first negative result applies. In order to obtain our negative results, we make use of universal-algebraic concepts.

JMLR Optimization & Learning Theory · 发表于 2019

Lazifying Conditional Gradient Algorithms

Gábor Braun, Sebastian Pokutta, Daniel Zink

摘要

Conditional gradient algorithms (also often called Frank-Wolfe algorithms) are popular due to their simplicity of only requiring a linear optimization oracle and more recently they also gained significant traction for online learning. While simple in principle, in many cases the actual implementation of the linear optimization oracle is costly. We show a general method to lazify various conditional gradient algorithms, which in actual computations leads to several orders of magnitude of speedup in wall-clock time. This is achieved by using a faster separation oracle instead of a linear optimization oracle, relying only on few linear optimization oracle calls.

JMLR Nonparametric & Semiparametric Networks & Graphs · 发表于 2019

Layer-Wise Learning Strategy for Nonparametric Tensor Product Smoothing Spline Regression and Graphical Models

Kean Ming Tan, Junwei Lu, Tong Zhang, Han Liu

摘要

Nonparametric estimation of multivariate functions is an important problem in statistical machine learning with many applications, ranging from nonparametric regression to nonparametric graphical models. Several authors have proposed to estimate multivariate functions under the smoothing spline analysis of variance (SSANOVA) framework, which assumes that the multivariate function can be decomposed into the summation of main effects, two-way interaction effects, and higher order interaction effects. However, existing methods are not scalable to the dimension of the random variables and the order of interactions. We propose a LAyer-wiSE leaRning strategy (LASER) to estimate multivariate functions under the SSANOVA framework. The main idea is to approximate the multivariate function sequentially starting from a model with only the main effects. Conditioned on the support of the estimated main effects, we estimate the two-way interaction effects only when the corresponding main effects are estimated to be non-zero. This process is continued until no more higher order interaction effects are identified. The proposed strategy provides a data-driven approach for estimating multivariate functions under the SSANOVA framework. Our proposal yields a sequence of estimators. To establish the theoretical properties of the sequence of estimators, we establish the notion of post-selection persistency. Extensive numerical studies are performed to evaluate the performance of our algorithm.

JMLR Nonparametric & Semiparametric · 发表于 2019

Kernels for Sequentially Ordered Data

Franz J. Kiraly, Harald Oberhauser

摘要

We present a novel framework for learning with sequential data of any kind, such as multivariate time series, strings, or sequences of graphs. The main result is a ”sequentialization” that transforms any kernel on a given domain into a kernel for sequences in that domain. This procedure preserves properties such as positive definiteness, the associated kernel feature map is an ordered variant of sample (cross-)moments, and this sequentialized kernel is consistent in the sense that it converges to a kernel for paths if sequences converge to paths (by discretization). Further, classical kernels for sequences arise as special cases of this method. We use dynamic programming and low-rank techniques for tensors to provide efficient algorithms to compute this sequentialized kernel.

JMLR Nonparametric & Semiparametric · 发表于 2019

Kernel Approximation Methods for Speech Recognition

Avner May, Alireza Bagheri Garakani, Zhiyun Lu, Dong Guo, Kuan Liu, Aurélien Bellet, Linxi Fan, Michael Collins, Daniel Hsu, Brian Kingsbury, Michael Picheny, Fei Sha

摘要

We study the performance of kernel methods on the acoustic modeling task for automatic speech recognition, and compare their performance to deep neural networks (DNNs). To scale the kernel methods to large data sets, we use the random Fourier feature method of Rahimi and Recht (2007). We propose two novel techniques for improving the performance of kernel acoustic models. First, we propose a simple but effective feature selection method which reduces the number of random features required to attain a fixed level of performance. Second, we present a number of metrics which correlate strongly with speech recognition performance when computed on the heldout set; we attain improved performance by using these metrics to decide when to stop training. Additionally, we show that the linear bottleneck method of Sainath et al. (2013a) improves the performance of our kernel models significantly, in addition to speeding up training and making the models more compact. Leveraging these three methods, the kernel methods attain token error rates between $0.5\%$ better and $0.1\%$ worse than fully-connected DNNs across four speech recognition data sets, including the TIMIT and Broadcast News benchmark tasks.

JMLR Latent Variables & Mixtures · 发表于 2019

Joint PLDA for Simultaneous Modeling of Two Factors

Luciana Ferrer, Mitchell McLaren

摘要

Probabilistic linear discriminant analysis (PLDA) is a method used for biometric problems like speaker or face recognition that models the variability of the samples using two latent variables, one that depends on the class of the sample and another one that is assumed independent across samples and models the within-class variability. In this work, we propose a generalization of PLDA that enables joint modeling of two sample-dependent factors: the class of interest and a nuisance condition. The approach does not change the basic form of PLDA but rather modifies the training procedure to consider the dependency across samples of the latent variable that models within-class variability. While the identity of the nuisance condition is needed during training, it is not needed during testing since we propose a scoring procedure that marginalizes over the corresponding latent variable. We show results on a multilingual speaker-verification task, where the language spoken is considered a nuisance condition. The proposed joint PLDA approach leads to significant performance gains in this task for two different data sets, in particular when the training data contains mostly or only monolingual speakers.

JMLR Other · 发表于 2019

Ivanov-Regularised Least-Squares Estimators over Large RKHSs and Their Interpolation Spaces

Stephen Page, Steffen Grünewälder

摘要

We study kernel least-squares estimation under a norm constraint. This form of regularisation is known as Ivanov regularisation and it provides better control of the norm of the estimator than the well-established Tikhonov regularisation. Ivanov regularisation can be studied under minimal assumptions. In particular, we assume only that the RKHS is separable with a bounded and measurable kernel. We provide rates of convergence for the expected squared $L^2$ error of our estimator under the weak assumption that the variance of the response variables is bounded and the unknown regression function lies in an interpolation space between $L^2$ and the RKHS. We then obtain faster rates of convergence when the regression function is bounded by clipping the estimator. In fact, we attain the optimal rate of convergence. Furthermore, we provide a high-probability bound under the stronger assumption that the response variables have subgaussian errors and that the regression function lies in an interpolation space between $L^\infty$ and the RKHS. Finally, we derive adaptive results for the settings in which the regression function is bounded.

JMLR Networks & Graphs · 发表于 2019

Iterated Learning in Dynamic Social Networks

Bernard Chazelle, Chu Wang

摘要

A classic finding by (Kalish et al., 2007) shows that no language can be learned iteratively by rational agents in a self-sustained manner. In other words, if $A$ teaches a foreign language to $B$, who then teaches what she learned to $C$, and so on, the language will quickly get lost and agents will wind up teaching their own common native language. If so, how can linguistic novelty ever be sustained? We address this apparent paradox by considering the case of iterated learning in a social network: we show that by varying the lengths of the learning sessions over time or by keeping the networks dynamic, it is possible for iterated learning to endure forever with arbitrarily small loss.

Econometrica Econometrics & Economics · 发表于 2019

Insurgency and Small Wars: Estimation of Unobserved Coalition Structures

Francesco Trebbi, Eric Weese

摘要

Insurgency and guerrilla warfare impose enormous socio‐economic costs and often persist for decades. The opacity of such forms of conflict is an obstacle to effective international humanitarian intervention and development programs. To shed light on the internal organization of otherwise unknown insurgent groups, this paper proposes two methodologies for the detection of unobserved coalitions of militants in conflict areas. These approaches are based on daily geocoded incident‐level data on insurgent attacks. We provide applications to the Afghan conflict during the 2004–2009 period and to Pakistan during the 2008–2011 period, identifying systematically different coalition structures. Applications to global terrorism data and identification of new groups or shifting coalitions are discussed.

Econometrica Latent Variables & Mixtures · 发表于 2019

Inference in Group Factor Models With an Application to Mixed‐Frequency Data

E. Andreou, P. Gagliardini, E. Ghysels, M. Rubin

摘要

We derive asymptotic properties of estimators and test statistics to determine—in a grouped data setting—common versus group‐specific factors. Despite the fact that our test statistic for the number of common factors, under the null, involves a parameter at the boundary (related to unit canonical correlations), we derive a parameter‐free asymptotic Gaussian distribution. We show how the group factor setting applies to mixed‐frequency data. As an empirical illustration, we address the question whether Industrial Production (IP) is still the dominant factor driving the U.S. economy using a mixed‐frequency data panel of IP and non‐IP sectors. We find that a single common factor explains 89% of IP output growth and 61% of total GDP growth despite the diminishing role of manufacturing.

Econometrica Latent Variables & Mixtures · 发表于 2019

Identification With Additively Separable Heterogeneity

Roy Allen, John Rehbeck

摘要

This paper provides nonparametric identification results for a class of latent utility models with additively separable unobservable heterogeneity. These results apply to existing models of discrete choice, bundles, decisions under uncertainty, and matching. Under an independence assumption, such models admit a representative agent. As a result, we can identify how regressors alter the desirability of goods using only average demands. Moreover, average indirect utility (“welfare”) is identified without needing to specify or identify the distribution of unobservable heterogeneity.

Econometrica Other · 发表于 2019

How Destructive Is Innovation?

Daniel Garcia-Macia, Chang-Tai Hsieh, Peter J. Klenow

摘要

Entrants and incumbents can create new products and displace the products of competitors. Incumbents can also improve their existing products. How much of aggregate productivity growth occurs through each of these channels? Using data from the U.S. Longitudinal Business Database on all nonfarm private businesses from 1983 to 2013, we arrive at three main conclusions: First, most growth appears to come from incumbents. We infer this from the modest employment share of entering firms (defined as those less than 5 years old). Second, most growth seems to occur through improvements of existing varieties rather than creation of brand new varieties. Third, own‐product improvements by incumbents appear to be more important than creative destruction. We infer this because the distribution of job creation and destruction has thinner tails than implied by a model with a dominant role for creative destruction.

JMLR High-Dimensional · 发表于 2019

High-dimensional Varying Index Coefficient Models via Stein's Identity

Sen Na, Zhuoran Yang, Zhaoran Wang, Mladen Kolar

摘要

We study the parameter estimation problem for a varying index coefficient model in high dimensions. Unlike the most existing works that iteratively estimate the parameters and link functions, based on the generalized Stein's identity, we propose computationally efficient estimators for the high-dimensional parameters without estimating the link functions. We consider two different setups where we either estimate each sparse parameter vector individually or estimate the parameters simultaneously as a sparse or low-rank matrix. For all these cases, our estimators are shown to achieve optimal statistical rates of convergence (up to logarithmic terms in the low-rank setting). Moreover, throughout our analysis, we only require the covariate to satisfy certain moment conditions, which is significantly weaker than the Gaussian or elliptically symmetric assumptions that are commonly made in the existing literature. Finally, we conduct extensive numerical experiments to corroborate the theoretical results.

JMLR High-Dimensional · 发表于 2019

High-Dimensional Poisson Structural Equation Model Learning via $\ell_1$-Regularized Regression

Gunwoong Park, Sion Park

摘要

In this paper, we develop a new approach to learning high-dimensional Poisson structural equation models from only observational data without strong assumptions such as faithfulness and a sparse moralized graph. A key component of our method is to decouple the ordering estimation or parent search where the problems can be efficiently addressed using $\ell_1$-regularized regression and the moments relation. We show that sample size $n = \Omega( d^{2} \log^{9} p)$ is sufficient for our polynomial time Moments Ratio Scoring (MRS) algorithm to recover the true directed graph, where $p$ is the number of nodes and $d$ is the maximum indegree. We verify through simulations that our algorithm is statistically consistent in the high-dimensional $p>n$ setting, and performs well compared to state-of-the-art ODS, GES, and MMHC algorithms. We also demonstrate through multivariate real count data that our MRS algorithm is well-suited to estimating DAG models for multivariate count data in comparison to other methods used for discrete data.

JMLR Bayesian Methods · 发表于 2019

Hamiltonian Monte Carlo with Energy Conserving Subsampling

Khue-Dung Dang, Matias Quiroz, Robert Kohn, Minh-Ngoc Tran, Mattias Villani

摘要

Hamiltonian Monte Carlo (HMC) samples efficiently from high-dimensional posterior distributions with proposed parameter draws obtained by iterating on a discretized version of the Hamiltonian dynamics. The iterations make HMC computationally costly, especially in problems with large data sets, since it is necessary to compute posterior densities and their derivatives with respect to the parameters. Naively computing the Hamiltonian dynamics on a subset of the data causes HMC to lose its key ability to generate distant parameter proposals with high acceptance probability. The key insight in our article is that efficient subsampling HMC for the parameters is possible if both the dynamics and the acceptance probability are computed from the same data subsample in each complete HMC iteration. We show that this is possible to do in a principled way in a HMC-within-Gibbs framework where the subsample is updated using a pseudo marginal MH step and the parameters are then updated using an HMC step, based on the current subsample. We show that our subsampling methods are fast and compare favorably to two popular sampling algorithms that use gradient estimates from data subsampling. We also explore the current limitations of subsampling HMC algorithms by varying the quality of the variance reducing control variates used in the estimators of the posterior density and its gradients.

JMLR Networks & Graphs Nonparametric & Semiparametric · 发表于 2019

Group Invariance, Stability to Deformations, and Complexity of Deep Convolutional Representations

Alberto Bietti, Julien Mairal

摘要

The success of deep convolutional architectures is often attributed in part to their ability to learn multiscale and invariant representations of natural signals. However, a precise study of these properties and how they affect learning guarantees is still missing. In this paper, we consider deep convolutional representations of signals; we study their invariance to translations and to more general groups of transformations, their stability to the action of diffeomorphisms, and their ability to preserve signal information. This analysis is carried by introducing a multilayer kernel based on convolutional kernel networks and by studying the geometry induced by the kernel mapping. We then characterize the corresponding reproducing kernel Hilbert space (RKHS), showing that it contains a large class of convolutional neural networks with homogeneous activation functions. This analysis allows us to separate data representation from learning, and to provide a canonical measure of model complexity, the RKHS norm, which controls both stability and generalization of any learned model. In addition to models in the constructed RKHS, our stability analysis also applies to convolutional networks with generic activations such as rectified linear units, and we discuss its relationship with recent generalization bounds based on spectral norms.

JMLR High-Dimensional Networks & Graphs · 发表于 2019

Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions

Salar Fattahi, Somayeh Sojoudi

摘要

Graphical Lasso (GL) is a popular method for learning the structure of an undirected graphical model, which is based on an $l_1$ regularization technique. The objective of this paper is to compare the computationally-heavy GL technique with a numerically-cheap heuristic method that is based on simply thresholding the sample covariance matrix. To this end, two notions of sign-consistent and inverse-consistent matrices are developed, and then it is shown that the thresholding and GL methods are equivalent if: (i) the thresholded sample covariance matrix is both sign-consistent and inverse-consistent, and (ii) the gap between the largest thresholded and the smallest un-thresholded entries of the sample covariance matrix is not too small. By building upon this result, it is proved that the GL method---as a conic optimization problem---has an explicit closed-form solution if the thresholded sample covariance matrix has an acyclic structure. This result is then generalized to arbitrary sparse support graphs, where a formula is found to obtain an approximate solution of GL. Furthermore, it is shown that the approximation error of the derived explicit formula decreases exponentially fast with respect to the length of the minimum-length cycle of the sparsity graph. The developed results are demonstrated on synthetic data, functional MRI data, traffic flows for transportation networks, and massive randomly generated data sets. We show that the proposed method can obtain an accurate approximation of the GL for instances with the sizes as large as $80,000\times 80,000$ (more than 3.2 billion variables) in less than 30 minutes on a standard laptop computer running MATLAB, while other state-of-the-art methods do not converge within 4 hours

JMLR Networks & Graphs · 发表于 2019

Graph Reduction with Spectral and Cut Guarantees

Andreas Loukas

摘要

Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for graph sparsification. This choice is motivated by the observation that restricted approximation carries strong spectral and cut guarantees, and that it implies approximation results for unsupervised learning problems relying on spectral embeddings. The article then focuses on coarsening - the most common type of graph reduction. Sufficient conditions are derived for a small graph to approximate a larger one in the sense of restricted approximation. These findings give rise to algorithms that, compared to both standard and advanced graph reduction methods, find coarse graphs of improved quality, often by a large margin, without sacrificing speed.

JMLR Networks & Graphs · 发表于 2019

GraSPy: Graph Statistics in Python

Jaewon Chung, Benjamin D. Pedigo, Eric W. Bridgeford, Bijan K. Varjavand, Hayden S. Helm, Joshua T. Vogelstein

摘要

We introduce graspy, a Python library devoted to statistical inference, machine learning, and visualization of random graphs and graph populations. This package provides flexible and easy-to-use algorithms for analyzing and understanding graphs with a sklearn compliant API. graspy can be downloaded from Python Package Index (PyPi), and is released under the Apache 2.0 open-source license. The documentation and all releases are available at https://neurodata.io/graspy.

JMLR Latent Variables & Mixtures · 发表于 2019

Generic Inference in Latent Gaussian Process Models

Edwin V. Bonilla, Karl Krauth, Amir Dezfouli

摘要

We develop an automated variational method for inference in models with Gaussian process (GP) priors and general likelihoods. The method supports multiple outputs and multiple latent functions and does not require detailed knowledge of the conditional likelihood, only needing its evaluation as a black-box function. Using a mixture of Gaussians as the variational distribution, we show that the evidence lower bound and its gradients can be estimated efficiently using samples from univariate Gaussian distributions. Furthermore, the method is scalable to large datasets which is achieved by using an augmented prior via the inducing-variable approach underpinning most sparse GP approximations, along with parallel computation and stochastic optimization. We evaluate our approach quantitatively and qualitatively with experiments on small datasets, medium-scale datasets and large datasets, showing its competitiveness under different likelihood models and sparsity levels. On the large-scale experiments involving prediction of airline delays and classification of handwritten digits, we show that our method is on par with the state-of-the-art hard-coded approaches for scalable GP regression and classification.

JMLR Other · 发表于 2019

Generalized Score Matching for Non-Negative Data

Shiqing Yu, Mathias Drton, Ali Shojaie

摘要

A common challenge in estimating parameters of probability density functions is the intractability of the normalizing constant. While in such cases maximum likelihood estimation may be implemented using numerical integration, the approach becomes computationally intensive. The score matching method of Hyvärinen (2005) avoids direct calculation of the normalizing constant and yields closed-form estimates for exponential families of continuous distributions over $\mathbb{R}^m$. Hyvärinen (2007) extended the approach to distributions supported on the non-negative orthant, $\mathbb{R}_+^m$. In this paper, we give a generalized form of score matching for non-negative data that improves estimation efficiency. As an example, we consider a general class of pairwise interaction models. Addressing an overlooked inexistence problem, we generalize the regularized score matching method of Lin et al. (2016) and improve its theoretical guarantees for non-negative Gaussian graphical models.

JMLR Other · 发表于 2019

Generalized Maximum Entropy Estimation

Tobias Sutter, David Sutter, Peyman Mohajerin Esfahani, John Lygeros

摘要

We consider the problem of estimating a probability distribution that maximizes the entropy while satisfying a finite number of moment constraints, possibly corrupted by noise. Based on duality of convex programming, we present a novel approximation scheme using a smoothed fast gradient method that is equipped with explicit bounds on the approximation error. We further demonstrate how the presented scheme can be used for approximating the chemical master equation through the zero-information moment closure method, and for an approximate dynamic programming approach in the context of constrained Markov decision processes with uncountable state and action spaces.

JMLR Other · 发表于 2019

Gaussian Processes with Linear Operator Inequality Constraints

Christian Agrell

摘要

This paper presents an approach for constrained Gaussian Process (GP) regression where we assume that a set of linear transformations of the process are bounded. It is motivated by machine learning applications for high-consequence engineering systems, where this kind of information is often made available from phenomenological knowledge. We consider a GP $f$ over functions on $\mathcal{X} \subset \mathbb{R}^{n}$ taking values in $\mathbb{R}$, where the process $linop f$ is still Gaussian when $linop $ is a linear operator. Our goal is to model $f$ under the constraint that realizations of $linop f$ are confined to a convex set of functions. In particular, we require that $a \leq linop f \leq b$, given two functions $a$ and $b$ where $a < b$ pointwise. This formulation provides a consistent way of encoding multiple linear constraints, such as shape-constraints based on e.g. boundedness, monotonicity or convexity. We adopt the approach of using a sufficiently dense set of virtual observation locations where the constraint is required to hold, and derive the exact posterior for a conjugate likelihood. The results needed for stable numerical implementation are derived, together with an efficient sampling scheme for estimating the posterior process.

Econometrica Econometrics & Economics · 发表于 2019

From Aggregate Betting Data to Individual Risk Preferences

Pierre-André Chiappori, Bernard Salanié, François Salanié, Amit Gandhi

摘要

We show that even in the absence of data on individual decisions, the distribution of individual attitudes towards risk can be identified from the aggregate conditions that characterize equilibrium on markets for risky assets. Taking parimutuel horse races as a textbook model of contingent markets, we allow for heterogeneous bettors with very general risk preferences, including non-expected utility. Under a standard single-crossing condition on preferences, we identify the distribution of preferences among the population of bettors and we derive testable implications. We estimate the model on data from U.S. races. Specifications based on expected utility fit the data very poorly. Our results stress the crucial importance of nonlinear probability weighting. They also suggest that several dimensions of heterogeneity may be at work. *(abstract via OpenAlex)*

JMLR High-Dimensional · 发表于 2019

Forward-Backward Selection with Early Dropping

Giorgos Borboudakis, Ioannis Tsamardinos

摘要

Forward-backward selection is one of the most basic and commonly-used feature selection algorithms available. It is also general and conceptually applicable to many different types of data. In this paper, we propose a heuristic that significantly improves its running time, while preserving predictive performance. The idea is to temporarily discard the variables that are conditionally independent with the outcome given the selected variable set. Depending on how those variables are reconsidered and reintroduced, this heuristic gives rise to a family of algorithms with increasingly stronger theoretical guarantees. In distributions that can be faithfully represented by Bayesian networks or maximal ancestral graphs, members of this algorithmic family are able to correctly identify the Markov blanket in the sample limit. In experiments we show that the proposed heuristic increases computational efficiency by about 1-2 orders of magnitude, while selecting fewer or the same number of variables and retaining predictive performance. Furthermore, we show that the proposed algorithm and feature selection with LASSO perform similarly when restricted to select the same number of variables, making the proposed algorithm an attractive alternative for problems where no (efficient) algorithm for LASSO exists.

Econometrica Networks & Graphs · 发表于 2019

Fixed‐Effect Regressions on Network Data

Koen Jochmans, Martin Weidner

摘要

This paper considers inference on fixed effects in a linear regression model estimated from network data. An important special case of our setup is the two‐way regression model. This is a workhorse technique in the analysis of matched data sets, such as employer–employee or student–teacher panel data. We formalize how the structure of the network affects the accuracy with which the fixed effects can be estimated. This allows us to derive sufficient conditions on the network for consistent estimation and asymptotically valid inference to be possible. Estimation of moments is also considered. We allow for general networks and our setup covers both the dense and the sparse case. We provide numerical results for the estimation of teacher value‐added models and regressions with occupational dummies.

JMLR Other · 发表于 2019

Fast Automatic Smoothing for Generalized Additive Models

Yousra El-Bachir, Anthony C. Davison

摘要

Generalized additive models (GAMs) are regression models wherein parameters of probability distributions depend on input variables through a sum of smooth functions, whose degrees of smoothness are selected by $L_2$ regularization. Such models have become the de-facto standard nonlinear regression models when interpretability and flexibility are required, but reliable and fast methods for automatic smoothing in large data sets are still lacking. We develop a general methodology for automatically learning the optimal degree of $L_2$ regularization for GAMs using an empirical Bayes approach. The smooth functions are penalized by hyper-parameters that are learned simultaneously by maximization of a marginal likelihood using an approximate expectation-maximization algorithm. The latter involves a double Laplace approximation at the E-step, and leads to an efficient M-step. Empirical analysis shows that the resulting algorithm is numerically stable, faster than the best existing methods and achieves state-of-the-art accuracy. For illustration, we apply it to an important and challenging problem in the analysis of extremal data.

JMLR Other · 发表于 2019

Fairness Constraints: A Flexible Approach for Fair Classification

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, Krishna P. Gummadi

摘要

Algorithmic decision making is employed in an increasing number of real-world applicationstions to aid human decision making. While it has shown considerable promise in terms of improved decision accuracy, in some scenarios, its outcomes have been also shown to impose an unfair (dis)advantage on people from certain social groups (e.g., women, blacks). In this context, there is a need for computational techniques to limit unfairness in algorithmic decision making. In this work, we take a step forward to fulfill that need and introduce a flexible constraint-based framework to enable the design of fair margin-based classifiers. The main technical innovation of our framework is a general and intuitive measure of decision boundary unfairness, which serves as a tractable proxy to several of the most popular computational definitions of unfairness from the literature. Leveraging our measure, we can reduce the design of fair margin-based classifiers to adding tractable constraints on their decision boundaries. Experiments on multiple synthetic and real-world datasets show that our framework is able to successfully limit unfairness, often at a small cost in terms of accuracy.

Econometrica Longitudinal Data Nonparametric & Semiparametric · 发表于 2019

Exclusion Restrictions in Dynamic Binary Choice Panel Data Models: Comment on “Semiparametric Binary Choice Panel Data Models Without Strictly Exogenous Regressors”

Songnian Chen, Shakeeb Khan, Xun Tang

摘要

In this note we revisit the use of exclusion restrictions in the semiparametric binary choice panel data model introduced in Honore and Lewbel (2002). We show that in a dynamic panel data setting (where one of the pre-determined explanatory variables is the lagged dependent variable), the exclusion restriction in Honore and Lewbel (2002) implicitly re- quires serial independence condition on an observed regressor, that if violated in the data will result in their procedure being inconsistent. We propose a new identification strategy and estimation procedure for the semiparametric binary panel data model under exclusion restrictions that accommodate the serial correlation of observed regressors in a dynamic setting. The new estimator converges at the parametric rate to a limiting normal distribution. This rate is faster than the nonparametric rates of existing alternative estimators for the binary choice panel data model, including the static case in Manski (1987) and the dynamic case in Honore and Kyriazidou (2000). *(abstract via OpenAlex)*

JMLR Networks & Graphs Latent Variables & Mixtures · 发表于 2019

Exact Clustering of Weighted Graphs via Semidefinite Programming

Aleksis Pirinen, Brendan Ames

摘要

As a model problem for clustering, we consider the densest $k$-disjoint-clique problem of partitioning a weighted complete graph into $k$ disjoint subgraphs such that the sum of the densities of these subgraphs is maximized. We establish that such subgraphs can be recovered from the solution of a particular semidefinite relaxation with high probability if the input graph is sampled from a distribution of clusterable graphs. Specifically, the semidefinite relaxation is exact if the graph consists of \(k\) large disjoint subgraphs, corresponding to clusters, with weight concentrated within these subgraphs, plus a moderate number of nodes not belonging to any cluster. Further, we establish that if noise is weakly obscuring these clusters, i.e, the between-cluster edges are assigned very small weights, then we can recover significantly smaller clusters. For example, we show that in approximately sparse graphs, where the between-cluster weights tend to zero as the size $n$ of the graph tends to infinity, we can recover clusters of size polylogarithmic in $n$ under certain conditions on the distribution of edge weights. Empirical evidence from numerical simulations is also provided to support these theoretical phase transitions to perfect recovery of the cluster structure.

Econometrica Causal Inference Econometrics & Economics · 发表于 2019

Estimation of an Equilibrium Model With Externalities: Post‐Disaster Neighborhood Rebuilding

Chao Fu, Jesse Gregory

摘要

We study the optimal design of subsidies in an equilibrium setting, where the decisions of individual recipients impose externalities on one another. We apply the model to the case of post‐Katrina rebuilding in New Orleans under the Louisiana Road Home rebuilding grant program (RH). We estimate the structural model via indirect inference, exploiting a discontinuity in the formula for determining the size of grants, which helps isolate the causal effect of neighbors' rebuilding on one's own rebuilding choices. We find that the additional rebuilding induced by RH generated positive externalities equivalent to $4950 to each inframarginal household whose rebuilding choice was not affected by the program. Counterfactual policy experiments find that optimal subsidy policies bias grant offers against relocation, with an inverse‐U‐shaped relationship between the degree of bias and the severity of damages from the disaster.

Biometrics Clinical Trials Testing & Uncertainty · 发表于 2019

Equivalence of regression curves sharing common parameters

Kathrin Möllenhoff, Frank Bretz, Holger Dette

摘要

In clinical trials, the comparison of two different populations is a common problem. Nonlinear (parametric) regression models are commonly used to describe the relationship between covariates, such as concentration or dose, and a response variable in the two groups. In some situations, it is reasonable to assume some model parameters to be the same, for instance, the placebo effect or the maximum treatment effect. In this paper, we develop a (parametric) bootstrap test to establish the similarity of two regression curves sharing some common parameters. We show by theoretical arguments and by means of a simulation study that the new test controls its significance level and achieves a reasonable power. Moreover, it is demonstrated that under the assumption of common parameters, a considerably more powerful test can be constructed compared with the test that does not use this assumption. Finally, we illustrate the potential applications of the new methodology by a clinical trial example.

Econometrica Econometrics & Economics · 发表于 2019

Equivalence of Stochastic and Deterministic Mechanisms

Yi-Chun Chen, Wei He, Jiangtao Li, Yeneng Sun

摘要

We consider a general social choice environment that has multiple agents, a finite set of alternatives, independent types, and atomless type distribution. We show that for any Bayesian incentive compatible mechanism, there exists an equivalent deterministic mechanism that (1) is Bayesian incentive compatible; (2) delivers the same interim expected allocation probabilities and the same interim expected utilities for all agents; and (3) delivers the same ex ante expected social surplus. This result holds in settings with a rich class of utility functions, multidimensional types, interdependent valuations, and in settings without monetary transfers. To prove our result, we develop a novel methodology of mutual purification, and establish its link with the mechanism design literature.

第 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 页