7
$\begingroup$

I am currently working on my last project before graduating. For this project, I have to develop a Natural Language Question Answering System. Now, I have read quite some research papers regarding this topic and have figured out everything except for the parsing algorithm.

The NL Q-A will be programmed in Python, and I will use the spaCy library to finish this project. However, I am stuck when it comes to parsing algorithms. I managed to reduce the parsing algorithms to 3:

  • Cocke-Kasami-Younger (CKY) algorithm
  • Earley algorithm
  • Chart Parsing algorithm

Note: I know that all three algorithms are chart parsing algorithms. I also know that the Earley algorithm is context-free, but has a low efficiency for a compiler.

What I don't know is: Which one should I pick? (Please, provide a non-subjective answer to this question!)

The system is for a specific domain. The answer to the natural question will be displayed in the form of the result of a calculation of some kind. Preferably in the tabular or graphical form.

I have done my research. However, I probably do not understand the algorithms properly, which makes it difficult to make a selection.The algorithm should be efficient and perhaps outperform others.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I have been reading and reading, and found answers to almost all my questions.

I am sticking to Earley algorithm, given that it offers a dynamic programming approach (CKY does the same). Both algorithms are chart parsing algorithms.

Earley is a context-free, top-down parsing algorithm, which makes it a goal-driven algorithm. From start symbol down. Furthermore, it is more efficient than the CKY algorithm.

Here are the slides that provide more info.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Use shift-reduce dependency parsing algorithm! $\endgroup$
    – kiner_shah
    Feb 6, 2017 at 12:34
  • $\begingroup$ @kiner_shah thank you for your comment! I know SpaCy contains a shift-reduce dependency parsing algorithm. However, why use shift-reduce depencency parsing algorithm over Earley? Couldn't find that answer. therefore had dropt it.. $\endgroup$
    – lilienfa
    Feb 6, 2017 at 12:36
  • $\begingroup$ Dependency parsing will give you the dependencies between various words in addition to parsing and validating the sentence structure. Those dependencies can be used for relation extraction in the question, to understand what the question is. Earley or CYK parsing will just give you the parse tree. You won't be able to do much with that parse tree! $\endgroup$
    – kiner_shah
    Feb 7, 2017 at 7:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .