Local Rademacher complexities

We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical version of Rademacher averages, in the sense that the Rademacher averages are computed from the data, on a subset of functions with small empirical error. We present some applications to classification and prediction with convex function classes, and with kernel classes in particular.

Classification with a reject option using a hinge loss

We consider the problem of binary classification where the classifier can, for a particular cost, choose not to classify an observation. Just as in the conventional classification problem, minimization of the sample average of the cost is a difficult optimization problem. As an alternative, we propose the optimization of a certain convex loss function φ, analogous to the hinge loss used in support vector machines (SVMs). Its convexity ensures that the sample average of this surrogate loss can be efficiently minimized. We study its statistical properties. We show that minimizing the expected surrogate loss—the φ-risk—also minimizes the risk. We also study the rate at which the φ-risk approaches its minimum value. We show that fast rates are possible when the conditional probability P(Y=1|X) is unlikely to be close to certain critical values.

Exponentiated gradient algorithms for conditional random fields and max-margin Markov Networks

Log-linear and maximum-margin models are two commonly-used methods in supervised machine learning, and are frequently used in structured prediction problems. Efficient learning of parameters in these models is therefore an important problem, and becomes a key factor when learning from very large data sets. This paper describes exponentiated gradient (EG) algorithms for training such models, where EG updates are applied to the convex dual of either the log-linear or max-margin objective function; the dual in both the log-linear and max-margin cases corresponds to minimizing a convex function with simplex constraints. We study both batch and online variants of the algorithm, and provide rates of convergence for both cases. In the max-margin case, O(1/ε) EG updates are required to reach a given accuracy ε in the dual; in contrast, for log-linear models only O(log(1/ε)) updates are required. For both the max-margin and log-linear cases, our bounds suggest that the online EG algorithm requires a factor of n less computation to reach a desired accuracy than the batch EG algorithm, where n is the number of training examples. Our experiments confirm that the online algorithms are much faster than the batch algorithms in practice. We describe how the EG updates factor in a convenient way for structured prediction problems, allowing the algorithms to be efficiently applied to problems such as sequence learning or natural language parsing. We perform extensive evaluation of the algorithms, comparing them to L-BFGS and stochastic gradient descent for log-linear models, and to SVM-Struct for max-margin models. The algorithms are applied to a multi-class problem as well as to a more complex large-scale parsing task. In all these settings, the EG algorithms presented here outperform the other methods.

Sparseness vs estimating conditional probabilities : some asymptotic results

One of the nice properties of kernel classifiers such as SVMs is that they often produce sparse solutions. However, the decision functions of these classifiers cannot always be used to estimate the conditional probability of the class label. We investigate the relationship between these two properties and show that these are intimately related: sparseness does not occur when the conditional probabilities can be unambiguously estimated. We consider a family of convex loss functions and derive sharp asymptotic results for the fraction of data that becomes support vectors. This enables us to characterize the exact trade-off between sparseness and the ability to estimate conditional probabilities for these loss functions.

Adaptive online gradient descent

We study the rates of growth of the regret in online convex optimization. First, we show that a simple extension of the algorithm of Hazan et al eliminates the need for a priori knowledge of the lower bound on the second derivatives of the observed functions. We then provide an algorithm, Adaptive Online Gradient Descent, which interpolates between the results of Zinkevich for linear functions and of Hazan et al for strongly convex functions, achieving intermediate rates between [square root T] and [log T]. Furthermore, we show strong optimality of the algorithm. Finally, we provide an extension of our results to general norms.

Learning the Kernel Matrix with Semi-Definite Programming

Kernel-based learning algorithms work by embedding the data into a Euclidean space, and then searching for linear relations among the embedded data points. The embedding is performed implicitly, by specifying the inner products between each pair of points in the embedding space. This information is contained in the so-called kernel matrix, a symmetric and positive definite matrix that encodes the relative positions of all points. Specifying this matrix amounts to specifying the geometry of the embedding space and inducing a notion of similarity in the input space -- classical model selection problems in machine learning. In this paper we show how the kernel matrix can be learned from data via semi-definite programming (SDP) techniques. When applied to a kernel matrix associated with both training and test data this gives a powerful transductive algorithm -- using the labelled part of the data one can learn an embedding also for the unlabelled part. The similarity between test points is inferred from training points and their labels. Importantly, these learning problems are convex, so we obtain a method for learning both the model class and the function without local minima. Furthermore, this approach leads directly to a convex method to learn the 2-norm soft margin parameter in support vector machines, solving another important open problem. Finally, the novel approach presented in the paper is supported by positive empirical results.

Ocular characteristics in myopic anisometropia

PURPOSE: To investigate the interocular symmetry of ocular optical, biometric and biomechanical characteristics between the more and less ametropic eyes of myopic anisometropes. METHODS: Thirty-four young, healthy myopic anisometropic adults (≥ 1 D spherical equivalent difference between eyes) without amblyopia or strabismus were recruited. A range of biometric and optical parameters were measured in the more and less ametropic eye of each subject including; axial length, ocular aberrations, intraocular pressure and corneal topography, thickness and biomechanics. Morphology of the anterior eye in primary and downward gaze was examined using custom software analysis of high resolution digital images. Ocular sighting dominance was assessed using the hole-in-the-card test. RESULTS: Mean absolute spherical equivalent anisometropia was 1.74 ± 0.74 D. There was a strong correlation between the degree of anisometropia and the interocular difference in axial length (r = 0.81, p < 0.001). The more and less ametropic fellow eyes displayed a high degree of interocular symmetry for the majority of biometric, biomechanical and optical parameters measured. When the level of anisometropia exceeded 1.75 D (n = 10), the more myopic eye was the dominant sighting eye in nine of these ten subjects. Subjects with greater levels of anisometropia (> 1.75 D) also showed high levels of correlation between the dominant and non-dominant eyes in their biometric, biomechanical and optical characteristics. CONCLUSIONS: Although significantly different in axial length, anisometropic eyes display a high degree of interocular symmetry for a range of anterior eye biometrics and optical parameters. For higher levels of anisometropia, the more myopic eye tends to be the dominant sighting eye.

Myopia and peripheral ocular aberrations

We measured wave aberrations over the central 42° x 32° visual field for a 5 mm pupil for groups of 10 emmetropic (mean spherical equivalent 0.11 ± 0.50 D) and 9 myopic (MSE -3.67 ± 1.91 D) young adults. Relative peripheral refractive errors over the measured field were generally myopic in both groups. Mean values of were almost constant across the measured field and were more positive in emmetropes (+0.023 ± 0.043 microns) than in myopes (-0.007 ± 0.045 microns). Coma varied more rapidly with field angle in myopes: modeling suggested that this difference reflected the differences in mean anterior corneal shape and axial length in the two groups. In general however, overall levels of RMS aberration differed only modestly between the two groups, implying that it is unlikely that high levels of aberration contribute to myopia development.

Effect of accommodation on peripheral ocular aberrations

Changes in peripheral aberrations, particularly higher-order aberrations, as a function of accommodation have received little attention. Wavefront aberrations were measured for the right eyes of 9 young adult emmetropes at 38 field positions in the central 42 x 32 degrees of the visual field. Subjects accommodated monocularly to targets at vergences of either 0.3 or 4.0 D. Wavefront data for a 5 mm diameter pupil were analyzed either in terms of the vector components of refraction or Zernike coefficients and total RMS wavefront aberrations. Relative peripheral refractive error (RPRE) was myopic at both accommodation demands and showed only a slight, not statistically significant, hypermetropic shift in the vertical meridian with the higher accommodation demand. There was little change in the astigmatic components of refraction or the higher-order Zernike coefficients, apart from fourth-order spherical aberration which became more negative (by 0.10 µm) at all field locations. Although it has been suggested that nearwork and the state of peripheral refraction may play some role in myopia development, for most of our adult emmetropes any changes with accommodation in RPRE and aberration were small. Hence it seems unlikely that such changes can be of importance to late-onset myopisation.

Interocular symmetry in myopic anisometropia

Purpose: To investigate the interocular symmetry of optical, biometric and biomechanical characteristics between the fellow eyes of myopic anisometropes. Methods: Thirty-four young, healthy myopic anisometropic adults (≥ 1 D spherical equivalent difference between eyes) without amblyopia or strabismus were recruited. A range of biometric and optical parameters were measured in both eyes of each subject including; axial length, ocular aberrations, intraocular pressure (IOP), corneal topography and biomechanics. Ocular sighting dominance was also measured. Results: Mean absolute spherical equivalent anisometropia was 1.70 ± 0.74 D and there was a strong correlation between the degree of anisometropia and the interocular difference in axial length (r = 0.81, p < 0.001). The more and less myopic eyes displayed a high degree of interocular symmetry for the majority of biometric, biomechanical and optical parameters measured. When the level of anisometropia exceeded 1.75 D, the more myopic eye was more likely to be the dominant sighting eye than for lower levels of anisometropia (p=0.002). Subjects with greater levels of anisometropia (> 1.75 D) also showed high levels of correlation between the dominant and non-dominant eyes in their biometric, biomechanical and optical characteristics. Conclusions: Although significantly different in axial length, anisometropic eyes display a high degree of interocular symmetry for a range of anterior eye biometrics and optical parameters. For higher levels of anisometropia, the more myopic eye tends to be the dominant sighting eye.

Ocular characteristics of anisometropia

Animal models of refractive error development have demonstrated that visual experience influences ocular growth. In a variety of species, axial anisometropia (i.e. a difference in the length of the two eyes) can be induced through unilateral occlusion, image degradation or optical manipulation. In humans, anisometropia may occur in isolation or in association with amblyopia, strabismus or unilateral pathology. Non-amblyopic myopic anisometropia represents an interesting anomaly of ocular growth, since the two eyes within one visual system have grown to different endpoints. These experiments have investigated a range of biometric, optical and mechanical properties of anisometropic eyes (with and without amblyopia) with the aim of improving our current understanding of asymmetric refractive error development. In the first experiment, the interocular symmetry in 34 non-amblyopic myopic anisometropes (31 Asian, 3 Caucasian) was examined during relaxed accommodation. A high degree of symmetry was observed between the fellow eyes for a range of optical, biometric and biomechanical measurements. When the magnitude of anisometropia exceeded 1.75 D, the more myopic eye was almost always the sighting dominant eye. Further analysis of the optical and biometric properties of the dominant and non-dominant eyes was conducted to determine any related factors but no significant interocular differences were observed with respect to best-corrected visual acuity, corneal or total ocular aberrations during relaxed accommodation. Given the high degree of symmetry observed between the fellow eyes during distance viewing in the first experiment and the strong association previously reported between near work and myopia development, the aim of the second experiment was to investigate the symmetry between the fellow eyes of the same 34 myopic anisometropes following a period of near work. Symmetrical changes in corneal and total ocular aberrations were observed following a short reading task (10 minutes, 2.5 D accommodation demand) which was attributed to the high degree of interocular symmetry for measures of anterior eye morphology, and corneal biomechanics. These changes were related to eyelid shape and position during downward gaze, but gave no clear indication of factors associated with near work that might cause asymmetric eye growth within an individual. Since the influence of near work on eye growth is likely to be most obvious during, rather than following near tasks, in the third experiment the interocular symmetry of the optical and biometric changes was examined during accommodation for 11 myopic anisometropes. The changes in anterior eye biometrics associated with accommodation were again similar between the eyes, resulting in symmetrical changes in the optical characteristics. However, the more myopic eyes exhibited slightly greater amounts of axial elongation during accommodation which may be related to the force exerted by the ciliary muscle. This small asymmetry in axial elongation we observed between the eyes may be due to interocular differences in posterior eye structure, given that the accommodative response was equal between eyes. Using ocular coherence tomography a reduced average choroidal thickness was observed in the more myopic eyes compared to the less myopic eyes of these subjects. The interocular difference in choroidal thickness was correlated with the magnitude of spherical equivalent and axial anisometropia. The symmetry in optics and biometrics between fellow eyes which have undergone significantly different visual development (i.e. anisometropic subjects with amblyopia) is also of interest with respect to refractive error development. In the final experiment the influence of altered visual experience upon corneal and ocular higher-order aberrations was investigated in 21 amblyopic subjects (8 refractive, 11 strabismic and 2 form deprivation). Significant differences in aberrations were observed between the fellow eyes, which varied according to the type of amblyopia. Refractive amblyopes displayed significantly higher levels of 4th order corneal aberrations (spherical aberration and secondary astigmatism) in the amblyopic eye compared to the fellow non-amblyopic eye. Strabismic amblyopes exhibited significantly higher levels of trefoil, a third order aberration, in the amblyopic eye for both corneal and total ocular aberrations. The results of this experiment suggest that asymmetric visual experience during development is associated with asymmetries in higher-order aberrations, proportional to the magnitude of anisometropia and dependent upon the amblyogenic factor. This suggests a direct link between the development of higher-order optical characteristics of the human eye and visual feedback. The results from these experiments have shown that a high degree of symmetry exists between the fellow eyes of non-amblyopic myopic anisometropes for a range of biomechanical, biometric and optical parameters for different levels of accommodation and following near work. While a single specific optical or biomechanical factor that is consistently associated with asymmetric refractive error development has not been identified, the findings from these studies suggest that further research into the association between ocular dominance, choroidal thickness and higher-order aberrations with anisometropia may improve our understanding of refractive error development.

Graph rigidity for near-coplanar structure from motion

Recent algorithms for monocular motion capture (MoCap) estimate weak-perspective camera matrices between images using a small subset of approximately-rigid points on the human body (i.e. the torso and hip). A problem with this approach, however, is that these points are often close to coplanar, causing canonical linear factorisation algorithms for rigid structure from motion (SFM) to become extremely sensitive to noise. In this paper, we propose an alternative solution to weak-perspective SFM based on a convex relaxation of graph rigidity. We demonstrate the success of our algorithm on both synthetic and real world data, allowing for much improved solutions to marker less MoCap problems on human bodies. Finally, we propose an approach to solve the two-fold ambiguity over bone direction using a k-nearest neighbour kernel density estimator.

Thomas Young’s investigations in gradient-index optics

Purpose: James Clerk Maxwell is usually recognized as being the first, in 1854, to consider using inhomogeneous media in optical systems. However, some fifty years earlier Thomas Young, stimulated by his interest in the optics of the eye and accommodation, had already modeled some applications of gradient-index optics. These applications included using an axial gradient to provide spherical aberration-free optics and a spherical gradient to describe the optics of the atmosphere and the eye lens. We evaluated Young’s contributions. Method: We attempted to derive Young’s equations for axial and spherical refractive index gradients. Raytracing was used to confirm accuracy of formula. Results: We did not confirm Young’s equation for the axial gradient to provide aberration-free optics, but derived a slightly different equation. We confirmed the correctness of his equations for deviation of rays in a spherical gradient index and for the focal length of a lens with a nucleus of fixed index surrounded by a cortex of reducing index towards the edge. Young claimed that the equation for focal length applied to a lens with part of the constant index nucleus of the sphere removed, such that the loss of focal length was a quarter of the thickness removed, but this is not strictly correct. Conclusion: Young’s theoretical work in gradient-index optics received no acknowledgement from either his contemporaries or later authors. While his model of the eye lens is not an accurate physiological description of the human lens, with the index reducing least quickly at the edge, it represented a bold attempt to approximate the characteristics of the lens. Thomas Young’s work deserves wider recognition.

Third-order theory of spectacle lenses applied to correction of peripheral refractive errors

Purpose: To demonstrate that relatively simple third-order theory can provide a framework which shows how peripheral refraction can be manipulated by altering the forms of spectacle lenses. Method: Third-order equations were used to yield lens forms that correct peripheral power errors, either for the lenses alone or in combination with typical peripheral refractions of myopic eyes. These results were compared with those of finite ray-tracing. Results: The approximate forms of spherical and conicoidal lenses provided by third-order theory were flatter over a moderate myopic range than the forms obtained by rigorous raytracing. Lenses designed to correct peripheral refractive errors produced large errors when used with foveal vision and a rotating eye. Correcting astigmatism tended to give large errors in mean oblique error and vice versa. When only spherical lens forms are used, correction of the relative hypermetropic peripheral refractions of myopic eyes which are observed experimentally, or the provision of relative myopic peripheral refractions in such eyes, seems impossible in the majority of cases. Conclusion: The third-order spectacle lens design approach can readily be used to show trends in peripheral refraction.

Binocular summation improves performance to defocus-induced blur

PURPOSE. To assess whether there are any advantages of binocular over monocular vision under blur conditions. METHODS. We measured the effect of defocus, induced by positive lenses, on the pattern reversal Visual Evoked Potential (VEP) and on visual acuity (VA). Monocular (dominant eye) and binocular VEPs were recorded from thirteen volunteers (average age: 28±5 years, average spherical equivalent: -0.25±0.73 D) for defocus up to 2.00 D using positive powered lenses. VEPs were elicited using reversing 10 arcmin checks at a rate of 4 reversals/second. The stimulus subtended a circular field of 7 degrees with 100% contrast and mean luminance 30 cd/m2. VA was measured under the same conditions using ETDRS charts. All measurements were performed at 1m viewing distance with best spectacle sphero-cylindrical correction and natural pupils. RESULTS. With binocular stimulation, amplitudes and implicit times of the P100 component of the VEPs were greater and shorter, respectively, in all cases than for monocular stimulation. Mean binocular enhancement ratio in the P100 amplitude was 2.1 in-focus, increasing linearly with defocus to be 3.1 at +2.00 D defocus. Mean peak latency was 2.9 ms shorter in-focus with binocular than for monocular stimulation, with the difference increasing with defocus to 8.8 ms at +2.00 D. As for the VEP amplitude, VA was always better with binocular than with monocular vision, with the difference being greater for higher retinal blur. CONCLUSIONS. Both subjective and electrophysiological results show that binocular vision ameliorates the effect of defocus. The increased binocular facilitation observed with retinal blur may be due to the activation of a larger population of neurons at close-to-threshold detection under binocular stimulation.