Algorithms for Optimizing the Ratio of Submodular Functions
Authors: Wenruo Bai, Rishabh Iyer, Kai Wei, Jeff Bilmes
ICML 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we empirically demonstrate the performance and good scalability properties of our algorithms. ... 6. Experiments: We empirically evaluate our proposed algorithmic frameworks for RS minimization, including in particular MMIN, GREEDRATIO, and ELLIPSOIDAPPROX, on a synthetic data set. |
| Researcher Affiliation | Academia | Wenruo Bai WRBAI@UW.EDU Rishabh Iyer RKIYER@U.WASHINGTON.EDU Kai Wei WEIKAI.HUST@GMAIL.COM Jeff Bilmes BILMES@UW.EDU University of Washington, Seattle, WA 98195, USA |
| Pseudocode | Yes | Algorithm 1 A (1 + ϵ)-approximation algorithm for RS minimization using an exact algorithm for DS minimization. ... Algorithm 2 Approx. algorithm for RS minimization using an approximation algorithm for SCSC. ... Algorithm 3 GREEDRATIO for RS minimization. ... Algorithm 4 ELLIPSOIDAPPROX. ... Algorithm 5 MMIN for RS minimization. |
| Open Source Code | No | The paper does not provide any statement or link indicating that open-source code for the described methodology is available. |
| Open Datasets | No | We empirically evaluate our proposed algorithmic frameworks for RS minimization, including in particular MMIN, GREEDRATIO, and ELLIPSOIDAPPROX, on a synthetic data set. In particular, we evaluate on a generalized form of the F-measure function: Fλ(X) = |Γ(X) T| λ|T| + (1 λ)|Γ(X)|, (32) where 0 λ 1 is a parameter that determines a tradeoff weight between precision and recall. Note Fλ=0.5 is the same as the F-measure function defined in Eqn. 3. We instantiate the F-measure function on a randomly generated bipartite graph G(U, W, E). The bipartite graph is defined with |U| = 100 and |W| = 100. We define an edge between u U and w W independently with probability p = 0.05. The set of targets T W is also randomly chosen with a fixed size 20, i.e., |T| = 20. We run the experiments on 10 instances of the randomly and independently generated data, and we report the averaged results. |
| Dataset Splits | No | The paper describes the generation of synthetic data for evaluation but does not specify distinct training, validation, or test splits for a model or algorithm, as the algorithms themselves are being evaluated rather than a trained model. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run the experiments. |
| Software Dependencies | No | The paper does not provide any specific software dependencies with version numbers. |
| Experiment Setup | Yes | We instantiate the F-measure function on a randomly generated bipartite graph G(U, W, E). The bipartite graph is defined with |U| = 100 and |W| = 100. We define an edge between u U and w W independently with probability p = 0.05. The set of targets T W is also randomly chosen with a fixed size 20, i.e., |T| = 20. We run the experiments on 10 instances of the randomly and independently generated data, and we report the averaged results. ... As a baseline, we also implement a random sampling method, where we randomly choose 100 subsets X U with size |X| = 50 and report their averaged function valuation in terms of Fλ and their standard deviation. In Figure 1, we compare the performance of all methods on with the varying λ. |