5
$\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? (non-subjective answer to this question)

The system is for a specific domain. And the answer of 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.

Furthermore, 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. (You are my last hope!)

Thank you!

$\endgroup$
1
$\begingroup$

I have been reading and reading, and found answers to almost all my questions. I am sticking to Early algorithm as 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. Slides of comparison, and explanation: https://www.cs.bgu.ac.il/~michaluz/seminar/CKY1.pdf

$\endgroup$
  • $\begingroup$ Use shift-reduce dependency parsing algorithm! $\endgroup$ – kiner_shah Feb 6 '17 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 '17 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 '17 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.