Solicitação de referência: Minimização submodular e funções booleanas monótonas

13

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ãoEG=(V,E)xθi(xi):iVθij(xi,xj):ijE

E(x)=iVθi(xi)+ijEθij(xi,xj)

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, .xxxθij(0,0)+θij(1,1)θij(0,1)+θij(1,0)x=argminxE(x)

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)θi(xi=1) para qualquer xi (ou seja, aumentar sua preferência para ser "verdadeiro"), então o ideal a atribuição de qualquer variável xix só pode mudar de 0 para 1 ("false" para "true"). Se todos os θi estiverem restritos a 0 ou 1, teremos |V|funções booleanas monótonas:

fi(θ)=xi

onde, como acima, x=argminxE(x) .

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?θijE|V|

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.

dan_x
fonte

Respostas:

7

Pelo que entendi, o caso de minimização submodular captura tudo o que se pode dizer sobre o caso booleano monótono, e as funções booleanas submodulares binárias podem expressar todas as funções booleanas submodulares. No entanto, se o domínio não for booleano, as funções submodulares binárias não serão suficientes para expressar todas as funções submodulares, mesmo que variáveis ​​ocultas possam ser introduzidas. (Peço desculpas se eu perdi uma sutileza na formulação precisa do seu problema.)

O estado da arte é discutido neste belo artigo, que possui muitos links para trabalhos relacionados, e isso também torna os links para a visão computacional bastante explícitos:

Caso sua próxima pergunta seja sobre aproximação, este artigo recente analisa a versão de aproximação:

  • Dorit S. Hochbaum, problemas submodulares - aproximações e algoritmos , arXiv: 1010.1945

Editar: link fixo.

András Salamon
fonte
Embora o link (pré-impressão) me leve a um papel diferente do doi: link.
21410 dan_x
@dan x: corrigido o link, obrigado pelo aviso.
András Salamon