Výpočetní modelování Statistické modely Simulace Shrnutí Modelování výukových dat, obtížnosti problémů Radek Pelánek Výpočetní modelování Statistické modely Simulace Shrnutí Kontext odlišné od zbytku předmětu – nikoliv „standardní pojmy , ale aktuální výzkum na FI osobní zkušenosti výzkumná skupina Adaptive Learning http://www.fi.muni.cz/adaptivelearning/ Výpočetní modelování Statistické modely Simulace Shrnutí Účel přednášky ilustrace různých přístupů v jedné oblasti: výpočetní statistické ilustrace praktického kontextu modelování: sběr dat volby při návrhu modelů, parametry evaluace aplikace Výpočetní modelování Statistické modely Simulace Shrnutí Otázky Co ovlivňuje obtížnost problémů? Jak predikovat obtížnost problémů? Jak detekovat schopnosti studentů? aplikace: výukové systémy Výpočetní modelování Statistické modely Simulace Shrnutí Obtížnost a výpočetní modelování případové studie Sokoban, Sudoku: sběr dat analýzy dat, hledání metrik obtížnosti výpočetní modely Výpočetní modelování Statistické modely Simulace Shrnutí Sokoban Sokoban 4 min 49 min Výpočetní modelování Statistické modely Simulace Shrnutí Sokoban Sběr dat vlastní web logování všech tahů 35 levelů, vždy 4 bedny cca 2000 odehraných her, data robustní Výpočetní modelování Statistické modely Simulace Shrnutí Sokoban Výsledky – čas Výpočetní modelování Statistické modely Simulace Shrnutí Sokoban Stavový prostor – čas strávený lidmi Výpočetní modelování Statistické modely Simulace Shrnutí Sokoban Výpočetní model dynamické procházení stavového prostoru snaha simulovat chování člověka (nikoliv myšlení) jednoduchý model, kombinace dvou tendencí „dobrý nápad – ideální posun směrem k cíli bloudění – náhoda čím blíž k cíli, tím méně náhody Výpočetní modelování Statistické modely Simulace Shrnutí Sokoban Lidé a model Výpočetní modelování Statistické modely Simulace Shrnutí Sokoban Metriky obtížnosti Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Sudoku Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Sběr dat fed-sudoku.eu: cca 1000 zadání, časy pro 100 řešitelů data od webmastera sudoku.org.uk: cca 1000 zadání, cca 1000 řešitelů, jen průměrný čas stažené skriptem z webu czech-sudoku.com: použito cca 20 zadání logy her (každý tah) stažené z webu / od webmastera Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Naivní metrika: počet čísel v zadání Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Výpočetní model „logické techniky pro odvození další pozice (hidden single, naked single, hidden pair, X-wing, ...) náhodně vybere jedno z možných doplnění a pak pokračuje Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Výpočetní model: příklad Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Výpočetní modely: principy běžný přístup: hodně logických technik, mnoho parametrů náš model: málo technik, málo parametrů snazší vyhodnocení lepší přenositelnost lepší „vhled Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Jednoduchý výpočetní model jen dvě základní logické techniky (hidden single, naked single) selže jednoduchá logika ⇒ prohledávání hledá pole, kde je potřeba nejmenší počet kroků k vyvrácení špatných kandidátů aproximace složitějších logických technik Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Model vs lidé: srovnání pro konkrétní hru Pozn. Možná aplikace – usnadnění řešení, generování nápověd (aplikace tohoto principu na výukové úlohy – DP Martin Vardan) Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Model vs lidé: srovnání pro konkrétní hru Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Počet možných „tahů a obtížnost Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Výsledky: kombinovaná metrika Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Výsledky koeficient determinace r2 fed-sudoku.eu sudoku.org.uk metric all simple all simple number of givens 6% 5% 2% 12% Serate 49% 30% 74% 28% Serate LM 61% 36% 75% 43% Fowler’s 47% 28% 76% 41% Refutation sum 47% – 70% – Dependency 45% 54% 49% 62% Combined (RD) 54% – 78% – Combined (SFRD) 66% 57% 91% 66% Výpočetní modelování Statistické modely Simulace Shrnutí Sudoku Shrnutí zkušeností – Sokoban, Sudoku „statické metriky nefungují „dynamické výpočetní modely jednoduché, abstraktní modely, málo parametrů, fungují docela dobře nejsou úplně přímočaré – spousta „dobrých nápadů nefungovala metrika „vzorek lidí – i pro úlohy s jednoduchými pravidly těžké překonat Výpočetní modelování Statistické modely Simulace Shrnutí Tutor Tutor web tutor.fi.muni.cz současně: sběr dat o řešení využití dat pro predikce, doporučování úloh predikce pomocí statistického modelu – model, který není vůbec specifický pro konkrétní úlohu inspirace: doporučující systémy (recommender systems), např. Amazon, Netflix asi 30 úloh (logické, matematické, informatické) Výpočetní modelování Statistické modely Simulace Shrnutí Tutor Tutor: úlohy tutor.fi.muni.cz Výpočetní modelování Statistické modely Simulace Shrnutí Tutor Tutor: předpovědi tutor.fi.muni.cz Výpočetní modelování Statistické modely Simulace Shrnutí Tutor Model obtížnosti úloh log(T) θ b a c -3 -2 -1 0 1 2 Výpočetní modelování Statistické modely Simulace Shrnutí Tutor Odhad parametrů dostupná data: uživatel i vyřešil úlohu j v čase tij potřebujeme současně odhadnout: schopnosti uživatelů θ parametry problémů a, b, c metody strojového učení (stochastic gradient descent) analogické doporučujícím systémům (např. Netflix – hodnocení filmů) vyhodnocení: úspěšnost predikcí (RMSE) Výpočetní modelování Statistické modely Simulace Shrnutí Tutor vysoká diskriminace vysoká náhodnost stejná základní obtížnost "na jistotu" Výpočetní modelování Statistické modely Simulace Shrnutí Slepé mapy Slepé mapy slepemapy.cz státy, města, pohoří, . . . základní data: uživatel, místo, správnost odpovědi model: predikuje pravděpodobnost správné odpovědi variace na Elo systém (hodnocení hráčů, šachy) adaptabilní chování na základě predikcí modelu podobné principy použity u: anatom.cz, matmat.cz, poznavackaprirody.cz a dalších Výpočetní modelování Statistické modely Simulace Shrnutí Slepé mapy Slepé mapy – obtížnost států model využívá mimo jiné: „globální znalost studenta , „obtížnost států Výpočetní modelování Statistické modely Simulace Shrnutí Výukové systémy – simulace adaptivní výukový systém: model pro predikci úspěšnosti algoritmus pro výběr otázky studenti zpětné vazby, netriviální chování využití simulace (simulovaní studenti) dopad různých nastavení systému zkoumání zpětné vazby mezi modelem a algoritmem Výpočetní modelování Statistické modely Simulace Shrnutí Výpočetní vs statistické modely výpočetní simulace chování člověka specifické pro problém, vhled využitelné pro nápovědy náročná příprava statistické popisné metody strojového učení povrchnější, menší vhled snadnější použití, široce aplikovatelné Výpočetní modelování Statistické modely Simulace Shrnutí Úvaha o technikách a problémech Když máte v ruce kladivo, všechno na světě vám připadá jako hřebík . . . „technika → problém „problém → technika Výpočetní modelování Statistické modely Simulace Shrnutí Shrnutí modely: výpočetní, statistické kvantitativní vyhodnocení nad daty aplikace modelů v reálných systémech možnost zapojení (např. BP, DP) – máme spousty zajímavých dat a nezodpovězených otázek ...