Faktoriální kód - Factorial code

Většina datových sad v reálném světě se skládá z datových vektorů, jejichž jednotlivé komponenty nejsou statisticky nezávislé. Jinými slovy, znalost hodnoty prvku poskytne informace o hodnotě prvků v datovém vektoru. Pokud k tomu dojde, může být žádoucí vytvořit a faktoriální kód údajů, tj. e., nová vektorová hodnota zastoupení každého datového vektoru tak, aby byl jednoznačně kódován výsledným kódovým vektorem (bezztrátové kódování), ale kódové komponenty jsou statisticky nezávislé.

Později učení pod dohledem obvykle funguje mnohem lépe, když jsou surová vstupní data nejprve přeložena do takového faktoriálního kódu. Předpokládejme například, že konečným cílem je klasifikace obrázků s vysoce redundantními pixely. A naivní Bayesův klasifikátor předpokládá, že pixely jsou statisticky nezávislé náhodné proměnné a proto nedokáží dosáhnout dobrých výsledků. Pokud jsou data nejprve kódována faktoriálním způsobem, pak naivní Bayesův klasifikátor dosáhne svého optimální výkon (srovnej Schmidhuber et al. 1996).

Chcete-li vytvořit faktoriální kódy, Horace Barlow a spolupracovníci navrhli minimalizovat součet bit entropie kódových komponent binární kódy (1989). Jürgen Schmidhuber (1992) problém přeformulovali z hlediska prediktorů a binárních hodnot Vlastnosti detektory, přičemž každý přijímá nezpracovaná data jako vstup. Pro každý detektor existuje prediktor, který vidí ostatní detektory a učí se předpovídat výstup vlastního detektoru v reakci na různé vstupní vektory nebo obrázky. Ale každý detektor používá a strojové učení algoritmus, aby se stal co nejvíce nepředvídatelným. The globální optimum z toho Objektivní funkce odpovídá faktoriálovému kódu zastoupenému distribuovaným způsobem napříč výstupy detektorů funkcí.

Painsky, Rosset a Feder (2016, 2017) dále tento problém studovali v kontextu analýza nezávislých komponent přes konečné velikosti abecedy. Prostřednictvím řady vět ukazují, že problém faktoriálního kódování lze přesně vyřešit pomocí algoritmu větveného a vázaného vyhledávacího stromu nebo těsně aproximovat řadou lineárních problémů. Kromě toho zavádějí jednoduchou transformaci (jmenovitě permutaci řádu), která poskytuje chamtivou, ale velmi efektivní aproximaci optimálního řešení. Prakticky ukazují, že při pečlivé implementaci lze dosáhnout příznivých vlastností permutace řádu v asymptoticky optimální výpočetní složitosti. Důležité je, že poskytují teoretické záruky, které ukazují, že i když ne každý náhodný vektor lze efektivně rozložit na nezávislé komponenty, většina vektorů se rozkládá velmi dobře (tj. S malými stálými náklady), jak se dimenze zvětšuje. Kromě toho demonstrují použití faktoriálních kódů ke kompresi dat ve více instalacích (2017).

Viz také

Reference

  • Horace Barlow T. P. Kaushal a G. J. Mitchison. Nalezení minimálních entropických kódů. Neural Computation, 1: 412-423, 1989.
  • Jürgen Schmidhuber. Učení faktoriálových kódů minimalizací předvídatelnosti. Neural Computation, 4 (6): 863-879, 1992
  • J. Schmidhuber a M. Eldracher a B. Foltin. Semilineární minimalizace předvídatelnosti vytváří známé detektory funkcí. Neural Computation, 8 (4): 773-786, 1996
  • A. Painsky, S. Rosset a M. Feder. Zobecněná analýza nezávislých komponent přes konečné abecedy. IEEE Transactions on Information Theory, 62 (2): 1038-1053, 2016
  • A. Painsky, S. Rosset a M. Feder. Velké abecední kódování zdroje pomocí analýzy nezávislých komponent. Transakce IEEE o teorii informací, 63 (10): 6514 - 6529, 2017