Enable fault tolerance in FastTree for distributed learning

[rogancarr]

As we plan to add distributed training to ML.NET, we have to consider Fault Tolerance of the individual worker nodes. In the case of FastTree, fault tolerance for individual workers has two requirements:

• Failed FastTree workers must be restarted in the current state of the calculation
• Non-failing workers must respond to failures in the IParallelTraining components*

*This response depends on the implementation of fault tolerance.

[rogancarr]

The method I propose to handle fault-tolerance of individual worker nodes is to checkpoint the calculation at each iteration (that is, at the last tree built in the ensemble). Then, restarted workers need to be "fast-forwarded" to the current iteration, and non-failing workers need to "rewind" to the last iteration.

The solution I am proposing requires the following changes to FastTree:

Rewinding the remaining FastTree tasks

• Synchronize all random seeds at the iteration boundary
  In the case of FastTree, some state is actually held in the random seed. To make sure that jobs can be restarted safely while keeping the output deterministic, it will be necessary to set the seeds to a deterministic state each iteration.
• FitTarget will restart on Failure (return a call to itself)
  To restart the tree-building process, I propose that FitTarget detect failure from the IParallelTraining component and force a restart of the tree-building process by calling itself again, with the same input parameters. This is the "least-touch" way of restarting the iteration, so that restart logic not need be passed back into the OptimizationAlgorithm or FastTree components. In this logic, IParallelTraining components would handle the restart/failure logic and throw to exit this loop.

Fast-forward a new FastTree task

• Retrieve the existing bins from IParallelTrainer
  • Add an interface to get existing Bins from IParallelTrainer
  • Add an existing bin check to DataConverter (DiskImpl | MemoryImpl)
    While here, it may be possible to consolidate some of the binning code, as it looks like there is a lot of code overlap between the two implementations.
• Retrieve the existing ensemble from IParallelTrainer
  • Move InitializeEnvironment() to TrainCore:Initialize(), rename to InitializeTraining, adding Ensemble as a parameter
    It is not actually necessary to call InitializeEnvironment() after env.Create()ing IParallelTrainer interfaces. As this calls the constructor, the second call to InitializeEnvironment() is unnecessary. Rather, this initialization step is needed at the beginning of training. By adding Ensemble as a parameter, the IParallelTraining component can update the ensemble with the model built so far.

[rogancarr]

I have started a branch to explore solutions. This commit is an example of how we could synchronize the random number generator seeds at each iteration.

[rogancarr]

Update: This issue was filed for work on an internal repository. We will not be merging it into the public branch at this time because of backwards-compatibility issues. Please reopen this issue if there is interest in bringing these changes into the public branch.

Please see my branch 349_FaultToleranceInFastTree for the necessary changes to FastTree to support fault-tolerant parallel execution. @singlis may also have a branch for this as well.