Dependency Parsing as a Classification Problem

Deniz Yuret. In Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X)



Abstract: This paper presents an approach to dependency parsing which can utilize any standard machine learning (classification) algorithm. A decision list learner was used in this work. The training data provided in the form of a treebank is converted to a format in which each instance represents information about one word pair, and the classification indicates the existence, direction, and type of the link between the words of the pair. Several distinct models are built to identify the links between word pairs at different distances. These models are applied sequentially to give the dependency parse of a sentence, favoring shorter links. An analysis of the errors, attribute selection, and comparison of different languages is presented.

Full post... Related link

Learning Morphological Disambiguation Rules for Turkish

Deniz Yuret and Ferhan Türe. In Proceedings of the Human Language Technology Conference - North American Chapter of the Association for Computational Linguistics Annual Meeting (HLT-NAACL 2006)
You can download the paper here, the stand-alone Turkish morphological disambiguator here, and the code used in this paper to train the model here.



Abstract: In this paper, we present a rule based model for morphological disambiguation of Turkish. The rules are generated by a novel decision list learning algorithm using supervised training. Morphological ambiguity (e.g. lives = live+s or life+s) is a challenging problem for agglutinative languages like Turkish where close to half of the words in running text are morphologically ambiguous. Furthermore, it is possible for a word to take an unlimited number of suffixes, therefore the number of possible morphological tags is unlimited. We attempted to cope with these problems by training a separate model for each of the 126 morphological features recognized by the morphological analyzer. The resulting decision lists independently vote on each of the potential parses of a word and the final parse is selected based on our confidence on these votes. The accuracy of our model (96%) is slightly above the best previously reported results which use statistical models. For comparison, when we train a single decision list on full tags instead of using separate models on each feature we get 91% accuracy.


Full post... Related link

Ray Solomonoff

Ray Solomonoff gave a nice series of lectures at Bilgi University this week and peaked my interest in algorithmic probability again. The link below contains some of his stuff. Should find out more about Levin's search (http://www.idsia.ch/~juergen/optimalsearch.html). Juergen's website contains more interesting stuff as well:

http://www.idsia.ch/~juergen/
Full post... Related link

Non-parametric Bayesian methods

[Math_ Learning_] Some tutorials:
http://wwwbrauer.informatik.tu-muenchen.de/~trespvol/papers/DPTresp2006.pdf
http://www.gatsby.ucl.ac.uk/~zoubin/talks/uai05tutorial-b.pdf
http://www.cs.berkeley.edu/~jordan/nips-tutorial05.ps
Full post...

Information Theory, Inference, and Learning Algorithms by David MacKay

[Books_] I just discovered this wonderful book by David MacKay. It has a very good interpretation of Occam's razor in Bayesian terms. Very nice examples of Bayesian inference and pitfalls of orthodox statistics. The book is at the intersection of communication, inference, and learning (although very little learning). I am still undecided about the pedagogic value of information theory for teaching inference - for the most part the information theory results can be stated in probability terms and vice versa. It inspired me to replan my machine learning course more on foundations and less on various algorithmic incarnations. The book is freely available on the net at the above address (which is another reason I appreciated it and bought a hardcopy at Amazon).
Full post... Related link