Framgången med kärnmetoder har initierat utformningen av nya positiva semidefinita funktioner, särskilt för strukturerade data. Ett ledande designparadigm för detta är konvolutionskärnan, som sönderfaller strukturerade objekt i sina delar och summor över alla par av delar. Uppdragskärnor erhålls däremot från en optimal bijection mellan delar, vilket kan ge en mer giltig uppfattning om likhet. I allmänhet ger dock optimala uppdrag obegränsade funktioner, vilket komplicerar deras användning i kärnmetoder. Vi karakteriserar en klass av baskärnor som används för att jämföra delar som garanterar positiva semidefinita optimala tilldelningskärnor. Dessa baskärnor ger upphov till hierarkier från vilka de optimala tilldelningskärnorna beräknas i linjär tid genom histogramkorsning. Vi tillämpar dessa resultat genom att utveckla Weisfeiler-Lehman optimal tilldelningskärna för grafer. Det ger hög klassificering noggrannhet på allmänt använda referensdatamängder som förbättrar över den ursprungliga Weisfeiler-Lehman-kärnan.
OA REF utvecklar några baskärnor som genererar hierarkier från vilka de optimala tilldelningskärnorna beräknas.
On Valid Optimal Assignment Kernels and Applications to Graph Classification
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}