En motivation för fastighetstestning av booleska funktioner är tanken att testning kan ge ett snabbt förbehandlingssteg innan du lär dig. I de flesta tillämpningar för maskininlärning är det dock inte möjligt att begära etiketter på godtyckliga exempel som konstruerats av en algoritm. Istället är det dominerande frågeparadigmet i tillämpad maskininlärning, som kallas aktivt lärande, en där algoritmen kan fråga efter etiketter, men bara på punkter i ett givet (polynom-stort) omärkt prov, som hämtats från någon underliggande distribution D. I detta arbete tar vi med denna välstuderade modell till testområdet. Vi utvecklar både generella resultat för denna aktiva testmodell och effektiva testalgoritmer för flera viktiga egenskaper för lärande, vilket visar att testning fortfarande kan ge betydande fördelar i denna begränsade miljö. Vi visar t.ex. att testföreningar med d-intervall kan göras med O(1)-etikettförfrågningar i vår miljö, medan det är känt att det krävs exempel med beteckningen "D" för lärande (och "O1 d" för passiv testning [22] där algoritmen måste betala för varje exempel som dras från D). I själva verket ger våra resultat för att testa fack av intervall också förbättringar på tidigare arbete i både den klassiska frågemodellen (där någon punkt i domänen kan ifrågasättas) och den passiva testmodellen också. För problemet med att testa linjära avskiljare i R n över Gaussian distribution, visar vi att både aktiv och passiv testning kan göras med O ( ε n) frågor, betydligt mindre än den ∂(n) som behövs för lärande, med nära-matchande lägre gränser. Vi presenterar också en allmän kombination resultat i denna modell för att bygga testbara egenskaper av andra, som vi sedan använder för att tillhandahålla testare för ett antal antaganden som används i semi-övervakad lärande. Förutom ovanstående resultat utvecklar vi också en allmän uppfattning om testdimensionen för en viss egenskap med avseende på en given fördelning, som vi visar karakteriserar (upp till konstanta faktorer) det inneboende antalet etikettförfrågningar som behövs för att testa denna egenskap. Vi utvecklar sådana föreställningar för både aktiva och passiva testmodeller. Vi använder sedan dessa dimensioner för att bevisa ett antal lägre gränser, inklusive för linjära avskiljare och klassen av diktatoriska funktioner.
I slutändan har den aktiva testaren nedan för allmänna F k-funktioner betydande skillnader jämfört med den ursprungliga testaren för unioner av intervaller från REF.
Active Property Testing
{'venue': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'journal': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}