Moderated by Stephen Muggleton.
 

Boris Ryabko

The nonprobabilistic approach to learning the best prediction

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

N:o Question Answer(s) Continued discussion
1 15.10  Anonymous Referee 1
   
2 15.10  Anonymous Referee 2
   
 

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).