Strojové u ení typy učení: • učení se znalostem (knowledge acquisition) • učení se dovednostem (skill refinement).
volba reprezentace
u ení
u ení
znalosti
rozhodování
objekt
popis objektu
rozhodování
rozhodnutí
Obr. 1 Obecné schema u ícího se systému
Metody učení: 1. učení zapamatováním (rote learning neboli biflování), 2. učení se z instrukcí (learning from instruction, learning by being told), 3. učení se z analogie (learning by analogy, instance-based learning, lazy learning),, 4. učení na základě vysvětlení (explanation-based learning), 5. učení se z příkladů (learning from examples), 6. učení se z pozorování a objevováním (learning from observation and discovery),
Metody učení: •
statistické metody - regresní metody, diskriminační analýza, shluková analýza,
•
symbolické metody um lé inteligence - rozhodovací stromy a pravidla, případové usuzování (CBR)
•
subsymbolické metody um lé inteligence - neuronové sítě, bayesovské sítě nebo genetické algoritmy.
Informace o správnosti učení: • příklady zařazené do tříd (u ení s u itelem - supervised learning) • odměny za správné chování a tresty za chování nesprávné (reinforcement learning) • nepřímé náznaky odvozené s chování učitele (apprenticeship learning) • žádné (u ení bez u itele - (unsupervised learning)
reprezentace příkladů: 1. atributy: kategoriální (binární, nominální, ordinální) a numerické [barva_vlasu=cerna & vyska=180 & vousy=ano & vzdelani=VS]
2. relace otec(jan_lucembursky, karel_IV)
Učení na základě podobnosti (similarity-based learning) • •
objekty, patřící do téže třídy mají podobné charakteristiky z konečného počtu příkladů odvozujeme obecné znalosti
Obr. 2 Málo dat
Obr. 3 Více dat
Obecná definice u ení (s u itelem) Analyzovaná data:
=
Řádky tabulky reprezentují sledované objekty Sloupce datové tabulky odpovídají atribut m Přidáme-li cílový atribut do datové tabulky, získáme data vhodná pro použití některé metody učení s učitelem (tzv. trénovací data).
=
Klasifikační úloha: hledáme znalosti (reprezentované rozhodovací funkcí ), které by umožňovaly k hodnotám vstupních atributů nějakého objektu přiřadit vhodnou hodnotu atributu cílového
→ V průběhu klasifikace se tedy pro hodnoty vstupních atributů nějakého objektu odvodí hodnota cílového atributu:
Odvozená hodnota se pro objekty z trénovacích dat může lišit od skutečné hodnoty . Můžeme tedy pro každý objekt ∈ vyčíslit chybu klasifikace • pro numerický atribut
např.
(oi , • pro kategoriální atribut ( ,
)2
) např.
pro pro
)
≠
Pro celou trénovací množinu pak můžeme vyčíslit souhrnnou chybu například jako střední chybu
)
( ,
Cílem učení je nalézt takové znalosti chybu
=
)
které by minimalizovaly tuto
)
1. U ení jako prohledávání: Předpokládejme, že jak vstupní atributy tak i cílový atribut jsou kategoriální - hodnotě atributu budeme říkat kategorie:
1. atomická formule vyjadřující vlastnost objektu ∀
= ≠
pro pro
=
2. množina objekt majících danou vlastnost
{
}=
=
}
Spojováním kategorií logickou spojkou ∧ budeme vytvářet kombinace " # = !
1.
2.
$
∀
" #
{
Platí-li " #
" #} =
=
$
pro jinak
=
∧
=
∧
=
∧
=
, říkáme, že kombinace
∧ ∧
=
∧
∧
∧
$
=
∧
$
$
$
=
$
$
}.
pokrývá objekt
Přidáváním kategorií ke kombinaci vznikají její nadkombinace, odebráním kategorií z kombinace vznikají její podkombinace.
Pomocí pojmu podkombinace můžeme definovat částečné uspořádání mezi kombinacemi. Je-li kombinace podkombinací kombinace , potom říkáme, že kombinace je obecn jší než kombinace a že kombinace je speciáln jší než kombinace
Je-li kombinace obecn jší než kombinace pokrývá alespoň všechny ty objekty, které pokrývá
, potom .
V případě učení s učitelem budeme hledat znalosti použitelné pro klasifikaci objektů do tříd. Znalosti budou reprezentovány kombinacemi, které budeme chápat jako hypotézy vyjadřující vazbu mezi hodnotami vstupních atributů na jedné straně a hodnotou cílového atributu na straně druhé. Kombinace jedné třídy:
∃
je konzistentní, právě když pokrývá pouze příklady
%
)∀
∈
=
" #
=
%
Cílem u ení bude hledat hypotézy konzistentní s trénovacími daty.
Příklad: p íjem vysoký vysoký nizký vysoký
konto vysoké vysoké nízké vysoké
pohlaví žena muž muž muž
nezam stnaný ne ne ne ne
auto ano ano ano ne
bydlení vlastní vlastní nájemní nájemní
úv r Ano Ano Ne Ano
Tab. 1 Trénovací data
V kombinaci Comb (hypotéze popisující koncept „úvěr“) se pro každý atribut může objevit: •
„?“ jakožto indikace toho, že na hodnotě atributu nezáleží,
•
hodnota atributu,
•
„∅“ jakožto indikace toho, že žádná hodnota atributu nevyhovuje.
[?, ?, ?, ?, ?, ?]
....
[?, ?, žena, ?, ?, ?]
[vysoký, ?, ?, ne, ?, ?]
[vysoký,?, ?, ?, ?, ?]
[?,vysoké, ?, ?, ?, ?]
[vysoký,vysoké,?, ?, ?, ?]
[?,?, ?, ?, ?, vlastní]
[?, vysoké, ?, ne, ?, ?, ?]
[vysoký,vysoké, ?, ne, ?, ?]
[vysoký,vysoké,?, ne,ano,?]
[vysoký, vysoké,?, ne,ano, vlastní]
[vysoký,vysoké,žena,ne, ano, vlastní]
[vysoký,vysoké,?,ne, ?,vlastní]
[vysoký, vysoké, muž,ne, ?,vlastní]
[vysoký, vysoké, žena,ne, ?,vlastní]
[vysoký,vysoké,muž,ne, ano, vlastní]
[vysoký,vysoké,muž, ne, ?,?]
[vysoký, vysoké, muž,ne, ano, ?]
[vysoký, vysoké, muž,ne, ne, ?]
[vysoký,vysoké,muž,ne, ne, nájemní]
[∅, ∅, ∅, ∅, ∅, ∅]
Obr. 4 Prostor hypotéz
Prostorem hypotéz se můžeme pohybovat dvěma způsoby: • od obecnějšího popisu ke speciálnějšímu (specializace), • od speciálnějšího popisu k obecnějšímu (generalizace).
...
Kritérium Err(f), které minimalizujeme, je počet chyb, kterých se dopustíme při klasifikaci trénovacích dat. Find-S algoritmus 1. přiřaď do h nejspeciálnější hypotézu v H 2. pro každý pozitivní příklad x 2.1. pro každý atribut ai z hypotézy h if hodnota atributu ai neodpovídá příkladu x then nahraď hdnotu ai nejbližší obecnou hodnotou která odpovídá x 3. vydej h
S:
[vysoký,vysoké,?, ne,ano,?]
[vysoký, vysoké,?,ne, ?, ?]
[vysoký,vysoké,?,ne, ?,vlastní]
[vysoký, vysoké,?, ne,ano, vlastní]
[vysoký,vysoké,žena,ne, ano, vlastní]
[vysoký,vysoké,muž, ne, ?,?]
[vysoký, vysoké, muž,ne, ne, ?]
[vysoký,vysoké,muž,ne, ano, vlastní]
[vysoký,vysoké,muž,ne, ne, nájemní]
Candidate-Elimination algoritmus 1. přiřaď do G množinu nejobecnějších hypotéz z H 2. přiřaď od S množinu nejspeciálnějších hypotéz z H 3. pro každý příklad x 3.1. if x je pozitivní příklad then odstraň z G všechny hypotézy inkonsistentní s příkladem x pro každou hypotézu s z S která je inkonsistentní s příkladem x odstraň s z S přidej do S nejmenší generalizaci h hypotézy s takovou, že h je konsistentni s příkladem x a že v G je hypotéza obecnější než h odstraň z S hypotézy, které jsou obecnější než jiné hypotézy v S 3.2. if x je negativní příklad then odstraň z S všechny hypotézy inkonsistentní s příkladem x pro každou hypotézu g z G která je inkonsistentní s příkladem x odstraň g z G přidej do G nejmenší specializaci h hypotézy g takovou, že h je konsistentní s příkladem x a že v S je hypotéza speciálnější než h odstraň z G všechny hypotézy, které jsou speciálnější než jiné hypotézy v G
G:
[vysoký,?, ?, ?, ?, ?]
[vysoký, ?, ?, ne, ?, ?]
[?, vysoké, ?, ?, ?, ?]
[vysoký,vysoké,?, ?, ?, ?]
S:
[vysoký, vysoké,?,ne, ?, ?]
[?, vysoké, ?, ne, ?, ?, ?]
U ení jako aproximace funkcí: na základě hodnot funkce v konečném počtu bodů snažíme zrekonstruovat její obecnou podobu
x
y=f(x)
x x x x x x x
metoda nejmenších tverc : Hledání minima celkové odchylky min i (yi - f(xi)) 2 se převádí na řešení rovnice d dq
(yi - f(xi))2 = 0 i
řešení: 1) analytické (známe typ funkce) řešení soustavy rovnic pro parametry funkce viz statistika
2) numerické (neznáme typ funkce) -
∂ ∇ Err(q) = ∂&
∂ ∂&
!& &
Modifikace znalostí
gradientní metody
∂ ∂& Q
.
& pak probíhá podle algoritmu
& ← & ' ∆& kde
)& = (
∂ ∂&
a η je parametr vyjadřující „velikost kroku“ kterým se přibližujeme k minimu funkce . Je-li např. chybová funkce
)2 =
) a předpokládaná funkce
lineární kombinací vstupů ∗
můžeme odvodit gradient funkce
∂Err 1 = ∂q j 2
*
∂ (yi - ~yi )2 = 1 2 i =1 ∂q j n
,
jako
∂ (yi - ~yi ) 2(y i - ~yi ) ∂q j i =1 n
∂ (y i = (y i - ~yi ) ∂q j i =1 n
)=
n i =1
(yi - ~yi )(- x ij )
a tedy
∆&
η
(
)
)) 2
