Learning with Kernels on Graphs: DAG-based kernels, data streams and RNA function prediction.

In many application domains data can be naturally represented as graphs. When the application of analytical solutions for a given problem is unfeasible, machine learning techniques could be a viable way to solve the problem. Classical machine learning techniques are defined for data represented in a vectorial form. Recently some of them have been extended to deal directly with structured data. Among those techniques, kernel methods have shown promising results both from the computational complexity and the predictive performance point of view. Kernel methods allow to avoid an explicit mapping in a vectorial form relying on kernel functions, which informally are functions calculating a similarity measure between two entities. However, the definition of good kernels for graphs is a challenging problem because of the difficulty to find a good tradeoff between computational complexity and expressiveness. Another problem we face is learning on data streams, where a potentially unbounded sequence of data is generated by some sources. There are three main contributions in this thesis. The first contribution is the definition of a new family of kernels for graphs based on Directed Acyclic Graphs (DAGs). We analyzed two kernels from this family, achieving state-of-the-art results from both the computational and the classification point of view on real-world datasets. The second contribution consists in making the application of learning algorithms for streams of graphs feasible. Moreover,we defined a principled way for the memory management. The third contribution is the application of machine learning techniques for structured data to non-coding RNA function prediction. In this setting, the secondary structure is thought to carry relevant information. However, existing methods considering the secondary structure have prohibitively high computational complexity. We propose to apply kernel methods on this domain, obtaining state-of-the-art results.

Operating System Contribution to Composable Timing Behaviour in High-Integrity Real-Time Systems

The development of High-Integrity Real-Time Systems has a high footprint in terms of human, material and schedule costs. Factoring functional, reusable logic in the application favors incremental development and contains costs. Yet, achieving incrementality in the timing behavior is a much harder problem. Complex features at all levels of the execution stack, aimed to boost average-case performance, exhibit timing behavior highly dependent on execution history, which wrecks time composability and incrementaility with it. Our goal here is to restitute time composability to the execution stack, working bottom up across it. We first characterize time composability without making assumptions on the system architecture or the software deployment to it. Later, we focus on the role played by the real-time operating system in our pursuit. Initially we consider single-core processors and, becoming less permissive on the admissible hardware features, we devise solutions that restore a convincing degree of time composability. To show what can be done for real, we developed TiCOS, an ARINC-compliant kernel, and re-designed ORK+, a kernel for Ada Ravenscar runtimes. In that work, we added support for limited-preemption to ORK+, an absolute premiere in the landscape of real-word kernels. Our implementation allows resource sharing to co-exist with limited-preemptive scheduling, which extends state of the art. We then turn our attention to multicore architectures, first considering partitioned systems, for which we achieve results close to those obtained for single-core processors. Subsequently, we shy away from the over-provision of those systems and consider less restrictive uses of homogeneous multiprocessors, where the scheduling algorithm is key to high schedulable utilization. To that end we single out RUN, a promising baseline, and extend it to SPRINT, which supports sporadic task sets, hence matches real-world industrial needs better. To corroborate our results we present findings from real-world case studies from avionic industry.

Interacting quantum-dissipative tunnelling systems

Die Untersuchung von dissipativen Quantensystemen erm¨oglicht es, Quantenph¨anomene auch auf makroskopischen L¨angenskalen zu beobachten. Das in dieser Dissertation gew¨ahlte mikroskopische Modell erlaubt es, den bisher nur ph¨anomenologisch zug¨anglichen Effekt der Quantendissipation mathematisch und physikalisch herzuleiten und zu untersuchen. Bei dem betrachteten mikroskopischen Modell handelt es sich um eine 1-dimensionale Kette von harmonischen Freiheitsgraden, die sowohl untereinander als auch an r anharmonische Freiheitsgrade gekoppelt sind. Die F¨alle einer, respektive zwei anharmonischer Bindungen werden in dieser Arbeit explizit betrachtet. Hierf¨ur wird eine analytische Trennung der harmonischen von den anharmonischen Freiheitsgraden auf zwei verschiedenen Wegen durchgef¨uhrt. Das anharmonische Potential wird als symmetrisches Doppelmuldenpotential gew¨ahlt, welches mit Hilfe der Wick Rotation die Berechnung der ¨Uberg¨ange zwischen beiden Minima erlaubt. Das Eliminieren der harmonischen Freiheitsgrade erfolgt mit Hilfe des wohlbekannten Feynman-Vernon Pfadintegral-Formalismus [21]. In dieser Arbeit wird zuerst die Positionsabh¨angigkeit einer anharmonischen Bindung im Tunnelverhalten untersucht. F¨ur den Fall einer fernab von den R¨andern lokalisierten anharmonischen Bindung wird ein Ohmsches dissipatives Tunneln gefunden, was bei der Temperatur T = 0 zu einem Phasen¨ubergang in Abh¨angigkeit einer kritischen Kopplungskonstanten Ccrit f¨uhrt. Dieser Phasen¨ubergang wurde bereits in rein ph¨anomenologisches Modellen mit Ohmscher Dissipation durch das Abbilden des Systems auf das Ising-Modell [26] erkl¨art. Wenn die anharmonische Bindung jedoch an einem der R¨ander der makroskopisch grossen Kette liegt, tritt nach einer vom Abstand der beiden anharmonischen Bindungen abh¨angigen Zeit tD ein ¨Ubergang von Ohmscher zu super- Ohmscher Dissipation auf, welche im Kern KM(τ ) klar sichtbar ist. F¨ur zwei anharmonische Bindungen spielt deren indirekteWechselwirkung eine entscheidende Rolle. Es wird gezeigt, dass der Abstand D beider Bindungen und die Wahl des Anfangs- und Endzustandes die Dissipation bestimmt. Unter der Annahme, dass beide anharmonischen Bindung gleichzeitig tunneln, wird eine Tunnelwahrscheinlichkeit p(t) analog zu [14], jedoch f¨ur zwei anharmonische Bindungen, berechnet. Als Resultat erhalten wir entweder Ohmsche Dissipation f¨ur den Fall, dass beide anharmonischen Bindungen ihre Gesamtl¨ange ¨andern, oder super-Ohmsche Dissipation, wenn beide anharmonischen Bindungen durch das Tunneln ihre Gesamtl¨ange nicht ¨andern.

Modellazione matematica delle non linearità di sistemi acustici mediante serie di Volterra modificate

In questa tesi si è studiato un metodo per modellare e virtualizzare tramite algoritmi in Matlab le distorsioni armoniche di un dispositivo audio non lineare, ovvero uno “strumento” che, sollecitato da un segnale audio, lo modifichi, introducendovi delle componenti non presenti in precedenza. Il dispositivo che si è scelto per questo studio il pedale BOSS SD-1 Super OverDrive per chitarra elettrica e lo “strumento matematico” che ne fornisce il modello è lo sviluppo in serie di Volterra. Lo sviluppo in serie di Volterra viene diffusamente usato nello studio di sistemi fisici non lineari, nel caso in cui si abbia interesse a modellare un sistema che si presenti come una “black box”. Il metodo della Nonlinear Convolution progettato dall'Ing. Angelo Farina ha applicato con successo tale sviluppo anche all'ambito dell'acustica musicale: servendosi di una tecnica di misurazione facilmente realizzabile e del modello fornito dalla serie di Volterra Diagonale, il metodo permette di caratterizzare un dispositivo audio non lineare mediante le risposte all'impulso non lineari che il dispositivo fornisce a fronte di un opportuno segnale di test (denominato Exponential Sine Sweep). Le risposte all'impulso del dispositivo vengono utilizzate per ricavare i kernel di Volterra della serie. L'utilizzo di tale metodo ha permesso all'Università di Bologna di ottenere un brevetto per un software che virtualizzasse in post-processing le non linearità di un sistema audio. In questa tesi si è ripreso il lavoro che ha portato al conseguimento del brevetto, apportandovi due innovazioni: si è modificata la scelta del segnale utilizzato per testare il dispositivo (si è fatto uso del Synchronized Sine Sweep, in luogo dell'Exponential Sine Sweep); si è messo in atto un primo tentativo di orientare la virtualizzazione verso l'elaborazione in real-time, implementando un procedimento (in post-processing) di creazione dei kernel in dipendenza dal volume dato in input al dispositivo non lineare.

Ergodicity and regularity of invariant measure for branching Markov processes with immigration

In this thesis we consider systems of finitely many particles moving on paths given by a strong Markov process and undergoing branching and reproduction at random times. The branching rate of a particle, its number of offspring and their spatial distribution are allowed to depend on the particle's position and possibly on the configuration of coexisting particles. In addition there is immigration of new particles, with the rate of immigration and the distribution of immigrants possibly depending on the configuration of pre-existing particles as well. In the first two chapters of this work, we concentrate on the case that the joint motion of particles is governed by a diffusion with interacting components. The resulting process of particle configurations was studied by E. Löcherbach (2002, 2004) and is known as a branching diffusion with immigration (BDI). Chapter 1 contains a detailed introduction of the basic model assumptions, in particular an assumption of ergodicity which guarantees that the BDI process is positive Harris recurrent with finite invariant measure on the configuration space. This object and a closely related quantity, namely the invariant occupation measure on the single-particle space, are investigated in Chapter 2 where we study the problem of the existence of Lebesgue-densities with nice regularity properties. For example, it turns out that the existence of a continuous density for the invariant measure depends on the mechanism by which newborn particles are distributed in space, namely whether branching particles reproduce at their death position or their offspring are distributed according to an absolutely continuous transition kernel. In Chapter 3, we assume that the quantities defining the model depend only on the spatial position but not on the configuration of coexisting particles. In this framework (which was considered by Höpfner and Löcherbach (2005) in the special case that branching particles reproduce at their death position), the particle motions are independent, and we can allow for more general Markov processes instead of diffusions. The resulting configuration process is a branching Markov process in the sense introduced by Ikeda, Nagasawa and Watanabe (1968), complemented by an immigration mechanism. Generalizing results obtained by Höpfner and Löcherbach (2005), we give sufficient conditions for ergodicity in the sense of positive recurrence of the configuration process and finiteness of the invariant occupation measure in the case of general particle motions and offspring distributions.

Orthogonal gamma-based expansions for volatility option prices under jump-diffusion dynamics

In my work I derive closed-form pricing formulas for volatility based options by suitably approximating the volatility process risk-neutral density function. I exploit and adapt the idea, which stands behind popular techniques already employed in the context of equity options such as Edgeworth and Gram-Charlier expansions, of approximating the underlying process as a sum of some particular polynomials weighted by a kernel, which is typically a Gaussian distribution. I propose instead a Gamma kernel to adapt the methodology to the context of volatility options. VIX vanilla options closed-form pricing formulas are derived and their accuracy is tested for the Heston model (1993) as well as for the jump-diffusion SVJJ model proposed by Duffie et al. (2000).

Representation theorems for indefinite quadratic forms and applications

Diese Arbeit widmet sich den Darstellungssätzen für symmetrische indefinite (das heißt nicht-halbbeschränkte) Sesquilinearformen und deren Anwendungen. Insbesondere betrachten wir den Fall, dass der zur Form assoziierte Operator keine Spektrallücke um Null besitzt. Desweiteren untersuchen wir die Beziehung zwischen reduzierenden Graphräumen, Lösungen von Operator-Riccati-Gleichungen und der Block-Diagonalisierung für diagonaldominante Block-Operator-Matrizen. Mit Hilfe der Darstellungssätze wird eine entsprechende Beziehung zwischen Operatoren, die zu indefiniten Formen assoziiert sind, und Form-Riccati-Gleichungen erreicht. In diesem Rahmen wird eine explizite Block-Diagonalisierung und eine Spektralzerlegung für den Stokes Operator sowie eine Darstellung für dessen Kern erreicht. Wir wenden die Darstellungssätze auf durch (grad u, h() grad v) gegebene Formen an, wobei Vorzeichen-indefinite Koeffzienten-Matrizen h() zugelassen sind. Als ein Resultat werden selbstadjungierte indefinite Differentialoperatoren div h() grad mit homogenen Dirichlet oder Neumann Randbedingungen konstruiert. Beispiele solcher Art sind Operatoren die in der Modellierung von optischen Metamaterialien auftauchen und links-indefinite Sturm-Liouville Operatoren.

Esperimenti di Modularizzazione dello Stack TCP-IP di Linux

In questo lavoro si introduce il progetto di estrarre lo stack tcp-ip dal kernel di linux e farlo funzionare come una normale libreria in userspace. Si parlerà dei vantaggi di avere lo stack tcp-ip in userspace, di altri progetti simili, del motivo per cui si è scelto lo stack di linux, dei principali problemi incontrati nel corso del lavoro, del percorso seguito, e di come il risultato possa essere migliorato per renderlo uno strumento effettivamente utile.

Non-parametric estimation of the diffusion coefficient of a branching diffusion with immigration

Wir betrachten Systeme von endlich vielen Partikeln, wobei die Partikel sich unabhängig voneinander gemäß eindimensionaler Diffusionen [dX_t = b(X_t),dt + sigma(X_t),dW_t] bewegen. Die Partikel sterben mit positionsabhängigen Raten und hinterlassen eine zufällige Anzahl an Nachkommen, die sich gemäß eines Übergangskerns im Raum verteilen. Zudem immigrieren neue Partikel mit einer konstanten Rate. Ein Prozess mit diesen Eigenschaften wird Verzweigungsprozess mit Immigration genannt. Beobachten wir einen solchen Prozess zu diskreten Zeitpunkten, so ist zunächst nicht offensichtlich, welche diskret beobachteten Punkte zu welchem Pfad gehören. Daher entwickeln wir einen Algorithmus, um den zugrundeliegenden Pfad zu rekonstruieren. Mit Hilfe dieses Algorithmus konstruieren wir einen nichtparametrischen Schätzer für den quadrierten Diffusionskoeffizienten $sigma^2(cdot),$ wobei die Konstruktion im Wesentlichen auf dem Auffüllen eines klassischen Regressionsschemas beruht. Wir beweisen Konsistenz und einen zentralen Grenzwertsatz.

Windkanalstudien zum Graupelwachstum und Bestimmung von Retentionskoeffizienten verschiedener Spurengase während der Bereifung

Am vertikalen Windkanal der Johannes Gutenberg-Universität Mainz wurden physikalische und chemische Bereifungsexperimente durchgeführt. Dabei lagen die Umgebungstemperaturen bei allen Experimenten zwischen etwa -15 und -5°C und der Flüssigwassergehalt erstreckte sich von 0,9 bis etwa 1,6g/m³, typische Bedingungen für Mischphasenwolken in denen Bereifung stattfindet. Oberflächentemperaturmessungen an wachsenden hängenden Graupelpartikeln zeigten, dass während der Experimente trockene Wachstumsbedingungen herrschten.rnZunächst wurde das Graupelwachstum an in einer laminaren Strömung frei schwebenden Eispartikeln mit Anfangsradien zwischen 290 und 380µm, die mit flüssigen unterkühlten Wolkentröpfchen bereift wurden, studiert. Ziel war es, den Kollektionskern aus der Massenzunahme des bereiften Eispartikels und dem mittleren Flüssigwassergehalt während des Wachstumsexperimentes zu bestimmen. Die ermittelten Werte für die Kollektionskerne der bereiften Eispartikel erstreckten sich von 0,9 bis 2,3cm³/s in Abhängigkeit ihres Kollektorimpulses (Masse * Fallgeschwindigkeit des bereifenden Graupels), der zwischen 0,04 und 0,10gcm/s lag. Bei den Experimenten zeigte sich, dass die hier gemessenen Kollektionskerne höher waren im Vergleich mit Kollektionskernen flüssiger Tropfen untereinander. Aus den aktuellen Ergebnissen dieser Arbeit und der vorhandenen Literaturwerte wurde ein empirischer Faktor entwickelt, der von dem Wolkentröpfchenradius abhängig ist und diesen Unterschied beschreibt. Für die untersuchten Größenbereiche von Kollektorpartikel und flüssigen Tröpfchen können die korrigierten Kollektionskernwerte in Wolkenmodelle für die entsprechenden Größen eingebunden werden.rnBei den chemischen Experimenten zu dieser Arbeit wurde die Spurenstoffaufnahme verschiedener atmosphärischer Spurengase (HNO3, HCl, H2O2, NH3 und SO2) während der Bereifung untersucht. Diese Experimente mussten aus technischen Gründen mit hängenden Eispartikeln, dendritischen Eiskristallen und Schneeflocken, bereift mit flüssigen Wolkenlösungströpfchen, durchgeführt werden.rnDie Konzentrationen der Lösung, aus der die Wolkentröpfchen mit Hilfe von Zweistoffdüsen erzeugt wurden, lagen zwischen 1 und 120mg/l. Für die Experimente mit Ammoniak und Schwefeldioxid wurden Konzentrationen zwischen 1 und 22mg/l verwendet. Das Schmelzwasser der bereiften hängenden Graupel und Schneeflocken wurden ionenchromatographisch analysiert und zusammen mit der bekannten Konzentration der bereifenden Wolkentröpfchen konnte der Retentionskoeffizient für jeden Spurenstoff bestimmt werden. Er gibt die Menge an Spurenstoff an, die bei der Phasenumwandlung von flüssig zu fest in die Eisphase übergeht. Salpetersäure und Salzsäure waren nahezu vollständig retiniert (Mittelwerte der gesamten Experimente entsprechend 99±8% und 100±9%). Für Wasserstoffperoxid wurde ein mittlerer Retentionskoeffizient von 65±17% bestimmt. rnDer mittlere Retentionskoeffizient von Ammoniak ergab sich unabhängig vom Flüssigwassergehalt zu 92±21%, während sich für Schwefeldioxid 53±10% für niedrige und 29±7% für hohe Flüssigphasenkonzentrationen ergaben. Bei einigen der untersuchten Spurenstoffe wurde eine Temperaturabhängigkeit beobachtet und wenn möglich durch Parametrisierungen beschrieben.rn

Analisi e processi di immagini astronomiche

Questa tesi riguarda l'analisi di immagini astronomiche. In particolare esamineremo tecniche che permettono l'elaborazione di immagini. Si parlerà di operazioni di base che comprendono le usuali operazioni matematiche e le trasformazioni geometriche fornendo alcuni esempi di applicazioni. Parleremo inoltre approfonditamente dell'operazione di convoluzione tra immagini e delle sue proprietà. Successivamente tratteremo in modo approfondito la teoria di Fourier, a partire dai suoi lavori sulle serie omonime fino allo sviluppo dell'algoritmo FFT. Vedremo inoltre svariate applicazioni della trasformata di Fourier all'analisi di immagini. Per concludere parleremo di deconvoluzione, analizzando in particolare due algoritmi deconvolutivi, l'algoritmo di Van Cittert e l'algoritmo di Richardson-Lucy.

Un approccio cross-layer all'affidabilita guidata dalle applicazioni

Il lavoro descrive la progettazione, implementazione e test sperimentale di un meccanismo, integrato nel kernel linux 4.0, dedicato al riconoscimento delle perdite dei frame Wi-Fi.

The Karhunen-Loève theorem

La trasformata di Karhunen-Loève monodimensionale è la decomposizione di un processo stocastico del secondo ordine a parametrizzazione continua in coefficienti aleatori scorrelati. Nella presente dissertazione, la trasformata è ottenuta per via analitica, proiettando il processo, considerato in un intervallo di tempo limitato [a,b], su una base deterministica ottenuta dalle autofunzioni dell'operatore di Hilbert-Schmidt di covarianza corrispondenti ad autovalori positivi. Fondamentalmente l'idea del metodo è, dal primo, trovare gli autovalori positivi dell'operatore integrale di Hilbert-Schmidt, che ha in Kernel la funzione di covarianza del processo. Ad ogni tempo dell'intervallo, il processo è proiettato sulla base ortonormale dello span delle autofunzioni dell'operatore di Hilbert-Schmidt che corrispondono ad autovalori positivi. Tale procedura genera coefficienti aleatori che si rivelano variabili aleatorie centrate e scorrelate. L'espansione in serie che risulta dalla trasformata è una combinazione lineare numerabile di coefficienti aleatori di proiezione ed autofunzioni convergente in media quadratica al processo, uniformemente sull'intervallo temporale. Se inoltre il processo è Gaussiano, la convergenza è quasi sicuramente sullo spazio di probabilità (O,F,P). Esistono molte altre espansioni in serie di questo tipo, tuttavia la trasformata di Karhunen-Loève ha la peculiarità di essere ottimale rispetto all'errore totale in media quadratica che consegue al troncamento della serie. Questa caratteristica ha conferito a tale metodo ed alle sue generalizzazioni un notevole successo tra le discipline applicate.

Simulazione di fluidi in Computer Graphics

Questa tesi si focalizza sullo studio dei modelli fisico-matematici attualmente in uso per la simulazione di fluidi al calcolatore con l’obiettivo di fornire nozioni di base e avanzate sull’utilizzo di tali metodi. La trattazione ha lo scopo di facilitare la comprensione dei principi su cui si fonda la simulazione di fluidi e rappresenta una base per la creazione di un proprio simulatore. E’ possibile studiare le caratteristiche di un fluido in movimento mediante due approcci diversi, l’approccio lagrangiano e l’approccio euleriano. Mentre l’approccio lagrangiano ha lo scopo di conoscere il valore, nel tempo, di una qualsiasi proprietà di ciascuna particella che compone il fluido, l’approccio euleriano, fissato uno o più punti del volume di spazio occupato da quest’ultimo, vuole studiare quello che accade, nel tempo, in quei punti. In particolare, questa tesi approfondisce lo studio delle equazioni di Navier-Stokes, approcciandosi al problema in maniera euleriana. La soluzione numerica del sistema di equazioni differenziali alle derivate parziali derivante dalle equazioni sopracitate, approssima la velocità del fluido, a partire dalla quale è possibile risalire a tutte le grandezze che lo caratterizzano. Attenzione viene riservata anche ad un modello facente parte dell’approccio semi-lagrangiano, il Lattice Boltzmann, considerato una via di mezzo tra i metodi puramente euleriani e quelli lagrangiani, che si basa sulla soluzione dell’equazione di Boltzmann mediante modelli di collisione di particelle. Infine, analogamente al metodo di Lattice Boltzmann, viene trattato il metodo Smoothed Particles Hydrodynamics, tipicamente lagrangiano, secondo il quale solo le proprietà delle particelle comprese dentro il raggio di una funzione kernel, centrata nella particella di interesse, influenzano il valore della particella stessa. Un resoconto pratico della teoria trattata viene dato mediante delle simulazioni realizzate tramite il software Blender 2.76b.

Hoisting C Structures Into Clay In Device Drivers

This project addresses the unreliability of operating system code, in particular in device drivers. Device driver software is the interface between the operating system and the device's hardware. Device drivers are written in low level code, making them difficult to understand. Almost all device drivers are written in the programming language C which allows for direct manipulation of memory. Due to the complexity of manual movement of data, most mistakes in operating systems occur in device driver code. The programming language Clay can be used to check device driver code at compile-time. Clay does most of its error checking statically to minimize the overhead of run-time checks in order to stay competitive with C's performance time. The Clay compiler can detect a lot more types of errors than the C compiler like buffer overflows, kernel stack overflows, NULL pointer uses, freed memory uses, and aliasing errors. Clay code that successfully compiles is guaranteed to run without failing on errors that Clay can detect. Even though C is unsafe, currently most device drivers are written in it. Not only are device drivers the part of the operating system most likely to fail, they also are the largest part of the operating system. As rewriting every existing device driver in Clay by hand would be impractical, this thesis is part of a project to automate translation of existing drivers from C to Clay. Although C and Clay both allow low level manipulation of data and fill the same niche for developing low level code, they have different syntax, type systems, and paradigms. This paper explores how C can be translated into Clay. It identifies what part of C device drivers cannot be translated into Clay and what information drivers in Clay will require that C cannot provide. It also explains how these translations will occur by explaining how each C structure is represented in the compiler and how these structures are changed to represent a Clay structure.