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.

Study of Italian isolates of Alternaria spp.: molecular and morphological characterization and pathogenesis on apple tree

It was decided to carry out a morphological and molecular characterization of the Italian Alternaria isolatescollected from apple , and evaluate their pathogenicity and subsequently combining the data collected. The strain collection (174 isolates) was constructed by collecting material (received from extension service personnel) between June and August of 2007, 2008, and 2009. A Preliminary bioassays were performed on detached plant materials (fruit and leaf wounded and unwounded), belonging to the Golden cultivar, with two different kind of inoculation (conidial suspension and conidial filtrate). Symptoms were monitored daily and a value of pathogenicity score (P.S.) was assigned on the basis of the diameter of the necrotic area that developed. On the basis of the bioassays, the number of isolates to undergo further molecular analysis was restricted to a representative set of single spore strains (44 strains). Morphological characteristics of the colony and sporulation pattern were determined according to previous systematic work on small-spored Alternaria spp. (Pryor and Michaelides, 2002 and Hong et al., 2006). Reference strains (Alternaria alternata, Alternaria tenuissima, Alternaria arborescens and four Japanese strains of Alternaria alternata mali pathotype), used in the study were kindly provided by Prof. Barry Pryor, who allows a open access to his own fungal collection. Molecular characterization was performed combining and comparing different data sets obtained from distinct molecular approach: 1) investigation of specific loci and 2) fingerprinting based on diverse randomly selected polymorphic sites of the genome. As concern the single locus analysis, it was chosen to sequence the EndoPG partial gene and three anonymous region (OPA1-3, OPA2- and OPa10-2). These markers has revealed a powerful tool in the latter systematic works on small-spored Alternaria spp. In fact, as reported in literature small-spored Alternaria taxonomy is complicated due to the inability to resolve evolutionary relationships among the taxa because of the lack of variability in the markers commonly used in fungi systematic. The three data set together provided the necessary variation to establish the phylogenetic relationships among the Italian isolates of Alternaria spp. On Italian strains these markers showed a variable number of informative sites (ranging from 7 for EndoPg to 85 for OPA1-3) and the parsimony analysis produced different tree topologies all concordant to define A. arborescens as a mophyletic clade. Fingerprinting analysis (nine ISSR primers and eight AFLP primers combination) led to the same result: a monophyleic A. arborescens clade and one clade containing both A. tenuissima and the A. alternata strains. This first attempt to characterize Italian Alternaria species recovered from apple produced concordant results with what was already described in a similar phylogenetic study on pistachio (Pryor and Michaelides, 2002), on walnut and hazelnut (Hong et al., 2006), apple (Kang et al., 2002) and citurus (Peever et al., 2004). Together with these studies, this research demonstrates that the three morphological groups are widely distributed and occupy similar ecological niches. Furthermore, this research suggest that these Alternaria species exhibit a similar infection pattern despite the taxonomic and pathogenic differences. The molecular characterization of the pathogens is a fundamental step to understanding the disease that is spreading in the apple orchards of the north Italy. At the beginning the causal agent was considered as Alteraria alternata (Marshall and Bertagnoll, 2006). Their preliminary studies purposed a pathogenic system related to the synthesis of toxins. Experimental data of our bioassays suggest an analogous hypothesis, considering that symptoms could be induced after inoculating plant material with solely the filtrate from pathogenic strains. Moreover, positive PCR reactions using AM-toxin gene specific primers, designed for identification of apple infecting Alternaria pathovar, led to a hypothesis that a host specific toxin (toxins) were involved. It remains an intriguing challenge to discover or not if the agent of the “Italian disease” is the same of the one previously typified as Alternaria mali, casual agent of the apple blotch disease.

Determinants of cesarean delivery, a population-based study in the Emilia Romagna Region

Cesarean Delivery (CD) rates are rising in many parts of the world. In order to define strategies to reduce them, it is important to explore the role of clinical and organizational factors. This thesis has the objective to describe the contemporary CD practice and study clinical and organizational variables as determinants of CD in all women who gave birth between 2005 and June 2010 in the Emilia Romagna region (Italy). All hospital discharge abstracts of women who delivered between 2005 and mid 2010 in the region were selected and linked with birth certificates. In addition to descriptive statistics, in order to study the role of clinical and organizational variables (teaching or non-teaching hospital, birth volumes, time and day of delivery) multilevel Poisson regression models and a classification tree were used. A substantial inter-hospital variability in CD rate was found, and this was only partially explained by the considered variables. The most important risk factors of CD were: previous CD (RR 4,95; 95%CI: 4,85-5,05), cord prolapse (RR 3,51; 95% CI:2,96-4,16), and malposition/malpresentation (RR 2,72; 95%CI: 2,66-2,77). Delivery between 7 pm and 7 am and during non working days protect against CD in all subgroups including those with a small number of elective CDs while delivery at a teaching hospital and birth volumes were not statistically significant risk factors. The classification tree shows that previous CD and malposition/malpresentation are the most important variables discriminating between high and low risk of CD. These results indicate that other not considered factors might explain CD variability and do not provide clear evidence that small hospitals have a poor performance in terms of CD rate. Some strategies to reduce CD could be found by focusing on the differences in delivery practice between day and night and between working and no-working day deliveries.