系統発生グラフ検索におけるマルチアームの盗賊、トムソンサンプリング、監視されていない機械学習

系統発生グラフ検索は、多数の高度にパラメーター化された検索手順（分岐スワッピング、摂動、シミュレーションアニーリング、遺伝的アルゴリズムなど）に依存しています。これらの手順は、分析パイプラインの代替ポイントでの有効性が異なります。マルチアームのBandit問題は、これらの手順をより効果的に利用するために、系統発生グラフ検索に適用されます。Thompsonのサンプリングは、検索と最適化「Bandits」のコレクションに適用され、あまり成功していないものよりも生産的な検索戦略を支持しています。この適応ランダムサンプリング戦略は、既存の均一な確率ランダム化検索戦略よりも、ヒューリスト的に最適な系統発生グラフの生成においてより効果的であり、より効率的であることが示されています。この戦略は、特性の事前知識なしに系統発生データセットの多様性に適用できる監視されていない機械学習の形式として機能します。

A phylogenetic graph search relies on a large number of highly parameterized search procedures (e.g. branch-swapping, perturbation, simulated annealing, genetic algorithm). These procedures vary in effectiveness over datasets and at alternative points in analytical pipelines. The multi-armed bandit problem is applied to phylogenetic graph searching to more effectively utilize these procedures. Thompson sampling is applied to a collection of search and optimization "bandits" to favour productive search strategies over those that are less successful. This adaptive random sampling strategy is shown to be more effective in producing heuristically optimal phylogenetic graphs and more time efficient than existing uniform probability randomized search strategies. The strategy acts as a form of unsupervised machine learning that can be applied to a diversity of phylogenetic datasets without prior knowledge of their properties.