Antecedentes: en el aprendizaje automático, a menudo trabajamos con modelos gráficos para representar funciones de densidad de probabilidad de alta dimensión. Si descartamos la restricción de que una densidad se integra (sumas) a 1, obtenemos una función de energía estructurada en gráficos no normalizada .
Supongamos que tenemos una función de energía, , definida en un gráfico . Hay una variable para cada vértice de la gráfica, y hay funciones unarias y por pares de valores reales, \ theta_i (x_i): i \ in \ mathcal {V} y \ theta_ {ij} (x_i, x_j): ij \ in \ mathcal {E} , respectivamente. La energía completa es entonces
Si todas las son binarias, podemos pensar en una como una membresía establecida y con un pequeño abuso de terminología se habla de submodularidad. En este caso, una función de energía es submodular iff . Normalmente estamos interesados en encontrar la configuración que minimice la energía, .
Parece haber una conexión entre minimizar una función de energía submodular y funciones booleanas monótonas: si disminuimos la energía de algunos para cualquier (es decir, aumentamos su preferencia para que sea "verdadera"), entonces el óptimo la asignación de cualquier variable solo puede cambiar de 0 a 1 ("falso" a "verdadero"). Si todo está restringido a 0 o 1, entonces tenemos funciones booleanas monótonas:
donde como arriba, .
Pregunta: ¿Podemos representar todas las funciones booleanas monótonas utilizando esta configuración variando los términos por pares, ? ¿Qué pasa si permitimos que sea una función de energía submodular arbitraria? Por el contrario, ¿podemos representar todos los problemas de minimización submodular como un conjunto defunciones booleanas monótonas?
¿Puede sugerir referencias que me ayudarán a comprender mejor estas conexiones? No soy un científico de la computación teórico, pero estoy tratando de entender si hay ideas sobre las funciones booleanas monótonas que no se capturan al pensar en los términos de minimización submodular.