Robust non-linear regression analysis: A greedy approach employing kernels and application to image denoising

We consider the task of robust non-linear estimation in the presence of both bounded noise and outliers. Assuming that the unknown non-linear function belongs to a Reproducing Kernel Hilbert Space (RKHS), our goal is to accurately estimate the coefficients of the kernel regression matrix. Due to the existence of outliers, common techniques such as the Kernel Ridge Regression (KRR), or the Support Vector Regression (SVR) turn out to be inadequate. Instead, we employ sparse modeling arguments to model and estimate the outliers, adopting a greedy approach. In particular, the proposed robust scheme, i.e., Kernel Greedy Algorithm for Robust Denoising (KGARD), is a modification of the classical Orthogonal Matching Pursuit (OMP) algorithm. In a nutshell, the proposed scheme alternates between a KRR task and an OMP-like selection step. Convergence properties as well as theoretical results concerning the identification of the outliers are provided. Moreover, KGARD is compared against other cutting edge methods (using toy examples) to demonstrate its performance and verify the aforementioned theoretical results. Finally, the proposed robust estimation framework is applied to the task of image denoising, showing that it can enhance the denoising process significantly, when outliers are present.

A model of interacting multiple choices of continuous opinions

We present a model of interacting multiple choices of opinions. At each step of the process, a listener is persuaded by his/her neighbour, the lobbyist, to modify his/her opinion on two different choices of event. Whether or not the listener will be convinced by the lobbyist depends on the difference between his/her opinion with that of the lobbyist, and with that of the revealed social opinion (the social pressure). If the listener is convinced, he/she will modify his/her opinion and update his/her revealed preference, and proceed to persuade his/her next neighbour. If the listener is not convinced by the lobbyist, he/she will retain his/her revealed preference, and try to persuade the lobbyist to change his/her opinion. In this case, the direction of opinion propagation is reversed. A consensus is reached when all the revealed preference is the same. Our numerical results show that consensus can always be attained in this model. However, the time needed to achieve consensus, or the so-called convergence time, is longer if the listener is more concerned with the public opinion, or is less likely to be influenced by the lobbyist.

Boosted Adaptive Filters

We introduce the boosting notion extensively used in different machine learning applications to adaptive signal processing literature and implement several different adaptive filtering algorithms. In this framework, we have several adaptive filtering algorithms, i.e., the weak learners, that run in parallel on a common task such as equalization, classification, regression or filtering. For each newly received input vector and observation pair, each algorithm adapts itself based on the performance of the other adaptive algorithms in the mixture on this current data pair. These relative updates provide the boosting effect such that the algorithms in the mixture learn a different attribute of the data providing diversity. The outputs of these parallel running algorithms are then combined using adaptive mixture approaches. We demonstrate the intrinsic connections of boosting with the adaptive mixture methods and data reuse algorithms. Specifically, we study parallel running recursive least squares and least mean squares algorithms and provide different boosted versions of these well known adaptation methods. We provide the MSE performance results as well as computational complexity bounds for the boosted adaptive filters. We demonstrate over widely used real life data sets in the machine learning and adaptive signal processing literatures that we can substantially improve the performances of these algorithms due to the boosting effect with a relatively small computational complexity increase.

Motivating Time-Inconsistent Agents: A Computational Approach

In this paper we investigate the computational complexity of motivating time-inconsistent agents to complete long term projects. We resort to an elegant graph-theoretic model, introduced by Kleinberg and Oren, which consists of a task graph G with n vertices, including a source s and target t, and an agent that incrementally constructs a path from s to t in order to collect rewards. The twist is that the agent is present-biased and discounts future costs and rewards by a factor \beta\in [0,1]. Our design objective is to ensure that the agent reaches t i.e.\ completes the project, for as little reward as possible. Such graphs are called motivating. We consider two strategies. First, we place a single reward r at t and try to guide the agent by removing edges from G. We prove that deciding the existence of such motivating subgraphs is NP-complete if r is fixed. More importantly, we generalize our reduction to a hardness of approximation result for computing the minimum r that admits a motivating subgraph. In particular, we show that no polynomial-time approximation to within a ratio of \sqrt{n}/4 or less is possible, unless {\rm P}={\rm NP}. Furthermore, we develop a (1+\sqrt{n})-approximation algorithm and thus settle the approximability of computing motivating subgraphs. Secondly, we study motivating reward configurations, where non-negative rewards r(v) may be placed on arbitrary vertices v of G. The agent only receives the rewards of visited vertices. Again we give an NP-completeness result for deciding the existence of a motivating reward configuration within a fixed budget b. This result even holds if b=0, which in turn implies that no efficient approximation of a minimum b within a ration grater or equal to 1 is possible, unless {\rm P}={\rm NP}.

Regression Discontinuity Designs: A Decision Theoretic Approach

The regression discontinuity design (RDD) is a quasi-experimental design that can be used to identify and estimate the causal effect of a treatment using observational data. In an RDD, a pre-specified rule is used for treatment assignment, whereby a subject is assigned to the treatment (control) group whenever their observed value of a specific continuous variable is greater than or equal to (is less than) a fixed threshold. Sharp RDDs occur when guidelines are strictly adhered to and fuzzy RDDs occur when the guidelines or not strictly adhered to. In this paper, we take a rigorous decision theoretic approach to formally study causal effect identification and estimation in both sharp and fuzzy RDDs. We use the language and calculus of conditional independence to express and explore in a clear and precise manner the conditions implied by each RDD and investigate additional assumptions under which the identification of the average causal effect at the threshold can be achieved. We apply the methodology in an example concerning the relationship between statins (a class of cholesterol-lowering drugs) and low density lipoprotein (LDL) cholesterol using a real set of primary care data.

A Multiresolution Analysis Framework for the Statistical Analysis of Incomplete Rankings

Though the statistical analysis of ranking data has been a subject of interest over the past centuries, especially in economics, psychology or social choice theory, it has been revitalized in the past 15 years by recent applications such as recommender or search engines and is receiving now increasing interest in the machine learning literature. Numerous modern systems indeed generate ranking data, representing for instance ordered results to a query or user preferences. Each such ranking usually involves a small but varying subset of the whole catalog of items only. The study of the variability of these data, i.e. the statistical analysis of incomplete rank-ings, is however a great statistical and computational challenge, because of their heterogeneity and the related combinatorial complexity of the problem. Whereas many statistical methods for analyzing full rankings (orderings of all the items in the catalog) are documented in the dedicated literature, partial rankings (full rankings with ties) or pairwise comparisons, only a few approaches are available today to deal with incomplete ranking, relying each on a strong specific assumption. It is the purpose of this article to introduce a novel general framework for the statistical analysis of incomplete rankings. It is based on a representation tailored to these specific data, whose construction is also explained here, which fits with the natural multi-scale structure of incomplete rankings and provides a new decomposition of rank information with a multiresolu-tion analysis interpretation (MRA). We show that the MRA representation naturally allows to overcome both the statistical and computational challenges without any structural assumption on the data. It therefore provides a general and flexible framework to solve a wide variety of statistical problems, where data are of the form of incomplete rankings.

Interpreting Latent Variables in Factor Models via Convex Optimization

Latent or unobserved phenomena pose a significant difficulty in data analysis as they induce complicated and confounding dependencies among a collection of observed variables. Factor analysis is a prominent multivariate statistical modeling approach that addresses this challenge by identifying the effects of (a small number of) latent variables on a set of observed variables. However, the latent variables in a factor model are purely mathematical objects that are derived from the observed phenomena, and they do not have any interpretation associated to them. A natural approach for attributing semantic information to the latent variables in a factor model is to obtain measurements of some additional plausibly useful covariates that may be related to the original set of observed variables, and to associate these auxiliary covariates to the latent variables. In this paper, we describe a systematic approach for identifying such associations. Our method is based on solving computationally tractable convex optimization problems, and it can be viewed as a generalization of the minimum-trace factor analysis procedure for fitting factor models via convex optimization. We analyze the theoretical consistency of our approach in a high-dimensional setting as well as its utility in practice via experimental demonstrations with real data.

Multimodal Event Detection in Twitter Hashtag Networks

Event detection in a multimodal Twitter dataset is considered. We treat the hashtags in the dataset as instances with two modes: text and geolocation features. The text feature consists of a bag-of-words representation. The geolocation feature consists of geotags (i.e., geographical coordinates) of the tweets. Fusing the multimodal data we aim to detect, in terms of topic and geolocation, the interesting events and the associated hashtags. To this end, a generative latent variable model is assumed, and a generalized expectation-maximization (EM) algorithm is derived to learn the model parameters. The proposed method is computationally efficient, and lends itself to big datasets. Experimental results on a Twitter dataset from August 2014 show the efficacy of the proposed method.

Sentiment/Subjectivity Analysis Survey for Languages other than English

Subjective and sentiment analysis has gained considerable attention recently. Most of the resources and systems built so far are done for English. The need for designing systems for other languages is increasing. This paper surveys different ways used for building systems for subjective and sentiment analysis for languages other than English. There are three different types of systems used for building these systems. The first (and the best) one is the language specific systems. The second type of systems involves reusing or transferring sentiment resources from English to the target language. The third type of methods is based on using language independent methods. The paper presents a separate section devoted to Arabic sentiment analysis.

GPU-Based Fuzzy C-Means Clustering Algorithm for Image Segmentation

In this paper, a fast and practical GPU-based implementation of Fuzzy C-Means (FCM) clustering algorithm for image segmentation is proposed. First, an extensive analysis is conducted to study the dependency among the image pixels in the algorithm for parallelization. The proposed GPU-based FCM has been tested on digital brain simulated dataset to segment white matter(WM), gray matter(GM) and cerebrospinal fluid (CSF) soft tissue regions. The execution time of the sequential FCM is 2798 seconds for an image dataset with the size of 1MB. While the proposed GPU-based FCM requires only 4.2seconds for the similar size of image dataset. An estimated 674-fold superlinear speedup is measured for the data size of 700 KB on a CUDA device that has 448 processors.

On the equivalence of probability spaces

Generalization of Scarpis’s theorem on Hadamard matrices

Approximate Distribution of L1 Median on Uncertain Data

Scalable Models for Computing Hierarchies in Information Networks

Distant IE by Bootstrapping Using Lists and Document Structure

Small drift limit theorems for random walks

Curve arrangements, pencils, and Jacobian syzygies

Multimodal Classification of Events in Social Media

Extrema of log-correlated random variables: Principles and Examples

Triple crystal action in Fock spaces

NFL Play Prediction

Signed tilings by ribbon L-shaped n-ominoes, n even, via Groebner bases

Signed tilings by ribbon L n-ominoes, n odd, via Groebner bases

Hölder continuity of the Liouville Quantum Gravity measure

Approximate Message Passing with Nearest Neighbor Sparsity Pattern Learning

Fractal dimensions of the wavefunctions and local spectral measures on the Fibonacci chain

Programming in logic without logic programming

Quenched localisation in the Bouchaud trap model with regularly varying traps

A central limit theorem for Lebesgue integrals of random fields

Gaussian perturbations of hard edge random matrix ensembles

Tri-connectivity Augmentation in Trees

Learning relationships between data obtained independently

Nonparametric Modeling of Dynamic Functional Connectivity in fMRI Data

Optimal block designs for experiments with responses drawn from a Poisson distribution

A microwave realization of the Gaussian symplectic ensemble

Fitting Spectral Decay with the $k$-Support Norm

On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^2)$

The largest Erdős-Ko-Rado sets in 2-(v,k,1) designs

Codimension two and three Kneser Transversals

The half plane UIPT is recurrent

On the Reducibility of Submodular Functions

A bijective proof of Vershik’s relations for the Kostka numbers

Generalization of Knuth’s formula for the number of skew tableaux

Mutual Information and Diverse Decoding Improve Neural Machine Translation

Sparse Diffusion Steepest-Descent for One Bit Compressed Sensing in Wireless Sensor Networks

Improved Randomized Response Technique for Two Sensitive Attributes

On the cycle structure of the product of random maximal cycles

A Unified Approach for Learning the Parameters of Sum-Product Networks

Noise-induced transitions in a double-well oscillator with nonlinear dissipation

Incidence bounds and applications over finite fields

An Empirical Comparison of Big Graph Frameworks in the Context of Network Analysis

Wavelet Scattering on the Pitch Spiral

Structure-Preserving Sparsification Methods for Social Networks

Treelike quintet systems

Firefighting on Trees Beyond Integrality Gaps

Infinite Horizon Risk-Sensitive Control of Diffusions Without Any Blanket Stability Assumptions

Euler characteristic reciprocity for chromatic and order polynomials

Contrastive Perplexity: A new evaluation metric for sentence level language models

Layering $\partial$-Graphs and Networks

Dimensionality-Dependent Generalization Bounds for $k$-Dimensional Coding Schemes

Assessing Time-Varying Causal Effect Moderation in Mobile Health

Supervised Dimensionality Reduction via Distance Correlation Maximization

Height restricted lattice paths, Elenas, and bijections

Identifying the Optimal Integration Time in Hamiltonian Monte Carlo

Faster GPU Based Genetic Programming Using A Two Dimensional Stack

The generalized master fields

Current status linear regression

An Improved Intelligent Agent for Mining Real-Time Databases Using Modified Cortical Learning Algorithms

Moduli space of families of positive $(n-1)$-weights

Implementing Brouwer’s database of strongly regular graphs

Counting lattice points in free sums of polytopes

Universality in the mean spatial shape of avalanches

Universal constructions for spaces of traffics

On a generalization of Nemhauser and Trotter’s local optimization theorem

A Parameterized algorithm for Bounded-Degree Vertex Deletion

PI : a Parallel in-memory skip list based Index

Asymptotic behavior of the Laplacian quasi-maximum likelihood estimator of affine causal processes

Joint Estimation of Precision Matrices in Heterogeneous Populations

The Reduced-Order Hybrid Monte Carlo Sampling Smoother

Stability and bifurcation properties of the algorithms for keeping of differential equations solutions on the required level

A Characterization of the Normal Distribution by the Independence of a Pair of Random Vectors

Beyond linear elasticity: Jammed solids at finite shear strain and rate

A characterization of tightly triangulated 3-manifolds

Practical Algorithms for Learning Near-Isometric Linear Embeddings

Combinatorial Formulas for Certain Sequences of Multiple Numbers

Stochastic Neural Networks with Monotonic Activation Functions

Neighborhood covering and independence on two superclasses of cographs