Pseudoboolovská funkce - Pseudo-Boolean function

v matematika a optimalizace, a pseudobolská funkce je funkce formuláře

${ displaystyle f: mathbf {B} ^ {n} rightarrow mathbb {R}}$,

kde B = {0, 1} je a Booleovská doména a n je nezáporné celé číslo zvané arity funkce. A Booleovská funkce je pak speciální případ, kdy jsou hodnoty omezeny také na 0,1.

Zastoupení

Libovolná pseudobolská funkce může být napsána jednoznačně jako a vícelineární polynom:^[1][2]

${ displaystyle f ({ boldsymbol {x}}) = a + součet _ {i} a_ {i} x_ {i} + součet _ {i$

The stupeň pseudobolské funkce je jednoduše stupeň polynomiální v tomto zobrazení.

V mnoha nastaveních (např. V Fourierova analýza pseudoboleovských funkcí ), pseudobolská funkce je považována za funkci ${ displaystyle f}$ že mapy ${ displaystyle {- 1,1 } ^ {n}}$ na ${ displaystyle mathbb {R}}$. Opět v tomto případě můžeme jednoznačně psát ${ displaystyle f}$ jako vícelineární polynom:${ displaystyle f (x) = součet _ {I subseteq [n]} { hat {f}} (I) prod _ {i in I} x_ {i},}$ kde ${ displaystyle { hat {f}} (I)}$ jsou Fourierovy koeficienty ${ displaystyle f}$ a ${ displaystyle [n] = {1, ..., n }}$.

Optimalizace

Minimalizace (nebo ekvivalentní maximalizace) pseudobolské funkce je NP-tvrdé. To lze snadno zjistit například formulováním maximální řez problém jako maximalizace pseudobolské funkce.^[3]

Submodularita

The funkce submodulární sady lze chápat jako speciální třídu pseudoboleovských funkcí, která je ekvivalentní podmínce

${ displaystyle f ({ boldsymbol {x}}) + f ({ boldsymbol {y}}) geq f ({ boldsymbol {x}} klín { boldsymbol {y}}) + f ({ boldsymbol {x}} vee { boldsymbol {y}}), ; forall { boldsymbol {x}}, { boldsymbol {y}} in mathbf {B} ^ {n} ,.}$

Toto je důležitá třída pseudoboleovských funkcí, protože mohou být minimalizován v polynomiálním čase.

Dualita střechy

Li F je kvadratický polynom, koncept zvaný dualita střechy lze použít k získání dolní meze pro její minimální hodnotu.^[3] Dualita střechy může také poskytnout částečné přiřazení proměnných, což naznačuje některé z hodnot minimalizátoru pro polynom. Bylo vyvinuto několik různých metod získání dolních mezí, aby se později ukázalo, že jsou ekvivalentní tomu, co se nyní nazývá duální střecha.^[3]

Kvadratizace

Pokud je stupeň F je větší než 2, lze vždy použít redukce získat ekvivalentní kvadratický problém s dalšími proměnnými. Kniha s otevřeným zdrojovým kódem na toto téma, převážně napsaná autorem Nike Dattani, obsahuje desítky různých kvadratizačních metod^[4].

Jednou z možných redukcí je

${ displaystyle displaystyle -x_ {1} x_ {2} x_ {3} = min _ {z in mathbf {B}} z (2-x_ {1} -x_ {2} -x_ {3} )}$

Existují i ​​další možnosti, například

${ displaystyle displaystyle -x_ {1} x_ {2} x_ {3} = min _ {z in mathbf {B}} z (-x_ {1} + x_ {2} + x_ {3}) -x_ {1} x_ {2} -x_ {1} x_ {3} + x_ {1}.}$

Různá snížení vedou k různým výsledkům. Vezměme si například následující kubický polynom:^[5]

${ displaystyle displaystyle f ({ boldsymbol {x}}) = - 2x_ {1} + x_ {2} -x_ {3} + 4x_ {1} x_ {2} + 4x_ {1} x_ {3} - 2x_ {2} x_ {3} -2x_ {1} x_ {2} x_ {3}.}$

Pomocí první redukce následované dualitou střechy získáme dolní hranici -3 a žádný údaj o tom, jak přiřadit tři proměnné. Pomocí druhé redukce získáme (těsnou) dolní hranici -2 a optimální přiřazení každé proměnné (což je ${ displaystyle {(0,1,1)}}$).

Polynomiální kompresní algoritmy

Zvažte pseudobolskou funkci ${ displaystyle f}$ jako mapování z ${ displaystyle {- 1,1 } ^ {n}}$ na ${ displaystyle mathbb {R}}$. Pak ${ displaystyle f (x) = součet _ {I subseteq [n]} { hat {f}} (I) prod _ {i in I} x_ {i}.}$ Předpokládejme, že každý koeficient ${ displaystyle { hat {f}} (I)}$ je integrální. Pak na celé číslo ${ displaystyle k}$ problém P rozhodování, zda ${ displaystyle f (x)}$ je více nebo rovno ${ displaystyle k}$ je NP-kompletní. Je prokázáno v ^[6] že v polynomiálním čase můžeme buď vyřešit P, nebo snížit počet proměnných na ${ displaystyle O (k ^ {2} log k)}$.Nechat ${ displaystyle r}$ být mírou výše uvedeného vícelineárního polynomu pro ${ displaystyle f}$. Pak ^[6] dokázal, že v polynomiálním čase můžeme buď vyřešit P, nebo snížit počet proměnných na ${ displaystyle r (k-1)}$.

Viz také

• Booleovská funkce
• Kvadratická pseudobolská optimalizace

Poznámky

Reference

• Boros, E .; Hammer, P. L. (2002). „Pseudoboleovská optimalizace“. Diskrétní aplikovaná matematika. 123 (1–3): 155–225. doi:10.1016 / S0166-218X (01) 00341-9.
• Crowston, R .; Fellows, M .; Gutin, G .; Jones, M .; Rosamond, F .; Thomasse, S .; Yeo, A. (2011). "Simultánně uspokojující lineární rovnice nad GF (2): MaxLin2 a Max-r-Lin2 parametrizovány nad průměrem". Proc. FSTTCS 2011. arXiv:1104.1135. Bibcode:2011arXiv1104.1135C.
• Ishikawa, H. (2011). "Transformace obecné binární minimalizace MRF na případ prvního řádu". Transakce IEEE na analýze vzorů a strojové inteligenci. 33 (6): 1234–1249. CiteSeerX  10.1.1.675.2183. doi:10.1109 / tpami.2010.91. PMID  20421673. S2CID  17314555.
• Kahl, F .; Strandmark, P. (2011). Zobecněná dualita střechy pro pseudobolskou optimalizaci (PDF). Mezinárodní konference o počítačovém vidění.
• O'Donnell, Ryan (2008). "Některá témata v analýze booleovských funkcí". ECCC  TR08-055. Externí odkaz v | deník = (Pomoc)
• Rother, C .; Kolmogorov, V .; Lempitsky, V .; Szummer, M. (2007). Optimalizace binárních MRF pomocí rozšířené střechy (PDF). Konference o počítačovém vidění a rozpoznávání vzorů.