13. decembra 2024
PAC

Leslie Valiant: Probably approximately correct

Ľudia si občas predstavujú informatikov ako ľudí, ktorí non-stop sedia za počítačom a niečo programujú. Oni však často sedia – napríklad aj za počítačom – a premýšľajú, čo vlastne vôbec počítače dokážu spočítať. Ktoré úlohy sú ťažké, ale zvládnuteľné, a ktoré veľmi ťažké a len tak sa vyriešiť nedajú, treba vymyslieť nejakú fintu.

Ľudská myseľ má pred sebou takúto výpočtovo náročnú úlohu. Má k dispozícii obmedzený čas na pochopenie sveta, ktorý je však prakticky neobmedzený.

Valiantova kniha opisuje jeho koncept z roku 1984, ktorý hovorí, ako túto obtiaž preklenúť. Musíme poľaviť z nárokov – nič nevieme s istotou a nevieme to popísať dokonale presne. V tomto kontexte sa pozerá na učenie ľudské, strojové a dokonca aj na samotnú evolúciu. Obšírne diskutuje „PAC learning“, teda koncept „pravdepodobne približne správneho učenia.“

Kniha mi pripomínala Quantum computing since Democritus od Scotta Aaronsona, ktorá je tiež z veľkej časti o výpočtovej komplexnosti. Číta sa mi podobne pomaly. Aj si žiada sústredenie a aj je v nej veľa podnetov na premýšľanie. Jedna ochutnávka, takmer len tak medzi riadkami autor utrúsi, že „ak by boli (Chomského) regulárne jazyky PAC naučiteľné, tak by boli RSA šifry zlomiteľné v polynomiálnom čase.“ Chvíľu trvá, kým sa z toho človek vysomári.

Kniha má tak 170 relatívne malých strán a čítam ju už skoro mesiac – to vravím ako kompliment. Ak vás zaujíma veľmi teoretický pohľad na učenie a ste ochotní knihe venovať istú mentálnu kapacitu, bude sa vám páčiť.

[Samuel]

Pridaj komentár