Komprimácia metódami umelej inteligencie

V mnohých aplikáciách výpočtovej techniky je v dnešnej dobe bežne používaná komprimácia údajov. Softvérové firmy...


V mnohých aplikáciách výpočtovej techniky je v dnešnej dobe bežne používaná
komprimácia údajov. Softvérové firmy sa predháňajú v tvorbe stále nových
štandardov na ukladanie a prenos statického obrazu, videa alebo hudby.
Niektoré metódy komprimácie údajov sú jednoduché a ich princíp je viac-menej
intuitívne pochopiteíný, zatiaí čo iné sú zložité a skrýva sa za nimi rozsiahla
teória. Mnoho metód komprimácie je chránených patentmi a sú predmetom
priemyselného tajomstva. Niekoíko metód komprimácie údajov je založených aj na
metódach umelej inteligencie: umelých neurónových sieťach, fuzzy systémoch,
fraktáloch či iterovaných funkciách.

Neurónové siete
Umelé neurónové siete dokážu svojou štruktúrou a parametrami reprezentovať
rozličné údaje. Tieto údaje sa do nich zakódujú v procese učenia, kedy sa
rozmanitými algoritmami upravuje štruktúra a parametre siete tak, aby vytvorili
model reprezentujúci požadované údaje. Existuje viacero základných spÖsobov
učenia sa umelých neurónových sietí. V prvom rade ide o kontrolované učenie
(angl. supervised learning), pri ktorom sa umelej neurónovej sieti predkladajú
vstupy spolu s požadovanými výstupmi a štruktúra a parametre siete sa učiacim
algoritmom upravujú tak, aby neurónová sieť predkladané vstupy čím ďalej tým
lepšie mapovala na príslušné výstupy.
Tento prístup k učeniu umelej neurónovej siete však nemožno použiť vždy. V
niektorých prípadoch sú k dispozícii iba vstupy do siete, ale nie k nim
zodpovedajúce výstupy. Na spracovanie údajov takéhoto typu sa používajú umelé
neurónové siete s odlišnou štruktúrou a s odlišným spÖsobom učenia, ktorý sa
nazýva nekontrolované učenie (angl. unsupervised learning) a mÖže sa použiť
napríklad na zhlukovanie, alebo čo je pre komprimáciu údajov zaujímavejšie na
výber hlavných komponentov zo vstupných údajov.
Princíp komprimácie údajov umelou neurónovou sieťou je v tom, že táto sa
použije v úlohe auto-asociatívnej pamäte, t.j. že sa jej budú predkladať
vstupy, a tieto sa budú očakávať aj na jej výstupe. Signál po prechode
neurónovou sieťou by sa teda nemal zmeniť, výstup by mal byť totožný so
vstupom. Komprimácia údajov sa dosiahne tým, že počas prechodu neurónovou
sieťou musí signál prejsť určitým úzkym miestom, kde dÖjde k jeho redukcii (viď
obrázok).
Úlohou prvej časti umelej neurónovej siete po komprimačnú vrstvu je
vyabstrahovať z údajov najdÖležitejšie črty, ktoré budú uložené ako
komprimované údaje. Údaje by mali byť vybrané tak, aby došlo k čo najmenšej
informačnej strate a aby z týchto redukovaných údajov mohli byť čo najlepšie
rekonštruované pÖvodné údaje.
Rekonštrukcia údajov je následne úlohou druhej časti umelej neurónovej siete,
ktorá je trénovaná tak, aby z redukovaných údajov vytvorila opäť údaje pÖvodné.
Je dÖležité dodať, že ide o stratovú komprimáciu údajov a pÖvodné údaje sú
rekonštruované iba čiastočne. Čitateíom určite neuniklo, že aj keď je na
obrázku nakreslená jedna neurónová sieť, je jej funkcia veími dobre
dekomponovateíná na dve časti: výber príznakov z údajov a vytvorenie siete na
ich opätovnú rekonštrukciu. Už na prvý pohíad sa jedná o odlišné úlohy a na ich
riešenie sa mÖžu použiť (a zvyčajne sa aj používajú) rozličné druhy umelých
neurónových sietí.
V prvej časti sa používajú neurónové siete s nekontrolovaným učením, pretože
nie je jasné, aké príznaky sa z údajov majú vyberať (keby to bolo známe, nebol
by tento proces potrebný). Keď sa však tieto príznaky už získajú, je jasné, aké
údaje sa z nich majú rekonštruovať (pÖvodné vstupné údaje), a preto sa v druhej
časti mÖže použiť umelá neurónová sieť s kontrolovaným učením. Výber príznakov
a učenie siete na ich rekonštrukciu dokonca ani nemusí prebiehať súčasne, ale
sekvenčne.
Najznámejším typom uvedenej umelej neurónovej siete na stratovú komprimáciu
údajov je tzv. sieť typu counterpropagation, ktorej autorom je Američan Robert
Hecht-Nielsen, ktorý v prvej časti siete použil konkurenčné a kooperačné učenie
(angl. competitive and cooperation learning), zatiaí čo v druhej časti siete
pÖvodné údaje rekonštruoval algoritmom so spätným šírením chyby (angl.
backpropagation of error, skrátene backprop). Výhodou tejto kombinácie je aj
to, že prvú časť siete možno upraviť tak, aby bol výstup "komprimačnej" vrstvy
binárny, a teda na uloženie komprimovaného údaja z jedného umelého neurónu v
tejto vrstve postačuje jeden bit pre každú zo vzoriek, zatiaí čo pÖvodný signál
mohol byť reprezentovaný reálnymi číslami.
Alternatívnym spÖsobom implementácie takejto siete mÖže byť použitie Ojovho
adaptačného pravidla zmeny váh v prvej časti neurónovej siete, pomocou ktorého
sa robí výber hlavných komponentov z údajov v štatistickom zmysle. Ďalšou
možnosťou je použiť súčasne jedinú umelú neurónovú sieť s kontrolovaným učením
na obe úlohy, pričom sa komprimované údaje budú odoberať z jednej jej "zúženej"
vrstvy. Posledne menovaný prístup sa však neosvedčil.

Fuzzy technológie
Hoci sa použitie fuzzy technológií zvyčajne spája s pravidlovými inferenčnými
systémami, existujú aj aplikácie, kde sa práca s neurčitosťou pomocou fuzzy
prístupov používa "nepravidlovým" spÖsobom. Komprimácia údajov a digitálne
spracovanie signálov (angl. digital signal processing) mÖžu byť príkladom
takýchto aplikácií.
Taliani Bereta a Tettamanzi vypracovali postup kombinujúci stochastické
optimalizačné metódy (konkrétne evolučné algoritmy) a fuzzy systémy pri
komprimácii signálov. Signál teoreticky íubovoínej dimenzie sa najskÖr pomocou
komplikovanej funkcie príslušnosti (angl. membership function) rozloží na
časti. Pre každú z týchto častí sa namiesto všetkých jej hodnÖt uloží jediná
hodnota. Pri dekomprimácii sa z uložených hodnÖt rekonštruuje pÖvodný signál
pomocou inej dekomprimačnej funkcie príslušnosti.
Príklad jednorozmerného signálu komprimovaného touto metódou je ďalšom na
obrázku. Porovnaním červeného priebehu hodnÖt pÖvodného signálu a žltého
priebehu dekomprimovaného signálu je vidieť, že došlo k určitej informačnej
strate (signál nie je rekonštruovaný presne, ale len približne) a k vyhladeniu
signálu. Kompresia teda opäť nie je bezstratová, ale na druhej strane možno
uvažovať o použití tejto metódy na odstraňovanie šumu zo signálu. Možnosť
spojiť komprimáciu signálu a jeho predspracovanie vyhladením mÖže byť v
niektorých prípadoch veími príťažlivá.
Uvedený prístup má však aj svoje silné obmedzenia. Ako je pri použití fuzzy
systémov zvykom, problémom je zvyčajne ich počiatočné nastavenie. V tomto
prípade je problematické nájsť vhodné funkcie príslušnosti na komprimáciu a
dekomprimáciu signálu a to tým viac, čím je spracovávaný signál zložitejší. Ich
návrh sa preto rieši pomocou algoritmov stochastickej optimalizácie, konkrétne
spomínaní autori použili genetické algoritmy.
Takto získané funkcie príslušnosti boli značne odlišné od tých, ktoré by
pravdepodobne našiel íudský expert: boli multimodál-ne (obsahovali viacero
extrémov) a medzi funkciou príslušnosti na komprimáciu a na dekomprimáciu nebol
žiadny na prvý pohíad zjavný vzťah, ako by sa možno dalo predpokladať z ich
vzájomne komplementárnej funkcie, čo pravdepodobne súvisí s ich zložitosťou.
Podobným problémom ako návrh fuzzy systému trpí aj prístup ku komprimácii
údajov pomocou umelej neurónovej siete, ktorý je spomenutý vyššie. Ak je totiž
dopredu daná štruktúra tejto siete, je dopredu daný aj komprimačný pomer
(množstvo komprimovaných údajov je dané množstvom pÖvodných údajov, pomerom
medzi vstupnou a komprimačnou vrstvou a veíkosťou siete potrebnej na ich
dekomprimáciu) a učením siete sa upravuje len stratovosť komprimácie.
Riešením mÖže byť použitie sofistikovanejších neurónových sietí: adaptívnych
samoorganizúcich sa máp (adaptive self-organizing maps) v prvej časti siete
určenej na extrakciu príznakov, alebo orezávanie (pruning, optimal brain
damage) či postupná výstavba (tzv. kaskádna korelácia, angl. cascade
corelation) druhej časti umelej neurónovej siete určenej na dekomprimáciu.
Alternatívou je opäť použitie stochastických optimalizačných techník, čo je
však časovo veími náročné.

Fraktálová komprimácia
Ďalšou zaujímavou metódou komprimácie, ktorá je známa najmä z oblasti
spracovania obrazu, je fraktálová komprimácia. Hoci sa používa najmä na
redukciu objemu obrazových údajov, principiálne možno touto metódou komprimovať
aj jednorozmerné signály rovnako ako aj viac ako dvojrozmerné.
Fraktálová komprimácia funguje na princípe híadania navzájom podobných častí
signálu, ktoré sa ale mÖžu líšiť svojou veíkosťou a otočením. Tento spÖsob
možno chápať aj ako zovšeobecnenie komprimačných metód založených na
frekvenčnom výskyte znakov (napr. Huffmanovo kódovanie) na prácu s celými
vzormi. Ak sa takéto opakujúce sa vzory v komprimovaných údajoch nachádzajú,
stačí ich zakódovať raz a doplniť údajmi o tých častiach obrazu, ktoré sa z
nich dajú vytvoriť preškálovaním, posunutím či otočením (a samozrejme aj
íubovoínou kombináciou týchto transformácií).
Zatiaí čo rekonštrukcia obrazu komprimovaného fraktálovou komprimáciou je
rýchla, výpočtovo náročným problémom je jeho komprimácia. Pri nej je potrebné
híadať podobnosť medzi mnohými možnými podčasťami obrazu. Počet porovnaní
dramaticky vzrastá aj možnými preškálovaniami, posunutiami a otočeniami
jednotlivých častí.
Komprimačné pomery dosahované touto technológiou sú však veími síubné: zvyčajne
sa dosahuje kvalita i kompresný pomer porovnateíný s komprimáciou obrazu do
formátu jpeg, v niektorých prípadoch fraktálová komprimácia vedie buď kvalitou
komprimovaného obrazu alebo komprimačným pomerom. Obrazové súbory komprimované
fraktálovou metódou majú prípony fif.
Heuristiky
Zatiaí čo pri bezstratovej komprimácii údajov má hlavné slovo matematika a
štatistika, oblasť stratovej komprimácie ponecháva priestor aj na rÖzne
alternatívne metódy. Nachádzajú tu uplatnenie metódy umelej inteligencie, ktoré
hoci stoja na pevných základoch matematiky predstavujú z híadiska riešenia
problémových úloh skÖr heuristiky ako algoritmy (z híadiska toho ako fungujú sú
to algoritmy, ale zvyčajne obsahujú nejakú stochastickú zložku a pod.). A ako
vidieť, aj v rámci metód umelej inteligencie možno k riešeniu tej istej úlohy
pristupovať viacerými diametrálne odlišnými spÖsobmi.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.