Abstrakt. I detta dokument överväger vi problemet med att spåra en delmängd av en domän (kallas målet) som förändras gradvis över tiden. En enda (okänd) sannolikhetsfördelning över domänen används för att generera slumpmässiga exempel för inlärningsalgoritmen och mäta den hastighet med vilken målet ändras. Klart, ju snabbare målet rör sig, desto svårare är det för algoritmen att upprätthålla en bra approximation av målet. Därför utvärderar vi algoritmer baserat på hur mycket rörelse av målet kan tolereras mellan exempel samtidigt förutsäga med noggrannhet (.. Dessutom påverkar komplexiteten hos klassen H av möjliga mål, mätt med d, dess VC-dimension, också svårigheten att spåra målkonceptet. Vi visar att om problemet med att minimera antalet meningsskiljaktigheter med ett prov från bland begrepp i en klass H kan approximeras till inom en faktor k, då finns det en enkel spårningsalgoritm för H som kan uppnå en sannolikhet f att göra ett misstag om målrörelsehastigheten är som mest en konstant gånger e 2 /(k(d + k) In j), där d är Vapnik-Chervonenkis dimension av H. Dessutom visar vi att om H är korrekt PAC-lärbar, då finns det en effektiv (randomized) algoritm som med hög sannolikhet ungefär minimerar meningsskiljaktigheter inom en faktor av 7d + 1, vilket ger en effektiv spårningsalgoritm för H som tolererar drifthastigheter upp till en konstant gånger e 2 /(d 2 I). Dessutom bevisar vi kompletterande resultat för klasserna av halvrymder och axeljusterade hyperrektanglar som visar att den maximala hastigheten av drift som någon algoritm (även med obegränsad beräkningskraft) kan tolerera är en konstant gånger f 2 /d.
I REF studerar författarna problemet med att spåra en delmängd av en domän (kallas målet) som ändras gradvis över tiden, under antagandet att avdriften sker långsamt.
Tracking Drifting Concepts By Minimizing Disagreements
{'venue': 'Machine Learning', 'journal': 'Machine Learning', 'mag_field_of_study': ['Mathematics']}