Nyligen gjorda framsteg i stormarginalklassificering av data som är bosatta i allmänna metriska utrymmen (snarare än Hilberts utrymmen) möjliggör klassificering under olika naturliga mått, såsom strängredigering och jordomfångsavstånd. En allmän ram som utvecklats för detta ändamål lämnade öppna frågorna om beräkningseffektivitet och att tillhandahålla direkta gränser för generalisering fel. Vi utformar en ny algoritm för klassificering i allmänna metriska utrymmen, vars körtid och noggrannhet beror på dubbla dimensioner av datapunkter, och kan därmed uppnå överlägsen klassificering prestanda i många vanliga scenarier. Den algoritmiska kärnan i vår strategi är en ungefärlig (snarare än exakt) lösning på de klassiska problemen med Lipschitz förlängning och närmaste grannsökning. Algoritmens generaliseringsprestanda garanteras via Lipschitz klassificeringsdimension, och vi presenterar experimentella bevis på dess överlägsenhet mot vissa vanliga kärnmetoder. Som en biprodukt erbjuder vi ett nytt perspektiv på närmaste grannklassare, som ger betydligt skarpare riskaymptotik än den klassiska analysen.
Gottlieb m.fl. REF studerar klassificeringsproblemet för punkter i ett metriska utrymme, och erhöll en generalisering bunden med avseende på dubbleringsdimensionen.
Efficient Classification for Metric Data
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}