M.Sc Thesis

M.Sc StudentLyachover Dmitry
SubjectUniversal Classification with Limited Training Data
DepartmentDepartment of Electrical and Computer Engineering


The problem of classification with finite memory is investigated.

This work is based on recent works by Ziv. 

  Universal classification algorithms are extremely important for discrimination and identification of finite

length sequences with rich alphabet emitted from unknown sources.

We consider classification of sequences emitted from the random source, where classifier has full

 information about one of the sources and the second one is represented by limited training sequence.

   We refer to three different basic universal classifiers that have appeared in the literature.

1)      A classifier based on Kac’s lemma when applied to l-vectors  (Wyner-Ziv classifier (1996)).

2)      A universal classifier (Ziv classifier (2003)) that uses classification that is conditioned on a context

      limited to sequences that appeared in the past or in a training sequence.

3)      A universal classifier (Ziv-Merhav empirical divergence estimator (1993))

      based on LZ data compression algorithm.

   In the first part, the Wyner-Ziv classification algorithm is studied and simulated. Some parameters like sequence length,

l-vector length and performance (like error probability, variance and complexity ) are investigated and their influence on universal classification error is explored. A modified classification algorithm based on Chernoff Bound is derived and explored.

  In the second part, the Ziv universal classification algorithm is studied and simulated. Some parameters like sequence length and appropriate criterions are investigated. The influence of the true divergence between different Markov sources on universal classification is explored. Error probabilities and computational complexity are analyzed. 

A classification algorithm based on Ziv algorithm and PST prediction algorithm is derived and simulated.

  In addition, we deal with Ziv-Merhav universal classification algorithm and the performance of this algorithm is analyzed.

An improved Ziv-Merhav universal classification algorithm is also simulated and investigated.

  Finally, we compare the different classification schemes mentioned above and conclusions are derived.