Vi ger nya teoretiska insikter om strukturerad förutsägelse i samband med effektiv konvex surrogatförlustminimering med konsekventa garantier. För alla uppgifter förlust, vi konstruera en konvex surrogat som kan optimeras via stokastisk lutning nedstigning och vi visar snäva gränser på den så kallade "kalibrering funktion" som relaterar överskottet surrogat risk till den faktiska risken. I motsats till tidigare relaterat arbete övervakar vi noggrant effekten av det exponentiella antalet klasser i inlärningsgarantierna samt på optimeringskomplexet. Som en intressant konsekvens formaliserar vi intuitionen att vissa uppgiftsförluster gör lärandet svårare än andra, och att den klassiska 0-1 förlusten är illa lämpad för strukturerade förutsägelser. Strukturerad förutsägelse är ett subfält av maskininlärning som syftar till att göra flera inbördes relaterade förutsägelser samtidigt. De önskade utdata (etiketter) är vanligtvis organiserade i vissa strukturerade objekt såsom en sekvens, en graf, en bild, etc. Uppgifter av denna typ visas i många praktiska områden såsom datorseende [31], naturligt språk bearbetning [38] och bioinformatik [17]. Den strukturerade förutsägelse setup har minst två typiska egenskaper som skiljer den från den klassiska binära klassificeringsproblem omfattande studerat i inlärningsteori: 1. Exponentiellt antal klasser: Detta medför både ytterligare beräknings- och statistiska utmaningar. Med exponentiellt menar vi exponentiellt stora i storleken på den naturliga dimensionen av produktionen, t.ex. antalet av alla möjliga sekvenser är exponentiellt w.r.t. sekvenslängden. 2. Utgångspunkten är följande: Kostnadskänsligt lärande: i typiska tillämpningar är inte alla förutsägelsefel lika kostsamma. Förutsägelsefelet mäts vanligen med en högstrukturerad uppgiftsspecifik förlustfunktion, t.ex. hammingavstånd mellan sekvenser av flermärkta variabler eller genomsnittlig precision för rankning. Trots många algoritmiska framsteg för att ta itu med strukturerade förutsägelser problem [3, 32], Det har varit relativt få papper ägnas åt sin teoretiska förståelse. Bland de undantag som nyligen gjorts kan nämnas Cortes m.fl. [12] och London m.fl. [25] (se hänvisningarna där) som föreslog databeroende generaliseringsfelgränser i termer av populära empiriska konvexa surrogatförluster såsom den strukturerade gångjärnsförlusten [40, 41, 43]. En fråga som inte tas upp i dessa verk är om deras algoritmer är konsekventa: leder minimering av deras konvexa gränser med oändliga data till minimering av aktivitetsförlusten också? Alternativt är de strukturerade probit- och rampförlusterna konsekventa [28, 27], men icke-konvexa och därmed är det svårt att få beräkningsgarantier för dem. I detta dokument syftar vi till att få egenskapen konsekvens för surrogatförluster som effektivt kan minimeras med garantier, och därmed anser vi konvexa surrogatförluster. Konsistensen hos konvexa surrogat är välförståelig när det gäller binär klassificering [46, 4, 39] och det finns betydande framsteg när det gäller förlust av flerklass 0-1 [45, 42] och allmän förlust
Osokin m.fl. REF överväga strukturerad förutsägelse med konvexa surrogatförluster för nedbrytning av klassificeringsmått för flera klasser (dvs. Mätvärden som kan uttryckas som ett genomsnitt över proverna).
On Structured Prediction Theory with Calibrated Convex Surrogate Losses
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}