Kernel Methods for Tree Structured Data

Machine learning comprises a series of techniques for automatic extraction of meaningful information from large collections of noisy data. In many real world applications, data is naturally represented in structured form. Since traditional methods in machine learning deal with vectorial information, they require an a priori form of preprocessing. Among all the learning techniques for dealing with structured data, kernel methods are recognized to have a strong theoretical background and to be effective approaches. They do not require an explicit vectorial representation of the data in terms of features, but rely on a measure of similarity between any pair of objects of a domain, the kernel function. Designing fast and good kernel functions is a challenging problem. In the case of tree structured data two issues become relevant: kernel for trees should not be sparse and should be fast to compute. The sparsity problem arises when, given a dataset and a kernel function, most structures of the dataset are completely dissimilar to one another. In those cases the classifier has too few information for making correct predictions on unseen data. In fact, it tends to produce a discriminating function behaving as the nearest neighbour rule. Sparsity is likely to arise for some standard tree kernel functions, such as the subtree and subset tree kernel, when they are applied to datasets with node labels belonging to a large domain. A second drawback of using tree kernels is the time complexity required both in learning and classification phases. Such a complexity can sometimes prevents the kernel application in scenarios involving large amount of data. This thesis proposes three contributions for resolving the above issues of kernel for trees. A first contribution aims at creating kernel functions which adapt to the statistical properties of the dataset, thus reducing its sparsity with respect to traditional tree kernel functions. Specifically, we propose to encode the input trees by an algorithm able to project the data onto a lower dimensional space with the property that similar structures are mapped similarly. By building kernel functions on the lower dimensional representation, we are able to perform inexact matchings between different inputs in the original space. A second contribution is the proposal of a novel kernel function based on the convolution kernel framework. Convolution kernel measures the similarity of two objects in terms of the similarities of their subparts. Most convolution kernels are based on counting the number of shared substructures, partially discarding information about their position in the original structure. The kernel function we propose is, instead, especially focused on this aspect. A third contribution is devoted at reducing the computational burden related to the calculation of a kernel function between a tree and a forest of trees, which is a typical operation in the classification phase and, for some algorithms, also in the learning phase. We propose a general methodology applicable to convolution kernels. Moreover, we show an instantiation of our technique when kernels such as the subtree and subset tree kernels are employed. In those cases, Direct Acyclic Graphs can be used to compactly represent shared substructures in different trees, thus reducing the computational burden and storage requirements.

Innovative Homogeneous and Heterogeneous Systems for Electrochemically Generated Luminescence Investigations: Towards One-Dimensional ECL

My research PhD work is focused on the Electrochemically Generated Luminescence (ECL) investigation of several different homogeneous and heterogeneous systems. ECL is a redox induced emission, a process whereby species, generated at electrodes, undergo a high-energy electron transfer reaction to form excited states that emit light. Since its first application, the ECL technique has become a very powerful analytical tool and has widely been used in biosensor transduction. ECL presents an intrinsically low noise and high sensitivity; moreover, the electrochemical generation of the excited state prevents scattering of the light source: for all these characteristics, it is an elective technique for ultrasensitive immunoassay detection. The majority of ECL systems involve species in solution where the emission occurs in the diffusion layer near to the electrode surface. However, over the past few years, an intense research has been focused on the ECL generated from species constrained on the electrode surface. The aim of my work is to study the behavior of ECL-generating molecular systems upon the progressive increase of their spatial constraints, that is, passing from isolated species in solution, to fluorophores embedded within a polymeric film and, finally, to patterned surfaces bearing “one-dimensional” emitting spots. In order to describe these trends, I use different “dimensions” to indicate the different classes of compounds. My thesis was mostly developed in the electrochemistry group of Bologna with the supervision of Prof Francesco Paolucci and Dr Massimo Marcaccio. With their help and also thanks to their long experience in the molecular and supramolecular ECL fields and in the surface investigations using scanning probe microscopy techniques, I was able to obtain the results herein described. Moreover, during my research work, I have established a new collaboration with the group of Nanobiotechnology of Prof. Robert Forster (Dublin City University) where I spent a research period. Prof. Forster has a broad experience in the biomedical field, especially he focuses his research on film surfaces biosensor based on the ECL transduction. This thesis can be divided into three sections described as follows: (i) in the fist section, homogeneous molecular and supramolecular ECL-active systems, either organic or inorganic species (i.e., corannulene, dendrimers and iridium metal complex), are described. Driving force for this kind of studies includes the search for new luminophores that display on one hand higher ECL efficiencies and on the other simple mechanisms for modulating intensity and energy of their emission in view of their effective use in bioconjugation applications. (ii) in the second section, the investigation of some heterogeneous ECL systems is reported. Redox polymers comprising inorganic luminophores were described. In such a context, a new conducting platform, based on carbon nanotubes, was developed aimed to accomplish both the binding of a biological molecule and its electronic wiring to the electrode. This is an essential step for the ECL application in the field of biosensors. (iii) in the third section, different patterns were produced on the electrode surface using a Scanning Electrochemical Microscopy. I developed a new methods for locally functionalizing an inert surface and reacting this surface with a luminescent probe. In this way, I successfully obtained a locally ECL active platform for multi-array application.

Algorithms for on-line image registration from multiple views

Images of a scene, static or dynamic, are generally acquired at different epochs from different viewpoints. They potentially gather information about the whole scene and its relative motion with respect to the acquisition device. Data from different (in the spatial or temporal domain) visual sources can be fused together to provide a unique consistent representation of the whole scene, even recovering the third dimension, permitting a more complete understanding of the scene content. Moreover, the pose of the acquisition device can be achieved by estimating the relative motion parameters linking different views, thus providing localization information for automatic guidance purposes. Image registration is based on the use of pattern recognition techniques to match among corresponding parts of different views of the acquired scene. Depending on hypotheses or prior information about the sensor model, the motion model and/or the scene model, this information can be used to estimate global or local geometrical mapping functions between different images or different parts of them. These mapping functions contain relative motion parameters between the scene and the sensor(s) and can be used to integrate accordingly informations coming from the different sources to build a wider or even augmented representation of the scene. Accordingly, for their scene reconstruction and pose estimation capabilities, nowadays image registration techniques from multiple views are increasingly stirring up the interest of the scientific and industrial community. Depending on the applicative domain, accuracy, robustness, and computational payload of the algorithms represent important issues to be addressed and generally a trade-off among them has to be reached. Moreover, on-line performance is desirable in order to guarantee the direct interaction of the vision device with human actors or control systems. This thesis follows a general research approach to cope with these issues, almost independently from the scene content, under the constraint of rigid motions. This approach has been motivated by the portability to very different domains as a very desirable property to achieve. A general image registration approach suitable for on-line applications has been devised and assessed through two challenging case studies in different applicative domains. The first case study regards scene reconstruction through on-line mosaicing of optical microscopy cell images acquired with non automated equipment, while moving manually the microscope holder. By registering the images the field of view of the microscope can be widened, preserving the resolution while reconstructing the whole cell culture and permitting the microscopist to interactively explore the cell culture. In the second case study, the registration of terrestrial satellite images acquired by a camera integral with the satellite is utilized to estimate its three-dimensional orientation from visual data, for automatic guidance purposes. Critical aspects of these applications are emphasized and the choices adopted are motivated accordingly. Results are discussed in view of promising future developments.

Assessing poverty with survey data. Uni-dimensional, multidimensional and resilience poverty analysis in Kenya

Traditionally Poverty has been measured by a unique indicator, income, assuming this was the most relevant dimension of poverty. Sen’s approach has dramatically changed this idea shedding light over the existence of many more dimensions and over the multifaceted nature of poverty; poverty cannot be represented by a unique indicator that only can evaluate a specific aspect of poverty. This thesis tracks an ideal path along with the evolution of the poverty analysis. Starting from the unidimensional analysis based on income and consumptions, this research enter the world of multidimensional analysis. After reviewing the principal approaches, the Foster and Alkire method is critically analyzed and implemented over data from Kenya. A step further is moved in the third part of the thesis, introducing a new approach to multidimensional poverty assessment: the resilience analysis.

Static analysis of functionally graded cylindrical and conical shells or panels using the generalized unconstrained third order theory coupled with the stress recovery

A 2D Unconstrained Third Order Shear Deformation Theory (UTSDT) is presented for the evaluation of tangential and normal stresses in moderately thick functionally graded conical and cylindrical shells subjected to mechanical loadings. Several types of graded materials are investigated. The functionally graded material consists of ceramic and metallic constituents. A four parameter power law function is used. The UTSDT allows the presence of a finite transverse shear stress at the top and bottom surfaces of the graded shell. In addition, the initial curvature effect included in the formulation leads to the generalization of the present theory (GUTSDT). The Generalized Differential Quadrature (GDQ) method is used to discretize the derivatives in the governing equations, the external boundary conditions and the compatibility conditions. Transverse and normal stresses are also calculated by integrating the three dimensional equations of equilibrium in the thickness direction. In this way, the six components of the stress tensor at a point of the conical or cylindrical shell or panel can be given. The initial curvature effect and the role of the power law functions are shown for a wide range of functionally conical and cylindrical shells under various loading and boundary conditions. Finally, numerical examples of the available literature are worked out.