I detta dokument granskar vi problemet med att välja relevanta funktioner för användning i maskininlärning. Vi beskriver detta problem i termer av heuristisk sökning genom ett utrymme av funktionsuppsättningar, och vi identifierar fyra dimensioner längs vilka sätt att närma sig problemet kan variera. Vi betraktar det senaste arbetet med urval av funktioner i termer av denna ram och avslutar sedan med vissa utmaningar för det framtida arbetet inom området. Valet av relevanta egenskaper, och elimineringen av irrelevanta, är ett centralt problem inom maskininlärning. Innan en induktionsalgoritm kan gå bortom träningsdata för att göra förutsägelser om nya testfall, måste den bestämma vilka attribut som ska användas i dessa förutsägelser och vilka som ska ignoreras. Intuitivt skulle man vilja att eleven endast använde de attribut som är "relevanta" för målkonceptet. Det har gjorts några försök att de ne'relevance' i samband med maskininlärning, som John, Kohavi och P eger (1994) har noterat i sin genomgång av detta ämne. Eftersom vi kommer att se över en rad olika strategier tar vi inte ställning i den här frågan. Vi kommer istället att fokusera på uppgiften att välja relevanta funktioner (dock de ned) för användning i lärande och förutsägelse. Många induktionsmetoder försöker att direkt ta itu med problemet med attributval, särskilt de som fungerar på logiska representationer. Till exempel, tekniker för att framkalla logiska samband gör lite mer än att lägga till eller ta bort funktioner från konceptbeskrivningen. Tillägg och strykning av enskilda attribut utgör också den grundläggande verksamheten med mer sofistikerade metoder för att få fram beslutslistor och beslutsträd. Vissa icke-logiska induktionsmetoder, som de för neurala nätverk och Bayesian classi ers, istället använda vikter för att tilldela grader av relevans för attribut. Och en del inlärningsprogram, till exempel den enkla närmaste grannmetoden, ignorerar helt och hållet frågan om relevans. Vi vill ha induktionsalgoritmer som skalas väl till domäner med många irrelevanta funktioner. Mer specifikt vill vi att urvalets komplexitet (antalet utbildningsfall som krävs för att uppnå en viss noggrannhetsnivå) ska växa långsamt med antalet irrelevanta attribut. Teoretiska resultat för algoritmer som söker begränsade hypotesrymder är uppmuntrande. Till exempel, det värsta fall antalet fel som gjorts av Littlestone's (1987) Men de teoretiska resultaten är mindre optimistiska för induktionsmetoder som söker ett större utrymme av konceptbeskrivningar. Till exempel, Langley och Ibas (1993) genomsnittliga fall analys av enkla närmaste granne indikerar att dess urval komplexitet växer exponentiellt med antalet irrelevanta attribut, även för konjunktiva målkoncept. Experimentella studier av närmaste granne är förenliga med denna slutsats, och andra experiment tyder på att liknande resultat håller även för induktionsalgoritmer som uttryckligen väljer funktioner. Till exempel verkar urvalets komplexitet för beslutsträdsmetoder växa linjärt med antalet irrelevanta begrepp, men exponentiellt för paritetsbegrepp, eftersom utvärderingsmåttet inte kan skilja relevanta från irrelevanta egenskaper i den senare situationen (Langley & Sage, i pressen). Resultat av detta slag har uppmuntrat maskininlärning forskare att utforska mer sofistikerade metoder för att välja relevanta funktioner. I de följande avsnitten lägger vi fram en allmän ram för denna uppgift, och sedan tar vi upp några aktuella exempel på arbete med detta viktiga problem. Man kan se funktionen markering som ett sökproblem, med varje tillstånd i sökområdet som anger en delmängd av de möjliga funktionerna. Som figur 1 visar kan man införa en partiell beställning på detta utrymme, där varje barn har exakt ett annat drag än sina föräldrar. Strukturen på detta utrymme tyder på att varje funktion urvalsmetod måste ta ställning i fyra grundläggande frågor som avgör arten av den heuristiska sökprocessen. Först måste man bestämma utgångspunkten i utrymmet, som i sin tur bestämmer sökriktningen. Till exempel, man kan börja med några funktioner och successivt lägga till attribut, eller man kan börja med alla attribut och successivt ta bort dem. Det tidigare tillvägagångssättet kallas ibland för framåtriktat urval, medan det senare kallas för bakåtriktad eliminering. Man kan också välja ett första tillstånd någonstans i mitten och flytta ut från denna punkt. Ett andra beslut gäller organisationen av sökningen. Det är uppenbart att en fullständig sökning av utrymmet är opraktisk, eftersom det finns 2 möjliga undergrupper av en attribut. Ett mer realistiskt tillvägagångssätt är beroende av en girig metod för att färdas genom rymden. Vid varje punkt i sökningen, tar man hänsyn till lokala ändringar i den nuvarande uppsättningen av attribut, väljer en, och sedan itererar, aldrig ompröva valet. En relaterad metod, känd som stegvis urval eller eliminering, överväger både lägga till och ta bort funktioner vid varje beslutspunkt, som låter en dra tillbaka ett tidigare beslut utan att hålla explicit spår av sökvägen. Inom dessa alternativ kan man överväga alla tillstånd som genereras av operatörerna och sedan välja det bästa, eller så kan man helt enkelt välja det rst-tillstånd som förbättrar noggrannheten över den aktuella uppsättningen. Man kan också ersätta det giriga systemet med mer sofistikerade metoder, t.ex. bästa-rest-sökning, som är dyrare men fortfarande lätthanterliga inom vissa områden. En tredje fråga gäller den strategi som används för att utvärdera alternativa undergrupper av attribut. En bred klass av strategier anser attribut oberoende av induktionsalgoritmen som kommer att använda dem, beroende på allmänna egenskaper av utbildningen uppsättningen för att välja vissa funktioner och utesluta andra. John, Kohavi, och P eger (1994) kallar dessa Lter metoder, eftersom de ter sig irrelevanta attribut innan induktionsprocessen inträffar. De kontrasterar detta tillvägagångssätt med omslagsmetoder, som genererar en uppsättning kandidatfunktioner, kör induktionsalgoritmen på träningsdata, och använda noggrannheten i den resulterande beskrivningen för att utvärdera funktionen uppsättning. Inom detta tillvägagångssätt, måste man fortfarande välja någon uppskattning för noggrannhet, men detta val verkar mindre centralt än att göra upp på en ter eller wrapper system. Slutligen måste man besluta om något kriterium för att stoppa sökning genom utrymmet för funktionsundergrupper. Inom ramen för omslag, kan man sluta lägga till eller ta bort attribut när inget av alternativen förbättrar uppskattningen av classi katjon noggrannhet, man kan fortsätta att revidera funktionen som så länge noggrannhet inte försämrar, eller man kan fortsätta att generera kandidatuppsättningar tills den når den andra änden av sökområdet och sedan välja det bästa. Inom ramen för Lter, ett kriterium för att stoppa anteckningar när varje kombination av värden för de valda attributen kartor på en enda klass värde. Ett annat alternativ helt enkelt beställer funktioner enligt vissa resiliens poäng, sedan använder en systemparameter för att bestämma brytpunkten. Observera att ovanstående metoder för funktionsval kan kombineras med vilken induktionsalgoritm som helst för att öka inlärningshastigheten i domäner med irrelevanta attribut. Den eekt på beteende kan di er för olika induktionstekniker och för olika målkoncept, i vissa fall producerar lite bene t och i andra ger stor förbättring. Men den grundläggande idén om att söka utrymme för funktioner uppsättningar är konceptuellt och praktiskt skiljer sig från den specifika c induktionsmetod som bene ts från funktionen-urvalsprocessen. Problemet med val av funktioner har länge varit ett aktivt forskningsämne inom statistik och mönsterigenkänning (t.ex. Devijver & Kittler, 1982), men det mesta arbetet inom detta område har handlat om linjär regression. Under de senaste åren, funktionsval har fått stor uppmärksamhet från maskininlärning forskare som är intresserade av att förbättra prestandan för sina algoritmer. De tidigaste tillvägagångssätt för att funktionsval inom maskininlärning betonade ltering metoder. Till exempel, Almuallim och Dietterich's (1991) Focus algoritm börjar med en tom funktion set och utför bredd-rst sökning tills det nds en minimal kombination av funktioner som förutspår rena klasser. Systemet passerar sedan den reducerade funktionen set till ID3, som konstruerar ett beslutsträd för att sammanfatta träningsdata. Schlimmer (1993) beskrev ett relaterat tillvägagångssätt som utför en systematisk sökning (för att undvika återbesök) genom utrymmet för funktionsuppsättningar, återigen börjar med den tomma uppsättningen och lägger till funktioner tills det är en kombination som överensstämmer med träningsdata. Kira och Rendell (1992) använde en ganska olika system för ltering attribut. Deras hjälpalgoritm tilldelar en vikt till varje funktion som reekterar dess förmåga att skilja mellan klasserna, väljer sedan dessa funktioner med vikter som överstiger en användar-specied tröskel. Systemet använder sedan ID3 för att inducera ett beslutsträd från träningsdata med endast de valda funktionerna. Relief inte riktigt in i vår ram, eftersom det tvingar en linjär ordning på funktionerna i stället för att söka det delvis beställda utrymmet av funktionsuppsättningar. Kononenko (1994) rapporterar två tillägg till metoden som hanterar icke-booleska attribut, och Doak (1992) har undersökt liknande metoder till problemet. Även Focus och Relief följer funktionen urval med beslut träd konstruktion, kan man också kombinera det förra med andra induktionsmetoder. Till exempel använde Cardie (1993) en ltering metod för att identifiera en undergrupp av funktioner för användning i närmaste grannhämtning, medan Kubat, Flotzinger och Pfurtscheller (1993) letsade funktioner för användning med en naiv Bayesian classi er. Båda använde C4.5 för att konstruera ett beslutsträd från datan, men bara för att bestämma de egenskaper som skulle överföras till deras primära induktionsmetoder. Den senaste forskningen om val av funktioner diers från dessa tidiga metoder genom att förlita sig på omslagsstrategier snarare än ltering system. Det allmänna argumentet för wrapper metoder är att induktionsmetoden som kommer att använda funktionen delmängd bör ge en bättre uppskattning av noggrannhet än en separat åtgärd som kan ha en helt olika induktiva fördomar. John, Kohavi och P eger (1994) var de första som presenterade omslagsidén som en allmän ram för val av funktioner. Deras eget arbete har betonat dess kombination med beslut träd metoder, men de uppmuntrar också dess användning med andra induktionsalgoritmer. Den generiska omslagsteknik måste fortfarande använda någon åtgärd för att välja bland alternativa funktioner. Ett naturligt system innebär att köra induktionsalgoritmen över hela träningsdata med hjälp av en viss uppsättning funktioner, sedan mäta noggrannheten i den lärda strukturen på träningsdata. Men John m.fl. På ett övertygande sätt hävda att en korsvalideringsmetod, som de använder vid genomförandet, ger ett bättre mått på förväntad noggrannhet i nya testfall. John och Al. Se också över befintliga definitioner av relevans i samband med maskininlärning och föreslå en ny definition som övervinner vissa problem med tidigare. Dessutom beskriver de funktionen urval i termer av heuristisk sökning och granska en mängd olika metoder som, även om de är utformade för lter system, också fungerar inom omslagsstrategi. Slutligen utför de systematiska experiment på en mängd olika sökmetoder inom omslagsmodellen, med varierande utgångspunkt och tillgängliga operatörer. Den största nackdelen med omslagsmetoder över Lter metoder är den tidigares beräkningskostnader, som är resultatet av att ringa induktionsalgoritmen för varje funktion som beaktas. Denna kostnad har fått vissa forskare att uppfinna geniala tekniker för att påskynda utvärderingsprocessen. I synnerhet Caruana och Freitag (1994) utarbetade ett system för caching beslut träd som avsevärt minskar antalet träd som beaktas under funktionen val, vilket i sin tur låter sin algoritm söka större utrymmen i rimlig tid. Moore och Lee (1994) beskriver ett alternativt system som istället hastigheter har val genom att minska andelen träningsfall som används under utvärderingen. Liksom John et al., Caruana och Freitag granska ett antal giriga metoder som söker utrymme för funktionsuppsättningar och rapportera om jämförande experiment som varierar startuppsättningen och operatörerna. Deras oro för e ektivitet fick dem emellertid också att undersöka handeln mellan noggrannhet och beräkningskostnader. Dessutom var deras motivation för att utforska metoder för val av funktioner strängare än att hantera irrelevanta attribut. Deras mål var att nd uppsättningar av attribut som är användbara för induktion och förutsägelse. Säkert inte alla arbete inom omslagsramverket har fokuserat på beslut träd induktion. Langley och Sage's (1994a) Oblivion algoritm kombinerar omslagsidén med den enkla närmaste grannmetoden. Deras system börjar med alla funktioner och tar iterativt bort den som leder till den största förbättringen av noggrannheten, och fortsätter tills den uppskattade noggrannheten faktiskt minskar. Aha och Bankert (1994) använder ett liknande tillvägagångssätt för att förstärka närmaste granne, men deras system börjar med en slumpmässigt utvald delmängd av funktioner och innehåller ett alternativ för strålsökning snarare än giriga beslut. Skalaks (1994) arbete på närmaste granne börjar också med en slumpmässig funktionsuppsättning, men ersätter girigt sökande med slumpmässig bergsklättring som fortsätter under ett visst antal cykler.
Viktiga aspekter av funktionen val Ref inkluderar funktion delmängd generering, sökstrategier, godhet utvärdering, etc.
Selection of Relevant Features in Machine Learning
{'venue': 'In Proceedings of the AAAI Fall symposium on relevance', 'journal': None, 'mag_field_of_study': ['Mathematics']}