| /* ----------------------------------------------------------------------- *//** |
| * |
| * @file lmf.sql_in |
| * |
| * @brief SQL functions for low-rank matrix factorization |
| * @date June 2012 |
| * |
| * @sa For a brief introduction to Low-rank Matrix Factorization, see the module |
| * description \ref grp_lmf. |
| * |
| *//* ----------------------------------------------------------------------- */ |
| |
| m4_include(`SQLCommon.m4') |
| |
| /** |
| @addtogroup grp_lmf |
| |
| |
| @about |
| |
| 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: |
| \f[ \|\boldsymbol A - \boldsymbol UV^{T} \|_2 \f] |
| subject to \f$rank(\boldsymbol UV^{T}) \leq r\f$, where \f$\|\cdot\|_2\f$ denotes the Frobenius norm. |
| Let \f$A\f$ be a \f$m \times n\f$ matrix, then \f$U\f$ will be \f$m \times r\f$ and \f$V\f$ will be \f$n \times r\f$, in dimension, and \f$1 \leq r \ll \min(m, n)\f$. |
| 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]). |
| |
| |
| @input |
| |
| The <b>input matrix</b> is expected to be of the following form: |
| <pre>{TABLE|VIEW} <em>input_table</em> ( |
| <em>row</em> INTEGER, |
| <em>col</em> INTEGER, |
| <em>value</em> DOUBLE PRECISION |
| )</pre> |
| |
| Input is contained in a table that describes an incomplete matrix, by having available entries specified as (row, column, value). |
| The input matrix is expected to be based 1, which means row >= 1, and col >= 1. |
| NULL values are not expected. |
| |
| |
| @usage |
| |
| Please find descriptions of SQL functions in lmf.sql_in |
| |
| Output factors matrix U and V are in flatten format. |
| <pre>RESULT AS ( |
| matrix_u DOUBLE PRECISION[], |
| matrix_v DOUBLE PRECISION[], |
| rmse DOUBLE PRECISION |
| );</pre> |
| |
| Features correspond to row i is |
| <code>matrix_u[i:i][1:r]</code>. |
| Features correspond to column j is |
| <code>matrix_v[j:j][1:r]</code>. |
| |
| |
| @examp |
| |
| -# Prepare an input table/view: |
| \code |
| CREATE TABLE lmf_data ( |
| column INT, |
| row INT, |
| value FLOAT8 |
| ); |
| \endcode |
| -# Populate the input table with some data. e.g.: |
| \code |
| 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); |
| \endcode |
| -# Call lmf_igd_run() stored procedure, e.g.: |
| \code |
| SELECT madlib.lmf_igd_run( |
| 'lmf_model', -- result table |
| 'lmf_data', -- input table |
| 'row', 'col', 'value', -- table column names |
| 999, -- row dimension |
| 10000, -- column dimension |
| 3, -- rank (number of features) |
| 0.1, -- stepsize |
| 2, -- initial value scale factor |
| 10, -- maximal number of iterations |
| 1e-9); -- error tolerance |
| \endcode |
| Example output (the exact result may not be the same): |
| \code |
| NOTICE: |
| Finished low-rank matrix factorization using incremental gradient |
| DETAIL: |
| * table : lmf_data (row, col, value) |
| Results: |
| * RMSE = 4.31144557397543e-05 |
| Output: |
| * view : SELECT * FROM lmf_model WHERE id = 1 |
| lmf_igd_run |
| ------------- |
| 1 |
| (1 row) |
| \endcode |
| -# Sanity check of the result. You may need a model id returned and also indicated by the function lmf_igd_run(), assuming 1 here, e.g.: |
| \code |
| SELECT array_dims(matrix_u), array_dims(matrix_v) FROM lmf_model WHERE id = 1; |
| \endcode |
| Example output: |
| \code |
| array_dims | array_dims |
| --------------+---------------- |
| [1:999][1:3] | [1:10000][1:3] |
| (1 row) |
| \endcode |
| -# Query the result value, e.g.: |
| \code |
| SELECT matrix_u[2:2][1:3] AS row_2_features FROM lmf_model WHERE id = 1; |
| \endcode |
| Example output (the exact result may not be the same): |
| \code |
| row_2_features |
| ---------------------------------------------------------- |
| {{0.51117920037359,0.169582297094166,0.837417622096837}} |
| (1 row) |
| \endcode |
| |
| |
| @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. |
| |
| */ |
| |
| CREATE TYPE MADLIB_SCHEMA.lmf_result AS ( |
| matrix_u DOUBLE PRECISION[], |
| matrix_v DOUBLE PRECISION[], |
| rmse DOUBLE PRECISION |
| ); |
| |
| -------------------------------------------------------------------------- |
| -- create SQL functions for IGD optimizer |
| -------------------------------------------------------------------------- |
| CREATE FUNCTION MADLIB_SCHEMA.lmf_igd_transition( |
| state DOUBLE PRECISION[], |
| row_num SMALLINT, |
| column_num SMALLINT, |
| val DOUBLE PRECISION, |
| previous_state DOUBLE PRECISION[], |
| row_dim SMALLINT, |
| column_dim SMALLINT, |
| max_rank SMALLINT, |
| stepsize DOUBLE PRECISION, |
| scale_factor DOUBLE PRECISION) |
| RETURNS DOUBLE PRECISION[] |
| AS 'MODULE_PATHNAME' |
| LANGUAGE C IMMUTABLE; |
| |
| CREATE FUNCTION MADLIB_SCHEMA.lmf_igd_merge( |
| state1 DOUBLE PRECISION[], |
| state2 DOUBLE PRECISION[]) |
| RETURNS DOUBLE PRECISION[] |
| AS 'MODULE_PATHNAME' |
| LANGUAGE C IMMUTABLE STRICT; |
| |
| CREATE FUNCTION MADLIB_SCHEMA.lmf_igd_final( |
| state DOUBLE PRECISION[]) |
| RETURNS DOUBLE PRECISION[] |
| AS 'MODULE_PATHNAME' |
| LANGUAGE C IMMUTABLE STRICT; |
| |
| /** |
| * @internal |
| * @brief Perform one iteration of the incremental gradient |
| * method for computing low-rank matrix factorization |
| */ |
| CREATE AGGREGATE MADLIB_SCHEMA.lmf_igd_step( |
| /*+ row_num */ SMALLINT, |
| /*+ column_num */ SMALLINT, |
| /*+ val */ DOUBLE PRECISION, |
| /*+ previous_state */ DOUBLE PRECISION[], |
| /*+ row_dim */ SMALLINT, |
| /*+ column_dim */ SMALLINT, |
| /*+ max_rank */ SMALLINT, |
| /*+ stepsize */ DOUBLE PRECISION, |
| /*+ scale_factor */ DOUBLE PRECISION) ( |
| STYPE=DOUBLE PRECISION[], |
| SFUNC=MADLIB_SCHEMA.lmf_igd_transition, |
| -- m4_ifdef(`__GREENPLUM__',`PREFUNC=MADLIB_SCHEMA.lmf_igd_merge,') |
| FINALFUNC=MADLIB_SCHEMA.lmf_igd_final, |
| INITCOND='{0,0,0,0,0,0,0,0,0}' |
| ); |
| |
| CREATE FUNCTION MADLIB_SCHEMA.internal_lmf_igd_distance( |
| /*+ state1 */ DOUBLE PRECISION[], |
| /*+ state2 */ DOUBLE PRECISION[]) |
| RETURNS DOUBLE PRECISION AS |
| 'MODULE_PATHNAME' |
| LANGUAGE c IMMUTABLE STRICT; |
| |
| CREATE FUNCTION MADLIB_SCHEMA.internal_lmf_igd_result( |
| /*+ state */ DOUBLE PRECISION[]) |
| RETURNS MADLIB_SCHEMA.lmf_result AS |
| 'MODULE_PATHNAME' |
| LANGUAGE c IMMUTABLE STRICT; |
| |
| |
| CREATE FUNCTION MADLIB_SCHEMA.internal_execute_using_lmf_igd_args( |
| sql VARCHAR, INTEGER, INTEGER, INTEGER, DOUBLE PRECISION, |
| DOUBLE PRECISION, INTEGER, DOUBLE PRECISION |
| ) RETURNS VOID |
| IMMUTABLE |
| CALLED ON NULL INPUT |
| LANGUAGE c |
| AS 'MODULE_PATHNAME', 'exec_sql_using'; |
| |
| CREATE FUNCTION MADLIB_SCHEMA.internal_compute_lmf_igd( |
| rel_args VARCHAR, |
| rel_state VARCHAR, |
| rel_source VARCHAR, |
| col_row VARCHAR, |
| col_column VARCHAR, |
| col_value VARCHAR) |
| RETURNS INTEGER |
| AS $$PythonFunction(convex, lmf_igd, compute_lmf_igd)$$ |
| LANGUAGE plpythonu VOLATILE; |
| |
| /** |
| * @brief Low-rank matrix factorization of a incomplete matrix into two factors |
| * |
| * This function takes as input the table representation of a incomplete matrix |
| * in the sparse (i, j, value) format and decomposes it into the specified set |
| * of most significant features of matrices of U and V matrix. The input matrix |
| * is expected to have dimension [1:row_dim][1:column_dim], but in sparse |
| * format. |
| * |
| * @param rel_output Name of the table that the factors will be appended to |
| * @param rel_source Name of the table/view with the source data |
| * @param col_row Name of the column containing cell row number |
| * @param col_column Name of the column containing cell column number |
| * @param col_value Name of the column containing cell value |
| * @param row_dim Maximum number of rows of input |
| * @param column_dim Maximum number of columns of input |
| * @param max_rank Rank of desired approximation |
| * @param stepsize Hyper-parameter that decides how aggressive that the gradient steps are |
| * @param scale_factor Hyper-parameter that decides scale of initial factors |
| * @param num_iterations Maximum number if iterations to perform regardless of convergence |
| * @param tolerance Acceptable level of error in convergence. |
| * |
| */ |
| CREATE FUNCTION MADLIB_SCHEMA.lmf_igd_run( |
| rel_output VARCHAR, |
| rel_source REGCLASS, |
| col_row VARCHAR, |
| col_column VARCHAR, |
| col_value VARCHAR, |
| row_dim INTEGER /*+ DEFAULT 'SELECT max(col_row) FROM rel_source' */, |
| column_dim INTEGER /*+ DEFAULT 'SELECT max(col_col) FROM rel_source' */, |
| max_rank INTEGER /*+ DEFAULT 20 */, |
| stepsize DOUBLE PRECISION /*+ DEFAULT 0.01 */, |
| scale_factor DOUBLE PRECISION /*+ DEFAULT 0.1 */, |
| num_iterations INTEGER /*+ DEFAULT 10 */, |
| tolerance DOUBLE PRECISION /*+ DEFAULT 0.0001 */) |
| RETURNS INTEGER AS $$ |
| DECLARE |
| iteration_run INTEGER; |
| model_id INTEGER; |
| rmse DOUBLE PRECISION; |
| old_messages VARCHAR; |
| BEGIN |
| RAISE NOTICE 'Matrix % to be factorized: % x %', rel_source, row_dim, column_dim; |
| |
| -- We first setup the argument table. Rationale: We want to avoid all data |
| -- conversion between native types and Python code. Instead, we use Python |
| -- as a pure driver layer. |
| old_messages := |
| (SELECT setting FROM pg_settings WHERE name = 'client_min_messages'); |
| EXECUTE 'SET client_min_messages TO warning'; |
| PERFORM MADLIB_SCHEMA.create_schema_pg_temp(); |
| -- Unfortunately, the EXECUTE USING syntax is only available starting |
| -- PostgreSQL 8.4: |
| -- http://www.postgresql.org/docs/8.4/static/plpgsql-statements.html#PLPGSQL-STATEMENTS-EXECUTING-DYN |
| -- We therefore have to emulate. |
| PERFORM MADLIB_SCHEMA.internal_execute_using_lmf_igd_args($sql$ |
| DROP TABLE IF EXISTS pg_temp._madlib_lmf_igd_args; |
| CREATE TABLE pg_temp._madlib_lmf_igd_args AS |
| SELECT |
| $1 AS row_dim, |
| $2 AS column_dim, |
| $3 AS max_rank, |
| $4 AS stepsize, |
| $5 AS scale_factor, |
| $6 AS num_iterations, |
| $7 AS tolerance; |
| $sql$, |
| row_dim, column_dim, max_rank, stepsize, |
| scale_factor, num_iterations, tolerance); |
| EXECUTE 'SET client_min_messages TO ' || old_messages; |
| |
| -- Perform acutal computation. |
| -- Unfortunately, Greenplum and PostgreSQL <= 8.2 do not have conversion |
| -- operators from regclass to varchar/text. |
| iteration_run := MADLIB_SCHEMA.internal_compute_lmf_igd( |
| '_madlib_lmf_igd_args', '_madlib_lmf_igd_state', |
| textin(regclassout(rel_source)), col_row, col_column, col_value); |
| |
| -- create result table if it does not exist |
| BEGIN |
| EXECUTE 'SELECT 1 FROM ' || rel_output || ' LIMIT 0'; |
| EXCEPTION |
| WHEN undefined_table THEN |
| EXECUTE ' |
| CREATE TABLE ' || rel_output || ' ( |
| id SERIAL, |
| matrix_u DOUBLE PRECISION[], |
| matrix_v DOUBLE PRECISION[], |
| rmse DOUBLE PRECISION)'; |
| END; |
| |
| -- A work-around for GPDB not supporting RETURNING for INSERT |
| -- We generate an id using nextval before INSERT |
| EXECUTE ' |
| SELECT nextval(' || quote_literal(rel_output || '_id_seq') ||'::regclass)' |
| INTO model_id; |
| |
| -- output model |
| -- Retrieve result from state table and insert it |
| EXECUTE ' |
| INSERT INTO ' || rel_output || ' |
| SELECT ' || model_id || ', (result).* |
| FROM ( |
| SELECT MADLIB_SCHEMA.internal_lmf_igd_result(_state) AS result |
| FROM _madlib_lmf_igd_state |
| WHERE _iteration = ' || iteration_run || ' |
| ) subq'; |
| |
| EXECUTE ' |
| SELECT rmse |
| FROM ' || rel_output || ' |
| WHERE id = ' || model_id |
| INTO rmse; |
| |
| -- return description |
| RAISE NOTICE ' |
| Finished low-rank matrix factorization using incremental gradient |
| * table : % (%, %, %) |
| Results: |
| * RMSE = % |
| Output: |
| * view : SELECT * FROM % WHERE id = %', |
| rel_source, col_row, col_column, col_value, rmse, rel_output, model_id; |
| |
| RETURN model_id; |
| END; |
| $$ LANGUAGE plpgsql VOLATILE; |
| |
| CREATE FUNCTION MADLIB_SCHEMA.lmf_igd_run( |
| rel_output VARCHAR, |
| rel_source REGCLASS, |
| col_row VARCHAR, |
| col_column VARCHAR, |
| col_value VARCHAR, |
| row_dim INTEGER, |
| column_dim INTEGER, |
| max_rank INTEGER, |
| stepsize DOUBLE PRECISION, |
| scale_factor DOUBLE PRECISION) |
| RETURNS INTEGER AS $$ |
| SELECT MADLIB_SCHEMA.lmf_igd_run($1, $2, $3, $4, $5, $6, $7, $8, $9, $10, 10, 0.0001); |
| $$ LANGUAGE sql VOLATILE; |
| |
| CREATE FUNCTION MADLIB_SCHEMA.lmf_igd_run( |
| rel_output VARCHAR, |
| rel_source REGCLASS, |
| col_row VARCHAR, |
| col_column VARCHAR, |
| col_value VARCHAR, |
| row_dim INTEGER, |
| column_dim INTEGER, |
| max_rank INTEGER, |
| stepsize DOUBLE PRECISION) |
| RETURNS INTEGER AS $$ |
| -- set scale_factor as default 0.1 |
| SELECT MADLIB_SCHEMA.lmf_igd_run($1, $2, $3, $4, $5, $6, $7, $8, $9, 0.1); |
| $$ LANGUAGE sql VOLATILE; |
| |
| CREATE FUNCTION MADLIB_SCHEMA.lmf_igd_run( |
| rel_output VARCHAR, |
| rel_source REGCLASS, |
| col_row VARCHAR, |
| col_column VARCHAR, |
| col_value VARCHAR, |
| row_dim INTEGER, |
| column_dim INTEGER, |
| max_rank INTEGER) |
| RETURNS INTEGER AS $$ |
| -- set stepsize as default 0.01 |
| SELECT MADLIB_SCHEMA.lmf_igd_run($1, $2, $3, $4, $5, $6, $7, $8, 0.01); |
| $$ LANGUAGE sql VOLATILE; |
| |
| CREATE FUNCTION MADLIB_SCHEMA.lmf_igd_run( |
| rel_output VARCHAR, |
| rel_source REGCLASS, |
| col_row VARCHAR, |
| col_column VARCHAR, |
| col_value TEXT) |
| RETURNS INTEGER AS $$ |
| DECLARE |
| row_dim INTEGER; |
| column_dim INTEGER; |
| BEGIN |
| EXECUTE ' |
| SELECT max(' || col_row || '), max(' || col_column || ') |
| FROM ' || textin(regclassout(rel_source)) |
| INTO row_dim, column_dim; |
| |
| RETURN (SELECT MADLIB_SCHEMA.lmf_igd_run($1, $2, $3, $4, $5, row_dim, column_dim, 20)); |
| END; |
| $$ LANGUAGE plpgsql VOLATILE; |
| |
