EarlyStopping.jl

Linux	Coverage

A small package for applying early stopping criteria to loss-generating iterative algorithms, with a view to training and optimizing machine learning models.

The basis of IterationControl.jl, a package externally controlling iterative algorithms.

Includes the stopping criteria surveyed in Prechelt, Lutz (1998): "Early Stopping - But When?", in Neural Networks: Tricks of the Trade, ed. G. Orr, Springer.

Installation

using Pkg
Pkg.add("EarlyStopping")

Sample usage

The EarlyStopper objects defined in this package consume a sequence of numbers called losses generated by some external algorithm - generally the training loss or out-of-sample loss of some iterative statistical model - and decide when those losses have dropped sufficiently to warrant terminating the algorithm. A number of commonly applied stopping criteria, listed under Criteria below, are provided out-of-the-box.

Here's an example of using an EarlyStopper object to check against two of these criteria (either triggering the stop):

using EarlyStopping

stopper = EarlyStopper(Patience(2), InvalidValue()) # multiple criteria
done!(stopper, 0.123) # false
done!(stopper, 0.234) # false
done!(stopper, 0.345) # true

julia> message(stopper)
"Early stop triggered by Patience(2) stopping criterion. "

One may force an EarlyStopper to report its evolving state:

losses = [10.0, 11.0, 10.0, 11.0, 12.0, 10.0];
stopper = EarlyStopper(Patience(2), verbosity=1);

for loss in losses
    done!(stopper, loss) && break
end

[ Info: loss: 10.0       state: (loss = 10.0, n_increases = 0)
[ Info: loss: 11.0       state: (loss = 11.0, n_increases = 1)
[ Info: loss: 10.0       state: (loss = 10.0, n_increases = 0)
[ Info: loss: 11.0       state: (loss = 11.0, n_increases = 1)
[ Info: loss: 12.0       state: (loss = 12.0, n_increases = 2)

The "object-oriented" interface demonstrated here is not code-optimized but will suffice for the majority of use-cases. For performant code, use the functional interface described under Implementing new criteria below.

Criteria

To list all stopping criterion, do subtypes(StoppingCriterion). Each subtype T has a detailed doc-string queried with ?T at the REPL. Here is a short summary:

criterion	description	notation in Prechelt
`Never()`	Never stop
`InvalidValue()`	Stop when `NaN`, `Inf` or `-Inf` encountered
`TimeLimit(t=0.5)`	Stop after `t` hours
`NumberLimit(n=100)`	Stop after `n` loss updates (excl. "training losses")
`NumberSinceBest(n=6)`	Stop when best loss occurred on the `n`th previous update (excl. "training losses")
`Threshold(value=0.0)`	Stop when `loss < value`
`GL(alpha=2.0)`	Stop after "Generalization Loss" exceeds `alpha`	`GL_α`
`PQ(alpha=0.75, k=5)`	Stop after "Progress-modified GL" exceeds `alpha`	`PQ_α`
`Patience(n=5)`	Stop after `n` consecutive loss increases	`UP_s`
`Disjunction(c...)`	Stop when any of the criteria `c` apply
`Warmup(c; n=1)`	Wait for `n` loss updates before checking criteria `c`

Criteria tracking both training and out-of-sample losses

For criteria tracking both an "out-of-sample" loss and a "training" loss (eg, stopping criterion of type PQ), specify training=true if the update is for training, as in

done!(stopper, 0.123, training=true)

In these cases, the out-of-sample update must always come after the corresponding training update. Multiple training updates may precede the out-of-sample update, as in the following example:

criterion = PQ(alpha=2.0, k=2)
needs_training_losses(criterion) # true

stopper = EarlyStopper(criterion)

done!(stopper, 9.5, training=true) # false
done!(stopper, 9.3, training=true) # false
done!(stopper, 10.0) # false

done!(stopper, 9.3, training=true) # false
done!(stopper, 9.1, training=true) # false
done!(stopper, 8.9, training=true) # false
done!(stopper, 8.0) # false

done!(stopper, 8.3, training=true) # false
done!(stopper, 8.4, training=true) # false
done!(stopper, 9.0) # true

Important. If there is no distinction between in and out-of-sample losses, then any criterion can be applied, and in that case training=true is never specified (regardless of the actual interpretation of the losses being tracked).

Stopping times

To determine the stopping time for an iterator losses, use stopping_time(criterion, losses). This is useful for debugging new criteria (see below). If the iterator terminates without a stop, 0 is returned.

julia> stopping_time(InvalidValue(), [10.0, 3.0, Inf, 4.0])
3

julia> stopping_time(Patience(3), [10.0, 3.0, 4.0, 5.0], verbosity=1)
[ Info: loss updates: 1
[ Info: state: (loss = 10.0, n_increases = 0)
[ Info: loss updates: 2
[ Info: state: (loss = 3.0, n_increases = 0)
[ Info: loss updates: 3
[ Info: state: (loss = 4.0, n_increases = 1)
[ Info: loss updates: 4
[ Info: state: (loss = 5.0, n_increases = 2)
0

If the losses include both training and out-of-sample losses as described above, pass an extra Bool vector marking the training losses with true, as in

stopping_time(PQ(),
              [0.123, 0.321, 0.52, 0.55, 0.56, 0.58],
              [true, true, false, true, true, false])

Implementing new criteria

To implement a new stopping criterion, one must:

Define a new struct for the criterion, which must subtype StoppingCriterion.
Overload methods update and done for the new type.

struct NewCriteria <: StoppingCriterion
    # Put relevant fields here
end

# Provide a default constructor with all key-word arguments
NewCriteria(; kwargs...) = ...

# Return the initial state of the NewCriteria after
# receiving an out-of-sample loss
update(c::NewCriteria, loss, ::Nothing) = ...

# Return an updated state for NewCriteria given a `loss`
# and the current `state`
update(c::NewCriteria, loss, state) = ...

# Return true if NewCriteria should stop given `state`.
# Always return false if `state === nothing`
done(c::NewCriteria, state) = state === nothing ? false : ....

Optionally, one may define the following:

Overload the final message with message.
Handle training losses by overloading update_training and the trait needs_training_losses.

# Final message when NewCriteria triggers a stop
message(c::NewCriteria, state) = ...

# Methods for initializing/updating the state given a training loss
update_training(c::NewCriteria, loss, ::Nothing) = ...
update_training(c::NewCriteria, loss, state) = ...

Wrappers. If your criterion wraps another criterion (as Warmup does) then the criterion must be a field and must store the criterion being wrapped.

New Criteria Example

We demonstrate this with a simplified version of the code for Patience:

Defining the new type

using EarlyStopping

struct Patience <: StoppingCriterion
    n::Int
end
Patience(; n=5) = Patience(n)

Overloading `update` and `done`

All information to be "remembered" must passed around in an object called state below, which is the return value of update (and update_training). The update function has two methods:

Initialization: update(c::NewCriteria, loss, ::Nothing)
Subsequent Loss Updates: update(c::NewCriteria, loss, state)

Where state is the return of the previous call to update or update_training. Notice, that state === nothing indicates an uninitialized criteria.

import EarlyStopping: update, done

function update(criterion::Patience, loss, ::Nothing)
    return (loss=loss, n_increases=0) # state
end

function update(criterion::Patience, loss, state)
    old_loss, n = state
    if loss > old_loss
        n += 1
    else
        n = 0
    end
    return (loss=loss, n_increases=n) # state
end

The done method returns true or false depending on the state, but always returns false if state === nothing.

done(criterion::Patience, state) =
    state === nothing ? false : state.n_increases == criterion.n

Optional methods

The final message of an EarlyStopper is generated using a message method for StoppingCriterion. Here is the fallback (which does not use state):

EarlyStopping.message(criteria::StoppingCriterion, state)
    = "Early stop triggered by $criterion stopping criterion. "

The optional update_training methods (two for each criterion) have the same signature as the update methods above. Refer to the PQ code for an example.

If a stopping criterion requires one or more update_training calls per update call to work, you should overload the trait needs_training_losses for that type, as in this example from the source code:

EarlyStopping.needs_training_losses(::Type{<:PQ}) = true

Unit Testing

The following are provided to facilitate testing of new criteria:

stopping_time: returns the stopping time for an iterator losses using criterion.
@test_criteria NewCriteria(): Runs a suite of unit tests against the provided StoppingCriteria. This macro is only part of the test suite and is not part of the API.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

README.md

README.md

EarlyStopping.jl

Installation

Sample usage

Criteria

Criteria tracking both training and out-of-sample losses

Stopping times

Implementing new criteria

New Criteria Example

Defining the new type

Overloading `update` and `done`

Optional methods

Unit Testing

Files

README.md

Latest commit

History

README.md

File metadata and controls

EarlyStopping.jl

Installation

Sample usage

Criteria

Criteria tracking both training and out-of-sample losses

Stopping times

Implementing new criteria

New Criteria Example

Defining the new type

Overloading update and done

Optional methods

Unit Testing

Overloading `update` and `done`