The fsvd Reference Manual

Table of Contents

The fsvd Reference Manual

This is the fsvd Reference Manual, version 0.0.3, generated automatically by Declt version 3.0 "Montgomery Scott" on Wed Mar 25 18:06:53 2020 GMT+0.

1 Introduction

Funky Singular Value Decomposition

This is a Common Lisp implementation of Simon Funk's quasi svd as
described at http://sifter.org/~simon/journal/20061211.html by Gabor
Melis.

It's under the MIT licence. See COPYING.

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 fsvd

Author

Gabor Melis

License

MIT

Description

Simon Funk’s quasi SVD

Long Description

This is a Common Lisp implementation of Simon
Funk’s quasi svd as described at http://sifter.org/~simon/journal/20061211.html

Version

0.0.3

Source

fsvd.asd (file)

Components

• package.lisp (file)
• fsvd.lisp (file)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 fsvd.asd

Location

fsvd.asd

Systems

fsvd (system)

Packages

fsvd.system

3.1.2 fsvd/package.lisp

Parent

fsvd (system)

Location

package.lisp

Packages

fsvd

3.1.3 fsvd/fsvd.lisp

Dependency

package.lisp (file)

Parent

fsvd (system)

Location

fsvd.lisp

Exported Definitions

• approximation-rmse (function)
• dense-column-index (generic function)
• dense-column-index (method)
• dense-row-index (generic function)
• dense-row-index (method)
• do-matrix (macro)
• do-matrix-macro-name (generic function)
• do-matrix-macro-name (method)
• do-matrix-macro-name (method)
• height-of (generic function)
• height-of (method)
• limiting-supervisor (class)
• load-svd (function)
• make-sv (function)
• make-svd (function)
• make-svd-approximator (function)
• map-matrix (generic function)
• map-matrix (method)
• max-n-iterations (method)
• (setf max-n-iterations) (method)
• max-n-svs (method)
• (setf max-n-svs) (method)
• save-svd (function)
• size-of (generic function)
• size-of (method)
• supervise-svd (generic function)
• supervise-svd (method)
• supervise-svd (method)
• supervise-svd (method)
• sv (structure)
• sv-left (function)
• (setf sv-left) (function)
• sv-right (function)
• (setf sv-right) (function)
• svd (function)
• svd (type)
• svd-in-progress (method)
• (setf svd-in-progress) (method)
• svd-value (function)
• width-of (generic function)
• width-of (method)

Internal Definitions

• 2d-single-float-array (type)
• add-sv-to-approximation (macro)
• append-to-svd (function)
• approximation-me (function)
• compact-sv (function)
• copy-sv (function)
• create-sv (function)
• declarationp (function)
• do-array-matrix (macro)
• expand-sv (function)
• make-v (function)
• read-float-array (function)
• single-float-vector (type)
• split-body (function)
• sv-p (function)
• svd-1 (function)
• sync->fd (function)
• sync<-fd (function)
• trace-stream (method)
• (setf trace-stream) (method)
• train/epoch (macro)
• write-float (function)
• write-float-array (function)

4 Packages

Packages are listed by definition order.

4.1 fsvd.system

Source

fsvd.asd

Use List

• asdf/interface
• common-lisp

4.2 fsvd

This is a Common Lisp implementation of Simon
Funk’s quasi svd as described at http://sifter.org/~simon/journal/20061211.html. There is nothing quasi about it when there are no missing elements in the original matrix and the normalization factor is zero, but that requires a small learning rate. Loss of orthogonality between singular vectors results from using too large learning rates.

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions

• approximation-rmse (function)
• dense-column-index (generic function)
• dense-column-index (method)
• dense-row-index (generic function)
• dense-row-index (method)
• do-matrix (macro)
• do-matrix-macro-name (generic function)
• do-matrix-macro-name (method)
• do-matrix-macro-name (method)
• height-of (generic function)
• height-of (method)
• limiting-supervisor (class)
• load-svd (function)
• make-sv (function)
• make-svd (function)
• make-svd-approximator (function)
• map-matrix (generic function)
• map-matrix (method)
• max-n-iterations (generic function)
• max-n-iterations (method)
• (setf max-n-iterations) (method)
• (setf max-n-iterations) (generic function)
• max-n-svs (generic function)
• max-n-svs (method)
• (setf max-n-svs) (method)
• (setf max-n-svs) (generic function)
• save-svd (function)
• size-of (generic function)
• size-of (method)
• supervise-svd (generic function)
• supervise-svd (method)
• supervise-svd (method)
• supervise-svd (method)
• sv (structure)
• sv-left (function)
• (setf sv-left) (function)
• sv-right (function)
• (setf sv-right) (function)
• svd (function)
• svd (type)
• svd-in-progress (generic function)
• svd-in-progress (method)
• (setf svd-in-progress) (method)
• (setf svd-in-progress) (generic function)
• svd-value (function)
• width-of (generic function)
• width-of (method)

Internal Definitions

• 2d-single-float-array (type)
• add-sv-to-approximation (macro)
• append-to-svd (function)
• approximation-me (function)
• compact-sv (function)
• copy-sv (function)
• create-sv (function)
• declarationp (function)
• do-array-matrix (macro)
• expand-sv (function)
• make-v (function)
• read-float-array (function)
• single-float-vector (type)
• split-body (function)
• sv-p (function)
• svd-1 (function)
• sync->fd (function)
• sync<-fd (function)
• trace-stream (generic function)
• trace-stream (method)
• (setf trace-stream) (method)
• (setf trace-stream) (generic function)
• train/epoch (macro)
• write-float (function)
• write-float-array (function)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Macros

Macro: do-matrix ((ROW COLUMN VALUE DENSE-INDEX) MATRIX) &body BODY

A simple, inefficient implementation of the macro interface to iterate over MATRIX.

Package

fsvd

Source

fsvd.lisp (file)

5.1.2 Functions

Function: approximation-rmse MATRIX DENSE-APPROXIMATION

Package

fsvd

Source

fsvd.lisp (file)

Function: load-svd FILENAME

Return the SVD loaded from FILENAME.

Package

fsvd

Source

fsvd.lisp (file)

Function: make-sv &key (LEFT LEFT) (RIGHT RIGHT)

Package

fsvd

Source

fsvd.lisp (file)

Function: make-svd ()

Create an empty SVD.

Package

fsvd

Source

fsvd.lisp (file)

Function: make-svd-approximator SVD &key MATRIX MAX-N BASE-APPROXIMATOR CLIP

Return a function of (ROW COLUMN) parameters that approximates MATRIX by SVD. The BASE-VALUE for SVD-VALUE is produced by BASE-APPROXIMATOR for the given coordinates, while CLIP is simply passed on. The returned function automatically translates to dense coordinates to query the SVD.

Package

fsvd

Source

fsvd.lisp (file)

Function: save-svd SVD FILENAME

Write the content of SVD to FILENAME in a reasonably compact form.

Package

fsvd

Source

fsvd.lisp (file)

Function: sv-left INSTANCE

Function: (setf sv-left) VALUE INSTANCE

Package

fsvd

Source

fsvd.lisp (file)

Function: sv-right INSTANCE

Function: (setf sv-right) VALUE INSTANCE

Package

fsvd

Source

fsvd.lisp (file)

Function: svd MATRIX &key SVD BASE-APPROXIMATOR LEARNING-RATE NORMALIZATION-FACTOR SUPERVISOR CLIP

Approximate the single-float MATRIX with a quasi singular value decomposition. Each SV of an SVD consists of a left and a right vector. The sum of the outer products of the left and right vectors of its consituent SVs is the approximation provided by an SVD. This SVD is quasi because while the rank of the approximation is N, the singular values are not explicit.

The sparse matrix interface must be supported on MATRIX.

BASE-APPROXIMATOR is a function of row and column. Its values are effectively subtracted from those of MATRIX. Don’t forget to supply the same BASE-APPROXIMATOR to MAKE-SVD-APPROXIMATOR and
SVD-VALUE.

CLIP is a symbol that is fbound to a function that takes a single single-float and returns it clamped into some valid range or leaves it alone.

To make training fast, a new trainer function is compiled for each SVD call using CLIP and DO-MATRIX-MACRO-NAME for MATRIX.

LEARNING-RATE controls the how much weights are drawn towards to optimum at each step. By default the LEARNING-RATE is scaled by 1/MAE* where MAE* is the MAE mean avarage error. To avoid normalization and to have finer grained control one can return learning rate from the supervisor.

The Tikhonov NORMALIZATION-FACTOR penalizes large weights.

After each iteration on a SV and also before adding a new SV SUPERVISE-SVD is invoked on SUPERVISOR. The return value being NIL indicates that the supervisor wants to stop. See SUPERVISE-SVD for details.

Package

fsvd

Source

fsvd.lisp (file)

Function: svd-value SVD ROW COLUMN &key BASE-VALUE CLIP

Return the value of the matrix represented by SVD at ROW and COLUMN. Start the summation from BASE-VALUE and CLIP the current sum to some valid range if any after every pass.

Package

fsvd

Source

fsvd.lisp (file)

5.1.3 Generic functions

Generic Function: dense-column-index MATRIX COLUMN

Number those columns that are not empty from 0. Return NIL for empty columns.

Package

fsvd

Source

fsvd.lisp (file)

Methods

Method: dense-column-index MATRIX COLUMN

Generic Function: dense-row-index MATRIX ROW

Number those rows that are not empty from 0. Return NIL for empty rows.

Package

fsvd

Source

fsvd.lisp (file)

Methods

Method: dense-row-index MATRIX ROW

Generic Function: do-matrix-macro-name MATRIX

Return the name of the macro that provides a
hopefully efficient way to iterate over MATRIX. See DO-MATRIX for an example.

Package

fsvd

Source

fsvd.lisp (file)

Methods

Method: do-matrix-macro-name (ARRAY array)

Method: do-matrix-macro-name MATRIX

Generic Function: height-of MATRIX &key DENSEP

Return the number of rows of MATRIX. If DENSEP return the number of non-empty rows.

Package

fsvd

Source

fsvd.lisp (file)

Methods

Method: height-of (ARRAY array) &key DENSEP

Generic Function: map-matrix FUNCTION MATRIX

Call FUNCTION for each non-empty cell of MATRIX.
FUNCTION is of four parameters: ROW, COLUMN, VALUE and DENSE-INDEX where DENSE-INDEX is akin to a row major index except it doesn’t skip over empty cells. DENSE-INDEX is always less than the SIZE-OF the MATRIX.

Package

fsvd

Source

fsvd.lisp (file)

Methods

Method: map-matrix FUNCTION (ARRAY array)

Generic Function: max-n-iterations OBJECT

Generic Function: (setf max-n-iterations) NEW-VALUE OBJECT

Package

fsvd

Methods

Method: max-n-iterations (LIMITING-SUPERVISOR limiting-supervisor)

automatically generated reader method

Source

fsvd.lisp (file)

Method: (setf max-n-iterations) NEW-VALUE (LIMITING-SUPERVISOR limiting-supervisor)

automatically generated writer method

Source

fsvd.lisp (file)

Generic Function: max-n-svs OBJECT

Generic Function: (setf max-n-svs) NEW-VALUE OBJECT

Package

fsvd

Methods

Method: max-n-svs (LIMITING-SUPERVISOR limiting-supervisor)

automatically generated reader method

Source

fsvd.lisp (file)

Method: (setf max-n-svs) NEW-VALUE (LIMITING-SUPERVISOR limiting-supervisor)

automatically generated writer method

Source

fsvd.lisp (file)

Generic Function: size-of MATRIX

Return the number known cells in MATRIX. This is an upper limit for the dense indices produced by MAP-MATRIX.

Package

fsvd

Source

fsvd.lisp (file)

Methods

Method: size-of (ARRAY array)

Generic Function: supervise-svd SUPERVISOR SVD ITERATION &key BASE-APPROXIMATOR CLIP MATRIX APPROXIMATION &allow-other-keys

This is invoked from SVD on its SUPERVISOR
argument. If ITERATION is NIL then a new SV is about to be added and upon rejecting that and returning NIL the decomposition is finished. When ITERATION is not NIL, it is a non-negative integer that is the index of the current iteration on the last SV of SVD. MATRIX, BASE-APPROXIMATOR, CLIP are passed through verbatim from the SVD call. APPROXIMATION is a single-float vector that parallels MATRIX with dense indices (see MAP-MATRIX). APPROXIMATION is updated when about to start on a new SV.

Its second return value is a list conforming to (&KEY LEARNING-RATE SV) that can be used to change the learning rate dynamically and to initialize or change the compact representation of the current SV.

Package

fsvd

Source

fsvd.lisp (file)

Methods

Method: supervise-svd (SUPERVISOR function) SVD ITERATION &rest ARGS

Method: supervise-svd (SUPERVISOR symbol) SVD ITERATION &rest ARGS

Method: supervise-svd (SUPERVISOR limiting-supervisor) SVD ITERATION &key BASE-APPROXIMATOR CLIP MATRIX APPROXIMATION

Generic Function: svd-in-progress OBJECT

Generic Function: (setf svd-in-progress) NEW-VALUE OBJECT

Package

fsvd

Methods

Method: svd-in-progress (LIMITING-SUPERVISOR limiting-supervisor)

automatically generated reader method

Source

fsvd.lisp (file)

Method: (setf svd-in-progress) NEW-VALUE (LIMITING-SUPERVISOR limiting-supervisor)

automatically generated writer method

Source

fsvd.lisp (file)

Generic Function: width-of MATRIX &key DENSEP

Return the number of columns of MATRIX. If DENSEP return the number of non-empty columns.

Package

fsvd

Source

fsvd.lisp (file)

Methods

Method: width-of (ARRAY array) &key DENSEP

5.1.4 Structures

Structure: sv ()

SV is a pair of vectors. They are not of unit lenght. The singular value is implicitly defined as the product of their euclidean norms.

Package

fsvd

Source

fsvd.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots

Slot: left

Type

(simple-array single-float *)

Readers

sv-left (function)

Writers

(setf sv-left) (function)

Slot: right

Type

(simple-array single-float *)

Readers

sv-right (function)

Writers

(setf sv-right) (function)

5.1.5 Classes

Class: limiting-supervisor ()

Construct an instance, keep it around and while the
SVD is in progress inspect/save SVD-IN-PROGRESS, or set MAX-N-SVS as you see how the learning is going.

Package

fsvd

Source

fsvd.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• supervise-svd (method)
• trace-stream (method)
• trace-stream (method)
• max-n-svs (method)
• max-n-svs (method)
• max-n-iterations (method)
• max-n-iterations (method)
• svd-in-progress (method)
• svd-in-progress (method)

Direct slots

Slot: svd-in-progress

Initform

(fsvd:make-svd)

Readers

svd-in-progress (generic function)

Writers

(setf svd-in-progress) (generic function)

Slot: max-n-iterations

Initargs

:max-n-iterations

Readers

max-n-iterations (generic function)

Writers

(setf max-n-iterations) (generic function)

Slot: max-n-svs

Initargs

:max-n-svs

Readers

max-n-svs (generic function)

Writers

(setf max-n-svs) (generic function)

Slot: trace-stream

Initargs

:trace-stream

Initform

*trace-output*

Readers

trace-stream (generic function)

Writers

(setf trace-stream) (generic function)

5.1.6 Types

Type: svd ()

SVD consists of n SVs - pairs of left and right vector - of the same sizes. The matrix SVD represents in this form is obtained by summing pairwise the outer products of these vectors.

Package

fsvd

Source

fsvd.lisp (file)

5.2 Internal definitions

5.2.1 Macros

Macro: add-sv-to-approximation &key MATRIX CLIP DO-MATRIX

Package

fsvd

Source

fsvd.lisp (file)

Macro: do-array-matrix ((ROW COLUMN VALUE DENSE-INDEX) MATRIX) &body BODY

Package

fsvd

Source

fsvd.lisp (file)

Macro: train/epoch &key MATRIX APPROXIMATION NORMALIZATION-FACTOR CLIP DO-MATRIX

Package

fsvd

Source

fsvd.lisp (file)

5.2.2 Functions

Function: append-to-svd SVD SV

Package

fsvd

Source

fsvd.lisp (file)

Function: approximation-me MATRIX DENSE-APPROXIMATION

Package

fsvd

Source

fsvd.lisp (file)

Function: compact-sv SV MATRIX

Take SV that uses sparse indices of MATRIX and turn it into one that uses dense indices.

Package

fsvd

Source

fsvd.lisp (file)

Function: copy-sv INSTANCE

Package

fsvd

Source

fsvd.lisp (file)

Function: create-sv HEIGHT WIDTH &optional VALUE

Package

fsvd

Source

fsvd.lisp (file)

Function: declarationp FORM

Package

fsvd

Source

fsvd.lisp (file)

Function: expand-sv SV MATRIX

Take SV that uses dense indices of MATRIX and turn it into one that uses normal indices.

Package

fsvd

Source

fsvd.lisp (file)

Function: make-v LENGTH INITIAL-ELEMENT

Package

fsvd

Source

fsvd.lisp (file)

Function: read-float-array ARRAY FD-STREAM

Package

fsvd

Source

fsvd.lisp (file)

Function: split-body BODY

Return the declarations and the rest of the body as separate lists.

Package

fsvd

Source

fsvd.lisp (file)

Function: sv-p OBJECT

Package

fsvd

Source

fsvd.lisp (file)

Function: svd-1 MATRIX &key TRAINER SVD SUPERVISOR LEARNING-RATE0

Package

fsvd

Source

fsvd.lisp (file)

Function: sync->fd FD-STREAM

Package

fsvd

Source

fsvd.lisp (file)

Function: sync<-fd FD-STREAM

Package

fsvd

Source

fsvd.lisp (file)

Function: write-float FLOAT STREAM

Package

fsvd

Source

fsvd.lisp (file)

Function: write-float-array ARRAY FD-STREAM

Package

fsvd

Source

fsvd.lisp (file)

5.2.3 Generic functions

Generic Function: trace-stream OBJECT

Generic Function: (setf trace-stream) NEW-VALUE OBJECT

Package

fsvd

Methods

Method: trace-stream (LIMITING-SUPERVISOR limiting-supervisor)

automatically generated reader method

Source

fsvd.lisp (file)

Method: (setf trace-stream) NEW-VALUE (LIMITING-SUPERVISOR limiting-supervisor)

automatically generated writer method

Source

fsvd.lisp (file)

5.2.4 Types

Type: 2d-single-float-array ()

Package

fsvd

Source

fsvd.lisp (file)

Type: single-float-vector ()

Package

fsvd

Source

fsvd.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types