GitHub

MGL Manual

Table of Contents

[in package MGL]

  • [system] "mgl"

    • Version: 0.1.0
    • Description: MGL is a machine learning library for backpropagation neural networks, boltzmann machines, gaussian processes and more.
    • Licence: MIT, see COPYING.
    • Author: Gábor Melis mega@retes.hu
    • Mailto: mega@retes.hu
    • Homepage: http://melisgl.github.io/mgl
    • Bug tracker: https://github.com/melisgl/mgl/issues
    • Source control: GIT
    • Depends on: alexandria, array-operations, cl-reexport, closer-mop, lla, mgl-gnuplot, mgl-mat, mgl-pax, named-readtables, num-utils, pythonic-string-reader, swank(?)

1 Introduction

1.1 Overview

MGL is a Common Lisp machine learning library by Gábor Melis with some parts originally contributed by Ravenpack International. It mainly concentrates on various forms of neural networks (boltzmann machines, feed-forward and recurrent backprop nets). Most of MGL is built on top of MGL-MAT so it has BLAS and CUDA support.

In general, the focus is on power and performance not on ease of use. Perhaps one day there will be a cookie cutter interface with restricted functionality if a reasonable compromise is found between power and utility.

1.2 Links

The official repository is https://github.com/melisgl/mgl, and this document in available in various formats on https://fixnum.com for the latest version.

1.3 Dependencies

MGL used to rely on LLA to interface to BLAS and LAPACK. That's mostly history by now, but configuration of foreign libraries is still done via LLA. See the README in LLA on how to set things up. Note that these days OpenBLAS is easier to set up and just as fast as ATLAS.

CL-CUDA and MGL-MAT are the two main dependencies and also the ones not yet in quicklisp, so just drop them into quicklisp/local-projects/. If there is no suitable GPU on the system or the CUDA SDK is not installed, MGL will simply fall back on using BLAS and Lisp code. Wrapping code in MGL-MAT:WITH-CUDA* is basically all that's needed to run on the GPU, and with MGL-MAT:CUDA-AVAILABLE-P one can check whether the GPU is really being used.

1.4 Code Organization

MGL consists of several packages dedicated to different tasks. For example, package MGL-RESAMPLE is about Resampling and MGL-GD is about Gradient Descent and so on. On one hand, having many packages makes it easier to cleanly separate API and implementation and also to explore into a specific task. At other times, they can be a hassle, so the MGL package itself reexports every external symbol found in all the other packages that make up MGL and MGL-MAT (see MAT Manual) on which it heavily relies.

One exception to this rule is the bundled, but independent MGL-GNUPLOT library.

The built in tests can be run with:

(ASDF:OOS 'ASDF:TEST-OP '#:MGL)

Note, that most of the tests are rather stochastic and can fail once in a while.

1.5 Glossary

Ultimately machine learning is about creating models of some domain. The observations in the modelled domain are called instances (also known as examples or samples). Sets of instances are called datasets. Datasets are used when fitting a model or when making predictions. Sometimes the word predictions is too specific, and the results obtained from applying a model to some instances are simply called results.

2 Common Stuff

[in package MGL-COMMON]

  • [generic-function] NAME OBJECT

  • [function] NAME= X Y

    Return T if X and Y are EQL or if they are structured components whose elements are EQUAL. Strings and bit-vectors are EQUAL if they are the same length and have identical components. Other arrays must be EQ to be EQUAL.

  • [generic-function] SIZE OBJECT

  • [generic-function] NODES OBJECT

    Returns a MGL-MAT:MAT object representing the state or result of OBJECT. The first dimension of the returned matrix is equal to the number of stripes.

  • [generic-function] DEFAULT-VALUE OBJECT
  • [generic-function] GROUP-SIZE OBJECT
  • [generic-function] BATCH-SIZE OBJECT
  • [generic-function] WEIGHTS OBJECT
  • [generic-function] SCALE OBJECT

3 Datasets

[in package MGL-DATASET]

An instance can often be any kind of object of the user's choice. It is typically represented by a set of numbers which is called a feature vector or by a structure holding the feature vector, the label, etc. A dataset is a SEQUENCE of such instances or a Samplers object that produces instances.

  • [function] MAP-DATASET FN DATASET

    Call FN with each instance in DATASET. This is basically equivalent to iterating over the elements of a sequence or a sampler (see Samplers).

  • [function] MAP-DATASETS FN DATASETS &KEY IMPUTE

    Call FN with a list of instances, one from each dataset in DATASETS. Return nothing. If IMPUTE is specified then iterate until the largest dataset is consumed imputing IMPUTE for missing values. If IMPUTE is not specified then iterate until the smallest dataset runs out.

    (map-datasets #'prin1 '((0 1 2) (:a :b)))
.. (0 :A)(1 :B)
(map-datasets #'prin1 '((0 1 2) (:a :b)) :impute nil)
.. (0 :A)(1 :B)(2 NIL)

    It is of course allowed to mix sequences with samplers:

    (map-datasets #'prin1
              (list '(0 1 2)
                    (make-sequence-sampler '(:a :b) :max-n-samples 2)))
.. (0 :A)(1 :B)

3.1 Samplers

Some algorithms do not need random access to the entire dataset and can work with a stream observations. Samplers are simple generators providing two functions: SAMPLE and FINISHEDP.

  • [generic-function] SAMPLE SAMPLER

    If SAMPLER has not run out of data (see FINISHEDP) SAMPLE returns an object that represents a sample from the world to be experienced or, in other words, simply something the can be used as input for training or prediction. It is not allowed to call SAMPLE if SAMPLER is FINISHEDP.

  • [generic-function] FINISHEDP SAMPLER

    See if SAMPLER has run out of examples.

  • [function] LIST-SAMPLES SAMPLER MAX-SIZE

    Return a list of samples of length at most MAX-SIZE or less if SAMPLER runs out.

  • [function] MAKE-SEQUENCE-SAMPLER SEQ &KEY MAX-N-SAMPLES

    Create a sampler that returns elements of SEQ in their original order. If MAX-N-SAMPLES is non-nil, then at most MAX-N-SAMPLES are sampled.

  • [function] MAKE-RANDOM-SAMPLER SEQ &KEY MAX-N-SAMPLES (REORDER #'MGL-RESAMPLE:SHUFFLE)

    Create a sampler that returns elements of SEQ in random order. If MAX-N-SAMPLES is non-nil, then at most MAX-N-SAMPLES are sampled. The first pass over a shuffled copy of SEQ, and this copy is reshuffled whenever the sampler reaches the end of it. Shuffling is performed by calling the REORDER function.

  • [variable] *INFINITELY-EMPTY-DATASET* #<FUNCTION-SAMPLER "infinitely empty" >

    This is the default dataset for MGL-OPT:MINIMIZE. It's an infinite stream of NILs.

3.1.1 Function Sampler

  • [class] FUNCTION-SAMPLER

    A sampler with a function in its GENERATOR that produces a stream of samples which may or may not be finite depending on MAX-N-SAMPLES. FINISHEDP returns T iff MAX-N-SAMPLES is non-nil, and it's not greater than the number of samples generated (N-SAMPLES).

      (list-samples (make-instance 'function-sampler
                               :generator (lambda ()
                                            (random 10))
                               :max-n-samples 5)
                10)
  => (3 5 2 3 3)

  • [reader] GENERATOR FUNCTION-SAMPLER (:GENERATOR)

    A generator function of no arguments that returns the next sample.

  • [reader] NAME FUNCTION-SAMPLER (:NAME = NIL)

    An arbitrary object naming the sampler. Only used for printing the sampler object.

4 Resampling

[in package MGL-RESAMPLE]

The focus of this package is on resampling methods such as cross-validation and bagging which can be used for model evaluation, model selection, and also as a simple form of ensembling. Data partitioning and sampling functions are also provided because they tend to be used together with resampling.

4.1 Shuffling

  • [function] SHUFFLE SEQ

    Copy of SEQ and shuffle it using Fisher-Yates algorithm.

  • [function] SHUFFLE! SEQ

    Shuffle SEQ using Fisher-Yates algorithm.

4.2 Partitions

The following functions partition a dataset (currently only SEQUENCEs are supported) into a number of partitions. For each element in the original dataset there is exactly one partition that contains it.

  • [function] FRACTURE FRACTIONS SEQ &KEY WEIGHT

    Partition SEQ into a number of subsequences. FRACTIONS is either a positive integer or a list of non-negative real numbers. WEIGHT is NIL or a function that returns a non-negative real number when called with an element from SEQ. If FRACTIONS is a positive integer then return a list of that many subsequences with equal sum of weights bar rounding errors, else partition SEQ into subsequences, where the sum of weights of subsequence I is proportional to element I of FRACTIONS. If WEIGHT is NIL, then it's element is assumed to have the same weight.

    To split into 5 sequences:

    (fracture 5 '(0 1 2 3 4 5 6 7 8 9))
=> ((0 1) (2 3) (4 5) (6 7) (8 9))

    To split into two sequences whose lengths are proportional to 2 and 3:

    (fracture '(2 3) '(0 1 2 3 4 5 6 7 8 9))
=> ((0 1 2 3) (4 5 6 7 8 9))

  • [function] STRATIFY SEQ &KEY (KEY #'IDENTITY) (TEST #'EQL)

    Return the list of strata of SEQ. SEQ is a sequence of elements for which the function KEY returns the class they belong to. Such classes are opaque objects compared for equality with TEST. A stratum is a sequence of elements with the same (under TEST) KEY.

    (stratify '(0 1 2 3 4 5 6 7 8 9) :key #'evenp)
=> ((0 2 4 6 8) (1 3 5 7 9))

  • [function] FRACTURE-STRATIFIED FRACTIONS SEQ &KEY (KEY #'IDENTITY) (TEST #'EQL) WEIGHT

    Similar to FRACTURE, but also makes sure that keys are evenly distributed among the partitions (see STRATIFY). It can be useful for classification tasks to partition the data set while keeping the distribution of classes the same.

    Note that the sets returned are not in random order. In fact, they are sorted internally by KEY.

    For example, to make two splits with approximately the same number of even and odd numbers:

    (fracture-stratified 2 '(0 1 2 3 4 5 6 7 8 9) :key #'evenp)
=> ((0 2 1 3) (4 6 8 5 7 9))

4.3 Cross-validation

  • [function] CROSS-VALIDATE DATA FN &KEY (N-FOLDS 5) (FOLDS (ALEXANDRIA:IOTA N-FOLDS)) (SPLIT-FN #'SPLIT-FOLD/MOD) PASS-FOLD

    Map FN over the FOLDS of DATA split with SPLIT-FN and collect the results in a list. The simplest demonstration is:

    (cross-validate '(0 1 2 3 4)
                (lambda (test training)
                 (list test training))
                :n-folds 5)
=> (((0) (1 2 3 4))
    ((1) (0 2 3 4))
    ((2) (0 1 3 4))
    ((3) (0 1 2 4))
    ((4) (0 1 2 3)))

    Of course, in practice one would typically train a model and return the trained model and/or its score on TEST. Also, sometimes one may want to do only some of the folds and remember which ones they were:

    (cross-validate '(0 1 2 3 4)
                (lambda (fold test training)
                 (list :fold fold test training))
                :folds '(2 3)
                :pass-fold t)
=> ((:fold 2 (2) (0 1 3 4))
    (:fold 3 (3) (0 1 2 4)))

    Finally, the way the data is split can be customized. By default SPLIT-FOLD/MOD is called with the arguments DATA, the fold (from among FOLDS) and N-FOLDS. SPLIT-FOLD/MOD returns two values which are then passed on to FN. One can use SPLIT-FOLD/CONT or SPLIT-STRATIFIED or any other function that works with these arguments. The only real constraint is that FN has to take as many arguments (plus the fold argument if PASS-FOLD) as SPLIT-FN returns.

  • [function] SPLIT-FOLD/MOD SEQ FOLD N-FOLDS

    Partition SEQ into two sequences: one with elements of SEQ with indices whose remainder is FOLD when divided with N-FOLDS, and a second one with the rest. The second one is the larger set. The order of elements remains stable. This function is suitable as the SPLIT-FN argument of CROSS-VALIDATE.

  • [function] SPLIT-FOLD/CONT SEQ FOLD N-FOLDS

    Imagine dividing SEQ into N-FOLDS subsequences of the same size (bar rounding). Return the subsequence of index FOLD as the first value and the all the other subsequences concatenated into one as the second value. The order of elements remains stable. This function is suitable as the SPLIT-FN argument of CROSS-VALIDATE.

  • [function] SPLIT-STRATIFIED SEQ FOLD N-FOLDS &KEY (KEY #'IDENTITY) (TEST #'EQL) WEIGHT

    Split SEQ into N-FOLDS partitions (as in FRACTURE-STRATIFIED). Return the partition of index FOLD as the first value, and the concatenation of the rest as the second value. This function is suitable as the SPLIT-FN argument of CROSS-VALIDATE (mostly likely as a closure with KEY, TEST, WEIGHT bound).

4.4 Bagging

  • [function] BAG SEQ FN &KEY (RATIO 1) N WEIGHT (REPLACEMENT T) KEY (TEST #'EQL) (RANDOM-STATE *RANDOM-STATE*)

    Sample from SEQ with SAMPLE-FROM (passing RATIO, WEIGHT, REPLACEMENT), or SAMPLE-STRATIFIED if KEY is not NIL. Call FN with the sample. If N is NIL then keep repeating this until FN performs a non-local exit. Else N must be a non-negative integer, N iterations will be performed, the primary values returned by FN collected into a list and returned. See SAMPLE-FROM and SAMPLE-STRATIFIED for examples.

  • [function] SAMPLE-FROM RATIO SEQ &KEY WEIGHT REPLACEMENT (RANDOM-STATE *RANDOM-STATE*)

    Return a sequence constructed by sampling with or without REPLACEMENT from SEQ. The sum of weights in the result sequence will approximately be the sum of weights of SEQ times RATIO. If WEIGHT is NIL then elements are assumed to have equal weights, else WEIGHT should return a non-negative real number when called with an element of SEQ.

    To randomly select half of the elements:

    (sample-from 1/2 '(0 1 2 3 4 5))
=> (5 3 2)

    To randomly select some elements such that the sum of their weights constitute about half of the sum of weights across the whole sequence:

    (sample-from 1/2 '(0 1 2 3 4 5 6 7 8 9) :weight #'identity)
=> ;; sums to 28 that's near 45/2
   (9 4 1 6 8)

    To sample with replacement (that is, allowing the element to be sampled multiple times):

    (sample-from 1 '(0 1 2 3 4 5) :replacement t)
=> (1 1 5 1 4 4)

  • [function] SAMPLE-STRATIFIED RATIO SEQ &KEY WEIGHT REPLACEMENT (KEY #'IDENTITY) (TEST #'EQL) (RANDOM-STATE *RANDOM-STATE*)

    Like SAMPLE-FROM but makes sure that the weighted proportion of classes in the result is approximately the same as the proportion in SEQ. See STRATIFY for the description of KEY and TEST.

4.5 CV Bagging

  • [function] BAG-CV DATA FN &KEY N (N-FOLDS 5) (FOLDS (ALEXANDRIA:IOTA N-FOLDS)) (SPLIT-FN #'SPLIT-FOLD/MOD) PASS-FOLD (RANDOM-STATE *RANDOM-STATE*)

    Perform cross-validation on different shuffles of DATA N times and collect the results. Since CROSS-VALIDATE collects the return values of FN, the return value of this function is a list of lists of FN results. If N is NIL, don't collect anything just keep doing repeated CVs until FN performs a non-local exit.

    The following example simply collects the test and training sets for 2-fold CV repeated 3 times with shuffled data:

    ;;; This is non-deterministic.
(bag-cv '(0 1 2 3 4) #'list :n 3 :n-folds 2)
=> ((((2 3 4) (1 0))
     ((1 0) (2 3 4)))
    (((2 1 0) (4 3))
     ((4 3) (2 1 0)))
    (((1 0 3) (2 4))
     ((2 4) (1 0 3))))

    CV bagging is useful when a single CV is not producing stable results. As an ensemble method, CV bagging has the advantage over bagging that each example will occur the same number of times and after the first CV is complete there is a complete but less reliable estimate for each example which gets refined by further CVs.

4.6 Miscellaneous Operations

  • [function] SPREAD-STRATA SEQ &KEY (KEY #'IDENTITY) (TEST #'EQL)

    Return a sequence that's a reordering of SEQ such that elements belonging to different strata (under KEY and TEST, see STRATIFY) are distributed evenly. The order of elements belonging to the same stratum is unchanged.

    For example, to make sure that even and odd numbers are distributed evenly:

    (spread-strata '(0 2 4 6 8 1 3 5 7 9) :key #'evenp)
=> (0 1 2 3 4 5 6 7 8 9)

    Same thing with unbalanced classes:

    (spread-strata (vector 0 2 3 5 6 1 4)
               :key (lambda (x)
                      (if (member x '(1 4))
                          t
                          nil)))
=> #(0 1 2 3 4 5 6)

  • [function] ZIP-EVENLY SEQS &KEY RESULT-TYPE

    Make a single sequence out of the sequences in SEQS so that in the returned sequence indices of elements belonging to the same source sequence are spread evenly across the whole range. The result is a list is RESULT-TYPE is LIST, it's a vector if RESULT-TYPE is VECTOR. If RESULT-TYPE is NIL, then it's determined by the type of the first sequence in SEQS.

    (zip-evenly '((0 2 4) (1 3)))
=> (0 1 2 3 4)

5 Core

[in package MGL-CORE]

5.1 Persistence

  • [function] LOAD-STATE FILENAME OBJECT

    Load weights of OBJECT from FILENAME. Return OBJECT.

  • [function] SAVE-STATE FILENAME OBJECT &KEY (IF-EXISTS :ERROR) (ENSURE T)

    Save weights of OBJECT to FILENAME. If ENSURE, then ENSURE-DIRECTORIES-EXIST is called on FILENAME. IF-EXISTS is passed on to OPEN. Return OBJECT.

  • [function] READ-STATE OBJECT STREAM

    Read the weights of OBJECT from the bivalent STREAM where weights mean the learnt parameters. There is currently no sanity checking of data which will most certainly change in the future together with the serialization format. Return OBJECT.

  • [function] WRITE-STATE OBJECT STREAM

    Write weight of OBJECT to the bivalent STREAM. Return OBJECT.

  • [generic-function] READ-STATE* OBJECT STREAM CONTEXT

    This is the extension point for READ-STATE. It is guaranteed that primary READ-STATE* methods will be called only once for each OBJECT (under EQ). CONTEXT is an opaque object and must be passed on to any recursive READ-STATE* calls.

  • [generic-function] WRITE-STATE* OBJECT STREAM CONTEXT

    This is the extension point for WRITE-STATE. It is guaranteed that primary WRITE-STATE* methods will be called only once for each OBJECT (under EQ). CONTEXT is an opaque object and must be passed on to any recursive WRITE-STATE* calls.

5.2 Batch Processing

Processing instances one by one during training or prediction can be slow. The models that support batch processing for greater efficiency are said to be striped.

Typically, during or after creating a model, one sets MAX-N-STRIPES on it a positive integer. When a batch of instances is to be fed to the model it is first broken into subbatches of length that's at most MAX-N-STRIPES. For each subbatch, SET-INPUT (FIXDOC) is called and a before method takes care of setting N-STRIPES to the actual number of instances in the subbatch. When MAX-N-STRIPES is set internal data structures may be resized which is an expensive operation. Setting N-STRIPES is a comparatively cheap operation, often implemented as matrix reshaping.

Note that for models made of different parts (for example, MGL-BP:BPN consists of MGL-BP:LUMPs) , setting these values affects the constituent parts, but one should never change the number stripes of the parts directly because that would lead to an internal inconsistency in the model.

  • [generic-function] MAX-N-STRIPES OBJECT

    The number of stripes with which the OBJECT is capable of dealing simultaneously.

  • [generic-function] SET-MAX-N-STRIPES MAX-N-STRIPES OBJECT

    Allocate the necessary stuff to allow for MAX-N-STRIPES number of stripes to be worked with simultaneously in OBJECT. This is called when MAX-N-STRIPES is SETF'ed.

  • [generic-function] N-STRIPES OBJECT

    The number of stripes currently present in OBJECT. This is at most MAX-N-STRIPES.

  • [generic-function] SET-N-STRIPES N-STRIPES OBJECT

    Set the number of stripes (out of MAX-N-STRIPES) that are in use in OBJECT. This is called when N-STRIPES is SETF'ed.

  • [macro] WITH-STRIPES SPECS &BODY BODY

    Bind start and optionally end indices belonging to stripes in striped objects.

      (WITH-STRIPES ((STRIPE1 OBJECT1 START1 END1)
                 (STRIPE2 OBJECT2 START2)
                 ...)
   ...)

    This is how one's supposed to find the index range corresponding to the Nth input in an input lump of a bpn:

       (with-stripes ((n input-lump start end))
     (loop for i upfrom start below end
           do (setf (mref (nodes input-lump) i) 0d0)))

    Note how the input lump is striped, but the matrix into which we are indexing (NODES) is not known to WITH-STRIPES. In fact, for lumps the same stripe indices work with NODES and MGL-BP:DERIVATIVES.

  • [generic-function] STRIPE-START STRIPE OBJECT

    Return the start index of STRIPE in some array or matrix of OBJECT.

  • [generic-function] STRIPE-END STRIPE OBJECT

    Return the end index (exclusive) of STRIPE in some array or matrix of OBJECT.

  • [generic-function] SET-INPUT INSTANCES MODEL

    Set INSTANCES as inputs in MODEL. INSTANCES is always a SEQUENCE of instances even for models not capable of batch operation. It sets N-STRIPES to (LENGTH INSTANCES) in a :BEFORE method.

  • [function] MAP-BATCHES-FOR-MODEL FN DATASET MODEL

    Call FN with batches of instances from DATASET suitable for MODEL. The number of instances in a batch is MAX-N-STRIPES of MODEL or less if there are no more instances left.

  • [macro] DO-BATCHES-FOR-MODEL (BATCH (DATASET MODEL)) &BODY BODY

    Convenience macro over MAP-BATCHES-FOR-MODEL.

5.3 Executors

  • [generic-function] MAP-OVER-EXECUTORS FN INSTANCES PROTOTYPE-EXECUTOR

    Divide INSTANCES between executors that perform the same function as PROTOTYPE-EXECUTOR and call FN with the instances and the executor for which the instances are.

    Some objects conflate function and call: the forward pass of a MGL-BP:BPN computes output from inputs so it is like a function but it also doubles as a function call in the sense that the bpn (function) object changes state during the computation of the output. Hence not even the forward pass of a bpn is thread safe. There is also the restriction that all inputs must be of the same size.

    For example, if we have a function that builds bpn a for an input of a certain size, then we can create a factory that creates bpns for a particular call. The factory probably wants to keep the weights the same though. In Parameterized Executor Cache, MAKE-EXECUTOR-WITH-PARAMETERS is this factory.

    Parallelization of execution is another possibility MAP-OVER-EXECUTORS allows, but there is no prebuilt solution for it, yet.

    The default implementation simply calls FN with INSTANCES and PROTOTYPE-EXECUTOR.

  • [macro] DO-EXECUTORS (INSTANCES OBJECT) &BODY BODY

    Convenience macro on top of MAP-OVER-EXECUTORS.

5.3.1 Parameterized Executor Cache

  • [class] PARAMETERIZED-EXECUTOR-CACHE-MIXIN

    Mix this into a model, implement INSTANCE-TO-EXECUTOR-PARAMETERS and MAKE-EXECUTOR-WITH-PARAMETERS and DO-EXECUTORS will be to able build executors suitable for different instances. The canonical example is using a BPN to compute the means and convariances of a gaussian process. Since each instance is made of a variable number of observations, the size of the input is not constant, thus we have a bpn (an executor) for each input dimension (the parameters).

  • [generic-function] MAKE-EXECUTOR-WITH-PARAMETERS PARAMETERS CACHE

    Create a new executor for PARAMETERS. CACHE is a PARAMETERIZED-EXECUTOR-CACHE-MIXIN. In the BPN gaussian process example, PARAMETERS would be a list of input dimensions.

  • [generic-function] INSTANCE-TO-EXECUTOR-PARAMETERS INSTANCE CACHE

    Return the parameters for an executor able to handle INSTANCE. Called by MAP-OVER-EXECUTORS on CACHE (that's a PARAMETERIZED-EXECUTOR-CACHE-MIXIN). The returned parameters are keys in an EQUAL parameters->executor hash table.

6 Monitoring

[in package MGL-CORE]

When training or applying a model, one often wants to track various statistics. For example, in the case of training a neural network with cross-entropy loss, these statistics could be the average cross-entropy loss itself, classification accuracy, or even the entire confusion matrix and sparsity levels in hidden layers. Also, there is the question of what to do with the measured values (log and forget, add to some counter or a list).

So there may be several phases of operation when we want to keep an eye on. Let's call these events. There can also be many fairly independent things to do in response to an event. Let's call these monitors. Some monitors are a composition of two operations: one that extracts some measurements and another that aggregates those measurements. Let's call these two measurers and counters, respectively.

For example, consider training a backpropagation neural network. We want to look at the state of of network just after the backward pass. MGL-BP:BP-LEARNER has a MONITORS event hook corresponding to the moment after backpropagating the gradients. Suppose we are interested in how the training cost evolves:

(push (make-instance 'monitor
                     :measurer (lambda (instances bpn)
                                 (declare (ignore instances))
                                 (mgl-bp:cost bpn))
                     :counter (make-instance 'basic-counter))
      (monitors learner))

During training, this monitor will track the cost of training examples behind the scenes. If we want to print and reset this monitor periodically we can put another monitor on MGL-OPT:ITERATIVE-OPTIMIZER's MGL-OPT:ON-N-INSTANCES-CHANGED accessor:

(push (lambda (optimizer gradient-source n-instances)
        (declare (ignore optimizer))
        (when (zerop (mod n-instances 1000))
          (format t "n-instances: ~S~%" n-instances)
          (dolist (monitor (monitors gradient-source))
            (when (counter monitor)
              (format t "~A~%" (counter monitor))
              (reset-counter (counter monitor)))))
      (mgl-opt:on-n-instances-changed optimizer))

Note that the monitor we push can be anything as long as APPLY-MONITOR is implemented on it with the appropriate signature. Also note that the ZEROP + MOD logic is fragile, so you will likely want to use MGL-OPT:MONITOR-OPTIMIZATION-PERIODICALLY instead of doing the above.

So that's the general idea. Concrete events are documented where they are signalled. Often there are task specific utilities that create a reasonable set of default monitors (see Classification Monitors).

  • [function] APPLY-MONITORS MONITORS &REST ARGUMENTS

    Call APPLY-MONITOR on each monitor in MONITORS and ARGUMENTS. This is how an event is fired.

  • [generic-function] APPLY-MONITOR MONITOR &REST ARGUMENTS

    Apply MONITOR to ARGUMENTS. This sound fairly generic, because it is. MONITOR can be anything, even a simple function or symbol, in which case this is just CL:APPLY. See Monitors for more.

  • [generic-function] COUNTER MONITOR

    Return an object representing the state of MONITOR or NIL, if it doesn't have any (say because it's a simple logging function). Most monitors have counters into which they accumulate results until they are printed and reset. See Counters for more.

  • [function] MONITOR-MODEL-RESULTS FN DATASET MODEL MONITORS

    Call FN with batches of instances from DATASET until it runs out (as in DO-BATCHES-FOR-MODEL). FN is supposed to apply MODEL to the batch and return some kind of result (for neural networks, the result is the model state itself). Apply MONITORS to each batch and the result returned by FN for that batch. Finally, return the list of counters of MONITORS.

    The purpose of this function is to collect various results and statistics (such as error measures) efficiently by applying the model only once, leaving extraction of quantities of interest from the model's results to MONITORS.

    See the model specific versions of this functions such as MGL-BP:MONITOR-BPN-RESULTS.

  • [generic-function] MONITORS OBJECT

    Return monitors associated with OBJECT. See various methods such as MONITORS for more documentation.

6.1 Monitors

  • [class] MONITOR

    A monitor that has another monitor called MEASURER embedded in it. When this monitor is applied, it applies the measurer and passes the returned values to ADD-TO-COUNTER called on its COUNTER slot. One may further specialize APPLY-MONITOR to change that.

    This class is useful when the same event monitor is applied repeatedly over a period and its results must be aggregated such as when training statistics are being tracked or when predictions are begin made. Note that the monitor must be compatible with the event it handles. That is, the embedded MEASURER must be prepared to take the arguments that are documented to come with the event.

  • [reader] MEASURER MONITOR (:MEASURER)

    This must be a monitor itself which only means that APPLY-MONITOR is defined on it (but see Monitoring). The returned values are aggregated by COUNTER. See Measurers for a library of measurers.

  • [reader] COUNTER MONITOR (:COUNTER)

    The COUNTER of a monitor carries out the aggregation of results returned by MEASURER. The See Counters for a library of counters.

6.2 Measurers

MEASURER is a part of MONITOR objects, an embedded monitor that computes a specific quantity (e.g. classification accuracy) from the arguments of event it is applied to (e.g. the model results). Measurers are often implemented by combining some kind of model specific extractor with a generic measurer function.

All generic measurer functions return their results as multiple values matching the arguments of ADD-TO-COUNTER for a counter of a certain type (see Counters) so as to make them easily used in a MONITOR:

(multiple-value-call #'add-to-counter <some-counter>
                     <call-to-some-measurer>)

The counter class compatible with the measurer this way is noted for each function.

For a list of measurer functions see Classification Measurers.

6.3 Counters

  • [generic-function] ADD-TO-COUNTER COUNTER &REST ARGS

    Add ARGS to COUNTER in some way. See specialized methods for type specific documentation. The kind of arguments to be supported is the what the measurer functions (see Measurers) intended to be paired with the counter return as multiple values.

  • [generic-function] COUNTER-VALUES COUNTER

    Return any number of values representing the state of COUNTER. See specialized methods for type specific documentation.

  • [generic-function] COUNTER-RAW-VALUES COUNTER

    Return any number of values representing the state of COUNTER in such a way that passing the returned values as arguments ADD-TO-COUNTER on a fresh instance of the same type recreates the original state.

  • [generic-function] RESET-COUNTER COUNTER

    Restore state of COUNTER to what it was just after creation.

6.3.1 Attributes

  • [class] ATTRIBUTED

    This is a utility class that all counters subclass. The ATTRIBUTES plist can hold basically anything. Currently the attributes are only used when printing and they can be specified by the user. The monitor maker functions such as those in Classification Monitors also add attributes of their own to the counters they create.

    With the :PREPEND-ATTRIBUTES initarg when can easily add new attributes without clobbering the those in the :INITFORM, (:TYPE "rmse") in this case.

      (princ (make-instance 'rmse-counter
                        :prepend-attributes '(:event "pred."
                                              :dataset "test")))
  ;; pred. test rmse: 0.000e+0 (0)
  => #<RMSE-COUNTER pred. test rmse: 0.000e+0 (0)>

  • [accessor] ATTRIBUTES ATTRIBUTED (:ATTRIBUTES = NIL)

    A plist of attribute keys and values.

  • [method] NAME (ATTRIBUTED ATTRIBUTED)

    Return a string assembled from the values of the ATTRIBUTES of ATTRIBUTED. If there are multiple entries with the same key, then they are printed near together.

    Values may be padded according to an enclosing WITH-PADDED-ATTRIBUTE-PRINTING.

  • [macro] WITH-PADDED-ATTRIBUTE-PRINTING (ATTRIBUTEDS) &BODY BODY

    Note the width of values for each attribute key which is the number of characters in the value's PRINC-TO-STRING'ed representation. In BODY, if attributes with they same key are printed they are forced to be at least this wide. This allows for nice, table-like output:

      (let ((attributeds
          (list (make-instance 'basic-counter
                               :attributes '(:a 1 :b 23 :c 456))
                (make-instance 'basic-counter
                               :attributes '(:a 123 :b 45 :c 6)))))
    (with-padded-attribute-printing (attributeds)
      (map nil (lambda (attributed)
                 (format t "~A~%" attributed))
           attributeds)))
  ;; 1   23 456: 0.000e+0 (0)
  ;; 123 45 6  : 0.000e+0 (0)

  • [function] LOG-PADDED ATTRIBUTEDS

    Log (see LOG-MSG) ATTRIBUTEDS non-escaped (as in PRINC or ~A) with the output being as table-like as possible.

6.3.2 Counter classes

In addition to the really basic ones here, also see Classification Counters.

  • [class] BASIC-COUNTER ATTRIBUTED

    A simple counter whose ADD-TO-COUNTER takes two additional parameters: an increment to the internal sums of called the NUMERATOR and DENOMINATOR. COUNTER-VALUES returns two values:

    • NUMERATOR divided by DENOMINATOR (or 0 if DENOMINATOR is 0) and

    • DENOMINATOR

    Here is an example the compute the mean of 5 things received in two batches:

       (let ((counter (make-instance 'basic-counter)))
     (add-to-counter counter 6.5 3)
     (add-to-counter counter 3.5 2)
     counter)
   => #<BASIC-COUNTER 2.00000e+0 (5)>

  • [class] RMSE-COUNTER BASIC-COUNTER

    A BASIC-COUNTER with whose nominator accumulates the square of some statistics. It has the attribute :TYPE "rmse". COUNTER-VALUES returns the square root of what BASIC-COUNTER's COUNTER-VALUES would return.

      (let ((counter (make-instance 'rmse-counter)))
    (add-to-counter counter (+ (* 3 3) (* 4 4)) 2)
    counter)
  => #<RMSE-COUNTER rmse: 3.53553e+0 (2)>

  • [class] CONCAT-COUNTER ATTRIBUTED

    A counter that simply concatenates sequences.

    (let ((counter (make-instance 'concat-counter)))
  (add-to-counter counter '(1 2 3) #(4 5))
  (add-to-counter counter '(6 7))
  (counter-values counter))
=> (1 2 3 4 5 6 7)

  • [reader] CONCATENATION-TYPE CONCAT-COUNTER (:CONCATENATION-TYPE = 'LIST)

    A type designator suitable as the RESULT-TYPE argument to CONCATENATE.

7 Classification

[in package MGL-CORE]

To be able to measure classification related quantities, we need to define what the label of an instance is. Customization is possible by implementing a method for a specific type of instance, but these functions only ever appear as defaults that can be overridden.

  • [generic-function] LABEL-INDEX INSTANCE

    Return the label of INSTANCE as a non-negative integer.

  • [generic-function] LABEL-INDEX-DISTRIBUTION INSTANCE

    Return a one dimensional array of probabilities representing the distribution of labels. The probability of the label with LABEL-INDEX I is element at index I of the returned arrray.

The following two functions are basically the same as the previous two, but in batch mode: they return a sequence of label indices or distributions. These are called on results produced by models. Implement these for a model and the monitor maker functions below will automatically work. See FIXDOC: for bpn and boltzmann.

  • [generic-function] LABEL-INDICES RESULTS

    Return a sequence of label indices for RESULTS produced by some model for a batch of instances. This is akin to LABEL-INDEX.

  • [generic-function] LABEL-INDEX-DISTRIBUTIONS RESULT

    Return a sequence of label index distributions for RESULTS produced by some model for a batch of instances. This is akin to LABEL-INDEX-DISTRIBUTION.

7.1 Classification Monitors

The following functions return a list monitors. The monitors are for events of signature (INSTANCES MODEL) such as those produced by MONITOR-MODEL-RESULTS and its various model specific variations. They are model-agnostic functions, extensible to new classifier types.

  • [function] MAKE-LABEL-MONITORS MODEL &KEY OPERATION-MODE ATTRIBUTES (LABEL-INDEX-FN #'LABEL-INDEX) (LABEL-INDEX-DISTRIBUTION-FN #'LABEL-INDEX-DISTRIBUTION)

    Return classification accuracy and cross-entropy monitors. See MAKE-CLASSIFICATION-ACCURACY-MONITORS and MAKE-CROSS-ENTROPY-MONITORS for a description of paramters.

The monitor makers above can be extended to support new classifier types via the following generic functions.

  • [generic-function] MAKE-CLASSIFICATION-ACCURACY-MONITORS* MODEL OPERATION-MODE LABEL-INDEX-FN ATTRIBUTES

    Identical to MAKE-CLASSIFICATION-ACCURACY-MONITORS bar the keywords arguments. Specialize this to add to support for new model types. The default implementation also allows for some extensibility: if LABEL-INDICES is defined on MODEL, then it will be used to extract label indices from model results.

  • [generic-function] MAKE-CROSS-ENTROPY-MONITORS* MODEL OPERATION-MODE LABEL-INDEX-DISTRIBUTION-FN ATTRIBUTES

    Identical to MAKE-CROSS-ENTROPY-MONITORS bar the keywords arguments. Specialize this to add to support for new model types. The default implementation also allows for some extensibility: if LABEL-INDEX-DISTRIBUTIONS is defined on MODEL, then it will be used to extract label distributions from model results.

7.2 Classification Measurers

The functions here compare some known good solution (also known as ground truth or target) to a prediction or approximation and return some measure of their [dis]similarity. They are model independent, hence one has to extract the ground truths and predictions first. Rarely used directly, they are mostly hidden behind Classification Monitors.

  • [function] MEASURE-CLASSIFICATION-ACCURACY TRUTHS PREDICTIONS &KEY (TEST #'EQL) TRUTH-KEY PREDICTION-KEY WEIGHT

    Return the number of correct classifications and as the second value the number of instances (equal to length of TRUTHS in the non-weighted case). TRUTHS (keyed by TRUTH-KEY) is a sequence of opaque class labels compared with TEST to another sequence of classes labels in PREDICTIONS (keyed by PREDICTION-KEY). If WEIGHT is non-nil, then it is a function that returns the weight of an element of TRUTHS. Weighted cases add their weight to both counts (returned as the first and second values) instead of 1 as in the non-weighted case.

    Note how the returned values are suitable for MULTIPLE-VALUE-CALL with #'ADD-TO-COUNTER and a CLASSIFICATION-ACCURACY-COUNTER.

  • [function] MEASURE-CROSS-ENTROPY TRUTHS PREDICTIONS &KEY TRUTH-KEY PREDICTION-KEY (MIN-PREDICTION-PR 1.0d-15)

    Return the sum of the cross-entropy between pairs of elements with the same index of TRUTHS and PREDICTIONS. TRUTH-KEY is a function that's when applied to an element of TRUTHS returns a sequence representing some kind of discrete target distribution (P in the definition below). TRUTH-KEY may be NIL which is equivalent to the IDENTITY function. PREDICTION-KEY is the same kind of key for PREDICTIONS, but the sequence it returns represents a distribution that approximates (Q below) the true one.

    Cross-entropy of the true and approximating distributions is defined as:

      cross-entropy(p,q) = - sum_i p(i) * log(q(i))

    of which this function returns the sum over the pairs of elements of TRUTHS and PREDICTIONS keyed by TRUTH-KEY and PREDICTION-KEY.

    Due to the logarithm, if q(i) is close to zero, we run into numerical problems. To prevent this, all q(i) that are less than MIN-PREDICTION-PR are treated as if they were MIN-PREDICTION-PR.

    The second value returned is the sum of p(i) over all TRUTHS and all I. This is normally equal to (LENGTH TRUTHS), since elements of TRUTHS represent a probability distribution, but this is not enforced which allows relative importance of elements to be controlled.

    The third value returned is a plist that maps each index occurring in the distribution sequences to a list of two elements:

       sum_j p_j(i) * log(q_j(i))

    and

      sum_j p_j(i)

    where J indexes into TRUTHS and PREDICTIONS.

      (measure-cross-entropy '((0 1 0)) '((0.1 0.7 0.2)))
  => 0.35667497
     1
     (2 (0.0 0)
      1 (0.35667497 1)
      0 (0.0 0))

    Note how the returned values are suitable for MULTIPLE-VALUE-CALL with #'ADD-TO-COUNTER and a CROSS-ENTROPY-COUNTER.

  • [function] MEASURE-ROC-AUC PREDICTIONS PRED &KEY (KEY #'IDENTITY) WEIGHT

    Return the area under the ROC curve for PREDICTIONS representing predictions for a binary classification problem. PRED is a predicate function for deciding whether a prediction belongs to the so called positive class. KEY returns a number for each element which is the predictor's idea of how much that element is likely to belong to the class, although it's not necessarily a probability.

    If WEIGHT is NIL, then all elements of PREDICTIONS count as 1 towards the unnormalized sum within AUC. Else WEIGHT must be a function like KEY, but it should return the importance (a positive real number) of elements. If the weight of an prediction is 2 then it's as if there were another identical copy of that prediction in PREDICTIONS.

    The algorithm is based on algorithm 2 in the paper 'An introduction to ROC analysis' by Tom Fawcett.

    ROC AUC is equal to the probability of a randomly chosen positive having higher KEY (score) than a randomly chosen negative element. With equal scores in mind, a more precise version is: AUC is the expectation of the above probability over all possible sequences sorted by scores.

  • [function] MEASURE-CONFUSION TRUTHS PREDICTIONS &KEY (TEST #'EQL) TRUTH-KEY PREDICTION-KEY WEIGHT

    Create a CONFUSION-MATRIX from TRUTHS and PREDICTIONS. TRUTHS (keyed by TRUTH-KEY) is a sequence of class labels compared with TEST to another sequence of class labels in PREDICTIONS (keyed by PREDICTION-KEY). If WEIGHT is non-nil, then it is a function that returns the weight of an element of TRUTHS. Weighted cases add their weight to both counts (returned as the first and second values).

    Note how the returned confusion matrix can be added to another with ADD-TO-COUNTER.

7.3 Classification Counters

7.3.1 Confusion Matrices

  • [class] CONFUSION-MATRIX

    A confusion matrix keeps count of classification results. The correct class is called target' and the output of the classifier is calledprediction'.

  • [function] MAKE-CONFUSION-MATRIX &KEY (TEST #'EQL)

    Classes are compared with TEST.

  • [generic-function] SORT-CONFUSION-CLASSES MATRIX CLASSES

    Return a list of CLASSES sorted for presentation purposes.

  • [generic-function] CONFUSION-CLASS-NAME MATRIX CLASS

    Name of CLASS for presentation purposes.

  • [generic-function] CONFUSION-COUNT MATRIX TARGET PREDICTION

  • [generic-function] MAP-CONFUSION-MATRIX FN MATRIX

    Call FN with TARGET, PREDICTION, COUNT paramaters for each cell in the confusion matrix. Cells with a zero count may be ommitted.

  • [generic-function] CONFUSION-MATRIX-CLASSES MATRIX

    A list of all classes. The default is to collect classes from the counts. This can be overridden if, for instance, some classes are not present in the results.

  • [function] CONFUSION-MATRIX-ACCURACY MATRIX &KEY FILTER

    Return the overall accuracy of the results in MATRIX. It's computed as the number of correctly classified cases (hits) divided by the name of cases. Return the number of hits and the number of cases as the second and third value. If FILTER function is given, then call it with the target and the prediction of the cell. Disregard cell for which FILTER returns NIL.

    Precision and recall can be easily computed by giving the right filter, although those are provided in separate convenience functions.

  • [function] CONFUSION-MATRIX-PRECISION MATRIX PREDICTION

    Return the accuracy over the cases when the classifier said PREDICTION.

  • [function] CONFUSION-MATRIX-RECALL MATRIX TARGET

    Return the accuracy over the cases when the correct class is TARGET.

  • [function] ADD-CONFUSION-MATRIX MATRIX RESULT-MATRIX

    Add MATRIX into RESULT-MATRIX.

8 Features

[in package MGL-CORE]

8.1 Feature Selection

The following scoring functions all return an EQUAL hash table that maps features to scores.

  • [function] COUNT-FEATURES DOCUMENTS MAPPER &KEY (KEY #'IDENTITY)

    Return scored features as an EQUAL hash table whose keys are features of DOCUMENTS and values are counts of occurrences of features. MAPPER takes a function and a document and calls function with features of the document.

    (sort (alexandria:hash-table-alist
       (count-features '(("hello" "world")
                         ("this" "is" "our" "world"))
                       (lambda (fn document)
                         (map nil fn document))))
      #'string< :key #'car)
=> (("hello" . 1) ("is" . 1) ("our" . 1) ("this" . 1) ("world" . 2))

  • [function] FEATURE-LLRS DOCUMENTS MAPPER CLASS-FN &KEY (CLASSES (ALL-DOCUMENT-CLASSES DOCUMENTS CLASS-FN))

    Return scored features as an EQUAL hash table whose keys are features of DOCUMENTS and values are their log likelihood ratios. MAPPER takes a function and a document and calls function with features of the document.

    (sort (alexandria:hash-table-alist
       (feature-llrs '((:a "hello" "world")
                       (:b "this" "is" "our" "world"))
                     (lambda (fn document)
                       (map nil fn (rest document)))
                     #'first))
      #'string< :key #'car)
=> (("hello" . 2.6032386) ("is" . 2.6032386) ("our" . 2.6032386)
    ("this" . 2.6032386) ("world" . 4.8428774e-8))

  • [function] FEATURE-DISAMBIGUITIES DOCUMENTS MAPPER CLASS-FN &KEY (CLASSES (ALL-DOCUMENT-CLASSES DOCUMENTS CLASS-FN))

    Return scored features as an EQUAL hash table whose keys are features of DOCUMENTS and values are their disambiguities. MAPPER takes a function and a document and calls function with features of the document.

    From the paper 'Using Ambiguity Measure Feature Selection Algorithm for Support Vector Machine Classifier'.

8.2 Feature Encoding

Features can rarely be fed directly to algorithms as is, they need to be transformed in some way. Suppose we have a simple language model that takes a single word as input and predicts the next word. However, both input and output is to be encoded as float vectors of length 1000. What we do is find the top 1000 words by some measure (see Feature Selection) and associate these words with the integers in [0..999] (this is ENCODEing). By using for example one-hot encoding, we translate a word into a float vector when passing in the input. When the model outputs the probability distribution of the next word, we find the index of the max and find the word associated with it (this is DECODEing)

  • [generic-function] ENCODE ENCODER DECODED

    Encode DECODED with ENCODER. This interface is generic enough to be almost meaningless. See ENCODER/DECODER for a simple, MGL-NLP:BAG-OF-WORDS-ENCODER for a slightly more involved example.

    If ENCODER is a function designator, then it's simply FUNCALLed with DECODED.

  • [generic-function] DECODE DECODER ENCODED

    Decode ENCODED with ENCODER. For an DECODER / ENCODER pair, (DECODE DECODER (ENCODE ENCODER OBJECT)) must be equal in some sense to OBJECT.

    If DECODER is a function designator, then it's simply FUNCALLed with ENCODED.

  • [class] ENCODER/DECODER

    Implements O(1) ENCODE and DECODE by having an internal decoded-to-encoded and an encoded-to-decoded EQUAL hash table. ENCODER/DECODER objects can be saved and loaded (see Persistence) as long as the elements in the hash tables have read/write consitency.

    (let ((indexer
        (make-indexer
         (alexandria:alist-hash-table '(("I" . 3) ("me" . 2) ("mine" . 1)))
         2)))
  (values (encode indexer "I")
          (encode indexer "me")
          (encode indexer "mine")
          (decode indexer 0)
          (decode indexer 1)
          (decode indexer 2)))
=> 0
=> 1
=> NIL
=> "I"
=> "me"
=> NIL

  • [function] MAKE-INDEXER SCORED-FEATURES N &KEY (START 0) (CLASS 'ENCODER/DECODER)

    Take the top N features from SCORED-FEATURES (see Feature Selection), assign indices to them starting from START. Return an ENCODER/DECODER (or another CLASS) that converts between objects and indices.

Also see Bag of Words.

9 Gradient Based Optimization

[in package MGL-OPT]

We have a real valued, differentiable function F and the task is to find the parameters that minimize its value. Optimization starts from a single point in the parameter space of F, and this single point is updated iteratively based on the gradient and value of F at or around the current point.

Note that while the stated problem is that of global optimization, for non-convex functions, most algorithms will tend to converge to a local optimum.

Currently, there are two optimization algorithms: Gradient Descent (with several variants) and Conjugate Gradient both of which are first order methods (they do not need second order gradients) but more can be added with the Extension API.

  • [function] MINIMIZE OPTIMIZER GRADIENT-SOURCE &KEY (WEIGHTS (LIST-SEGMENTS GRADIENT-SOURCE)) (DATASET *INFINITELY-EMPTY-DATASET*)

    Minimize the value of the real valued function represented by GRADIENT-SOURCE by updating some of its parameters in WEIGHTS (a MAT or a sequence of MATs). Return WEIGHTS. DATASET (see Datasets) is a set of unoptimized parameters of the same function. For example, WEIGHTS may be the weights of a neural network while DATASET is the training set consisting of inputs suitable for SET-INPUT. The default DATASET, (*INFINITELY-EMPTY-DATASET*) is suitable for when all parameters are optimized, so there is nothing left to come from the environment.

    Optimization terminates if DATASET is a sampler and it runs out or when some other condition met (see TERMINATION, for example). If DATASET is a SEQUENCE, then it is reused over and over again.

    Examples for various optimizers are provided in Gradient Descent and Conjugate Gradient.

9.1 Iterative Optimizer

  • [class] ITERATIVE-OPTIMIZER

    An abstract base class of Gradient Descent and Conjugate Gradient based optimizers that iterate over instances until a termination condition is met.

  • [reader] N-INSTANCES ITERATIVE-OPTIMIZER (:N-INSTANCES = 0)

    The number of instances this optimizer has seen so far. Incremented automatically during optimization.

  • [accessor] TERMINATION ITERATIVE-OPTIMIZER (:TERMINATION = NIL)

    If a number, it's the number of instances to train on in the sense of N-INSTANCES. If N-INSTANCES is equal or greater than this value optimization stops. If TERMINATION is NIL, then optimization will continue. If it is T, then optimization will stop. If it is a function of no arguments, then its return value is processed as if it was returned by TERMINATION.

  • [accessor] ON-OPTIMIZATION-STARTED ITERATIVE-OPTIMIZER (:ON-OPTIMIZATION-STARTED = NIL)

    An event hook with parameters (OPTIMIZER GRADIENT-SOURCE N-INSTANCES). Called after initializations are performed (INITIALIZE-OPTIMIZER*, INITIALIZE-GRADIENT-SOURCE*) but before optimization is started.

  • [accessor] ON-OPTIMIZATION-FINISHED ITERATIVE-OPTIMIZER (:ON-OPTIMIZATION-FINISHED = NIL)

    An event hook with parameters (OPTIMIZER GRADIENT-SOURCE N-INSTANCES). Called when optimization has finished.

  • [accessor] ON-N-INSTANCES-CHANGED ITERATIVE-OPTIMIZER (:ON-N-INSTANCES-CHANGED = NIL)

    An event hook with parameters (OPTIMIZER GRADIENT-SOURCE N-INSTANCES). Called when optimization of a batch of instances is done and N-INSTANCES is incremented.

Now let's discuss a few handy utilities.

  • [function] MONITOR-OPTIMIZATION-PERIODICALLY OPTIMIZER PERIODIC-FNS

    For each periodic function in the list of PERIODIC-FNS, add a monitor to OPTIMIZER's ON-OPTIMIZATION-STARTED, ON-OPTIMIZATION-FINISHED and ON-N-INSTANCES-CHANGED hooks. The monitors are simple functions that just call each periodic function with the event parameters (OPTIMIZER GRADIENT-SOURCE N-INSTANCES). Return OPTIMIZER.

    To log and reset the monitors of the gradient source after every 1000 instances seen by OPTIMIZER:

      (monitor-optimization-periodically optimizer
                                     '((:fn log-my-test-error
                                        :period 2000)
                                       (:fn reset-optimization-monitors
                                        :period 1000
                                        :last-eval 0)))

    Note how we don't pass it's allowed to just pass the initargs for a PERIODIC-FN instead of PERIODIC-FN itself. The :LAST-EVAL 0 bit prevents RESET-OPTIMIZATION-MONITORS from being called at the start of the optimization when the monitors are empty anyway.

  • [generic-function] RESET-OPTIMIZATION-MONITORS OPTIMIZER GRADIENT-SOURCE

    Report the state of MONITORS of OPTIMIZER and GRADIENT-SOURCE and reset their counters. See MONITOR-OPTIMIZATION-PERIODICALLY for an example of how this is used.

  • [method] RESET-OPTIMIZATION-MONITORS (OPTIMIZER ITERATIVE-OPTIMIZER) GRADIENT-SOURCE

    Log the counters of the monitors of OPTIMIZER and GRADIENT-SOURCE and reset them.

  • [generic-function] REPORT-OPTIMIZATION-PARAMETERS OPTIMIZER GRADIENT-SOURCE

    A utility that's often called at the start of optimization (from ON-OPTIMIZATION-STARTED). The default implementation logs the description of GRADIENT-SOURCE (as in DESCRIBE) and OPTIMIZER and calls LOG-MAT-ROOM.

9.2 Cost Function

The function being minimized is often called the cost or the loss function.

  • [generic-function] COST MODEL

    Return the value of the cost function being minimized. Calling this only makes sense in the context of an ongoing optimization (see MINIMIZE). The cost is that of a batch of instances.

  • [function] MAKE-COST-MONITORS MODEL &KEY OPERATION-MODE ATTRIBUTES

    Return a list of MONITOR objects, each associated with one BASIC-COUNTER with attribute :TYPE "cost". Implemented in terms of MAKE-COST-MONITORS*.

  • [generic-function] MAKE-COST-MONITORS* MODEL OPERATION-MODE ATTRIBUTES

    Identical to MAKE-COST-MONITORS bar the keywords arguments. Specialize this to add to support for new model types.

9.3 Gradient Descent

[in package MGL-GD]

Gradient descent is a first-order optimization algorithm. Relying completely on first derivatives, it does not even evaluate the function to be minimized. Let's see how to minimize a numerical lisp function with respect to some of its parameters.

(cl:defpackage :mgl-example-sgd
  (:use #:common-lisp #:mgl))
(in-package :mgl-example-sgd)
;;; Create an object representing the sine function.
(defparameter *diff-fn-1*
  (make-instance 'mgl-diffun:diffun
                 :fn #'sin
                 ;; We are going to optimize its only parameter.
                 :weight-indices '(0)))
;;; Minimize SIN. Note that there is no dataset involved because all
;;; parameters are being optimized.
(minimize (make-instance 'sgd-optimizer :termination 1000)
          *diff-fn-1*
          :weights (make-mat 1))
;;; => A MAT with a single value of about -pi/2.
;;; Create a differentiable function for f(x,y)=(x-y)^2. X is a
;;; parameter whose values come from the DATASET argument passed to
;;; MINIMIZE. Y is a parameter to be optimized (a 'weight').
(defparameter *diff-fn-2*
  (make-instance 'mgl-diffun:diffun
                 :fn (lambda (x y)
                       (expt (- x y) 2))
                 :parameter-indices '(0)
                 :weight-indices '(1)))
;;; Find the Y that minimizes the distance from the instances
;;; generated by the sampler.
(minimize (make-instance 'sgd-optimizer :batch-size 10)
          *diff-fn-2*
          :weights (make-mat 1)
          :dataset (make-instance 'function-sampler
                                  :generator (lambda ()
                                               (list (+ 10
                                                        (gaussian-random-1))))
                                  :max-n-samples 1000))
;;; => A MAT with a single value of about 10, the expected value of
;;; the instances in the dataset.
;;; The dataset can be a SEQUENCE in which case we'd better set
;;; TERMINATION else optimization would never finish.
(minimize (make-instance 'sgd-optimizer :termination 1000)
          *diff-fn-2*
          :weights (make-mat 1)
          :dataset '((0) (1) (2) (3) (4) (5)))
;;; => A MAT with a single value of about 2.5.

We are going to see a number of accessors for optimizer paramaters. In general, it's allowed to SETF real slot accessors (as opposed to readers and writers) at any time during optimization and so is defining a method on an optimizer subclass that computes the value in any way. For example, to decay the learning rate on a per mini-batch basis:

(defmethod learning-rate ((optimizer my-sgd-optimizer))
  (* (slot-value optimizer 'learning-rate)
     (expt 0.998
           (/ (n-instances optimizer) 60000))))

9.3.1 Batch Based Optimizers

First let's see everything common to all batch based optimizers, then discuss SGD Optimizer, Adam Optimizer and Normalized Batch Optimizer. All batch based optimizers are ITERATIVE-OPTIMIZERs, so see Iterative Optimizer too.

  • [accessor] BATCH-SIZE GD-OPTIMIZER (:BATCH-SIZE = 1)

    After having gone through BATCH-SIZE number of inputs, weights are updated. With BATCH-SIZE 1, one gets Stochastics Gradient Descent. With BATCH-SIZE equal to the number of instances in the dataset, one gets standard, 'batch' gradient descent. With BATCH-SIZE between these two extremes, one gets the most practical 'mini-batch' compromise.

  • [accessor] LEARNING-RATE GD-OPTIMIZER (:LEARNING-RATE = 0.1)

    This is the step size along the gradient. Decrease it if optimization diverges, increase it if it doesn't make progress.

  • [accessor] MOMENTUM GD-OPTIMIZER (:MOMENTUM = 0)

    A value in the [0, 1) interval. MOMENTUM times the previous weight change is added to the gradient. 0 means no momentum.

  • [reader] MOMENTUM-TYPE GD-OPTIMIZER (:MOMENTUM-TYPE = :NORMAL)

    One of :NORMAL, :NESTEROV or :NONE. For pure optimization Nesterov's momentum may be better, but it may also increases chances of overfitting. Using :NONE is equivalent to 0 momentum, but it also uses less memory. Note that with :NONE, MOMENTUM is ignored even it it is non-zero.

  • [accessor] WEIGHT-DECAY GD-OPTIMIZER (:WEIGHT-DECAY = 0)

    An L2 penalty. It discourages large weights, much like a zero mean gaussian prior. WEIGHT-DECAY * WEIGHT is added to the gradient to penalize large weights. It's as if the function whose minimum is sought had WEIGHT-DECAY*sum_i{0.5 * WEIGHT_i^2} added to it.

  • [accessor] WEIGHT-PENALTY GD-OPTIMIZER (:WEIGHT-PENALTY = 0)

    An L1 penalty. It encourages sparsity. SIGN(WEIGHT) * WEIGHT-PENALTY is added to the gradient pushing the weight towards negative infinity. It's as if the function whose minima is sought had WEIGHT-PENALTY*sum_i{abs(WEIGHT_i)} added to it. Putting it on feature biases consitutes a sparsity constraint on the features.

  • [reader] USE-SEGMENT-DERIVATIVES-P GD-OPTIMIZER (:USE-SEGMENT-DERIVATIVES-P = NIL)

    Save memory if both the gradient source (the model being optimized) and the optimizer support this feature. It works like this: the accumulator into which the gradient source is asked to place the derivatives of a segment will be SEGMENT-DERIVATIVES of the segment. This allows the optimizer not to allocate an accumulator matrix into which the derivatives are summed.

  • [accessor] AFTER-UPDATE-HOOK GD-OPTIMIZER (:AFTER-UPDATE-HOOK = NIL)

    A list of functions with no arguments called after each weight update.

  • [accessor] BEFORE-UPDATE-HOOK BATCH-GD-OPTIMIZER (:BEFORE-UPDATE-HOOK = NIL)

    A list of functions of no parameters. Each function is called just before a weight update takes place (after accumulated gradients have been divided the length of the batch). Convenient to hang some additional gradient accumulating code on.

SGD Optimizer

  • [class] SGD-OPTIMIZER BATCH-GD-OPTIMIZER

    With BATCH-SIZE 1 this is Stochastic Gradient Descent. With higher batch sizes, one gets mini-batch and Batch Gradient Descent.

    Assuming that ACCUMULATOR has the sum of gradients for a mini-batch, the weight update looks like this:

Read the original on github.com ↗