Comment on Reply of Benedetto et al.
We regret to point out several inaccurate and misleading statements that Benedetto {\em et al.} make in their Reply\cite{Bene:2003r} to our Comment\cite{khmelev:2003c} on their paper titled ``Language Trees and Zipping''\cite{Bene:2002}.
replycom.tex
% Group addresses by affiliation; use superscriptaddress for long
% author lists, or if there are many overlapping affiliations.
% For Phys. Rev. appearance, change preprint to twocolumn.
% Choose pra, prb, prc, prd, pre, prl, prstab, or rmp for journal
%  Add 'draft' option to mark overfull boxes with black boxes
%  Add 'showpacs' option to make PACS codes appear
%  Add 'showkeys' option to make keywords appear
\documentclass[aps,prl,twocolumn,showpacs,superscriptaddress]{revtex4}
%\documentclass[aps,prl,preprint,superscriptaddress]{revtex4}
%\documentclass[aps,prl,twocolumn,groupedaddress]{revtex4}

% You should use BibTeX and apsrev.bst for references
% Choosing a journal automatically selects the correct APS
% BibTeX style file (bst file), so only uncomment the line
% below if necessary.
%\bibliographystyle{apsrev}

\begin{document}

% Use the \preprint command to place your local institutional report
% number in the upper righthand corner of the title page in preprint mode.
% Multiple \preprint commands are allowed.
% Use the 'preprintnumbers' class option to override journal defaults
% to display numbers if necessary
%\preprint{}

%Title of paper
\title{Comment on Reply of Benedetto et al.}

% repeat the \author .. \affiliation  etc. as needed
% \email, \thanks, \homepage, \altaffiliation all apply to the current
% author. Explanatory text should go in the []'s, actual e-mail
% address or url should go in the {}'s for \email and \homepage.
% Please use the appropriate macro foreach each type of information

% \affiliation command applies to all authors since the last
% \affiliation command. The \affiliation command should follow the
% other information
% \affiliation can be followed by \email, \homepage, \thanks as well.
\author{Dmitry V. Khmelev}
\email{D.Khmelev@newton.cam.ac.uk}
%\homepage[]{Your web page}
%\thanks{}
\affiliation{}  
\affiliation{Heriot-Watt
  University, Edinburgh, U.K. and Moscow State University, Russia}

\author{William J. Teahan}
\email{wjt@informatics.bangor.ac.uk}
%\homepage[]{Your web page}
%\thanks{}
\affiliation{University of Wales, Bangor, Dean Street, Bangor, LL57 1UT, U.K.}

\date{\today}

\begin{abstract}
  We regret to point out several inaccurate and misleading statements
that Benedetto {\em et al.} make in their Reply\cite{Bene:2003r} to
our Comment\cite{khmelev:2003c} on their paper titled ``Language Trees
and Zipping''\cite{Bene:2002}.
\end{abstract}

% insert suggested PACS numbers in braces on next line
\pacs{89.70.+c, 01.20.+x, 05.20.-y, 05.45.Tp}
% insert suggested keywords - APS authors don't need to do this
%\keywords{}

%\maketitle must follow title, authors, abstract, \pacs, and \keywords
\maketitle

We regret to point out several inaccurate and misleading statements
that Benedetto {\em et al.} make in their Reply\cite{Bene:2003r} to
our Comment\cite{khmelev:2003c} on their paper titled ``Language Trees
and Zipping''\cite{Bene:2002}.

First they confusingly state in paragraph 7 that Russian and Greek
alphabets are not phonetic, putting Russian and Greek in a row with
Chinese, the latter enjoing hieroglyphic writings. Second, they use
unfair and irrelevant experiments in order to convince the reader that
the gzip-based approach is better than the Markov chains based
approach. Third, the figures reported for Newsgroups corpus seems to
be obtained on a randomly selected small subset of the Newsgroups corpus,
which probably makes them completely meaningless in the discussed
topic. Fourth, their reference to RAR compressor classification
performance for refuting our Comment is irrelevant to our Comment and
their Letter\cite{Bene:2002}. And fifth, authors of~\cite{Bene:2003r}
obviously experience some problems with scientific English language.
We elaborate on each of these points in more detail in the subsequent
paragraphs.

It is a well-established fact that Russian language as well as Greek
enjoys phonetic alphabet. Perhaps, Benedetto \emph{et
  al.}~\cite{Bene:2002} meant to use the transliteration for the
construction of Language Tree (LT). However this procedure has its
drawbacks like non-uniqueness, non-reversability, and inexactness of
the transformation. Most importantly this procedure requires some
\emph{knowledge} about the language, which shows that the requirement
for \emph{a-priori} information, pointed out in~\cite{khmelev:2003c}
remains valid contrary to the claim in~\cite{Bene:2002}.

We believe that if one wants to compare the perfomance of several
classification methods then the comparision should be performed in the
same experimental framework. To start with, let us denote by $M$, $G$,
$g$ the classification performance of the following methods,
respectively, on the corpus, discussed in~\cite{Khmelev:2000}: Markov
Chains approach~\cite{Khmelev:2000}; attribution with a single
source using gzip~\cite{Kukush:2001}; and attribution with
multiple-source using gzip~\cite{Bene:2002}. Let us denote by
$M'$, $G'$, $g'$ the classification performance of these methods in
the framework of~\cite{Bene:2002}, and, finally, let $M''$, $G''$,
$g''$ denote the classification performance of the same methods on the
Newsgroups dataset.  Notice that in~\cite{Bene:2002} only values for
$G''=60\%<g''=85\%$ and $G''=77\%<g''=93\%$ are presented. One can not
make any conclusion about $M'$ or $M''$ using these data, so our
statement about superiority of Markov Chains approach with respect to
gzip approach (either with a single- or multiple-source files)
remains valid.  Moreover, we have stated in our
Comment~\cite{khmelev:2003c} that $M=69/82\approx84\%$ is greater than
$G=50/82\approx61\%$. We also reported to editors of Phys.Rev.Lett.
in our answer to the referee report of Benedetto \emph{et al.} that
$g=53/82\approx65\%$, which can indeed be considered as an argument
for our claim that generally Markov chains are more attractive than
gzip-based approach.

In our opinion the ``slightly different method'' of \cite{Bene:2002}
should be considered as an approach to the design of the experiment,
which leads to an extremely slow classification speed especially in
the case of thousands of documents to classify, where a thousand
source documents makes prohibitive the really large experiment on
classification. This gives rise to the question of the validity of the
figures $G''=60\%$ and $g''=85\%$ outlined in~\cite{Bene:2003r}.
Traditionally, the precision of the classification method on the
Newsgroups is measured in the following way: one performs a random
10-fold or 5-fold split and reports the average results of
cross-validation.  Typical numbers reported are around
80\%~\cite{Teahan:2000}, with 82.1\% for PPM (Markov-based) approach.
It would be interesting to know the technique used
by\cite{Bene:2003r}, since even 5-fold split validation by their
method would require about
$5\times(18828/5)\times(4\times18828/5)\approx284\times10^6$ calls of gzip
compression program, which is prohibitive on conventional computers.
If one wants to apply a complete cross-validation as suggested
in~\cite{Bene:2002}, then one has to do even more
$18828^2\approx354\times10^6$ calls of gzip. We suspect that the
figures $G''=60\%$ and $g''=85\%$, outlined in~\cite{Bene:2003r}, are
obtained on a randomly selected small subset of the Newsgroups, are
subject to essential random variation, and hence $G''=60\%$ and
$g''=85\%$ should not be used for quantitative comparision of a
single- and multiple-source file setting.

Finally, in our Comment we stated that Markov chain approach as
reported in~\cite{Kukush:2001} is superior to LZ approach \emph{used
  in}~\cite{Bene:2002}. This statement was misinterpreted
in~\cite{Bene:2003r} as a general statement that LZ approach is
outperformed by the \emph{simple Markov chain} approach and Benedetto
\emph{et al.}\cite{Bene:2003r} easily refute the misinterpreted
statement using our own result on RAR~\cite{Kukush:2001}. The correct
generalization (and the only possible understanding in view of
references given) of our statement is: \emph{for any modification of
  LZ compression scheme there exists a modification of Markov Chain
  approach (PPM compression scheme), which outperforms LZ in
  classification} (this statement is similar to a well-known postulate
among specialists: any modification of LZ compression scheme can be
outperformed by a properly modified PPM compression scheme).  The
highly sophisticated, going far beyond the naive use of Ziv-Lempel
theory, algorithm of RAR, know-how of its creator Eugene Roshal,
should be compared with, for example, the the state-of-art PPMd
(PPMonstr) algorithm developed recently by Dmitry Shkarin. And we find
extremely interesting and scientifically valuable that the tough
first-order Markov chain produce results competitive to highly
sophisticated algorithms. As for the polemical comparision between
Markov Chain and RAR compressor by Benedetto \emph{et
  al.}\cite{Bene:2003r}, we find it irrelevant in the framework of
their paper~\cite{Bene:2002}. Indeed, if Benedetto \emph{et
  al.}\cite{Bene:2003r} stand for technical
details, like multiple- and single- source classification, they should
restrict their method to application of gzip only, which is the main 
technical detail of their Letter~\cite{Bene:2002}.

As a final remark we would like to point out that
Reply~\cite{Bene:2003r} exhibits some language
mistakes of it's authors themselves. Indeed, they reference to our
comment~\cite{khmelev:2003c} using expression ``Khmelev \emph{et al}''
as if~\cite{khmelev:2003c} has at least three co-authors (common
meaning of \emph{et al} is \emph{and others}).

To sum up, one can not draw any conclusion on the comparision between
$n$th order Markov chain approach (by which we
meant\cite{khmelev:2003c} the PPM approach as well) with gzip-based
approach from the statements, given in~\cite{Bene:2003r}. We also
believe that the authors of\cite{Bene:2003r} were not aware of our
reported figure for $g=64\%$; otherwise it looks very strange that
they did not mention this argument in their Reply. Also we suggest to
authors of~\cite{Bene:2003r} to present a fair comparision of their
method against others, \cite{Teahan:2000}, \cite{Kukush:2001} and,
e.g., SVM
approach~\cite{allwein00reducing,crammer00learnability,weston98multiclass}.


P.S. This story shows that editors of physical journal like
Phys.Rev.Lett. perhaps should avoid publishing papers
like~\cite{Bene:2002}, because Phys.Rev.Lett. referees do not have
enough experience to identify scientifical value and mistakes in
non-physical papers. We also encourage physicists and mathematicians
to send their non-physical and non-mathematical papers to appropriate
scientific journals, even if they are not so well-known as
Phys.Rev.Lett. Probably such a publication would not yield much
publicity, but the quality and scientific value of the paper would
increase significantly.

The example with~\cite{Bene:2002} is not unique. A similar story,
which reappears time-to-time in newspapers, is the story about
computing using DNA, described in details in~\cite{gusfield}. It is
possible to do computations with DNA. However, the amount of DNA,
required for solution of, say, salesmen problem with 100 cities, is
comparable with the Earth mass, which makes it's use impractical and
impossible. Notice that computer science methods allow to solve
practical salesmen problem in reasonable time for number of cities
like $10^6$ on contemporary computers.  However, the authors of DNA
computation speculative approach speculate that the effectiveness
issue will be solved in future, a strange analogy with suggestion
of~\cite{Bene:2003r}.

Notice also that a publication of non-physical paper in physical
journal evidence the crisis in physics, which responsible phisicists
should aware of. Otherwise why phisicists are publishing speculative
papers on non-physical subjects? Is not this the evidence that they
can not find application of their abilities in physics?


% Create the reference section using BibTeX:
\bibliography{replycom}

\end{document}

replycom.bbl
\begin{thebibliography}{10}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname bibnamefont\endcsname\relax
  \def\bibnamefont#1{#1}\fi
\expandafter\ifx\csname bibfnamefont\endcsname\relax
  \def\bibfnamefont#1{#1}\fi
\expandafter\ifx\csname citenamefont\endcsname\relax
  \def\citenamefont#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi
\providecommand{\bibinfo}[2]{#2}
\providecommand{\eprint}[2][]{\url{#2}}

\bibitem[{\citenamefont{Benedetto et~al.}(2003)\citenamefont{Benedetto,
  Caglioti, and Loreto}}]{Bene:2003r}
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Benedetto}},
  \bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Caglioti}}, \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{Loreto}},
  \bibinfo{journal}{Phys.\ Rev.\ Lett.} \textbf{\bibinfo{volume}{90}}
  (\bibinfo{year}{2003}).

\bibitem[{\citenamefont{Khmelev and Teahan}(2003)}]{khmelev:2003c}
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Khmelev}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{W.}~\bibnamefont{Teahan}},
  \bibinfo{journal}{Phys.\ Rev.\ Lett.} \textbf{\bibinfo{volume}{90}}
  (\bibinfo{year}{2003}).

\bibitem[{\citenamefont{Benedetto et~al.}(2002)\citenamefont{Benedetto,
  Caglioti, and Loreto}}]{Bene:2002}
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Benedetto}},
  \bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Caglioti}}, \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{Loreto}},
  \bibinfo{journal}{Phys.\ Rev.\ Lett.} \textbf{\bibinfo{volume}{88}}
  (\bibinfo{year}{2002}).

\bibitem[{\citenamefont{Khmelev}(2000)}]{Khmelev:2000}
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Khmelev}}, \bibinfo{journal}{J.
  of Quantitative Linguistics} \textbf{\bibinfo{volume}{7}},
  \bibinfo{pages}{201} (\bibinfo{year}{2000}).

\bibitem[{\citenamefont{Kukushkina et~al.}(2001)\citenamefont{Kukushkina,
  Polikarpov, and Khmelev}}]{Kukush:2001}
\bibinfo{author}{\bibfnamefont{O.}~\bibnamefont{Kukushkina}},
  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Polikarpov}},
  \bibnamefont{and} \bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Khmelev}},
  \bibinfo{journal}{Problems of Information Transmission}
  \textbf{\bibinfo{volume}{37}}, \bibinfo{pages}{172} (\bibinfo{year}{2001}).

\bibitem[{\citenamefont{Teahan}(2000)}]{Teahan:2000}
\bibinfo{author}{\bibfnamefont{W.~J.} \bibnamefont{Teahan}},
  \bibinfo{journal}{Proceedings RIAO'2000} \textbf{\bibinfo{volume}{2}},
  \bibinfo{pages}{943} (\bibinfo{year}{2000}).

\bibitem[{\citenamefont{Allwein et~al.}(2000)\citenamefont{Allwein, Schapire,
  and Singer}}]{allwein00reducing}
\bibinfo{author}{\bibfnamefont{E.~L.} \bibnamefont{Allwein}},
  \bibinfo{author}{\bibfnamefont{R.~E.} \bibnamefont{Schapire}},
  \bibnamefont{and} \bibinfo{author}{\bibfnamefont{Y.}~\bibnamefont{Singer}},
  in \emph{\bibinfo{booktitle}{Proc. 17th International Conf. on Machine
  Learning}} (\bibinfo{publisher}{Morgan Kaufmann, San Francisco, CA},
  \bibinfo{year}{2000}), pp. \bibinfo{pages}{9--16},
  \urlprefix\url{citeseer.nj.nec.com/allwein00reducing.html}.

\bibitem[{\citenamefont{Crammer and Singer}(2000)}]{crammer00learnability}
\bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Crammer}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{Y.}~\bibnamefont{Singer}}, in
  \emph{\bibinfo{booktitle}{Computational Learning Theory}}
  (\bibinfo{year}{2000}), pp. \bibinfo{pages}{35--46},
  \urlprefix\url{citeseer.nj.nec.com/crammer00learnability.html}.

\bibitem[{\citenamefont{Weston and Watkins}(1998)}]{weston98multiclass}
\bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Weston}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{C.}~\bibnamefont{Watkins}},
  \emph{\bibinfo{title}{Multi-class support vector machines}}
  (\bibinfo{year}{1998}), \urlprefix\url{citeseer.nj.nec.com/8884.html}.

\bibitem[{\citenamefont{Gusfield}(1997)}]{gusfield}
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Gusfield}},
  \emph{\bibinfo{title}{Algorithms on strings, trees, and sequences}}
  (\bibinfo{publisher}{Cambridge University Press},
  \bibinfo{address}{Cambridge}, \bibinfo{year}{1997}).

\end{thebibliography}
