Solución:
Aquí probaré que la siguiente función de pérdida es una función convexa.
begin {ecuación} L ( theta, theta_0) = sum_ {i = 1} ^ N left (- y ^ i log ( sigma ( theta ^ T x ^ i + theta_0)) – ( 1-y ^ i) log (1- sigma ( theta ^ T x ^ i + theta_0)) right) end {ecuación}
Luego se mostrará que la función de pérdida a continuación que el interrogador propuso NO es una función convexa.
begin {ecuación} L ( theta, theta_0) = sum_ {i = 1} ^ N left (y ^ i (1- sigma ( theta ^ T x ^ i + theta_0)) ^ 2 + (1-y ^ i) sigma ( theta ^ T x ^ i + theta_0) ^ 2 right) end {ecuación}
Para probar que resolver una regresión logística usando la función de primera pérdida es resolver un problema de optimización convexa, necesitamos dos hechos (para probar).
$ newcommand { reals} {{ mathbf {R}}} newcommand { preals} {{ reals_ +}} newcommand { ppreals} {{ reals _ {++}}} $
Suponer que $ sigma: reals to ppreals $ es la función sigmoidea definida por
begin {ecuación} sigma (z) = 1 / (1+ exp (-z)) end {ecuación}
-
Las funciones $ f_1: reals a reals $ y $ f_2: reals to reals $ definido por $ f_1 (z) = – log ( sigma (z)) $ y $ f_2 (z) = – log (1- sigma (z)) $ respectivamente son funciones convexas.
-
Una función convexa (dos veces diferenciable) de una función afín es una función convexa.
Prueba) Primero, mostramos que $ f_1 $ y $ f_2 $ son funciones convexas. Ya que
begin {eqnarray} f_1 (z) = – log (1 / (1+ exp (-z))) = log (1+ exp (-z)), end {eqnarray}
begin {eqnarray} frac {d} {dz} f_1 (z) = – exp (-z) / (1+ exp (-z)) = -1 + 1 / (1 + exp (-z) ) = -1 + sigma (z), end {eqnarray}
la derivada de $ f_1 $ es una función que aumenta monótonamente y $ f_1 $ función es una función (estrictamente) convexa (página Wiki para función convexa).
Asimismo, desde
begin {eqnarray} f_2 (z) = – log ( exp (-z) / (1+ exp (-z))) = log (1+ exp (-z)) + z = f_1 ( z) + z end {eqnarray}
begin {eqnarray} frac {d} {dz} f_2 (z) = frac {d} {dz} f_1 (z) + 1. end {eqnarray}
Dado que la derivada de $ f_1 $ es una función que aumenta monótonamente, la de $ f_2 $ es también una función que aumenta monótonamente, por lo tanto $ f_2 $ es una función (estrictamente) convexa, de ahí la prueba.
Ahora probamos la segunda afirmación. Dejar $ f: reals ^ m to reals $ es una función convexa diferencial doble, $ A in reals ^ {m times n} $, y $ b in reals ^ m $. Y deja $ g: reals ^ n to reals $ tal que $ g (y) = f (Ay + b) $. Entonces el gradiente de $ g $ con respecto a $ y $ es
begin {ecuación} nabla_y g (y) = A ^ T nabla_x f (Ay + b) in reals ^ n, end {ecuación}
y el arpillera de $ g $ con respecto a $ y $ es
begin {ecuación} nabla_y ^ 2 g (y) = A ^ T nabla_x ^ 2 f (Ay + b) A in reals ^ {n times n}. end {ecuación}
Ya que $ f $ es una función convexa, $ nabla_x ^ 2 f (x) successq 0 $, es decir, es una matriz semidefinida positiva para todos $ x in reals ^ m $. Entonces para cualquier $ z in reals ^ n $,
begin {ecuación} z ^ T nabla_y ^ 2 g (y) z = z ^ TA ^ T nabla_x ^ 2 f (Ay + b) A z = (Az) ^ T nabla_x ^ 2 f (Ay + b ) (A z) geq 0, end {ecuación}
por eso $ nabla_y ^ 2 g (y) $ es también una matriz semidefinita positiva para todos $ y in reals ^ n $ (Página wiki para función convexa).
Ahora, la función de objeto que se minimizará para la regresión logística es
begin {ecuación} begin {array} {ll} mbox {minimizar} & L ( theta) = sum_ {i = 1} ^ N left (- y ^ i log ( sigma ( theta ^ T x ^ i + theta_0)) – (1-y ^ i) log (1- sigma ( theta ^ T x ^ i + theta_0)) right) end {matriz} end {ecuación}
dónde $ (x ^ i, y ^ i) $ por $ i = 1, ldots, N $ están $ N $ datos de entrenamiento. Ahora bien, esta es la suma de funciones convexas de funciones lineales (por lo tanto, afines) en $ ( theta, theta_0) $. Dado que la suma de funciones convexas es una función convexa, este problema es una optimización convexa.
Tenga en cuenta que si maximizara la función de pérdida, NO sería una función de optimización convexa. ¡Entonces la dirección es crítica!
Tenga en cuenta también que, ya sea que el algoritmo que usemos sea descenso de gradiente estocástico, solo descenso de gradiente o cualquier otro algoritmo de optimización, resuelve el problema de optimización convexa, y que incluso si usamos núcleos no lineales no convexos para la transformación de características, sigue siendo una optimización convexa. problema ya que la función de pérdida sigue siendo una función convexa en $ ( theta, theta_0) $.
Ahora, la nueva función de pérdida propuesta por el interrogador es
begin {ecuación} L ( theta, theta_0) = sum_ {i = 1} ^ N left (y ^ i (1- sigma ( theta ^ T x ^ i + theta_0)) ^ 2 + (1-y ^ i) sigma ( theta ^ T x ^ i + theta_0) ^ 2 right) end {ecuación}
Primero mostramos que $ f (z) = sigma (z) ^ 2 $ no es una función convexa en $ z $. Si diferenciamos esta función, tenemos
begin {ecuación} f ‘(z) = frac {d} {dz} sigma (z) ^ 2 = 2 sigma (z) frac {d} {dz} sigma (z) = 2 exp (-z) / (1+ exp (-z)) ^ 3. end {ecuación}
Ya que $ f ‘(0) = 1 $ y $ lim_ {z to infty} f ‘(z) = 0 $ (y f ‘(z) es diferenciable), el teorema del valor medio implica que existe $ z_0 geq0 $ tal que $ f ‘(z_0) <0 $. Por lo tanto $ f (z) $ NO es una función convexa.
Ahora si dejamos $ N = 1 $, $ x ^ 1 = 1 $, $ y ^ 1 = 0 $, $ theta_0 = 0 $, y $ theta in reals $, $ L ( theta, 0) = sigma ( theta) ^ 2 $, por eso $ L ( theta, 0) $ no es una función convexa, ¡de ahí la prueba!
Sin embargo, resolver el problema de optimización no convexa mediante el descenso de gradientes no es necesariamente una mala idea. (Casi) todos los problemas de aprendizaje profundo se resuelven mediante el descenso de gradiente estocástico porque es la única forma de resolverlo (aparte de los algoritmos evolutivos).
Espero que esta sea una prueba autónoma (estricta) del argumento. Deje sus comentarios si algo no está claro o si cometí errores.
Gracias. – Sunghee
Estás mirando la variable incorrecta. Es necesario que $ J ( theta) $ sea convexo (en función de $ theta $), por lo que se necesita que $ Cost (h _ { theta} (x), y) $ sea convexo función de $ theta $, no $ x $. Tenga en cuenta que la función dentro del sigmoide es lineal en $ theta $.
Considere una función dos veces diferenciable de una variable $ f (z) $. Si la segunda derivada de $ f (z) $ es (siempre) no negativa, entonces $ f (z) $ es convexa. Así que considere la función $$ j (z) = -y log ( sigma (z)) – (1-y) log (1- sigma (z)) $$ donde $ sigma (x) = sigmoide (x) $ y $ 0 leq y leq 1 $ es una constante. Puede demostrar que $ j (z) $ es convexo tomando la segunda derivada. Compare con el caso de que tome $$ k (z) = y sigma (z) ^ 2 + (1-y) (1- sigma (z)) ^ 2 $$ ¿es $ k (z) $ convexo? ¿Qué pasa si tomas $ tilde { sigma} (z) = sigmoid (1 + z ^ 2 + z ^ 3) $ en lugar de $ sigma $ (z)?
Ahora, la composición de una función convexa con una función lineal es convexa (¿puedes mostrar esto?). Tenga en cuenta que $ Z ( theta): = theta ^ T cdot X $ es una función lineal en $ theta $ (donde $ X $ es una matriz constante). Por lo tanto, $ J ( theta): = j (Z ( theta)) $ es convexo como una función en $ theta $.