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.

Traces de terre, traces d'encre... La rappresentazione dello spazio nella letteratura caraibica. (Francofona e Anglofona)

This study concerns the representation of space in Caribbean literature, both francophone and Anglophone and, in particular, but not only, in the martinican literature, in the works of the authors born in the island. The analysis focus on the second half of the last century, a period in which the martinican production of novels and romances increased considerably, and where the representation and the rule of space had a relevant place. So, the thesis explores the literary modalities of this representation. The work is constituted of 5 chapters and the critical and methodological approaches are both of an analytical and comparative type. The first chapter “The caribbean space: geography, history and society” presents the geographic context, through an analysis of the historical and political major events occurred in the Caribbean archipelago, in particular of the French Antilles, from the first colonization until the départementalisation. The first paragraph “The colonized space: historical-political excursus” the explores the history of the European colonization that marked forever the theatre of the relationship between Europe, Africa and the New World. This social situation take a long and complex process of “Re-appropriation and renegotiation of the space”, (second paragraph) always the space of the Other, that interest both the Antillean society and the writers’ universe. So, a series of questions take place in the third paragraph “Landscape and identity”: what is the function of space in the process of identity construction? What are the literary forms and representations of space in the Caribbean context? Could the writing be a tool of cultural identity definition, both individual and collective? The second chapter “The literary representation of the Antillean space” is a methodological analysis of the notions of literary space and descriptive gender. The first paragraph “The literary space of and in the novel” is an excursus of the theory of such critics like Blanchot, Bachelard, Genette and Greimas, and in particular the recent innovation of the 20th century; the second one “Space of the Antilles, space of the writing” is an attempt to apply this theory to the Antillean literary space. Finally the last paragraph “Signs on the page: the symbolic places of the antillean novel landscape” presents an inventory of the most recurrent antillean places (mornes, ravines, traces, cachots, En-ville,…), symbols of the history and the past, described in literary works, but according to new modalities of representation. The third chapter, the core of the thesis, “Re-drawing the map of the French Antilles” focused the study of space representation on francophone literature, in particular on a selected works of four martinican writers, like Roland Brival, Édouard Glissant, Patrick Chamoiseau and Raphaël Confiant. Through this section, a spatial evolution comes out step by step, from the first to the second paragraph, whose titles are linked together “The novel space evolution: from the forest of the morne… to the jungle of the ville”. The virgin and uncontaminated space of the Antilles, prior to the colonisation, where the Indios lived in harmony with the nature, find a representation in both works of Brival (Le sang du roucou, Le dernier des Aloukous) and of Glissant (Le Quatrième siècle, Ormerod). The arrival of the European colonizer brings a violent and sudden metamorphosis of the originary space and landscape, together with the traditions and culture of the Caraïbes population. These radical changes are visible in the works of Chamoiseau (Chronique des sept misères, Texaco, L’esclave vieil homme et le molosse, Livret des villes du deuxième monde, Un dimanche au cachot) and Confiant (Le Nègre et l’Amiral, Eau de Café, Ravines du devant-jour, Nègre marron) that explore the urban space of the creole En-ville. The fourth chapter represents the “2nd step: the Anglophone novel space” in the exploration of literary representation of space, through an analytical study of the works of three Anglophone writers, the 19th century Lafcadio Hearn (A Midsummer Trip To the West Indies, Two Years in the French West Indies, Youma) and the contemporary authors Derek Walcott (Omeros, Map of the New World, What the Twilight says) and Edward Kamau Brathwaite (The Arrivants: A New World Trilogy). The Anglophone voice of the Caribbean archipelago brings a very interesting contribution to the critical idea of a spatial evolution in the literary representation of space, started with francophone production: “The spatial evolution goes on: from the Martiniques Sketches of Hearn… to the modern bards of Caribbean archipelago” is the new linked title of the two paragraphs. The fifth chapter “Extended look, space shared: the Caribbean archipelago” is a comparative analysis of the results achieved in the prior sections, through a dialogue between all the texts in the first paragraph “Francophone and Anglophone representation of space compared: differences and analogies”. The last paragraph instead is an attempt of re-negotiate the conventional notions of space and place, from a geographical and physical meaning, to the new concept of “commonplace”, not synonym of prejudice, but “common place” of sharing and dialogue. The question sets in the last paragraph “The “commonplaces” of the physical and mental map of the Caribbean archipelago: toward a non-place?” contains the critical idea of the entire thesis.