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.

Tutkielmassa käsitellään symmetristen ja vasta-symmetristen ydinfunktioiden teoreettisia ominaisuuksia. Ensimmäisissä kappeleissa esitetään tiivistelmä ydinfunktioiden käytöstä valvotussa koneoppimisessa. Työn kannalta keskeisenä algoritmina käsitellään neliösumman minimointia, joka tutkielmassa motivoidaan diskretisoidun funktion uudelleenrakentamisena abstraktin käänteisongelman kautta. Lyhyt katsaus Hilbert-avaruuksien teoriaan osoittaa ydinfunktion määrittämän funktioavaruuden ja kirjallisuudessa käytetyt loogisesti ekvivalentit konstruktiot tälle avaruudelle, sekä miten ydinfunktioita muokkaamalla saadaan avaruuksia joihin sisältyy esitietoa opittavasta funktiosta. Matemaattisia tuloksia abstraktista käänteisongelmasta, erityisesti sen spektriominaisuuksia, pseudokäänteisfunktiota ja kompleksisuusrajoituksia kootaan yhteen ja sovelletaan ydinfunktioilla oppimiseen. Symmetrisiä ja vasta-symmetrisiä ydinfunktioita sovelletaan relaatio-oppimisongelmissa joissa tiedetään että opittava relaatio on joko symmetrinen tai vasta-symmetrinen. Näiden ydinfunktioiden teoreettisia ominaisuuksia todistetaan julkaisuluonnoksessa jonka varaan tämä tutkielma rakentuu ja näihin tuloksiin viitataan kattavasti. Nämä todisteukset osoittavat että ydinfunktiot voivat oppia vain symmetrisiä ja vasta-symmetrisiä relaatioita, ja toisaalta ne voivat oppia minkä tahansa funktion suhteessa alkuperäiseen ydinfunktioon joka on muokattu oppimaan symmetrisiä tai vasta-symmetrisiä osia. Muut tulokset osoittavat spektriin liittyviä ominaisuuksia, joista keskeinen on yksinkertainen epäyhtälö arvioijan ominaisarvosummalle, jota myös kutsutaan arvioijan käytännön ulottuvuudeksi (effective dimension). Tätä mittaa käytetään esimerkiksi oppimisteoriassa takaamaan pienempi varianssi.