The problem of hierarchical clustering items from pairwise similarities is found across various scientific disciplines, from biology to networking. Often, applications of clustering techniques are limited by the cost of obtaining similarities between pairs of items. While prior work has been developed to reconstruct clustering using a significantly reduced set of pairwise similarities via adaptive measurements, these techniques are only applicable when choice of similarities are available to the user. In this paper, we examine reconstructing hierarchical clustering under similarity observations at-random. We derive precise bounds which show that a significant fraction of the hierarchical clustering can be recovered using fewer than all the pairwise similarities. We find that the correct hierarchical clustering down to a constant fraction of the total number of items (i.e., clusters sized O(N)) can be found using only O(N log N) randomly selected pairwise similarities in expectation.

Case vs control comparisons have been the classical approach to the study of neurological diseases. However, most patients will not fall cleanly into either group. Instead, clinicians will typically find patients that cannot be classified as having clearly progressed into the disease state. For those subjects, very little can be said about their brain function on the basis of analyses of group differences. To describe the intermediate brain function requires models that interpolate between the disease states. We have chosen Gaussian Processes (GP) regression to obtain a continuous spectrum of brain activation and to extract the unknown disease progression profile. Our models incorporate spatial distribution of measures of activation, e.g. the correlation of an fMRI trace with an input stimulus, and so constitute ultra-high multi-variate GP regressors. We applied GPs to model fMRI image phenotypes across Alzheimer's Disease (AD) behavioural measures, e.g. MMSE, ACE etc. scores, and obtained predictions at non-observed MMSE/ACE values. The overall model confirmed the known reduction in the spatial extent of activity in response to reading versus false-font stimulation. The predictive uncertainty indicated the worsening confidence intervals at behavioural scores distance from those used for GP training. Thus, the model indicated the type of patient (what behavioural score) that would need to included in the training data to improve models predictions.

A lot of effort has been invested into characterizing the convergence rates of gradient based algorithms for non-linear convex optimization. Recently, motivated by large datasets and problems in machine learning, the interest has shifted towards distributed optimization. In this work we present a distributed algorithm for strongly convex constrained optimization. Each node in a network of n computers converges to the optimum of a strongly convex, L-Lipchitz continuous, separable objective at a rate O(log (sqrt(n) T) / T) where T is the number of iterations. This rate is achieved in the online setting where the data is revealed one at a time to the nodes, and in the batch setting where each node has access to its full local dataset from the start. The same convergence rate is achieved in expectation when the subgradients used at each node are corrupted with additive zero-mean noise.

We present four methods for recovering the epipolar geometry from images of smooth surfaces. In the existing methods for recovering epipolar geometry corresponding feature points are used that cannot be found in such images. The first method is based on finding corresponding characteristic points created by illumination (ICPM - illumination characteristic points' method (PM)). The second method is based on correspondent tangency points created by tangents from epipoles to outline of smooth bodies (OTPM - outline tangent PM). These two methods are exact and give correct results for real images, because positions of the corresponding illumination characteristic points and corresponding outline are known with small errors. But the second method is limited either to special type of scenes or to restricted camera motion. We also consider two more methods which are termed CCPM (curve characteristic PM) and CTPM (curve tangent PM), for searching epipolar geometry for images of smooth bodies based on a set of level curves with constant illumination intensity. The CCPM method is based on searching correspondent points on isophoto curves with the help of correlation of curvatures between these lines. The CTPM method is based on property of the tangential to isophoto curve epipolar line to map into the tangential to correspondent isophoto curves epipolar line. The standard method (SM) based on knowledge of pairs of the almost exact correspondent points. The methods have been implemented and tested by SM on pairs of real images. Unfortunately, the last two methods give us only a finite subset of solutions including "good" solution. Exception is "epipoles in infinity". The main reason is inaccuracy of assumption of constant brightness for smooth bodies. But outline and illumination characteristic points are not influenced by this inaccuracy. So, the first pair of methods gives exact results.

Stochastic optimization algorithms have many desirable features for large-scale machine learning, and accordingly have been the focus of renewed and intensive study in the last several years (e.g., see the papers [26, 4, 10, 30] and references therein). The empirical efficiency of these methods is backed with strong theoretical guarantees, providing sharp bounds on their convergence rates. These convergence rates are known to depend on the structure of the underlying objective function, with faster rates being possible for objective functions that are smooth and/or (strongly) convex, or optima that have desirable features such as sparsity. More precisely, for an objective function that is strongly convex, stochastic gradient descent enjoys a convergence rate ranging from O(1/T), when features vectors are extremely sparse, to O(d/T) when feature vectors are dense [11, 19, 12]. Such results are of significant interest, because the strong convexity condition is satisfied for many common machine learning problems, including boosting, least squares regression, support vector machines and generalized linear models, among other examples. A complementary type of condition is that of sparsity, either exact or approximate, in the optimal solution.

Many models of interest in the natural and social sciences have no closed-form likelihood function, which means that they cannot be treated using the usual techniques of statistical inference. In the case where such models can be efficiently simulated, Bayesian inference is still possible thanks to the Approximate Bayesian Computation (ABC) algorithm. Although many refinements have been suggested, ABC inference is still far from routine. ABC is often excruciatingly slow due to very low acceptance rates. In addition, ABC requires introducing a vector of "summary statistics", the choice of which is relatively arbitrary, and often require some trial and error, making the whole process quite laborious for the user. We introduce in this work the EP-ABC algorithm, which is an adaptation to the likelihood-free context of the variational approximation algorithm known as Expectation Propagation (Minka, 2001). The main advantage of EP-ABC is that it is faster by a few orders of magnitude than standard algorithms, while producing an overall approximation error which is typically negligible. A second advantage of EP-ABC is that it replaces the usual global ABC constraint on the vector of summary statistics computed on the whole dataset, by n local constraints of the form that apply separately to each data-point. As a consequence, it is often possible to do away with summary statistics entirely. In that case, EP-ABC approximates directly the evidence (marginal likelihood) of the model. Comparisons are performed in three real-world applications which are typical of likelihood-free inference, including one application in neuroscience which is novel, and possibly too challenging for standard ABC techniques.

Precision-recall (PR) curves and the areas under them are widely used to summarize machine learning results, especially for data sets exhibiting class skew. They are often used analogously to ROC curves and the area under ROC curves. It is known that PR curves vary as class skew changes. What was not recognized before this paper is that there is a region of PR space that is completely unachievable, and the size of this region depends only on the skew. This paper precisely characterizes the size of that region and discusses its implications for empirical evaluation methodology in machine learning.

Many fundamental problems in artificial intelligence, knowledge representation, and verification involve reasoning about sets and relations between sets and can be modeled as set constraint satisfaction problems (set CSPs). Such problems are frequently intractable, but there are several important set CSPs that are known to be polynomial-time tractable. We introduce a large class of set CSPs that can be solved in quadratic time. Our class, which we call EI, contains all previously known tractable set CSPs, but also some new ones that are of crucial importance for example in description logics. The class of EI set constraints has an elegant universal-algebraic characterization, which we use to show that every set constraint language that properly contains all EI set constraints already has a finite sublanguage with an NP-hard constraint satisfaction problem.

SAR sensors work on the microwaves spectrum, so they are almost immune to adverse weather conditions and they are able to penetrate, to some extent, the surface of certain targets. The first civilian SAR satellite was launched in 1978, and it was followed by a constellation of other similar sensors, mostly devoted to specific applications and in all cases operated at a single frequency and polarization. The Shuttle Imaging Radar-C/X-band SAR (SIRC/XSAR), launched in 1994, could be operated simultaneously at three frequencies, with two of them able to transmit and receive at both horizontal and vertical polarization. This polarimetric capability provides a more complete description of the target [46]. Polarimetric images are multiple complex-valued data sets requiring, thus, specialized models and algorithms.

In 1998, it was proved by Ben-David and Litman that a concept space has a sample compression scheme of size d if and only if every finite subspace has a sample compression scheme of size d. In the compactness theorem, measurability of the hypotheses of the created sample compression scheme is not guaranteed; at the same time measurability of the hypotheses is a necessary condition for learnability. In this thesis we discuss when a sample compression scheme, created from compression schemes on finite subspaces via the compactness theorem, have measurable hypotheses. We show that if X is a standard Borel space with a d-maximum and universally separable concept class C, then (X, C) has a sample compression scheme of size d with universally Borel measurable hypotheses. Additionally we introduce a new variant of compression scheme called a copy sample compression scheme.