Redigerer Dependensparsing

'''Dependensparsing''' er [[parsing]] av naturlige språk i henhold til en [[dependensgrammatikk]] (DG). Slik parsing resulterer i et ''dependenstre'', en [[Grafteori|graf]] som angir hvordan ord i en setning er over- og underordnet hverandre og hva slags relasjoner de har overfor hverandre.

== Dependensgrammatikk ==
Moderne dependensgrammatikk (DG) tilskrives gjerne Lucien Tesnière <ref>Nivre, Joakim: [http://stp.lingfil.uu.se/~nivre/docs/05133.pdf «Dependency Grammar and Dependency Parsing»] {{Wayback|url=http://stp.lingfil.uu.se/~nivre/docs/05133.pdf |date=20171013154536 }}.</ref> og hans posthume verk ''Les eléments de syntaxe structurale'' (1959). DG forfekter at språklige strukturer er [[binær]]e, antisymmetriske relasjoner mellom [[ord]].

=== Eksempel på dependenstre ===
Dependenstreet for setningen "Jagland skal lede utenrikskomitéen" med annoteringer fra Universal Dependencies ser slik ut:
[[Fil:Dependenstre.png|rammeløs|414x414px]]

== Data- og regelbaserte metoder ==
Det finnes flere typer dependensparsere som benytter seg av forskjellige metoder for tekstanalyse, bl.a. regelbaserte parsere og datadrevne parsere. Regelbaserte parsere bruker en formell grammatikk for å analysere tekst. Denne formelle grammatikken representerer et språk, og er satt sammen av regler for hvordan språket er bygget opp. Reglene som parseren bruker er menneskeskapte og kan ta lang tid å lage. Ord som kan være flertydige eller høre til flere ordklasser er et problem for regelbaserte parsere, fordi det ofte finnes mange regler som kan representere den samme setningen. For at denne typen parsere skal komme frem til den korrekte analysen kan den bruke statistikk for å avgjøre hvilken analyse som er mest sannsynlig<ref name=":0">{{Kilde bok|url=https://web.stanford.edu/~jurafsky/slp3/14.pdf|tittel=Speech and Language Processing|etternavn=Jurafsky|fornavn=Daniel|etternavn2=Martin|fornavn2=James|utgiver=|år=2017|isbn=|utgivelsessted=|side=1|sider=|kapittel=Ch 14: Dependency Parsing|sitat=|besøksdato=2017-10-27|arkivurl=https://web.archive.org/web/20171011052058/http://web.stanford.edu/~jurafsky/slp3/14.pdf|arkivdato=2017-10-11|url-status=død}}</ref><ref>{{Kilde bok|url=https://web.stanford.edu/~jurafsky/slp3/11.pdf|tittel=Speech and Language Processing|etternavn=Jurafsky|fornavn=Daniel|etternavn2=Martin|fornavn2=James|utgiver=|år=2017|isbn=|utgivelsessted=|side=22|sider=|kapittel=Ch 11: Formal Grammars of English|sitat=}}</ref>.

Den andre typen dependensparsere er datadrevne parsere. I motsetning til regelbaserte parsere har datadrevne parsere ingen predefinerte regler. De fleste datadrevne parsere baserer seg på ikke-deterministiske teknikker for parsing ved bruk av sannsynlighetsmodeller og dynamiske algoritmer<ref>{{Kilde artikkel|tittel=MaltParser: A language-independent system for data-driven dependency parsing|publikasjon=Natural Language Engineering|url=https://stp.lingfil.uu.se/~nivre/docs/nle07.pdf|dato=12. januar 2007|forfattere=Nivre et al|via=|bind=13|hefte=2|sider=96|sitat=|besøksdato=2017-10-27|arkiv-dato=2017-08-10|arkiv-url=https://web.archive.org/web/20170810170943/http://stp.lingfil.uu.se/~nivre/docs/nle07.pdf|url-status=yes}}</ref>. Ved hjelp av en annotert tekst (tagged) lager parseren en statistisk modell som senere brukes til å analysere tekst som ikke har blitt annotert. Siden denne typen parsere baserer seg på statistikk og data, vil den kunne generalisere og analysere data som den ikke har sett før, i motsetning til regelbasert parsing som ikke kan analysere en setning dersom det ikke finnes en regel som kan representere setningen. En annen fordel med datadreven dependensparsing er at denne  typen parsere kan håndtere språk som ikke har en bestemt rekkefølge på ord. En regelbasert parser vil måtte ha en regel for hver mulige rekkefølge av ord, mens datadrevne parsere håndterer dette ved å ha en dependenslink som representerer en gitt relasjon<ref name=":0" />.

=== Ulike parsere ===
Vi har tre ulike avhengighetsbaserte parsere: Syntaktiske parsere, statistiskeparsere og datadrevne parsere.

Syntaktiske parsere søker gjennom alle mulige parsertre for en setning for å velger den mest sannsynlige.

Statistiske parsere har predefinerte regler i samsvar med sannsynlighet for å finne meningen med setningen. Den tilegner hver regel med en sannsynlighet som vil gi den relative frekvensen av den regelen.

Datadrevene parsere har i motsetning til statistiske parsere ingen predefinerte regler, men tar inn et annotert tekstkorpus. Når det har blitt gjort vil den kunne annotere ikke-annoterte tekster ved hjelp av sannsynlighet.

=== Verktøy ===

Det finnes en rekke tilgjengelige modeller for dependensparsing på internett. Blant disse har vi:
* [https://nlp.stanford.edu/software/nndep.shtml Stanford Neural Network Dependency Parser]
* [http://www.maltparser.org/ MaltParser] 
* [http://ufal.mff.cuni.cz/udpipe UDPipe]
* [http://www.ims.uni-stuttgart.de/forschung/ressourcen/werkzeuge/imstrans.en.html IMStrans]
* [http://turkunlp.github.io/Finnish-dep-parser/ TurkuNLP]
* [http://www.seas.upenn.edu/~strctlrn/MSTParser/MSTParser.html MSTParser] {{Wayback|url=http://www.seas.upenn.edu/~strctlrn/MSTParser/MSTParser.html |date=20171123103315 }}
Python-biblioteket [https://spacy.io/ spaCy] har også støtte for [https://spacy.io/usage/linguistic-features#dependency-parse dependensparsing] samt visualisering av resulterende trær.

Disse verktøyene tar i bruk data- og regelbaserte metoder, og de datadrevne verktøyene vil vanligvis bestå av tre ting: en formell modell som beskriver hva vi godtar eller gir betydning i dependensanalysen, en mengde annotert tekst og en metode for å indusere den faktiske analysen. Prosessen vil da være at vi trener en modell på de annoterte tekstene, gjerne en trebank med dependensannotasjoner og for eksempel PoS-tagger som også ofte er brukt sammen; når vi har en modell som er trent er vi klare for induksjon og den faktiske analysen.

=== Evaluering ===
Det er også vanlig å ta i bruk vanlige mål for resultater til analysen, og for å kunne gjøre dette kreves det et gyllent eksempel med annotert data: altså data som er helt riktig annotert. Hvis vi da bruker verktøyet på denne gylne dataen, vil vi kunne regne ut mål som f.eks. "UAS" ("Unlabeled Attachment Score") som representerer gjennomsnittlig prosent av hvor ofte modellen gjettet riktig hode på eller "LAS" ("Labeled Attachment Score") som er gjennomsnittlig riktig gjettet for både hode og dependens etikett. Dette er viktig for å kunne teste verktøy opp i mot andre verktøy, og hvis de er trent og evaluert på samme data kan vi da få et mål på hvilket verktøy som er best under de forhold.

== Trebanker ==
I lingvistikk er en [[trebank]] et analysert tekstkorpus som annoterer syntaktisk eller semantisk setningsstruktur. Konstruksjonen av analyserte tekstkorpora i begynnelsen av 1990-tallet revolusjonerte datalingvistikken, som dro fordel av empiriske data på stor skala.<ref>Alexander Clark, Chris Fox and Shalom Lappin (2010). The handbook of computational linguistics and natural language processing. Wiley.</ref> Utnyttelsen av trebankdata har vært viktig siden den første store trebanken, The Penn Treebank, ble publisert. Selv om trebanker har sitt utgangspunkt i datalingvistikk, har verdien av trebanker blitt mer verdsatt i den helhetlige lingvistikkforskningen. For eksempel har annoterte trebankdata vært avgjørende for syntaktisk forskning for å teste språklige teorier om setningsstruktur mot store mengder naturlig forekommende eksempler.

En avhengighetstrebank er en samling av setninger fra naturlige språk hvor avhengighetene til ordene er merket.

=== Universal Dependencies ===
Et problem ved utvikling av tverrspråklig språkteknologi er at tilgjengelige ressurser for ulike språk kan ha betydelige forskjeller som gjør det vanskelig å sammenligne modellene. Det er bakgrunnen for prosjektet Universal Dependencies (UD), som koordineres av Joakim Nivre ved [[Uppsala universitet]]. UD lager retningslinjer for syntaktisk annotering slik at trebanker for ulike språk er konsistente og danner bedre sammenligningsgrunnlag mot hverandre.<ref>{{Kilde www|url=https://nlp.stanford.edu/pubs/nivre2016ud.pdf|tittel=Universal Dependencies v1: A Multilingual Treebank Collection|besøksdato=2017-10-27|forfattere=Nivre, Joakim et al.|dato=|forlag=|sitat=}}</ref> Blant annet spesifiserer retningslinjene at et utvalg på 17 ulike [[ordklasse]]r skal brukes for alle språk, samt at hodet i en dependensfrase skal være et innholdsord (verb, substantiv osv.), ikke et funksjonsord (hjelpeverb, bestemmere osv.). UD spesifiserer også et filformat, ''CoNLL-U'', som representerer samlinger med annoterte setninger i et [[Tekstfil|rent tekstformat]]. I tillegg gjør prosjektet et utvalg slike trebanker tilgjengelige på nettsidene sine.<ref>{{Kilde www|url=http://universaldependencies.org/#ud-treebanks|tittel=Universal Dependencies v2: UD Treebanks|besøksdato=2017-10-27|forfattere=Universal Dependencies Contributors|dato=|forlag=|sitat=}}</ref> Det finnes tre norske trebanker i UD-formatet. Bokmål og Nynorsk trebankene er konvertert fra den Norske Dependenstrebanken (NDT), som er to separate trebanker, med tekster på bokmål og nynorsk, annotert [[Morfologisk typologi|morfologisk]] og syntaktisk. Nynorsk LIA trebanken er basert på LIA trebanken som er translitterering fra dialekt til nynorsk.<ref>{{Kilde www|url=http://www.hf.uio.no/iln/english/research/projects/language-infrastructure-made-accessible/|tittel=LIA - Department of Linguistics and Scandinavian Studies|besøksdato=2017-10-27|språk=en|verk=www.hf.uio.no}}</ref> NDT ble utviklet 2011-2014 på Nasjonalbiblioteket i samarbeid med tekstlaboratoriet og informatikkdepartementet ved Universitetet i Oslo. NDT er automatisk konvertert til å følge UD-annotasjon ved Lilja Øvrelid ved Universitetet i Oslo.<ref>{{Kilde www|url=http://universaldependencies.org/no/overview/introduction.html|tittel=Introduction|besøksdato=2017-10-27|språk=en-GB|verk=universaldependencies.org}}</ref>

== ''Shared Task'' ==
CoNLL er en årlig konferanse for maskinell naturlig språklæring<ref>[http://www.conll.org «The SIGNLL Conference on Computational Natural Language Learning»]</ref>, som hvert år har en oppgave der flere deltakere tar for seg en relevant oppgave, eller ''Shared Task''. Dependensparsing har vært tema flere ganger.

=== ''2006: Multi-Lingual Dependency Parsing'' ===

Oppgaven som markerte den tiende CoNLL-konferansen (CoNNL-X) innførte conllx-formatet som en standardisert representasjon av en trebank som kunne brukes på tvers av (naturlige) språk. Trebanker for 13 ulike språk ble konstruert, og deltakerne fikk i oppgave å trene dependensparsingmodeller for disse språkene. Disse modellene ble deretter evaluert etter to målestokker: hvor stor andel av dependensrelasjonene som ble funnet og markert med riktig «tagg» (LAS, labeled attachment score) og tilsvarende uten hensyn til om taggen var riktig (UAS, unlabeled attachment score). McDonald et al. oppnådde best resultat med gjennomsnittlige poengsummer på henholdsvis 80,3 og 86,6 på tvers av språk. Et av funnene Buchholz og Marsi trakk frem var at datasettene for noen språk var jevnt over enklere enn andre å få høy poengsum på, da en slik tendens ble funnet på tvers av deltakerne. De var imidlertid avventende med å bruke dette til å påstå at noen språk var enklere enn andre.<ref>Buchholz, Sabine og Marsi, Erwin: [https://dl.acm.org/citation.cfm?id=1596305 «CoNLL-X shared task on Multilingual Dependency Parsing»]</ref>

=== ''2007: Dependency Parsing: Multilingual & Domain Adaptation'' ===

I 2007 ble oppgaven fra året før, utvikling av en parser som skal fungere på tvers av språk, videreført med et nytt utvalg av språk. Samtidig ble en sideoppgave innført der en parser for engelsk skulle videreutvikles til å fungere på et nytt felt, eller domene.<ref name="CoNLL 2007 Shared Task">Nivre et al.: [http://www.aclweb.org/anthology/D07-1096 «The CoNLL 2007 Shared Task on Dependency Parsing»]</ref>

De flerspråklige parserne ble i denne oppgaven evaluert på et utvalg av språk som skulle representere en større grad av [[Språktypologi|typologisk]] variasjon. På disse språkene fikk Nilsson best resultat for LAS (80,32) og Nakagawa best resultat for UAS (86,55). Når man ser på de fire språkene som overlappet med 2006-oppgaven ble resultatet for to språk forbedret og ett språk forverret, mens det siste stod på sted hvil. Her turte Nivre et al. å konkludere med at språk med mye morfologi ga konsekvent lavere resultater enn språk med lite morfologi.<ref name="CoNLL 2007 Shared Task" />

Domenetilpasningsoppgaven gikk ut på å tilpasse en parser som var trent på nyheter til å fungere på tekster i det kjemiske domenene samt [[CHILDES]]-korpuset, som består av transkriberte tekster av barn som lærer sitt førstespråk. Vinnersystemet fra Sagae og Tsuji oppnådde for de kjemiske tekstene en LAS på 81,06, sammenlignet med 89,01 for den flerspråklige oppgaven, mens CHILDES-korpuset jevnt over ga dårlige resultater for alle deltakerne. Det ble konkludert med at det hovedsakelige problemet lå i konverteringen fra parsernes annoteringsformat til formatet som ble brukt i oppgaven.<ref name="CoNLL 2007 Shared Task" />

=== ''2017: Multilingual Parsing from Raw Text to Universal Dependencies'' ===

Med oppgaven i 2017 hadde man et helt nytt utgangspunkt takket være Universal Dependencies, som ga et treningsmateriale bestående av trebanker for over 50 språk med konsekvent annotering på tvers av språk. Zeman et al. rapporterte at Stanford var i stand til å oppnå et gjennomsnittlig LAS-resultat på 81,77 for 55 trebanker som dekket over 40 språk, med det forbehold at dette resultatet ikke kunne sammenlignes direkte med tidligere resultater.<ref>Zeman et al.: [http://universaldependencies.org/conll17/proceedings/pdf/K17-3001.pdf «CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies»]</ref>

==Referanser==
<references />

[[Kategori:Språkteknologi]]
[[Kategori:Informatikk]]
[[Kategori:Lingvistikk]]
[[Kategori:Parsingalgoritmer]]