Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Dynamic Programming Algorithms for Semantic Dependency Parsing
Linköping University, Department of Computer and Information Science, Human-Centered systems.
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Algoritmer för semantisk dependensparsning baserade på dynamisk programmering (Swedish)
Abstract [en]

Dependency parsing can be a useful tool to allow computers to parse text. In 2015, Kuhlmann and Jonsson proposed a logical deduction system that parsed to non-crossing dependency graphs with an asymptotic time complexity of O(n3), where “n” is the length of the sentence to parse. This thesis extends the deduction system by Kuhlmann and Jonsson; the extended deduction system introduces certain crossing edges, while maintaining an asymptotic time complexity of O(n4).

In order to extend the deduction system by Kuhlmann and Jonsson, fifteen logical item types are added to the five proposed by Kuhlmann and Jonsson. These item types allow the deduction system to intro-duce crossing edges while acyclicity can be guaranteed. The number of inference rules in the deduction system is increased from the 19 proposed by Kuhlmann and Jonsson to 172, mainly because of the larger number of combinations of the 20 item types.

The results are a modest increase in coverage on test data (by roughly 10% absolutely, i.e. approx. from 70% to 80%), and a comparable placement to that of Kuhlmann and Jonsson by the SemEval 2015 task 18 metrics. By the method employed to introduce crossing edges, derivational uniqueness is impossible to maintain. It is hard to defien the graph class to which the extended algorithm, QAC, parses, and it is therefore empirically compared to 1-endpoint crossing and graphs with a page number of two or less, compared to which it achieves lower coverage on test data. The QAC graph class is not limited by page number or crossings.

The takeaway of the thesis is that extending a very minimal deduction system is not necessarily the best approach, and that it may be better to start off with a strong idea of to which graph class the extended algorithm should parse. Additionally, several alternative ways of extending Kuhlmann and Jonsson are proposed.

Abstract [sv]

Dependensparsning kan vara ett användbart verktyg för att få datorer att kunna läsa text. Kuhlmann och Jonsson kom 2015 fram till ett logiskt deduktionssystem som kan parsa till ickekorsande grafer med en asymptotisk tidskomplexitet O(n3), där "n" är meningens som parsas längd. Detta arbete utökar Kuhlmann och Jonssons deduktionssystem så att det kan introducera vissa korsande bågar, medan en asymptotisk tidskomplexitet O(n4) uppnås.

För att tillåta deduktionssystemet att introducera korsande bågar, introduceras 15 nya logiska delgrafstyper, eller item. Dessa item-typer tillåter deduktionssystemet att introducera korsande bågar på ett sådant sätt att acyklicitet bibehålls. Antalet logiska inferensregler tags från Kuhlmanns och Jonssons 19 till 172, på grund av den större mängden kombinationer av de nu 20 item-typerna.

Resultatet är en mindre ökning av täckning på testdata (ungefär 10 procentenheter, d v s från cirka 70% till 80%), och jämförbar placering med Kuhlmann och Jonsson enligt måtten från uppgift 18 från SemEval 2015. Härledningsunikhet kan inte garanteras på grund av hur bågar introduceras i det nya deduktionssystemet. Den utökade algoritmen, QAC, parsar till en svårdefinierad grafklass, som jämförs empiriskt med 1-endpoint-crossing-grafer och grafer med pagenumber 2 eller mindre. QAC:s grafklass har lägre täckning än båda dessa, och har ingen högre gräns i pagenumber eller antal korsningar.

Slutsatsen är att det inte nödvändigtvis är optimalt att utöka ett mycket minimalt och specifikt deduktionssystem, och att det kan vara bättre att inleda processen med en specifik grafklass i åtanke. Dessutom föreslås flera alternativa metoder för att utöka Kuhlmann och Jonsson.

Place, publisher, year, edition, pages
2017. , p. 102
Keywords [en]
semantic dependency parsing, machine learning, parsing, logic, deduction system, crossing edges, SemEval, coverage, crossing arcs, graph, graph class, non-crossing, QAC, quartic, acyclic
Keywords [sv]
semantisk dependensparsning, maskininlärning, parsning, logik, deduktionssystem, korsande bågar, SemEval, täckning, korsande kanter, graf, grafklass, ickekorsande, QAC, kvartiskt, acykliskt
National Category
Language Technology (Computational Linguistics)
Identifiers
URN: urn:nbn:se:liu:diva-138594ISRN: LIU-IDA/LITH-EX-A--17/014--SEOAI: oai:DiVA.org:liu-138594DiVA, id: diva2:1111896
Subject / course
Computer Engineering
Presentation
2017-05-31, Alan Turing, Hus E, ingång 27 C, Linköpings Universitet, Linköping, 13:15 (Swedish)
Supervisors
Examiners
Available from: 2017-06-21 Created: 2017-06-19 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

fulltext(4425 kB)92 downloads
File information
File name FULLTEXT01.pdfFile size 4425 kBChecksum SHA-512
8750f5c7253e79b24bfa249651ede0a03da789b7e6855127c4ab682733a80dca5fcdd57d722bc5eba12b7b0b1c3b714fd60e2693e60016e24144abab67fa90c4
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Axelsson, Nils
By organisation
Human-Centered systems
Language Technology (Computational Linguistics)

Search outside of DiVA

GoogleGoogle Scholar
Total: 92 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 389 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf