Learning with Limited Visibility

LearningwithLimitedVisibilityEliDichtermanDepartmentofMathematicsLondonSchoolofEconomicsHoughtonStreet,LondonWC2A2AE,UK.And,DepartmentofComputerScienceRoyalHollowayUniversityofLondonEgham,SurreyTW200EX,UK.E-mail:[e-mail]ysrecentstudiesoflearningproblemsinwhichthelearnerfacesrestrictionsontheamountofinformationhecanextractfromeachexampleheencounters.OurmainframeworkfortheanalysisofsuchscenariosistheRFA(RestrictedFocusofAttention)model.WhilebeinganaturalrenementofthePAClearningmodel,someofthefundamentalPAC-learningresultsandtechniquesfailintheRFAparadigm;learnabilityintheRFAmodelisnolongercharacterizedbytheVCdimension,andmanyPAClearningalgorithmsarenotapplicableintheRFAsetting.Hence,theRFAformulationreectstheneedfornewtechniquesandtoolstocopewithsomefundamentalconstraintsofrealisticlearningproblems.Wealsopresentsomeparadigmsandalgorithmsthatmayserveasarststeptowardsansweringthisneed.TwomaintypesofrestrictionscanbeconsideredinthegeneralRFAsetting:Inthemorestringentone,calledk-RFA,onlykofthenattributesofeachexamplearerevealedtothelearner,whileinthemorepermissiveone,calledk-wRFA,therestrictionismadeonthesizeofeachobservation(kbits),andnorestrictionismadeonhowtheobservationsareextractedfromtheexamples.Weshowaninformation-theoreticcharacterizationofRFAlearnabilityuponwhichwebuildageneraltoolforprovinghardnessresults.WethenapplythisandothernewtechniquesforstudyingRFAlearningtotwoparticularlyexpressivefunctionclasses,k-decision-lists(k-DL)andk-TOP,theclassofthresholdsofparityfunctionsinwhicheachparityfunctiontakesatmostkinputs.Amongotherresults,weshowahardnessresultfork-RFAlearnabilityofk-DL,kn2.Insharpcontrast,an(n1)-RFAalgorithmforlearning(n1)-DLispresented.Similarly,weprovethat1-DLislearnableifandonlyifatleasthalfoftheinputsarevisibleineachinstance.Inaddition,weshowthatthereisauniform-distributionk-RFAlearningalgorithmfortheclassofk-DL.Fork-TOPweshowweaklearnabilitybyak-RFAalgorithm(withecienttimeandsamplecomplexityforconstantk)andstronguniform-distributionk-RFAlearnabilityofk-TOPwithecientsamplecomplexityforconstantk.Finally,bycombiningsomeofourk-DLandk-TOPresults,weshowthat,unlikethePACmodel,weaklearningdoesnotimplystronglearninginthek-RFAmodel.Wealsoshowageneraltechniqueforcomposingecientk-RFAalgorithms,andapplyittodeduce,forinstance,theecientk-RFAlearnabilityofk-DNFformulas,andtheecient1-RFAlearnabilityofaxis-alignedrectanglesintheEuclideanspaceRn.Wealsoprovethek-RFAlearnabilityofricherclassesofBooleanfunctions(suchask-decisionlists)withrespecttoagivendistribution,andtheecient(n1)-RFAlearnability(forxedn),underproductdistributions,ofclassesofsubsetsofRnwhicharedenedbymildsurfaces.Forthek-wRFArestriction,weshowthatfork=O(logn),ecientk-wRFAlearningisrobustagainstclassicationnoise.Asastraightforwardapplication,weobtainanewsimplenoise-tolerantalgorithmfortheclassofk-decisionlists,byconstructinganintuitivek-wRFAalgorithmforthistask.11IntroductionLearningtheoryhasbeenmainlyconcernedwiththeproblemofgeneralizingfromasampleoffully-speciedclassiedexamples.Forthisproblemclassicalstatisticaluniformconvergencetheoremshavebeenusedtocharacterizescenariosinwhichagoodgeneralizationcanbefoundwithhighcondence[42],specicboundsonthesamplesizeneededforsuchgeneralizationhavebeenproven[14],andecientlearningalgorithmshavebeendesignedforspeciccases(cf.[41]).Ithasalsobeennoticedthatinmanyrealisticscenarios,thesamplesfromwhichthelearnerhastogeneralizearenotfullyspecied[28,30].Theimportanceofthis\focus-of-attentionproblemhasbeennoticedsincetheemergenceofthecomputationallearningtheory[1].However,thelearningmodelswhichhavebeenformulatedforstudyingthistypeofproblemsusuallyassume|sometimesimplicitly[13]|thatthereisaxedsetofrelevantvariableswhichareinvisibletothelearner.Insuchproblems,thelearnermayonlyattempttondagoodprobabilisticpredictionrulewithrespecttothevisibleattributes.However,asobservedbyBen-DavidandDichterman[6],therearemanycasesinwhichtherearenoattributeswhichareinherentlyinvisible,butratherthereareotherrestrictionsonthevisibilityoftheattributes,suchastheamountofvisibleattributesineachsingleexample.Sinceinsuchcaseseveryattributeispotentiallyvisible,thelearnermayattempttondmorethanjustaprobabilisticpredictionrule;hemaytrytoformulateafulldescriptionoftheconceptwithrespecttoalltherelevantattributes.Consider,forinstance,medicalresearchwhichaimsatformingtheexactpatternofsomedisease.Typically,thereissomeaprioriknowledgeaboutthedisease,suchasthepotentiallyrelevantattributesofthediseaseandthepossiblepatternsofthediseasewithrespecttotheseattributes.Then,inthecourseofstudyingthedisease,itisusuallypossibletosamplepeoplefromagivenpopulationandconductseveraltestsoneachoneofthem.However,duetopracticalconsiderations(e.g.,thecostofthetests),orinherentrestrictions(e.g.,thefactthatsomebloodtestsmaybedestructive,ormaynotbeusableformorethanalimitednumberoftests),theamountofdatathatisavailableforeachsinglepersonislimited.Insuchcircumstances,researchersfacethefollowingproblem:Theycanchooseaseto