Abstract
Subset selection that selects the best k variables from n variables is a fundamental problem in many areas. Pareto optimization for subset selection (called POSS) is a recently proposed approach for subset selection based on Pareto optimization and has shown good approximation performances. In the reproduction of POSS, it uses a fixed mutation rate, which may make POSS get trapped in local optimum. In this paper, we propose a new version of POSS by using a dynamic mutation rate, briefly called DM-POSS. We prove that DM-POSS can achieve the best known approximation guarantee for the application of sparse regression in polynomial time and show that DM-POSS can also empirically perform well.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The datasets are from https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/.
- 2.
The datasets are from https://snap.stanford.edu/data/.
References
Das, A., Kempe, D.: Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In: 28th International Conference on Machine Learning, Bellevue, WA, pp. 1057–1064 (2011)
Davis, G., Mallat, S., Avellaneda, M.: Adaptive Greedy approximations. Constr. Approx. 13(1), 57–98 (1997)
Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: 19th ACM Genetic and Evolutionary Computation Conference, Berlin, Germany, pp. 777–784 (2017)
Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theoret. Comput. Sci. 276(1–2), 51–58 (2002)
Fischer, S., Wegener, I.: The one-dimensional Ising model: mutation versus recombination. Theoret. Comput. Sci. 344(2–3), 208–225 (2005)
Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: 20th Annual Symposium on Theoretical Aspects of Computer Science, London, UK, pp. 415–426 (2003)
Gilbert, A.C., Muthukrishnan, S., Strauss, M.J.: Approximation of functions over redundant dictionaries using coherence. In: 14th Annual ACM-SIAM symposium on Discrete Algorithms, Baltimore, MA, pp. 243–252 (2003)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, D.C., pp. 137–146 (2003)
Miller, A.: Subset Selection in Regression. CRC Press, Boca Raton (2002)
Qian, C., Yu, Y., Zhou, Z.H.: Subset selection by Pareto optimization. In: Advances in Neural Information Processing Systems 28, Montreal, Canada, pp. 1774–1782 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Wu, M., Qian, C., Tang, K. (2018). Dynamic Mutation Based Pareto Optimization for Subset Selection. In: Huang, DS., Gromiha, M., Han, K., Hussain, A. (eds) Intelligent Computing Methodologies. ICIC 2018. Lecture Notes in Computer Science(), vol 10956. Springer, Cham. https://doi.org/10.1007/978-3-319-95957-3_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-95957-3_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-95956-6
Online ISBN: 978-3-319-95957-3
eBook Packages: Computer ScienceComputer Science (R0)