Doplňování posloupností

Vstupem do programu je soubor obsahující na každém řádku číselnou posloupnost. Program se pokusí uhádnout její pokračovaní a výstup uloží ve stejném formátu do souboru.

S volbou --debug vypisuje program do konzole posloupnost, její predikci a získané koeficienty spolu s celkovou chybou odhadu.

Algoritmus

Jako model se používá lineární regrese, vstupem jsou pouze předchozí členy posloupnosti. N-tý člen se predikuje na základě vzorce: a[n] = [1 a[n-1] ... a[n-k]] * w, kde w je vektor vah.

Hledání modelu začíná vztahem a[n] = w[0] + w[1]*a[n-1] a postupuje ke složitějším modelům, pokud stále můžeme získat lepší predikci.

Proč lineární model funguje?

V případě algebraických posloupností bývají následné členy lineární transformací členů předchozích. To platí dokonce i v případě nelineárních vztahů. Každý člen pak v sobě obsahuje "ozvěnu" informace získanou z předchozích členů. Výhodou lineárního modelu je, že dobře funguje s nízkou informační kapacitou i pro složitější vzory.

Příklad: pro posloupnost a[n] = n*n platí,

a[n+1] = (n+1)^2 = n*n + 2n + 1
a[n-1] = (n-1)^2 = n*n - 2n + 1

a[n+1] = 2*a[n] - a[n-1] + 2

Obvyklý postup by dále pokračoval hledáním modelů s polynomiálním nebo radiálním jádrem, což ovšem vyžaduje mnohem větší množství vstupních dat.

Požadavky

• Python >= 3.5

Použití

python predict.py -h
usage: predict.py [-h] [--debug] input output

positional arguments:
  input       input file
  output      output file

optional arguments:
  -h, --help  show this help message and exit
  --debug     print debug info

Spuštění na přiloženém příkladu s debug výpisem

python predict.py in.txt out.txt --debug

Galerie

Program byl vytvořen v roce 2016.