Stochastic Discriminant Analysis

Abstract

The processing powers of computers have increased constantly during the last decades. Ordinary personal computers are now able to perform intricate calculations with datasets. Large datasets, such as images, create unique challenges as they often contain more variables than used in ordinary statistical analysis.

In dimension reduction we are decreasing the amount of variables by combining them. The locations of the data points in a low-dimensional space are often optimized with respect to some predefined criteria. If we use a response variable to guide the search of the subspace, the method is called a supervised method. When the objective of the dimension reduction is to reduce the size of the space to two or three dimensions, the procedure is often called visualization. This thesis is mostly focused on supervised visualization.

This thesis first discusses a supervised dimension reduction tool developed at the Aalto University: Supervised Distance Preserving Projections (SDPP). The method matches response space distances with linearly transformed input space distances using the Euclidean divergence. Second, this thesis introduces a new method for dimension reduction based on the SDPP: Stochastic Discriminant Analysis (SDA). The method matches point-to-point neighbor probabilities in the linearly transformed input space with target probabilities from the response space, using the relative entropy (Kullback-Leibler divergence). Finally, the performance of this method is analyzed against some selected supervised state-of-the-art dimension reduction methods on contemporary datasets.

Under de senaste decennierna har moderna bordsdatorer utvecklats avsevärt. Modern processeringsförmåga möjliggör komplicerad databehandling. I analysering av stora datamängder behöver man dock i praktiken förhandsbehandla datan för att minska minnesanvändningen och processeringstiden.

I dimensionsförminskning strävar man efter att minska antalet variabler i datan. Ifall responsvariabler som associeras med observationerna används till nytta kallar man förminskningsmetoderna handledda. Dimensionsförminskning kallas också visualisering då man förminskar datan till två eller tre dimensioner med avsikt att betrakta datan ögonmässigt. I detta diplomarbete fokuserar jag på handledda visualiseringsmetoder.

Först undersöks handledda dimensionsförminskningsmetoden Supervised Distance Preserving Projections (SDPP). Metoden passar ihop avstånd mellan datapunkter i en lågdimensionell projektion av indatan med motsvarande avstånd i utdatan genom att använda Euklidiska divergensen. Sedan utvecklas en motsvarande metod baserad på sannolikhetskalkyl och metodens lämplighet till dimensionsförminskning undersöks. Metoden passar ihop icke-linjärt projiserade avstånd i indatan med motsvarande avstånd i utdatan genom att utnyttja relativa entropin (Kullback-Leibler divergens) mellan de sannolikhetsfördelningar som dessa avstånd ger upphov till. I slutet av diplomarbetet jämförs metodens nyttighet med andra motsvarande metoder.