Spectral Analysis of Symmetric and Anti-Symmetric Pairwise Kernels

This work investigates theoretical properties of symmetric and anti-symmetric kernels. First chapters give an overview of the theory of kernels used in supervised machine learning. Central focus is on the regularized least squares algorithm, which is motivated as a problem of function reconstruction through an abstract inverse problem. Brief review of reproducing kernel Hilbert spaces shows how kernels define an implicit hypothesis space with multiple equivalent characterizations and how this space may be modified by incorporating prior knowledge. Mathematical results of the abstract inverse problem, in particular spectral properties, pseudoinverse and regularization are recollected and then specialized to kernels. Symmetric and anti-symmetric kernels are applied in relation learning problems which incorporate prior knowledge that the relation is symmetric or anti-symmetric, respectively. Theoretical properties of these kernels are proved in a draft this thesis is based on and comprehensively referenced here. These proofs show that these kernels can be guaranteed to learn only symmetric or anti-symmetric relations, and they can learn any relations relative to the original kernel modified to learn only symmetric or anti-symmetric parts. Further results prove spectral properties of these kernels, central result being a simple inequality for the the trace of the estimator, also called the effective dimension. This quantity is used in learning bounds to guarantee smaller variance.

New kernel functions and learning methods for text and data mining

Recent advances in machine learning methods enable increasingly the automatic construction of various types of computer assisted methods that have been difficult or laborious to program by human experts. The tasks for which this kind of tools are needed arise in many areas, here especially in the fields of bioinformatics and natural language processing. The machine learning methods may not work satisfactorily if they are not appropriately tailored to the task in question. However, their learning performance can often be improved by taking advantage of deeper insight of the application domain or the learning problem at hand. This thesis considers developing kernel-based learning algorithms incorporating this kind of prior knowledge of the task in question in an advantageous way. Moreover, computationally efficient algorithms for training the learning machines for specific tasks are presented. In the context of kernel-based learning methods, the incorporation of prior knowledge is often done by designing appropriate kernel functions. Another well-known way is to develop cost functions that fit to the task under consideration. For disambiguation tasks in natural language, we develop kernel functions that take account of the positional information and the mutual similarities of words. It is shown that the use of this information significantly improves the disambiguation performance of the learning machine. Further, we design a new cost function that is better suitable for the task of information retrieval and for more general ranking problems than the cost functions designed for regression and classification. We also consider other applications of the kernel-based learning algorithms such as text categorization, and pattern recognition in differential display. We develop computationally efficient algorithms for training the considered learning machines with the proposed kernel functions. We also design a fast cross-validation algorithm for regularized least-squares type of learning algorithm. Further, an efficient version of the regularized least-squares algorithm that can be used together with the new cost function for preference learning and ranking tasks is proposed. In summary, we demonstrate that the incorporation of prior knowledge is possible and beneficial, and novel advanced kernels and cost functions can be used in algorithms efficiently.

Learning Preferences with Kernel-Based Methods

Learning of preference relations has recently received significant attention in machine learning community. It is closely related to the classification and regression analysis and can be reduced to these tasks. However, preference learning involves prediction of ordering of the data points rather than prediction of a single numerical value as in case of regression or a class label as in case of classification. Therefore, studying preference relations within a separate framework facilitates not only better theoretical understanding of the problem, but also motivates development of the efficient algorithms for the task. Preference learning has many applications in domains such as information retrieval, bioinformatics, natural language processing, etc. For example, algorithms that learn to rank are frequently used in search engines for ordering documents retrieved by the query. Preference learning methods have been also applied to collaborative filtering problems for predicting individual customer choices from the vast amount of user generated feedback. In this thesis we propose several algorithms for learning preference relations. These algorithms stem from well founded and robust class of regularized least-squares methods and have many attractive computational properties. In order to improve the performance of our methods, we introduce several non-linear kernel functions. Thus, contribution of this thesis is twofold: kernel functions for structured data that are used to take advantage of various non-vectorial data representations and the preference learning algorithms that are suitable for different tasks, namely efficient learning of preference relations, learning with large amount of training data, and semi-supervised preference learning. Proposed kernel-based algorithms and kernels are applied to the parse ranking task in natural language processing, document ranking in information retrieval, and remote homology detection in bioinformatics domain. Training of kernel-based ranking algorithms can be infeasible when the size of the training set is large. This problem is addressed by proposing a preference learning algorithm whose computation complexity scales linearly with the number of training data points. We also introduce sparse approximation of the algorithm that can be efficiently trained with large amount of data. For situations when small amount of labeled data but a large amount of unlabeled data is available, we propose a co-regularized preference learning algorithm. To conclude, the methods presented in this thesis address not only the problem of the efficient training of the algorithms but also fast regularization parameter selection, multiple output prediction, and cross-validation. Furthermore, proposed algorithms lead to notably better performance in many preference learning tasks considered.

Kernel-Based Ranking. Methods for Learning and Performance Estimation

Machine learning provides tools for automated construction of predictive models in data intensive areas of engineering and science. The family of regularized kernel methods have in the recent years become one of the mainstream approaches to machine learning, due to a number of advantages the methods share. The approach provides theoretically well-founded solutions to the problems of under- and overfitting, allows learning from structured data, and has been empirically demonstrated to yield high predictive performance on a wide range of application domains. Historically, the problems of classification and regression have gained the majority of attention in the field. In this thesis we focus on another type of learning problem, that of learning to rank. In learning to rank, the aim is from a set of past observations to learn a ranking function that can order new objects according to how well they match some underlying criterion of goodness. As an important special case of the setting, we can recover the bipartite ranking problem, corresponding to maximizing the area under the ROC curve (AUC) in binary classification. Ranking applications appear in a large variety of settings, examples encountered in this thesis include document retrieval in web search, recommender systems, information extraction and automated parsing of natural language. We consider the pairwise approach to learning to rank, where ranking models are learned by minimizing the expected probability of ranking any two randomly drawn test examples incorrectly. The development of computationally efficient kernel methods, based on this approach, has in the past proven to be challenging. Moreover, it is not clear what techniques for estimating the predictive performance of learned models are the most reliable in the ranking setting, and how the techniques can be implemented efficiently. The contributions of this thesis are as follows. First, we develop RankRLS, a computationally efficient kernel method for learning to rank, that is based on minimizing a regularized pairwise least-squares loss. In addition to training methods, we introduce a variety of algorithms for tasks such as model selection, multi-output learning, and cross-validation, based on computational shortcuts from matrix algebra. Second, we improve the fastest known training method for the linear version of the RankSVM algorithm, which is one of the most well established methods for learning to rank. Third, we study the combination of the empirical kernel map and reduced set approximation, which allows the large-scale training of kernel machines using linear solvers, and propose computationally efficient solutions to cross-validation when using the approach. Next, we explore the problem of reliable cross-validation when using AUC as a performance criterion, through an extensive simulation study. We demonstrate that the proposed leave-pair-out cross-validation approach leads to more reliable performance estimation than commonly used alternative approaches. Finally, we present a case study on applying machine learning to information extraction from biomedical literature, which combines several of the approaches considered in the thesis. The thesis is divided into two parts. Part I provides the background for the research work and summarizes the most central results, Part II consists of the five original research articles that are the main contribution of this thesis.

Recording and reproducing Soundscapes : using and interpreting data in a creative way

http://elo.aalto.fi/fi/studies/elomedia/dataseminar/

Vanhasuomalaisuutta uusintamassa : Kokoomuksen ja SDP:n ryhmäpuheenvuorot EU:n ulko- ja turvallisuuspolitiikasta 1995-2000

Abstract: Reproducing the Old Finn mentality

Pääministerin vallan kasvu Suomessa

Abstract: Reproducing the Old Finn mentality

EU-keskustelun vaikeudesta

Abstract: Reproducing the Old Finn mentality

Yhteisön langaton palvelualusta

Yhteisön langaton palvelualusta on konsepti langattomien yhteisöllisten verkkopalveluiden tarjoamiseen.Konsepti perustuu langattomaan WLAN-reititinlaitteeseen sekä Linux-käyttöjärjestelmäpohjaiseen laiteohjelmistoon, joiden avulla voidaan tarjota paikallisia, erilaisten pienten yhteisöjen käyttöön tarkoitettuja langattomia verkkopalveluita.Soveltuvia käyttökohteita voivat olla esimerkiksi asuntoyhteisöjen välinen tiedotuskanava tai perheen sisäinen viihdekeskus, jonka kautta voidaan tarjota yhteisön toimintaa helpottavia ja tavoitteita edistäviä palveluita. Yhteisön langattomat palvelut perustuvat vapaisiin ohjelmistoihin, jotka mahdollistavat monipuolisen palveluvalikoiman luomisen. Langattoman palvelualustan avulla pienten yhteisöjen tarvitsemat langattomat palvelut voidaan luoda helposti, edullisesti ja joustavasti, ilman kaupallisten palveluoperaattoreiden asettamia rajoituksia.

Benchmarking Symbian OS smartphones

Diplomityön tarkoituksena oli luoda menetelmä Symbian-käyttöjärjestelmää käyttävien älypuhelinten suorituskyvyn määrittämiseen, jotta laitteiden välisiä eroja voitaisiin mitata. Aluksi Symbian-käyttöjärjestelmää ja älypuhelinlaitteistoja tutkittiin suorituskykyyn ja sen vaihteluun vaikuttavien tekijöiden ja osien löytämiseksi. Tämän jälkeen kehitettiin useita testitapauksia sisältävä testikirjasto, jolla voitiin mitata joidenkin suorituskykyyn vaikuttavien käyttöjärjestelmän rajapintojen suoritusaikoja. Testikirjaston testit ajettiin kolmella eri älypuhelinmallilla, jotta testien toimivuutta voitiin arvioida. Lopuksi testituloksia analysoitiin mahdollisten pullonkaulojen havaitsemiseksi suorituskyvystä. Testikirjaston pystyttiin havaitsemaan eroja laitteiden suorituskyvyssä. Viimeisin, uudella Symbianin EKA2-ytimellä varustettu älypuhelin, Nokia E70, jäi mittauksissa viimeiseksi, koska se pärjäsi huonosti muistinvarauksia ja TRAP-poikkeuksia testaavissa tapauksissa. Muilla mitatuilla osa-alueilla se kuitenkin päihitti selvästi muut testatut puhelimet, Nokia N90:n ja Nokia 6630:n. Näiden kahden muun laitteen tulosten skaalan tasaisuus osoittaa, että kehitetyn testikirjaston avulla saadaan johdonmukaisia ja uskottavia mittaustuloksia.

Thick XML client and technology of its construction

Nykyään kolmeen kerrokseen perustuvat client-server –sovellukset ovat suuri kinnostuskohde sekä niiden kehittäjille etta käyttäjille. Tietotekniikan nopean kehityksen ansiosta näillä sovelluksilla on monipuolinen käyttö teollisuuden eri alueilla. Tällä hetkellä on olemassa paljon työkaluja client-server –sovellusten kehittämiseen, jotka myös tyydyttävät asiakkaiden asettamia vaatimuksia. Nämä työkalut eivät kuitenkaan mahdollista joustavaa toimintaa graafisen käyttöliittyman kanssa. Tämä diplomityö käsittelee client-server –sovellusten kehittamistä XML –kielen avulla. Tämä lähestymistapa mahdollistaa client-server –sovellusten rakentamista niin, että niiden graafinen käyttöliittymä ja ulkonäkö olisivat helposti muokattavissa ilman ohjelman ytimen uudelleenkääntämistä. Diplomityö koostuu kahdesta ostasta: teoreettisesta ja käytännöllisestä. Teoreettinen osa antaa yleisen tiedon client-server –arkkitehtuurista ja kuvailee ohjelmistotekniikan pääkohdat. Käytannöllinen osa esittää tulokset, client-server –sovellusten kehittämisteknologian kehittämislähestymistavan XML: ää käyttäen ja tuloksiin johtavat usecase– ja sekvenssidiagrammit. Käytännöllinen osa myos sisältää esimerkit toteutetuista XML-struktuureista, jotka kuvaavat client –sovellusten kuvaruutukaavakkeiden esintymisen ja serverikyselykaaviot.

Multilayer switch hardware support for Linux

VDSL on teknologia, joka mahdollistaa nopeat Internet-yhteydet tavallista puhelinlinjaa käyttäen. Tätä varten käyttäjä tarvitsee VDSL-modeemin ja Internet-operaattori reitittimen, johon VDSL-linjat kytketään. Reitittimen on oltava suorituskykyinen, jotta kaikki VDSL-liikenne voidaan reittittää eteenpäin. Tehokkuutta haetaan tekemällä suuri osa reitityksestä erityisillä reititinpiireillä. Tässä diplomityössä käsitellään reititinpiirien teoriaa ja niiden hallintaa. Lisäksi vertailtiin kolmen suuren valmistajan tuotteita. Tuotteiden tarjoamat ominaisuudet vaikuttivat hyvin yhteneväisiltä. Ominaisuuksien hallinta ja toteutus olivat erilaisia. Työn tavoitteena oli löytää ohjelmistoarkkitehtuuri piirien ohjaamiseen niin, että Linux-käyttöjärjestelmän ytimen palveluja voitaisiin käyttää mahdollisimman hyödyllisesti. Työssä havaittiin, että ohjelmistoarkkitehtuurin voi määritellä monella eri tavalla riippuen siitä, miten piiri on kytketty prosessoriin, mitä piirin ominaisuuksia halutaan käyttää ja miten arkkitehtuuria halutaan jatkossa laajentaa.

STACK OVERWRITING ATTACKS AND DEFENCES IN UNIX ENVIRONMENT

Työn tarkoituksena on tutkia pinon ylikirjoitukseen perustuvien hyökkäysten toimintaa ja osoittaa kokeellisesti nykyisten suojaustekniikoiden olevan riittämättömiä. Tutkimus suoritetaan testaamalla miten valitut tietoturvatuotteet toimivat eri testitilanteissa. Testatut tuotteet ovat Openwall, PaX, Libsafe 2.0 ja Immunix 6.2. Testaus suoritetaan pääasiassa RedHat 7.0 ympäristössä testiohjelman avulla. Testeissä mitataan sekä tuotteiden kyky havaita hyökkäyksiä että niiden nopeusvaikutukset. Myös erityyppisten hyökkäysten ja niitä vastaan kehitettyjen metodien toimintaperiaatteet esitellään seikkaperäisesti ja havainnollistetaan yksinkertaistetuilla esimerkeillä. Esitellyt tekniikat sisältävät puskurin ylivuodot, laittomat muotoiluparametrit, loppumerkittömät merkkijonot ja taulukoiden ylivuodot. Testit osoittavat, etteivät valitut tuotteet estä kaikkia hyökkäyksiä, joten lopuksi perehdytään myös vahinkojen minimointiin onnistuneiden hyökkäysten varalta.

Real-time Linux in electric drive systems

Reaaliaikaisten käyttöjärjestelmien käyttö sulautetuissa järjestelmissä on kasvamassa koko ajan. Sulautettuja tietokoneita käytetään yhä useammassa kohteessa kuten sähkökäyttöjen ohjauksessa. Sähkökäyttöjen ohjaus hoidetaan nykyisin yleensä nopealla digitaalisella signaaliprosessorilla (DSP), jolloin ohjelmointi ja päivittäminen on hidasta ja vaikeaa johtuen käytettävästä matalan tason Assembler-kielestä. Ratkaisuna yleiskäyttöisten prosessorien ja reaaliaikakäyttöjärjestelmien käyttö. Kaupalliset reaaliaikakäyttöjärjestelmät ovat kalliita ja lähdekoodin saaminen omaan käyttöön jopa mahdotonta. Linux on ei-kaupallinen avoimen lähdekoodin käyttöjärjestelmä, joten sen käyttö on ilmaista ja sitä voi muokata vapaasti. Linux:iin on saatavana useita laajennuksia, jotka tekevät siitä reaaliaikaisen käyttöjärjestelmän. Vaihtoehtoina joko kova (hard) tai pehmeä (soft) reaaliaikaisuus. Linux:iin on olemassa valmiita kehitysympäristöjä mutta ne kaipaavat parannusta ennen kuin niitä voidaan käyttää suuressa mittakaavassa teollisuudessa. Reaaliaika Linux ei sovellus nopeisiin ohjauslooppeihin (<100 ms) koska nopeus ei riitä vielä mutta nopeus kasvaa samalla kun prosessorit kehittyvät. Linux soveltuu hyvin rajapinnaksi nopean ohjauksen ja käyttäjän välille ja hitaampaan ohjaukseen.