The fsvd Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The fsvd Reference Manual

This is the fsvd Reference Manual, version 0.0.3, generated automatically by Declt version 2.3 "Robert April" on Wed Mar 14 03:55:02 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

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.


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

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


Previous: , Up: Systems   [Contents][Index]

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

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

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


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 fsvd.asd

Location

fsvd.asd

Systems

fsvd (system)

Packages

fsvd.system


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 fsvd/package.lisp

Parent

fsvd (system)

Location

package.lisp

Packages

fsvd


Previous: , Up: Lisp files   [Contents][Index]

3.1.3 fsvd/fsvd.lisp

Dependency

package.lisp (file)

Parent

fsvd (system)

Location

fsvd.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

4.1 fsvd.system

Source

fsvd.asd

Use List

Previous: , Up: Packages   [Contents][Index]

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
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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

Next: , Previous: , Up: Exported definitions   [Contents][Index]

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)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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
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)


Previous: , Up: Exported definitions   [Contents][Index]

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)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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)


Previous: , Up: Internal definitions   [Contents][Index]

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)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L  
Index Entry  Section

F
File, Lisp, fsvd.asd: The fsvd<dot>asd file
File, Lisp, fsvd/fsvd.lisp: The fsvd/fsvd<dot>lisp file
File, Lisp, fsvd/package.lisp: The fsvd/package<dot>lisp file
fsvd.asd: The fsvd<dot>asd file
fsvd/fsvd.lisp: The fsvd/fsvd<dot>lisp file
fsvd/package.lisp: The fsvd/package<dot>lisp file

L
Lisp File, fsvd.asd: The fsvd<dot>asd file
Lisp File, fsvd/fsvd.lisp: The fsvd/fsvd<dot>lisp file
Lisp File, fsvd/package.lisp: The fsvd/package<dot>lisp file

Jump to:   F   L  

Next: , Previous: , Up: Indexes   [Contents][Index]

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): Exported generic functions
(setf max-n-iterations): Exported generic functions
(setf max-n-svs): Exported generic functions
(setf max-n-svs): Exported generic functions
(setf sv-left): Exported functions
(setf sv-right): Exported functions
(setf svd-in-progress): Exported generic functions
(setf svd-in-progress): Exported generic functions
(setf trace-stream): Internal generic functions
(setf trace-stream): Internal generic functions

A
add-sv-to-approximation: Internal macros
append-to-svd: Internal functions
approximation-me: Internal functions
approximation-rmse: Exported functions

C
compact-sv: Internal functions
copy-sv: Internal functions
create-sv: Internal functions

D
declarationp: Internal functions
dense-column-index: Exported generic functions
dense-column-index: Exported generic functions
dense-row-index: Exported generic functions
dense-row-index: Exported generic functions
do-array-matrix: Internal macros
do-matrix: Exported macros
do-matrix-macro-name: Exported generic functions
do-matrix-macro-name: Exported generic functions
do-matrix-macro-name: Exported generic functions

E
expand-sv: Internal functions

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

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

H
height-of: Exported generic functions
height-of: Exported generic functions

L
load-svd: Exported functions

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

R
read-float-array: Internal functions

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

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

W
width-of: Exported generic functions
width-of: Exported generic functions
write-float: Internal functions
write-float-array: Internal functions

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

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   L   M   R   S   T  
Index Entry  Section

L
left: Exported structures

M
max-n-iterations: Exported classes
max-n-svs: Exported classes

R
right: Exported structures

S
Slot, left: Exported structures
Slot, max-n-iterations: Exported classes
Slot, max-n-svs: Exported classes
Slot, right: Exported structures
Slot, svd-in-progress: Exported classes
Slot, trace-stream: Exported classes
svd-in-progress: Exported classes

T
trace-stream: Exported classes

Jump to:   L   M   R   S   T  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   2  
C   F   L   P   S   T  
Index Entry  Section

2
2d-single-float-array: Internal types

C
Class, limiting-supervisor: Exported classes

F
fsvd: The fsvd system
fsvd: The fsvd package
fsvd.system: The fsvd<dot>system package

L
limiting-supervisor: Exported classes

P
Package, fsvd: The fsvd package
Package, fsvd.system: The fsvd<dot>system package

S
single-float-vector: Internal types
Structure, sv: Exported structures
sv: Exported structures
svd: Exported types
System, fsvd: The fsvd system

T
Type, 2d-single-float-array: Internal types
Type, single-float-vector: Internal types
Type, svd: Exported types

Jump to:   2  
C   F   L   P   S   T