Overfitting in feature selection: Pitfalls and solutions

Abstract

When facing a typical pattern recognition task, one usually comes up with a number of so-called features: properties that describe the objects to be recognised. Based on these features, the task of the classifier building algorithm is to find useful rules that are suitable for the recognition of new objects. Feature selection is a process where one tries to identify the useful features from among a potentially large set of candidates. The task is notoriously hard, and researchers have been tackling it already for decades. Solving the problem properly might today be more important than ever before, because in many applications, dataset sizes seem to grow faster than does the processing power of computers. For example, in the domain of genetic microarray data, there can easily be thousands of features. Several research groups have published comparisons aiming to identify the feature selection method that is universally the best. Unfortunately, too often the way that such comparisons are done is just plain wrong. Based on the results of such studies, the computationally intensive search algorithms seem to perform much better than the simple approaches. However, it is shown in this thesis that when the comparison is done properly, it very often turns out that the simple and fast algorithms give results that are just as good, if not even better. In addition, many studies suggest that excluding some of the features is much more useful than it actually is. This observation is relevant in practice, because the selection process typically takes a lot of time and computing resources - therefore, it would be very convenient not to have to carry it out at all. This thesis shows that the benefits obtained may be negligible compared to what has been presented previously, provided that they are measured correctly. Moreover, the thesis presents a better-performing approach for accuracy estimation in case the amount of data is small. Further, extensions are discussed from feature selection to generic model selection, from the selection of individual features to that of sensors measuring the features, and from classification to regression. Finally, an industrial application is pointed out where the methods discussed prove useful.

Hahmontunnistustehtävää ratkaistaessa määritetään yleensä joukko piirteitä eli ominaisuuksia, jotka kuvaavat tunnistettavia kohteita. Luokittelijan rakentavan algoritmin tehtävä on löytää näihin piirteisiin perustuvat säännöt, jotka soveltuvat uusien kohteiden luokitteluun. Piirrevalinnassa pyritään löytämään käyttökelpoiset piirteet mahdollisesti suuresta ehdokkaiden joukosta. Tehtävä on vaikea: sitä on yritetty ratkaista jo 1960-luvulta lähtien. Aihe on edelleen ajankohtainen, sillä aineistojen koot kasvavat monissa sovelluksissa jopa nopeammin kuin tietokoneiden laskentakapasiteetti. Esimerkiksi geneettisissä tutkimuksissa käytettävissä olevien piirteiden määrä nousee helposti tuhansiin. Monissa vertailevissa tutkimuksissa on pyritty löytämään paras piirrevalintamenetelmä, mutta vertailu on usein tehty väärin. Tällöin on saatu tuloksia, joiden mukaan raskaat hakualgoritmit tuottavat selvästi parempia tuloksia kuin mitä yksinkertaisilla ja nopeilla menetelmillä saadaan. Tässä väitöskirjassa osoitetaan, että raskaat ja hitaat algoritmit eivät välttämättä anna lainkaan parempia tuloksia, kunhan vertailu yksinkertaisiin menetelmiin tehdään oikeaoppisesti. Kirjallisuudessa annetaan myös ymmärtää piirrevalinnan olevan hyödyllisempää kuin mitä se todellisuudessa on. Tämä on käytännön sovellusten kannalta tärkeä havainto, sillä usein valintaprosessi vie paljon aikaa ja laskentaresursseja, joten olisi helpotus, jos sitä ei tarvitsisi lainkaan tehdä. Tässä työssä tuodaan esille, että piirrevalinnalla saavutetut hyödyt voivat olla suorastaan olemattomia kirjallisuudessa aiemmin esitettyyn verrattuna, mikäli mittaaminen suoritetaan oikein. Väitöskirjassa esitetään myös uusi tarkkuuden estimointiin soveltuva menettely, joka suoriutuu aikaisemmin tunnettuja menetelmiä paremmin silloin, kun dataa on vain vähän. Lisäksi käydään läpi laajennuksia piirrevalinnasta yleisempään mallinvalintaan, yksittäisten piirteiden valinnasta sensorien valintaan, sekä luokittelusta regressioon. Lopuksi käsitellään teollista sovellusta, jonka yhteydessä työssä esitellyt menetelmät osoittautuvat käyttökelpoisiksi.