Vi undersöker problemet med aktivt lärande på ett givet träd vars noder tilldelas binära etiketter på ett kontradiktoriskt sätt. Inspirerad av de senaste resultaten av Guillory och Bilmes, karakteriserar vi (upp till konstanta faktorer) den optimala placeringen av frågor så att minimera de misstag som gjorts på de icke-krävda noderna. Vår frågevalsalgoritm är extremt effektiv, och det optimala antalet misstag på de icke-krävda noderna uppnås genom en enkel och effektiv mincut klassificering. Genom en enkel ändring av frågevalsalgoritm visar vi också optimalitet (upp till konstanta faktorer) med avseende på avvägningen mellan antal frågor och antal misstag på icke-krävda noder. Genom att använda spännande träd kan våra algoritmer effektivt tillämpas på allmänna grafer, även om problemet med att hitta optimala och effektiva aktiva läralgoritmer för allmänna grafer fortfarande är öppet. I detta syfte ger vi en lägre gräns för antalet misstag som görs på godtyckliga grafer av någon aktiv inlärningsalgoritm med hjälp av ett antal frågor som är upp till en konstant bråkdel av grafens storlek.
REF studerar aktivt lärande på träd.
Active Learning on Trees and Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}