aurnmf {rnnmf} | R Documentation |
nmf .
Description
Additive update Non-negative matrix factorization with regularization.
Usage
aurnmf(
Y,
L,
R,
W_0R = NULL,
W_0C = NULL,
lambda_1L = 0,
lambda_1R = 0,
lambda_2L = 0,
lambda_2R = 0,
gamma_2L = 0,
gamma_2R = 0,
tau = 0.1,
annealing_rate = 0.01,
check_optimal_step = TRUE,
zero_tolerance = 1e-12,
max_iterations = 1000L,
min_xstep = 1e-09,
on_iteration_end = NULL,
verbosity = 0
)
Arguments
Y |
an |
L |
an |
R |
an |
W_0R |
the row space weighting matrix.
This should be a positive definite non-negative symmetric |
W_0C |
the column space weighting matrix.
This should be a positive definite non-negative symmetric |
lambda_1L |
the scalar |
lambda_1R |
the scalar |
lambda_2L |
the scalar |
lambda_2R |
the scalar |
gamma_2L |
the scalar |
gamma_2R |
the scalar |
tau |
the starting shrinkage factor applied to the step length.
Should be a value in |
annealing_rate |
the rate at which we scale the shrinkage factor towards 1.
Should be a value in |
check_optimal_step |
if TRUE, we attempt to take the optimal step length in the given direction. If not, we merely take the longest feasible step in the step direction. |
zero_tolerance |
values of |
max_iterations |
the maximum number of iterations to perform. |
min_xstep |
the minimum L-infinity norm of the step taken. Once the step falls under this value, we terminate. |
on_iteration_end |
an optional function that is called at the end of
each iteration. The function is called as
|
verbosity |
controls whether we print information to the console. |
Details
Attempts to factor given non-negative matrix Y
as the product LR
of two non-negative matrices. The objective function is Frobenius norm
with \ell_1
and \ell_2
regularization terms.
We seek to minimize the objective
\frac{1}{2}tr((Y-LR)' W_{0R} (Y-LR) W_{0C}) + \lambda_{1L} |L| + \lambda_{1R} |R| + \frac{\lambda_{2L}}{2} tr(L'L) + \frac{\lambda_{2R}}{2} tr(R'R) + \frac{\gamma_{2L}}{2} tr((L'L) (11' - I)) + \frac{\gamma_{2R}}{2} tr((R'R) (11' - I)),
subject to L \ge 0
and R \ge 0
elementwise,
where |A|
is the sum of the elements of A
and
tr(A)
is the trace of A
.
The code starts from initial estimates and iteratively improves them, maintaining non-negativity. This implementation uses the Lee and Seung step direction, with a correction to avoid divide-by-zero. The iterative step is optionally re-scaled to take the steepest descent in the step direction.
Value
a list with the elements
- L
The final estimate of L.
- R
The final estimate of R.
- Lstep
The infinity norm of the final step in L.
- Rstep
The infinity norm of the final step in R.
- iterations
The number of iterations taken.
- converged
Whether convergence was detected.
Note
This package provides proof of concept code which is unlikely to be fast or robust, and may not solve the optimization problem at hand. User assumes all risk.
Author(s)
Steven E. Pav shabbychef@gmail.com
References
Merritt, Michael, and Zhang, Yin. "Interior-point Gradient Method for Large-Scale Totally Nonnegative Least Squares Problems." Journal of Optimization Theory and Applications 126, no 1 (2005): 191–202. https://scholarship.rice.edu/bitstream/handle/1911/102020/TR04-08.pdf
Pav, S. E. "An Iterative Algorithm for Regularized Non-negative Matrix Factorizations." Forthcoming. (2024)
Lee, Daniel D. and Seung, H. Sebastian. "Algorithms for Non-negative Matrix Factorization." Advances in Neural Information Processing Systems 13 (2001): 556–562. http://papers.nips.cc/paper/1861-algorithms-for-non-negative-matrix-factorization.pdf
See Also
Examples
nr <- 100
nc <- 20
dm <- 4
randmat <- function(nr,nc,...) { matrix(pmax(0,runif(nr*nc,...)),nrow=nr) }
set.seed(1234)
real_L <- randmat(nr,dm)
real_R <- randmat(dm,nc)
Y <- real_L %*% real_R
# without regularization
objective <- function(Y, L, R) { sum((Y - L %*% R)^2) }
objective(Y,real_L,real_R)
L_0 <- randmat(nr,dm)
R_0 <- randmat(dm,nc)
objective(Y,L_0,R_0)
out1 <- aurnmf(Y, L_0, R_0, max_iterations=5e3L,check_optimal_step=FALSE)
objective(Y,out1$L,out1$R)
# with L1 regularization on one side
out2 <- aurnmf(Y, L_0, R_0, lambda_1L=0.1, max_iterations=5e3L,check_optimal_step=FALSE)
# objective does not suffer because all mass is shifted to R
objective(Y,out2$L,out2$R)
list(L1=sum(out1$L),R1=sum(out1$R),L2=sum(out2$L),R2=sum(out2$R))
sum(out2$L)
# with L1 regularization on both sides
out3 <- aurnmf(Y, L_0, R_0, lambda_1L=0.1,lambda_1R=0.1,
max_iterations=5e3L,check_optimal_step=FALSE)
# with L1 regularization on both sides, raw objective suffers
objective(Y,out3$L,out3$R)
list(L1=sum(out1$L),R1=sum(out1$R),L3=sum(out3$L),R3=sum(out3$R))
# example showing how to use the on_iteration_end callback to save iterates.
max_iterations <- 5e3L
it_history <<- rep(NA_real_, max_iterations)
quadratic_objective <- function(Y, L, R) { sum((Y - L %*% R)^2) }
on_iteration_end <- function(iteration, Y, L, R, ...) {
it_history[iteration] <<- quadratic_objective(Y,L,R)
}
out1b <- aurnmf(Y, L_0, R_0, max_iterations=max_iterations, on_iteration_end=on_iteration_end)
# should work on sparse matrices too.
if (require(Matrix)) {
real_L <- randmat(nr,dm,min=-1)
real_R <- randmat(dm,nc,min=-1)
Y <- as(real_L %*% real_R, "sparseMatrix")
L_0 <- as(randmat(nr,dm,min=-0.5), "sparseMatrix")
R_0 <- as(randmat(dm,nc,min=-0.5), "sparseMatrix")
out1 <- aurnmf(Y, L_0, R_0, max_iterations=1e2L,check_optimal_step=TRUE)
}