Por qué 0-1 la función de pérdida es insuperable

Question

En Ian Goodfellow del aprendizaje profundo libro, está escrito que

A veces, la pérdida de la función en realidad la atención sobre (es decir, error de clasificación) no es uno que se puede optimizar de manera eficiente. Por ejemplo, exactamente minimizando la espera 0-1 pérdida es generalmente insolubles (exponencial en la entrada de la dimensión), incluso para un clasificador lineal. En tales situaciones, uno normalmente se optimiza un sustituto de la función de pérdida lugar, que actúa como un proxy, pero tiene sus ventajas.

Yo no entiendo por qué 0-1 pérdida es intratable o cómo es exponencial en la entrada de las dimensiones?

Answer 1

El 0-1 de la pérdida de la función no es convexo y discontinuo, por lo que (sub)gradiente de métodos no pueden ser aplicados. Para la clasificación binaria con un separador lineal, esta función de pérdida puede ser formulado como la búsqueda de la $\beta$ que minimiza el valor promedio de la función del indicador de $\mathbf{1}(y_{i}\beta\mathbf{x}_{i} \leq 0)$ $i$ de las muestras. Este es exponencial en las entradas, ya que existen dos valores posibles para cada par, hay $2^{n}$ configuraciones posibles de verificación para $n$ total de puntos de la muestra. Esto es conocido por ser NP-duro. Conocer el valor actual de la función de pérdida no proporciona ninguna pista en cuanto a cómo se debe posiblemente a modificar su actual solución para mejorar, ya que podría derivar si gradiente de métodos para convexo o funciones continuas.

Answer 2

El error de clasificación es, de hecho, a veces manejable. Puede ser optimizado de manera eficiente - aunque no exactamente - el uso de la Nelder-Mead el método, como se muestra en este artículo:

https://www.computer.org/csdl/trans/tp/1994/04/i0420-abs.html

"La dimensión de la reducción es el proceso de transformación multidimensional vectores en un espacio de pocas dimensiones. En el reconocimiento de patrones, es a menudo se desea que la tarea se realiza sin pérdida significativa de clasificación de la información. El error de Bayes es un ideal criterio para este propósito; sin embargo, se sabe que es muy difícil para el tratamiento matemático. En consecuencia, subóptima de los criterios de se utiliza en la práctica. Proponemos una alternativa criterio, basado en la estimación del error de Bayes, que es de esperar que más cerca de la óptima criterio de los criterios actualmente en uso. Un algoritmo lineal reducción de dimensiones, con base en este criterio, se concibe y implementado. Los experimentos demuestran su rendimiento superior en comparación con los sistemas convencionales de algoritmos."

La Bayes de error que se menciona aquí es básicamente el 0-1 de la pérdida.

Este trabajo fue realizado en el contexto de la dimensión lineal de reducción. Yo no sé cuán efectivo sería para la formación de aprendizaje profundo redes. Pero el punto es, y la respuesta a la pregunta: 0-1 pérdida no es universalmente intratable. Puede ser optimizado relativamente bien por lo menos algunos tipos de modelos.