We wish to rename the repo to be sfu-nlp-toolkit but we need to refactor the directories to make sure the parser directories and ner, tagger directories are not in conflict.

Implement the MIRA algorithm for weight learning.

See the description and pseudo code provided in David Chiang's paper Hope and fear for discriminative training of statistical translation models.

The problem is, the ner feature generator needs to read some data from two txt files, and in yarn mode, it's just difficult without adding additional parameters to the universal_tagger.

This is my design:
-----------------------------------Sean's part-----------------------------------
DataPool read two files when initiated:
config file: n lines, each line a field name
data file: n columns, each column corresponds to the field name specified in config file
They are both specified in command line arguments.

DataPool read the config file and create a field_name_list. In data file, each time an empty line is read, DataPool pack the columns of data into a list (a list of lists) and give it to Sentence along with field_name_list as arguments of init function.

Sentence should have another function (e.g. fetch_column(self, field_name)) to fetch a column of data according to the field_name.

-----------------------------------Kingston's part------------------------------

1. The field_names of the columns needed for a feature generator is hard-coded (in care_list) in its init function.
2. Sentence reads f_gen.care_list and knows what columns does f_gen care about.
3. Sentence fetches the data columns and pack them with a list.
4. Sentence calls f_gen.init_resources function to give the f_gen the data columns.
5. Thus f_gen gets all it wants from Sentence without having Sentence as its init function's argument.

----------------------------------Branch merge order change------------
In this design, my branch should be merged with Sean's branch, or it doesn't work. After our two branches are merged and debugged, we can merge Vivian's branch.

So what do you think about this design? If you get a better idea, please comment on this issue : )
I have changed code on my branch (data_pool_fgen_clean). Now the english_1st_fgen works fine.

Weight vector could only be dumped to a local directory now. We need to find a way to dump it to HDFS.

Let us create a more hierarchical structure to the repo. Perhaps have a src directory, and a expts directory to separate the main source files from the experiment helper scripts.

The chart is currently allocated and de-allocated for each sentence. Initialization also takes time proportional to the number of cells in the chart. We should use a sparse array trick where a single chart is allocated with a max size and for each sentence we use a sub-part of the entire chart. Also we should implement the O(1) clear operation for sparse arrays.

http://research.swtch.com/sparse

There’s difference between the cube-pruning algorithm introduced in the papers and the implementation by Yizhou.

In the paper, the cube-pruning goes like this:

1. let q loop through [s, t], and separate [s, t] into [s, q], [q+1, t]
2. for each separation, score the k cells at top-left, and get the highest score
3. keep the top k scored separation and q is the feature signature

But Yizhou’s implementation is like this:

1. let q loop through [s, t], and separate [s, t] into [s, q], [q+1, t]
2. for each separation, score the most top-left cell and push it into a heap
3. explore: repeatedly pop the heap, score the neighbouring cells of the cell popped, and push them into the heap
4. the first k popped cells and the scores is kept as the k best scores of [s, t]

The major differences are:

1. In the paper, only one score could be kept for one feature signature (separation), but in Yizhou’s implementation, it is possible for multiple scores being kept with the same feature signature.
2. In the paper, up to (t-s)*k cells are scored, but in Yizhou’s implementation, t - s + 4*k cells are scored

Add 2nd order features and augment the Eisner algorithm to handle these extra features.

implement feature hashing using murmur hash.

have a flag to ignore collisions to implement the feature hashing trick where multiple features share the same weight if hashed to the same integer.

what if the number of features is larger than sys.maxint?

add TAG elementary trees (etrees) in the edge features and also implement the method for building the derived tree described in the Carreras et al paper.

Loading the weight vector with -l option is not working, I tested it on debug.config and got an accuracy of 20%, which should have been over 80%

@anoopsarkar Hi Anoop, what do you expect the wiki homepage to be like? I found that it seems you have pushed an empty *.md file two years ago and I don't know if this is done by mistake.

Parsing will occur in multiple rounds (at least two). First round is done using first-order features. Subsequent rounds use the cube pruning approach described in the following papers:

• Hao Zhang; Ryan McDonald. Enforcing Structural Diversity in Cube-pruned Dependency Parsing. EMNLP 2014. (this one has the clearest examples of the cube pruning algorithm).
• Hao Zhang; Ryan McDonald. Generalized Higher-Order Dependency Parsing with Cube Pruning
• Hao Zhang; Liang Huang; Kai Zhao; Ryan McDonald. Online Learning for Inexact Hypergraph Search. attachment

Use automatically assigned POS tags (use the Stanford POS tagger) to the dev and test sets.

problem with file permissions are causing some issues with spark_submit.

use the hvector package from http://acl.cs.qc.edu/~lhuang/ to implement the weight vector and updates.

this will also make it easier to implement averaged perceptron and MIRA (see Issue #8 )

For 1st order features

1. Eisner state C[s][t][d][c] is a dict, of which the keys and values are both tuples:

   {(POS_of_head, POS_of_dependent): (score, mid_index), ....}

2. Keep every combination of POSTAG of head and dependent

for q in range(s, t):
    for pos_head in possible_POSTAG_of_head:
        for pos_dept in possible_POSTAG_of_dependent:
            for pos_mid in possible_POSTAG_of_q:
                # complete right triangle
                score = C[s][q][->][1](pos_head, pos_mid)][0] + C[q][t][->][0][(pos_mid, pos_dept)][0]
                if (C[s][t][->][0][(pos_head, pos_dept)][0] < score)
                    C[s][t][->][0][(pos_head, pos_dept)] = (score, q)
                # incomplete right trapezoidal
                score = C[s][q][->][0](pos_head, pos_mid)][0] + C[q][t][<-][0][(pos_mid, pos_dept)][0] + get_score(s, t, pos_head, pos_dept)
                if (C[s][t][->][1][(pos_head, pos_dept)][0] < score)
                    C[s][t][->][0][(pos_head, pos_dept)] = (score, q)
                # complete left triangle
                ....
                # incomplete left trapezoidal
                ....

For 2nd order features (with cube pruning)

1. Eisner state C[s][t][d][c] is a list of tuples:

   [(feature_signature , POS_of_head, POS_of_dependent, score, mid_index), ....]

2. Keep only top k tuples

for q in range(s, t):
    for pos_head in possible_POSTAG_of_head:
        for pos_mid in possible_POSTAG_of_q:
            for pos_dept in possible_POSTAG_of_dependent:

                # complete right triangle
                list_left = SELECT tuples FROM C[s][q][->][1] WHERE tuple[1] == pos_head AND tuple[2] == pos_mid ORDER BY score
                list_right = SELECT tuples FROM C[q][t][->][0] WHERE tuple[1] == pos_mid AND tuple[2] == pos_dept ORDER BY score
                C[s][t][->][0].push((q, pos_head, pos_mid, explore(list_left, list_right), q))

                # incomplete right trapezoidal
                list_left = SELECT tuples FROM C[s][q][->][0] WHERE tuple[1] == pos_head AND tuple[2] == pos_mid ORDER BY score
                list_right = SELECT tuples FROM C[q][t][<-][0] WHERE tuple[1] == pos_dept AND tuple[2] == pos_mid ORDER BY score
                C[s][t][->][1].push((t, pos_head, pos_dept, explore(list_left, list_right), q))

                # complete left triangle
                ....
                # incomplete left trapezoidal
                ....
            keep_highest_score(C[s][t][->][0], q, pos_head, pos_mid)
            keep_highest_score(C[s][t][<-][0], q, pos_head, pos_mid)
keep_k_scores(C, s, t)

This can also implemented by dict. In this case, the function keep_k_scores would extract items from the dict, sort them, and delete items other than k best from the dict.

Get the NER code working on the CoNLL 2003 data.

This paper contains an exhaustive list of features for NER.

There may be some organization work to be done. Keep the NER feature generator as a separate file that is loaded (just like how glm_parser.py does it).

If the user accidentally* created a file called (e.g.) -i, the code will try to read from that (probably empty) file instead of parsing it as a flag.

I think the safest solution would be to get the config file path passed in using a parameter like --config because then we can warn the user that the file doesn't exist and there's also no ambiguity about what they meant.

* it's very unlikely, but still a possibility if you do stuff like :w -i because you didn't properly hit ENTER after the w

for instance we should have hooks for the following improvements to the perceptron:

• averaged perceptron
• MIRA (margin infused perceptron updates) or PA updates
• AdaGrad (Duchi et al)
• SAG (Schmidt et al)

I'm trying to run glm_parser.py using UD_Czech.config (no other parameters), and getting the exception in the title.

Shouldn't that directory get created if it's non-existent?

A data pool generator is constructed using feature generator: fgen is passed in data_pool constructor
A feature generator is constructed using sentences: sentence is passed in feature_generator constructor
Need to get rid of this circular dependency, so that data_pool can be created without using fgen.

we switched from config to format for different formats of data files such as CoNLL-X and CoNLL-U or MALT-tab. the code still refers to the data read from the new format files as config.

provide a choice between Eisner and the Ryan McDonald MST parsing algorithm.

particularly interesting for when we add the TAG features.

We should try computing accuracy on the dev set with different count cutoffs for the vocabulary only (i.e. not a count cutoff on features but a count cutoff based on an initial pruning of the vocabulary based on unigram frequency). This will mean more compact models and faster training as well.

A separate idea (which we can come back to later on) is replacing uncommon words is to replace them with the word shape, so that "reprehensible" would get replaced by the token "xxxx", the word "Boeing" would get replaced by "Xxxx", a hyphenated word "ex-accomplice" would get replaced by "Xx-xx", a sequence of 4 digits would get replaced by "YYYY" and a longer number would become "Dddd" and a number with a decimal point becomes "Dd.dd". Some of these heuristics are not that useful since the information is already captured by the POS tag, but it does help in debugging these unknown word features later on.

Track the performance of first order features using words on dev set to check if we are getting similar performance on English UAS as others.

In glm_parser.py, if sys.argv[1] is not a file, and --learner is not used, then learnerValue never gets defined, but it still gets used on line 401 or 403 in

learner = get_class_from_module('sequential_learn', 'learn', learnerValue)

So you get a NameError.

implement the algorithm in sec 3.2 of the Carreras et al paper in order to effectively prune edges using beam search based on marginal scores from a 1st order (purely word-based) dependency model.

While running the tagger in parallel, one couldn't help to discover that the first iteration usually takes significantly less time than the rest of the iterations. To be more specific, on my own tiny cluster, first iteration of training on penn2malt usually takes 3.4 hours, while the rest takes about 6-7 hours. Such difference exhibits signs of memory leaking.

The issue was even more severe with glm_parser. Unlike tagger which at least was able to successfully complete the test, multiple attempts to train on penn2malt on linearb all lead to outOfMemory error(with only 4 shards). When running it on my cluster it was even worse, all the dataNodes gave out outOfMemory error and crushed short after. I checked the memory usage and found all 32GB of memory on one of the nodes are all used up by the parser.

I suspect that this issue might be caused by our cython written parser and WeightVector(hvector). I haven't checked the memory management part of these implementations but I think it might also have something to do with spark.

Currently I have two ideas on addressing this issue:

1. We fix the cython implementation; or
2. instead of using cython for ceisener parser and hvector, we switch to native python for better memory management compatibility with spark and hadoop.

Hi
could you please tell me what does each column in conll dataset show? specially the last columns which are of names (ARGM-TMP*) , (ARG0*) , thanks, I will share a part of one sample here:

bc/cctv/00/cctv_0000 0 0 In IN (TOP(S(PP* - - - Speaker#1 * * * * (ARGM-TMP* * -
bc/cctv/00/cctv_0000 0 1 the DT (NP(NP* - - - Speaker#1 (DATE* * * * * * -
bc/cctv/00/cctv_0000 0 2 summer NN ) summer - - Speaker#1 * * * * * * -
bc/cctv/00/cctv_0000 0 3 of IN (PP - - - Speaker#1 * * * * * * -

I just noticed that Spark 2.0.2 is already released.
Previously all our testings are done under spark version 1, I think we'll need to look into this newer version. The only problem is that the school linearb computer and Hadoop cluster doesn't have the newest version of spark installed yet. I'll try to install it on my own cluster first.

Do an analysis using dev set accuracy of using feature frequency as a cutoff, so ignoring features that occur fewer than k times. Produce some graphs to enable us to speed up the parser by reducing the number of features.

Task: Convert the Ontonotes data into the CoNLL format.

The instructions for conversion are given here: http://cemantix.org/data/ontonotes.html

It also contains the script to convert to CoNLL format for all three languages: English, Chinese and Arabic.

Remove all the log files from master and all branches and move them into the wiki git for this repo.

compare the unlabeled attachment accuracy against another implementation trained on the same training data and evaluated on the same dev data.

We should use eval.pl to compute the unlabeled attachment score. As an external scorer we can be kept honest about the output scores we report.

http://ilk.uvt.nl/conll/software.html

We observed an indentation problem in data_pool.py, get_next_data(). The return statement should not be under the innermost if block, and should be move one level up.

Also there might be an omit of character "0" in that if statement. Please check your branch accordingly

This issue has been fixed in 3rd_order_feature branch

pybind11 is an interesting alternative to Cython

https://github.com/pybind/pybind11

Discuss.