Kärnans stödvektormaskin (SVM) är en av de mest använda klassificeringsmetoderna, men den mängd beräkning som krävs blir flaskhalsen när man möter miljontals prover. I det här dokumentet föreslår och analyserar vi en ny splitter-och-konquer-lösare för kärn-SVM (DC-SVM). I divisionssteget partitionerar vi kärnans SVM-problem till mindre subproblem genom att gruppera data, så att varje subproblem kan lösas självständigt och effektivt. Vi visar teoretiskt att de stödvektorer som identifierats av subproblemlösningen sannolikt kommer att vara stödvektorer för hela kärnan SVM-problemet, förutsatt att problemet partitioneras på lämpligt sätt genom klustring av kärnan. I det erövrade steget används de lokala lösningarna från underproblemen för att initiera en global koordinatnedstigningslösning, som snabbt konvergerar enligt vår analys. Genom att utöka denna idé utvecklar vi en flernivås SVM-algoritm med adaptiv kluster- och tidig förutsägelsestrategi, som överträffar toppmoderna metoder när det gäller träningshastighet, testnoggrannhet och minnesanvändning. På covtypdatauppsättningen med en halv miljon prov är DC-SVM 7 gånger snabbare än LIBSVM när det gäller att erhålla den exakta SVM-lösningen (till inom 10 −6 relativa fel) som uppnår 96,15 % exakthet i förutsägelsen. Med vår föreslagna tidiga prognosstrategi uppnår DC-SVM dessutom ungefär 96 % noggrannhet på bara 12 minuter, vilket är mer än 100 gånger snabbare än LIBSVM.
Multilevel Divide-and-Conquer SVM (DC-SVM) utvecklades med hjälp av adaptiv klusterbildning och tidig förutsägelse strategi REF.
A Divide-and-Conquer Solver for Kernel Support Vector Machines
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}