Permintaan Referensi: Minimisasi Submodular dan Fungsi Monote Boolean

Latar Belakang: Dalam pembelajaran mesin, kami sering bekerja dengan model grafis untuk mewakili fungsi kepadatan probabilitas dimensi tinggi. Jika kita membuang batasan yang mengintegrasikan kepadatan (jumlah) ke 1, kita mendapatkan fungsi energi terstruktur grafik yang tidak dinormalisasi .

Misalkan kita memiliki fungsi energi seperti itu, , didefinisikan pada grafik . Ada satu variabel untuk setiap simpul grafik, dan ada fungsi unary dan pairwise bernilai nyata, dan , masing-masing. Energi penuh ituG = ( V , E ) x θ i ( x i ) : i ∈ V θ i j ( x i , x j ) : i j ∈ $E$$G = (\mathcal{V}, \mathcal{E})$$x$$\theta_i(x_i) : i \in \mathcal{V}$$\theta_{ij}(x_i, x_j) : ij \in \mathcal{E}$

$$E(\mathbf{x}) = \sum_{i \in \mathcal{V}} \theta_i(x_i) + \sum_{ij \in \mathcal{E}} \theta_{ij}(x_i, x_j)$$

Jika semua adalah biner, kita dapat menganggap sebagai mengindikasikan keanggotaan yang ditetapkan dan dengan sedikit penyalahgunaan terminologi, bicaralah tentang submodularity. Dalam hal ini, fungsi energi adalah submodular . Kami biasanya tertarik untuk menemukan konfigurasi yang meminimalkan energi, \ mathbf {x} ^ * = \ arg \ min _ {\ mathbf {x}} E (\ mathbf {x}) . x θ i j ( 0 , 0 ) + θ i j ( 1 , 1 ) ≤ θ i j ( 0 , 1 ) + θ i j ( 1 , 0 ) x ∗ = arg min x E ( x$x \in \mathbf{x}$$x$$\theta_{ij}(0, 0) + \theta_{ij}(1, 1) \le \theta_{ij}(0, 1) + \theta_{ij}(1, 0)$$\mathbf{x}^* = \arg \min_{\mathbf{x}} E(\mathbf{x})$

Tampaknya ada hubungan antara meminimalkan fungsi energi submodular dan fungsi boolean monoton: jika kita menurunkan energi beberapa $\theta_i(x_i=1)$ untuk setiap $x_i$ (yaitu, meningkatkan preferensi untuk menjadi "benar"), maka optimal penetapan variabel $x_i^* \in \mathbf{x}^*$ pun hanya dapat berubah dari 0 menjadi 1 ("false" menjadi "true"). Jika semua $\theta_i$ dibatasi menjadi 0 atau 1, maka kita memiliki $|\mathcal{V}|$fungsi boolean monoton:

$$f_i(\mathbf{\theta}) = x_i^*$$

dimana seperti di atas, $\mathbf{x^*} = \arg \min_{\mathbf{x}} E(\mathbf{x})$ .

Pertanyaan: Bisakah kita mewakili semua fungsi boolean monoton menggunakan pengaturan ini dengan memvariasikan istilah berpasangan, ? Bagaimana jika kita membiarkan menjadi fungsi energi submodular yang berubah-ubah? Sebaliknya, dapatkah kita merepresentasikan semua masalah minimisasi submodular sebagai seperangkatfungsi boolean monoton?$\theta_{ij}$$E$$|\mathcal{V}|$

Bisakah Anda menyarankan referensi yang akan membantu saya lebih memahami koneksi ini? Saya bukan ilmuwan komputer teoretis, tetapi saya mencoba memahami jika ada wawasan tentang fungsi boolean monoton yang tidak ditangkap dengan berpikir dalam istilah minimisasi submodular.

Sejauh yang saya mengerti, kasus minimisasi submodular menangkap semua yang bisa dikatakan tentang kasus Boolean monoton, dan fungsi Boolean submodular biner dapat mengekspresikan semua fungsi Boolean submodular. Namun, jika domain adalah non-Boolean, maka fungsi submodular biner tidak cukup untuk mengekspresikan semua fungsi submodular, bahkan jika variabel tersembunyi dapat diperkenalkan. (Mohon maaf jika saya melewatkan kehalusan dalam ungkapan masalah Anda yang tepat.)

Keadaan seni dibahas dalam makalah yang bagus ini yang memiliki banyak tautan ke pekerjaan terkait, dan itu juga membuat tautan ke visi komputer cukup eksplisit:

• Stanislav Živný, David A. Cohen, Peter G. Jeavons, Kekuatan ekspresif fungsi submodular biner , DAM 157 3347-3358, 2009. doi: 10.1016 / j.dam.2009.07.001 ( pracetak )

Jika pertanyaan Anda berikutnya adalah tentang aproksimasi, makalah terbaru ini membahas versi aproksimasi:

• Dorit S. Hochbaum, Masalah submodular - perkiraan dan algoritma , arXiv: 1010.1945

Edit: tautan tetap.