Mesterséges Intelligencia MI
Egyszerű döntés. Tanuljuk meg! Dobrowiecki Tadeusz Eredics Péter, és mások
BME I.E. 437, 463-28-99
[email protected], http://www.mit.bme.hu/general/staff/tade
Neuron doktrina: S. Ramón y Cajal (1852-1934) Mesterséges neuron: W. McCulloch and W. Pitts, 1943 Tanulás: D. Hebb, 1949 SNARC (Stochastic Neural Analog Reinforcement Calculator): M. Minsky, 1951 Perceptron: F. Rosenblatt, 1957 … Mély neurális hálók, stb., 2006
Perceptron n+1
n
i =1
i =1
y = sgn(∑ wi xi ) = sgn(∑ wi xi + wn+1 ) = sgn(xT w + b)
xT w + b > 0 xT w + b < 0 lineárisan (hipersíkkal) szeparálható függvényt képes reprezentálni
Perceptron tanítása
w(k ) = w(k −1) + α ε (k ) x(k )
α - bátorsági faktor, tanulási tényező
Perceptron tanítása
w(k ) = w(k −1) + α ε (k ) x(k )
Tanítás konvergens, ha A tanító példák lineárisan szeparálhatók Bátorsági tényező elegendően kicsi
Perceptron és logikai függvények
XOR (és hasonlóan lineárisan nem szeparálhatók) problémája: több réteg tanulás = csak 1 réteg (hiba értelmezése)
Mesterséges neuron
Mesterséges Neurális Háló (Artificial Neural Network) nemlineáris approximációt megvalósító, induktív tanulási algoritmussal tanítható matematikai struktúra.
Mesterséges Neurális Háló D. Hilbert (1900) 23 matematikai problémája/sejtése: 13. probléma: "Bizonyítsuk be, hogy az x7+ax3+bx2+cx+1=0 hetedfokú egyenlet nem oldható meg pusztán kétváltozós függvények segítségével!„ … "Mutassuk meg, hogy van olyan háromváltozós folytonos függvény, mely nem írható fel véges számú kétváltozós folytonos függvény segítségével!„ … A. Kolmogorov (1957): nem csupán minden háromváltozós függvény, hanem tetszőleges N-változós folytonos függvény felírható csupán egyváltozós függvények és az összeadás segítségével. … http://mialmanach.mit.bme.hu/neuralis/ch01s04
Mesterséges Neurális Háló
Mesterséges Neurális Háló Többrétegű előrecsatolt háló tanítása (elemi alapok) Hibavisszaterjesztés gradiens módszerrel - példa bemeneteket mutatunk a hálónak, - ha hiba lép fel (a kimenet és a kívánt érték eltér), a súlyokat úgy módosítjuk, hogy a hiba csökkenjen. A trükk a hiba megállapítása és a hibának a hibát létrehozó súlyok közti szétosztása.
∂E W ← W −α ∂W
Mesterséges Neurális Háló
Wk , j ← Wk , j
∂E −α ∂Wk , j
W j ,i ← W j , i − α
∂E ∂W j , i
1 E = Σ i ( d i − yi ) 2 2
Mesterséges Neurális Háló – hibavisszaterjesztés, alapok 1 1 2 E = Σ i ( d i − yi ) = Σ i Erri 2 2
W j ,i ← W j ,i − α
∂E ∂W j , i
1 1 2 E ( W ) = Σ i ( d i − g (Σ jW j ,i a j )) = Σ i ( d i − g (Σ jW j ,i g (Σ kWk , j I k ))) 2 2 2
∂E = − a j ( d i − yi ) g '(Σ jW j ,i a j ) = − a j ( d i − yi ) g '(ini ) = − a j ∆ i ∂W j , i ∂E W j ,i ← W j , i + α a j ∆ i W j ,i ← W j , i − α = W j ,i + α a j Erri g '(ini ) ∂W j , i ∆ i = Erri g '(ini ) ∂E ∂E Wk , j ← Wk , j − α = −Ik ∆ j ∂Wk , j ∂Wk , j Wk , j ← Wk , j + α I k ∆ j
∆ j = g '(in j ) Σ iW j ,i ∆ i
Mesterséges Neurális Háló Kérdések: mekkora (hány réteg, rétegenként hány processzáló elem) hálózatot válasszunk, hogyan válasszuk meg a tanulási tényező, α értékét, milyen kezdeti súlyértékeket állítsunk be, hogyan válasszuk meg a tanító és a tesztelő minta készletet, hogyan használjuk fel a tanító pontokat, milyen gyakorisággal módosítsuk a hálózat súlyait, meddig tanítsuk a hálózatot, stb? (hogyan gyorsítsuk meg a tanulást?) (hogyan védekezzünk a túltanulással szemben?) http://mialmanach.mit.bme.hu/neuralis/index
Mesterséges Neurális Háló
http://mialmanach.mit.bme.hu/neuralis/index
XOR - újra
A hibavisszaterjesztést alkalmazó hálókban általában a szigmoid függvényt vagy annak valamelyik változatát használjuk. A szigmoidnak megvan az a tulajdonsága, hogy deriváltja
g ' = g (1 − g )
Elemzés
g ( x) =
1 1 + e− x
Kifejezőképesség: nem rendelkeznek az általános logikai reprezentációk kifejezőképességével. A többrétegű hálók osztálya egészében, mint osztály az attribútumok bármely függvényének reprezentációjára képes. Számítási hatékonyság: legrosszabb esetben a szükséges epochok száma a bemenetek számának, n-nek, még exponenciális függvénye is lehet. A hibafelület lokális minimumai problémát jelenthetnek. Általánosító képesség: jó általánosításra képesek. Zajérzékenység: alapvetően nemlineáris regresszió, nagyon jól tolerálják a bemeneti adatok zajosságát. Átláthatóság: alapvetően fekete doboz. A priori ismeret: ?
Mesterséges Neurális Háló – „sekélytől” „mélyig” háló felskálázása és tanulás nehézségei (gradiens) (1971, 8 réteg) heurisztikus jellegkiemelés – ad hoc vizuális cortex struktúra – implicit jellegkiemelés háló felskálázása és struktúrálása (CNN) tanítás felgyorsítása kép, hang, nyelv, … multimodális …
Perceptron és a lineáris szeparálhatóság - újra Optimális szétválasztás - maximális margó
w ⋅x +b > 0
w ⋅x +b < 0
d i (w ⋅ xi + b) ≥ 1 d i (w ⋅ x + b) = 1 minden x-re a margó határán
x w
Optimális szétválasztás
2 szélesség = w
Margó szélesség maximalizálása
1 2 A feladat: min w 2 ∗ ∗ A megoldása: w , b ,
d i (w ⋅ xi + b) ≥ 1
i=1, …, m:
f ( x ) = sgn {w ∗ ⋅ x + b ∗ }
P 1 2 min L ( w , b, α ) = w − ∑ α i [ d i ( w ⋅ x i + b ) − 1] 2 i =1 i=
(Lagrange multiplikátorokkal)
Duál feladat
P
1 P P max[Q (α ) = ∑ α i − ∑ ∑ α iα j d i d j x i ⋅ x j ] 2 i =1 j =1 i =1 P
∑α d i =1
i
i
= 0, α i ≥ 0, i = 1,..., P
P P ∗ ∗ ∗ f ( x) = sgn ∑ α i d i x i ⋅ x + b , w = ∑ α i∗ d i x i i =1 i =1
Optimális szétválasztás
P ∗ f ( x) = sgn ∑ α i d i x i ⋅ x + b∗ , i =1 P
w = ∑ α i∗ d i x i ∗
i =1
Nem zérus αi = szuport vektor Szuport vektor = példa az osztály határán Ha nem nagyon „vad” az osztály határ = kevés szuport vektor is elég
Kernelgépek (SVM, szupport vektor gépek) Kerneltrükk (avagy mi van, ha mégsem lineárisan szeparálható?)
Kernelgépek (SVM, szupport vektor gépek)
Feladattér – nemlineáris osztályozó határfelület Transzformált (dimenziót növelő) tér – lineáris osztályozó hipersík
Kernelgépek (SVM, szupport vektor gépek)
Optimális szétválasztás jellemzőtérben m
1 m m max[Q (α ) = ∑ α i − ∑ ∑ α iα j d i d jϕ ( x i ) ⋅ ϕ ( x j )] 2 i =1 j =1 i =1 m
∑α d i =1
i
i
= 0, α i ≥ 0, i = 1,..., m
P P ∗ ∗ ∗ f ( x) = sgn ∑ α i d iϕ ( x i ) ⋅ ϕ ( x ) + b , w = ∑ α i∗ d iϕ ( x i ) i =1 i =1
Kerneltrükk
ϕ ( z ) ⋅ ϕ ( x) = k ( z , x) = g (x ⋅ x)
m
1 m m max[Q (α ) = ∑ α i − ∑ ∑ α iα j d i d j k ( x i , x j )], ... 2 i =1 j =1 i =1 ∗ ∗ f ( x) = sgn ∑ α i d i k ( x i , x) + b i = PS
Kerneltrükk
ϕ ( z ) ⋅ ϕ ( x) = k ( z , x) = g ( x ⋅ x)
ϕ : x = ( x1 , x2 ) → ϕ ( x) = ( x12 , x22 , 2 x1 x2 ) ϕ ( z ) ⋅ ϕ ( x) = ( z12 , z22 , 2 z1 z2 ) ⋅ ( x12 , x22 , 2 x1 x2 ) = x12 z12 + x22 z 22 + 2 x1 x2 z1 z2 = ( x1 z1 + x2 z2 ) 2 = ( z ⋅ x) 2 = k ( z , x)
ϕ : x = ( x1 , x2 ) → ϕ ( x) = (1, 2 x1 , 2 x2 , x12 , x22 , 2 x1 x2 ) ϕ ( z ) ⋅ ϕ ( x) = ... = (1 + x1 z1 + x2 z2 ) 2 = (1 + z ⋅ x) 2 = k ( z , x) ϕ : x = ( x ) → ϕ ( x) = ( x, x 2 ) ϕ ( z ) ⋅ ϕ (x) = ... = ( xz + x 2 z 2 ) = z ⋅ x(1 + z ⋅ x) = k ( z , x)
Kernelgépek (SVM, szupport vektor gépek)
ϕ : x = ( x1 , x2 ) → ϕ ( x) = (1, 2 x1 , 2 x2 , x12 , x22 , 2 x1 x2 ) ϕ ( z ) ⋅ ϕ ( x) = ... = (1 + x1 z1 + x2 z2 ) 2 = (1 + z ⋅ x) 2 = k ( z , x) 2 x1 x2 = ± 2
ϕ : x = ( x1 , x2 ) → ϕ ( x) = ( 2 x1 , 2 x1 x2 )
x2 = ±
1 x1
Kernelgépek (SVM, szupport vektor gépek) Hogyan lehetünk biztosak, hogy jellmzőtérben már lineárisan szeparálható?
Kernelgépek (SVM, szupport vektor gépek) „slack” = laza változók módszere 1 min w 2
2
n
i =1
0 ≤ αi ≤ C
n
1 n n max ∑ α i − ∑∑ α iα j yi y j xTi x j 2 i =1 j =1 i =1 g ( x) = w T x + b =
ξi ≥ 0
yi (w T xi + b) ≥ 1 − ξi
+ C ∑ ξi
n
∑α y
T α x ∑ i i x+b
i =1
i
i
=0
i∈SV
n
1 n n max ∑ α i − ∑∑ α iα j yi y j k (xi , x j ) 2 i =1 j =1 i =1 g ( x ) = w φ ( x) + b = T
∑ α φ ( x ) φ ( x) + b T
i∈SV
g (x) = ∑ αi k (xi , x) + b i∈SV
i
0 ≤ αi ≤ C n
∑α y i =1
i
i
=0
i
k (xi , x j ) = φ (xi )T φ (x j )
k ( xi , x j ) = (1 + xi x j ) 2 C = 100 5
1 5 5 max ∑ α i − ∑∑ α iα j yi y j (1 + xi x j ) 2 0 ≤ α i ≤ 100 5 2 i =1 j =1 i =1 ∑ α i yi = α1 + α 2 + α 5 − α 3 − α 4
α1 = 0 α 2 = 2.5 α3 = 0 α 4 = 7.333 α 5 = 4.833
i =1
g ( x) = 0.6667 x 2 − 5.333 x + 9
g ( x) = 2.5 × 1× (1 + 2 x) 2 + 7.333 × (−1) × (1 + 5 x) 2 + 4.833 × 1× (1 + 6 x) 2 + b = 0.6667 x 2 − 5.333 x + b b=9
MI kis HF4
x1
x2
Osztály cimke
-2
-2
A
Legyen a bemeneti tér leképezése a 2-dim jellemzőtérbe: (x1,x2) → (x12, x1*x2)
-2
-1
A
1
2
A
(a) Kockás papíron(*) ábrázolva jelölje be és megfelelően címkézze a bemeneti tér tanító példáit. Állapítsa meg, hogy ebben a térben a két osztály lineárisan szétválasztható-e?
2
1
A
-2
2
B
0
2
B
0
-1
B
2
-1
B
Jellemezzünk egy bináris osztályozási problémát 2-dim bemeneti térben az alábbi pontokkal:
b) Külön ábrán jelölje be és megfelelően cimkézze a tanító példákat a jellemzőtérben.
c) Keresse meg a jellemzőtérben (grafikon alapján, szemrevételezéssel, nem optimum számítással!) a maximális margójú lineáris osztályozót! Adja meg a szétválasztó egyenes és a margót határoló két egyenes képletét. Rajzolja be ezeket az egyeneseket a (b) pontban készített grafikonon. Listázza ki és jelólje be a jellemzőtérben megtalált szuport vektorokat. d) Határozza meg, hogy a megtalált szuport vektoroknak mely példák felelnek meg a bemeneti térben.
e) Az (a) pontban készített grafikonon rajzolja be az osztályokat szétválasztó görbéket. Vegye figyelembe, hogy: A bemeneti tér határoló görbéi könnyen megkaphatók x2 = g(x1) formában a jellemzőtér határoló egyeneseiből. A határoló görbék hiperbolikus jellegűek. Ügyeljen az aszimptoták helyes ábrázolására. Ügyeljen a jellemzőtérben origó körüli határoló egyenesek bemeneti térbe történő visszatranszformálására. Legjobb, ha a jellemzőtérben az origó közeli határoló egyenest fokozatosan közelíti az origó felé és megvizsgálja ennek hatását a bemeneti térben. f) Satirozza be a jellemzőtérbeli szétválasztó margónak megfelelő területet a bemeneti térben. g) Minél egyszerűbb formában írja fel az (a-f) pontokban meghatározott SVM osztályozónak a bemeneti térre vonatkozó, az új példák besorolására használható egyenlőtlenségét! (*) Elegendő 1 db A4 kockás lapon, olvasható kézirással készített megoldás szkennelt képét (jpg, pdf) benyújtani. Természetesen igényesebb szerkesztésű (de nem hosszabb!) megoldás is benyújtható.
