Lower and upper bounds for linkage discovery
For a real-valued function f defined on {0,1}n , the linkage graph of f is a hypergraph that represents the interactions among the input variables with respect to f . In this paper, lower and upper bounds for the number of function evaluations required to discover the linkage graph are rigorously an...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/52340 |
| _version_ | 1826217451144085504 |
|---|---|
| author | Choi, Sung-Soon Jung, Kyomin Moon, Byung-Ro |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Choi, Sung-Soon Jung, Kyomin Moon, Byung-Ro |
| author_sort | Choi, Sung-Soon |
| collection | MIT |
| description | For a real-valued function f defined on {0,1}n , the linkage graph of f is a hypergraph that represents the interactions among the input variables with respect to f . In this paper, lower and upper bounds for the number of function evaluations required to discover the linkage graph are rigorously analyzed in the black box scenario. First, a lower bound for discovering linkage graph is presented. To the best of our knowledge, this is the first result on the lower bound for linkage discovery. The investigation on the lower bound is based on Yao's minimax principle. For the upper bounds, a simple randomized algorithm for linkage discovery is analyzed. Based on the Kruskal-Katona theorem, we present an upper bound for discovering the linkage graph. As a corollary, we rigorously prove that O(n [superscript 2]logn) function evaluations are enough for bounded functions when the number of hyperedges is O(n), which was suggested but not proven in previous works. To see the typical behavior of the algorithm for linkage discovery, three random models of fitness functions are considered. Using probabilistic methods, we prove that the number of function evaluations on the random models is generally smaller than the bound for the arbitrary case. Finally, from the relation between the linkage graph and the Walsh coefficients, it is shown that, for bounded functions, the proposed bounds are eventually the bounds for finding the Walsh coefficients. |
| first_indexed | 2024-09-23T17:03:51Z |
| format | Article |
| id | mit-1721.1/52340 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:03:51Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/523402022-10-03T10:09:24Z Lower and upper bounds for linkage discovery Choi, Sung-Soon Jung, Kyomin Moon, Byung-Ro Massachusetts Institute of Technology. Department of Mathematics Jung, Kyomin Jung, Kyomin lower and upper bounds linkage graph linkage discovery complexity analysis Walsh analysis black box scenario For a real-valued function f defined on {0,1}n , the linkage graph of f is a hypergraph that represents the interactions among the input variables with respect to f . In this paper, lower and upper bounds for the number of function evaluations required to discover the linkage graph are rigorously analyzed in the black box scenario. First, a lower bound for discovering linkage graph is presented. To the best of our knowledge, this is the first result on the lower bound for linkage discovery. The investigation on the lower bound is based on Yao's minimax principle. For the upper bounds, a simple randomized algorithm for linkage discovery is analyzed. Based on the Kruskal-Katona theorem, we present an upper bound for discovering the linkage graph. As a corollary, we rigorously prove that O(n [superscript 2]logn) function evaluations are enough for bounded functions when the number of hyperedges is O(n), which was suggested but not proven in previous works. To see the typical behavior of the algorithm for linkage discovery, three random models of fitness functions are considered. Using probabilistic methods, we prove that the number of function evaluations on the random models is generally smaller than the bound for the arbitrary case. Finally, from the relation between the linkage graph and the Walsh coefficients, it is shown that, for bounded functions, the proposed bounds are eventually the bounds for finding the Walsh coefficients. ICT at Seoul National University Brain Korea 21 Project 2010-03-05T16:21:41Z 2010-03-05T16:21:41Z 2009-02 2008-01 Article http://purl.org/eprint/type/JournalArticle 1089-778X http://hdl.handle.net/1721.1/52340 Sung-Soon Choi, Kyomin Jung, and Byung-Ro Moon. “Lower and Upper Bounds for Linkage Discovery.” Evolutionary Computation, IEEE Transactions on 13.2 (2009): 201-216. © 2009 Institute of Electrical and Electronics Engineers en_US http://dx.doi.org/10.1109/TEVC.2008.928499 IEEE Transactions on Evolutionary Computation, Article is made available in accordance with the publisher’s policy and may be subject to US copyright law. Please refer to the publisher’s site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | lower and upper bounds linkage graph linkage discovery complexity analysis Walsh analysis black box scenario Choi, Sung-Soon Jung, Kyomin Moon, Byung-Ro Lower and upper bounds for linkage discovery |
| title | Lower and upper bounds for linkage discovery |
| title_full | Lower and upper bounds for linkage discovery |
| title_fullStr | Lower and upper bounds for linkage discovery |
| title_full_unstemmed | Lower and upper bounds for linkage discovery |
| title_short | Lower and upper bounds for linkage discovery |
| title_sort | lower and upper bounds for linkage discovery |
| topic | lower and upper bounds linkage graph linkage discovery complexity analysis Walsh analysis black box scenario |
| url | http://hdl.handle.net/1721.1/52340 |
| work_keys_str_mv | AT choisungsoon lowerandupperboundsforlinkagediscovery AT jungkyomin lowerandupperboundsforlinkagediscovery AT moonbyungro lowerandupperboundsforlinkagediscovery |