MDL hierarchical clustering for stemmatology

Po-Hsiang Lai, Teemu Teppo Roos, Joseph O'Sullivan

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu


In real life, one often encounters situations where one needs to infer a structural relationship among data points based on an incomplete dataset. Stemmatology and phylogenetics are two classes of such problems where partial text scripts or genome sequences are available and the goal is to reconstruct the copying history of scripts or evolutionary relations among species. In this paper, we study the potential applications of minimum description length (MDL) concepts to the structural inference problem, particularly focusing on stemmatology where in addition to missing data points, the available data points have missing values. We offer new insights on how to handle these issues, especially missing values. We develop a general algorithm based on MDL insights that is simple to implement and can be used along with other existing algorithms, and propose a generic MDL encoder with minimal assumptions made about the data. In simulations, our method performs reasonably well on a simple dataset and outperforms major existing methods in a larger and much more realistic dataset. We discuss directions and ongoing efforts to further improve performance.
OtsikkoInformation Theory Proceedings (ISIT)
ToimittajatM. Gastpar, R. Heath, K. Narayanan
KustantajaIEEE Press
Julkaisupäiväkesäkuuta 2010
ISBN (painettu)978-1-4244-7890-3
ISBN (elektroninen)978-1-4244-7891-0
DOI - pysyväislinkit
TilaJulkaistu - kesäkuuta 2010
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
Tapahtuma2010 IEEE Information Theory Symposium - Austin, Texas, Yhdysvallat (USA)
Kesto: 13 kesäkuuta 201018 kesäkuuta 2010


  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä