Finding dependencies in data with information-theoretic methods

Davor Sluga (Avtor), Uroš Lotrič (Mentor)

Povzetek

Izbira značilk je nujna na mnogih področjih, ki vključujejo visoko-dimenzionalne podatke. Izboljšuje možnost posploševanja regresijskih in klasifikacijskih metod in s tem tudi uspešnost modeliranja sistemov ter omogoča lažjo interpretacijo podatkov. Pomembnost značilk ocenimo s pomočjo kriterijske funkcije. Informacijske mere so samoumevne kandidatke, saj izhajajo iz cilja izbire značilk: želimo pridobiti nabor značilk, ki nudijo največ informacij o sistemu. Informacijsko-teoretične metode izbiranja značilk ponavadi potrebujejo oceno verjetnostne porazdelitve podatkov, na žalost pa se njeno ocenjevanje velikokrat izkaže za problematično. V disertaciji predlagamo novo metodo za izbiro značilk QMIFS (ang. quadratic mutual information feature selection), ki temelji na kvadratni medsebojni informaciji. Ta informacijsko-teoretična mera izhaja iz Cauchy-Schwarzeve divergence in Renyijeve entropije. Metoda uporablja neposredno oceno kvadratne medsebojne informacije iz podatkov z uporabo Gaussovih jedrnih funkcij. Zazna lahko nelinearne odvisnosti drugega reda. Izbira značilk iz velikih zbirk podatkov lahko postane zaradi dolgih izvajalnih časov praktično neuporabna. Računsko zahtevnost naše metode zmanjšamo s pomočjo nepopolne dekompozicije Choleskega nad vhodnimi podatki in ustreznim preoblikovanjem izračuna kriterijske funkcije. Učinkovitost predlagane metode se kaže skozi obsežno primerjavo z metodami MIFS (ang. mutual information feature selection), MRMR (ang. minimum redundancy maximum relevance) in JMI (ang. joint mutual information) na regresijski in klasifikacijski problemski domeni. Rezultati kažejo, da je predlagana metoda iz stališča uspešnosti modela primerljiva z ostalimi na klasifikacijskih problemih, le da je precej hitrejša. Na regresijskih problemih je nekoliko bolj uspešna od ostalih, vendar počasnejša. Zaporedni algoritmi za izbiro značilk lahko odpovejo, če podatkovna množica vsebuje več sto ali celo več tisoč značilk. Masovno vzporedni sistemi, kot na primer grafične procesne enote, nudijo veliko računske moči in naredijo analizo visoko-dimenzionalnih podatkovnih množic časovno izvedljivo. Predlagano metodo za izbiro značilk smo preoblikovali tako, da omogoča izrabo zmogljivih grafičnih procesnih enot in računskih koprocesorjev. Dosegli smo precejšnje zmanjšanje časov izvajanja, zaradi česar je metoda veliko bolj primerna za uporabo na velikih zbirkah podatkov.

Ključne besede

feature selection;information theory;Cauchy-Shwarz divergence;Renyi entropy;general-purpose GPU computing;computer and information science;doctoral dissertations;

Podatki

Jezik:	Angleški jezik
Leto izida:	2017
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[D. Sluga]
UDK:	004.8:519.72(043.3)
COBISS:	1537654979
Št. ogledov:	1196
Št. prenosov:	518
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Finding dependencies in data with information-theoretic methods
Sekundarni povzetek:	The selection of features that are relevant for a classification or a regression problem is very important in many domains which involve high-dimensional data. It improves the performance and generalization capabilities of regression and classification methods and facilitates the interpretation of the data about a system. To assess feature relevance, some kind of criterion function must be used. Information measures are an obvious candidate because they arise from the goal of feature selection: we wish to obtain a set of features that contain the most information about a system. Information-theoretic feature selection methods usually need to estimate the probability distributions of the data in order to assess feature relevance, this often proves to be problematic. In this thesis we propose a novel feature selection method (QMIFS) based on quadratic mutual information which has its roots in Cauchy--Schwarz divergence and Renyi entropy. The method uses the direct estimation of quadratic mutual information from data samples using Gaussian kernel functions, and can detect second order non-linear relations. Feature selection on large data sets can be infeasible due to long execution times. We reduce the computational complexity of the method through incomplete Cholesky decomposition of the input data and derive an appropriate estimator of the criterion function. The effectiveness of the proposed method is demonstrated through an extensive comparison with mutual information feature selection (MIFS), minimum redundancy maximum relevance (MRMR), and joint mutual information (JMI) on classification and regression problem domains. The experiments show that proposed method performs comparably to the other methods when applied to classification problems, except it is considerably faster. In the case of regression, it compares favourably to the others, but is slower. If the data includes hundreds or even thousands of features, sequential algorithms for feature selection may no longer suffice. Nowadays massively parallel systems such as graphics processing units offer the computational power to make analysis of high-dimensional data feasible. We modified the proposed method to make use of the powerful hardware of graphics processing units. We achieve considerable improvements in the execution times, making it viable for usage on large data sets.
Sekundarne ključne besede:	iskanje značilk;teorija informacij;Cauchy-Shwarzova divergenca;Renyijeva entropija;splošno namensko računanje na GPE;računalništvo in informatika;doktorske disertacije;Podatki;Disertacije;Odvisnost;Teorija informacij;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Doktorsko delo/naloga
Študijski program:	1000474
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	VII, 133 str.
ID:	10914843