Hay bastante trabajo sobre la optimización submodular en Machine Learning (mira el trabajo de Andreas Krause en este campo, él es uno de los investigadores clave para esto).
Para la selección de funciones , sin embargo, hay algunos problemas. La cuestión clave es que el valor de la información de los conjuntos de características no es submodular .
Por ejemplo, considere ejemplos que tienen 2 características binarias X e Y, y una clasificación binaria Z, que es igual a (X xo Y).
El valor de la información de la primera característica por sí solo es 0: sin la segunda característica, esta información es inútil. Del mismo modo, el valor de información de la segunda característica en sí es 0. Pero el valor de información del conjunto de ambas características es 1: con estas dos características podemos predecir exactamente Z. Por lo tanto, no hay rendimientos decrecientes: [matemática] 0 = f (\ {X \}) – f (\ emptyset) <f (\ {X, Y \}) – f (\ {Y \}) = 1 [/ math].
Una de las ideas clave (lo que significa que me pareció sorprendente al principio) está en la investigación de la entropía y la información mutua de conjuntos de variables.
Si observamos un conjunto de variables (por ejemplo, las características y el valor pronosticado para una tarea de clasificación), entonces la entropía conjunta sobre todas las variables desconocidas dados los valores de un subconjunto es una función submodular: conociendo X, la información adicional sobre Y se reduce nuestra incertidumbre total sobre X, Y y Z a lo sumo tanto como cuando no conocemos X. Para esta configuración, excelente, tenemos una función submodular y podemos seleccionar qué características queremos usar con una política codiciosa, obteniendo límites agradables en el peor Rendimiento de caso.
- ¿Cómo ha influido la teoría de conjuntos en el desarrollo de las estructuras de datos?
- ¿Cómo funciona la distribución de probabilidad al construir una nueva variable aleatoria?
- ¿Es log n lo mismo que O (nlogn)?
- ¿Debo especializarme en informática teórica o aprendizaje automático?
- Para un número binario [matemático] n [/ matemático], ¿cuál es la probabilidad de que los dígitos contengan 1 consecutivos? Por ejemplo, un número binario de 3 dígitos tiene 8 posibilidades, y 110, 011 y 111 son los 3 escenarios donde hay 1s consecutivos.
Sin embargo, cuando queremos ver solo la incertidumbre sobre otra variable (por ejemplo, Z en el ejemplo anterior), esto no es submodular.
Resumido: la entropía conjunta es submodular, la entropía condicional no lo es.
