Topic outline

  • General

    Collapse all Expand all

    Predavatelj: Blaž Zupan (blaz.zupan@fri.uni-lj.si)

    Asistenti: Marko Toplak (marko.toplak@fri.uni-lj.si), Martin Špendl, Jaka Kokošar

    Komunikacija v zvezi s predmetom, nalogami, snovjo in vsem ostalim poteka po Slacku, vabilo smo vam poslali dan pred predavanji. Če ga slučajno niste prejeli, za prijavo v kanal uporabite tole povezavo.

    Izvajanje predmeta pričnemo v sredo, 15. februarja 2023. O načinu izvajanja boste obveščeni pred prvimi predavanji po Slacku. Z izjemo prvih dveh predavanj bodo ta potekala v živo.

    Vaje pri predmetu bodo kombinacija konzultacij in (po potrebi) kratkih tečajev o praktičnih temah, ki bodo povezane z izvedbo domačih nalog. Na konzultacijah na začetku v skupini razpravljamo o snovi oziroma nalogah, kasneje pa delamo individualno. Govorilne ure so na voljo ob predhodnem dogovoru preko Slacka ali elektronske pošte.

    Ocenjevanje: Ocena predmeta je sestavljena iz ocen domačih nalog in pisnega izpita. Pozitivna ocena domačih nalog (študent je zbral več kot 60% možnih točk) je pogoj za pristop k izpitu. Ocena predmeta je pozitivna, če je pozitivna tako ocena domačih nalog kot pisnega izpita (zbranih več kot 60% možnih točk pri domačih nalogah in več kot 60% možnih točk pri izpitu). Bonusi iz domačih nalog se ne prenašajo na pisni izpit (in obratno). Združena ocena domačih nalog in izpita v odstotnih točkah, kjer je DN ocena domačih nalog in I ocena izpita v odstotnih točkah se izračuna po enačbi: ocena [odstotne točke] = max( min(DN+15, I), min(DN, I+15) ). Primer: 85% točk iz domačih nalog, 65% iz izpita, ocena je 80%. Še en primer: pisni izpit 90%, domače naloge 65%, ocena je 80%. Zaokrožene odstotne točke (celo število) se prevedejo v končno oceno pri predmetu. Do 60 točk: ocena 5, od 61 do 68: ocena 6, od 69 do 76: 7, od 77 do 84: 8, od 85 do 92: 9, od 93 točk: ocena 10. Vpis ocene bo potekal v izpitnem obdobju hkrati z ustnim izpitom, ki bo na voljo za vse, ki bi radi spremenili oceno.

    Domače naloge so dveh tipov:

    1. Dve večji nalogi, ki skupaj tvorita oceno iz nalog; predvidoma bosta to projekt in naloga, ki jo bomo organizirali kot tekmovanje. Domačo nalogo pripravite skrbno: na oceno vpliva tudi predstavitev rezultatov in urejenost izvorne kode (lažje razumljivo je v obeh primerih bolje). Če nalogo oddate prepozno, odštejemo 20 odstotnih točk. Maksimalna dovoljena zamuda so trije dnevi.

    2. Redne (krajše) naloge, ki jih ocenjujemo strojno, s testi. Za pristop k izpitu morate pravilno rešiti vse te naloge. Za vsako zamujeno nalogo se ocena nalog s prejšnje postavke (pod 1) zmanjša za 5 odstotnih točk. Prva naloga bo predstavljena že prvi teden.

    Naloge morajo biti vaše delo. Če odkrijemo prepisovanje, dobita tako avtor kot prepisovalec negativne točke, ki so po absolutni vrednosti enake maksimalnim možnim točkam za to nalogo. Za vsako odkrito prepisovanje krajše naloge se vaša ocena iz nalog s prve točke zmanjša za 20 odstotnih točk.

    Literatura

    Priporočena dodatna gradiva in tečaji (neobvezno, a za vsa radovedne):

    • Janez Demšar (2009) Python za programerje. Knjiga, namenjena tem, ki že znajo programirati v kakem drugem jeziku. Kdor ima raje verzijo na papirju, jo lahko kupi pod menzo za ceno cca dveh kosil.

    • Luciano Ramalho (2015) Fluent Python, O'Reilly Media. Lahko tudi Early Release 2014, ki je bil nekaj časa prosto dostopen na webu. Debela bukla, skoraj enciklopedija, a s super primeri in triki.

    • Tečaji s področij strojnega učenja, analize podatkov, nevronskih mrež dostopni na raznih MOOCih.

    Primeri izpitov

    • Izpiti iz prejšnjih let. Stari izpiti vsebujejo tudi naloge s področja podpore odločanja, ki ga v predmetu več ne obravnavamo. V šolskem letu 2021/22 smo prešli na nov tip izpita z večjim številom vprašanj in izbirnimi odgovori. Primere takih izpitov bomo objavili tu pred koncem semestra.

  • Odkrivanje skupin

    Odkrivanje skupin je eden od temeljnih postopkov, ki jih uporabljamo pri analizi podatkov. Odkrivamo lahko skupine uporabnikov glede na njihove uporabniške profile (uporaba storitev, nakupovalne košarice, vzorci obnašanja, stiki v družabnih omrežij), stvari (profili zanimanja uporabnikov, semantične podobnosti), dokumentov (glede na besedilo, ključne besede, zanimanje in ocene uporabnikov). Med številnimi algoritmi, ki se danes uporabljajo za odkrivanje skupin v podatkih, je prav gotovo najbolj znan algoritem hierarhičnega razvrščanja v skupine. Najbrž zaradi njegovi enostavnosti in pa zaradi tega, ker je njegove rezultate moč enostavno grafično predstaviti. Prav je, da s tem algoritmom pričnemo predmet. Literatura
    Video predstavitve izbranih tem
    Dodatni viri
    Podatki in koda

  • Metoda voditeljev

    Hierarhično gručenje lahko zaradi časovne in prostorske kompleksnosti algoritma uporabljamo samo na manjših množicah podatkov. Gručenje, ki ga lahko uporabimo tudi na velikih množicah podatkov uporablja metodo voditeljev, ki pa od uporabnika zahteva, da vnaprej poda število gruč. Iskanje primernega števila voditeljev lahko avtomatiziramo z oceno kvalitete razbitja. Ena od preprostejših mer uporablja pristop silhuete. Literatura
    Predavanja
    Dodatni viri
    Podatki in koda

  • Razvrščanje besedil

    Za obravnavo besedilnih dokumentov bomo uporabili trik. In sicer jih bomo za rešitev domače naloge predstavili s frekvenco k-terk, to je frekvenco k soslednih znakov, ki jih bomo dobili tako, da bomo z oknom širine k drseli po besedilu, znak po znak, in si zapisovali, kolikokrat smo pri tem naleteli na posamezno terko. Ker dokumente na ta način zapišemo s frekvencami terk, pravimo tudi, da je gre za spektralno predstavitev besedila. Literatura

    Koda s predavanja

    Dodatni viri
    • Programming Collective Intelligence, tretje poglavje (Document Filtering)
    • Language Trees and Zipping, eden prvih člankov, ki predlaga, da se za jezikovna drevesa da uporabljati tudi navadni program za zgoščevanje datotek (npr. gzip)
    • Quantitative analysis of culture using millions of digitized books, članek Ereza Liebermana in sodelavcev iz revije Science, kjer so analizirali angleška besedila od leta 1800 do 2000 in opazovali razvoj jezika, kulture in zgodovine.

  • Projekcije v nižjedimenzionalne prostore

    Za razumevanje strukture podatkov, razkrivanje podobnosti med primeri in odkrivanje skupin nam zalo koristijo prikazi podatkov na nizkodimenzionalnih kartah. Še najbolje kar točkovni prikaz podatkov v dveh dimenzijah. To mislimo na karte, kjer so primeri podani s točkami in kjer odnosi med primeri (oddaljenost, bližina) čimbolj ustrezajo odnosom med primeri v osnovnem, večdimenzionalnem prostoru. Ideja je torej zmanjšanje dimenzionalnosti podatkov in osnovnih n dimenzij na naprimer dve dimenziji. Na predavanju orišemo dva postopka, ki lahko vodita k konstrukciji takih projekcij. Prvi postopek je tehnika glavnih komponent (angl. PCA, principal component analysis), ki v osnovnem prostoru poišče smeri, ki najbolj razpenjajo podatke. Drugi postopek pa v prikazu v dveh dimenzijah skuša kar najbolj verno ohranjati razdalje med primeri, torej razdalje, ki jih izmerimo z neko mero razdalje v osnovnem n-dimenzionalnem prostoru. Slednji postopek se imenuje večrazredno lestvičenje (angl. MDS, multi-dimensional scaling). Mnogokrat nas namesto razdalj zanima samo ohranjanje bližine: primeri, ki so blizu v osnovnem prostoru naj bi bili blizu tudi v projekciji. Na predavanjih tehniko, ki implementira tako projekcijo in se imenuje t-SNE, samo omenimo in je ne izpeljemo, povdarimo pa, da predstavlja izboljšanje tehnike MDS.

    		 Literatura
    Predavanja
    Dodatni viri

  • Gradienti sestop

    Vrsta metod, ki sledi v nadaljevanju tega predmeta, temelji na optimizacije kriterijske funkcije. Se pravi, imamo podatke, določimo obliko našega modela ter zapišemo, kako ocenimo napako modela. Ta zapis imenujemo kriterijska funkcija. Konkretni model bo opisan s parametri, ki jih bomo izbrali tako, da bo pri izbranih parametrih kriterijska funkcija imela minimum. To bo tipično pomenilo, da bomo izbrali model, ki ima na učnih primerih najmanjšo napako. Parametre takih modelov tipično poiščemo z metodo gradientnega spusta. Pričnemo pri nekem začetnem izboru parametrov, pogledamo, kako je od teh odvisen odvod kriterijske funkcije, in popravimo parametre v nasprotni smeri gradienta. Na predavanjih smo si najprej pogledali, kako gradientni sestop uporabimo pri iskanju minimuma enoparametrske funkcije. Pristop potem razširimo na iskanja minimuma funkcije s poljubnim številom parametrov. Tu objavljamo kodo, ki smo jo izdelali na predavanju, prava uporaba tega pristopa pa sledi v poglavju o linearni regresiji. Predavanje
    Koda iz predavanj

  • Linearna regresija

    Problemom, kjer je cilj iz atributnega opisa primera napovedati vrednost ciljne zvezne spremenljivke (imenujemo jo tudi razred), pravimo regresijski problemi. Iz učnih podatkov, ki tokrat poleg atributnega opisa vsebujejo tudi podatek o razredu, tu gradimo regresijske napovedne modele. Pri predmetu se bomo z večino tehnik regresijskega modeliranja le seznanili. Pobližje spoznamo le linearno regresijo. Gre za sicer zelo enostaven model, ki pa ima skoraj vse, kar imajo veliki. Najprej je tu struktura modela, kjer pri linearni regresiji povemo, da gre za uteženo vsoto vrednosti atributov, kjer pravimo utežem parametri modela in jih moramo določiti iz podatkov. Določimo jih tako, da minimizirajo neko kriterijsko funkcijo. Pri predavanji to definiramo kot povprečno vrednost kvadrata napake. Kot postopek optimizacije, se pravi, iskanja optimalne vrednosti parametrov glede na izbrano kriterijsko funkcijo, uporabimo metodo gradientnega spusta. Literatura
    Predavanja
    Koda s predavanj
    Drugi viri

  • Regularizacija

    Linearna regresije se v primeru dovolj velikega števila atributov povsem prilagodi učni množici. Če je atributov dovolj, primerov pa dovolj malo, lahko celo dosežemo, da model linearne regresije točno napove vse vrednosti razredov primerov učne množice. Tako prilagojeni modeli pa tipično ne napovedujejo dobro na učni množici. Da vse to rešimo rabimo določiti mere za ocenjevanje točnosti, postopek, kako merimo točnost (množico primerov razbijemo na učno in testno množico) in postopek, kako preprečimo preveliko prileganje učni množici. Slednjega imenujemo regularizacija, in je v osnovni zelo enostavna: poleg napake na učni množici gradimo model linearne regresije tako, da skušamo minimizirati tudi vsoto kvadratov vrednosti parametrov modela. Postopek opišemo na primeru polinomske regresije. Literatura
    Predavaja

  • Vrednotenje uspešnosti regresijskih metod

    Napovedno točnost tehnik strojnega učenja vedno vrednotimo na testni množici, to je na podatkih, ki jih nismo uporabili pri gradnji modela. Vrednotimo kvantitativno, to je, izračunamo napovedno točnost, ki jo pridobimo z izbrano mero točnosti. Med številnimi merami, ki se uporabljajo za ocenjevanje uspešnosti regresijskih metod, predstavimo dve: koren povprečne kvadrirane napake (RMSE) in delež razložene variance (R2). Prednosti slednje je v razponu in interpretaciji: slabši modeli bodo imeli R2 blizu nič, boljši pa blizu 1. Za oceno teh mer tipično ne uporabimo eno samo testno množico, ampak mere izračunamo s ponavljanjem deljenja podatkov na učne in testne, kjer vsakič pridobimo za delitev specifično vrednost mere kvalitete in potem poročamo o povprečni vrednosti teh mer. V ta namen lahko uporabimo na primer tehniko prečnega preverjanja. Predavanja
    Koda s predavanj

  • Nekaj ostalih regresijskih tehnik

    Spoznali smo linearno regresijo, ki je morda najbolj osnovna regresijska tehnika, ni pa navadno najbolj točno in morda tudi ne najbolj uporabljana. V tem razdelku spoznamo še tri regresijske metode, ki vključujejo metodo najbližjih sosedov, regresijska drevesa in regresijske gozdove. Med naštetimi so slednji ti, ki tipično dosegajo najvišje napovedne točnosti. Spregovorimo tudi o nestabilnosti dreves, lenosti metode najbližjih sosedov, in pristopih z ansambli. Predavaja

  • Logistična regresija

    Uvrščanje v skupine ali klasifikacija predpostavlja, da je pri za vsak primer v naboru učnih primerov podan tudi razred. Cilj uvrščanja je iz učnih primerov zgraditi napovedni model, ki za nov primer in njegov opis v atributnem jeziku napove razred. Častnikarske novice tako na primer lahko pripadajo razredu šport, poslovne novice, razvedrilo. Uporabniki telekomunikacijskih storitev so lahko zvesti ali pa po določenem času zbežijo k drugemu ponudniku (angl. churn). Spletna stran je lahko dobro ali slabo obiskana. Izdelek v prodajalni je lahko prodajan z dobičkom ali pa izgubo.

    Logistično regresijo tu izpostavljamo kot prvo med klasifikacijskimi tehnikami, predvsem zaradi podobnosti z linearno regresijo, elegantnosti izpeljave tega modela in njene izboljšave s tehniko regularizacije. Nastavek za izpeljavo logistične regresije je logistična funkcija, ki preslika linearno kombinacijo parametrov (pomnoženih z vrednostmi vhodnih spremenljivk) v interval [0, 1]. Ko predpostavimo, da nam ta funkcija vrača verjetnosti ciljnega razreda danega primera, lahko za nabor učnih primerov zapišemo verjetje, iz njega pa izpeljemo kriterijsko funkcijo in njen gradient. Tako, kot pri linearni regresiji, gradient uporabimo pri iskanju najprimernejših parametrov modela, to je parametrov, pri katerih je, glede na dane učne primere, verjetje največje.

    		Literatura
    Koda s predavanj
    Predavanja

  • Najbližji sosedi, ocenjevanje pomembnosti atributov, klasifikacijska drevesa in gozdovi

    Klasifikacijska drevesa so podobna regresijskim: izberemo atribut, ki nam najbolje določi množice z različno porazdelitvijo razredov, in postopek ponavaljamo na podmnožicah, ki smo jih na ta način odkrili. Seveda bomo za klasifikacijo v ta nemen morali iznajti nove mere za informativnosti atributov (recimo, informacijski prispevek), a postopek gradnje drevesa bo isti. Prav tako ne bo večjih razlik pri gradnji klasifikacijskih gozdov. Literatura
    Predavanja

  • Mere za ocenjevanje točnosti klasifikacijskih modelov

    V tem delu predavanj odgovorimo, zakaj mera, ki jo imenujemo klasifikacijska točnost, ni najbolj primerna. In zakaj jo lahko dopolnimo z merami, kot sta občutljivost in specifičnost. In kako lahko ti dve meri, izmerjeni pri različnih pogojih, predstavimo v t.im. grafu ROC. In kako karakteristike v tem grafu predstavimo s karekteristično krivuljo ter povzamemo z AUC, torej z površino pod krivuljo ROC. Literatura
    Predavanja

  • Nomogrami in naivni Bayesov klasifikator

    Nomogram je grafična predstavitev relacij spremenljivk v enačbah. Tudi enostavni regresijski modeli so pravzaprav enačbe. Linearna regresija je utežena vsota atributov. Logistična regresija enako, samo da je potem rezultat te funkcije še dodatno preoblikovan z logistično funkcijo. Grafične predstavitve relacij so lahlo zanimive, saj jih lahko intuitivno "razumemo", razmišljamo o relacijah vizualno, in si na podlagi grafičnih izrisov predstavljamo, katere spremenljivke so pomembne in kako. Na predavanju uvedemo naivni Bayesov klasifikator, pokažemo, da se ta da predstaviti z nomogramom in namignemo na njegovo podobnost z logistično regresijo. Literatura
    Predavanja

  • Priporočanje

    K rešitvi vseh teh in podobnih dilem nam danes lahko danes pomagajo priporočilni sistemi. Spoznali bomo te, ki temeljijo na "modrosti možic" in jih označujemo s terminom "skupinsko filtriranje" (angl. collaborative filtering). Za vsako od priporočil, ki jih bomo zahtevali od sistema, bo ta pogledal, ali obstajajo nam podobni uporabniki in nam priporočil stvar, ki so ti dobro ocenili oziroma že izbrali. Prav tako bi lahko za priporočilo lahko pogledali, katere so podobne stvari tem, ki smo jih mi že izbrali. V obeh primerih bomo podobnosti (torej med uporabniki ali pa stvarmi) ocenili na podlagi zapisov preferenčnih podatkov vseh uporabnikov in stvari, ki jih lahko sistem priporoča.

    Pristopi priporočanja na podlagi merjenja podobnosti uporabnikov ali pa podobnosti stvari so precej osnovni in tipično ne dajo najboljše rezultate. Veliko boljše napovedi nam da pristop z matrično faktorizacijo. Tu za preferenčno matriko R{m x n} poiščemo približek v latentnem prostoru, tipično kot zmnožek veliko manjših matrik P{m x k} in Q{k x n}. Matrika P je zbirka latetnih profilov uporabnikov, R pa latetnih profilov stvari. Število k je stopnja faktorizacije in ustreza velikosti latentnih profilov. Tipično je R zelo redka matrika, P in Q pa sta polni. Iščemo tako P in Q, kjer je napaka ||R-PQ|| čim manjša. Za minimizacijo te napake lahko P in Q poiščemo z metodo gradientnega spusta. Ker sta P in Q polni matriki, lahko preko njunih produktov napovemo oceno za poljubno kombinacijo porabnika in stvari. Praktični pristopi k faktorizaciji, predobdelavi podatkov in regularizaciji so opisani v priloženi literaturi.

    To poglavje je kar pestro in uvaja številne nove prijeme, pri tem pa uporabi nekatere koncepte, ki smo jih že dobro spoznali. Med slednje predvsem sodijo tehnike merjenje razdalj (oziroma ocenjevanja podobnosti) in optimizacijski pristop z gradientnim spustom.     		Literatura
    Predavanja
    Dodatni viri

  • Povezovalna pravila in pogosti nabori stvari

    Gremo v trgovino, nakupimo nekaj stvari in plačamo. Moderne blagajne vsako tako transakcijo in skupino transakcij, torej vsebino nakupovalne košarice, vestno zabeležijo. Kakšne zanimive informacije lahko ponudnik - prodajalec izve iz takih podatkov? Kako te na primerno hiter način obdelamo? Učinkoviti algoritmi za tako analizo so bili načrtani v 90ih letih, danes pa raziskovalci predvsem delajo na njihovih specializacijah (časovne vrste, zvezni števci stvari, ipd.). Na predavanju bomo spoznali nekaj osnovnih prijemov, ki se ukvarjajo samo z vsebino košaric in ne s količino nakupljenih stvari. Odkrite zakonitosti v takih podatkih lahko predstavimo z naborom pogosto pojavljajočih se stvari v košaricah (angl. frequent itemsets) ali pa s seznamom povezovalnih pravil (angl. association rules). Odkrivanju obeh služi algoritem Apriori. Nabore stvari in pravila moramo tudi kvantitativno ovrednotiti, čemur služijo mere kot so podpora (angl. support), zaupanje (angl. confidence) in dvig (angl. lift).

    Tovrstne tehnike seveda niso namenjene samo analizi podatkov iz nakupovanj. Uporabne so tudi na področjih analiz spletnih strani, besedilnih dokumentov, v bioinformatiki, medicinski diagnostiki, astronomiji (prvi algoritmi na tem področju so bili uporabljeni prav na tej domeni), analizi podatkov iz družabnih omrežij in kjerkoli lahko primere predstavimo s skupino oznak.     		Literatura
    Predavanja
    Dodatni viri