Developing Efficient Numerical Algorithms Using Fast Bayesian Random Forests

研究随机森林是你的主要兴趣吗？你想熟练使用顺序蒙特卡罗采样器和并行计算技术吗？GCHQ和CDT正在寻找一位精通随机森林算法的博士候选人，以协助他们开发新的分而治之的方法，以帮助产生更准确的预测。这听起来像是你正在寻找的具有挑战性的项目吗？随机森林（例如在sk-learn中）在数据科学和机器学习中被广泛使用。在这种算法中，每棵树都描述了将输入与输出（在回归上下文中可以是连续值，在分类上下文中可以是离散标签）联系起来的简明规则。然后，随机森林使用树集的多样性来传达适用于任何数据的规则的不确定性。这种简洁性和多样性的结合可能是随机森林的训练算法既快速又通常（非常）有效的原因。从统计学的角度来看，随机森林的训练算法是特别的。人们相信更有原则的方法可以提高性能，这促使人们尝试使用数值贝叶斯技术来估计基于树的数据科学算法的参数。由此产生的方法，如贝叶斯加性回归树（BART）和分类加性回归树（CART），尽管使用的模型可以说没有随机森林中使用的模型那么复杂，但通常速度很慢。这种速度的缺乏是因为像BART和CART这样的算法使用了一种特定的数值贝叶斯技术，即马尔可夫链蒙特卡罗（MCMC）。虽然存在有效的通用MCMC变体（例如No-U-Turn-Sampler (NUTS)），并且可以应用于许多问题，但这些MCMC变体不适用于参数数量未知的环境。因为树可以有不同数量的节点，所以不同数量的参数，像NUTS这样的算法不能用来改善像BART和CART这样基于树的算法的运行时间。NUTS通过使用梯度信息来识别移动方向以优化模型参数来实现其效率。虽然不能在树的背景下计算梯度，但可以使用神经网络文献中称为mini-batch的层次结构来模拟这种设置下的梯度计算。2004年开发了一种利用这一思想的算法，即嵌套训练样本的层次重要性（hint），但它现在很模糊，其潜力在很大程度上尚未开发。此外，在顺序蒙特卡罗（SMC）采样器的背景下，有可能使用更多的最新进展，这是一组可以利用并行处理资源（例如gpu）的算法，并且可以消除顺序刻录阶段的需要，而顺序刻录阶段通常是导致MCMC算法运行时间缓慢的原因。本博士将寻求开发有效的数值贝叶斯算法（可能基于hint和SMC采样器的组合），可用于开发随机森林算法的变体。其目的是，新算法将替代sk-learn中使用的随机森林算法，后者提供相同的接口，但可以使用并行计算资源，使用给定的训练数据集，在相同的运行时间内为GCHQ提供更准确的预测。

Is working with Random Forests a key interest of yours? Would you like to become adept at using Sequential Monte Carlo Samplers and parallel computing techniques? GCHQ and the CDT is looking for a keen PhD candidate who is conversant in Random Forest algorithms to assist them in developing new divide-and-conquer approaches that can help generate more accurate predictions. Does this sound like the challenging project you are looking for?Random Forests (e.g. in sk-learn) are in pervasive use in data science and machine learning. In such algorithms, each tree describes succinct rules that relate the inputs to the outputs (which can be both continuous values, in the context of regression, and discrete labels, in the context of classification). Random Forests then use the diversity of the set of trees to convey uncertainty about which rules apply to any datum. This combination of succinctness and diversity is perhaps why the training algorithms for random forests are both fast and often (remarkably) effective.When seen through the lens of statistics, the training algorithms for Random Forests are ad-hoc. The belief that a more principled approach could lead to improved performance has motivated historic attempts to use numerical Bayesian techniques to estimate the parameters of tree-based data science algorithms. The resulting approaches, e.g. Bayesian Additive Regression Trees (BART) and Classification Additive Regression Trees (CART), despite using models that are arguably less sophisticated than those used in Random Forests, are typically slow. This lack of speed comes about because algorithms like BART and CART use a specific numerical Bayesian technique, Markov Chain Monte Carlo (MCMC). While efficient general-purpose variants of MCMC (e.g. the No-U-Turn-Sampler (NUTS)) exist and can applied to many problems, these MCMC variants are not applicable in contexts where the number of parameters is unknown. Since trees can have different numbers of nodes and so different numbers of parameters, algorithms like NUTS can't be used to improve the run-time for tree-based algorithms like BART and CART.NUTS achieves its efficiency by using gradient information to identify the directions in which to move to optimise the parameters of the model. While one cannot calculate gradients in the context of trees, one can emulate the calculation of gradients in such settings using a hierarchy of what is known as mini-batches in the neural network literature. An algorithm that exploits this idea, Hierarchical Importance with Nested Training Samples (HINTS), was developed in 2004, but it is now obscure and its potential largely untapped. Furthermore, there is potential to use more recent advances in the context of Sequential Monte Carlo (SMC) samplers, a family of algorithms that can be exploit parallel processing resources (e.g. GPUs) and that can remove the need for the sequential burn-in phase that is often responsible for MCMC algorithms' slow run-time.This PhD will seek to develop efficient numerical Bayesian algorithms (likely to be based on a combination of HINTS and SMC samplers) that can be used to develop a variant of a Random Forest algorithms. The intent is that the new algorithms would be drop-in replacements to the Random Forest algorithms used in sk-learn that offer the same interfaces, but can use parallel computational resources to use a given training dataset to provide GCHQ more accurate predictions in the same elapsed time.