The
article
mentioned above has been submitted to the Electronic
Transactions on Artificial Intelligence, and the present page
contains the review discussion. Click here for
more
explanations and for the webpage of theauthor, Boris Ryabko.
Overview of interactions
Q1. Anonymous Referee 1 (15.10):
Recommendation: The paper can be accepted for ETAI after minor
revisions. No further refereeing round is needed.
Summary:
This paper discusses the problem of predicting the next character
in a string using the information of the previous characters.
When the source of characters is stationary and ergotic,
although an asymptotically optimal prediction method exists,
it cannot find "simple" patterns appearing in the string, such as
in: 0100100010000100000...
This paper introduces a new approach to analyzing such sequences,
and shows
1. the existence of large sets of well predictable sequences which
cannot be found with the ESS (ergotic and stationary source) model,
and
2. the existence of large sets which can be predicted with complex
algorithms which do not use only estimations of conditional properties.
Comments:
It might help if the definitions were more "decorative".
Minor problems:
Introduction:
Line 9:
Each moment $t$ that the gambler divides the capital $V_t$ into
$|A|$ parts equals $V_tP_I(a | x_1,\ldots, x_t), a \in A$.
This would read: t equals V_tP_I(...) ? (but probably not)
Q2. Anonymous Referee 2 (15.10):
This paper is apparently of high quality. Unfortunately, the field is
outside my area of competence and I cannot give any better judgement than a
general appreciation of the quality of the work. My understanding is that
it is a very important contribution to the theory of learning and with
strong applications to learning e.g. in biological systems that probably
are not probabilistic.
The presentation is very expert and it would have been well-written if it
had not several (correctable) English mistakes. Regarding some details, I
believe it would be useful for many a readers to add a definition of
ergodic and stationary processes. I also wonder whether there are any
possible connections to Valiant's work that need be explored. Having no
access to literature at the moment of writing the review I am only
providing one author of an interesting work on what is learnable/not
learnable. The authors are Gora et al and I believe one can find a precise
reference at the home page of the Logic Section, Department of Mathematics,
Warsaw University, or through a search for Andzrej Skowron's page and that
Section.
Background: Review Protocol Pages and the ETAI
This Review Protocol Page (RPP) is a part of the webpage structure
for the Electronic Transactions on Artificial Intelligence, or
ETAI. The ETAI is an electronic journal that uses the Internet
medium not merely for distributing the articles, but also for a
novel, two-stage review procedure. The first review phase is open
and allows the peer community to ask questions to the author and
to create a discussion about the contribution. The second phase -
called refereeing in the ETAI - is like conventional journal
refereeing except that the major part of the required feedback
is supposed to have occurred already in the first, review phase.
The referees make a recommendation whether the article is to be
accepted or declined, as usual. The article and the discussion
remain on-line regardless of whether the article was accepted or
not. Additional questions and discussion after the acceptance decision
are welcomed.
The Review Protocol Page is used as a working structure for the entire
reviewing process. During the first (review) phase it accumulates the
successive debate contributions. If the referees make specific
comments about the article in the refereeing phase, then those comments
are posted on the RPP as well, but without indicating the identity
of the referee. (In many cases the referees may return simply an
" accept" or " decline" recommendation, namely if sufficient feedback
has been obtained already in the review phase).
| 