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:#