22.18 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, \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, \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 \(\frac{1}{1-q}\) has Taylor expansion \[ 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^*\) but only from positive examples: First we get \(1 ({=} \varepsilon)\), then \(q\), then \(q^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, \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 \(\frac{1}{(1-q)^2}\) has Taylor expansion \(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, \quad 2, \quad 2 + 2q - q^2, \quad 2 + 2q + 2q^2 - 2q^3, \quad {\dots} \quad {}\longrightarrow{} \quad \textnormal{???} \] Notice that, for \(q^2\), the weight changed from \({-}1\) to \(2\) from iteration 3 to 4. The same can be observed for the \(q^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 \(q^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)?