Teorija Flashcards
Slabosti preiskovanja v globino v primerjavi s preiskovanjem v širino
Lahko zaide v neskončne veje in ne najde rešitve. Ni optimalno, saj ne zagotavlja najkrajše poti do rešitve.
Prednost preiskovanja v globino v primerjavi s širinskim preiskovanjem
Manjša prostorska zahtevnost, saj hrani le pot do trenutnega vozlišča.
Podobnosti med algoritmom širinskega preiskovanja in iterativnim poglabljanjem
Oba algoritma sta popolna in zagotavljata, da bosta našla rešitev, če ta obstaja.
Razlike med algoritmom širinskega preiskovanja in iterativnim poglabljanjem
Širinsko preiskovanje uporablja vrsto in hkrati razišče vsa vozlišča na isti globini. Iterativno poglabljanje kombinira širinsko in globinsko preiskovanje, ponavlja globinsko preiskovanje z vedno večjo dovoljeno globino.
Definicija optimistične hevristične funkcije h v algoritmu A*
Hevristična funkcija h je optimistična, če nikoli ne preceni dejanskih stroškov poti do cilja (h(n) ≤ h*(n)).
Zakaj smo zainteresirani za optimistične hevristične funkcije h v algoritmu A*
Optimistične funkcije zagotavljajo, da je A* popoln in optimalen, saj vedno najde najkrajšo pot.
Kaj pomeni pretirano prilagajanje (angl. overfitting) v strojnem učenju
Pretirano prilagajanje pomeni, da model preveč natančno sledi učnim podatkom, vključno s šumom in nepomembnimi vzorci.
Kaj so nezaželene posledice pretiranega prilagajanja
Model ima slabo generalizacijo na novih podatkih, kar vodi do slabše napovedne točnosti.
Kako se manifestirajo težave pri učenju odločitvenih dreves iz šumnih podatkov
Odločitvena drevesa se lahko naučijo šumnih vzorcev, kar vodi do pretiranega prilagajanja in slabe napovedne točnosti.
Kaj je osnovna ideja pri učenju dreves iz šumnih podatkov
Uporaba metod za obrezovanje dreves in tehnike, kot so omejitev globine drevesa, da se zmanjšajo vplivi šuma.
Na kaj se nanaša beseda »kratkovidnost« (angl. myopy) v gradnji odločitvenih dreves
Kratkovidnost pomeni, da odločitvena drevesa sprejemajo odločitve na podlagi lokalno optimalnih kriterijev, ki niso nujno globalno optimalni.
Za kaj se uporabljata metoda »prečno preverjanje« (angl. cross validation) in metoda »leave-one-out« v strojnem učenju
Prečno preverjanje in leave-one-out metoda se uporabljata za ocenjevanje napovedne točnosti modelov.
Postopek prečnega preverjanja (k-fold cross validation)
Podatki se razdelijo na k podmnožic, model se trenira k-krat, vsakič z drugo podmnožico kot testno.
Postopek leave-one-out
Posebna oblika prečnega preverjanja, kjer je k enako številu podatkovnih točk, kar pomeni, da se vsakič uporabi ena podatkovna točka kot testna.
Kaj pomeni parameter k v metodi prečnega preverjanja
Parameter k določa število podmnožic, v katere se razdelijo podatki za prečno preverjanje.
Bayesova formula za izračun pogojne verjetnosti P(A|B)
P(A|B) = \frac{P(B|A)P(A)}{P(B)}
Bayesova formula za izračun P(A|BC)
P(A|BC) = \frac{P(C|A)P(B|A)P(A)}{P(B)P(C)}
Naivna Bayesova formula za izračun P(A|BC)
P(A|BC) \approx P(A) \cdot P(B|A) \cdot P(C|A)
V čem je naivna Bayesova formula naivna
Predpostavlja neodvisnost med atributi, kar pogosto ni resnično.
Prednost naivne Bayesove formule
Preprosta in učinkovita za računanje ter pogosto daje dobre rezultate kljub poenostavitvi.
Kaj pomeni “optimistična hevristična funkcija”
Hevristična funkcija je optimistična, če je njena ocena stroškov do cilja manjša ali enaka dejanskim stroškom.
Zakaj smo pogosto zainteresirani za optimistične hevristične funkcije
Takšne funkcije zagotavljajo optimalnost in učinkovitost algoritmov, kot je A*.
Katera hevristična funkcija deluje bolje v A* algoritmu, če je h1(N) < h2(N)
A* bo deloval bolje s hevristiko h2, ker boljša ocena (bližje dejanskim stroškom) vodi do manj preiskovanih vozlišč in hitrejšega dosega cilja.
Kolikokrat več časa bo program potreboval za iskanje druge rešitve, če ima uniformno vejanje b = 5, prvo rešitev na globini 9 in drugo na globini 12
Razmerje T2:T1 je približno enako b^{12-9} = 5^3 = 125. Torej bo program potreboval približno 125-krat več časa.
Oceni na grobo, koliko je vejanje b, če program najde prvo rešitev v 3 sek., drugo pa po 4 minutah, ki je za 4 korake daljša
Če je razlika v globini 4 korake in traja 4 minute (240 sekund) po prvih 3 sekundah, razmerje časa je 240/3 = 80. Torej, b^4 \approx 80, kar daje b \approx 3.
Prostorska in časovna zahtevnost algoritmov preiskovanja v globino, v širino in iterativnega poglabljanja
Globinsko preiskovanje: Prostorska: O(d), Časovna: O(b^d). Širinsko preiskovanje: Prostorska: O(b^d), Časovna: O(b^d). Iterativno poglabljanje: Prostorska: O(d), Časovna: O(b^d).
Prednosti in pomanjkljivosti globinskega preiskovanja
Prednosti: Nizka prostorska zahtevnost. Pomanjkljivosti: Lahko ne najde rešitve, če gre v neskončno globino.
Prednosti in pomanjkljivosti širinskega preiskovanja
Prednosti: Zagotavlja najkrajšo pot, če obstaja rešitev. Pomanjkljivosti: Visoka prostorska zahtevnost.
Prednosti in pomanjkljivosti iterativnega poglabljanja
Prednosti: Kombinira prednosti obeh, nizka prostorska zahtevnost in zagotavlja najkrajšo pot. Pomanjkljivosti: Višja časovna zahtevnost zaradi ponovnega iskanja.
Ali je manhattanska razdalja optimistična hevristika za igre 8 ali 15 kvadratov
Da, manhattanska razdalja je optimistična hevristika, ker nikoli ne preceni dejanskih stroškov premikov ploščic.
Relativni informacijski dobitek atributa
Relativni informacijski dobitek upošteva razmerje med informacijskim dobitkom in entropijo atributa, kar omogoča primerjavo atributov z različnimi razponi vrednosti.
Kaj je entropija?
Entropija je mera negotovosti ali neurejenosti v podatkih, ki kvantificira povprečno količino informacij potrebnih za opisovanje podatkovnih vrednosti.
Formula za izračun entropije
H(X) = -\sum_{i=1}^n P(x_i) \log P(x_i)
Kaj je informacijski dobitek atributa
Informacijski dobitek je mera zmanjšanja entropije, ki pove, koliko dodatnih informacij določen atribut prinese za razločevanje med različnimi razredi v podatkovnem naboru.
Kaj je pristranskost (bias) v strojnem učenju
Pristranost v strojnem učenju se nanaša na sistematična odstopanja, kjer model favorizira določene napovedi zaradi predpostavk, vgrajenih v model ali podatke.
Kaj je jezikovna pristranskost (language bias)
Jezikovna pristranost se nanaša na pristranskost, ki izhaja iz predpostavk, povezanih z obliko ali strukturo jezika, uporabljeno za opis hipotez ali modelov, kar lahko omeji izražanje določenih rešitev.
Pomen angleške besede »overfitting« v kontekstu strojnega učenja
Pretirano prilagajanje: Model se preveč prilagodi učnim podatkom in izgubi sposobnost generalizacije na nove podatke.
Neugodne posledice šuma v učnih podatkih pri učenju odločitvenih dreves
Model se lahko nauči napačnih vzorcev, kar vodi do pretiranega prilagajanja in slabe napovedne točnosti.
Metoda ocenjevanja klasifikacijske točnosti v algoritmih za rezanje odločitvenih dreves
Prečno preverjanje: Podatke razdelimo na več podmnožic, treniramo model na vsaki podmnožici in ocenimo točnost na preostalih.
Postopek prečnega preverjanja (k-fold cross validation)
Podatke razdelimo na k delov, model treniramo k-krat, pri čemer vsakič uporabimo drug del za testiranje in ostale za treniranje.
Postopek leave-one-out
Posebna oblika prečnega preverjanja, kjer je k enako številu podatkovnih točk, vsakič pustimo eno točko za testiranje in ostale za treniranje. Uporaba leave-one-out je smiselna pri majhnih podatkovnih množicah za maksimalno izkoriščanje razpoložljivih podatkov.
Bayesova formula za verjetnost razreda R pri vrednostih atributov A1, A2, A3
P(R|A1=1, A2=2, A3=3) = \frac{P(A1=1, A2=2, A3=3|R)P(R)}{P(A1=1, A2=2, A3=3)}
Razlika med Bayesovim in naivnim Bayesovim klasifikatorjem
Bayesov klasifikator upošteva vse odvisnosti med atributi, medtem ko naivni Bayesov predpostavlja njihovo neodvisnost.
Naivni Bayesov klasifikator za verjetnost razreda R pri vrednostih atributov A1, A2, A3
P(R|A1=1, A2=2, A3=3) \approx P(R) \cdot P(A1=1|R) \cdot P(A2=2|R) \cdot P(A3=3|R)
Primerjava Bayesovega in naivnega Bayesovega klasifikatorja
Bayesov klasifikator je natančnejši, a bolj zapleten in zahteva več podatkov. Naivni Bayesov je preprostejši in hitrejši, vendar temelji na močni predpostavki neodvisnosti atributov. Bayesov klasifikator je bolj zanesljiv, če so podatki zadostni in predpostavke držijo, medtem ko je naivni Bayesov bolj robusten pri omejenih podatkih.
