Labels

Showing posts with label ELPL. Show all posts
Showing posts with label ELPL. Show all posts

Tuesday, December 13, 2011

Do we even need machine translation?

Massive-scale online collaboration is a TED talk given by  Luis von Ahn, known as one of the first people who worked with CAPTCHAs and as the inventor of reCAPTCHA. He argues that machine translation isn't good enough and proposes a crowd-sourcing solution for breaking down language barriers. Interesting stuff!




Here's the website of Duolingo, the translation crowd-sourcing project that was described in the talk. Note that this isn't necessarily antagonistic to our AI approach; the output of this project can be used to provide us with the sentence pairs we so desperately need to train our translation algorithms.

Monday, December 5, 2011

CYK-parser performance

Hi all,

so I ran CYK with Viterbi without smoothing out unknown words and as a result I got:

-- len<=15 --
Number of sentence = 603
Number of Error sentence = 0
Number of Skip sentence = 0
Number of Valid sentence = 603
Bracketing Recall = 31.71
Bracketing Precision = 41.81
Bracketing FMeasure = 36.06
Complete match = 0.66
Average crossing = 1.42
No crossing = 51.41
2 or less crossing = 75.79
Tagging accuracy = 83.71

does this match your findings so far? I want to know before I start smoothing :)

Update:
-- All --
Number of sentence = 603
Number of Error sentence = 0
Number of Skip sentence = 0
Number of Valid sentence = 603
Bracketing Recall = 77.30
Bracketing Precision = 78.17
Bracketing FMeasure = 77.73
Complete match = 21.56
Average crossing = 0.73
No crossing = 70.48
2 or less crossing = 89.39
Tagging accuracy = 92.66

Friday, November 25, 2011

ELPL - Empirical findings

Hey peeps,

While sifting through the masses of documents about assignment 1, we found that we have to list some empirical findings about the probabilities of words and productions. I've attached our findings in a document. Could anyone check if it matches your own findings?

https://docs.google.com/open?id=0B5e7DAOiLEZwYjhjODFkZGQtMjI1My00Mjg2LTgzY2UtOGYxZjA3OTdjNGQ0

Cheers

Friday, November 18, 2011

CYK and unit rules

There was some heated discussion on CYK and unit production rules during today's ELPL lab session. In essence, the CYK algorithm expects all the grammar rules to be in the form A -> B C except for when words (terminals) are produced in which case it expects them to be in the form A -> a. This is known as the Chomsky Normal Form (CNF),

However, as we have all seen, our treebanks are not like that; there are some unit productions. I spent some time making up variations of CYK that would work with less strict assumptions but to no avail. It really felt that the problem isn't something that can be easily overcome with a simple hack. From what I could tell, there was some deeply ingrained constraint that probably makes it impossible for any simple modification of CYK to work with a grammar like the one we have.

Still, not all hope is lost. Wikipedia says:
Any context-free grammar can be represented in CNF
I suppose that, by extension, this must be true for PCFGs as well. So, in essence, we should be able to find an algorithm to transcribe our syntax trees and/or grammar to this form, with no loss of information, right? It seems that this might be our best bet. Wikipedia again suggests one. The same algorithm (and some motivation on why it works) can be found in Michael Sipser's "Introduction to the Theory of Computation".

However, this transcription to the CNF might introduce new symbols or merge existing ones. That could pose a problem with the evaluation later because the parsing is expected to produce syntax trees that use the same terminology as the ones in the training dataset.

But! If I understand the algorithm correctly, the only contentious point is when eliminating rules of the form A -> B C D ... which introduces new symbols. Luckily, we don't have any rules in that form.

So, we could just go through the grammar and each time we find a unit rule, A -> B, we remove it. Then, for each rule in the form B -> u (where u is a string that can be composed of terminal and non-terminal symbols) we add the rule A -> u, unless it's one of those unit rules we removed before. This is repeated until no unit rules are left.

A possible issue with the above approach is how to deal with the frequencies / probabilities of these rules. How are we supposed to decide the probabilities of the new rules based on the removed ones? Other than this one thorn, do you think this is a good solution?

Friday, November 11, 2011

CYK for dummies

Hi guys,

here I share a nice PDF (tnx Mihai!) about the CYK algorithm:


The tables shown in the document (1.2, CYK by example) are very useful to understand the idea behind the algorithm, I think that the key point to quickly understand them is just being aware that, for a sentence S, each cell (X,Y), represents the sub-string of S starting with the word X and having length Y.

Enjoy :-)
Dario

 Edit: Additional resources from the comments, credit goes to Robrecht:
Edit again: Even more stuff, credit goes to Wenjin:

someone to make a 2- student group with, Elements of Language Processing and Learning- first assignment

Hi all,
I am a second year student of the Master of Logic. I am taking the AI course Elements of Language Processing and Learning, taught by Khalil Sima'an.

I am looking for a student I can make a group with since the student I was working with decided to drop the course. Is there someone who is still working alone? In the case, I would be happy if you could contact me as soon as possible.

Thank you,
Alessandra