Vi studerar online öka, uppgiften att omvandla alla svaga onlineinlärare till en stark onlineinlärare. Baserat på en ny och naturlig definition av svag online-inlärbarhet utvecklar vi två online-höjande algoritmer. Den första algoritmen är en onlineversion av boost-by-majoritet. Genom att bevisa en matchande lägre gräns, visar vi att denna algoritm är i huvudsak optimal när det gäller antalet svaga elever och den prov komplexitet som krävs för att uppnå en specificerad noggrannhet. Denna optimala algoritm är dock inte adaptiv. Med hjälp av verktyg från online förlustminimering, härleder vi en adaptiv online öka algoritm som också är parameter-fri, men inte optimal. Båda algoritmerna arbetar med basinlärare som kan hantera exempel vikter direkt, samt genom avstötning provtagning exempel med sannolikhet definieras av booster. Resultaten kompletteras med en experimentell studie.
På senare tid utvidgar REF detta tidigare arbete till att föreslå en optimal version av att öka antalet svaga elever för klassificering.
Optimal and Adaptive Algorithms for Online Boosting
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}