1.10.0
User Documentation for MADlib

This module implements "factor model" for representing an incomplete matrix using a low-rank approximation [1]. Mathematically, this model seeks to find matrices U and V (also referred as factors) that, for any given incomplete matrix A, minimizes:

\[ \|\boldsymbol A - \boldsymbol UV^{T} \|_2 \]

subject to $rank(\boldsymbol UV^{T}) \leq r$, where $\|\cdot\|_2$ denotes the Frobenius norm. Let $A$ be a $m \times n$ matrix, then $U$ will be $m \times r$ and $V$ will be $n \times r$, in dimension, and $1 \leq r \ll \min(m, n)$. This model is not intended to do the full decomposition, or to be used as part of inverse procedure. This model has been widely used in recommendation systems (e.g., Netflix [2]) and feature selection (e.g., image processing [3]).

Function Syntax

Low-rank matrix factorization of an incomplete matrix into two factors.

lmf_igd_run( rel_output,
             rel_source,
             col_row,
             col_column,
             col_value,
             row_dim,
             column_dim,
             max_rank,
             stepsize,
             scale_factor,
             num_iterations,
             tolerance
           )

Arguments

rel_output

TEXT. The name of the table to receive the output.

Output factors matrix U and V are in a flattened format.

RESULT AS (
        matrix_u    DOUBLE PRECISION[],
        matrix_v    DOUBLE PRECISION[],
        rmse        DOUBLE PRECISION
);

Features correspond to row i is matrix_u[i:i][1:r]. Features correspond to column j is matrix_v[j:j][1:r].

rel_source

TEXT. The name of the table containing the input data.

The input matrix> is expected to be of the following form:

{TABLE|VIEW} input_table (
    row    INTEGER,
    col    INTEGER,
    value  DOUBLE PRECISION
)

Input is contained in a table that describes an incomplete matrix, with available entries specified as (row, column, value). The input matrix should be 1-based, which means row >= 1, and col >= 1. NULL values are not expected.

col_row
TEXT. The name of the column containing the row number.
col_column
TEXT. The name of the column containing the column number.
col_value
DOUBLE PRECISION. The value at (row, col).
row_dim (optional)
INTEGER, default: "SELECT max(col_row) FROM rel_source". The number of columns in the matrix.
column_dim (optional)
INTEGER, default: "SELECT max(col_col) FROM rel_source". The number of rows in the matrix.
max_rank
INTEGER, default: 20. The rank of desired approximation.
stepsize (optional)
DOUBLE PRECISION, default: 0.01. Hyper-parameter that decides how aggressive the gradient steps are.
scale_factor (optional)
DOUBLE PRECISION, default: 0.1. Hyper-parameter that decides scale of initial factors.
num_iterations (optional)
INTEGER, default: 10. Maximum number if iterations to perform regardless of convergence.
tolerance (optional)
DOUBLE PRECISION, default: 0.0001. Acceptable level of error in convergence.

Examples
  1. Prepare an input table/view:
    DROP TABLE IF EXISTS lmf_data;
    CREATE TABLE lmf_data (
     row INT,
     col INT,
     val FLOAT8
    );
    
  2. Populate the input table with some data.
    INSERT INTO lmf_data VALUES (1, 1, 5.0);
    INSERT INTO lmf_data VALUES (3, 100, 1.0);
    INSERT INTO lmf_data VALUES (999, 10000, 2.0);
    
  3. Call the lmf_igd_run() stored procedure.
    DROP TABLE IF EXISTS lmf_model;
    SELECT madlib.lmf_igd_run( 'lmf_model',
                               'lmf_data',
                               'row',
                               'col',
                               'val',
                               999,
                               10000,
                               3,
                               0.1,
                               2,
                               10,
                               1e-9
                             );
    
    Example result (the exact result may not be the same).
    NOTICE:
    Finished low-rank matrix factorization using incremental gradient
    DETAIL:
       table : lmf_data (row, col, val)
    Results:
       RMSE = 0.0145966345300041
    Output:
       view : SELECT * FROM lmf_model WHERE id = 1
     lmf_igd_run
     -----------
               1
     (1 row)
    
  4. Sanity check of the result. You may need a model id returned and also indicated by the function lmf_igd_run(), assuming 1 here:
    SELECT array_dims(matrix_u) AS u_dims, array_dims(matrix_v) AS v_dims
    FROM lmf_model
    WHERE id = 1;
    
    Result:
         u_dims    |     v_dims
     --------------+----------------
      [1:999][1:3] | [1:10000][1:3]
     (1 row)
    
  5. Query the result value.
    SELECT matrix_u[2:2][1:3] AS row_2_features
    FROM lmf_model
    WHERE id = 1;
    
    Example output (the exact result may not be the same):
                           row_2_features
     ---------------------------------------------------------
      {{1.12030523084104,0.522217971272767,0.0264869043603539}}
     (1 row)
    
  6. Make prediction of a missing entry (row=2, col=7654).
    SELECT madlib.array_dot(
        matrix_u[2:2][1:3],
        matrix_v[7654:7654][1:3]
        ) AS row_2_col_7654
    FROM lmf_model
    WHERE id = 1;
    
    Example output (the exact result may not be the same due the randomness of the algorithm):
       row_2_col_7654
     ------------------
      1.3201582940851
     (1 row)
    

Literature

[1] N. Srebro and T. Jaakkola. “Weighted Low-Rank Approximations.” In: ICML. Ed. by T. Fawcett and N. Mishra. AAAI Press, 2003, pp. 720–727. isbn: 1-57735-189-4.

[2] Simon Funk, Netflix Update: Try This at Home, December 11 2006, http://sifter.org/~simon/journal/20061211.html

[3] J. Wright, A. Ganesh, S. Rao, Y. Peng, and Y. Ma. “Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization.” In: NIPS. Ed. by Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta. Curran Associates, Inc., 2009, pp. 2080–2088. isbn: 9781615679119.