Vi ger nya resultat gällande etiketteffektiv, polynomisk tid, passiv och aktiv inlärning av linjära avskiljare. Vi visar att aktivt lärande ger en exponentiell förbättring jämfört med PAC (passiv) inlärning av homogena linjära separatorer under nästan log-konkav fördelningar. Baserat på detta ger vi en beräkningseffektiv PAC-algoritm med optimal (upp till en konstant faktor) prov komplexitet för sådana problem. Detta löser en öppen fråga (Long, 1995 (Long,, 2003 Bshouty et al., 2009 ) om urvalet komplexiteten av effektiva PAC algoritmer under den enhetliga fördelningen i enheten bollen. Dessutom ger det den första gränsen för en polynom-tid PAC algoritm som är tight för en intressant oändlig klass av hypotes funktioner under en allmän och naturlig klass av data-distributioner, vilket ger betydande framsteg mot en långvarig öppen fråga om Blumer et al., 1989). Vi tillhandahåller också nya gränser för aktivt och passivt lärande om uppgifterna kanske inte är linjärt åtskilda, både i det agnostiska fallet och under Tsybakovs lågbullertillstånd. För att härleda våra resultat ger vi nya strukturella resultat för (nästan) log-concave distributioner, som kan vara av oberoende intresse också.
Aktivt lärande med avseende på isotropisk log-konkav fördelning i frånvaro av buller studerades i REF.
Active and passive learning of linear separators under log-concave distributions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}