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.
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 (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.
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.
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.
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.
Decision trees
S100-8
Pokazane są różne miary służące do określania stopnia zanieczyszcznia (poprawnie sklasyfikowanych przypadków).
S109
: wynikowe drzewo wraz z pojęciami na liściach i liczbami klasyfikowanych przez nie przypadków.
Drzewo jest klasyfikatorem grupującym.
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ść.
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 (Hammond_organ) w zależności od modelu, stanu i głośnika (Leslie_speaker).
Drzewa klasteryzujące wykorzystują miarę odległości przykłądół względem określonych cech od środka klastra S124-8
.
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).
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.
S134
, reguła: if Gills=yes then Class=-S134
, mamy regułę: : if Teeth=many then Class=+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.
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
.
Descriptive rule learning
Czyli sytuacja w której nie znamy z góry pojęć, które chcemy opisać, sklasyfikować regułowo.
Subgrup discovery
S158-164
Dotyczy odrywania wzorców (opisanych regułowo) w uprzednio określonych klasach. (pominięte na wykładzie).
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ęć:
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.
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).