====== Peter Flach: Machine Learning, repetytorium 2 ======

===== -#4 Uczenie pojęć =====
//Concept learning//

Zakładamy, że rozpoznawane obiekty są opisywane przy pomocy cech (//features//), które tu będziemy nazywać **pojęciami** (//concepts//).
Cechy reprezentujemy przez symbole zdaniowe w rachunku zdań, tj. cechy orzekane o obiekcie są binarne (obiekt ma lub nie ma jakiejś cechy), lub atrybutowe (atrybut przyjmuje konkretną wartość ze ściśle określonej dziedziny).
W praktyce jest to opis w rachunku zdań.
Co za tym idzie,
pojęcie, służące do opisania obiektu możemy wyrazić jako koniunkcję w.w. cech, np. pojęcie delfina.


==== - Przestrzeń hipotez ====
//The hypothesis space//

''S079''
wprowadza przykład, gdzie napotykanymi obiektami są zwierzęta morskie.
Będzie nas interesowało wyróżnienie wśród nich delfinów.
Zwięrzęta opisujemy przy pomocy 4 cech, długość, skrzela, dziób (nos), ilość zębów.

''S080''
przez przestrzeń hipotez rozumiemy graf reprezentujący wszystkie możliwe koninkcje tych 4 cech.
W naszym przypadku graf ma postać **kraty** (//[[wp>Lattice_(order)]]//).

''S081''
jesteśmy zainteresowani ograniczeniem rozmiaru przestrzeni poprzez uwzględnienie tylko tych koniunkcji które pozwalają na klasyfikację obserwowanych przykładów - są pewnym uogólnieniem.

''S082,3''
wskazanie najmniej ogólnych generalizacji (LGG) pozwala na ograniczenie przestrzeni i jej redukcję do tych koniunkcji cech które pozwalają na określenie pojęć.

''S084,5''
użycie przykładów negatywnych pozwala na dalsze zmniejszenie przestrzeni.

==== - Ścieki w przestrzeni hipotez ====
//Paths through the hypothesis space//

Pojęcia które są w kracie pomiędzy LGG a górnym ograniczeniem to możliwe hipotezy - pojęcia potencjalnie opisujące możliwe do spotkania obiekty.

Użyteczną podprzestrzenią przestrzeni hipotez jest przestrzeń wersji //version space// (pojęcie wprowadzone przez t. Mitchella) zwierająca wyłącznie pojęcia (koniunkcje) zupełne i spójne ''S090''.

W praktyce często chcemy przestrzeń ograniczyć do pojęć zamkniętych, tzn. takich, które są LGG dla wszystkich przykładów, które opisują. Na ''S095'' takim pojęciem jest D.

==== - Więcej niż koniunkcje pojęć ====
//Beyond conjunctive concepts//

Język opisu można wzbogacić, jeżeli zamiast opisu atrybutowego, redukowalnego do rachunku zdań, użyjemy logiki pierwszego rzędu.
Komplikuje to jednak uczenie i ma ograniczone zastosowania.

---------------------

===== - Modele oparte na drzewach decyzyjnych =====
//Tree models//

''S100''
Ścieżkę w przestrzeni hipotez możemy reprezentować przy pomocy drzewa decyzyjnego.
Algorytmy uczące potrafią budować znacznie oszczędniejsze drzewa.

Każdy liści drzewa odpowiada ekstensji pewnego pojęcia - koniunkcji literałów - wyaznaczjąc tym samym fragment, segment przestrzeni instancji ''S101''.

Uczenie drzewa polega na itercyjnym wyborze optymalnych cech znajdujących się w kolejnych węzłach i wyborze optymalnych  wartości tych cech - czyli //split// (rozgałęzienie).
Do wyznaczania tych wartości służą różne miary.

==== - Drzewa decyzyjne ====
//Decision trees//

''S100-8''
Pokazane są różne miary służące do określania stopnia zanieczyszcznia (poprawnie sklasyfikowanych przypadków).
  - **miara** błędu (//minority class//)
  - **indeks Giniego**, [[wp>Gini_coefficient]] od [[wp>Corrado_Gini]]
  - **miara entropii** (teorioinformacyjna)

''S109'': wynikowe drzewo wraz z pojęciami na liściach i liczbami klasyfikowanych przez nie przypadków.

Drzewo jest klasyfikatorem grupującym.

==== - Drzewa oceniające i określejące prawdopodobieństwo ====
//Ranking and probability estimation trees//

''S111-4''
Rozważamy drzewa binarne, których liście możemy etykietować +/- w zależności od tego do jakiej klasy przypisują klasyfikowane przykłady.
Budowa tekich drzew polega na wyborze binarnych splitów i takiej zmianie etykietowania liści, aby uzyskać najwyższą dokłądność.

==== - Uczenie drzew decyzyjnych jako redukcja wariancji ====
//Tree learning as variance reduction//

Warto wskazać dwa inne zastosowania drzew: dla regresji i klasteryzacji.

W tych pierwszych na w liściach mamy jakieś wyznaczane wartości w postaci liczb reczywistych.
Miarę zanieczyszczenia zastępujmey wariancją.
Przykład ''S120-3'' budowy drzewa pozwalającego nw określenie optymalnej ceny organów ([[wp>Hammond_organ]]) w zależności od modelu, stanu i głośnika ([[wp>Leslie_speaker]]).

Drzewa klasteryzujące wykorzystują miarę odległości przykłądół względem określonych cech od środka klastra ''S124-8''.

---------------------

===== - Modele oparte na regułach decyzyjnych =====
//Rule models//

''S131''
W uczeniu reguł nie ma znaczenia jakiej miary zanieczyszczenia używamy.
Są one równoważne, gdyż zawsze dodajemy do reguły tylko pojedynczy lietarł reprezentujący wartość cechy (nie ma rozgałęzienia - podziału przestrzeni).

==== - Uczenie uporządkowanych zbiorów reguł ====
//Learning ordered rule lists//

''S132,3''
Rozważamy przykład ze zwierzętami morskimi.
W drzewie lierałów wybieramy te, które nie są zanieczyszczone - klasyfikują jedynie pozytywne przykłady.
  - wybieramy Gills=yes, bo klasyfikuje najwięcej przykładów ''S134'', reguła: //if Gills=yes then Class=-//
  - w drugim kroku Teeth=many ''S134'', mamy regułę: : //if Teeth=many then Class=+//
  - następnie Length=4 ''S135'', reguła: //if Length=4 then Calss=-//
Całość algorytmu jest na ''S137-8''

Nauczony model regułwy dopełniamy regułą domyślną i ma on wtedy postać:
  if Gills=yes then Class=-
  else
  if Teeth=many then Class=+
  else
  if Length=4 then Calss=-
  else
  Class=+

Aby kolejność reguł nie miała znaczenia uzupełniamy go zanegowanym literałmi:
  if Gills=yes then Class=-
  if Gills=no  and  Teeth=many then Class=+
  if Gills=no  and  Teeth=few  and  Length=4  then Calss=-
  if Gills=no  and  Teeth=few  and  Length=!4 then Calss=+

Taki zbiór reguł możemy też reprezentować przy pomocy odpowiadającemu mu zbiorowi drzew ''S139''.

''S140-3''
Reguły możemy też traktować jako model oceniający, zaznaczając ile i jakich przypadków każda z nich pokrywa.
W ogólnym przypadku kolejność literałów w sekwencji może mieć znaczenie ze względu na to jaki fragment przestrzeni pokrywają.
Jako klasyfikatory, listy reguł są podobne do drzew -- również dostajemy wypukłą krzywą pokrycia/ROC na wykresie.


==== - Uczenie nieuporządkowanych zbiorów reguł ====
//Learning unordered rule sets//

''S145-150''
Uczenie nieuporządkowanych zbiorów reguł przebiega podobnie, z tym że do wyboru literałów w regułach używamy miary niezanieczyszczenia (ile klasyfikujemy p vs. n).

''S151,2''
W takim przypadku preferowane są literały klasyfikujące tylko p, co może prowadzić do niedopasowania i potrzeby wprowadzenia korekcji.

''S153,4''
Nieuporządkowany zbiór reguł też może służyć do oceniania ilości przykładów (//ranker//).

Uwaga: w ogólnym przypadku, nauczony zbiór reguł może nie pokrywać całości przestrzeni przypadków ''S156''.


==== - Uczenie deskrypcyjne reguł ====
//Descriptive rule learning//

Czyli sytuacja w której nie znamy z góry pojęć, które chcemy opisać, sklasyfikować regułowo.

=== Odkrywanie reguł dla podgrup ===
//Subgrup discovery//

''S158-164''

Dotyczy odrywania wzorców (opisanych regułowo) w uprzednio określonych klasach.
(pominięte na wykładzie).

=== Odkrywanie reguł asocjacyjnych ===
//Associative rules//

''S165''
Jest to jedna z podstawowych metod odrywania wiedzy (//knowledge discovery//) lub drążenia danych (//data mining//).

Przykład:
mając listę transakcji ze sklepu (kto, co kupował) chcemy odkryć pewne zależności pomiędzy kupowanymi przedmiotami.
Poszczególne pojęcia (koniunkcje) porządkujemy - budujemy kratę.

Używamy dwóch pojęć:
  - //support// (względem pojęcia) - liczba transakcji opisywana (pokrywana) przez dane pojęcie, np. Supp({Beer,Crisps} = 3
  - //confidence// (względem reguły) - stosunek wielkości Supp dla pojęć w głowie i ciele reguły

Budowanie reguł sprowada się do wybierania krawędzi na grafie - par pojęć - zgodnie z uporządkowaniem. 
Np. wybieramy {Beer} (Supp=3) i {Nappies,Beer} (Supp=2).
Możemy zbudować regułę: {Beer} -> {Nappies,Beer}; Conf=2/3, czyli //if Beer then Nappies//

Inna reguła: {Nappies} (Supp=4) i {Nappies,Beer} (Supp=2).
Możemy zbudować regułę: {Nappies} -> {Nappies,Beer}; Conf=2/4, czyli //if Nappies then Beer//

Następnie oceniamy (wzg. Conf) i odsiewamy reguły słabsze.
Np. wybieramy tylko reguły w których przesłance (głowa) są pojęcia o Supp co najmniej 3,
a z otrzymanego zbiory reguł wybieramy te zadanym progu Conf, np. 0.6.

==== - Uczenie reguły w logice pierwszego rzędu ====
//First-order rule learning//

''S173-7''
Znane również jako indykcyjne programowanie logiczne.
Polega na uczeniu zbioru klauzul Horne'a czyli bazy wiedzy w Prologu.
Jest skomplikowane ze wzglęu na siłę ekspresji języka.
(pominięte na wykładzie).

---------------------