NAI.md

Pytania kontrolne z wykładów

Wykład 1A

Wymienić aspekty inteligencji

• uczenie się (na przykładach)
• rozwiązywanie złożonych problemów
• adaptacja (do zmiennych warunków)
• wnioskowanie (na podstawie wiedzy i reguł)
• percepcja (widzenie, słyszenie)
• wiedza (reprezentacja)
• uogólnianie (zaobserwowanych przykładów)
• komunikacja (język)
• mobilność(przemieszczanie dizycznych obiektów)
• planowanie
• filozoficzny
• etyczny
• teoretyczny

Test Turinga

A i B komunikują się językiem naturalnym. Jeden jest człowiekim, drugi maszyną. C obserwuje i próbuje rozróżnić człowieka od maszyny.

Silna AI/słaba AI oraz cechy

Słaba AI

Wąskie aspekty, dotyczy rozwiązywania wąskich, konkretnych problemów. Charakteryzuje ją adaptacyjność, uczenie, wnioskowanie.

Silna AI

Charakteryzuje się świadomością, kreatywnością, auto-refleksją(znajomość własnych limitów), ewolucja.

Elementy historii

• prehistoria (przed 1960 - pierwsze nowoczesne komputery)
• romantyzm (60-65) - optymistyczna wiara, że sztuczna inteligencja dorówna ludzkiej w 10 lat...
• ciemność (65-70) - pesymizm
• renesans (70-75) - powstają pierwsze praktyczne systemy eksperckie
• współpraca (75-80) - badania interdyscyplinarne: nauki ścisłe, przyrodnicze, humanistyczne; środowiska akademickie i przemysłowe
• komercjalizacja (80-)

Zastosowania współczesne AI

Medycyna, reklama, asystenci, proste boty, antyfraudy, przewidywanie pogody.

Pozytywne i negatywne aspekty rozwoju AI dla człowieka

Optymalizacja zadań, unicestwienie ludzkości, tu można sporo popierdzielić.

Jaki jest cel sztucznej inteligencji?

Budowa maszyn, oprogramowania i algorytmów przejawiających cechy inteligentne.

Dyscypliny powiązane z AI

• Informatyka
• Biologia
• Finanse
• Matematyka
• Lingwistyka
• robotyka

Wymień 2-3 podejścia do rozwiązywania/modelowania zagadnień AI

• symboliczne (logika, reprezentacja)
• statystyczne (dane, prawdopodobieństwo)
• obliczeniowe (przeszukiwanie)

Wymień 4-5 spektakularnych sukcesów AI

• smartfony
• wygrana w GO
• wyszukiwarki
• gry
• inteligentne miasta
• inteligentne budynki

Wymień po 2 potencjalnie pozytywne i negatywne aspekty rozwoju AI

• Generowanie pracy bez udziału człowieka
• Optymalizacja procesów

• Zniszczenie ludzkości
• Limity = ściana w rozwoju

Wykład 1B

Motywacja dla uczenia maszynowego

Stanowi rozwiązanie dla tych intuicyjnych problemów, polega nasprawieniu by komputery:

• uczyły się na przykładach
• stosowały do “rozumienia” świata hierarchię pojęć definiowalnych w relacji do innych pojęć
• Podejście takie pozwala uniknąć problemu dokładnego specyfikowania wiedzy.

Krótka charakteryzacja głębokiego uczenia maszynowego

Jest to podejście do AI, odmiana uczenia maszynowego, które umożliwia hierarchiczne modelowanie bardziej złożonych pojęć za pomocą prostszych na podstawie dostarczonych danych treningowych.

Jakie są przyczyny niedawnego odnowienia zainteresowania głębokim uczeniem maszynowym?

• coraz większa ilość dostępnych danych treningowych
• coraz większe możliwości sprzętu obliczeniowego, dzięki czemu można skutecznie implementować duże i złożone modele, co było technicznie niemożliwe wcześniej

Wymień 2-3 powody mocy obliczeniowej mózgu ludzkiego, która jest wciąż trudna do osiągnięcia przez implementacje sztucznych sieci neuronowych.

• łączna liczba neuronów
• liczba połączeń pomiędzy neuronami

Wykład 2A

Motywacje eksploracji danych

• Danych jest dużo, są interesujące ale trudne do analizy przez człowieka
• Są w formie elektronicznej

Przykładowe typy zadań uczenia maszynowego

• grupowanie obiektów podobnych
• rozpoznawanie istotnych wzorców w danych
• klasyfikacja nowo-obserwowanych przypadków
• przewidywanie przyszłości na podstawie poprzednich obserwacji
• wykrywanie trendów w danych (np. wczesne wykrycie kryzysów ekonomicznych, itp.)

Fazy w uczeniu maszynowym

1. zbieranie danych
2. czyszczenie i wstępne przetworzenie danych
3. (tylko w uczeniu z nadzorem) podział na zbiór treningowy i testowy
4. uczenie się na danych
5. ewaluacja (iteracyjnie)
6. używanie systemu do zadań

Co to jest tablica decyzyjna? Jaka ma formę, co reprezentują kolumny a co wiersze?

1. obserwacje (przypadki) = wiersze
2. atrybuty = kolumny

Służy analizie zbiorów danych przy uczeniu z nadzorem.

Krótko scharakteryzuj uczenie z nadzorem

1. podawanie systemowi prawidłowych rozwiązań w tzw zbiorze danych treningowych (sygnał uczący)
2. system uczy się(dane treningowe) uogólnić sposób rozwiązania zadania poprzez automatyczne wykrycie związków pomiędzy danymi, a prawidłowymi rozwiązaniami(automatyczne budowanie modelu prawidłowego rozwiązania)
3. automatycznie wyuczony model jest stosowany do nowych przypadków (nie trenujących)

Krótko scharakteryzuj uczenie bez nadzoru

Brak sygnału uczącego. Wykrycie pewnych związków między obiektami i atrybutami (np. grupowanie, reguły asocjacyjne)

Typy atrybutów

• numeryczne albo kategoryczne
• uporządkowane lub nie
• przeskalowanie, transformacje atrybutów
• kwantyzacja (zamiana z numerycznych na kategoryczne)

Co to jest atrybut decyzyjny?

Wyszczególniony atrybut w tabeli decyzyjnej. Podana w nim jest decyzja na temat danego wiersza z danymi.

Co to jest zbiór treningowy?

Zbiór danych na których uczy się model podając mu odpowiedzi, w celu pomocy w nauczeniu go związków pomiędzy danymi atrybutami.

Co to jest zbiór testowy?

Zbiór danych przy uczeniu z nadzorem na którym testuje się algorytm wyuczony na zbiorze treningowym.

Na czym polega zadanie grupowania (ang. clustering)?

Należy podzielić wszystkie badane przypadki na grupy obiektów podobnych do siebie (wewnątrz każdej grupy), przy czym obiekty z różnych grup powinny się jak najbardziej różnić między sobą. Nie wiemy jaka jest faktyczna kategoria odpowiadajaca każdej grupie - nie mamy przykładów.

Wykład 2B

Co to są miary ewaluacyjne i do czego służą?

• Dokładność (ang. accuracy)
• Precyzja i Pełność (Precision, Recall) (tylko 2 klasy)
• F-miara (tylko 2 klasy)
• Macierz omyłek (ang. Confusion Matrix) (dowolna liczba klas)

Opisz co to jest macierz omyłek

Kwadratowa macierz K × K, gdzie K jest liczbą klas. Każdy wiersz odpowiada faktycznej klasie obiektów. Każda kolumna odpowiada klasie wskazanej przez klasyfikator (być może nieprawidłowo) Każda komórka (i, j) zawiera liczbę przypadków (lub procent) obiektów klasy i zaklasyfikowanych jako j.

Opisz co oznaczają wielkości: TP,FP, TN, FN

T-true, F-false, P-positive, N-negative.

Co to jest dokładność?

procent przykładów testowych, dla których algorytm prawidłowo rozwiązał problem (ma wady np. dla niezrównoważonych klas):

(TP+TN)/all

Jaka jest wada dokładności (miary ewaluacyjnej)?

Sama w sobie dokładność jest słabą miarą. NP. 99% czasu system przecipożąrowy wykrywa brak pożaru.

Jaka jest definicja precyzji?

P = TP/(TP+FP)

To proporcja przypadków zaklasyfikowanych jako pozytywne i faktycznie pozytywnych do wszystkich zaklasyfikowanych jako pozytywne.

Jaka jest definicja pełności?

To proporcja przypadków zaklasyfikowanych jako pozytywne i faktycznie pozytywnych do wszystkich faktycznie pozytywnych

Co to jest F-miara?

     2·P·R
F = -------
      P+R

Jest to średnia harmoniczna P i R. Intuicyjnie, jeśli F-miara jest wysoka, to obie miary P i R muszą być wysokie.

Jaka jest zaleta F-miary?

Trudno jest w praktyce zbudować klasyfikator maksymalizujący równocześnie P i R.

Zadanie 2b-1

Zbiór testowy zawiera 60 przypadków (obserwacji) dotyczących danych pacjentów chorych na pewną chorobę i poddanych pewnej kuracji. Każdy pacjent w wyniku kuracji wyzdrowiał (klasa "pozytywna") lub nie (klasa "negatywna").

Załóżmy, że w celu wspomagania decyzji czy poddac pacjenta w/w kuracji, zbudowano klasyfikator, który na podstawie pewnych atrybutów dotyczących pacjentów próbuje przewidzieć, czy kuracja dla danego pacjenta będzie skuteczna (wyzdrowieje), czy też nie.

Dla 36 pacjentów ze zbioru testowego system przewidział, że kuracja będzie skuteczna, przy czym w 30 przypadkach była to faktycznie prawda. Ponadto system prawidłowo przewidział, że w 4 przypadkach kuracja będzie nieskuteczna.

Stwórz macierz omyłek

oblicz: a) TP, FN, FP, FN b) dokładność klasyfikatora c) precyzję d) pełność e) F-miarę

(UWAGA: proszę podać wynik w postaci ułamka zwykłego maksymalnie uproszczonego)

Odpowiedź

macierz omyłek: zaklasyfikowane jako -> p | n

faktycznie p: 30 | 20

faktycznie n: 6 | 4

a) TP = 30, FN = 20, FP = 6, TN = 4

b) dokładność: (30+4)/60 = 17/30

c) precyzja: P = 30/(30+6) = 5/6

d) pełność: R = 30/(30+20) = 3/5

e) F-miara: F = 2PR/(P+R) = (25/63/5)/(5/6 + 3/5) = (6/6)/(25+18/30) = 30/43

Wykład 3

Wymień 3 ważne własności neuronu

Opisz krótko matematyczny model Perceptronu

Slajd

Jak obliczane jest wyjście Perceptronu?

Perceptron jest aktywowany (y=1) tylko jeśli iloczyn skalarny WTX (wartość ta jest często nazywana net) przekracza wartość progu Θ

Opisz krótko interpretację geometryczną działania Perceptronu

Rozważmy n-wymiarową przestrzeń wektorów wejściowych(każdy jej element jest potencjalnym wektorem wejściowym X ∈ R^n). Wektor wag W ∈ R^njest wektorem normalnym hiperpłaszczyźnie decyzyjnej, która rozgranicza wektory na aktywujące i nieaktywujące. Perceptron aktywuje si¦ (y=1) tylko jeśli wektor wejść X jest po tej samej stronie hiperpªaszczyzny decyzyjnej co wektor wag W. Osiągana jest tym większa wartość net (W T X) im bliżej wektor X jest wektora W , jest zerowa gdy są prostopadłe i ujemna gdy są po przeciwnych stronach.

Jak Perceptron może działać jako klasyfikator

Może działąć gdy mamy dokładnie 2 klasy. Może jednak rozróżniać jedynie obszary, które są liniowo separowalne. W szczególności, nie jest zdolny do modelowania np. funkcji logicznej XOR.

Wymień przynajmniej 2 ograniczenia działania Perceptronu jako klasyfikatora

• Działa liniowo, klasyfikuje maksymalnie dwie klasy.
• Może korzystać jedynie z AND oraz OR

Opisz regułę delta uczenia perceptronu (wzór + interpretacja geometryczna)

Podajemy perceptronowi przykłady uczące ze zbioru treningowego po kolei. Po każdym przykładzie, jeśli odpowiedź (wyjście perceptronu) jest niewłaściwa, modyfikujemy wagi w następujący sposób:

W0 = W + (d − y)αX

d - decyzja (wyj±cie) prawidªowa y - faktyczna decyzja 0 < α < 1 - parametr (stała uczenia) wpływający na intensywność uczenia

Neuron i jego ważne własności

• Transmituje sygnał będący funkcją sygnałów z wejść, po jego przetworzeniu wewnątrz komórki, na wyjście podłączone do wejść innych neuronów.
• Nieliniowe przetwarzanie sygnału: wyjście nie jest po prostu sumą sygnałów z wejść
• Dynamicznie modyfikuje czułość (wagi) połączeń z innymi neuronami (przez synapsy), dzięki czemu może wzmacniać lub osłabiać połączenia z innymi neuronami, w zależności od wykonywanego zadania.

interpretacja geometryczna reguły Delta

Docelowo, wektor wag powinien być możliwie blisko przykładów pozytywnych (y=1). Stąd, wzór:

W 0 = W + (d − y)αX

Przyciąga wektor W do pozytywnych przykładów X jeśli odpowiedź jest 0 zamiast 1 (za słaba aktywacja) odpycha wektor W od negatywnych przykładów X jeśli odpowiedź jest 1 zamiast 0 (zbyt mocna aktywacja) Zwykle, nauczenie perceptronu wymaga wielokrotnego przejścia całego zbioru treningowego, zanim się nauczy odpowiednich wag i progu.

Wykład 3 - zadanie

Perceptron:

Dany jest wektor wejściowy p=(0,1,-2) oraz wektor wag perceptronu q=(2,-2,1) i próg r=2 dyskretnego perceptronu unipolarnego. a) oblicz wyjście tego perceptronu b) zakładając, że wyjście jest nieprawidłowe, oblicz, używając reguły uczenia delta, zmodyfikowany wektor wag, zakładając, że stała ucząca wynosci a=1. c) czy wartość progu podniesie się, czy obniży?

Rozwiązanie

Perceptron:

Dany jest wektor wejściowy p=(0,1,-2) oraz wektor wag perceptronu q=(2,-2,1) i próg r=2 dyskretnego perceptronu unipolarnego. a) oblicz wyjście tego perceptronu b) zakładając, że wyjście jest nieprawidłowe, oblicz, używając reguły uczenia delta, zmodyfikowany wektor wag, zakładając, że stała ucząca wynosci a=1. c) czy wartość progu podniesie się, czy obniży?

a) net = 02 + 1(-2) + (-2)1 = -4 r = 2 net < r wiec perceptron nie aktywuje sie, wyjscie wynosi y = 0 b) jezeli zalozymy, ze wyjscie y = 0 jest nieprawidlowe, to prawidlowe wyjscie powinno byc d = 1. w = q = (2,-2,1) x = p = (0,1,-2) Ze wzoru na regule uczenia delta, nowe wagi musza wyniesc: w' = w + a(d-y)x = (2,-2,1) + 1(1-0)*(0,1,-2) = (2,-2,1) + (0,1,-2) = (2,-1,-1) c) perceptron nie aktywuje sie, a powinien, wiec prog musi sie obnizyc

Słowo Seby

sprawa jest prosta

masz perceptron (czyli tak naprawdę funkcję matematyczną)

perceptron ma jakieś wejścia i jedno wyjście

każde wejście to po prostu jakaś liczba

wyjście to też liczba

trzeba pamiętać że nie każde wejście jest tak samo istotne w wyniku dlatego każde wejście x ma przypisaną wagę w ta waga to też liczba która po prostu mówi jaki wpływ na wynik będzie miało dane wejście (na przykład 0 oznacza brak wpływu) teraz jeśli chcemy obliczyć wyjście perceptronu to po prostu robimy tak:

każde wejscie mnożymy przez jego wagę, potem wszystkie wyniki sumujemy i mamy jakąś liczbę którą stosujemy w funkcji aktywacji do sprawdzenia czy perceptron ma się aktywować czy nie- decyduje o tym funkcja która sprawdza czy ten nasz wynik mnożenia wektora wag przez wektor wejść jest większy od pewnego progu który ustalimy:

W x X > P,

a po prostym przekształceniu mamy:

W x X - P > 0

i jeśli to jest prawdziwe to perceptron się aktywuje, a jak nie to nie

ten 'x' oznacza mnożenie wektorów. Na slajdach jest T (którego tutaj nie napiszę jako indeks górny dlatego użyłem 'x'). To 'T' oznacza, że wektor W transponujemy i dopiero mnożymy przez wektor X, bo inaczej nie da się pomnożyć dwóch wektorów. Ten 'x' tutaj oznacza to samo - mnożenie wektorów czyli tak naprawdę macierzy jednowymiarowych, a wiadomo że jak mnożymy macierze to ta po lewej musi mieć tyle kolumn co ta po prawej wierszy, dlatego tutaj wektor wag "stawiamy pionowo" i dopiero przystępujemy do mnożenia przez "poziomy" wektor wag

Wykład 4A

Dyskretny perceptron i jego ograniczenia

Pojedyczny perceptron może być użyty jako klasyfikator w przypadku najwyżej 2 klas Nawet dla 2 klas są przypadki, które nie mog¡ być rozwiązane przez pojedynczy perceptron. Ma też pewne oczywiste ograniczenia: może rozróżniać tylko rejony liniowo-separowalne w przestrzeni atrybutów.

Inne funkcje aktywacji

Ze względu na typ numeryczny wartości wyjścia:

• dyskretny (liczba całkowita): może być użyty do klasyfikacji
• ciągły (liczba zmiennoprzecinkowa): może być użyty do regresji (lub również klasyfikacji)

Ze względu na maksymalną (aktywacja) i minimalną (brak aktywacji) zwracaną wartość:

• bipolarny (dyskretny: {0,1}, ciągły: [0,1])
• unipolarny (dyskretny: {-1,1}, ciągły: [-1,1])

Niech x oznacza wektor wejściowy, net = Ei wi xi − Θ (y oznacza wyjście neuronu)

Najczęściej używane funkcje aktywacji:

• funkcja signum(znak): y = signum(net)

• funkcja progowa: y = bx > 0e

• funkcja liniowa(surowe wyjście): y = net

• funkcja sigmoidalna:

  a) unipolarna - y = 1/((1+e)^−net)

  b) bipolarna - y = (2/((1+e)^−net)) - 1

  Funkcja może być wyposażona w parametr stromości y = 1/((1+e)^(−λ * net))

Wielo-klasyfikacja przy pomocy jedno-warstwowej sieci neuronowej

Każdy pojedyczny perceptron może klasyfikować do 2 klas. Gdy mamy wiecej niż 2 klasy, możemy użyć całej warstwy perceptronów aby dokonywać klasyfikacji. Typowa architektura jest następująca:

• każde wejście jest podłączone do każdego perceptrona
• wyjścia poszczególnych perceptronów są agregowane aby wyznaczyć wyjście całej takiej 1-warstwowej sieci.

W przypadku 2 klas, wyjście perceptronu stanowi¡cego klasyfikator jest naturalnie interpretowane:

• maximum aktywacji: klasa 1
• minimum aktywacji: klasa 0

W przypadku wielu klas, klasyfikator w formie 1-warstwowej sieci neuronów ma wiele wyjść. Istnieją 2 główne podejścia do architektury i reprezentacji wyjścia sieci:

• lokalne
• globalne

Lokalna:

Liczba perceptronów jest dokładnie taka sama jak liczba klas. Każdy perceptron jest trenowany do aktywacji dla dokładnie jednej klasy. Prawidłowe wyjście takiej architektury jest następujące:

Dokładnie jeden perceptron jest aktywny (i wyznacza decyzję klasyfikatora) a pozostałe są niekatywne.

Globalna

W tym przypadku liczba perceptronów nie jest dokładnie okreslona (ale może być mniejsza niż w lokalnej). Decyzja klasyfikacyjna wyznaczana jest na podstawie kombinacji wyjść wszystkich perceptronów.

Uwaga: skoro każdy perceptron ma 2 możliwe wyjścia to dla K klas potrzeba nie mniej niż log2K perceptronów (ale często więcej). Lokalna reprezentacja ma tą zaletę, że jeśli jest możliwa to łatwiej ją wytrenować. Z drugiej strony, potrzebuje więcej perceptronów i nie zawsze można ją stosowa¢.

Zamiast dyskretnych perceptronów w warstwie można użyć też c¡ągłych (o ciągłej funkcji aktywacji). Wtedy podejście może być następujące:

• każdy ciągły neuron jest trenowany aby maksymalnie się aktywować tylko dla swojej klasy
• decyzja klasyfikacyjna podjęta jest na podstawie tego neurona, który się maksymalnie aktywuje

Takie podejście jest bardziej odporne na niepożądane sytuacje niż klasyczna dyskretna reprezentacja lokalna, ponieważ praktycznie każde wyjście może być interpretowalne. (zredukowany jest problem jednoczesnej aktywacji wielu neuronów)

Miary ewaluacyjne dla klasyfikacji

• Dokładność (ang. accuracy)
• Precyzja i Pełność (Precision, Recall) (tylko 2 klasy)
• F-miara (tylko 2 klasy)
• Macierz omyłek (ang. Confusion Matrix) (dowolna liczba klas)

Wykład 4B

Wykład 5

model typu black box

W sieciach neuronowych dane są prezentowane w postaci wag połaczen i wartosci progów poszczególnych neuronów

reprezentacja wiedzy

Czytelniejsz reguły decyzyjne i drzewa decyzyjne. ich zapis wygląda dokładnie tak jak ich nazwy gdzie reguły to predykaty np a==true && b=='costam'. Drzewa decyzyjne mogą być automatycznie generowane ze zbiorów danych za pomocą algorytmu ID3.

enropia

Funckja przyrostu informacji(zdziwienie)

reguły decyzyjne i algorytmy (idea)

Reguły mogą stanowic duzo bardziej zwarta forme reprezentacji wiedzy niz tabela decyzyjna. Przykladem algorytmu automatycznie generujacego reguly decyzyjne jest algorytm pokrywania (ang. covering).

IF tear production rate = reduced THEN recommendation = NONE

zlozonosc modelu

Im bardziej zlozony (zawierajacy wiecej detali) jest model, tym ma teoretycznie wieksze mozliwosci w odwzorowaniu niuansów uczonego pojecia, ale niesie to tez ryzyko tzw. przetrenowania czyli dostosowania sie modelu na sztywno do danych trenujacych, bez uogólnienia wiedzy na nieznane przypadki. Zlozonosc nie powinna byc wiec za wysoka. Zwykle mozemy kontrolowac zlozonosc modelu.

Na przyklad:

• w sieciach neuronowych, zlozonosc modelu rosnie wraz z liczba neuronów.
• w drzewach decyzyjnych: wraz z liczb¡ wezlów drzewa
• w regulach decyzyjnych: wraz z liczb¡ regul

Model powinien by¢ jak najprostszy.

wybór i ocena modelu

Dwa istotne problemy:

• wybór odpowiedniego modelu i stopnia jego zlozonosci
• ocena jakosci modelu (przewidzenie jak dobrze model bedzie dzialal na faktycznie nieznanych przypadkach)

Jakosc oceniana na danych uczacych, bedzie zawsze zawyzona.

Jesli danych treningowych jest wystarczajaco duzo, mozna podzielic dane na trzy oddzielne zbiory:

• treningowy (do uczenia sie)
• walidacyjny (wybór modelu i kontrola stopnia zlozonosci)
• testowy (zachowany do momentu ostatecznej oceny modelu) Nie ma ogólnej reguly na proporcje wielkosci, moze byc np. 50%, 25%, 25%, respectively

przetrenowanie i jego ominiecie

Model na sztywno pod dane. Zapobiegaja temu lepsze algorytmy rozwoju, prostszy model danych.

walidacja krzyzowa

Pozwala jednocze±nie osi¡gn¡¢ 2 pozornie sprzeczne cele:

• uczyc calego zbioru treningowego
• nie oceniac systemu na przykladach ze zbioru treningowego

Dzielimy zbiór treningowy na N rozlacznych czesci (w sposób losowy). Bierzemy jedna czesc jako zbiór ewaluacyjny a pozostale N-1 jako treningowe. Powtarzamy N razy (dla kazdej czesci). Łączna Proporcja błędu to usrednione proporcje ze wszystkich N. Najczesciej bierze sie N=10 (ang. 10-fold cross-validation).

Wykład 5B

Wykład 6

Wykład 7

Algorytm k-NN (k nearest neighbours).

Jest to algorytm klasyfikujący działający na danych numerycznych (tzn wszystkie atrybuty są numeryczne). k jest liczbą naturalną dodatnią, parametrem algorytmu (wlasciwie hiperparametrem).

Algorytm jest bardzo prosty i specyficzny, gdyż nie posiada fazy uczenia modelu - modelem jest surowy zbiór treningowy, a wszystkie obliczenia dokonywane są w momencie klasyfikacji.

Działanie jest następujące: Zbiór treningowy to zbiór wektorów p-wymiarowych reprezentujących przypadki uczące, każdy z nich przyporządkowany jest do pewnej klasy (kategorii).

Dla wektora x, który ma być zaklasyfikowany, wyznaczane jest k najbliższych mu wektorów ze zbioru treningowego i zostaje on zaklasyfikowany do takiej klasy, której etykieta przeważa pośród k najbliższych wektorów.

Np. jeśli k = 4 i najbliższe 4 wektory ze zbioru treningowego przynależą odpowiednio do klas X,Y,X,Z, to wektor klasyfikowany x zostanie przyporządkowany do klasy X. Remisy rozsztrzygane są dowolnie.

Odległość euklidesowa wektorów x i y to pierwiastek 2 stopnia z sumy kwadratów różnic odpowiednich współrzędnych wektorów x i y.

np: x = (1,2), y = (-1,3)

to odległość euklidesowa x i y: d(x,y) = sqrt( (1-(-1))^2 + (2-3)^2 ) = sqrt(4+1) = sqrt(5) (sqrt: pierwiastek kwadratowy)

Zadanie KNN

Algorytm k-NN

Mając podane 6 wektorów należących do 3 kategorii (klas): klasa A: a = (1,1,0) c = (2,1,-2) klasa B: b = (0,1,-1) d = (1,0,0) klasa C: e = (1,-1,3) f = (1,-1,4)

Zaklasyfikuj wektor x = (1,0,4) używając algorytmu k-NN (k nearest neighbours) dla k = 3 i zwykłej odległości euklidesowej. Zademonstruj wszystkie niezbedne obliczenia.

Rozwiązanie

odpowiedz: x bedzie nalezal do kategorii C

Rozwiązanie zadania dotyczącego k-NN: (ponizej, d(x,y) bedzie oznaczalo odleglosc euklidesowa pomiedzy wektorami x,y)

Obliczamy odleglosci wektora x do wszystkich wektorow w zbiorze danych: d(x,a) = 4.12 (=sqrt(17)) d(x,b) = 5.19 (=sqrt(27)) d(x,c) = 6.16 (=sqrt(38)) d(x,d) = 4 (=sqrt(16)) d(x,e) = 1.41 (=sqrt(2)) d(x,f) = 1

a wiec najblizsze 3 wektory do wektora x to beda: wektor f (z klasy C) wektor e (z klasy C) wektor d (z klasy B)

poniewaz wsrod 3 najblizszych wektorowi x wektorow najliczniejsza klase stanowi klasa C, wektor x jest zaklasyfikowany do klasy C

UWAGA praktyczna: zauwazmy, ze przy braku kalkulatorow, prosciej bedzie liczyc kwadraty odleglosci (czyli wzor euklidesa bez wyciagania z nich pierwiastka), nie zmieni to faktu, ktore wektory sa najblizsze

Zadanie z klasyfikacji za pomoca klasyfikatora "naive Bayes"

Potraktuj zalaczona tabele decyzyjna w nastepujacy sposob: a) zbior treningowy: pierwsze 12 wierszy tabeli b) przypadek do zaklasyfikowania: wiersz 13 tabeli (zignoruj atrybut decyzyjny w 13 wierszu) c) wiersz 14 zignoruj

Nastepnie, stosujac klasyfikator "naiwnego Bayesa" zaklasyfikuj przypadek b) uzywajac zbioru treningowego a). Pokaz wszystkie niezbedne obliczenia.

Jesli jest to konieczne dla jakiegos atrybutu, to zastosuj wygladzanie dla tego atrybutu.

Rozwiązanie

P(tak|pochmurno & cieplo & normalna & brak): P1 = P(pochmurno|tak) * P(cieplo|tak) * P(normalna|tak) * P(brak|tak) * P(tak) = = 3/8 * 1/8 * 5/8 * 5/8 * 8/12 = 0.01220703

P(nie|pochmurno & cieplo & normalna & brak): P2 = P(pochmurno|nie) * P(cieplo|nie) * P(normalna|nie) * P(brak|nie) * P(nie) = = 0/4 * 2/4 * 1/4 * 2/4 * 4/12

tu zauwazamy, ze pierwsze prawdopobodobienstwo wynosi 0 (0/4), wiec zastosujemy dla tego atrybutu wygladzanie Laplace'a.

Do licznika dodajemy 1 a do mianownika liczbe mozliwych wartosci tego atrybutu (3) 0/4 -> (0+1)/(4+3) = 1/7

po modyfikacji mamy: P2' = 1/7 * 2/4 * 1/4 * 2/4 * 4/12 = 0.00297619

a wiec P1 > P2, czyli zgodnie z algorytmem naiwnego Bayesa przypadek bedzie zaklasyfikowany do klasy "TAK"

Podczas sprawdzianu nie bedzie kalkulatorow, wiec wystarczy oszacowac oba wyrazenia (przez skracanie ulamkow), aby okreslic ktore jest wyzsze, nie trzeba dokladnie obliczac wartosci.

Przykładowe zadanie na algorytm grupowania K-średnich

Mając dany zbiór danych składający się z 4 wektorów: a=(1,1,1, 0), b=(0,2,0,0), c=(2,3,-1,3), d=(1,2, 0,0) oraz początkowe wartości centroidów 2 grup: c_1=(1,1,1, 0) c_2=(1,2, 0,0)

wykonaj obliczenia dla algorytmu k-średnich (ewentualne remisy w odległościach rozstrzygnij zgodnie z numeracją grup 1 i 2) dla k=2 do momentu zakończenia algorytmu i wypełnij następujące pola:

końcowy skład grupy 1:...................... końcowy skład grupy 2:...................... końcowa wartość centroidu c_1 pierwszej grupy:.................... końcowa wartość centroidu c_2 drugiej grupy:....................

Rozwiązanie

ponizej, d(x,y) oznacza wartosc odleglosci euklidesowej pomiedzy wektorami x,y

Iteracja 1a: (przyporzadkowanie wektorow do najblizszych centroidow)

d(a,c1) = 0 d(a,c2) = 1.41 (=sqrt(2)) (a wiec a ma blizej do c1)

d(b,c1) = 1.73 (=sqrt(3)) d(b,c2) = 1 (a wiec b ma blizej do c2)

d(c,c1) = 4.24 (=sqrt(18)) d(c,c2) = 3.46 (=sqrt(12)) (a wiec c ma blizej do c2)

d(d,c1) = 1.41 d(d,c2) = 0 (a wiec d ma blizej do c2)

a wiec po iteracji 1a, grupy beda nastepujace: grupa 1: a grupa 2: b,c,d

Iteracja 1b: (obliczanie nowych wartosci centroidow)

c_1 = a = (1,1,1,0) c_2 = (b+c+d)/3 = (1,7/3,-1/3,1)

Iteracja 2a: (przyporzadkowanie wektorow do najblizszych centroidow)

d(a,c1) = 0 d(a,c2) = 2.13 (a wiec a ma blizej do c1)

d(b,c1) = 1.73 d(b,c2) = 1.49 (a wiec b ma blizej do c2)

d(c,c1) = 4.24 (=sqrt(18)) d(c,c2) = 2.42 (a wiec c ma blizej do c2)

d(d,c1) = 1.41 d(d,c2) = 1.10 (a wiec d ma blizej do c2)

a wiec po iteracji 2a, grupy beda nastepujace: grupa 1: a grupa 2: b,c,d a wiec nie zmienily sie juz, algorytm konczy sie:

końcowy skład grupy 1: a końcowy skład grupy 2: b,c,d końcowa wartość centroidu c_1 pierwszej grupy: (1,1,1,0) końcowa wartość centroidu c_2 drugiej grupy: (1,7/3,-1/3,0)

UWAGA praktyczna: zauwazmy, ze przy braku kalkulatorow, prosciej bedzie liczyc kwadraty odleglosci (czyli wzor euklidesa bez wyciagania z nich pierwiastka), nie zmieni to faktu, ktory centroid jest blizszy