Efficient minimization of higher order submodular functions using monotonic Boolean functions
<p>Submodular function minimization is a key problem in a wide variety of applications in machine learning, economics, game theory, computer vision, and many others. The general solver has a complexity of O(n3 log2 n:E + n4logO(1)n) where E is the time required to evaluate the function and n i...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2017
|
| _version_ | 1797074774533341184 |
|---|---|
| author | Ramalingam, S Russell, C Ladický, L Torr, P |
| author_facet | Ramalingam, S Russell, C Ladický, L Torr, P |
| author_sort | Ramalingam, S |
| collection | OXFORD |
| description | <p>Submodular function minimization is a key problem in a wide variety of applications in machine learning, economics, game theory, computer vision, and many others. The general solver has a complexity of O(n3 log2 n:E + n4logO(1)n) where E is the time required to evaluate the function and n is the number of variables [32]. On the other hand, many computer vision and machine learning problems are defined over special subclasses of submodular functions that can be written as the sum of many submodular cost functions defined over cliques containing few variables. In such functions, the pseudo-Boolean (or polynomial) representation [3] of these subclasses are of degree (or order, or clique size) k where k << n. In this work, we develop efficient algorithms for the minimization of this useful subclass of submodular functions. To do this, we define novel mapping that transform submodular functions of order k into quadratic ones. The underlying idea is to use auxiliary variables to model the higher order terms and the transformation is found using a carefully constructed linear program. In particular, we model the auxiliary variables as monotonic Boolean functions, allowing us to obtain a compact transformation using as few auxiliary variables as possible. The transformed quadratic function can be efficiently minimized using the standard maxflow algorithm with a time complexity of O((n + m)3) where m is the total number of auxiliary variables involved in transforming all the higher order terms to quadratic ones. Specifically, we show that our approach for fourth order function requires only 2 auxiliary variables in contrast to 30 or more variables used in existing approaches. In the general case, we give an upper bound for the number or auxiliary variables required to transform a function of order k using Dedekind number, which is substantially lower than the existing bound of 22k .</p> |
| first_indexed | 2024-03-06T23:41:03Z |
| format | Journal article |
| id | oxford-uuid:6f5354a2-3752-4602-b344-7095f36f0c80 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T23:41:03Z |
| publishDate | 2017 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:6f5354a2-3752-4602-b344-7095f36f0c802022-03-26T19:29:59ZEfficient minimization of higher order submodular functions using monotonic Boolean functionsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:6f5354a2-3752-4602-b344-7095f36f0c80Symplectic Elements at OxfordElsevier2017Ramalingam, SRussell, CLadický, LTorr, P<p>Submodular function minimization is a key problem in a wide variety of applications in machine learning, economics, game theory, computer vision, and many others. The general solver has a complexity of O(n3 log2 n:E + n4logO(1)n) where E is the time required to evaluate the function and n is the number of variables [32]. On the other hand, many computer vision and machine learning problems are defined over special subclasses of submodular functions that can be written as the sum of many submodular cost functions defined over cliques containing few variables. In such functions, the pseudo-Boolean (or polynomial) representation [3] of these subclasses are of degree (or order, or clique size) k where k << n. In this work, we develop efficient algorithms for the minimization of this useful subclass of submodular functions. To do this, we define novel mapping that transform submodular functions of order k into quadratic ones. The underlying idea is to use auxiliary variables to model the higher order terms and the transformation is found using a carefully constructed linear program. In particular, we model the auxiliary variables as monotonic Boolean functions, allowing us to obtain a compact transformation using as few auxiliary variables as possible. The transformed quadratic function can be efficiently minimized using the standard maxflow algorithm with a time complexity of O((n + m)3) where m is the total number of auxiliary variables involved in transforming all the higher order terms to quadratic ones. Specifically, we show that our approach for fourth order function requires only 2 auxiliary variables in contrast to 30 or more variables used in existing approaches. In the general case, we give an upper bound for the number or auxiliary variables required to transform a function of order k using Dedekind number, which is substantially lower than the existing bound of 22k .</p> |
| spellingShingle | Ramalingam, S Russell, C Ladický, L Torr, P Efficient minimization of higher order submodular functions using monotonic Boolean functions |
| title | Efficient minimization of higher order submodular functions using monotonic Boolean functions |
| title_full | Efficient minimization of higher order submodular functions using monotonic Boolean functions |
| title_fullStr | Efficient minimization of higher order submodular functions using monotonic Boolean functions |
| title_full_unstemmed | Efficient minimization of higher order submodular functions using monotonic Boolean functions |
| title_short | Efficient minimization of higher order submodular functions using monotonic Boolean functions |
| title_sort | efficient minimization of higher order submodular functions using monotonic boolean functions |
| work_keys_str_mv | AT ramalingams efficientminimizationofhigherordersubmodularfunctionsusingmonotonicbooleanfunctions AT russellc efficientminimizationofhigherordersubmodularfunctionsusingmonotonicbooleanfunctions AT ladickyl efficientminimizationofhigherordersubmodularfunctionsusingmonotonicbooleanfunctions AT torrp efficientminimizationofhigherordersubmodularfunctionsusingmonotonicbooleanfunctions |