← All problems
Unverified

Learning sequences

The following is a problem inspired from quantitative program verification. It is more vague than ``Prove or disprove whether XYZ holds'', but in turn has real applications in probabilistic verification. I posed this problem several times to several different machine learning experts and none of them were able (or interested) to help me with this problem. I now hope that the automata (learning) experts can help me out. We would like to learn / guess the limit of the sequence

1,32,74,158,…⟶2 1, \quad \frac{3}{2}, \quad \frac{7}{4}, \quad \frac{15}{8}, \quad {\dots} \quad {}\longrightarrow{} \quad 2

In order to approach this problem more systematically, we do have -- in practice -- access to a more symbolic representation of this sequence, namely

1,1+q,1+q+q2,1+q+q2+q3,…⟶11−q . 1, \quad 1 + q, \quad 1 + q + q^2, \quad 1 + q + q^2 + q^3, \quad {\dots} \quad {}\longrightarrow{} \quad \frac{1}{1 - q}~.

The limit 11−q\frac{1}{1-q} has Taylor expansion

1+q+q2+q3+q4+q5+⋯ 1 + q + q^2 + q^3 + q^4 + q^5 + \cdots

So learning the limit of this sequence appears like wanting to learn the ``regular language''~q∗q^* but only from positive examples: First we get 1(=ε)1 ({=} \varepsilon), then qq, then q2q^2, and so on. So the problem is: How can we learn / guess regular languages from positive examples (reasonably well)? Going one step further, we would also like to learn the following sequence (which did not occur to me in practice, but I made up):

q,q+2q2,q+2q2+3q3,q+2q2+3q3+4q4,…⟶1(1−q)2 q, \quad q + 2q^2, \quad q + 2q^2 + 3q^3, \quad q + 2q^2 + 3q^3 + 4q^4, \quad {\dots} \quad {}\longrightarrow{} \quad \frac{1}{(1 - q)^2}

The limit 1(1−q)2\frac{1}{(1-q)^2} has Taylor expansion q+2q2+3q3+4q4+5q5+⋯q + 2q^2 + 3q^3 + 4q^4 + 5q^5 + \cdots So learning the limit of this sequence appears like wanting to learn a weighted ``regular language'' (are there regular expressions for weighted languages?) but only from positive examples. So: How can we learn / guess weighted regular languages from positive examples (reasonably well)? Another example -- this one again does actually occur in practice -- is learning the limit of the (more complicated) sequence

1,2,2+2q−q2,2+2q+2q2−2q3,…⟶??? 1, \quad 2, \quad 2 + 2q - q^2, \quad 2 + 2q + 2q^2 - 2q^3, \quad {\dots} \quad {}\longrightarrow{} \quad \textnormal{???}

Notice that, for q2q^2, the weight changed from −1{-}1 to 22 from iteration 3 to 4. The same can be observed for the q0q^0 weight from iteration 1 to 2. I hence suspect that this is not ``learning from positive examples'' anymore, but something slightly more general. In particular, I do believe that the weights for each qnq^n stabilize at some iteration and never again change. So our problem is: From what kind of examples are we even trying to learn here? Can such learning be done (reasonably well)?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu