[{"year":"2023","page":"123-145","intvolume":"       940","citation":{"short":"J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, Theoretical Computer Science 940 (2023) 123–145.","bibtex":"@article{Heins_Bossek_Pohl_Seiler_Trautmann_Kerschke_2023, title={A study on the effects of normalized TSP features for automated algorithm selection}, volume={940}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2022.10.019\">https://doi.org/10.1016/j.tcs.2022.10.019</a>}, journal={Theoretical Computer Science}, author={Heins, Jonathan and Bossek, Jakob and Pohl, Janina and Seiler, Moritz and Trautmann, Heike and Kerschke, Pascal}, year={2023}, pages={123–145} }","mla":"Heins, Jonathan, et al. “A Study on the Effects of Normalized TSP Features for Automated Algorithm Selection.” <i>Theoretical Computer Science</i>, vol. 940, 2023, pp. 123–45, doi:<a href=\"https://doi.org/10.1016/j.tcs.2022.10.019\">https://doi.org/10.1016/j.tcs.2022.10.019</a>.","apa":"Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., &#38; Kerschke, P. (2023). A study on the effects of normalized TSP features for automated algorithm selection. <i>Theoretical Computer Science</i>, <i>940</i>, 123–145. <a href=\"https://doi.org/10.1016/j.tcs.2022.10.019\">https://doi.org/10.1016/j.tcs.2022.10.019</a>","ama":"Heins J, Bossek J, Pohl J, Seiler M, Trautmann H, Kerschke P. A study on the effects of normalized TSP features for automated algorithm selection. <i>Theoretical Computer Science</i>. 2023;940:123-145. doi:<a href=\"https://doi.org/10.1016/j.tcs.2022.10.019\">https://doi.org/10.1016/j.tcs.2022.10.019</a>","ieee":"J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, and P. Kerschke, “A study on the effects of normalized TSP features for automated algorithm selection,” <i>Theoretical Computer Science</i>, vol. 940, pp. 123–145, 2023, doi: <a href=\"https://doi.org/10.1016/j.tcs.2022.10.019\">https://doi.org/10.1016/j.tcs.2022.10.019</a>.","chicago":"Heins, Jonathan, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann, and Pascal Kerschke. “A Study on the Effects of Normalized TSP Features for Automated Algorithm Selection.” <i>Theoretical Computer Science</i> 940 (2023): 123–45. <a href=\"https://doi.org/10.1016/j.tcs.2022.10.019\">https://doi.org/10.1016/j.tcs.2022.10.019</a>."},"publication_identifier":{"issn":["0304-3975"]},"title":"A study on the effects of normalized TSP features for automated algorithm selection","doi":"https://doi.org/10.1016/j.tcs.2022.10.019","date_updated":"2024-06-10T11:57:21Z","volume":940,"date_created":"2023-08-04T07:18:38Z","author":[{"first_name":"Jonathan","full_name":"Heins, Jonathan","last_name":"Heins"},{"id":"102979","full_name":"Bossek, Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"first_name":"Janina","full_name":"Pohl, Janina","last_name":"Pohl"},{"first_name":"Moritz","last_name":"Seiler","full_name":"Seiler, Moritz","id":"105520"},{"last_name":"Trautmann","orcid":"0000-0002-9788-8282","full_name":"Trautmann, Heike","id":"100740","first_name":"Heike"},{"last_name":"Kerschke","full_name":"Kerschke, Pascal","first_name":"Pascal"}],"abstract":[{"lang":"eng","text":"Classic automated algorithm selection (AS) for (combinatorial) optimization problems heavily relies on so-called instance features, i.e., numerical characteristics of the problem at hand ideally extracted with computationally low-demanding routines. For the traveling salesperson problem (TSP) a plethora of features have been suggested. Most of these features are, if at all, only normalized imprecisely raising the issue of feature values being strongly affected by the instance size. Such artifacts may have detrimental effects on algorithm selection models. We propose a normalization for two feature groups which stood out in multiple AS studies on the TSP: (a) features based on a minimum spanning tree (MST) and (b) nearest neighbor relationships of the input instance. To this end we theoretically derive minimum and maximum values for properties of MSTs and k-nearest neighbor graphs (NNG) of Euclidean graphs. We analyze the differences in feature space between normalized versions of these features and their unnormalized counterparts. Our empirical investigations on various TSP benchmark sets point out that the feature scaling succeeds in eliminating the effect of the instance size. A proof-of-concept AS-study shows promising results: models trained with normalized features tend to outperform those trained with the respective vanilla features."}],"status":"public","publication":"Theoretical Computer Science","type":"journal_article","keyword":["Feature normalization","Algorithm selection","Traveling salesperson problem"],"language":[{"iso":"eng"}],"_id":"46310","department":[{"_id":"34"},{"_id":"819"}],"user_id":"15504"},{"status":"public","abstract":[{"lang":"eng","text":"Classic automated algorithm selection (AS) for (combinatorial) optimization problems heavily relies on so-called instance features, i.e., numerical characteristics of the problem at hand ideally extracted with computationally low-demanding routines. For the traveling salesperson problem (TSP) a plethora of features have been suggested. Most of these features are, if at all, only normalized imprecisely raising the issue of feature values being strongly affected by the instance size. Such artifacts may have detrimental effects on algorithm selection models. We propose a normalization for two feature groups which stood out in multiple AS studies on the TSP: (a) features based on a minimum spanning tree (MST) and (b) a k-nearest neighbor graph (NNG) transformation of the input instance. To this end we theoretically derive minimum and maximum values for properties of MSTs and k-NNGs of Euclidean graphs. We analyze the differences in feature space between normalized versions of these features and their unnormalized counterparts. Our empirical investigations on various TSP benchmark sets point out that the feature scaling succeeds in eliminating the effect of the instance size. Eventually, a proof-of-concept AS-study shows promising results: models trained with normalized features tend to outperform those trained with the respective vanilla features."}],"type":"book_chapter","publication":"Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms","extern":"1","language":[{"iso":"eng"}],"keyword":["automated algorithm selection","graph theory","instance features","normalization","traveling salesperson problem (TSP)"],"user_id":"102979","department":[{"_id":"819"}],"_id":"48881","citation":{"chicago":"Heins, Jonathan, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann, and Pascal Kerschke. “On the Potential of Normalized TSP Features for Automated Algorithm Selection.” In <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, 1–15. New York, NY, USA: Association for Computing Machinery, 2021.","ieee":"J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, and P. Kerschke, “On the Potential of Normalized TSP Features for Automated Algorithm Selection,” in <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–15.","ama":"Heins J, Bossek J, Pohl J, Seiler M, Trautmann H, Kerschke P. On the Potential of Normalized TSP Features for Automated Algorithm Selection. In: <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>. Association for Computing Machinery; 2021:1–15.","apa":"Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., &#38; Kerschke, P. (2021). On the Potential of Normalized TSP Features for Automated Algorithm Selection. In <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i> (pp. 1–15). Association for Computing Machinery.","mla":"Heins, Jonathan, et al. “On the Potential of Normalized TSP Features for Automated Algorithm Selection.” <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, Association for Computing Machinery, 2021, pp. 1–15.","bibtex":"@inbook{Heins_Bossek_Pohl_Seiler_Trautmann_Kerschke_2021, place={New York, NY, USA}, title={On the Potential of Normalized TSP Features for Automated Algorithm Selection}, booktitle={Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, publisher={Association for Computing Machinery}, author={Heins, Jonathan and Bossek, Jakob and Pohl, Janina and Seiler, Moritz and Trautmann, Heike and Kerschke, Pascal}, year={2021}, pages={1–15} }","short":"J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, in: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Association for Computing Machinery, New York, NY, USA, 2021, pp. 1–15."},"page":"1–15","place":"New York, NY, USA","year":"2021","publication_identifier":{"isbn":["978-1-4503-8352-3"]},"title":"On the Potential of Normalized TSP Features for Automated Algorithm Selection","date_created":"2023-11-14T15:58:58Z","author":[{"last_name":"Heins","full_name":"Heins, Jonathan","first_name":"Jonathan"},{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668"},{"full_name":"Pohl, Janina","last_name":"Pohl","first_name":"Janina"},{"first_name":"Moritz","full_name":"Seiler, Moritz","last_name":"Seiler"},{"first_name":"Heike","last_name":"Trautmann","full_name":"Trautmann, Heike"},{"last_name":"Kerschke","full_name":"Kerschke, Pascal","first_name":"Pascal"}],"date_updated":"2023-12-13T10:47:23Z","publisher":"Association for Computing Machinery"},{"citation":{"short":"M. Lieb, R. Haeb-Umbach, in: IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2000), 2000, pp. II1105-II1108 vol.2.","bibtex":"@inproceedings{Lieb_Haeb-Umbach_2000, title={LDA derived cepstral trajectory filters in adverse environmental conditions}, volume={2}, DOI={<a href=\"https://doi.org/10.1109/ICASSP.2000.859157\">10.1109/ICASSP.2000.859157</a>}, booktitle={IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2000)}, author={Lieb, M. and Haeb-Umbach, Reinhold}, year={2000}, pages={II1105-II1108 vol.2} }","mla":"Lieb, M., and Reinhold Haeb-Umbach. “LDA Derived Cepstral Trajectory Filters in Adverse Environmental Conditions.” <i>IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2000)</i>, vol. 2, 2000, pp. II1105-II1108 vol.2, doi:<a href=\"https://doi.org/10.1109/ICASSP.2000.859157\">10.1109/ICASSP.2000.859157</a>.","apa":"Lieb, M., &#38; Haeb-Umbach, R. (2000). LDA derived cepstral trajectory filters in adverse environmental conditions. In <i>IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2000)</i> (Vol. 2, pp. II1105-II1108 vol.2). <a href=\"https://doi.org/10.1109/ICASSP.2000.859157\">https://doi.org/10.1109/ICASSP.2000.859157</a>","chicago":"Lieb, M., and Reinhold Haeb-Umbach. “LDA Derived Cepstral Trajectory Filters in Adverse Environmental Conditions.” In <i>IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2000)</i>, 2:II1105-II1108 vol.2, 2000. <a href=\"https://doi.org/10.1109/ICASSP.2000.859157\">https://doi.org/10.1109/ICASSP.2000.859157</a>.","ieee":"M. Lieb and R. Haeb-Umbach, “LDA derived cepstral trajectory filters in adverse environmental conditions,” in <i>IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2000)</i>, 2000, vol. 2, pp. II1105-II1108 vol.2.","ama":"Lieb M, Haeb-Umbach R. LDA derived cepstral trajectory filters in adverse environmental conditions. In: <i>IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2000)</i>. Vol 2. ; 2000:II1105-II1108 vol.2. doi:<a href=\"https://doi.org/10.1109/ICASSP.2000.859157\">10.1109/ICASSP.2000.859157</a>"},"intvolume":"         2","page":"II1105-II1108 vol.2","year":"2000","main_file_link":[{"url":"https://groups.uni-paderborn.de/nt/pubs/2000/LiHa00.pdf","open_access":"1"}],"doi":"10.1109/ICASSP.2000.859157","title":"LDA derived cepstral trajectory filters in adverse environmental conditions","date_created":"2019-07-12T05:29:50Z","author":[{"first_name":"M.","last_name":"Lieb","full_name":"Lieb, M."},{"id":"242","full_name":"Haeb-Umbach, Reinhold","last_name":"Haeb-Umbach","first_name":"Reinhold"}],"volume":2,"oa":"1","date_updated":"2022-01-06T06:51:11Z","status":"public","abstract":[{"text":"Amongst several data driven approaches for designing filters for the time sequence of spectral parameters, the linear discriminant analysis (LDA) based method has been proposed for automatic speech recognition. Here we apply LDA-based filter design to cepstral features, which better match the inherent assumption of this method that feature vector components are uncorrelated. Extensive recognition experiments have been conducted both on the standard TIMIT phone recognition task and on a proprietary 130-words command word task under various adverse environmental conditions, including reverberant data with real-life room impulse responses and data processed by acoustic echo cancellation algorithms. Significant error rate reductions have been achieved when applying the novel long-range feature filters compared to standard approaches employing cepstral mean normalization and delta and delta-delta features, in particular when facing acoustic echo cancellation scenarios and room reverberation. For example, the phone accuracy on reverberated TIMIT data could be increased from 50.7\\% to 56.0\\%","lang":"eng"}],"type":"conference","publication":"IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2000)","language":[{"iso":"eng"}],"keyword":["acoustic echo cancellation algorithms","adverse environmental conditions","automatic speech recognition","cepstral analysis","cepstral features","cepstral mean normalization","command word task","delta-delta features","delta features","echo suppression","error rate reductions","feature vector components","FIR filters","LDA derived cepstral trajectory filters","linear discriminant analysis","long-range feature filters","phone accuracy","real-life room impulse responses","reverberant data","spectral parameters","speech recognition","standard TIMIT phone recognition task"],"user_id":"44006","department":[{"_id":"54"}],"_id":"11869"}]