I denna artikel behandlas metoder som omvärderar resultatet av en befintlig probabilistisk tolk. Bastolken producerar en uppsättning kandidattolkar för varje inmatningsmening, med tillhörande sannolikheter som definierar en första rankning av dessa parser. En andra modell försöker sedan förbättra denna ursprungliga ranking, med hjälp av ytterligare funktioner i trädet som bevis. Styrkan i vårt tillvägagångssätt är att det gör det möjligt att representera ett träd som en godtycklig uppsättning funktioner, utan oro för hur dessa funktioner interagerar eller överlappar och utan att behöva definiera en härledning eller en generativ modell som tar hänsyn till dessa egenskaper. Vi introducerar en ny metod för omplaceringsuppgiften, baserad på det ökade tillvägagångssättet för att rangordna problem som beskrivs i Freund et al. (1998)................................................................................................. Vi använder den förstärkande metoden för att tolka Wall Street Journals trädbank. Metoden kombinerade log-likelihood enligt en baslinjemodell (den för Collins [1999]) med bevis från ytterligare 500.000 funktioner över parseträd som inte ingick i den ursprungliga modellen. Den nya modellen uppnådde 89,75 % F-mått, en relativ minskning av F-mätfelet med 13 % jämfört med referensmodellens poäng på 88,2 %. Artikeln introducerar också en ny algoritm för att öka tillvägagångssätt som drar nytta av den gleshet av funktionen utrymme i tolkningsdata. Experiment visar på betydande effektivitetsvinster för den nya algoritmen jämfört med det uppenbara genomförandet av den ökade strategin. Vi hävdar att metoden är ett tilltalande alternativ när det gäller både enkelhet och effektivitet för att arbeta med funktionsvalsmetoder inom log-lineära (maximal-entropi) modeller. Även om experimenten i denna artikel är på naturligt språk tolkning (NLP), bör metoden vara tillämplig på många andra NLP-problem som naturligt inramas som rankning uppgifter, till exempel taligenkänning, maskinöversättning, eller naturligt språk generation. som anses vara användbara för att diskriminera bland kandidatträd för en mening. I praktiken kan det dock vara pinsamt att lägga till nya funktioner i en generativ eller historiebaserad modell: härledningen i modellen måste ändras för att ta hänsyn till de nya funktionerna, och detta kan vara en invecklad uppgift. I denna artikel behandlas metoder som omvärderar resultatet av en befintlig probabilistisk tolk. Bastolken producerar en uppsättning kandidattolkar för varje inmatningsmening, med tillhörande sannolikheter som definierar en första rankning av dessa parser. En andra modell försöker sedan förbättra denna ursprungliga ranking, med hjälp av ytterligare funktioner i trädet som bevis. Styrkan i vårt tillvägagångssätt är att det gör det möjligt att representera ett träd som en godtycklig uppsättning funktioner, utan oro för hur dessa funktioner interagerar eller överlappar och utan att behöva definiera en härledning som tar hänsyn till dessa funktioner. Vi introducerar en ny metod för omplaceringsuppgiften, baserad på det ökade tillvägagångssättet för att rangordna problem som beskrivs i Freund et al. (1998)................................................................................................. Algoritmen kan ses som en funktionsvalsmetod, som optimerar en viss förlustfunktion (den exponentiella förlustfunktionen) som har studerats i den ökande litteraturen. Vi tillämpade den förstärkande metoden för att tolka Wall Street Journal (WSJ) trädbank (Marcus, Santorini, och Marcinkiewicz 1993). Metoden kombinerar log-likelihood enligt en baslinjemodell (den för Collins [1999]) med bevis från ytterligare 500.000 funktioner över parseträd som inte ingick i den ursprungliga modellen. Baslinjemodellen uppnådde 88,2 % F-åtgärd på denna uppgift. Den nya modellen uppnår 89,75 % F-åtgärd, vilket är en relativ minskning på 13 % av F-åtgärdsfelet. Även om experimenten i denna artikel handlar om tolkning av naturligt språk, bör metoden vara tillämplig på många andra problem med naturligt språk (NLP) som är naturligt inramade som rankningsuppgifter, till exempel taligenkänning, maskinöversättning eller naturlig språkgenerering. Se Collins (2002a) för en tillämpning av en ökad strategi för namngivna enheter erkännande, och Walker, Rambow, och Rogati (2001) för tillämpningen av öka tekniker för rankning i samband med naturligt språk generation. Artikeln introducerar också en ny, mer effektiv algoritm för att öka tillvägagångssättet som drar nytta av den glesa karaktären av funktionsutrymmet i tolkningsdata. Andra NLP-uppgifter kommer sannolikt att ha liknande egenskaper när det gäller sparsamhet. Experiment visar en effektivitetsvinst av en faktor på 2.600 för den nya algoritmen över det uppenbara genomförandet av den förstärkande metoden. Effektivitetsfrågor är viktiga, eftersom tolkningsuppgiften är ett ganska stort problem, som omfattar omkring en miljon parsträd och över 500.000 egenskaper. Den förbättrade algoritmen kan utföra 100 000 omgångar av funktionsval på vår uppgift på några timmar med aktuella bearbetningshastigheter. De 100 000 omgångarna av funktionsval kräver beräkning motsvarande cirka 40 pass över hela träningssetet (i motsats till 100 000 pass för "naive" genomförande). Problemen med historiska modeller och önskan att kunna specificera funktioner som godtyckliga predikat av hela trädet har noterats tidigare. I synnerhet tidigare arbete (Riezler et al. 2002) har undersökt användningen av Markovs slumpmässiga fält (MRF) eller loglinjära modeller som probabilistiska modeller med globala funktioner för tolkning och andra NLP-uppgifter. (Logglinjära modeller kallas ofta för maximalentropimodeller i NLP-litteraturen.) Liknande metoder har också föreslagits för maskinöversättning (och och Ney 2002) och språkförståelse i dialogsystem Ward 1997, 1998). Tidigare arbeten (Friedman, Hastie, och Tibshirani 1998) har dock ritat kopplingar mellan log-linjära modeller och 26 beräkningslingvistik Volym 31, Nummer 1 Observera att log-linjära modeller som använder regulariseringsmetoder istället för funktionsval-se t.ex. Johnson et al. (1999) och Lafferty, McCallum och Pereira (2001) är sannolikt jämförbara i fråga om effektivitet med vår metod för urval av funktioner. Se avsnitt 6.3 för mer diskussion.
Men i arbetet av Collins REF, 42% av rätt parse träd var inte i kandidatpoolen av ~30-bästa parser.
Discriminative Reranking for Natural Language Parsing
{'venue': 'Computational Linguistics', 'journal': 'Computational Linguistics', 'mag_field_of_study': ['Computer Science']}