Lifelong Machine Learning Systems & Optimisation

Typical meta and hyper heuristic algorithms tend to operate in the same manner: an algorithm is tuned to work well on a (possibly large) set of representative problems and each time a new problem instance needs to be solved, the algorithm conducts a search of either the solution space or the heuristic space to locate good solutions. Whilst this often leads to acceptable solutions, such approaches have a number of weaknesses in that if the nature of the problems to be solved changes over time, then the algorithm needs to be periodically re-tuned. Furthermore, such approaches are likely to be inefficient, failing to exploit previously learned knowledge in the search for a solution.

In contrast, in the field of machine-learning, several contemporary learning systems employ methods that use prior knowledge when learning behaviours in new, but similar tasks. [1] recently proposed that the AI community should move beyond learning algorithms to more seriously consider the nature of systems that are capable of learning over a lifetime, creating lifelong machine learning or LML systems. Although this was in some senses directed at typical ML applications such as robotics, it seems entirely appropriate that optimisation systems should embody the same properties.

[1] identify three essential components of an LML system that clearly apply in an optimisation context:

  1. it should be able to retain and/or consolidate knowledge, i.e. incorporate a long- term memory
  2. it should selectively transfer prior knowledge when learning new tasks; it should adopt a systems approach that ensures the effective and efficient interaction of the elements of the system.
  3. the system should be computationally efficient when storing learned knowledge in long-term memory; ideally, retention should occur online.

We propose that the natural immune system has properties that map very closely to these requirements:

  •  It exhibits memory that enables it to respond rapidly when faced with pathogens it has previously been exposed to;
  • it can selectively adapt prior knowledge via clonal selection mechanisms that can rapidly adapt existing antibodies to new variants of previous pathogens and
  •  it embodies a systemic approach by maintaining a repertoire of antibodies that collectively cover the space of potential pathogens.

We’ve developed a novel optimisation method that combines inspiration from AIS with hyper-heuristics into a system solves 1D bin-packing problems; the system is continuously fed problems – the AIS component retains a network of interacting deterministic heuristics that both solves problems as they arrive but also acts as a memory of past experience, enabling solutions to be rapidly found to problems that share characteristics with those previously solved.

Furthermore, the system continuously generates new knowledge in the form of novel deterministic heuristics; this knowledge, if useful, becomes integrated into the network of heuristics. Both the content and topology of the network are plastic, enabling adaption over time to new environments.

conceptA description of an early version of the system is given in our ECAL 2013 paper;  an improved version that we’re calling NELLI (Network for Lifelong Learning) will be described in a journal paper, a draft version of which will be shortly available.
The new system creates a network of interacting heuristics and problems: the problems incorporated in the network provide a minimal representative map of the problem space; the heuristics generalise over the problem space, each occupying its own niche.

  1. D.Silver,Q.Yang,L.Li. Lifelong machine learning systems: Beyond learning algorithms, AAAI 2013 Spring Symposium Series.