Finding dependencies in data with information-theoretic methods

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

Abstract

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.

Keywords

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

Data

Language:	English
Year of publishing:	2017
Typology:	2.08 - Doctoral Dissertation
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[D. Sluga]
UDC:	004.8:519.72(043.3)
COBISS:	1537654979
Views:	1196
Downloads:	518
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Finding dependencies in data with information-theoretic methods
Secondary abstract:	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.
Secondary keywords:	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;
File type:	application/pdf
Type (COBISS):	Doctoral dissertation
Study programme:	1000474
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	VII, 133 str.
ID:	10914843