Beslutsträd och randomiserade skogar används i stor utsträckning i datorseende och maskininlärning. Standardalgoritmer för beslut trädinduktion optimerar delningsfunktionerna en nod åt gången enligt vissa uppdelningskriterier. Detta giriga tillvägagångssätt leder ofta till suboptimala träd. I detta dokument presenterar vi en algoritm för optimering av delningsfunktionerna på alla nivåer av trädet tillsammans med bladparametrarna, baserat på ett globalt mål. Vi visar att problemet med att hitta optimal linjär kombination (oblique) uppdelningar för beslut träd är relaterad till strukturerad förutsägelse med latenta variabler, och vi formulerar en konvex-konkav övre gräns på trädets empiriska förlust. Tidpunkten för beräkning av lutningen för det föreslagna surrogatmålet med avseende på varje övningsexempel är kvadratisk i träddjupet, och det är därför möjligt att träna djupa träd. Användningen av stokastisk lutningsnedstigning för optimering möjliggör effektiv träning med stora dataset. Experiment på flera klassificeringsriktmärken visar att de resulterande icke-grå beslutsträden överträffar giriga beslutsträdets baslinjer.
REF föreslår en algoritm för optimering av ett helt träd med en given struktur.
Efficient non-greedy optimization of decision trees
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}