Organizations: Faculty of Mathematics, Technion – Israel Institute of Technology, Haifa, Israel 3200003. · Computational Rational Agents Laboratory (coral-research.org), 2810 N Church St PMB 49028, Wilmington, DE 19802.
We propose novel algorithms for sequence prediction based on ideas from stringology. These algorithms are time and space efficient and satisfy mistake bounds related to particular stringological complexity measures of the sequence. In this work (the first in a series) we focus on two such measures: (i) the size of the smallest straight-line program that produces the sequence, and (ii) the number of states in the minimal automaton that can compute any symbol in the sequence when given its position in base k as input. These measures are interesting because multiple rich classes of sequences studied in combinatorics of words (automatic sequences, morphic sequences, characteristic words) have low complexity and hence high predictability in this sense.
Figures & tables
1
Input: base k , state {D(j),u(j)}j≥0 , new symbol a∈Σ
x^t←argmaxa∈ΣNa (ties broken by a fixed ordering of Σ )
6
receive x[t]
Appendix
Algorithm 3 Plurality Algorithm
1
Input: index i<n , symbol a∈Σ
2
L←n−i
3
Rstart←ISA[i]
4
left←Rstart , right←n−1
5
Rlimit←Rstart
6
while left≤right
7
mid←⌊(left+right)/2⌋
Appendix
Algorithm 4 Pattern range search via suffix array oracle
1
Procedure IPC(i,a)
2
range←PatternRangeSearch(i,a)
3
if range=⊥
4
return 0
5
else
6
(rstart,rend)←range
7
return rend−rstart+1
Appendix
Algorithm 5 IPC and IPM queries
1
Input: LZP state list R , new symbol a∈Σ
2
if R is empty
3
R.append(a)
4
return
5
z←R.len
6
entry←R[z−1]
7
if “entry” is pair (j,k)
Appendix
Algorithm 6 LZP update
1
Input: LZP state list R , alphabet Σ
2
if R is empty
3
return arbitrary symbol
4
z←R.len
5
entry←R[z−1]
6
if “entry” is pair (j,k)
7
len←k
Appendix
Algorithm 7 LZP predict
Tuples looked up
Buffers after the update
t
x[t]
D(1)
D(2)
D(3)
D(4)
u(0)
u(1)
u(2)
u(3)
u(4)
0
a
a
1
b
(a,b)↦0∗
0
2
b
b
0
3
a
(b,a)↦1∗
(0,1)↦0∗
0
4
b
b
0
Appendix
Table 1: The updates of HDP on the word x of Example H.1 . In round t , the column D(j) shows the tuple that is formed from the full buffer u(j−1) (line 8 of Algorithm 1 ) and looked up in D(j) , followed by the index that it receives (line 11 or line 14). An asterisk marks a tuple that is not found in D(j) and is therefore appended to it (line 13). The remaining columns show the buffers after the update, where an empty cell stands for the empty buffer λ .
level 4
0
level 3
0
1
level 2
0
1
1
0
level 1
0
1
1
0
1
0
0
1
level 0
a
b
b
a
b
a
a
b
b
a
a
b
a
b
b
a
t
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Appendix
Figure 1: The aligned blocks of the word x of Example H.1 , labeled by their indices in the dictionaries of HDP. The bottom row shows the positions t . For 1≤j≤4 , the row of level j is divided into the aligned blocks of size 2j , and every block is labeled by the index q s.t. D(j)[q] represents it. This is the index that Algorithm 1 appends to u(j) when the block is completed. The entry D(j)[q] itself is the pair of labels of the two halves of the block, in the row of level j−1 (where the indices of D(0) are the symbols). For example, the block x[4:8]=baab is labeled by 1 at level 2 , and its halves are labeled by 1 and 0 at level 1 . Accordingly, D(2)[1]=(1,0) .
t
V1
V2
V3
Jt
Votes ( a:b )
x^t
x[t]
0
0
1:1
a
a
1
0
1:1
a
b
×
2
{(0,a)}
1
1:0
a
b
×
3
0
1:1
a
a
4
{(0,a),(1,b)}
{(0,a)}
2
1:0
a
b
×
5
{(1,a)}
1
1:0
a
a
Appendix
Table 2: The predictions of HDP in the first 16 rounds on the word x of Example H.1 . For j∈{1,2,3} , the column Vj shows the set V at the beginning of iteration j of the loop in Algorithm 2 , where an empty cell means that the loop does not reach iteration j . (At the beginning of iteration 0 , V={(a,a),(b,b)} in every round.) The algorithm returns in iteration Jt , and the column “Votes” shows how many of the versions in V vote for a and for b in this iteration. Wrong predictions are marked by × .
Figure 2: The SLP P of Example I.1 as a directed acyclic graph. There is an edge for every position in every rule, labeled by this position. For example, the two edges from q0 to q1 correspond to the positions 0 and 4 of δ(q0)=q1cadq1 , and the two edges from q1 to a correspond to the positions 0 and 3 of δ(q1)=abra .