LXMLS 2017 - Day 4

Syntax and Parsing



In [2]:

    
%matplotlib inline



In [4]:

    
%load_ext autoreload









    



The autoreload extension is already loaded. To reload it, use:
  %reload_ext autoreload



In [5]:

    
%autoreload 2
import sys
import scipy
sys.path.append(".")
import lxmls

CKY Algorithm: Step by Step

The CKY algorithm is a dynamic programming algorithm, much like Viterbi. The general idea is to build up on smaller, simpler things you have computed in previous iterations.

Viterby is focused on building sequences (of labels) by computing the highest scoring sequence of length $n$ from sequences of length $(n-1)$. CKY expands this idea to graphs, which can be thought as higher dimension sequences. In particular, trees spanning over $n$ words are built from trees spanning up to $(n-1)$ words.

In the next section, we're going to do some CKY iterations on a real sequence, to get a more concrete sense of how the algorithm works.



In [ ]: