resumen del teorema de convergencia del perceptron
TRANSCRIPT
-
8/17/2019 Resumen Del Teorema de Convergencia Del Perceptron
1/2
Felipe de Jesús Duarte López00000037902
Resumen del teorema de convergencia del perceptron
El algoritmo de aprendizaje siempre encontrara los pesos que clasiquen lasentradas! si tales pesos e"isten#
$ins%& ' (apert demostraron que tales pesos e"isten si & solamente si elpro)lema es linealmente separa)le! razón cla*e para el inter+s del perceptron#
Teorema
,uponga que las clases -.! -2 son linealmente separa)les#
Entonces! el algoritmo del perceptron aplicado a -. / -2 termina con +"itodespu+s de un número nito de iteraciones#
Esto es E"iste un numero entero 1 tal que para todo % 1! el error e%4 5 0! &entonces 6%.456%4
(rue)a
(or simplicidad asumimos que 6.4 5 0! 8 5 . & el contador de iteraciones kcuenta solamente los pasos en los que se corrige el *ector de pesos# Entonces
62456.4e.4".4! 6345624e24"24! 6%.456%4e%4"%4#
a que -. & -2 son linealmente separa)les entonces e"iste 6: tal que clasicacorrectamente a todos los *ectores de entrada! ; " < -#
" < -.6:= ">0 -.5.
" < -26:= "?0 -25@.
,ea
a que todos los *ectores de entrada "j4 Aan sido clasicados incorrectamenteej4 6:="j4 es estrictamente positi*o# ,i 6:="j4>0 ej4>0! si 6:="j4?0 ej4?0# ,e tiene que
6:=6%.4>%aB a5min jej4 6:t"j44
-
8/17/2019 Resumen Del Teorema de Convergencia Del Perceptron
2/2
Felipe de Jesús Duarte López00000037902
(or la desigualdad de -aucA&@,cA6arz
CC6j.4CC2 5¿w¿ T w (k +1)2∨ ¿
¿∨w¿T ∨¿
¿
! CC6j.4CC25
¿∨w∗¿∨¿2
(ka)2
¿
,i se considera otro camino
CC6j.4CC25CC6j4CC2CCej4"j4CC22ej46 =j4"j4
2ej46 =j4"j4 ?0! Los vectores son clasifcados incorrectamente
5ma" jCCej4"j4CC2
CC6j.4CC2 ≤ CC6j4CC2
Entonces
CC6%.4CC2 ≤ %
%
¿∨w∗¿∨¿2
≥∨¿w (k +1 )∨¿2≥(ka)2
¿
.
Q∨¿w∗¿∨¿2
≥ ka
2
¿
(or lo tanto % no puede ser ma&or que %ma" tal que
ma"5
Q∨|w|∨¿2
a2
¿
Entonces el algoritmo termina con +"ito al menos en %ma" iteraciones#
• El algoritmo con*erge a la clasicación correcta sio Los datos de entrenamiento son linealmente separa)leso La *elocidad de aprendizaje es lo sucientemente pequea
• La solución 6: no es única! &a que si 6 :="50 un Aiperplano tam)i+n lo
Aace 6:G5 ∝ 6:#