Zadanie
Správna odpoveď na otázku z nadpisu: všetci okrem nás programátorov. To sa nedávno vypomstilo mladému programátorovi Jarkovi. Jedného dňa spoznal krásnu mladú slečnu, s ktorou si padli do oka. Keď sa večer lúčili, mal práve Jarko vybitý mobil, a tak mu slečna perom na ruku napísala svoje telefónne číslo. Keď však Jarko prišiel domov, s hrôzou zistil, že niektoré cifry nevie prečítať.
Úloha
V tejto úlohe sa budeme hrať s bitmapami v odtieňoch šedej. Bitmapy budú mať rozmer \(28\times 28\) a každý ich pixel bude mať hodnotu od 0 (čierna) po 255 (biela). Na každej bitmape bude rukou napísaná jedna z cifier od 0 po 9, a to čiernou farbou na bielom pozadí. Príklad niekoľkých takýchto bitmáp:
Môžeš si od nás stiahnuť zip archív (13 MB) obsahujúci nasledovné dobroty:
- vstupný súbor s \(50\,000\) bitmapami cifier
- obrázok s prvými \(10\,000\) ciframi z toho vstupného súboru
- výstupný súbor v ktorom je ku každej bitmape zo vstupu správna cifra
Tvojou úlohou je napísať a odovzdať program, ktorý zo vstupu načíta súbor s bitmapami cifier (v rovnakom formáte ako ukážkový, vrátane prázdnych riadkov medzi bitmapami) a na výstup vypíše postupnosť cifier na bitmapách (tiež v rovnakom formáte ako ukážkový).
Hodnotenie
Tvoje riešenie bude otestované na súbore s \(10\,000\) bitmapami cifier. (Tieto bitmapy nie sú medzi \(50\,000\) bitmapami z ukážkového vstupu. Všetkých \(60\,000\) bitmáp naozaj pochádza od ľudí.)
Nech \(x\) je počet bitmáp, pre ktoré dá tvoj program správnu odpoveď. Počet bodov, ktoré dostaneš, bude medián spomedzi \(0\), \(20\) a \((x-1000)/420\), zaokrúhlený na dve desatinné miesta. (Inými slovami, ak \(x\leq 1000\), dostaneš nulu, ak \(x\geq 9400\), dostaneš 20, a medzi týmito dvomi hranicami počet bodov rastie lineárne.)
Upozorňujeme, že tvoj program musí skončiť v časovom limite (30 sekúnd), inak nedostane body žiadne.
Čo už s takouto úlohou?
Jedna rozumná možnosť je nájsť spôsob ako z nej bezbolestne požmýkať čo najviac bodov. Celkom dosť sa toho dá dosiahnuť jednoduchými algoritmickými trikmi. Napríklad vieme spočítať počty uzavretých oblastí (8 má dve, 6 má jednu v dolnej časti, 4 a 9 majú jednu v hornej časti, 0 má jednu na celú výšku) a tiež počty miest kde sa čiara vetví/pretína. Takéto niečo nebude síce 100-percentne úspešné, ale bodov to dá dosť a kódi sa to ľahko.
Lepšiu úspešnosť by sme vedeli dostať výpočtom korelácie: zoberieme obrázok, ktorý sme dostali na vstupe, porovnáme ho s \(10\,000\) známymi bitmapami, a odpovieme podľa tej, na ktorú sa najviac podobá. Takýto prístup však má dva problémy: porovnávanie s \(10\,000\) bitmapami bude asi trošku pomalé, no a hlavne by sme potrebovali všetky napchať do zdrojového kódu nášho programu.
Oba tieto problémy vieme vyriešiť tak, že najskôr si doma natrénujeme náš program na obrázkoch, ktoré máme – inými slovami, nájdeme vhodnú funkciu, do ktorej keď vopcháme bitmapu tak vypadne číslo na nej. Odovzdaný program bude potom namiesto tých 13 MB dát, ktoré sme dostali, obsahovať len popis tejto funkcie.
Akú formu môže mať táto funkcia? Dalo by sa napríklad hľadať rôzne váhy, ktorými budeme násobiť farbu rôznych políčok. Existujú však aj omnoho lepšie možnosti. Jednou z nich je perceptrón – asi najjednoduchšia forma umelej neurónovej siete. Pri trénovaní perceptrónu v podstate hľadáme naraz 10 funkcií. Každá z nich sa pozerá na obrázok a snaží sa rozhodnúť, či to vyzerá alebo nevyzerá byť jedna z našich 10 cifier.
V skutočnosti sa dokonca presne tie dáta, ktoré boli použité v našej úlohe, používajú ako testovacie dáta pre porovnávanie úspešnosti rôznych prístupov strojového učenia. Najlepšie prístupy majú pri rozpoznávaní rovnakú úspešnosť ako ľudia – teda v princípe všetko rozpoznajú správne, až na pár vstupov u ktorých naozaj nie je jasné, čo tým chcel básnik povedať.
Viac sa o tom všetkom dočítate napríklad na tejto stránke.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.