resumen del teorema de convergencia del perceptron

Upload: felipe-de-jesus-duarte-lopez

Post on 06-Jul-2018

216 views

Category:

Documents


0 download

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