The fsvd Reference Manual

This is the fsvd Reference Manual, version 0.0.3, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sat Dec 03 21:29:44 2022 GMT+0.

Table of Contents


1 Introduction


2 Systems

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


2.1 fsvd

Simon Funk’s quasi SVD

Author

Gabor Melis

License

MIT

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.

Child Components

3 Files

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


3.1 Lisp


3.1.1 fsvd/fsvd.asd

Source

fsvd.asd.

Parent Component

fsvd (system).

ASDF Systems

fsvd.

Packages

fsvd.system.


3.1.2 fsvd/package.lisp

Source

fsvd.asd.

Parent Component

fsvd (system).

Packages

fsvd.


3.1.3 fsvd/fsvd.lisp

Dependency

package.lisp (file).

Source

fsvd.asd.

Parent Component

fsvd (system).

Public Interface
Internals

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.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

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


5.1 Public Interface


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.


5.1.2 Ordinary functions

Function: approximation-rmse (matrix dense-approximation)
Package

fsvd.

Source

fsvd.lisp.

Function: load-svd (filename)

Return the SVD loaded from FILENAME.

Package

fsvd.

Source

fsvd.lisp.

Function: make-sv (&key left right)
Package

fsvd.

Source

fsvd.lisp.

Function: make-svd ()

Create an empty SVD.

Package

fsvd.

Source

fsvd.lisp.

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.

Function: save-svd (svd filename)

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

Package

fsvd.

Source

fsvd.lisp.

Reader: sv-left (instance)
Writer: (setf sv-left) (instance)
Package

fsvd.

Source

fsvd.lisp.

Target Slot

left.

Reader: sv-right (instance)
Writer: (setf sv-right) (instance)
Package

fsvd.

Source

fsvd.lisp.

Target Slot

right.

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.

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.


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.

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.

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.

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.

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.

Methods
Method: map-matrix (function (array array))
Generic Reader: max-n-iterations (object)
Package

fsvd.

Methods
Reader Method: max-n-iterations ((limiting-supervisor limiting-supervisor))

automatically generated reader method

Source

fsvd.lisp.

Target Slot

max-n-iterations.

Generic Writer: (setf max-n-iterations) (object)
Package

fsvd.

Methods
Writer Method: (setf max-n-iterations) ((limiting-supervisor limiting-supervisor))

automatically generated writer method

Source

fsvd.lisp.

Target Slot

max-n-iterations.

Generic Reader: max-n-svs (object)
Package

fsvd.

Methods
Reader Method: max-n-svs ((limiting-supervisor limiting-supervisor))

automatically generated reader method

Source

fsvd.lisp.

Target Slot

max-n-svs.

Generic Writer: (setf max-n-svs) (object)
Package

fsvd.

Methods
Writer Method: (setf max-n-svs) ((limiting-supervisor limiting-supervisor))

automatically generated writer method

Source

fsvd.lisp.

Target Slot

max-n-svs.

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.

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.

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 Reader: svd-in-progress (object)
Package

fsvd.

Methods
Reader Method: svd-in-progress ((limiting-supervisor limiting-supervisor))

automatically generated reader method

Source

fsvd.lisp.

Target Slot

svd-in-progress.

Generic Writer: (setf svd-in-progress) (object)
Package

fsvd.

Methods
Writer Method: (setf svd-in-progress) ((limiting-supervisor limiting-supervisor))

automatically generated writer method

Source

fsvd.lisp.

Target Slot

svd-in-progress.

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.

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.

Direct superclasses

structure-object.

Direct slots
Slot: left
Type

(simple-array single-float *)

Readers

sv-left.

Writers

(setf sv-left).

Slot: right
Type

(simple-array single-float *)

Readers

sv-right.

Writers

(setf sv-right).


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.

Direct methods
Direct slots
Slot: svd-in-progress
Initform

(fsvd:make-svd)

Readers

svd-in-progress.

Writers

(setf svd-in-progress).

Slot: max-n-iterations
Initargs

:max-n-iterations

Readers

max-n-iterations.

Writers

(setf max-n-iterations).

Slot: max-n-svs
Initargs

:max-n-svs

Readers

max-n-svs.

Writers

(setf max-n-svs).

Slot: trace-stream
Initform

*trace-output*

Initargs

:trace-stream

Readers

trace-stream.

Writers

(setf trace-stream).


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.


5.2 Internals


5.2.1 Macros

Macro: add-sv-to-approximation (&key matrix clip do-matrix)
Package

fsvd.

Source

fsvd.lisp.

Macro: do-array-matrix (((row column value dense-index) matrix) &body body)
Package

fsvd.

Source

fsvd.lisp.

Macro: train/epoch (&key matrix approximation normalization-factor clip do-matrix)
Package

fsvd.

Source

fsvd.lisp.


5.2.2 Ordinary functions

Function: append-to-svd (svd sv)
Package

fsvd.

Source

fsvd.lisp.

Function: approximation-me (matrix dense-approximation)
Package

fsvd.

Source

fsvd.lisp.

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.

Function: copy-sv (instance)
Package

fsvd.

Source

fsvd.lisp.

Function: create-sv (height width &optional value)
Package

fsvd.

Source

fsvd.lisp.

Function: declarationp (form)
Package

fsvd.

Source

fsvd.lisp.

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.

Function: make-v (length initial-element)
Package

fsvd.

Source

fsvd.lisp.

Function: read-float-array (array fd-stream)
Package

fsvd.

Source

fsvd.lisp.

Function: split-body (body)

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

Package

fsvd.

Source

fsvd.lisp.

Function: sv-p (object)
Package

fsvd.

Source

fsvd.lisp.

Function: svd-1 (matrix &key trainer svd supervisor learning-rate0)
Package

fsvd.

Source

fsvd.lisp.

Function: sync->fd (fd-stream)
Package

fsvd.

Source

fsvd.lisp.

Function: sync<-fd (fd-stream)
Package

fsvd.

Source

fsvd.lisp.

Function: write-float (float stream)
Package

fsvd.

Source

fsvd.lisp.

Function: write-float-array (array fd-stream)
Package

fsvd.

Source

fsvd.lisp.


5.2.3 Generic functions

Generic Reader: trace-stream (object)
Package

fsvd.

Methods
Reader Method: trace-stream ((limiting-supervisor limiting-supervisor))

automatically generated reader method

Source

fsvd.lisp.

Target Slot

trace-stream.

Generic Writer: (setf trace-stream) (object)
Package

fsvd.

Methods
Writer Method: (setf trace-stream) ((limiting-supervisor limiting-supervisor))

automatically generated writer method

Source

fsvd.lisp.

Target Slot

trace-stream.


5.2.4 Types

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

fsvd.

Source

fsvd.lisp.

Type: single-float-vector ()
Package

fsvd.

Source

fsvd.lisp.


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   (  
A   C   D   E   F   G   H   L   M   R   S   T   W  
Index Entry  Section

(
(setf max-n-iterations): Public generic functions
(setf max-n-iterations): Public generic functions
(setf max-n-svs): Public generic functions
(setf max-n-svs): Public generic functions
(setf sv-left): Public ordinary functions
(setf sv-right): Public ordinary functions
(setf svd-in-progress): Public generic functions
(setf svd-in-progress): Public generic functions
(setf trace-stream): Private generic functions
(setf trace-stream): Private generic functions

A
add-sv-to-approximation: Private macros
append-to-svd: Private ordinary functions
approximation-me: Private ordinary functions
approximation-rmse: Public ordinary functions

C
compact-sv: Private ordinary functions
copy-sv: Private ordinary functions
create-sv: Private ordinary functions

D
declarationp: Private ordinary functions
dense-column-index: Public generic functions
dense-column-index: Public generic functions
dense-row-index: Public generic functions
dense-row-index: Public generic functions
do-array-matrix: Private macros
do-matrix: Public macros
do-matrix-macro-name: Public generic functions
do-matrix-macro-name: Public generic functions
do-matrix-macro-name: Public generic functions

E
expand-sv: Private ordinary functions

F
Function, (setf sv-left): Public ordinary functions
Function, (setf sv-right): Public ordinary functions
Function, append-to-svd: Private ordinary functions
Function, approximation-me: Private ordinary functions
Function, approximation-rmse: Public ordinary functions
Function, compact-sv: Private ordinary functions
Function, copy-sv: Private ordinary functions
Function, create-sv: Private ordinary functions
Function, declarationp: Private ordinary functions
Function, expand-sv: Private ordinary functions
Function, load-svd: Public ordinary functions
Function, make-sv: Public ordinary functions
Function, make-svd: Public ordinary functions
Function, make-svd-approximator: Public ordinary functions
Function, make-v: Private ordinary functions
Function, read-float-array: Private ordinary functions
Function, save-svd: Public ordinary functions
Function, split-body: Private ordinary functions
Function, sv-left: Public ordinary functions
Function, sv-p: Private ordinary functions
Function, sv-right: Public ordinary functions
Function, svd: Public ordinary functions
Function, svd-1: Private ordinary functions
Function, svd-value: Public ordinary functions
Function, sync->fd: Private ordinary functions
Function, sync<-fd: Private ordinary functions
Function, write-float: Private ordinary functions
Function, write-float-array: Private ordinary functions

G
Generic Function, (setf max-n-iterations): Public generic functions
Generic Function, (setf max-n-svs): Public generic functions
Generic Function, (setf svd-in-progress): Public generic functions
Generic Function, (setf trace-stream): Private generic functions
Generic Function, dense-column-index: Public generic functions
Generic Function, dense-row-index: Public generic functions
Generic Function, do-matrix-macro-name: Public generic functions
Generic Function, height-of: Public generic functions
Generic Function, map-matrix: Public generic functions
Generic Function, max-n-iterations: Public generic functions
Generic Function, max-n-svs: Public generic functions
Generic Function, size-of: Public generic functions
Generic Function, supervise-svd: Public generic functions
Generic Function, svd-in-progress: Public generic functions
Generic Function, trace-stream: Private generic functions
Generic Function, width-of: Public generic functions

H
height-of: Public generic functions
height-of: Public generic functions

L
load-svd: Public ordinary functions

M
Macro, add-sv-to-approximation: Private macros
Macro, do-array-matrix: Private macros
Macro, do-matrix: Public macros
Macro, train/epoch: Private macros
make-sv: Public ordinary functions
make-svd: Public ordinary functions
make-svd-approximator: Public ordinary functions
make-v: Private ordinary functions
map-matrix: Public generic functions
map-matrix: Public generic functions
max-n-iterations: Public generic functions
max-n-iterations: Public generic functions
max-n-svs: Public generic functions
max-n-svs: Public generic functions
Method, (setf max-n-iterations): Public generic functions
Method, (setf max-n-svs): Public generic functions
Method, (setf svd-in-progress): Public generic functions
Method, (setf trace-stream): Private generic functions
Method, dense-column-index: Public generic functions
Method, dense-row-index: Public generic functions
Method, do-matrix-macro-name: Public generic functions
Method, do-matrix-macro-name: Public generic functions
Method, height-of: Public generic functions
Method, map-matrix: Public generic functions
Method, max-n-iterations: Public generic functions
Method, max-n-svs: Public generic functions
Method, size-of: Public generic functions
Method, supervise-svd: Public generic functions
Method, supervise-svd: Public generic functions
Method, supervise-svd: Public generic functions
Method, svd-in-progress: Public generic functions
Method, trace-stream: Private generic functions
Method, width-of: Public generic functions

R
read-float-array: Private ordinary functions

S
save-svd: Public ordinary functions
size-of: Public generic functions
size-of: Public generic functions
split-body: Private ordinary functions
supervise-svd: Public generic functions
supervise-svd: Public generic functions
supervise-svd: Public generic functions
supervise-svd: Public generic functions
sv-left: Public ordinary functions
sv-p: Private ordinary functions
sv-right: Public ordinary functions
svd: Public ordinary functions
svd-1: Private ordinary functions
svd-in-progress: Public generic functions
svd-in-progress: Public generic functions
svd-value: Public ordinary functions
sync->fd: Private ordinary functions
sync<-fd: Private ordinary functions

T
trace-stream: Private generic functions
trace-stream: Private generic functions
train/epoch: Private macros

W
width-of: Public generic functions
width-of: Public generic functions
write-float: Private ordinary functions
write-float-array: Private ordinary functions