Antecedentes: No aprendizado de máquina, geralmente trabalhamos com modelos gráficos para representar funções de densidade de probabilidade dimensional alta. Se descartamos a restrição de que uma densidade se integra (soma) a 1, obtemos uma função de energia estruturada em gráfico não normalizada .
Suponha que tenhamos uma função energética, , definida em um gráfico . Há uma variável para cada vértice do gráfico e há funções unárias e em pares com valor real, e , respectivamente. A energia total é então
Se todos os são binários, podemos pensar em um como indicando associação ao conjunto e, com apenas um pequeno abuso de terminologia, fale sobre submodularidade. Nesse caso, uma função de energia é submodular se . Normalmente, estamos interessados em encontrar a configuração que minimize a energia, .
Parece haver uma conexão entre minimizar uma função de energia submodular e funções booleanas monótonas: se abaixarmos a energia de alguns \ theta_i (x_i = 1) para qualquer (ou seja, aumentar sua preferência para ser "verdadeiro"), então o ideal a atribuição de qualquer variável só pode mudar de 0 para 1 ("false" para "true"). Se todos os estiverem restritos a 0 ou 1, teremos funções booleanas monótonas:
onde, como acima, .
Pergunta: Podemos representar todas as funções booleanas monótonas usando essa configuração variando os termos em pares, ? E se permitirmos que seja uma função de energia submodular arbitrária? Por outro lado, podemos representar todos os problemas de minimização submodular como um conjunto defunções booleanas monótonas?
Você pode sugerir referências que me ajudarão a entender melhor essas conexões? Não sou um cientista da computação teórico, mas estou tentando entender se há informações sobre funções booleanas monótonas que não são capturadas ao pensar nos termos de minimização submodular.