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).

1. miara błędu (minority class)
2. indeks Giniego, Gini_coefficient od Corrado_Gini
3. 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.

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.

1. wybieramy Gills=yes, bo klasyfikuje najwięcej przykładów S134, reguła: if Gills=yes then Class=-
2. w drugim kroku Teeth=many S134, mamy regułę: : if Teeth=many then Class=+
3. 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.

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ęć:

1. support (względem pojęcia) - liczba transakcji opisywana (pokrywana) przez dane pojęcie, np. Supp({Beer,Crisps} = 3
2. 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.

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).