Metalearning---Applications-to-Data-Mining

CognitiveTechnologiesManagingEditors:D.M.GabbayJ.SiekmannEditorialBoard:A.BundyJ.G.CarbonellM.PinkalH.UszkoreitM.VelosoW.WahlsterM.J.WooldridgeAdvisoryBoard:LuigiaCarlucciAielloFranzBaaderWolfgangBibelLeonardBolcCraigBoutilierRonBrachmanBruceG.BuchananAnthonyCohnArturd’AvilaGarcezLuisFariñasdelCerroKoichiFurukawaGeorgGottlobPatrickJ.HayesJamesA.HendlerAnthonyJamesonNickJenningsAravindK.JoshiHansKampMartinKayHiroakiKitanoRobertKowalskiSaritKrausMaurizioLenzeriniHectorLevesqueJohnLloydAlanMackworthMarkMayburyTomMitchellJohannaD.MooreStephenH.MuggletonBernhardNebelSharonOviattLuisPereiraLuRuqianStuartRussellErikSandewallLucSteelsOlivieroStockPeterStoneGerhardStrubeKatiaSycaraMilindTambeHidehikoTanakaSebastianThrunJunichiTsujiiKurtVanLehnAndreiVoronkovTobyWalshBonnieWebber·WithFiguresand11Tables53ABCPavelBrazdilChristopheGiraud-CarrierCarlosSoaresRicardoVilalta·MetalearningApplicationstoDataMiningISBN:978-3-540-73262-4e-ISBN:978-3-540-73263-1CognitiveTechnologiesISSN:1611-2482LibraryofCongressControlNumber:2008937821ACMComputingClassification(1998):I.2.6,H.2.8cSpringer-VerlagBerlinHeidelberg2009Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation,broadcasting,reproductiononmicrofilmorinanyotherway,andstorageindatabanks.DuplicationofthispublicationorpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.ViolationsareliabletoprosecutionundertheGermanCopyrightLaw.Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse.Coverdesign:KünkelLopka,HeidelbergPrintedonacid-freepaper987654321springer.comAuthors:ManagingEditors:AugustusDeMorganProfessorofLogicDepartmentofComputerScienceKingsCollegeLondon’Strand,LondonWC2R2LS,UKProf.Dr.JörgSiekmannForschungsbereichDeduktions-undMultiagentensysteme,DFKIStuhlsatzenweg3,Geb.4366123Saarbrücken,GermanyProf.DovM.GabbayDOI:10.1007/978-3-540-73263-1Prof.PavelBrazdilLIAADUniversidadedoPortoFac.EconomiaRuadeCeuta118-6◦4050-190Porto,[e-mail]-CarrierBrighamYoungUniversityDepartmentofComputerScienceProvo,UT84602,[e-mail]118-6◦4050-190Porto,[e-mail]ofHoustonDepartmentofComputerScience501PGHBuildingHouston,TX77204-3010,[e-mail]feandlifelongcompanion,F´atima.Christophetomywifeandchildren.CarlostoManela,QuicaandManel.Ricardotomyparents.PrefaceThecontinuousgrowthofsuccessfulapplicationsinmachinelearninganddatamininghasledtoanapparentviewofrealprogresstowardstheunderstand-ingofthenatureandmechanismsoflearningmachines.Fromtheautomatedclassificationofmillionsofluminousobjectsstoredinastronomicalimages,tothecomplexanalysisoflongsequencesofgenesinbiomedicaldatasets,machinelearninghaspositioneditselfasanindispensabletoolfordataanal-ysis,patternrecognition,andscientificdiscovery.Thisapparentprogressinthesearchforaccuratepredictivemodelsreliesonthedesignoflearningalgo-rithmsexhibitingnovelfunctionalities.Thehistoryofmachinelearningshowsaresearchcommunitydevotedtothestudyandimprovementofahighlydi-versesetoflearningalgorithmssuchasnearestneighbors,Bayesianclassifiers,decisiontrees,neuralnetworks,andsupportvectormachines(tonamejustafew).Whilethedesignofnewlearningalgorithmsiscertainlyimportantinadvancingourabilitytofindingaccuratedatamodels,soistheunderstandingoftherelationbetweendatasetcharacteristicsandtheparticularmechanismsembeddedinthelearningalgorithm.Ratherthantestingmultiplealgorithmstoassesswhichonewouldperformsatisfactorilyonacertaindataset,theenduserneedsguidelinespointingtothebestlearningstrategyfortheparticularproblemathand.Researchersandpractitionersinmachinelearninghaveaclearneedtoanswerthefollowingquestion:whatworkswellwhere?Thereisastrongneedtocharacterizebothdatadistributionsandlearningmecha-nismstoconstructatheoryoflearningbehavior.Moreover,weadvocatethedevelopmentofanewgenerationoflearningalgorithmsthatarecapableofprofoundadaptationsintheirbehaviortotheinputdata.Thismayincludechangestothemodellanguageitself.Despitedifferentinterpretationsofthetermmetalearning,inthisbookwepursuethegoaloffindingprincipledmethodsthatcanmakelearningalgorithmsadaptivetothecharacteristicsofthedata.Thiscanbeachievedinmanywaysaslongasthereissomeformoffeedbackrelatinglearningperformancewithdatadistributions.Thusonecanthinkoftheproblemofalgorithmselection(orranking),oralgorithmcombination,asframeworksVIIIPrefacethatexploitpastperformancetoguidetheselectionofafinalmodel.Theultimateendistodesignlearningalgorithmsthatadapttotheproblemathand,ratherthaninvokingthesamefixedmechanismsindependentofthenatureofthedataunderanalysis.Weexplaininthisbookthataunifying