Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:ml:mlrep2 [2017/07/17 10:08] |
pl:dydaktyka:ml:mlrep2 [2019/06/27 15:50] (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). | ||
| + | |||
| + | --------------------- | ||
