Universal Dependency Analysis

Most data is multi-dimensional. Discovering whether any subset of dimensions, or subspaces, of such data is significantly correlated is a core task in data mining. To do so, we require a measure that quantifies how correlated a subspace is. For practical use, such a measure should be universal in the sense that it captures correlation in subspaces of any dimensionality and allows to meaningfully compare correlation scores across different subspaces, regardless how many dimensions they have and what specific statistical properties their dimensions possess. Further, it would be nice if the measure can non-parametrically and efficiently capture both linear and non-linear correlations. In this paper, we propose UDS, a multivariate correlation measure that fulfills all of these desiderata. In short, we define \uds based on cumulative entropy and propose a principled normalization scheme to bring its scores across different subspaces to the same domain, enabling universal correlation assessment. UDS is purely non-parametric as we make no assumption on data distributions nor types of correlation. To compute it on empirical data, we introduce an efficient and non-parametric method. Extensive experiments show that UDS outperforms state of the art.


Linear-time Detection of Non-linear Changes in Massively High Dimensional Time Series

Change detection in multivariate time series has applications in many domains, including health care and network monitoring. A common approach to detect changes is to compare the divergence between the distributions of a reference window and a test window. When the number of dimensions is very large, however, the naive approach has both quality and efficiency issues: to ensure robustness the window size needs to be large, which not only leads to missed alarms but also increases runtime. To this end, we propose LIGHT, a linear-time algorithm for robustly detecting non-linear changes in massively high dimensional time series. Importantly, LIGHT provides high flexibility in choosing the window size, allowing the domain expert to fit the level of details required. To do such, we 1) perform scalable PCA to reduce dimensionality, 2) perform scalable factorization of the joint distribution, and 3) scalably compute divergences between these lower dimensional distributions. Extensive empirical evaluation on both synthetic and real-world data show that LIGHT outperforms state of the art with up to 100% improvement in both quality and efficiency.


Flexibly Mining Better Subgroups

In subgroup discovery, also known as supervised pattern mining, discovering high quality one-dimensional subgroups and refinements of these is a crucial task. For nominal attributes, this is relatively straightforward, as we can consider individual attribute values as binary features. For numerical attributes, the task is more challenging as individual numeric values are not reliable statistics. Instead, we can consider combinations of adjacent values, i.e. bins. Existing binning strategies, however, are not tailored for subgroup discovery. That is, they do not directly optimize for the quality of subgroups, therewith potentially degrading the mining result. To address this issue, we propose FLEXI. In short, with FLEXI we propose to use optimal binning to find high quality binary features for both numeric and ordinal attributes. We instantiate FLEXI with various quality measures and show how to achieve efficiency accordingly. Experiments on both synthetic and real-world data sets show that FLEXI outperforms state of the art with up to 25 times improvement in subgroup quality.


Canonical Divergence Analysis

We aim to analyze the relation between two random vectors that may potentially have both different number of attributes as well as realizations, and which may even not have a joint distribution. This problem arises in many practical domains, including biology and architecture. Existing techniques assume the vectors to have the same domain or to be jointly distributed, and hence are not applicable. To address this, we propose Canonical Divergence Analysis (CDA). We introduce three instantiations, each of which permits practical implementation. Extensive empirical evaluation shows the potential of our method.


Operator-valued Kernels for Learning from Functional Response Data

In this paper we consider the problems of supervised classification and regression in the case where attributes and labels are functions: a data is represented by a set of functions, and the label is also a function. We focus on the use of reproducing kernel Hilbert space theory to learn from such functional data. Basic concepts and properties of kernel-based learning are extended to include the estimation of function-valued functions. In this setting, the representer theorem is restated, a set of rigorously defined infinite-dimensional operator-valued kernels that can be valuably applied when the data are functions is described, and a learning algorithm for nonlinear functional data analysis is introduced. The methodology is illustrated through speech and audio signal processing experiments.


Clustering Via Finite Nonparametric ICA Mixture Models

We propose an extension of non-parametric multivariate finite mixture models by dropping the standard conditional independence assumption and incorporating the independent component analysis (ICA) structure instead. We formulate an objective function in terms of penalized smoothed Kullback Leibler distance and introduce the nonlinear smoothed majorization-minimization independent component analysis (NSMM-ICA) algorithm for optimizing this function and estimating the model parameters. We have implemented a practical version of this algorithm, which utilizes the FastICA algorithm, in the R package icamix. We illustrate this new methodology using several applications in unsupervised learning and image processing.


Priors on exchangeable directed graphs

Stochastic control for a class of nonlinear kernels and applications

Second Order Calibration: A Simple Way to Get Approximate Posteriors

Hilbert series and degree bounds for matrix (semi-)invariants

Fast k-best Sentence Compression

Intersections of Amoebas

Toroidal boards and code covering

Fast Landmark Subspace Clustering

Betti-linear Ideals

The Generalized Marshall-Olkin-Kumaraswamy-G family of distributions

A Central Limit Theorem for Operators

Completeness of cubic curves in PG(2, q), q <= 81

Extremal graph for intersecting odd cycles

A polynomial expansion line search for large-scale unconstrained minimization of smooth L2-regularized loss functions, with implementation in Apache Spark

Fault-tolerant parallel-in-time integration with PFASST

On the dual problem of utility maximization in incomplete markets

Level repulsion exponent $β$ for Many-Body Localization Transitions and for Anderson Localization Transitions via Dyson Brownian Motion

Lévy Processes on Quantum Permutation Groups

Trees on hyperbolic honeycombs

Numerical solving unsteady space-fractional problems with the square root of an elliptic operator

Linear Shape Deformation Models with Local Support Using Graph-based Structured Matrix Factorisation

The corrector in stochastic homogenization: Near-optimal rates with optimal stochastic integrability

Homotopy Theory of Probability Spaces I: Classical independence and homotopy Lie algebras

Sobolev spaces with respect to weighted Gaussian measures in infinite dimensions

Optimal two-level choice designs for the main effects and specified interaction effects model

Approximate Association via Dissociation

Testing Cyclic Level and Simultaneous Level Planarity

Graph properties in node-query setting: effect of breaking symmetry

Computing the Ramsey Number R(4,3,3) using Abstraction and Symmetry breaking

Almost simplicial polytopes I. The lower and upper bound theorems

On global fluctuations for non-colliding processes

On convex hull and winding number of self similar processes

Time-frequency and time-scale analysis of deformed stationary processes, with application to non-stationary sound modeling

About the analogy between optimal transport and minimal entropy

Asymptotic expansion of the risk of maximum likelihood estimator with respect to $α$-divergence as a measure of the difficulty of specifying a parametric model –with detailed proof

On vanishing patterns in $j$-strands of edge ideals

Minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays

On two $q$-ary $n$-cube coloring problems

Floating-strike Asian options with regime-switching

A position in infinite chess with game value $ω^4$

A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion

Establishing consistency and improving uncertainty estimates of variational inference through M-estimation

Cayley graphs and automatic sequences

Interatomic repulsion softness directly controls the fragility of supercooled metallic melts

Words containing all permutations of a family of factors

Spectral Convergence Rate of Graph Laplacian

Online Learning with Gaussian Payoffs and Side Observations

Can 3D light localization be reached in ‘white paint’?

Advertisements