Support Vector Machines: Training and Applications

The Support Vector Machine (SVM) is a new and very promising classification technique developed by Vapnik and his group at AT&T Bell Labs. This new learning algorithm can be seen as an alternative training technique for Polynomial, Radial Basis Function and Multi-Layer Perceptron classifiers. An interesting property of this approach is that it is an approximate implementation of the Structural Risk Minimization (SRM) induction principle. The derivation of Support Vector Machines, its relationship with SRM, and its geometrical insight, are discussed in this paper. Training a SVM is equivalent to solve a quadratic programming problem with linear and box constraints in a number of variables equal to the number of data points. When the number of data points exceeds few thousands the problem is very challenging, because the quadratic form is completely dense, so the memory needed to store the problem grows with the square of the number of data points. Therefore, training problems arising in some real applications with large data sets are impossible to load into memory, and cannot be solved using standard non-linear constrained optimization algorithms. We present a decomposition algorithm that can be used to train SVM's over large data sets. The main idea behind the decomposition is the iterative solution of sub-problems and the evaluation of, and also establish the stopping criteria for the algorithm. We present previous approaches, as well as results and important details of our implementation of the algorithm using a second-order variant of the Reduced Gradient Method as the solver of the sub-problems. As an application of SVM's, we present preliminary results we obtained applying SVM to the problem of detecting frontal human faces in real images.

Continuous GRASP with a local active-set method for bound-constrained global optimization

Global optimization seeks a minimum or maximum of a multimodal function over a discrete or continuous domain. In this paper, we propose a hybrid heuristic-based on the CGRASP and GENCAN methods-for finding approximate solutions for continuous global optimization problems subject to box constraints. Experimental results illustrate the relative effectiveness of CGRASP-GENCAN on a set of benchmark multimodal test functions.

Structured minimal-memory inexact quasi-Newton method and secant preconditioners for augmented Lagrangian optimization

Augmented Lagrangian methods for large-scale optimization usually require efficient algorithms for minimization with box constraints. On the other hand, active-set box-constraint methods employ unconstrained optimization algorithms for minimization inside the faces of the box. Several approaches may be employed for computing internal search directions in the large-scale case. In this paper a minimal-memory quasi-Newton approach with secant preconditioners is proposed, taking into account the structure of Augmented Lagrangians that come from the popular Powell-Hestenes-Rockafellar scheme. A combined algorithm, that uses the quasi-Newton formula or a truncated-Newton procedure, depending on the presence of active constraints in the penalty-Lagrangian function, is also suggested. Numerical experiments using the Cute collection are presented.

On the resolution of the generalized nonlinear complementarity problem

Minimization of a differentiable function subject to box constraints is proposed as a strategy to solve the generalized nonlinear complementarity problem (GNCP) defined on a polyhedral cone. It is not necessary to calculate projections that complicate and sometimes even disable the implementation of algorithms for solving these kinds of problems. Theoretical results that relate stationary points of the function that is minimized to the solutions of the GNCP are presented. Perturbations of the GNCP are also considered, and results are obtained related to the resolution of GNCPs with very general assumptions on the data. These theoretical results show that local methods for box-constrained optimization applied to the associated problem are efficient tools for solving the GNCP. Numerical experiments are presented that encourage the use of this approach.

Estudo dos problemas de corte e empacotamento

Pós-graduação em Engenharia Elétrica - FEIS

Grey-box radial basis function modelling: the art of incorporating prior knowledge

A basic principle in data modelling is to incorporate available a priori information regarding the underlying data generating mechanism into the modelling process. We adopt this principle and consider grey-box radial basis function (RBF) modelling capable of incorporating prior knowledge. Specifically, we show how to explicitly incorporate the two types of prior knowledge: the underlying data generating mechanism exhibits known symmetric property and the underlying process obeys a set of given boundary value constraints. The class of orthogonal least squares regression algorithms can readily be applied to construct parsimonious grey-box RBF models with enhanced generalisation capability.

Grey-box radial basis function modelling

A fundamental principle in data modelling is to incorporate available a priori information regarding the underlying data generating mechanism into the modelling process. We adopt this principle and consider grey-box radial basis function (RBF) modelling capable of incorporating prior knowledge. Specifically, we show how to explicitly incorporate the two types of prior knowledge: (i) the underlying data generating mechanism exhibits known symmetric property, and (ii) the underlying process obeys a set of given boundary value constraints. The class of efficient orthogonal least squares regression algorithms can readily be applied without any modification to construct parsimonious grey-box RBF models with enhanced generalisation capability.

Isotopic constraints on marine and terrestrial N2O emissions during the last deglaciation

Nitrous oxide (N2O) is an important greenhouse gas and ozone-depleting substance that has anthropogenic as well as natural marine and terrestrial sources. The tropospheric N2O concentrations have varied substantially in the past in concert with changing climate on glacial–interglacial and millennial timescales. It is not well understood, however, how N2O emissions from marine and terrestrial sources change in response to varying environmental conditions. The distinct isotopic compositions of marine and terrestrial N2O sources can help disentangle the relative changes in marine and terrestrial N2O emissions during past climate variations. Here we present N2O concentration and isotopic data for the last deglaciation, from 16,000 to 10,000 years before present, retrieved from air bubbles trapped in polar ice at Taylor Glacier, Antarctica. With the help of our data and a box model of the N2O cycle, we find a 30 per cent increase in total N2O emissions from the late glacial to the interglacial, with terrestrial and marine emissions contributing equally to the overall increase and generally evolving in parallel over the last deglaciation, even though there is no a priori connection between the drivers of the two sources. However, we find that terrestrial emissions dominated on centennial timescales, consistent with a state-of-the-art dynamic global vegetation and land surface process model that suggests that during the last deglaciation emission changes were strongly influenced by temperature and precipitation patterns over land surfaces. The results improve our understanding of the drivers of natural N2O emissions and are consistent with the idea that natural N2O emissions will probably increase in response to anthropogenic warming.

Comet 67P/Churyumov-Gerasimenko: Constraints on its origin from OSIRIS observations

Context. One of the main aims of the ESA Rosetta mission is to study the origin of the solar system by exploring comet 67P/Churyumov-Gerasimenko at close range. Aims. In this paper we discuss the origin and evolution of comet 67P/Churyumov-Gerasimenko in relation to that of comets in general and in the framework of current solar system formation models. Methods. We use data from the OSIRIS scientific cameras as basic constraints. In particular, we discuss the overall bi-lobate shape and the presence of key geological features, such as layers and fractures. We also treat the problem of collisional evolution of comet nuclei by a particle-in-a-box calculation for an estimate of the probability of survival for 67P/Churyumov-Gerasimenko during the early epochs of the solar system. Results. We argue that the two lobes of the 67P/Churyumov-Gerasimenko nucleus are derived from two distinct objects that have formed a contact binary via a gentle merger. The lobes are separate bodies, though sufficiently similar to have formed in the same environment. An estimate of the collisional rate in the primordial, trans-planetary disk shows that most comets of similar size to 67P/Churyumov-Gerasimenko are likely collisional fragments, although survival of primordial planetesimals cannot be excluded. Conclusions. A collisional origin of the contact binary is suggested, and the low bulk density of the aggregate and abundance of volatile species show that a very gentle merger must have occurred. We thus consider two main scenarios: the primordial accretion of planetesimals, and the re-accretion of fragments after an energetic impact onto a larger parent body. We point to the primordial signatures exhibited by 67P/Churyumov-Gerasimenko and other comet nuclei as critical tests of the collisional evolution.

Carbonate mineralogical and isotopic analyses of TV-guided grab samples and TV-guided box corer samples from the Shumagin area

Methane seepage leads to Mg-calcite and aragonite precipitation at a depth of 4,850 m on the Aleutian accretionary margin. Stromatolitic and oncoid growth structures imply encrustation of microorganisms (microbial mats) in the host sediment with a unique growth direction downward into the sediment, forming crust-shaped lithologies. Biomarker investigations of the residue after carbonate dissolution show strong enrichments in crocetane and archaeol, which contain extremely low d13C values. This indicates the presence of methane-consuming archaea, and d13C values of -42 to -51 per mill PDB indicate that methane is the carbon source for the carbonate crusts. Thus, it appears that stromatolitic encrustations of methanotrophic anaerobic archaea probably occurs in a consortium with sulphate-reducing bacteria and that carbonate precipitation proceeds downward into the sediment, where ascending cold fluids provide a methane source. Strontium and oxygen isotope analyses as well as 14C ages of the carbonates suggest that the fluids come from deep within the sediment and that carbonate precipitation began about 3,000 years ago.

Box Corer (engineering detail drawing of the large version)

The Box corer is a marine geological and biological sampling tool for soft sediments in lakes or oceans. It is deployed from a research vessel with a deep sea wire and suitable for any water depth. It is designed for a minimum of disturbance of the sediment surface by bow wave effects which is important for quantitative investigations of the benthos micro- to macrofauna, geochemical processes, sampling of bottom water or sedimentology. The large box corer version with an area of 2,500 cm? is frequently used on research vessels since the 1980th years. This data set is a publication of the engeneering drawings.