---
_id: '46310'
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.'
author:
- first_name: Jonathan
  full_name: Heins, Jonathan
  last_name: Heins
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Janina
  full_name: Pohl, Janina
  last_name: Pohl
- first_name: Moritz
  full_name: Seiler, Moritz
  id: '105520'
  last_name: Seiler
- first_name: Heike
  full_name: Trautmann, Heike
  id: '100740'
  last_name: Trautmann
  orcid: 0000-0002-9788-8282
- first_name: Pascal
  full_name: Kerschke, Pascal
  last_name: Kerschke
citation:
  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>
  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>
  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} }'
  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>.'
  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>.'
  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>.
  short: J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, Theoretical
    Computer Science 940 (2023) 123–145.
date_created: 2023-08-04T07:18:38Z
date_updated: 2024-06-10T11:57:21Z
department:
- _id: '34'
- _id: '819'
doi: https://doi.org/10.1016/j.tcs.2022.10.019
intvolume: '       940'
keyword:
- Feature normalization
- Algorithm selection
- Traveling salesperson problem
language:
- iso: eng
page: 123-145
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - 0304-3975
status: public
title: A study on the effects of normalized TSP features for automated algorithm selection
type: journal_article
user_id: '15504'
volume: 940
year: '2023'
...
---
_id: '48881'
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.'
author:
- first_name: Jonathan
  full_name: Heins, Jonathan
  last_name: Heins
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Janina
  full_name: Pohl, Janina
  last_name: Pohl
- first_name: Moritz
  full_name: Seiler, Moritz
  last_name: Seiler
- first_name: Heike
  full_name: Trautmann, Heike
  last_name: Trautmann
- first_name: Pascal
  full_name: Kerschke, Pascal
  last_name: Kerschke
citation:
  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.
  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} }'
  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.'
  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.
  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.'
date_created: 2023-11-14T15:58:58Z
date_updated: 2023-12-13T10:47:23Z
department:
- _id: '819'
extern: '1'
keyword:
- automated algorithm selection
- graph theory
- instance features
- normalization
- traveling salesperson problem (TSP)
language:
- iso: eng
page: 1–15
place: New York, NY, USA
publication: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
  Algorithms
publication_identifier:
  isbn:
  - 978-1-4503-8352-3
publisher: Association for Computing Machinery
status: public
title: On the Potential of Normalized TSP Features for Automated Algorithm Selection
type: book_chapter
user_id: '102979'
year: '2021'
...
---
_id: '11869'
abstract:
- lang: eng
  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\%
author:
- first_name: M.
  full_name: Lieb, M.
  last_name: Lieb
- first_name: Reinhold
  full_name: Haeb-Umbach, Reinhold
  id: '242'
  last_name: Haeb-Umbach
citation:
  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>'
  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>
  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} }'
  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.
  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>.
  short: 'M. Lieb, R. Haeb-Umbach, in: IEEE International Conference on Acoustics,
    Speech, and Signal Processing (ICASSP 2000), 2000, pp. II1105-II1108 vol.2.'
date_created: 2019-07-12T05:29:50Z
date_updated: 2022-01-06T06:51:11Z
department:
- _id: '54'
doi: 10.1109/ICASSP.2000.859157
intvolume: '         2'
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
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://groups.uni-paderborn.de/nt/pubs/2000/LiHa00.pdf
oa: '1'
page: II1105-II1108 vol.2
publication: IEEE International Conference on Acoustics, Speech, and Signal Processing
  (ICASSP 2000)
status: public
title: LDA derived cepstral trajectory filters in adverse environmental conditions
type: conference
user_id: '44006'
volume: 2
year: '2000'
...