Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

pl:dydaktyka:ml:mlrep2 [2017/07/17 08:08] (aktualna)
Linia 1: Linia 1:
 +
 +====== 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).
 +
 +---------------------
  
pl/dydaktyka/ml/mlrep2.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0