Vi ger en frågealgoritm för agnostiskt lärande beslut träd med avseende på den enhetliga fördelningen på indata. Eftersom svart-box tillgång till en godtycklig binär funktion f på n-dimensionell hyperkub, finner vår algoritm en funktion som överensstämmer med f på nästan (inom ett bråk) så många ingångar som den bästa storlek-t beslut träd, i tid poly (n, t, 1/ ). Detta är den första polynom-tid algoritm för att lära beslut träd i en hård bullermodell. Vi ger också en riktig agnostisk inlärningsalgoritm för juntor, en underklass av beslut träd, igen med hjälp av medlemskap frågor. Konceptuellt är det aktuella dokumentet paralleller med det senaste arbetet mot agnostiskt lärande av halvrymder [13]; algoritmiskt är det mer utmanande. Kärnan i vår inlärningsalgoritm är en procedur för att implicit lösa ett konvext optimeringsproblem över L1-kulan i 2 n dimensioner med hjälp av en ungefärlig gradient projiceringsmetod.
Vår algoritm för agnostiskt lärande juntor i slumpmässiga promenadmodellen har vissa likheter med Gopalan et al.'s senaste algoritm för korrekt agnostiskt lärande juntor i medlemskap frågemodell REF.
Agnostically learning decision trees
{'venue': "STOC '08", 'journal': None, 'mag_field_of_study': ['Computer Science']}