Abstrakt. Vi presenterar en allmän studie av lärande och linjär separabilitet med rationella kärnor, de sekvenskärnor som vanligen används i beräkningsbiologi och bearbetning av naturligt språk. Vi ger en karakterisering av klassen av alla språk linjärt åtskilda med rationella kärnor och bevisar flera egenskaper hos klassen av språk linjärt åtskilda med en fast rationell kärna. I synnerhet visar vi att för kärnor med ändligt intervall, dessa språk nödvändigtvis är finita Booleska kombinationer av förbilder av en givare av en enda sekvens. Vi analyserar också marginalegenskaperna hos linjär separation med rationella kärnor och visar att kärnor med ändligt intervall garanterar en positiv marginal och leder till bättre inlärningsgarantier. Att skapa en ändlig skala rationell kärna är ofta icke-trivial även för relativt enkla fall. Vi presenterar dock en ny och allmän algoritm, dubbelbandsdisambigering, som tar som ingång en godtycklig givare karteringssekvenser till sekvensfunktioner, och ger en associerad givare som definierar en ändlig intervall rationell kärna. Vi beskriver algoritmen i detalj och visar dess tillämpning på flera intressanta fall. I tidigare arbete introducerade vi ett paradigm för att lära sig språk som består av att kartlägga strängar till ett lämpligt högdimensionellt funktionsutrymme och lära sig ett separerande hyperplane i det utrymmet [13]. Vi bevisade att den rika klassen av bitvis-testbara språk [21] kan separeras linjärt med hjälp av en högdimensionell funktionskartläggning baserad på subsekvenser. Vi visade också att den positiva bestämda kärnan som är associerad med denna inbäddning, subsekvenskärnan, kan beräknas på ett effektivt sätt. Stöd vektormaskiner kan användas i kombination med denna kärna för att bestämma ett separerande hyperplane för bitvis-testbara språk. Vi bevisade vidare att språken linjärt kan särskiljas med denna kärna är exakt de bitvis-testbara språken. Subsekvenskärnan är en rationell kärna - det vill säga en kärna som kan representeras av viktade finit-state transducers [5, 12]. De flesta sekvenskärnor som framgångsrikt används i beräkningsbiologi och behandling av naturligt språk, inklusive missmatchning av kärnor [15], gappy n-gram-kärnor [16], locality-förbättrade kärnor [24], convolutionskärnor för strängar [11], trädkärnor [4], n-gramkärnor [5], och momentkärnor [6], är speciella fall av rationella kärnor. Rationella kärnor kan beräknas i kvadratisk tid med hjälp av en enda allmän algoritm [5]. Detta motiverar vår studie av lärande med rationella kärnor, i synnerhet frågan om att bestämma vilken klass av språk som linjärt kan separeras med en given rationell kärna, och därmed generalisera resultatet som avser subsekvenskärnor och bitvis-testbara språk, och även analysera deras generaliseringsegenskaper baserat på marginalen. Det är också naturligt att fråga vilka språk som är åtskilda med rationella kärnor i allmänhet.
Denna forskningslinje fortsätter i REF, där linjära separerbarhetsegenskaper hos rationella kärnor undersöks.
Learning Languages with Rational Kernels
{'venue': 'In Proceedings of The 20th Annual Conference on Learning Theory (COLT 2007', 'journal': None, 'mag_field_of_study': ['Computer Science']}