algorithmic probability

Angol

Főnév

algorithmic probability (tsz. algorithmic probabilities)

(informatika, mesterséges intelligencia) Az algorithmic probability (magyarul: algoritmikus valószínűség) az információelmélet és algoritmikus tanulás egy fogalma, amely a valószínűséget köti össze a legrövidebb programok hosszával egy adott adatsor előállítására.

Mi az az algorithmic probability?

Egy adott adat vagy megfigyelés valószínűségét méri annak alapján, hogy mennyire valószínű, hogy egy véletlenszerűen generált program hozza létre azt egy univerzális Turing-gépen.
Más szóval: minél rövidebb (egyszerűbb) az a program, ami előállítja az adott adatot, annál nagyobb az adat algoritmikus valószínűsége.

Formalizálás

Ha ${\textstyle x}$ egy adott adat, akkor az algoritmikus valószínűsége ${\textstyle P(x)}$ megközelítőleg:

$P(x)=\sum _{p:U(p)=x}2^{-|p|}$

ahol

${\textstyle U}$ egy univerzális Turing-gép,
${\textstyle p}$ egy olyan program, amely az ${\textstyle x}$ adatot állítja elő,
${\textstyle |p|}$ a program hossza (bitben).

Ez azt jelenti, hogy összeadjuk az összes olyan program hozzájárulását, amelyek ${\textstyle x}$ -et generálják, és a hozzájárulásuk fordított arányban van a program hosszával (rövidebb program nagyobb súlyú).

Kapcsolódó fogalmak

Kolmogorov komplexitás: A legrövidebb program hossza, amely előállítja az adott adatot.
Solomonoff-féle indukció: Az algoritmikus valószínűség elméleti alapja az univerzális előrejelzésnek.

Miért fontos?

Egy alapelv az automatikus tanulásban és predikcióban, amely az egyszerűség elvén (Occam borotvája) alapul.
Az algoritmikus valószínűség formalizálja azt a gondolatot, hogy a egyszerűbb magyarázatok a valószínűbbek.
Alapja az univerzális prediktív modelleknek, ahol nem ismerjük előre a környezet működését.

Összefoglaló

Az algorithmic probability azt méri, hogy egy adat mennyire valószínű, hogy előáll egy véletlenszerű program segítségével egy univerzális számítógépen, és ezzel az egyszerűség és a valószínűség szoros kapcsolatát fejezi ki.

További információk

algorithmic probability - Szótár.net (en-hu)
algorithmic probability - Sztaki (en-hu)
algorithmic probability - Merriam–Webster
algorithmic probability - Cambridge
algorithmic probability - WordNet
algorithmic probability - Яндекс (en-ru)
algorithmic probability - Google (en-hu)
algorithmic probability - Wikidata
algorithmic probability - Wikipédia (angol)